2値画像の重みつき距離変換を行なう並列アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
白黒2値画像の距離変換とは,各画素について最も近い黒画素までの距離を求める処理である。また, 白黒2値画像の最近点変換とは, 各画素について最も近い黒画素の座標を求める処理である。本稿では, 重みつき距離を用いて, 距離変換及び最近点変換を行なう並列アルゴリズムを示す。このアルゴリズムはn×nの入力画像に対して, EREW PRAM上ではO(log n)時間, n^2/log nプロセッサで実行でき,common CRCW PRAM上では, O(loglog n)時間,n^2/loglog nプロセッサで実行できる。また, p^2プロセッサのメッシュモデル,ハイパーキューブモデル上ではO(n^2/p^2+n)時間, O(n^2/p^2+(nlog p)/p)時間でそれぞれ実行できる。これらの結果より, このアルゴリズムはPRAM, メッシュモデル(1≤p≤√<n>,および,ハイパーキューブモデル(1≤p≤n/log n)上でコスト最適である。
1996-10-17

著者

関連論文

もっと見る

スポンサーリンク