# Accessing the graph Thinning produces without losing all the edges' lengths/slopes

This is a follow up to the OCR question I had earlier.

What I want to do is to use Thinning to create "skeletons" of images of characters and then compare their shapes, utilizing such properties as the slopes/lengths of the edges. The problem is however that I have not been able so far to access the graph Thinning produces. MorphologicalGraph is what I have found in the documentation but this removes a lot of information. And for comparing graphs so far I only have found IsomorphicGraphQ which doesn't seem to offer much customization (tolerances for matching).

The code below demonstrates the problem I have with my current approach. Because MorphologicalGraph reduces the Thinned images to a very similar shape for all these characters, the code will deem a "C" character similar to "I" and "S":

Graphize[u_] := MorphologicalGraph@Thinning@ColorNegate[Import[u]]
whichQ = Graphize["http://i.imgur.com/2Fxyh.gif"] (* C *)
i = Graphize["http://i.imgur.com/SPp7R.gif"]  (* I *)
c = Graphize["http://i.imgur.com/SeXA7.gif"]  (* C *)
s = Graphize["http://i.imgur.com/aguQ6.gif"]  (* S *)
IsomorphicGraphQ[whichQ, i] (* -> True *)
IsomorphicGraphQ[whichQ, c] (* -> True *)
IsomorphicGraphQ[whichQ, s] (* -> True *)

-

The basic problem is that the letters I, C and S have the same graph - they all consist of two endpoints (vertices) with a single line (edge) going from one to the other. The shape of the line doesn't change the graph. The only other thing MorphologicalGraph gives you is that the EdgeWeights of the resulting graph correspond to the number of pixels in the skeleton between the two vertices.

One idea that I had is to try and increase the complexity of the graphs by mirroring each letter vertically and horizontally. I also found it helped to remove very short (low weight) edges.

Here are the functions to do the mirroring and pruning:

mirror[letter_] := Module[{im},
ImageAssemble[{{ImageReflect[im, Left], im},
{ImageReflect[ImageReflect[im, Left]], ImageReflect[im]}}]];

prune[g_] := Module[{ew, el},
ew = PropertyValue[g, EdgeWeight];
el = EdgeList[g];
el = Sort /@ (el /. (Pick[el, ew, w_ /; w < 10] /. UndirectedEdge -> Rule));
Graph[DeleteCases[DeleteDuplicates[el], UndirectedEdge[x_, x_]]]];


Create a reference set from the letters A-Z in "Arial" font:

chars = FromCharacterCode /@ Range[65, 90];
reference = Style[#, FontFamily -> "Arial", 100] & /@ chars;
refgraphs = prune[MorphologicalGraph[mirror[#]]] & /@ reference;


Here are the mirrored letter images and the corresponding graphs:

Grid[Partition[ImageResize[mirror[#], {Automatic, 50}] & /@ reference,  5]]
Grid[Partition[Show[#, ImageSize -> {50, 50}] & /@ refgraphs, 5]]


Now create a test set using a different font ("Calibri")

test = Style[#, FontFamily -> "Calibri", 100] & /@ chars;
testgraphs = prune[MorphologicalGraph[mirror[#]]] & /@ test;


Check the isomorphism:

Outer[IsomorphicGraphQ, testgraphs, refgraphs] // Boole // ArrayPlot


Even with such similar fonts as Arial and Calibri, it doesn't work perfectly, though the mirroring has certainly helped. Perhaps you can think of a better way to create unique graphs from the letters.

-
To the point of the general approach, I would probably use the graph approach as one factor. For example, H and I share a graph (assuming H doesn't have serifs). If a symbol falls in the H/I category, then other methods can be used to further discriminate between those symbols. – amr Nov 3 '12 at 20:58
@amr I tried to use CornerFilter/EdgeDetect as an additional measure but it wasn't really working. HammingDistance might be a good additional measure to use but it needs a full graph representation (which one can't create from a picture with standard MMA functions as it seems). edit: Maybe unthinned image->MorphologicalGraph->HammingDistance is an idea for an additional measurement – Sven K Nov 5 '12 at 10:24
@Simon-Woods Thanks for the answer. Interesting idea. – Sven K Nov 5 '12 at 14:52
@SvenK, it's an interesting problem. I wonder if the EdgeWeights (i.e. skeleton length in pixels) could be compared to the Euclidean distance between two vertices, to estimate how straight or curvy the line is. – Simon Woods Nov 6 '12 at 22:18