Shifting signal smaller than discrete step

Question

I have a image that I need to shift with less than a pixel.

My plan was to do a Fourier transform and multiply the signal with $e^{-aiu-biv}$ where $a, b$ are the shifts in x and y direction. This might make sense in theory but in practice I don't really know how to represent $e^{-aiu-biv}$.

I am using numpy to do a 2d FFT of the image which, ofcourse, is represented as a matrix of complex values. From this point of I'm kinda lost, how do I multiply this with $e^{-aiu-biv}$?

It seems like fundamentally something is wrong as I need to temporarily represent the image in a higher resolution, shift is slightly and then collapse it back to the original resolution.

Answer 1

I don't do much image processing but maybe the simpler 1D case will help:

A delay in the time domain is a phase shift in the frequency domain, this notion can be used to shift your FFT in the frequency domain by a rotation much smaller than a sample

$$x(n-n_o) = W_N^{kn_o}X(k)$$

$$W_N^{kn_o} = e^{\frac{-j 2 \pi k n_o}{N}}$$

You need to apply this principle row wise and column wise. I tried giving it a go by building a 2D matrix of the x y shift and then applying it to the image. For integer shift this works, when you get into fractional shift (0-.99) for $n_o$ it gets weird.

Non-fractional shift of a "cat eating fancy ice cream" to prove that it does what I think it does:

Matlab code:

close all 
clear all

%load image
I = imread('cat_eating_fancy_ice_cream.jpg');


I = im2double(I);

%make phase shift matrix for frequency domain shifting
sz = size(I)
y = e.^((-j*2*pi*[0:sz(1)-1]*100)/sz(1)).';
x = e.^((-j*2*pi*[0:sz(2)-1]*200)/sz(2));
shift = y*x;

%convert image to grayscale for easier manipulation
pF1 =(fft2(rgb2gray(I)));

%phase shift frequency domain info
pF = pF1.*shift;

%plots
figure
subplot(121)
imshow(rgb2gray(I))
subplot(122)
imshow(ifft2(pF))

Answer 2

The following Matlab line shows a 1D example of a fractional delay, implemented via DFT/FFT multiplication instead of a time-domain approach. Accuracy should be considered, noticeable ringing occurs.

You can extend it to 2D easily.

N = 64;                      % signal length
d = 0.5;                     % fractional shift

x = sin(2*pi*0.0323*[0:N-1]);  % signal
y = real( ifft( fftshift( exp(-j*(2*pi/N)*[-N/2:N/2-1]*d)).*fft(x,N) , N));

figure,stem(x,'g');
hold on
stem(y,'r+')
title('original x[n] and shifted y[n]');
legend('x[n]','y[n]');