IM compare with subimage-search does a search of every possible position, shifting one pixel at a time and getting the compare metric score. At the end, it reports the location of the best match and the match score (and optionally a match score image).
Do you think your app will be too slow to do that? Is that why you suggest a grid?
One technique that is use is to reduce the images and do it one. Then find a region about the best score and repeat only in that region for the full resolution images.
Offering new feature: Image registration
Re: Offering new feature: Image registration
Note: I'm dumping my makefile and move to GNU autotools (configure). Makes life easier for people using the lib, I guess.
Re: Offering new feature: Image registration
First version based on autotools for a sneek peak:
http://embedded-software-architecture.c ... 9.3.tar.gz
Better, however, wait for 1.0.0 before starting the integration.
http://embedded-software-architecture.c ... 9.3.tar.gz
Better, however, wait for 1.0.0 before starting the integration.
Re: Offering new feature: Image registration
Hi fmw42,
Regarding the grid-search: The 'magick' of the algorithm is that it is iterative and automagically proceeds comparing into the right direction. This is done by analytically (!) solving an optimization problem, where shift/rotation are the parameters to be optimized. To say it a bit rough (well, don't let my old math professor read this
: Because derivatives are used, the algorithm knows more than the current place it is looking at, it has some good assumptions about the solution space in the neighborhood. Therefore the algorithm does not try out every possible solution (like the algorithm you mentioned), instead it knows that e.g.: From the current place 10 pixels to the right and 5 pixels to the top and 4 degrees rotation is the next place to look at. The algorithm is very effective in predicting where is the next best place to look at and can align or 'find' images after just a few tries, like 5 or 10.
Iterating through all possibilities would probably be far slower, esp. for an affine setting where six parameters (rigid: three) have to be tried out. Imagine 1000x1000 pixel. For a shift-only-search (as implemented today) this is 10E6 times a try. If one has six parameters it is 1000x1000x1000x1000x1000x1000 = 10E18 times a try. The algorithm I wrote would for equisized images just try a few times (again, like 5 or 10). But, however, each try is more computaionally demanding, because derivatives have to be calculated to have some projection of the solution space around each particular position. For details see chapter three of http://www.embedded-software-architectu ... eprint.pdf .
Regards,
Roelof
Regarding the grid-search: The 'magick' of the algorithm is that it is iterative and automagically proceeds comparing into the right direction. This is done by analytically (!) solving an optimization problem, where shift/rotation are the parameters to be optimized. To say it a bit rough (well, don't let my old math professor read this
: Because derivatives are used, the algorithm knows more than the current place it is looking at, it has some good assumptions about the solution space in the neighborhood. Therefore the algorithm does not try out every possible solution (like the algorithm you mentioned), instead it knows that e.g.: From the current place 10 pixels to the right and 5 pixels to the top and 4 degrees rotation is the next place to look at. The algorithm is very effective in predicting where is the next best place to look at and can align or 'find' images after just a few tries, like 5 or 10.Iterating through all possibilities would probably be far slower, esp. for an affine setting where six parameters (rigid: three) have to be tried out. Imagine 1000x1000 pixel. For a shift-only-search (as implemented today) this is 10E6 times a try. If one has six parameters it is 1000x1000x1000x1000x1000x1000 = 10E18 times a try. The algorithm I wrote would for equisized images just try a few times (again, like 5 or 10). But, however, each try is more computaionally demanding, because derivatives have to be calculated to have some projection of the solution space around each particular position. For details see chapter three of http://www.embedded-software-architectu ... eprint.pdf .
Regards,
Roelof
Re: Offering new feature: Image registration
Details about the planned adaption of my Image Registration code for subimage-searches.
http://embedded-software-architecture.com/?p=183
Unfortunately the API has to be changed heavily.
https://raw.githubusercontent.com/Roelo ... /limereg.h
I will provide an example code in:
https://github.com/RoelofBerg/limereg/b ... Subimage.c
(Currently this file does not contain the new algorithm, it just tests the C interface, which should be sufficient for a subimage search now.)
http://embedded-software-architecture.com/?p=183
Unfortunately the API has to be changed heavily.
https://raw.githubusercontent.com/Roelo ... /limereg.h
I will provide an example code in:
https://github.com/RoelofBerg/limereg/b ... Subimage.c
(Currently this file does not contain the new algorithm, it just tests the C interface, which should be sufficient for a subimage search now.)
Re: Offering new feature: Image registration
We've been holding off adopting the image registration code in ImageMagick until the API becomes stable. When you have confidence the API is stable, post here and let us know.