ユークリッド距離変換アルゴリズムの効率化

加藤 敏洋  平田 富夫  斉藤 豊文  吉瀬 謙二  

誌名
電子情報通信学会論文誌 D   Vol.J78-D2    No.12    pp.1750-1757
発行日: 1995/12/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1923
論文種別: 論文
専門分野: 画像・パターン認識,コンピュータビジョン
キーワード: 
距離変換,  画像処理,  ユークリッド距離,  並列アルゴリズム,  

本文: PDF(604.9KB)>>
論文を購入



あらまし: 
本論文では,サイズがN×Nの2値画像のユークリッド距離変換をO(N 2)時間で実行するアルゴリズムを与える.距離変換とは,入力として与えられた2値画像の各画素についてそこから最も近い0画素への距離を求める処理で,ディジタル画像処理における基本的な処理である.このアルゴリズムは,4近傍距離や8近傍距離などユークリッド距離以外の他の距離についてもアルゴリズム中の距離関数を置き換えるだけで距離変換が実行でき,その意味で一般的な距離変換アルゴリズムとなっている.また,p(1≦pN)台のプロセッサを用意すればO(N2/p)時間の並列アルゴリズムが得られ,これまでの並列アルゴリズムより効率が良い.