The equivalence of the chessboard distance transform and the medial axis transform^∗

^∗ The correspondence address is: Prof. Shi-Jinn Horng, Department of Electrical Engineering, National Taiwan Institute of Technology, 43, Section 4, Kee-Lung Road, Taipei, Taiwan, R. O. C. Tel:[phone], FAX:[phone]. [email protected] or horng@mouse. ee. ntit. edu. tw.

Abstract

The distance transform (DT) and the medial axis transform (MAT) are two image computation tools used to extract the information about the shape and the position of the foreground pixels relative to each other. The DT converts a binary image into an image, where each pixel has a value to represent the distance from it to its nearest foreground pixel. The MAT of an image is a set of maximal squares that represents the foreground pixels of an image. Extensively applications of these two transforms are used in the fields of computer vision and image processing, such as expanding shrinking, thinning and computing shape factor etc. There are many different distance transforms based on different distance metrics. The chessboard distance transform (CDT) is one kind of distance transform (DT) which converts an image based on the chessboard distance metrics. In this paper, we first demonstrate that both transforms (i.e. MAT and. CDT) are interchangeable. Then the corresponding algorithms are also proposed. That is, the MAT can be found by ultilizing a CDT algorithm and vice versa. That is also true in any computation models.

Keywords:

• Algorithms
• computer vision
• distance transform
• image processing
• medial axis transform
• parallel algorithm

C. R. Categories:

• I 4.5
• F 2.2

^∗ The correspondence address is: Prof. Shi-Jinn Horng, Department of Electrical Engineering, National Taiwan Institute of Technology, 43, Section 4, Kee-Lung Road, Taipei, Taiwan, R. O. C. Tel:[phone], FAX:[phone]. [email protected] or horng@mouse. ee. ntit. edu. tw.

^∗ The correspondence address is: Prof. Shi-Jinn Horng, Department of Electrical Engineering, National Taiwan Institute of Technology, 43, Section 4, Kee-Lung Road, Taipei, Taiwan, R. O. C. Tel:[phone], FAX:[phone]. [email protected] or horng@mouse. ee. ntit. edu. tw.

Notes

^∗ The correspondence address is: Prof. Shi-Jinn Horng, Department of Electrical Engineering, National Taiwan Institute of Technology, 43, Section 4, Kee-Lung Road, Taipei, Taiwan, R. O. C. Tel:[phone], FAX:[phone]. [email protected] or horng@mouse. ee. ntit. edu. tw.