Dynamic algorithm for constructing discrete Voronoi diagrams
Raul E. Sequeira, Françoise J. Prêteux · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1996
The problem of image segmentation is addressed via the Voronoi diagram (VD). The set of seeds, which determine the Voronoi regions, can be modified by adding and removing seeds. These modifications can be governed by user-specified constraints, but can also be driven by 'salt-and-pepper' noise. The VD, seen as a segmentation operator, is unstable to this kind of perturbation. A dynamic algorithm for the construction of discrete VD, exploiting the local dependence of the diagram on each seed, is presented. The updates in the diagram are made inside a convex set obtained by mapping seeds to linear inequalities; the updates in the neighbor relationships are done using a version of the incremental method.