Lines and Arcs

[VirtuallyVB]

Say I have a 2 color graphic file. The background is white. The foreground is black and has lines and arcs drawn on the white background.

The lines and arcs may overlap, but I want to "extract" only lines and arcs. Actually, the image approximates lines and arcs; they may not be perfectly straight lines or constant radii arcs.

1) Say the image contains only 1 line. How do I get (extract) the endpoints of such a line? I consider knowing xStart, yStart, xEnd, yEnd as "extracting" the line from the image.

2) Say the image contains multiple non-overlapping lines as in #1. For let's say 1 to n lines; how do I get xStart(1), yStart(1), xEnd(1), yEnd(1); through xStart(n), yStart(n), xEnd(n), yEnd(n).

3) Same as #2 but with overlapping lines.

4) What if the lines aren't exactly straight? Perhaps a polyline or several arcs can represent this approximated line.

5) How about arcs?

I guess my real issue is that the lines can be at any angle and I'm blocked by thinking I can only process lines at 45 degree intervals to my present pixel location. For instance, consider the pixel at position 5:

123
456
789

The neigboring pixels are oriented at multiples of 45 degrees with respect to position 5. But how would I track a line that is at any angle and begins at position 5?

Thanks.

[Zaei]

Well, for the endpoints of a single line, just take a sample of the image, 3x3 pixels, and if 7 of the 9 are white, thats an endpoint. (this is assuming that the line width is 1).

Z.

[VirtuallyVB]

True. Also, I think I'm okay with any angle now, not just 45 degree multiples.

Let's say the angle for a line is 10 degrees with an endpoint starting from the left and going to the upper-right with respect to the start position.

Zero degress is from position 5 to position 6. 45 degrees is from position 5 to position 3. Do you agree that all methods of representing this 10 degree line will basically show pixels to the right of the start endpoint at zero degrees (position 6) for a few pixels, then 1 pixel at position 3, then several more pixels at position 6, then 1 at position 3 etc.?

By this, I mean; start at any location (say the center of your monitor) and call that the left endpoint of my 10 degree line which basically goes in the direction to the right and up from the center of the monitor. Call this present pixel (the start endpoint) as being located at position 5 in our 3x3 grid
123
456
789

In all techniques, is the neighboring pixel at position 6? Using this neighboring pixel as if it was located at position 5 on our 3x3 grid, is its neighbor (moving away from the start endpoint) also at position 6 with respect to this present pixel? Are there several more pixels located at position 6 and then 1 at position 3?

MS paint.exe seems to follow this method.

Yes, the above is 1 pixel width, but what if I have a line that is several pixels wide? I would like a "Thinning Algorithm" to create a new line that is 1 pixel wide, then I will apply the above technique to extract the single pixel width line or polyline.

Can anyone provide a "thinning algorithm"?

[kedaman]

note, this might be a slow algoritm, but efficient for it purpose.
IF as you say there are only lines and arcs, start searching for connected pixels, store them for later use as positioned vectors. You can do this with nested loops. next run trough each vector and check if it can be "expanded" in both directions. Adjacent pixels could be included and by that tilting the vector, you should though decide how much tilt is allowed with respect to earlier pixels, take for instance the scalaproduct of an earlier vector and the current and set a reasonable lower rate. Let this run until all pixels are connected, you can clean up later by removing irrelevant vectors that are 2 or 3 pixels, that depends on what thickness of lines you have. For arcs, introduce a experimental eliptical equation instead of a positioned vector with the same kind of "expansion" technique you can build up arcs.