Robotic Vision
Robotic Vision
In a 2-dimensional deBruijn array, we fix a window size (say 2 X 2) and have 2-dimensional array where every subgrid of
How It Works
This interactive demonstrates a 2D de Bruijn pattern. You can move the 2×2 window around the 4×4 grid using the arrow buttons or keyboard arrow keys. The window can wrap around the edges and corners.
Each unique 2×2 pattern you encounter is recorded below. There are exactly 16 possible patterns (2^4), and in a perfect de Bruijn pattern, each appears exactly once as you move the window through all possible positions.
This property makes de Bruijn patterns useful in robotics and computer vision for position encoding, as a robot can determine its exact location by observing just a small window of the pattern.
Cross Patterns
What if we use a different window shape? Let’s try a cross pattern instead of a square:
Unlike the 2×2 window, it turns out that with a cross-shaped window, it’s impossible to create a pattern where every position has a unique signature.
Let’s explore this with two interactive games:
In this randomly generated 4×4 grid, find two locations where the cross pattern (up, down, left, right) is identical.
Color the grid however you like by clicking on cells to toggle between 0 and 1. When you press "Done", the game will find two locations with identical cross patterns.
De Bruijn Combs
A “comb” is a pattern where certain positions are transparent (open blocks) and others are opaque (shaded blocks). Imagine having a 8-length window where the first, second, fourth and eighth positions are exposed and the others are opaque. Now imagine sliding this window over a 16-bit sequence (with wrap-arounds).At every step of the slide, you can read off four bits from the exposed positions. Can you find a 16-bit sequence so that every read is distinct? It turns out that there is exactly one such sequence (not counting cyclic shifts or complements), and you can play with it below.
This opens up a host of puzzles: what about other comb patterns? For a given comb pattern, is it solvable? If yes, how many morally distinct solutions are there?