How to find 4 points next to the intersection of two lines

Let's say I have some bitmap data (in black) over which some lines have been hand drawn in vector format (in green). The lines roughly follow the shape of the bitmap data. In some places, the lines intersect.

So what I'm trying to do is, knowing the position of the green lines intersection, how I can find the position of A, B, C and D?

See below for some examples:

I'm not sure how to approach this problem given the random positioning of the lines and sometime they are not even inside the black shape. However, I guess th开发者_运维百科ere must be some way. Any suggestion?

Simplest approach I can think of is this:

1. Filter the image to remove the green line. A simple approach would be to use some sort of thinning that fills with the background color of the neighboring pixel(s).

2. Now you should have an image which consists of only black (broad) lines and white background.

3. Filter the image again using a corner detection algorithm, such as the Harris detector. This will give you the four corners.

Notes:

1. Depending on the input data, you might get more than four corners. In any case it is a good idea to verify that the four corners you extracted are indeed possible corners of the intersection.

2. Again, this is a quite rough approach, but if the input data is as clean as in your example pictures, and the distance between the green lines and the black lines is not too big, I think it might work.

I assume you know how to obtain the coordinates (x,y) of the (green) vector line intersection, so I'll leave out that part.

Starting at the pixel closest to (x,y), gradually march outward in an square spiral (or some other search pattern of your liking) from pixel to pixel. At each step, check if you're on a black pixel with one and only one white Moore neighbour. If so, then the place where the black pixel and its white neighbour touch (probably a common corner) is one of your points (call it A). Continue marching until you've found three more (B,C,D). These will be the four such points nearest the green intersection -- which will work fine in the four examples you show in your question.

However, this algorithm will fail if the green intersection is kind of halfway between two black intersections; in this case it will mix points from both black intersections. If you're concerned about this, then as soon as you've found point A, re-initiate your marching spiral, centred on A this time, and march until you've found B, C, D. This will in effect "snap" to the closest black intersection.

You can add more cleverness to avoid searching the same area twice; re-initiate or re-focus your search pattern once you've found B and once more once you've found C, etc... Depends how fancy you want/need to get.

First, let me say I know nothing about the subject nor have I had any experience with it. So this is just my guess. But I would start by disregarding the green lines - which, btw, also don't seem like lines.

Btw, has this got to do anything with roads?

So, off go the green lines. After that, take a small square like any of the 4 of the above you got, until you go through all of them, and look for those that have maximum black/white ratio of pixels. Those should be the ones with the "crossroads". By mapping those black pixels that border with white pixels you should have the road/field borders. After that determining those points should be faily easy.

Like I said, a wild guess. Interesting problem - wonder what the knowledgeable chaps will come up with.

First you have to extract edges from your original image to get polygones which describe the black-white-border.

Then you iterate over the points of theses edges and calculate a pointwise distance to the intersection point of the two green lines. The four smallest distances come from the points you are looking for.

Did this answer your question ? Or did I misunderstand something ?

If you only want the 4 corners, you do not need the green line: Just take the borders from the edge extraction, smooth then with a Savitzky-Golay filter and calculate the pointwise curvature. The just extract the points with maximum curvature.

You need vectorization of the binary image. Our university project was right on the topic - Corners Toolbox Allowing Processing Binary Images in a Compressed Form (don't get confused by the title - "compressed" here means that the binary image is first converted in linked lists of so called corners).

1) convert the image to corners (see chapter 4 of the above link). You can then use line interpolation of the corner points (chapter 5.5) - you would modify our algorithm to see big slope changes (~ 90 degrees) in larger pieces of lines.

2) you don't need the green line. You can use skeletonization algorithm to find the skeleton of the black part (see chapter 5.4), and interpolate this skeleton with lines (see chapter 5.5 of the above link).

If you are interested in the project I can ask colleagues if we can provide the source code.

The easiest way would be a skeletonization. First separate the green and the black/white image. Run a skeleton algorithm (a pretty simple morphological operation, also in OpenCV) on both images and determine the points of intersection (can be done with a simple 8-neighbourhood pixel count in skeleton images: that is, for each black pixel count how many pixels are connected horizontally, vertically or diagonally, and if this value is >= 4, it's an intersection). Now do a nearest-neighbour match for these skeletonized points, and you are done.

You should be able to find the point where the green lines cross as well as the midpoint where the black lines cross by a process of erosion (shrinking to points). Then use a closest pair of points sort of algorithm to find which black lines intersection the green line intersection is closest too.

Then, you can do a search away from the point where the black lines intersect. You'll need a priority queue that will process points according to their distance away from the black lines intersection point, closest first. Put the four adjacent points to the black lines intersection in the queue. For each point in the queue, you'll want to check if it is a white pixel (we want those), check that it hasn't been visited before (skip in that case), and then add its four adjacent pixels to to the queue. The first four white pixels should the ones that you want (assuming that you had a good skeletonizing/shrinking method for finding the intersection), but you should really take white pixels until you get the first four found that aren't adjacent to each other.