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

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.<\/p>\n\n

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

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.<\/p>\n\n

The algorithm is contained in the findPattern<\/strong> 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.<\/p>\n\n

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). <\/p>\n\n

Other ideas, that came to mind, are the perceptual hashing algorithm<\/a><\/strong> and of course Machine Learning.<\/p>\n\n

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

Hope this helps you in some way. You can take it from here and experiement.<\/p>\n

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](https://www.wikiwand.com/en/Perceptual_hashing)** 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.

User: kostasx

Question: Efficient pattern matching algo (python or js)

Back to question