Distance
A distance or metric d must satisty conditions:
- d(u,v)>=0, if d(u,v)=0 then u=v
- d(u,v) = d(v,u)
- d(u,v) = d(u,w) + d(w,v)
The first condition says that the distance is non-negative value. If the distance between two points is zero, then these two points are at the same location. The second condition says that the distance for going from one point to another is the same as returning distance. Finally, the third condition says that when going from one point to another, if stoping at a third point in between, the overall distance can never be less than going non-stop.
A distance n from a point or region can be determined by dilating the point or region by the str. el. nB. B gives the metric used. B is any symetrical str. el. with the origin.
Distance: Digital Disks
The 8-connected distance (chessboard) can be generated by the elementary 3x3 square. Below a disk of radius 5 is generated.
str1=mmsebox(1); A=mmseshow(str1,'EXPAND'); mmshow(A); ; str2=mmsesum(str1,5); B=mmseshow(str2,'EXPAND'); ; mmshow(B); ;
|
The 4-connected distance (city-block) can be generated by the elementary 3x3 cross. Below a disk of radius 5 is generated.
str1=mmsecross(1); C=mmseshow(str1,'EXPAND'); mmshow(C); ; str2=mmsesum(str1,5); D=mmseshow(str2, 'EXPAND'); mmshow(D); ;
|
Distance Transform (DT)
The distance from any object pixel to the background can be computed by the Distance Transform DT. You can choose the metric using in the DT. Three metrics are used below: city-block, chessboard and Euclidean. The Euclidean is not a discrete metric and the str. el. to define the neighborhood depends on the maximum possible distance on the image.
A=imread('blob3.tif');
mmshow(A);
d4=mmdist(A,mmsecross);
mmshow(d4);
d8=mmdist(A,mmsebox);
mmshow(d8);
de=mmdist(A,mmsebox,'EUCLIDEAN');
mmshow(de);
|
Distance from Region
The distance from a region can be computed by taking the Distance Transform of the background. Below, we compute the distance using three different metrics: city-block, using the elementary cross str. el., chessboard, using the elementary square, and a vertical distance using a 1x3 structuring element.
A=imread('region.tif');
mmshow(A); ;
B=mmdist(mmneg(A),mmsecross(1));
mmdtshow(B); ;
C=mmdist(mmneg(A),mmsebox(1));
mmdtshow(C); ;
se=logical(uint8([1;1;1]));
str=mmimg2se(se);
D=mmdist(mmneg(A),str);
mmdtshow(D); ;
|
Geodesic Distance
The geodesic distance is a distance more familiar to our daily activities. The distance from our home to work is not a straight line, rather the paths available are restricted. In this sense the distance is the shortest path in all possible paths availables. The geodesic distance can be computed by the geodesic dilation.
Below is an illustration where the restriction is given by a region in the shape of the letter G. We want to compute all the geodesic distances from any point in G to a given point.
A=imread('gletter.tif');
mmshow(A);
B=mmsubm(A,A);
B(62,78)=1;
B=mmdil(B,mmsedisk(1));
mmshow(A,B);
C=mmgdist(A,B,mmsebox,'EUCLIDEAN');
mmdtshow(C,20);
|
Finding Shortest Path between two points
To find the shortest geodesic path between two points, we can use the property that the sum of the distances to both points is minimal in the shortest path. So, we can process the following steps:
- Compute the Geodesic Distance from the first point
- Compute the Geodesic Distance from the second point
- Add both distances
- Find the minimum value, they are in the shortest path
Minimum Distance in a Map
Below is a simple demonstration to compute the shortest path from one place to another in a map. Suppose that the white pixels in the map are the only places that a path can exists. First compute the geodesic distance from each points.
A=imread('mapacampus_bw.tif');
img=mmsubm(A,A);
P1=img; P2=img;
P1(26,94)=1;
P2(300,290)=1;
P1=mmdil(P1,mmsedisk(2));
P2=mmdil(P2,mmsedisk(2));
mmshow(A,P1,P2);
B=mmgdist(A,P1,mmsebox,'EUCLIDEAN');
mmdtshow(B,80);
C=mmgdist(A,P2,mmsebox,'EUCLIDEAN');
mmdtshow(C,80);
|
Next, add both distances and compute the places of the minimum values. The shortest path is overalayed in red.
D=mmaddm(B,C); mmdtshow(D,400); d=mmstats(D,'min') d = 389 res=mmcmp(D,'<=', uint16(d+1)); mmshow(A,res);
|
Exercises
- Generate an image similar to the touchcell.tif using the distance function.
f=imread('touchcell.tif');
mmshow(f);
|
