ラベリング

　ビットマップイメージの中の図形データーに番号を振るのを、ラベリングと言うらしいのですが、このラベリング処理によって、輪郭追跡、面積の取得が非常に簡単になります。
実際のプログラムのアルゴリズムは、イメージ配列の左上から、スキャン検出し、最初に検出した番号の振っていない図形に、８方向番号塗りつぶしを実行すれば良いことになります。
ラベリングは、２値化データーにより行いますが、８ビットの場合、＄００と、＄ＦＦは、白と黒として使用済みなので、＄０１～＄ＦＥ迄（１～２５４）をラベルとして使用します。
そうすると、ラベリングした図形を表示した時、簡単に色分けして表示することが出来ます。
図形の数が２５４個以上ある場合は、１６ビットカラーを使用しても良いですが、１ビット毎の差では、色の見分けが付かないので、図形ごとの色のビット差を大きくする必要があります。

左図の様に図形に番号を付けます。
一連の繋がった図形が、同じ番号になります。
実際には、画面上には番号は表示できません、色分けして表示します。

通常の塗りつぶしは、４方向検索ですが、ラベリングの場合は、８方向検索となります。
塗りつぶしの方法は、画像処理（輪郭追跡と塗りつぶし）を参照して下さい。

var
  XX, YY : integer;                  // for loop 用 ポインター計算用
  FN : Byte;                         // byteデーター
  ArPosi : integer;                  // 配列長さ
  PushPopAryX : array of cardinal;  // X座標用配列
  PushPopAryY : array of cardinal;  // y座標用配列

// ブッファ末尾追加
procedure Push(X1, Y1: integer);
begin
  ArPosi := ArPosi + 1;           // 配列長さ１加算
  SetLength(PushPopAryX, ArPosi); // x配列長さセット
  SetLength(PushPopAryY, ArPosi); // y配列長さセット
  PushPopAryX[ArPosi - 1] := X1;  // 配列の最後にX位置書き込み
  PushPopAryY[ArPosi - 1] := Y1;  // 配列の最後にY位置書き込み
end;

// ブッファ末尾抜き出し
procedure PoP(var X, Y: integer);
begin
  X := PushPopAryX[ArPosi - 1];             // X最後の位置のデーター取り出し
  Y := PushPopAryY[ArPosi - 1];             // Y最後の位置のデーター取り出し
  if ArPosi > 0 then ArPosi := ArPosi - 1;  // 配列長さ１減算
  SetLength(PushPopAryX, ArPosi);           // x配列長さセット
  SetLength(PushPopAryY, ArPosi);           // y配列長さセット
end;

// ラベルリングか確認 ラベルリングされてなかったらTrue を返します
function OnPaint(X2, Y2: integer): boolean;
begin
  Result := False;
  if NumberingD[Y2, X2] = $00 then Result := True;
end;

// ラベルリング場所検索 ラベリングなかったら 配列の最後に座標追加 （通常の塗りつぶしに斜め方向を追加したもの）
procedure pushPixel(X, Y: integer);
begin
  // 次の４行はラベリング用として斜め方向追加部分
  if (X - 1 >= 0)     and (Y - 1 >= 0)     then if OnPaint(X - 1, Y - 1) then Push(X - 1, Y - 1);  // 左上
  if (X + 1 < BWidth)  and (Y - 1 >= 0)     then if OnPaint(X + 1, Y - 1) then Push(X + 1, Y - 1);  // 右上
  if (X + 1 < BWidth)  and (Y + 1 < Bheight) then if OnPaint(X + 1, Y + 1) then Push(X + 1, Y + 1);  // 右下
  if (X - 1 >= 0)     and (Y + 1 < Bheight) then if OnPaint(X - 1, Y + 1) then Push(X - 1, Y + 1);  // 左下
  // ここから下は塗りつぶしと同じ
  if X - 1 >= 0     then if OnPaint(X - 1, Y) then Push(X - 1, Y);   // 左端を越えなかったら左側チェック
  if X + 1 < BWidth  then if OnPaint(X + 1, Y) then Push(X + 1, Y);   // 右端を越えなかったら右側チェック
  if Y - 1 >= 0     then if OnPaint(X, Y - 1) then Push(X, Y - 1);   // 上端を越えなかったら上側チェック
  if Y + 1 < Bheight then if OnPaint(X, Y + 1) then Push(X, Y + 1);   // 下端を越えなかったら下端チェック
end;


// ラベリング
procedure Nopainting(Y, X: integer);
begin
  ArPosi := 0; // 配列長
  SetLength(PushPopAryX, ArPosi);             // Ｘ座標配列長さをゼロにする
  SetLength(PushPopAryY, ArPosi);             // Ｙ座標配列長さをゼロにする
  NumberingD[Y, X] := FN;                     // 最初の位置ラベル番号に変更
  while True do begin                       // ラベルリングルーチン
    // ラベルリングの対象の検索
    pushPixel(X, Y);                          // ８箇所周囲検索配列データー末尾に追加
    // ラベルリング対象が無いなら終了
    if Length(PushPopAryX) = 0 then break;
    // バッファから塗りつぶし指定場所取り出し
    Pop(X, Y);                                // 配列データー末尾から座標抜き出し
    // ラベルリング
    if NumberingD[Y, X] = $00 then begin    // ラベルリングしてなかったら
      NumberingD[Y, X] := FN;                // ラベルリングする
    end;
  end;
  inc(FN);
end;

//-------------------------------------------------------------------
// データーの番号化 ラベリング １～２５４ 　0 は黒 ２５５は白
//-------------------------------------------------------------------
procedure Labeling;
begin
  FN := 1; // ラベリング最初の番号セット

  for YY := 0 to BHeight - 1 do // ラベリング開始点検索
    for XX := 0 to BWidth - 1 do begin
      if NumberingD[YY, XX] = $00 then begin // ラベリングされていなかったら
        Nopainting(YY, XX); // ラベリング実行
      end;
      if FN > $FE then Break; // ラベルの番号の大きさ確認
    end;
    if FN > $FE then Application.MessageBox('画像の数が多すぎて途中で打ち切りました。','注意',0);
end;

輪郭追跡

　ラベリングをしてあると、各図形の輪郭追跡が容易になります。(輪郭追跡は輪郭追跡と塗りつぶしを参照して下さい。)

各図形の面積

　ラベリングされた図形の面積は、同じ番号を振られた座標点の数を数えれば簡単に得ることが出来ます。

図形の外周長

　図形の外周長は、輪郭追跡を行い、上下左右に移動した時は、１　加算し、斜めに移動した時は、 √2 (1.414)加算します。
図形の面積と、外周長は理論値には一致しません。

画像の座標点を加算すると、面積は座標点の面積を単位１として、左図の様に加算され、長さは、座標点中心から次の座標点中心点までの距離とされる為、上下左右だけの移動の場合は面積に対して、外周長は小さい値になります。


　実態に対して、画像はデジタル画像となり、斜めの直線、或いは曲線を正確にたどるものではありません。
水平、垂直線と、斜め４５度の線の組み合わせとなる為に、面積にたいして、長くなります。
面積が大きければ、プラス、マイナスの誤差が打ち消されそれなりの値となります。

重心の計算
　重心の計算は、図形点のの座標を元に計算します。
　重心位置は、座標の原点、ここの例では、左上の点が原点となります。
Ｙ軸投影量、Ｘ軸投影量をラベリングした図形毎に求めます。
軸投影量とその軸の原点からの距離を乗算したものの総和を求め面積で割れば、重心位置の座標を得ることが出来ます。
（各軸の投影量の総和と面積は一致します。）
画像の軸角も求める事ができます。

画像処理（黒丸の抽出と処理）を参照して下さい。

円形度
　円に注目する場合は、円形度を計算します。
円は面積に対して、外周長が一番短くなるので、円形度を計算することで、円の抽出が可能となります。

　Ｓ＝画像の面積　　Ｌ＝外周長

円形度　＝　4 * π * S / L^2　          （Ｌ＾2　は　L*L）

   
　完全な円であれば、値は１になりますので、１に近いほど円に近いといえます。
但し、円は塗りつぶし円である必要があります。

空白部の検出


 図形のラベリングが終了したら、図形の外側を４方向塗りつぶしをすれば、図形の中抜き部分の検出が容易になります。
８方向塗りつぶしで、周囲を塗りつぶすと、中抜き部まで塗りつぶされてしまう事があります。
塗りつぶし手順は、輪郭追跡と塗りつぶしを参照して下さい。
ここでダウンロード出来るサンプルプログラムには、中抜き検出は含まれていません。

カラーの２５６階調グレイデーターへの変換

　カラー画像を２値化する場合、一度グレイデーターに変換していますが、ここでは、三色加算して平均を求める方法ではなく、米、日本のテレビで使用されている、輝度信号の重み付けを使用してみました。
これは、カラーに対する 視感度 特性の補正ですが、これは、個人によって差があるのは当然なので、余り厳密に従う必要な無いと思われます。
又、そもそも、輝度信号変換は、アナログ回路により変換をしていたので、五桁もあるような正確な変換ではありません。
多くの日本人は、黒い瞳を持ち、虹の色を七色と感じますが、青い目をもつ人は、六色とか五色に感じるように、元の値の根拠もあまり厳密なものではありません。
しかし、何らかの値を決めておかないと、バラバラの値がテレビ信号に採用されてしまうので、それを防止するためのものです。

R、G、B の各々の値が 0 ～ 255 の任意の整数とすると、グレースケール変換後の値 Y （値の範囲は 0 ～ 255 の整数）は、以下の式で求められます。

　　　　Y = ( 0.298912 * R + 0.586611 * G + 0.114478 * B )

近似値で良いと思われるなら、下記の計算で十分と思われます。

　　　　Ｙ = ( 2 * R + 4 * G + B ) div 7   （整数演算のみで計算されます　Y=0.286*R + 0.571*G+ 0.143*B）

データー全てに浮動小数点演算をせず、整数の係数を用意して、整数演算する方法を使用してみました。

係数を 32768 倍して、計算後、１５ビット右シフトしてグレーデーターとする方法です。
（1024倍して、１０ビット右シフトでも実際には十分でしょう)

 
  Pa : PByteArray;                                 // TbyteArray ポインター


  SetLength(Graydata, BHeight, Bwidth);            // グレースケール配列長さセット

  RParam := Round(0.298912 * 32768);               // 色係数作成
  GParam := Round(0.586611 * 32768);
  BParam := Round(0.114478 * 32768);
  for YY := 0 to BHeight - 1 do                    // グレースケールデーター生成
    begin
      Pa := InputBitmap.Scanline[YY];              // ビットマップラインポインター取得
      for XX := 0 to BWidth -1 do                  // １ライン処理
        begin
          GG := XX * 3;                            // １ピクセル当たり３バイトなので３倍する
          B := (Pa[GG ]    * BParam);              // 青
          G := (Pa[GG + 1] * GParam);              // 緑
          R := (Pa[GG + 2] * Rparam);              // 赤
          Graydata[YY, XX] := (R + G + B) shr 15;  // 三色の加算 　32768 分 右シフト
       end;
  end;

２値化データーの表示

　 ２値化データーの表示には、黒を＄００とし、白＄ＦＦとして８ビットフォーマットとして表示するのが、一番簡単なのですが、単なる白と黒だけなので、１ビットフォーマットでも表示可能なので、あえて、１ビットフォーマットで表示をしてみました。
　BinarizeDataは、黒＄００白＄ＦＦの８ビットデーター配列にしてあるので、１ビット単位にする場合、８バイト分が１バイトに変換されることになります。

  XX, YY : integer;                               // for loop 用 PD ポインター計算用
  DD : byte;                                      // byteデーター
  Pa        : PByteArray;                         // TbyteArray ポインター
  WaBBitmap : TBitmap
  SiftD : integer;
  NBITD : Byte;
  WabPointer : cardinal;


// ２値化データーの表示
  WaBBitmap := TBitmap.Create;
  WaBBitmap.Width := BWidth;
  WaBBitmap.Height := Bheight;
  WaBBitmap.PixelFormat := pf1bit;                // 一ビット フォーマット
  for YY := 0 to BHeight - 1 do                   // ビットマップのデーター表示
    begin
      Pa := WaBBitmap.ScanLine[YY];               // ポインターの取得
      for XX := 0 to BWidth - 1 do                // ライン処理
        begin
          WaBPointer := XX div 8;                 // ビット単位なので X方向 ８個で １バイト
          SiftD := XX mod 8;                      // ビットシフト量を求めます　X方向の値を８で割った余りが右シフト量となります。
          NBITD := $80 shr SiftD;                 // 010000000 を右シフトして白ビットデーター作成
          DD := BinarizeData[YY, XX];             // 配列データー取得
          if DD = $FF then pa[WaBPointer] := pa[WaBPointer] or NBITD       // 白だったらそこのビットをセット 1 にします
                      else pa[WaBPointer] := pa[WaBPointer] and not NBITD; // 黒だったらそこのビットをリセット 0 にします
        end;
    end;
  Canvas.StretchDraw(Vcrect, WaBBitmap);          // ストレッチ表示

　　　　 　Labeling.zip

画像処理一覧へ戻る

　　　　　　最初に戻る