Revisions for "Efficient pattern matching algo (python or js)"

Efficient pattern matching algo (python or js)

I need to compare a cropped image or slightly skewed image against a corpus of images to find matches. My first thought was it can be something like fingerprint matching since there is a concept of partial fingerprint matches.

here is the scenario. I have 100K images in a corpus. I have processed these to come up with a fingerprint of the image. It looks like this https://www.dropbox.com/s/a7028so6mfnj9sf/2020-06-26_07-23-44.png?dl=0 you can think of it as a matrix where we have either a 1 or zero in a bubble zone.

now i have an image that i need to check against the corpus to find the match. its a smaller subset of the 1/0 pattern and visually looks like this - https://www.dropbox.com/s/2uchttganjbfc3i/2020-06-26_07-25-35.png?dl=0

here you can see the subsection - https://www.dropbox.com/s/rxg8ni6b6w22qn0/2020-06-26_07-25-50.png?dl=0

so we need an algo that we can use the data matrix of values to find the pattern or partial pattern match. Ideally it can be resilient to slight differences (Im thinking some sort of confidence score like 90% sure this image is a subset of image X, or 70% sure its a subset of image Y.

My thought is that we can express the matrix numerically as a curve (signal) and then attempt to find signal or partial signal matches. Totally guessing and thats why Im turning to the community here for a bounty project.

The first place bounty will be $100, second place $50 and 3rd place $25. Ideally with your submission there is some technical details or pseudo code to represent your idea.

Efficient pattern matching algo (python or js)
I need to compare a cropped image or slightly skewed image against a corpus of images to find matches. My first thought was it can be something like fingerprint matching since there is a concept of partial fingerprint matches. here is the scenario. I have 100K images in a corpus. I have processed these to come up with a fingerprint of the image. It looks like this https://www.dropbox.com/s/a7028so6mfnj9sf/2020-06-26_07-23-44.png?dl=0 you can think of it as a matrix where we have either a 1 or zero in a bubble zone. now i have an image that i need to check against the corpus to find the match. its a smaller subset of the 1/0 pattern and visually looks like this - https://www.dropbox.com/s/2uchttganjbfc3i/2020-06-26_07-25-35.png?dl=0 here you can see the subsection - https://www.dropbox.com/s/rxg8ni6b6w22qn0/2020-06-26_07-25-50.png?dl=0 so we need an algo that we can use the data matrix of values to find the pattern or partial pattern match. Ideally it can be resilient to slight differences (Im thinking some sort of confidence score like 90% sure this image is a subset of image X, or 70% sure its a subset of image Y. My thought is that we can express the matrix numerically as a curve (signal) and then attempt to find signal or partial signal matches. Totally guessing and thats why Im turning to the community here for a bounty project. The first place bounty will be $100, second place $50 and 3rd place $25. Ideally with your submission there is some technical details or pseudo code to represent your idea.. --- more of my thoughts on how to approach maybe (update 1) so i think there should be a reasonable way to represent this string as a "signal" and then i can try to match other signals against it for full match or fuzzy match thinking something like a cosine wave or maybe i mean sine wave reason I'm thinking signals is i did some research on fingerprint recognition and thats generally how they approach it as a series of cosine waves per print. and then they try to fuzzy match those aka - Fingerprint matching by using 2D discrete cosine transform and 2D Fourier transforms. Not sure if this helps or not but thought i would share
Efficient pattern matching algo (python or js)
I need to compare a cropped image or slightly skewed image against a corpus of images to find matches. My first thought was it can be something like fingerprint matching since there is a concept of partial fingerprint matches. here is the scenario. I have 100K images in a corpus. I have processed these to come up with a fingerprint of the image. It looks like this https://www.dropbox.com/s/a7028so6mfnj9sf/2020-06-26_07-23-44.png?dl=0 you can think of it as a matrix where we have either a 1 or zero in a bubble zone. now i have an image that i need to check against the corpus to find the match. its a smaller subset of the 1/0 pattern and visually looks like this - https://www.dropbox.com/s/2uchttganjbfc3i/2020-06-26_07-25-35.png?dl=0 here you can see the subsection - https://www.dropbox.com/s/rxg8ni6b6w22qn0/2020-06-26_07-25-50.png?dl=0 so we need an algo that we can use the data matrix of values to find the pattern or partial pattern match. Ideally it can be resilient to slight differences (Im thinking some sort of confidence score like 90% sure this image is a subset of image X, or 70% sure its a subset of image Y. My thought is that we can express the matrix numerically as a curve (signal) and then attempt to find signal or partial signal matches. Totally guessing and thats why Im turning to the community here for a bounty project. The first place bounty will be $100, second place $50 and 3rd place $25. Ideally with your submission there is some technical details or pseudo code to represent your idea. --- more of my thoughts on how to approach maybe (update 1) so i think there should be a reasonable way to represent this string as a "signal" and then i can try to match other signals against it for full match or fuzzy match thinking something like a cosine wave or maybe i mean sine wave reason I'm thinking signals is i did some research on fingerprint recognition and thats generally how they approach it as a series of cosine waves per print. and then they try to fuzzy match those aka - Fingerprint matching by using 2D discrete cosine transform and 2D Fourier transforms. Not sure if this helps or not but thought i would share --- shazam (update 2) started looking how an app like shazam works and it seems similar to the ideas above, nicely laid out here. https://www.toptal.com/algorithms/shazam-it-music-processing-fingerprinting-and-recognition so maybe the solution is to convert the image representation to a signal and then process it in a similar way to the music?
Back to question