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?".
Post Reply
HugoRune
Posts: 90
Joined: 2009-03-11T02:45:12-07:00
Authentication code: 8675309

subimage search with fourier (cross-correlate)

Post by HugoRune »

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
User avatar
magick
Site Admin
Posts: 11064
Joined: 2003-05-31T11:32:55-07:00

Re: subimage search with fourier (cross-correlate)

Post by magick »

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).
HugoRune
Posts: 90
Joined: 2009-03-11T02:45:12-07:00
Authentication code: 8675309

Re: subimage search with fourier (cross-correlate)

Post by HugoRune »

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.
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: subimage search with fourier (cross-correlate)

Post by fmw42 »

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
HugoRune
Posts: 90
Joined: 2009-03-11T02:45:12-07:00
Authentication code: 8675309

Re: subimage search with fourier (cross-correlate)

Post by HugoRune »

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
Post Reply