I have read a lot article saying that clip limit is the limit of the slope of CDF. But in OpenCV, that parameter can be set to 0~999..., I don't know the maximum of this parameter, isn't sum of the PDF equal to 1? How could the slope is greater than 1? Another way of saying clip limit is that is the limit to every graylevel's count, so for example, if I set tile to (8,8), there is no way that any graylevel in that tile have over 64 pixel, but if I set limit over 64, the results are still changing. Please enlighten me with any point of view.
1 Answers
So, the way that clip limit is implemented is as follows:
- The probability density function (PDF) is calculated for each possible pixel intensity, let's say we have an 8 bit image, so the PDF is an array with indices 0 to 255. The PDF is calculated by counting the number of pixels in the image with that intensity, so for example, PDF(intensity = 0) = 26 means that there are 26 pixels in the image with an intensity of 0.
- Once the PDF has been calculated, the code loops through each element in the PDF, and determines whether or not that element of the PDF is greater than the clipLimit. So, say for example that the clipLimit is 4, and we start with PDF(0) = 26, which is greater than 4. So, the code "clips" the count of pixels with intensity of 0 at 4 by
clipped = clipped + pdf[i] - clipLimit;, where clipped starts at 0. Then clipped = 0 + 26 - 4 = 22. The code continues to do that for PDF(intensity = 1), PDF(intensity = 2), ... , PDF(intensity = 255). At the end, no individual element of PDF is greater than the clipLimit, and the excess pixel counts have been stored in the variable clipped. (Like what fmw42 said). - Then, the number of clipped pixels is redistributed evenly across the array PDF. For example, say clipped = 128, then roughly every other element of PDF gets a +1 pixel count. So, if PDF(0) = 4, PDF(1) = 2, PDF(2) = 0 after the clipping, then after redistributing it will be PDF(0) = 4+1, PDF(1) = 2, PDF(2) = 0+1. Notice that after redistribution, some of the pixels that were previously at the max, the clipLimit, get pushed up slightly over the clipLimit.
From Wikipedia, the clipLimit is usually set between 3 to 4. When the clip limit is implemented as above, the maximum value of any element in the histogram is limited, and therefore, the maximum slope (i.e. change in intensity) between any two adjacent elements in the histogram is limited.
- An unrealistic but helpful exercise to think about is imagine that all of the pixels in an image of size 1920 x 1080 pixels are of intensity 1, so the beginning of the PDF is PDF(0) = 0, PDF(1) = 2073600, and the rest of the elements of the PDF are 0. Then, the slope of the CDF = (2073600-0)/(1-0) = 2073600.
- However, now imagine that for the same image, we set a clipLimit of 4 and just have one histogram for the whole image. After clipping, the PDF is: PDF(0) = 0, PDF(1) = 4, PDF(2) = 0, and so on. The maximum slope after clipping is (4-0)/(1-0) = 4, which is much smaller than 2073600. After redistribution, each histogram bin gets roughly 8100 more pixels, so it the PDF would be like PDF(0) = 8100, PDF(1) = 8104, PDF(2) = 8100, and so on. Now, the maximum slope of the CDF after clipping and redistribution is (8104-8100)/(1-0) = 4.
As to your questions, the sum of the PDF is indeed 1. However, the array PDF here stores the counts, i.e., the numerators of the PDF. So, for an image of size 1920 x 1080, if the actual PDF is
- Probability(intensity = 0) = 4/(1920x1080) = 4/2073600
- P(intensity = 1) = 2/2073600
- P(intensity = 2) = 0/2073600 ,then the sum of these fractions is indeed 1. This probability density function implemented like in the OpenCV source code would appear in the array PDF as:
- PDF(0) = 4
- PDF(1) = 2
- PDF(2) = 0 ,and these elements do not sum to 1 without their denominator.
For the implementation of the code, refer to the OpenCV source code. As a footnote, I made some simplifications about the implementation of the redistribution but hopefully it should be easier to understand.
Related