0

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

shakthydoss
  • 101
  • 1
    It is unclear what you are asking. If both components of $M$ are multiplied by the same constant $c$ to obtain the components of $N$, one can write $N=cM$. If the relation is more complicated than this, I don't think there is any special notation; just express exactly how the components of $N$ are expressed in terms of those of $M$. – Marc van Leeuwen Apr 29 '14 at 12:23
  • @MarcvanLeeuwen that is the question I am trying to ask how the components of N are expressed in terms of those of M to say M = N – shakthydoss Apr 29 '14 at 12:27
  • $M=N$ means $N$ is identical to $N$: each component of $N$ is the same as the corresponding component of $N$. If that is not the case then $M\neq N$. If $M$ and $N$ represent the same point in different coordinate systems, then you must specify how the coordinate systems are related, and this amounts to saying how $M$ and $N$ should be related in order to represent the same point. You cannot hope to get an answer if you provide no information about the situation, – Marc van Leeuwen Apr 29 '14 at 12:32
  • @MarcvanLeeuwen just added a image, let me know if it adds more clarity to my question to get a answer. – shakthydoss Apr 29 '14 at 12:51
  • Suggestion: Not sure about this, but if you have two sets of ordered pairs $S$ and $S'$on a graph, and there exists numbers $a,$ $b$ and $c$ such that for $(x,y)\in S$, you have $(c(x-a), c(y-b))\in S',$ then I think you have a figure in $S'$ that is the same shape as $S$ in the sense I think you mean. (It gets more complicated if you allow rotations.) Pick three pairs of corresponding points on each figure, substitute and solve for $a,$ $b$ and $c.$ – Dan Christensen Apr 29 '14 at 14:33
  • Not sure I understand you problem but I think Procrustes analysis may be your solution. – user121049 Apr 29 '14 at 14:48
  • @user121049 Modified the post to add clarity to tell what i am exactly trying to do and where i am trapped. – shakthydoss Apr 29 '14 at 16:29
  • @DanChristensen Modified the post to add clarity to tell what i am exactly trying to do and where i am trapped. – shakthydoss Apr 29 '14 at 16:29
  • your early help would be greatly appreciable. – shakthydoss Apr 29 '14 at 16:31
  • Made major edit to the question to add more details and clarity. – shakthydoss Apr 29 '14 at 17:30
  • If you are talking about 2D patterns in general, there is no simple mathematical test. You will need some object recognition software. There must be some that will quickly recognize parts of an image that are embedded in another. – Dan Christensen Apr 29 '14 at 20:01
  • I think the OP is asking the following: Given two finite sets of points in $\mathbb{R}^2$, say $M = {(x_i, y_i)}$ and $N = {(x_i', y_i')}$, how can one determine whether there exists a linear isomorphism of $\mathbb{R}^2$ that sends $M$ to $N$? And if we know that such an isomorphism exists, how can we find it? – Jesse Madnick Apr 30 '14 at 07:05

2 Answers2

1

Procrustes analysis translates rotates scales and reflects one geometric object so as to get the best fit with another object. I guess that both objects have to be described in a similar way. You also get a measure of fit.

user121049
  • 1,599
  • As you said I gone through Procrustes Analysis. And I found that General Procrustes Analysis would be even more appropriate. But I am not sure I have understood GPA correctly. – shakthydoss May 05 '14 at 17:32
  • I have summaries what I have understood. Please take a look and tell me what I have understood is right or wrong. – shakthydoss May 05 '14 at 17:33
  • GPA is compare the shape of objects. It is uses Procrustes distance measure to determine how alike the shape of objects are. – shakthydoss May 05 '14 at 17:33
  • In Procrustes distance measure shapes of objects are defined by removing the translational, rotational and scaling property. – shakthydoss May 05 '14 at 17:34
  • This action of redefining the object is technically called super imposition of object. Because in this action we are adjusting the geometrical properties of objects to make them as equivalent class so that objects are eligible to compare with each other. – shakthydoss May 05 '14 at 17:34
0

$M$ and $N$ both seem to be cirles with the center $\vec{c}=(7,9)^T$. One has a radius of $1$, the other has a radius of $3$.

Thus, you can translate both sets by $(7,9)^T$ to get two circles which are centered at the origin $M' = M - \vec{c}$ and $N' = N -\vec{c}$. If you take a point in $M'$ and stretch it by $3$, then you end up in $N'$, and you have $$N'=3M'$$

or $$(N - (7,9)^T) = 3(M - (7,9)^T),$$

where it's worth noting that you can't expand the brackets.

Edit: the corresponding equations which describe $M,N$ are

$$M: (x-7)^2 + (y-9)^2 = 1^2, \quad \quad (x-7)^2 + (y-9)^2 = 3^2 $$

Roland
  • 6,064
  • Its not really specific to circle – shakthydoss Apr 29 '14 at 16:45
  • I am looking for how to test whether M and N might be representations of the same underlying geometric object? – shakthydoss Apr 29 '14 at 16:47
  • and geometric object means its not just circle. it can be any figure i can draw in graph – shakthydoss Apr 29 '14 at 16:47
  • @shakthydoss How automated do you want to have your test? Are your objects in a way that you can compute a 'center'? What I wrote would also work if $M$ and $N$ were other conic sections: Translate to the 'center', then stretch/shrink. – Roland Apr 29 '14 at 16:53
  • Okay here is what i have done so far I have developed a system to trace the outline of the objects. Now I want a hypothesis to test and say they(objects) represent a common feature. That is M and N might be representations of the same underlying geometric object – shakthydoss Apr 29 '14 at 16:59
  • Procrustes analysis is what you need but there must be a ton of stuff from the computer vision people. – user121049 Apr 29 '14 at 17:24
  • Made major edit to the question to add more details and clarity. @user121049 do u still advice Procrustes analysis for me – shakthydoss Apr 29 '14 at 17:31