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.
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.
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.
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)
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
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.
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!
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;
ptsIn(repeatedPtsMask,:) = ;
ptsXYZdistanceCumsum(repeatedPtsMask) = ;
ptsSampleLocs = linspace(0,ptsXYZdistanceCumsum(end), ceil(ptsXYZdistanceCumsum(end))/sampleDistance);
ptsOut = interp1(ptsXYZdistanceCumsum, ptsIn, ptsSampleLocs);
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 :)
Is there an algorithm implemented in MATLAB which estimate the depth map from a single image?
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?