Definitively, this is the right way.

http://www.powerretouche.com/Histogram_Repair_plugin_tutorial.htm

I need an algorithm to do it. I don't found yet something in open source world. 

All suggestion are fine. thanks in advance

Gilles Caulier

I expect (actually I'm quite convinced) that their "algorithm" is adding noise, like I explained in Bug 170169. Very simple, very effective.

Really ? And which type of noise ? 

If noise is added, it will be visible to the image. Right ? This can be confirmed to test photoshop plugin ?

Gilles Caulier

The noise is very subtle, just enough to fill the gaps in the histogram. On a 8-bit display, it is even impossible to see it. Only if you apply curves to the image, the noise may become visible, provided that the image itself is clean. You might try it on an 8-bit gradient. Create an 8-bit gradient, convert to 16-bit, repair the histogram and apply some extreme curve to it. If the gradient repair plugin uses noise, you will see it now. Can anyone try this?

The algorithm for repairing the histogram after 8 -> 16 bit conversion looks like this:

function RepairHistogram()
{
  for every pixel do
  {
    for every channel do
    {
      Pixel[channel].value += ( Random() % 256 )
    }
  }
}

Ideally, the histogram repair should be done automatically when converting from 8 to 16 bit. Image filtering plugins (like curves) should temporarily convert the image to 16-bits and apply the noise to produce high quality 8-bit filtered images.

Created attachment 40376 [details]
preview of convert with additional noise

Warning: this patch is not intended to be merged, it only shows what is ment and how it will look. 

When converting up to 16bit this patch fills the gaps between the computated 16bit values. But there is currently one problem: All gaps are filled from the next lower value with noise (to preserve reversible 16bit->8bit conversation after) - the only value can not be spread is highest, 65535, so the weightened count of 65535 to any other value changed.

Jens

Jens, 

You method scan all pixels image to add noise everywhere.

It will be better to scan histogram, find hole in graph and identify place in image where holes are located to limit noise to add in image.

Dik,

Have you tried this patch on your computer and test if globaly, the noisify method is right here ?

Gilles Caulier

You MUST add noise everywhere, because every pixel has holes... It's a statistical thing. I did not test the patch, I can't run SVN checkouts at the moment. Testing is easy though. Just check if:

* The histogram is smooth
* The noise is invisible
* No clipping occurs
* The images degrades gracefully (no banding) when applying a steep curve

If the above checks out, it works.

I just took a quick peek at the patch, and I realized that this patch will make the image slightly brighter. Statistically, it will add 128 to the value of every pixel. I don't know if the brightening will be visible, but here is an improved algorithm:

function RepairHistogram()
{
  for every pixel do
  {
    for every channel do
    {
      // Add noise:
      Pixel[channel].value += ( Random() % 256 ) - 128

      // Fix clipping:
      Pixel[channel].value = MAX(Pixel[channel].value, 0)
      Pixel[channel].value = MIN(Pixel[channel].value, 65535)
    }
  }
}

@DIK: yes, the patch will make the image slightly brighter. This is to preserve full reversibleness with current code when doing a 16bit->8bit downscale again. So you can do as many up/down conversations as you want, the orginal image will stay the same and you do not lost any information.

@Gilles: As DIK already said, you must add noise to every pixel and every color channel. This noise will be clipped when doing 16bit->8bit downscale again. So again, there is no information loss. I know, this sounds a bit weird for the first time. ;o)

I starred again at this.

Currently we have:

get8from16(  0..256) = 0
get8from16(257..513) = 1
get8from16(65278..65534) = 254
get8from16(65535) = 255

As you can see the last value is only build from one source value where are the others build from an interval.

What we do want to have is a uniform quantization:

get8from16(  0..255) = 0
get8from16(256..511) = 1
get8from16(65024..65279) = 254
get8from16(65280..65535) = 255

and the reverse:

get16from8(0) = 0..255
get16from8(1) = 256..511
get16from8(254) = 65024..65279
get16from8(255) = 65280..65535

therefore we have to use a grain of salt.

Created attachment 51915 [details]
patch for the suggested change

Thanks Jens. i tested it, and it work perfectly. Look my screenshot :

http://www.flickr.com/photos/digikam/5020489802/

Gilles Caulier

SVN commit 1179081 by cgilles:

New histogram repair algorithm written by Jens Muller to convert 8 bits image to 16 bits, to limit histogram holes during conversion.
BUGS: 170170


 M  +23 -2     dimg.cpp  


WebSVN link: http://websvn.kde.org/?view=rev&revision=1179081