(57)【特許請求の範囲】
【請求項１】
山形曲線記憶手段、入力手段、変換手段、交点算出手段、特徴量算出手段及び出力手段を具備する角度特徴量算出装置で実行される角度特徴量算出方法であって、
前記入力手段が、処理対象となる角度を受け取り、
前記変換手段が、前記角度を、原点を通る直線または原点を通る直線上の点に変換し、
前記交点算出手段が、前記山形曲線記憶手段に記憶された山形またはそれから変換される形状を持つ曲線を読み出して、その読み出した曲線と前記直線との交点を求め、
前記特徴量算出手段が、前記交点の座標値または前記交点と前記原点との間の距離を算出して、その算出した値を前記角度の特徴量として求め、
前記出力手段が、前記特徴量算出手段の求めた角度の特徴量を出力する
ことを特徴とする角度特徴量算出方法。
【請求項２】
山形曲線記憶手段、入力手段、変換手段、交点算出手段、特徴量算出手段及び出力手段を具備する角度特徴量算出装置で実行される角度特徴量算出方法であって、
前記入力手段が、処理対象となる角度を受け取り、
前記変換手段が、前記角度を、原点を通る直線または原点を通る直線上の点に変換し、
前記交点算出手段が、前記山形曲線記憶手段に記憶された山形またはそれから変換される形状を持つ曲線を複数個読み出して、その読み出したそれぞれの曲線と前記直線との交点を求め、
前記特徴量算出手段が、前記複数の交点の座標値または前記複数の交点と前記原点との間の距離を算出して、その算出した値をベクトル要素とする特徴ベクトルを前記角度の特徴量として求め、
前記出力手段が、前記特徴量算出手段の求めた角度の特徴量を出力する
ことを特徴とする角度特徴量算出方法。
【請求項３】
山形曲線記憶手段、入力手段、変換手段、回転手段、交点算出手段、特徴量算出手段及び出力手段を具備する角度特徴量算出装置で実行される角度特徴量算出方法であって、
前記入力手段が、処理対象となる角度を受け取り、
前記変換手段が、前記角度を、原点を通る直線または原点を通る直線上の点に変換し、
前記回転手段が、前記直線を座標変換により回転させることで複数の特徴量算出用直線を生成し、
前記交点算出手段が、前記山形曲線記憶手段に記憶された山形またはそれから変換される形状を持つ曲線を読み出して、その読み出した曲線と前記それぞれの特徴量算出用直線との交点を求め、
前記特徴量算出手段が、前記複数の交点の座標値または前記複数の交点と前記原点との間の距離を算出して、その算出した値をベクトル要素とする特徴ベクトルを前記角度の特徴量として求め、
前記出力手段が、前記特徴量算出手段の求めた角度の特徴量を出力する
ことを特徴とする角度特徴量算出方法。
【請求項４】
多次元空間索引記憶手段、第１の特徴ベクトル算出手段、第２の特徴ベクトル算出手段、検索手段及び出力手段を具備する類似角度検索装置で実行される類似角度検索方法であって、
前記第１の特徴ベクトル算出手段が、請求項１ないし３のいずれか１項に記載の角度特徴量算出方法を使って、データベースに格納される角度の特徴ベクトルを算出し、該特徴ベクトルに対する多次元空間索引を作成して、該多次元空間索引を前記多次元空間索引記憶手段に格納し、
前記第２の特徴ベクトル算出手段が、請求項１ないし３のいずれか１項に記載の角度特徴量算出方法を使って、検索キー角度の特徴ベクトルを算出し、
前記検索手段が、前記多次元空間索引記憶手段に記憶された前記多次元空間索引を使って、前記検索キー角度の特徴ベクトルに類似する特徴ベクトルを持つ角度を検索し、
前記出力手段が、前記検索手段の検索した結果を出力する
ことを特徴とする類似角度検索方法。
【請求項５】
請求項１ないし３のいずれか１項に記載の角度特徴量算出方法の実現に用いられる処理をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項６】
請求項４に記載の類似角度検索方法の実現に用いられる処理をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、角度を正しく、更に人間の感覚にあった形で、更に多次元空間索引にそのまま適用な形で表現する角度特徴量を算出できるようにする角度特徴量算出方法と、その角度特徴量の算出技術を使ってデータベースに格納される角度を検索する類似角度検索方法と、その角度特徴量算出方法の実現に用いられるプログラムを記録したコンピュータ読み取りな記録媒体と、その類似角度検索方法の実現に用いられるプログラムを記録したコンピュータ読み取り可能な記録媒体とに関する。
【０００２】
画像やテキストやＣＧなどのマルチメディア情報の検索や分類を行う場合に、その構成要素となる複数のオブジェクト間の位置関係の類似度を算出することや、構図などに現れる直線情報間の類似度を算出することが必要となる。
【０００３】
このようなことを背景にして、角度の類似性を高精度に表現する技術の構築が叫ばれている。
【０００４】
【従来の技術】
一般に、角度は、原点を通る直線またはその直線上の点として表現することができる。例えば、４５度は、「ｙ＝ｘ」という直線、または、原点と点（１，１）とを通る直線として表現される。
【０００５】
角度という特徴量を表現する方法としては、これまで以下の２種類が用いられてきた。
【０００６】
（１）角度を区分した領域で表現する方法
図１６に、この表現方法の一例を示す。
【０００７】
この図の例では、全方向を８等分し、縦軸・横軸を含めて１２方向の領域に分割する。それぞれの方向領域をＤａ１，Ｄｂ１，Ｄｃ１，Ｄｃ２，Ｄｄ１，Ｄａ２，Ｄａ３，Ｄｂ２，Ｄｃ３，Ｄｃ４，Ｄｄ２，Ｄａ４と呼ぶとするならば、「Ｄａ１〜Ｄａ４」と、「Ｄｂ１〜Ｄｂ２」と、「Ｄｃ１〜Ｄｃ４」と、「Ｄｄ１〜Ｄｄ２」を同一角度と見なして、その４つの角度を１〜４で表すことで角度の特徴量とする。
【０００８】
例えば、点Ｐ１はＤｃ１方向なのでその特徴量は３と表現し、点Ｐ２はＤａ２方向なのでその特徴量は１と表現し、点Ｐ３はＤａ１方向なのでその特徴量は１と表現し、点Ｐ４はＤｂ１方向なのでその特徴量は２と表現し、点Ｐ５はＤｂ１方向なのでその特徴量は２と表現する。
【０００９】
この表現方法は単純である。しかしながら、この表現方法では以下のような問題点が存在する。
【００１０】
すなわち、同一角度領域に入った点に関しては、同一角度なのか、極めて近い角度なのか、若干離れた角度なのかが全く分からない。また、異なる角度領域に入った点に関しても、その異なる度合いを表現できない。また、同一角度領域に入った点よりも異なる角度領域に入った点の方が近い場合が存在する。
【００１１】
例えば、図１６の例で説明するならば、点Ｐ４に対して、点Ｐ１、点Ｐ３、点Ｐ５の近さを表現する場合、点Ｐ１、点Ｐ５、点Ｐ３の順に点Ｐ４に近いというのが正しいのであるが、この表現方法に従うと、点Ｐ４と点Ｐ５とは同一角度で、点Ｐ４と点Ｐ１との間は点Ｐ５と点Ｐ１との間と同じだけ離れており、点Ｐ４と点Ｐ３との間は点Ｐ５と点Ｐ３との間と同じだけ離れているという情報しか得られない。
【００１２】
（２）角度で表現する方法
図１７に、この表現方法の一例を示す。
【００１３】
例えば、角度０となる基軸方向をｘ軸方向と決め、それに対する角度を度やラジアンで表すことで角度の特徴量とする。
【００１４】
この表現方法に従うと、上述の表現方法のような問題点がなくなる代わりに、角度０と角度１８０度の近辺に断面が発生するという問題点がある。
【００１５】
例えば、図１７に示す点Ｐ３が１０度、点Ｐ１が８０度、点Ｐ２が１７０度である場合に、この表現方法に従うと、点Ｐ３と点Ｐ１の類似性は、
ａｂｓ（点Ｐ３の角度−点Ｐ１の角度）＝７０度
但し、ａｂｓ（）は絶対値を示す
で、点Ｐ３と点Ｐ２の類似性は、
ａｂｓ（点Ｐ３の角度−点Ｐ２の角度）＝１６０度
となる。
【００１６】
これから、この表現方法に従うと、点Ｐ３から見て、点Ｐ２の角度よりも点Ｐ１の角度の方が近いという不都合な状態になる。
【００１７】
この問題点を解決するために、基軸を複数用意する方法もある。
【００１８】
例えば、ｘ軸を角度０とすることで求まる特徴量の他に、ｙ軸を角度０とすることで求まる特徴量を求めて、これらの内の小さい方の値を最終的な特徴量とする方法もある。
【００１９】
この方法に従うと、ｘ軸を基軸としたときの点Ｐ３が１０度、点Ｐ１が８０度、点Ｐ２が１７０度である場合に、ｙ軸を基軸としたときの点Ｐ３が１００度、点Ｐ１が１７０度、点Ｐ２が８０度となる。
【００２０】
したがって、点Ｐ３と点Ｐ１の類似性は、
ｍｉｎ〔ａｂｓ（点Ｐ３のｘ基軸での角度−点Ｐ１のｘ基軸での角度），
ａｂｓ（点Ｐ３のｙ基軸での角度−点Ｐ１のｙ基軸での角度）〕
＝ｍｉｎ（７０，７０）＝７０
で、点Ｐ３と点Ｐ２の類似性は、
ｍｉｎ〔ａｂｓ（点Ｐ３のｘ基軸での角度−点Ｐ２のｘ基軸での角度），
ａｂｓ（点Ｐ３のｙ基軸での角度−点Ｐ２のｙ基軸での角度）〕
＝ｍｉｎ（１６０，２０）＝２０
となる。
【００２１】
このように基軸を複数用意する方法に従うと、点Ｐ３から見て、点Ｐ１の角度よりも点Ｐ２の角度の方が近くなる。しかしながら、この表現方法では以下のような問題点が存在する。
【００２２】
すなわち、ｙ軸を基軸とした情報はｘ軸を基軸とした情報から算出できるので、その算出を含めた距離関数を定義することで実現することが可能であるものの、ｍｉｎ演算操作が入ることで、その距離関数がマンハッタン距離やユークリッド距離のような幾何学的距離ではなくなることから多次元空間索引を利用できなくなり、これがために検索が遅くなるという問題点がある。
【００２３】
画像検索で用いられる特徴ベクトルは高次元（ｋ次元）の点データであり、類似検索を高速化するために多次元空間索引が用いられている。
【００２４】
例えば、ｋ−ｄ木の方式に従う多次元空間索引では、ｋ本の座標軸の中から巡回的に座標軸を選択して、その選択した座標軸についての値が大きくなる点群と小さくなる点群の数がほぼ等しくなるようにと点データを分割していくことで多次元空間索引を作成して、検索対象の点データが与えられるときに、その多次元空間索引を辿ることで、その点データに類似する点データの高速検索を実現する。
【００２５】
図１８に、２次元の点データを具体例にして、この多次元空間索引の作成手順を図示する。
【００２６】
上述した基軸を複数用意する方法に従うと、ｍｉｎ演算操作が入ることで距離関数が幾何学的距離ではなくなり、これがために、この多次元空間索引を利用できなくなることで検索が遅くなってしまうのである。
【００２７】
この場合、ｘ軸を基軸とした場合とｙ軸を基軸とした場合とを別々の情報としてデータベース中で管理し、それぞれに索引を適用して、その２つの結果を統合（上述のｍｉｎ演算操作）するという方法を用いることも考えられるが、この方法を用いると、統合操作が入ることで、他の色や形などの特徴量との方式差が発生し、通常の多次元空間索引の結果との統合が難しくなるいう別の問題点が出てくることになる。
【００２８】
更に、人間の感覚として、複数の角度を比較した場合に、多少の直線のずれがあっても同一の角度と感じるが、角度が離れるに従って急激に不一致と感じる度合いが上がるという特性（感覚が比例的でない特性）がある。また、水平線や垂直線に関しては斜め線よりも感度が高く、斜め線では同一と判定できる許容範囲であっても、水平線や垂直線では不一致と感ずるといった特性がある。
【００２９】
類似度の算出時には、これらの感覚を反映させることが望まれる。しかるに、角度で表現するという従来技術の方法((２）の方法）は、類似度を算出する距離関数としては組み込むことが可能であっても、データベース中に格納するデータ分布として、言い換えると、多次元空間索引の対象となる特徴ベクトルとして、角度の離れ具合に応じた感覚を表現することはできない。
【００３０】
【発明が解決しようとする課題】
このように、角度を区分した領域で表現するという従来技術の方法に従うと、正しい類似度を求められないという問題点や、詳細な類似度が得られないという問題点がある。
【００３１】
そして、角度で表現するという従来技術の方法に従うときに、角度の断面をなくす処理を距離関数で実現するようにすると、索引を利用できなくなるという問題点や、これを解決するために、複数の情報に分けて別々の索引を使うようにすると、結果を統合する特殊な処理が必要になるという問題点がある。更に、この従来技術の方法では、人間の感ずる角度の離れ具合をデータとして表現できないという問題点がある。
【００３２】
本発明はかかる事情に鑑みてなされたものであって、角度を正しく表現（つまり類似度の順序が逆転することがない）でき、更に、人間の感覚に合った角度の表現（つまり特定の角度の近辺に強く反応し、角度が離れると急激に類似度が下がるという特徴を表現できる）が可能になり、更に、多次元空間索引にそのまま適用可能（つまり高速な類似検索が可能である）となるという特徴を持つ新たな角度特徴量算出技術の提供と、その角度特徴量算出技術を用いる類似角度検索技術の提供を目的とする。
【００３３】
【課題を解決するための手段】
〔１〕本発明の角度特徴量算出方法の構成
〔１−１〕第１の構成
上記の目的を達成するために、本発明の角度特徴量算出方法は、山形曲線記憶手段、入力手段、変換手段、交点算出手段、特徴量算出手段及び出力手段を具備する角度特徴量算出装置で実行されるときに、（イ）入力手段が、処理対象となる角度を受け取り、（ロ）変換手段が、入力手段の受け取った角度を、原点を通る直線または原点を通る直線上の点に変換し、（ハ）交点算出手段が、山形曲線記憶手段に記憶された山形またはそれから変換される形状を持つ曲線を読み出して、その読み出した曲線と変換手段の変換した直線との交点を求め、（ニ）特徴量算出手段が、交点算出手段の求めた交点の座標値またはその交点と原点との間の距離を算出して、その算出した値を入力手段の受け取った角度の特徴量として求め、（ホ）出力手段が、特徴量算出手段の求めた角度の特徴量を出力するように処理する。
〔１−２〕第２の構成
また、上記の目的を達成するために、本発明の角度特徴量算出方法は、山形曲線記憶手段、入力手段、変換手段、交点算出手段、特徴量算出手段及び出力手段を具備する角度特徴量算出装置で実行されるときに、（イ）入力手段が、処理対象となる角度を受け取り、（ロ）変換手段が、入力手段の受け取った角度を、原点を通る直線または原点を通る直線上の点に変換し、（ハ）交点算出手段が、山形曲線記憶手段に記憶された山形またはそれから変換される形状を持つ曲線を複数個読み出して、その読み出したそれぞれの曲線と変換手段の変換した直線との交点を求め、（ニ）特徴量算出手段が、交点算出手段の求めた複数の交点の座標値またはそれらの交点と原点との間の距離を算出して、その算出した値をベクトル要素とする特徴ベクトルを入力手段の受け取った角度の特徴量として求め、（ホ）出力手段が、特徴量算出手段の求めた角度の特徴量を出力するように処理する。
〔１−３〕第３の構成
また、上記の目的を達成するために、本発明の角度特徴量算出方法は、山形曲線記憶手段、入力手段、変換手段、回転手段、交点算出手段、特徴量算出手段及び出力手段を具備する角度特徴量算出装置で実行されるときに、（イ）入力手段が、処理対象となる角度を受け取り、（ロ）変換手段が、入力手段の受け取った角度を、原点を通る直線または原点を通る直線上の点に変換し、（ハ）回転手段が、変換手段の変換した直線を座標変換により回転させることで複数の特徴量算出用直線を生成し、（ニ）交点算出手段が、山形曲線記憶手段に記憶された山形またはそれから変換される形状を持つ曲線を読み出して、その読み出した曲線と回転手段の生成したそれぞれの特徴量算出用直線との交点を求め、（ホ）特徴量算出手段が、交点算出手段の求めた複数の交点の座標値またはそれらの交点と原点との間の距離を算出して、その算出した値をベクトル要素とする特徴ベクトルを入力手段の受け取った角度の特徴量として求め、（ヘ）出力手段が、特徴量算出手段の求めた角度の特徴量を出力するように処理する。
〔２〕本発明の類似角度検索方法の構成
上記の目的を達成するために、本発明の類似角度検索方法は、多次元空間索引記憶手段、第１の特徴ベクトル算出手段、第２の特徴ベクトル算出手段、検索手段及び出力手段を具備する類似角度検索装置で実行されるときに、（イ）第１の特徴ベクトル算出手段が、本発明の角度特徴量算出方法を使って、データベースに格納される角度の特徴ベクトルを算出し、その特徴ベクトルに対する多次元空間索引を作成して、その作成した多次元空間索引を多次元空間索引記憶手段に格納し、（ロ）第２の特徴ベクトル算出手段が、本発明の角度特徴量算出方法を使って、検索キー角度の特徴ベクトルを算出し、（ハ）検索手段が、多次元空間索引記憶手段に記憶された多次元空間索引を使って、第２の特徴ベクトル算出手段の算出した検索キー角度の特徴ベクトルに類似する特徴ベクトルを持つ角度を検索し、（ニ）出力手段が、検索手段の検索した結果を出力するように処理する。
次に、このように構成される本発明について具体的に説明する。
このように構成される本発明では、処理対象となる角度を、原点を通る直線または原点を通る直線上の点に変換し、山形またはそれから変換される形状を持つ曲線と変換した直線との交点を求め、この交点の座標値またはこの交点と原点との間の距離を角度の特徴量として算出するように処理する。
【００３４】
このとき、曲線を複数の角度に対して用意して、各々の曲線と変換した直線との交点を求め、それらの交点から算出する特徴値をベクトル要素とする特徴ベクトルを角度の特徴量として算出することがある。
【００３５】
また、変換した直線を座標変換により回転させることで複数の特徴量算出用直線を生成して、曲線とこれらの特徴量算出用直線との交点を求め、それらの交点から算出する特徴値をベクトル要素とする特徴ベクトルを角度の特徴量として算出することがある。
【００３６】
このように、本発明では、山形の形状を持つ山形曲線を用意する。
【００３７】
この山形曲線は、非単調な曲線で、角度算出に利用する区間内で、両端に最小点を持つとともに、中央に最大点を持つ形状を有するものであり、座標の拡大縮小、並行移動、回転によって、この山形曲線から変換される曲線（例えば谷形の形状を持つ曲線）も含み、その概形を複数の直線で近似したものも含む。例えば、円、楕円、sin やcos 曲線、２次曲線、正規分布曲線などが山形曲線に該当する。
【００３８】
本発明では、処理対象となる角度が与えられた場合、先ず最初に、その角度を原点を通る直線または原点を通る直線上の点に変換する。
【００３９】
原点（０，０）と点（ａ，ｂ）とを通る直線は、
ｙ＝（ｂ／ａ）ｘ
であり、原点（０，０）を通る傾きθの直線は、
ｙ＝ｘtan θ
であって、点（１，tan θ）を通る。
【００４０】
すなわち、傾きをｍで表現するならば、原点を通る直線は、
ｙ＝ｍｘ
であり、点は（ｘ，ｍｘ）となる。
【００４１】
この公式に従って、処理対象となる角度が与えられた場合、先ず最初に、その角度を原点を通る直線または原点を通る直線上の点に変換する。
【００４２】
続いて、この直線と用意した山形曲線との交点を求める。例えば図１に示すように、処理対象となる角度から変換される点Ｐ１の規定する直線と楕円で定義される山形曲線との交点を求め、また、処理対象となる角度から変換される点Ｐ２の規定する直線と楕円で定義される山形曲線との交点を求め、また、処理対象となる角度から変換される点Ｐ３の規定する直線と楕円で定義される山形曲線との交点を求めるのである。
【００４３】
続いて、この交点の座標値またはこの交点と原点との間の距離を角度の特徴量として算出する。例えば図１に示すように、この交点のｙ座標値を角度の特徴量として算出する。
【００４４】
このようにして算出された角度の特徴量は、点Ｐ３から見て、点Ｐ１の角度よりも点Ｐ２の角度の方が近くなることから分かるように、角度を正しく表現できる。更に、特定の角度の近辺に強く反応し、角度が離れると急激に類似度が下がるという特徴を表現できることで、人間の感覚に合った角度の表現が可能になる。
【００４５】
上述したように、山形曲線には、座標の拡大縮小、並行移動、回転によって山形曲線から変換される曲線も含む。
【００４６】
これから、図２に示すように、座標回転の公式
ｘ’＝ｘcos θ−ｙsin θ
ｙ’＝ｘsin θ＋ｙcos θ
を使って山形曲線を回転させて交点を求め、この交点の座標値またはこの交点と原点との間の距離を角度の特徴量として算出してもよいし、図３に示すように、直線を回転させて交点を求め、この交点の座標値またはこの交点と原点との間の距離を角度の特徴量として算出してもよい。
【００４７】
角度の特徴ベクトルの次元数（基軸の個数）は１つに限られるものでなくて、１以上であればいくつでも構わない。一般的には、縦方向、横方向、斜め上がり方向、斜め下がり方向の４つの方向に対応すればよいが、５つ以上であってもよく、このとき、山形曲線をより尖ったものにして、そのうえで山形曲線を増やすようにすることが好ましい。
【００４８】
角度の特徴ベクトルの次元数を大きくする場合には、図４に示すように、山形曲線を複数の角度に対して用意して、各々の山形曲線と直線との交点を求め、それらの交点から算出する特徴値をベクトル要素とする特徴ベクトルを角度の特徴量として算出したり、図５に示すように、直線を座標変換により回転させることで複数の特徴量算出用直線を生成して、山形曲線とこれらの特徴量算出用直線との交点を求め、それらの交点から算出する特徴値をベクトル要素とする特徴ベクトルを角度の特徴量として算出する。
【００４９】
このようにして算出された角度の特徴ベクトルは、複数の傾きに対して反応する。これから、更に人間の感覚に合った角度の表現が可能になる。
【００５０】
以上に説明した本発明の角度特徴量算出技術により算出される角度特徴量は、幾何学的距離としての性質を持つ。これから、多次元空間索引を利用できる。
【００５１】
したがって、本発明の角度特徴量算出技術を使って、データベースに格納される角度の特徴ベクトルを算出して、それらの特徴ベクトルに対する多次元空間索引を作成し、本発明の角度特徴量算出技術を使って、検索キー角度の特徴ベクトルを算出し、その作成した多次元空間索引を使って、その算出した検索キー角度の特徴ベクトルに類似する特徴ベクトルを持つ角度を検索するという本発明の類似角度検索技術を構築できることで、データベースに格納される角度の中から、検索キー角度に類似する角度を高速に検索できるようになる。
【００５２】
【発明の実施の形態】
以下、実施の形態に従って本発明を詳細に説明する。
【００５３】
図６に、本発明を具備する角度特徴量算出装置１の一実施形態例を図示する。
【００５４】
この実施形態例に従う本発明の角度特徴量算出装置１は、入力装置２から入力される処理対象の角度データを入力する入力部１０と、入力部１０の入力した角度を原点を通る直線または原点を通る直線上の点に変換する変換部１１と、山形曲線を記憶する山形曲線記憶部１２と、変換部１１の変換した直線と山形曲線記憶部１２の記憶する山形曲線とから、入力部１０の入力した角度の特徴量を算出する特徴量算出部１３と、特徴量算出部１３の算出した角度特徴量を記憶する特徴量記憶部１４と、特徴量記憶部１４の記憶する角度特徴量を出力装置３に出力する出力部１５とを備える。
【００５５】
ここで、この角度特徴量算出装置１の持つ機能は具体的にはプログラムで実現されるものであり、このプログラムは、計算機が読み取り可能な可搬媒体メモリや半導体メモリやハードディスクなどの適当な記録媒体に格納することができる。
【００５６】
山形曲線記憶部１２に記憶される山形曲線は、非単調な曲線で、角度算出に利用する区間内で、両端に最小点を持つとともに、中央に最大点を持つ形状を有するものであり、座標の拡大縮小、並行移動、回転によって、この山形曲線から変換される曲線も含み、その概形を複数の直線で近似したものも含む。
【００５７】
図７に、山形曲線記憶部１２に記憶される山形曲線の一実施形態例を図示する。
【００５８】
この図に示すように、山形曲線記憶部１２は、例えば、山形曲線として楕円を用いる場合には、
（ｘ2 ／ａ2 ）＋（ｙ2 ／ｂ2 ）＝１
を記憶し、山形曲線として２次曲線を記憶する場合には、
ｙ＝−ａ（ｘ−１）2 ＋１
を記憶し、山形曲線としてcos 関数を用いる場合には、
ｙ＝cos ｘ
を記憶するのである。
【００５９】
ここで、複数の基軸に対して山形曲線を用意する場合には、それらの山形曲線は異なっていても構わない。例えば、人間の感覚として上下方向や左右方向は斜め方向よりも敏感に反応することから、上下方向や左右方向に用意する楕円のゆがみを、斜め方向に用意する楕円のゆがみよりも大きくするなどしてもよい。
【００６０】
また、一般に角度は点対称であるので、１８０度の範囲で考えればよいが、向きを持つ角度を扱う場合には、これから説明する技術内容を３６０度の範囲に拡張すればよい。すなわち、直線に向きが必要となる場合には、例えば楕円と直線との交点の内、反対側の点を利用すればよい。
【００６１】
図８に、このように構成される本発明の角度特徴量算出装置１の実行する処理フローの一実施形態例を図示する。
【００６２】
次に、この処理フローに従って、このように構成される本発明の角度特徴量算出装置１の実行する角度特徴量の算出処理について詳細に説明する。
【００６３】
このように構成される本発明の角度特徴量算出装置１は、角度特徴量の算出要求があると、図８の処理フローに示すように、先ず最初に、ステップ１で、入力装置２から処理対象の角度データを入力する。
【００６４】
続いて、ステップ２で、その入力した角度を原点を通る直線（または原点を通る直線上の点）に変換する。すなわち、入力した角度の規定する傾きをｍで表現するならば、原点を通る直線は「ｙ＝ｍｘ」であり、その直線上の点は（ｘ，ｍｘ）となるので、この公式に従って、その入力した角度を原点を通る直線（または原点を通る直線上の点）に変換するのである。
【００６５】
続いて、ステップ３で、その変換した直線と山形曲線記憶部１２に記憶される山形曲線との交点を求め、その交点の持つｙ軸値（またはその交点の原点からの距離）を角度特徴量として算出し、続くステップ４で、その算出した角度特徴量を出力して、処理を終了する。
【００６６】
このようにして、山形曲線として楕円を用いる場合には、図１に示したように、処理対象の角度から変換される直線と楕円で定義される山形曲線との交点を求めて、その交点のｙ軸値（またはその交点の原点からの距離）を角度特徴量として算出するのである。
【００６７】
このようにして算出された角度の特徴量は、図１で説明したように、角度を正しく表現でき、更に、特定の角度の近辺に強く反応し、角度が離れると急激に類似度が下がるという特徴を表現できることで、人間の感覚に合った角度の表現が可能になる。
【００６８】
図９に、本発明を具備する角度特徴量算出装置１の他の実施形態例を図示する。
【００６９】
この実施形態例に従う本発明の角度特徴量算出装置１は、図６で説明した入力部１０と、図６で説明した変換部１１と、座標回転の回転行列を記憶する回転行列記憶部１６と、回転行列記憶部１６の記憶する回転行列を使って、変換部１１の変換した直線を回転させることで直線群を生成する直線群生成部１７と、直線群生成部１７の生成した直線群を記憶する直線群記憶部１８と、図６で説明した山形曲線記憶部１２と、直線群記憶部１８の記憶する直線群と山形曲線記憶部１２の記憶する山形曲線とから、入力部１０の入力した角度の特徴量を算出する特徴量算出部１３ａと、特徴量算出部１３ａの算出した角度特徴量を記憶する特徴量記憶部１４と、特徴量記憶部１４の記憶する角度特徴量を出力装置３に出力する出力部１５とを備える。
【００７０】
ここで、この角度特徴量算出装置１の持つ機能は具体的にはプログラムで実現されるものであり、このプログラムは、計算機が読み取り可能な可搬媒体メモリや半導体メモリやハードディスクなどの適当な記録媒体に格納することができる。
【００７１】
図１０に、このように構成される本発明の角度特徴量算出装置１の実行する処理フローの一実施形態例を図示する。
【００７２】
次に、この処理フローに従って、このように構成される本発明の角度特徴量算出装置１の実行する角度特徴量の算出処理について詳細に説明する。
【００７３】
このように構成される本発明の角度特徴量算出装置１は、角度特徴量の算出要求があると、図１０の処理フローに示すように、先ず最初に、ステップ１で、入力装置２から処理対象の角度データを入力する。続いて、ステップ２で、その入力した角度を原点を通る直線（または原点を通る直線上の点）に変換する。
【００７４】
続いて、ステップ３で、回転行列記憶部１６の記憶する回転行列を使って、その変換した直線（または点）を回転させた直線群（または点群）を得る。
【００７５】
例えば、回転行列記憶部１６に記憶される回転行列として、０度回転の回転行列と、４５度回転の回転行列と、９０度回転の回転行列と、１３５度回転の回転行列という４つが用意される場合には、この４つの回転行列を使って、図５に示す角度を表す点Ｐ１（ｘ，ｙ）を回転させることで、
▲１▼０度回転の場合
ｘ’＝ｘ，ｙ’＝ｙ
▲２▼４５度回転の場合
ｘ’＝（２1/2 ／２)(ｘ−ｙ），ｙ’＝（２1/2 ／２)(ｘ＋ｙ）
▲３▼９０度の場合
ｘ’＝−ｙ，ｙ’＝ｘ
▲４▼１３５度回転の場合
ｘ’＝−（２1/2 ／２)(ｘ＋ｙ），ｙ’＝（２1/2 ／２)(ｘ−ｙ）
という４つの点（ｘ’，ｙ’）を得るのである。
【００７６】
このとき各直線の傾きｍ’は、「ｍ’＝ｙ’／ｘ'(但し、ｘ’＝０の場合は例外）」で求められる。
【００７７】
続いて、ステップ４で、ステップ３で得た直線群（または点群）の全ての直線（または点）を選択したのか否かを判断して、全てを選択していないことを判断するときには、ステップ５に進んで、ステップ３で得た直線群（または点群）の中から規定の順番に従って未処理の直線（または原点を通る直線上の点）を１つ選択する。
【００７８】
続いて、ステップ６で、その選択した直線（または原点を通る直線上の点）と山形曲線記憶部１２に記憶される山形曲線との交点を求め、その交点の持つｙ軸値（またはその交点の原点からの距離）を特徴値として算出してから、ステップ４に戻る。
【００７９】
例えば、山形曲線記憶部１２に記憶される山形曲線が楕円である場合には、楕円の式
（ｘ2 ／ａ2 ）＋（ｙ2 ／ｂ2 ）＝１
に、ステップ５で選択した直線の式
ｙ＝ｍ’ｘ
を代入することで交点のｘ軸値を求めるための
（ｘ2 ／ａ2 ）＋（（ｍ’ｘ）2 ／ｂ2 ）＝１
を導出して交点のｘ座標値を求めることで、交点のｘ軸値／ｙ軸値
ｘ＝ａｂ／（ａ2 ｍ'2＋ｂ2 ）1/2 
ｙ＝ａｂｓ（ｍ’ｘ）
を算出し、特徴値として交点のｙ軸値を算出する場合には、このｙ軸値を特徴値として算出するのである。
【００８０】
また、山形曲線記憶部１２に記憶される山形曲線が２次曲線である場合には、２次曲線の式
ｙ＝−ａ（ｘ−１)2＋１
に、ステップ５で選択した直線の式
ｙ＝ｍ’ｘ
を代入することで交点のｘ軸値を求めるための
ａｘ2 −（２ａ−ｍ')ｘ＋（ａ−１）＝０
を導出して交点のｘ座標値を求めることで、交点のｘ軸値／ｙ軸値
ｘ＝[(２ａ−ｍ')＋((２ａ−ｍ')2 −４ａ（ａ−１))1/2 ] ／２ａ
ｙ＝ａｂｓ（ｍ’ｘ）
を算出し、特徴値として交点の原点からの距離を算出する場合には、その距離Ｌ
Ｌ＝（ｘ2 ＋ｙ2 ）1/2 
を算出するのである。
【００８１】
一方、ステップ４で、ステップ３で得た直線群（または点群）の全ての直線（または点）を選択したことを判断するときには、ステップ７に進んで、ステップ６で算出した特徴値をベクトル要素とする特徴ベクトルを作成して、それを最終的な角度特徴量として出力して、処理を終了する。
【００８２】
このようにして、図９に示す実施形態例に従う場合には、図５に示したように、図６の実施形態例で求まる特徴値のヒストグラムで表される特徴ベクトルが最終的な角度の特徴量として算出されることになるのである。
【００８３】
このようにして算出される角度の特徴量は、角度を正しく表現でき、更に、特定の角度の近辺に強く反応し、角度が離れると急激に類似度が下がるという特徴を表現できることで、人間の感覚に合った角度の表現が可能になる。しかも、複数の傾きに対して反応する角度の特徴量を求めることができるようになることで、更に人間の感覚に合った角度の表現が可能になる。
【００８４】
図１１に、本発明を具備する角度特徴量算出装置１の他の実施形態例を図示する。
【００８５】
この実施形態例に従う本発明の角度特徴量算出装置１は、図６で説明した入力部１０と、図６で説明した変換部１１と、図６で説明した山形曲線記憶部１２と、図９で説明した回転行列記憶部１６と、回転行列記憶部１６の記憶する回転行列を使って、山形曲線記憶部１２の記憶する山形曲線を回転させることで山形曲線群を生成する山形曲線群生成部１９と、山形曲線群生成部１９の生成した山形曲線群を記憶する山形曲線群記憶部２０と、変換部１１の変換した直線と山形曲線群記憶部２０の記憶する山形曲線群とから、入力部１０の入力した角度の特徴量を算出する特徴量算出部１３ｂと、特徴量算出部１３ｂの算出した角度特徴量を記憶する特徴量記憶部１４と、特徴量記憶部１４の記憶する角度特徴量を出力装置３に出力する出力部１５とを備える。
【００８６】
ここで、この角度特徴量算出装置１の持つ機能は具体的にはプログラムで実現されるものであり、このプログラムは、計算機が読み取り可能な可搬媒体メモリや半導体メモリやハードディスクなどの適当な記録媒体に格納することができる。
【００８７】
図１２及び図１３に、このように構成される本発明の角度特徴量算出装置１の実行する処理フローの一実施形態例を図示する。
【００８８】
次に、この処理フローに従って、このように構成される本発明の角度特徴量算出装置１の実行する角度特徴量の算出処理について詳細に説明する。
【００８９】
このように構成される本発明の角度特徴量算出装置１は、山形曲線群の生成要求があると、図１２の処理フローに示すように、先ず最初に、ステップ１で、回転行列記憶部１６の記憶する全ての回転行列を選択したのか否かを判断して、選択していないことを判断するときには、ステップ２に進んで、回転行列記憶部１６の記憶する回転行列の中から規定の順番に従って未処理の回転行列を１つ選択する。
【００９０】
続いて、ステップ３で、その選択した回転行列を使って、山形曲線記憶部１２に記憶される山形曲線を回転させることで新たな山形曲線を生成して、それを山形曲線群記憶部２０に格納してから、ステップ１に戻る。
【００９１】
そして、ステップ１で、回転行列記憶部１６の記憶する全ての回転行列を選択したことを判断するときに、処理を終了する。
【００９２】
このようにして、山形曲線群の生成要求があると、回転行列記憶部１６の記憶する回転行列を使って、山形曲線記憶部１２に記憶される山形曲線を回転させることで山形曲線群を生成して、それを山形曲線群記憶部２０に登録するように処理するのである。
【００９３】
一方、このように構成される本発明の角度特徴量算出装置１は、角度特徴量の算出要求があると、図１３の処理フローに示すように、先ず最初に、ステップ１で、入力装置２から処理対象の角度データを入力する。続いて、ステップ２で、その入力した角度を原点を通る直線（または原点を通る直線上の点）に変換する。
【００９４】
続いて、ステップ３で、山形曲線群記憶部２０に記憶される全ての山形曲線を選択したのか否かを判断して、全ての山形曲線を選択していないことを判断するときには、ステップ４に進んで、山形曲線群記憶部２０に記憶される山形曲線群の中から規定の順番に従って未処理の山形曲線を１つ選択する。
【００９５】
続いて、ステップ５で、その選択した山形曲線とステップ２で変換した直線との交点を求め、その交点の持つｙ軸値（またはその交点の原点からの距離）を特徴値として算出してから、ステップ３に戻る。
【００９６】
一方、ステップ３で、山形曲線群記憶部２０に記憶される全ての山形曲線を選択したことを判断するときには、ステップ６に進んで、ステップ５で算出した特徴値をベクトル要素とする特徴ベクトルを作成して、それを最終的な角度特徴量として出力して、処理を終了する。
【００９７】
このようにして、図９の実施形態例では、変換部１１の変換した直線を回転させることで角度の特徴ベクトルを得るのに対して、この図１１に示す実施形態例では、図４に示したように、山形曲線を回転させることで角度の特徴ベクトルを得るように処理するのである。
【００９８】
これから、山形曲線が同一であるならば、図１１の実施形態例で得られる角度の特徴ベクトルは、図９の実施形態例で得られる角度の特徴ベクトルと同じものとなる。
【００９９】
以上に説明した本発明の角度特徴量算出技術により算出される角度の特徴ベクトル（図６の実施形態例で得られる特徴量も１次元の特徴ベクトルと捉えることができる）は、幾何学的距離としての性質を持つ。これから、多次元空間索引を利用できる。
【０１００】
したがって、図１４に示すような本発明を具備する類似角度検索装置３０を構築することが可能になる。
【０１０１】
画像やテキストやＣＧなどのマルチメディア情報の検索や分類を行う場合に、その構成要素となる複数のオブジェクト間の位置関係の類似度を算出することや、構図などに現れる直線情報間の類似度を算出することが必要になる。また、地図上の複数の地点や領域間の位置関係の類似度を算出することが要求されている。
【０１０２】
この本発明の類似角度検索装置３０は、そのような場合に必要とされる類似角度の検索処理を高速に実行することを実現する。
【０１０３】
この実施形態例に従う本発明の類似角度検索装置３０は、データベース３１と、第１の特徴ベクトル算出部３２と、データベース追加管理部３３と、多次元空間索引追加部３４と、第２の特徴ベクトル算出部３５と、データベース検索管理部３６と、類似度計算部３７と、多次元空間索引検索部３８と、類似検索結果出力部３９とを備える。
【０１０４】
このデータベース３１は、上述した本発明の角度特徴量算出技術により算出される角度の特徴ベクトルを、その角度との対応をとりつつ格納する特徴ベクトルＤＢ３１０と、その特徴ベクトルＤＢ３１０に格納される特徴ベクトルの多次元空間索引３１１とを備える。
【０１０５】
第１の特徴ベクトル算出部３２は、データベース３１への登録対象となる角度データが与えられるときに、上述した本発明の角度特徴量算出技術に従って、その角度の特徴ベクトルを算出する。
【０１０６】
データベース追加管理部３３は、第１の特徴ベクトル算出部３２により算出された特徴ベクトルとその算出元となった登録対象の角度との対応関係を特徴ベクトルＤＢ３１０に追加登録する。多次元空間索引追加部３４は、第１の特徴ベクトル算出部３２により算出された特徴ベクトルを多次元空間索引３１１に追加登録する。
【０１０７】
第２の特徴ベクトル算出部３５は、検索キーとなる角度が与えられるときに、上述した本発明の角度特徴量算出技術に従って、その角度の特徴ベクトルを算出する。
【０１０８】
データベース検索管理部３６は、多次元空間索引検索部３８及び類似度計算部３７を制御することで、データベース３１に登録される角度の中から検索キー角度に類似するものを検索する。
【０１０９】
類似度計算部３７は、多次元空間索引検索部３８により検索された特徴ベクトルと第２の特徴ベクトル算出部３５の算出した特徴ベクトルとの類似度を計算する。多次元空間索引検索部３８は、多次元空間索引３１１を辿ることで、第２の特徴ベクトル算出部３５の算出した特徴ベクトルに類似する特徴ベクトルを検索する。
【０１１０】
類似検索結果出力部３９は、データベース検索管理部３６により検索された検索キー角度に類似する角度の情報を出力する。
【０１１１】
ここで、この類似角度検索装置３０の持つ機能は具体的にはプログラムで実現されるものであり、このプログラムは、計算機が読み取り可能な可搬媒体メモリや半導体メモリやハードディスクなどの適当な記録媒体に格納することができる。
【０１１２】
図１５に、このように構成される本発明の類似角度検索装置３０の実行する処理フローの一実施形態例を図示する。
【０１１３】
次に、この処理フローに従って、このように構成される本発明の類似角度検索装置３０の実行する角度特徴量の算出処理について詳細に説明する。
【０１１４】
このように構成される本発明の類似角度検索装置３０は、角度（特徴ベクトル）の登録要求があると、図１５（ａ）の処理フローに示すように、先ず最初に、ステップ１で、登録対象の角度データを入力する。続いて、ステップ２で、上述した本発明の角度特徴量算出技術を使って、その入力した角度の特徴ベクトルを算出する。
【０１１５】
続いて、ステップ３で、その算出した角度の特徴ベクトルを、その角度との対応をとりつつ特徴ベクトルＤＢ３１０に追加登録する。続いて、ステップ４で、多次元空間索引３１１を辿ることで、その算出した特徴ベクトルのリーフ位置を求めて追加することで、多次元空間索引３１１にその算出した特徴ベクトルを追加登録して、処理を終了する。
【０１１６】
一方、このように構成される本発明の類似角度検索装置３０は、角度の検索要求が発行されると、図１５（ｂ）の処理フローに示すように、先ず最初に、ステップ１で、検索キーの角度データを入力する。続いて、ステップ２で、上述した本発明の角度特徴量算出技術を使って、入力した検索キー角度の特徴ベクトルを算出する。
【０１１７】
続いて、ステップ３で、多次元空間索引３１１を辿って、その算出した特徴ベクトルに近い複数の特徴ベクトルを検索することで、特徴ベクトルＤＢ３１０に登録されている角度の中から、検索キー角度に類似する複数の角度を検索する。
【０１１８】
続いて、ステップ４で、その検索した特徴ベクトルと、ステップ２で算出した検索キー角度の特徴ベクトルとの間の類似度を計算することで、検索キー角度とステップ３で検索した角度との間の類似度を計算して、それに従って、ステップ３で検索した角度を類似度の高い順にソートする。続いて、ステップ５で、そのソートした角度を検索結果として出力して、処理を終了する。
【０１１９】
このようにして、本発明の類似角度検索装置３０は、本発明の角度特徴量算出技術により算出される角度の特徴ベクトルを利用し、多次元空間索引による高速検索を実現しつつ、検索キーの角度に類似する角度を高精度で検索するように処理するのである。
【０１２０】
以上に説明した本発明により算出される角度の特徴量は、次のような類似検索や検索結果の構造化やクラスリングや自己組織化のための特徴量として応用できる。すなわち、画像内直線の傾きや、画像内オブジェクト間の傾きや、ＧＩＳ（地理情報システムや電子地図）上の地点や領域間の方位などのための特徴量として応用できる。
【０１２１】
そして、本発明により算出される角度の特徴量は、基準方向を３次元に配置することで、３Ｄ空間内物体やＣＧ間の角度や方向にも適用できる。その他、方位や方向や角度を使ったインターネットサービスでも容易に利用できる。
【０１２２】
【発明の効果】
以上説明したように、本発明によれば、特定の傾きに対して反応する特徴量を求めることができるようになる。また、その場合に、特定の傾きからの角度の離れ具合による類似の度合いも調整が可能である。これから、人間の感覚に合った角度特徴量を表現することが可能になる。
【０１２３】
そして、本発明によれば、複数の傾きに対して反応する特徴量を求めることが可能になる。例えば、山形曲線を縦長の楕円にすると、垂直方向に敏感な特徴量となり、山形曲線を横長の楕円にすると、水平方向に敏感な特徴量となり、山形曲線を４５度の楕円にすると、４５度の方向に敏感な特徴量となる。これから、これらをベクトル要素とする特徴ベクトルを作ることで、更に人間の感覚に合った角度特徴量を表現することが可能になる。
【０１２４】
そして、本発明で算出される角度の特徴量は角度の傾きをデータ分布として表現することを可能にすることから、本発明によれば、多次元空間索引を適用することができることで高速な類似検索が可能になる。
【図面の簡単な説明】
【図１】本発明の説明図である。
【図２】本発明の説明図である。
【図３】本発明の説明図である。
【図４】本発明の説明図である。
【図５】本発明の説明図である。
【図６】本発明の角度特徴量算出装置の一実施形態例である。
【図７】山形曲線の一実施形態例である。
【図８】本発明の角度特徴量算出装置の実行する処理フローの一実施形態例である。
【図９】本発明の角度特徴量算出装置の他の実施形態例である。
【図１０】本発明の角度特徴量算出装置の実行する処理フローの一実施形態例である。
【図１１】本発明の角度特徴量算出装置の他の実施形態例である。
【図１２】本発明の角度特徴量算出装置の実行する処理フローの一実施形態例である。
【図１３】本発明の角度特徴量算出装置の実行する処理フローの一実施形態例である。
【図１４】本発明の類似角度検索装置の一実施形態例である。
【図１５】本発明の類似角度検索装置の実行する処理フローの一実施形態例である。
【図１６】従来技術の説明図である。
【図１７】従来技術の説明図である。
【図１８】多次元空間索引の説明図である。
【符号の説明】
１    角度特徴量算出装置
２    入力装置
３    出力装置
１０  入力部
１１  変換部
１２  山形曲線記憶部
１３  特徴量算出部
１４  特徴量記憶部
１５  出力部
【図１】
0003732717.tif 000002
【図２】
0003732717.tif 000003
【図３】
0003732717.tif 000004
【図４】
0003732717.tif 000005
【図５】
0003732717.tif 000006
【図６】
0003732717.tif 000007
【図７】
0003732717.tif 000008
【図８】
0003732717.tif 000009
【図９】
0003732717.tif 000010
【図１０】
0003732717.tif 000011
【図１１】
0003732717.tif 000012
【図１２】
0003732717.tif 000013
【図１３】
0003732717.tif 000014
【図１４】
0003732717.tif 000015
【図１５】
0003732717.tif 000016
【図１６】
0003732717.tif 000017
【図１７】
0003732717.tif 000018
【図１８】
0003732717.tif 000019