Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
sub-pixel shifting of a matrix

Subject: sub-pixel shifting of a matrix

From: Shalin Mehta

Date: 17 Sep, 2009 08:34:03

Message: 1 of 15

Hello world,

 I have data defined over a grid, e.g.
[xx yy]=meshgrid(-1:0.1:1); %each pixel represents distance of 0.1
data=xx.^2+yy.^2 ;

I need to translate this data by sub-pixel distances which will inevitably involve interpolation. I can live with linear interpolation as the data is sampled quite finely. I am using imtransform to achieve this. The shifted-data need to be obtained only over the original grid. I want extrapolated locations to be zero.

xshift=0.235; yshift=-0.95; %Since shift is finer than sampling, sub-pixel shifting is required.
xdata=[1 wt];
ydata=[1 ht];
T=maketform('affine',[1 0 0; 0 1 0; xshift yshift 1]);
shifteddata=imtransform(data,T,'bilinear','XData',xdata,'YData',ydata);

Results are satisfactory but slow as this shifting happens in the inner-most loop.
Can anyone suggest a method that involves direct indexing and hence would be faster? Any neat algorithm published in the literature for sub-pixel translation?

best
Shalin

Subject: sub-pixel shifting of a matrix

From: Shalin Mehta

Date: 17 Sep, 2009 09:33:02

Message: 2 of 15

Just found a useful solution: Use interp2 with '*linear' option. Works factor of 2.5 faster than imtransform. Any other ideas?

best
shalin
"Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8ss9r$jhf$1@fred.mathworks.com>...
> Hello world,
>
> I have data defined over a grid, e.g.
> [xx yy]=meshgrid(-1:0.1:1); %each pixel represents distance of 0.1
> data=xx.^2+yy.^2 ;
>
> I need to translate this data by sub-pixel distances which will inevitably involve interpolation. I can live with linear interpolation as the data is sampled quite finely. I am using imtransform to achieve this. The shifted-data need to be obtained only over the original grid. I want extrapolated locations to be zero.
>
> xshift=0.235; yshift=-0.95; %Since shift is finer than sampling, sub-pixel shifting is required.
> xdata=[1 wt];
> ydata=[1 ht];
> T=maketform('affine',[1 0 0; 0 1 0; xshift yshift 1]);
> shifteddata=imtransform(data,T,'bilinear','XData',xdata,'YData',ydata);
>
> Results are satisfactory but slow as this shifting happens in the inner-most loop.
> Can anyone suggest a method that involves direct indexing and hence would be faster? Any neat algorithm published in the literature for sub-pixel translation?
>
> best
> Shalin

Subject: sub-pixel shifting of a matrix

From: Dumebi Okwechime

Date: 30 Oct, 2009 10:07:01

Message: 3 of 15

Hi Shalin,

Was wondering what your input parameters were when using interp2.
Thanks

Dumebi

"Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8svoe$rkb$1@fred.mathworks.com>...
> Just found a useful solution: Use interp2 with '*linear' option. Works factor of 2.5 faster than imtransform. Any other ideas?
>
> best
> shalin
> "Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8ss9r$jhf$1@fred.mathworks.com>...
> > Hello world,
> >
> > I have data defined over a grid, e.g.
> > [xx yy]=meshgrid(-1:0.1:1); %each pixel represents distance of 0.1
> > data=xx.^2+yy.^2 ;
> >
> > I need to translate this data by sub-pixel distances which will inevitably involve interpolation. I can live with linear interpolation as the data is sampled quite finely. I am using imtransform to achieve this. The shifted-data need to be obtained only over the original grid. I want extrapolated locations to be zero.
> >
> > xshift=0.235; yshift=-0.95; %Since shift is finer than sampling, sub-pixel shifting is required.
> > xdata=[1 wt];
> > ydata=[1 ht];
> > T=maketform('affine',[1 0 0; 0 1 0; xshift yshift 1]);
> > shifteddata=imtransform(data,T,'bilinear','XData',xdata,'YData',ydata);
> >
> > Results are satisfactory but slow as this shifting happens in the inner-most loop.
> > Can anyone suggest a method that involves direct indexing and hence would be faster? Any neat algorithm published in the literature for sub-pixel translation?
> >
> > best
> > Shalin

Subject: sub-pixel shifting of a matrix

From: Shalin Mehta

Date: 24 Feb, 2010 11:58:07

Message: 4 of 15

Hi Dumebi,
I did not receive a notification of your reply - so didn't get back to you on this.
interp2's syntax is as follows:
http://www.mathworks.com/access/helpdesk/help/techdoc/ref/interp2.html

out=interp2(xx,yy,in,xxi,yyi).

You could do the following to shift a matrix by 0.5 pixels in X and 0.75 pixels in Y.
[M N]=size(in); %Assuming square matrix.
[xx yy]=meshgrid(1:N,1:M); %xx,yy are both outputs of meshgrid (so called plaid matrices).
out=interp2(xx,yy,in,xx+0.5,yy+0.75);

best
Shalin

"Dumebi Okwechime" <dumebi833@hotmail.com> wrote in message <hceds5$fa0$1@fred.mathworks.com>...
> Hi Shalin,
>
> Was wondering what your input parameters were when using interp2.
> Thanks
>
> Dumebi
>
> "Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8svoe$rkb$1@fred.mathworks.com>...
> > Just found a useful solution: Use interp2 with '*linear' option. Works factor of 2.5 faster than imtransform. Any other ideas?
> >
> > best
> > shalin
> > "Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8ss9r$jhf$1@fred.mathworks.com>...
> > > Hello world,
> > >
> > > I have data defined over a grid, e.g.
> > > [xx yy]=meshgrid(-1:0.1:1); %each pixel represents distance of 0.1
> > > data=xx.^2+yy.^2 ;
> > >
> > > I need to translate this data by sub-pixel distances which will inevitably involve interpolation. I can live with linear interpolation as the data is sampled quite finely. I am using imtransform to achieve this. The shifted-data need to be obtained only over the original grid. I want extrapolated locations to be zero.
> > >
> > > xshift=0.235; yshift=-0.95; %Since shift is finer than sampling, sub-pixel shifting is required.
> > > xdata=[1 wt];
> > > ydata=[1 ht];
> > > T=maketform('affine',[1 0 0; 0 1 0; xshift yshift 1]);
> > > shifteddata=imtransform(data,T,'bilinear','XData',xdata,'YData',ydata);
> > >
> > > Results are satisfactory but slow as this shifting happens in the inner-most loop.
> > > Can anyone suggest a method that involves direct indexing and hence would be faster? Any neat algorithm published in the literature for sub-pixel translation?
> > >
> > > best
> > > Shalin

Subject: sub-pixel shifting of a matrix

From: Matt J

Date: 24 Feb, 2010 15:12:22

Message: 5 of 15

"Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8svoe$rkb$1@fred.mathworks.com>...
> Just found a useful solution: Use interp2 with '*linear' option. Works factor of 2.5 faster than imtransform. Any other ideas?
=================

Yes, interp2 will still be quite slow because of all the different functionality it has to support, for example, interpolation on non-uniform grids. It is much faster to express the interpolation as a separable convolution and use
conv2().

Namely if your shift in x and y are 0<sx<1 and 0<sy<1 respectively, then you can do

Image=conv2(Image,[sx, 1-sx],'same');
Result=conv2(Image,[sy, 1-sy],'same');

Subject: sub-pixel shifting of a matrix

From: Rajesh

Date: 25 Feb, 2010 06:02:05

Message: 6 of 15

interp2 works well alright (thanks shalin mehta) but it fills the shifted region of the matrix with NaNs. may be it can be padded by copying the adjacent columns or rows, as the case may be, using 'padarray' function. but again this loop takes longer time. especially when you are dealing with series of matrices/images to be shifted in a loop as Mat also points out.

@Mat
does conv2 work for fractions >1?? but even this, i guess, leaves the shifted column (for shift in x direction) in shambles.

Wish we could have something like 'circshift' handle fractions along with integers. :(

I need to shift an image by say 6.3 pixels in x direction in such a way that as if only the object in the image has moved and the background is retained as it is. and i need to implement it in a loop for several images with varying values of shift in x direction. so needless to say the faster the better as the original post has asked for.

thanks.

Subject: sub-pixel shifting of a matrix

From: Matt J

Date: 25 Feb, 2010 06:54:05

Message: 7 of 15

"Rajesh " <rv_acharya@rediffmail.com> wrote in message <hm53ot$ig8$1@fred.mathworks.com>...
> interp2 works well alright (thanks shalin mehta) but it fills the shifted region of the matrix with NaNs.
=================

You can extrapolate with zeros or any other desired value using the EXTRAPVAL option.

>may be it can be padded by copying the adjacent columns or rows, as the case may be, using 'padarray' function.
====================

That's an option if you have the image processing toolbox. If you don't have it, you can create a convolution matrix modified for replicate extrapolation using my interpMatrix tool:

http://www.mathworks.com/matlabcentral/fileexchange/26292-regular-control-point-interpolation-matrix-with-boundary-conditions


>
> @Mat
> does conv2 work for fractions >1?? but even this, i guess, leaves the shifted column (for shift in x direction) in shambles.

I don't know what you mean by leaving the column in shambles.

For shifts >1, you could just convolve using a zero-padded version of the convolution kernel. However, it would probably be more efficient to do an integer shift of the image first, which just requires that you reorder the image data, and do a fractional shift using the method I've described. circshift() will work for the integer shift, but I've found circshift to be slower than as compared to just reordering the data manually, as in

Result=zeros(size(Image));
Result(1:end+1-k,1:end+1-j)=Image(k:end,j:end);

Incidentally, I've just noticed that interp2 has a "*METHOD" option allowing you to tell it that the samples are uniformly spaced, for more optimized execution. This probably means that interp2 will implement the interpolation as a separable convolution for you under the hood.


> I need to shift an image by say 6.3 pixels in x direction in such a way that as if only the object in the image has moved and the background is retained as it is.
==============

If the object is completely surrounded by background values of zero, I don't see what's challenging about that. What I've outlined above will work.

Subject: sub-pixel shifting of a matrix

From: Matt J

Date: 25 Feb, 2010 15:25:21

Message: 8 of 15

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hm56qd$t3c$1@fred.mathworks.com>...

> Incidentally, I've just noticed that interp2 has a "*METHOD" option allowing you to tell it that the samples are uniformly spaced, for more optimized execution. This probably means that interp2 will implement the interpolation as a separable convolution for you under the hood.
================

Come to think of it, that can't (always) be true. The interpolation only boils down to a convolution if the sample spacing is 1 pixel. So the question is whether interp2 is smart enough to check for this special case.

 

Subject: sub-pixel shifting of a matrix

From: Rajesh

Date: 26 Feb, 2010 10:24:05

Message: 9 of 15

> You can extrapolate with zeros or any other desired value using the EXTRAPVAL option.
>

I already tried that but the background in the image has a certain mean and sd as would be the case for an image. moreover replacing it with a certain constant requires a knowledge of the actual pixl value of the background which will have to be obtained from the image itself by picking a certain area or certain pixel of the background in the image but that, i guess, would take further time (or no?) since i am handling mutliple images in a loop while translatng them.

Also, replacing them with a constant might give artefacts in futue reconstructions (rings in CT images)
>
> Result=zeros(size(Image));
> Result(1:end+1-k,1:end+1-j)=Image(k:end,j:end);

Thanks for this as well.

> If the object is completely surrounded by background values of zero, I don't see what's challenging about that. What I've outlined above will work.

thanks (appologies if this amounts to hijacking the original thrd)

Subject: sub-pixel shifting of a matrix

From: Paulus Potter

Date: 6 Feb, 2013 19:26:07

Message: 10 of 15

It should be:

Image=conv2(Image,[sx, 1-sx],'same');
Result=conv2(Image,[sy; 1-sy],'same');

=> the semicolon for y direction is necessary. This should give the same results as interp2, with border row and column not being NaN or zero though.

"Matt J" wrote in message <hm3fkm$c2u$1@fred.mathworks.com>...
> "Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8svoe$rkb$1@fred.mathworks.com>...
> > Just found a useful solution: Use interp2 with '*linear' option. Works factor of 2.5 faster than imtransform. Any other ideas?
> =================
>
> Yes, interp2 will still be quite slow because of all the different functionality it has to support, for example, interpolation on non-uniform grids. It is much faster to express the interpolation as a separable convolution and use
> conv2().
>
> Namely if your shift in x and y are 0<sx<1 and 0<sy<1 respectively, then you can do
>
> Image=conv2(Image,[sx, 1-sx],'same');
> Result=conv2(Image,[sy, 1-sy],'same');

Subject: sub-pixel shifting of a matrix

From: Bruno Luong

Date: 6 Feb, 2013 19:47:09

Message: 11 of 15

"Paulus Potter" wrote in message <keuaof$amu$1@newscl01ah.mathworks.com>...
> It should be:
>
> Image=conv2(Image,[sx, 1-sx],'same');
> Result=conv2(Image,[sy; 1-sy],'same');
>

This is about twice faster
Result=conv2(Image,[sy; 1-sy]*[sx, 1-sx],'same');

% Bruno

Subject: sub-pixel shifting of a matrix

From: Matt J

Date: 6 Feb, 2013 22:33:09

Message: 12 of 15

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <keubvt$fki$1@newscl01ah.mathworks.com>...
> "Paulus Potter" wrote in message <keuaof$amu$1@newscl01ah.mathworks.com>...
> > It should be:
> >
> > Image=conv2(Image,[sx, 1-sx],'same');
> > Result=conv2(Image,[sy; 1-sy],'same');
> >
>
> This is about twice faster
> Result=conv2(Image,[sy; 1-sy]*[sx, 1-sx],'same');

Maybe, but only because there are some funny sub-optimal things happening inside conv2 implementation-wise, and because the interpolation kernel here happens to be small. There's no way the 3rd version below should be the slowest.

Image=rand(2000);
kx=rand(1,10);
ky=rand(10,1);

tic;
Image=conv2(Image,kx,'same');
Result=conv2(Image,[sy; 1-sy],'same');
toc
%Elapsed time is 0.045940 seconds.


tic;
Result=conv2(Image,ky*kx,'same');
toc
%Elapsed time is 0.090292 seconds.


tic;
Result=conv2(kx , ky, Image,'same');
toc
 %Elapsed time is 0.162708 seconds.

Subject: sub-pixel shifting of a matrix

From: Bruno Luong

Date: 6 Feb, 2013 22:49:08

Message: 13 of 15

"Matt J" wrote in message <keuln5$onb$1@newscl01ah.mathworks.com>...

>
> Maybe, but only because there are some funny sub-optimal things happening inside conv2 implementation-wise, and because the interpolation kernel here happens to be small. There's no way the 3rd version below should be the slowest.

Of course. The reason is obvious: 2+2 = 2*2, but 10+10 << 10*10.

Bilinear interpolation - as we discussed here - requires kernel of 2. So there is no need to decompose the convolution in tensorial at the price of memory parsing twice.

Bruno

Subject: sub-pixel shifting of a matrix

From: Matt J

Date: 7 Feb, 2013 16:49:08

Message: 14 of 15

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <keuml4$rtj$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <keuln5$onb$1@newscl01ah.mathworks.com>...
>
> >
> > Maybe, but only because there are some funny sub-optimal things happening inside conv2 implementation-wise, and because the interpolation kernel here happens to be small. There's no way the 3rd version below should be the slowest.
>
> Of course. The reason is obvious: 2+2 = 2*2, but 10+10 << 10*10.
============

That doesn't explain why the 3rd version was the slowest. The 3rd version uses a 10+10 tensorial operation so since 10+10 << 10*10, you would expect the 3rd version to be faster (or comparable to) the others.

Subject: sub-pixel shifting of a matrix

From: Bruno Luong

Date: 7 Feb, 2013 17:23:08

Message: 15 of 15

"Matt J" wrote in message <kf0lu4$eph$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
>
> That doesn't explain why the 3rd version was the slowest. The 3rd version uses a 10+10 tensorial operation so since 10+10 << 10*10, you would expect the 3rd version to be faster (or comparable to) the others.

This is an independent question, and a little OT. But here is few elements of explanation:

I imagine on the implementation side, the first and second input arguments of CONV2 is not symmetric. There should be an outer loop and inner loop must be on 1st/2nd arguments (or the opposite). Also the sum is carried out on a direct/flipped memory arrangement of the arguments. That can make a huge difference espectially considering the computer cache system that is not symmetric in the memory reading.

The lesson here is that one should put the large array as first argument of conv/conv2, which is probably the marojity of the cases in practice.

Bruno

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us