filter idea - maximize contrast

[Boudewijn Rempt]

On Tuesday 14 October 2008, Matthew Woehlke wrote:
> 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.

It sounds like a fun plugin: if you want, you could initially develop it in 
Cyrille's krita2plugins module (if he agrees, of course) -- and then, after 
2.0 move it into Krita's source tree. Or you could build it in Krita anyway, 
only disable compilation by default until we've released 2.0.

-- 
Boudewijn Rempt | http://www.valdyas.org