Otsu's Method

[Rei]

Download :

Otsu.zip

It will be installed under Effects\Stylize.

Algorithm by Nobuyuki Otsu
Code ported from ImageJ plugin by me
Original Java code by Hugo MARTIN
Made with the CodeLab plugin for Paint.NET
 
Source code :

Hidden Content:

 

static readonly int NB_LEVEL_GRAY = 256;
bool isFirst = true;
int threshold;

byte getGrayscaleValue(ColorBgra pixel){
    return (byte) (0.2126*pixel.R + 0.7152*pixel.G + 0.0722*pixel.;
}

int getOtsuThreshold(Surface src){
    int otsuThreshold = 0;

    /**
     * Otsu threshold determination
     */
    double nbPixels = 0;
    double[] probabilities = new double[NB_LEVEL_GRAY];
    
    Rectangle[] selectionRectangles = EnvironmentParameters.GetSelection(src.Bounds).GetRegionScansInt();
    foreach(Rectangle r in selectionRectangles){
        nbPixels += r.Width*r.Height;
        for(int i=r.Top;i<r.Bottom;i++)
            for(int j=r.Left; j<r.Right; j++)
                if(src[j,i].A==0) //if the pixel is transparent, don't count it in the total pixels and don't add it to the histogram
                    nbPixels-=1;
                else
                    probabilities[getGrayscaleValue(src[j, i])] += 1;
    }
    for(int i=0; i<NB_LEVEL_GRAY; i++){
        probabilities[i]/=nbPixels;
    }
    
   
    /**
     * interclass variance maximisation
     */
    double max = 0;
    for(int i=0; i<NB_LEVEL_GRAY; i++){
        double w1=0, w2=0, u1=0, u2=0;
        for(int j=0; j<i; j++){
            w1 += probabilities[j];
            u1 += j*probabilities[j];
        }
        
        u1/=w1;
        w2 = 1-w1;
    
        for(int j=i; j<NB_LEVEL_GRAY; j++){
            u2 += j*probabilities[j];
        }
        u2/=w2;
        
        double value= w1*w2*(u1-u2)*(u1-u2);
        if(max<value){
            otsuThreshold = i;
            max = value;
        }
    }
    
    return otsuThreshold;
}

void Render(Surface dst, Surface src, Rectangle rect){
    if (isFirst){ //we don't need to compute the threshold at every call
        threshold = getOtsuThreshold(src);
        isFirst=false;
    }
    
    ColorBgra CurrentPixel;
    for (int y = rect.Top; y < rect.Bottom; y++){
        if (IsCancelRequested) return;
        for (int x = rect.Left; x < rect.Right; x++){
            CurrentPixel = src[x,y];
            if(getGrayscaleValue(CurrentPixel)<threshold)
                CurrentPixel.R=CurrentPixel.G=CurrentPixel.B=0;
            else
                CurrentPixel.R=CurrentPixel.G=CurrentPixel.B=255;
            dst[x,y] = CurrentPixel;
        }
    }
}

Changelog :

Hidden Content:

1.2
Threshold determination doesn't take transparent pixels into account anymore

1.1
Fixed a bug with selections
Increased speed drastically by computing the threshold only once
(Thanks MJW for pointing those out)

1.0
Original release

 
If you use the code above or the original Java code, please give credit to Hugo Martin and provide a link to his GitHub. Edited July 26, 2016 by Rei

[Eli]

Hello Rei, and thank you for sharing.

 

A couple of details, the effects icon is not showing. And, perhaps the effect could be renamed to Otsu's Threshold Method.

 

I do not know the details of how it works (I do not need to know because I would not understand )  but I tried using it different ways and found that the results can be different for the same image. For example, if you flip/mirror the image, the result is not the same.

 

 

I also found that if you add some grain and run the Otsu's effect some detail can be more vissible. Perhaps an option can be added to add some grain.

 

Do you know what type of images can take advantage of this effect?

[MJW]

If the result actually does depend on the image orientation, I think there may be a problem with the implementation, since Otsu's method cares only about the number of pixels at each brightness level, not their locations.

 

EDIT: After looking over the code, I don't notice any reason the result would depend on the orientation when the whole image is selected (or there's no selection). I do however, believe it won't work correctly when there's a selection. I see two problems.

 

First, if the selection is a rectangle, instead of computing the histogram for the pixels within the rectangle, it will compute the histogram for the rectangle of the same size that begins at the upper-right corner. That's because the code has:

    for(int i=0; i<height; i++){
    	for(int j=0; j<width; j++){
    		probabilities[getGrayscaleValue(src[j, i])] += 1/nbPixel;

 The starting points need to be (selection.Left, selection.Top) not (0, 0).

 

Second, if the selection isn't a rectangle, it will still compute the histogram over the selection's bounding rectangle, not the selection.

 

I believe both problems can be solved by code something like:

selectionRectangles = EnvironmentParameters.GetSelection(src.Bounds).GetRegionScansInt();

foreach (Rectangle r in selectionRectangles)
    for (y = r.Top; y < r.Bottom; y++)
        for (x = r.Left; x < r.Right; x++)
            probabilities[getGrayscaleValue(src[x, y])] += 1/nbPixel;

Also, there's no reason to recompute the histogram for each ROI. I suggest something like:

if (firstTime)
{
    threshold = getOtsuThreshold(src, width, height);
    firstTime = false;
}

firstTime should be a "global" variable initialized to true.

 

EDIT 2: The number of pixels in the selection will need to be accumulated, and the histogram divided after the summation. I'll show the corrected version when I get a chance. I'm pretty sure the count for each gray value can be accumulated, the threshold computation performed, then the final threshold computed by dividing by the number of pixels. I don't see that the scaling matters for the threshold computation. Think I'll take that back until I have more time to look at the algorithm.

[Eli]

MJW,

 

This is what I get when I use the effect on the entire image and as you can see it is symmetrical :

 

 

What I meant is that if you select and apply the effect one side at a time you get different results.

 

[MJW]

I now see what you're saying. I'm not quite sure why there's difference, since I'd expect the threshold to be computed over the same pixels. In any case, the way the plugin handles selections is wrong, so that should be fixed. My philosophy has always been that if there's a bug that might potentally cause the problem, fix the bug, and if it fixes the problem, don't spend too much time figuring out exactly why it did. (Though I'm not always successful at suppressing my curiosity.)

[MJW]

I found some pseudo-code (page 160) that seems better suited to writing a version that handles the selection correctly. There's also a C++ version that can be downloaded, though I think it might be easier to just translate the pseudo-code. This version just adds one to the histogram entry instead of some value that requires knowing the total pixels before computing the histogram. Therefore, the total can be computed while computing the histogram.

 

(The pseudo-code contains some stuff about making sure there's only one color channel and using a manual threshold. I'm not sure why that was included in pseudo-code which, to me, should show the algorithm without any implementation-specific fluff.)

[Rei]

If you select and apply the effect one side at a time you get different results.

If I understand correctly, you mirror the image and run the effect on each half individually? If that's the case, you're probably not selecting exactly half of the image, therefore the color distribution is different, and the threshold is slightly different.

If you're doing this on 2 separate images, it's surprising. It could be that PDN doesn't create perfect mirrors, but most likely it's my implementation that's slightly affected by the order in which pixels are analyzed.

 

In any case, the way the plugin handles selections is wrong, so that should be fixed.

I realized that might be a problem as I was copy/pasting/editing, but ended up forgetting about it. I'll try to get a decent version up by next week (going to be busy in the meantime).

 

 

I also found that if you add some grain and run the Otsu's effect some detail can be more vissible. Perhaps an option can be added to add some grain.

[...]

Do you know what type of images can take advantage of this effect?

The results of adding grain are very interesting, however I most likely won't add a grain option. This is because Otsu's method is mostly used in automatic image analysis (typically to extract parts of an image), and the results created by the grain effect are counterproductive in this case. However, if you find an interesting application for this, feel free to write a tutorial.

 

A couple of details, the effects icon is not showing. And, perhaps the effect could be renamed to Otsu's Threshold Method.

Yeah, I don't have an icon yet, I'm trying to think of a good icon idea, and the only one I have looks terrible using PDN's RGB colorspace, I'll try it with Photoshop's Lab colorspace when I have the opportunity. As for the name, "Otsu's method" seems to be standard, but "Otsu's Thresholding" is more explicit and sounds better, thanks for the idea, I'll integrate that into the next update.

 

Thanks MJW and Eli for all the advice and the time you put into this.

 

EDIT :

I just tried running Otsu's Method on a circular selection in the middle of the image, and it worked as intended. I suspect selection management is integrated into the plugin API (or maybe CodeLab). I'll still see what happens when I integrate proper selection management in my code, though.

 

EDIT 2 :

@Eli : I Haven't been able to reproduce the differing results you've described when performing Otsu's Method on two separate identical mirrored images. I suspect the differences you've observed come from inexact selections modifying slightly the color distribution, and therefore changing the threshold.

Edited July 25, 2016 by Rei

[MJW]

I'd be happy to translate the pseudo-code into C# if you'd prefer not to do it yourself. I could either post it here or PM it to you.

[Rei]

I'd be happy to translate the pseudo-code into C# if you'd prefer not to do it yourself. I can either post it here or PM it to you.

No thanks, it's very nice of you but I'd rather do it on my own, I need the practice. It's a very interesting article, it may really come in handy! Thanks for bringing my attention to it.

Edited July 25, 2016 by Rei

[MJW]

EDIT :

I just tried running Otsu's Method on a circular selection in the middle of the image, and it worked as intended. I suspect selection management is integrated into the plugin API (or maybe CodeLab). I'll still see what happens when I integrate proper selection management in my code, though.

 

It will work as far as generally producing a reasonable-looking result, but it won't be the correct result. If you select a rectangle in the center of the window, the threshold value will be based on the pixels in the same-sized rectangle in the upper-left corner. And even if the offset problem is corrected, if you select a circular selection, the threshold will be based on the pixels in the bounding rectangle. There's no possible way any sort of built-in selection management, by the plugin API or CodeLab, can make the threshold depend on the correct pixels if the plugin's computation is done using the wrong pixels.

[Rei]

@MJW

Ahah, you're right about the threshold being computed on the wrong pixels. However, I fail to see why it wouldn't be possible to limit a plugin's ability to read pixels to the selection. Ignoring the problem of non-rectangular selections, if you consider the src Surface to be the selection rather than the whole image, then 0 is effectively selection.Left and selection.Top. I'll trust you however that this is not the case.

[MJW]

If you ignore the problem of non-rectangular selections, then the only problem with the code is that,

    for(int i=0; i<height; i++)
    	for(int j=0; j<width; j++)
    		probabilities[getGrayscaleValue(src[j, i])] += 1/nbPixel;

should be something like,

    for(int i=selection.Top; i<selection.Bottom; i++)
    	for(int j=selection.Left; j<selection.Right; j++)
    		probabilities[getGrayscaleValue(src[j, i])] += 1/nbPixel;

However, I believe the code I gave (which I didn't come up with myself, but swiped from someone else) handles all selections correctly, and isn't overly complex. As far as i know, it's the best way to iterate over the selected pixels.

Rectangle[] selectionRectangles = EnvironmentParameters.GetSelection(src.Bounds).GetRegionScansInt();
totalCount = 0;
foreach (Rectangle r in selectionRectangles)
{
    totalCount += r.Width * r.Height;
    
    for (int y = r.Top; y < r.Bottom; y++)
        for (int x = r.Left; x < r.Right; x++)
            probabilities[getGrayscaleValue(src[x, y])] += 1;
}

(Disclaimer: I haven't tested the above code, so there could possibly be errors, but it should be close.)

[Rei]

Rectangle[] selectionRectangles = EnvironmentParameters.GetSelection(src.Bounds).GetRegionScansInt();

Wow, awesome, thanks! Iterating over this is going to be so much better! Hope I get to work on this soon.

[MJW]

You're certainly welcome.

 

One more thing. If you have a burning desire to handle transparency, I believe the following might work:

Rectangle[] selectionRectangles = EnvironmentParameters.GetSelection(src.Bounds).GetRegionScansInt();
totalCount = 0;
foreach (Rectangle r in selectionRectangles)
    for (int y = r.Top; y < r.Bottom; y++)
        for (int x = r.Left; x < r.Right; x++)
        {
            double alpha = src[x, y].A
            probabilities[getGrayscaleValue(src[x, y])] += alpha;
            totalCount += alpha;
        }

I'm not completely sure doing that that makes sense, though.

 

(You could, of course, just compute the histogram, then afterward get the total count by summing the histogram entries in a separate loop.)

[Ego Eram Reputo]

I think this thread should be moved to the plugin development section while the plugin is undergoing development. Once the plugin is ready for public release the thread can be moved back (or a new one started).

Moved.

[Rei]

Updated to 1.2.

For some reason, all the beginning of my post (up to the download section) disappears sometimes when I edit my post, and a bunch of links to the Wikipedia page of Otsu just fill the post. It's the third time that this happens, so I'm not redoing it until the final release, unless I find a way to view older versions.

[toe_head2001]

A tiny suggestion for the first line: 

static readonly int NB_LEVEL_GRAY = 256;

a const would be more appropriate than a static readonly in this case.

const int NB_LEVEL_GRAY = 256;

Not that a makes any real difference.

[Rei]

A tiny suggestion for the first line: 

static readonly int NB_LEVEL_GRAY = 256;

a const would be more appropriate than a static readonly in this case.

const int NB_LEVEL_GRAY = 256;

Not that a makes any real difference.

Thanks! I'll integrate that in the next version. I was suspecting there was a better modifier that I didn't know of for this.

[Rei]

A tiny suggestion for the first line: 

static readonly int NB_LEVEL_GRAY = 256;

a const would be more appropriate than a static readonly in this case.

const int NB_LEVEL_GRAY = 256;

Not that a makes any real difference.

Thanks! I'll integrate that in the next version. I was suspecting there was a better modifier that I didn't know of for this.

[Rick Brewster]

I've always thought C# was a little silly with how it requires 'const', instead of just doing the right thing and optimizing the obviously optimizable 'static readonly' fields. Java is smart about optimizing 'static final' (equivalent to C#'s 'static readonly') when the value is a compile-time constant literal.

 

'const' also works for string literals, btw.

 

private const string imaString = "string literal goes here";