From Hadamard Matrices to Autonomous Vision

Why I returned to Hadamard matrices

After working on Hadamard matrices and incomplete block designs as mathematical objects, I encountered the same structure again in practical autonomous-driving vision. The setting had changed, but the arrangement of plus and minus signs was familiar.

My graduate research in mathematics at the Hebrew University included Hadamard matrices, incomplete block designs, and fractal methods, working with Profs. Perles and Levin. By the time I joined Mobileye, this mathematical structure was already very familiar to me. So when Walsh–Hadamard texture kernels appeared in our DARPA Grand Challenge computer-vision work, the connection was not merely something I noticed only in retrospect — it was part of how I understood the representation at the time.

Looking back, I see a useful connection between those experiences: a discrete structure can be studied for its mathematical properties and later become a practical way to represent visual information.

The mathematical object

A Hadamard matrix H is an n × n matrix whose entries are +1 or −1 and whose rows are mutually orthogonal:

Here I is the identity matrix. Each row has squared length n; distinct rows have dot product zero. Dividing H by √n gives an orthonormal transform. This is a structured binary representation, with two possible signs rather than arbitrary coefficients.

Balance needs a qualification. After sign changes that make the first row and column all +1, every other row has equally many +1 and −1 entries. It must sum to zero to be orthogonal to the first row. This is the normalized convention described in the Indian Statistical Institute lecture notes.

Two distinct rows agree in half their positions and disagree in half. Mapping signs to bits turns that separation into Hamming distance n/2: a direct connection between orthogonality and coding ideas. The appeal is precise control over how representations differ.

Hadamard matrices and block designs

A block design organizes a set of points into subsets called blocks. In a balanced incomplete block design, every block contains the same number of points, every point occurs equally often, and every pair of distinct points occurs together in a fixed number of blocks. “Incomplete” means a block contains fewer than all the points.

One specific construction makes the connection concrete. Start with a normalized Hadamard matrix of order 4t, delete its first row and column, and replace −1 by 0. Interpreting the remaining matrix as an incidence matrix gives a symmetric 2-(4t − 1, 2t − 1, t − 1) design. There are 4t − 1 points and equally many blocks; each block has 2t − 1 points, and each pair occurs in t − 1 blocks.

This is a particular family, not a correspondence between arbitrary incomplete block designs and arbitrary matrices. In this construction, orthogonality becomes a statement about balanced incidence. Ó Catháin’s notes on designs and Hadamard matrices give the underlying relationship.

From matrices to Walsh–Hadamard filters

A row can also be read as a projection: add the signal values under its +1 entries and subtract those under its −1 entries. In the usual power-of-two Walsh–Hadamard transform, a recursively constructed Hadamard basis supplies a full set of these measurements. Walsh ordering arranges the basis by its pattern of sign changes.

For images, products of one-dimensional basis functions form two-dimensional ±1 filters. Applied to a patch, they measure contrasting spatial patterns. The filters are binary-valued; the image intensities and filter responses need not be binary. Collections of responses can serve as texture features.

The arithmetic is attractive: the unnormalized transform uses additions and subtractions, without arbitrary learned multiplications. Its recursive structure yields an O(n log₂ n) fast transform; normalization is a separate scaling step. Ruye Wang’s transform notes show that decomposition. Orthogonality alone does not give every Hadamard matrix this fast factorization, nor does cheap arithmetic guarantee that a feature will discriminate the visual categories we care about.

Mobileye and the DARPA Grand Challenge

Later, at Mobileye, the mathematics unexpectedly reappeared in a very practical setting. I worked directly with Prof. Amnon Shashua, Andras Ferencz, and Yaniv Alon on computer-vision work connected to the DARPA Grand Challenge, in the context of off-road perception and drivable-path understanding.

My contribution was hands-on: implementation, experimentation, and algorithm improvement. I worked closely with Amnon, and through that collaboration with Andras, whose implementation code I worked on and improved; I also collaborated with Yaniv on the project. Walsh–Hadamard texture representations and kernels were part of that work.

Alon, Ferencz, and Shashua’s CVPR 2006 paper provides a public technical reference for the related DARPA Grand Challenge work and its use of Walsh–Hadamard texture features. My account here describes my own implementation and experimental contribution to that work.

The connection I see now

In the mathematical setting, I was working with Hadamard matrices and combinatorial structure. In vision, the same orthogonal sign patterns offered an efficient representation of local appearance. The common structure is what connects these experiences for me.

The broader design-theoretic interpretation is retrospective; the familiarity of the Hadamard structure itself was not. I am not suggesting that block-design theory was explicitly used to select the vision filters, but the shared mathematical structure was already meaningful to me while working on them.

A modern research question

The question I would return to is how much of a structured basis a visual task actually needs. Keeping the full orthonormal transform preserves information; keeping a subset generally does not. Any useful selection rule must therefore be judged against a task and its data.

Design-theoretic constraints might offer a way to organize that selection. Compact visual descriptors, efficient feature transforms, structured sensing, retrieval and representation learning, and hardware-efficient vision are possible settings in which to investigate the idea.

These are directions to test, not established results or a claim of a new invention. A meaningful study would compare constrained selection with simple and learned alternatives at the same feature budget, and measure actual computation as well as task performance. Fewer coefficients alone would not establish a useful speedup.

Can design-theoretic constraints help choose a compact subset of structured Hadamard projections that preserves discriminative information while reducing computation?