Independent scanning

In his founding article [132], Rosenfeld proposes an alternative approach to the generation of the city-block (dist_CB) distance transformation. The N-dimensional problem is decomposed into N 1-dimensional sub-problems. In 2D, the distance from the nearest pixel is first computed in each row independently. Then, these values are used to compute the distances in each columns. With the dist_CB metric, as defined in eq. , both sub-problems have an identical solution: applying the $[ \; 1 \; 0 \; 1 \; ]$ mask back and forth. Paglieroni [118] and Saito and Toriwaki [140] show that a similar approach can be used with the Euclidean metric.

Paglieroni [118] develops a ``unified'' DT algorithm, valid for any metric M that satisfies

 

dist_M(p,q) = f( |p_x-q_x| , |p_y-q_y| ) (2.27)

$$\Rightarrow f( \vert dp_{1x}\vert , \vert dp_y\vert ) \leq f( \vert dp_{2x}\vert , \vert dp_y\vert )$$ |dp_1x| < |dp_2x|

$$\Rightarrow f( \vert dp_x\vert , \vert dp_{1y}\vert ) \leq f( \vert dp_{x}\vert , \vert dp_{2y}\vert )$$ |dp_1y| < |dp_2y|

which is true for all the metrics defined in section , including the Euclidean one. The ``row'' scan goes back-and-forth across each row and determines the ``nearest object pixel within the row'' (NOPwR). The key to the algorithm of course relies on the up-and-down column scan.

From equations , one can deduce that if the 2D nearest object pixel from pixel p(p_x,p_y) is pixel q(q_x,q_y), then q is the NOPwR of pixel (p_x,q_y), in the same column as p and the same row as q. Therefore, checking all NOPwRs in column p_x guarantees to find the 2D nearest pixel for p. Paglieroni implements this check with an up-and-down scan over each column. He applies a few simple tests to restrict the number of NOPwRs to consider for each pixel.

  

Figure 2.11: Independent scanning. Left: After left-right scan Right: up-and-down scan, finding the value for D(p) by scanning column p_x.

Saito and Toriwaki [140] particularize Paglieroni's algorithm to the Euclidean metric, in order to restrict further the number of rows to consider for each pixel in the column scans, and therefore reduce the overall computational cost.

Let us consider the column p_x after the ``row'' scan. Pixel (p_x,y) in row y of that column contains the value R(y)=(p_x-q_x(y))² where q(y) is the NOPwR of (p_x,y). During the up-scan along the column, we want to know to which pixels (p_x,p_y) we should propagate the information from (p_x,y). Saito first notices that if $R(y) \geq R(y+1)$, then the information from row y should not be propagated upwards since dist_E(p,q(y)) = R(y) + (p_y-y)² > dist_E(p,q(y+1) = R(y+1) + (p_y-y-1)² for any p(p_x,p_y) with $p_y \geq y+1$. On the other hand, if R(y) < R(y+1), then the information from row y should propagate up to y_max = y+(R(y+1)-R(y)-1)/2, the value for which dist_E(p,q(y)) > dist_E(p,q(y+1)). Therefore, in the up-scan part of Saito's algorithm, pixel (p_x,y) is propagated to (p_x,y+i) until either $R(y) \geq R(y+i)$ or y_max is reached. The down-scan proceeds similarly.