Two fast euclidean distance transformations in Z2 based on sufficient propagation

Two new error-free sequential Euclidean distance transformations (EDT) for binary images in Z(2) are introduced: sufficient d(1)-propagation and sufficient d(infinity)-propagation. Both methods use ordered propagation, i.e. iterative propagation via contour pixels, However, we restrict the propagation to unique shortest Euclidean paths, the sufficient propagation paths. Moreover, we ensure error-free direct pixel update by adding a distance suggestion to each propagation pixel. Using these ideas, we avoid many unneccesary calculations. The computational tests show that our algorithms, used as signed and as unsigned methods, are significantly faster than other well-known signed and unsigned EDTs. Comparing both methods, sufficient d(infinity)-propagation yields the better average performance. (C) 1998 academic Press.