labeling_source labeling_result

画像の連続した領域をラベリング(連結成分抽出とも言います。英語だと Connected Component Analysis, Connected Component Labeling と呼ばれることが多いようです)するルーチンです。C++のクラス化してあります。

サイズの大きい順に領域番号を付けていくことができます。またサイズが閾値よりも小さい領域を除去できます。多値にも対応しています。

ダウンロード

性能

SD画像(640×480,領域数68,下図左): 2.41msec

HD画像(1920×1080,領域数5084,下図右): 34.7msec

CPU: Intel Core i7-920 (ただしシングルスレッド), Memory: 3GB, Microsoft Visual Studio 2008

labeling_result_sd labeling_result_hd

動作環境

C++。STL(Standard Template Library)が使えること。Visual Studio 2008 (windows) で動作確認済みである。

ラベリングクラスの使用法

ダウンロード

Labeling.h をダウンロードし、使用したいプログラムソースがあるディレクトリに保存して下さい。

インクルード

ソースコードに

#include "Labeling.h"

を記入して下さい。

入力・出力

入力として処理対象画像を与えます。画像はグレイスケール(各画素1バイト)です。

下図の順序でデータが並んでいることを前提にしています(極めて一般的な配置です)。

labeling_image_memory

入力画像の画素値については、0は背景(ラベリング対象外)、1以上が対象画素です。
普通は二値化した画像を入力すると思いますが、仕様としては、0以外の異なる値はそれぞれ異なる領域として扱っています。

出力画像の各画素値には連結領域番号が入ります。0は背景を示します。連結領域番号は 1, 2, … と順に振られます。

実行

連結領域抽出の処理本体である Labeling クラスと、各連結領域に関する情報を格納する RegionInfo クラスは、C++のテンプレート機能を用いて様々な型に対応できるように作られています。

入力画像の各ピクセル値は unsigned char 型が一般的だと思います。出力の連続領域番号は short 型に格納することを推奨します。

この場合に対応するクラスとして LabelingBS クラス / RegionInfoBS クラスが typedef により定義されています。詳しくは Labeling.h の末尾を見て下さい。以下の説明では LabeingBS クラス / RegionInfoBS クラスを使用します。

まず、LabelingBS クラスのインスタンスを作成します(何のこっちゃ、という人へ。要は変数宣言です)。

LabelingBS	labeling;

入出力画像のバッファは適宜用意して下さい。例えば、

int w = 640;
int h = 480;
unsigned char *src = new unsigned char[ w * h ];
short *result = new short[ w * h ];

などとしてメモリを確保した上で、src に二値化した画像を格納します。

ラベリング処理を実行する際には6個の引数を指定します。

labeling.Exec( src, result, w, h, true, 30 );

引数は順に以下の通りです。

  1. 入力画像の先頭アドレス(unsigned char *)
  2. 出力画像の先頭アドレス(short *)
  3. 画像の幅(int)
  4. 画像の高さ(int)
  5. 領域の大きさ順にソートするか(bool) – true:する false:しない
  6. 消去する小領域の最大サイズ(int) – これ以下のサイズの領域を消去する

処理結果は result (が指す画像バッファ)に格納されます。

各連結領域の情報は labeling 内に保持されており、メソッドを通じて取り出すことができます。この情報は、別の画像に対して labeling.Exec() を実行すると上書きされます(LabelingBS クラスのインスタンスを別途作成すればこの限りではありません)。

結果の取り出し

前述の通り、処理結果自体は result に格納されます。各連結領域に関する情報は以下のメソッドにより取り出せます。(メソッドとは何だという人へ。クラス専用関数です)。

連結領域数(消去された小領域の数を含まない)の取り出し
int n = labeling.GetNumOfResultRegions();
各連結領域に関する情報の取り出し

連結領域に関する種々の情報は RegionInfoBS クラスに格納されます。

注意!!!! 結果画像に格納されている領域番号は1から始まりますが、GetRegionInfo への引数は 0 から始まります。変な仕様ですみません。

まず対象とする領域の情報が格納された RegionInfoBS へのポインタを得ます。

RegionInfoBS	*ri;
ri = labeling.GetResultRegionInfo( 0 );

RegionInfoBS には以下のメソッドが用意されています。

  • 画素数を返す 
    int GetNumOfPixels( void )
  • 領域中央の座標(!=重心) を返す 
    void GetCenter( float& x, float& y )
  • 領域のサイズを返す 
    void GetSize( int& x, int& y )
  • 領域の左上座標を返す 
    void GetMin( int& x, int& y )
  • 領域の右下座標を返す 
    void GetMax( int& x, int& y )
  • 領域の重心を返す 
    void GetCenterOfGravity( float& x, float& y )
  • 領域の入力バッファにおける値を返す 
    SrcT GetSourceValue( void )
  • 領域の連続領域番号を返す 
    DstT GetResult( void )

引数の int& や float& は変数の参照渡しという C++ の機能です。
詳しい内容は C++ の入門書にゆずります。
あるいはこちら。

SrcTはここでは unsigned char、DstTは short です。

例として、領域のサイズを得る方法を以下に示します。

int size_x, size_y;
ri->GetSize( size_x, size_y );
cout << "size: " << size_x << "," << size_y << endl;

注意

Visual Studio で使用する際には、Debug と Release で速度に非常に大きな
差がありますので注意して下さい。基本的には Release 環境で使用して下さい。

より詳しい解説

より詳しい解説(PDF)

ライセンスについて

何件かお問い合わせをいただきましたので、ライセンスについて表記しておきます。

Labeling.h は修正BSDライセンスのもとで配布いたします。

  • 商用であってもお使いいただいて結構です。
  • 使用していただくにあたって費用は発生しません。
  • 不具合については補償できませんのでご了承下さい。
  • 著作権表記については “Copyright (c) 2010, IMURA Masataka” と記載してください。

商用でご使用いただく際には、可能でしたらご一報いただけると嬉しく思います。

Copyright (c) 2010, IMURA Masataka.
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

連絡先

バグ報告・要望は井村まで。