# Detecting/Locating endpoints of a bridge-like structure in images using Graph Theory

I have asked similar questions on stackoverflow; as i couldn't post the very same question in this part of stackexchange. However, i would still like to receive recommendations / advice from this side of stackexchange, so forgive me and correct me if this is not the right place to ask such question.

The image can be seen here!

Problem Scenario

I have a set of images that look like what you see on the left hand column as shown in the above picture. What I am trying to detect/locate is actually the two endpoints that are shown on the right hand column in the above picture. It's quite like locating the "two ends points" of the 'bridge'.

I sincerely would like to seek for your advice and recommendation to achieve such goals. I have applied some basic morphological operations; however, either im doing it wrong or those basic morpological operations aren't working in this scenario. (i have tried making it into skeletons; however, once the skeletons are formed, I can't seem to detect the cross with 3 edges).

Also, would Graph Theory be applicable in this case? If so, how do i detect the end points using Graph Theory?

Thanks very much.

## Edits

It looks like the original sets of images cannot be completely generalized like what i'd previously drawn.

i have attached the latest updates to this question. Below is a more detailed representation that includes the original segmented regions and the corresponding images that'd undergone a "thinning" morphological operation. Again, the left side is the originally segmented region; while on the right would be the points to be detected.

• I doubt that graph theory could be used to detect the red points (I could be wrong). That seems like a pure image processing task. Graph theory could be used after you have detected the points and connected then, for example, based on whether they are connected via black. Commented May 30, 2011 at 11:12
• Have you tried in the following order: remove noise, icrease "pixel size" and then apply a thinning algorithm (en.wikipedia.org/wiki/Topological_skeleton)? You should end up with a longest segment connecting two (probably badly skeletonized, but with shorter segments) zones. Commented May 30, 2011 at 11:21
• I saw the new pictures. 1) you can cut the shortest edges 2) at each node of degree 3 (a possible bridge endpoint), you can check the outgoing directions (intersecting a large enough circle centered on the node, with the other segments of the skeleton), and then define the acceptable ranges for the three directions. In such a way you can distinguish between false middle branches and false top branches 3) if the figures are always oriented like the examples, you can use an horizontal scanline to improve the bounds between upper/lower "mass" and the bridge. Commented May 31, 2011 at 17:09
• @Vor. Thanks for the help. This might be another silly and trivial question. How does one check for a node of degree 3 (the intersection)? What i have in mind immediately is to traverse the pixel, and at any pixel, if there is an 'extra neighbor', that pixel would be pinpoint as the potential intersection? Commented Jun 1, 2011 at 2:24
• you must transform the 1bit bitmap skeleton into a graph; see the edit in my answer. Let me know if you need further details. Commented Jun 1, 2011 at 12:18

I extend my comment adding an image produced with an (old) piece of software I made to automatically fill a figure with a colored gel.

The steps are:

1. reduce colors to black and white (1 bit)
2. reduce DPI
3. remove noise
4. apply a standard thinning algorithm
5. remove edges shorter than a fixed amount (based on the whole figure size)

I was interested in finding the center of each zone; if you are interested in the exact length of the bridge you can use various techniques.

For example:

• add a "growing" white circle at the two endpoints of the longest segment found and reapply the algorithm, until the graph becomes disconnected, or
• scan the longest segment with an orthogonal line and calculate the length of its intersection with the original image; cut the bridge when you find a fast change in the length of the intersection
• ...

EDIT

In order to transform the image into a graph, you must scan the 1bit bitmap produced with the thinning algorithm (the skeleton).

The algorithmm I used in my program, generates at most 3 neighbours (out of 8) for each pixel. So the graph construction can be done in this way:

1. start from top left pixel P=(x,y), create a starting node N_0=(x,y)
2. mark P as processed
3. count the unprocessed neighbours neig_num of P
3.1 if neig_num = 0 then P is an endpoint of an edge
- check if one of its neighbours is an already created node N
- otherwise create a new node N=(x,y)
- add an edge from N to the last node found LASTN
3.2 if neig_num = 1 then P is an inner point of an edge, do nothing
3.3 if neig_num = 2 then P is a node of degree 3
- create a new node N=(x,y)
- add an edge from N to the last node found LASTN
6. for each unprocessed neighbour P' of P recursively call 2 (passing P as LASTN).
7. stop when all pixels have been processed
8. do some clean up stuff: merge closer nodes, remove short edges,
check if N_0 has degree 2 (we started on an edge in a closed path)