filter idea - maximize contrast

Matthew Woehlke mw_triad at
Tue Oct 14 01:37:28 CEST 2008

I thought I'd solicit opinions here first before making this an 
"official idea" and dumping it on the wiki...

Something I've done occasionally in rawstudio is to improve the contrast 
in an image by effectively attempting to flattening the histogram. It 
occurred to me that this might make an interesting filter (not to 
mention that it's not terribly complicated as an algorithm, but hard to 
do by hand).

Basically, the idea is this:

1. Build a histogram of the image (O(1) memory, O(N) cpu).
2. Initialize <high-in> and <low-in> to 1.0 and 0.0, similar with -out.
3. Determine the median of the histogram, that is, the value which most 
closely satisfies an equal number of pixels less than that value (and 
greater than <low-in>) compared to pixels greater than that value (and 
less than <high-in>).
4. Map that value to an output of 0.5 * (<high-out> + <low-out>).
5. Repeat 3-5 twice for appropriate high- and low- (O(log K) complexity 
where K is the bit depth; IOW, basic binary division of labor).

This looks surprisingly good for some images (and quite poor for others 
;-) ). For i8 and i16 color spaces, it would likely be best to do all of 
the above in one thread to build a map table (which can be saved in 128k 
of storage) and apply it in parallel. For i32 and f* it is probably 
required to build a list of all values (O(n) memory), sort it using some 
stable sort (preferably with some form of diffusion-based sampling), 
then output based on the position in the list.

The problem, of course, is that updates would be horridly slow :-). (For 
i8 and i16 you could probably optimize by feeding it the old data and 
new data; you can then generate the histogram more quickly by "removing" 
the old data and appending the new.)

An alternative of course is to have something that would produce a curve 
for the B/C filter using the above method.

Please do not quote my e-mail address unobfuscated in message bodies.
"NT was a marketing name that stood for New Technology, but it was still 
an amusing coincidence that WNT was VMS with each letter replaced by the 
next one."
   -- Jeremy Reimer

More information about the kimageshop mailing list