kerncy's solution to "Efficient pattern matching algo (python or js)"

Hi<\/p>\n\n

As far as I know, all recognition algorithm always work with derivative data of fingerprints, so you are not subject to resizing issue. So here is my idea ( a bit complicated I assume it)<\/p>\n\n

If you want to compare two curves for example, it's easier to compare their derivative (when they are going up or down) instead of their absolute value (relative delta between all values).<\/p>\n\n

for example if you take : <\/p>\n\n

Hi As far as I know, all recognition algorithm always work with derivative data of fingerprints, so you are not subject to resizing issue. So here is my idea ( a bit complicated I assume it) If you want to compare two curves for example, it's easier to compare their derivative (when they are going up or down) instead of their absolute value (relative delta between all values). for example if you take : - y = sin(x) - y = 0.5 * sin(x) both curves have exactly the same derivative, but the relative delta would be huge (moreover, it depends on your domain). With this intuition you can see that the resizing is not take into account. If you expand this idea to your image, your fingerprint which contains absolute positions of 0 and 1 are pure data that are subject to resizing. An idea would be to compute slopes between nearest points (3 for example) on your curve. That will lead you to a list of slopes for each "remarquable point". Than you will have to compare your list of slopes to your cropped images, and if it matches you find your solution. As an example, consider your original image : https://zupimages.net/up/20/27/190s.png slopes ((yb-ya) / (xb-xa)) with 3 neighbours would be for each point (I take clockwise 3 nearest neighbour) - Point A [1,1] --> [to B : 0 | to D : 2/3 | to E : INF] - Point B [5,1] --> [to C : 1/2 | to D : -1/2 | to F : -1/2] - ... - ... - Point H [2,8] --> [to E : -4 / -1| to F : -3 / 1 | to G : -1 / 4] Than do the same for your cropped/resized image. For each point of your cropped compute fingerprint with the same algorithm. Next step, for each point of your cropped image, compute all the relative slopes with all points of your original images. The one with relative slopes nearest to 0 matches your original image The more point in your image near 0 that matches your original image slopes, than the greatest chance you have to match your original image. EDIT : just an update, this only works if your resize is an homothety (same factor for x and y resize) otherwise it would fail

User: kerncy

Question: Efficient pattern matching algo (python or js)

Back to question