"カメラによって撮像された画像から複数のエッジを抽出するエッジ処理部と、前記複数のエッジのエッジ点における法線の方向を求める法線ベクトル処理部と、前記複数のエッジのそれぞれについて、エッジ点から法線の方向の所定の距離において前記法線と直交する投票領域を求め、前記投票領域に含まれる点に、前記法線の方向に対応した得票値を加算する投票処理部と、前記画像に含まれるすべての点から、前記得票値が局所的に高い点である局所ピーク位置を抽出し、第1局所ピーク位置に加算された前記得票値に対応する前記法線の方向の角度の第1相対関係と、予め記憶された形状の内接円の接点における法線の方向の角度の第2相対関係とが一致するか否か判断する部分形状検出処理部と、前記部分形状検出処理部において一致すると判断された場合、前記第1局所ピーク位置に対応する第1相対スケール変化率及び第1相対回転角度を、前記第1局所ピーク位置、前記所定の距離及び前記得票値に対応する法線の方向の角度と、前記予め記憶された形状の内接円の中心点及び半径並びに前記接点における法線の方向の角度とに基づいて求める形状形態処理部と、前記第1相対スケール変化率と前記第1相対回転角度と前記予め記憶された形状とに基づいて、前記画像に含まれる図形を認識する形状認識処理部と、を備えることを特徴とする画像処理装置。前記部分形状検出処理部は、前記第1局所ピーク位置に加算された前記得票値に対応する前記法線の方向をクラスタリングし、クラスタリングの誤差が所定閾値よりも小さい場合に、前記第1相対関係と前記第2相対関係とが一致するか否か判断する請求項1に記載の画像処理装置。前記第1相対関係は、前記得票値に対応する前記法線の方向の角度の差分の絶対値であり、前記第2相対関係は、前記接点における法線の方向の角度の差分の絶対値である請求項1に記載の画像処理装置。前記局所ピーク位置が複数存在する場合において、前記形状形態処理部は、さらに、第2局所ピーク位置に対応する第2相対スケール変化率及び第2相対回転角度を求め、前記形状認識処理部は、前記第1局所ピーク位置と前記第2局所ピーク位置との相対位置関係と、前記第2相対スケール変化率と、前記第2相対回転角度とに基づいて、前記画像に含まれる図形を認識する請求項1に記載の画像処理装置。エッジ処理部は、カメラによって撮像された画像から複数のエッジを抽出し、法線ベクトル処理部は、前記複数のエッジのエッジ点における法線の方向を求め、投票処理部は、前記複数のエッジのそれぞれについて、エッジ点から法線の方向の所定の距離において前記法線と直交する投票領域を求め、前記投票領域に含まれる点に、前記法線の方向に対応した得票値を加算し、部分形状検出処理部は、前記画像に含まれるすべての点から、前記得票値が局所的に高い点である局所ピーク位置を抽出し、第1局所ピーク位置に加算された前記得票値に対応する前記法線の方向の角度の第1相対関係と、予め記憶された形状の内接円の接点における法線の方向の角度の第2相対関係とが一致するか否か判断し、形状形態処理部は、前記部分形状検出処理部において一致すると判断された場合、前記第1局所ピーク位置に対応する第1相対スケール変化率及び第1相対回転角度を、前記第1局所ピーク位置、前記所定の距離及び前記得票値に対応する法線の方向の角度と、前記予め記憶された形状の内接円の中心点及び半径並びに前記接点における法線の方向の角度とに基づいて求め、形状認識処理部は、前記第1相対スケール変化率と前記第1相対回転角度と前記予め記憶された形状とに基づいて、前記画像に含まれる図形を認識する画像処理方法。従来の技術では、任意形状を高速に検出できないという課題がある。一般化ハフ変換は任意形状に適用可能であるが、投票空間の次元数が高いため、高速実現が困難である。例えば、形状のスケール変換や回転のパラメータを考慮した場合、通常投票空間が3次元以上となる。また、特許文献3に記載の技術が高速に実現可能であるが、正多辺形以外の形状に対して、適用できない問題があった。また、従来の形状検出手法では、対象形状の構成成分を1つずつ検出するか、全構成成分を総合的に検出する。そのため、例えば、特許文献3ではエッジ点の強度を用いるため、特定の組合せの検出に対しロバスト性が不十分であった。本発明の目的は、画像から特定形状を高速に検出することができ、かつ、ロバスト性を改善することができる画像処理装置および画像処理方法を提供することである。本発明の画像処理装置は、カメラによって撮像された画像から複数のエッジを抽出するエッジ処理部と、前記複数のエッジのエッジ点における法線の方向を求める法線ベクトル処理部と、前記複数のエッジのそれぞれについて、エッジ点から法線の方向の所定の距離において前記法線と直交する投票領域を求め、前記投票領域に含まれる点に、前記法線の方向に対応した得票値を加算する投票処理部と、前記画像に含まれるすべての点から、前記得票値が局所的に高い点である局所ピーク位置を抽出し、第1局所ピーク位置に加算された前記得票値に対応する前記法線の方向の角度の第1相対関係と、予め記憶された形状の内接円の接点における法線の方向の角度の第2相対関係とが一致するか否か判断する部分形状検出処理部と、前記部分形状検出処理部において一致すると判断された場合、前記第1局所ピーク位置に対応する第1相対スケール変化率及び第1相対回転角度を、前記第1局所ピーク位置、前記所定の距離及び前記得票値に対応する法線の方向の角度と、前記予め記憶された形状の内接円の中心点及び半径並びに前記接点における法線の方向の角度とに基づいて求める形状形態処理部と、前記第1相対スケール変化率と前記第1相対回転角度と前記予め記憶された形状とに基づいて、前記画像に含まれる図形を認識する形状認識処理部と、を備える構成を採る。本発明によれば、画像から特定形状を高速に検出することができ、かつ、ロバスト性を改善することができる。以下、図面を参照して、本発明の実施の形態を詳細に説明する。以下に説明する実施の形態で、特定形状の線分の組合せとは、検出対象の画像の輪郭が1つ以上の線分を含むことである。輪郭は開形状でも閉形状でもよい。また、線分として曲線を含んでもよい。2006年7月17日出願の願番200610105667.3の中国出願に含まれる明細書、図面および要約書の開示内容はすべて本願に援用される。<実施の形態1>図1は、本発明の実施の形態1に係る画像処理装置の構成図である。図1に示す画像処理装置100において、格納部101は、検出対象の特定形状を標準テンプレートとして格納する。形状特徴処理部102は、格納部101に格納された検出対象の特定形状の標準テンプレートから特定形状の構成特徴を記述する構成特徴テーブルを生成する。例えば、形状特徴処理部102は、図2Aに示した標準テンプレートに対し、図3に示すような任意の3辺に3点で接する円以下、内接円というを抽出する。図3に示す例では、形状特徴処理部102は、計4つの内接円O1,r1;O2,r2;O3,r3;O4,r4を抽出する。形状特徴処理部102は、各内接円の中心点、半径、接点の法線方向、および内接円中心点間の相対位置関係を構成特徴テーブルとして表1のように記述する。直線の場合、各点の法線方向は同方向である。内接円に対して、接点の数だけ法線方向を求める。図3では、法線方向は全部で4つあるので、内接円間では法線方向を部分的に共有している。形状特徴処理部102の処理は通常オフラインで行う。エッジ処理部103は、カメラ等の撮像部から出力された入力画像に含まれる各図形のエッジを抽出する。例えば、図2Bに示す例では、図形S1、S2、S3の全ての図形のエッジを抽出する。本実施の形態ではエッジ抽出方法を限定しない。公知の方法、例えば、Canny、Sobel、LoGなどいずれの方法を利用してもよい。本実施の形態において、入力画像から図形の形状を認識する例で説明するが、格納された画像に対しても、図形の形状を認識する処理を適用可能である。法線ベクトル処理部104は、エッジ処理部103で求めた各エッジのエッジ点の法線方向を求める。例えば、法線ベクトル処理部104は、図2Bの原画像に対し、図2Cに示すエッジ点および法線方向を各図形について求める。投票処理部105は、エッジ点に対し、投票領域を求め、投票領域に属する各点の得票値を加算し、投票する。例えば、図5に投票領域の一例を示す。図5において、pはエッジ点、θはエッジ点pの法線方向、rは指定した投票半径、線分ABとCDは投票領域である。法線方向θは、エッジ点pの勾配方向である。線分ABと線分CDの方向は法線と直交し、長さは通常rに比例する。例えば、線分の長さLは次の式1で表される。L=arb...1但し、aとbは任意の係数である。投票処理部105は、投票半径rを、通常、ある範囲[rmin,rmax]において複数の値を順次に指定する。投票とは、投票領域ABとCDに属する全ての点qに対し、その得票値Sqを加算する。例えば、得票値Sqは、次の式2で表される。Sq=Sq1...2但し、投票処理部105は、Sqの初期値を同一値、例えば0にする。同時に、投票処理部105は、得票方向Dsqも記憶する。例えば、得票方向Dsqは、次の式3で表される。Dsq=θまたはθπ...3投票する際に、点qの位置を入力画像の画素点位置に設定しても画素点間の位置に設定してもよい。また、全画素点の可能な投票領域の和を投票範囲と言う。通常、投票範囲を画像範囲と同じ、つまり全画素点範囲に設定することができる。以上、投票処理の基本方法を説明した。しかし、投票範囲、投票領域、得票値の加算方法など具体的な計算方法は特に限定されない。例えば、特許文献3に提示した投票領域の設定方法を利用してもよい。部分形状検出処理部106は、形状特徴処理部102の処理結果と投票処理部105の処理結果に基づき、テンプレート形状に対応する線分の組み合わせを検出する。具体的に、図6および表1に示した内接円O1,r1の検出を例として、図6を参照して部分形状検出処理部106の動作フローを説明する。図6は、部分形状検出処理部106における内接円検出の処理を示すフローチャートである。まず、ステップ10では、部分形状検出処理部106本発明の候補位置算出部に相当が、投票範囲Qの全ての点qに対し得票値Sqの局所ピーク位置を全部求める。局所ピーク位置は得票値が局所的に高い点である。例えば、局所ピーク位置をxj,j1...Jで表現し、内接円中心点位置O1の候補位置とする。次に、ステップ11では、部分形状検出処理部106が、局所ピーク位置xjの得票方向を整理する。具体的には、内接円O1,r1に対する接点の法線方向の数n=3なので、投票処理部105で記憶された得票方向DSqを公知の方法で3つのクラスタにクラスタリングする。ここで、公知の方法としては、Kmeans手法がある。ステップ12では、クラスタリングの誤差が所定閾値よりも小さい場合YES、部分形状検出処理部106が、得票方向数をn=3にし、各クラスタの中心方向を局所ピーク位置xj,j1...Jの得票方向として設定する。更に、部分形状検出処理部106本発明の角度算出部に相当は、投票する3辺から候補位置への法線と、前記法線と各辺が交わる点を通る一定方向の線との角度を求める。言い換えると、部分形状検出処理部106は、得票方向を求める。ステップ13では、クラスタリングの誤差が所定閾値よりも小さくない場合ステップ12:NO、部分形状検出処理部106が、xjを内接円中心点位置O1の候補点でないと記憶する。次に、ステップ14では、クラスタリングの誤差が所定閾値よりも小さい場合ステップ12:YES、部分形状検出処理部106本発明の相対関係算出部に相当が、局所ピーク位置xj,j1...Jの得票方向の角度の相対関係が内接円O1,r1の接点の法線方向の角度の相対関係と一致するか否かを判断する。ステップ15では、各角度の相対関係が一致した場合ステップ14:YES、部分形状検出処理部106本発明の相対関係算出部に相当が、内接円中心点位置O1の候補点として、局所ピーク位置xjを記憶する。ステップ13では、各角度の相対関係が一致しない場合ステップ14:NO、部分形状検出処理部106が、xjを内接円中心点位置O1の候補点でないと記憶する。例えば、図4に示したように、内接円中心点位置O1の候補位置O1’の3つの得票方向θ1’,θ2’,θ4’が求まった場合、部分形状検出処理部106は、得票方向θ1’,θ2’,θ4’の角度の相対関係|θ1’-θ2’|,|θ2’-θ4’|,|θ4’-θ1’|が表1に示した3つの接点の法線方向θ4,θ1,θ2の角度の相対関係|θ1-θ2|,|θ2-θ4|,|θ4-θ1|と等しいかを判断する。しかし、必ずしも、θ1’とθ1、θ2’とθ2、θ4’とθ4の対応関係に限らなくてもよい。角度の相対関係|θ1’-θ2’|,|θ2’-θ4’|,|θ4’-θ1’|と角度の相対関係|θ1-θ2|,|θ2-θ4|,|θ4-θ1|それぞれが等しい場合、部分形状検出処理部106は、θ1,θ2,θ4それぞれの対応する得票方向を求める。ステップ16では、部分形状検出処理部106が、j=Jまで、全ての局所ピーク位置xjについて処理が完了したか否かを判断する。ステップ17では、全ての局所ピーク位置xjについて処理が完了していない場合ステップ16:NO、jに1を加算し、その後、ステップ11からステップ15までの処理を行う。全ての局所ピーク位置xjについて処理が完了した場合ステップ16:YES、ステップ18に進む。ステップ18では、部分形状検出処理部106が、内接円中心点位置O1に対応する局所ピーク位置O1’,対応半径r1’および対応得票方向θ1’,θ2’,θ4’を出力する。次に、形状形態処理部107は、形状特徴処理部102の処理結果と部分形状検出処理部106の処理結果に基づき入力画像上の形状と標準テンプレートとの相対スケール変化率と相対回転角度を求める。例えば、図2Cに示す4角形S1に対し、図4のように内接円候補O1’r1’が部分形状検出処理部106から出力された場合、形状形態処理部107は、r1’/r1で相対スケール変化率、θ1’-θ1θ2’-θ2θ4’-θ4/3で相対回転角度を計算する。形状認識処理部108本発明の認識部に相当は、形状形態処理部107で求められた各部分形状の相対位置関係より形状全体を検出する。形状認識処理部108は、形状形態処理部107で求めた相対スケール変化率と相対回転角度の結果を考慮し、O1’に対するO2’,O3’,O4’の相対位置関係が表1に示す各中心点の相対位置関係と一致するか否かを判断する。各相対位置関係が一致した場合、形状認識処理部108は、検出結果として入力画像に含まれる図形S1が図2Aに示すテンプレート形状と一致する旨を出力する。<変形例>上述の具体的な説明は本発明の範囲を制限しない。例えば、以下の利用形態も考えられる。内接円中心点位置O1に対応する部分形状の局所ピーク位置O1’が入力画像から検出された場合、相対スケール変化率、相対回転角度および表1に示す構成特徴テーブルを考慮し、局所ピーク位置O2’,O3’,O4’の位置は予測できる。投票処理部105の結果を用いて、予測された局所ピーク位置O2’,O3’,O4’付近に局所ピーク位置があるかを判断することによって形状検出も実現できる。また、図3のテンプレート形状に対し、4つの内接円でなく、その内の2つの内接円を表1の構成特徴テーブルに記述してもよい。2つの内接円および角度の相対関係を検出することより図形S1の形状検出を実現する。また、全ての内接円を利用しない場合、任意の内接円を選択可能である。また、半径の大きい順でもその他の基準でもよい。また、本実施の形態では、形状特徴処理部102が、任意の3辺に3点で接する円を抽出する例で説明したが、これに限られない。形状特徴処理部102が、任意の3辺以上に3点以上で接する円を抽出する構成としてもよい。例えば、形状特徴処理部102が、任意の4辺に4点で接する円を抽出する構成としてもよい。ここで、任意の4辺に4点で接する円を抽出する場合であっても、任意の3辺に3点で接する円を抽出することが観念される。また、形状認識処理部108からの検出結果は、上記過程を特定形状の有無を検出するか、特定形状に近い形状を抽出するか、のどちらに利用されてもよい。本実施の形態によれば、指定位置に線分が存在するかの検証は高速に実現可能のため、本実施の形態においても特定形状を高速に検出することができる。また、複数線分の組合せを検出するため、エッジ点の強度よりも分布のほうが重視される。このため、ロバスト性を改善することができる。<実施の形態2>本実施の形態においては、形状特徴処理部102が生成する検出対象形状の構成特徴テーブルの生成方法について説明する。従来、画像処理の分野で2値画像のスケルトン抽出技術が知られている。形状特徴処理102は、例えば、図2Aの標準テンプレート形状に対し、形状内部を1に、形状外部を0に設定し、2値画像を生成する。形状特徴処理部102は、スケルトン抽出技術より、図7に示すようにスケルトン細線を求めることができる。形状特徴処理102は、スケルトンに存在する交点T1,T2を表1に示す3辺に3点で接する内接円の中心点として設定する。形状特徴処理部102は、内接円の半径を以下のように求める。まず、形状特徴処理部102は、上記2値画像のエッジ点を求める。次に、形状特徴処理部102は、半径rを仮定し、求めたエッジ点で投票を行う。次に、形状特徴処理部102は、上記スケルトン交点T1,T2の位置の得票値を計算する。形状特徴処理部102は、上記得票値とrとの依存関係より、得票値を最大にするrを内接円の半径に設定し、接点の法線方向を求め、表1に示す構成特徴テーブルを生成する。<実施の形態3>本実施の形態においては、形状特徴処理部102は、内接円の特徴だけでなく、形状を構成する1つ以上の直線線分の特徴も生成し、検出対象形状の構成特徴テーブルにそれらを記述する。形状特徴処理部102は、図8Aに示した標準テンプレートの場合、以下の表2Aと表2Bの構成特徴テーブルを生成する。表2Aは表1と同じように内接円の特徴を記述し、表2Bは内接円を共有しないその他の線分の特徴を記述する。形状特徴処理部102は、表2Bに直線線分m1,m2,m3,m4のそれぞれの中点位置P1,P2,P3,P4、中点位置と内接円中心点とを結ぶ線分OP1,OP2,OP3,OP4の図示されない方向、およびそれぞれの長さL1,L2,L3,L4図示されないを記述する。中点位置P1,P2,P3,P4は内接円の中心点Oの座標に対する相対位置で表す。方向α1~α4図示されないは、線分OP1,OP2,OP3,OP4と中心点Oを通る一定方向の直線例えば、画面の走査線とで形成される角度である。表2Aの内接円O,rの特徴を実施の形態1で説明したように検出する。例えば、部分形状検出処理部106は、図8Bの画像形状に対し、内接円の検出より特定形状の線分の組合せl3’,l4’,l5’を検出する。形状形態処理部107は、表2Bの標準テンプレートの組合せl3,l4,l5との相対スケール変化率と相対回転角度を求める。形状認識処理部108は、内接円の位置、相対スケール変化率、相対回転角度、および表2Bの構成特徴テーブルに基づき線分m1,m2,m3,m4に対応する画像エッジが存在するか否かを検証する。具体的に、形状認識処理部108は、各線分の画像におけるべき位置と長さを計算し、そこに存在するエッジ点の数を合計する。形状認識処理部108は、エッジ点の数が指定閾値より大きい場合、線分の存在を認識する。形状認識処理部108は、全ての線分の存在を確認できれば、図8Aに示す形状全体が存在することを検出する。即ち、形状認識処理部108は、他の全ての辺を予測し、予測された他の全ての辺のエッジ点の数を求めることにより他の全ての辺を含む形状を認識する。本実施の形態によれば、検出対象形状に存在する相対的に短い線分、例えば図8Aのm1とm4に対し特に有効である。指定位置に線分が存在するかの検証は高速に実現可能のため、本実施の形態においても特定形状を高速に検出することができる。また、複数線分の組合せを検出するため、エッジ点の強度よりも分布のほうが重視される。このため、ロバスト性を改善することができる。<実施の形態4>本実施の形態においては、検出対象形状に曲線線分が存在した場合の検出する例を説明する。図9Aに標準テンプレートの一例を示す。形状特徴処理部102は、以下の表3Aと表3Bの構成特徴テーブルを生成する。表3Aは表1と同じように内接円の特徴を記述し、表3Bは内接円を共有しない曲線線分の特徴を記述する。形状特徴処理部102は、表3Bに示すように、曲線線分c1をサンプリングするm点の位置を記述する。曲線線分c1上のサンプル点の位置は表3Aの内接円O,rの中心点との相対位置で表す。画像から当該標準テンプレートに対応する形状、例えば、図9Bに示す形状を検出する場合、まず、実施の形態1で説明したように、部分形状検出処理部106は、内接円を共有する特定形状の線分の組合せを検出する。次に、形状形態処理部107は、標準テンプレートとの相対スケールと相対回転を検出する。次に、形状認識処理部108は、内接円の位置、相対スケール変化率、相対回転角度、および構成特徴テーブルに基づき曲線線分に対応する画像エッジが存在するかを検証する。即ち、形状認識処理部108は、設定したサンプル点に対応する画像位置に存在すべきエッジ点の数を合計する。形状認識処理部108は、対応するエッジの存在を確認できれば、図9Aに示す全体形状が存在することを検出する。また、曲線線分が解析式で表す場合、画像から曲線線分に対応する位置を求め、求めた位置に存在するエッジ点を合計してもよい。本実施の形態によれば、指定位置に線分が存在するかの検証は高速に実現可能のため、本実施の形態においても特定形状を高速に検出することができる。また、複数線分の組合せを検出するため、エッジ点の強度よりも分布のほうが重視される。このため、ロバスト性を改善することができる。<実施の形態5>本実施の形態においては、検出対象形状に1つの共有内接円が存在した場合の検出を実現する。この場合、特徴テーブルとして接点の相対法線方向だけを記録するため、標準テンプレートを利用しなくても、特定形状を検出できる。例として、図10Aの三角形を検出する場合、3つの投票方向が存在した上で、相対方向がいずれも180°未満であれば、三角形の存在を検出できる。更に、相対方向がいずれも120°であれば、正三角形が検出される。また、図10Bに示した形状に対し、3つの投票方向が存在し、かつ相対方向がそれぞれ90°、180°、90°であれば、所定の形状が検出される。本実施の形態によれば、複数線分の組合せを検出するため、エッジ点の強度よりも分布のほうが重視される。このため、ロバスト性を改善することができる。以上、実施の形態1から実施の形態5に係る画像処理装置および画像処理方法について説明した。本発明は、画像処理方法を実行可能なコンピュータプログラムにも適用可能である。"