How to compare two shapes?
I have the same problem. I compute the adjacent matrix of the vertex weighted with the distances. This compute all the sides length and diagonals. Then if the module of each row or column of the matrix are the same with the other matrix, then the two shapes are the same. For the tolerance just use the function round() before start. The complexity is O(n2 / 2), because you have to compute just an half of the adjacent matrix that is symmetric. The problem is that I cannot detect if a shape is flipped.
handle shape as polygon
convert your points (each line) to set of lines
(length,angle)
like on this image:this ensures invariance on rotation/translation. If you see more lines with
angle=PI
join them together to avoid miss comparisons of the same shapes with different sampling also try to match the same CW/CCW polygon winding rule for both shapes.find start point
Can be biggest or smallest
angle, length
... or specific order ofangles+lengths
. So reorder lines of one polygon(cyclic shift)
so your shapes are compared from the 'same point' if they can.comparison - for exact match
- number of lines have to be the same
- perimeters must be the same +/- some accuracy
so for example:
fabs (sum of all lengths of poly1 - sum of all lengths of poly2) <= 1e-3
if not shapes are different. Then compare all lengths and angles. If any one value differs more then accuracy value then shapes are different.
comparison - size does not matter
compute perimeter of both polygons
l1,l2
and resize all lengths of comparedpoly2
to match perimeter ofpoly1
so all lengths ofpoly2
are multiplied byvalue = l1/l2;
. After this use comparison from bullet #3comparison - shape deviations can still do positive match (size must be the same)
try to set the number of lines to the same value (join all lines with angle close to
PI
). Then perimeters should "match" ...fabs(l1-l2)<=1e-3*l1
. You can use bullet #4 comparisoncomparison - size and shape deviations can still match
just resize
poly2
to match perimeter ofpoly1
as in bullet #4 and then use bullet #5
If you can not find the start point in booth polygons (bullet #2)
Then you have to check for all start point shifts so if your polygons have booth 5 lines:
poly1: l11,l12,l13,l14,l15
poly2: l21,l22,l23,l24,l25
Then you have to compare all 5 combinations (unless you found match sooner):
cmp (l11,l12,l13,l14,l15),(l21,l22,l23,l24,l25)
cmp (l11,l12,l13,l14,l15),(l22,l23,l24,l25,l21)
cmp (l11,l12,l13,l14,l15),(l22,l23,l24,l25,l21)
cmp (l11,l12,l13,l14,l15),(l23,l24,l25,l21,l22)
cmp (l11,l12,l13,l14,l15),(l24,l25,l21,l22,l23)
cmp (l11,l12,l13,l14,l15),(l25,l21,l22,l23,l24)
[Notes]
There are also faster ways to compare but they can miss in some cases
- you can compare histograms of lines, angles
- you can use neural network (I do not like them but they are ideal for classifications like this)
if your shapes have to be oriented in the same ways (no rotation invariance)
then instead of vertex angle use the line direction angle
if you can not ensure the same winding rule for both compared polygons
then you have to check them booth:
cmp (l11,l12,l13,l14,l15),(l21,l22,l23,l24,l25) cmp (l11,l12,l13,l14,l15),(l25,l24,l23,l22,l21)
I know it is a bit vague answer but still hope it helps at least a little ...
I am not sure how do you want to solve this problem. you want to go deep or you just want a solution. I can suggest you use an OpenCV function called "matchShapes". This function is based on Hu moments and has a good performance for rigid shapes. After you extract the target and the main contours then use the below code to compare them.
dif = cv.matchShapes(Contour1, Contour2, 1, 0, 0)
Smaller "dif" value means more similarity between contours.