c++opencvtrigonometryhough-transformhoughlinesp

I need to explain the specific part of the Hough code(opencv/c++)


This part of the Hough Transform is difficult to me.

Why the 16-bit(and 15-bit) shift operations, and wondered what the meaning is '-sin'.

Original code : https://github.com/opencv/opencv/blob/master/modules/imgproc/src/hough.cpp

    a = -ttab[max_n*2+1];
    b = ttab[max_n*2];
    x0 = j;
    y0 = i;
    if( fabs(a) > fabs(b) )
    {
        xflag = 1;
        dx0 = a > 0 ? 1 : -1;
        dy0 = cvRound( b*(1 << shift)/fabs(a) );
        y0 = (y0 << shift) + (1 << (shift-1));
    }
    else
    {
        xflag = 0;
        dy0 = b > 0 ? 1 : -1;
        dx0 = cvRound( a*(1 << shift)/fabs(b) );
        x0 = (x0 << shift) + (1 << (shift-1));
    }

Solution

  • As you might already know, C/C++ int (short and short unsigned) variables are often stored in 16 bits, and C/C++ arrays store their elements in successive positions in RAM memory.

    This means that as long as you know the address of the first array element and the number of bytes per element, you can manually transverse an array by incrementing the pointer value (which is just a 64-bit number).

    To answer your question, they are manually incrementing the pointer value to transverse the set of coordinates using pointers instead of array positions. The shifting operations are just over-optimized ways to increase the pointer by just the right amount (from a binary number perspective).

    I'm not going to discuss why they do that or how this changes between platforms and compilers, but they probably thought this would increase performance in this specific algorithm.

    The "shift" variable is there to easily change the size of an "unsigned int" variable, probably in case they need to compile for different architectures where this variable type is not stored in 2 bytes.

    This is in no way related to the Hough transform, and I would advise against using this specific code to study Hough unless you're interested in contributing to OpenCV. As an alternative, I recommend this very clear Python implementation.