Request for exact version of CLAHE

Questions and postings pertaining to the development of ImageMagick, feature enhancements, and ImageMagick internals. ImageMagick source code and algorithms are discussed here. Usage questions which are too arcane for the normal user list should also be posted here.
Locked
zazahohonini
Posts: 5
Joined: 2019-12-28T03:34:11-07:00
Authentication code: 1152

Request for exact version of CLAHE

Post by zazahohonini »

Hello,

First of all, I would like to thank you for all your efforts to produce this wonderful piece of software. I have worked for more than 20 years in
research and ImageMagick has been my go-to tool for several tasks for as many years.

This email concerns the CLAHE option that exists in IM7. In reality there are 2 different versions implemented in different softwares:
1) Original CLAHE which calculates a equalization function for a number of boxes and interpolates between these boxes to get a transfer function for each pixel.
2) Exact CLAHE which calculates the transfer function for each pixel based on a box centered of that pixel. No interpolation is needed

The advantage of "1", which is the version currently implemented in IM7, is speed; the dis-advantage is that it introduces artifacts (stripes) when the interpolation is not able to follow strong gradients in the image.

I would like to ask your help/opinion for making available option 2, also. Any pointers or help implementing this would be greatly appreciated.

Sacha Hony

Here I list some of the background information on method "2":

The available implementations use a trick (sliding window) to gain speed. Basically the histogram centered on the next pixel is updated from the previous histogram by removing just those pixels that moved out of the window and adding just those that entered. Because of this those implementations are sometimes referred to as SWAHE (https://en.wikipedia.org/wiki/Adaptive_ ... ualization). This could be the name used in IM7.

I have found:
Implementation in java: https://imagej.nih.gov/ij/plugins/clahe/CLAHE_.java
Implementation in python: https://github.com/anntzer/clahe

But both of these are impractical (i.e. slow) because of the overhead of the framework.

The scikit-image rank-equalization has a nice figure that demonstrates the sliding window strategy:
https://github.com/scikit-image/scikit- ... generic.py

I have implemented the basic sliding window algorithm (in the y-direction) in python but I am not a good enough C++ programmer to implement it for IM7.

Code: Select all

import numpy as np
def slidehist(img, h, x0, x1, y0, y1):
    # we remove the bottom strip from the previous calculation
    # if it was in the image
    if y0-1 >= 0:
        h = h - np.histogram(
            img[x0:x1, y0-1],
            bins=256,
            range=(0, 256)
        )[0]

    # we add the bottom strip to the previous calculation
    # if it is in the image
    if y1 < img.shape[1]:
        h = h + np.histogram(
            img[x0:x1, y1],
            bins=256,
            range=(0, 256)
        )[0]
    return h

snibgo
Posts: 13034
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Request for exact version of CLAHE

Post by snibgo »

"-clahe" is a recent addition to IM. I haven't yet played with it. My own older implementation is at [Adaptive] Contrast-limited equalisation.

Wikipedia references a SWAHE paper, "Sliding window adaptive histogram equalization of intraoralradiographs: effect on image quality", Sund and Moystad, 2006, is: https://www.researchgate.net/profile/To ... uality.pdf . The "sliding window" feature is merely for performance, with no effect on the actual result.

EDIT: In the paper:
Sund and Moystad wrote:As shown by Pizer et al, the noise can be reduced by clipping the histogram before computing the cumulative histogram. In our implementation the degree of clipping is selected by choosing a value for a dimension-less “contrast limitation parameter” c with a nominal value of 1.
... so they cap the histogram, but apparently without redistribution.

If I understand you correctly, your method (2) is adaptive histogram equalization with contrast limiting. Do you want just capping, or capping with redistribution?

Do you have examples where method (1) gives bad results and method (2) is better?

As you say, method (2) can use sliding windows so the histogram doesn't need building at each pixel. But with contrast limiting, the histogram is capped and counts are redistributed, and the histogram is cumulated. As far as I can see, this needs to be done at each pixel, and can't be optimised. Even with a small histogram of 256 bins, this will be expensive.
snibgo's IM pages: im.snibgo.com

zazahohonini
Posts: 5
Joined: 2019-12-28T03:34:11-07:00
Authentication code: 1152

Re: Request for exact version of CLAHE

Post by zazahohonini »

Dear Snibgo,

Thank you for the quick response. To answer your questions:
Here are three images that show the effect I mention.
input:
Image

output from magick test.jpg -clahe 127x127+128+3 test_clahe.jpg
Image

and the output from imagej/fiji plugin (Process/Enhance Local Contrast (CLAHE))
with options (blocksize 127; histogram bins 256; maximum slope 3.00; no mask and fast option disabled)
Image

You can see artifacts that are related to the size of the blocks.

You are correct that with clipping some part of the calculation has to be done many times, but you can win quite a bit if you separate the histogram
of pixel values and the transfer function:
use the old histogram to calculate the new histogram because sliding the window updates the histogram of pixel values only slightly.
make a copy of the new histogram and use this copy to apply the clipping and make the transfer function valid for this pixel
use the new histogram (not the copy) as the old histogram input for the next slide window.


snibgo
Posts: 13034
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Request for exact version of CLAHE

Post by snibgo »

I can see your images, but thanks for also giving links.

I think the banding is an 8-bit quantisation problem, rather than an inherent feature of the method. You limit the number of bins to 128 or 256. Try increasing this, eg to 4096.

For example, using my eqlTiles script with defaults, so we get a 3x3 array of tiles, on your 8-bit image, the script will use 256 buckets:

Code: Select all

call %PICTBAT%eqlTile testclahe.jpg
Image
Note the banding in the sky.

But if we first convert the input to 16-bit, the script will use 65536 buckets:

Code: Select all

magick testclahe.jpg -depth 16 t.tiff
call %PICTBAT%eqlTile t.tiff
Image
The banding is greatly reduced.
snibgo's IM pages: im.snibgo.com

zazahohonini
Posts: 5
Joined: 2019-12-28T03:34:11-07:00
Authentication code: 1152

Re: Request for exact version of CLAHE

Post by zazahohonini »

Hi Snibgo,

Actually the banding is really related to the interpolation and not to the bit depth. The actual image for which I first noticed the stripes is a 16bit grayscale png that I am not allowed to share. Inside ImageJ I can choose between methods 1 and 2. Using the interpolated method I get these stripes
using method 2, the stripes are not there. The other indication that make me quite sure is that the size of the stripes is directly related to the blocksize parameter.

I tried, as you suggested to play with the number of bins. On my original 16bit image changing the 128 to for example 65535
magick test16bit.jpg -clahe 127x127+128+3 test_clahe.jpg ->
magick test16bit.jpg -clahe 127x127+65535+3 test_clahe.jpg

This does not change to output (stripes are still there with the same intensity).

I think having reasonable number of bins here make sense also because this histogram is there to create the LUT and the LUT should be reasonable smooth even for input images with large bit depth.

Does this make sense?

Thanks,

Sacha

PS. The method 2 in ImageJ is clearly slower that method 1 but it is not unreasonably slow.

snibgo
Posts: 13034
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Request for exact version of CLAHE

Post by snibgo »

Okay, fair enough.

A workaround may be to mask-out areas of no detail.

I may experiment with a script for method (2). It would be too slow for production use, but could prove the quality.
snibgo's IM pages: im.snibgo.com

User avatar
fmw42
Posts: 26383
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Request for exact version of CLAHE

Post by fmw42 »

My redist script does a Gaussian-shaped histogram redistribution (with clipping of the histogram). So it does not suffer from the blocking artifacts. (It runs only on Unix-like systems).

Input:
Image

Code: Select all

redist -f 1 60,60,60 test.jpg test_rdist_60x60x60_f1.jpg
Image

Or my script retinex, produces:

Code: Select all

retinex test.jpg test_retinex.jpg
Image

Or my script space2 (spatially adaptive contrast enhancement), which uses effectively a sliding window at each pixel, produces:

Code: Select all

space2 -b 1.75 -c 2 -m 2 test.jpg test_space2_b1p75_c2_m2.jpg
Image

zazahohonini
Posts: 5
Joined: 2019-12-28T03:34:11-07:00
Authentication code: 1152

Re: Request for exact version of CLAHE

Post by zazahohonini »

Hi fmw42,

You page with scripts is impressive and a great resource. The solutions you suggest are not exactly what I am looking for.

@snibgo, Is there something I can do to help? I have looked at the ImageJ implementation and it looks relatively understandable.

Basically they calculate the LUT for every pixel using a window centered on that pixel. The only tricky part is the speed wich add and subtracts one line or row from the pixel value histogram when sliding the window.

The ImageJ implementation is not forbiddingly slow (~20s) for a 2000x2000 pixel grayscale. But loading the framework takes ages. and I detest their idea of a macro language. Command-line magick is clearly my preference.

Thanks again for your time

Sacha

Locked