{"id":1232,"date":"2012-09-13T17:00:20","date_gmt":"2012-09-13T17:00:20","guid":{"rendered":"https:\/\/cml-a.com\/content\/?p=1232"},"modified":"2012-09-13T17:00:20","modified_gmt":"2012-09-13T17:00:20","slug":"image-shift-using-fft","status":"publish","type":"post","link":"https:\/\/cml-a.com\/content\/2012\/09\/13\/image-shift-using-fft\/","title":{"rendered":"Image Shift using FFT"},"content":{"rendered":"

This is a tool for estimating the amount of shift (displacement) between two images using FFT (Fast Fourier Transform). The images can be of different sizes. This method is faster than enumerating all the possible (x,y) shifts and selecting the right one, especially for large images. To perform the transforms it uses the\u00a0fftw<\/a>\u00a0library.<\/p>\n

More specifically it uses the 2D convolution function between the images. The steps for this are:
\n1. take the Fourier coefficients of the first image
\n2. take the same the second image,
\n3. find the element-wise product of the two results,
\n4. find the inverse Fourier transform of the above.<\/p>\n

It shows the resulting image, with scaled colour channels so the darkest is black and the lightest is white. The light areas indicate likely amounts of shift. For example, a light area at co-ordinate (5, 6) means the second image was probably shifted 5 pixels across, 6 units down from the first.<\/p>\n

As an example of using it, consider cropping an image so that the resulting image is 47 units across and 30 units down.<\/p>\n

<\/p>\n

Point the program toward the two image files and hit 'Estimate'.<\/p>\n

<\/p>\n

The dialog will (quickly) show a visual result of the convolution, and the estimated shift. The shift matches with\u00a0where the image was cropped. The units are the position of the first image, in pixels, relative to the second one.<\/p>\n

A brute-force implementation of the same thing is very doable but takes around 30 seconds on this sample, so it's a pretty significant speedup!<\/p>\n

<\/p>\n


\nDownload binary (Windows .exe) + sample images<\/a><\/p>\n

The source code is compiled using Visual Studio 2008. There are three project files. ConvolveShift is the main executable, a Windows Forms program in C#. Native is a C++ DLL that does most of the real work. NativeDriver is a non-graphical program for testing Native.<\/p>\n

Download Source<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

This is a tool for estimating the amount of shift (displacement) between two images using FFT (Fast Fourier Transform). The images can be of different sizes. This method is faster than enumerating all the possible (x,y) shifts and selecting the right one, especially for large images. To perform the transforms it uses the\u00a0fftw\u00a0library. More specifically […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[84,178],"class_list":["post-1232","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-imaging","tag-software-development-project"],"_links":{"self":[{"href":"https:\/\/cml-a.com\/content\/wp-json\/wp\/v2\/posts\/1232","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cml-a.com\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/cml-a.com\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/cml-a.com\/content\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cml-a.com\/content\/wp-json\/wp\/v2\/comments?post=1232"}],"version-history":[{"count":0,"href":"https:\/\/cml-a.com\/content\/wp-json\/wp\/v2\/posts\/1232\/revisions"}],"wp:attachment":[{"href":"https:\/\/cml-a.com\/content\/wp-json\/wp\/v2\/media?parent=1232"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/cml-a.com\/content\/wp-json\/wp\/v2\/categories?post=1232"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/cml-a.com\/content\/wp-json\/wp\/v2\/tags?post=1232"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}