An O (n) Connected - Component Labelling Algorithm for Two Dimensional n×n Images Based on the Divide -and- Conquer Programming Technique

IPSJ

Bibliographic Information

Other Title
  • 分割統治法に基づいた線形時間・画像連結要素ラベリング・アルゴリズム

Search this article

Description

近年のハードウェア価格の低下とともに 種々のアーキテクチャをもつ並列画像処理装置が開発され それらの上で動作する数多くの並列画像処理アルゴリズムが提案されている.本稿では 従来から高速アルゴリズム設計法の一つとして知られている分割統治法を並列画像処理アルゴリズム設計に適用し 完全並列型プロセッサの一種と考えられるメモリ付きセルラオートマトン上で 線形時間で動作する連結要素ラベリング・アルゴリズムを提案する.連結要素のラベリングは 本来逐次的な性質ゆえにその並列化が困難なものと考えられてきた.本演算に関しては 自明な面積時間アルゴリズムが知られているだけで 線形時間アルゴリズムの存在については 理論的にも興味ある未解決問題として残されていたものである.時間計算量の減少とともに プロセッサ当りのハードウェア量が増大し 実用化という観点からはさらに改良を重ねる必要がある.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top