(57)【要約】【課題】２次元空間における対象物の傾き角度の近似値をより速く計算することを可能にした情報処理方法を提供する。【解決手段】２次元空間上に基準方向をｘ軸とするｘｙ座標を設定し、Ｎを自然数とし、ｘｙ座標の原点を端点とし、それぞれｘ軸からの角度に対応づけられた、異なる傾きＡ(ｋ)（ｋは０≦ｋ≦Ｎ−１を満たす整数）を有するＮ個の半直線を境界とするＮ個の分割領域に２次元空間を分割し、線分の一方の端点が原点に一致するように線分を平行移動したときの線分の他方の端点の座標（ｘｉ，ｙｉ）を特定し、ｋを０から（Ｎ−１）まで１ずつ増加させながら、ｙｉとｘｉ×Ａ(ｋ)との大小関係を判定することにより、座標（ｘｉ，ｙｉ）の端点が属する分割領域を求め、求めた分割領域に対応付けられた角度を線分の角度とするものである。【選択図】図４
2013037482.tif 000002
【特許請求の範囲】
【請求項１】
２次元空間上に与えられた線分が基準方向と成す角度を求めるための情報処理方法であって、
前記２次元空間上に前記基準方向をｘ軸とするｘｙ座標を設定し、
Ｎを自然数とし、前記ｘｙ座標の原点を端点とし、それぞれｘ軸からの角度に対応づけられた、異なる傾きＡ(ｋ)（ｋは０≦ｋ≦Ｎ−１を満たす整数）を有するＮ個の半直線を境界とするＮ個の分割領域に前記２次元空間を分割し、
前記線分の一方の端点が前記原点に一致するように該線分を平行移動したときの前記線分の他方の端点の座標（ｘｉ，ｙｉ）を特定し、
前記ｋを０から（Ｎ−１）まで１ずつ増加させながら、ｙｉとｘｉ×Ａ(ｋ)との大小関係を判定することにより、前記座標（ｘｉ，ｙｉ）の端点が属する分割領域を求め、
求めた分割領域に対応付けられた角度を前記線分の角度とする、情報処理方法。
【請求項２】
請求項１記載の情報処理方法において、
前記座標（ｘｉ，ｙｉ）を特定した後、ｘｉ及びｙｉの正負の符号を記憶し、該ｘｉ及びｙｉの絶対値として｜ｘｉ｜及び｜ｙｉ｜を算出し、
前記ｋを０から（Ｎ−１）まで１ずつ増加させながら、ｙｉとｘｉ×Ａ(ｋ)との大小関係を判定する際、｜ｙｉ｜と｜ｘｉ｜×Ａ（ｋ）の大小判定を行い、｜ｙｉ｜が｜ｘｉ｜×Ａ（ｋ）より小さくなるｋを求め、求めたｋと前記ｘｉ及びｙｉについて記憶した正負の符号とに基づいて、前記座標（ｘｉ，ｙｉ）の端点が属する分割領域を求める、情報処理方法。
【請求項３】
請求項１または２記載の情報処理方法において、
前記Ｎが４の倍数である場合、前記Ｎ個に前記２次元空間を分割する際、該２次元空間を均等に、かつ原点対称に分割する、情報処理方法。
【請求項４】
請求項１から３のいずれか１項記載の情報処理方法において、
前記大小関係の判定を行う際に三項演算子を用いる、情報処理方法。
【請求項５】
２次元空間上に与えられた線分が基準方向と成す角度を求める情報処理装置であって、
Ｎを自然数としたとき、前記２次元空間上に前記基準方向をｘ軸とするｘｙ座標が設定され、前記２次元空間が、前記ｘｙ座標の原点を端点とし、それぞれｘ軸からの角度に対応づけられた、異なる傾きＡ(ｋ)（ｋは０≦ｋ≦Ｎ−１を満たす整数）のＮ個の半直線でＮ個の分割領域に分割された場合の、前記ｋが０から（Ｎ−１）までのそれぞれの前記Ａ(ｋ)の値を記憶する記憶手段と、
前記線分の一方の端点が該座標の原点に一致するように該線分を平行移動させたときの、該線分の他方の端点の座標（ｘｉ，ｙｉ）を特定する座標変換手段と、
前記ｋを０から（Ｎ−１）まで１ずつ増加させながら、ｙｉとｘｉ×Ａ(ｋ)との大小関係を判定することにより、前記座標（ｘｉ，ｙｉ）の端点が属する分割領域を求め、該分割領域に対応付けられた角度を前記線分の角度とする判定手段と、
を有する情報処理装置。
【請求項６】
請求項５記載の情報処理装置において、
前記座標変換手段が座標（ｘｉ，ｙｉ）を特定した後、ｘｉ及びｙｉの正負の符号を前記記憶手段に格納し、該ｘｉ及びｙｉの絶対値として｜ｘｉ｜及び｜ｙｉ｜を算出する象限変換手段をさらに有し、
前記判定手段は、前記ｋを０から（Ｎ−１）まで１ずつ増加させながら、ｙｉとｘｉ×Ａ(ｋ)との大小関係を判定する際、｜ｙｉ｜と｜ｘｉ｜×Ａ（ｋ）の大小判定を行い、｜ｙｉ｜が｜ｘｉ｜×Ａ（ｋ）より小さくなるｋを求め、該ｋと前記ｘｉ及びｙｉについて前記記憶手段に格納された正負の符号とに基づいて、前記座標（ｘｉ，ｙｉ）の端点が属する分割領域を求める、情報処理装置。
【請求項７】
請求項５または６に記載の情報処理装置をコンピュータに実現させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２次元空間において、線分と基準方向との成す角度を計算するための情報処理方法、情報処理装置、及びその装置をコンピュータに実現させるためのプログラムに関する。
【背景技術】
【０００２】
画像検出処理等の分野では、ディジタル画像内に現わされた対象物（例えば、人物や車などの被写体）が画像内でどの程度傾いているか、言い換えれば、対象物が基準方向（例えば、画像水平方向）との成す角度がどの程度かを計算したい場合がある。こうした場合、対象物に対応する画像領域内から適当な２点を選び、この２点を結ぶ線分と基準方向とが成す角度を求めることになる。以下に、角度計算方法の一例を説明する。
【０００３】
ディジタル画像を２次元空間とみなし、画像領域の中心に原点をとり、その原点から画面水平方向にｘ軸、画面鉛直方向にｙ軸をとるものとする。
【０００４】
図１に示すように、ディジタル画像５内に現わされた対象物の領域から適当な２点(x1,y1)及び(x2,y2)を選んだとき、この２点を結ぶ線分がｘ軸と成す角度angleは、逆正接関数により、
angle = atan2(x2-x1,y2-y1) = atan((y2-y1)/(x2-x1))                （式１）
で計算できる（比例定数を１としている）。ただし、angleは、ラジアン単位で表された角度とする。
【０００５】
通常、関数atan2(x,y)は近似多項式による繰り返し演算で計算される。例えば、
atan2(x,y) = atan(y/x) = (y/x) + (1/3)*(y/x)^3 + … + 1/(2*i+1)*(y/x)^(2*i+1) + …      （式２）
といったものが挙げられる。近似多項式を用いることにより、原理的には任意の精度で角度を計算できる。
【０００６】
一般のプログラム言語（例えば、Ｃ言語）においては、単精度や倍精度の角度が計算できる組込関数ライブラリが用意されている。
【０００７】
特許文献１には、角度計算方法の一例が開示されている。特許文献１の発明では、X及びYの２値を入力とし、その逆正接値argtan(Y/X)をテーブルを参照して求める方法において、テーブル量の圧縮を図ることにより角度計算方法を高速に行うことを可能にしている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平１１−２５１８４１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
特許文献１に開示された発明は、２つの入力値の絶対値の商|Y|/|X|をテーブルで検索する方法であるため、入力値X及びYの精度が増すと、これに伴ってテーブルのエントリ数も増大する欠点がある。入力値の精度が単精度ほどであっても、エントリ数は極めて大きなものとなる。
【００１０】
一方、ディジタル画像の解析結果を応用する際、正確な角度を必要とせず、おおまかな角度値を高速に計算したい場合がある。例えば、全方位を２π[ラジアン]として、これを複数に分割し、求める角度が複数の分割領域のうち、どの分割領域に含まれるかさえわかればよい、すなわち、角度の量子化値さえわかればよい、といった場合である。
【００１１】
式２に示したような近似多項式による計算方法は、概して計算コストが高く、多くの処理時間を要するため、精度が高くても、角度を速く求めたいという要求には応えられないことがある。
【００１２】
本発明は上述したような技術が有する問題点を解決するためになされたものであり、２次元空間における対象物の傾き角度の近似値をより速く計算することを可能にした情報処理方法、情報処理装置、及びその装置をコンピュータに実現させるためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するための本発明の情報処理方法は、２次元空間上に与えられた線分が基準方向と成す角度を求めるための情報処理方法であって、
前記２次元空間上に前記基準方向をｘ軸とするｘｙ座標を設定し、
Ｎを自然数とし、前記ｘｙ座標の原点を端点とし、それぞれｘ軸からの角度に対応づけられた、異なる傾きＡ(ｋ)（ｋは０≦ｋ≦Ｎ−１を満たす整数）を有するＮ個の半直線を境界とするＮ個の分割領域に前記２次元空間を分割し、
前記線分の一方の端点が前記原点に一致するように該線分を平行移動したときの前記線分の他方の端点の座標（ｘｉ，ｙｉ）を特定し、
前記ｋを０から（Ｎ−１）まで１ずつ増加させながら、ｙｉとｘｉ×Ａ(ｋ)との大小関係を判定することにより、前記座標（ｘｉ，ｙｉ）の端点が属する分割領域を求め、
求めた分割領域に対応付けられた角度を前記線分の角度とするものである。
【００１４】
また、本発明の情報処理装置は、２次元空間上に与えられた線分が基準方向と成す角度を求める情報処理装置であって、
Ｎを自然数としたとき、前記２次元空間上に前記基準方向をｘ軸とするｘｙ座標が設定され、前記２次元空間が、前記ｘｙ座標の原点を端点とし、それぞれｘ軸からの角度に対応づけられた、異なる傾きＡ(ｋ)（ｋは０≦ｋ≦Ｎ−１を満たす整数）のＮ個の半直線でＮ個の分割領域に分割された場合の、前記ｋが０から（Ｎ−１）までのそれぞれの前記Ａ(ｋ)の値を記憶する記憶手段と、
前記線分の一方の端点が該座標の原点に一致するように該線分を平行移動させたときの、該線分の他方の端点の座標（ｘｉ，ｙｉ）を特定する座標変換手段と、
前記ｋを０から（Ｎ−１）まで１ずつ増加させながら、ｙｉとｘｉ×Ａ(ｋ)との大小関係を判定することにより、前記座標（ｘｉ，ｙｉ）の端点が属する分割領域を求め、該分割領域に対応付けられた角度を前記線分の角度とする判定手段と、
を有する構成である。
【００１５】
さらに、本発明のプログラムは、上記本発明の情報処理装置をコンピュータに実現させるものである。
【発明の効果】
【００１６】
本発明によれば、近似多項式を用いる逆正接関数で算出する場合に比べて、角度を速く算出することができる。
【図面の簡単な説明】
【００１７】
【図１】角度算出対象となる線分をｘｙ座標に表した図である。
【図２】角度算出対象となる線分の座標変換を示す図である。
【図３】原点を中心に全方位をＮ分割したときの一例を示す図である。
【図４】本発明の基本原理による角度計算方法を説明するための図である。
【図５】座標変換後の線分が第１象限にある場合の計算方法を示す図である。
【図６】座標変換後の線分が第２象限にある場合の計算方法を示す図である。
【図７】座標変換後の線分が第３象限にある場合の計算方法を示す図である。
【図８】座標変換後の線分が第４象限にある場合の計算方法を示す図である。
【図９】原点を中心に全方位を均等、かつ原点対称に分割したときの一例を示す図である。
【図１０】第２象限の線分を第１象限に対応させて計算する方法を示す図である。
【図１１】第３象限の線分を第１象限に対応させて計算する方法を示す図である。
【図１２】第４象限の線分を第１象限に対応させて計算する方法を示す図である。
【図１３】第１の実施形態の情報処理装置の一構成例を示すブロック図である。
【図１４】図１３に示す演算手段の一構成例を示すブロック図である。
【図１５】第１の実施形態の情報処理方法を示すフローチャートである。
【図１６】第２の実施形態における演算手段の一構成例を示すブロック図である。
【図１７】実施例１による角度算出方法と組込関数を用いた方法のそれぞれの処理時間を示すグラフである。
【発明を実施するための形態】
【００１８】
本発明の一実施形態における角度計算方法の基本原理について説明する。
【００１９】
（１）基本原理
図１に示すように、ディジタル画像５を２次元空間とみなし、画像領域の中心に原点をとり、その原点から画像水平方向にｘ軸、画像鉛直方向にｙ軸をとることとする。計算したいのは、画像領域中の２点(x1,y1)及び(x2,y2)を結ぶ線分がｘ軸と成す角度である。
この角度を求める問題は、線分の２点の端点のうち、一方が原点に一致するように平行移動しても明らかに等価なので、図２に示すように、原点と座標(xi,yi)を結ぶ線分がｘ軸と成す角度を求める方法に置き換えることにする。ここで、xiはx2-x1であり、yiはy2-y1である。
そして、角度の計算に要求される精度は、Ｎを自然数とすると、全方位２π[ラジアン]のＮ分の１程度で十分であるものとする。つまり、全方位をＮ分割したとき、求める角度がどの分割領域に含まれるのかがわかればよいこととする。
ここで、全方位の分割は、ｋを０から（Ｎ−１）までの整数とするとき、図３に示すように、原点を始点とする傾きＡ（ｋ）の半直線により、ｋ番目の分割領域と（ｋ＋１）番目の分割領域が区切られる形でなされているものとする。ｋは分割領域に対応する番号であり、以下では、この番号を分割番号と称する。
係数Ａ（ｋ）は、例えば、
A(k) = tan((k+1)*2π/N)    （k = 0,1,2,…,N-1）         （式３）
といった形で与えられる。
以下、点(xi,yi)の座標xi,yiの符号について、４つの象限で場合分けして考える。
【００２０】
（１．１）点(xi,yi)が第１象限（xi>=0でかつyi>=0）にある場合
図４に示す場合で、原点と点(xi,yi)を結ぶ線分とｘ軸とが成す角度を求めてみる。図４を参照すると、原点と点(xi,yi)を結ぶ線分がｋ番目の分割領域に含まれるならば、点(xi,yi)がｋ番目の分割領域と（ｋ＋１）番目の分割領域との境界線
y = A(k)*x          （式４）
より下に位置することになる。
したがって、
xi*A(k) > yi        （式５）
が成立するならば、求める角度を示す線分はｋ番目の分割領域に含まれる。
ここで、ｋ番目と（ｋ＋１）番目の分割領域の境界線（以下では、分割境界線と称する）上に点(xi,yi)がある場合には、求める角度を示す線分は（ｋ＋１）番目の分割領域に含まれるものとする。
また、（ｋ＋１）番目よりｙ軸方向上方にある分割境界線について、式５と同様の式
xi*A(k+1) > yi        （式６）
が成立することは明らかである。このことを図５に示す。
したがって、ｘ軸に近い分割境界線から順に、その係数Ａ（ｋ）をもって
xi*A(k) > yi        （式７）
を計算し、式７が成立する最初の分割領域を見つければ、それが求める角度を示す線分の端点(xi,yi)が属する分割領域であることになる。
つまり、kの値を0から1ずつ増加させながら、式７を判定することで、式７が成立したときのkの値を知ることができ、ｋの値がわかれば、これに対応する分割領域がどれであるかもわかる。
いま、求めるべき分割領域に付された分割番号がｍだったとすると、式７が成立したときのｋの値が求めるべきｍであるということになる。
各分割には、代表的な角度値が定められているものとすれば、分割番号ｍを知ることにより、求めるべき角度の量子化値を得ることができる。
例えば、各分割についてその分割を代表する角度値、例えば、分割が均等である場合ならば、
angleQ(k) = tan((k+1/2)*2π/N)      （式８）
を予め計算機の記憶装置に保存しておき、分割番号ｍをインデクスとして参照すればよい。
式７の計算には、除算のようなコストの大きい演算を必要としないため、高速に処理できる。
【００２１】
（１．２）点(xi,yi)が第２象限（xi<0でかつyi>=0）にある場合
この第２象限では、第１象限の場合と異なり、図６に示すように、ｋ番目の分割領域が（ｋ＋１）番目の分割領域よりもｙ軸方向上方に位置することになる。そこで、角度の分割番号ｍを計算する手順で判定した不等式は、次の形にする必要がある。
xi*A(k) < yi        （式９）
この式は次のように変形できる。
-|xi|*A(k) < yi  ⇒  |xi|*A(k) > yi      （式１０）
つまり、xiについてその絶対値|xi|をとることで、第１象限の場合と同じ不等式を用いて、分割番号ｍを得ることができる。
【００２２】
（１．３）点(xi,yi)が第３象限（xi<0でかつyi<0）にある場合
この第３象限でも、図７に示すように、ｋ番目の分割領域は（ｋ＋１）番目の分割領域よりもｙ軸方向上方に位置することになる。そこで、角度の分割番号ｍを計算する手順で判定した不等式は、式９の形にする必要がある。
xiとyiが負であることから、式９は次のように変形できる。
-|xi|*A(k) < -|yi|  ⇒  |xi|*A(k) > |yi|      （式１１）
つまり、xi及びyiについてそれぞれの絶対値|xi|及び|yi|をとることで、第１の象限の場合と同じ不等式を用いて、分割番号ｍを求めることができる。
【００２３】
（１．４）点(xi,yi)が第４象限（xi>=0でかつyi<0）にある場合
この第４象限では、第１象限の場合と同様に、図８に示すように、ｋ番目の分割領域が（ｋ＋１）番目の分割領域よりもｙ軸方向下方に位置する。したがって、第１象限の場合で説明した（１．１）と同じ手順で、分割番号ｍを求めることができる。
【００２４】
（２）全方位の分割に均等性や対称性がある場合
全方位をＮ分割する方法はさまざまだが、均等かつ原点対称な分割が最も実用的である場合が多い。そこで、分割境界線の係数Ａ（ｋ）が、式３の代わりに
A(k) = tan((k+1)*2π/N)    （k = 0,1,2,…,N-1）       （式１２）
で与えられる均等分割であって、Ｎが４の倍数である場合を考える。
この場合、全方位はｘ軸及びｙ軸について対称に分割されている。
分割番号は、
・第１象限（xi>=0でかつyi>=0）は、分割番号０番から（Ｎ／４−１）番まで
・第２象限（xi< 0でかつyi>=0）は、分割番号（Ｎ／４）番から（Ｎ／２−１）番まで
・第３象限（xi< 0でかつyi< 0）は、分割番号（Ｎ／２）番から（３Ｎ／４−１）番まで
・第４象限（xi>=0でかつyi< 0）は、分割番号（３Ｎ／４）番から（Ｎ−１）番まで
というように割り振られている。この割り振りを図９に示す。
この性質を利用することにより、「（１）基本原理」で説明したような、象限毎の場合分けによる計算が不要となる。
【００２５】
（２．１）点(xi,yi)が第１象限（xi>=0でかつyi>=0）にある場合
この場合、（１．１）で説明した手順と同様に、分割番号ｍが求められる。
【００２６】
（２．２）点(xi,yi)が第２象限（xi<0でかつyi>=0）にある場合
この第２象限で分割番号を求める問題は、点（xi,yi）のx座標を符号反転することにより、図１０（ａ）に示すように、第１象限における点(|xi|,yi)についての問題に帰着できる。ただし、第２象限をｙ軸で折り返して第１象限に重ね合わせる形になるため、第１象限で求めた分割番号ｍを
m  → N/2-1 - m
として、第２象限の分割番号に対応させる必要がある。第２象限と第１象限の分割番号の対応づけを図１０（ｂ）に示す。
【００２７】
（２．３）点(xi,yi)が第３象限（xi<0でかつyi<0）にある場合
この第３象限で分割番号を求める問題は、点（xi,yi）のx座標及びy座標を符号反転することにより、図１１（ａ）に示すように、第１象限における点（|xi|,|yi|）についての問題に帰着できる。ただし、第３象限をｙ軸で折り返し、さらにｘ軸で折り返して第１象限に重ね合わせる形になるため、第１象限で求めた分割番号ｍを
m  →  N-1-(N/2-1-m)  =  N/2 + m
として、第３象限の分割番号に対応させる必要がある。第３象限と第１象限の分割番号の対応づけを図１１（ｂ）に示す。
【００２８】
（２．４）点(xi,yi)が第４象限（xi>=0でかつyi<0)にある場合
この第４象限で分割番号を求める問題は、点（xi,yi）のy座標を符号反転することにより、図１２（ａ）に示すように、第１象限における点（xi,|yi|）についての問題に帰着できる。ただし、第４象限をｘ軸で折り返して第１象限に重ね合わせる形になるため、第１象限で求めた分割番号ｍを
m  →  N-1 - m
として、第４象限の分割番号に対応させる必要がある。第４象限と第１象限の分割番号の対応づけを図１２（ｂ）に示す。
【００２９】
以上のように、分割が均等かつ原点対称に行われる場合には、第１象限での解法のみを用いて角度が計算できる。その結果、得られた分割番号ｍを点(xi,yi)が属する象限に応じて読み替えるだけで足りる。
以下に、上述した角度計算方法を実行するための情報処理装置の実施形態を説明する。
【００３０】
（第１の実施形態）
本実施形態の情報処理装置の構成を説明する。
【００３１】
図１３は本実施形態の情報処理装置の一構成例を示すブロック図である。図１４は図１３に示す演算手段の一構成例を示すブロック図である。
【００３２】
図１３に示すように、本実施形態の情報処理装置１０は、演算手段１１と、記憶手段１２を有する。演算手段１１は、プログラムを記憶するメモリ１４と、プログラムにしたがって処理を実行するＣＰＵ（Central Processing Unit）１３とを有する。
【００３３】
図１４に示すように、演算手段１１は、空間分割手段５１と、座標変換手段５２と、象限変換手段５３と、判定手段５４とを有する。ＣＰＵ１３がプログラムを実行することで、空間分割手段５１、座標変換手段５２、象限変換手段５３、及び判定手段５４が情報処理装置１０に仮想的に構成される。
【００３４】
記憶手段１２は、分割番号に対応して角度を算出するための式８を予め記憶している。空間分割手段５１は、角度算出対象となる線分が表示されたディジタル画像に２次元空間としてｘｙ座標を設定し、ｘ軸を基準方向に定義し、ｘｙ座標の原点を中心にした全方位をＮ個に分割し、隣り合う分割領域間の境界線となるＮ個の半直線の傾きの値をテーブルとして記憶手段１２に格納する。境界線となるＮ個の半直線は、「（１）基本原理」で説明したように、ｘｙ座標の原点を端点とし、それぞれｘ軸からの角度に対応づけられ、傾きＡ(ｋ)（ｋは０≦ｋ≦Ｎ−１を満たす整数）が互いに異なっている。
【００３５】
座標変換手段５２は、角度算出対象となる線分の一方の端点がｘｙ座標の原点に一致するように平行移動させたときのその線分の他方の端点の座標（ｘｉ，ｙｉ）を特定する。象限変換手段５３は、座標変換後の（ｘｉ，ｙｉ）について、ｘｉ及びｙｉの正負の符号を記憶手段１２に格納し、ｘｉ及びｙｉの絶対値として｜ｘｉ｜及び｜ｙｉ｜を算出する。
【００３６】
判定手段５４は、座標変換手段５２が座標（ｘｉ，ｙｉ）を特定すると、ｋを０から（Ｎ−１）まで１ずつ増加させながら、ｙｉとｘｉ×Ａ(ｋ)との大小関係を判定することにより、座標（ｘｉ，ｙｉ）の端点が属する分割領域を求め、求めた分割領域に対応付けられた角度を線分の角度とする。また、判定手段５４は、象限変換手段５３が座標（ｘｉ，ｙｉ）について｜ｘｉ｜及び｜ｙｉ｜を算出すると、ｋを０から（Ｎ−１）まで１ずつ増加させながら、｜ｙｉ｜と｜ｘｉ｜×Ａ（ｋ）の大小判定を行い、｜ｙｉ｜が｜ｘｉ｜×Ａ（ｋ）より小さくなるｋを求め、求めたｋとｘｉ及びｙｉの正負の符号とに基づいて、座標（ｘｉ，ｙｉ）の端点が属する分割領域を求める。さらに、判定手段５４は、求めた分割領域のｋの値を記憶手段１２の式８に代入することで、角度を算出する。
【００３７】
次に、本実施形態の情報処理装置が実行する、角度算出のための情報処理方法を説明する。図１５は本実施形態における、角度算出のための情報処理手順を示すフローチャートである。
【００３８】
空間分割手段５１は、角度算出対象となる線分が表示されたディジタル画像に２次元空間としてｘｙ座標を設定し、ｘ軸を基準方向に設定する（ステップ１０１）。続いて、空間分割手段５１は、ｘｙ座標の原点を端点とし、それぞれｘ軸からの角度に対応づけられた、異なる傾きＡ(ｋ)（ｋは０≦ｋ≦Ｎ−１を満たす整数）を有するＮ個の半直線を境界とするＮ個の分割領域に２次元空間を分割する（ステップ１０２）。さらに、空間分割手段５１は、各傾きＡ（ｋ）を記憶手段１２に格納する。
【００３９】
座標変換手段５２は、角度計算対称の線分の一方の端点がｘｙ座標の原点に一致するようにその線分を平行移動させたときの線分の他方の端点の座標（ｘｉ，ｙｉ）を特定する（ステップ１０３）。判定手段５４は、ｋを０から（Ｎ−１）まで１ずつ増加させながら、ｙｉとｘｉ×Ａ(ｋ)との大小関係を判定することにより、座標（ｘｉ，ｙｉ）の端点が属する分割領域を求める（ステップ１０４）。その後、判定手段５４は、求めた分割領域に対応付けられた角度を線分の角度とする。具体的には、判定手段５４は、記憶手段１２に保存された式８を参照し、求めたｋを式８に代入することで角度を求める。
【００４０】
ステップ１０４における大小判定方法の具体例を説明する。座標変換手段５２が座標（ｘｉ，ｙｉ）を特定した後、象限変換手段５３は、ｘｉ及びｙｉの正負の符号を記憶手段１２に格納し、ｘｉ及びｙｉの絶対値として｜ｘｉ｜及び｜ｙｉ｜を算出する。判定手段５４は、象限変換手段５３が｜ｘｉ｜及び｜ｙｉ｜を算出すると、ｋを０から（Ｎ−１）まで１ずつ増加させながら、｜ｙｉ｜と｜ｘｉ｜×Ａ（ｋ）の大小判定を行い、｜ｙｉ｜が｜ｘｉ｜×Ａ（ｋ）より小さくなるｋを求め、求めたｋとｘｉ及びｙｉについて記憶手段１２に格納された正負の符号とに基づいて、座標（ｘｉ，ｙｉ）の端点が属する分割領域を求める。
【００４１】
次に、本実施形態の情報処理装置が実行する角度算出のための情報処理の手順を、一般的なプログラム言語、例えばＣ言語の書法に則って具体化した場合を説明する。ここでは、「（２）全方位の分割に均等性や対称性がある場合」を適用して説明する。
【００４２】
// 入力：  線分を決める２点の座標  →  x1,y1,  x2,y2
//         Ｎ分割境界線の傾き（予め計算され、記憶手段１２が記憶）→  a[0], a[1], a[2], …, a[N/4-1]
//         ここで、a[i] = tan(2*π*(i+1)/N)
// 出力：  求める角度が属する分割番号  →  m
// 処理１
xi = x2-x1 ;                  // 原点への平行移動のため、x座標を操作
yi = y2-y1 ;                  // 原点への平行移動のため、y座標を操作
// 処理２
flagx = 1;
if (xi < 0) {
flagx = -1;             // 点(xi,yi)が第２象限、第３象限にあることを記録
xi = -xi;               // xiを符号反転し、第１象限の問題に変換
}
flagy = 1;
if (yi < 0) {
flagy = -1;             // 点(xi,yi)が第３象限、第４象限にあることを記録
yi = -yi;               // yiを符号反転し、第１象限の問題に変換
}
// 処理３
m = 0 ;                       // 分割番号mの初期値は0
// 処理４
while (m < N/4-1){            // 第１象限での分割番号は0からN/4-1まで
if ( xi*a[m] > yi ) {   // 第１象限の問題を解くための条件文
break;            // 上のif文が成立したときのmが答えなので、ループ処理終了
}
m = m+1;
}
// 処理５
if (flagx == -1) {            // 第２象限、第３象限の場合、mの値を変換
m = N/2-1-m;
}
if (flagy == -1) {            // 第３象限、第４象限の場合、mの値を変換
m = N-1-m;
}
このプログラムは次の手順を実行するものである。
【００４３】
ここでは、空間分割手段５１が２次元空間としてｘｙ座標を設定し、ｘｙ座標をＮ個に均等に、かつ原点対称に分割し、分割境界線となる半直線の傾きa[0], a[1], a[2], …, a[N/4-1]を記憶手段１２に予め格納しているものとする。
【００４４】
[手順１] 角度を求めるべき線分を定める２点(x1,y1)及び(x2,y2)が演算手段１１に入力される。
[手順２] 座標変換手段５２は点(x1,y1)が原点と重なるよう線分を平行移動させる（処理１）。
[手順３] 象限変換手段５３は、平行移動後の点(x2-x1,y2-y1)が属する象限を記憶手段１２に記録し、その点を第１象限上の点に変換する（処理２）。
[手順４] 判定手段５４は、求める角度に対応する分割番号mに初期値0を設定する（処理３）。
[手順５] 判定手段５４は、分割番号mを増加しながら、求める角度が分割mに属すか否かの条件式を計算し、正しいmを探索する。
条件が成立したら探索を終了する（処理４）。
[手順６] 判定手段５４は、手順２で記憶手段１２に記録された象限に応じて、分割番号mを変換する（処理５）。
【００４５】
このようにして、演算コストの小さな加算や乗算、それと条件判断を用いて、角度に対応する分割番号ｍを求めることができる。手順６の後、判定手段５４が記憶手段１２に保存された式８のｋにｍを代入すれば、分割番号ｍに対応する角度が求められる。
【００４６】
本実施形態は、近似多項式を用いる逆正接関数で角度を求める場合に比べ精度は低いものの、加算、乗算、及び条件判断のみを用いて角度を計算することができ、高速に角度を求めることが可能となる。
【００４７】
また、角度計算のために分割境界線の傾きの値をテーブルとして記憶手段１２に保持しているが、このテーブルのエントリ数は、角度領域の分割数、すなわち、求める角度の精度に応じて定まるものであり、本発明の対象となる「精度が低くても、高速な角度計算」を実現する場合においては、特許文献１に開示されたような大規模なテーブルを準備しておく必要がない。
【００４８】
（第２の実施形態）
本実施形態は、全方位を均等かつ原点対称に複数に分割し、加算、乗算及び三項演算子を用いて、高速に角度計算を実行する機能を備えた計算ハードウェアの場合である。
【００４９】
第１の実施形態で説明した情報処理方法では、if文による条件分岐処理を多用している。そのため、if文の高速処理に寄与する機構（例えば、予測分岐機構）を備えていない計算ハードウェア上で実施した場合、if文の演算コストがやや大きいことから、本発明の効果が十分に発揮されるとは言い切れない。
【００５０】
一方、ある種の計算ハードウェアの中には（例えば、ＮＶＩＤＩＡ製ＧＰＵ(Graphics Processing Unit)、ＡＲＭ製プロセッサ等）、三項演算子
x = cond ? a : b    …  （条件condが成立したらx=a、不成立ならx=b）
を高速に実行できる機能を備えたものがある。
【００５１】
こうした特別な計算ハードウェアを利用すれば、第１の実施形態で説明した角度計算方法をさらに高速に処理することが可能となる。
【００５２】
本実施形態の情報処理装置の構成は、図１３に示した情報処理装置１０と同様であるが、演算手段１１の構成が第１の実施形態とは異なる。図１６は本実施形態の情報処理装置における演算手段の一構成例を示すブロック図である。
【００５３】
図１６に示すように、演算手段１１は、空間分割手段６１と、座標変換手段６２と、象限変換手段６３と、判定手段６４とを有する。本実施形態では、象限変換手段６３及び判定手段６４のそれぞれは、第１の実施形態で説明した象限変換手段５３及び判定手段５３のそれぞれの機能を備えているだけでなく、三項演算子を実行する機能を備えている。空間分割手段６１及び座標変換手段６２のそれぞれは第１の実施形態で説明した空間分割手段５１及び座標変換手段５２のそれぞれと同様な構成であるため、その詳細な説明を省略する。
【００５４】
次に、第１の実施形態で説明した角度計算方法について、三項演算子を用いて処理する方法の手順を具体化した場合を説明する。
【００５５】
// 入力：  線分を決める２点の座標  →  x1,y1,  x2,y2
//         Ｎ分割境界線の傾き（予め計算され、記憶手段１２が記憶）→  a[0], a[1], a[2], …, a[N/4-1]
//         ここで、a[i] = tan(2*π*(i+1)/N)
// 出力：  求める角度が属する分割番号  →  m
// 処理１
xi    = x2-x1 ;                   // 原点への平行移動のため、x座標を操作
yi    = y2-y1 ;                   // 原点への平行移動のため、y座標を操作
// 処理２
flagx = xi<0 ? -1 : 1 ;           // 点(xi,yi)が第２象限、第３象限にあるか否かを記録
xi    = xi<0 ? -xi : xi ;         // xiを符号反転し、第１象限の問題に変換
flagy = yi<0 ? -1 : 1 ;           // 点(xi,yi)が第２象限、第３象限にあるか否かを記録
yi    = yi<0 ? -yi : yi ;         // yiを符号反転し、第１象限の問題に変換
// 処理３
m     = 0 ;                       // 出力mの初期値は0
// 処理４
※    m     = xi*a[m]>yi ? m : m+1 ;  // 第１象限での条件文が成立すればmが答え、不成立ならm+1として次へ(m=0)
※    m     = xi*a[m]>yi ? m : m+1 ;  // 第１象限での条件文が成立すればmが答え、不成立ならm+1として次へ(m=1)
※    m     = xi*a[m]>yi ? m : m+1 ;  // 第１象限での条件文が成立すればmが答え、不成立ならm+1として次へ(m=2)
※      ...
※    m     = xi*a[m]>yi ? m : m+1 ;  // 第１象限での条件文が成立すればmが答え、不成立ならm+1として次へ(m=N/4-1)
// 処理５
m     = flagx<0 ? N/2-1-m : m ;   // 第２象限、３象限の場合、mの値を変換、そうでなければmのまま
m     = flagy<0 ? N-1-m : m ;     // 第３象限、４象限の場合、mの値を変換、そうでなければmのまま
なお、上記処理４における※の部分は、同じ処理内容が(N/4-1)回分記述されているものとする。
【００５６】
このプログラムは次の手順を実行するものである。ここでは、空間分割手段６１が２次元空間としてｘｙ座標を設定し、ｘｙ座標をＮ個に均等に、かつ対称に分割し、分割境界線となる半直線の傾きa[0], a[1], a[2], …, a[N/4-1]を記憶手段１２に予め格納しているものとする。
【００５７】
[手順１] 角度を求めるべき線分を定める２点(x1,y1)及び(x2,y2)が演算手段１１に入力される。
[手順２] 座標変換手段６２は点(x1,y1)が原点と重なるよう線分を平行移動させる（処理１）。
[手順３] 象限変換手段６３は、平行移動後の点(x2-x1,y2-y1)が属する象限を記憶手段１２に記録し、その点を第１象限上の点に変換する（処理２）。
[手順４] 判定手段６４は、求める角度に対応する分割番号mに初期値0を設定する（処理３）。
[手順５] 判定手段６４は、求める角度が分割mに属すか否かの条件式を計算し、成立したらmの値を保存し、不成立ならばmを1増加させる。
この処理をN/4-1回繰り返す（処理４）。
[手順６] 判定手段６４は、手順２で記憶手段１２に記録された象限に応じて、分割番号mを変換する（処理５）。
【００５８】
このようにして、演算コストの小さな加算や乗算と、それと三項演算子を用いて、角度に対応する分割番号ｍを求めることができる。手順６の後、判定手段５４が記憶手段１２に保存された式８のｋにｍを代入すれば、分割番号ｍに対応する角度が求められる。
【００５９】
本実施形態では、三項演算子が特別な計算ハードウェアにおいては高速に実行される性質を利用したものであり、第１の実施形態と同様な効果が得られるだけでなく、全方位の分割数Ｎが第１の実施形態と同じ場合、第１の実施形態に比べてより速く角度を計算できる。
【００６０】
なお、第２の実施形態では、「（２）全方位の分割に均等性や対称性がある場合」を説明したが、第２の実施形態の角度計算方法を「（１）基本原理」にしたがって行ってもよい。
【実施例１】
【００６１】
第２の実施形態についての実施例を説明する。本実施例では、図１６に示した演算手段１１がＮＶＩＤＩＡ製ＧＰＵ(形式：ＧＴＸ５８０)を含む構成である。
【００６２】
この演算手段１１のＧＰＵは、三項演算子を一命令で実行できる機能を備えている。また、演算手段１１のＧＰＵは、逆正接計算のための組み込み関数atan2f(y,x)を実行する機能も備えている。
【００６３】
本実施例の情報処理装置が実行する角度算出方法と式２を用いた近似計算法とについて、実行時間の比較を行ったので、その結果を説明する。角度の計算精度は、全方位を８等分に分割した場合において、角度計算対象の線分の端点がどの分割領域に属するかを求めればよいものとする。
【００６４】
図１７は本実施例の角度算出方法と式２を用いた近似計算方法のそれぞれの処理時間の結果を示すグラフである。図１７では、入力されるディジタル画像に対して、１４１４万１９５２回の角度計算を行った場合の処理時間を示す。図１７に示すように、式２を用いた近似計算方法の処理時間が約４６０マイクロ秒であるのに対して、本実施例の角度算出方法の処理時間は約２２３マイクロ秒であった。本実施例の角度算出方法は、組込関数で計算した場合の約２倍強の速度で計算を完了した。
【００６５】
なお、本発明の情報処理装置はコンピュータとプログラムによっても実現でき、そのプログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【符号の説明】
【００６６】
１０    情報処理装置
１１    演算手段
１２    記憶手段
５１、６１    空間分割手段
５２、６２    座標変換手段
５３、６３    象限変換手段
５４、６４    判定手段
【図１】
2013037482.tif 000003
【図２】
2013037482.tif 000004
【図３】
2013037482.tif 000005
【図４】
2013037482.tif 000006
【図５】
2013037482.tif 000007
【図６】
2013037482.tif 000008
【図７】
2013037482.tif 000009
【図８】
2013037482.tif 000010
【図９】
2013037482.tif 000011
【図１０】
2013037482.tif 000012
【図１１】
2013037482.tif 000013
【図１２】
2013037482.tif 000014
【図１３】
2013037482.tif 000015
【図１４】
2013037482.tif 000016
【図１５】
2013037482.tif 000017
【図１６】
2013037482.tif 000018
【図１７】
2013037482.tif 000019