Gray Code Pattern Decoding

1. 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.

---

2. 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.

---

3. Step-by-Step Strategy

4. 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).

2. 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.

3. 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.

4. (Optional) Validation / Bounds

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

---

4. 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).

---

5. 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.