[PDF] CHAPTER 4 4. METHODS FOR MEASURING DISTANCE IN IMAGES

View - Download CHAPTER 4 4. METHODS FOR MEASURING DISTANCE IN IMAGES

Previous PDF

Next PDF

CHAPTER 4

4. METHODS FOR MEASURING DISTANCE IN IMAGES

4.1. INTRODUCTION

In image analysis, the distance transform measures the distance of each object point from the nearest boundary and is an important tool in computer vision, image processing and pattern recognition. In the distance transform, binary image specifies the distance from each pixel to the nearest non-zero pixel. The euclidean distance is the straight-line distance between two pixels and is evaluated using the euclidean norm. The city block distance metric measures the path between the pixels based on a four connected neighbourhood and pixels whose edges touch are one unit apart and pixels diagonally touching are two units apart. The chessboard distance metric measures the path between the pixels based on an eight connected neighbourhood. The quasi-euclidean metric measures are the total euclidean distance along a set of horizontal, vertical, and diagonal line segments. A central problem in image recognition and computer vision is determining the distance between images and efforts which have been made to define image distances to provide intuitively reasonable results. Estimating distances in digital image is useful in different shape representation and shape recognition tasks [Borgefors 1994].

4.2. DISTANCE METRICS

The distance transform provides a metric or measure of the separation of points in the image. The bwdist function calculates the distance between each pixel and the nearest nonzero pixel for binary images. The bwdist function supports several distance metrics listed in table 4.1. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.

Table 4.1 various distance metrics

Distance

Metric

Description Illustration

Euclidean The Euclidean distance is the

straight-line distance between two pixels. 0 0 0 0 1 0 0 0 0 Image

1.41 1.0 1.41

1.0 0.0 1.0

1.41 1.0 1.41

Distance Transform

City Block

The city block distance metric

measures the path between the pixels based on a 4-connected neighborhood. Pixels whose edges touch are 1 unit apart and pixels diagonally touching are 2 units apart. 1 0 0 0 1 0 0 0 0 Image

2 1 2

1 0 1

2 1 2

Distance

Transform

Chessboard

The chessboard distance metric

measures the path between the pixels based on an 8-connected neighborhood. Pixels whose edges or corners touch are 1 unit apart. 1 0 0 0 1 0 0 0 0 Image

1 1 1

1 1 1

1 1 1

Distance

Transform

Quasi-

Euclidean

The quasi-Euclidean metric

measures the total Euclidean distance along a set of horizontal, vertical and diagonal line segments.

0 0 0 0 0

0 0 0 0 0

0 0 1 0 0

0 0 0 0 0

0 0 0 0 0

Image

2.8 2.2 2.0 2.2 2.8

2.2 1.4 1.0 1.4 2.2

2.0 1.0 0 1.0 2.0

2.2 1.4 1.0 1.4 2.2

2.8 2.2 2.0 2.2 2.8

Distance Transform

Chamfer distance

The chamfer distance dM between 2

points A and B is the minimum of the associated costs to all the paths starting from A to B c2 c1 c2 c1 0 c1 c2 c1 c2 c2 c1 c2 c1 0 0 c1 c2 c1 c2

Parallel, forward & backward chamfer

Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.

4.3. EUCLIDEAN DISTANCE

4.3.1. Euclidean distance

The euclidean distance is the distance between two points in euclidean space. The two points P and Q in two dimensional euclidean spaces and P with the coordinates (p1, p2), Q with the coordinates (q1, q2). The line segment with the endpoints of P and Q will form the hypotenuse of a right angled triangle. The distance between two points p and q is defined as the square root of the sum of the squares of the differences between the corresponding coordinates of the points. The two-dimensional euclidean geometry, the euclidean distance between two points a = (ax, ay) and b = (bx, by) is defined as :

4.3.2. Euclidean distance algorithm

Euclidean distance algorithm computes the minimum distance between a column vector x and a collection of column vectors in the code book matrix cb. The algorithm computes the minimum distance to x and finds the column vector in cb that is closest to x.

Figure 4.1 shows Euclidean distance algorithm.

ෂ቗ݩ1ൣ ݪ1ቘ୓ൢ ቗ݩ2ൣ ݪ2ቘ୓ൢ ⋯ൢ ቗ݩnൣ ݪnቘ୓

൩ෆ෪቗ݩiൣ ݪiቘ୓௾ In one dimension, the distance between two points, x

1 and x2, on a line is simply the

absolute value of the difference between the two points as: Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.

ෂ቗ݗ2ൣ ݗ1ቘ୓൩|ݗ2ൣ ݗ1| In two dimensions, the distance between P = (p1, p2) and q = (q1, q2) as: ෂ቗ݩ1ൣ ݪ1ቘ୓ൢ ቗ݩ2ൣ ݪ2ቘ୓

Step1: load the column vector x;

Step2: load the code book;

Step3: minimum distance is initially set to the first element of cb.

Step4: i.e. set idx=1;

Step5: compute distance by normalized values of (x-cb) for all cb; Step6: if d is less than distance set distance is equal to d;

Step7: set idx=index;

Step8: end

Figure 4.1 Euclidean distance algorithm

4.3.3. Euclidean function

The input source data is a feature class; it will first be converted internally to a raster before the euclidean analysis is performed. The resolution will be smaller of the height or width of the extent of the feature class, divided by 250 and the resolution can be set with the output cell size parameter. Figure 4.2 shows how euclidean function works.

Figure 4.2 Euclidean function

Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. The euclidean distance is calculated from the center of the source cells to the center of

each of the surrounding cells and true distance is calculated to each cell in the distance

functions. The euclidean algorithm works as follows: for each cell, the distance is calculated to each source cell by calculating the hypotenuse, with the x-max and y-max. Figure 4.3 shows sample sonographic image of appendicitis.

Figure 4.3 Sonographic image of Appendicitis

Figure 4.4 Euclidean Distance Measure

Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. The shortest distance to a source is determined if it is less than the specified maximum distance and the value is assigned to the cell location on the output raster. The output values for the euclidean distance raster are floating-point distance values and the cell is at an equal distance to two or more sources, which assigned to the source as encountered first in the scanning process. The euclidean distance raster tells how close each cell is to the nearest source and raster defines which source zone and cell value is the closest. The euclidean direction identifies the direction to the closest source cell [Esri, 2007]. Figure 4.4 shows euclidean distance measure.

4.3.4. Image and Euclidean Distance

M X N images can be easily discussed in an MN dimensional euclidean space, called image space. It is natural to adopt the base e

1, e2 ,....., eMN to form a coordinate system of

the image space, where e kN+ l corresponds to an ideal point source with unit intensity at location (k, l). Thus an image x = (x

1, x2 ,.........., xMN ) , where xkN+l is the gray level at the

(k, l) th pixel, is represented as a point in the image space, and xkN+l with respect to ekN+ l . The origin of the image space is an image whose gray levels are zero everywhere [Liwei Wang et al., 2005]. Although the algebra of the image space can be easily formulated as above, the euclidean distance of images could not be determined until the metric coefficients of the basis are given. The metric coefficients g ij i, j =1, 2,.....,MN , are defined as where <, > is the scalar product, and θij is the angle between ei and ej . Note that, if < e i ei > = < ej ej> =..., i.e. all the base vectors have the same length, then gij depends Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. completely on the angle θij. Given the metric coefficients, the euclidean distance of two images x, y is written by where the symmetric matrix G = (g ij)MNxMN will be referred to as metric matrix.

For images of fixed size M by N , every MN

th order and positive definite matrix G induces a euclidean distance. But most of them are not appropriate for measuring image distances. For example, suppose any two base vectors e i ,ej (i ≠ j) , no matter which pixels they correspond to are mutually perpendicular, the basis then forms a Cartesian coordinate system. Accordingly, G is the identity matrix, and it induces the traditional euclidean distance given by Geometrically, this defect is due to the orthogonality of the base vectors e

1, e2

,.....,e MN which correspond to pixels. Clearly, the information about the spatial relationship, i.e. the distances between the pixels, cannot be reflected by all mutually perpendicular base vectors. Such information, however, often appears in intuitive image distance as in the following statement: A slightly deformed image is very similar to the original one. Here, slightly deformed means that pixels in the deformed image are close to the corresponding pixels in the original image. This implies that a good euclidean distance for images should contain the information of pixel distances. Accordingly, the metric coefficients, which define the euclidean distance, have to be related to the pixel distances. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. If the metric coefficients depend properly on the pixel distances, the obtained euclidean distance is insensitive to small deformation. The two distances that are considered are: one is the image distance measured in the high dimensional image space, the other is the pixel distance. Let P iPj , i, j = 1, 2,....., MN , be pixels. The pixel distance, written as | P i - Pj |, is the distance between Pi and Pj on the image lattice. For example, if Pi is at location (k, l), and P j is at (k′, l′) , | Pi - Pj | may be . Let euclidean distance, set θ ij = π/2 . Then gij = cos θij = 0 hence thus obtained euclidean distance is

4.4. CHAMFER DISTANCE

The chamfer distance relatively well approximates the euclidean distance and is widely used because of its relatively small computational requirements as it imposes only

2 scans of the n-dimensional image independently of the dimension of the image. The

chamfer distances are widely used in image analysis of the euclidean distance with integers [Eric Remy et al., 2000]. The chamfer distance dM between 2 points A and B is the minimum of the associated costs to all the paths PAB from A to B : Chamfer distance was first proposed an evaluation of two dimensional asymmetric distance between two set of edge points. Given a template T positioned at location x in an Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. image I and a binary edge map E of the image I, the basic form of chamfer distance is calculated as where || . ||

2 is l2 norm and |T| denotes number of points in template T. Chamfer

distance can be efficiently computed as: where DT E is a distance transform defined for every image point x ׭ Meanwhile, in practice, distance transform is truncated to a constant Chamfer distances are used for computing geodesic diameters to propagate chamfer distances from a binary image, constrained to another binary image. Figure 4.5 Chamfer Distance [Muhammad Akmal et al., 1998] Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. The chamfer distance transformations rely on the assumption that it is possible to deduce the value of the distance at a pixel from the value of the distance at its neighbours. They offer a good approximation to the desired euclidean distance transform which is computationally very intensive [Shengwen Guo et al., 2009]. Chamfer distance algorithms are a class of discrete algorithms that offer a good approximation and euclidean distance transform at a lower computational cost. The distance approximates the global distance computation with repeated propagation of local distances within a small neighborhood mask. The approximation error depends upon the size of the neighborhood and the selection of the local distances [Muhammad Akmal et al., 1998].

Figure 4.5 shows the sample chamfer distance.

Figure 4.6 Euclidean and chamfer distances on appendicitis image Chamfer distances are local distances which permit to deduce a distance from the distances of close neighbours unlike d E. The computation of the medial axis is done by a local test and all computations are done by using integer numbers and linear operations such as +, - and <. Figure 4.6 shows euclidean and chamfer distances on appendicitis image. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.

4.5. GEODESIC DISTANCE

Geodesics are locally shortest paths in the sense that any perturbation of a geodesic curve will increase the length. The minimal length path between two points on the surface is the minimal geodesics connecting those points. Geodesics minimize the euclidean distance on a surface and a geodesic distance between two vertices of a triangle mesh surface, for instance is computed using a shortest path algorithm on the mesh graph, where the weight associated with an edge is its length. The geodesic distances on a three dimensional surface, is important in many fields of computer graphics and geometric modeling. Normally, geodesic paths on a surface are critical in surface segmentation and editing methods since cutting the surface along the geodesic paths produces better results and minimum distortion parameterization or remeshing of 3D models are based on the knowledge of geodesic distances . The applications include isometry-invariant shape classification, skinning, medical imaging and geophysics [Katz et al., 2003]. Figure 4.7 shows difference between euclidean distance and geodesic distance on a circle. Figure 4.7 Euclidean and geodesic distances on a circle [Balu et al., 2012] Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. Geodesic has shortest paths, and perturbation of a geodesic curve will increase its length. A geodesic distance between two vertices of a triangle mesh surface can be computed using a shortest path algorithm on the mesh graph with an edge is its length. The Dijkstra"s

algorithm can lengths of paths very quickly, but produce paths quite different from true

geodesics and the paths created pass only through the mesh vertices. The research on geodesic computation on a surface focuses on solving the eikonal equation. Kimmel and Sethian proposed an optimal time algorithm for computing the geodesic distances and extracting shortest paths on triangulated manifolds using the fast marching method [Sifri et al., 2003]. Figure 4.8 Euclidean and geodesic distances on an appendicitis image In figure 4.8, white lines are represent euclidean distance and blue line represents geodesic distances on an appendicitis image. Mitchell et al (1987) presented an algorithm for determining the shortest path between a source and a destination on an arbitrary polyhedral surface, and seeking to approximate distance maps on a parametric surface and the eikonal equation on a discrete grid obtained by sampling the parametric domain. Elad et al., (2003) presented an efficient O(n) numerical algorithm for first-order approximation of geodesic distances on parametric surfaces, where n is the number of points on the surface. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.

4.5.1. Geodesic distance from a binary region on an image

Let I(x) :

ψ  Rd be an image (d = 3 for a color image), whose support ψ ٜ assumed to be continuous. Given a binary mask M (with M(x) ׭ {0, 1}, ק x ׭ to a "seed" region (or "object" region) Ω = x ׭ distance transform D

0 (. ; M, ׬

as :

Where P

a,b is the set of all possible differentiable paths in ψ between the points a and b and Γ(s) : R  R2 indicates a path, parametrized by its arc length s ׭ derivative

Γ ` (s) = ∂ Γ(s) / ∂s is the unit vector tangent to the direction of the path. The dot-

product is ensuring the maximum influence for the gradient direction of the path Γ. The geodesic factor γ weighs the contribution of the image gradient versus the spatial distances. Figure 4.9 shows the difference between euclidean distance and geodesic distance. Figure 4.9 Euclidean Distance vs Geodesic Distance [Hilaga et al., 2001] Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.

4.6. MANHATTAN DISTANCE

The distance between two points in a grid is based on a strictly horizontal and/or vertical path as opposed to the diagonal. The manhattan distance is the simple sum of the horizontal and vertical components, whereas the diagonal distance might be computed by applying the Pythagorean Theorem [Wikipedia, 2010]. It is also called the L

1 distance and of

u = (x

1 , y1) and v = (x2 , y2) are two points, then the manhattan distance between u and v is

given by ------------------------------------------------ (1) Instead of two dimensions, if the points have n-dimensions, such as a = (x

1 , x2 ,..., xn)

and b = (y

1 , y2 ,..., yn) then, equation (1) can be generalized by defining the manhattan

distance between a and b as Figure 4.10 Euclidean and Manhattan distances on a appendicitis image Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. Figure 4.10 shows euclidean and manhattan distances on an appendicitis image. The yellow lines are representing euclidean and green lines are representing manhattan distance. The Manhattan distance function computes the distance that would be travelled from one data point to the other if a grid-like path is followed and manhattan distance between two items is the sum of the differences of their corresponding components. Figure 4.11 shows the difference between euclidean distance and manhattan distance. Figure 4.11 Euclidean distance vs manhattan distance [Balu et al., 2012]

4.7. CITY BLOCK DISTANCE

The city block distance is always greater than or equal to zero. The measurement would be zero for identical points and high for points that show little similarity. The city- block distance measuring horizontal and vertical directions and the chessboard distance takes diagonal directions. The chamfer distance is faster than the city-block distance and city- block distance largely over estimates distances towards 45 directions. This makes the needed rectangular area around the moving object for the city-block distance than the chamfer distance [Theo E. Schouten et al., 2005]. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.

4.7.1. The City Block Distance Transform

Consider a black and white n x n binary image: i.e. a two dimensional array where a ij =

0 or 1, for i, j = 0, 1, 2, n -1. The index i stands for the row and the index j for column and

pixel (0, 0) is the upper left point in the image. The city block distance transform is to find for each point (i , j ) its city block distance from the set of all black pixels B = { ( i, j) : a ij = 1}.

In other words, authors compute the array

The city block distance transform is a basic operation in computer vision, pattern recognition and robotics. For instance, if the black pixels represent obstacles, then d ij tells us how far the point (i, j) is from these obstacles. This information is useful when one tries to move a robot in the free space hit pixels of the image and to keep it away from the obstacles. Many algorithms have been proposed for computing the distance transform using different distance metrics. Figure 4.12 shows difference between euclidean distance and city block distance. Figure 4.12 Euclidean distance vs city block distance [Sarah et al., 1999] Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.

4.8. CHESS BOARD DISTANCE

The chessboard distance is a metric defined on a vector space where the distance between two vectors is the greatest of their differences along any coordinate dimension. In two dimensions, i.e. plane geometry, if the points P and Q have Cartesian coordinates (x

1, y1)

and (x

2, y2), their chessboard distance is:

D

Chess = max ( | x2 - x1| , | y2 - y1| )

Figure 4.13 shows difference between euclidean distance and chess board distance. Danielsson (1980) asserted that both manhattan and chessboard distance are rarely used. The recent publication of a few transforms use manhattan distance in particular, due to the speed of calculation but result in a coarse solution. Figure 4.14 shows difference between euclidean distance and chess board distance matrix. Figure 4.13 Euclidean Distance vs Chess Board Distance [Sarah et al., 1999] Figure 4.14 Euclidean Distance vs Chess Board Distance Matrix [Antoni Moore, 2002] Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.

4.9. SUMMARY

The relationship and understanding among different distance measures is helpful in choosing a proper measure for a particular application. Various distance measures, euclidean distance, chamfer, geodesic, manhattan, city block and chess board distance are described in detail. This chapter highlighted euclidean distance, how it is useful and described chamfer

distance as available from literature. In addition, this chapter illustrated the difference

between geodesic and euclidean distance and also demonstrated differences between

manhattan and euclidean distance, euclidean and city block distance. Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.

quotesdbs_dbs14.pdfusesText_20

[PDF] types of distance measures in machine learning

[PDF] types of drama pdf

[PDF] types of educational videos

[PDF] types of federal constitutional courts

[PDF] types of flexible work arrangements

[PDF] types of flexible work schedules

[PDF] types of google ads

[PDF] types of introductions pdf

[PDF] types of jurisprudence

[PDF] types of machine language

[PDF] types of operators

[PDF] types of packets in usb protocol

[PDF] types of paragraph with examples pdf

[PDF] types of polynomials

[PDF] types of sentences