Get notified about new tutorials
RECEIVE NEW TUTORIALS

First 15 Minutes Free

329 sessions given

since Jul 09, 2014

since Jul 09, 2014

Likelihood of Reply:
75%

Response Time:
within an hour

Ray Phan

Jan 30, 2015

<p>In your comments, you mentioned you wanted to resize an image using bilinear interpolation. Bear in mind that the bilinear interpolation algorithm is size independent. You can very well use the same algorithm for enlarging an image as well as shrinking an image. The right scale factors to sample the pixel locations are dependent on the output dimensions you specify. This <strong>doesn't</strong> change the core algorithm by the way.</p>
<p>Before I start with any code, I'm going to refer you to <a href="https://ia700307.us.archive.org/7/items/Lectures_on_Image_Processing/EECE253_12_Resampling.pdf" rel="nofollow">Richard Alan Peters' II digital image processing slides on interpolation</a>, specifically slide #96. It has a great illustration as well as pseudocode on how to do bilinear interpolation that is MATLAB friendly. To be self-contained, I'm going to include his slide here so we can follow along and code it:</p>
<p><img src="http://i.stack.imgur.com/t7z2N.png" alt="enter image description here"></p>
<p>Let's write a routine that will do this for us. This function will take in an image (that is read in through <a href="http://www.mathworks.com/help/matlab/ref/imread.html" rel="nofollow"><code>imread</code></a>) which can be either colour or grayscale, as well as an array of two elements - The image you want to resize and the output dimensions in a two-element array of the final resized image you want. The first element of this array will be the rows and the second element of this array will be the columns. We will simply go through this algorithm and calculate the output pixel colours / grayscale values using this pseudocode:</p>
<pre><code>function [out] = bilinearInterpolation(im, out_dims)
%// Get some necessary variables first
in_rows = size(im,1);
in_cols = size(im,2);
out_rows = out_dims(1);
out_cols = out_dims(2);
%// Let S_R = R / R'
S_R = in_rows / out_rows;
%// Let S_C = C / C'
S_C = in_cols / out_cols;
%// Define grid of co-ordinates in our image
%// Generate (x,y) pairs for each point in our image
[cf, rf] = meshgrid(1 : out_cols, 1 : out_rows);
%// Let r_f = r'*S_R for r = 1,...,R'
%// Let c_f = c'*S_C for c = 1,...,C'
rf = rf * S_R;
cf = cf * S_C;
%// Let r = floor(rf) and c = floor(cf)
r = floor(rf);
c = floor(cf);
%// Any values out of range, cap
r(r < 1) = 1;
c(c < 1) = 1;
r(r > in_rows - 1) = in_rows - 1;
c(c > in_cols - 1) = in_cols - 1;
%// Let delta_R = rf - r and delta_C = cf - c
delta_R = rf - r;
delta_C = cf - c;
%// Final line of algorithm
%// Get column major indices for each point we wish
%// to access
in1_ind = sub2ind([in_rows, in_cols], r, c);
in2_ind = sub2ind([in_rows, in_cols], r+1,c);
in3_ind = sub2ind([in_rows, in_cols], r, c+1);
in4_ind = sub2ind([in_rows, in_cols], r+1, c+1);
%// Now interpolate
%// Go through each channel for the case of colour
%// Create output image that is the same class as input
out = zeros(out_rows, out_cols, size(im, 3));
out = cast(out, class(im));
for idx = 1 : size(im, 3)
chan = double(im(:,:,idx)); %// Get i'th channel
%// Interpolate the channel
tmp = chan(in1_ind).*(1 - delta_R).*(1 - delta_C) + ...
chan(in2_ind).*(delta_R).*(1 - delta_C) + ...
chan(in3_ind).*(1 - delta_R).*(delta_C) + ...
chan(in4_ind).*(delta_R).*(delta_C);
out(:,:,idx) = cast(tmp, class(im));
end
</code></pre>
<p>Take the above code, copy and paste it into a file called <code>bilinearInterpolation.m</code> and save it. Make sure you change your working directory where you've saved this file. </p>
<hr>
<p>Except for <code>sub2ind</code> and perhaps <code>meshgrid</code>, everything seems to be in accordance with the algorithm. <a href="http://www.mathworks.com/help/matlab/ref/meshgrid.html" rel="nofollow"><code>meshgrid</code></a> is very easy to explain. All you're doing is specifying a 2D grid of <code>(x,y)</code> co-ordinates, where each location in your image has a pair of <code>(x,y)</code> or column and row co-ordinates. Creating a grid through <code>meshgrid</code> avoids any <code>for</code> loops as we will have generated all of the right pixel locations from the algorithm that we need before we continue.</p>
<p>How <a href="http://www.mathworks.com/help/matlab/ref/sub2ind.html" rel="nofollow"><code>sub2ind</code></a> works is that it takes in a row and column location in a 2D matrix (well... it can really be <strong>any</strong> amount of dimensions you want), and it outputs a <strong>single</strong> linear index. If you're not aware of how MATLAB indexes into matrices, there are two ways you can access an element in a matrix. You can use the row and column to get what you want, or you can use a <strong>column-major</strong> index. Take a look at this matrix example I have below:</p>
<pre><code>A =
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
</code></pre>
<p>If we want to access the number 9, we can do <code>A(2,4)</code> which is what most people tend to default to. There is another way to access the number 9 using a single number, which is <code>A(11)</code>... now how is that the case? MATLAB lays out the memory of its matrices in <strong>column-major</strong> format. This means that if you were to take this matrix and stack all of its <strong>columns</strong> together in a single array, it would look like this:</p>
<pre><code>A =
1
6
11
2
7
12
3
8
13
4
9
14
5
10
15
</code></pre>
<p>Now, if you want to access element number 9, you would need to access the 11th element of this array. Going back to the interpolation bit, <code>sub2ind</code> is crucial if you want to vectorize accessing the elements in your image to do the interpolation without doing any <code>for</code> loops. As such, if you look at the last line of the pseudocode, we want to access elements at <code>r</code>, <code>c</code>, <code>r+1</code> and <code>c+1</code>. Note that all of these are <strong>2D arrays</strong>, where each element in each of the matching locations in all of these arrays tell us the four pixels we need to sample from in order to produce the final output pixel. The output of <code>sub2ind</code> will <strong>also</strong> be 2D arrays of the same size as the output image. The key here is that each element of the 2D arrays of <code>r</code>, <code>c</code>, <code>r+1</code>, and <code>c+1</code> will give us the <strong>column-major</strong> indices into the image that we want to access, and by throwing this as input into the image for indexing, we will exactly get the pixel locations that we want.</p>
<hr>
<p>There are some important subtleties I'd like to add when implementing the algorithm:</p>
<ol>
<li><p>You need to make sure that any indices to access the image when interpolating outside of the image are either set to 1 or the number of rows or columns to ensure you don't go out of bounds. Actually, if you extend to the right or below the image, you need to set this to one <strong>below</strong> the maximum as the interpolation requires that you are accessing pixels to one over to the right or below. This will make sure that you're still within bounds.</p></li>
<li><p>You also need to make sure that the output image is cast to the same class as the input image.</p></li>
<li><p>I ran through a <code>for</code> loop to interpolate each channel on its own. You could do this intelligently using <a href="http://www.mathworks.com/help/matlab/ref/bsxfun.html" rel="nofollow"><code>bsxfun</code></a>, but I decided to use a <code>for</code> loop for simplicity, and so that you are able to follow along with the algorithm.</p></li>
</ol>
<hr>
<p>As an example to show this works, let's use the <code>onion.png</code> image that is part of MATLAB's system path. The original dimensions of this image are <code>135 x 198</code>. Let's interpolate this image by making it larger, going to <code>270 x 396</code> which is twice the size of the original image:</p>
<pre><code>im = imread('onion.png');
out = bilinearInterpolation(im, [270 396]);
figure;
imshow(im);
figure;
imshow(out);
</code></pre>
<p>The above code will interpolate the image by increasing each dimension by twice as much, then show a figure with the original image and another figure with the scaled up image. This is what I get for both:</p>
<p><img src="http://i.stack.imgur.com/KE5s0.png" alt="enter image description here"></p>
<p><img src="http://i.stack.imgur.com/OmNRo.png" alt="enter image description here"></p>
<hr>
<p>Similarly, let's shrink the image down by half as much:</p>
<pre><code>im = imread('onion.png');
out = bilinearInterpolation(im, [68 99]);
figure;
imshow(im);
figure;
imshow(out);
</code></pre>
<p>Note that half of 135 is 67.5 for the rows, but I rounded up to 68. This is what I get:</p>
<p><img src="http://i.stack.imgur.com/t7x4f.png" alt="enter image description here"></p>
<p><img src="http://i.stack.imgur.com/VE7JC.png" alt="enter image description here"></p>
<hr>
<p>One thing I've noticed in practice is that upsampling with bilinear has decent performance in comparison to other schemes like bicubic... or even <a href="http://en.wikipedia.org/wiki/Lanczos_resampling" rel="nofollow">Lanczos</a>. However, when you're shrinking an image, because you're removing detail, nearest neighbour is very much sufficient. I find bilinear or bicubic to be overkill. I'm not sure about what your application is, but play around with the different interpolation algorithms and see what you like out of the results. Bicubic is another story, and I'll leave that to you as an exercise. Those slides I referred you to does have material on bicubic interpolation if you're interested.</p>
<hr>
<p>Good luck!</p>
<p>This tip was originally posted on <a href="http://stackoverflow.com/questions/26142288/Resize%20an%20image%20with%20bilinear%20interpolation%20without%20imresize/26143655">Stack Overflow</a>.</p>