Potential contribution: subpixel cross correlation

[Mike Sarahan]

Hi there,

I've implemented this code in Python for one of my projects:

http://www.mathworks.com/matlabcentral/fileexchange/18401-efficient-subpixel-image-registration-by-cross-correlation

It seems to me like this might fit in scikits-image.  If you guys would like, I'll clean up my code and do a PR.  I'm not sure what the general use cases would be, though - for me, all I care about is the subpixel registration value (how much to shift the images so that they are aligned).  Would anyone have any other use cases for this sort of thing?  I see this as not quite the same as template matching, but please correct me if I'm wrong.

Best,
Michael

[Stuart Mumford]

Hello,

I think we could use this in SunPy, we are currently working on template matching but having multiple options would be handy.

Stuart

--
You received this message because you are subscribed to the Google Groups "scikit-image" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scikit-image...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Stéfan van der Walt]

Hi Mike

On Sat, Apr 26, 2014 at 8:24 PM, Mike Sarahan <msar...@gmail.com> wrote:
> http://www.mathworks.com/matlabcentral/fileexchange/18401-efficient-subpixel-image-registration-by-cross-correlation

Are you doing phase correlation, or cross-correlation in the image
domain? If so, I wonder if you can build on top of the existing
template matching algorithm to use that as an initial value from which
to start the subpixel search?

Anyway, always keen to be able to do better alignment, and would love
to build out the registration capabilities in scikit-image.

Thanks for getting in touch!
Stéfan

[Michael Sarahan]

Hi Stefan,

As I understand it, it's phase correlation, but with a clever way of upsampling the DFT to achieve subpixel registration.  The algorithm does one cross correlation in the frequency domain, finds the maximum, then expands around that maximum to arbitrary (user-specified) precision.

My experience with template matching is to use it for finding a smaller image in a larger image.  I've used only OpenCV for that, so please forgive my lack of understanding of scikit-image's template match.  I use this for finding the shift that registers two equally-sized images.  I can't use OpenCV's template matching for that, because it always returns a cross correlation that is the size of the larger image minus the size of the smaller image, which for equally sized images is 0.  Based on the docs, it looks like that's also true for scikit-image?  Phase correlation works pretty well in these cases, but I've found that this particular algorithm works better than OpenCV's phase correlation, thanks to its approach to upsampling.

I'll put things together for a PR, and I'll look forward to comments/revisions...

Best,
Mike

[Tony Yu]

On Sat, Apr 26, 2014 at 12:02 PM, Stéfan van der Walt <ste...@sun.ac.za> wrote:

Hi Mike

On Sat, Apr 26, 2014 at 8:24 PM, Mike Sarahan <msar...@gmail.com> wrote:
> http://www.mathworks.com/matlabcentral/fileexchange/18401-efficient-subpixel-image-registration-by-cross-correlation

This sounds interesting, but I'm a bit worried by the license. Most posts on the File Exchange have a BSD license, but this particular contribution has "No BSD License" written next to it. I'm not sure what the protocol is for derivative works, but it's something to keep in mind.

Best,

-Tony

[Michael Sarahan]

I've emailed the original author (Manuel Guizar) and asked about licensing.  I'll make sure it's OK to bring under the scikit-image license before I do a PR.

Best,
Mike

--

[Stéfan van der Walt]

On Sat, Apr 26, 2014 at 10:50 PM, Michael Sarahan <msar...@gmail.com> wrote:
> Based on the docs, it
> looks like that's also true for scikit-image?

Here's what I meant:

http://nbviewer.ipython.org/urls/dl.dropbox.com/s/dmqwusnh9hlk505/find_shift.ipynb

This is very slow, though, and a bit of a hack, so I'm happy to
include this algorithm (if, as Tony mentioned, the license checks
out).

Thanks!
Stéfan

[Michael Sarahan]

Hi Stefan,

Your example highlights a critical issue: handling color data.  I've only ever played with grayscale data (electron microscope images).  I tested my code with your example image, and it falls over.  Do you have any tips for what special handling I might need to do (convolutions, finding maxima)?  I can just grayscale the input images, but that doesn't feel like an optimal solution.

Thanks,
Mike

Stéfan

[Stéfan van der Walt]

On Sun, Apr 27, 2014 at 2:48 AM, Michael Sarahan <msar...@gmail.com> wrote:
> Your example highlights a critical issue: handling color data. I've only
> ever played with grayscale data (electron microscope images). I tested my
> code with your example image, and it falls over. Do you have any tips for
> what special handling I might need to do (convolutions, finding maxima)? I
> can just grayscale the input images, but that doesn't feel like an optimal
> solution.

Perhaps Juan can answer this one--he is our most vocal 3D proponent!

In the meanwhile, getting a version up and running with tests in 2D is
a great start.

Stéfan

[Juan Nunez-Iglesias]

On Sun, Apr 27, 2014 at 10:53 AM, Stéfan van der Walt <ste...@sun.ac.za> wrote:

Perhaps Juan can answer this one--he is our most vocal 3D proponent!

Haha, 3D is not the same as 2D+c! I'm actually also used to grayscale EM images, but in 3D. For that case, I think the generalisation would be straightforward. For 2D+c, I have no idea!

In the meanwhile, getting a version up and running with tests in 2D is
a great start.

Or 3D grayscale. Just a suggestion. ;)

Juan.

[Michael Sarahan]

Sorry guys, things aren't looking good for the license.  Manuel was kind enough to reply to me and to forward my message to James Fienup, but it seems the license (or lack thereof) was already a point of contention between Manuel and James.

I'm going to leave my branch open for anyone wanting to use the code, but I think it's better to not include officially until a license is determined for the parent work.
https://github.com/msarahan/scikit-image/tree/PhaseCorrelation

Best,
Michael

[Stéfan van der Walt]

Hi Michael

On Mon, May 5, 2014 at 5:21 AM, Michael Sarahan <msar...@gmail.com> wrote:
> Sorry guys, things aren't looking good for the license. Manuel was kind
> enough to reply to me and to forward my message to James Fienup, but it
> seems the license (or lack thereof) was already a point of contention
> between Manuel and James.

Did James sound like he was willing to negotiate on the license terms?
If not, is this work published and unpatented?

Stéfan

[Michael Sarahan]

Hi Stefan,

I wrote to Prof. Fienup last Tuesday, but haven't heard back.  The work is published, and to the best of my knowledge unpatented (Google patent search turns up nothing.)  Let me know if you'd still be up for a PR.

Best,
Michael

[Stéfan van der Walt]

Hi Michael

On Tue, May 13, 2014 at 6:02 AM, Michael Sarahan <msar...@gmail.com> wrote:
> I wrote to Prof. Fienup last Tuesday, but haven't heard back. The work is
> published, and to the best of my knowledge unpatented (Google patent search
> turns up nothing.) Let me know if you'd still be up for a PR.

I would prefer to get Prof. Fienup's approval of the work. However,
if that cannot be obtained we can still publish code if we can show
that it was derived purely from the published information (not from
the "tainted" code the current version is based on).

Regards
Stéfan

[j...@rybarski.com]

Where are things at with this? The method works incredibly well and my current project is pretty much impossible without it.

[Stéfan van der Walt]

On Sat, Jul 12, 2014 at 10:11 PM, <j...@rybarski.com> wrote:
> Where are things at with this? The method works incredibly well and my
> current project is pretty much impossible without it.

If anyone can provide me the original author's contact information,
I'd be happy to contact him and ask permission. I'll be traveling for
a few days, so I may not be able to respond immediately.

Regards
Stéfan

[j...@rybarski.com]

His contact info is all here: http://www.optics.rochester.edu/workgroups/fienup/Professor.htm