Is the Leptonica implementation of 'Modified Median Cut' not using the median at all?

Question

I'm playing around a bit with image processing and decided to read up on how color quantization worked and after a bit of reading I found the Modified Median Cut Quantization algorithm.

I've been reading the code of the C implementation in Leptonica library and came across something I thought was a bit odd.

Now I want to stress that I am far from an expert in this area, not am I a math-head, so I am predicting that this all comes down to me not understanding all of it and not that the implementation of the algorithm is wrong at all.

The algorithm states that the vbox should be split along the lagest axis and that it should be split using the following logic

The largest axis is divided by locating the bin with the median pixel (by population), selecting the longer side, and dividing in the center of that side. We could have simply put the bin with the median pixel in the shorter side, but in the early stages of subdivision, this tends to put low density clusters (that are not considered in the subdivision) in the same vbox as part of a high density cluster that will outvote it in median vbox color, even with future median-based subdivisions. The algorithm used here is particularly important in early subdivisions, and 3is useful for giving visible but low population color clusters their own vbox. This has little effect on the subdivision of high density clusters, which ultimately will have roughly equal population in their vboxes.

For the sake of the argument, let's assume that we have a vbox that we are in the process of splitting and that the red axis is the largest. In the Leptonica algorithm, on line 01297, the code appears to do the following

• Iterate over all the possible green and blue variations of the red color
• For each iteration it adds to the total number of pixels (population) it's found along the red axis
• For each red color it sum up the population of the current red and the previous ones, thus storing an accumulated value, for each red

note: when I say 'red' I mean each point along the axis that is covered by the iteration, the actual color may not be red but contains a certain amount of red

So for the sake of illustration, assume we have 9 "bins" along the red axis and that they have the following populations

4 8 20 16 1 9 12 8 8

After the iteration of all red bins, the partialsum array will contain the following count for the bins mentioned above

4 12 32 48 49 58 70 78 86

And total would have a value of 86

Once that's done it's time to perform the actual median cut and for the red axis this is performed on line 01346

It iterates over bins and check they accumulated sum. And here's the part that throws me of from the description of the algorithm. It looks for the first bin that has a value that is greater than total/2

Wouldn't total/2 mean that it is looking for a bin that has a value that is greater than the average value and not the median ? The median for the above bins would be 49

The use of 43 or 49 could potentially have a huge impact on how the boxes are split, even though the algorithm then proceeds by moving to the center of the larger side of where the matched value was..

Another thing that puzzles me a bit is that the paper specified that the bin with the median value should be located, but does not mention how to proceed if there are an even number of bins.. the median would be the result of (a+b)/2 and it's not guaranteed that any of the bins contains that population count. So this is what makes me thing that there are some approximations going on that are negligible because of how the split actually takes part at the center of the larger side of the selected bin.

Sorry if it got a bit long winded, but I wanted to be as thoroughas I could because it's been driving me nuts for a couple of days now ;)

Pest

This question is probably better suited for programmers.stackexchange.com or even math.stackexchange.com – Hilariahilario

Hmm, possibly. What is the rule on cross posting? =) – Pest

Answer 1

In the 9-bin example, 49 is the number of pixels in the first 5 bins. 49 is the median number in the set of 9 partial sums, but we want the median pixel in the set of 86 pixels, which is 43 (or 44), and it resides in the 4th bin.

Inspection of the modified median cut algorithm in colorquant2.c of leptonica shows that the actual cut location for the 3d box does not necessarily occur adjacent to the bin containing the median pixel. The reasons for this are explained in the function medianCutApply(). This is one of the "modifications" to Paul Heckbert's original method. The other significant modification is to make the decision of which 3d box to cut next based on a combination of both population and the product (population * volume), thus permitting splitting of large but sparsely populated regions of color space.

Administer

Answer 2

I do not know the algo, but I would assume your array contains the population of each red; let's explain this with an example:

Assume you have four gradations of red: A,B,C and D And you have the following sequence of red values:

AABDCADBBBAAA

To find the median, you would have to sort them according to red value and take the middle:

    median
      v
AAAAAABBBBCDD

Now let's use their approach:

A:6 => 6 
B:4 => 10
C:1 => 11
D:2 => 13

13/2 = 6.5 => B

I think the mismatch happened because you are counting the population; the average color would be:

(6*A+4*B+1*C+2*D)/13

Currency

Well it's not an accurate comparison to a) the described implementation b) the description of the algorithm in the paper. It's counting population along an axis and since an accumulated value is stored for each point along the axis you would not have to sort. – Pest

To ealborate. Each point a long the axis (say the red one) have an unknown number of variations of the green and blue values as well. That's the population for a given point. For that point, the algorithm stores the calculated population with the accumulated population of all the points prior to the current one. Check my samples above – Pest

By the way its not calculating the average color at this stage, it's deciding where, along the given axis, it should slice it into two parts. It's no calculating an average color (yet) .. all we know is that there is "population" number of pixels occupied in that 3d space – Pest

Oh and the population is grabbed from a histogram, ie. think of it as a lookup table that works like RGB -> Number of pixels that are associated with that exact color – Pest

I've scanned the paper, and I still think the same principle applies, even though it is in 3 dimensions instead of 1 (i.e. RGB instead of R); I googled for a good explanation and might have found one here: micro.magnet.fsu.edu/primer/java/digitalimaging/processing/… – Currency

Exactly, all you need to know is the population, I assume they store it in an array indexed by the color (which is sorted naturally) – Currency

Yes and this algorithm for color reduction is based on the "median cut" where the median along the axis is described to use. The algorithm doesn't appear to look for the media, but the average? Unless I am missing something =) – Pest