The macosxhints Forums - finding angle of line in data (Biometrics)

The macosxhints Forums (http://hintsforums.macworld.com/index.php)

- OS X Developer (http://hintsforums.macworld.com/forumdisplay.php?f=27)

- - finding angle of line in data (Biometrics) (http://hintsforums.macworld.com/showthread.php?t=123358)

finding angle of line in data (Biometrics)

Hello again :)
I'm almost finished with my program to fingerprint recognition. Now i'm struggling with matching. All I need is coordinates of minutiae and its angle, like on image below

http://i54.tinypic.com/2wqzvb7.png

I don't have idea how to get this angle. Well, I think to make straight line from from last two or three pixels but i'm not sure if this is correct way to do this.

Quote:

Originally Posted by maverick (Post 622339)

I'm almost finished with my program to fingerprint recognition. Now i'm struggling with matching.

Forgive me for saying this, but if you haven't got matching working it sounds like you are just beginning your program (since matching is presumably at the heart of the program).

Quote:

I think to make straight line from from last two or three pixels but i'm not sure if this is correct way to do this.

You need to look up about algorithms for fitting data to polynomials (in particular to a line).

Quote:

Originally Posted by hayne (Post 622377)

Forgive me for saying this, but if you haven't got matching working it sounds like you are just beginning your program (since matching is presumably at the heart of the program).

Well, and yes and no. Because i have some algorithms for image enhancement that is why i wrote almost finished.

Quote:

Originally Posted by hayne (Post 622377)

You need to look up about algorithms for fitting data to polynomials (in particular to a line).

I will look closer to this. Thanks.

Quote:

Originally Posted by maverick (Post 622339)

I don't have idea how to get this angle. Well, I think to make straight line from from last two or three pixels but i'm not sure if this is correct way to do this.

If you have two points, you can determine the slope (delta Y/delta X) and then the degree of the angle would be the arc tangent of the slope.

Looking at your picture examples as well, it's obvious that using the "last two or three pixels" will not be accurate either.
In the left pic, the line (and angle) seems to be derived from the end-centers of the gray bar in question. In the right one, they seemed to split the difference between the ends of the "Y" to formulate a center point and drew the line from there. I'd want to verify the method being used here before doing anything.

Quote:

Originally Posted by Jasen (Post 622439)

If you have two points, you can determine the slope (delta Y/delta X) and then the degree of the angle would be the arc tangent of the slope.

You mean to calculate a gradient at point [x,y]?

Quote:

Originally Posted by Jasen (Post 622450)

It was just a thought. So it's not good idea to get the angle from this...

Can someone show me an easy (or any) way to calculate gradient? I know how to calculate gradient of function but calculate gradient of an image at [x,y] is a mystery.

1) Define exactly what you mean by "calculate gradient of an image at [x,y]". Write down a concise definition in words.
2) Google for what you wrote in step 1.

Quote:

Originally Posted by maverick (Post 622624)

Can someone show me an easy (or any) way to calculate gradient? I know how to calculate gradient of function but calculate gradient of an image at [x,y] is a mystery.

You ask for two separate things here - one is how to calculate the slope of a line (that's high school algebra) and the other is how to identify a line in an image, a rather harder project. You also will need to deal with rotation of the image.

Unless this is a programming exercise you will probably save a substantial amount of time by licensing a module from a biometrics company, that way your part is limited to sending the image to the module and processing the true/false return.

First - finding a minutiae (i.e. bifurcation) is not that big deal. Let's say I already have minutiaes coordinations in array.

By calculate gradient at (x,y) i meant:

The gradient grad(x,y) at point [x,y] of an image is a 2 dimensional vector [grad_x(x,y), grad_y(x,y)] where grad_x, grad_y are derivatives of an image at (x,y).

That what I want to achieve. It's for ridge orientation. So i think if I will get the ridge orientation I will be able to get the minutiae orientation.

Quote:

Originally Posted by acme.mail.order (Post 622652)

I know that is not easy project. But why not to try to do :) It is not impossible :) It's only a matter of time. And i think if I want to get better in programming it is good to write hard programms.

It will be good to add LaTeX to forum ;)

Quote:

Originally Posted by maverick (Post 622654)

By calculate gradient at (x,y) i meant:

The gradient grad(x,y) at point [x,y] of an image is a 2 dimensional vector [grad_x(x,y), grad_y(x,y)] where grad_, grad_y are derivatives of an image at (x,y).

You haven't defined what you mean by "derivatives of an image".
(Once you define these things in terms of the data you have, you will be able to figure out how to do it. Derivatives are things that act on functions. Functions act on numbers. What are the functions? What are the numbers? Don't tell me - tell yourself.)

ok I figured out that i will get grad_x and grad_y from Sobel mask/operator. Simply saying Sobel mask is for edge detection. It's 3x3 mask applied on each pixel. Seems easy but... my code doesn't work

Code:

NSBitmapImageRep *bitmapImageRep = [[NSBitmapImageRep alloc] initWithData:[loadedImage TIFFRepresentation]];

        NSInteger width = [bitmapImageRep pixelsWide];

        NSInteger height = [bitmapImageRep pixelsHigh];

        

    int Gx[3][3];

    int Gy[3][3];

    int col = 0;

    int row = 0;

    

    int sumX, sumY;

    int SUM;

    int I, J;

    

    // Sobel Mask, Gx

    Gx[0][0]=-1;    Gx[0][1]=0;     Gx[0][2]=1;

    Gx[1][0]=-2;    Gx[1][1]=0;     Gx[1][2]=2;

    Gx[2][0]=-1;    Gx[2][1]=0;     Gx[2][2]=1;

    

    // Sobel Mask, Gy

    Gy[0][0]=1;     Gy[0][1]=2;     Gy[0][2]=1;

    Gy[1][0]=0;     Gy[1][1]=0;     Gy[1][2]=0;

    Gy[2][0]=-1;    Gy[2][1]=-2;    Gy[2][2]=-1;

        

    //

    unsigned char *pixels;

    NSBitmapImageRep *bitmap2;

    NSGraphicsContext *context;

    

    pixels = malloc(width * height);

        

    bitmap2 = [[NSBitmapImageRep alloc] initWithBitmapDataPlanes: &pixels

                                                      pixelsWide: width

                                                      pixelsHigh: height

                                                   bitsPerSample: 8

                                                 samplesPerPixel: 1

                                                        hasAlpha: NO

                                                        isPlanar: NO

                                                  colorSpaceName: NSCalibratedWhiteColorSpace

                                                    bitmapFormat: 0

                                                     bytesPerRow: width

                                                    bitsPerPixel: 8];

    

    context = [NSGraphicsContext graphicsContextWithBitmapImageRep: bitmap2];

    [NSGraphicsContext saveGraphicsState];

    [NSGraphicsContext setCurrentContext: context];

    [bitmapImageRep drawInRect: NSMakeRect(0, 0, width, height)];

    [NSGraphicsContext restoreGraphicsState];

        //

    

    /*-----------------------------------

            Sobel Mask Algorithm

    -----------------------------------*/

    for(col=0; col<width-1; col++) {

        for(row=0; row<height-1; row++) {

            sumX = 0;

            sumY = 0;

            

            // Image boundaries

            /*if (height==0)

                SUM=0;

            else if (width==0)

                SUM=0;

            else {*/

            // Gradient X

            /*for(I=-1; I<=1; I++) {

                for(J=-1; J<=1; J++) {

                    sumX += pixels[(row+I)*width + (col+J)]*Gx[I+1][J+1];

                    //sumX += pixels[row][col]*Gx[I+1][J+1];

                    //pixels[(row*width + col)] = pixels[(row*width + col)]*Gx[I+1][J+1];

                }

            }*/

            /*

            // Gradient Y

            for(I=-1; I<=1; I++) {

                for(J=-1; J<=1; J++) {

                    sumY += pixels[row*width + col]*Gy[I+1][J+1];

                }

            }*/

                

            // Gradient

            //SUM = sqrt(pow((double)sumX, 2.0) + pow((double)sumY, 2.0));

            

            //pixels[(row*width + col)] = 255 - SUM;

            pixels[(row*width + col)] = abs( (pixels[((row+1)*width + (col-1))] + 2*pixels[((row+1)*width + col)] + pixels[((row+1)*width + (col+1))]) - (pixels[((row-1)*width + (col-1))] + 2*pixels[((row-1)*width + col)] + pixels[((row+1)*width + (col+1))] ));

        }

    }

    

        producedImage = [[NSImage alloc] init];

        [producedImage addRepresentation:bitmap2];

        

        [bitmap2 release];

    

    [processedImage setImage: producedImage];

In above code there are two methods to apply this mask. One is commented

Code:

// Gradient X

            /*for(I=-1; I<=1; I++) {

                for(J=-1; J<=1; J++) {

                    sumX += pixels[(row+I)*width + (col+J)]*Gx[I+1][J+1];

                    //sumX += pixels[row][col]*Gx[I+1][J+1];

                    //pixels[(row*width + col)] = pixels[(row*width + col)]*Gx[I+1][J+1];

                }

            }*/

            /*

            // Gradient Y

            for(I=-1; I<=1; I++) {

                for(J=-1; J<=1; J++) {

                    sumY += pixels[row*width + col]*Gy[I+1][J+1];

                }

            }*/

                

            // Gradient

            //SUM = sqrt(pow((double)sumX, 2.0) + pow((double)sumY, 2.0));

Second one:

Code:

pixels[(row*width + col)] = abs( (pixels[((row+1)*width + (col-1))] + 2*pixels[((row+1)*width + col)] + pixels[((row+1)*width + (col+1))]) - (pixels[((row-1)*width + (col-1))] + 2*pixels[((row-1)*width + col)] + pixels[((row+1)*width + (col+1))] ));

is commonly used approximation. But when using first or second way i receive this:
http://img821.imageshack.us/img821/7...sedlena.th.png

Well, either your pixels calculation is incorrect or you aren't displaying the pixels correctly.
At a cursory glance at your code, I don't see you using the 'pixels' array after it has been filled in.

I don't know where but the calculations are wrong somewhere. 'pixels' array is used here:

Code:

bitmap2 = [[NSBitmapImageRep alloc] initWithBitmapDataPlanes: &pixels

                                                      pixelsWide: width

                                                      pixelsHigh: height

                                                   bitsPerSample: 8

                                                 samplesPerPixel: 1

                                                        hasAlpha: NO

                                                        isPlanar: NO

                                                  colorSpaceName: NSCalibratedWhiteColorSpace

                                                    bitmapFormat: 0

                                                     bytesPerRow: width

                                                    bitsPerPixel: 8];

after calculations are done i'm adding a representation.

I'm curious where i have a mistake. The second method, is simple. I remember that the zero point (0,0) of the image is in top left corner. But still it doesn't make any sense to me why this code doesn't work...

Quote:

Originally Posted by maverick (Post 623125)

I don't know where but the calculations are wrong somewhere. 'pixels' array is used here:

Code:

bitmap2 = [[NSBitmapImageRep alloc] initWithBitmapDataPlanes: &pixels

                                                      pixelsWide: width

                                                      pixelsHigh: height

                                                   bitsPerSample: 8

                                                 samplesPerPixel: 1

                                                        hasAlpha: NO

                                                        isPlanar: NO

                                                  colorSpaceName: NSCalibratedWhiteColorSpace

                                                    bitmapFormat: 0

                                                     bytesPerRow: width

                                                    bitsPerPixel: 8];

after calculations are done i'm adding a representation.

Maybe there's some magic happening here that I don't remember, but I don't think the bitmap goes back and looks at the pixels array you've pointed it at when you add a representation. I think it copies the pixels when you call 'initWithBitmapDataPlanes'

No. It works. If you paint half an image with black or white color it works. Even if this image i posted you can see that it paints something, but it's not what i'm looking for. It's more white noise but you can see the shape of Lena.

But just for curiosity - i will check it

EDIT:

This code is working as it is. But definitely there is a mistake that I cannot see. But as I said - i receive white noise with shape of Lena...

Slowly forward. I added some simple code

Code:

if (SUM>255)

                SUM=255;

            else if (SUM<0)

                SUM=0;

after

Code:

SUM = abs(sumX) + abs(sumY);

and I receive something closer to what I'm looking for

http://img35.imageshack.us/img35/575...517godz.th.png

But still it's not properly done edge detection.

I'd suggest debugging this with a very simple constructed image rather than Lena. Something where you can see what results you should get on a per-pixel basis. Something with as few pixels as possible - maybe a 4x6 image. Then step through the code and compare with your paper calculations until you find where it is going wrong.

Ok. The problem is trival. And I don't know why i didn't saw this mistake before.

Insted of using pixels(row*width + col) here:

Code:

pixels[(row*width + col)] = 255 - SUM;

i should make another array lets say:

Code:

helpeArray[(row*width + col)] = 255 - SUM;

and then in loop copy new values from helpArray back to pixels array. To prove it's working
http://img10.imageshack.us/img10/526...518godz.th.png

Quote:

Originally Posted by maverick

To prove it's working

Sorry - but I beg to differ.

Looks like your latest routine is not picking up vertical edges. None of the detail above and to Lena's left is being picked up for example.
EDIT(Actually implies there's something wrong with your dx calculation)
Implies there's at least one problem in your code dealing with dy. Are you sure your y Sobel mask is the right way up? Cocoa uses a bottom left origin not a top left origin as in some graphic systems.

Also don't see why simply copying an array improves your result. Would seem that something else is actually going on.

Quote:

Originally Posted by bramley (Post 623390)

After Hayne told to make some simple image i did what he said. I made simple 4x4 image and watched every step. I did the math on my own and saw what my program will do. And then i figured out where is my problem.
And yes I think this code is correct right now. This convolution is correct. And if you copy my code to your program and you will add this 2 loops instead of Sobel algorithm:

Code:

    for(row=0; row<height/2; row++) {

        for(col=0; col<width/2; col++) {

            pixels[row*width + col] = 0;

        }

    }

you will see that the origin is in top left point of an image.

Quote:

Originally Posted by bramley (Post 623390)

Also don't see why simply copying an array improves your result. Would seem that something else is actually going on.

Well maybe i didn't write it correctly. I pick 3x3 matrix of an image (around point [x,y]) and multiply it by 3x3 sobel mask. After summing etc. i have to store somewhere this new value. I cannot write it directly at [x,y] of an image, because I will use original values in further calculations. Each pixel is being used several times during calculations. So, after all calculations, i have new matrix. I can copy calculated values to 'pixels' matrix or make a new image from this matrix.

But OK, now i see that i took wrong image ;) I should use this one:

http://img687.imageshack.us/img687/5...110518godz.png

If you have other insights please feel free to write. :) As anyone else :) And sorry for my bad english :)

Not sure, but isn't there an edge detection routine in the Cocoa frameworks somewhere? I know it's one of the things that QuickTime can do.

Well, to be honest, I haven't heard about it. But even if there is a class for edge detection, I'm glad to write my own program just to practice. I'm new in image processing and this seems to be great exercise :)