To recognize objects in an image methods involving graphs have been developped as the shock graph method. These graphs are derived from image skeleton and then handled, compared. However, it seems taken for granted that a graph is available for work.
Here, a python code generating a networkx graph object from the skeleton of a binary image is proposed.
The image of the B letter was chosen as model. The image is generated with PIL:
Skeleton decomposition:The skeleton was then computed by morphological thining, branched points were extracted with a hit-or-miss operator and labelled:
A bug somewhere (update fri 06, 2013):For some shapes, as 'Y':
the algorithm fails at the end points linking step (see bellow). A way to cure the situation is to prune the initial skeleton of 'Y' once:
Branched points neighborhood:The end points can also be extracted and labelled from the initial skeleton, but end points from the edges will be needed.
The edges were obtained by difference between skeleton and branched points, there seven edges labelled from 1 to 7. The edges are pruned by one pixel (labels are 1,2,3,4,5,6,7).The edges end points were then extracted and labelled individually (1,2,3,...,14). The end points were also labelled according to their edge of origin ( 1,2,3,4,5,6,7):
For each branched point, its neighborhood was isolated to get the labels of the adjacent end points (right images):
Building the graph:The graph was build by adding branched points first (vertex 1, 2, 3, 4), it assumes that at least one branched point exists, then end points adjacent to the branched points are added (vertex 8,9,10 and 11,12,13 and 14,15,16):
The remaining lonely end points are added to the graph (vertex 17, 18):
The end points are linked using the pruned edges, the edges are weighted according to their pixel size. The edges length here do not match to their weight:
|Graph of the letter B, without initial skeleton pruning|
With the letter 'Y', with initial skeleton pruning, the algorithm yields the following graph:
|Branched points are figured in red circles on the image of labelled edges and end points are figured by a white star.|
In the case of the letter 'A', the algorithm yields :
The bug seems to come from too short edges as after three pruning steps removing the small barbs on the top of the letter, the algorithm succeeds in producing a graph