subimage search with fourier (cross-correlate)

Questions and postings pertaining to the usage of ImageMagick regardless of the interface. This includes the command-line utilities, as well as the C and C++ APIs. Usage questions are like "How do I use ImageMagick to create drop shadows?".

subimage search with fourier (cross-correlate)

Postby HugoRune » 2011-03-19T07:00:20+00:00

I am trying to figure out how to do subimage search with the fast fourier transform.

I managed to compile imagemagick with HDRI and fft support.

I tried various commands adapted from
http://www.imagemagick.org/Usage/fourie ... /#multiply and http://www.fmwconcepts.com/imagemagick/ ... /index.php
without success.

The latest attempt was
convert \
testsearch.png -rotate 180 ( +clone +fft ) \
( testsrc.png +fft ) +matte \
( -clone 0 -scale 1x1 ) -delete 0 \
\
( -clone 0-4 -fx "( u[0]*u[2] - u[1]*u[3] ) / u[4].p{0,0}" ) \
( -clone 0-4 -fx "( u[0]*u[3] + u[1]*u[2] ) / u[4].p{0,0}" ) \
-delete 0-4 +ift test.png

--> output is 252x252 almost black picture, contrast-stretch reveals some peaks


I am having trouble understanding the whole concept.
Do the pictures have to be scaled to the same size?
Do I have to pad them to be square?
Is the rotation in the correct place to achive f(-x,-y)?
I am pretty sure that I do not need to -roll the search image to move the origin, and that I do not need normalisation either?

My test images:
Main Image
Image

Search image
Image

result after -contrast-stretch 0:
Image

I expected one strong peak, I am not sure how to interpret this. The dimensions are off too. Do I need to switch the images?


Resources:
http://www.imagemagick.org/Usage/fourie ... /#multiply
http://www.imagemagick.org/Usage/compare/#sub-image
http://en.wikipedia.org/wiki/Phase_correlation
http://en.wikipedia.org/wiki/Cross-correlation
http://www.imagemagick.org/Usage/fourier/#advanced
http://www.fmwconcepts.com/imagemagick/ ... /index.php
http://www.fmwconcepts.com/imagemagick/ ... mcrosscorr
HugoRune
 
Posts: 90
Joined: 2009-03-11T02:45:12+00:00

Re: subimage search with fourier (cross-correlate)

Postby magick » 2011-03-19T08:27:56+00:00

Fred will most likely comment on the Fourier method of subimage search. In the mean-time have you looked at -subimage-search option of the compare command?

    compare -metric ncc -subimage-search testsrcl.png testsearch.png result.png
    1 @ 84,46
A match was found @ (84,46).
User avatar
magick
Site Admin
 
Posts: 9703
Joined: 2003-05-31T11:32:55+00:00

Re: subimage search with fourier (cross-correlate)

Postby HugoRune » 2011-03-19T09:17:10+00:00

I did try the compare -subimage-search, but it seems a bit too slow at these sizes.
Non-hdri imagemagick takes 25 minutes for the test-images, using nearly 100% of both cpu cores.

I thought about ways to speed that up, by searching only part of the subimage fist, or first searching in a scaled-down image, but I guess nothing I could try would be faster than the FFT.
HugoRune
 
Posts: 90
Joined: 2009-03-11T02:45:12+00:00

Re: subimage search with fourier (cross-correlate)

Postby fmw42 » 2011-03-19T10:36:21+00:00

For FFT you can use my script normcrosscorr. See below. The images must be at the same scale and no rotational differences. see examples at http://www.fmwconcepts.com/imagemagick/ ... mcrosscorr
User avatar
fmw42
 
Posts: 15025
Joined: 2007-07-02T17:14:51+00:00
Location: Sunnyvale, California, USA

Re: subimage search with fourier (cross-correlate)

Postby HugoRune » 2011-03-19T12:18:17+00:00

Thanks. I have been using that script in trying to get a working command line, but so far without success.
I am not well versed in bash code.
Since I am on windows, I have not actually executed it; my main goal currently is to get some understanding of what I am doing.

As far as I can tell, I do not need normalisation just yet, so I have been trying to get a standard un-normalized cross-correlation going.

from this piece of code:
Code: Select all
crossCorr()
# function crossCorr to compute IFT of complex product of (A*)x(B),
# where A* is complex conjugate
# A*=a1-ia2; B=b1+ib2
# (A*)x(B)=(a1xb1+a2*b2) + i(a1xb2-a2xb1)   
{
   img1=$1
   img2=$2
   # note both images contain 2 frames
   convert $img1 $img2 \
      \( -clone 0 -clone 2 -compose multiply -composite \) \
      \( -clone 1 -clone 3 -compose multiply -composite \) \
      \( -clone 4 -clone 5 -compose plus -composite \) \
      \( -clone 0 -clone 3 -compose multiply -composite \) \
      \( -clone 1 -clone 2 -compose multiply -composite \) \
      \( -clone 7 -clone 8 +swap -compose minus -composite \) \
      -delete 0-5,7,8 +ift $tmp0
   }


I have tried this command line, as well as several permutations of it:
Code: Select all
convert testsearch.png -rotate 180 +fft  ( testsrc.png  +fft  ) ^
( -clone 0 -clone 2 -compose multiply -composite ) ^
( -clone 1 -clone 3 -compose multiply -composite ) ^
( -clone 4 -clone 5 -compose plus -composite ) ^
( -clone 0 -clone 3 -compose multiply -composite ) ^
( -clone 1 -clone 2 -compose multiply -composite ) ^
( -clone 7 -clone 8 +swap -compose minus -composite ) ^
-delete 0-5,7,8 +ift ^
-contrast-stretch 0 ^
test.png

but without success.

However, upon rereading I noticed a part about padding I missed. With the search image padded to the same size, the results are a little bit closer to what i expected. Still not quite there though
Image
HugoRune
 
Posts: 90
Joined: 2009-03-11T02:45:12+00:00


Return to Users

Who is online

Users browsing this forum: Baidu [Spider], Bing [Bot], BubbleBobble, Google Adsense [Bot], Yahoo [Bot] and 30 guests