著者

浅野 哲夫 セルゲイ ベレグ

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.2013, no.20, pp.1-8, 2013-05-10

---

n画素からなる2値画像が与えられたとき,連結成分ごとに異なる整数ラベルを付ける問題に対して新たなアルゴリズムの枠組みを与える.O(n)の作業領域が利用できるならO(n)時間でラベル付けは可能である.ここでの問題は,実行時間を余り増やさずに作業領域を削減できるかである.本文では,省メモリのアルゴリズムを提案する.具体的には,入力画像は読み出し専用メモリで与えられるものとし,O(√n)の作業領域だけを用いてO(n log n)時間でラベル付けを行うアルゴリズムを提案する.さらに,応用についても述べる.