|
画像処理に関する研究 −◎−◎−◎−アメリカ・シカゴ大学鈴木研究室との共同研究 −◎−◎−◎− |
パターン認識やコンピュータビジョンにおいて，2値画像中の対象物（連結成分）に別々のラベルを付けるラベル付けは， 最も基本的かつ重要な処理の１つ であり，コンピュータに対象物を認識させる上で欠くことができない．ラベル付けは，エッジ検出やノイズ平滑化などの他の基本的画像処理手法と比べて演算時間が長いため，これらを組み合わせて構成されるパターン認識システムにおいて，そのオンライン実時間実現を妨げる決定的な要因となっていた．これはパターン認識システムにおけるラベル付け手法のボトルネック問題と呼ばれている．これまでに多くのラベル付けアルゴリズムが提案されており，次の4種類が代表的である． (A) マルチ走査アルゴリズム．これらのアルゴリズムは 逐次局所処理により図形上でラベルを伝播させ，画像の走査を複数回行う ことによりラベル付けを行う．N×N画素の画像では，最悪の場合にN-2回の走査が必要である． (B) 2回走査アルゴリズム．これらのアルゴリズムは ラベルの連結性を記憶する1次元もしくは2次元テーブルを利用し， 画像走査中または走査後にテーブル解析を行うことにより， 2回の画像走査によりラベル付けを行う．複雑なテーブル解析が一般的に必要である． (C) ハイブリッドアルゴリズム． このアルゴリズムは分類(A)と(B)のアルゴリズムの利点を 組み合わせたものである． 分類(A)と(B)のアルゴリズムより高速であり，最大4回の走査で完全なラ ベル付けを完了することが実験的に確認されている. (D) 輪郭追跡アルゴリズム．このアルゴリズムは 走査中に発見した対象物の輪郭を追跡することにより ラベル付けを行う．画像の走査が不規則となるため，並列処理，ハードウェア実装，オンライン実時間処理に 向かない． 我々は， 新しい2回走査ラベル付けアルゴリズム[1]を提案した．提案したアルゴリズムでは，同等 ラベル集合と代表ラベルテーブルを用いて 暫定ラベル間の連結性の解析を行うことにより高速なラベル付けを実現する． 本アルゴリズムはラスタ走査型である分類(A)，(B)，(C)中最速のハイブリッドアルゴリズム に較べ， 走査回数が少なく， 連結性解析も効率的であ る．また， 輪郭追跡アルゴリズムより，原理的に単純であり 実装し易い上， 並列化にも拡張し易い．風景画像，航空画像，人物画像， 静物画像，指紋画像，スナップ画像およびテキスト画像を含む50種類の自然画像， 医用画像，テクスチャ画像，テストパターン画像およびノイズ画像など様々な 性質の画像を用いた比較評価実験により，本アルゴリズムの有効性を示した．  画像サイズに対するラベル付けの実行時間  各種性質の画像に対するラベル付けの実行時間  他の基本的な画像処理手法との実行時間（ミリ秒）の比較 画像上において同じ行にある連続した対象物画素のブロックを 連と呼ぶ． データ圧縮方法には連に基づいた（例えば，ＪＰＥＧ）方式がある．我々は連に基づいた2回走査 ラベル付けアルゴリズムを始めて提案した[2]． 第一走査により獲得連の情報をキューに保存しその後の連結性解析に用いる．連を 用いることで同じ画像において暫定ラベルの数が減少することにより，暫定ラベルの連結性 の解析に関わる計算も減少する．これによって，効率を実現している．画像データが連 に基づいている場合，非常に効率であることが確認した．  画像サイズに対する仮ラベルの数  画像サイズに対するラベル付けの実行時間 [1] Lifeng He, Y. Chao, K. Suzuki, A Linear-Time Two-Scan Labeling Algorithm, 2007 IEEE International Conference on Image Processing (ICIP), pp.xxx-xxxx, 2007年9月, San Antonio, Texas, USA. [2] Lifeng He, Y. Chao, K. Suzuki, A Run-based Two-Scan Labeling Algorithm, Lecture Notes in Computer Science series (LNCS), Vol.xxxx, pp.xxx-xxx, Spring-Verlag, 2007年8月. To be continued ............To be continued ............ |
