Shape detection in image

[Chrono251]

Hi everyone!
I'm pretty new to C#, as I used to program in VB and VB.NET in the past (migration to C# is pretty easy I have to say).

I'm also into astrophotography and I'm developing a program to focus the telescope. A way to focus is to use a Bahtinov mask, that makes a particular diffraction pattern composed by an X and a line that moves up and down. The mask goes in front of the telescope and, when focus is close, here's what it is possible to see:

With perfect focus here's the pattern:

The aim of my program is to detect the X and the line, overlap lines highlight the pattern and calculate some sort of index by measuring the distance between the center of the X and the line. Basically here's what I want to achieve if the input is composed by the 2 pictures above:



Here's how my program works:
- Using Canon SDK libraries I get a snapshot from the camera (I haven't implemented this yet, as for my tests I'm using pictures I have);
- I have developed a class to apply convolution and threshold on the image to filter the data in the snapshot;
- Using AForge I detect the biggest blob (which should be the diffraction pattern);
- I detect the X and the line and overlap new lines.

The problem I how to implement the last point of my list. With AForge I can select the quadrilateral around the pattern, but I have no idea about how to detect the parts of the pattern.
Can anybody halp me with that?

Thank you!

[BioPhysEngr]

Hrm, interesting project.

My thought is that perhaps it would be better to take a different approach and classify it based on a principle component analysis (PCA)-type method. A similar approach has been used to detect faces in images (see the Wikipedia article on Eigenfaces).

Alternatively, you could use a Harr-like feature detection scheme (good summary: http://www.cis.upenn.edu/~seupark/VisualTracking.pdf; the definitive paper though is the Viola-Jones article [reference #10]).

There is also a great computer-vision library called OpenCV and I think there are .NET bindings, see https://code.google.com/p/opencvdotnet/

Also note that computer vision is hard. However, it is achievable. Don't get discouraged if you have to play around with a few different things to get it to work.

If you have any interest, please keep us updated on your progress!

[TheGreatCthulhu]

Just wanted to re-post the link to the PDF above, as an ";" got accidentally incorporated into it, and it won't work as a result:
http://www.cis.upenn.edu/~seupark/VisualTracking.pdf

[TheGreatCthulhu]

P.S. Just contemplating possibilities here: maybe you could take a different approach, and instead of trying to detect the linear elements, maybe you could incrementally move the focus by small amounts and analyze the difference between the successive images, then adjust the focus a bit based on that, then repeat the process, until the difference is acceptable (minimal). Maybe it's even possible to calculate the optimal focus based on a few steps.
Anyway, it's just an idea, I don't have any papers to back it up with.

[Chrono251]

Thanks for the answers!
I'm realizing how hard computer vision can be!

I'll check out OpenCV and read the papers in the next few days. I also found a C++ demo of PCA and Harr method for face detection that I'm going to analyze.
I'll post future updates!

@TheGreatCthulhu:
That would have been a great idea, but unfortunately mother nature likes to make things hard The main problem is atmospheric turbulence (and also turbulence caused by convection inside the telescope assembly): that pattern is not steady even if I don't touch the focuser. The vibration caused by simply touching the telescope have to be considered as well.

[TheGreatCthulhu]

Bummer
And if you managed to calculate the index you're trying to calculate, what would you use it for? To try and automate the focusing process? If so, have you worked out how the focuser position and the given index relate to each other?

Sorry we couldn't be of more help so far. Interesting thread, though.

[Chrono251]

Bummer
And if you managed to calculate the index you're trying to calculate, what would you use it for? To try and automate the focusing process? If so, have you worked out how the focuser position and the given index relate to each other?

Sorry we couldn't be of more help so far. Interesting thread, though.

Initially I would just use the index to give a digital indication of the focus quality, maybe I could also plot a graph.

But potentially it can be also use to create some sort of "autofocus" system (devices that do that already exist, but their price is pretty high - 600$ or more). I used in the past a prototyping board called Arduino for some electronic projects, so I could use it to interface with my project.

I haven't thought about how to determine focuser's position yet, but if I had to implement it now I would do as follows:
- if focus is way out, the pattern visible is like this: Bahtinov - out of focus
- if the size of that increases over time (say 1-2s - it depends on the speed of the servo), I have to turn the focusing knob in the opposite direction
- when focus gets closer, that circular pattern transforms in the pattern showed in the links of my first post, so I can detect the position of the X and the line and calculate the index with the algorithm I'm currently trying to develop
- when the index is at the minimum, the telescope is focused. The problem here is stabilizing the value, but I could find some kind of filter, like calculating the average index of, say, 4-5 frames.

This is just an idea, but I have so many problems to solve before thinking about this that I may find a better way while working on my project.


In computer vision, does working in color make things harder than working in grayscale?
The reason for this question is based on the fact that the image I was using is in color, as I currently use a DSLR for astrophotography. I'm planning to upgrade to a dedicated monochrome CCD in the future, so I'll be working with pictures in grayscale (many manufacturers offer a SDK for their cameras, so this project could be ported to those devices as well).

[Chrono251]

Just an update.
I spent some time reading all the documents and other stuff I found online, and in the meantime I've been working on my project.

I tried to solve the problem with a different approach.
My program applies these transformations:
- gaussian blur filter (with a convolution matrix) - I need to do this to reduce the noise in the picture (but I may change it to something better in the future);
- binarizing (during debugging to highlight the shape) threshold filter - to isolate blobs;
- biggest blob detection (I use the AForge.NET library).
- rotation of the blob (I think it is easier to understand).
At this point I have the coordinates and dimensions of the rectangle containing the blob and I can isolate it from the rest of the picture to work faster.

Here is a picture of part of the main screen and the preview form: Program main screen after detection

What I'm currently working on is the analysis of what I isolated.
To find the main "focus line" I simply count the pixels for each line in the image. The line where I find the most pixels is where the main component of the "focus line" is. This is showed in a graph (bottom left).
I tried this method with many different pictures and it worked fine.
The next step is to detect the "X".

[Chrono251]

I tried to use PCA in my project and I wrote a function that determines the eigenvector and eigenvalues for the blob being analyzed.
I use the eigenvector to determine the inclination angle of the pattern.
But that's the only use I can think of in my project: the center of the new reference system doesn't necessarily lay on the "focus line" or the two lines making the "X". I can't find a way to determine the location of those 3 lines with this method...

Any ideas?

[Chrono251]

I found some articles on an Italian University's website that explains the Hough transform.
This looks like the way to go, as it purpose is to find lines and other shapes (like circles) in an image. The AForge.NET library has a class for the transform, so I'll try to see if this works out.

[Chrono251]

Another update after some tests I did.

The Hough transform library in AForge works great for normal pictures. It works also for my project, but not as well: the problem here is that I don't want to determine the straight lines by analyzing the edges, but I want to determine the location of 3 lines by considering the center of the "rays".
In my experiments I used about 15 images and, with the exception of 2 or 3 of them, the library was able to detect the "focus line" (it's the brightest of the 3). The other lines are detected in many cases, but they are considered just "two of many", and this is not ideal for me.

I'm now going back slightly. The solution I had before trying PCA and Hough transform was pretty good if the rotation of the image was correct, otherwise the graph wouldn't show a single peak but rather 2 smaller ones.
My idea was to determine the distance between the peaks and calculate the rotation angle required to maximize the peak. This is where the Hough transform comes, somehow, into play, as in this case I basically have to analize a pencil of lines, but in the image space instead of the Hough space.

I'm not thinking about an actual Hough transform implementation, as I know that:
- I don't need to find all the lines but just 3;
- for every angular coefficient there has to be only one line (the one with the maximum number of pixels - like in my implementation), as I'm not trying to find parallel lines;
- if the algorithm finds a series of lines with a similar angular coefficient, the line I'm looking for has to be the one with the highest number of pixels.

So here's the list of operations for the algorithm I'm working on:
- filter the image to reduce noise and stretch the histogram (I have to carry out some tests to see which works best - my list includes linear stretch, sin, log and sqrt all with each pixel's RGB value reduced between 0 and 1);
- like for the Hough transform I'm going to analize theta from -90 deg to +90 deg in steps small enough not to affect performance too much;
- for each "theta" (in my case that stands for a rotation) I'm going to determine the graph like in my previews algorithm;
- I analize the intensity of all the peaks;
- the highest 3 have to be related to the lines I'm looking for.

My concern is about performance, as the Hough transform is quite slow. In my tests it took on average between 300ms and 600ms to find the lines, depending on the size of the image. I will see if this solution works and if this is the case I'll try to optimize it.