(57)【要約】【課題】少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理を高速で安価に実現すること。【解決手段】  画像処理装置は、部分画像を格納する読み取り用バッファを制御する第１バッファ制御部と、読み取り用バッファに格納された部分画像を、出力座標の位置に順次変換する変換部と、変換部により出力座標の位置に変換された部分画像を格納する書き込み用バッファを制御する第２バッファ制御部と、を備える。【選択図】  図１
2008192073.tif 000002
【特許請求の範囲】
【請求項１】
部分画像を格納する第１格納手段を制御する第１バッファ制御手段と、
前記第１格納手段に格納された前記部分画像を、出力座標の位置に順次変換する変換手段と、
前記変換手段により出力座標の位置に変換された部分画像を格納する第２格納手段を制御する第２バッファ制御手段と、
を備えることを特徴とする画像処理装置。
【請求項２】
前記部分画像と、当該部分画像の座標情報とを入力する画像入力手段を更に備え、
前記第１格納手段は、前記画像入力手段により入力された前記部分画像と当該部分画像の座標情報とを、前記第１バッファ制御手段の制御により格納することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
圧縮された画像を伸張して出力する圧縮画像伸張手段を更に備え、
前記第１格納手段は、前記圧縮画像伸張手段により伸張された画像の部分画像と、当該部分画像に関する座標情報とを、前記第１バッファ制御手段の制御により格納することを特徴とする請求項１に記載の画像処理装置。
【請求項４】
入力された部分画像の中で、画像処理すべき部分画像の座標範囲の情報を保持する入力領域保持手段を更に備え、
前記第１バッファ制御手段は、前記座標範囲の情報に基づき、前記入力された部分画像の座標が前記画像処理すべき部分画像の座標範囲に含まれるか判定し、
前記第１バッファ制御手段は、前記判定に基づいて、前記入力された部分画像の座標が前記画像処理するべき部分画像の座標範囲に含まれている場合に、前記第１格納手段に、前記部分画像を書き込むように制御することを特徴とする請求項１に記載の画像処理装置。
【請求項５】
出力すべき領域の座標範囲の情報を保持する出力領域保持手段を更に備え、
前記第２バッファ制御手段は、前記変換手段により出力される出力画像の位置情報が、前記出力すべき領域の座標範囲に含まれているか判定し、
前記第２バッファ制御手段は、前記判定に基づいて、前記出力画像の位置情報が前記出力すべき領域の座標範囲に含まれている場合に、前記第２格納手段に、前記出力画像を書き込むように制御することを特徴とする請求項１に記載の画像処理装置。
【請求項６】
第１バッファ制御手段が、部分画像を格納する第１格納手段を制御する第１バッファ制御工程と、
変換手段が、前記第１格納手段に格納された前記部分画像を、出力座標の位置に順次変換する変換工程と、
第２バッファ制御手段が、前記変換工程により出力座標の位置に変換された部分画像を格納する第２格納手段を制御する第２バッファ制御工程と、
を備えることを特徴とする画像処理装置の制御方法。
【請求項７】
請求項６に記載の画像処理装置の制御方法をコンピュータに実行させることを特徴とするプログラム。
【請求項８】
請求項７に記載のプログラムを格納したことを特徴とするコンピュータ可読の記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像処理技術に関するものである。
【背景技術】
【０００２】
画像処理の出力側でラスタ走査順となるように画像データを処理するためには、入力側で画像データにランダムアクセスすることが必要なる（この変換方式を逆変換方式という）。出力座標系から逆変換を行って入力座標系上での処理領域を求めて画像処理を行う技術としては、例えば、特許文献１に示されるものがある。特許文献１においては、逆変換と順変換は、変換方式の選択として説明されている。
【特許文献１】特開平１１−１５４２２８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、逆変換と順変換は、選択により何れの変換も実行することが可能とは限らない。一般的な１次変換式によるアフィン変換の場合、変換行列は必ずしも逆行列を持つとは限らないためである。逆変換を行う場合には、逆行列が存在しない場合の処理を必ず入れなければならず、そのときだけ処理が切り替わることにより、処理時間が変動してしまうなど、逆変換による画像処理には逆変換処理上の問題がある。
【０００４】
また、図１８に示すように、画像中の一部分を回転しながら取り出すような変換を行う場合として、例えば、入力画像中１８０１にある領域１８０２を回転して出力する場合を考える。出力バッファに一度に入るバッファサイズを領域１８０３とすると、その幅サイズ１８０４と高さサイズ１８０５とを含む入力データとして必要な領域のサイズは高さサイズ１８０６として示される。このように、回転角度が大きいほど、一度に保持しなければならない入力画像の範囲（サイズ）は大きくなる。
【０００５】
特許文献１では、入力として必要な画像をライン単位で入力し、図１８の参照番号１８０７に示すような範囲の局所データを読み取るだけのデータがたまるまで入力ラインの画像データをためる処理を行う技術を開示している。そのため、回転変倍処理には、大きな入力バッファサイズが必要になる。
【０００６】
例えば、画像の横幅をＡ４サイズ６００ｄpiとして考えると、１ラインが５０００画素以上になることから、４５度の回転を想定しても、５０００／√２、すなわち３５３５ライン分のデータを保持しなければならない。この場合、１画素を３バイトで保持したとすると５０００×３×３５３５＝約５０ＭＢのメモリ量となり、巨大なメモリが必要となる。
【０００７】
こうした問題を回避するために入力側の画像を圧縮して保持することが考えられる。圧縮率１０倍の圧縮方法を使用すれば、５０ＭＢのデータを５ＭＢという比較的現実的なサイズに抑えることが可能である。しかし、この場合も逆変換方式では入力データを斜めに横切るように読まなければならないため、圧縮データの並びに逆らった読み方となり、結果として読み出しに要する時間がかかりすぎて高速に処理を実施することができないという問題がある。特に、ＪＰＥＧ、ＰＮＧ、ＴＩＦＦ等のように、カラム方向にピクセルないしはブロック単位で移動しながら圧縮する画像圧縮方法では、斜めに読むことに対する負荷が非常に大きく、現実に利用することが困難であるという問題がある。
【０００８】
更に、アドレス変換ＲＯＭによって回転を行う技術が特許文献１に開示されており、アフィン変換を行う場合には、回転・変倍の他に更に平行性を保った形での変形が可能である。回転・変倍等の全てのケースに対応するには、２×２又は３×３の変換マトリクスの個々の係数の全ての値の組み合わせに対してアドレス変換テーブルをＲＯＭ化しなければならず、実際には実現困難であるという問題がある。
【０００９】
近年標準化されたＳＶＧ（Scalable Vector graphics）規格などでは、回転、変倍などのほかにアフィン変換行列の係数を個々に自由に指定することが可能である。ＳＶＧ規格への応用においてはＲＯＭ化テーブルは必ずしも安価・高速に処理を実行するための有効な手段とならない場合があるという問題がある。
【００１０】
上記問題を鑑み、本発明は、少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理等を高速で安価に実現する画像処理技術の提供を目的とする。
【課題を解決するための手段】
【００１１】
上記の従来技術を解決するべく、本発明に係る画像処理装置は、部分画像を格納する第１格納手段を制御する第１バッファ制御手段と、
前記第１格納手段に格納された前記部分画像を、出力座標の位置に順次変換する変換手段と、
前記変換手段により出力座標の位置に変換された部分画像を格納する第２格納手段を制御する第２バッファ制御手段と、
を備えることを特徴とする。
【発明の効果】
【００１２】
本発明によれば、少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理を高速で安価に実現する画像処理技術の提供が可能になる。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照して、本発明の好適な実施形態を例示的に詳しく説明する。ただし、この実施の形態に記載されている構成要素はあくまで例示であり、本発明の技術的範囲は、特許請求の範囲によって確定されるのであって、以下の個別の実施形態によって限定されるわけではない。
【００１４】
（第１実施形態）
図１は、本発明の実施形態に係る画像処理装置が備える構成要素を示す図である。画像入力部１０１は画像データ、画像データの座標情報を入力する。画像入力部１０１は単純なメモリアクセスやハードディスクアクセス、ないしはネットワークアクセスにより画像データ、座標情報を取得することも可能である。
【００１５】
画像処理装置の構成としては、画像データを取得する画像入力部１０１の他、圧縮画像伸張部１５０１を設ける構成でもよい。図１５に示す構成によれば、回転・変倍・変形処理の前に、圧縮画像伸張部１５０１は、圧縮された画像を伸張して出力することが可能である。その場合、回転、変倍、変形処理は、高々数ピクセルの入力単位で処理が可能であるので、特別なバッファなしに、画素（ピクセル）単位、またはブロック単位の部分画像と、その座標情報と、の受け渡しを直接行うようにすることも可能である。符号化方式として、例えば、ＤＣＴ、ＤＦＴ、ＤＳＴ、ＬＯＴ、アダマール変換、Ｗａｖｅｌｅｔ変換、サブバンド符号化、ランレングス符号化、ＬＺＷ符号化、ハフマン符号化またはこれらの組み合わせを利用することが可能である。
【００１６】
読み出し用バッファ１０２は、画像入力部１０１から入力された画像データを保持するバッファである。読み出し用バッファ１０２は、部分画像を格納する第１格納部として機能することが可能である。
【００１７】
読み出し用バッファ制御部１０３は、入力された画像データのうち局所データ（部分画像）を格納する読み出し用バッファ１０２（第１格納手段）を制御する。読み出し用バッファ制御部１０３は、読み出し用バッファ１０２（第１格納部）を制御する第１バッファ制御部として機能することが可能である。
【００１８】
読み出し用バッファ制御部１０３は処理に必要な画像データを、局所データ（部分画像）として、読み出し用バッファ１０２（第１格納部）に保持させるように不要な画像データを削除したり、新たな画像データを保持させたりする制御が可能である。また、読み出し用バッファ制御部（第１バッファ制御部）１０３は、必要に応じて、読み出し用バッファ１０２（第１格納部）における画像データの保持位置をシフトさせるなどの並べ替えを行うことも可能である。
【００１９】
局所データ変換部１０４は、読み出し用バッファ制御部（第１バッファ制御部）１０３によって並べ替えられた入力画像の局所データ（部分画像）を順変換により、出力座標の位置に順次変換する座標変換を行い出力することが可能である。
【００２０】
局所データ出力アドレス計算部１０５は、局所データ（部分画像）から、順変換による座標変換で必要となる出力座標点を算出することが可能である。
【００２１】
順変換座標算出部１０６は、局所データ出力アドレス計算部１０５に、入力座標位置と変換マトリクスによって順変換方式で出力座標位置を求めることが可能である。
【００２２】
一般的な画像処理においては、画像データはラスタ走査順に処理され、その画像処理結果はラスタ走査順に出力される。これに対して、回転処理は、入力側と出力側でデータの入出力の順番が異なる。入力側からラスタ走査順に画像データが入力され、回転された画像データは、回転角に従った傾きの方向に書き込まれることになる。このため、出力側では、入力順とは異なる書き込み用バッファ１０７へのアクセス（ランダムアクセス）が必要となる。この変換方式を以下、順変換方式という。
【００２３】
書き込み用バッファ１０７は、局所データ変換部１０４により変換された出力用画像データを保持する。読み出し用バッファ１０２（第１格納部）に格納された部分画像（局所データ）は、局所データ変換部１０４により出力座標の位置に変換され、書き込み用バッファ１０７に格納される。書き込み用バッファ１０７は、出力座標の位置に変換された部分画像を格納する第２格納部として機能することが可能である。
【００２４】
書き込み用バッファ制御部１０８は、書き込み用バッファ１０７（第２格納部）に効率よく出力データを保持させるための書き込みアドレスの制御を行う。書き込み用バッファ制御部１０８は、出力座標の位置に変換された部分画像を格納する第２格納部を制御する第２バッファ制御部として機能することが可能である。
【００２５】
画像出力部１０９は、書き込み用バッファ１０７（第２格納部）に保持された出力用画像データを適宜、外部処理モジュールまたは外部メモリに出力する。
【００２６】
（順変換による局所データの変換処理）
順変換による局所データの変換処理について図２を参照して説明する。図２では、入力画像が画素（ピクセル）単位に、矢印２５０で示す横方向に順次入力されてくるようなデータの流れを想定している。図２（ａ）に示すように、４画素を一度に処理することで処理回数を減らし、なおかつ読み出し用バッファ１０２（第１格納部）、書き込み用バッファ１０７（第２格納部）上での読み書き回数を低減させることができる。
【００２７】
横方向の画素（ピクセル）４点２１０〜２１３に基づき出力される出力画素として、図２（ａ）中のＡで示した領域に含まれる画素に限定することで、処理を簡素化しつつ、出力バッファ上での読み書きの回数を低減させるこがきる。
【００２８】
原理的には、４点（４画素）全てが関与する範囲である図２(ａ)中にＢで示す範囲に対して出力値を算出することが可能である。その場合、出力値に対する画素の関与の比率が出力画素ごとに異なってしまい、一律の処理によって出力値の算出処理を進めることが不可能になる。よって、本実施形態では、入力４点（４画素）に対してＡで示した領域についてのみ出力を行うものとする。図中の「○」は出力画素を例示的に示すものである。
【００２９】
次に、図２（ｂ）に示すように、次の画素が１点（１画素分）入ってきたところで、最初に入力された画素を記憶領域から破棄し、新たに入力された１画素を含む４点（４画素）を保持することで同様の出力値の計算を行う。そして、図２（ｂ）中Ｃで示す範囲に含まれる出力座標点への出力を行う。このようにして、１ラスタ目の画像入力については１ピクセルの入力毎に４点という非常に少ない保持データにより、順次出力画素を出力する。
【００３０】
次に、図２（ｃ）に示すように２ラスタ目の処理に移ると、４点により出力できる領域が上方向にもあることになるため、図中に領域Ｄに示すような領域に含まれる出力座標点への出力を行う。
【００３１】
２ラスタ目についても１ラスタ目と同様、図２（ｄ）に示すとおり次のピクセルが入力されたところで最初のピクセルを破棄し、新たな４点（４画素）について同様の処理を行うことで、順次処理を進めていくことができる。
【００３２】
その後、図２（ｅ）、（ｆ）に示すように３ラスタ目、４ラスタ目と順次同様の処理を繰り返していくことで、出力画素を生成することが可能である。
【００３３】
画像の下端については、図２(ａ)〜図２（ｄ）に示した領域をちょうど上下反転したように処理することで、入力画像の境界部分での出力処理を境界以外の他の処理と同様に行うことが可能になる。一定の透過率による画像合成を行う場合には、予め出力バッファ上に描画されている画像をピクセル単位で読み出し、透過率によって決まる係数を掛けて書き戻しておくことにより、合成画像を得ることも可能である。
【００３４】
次に、処理をより高速に実現するにあたって、画像上端・下端を除いた一般的な処理において、バッファ上での読み書き回数を減らすために最低限必要なバッファの構成について図３を用いて説明する。
【００３５】
例えば、本実施形態の処理をキャッシュメモリなどのローカルバッファを持つハードウェアないしはＣＰＵにおいて実現することも可能である。この場合、図３で示した領域に含まれる出力座標点分のサイズのローカルバッファを持つことにより、効果的に外部メモリへの書き込み回数を減らすことが可能である。この場合、バッファのサイズは、変倍率などによって変動する。拡大処理を行う場合、図中の領域に含まれる出力座標点は多くなり、縮小の場合には少なくなるからである。
【００３６】
一般にローカルバッファのサイズには実装コスト上の制約があるため、変倍率に対しても制限が必要となる。しかし、本実施形態によれば、ローカルバッファに入らない領域の出力座標点については直接外部メモリに出力しておき、その後の処理時に再度読み出して処理をすればよく、ローカルバッファに全ての出力座標点の情報が含まれる必要はない。ローカルバッファの上限を超える変倍率を指定した際には、変倍率の増加に対して単調増加の傾向で処理負荷が重くなるだけであり、高速化と柔軟性を比較的制御性の良い形で両立することも可能である。
【００３７】
また、ローカルバッファの構成では、画素が連続して入力される横方向の画素数分、ローカルバッファの幅を持つ必要がある。これを効果的に小さくするための方法について図４を用いて説明する。図４（ａ）中の参照番号４０１は、図２で示した入力されるデータの入力順を概略的に示している。このようにラスタ単位でデータを処理する場合、入力されるデータの入力順は参照番号４０１にようになる。この場合、多くの画像処理に対して適用可能であるが、反面、本実施形態で用意するべきバッファの容量は、図４中の参照番号４０２で示すように大きくなってしまう。
【００３８】
これに対して、画像をバンド単位に処理する場合、画素の入力方向を縦方向にすることで、回転処理で必要となるローカルバッファの領域を９０度回転させたものとすることができ、結果としてローカルバッファのサイズを小さく抑えることが可能である。
【００３９】
次に、画像の回転を行う場合の局所データ変換部１０４の処理について図５を用いて説明する。回転においては、例えば、図２(ｅ)の領域Fに、斜めに出力画素が並ぶことになる。この場合には、参照番号５０１に示した点に対してそれぞれ計算を行ったうえで積算処理を行う必要があるが、処理としてはこれまでに説明した処理と同様である。例えば、１６点の補間の処理であっても、４画素（ピクセル）という非常に少ない入力画像の局所データの保持で、かつ、効率的な回転変倍を行うことができる。
【００４０】
ただし、これだけでは、アフィン変換のための乗算処理を複数行う必要があるなど、ハードウェア化においては回路規模が大きくなる要素を残している。そこで、出力座標範囲と、その中に含まれる実際に出力を行うべき出力座標点の集合を簡単な演算で実施する構成を以下に説明する。
【００４１】
アフィン変換と呼ばれる行列演算による変形では、「平行な直線は変換後も平行である」という性質を持っていることが知られている。このことは、すなわち直線によって囲まれた領域を変形する場合には、領域を囲む平行でない直線の数だけの傾き情報の変換によって図形の変換が可能であることを示している。
【００４２】
こうしたことからアフィン変換における変換パラメータは、行列演算から求められる入力座標系の整数位置の単位移動量に対する変換後の単位移動量、すなわち傾きとして求められることになる。
【００４３】
アフィン変換は、入力座標を(x,y)、出力座標を(X,Y)とすると、以下のように表される。
【００４４】
【数１】
2008192073.tif 000003
【００４５】
ここで、デジタル画像処理では入出力座標位置は整数で表される位置に離散化されていることから、例えば(x,0)という点は、この式によって(ax+c,dx+f)という位置に写像される。
【００４６】
【数２】
2008192073.tif 000004
【００４７】
更に、x＋１という位置は、下式に示すように(ax+c+a,dｘ+f+d)という位置に写像されることになる。
【００４８】
【数３】
2008192073.tif 000005
【００４９】
（３）式より明らかなように、入力座標系での隣の画素位置への移動は、出力座標系での(a,d)という傾きを持った移動となる。アフィン変換によって行われる座標変換は、入力座標系での一定の移動量は、出力座標系では変換された傾きを持った移動量となる事がわかる。このことから、アフィン変換では入力座標上のある点の変換座標と、そこからの移動量を傾きとして与えることで、変換後の出力位置を簡便に求められる可能性があることが分かる。
【００５０】
逆行列が存在しない行列式による変換の場合には、入力画像上で互いに平行でなかった直線が平行になってしまったり、１点に集約されてしまったりするなどの現象が起きる。こうした場合には、ある１点の出力座標に対応する入力座標位置が無数に存在してしまうため、逆変換によって入力座標位置を求めることは単なる計算だけでは行えなくなる。このような場合でも、変換前には異なる傾きを持った直線が、変換後には同じ傾きを持つようになるというだけであり、その変換は傾きの変換によって行える。
【００５１】
図６は、順変換により回転・変形・変倍を行った場合の座標値の簡便な求め方を説明する図である。アフィン変換による座標変換は、出力画像座標系に対して、入力画像座標が軸の平行性を保った形で写像される。入力座標系の座標点を白丸で示すと、正方形として配置する座標点は、アフィン変換を行うことにより、一般的に、黒丸で座標点を示す平行四辺形の配置に写像される。入力座標系のＸ座標、Ｙ座標は、出力座標系でそれぞれｄ／ａ、ｅ／ｂの傾きを持つ直線に写像されることになる。
【００５２】
これにより、矩形領域を持つ画像の回転・変倍・変形処理を簡素化して行うことが可能になる。図７は、アフィン変換による回転・変倍・変形処理を行う場合の設定パラメータについて説明した図である。
【００５３】
図７中に黒丸で示したのが出力座標上の画素点であり、四角で示したのが入力座標系の画素点である。入力画像の処理開始点を出力座標上に写像した位置(StartX, StartY)を基点とする。
【００５４】
入力画像の点の出力座標上の配置は入力座標のＸ軸、Ｙ軸が出力座標系上で持つ傾き(rate_x, rate_y)、(line_rate_x, line_rate_y)とを算出して求めることが可能である。
【００５５】
アフィン変換による変倍後の座標計算は、(StartX, StartY), (rate_x, rate_y), (line_rate_x, line_rate_y)の６つのパラメータによって置き換えることが可能である。
【００５６】
６つのパラメータは、アフィン変換を表現するための基本的なものであるが、これだけでは出力座標上の画素位置を求めることが困難である。なぜなら、入力画像の画素位置は、出力画像の画素位置の途中、つまり小数点以下の値を含む位置に一般に写像されるからである。出力画像を正しく求めるためには、こうした小数点を含む位置から整数によって表される出力座標格子点を求める計算を行わなければならない。
【００５７】
このパラメータの与え方について、図８を用いて説明する。先に与えられた６つのパラメータから直線line1、line2、line3を求める。そして、出力座標系のＹ座標整数位置にある水平線との交点（図８の（CstartX1,CstartY1）、（CstartX2, CstartY2）および（CendX1,CendY1）、（CendX2, CendY2））を算出する。
【００５８】
これは、ハードウェアで行うためには乗算器を含む比較的回路規模の大きな演算処理を必要とするため、安価な実施には不適当であるが、ソフトウェアによってあらかじめ求めることは実装上の負荷とはならない。これらの交点座標を初期値として与え、その後は傾きの情報を加算することで順次出力座標の範囲を求めることが可能である。これにより、ハードウェア実装負荷の低い加算器のみを用いてアフィン変換の順変換座標算出部を実施することが可能となり、安価な構成で、かつ高速な処理の実行が可能となる。
【００５９】
図８のように、最初に入力される４点についての座標位置として（StartX,StartY）、（EndX, EndY）、（EndLineX, EndLineY）、（EndRectX, EndRectY）を求める（矩形範囲８０１）。これらはそれぞれ、所望のアフィン変換行列をかけることで求めることが可能である。
【００６０】
n×mの参照点を持つフィルタの場合、ｎとｍから求められる係数cn1,cn2,cm1,cm2により(x+cn1, y-cm1),(x+cn2, y-cm1),(x+cn1, y+cm2),(x+cn2, y+cm2)を求めることができる。cn1,cm1,cn2,cm2は、単純にn/2-1, m/2, n/2, m/2となるのが基本となる。
【００６１】
しかしながら、フィルタサイズｎ、ｍは必ずしも偶数であるとは限らないことから、cn1,cn2,cm1,cm2が常にこのような単純な式で求められるとは限らない。また、入力画像の上端、下端、左端、右端においては、さらにこのcn1,cn2,cm1,cm2を図２に示したように変化させる制御を行う必要がある。但し、入力画素をn,mを考慮して画像の外に当たる部分も供給するなどの方法によって、処理に必要な画像を補うことで、こうした出力領域の制御を行わないように構成することも可能である。
【００６２】
こうして求められた矩形範囲８０１について、（StartX, StartY）を基点として画像を処理する方向で最も近い出力座標系で整数位置を持つ水平線（line5）との交点を求める。(CstartX1,CstartY1)は、先に述べた（EndLineX,EndLineY）から（rate_x,rate_Y）の傾きによって伸びる直線line1と、line5の交点である。この点は、出力座標上でY座標は整数位置にあるが、X座標は小数点以下の値を持つ位置になる。以下同様に、(CstartX2,CstartY2)は、（StartX,StartY）からline_rate_y  /  line_rate_x  の傾きで伸びる直線line2とline5の交点である。（CendX1,CendY1）は（EndX,EndY）からline_rate_y/line_rate_xの傾きで伸びる直線line3とline5の交点である。
【００６３】
(StartX,StartY),(EndX, EndY),(EndLineX,EndLineY),(EndRectX, EndRectY)を出力座標領域算出の初期値として与える。その後は傾きの情報を加算することで順次出力座標における局所データの変換を求めることが可能になる。
【００６４】
本実施形態の出力座標算出処理の流れを図９のフローチャートを参照して説明する。本処理は、局所データ変換部１０４、局所データ出力アドレス計算部１０５、順変換座標算出部１０６の制御の下に実行することが可能である。
【００６５】
出力座標位置算出処理が開始されると、ステップＳ９０１で、入力座標CstartX1,CstartX2のうち、X座標の値が大きいほうを選択し、CstartXとする。
【００６６】
ステップＳ９０２において、入力座標CendX1,CendX2のうち、X座標の小さいほうを選択し、CendXとする。
【００６７】
ステップＳ９０３において、CstartY1,CstartY2, CendY1, CendY2は、全ての点について同じ値となるため、いずれかのCYを決定する。
【００６８】
ステップＳ９０４において、CstartXを切り上げ、整数位置に移動させ、CXとする。
【００６９】
ステップＳ９０５において、現在のCX,CYを出力座標位置として図１に示す局所データ出力アドレス計算部１０５に出力する。
【００７０】
ステップＳ９０６において、CXに出力座標系で１を加算する。
【００７１】
ステップＳ９０７において、もしCXが先に求めたCendXよりも小さければ（S907−Yes）、処理をステップＳ９０５に戻す。一方、ステップＳ９０７の判定で、CXがCendx以上の場合（S907−No）、処理はステップＳ９０８に進められる。
【００７２】
ステップＳ９０８では、CYに１を加算する。
【００７３】
ステップＳ９０９において、CYがEndRectYを超えていた場合には処理を終了する。一方、ステップＳ９０９の判定で、CYがEndRectYを超えていない場合（S909‐Yes）、処理はステップＳ９１０に進められる。
【００７４】
ステップＳ９１０において、CstartX1にrate_y/rate_xを足すことにより、ステップＳ９０８で更新されたCYの水平線と、図８のline1との交点に移動させて、CstartX１の更新を行う。
【００７５】
ステップＳ９１１において、CstartX2にline_rate_y/line_rate_xを足すことにより、CYの水平線と図８のline2との交点に移動させて、CstartX2の更新を行う。
【００７６】
ステップＳ９１２において、CendX1にline_rate_y/line_rate_xを足すことにより、CYの水平線と図８のline3との交点に移動させて、CendX1の更新を行う。
【００７７】
ステップＳ９１３において、CendX2にrate_y/rate_xを足すことにより、ステップＳ９０８で更新されたCYの水平線と、図８のline4との交点に移動させて、CendX2の更新を行い、処理をステップＳ９０１に戻す。そして、ステップＳ９０１〜Ｓ９１３まで同様の処理が繰り返される。
【００７８】
本実施形態によれば、少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理を高速で安価に実現する画像処理技術の提供が可能になる。
【００７９】
（第２実施形態）
本実施形態における画像処理装置の構成を図１０に示す。構成要素は（１０１〜１０９）、図１に示した構成と同一であるので、ここでは詳細な説明を省略する。本実施形態にかかる画像処理装置において、画像入力部１０１と読み出し用バッファ１０２との間でやりとりするデータ１０１０には、ピクセル情報だけでなく、座標情報も含む。
【００８０】
画像処理に与える入力画像データは、必ずしも1ラスタ単位であるとは限らない。図４（ａ）で示したように横方向に1ラインずつ入力するケースのほかに、バンドに区切った部分画像について縦方向に順次データを入力する場合もありうるためである（図４（ｂ））。このような様々な入力データの入力順序に臨機応変に対応するためには、図１０のデータ１０１０に、座標情報も同時に含まれるようなデータ構造が必要となる。
【００８１】
部分画像データ（ピクセルデータ）と座標情報とを同時に入力する場合の好適なデータの入力順序の例を図１１に示す。
【００８２】
データの入力順序は、２ラスタ１１０１をカラム単位で順次入力するものである。この場合、第１実施形態で既に説明した1ラスタ単位のデータ入力に比べ、一度に２ラスタ分のデータを（４）式により計算できる。（４）式において、ｃｉは、横方向の変倍時のピクセル影響度を示す係数である。ｃｊは縦方向の係数であり、Ｐｉｎは局所画像範囲内の（ｉ、ｊ）の位置にある画素値である。そして、出力画像生成のための加算は（５）式により算出することができる。
【００８３】
【数４】
2008192073.tif 000006
【００８４】
出力メモリまたは出力側ローカルメモリ上での積算回数が半分または半分＋１回とすることが可能となり、特に出力バッファを応答速度の遅い外部メモリにおく場合には処理の高速化が期待できる。また、ある１点の出力点についての横方向の係数ciは、２ラスタについて同じ値が使用できるため、係数の算出にかかる処理速度も向上が図れる。
【００８５】
２ラスタ単位でのデータ入力を行った場合に、出力側に持つべきローカルメモリの領域１２０１を図１２に示す。
【００８６】
２ラスタ入力の場合には、１ラスタ入力の場合（図３）に比べてバッファの重なり部分が小さくなることがわかる。このような領域をカバーする分のローカルメモリを持つことで、積算処理をローカルメモリで行うことができ、応答の遅い外部メモリへのアクセスは１回の書き込みに抑えることが可能となる。
【００８７】
ローカルメモリ容量の限界を超えるフィルタサイズの処理を行う場合でも、はみ出した部分を外部メモリに割り当てることで処理を行うことが可能であり、ローカルメモリのサイズによって処理可能なフィルタサイズは制限を受けない。
【００８８】
図１３は、３ラスタをカラム単位１３０１で入力する状態を示す図である。
【００８９】
この場合、先に示した式（４）、（５）式は、以下の（６）式、（７）式となる。
【００９０】
【数５】
2008192073.tif 000007
【００９１】
出力メモリまたは出力側ローカルメモリ上での積算回数が１／３または１/３＋１回とすることが可能となり、特に出力バッファを応答速度の遅い外部メモリにおく場合には処理の高速化が期待できる。また、ある1点の出力点についての横方向の係数ciは、３ラスタについて同じ値が使用できるため、係数の算出にかかる処理速度も更なる向上が図れる。
【００９２】
尚、係数ci, cj、フィルタ、補間演算の参照点を選択することにより、局所データ変換処理の構成を変えずに、例えば、１次補間、３次補間などの処理を切り替えて実施する処理をハードウェアまたはソフトウェアに実装しても良い。
【００９３】
更に、係数算出時に周囲の局所データの水平、垂直方向の距離を求めるステップにおいて、最も近傍の点を割り出す判断処理を追加することも可能である。この判断ステップの追加により局所データ変換部の構成を変えずに、０次補間（最近傍サンプリング処理）を行う処理をハードウェアまたはソフトウェアに実装することも可能である。
【００９４】
（第３実施形態）
第３実施形態として、フィルタサイズと同じライン数のデータを入力として同時に与えた場合の処理を説明する。図１４の参照番号１４０１で示した部分については、そもそも全てのフィルタ計算用の入力画素が一度に保持されていることから、積算の必要がない。図１４の参照番号１４０２で示した領域については複数回の処理に分かれる積算処理が不要であるため、ローカルバッファへの保存を行う必要がない。ここでは単に積算処理が不要となる特別なケースを例示的に説明するものであり、外部メモリへの連続書き込み（バーストライト）を行うための一時保持バッファとしてローカルバッファを使用することは可能である。
【００９５】
（第４実施形態）
図１６は、画像データの入出力制限を例示的に説明する図である。画像領域１６０１は入力される画像データの全体を示す画像領域である。領域１６０２は、画像領域１６０１の中で処理されるべき領域を示している。領域１６０２の画像を全て処理した結果が、出力画像のデータを保持するバッファの領域１６０３に格納される。実際には、出力画像のデータを保持するバッファ容量が十分に確保できない等の理由により制限される場合がある。
【００９６】
図１７は、本実施形態に係る画像処理装置の構成を示す図である。図１５の構成に対して、入力領域保持部１７１０、出力領域保持部１７１１が設けられている。尚、圧縮画像伸張部１５０１に代わり画像入力部１０１を設ける構成としてもよい。
【００９７】
入力領域保持部１７１０は、入力画像の中で、処理すべき座標範囲を保持する。入力領域保持部１７１０が保持する座標範囲に基づき読み出し用バッファ制御部（第１バッファ制御部）１０３は入力された画像の座標が、処理すべき領域に含まれるか判定する。読み出し用バッファ制御部１０３は判定結果に基づいて入力された画像の座標が処理するべき座標範囲に含まれている場合、読み出し用バッファ１０２への格納と、読み出し用バッファ１０２から局所データ変換部１０４への出力を制御する。
【００９８】
但し、補間演算などが必要となる変倍処理やフィルタ処理においては、入力領域に対してフィルタサイズや補間時に参照する周辺が元の範囲を考慮した上で入力画像（入力画素）の選別を行う処理を読み出し用バッファ制御部１０３が行う。
【００９９】
出力領域保持部１７１１は、出力すべき領域の座標範囲の情報を保持する。書き込み用バッファ制御部（第２バッファ制御部）１０８は、座標の位置に変換された部分画像（出力画像）とその出力座標系での位置情報１７３０とに基づき、部分画像（出力画像）の位置情報が、出力すべき領域の座標範囲に含まれているか判定する。書き込み用バッファ制御部（第２バッファ制御部）１０８は判定結果により出力画像の位置情報が出力すべき領域の座標範囲に含まれている場合には、出力画像と位置情報とを書き込み用バッファ１０７に書き込み、画像出力部１０９に対する出力を制御する。
【０１００】
（他の実施形態）
なお、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録したコンピュータ可読の記憶媒体を、システムあるいは装置に供給することによっても、達成されることは言うまでもない。また、システムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても、達成されることは言うまでもない。
【０１０１】
この場合、記憶媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【０１０２】
プログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。
【０１０３】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現される。また、プログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【０１０４】
【図１】第１実施形態に係る画像処理装置が備える構成要素を示す図である。
【図２】順変換による局所データの変換処理を説明する図である。
【図３】ローカルバッファを説明する図である。
【図４】ローカルバッファを説明する図である。
【図５】画像の回転を行う場合の局所データ変換部１０４の処理を説明する図である。
【図６】順変換により回転・変形・変倍を行った場合の座標値の求め方を説明する図である。
【図７】アフィン変換による回転・変倍・変形処理を行う場合の設定パラメータについて説明した図である。
【図８】アフィン変換による回転・変倍・変形処理を行う場合の設定パラメータについて説明した図である。
【図９】出力座標算出処理の流れを説明する図である。
【図１０】第２実施形態に係る画像処理装置が備える構成要素を示す図である。
【図１１】部分画像データと座標情報とを同時に引き渡す場合の好適なデータの入力順序の例を示す図である。
【図１２】２ラスタ単位でのデータ入力を行った場合に、出力側に持つべきローカルメモリの領域を示す図である。
【図１３】３ラスタをカラム単位１３０１で入力する状態を示す図である
【図１４】フィルタサイズと同じライン数のデータを入力として同時に与えた場合の処理を説明する図である。
【図１５】圧縮画像伸張部１５０１を備えた画像処理装置の構成を例示する図である。
【図１６】画像データの入出力制限を例示的に説明する図である。
【図１７】第４実施形態に係る画像処理装置の構成を示す図である。
【図１８】画像中の一部分を回転しながら取り出す変換を例示的に説明する図である。
【図１】
2008192073.tif 000008
【図２】
2008192073.tif 000009
【図３】
2008192073.tif 000010
【図４】
2008192073.tif 000011
【図５】
2008192073.tif 000012
【図６】
2008192073.tif 000013
【図７】
2008192073.tif 000014
【図８】
2008192073.tif 000015
【図９】
2008192073.tif 000016
【図１０】
2008192073.tif 000017
【図１１】
2008192073.tif 000018
【図１２】
2008192073.tif 000019
【図１３】
2008192073.tif 000020
【図１４】
2008192073.tif 000021
【図１５】
2008192073.tif 000022
【図１６】
2008192073.tif 000023
【図１７】
2008192073.tif 000024
【図１８】
2008192073.tif 000025