# Connecting edges detected by an edge detector

I have a binary image obtained from a canny edge detector. The edges are not nicely detected in the center and I need to join them. The connection of edges is orientation and neighborhood dependent. I need to connect the vertices if they are below a threshold (say less than 5 pixel distance). If my almost linear features are nicely oriented, this threshold should be relaxed. (This is the best case.)

I tried the Hough transform, but it didn't work for me because I don't have straight lines. Dilation and erosion are also not good; they make the images messier.

The approach I am trying is to first detect vertices and nodes (in MATLAB with bwmorph) and then make leaves as a separate feature. This is done as follows:

1. Scanning in a 3x3 window, look for neighbors.
2. Traverse the complete connected object.
3. Try to fit a line (or maybe a quadratic polynomial).
4. Check feature-by-feature if it's worth a connection or not.

The implementation is not straightforward since the decision-making part where vertices need to be connected is tricky.

• I found an interesting solution to find the branches. MATLAB can readily give the location the nodes. MATLAB can also label connected features. So you can choose one connected feature. Find nodes. Set these nodes to 0. Basically disconnect the feaure and label them again. You will have branches in the trees. This required less manual programming and results seems fine. Some input? – Naresh Jun 6 '12 at 13:38
• For the connection part, now I am thinking of finding large features and consider them more reliable. Then if they are straight lines, (check quality of fitness), convert it into polar coordinates and search neighborhood like hough transformation. For large features, search radius is big (proportional to the size). I am implementing this code. Results on the way. Comments pls. – Naresh Jun 6 '12 at 13:42

This might not be complete solution, but will give you good direction.

Basically, what is the key criteria of to say that edges match? That "locally" the gradient of the edge matches and to some extent the distances are reasonable against how long the edge is continuous.

If you have geometric edges, like long straight lines, Hough will do very seamless job right away. But this doesn't work when edges are arbitrary curve. In this case, you can still think of curve as roughly piece wise constant segments (good enough in your case), hence, you should take Hough locally. i.e. you can take a small portion of image (say a block) compute the Hough and identify some peaks. Based on this, you can identify that de-houghing is creating meaningful gap, if so, keep it or move on.

Once smaller gaps are filled up, you can extend the same to take up on a larger size. the peaks will be more, but you may select fewer from it.

• thanks Dipan, I thought of that too. It will be costly operation but I can extract some information. But sometimes Hoguh transfomation is not giving me connected lines either. Hough only takes care of perfect straight lines. And doesnt care for the connectivity of the pixels. It just fits a line to 3 or more random pixels on a straight line. I am coding my hypothesis. I will post results here for further discussion. Naresh – Naresh Jun 1 '12 at 9:08
• I agree, but the noise related to the issue gets easy when hough becomes localized. Secondly, for noisy edges, you will see smaller multiple peaks. We translate them to primary peak and treat that as a connected edge. Yes, this is approximation - but that is always the case for any regression and prediction process you go through. Idea is to see which lines have shared $\theta$ over a small region. – Dipan Mehta Jun 1 '12 at 9:22

That's not going to be straightforward indeed... You could try working entirely with a Graph structure. First extract all the connected pixels from the image and insert them in a Graph where neighboring nodes are connected with an edge. You could discard Graphs that are smaller than some M number of nodes (to exclude little spots that are not relevant to the image).

At the end of this process you will have a set of disconnected Graphs. (Judging from your image, these are not exactly Trees because there are cycles in there)

You can find the extremal points of each Graph (the extremal pixels in the periphery of each Graph) by starting from some random node and doing a DFS.

At the end of this process you will have a set of pixel coordinates for each Graph corresponding to the extremal points where connections are more likely to form.

You can now try to connect the nearest extremal point neighbors (with a distance <=5) simply with a straight line.

But, if you want to take into account the slope of the line segment that leads to that extremal pixel you could try to "fit a line" to N pixels PRIOR to reaching that extremal pixel. So if N = 5, then the last 5 pixels of a branch would be used in estimating a line.

Therefore, for each nearest neighbor pair you now also have another thing to use as a criterion to judge if two segments should be connected (i.e. Extremal Point Distance <=5 pixels AND approximately equal line slope).

To minimise the impact of noise that may make your lines appear jagged near the branch's tips (and therefore distort your slope estimation) you could try applying a simplification step to your Graph (this is another point (besides the DFS above) where it pays to work with a Graph structure). You could for example remove subsequent nodes of the Graph that would make the line "bend" at angles greater than some cut-off (for something more complex, please see here). In this way you will be fitting "simpler" lines, roughly to the direction of a larger part of the segment formed by the image pixels.

That will probably result in decent connections for the majority of cases (judging by the image you have posted) but it would still leave you with some challenging ones. For example how would a "Y" shaped interrupted pattern where one of the branches is interrupted near the connection point be connected? (i.e., you have a "continuous" bend that must be connected with a line segment that "blends" with it). Perhaps you could review how common such cases are and revise your connection criteria later.

Also, maybe it would be worth examining how you could improve your image acquisition (increase the resolution for example).

• Thanks for a good response. Yes, your observation is right. Its not a tree, so better to make a graph. This will help me in finding cycles also. Thing is, MATLAB implemented graph in bioinfo tool box, which I cant assume most people will have. Most I can go is image processing tool box. Douglas-peucker is also something I considered. But after consulting a GIS expert, i realized it might make things more complex and i might get intersecting lines. Also, I need to look at different lines segments in a graph also, since I need 10 pixels to make a line, and i might have a bifurcation already. – Naresh Jun 1 '12 at 15:05