5
$\begingroup$

I have developed a system to trace the outlines of (images of) objects. Now I want to test whether two independent traces represent a common feature.

Imagine two people (or machines) tracing the outline of a feature in an image, recording it as sequence of vertices. Inaccuracies in recognizing the feature boundaries and in specifying the vertices can be viewed as random errors in vertex positions. The problem is the two traces might use completely different (Cartesian) coordinate systems (set up on two digitizing tablets, for instance). The null hypothesis to test is that they represent a common feature.

This is illustrated below. I drew a figure and recorded the $x$ and $y$ co-ordinates of its vertices in its coordinate system. Let's call this figure $M$. It is represented as a sequence $(x_i,y_i), i=1, 2, \ldots, m$.

Then I drew the same figure in a bigger size in another coordinate system (with no known relationship to the first coordinates system) and recorded the $x$ and $y$ co-ordinates. Let's call this $N$, represented as a sequence $(x_i^\prime, y_i^\prime), i=1, 2, \ldots, n$.

Question: Having these data, how can I test whether the figures $M$ and $N$ represent the same image features even though they have different sizes and co-ordinates?

If the conclusion is that yes, they do represent a common object, then how can I estimate a similarity transformation between $M$ and $N$ so that I can work on formulas or equations to check the results with different figures?

enter image description here

$\endgroup$
12
  • 1
    $\begingroup$ This question might be on topic, but it is unclear what is going on. Your sketches won't be random, to begin with. More importantly, it is not evident what you are really doing when you "capture the coordinates," nor is it apparent how the scales and coordinates differ between sketches. If you find a way to communicate what you are doing, please edit your question accordingly so that the community can vote to re-open it. $\endgroup$
    – whuber
    Apr 29, 2014 at 15:51
  • 3
    $\begingroup$ We still need a more precise sense of "similarity." Do you mean similarity in the Euclidean sense that there exists some combination of a translation, rotation, and uniform scaling that sends $M$ to $N$? If not, exactly what does "M ≈ N" mean? Are you perhaps asking how to measure a degree of similarity when the vertices of both $M$ and $N$ are traced with random-looking errors or how to test whether $M$ and $N$ might be representations of the same underlying geometric object? $\endgroup$
    – whuber
    Apr 29, 2014 at 16:36
  • 1
    $\begingroup$ You really need to address @whuber's specific questions. If you can't understand them, then so be it, but you're not making this question statistical in any sense so far as I can see. It's a question on (computational) geometry, it seems. $\endgroup$
    – Nick Cox
    Apr 29, 2014 at 16:40
  • 4
    $\begingroup$ @Nick Actually I see a potentially very interesting statistical question--provided I am correctly interpreting it. Imagine two people (or machines) tracing the outline of a feature in an image, recording it as sequence of vertices. Inaccuracies in recognizing the feature boundaries and in specifying the vertices can be viewed as random errors. The problem is the two traces might use completely different (Cartesian) coordinate systems (set up on two digitizing tablets, for instance). The null hypothesis to test is that they represent a common feature. Shakthydoss, am I close? $\endgroup$
    – whuber
    Apr 29, 2014 at 16:47
  • 1
    $\begingroup$ I have incorporated your comments and my preceding comment into a major edit to the question. Please read it over and correct any misunderstandings I may inadvertently have introduced. $\endgroup$
    – whuber
    Apr 29, 2014 at 17:19

1 Answer 1

1
$\begingroup$

There has been considerable work done in this area in the image processing community. From a theoretical standpoint, it seems you want to compute a distance metric that given two arbitrary sequences of points determine how similar these sequences of points (vertices) are. The problem could become much easier if you had a constrained number of shapes you were trying to match against, but you probably have already considered that work.

For example, there is a whole host of techniques for measuring the similarity of drawn shapes and touch screen devices do this to infer what actions/letters, etc... you are drawing/requesting. However, generally the algorithm to match what action/shape is being drawn on a device with a 3 inch screen, would be different than the algorithm used on a tablet. To recognize that a shape drawn on a tablet is similar to a shape drawn on a smart phone is difficult due to the scale changes - as you indicate in your question. It can be done, and this is essentially what OCR and in particular handwritten OCR attempts to do, and those techniques would help given insight into how to solve your problem.

Based on what I infer from your question you definitely need translation, scale view, and even arbitrary affine transformation invariance - is that correct. That is, even if one of the figures is rotated by 70 degrees and sheared you want a match. But should two ellipses always match? Or do different ellipses need to not match? What if there are two circles in one of your images. Should they each match the other image or should the other image have two circles in order to match best?

From a simple perspective, suppose you only need to match single circles vs single ellipses, then you could pretty easily distinguish between those two classes, by finding the euclidean error using the best fitting circle and ellipse. This could be generalized to many other classes such as squares, triangles, etc... and there is much work in this area of fitting such sequences of points to various idealized shapes. In this case notice that we are not directly comparing the two drawn shapes, but comparing each to a model and then comparing the errors of the two models. This allows us to easily accommodate different number of points for each drawn shape.

There is another image processing technique called SIFT - Spatial Invariance Feature Transform that computes a sparse set of points from an image - and for each of these sparse points computes the histogram of gradients around that point (at multiple scales). This technique has a number of variants (SURF, PCA-SIFT, etc...) and has enjoyed considerable success. You might want to look there even though in your case you do not have image data.

Handling outliers and missing data would be entirely different topics...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.