画像認識方法
【課題】連結領域を含む２値画像に対して、汎用的に画像の構造を記述する方法、および同方法を用いた画像認識方法を提供する。
【解決手段】ある領域の支配域は当該領域に属する全ての画素の支配域の和である、という規則により、連結領域に対して計算幾何学の基礎概念「ボロノイ図」「ドローネグラフ」を拡張する。これにより、多数の領域からなる２値画像に対して「領域ドローネグラフ」が作成できる。認識対象となる物体についても、その構造を予めグラフ構造として規定しておき、これと上記「領域ドローネグラフ」とのマッチングをグラフ上で行う事で、当該物体を認識する機能が実現できる。以上により、２値画像の中から人物の顔など特定の構造を有する物体を、効率的に認識できる。
【解決手段】ある領域の支配域は当該領域に属する全ての画素の支配域の和である、という規則により、連結領域に対して計算幾何学の基礎概念「ボロノイ図」「ドローネグラフ」を拡張する。これにより、多数の領域からなる２値画像に対して「領域ドローネグラフ」が作成できる。認識対象となる物体についても、その構造を予めグラフ構造として規定しておき、これと上記「領域ドローネグラフ」とのマッチングをグラフ上で行う事で、当該物体を認識する機能が実現できる。以上により、２値画像の中から人物の顔など特定の構造を有する物体を、効率的に認識できる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はディジタル画像認識技術に係り、特に予め規定された構造物が２値画像の中に含まれるか否かを判定する方法に関する。
【背景技術】
【０００２】
発明者は既に特許文献１において、２値画像の中から特定の形状の線分（曲線を含む）を抽出する方法（以下「従来法」と記す）を開示している。従来法は、ノイズの影響で線分に途切れが生じた場合に、ある線分の端点を近隣の線分の端点と結ぶ事により、途切れを補うものである。ここで、どの端点同士をペアにして結べば良いかを効率的に決定するために、計算幾何学の手法を応用している。
【０００３】
すなわち図１７に示す通り、特許文献１においては医療用Ｘ線写真から胃の外形線を抽出する事を目的として、まず入力画像のエッジ部分を強調した画像（図１７（ａ））を用意し、これに対して線分追跡処理を行う。しかしながら画像には胃１７０１以外に脊椎１７１１が映っており、またノイズ領域１７１２等が存在する。このため線分追跡処理のみでは外形線１７３１を完全には抽出できず、図１７（ｂ）に示す通り外形線の局所的な断片１７０２−１等が抽出されたり、余分な線分１７０９等が抽出されたりする。そこでこれらの線分の端点１７０３−１等に対して、計算幾何学の手法によりドローネグラフ（図１７（ｃ））を作成する事により、たとえば端点１７０３−２と１７０３−３とを結んで良い事がわかり、ペアの決定が効率的に行える、というのが従来法の要点であった。なお図１７（ｃ）において１７２０−１等は後述するボロノイ分割の分割線を、１７０４−１等は後述するドローネ辺を示す。また図１７は特許文献１から引用したものであり、（ａ）、（ｂ）、（ｃ）が各々、第１図（ａ）、第１図（ｂ）、第２図（ｂ）に対応する。
【特許文献１】特開平０４−０７８９６６「画像処理方法」
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら上記の従来法では、抽出の対象は線分に限られていた。一般の２値画像では、その中に含まれる図形は「線画」のみではなく、２次元的な広がりを持った図形が存在しうる。この場合、図形のどの点を代表点（線分における端点に相当する点）としてドローネグラフを作成するべきかが、必ずしも明確ではなかった。従って従来法は、一般の２値画像には適用できないという制約があった。
【０００５】
本発明は上記の制約を取り除き、一般の２値画像に対しても計算幾何学の手法を利用できる事、その結果を応用して効率の良い画像認識方法が構成できる事、を開示するものである。
【課題を解決するための手段】
【０００６】
上記課題が生じる本質的な原因は、計算幾何学においては離散的な点の集合を処理の対象とする、という点にある。一方で画像認識技術においては、多数の画素が連続的（数学用語で言う連結状態）に塊を構成した領域（以下単に「領域」と記す）を、処理の対象とする場合がしばしば生じる。本発明ではまず、この様な領域に対して計算幾何学の基礎概念を拡張する方法を提案する。更に、この様に拡張された概念を、画像認識技術に応用する方法を提案する。
【０００７】
まず、計算幾何学の基礎概念である「ボロノイ分割」及び「ドローネグラフ」が、どの様に定義されたかを図２を用いて説明する。
・ボロノイ分割：平面上に離散的な点（以下「母点」と呼ぶ）の集合が与えられた時、平面上のどの位置もそこから最も近い母点に帰属するものとして平面を分割する事をボロノイ分割と言う。具体的な例として、図２（ａ）においては平面２００の上に４つの母点２０１−１〜２０１−４が与えられている。これに対して、たとえば図２（ｂ）における位置２０２は、そこから最も近い母点が２０１−１であるから、母点２０１−１に帰属する事になる。ここで母点２０１−１と母点２０１−２のどちらに帰属するかを分ける境界線は、両点を結ぶ線分２６０−１の垂直２等分線である線分２５０−１となる。同様に他の母点２０１−３、２０１−４との境界線は各々線分２５０−２、２５０−３となる。以上の結果、母点２０１−１に帰属する点の範囲（当該母点の支配域と言う）は、線分２５０−１〜２５０−３に囲まれた区域（図中に斜線で示した内側）となる。他の母点についても同様にして、図に示した実線２５０−１〜２５０−５により平面２００がボロノイ分割される。
・ドローネグラフ：ボロノイ分割を行った結果、ある２つの母点の支配域が隣接する（１点による接触は除く）場合、当該２点を辺（ドローネ辺と呼ばれる）で結ぶ。この結果得られるグラフをドローネグラフと呼ぶ。ドローネグラフは、その元となるボロノイ分割に対して、幾何学的に双対な図形となる。図２（ｂ）の例では、二重線で記したドローネ辺２６０−１等で構成されるグラフがドローネグラフである。
【０００８】
以上の概念は、２値画像の領域に対して以下の様に拡張できる。まず、０／１の２値からなる２値画像において値が「１」の画素を母点と考えれば、上記の基礎概念はそのまま適用できる。一方で領域とは、いくつかの画素が集まって構成されるのであるから、領域に対しては上記の基礎概念を以下の通り拡張して考えるのが妥当である。
・領域ボロノイ分割：ある領域の支配域は、当該領域に属する全ての母点（画素）の支配域の和とする。たとえば図１の例では、平面１００にいくつかの母点（画素）１０１−１、１０１−２、……、１０１−ｎが与えられている。これに対する原義のボロノイ分割は、図１（ａ）の破線１５０で示した通りとなる。しかしながらこの例では、図１（ｂ）に示す通り、母点（画素）が３つの連結な領域１１０−１〜１１０−３に分けられる。そこで各領域に対して、それぞれに属する母点（画素）の支配域の和を作ると、図１（ｂ）に実線１２０で示した部分が分割線として残る。この様に平面を分割する事を、領域ボロノイ分割と呼ぶ事にする。
・領域ドローネグラフ：上記の領域ボロノイ分割を行った結果、ある２つの領域の支配域が隣接する（１点による接触は除く）場合、当該２領域を辺（原義のドローネグラフと同様に、以後ドローネ辺と呼ぶ事にする）で結ぶ。この結果得られるグラフを領域ドローネグラフと呼ぶ事にする。図１（ｂ）では、二重線１３０−１〜１３０−３で示したグラフが領域ドローネグラフである。なおここで、領域が複数の画素からなる場合に、どの画素をドローネ辺の端点とするかという選択が生じるが、本発明では各々のドローネ辺は、２つの領域を最短距離で結ぶ様に引くものとした。
【０００９】
以上の通り、計算幾何学の基礎概念を領域に対して拡張できたので、複数の領域の位置関係をグラフにより表現する事が可能となる。この手段による本発明の第１の特徴は、２値画像から特定の構造物を検出する方法であって、当該２値画像は被写体を現す画素値１および背景を現す画素値０のいずれかのみからなり、画素値１の画素が複数の連結な領域を構成する場合において、まず画素値１の画素を母点とみなしてボロノイ分割を行なった後、ある領域に属する全ての画素の支配域の和を求める事により当該領域の支配域を定め、ある２つの領域に関して夫々の支配域が隣接する場合に当該２つの領域を辺で結んだグラフを作成し、上記グラフ構造に沿って上記特定の構造を検出する事を特徴とする画像認識方法を提供する事にある。
【００１０】
また、上記第１の特徴において、ある領域の内部にある点は、当該領域の支配域を決定する際には寄与しない。これを利用して、支配域を決定する手続きを簡素化する事ができる。この手段による本発明の第２の特徴は、第１の特徴を有する画像認識方法における領域の支配域を求める方法であって、全ての領域に対して当該領域の外形線を求めた後、全ての領域に対して外形線から外側へ逐次的に支配域を拡張して行き、ある２つの領域の支配域が接触した場合に当該２つの領域を辺で結んだグラフを作成する事を特徴とする画像認識方法を提供する事にある。
【００１１】
以上の特徴を利用する事により、従来法で開示した方法が２値画像に対しても適用可能となり、効率の良い画像認識アルゴリズムを構成できる。但し実際の応用では、与えられた２値画像がノイズを含む場合が多いので、このために以下の手段を画像認識アルゴリズムに加える事が実用性を増す。すなわち、本発明の第３の特徴は、第１の特徴を有する画像認識方法であって、上記で得られたグラフにおいて辺で結ばれた複数の領域を所定の規則に従って１つの領域に統合する手続きを含む事を特徴とする画像認識方法を提供する事にある。
【００１２】
以上の各特徴を利用する事により、本発明の第４の特徴は、第１の特徴を有する画像認識方法であって、第１の特徴または第３の特徴に記した方法により得られたグラフが、特定の構造を部分的に含むか否かを判定する事により、特定の構造物が当該２値画像に含まれるか否かを判定する事を特徴とする画像認識方法を提供する事にある。
【発明の効果】
【００１３】
以上の通り、本発明によれば、従来法よりも広い範囲の画像に対して特定の構造を検出する事が可能になり、画像認識技術や装置の更なる高度化・高機能化に資する事ができる。
【発明を実施するための最良の形態】
【００１４】
本発明は、コンピュータ上で動作するソフトウェアとして実施するのが妥当である。ここで使用するコンピュータは、いわゆる画像処理機能を実行できるものならば何でも良い。以下に実施例として、本発明の特徴を有するコンピュータプログラムの算法を、図面を用いて説明する。なお説明の便宜上、実施例では画像の中から人物の顔を検出する機能を取り上げて説明するが、これは本発明の適用範囲を制限するものではない。
【実施例】
【００１５】
図３は本発明を応用した顔検出アルゴリズムの全体を示すフローチャートである。本実施例においては、ステップ３００（以下「Ｓ３００」等と略記する）以下の処理によって画像から人物の顔を検出する。まず画像を入力（Ｓ３０１）した後、前処理として画像の２値化（Ｓ３０２）を行う。ここで得られた２値画像に対して［課題を解決するための手段］にて述べた通り、領域ボロノイ図作成（Ｓ３０３）、領域ドローネグラフ作成（Ｓ３０４）、領域の統合（Ｓ３０５）、標準顔グラフとのマッチング（Ｓ３０６）を順次行う。以上の結果により、画像の中に人物の顔が含まれているか否かを判定して（Ｓ３０７）、顔が検出されればその結果を表示（Ｓ３０８）し、そうでなければ顔が存在しない旨を表示（Ｓ３０９）して、処理を修了する（Ｓ３１０）。以上のフローに沿って、各ステップにおける動作を以下に詳細に説明する。
【００１６】
まずＳ３０１からＳ３０２により、画像を入力（Ｓ３０１）した後、前処理として画像の２値化（Ｓ３０２）を行う。本発明は２値画像を対象とした認識技術に係るものなので、Ｓ３０２における具体的な算法は特に規定しないが、最も簡単には各画素の画素値を予め定めた敷居値と比較して、敷居値以上ならば当該画素の値を‘０（白）’に、敷居値未満ならば‘１（黒）’にすれば良い。以上により、たとえば図４に示した入力画像４００に対して、図５に示した２値画像５００が得られる。なお図５において（ａ）は２値画像そのものを示したものであり、（ｂ）は引き続くステップで引用するために、２値画像に含まれる領域に適宜符号を付したものである。すなわち２値画像５００は、５０１−１、５０１−２、……、５０１−ｎで示される各領域から構成される。これらのうち５０１−１は頭髪を中心とした大きな領域であり、５０１−２、５０１−３は右および左の鼻腔に各々対応する領域である。また５０１−４、５０１−５は共に右目に対応する領域であるが、２値化処理におけるノイズの影響で、目尻から瞳にかけての部分５０１−４と目頭の部分５０１−５とに分かれている。左目についても同様に、目尻から瞳にかけての部分５０１−６と目頭の部分５０１−７とが領域として存在する。
【００１７】
次に領域ボロノイ図作成（Ｓ３０３）を行なう。このステップの詳細を、図６から図８を用いて説明する。
【００１８】
図６は領域ボロノイ図を作成するアルゴリズムを示したフローチャートである。領域ボロノイ図を作成するには、画像が有限個の画素からなる事に着眼して、各画素がどの領域の支配域に属するかを調べれば良い。すなわち図６に示す通り、画像に含まれる全ての画素に対して以下のＳ６０２〜Ｓ６０４を繰り返す（Ｓ６０１）。まず当該画素の画素値が０かどうかを調べ、０でない（すなわち領域のどれかに含まれている）ならば以下のＳ６０３〜Ｓ６０４はスキップする（Ｓ６０２）。０である（すなわち背景部分にある）場合は当該画素から最も近い領域（これを領域Ｒとする）を探索して（Ｓ６０３）、当該画素を領域Ｒのボロノイ領域とする（Ｓ６０４）。以上の繰返しを完了する事により、領域ボロノイ図作成が完了する（Ｓ６０５）。
【００１９】
また領域ボロノイ図は、次に述べる「領域逐次拡張法」にて作成しても良い。「領域逐次拡張法」とは、各領域からの距離が１の画素、距離が２の画素、……、を逐次的に求める方法であり、具体的には図７に示す通りの動作で実行される。図７は２値画像の一部分を取り出したものであり、図中の○、▲１▼、▲２▼、●は全て画素を表わす。これらのうち黒丸「●」は２値画像の中で値が‘１（黒）’の画素であり、すなわちある領域に属する画素を表わす。他の３者は全て、値が‘０（白）’の画素を表わす。ここで当該領域から距離が１の画素は、当該領域の外周を辿る事により、図中の「▲１▼」で示した画素である事がわかる。また距離が２の画素は、「▲１▼」で示した画素の外周を辿る事により、図中の「▲２▼」で示した画素である事がわかる。以下同様に、距離が３、４、５、……、の画素を逐次的に求める事ができる。以上を全ての領域に対して適用して、最も小さい距離が得られた領域が、当該画素を支配域とするものとする。なおこの「領域逐次拡張法」においては、距離の測定方法として通常のユークリッド距離ではなくいわゆる「マンハッタン距離」を用いる事になるが、これは引き続くＳ３０４以下の実行に支障を生じるものではない。
【００２０】
以上の方法を図５における２値画像５００に適用した例を図８に示す。図８において８００は領域ボロノイ図を作成した結果となる写真を示しており、ある領域に属する支配域を同一の濃淡色で表わしている。たとえば図５における領域５０１−１に対しては８０１−１が、同様に５０１−２、５０１−３、……、５０１−ｎ、に対しては８０１−２、８０１−３、……、８０１−ｎ、が、それぞれ支配域となる。なお以上において、ある画素が複数の領域から等距離にある場合は、便宜的に最も若い番号の領域に支配されるものとした。また図８においては、作画装置の性能的な制約上、異なった支配域に見かけ上同一の濃淡色が割当てられている点を御了承頂きたい。これらはいずれも、引き続くＳ３０４以下の実行に支障を生じるものではない。
【００２１】
次に領域ドローネグラフ作成（Ｓ３０４）を行う。このステップの詳細を、図９から図１０を用いて説明する。
【００２２】
図９は領域ドローネグラフを作成するアルゴリズムを示したフローチャートである。領域ドローネグラフの定義は［課題を解決するための手段］に記した通り、２つの領域の支配域が隣接していれば、その間にドローネ辺を引く、というものであった。図９はこの定義に沿ってドローネ辺を引くものである。すなわち図９に示す通り、２つの領域の組合せを全て列挙して、それらに対して以下のＳ９０２〜Ｓ９０４を繰り返す（Ｓ９０１）。まず両領域のボロノイ領域が隣接しているか否かを領域ボロノイ図８００を参照して判定し、否であれば以下のＳ９０３〜Ｓ９０４はスキップする（Ｓ９０２）。隣接している場合は両領域が最も接近している場所を２値画像５００から求め（Ｓ９０３）、その場所にドローネ辺を引く（Ｓ９０４）。以上の繰返しを完了する事により、領域ドローネグラフ作成が完了する（Ｓ９０５）。
【００２３】
なお図９は領域ドローネグラフの定義に忠実に沿った方法であるが、前述の領域ボロノイ図作成（Ｓ３０３）において「領域逐次拡張法」を用いる場合は、拡張の途中経過から複数の領域の支配域が隣接する事がわかるので、その情報を記憶しておけばＳ９０２あるいはＳ９０３を簡略化する事ができる。
【００２４】
以上のステップにより作成された領域ドローネグラフの例を図１０に示す。図１０は領域ボロノイ図８００から領域ドローネグラフ１０００を作成したものであり、同グラフはドローネ辺１００１−１、１００１−２、……、１００１−ｎから構成される。これらの内、１００１−１は２値画像５００における領域５０１−５（右目頭）と５０１−７（左目頭）が隣接している事を示すものである。同様に１００１−２（５０１−５と５０１−２）、１００１−３（５０１−５と５０１−３）、１００１−４（５０１−２と５０１−３）、などのドローネ辺が引かれる。
【００２５】
次に領域の統合（Ｓ３０５）を行う。本ステップは課題を解決するための手段に記した通り、２値画像５００にノイズが混入している場合に必要となる。従って、何らかの条件によりノイズが無い事が保証されている場合には、本ステップを省略して良い。本実施例においては２値画像５００に示す通り、画像にノイズが混入した結果、２値化の結果が不完全になっている。たとえば、本来は１つの構造物である右目が、目尻から瞳にかけての部分５０１−４と目頭の部分５０１−５とに分かれている。左目についても同様である。更に、鼻は左右の鼻腔５０１−２、５０１−３に分かれている。これらを１つのものと見なす事が、本ステップの目的である。この詳細を、図１１から図１２を用いて説明する。
【００２６】
図１１は領域の統合を行うアルゴリズムを示したフローチャートである。本実施例においては、以下の条件で領域の統合を行うものとする。
条件０：２つの領域がドローネ辺で結ばれている。
条件１：条件０の下で、２つの領域が極めて近距離（規定のパラメータ以内）にある場合は、両者はノイズにより分離されたものと見なして、両者を統合する。
条件２：条件０の下で、概ね同一サイズの２領域が概ね水平に並んでおり、それらの至近（規定のパラメータ以内）に他の領域が無い場合は、両者は鼻腔であると見なして、両者を統合する。
以上の条件の下に、アルゴリズムは図１１に示す通りとなる。すなわち、全てのドローネ辺に対して、以下のＳ１１０２〜Ｓ１１０５を繰り返す（Ｓ１１０１）。まずＳ１１０２において上記の条件１が成立するか否かを判定し、成立すればＳ１１０４以降を実行する。否の場合は、Ｓ１１０３において上記の条件２が成立するか否かを判定し、成立すればＳ１１０４以降を実行する。否の場合は統合が不要な場合であるので、Ｓ１１０４〜Ｓ１１０５はスキップする。Ｓ１１０４〜Ｓ１１０５は、領域が統合された結果を反映してドローネグラフを更新するステップである。すなわち、まずＳ１１０４において、両者を結ぶドローネ辺が不要となるので、当該ドローネ辺を削除する。次にＳ１１０５において、他の領域からのドローネ辺で重複が生じるものを、１つのドローネ辺に統合する。以上の繰返しを完了する事により、領域の統合が完了する（Ｓ１１０６）。
【００２７】
図１２は、領域ドローネグラフ１０００に対して領域の統合を行った結果、得られる統合済領域ドローネグラフ１２００を示す。統合済領域ドローネグラフ１２００においては、１００１−１に示す様に１０００におけるドローネ辺がそのまま残る場合もあるが、１２０１−１、……、１２０１−ｎに示す様な新たなドローネ辺が生じる場合もある。また１０００におけるドローネ辺１００１−４は消失している。これらは、ドローネ辺１００１−４に対してＳ１１０３の条件が成立した結果、２値画像５００における領域５０１−２と５０１−３とが統合され、仮想的な１つの領域１２１０−１となった結果、ドローネグラフが更新されたためである。すなわち、ドローネ辺１００１−４はＳ１１０４により削除され、またドローネ辺１００１−２と１００１−３とがＳ１１０５により統合されて１２０１−１となっている。ここで１２０１−１においてドローネ辺の下端は、領域５０１−２と５０１−３との中間点に取るものとした。なお図１２においては、符号は省略したが、鼻と同様に右目、左目、口においても統合が行なわれた結果、各々が１つの領域になっており、新たなドローネ辺１２０１−２、１２０１−３が生じている。
【００２８】
ここで図１１のアルゴリズムにおいては、条件１および条件２における「規定のパラメータ」は、実験的に定めるものとする。また図１１の処理全体を適当な制約条件の下に繰り返して適用して、３つ以上の領域を１つに統合する様にしても良い。更に、領域の統合の可否の判定には多様なルールが考えられるので、それらでＳ１１０２〜Ｓ１１０３を置き換えても良い。
【００２９】
以上のステップにより統合済領域ドローネグラフ１２００が得られたので、これに対して従来法と類似の手法を適用する事により、画像認識機能（本実施例では顔の認識機能）を実現する事ができる。すなわちＳ３０６として、標準顔グラフとのマッチングを行う。この詳細を図１３から図１５を用いて説明する。
【００３０】
まず図１３は、人間の顔の普遍的な構造をグラフの形で表現する「標準顔グラフ」１３００を示したものである。すなわち、人間の顔には４つの部位（右目、左目、鼻、口）が存在し、これら全体が輪郭線で囲まれている。ここで各部位の位置関係を領域ドローネグラフで表すと、１３００に記した通りとなる。すなわち、右目と左目は隣接関係にあり、ドローネ辺１３０１で結ばれる。同様に右目と鼻、左目と鼻、鼻と口も隣接関係にあり、各々ドローネ辺１３０２、１３０３、１３０４で結ばれる。一方、右目と口および左目と口は中間に鼻があるため隣接関係とはならず、従って図中の１３１１および１３１２に相当するドローネ辺は存在しない。図ではドローネ辺が存在しない事を破線で示した。以上の部位は輪郭線１３２０で囲まれる。ここで輪郭線はいくつかのドローネ辺が概ね滑らかに連続したものである。
【００３１】
上記１３００に基づいて、標準顔グラフとのマッチング（Ｓ３０６）は図１４のフローチャートで示されるアルゴリズムにて実行できる。すなわち、まず統合済領域ドローネグラフ１２００に含まれる輪郭線候補を列挙する（Ｓ１４０１）。このステップは従来法で開示したのと同様に、隣接する領域の適当な系列を作成して、それらを結ぶドローネ辺が概ね滑らかに方向を変えてゆく事を確認すれば良い。この結果列挙された輪郭線候補に対して、以下のＳ１４０３〜Ｓ１４０５を繰り返す（Ｓ１４０２）。まずＳ１４０３において、輪郭線の内部に含まれる領域（統合済のもの）の数が、顔の部位の数である４に等しいか否かを確認し、否であれば引き続くＳ１４０４〜Ｓ１４０５はスキップする。等しい場合は更にＳ１４０４において、輪郭内の領域から作成される領域ドローネグラフが、標準顔グラフ１３００と相同であるか否かを確認する。すなわちより詳細には、４つの領域の内で他の３つ全てと隣接するものがあれば、そこを鼻と見なす。次に、鼻のみと隣接する領域を口と見なす。残りの２領域は右目と左目になるべきなので、この両者が隣接している事を確認する。以上の条件に全て適合すれば、輪郭内の領域は標準顔グラフ１３００と相同な領域ドローネグラフを構成していると結論できる。これらの結果、相同で無いと判定された場合は、引き続くＳ１４０５はスキップする。相同な場合はＳ１４０５に進み、輪郭内の各領域を対応する顔の部位として登録する。以上の繰返しを完了する事により、標準顔グラフとのマッチング（Ｓ３０６）が完了する（Ｓ１４０６）。
【００３２】
図１５は図１４に従ってＳ３０６を統合済領域ドローネグラフ１２００に適用した例を示す。まずＳ１４０１により輪郭線の候補が多数列挙されるが、それらの一つとして図の１５０１−１、１５０１−２、……、１５０１−ｎで示した候補が含まれる。この候補に対してＳ１４０３〜Ｓ１４０５を適用すると、まず輪郭線内部の領域の数は、Ｓ３０５による統合の結果４つとなっているので、Ｓ１４０３の条件は成立する。更にＳ１４０４においては上述の条件に適合する事が確認される。すなわちドローネ辺１００１−１が１３００における１３０１に、１２０１−１、１２０１−２、１２０１−３が各々１３０２、１３０３、１３０４に対応する。更に１３１１、１３１２に相当するドローネ辺は１５００に存在しない。以上から標準顔グラフ１３００との相同性が確認されたので、その結果をＳ１４０５にて登録する。
【００３３】
ここまでの各段落で説明の通り、図３におけるＳ３０３〜Ｓ３０６により顔の有無が判定できたので、その結果を冒頭に述べた通りＳ３０７〜Ｓ３１０にて扱う。ここでＳ３０８における表示は、たとえば図１６の様に、入力画像４００に部位の名称を重畳させて示せば良い。
【００３４】
以上、本発明の一実施例を説明したが、この実施例を変形した様々な方法も考えられる。たとえば、Ｓ３０７において顔が発見されなかった場合は、Ｓ３０２に戻って画像２値化をやり直してＳ３０３以下をリトライする、としても良い。またＳ３０６において標準顔グラフとのマッチングが失敗した場合は、Ｓ３０５に戻って領域の統合をやり直しても良く、この場合にはＳ３０５で述べた「規定のパラメータ」を適宜変更して処理する方法が考えられる。更にＳ３０６においては、単に領域ドローネグラフの相同性を判定するのに留まらず、各領域が人間の顔の部位として妥当な大きさや形状を持つかどうか、より具体的には左右の目は概ね同一サイズ化かどうか、目が口よりも大きい事はないか、等を判定する機能を持たせても良い。また標準顔グラフ１３００においては、右目（左目も同様）と口とは隣接関係に無いとしたが、両者の隣接の度合いが微小ならば隣接しても良い、というルールにしても良い。ここで「隣接の度合」は、図８において両領域の支配域がどの程度境界線を共有するか、という情報から決定できる。
【００３５】
以上、人物顔の検出を例として実施例を示したが、冒頭に述べた通り本発明は本実施例に限定される事なく、規定の構造を持つ物体が画像の中に含まれるかを判定する方法として、広範に応用できる。たとえば円形又は方形の構造物の中に１２個の文字領域が概ね円形状に配列されていれば、それが時計である事が本発明により容易に判定できる。より一般には、ある種の構造物が何らかの生成規範に従って構成されている場合、その規範をグラフ構造によって表現できるならば、一つ一つの具体的な物体（個体）には違いがあっても、本質的に同種の物である事が本発明により認識できる。
【産業上の利用可能性】
【００３６】
本発明は画像認識技術を応用した各種の映像処理装置で利用可能であり、より具体的には映像監視装置、ビデオ編集装置、ディジタルカメラなどへの応用が期待できる。
【図面の簡単な説明】
【００３７】
【図１】 連結領域を含む２値画像に対して図２の概念を拡張する方法を説明する図。（ａ）原義に従い作成されたボロノイ図の一例。（ｂ）（ａ）から「領域ボロノイ図」「領域ドローネグラフ」を作成する方法。
【図２】 計算幾何学の基礎概念「ボロノイ図」「ドローネグラフ」を説明する図。（ａ）平面上の点集合の１例。（ｂ）（ａ）から作成される「ボロノイ図」「ドローネグラフ」の定義を説明する図。
【図３】 本発明の実施例である顔認識算法の全体構成を示すフローチャート。
【図４】 実施例における入力画像の一例を示す写真。
【図５】 入力画像を２値化した結果の例を示す図。（ａ）２値化した結果そのものを示す図。（ｂ）（ａ）に対して説明用の符号を付した図。
【図６】 ステップ３０３「領域ボロノイ図作成」の算法を示すフローチャート。
【図７】 領域ボロノイ図を作成する別の方法「領域逐次拡張法」を説明する図。
【図８】 ステップ３０３の結果得られる領域ボロノイ図の一例を示す写真。
【図９】 ステップ３０４「領域ドローネグラフ作成」の算法を示すフローチャート。
【図１０】 ステップ３０４の結果得られる領域ドローネグラフ。
【図１１】 ステップ３０５「領域の統合」の算法を示すフローチャート。
【図１２】 ステップ３０５の結果得られる統合済領域ドローネグラフの一例。
【図１３】 ステップ３０６で用いる標準顔グラフを説明する図。
【図１４】 ステップ３０６「標準顔グラフとのマッチング」の算法を示すフローチャート。
【図１５】 ステップ３０６によるマッチングの結果の一例を示す図。
【図１６】 本実施例により顔の認識に成功した例を示す写真。
【図１７】 従来法による線分の抽出技術を説明する図。
【符号の説明】
【００３８】
１０１…母点（値が「１」の画素）
１１０…連結領域
１２０…領域ボロノイ分割における分割線
１３０…領域ドローネグラフにおけるドローネ辺
１５０、２５０…原義のボロノイ分割における分割線
２６０…原義のドローネグラフにおけるドローネ辺
【技術分野】
【０００１】
本発明はディジタル画像認識技術に係り、特に予め規定された構造物が２値画像の中に含まれるか否かを判定する方法に関する。
【背景技術】
【０００２】
発明者は既に特許文献１において、２値画像の中から特定の形状の線分（曲線を含む）を抽出する方法（以下「従来法」と記す）を開示している。従来法は、ノイズの影響で線分に途切れが生じた場合に、ある線分の端点を近隣の線分の端点と結ぶ事により、途切れを補うものである。ここで、どの端点同士をペアにして結べば良いかを効率的に決定するために、計算幾何学の手法を応用している。
【０００３】
すなわち図１７に示す通り、特許文献１においては医療用Ｘ線写真から胃の外形線を抽出する事を目的として、まず入力画像のエッジ部分を強調した画像（図１７（ａ））を用意し、これに対して線分追跡処理を行う。しかしながら画像には胃１７０１以外に脊椎１７１１が映っており、またノイズ領域１７１２等が存在する。このため線分追跡処理のみでは外形線１７３１を完全には抽出できず、図１７（ｂ）に示す通り外形線の局所的な断片１７０２−１等が抽出されたり、余分な線分１７０９等が抽出されたりする。そこでこれらの線分の端点１７０３−１等に対して、計算幾何学の手法によりドローネグラフ（図１７（ｃ））を作成する事により、たとえば端点１７０３−２と１７０３−３とを結んで良い事がわかり、ペアの決定が効率的に行える、というのが従来法の要点であった。なお図１７（ｃ）において１７２０−１等は後述するボロノイ分割の分割線を、１７０４−１等は後述するドローネ辺を示す。また図１７は特許文献１から引用したものであり、（ａ）、（ｂ）、（ｃ）が各々、第１図（ａ）、第１図（ｂ）、第２図（ｂ）に対応する。
【特許文献１】特開平０４−０７８９６６「画像処理方法」
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら上記の従来法では、抽出の対象は線分に限られていた。一般の２値画像では、その中に含まれる図形は「線画」のみではなく、２次元的な広がりを持った図形が存在しうる。この場合、図形のどの点を代表点（線分における端点に相当する点）としてドローネグラフを作成するべきかが、必ずしも明確ではなかった。従って従来法は、一般の２値画像には適用できないという制約があった。
【０００５】
本発明は上記の制約を取り除き、一般の２値画像に対しても計算幾何学の手法を利用できる事、その結果を応用して効率の良い画像認識方法が構成できる事、を開示するものである。
【課題を解決するための手段】
【０００６】
上記課題が生じる本質的な原因は、計算幾何学においては離散的な点の集合を処理の対象とする、という点にある。一方で画像認識技術においては、多数の画素が連続的（数学用語で言う連結状態）に塊を構成した領域（以下単に「領域」と記す）を、処理の対象とする場合がしばしば生じる。本発明ではまず、この様な領域に対して計算幾何学の基礎概念を拡張する方法を提案する。更に、この様に拡張された概念を、画像認識技術に応用する方法を提案する。
【０００７】
まず、計算幾何学の基礎概念である「ボロノイ分割」及び「ドローネグラフ」が、どの様に定義されたかを図２を用いて説明する。
・ボロノイ分割：平面上に離散的な点（以下「母点」と呼ぶ）の集合が与えられた時、平面上のどの位置もそこから最も近い母点に帰属するものとして平面を分割する事をボロノイ分割と言う。具体的な例として、図２（ａ）においては平面２００の上に４つの母点２０１−１〜２０１−４が与えられている。これに対して、たとえば図２（ｂ）における位置２０２は、そこから最も近い母点が２０１−１であるから、母点２０１−１に帰属する事になる。ここで母点２０１−１と母点２０１−２のどちらに帰属するかを分ける境界線は、両点を結ぶ線分２６０−１の垂直２等分線である線分２５０−１となる。同様に他の母点２０１−３、２０１−４との境界線は各々線分２５０−２、２５０−３となる。以上の結果、母点２０１−１に帰属する点の範囲（当該母点の支配域と言う）は、線分２５０−１〜２５０−３に囲まれた区域（図中に斜線で示した内側）となる。他の母点についても同様にして、図に示した実線２５０−１〜２５０−５により平面２００がボロノイ分割される。
・ドローネグラフ：ボロノイ分割を行った結果、ある２つの母点の支配域が隣接する（１点による接触は除く）場合、当該２点を辺（ドローネ辺と呼ばれる）で結ぶ。この結果得られるグラフをドローネグラフと呼ぶ。ドローネグラフは、その元となるボロノイ分割に対して、幾何学的に双対な図形となる。図２（ｂ）の例では、二重線で記したドローネ辺２６０−１等で構成されるグラフがドローネグラフである。
【０００８】
以上の概念は、２値画像の領域に対して以下の様に拡張できる。まず、０／１の２値からなる２値画像において値が「１」の画素を母点と考えれば、上記の基礎概念はそのまま適用できる。一方で領域とは、いくつかの画素が集まって構成されるのであるから、領域に対しては上記の基礎概念を以下の通り拡張して考えるのが妥当である。
・領域ボロノイ分割：ある領域の支配域は、当該領域に属する全ての母点（画素）の支配域の和とする。たとえば図１の例では、平面１００にいくつかの母点（画素）１０１−１、１０１−２、……、１０１−ｎが与えられている。これに対する原義のボロノイ分割は、図１（ａ）の破線１５０で示した通りとなる。しかしながらこの例では、図１（ｂ）に示す通り、母点（画素）が３つの連結な領域１１０−１〜１１０−３に分けられる。そこで各領域に対して、それぞれに属する母点（画素）の支配域の和を作ると、図１（ｂ）に実線１２０で示した部分が分割線として残る。この様に平面を分割する事を、領域ボロノイ分割と呼ぶ事にする。
・領域ドローネグラフ：上記の領域ボロノイ分割を行った結果、ある２つの領域の支配域が隣接する（１点による接触は除く）場合、当該２領域を辺（原義のドローネグラフと同様に、以後ドローネ辺と呼ぶ事にする）で結ぶ。この結果得られるグラフを領域ドローネグラフと呼ぶ事にする。図１（ｂ）では、二重線１３０−１〜１３０−３で示したグラフが領域ドローネグラフである。なおここで、領域が複数の画素からなる場合に、どの画素をドローネ辺の端点とするかという選択が生じるが、本発明では各々のドローネ辺は、２つの領域を最短距離で結ぶ様に引くものとした。
【０００９】
以上の通り、計算幾何学の基礎概念を領域に対して拡張できたので、複数の領域の位置関係をグラフにより表現する事が可能となる。この手段による本発明の第１の特徴は、２値画像から特定の構造物を検出する方法であって、当該２値画像は被写体を現す画素値１および背景を現す画素値０のいずれかのみからなり、画素値１の画素が複数の連結な領域を構成する場合において、まず画素値１の画素を母点とみなしてボロノイ分割を行なった後、ある領域に属する全ての画素の支配域の和を求める事により当該領域の支配域を定め、ある２つの領域に関して夫々の支配域が隣接する場合に当該２つの領域を辺で結んだグラフを作成し、上記グラフ構造に沿って上記特定の構造を検出する事を特徴とする画像認識方法を提供する事にある。
【００１０】
また、上記第１の特徴において、ある領域の内部にある点は、当該領域の支配域を決定する際には寄与しない。これを利用して、支配域を決定する手続きを簡素化する事ができる。この手段による本発明の第２の特徴は、第１の特徴を有する画像認識方法における領域の支配域を求める方法であって、全ての領域に対して当該領域の外形線を求めた後、全ての領域に対して外形線から外側へ逐次的に支配域を拡張して行き、ある２つの領域の支配域が接触した場合に当該２つの領域を辺で結んだグラフを作成する事を特徴とする画像認識方法を提供する事にある。
【００１１】
以上の特徴を利用する事により、従来法で開示した方法が２値画像に対しても適用可能となり、効率の良い画像認識アルゴリズムを構成できる。但し実際の応用では、与えられた２値画像がノイズを含む場合が多いので、このために以下の手段を画像認識アルゴリズムに加える事が実用性を増す。すなわち、本発明の第３の特徴は、第１の特徴を有する画像認識方法であって、上記で得られたグラフにおいて辺で結ばれた複数の領域を所定の規則に従って１つの領域に統合する手続きを含む事を特徴とする画像認識方法を提供する事にある。
【００１２】
以上の各特徴を利用する事により、本発明の第４の特徴は、第１の特徴を有する画像認識方法であって、第１の特徴または第３の特徴に記した方法により得られたグラフが、特定の構造を部分的に含むか否かを判定する事により、特定の構造物が当該２値画像に含まれるか否かを判定する事を特徴とする画像認識方法を提供する事にある。
【発明の効果】
【００１３】
以上の通り、本発明によれば、従来法よりも広い範囲の画像に対して特定の構造を検出する事が可能になり、画像認識技術や装置の更なる高度化・高機能化に資する事ができる。
【発明を実施するための最良の形態】
【００１４】
本発明は、コンピュータ上で動作するソフトウェアとして実施するのが妥当である。ここで使用するコンピュータは、いわゆる画像処理機能を実行できるものならば何でも良い。以下に実施例として、本発明の特徴を有するコンピュータプログラムの算法を、図面を用いて説明する。なお説明の便宜上、実施例では画像の中から人物の顔を検出する機能を取り上げて説明するが、これは本発明の適用範囲を制限するものではない。
【実施例】
【００１５】
図３は本発明を応用した顔検出アルゴリズムの全体を示すフローチャートである。本実施例においては、ステップ３００（以下「Ｓ３００」等と略記する）以下の処理によって画像から人物の顔を検出する。まず画像を入力（Ｓ３０１）した後、前処理として画像の２値化（Ｓ３０２）を行う。ここで得られた２値画像に対して［課題を解決するための手段］にて述べた通り、領域ボロノイ図作成（Ｓ３０３）、領域ドローネグラフ作成（Ｓ３０４）、領域の統合（Ｓ３０５）、標準顔グラフとのマッチング（Ｓ３０６）を順次行う。以上の結果により、画像の中に人物の顔が含まれているか否かを判定して（Ｓ３０７）、顔が検出されればその結果を表示（Ｓ３０８）し、そうでなければ顔が存在しない旨を表示（Ｓ３０９）して、処理を修了する（Ｓ３１０）。以上のフローに沿って、各ステップにおける動作を以下に詳細に説明する。
【００１６】
まずＳ３０１からＳ３０２により、画像を入力（Ｓ３０１）した後、前処理として画像の２値化（Ｓ３０２）を行う。本発明は２値画像を対象とした認識技術に係るものなので、Ｓ３０２における具体的な算法は特に規定しないが、最も簡単には各画素の画素値を予め定めた敷居値と比較して、敷居値以上ならば当該画素の値を‘０（白）’に、敷居値未満ならば‘１（黒）’にすれば良い。以上により、たとえば図４に示した入力画像４００に対して、図５に示した２値画像５００が得られる。なお図５において（ａ）は２値画像そのものを示したものであり、（ｂ）は引き続くステップで引用するために、２値画像に含まれる領域に適宜符号を付したものである。すなわち２値画像５００は、５０１−１、５０１−２、……、５０１−ｎで示される各領域から構成される。これらのうち５０１−１は頭髪を中心とした大きな領域であり、５０１−２、５０１−３は右および左の鼻腔に各々対応する領域である。また５０１−４、５０１−５は共に右目に対応する領域であるが、２値化処理におけるノイズの影響で、目尻から瞳にかけての部分５０１−４と目頭の部分５０１−５とに分かれている。左目についても同様に、目尻から瞳にかけての部分５０１−６と目頭の部分５０１−７とが領域として存在する。
【００１７】
次に領域ボロノイ図作成（Ｓ３０３）を行なう。このステップの詳細を、図６から図８を用いて説明する。
【００１８】
図６は領域ボロノイ図を作成するアルゴリズムを示したフローチャートである。領域ボロノイ図を作成するには、画像が有限個の画素からなる事に着眼して、各画素がどの領域の支配域に属するかを調べれば良い。すなわち図６に示す通り、画像に含まれる全ての画素に対して以下のＳ６０２〜Ｓ６０４を繰り返す（Ｓ６０１）。まず当該画素の画素値が０かどうかを調べ、０でない（すなわち領域のどれかに含まれている）ならば以下のＳ６０３〜Ｓ６０４はスキップする（Ｓ６０２）。０である（すなわち背景部分にある）場合は当該画素から最も近い領域（これを領域Ｒとする）を探索して（Ｓ６０３）、当該画素を領域Ｒのボロノイ領域とする（Ｓ６０４）。以上の繰返しを完了する事により、領域ボロノイ図作成が完了する（Ｓ６０５）。
【００１９】
また領域ボロノイ図は、次に述べる「領域逐次拡張法」にて作成しても良い。「領域逐次拡張法」とは、各領域からの距離が１の画素、距離が２の画素、……、を逐次的に求める方法であり、具体的には図７に示す通りの動作で実行される。図７は２値画像の一部分を取り出したものであり、図中の○、▲１▼、▲２▼、●は全て画素を表わす。これらのうち黒丸「●」は２値画像の中で値が‘１（黒）’の画素であり、すなわちある領域に属する画素を表わす。他の３者は全て、値が‘０（白）’の画素を表わす。ここで当該領域から距離が１の画素は、当該領域の外周を辿る事により、図中の「▲１▼」で示した画素である事がわかる。また距離が２の画素は、「▲１▼」で示した画素の外周を辿る事により、図中の「▲２▼」で示した画素である事がわかる。以下同様に、距離が３、４、５、……、の画素を逐次的に求める事ができる。以上を全ての領域に対して適用して、最も小さい距離が得られた領域が、当該画素を支配域とするものとする。なおこの「領域逐次拡張法」においては、距離の測定方法として通常のユークリッド距離ではなくいわゆる「マンハッタン距離」を用いる事になるが、これは引き続くＳ３０４以下の実行に支障を生じるものではない。
【００２０】
以上の方法を図５における２値画像５００に適用した例を図８に示す。図８において８００は領域ボロノイ図を作成した結果となる写真を示しており、ある領域に属する支配域を同一の濃淡色で表わしている。たとえば図５における領域５０１−１に対しては８０１−１が、同様に５０１−２、５０１−３、……、５０１−ｎ、に対しては８０１−２、８０１−３、……、８０１−ｎ、が、それぞれ支配域となる。なお以上において、ある画素が複数の領域から等距離にある場合は、便宜的に最も若い番号の領域に支配されるものとした。また図８においては、作画装置の性能的な制約上、異なった支配域に見かけ上同一の濃淡色が割当てられている点を御了承頂きたい。これらはいずれも、引き続くＳ３０４以下の実行に支障を生じるものではない。
【００２１】
次に領域ドローネグラフ作成（Ｓ３０４）を行う。このステップの詳細を、図９から図１０を用いて説明する。
【００２２】
図９は領域ドローネグラフを作成するアルゴリズムを示したフローチャートである。領域ドローネグラフの定義は［課題を解決するための手段］に記した通り、２つの領域の支配域が隣接していれば、その間にドローネ辺を引く、というものであった。図９はこの定義に沿ってドローネ辺を引くものである。すなわち図９に示す通り、２つの領域の組合せを全て列挙して、それらに対して以下のＳ９０２〜Ｓ９０４を繰り返す（Ｓ９０１）。まず両領域のボロノイ領域が隣接しているか否かを領域ボロノイ図８００を参照して判定し、否であれば以下のＳ９０３〜Ｓ９０４はスキップする（Ｓ９０２）。隣接している場合は両領域が最も接近している場所を２値画像５００から求め（Ｓ９０３）、その場所にドローネ辺を引く（Ｓ９０４）。以上の繰返しを完了する事により、領域ドローネグラフ作成が完了する（Ｓ９０５）。
【００２３】
なお図９は領域ドローネグラフの定義に忠実に沿った方法であるが、前述の領域ボロノイ図作成（Ｓ３０３）において「領域逐次拡張法」を用いる場合は、拡張の途中経過から複数の領域の支配域が隣接する事がわかるので、その情報を記憶しておけばＳ９０２あるいはＳ９０３を簡略化する事ができる。
【００２４】
以上のステップにより作成された領域ドローネグラフの例を図１０に示す。図１０は領域ボロノイ図８００から領域ドローネグラフ１０００を作成したものであり、同グラフはドローネ辺１００１−１、１００１−２、……、１００１−ｎから構成される。これらの内、１００１−１は２値画像５００における領域５０１−５（右目頭）と５０１−７（左目頭）が隣接している事を示すものである。同様に１００１−２（５０１−５と５０１−２）、１００１−３（５０１−５と５０１−３）、１００１−４（５０１−２と５０１−３）、などのドローネ辺が引かれる。
【００２５】
次に領域の統合（Ｓ３０５）を行う。本ステップは課題を解決するための手段に記した通り、２値画像５００にノイズが混入している場合に必要となる。従って、何らかの条件によりノイズが無い事が保証されている場合には、本ステップを省略して良い。本実施例においては２値画像５００に示す通り、画像にノイズが混入した結果、２値化の結果が不完全になっている。たとえば、本来は１つの構造物である右目が、目尻から瞳にかけての部分５０１−４と目頭の部分５０１−５とに分かれている。左目についても同様である。更に、鼻は左右の鼻腔５０１−２、５０１−３に分かれている。これらを１つのものと見なす事が、本ステップの目的である。この詳細を、図１１から図１２を用いて説明する。
【００２６】
図１１は領域の統合を行うアルゴリズムを示したフローチャートである。本実施例においては、以下の条件で領域の統合を行うものとする。
条件０：２つの領域がドローネ辺で結ばれている。
条件１：条件０の下で、２つの領域が極めて近距離（規定のパラメータ以内）にある場合は、両者はノイズにより分離されたものと見なして、両者を統合する。
条件２：条件０の下で、概ね同一サイズの２領域が概ね水平に並んでおり、それらの至近（規定のパラメータ以内）に他の領域が無い場合は、両者は鼻腔であると見なして、両者を統合する。
以上の条件の下に、アルゴリズムは図１１に示す通りとなる。すなわち、全てのドローネ辺に対して、以下のＳ１１０２〜Ｓ１１０５を繰り返す（Ｓ１１０１）。まずＳ１１０２において上記の条件１が成立するか否かを判定し、成立すればＳ１１０４以降を実行する。否の場合は、Ｓ１１０３において上記の条件２が成立するか否かを判定し、成立すればＳ１１０４以降を実行する。否の場合は統合が不要な場合であるので、Ｓ１１０４〜Ｓ１１０５はスキップする。Ｓ１１０４〜Ｓ１１０５は、領域が統合された結果を反映してドローネグラフを更新するステップである。すなわち、まずＳ１１０４において、両者を結ぶドローネ辺が不要となるので、当該ドローネ辺を削除する。次にＳ１１０５において、他の領域からのドローネ辺で重複が生じるものを、１つのドローネ辺に統合する。以上の繰返しを完了する事により、領域の統合が完了する（Ｓ１１０６）。
【００２７】
図１２は、領域ドローネグラフ１０００に対して領域の統合を行った結果、得られる統合済領域ドローネグラフ１２００を示す。統合済領域ドローネグラフ１２００においては、１００１−１に示す様に１０００におけるドローネ辺がそのまま残る場合もあるが、１２０１−１、……、１２０１−ｎに示す様な新たなドローネ辺が生じる場合もある。また１０００におけるドローネ辺１００１−４は消失している。これらは、ドローネ辺１００１−４に対してＳ１１０３の条件が成立した結果、２値画像５００における領域５０１−２と５０１−３とが統合され、仮想的な１つの領域１２１０−１となった結果、ドローネグラフが更新されたためである。すなわち、ドローネ辺１００１−４はＳ１１０４により削除され、またドローネ辺１００１−２と１００１−３とがＳ１１０５により統合されて１２０１−１となっている。ここで１２０１−１においてドローネ辺の下端は、領域５０１−２と５０１−３との中間点に取るものとした。なお図１２においては、符号は省略したが、鼻と同様に右目、左目、口においても統合が行なわれた結果、各々が１つの領域になっており、新たなドローネ辺１２０１−２、１２０１−３が生じている。
【００２８】
ここで図１１のアルゴリズムにおいては、条件１および条件２における「規定のパラメータ」は、実験的に定めるものとする。また図１１の処理全体を適当な制約条件の下に繰り返して適用して、３つ以上の領域を１つに統合する様にしても良い。更に、領域の統合の可否の判定には多様なルールが考えられるので、それらでＳ１１０２〜Ｓ１１０３を置き換えても良い。
【００２９】
以上のステップにより統合済領域ドローネグラフ１２００が得られたので、これに対して従来法と類似の手法を適用する事により、画像認識機能（本実施例では顔の認識機能）を実現する事ができる。すなわちＳ３０６として、標準顔グラフとのマッチングを行う。この詳細を図１３から図１５を用いて説明する。
【００３０】
まず図１３は、人間の顔の普遍的な構造をグラフの形で表現する「標準顔グラフ」１３００を示したものである。すなわち、人間の顔には４つの部位（右目、左目、鼻、口）が存在し、これら全体が輪郭線で囲まれている。ここで各部位の位置関係を領域ドローネグラフで表すと、１３００に記した通りとなる。すなわち、右目と左目は隣接関係にあり、ドローネ辺１３０１で結ばれる。同様に右目と鼻、左目と鼻、鼻と口も隣接関係にあり、各々ドローネ辺１３０２、１３０３、１３０４で結ばれる。一方、右目と口および左目と口は中間に鼻があるため隣接関係とはならず、従って図中の１３１１および１３１２に相当するドローネ辺は存在しない。図ではドローネ辺が存在しない事を破線で示した。以上の部位は輪郭線１３２０で囲まれる。ここで輪郭線はいくつかのドローネ辺が概ね滑らかに連続したものである。
【００３１】
上記１３００に基づいて、標準顔グラフとのマッチング（Ｓ３０６）は図１４のフローチャートで示されるアルゴリズムにて実行できる。すなわち、まず統合済領域ドローネグラフ１２００に含まれる輪郭線候補を列挙する（Ｓ１４０１）。このステップは従来法で開示したのと同様に、隣接する領域の適当な系列を作成して、それらを結ぶドローネ辺が概ね滑らかに方向を変えてゆく事を確認すれば良い。この結果列挙された輪郭線候補に対して、以下のＳ１４０３〜Ｓ１４０５を繰り返す（Ｓ１４０２）。まずＳ１４０３において、輪郭線の内部に含まれる領域（統合済のもの）の数が、顔の部位の数である４に等しいか否かを確認し、否であれば引き続くＳ１４０４〜Ｓ１４０５はスキップする。等しい場合は更にＳ１４０４において、輪郭内の領域から作成される領域ドローネグラフが、標準顔グラフ１３００と相同であるか否かを確認する。すなわちより詳細には、４つの領域の内で他の３つ全てと隣接するものがあれば、そこを鼻と見なす。次に、鼻のみと隣接する領域を口と見なす。残りの２領域は右目と左目になるべきなので、この両者が隣接している事を確認する。以上の条件に全て適合すれば、輪郭内の領域は標準顔グラフ１３００と相同な領域ドローネグラフを構成していると結論できる。これらの結果、相同で無いと判定された場合は、引き続くＳ１４０５はスキップする。相同な場合はＳ１４０５に進み、輪郭内の各領域を対応する顔の部位として登録する。以上の繰返しを完了する事により、標準顔グラフとのマッチング（Ｓ３０６）が完了する（Ｓ１４０６）。
【００３２】
図１５は図１４に従ってＳ３０６を統合済領域ドローネグラフ１２００に適用した例を示す。まずＳ１４０１により輪郭線の候補が多数列挙されるが、それらの一つとして図の１５０１−１、１５０１−２、……、１５０１−ｎで示した候補が含まれる。この候補に対してＳ１４０３〜Ｓ１４０５を適用すると、まず輪郭線内部の領域の数は、Ｓ３０５による統合の結果４つとなっているので、Ｓ１４０３の条件は成立する。更にＳ１４０４においては上述の条件に適合する事が確認される。すなわちドローネ辺１００１−１が１３００における１３０１に、１２０１−１、１２０１−２、１２０１−３が各々１３０２、１３０３、１３０４に対応する。更に１３１１、１３１２に相当するドローネ辺は１５００に存在しない。以上から標準顔グラフ１３００との相同性が確認されたので、その結果をＳ１４０５にて登録する。
【００３３】
ここまでの各段落で説明の通り、図３におけるＳ３０３〜Ｓ３０６により顔の有無が判定できたので、その結果を冒頭に述べた通りＳ３０７〜Ｓ３１０にて扱う。ここでＳ３０８における表示は、たとえば図１６の様に、入力画像４００に部位の名称を重畳させて示せば良い。
【００３４】
以上、本発明の一実施例を説明したが、この実施例を変形した様々な方法も考えられる。たとえば、Ｓ３０７において顔が発見されなかった場合は、Ｓ３０２に戻って画像２値化をやり直してＳ３０３以下をリトライする、としても良い。またＳ３０６において標準顔グラフとのマッチングが失敗した場合は、Ｓ３０５に戻って領域の統合をやり直しても良く、この場合にはＳ３０５で述べた「規定のパラメータ」を適宜変更して処理する方法が考えられる。更にＳ３０６においては、単に領域ドローネグラフの相同性を判定するのに留まらず、各領域が人間の顔の部位として妥当な大きさや形状を持つかどうか、より具体的には左右の目は概ね同一サイズ化かどうか、目が口よりも大きい事はないか、等を判定する機能を持たせても良い。また標準顔グラフ１３００においては、右目（左目も同様）と口とは隣接関係に無いとしたが、両者の隣接の度合いが微小ならば隣接しても良い、というルールにしても良い。ここで「隣接の度合」は、図８において両領域の支配域がどの程度境界線を共有するか、という情報から決定できる。
【００３５】
以上、人物顔の検出を例として実施例を示したが、冒頭に述べた通り本発明は本実施例に限定される事なく、規定の構造を持つ物体が画像の中に含まれるかを判定する方法として、広範に応用できる。たとえば円形又は方形の構造物の中に１２個の文字領域が概ね円形状に配列されていれば、それが時計である事が本発明により容易に判定できる。より一般には、ある種の構造物が何らかの生成規範に従って構成されている場合、その規範をグラフ構造によって表現できるならば、一つ一つの具体的な物体（個体）には違いがあっても、本質的に同種の物である事が本発明により認識できる。
【産業上の利用可能性】
【００３６】
本発明は画像認識技術を応用した各種の映像処理装置で利用可能であり、より具体的には映像監視装置、ビデオ編集装置、ディジタルカメラなどへの応用が期待できる。
【図面の簡単な説明】
【００３７】
【図１】 連結領域を含む２値画像に対して図２の概念を拡張する方法を説明する図。（ａ）原義に従い作成されたボロノイ図の一例。（ｂ）（ａ）から「領域ボロノイ図」「領域ドローネグラフ」を作成する方法。
【図２】 計算幾何学の基礎概念「ボロノイ図」「ドローネグラフ」を説明する図。（ａ）平面上の点集合の１例。（ｂ）（ａ）から作成される「ボロノイ図」「ドローネグラフ」の定義を説明する図。
【図３】 本発明の実施例である顔認識算法の全体構成を示すフローチャート。
【図４】 実施例における入力画像の一例を示す写真。
【図５】 入力画像を２値化した結果の例を示す図。（ａ）２値化した結果そのものを示す図。（ｂ）（ａ）に対して説明用の符号を付した図。
【図６】 ステップ３０３「領域ボロノイ図作成」の算法を示すフローチャート。
【図７】 領域ボロノイ図を作成する別の方法「領域逐次拡張法」を説明する図。
【図８】 ステップ３０３の結果得られる領域ボロノイ図の一例を示す写真。
【図９】 ステップ３０４「領域ドローネグラフ作成」の算法を示すフローチャート。
【図１０】 ステップ３０４の結果得られる領域ドローネグラフ。
【図１１】 ステップ３０５「領域の統合」の算法を示すフローチャート。
【図１２】 ステップ３０５の結果得られる統合済領域ドローネグラフの一例。
【図１３】 ステップ３０６で用いる標準顔グラフを説明する図。
【図１４】 ステップ３０６「標準顔グラフとのマッチング」の算法を示すフローチャート。
【図１５】 ステップ３０６によるマッチングの結果の一例を示す図。
【図１６】 本実施例により顔の認識に成功した例を示す写真。
【図１７】 従来法による線分の抽出技術を説明する図。
【符号の説明】
【００３８】
１０１…母点（値が「１」の画素）
１１０…連結領域
１２０…領域ボロノイ分割における分割線
１３０…領域ドローネグラフにおけるドローネ辺
１５０、２５０…原義のボロノイ分割における分割線
２６０…原義のドローネグラフにおけるドローネ辺
【特許請求の範囲】
【請求項１】
２値画像から特定の構造物を検出する方法であって、当該２値画像は被写体を現す画素値１および背景を現す画素値０のいずれかのみからなり、画素値１の画素が複数の連結な領域を構成する場合において、まず画素値１の画素を母点とみなしてボロノイ分割を行なった後、ある領域に属する全ての画素の支配域の和を求める事により当該領域の支配域を定め、ある２つの領域に関して夫々の支配域が隣接する場合に当該２つの領域を辺で結んだグラフを作成し、上記グラフ構造に沿って上記特定の構造を検出する事を特徴とする画像認識方法。
【請求項２】
請求項１における領域の支配域を求める方法であって、全ての領域に対して当該領域の外形線を求めた後、全ての領域に対して外形線から外側へ逐次的に支配域を拡張して行き、ある２つの領域の支配域が接触した場合に当該２つの領域を辺で結んだグラフを作成する事を特徴とする画像認識方法。
【請求項３】
請求項１記載の方法を利用した画像認識方法であって、上記で得られたグラフにおいて辺で結ばれた複数の領域を所定の規則に従って１つの領域に統合する手続きを含む事を特徴とする画像認識方法。
【請求項４】
請求項１記載の方法を利用した画像認識方法であって、請求項１または請求項３により得られたグラフが、特定の構造を部分的に含むか否かを判定する事により、特定の構造物が当該２値画像に含まれるか否かを判定する事を特徴とする画像認識方法。
【請求項１】
２値画像から特定の構造物を検出する方法であって、当該２値画像は被写体を現す画素値１および背景を現す画素値０のいずれかのみからなり、画素値１の画素が複数の連結な領域を構成する場合において、まず画素値１の画素を母点とみなしてボロノイ分割を行なった後、ある領域に属する全ての画素の支配域の和を求める事により当該領域の支配域を定め、ある２つの領域に関して夫々の支配域が隣接する場合に当該２つの領域を辺で結んだグラフを作成し、上記グラフ構造に沿って上記特定の構造を検出する事を特徴とする画像認識方法。
【請求項２】
請求項１における領域の支配域を求める方法であって、全ての領域に対して当該領域の外形線を求めた後、全ての領域に対して外形線から外側へ逐次的に支配域を拡張して行き、ある２つの領域の支配域が接触した場合に当該２つの領域を辺で結んだグラフを作成する事を特徴とする画像認識方法。
【請求項３】
請求項１記載の方法を利用した画像認識方法であって、上記で得られたグラフにおいて辺で結ばれた複数の領域を所定の規則に従って１つの領域に統合する手続きを含む事を特徴とする画像認識方法。
【請求項４】
請求項１記載の方法を利用した画像認識方法であって、請求項１または請求項３により得られたグラフが、特定の構造を部分的に含むか否かを判定する事により、特定の構造物が当該２値画像に含まれるか否かを判定する事を特徴とする画像認識方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２００９−２７７２０５（Ｐ２００９−２７７２０５Ａ）
【公開日】平成２１年１１月２６日（２００９．１１．２６）
【国際特許分類】
【出願番号】特願２００８−１５２２１０（Ｐ２００８−１５２２１０）
【出願日】平成２０年５月１５日（２００８．５．１５）
【出願人】（５０８１７３１１８）
【Ｆターム（参考）】
【公開日】平成２１年１１月２６日（２００９．１１．２６）
【国際特許分類】
【出願日】平成２０年５月１５日（２００８．５．１５）
【出願人】（５０８１７３１１８）
【Ｆターム（参考）】
[ Back to top ]