2値画像の連結成分にラベル付けするための新たな方式

• 浅野 哲夫

  北陸先端科学技術大学院大学情報科学研究科

• セルゲイ ベレグ

  Department of Computer Science, University of Texas at Dallas

書誌事項

タイトル別名

• A New Framework for Connected Components Labeling of Binary Images

抄録

n画素からなる2値画像が与えられたとき,連結成分ごとに異なる整数ラベルを付ける問題に対して新たなアルゴリズムの枠組みを与える.O(n)の作業領域が利用できるならO(n)時間でラベル付けは可能である.ここでの問題は,実行時間を余り増やさずに作業領域を削減できるかである.本文では,省メモリのアルゴリズムを提案する.具体的には,入力画像は読み出し専用メモリで与えられるものとし,O(√n)の作業領域だけを用いてO(n log n)時間でラベル付けを行うアルゴリズムを提案する.さらに,応用についても述べる.
Given a binary image of n pixels, assign integral labels to all pixels so that any background pixel has label 0 and any two foreground pixels have the same positive integral labels if and only if they belong to the same connected components. This problem is referred to as 'Connected Components Labeling' and it is one of the most fundamental problems in image processing and analysis. This paper presents a new algorithmic framework for the problem. Prom an algorithmic point of view, the problem can be solved in 0(n) time and 0(n) space. We propose new algorithms which use smaller work space without much sacrifice of the running time. More exactly, assuming that an input binary image is given on a read-only array, our algorithm outputs correct labels in the raster order in O(n log n) time using only 0(√n) work space. Some applications of the algorithm are also given.

収録刊行物

• 情報処理学会研究報告. AL, アルゴリズム研究会報告

  情報処理学会研究報告. AL, アルゴリズム研究会報告 2013 (20), 1-8, 2013-05-10

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

詳細情報

• CRID: 1573950402684290048
• NII論文ID: 110009579696
• NII書誌ID: AN1009593X
• ISSN: 09196072
• 本文言語コード: en
• データソース種別:
  • CiNii Articles