Voronoi transformation

Recently, a new class of DT algorithms was proposed. It considers distance transformation as a sub-product of the generation of the Voronoi diagram in the continuous plane. Obviously, the knowledge of the Voronoi diagram, i.e. the knowledge of what is the nearest object pixel for any point in the image plane, is sufficient for a straightforward computation of the DT.

On one hand, working in the continuous plane ensures that the Voronoi Polygons are indeed connected sets, so that none of the problems encountered at section occur. On the other hand, computers are not particularly well-suited for working on continuous (non-discretized) problems. The key to the following algorithms [17,69,44] is that one can efficiently compute the intersection of the Voronoi diagram with a row or a column of the image. This could be seen as a half-way discretization, along one axis and not the other. Because they work row by row, the following algorithms also have similarities with those of the preceding section.

Breu, Gil, Kirkpatrick and Werman [17] first show that, because the image pixels are restricted to a limited-size array, and because they are structured in rows and columns, the Voronoi diagram of the centers of object pixels can theoretically be computed in linear time, i.e. o(mn) for an $n \times m$ image. Then, they show how this can be done row by row, by computing the intersection of any row with the Voronoi diagram. Once again, this is performed in two steps, with an up- and down-scan of the row. Let us consider the up-scan for instance.

During the up-scan, we compute the intersection of every row R with the Voronoi diagram of the object pixels located under R, i.e $p(p_x,p_y) \in O$ with $p_y \leq R$. This intersection is represented as L_R, the list of object pixels p for which VP(p) intersects row R. The method is based on two observations.

• for pixels p and q in the sub-image below row R, if p_x=q_x and p_y > q_y, then VP(q) does not intersect row R.
• for pixels p and q in the sub-image below row R, if p_x < q_x, then VP(p) (VP(q)) lies to the left (right) of the mid-perpendicular between p and q.

From the first observation, we conclude that L_R contains at most one object pixel per column. The object pixels $(p_x,p_y) \in O$ with $p_y \leq R$ and $p_y \geq y \forall (p_x,y) \in O$ are the only candidates C_R to belong to L_R. This list of candidates C_R is easily produced from the candidates C_R-1 and the list of object pixels in row R.

  

Figure 2.12: Voronoi Polygon VP(q) does not intersect line R if $\widehat{pq}_x \geq \widehat{qr}_x$

Using the second observation, we can then trim the list of candidates C_R of pixels q for which VP(q) does not intersect row R. At Figure , VP(q) does not reach row R because p and r hide it. The second observation tells us that, with p_x < q_x < r_x, this will happen if $\widehat{pq}_x \geq \widehat{qr}_x$ where $\widehat{pq}$ ( $\widehat{qr}$) is the intersection of the mid-perpendicular of pq (qr) with row R, i.e. $\widehat{pq}_y = R$ and

$$\widehat{pq}_x = \frac{ q_x^2 - p_x^2 - 2.R.(q_y-p_y) + q_y^2 - p_y^2 }{ 2.(q_x-p_x) }$$ (2.28)

and a similar expression for $\widehat{qr}$. Therefore, pixel $q \in C_R$ will not belong to L_R only if there exists $p,r \in C(R)$ such that p_x < q_x < r_x and $\widehat{pq}_x \geq \widehat{qr}_x$, i.e.

 

$$\geq ( p_x - q_x ) . ( q_x^2 - r_x^2 - 2.R.(q_y-r_y) + q_y^2 - r_y^2 )$$ (2.29)

The procedure to produce the list L_R from the list C_R is then the following. Pixels from C_R are added one by one to L_R. Before actually adding a pixel r to L_R, equation () is checked with q the last pixel in L_R and p the preceding one. The last pixel of L_R is removed iteratively until () is not satisfied anymore or until L_R only contains one pixel. Then only, r is added at the end of L_R.

Because each pixel is added or removed at most once in the process, creating L_R from C_R is a linear complexity operation. Allocating each pixel along the row to the correct VP knowing L_R is then also a linear-complexity operation, because VPs along row R and object pixels in L_R are ordered in the same way. Therefore, Breu's DT has global linear complexity.

Guan and Ma [69] adapt the above algorithm to another data representation. Instead of using L_R that contains the list of object pixels whose VP intersect row R, they consider an equivalent list of segments that partition row R between the VPs. The main improvement of the method is that they use L_R-1 to produce L_R instead of using the row-to-row redundancy only when producing C_R. This reduces the computational time significantly for sparse object images.

For an $m \times n$ image with t object pixels, this method has a complexity in $\alpha . \mathrm{O}(mn) + \beta . \mathrm{O}(\sqrt{mnt})$. The O(mn) term corresponds to the computation of the DT from the segments lists. The O $(\sqrt{mnt})$ term corresponds to the creation of the segments lists. Because of the complexity of the computations involved (typically ), this second term is dominant unless the object image is extremely sparse. For some images he considers, this step can be up to 30 times slower than the O(mn) step.

Finally, as announced in section , Embrechts and Roose [44] use similar techniques to implement Danielsson's 4SED algorithm on multi-processors machines. The image is divided into sub-images, one per processor. In order to be able to apply 4SED, each processor needs to know two things. First the location of the object pixels inside its own sub-image, secondly the object pixels from other sub-images that influence it, i.e. the intersection of the border of its sub-image with the Voronoi diagram of the whole object image.

The intersections of the Voronoi diagram of the object pixels in the sub-image with the sub-image borders are first computed by each processor using a technique somewhat similar to Breu's. From these, the intersections of the complete Voronoi diagram with the sub-image borders are computed, using a number of merging and splitting rules. This merging and splitting is the only step requiring communication between the processors.

Embrechts and Roose find that it is possible to reach a good parallel efficiency (typically $80\%$) as soon as the image size is sufficiently large, i.e. as soon as the cost of the Voronoi diagram computations on the sub-image borders becomes negligible compared to the 4SED algorithm.