how to figure out (calculate) the translation of 2 images

[username]

hi everybody,

i want to make a movie of thousands of single pictures, but the pictures are not aligned perfectly.
so i have to calculate the translation value to one reference picture.
theoretically i have to compute the power spectral density and the peak shows me the translation.
is there a way to align them with image magic?

salute

[fmw42]

see compare function

http://www.imagemagick.org/script/compare.php
http://www.imagemagick.org/Usage/compare/

and an example at viewtopic.php?f=1&t=14613&p=51076&hilit ... ric#p51076
but note that you need to add -subimage-search to the command line in more current IM versions. see http://www.imagemagick.org/script/comma ... age-search

Alternately, if you can do it with my script normcrosscorr at the link below, if you are on Linux/Mac or Windows with Cygwin

[whugemann]

You should consider using JImage, readily packed to Fiji, in order to do that. This program offers this feature as a ready-made extension. I have tested it a video project it an found it doing a very effective job.

Fiji knows picture stacks as input entitites. The funtionality is called "registration" and you find it at PlugIns > Registration > Linear Stack allignment with SIFT.

I have only tested it with about 100 video frames of 720x576 pixel. I had the impression that the funtionality is limited by memory requirements, so you might have to apply it to sequences of about 100 frames at a time.

There are also a lot of deshake plugins for video prcessing programs. Some of them do an acceptable job. For VirtualDub (Windows freeware) there is for instance Deshaker (http://www.guthspot.se/video/deshaker.htm) . Anternatively, you can use Magix17 with Mercalli2-Plugin, both commercially sold.

[username]

thank you for giving hints and the GREAT script collection.
yes, i'm on linux and although i'm not very familiar with bash scripting i try to extend the normcrosscorr.sh to a deshaker.sh.
i add a for loop over all files and calculate an average shift.
after that crop it with something like

Code: Select all

convert img.jpg -crop (width+border)x(height+border)+xoffset+yoffset\! -background black -flatten target.jpg

salute

[username]

et voilà. this is the deshaker or image stabilizer.

Code: Select all

#!/bin/bash
#
# Developed by username 8/21/2011, based on NORMCROSSCORR by 
# Fred Weinhaus (http://www.fmwconcepts.com/imagemagick/index.html)
#
# USAGE: ./deshaker.sh referencefile.jpg geometry_1 geometry_2
# USAGE: ./deshaker.sh [-h or -help]
#
# PARAMETER: 
# referencefile.jpg: image to which all other images are aligned.
# the reference image must be at the same location as the rest of the collection.
#
# geometry_1: downsize all images temporarily to reduce computation time.
# the size depends on the maximum shift in the image collection.
# because of lens distortion crop the image somewhere in the middle
# around some salient objects.
#
# geometry_2: smaller part of reference image to which the correlation is computed.
# the geometry_2 is RELATIVE to geometry_1. the size and shift 
# depends on where and how large the salient objects in your
# reference image are.
#
# EXAMPLE: ./deshaker.sh refimg.jpg 512x256+800+320 256x128+128+32
# 
###
#
# NAME: DESHAKER 
# 
# PURPOSE: Aligns shifted images
#
# DESCRIPTION: DESHAKER imitates an image stabilizator
# by computing the amount of translation between a
# reference image and the rest of the images in the folder and cropping 
# the images accordingly.
# To save computation time the images are cropped temporarily by the
# first geometry parameter.
# To make results stable, choose salient points in cropped images 
#
# WARNING: Due to the way ImageMagick normalizes images internally to a full 
# dynamic range of 0 to 1 before doing any processing such as image-to-image 
# multiplication, the correlation surface will not generally have a perfect 
# match score of +1, but will be image dependent and smaller than 1. 
# Nevertheless, it does seem to find the correct best match location.
# 
# REQUIREMENTS: IM version 6.5.4-7 or higher, but compiled with HDRI enabled 
# in any quantum level of Q8, Q16 or Q32. Also requires the FFTW delegate 
# library.
#
# REQUIREMENTS: IM version 6.5.4-7 or higher, but compiled with HDRI enabled.
# 
# CAVEAT: No guarantee that this script will work on all platforms, 
# nor that trapping of inconsistent parameters is complete and 
# foolproof. Use At Your Own Risk. 
# 
######
#

# set directory for temporary files
dir="."    # suggestions are dir="." or dir="/tmp"

# set up functions to report Usage and Usage with Description
PROGNAME=`type $0 | awk '{print $3}'`  # search for executable on path
PROGDIR=`dirname $PROGNAME`            # extract directory of program
PROGNAME=`basename $PROGNAME`          # base name of program
usage1() 
	{
	echo >&2 ""
	echo >&2 "$PROGNAME:" "$@"
	sed >&2 -n '/^###/q;  /^#/!q;  s/^#//;  s/^ //;  4,$p' "$PROGDIR/$PROGNAME"
	}
usage2() 
	{
	echo >&2 ""
	echo >&2 "$PROGNAME:" "$@"
	sed >&2 -n '/^######/q;  /^#/!q;  s/^#*//;  s/^ //;  4,$p' "$PROGDIR/$PROGNAME"
	}


# function to report error messages
errMsg()
	{
	echo ""
	echo $1
	echo ""
	usage1
	exit 1
	}

# 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)
crossCorr()
	{
	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
	}

# function to test for minus at start of value of second part of option 1 or 2
checkMinus()
	{
	test=`echo "$1" | grep -c '^-.*$'`   # returns 1 if match; 0 otherwise
    [ $test -eq 1 ] && errMsg "$errorMsg"
	}

# test for correct number of arguments and get values
if [ $# -eq 0 ]
	then
	# help information
   echo ""
   usage1
   exit 0
elif [ $# -gt 3 ]
	then
	errMsg "--- TOO MANY ARGUMENTS WERE PROVIDED ---"
else
	while [ $# -gt 0 ]
		do
			# get parameter values
			case "$1" in
		  -h|-help)    # help information
					   echo ""
					   usage2
					   exit 0
					   ;;
				 -)    # STDIN and end of arguments
					   break
					   ;;
				-*)    # any other - argument
					   errMsg "--- UNKNOWN OPTION ---"
					   ;;
		     	 *)    # end of arguments
					   break
					   ;;
			esac
			shift   # next option
	done
	
fi

# test params
[ ! -f $1 ] && errMsg "--- Image $1 not found ---"

geo_1=`echo $2 | egrep "^[0-9]+x[0-9]+\+[0-9]+\+[0-9]+$"`
[ "$geo_1" = "" ] && errMsg "--- Incorrect geometry_1 parameter ---"

geo_2=`echo $3 | egrep "^[0-9]+x[0-9]+\+[0-9]+\+[0-9]+$"`
[ "$geo_2" = "" ] && errMsg "--- Incorrect geometry_2 parameter ---"

# extract offset of the smaller image
geometryoffset=`echo $3 | sed 's/^[0-9]\+x[0-9]\++//'`
refOffsetX=`echo $geometryoffset | egrep -o "^[0-9]+"`
refOffsetY=`echo $geometryoffset | egrep -o "[0-9]+$"`
#echo "refOffsetX: $refOffsetX"
#echo "refOffsetY: $refOffsetY"


# extract directory, filename and file extension of the reference image
IMAGEDIR=`dirname $1`
echo "imagedir: $IMAGEDIR"
declare -a files
FILENAME=`basename $1`
echo "reference filename: $FILENAME"
EXTENSION=${FILENAME##*.}
echo "extension: $EXTENSION"
#`echo $1 | grep -o "\.[a-zA-Z]\{3,4\}"`
cd ${IMAGEDIR}
# put all images into an array
files=(`ls -v *.$EXTENSION`)
#echo "${IMAGEDIR}/*$EXTENSION"
#echo "files: ${files[@]}"
declare -a xShifts
declare -a yShifts
declare -i index
declare -i minXShift
declare -i maxXShift
declare -i minYShift
declare -i maxYShift
index=0
minXShift=0
maxXShift=0
minYShift=0
maxYShift=0
subimage="subimg"
reference="ref"

# crop ref image to reduce computation time
convert $FILENAME -crop $2 $subimage
# crop small image
convert $subimage -crop $3 $reference


# loop over all jpg files
for imgfile in ${files[@]} ; do
echo "Calculating translation for: $imgfile"       

# crop image to reduce computation time
convert $imgfile -crop $2 $subimage

# setup temporary images
tmpA1="$dir/normcrosscorr_1_$$.mpc"
tmpB1="$dir/normcrosscorr_1_$$.cache"
tmpA2="$dir/normcrosscorr_2_$$.mpc"
tmpB2="$dir/normcrosscorr_2_$$.cache"
tmpS="$dir/normcrosscorr_S.pfm"
tmpU="$dir/normcrosscorr_W.pfm"
tmpL="$dir/normcrosscorr_L.pfm"
tmpL2="$dir/normcrosscorr_L2.pfm"
tmp0="$dir/normcrosscorr_0.pfm"
tmpP="$dir/normcrosscorr_P.pfm"
trap "rm -f $tmpA1 $tmpB1 $tmpA2 $tmpB2 $tmpS $tmpU $tmpL $tmpL2 $tmp0 $tmpP; exit 0" 0
trap "rm -f $tmpA1 $tmpB1 $tmpA2 $tmpB2 $tmpS $tmpU $tmpL $tmpL2 $tmp0 $tmpP; exit 1" 1 2 3 15

# read the input image and filter image into the temp files and test validity.
convert -quiet -regard-warnings "$reference" -alpha off +repage -write "$tmpA1" -colorspace gray "$tmpS" ||
	errMsg "--- FILE $reference DOES NOT EXIST OR IS NOT AN ORDINARY FILE, NOT READABLE OR HAS ZERO SIZE  ---"

convert -quiet -regard-warnings "$subimage" -alpha off +repage -write "$tmpA2" -colorspace gray "$tmpL" ||
	errMsg "--- FILE $subimage DOES NOT EXIST OR IS NOT AN ORDINARY FILE, NOT READABLE OR HAS ZERO SIZE  ---"


# test for valid version of IM
im_version=`convert -list configure | \
	sed '/^LIB_VERSION_NUMBER /!d;  s//,/;  s/,/,0/g;  s/,0*\([0-9][0-9]\)/\1/g'`
[ "$im_version" -lt "06050407" ] && errMsg "--- REQUIRES IM VERSION 6.5.4-7 OR HIGHER ---"

# test for hdri enabled
hdri_on=`convert -list configure | grep "enable-hdri"`
[ "$hdri_on" = "" ] && errMsg "--- REQUIRES HDRI ENABLED IN IM COMPILE ---"

# get image dimensions to be sure that infile1 is smaller than infile2
ws=`identify -ping -format "%w" $tmpA1`
hs=`identify -ping -format "%h" $tmpA1`
wl=`identify -ping -format "%w" $tmpA2`
hl=`identify -ping -format "%h" $tmpA2`

[ $ws -gt $wl ] && errMsg "--- SECOND IMAGE MUST BE WIDER THAN FIRST IMAGE ---"
[ $hs -gt $hl ] && errMsg "--- SECOND IMAGE MUST BE TALLER THAN FIRST IMAGE ---"


: '
C = ((S-Ms) X L)/(sigmaS*sqrt(Nx(U X L^2) - (U X L)^2)
where
A X B = I(F(A*)F(B)] and A* is complex conjugate of A, F=FFT and I=IFT
L is large image.
S-Ms is the mean subtracted small image. 
U is a unit image (value=1) 
Both S-Ms and U are padded at right and bottom to size of L. 
'

# compute N=wsxhs = total pixels in small image
N=`convert xc: -format "%[fx:$ws*$hs]" info:`

# get mean and std of small image
mean=`convert $tmpS -format "%[mean]" info:`
std=`convert $tmpS -format "%[standard_deviation]" info:`
#echo "mean=$mean; std=$std"

# ncc has range -1 to +1, so need to scale that to range 0 to quantumrange
# thus we scale by dividing std by quantumrange and 
# note that negatives are clipped by PNG output.
if [ "$im_version" -ge "06050410" ]; then
	#HDRI was auto scaled by quantumrange
	# not sure why a perfect match is considerably less that quantumrange?
	std=`convert xc: -format "%[fx:$std/(quantumrange)]" info:`
	divide1="-evaluate divide 100%"
else
	#HDRI was unscaled by quantumrange
	# so need the extra factor of quantumrange?
	# not sure why a perfect match is considerably less that quantumrange?
	std=`convert xc: -format "%[fx:$std/(quantumrange*quantumrange)]" info:`
	divide1=""
fi
#echo "std=$std"


# get square of large image and take FFT
convert $tmpL $tmpL \
	-compose multiply -composite +fft $tmpL2

# take FFT of large image
convert $tmpL +fft $tmpL

# subtract mean from small image and pad and take FFT

convert $tmpS -evaluate subtract $mean \
	-background black -extent ${wl}x${hl} +fft $tmpS

# create identity U image (value=1) and pad and take FFT
convert -size ${ws}x${hs} xc:white $divide1 \
	-background black -extent ${wl}x${hl} +fft $tmpU

# create (S-Ms) X L
crossCorr $tmpS $tmpL
convert $tmp0 $tmpS

# create N(U X L^2)
crossCorr $tmpU $tmpL2
convert $tmp0 -evaluate multiply $N $tmpL2

#create (U X L)^2
crossCorr $tmpU $tmpL
convert $tmp0 $tmp0 -compose multiply -composite $tmpU
	
#evaluate normalize cross correlation image
convert $tmpS \
	\( $tmpL2 $tmpU +swap -compose minus -composite \
	-evaluate pow 0.5 -evaluate multiply $std \) \
	+swap -compose divide -composite $tmp0





: '
#old slow method 
echo "get match"
# convert to txt format
# skip to second line
# remove all non numeric characters
# sort in reverse order according to field 3 
# keep 1 result with highest value in field 3
# for that result get fields 1 and 2 for location
# convert space to + sign
match=`convert $tmp0 txt:- | tail -n +2 | tr -cs '0-9\012' ' ' | \
sort -n -r -k 3 | head -n 1 | cut -d\  -f 1-3`
echo ""
echo "Match Coords And Score: $match"
echo ""
# compute subsection
ulx=`echo $match | cut -d\  -f 1`
uly=`echo $match | cut -d\  -f 2`
subsection="${ws}x${hs}+$ulx+$uly"
echo "$subsection"
'


#echo "get match"
max=`convert $tmp0 -format "%[fx:maxima]" info:`
str=`convert $tmp0 -fx "u>=($max-quantumscale)?debug(u):0" null: 2>&1`
#echo "str: $str"
coords=`echo "$str" | sed -n 's/^.*\[\([0-9]*,[0-9]*\)\]\.red.*$/\1/p'`
echo ""
#echo "Match Coords: ($coords) And Score In Range 0 to 1: ($max)"
#echo ""

# compute subsection
ulx=`echo $coords | cut -d,  -f 1`
uly=`echo $coords | cut -d,  -f 2`
subsection="${ws}x${hs}+$ulx+$uly"
#echo "$subsection"



lrx=$(($ulx+$ws))
lry=$(($uly+$hs))
#echo "ulx=$ulx; uly=$uly; lrx=$lrx; lry=$lry"


let xShift=$ulx-$refOffsetX
let yShift=$uly-$refOffsetY
#echo "$xShift $yShift"
echo ""
echo ""
xShifts[$index]=$xShift
yShifts[$index]=$yShift
let index=$index+1

if [ $xShift -lt $minXShift ]; then
  minXShift=$xShift
fi

if [ $xShift -gt $maxXShift ]; then
  maxXShift=$xShift
fi

if [ $yShift -lt $minYShift ]; then
  minYShift=$yShift
fi

if [ $yShift -gt $maxYShift ]; then
  maxYShift=$yShift
fi


done  # loop over files


widthOld=`identify -ping -format "%w" $FILENAME`
heightOld=`identify -ping -format "%h" $FILENAME`

# geometry of target images
declare -i width 
let width=$widthOld+$maxXShift-$minXShift
declare -i height
let height=$heightOld+$maxYShift-$minYShift

echo "Geometry of source images: $widthOld x $heightOld"
echo "New geometry $width x $height"


index=0
rm $reference
rm $subimage

for imgfile in ${files[@]} ; do
echo "Cropping: $imgfile" 

let xShift=$[ ${xShifts[$index]} - $maxXShift ]*$[ 0 - 1 ]
let yShift=$[ ${yShifts[$index]} - $maxYShift ]*$[ 0 - 1 ]
echo "${width}x${height}-${xShift}-${yShift}"
convert $imgfile -crop "${width}x${height}-${xShift}-${yShift}"\! -background black -flatten "shifted_${imgfile}"

let index=$index+1
echo ""
done

exit 0

salute

[fmw42]

If you don't mind, please add my web site http://www.fmwconcepts.com/imagemagick/index.html to your header in addition to my name. So others can find it and my licensing policy.

Thanks.

Fred

[username]

done

[fmw42]

thank you