Constant-Working-Space Algorithm for Euclidean Distance Transform

摘要

2値画像が与えられたとき，値1の画素それぞれから最も近い0画素までのユークリッド距離（の2乗）を求めるのがユークリッド距離変換である.本論文では，画像を蓄える行列以外には定数サイズの作業領域しか使わずに線形時間でユークリッド距離変換を実行するためのアルゴリズムを提案する.実行結果および既存のアルゴリズムとの比較についても触れる.%Given a binary image, Euclidean distance transform is to compute for each pixel the Euclidean distance to the closest 0-pixel. This paper presents a linear-time algorithm for Euclidean distance transform using only constant amount of working space in addition to an image matrix. Implementation results and comparisons with existing algorithms are also included.