Similar Polygon Comparison for School Project

[YouWayne]

I'm working on a school project and my goal is to recognize objects. I started with taking pictures, applying various filters and doing boundary tracing. Fourier descriptors are to high for me, so I started approximating polygons from my List of Points. Now I have to match those polygons, which all have the same amount of vertices and all sites have the same length. More particular, I have two polygons and now I have to calculate some scale of similarity. This process has to be translation, rotation and scale invariant.

1. I tried turning and scaling one in different ways and calculate the distance between each pair of vertices, but this is very slow.
2. I tried turning the polygon in a set of vectors and calculate each angle of the corners and compare them. But this is also a bit slow.
3. I found an article called Contour Analysis. But i find this a bit difficult. In this article, firstly all vectors of each set are interpreted as complex numbers, so we only have two vectors with complex compounds. Then the cosine of both vectors is calculated. But the cosine is also a complex number and the norm of it is always 1 if both vectors are the same. So how does it make sense to interpret a set of vectors as one vector. I don't understand this practice.
   

Are there any other ways to compare two polygons or sets of vectors? Or can someone explain my 3rd try or do it with normal vectors?

I hope someone can help me out :-)

 

[fresh_42]

I would pursue the second of your solutions. It's simple and maybe possible to pimp.

Let's assume you have points $P_i=(x_i,y_i)$ given in Cartesian coordinates. Then we get vectors $Q_i=P_{i+1}-P_i = (\bar{x}_i,\bar{y}_i)$ as the edges. Now for the angles $\varphi_i$ at $P_{i+1}$ we can use the formula
$$
\cos \varphi_i = \frac{Q_i \cdot Q_{i+1}}{|Q_i| \cdot |Q_{i+1}|} = \frac{\bar{x}_i \bar{x}_{i+1} + \bar{y}_i \bar{y}_{i+1} }{\sqrt{\bar{x}_i^2+\bar{y}_i^2} \cdot \sqrt{\bar{x}_{i+1}^2 + \bar{y}_{i+1}^2 } }
$$
If space doesn't play a role, which is usually the case, we can form a vector
$$
C_i := (\bar{x}_i \bar{x}_{i+1} + \bar{y}_i \bar{y}_{i+1} \, , \, \bar{x}_i^2+\bar{y}_i^2 \, , \,\bar{x}_{i+1}^2 + \bar{y}_{i+1}^2 )_i
$$
that contains the essential information and the cosines can be computed from its coordinates whenever needed instead of always.

Now comes the time consumption part of it: the comparison whether two vectors are a permutation of each other. Since only rotations have to be checked, it is sufficient to find two numbers $\cos \varphi_i = \cos \psi_j$ and check a single shift instead of all permutations.

If we like we could finally check scaling factors again using the coordinates of $C_i$.

It might be more difficult, to make the algorithm robust w.r.t. input variations of the coordinates. So you would probably have to program some tolerances like $\; if \; \cos \varphi_i \in \cos \psi_j \, \pm\, 0.05 \,$ or similar.

 

[YouWayne]

Thank you for your reply,
so if I have 30 points, i can make 30 vectors, right? Then, when I want to form the vector Ci
, do I have 30 of those 3-dimensional vectors which I can store as one template, right? And why in that form, why isn't the square root in it? Couldn't i just store the angles in an array?

If I want to check for scaling factors, how would implement that?
And what if 2 or more corners share the same angle, then I still have to do more shifts.

 

[fresh_42]

Thank you for your reply,
so if I have 30 points, i can make 30 vectors, right? Then, when I want to form the vector "C_i := (\bar{x}_i \bar{x}_{i+1} + \bar{y}_i \bar{y}_{i+1} \, , \, \bar{x}_i^2+\bar{y}_i^2 \, , \,\bar{x}_{i+1}^2 + \bar{y}_{i+1}^2 )_i"
, do I have 30 of those 3-dimensional vectors which I can store as one template, right? And why in that form, why isn't the square root in it? Couldn't i just store the angles in an array?

If I want to check for scaling factors, how would implement that?
And what if 2 or more corners share the same angle, then I still have to do more shifts.

Whether you store the square or the length doesn't make a difference, because it is the same information. Of course you could also store the angles, but then you have to perform an $\arccos$ operation and two possible solutions. I don't see an advantage here as $\cos \varphi_i$ will do. But storing all $\cos \varphi_i$ is probably the best thing to do.

You can pick an arbitrary angle to start with, say the one with index $1$ and search all $j$ with $\cos \varphi_1 = \cos \psi_j\;.$ Now all of them must be investigated. The next angle will show you, whether it is eventually a rotation or not. The previous angle indicates whether it's a reflection. As soon as a $\cos \varphi_{i+k} \neq \cos \psi_{j+k}$ they are either of different shape or you have to pick the next $j$ . A Boolean variable will certainly be helpful here to end calculations whenever the two shapes cannot be congruent, or you throw an exception depending on the language you use.

If all angles are the same and in the same (or reversed) order, say $\cos \varphi_{1+k} = \cos \psi_{j+k}$ (or $\cos \varphi_{1+k} = \cos \psi_{j-k}$ in case reflections are allowed) and $Q'_1,\ldots,Q'_n$ indicate the second polygon, then $|Q_1| / |Q'_j| = (\bar{x}_1^2+\bar{y}_1^2)\, / \, (\bar{x'}_j^2+\bar{y'}_j^{2})$ is the square of the scaling factor.

Note that all additions of indices above are modulo $n=30$. There are probably more possibilities to improve the algorithm, e.g. with less cosines, but I don't think that makes much of a difference. If your algorithm is slow, then it's very likely that you have either too many I/O operations or you ran over all $30!$ permutations instead of only the index shifts.

 

[YouWayne]

So the best way would be to store an Array of Integers (-1 to 1) for the templates. Now when I have an image, i filter out my polygon and make 30 3D-Vectors out if it. If I found an angle, say cosφ1 = cosψ5 and cosφ2 = cosψ6 and so on, it's the same shape. But how does that "pimp" the original algorithm? I also stored only the cosines and computet all angles of the new polygon and then compared the stored one with the already computet ones. Maybe you can spead up the algorithm with some kind of autocorrelation, so I don't have to do the shifting thing, if that's possible.

 

[fresh_42]

I cannot know where your runtime goes to. As already said, usually it's I/O's or exponential loops. The dimension isn't a problem here. The above is basically the same, whether $Q_i=(x_i,y_i)$ or $Q_i=(x_i,y_i,z_i)$. All arithmetic operations directly on the coordinates are fast. With the break condition for negative results and the shifts instead of complete permutations, the time is probably below $O(n^3)$: there are only two arrays of $30$ doubles with a fixed (or reversed) order to be compared. It is as if you have two rulers with one moving along the other that stops every time you have a coincidence, in which case you check, whether the rest is equal, too. Do not compare each entry with each other entry! I'm almost certain that - given the coordinates - it will run in less than a second.

Maybe to find the coordinates takes the time.

 

[YouWayne]

With 3D-Vector I meant your Ci-Vectors not Qi. But I still don't get your point :-/
"It is as if you have two rulers with one moving along the other that stops every time you have a coincidence, in which case you check, whether the rest is equal, too. Do not compare each entry with each other entry!" I'm already doing that, so I don't see any improvement from now on. What I do right now is taking the template (List of Integer(cosines)) and compute the new polygon also to a List of Integers (cosines) and comparing them the way you said. What role does Ci play in this?

 

[fresh_42]

The $C_i$ are fast to calculate and $\cos \varphi_i = \frac{C_{i1}}{\sqrt{C_{i2} C_{i3}}}\, ; \,O(n)$ operations.
I first thought we could save some cosines and could use the $C_i$ on demand, like

compute $\cos \varphi_1$
for i = 1 to n
if not break
compute $\cos \psi_i$
if compare $\cos \varphi_1 = \cos \psi_i \pm$ margin true
compute $\cos \varphi_2$
etc.

or forget about the angles and work with the $C_{ij}$ instead. E.g. calculate a potential scaling factor and compare the lengths $C_{i2}$ and $C_{i3}$ with $C'_{i2}$ and $C'_{i3}$

This would save a little time, because only for congruent polynomials all cosines would have to be computed. But on the other hand, computing $60$ cosines instead isn't much worse nowadays, me thinks. These loops look like $O(n^2)$ operations and therefore the entire algorithm goes even with $O(n^2)$ arithmetic operations. For $n=30$ I estimate less than $2,000$ arithmetic, shift and comparison operations worst case, $1,000$ on average. Nothing to worry about. If it's still slow, and you can rule out "find the coordinates" and "read / write operations", then my bet would be some environmental conditions like class building, bad variables or floating point engine or similar.

 

[YouWayne]

But I don't have to compute cosφ because they are already computed and saved in a database to compare with the polygons in the picture. I really only have to compute cosψ. And to make sure the hole polygon is similar I have to compute all of cosψ. And doing that everytime is not as good as computing all at first an then comparing to the ones in the database. So I still see no improvements, and also I cannot determine at which angle the polygon is rotated. A new solution would be better I think or some kind of the 3rd solution I mentioned.

But thank you for your help so far.

 

[fresh_42]

saved in a database to compare with the polygons in the picture

And here you have your runtime. DB I/O! You only need a badly indexed database or you close and re-open the queries too often and you're dammed to have a slow performance. Try to load them in one step beforehand, instead of single accesses. Or do some database maintenance!