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

Question

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.

Answer 1

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)