I’m preparing to add a new feature for my Open Source project for image registration ‘Limereg‘, which was inspired by the ImageMagick community who asked me for a solution for the ImageMagick compare -subimage-search command that allows for more than only translation.
For searching such a smaller image inside a big one, that is not only translated, but also rotated (rigid registration) or stretched (affine registration), I will try to perform a series of image registrations on different starting positions.
Algorithm (with regard to the multilevel pyramid scheme, Limereg uses):
- Create pyramid images of the big reference (R) and the small template (T) image.
- On the coarsest level register the smaller image to be searched (T) on the bigger image (R)
- Do this several times from different starting positions. E.g. by putting an equidistant grid of starting positions on R.
- The best (resulting in the smallest SSD distance measure) n% (e.g. 20%) of positions may survive for the next run on the next finer pyramid level.
- The next finer level should have a finer grid of starting positions. E.g. for each position that ‘survived’ above, create four new grid-positions (2×2) around the survived one.
- Repeat this steps recursively until the finest level has been reached.
- The best (smallest SSD) result points to the found subimage, if the resulting SSD is below a threshold.
I’m very curious how this will work out and how fast it will be.