Legacy ImageMagick Discussions Archive

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

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).

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.

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

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

Legacy ImageMagick Discussions Archive

subimage search with fourier (cross-correlate)

subimage search with fourier (cross-correlate)

Re: subimage search with fourier (cross-correlate)

Re: subimage search with fourier (cross-correlate)

Re: subimage search with fourier (cross-correlate)

Re: subimage search with fourier (cross-correlate)