Solution Timeline

All versions (edits) of solutions to Efficient pattern matching algo (python or js) appear below in the order they were created. Comments that appear under revisions were those created when that particular revision was current.

To see the revision history of a single solution (with diffs), click on the solution number (ie. "#1") in the upper right corner of a solution revision below.

← Bounty Expand all edits

I started experimenting with a somewhat brute-force approach algorithm: the target (image) is scanned for the pattern from top to bottom and left to right. At each scan-cycle, the white and black cells that match are added to an accuracy score (2x for black ones, 0.5x for white ones) and then are calculated depending on the total cells that are compared.

I've set up a little demo here: https://codepen.io/kostasx/pen/RwrZEvO?editors=0011

As you can see, in the beginning, the pattern placed at the exact subsection, matches at about 92% accuracy. As you move the pattern (window) back and forth, you'll see it being compared to other subsections of the image along with the accompanying accuracy.

The algorithm is contained in the findPattern function which returns an object with each match categorized according to its accuracy along with a full list array with all the comparisons. You can play around with the scores (section: if ( entry === 1 ){ ... } else { ... }) and see different accuracy scores.

I am not sure if this approach will get you close to the desired result, but my curiosity and my intuition led me here (mostly my curiosity to see how this algorithm would behave).

Other ideas, that came to mind, are the perceptual hashing algorithm and of course Machine Learning.

If you have more examples to provide (target + pattern to match), perhaps I can test this setup and see how it goes.

Hope this helps you in some way. You can take it from here and experiement.

I started experimenting with a somewhat brute-force approach algorithm: the target (image) is scanned for the pattern from top to bottom and left to right. At each scan-cycle, the white and black cells that match are added to an accuracy score (2x for black ones, 0.5x for white ones) and then are calculated depending on the total cells that are compared.

I've set up a little demo here: https://codepen.io/kostasx/pen/RwrZEvO?editors=0011

As you can see, in the beginning, the pattern placed at the exact subsection, matches at about 92% accuracy. As you move the pattern (window) back and forth, you'll see it being compared to other subsections of the image along with the accompanying accuracy.

The algorithm is contained in the findPattern function which returns an object with each match categorized according to its accuracy along with a full list array with all the comparisons. You can play around with the scores (section: if ( entry === 1 ){ ... } else { ... }) and see different accuracy scores.

I am not sure if this approach will get you close to the desired result, but my curiosity and my intuition led me here (mostly my curiosity to see how this algorithm would behave).

Other ideas, that came to mind, are the perceptual hashing algorithm and of course Machine Learning.

If you have more examples to provide (target + pattern to match), perhaps I can test this setup and see how it goes.

Hope this helps you in some way. You can take it from here and experiement.

P.S. So far I was just experimenting, but of course there's room for optimizations and performance refactoring.

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.

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