Locate a b&w shape on a page. rotation and scale invariant

Python
1

Hello.

I would like to use OpenCV to search for a black and white shape within a page full of similar shapes. This is just for my own hobby project, and because I thought it would be interesting.

For an example of my actual inputs. Here is the kind of shape I want to locate and a page it is in. My goal would be that it locates that one labelled ER9 in this case:

example
example1709×1632 251 KB

I’ve been reading some background for a while and googling and found lots of things. I haven’t been able to adapt any example code to do this.

Do you think OpenCV is a good fit for solving this problem? and what are the exact algorithms and methods that would be best for doing it? Thanks!

2

so those are keyway profiles of pin tumbler locks.

the complexity of the problem depends on how big the “database” is.

I can think of some approaches:

  • alignment of point sets
  • shape matching based on “moments” because OpenCV has code for that
  • feature vectors from hand-crafted features (also moments)

an alignment of point sets implies a matching of points and various flavors of “distance” measure. basically, Iterative Closest Point, for 2D.

first, get contours.

  • keep it dense, no approximation.
  • scale, from pixels, into something metric (or inch-y). if that’s not possible, just get things close to equal size.
  • rotate so it’s roughly upright. in your reference sheet they’re all sideways so that’s an easy 90 degrees. that’ll shave off some iterations of ICP.
  • get bounding box, translate so the top center becomes the origin. makes sense for keys. far from necessary but may shave an iteration or two off the ICP.

perform ICP. ICP involves calculating a nearest-neighbor matching for all points of both sets (is what I would do), considering the resulting vectors, and deriving translation and rotation from that set of vectors. ICP can also account for some scaling.

during iteration, the sum of distances is observed. when that has settled (converged, not necessarily to 0), the sum of distances would tell you how well both point sets match.

you could also apply some geometry processing (or “cheat” and draw the polygons as binary masks) and then consider the area of intersection vs. the area of the union

if the database is large, all of this can take a moment to calculate. anything that has to compare rich data will be slow. comparing hashes or feature vectors will be cheap, and more importantly, indexable. that puts a query in a different complexity class.

you could try some kind of “signature” (not exactly hashing). normalize a profile as above, then “measure” a few things on it like

  • area of profile
  • a bunch of “moments”, also hu moments
    – opencv’s shape matching code uses those anyway
  • thickness and offset from center line at various heights
  • number of kinks/corners in the entire profile
  • all straight lines, or does the profile have a few curves (how many)

that’ll give you a “feature vector”. stuff them all in a database. now it’s a database problem to find the “nearest neighbor”. FLANN can be used for that. OpenCV comes with it.

FlannBasedMatcher isn’t terribly well documented but there’s at least one example that shows how to use it with custom data instead of existing feature descriptors (you might have heard of SIFT or AKAZE).

here’s a recipe where I use FLANN to undo the application of a colormap (turn false color back into "values’) decolormap.ipynb · GitHub

1 Like