Image Comparison for vector images (based on edge detection)?

Question

I've been going through posts and examples for the past two days and all snippets Ive tried and extensively tested have proven to be quite useless, at least for my purposes.

What I want to do is compare a black vector symbol photographed off a wall or piece of paper (quality akin to badly scanned images one might say) and compare that to an electronic version of the same or similar symbol (which would be stored locally and compared to the photograph). Please take a look at the two attached images, the first clean one (reference image) is the database version of the symbol and the second is a crappy drawing I made on a piece of paper which I then photographed with my iPad.

I wanted the procedure to go as follows:

• The two images are loaded and then trimmed using a modified version of this trimming algorithm I found here: Trimming images with PIL. I found that a 'threshold' value of 50 and an 'obviousness' value of 20 (parameters in the linked script) give good results for these images
• The images would then be resized to the same size and compared

Now for the comparison, I've tried a ton of different suggested approaches but so far the results are terrible. I can actually get better comparison results with a random image than the tested one. I've tried RMS difference comparison based on the actual images, their edges (created with the 'filter' function with ImageFilter.CONTOUR or ImageFilter.FIND_EDGES), Pixel-Based Comparison but so far nothing Ive found online (despite my incessant googling) or here in StackOverflow has given me decent results.

I believe that the problem lies in the noisy backdrop of the test image but I havent been able to prove it. Does anyone know if there's a way to get a vectorial outline out of the edges in these images and compare them not merely as images but as image-vectors? Despite my crappy drawing, I find that these two images are fairly similar and it should be possible to get a good comparison out of it.

Answer 1

To get a better response you need to better limit the scope of your application. Here is something that might help you. I suppose your "crappy drawing" input is always similar to the one you provided in the sense that it has strong edges, and the color present on it is irrelevant. To solve (or, better, to get closer to a solution for) your problem in a simple way, you need to describe both images in terms of scale invariant descriptors.

My take on it: binarize both images, count number of connected components (CCs) inside both, discard CCs of irrelevant size (too far from the median, mean, related to stddev, etc, you decide). You will possibly want to supplement the second step, to better discriminate your image from other inputs, i.e., the more powerful you want your approach to be, the more discriminant descriptors you will need. At some point you might also want to consider using SVM, or other machine learning techniques.

So, the binarize step: perform a morphological gradient and discard weak gradient. This is very easy if the inputs are similar to what was posted. Here is what I get with a threshold at intensity 60 (I'm also assuming your input is in the range [0, 255]):

I quickly experimented with thresholds ranging till 90, and all them worked for these images. Cropping these is easy, and you can also flood fill the background and the object:

Now you can extract the connected components in white and do the analysis on them. In this case, the simplest thing to do is to count them. For these inputs, we get 12 in the "perfect" image and 14 in the "bad" one. But, in the "bad" one, we have 2 components of size 1 (there is only one pixel in each one of them), which are trivially eliminated. There are many other ways to compare the connected components, but I hope this can get you started. If you need the code for these tasks I can include it.

Answer 2

I'm not sure how to do this with PIL specifically, but I can point you to some good working examples to help you self-learn (this is a non-trivial task for image processing!).

A good working example is DeTeXify, a program that matches a mouse-drawn symbol with a large library of known symbols (in this case the symbols one can create in the typesetting program LaTeX). The source code for both the front and back-end's are available.

Another example is ShapeCatcher which:

... uses so called "shape contexts" to find similarities between two shapes. Shape contexts, a robust mathematical way of describing the concept of similarity between shapes, is a feature descriptor first proposed by Serge Belongie and Jitendra Malik.

A freely available research paper for shape contexts can be found on their Berkeley site.

Answer 3

I think if you visualize the lines as edges on a graph, and the intersections as nodes, even if one is fugly the computer should be able to see that they are the same sign. Just play with levels to get your whites and blacks, then try and analyze the contiguous black spots.

Answer 4

There is a method called SIFT. OpenCV uses it and there is an implementation in Python OpenCV as well. The implementation is SURF in OpenCV, various questions and examples can be found, and it works well. There is an example in this question.

(Posting this answer as an extra reference)

Answer 5

I know this has already been answered, but maybe someone will still find this.

Unlike the accepted answer, I wouldn't deal with the gradient to perform the binarization, but would instead look at Otsu's Thresholding. This should work well if all your images contain only very dark and very light regions, as it looks for the two peaks in the images histogram (one for all the light pixels, one for all the dark pixels) and then thresholds on a value in between the two peaks.