Offering new feature: Image registration

[rberg]

Hello,

recently I developed a simple and fast algorihm for rigid image registration. I wonder if it could be interesting for Imagemagick.

Example:
mogrify -register reference.jpg template.jpg

Would shift/rotate template.jpg in a way that it is aligned to reference.jpg (best possible overlay). Read more in my paper http://www.embedded-software-architectu ... eprint.pdf (this is a preprint, the final publication is available at link.springer.com).

If it is interesting (at all), I wonder what would be the best way to contribute.
a) Place the registration code (https://github.com/RoelofBerg/limereg) into a library and link imagemagick to that library.
b) Copy and paste the registration code to the imagemagick codebase (which I haven't looked at yet at all - is there a tutorial for contributors ?).

Best regards,
Roelof

[magick]

ImageMagick is ANSI C so we can't directly import your C++ source, instead it may make sense to create an API, that we can call. Like other delegate libraries, we would use automake / autoconf to search for the API, if found, support for image registration is included in that instance of ImageMagick.

[rberg]

I see, thanks, so I will extract the tool's features into a library. I'm not sure yet which method I will use for extracting code of an executable-project into a library.

a) Use a makefile that has a special make target for a library-only-version (instead of an executable), like 'make lib' and 'make lib-install'.

b) Split up the tool into two distinct projects. One pure library project containing the algorithm and one small executable project that is just a shell frontend to the library.

The first way is more lean and pragmatic, probably using some #ifdef. The second method is more tidy. Which one would you use in an Open Source context ? (In an industrial project I'd use variant b, but in the Open Source community variant a might be favorable for it's reduced complexity ?)

[magick]

Use b). Your command-line program calls the API and proves the algorithm works and isolates the API calls. The ImageMagick project can then make those same API calls. Note you must export a portion of the API in C so ImageMagick can utilize it.

[rberg]

Ok, now I have a library 'liblimereg' that can be called from C and processes byte-stream-images. I'm also busy with packaging the library for Debian (the official repo, if they allow me to).

API so far (simplified):

Code: Select all

int Limereg_RegisterImage(
                unsigned char* imgRef,       //input buffer
                unsigned char* imgTmp,      //input buffer
                unsigned int xDimension,
                unsigned int yDimension,
                unsigned char* imgDst        //output buffer
                );

I have little experience with ImageMagick, and I wondered what library might be the best template/example for me for the configure script and the code modifications. Maybe Liquid Rescale ?

My algorithm transforms an image (template.jpg) by taking another image as input data (reference.jpg): mogrify -register reference.jpg template.jpg. The lib needs the data of both images as byte-array, 1 byte for each pixel's luminance (greyscale). And the image dimensions as integer. What would be the best starting point (which delegate-lib ? Which mogrify-command belongs to this lib ?)

Thanks, I aprechiate every hint.

[fmw42]

I would love to see this implemented. But I am puzzled why you are using mogrify and also as far as I can tell there is no -register option at least not listed at http://www.imagemagick.org/script/mogrify.php.

Seems to me that you should be using

Code: Select all

compare -metric XX -subimage-search largeimage smallimage null: 

to locate the best match between two different size images.

[magick]

https://github.com/RoelofBerg/limereg currently will not compile, at least not under Fedora. Let's us know when it does and we'll look into calling the API from ImageMagick.

[rberg]

Great ! I extracted the sole library to: https://github.com/RoelofBerg/liblimereg. If
make
sudo make install-dev
doesn't work, please let me know. Note: 'make lib' can be used instead of 'make all' to avoid the dependency to doxygen.

Calling example see folder named 'test' (make test). Another example is the command line utility limereg https://github.com/RoelofBerg/limereg, of which the library liblimereg was extracted from, that gives also visual example output by OpenCV.

The current version of the library-extract liblimereg is 0.9.0. This version can only handle images with square dimensions (width==height). V1.0.0 will be ready in a few weeks and will be able to deal with images in arbitrary page ratios. Image format: One byte per pixel (luminance / grey value). Furthermore there is some potential for performance optimization left in the code, that surrounds the algorithm (the algorithm itself is pretty much performance optimized).

Regards,
Roelof

[rberg]

Hi fmw42,

thanks for noting about the demand for a solution The algorithm operates on equisized images. The result of the (rigid, 2D) image registration is an angle and an x-shift, y-shift. So the rigid transformation parameters needed to align the images. The example images on the .pdf in the original post will be pretty speaking.

If you need something else, let's talk about it (well, you mentioned it allready Maybe I can extend the algorithm.

The library can output either angle and shift as numerical values, or it can transform an template image to be best aligned with a reference image - that's where I assume, mogrify can be useful. The output is a rotated/shifted image to be best aligned to another one. The command 'register' would have to be added in this case to mogrify. But, I have little experience in Image Magick, maybe another way of execution will be more suitable to the usage intended by the Image Magick authors.

Regards,
Roelof

[rberg]

Note for the tryout:
Usually images for image registration have content in the middle that is surrounded by a black background, like in the .pdf mentioned in the original post. The current algorithm works best with this types of images. I'm working on a way to be more tolerant to image edges with content>0 (there are five aproaches of which I have to choose one).

[fmw42]

It would be a great extension to be able to match/register the two images when one image is larger than the other. That is not only get the scale and rotation, but the offset as well.

[rberg]

Extending rigid registration to affine would be pretty easy. (In fact one has to ADD more math to the affine registration to get a rigid one - which we did.) This aproach would allow more flexibility (like magnification or shearing) when needed. Even more easily I could allow a smaller template image to be 'found' in the reference image, while keeping the rigid transformation aproach. Then with several attempts from different starting points one could 'find' the subimage and determine by the distance measure (which is allways returned in addition to the image position) wether this is a 'hit'. Sounds interesting, one could find stuff in bigger images this way, like faces in a crowd.

[fmw42]

See Imagemagick compare with -subimage-search. It allow one to search for the best match. But it does not allow for scale, rotation, shear; only translation.

http://www.imagemagick.org/script/compare.php
http://www.imagemagick.org/Usage/compare/
viewtopic.php?f=1&t=14613&p=51076&hilit ... ric#p51076 (but now requires -subimage-search)

[rberg]

Ok. I just noticed that you have > 15000 posts. Dear, who am I e-mailing to ? And magick also has so many, many posts. Such an honor

I'm currently busy with bringing limereg and liblimereg into Debian. Which also means to do get rid of some limitations (square image size). Feature work can be done after this task.

A subimage search feature would be easy when I just allow the template image to be smaller than the reference image (which is allready the case under the hood - but not in the API yet), and when I allow to pass the starting point to the algorithm (which is now constantly 0, also only an API issue). Both should be very easy. Then all one has to do is to call the registration several times with several starting points and take the best result (or abort at the first sufficient result, which is easy, as one gets the distance measure in return).

It would be a simple algorithm, yust a matter of some hours of coding:
for(y...)
for(x...)
ssdNew = register(... x, y ....)
if (ssdNew < bestSSD)
remember result (shift, rotation)
bestSSD = ssdNew

The question is, where such an algorithm should be placed ? I see liblimereg more as a general functionality, and the example above as the application of the algorithm. This would lead me to the assumption that the code that will follow the example above should be in Imagemagick and liblimeregs API should only be versatile enough, to support such an algorithm. Would you agree ?

By the way, in Ubuntu liblimereg v0.9.2 can (now) be installed by:
sudo add-apt-repository ppa:roelofberg/limereg
sudo apt-get update
sudo apt-get install liblimereg0 liblimereg-dev

Thanks for sharing your ideas.

Regards,
Roelof

[rberg]

(x,y: Gridsize smaller than the Imagesize. E.g. every 50 pixels for a 100 pixel subimage. Has to be found out ...)