LocalHistogramEqualization bugs?

[mschuster]

Hi, I hope it is OK to post this here.

Occasionally I notice some strangeness on the right hand edge of my images processed with LHE.

I found a copy of the code on Zbynek's site, so I took a look to see if I could find the problem.

Here is a list of things I found:

1) In InitHistogram() and AdvanceHistogram(), the kernel is mirrored at the edges of the image. The mirror code has bugs in both axes. At the upper edge, the Y-axis clip code is off by one. At the upper edge, the X-axis clip code uses image.Height rather than image.Width. This accounts for the strangeness I see.

2) In ClipHistogram(), the code computes a quotient and a remainder for equalization purposes. The loop that equalizes the remainder is off by one. One too many bins are incremented. This introduces a small bias in the results.

3) Also in ClipHistogram(), the equalization process is iterative. Any remainder on each iteration will increment bin zero. So bin zero "piles up" and a small bias is so introduced. An easy solution would be to do a binary search to find the proper clipping threshold, and then equalize the histogram only once. This runs no faster but avoids all iterative pile up from multiple remainders.

4) ComputeCDF() basically does a table lookup on quantized pixel values. It is a bit annoying that the results are so quantized and that full 32-bit precision is not exploited. I think a simple improvement would be to interpolate the histogram using the pixel's fractional position in its bin. Linear interpolation would probably be sufficient, but higher-order (e.g. cubic) would be easy of course also.

Thanks,
Mike

[Carlos Milovic]

Hi Mike
4) This is what I do in my implementation of HistogramEqualization (global). I was planning to write a CLAHE algorithm based on my implementation, but I dropped the plans. Perhaps I should give it another try.
Anyway, we cannot use the full 32bits to generate the histograms needed. Quantization is needed at least to create the control points of the HE algorithm. Of course, then the actual transfer curve may be piecewise linear functions.

BTW, the AdaptiveContrast tool works in a similar way...

[mschuster]

Hi Carlos,
Yes, I agree and it is what I was thinking: histogram requires quantization but transfer curve can be interpolated. I'm glad to hear other tools work this way.
Mike