ラベリング方法の工夫をしたいのですが・・・

はじめまして！大学で画像処理について学び始めたものですが、
ラベリング処理でわからないことがあり、質問させていただきました！
二値化はなんとかできたのですが・・・
下記のようにラベルをつけるにはどうしたらよろしいでしょうか？？


画素数
○⇒２５５
●⇒０

一○○○○○○○○○
行○○○○●○○○○⇒左から順に●に１、２、３、とつけたい
目○●○○○○○●○
　○○○○○○○○○
　○○○○○○○○○
　○○○○○○○○○
二○○○○○○○●○
行○●○○●○○○○⇒左から順に●に１１、１２、１３とつけたい
目○○○○○○○○○
　○○○○○○○○○
　○○○○○○○○○
※●は横一列ですが上記のように一番右の●の座標が上だったりするなど縦にずれていてラベリングがうまく走査できません。。。この図だと縦に一列ですが、実際は横にも画素がずれています。。。。

最終的には、このようにラベリングして
一○○○○○○○○○
行○○○○２○○○○
目○１○○○○○３○
　○○○○○○○○○
　○○○○○○○○○
　○○○○○○○○○
二○○○○○○○13○
行○11○○12○○○○
目○○○○○○○○○
　○○○○○○○○○
　○○○○○○○○○

１と１１　２と１２　３と１３の距離を測りたいと思っています・・・なのですが、この際ラベリングを走査すると
一行目の「１」とつけたい画素に「２」がついてしまったり、
二行目の「３」とつけたい画素に「１」がついてしまいます。。

そこでラベリングを、コンビニのスキャナーのように
４つの画素分ぐらいで横に走査できるようにできないか、
と考えたのですが、参考書などを調べたのですが
そのようなラベリングは見つからず、
うずまきラベリングや
４近傍ラベリングは見つけたのですが、
うまくラベルをつけることができませんでした。
うずまきラベリングは一行目の横画素に到達するまえに
上下の画素に触れてしまいラベリングできませんでした。
４近傍ラベリングは通常のラベリングと同じような結果になってしまいました。

もしどなたか、このようなラベリング方法を知っている方など
いましたらご教授お願いします！！
説明不足、意味がよくわからないところなどありましたらご指摘お願いします
よろしくお願いします（＞＜）

No.1 回答者： Tacosan 回答日時： 2009/01/27 15:57

「一行目」とか「二行目」の意味が分からん. どこが一行目でどこが二行目なのか.

でもって, 単純に「左から右にスキャンする」だけじゃダメなの?

この回答への補足

早速返信ありがとうございます。
わかりずらく、すいません；
一行目と二行目は気にしないでください。
☆開始で左から右にスキャンしていくと
⇒⇒⇒
☆⇒⇒⇒⇒⇒⇒⇒⇒
⇒⇒⇒⇒１○○○○
○２○○○○○３○
○○○○○○○○○
○○○○○○○○○
○○○○○○○○○
○○○○○○○11○
○12○○13○○○○
○○○○○○○○○
○○○○○○○○○
○○○○○○○○○
のようにラベルが思ったようにつかないのです。。

補足日時：2009/01/27 16:35

No.2 回答者： arain 回答日時： 2009/01/27 16:39

「行」の意味が分からないのはNo.1氏と同じなんだけど、

>画素数
>○⇒２５５
>●⇒０
もわからない。
これが、二次元配列(行を含めると三次元？)に入った内容なのかもあいまい。
少なくとも、
「理想」と「現実」にギャップがあるのであれば、まずソースの提示。

この回答への補足

不勉強ですいません！
まず、二次元配列です。ｘ、ｙ軸にして座標をテキスト出力する予定です。

●⇒０
○⇒２５５
の数字は輝度値です。なのでただの画素の集合と思っていただいて大丈夫だと思います。

行の意味は
質問で記述したのをアップすると
○○○○○○○○○○○○○
○●○●○●○●○●○●○
○○○○○○○○○○○○○
○●○●○●○●○●○●○
○○○○○○○○○○○○○
このように画素が横に並んだように見えるので
（実際には上下左右に若干乱れています。）
一行目と
二行目に分けさせていただきました；自分視点で書いてしまいすいません・・
その不ぞろいに並んでいる左から右に画素を１，２，３・・・と
順番をラベリングしたいと思っているんですが・・・
ソースなのですが今ソースが手元にありませんので明日にはUPさせてもらいます・・・

補足日時：2009/01/27 17:22

No.3 回答者： chie65535 回答日時： 2009/01/27 17:30

と言う事は、以下のようになっている事がある訳だな？

　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
一○○○○●○○○○○○○○○○○●○○●○○○○○○○
行○●○○○○○●○○●○○●○○○○○●○○●○○●○
目○○○○○○○○○○●○○○○○○○○○○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
二○○○○○○○●○○●○○○○○○○○○○○○○○○○
行○●○○●○○○○○○○○●○○●○○○○○●○○●○
目○○○○○○○○○○○○○○○○●○○●○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○

で
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
一○○○○ ２○○○○○○○○○○○ ６○○ ７○○○○○○○
行○ １○○○○○ ３○○ ４○○ ５○○○○○ ７○○ ８○○ ９○
目○○○○○○○○○○ ４○○○○○○○○○○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
二○○○○○○○13○○14○○○○○○○○○○○○○○○○
行○11○○12○○○○○○○○15○○16○○○○○18○○19○
目○○○○○○○○○○○○○○○○16○○17○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
と「ラベル」を付けたいと。

だったら
一○○○○●○○○○○○○○○○○●○○●○○○○○○○
行○●○○○○○●○○●○○●○○○○○●○○●○○●○
目○○○○○○○○○○●○○○○○○○○○○○○○○○○
の３ラインを、左から同時に見ていくしかない。３個ペアになった「３個縦１列」に「１個以上の黒い画素」があったら、その「黒い画素」にラベルを振る。

２行目も
二○○○○○○○●○○●○○○○○○○○○○○○○○○○
行○●○○●○○○○○○○○●○○●○○○○○●○○●○
目○○○○○○○○○○○○○○○○●○○●○○○○○○○
の３ラインを左から順に同時に調べ「画素３個ペア」で見ていくしかないだろう。

「元の映像」で「ラインとラインの間に黒い点」があれば「１行目の４番」のように「縦に、２つの黒い画素が並ぶ可能性がある」ので「同じラベルが複数の画素に付く可能性」も考慮すること。

なお
　 ○○○○○○○○○○○○○○○○○○○○○○○○○●○
一○○○○○○○○○○○○○○○○○○○●○○●○○○○
行○○○○○○○●○○●○○●○○●○○○○○○○○○○
目○●○○●○○○○○○○○○○○○○○○○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○●○
二○○○○○○○○○○○○○○○○○○○●○○●○○●○
行○○○○○○○○○○●○○●○○●○○○○○○○○○○
目○●○○●○○●○○○○○●○○○○○○○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○○○
　 ○○○○○○○○○○○○○○○○○○○○○○○○○●○
のように、ラインが斜めにひん曲がった状態で画像を取り込んでしまった場合は、単純な方法ではラベリングできない。

「予想されるライン」を斜めのベクトルを持つ「線分」として求め、その「線分」に添って「銭分上の画素を、上下の画素とともに３画素ペアでスキャン」していく事になる。

この回答へのお礼

chie65535さん、ありがとうございます！
元の画像の状態として、3ラインで走査していけばできそうですが、弱冠曲がっているので、もしかしたらchie65535さんが言ってくれた通り、線分を求めてその線分上を走査する必要がでてくるかもしれません。
まず「３ラインでラベリング」を試してみたいと思います。
自分無知で申し訳ないのですが、もしよろしければ、3ラインでラベリングのプログラムや参考サイトなどがございましたら教えていただけると助かります（＞＜）よろしくお願いします。。

お礼日時：2009/01/27 18:40

No.4 回答者： zwi 回答日時： 2009/01/27 23:14

>自分無知で申し訳ないのですが、もしよろしければ、3ラインでラベリングのプログラムや参考サイトなどがございましたら教えていただけると助かります（＞＜）よろしくお願いします。

。
単にdata[Ｘ軸][ライン]だとしたら、
line = 0;
while( line < ラインの終わり ) {
　for( int x=0 ; x<Ｘ軸の最大値 ; x++ ) {
　　if( data[x][line+0]==0 || data[x][line+1]==0 ||data[x][line+2]==0 ) {
　　　//ラベリングする
　　}
　}
　line += 3;//?３つ進ませるのが良いかは取り込み方が一定化できる場合だけ。機械誤差を含むなら工夫が必要。
}
って事では？
ただ、常に３ラインなのかも機械誤差が含まれるなら問題になる気がする。

この回答への補足

機械誤差とは
取り込む際の誤差で画像が歪む？という事でよろしいでしょうか？
プログラム貼り付けありがとうございます！
参考にさせてもらいます！

補足日時：2009/01/28 14:24

No.5 ベストアンサー 回答者： chie65535 回答日時： 2009/01/28 12:59

歪んだ画像も処理できる、ラベリングの方法。

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○●○○
03○○○○○○○○○○○○○○○○○●○○●○○○○○
04○○○○○●○○●○○●○○●○○○○○○○○○○○
05○○●○○●○○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○
07○○○○○○○○○○○○○○○●○○●○○●○○○○
08○○○○○○●○○●○○●○○●○○○○○○○○○○
09●○○●○○○○○○○○○○○○○○○○○○○○○○
10○○○○○○○○○○○○○○○○○○○○○○○○○○
11○○○○○○○○○○○○○○○○○○○○○○○○○●
12○○○○○○○○○○○○○○○○○○○●○○●○○●
13○○○○○○○○○○●○○●○○●○○○○○○○○○
14○●○○●○○●○○○○○●○○○○○○○○○○○○
15○○○○○○○○○○○○○○○○○○○○○○○○○○
16○○○○○○○○○○○○○○○○○○○○○○○○○●

上記のような画像があったとする。

まず、１行目の先頭「Ａ」を見付けなければならない。

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○●○○
03○○○○○○○○○○○○○○○○○●○○●○○○○○
04○○○○○●○○●○○●○○●○○○○○○○○○○○
05○○ Ａ○○●○○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○
07○○○○○○○○○○○○○○○●○○●○○●○○○○
08○○○○○○●○○●○○●○○●○○○○○○○○○○
09●○○●○○○○○○○○○○○○○○○○○○○○○○
10○○○○○○○○○○○○○○○○○○○○○○○○○○
11○○○○○○○○○○○○○○○○○○○○○○○○○●
12○○○○○○○○○○○○○○○○○○○●○○●○○●
13○○○○○○○○○○●○○●○○●○○○○○○○○○
14○●○○●○○●○○○○○●○○○○○○○○○○○○
15○○○○○○○○○○○○○○○○○○○○○○○○○○
16○○○○○○○○○○○○○○○○○○○○○○○○○●

まず、上から１ラインづつスキャンしていき、Ｂを見付ける。

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○ Ｂ○○
03○○○○○○○○○○○○○○○○○●○○●○○○○○

01→○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○ Ｂ○○
03○○○○○○○○○○○○○○○○○●○○●○○○○○

01→→○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○ Ｂ○○
03○○○○○○○○○○○○○○○○○●○○●○○○○○
（略）
01→→→→→→→→→→→→→→→→→→→→→→→→→→
02→→→→→→→→→→→→→→→→→→→→→→→ Ｂ○○
03○○○○○○○○○○○○○○○○○●○○●○○○○○

この時点ではラベリングはしない。なぜなら、現在行っている処理は「Ａを発見するため」である。

但し、Ｂの位置を「最も最近に見付けた画素」として位置を記憶しておくこと。

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○ Ｂ○○
03○○○○○○○○○○○○○○○○○●○○●○○○○○
04○○○○○●○○●○○●○○●○○○○○○○○○○○
05○○ Ａ○○●○○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○
07○○○○○○○○○○○○○○○●○○●○○●○○○○
08○○○○○○●○○●○○●○○●○○○○○○○○○○
09●○○●○○○○○○○○○○○○○○○○○○○○○○
10○○○○○○○○○○○○○○○○○○○○○○○○○○
11○○○○○○○○○○○○○○○○○○○○○○○○○●
12○○○○○○○○○○○○○○○○○○○●○○●○○●
13○○○○○○○○○○●○○●○○●○○○○○○○○○
14○●○○●○○●○○○○○●○○○○○○○○○○○○
15○○○○○○○○○○○○○○○○○○○○○○○○○○
16○○○○○○○○○○○○○○○○○○○○○○○○○●

Ｂから、左方向に進みながら、Ｂがあるラインの上下３画素をスキャンしていく。「◎」が調べる画素である。

01○○○○○○○○○○○○○○○○○○○○○○◎○○○
02○○○○○○○○○○○○○○○○○○○○○○◎●○○
03○○○○○○○○○○○○○○○○○●○○●○◎○○○
04○○○○○●○○●○○●○○●○○○○○○○○○○○
05○○ Ａ○○●○○○○○○○○○○○○○○○○○○○○

01○○○○○○○○○○○○○○○○○○○○○◎○○○○
02○○○○○○○○○○○○○○○○○○○○○◎○●○○
03○○○○○○○○○○○○○○○○○●○○●◎○○○○
04○○○○○●○○●○○●○○●○○○○○○○○○○○
05○○ Ａ○○●○○○○○○○○○○○○○○○○○○○○

01○○○○○○○○○○○○○○○○○○○○◎○○○○○
02○○○○○○○○○○○○○○○○○○○○◎○○ Ｂ○○
03○○○○○○○○○○○○○○○○○●○○ Ｃ○○○○○
04○○○○○●○○●○○●○○●○○○○○○○○○○○
05○○ Ａ○○●○○○○○○○○○○○○○○○○○○○○

Ｃを発見した所で「最も最近に見付けた画素」をＣに更新する。

そして、Ｃがあるラインの上下３画素をスキャンしていく。

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○◎○○○ Ｂ○○
03○○○○○○○○○○○○○○○○○●○◎ Ｃ○○○○○
04○○○○○●○○●○○●○○●○○○○◎○○○○○○
05○○ Ａ○○●○○○○○○○○○○○○○○○○○○○○

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○◎○○○○ Ｂ○○
03○○○○○○○○○○○○○○○○○●◎○ Ｃ○○○○○
04○○○○○●○○●○○●○○●○○○◎○○○○○○○
05○○ Ａ○○●○○○○○○○○○○○○○○○○○○○○

このように、黒い画素を見付けるたびに「最も最近に見付けた画素」を更新しながら、スキャンするラインを調整しつつ、左へ進んで行く。

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○ Ｂ○○
03○○○○○○◎○○○○○○○○○○●○○●○○○○○
04○○○○○●◎○●○○●○○●○○○○○○○○○○○
05○○ Ａ○○●◎○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○

まず最初の問題は、上記の「次」である。見付かる画素は以下のようにＤ、Ｅの２つある。

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○ Ｂ○○
03○○○○○◎○○○○○○○○○○○●○○●○○○○○
04○○○○○ Ｄ○○●○○●○○●○○○○○○○○○○○
05○○ Ａ○○ Ｅ○○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○

この場合は「Ｄの１ライン上から、Ｅの１ライン下までの４ライン」が「探すライン」となる。

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○ Ｂ○○
03○○○○◎○○○○○○○○○○○○●○○●○○○○○
04○○○○◎●○○●○○●○○●○○○○○○○○○○○
05○○ Ａ○◎●○○○○○○○○○○○○○○○○○○○○
06○○○○◎○○○○○○○○○○○○○○○○○○○●○

つまりは「見付かった画素のうち、一番上にある画素の１ライン上から始めて、一番下にある画素の１ライン下まで」と言う事になる。

前述の「Ｂがあるラインの上下３画素をスキャンしていく」も「Ｂが一番上にある画素であり、かつ、一番下にある画素」であるので、結局は「同じ事」である。

03○○○◎○○○○○○○○○○○○○●○○●○○○○○
04○○○◎○●○○●○○●○○●○○○○○○○○○○○
05○○ Ａ◎○●○○○○○○○○○○○○○○○○○○○○
06○○○◎○○○○○○○○○○○○○○○○○○○○●○

03○○○○○○○○○○○○○○○○○●○○●○○○○○
04○○◎○○●○○●○○●○○●○○○○○○○○○○○
05○○ Ａ○○●○○○○○○○○○○○○○○○○○○○○
06○○◎○○○○○○○○○○○○○○○○○○○○○●○

この時点でＡを発見する。「最も最近に見付けた画素」をＡに更新していく。

そして、更に左に進む。

03○○○○○○○○○○○○○○○○○●○○●○○○○○
04○◎○○○●○○●○○●○○●○○○○○○○○○○○
05○◎ Ａ○○●○○○○○○○○○○○○○○○○○○○○
06○◎○○○○○○○○○○○○○○○○○○○○○○●○

03○○○○○○○○○○○○○○○○○●○○●○○○○○
04◎○○○○●○○●○○●○○●○○○○○○○○○○○
05◎○ Ａ○○●○○○○○○○○○○○○○○○○○○○○
06◎○○○○○○○○○○○○○○○○○○○○○○○●○

画像の一番左に達した所で、一旦、終了する。

ここで「最も最近に見付けた画素」が「Ａ」になっている。

つまり、この時点での「最も最近に見付けた画素」が「１行目の開始点」であり、探すべき「Ａ」である。

さて、無事にＡが見付かったので、ここから「ラベリング」を行う。

まず「１行目の１つ目」として「Ａ」にラベルを付ける。

次に行うのは「今やった事を、逆方向、つまり、右方向に行うだけ」である。図の「Ｈ」は「ヒットした画素」で「Ｈ」を順にラベリングすれば良い。

03○○○○○○○○○○○○○○○○○●○○●○○○○○
04○○○◎○●○○●○○●○○●○○○○○○○○○○○
05○○ Ａ◎○●○○○○○○○○○○○○○○○○○○○○
06○○○◎○○○○○○○○○○○○○○○○○○○○●○

03○○○○○○○○○○○○○○○○○●○○●○○○○○
04○○○○◎●○○●○○●○○●○○○○○○○○○○○
05○○ Ａ○◎●○○○○○○○○○○○○○○○○○○○○
06○○○○◎○○○○○○○○○○○○○○○○○○○●○

03○○○○○○○○○○○○○○○○○●○○●○○○○○
04○○○○○ Ｈ○○●○○●○○●○○○○○○○○○○○
05○○ Ａ○○ Ｈ○○○○○○○○○○○○○○○○○○○○
06○○○○○◎○○○○○○○○○○○○○○○○○○●○

03○○○○○○◎○○○○○○○○○○●○○●○○○○○
04○○○○○ Ｈ◎○●○○●○○●○○○○○○○○○○○
05○○ Ａ○○ Ｈ◎○○○○○○○○○○○○○○○○○○○
06○○○○○○◎○○○○○○○○○○○○○○○○○●○

03○○○○○○○◎○○○○○○○○○●○○●○○○○○
04○○○○○ Ｈ○◎●○○●○○●○○○○○○○○○○○
05○○ Ａ○○ Ｈ○◎○○○○○○○○○○○○○○○○○○
06○○○○○○○◎○○○○○○○○○○○○○○○○●○

03○○○○○○○○◎○○○○○○○○●○○●○○○○○
04○○○○○ Ｈ○○ Ｈ○○●○○●○○○○○○○○○○○
05○○ Ａ○○ Ｈ○○◎○○○○○○○○○○○○○○○○○
06○○○○○○○○◎○○○○○○○○○○○○○○○●○

03○○○○○○○○○◎○○○○○○○●○○●○○○○○
04○○○○○ Ｈ○○ Ｈ◎○●○○●○○○○○○○○○○○
05○○ Ａ○○ Ｈ○○○◎○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○

中略。

01○○○○○○○○○○○○○○○○○○○○○○◎○○○
02○○○○○○○○○○○○○○○○○○○○○○◎●○○
03○○○○○○○○○○○○○○○○○ H○○ Ｈ○◎○○○
04○○○○○ H○○ Ｈ○○ H○○ Ｈ○○○○○○○○○○○
05○○ Ａ○○ Ｈ○○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○

01○○○○○○○○○○○○○○○○○○○○○○○◎○○
02○○○○○○○○○○○○○○○○○○○○○○○ Ｈ○○
03○○○○○○○○○○○○○○○○○ H○○ Ｈ○○◎○○
04○○○○○ H○○ Ｈ○○ H○○ Ｈ○○○○○○○○○○○
05○○ Ａ○○ Ｈ○○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○

01○○○○○○○○○○○○○○○○○○○○○○○○◎○
02○○○○○○○○○○○○○○○○○○○○○○○ Ｈ◎○
03○○○○○○○○○○○○○○○○○ H○○ Ｈ○○○◎○
04○○○○○ Ｈ○○ H○○ Ｈ○○ H○○○○○○○○○○○
05○○ Ａ○○ Ｈ○○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○

01○○○○○○○○○○○○○○○○○○○○○○○○○◎
02○○○○○○○○○○○○○○○○○○○○○○○ Ｈ○◎
03○○○○○○○○○○○○○○○○○ H○○ Ｈ○○○○◎
04○○○○○ Ｈ○○ H○○ Ｈ○○ H○○○○○○○○○○○
05○○ Ａ○○ Ｈ○○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○

右端まで行けば、１行目のラベリングが終了する。

左方向、右方向のどちらの方向にスキャンする時も、注意しなければならないのは下図のような「スキャンしているラインからはみ出した、縦に並んだ黒い画素」である。

スキャン方向→
○○○○○○○○○○
○○○○○○○●○○
○○○○●○○○○○
○○◎○●○○○○○
○ Ｈ◎○○○○○○○
○○◎○○○○○○○

○○○○○○○○○○
○○○○○○○●○○
○○○○●○○○○○
○○○◎●○○○○○
○ Ｈ○◎○○○○○○
○○○◎○○○○○○

○○○○○○○○○○
○○○○○○○●○○
○○○○●○○○○○
○○○○ Ｈ○○○○○
○ Ｈ○○◎○○○○○
○○○○◎○○○○○

この時点で、縦に並んだ２つのうち「下の１つだけ」しかヒットしない。

なので「ヒットした画素があったら、スキャンしてないラインであっても、上下の１画素も確認する必要」がある。

上下も確認すると、２つ縦に並んだ両方がヒットする。

○○○○○○○○○○
○○○○○○○●○○
○○○○ Ｈ○○○○○
○○○○ Ｈ○○○○○
○ Ｈ○○◎○○○○○
○○○○◎○○○○○

そして、次にスキャンするのは「見付かった画素のうち、一番上にある画素の１ライン上から、一番下にある画素の１ライン下まで」と言う事になる。

○○○○○○○○○○
○○○○○○○●○○
○○○○ Ｈ○○○○○
○○○○ Ｈ○○○○○
○ Ｈ○○◎○○○○○
○○○○◎○○○○○

○○○○○○○○○○
○○○○○◎○●○○
○○○○ Ｈ◎○○○○
○○○○ Ｈ◎○○○○
○ Ｈ○○○◎○○○○
○○○○○○○○○○

○○○○○○○○○○
○○○○○○◎●○○
○○○○ Ｈ○◎○○○
○○○○ Ｈ○◎○○○
○ Ｈ○○○○◎○○○
○○○○○○○○○○

○○○○○○○○○○
○○○○○○○ Ｈ○○
○○○○ Ｈ○○◎○○
○○○○ Ｈ○○◎○○
○ Ｈ○○○○○◎○○
○○○○○○○○○○

○○○○○○○○◎○
○○○○○○○ Ｈ◎○
○○○○ Ｈ○○○◎○
○○○○ Ｈ○○○○○
○ Ｈ○○○○○○○○
○○○○○○○○○○

さて、次は「２行目の処理」である。

まず、ライン09の左端、２行目の先頭「Ｅ」を見付けなければならない。

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○●○○
03○○○○○○○○○○○○○○○○○●○○●○○○○○
04○○○○○●○○●○○●○○●○○○○○○○○○○○
05○○●○○●○○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○●○
07○○○○○○○○○○○○○○○●○○●○○●○○○○
08○○○○○○●○○●○○●○○●○○○○○○○○○○
09 Ｅ○○●○○○○○○○○○○○○○○○○○○○○○○
10○○○○○○○○○○○○○○○○○○○○○○○○○○
11○○○○○○○○○○○○○○○○○○○○○○○○○●
12○○○○○○○○○○○○○○○○○○○●○○●○○●
13○○○○○○○○○○●○○●○○●○○○○○○○○○
14○●○○●○○●○○○○○●○○○○○○○○○○○○
15○○○○○○○○○○○○○○○○○○○○○○○○○○
16○○○○○○○○○○○○○○○○○○○○○○○○○●

これも、一行目と同じく、上から１ラインづつスキャンしていく事になる。

但し「ラベリング済みの画素は無視」する。

「ラベリング済みの画素は無視」で探すと、「Ｆ」が見付かる。

01○○○○○○○○○○○○○○○○○○○○○○○○○○
02○○○○○○○○○○○○○○○○○○○○○○○●○○
03○○○○○○○○○○○○○○○○○●○○●○○○○○
04○○○○○●○○●○○●○○●○○○○○○○○○○○
05○○●○○●○○○○○○○○○○○○○○○○○○○○
06○○○○○○○○○○○○○○○○○○○○○○○○ Ｆ○
07○○○○○○○○○○○○○○○●○○●○○●○○○○
08○○○○○○●○○●○○●○○●○○○○○○○○○○
09 Ｅ○○●○○○○○○○○○○○○○○○○○○○○○○
10○○○○○○○○○○○○○○○○○○○○○○○○○○
11○○○○○○○○○○○○○○○○○○○○○○○○○●
12○○○○○○○○○○○○○○○○○○○●○○●○○●
13○○○○○○○○○○●○○●○○●○○○○○○○○○
14○●○○●○○●○○○○○●○○○○○○○○○○○○
15○○○○○○○○○○○○○○○○○○○○○○○○○○
16○○○○○○○○○○○○○○○○○○○○○○○○○●

あとは「１行目の処理と同じ」である。

実は「１行目の最初のスキャンの時も、ラベリング済みの画素は無視」で良い。そうする事で「１行目も２行目も同じ処理」となる。

なお「歪んだ画像」を走査している場合「ラベリング済みの画素が、再度、ヒットしてしまう」と言う事が起きる。

なので「ラベリング済みの画素は、画像データを○に書き替えるなど、２度とヒットしない」ようにすると良い。

その場合、当然「元画像が残ってないと困る」ので、ラベリングは「画素を自由に書き替えて良い、作業用画像」で行う事となる。

あとは、上記の通りにプログラミングするだけ。

この回答へのお礼

とても丁寧にありがとうございます！まだ画像処理、c言語自体もほとんどわからない身ですが、理解する事ができました。
どうにかプログラミングを組んでみたいと思います！
8近傍のラベリングとはまったく違ったものですね;
厳しそうですが、今から頑張りたいと思います。
解決口を教えて頂いて大変助かりました。
本当にありがとうございました！

お礼日時：2009/01/28 14:35