http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037
MATLAB Central Newsreader  subpixel shifting of a matrix
Feed for thread: subpixel shifting of a matrix
enus
©19942015 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Thu, 17 Sep 2009 08:34:03 +0000
subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#680758
Shalin Mehta
Hello world,<br>
<br>
I have data defined over a grid, e.g. <br>
[xx yy]=meshgrid(1:0.1:1); %each pixel represents distance of 0.1<br>
data=xx.^2+yy.^2 ;<br>
<br>
I need to translate this data by subpixel 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 shifteddata need to be obtained only over the original grid. I want extrapolated locations to be zero.<br>
<br>
xshift=0.235; yshift=0.95; %Since shift is finer than sampling, subpixel shifting is required.<br>
xdata=[1 wt];<br>
ydata=[1 ht];<br>
T=maketform('affine',[1 0 0; 0 1 0; xshift yshift 1]);<br>
shifteddata=imtransform(data,T,'bilinear','XData',xdata,'YData',ydata);<br>
<br>
Results are satisfactory but slow as this shifting happens in the innermost loop. <br>
Can anyone suggest a method that involves direct indexing and hence would be faster? Any neat algorithm published in the literature for subpixel translation?<br>
<br>
best<br>
Shalin

Thu, 17 Sep 2009 09:33:02 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#680770
Shalin Mehta
Just found a useful solution: Use interp2 with '*linear' option. Works factor of 2.5 faster than imtransform. Any other ideas?<br>
<br>
best<br>
shalin<br>
"Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8ss9r$jhf$1@fred.mathworks.com>...<br>
> Hello world,<br>
> <br>
> I have data defined over a grid, e.g. <br>
> [xx yy]=meshgrid(1:0.1:1); %each pixel represents distance of 0.1<br>
> data=xx.^2+yy.^2 ;<br>
> <br>
> I need to translate this data by subpixel 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 shifteddata need to be obtained only over the original grid. I want extrapolated locations to be zero.<br>
> <br>
> xshift=0.235; yshift=0.95; %Since shift is finer than sampling, subpixel shifting is required.<br>
> xdata=[1 wt];<br>
> ydata=[1 ht];<br>
> T=maketform('affine',[1 0 0; 0 1 0; xshift yshift 1]);<br>
> shifteddata=imtransform(data,T,'bilinear','XData',xdata,'YData',ydata);<br>
> <br>
> Results are satisfactory but slow as this shifting happens in the innermost loop. <br>
> Can anyone suggest a method that involves direct indexing and hence would be faster? Any neat algorithm published in the literature for subpixel translation?<br>
> <br>
> best<br>
> Shalin

Fri, 30 Oct 2009 10:07:01 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#690916
Dumebi Okwechime
Hi Shalin, <br>
<br>
Was wondering what your input parameters were when using interp2. <br>
Thanks<br>
<br>
Dumebi<br>
<br>
"Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8svoe$rkb$1@fred.mathworks.com>...<br>
> Just found a useful solution: Use interp2 with '*linear' option. Works factor of 2.5 faster than imtransform. Any other ideas?<br>
> <br>
> best<br>
> shalin<br>
> "Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8ss9r$jhf$1@fred.mathworks.com>...<br>
> > Hello world,<br>
> > <br>
> > I have data defined over a grid, e.g. <br>
> > [xx yy]=meshgrid(1:0.1:1); %each pixel represents distance of 0.1<br>
> > data=xx.^2+yy.^2 ;<br>
> > <br>
> > I need to translate this data by subpixel 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 shifteddata need to be obtained only over the original grid. I want extrapolated locations to be zero.<br>
> > <br>
> > xshift=0.235; yshift=0.95; %Since shift is finer than sampling, subpixel shifting is required.<br>
> > xdata=[1 wt];<br>
> > ydata=[1 ht];<br>
> > T=maketform('affine',[1 0 0; 0 1 0; xshift yshift 1]);<br>
> > shifteddata=imtransform(data,T,'bilinear','XData',xdata,'YData',ydata);<br>
> > <br>
> > Results are satisfactory but slow as this shifting happens in the innermost loop. <br>
> > Can anyone suggest a method that involves direct indexing and hence would be faster? Any neat algorithm published in the literature for subpixel translation?<br>
> > <br>
> > best<br>
> > Shalin

Wed, 24 Feb 2010 11:58:07 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#720807
Shalin Mehta
Hi Dumebi,<br>
I did not receive a notification of your reply  so didn't get back to you on this.<br>
interp2's syntax is as follows:<br>
<a href="http://www.mathworks.com/access/helpdesk/help/techdoc/ref/interp2.html">http://www.mathworks.com/access/helpdesk/help/techdoc/ref/interp2.html</a><br>
<br>
out=interp2(xx,yy,in,xxi,yyi).<br>
<br>
You could do the following to shift a matrix by 0.5 pixels in X and 0.75 pixels in Y.<br>
[M N]=size(in); %Assuming square matrix.<br>
[xx yy]=meshgrid(1:N,1:M); %xx,yy are both outputs of meshgrid (so called plaid matrices).<br>
out=interp2(xx,yy,in,xx+0.5,yy+0.75);<br>
<br>
best<br>
Shalin<br>
<br>
"Dumebi Okwechime" <dumebi833@hotmail.com> wrote in message <hceds5$fa0$1@fred.mathworks.com>...<br>
> Hi Shalin, <br>
> <br>
> Was wondering what your input parameters were when using interp2. <br>
> Thanks<br>
> <br>
> Dumebi<br>
> <br>
> "Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8svoe$rkb$1@fred.mathworks.com>...<br>
> > Just found a useful solution: Use interp2 with '*linear' option. Works factor of 2.5 faster than imtransform. Any other ideas?<br>
> > <br>
> > best<br>
> > shalin<br>
> > "Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8ss9r$jhf$1@fred.mathworks.com>...<br>
> > > Hello world,<br>
> > > <br>
> > > I have data defined over a grid, e.g. <br>
> > > [xx yy]=meshgrid(1:0.1:1); %each pixel represents distance of 0.1<br>
> > > data=xx.^2+yy.^2 ;<br>
> > > <br>
> > > I need to translate this data by subpixel 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 shifteddata need to be obtained only over the original grid. I want extrapolated locations to be zero.<br>
> > > <br>
> > > xshift=0.235; yshift=0.95; %Since shift is finer than sampling, subpixel shifting is required.<br>
> > > xdata=[1 wt];<br>
> > > ydata=[1 ht];<br>
> > > T=maketform('affine',[1 0 0; 0 1 0; xshift yshift 1]);<br>
> > > shifteddata=imtransform(data,T,'bilinear','XData',xdata,'YData',ydata);<br>
> > > <br>
> > > Results are satisfactory but slow as this shifting happens in the innermost loop. <br>
> > > Can anyone suggest a method that involves direct indexing and hence would be faster? Any neat algorithm published in the literature for subpixel translation?<br>
> > > <br>
> > > best<br>
> > > Shalin

Wed, 24 Feb 2010 15:12:22 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#720879
Matt J
"Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8svoe$rkb$1@fred.mathworks.com>...<br>
> Just found a useful solution: Use interp2 with '*linear' option. Works factor of 2.5 faster than imtransform. Any other ideas?<br>
=================<br>
<br>
Yes, interp2 will still be quite slow because of all the different functionality it has to support, for example, interpolation on nonuniform grids. It is much faster to express the interpolation as a separable convolution and use <br>
conv2().<br>
<br>
Namely if your shift in x and y are 0<sx<1 and 0<sy<1 respectively, then you can do<br>
<br>
Image=conv2(Image,[sx, 1sx],'same');<br>
Result=conv2(Image,[sy, 1sy],'same');

Thu, 25 Feb 2010 06:02:05 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#721055
Rajesh
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. <br>
<br>
@Mat<br>
does conv2 work for fractions >1?? but even this, i guess, leaves the shifted column (for shift in x direction) in shambles. <br>
<br>
Wish we could have something like 'circshift' handle fractions along with integers. :(<br>
<br>
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.<br>
<br>
thanks.

Thu, 25 Feb 2010 06:54:05 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#721066
Matt J
"Rajesh " <rv_acharya@rediffmail.com> wrote in message <hm53ot$ig8$1@fred.mathworks.com>...<br>
> interp2 works well alright (thanks shalin mehta) but it fills the shifted region of the matrix with NaNs. <br>
=================<br>
<br>
You can extrapolate with zeros or any other desired value using the EXTRAPVAL option.<br>
<br>
>may be it can be padded by copying the adjacent columns or rows, as the case may be, using 'padarray' function. <br>
====================<br>
<br>
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:<br>
<br>
<a href="http://www.mathworks.com/matlabcentral/fileexchange/26292regularcontrolpointinterpolationmatrixwithboundaryconditions">http://www.mathworks.com/matlabcentral/fileexchange/26292regularcontrolpointinterpolationmatrixwithboundaryconditions</a><br>
<br>
<br>
> <br>
> @Mat<br>
> does conv2 work for fractions >1?? but even this, i guess, leaves the shifted column (for shift in x direction) in shambles. <br>
<br>
I don't know what you mean by leaving the column in shambles.<br>
<br>
For shifts >1, you could just convolve using a zeropadded 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<br>
<br>
Result=zeros(size(Image));<br>
Result(1:end+1k,1:end+1j)=Image(k:end,j:end);<br>
<br>
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.<br>
<br>
<br>
> 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.<br>
==============<br>
<br>
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.

Thu, 25 Feb 2010 15:25:21 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#721205
Matt J
"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hm56qd$t3c$1@fred.mathworks.com>...<br>
<br>
> 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.<br>
================<br>
<br>
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.<br>
<br>

Fri, 26 Feb 2010 10:24:05 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#721456
Rajesh
> You can extrapolate with zeros or any other desired value using the EXTRAPVAL option.<br>
> <br>
<br>
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. <br>
<br>
Also, replacing them with a constant might give artefacts in futue reconstructions (rings in CT images) <br>
> <br>
> Result=zeros(size(Image));<br>
> Result(1:end+1k,1:end+1j)=Image(k:end,j:end);<br>
<br>
Thanks for this as well.<br>
<br>
> 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.<br>
<br>
thanks (appologies if this amounts to hijacking the original thrd)

Wed, 06 Feb 2013 19:26:07 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#897327
Paulus Potter
It should be:<br>
<br>
Image=conv2(Image,[sx, 1sx],'same');<br>
Result=conv2(Image,[sy; 1sy],'same'); <br>
<br>
=> 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.<br>
<br>
"Matt J" wrote in message <hm3fkm$c2u$1@fred.mathworks.com>...<br>
> "Shalin Mehta" <shalinDOTmehtaHATESSPAM@gmail.com> wrote in message <h8svoe$rkb$1@fred.mathworks.com>...<br>
> > Just found a useful solution: Use interp2 with '*linear' option. Works factor of 2.5 faster than imtransform. Any other ideas?<br>
> =================<br>
> <br>
> Yes, interp2 will still be quite slow because of all the different functionality it has to support, for example, interpolation on nonuniform grids. It is much faster to express the interpolation as a separable convolution and use <br>
> conv2().<br>
> <br>
> Namely if your shift in x and y are 0<sx<1 and 0<sy<1 respectively, then you can do<br>
> <br>
> Image=conv2(Image,[sx, 1sx],'same');<br>
> Result=conv2(Image,[sy, 1sy],'same');

Wed, 06 Feb 2013 19:47:09 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#897333
Bruno Luong
"Paulus Potter" wrote in message <keuaof$amu$1@newscl01ah.mathworks.com>...<br>
> It should be:<br>
> <br>
> Image=conv2(Image,[sx, 1sx],'same');<br>
> Result=conv2(Image,[sy; 1sy],'same'); <br>
> <br>
<br>
This is about twice faster<br>
Result=conv2(Image,[sy; 1sy]*[sx, 1sx],'same');<br>
<br>
% Bruno

Wed, 06 Feb 2013 22:33:09 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#897351
Matt J
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <keubvt$fki$1@newscl01ah.mathworks.com>...<br>
> "Paulus Potter" wrote in message <keuaof$amu$1@newscl01ah.mathworks.com>...<br>
> > It should be:<br>
> > <br>
> > Image=conv2(Image,[sx, 1sx],'same');<br>
> > Result=conv2(Image,[sy; 1sy],'same'); <br>
> > <br>
> <br>
> This is about twice faster<br>
> Result=conv2(Image,[sy; 1sy]*[sx, 1sx],'same');<br>
<br>
Maybe, but only because there are some funny suboptimal things happening inside conv2 implementationwise, and because the interpolation kernel here happens to be small. There's no way the 3rd version below should be the slowest.<br>
<br>
Image=rand(2000);<br>
kx=rand(1,10);<br>
ky=rand(10,1);<br>
<br>
tic;<br>
Image=conv2(Image,kx,'same');<br>
Result=conv2(Image,[sy; 1sy],'same'); <br>
toc<br>
%Elapsed time is 0.045940 seconds.<br>
<br>
<br>
tic;<br>
Result=conv2(Image,ky*kx,'same');<br>
toc<br>
%Elapsed time is 0.090292 seconds.<br>
<br>
<br>
tic;<br>
Result=conv2(kx , ky, Image,'same');<br>
toc <br>
%Elapsed time is 0.162708 seconds.

Wed, 06 Feb 2013 22:49:08 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#897352
Bruno Luong
"Matt J" wrote in message <keuln5$onb$1@newscl01ah.mathworks.com>...<br>
<br>
> <br>
> Maybe, but only because there are some funny suboptimal things happening inside conv2 implementationwise, and because the interpolation kernel here happens to be small. There's no way the 3rd version below should be the slowest.<br>
<br>
Of course. The reason is obvious: 2+2 = 2*2, but 10+10 << 10*10.<br>
<br>
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.<br>
<br>
Bruno

Thu, 07 Feb 2013 16:49:08 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#897424
Matt J
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <keuml4$rtj$1@newscl01ah.mathworks.com>...<br>
> "Matt J" wrote in message <keuln5$onb$1@newscl01ah.mathworks.com>...<br>
> <br>
> > <br>
> > Maybe, but only because there are some funny suboptimal things happening inside conv2 implementationwise, and because the interpolation kernel here happens to be small. There's no way the 3rd version below should be the slowest.<br>
> <br>
> Of course. The reason is obvious: 2+2 = 2*2, but 10+10 << 10*10.<br>
============<br>
<br>
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.

Thu, 07 Feb 2013 17:23:08 +0000
Re: subpixel shifting of a matrix
http://www.mathworks.com/matlabcentral/newsreader/view_thread/261037#897426
Bruno Luong
"Matt J" wrote in message <kf0lu4$eph$1@newscl01ah.mathworks.com>...<br>
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <br>
> <br>
> 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.<br>
<br>
This is an independent question, and a little OT. But here is few elements of explanation:<br>
<br>
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.<br>
<br>
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.<br>
<br>
Bruno