⬆️ ⬇️

Own algorithm 2. Search for similar images

In my first article on Habré, I talked about my algorithm for searching for similar images. Today I want to talk about the second (improved) version of my algorithm.



The article will be slightly shorter than the previous one. I will tell only about the differences between the two algorithms. Therefore, it is advisable to read the previous article that would be "in the subject."



Key Point Detector



The first thing I want to emphasize separately is the fact that in my algorithm you can use any detector of key points that best suits your tasks and specific images. You can select the best detector empirically, or you can use an algorithm to automatically select, as the creators of the MODS algorithm do (thanks to the devpony for the tip).



For my algorithm and my situation, I will use Harris' corner detector. The Harris detector is invariant to rotations, partially invariant to affine changes in intensity, simple, reasonably accurate, and has such a measure of response that can be used to estimate the significance of key points.

')

We need only 10 of the most significant points!



Descriptor



And unlike the previous version, we will build not segments, but triangles, the vertices of which will be key points found by us.



The descriptor will be a series of lengths of three sides of a triangle, recorded from major to minor. A, B, C , where A> B> C.



Hash



From 10 points you can build 10 * 9 * 8/6 = 120 triangles. This means our hash will consist of 120 rows of 3 numbers A1, B1, C1; A2, B2, C2; ...; A120, B120, C120 .



Hash comparison



Comparison of two images is reduced to the search for similar triangles, built through their key points.



In accordance with the third sign of similarity of triangles:



If the three sides of one triangle are respectively proportional to the three sides of another, then such triangles are similar.


Since our hashes consist of the lengths of the sides of the triangles written in decreasing order, then the search for similar triangles is reduced to dividing numbers and comparing the results.



You need to compare all the triangles of one hash, with all the triangles of the second. If such a triangle is found, then these 2 triangles are excluded from further comparison (to increase the speed of comparison). If such a triangle was not found, then we increase the error counter by 1. After comparing all the triangles with all, we get the number of errors or the so-called. distance two hashes p .



Comparison result



As in the previous version of the algorithm for interpreting the results, it is necessary to compare the obtained distance P with a certain estimated value.



How do you like this version of the algorithm? Waiting for comments!



Links



In addition to the materials used in the last article.



Developer MODS algorithm page

Source: https://habr.com/ru/post/320994/



All Articles