Adaptive Thresholding using Integral Image [source]

August 10, 2009
posted to Actionscript, Examples and works
. 15 Comments Tags: , , , , .
Adaptive Thresholding

I have to admit that built in Flash methods is really fast in processing time and I cant beat the speed of blurred adaptive thresholding versions provided by Mario and Saqoosha. I still think it could perform faster… ;) Talking about thresholding result I cant say which one is more accurate – try it yourself.

Demo application (you will need web camera and Flash 10 installed)
See my comparison of thresholded image results

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

var w:int = 320;
var h:int = 240;
var size:int = w * h;
var S:int = w / 8;
var S2:int = S >> 1;
var T:Number = 0.15;
var IT:Number = 1.0 - T;
var integral:Vector.<int> = new Vector.<int>(size, true);
var threshold:Vector.<uint> = new Vector.<uint>(size, true);
 
/**
* @param bmp Input image (should be gray scaled)
* @param dst Result image
*/
 
function IntegralImageThresholding(bmp:BitmapData, dst:BitmapData):void
{
	var data:Vector.<uint> = bmp.getVector(bmp.rect);
	//data.fixed = true;
	var i:int, j:int, diff:int;
	var x1:int, y1:int, x2:int, y2:int, ind1:int, ind2:int, ind3:int;
	var sum:int = 0;
	var ind:int = 0;
 
	while( ind < size )
	{
		sum += data[ind] & 0xFF;
		integral[ind] = sum;
		ind += w;
	}
 
	x1 = 0;
	for( i = 1; i < w; ++i )
	{
		sum = 0;
		ind = i;
		ind3 = ind - S2;
 
		if( i > S ) x1 = i - S;
		diff = i - x1;
		for( j = 0; j < h; ++j )
		{
			sum += data[ind] & 0xFF;
			integral[ind] = integral[int(ind-1)] + sum;
			ind += w;
 
			if(i < S2) continue;
			if(j < S2) continue;
 
			y1 = (j < S ? 0 : j - S);
 
			ind1 = y1 * w;
			ind2 = j * w;
 
			if (((data[ind3]&0xFF)*(diff * (j - y1))) < ((integral[int(ind2 + i)] - integral[int(ind1 + i)] - integral[int(ind2 + x1)] + integral[int(ind1 + x1)])*IT))
			{
				threshold[ind3] = 0x00;
			} else {
				threshold[ind3] = 0xFFFFFF;
			}
			ind3 += w;
		}
	}
 
	y1 = 0;
	for( j = 0; j < h; ++j )
	{
		i = 0;
		y2 = h - 1;
		if( j < h - S2 ) 
		{
			i = w - S2;
			y2 = j + S2;
		}
 
		ind = j * w + i;
		if( j > S2 ) y1 = j - S2;
		ind1 = y1 * w;
		ind2 = y2 * w;
		diff = y2 - y1;
		for( ; i < w; ++i, ++ind )
		{
 
			x1 = ( i < S2 ? 0 : i - S2);
			x2 = i + S2;
 
			// check the border
			if (x2 >= w) x2 = w - 1;
 
			if (((data[ind]&0xFF)*((x2 - x1) * diff)) < ((integral[int(ind2 + x2)] - integral[int(ind1 + x2)] - integral[int(ind2 + x1)] + integral[int(ind1 + x1)])*IT))
			{
				threshold[ind] = 0x00;
			} else {
				threshold[ind] = 0xFFFFFF;
			}
		}
	}
 
	dst.setVector(dst.rect, threshold);
}

15 Responses to “Adaptive Thresholding using Integral Image [source]”

Feed for this Entry Trackback Address
  1. 1 Mario Klingemann
    August 10, 2009 at 5:11 am

    Correct me if I am wrong, but looking at the algorithm I get the impression that in the end calculating the integral image is just summing up the pixels over a certain area (which in your case seems to be a 16th of the image width). Then I see a a simplified distance comparison (taxicab distance?) which decides if the pixel is set or not. It seems that the calculation of the integral image is quite expensive. And from what it does eventually the result is not much different from a box blur. So maybe you could adapt the method and replace the integral image with the blazing fast internal blur.

    If you want to stay with the integral image I would at least get rid of checking the border condition which adds quite some overhead to your internal loop. You could do that by adding a border of a 16th of the image width around your image before the calculation which you crop away afterwards.

  2. 2 Eugene
    August 10, 2009 at 5:30 am

    @Mario you right integral image is kind of summing pixels in special order and the idea was to produce thresholding without blurring, drawing, subtracting etc. Sure I can implement simple blur here for the part of integral computation but I guess it would result in what we already have made by Saqoosha and you except pixel comparison part :)
    Adding border is good idea and I’ve already tried it but failed to archive good performance. (got to try it again more wisely)
    Also as you can see in Demo application you can change the amount of surround pixels to compare without any performance drop – thats the main idea ;)

  3. 3 katopz
    August 10, 2009 at 5:45 am

    as i remember vector fixed length return as true after getVector
    so maybe this can gain some speed

    var data:Vector. = bmp.getVector(bmp.rect);
    data.fixed = true;

    i didn’t try the code yet, just quick idea, not sure it work or not ;)

  4. 4 Eugene
    August 10, 2009 at 5:50 am

    @katopz you right fixed could be set here but it doesn’t result in any performance boost ;) as far as we don’t right anything to data vector…

  5. 5 VK
    August 13, 2009 at 1:00 pm

    я так понимаю, именно это позволит сделать AR более стабильной, да?

  6. 6 Prashanth
    November 16, 2009 at 6:09 am

    I am sorry to ask, but what language is this? Is it possible to get an equivalent C# code

  7. 7 Eugene
    November 16, 2009 at 7:12 am

    @Prashanth I think it is very easy to port it to C#. This is Flash Action Script version.

  8. 8 Prashanth
    November 25, 2009 at 2:45 am

    Hi, I am trying to port this code to C#, but I have a few doubts regarding certain lines of code. It would be helpful if you can explain the meaning to me.
    1. How are you considering the pixels? As x,y or any other way?
    2. var data:Vector. = bmp.getVector(bmp.rect); : what does this do?

  9. 9 Paul
    January 22, 2010 at 8:41 am

    Hey there :) First of all, great work! It’s been really useful for my work. I’m having a problem however. I have a BitmapData containing the current video frame from the webcam. I apply the function you created and it works perfect. However, I don’t want to perform the function on the entire image but only a smaller portion in the image. So i use copyPixels to store it into a new BitmapData object, then pass the new object into the function. However, the new BitmapData becomes black.

    Is there something I am missing or should be doing? Thanks!

  10. 10 Eugene
    January 22, 2010 at 8:57 am

    Hi! I guess you should update other variables to work with new size of the bitmap object. look carefully through the source and find what vars are connected to bitmap object properties.

  11. 11 Willkopf
    February 25, 2010 at 6:52 pm

    Hi everyone. Great work Eugene! I was testing various Edge Detector algorithm for grayscale images, and this code was really useful.
    With your permission, I´d like to post a C# code.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

            public void IntegralThresh(ref int[,] im) //im -&gt; source/dest image
        {
            int h = im.GetLength(0);  //image height
            int w = im.GetLength(1);  //image width
 
            int size = w * h;
            int S = w &gt;&gt; 3;
            int S2 = S &gt;&gt; 1;
            float T = 0.15f;
            float IT = 1.0f - T;
 
            int[] integral = new int[size];
            int[] threshold = new int[size];
            int[] data = new int[size];
 
            //Note: copying source image(im) to a vector to use the same code from Eugene
            int index = 0;
            for (int l = 0; l &lt; h; l++)
                for (int c = 0; c &lt; w; c++)
                    data[index++] = im[l, c];
 
 
            int i, j, diff;
	        int x1, y1, x2, y2, ind1, ind2, ind3;
	        int sum = 0, ind = 0;
 
	        while( ind &lt; size )
	        {
		        sum += data[ind] &amp; 0xFF;
		        integral[ind] = sum;
		        ind += w;
	        }
 
           	x1 = 0;
	        for( i = 1; i  S ) x1 = i - S;
		        diff = i - x1;
		        for( j = 0; j &lt; h; ++j )
		        {
			        sum += data[ind] &amp; 0xFF;
			        integral[ind] = integral[(int)(ind-1)] + sum;
			        ind += w;
 
			        if(i &lt; S2) continue;
			        if(j &lt; S2) continue;
 
			        y1 = (j &lt; S ? 0 : j - S);
 
			        ind1 = y1 * w;
			        ind2 = j * w;
 
			        if (((data[ind3]&amp;0xFF)*(diff * (j - y1))) &lt; ((integral[(int)(ind2 + i)] - integral[(int)(ind1 + i)] - integral[(int)(ind2 + x1)] + integral[(int)(ind1 + x1)])*IT))
			        {
				        threshold[ind3] = 0x00;
			        } else 
                    {
				        threshold[ind3] = 0xFF;
			        }
			        ind3 += w;
		        }
	        }
 	        y1 = 0;
	        for( j = 0; j &lt; h; ++j )
	        {
		        i = 0;
		        y2 = h - 1;
		        if( j  S2 ) y1 = j - S2;
		        ind1 = y1 * w;
		        ind2 = y2 * w;
		        diff = y2 - y1;
		        for( ; i &lt; w; ++i, ++ind )
		        {
 
			        x1 = ( i = w) x2 = w - 1;
 
			        if (((data[ind]&amp;0xFF)*((x2 - x1) * diff)) &lt; ((integral[(int)(ind2 + x2)] - integral[(int)(ind1 + x2)] - integral[(int)(ind2 + x1)] + integral[(int)(ind1 + x1)])*IT))
			        {
				        threshold[ind] = 0x00;
			        } else 
                    {
				        threshold[ind] = 0xFF;
			        }
		        }
	        }
 
            //Note: Copying the vector to dest(im)
            index = 0;
            for (int l = 0; l &lt; h; l++)
                for (int c = 0; c &lt; w; c++)
                    im[l, c] = threshold[index++];
        }
  12. 12 João Real
    April 29, 2010 at 1:14 pm

    I’m building one augmented reality application, using MyARtoolkit C#, and I’m trying to improve the thresholding algorithm. I have tried your code but I’m not getting the same results as you get in the demo. I’m I missing something?

    Thanks in advance

    This is the code:

    public void integralThresh(byte[] in_buf, NyARIntSize i_size,INyARBufferReader i_output) //im -> source/dest image
    {
    int h = i_size.h; //image height
    int w = i_size.w; //image width

    int size = w * h;
    int S = w >> 3;
    int S2 = S >> 1;
    float T = 0.15f;
    float IT = 1.0f – T;

    int[] integral = new int[size];
    int[] threshold = new int[size];
    int[] data = new int[size];
    int bp = 0;
    int aux = 0;
    int[] out_buf = (int[])i_output.getBuffer();

    //Note: copying source image(im) to a vector to use the same code from Eugene
    int index = 0;
    for (int l = 0; l < h; l++)
    for (int c = 0; c < w; c++)
    {
    aux = ((in_buf[bp] & 0xFF) + (in_buf[bp + 1] & 0xFF) + (in_buf[bp + 2] & 0xFF));
    bp += 4;

    data[index++] = aux;
    }

    int i, j, diff;
    int x1, y1, x2, y2, ind1, ind2, ind3 = 0;
    int sum = 0, ind = 0;

    while( ind < size )
    {
    sum += data[ind] & 0xFF;
    integral[ind] = sum;
    ind += w;
    }

    x1 = 0;
    for (i = 1; i S) x1 = i – S;
    diff = i – x1;
    for (j = 0; j < h; ++j)
    {
    sum += data[ind] & 0xFF;
    integral[ind] = integral[(int)(ind - 1)] + sum;
    ind += w;

    if (i < S2) continue;
    if (j < S2) continue;

    y1 = (j < S ? 0 : j – S);

    ind1 = y1 * w;
    ind2 = j * w;

    if (((data[ind3] & 0xFF) * (diff * (j – y1))) < ((integral[(int)(ind2 + i)] – integral[(int)(ind1 + i)] – integral[(int)(ind2 + x1)] + integral[(int)(ind1 + x1)]) * IT))
    {
    threshold[ind3] = 0xFF;// 0×00;
    out_buf[ind3] = 0xFF;// 0×00;
    }
    else
    {
    threshold[ind3] = 0×00;//0xFF;
    out_buf[ind3] = 0×00;//0xFF;
    }
    ind3 += w;
    }
    }

    y1 = 0;
    for( j = 0; j < h; ++j )
    {
    i = 0;
    y2 = h – 1;
    if( j S2 ) y1 = j – S2;
    ind1 = y1 * w;
    ind2 = y2 * w;
    diff = y2 – y1;

    for( ; i < w; ++i, ++ind )
    {

    x1 = (i = w) x2 = w – 1;

    if (((data[ind]&0xFF)*((x2 – x1) * diff)) < ((integral[(int)(ind2 + x2)] – integral[(int)(ind1 + x2)] – integral[(int)(ind2 + x1)] + integral[(int)(ind1 + x1)])*IT))
    {
    threshold[ind] = 0xFF;// 0×00;
    out_buf[ind] = 0xFF;// 0×00;
    } else
    {
    threshold[ind] = 0×00;//0xFF;
    out_buf[ind] = 0×00;//0xFF;
    }
    }
    }

    }
    }

  1. 1 Extended Adaptive Thresholding | astatic notes
    Pingback on Aug 11th, 2009 at 12:21 pm
  2. 2 Playing with chroma key and thresholding in Flash (with Pixel Bender) | Andy Li's Blog
    Pingback on Dec 10th, 2009 at 3:18 am
  3. 3 イナヅマtvログ » 気になるサイト, astatic notes @inspirit
    Pingback on Jan 27th, 2010 at 1:35 am

Leave a Reply