Steve on Image Processing

Walking along a path 5

Posted by Steve Eddins,

Last month I was experimenting with an algorithm in which I needed to construct a set of equidistant steps along a path consisting of line segments. (I'll call this a polyline path, or polyline for short.) Today I want to show you how to construct such a path in MATLAB. Along the way I'll show you the function improfile and give you a pointer to a database of sample range images that I found.

Contents

Polylines

Here's a simple example of a polyline. (Note that, because we're going to be talking about distances, I'm going to set the aspect ratio of my plots to be 1:1 by calling axis equal.)

x = [24 214 327 617];
y = [375 223 218 341];
plot(x,y)
axis equal

This has three connected line segments. In this example, each segment has a different length. I wanted to be able to find a certain number of points that were equally spaced along this path.

IMPROFILE

After pondering this problem for a minute or so, I remembered that the function improfile does exactly this computation internally. The function improfile is used to compute pixel-value profiles along a user-specified polyline.

Let me illustrate improfile using a range image. In a range image, the pixel values represent estimated distance from the imaging device. I found the USF (University of South Florida) Range Image Database online. Below is a range image I downloaded from the database. It was taken by the Vision Lab at USF using a "K2T structured light camera." (No, I don't know what that is.) The web site helpfully tells me that the image is stored in "rasterfile format," which is pretty dated but fortunately supported by imread.

url = 'http://blogs.mathworks.com/images/steve/2012/chessmen.range';
I = imread(url, 'ras');
imshow(I, 'InitialMagnification', 50)

Let's use improfile to compute a cross-section of range values along a particular path. First, though, let me superimpose the path on the image so you can where it is. (Although improfile has an interactive mode that lets you select the path using a mouse, I can't show that here.)

hold on
plot(x,y,'r','LineWidth',5)
hold off

Here's the cross-section of range values.

improfile(I,x,y)

You can see that improfile shows the cross-section as a 3-D plot. To see the cross-section as a normal 2-D line plot, call improfile with an output argument to get the cross-section values and then pass them to plot.

c = improfile(I,x,y);
plot(c)

Computing equidistant steps along the polyline

As part of its computation, improfile needs to compute equidistant steps along the polyline path. So how does that work?

The function first computes the cumulative distance from the beginning of the polyline to each vertex along the way, and then it uses a clever call to interp1 to compute the steps.

xy = [x' y'];
d = diff(xy,1)
d =

   190  -152
   113    -5
   290   123

dist_from_vertex_to_vertex = hypot(d(:,1), d(:,2))
dist_from_vertex_to_vertex =

  243.3187
  113.1106
  315.0063

cumulative_dist_along_path = [0;
    cumsum(dist_from_vertex_to_vertex,1)]
cumulative_dist_along_path =

         0
  243.3187
  356.4293
  671.4356

Now we can get our steps by constructing a call to interp1.

num_points = 20;
dist_steps = linspace(0, cumulative_dist_along_path(end), num_points);
points = interp1(cumulative_dist_along_path, xy, dist_steps)
points =

   24.0000  375.0000
   51.5949  352.9241
   79.1898  330.8482
  106.7847  308.7722
  134.3796  286.6963
  161.9745  264.6204
  189.5694  242.5445
  218.0483  222.8209
  253.3525  221.2587
  288.6567  219.6966
  323.9609  218.1345
  356.7328  230.6108
  389.2662  244.4095
  421.7996  258.2081
  454.3330  272.0068
  486.8664  285.8054
  519.3998  299.6041
  551.9332  313.4027
  584.4666  327.2014
  617.0000  341.0000

Plot the points, superimposing them on the original path, to see how we did.

plot(x,y)
hold on
plot(points(:,1), points(:,2), 'o')
hold off
axis equal

There you go. Now you know about improfile, you know how to compute a path along a polyline, and you know about an online database of sample range imagery.

I think we should call it a day.


Get the MATLAB code

Published with MATLAB® 7.14

5 CommentsOldest to Newest

Hi Steve,
Very nice, useful post. Thanks.
It’s worth pointing out that one can compute disparity (depth) maps using the Computer Vision System Toolbox and multiple views (images) of a scene. Disparity maps are convertable (with appropriate calibration and scaling) to range maps.
Cheers,
Brett

Hi Steve,

This is a very useful post.

Obtaining equidistant points along a path shows up in many different applications/workflows. For example, using Fourier descriptors for shape matching or classification in images typically requires a preliminary step of resampling the boundary of the shape to N equidistant points along the boundary (sometimes termed boundary point equalization). So if we want to have a 32-element Fourier descriptor vector for the boundary, we need obtain 32 equidistant points on the boundary.

Having a simple way as shown in your post to get these equidistant points makes it much easier to just work with Fourier descriptors.

Thanks for this nice post!

-Spandan

Hi Steve, nice post, thanks.
I hit this type of problem regularly, so I made a function which follows the same logic. I added a little piece to ensure it handles repeated points (which would result in an interp1 error):

function ptsOut = subSamplePts(ptsIn,sampleDistance)
ptsXYZdistanceCumsum = cat(1,0,cumsum(sqrt(sum(diff(ptsIn,1).^2,2))));
repeatedPtsMask = diff(ptsXYZdistanceCumsum)==0;
if any(repeatedPtsMask)
ptsIn(repeatedPtsMask,:) = [];
ptsXYZdistanceCumsum(repeatedPtsMask) = [];
end
ptsSampleLocs = linspace(0,ptsXYZdistanceCumsum(end), ceil(ptsXYZdistanceCumsum(end))/sampleDistance);
ptsOut = interp1(ptsXYZdistanceCumsum, ptsIn, ptsSampleLocs);
end

Just a final note, while the output will be equally spaced “along the original polyline path”, they won’t necessarily be equally spaced points themselves. I had this mentioned in an Answers post somewhere where I used “equally spaced points” to describe this… I was about to argue until I saw it was John D’Errico commenting… he’s right of course :)

Hi,
Is there an algorithm implemented in MATLAB which estimate the depth map from a single image?

Thanks.

Hi, this doubt does not have relationship with example but anyway, do you have any idea about how I can use the Dijkstra algorithm I’m totally lost with biograph? what do you could recommend for the optimization routes?

thanks

These postings are the author's and don't necessarily represent the opinions of MathWorks.