(57)【特許請求の範囲】
【請求項１】
第１画像内の各ラインに複数設定された代表画素の座標に対応すべき第２画像内の画素の座標を、透視変換用の変換式を用いて算出する代表画素座標算出部と、
ラインごとに、隣接する二つの代表画素間に存在する複数の画素の座標にそれぞれ対応すべき前記第２画像内の複数の画素のそれぞれの座標を、当該二つの代表画素の座標に対応すべき前記第２画像内の二つの画素の座標を線形補間して算出する非代表画素座標算出部と、
前記第１画像内の各ラインを、それぞれ同じ画素数を含む複数の区間に分割し、かつ各区間の先頭画素を前記代表画素に設定する区間設定部と、
を備え、
前記代表画素座標算出部は、
ラインごとに、先頭区間およびその次区間の二つの代表画素の座標に対応すべき前記第２画像内の二つの画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値およびそれら中間値を最終値に変換するための変換値を、前記変換式を用いて前記二つの代表画素毎に算出する先頭中間値算出部と、
前記先頭中間値算出部により算出された、二つのｘ座標の中間値、二つのｙ座標の中間値、および二つの前記変換値のそれぞれの差分を算出して、ｘ座標の中間値の増分値、ｙ座標の中間値の増分値、および前記変換値の増分値を求める増分値算出部と、
ラインごとに、先頭区間の代表画素の座標に対応すべき前記第２画像内の画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および前記変換値、ならびに前記ｘ座標の中間値の増分値、前記ｙ座標の中間値の増分値および前記変換値の増分値をもとに、前記先頭区間以外の区間のそれぞれの代表画素の座標に対応すべき前記第２画像内の画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および前記変換値を前記それぞれの代表画素毎に算出する非先頭中間値算出部と、
各代表画素の座標に対応すべき前記第２画像内の各画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および前記変換値をもとに、当該第２画像内の各画素のｘ座標およびｙ座標の最終値を算出する最終値算出部と、
を含むことを特徴とする画像処理装置。
【請求項２】
前記区間設定部は、各区間に含まれる画素数を二の乗数に設定することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
第１画像内の各ラインに複数の代表画素を設定し、代表画素の座標に対応すべき第２画像内の画素の座標を、透視変換用の変換式を用いて算出する第１ステップと、
ラインごとに、隣接する二つの代表画素間に存在する複数の画素の座標にそれぞれ対応すべき前記第２画像内の複数の画素のそれぞれの座標を、当該二つの代表画素の座標に対応すべき前記第２画像内の二つの画素の座標を線形補間して算出する第２ステップと、
を備え、
前記第１ステップは、
前記第１画像内の各ラインを等間隔の複数の区間に分割し、かつ各区間の先頭画素を前記代表画素に設定するステップと、
ラインごとに、先頭区間およびその次区間のそれぞれの代表画素の座標に対応すべき前記第２画像内の二つの画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値およびそれら中間値を最終値に変換するための変換値を、前記変換式を用いて前記二つの代表画素毎に算出するステップと、
算出された、二つのｘ座標の中間値、二つのｙ座標の中間値、および二つの前記変換値のそれぞれの差分を算出して、ｘ座標の中間値の増分値、ｙ座標の中間値の増分値、および前記変換値の増分値を求めるステップと、
ラインごとに、先頭区間の代表画素の座標に対応すべき前記第２画像内の画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および前記変換値、ならびに前記ｘ座標の中間値の増分値、前記ｙ座標の中間値の増分値および前記変換値の増分値をもとに、前記先頭区間以外の区間のそれぞれの代表画素の座標に対応すべき前記第２画像内の画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および前記変換値を前記それぞれの代表画素毎に算出するステップと、
各代表画素の座標に対応すべき前記第２画像内の各画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および前記変換値をもとに、当該第２画像内の各画素のｘ座標およびｙ座標の最終値を算出するステップと、
を含むことを特徴とする画像処理方法。
【請求項４】
前記各ラインを複数の区間に分割するステップにおいて、各区間に含まれる画素数を二の乗数に設定することを特徴とする請求項３に記載の画像処理方法。
【請求項５】
第１画像内の各ラインに複数の代表画素を設定し、代表画素の座標に対応すべき第２画像内の画素の座標を、透視変換用の変換式を用いて算出する第１ステップと、
ラインごとに、隣接する二つの代表画素間に存在する複数の画素の座標にそれぞれ対応すべき前記第２画像内の複数の画素のそれぞれの座標を、当該二つの代表画素の座標に対応すべき前記第２画像内の二つの画素の座標を線形補間して算出する第２ステップと、
をコンピュータに実行させ、
前記第１ステップは、
前記第１画像内の各ラインを等間隔の複数の区間に分割し、かつ各区間の先頭画素を前記代表画素に設定するステップと、
ラインごとに、先頭区間およびその次区間のそれぞれの代表画素の座標に対応すべき前記第２画像内の二つの画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値およびそれら中間値を最終値に変換するための変換値を、前記変換式を用いて前記二つの代表画素毎に算出するステップと、
算出された、二つのｘ座標の中間値、二つのｙ座標の中間値、および二つの前記変換値のそれぞれの差分を算出して、ｘ座標の中間値の増分値、ｙ座標の中間値の増分値、および前記変換値の増分値を求めるステップと、
ラインごとに、先頭区間の代表画素の座標に対応すべき前記第２画像内の画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および前記変換値、ならびに前記ｘ座標の中間値の増分値、前記ｙ座標の中間値の増分値および前記変換値の増分値をもとに、前記先頭区間以外の区間のそれぞれの代表画素の座標に対応すべき前記第２画像内の画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および前記変換値を前記それぞれの代表画素毎に算出するステップと、
各代表画素の座標に対応すべき前記第２画像内の各画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および前記変換値をもとに、当該第２画像内の各画素のｘ座標およびｙ座標の最終値を算出するステップと、
を含むことを特徴とする画像処理プログラム。
【請求項６】
前記各ラインを複数の区間に分割するステップにおいて、各区間に含まれる画素数を二の乗数に設定することを特徴とする請求項５に記載の画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を幾何学変換する画像処理装置、画像処理方法およびそのプログラムに関する。
【背景技術】
【０００２】
画像処理技術の分野では、画像の形状を変更するために幾何学変換が多く用いられる。幾何学変換を用いた画像処理の代表的なものとして、画像符号化のグローバル動き補償、カメラの電子式手振れ補正、プロジェクタの台形補正、パノラマ画像生成、超解像処理、多眼カメラで撮影された多視点映像の視点移動などが挙げられる。
【０００３】
幾何学変換は、入力画像の画素の座標(x, y)を出力画像の座標(X, Y)に移動させることによって行われる。幾何学変換の一種に透視変換がある。透視変換は、射影変換の一種であり、視点位置より遠くにある物体を縮小して遠近感を出すことができる。
【０００４】
透視変換の順変換は、次の式（１）〜式（５）により定義される。
【数１】
0005387288.tif 000002
【数２】
0005387288.tif 000003
式（１）、式（２）を行列の形で書き表すと、
【数３】
0005387288.tif 000004
ここで、
【数４】
0005387288.tif 000005
【数５】
0005387288.tif 000006
【０００５】
次に、透視変換の逆変換は、次の式（６）〜式（１０）により定義される。
【数６】
0005387288.tif 000007
【数７】
0005387288.tif 000008
式（６）、式（７）を行列の形で書き表すと、
【数８】
0005387288.tif 000009
ここで、
【数９】
0005387288.tif 000010
【数１０】
0005387288.tif 000011
【０００６】
式（３）および式（８）内の３×３の行列は、変換行列である。透視変換を行うには、まず、この変換行列を求める必要がある。変換行列を求めた後、順変換では、式（３）〜式（５）の演算式を用いて、入力画像の各画素の座標(x, y)に対応する出力画像の各画素の座標(X, Y)を算出する。その座標(X, Y)の画素値を、入力画像の上記座標(x, y)の画素値に設定する。逆変換では、式（８）〜式（１０）の演算式を用いて、出力画像の各画素の座標(X,Y)に対応する入力画像の各画素の座標(x,y)を算出する。その座標(x, y)の画素値を、出力画像の上記座標(X,Y)の画素値に設定する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開昭６１−１４７３７６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
透視変換の順変換では、出力画像の各画素の座標(X, Y)に対応する入力画像の各画素の座標（x, y）を計算する際、画素ごとに、加算および乗算をそれぞれ６回、除算を２回行う必要がある（式（１）、式（２）参照）。なお、式（１）、式（２）の分母は共通であるため、加算および乗算をそれぞれ８回行うのではなく、６回行う。これらの考察は逆変換についても同様にあてはまる。
【０００９】
種々のアプリケーションで使用される画像の解像度は、年々、増加しており、一枚の画像の透視変換に必要な演算量も増大している。ところで、ハードウェアで除算を実行する場合、実行サイクル数を多く必要とする。透視変換には除算が含まれるため、高解像度の画像をハードウェアで透視変換するには、処理負荷が高くなり、難しい面が多い。たとえば、演算エラーやコマ落ちが発生する可能性も懸念される。
【００１０】
本発明はこうした状況に鑑みなされたものであり、その目的は、ある画像を透視変換して別の画像を生成する際の演算量を低減する技術を提供することにある。
【課題を解決するための手段】
【００１１】
本発明のある態様の画像処理装置は、第１画像内の各ラインに複数設定された代表画素の座標に対応すべき第２画像内の画素の座標を、透視変換用の変換式を用いて算出する代表画素座標算出部と、ラインごとに、隣接する二つの代表画素間に存在する複数の画素の座標にそれぞれ対応すべき第２画像内の複数の画素のそれぞれの座標を、当該二つの代表画素の座標に対応すべき第２画像内の二つの画素の座標を線形補間して算出する非代表画素座標算出部と、第１画像内の各ラインを、それぞれ同じ画素数を含む複数の区間に分割し、かつ各区間の先頭画素を代表画素に設定する区間設定部と、を備える。代表画素座標算出部は、ラインごとに、先頭区間およびその次区間の二つの代表画素の座標に対応すべき第２画像内の二つの画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値およびそれら中間値を最終値に変換するための変換値を、変換式を用いて二つの代表画素毎に算出する先頭中間値算出部と、先頭中間値算出部により算出された、二つのｘ座標の中間値、二つのｙ座標の中間値、および二つの変換値のそれぞれの差分を算出して、ｘ座標の中間値の増分値、ｙ座標の中間値の増分値、および変換値の増分値を求める増分値算出部と、ラインごとに、先頭区間の代表画素の座標に対応すべき第２画像内の画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および変換値、ならびにｘ座標の中間値の増分値、ｙ座標の中間値の増分値および変換値の増分値をもとに、先頭区間以外の区間のそれぞれの代表画素の座標に対応すべき第２画像内の画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および変換値をそれぞれの代表画素毎に算出する非先頭中間値算出部と、各代表画素の座標に対応すべき第２画像内の各画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および変換値をもとに、当該第２画像内の各画素のｘ座標およびｙ座標の最終値を算出する最終値算出部と、を含む。
【００１２】
本発明の別の態様は、画像処理方法である。この方法は、第１画像内の各ラインに複数の代表画素を設定し、代表画素の座標に対応すべき第２画像内の画素の座標を、透視変換用の変換式を用いて算出する第１ステップと、ラインごとに、隣接する二つの代表画素間に存在する複数の画素の座標にそれぞれ対応すべき第２画像内の複数の画素のそれぞれの座標を、当該二つの代表画素の座標に対応すべき第２画像内の二つの画素の座標を線形補間して算出する第２ステップと、を備える。第１ステップは、第１画像内の各ラインを等間隔の複数の区間に分割し、かつ各区間の先頭画素を代表画素に設定するステップと、ラインごとに、先頭区間およびその次区間のそれぞれの代表画素の座標に対応すべき第２画像内の二つの画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値およびそれら中間値を最終値に変換するための変換値を、変換式を用いて二つの代表画素毎に算出するステップと、算出された、二つのｘ座標の中間値、二つのｙ座標の中間値、および二つの変換値のそれぞれの差分を算出して、ｘ座標の中間値の増分値、ｙ座標の中間値の増分値、および変換値の増分値を求めるステップと、ラインごとに、先頭区間の代表画素の座標に対応すべき第２画像内の画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および変換値、ならびにｘ座標の中間値の増分値、ｙ座標の中間値の増分値および変換値の増分値をもとに、先頭区間以外の区間のそれぞれの代表画素の座標に対応すべき第２画像内の画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および変換値をそれぞれの代表画素毎に算出するステップと、各代表画素の座標に対応すべき第２画像内の各画素の座標を求めるための、ｘ座標の中間値、ｙ座標の中間値および変換値をもとに、当該第２画像内の各画素のｘ座標およびｙ座標の最終値を算出するステップと、を含む。
【００１３】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１４】
ある画像を透視変換して別の画像を生成する際の演算量を低減することができる。
【図面の簡単な説明】
【００１５】
【図１】透視変換前の入力画像の一例を示す図である。
【図２】図１の入力画像に対する、透視変換後の出力画像を示す図である。
【図３】本発明の実施の形態１に係る画像処理装置の構成を示すブロック図である。
【図４】本発明の実施の形態１に係る画像処理装置の代表画素座標算出部の構成を示すブロック図である。
【図５】出力画像（１９２０×１０８０）を区間分割する一例を示す図である。
【図６】一区間の画素数が２５６の場合における、各区間における区間インデックスと開始点のｘ座標をまとめた図である。
【図７】実施の形態１に係る画像処理装置の処理手順を示すフローチャートである。
【図８】図７のステップＳ１０４の詳細な処理手順を示すフローチャートである。
【図９】図７のステップＳ１０７の詳細な処理手順を示すフローチャートである。
【図１０】ステップＳ１０９の詳細な処理手順を示すフローチャートである。
【図１１】本発明の実施の形態２に係る画像処理装置の代表画素座標算出部の構成を示すブロック図である。
【図１２】実施の形態２に係る画像処理装置の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１６】
本発明では画像を透視変換するため、上記式（１）および式（２）に示したように、二次元図形の透視変換式が用いられる。当該透視変換式の分子は、アフィン変換式である。アフィン変換は、線形変換と平行移動を合成した変換方式であり、変換前の図形と変換後の図形とで幾何学的性質が保たれる。たとえば、変換前の図形で直線上に並ぶ点は変換後も直線上に並び、平行線は変換後も平行線である。
【００１７】
上記透視変換式の分母は、入力画像の画素の座標（x, y）を変数とする一次方程式で定義される。これにより、遠くの図形が小さく、近くの図形が大きく投影される。このように、透視変換では、ワールド座標系の平面図形を、視点座標系の平面図形に変換することが可能である。すなわち、ワールド座標系の図形が形成されている平面に対して、傾いている平面に当該図形を変換しつつ複写することが可能である。
【００１８】
図１は、透視変換前の入力画像の一例を示す図である。図２は、図１の入力画像に対する、透視変換後の出力画像を示す図である。図１に示す透視変換前の入力画像に描かれている頂点Ａ、Ｂ、Ｃ、Ｄにより形成される四角形は、左側が大きく、右側が小さい。すなわち、右側に奥行きを持つ四角形である。図２に示す四角形は、図１に示す四角形を透視変換することにより、奥行きのない四角形に変換されたものである。なお、図２に示す出力画像内の黒色部分は、図１に示す入力画像の領域外の座標に対応するため、画素値を補償することができない部分である。
【００１９】
透視変換は、入力画像の各画素の座標(x, y)を出力画像の各画素の座標(X, Y)に移動させることによって行われる。より具体的には、まず、変換行列を求める。次に、順変換ではその変換行列を用いて、入力画像の各画素の座標(x, y)に対応する、出力画像の各画素の座標(X, Y)を算出する（上記式（３）〜式（５）参照）。次に、出力画像の算出された座標(X, Y)の画素値として、入力画像の座標(x, y)の画素値を割り当てる。出力画像の算出された座標(X, Y)のほとんどは小数を含む値となる。
【００２０】
デジタル画像の座標は整数値で表現される必要があるため、出力画像がデジタル画像である場合、出力画像の算出された座標(X, Y)の画素値をもとに、出力画像の整数の座標(X, Y)の画素値を補間演算により算出する。
【００２１】
また、逆変換では上記変換行列を用いて、出力画像の各画素の座標(X, Y)に対応する、入力画像の各画素の座標(x, y)を算出する（上記式（８）〜式（１０）参照）。次に、入力画像の算出された座標(x, y)の画素値を、出力画像の座標(X, Y)の画素値として割り当てる。入力画像の算出された座標(x, y)のほとんどは小数を含む値となる。
【００２２】
デジタル画像の座標は整数値で表現されるため、小数を含む座標を参照することはできない。入力画像がデジタル画像である場合、入力画像の整数の座標(x, y)の画素値をもとに、入力画像の算出された座標(x, y)の画素値を補間演算により算出する。その補間演算により算出された画素値が出力画像の座標(X, Y)の画素値として割り当てられる。
【００２３】
上述した補間演算には、線形補間法（たとえば、バイリニア法）や三次補間法（たとえば、バイキュービック法）などを採用することができる。
【００２４】
以下、本発明の実施の形態を、逆変換を用いた例をもとに説明する。なお、本発明の実施の形態を、順変換を用いても実現可能なことは、当業者に理解されるところである。また、以下の説明では、入力画像は透視変換前の画像を指し、出力画像は透視変換後の画像を指すとする。
【００２５】
（実施の形態１）
図３は、本発明の実施の形態１に係る画像処理装置１００の構成を示すブロック図である。画像処理装置１００は、第１記憶部１０１、変換行列算出部１０２、座標算出部１０３、画素補間部１０４および第２記憶部１０５を備える。変換行列算出部１０２は、対応点座標算出部１２１および連立方程式算出部１２２を含む。座標算出部１０３は、区間設定部１３１、代表画素座標算出部１３２および非代表画素座標算出部１３７を含む。
【００２６】
図４は、本発明の実施の形態１に係る画像処理装置１００の代表画素座標算出部１３２の構成を示すブロック図である。代表画素座標算出部１３２は、先頭中間値算出部１３３、中間値増分値算出部１３４、非先頭中間値算出部１３５および最終値算出部１３６を含む。
【００２７】
図３および図４に示した構成は、ハードウェア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウェア的にはメモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。
【００２８】
第１記憶部１０１には、入力画像が蓄積される。また、変換行列算出用の基準画像が蓄積されてもよい。
【００２９】
変換行列算出部１０２は、透視変換用の変換行列を算出する。より具体的には、変換行列算出部１０２は、入力画像内の任意の４点（たとえば、四角形の頂点）の座標と、その４点の座標を移動させるべき出力画像内の４点の座標を特定する。そして、入力画像内の４点の座標と、出力画像内の４点の座標とから連立方程式を導き、この連立方程式を解くことにより変換行列を求める。
【００３０】
以下、さらに具体的に説明する。対応点座標算出部１２１は、第１記憶部１０１に蓄積された入力画像または基準画像の特徴点を抽出し、四角形を形成すべき４点の座標を求める。次に、その４点の特徴点に対応すべき、出力画像内の対応点を画素マッチングや勾配法などの手法を用いて特定し、入力画像または基準画像と出力画像において、対応する４点の座標を求める。なお、出力画像内の４点の座標は、事前にまたはリアルタイムに、ユーザ操作に起因して設定されてもよい。すなわち、手動で設定されてもよい。
【００３１】
たとえば、上述した図１に示した入力画像から、図２に示した出力画像に透視変換する場合、図１に示した入力画像内の画素Ａの座標（xa, ya）とその移動先の図２に示した出力画像内の画素Ａの座標（Xa, Ya）、当該入力画像内の画素Ｂの座標（xb, yb）とその移動先の当該出力画像内の画素Ｂの座標（Xb, Yb）、当該入力画像内の画素Ｃの座標（xc, yc）とその移動先の当該出力画像内の画素Ｃの座標（Xc, Yc）、および当該入力画像内の画素Ｄの座標（xd, yd）とその移動先の当該出力画像内の画素Ｄの座標（Xd, Yd）を求める。
【００３２】
すなわち、歪んだ長方形の頂点を形成する４点を、歪みのない長方形の頂点位置に移動させる。この４点の頂点同士を基礎とする透視変換用の変換行列を算出することにより、入力画像内の歪んだ長方形を、歪みのない長方形に補正することができる。
【００３３】
連立方程式算出部１２２は、入力画像の内の４点の座標と、それらに対応する出力画像内の４点の座標から８元１次連立方程式を導き、この連立方程式を解くことにより、上記変換行列を求める。上記式（８）〜式（１０）の変換行列は、下記式（１１）を解くことにより求めることができる。
【００３４】
【数１１】
0005387288.tif 000012
【００３５】
上記式（１１）は、ガウスの消去法などのアルゴリズムを用いて解くことができる。ただし、入力画像内の画素Ａの座標（xa, ya）と出力画像内の画素Ａの座標（Xa, Ya）とが１対１で対応し、当該入力画像内の画素Ｂの座標（xb, yb）と当該出力画像内の画素Ｂの座標（Xb, Yb）とが１対１で対応し、当該入力画像の画素Ｃの座標（xc, yc）と当該出力画像内の画素Ｃの座標（Xc, Yc）とが１対１で対応し、および当該入力画像内の画素Ｃの座標（xd, yd）と当該出力画像内の画素Ｃの座標（Xd, Yd）とが１対１で対応するものとする。
【００３６】
座標算出部１０３は、変換行列算出部１０２で算出された変換行列を用いて、出力画像内の各画素の座標(X, Y)に対応する、入力画像内の各画素の座標(x, y)を算出する。上述したように、透視変換の逆変換では、出力画像内の各画素の座標(X, Y)に対応する、入力画像内の各画素の座標(x, y)のほとんどは小数を含むことになり、小数を含む画素の座標(x, y)は、整数画素の座標(x, y)から補間演算により算出される。この点を捉えて、以下の説明では、適宜、出力画像内の各画素の座標(X, Y)に対応する、入力画像内の各画素の座標(x, y)を補間座標(x, y)と呼ぶ。
【００３７】
上述したように、出力画像内の各画素ごとに上記式（８）〜式（１０）に示された演算を行うことにより、補間座標(x, y)を算出することができる。その際、画素ごとに、加算と乗算を６回、除算を２回行う必要があり、ハードウェアへの実装を考慮すると、非常に演算コストのかかる処理となる。そこで、本実施の形態では演算量を削減するため、画素ごとに乗算や除算を行わずに、補間座標(x, y)を算出する手法を用いる。
【００３８】
以下、より具体的に説明する。区間設定部１３１は、出力画像内の各ラインを、それぞれ同じ画素数を含む複数の区間に分割する。区間設定部１３１は、分割した各区間の先頭画素を代表画素に設定する。
【００３９】
図５は、出力画像（１９２０×１０８０）を区間分割する一例を示す図である。ここでは、各水平ラインが２５６画素ごとに区切られ、各水平ラインに七つの区間が設定される。なお、一区間の幅Ｎ（Ｎは水平方向の画素数）は、２５６画素に限定されないが、１２８画素や５１２画素など、二の乗数の値に設定されることが好ましい。
【００４０】
以下の説明では、画像の左上隅の座標を(0, 0)とし、水平方向で左から右を主走査方向、垂直方向で上から下を副走査方向とする。さらに、各ラインの最初の区間を区間０とし、その区間の区間インデックスｉを０とする。この区間０の開始点のｘ座標の値は０である。その次の区間を区間１とし、その区間の区間インデックスｉを１とする。この区間１の開始点のｘ座標の値は２５６である。区間インデックスｉの区間の開始点のｘ座標は、（Ｎ×ｉ）である。
【００４１】
図６は、一区間の画素数が２５６の場合における、各区間における区間インデックスと開始点のｘ座標をまとめた図である。なお、図５に示した出力画像では、区間７は実際には１２８画素（＝１９２０−１７９２）しか存在しないが、本実施の形態に係る座標の計算では、処理を単純化するため、区間７も仮想的に他の区間０〜６と同様に２５６画素存在するものとして計算する。すなわち、全区間の画素数を同一にすることにより、処理を単純化し、演算量の削減に繋げている。また、区間８には画素が存在しないが、区間８の開始点のｘ座標の値を２０４８とする。これにより、区間７も区間０〜区間６と同様の方法で、座標を算出することができる。
【００４２】
代表画素座標算出部１３２は、出力画像内の各ラインに複数設定された代表画素の座標に対応すべき入力画像内の画素の座標を、透視変換用の変換式を用いて算出する。上述した例では、代表画素座標算出部１３２は、出力画像内の各ラインにおける各区間の開始点の座標に対応すべき、入力画像内の補間座標を算出する。
【００４３】
以下、より具体的に説明する。先頭中間値算出部１３３は、出力画像の各ラインごとに、先頭区間およびその次の区間の二つの代表画素の座標に対応すべき入力画像内の二つの画素の座標を求めるための、テンポラル値（一時的な値）である、ｘ座標の中間値、ｙ座標の中間値およびそれら中間値を最終値に変換するための変換値を上記変換式を用いてそれぞれ算出する。以下適宜、ｘ座標の中間値、ｙ座標の中間値および当該変換値をそれぞれx’, y’, wと表記する。上記式（８）に示したように、x’はAX+BY+C（以下、第１の一次方程式と表記する）により算出され、 y’はDX+EY+F（以下、第２の一次方程式と表記する）により算出され、およびwはPX+QY+R（以下、第３の一次方程式と表記する）により算出される。
【００４４】
中間値増分値算出部１３４は、先頭中間値算出部１３３により算出された、二種類のx’, y’, wのそれぞれの差分を算出して、区間単位のx’の増分値、y’の増分値、およびwの増分値を求める。
【００４５】
非先頭中間値算出部１３５は、出力画像の各ラインごとに、先頭中間値算出部１３３により算出された、先頭区間の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, w、ならびに中間値増分値算出部１３４により算出された、x’の増分値、y’の増分値、およびwの増分値をもとに、先頭区間以外の区間のそれぞれの代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wをそれぞれ算出する。
【００４６】
より具体的には、ラインごとに、先頭区間の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wのそれぞれに、x’の増分値、y’の増分値、およびwの増分値をそれぞれ主走査方向に順次加算することにより、先頭区間に後続する区間の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wを順次算出することができる。なお、先頭区間の次の区間の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wは、先頭中間値算出部１３３により算出された値をそのまま、当てはめてもよい。
【００４７】
最終値算出部１３６は、出力画像の各代表画素の座標に対応すべき入力画像内の各画素の座標を求めるためのx’, y’, wをもとに、当該入力画像内の各画素のｘ座標およびｙ座標の最終値を算出する。以下適宜、ｘ座標およびｙ座標の最終値をそれぞれx, yと表記する。すなわち、代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wごとに、x’/wおよび y’/wを演算することにより、x, yを算出する（上記式（９）、式（１０）参照）。
【００４８】
非代表画素座標算出部１３７は、出力画像の各ラインごとに、隣接する二つの代表画素間に存在する複数の画素の座標にそれぞれ対応すべき入力画像内の複数の画素のそれぞれの補間座標を、当該二つの代表画素の座標に対応すべき入力画像内の二つの画素の補間座標を線形補間して算出する。
【００４９】
以下、より具体的に説明する。座標増分値算出部１３８は、ある区間の代表画素のx, yとその次の区間の代表画素のx, yとの差分値をそれぞれ算出することにより、ある区間の代表画素とその次の区間の代表画素との間のx, yの増分値を算出する。この代表画素間のx, yの増分値を、各ラインごとに、すべての区間について算出する。座標増分値算出部１３８は、ある区間のx, yの増分値をその区間の画素数で割ることにより、その区間内における、隣り合う画素間のx, yの増分値を算出する。この画素間のx, yの増分値を、各ラインごとに、すべての区間について算出する。
【００５０】
座標増分値加算部１３９は、各区間ごとに、代表画素のx, yに、画素間のx, yの増分値を主走査方向に順次加算することにより、各区間のすべての画素のx, yを算出する。以上の処理により、出力画像内の全画素の座標に対応する、入力画像内の補間座標（x, y）を算出する。
【００５１】
以下、実施の形態１に係る代表画素座標算出部１３２および非代表画素座標算出部１３７の処理を、上記図５、図６に則した例で説明する。まず、代表画素座標算出部１３２は、各ラインの各区間の開始点のx’, y’, wを算出する。その際、全区間の開始点のx’, y’, wを上記式（８）を用いて算出するのではなく、各ラインごとに、最初の区間の開始点（0, Y）とその次の区間の開始点（256, Y）のx’, y’, wのみを算出する。すなわち、先頭中間値算出部１３３は、各ラインごとに、最初の区間の開始点（0, Y）とその次の区間の開始点（256, Y）のx’, y’, wを上記式（８）を用いて算出する。
【００５２】
中間値増分値算出部１３４は、最初の区間の開始点（0, Y）のx’, y’, wと、その次の区間の開始点（256, Y）のx’, y’, wとの差分値をそれぞれ算出する。これにより、ある区間の開始点（X, Y）のx’, y’, wと、その次の区間の開始点（X+256, Y）のx’, y’, wとの間の、x’の増分値Δx’hi、y’の増分値Δy’ hi、およびwの増分値Δw hiを求める。
【００５３】
非先頭中間値算出部１３５は、ある区間の開始点（X, Y）のx’, y’, wに、x’の増分値Δx’hi、y’の増分値Δy’ hi、およびwの増分値Δw hiをそれぞれ加算することにより、その次の区間の開始点（X+256, Y）のx’, y’, wを算出する。たとえば、区間１の開始点のx’, y’, wにそれぞれの増分値Δx’hi, Δy’ hi, Δw hiを加算することにより、区間２の開始点のx’, y’, wを算出する。このようにして、本実施の形態では乗算回数を減らしている。
【００５４】
最終値算出部１３６は、各区間の開始点のx’, y’をそれぞれwで割り、各区間の開始点のx, yを算出する（上記式（９）、式（１０）参照）。
【００５５】
座標増分値算出部１３８は、ある区間の開始点のx, yとその次の区間の開始点のx, yとの差分値をそれぞれ算出することにより、ある区間の開始点とその次の区間の開始点との間のx, yの増分値Δxi, Δyiを算出する。この区間単位のx, yの増分値Δxi, Δyiを、各ラインごとに、全区間について算出する。座標増分値算出部１３８は、ある区間のx, yの増分値Δxi, Δyiをその区間の幅Ｎで割ることにより、その区間内における、ある画素のx, yからその次の画素のx, yへの増分値Δx, Δyを算出する。この画素単位のx, yの増分値Δx, Δyを、各ラインごとに、全区間について算出する。
【００５６】
ここで、各区間の画素数が二の乗数に設定されている場合、割り算を、ビットシフトや指数の減算など、負荷が小さい演算処理で実現することができる。たとえば、区間の幅Ｎを２５６とした場合、上記開始点間のx, yの増分値Δxi, Δyiを２５６で割る代わりに、整数演算や固定小数点演算では、それらの増分値Δxi, Δyiをそれぞれ右に８ビットシフトさせるだけでよい。また、ＩＥＥＥ７５４方式などによる浮動小数点演算では、指数値から８を引くだけでよい。なお、指数部は２を基数としている。
【００５７】
座標増分値加算部１３９は、各区間ごとに、開始点のx, yに、画素単位のx, yの増分値Δx, Δyを順次加算することにより、各区間の全画素のx, yを算出する。以上の処理により、出力画像内の全画素の座標に対応する、入力画像内の補間座標（x, y）を算出する。
【００５８】
上記式（９）、式（１０）に示したように、x, yはwで割ることにより算出されるため、x, yの増分値Δx, Δyは画素ごとに異なる値となる。これに対し、本実施の形態では、ラインごとに区間を設定し、区間内では同一の増分値とすることにより、画素ごとの演算としては増分値Δx, Δyの加算のみでx, yを算出することができる。したがって、画素ごとに乗算、除算を行う手法と比較して、演算量を削減することができる。
【００５９】
画素補間部１０４は、座標算出部１０３により算出された、入力画像内の各補間座標（x, y）の画素値を、入力画像内の整数座標の画素値から線形補間法（たとえば、バイリニア法）などの画素補間法を用いて算出する。そして、算出した入力画像内の各補間座標（x, y）の画素値を、出力画像の対応する座標の画素値にそれぞれ割り当てる。このように生成された出力画像は、第２記憶部１０５に一時記憶され、必要なタイミングで外部に出力される。
【００６０】
図７は、実施の形態１に係る画像処理装置１００の処理手順を示すフローチャートである。まず、区間設定部１３１は、出力画像の各ラインを分割すべき区間の幅Ｎを設定する（Ｓ１０１）。ここでは、Ｎ＝２５６とする。このとき、各区間における区間インデックスｉと開始点のｘ座標を、上記図６に示した値に設定する。続いて、変換行列算出部１０２は、上述した手法を用いて、上記式（８）に示した変換式内の変換行列を算出する（Ｓ１０２）。続いて、出力画像のｙ座標の値Yが０に設定される（Ｓ１０３）。続いて、先頭中間値算出部１３３は、各ラインにおけるx’, y’, wの初期値x’0, y’ 0, w0を計算し、中間値増分値算出部１３４は、区間単位のx’, y’, wの増分値Δx’hi, Δy’ hi, Δw hiを計算する（Ｓ１０４）。
【００６１】
図８は、図７のステップＳ１０４の詳細な処理手順を示すフローチャートである。まず、先頭中間値算出部１３３は、各ラインごとに、上記式（８）を用いて、最初の区間の開始点（0, Y）のx’, y’, wを算出する（Ｓ２０１）。それとともに、各ラインごとに、上記式（８）を用いて、その次の区間の開始点（256, Y）のx’, y’, wも算出する（Ｓ２０２）。続いて、中間値増分値算出部１３４は、次の区間の開始点（256, Y）のx’, y’, wから最初の区間の開始点（0, Y）のx’, y’, wをそれぞれ減算し、ある区間の開始点（X, Y）のx’, y’, wからその次の区間の開始点（X+256, Y）のx’, y’, wへの増分値Δx’hi, Δy’ hi, Δw hiを算出する（Ｓ２０３）。
【００６２】
図７に戻り、先頭中間値算出部１３３は、最初の区間の開始点（0, Y）のx’, y’, wを各ラインのx’, y’, wの初期値x’0, y’ 0, w0に設定する（Ｓ１０５）。続いて、先頭中間値算出部１３３は、区間インデックスiを０に設定する（Ｓ１０６）。続いて、非先頭中間値算出部１３５は、先頭区間以外の各区間の開始点のx’, y’, wを算出し、最終値算出部１３６は、各区間におけるx, yの初期値x0i, y0iを算出し、座標増分値算出部１３８は、画素単位のx, yの増分値Δxh, Δyhを計算する（Ｓ１０７）。
【００６３】
図９は、図７のステップＳ１０７の詳細な処理手順を示すフローチャートである。まず、区間インデックスｉが０の場合（Ｓ３０１のＮ）、ステップＳ３０２に進み、区間インデックスｉが１以上の場合（Ｓ３０１のＹ）、ステップＳ３０３に進む。ステップＳ３０２では、最終値算出部１３６は、各ラインごとに、上記式（９）、式（１０）により、最初の区間の開始点（0, Y）のx’, y’をそれぞれwで割り、最初の区間の開始点のx, yを算出し、ステップＳ３０３に進む。
【００６４】
ステップＳ３０３では、非先頭中間値算出部１３５は、現区間のx’, y’, wにそれぞれの増分値Δx’hi, Δy’ hi, Δw hiを加算し、次の区間の開始点（X+256, Y）のx’, y’, wを算出する。続いて、最終値算出部１３６は、次の区間の開始点（X+256, Y）のx’, y’ をそれぞれwで割り、次の区間の開始点（X+256, Y）のx, yを算出し、次の区間のx, yの初期値とする（Ｓ３０４）。座標増分値算出部１３８は、現区間の次の区間のx, yの初期値x0i, y0iから現区間のx,yの初期値x0i, y0iをそれぞれ減算することにより、区間単位のx,yの差分を算出する（Ｓ３０５）。続いて、座標増分値算出部１３８は、区間単位のx, yを現区間の画素数を除算することにより、画素単位のx, yの増分値Δxh, Δyhを算出する（Ｓ３０６）。この除算は、ビットシフトや指数の減算などにより実行する。
【００６５】
図７に戻り、座標増分値加算部１３９は、各区間ごとの開始点のｘ座標の値Xを出力画像のｘ座標の値Xに設定する（Ｓ１０８）。続いて、座標増分値加算部１３９は、各画素のx, yを算出する（Ｓ１０９）。
【００６６】
図１０は、ステップＳ１０９の詳細な処理手順を示すフローチャートである。まず、座標増分値加算部１３９は、出力画像のｘ座標の値Xが、現区間のXの初期値の場合（Ｓ４０１のＮ）、ステップＳ４０２に進み、座標増分値加算部１３９は、現区間の開始点（0, Y）にマッピングされるx, yを初期値に設定する。ステップＳ４０１にて、出力画像のｘ座標の値Xが現区間のXの初期値より大きい場合（Ｓ４０１のＹ）、ステップＳ４０３に進み、座標増分値加算部１３９は、x, yにそれぞれの増分値Δxh, Δyhを加算する。
【００６７】
図７に戻り、画素補間部１０４は、算出された補間座標（x, y）に相当する画素値を、入力画像から線形補間法などの画素補間法を用いて算出し、出力画像の対応する画素の座標（X,Y）の画素値に割り当てる（Ｓ１１０）。続いて、出力画像のｘ座標の値Xが一つ、インクリメントされる（Ｓ１１１）。現区間内の全画素の処理が終了するまで（Ｓ１１２のＮ）、ステップＳ１０９〜Ｓ１１１までの処理を繰り返す。現区間内の全画素の処理が終了したら（Ｓ１１２のＹ）、区間インデックスｉが一つ、インクリメントされる（Ｓ１１３）。
【００６８】
当該ライン内の全区間の処理が終了するまで（Ｓ１１４のＮ）、ステップＳ１０７からＳ１１３までの処理を繰り返す。当該ライン内の全区間の処理が終了したら（Ｓ１１４のＹ）、出力画像のｙ座標の値Yが一つ、インクリメントされる（Ｓ１１５）。全ラインの処理が終了するまで（Ｓ１１６のＮ）、ステップＳ１０４からＳ１１５までの処理を繰り返す。全ラインの処理が終了したら（Ｓ１１６のＹ）、本画像処理手順は終了となる。
【００６９】
以上説明したように実施の形態１によれば、入力画像を透視変換して出力画像を生成する際の演算量を低減することができる。すなわち、出力画像内の代表画素のみ、正規に算出し、非代表画素を線形補間により算出することにより、出力画像内の全画素を正規に算出する場合より、大幅に演算量（とくに、除算の回数）を削減することができる。また、代表画素間の区間の画素数を二の乗数に設定することにより、乗算および除算を、ビットシフトや指数の加減算で実現することができ、乗算および除算の回数を削減することができる。これにより、ハードウェアへの実装も容易になる。
【００７０】
また、一区間の幅を調整可能なことにより、演算量と画質のバランスを調整することができる。区間の幅を広げるほど、演算量は低減されるが、線形補間される画素が多くなるため画質が低下する。一方、区間の幅を狭めるほど、演算量は増大されるが、正規に算出される画素が多くなるため画質が向上する。このように、演算量と画質とはトレードオフの関係にある。
【００７１】
（実施の形態２）
図１１は、本発明の実施の形態２に係る画像処理装置１００の代表画素座標算出部１３２の構成を示すブロック図である。代表画素座標算出部１３２は、初期中間値設定部５３３、ライン中間値算出部５３４、区間中間値算出部５３５および最終値算出部１３６を含む。なお、実施の形態２に係る代表画素座標算出部１３２以外の構成要素は、実施の形態１と同様であるため、それらの説明は省略する。
【００７２】
実施の形態２では、代表画素座標算出部１３２は、先頭ラインの先頭区間の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wを変換式（上記式（８）参照）の定数を用いて求める。また、代表画素座標算出部１３２は、その他の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wを当該変換式の係数から求められる、それらの主走査方向および副走査方向の増分値を、順次加算することにより求める。また、代表画素座標算出部１３２は、出力画像内の各代表画素の座標に対応すべき入力画像内の各画素の座標を求めるためのx’, y’, wをもとに、当該入力画像内の各画素のｘ座標およびｙ座標の最終値を求める。
【００７３】
以下、より具体的に説明する。初期中間値設定部５３３は、先頭ラインの先頭区間の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wのそれぞれに、第１の一次方程式の定数C、第２の一次方程式の定数Fおよび第３の一次方程式の定数Rのそれぞれを設定する。
【００７４】
上述したように、第１の一次方程式は、X,Yを変数として含み、x’を算出するための式である（上記式（６）、式（８）参照）。第２の一次方程式は、X,Yを変数として含み、y’を算出するための式である（上記式（７）、式（８）参照）。第３の一次方程式は、X,Yを変数として含み、wを算出するための式である（上記式（６）〜式（８）参照）。
【００７５】
ライン中間値算出部５３４は、先頭ラインの先頭区間の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wのそれぞれに、第１の一次方程式のｙ座標変数の係数B、第２の一次方程式のｙ座標変数の係数Eおよび第３の一次方程式のｙ座標変数の係数Qのそれぞれを、副走査方向に順次加算する。これにより、先頭ライン以外のラインの先頭区間の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wをそれぞれ算出する。
【００７６】
区間中間値算出部５３５は、ラインごとに、先頭区間の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wのそれぞれに、第１の一次方程式のｘ座標変数の係数Aに一区間の画素数Ｎを掛けた値、第２の一次方程式のｘ座標変数の係数Dに一区間の画素数Ｎを掛けた値および第３の一次方程式のｘ座標変数の係数Pに一区間の画素数Ｎを掛けた値のそれぞれを、主走査方向に順次加算する。これにより、先頭区間以外の区間の代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wをそれぞれ算出する。
【００７７】
最終値算出部１３６は、初期中間値設定部５３３、ライン中間値算出部５３４および区間中間値算出部５３５により求められた各代表画素の座標に対応すべき入力画像内の画素の座標を求めるためのx’, y’, wをもとに、x, yを算出する。
【００７８】
以下、実施の形態２に係る代表画素座標算出部１３２の処理を、上記図５、図６に則した例で説明する。初期中間値設定部５３３およびライン中間値算出部５３４は、出力画像の各ラインにおける開始点（すなわち、各ラインの最も左の画素）（0, Y）のx’, y’, wの初期値x’0, y’ 0, w0をそれぞれ算出する。すなわち、各ラインにおけるx’, y’, wの初期値x’0, y’ 0, w0を算出する。この際、実施の形態１では、上記式（８）用いて各ラインにおけるx’, y’, wの初期値x’0, y’ 0, w0を算出した。この点、実施の形態２では、あるラインにおけるx’, y’, wの初期値x’0, y’ 0, w0に、その次のラインへのx’, y’, wの増分値Δx’v, Δy’ v, Δw vをそれぞれ加算することにより、その次のラインにおけるx’, y’, wの初期値x’0, y’ 0, w0を求める。これにより、実施の形態２では実施の形態１より乗算の回数を削減することができる。
【００７９】
なお、初期中間値設定部５３３は、全ラインのx’, y’, wの初期値x’0, y’ 0, w0の初期値、すなわち、最初のラインのx’, y’, wの初期値x’0, y’ 0, w0に、上記式（８）に示した変換式内の変換行列の３列目の各係数C,F,Rの値をそれぞれ設定する。また、ライン中間値算出部５３４は、x’, y’, wの増分値Δx’v, Δy’ v, Δw vに、当該変換行列の２列目の各係数B,E,Qの値をそれぞれ用いる。
【００８０】
区間中間値算出部５３５は、あるラインにおいて、ある区間の開始点（N*i, Y）のx’, y’, wから水平方向に進んだその次の区間の開始点（N*(i+1), Y）のx’, y’, wへの増分値Δx’hi, Δy’ hi, Δw hiを算出する。区間中間値算出部５３５は、これら増分値Δx’hi, Δy’ hi, Δw hiを次のように算出する。すなわち、上記変換行列の１列目の各係数A, D, Pの値のそれぞれに、区間の幅Ｎ（画素数）を掛けて算出する。
【００８１】
なお、区間の幅Ｎに二の乗数が設定されている場合、乗算の代わりに、ビットシフトや指数部の加算により、上記増分値Δx’hi, Δy’ hi, Δw hiを算出することができる。たとえば、区間の幅Ｎが２５６に設定されている場合にて、整数演算や固定小数点演算では、数値を左に８ビットシフトさせる。また、ＩＥＥＥ７５４方式などによる浮動小数点演算では、指数部の値に８を足す。なお、指数部は２を基数としている。
【００８２】
区間中間値算出部５３５は、出力画像の各区間における開始点（すなわち、各区間の最も左の画素（N*i, Y））のx’, y’, wの初期値x’0i, y’ 0i, w0iをそれぞれ算出する。すなわち、各区間におけるx’, y’, wの初期値x’0i, y’ 0i, w0iを算出する。区間中間値算出部５３５は、ある区間のx’, y’, wの初期値x’0i, y’ 0i, w0iに、x’, y’, wの増分値Δx’hi, Δy’ hi, Δw hiをそれぞれ加算することにより、その次の区間のx’, y’, wの初期値x’0i, y’ 0i, w0iを算出する。
【００８３】
なお、各ラインの開始点（0, Y）は各ラインの最初の区間の開始点でもある。したがって、各ラインの最初の区間のx’, y’, wの初期値x’0i, y’ 0i, w0iには、各ラインにおけるx’, y’, wの初期値x’0, y’ 0, w0を設定する。もちろん、上記式（８）を用いて行列の積和演算によりx’, y’, wを直接算出してもよいが、本実施の形態では増分値の加算により乗算回数を減らしている。
【００８４】
最終値算出部１３６は、出力画像の各区間における開始点（すなわち、各区間の最も左の画素（N*i, Y））のx, yの初期値x0i, y0iを算出する。すなわち、各区間におけるx, yの初期値x0i, y0iを算出する。より具体的には、最終値算出部１３６は、各区間ごとに、上記式（９）、式（１０）を用いて、各区間の開始点のx’ 0i, y’ 0iをそれぞれw0iで割り、各区間の開始点のx, yの初期値x0i, y0iを算出する。
【００８５】
図１２は、実施の形態２に係る画像処理装置１００の処理手順を示すフローチャートである。まず、区間設定部１３１は、出力画像の各ラインを分割すべき区間の幅を設定する（Ｓ５０１）。ここでは、Ｎ＝２５６とする。このとき、各区間における区間インデックスｉと開始点のｘ座標を、上記図６に示した値に設定する。続いて、変換行列算出部１０２は、上述した手法を用いて上記式（８）に示した変換式内の変換行列を算出する（Ｓ５０２）。続いて、出力画像のｙ座標の値Yが０に設定される（Ｓ５０３）。これは、画面内の上から０番目のラインの画素を補間することを意味している。
【００８６】
続いて、初期中間値設定部５３３は、当該変換行列の３列目の係数C,F,Rを、各ラインにおけるx’, y’, wの初期値x’0, y’ 0, w0の、最初のラインの値として設定する（Ｓ５０４）。すなわち、これら係数C,F,Rの値は、最初のラインの最初の区間におけるx', y', wの初期値x’i 0, y’ i 0, wi 0となる。
【００８７】
続いて、ライン中間値算出部５３４は、ある区間の開始点（N*i, Y）のx', y', wからその次の区間の開始点（N*(i+1), Y）のx', y', wへの増分値Δx’hi, Δy’ hi, Δw hiを算出する（Ｓ５０５）。具体的には、上記変換行列の１列目の各係数A,D,Pに区間の幅Ｎを掛けることにより算出する。なお、この乗算は、区間の幅Ｎの値が２の乗数であれば、ビットシフトまたは指数部の加算により演算することができる。
【００８８】
続いて、ライン中間値算出部５３４は、各ラインにおけるx’, y’, wの初期値x’0, y’ 0, w0を、各ラインの最初の区間のx’, y’, wの初期値x’0i, y’0i, w0iとして設定する（Ｓ５０６）。続いて、区間インデックスiが０に設定される（Ｓ５０７）。続いて、ライン中間値算出部５３４は、各区間におけるx, yの初期値x0i, y0iを算出し、画素単位でのx, yの増分値Δxh, Δyhを算出する（Ｓ５０８）。このステップＳ５０８の詳細な処理手順は、図９に示したフローチャートと同様の処理手順となる。
【００８９】
続いて、座標増分値加算部１３９は、出力画像のｘ座標の値Xを、各区間の開始点（N*i, Y）のｘ座標の値（すなわち、（N*i））に設定する（Ｓ５０９）。続いて、座標増分値加算部１３９は、各画素のx, yを算出する（Ｓ５１０）。このステップＳ５１０の詳細な処理手順は、図１０に示したフローチャートと同様の処理手順となる。
【００９０】
続いて、画素補間部１０４は、算出された補間座標（x, y）に相当する画素値を、入力画像から線形補間法などの画素補間法を用いて算出し、出力画像の対応する画素の座標（X,Y）の画素値に割り当てる（Ｓ５１１）。続いて、出力画像のｘ座標の値Xが一つ、インクリメントされる（Ｓ５１２）。これは、次に画面の左からX番目の右隣の画素を補間することを意味している。
【００９１】
続いて、現区間内の全画素の処理が終了していなければ（Ｓ５１３のＮ）、次の画素、すなわち、右隣の画素の処理を開始し（Ｓ５１０）、現区間内の全画素の処理が終了するまで、ステップＳ５１０からＳ５１２までの処理を繰り返す。現区間内の全画素の処理が終了したら（Ｓ５１３のＹ）、区間インデックスiが一つ、インクリメントされる（Ｓ５１４）。これは、次に画面の左からＸ番目の区間の右隣の区間を補間することを意味している。
【００９２】
続いて、区間中間値算出部５３５は、次の区間の演算を行うために、次の区間のx’, y’, wの初期値x’ ni, y’ ni, wniを、x’0i, y’0i, w0iに設定する（Ｓ５１５）。現ライン内の全区間の処理が終了していなければ（Ｓ５１６のＮ）、次の区間（すなわち、右隣の区間）の処理を開始し（Ｓ５０８）、現ライン内の全区間の処理が終了するまで、ステップＳ５０８〜Ｓ５１５までの処理を繰り返す。現ライン内の全区間の処理が終了したら（Ｓ５１６のＹ）、出力画像のｙ座標の値Yが一つ、インクリメントされる（Ｓ５１７）。これは、次に画面の上からY番目のラインの一つ下のラインの画素を補間することを意味している。
【００９３】
続いて、ライン中間値算出部５３４は、現ラインのx’, y’, wの初期値x’0, y’0, w0に、上記変換行列の２列目の係数B,E,Qの値をそれぞれ加算し、次のラインのx’, y’, wの初期値x’0, y’ 0, w0を算出する（Ｓ５１８）。ここでは、当該変換行列の２列目の係数B,E,Qの値をそれぞれ、あるラインのx’, y’, wの初期値x’0, y’ 0, w0から、その次のラインのx’, y’, wの初期値x’0, y’ 0, w0への増分値Δx’v, Δy’ v, Δw vを示す値として用いている。
【００９４】
続いて、全ラインの処理が終了していなければ（Ｓ５１９のＮ）、次のライン（すなわち、一つ下のライン）の処理を開始し（Ｓ５０４）、全ラインの処理が終了するまで、ステップＳ５０４〜Ｓ５１８までの処理を繰り返す。全ラインの処理が終了したら（Ｓ５１９のＹ）、本画像処理手順は終了となる。
【００９５】
以上説明したように実施の形態２によれば、実施の形態１と同様の効果を奏する。実施の形態２では、代表画素のx’, y’, wを算出する際、上記変換行列内の係数および定数を用いることにより、実施の形態１と比較し、さらに演算量を削減することができる。
【００９６】
以上、本発明をいくつかの実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００９７】
たとえば、区間設定部１３１は、上記区間の幅Ｎを適応的に変化させてもよい。たとえば、水平方向の画素数が大きい場合、上記区間の幅Ｎを広げる。また、処理負荷が所定の閾値を超えたとき（たとえば、コマ落ちしたとき）、上記区間の幅Ｎを広げる。また、区間設定部１３１は、ユーザ操作に起因して上記区間の幅Ｎを適応的に変化させてもよい。ユーザから画質を上げたい旨の指示が入力された場合、上記区間の幅Ｎを狭める。
【符号の説明】
【００９８】
１００  画像処理装置、  １０１  第１記憶部、  １０２  変換行列算出部、  １２１  対応点座標算出部、  １２２  連立方程式算出部、  １０３  座標算出部、  １３１  区間設定部、  １３２  代表画素座標算出部、  １３３  先頭中間値算出部、  １３４  中間値増分値算出部、  １３５  非先頭中間値算出部、  １３６  最終値算出部、  １３７  非代表画素座標算出部、  １３８  座標増分値算出部、  １３９  座標増分値加算部、  １０４  画素補間部、  １０５  第２記憶部、  ５３３  初期中間値設定部、  ５３４  ライン中間値算出部、  ５３５  区間中間値算出部。
【図１】
0005387288.tif 000013
【図２】
0005387288.tif 000014
【図３】
0005387288.tif 000015
【図４】
0005387288.tif 000016
【図６】
0005387288.tif 000017
【図７】
0005387288.tif 000018
【図８】
0005387288.tif 000019
【図９】
0005387288.tif 000020
【図１０】
0005387288.tif 000021
【図１１】
0005387288.tif 000022
【図１２】
0005387288.tif 000023
【図５】
0005387288.tif 000024