Chamfering.

Chamfer distance transformations are relying 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 neighbors. This assumption is correct for regular metrics [131], i.e. metrics for which

For all p,q such that $dist_M(p,q) \leq 2$, there exists an r different from p and q such that dist_M(p,q)=dist_M(p,r)+dist_M(r,q).

This property is true for the city-block (), chess-board () and chamfer () metrics - among others - but not for the Euclidean one when pixels p,q,r are restricted to locations on an integer grid.

Chamfer DTs were developed and studied by Rosenfeld and Pfaltz [132,133], Montanari [109], Barrow [3], Borgefors [10,12], Piper and Granum [122], Forchhammer [56], Verwer, Verbeek and Dekker [167], Sharaiha and Christofides [145] and Coquin and Bolon [22].

Rosenfeld [132,133] proposes raster scanning (see below) and independent scanning (see section ) algorithms for the distance transformation using the dist₄ and dist₈ metrics. Montanari [109] investigates distances defined as the length of the shortest path between two pixels. If the path is restricted to steps between 4-direct neighbors, this is equivalent to the dist₄ metric. With 8-direct neighborhoods, it defines a $dist_{cha(1:\sqrt{2})}$ metric. Montanari proves that the shortest path between two points consists of at most two types of steps, those with orientations closest to the Euclidean vector between those points. This property is central to the later publications by Borgefors [10] and Ragnelmam [127]. Barrow [3] uses a DT similar to Montanari's, replacing $(1:\sqrt{2})$ by (2:3), an integer approximation.

In [10], Borgefors reviews a number of metrics in 2 and 3 dimensions. Chamfer distance transformations are produced in two raster scans over the image, using the masks of Figure . In the forward scan, the mask starts in the upper left corner of the picture, moves from left to right and from top to bottom. In the backward scan, it starts in the lower right corner, moves from right to left and from bottom to top. The local distances, d₁ and d₂, in the mask pixels are added to the pixel values in the distance map and the new value of the zero pixel is the minimum of the five sums.

  

Figure 2.2: Masks used by chamfer DT algorithms, in 2 (left) and 3 (right) dimensions

This algorithm can produce distance transformation with several metrics. For instance, for d₁=1 and $d_2=\infty$, we have the city block metric; for d₁=d₂=1, the chess board metric, for d₁=1 and $d_2=\sqrt{2}$, Montanari's metric and for d₁=2 and d₂=3, Barrow's approximation. Borgefors computes the optimal values for d₁ and d₂ in order to minimize the maximal difference between the chamfer metric and the Euclidean one. Assuming that $d_2 < 2 \, d_1$ (otherwise the diagonal direction is never used), the distance between two pixels is

 

dist_cha(d1:d2)(p,q) = m₂ . d₂ + ( m₁ - m₂ ) . d₁ (2.14)

where m₁ = | q_x - p_x | and m₂ = | q_y - p_y |, using Borgefors' notations, and $m_1 \geq m_2$ (otherwise, m₁ and m₂ change places in ()). The difference between the Euclidean and chamfer distance is thus

$$\sqrt{m_1^2 + m_2^2} - m_2 . d_2 - ( m_1 - m_2 ) . d_1$$ (2.15)

If we set d₁ = 1 and d₂ = d < 2, the optimal d can be found by minimizing the maximum of (). The maximum occurs either for m₂ = 0, m₂ = m₁ or the value of m₂ where the differential is 0. For m₂ = 0, () is zero. For m₂ = m₁, () becomes

$$( \sqrt{2} - d ) M$$ (2.16)

where M=m₁=m₂. The differential of () with respect to m₂ is zero for $m_2 = ((d-1)/\sqrt{2d-d^2}) . m_1$. Substituting this value in (), we find

$$( \sqrt{2d-d^2} - 1 ) M$$ (2.17)

where M=m₁. The minimum of the absolute maximum of and happens when they cross each other at $d = 1 / \sqrt{2} + \sqrt{\sqrt{2}-1} \approx 1.351$. The upper limit for () is then $(1/\sqrt{2} - \sqrt{\sqrt{2}-1}) . M \approx 0.06 M$. Slightly better results could actually be obtained by removing the constraint that d₁=1, as in [166], but this is beyond the scope of the present review.

For computational efficiency, floating point operations are not desirable, and therefore Borgefors suggests to use the sub-optimal integer approximation d₁=3 and d₂=4, then to divide the resulting DT by 3. In this case, the upper limit for the difference between the Euclidean and chamfer metric becomes $\sqrt{2}-4/3 \approx 0.08M$. This is obviously much better than the limits found for the city-block and chess-board metrics, $(\sqrt{2}-2)M \approx -0.59M$ and $(\sqrt{2}-1)M \approx 0.41M$, respectively.

In 3 dimensions, the optimal values are d₁=1, $d_2 = (\sqrt{3}+1+\sqrt{2\sqrt{3}-2})/3 \approx 1.314$ and $d_3 = (2\sqrt{3}-1+2\sqrt{2\sqrt{3}-2})/3 \approx 1.628$, which gives $((\sqrt{3}+1-2\sqrt{2\sqrt{3}-2})/3)M \approx 0.10M$ for the upper limit of the absolute difference between the metrics. Once again, it is often better to consider a sub-optimal integer approximation with d₁=3, d₂=4 and d₃=5. The upper limit of the difference with the Euclidean metric is then $( \sqrt{7}/3-1)M \approx -0.12 M$.

In [12], Borgefors extends the chamfer masks to $5 \times 5$ and $7 \times 7$. She computes the optimal values for the local distances and evaluates several integer approximations for $3 \times 3$ to $7 \times 7$ masks. She recommends using (3:4) and (5:7:11) approximations for $3 \times 3$ and $5 \times 5$ masks, but finds no significant interest in using $7 \times 7$ masks. The gain in precision becomes negligible compared to the additional cost of using larger masks. With chamfer (5:7:11), the upper limit for the absolute difference between this metric and the Euclidean one is reduced to 0.02 M. The chamfer (5:7:11) DT is illustrated at Figure .

  

Figure: The chamfer (5:7:11) DT. Left: forward and backward masks. Center: result after forward scan applied on the original image of figure . Right: final result.

Piper and Granum [122] and Verwer et al. [167] propose to reach the same results with a different type of scanning. Instead of two raster scans, they use a propagation from the object pixels to the rest of the image. This proves to be more efficient on non-convex image domains, and will be further explained in section .

Sharaiha and Christofides [145] propose a graph theoretic approach to chamfer distance transformation. They represent the image as a graph where pixels are represented as vertices and adjacency relations as arcs. The cost associated with each arc is equal to the equivalent local distance in the chamfer masks. The vertices associated to the object pixels are called root vertices. The Chamfer DT problem is then equivalent to the shortest path forest problem in graph theory. They solve this using a variation of the algorithms proposed by Moore [110] and Dial [39]. Practically, this is similar to Piper's approach [122], with a more complex data representation.

In [56], Forchhammer shows that, within a limited distance, the true Euclidean distance can be deduced from its chamfer approximation. In particular, using the $3 \times 3$ mask with (3:4) local distances, the exact EDT can be deduced from the chamfer distances for $D(p)<\sqrt{17}$, but not beyond.

Finally, Bolon [9] and Coquin [22] extend the chamfer metrics to anisotropic grids. The optimal mask coefficients are found by minimizing the maximum of the difference between the anisotropic chamfer metric and the Euclidean along a circle. The complete solution is given for $5 \times 5$ anisotropic masks, but can be applied to other masks as well.