## Magic moments

Posted on May 20th, 2009 by Benjamin in actionscript, computer vision, image processingSurfing on Wikipedia, I found this article about image moments. To be honest at the beginning it just seemed to me to be some ugly maths . But believe me or not, when I read it in more details I discovered really interesting things .

Basically moments are often used in physic in order to describe mass repartition of a body. You can derive the “idea” in image processing in substituting mass by grey level of pixel. This can give really interesting information about pixels repartition into an image. Indeed, it’s possible to use them in order to find center, orientation and size of a shape into an image. To summary image moments is a way to find all my schema below parameters just with pixels information:

Let’s see how it works and how to implement it in Actionscript.

*(Notice I insert directly in my post Wikipedia article formula for a better readability*.)

For binary or grey-scale image general moments equation for image is the following:

where 0 < x < image width, o< y < image height, and I(x,y) is the pixel value(color or brightness).

For those who are allergic to math don’t worry, it is in fact fairly simple to understand and to implement moments computation. A little loop across images pixels, some little summations and voila . Below the implementation to compute zero moment (m00), first oder moments (m10, m01) and second order moments (m11, m20, m02):

^{?}View Code ACTIONSCRIPT

m00 = m01 = m10 = m11 = m02 = m20 = 0; var x:int; var y:int; var a:Array; var val:Number for(x = 0; x < aData.length; ++x) { a = aData[x]; for(y = 0; y < a.length; ++y) { val = a[y]; m00 += val; m01 += y * val; m10 += x * val; m11 += x * y * val; m02 += y * y * val; m20 += x * x * val; } } |

Moo, zeroth moment, gives the area of the shape for binary image ( or area or sum of grey level for grey-scale images). M1o and Mo1, first order moments, are spatial moments. First order moments don’t have really direct interpretations for an image because they depend of the size of the image. But if you normalize them by M00, it is possible to find the gravity center of the shape in our image( called also centroid because it is not physic) by those fairly simple formula:

Cool we have already the center of our shape!

To find orientation or size of the shape it is not possible to work directly with general moments because they are variants in translation. It just means that wherever is your shape in the image, you will not find the same general moments values. That is why we need to compute also central moments, which are invariant in translation. We can deduce them from the general moments and the center of gravity:

In computing some intermediate values:

We can construct the following covariance matrix for the image:

What’s that? . Well covariance matrix is a particular matrix to measure the variance of a points distribution. Those who know statistics know covariance into probabilities distribution. Those who know physic can make an analogy with inertia tensor which give inertia axis of an object (long time ago for me). Those who do not know both and who already have an headache just admit, and it is what I discovered too, you can find object axes when you calculate the eigenvectors and eigenvalues of the covariance matrix. What’s that again? To quickly (and badly?) explain it, eigenvectors are just some particular vectors linked to a matrix A. They have the property to be just scaled when you apply to them the transformation represented by A . Intuitively I guess it is why they represent object axes, but I am not sure of this For the covariance matrix eigenvalues are:

Well finally the interesting part is that you can deduct from that the 3 geometric elements I was looking for at the beginning of this post.

So the angle between the x-axis and the major is given by:

And the length and the width of the shape , given by:

I multiply by 2 one time because the square of the eigenvalue just give you the size of the semi-axis. Second time because is a kind of “confidence factor” use to enclose more points in the distribution.

Well I tried that on some binary images and it seems to work pretty well. Notice I used atan2 instead of atan to deal with angle between -PI and PI and green axe is the major orientation axis.

I implemented this little class to compute moments.

Below is the Actionscript I used to compute moments for my binary images.

^{?}View Code ACTIONSCRIPT

var bmp:BitmapData = new BitmapData(t.width, t.height); bmp.draw(t); addChild(new Bitmap(bmp)); var val:Number; var i:int; var j:int; var aData:Array = []; var aTemp:Array; // get all the pixels value (1 or 0) of binary image // into a multi-array for(i = 0; i < bmp.width; ++i) { aTemp = []; for(j = 0; j < bmp.height; ++j) { val = (bmp.getPixel(i, j) < 0xFFFFFF)?1:0; aTemp.push(val); } aData.push(aTemp); } // compute moments var m:Moments = new Moments(aData); // center of the shape var xc:Number = m.m10 * m.invM00; var yc:Number = m.m01 * m.invM00; // intermediate values var a:Number = m.mu20 * m.invM00; var b:Number = m.mu11 * m.invM00; var c:Number = m.mu02 * m.invM00; var d:Number = a + c; var e:Number = Math.sqrt((4 * b * b) + ((a - c) * (a - c))); // length and width var w:Number = Math.sqrt( (d - e)*0.5 ); var h:Number = Math.sqrt( (d + e)*0.5 ); // orientation in radians var angle:Number = Math.atan2( 2*b, a - c + e ); |

Well for next time I will try to implement cool stuff with that. I am sure it will be again a good “moment”… Maths make me really unfunny sometimes

Tags: Add new tag, distribution, image, moments
[...] locating the maximum of density of the probabilities distribution, Camshift uses the 2nd order moment to retrieve the size and the orientation of the distribution. Actually camshift is almost the [...]

Great blog and very interesting stuff here, I am gonna try that technique with blob detection. How about BitmapData.getPixels method to get all the pixels into the ByteArray (for speed)? Cheers, Tomek

@Og2t:

I did not do some benchmark between bytesarray and 2-D loops. If I remember what I have read it is better to use bytesarray for large bitmapdata, but otherwise the speed is not so different. But I have to check what I am saying, Joa wrote a nice paper about this topic

Hey Benjamin..

is there a way to tell, if the lookup shape is at all in the image with this method? I found that with real life pictures this method is always finding something in the image that seems to be likely to the lookup.

[...] I used the Moment of the binary image as described and implemented here: http://www.mukimuki.fr/flashblog/2009/05/20/magic-moments/ thinking that having a global angle of the shape would make it more efficient. but it didn’t [...]