(57)【特許請求の範囲】
【請求項１】
２値画像データである入力画像データ内のある画素がユーザーにより指定されたとき、コンピュータによりその画素を含む連結成分を抽出する連結成分抽出方法であって、
前記指定された画素を起点にして、当該画素からその周囲に向かう所定の方向に注目点を移動して境界点を求める処理工程と、
前記境界点から境界追跡をして得られる境界線が前記連結成分の最も外側の境界線であるか判定する処理工程であって、前記指定された画素と境界線上の注目点を結ぶ直線が、境界追跡をする間に、前記指定した画素を中心として360度回転するか否かで、その境界線が連結成分の最も外側の境界線であるか否かを判定する処理工程と、
前記連結成分の最も外側の境界線である場合、その境界線を囲む矩形を生成する処理工程と、
前記矩形を対象として目的の連結成分を生成する処理工程と
を備えたことを特徴とするコンピュータによる連結成分抽出方法。
【請求項２】
２値画像データである入力画像データ内のある画素がユーザーにより指定されたとき、その画素を含む連結成分を抽出する連結成分抽出装置であって、
前記指定された画素を起点にして、当該画素からその周囲に向かう所定の方向に注目点を移動して境界点を求める手段と、
前記境界点から境界追跡をして得られる境界線が前記連結成分の最も外側の境界線であるか判定する手段であって、前記指定された画素と境界線上の注目点を結ぶ直線が、境界追跡をする間に、前記指定した画素を中心として360度回転するか否かで、その境界線が連結成分の最も外側の境界線であるか否かを判定する手段と、
前記連結成分の最も外側の境界線である場合、その境界線を囲む矩形を生成する手段と、
前記矩形を対象として目的の連結成分を生成する手段と
を備えたことを特徴とする連結成分抽出装置。
【請求項３】
２値画像データである入力画像データ内のある画素がユーザーにより指定されたとき、その画素を含む連結成分を抽出するために、コンピュータを、
前記指定された画素を起点にして、当該画素からその周囲に向かう所定の方向に注目点を移動して境界点を求める手段、
前記境界点から境界追跡をして得られる境界線が前記連結成分の最も外側の境界線であるか判定する手段であって、前記指定された画素と境界線上の注目点を結ぶ直線が、境界追跡をする間に、前記指定した画素を中心として360度回転するか否かで、その境界線が連結成分の最も外側の境界線であるか否かを判定する手段、
前記連結成分の最も外側の境界線である場合、その境界線を囲む矩形を生成する手段、および、
前記矩形を対象として目的の連結成分を生成する手段
として機能させるための連結成分抽出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２値画像内の連結成分を効率よく抽出できる連結成分抽出方法、装置、およびプログラムに関する。
【０００２】
【従来の技術】
連結成分抽出とは、２値画像内のある画素を指定して、その画素を含む連結成分を抽出する処理のことである。ある画素に対して、その画素の左右上下斜めに隣接する八つの画素のそれぞれとは８−連結の意味で連結しているという。ある図形が連結成分であるとは、その図形に含まれる任意の二つの画素について、この二つの画素を結ぶ互いに８−連結の意味で連結した画素の組からなる道が図形内に存在していることをいう。ここで、図形とは値１の画素からなる集合を意味する。なお、ある画素の左右上下に隣接する四つの画素で定義される４−連結についても同様の連結成分が定義できる。
【０００３】
連結成分抽出は、衛星画像や医療画像などの画像処理システムにおける基本的かつ重要な処理として広く用いられている。例えば、衛星画像の処理において、ユーザがインタラクティブな画像処理システムで道路や建築物などの対象物をピックアップする際、対象物の一点を指して、対象物全体を獲得する場合などに、連結成分抽出の機能が使用される。連結成分抽出は、極めて基本的な技術であり、その応用分野は物体認識・文字認識・ロボットの視覚情報処理など広範囲に渡る。
【０００４】
連結成分抽出方法として現在のところ最も一般的な手法は、ラスタ走査型ラベリングである。この手法では、まず、１回目の画像のラスタ走査で、注目画素の近傍の画素値を参照して各画素に暫定的なラベルを割り付けると共に、異なる暫定的なラベルが接続する場合には、暫定的なラベルの接続関係のテーブルにその接続関係を登録（あるいは更新）する。次に、先のテーブルを解析し、同一関係にある暫定的なラベルの統合を行い、実ラベルを求める。そして、２回目の画像のラスタ走査で、先のテーブルの解析結果に基づいて、最終結果である各連結成分に実ラベルが付与されたラベル画像を得る。
【０００５】
したがって、従来の手法では、画像全体を２回ラスタ走査し、かつ、暫定的なラベルの解析処理をする必要があった。特に、暫定的なラベルの解析処理は複雑であるので、それをハードウェア化するのは困難である。接続関係のテーブルを一次元配列で表した場合、この解析処理の計算コストは、通常、暫定的なラベルの総数の二乗に比例する。代表的なラスタ走査型ラベリングのアルゴリズムは、例えば、鳥脇純一郎：画像理解のためのディジタル画像処理[II]：昭晃堂（平成３年）などに記載されている。
【０００６】
【発明が解決しようとする課題】
本発明が解決しようとする課題は、連結成分抽出の高速化である。連結成分抽出は、画像処理システムの基本的処理であるので、頻繁に使われる。したがって、その処理効率は画像処理システム全体の処理効率を決める一つの重要な因子である。上述の従来の手法では、指定した画素を含む一個の連結成分を獲得するために、画像中の全ての連結成分を求めるという無駄な処理を行う。その処理のために画像全体を２回走査すると共に、暫定的なラベルの解析処理を行うため、かなりの計算コストを必要とする欠点がある。
【０００７】
本発明は、上述の従来技術における問題点に鑑み、連結成分抽出処理を高速化することを目的とするものである。
【０００８】
【課題を解決するための手段】
上記目的を達成するため、本発明では、なるべく局所的な処理に制限して、画像全体を走査するような全局的処理を避けるようにした。そのために、連結成分の内部に指定した画素を起点にして外側に注目点を移動して、境界点を求め、そこから境界追跡をして連結成分を囲む矩形を獲得する。次に、この矩形内に制限してラスタ走査型ラベリングを実行して連結成分を得る。通常、連結成分を囲む矩形は画像全体と比べてはるかに小さいので、ラスタ走査型ラベリングは高速に行われる。
【０００９】
すなわち、請求項１に係る発明は、２値画像データである入力画像データ内のある画素がユーザーにより指定されたとき、コンピュータによりその画素を含む連結成分を抽出する連結成分抽出方法であって、前記指定された画素を起点にして、当該画素からその周囲に向かう所定の方向に注目点を移動して境界点を求める処理工程と、前記境界点から境界追跡をして得られる境界線が前記連結成分の最も外側の境界線であるか判定する処理工程であって、前記指定された画素と境界線上の注目点を結ぶ直線が、境界追跡をする間に、前記指定した画素を中心として360度回転するか否かで、その境界線が連結成分の最も外側の境界線であるか否かを判定する処理工程と、前記連結成分の最も外側の境界線である場合、その境界線を囲む矩形を生成する処理工程と、前記矩形を対象として目的の連結成分を生成する処理工程とを備えたことを特徴とする。
【００１１】
請求項２に係る発明は、２値画像データである入力画像データ内のある画素がユーザーにより指定されたとき、その画素を含む連結成分を抽出する連結成分抽出装置であって、前記指定された画素を起点にして、当該画素からその周囲に向かう所定の方向に注目点を移動して境界点を求める手段と、前記境界点から境界追跡をして得られる境界線が前記連結成分の最も外側の境界線であるか判定する手段であって、前記指定された画素と境界線上の注目点を結ぶ直線が、境界追跡をする間に、前記指定した画素を中心として360度回転するか否かで、その境界線が連結成分の最も外側の境界線であるか否かを判定する手段と、前記連結成分の最も外側の境界線である場合、その境界線を囲む矩形を生成する手段と、前記矩形を対象として目的の連結成分を生成する手段とを備えたことを特徴とする。
【００１２】
請求項３に係る発明は、２値画像データである入力画像データ内のある画素がユーザーにより指定されたとき、その画素を含む連結成分を抽出するために、コンピュータを、前記指定された画素を起点にして、当該画素からその周囲に向かう所定の方向に注目点を移動して境界点を求める手段、前記境界点から境界追跡をして得られる境界線が前記連結成分の最も外側の境界線であるか判定する手段であって、前記指定された画素と境界線上の注目点を結ぶ直線が、境界追跡をする間に、前記指定した画素を中心として360度回転するか否かで、その境界線が連結成分の最も外側の境界線であるか否かを判定する手段、前記連結成分の最も外側の境界線である場合、その境界線を囲む矩形を生成する手段、および、前記矩形を対象として目的の連結成分を生成する手段として機能させるための連結成分抽出プログラムである。
【００１３】
【発明の実施の形態】
以下、図面を用いて本発明の実施の形態を説明する。
【００１４】
まず、本発明の連結成分抽出法の基本的な手順を図面を用いて説明する。図１(a)は、連結成分抽出の処理対象である２値画像（入力画像）である。この２値画像は、三つの連結成分（網掛けで図示した範囲）を含む。この中で最も大きな連結成分を抽出の対象とする。図１(b)は、対象とする連結成分を囲む矩形を生成する過程を示したものである。まず、連結成分の中央部に画素を指定する。次に、その画素を起点として矢印（図の右方向）に沿って境界点を探索する。次に、見つかった境界点を始点として境界追跡を行い、矩形を生成する。図１(c)は、生成した矩形内を対象としたラスタ走査型ラベリングの結果、最終的に得られた連結成分を示す。
【００１５】
一般に、連結成分は穴を含む場合があるので、境界線は複数個ある。さらに、連結成分が含む穴の中に別の連結成分が存在する場合もあり、その境界線も考慮の対象にしなければならない。連結成分を囲む矩形を求めるためには、これらの境界線の中から最も外側にある境界線を選び出す必要がある。これは指定した画素と境界線上の注目点を結ぶ直線が境界追跡する間に指定した画素を中心として回転する角度を測定して行う。
【００１６】
図２(a)の折れ線ABC...Hは、連結成分の最も外側にある境界線とする。境界線に沿って連結成分を左側に見て境界追跡をすると、連結成分内の点Pに対して、角度
∠APB + ∠BPC + ... + ∠HPA
は明らかに360度になる。一方、図２(b)の折れ線ABC...Hは、連結成分の内側にある境界線とする。前と同様に境界追跡をすると、連結成分内の点Pに対して、角度
∠GPH + ∠HPA + ∠APB + ∠BPC = ∠GPC
と角度
∠CPD + ∠DPE + ∠EPF + ∠FPG = ∠CPG
とは角度の大きさは同一であり、向きは反対である。したがって、角度
∠APB + ∠BPC + ... + ∠HPA
は0度となる。
【００１７】
一般に、最も外側の境界線の場合、この回転角は360度であり、それ以外の境界線の場合、0度であるので、回転角から目的の境界線であるか否かが分かる。
【００１８】
図３は、上述の手順で連結成分の抽出を行う連結成分抽出システムのハードウェアのブロック図である。連結成分抽出システムは、キーボード３０１、マウス３０２、処理装置３０３、記憶装置３０５、および、ディスプレイ３０９を備えている。キーボード３０１は、コマンド名やそのパラメータの入力を行う。マウス３０２は、どの連結成分を抽出すべきかの指示を与える。処理装置３０３は、記憶装置３０５内の画像に対してコマンドで指示された処理を行う。すなわち、連結成分抽出モジュール３０４が、マウス３０２の位置情報と入力画像３０６を入力として、作業画像３０８を使って図１および図２で説明したような処理を行い、出力画像３０７を出力する。ディスプレイ３０９は、キーボード３０１が入力した文字列や処理装置３０３がコマンドを処理した結果などの表示を行う。
【００１９】
図４は、図３のシステムの連結成分抽出モジュール３０４が実行する連結成分抽出のアルゴリズムを示すフローチャートである。なお、ｘｙ座標系は、図の右方向がｘ座標増加方向、下方向がｙ座標増加方向に設定されているものとする。
【００２０】
ステップ４０１と４０２で、ユーザが指定した画素(x0, y0)を注目点(x, y)の初期値とする。次にステップ４０３と４０６により、注目点が境界点になるまで、その注目点をx軸の方向（x座標の増加方向）に一つずつ移動する。ある画素が境界点であるとは、その画素が１画素であり、その画素に隣接する八つの画素の中に０画素と１画素の両方があることと同値である。なお、０画素とは、値が０である画素のことである。１画素とは、値が１である画素のことである。
【００２１】
次に、ステップ４０４で、見つかった境界点を始点(xs, ys)として境界線を一周する。その際、画素(x0, y0)と境界線上の注目点(x, y)を結ぶ直線が回転する角度thetaを求める。ステップ４０５で、角度thetaが360度になっているか否か判定する。360度になっていなければ、ステップ４０６を経てステップ４０３に戻り、再びx軸の方向に境界点を探す。ステップ４０５で角度thetaが360度になっていれば、ステップ４０７で、境界線を囲む矩形についてラスタ走査型ラベリングを適用する。次にステップ４０８で、ラベルの配列の(x0, y0)に位置するラベルLを獲得する。最後にステップ４０９で、ラベルの配列の中で値がLである要素を取り出して、指定した連結成分を１画素とする２値画像を生成する。
【００２２】
図５は、図４中のステップ４０４の境界追跡手続きの詳細を示すフローチャートである。ステップ５０１で、初期設定（図７で後述する）を行う。ステップ５０２で、flagが0であるか否か判定をする。flagは、境界線が孤立点でないときは値0をとり、孤立点であるときは値1をとるフラグである。なお、ある画素が孤立点であるとは、その画素が１画素であり、その画素に隣接する八つの画素が全て０画素であることと同値である。
【００２３】
ステップ５０２でflagが0でなければ、境界線が孤立点であるのでリターンする。0であれば、境界追跡を続ける。ステップ５０３で、注目点の近傍の画素を配列Nに代入するGetNeighbor処理（図８で後述する）を行う。ステップ５０４と５０５で、注目点(x, y)を(old_x, old_y)に保存しておく。ステップ５０６で、方向dをc[d]で置き換える。ここで、方向dは、図６で示す0から7までの値をとる整数である。c[d]は図６中の表の通りである。図８(b)に、方向dの整数の値と方向との関係を示す。すなわち、右方向をd=0とし、そこから反時計回りに、各方向を1,2,…,7で表す。
【００２４】
ここで、ステップ５０６の意味について説明する。本処理では注目点(x, y)を境界線に沿って動かしていくが、注目点(x, y)の設定は、後述する図７の初期設定処理内のステップ７１０，７１１、またはステップ５０９，５１０で行われるので、ステップ５０６に至った時点では、方向dは前の注目点から見て境界線に沿った１画素の方向を示していることになる。すなわち、境界線に沿って第１の注目点から第２の注目点に移動するとすると、ステップ５０６の時点では、方向dには第１の注目点から見た第２の注目点の方向が設定され、(x, y)には第２の注目点の位置が設定されている。このとき、第２の注目点から見た第１の注目点の方向は、方向dの正反対の方向、すなわち(d + 4) % 8である。したがって、第２の注目点から見た０画素の方向は、(d + 4) % 8にさらに１つ反時計回りに進んだ方向になる。これは(d + 5) % 8であり、図６のc[d]はこの値を意味するものである。すなわち、ステップ５０６により、その時点の注目点(x, y)から見た０画素の方向がdに設定されたことになる。なお、A % BはAをBで割った時の余りを示すものである。
【００２５】
ステップ５０７で、N[d]が１画素であるか判定する。１画素でなければ、ステップ５０８で、方向dを反時計回りに一つ進めるために、方向dに(d + 1) % 8を代入し、再びステップ５０７に戻る。ステップ５０７，５０８は、現注目点(x, y)から見た０画素の方向から開始して、注目点の回りを反時計回りに１画素を探す処理である。１画素があれば、その画素に注目点を移動させるため、ステップ５０９で、xにold_x + a[d]を、ステップ５１０で、yにold_y + b[d]をそれぞれ代入する。
【００２６】
なお、a[d]とb[d]の値については、図６に示した。d=０なら、現在の注目点の右側に次の注目点があるということだから、ｘ座標に加算するa[0]=１で、ｙ座標に加算するb[0]=０である。他のdの値についても同様であり、その方向に次の注目点があるので、それに応じた加算値がa[d]とb[d]により得られる。
【００２７】
次に、ステップ５１１で、境界線を囲む矩形を更新する。ステップ５１２で、角度thetaに∠PoldPoPを加える。ここで、P = (x, y)、Po = (x0, y0)、Pold = (old_x, old_y)である。ステップ５１３で、注目点(x, y)が境界追跡の始点(xs, ys)に等しいか判定する。等しくなければ、ステップ５０３に戻って境界追跡を続ける。等しければ、リターンする。
【００２８】
図７は、図５中のステップ５０１の初期設定手続きの詳細を示すフローチャートである。ステップ７０１と７０２で、境界追跡の始点(xs, ys)を注目点(x, y)の値に設定する。ステップ７０３で、注目点(x, y)の近傍の画素を配列Nに代入する。ステップ７０４で、配列Nの中の０画素を取り出す。ステップ７０５で、注目点が孤立点であるか判定する。孤立点でなければ、ステップ７０７に進む。孤立点であれば、ステップ７０６で、注目点(x, y)が最初に指定した画素(x0, y0)に等しいか否かを判定する。等しくなければ、ステップ７１６に進む。等しければ、ステップ７２４に進む。
【００２９】
ステップ７０７では、ステップ７０４で獲得した０画素への方向d0を方向dに代入する。ステップ７０８で、N[d]が１画素であるか判定する。１画素でなければ、ステップ７０９で、方向dを反時計回りに一つ進めるために、方向dに(d + 1) % 8を代入し、ステップ７０８に戻る。ステップ７０８で１画素が発見されたら、その画素を次の注目点とするため、ステップ７１０で、xにx + a[d]を、ステップ７１１で、yにy + b[d]をそれぞれ代入する。
【００３０】
ステップ７１２で、境界線が孤立点でないことを示すために、flagに0を代入する。ステップ７１３で、角度thetaに0を代入する。ステップ７１４から７１７にかけて、矩形のサイズの初期化を行い、リターンする。矩形のサイズの初期化は、xmin，yminにｘ座標とｙ座標の最大値を、xmax，ymaxにｘ座標とｙ座標の最小値を、それぞれ設定するものである。
【００３１】
ステップ７１８では、境界線が孤立点であることを示すために、flagに1を代入する。ステップ７１９で、角度thetaに0を代入する。ステップ７２０から７２３にかけて、矩形のサイズの設定を行い、終了する。
【００３２】
ステップ７２４では、連結成分が指定した画素(x0, y0)から成る孤立点であるので、角度thetaに360を代入する。ステップ７２５から７２８にかけて、矩形のサイズを初期設定して、終了する。
【００３３】
図８(a)は、図５と図７の中のGetNeighbor手続きの詳細を示すフローチャートである。配列Nは、２値画像imageの画素(x, y)の右隣りの画素を始めとして、隣接する八つの画素を反時計回りに並べたものであり、ステップ８０１から８０８でその配列Nの値を設定している。図８(b)は、注目点(x, y)に対する方向dを示したものである。右方向を0として、反時計回りに0から7までの値を取る。
【００３４】
図９は、図５中の矩形処理の詳細を示すフローチャートである。xmin、ymin、xmax、ymaxは、それぞれ、矩形の左端、上端、右端、下端を意味する。ステップ９０１で、xがxminより小さいか判定する。小さければ、ステップ９０２で、xminにxの値を代入する。以下、ymin、xmax、ymaxについて、同様の処理を行う。
【００３５】
【発明の効果】
以上説明したように、本発明によれば、ラスタ走査型ラベリングの処理対象を、画像全体でなく、連結成分を囲む矩形に制限できるので、入力画像の必要最小限の部分をアクセスして連結成分抽出処理するため、効率よく高速に処理を行うことができる。
【図面の簡単な説明】
【図１】連結成分抽出法の基本的な手順を説明するための図
【図２】最も外側の境界線であるか判定する方法を説明するための図
【図３】連結成分抽出システムのハードウェアのブロック図
【図４】連結成分抽出のアルゴリズムを示すフローチャート
【図５】境界追跡手続きのアルゴリズムを示すフローチャート
【図６】方向dと配列a、b、cの関係を示す表を示す図
【図７】初期設定手続きのアルゴリズムを示すフローチャート
【図８】  GetNeighbor手続きのアルゴリズムを示すフローチャートと方向dを説明する図
【図９】矩形処理手続きのアルゴリズムを示すフローチャート
【符号の説明】
３０１…キーボード、３０２…マウス、３０３…処理装置、３０４…連結成分抽出モジュール、３０５…記憶装置、３０９…ディスプレイ。
【図１】
0003909754.tif 000002
【図２】
0003909754.tif 000003
【図３】
0003909754.tif 000004
【図４】
0003909754.tif 000005
【図５】
0003909754.tif 000006
【図６】
0003909754.tif 000007
【図７】
0003909754.tif 000008
【図８】
0003909754.tif 000009
【図９】
0003909754.tif 000010