Calculate similarity between two shapes

Question

I'm developing an app which lets the user draw in a specific area and then checks if the shapes he drawn are similar. For example, these are two shapes that should be considered similar (I cannot check the exactly coordinates because I need to be flexible since the users draw by hand):

The coordinates of the first shape are here: link1 and the coordinates of the second one are here link2

So, to check with precision if the shapes are similar, I thought to divide each on in 10 micro-segments (each of them composed by 1/10 of its points) and see the variation. This is the code:

private boolean checkShape (int z, ArrayList<Pair<Float,Float>> points) {
    ArrayList<Pair<Float,Float>> copia = segments.get(z);
    int nGroupsFirstShape = (segments.get(z).size()*10)/100;
    int nValuesFirstShape[] = new int[10];
    for (int j=0, j2=0; j<10; j++, j2+=nGroupsFirstShape) {
        int sumValues=0;
        sumValues+=copia.get(j2).first-copia.get(j2+nGroupsFirstShape-1).first;
        sumValues+=copia.get(j2).second-copia.get(j2+nGroupsFirstShape-1).second;
        nValuesFirstShape[j] = sumValues;
    }
    ArrayList<Pair<Float,Float>> copia2 = points;
    int nGroupSecondShape = (copia2.size()*10)/100;
    int nValuesSecondShape[] = new int[10];
    for (int j=0, j2=0; j<10; j++, j2+=nGroupSecondShape) {
        int sumValues=0;
        sumValues+=copia2.get(j2).first-copia2.get(j2+nGroupSecondShape-1).first;
        sumValues+=copia2.get(j2).second-copia2.get(j2+nGroupSecondShape-1).second;
        nValuesSecondShape[j] = sumValues;
    }
    int differences[] = new int[10];
    int numberOf = 0;
    for (int index=0; index<10; index++) {
        differences[index] = nValuesFirstShape[index] - nValuesSecondShape[index];
        if (differences[index]<0) differences[index] = -differences[index];
        if (differences[index]<nGroupsFirstShape*3.5) numberOf++;
    }
    if (numberOf>=6) return true; else return false;
}

copia is the ArrayList corresponding to the first shape, and copia2 the second one. The first thing I do, is calculating the 10% of the shape, so I know how big the micro-groups are, then I sum the difference between the X and the Y coordinates (to see how the segments moves through the draw) of that group and save it in an array which I will use to calculate the differences between the shapes. Then, once I calculated that, I check if the differences between the two shapes is less than nGroupsFirstShape*3.5 (a constant to keep a bit of flexibility). With this method it works, but I don't understand if it can be applied to all the geometric forms. This is the result of a print I made in the first for:

First Shape: 5
First Shape: 11
First Shape: 6
First Shape: 4
First Shape: 3
First Shape: 4
First Shape: -23
First Shape: -15
First Shape: -13
First Shape: -8

And this in the second for:

Second Shape: 1
Second Shape: 7
Second Shape: 8
Second Shape: 6
Second Shape: 6
Second Shape: 0
Second Shape: -4
Second Shape: -29
Second Shape: -19
Second Shape: -15

Then, these are the differences:

DIFF: 4
DIFF: 4
DIFF: 2
DIFF: 2
DIFF: 3
DIFF: 4
DIFF: 19
DIFF: 14
DIFF: 6
DIFF: 7

Since the first shape has been divide into micro-groups of 4 elements, the number of differences with a value less then 3.5*4 is 8 and it can be considered similar. Do you think that this algorithm can be applied to each geometric form? PS: sorry for my English, I'm Italian

And honestly: this isn't really a java specific question. The language used to implement your algorithm doesnt matter to that algorithm at all. — GhostCat, Aug 15 '19 at 07:50
What if the two shapes are identical, but are slightly shifted laterally? — Malt, Aug 15 '19 at 07:51
Another important consideration is when the shapes are visually similar, but the segment(s) is/are drawn in different order and/or direction. (Think of drawing x; https://www.today.com/popculture/how-do-you-draw-x-internet-confused-t147124 ) — Hans Olsson, Aug 15 '19 at 07:59
This is basically standard scan matching. Check for point cloud matching and Horn algorithm....@shukiavraham no machine learning required, just simple maths. — mikuszefski, Aug 15 '19 at 08:02
I made another method to invert the Y and the X axes to check if the shapes are drawn symmetrically, so I repeat the method above three times: one taking the shape as it has been drawn, one with the coordinates inverted on the Y-axis and the last one with the coordinates inverted on the X-axis — Fabio, Aug 15 '19 at 08:42
Before rushing to an algorithm, you should make up your mind (or explain us) how your shapes look like in general, what deformations are accepted and what features are important to declare similarity. — , Aug 15 '19 at 08:48
@YvesDaoust all the deformations are accepted. The similarity are based on what the human eye sees. In this case these shapes are similar because the path (or the variation between the points drawn) that the user draw is the same for each one. — Fabio, Aug 15 '19 at 08:55
"all the deformations are accepted" is not a valid description. Any curve can be deformed into any other by a continuous transform, so everything would match. Are d and p similar ? Are 5 and s similar ? — , Aug 15 '19 at 08:58
@YvesDaoust it is a classical problem to match one point cloud with another. A simple example is just a shifted and rotated 3D cloud and you need to find the best transformation from one to the other (Horn). Another application of the according methods is to match 2d scanned images, where rotation shift and scale might occur. This is what I mean by standard scan matching. As a result you get also a chi2 value giving you the quality of the match and that is likely what the OP was looking for. I am sure you get sufficient amount of hits using your preferred search engine. Cheers. — mikuszefski, Aug 15 '19 at 09:18
@mikuszefski: I see, "scan matching" refers to the fact that the point clouds are obtained from a 3D scanner. — , Aug 15 '19 at 09:52
@YvesDaoust Well, I know different cases, but yes, you some sort of 3D position measurement and you want to match 2 data sets. But 2D versions exist. — mikuszefski, Aug 15 '19 at 10:34
Maybe this is of interest https://stackoverflow.com/a/6487735/803359 , but I don't know to what extend it can deal with scale and rotation. — mikuszefski, Aug 15 '19 at 10:35
@mikuszefski: I was asking about "scan matching", which I never heard. I have been doing point cloud matching since years. — , Aug 15 '19 at 10:37
@YvesDaoust :) Hence the `Image-Processing` tag in your profile. — mikuszefski, Aug 15 '19 at 11:31
Do you guys think my method has a minimum of sense (however imprecise) or is it completely to be discarded? — Fabio, Aug 15 '19 at 12:18
@Fabio That's up to you to decide. We have no idea what your use case is and what's an acceptable error in that use case. — Malt, Aug 15 '19 at 14:44

Calculate similarity between two shapes

0 Answers0