JP5192315B2 - ２値画像を領域分割するための凹点検出方法 - Google Patents

Description

本発明はディジタル画像処理技術に係り、特に２値化された領域を複数の素図形に分割する際に必要となる、輪郭線上の凹点を検出する技術に関する。

映像情報機器の進歩により、テレビやビデオの映像を計算機によって処理する技術が広く普及しつつある。例えば映画をビデオ化した映像では、旧来は映像が単に受像機に表示されるのみで、ここから特定の出演者が映されているシーンを抜き出そうとすると、視聴者が目視でシーンを選択する必要があった。これがディジタル映像処理の普及につれて、映像中の１コマ（以下「画像」と表記する）にどんな物体や人物が写っているかを、自動的に抽出できるようになりつつある。

この様な機能は通常、画像中の物体の形状を既知の物体と比較する事、すなわち何らかのマッチング作業を行なう事で実現される。しかしながらマッチング作業では、物体が１つずつ個別に撮影されている事が前提条件となる。従ってマッチング作業の前段階として、複数の物体を個々のものに分割する作業が、しばしば必要となる。典型的な例として、画像に２人の歩行者が映されている場合、両者がすれ違う時に物体が重なりあう。この場合、一人ずつに分割しないと、それが歩行者（人間）である事を検出できなくなる。

上記の様な分割を自動的に行なうための類似技術として、特許文献１では以下の発明（以下「従来法」と記す）が開示されている。すなわち、人間の手の映像を入力として、まず手の輪郭線（エッジ）を抽出した後、輪郭線の方向が急激に変化する点（特許文献１における「屈曲点」）を検出する、というものである。この結果２本の指の境界が、屈曲点として検出される。これにより、特許文献１には明記されていないが、手の映像から複数の指を分割する、という発明が開示されている。
特開２００１−３４７６４「動画像処理方法、及び装置並びに媒体」

しかしながら上記の従来法では、輪郭線の方向がどの程度急激に変化すれば「屈曲点」とするべきか、という点が明確に述べられていない。この結果、図２に示すような図形を上手く分離できない。図２は２つの円が重なった図形であり、重なりが（ａ）は小さく（ｂ）は大きい。両者共に図中の点２０１〜２０２を結ぶ線分で切断すれば、図形は２つの円（の一部）に分割される。これに従来法を適用する場合、変化の判定基準をたとえば角度９０度に設定したとすると、（ａ）は分割されるが（ｂ）は分割の対象とならず、円が２つあるという事実を見失う事になる。図２における点２０１の角度は、円の重なりが大きくなるに従いいくらでも大きくなるので、一般的に適切な判定基準を決定する事は原理的に不可能である。このため、屈曲点の判定基準を応用場面に応じて実験的に設定する必要が生じ、汎用性の低い方法となっていた。

本発明の目的は上記の課題を解決して、広範囲の画像に対して一般的に適用できる分割方法を提供する事にある。このための核心技術として、経験的な判定基準を用いずに輪郭線上の凹点を検出する方法を提供する。ここで凹点とは文字通り輪郭線上の窪んだ点であり、従来技術における「屈曲点」のうち輪郭線が外側方向に屈曲しているものを意味する。凹点が検出できれば、それに基づいて図形を分割する事は、比較的簡単な作業となるので、本明細書においては凹点を検出する方法に絞って発明を開示する。

上記の課題を解決するためには、角度などの概念を用いずに凹点を定義できれば良い。このために本発明では、下記の幾何学的性質に基づいて、新たな凹点の定義を開示する。

まず、凹点を定義するという事は、それと相補的な概念である凸領域を定義する事と等価である。ここで凸領域は、通常の意味での幾何学（ユークリッド幾何学）においては以下の様に定義されている。
「単連結の領域において、領域中の任意の２点を結ぶ線分が、常に当該領域の内部にある場合、当該領域を凸であると言う。」
しかしながらこの定義は、ユークリッド幾何学すなわち点が連続的に存在する事を前提としている。本発明はディジタル画像を対象としたものであり、そこでは点（画素）が離散的にしか存在しない。この場合、領域の内部／外部という概念が曖昧になる。典型例として図３（ａ）に示す５点からなる領域を考えると、図中の線分３０１が図形の内部か外部かは明確でない。また図３（ｂ）は２値画像３０２の中に直角三角形３０３を描いた例である。画素が２値でかつ離散的に存在する限り、直角三角形をこれ以上正確に描くのは不可能である。しかしながら同図の斜辺は微視的にみるとギザギザの折線であり、直線とは言い難い。しかしながらこの折線は直線を可能な限り忠実に描いたものであるから、これが実は直線であり、従って直角三角形は凸図形である事を示す様な定義が必要である。

そこで本発明では、計算幾何学の概念を用いて上記の定義を変換する。計算幾何学では、「凸包」という概念が知られている。凸包とは図４（ａ）に示す通り、４０１−１等の与えられた点の集合を包含する最小の凸図形４１０の事を言う。これは点が有限個の場合は必然的に凸多角形となる。これを用いれば、上記の凸領域の定義は以下の様に言い換えられる。
「ある領域が、その領域から定められる凸包と一致する場合、その領域は凸である。」
ここで凸包は、領域が有限離散個の点の集合からなる場合、以下の手続きにより作成できる事が知られている。すなわち、図４（ｂ）に示す通り、まず領域の最も右側にある点（図４（ｂ）における点Ｐ０）を求める。この結果、領域に属する点は全て図中の線分４２０の左側に存在する（この性質を以下で「左側ルール」と呼ぶ）。次に、有向線分４２１を定める。ここで４２１は、Ｐ０を始点として左側ルールが成立ち、かつ４２０となす角度（左折の大きさ、図中の角度ａ０）が最小になる様な線分である。この様に４２１を定めた結果、凸包の次の頂点となる点Ｐ１が求まる。以後同様に繰り返して、有向線分４２２および頂点Ｐ２、……、を定めて行く。領域は有限の大きさなので、この繰り返しは有限回で終了し、最後の有向線分の終点は最初の頂点Ｐ０となる。以上で得られる多角形Ｐ０Ｐ１Ｐ２……Ｐｎ−１が、当該領域の凸包である。

凸包は多角形の一種であるから、その内部／外部という概念は、点（画素）が離散的にしか存在しない場合でも明確に定義できる。また、凸包の外部には当該領域に属する点は存在しない事は、上記の手続きから明らかである。これらの結果、凸領域の定義を更に言換える事ができる。すなわち、
「ある領域から作成される凸包の内部に、当該領域に属さない点（画素）が含まれない場合、当該領域を凸領域と呼ぶ。」
以上の定義に基づき、凹点が存在する事の判定が可能となる。すなわち、ある領域の全部または一部を取出した場合、その部分が上記の凸領域の定義に合致すれば、凹点は存在しない。たとえば図１に示す通り、（ａ）の領域１０１は凸領域であり凹点は存在せず、（ｂ）の領域１０２は凸領域ではなく図中の点１１０が凹点となる。この方法によれば、従来法における角度の設定という課題を経る事なく、凹点が検出できる。

但し上記の定義をそのまま凹点検出に適用するのは効率的でない。
すなわち上記によれば、まず当該領域の凸包を図４に示した手順により求めねばならない。この為には凸包の頂点（「包絡点」と称する文献もある）を求める必要があるが、通常は外形線上のどの点（画素）が頂点となるか自明ではなく、外形線を辿って頂点を探索する必要が生じる。領域の形状が複雑な場合、ある頂点から次の頂点を求めるために、外形線の長さの半分以上を探索する場合もあり、処理に手間がかかる。更に、仮に凸包が求められたとしても、その内部に領域外の点が含まれるか否かを判定する為には、外形線を再度辿る、あるいはそれと等価な何等かの処理を行なう必要があり、処理に重複を生じる。
本発明では以上の状況をも考慮して、凸包を陽に求める事なく、かつ前述した凸領域の定義に則って凹点を検出する方法を開示する。

以上に拠った本発明の特徴は、以下の通りである。すなわち本発明の第１の特徴は、２値画像内の領域に対して、外形線上の凹点を求める方法であって、当該領域が形成する凸包の内部に領域外の点が存在するか否かを判定する事により凹点が存在するか否かを決定する方法において、当該領域の外形線を方向差分符号で表現した後に、上記方向差分符号の系列を、方向が隣接する２つの符号のみからなる部分系列（「２方向系列」と称する）に分割するステップと、得られた２方向系列の集合に対して隣接する２者の方向を比較する事により両者の間に凹点が存在するか否かを決定する隣接凹点判定ステップと、得られた２方向系列の集合に対して個々の２方向系列の内部に凹点が存在するか否かを決定する内部凹点判定ステップと、を備える事にある。

また本発明の第２の特徴は、第１の特徴を有する凹点検出方法において、上記内部凹点判定ステップは、判定対象となる２方向系列をラン表現に変換した後、隣接する２つのラン（「ラン対」と称する）に対して各々のラン長の差を当該ラン対の指標とし、左記指標の変化に基づいて凹点が存在するか否かを決定する事にある。

また本発明の第３の特徴は、第２の特徴を有する凹点検出方法において、前期指標の変化が高々１のみである区間（「擬直線」と称する）を検出し、当該区間に対しては他の区間と別の凹点判定ステップを適用する事にある。

また本発明の第４の特徴は、第３の特徴を有する凹点検出方法において、当該擬直線の内側に含まれる画素数を当該擬直線に対応する指標の系列から算出するステップを有し、左記ステップにより算出された画素数を、当該擬直線の始点と終点を斜辺とする直角三角形の面積と比較する事により、前記凸包の内部に領域外の点が存在するか否かを判定する事にある。

また本発明の第５の特徴は、第４の特徴を有する凹点検出方法において、底辺の長さがｍかつ垂辺の長さがｎである直角三角形の面積を、下記の数式
（（ｍ＋１）×（ｎ＋１）−ｇｃｄ（ｍ、ｎ）−１）÷２＋ｇｃｄ（ｍ、ｎ）＋１
但しｇｃｄ（ｍ、ｎ）はｍとｎとの最大公約数を表す
を用いて算出する事にある。
なお上記の数式は、後述の数１と同じものである。

本発明によれば、従来法よりも汎用性の高い領域分割方法を実現する事が可能になり、画像認識技術やその応用装置の更なる高度化・高機能化に資する事ができる。

本発明は、コンピュータ上で動作するソフトウェアとして実施するのが妥当である。ここで使用するコンピュータは、いわゆる画像処理機能を実行できるものならば何でも良い。以下に実施例として、本発明の特徴を有するコンピュータプログラムの算法を、図面を用いて説明する。

図５は本発明による凹点検出方法のアルゴリズムの全体像を示すフローチャートである。以下、同図面に沿って算法の概要を説明する。

本発明による凹点検出方法は、ステップ５００（以下「Ｓ５００」等と略記する）以下の処理によって実現される。まず処理対象の２値画像を入力し（Ｓ５０１）、その中の処理対象となる領域に対して、その輪郭線を抽出する（Ｓ５０２）。ここで「領域」とは、２値画像において画素値が「１」の画素の連結集合の事であり、たとえば図６（ａ）では２つの領域６０１および６０２が２値画像６００に含まれている。ここで領域を構成する画素の中で、領域外の画素との境界部分にある画素を順次辿ったものを、当該領域の「輪郭線」と呼ぶ事にする。たとえば領域６０１に対しては、同図（ｂ）の矢印「→」等に沿って境界を辿る事により、輪郭線が得られる。なお本発明では境界を辿る際には、縦横に加えて斜め方向へ進む事も許す（いわゆる「８近傍ルール」）ものとした。

次に輪郭線の形状を、以下に述べる「方向差分符号」の系列とした表現に変換する（Ｓ５０３）。方向差分符号とは、２値画像で２つの画素が隣接する場合に、片方がもう一方からみてどの方向にあるかを符号化して表現するものである。輪郭線は隣接する画素の系列であるから、その形状を表現するには画素の位置を示すよりも、画素がどの方向に並ぶかを示した方が便利な場合が多い。そこで図６（ｂ）で用いた８方向の矢印に対して、図７（ａ）で示す様な８種類の符号〈０〉……〈７〉を定めて、この符号を輪郭線に沿った系列として並べる事により、輪郭線の形状が表現できる。例えば図６（ｂ）に示した矢印の系列は、図７（ｂ）（説明の便宜上拡大して表示した）の７０１で示すとおり〈０１１１２１２２３２３３３３４５５５６５６６７６７７７７〉と表現できる。ここで用いられる８種類の符号〈０〉……〈７〉を「方向差分符号」と本書では記す。なお本明細書では他の符号や数値との混同を避けるため、方向差分符号を記述する際には山形括弧「〈 〉」で括る事とした。また図６の様に輪郭線が閉じた曲線をなす場合は、符号の開始位置を何処にとるかに任意性が生じるが、これは処理プログラムの都合に従って適宜定めれば良い。なお本発明においては、符号〈０〉が最初に現れる位置（図７（ｂ）における位置７１０）を開始位置とした。

次に本発明においては、輪郭線上の９０度を越える屈曲を除去する（Ｓ５０４）。このステップは、９０度を越える屈曲が輪郭線上に存在すると後続する諸ステップにおいて煩雑な例外処理が生じるため、予め輪郭線をある程度滑らかにしておく事を目的とする。具体的には図８に示す通り、輪郭線上に±９０度（同図（ａ））、±１３５度（同図（ｂ））、および１８０度（同図（ｃ））の屈曲が存在する場合、屈曲の原因となる画素を輪郭線から除去する作業を行なう。この結果、方向差分符号系列で引き続く２つの符号は、同じか差が±１かのいずれかに限られる事になり、その後の処理が簡略化できる。なお本ステップを実現する方法としては、方向差分符号系列を先頭からスキャンして行き、図８に当てはまる箇所を図示の規則により書き換えて行く、という操作を繰返すプログラムを作成すれば良い。

ここまでに述べた諸ステップはまとめて、本発明による凹点検出方法における前処理段階５５０となる。これらの諸ステップは、入力画像の諸特性に応じて適宜省略又は簡略化して良く、たとえば入力画像６００が既に何らかの平滑化処理を経ている事が確実な場合は、Ｓ５０４を省略または簡略化できる。またこれらの諸ステップはいずれも、画像処理分野で周知の技法であるので、実装に関する詳細な説明（流れ図等）は省略する。

以上の前処理段階５５０の基に本発明においては、引続くステップとして輪郭線を２方向系列に分割する作業を行なう（Ｓ５０５）。ここで２方向系列とは、本発明の第１の特徴で述べた通り、方向差分符号において方向が隣接する２つの符号値を組にした系列の事を言う。
具体的には、図９（ａ）に示される領域９００に対して図９（ｂ）９１０の通り方向差分符号の系列が得られるが、これを更に図９（ｃ）の要領で、（０１）からなる２方向系列、（１２）からなる２方向系列、……、（７０）からなる２方向系列、に分割する。

この様に分割する事で、輪郭線の大局的な方向を表現する事ができる。たとえば円の輪郭線を方向差分符号で表現した場合、図１０に模式的に示される様に、円の最上点の近傍では、符号〈１〉がまとまって出現する。同様に最右点、最下点、最左点の近傍で符号〈３〉、〈５〉、〈７〉が各々まとまって出現する。更にこれらから４５°傾いた付近で、符号〈０〉、〈２〉、〈４〉、〈６〉が各々まとまって出現する。これらの中間となる区間では２種類の符号が混在して出現する事になり、たとえば符号〈０〉と〈１〉との間は〈０１〉からなる２方向系列が形成される。なお２方向系列〈０１〉には定義により、前後の〈０〉および〈１〉のみからなる区間も含まれ、従って２方向系列〈０１〉と〈１２〉とは、〈１〉のみからなる区間を共有する（他の組合せも同様）。ここで各２方向系列の内部においては、微視的には方向が逆順で現れる事がありうる。たとえば図９（ａ）の例では、図中の点９０１の所で符号〈１〉の後に符号〈０〉が現れており、微視的に見れば輪郭線が凹型をしている様に見える。しかしながらこれは図３にも示した通り、画素が離散的に存在するため生じる現象であり、これのみからこの点が凹点であるとは断定できない。２方向系列を用いれば、この様な微視的な問題に囚われずに、大局的に凹凸を判定できる。

以上で述べた分割作業を実行するためには、方向差分符号系列を前方からスキャンして行き、３種類目の符号が出現した時点で分割箇所を決定する、という操作を行なうプログラムを作成すれば良い。これらの操作は文字列処理技術において周知の技法であるので、詳細なフローチャートは省略する。

以上の通り２方向系列への分割が完了したので、これを用いて本発明の特徴である凹点検出を、引き続くＳ５０６以降で行なう。この最初の段階としてＳ５０６からＳ５０８により、２方向系列の境界部分に凹点が存在するか否かを判定する。すなわち、たとえば２方向系列〈０１〉に引き続いて〈１２〉が出現すれば、当該領域は大局的には凸であると判定し、逆に〈７０〉が引き続いて出現すれば、両者の接続部分が非凸図形となっていると判定する。後者の例を図１１に示す。この例では同図（ａ）に示す方向差分符号系列１１００が２つの２方向系列１１０１および１１０２に分けられ、すなわち２方向系列〈０１〉に〈７０〉が引き続いて出現している。この輪郭線の形状は同図（ｂ）の通りとなり、局所的な凸包１１１０の上に領域外の画素１１１１−１および１１１１−２が存在するので、凸領域の定義に反している。この様に、次の系列が図１０で示した方向（これを「凸方向」と記した）であるか否かの判定を行なって（Ｓ５０７）、否の場合には両者の接続部分を凹点として登録する（Ｓ５０８）、という処理を全ての２方向系列に対して繰り返す（Ｓ５０６）事により、与えられた領域が大局的に凸領域かどうかについて判定が完了する。なおここで登録とは、画像処理装置のメモリに記憶する方法、外部記憶装置に出力する方法、等が考えられるが、凹点の存在情報を以降の処理で利用できればどの様な方法でも良く、本発明ではその詳細は規定しない。また接続部分が多数の画素からなる場合は、たとえば中間点のみで代表させても良い。

引き続くステップＳ５０９〜では、１つの２方向系列の内部に凹点が存在するか否かを判定する。これらのステップを以下に説明するが、そのための準備としてまず、本発明の特徴である「ラン対」および「擬直線」とは何かを説明する。

既に説明の通り、本発明は「２方向系列」すなわち方向差分符号において方向が隣接する２つの符号値を組にした系列を、処理の単位としている。この下では、系列に含まれる符号は２種類のみであるから、１つの符号が連続して現れる回数を用いて、系列を表現する事ができる。すなわち図１２の例に示す通り、２方向系列１２００において符号〈０〉と〈１〉とが各々何回ずつ連続するかを数えると１２０１の通りとなり、従って１２１０で示される表現でこの２方向系列を表す事ができる。この様な表現方法は「ラン表現」として知られており、画像処理装置（たとえばＦＡＸ装置）で実用されている。なお本明細書では他の符号や数値との混同を避けるため、ラン表現を記述する際には「」で括る事とした。

「ラン対」とは上記の「ラン表現」において、隣接する２つのランを１組にして考えるものである。すなわち図１３に示す通り、符号〈０〉のランと〈１〉のランとを端から２つずつ組にして考える。この様にすると次に述べる様な利点が得られる。まず、処理の対象となる輪郭線は十分に滑らかであって、直線又は直線に近い形状を持っているものとする。図１３はこの様な例であり、（ａ）は図中の点１３１１と点１３１２とを結ぶ直線１３１０を、（ｂ）は図中の点１３１１と点１３２２とを結ぶ直線１３２０を、（ｃ）は十分に滑らかな曲線（楕円の一部）１３３０を、それぞれ２値画像上で近似的に表現したものである。（ａ）の場合、直線１３１０の傾きは１３／２１であり、この値は２／３よりも小さく１／２よりも大きい。従って直線１３１０は２値画像上では、傾き２／３の素辺１３０１と傾き１／２の素辺１３０２との組み合わせで近似される。この例で代表される様に、一般に傾き１／２以上の直線は、傾きが丁度ｎ／（ｎ＋１）となる場合を除いて、傾きｎ／（ｎ＋１）の素辺と傾き（ｎ−１）／ｎとの組み合わせで近似される。なお以上においてｎは適当な正整数を表すものとする。直線の傾きが１／２以下の場合も図１３（ｂ）に示す通り、傾き１／ｎの素辺と傾き１／（ｎ＋１）の素辺との組み合わせで近似される。輪郭線が滑らかに曲がる場合は、同図（ｃ）に例示した様に同図の（ａ）と（ｂ）とが滑らかに接続される場合と考えられる。

以上の図１３における素辺１３０１、１３０２等は「ラン対」の一種であるが、同図の様に輪郭線が十分に滑らかな場合は、各素辺は次の性質を持つ事が、同図の例から確認できる。
性質：２つのランのうち少なくとも一方はラン長が１となる。
従って、輪郭線が滑らかである事を前提とすれば、「ラン対」を記憶する際に２つのラン長を両方記憶する必要は無くなり、その代りに両者の差を記憶しておけば良い。すなわち、あるラン対を構成する２つのラン長をｍ、ｎ（これを「ラン対（ｍ、ｎ）」と記す）とすると、値（ｍ−ｎ）のみを記憶しておけば良い。ここで値（ｍ−ｎ）の事を、当該ラン対の「指標」と以後呼ぶ事にする。図１３では（ａ）（ｂ）（ｃ）各々の例において、１３１５、１３２５、１３３５で示した２方向系列に対して１３１６、１３２６、１３３６で示したラン表現が得られ、これらから更に１３１７、１３２７、１３３７で示した指標の系列が得られる。なお本明細書では他の符号や数値との混同を避けるため、指標を記述する際には［ ］で括る事とした。

指標を利用すると、図１３における素辺の傾きは上記の表１の様に整理できる。また表に示される通り、指標が増減する事は素辺の傾きが増減する事と等価である。これらの性質を用いると、以下の様に凹点を検出する事が可能となる。まず表１に示した通り、指標が増減する事は素辺の傾きが増減する事と等価であり、特に指標が増減しないあるいは減少する場合は、素辺の傾きが一定または領域の内側方向（凸方向）へ変化する事であるから、その部分には凹点は存在しない。また指標が＋１だけ増加する場合は、後述する「擬直線」の可能性があり、凹点が存在するとは断定できない。しかしながら指標が＋２以上増加する場合は、２つのラン対が接続する部分に凹点が存在する。この様な例を図１４に示す。図１４の例は黒丸で示した輪郭線について、２方向系列１４１５を得た後にラン表現１４１６を経て指標の系列１４１７を得ている。なお図示は省略したが、図の下方が領域の内側であるとする。ここでは２番目のラン対から３番目へ進む際に、指標が１から３へ＋２だけ増加している。この場合、図の線分１４００が局所的な凸包となり、その内側（線分上を含む）に矢印で示した画素１４１０が存在するため、この領域は凸では無いと判定できる。ここで指標が他の値（たとえば２から４へ増加）であっても、線分１４００の両端が対称的に移動するのみで、画素１４１０が線分１４００の中点となる、という性質に変化は無い。また、指標の増加量がもっと大きい（たとえば＋３）場合は、線分１４００の傾きが本図よりも大きくなるので、画素１４１０は凸包の内部に入る。以上より、指標がどの様な値でも＋２以上の増加があれば、その領域は凸では無いと判定できる。本実施例ではこの性質を、図５におけるＳ５１４で凹点を検出するために利用する。なおこの判定方法は、ラン対の一方が２方向系列の始端または終端にある場合には図の線分１４００が引けなくなるため、これらの場合は除外して適用する。また実際の輪郭線では、ラン対（ｍ、ｎ）におけるｍとｎとが共に１より大きい場合もありうる。しかしながらこの様なラン対では、２つのランの接続箇所が明白な凸点となるので、この点を境に輪郭線を前後に分割して処理しても凹点を検出するためには支障は生じない。この場合にはラン対（ｍ、ｎ）を、分割の前半においてはラン対（ｍ、１）、後半においてはラン対（１、ｎ）と見なして処理すれば良い。

次に「擬直線」について説明する。図１３で示した通り、２値画像上では直線は２種類のラン対で表現され、それらの指標は１だけ異なる。そこで逆に、２方向系列をラン対指標で表現した後に、「指標が±１だけ異なる２種類のラン対」が継続する区間を、本発明では「擬直線」と呼ぶことにする。擬直線は、その区間が直線である可能性を示す必要条件となっている。また擬直線でない区間ではラン対指標が２以上変化する事になり、先述の方法により凹点を検出する事が可能である。

以上の様に「ラン対」および「擬直線」という概念が定義できる。これらを用いる事により、Ｓ５０９以降の処理は以下に述べる通りに構成できる。すなわち、Ｓ５１０からＳ５１９までの処理を全ての２方向系列に対して適用し（Ｓ５０９）、その結果登録された凹点に基づき分割処理を実施（Ｓ５２０）して、実行を終了（Ｓ５２１）すれば良い。ここでＳ５１０からＳ５１９までは、以下の通りに構成される。

まず、当該２方向系列を上述のラン対表現に変換し（Ｓ５１０）、解析開始点をラン対表現の始点とする（Ｓ５１１）。以上の２つのステップは、ラン対表現を利用して凹点を検出するための準備段階となる。なおラン対と同時にその指標も得ておく事にする。この下に、解析開始点から後ろの外形線がどの様な形状を持っているかを、以降のステップで分析する。すなわちまずＳ５１２として、解析開始点から始まるラン対が十分に凸となる区間を求める。具体的には引き続くラン対の指標を逐次比較して行き、指標が最初に増加する箇所を区間の終点とする。得られた区間が当該２方向系列の終点まで達したかを判定し（Ｓ５１３）、結果がｙｅｓすなわち終点まで達していれば、当該２方向系列にはこれ以上の凹点は存在しない事になるから、Ｓ５０９にループして次の２方向系列の分析を開始する。結果がｎｏの場合は、凸区間の最後となるラン対と更にその次のラン対とに関して、各々の指標を比較する（Ｓ５１４）。指標が２以上増加している場合は、図１４で説明した通り凹点が存在するので、次のラン対との接続部分を凹点として登録する（Ｓ５１５）。以上により次のラン対までの検出処理が完了した事になるので、更なる検出を続けるためには、解析開始点を次のラン対の始点として（Ｓ５１６）、Ｓ５１２以降を再度繰り返せば良い。なお以上の説明において、Ｓ５１５における登録はＳ５０８と同様に行えば良い。

一方、Ｓ５１４において指標が＋１しか増加していない場合は、この部分が前述の「擬直線」となっている可能性があり、凹点が存在するか否かは簡単に決定できない。そこでこのような場合は、まずＳ５１２により求めた区間の最後となるラン対を含む擬直線区間を求め（Ｓ５１７）、その擬直線区間の凹凸を判定する（Ｓ５１８）ものとする。しかる後に、当該擬直線区間が当該２方向系列の終点まで達したかを判定し（Ｓ５１９）、結果がｙｅｓすなわち終点まで達していれば、Ｓ５１３と同様にＳ５０９にループして次の２方向系列の分析を開始する。結果がｎｏの場合は更なる検出を続けるために、Ｓ５１５の場合と同様にＳ５１６を経てＳ５１２以降を再度繰り返す。

ここで疑直線に対する処理、すなわちＳ５１７およびＳ５１８について説明する。まずＳ５１７において２方向系列から疑直線を構成する区間を求めるが、既にＳ５１０においてラン対表現が作成されてその指標も得られているので、Ｓ５１７では指標の値が現在の値に対して＋０または＋１となる区間を求めれば良い。たとえば指標の系列が
［−２−１−２−２−１−１−２−２−１−２−３−２−４−４］（先頭の−２が解析開始点）
と得られていれば、先頭から−２または−１が引き続く区間を求める事になる。上記例の場合には、−２でも−１でもない指標が最初に現われるのは−３の箇所であるから、その直前までの
［−２−１−２−２−１−１−２−２−１−２］
が、疑直線を構成する区間となる。この処理は数値列の中から特定条件を満たす部分列を抜き出す処理であり、周知の技術で実現できるので詳細は省略する。

次にＳ５１８において、上記で求められた区間の凹凸を判定する。
この判定においては、図４に示した方法で凸包を作成しても良いが、先に述べた通り効率的でない。また実用面では、擬直線は実際に直線であるか、又は直線に十分近い形状である事が大半である。そこで本実施例では、擬直線に対して近似的ではあるが高速に凹凸を判定する方法を、図１５以降を用いて開示する。

図１５は擬直線の一例を示したもので、対応する２方向系列、ラン表現、指標の系列は各々１５１５、１５１６、１５１７に示した通りである。すなわちこの擬直線は指標が−２および−１となる２種類のラン対から構成されており、その具体的な形状は図示の通りである。ここで同擬直線の最初および最後のラン対に注目すると、両者における画素１５０１および１５０２が微視的に輪郭線の頂点となっている。これは両点を結ぶ線分１５００が、この輪郭線の局所的な凸包となっている可能性を示唆するものである。そこで線分１５００を仮の凸包とみなした場合、この内部（下方を内部とする）に領域外の点が含まれていれば、同擬直線を輪郭線とする部分は凸ではないと結論する。このための十分条件として、線分１５００の下方にある画素の数と領域内でかつ図の長方形１５０５に含まれる画素の数を比較して、後者の方が少なければ凸ではないと結論できる。ここで上記の２種類の画素数は、各々以下の通りの方法により計算できる。

まず領域内でかつ図の長方形１５０５に含まれる画素の数については、図１６に示す方法により算出できる。すなわち、まず当該擬直線に対する「参照擬直線」を想定する。参照擬直線とは当該擬直線と同一の指標の値を有する擬直線であって、その指標のうち値の大きい方が系列の前半に集中しているものを言う。たとえば図１５の擬直線の指標には−１が４回、−２が６回現れるから、これらをこの順に並べた
［−１−１−１−１−２−２−２−２−２−２］
という指標の系列１６１７を持つ擬直線が参照擬直線となる。これに対応する２方向系列、ラン表現は各々１６１５、１６１６の通りである。なお図では、参照擬直線を構成する画素を正方形で示した。ここで参照擬直線の下方の面積は図１６（ａ）に示す通り初等的に計算できる。すなわち、図１５における長方形ｒを、図１６（ａ）の３つの長方形１６０１、１６０２、１６０３に分けて考えると、
１６０１における下方の面積＝（ｉ１＋２）×（ｋ１×（ｋ１＋１）÷２）
１６０２における下方の面積＝（ｉ２＋２）×（ｋ２×（ｋ２−１）÷２）＋ｋ２
１６０３における下方の面積＝ｋ１×（（ｉ２＋２）×（ｋ２−１）＋１）
但し ｉ１＝指標のうち値の大きい方の絶対値、
ｋ１＝指標のうち値の大きい方の出現回数、
ｉ２＝指標のうち値の小さい方の絶対値、
ｋ２＝指標のうち値の小さい方の出現回数
となるので、これら３つの値を合計すれば良い。しかる後に、この合計値を基に当該擬直線の下方の面積を算出する。このためには図１６（ｂ）の原理を利用する。図１６（ｂ）は、擬直線において指標の現われる順序が変化した場合に、下方の面積がどのように変化するかを説明したものである。図の例では擬直線の指標が１６２０に示す［−１−２−２］から１６３０に示す［−２−１−２］へと変化している。この結果、元の擬直線が通過していた画素１６１１が直線の上方へ除外され、擬直線は画素１６１２を通る様になる。それ以外の部分では擬直線の形状は不変なので、結局画素１６１１による１画素分だけ面積が減少する。この原理を用いれば、当該擬直線における指標のうち値の大きい方が参照擬直線と比べてどれだけ後ろに出現するか、を合算する事により、参照擬直線と比べてどれだけ面積が減少したかを算出する事ができる。たとえば図１５および図１６に示した例では、
参照擬直線の指標１６１７：［−１−１−１−１−２−２−２−２−２−２］
当該擬直線の指標１５１７：［−２−１−２−２−１−１−２−２−１−２］
であるから、
４つ目の［−１］の出現位置：４番目→９番目、面積減少＝５画素
３つ目の［−１］の出現位置：３番目→６番目、面積減少＝３画素
２つ目の［−１］の出現位置：２番目→５番目、面積減少＝３画素
１つ目の［−１］の出現位置：１番目→２番目、面積減少＝１画素
となり、これらを合計した１２画素だけ面積が減少している事が計算できるので、前述の参照擬直線の下方の面積から１２画素を減じれば良い。なお以上の説明においては、指標の値が負またはゼロの場合を例に示したが、値が正またはゼロの場合は図１５および図１６を９０度回転して同様の計算を行えば良い。

次に線分１５００の下方にある画素の数については、図１７に示す方法により算出できる。すなわち、凸包の頂点の候補として２つの画素１７０１、１７０２が与えられた時、両者を結ぶ線分１７０５の下方（線分上を含む）にある画素数を求める。ここで１７０２は１７０１から水平方向にｍ画素、垂直方向にｎ画素離れているものとする。まずｍとｎとが互いに素な場合を同図（ａ）に示す。図には全部で（ｍ＋１）×（ｎ＋１）個の画素がある。このうち１７０１、１７０２の２つを除くと、線分１７０５の上には画素は存在せず、それらは線分１７０５により対称的に２分割される。従って、全部の画素数から２画素を除いたものを半分にして、これに２画素を再度加えれば、求める画素数が得られる。以上を式で表せば、
（（ｍ＋１）×（ｎ＋１）−２）÷２＋２＝（ｍ＋１）×（ｎ＋１）÷２＋１
が求める画素数である。一般にはｍとｎとが互いに素とは限らないが、この場合でも上記の考え方を拡張して画素数を算出する事ができる。すなわち同図（ｂ）に示す通り、この場合には線分１７１５上に画素１７２０−１、１７２０−２、……、が存在しうるが、これらを除いて考えれば、同図（ａ）と同様の計算が成り立つ。従って問題は線分１７１５上に画素が全部で何個存在するかという点に帰着するが、初等整数論による考察により、この個数は
ｍとｎとの最大公約数＋１（但し両端の画素１７１１、１７１２も含める）
である事が確認できる。従って求める式は、下記の数式１の通りとなる。なお当然の事であるが、同図（ａ）は同図（ｂ）においてｇｃｄ（ｍ，ｎ）＝１とした場合に他ならない。

但しｇｃｄ（ｍ，ｎ）はｍとｎとの最大公約数を表す

以上により、Ｓ５１８における近似的ではあるが高速な判定方法として、図１８のフローチャートで示す処理が実現できる。すなわち擬直線が指標の系列によって与えられたものとして（Ｓ１８０１）、まず図１６で示した方法により当該擬直線の下方の面積を求め（Ｓ１８０２）、引続き図１７で示した方法により凸包の候補の内部にある面積を求める（Ｓ１８０３）。両者を比較して（Ｓ１８０４）、前者の方が小さい場合には当該擬直線を凹点として登録し（Ｓ１８０５）、処理を終了する（Ｓ１８０６）。以上においてＳ１８０５における登録はＳ５０８と同等に行えば良い。なお当該擬直線の区間が長い場合には、その中点をもって凹点を代表させても良い。

以上により図５におけるＳ５１９までが実施できるので、それらにより求められた凹点を用いて、領域の分割を行う事が可能となる（Ｓ５２０）。この応用方法は様々に考えられるが、たとえば人間の横顔を入力して鼻の隆起点を検出する、などの応用が考えられる。これは、従来は困難とされた映像中から人間の横顔を自動検出する機能が、本発明を利用することにより可能となる事を示している。

なおここまでの説明においては、輪郭線が方向差分符号〈０〉および〈１〉で示される場合を主に取り上げて説明したが、座標を適宜回転あるいは鏡像反転させて考える事により、他の方向の場合にも本発明が適用できる事は言うまでもない。

以上、領域の輪郭線から凹点を検出する方法を開示した。これらの説明においては、輪郭線が基本的に凸区間からなり、凹点は凸区間の接続部分にのみ存在する、という領域を処理の対象とした。しかしながら一般には、輪郭線が本質的に凹図形を形成する領域も存在する。たとえば「三日月形」は、外側の輪郭線は凸図形であるが、内側の輪郭線は全体が凹図形であり、その中の特定の点のみを凹点とする事は合理性を欠く。この様な図形をどう扱うべきかは本発明の課題から外れるものであり、より上位の画像処理機能に扱いを委ねるものとする。なお輪郭線が凹図形である事は、領域の外側と内側を入換て考える事により、本発明と同様の算法で確認できる。これを利用すれば、たとえば輪郭線上の凹図形の部分をあらかじめ分離しておく、などの処理方法が上位の画像処理機能として考えられる。従って本発明は、凹図形も含めた一般の領域に対しても、応用の可能性を残すものである。

本発明は画像認識技術を応用した各種の映像処理装置で利用可能であり、より具体的には映像監視装置、ビデオ編集装置、ディジタルカメラなどへの応用が期待できる。

本発明で用いる凸領域の定義を説明する図（２値画像） 従来法による凹点検出の課題を説明する模式図 画素が離散的に存在する場合の課題を説明する図 計算幾何学による凸包の定義およびその作成方法を説明する図 本発明による凹点検出方法の全体の構成を示すフローチャート ２値画像における領域およびその輪郭線を説明する図 方向差分符号の定義および使用例を説明する図 Ｓ５０４における屈曲の除去方法を説明する図 方向差分符号を２方向系列に分割する方法を説明する図 滑らかな凸図形における２方向系列の挙動を説明する模式図 Ｓ５０７における凹凸の判定の根拠を説明する図 ２方向系列をラン表現に変換する方法を説明する図 ラン表現からラン対およびその指標を求める方法を説明する図 Ｓ５１４における凹凸の判定の根拠を説明する図 擬直線の例を説明する図 参照擬直線の例およびそれを用いた面積算出方法を説明する図 直線下の面積を算出するための数式１の根拠を説明する図 Ｓ５１８における擬直線の近似的な凹凸判定方法を示すフローチャート

符号の説明

５５０…前処理段階 １２０１…ラン長 １７０５，１７１５…凸包の候補となる線分

Claims (5)

1. ２値画像内の領域に対して、外形線上の凹点を求める方法であって、当該領域が形成する凸包の内部に領域外の点が存在するか否かを判定する事により凹点が存在するか否かを決定する方法において、当該領域の外形線を方向差分符号で表現した後に、上記方向差分符号の系列を、方向が隣接する２つの符号のみからなる部分系列（以下「２方向系列」と称する）に分割するステップと、得られた２方向系列の集合に対して隣接する２者の方向を比較する事により両者の間に凹点が存在するか否かを決定する隣接凹点判定ステップと、得られた２方向系列の集合に対して個々の２方向系列の内部に凹点が存在するか否かを決定する内部凹点判定ステップと、を備える事を特徴とする凹点検出方法。
2. 請求項１記載の凹点検出方法において、上記内部凹点判定ステップは、判定対象となる２方向系列をラン表現に変換した後、隣接する２つのラン（以下「ラン対」と称する）に対して各々のラン長の差を当該ラン対の指標とし、左記指標の変化に基づいて凹点が存在するか否かを決定する事を特徴とする凹点検出方法。
3. 請求項２記載の凹点検出方法において、前期指標の変化が高々１のみである区間（以下「擬直線」と称する）を検出し、当該区間に対しては他の区間と別の凹点判定ステップを適用する事を特徴とする凹点検出方法。
4. 請求項３記載の凹点検出方法において、当該擬直線の内側に含まれる画素数を当該擬直線に対応する指標の系列から算出するステップを有し、左記ステップにより算出された画素数を、当該擬直線の始点と終点を斜辺とする直角三角形の面積と比較する事により、前記凸包の内部に領域外の点が存在するか否かを判定する事を特徴とする凹点検出方法。
5. 請求項４記載の凹点検出方法において、底辺の長さがｍかつ垂辺の長さがｎである直角三角形の面積を、下記の数式
   （（ｍ＋１）×（ｎ＋１）−ｇｃｄ（ｍ、ｎ）−１）÷２＋ｇｃｄ（ｍ、ｎ）＋１
   但しｇｃｄ（ｍ、ｎ）はｍとｎとの最大公約数を表す
   を用いて算出する事を特徴とする凹点検出方法。

Images