Gray Code Pattern Decoding

mediumFREE3D ScanningScanningCV: 3D Reconstruction

Decode Gray code binary patterns to get projector column index.

Structured light scanning projects binary patterns onto objects. Gray code is preferred over standard binary because adjacent columns differ by only one bit, making it robust to slight misalignments.

For N patterns, decode to column index: $col = \sum_{i=0}^{N-1} b_i \cdot 2^{N-1-i}$

This treats the pattern bits as a binary number with the first pattern as the most significant bit. The resulting value indexes into the projector's column space.

Example

Input

decode_gray([1, 0, 1, 0])

Output

Reasoning

Input: patterns holds one bit per projected pattern seen at one camera pixel: $1$ = lit, $0$ = dark. Here $N = 4$ patterns, so the bits are $b_0 = 1,\ b_1 = 0,\ b_2 = 1,\ b_3 = 0$ .
Weights: pattern $i$ carries weight $2^{N-1-i}$ . With $N = 4$ the weights are $2^3 = 8$ , $2^2 = 4$ , $2^1 = 2$ , $2^0 = 1$ . The first pattern is the most significant: it splits the columns in half.
Contributions: only lit patterns add their weight: $1 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 0 \cdot 1 = 8 + 2$ .
Output: $col = 10$ , the integer index of the projector column that lit this pixel. Four patterns can address $2^4 = 16$ columns, numbered $0$ to $15$ , so all four dark gives $0$ and all four lit gives $8 + 4 + 2 + 1 = 15$ .
Notice: the bits are read as ordinary binary, first bit most significant. There is no separate Gray-to-binary conversion, so flipping only the last bit moves the column by exactly $1$ .

Constraints

patterns: list of binary values [b0, b1, ..., bN-1]
Return decoded column index (integer)

Learn this in

3D ReconstructionCV Study Plan Depth Estimation3D Computer Vision

More from CV: 3D Reconstruction

NeRF Ray Samplinghard Surface Integration from Normalsmedium Marching Cubes SDF to Meshmedium ICP Point Cloud Alignmenthard NeRF Positional Encodingmedium

Concept primer

Background Knowledge

In structured light 3D scanning, a projector displays a sequence of binary patterns across the scene while a camera captures the deformed patterns on the object’s surface. Each projector column (or row) is assigned a unique codeword across the sequence of patterns, so by decoding the observed bits at a camera pixel, you can find which projector column illuminated that 3D point. That column index is then used in triangulation with the camera ray to recover 3D geometry.

Gray code is a special binary encoding where adjacent integers differ by exactly one bit. This is useful in 3D scanning because neighboring projector columns project very similar patterns—only one bit changes. If the object boundary shifts slightly or there is a small misalignment, errors are more likely to flip at most one bit instead of multiple bits, which reduces catastrophic decoding errors. However, most geometric computations expect the index in standard binary, so you usually must convert from Gray code to binary, then interpret that binary as an integer column index.

Algorithm/Approach

General pattern:

Input: For each pixel, you have an array of N bits from N captured Gray-code patterns (e.g., g[0..N-1]).
Task: Convert this N-bit Gray code value into the corresponding binary value b[0..N-1], then compute the integer column index using the given formula:

col = \sum_{i=0}^{N-1} b_i \cdot 2^{N-1-i}

Key step: Gray → binary conversion using a prefix XOR rule:
The most significant binary bit is the same as the most significant Gray bit.
Each subsequent binary bit is the XOR of the previous binary bit and the current Gray bit.

Step-by-Step Strategy
Read the N-bit Gray code for the pixel

Assume you have an array g[0..N-1] where g is the most significant bit (MSB).

Convert Gray to Binary

Initialize a binary array b[0..N-1].
Set:

b = g

For each i from 1 to N-1:

b[i] = b[i-1] XOR g[i]

After this loop, b holds the standard binary representation of the column index.

Compute the integer column index

Start with col = 0.
For each bit i from 0 to N-1:

col = (col << 1) + b[i]

This is equivalent to: $col = \sum_{i=0}^{N-1} b_i \cdot 2^{N-1-i}$

Return col.

(Optional) Validation / Bounds

If the projector has W columns, ensure 0 ≤ col < W.
If not, mark as invalid/occluded if the problem specifies.

Common Pitfalls

Bit order confusion:
Be consistent about which index is the MSB. The formula assumes b is the most significant bit.
If the input is given LSB-first, you must reverse or adapt the logic.
Skipping Gray→binary conversion:
Directly interpreting Gray code as binary will give wrong indices. Always convert first.
Using wrong XOR direction:
The rule is: b[i] = b[i-1] XOR g[i], not g[i] XOR g[i-1].
Integer vs. string handling:
If bits come as characters ('0', '1'), convert to integers carefully (bit = ch - '0').
Overflow or type choice:
For large N, ensure the integer type can hold up to 2^N - 1 (e.g., 32-bit int is fine up to N=31, 64-bit up to N=63).

Time & Space Complexity

Time complexity:
Gray→binary conversion: O(N) per pixel.
Binary→integer accumulation: O(N) per pixel.
Total per pixel: O(N).
Space complexity:
If you store both g and b, it’s O(N).
You can also convert in place or accumulate directly to reduce extra space to O(1) auxiliary space.

solution.py

Python 3.13

Test results