subimage search with fourier (cross-correlate)

[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


Search image


result after -contrast-stretch 0:


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

[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]

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.

[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]

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