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?