(57)【要約】【課題】複雑な２値画像のラベリング処理の処理速度を向上させる。【解決手段】２値画像を解析する前処理として、この画像をラベリングする際に、はじめにラベル付けしたラベル画像上で異なるラベル番号が隣接する箇所があったとき、この連結性に着目して、連結したラベル番号の組をテーブルとして記憶し、連結する番号は同一ラベル番号としてこのテーブルを再編成し、最終的に作成されたテーブルに基づいて、はじめにラベル付けしたラベル画像を再ラベリングする装置である。これによって、３次元画像のような複雑な画像を解析する際に必要となる理想的なラベル画像を得るための演算処理がより効率化できる。【選択図】  図７
2004164017.tif 000002
【特許請求の範囲】
【請求項１】
２値画像にラベリング処理を施し、仮ラベル画像を作成する仮ラベル画像作成手段と、
上記仮ラベル画像の異なるラベル番号が連結している箇所のラベル番号を格納した仮ラベルテーブルを作成する仮ラベルテーブル作成手段と、
上記仮ラベルテーブルに基づいて、仮ラベル画像のラベル番号に対する最終ラベル画像のラベル番号を格納した再ラベルテーブルを作成する再ラベルテーブル作成手段と、
上記再ラベルテーブルを参照して、仮ラベル画像のラベル番号を変換し、最終ラベル画像を作成する最終ラベル画像作成手段と
を備えることを特徴とするラベリング処理装置。
【請求項２】
上記仮ラベルテーブル作成手段は、任意の画素のラベル番号と、上記任意の画素の周囲の画素のラベル番号とを比較し、これらのラベル番号が異なる場合、上記任意の画素と異なるラベル番号を上記任意の画素のラベル番号に対応付けて、仮ラベルテーブルに格納することを特徴とする請求項１記載のラベリング処理装置。
【請求項３】
上記２値画像は、３次元画像であり、
上記仮ラベルテーブル作成手段は、上記任意の画素のラベル番号と上記任意の画素の周囲に存在する３×３×２の画素集合のラベル番号とを比較して仮ラベルテーブルを作成することを特徴とする請求項２記載のラベリング処理装置。
【請求項４】
上記再ラベルテーブル作成手段は、上記仮ラベルテーブルに格納された異なるラベル番号が同一のラベル番号に変換されるように、仮ラベル画像のラベル番号と最終ラベル画像のラベル番号との対応を付けることを特徴とする請求項１記載のラベリング処理装置。
【請求項５】
２値画像にラベリング処理を施し、仮ラベル画像を作成する仮ラベル画像作成工程と、
上記仮ラベル画像の異なるラベル番号が連結している箇所のラベル番号を格納した仮ラベルテーブルを作成する仮ラベルテーブル作成工程と、
上記仮ラベルテーブルに基づいて、仮ラベル画像のラベル番号に対する最終ラベル画像のラベル番号を格納した再ラベルテーブルを作成する再ラベルテーブル作成工程と、
上記再ラベルテーブルを参照して、仮ラベル画像のラベル番号を変換し、最終ラベル画像を作成する最終ラベル画像作成工程と
を有することを特徴とするラベリング処理方法。
【請求項６】
上記仮ラベルテーブル作成工程は、上記仮ラベル画像の任意の画素のラベル番号と、上記任意の画素の周囲の画素のラベル番号とを比較し、これらのラベル番号が異なる場合、上記任意の画素とラベル番号の異なるラベル番号を上記任意の画素に対応付けて、仮ラベルテーブルに格納することを特徴とする請求項５記載のラベリング処理方法。
【請求項７】
上記２値画像は、３次元画像であり、
上記任意の画素のラベル番号と上記任意の画素の周囲に存在する３×３×２の画素集合のラベル番号とを比較して仮ラベルテーブルを作成することを特徴とする請求項５記載のラベリング処理方法。
【請求項８】
上記再ラベルテーブル作成工程では、上記仮ラベルテーブルに格納された異なるラベル番号が同一のラベル番号に変換されるように、仮ラベル画像のラベル番号と最終ラベル画像のラベル番号との対応を付けることを特徴とする請求項５記載のラベリング処理方法。
【請求項９】
物体の画像を撮像する撮像手段と、
上記撮像手段によって撮像された画像にラベリング処理を施し、仮ラベル画像を作成する仮ラベル画像作成手段と、
上記仮ラベル画像の異なるラベル番号が連結している箇所のラベル番号を格納した仮ラベルテーブルを作成する仮ラベルテーブル作成手段と、
上記仮ラベルテーブルに基づいて、仮ラベル画像のラベル番号に対する最終ラベル画像のラベル番号を格納した再ラベルテーブルを作成する再ラベルテーブル作成手段と、
上記再ラベルテーブルを参照して、仮ラベル画像のラベル番号を変換し、最終ラベル画像を作成する最終ラベル画像作成手段と
上記ラベル画像をもとに物体の状態を解析する解析手段と
を備えることを特徴とする画像処理装置。
【請求項１０】
上記仮ラベルテーブル作成手段は、任意の画素のラベル番号と、上記任意の画素の周囲の画素のラベル番号とを比較し、これらのラベル番号が異なる場合、上記任意の画素と異なるラベル番号を上記任意の画素に対応付けて、仮ラベルテーブルに格納することを特徴とする請求項９記載の画像処理装置。
【請求項１１】
上記撮像手段により撮像された画像は、３次元画像であり、上記仮ラベルテーブル作成手段は、上記任意の画素のラベル番号と上記任意の画素の周囲に存在する３×３×２の画素集合のラベル番号とを比較して仮ラベルテーブルを作成することを特徴とする請求項９記載の画像処理装置。
【請求項１２】
上記再ラベルテーブル作成手段は、上記仮ラベルテーブルに格納された異なるラベル番号が同一のラベル番号に変換されるように、仮ラベル画像のラベル番号と最終ラベル画像のラベル番号との対応を付けることを特徴とする請求項９記載の画像処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２値画像のラベル付けを行うラベリング処理装置、ラベリング処理方法、並びにこのラベリング処理装置を適用した画像処理装置に関する。
【０００２】
【従来の技術】
従来、２次元画像の画像処理の手法としてラベリング処理がある。ラベリング処理は、画像上の画素の集合（画像上の領域）ごとに番号を付け、画像を領域ごとに分類する処理であり、ラベリング処理によって付けられたラベル番号ごとに１次又は２次のモーメント、面積や周囲長などの特徴量や画像領域の連結性を求めることができる。
【０００３】
この手法は、３次元画像の解析に対しても有効な画像処理であり、例えば、３次元ＣＴスキャンで物体の３次元画像を取得し、この物体の体積や重心、モーメント等の特徴量を求めたり、物体の連結性を検査する際にも、重要な前処理として用いることができる。
【０００４】
【発明が解決しようとする課題】
上述のように、ラベリング処理は、特に、画像解析処理の前処理として重要な処理であるが、対象とする画像の情報量が多くなるほど演算量が増え、この処理に多大な時間を要する。
【０００５】
本発明は、上記した従来の実情に鑑みてなされたものであって、ラベリング処理の処理速度を向上させるラベリング処理装置、ラベリング処理方法、並びに画像処理装置を提供することを目的とする。
【０００６】
【課題を解決するための手段】
上述した課題を解決するため、本発明にかかるラベリング処理装置は、２値画像にラベリング処理を施し、仮ラベル画像を作成する仮ラベル画像作成手段と、仮ラベル画像の異なるラベル番号が連結している箇所のラベル番号を格納した仮ラベルテーブルを作成する仮ラベルテーブル作成手段と、仮ラベルテーブルに基づいて、仮ラベル画像のラベル番号とラベル画像のラベル番号とを対応付けて格納した再ラベルテーブルを作成する再ラベルテーブル作成手段と、再ラベルテーブルを参照して、仮ラベル画像のラベル番号をラベル画像のラベル番号に変換するラベル画像作成手段とを備える。
【０００７】
また、本発明にかかるラベリング処理方法は、２値画像にラベリング処理を施し、仮ラベル画像を作成する仮ラベル画像作成工程と、仮ラベル画像の異なるラベル番号が連結している箇所のラベル番号を格納した仮ラベルテーブルを作成する仮ラベルテーブル作成工程と、仮ラベルテーブルに基づいて、仮ラベル画像のラベル番号とラベル画像のラベル番号とを関連付けて格納した再ラベルテーブルを作成する再ラベルテーブル作成工程と、再ラベルテーブルを参照して、仮ラベル画像のラベル番号を最終的なラベル番号に変換し、最終ラベル画像を作成する最終ラベル画像作成工程とを有する。
【０００８】
また、本発明にかかる画像処理装置は、物体の画像を撮像する撮像手段と、撮像手段によって撮像された画像にラベリング処理を施し、仮ラベル画像を作成する仮ラベル画像作成手段と、仮ラベル画像の異なるラベル番号が連結している箇所のラベル番号を格納した仮ラベルテーブルを作成する仮ラベルテーブル作成手段と、仮ラベルテーブルに基づいて、仮ラベル画像のラベル番号とラベル画像のラベル番号とを対応付けて格納した再ラベルテーブルを作成する再ラベルテーブル作成手段と、再ラベルテーブルを参照して、仮ラベル画像のラベル番号を最終的なラベル番号に変換し、最終ラベル画像を作成する最終ラベル画像作成手段とラベル画像をもとに物体の異常を検出する解析手段とを備える。
【０００９】
【発明の実施の形態】
本発明の具体例として示すラベリング処理装置１は、２値画像を解析する前処理として、この画像をラベリングする際に、はじめにラベル付けしたラベル画像上で異なるラベル番号が隣接する箇所があったとき、この連結性に着目して、連結したラベル番号の組をテーブルとして記憶し、連結する番号は同一ラベル番号としてこのテーブルを再編成し、最終的に作成されたテーブルに基づいて、はじめにラベル付けしたラベル画像を再ラベリングする装置である。これによって、３次元画像のような複雑な画像を解析する際にラベル画像を得るための演算処理がより効率化できる。
【００１０】
以下、図面を参照して本発明を適用したラベリング処理装置１について説明する。本発明を適用したラベリング処理装置１を図１を用いて説明する。本具体例でラベリングする画像は、画像解析の対象である物体とこの物体以外の部分（以下、背景と記す。）とを含む２値画像である。また、ここでは、ラベリング処理が複雑とされる３次元画像に対して本手法を適用した例について説明する。
【００１１】
ラベリング装置１は、２値画像をもとに仮ラベル画像及び仮ラベルテーブルを作成する仮ラベル画像作成部１２と、上記仮ラベル画像作成部１２によって作成された仮ラベルテーブルをもとに最終ラベルテーブルを作成する再ラベルテーブル作成部１３と、最終ラベルテーブルの記載をもとに仮ラベル画像のラベル番号を変換しラベル画像を作成するラベル画像作成部１４と、仮ラベルテーブル、仮ラベル画像、最終ラベルテーブル等を記憶する記憶部１５とを備える。
【００１２】
また、これらの各部は、図示しない制御部によって統括制御されている。制御部は、単体で設けられ各部を一括して制御する形態であってもよいし、各部ごとに分散して設けてもよい。
【００１３】
入力部１１は、外部から入力された２値画像を仮ラベル画像作成部１２に出力する。２値画像は、図２に示すように、０と１との２値で表現した画像であり、図２の例では、０が背景、１が物体に対応している。２値画像では、撮像された物体は分類されておらず、物体か背景かの２つに分類されている。
【００１４】
仮ラベル画像作成部１２は、２値画像を所定のラベリング規則に従い上から順にラベリングし、領域ごとにラベル番号を付けていく。ここで領域ごとにラベル番号が付けられた画像を仮ラベル画像という。図３は、仮ラベル画像の一例を示している。図３の仮ラベル画像において、上述したように、ラベル番号０である部分は、画像の背景であるから、この仮ラベル画像の物体部分は、ラベル番号１〜６の領域で分類されることになる。仮ラベル画像のラベル番号は、一時的に付けられたラベル番号であり、後の処理によって、ラベル番号が変換され、最終的なラベル画像が作成される。
【００１５】
また、仮ラベル画像作成部１２は、仮ラベル画像を作成するとき、異なるラベル番号が連結した場合、この連結した異なるラベル番号の対応関係を図４に示す仮ラベルテーブルとして記憶する。仮ラベルテーブルは、仮ラベル画像に付けられたラベル番号のうち、異なるラベル番号が連結した箇所のラベル番号の対応関係を格納している。
【００１６】
図３の仮ラベル画像及び図４の仮ラベルテーブルを例とすると、図３の仮ラベル画像では、２行５列目のラベル番号「２」の画素と、３行４列目のラベル番号「１」の画素が斜め上下に連結している。そのため、図４の仮ラベルテーブルの１行目には、ラベル番号「１」に対応してラベル番号「２」が格納される。
【００１７】
再ラベルテーブル作成部１３は、仮ラベル画像作成部１２で作成された仮ラベルテーブルをもとに、最終ラベルテーブルを作成する。最終ラベルテーブルは、図５に示すように、仮ラベル画像のラベル番号λとラベル画像のラベル番号Ｗ（λ）とを対応付けて格納している。
【００１８】
ラベル番号作成部は、最終ラベルテーブルの記載に従い、仮ラベル画像のラベル番号λをＷ（λ）に変換し、ラベル画像を作成する。この処理により、異なるラベル番号の画素が連結した箇所がなくなり、連結した画素には同一のラベル番号が付けられる。
【００１９】
上述の仮ラベル作成部、再ラベルテーブル作成部１３、ラベル画像作成部１４の処理は、ソフトウェア的に実現することもできる。この場合、ラベリング処理装置１の構成は、図６のようになる。このラベリング処理装置１は、処理プログラムや作業用の記憶領域を含むメモリ２１と、メモリ２１に格納されたプログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２２と、ＣＰＵ２２と他の各部とのデータの入出力を管理するＩ／Ｏ制御部２３とを備える。
【００２０】
メモリ２１には、プログラムエリアとデータエリアとがそれぞれ異なる領域として設けられている。プログラムエリアには、ＣＰＵ２２によって読み込まれる制御プログラムとラベリング処理を行うプログラム等が格納されている。データエリアには、仮ラベル画像、仮ラベルテーブル、最終ラベルテーブル等のデータが格納される。ラベリング処理を行うプログラムは、仮ラベル画像および仮ラベルテーブルを作成するプログラム、最終ラベルテーブルを作成するプログラム、ラベル画像を作成するプログラム等から構成される。
【００２１】
ラベリング処理は、図７のフローチャートに示すアルゴリズムに従い記述されている。ラベリング処理のアルゴリズムについて説明する。
【００２２】
【００２３】
ただし、（ｉ，ｊ，ｋ）：画像のＸＹＺ座標
Ｆ＝｛ｆｉｊｋ｝：入力２値画像
Ｌ＝｛ｌｉｊｋ｝：ラベル画像。ｌｉｊｋは、ラベル番号を表す正整数（Ｆ０００にはラベル番号として０が入る。）
λ            ：仮ラベル画像のラベル番号（以下、連結成分と記す）
Ｋ［γ，２］  ：仮ラベルテーブル（ただし、Ｋ［γ，０］＜Ｋ［γ，１］）
Ｔ［ｉ］      ：再ラベルテーブル
Ｗ［ｉ］      ：最終ラベルテーブル
【００２４】
まず、仮ラベル画像作成部１２が仮ラベルテーブル及び仮ラベル画像を作成するアルゴリズムについて説明する。仮ラベル画像作成部１２は、初めに、λ、γ、Ｔ［ｉ］、ｉの変数に０を入力し、変数値の初期設定を行う（ステップＳ１）。
【００２５】
次いで、仮ラベル画像作成部１２は、入力２値画像ｆｉｊｋの値をチェックし（ステップＳ２）、入力２値画像ｆｉｊｋの値が０のとき、ラベル画像ｌｉｊｋの値を０にし、ステップＳ１２に処理を移行する。一方、ステップＳ２において、入力２値画像ｆｉｊｋの値が１のとき、ステップＳ４に処理を移行する。
【００２６】
仮ラベル画像作成部１２は、３次元画像に対して３×３×２画素のマスクを生成し、マスク内のラベルを走査し、異なるラベル番号のラベルが連結している箇所を検出する。図８（ａ）は、走査済みの画素Ｘ１〜Ｘ１３を示している。図８（ｂ），（ｃ），（ｄ）は、図８（ａ）を手前から順に縦に分解した図であり、図８（ｂ），（ｃ），（ｄ）は、仮ラベル画像作成部１２がマスク内の画素を走査していく順番Ｘ１，Ｘ２，…，Ｘ１３を示している。仮ラベル画像作成部１２は、ラベル付けの対象となる画素Ｘ０＝（ｉ，ｊ，ｋ）と、マスク内の画素Ｘ１，Ｘ２，…，Ｘ１３のラベル番号を画素番号の順に比較する。ステップＳ４において検出された異なるラベル番号をＬ１、Ｌ２、…、Ｌｎと記す（０＜Ｌ１＜Ｌ２＜…＜Ｌｎ）。
【００２７】
ステップＳ５及びステップＳ６では、検出されたラベルの個数をチェックする。仮ラベル画像作成部１２は、ステップＳ５において、ステップＳ４で検出したラベル番号Ｌ１、Ｌ２、…、Ｌｎが２つ以上（ｎ≧２）であるか否かをチェックし、ｎ≧２の場合（ステップＳ５；ＹＥＳ）、ステップＳ９に処理を移行する。
一方、ステップＳ４で検出したラベル番号の個数が０又は１の場合（ステップＳ５；ＮＯ）、ステップＳ６に処理を移行する。
【００２８】
ステップＳ６では、ステップＳ４で検出したラベル番号Ｌ１、Ｌ２、…、Ｌｎの個数が０か否かをチェックし、ラベル番号の個数が０個（ｎ＝０）の場合（ステップＳ６；ＹＥＳ）、ステップＳ７に処理を移行する。一方、ステップＳ４で検出したラベル番号Ｌ１、Ｌ２、…、Ｌｎの個数が１個（ｎ＝１）の場合（ステップＳ６；ＮＯ）、ステップＳ８に処理を移行する。
【００２９】
ステップＳ７では、連結成分λの値を１つインクリメントし、λを画素ｆｉｊｋのラベル番号ｌｉｊｋに入力する（ステップＳ７）。また、ステップＳ８では、対象画素Ｘ０連結するラベルのラベル番号Ｌ１を画素ｆｉｊｋのラベル番号ｌｉｊｋに入力する。
【００３０】
一方、ステップＳ９では、連結した複数のラベル番号Ｌ１、Ｌ２、…、Ｌｎのうち、最も値の小さいラベル番号Ｌ１を画素ｆｉｊｋのラベル番号ｌｉｊｋに入力し、ステップＳ１０に処理を移行する。
【００３１】
ステップＳ１０では、一つ前の画素の時のラベル番号Ｌ１、Ｌ２、…、Ｌｎと現画素のラベル番号Ｌ１、Ｌ２、…、Ｌｎとの比較を行ない、対応する値がすべて同じ値であれば（ステップＳ１０；ＹＥＳ）、ステップＳ１２に処理を移行し、ラベル番号に異なる値が存在する場合には（ステップＳ１０；ＮＯ）、ステップＳ１１に処理を移行する。
【００３２】
ステップＳ１１では、仮ラベルテーブルの作成を行う。仮ラベルテーブルの作成では、Ｋ［γ，０］にラベル番号Ｌ１を入力し、Ｋ［γ，１］にラベル番号Ｌ２，…，Ｌｎのラベル番号Ｌｊ（２≦ｊ≦ｎ）を順に入力する。このとき、Ｌ１とＬｊとのセットを１つ格納するごとにγの値を１つインクリメントし、仮ラベルテーブルの１レコードを作成する。ラベル番号Ｌ２〜Ｌｎ全てのラベル番号に対するレコードを作成すると、現在の画素に対する仮ラベルテーブルの生成を終了し、ステップＳ１２に処理を移行する。
【００３３】
ステップＳ１２では、入力２値画像の画素ｆｉｊｋ全てに対してステップＳ２〜ステップＳ１１までの処理が施されたか否かをチェックし、まだ処理が施されていない画素ｆｉｊｋがある場合には（ステップＳ１２；ＮＯ）、次の画素ｆｉｊｋを読み出して、ステップＳ２に処理を移行する。一方、全ての画素ｆｉｊｋに対して、ステップＳ２〜ステップＳ１１までの処理が施された場合（ステップＳ１２；ＹＥＳ）、ステップＳ１４に処理を移行する。
【００３４】
ステップＳ１４では、仮ラベルテーブルをもとに再ラベルテーブルを作成する。ステップＳ１４において、再ラベルテーブルが作成されると、作成した再ラベルテーブルをもとに最終ラベルテーブルを作成し（ステップＳ１５）、最終ラベルテーブルと仮ラベル画像をもとに最終的なラベル画像を作成する。
【００３５】
続いて、再ラベルテーブル作成部１３が再ラベルテーブルを作成するアルゴリズムについて図９〜図１４を参照して説明する。ここで、仮ラベルテーブルの値Ｋ［ｉ，０］をｍ、Ｋ［ｉ，１］をｎ、添え字ｍの仮再ラベルテーブルの値Ｔ［ｍ］＝ｋ、添え字ｎの再ラベルテーブルの値Ｔ［ｎ］＝ｌとおく。
【００３６】
再ラベルテーブルを作成する際、まず、再ラベルテーブルＴ［１］，Ｔ［２］，Ｔ［３］，…，Ｔ［ｈ］の全ての値を０に初期化する。そして、仮ラベルテーブルの値ｍ、ｎを入力し、以下に示す規則に従い、再ラベルテーブルの値を更新する。
【００３７】
再ラベルテーブルを更新する規則について説明する。この規則は、仮ラベルテーブルの値ｍ、ｎを添え字とする再ラベルテーブルＴ［ｍ］及びＴ［ｎ］の組み合わせに従って、決められている。再ラベルテーブルの値Ｔ［ｍ］、Ｔ［ｎ］の組み合わせには、Ｔ［ｍ］＝０かつＴ［ｎ］＝０、Ｔ［ｍ］≠０かつＴ［ｎ］＝０、Ｔ［ｍ］＝０かつＴ［ｎ］≠０、Ｔ［ｍ］≠０かつＴ［ｎ］≠０の４通りある。
【００３８】
Ｔ［ｍ］＝０かつＴ［ｎ］＝０のときには、Ｔ［ｍ］及びＴ［ｎ］にｍをセットする。図９の例では、更新前の再ラベルテーブルの値は、Ｔ［１］＝０、Ｔ［２］＝０、Ｔ［３］＝０であり、入力される仮ラベルテーブルの値は、ｍ＝１、ｎ＝２である。このとき、Ｔ［１］＝０及びＴ［２］＝０であり、Ｔ［ｍ］＝０かつＴ［ｎ］＝０を満たす。そこで、Ｔ［１］及びＴ［２］に１をセットする。
この処理の結果、更新後の再ラベルテーブルの値は、Ｔ［１］＝１、Ｔ［２］＝１、Ｔ［３］＝０となる。
【００３９】
また、Ｔ［ｍ］≠０かつＴ［ｎ］＝０のときには、Ｔ［ｍ］の値ｋをＴ［ｎ］にセットする。図１０の例では、更新前の再ラベルテーブルの値は、Ｔ［１］＝１、Ｔ［２］＝１、Ｔ［３］＝０であり、入力される仮ラベルテーブルの値は、ｍ＝２、ｎ＝３である。このとき、Ｔ［２］＝１及びＴ［３］＝０であり、Ｔ［ｍ］≠０かつＴ［ｎ］＝０を満たす。そこで、Ｔ［３］にＴ［２］の値をセットする。この処理の結果、更新後の再ラベルテーブルの値は、Ｔ［１］＝１、Ｔ［２］＝１、Ｔ［３］＝１となる。
【００４０】
また、Ｔ［ｍ］＝０かつＴ［ｎ］≠０の場合には、ｍ＜ｌ、ｍ＞ｌの２つの場合に場合分けして、再ラベルテーブルを生成する。なお、ｍ＝ｌの場合は存在しない。
【００４１】
ｍ＜ｌの場合、Ｔ［ｍ］にｍをセットし、Ｔ［ｉ］＝ｌである全てのＴ［ｉ］にｍをセットする。図１１の例では、更新前の再ラベルテーブルの値は、Ｔ［１］＝０、Ｔ［２］＝２、Ｔ［３］＝２であり、入力される仮ラベルテーブルの値は、ｍ＝１、ｎ＝２である。このとき、Ｔ［１］＝０及びＴ［２］＝２であり、Ｔ［ｍ］＝０かつＴ［ｎ］≠１を満たす。また、ｍ＝１及びｌ＝２であるため、ｍ＜ｌを満たす。そこで、Ｔ［１］に１をセットし、Ｔ［ｉ］＝ｌである全てのＴ［ｉ］、すなわち、Ｔ［２］及びＴ［３］に１をセットする。この処理の結果、更新後の再ラベルテーブルの値は、Ｔ［１］＝１、Ｔ［２］＝１、Ｔ［３］＝１となる。
【００４２】
ｍ＞ｌの場合、Ｔ［ｍ］にｌをセットする。図１２の例では、更新前の再ラベルテーブルの値は、Ｔ［１］＝１、Ｔ［２］＝０、Ｔ［３］＝１であり、入力される仮ラベルテーブルの値は、ｍ＝２、ｎ＝３である。このとき、Ｔ［２］＝０及びＴ［３］＝１であり、Ｔ［ｍ］＝０かつＴ［ｎ］≠０を満たす。また、ｍ＝２及びｌ＝１であるため、ｍ＞ｌを満たす。そこで、Ｔ［２］に１をセットする。この処理の結果、更新後の再ラベルテーブルの値は、Ｔ［１］＝１、Ｔ［２］＝１、Ｔ［３］＝１となる。
【００４３】
また、Ｔ［ｍ］≠０かつＴ［ｎ］≠０の場合には、ｋ＜ｌ、ｋ＞ｌ、ｋ＝ｌの３つの場合に場合分けして、再ラベルテーブルを生成する。
【００４４】
ｋ＜ｌの場合、Ｔ［ｉ］＝ｌを満たす全てのＴ［ｉ］にｋをセットする。図１３の例では、更新前の再ラベルテーブルの値は、Ｔ［１］＝１、Ｔ［２］＝１、Ｔ［３］＝３、Ｔ［４］＝３であり、入力される仮ラベルテーブルの値は、ｍ＝１、ｎ＝３である。このとき、Ｔ［１］＝１及びＴ［３］＝３であるため、Ｔ［ｍ］≠０かつＴ［ｎ］≠０を満たす。また、ｋ＝１及びｌ＝３であるため、ｋ＜ｌを満たす。そこで、Ｔ［ｉ］＝ｌであるＴ［ｉ］、すなわち、Ｔ［３］及びＴ［４］に１をセットする。この処理の結果、更新後の再ラベルテーブルの値は、Ｔ［１］＝１、Ｔ［２］＝１、Ｔ［３］＝１、Ｔ［４］＝１となる。
【００４５】
ｋ＞ｌの場合、Ｔ［ｉ］＝ｋを満たす全てのＴ［ｉ］にｌをセットする。図１４の例では、更新前の再ラベルテーブルの値は、Ｔ［１］＝１、Ｔ［２］＝２、Ｔ［３］＝２、Ｔ［４］＝１であり、入力される仮ラベルテーブルの値は、ｍ＝２、ｎ＝４である。このとき、Ｔ［２］＝２及びＴ［４］＝１であるため、Ｔ［ｍ］≠０かつＴ［ｎ］≠０を満たす。また、ｋ＝２及びｍ＝１であるため、ｋ＞ｌを満たす。そこで、Ｔ［ｉ］＝ｋである全てのＴ［ｉ］、すなわち、Ｔ［２］及びＴ［３］に１をセットする。この処理の結果、更新後の再ラベルテーブルの値は、Ｔ［１］＝１、Ｔ［２］＝１、Ｔ［３］＝１、Ｔ［４］＝１となる。
【００４６】
ｋ＝ｌの場合、再ラベルテーブルＴ［１］，Ｔ［２］，…，Ｔ［ｈ］には、特に処理を施さない。
【００４７】
次に、再ラベルテーブル作成部１３が最終ラベルテーブルＷ［ｉ］を作成するアルゴリズムを説明する。最終ラベルテーブルＷ［ｉ］を作成するためには、その途中経過として第１中間テーブルＵ［ｉ］、第２中間テーブルＶ［ｉ］を作成し、最終ラベルテーブルを作成する。
【００４８】
第１中間テーブルを作成するアルゴリズムを説明する。第１中間ラベルテーブルＵ［ｉ］は、仮ラベルテーブルＴ［ｉ］をもとに作成される。仮ラベルテーブルＴ［ｉ］＝ｉならばＵ［ｉ］＝１になり、Ｔ［ｉ］≠ｉならばＵ［ｉ］＝０となる。図１５の例では、ｉ＝１，４，５のときＴ［ｉ］＝ｉが成立するので、Ｕ［ｉ］に１がセットされる。また、ｉ＝２，３，６のとき、Ｔ［ｉ］≠ｉであるためにＵ［ｉ］に０がセットされる。
【００４９】
第２中間テーブルを作成するアルゴリズムを説明する。第２中間テーブルを作成する際、第１中間テーブルＵ［ｉ］の１の個数を記憶するカウンタｐをメモリに確保し、第１中間テーブルＵ［ｉ］が０か１かをチェックし、第１中間テーブルＵ［ｉ］＝１であるとき、ｐの値を１インクリメントするとともに、ｐの値を第２中間テーブルＶ［ｉ］にセットする。
【００５０】
図１５の第１中間テーブルから第２中間テーブルを作成する場合、まず、Ｕ［１］が１か０かをチェックする。図１５の例では、Ｕ［１］＝１である。ｐの初期値０を１インクリメントし、Ｖ［１］にｐの値１をセットする。続いて、Ｕ［２］，Ｕ［３］が１か０かをチェックする。Ｕ［２］＝Ｕ［３］＝０である。そこで、Ｖ［２］，Ｖ［３］に０をセットする。続いて、Ｕ［４］が１か０かをチェックすると、Ｕ［４］＝１である。そこで、ｐを１インクリメントしＶ［４］に２をセットする。上記の処理を全ての第１中間テーブルに対して施し、第２中間テーブルが完成する。
【００５１】
次に、最終ラベルテーブルＷ［ｉ］を作成するアルゴリズムを説明する。最終ラベルテーブルは、仮ラベルテーブルＴ［ｉ］の値を添え字とした第２中間テーブル、すなわちＷ［ｉ］＝Ｖ［Ｔ［ｉ］］として生成される。
【００５２】
図１５では、ｉ＝１のとき、Ｔ［１］＝１である。そこで、Ｗ［１］にＶ［１］＝１をセットする。ｉ＝２のとき、Ｔ［２］＝１である。そこで、Ｗ［２］にＶ［１］＝１をセットする。この処理を全てのｉに対して施し、最終ラベルテーブルＷ［ｉ］が完成する。
【００５３】
このように、最終ラベルテーブルが完成すると、ラベル画像作成部１４は、最終ラベルテーブルと仮ラベル画像とをもとに、ラベル画像を作成する。例えば、図１５の最終ラベルテーブルでは、仮ラベル画像のラベル番号λとし、ラベル画像のラベル番号Ｗ［λ］が対応付けて格納されている。ラベル画像作成部１４は、仮ラベル画像のラベル番号λをＷ（λ）に変換し、ラベル画像を作成する。図１５の最終ラベルテーブルにおいて、λ＝２、Ｗ（λ）＝１である。そのため、ラベル画像作成部１４は、図３の仮ラベル画像の２行５列目のラベル番号２を１に変換する。また、また、図１５の最終ラベルテーブルにおいて、λ＝３、Ｗ（λ）＝１である。そのため、ラベル画像作成部１４は、図３の仮ラベル画像の４行１列目、４行２列目、５行２列目の３を１に変換する。このようにして作成されたラベル画像は、画像を構成する物体ごとに１から順にラベリングされており、背景には０が割り当てられている。
【００５４】
以上のようなラベリング処理装置１は、例えば、３次元ＣＴスキャンを用いた画像処理装置に適用される。図１６に、この画像処理装置３の一例を示す。この画像処理装置は、ラベリング処理装置をラベリング部として適用している。
【００５５】
画像処理装置３は、物体の３次元画像を撮像する撮像部３１と、撮像した画像にラベリング処理を施すラベリング部３２、ラベリングした物体の形状をもとに物体の歪みや破損を検出する解析部３３とを備える。
【００５６】
この画像処理装置３の検査の例として、ＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）のボールグリッドアレイの検査を説明する。ボールグリッドアレイは、図１７（ａ）に示すように、ＩＣの端子の先をボール状に加工したものである。このようなボールグリッドアレイは、ＩＣの底面に格子状に形成される。ボールグリッドアレイは、製造した後にボールの状態を外部から検査することができない。また、微小なものであるため、目視による検査も困難である。そこで、Ｘ線を用いた３次元ＣＴスキャン等で内部画像を得て、これを解析して不良を検査している。ラベリング処理部３２は、画像解析の前処理としてボールグリッドアレイの形状を特定するために使用される。
【００５７】
図１７（ｂ）及び図１７（ｃ）は、ボールグリッドアレイの一部を撮像したＣＴスキャン写真を模式的に表している。ここで、図１７（ｂ）は、隣接するボール同士が接合した状態を示し、図１７（ｃ）は、ボール内に空隙が生じた状態を示している。
【００５８】
ラベリング部３２は、図１７（ｂ）及び図１７（ｃ）のボールグリッドアレイのボール部分とその他の部分とが検出される。例えば、図１７（ａ）のように、隣接ボール同士が接合している場合や、ボール内部に空隙が生じた場合などには、接合した部分には同一のラベル番号を付し、空隙にはボールと異なるラベル番号を付す。ボールが接合したいる場合や、ボール内部に空隙が生じた場合などには、正常なボールグリッドアレイのラベル画像と比較して、ラベル番号が変わってくる。
【００５９】
解析部３３は、正常なボールグリッドアレイのラベル画像や、このラベル画像をもとに算出した特徴量を予め記憶し、ラベリング部から出力されたラベル画像と比較し、ボールグリッドアレイの異常を検査する。
【００６０】
また、ラベリング装置１を適用した画像処理装置３は、リチウム乾電池のリード部分の接合状態の検査、ＬＥＤのリード部分の接合状態の検査等、非破壊検査の画像解析の前処理として適用できる。
【００６１】
以上のように、本発明を適用したラベリング処理装置１は、単純なアルゴリズムでラベリング処理を実行するため、ソフトウェアの処理速度が速くなる。これにより、検査時間が短縮できるなどの効果がある。
【００６２】
また、このアルゴリズムをハードウェアで実現した場合、アルゴリズムが単純なため、ハードウェアが容易に開発できるとともに、ハードウェアの処理速度を向上することができる。
【００６３】
なお、本発明は、上述した実施の形態に限定されることはない。例えば、画像処理装置の撮像部は、ＣＴスキャンとしたが、ＣＴスキャン以外の装置を用いて３次元画像を撮像してもよい。
【００６４】
【発明の効果】
上述したように、本発明に係るラベリング処理装置は、仮ラベル画像を作成した後、最終的なラベル画像を作成する。仮ラベル画像を作成する際、ラベリング処理装置は、仮ラベル画像上で異なるラベル画像が連結する箇所があった場合、連結したラベル番号の組を仮ラベルテーブルに記憶する。ラベリング処理装置は、仮ラベルテーブルを再編成し、最終的に作成されたテーブルに基づいて、仮ラベル画像を再ラベリングし、ラベル画像を作成する。
【００６５】
これにより、ラベリング装置は、ラベリング処理に必要な演算量が減少し、処理速度が向上し、ラベリング処理の実行にかかる時間を短縮できる。また、ラベリング処理をハードウェアで実現する場合には、ハードウェアを容易に開発することできるとともに、ハードウェアの処理速度を向上することができる。
【図面の簡単な説明】
【図１】ラベリング処理装置の構成を示す図である。
【図２】ラベリング処理装置に入力される２値画像の１例を示す図である。
【図３】仮ラベル画像の１例を示す図である。
【図４】仮ラベルテーブルの１例を示す図である。
【図５】再ラベルテーブルの１例を示す図である。
【図６】ラベリング処理をソフトウェアで実行する際のラベリング処理装置の構成を示す図である。
【図７】ラベリング処理の手順を示すフローチャートである。
【図８】マスク内の画素を示す図である。
【図９】再ラベルテーブルの作成規則を示す図である。
【図１０】再ラベルテーブルの作成規則を示す図である。
【図１１】再ラベルテーブルの作成規則を示す図である。
【図１２】再ラベルテーブルの作成規則を示す図である。
【図１３】再ラベルテーブルの作成規則を示す図である。
【図１４】再ラベルテーブルの作成規則を示す図である。
【図１５】再ラベルテーブル、第１中間テーブル、第２中間テーブル、および最終ラベルテーブルの１例を示す図である。
【図１６】画像処理装置の構成を示す図である。
【図１７】ボールグリッドアレイの形状を示す図である。
【符号の説明】
１  ラベリング装置、３  画像処理装置、１２  仮ラベル画像作成部、１３  再ラベルテーブル作成部、１４  ラベル画像作成部、１５  記憶部、３１  撮像部、３２  ラベリング部、３３  解析部
【図１】
2004164017.tif 000003
【図２】
2004164017.tif 000004
【図３】
2004164017.tif 000005
【図４】
2004164017.tif 000006
【図５】
2004164017.tif 000007
【図６】
2004164017.tif 000008
【図７】
2004164017.tif 000009
【図８】
2004164017.tif 000010
【図９】
2004164017.tif 000011
【図１０】
2004164017.tif 000012
【図１１】
2004164017.tif 000013
【図１２】
2004164017.tif 000014
【図１３】
2004164017.tif 000015
【図１４】
2004164017.tif 000016
【図１５】
2004164017.tif 000017
【図１６】
2004164017.tif 000018
【図１７】
2004164017.tif 000019