画像処理ソリューション
これを見れば画像処理の入門から基礎~応用まで全てがわかるのを目指して!
   
翻訳(Translate)

プロフィール

Akira

ニックネーム:Akira
東京都の町田事業所に勤務
画像処理ソフトの開発を行っています。リンクフリーです!
詳細プロフィールは こちら
お問い合わせは、こちら↓

【補助HP】
画像処理ソリューションWeb版 【Newブログ】
イメージングソリューション

スポンサーリンク


カテゴリ

最近のコメント

カレンダー

07 | 2017/08 | 09
S M T W T F S
- - 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 - -

趣味のブログ

iPhone萬歳!
iPhoneの情報いろいろ。
ブログ学習帳
ブログ、SEO、アフィリエイト情報など(まだまだこれから)
俺流クラフト日記
ハンドメイド作品の記録(現在、放置中)

スポンサーリンク 最近の記事
(09/18)  計測測定展に光切断のデモを出展しました
(08/17)  ディジタル画像技術事典200に記事が載りました
(06/09)  光切断を画像センシング展で公開
(05/14)  中国(上海)へ行って来ました
(04/12)  韓国へ行って来ました
(03/10)  私の求める新人像
(01/18)  エレクトロテストジャパンにカラー光切断法のデモを出展しました。
(12/23)  ユニークアクセス200万達成!
(12/10)  【カラー光切断法】YouTube動画まとめ
(11/04)  国際画像機器展2014にカラー光切断法を出展します。
(10/05)  第25回コンピュータビジョン勉強会@関東に参加してきました。
(09/08)  フーリエ変換の記事を追加しました。
(08/09)  【画像処理】ランキング低下中
(07/06)  記事の更新が停滞中...
(06/08)  画像センシング展2014でカラー光切断法のデモを行います。
(05/17)  カラー光切断法の動画を公開しました。
(04/30)  ソニーα NEX-5Rで星空撮影
(04/10)  カラー光切断法の取込結果を追加しました
(03/08)  Korea Vision Show 2014へ行ってきました
(02/05)  フーリエ変換シリーズを始めます。
(01/06)  2014年、あけましておめでとうございます。
(12/04)  カラー光切断法を公開(国際画像機器展2013にて)
(11/13)  国際画像機器展2013に出展します
(10/14)  「画像処理のためのC#」はじめます。
(09/16)  【C#,VB.NET】高速描画コントロールをバージョンアップしました。
(09/04)  拡大鏡に輝度値表示、ルーラー機能を追加した個人ツールを公開
(08/05)  7月の拍手Top5
(07/06)  2013年6月人気記事Top5
(05/12)  SONY α NEX-5Rレビュー
(04/24)  SONY α NEX-5RY購入

ラベリング処理アルゴリズム

メインページ画像処理

二値化画像処理された画像において、白の部分(または黒の部分)が連続した画素に同じ番号を割り振る処理を
ラベリングと言います。

通常、同じ番号ごとの面積(画素数)や幅、高さなどの特徴量を求めて欠陥検査や分類処理などに用いられます。

ラベリングには、二値化された画像の横方向に連続している部分を同じラベルにする4連結と、
縦、横、斜め方向に連続している部分を同じラベルにする8連結との2種類の処理があります。
(4近傍、8近傍という場合もあります。)

【二値化画像】 
ラベリング処理アルゴリズム 

【4連結】

【8連結】
ラベリング処理アルゴリズムラベリング処理アルゴリズム

以下、8連結の場合において、ラベリング処理アルゴリズムを紹介します。

まず、画像全ての画素のラベル番号を0(ゼロ)で初期化しておき、ラベリングで番号を割り付けるための
ラベリング番号のルックアップテーブルを用意しておきます。(テーブルの使い方の詳細は後ほど)

そして、画像の左上からラスタスキャンを行い、画素の色がの位置を検索します。
ラベリング処理アルゴリズム

白の画素の左上、上、右上、左の画素のラベル番号を参照し、全て0(ゼロ)の場合は、最後に割り振った番号+1のラベル番号を割り振ります。
もし、参照した画素のラベル番号が複数存在した場合は、最小の番号を割り振ります。
ラベリング処理アルゴリズム

最初に番号を割り振った様子↓
ラベリング処理アルゴリズム

この処理を左上からラスタスキャンして続けていきます。
ラベリング処理アルゴリズム

新しい番号が割り振られるとき↓
ラベリング処理アルゴリズム

新しい番号が割り振られるとき↓ その2
ラベリング処理アルゴリズム

参照した画素のラベル番号が複数存在した場合、最小の番号を割り振ります。
このとき、用いなかったラベル番号(下図の例では3)のルックアップテーブルの番号を最小の番号に書き換えます。
ラベリング処理アルゴリズム

同様に、処理を続けていきます↓
ラベリング処理アルゴリズム

全ての白の画素に番号が割り振れれた様子↓
ラベリング処理アルゴリズム

ただし、よ~く見ると、ラベル番号の2や3など、連続していない部分が存在している事に気がつきます。
そこで、ルックアップテーブルの出番です。

処理の途中でルックアップテーブルの番号を変更した番号を
 2→1、3→1、6→5
に変更すると、連続した領域は同じ番号になります。

このまま番号を変更しても良いのですが、ラベル番号が虫食いになるのも気持ちが悪いので、以下のようにルックアップテーブルの番号を詰め直してから、ルックアップテーブルを参照し、全画素のラベル番号を修正すると、以下のようになります。

ラベリング処理アルゴリズム

基本的なアルゴリズムは上記、紹介したアルゴリズムで良いのですが、ラベリング処理を行う画像のパターンによってはうまくラベル番号が割り振られない場合があります。
そこは、何とかして(ちょっと説明が難しい部分)うまく割り振られるようにチャレンジしてみて下さい。

参考までに、ラベリング処理をすると失敗しやすい特徴的な画像を添付しておきます。↓

◆Level.1
 ラベリング処理アルゴリズム

◆Level.2
 ラベリング処理アルゴリズム

◆Level.Max!?

 ラベリング処理アルゴリズム
 
ラベリング処理のアルゴリズムには、この手法の他にも輪郭線を追跡し、閉じた領域を1つのラベルとする手法もあります。
Loading...
スポンサーリンク

この記事に対するコメント
Re: タイトルなし
コメント頂きありがとうございます。
コメントの内容からすると、ちゃんと出来たようですね。
ここに書いてある、Level.Maxの画像は、私自身、けっこうハマりました。
【2015/08/16 20:36】 URL | Akira #- [ 編集]


最小の番号を振るときに間接参照の最小値を設定するところが抜けているため
Level.1~Maxの判定に失敗していたんですね。
原因を見つけるまで嵌りました。
【2015/08/14 01:16】 URL | たね #- [ 編集]

Re: タイトルなし
お返事が遅くなり申し訳ありません。
ラベル番号を振り直す部分がちゃんとできていれば、前の番号と違う時に、ラベル番号をカウントアップしていけばできると思います。
【2015/06/28 20:55】 URL | Akira #- [ 編集]

Re: Re: Re: テーブルの大きさはいくつにするのでしょうか?
確かにそうですね。(^_^;)
【2013/12/09 20:19】 URL | Akira #- [ 編集]

Re: Re: テーブルの大きさはいくつにするのでしょうか?
了解しました。ありがとうございます

>> 可能性のあるラベルの最大個数(画像の画素数の1/4)で確保するようにしています。

> あー、なるほど。1点おきに点があった場合にそうなりますね。

これ画像の縦と横のピクセルが偶数と奇数の場合で変わりますね。
横幅のピクセル数をwidth、縦幅のピクセル数を heightとすると

(width / 2 + width % 2)*(height / 2+ height % 2)

ですかね。
【2013/12/09 16:55】 URL | くんにゃ #WTRyGCH2 [ 編集]

Re: Re: テーブルの大きさはいくつにするのでしょうか?
ソースコードは、残念ながら、仕事で組んだ事はあるのですが、個人的には作っていないので、公開できません。
ここにある方法は、意外と難しいので、効率は悪いのですが、ここ↓
http://msdn.microsoft.com/ja-jp/cc998604.aspx
にあるような方法でやった方が、バグが少ないと思います。
【2013/12/08 22:33】 URL | Akira #- [ 編集]

Re: テーブルの大きさはいくつにするのでしょうか?
さっそくのお返事ありがとうございます。

> 可能性のあるラベルの最大個数(画像の画素数の1/4)で確保するようにしています。

あー、なるほど。1点おきに点があった場合にそうなりますね。

ちなみに、このラベリングのアルゴリズムを実装したコードは公開されていないのでしょうか?見落としているのかな。
【2013/12/08 19:42】 URL | くんにゃ #WTRyGCH2 [ 編集]

Re: テーブルの大きさはいくつにするのでしょうか?
コメント頂きありがとうございます。

ルックアップテーブルのサイズですが、私は、実際にはあまりないかも?しれませんが、可能性のあるラベルの最大個数(画像の画素数の1/4)で確保するようにしています。
【2013/12/08 13:29】 URL | Akira #- [ 編集]

テーブルの大きさはいくつにするのでしょうか?
大変参考になります。

一つ教えてください。これカメラで撮った画像を使うとラベル数がかなり多くなりそうですが、ルックアップテーブルのサイズはどれくらいにしておくものなのでしょうか?1000もあればよいのですかね?
【2013/12/07 22:30】 URL | くんにゃ #WTRyGCH2 [ 編集]

Re: 8連結に修正する
情報ありがとうございます。
私は井村先生のラベリングクラスは、かなり昔にちょっと動かした事はありますが、あまり触っていなかったので、4連結である事も知りませんでした...
ちなみに、提示して頂いた方法で、二値化された画素が画像の右端と1段下の左端にあるときにつながったり、画像の最初の画素(左上の画素)や最後の画素(右下の画素)が二値化された画素の場合に、Access Violationになったりしませんでしたでしょうか?
【2012/09/21 21:48】 URL | Akira #- [ 編集]

8連結に修正する
元々井村先生のクラスでは4連結にしか、結合しなくて、8連結に直すには、ソースコードを見て、結構複雑だった。

4連結から、8連結に直すためには、以下のところを修正しました。

409行
 修正前:while (( *rspi )->RightX() < rs_seed_lx ) {
 修正後:while (( *rspi )->RightX() < rs_seed_lx-1 ) {
417行
 修正前:while (( rs = *rspi )->LeftX() <= rs_seed_rx) {
 修正後:while (( rs = *rspi )->LeftX() <= rs_seed_rx + 1) {
  
【2012/09/21 13:57】 URL | WW #- [ 編集]

Re: さっそく使わせてもらいました
コメント頂きありがとうございます。
私のブログがお役に立てているようで、何よりです。
ラべリング処理については私が画像処理のプログラムを作った中では比較的難しかった方です。
ここに載せている画像は、その時にハマった画像ですので、是非評価用にお使い下さい。
【2012/04/23 20:22】 URL | Akira #- [ 編集]

さっそく使わせてもらいました
はじめてコメントします。
JProgramerといいます。

いま、画像処理でラベリング処理の仕方を探していました。
ここの記事がたいへんわかりやすく参考になりました。
さっそく、ラベリング処理のアルゴリズムを書いて使用しています。

いまのところうまく機能して、満足しています。

よくこのサイトで画像処理でわからなかったことがあると参考にしています。

いつもありがとうございます。
【2012/04/22 09:59】 URL | JProgramer #- [ 編集]

Re: 基本的なアルゴリズムで、Level1,2の画像では複数のラベルが貼られました。
小松原様、コメント頂きありがとうございます。

ここにある手法のラベリングに関しては、8年ぐらい前?に会社で実装した事があるのですが、一応、ルックアップテーブルは1つで、全画素数のスキャンは最初のスキャンとルックアップテーブルに基づいて、番号を振りなおすスキャンの2回で、Level.MAXとしている画像についてもラベリングする事ができました。詳細は会社でやった事なので、といよりも、覚えていないのですが、ルップアップテーブルの番号を変更する部分はかなり苦労したのを覚えています。
といっても、どの方法が一番、高速にできるのか?はよく分かっていません。
それよりも、教えて頂いたリンクのURLのようにランレングス的な処理(3の処理)の方が、ラベリング処理としては良いかもしれません。
この方法は大阪大学の井村先生が実装されているので、参考になると思います。
http://oshiro.bpe.es.osaka-u.ac.jp/people/staff/imura/products/labeling
【2011/06/06 20:59】 URL | Akira #- [ 編集]

基本的なアルゴリズムで、Level1,2の画像では複数のラベルが貼られました。
解答のヒントが、URLに書かれています。

参照した画素のラベル番号が複数存在した場合、最小の番号を割り振ります。
このとき、用いなかったラベル番号(下図の例では3)のルックアップテーブルの番号を最小の番号に書き換えます。
参照した画素のラベル番号が複数存在
 1・・・問題なし
 2・・・問題なし
 3、4・・・すべてが異なった場合、ラベル番号を関連付ける事が出来ない場合があります。(この時点では、再スキャンをし直さない限りわからないと思われます。)
URLには、
このとき、
「ラベルはすべて同一成分に属することも控えておく」
と、書かれていましたので、このことを考慮して、ルックアップテーブルを2重化(もう1列追加)して、控えておくことにしました。
これで、Level1・2の画像については、解決出来ました。
【2011/06/06 12:47】 URL | 小松原 恵夢 #zdvXpt9s [ 編集]

Re: タイトルなし
申し訳ありません。
教えて頂いたパターンでの失敗が再現できず、『多段階に変化』という部分がいまいち理解できていないのですが、注目画素の左、左上、上、右上のラベル番号を参照し、注目画素のラベル番号を割り振る時に、近傍の画素に割り振られた番号そのものではなく、ルックアップテーブルの番号を注目画素へ割り振る事で回避できませんか?
【2010/11/02 21:57】 URL | Akira #- [ 編集]


ルックアップテーブルが多段階に変化を求めたとき、この方法ではうまくいきませんね。
ルックアップテーブルを多段で持つ必要があると思います。
【2010/11/02 21:00】 URL | ss #mQop/nM. [ 編集]


おっしゃる通り、ルックアップテーブルの部分が難しいんです。
私が最初にラベリング処理のプログラムを作った時は、バグが無くなるまで、結局2週間ぐらいかかったと思います。
ルックアップテーブルの更新の部分は、いかに速い処理ができるかは腕の見せどころだと思いますが、私も正直、どのような方法が正解かは分かっていないので、本文中ではごまかしちゃってます。
前回のコメントでも言ったように、ラベリングがうまく出来ていない部分の画素パターンを抜き出して、エクセルでアルゴリズムの評価をすると、なぜ?ミスってしまうのか?分かりやすいと思います。
もし、画素レベルで輝度値を見るツールなどが無ければ、
http://imagingsolution.blog107.fc2.com/blog-entry-55.html

http://imagingsolution.blog107.fc2.com/blog-entry-72.html
で公開しているソフトも参考にしてみて下さい。
それでは、頑張って下さい。
【2010/07/23 22:00】 URL | Akira #- [ 編集]


いろいろ試してたら一箇所ラベリングが上手くいってない部分が出てきましたorz
ルックアップテーブルの作成の際にいろいろ気をつけないといけないみたいですね;;
a→bというテーブルがあったときに、a→cというテーブルを作りたくなってしまった場合、どっちかが犠牲になります。
c→cの終点→a→bとして解決しようとしましたが、組み方が悪かったのか無限ループします;;
分からない部分が多いのでとりあえず応急処置として、ラベリング後に、隣り合った画素が同一色でラベルが違う部分を探し修正する、という力技を使って対処しました。。。
・・・ちょっと納得いかないのでまたじっくり作ってみようと思います。
【2010/07/23 11:13】 URL | にとり #- [ 編集]

一つ言い忘れてました。
ここに載せている画像ですが、私が評価したときはビットマップファイル(*.bmp)をバイナリデータで輝度値を取得し、ラベリング処理をしていたので、処理の開始点が画像の左下で行っていました。.NETやOpenCVなどで画像の輝度値を取得すると左上が原点となるので、念のため画像を上下反転した画像でも評価してみて下さい。
【2010/07/23 07:40】 URL | Akira #- [ 編集]


にとりさん。はじめまして。
ここに載せてある画像でラベリングが失敗せずに出来たのは良かったです。
私自身がこの方法でラベリング処理を作った時は、かなりハマっていました。
特にLevelMAXとした画像は、エクセルを使ってアルゴリズムのシュミレーションをしながらでないと、なぜ失敗するのか?さえ分からなかった状態でした。
【2010/07/23 07:28】 URL | Akira #- [ 編集]


はじめまして!
私画像処理を勉強していまして、このたびこちらのサイトのアルゴリズムを参考にラベリング処理を作らせてもらいました
ありがとうございました!
ラベリングの失敗は、Lv2、LvMAX、等で試しましたが発生しませんでした。
【2010/07/23 01:25】 URL | にとり #- [ 編集]


情報ありがとうございます。
あまり理解しきれていませんが、マイクロソフトのサンプルよりも教えて頂いた方のが良さそうな気がします。
ちなみに、教えて頂いた処理は4近傍処理になっていますが、このページの手法だと4近傍処理の時は周辺画素との比較は2方向だけで済みます。
その分だけ有利な点とラベルを振り直す分の処理とで、差し引きどちらが速いか?ってとこですね。
【2010/07/08 21:57】 URL | Akira #- [ 編集]


ここの説明のほうが解り易いかも知れません
http://www7a.biglobe.ne.jp/~fairytale/article/program/graphics.html#region_growing

計算コストは私もよくわかりませんが、region growingの方はテーブルを参照してラベル修正する必要はないのでその分早いかもしれないです。ただ、スタックが多量に必要になるので、メモリの確保、参照の計算は増えると思います。
【2010/07/08 19:55】 URL | #- [ 編集]


情報ありがとうございます。
教えて頂いたregion growingアルゴリズムというのはマイクロソフトのページで紹介されいてるこのページ↓
アルゴリズム入門 : 第 3 章 画像処理入門 1(http://msdn.microsoft.com/ja-jp/academic/cc998604.aspx
のような手法でしょうか?
このやり方は分かり易さの面では良いと思うのですが、処理時間がかかりそうですが、高速化は期待出来るものでしょうか?
テーブルを使う/使わないは、あまりこだわりは無いのですが、良い方があるのなら...
【2010/07/07 21:15】 URL | Akira #- [ 編集]


region growing アルゴリズムなら、テーブルを使わないでいけるんじゃないでしょうか? seedはラスタ走査しながら、すでにラベリングされている画素は選ばないようにして決定。
【2010/07/07 01:15】 URL | #- [ 編集]

Re: ラベリング失敗する例について
お返事が遅くなり申し訳ありません。
ラベリングが失敗する例についてですが、正確には失敗しやすい例ですが、ここでのラベリングの説明では、中心の画像を基準として左上側の画素とラベル番号を比較していくようにしていますが、この左上の4画素の中にラベルング番号が複数存在する場合、比較的失敗しやすいと思います。
処理速度を無視した処理を行うと、失敗する可能性は低くなると思いますが、高速でバグの無い方法は、どれが正解か?いまいち分かっていなかったりもします。
このページに載せている画像データは私が最初、うまくラベリング処理が出来なかった画像ですので、この画像データを使って評価してみて下さい。
評価段階では、エクセルのセルに色を付けながら、ちゃんとラベル番号が割り振られるか?検証してみると分かりやすいと思います。
【2010/06/25 21:28】 URL | Akira #- [ 編集]

ラベリング失敗する例について
大変参考になりますが、
ラベリング失敗例の画素パタンを
具体的に説明して頂けると有り難い
【2010/06/24 11:29】 URL | kkw #VLBf9j/g [ 編集]


テーブルが要らない方法というのは、ランレングス的な処理か、輪郭追跡で行うラベリング処理でしょうか?
何か情報を教えて頂けると助かります。
上記の方法が比較的、一般的な手法かと思っていました。
【2010/06/09 23:31】 URL | Akira #- [ 編集]

ww
v-114てーぶるとかいらねえからwwwwww
しったか乙wwwww
【2010/06/09 18:16】 URL | ふるたに #SFo5/nok [ 編集]


この記事に対するコメントの投稿














管理者にだけ表示を許可する


この記事に対するトラックバック
トラックバックURL
→http://imagingsolution.blog107.fc2.com/tb.php/193-4a5024db
この記事にトラックバックする(FC2ブログユーザー)

現在の閲覧者数: / 合計