Where can I find information on line growing algorithms?

Question

I'm doing some image processing, and I need to find some information on line growing algorithms - not sure if I'm using the right terminology here, so please call me out on this is needs be.

Imagine my input image is simply a circle on a black background. I'd basically like extract the coordinates, so that I may draw this circle elsewhere based on the coordinates.

Note: I am already using edge detection image filters, but I thought it best to explain with a simple example.

Basically what I'm looking to do is detect lines in an image, and store the result in a data type where by I have say a class called Line, and various different Point objects (containing X/Y coordinates).

class Line
{
    Point points[];
}

class Point
{
    int X, Y;
}

And this is how I'd like to use it...

Line line;

for each pixel in image
{
    if pixel should be added to line
    {
        add pixel coordinates to line;
    }
}

I have no idea how to approach this as you can probably establish, so pointers to any subject matter would be greatly appreciated.

Answer 1

You could take a look at http://processing.org/ the project was created to teach the fundamentals of computer programming within a visual context. There is the language, based on java, and an IDE to make 'sketches' in. It is a very good package to quickly work with visual objects and has good examples of things like edge detection that would be useful to you.

Answer 2

I'm not sure if I'm interpreting you right, but the standard way is to use a Hough transform. It's a two step process:

1. From the given image, determine whether each pixel is an edge pixel (this process creates a new "binary" image). A standard way to do this is Canny edge-detection.

2. Using the binary image of edge pixels, apply the Hough transform. The basic idea is: for each edge pixel, compute all lines through it, and then take the lines that went through the most edge pixels.

Edit: apparently you're looking for the boundary. Here's how you do that.

Recall that the Canny edge detector actually gives you a gradient also (not just the magnitude). So if you pick an edge pixel and follow along (or against) that vector, you'll find the next edge pixel. Keep going until you don't hit an edge pixel anymore, and there's your boundary.

Answer 3

What you are talking about is not an easy problem! I have found that this website is very helpful in image processing: http://homepages.inf.ed.ac.uk/rbf/HIPR2/wksheets.htm

One thing to try is the Hough Transform, which detects shapes in an image. Mind you, it's not easy to figure out.

For edge detection, the best is Canny edge detection, also a non-trivial task to implement.

Answer 4

Assuming the following is true:

• Your image contains a single shape on a background
• You can determine which pixels are background and which pixels are the shape
• You only want to grab the boundary of the outside of the shape (this excludes donut-like shapes where you want to trace the inside circle)

You can use a contour tracing algorithm such as the Moore-neighbour algorithm.

Steps:

1. Find an initial boundary pixel. To do this, start from the bottom-left corner of the image, travel all the way up and if you reach the top, start over at the bottom moving right one pixel and repeat, until you find a shape pixel. Make sure you keep track of the location of the pixel that you were at before you found the shape pixel.

2. Find the next boundary pixel. Travel clockwise around the last visited boundary pixel, starting from the background pixel you last visited before finding the current boundary pixel.

3. Repeat step 2 until you revisit first boundary pixel. Once you visit the first boundary pixel a second time, you've traced the entire boundary of the shape and can stop.

Answer 5

Just to echo the answers above you want to do edge detection and Hough transform.
Note that a Hough transform for a circle is slightly tricky (you are solving for 3 parameters, x,y,radius) you might want to just use a library like openCV