Wrong implementation of balanceWhiteSimple

[kqwyf]

Related file

On master branch of opencv_contrib (20190912):

opencv_contrib/modules/xphoto/src/simple_color_balance.cpp

Description

// simple_color_balance.cpp: line 80 to 98

int pos = 0;
float minValue = inputMin - 0.5f;
float maxValue = inputMax + 0.5f;
T val = *it;

float interval = float(maxValue - minValue) / bins;

for (int j = 0; j < depth; ++j)
{
    int currentBin = int((val - minValue + 1e-4f) / interval);
    ++hist[pos + currentBin];

    pos = (pos + currentBin) * bins;

    minValue = minValue + currentBin * interval;
    maxValue = minValue + interval;

    interval /= bins;
}

The algorithm uses a histogram tree to accelerate calculation. However, it seems that there is something wrong with it.

Take a tree of depth = 2 and bins = 16 for example. We number the nodes on the 1st level 0~15, and nodes on the 2nd level 16~(16+255). The nodes on the 1st level of the tree should store the partial sum of values of nodes on the 2nd level. e.g. node 0 contains the sum of values of node 16~31, and node 1 contains the sum of values of node 32~47.

But in this implementation I found mistakes. For example, let pos = 0 and currentBin = 0(i.e. val == minValue), we can see that hist[0] will increase by 1 twice no matter j = 0 or j = 1, which is obviously not what we expected. We expect it to update level 1 when j = 0, and update level 2 when j = 1.

There is the same mistake in the code below.

// simple_color_balance.cpp: line 103 to 129

int p1 = 0, p2 = bins - 1;
int n1 = 0, n2 = total;

float minValue = inputMin - 0.5f;
float maxValue = inputMax + 0.5f;

float interval = (maxValue - minValue) / float(bins);

for (int j = 0; j < depth; ++j)
// searching for s1 and s2
{
    while (n1 + hist[p1] < s1 * total / 100.0f)
    {
        n1 += hist[p1++];
        minValue += interval;
    }
    p1 *= bins;

    while (n2 - hist[p2] > (100.0f - s2) * total / 100.0f)
    {
        n2 -= hist[p2--];
        maxValue -= interval;
    }
    p2 = (p2 + 1) * bins - 1;

    interval /= bins;
}

Question

I'm working to fix it, but I found that the fixed code won't pass the tests. Would you kindly tell me whether the ground truth is generated by the current implementation? If that's true, may I replace it with a new one generated by my fixed implementation?

[mshabunin]

Could you please inject some debug printing after problematic code blocks to verify that histogram is wrong for some simple synthetic images?

Probably we should add more synthetic tests for several different image types and corner cases instead of "comparison with gold" test case.

[kqwyf]

// simple_color_balance.cpp: line 67
int nElements = int(pow((float)bins, (float)depth));
// simple_color_balance.cpp: line 72
std::vector<int> hist(nElements, 0);

Actually from the code above we know that the number of nodes of the tree is less than what we expect (the tree should be of (bins^(depth+1)-bins)/(bins-1) nodes)... So we could not even give a ground truth for hist to verify it.

If we correct nElements first and look for a simple image to verify it, here is a counterexample.

Mat test = Mat::zeros(4,1,CV_8UC1);
test.at<uchar>(0, 0) = 0;
test.at<uchar>(1, 0) = 1;
test.at<uchar>(2, 0) = 16;
test.at<uchar>(3, 0) = 255;

cv::Ptr<cv::xphoto::SimpleWB> wb = cv::xphoto::createSimpleWB();
wb->setInputMin(0);
wb->setInputMax(255);
wb->setOutputMin(0);
wb->setOutputMax(255);

wb->balanceWhite(test, test);

/*
output hist (16 items per line):
3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

expected hist:
2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
*/

BTW, the debug printing is inserted to simple_color_balance.cpp: line 100

printf("hist:\n");
for (int j = 0; j < nElements; j++)
{
    printf("%d ", hist[j]);
    if((j + 1) % 16 == 0) printf("\n");
}

[mshabunin]

We should try an fix it then. I think problematic test should be replaced with several synthetic tests verifying algorithm behavior. If you're going to create a pull request, please target it to branch 3.4, we will merge it to master by ourselves.

BTW, can we use cv::calcHist here?

[kqwyf]

A pull request has been created as #2263 .