zncc performance

[jakobs]

Hey, I've noticed there is an undocumented unstructured encoding method. I've tried it out, and it looks like it would consume a lot of memory to decode. Anything above 100 x 100 pixel does not seem practical on my machine

import structuredlight as sl
import matplotlib.pyplot as plt

us = sl.Unstructured()
imlist_pattern = us.generate((100,100), 10, 32)
res = us.decode( imlist_pattern, imlist_pattern )

plt.imshow( res[0] )

Would you share some insights if this method is useful for any real projector sizes like 1920x1080 at all? It seems the memory needed for decoding would be quite excessive.

Also, in any of the other decoding methods, what would you normally recommend?

[elerac]

Hello @jakobs ! Thanks for waiting for my response.

As you mention, my implementation of the ZNCC decoder isn't practical. It requires enormous memory and calculation time.

There are two reasons.

1. Theoretically, calculating all ZNCC values requires a massive cost.
   Our problem is to find the correspondence points between a projector and a camera. To solve that, the ZNCC decoder calculates a zncc value in all combinations of projector-camera, which is (width x height)_projector x (width x height)_camera times. If you use same resolution at 1920x1080, the decoder calculates a zncc value (1920x1080)x(1920x1080)=4299816960000 times. It costs a lot.

2. My implementation in NumPy is inefficient
   You can see my implementation from here. output = ( a.T @ b ) / np.sqrt( aa_sum @ bb_sum.T ) is the bottleneck.
   The shape of ( a.T @ b ) and np.sqrt( aa_sum @ bb_sum.T ) is same as output. It means this code uses more than x2 memory than . And more, memory access efficiency inside the for-loop is low.

def calculate_zncc(a: np.ndarray, b: np.ndarray) -> np.ndarray:
    a = a - np.average(a, axis=0)
    b = b - np.average(b, axis=0)
    aa_sum = np.expand_dims(np.sum(a*a, axis=0), -1)
    bb_sum = np.expand_dims(np.sum(b*b, axis=0), -1)
    output = ( a.T @ b ) / np.sqrt( aa_sum @ bb_sum.T )
    return output

To improve efficiency, I need to reimplement it using C++-like code, such as CPython, Numba, or Pybind11. But I'm so busy.