Previously an attempt was made to write a code capable of building a graph from the skeleton of an image and it was not a complete success since some preprocessing (pruning) had to be done to build a graph. Here an other python code was written and at very first sight, it seems to produce a graph without complaining....sometimes (see at the end).
The code was run in a ipython notebook running on sagemath cloud. It relies on several libraries : mahotas and networkx, numpy is provided by default. Scikit image was also tested. Pillow was used to generate images of some letter as model.
The idea is the following:
- make the skeleton of a binary image.
- get its branched-points and add them in a graph.
- get its end-points, add them to the graph.
- get the edges of the skeleton and decompose them into:
- edges between end-points and branched-points.
- edges between branched points.
- add edges to the graph between end-points and branched-points.
- add edges to the graph between branched-points.
Images models
Since the code is run on sagemath cloud, Pillow has to be installed. From a terminal :
pip install Pillow
The verdana true type font was obtained from fontsupply and the file verdana.ttf had to be at the same location than the ipython notebook ( verdana.ttf was uploaded on SMC project at the same location than the ipython notebook).
The code used to generate images and draw them is:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from PIL import Image, ImageDraw, ImageFont | |
| import mahotas as mh | |
| def makeLetterImage(character, size): | |
| image = Image.new("RGBA", (600,150), (255,255,255)) | |
| draw = ImageDraw.Draw(image) | |
| font = ImageFont.truetype("verdana.ttf", size) | |
| draw.text((5, 0), character, (0,0,0), font=font) | |
| img_resized = np.array(image.resize((300,75), Image.ANTIALIAS)) | |
| letter = img_resized[0:40,0:30,0]<64 | |
| r1 = mh.bbox(letter)[0] | |
| r2 = mh.bbox(letter)[1] | |
| c1 = mh.bbox(letter)[2] | |
| c2 = mh.bbox(letter)[3] | |
| letter = letter[r1-1:r2+1,c1-1:c2+1] | |
| return letter | |
| imA = makeLetterImage("A", 70) | |
| imB = makeLetterImage("B", 70) | |
| imH = makeLetterImage("H", 70) | |
| subplot(131) | |
| imshow(imA, interpolation='nearest') | |
| subplot(132) | |
| imshow(imB, interpolation='nearest') | |
| subplot(133) | |
| imshow(imH, interpolation='nearest') |
and we get:
What kind of skeleton?
Both mahotas an scikit-image implement morphological operators to generate the skeleton of a binary shape. Scikit-image seems to use a neighbourhood on 4 pixels (C4) and mahotas on on neighbourhood of 8 pixels (C8). This is why mahotas was retained to produce skeletons:
- medial axis of the letter A computed with scikit image (left), branched points and end-points are extracted using hit-or-miss operator implemented in mahotas (middle). The branched-points can be removed from the medial axis and the resulting image can be labelled (left), pixels connected only vertically or horizontally share the same label.
 |
| Skeleton from the letter A (left) |
- If a skeleton is generated by morphological thining with mahotas, we get the left image. The fourth image is the skeleton deprived of its branched points. Scikit-image provide a thining operator with a C4 neighborhood (right image):
 |
| C8 skeleton by thining (left). C4 skeleton by thining (right). |
What's happen if a C8 skeleton is labeled? Here, both mahotas and scikit-image provide the same result:
 |
| edges (mahotas:left; scikit-image:right) |
The labelled regions fit here what can be seen as an edges.
Prior to start to build a graph, several additionnal images are needed:
Edges decomposition:
Let's decompose the image of edges by considering edges connecting end-points to branched-points and edges connecting only branched points:
Starting to build the graph by the branched-points:
The branched-points are added first. The branched point of label 1 in the image, is the first vertex in the graph, and so on:
The end points are the added to the graph, there is a shift between the end-points label in the image and their index in the graph. The first end-point in the image will be the fith vertex in the graph:
The vertex of the graph (G) have attributes derived from the images they come from: their position 'pos' define by (row,col), their label in the image of origin. Typing in a ipython cell:
print G.nodes(data=True)
print nx.get_node_attributes(G,'label')
print nx.get_node_attributes(G,'label')
yields:
Linking end-points to branched points:
The idea here is to get the neighbourhood of each branched-point in the "edges ep-ep" image and to add an edge in the graph between the corresponding branch-point and end-point(s). This yield:
Linking branched-points
- A dictionnary where the keys are the labels of the branched-points and the values are the label of the "edges bp-bp" in the neighbourhood of the branched point is build. Thus there's one key (bp label) for several values (edges labels).
- But an edge can be seen as one key (the edge label) for two values (the two labels of the two branched-points). So the dictionnary has to be inverted in that very particular way. Fortunately, that problem was solved on stackoverflow.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import mahotas as mh | |
| import networkx as nx | |
| import numpy as np | |
| def C8skeleton_to_graph(skeletonC8): | |
| #images processing: extraction of branchedpoints, end-points, edges | |
| ep = endPoints(skeletonC8) | |
| bp = branchedPoints(skeletonC8, showSE = False) | |
| ## Label branched-points | |
| l_bp,_ = mh.label(bp) | |
| ## Label the edges | |
| l_edges = edges_from_C8skel(skeletonC8) | |
| ##Make end-points with the same label than their edge | |
| l_ep = ep*l_edges | |
| ##edges between branched-points | |
| endpoints_labels = np.where(mh.histogram.fullhistogram(np.uint16(l_ep))[:]==1)[0] | |
| edges_bp = np.copy(l_edges) | |
| for l in endpoints_labels: | |
| edges_bp[np.where(edges_bp == l)]=0 | |
| #edges between end-points and branched points | |
| edges_ep_to_bp = l_edges * np.logical_not(edges_bp > 0) | |
| #Building graph | |
| ## Add branched points first | |
| G=nx.Graph() | |
| lab_bpTonode = add_bp_to_graph(G, l_bp) | |
| ## Add end-points | |
| lab_epTonode = add_ep_to_graph(G, l_ep) | |
| ##Link end-points to branched-points | |
| ###labels of bp | |
| branchedpoints_labels = np.where(mh.histogram.fullhistogram(np.uint16(l_bp))[:]==1)[0] | |
| for lab in branchedpoints_labels: | |
| pos = np.where(l_bp == lab) | |
| row = int(pos[0]) | |
| col = int(pos[1]) | |
| #search label(s) of edges in image containing edges between ep and bp | |
| ## first get the neighborhood of the curent bp | |
| neigh_epbp = edges_ep_to_bp[row-1:row+1+1,col-1:col+1+1] | |
| labels_in_neigh = np.where(mh.histogram.fullhistogram(np.uint16(neigh_epbp))[:]<>0)[0] | |
| #print neigh_epbp, labels_in_neigh[1:] | |
| #get node(s) of attribute label= labels_in_neigh ! may be more than one, think to a list | |
| for lab_ep in labels_in_neigh[1:]: | |
| #search for nodes f attribute label= lab_ep | |
| w = np.sum(l_edges==lab_ep) | |
| print 'linking ',lab, lab_ep, ' weight ',w | |
| G.add_edge(lab_bpTonode[lab],lab_epTonode[lab_ep],weight=w)# | |
| ## | |
| ##Now try to link branched points between them | |
| ## | |
| bps_neighborhood = {} | |
| branchedpoints_labels = np.where(mh.histogram.fullhistogram(np.uint16(l_bp))[:]==1)[0] | |
| for lab in branchedpoints_labels: | |
| pos = np.where(l_bp == lab) | |
| row = int(pos[0]) | |
| col = int(pos[1]) | |
| #search label(s) of edges in image containing edges between ep and bp | |
| ## first get the neighborhood of the curent bp | |
| neigh_epbp = edges_bp[row-1:row+1+1,col-1:col+1+1] | |
| labels_in_neigh = np.where(mh.histogram.fullhistogram(np.uint16(neigh_epbp))[:]<>0)[0] | |
| bps_neighborhood[lab]=labels_in_neigh[1:].tolist() | |
| print bps_neighborhood | |
| ## Build the dictionnary of edges see (http://stackoverflow.com/questions/21375146/pythonic-inverse-dict-non-unique-mappings) | |
| invert_is_edges = {item: [key for key in bps_neighborhood if item in bps_neighborhood[key]] for value in bps_neighborhood.values() for item in value} | |
| ## Addeges to graph | |
| for ed in invert_is_edges.keys(): | |
| ## first get edge size -> its weight | |
| w = np.sum(edges_bp==ed) | |
| vertex1 = invert_is_edges[ed][0] | |
| vertex2 = invert_is_edges[ed][1] | |
| #print ed,w | |
| G.add_edge(vertex1,vertex2,weight=w) | |
| ## This is it !! | |
| return G | |
| skeletonB = mh.thin(imB) | |
| Bgraph = C8skeleton_to_graph(skeletonB) | |
| skeletonH = mh.thin(imH) | |
| Hgraph = C8skeleton_to_graph(skeletonH) | |
| figsize(6,6) | |
| subplot(221,xticks=[] | |
| ,yticks=[]) | |
| imshow(imB, interpolation='nearest') | |
| subplot(222,xticks=[],yticks=[]) | |
| nx.draw(Bgraph) | |
| subplot(223,xticks=[],yticks=[]) | |
| imshow(imH, interpolation='nearest') | |
| subplot(224,xticks=[],yticks=[]) | |
| nx.draw(Hgraph) |
Processing other letters gives for example:
The ipython notebook is here:
View the notebook on ipython.orgSometimes building the graph fails:
On a larger set of images:
- For the image corresponding to the letter K, the graph construction fails due to the presence of branched regions made of several pixels instead of one.
- There's also a problem with the letter D, its graph has no loop.
- Since there's no branched point in the skeleton of the letter C, its graph is not build.
