Locating the end points of a bridge-like structure in an image

How do I locate the end points of a bridge-like structure in an image?

Below is a generalized representation.

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 have applied some basic morphological operations; however, either I'm doing it wrong or those basic morphological 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 three edges).

EDITS

Thanks for the previous suggestion; however, 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 th开发者_如何学Pythone 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.

Solution using Python, NumPy, Pymorph and Mahotas:

import pymorph as m
import mahotas
from numpy import where, reshape

image = mahotas.imread('input.png') # Load image

b1 = image[:,:,0] < 100 # Make a binary image from the thresholded red channel
b2 = m.erode(b1, m.sedisk(4)) # Erode to enhance contrast of the bridge
b3 = m.open(b2,m.sedisk(4)) # Remove the bridge
b4 = b2-b3 # Bridge plus small noise
b5 = m.areaopen(b4,1000) # Remove small areas leaving only a thinned bridge
b6 = m.dilate(b3)*b5 # Extend the non-bridge area slightly and get intersection with the bridge.

#b6 is image of end of bridge, now find single points
b7 = m.thin(b6, m.endpoints('homotopic')) # Narrow regions to single points.
labelled = m.label(b7) # Label endpoints.

x1, y1 = reshape(where(labelled == 1),(1,2))[0]
x2, y2 = reshape(where(labelled == 2),(1,2))[0]

outputimage = m.overlay(b1, m.dilate(b7,m.sedisk(5)))
mahotas.imsave('output.png', outputimage)

Here is a code example to locate branch points after skeletonizing the image:

import pymorph as m
import mahotas
from numpy import array

image = mahotas.imread('1.png') # load image

b1 = image[:,:,1] < 150 # make binary image from thresholded green channel

b2 = m.thin(b1) # create skeleton
b3 = m.thin(b2, m.endpoints('homotopic'), 15) # prune small branches, may need tuning

# structuring elements to search for 3-connected pixels
seA1 = array([[False,  True, False],
       [False,  True, False],
       [ True, False,  True]], dtype=bool)

seB1 = array([[False, False, False],
       [ True, False,  True],
       [False,  True, False]], dtype=bool)

seA2 = array([[False,  True, False],
       [ True,  True,  True],
       [False, False, False]], dtype=bool)

seB2 = array([[ True, False,  True],
       [False, False, False],
       [False,  True, False]], dtype=bool)

# hit or miss templates from these SEs
hmt1 = m.se2hmt(seA1, seB1)
hmt2 = m.se2hmt(seA2, seB2)

# locate 3-connected regions
b4 = m.union(m.supcanon(b3, hmt1), m.supcanon(b3, hmt2))

# dilate to merge nearby hits
b5 = m.dilate(b4, m.sedisk(10))

# locate centroids
b6 = m.blob(m.label(b5), 'centroid')

outputimage = m.overlay(b1, m.dilate(b6,m.sedisk(5)))
mahotas.imsave('output.png', outputimage)  

Here you have a code example in Mathematica, probably not optimal:

f[i_] := 
   Module[{t, i2, w, z, neighbours, i3, cRed}, 
  (t = Thinning[ColorNegate@i, 15]; 
   i2 = ImageData@Binarize[ DeleteSmallComponents[
        ImageSubtract[t, Dilation[Erosion[t, 1], 1]], 100], .1];

    For[w = 2, w < Dimensions[i2][[1]], w++,
     For[z = 2, z < Dimensions[i2][[2]], z++,
      If[i2[[w, z]] == 1 && i2[[w + 1, z + 1]] == 1, 
         i2[[w, z + 1]] = i2[[w + 1, z]] = 0];
      If[i2[[w, z]] == i2[[w - 1, z - 1]] == 1, 
         i2[[w, z - 1]] = i2[[w - 1, z]] = 0];
      If[i2[[w, z]] == i2[[w + 1, z - 1]] == 1, 
         i2[[w, z - 1]] = i2[[w + 1, z]] = 0];
      If[i2[[w, z]] == i2[[w - 1, z + 1]] == 1, 
         i2[[w, z + 1]] = i2[[w - 1, z]] = 0];
      ]
     ];

    neighbours[l_, k_, j_] := 
      l[[k - 1, j]] +     l[[k + 1, j]] +     l[[k, j + 1]] + l[[k, j - 1]] + 
      l[[k + 1, j + 1]] + l[[k + 1, j - 1]] + l[[k - 1, j + 1]] + 
      l[[k - 1, j - 1]];

    i3 = Table[
      If[i2[[w, z]] ==1,neighbours[i2, w, z], 0],{w,2,Dimensions[i2][[1]]-1}, 
                                                 {z,2,Dimensions[i2][[2]]-1}];
    cRed = 
     ColorNegate@Rasterize[Graphics[{Red, Disk[]}], ImageSize -> 15];

    ImageCompose[
     ImageCompose[i, 
      cRed, {#[[2]], Dimensions[i2][[1]] - #[[1]]} &@
       Position[i3, 1][[1]]], 
      cRed, {#[[2]], Dimensions[i2][[1]] - #[[1]]} &@
       Position[i3, 1][[2]]])];

A generic approach comes to mind:

1) trace the outline and turn it into a path. So there is one path that goes all around the shape, it being made out of line segments

2) look for the stem - the place on the path where the line segments are approximately parallel for some distance (a spatial index e.g. octree or kdtree will help keep the search localised)

3) follow the path in some direction until the two sides suddenly diverge. That's an endpoint to the stem

4) follow the path in the other direction to find the other endpoint

You could also try running a moving window over the image with a filter that is sum of the pixel values inside. Tune the size to say double the size of the bridge width. You should expect to see a fairly sharp transition when you run off the bridge onto the shore.

One interesting feature that found is the junction point in the skeleton which has the least value of the distance function of the complement of the object associated with it.

X - object set in black in input image D(X) - Distance function of object X D(~X) - Distance function of the complement of the object - this would usually resemble the skeletonization of the object set by itself.

Thus the basic intuition here is that the object X's topology is such that near the heavy heads one finds pinch - a place where you are sure to have a junction point in the skeleton - and at the same time a low value of the distance function of the complement of the object. The neck or pinch produces a minimum here at the junction point.

Maybe this idea needs some tuning - but i guess one can work around.