platform: CPU： Intel(R) Xeon(R) X5550 Quad Core CPU 2-ways

Analysis of A Remap Bug¶

Wu Zailong email:[email protected]

1.Introduction to the Remap¶

Remap is a mapping function defined as dst (x ,y) = src (map1(x , y).s0 , map1(x , y).s1), map1 is a dual channels matrix. All the matrixes mentioned here are from opencv library. In these matrixes, x stands for column number and y stands for row number. For instance, the element dst(x,y) denotes the xth column and yth row of the dst matrix. map1(x , y).s0 stands for the value of the first channel of map1(x, y), and map1(x , y).s1 stands for the value of the second channel of map1(x, y). Every dst(x,y) has its corresponding map(x,y) in the map matrix at the same places of two matrixes.

2.The Input Case That Triggers the Bug¶

Here is the case that triggers the bug. Data types of src and map1 are 8UC1 and 32FC2, respectively. Bordertype is BODER_CONSTANT. Interpolation option is INTER_NEAREST. Results are incorrect when dst's ROI is larger than 16384.

3. Source Location of the Bug
Here is the source location of the bug: modules/imgproc/src/imgwarp.cpp:2556. It exists in the official version of OpenCV2.4.
Specifically, this is the buggy line (2556) of code:

 map1(Rect(0,0,bcols,brows)).convertTo(bufxy, bufxy.depth());

This should be changed into:

 map1(Rect(x,y,bcols,brows)).convertTo(bufxy, bufxy.depth());

4.Analysis
We start the analysis from imgwarp.cpp:2451:

Mat src = _src.getMat(), map1 = _map1.getMat(), map2 = _map2.getMat();
    //src is the source image，map1 is the matrix of mapping rules.
...//irrelevant code…
Mat dst = _dst.getMat();//dst is the destination  matrix. It has the same size as map1 and the same type as src.
...//irrelevant code…
    const int buf_size = 1 << 14;
    int brows0 = std::min(128, dst.rows);
    int bcols0 = std::min(buf_size/brows0, dst.cols);
brows0 = std::min(buf_size/bcols0, dst.rows);
//here as the size of buf is 2^14，so the biggest value of bcols0*brows0 is 2^14
...
    Mat _bufxy(brows0, bcols0, CV_16SC2), _bufa;//_bufxy is the buffer of map1.
    if( !nnfunc )
      ...
    for( y = 0; y < dst.rows; y += brows0 )
    {
        for( x = 0; x < dst.cols; x += bcols0 )
        {//inner loop，the biggest value of each data processing block is bcols0*brows0
            int brows = std::min(brows0, dst.rows - y);
            int bcols = std::min(bcols0, dst.cols - x);
            Mat dpart(dst, Rect(x, y, bcols, brows));//when the number of the piont of the dst is more than bcols0*brows0, further partitioning of the dst is needed

            Mat bufxy(_bufxy, Rect(0, 0, bcols, brows));//The bufxy is the buffer of map1's each partition, and the map1's partition is corresponding to the dst's.
            if( nnfunc )
            {
                if( map_depth != CV_32F )
                {
 ...
                }
                else if( !planar_input )
                    map1(Rect(0,0,bcols,brows)).convertTo(bufxy, bufxy.depth());
//Here the convertTo processing from map1 to bufxy is starting from (0,0) statically and also doesn't follow the correspondence between map1 and dst. When the double circulation executes at the second time, the error is occured. Therefore, it should be changed into map1(Rect(x,y,bcols,brows)).convertTo(bufxy, bufxy.depth()) and then we can get the right value. 

                else
                {
                      ...
}
   nnfunc( src, dpart, bufxy, borderType, borderValue );
}
}
...

Now let's explain the algorithm in detail. First of all, the dst matrix is partitioned into blocks with a maximum size of 16384. If dst's ROI size is less than 16384, then the nested loop here only executes once to get the result. If dst's ROI size is larger than 16384, further partitioning is needed. That is, the first block should be 16384 , the next block is brows*bcols(here the brows = std::min(brows0, dst.rows - y)，bcols = std::min(bcols0, dst.cols - x). The specific way of partitioning is shown in the following figure. Note that when partition the dst matrix, partitioning of map1 should be the same with the partitioning of dst in order to make sure that every element in dst gets its corresponding value in map1 matrix.

Fig1 The partition of the dst
Fig1 shows an example of this algorithm. In this example, dst refers to the destination matrix and is partitioned into four blocks according to the rule described above. Sub-matrix A with the vertex coordinate a(x,y) and sub-matrix B with the vertex coordinates b(x,y) are the top-left partition and bottom-right partition respectively. When remapping sub-matirx A, we set x =0, y=0, and the processing codes as follows:

Mat dpart(dst, Rect(x, y, bcols, brows))
...
map1(Rect(0,0,bcols,brows)).convertTo(bufxy, bufxy.depth());
...
nnfunc( src, dpart, bufxy, borderType, borderValue );

As can be seen, the mapping relationship between dst and map1 has not been changed, and remap results are correct. However, results are wrong if we process sub-matrix B using the same code. In this case, the corresponding sub-matrix of map1 should be map1(Rect(x,y, bcols, brows)), not map1(Rect(0,0, bcols, brows)). So the 3rd line code should be changed into: map1(Rect(x,y,bcols,brows)).convertTo(bufxy, bufxy.depth()). After that, the remap function can execute correctly.

    Mat dpart(dst, Rect(x, y, bcols, brows));
    ...
    map1(Rect(0,0,bcols,brows)).convertTo(bufxy, bufxy.depth());
    ...
    nnfunc( src, dpart, bufxy, borderType, borderValue );

We can see here the mapping between dst1 and map1 has changed. The peak point of dst matrix is （bcols0，brows0）, while for map1 matrix is （0,0）statically. Hence the error happens.
The code here should be corrected as follows :

map1(Rect(x,y,bcols,brows)).convertTo(bufxy, bufxy.depth());

After this fix the function executes correctly.