画像処理装置、画像処理装置の制御方法
【課題】少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理を高速で安価に実現すること。
【解決手段】 画像処理装置は、部分画像を格納する読み取り用バッファを制御する第1バッファ制御部と、読み取り用バッファに格納された部分画像を、出力座標の位置に順次変換する変換部と、変換部により出力座標の位置に変換された部分画像を格納する書き込み用バッファを制御する第2バッファ制御部と、を備える。
【解決手段】 画像処理装置は、部分画像を格納する読み取り用バッファを制御する第1バッファ制御部と、読み取り用バッファに格納された部分画像を、出力座標の位置に順次変換する変換部と、変換部により出力座標の位置に変換された部分画像を格納する書き込み用バッファを制御する第2バッファ制御部と、を備える。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は画像処理技術に関するものである。
【背景技術】
【0002】
画像処理の出力側でラスタ走査順となるように画像データを処理するためには、入力側で画像データにランダムアクセスすることが必要なる(この変換方式を逆変換方式という)。出力座標系から逆変換を行って入力座標系上での処理領域を求めて画像処理を行う技術としては、例えば、特許文献1に示されるものがある。特許文献1においては、逆変換と順変換は、変換方式の選択として説明されている。
【特許文献1】特開平11−154228号公報
【発明の開示】
【発明が解決しようとする課題】
【0003】
しかしながら、逆変換と順変換は、選択により何れの変換も実行することが可能とは限らない。一般的な1次変換式によるアフィン変換の場合、変換行列は必ずしも逆行列を持つとは限らないためである。逆変換を行う場合には、逆行列が存在しない場合の処理を必ず入れなければならず、そのときだけ処理が切り替わることにより、処理時間が変動してしまうなど、逆変換による画像処理には逆変換処理上の問題がある。
【0004】
また、図18に示すように、画像中の一部分を回転しながら取り出すような変換を行う場合として、例えば、入力画像中1801にある領域1802を回転して出力する場合を考える。出力バッファに一度に入るバッファサイズを領域1803とすると、その幅サイズ1804と高さサイズ1805とを含む入力データとして必要な領域のサイズは高さサイズ1806として示される。このように、回転角度が大きいほど、一度に保持しなければならない入力画像の範囲(サイズ)は大きくなる。
【0005】
特許文献1では、入力として必要な画像をライン単位で入力し、図18の参照番号1807に示すような範囲の局所データを読み取るだけのデータがたまるまで入力ラインの画像データをためる処理を行う技術を開示している。そのため、回転変倍処理には、大きな入力バッファサイズが必要になる。
【0006】
例えば、画像の横幅をA4サイズ600dpiとして考えると、1ラインが5000画素以上になることから、45度の回転を想定しても、5000/√2、すなわち3535ライン分のデータを保持しなければならない。この場合、1画素を3バイトで保持したとすると5000×3×3535=約50MBのメモリ量となり、巨大なメモリが必要となる。
【0007】
こうした問題を回避するために入力側の画像を圧縮して保持することが考えられる。圧縮率10倍の圧縮方法を使用すれば、50MBのデータを5MBという比較的現実的なサイズに抑えることが可能である。しかし、この場合も逆変換方式では入力データを斜めに横切るように読まなければならないため、圧縮データの並びに逆らった読み方となり、結果として読み出しに要する時間がかかりすぎて高速に処理を実施することができないという問題がある。特に、JPEG、PNG、TIFF等のように、カラム方向にピクセルないしはブロック単位で移動しながら圧縮する画像圧縮方法では、斜めに読むことに対する負荷が非常に大きく、現実に利用することが困難であるという問題がある。
【0008】
更に、アドレス変換ROMによって回転を行う技術が特許文献1に開示されており、アフィン変換を行う場合には、回転・変倍の他に更に平行性を保った形での変形が可能である。回転・変倍等の全てのケースに対応するには、2×2又は3×3の変換マトリクスの個々の係数の全ての値の組み合わせに対してアドレス変換テーブルをROM化しなければならず、実際には実現困難であるという問題がある。
【0009】
近年標準化されたSVG(Scalable Vector graphics)規格などでは、回転、変倍などのほかにアフィン変換行列の係数を個々に自由に指定することが可能である。SVG規格への応用においてはROM化テーブルは必ずしも安価・高速に処理を実行するための有効な手段とならない場合があるという問題がある。
【0010】
上記問題を鑑み、本発明は、少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理等を高速で安価に実現する画像処理技術の提供を目的とする。
【課題を解決するための手段】
【0011】
上記の従来技術を解決するべく、本発明に係る画像処理装置は、部分画像を格納する第1格納手段を制御する第1バッファ制御手段と、
前記第1格納手段に格納された前記部分画像を、出力座標の位置に順次変換する変換手段と、
前記変換手段により出力座標の位置に変換された部分画像を格納する第2格納手段を制御する第2バッファ制御手段と、
を備えることを特徴とする。
【発明の効果】
【0012】
本発明によれば、少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理を高速で安価に実現する画像処理技術の提供が可能になる。
【発明を実施するための最良の形態】
【0013】
以下、図面を参照して、本発明の好適な実施形態を例示的に詳しく説明する。ただし、この実施の形態に記載されている構成要素はあくまで例示であり、本発明の技術的範囲は、特許請求の範囲によって確定されるのであって、以下の個別の実施形態によって限定されるわけではない。
【0014】
(第1実施形態)
図1は、本発明の実施形態に係る画像処理装置が備える構成要素を示す図である。画像入力部101は画像データ、画像データの座標情報を入力する。画像入力部101は単純なメモリアクセスやハードディスクアクセス、ないしはネットワークアクセスにより画像データ、座標情報を取得することも可能である。
【0015】
画像処理装置の構成としては、画像データを取得する画像入力部101の他、圧縮画像伸張部1501を設ける構成でもよい。図15に示す構成によれば、回転・変倍・変形処理の前に、圧縮画像伸張部1501は、圧縮された画像を伸張して出力することが可能である。その場合、回転、変倍、変形処理は、高々数ピクセルの入力単位で処理が可能であるので、特別なバッファなしに、画素(ピクセル)単位、またはブロック単位の部分画像と、その座標情報と、の受け渡しを直接行うようにすることも可能である。符号化方式として、例えば、DCT、DFT、DST、LOT、アダマール変換、Wavelet変換、サブバンド符号化、ランレングス符号化、LZW符号化、ハフマン符号化またはこれらの組み合わせを利用することが可能である。
【0016】
読み出し用バッファ102は、画像入力部101から入力された画像データを保持するバッファである。読み出し用バッファ102は、部分画像を格納する第1格納部として機能することが可能である。
【0017】
読み出し用バッファ制御部103は、入力された画像データのうち局所データ(部分画像)を格納する読み出し用バッファ102(第1格納手段)を制御する。読み出し用バッファ制御部103は、読み出し用バッファ102(第1格納部)を制御する第1バッファ制御部として機能することが可能である。
【0018】
読み出し用バッファ制御部103は処理に必要な画像データを、局所データ(部分画像)として、読み出し用バッファ102(第1格納部)に保持させるように不要な画像データを削除したり、新たな画像データを保持させたりする制御が可能である。また、読み出し用バッファ制御部(第1バッファ制御部)103は、必要に応じて、読み出し用バッファ102(第1格納部)における画像データの保持位置をシフトさせるなどの並べ替えを行うことも可能である。
【0019】
局所データ変換部104は、読み出し用バッファ制御部(第1バッファ制御部)103によって並べ替えられた入力画像の局所データ(部分画像)を順変換により、出力座標の位置に順次変換する座標変換を行い出力することが可能である。
【0020】
局所データ出力アドレス計算部105は、局所データ(部分画像)から、順変換による座標変換で必要となる出力座標点を算出することが可能である。
【0021】
順変換座標算出部106は、局所データ出力アドレス計算部105に、入力座標位置と変換マトリクスによって順変換方式で出力座標位置を求めることが可能である。
【0022】
一般的な画像処理においては、画像データはラスタ走査順に処理され、その画像処理結果はラスタ走査順に出力される。これに対して、回転処理は、入力側と出力側でデータの入出力の順番が異なる。入力側からラスタ走査順に画像データが入力され、回転された画像データは、回転角に従った傾きの方向に書き込まれることになる。このため、出力側では、入力順とは異なる書き込み用バッファ107へのアクセス(ランダムアクセス)が必要となる。この変換方式を以下、順変換方式という。
【0023】
書き込み用バッファ107は、局所データ変換部104により変換された出力用画像データを保持する。読み出し用バッファ102(第1格納部)に格納された部分画像(局所データ)は、局所データ変換部104により出力座標の位置に変換され、書き込み用バッファ107に格納される。書き込み用バッファ107は、出力座標の位置に変換された部分画像を格納する第2格納部として機能することが可能である。
【0024】
書き込み用バッファ制御部108は、書き込み用バッファ107(第2格納部)に効率よく出力データを保持させるための書き込みアドレスの制御を行う。書き込み用バッファ制御部108は、出力座標の位置に変換された部分画像を格納する第2格納部を制御する第2バッファ制御部として機能することが可能である。
【0025】
画像出力部109は、書き込み用バッファ107(第2格納部)に保持された出力用画像データを適宜、外部処理モジュールまたは外部メモリに出力する。
【0026】
(順変換による局所データの変換処理)
順変換による局所データの変換処理について図2を参照して説明する。図2では、入力画像が画素(ピクセル)単位に、矢印250で示す横方向に順次入力されてくるようなデータの流れを想定している。図2(a)に示すように、4画素を一度に処理することで処理回数を減らし、なおかつ読み出し用バッファ102(第1格納部)、書き込み用バッファ107(第2格納部)上での読み書き回数を低減させることができる。
【0027】
横方向の画素(ピクセル)4点210〜213に基づき出力される出力画素として、図2(a)中のAで示した領域に含まれる画素に限定することで、処理を簡素化しつつ、出力バッファ上での読み書きの回数を低減させるこがきる。
【0028】
原理的には、4点(4画素)全てが関与する範囲である図2(a)中にBで示す範囲に対して出力値を算出することが可能である。その場合、出力値に対する画素の関与の比率が出力画素ごとに異なってしまい、一律の処理によって出力値の算出処理を進めることが不可能になる。よって、本実施形態では、入力4点(4画素)に対してAで示した領域についてのみ出力を行うものとする。図中の「○」は出力画素を例示的に示すものである。
【0029】
次に、図2(b)に示すように、次の画素が1点(1画素分)入ってきたところで、最初に入力された画素を記憶領域から破棄し、新たに入力された1画素を含む4点(4画素)を保持することで同様の出力値の計算を行う。そして、図2(b)中Cで示す範囲に含まれる出力座標点への出力を行う。このようにして、1ラスタ目の画像入力については1ピクセルの入力毎に4点という非常に少ない保持データにより、順次出力画素を出力する。
【0030】
次に、図2(c)に示すように2ラスタ目の処理に移ると、4点により出力できる領域が上方向にもあることになるため、図中に領域Dに示すような領域に含まれる出力座標点への出力を行う。
【0031】
2ラスタ目についても1ラスタ目と同様、図2(d)に示すとおり次のピクセルが入力されたところで最初のピクセルを破棄し、新たな4点(4画素)について同様の処理を行うことで、順次処理を進めていくことができる。
【0032】
その後、図2(e)、(f)に示すように3ラスタ目、4ラスタ目と順次同様の処理を繰り返していくことで、出力画素を生成することが可能である。
【0033】
画像の下端については、図2(a)〜図2(d)に示した領域をちょうど上下反転したように処理することで、入力画像の境界部分での出力処理を境界以外の他の処理と同様に行うことが可能になる。一定の透過率による画像合成を行う場合には、予め出力バッファ上に描画されている画像をピクセル単位で読み出し、透過率によって決まる係数を掛けて書き戻しておくことにより、合成画像を得ることも可能である。
【0034】
次に、処理をより高速に実現するにあたって、画像上端・下端を除いた一般的な処理において、バッファ上での読み書き回数を減らすために最低限必要なバッファの構成について図3を用いて説明する。
【0035】
例えば、本実施形態の処理をキャッシュメモリなどのローカルバッファを持つハードウェアないしはCPUにおいて実現することも可能である。この場合、図3で示した領域に含まれる出力座標点分のサイズのローカルバッファを持つことにより、効果的に外部メモリへの書き込み回数を減らすことが可能である。この場合、バッファのサイズは、変倍率などによって変動する。拡大処理を行う場合、図中の領域に含まれる出力座標点は多くなり、縮小の場合には少なくなるからである。
【0036】
一般にローカルバッファのサイズには実装コスト上の制約があるため、変倍率に対しても制限が必要となる。しかし、本実施形態によれば、ローカルバッファに入らない領域の出力座標点については直接外部メモリに出力しておき、その後の処理時に再度読み出して処理をすればよく、ローカルバッファに全ての出力座標点の情報が含まれる必要はない。ローカルバッファの上限を超える変倍率を指定した際には、変倍率の増加に対して単調増加の傾向で処理負荷が重くなるだけであり、高速化と柔軟性を比較的制御性の良い形で両立することも可能である。
【0037】
また、ローカルバッファの構成では、画素が連続して入力される横方向の画素数分、ローカルバッファの幅を持つ必要がある。これを効果的に小さくするための方法について図4を用いて説明する。図4(a)中の参照番号401は、図2で示した入力されるデータの入力順を概略的に示している。このようにラスタ単位でデータを処理する場合、入力されるデータの入力順は参照番号401にようになる。この場合、多くの画像処理に対して適用可能であるが、反面、本実施形態で用意するべきバッファの容量は、図4中の参照番号402で示すように大きくなってしまう。
【0038】
これに対して、画像をバンド単位に処理する場合、画素の入力方向を縦方向にすることで、回転処理で必要となるローカルバッファの領域を90度回転させたものとすることができ、結果としてローカルバッファのサイズを小さく抑えることが可能である。
【0039】
次に、画像の回転を行う場合の局所データ変換部104の処理について図5を用いて説明する。回転においては、例えば、図2(e)の領域Fに、斜めに出力画素が並ぶことになる。この場合には、参照番号501に示した点に対してそれぞれ計算を行ったうえで積算処理を行う必要があるが、処理としてはこれまでに説明した処理と同様である。例えば、16点の補間の処理であっても、4画素(ピクセル)という非常に少ない入力画像の局所データの保持で、かつ、効率的な回転変倍を行うことができる。
【0040】
ただし、これだけでは、アフィン変換のための乗算処理を複数行う必要があるなど、ハードウェア化においては回路規模が大きくなる要素を残している。そこで、出力座標範囲と、その中に含まれる実際に出力を行うべき出力座標点の集合を簡単な演算で実施する構成を以下に説明する。
【0041】
アフィン変換と呼ばれる行列演算による変形では、「平行な直線は変換後も平行である」という性質を持っていることが知られている。このことは、すなわち直線によって囲まれた領域を変形する場合には、領域を囲む平行でない直線の数だけの傾き情報の変換によって図形の変換が可能であることを示している。
【0042】
こうしたことからアフィン変換における変換パラメータは、行列演算から求められる入力座標系の整数位置の単位移動量に対する変換後の単位移動量、すなわち傾きとして求められることになる。
【0043】
アフィン変換は、入力座標を(x,y)、出力座標を(X,Y)とすると、以下のように表される。
【0044】
【数1】
【0045】
ここで、デジタル画像処理では入出力座標位置は整数で表される位置に離散化されていることから、例えば(x,0)という点は、この式によって(ax+c,dx+f)という位置に写像される。
【0046】
【数2】
【0047】
更に、x+1という位置は、下式に示すように(ax+c+a,dx+f+d)という位置に写像されることになる。
【0048】
【数3】
【0049】
(3)式より明らかなように、入力座標系での隣の画素位置への移動は、出力座標系での(a,d)という傾きを持った移動となる。アフィン変換によって行われる座標変換は、入力座標系での一定の移動量は、出力座標系では変換された傾きを持った移動量となる事がわかる。このことから、アフィン変換では入力座標上のある点の変換座標と、そこからの移動量を傾きとして与えることで、変換後の出力位置を簡便に求められる可能性があることが分かる。
【0050】
逆行列が存在しない行列式による変換の場合には、入力画像上で互いに平行でなかった直線が平行になってしまったり、1点に集約されてしまったりするなどの現象が起きる。こうした場合には、ある1点の出力座標に対応する入力座標位置が無数に存在してしまうため、逆変換によって入力座標位置を求めることは単なる計算だけでは行えなくなる。このような場合でも、変換前には異なる傾きを持った直線が、変換後には同じ傾きを持つようになるというだけであり、その変換は傾きの変換によって行える。
【0051】
図6は、順変換により回転・変形・変倍を行った場合の座標値の簡便な求め方を説明する図である。アフィン変換による座標変換は、出力画像座標系に対して、入力画像座標が軸の平行性を保った形で写像される。入力座標系の座標点を白丸で示すと、正方形として配置する座標点は、アフィン変換を行うことにより、一般的に、黒丸で座標点を示す平行四辺形の配置に写像される。入力座標系のX座標、Y座標は、出力座標系でそれぞれd/a、e/bの傾きを持つ直線に写像されることになる。
【0052】
これにより、矩形領域を持つ画像の回転・変倍・変形処理を簡素化して行うことが可能になる。図7は、アフィン変換による回転・変倍・変形処理を行う場合の設定パラメータについて説明した図である。
【0053】
図7中に黒丸で示したのが出力座標上の画素点であり、四角で示したのが入力座標系の画素点である。入力画像の処理開始点を出力座標上に写像した位置(StartX, StartY)を基点とする。
【0054】
入力画像の点の出力座標上の配置は入力座標のX軸、Y軸が出力座標系上で持つ傾き(rate_x, rate_y)、(line_rate_x, line_rate_y)とを算出して求めることが可能である。
【0055】
アフィン変換による変倍後の座標計算は、(StartX, StartY), (rate_x, rate_y), (line_rate_x, line_rate_y)の6つのパラメータによって置き換えることが可能である。
【0056】
6つのパラメータは、アフィン変換を表現するための基本的なものであるが、これだけでは出力座標上の画素位置を求めることが困難である。なぜなら、入力画像の画素位置は、出力画像の画素位置の途中、つまり小数点以下の値を含む位置に一般に写像されるからである。出力画像を正しく求めるためには、こうした小数点を含む位置から整数によって表される出力座標格子点を求める計算を行わなければならない。
【0057】
このパラメータの与え方について、図8を用いて説明する。先に与えられた6つのパラメータから直線line1、line2、line3を求める。そして、出力座標系のY座標整数位置にある水平線との交点(図8の(CstartX1,CstartY1)、(CstartX2, CstartY2)および(CendX1,CendY1)、(CendX2, CendY2))を算出する。
【0058】
これは、ハードウェアで行うためには乗算器を含む比較的回路規模の大きな演算処理を必要とするため、安価な実施には不適当であるが、ソフトウェアによってあらかじめ求めることは実装上の負荷とはならない。これらの交点座標を初期値として与え、その後は傾きの情報を加算することで順次出力座標の範囲を求めることが可能である。これにより、ハードウェア実装負荷の低い加算器のみを用いてアフィン変換の順変換座標算出部を実施することが可能となり、安価な構成で、かつ高速な処理の実行が可能となる。
【0059】
図8のように、最初に入力される4点についての座標位置として(StartX,StartY)、(EndX, EndY)、(EndLineX, EndLineY)、(EndRectX, EndRectY)を求める(矩形範囲801)。これらはそれぞれ、所望のアフィン変換行列をかけることで求めることが可能である。
【0060】
n×mの参照点を持つフィルタの場合、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となるのが基本となる。
【0061】
しかしながら、フィルタサイズn、mは必ずしも偶数であるとは限らないことから、cn1,cn2,cm1,cm2が常にこのような単純な式で求められるとは限らない。また、入力画像の上端、下端、左端、右端においては、さらにこのcn1,cn2,cm1,cm2を図2に示したように変化させる制御を行う必要がある。但し、入力画素をn,mを考慮して画像の外に当たる部分も供給するなどの方法によって、処理に必要な画像を補うことで、こうした出力領域の制御を行わないように構成することも可能である。
【0062】
こうして求められた矩形範囲801について、(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の交点である。
【0063】
(StartX,StartY),(EndX, EndY),(EndLineX,EndLineY),(EndRectX, EndRectY)を出力座標領域算出の初期値として与える。その後は傾きの情報を加算することで順次出力座標における局所データの変換を求めることが可能になる。
【0064】
本実施形態の出力座標算出処理の流れを図9のフローチャートを参照して説明する。本処理は、局所データ変換部104、局所データ出力アドレス計算部105、順変換座標算出部106の制御の下に実行することが可能である。
【0065】
出力座標位置算出処理が開始されると、ステップS901で、入力座標CstartX1,CstartX2のうち、X座標の値が大きいほうを選択し、CstartXとする。
【0066】
ステップS902において、入力座標CendX1,CendX2のうち、X座標の小さいほうを選択し、CendXとする。
【0067】
ステップS903において、CstartY1,CstartY2, CendY1, CendY2は、全ての点について同じ値となるため、いずれかのCYを決定する。
【0068】
ステップS904において、CstartXを切り上げ、整数位置に移動させ、CXとする。
【0069】
ステップS905において、現在のCX,CYを出力座標位置として図1に示す局所データ出力アドレス計算部105に出力する。
【0070】
ステップS906において、CXに出力座標系で1を加算する。
【0071】
ステップS907において、もしCXが先に求めたCendXよりも小さければ(S907−Yes)、処理をステップS905に戻す。一方、ステップS907の判定で、CXがCendx以上の場合(S907−No)、処理はステップS908に進められる。
【0072】
ステップS908では、CYに1を加算する。
【0073】
ステップS909において、CYがEndRectYを超えていた場合には処理を終了する。一方、ステップS909の判定で、CYがEndRectYを超えていない場合(S909‐Yes)、処理はステップS910に進められる。
【0074】
ステップS910において、CstartX1にrate_y/rate_xを足すことにより、ステップS908で更新されたCYの水平線と、図8のline1との交点に移動させて、CstartX1の更新を行う。
【0075】
ステップS911において、CstartX2にline_rate_y/line_rate_xを足すことにより、CYの水平線と図8のline2との交点に移動させて、CstartX2の更新を行う。
【0076】
ステップS912において、CendX1にline_rate_y/line_rate_xを足すことにより、CYの水平線と図8のline3との交点に移動させて、CendX1の更新を行う。
【0077】
ステップS913において、CendX2にrate_y/rate_xを足すことにより、ステップS908で更新されたCYの水平線と、図8のline4との交点に移動させて、CendX2の更新を行い、処理をステップS901に戻す。そして、ステップS901〜S913まで同様の処理が繰り返される。
【0078】
本実施形態によれば、少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理を高速で安価に実現する画像処理技術の提供が可能になる。
【0079】
(第2実施形態)
本実施形態における画像処理装置の構成を図10に示す。構成要素は(101〜109)、図1に示した構成と同一であるので、ここでは詳細な説明を省略する。本実施形態にかかる画像処理装置において、画像入力部101と読み出し用バッファ102との間でやりとりするデータ1010には、ピクセル情報だけでなく、座標情報も含む。
【0080】
画像処理に与える入力画像データは、必ずしも1ラスタ単位であるとは限らない。図4(a)で示したように横方向に1ラインずつ入力するケースのほかに、バンドに区切った部分画像について縦方向に順次データを入力する場合もありうるためである(図4(b))。このような様々な入力データの入力順序に臨機応変に対応するためには、図10のデータ1010に、座標情報も同時に含まれるようなデータ構造が必要となる。
【0081】
部分画像データ(ピクセルデータ)と座標情報とを同時に入力する場合の好適なデータの入力順序の例を図11に示す。
【0082】
データの入力順序は、2ラスタ1101をカラム単位で順次入力するものである。この場合、第1実施形態で既に説明した1ラスタ単位のデータ入力に比べ、一度に2ラスタ分のデータを(4)式により計算できる。(4)式において、ciは、横方向の変倍時のピクセル影響度を示す係数である。cjは縦方向の係数であり、Pinは局所画像範囲内の(i、j)の位置にある画素値である。そして、出力画像生成のための加算は(5)式により算出することができる。
【0083】
【数4】
【0084】
出力メモリまたは出力側ローカルメモリ上での積算回数が半分または半分+1回とすることが可能となり、特に出力バッファを応答速度の遅い外部メモリにおく場合には処理の高速化が期待できる。また、ある1点の出力点についての横方向の係数ciは、2ラスタについて同じ値が使用できるため、係数の算出にかかる処理速度も向上が図れる。
【0085】
2ラスタ単位でのデータ入力を行った場合に、出力側に持つべきローカルメモリの領域1201を図12に示す。
【0086】
2ラスタ入力の場合には、1ラスタ入力の場合(図3)に比べてバッファの重なり部分が小さくなることがわかる。このような領域をカバーする分のローカルメモリを持つことで、積算処理をローカルメモリで行うことができ、応答の遅い外部メモリへのアクセスは1回の書き込みに抑えることが可能となる。
【0087】
ローカルメモリ容量の限界を超えるフィルタサイズの処理を行う場合でも、はみ出した部分を外部メモリに割り当てることで処理を行うことが可能であり、ローカルメモリのサイズによって処理可能なフィルタサイズは制限を受けない。
【0088】
図13は、3ラスタをカラム単位1301で入力する状態を示す図である。
【0089】
この場合、先に示した式(4)、(5)式は、以下の(6)式、(7)式となる。
【0090】
【数5】
【0091】
出力メモリまたは出力側ローカルメモリ上での積算回数が1/3または1/3+1回とすることが可能となり、特に出力バッファを応答速度の遅い外部メモリにおく場合には処理の高速化が期待できる。また、ある1点の出力点についての横方向の係数ciは、3ラスタについて同じ値が使用できるため、係数の算出にかかる処理速度も更なる向上が図れる。
【0092】
尚、係数ci, cj、フィルタ、補間演算の参照点を選択することにより、局所データ変換処理の構成を変えずに、例えば、1次補間、3次補間などの処理を切り替えて実施する処理をハードウェアまたはソフトウェアに実装しても良い。
【0093】
更に、係数算出時に周囲の局所データの水平、垂直方向の距離を求めるステップにおいて、最も近傍の点を割り出す判断処理を追加することも可能である。この判断ステップの追加により局所データ変換部の構成を変えずに、0次補間(最近傍サンプリング処理)を行う処理をハードウェアまたはソフトウェアに実装することも可能である。
【0094】
(第3実施形態)
第3実施形態として、フィルタサイズと同じライン数のデータを入力として同時に与えた場合の処理を説明する。図14の参照番号1401で示した部分については、そもそも全てのフィルタ計算用の入力画素が一度に保持されていることから、積算の必要がない。図14の参照番号1402で示した領域については複数回の処理に分かれる積算処理が不要であるため、ローカルバッファへの保存を行う必要がない。ここでは単に積算処理が不要となる特別なケースを例示的に説明するものであり、外部メモリへの連続書き込み(バーストライト)を行うための一時保持バッファとしてローカルバッファを使用することは可能である。
【0095】
(第4実施形態)
図16は、画像データの入出力制限を例示的に説明する図である。画像領域1601は入力される画像データの全体を示す画像領域である。領域1602は、画像領域1601の中で処理されるべき領域を示している。領域1602の画像を全て処理した結果が、出力画像のデータを保持するバッファの領域1603に格納される。実際には、出力画像のデータを保持するバッファ容量が十分に確保できない等の理由により制限される場合がある。
【0096】
図17は、本実施形態に係る画像処理装置の構成を示す図である。図15の構成に対して、入力領域保持部1710、出力領域保持部1711が設けられている。尚、圧縮画像伸張部1501に代わり画像入力部101を設ける構成としてもよい。
【0097】
入力領域保持部1710は、入力画像の中で、処理すべき座標範囲を保持する。入力領域保持部1710が保持する座標範囲に基づき読み出し用バッファ制御部(第1バッファ制御部)103は入力された画像の座標が、処理すべき領域に含まれるか判定する。読み出し用バッファ制御部103は判定結果に基づいて入力された画像の座標が処理するべき座標範囲に含まれている場合、読み出し用バッファ102への格納と、読み出し用バッファ102から局所データ変換部104への出力を制御する。
【0098】
但し、補間演算などが必要となる変倍処理やフィルタ処理においては、入力領域に対してフィルタサイズや補間時に参照する周辺が元の範囲を考慮した上で入力画像(入力画素)の選別を行う処理を読み出し用バッファ制御部103が行う。
【0099】
出力領域保持部1711は、出力すべき領域の座標範囲の情報を保持する。書き込み用バッファ制御部(第2バッファ制御部)108は、座標の位置に変換された部分画像(出力画像)とその出力座標系での位置情報1730とに基づき、部分画像(出力画像)の位置情報が、出力すべき領域の座標範囲に含まれているか判定する。書き込み用バッファ制御部(第2バッファ制御部)108は判定結果により出力画像の位置情報が出力すべき領域の座標範囲に含まれている場合には、出力画像と位置情報とを書き込み用バッファ107に書き込み、画像出力部109に対する出力を制御する。
【0100】
(他の実施形態)
なお、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録したコンピュータ可読の記憶媒体を、システムあるいは装置に供給することによっても、達成されることは言うまでもない。また、システムあるいは装置のコンピュータ(またはCPUやMPU)が記憶媒体に格納されたプログラムコードを読出し実行することによっても、達成されることは言うまでもない。
【0101】
この場合、記憶媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【0102】
プログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、CD−ROM、CD−R、不揮発性のメモリカード、ROMなどを用いることができる。
【0103】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現される。また、プログラムコードの指示に基づき、コンピュータ上で稼働しているOS(オペレーティングシステム)などが実際の処理の一部または全部を行い、その処理によって前述した実施形態が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【0104】
【図1】第1実施形態に係る画像処理装置が備える構成要素を示す図である。
【図2】順変換による局所データの変換処理を説明する図である。
【図3】ローカルバッファを説明する図である。
【図4】ローカルバッファを説明する図である。
【図5】画像の回転を行う場合の局所データ変換部104の処理を説明する図である。
【図6】順変換により回転・変形・変倍を行った場合の座標値の求め方を説明する図である。
【図7】アフィン変換による回転・変倍・変形処理を行う場合の設定パラメータについて説明した図である。
【図8】アフィン変換による回転・変倍・変形処理を行う場合の設定パラメータについて説明した図である。
【図9】出力座標算出処理の流れを説明する図である。
【図10】第2実施形態に係る画像処理装置が備える構成要素を示す図である。
【図11】部分画像データと座標情報とを同時に引き渡す場合の好適なデータの入力順序の例を示す図である。
【図12】2ラスタ単位でのデータ入力を行った場合に、出力側に持つべきローカルメモリの領域を示す図である。
【図13】3ラスタをカラム単位1301で入力する状態を示す図である
【図14】フィルタサイズと同じライン数のデータを入力として同時に与えた場合の処理を説明する図である。
【図15】圧縮画像伸張部1501を備えた画像処理装置の構成を例示する図である。
【図16】画像データの入出力制限を例示的に説明する図である。
【図17】第4実施形態に係る画像処理装置の構成を示す図である。
【図18】画像中の一部分を回転しながら取り出す変換を例示的に説明する図である。
【技術分野】
【0001】
本発明は画像処理技術に関するものである。
【背景技術】
【0002】
画像処理の出力側でラスタ走査順となるように画像データを処理するためには、入力側で画像データにランダムアクセスすることが必要なる(この変換方式を逆変換方式という)。出力座標系から逆変換を行って入力座標系上での処理領域を求めて画像処理を行う技術としては、例えば、特許文献1に示されるものがある。特許文献1においては、逆変換と順変換は、変換方式の選択として説明されている。
【特許文献1】特開平11−154228号公報
【発明の開示】
【発明が解決しようとする課題】
【0003】
しかしながら、逆変換と順変換は、選択により何れの変換も実行することが可能とは限らない。一般的な1次変換式によるアフィン変換の場合、変換行列は必ずしも逆行列を持つとは限らないためである。逆変換を行う場合には、逆行列が存在しない場合の処理を必ず入れなければならず、そのときだけ処理が切り替わることにより、処理時間が変動してしまうなど、逆変換による画像処理には逆変換処理上の問題がある。
【0004】
また、図18に示すように、画像中の一部分を回転しながら取り出すような変換を行う場合として、例えば、入力画像中1801にある領域1802を回転して出力する場合を考える。出力バッファに一度に入るバッファサイズを領域1803とすると、その幅サイズ1804と高さサイズ1805とを含む入力データとして必要な領域のサイズは高さサイズ1806として示される。このように、回転角度が大きいほど、一度に保持しなければならない入力画像の範囲(サイズ)は大きくなる。
【0005】
特許文献1では、入力として必要な画像をライン単位で入力し、図18の参照番号1807に示すような範囲の局所データを読み取るだけのデータがたまるまで入力ラインの画像データをためる処理を行う技術を開示している。そのため、回転変倍処理には、大きな入力バッファサイズが必要になる。
【0006】
例えば、画像の横幅をA4サイズ600dpiとして考えると、1ラインが5000画素以上になることから、45度の回転を想定しても、5000/√2、すなわち3535ライン分のデータを保持しなければならない。この場合、1画素を3バイトで保持したとすると5000×3×3535=約50MBのメモリ量となり、巨大なメモリが必要となる。
【0007】
こうした問題を回避するために入力側の画像を圧縮して保持することが考えられる。圧縮率10倍の圧縮方法を使用すれば、50MBのデータを5MBという比較的現実的なサイズに抑えることが可能である。しかし、この場合も逆変換方式では入力データを斜めに横切るように読まなければならないため、圧縮データの並びに逆らった読み方となり、結果として読み出しに要する時間がかかりすぎて高速に処理を実施することができないという問題がある。特に、JPEG、PNG、TIFF等のように、カラム方向にピクセルないしはブロック単位で移動しながら圧縮する画像圧縮方法では、斜めに読むことに対する負荷が非常に大きく、現実に利用することが困難であるという問題がある。
【0008】
更に、アドレス変換ROMによって回転を行う技術が特許文献1に開示されており、アフィン変換を行う場合には、回転・変倍の他に更に平行性を保った形での変形が可能である。回転・変倍等の全てのケースに対応するには、2×2又は3×3の変換マトリクスの個々の係数の全ての値の組み合わせに対してアドレス変換テーブルをROM化しなければならず、実際には実現困難であるという問題がある。
【0009】
近年標準化されたSVG(Scalable Vector graphics)規格などでは、回転、変倍などのほかにアフィン変換行列の係数を個々に自由に指定することが可能である。SVG規格への応用においてはROM化テーブルは必ずしも安価・高速に処理を実行するための有効な手段とならない場合があるという問題がある。
【0010】
上記問題を鑑み、本発明は、少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理等を高速で安価に実現する画像処理技術の提供を目的とする。
【課題を解決するための手段】
【0011】
上記の従来技術を解決するべく、本発明に係る画像処理装置は、部分画像を格納する第1格納手段を制御する第1バッファ制御手段と、
前記第1格納手段に格納された前記部分画像を、出力座標の位置に順次変換する変換手段と、
前記変換手段により出力座標の位置に変換された部分画像を格納する第2格納手段を制御する第2バッファ制御手段と、
を備えることを特徴とする。
【発明の効果】
【0012】
本発明によれば、少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理を高速で安価に実現する画像処理技術の提供が可能になる。
【発明を実施するための最良の形態】
【0013】
以下、図面を参照して、本発明の好適な実施形態を例示的に詳しく説明する。ただし、この実施の形態に記載されている構成要素はあくまで例示であり、本発明の技術的範囲は、特許請求の範囲によって確定されるのであって、以下の個別の実施形態によって限定されるわけではない。
【0014】
(第1実施形態)
図1は、本発明の実施形態に係る画像処理装置が備える構成要素を示す図である。画像入力部101は画像データ、画像データの座標情報を入力する。画像入力部101は単純なメモリアクセスやハードディスクアクセス、ないしはネットワークアクセスにより画像データ、座標情報を取得することも可能である。
【0015】
画像処理装置の構成としては、画像データを取得する画像入力部101の他、圧縮画像伸張部1501を設ける構成でもよい。図15に示す構成によれば、回転・変倍・変形処理の前に、圧縮画像伸張部1501は、圧縮された画像を伸張して出力することが可能である。その場合、回転、変倍、変形処理は、高々数ピクセルの入力単位で処理が可能であるので、特別なバッファなしに、画素(ピクセル)単位、またはブロック単位の部分画像と、その座標情報と、の受け渡しを直接行うようにすることも可能である。符号化方式として、例えば、DCT、DFT、DST、LOT、アダマール変換、Wavelet変換、サブバンド符号化、ランレングス符号化、LZW符号化、ハフマン符号化またはこれらの組み合わせを利用することが可能である。
【0016】
読み出し用バッファ102は、画像入力部101から入力された画像データを保持するバッファである。読み出し用バッファ102は、部分画像を格納する第1格納部として機能することが可能である。
【0017】
読み出し用バッファ制御部103は、入力された画像データのうち局所データ(部分画像)を格納する読み出し用バッファ102(第1格納手段)を制御する。読み出し用バッファ制御部103は、読み出し用バッファ102(第1格納部)を制御する第1バッファ制御部として機能することが可能である。
【0018】
読み出し用バッファ制御部103は処理に必要な画像データを、局所データ(部分画像)として、読み出し用バッファ102(第1格納部)に保持させるように不要な画像データを削除したり、新たな画像データを保持させたりする制御が可能である。また、読み出し用バッファ制御部(第1バッファ制御部)103は、必要に応じて、読み出し用バッファ102(第1格納部)における画像データの保持位置をシフトさせるなどの並べ替えを行うことも可能である。
【0019】
局所データ変換部104は、読み出し用バッファ制御部(第1バッファ制御部)103によって並べ替えられた入力画像の局所データ(部分画像)を順変換により、出力座標の位置に順次変換する座標変換を行い出力することが可能である。
【0020】
局所データ出力アドレス計算部105は、局所データ(部分画像)から、順変換による座標変換で必要となる出力座標点を算出することが可能である。
【0021】
順変換座標算出部106は、局所データ出力アドレス計算部105に、入力座標位置と変換マトリクスによって順変換方式で出力座標位置を求めることが可能である。
【0022】
一般的な画像処理においては、画像データはラスタ走査順に処理され、その画像処理結果はラスタ走査順に出力される。これに対して、回転処理は、入力側と出力側でデータの入出力の順番が異なる。入力側からラスタ走査順に画像データが入力され、回転された画像データは、回転角に従った傾きの方向に書き込まれることになる。このため、出力側では、入力順とは異なる書き込み用バッファ107へのアクセス(ランダムアクセス)が必要となる。この変換方式を以下、順変換方式という。
【0023】
書き込み用バッファ107は、局所データ変換部104により変換された出力用画像データを保持する。読み出し用バッファ102(第1格納部)に格納された部分画像(局所データ)は、局所データ変換部104により出力座標の位置に変換され、書き込み用バッファ107に格納される。書き込み用バッファ107は、出力座標の位置に変換された部分画像を格納する第2格納部として機能することが可能である。
【0024】
書き込み用バッファ制御部108は、書き込み用バッファ107(第2格納部)に効率よく出力データを保持させるための書き込みアドレスの制御を行う。書き込み用バッファ制御部108は、出力座標の位置に変換された部分画像を格納する第2格納部を制御する第2バッファ制御部として機能することが可能である。
【0025】
画像出力部109は、書き込み用バッファ107(第2格納部)に保持された出力用画像データを適宜、外部処理モジュールまたは外部メモリに出力する。
【0026】
(順変換による局所データの変換処理)
順変換による局所データの変換処理について図2を参照して説明する。図2では、入力画像が画素(ピクセル)単位に、矢印250で示す横方向に順次入力されてくるようなデータの流れを想定している。図2(a)に示すように、4画素を一度に処理することで処理回数を減らし、なおかつ読み出し用バッファ102(第1格納部)、書き込み用バッファ107(第2格納部)上での読み書き回数を低減させることができる。
【0027】
横方向の画素(ピクセル)4点210〜213に基づき出力される出力画素として、図2(a)中のAで示した領域に含まれる画素に限定することで、処理を簡素化しつつ、出力バッファ上での読み書きの回数を低減させるこがきる。
【0028】
原理的には、4点(4画素)全てが関与する範囲である図2(a)中にBで示す範囲に対して出力値を算出することが可能である。その場合、出力値に対する画素の関与の比率が出力画素ごとに異なってしまい、一律の処理によって出力値の算出処理を進めることが不可能になる。よって、本実施形態では、入力4点(4画素)に対してAで示した領域についてのみ出力を行うものとする。図中の「○」は出力画素を例示的に示すものである。
【0029】
次に、図2(b)に示すように、次の画素が1点(1画素分)入ってきたところで、最初に入力された画素を記憶領域から破棄し、新たに入力された1画素を含む4点(4画素)を保持することで同様の出力値の計算を行う。そして、図2(b)中Cで示す範囲に含まれる出力座標点への出力を行う。このようにして、1ラスタ目の画像入力については1ピクセルの入力毎に4点という非常に少ない保持データにより、順次出力画素を出力する。
【0030】
次に、図2(c)に示すように2ラスタ目の処理に移ると、4点により出力できる領域が上方向にもあることになるため、図中に領域Dに示すような領域に含まれる出力座標点への出力を行う。
【0031】
2ラスタ目についても1ラスタ目と同様、図2(d)に示すとおり次のピクセルが入力されたところで最初のピクセルを破棄し、新たな4点(4画素)について同様の処理を行うことで、順次処理を進めていくことができる。
【0032】
その後、図2(e)、(f)に示すように3ラスタ目、4ラスタ目と順次同様の処理を繰り返していくことで、出力画素を生成することが可能である。
【0033】
画像の下端については、図2(a)〜図2(d)に示した領域をちょうど上下反転したように処理することで、入力画像の境界部分での出力処理を境界以外の他の処理と同様に行うことが可能になる。一定の透過率による画像合成を行う場合には、予め出力バッファ上に描画されている画像をピクセル単位で読み出し、透過率によって決まる係数を掛けて書き戻しておくことにより、合成画像を得ることも可能である。
【0034】
次に、処理をより高速に実現するにあたって、画像上端・下端を除いた一般的な処理において、バッファ上での読み書き回数を減らすために最低限必要なバッファの構成について図3を用いて説明する。
【0035】
例えば、本実施形態の処理をキャッシュメモリなどのローカルバッファを持つハードウェアないしはCPUにおいて実現することも可能である。この場合、図3で示した領域に含まれる出力座標点分のサイズのローカルバッファを持つことにより、効果的に外部メモリへの書き込み回数を減らすことが可能である。この場合、バッファのサイズは、変倍率などによって変動する。拡大処理を行う場合、図中の領域に含まれる出力座標点は多くなり、縮小の場合には少なくなるからである。
【0036】
一般にローカルバッファのサイズには実装コスト上の制約があるため、変倍率に対しても制限が必要となる。しかし、本実施形態によれば、ローカルバッファに入らない領域の出力座標点については直接外部メモリに出力しておき、その後の処理時に再度読み出して処理をすればよく、ローカルバッファに全ての出力座標点の情報が含まれる必要はない。ローカルバッファの上限を超える変倍率を指定した際には、変倍率の増加に対して単調増加の傾向で処理負荷が重くなるだけであり、高速化と柔軟性を比較的制御性の良い形で両立することも可能である。
【0037】
また、ローカルバッファの構成では、画素が連続して入力される横方向の画素数分、ローカルバッファの幅を持つ必要がある。これを効果的に小さくするための方法について図4を用いて説明する。図4(a)中の参照番号401は、図2で示した入力されるデータの入力順を概略的に示している。このようにラスタ単位でデータを処理する場合、入力されるデータの入力順は参照番号401にようになる。この場合、多くの画像処理に対して適用可能であるが、反面、本実施形態で用意するべきバッファの容量は、図4中の参照番号402で示すように大きくなってしまう。
【0038】
これに対して、画像をバンド単位に処理する場合、画素の入力方向を縦方向にすることで、回転処理で必要となるローカルバッファの領域を90度回転させたものとすることができ、結果としてローカルバッファのサイズを小さく抑えることが可能である。
【0039】
次に、画像の回転を行う場合の局所データ変換部104の処理について図5を用いて説明する。回転においては、例えば、図2(e)の領域Fに、斜めに出力画素が並ぶことになる。この場合には、参照番号501に示した点に対してそれぞれ計算を行ったうえで積算処理を行う必要があるが、処理としてはこれまでに説明した処理と同様である。例えば、16点の補間の処理であっても、4画素(ピクセル)という非常に少ない入力画像の局所データの保持で、かつ、効率的な回転変倍を行うことができる。
【0040】
ただし、これだけでは、アフィン変換のための乗算処理を複数行う必要があるなど、ハードウェア化においては回路規模が大きくなる要素を残している。そこで、出力座標範囲と、その中に含まれる実際に出力を行うべき出力座標点の集合を簡単な演算で実施する構成を以下に説明する。
【0041】
アフィン変換と呼ばれる行列演算による変形では、「平行な直線は変換後も平行である」という性質を持っていることが知られている。このことは、すなわち直線によって囲まれた領域を変形する場合には、領域を囲む平行でない直線の数だけの傾き情報の変換によって図形の変換が可能であることを示している。
【0042】
こうしたことからアフィン変換における変換パラメータは、行列演算から求められる入力座標系の整数位置の単位移動量に対する変換後の単位移動量、すなわち傾きとして求められることになる。
【0043】
アフィン変換は、入力座標を(x,y)、出力座標を(X,Y)とすると、以下のように表される。
【0044】
【数1】
【0045】
ここで、デジタル画像処理では入出力座標位置は整数で表される位置に離散化されていることから、例えば(x,0)という点は、この式によって(ax+c,dx+f)という位置に写像される。
【0046】
【数2】
【0047】
更に、x+1という位置は、下式に示すように(ax+c+a,dx+f+d)という位置に写像されることになる。
【0048】
【数3】
【0049】
(3)式より明らかなように、入力座標系での隣の画素位置への移動は、出力座標系での(a,d)という傾きを持った移動となる。アフィン変換によって行われる座標変換は、入力座標系での一定の移動量は、出力座標系では変換された傾きを持った移動量となる事がわかる。このことから、アフィン変換では入力座標上のある点の変換座標と、そこからの移動量を傾きとして与えることで、変換後の出力位置を簡便に求められる可能性があることが分かる。
【0050】
逆行列が存在しない行列式による変換の場合には、入力画像上で互いに平行でなかった直線が平行になってしまったり、1点に集約されてしまったりするなどの現象が起きる。こうした場合には、ある1点の出力座標に対応する入力座標位置が無数に存在してしまうため、逆変換によって入力座標位置を求めることは単なる計算だけでは行えなくなる。このような場合でも、変換前には異なる傾きを持った直線が、変換後には同じ傾きを持つようになるというだけであり、その変換は傾きの変換によって行える。
【0051】
図6は、順変換により回転・変形・変倍を行った場合の座標値の簡便な求め方を説明する図である。アフィン変換による座標変換は、出力画像座標系に対して、入力画像座標が軸の平行性を保った形で写像される。入力座標系の座標点を白丸で示すと、正方形として配置する座標点は、アフィン変換を行うことにより、一般的に、黒丸で座標点を示す平行四辺形の配置に写像される。入力座標系のX座標、Y座標は、出力座標系でそれぞれd/a、e/bの傾きを持つ直線に写像されることになる。
【0052】
これにより、矩形領域を持つ画像の回転・変倍・変形処理を簡素化して行うことが可能になる。図7は、アフィン変換による回転・変倍・変形処理を行う場合の設定パラメータについて説明した図である。
【0053】
図7中に黒丸で示したのが出力座標上の画素点であり、四角で示したのが入力座標系の画素点である。入力画像の処理開始点を出力座標上に写像した位置(StartX, StartY)を基点とする。
【0054】
入力画像の点の出力座標上の配置は入力座標のX軸、Y軸が出力座標系上で持つ傾き(rate_x, rate_y)、(line_rate_x, line_rate_y)とを算出して求めることが可能である。
【0055】
アフィン変換による変倍後の座標計算は、(StartX, StartY), (rate_x, rate_y), (line_rate_x, line_rate_y)の6つのパラメータによって置き換えることが可能である。
【0056】
6つのパラメータは、アフィン変換を表現するための基本的なものであるが、これだけでは出力座標上の画素位置を求めることが困難である。なぜなら、入力画像の画素位置は、出力画像の画素位置の途中、つまり小数点以下の値を含む位置に一般に写像されるからである。出力画像を正しく求めるためには、こうした小数点を含む位置から整数によって表される出力座標格子点を求める計算を行わなければならない。
【0057】
このパラメータの与え方について、図8を用いて説明する。先に与えられた6つのパラメータから直線line1、line2、line3を求める。そして、出力座標系のY座標整数位置にある水平線との交点(図8の(CstartX1,CstartY1)、(CstartX2, CstartY2)および(CendX1,CendY1)、(CendX2, CendY2))を算出する。
【0058】
これは、ハードウェアで行うためには乗算器を含む比較的回路規模の大きな演算処理を必要とするため、安価な実施には不適当であるが、ソフトウェアによってあらかじめ求めることは実装上の負荷とはならない。これらの交点座標を初期値として与え、その後は傾きの情報を加算することで順次出力座標の範囲を求めることが可能である。これにより、ハードウェア実装負荷の低い加算器のみを用いてアフィン変換の順変換座標算出部を実施することが可能となり、安価な構成で、かつ高速な処理の実行が可能となる。
【0059】
図8のように、最初に入力される4点についての座標位置として(StartX,StartY)、(EndX, EndY)、(EndLineX, EndLineY)、(EndRectX, EndRectY)を求める(矩形範囲801)。これらはそれぞれ、所望のアフィン変換行列をかけることで求めることが可能である。
【0060】
n×mの参照点を持つフィルタの場合、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となるのが基本となる。
【0061】
しかしながら、フィルタサイズn、mは必ずしも偶数であるとは限らないことから、cn1,cn2,cm1,cm2が常にこのような単純な式で求められるとは限らない。また、入力画像の上端、下端、左端、右端においては、さらにこのcn1,cn2,cm1,cm2を図2に示したように変化させる制御を行う必要がある。但し、入力画素をn,mを考慮して画像の外に当たる部分も供給するなどの方法によって、処理に必要な画像を補うことで、こうした出力領域の制御を行わないように構成することも可能である。
【0062】
こうして求められた矩形範囲801について、(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の交点である。
【0063】
(StartX,StartY),(EndX, EndY),(EndLineX,EndLineY),(EndRectX, EndRectY)を出力座標領域算出の初期値として与える。その後は傾きの情報を加算することで順次出力座標における局所データの変換を求めることが可能になる。
【0064】
本実施形態の出力座標算出処理の流れを図9のフローチャートを参照して説明する。本処理は、局所データ変換部104、局所データ出力アドレス計算部105、順変換座標算出部106の制御の下に実行することが可能である。
【0065】
出力座標位置算出処理が開始されると、ステップS901で、入力座標CstartX1,CstartX2のうち、X座標の値が大きいほうを選択し、CstartXとする。
【0066】
ステップS902において、入力座標CendX1,CendX2のうち、X座標の小さいほうを選択し、CendXとする。
【0067】
ステップS903において、CstartY1,CstartY2, CendY1, CendY2は、全ての点について同じ値となるため、いずれかのCYを決定する。
【0068】
ステップS904において、CstartXを切り上げ、整数位置に移動させ、CXとする。
【0069】
ステップS905において、現在のCX,CYを出力座標位置として図1に示す局所データ出力アドレス計算部105に出力する。
【0070】
ステップS906において、CXに出力座標系で1を加算する。
【0071】
ステップS907において、もしCXが先に求めたCendXよりも小さければ(S907−Yes)、処理をステップS905に戻す。一方、ステップS907の判定で、CXがCendx以上の場合(S907−No)、処理はステップS908に進められる。
【0072】
ステップS908では、CYに1を加算する。
【0073】
ステップS909において、CYがEndRectYを超えていた場合には処理を終了する。一方、ステップS909の判定で、CYがEndRectYを超えていない場合(S909‐Yes)、処理はステップS910に進められる。
【0074】
ステップS910において、CstartX1にrate_y/rate_xを足すことにより、ステップS908で更新されたCYの水平線と、図8のline1との交点に移動させて、CstartX1の更新を行う。
【0075】
ステップS911において、CstartX2にline_rate_y/line_rate_xを足すことにより、CYの水平線と図8のline2との交点に移動させて、CstartX2の更新を行う。
【0076】
ステップS912において、CendX1にline_rate_y/line_rate_xを足すことにより、CYの水平線と図8のline3との交点に移動させて、CendX1の更新を行う。
【0077】
ステップS913において、CendX2にrate_y/rate_xを足すことにより、ステップS908で更新されたCYの水平線と、図8のline4との交点に移動させて、CendX2の更新を行い、処理をステップS901に戻す。そして、ステップS901〜S913まで同様の処理が繰り返される。
【0078】
本実施形態によれば、少ない容量のメモリを用いて、入力側の画像の座標から出力側の座標を求める順変換方式による行列演算によって回転・変倍・変形処理を高速で安価に実現する画像処理技術の提供が可能になる。
【0079】
(第2実施形態)
本実施形態における画像処理装置の構成を図10に示す。構成要素は(101〜109)、図1に示した構成と同一であるので、ここでは詳細な説明を省略する。本実施形態にかかる画像処理装置において、画像入力部101と読み出し用バッファ102との間でやりとりするデータ1010には、ピクセル情報だけでなく、座標情報も含む。
【0080】
画像処理に与える入力画像データは、必ずしも1ラスタ単位であるとは限らない。図4(a)で示したように横方向に1ラインずつ入力するケースのほかに、バンドに区切った部分画像について縦方向に順次データを入力する場合もありうるためである(図4(b))。このような様々な入力データの入力順序に臨機応変に対応するためには、図10のデータ1010に、座標情報も同時に含まれるようなデータ構造が必要となる。
【0081】
部分画像データ(ピクセルデータ)と座標情報とを同時に入力する場合の好適なデータの入力順序の例を図11に示す。
【0082】
データの入力順序は、2ラスタ1101をカラム単位で順次入力するものである。この場合、第1実施形態で既に説明した1ラスタ単位のデータ入力に比べ、一度に2ラスタ分のデータを(4)式により計算できる。(4)式において、ciは、横方向の変倍時のピクセル影響度を示す係数である。cjは縦方向の係数であり、Pinは局所画像範囲内の(i、j)の位置にある画素値である。そして、出力画像生成のための加算は(5)式により算出することができる。
【0083】
【数4】
【0084】
出力メモリまたは出力側ローカルメモリ上での積算回数が半分または半分+1回とすることが可能となり、特に出力バッファを応答速度の遅い外部メモリにおく場合には処理の高速化が期待できる。また、ある1点の出力点についての横方向の係数ciは、2ラスタについて同じ値が使用できるため、係数の算出にかかる処理速度も向上が図れる。
【0085】
2ラスタ単位でのデータ入力を行った場合に、出力側に持つべきローカルメモリの領域1201を図12に示す。
【0086】
2ラスタ入力の場合には、1ラスタ入力の場合(図3)に比べてバッファの重なり部分が小さくなることがわかる。このような領域をカバーする分のローカルメモリを持つことで、積算処理をローカルメモリで行うことができ、応答の遅い外部メモリへのアクセスは1回の書き込みに抑えることが可能となる。
【0087】
ローカルメモリ容量の限界を超えるフィルタサイズの処理を行う場合でも、はみ出した部分を外部メモリに割り当てることで処理を行うことが可能であり、ローカルメモリのサイズによって処理可能なフィルタサイズは制限を受けない。
【0088】
図13は、3ラスタをカラム単位1301で入力する状態を示す図である。
【0089】
この場合、先に示した式(4)、(5)式は、以下の(6)式、(7)式となる。
【0090】
【数5】
【0091】
出力メモリまたは出力側ローカルメモリ上での積算回数が1/3または1/3+1回とすることが可能となり、特に出力バッファを応答速度の遅い外部メモリにおく場合には処理の高速化が期待できる。また、ある1点の出力点についての横方向の係数ciは、3ラスタについて同じ値が使用できるため、係数の算出にかかる処理速度も更なる向上が図れる。
【0092】
尚、係数ci, cj、フィルタ、補間演算の参照点を選択することにより、局所データ変換処理の構成を変えずに、例えば、1次補間、3次補間などの処理を切り替えて実施する処理をハードウェアまたはソフトウェアに実装しても良い。
【0093】
更に、係数算出時に周囲の局所データの水平、垂直方向の距離を求めるステップにおいて、最も近傍の点を割り出す判断処理を追加することも可能である。この判断ステップの追加により局所データ変換部の構成を変えずに、0次補間(最近傍サンプリング処理)を行う処理をハードウェアまたはソフトウェアに実装することも可能である。
【0094】
(第3実施形態)
第3実施形態として、フィルタサイズと同じライン数のデータを入力として同時に与えた場合の処理を説明する。図14の参照番号1401で示した部分については、そもそも全てのフィルタ計算用の入力画素が一度に保持されていることから、積算の必要がない。図14の参照番号1402で示した領域については複数回の処理に分かれる積算処理が不要であるため、ローカルバッファへの保存を行う必要がない。ここでは単に積算処理が不要となる特別なケースを例示的に説明するものであり、外部メモリへの連続書き込み(バーストライト)を行うための一時保持バッファとしてローカルバッファを使用することは可能である。
【0095】
(第4実施形態)
図16は、画像データの入出力制限を例示的に説明する図である。画像領域1601は入力される画像データの全体を示す画像領域である。領域1602は、画像領域1601の中で処理されるべき領域を示している。領域1602の画像を全て処理した結果が、出力画像のデータを保持するバッファの領域1603に格納される。実際には、出力画像のデータを保持するバッファ容量が十分に確保できない等の理由により制限される場合がある。
【0096】
図17は、本実施形態に係る画像処理装置の構成を示す図である。図15の構成に対して、入力領域保持部1710、出力領域保持部1711が設けられている。尚、圧縮画像伸張部1501に代わり画像入力部101を設ける構成としてもよい。
【0097】
入力領域保持部1710は、入力画像の中で、処理すべき座標範囲を保持する。入力領域保持部1710が保持する座標範囲に基づき読み出し用バッファ制御部(第1バッファ制御部)103は入力された画像の座標が、処理すべき領域に含まれるか判定する。読み出し用バッファ制御部103は判定結果に基づいて入力された画像の座標が処理するべき座標範囲に含まれている場合、読み出し用バッファ102への格納と、読み出し用バッファ102から局所データ変換部104への出力を制御する。
【0098】
但し、補間演算などが必要となる変倍処理やフィルタ処理においては、入力領域に対してフィルタサイズや補間時に参照する周辺が元の範囲を考慮した上で入力画像(入力画素)の選別を行う処理を読み出し用バッファ制御部103が行う。
【0099】
出力領域保持部1711は、出力すべき領域の座標範囲の情報を保持する。書き込み用バッファ制御部(第2バッファ制御部)108は、座標の位置に変換された部分画像(出力画像)とその出力座標系での位置情報1730とに基づき、部分画像(出力画像)の位置情報が、出力すべき領域の座標範囲に含まれているか判定する。書き込み用バッファ制御部(第2バッファ制御部)108は判定結果により出力画像の位置情報が出力すべき領域の座標範囲に含まれている場合には、出力画像と位置情報とを書き込み用バッファ107に書き込み、画像出力部109に対する出力を制御する。
【0100】
(他の実施形態)
なお、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録したコンピュータ可読の記憶媒体を、システムあるいは装置に供給することによっても、達成されることは言うまでもない。また、システムあるいは装置のコンピュータ(またはCPUやMPU)が記憶媒体に格納されたプログラムコードを読出し実行することによっても、達成されることは言うまでもない。
【0101】
この場合、記憶媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【0102】
プログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、CD−ROM、CD−R、不揮発性のメモリカード、ROMなどを用いることができる。
【0103】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現される。また、プログラムコードの指示に基づき、コンピュータ上で稼働しているOS(オペレーティングシステム)などが実際の処理の一部または全部を行い、その処理によって前述した実施形態が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【0104】
【図1】第1実施形態に係る画像処理装置が備える構成要素を示す図である。
【図2】順変換による局所データの変換処理を説明する図である。
【図3】ローカルバッファを説明する図である。
【図4】ローカルバッファを説明する図である。
【図5】画像の回転を行う場合の局所データ変換部104の処理を説明する図である。
【図6】順変換により回転・変形・変倍を行った場合の座標値の求め方を説明する図である。
【図7】アフィン変換による回転・変倍・変形処理を行う場合の設定パラメータについて説明した図である。
【図8】アフィン変換による回転・変倍・変形処理を行う場合の設定パラメータについて説明した図である。
【図9】出力座標算出処理の流れを説明する図である。
【図10】第2実施形態に係る画像処理装置が備える構成要素を示す図である。
【図11】部分画像データと座標情報とを同時に引き渡す場合の好適なデータの入力順序の例を示す図である。
【図12】2ラスタ単位でのデータ入力を行った場合に、出力側に持つべきローカルメモリの領域を示す図である。
【図13】3ラスタをカラム単位1301で入力する状態を示す図である
【図14】フィルタサイズと同じライン数のデータを入力として同時に与えた場合の処理を説明する図である。
【図15】圧縮画像伸張部1501を備えた画像処理装置の構成を例示する図である。
【図16】画像データの入出力制限を例示的に説明する図である。
【図17】第4実施形態に係る画像処理装置の構成を示す図である。
【図18】画像中の一部分を回転しながら取り出す変換を例示的に説明する図である。
【特許請求の範囲】
【請求項1】
部分画像を格納する第1格納手段を制御する第1バッファ制御手段と、
前記第1格納手段に格納された前記部分画像を、出力座標の位置に順次変換する変換手段と、
前記変換手段により出力座標の位置に変換された部分画像を格納する第2格納手段を制御する第2バッファ制御手段と、
を備えることを特徴とする画像処理装置。
【請求項2】
前記部分画像と、当該部分画像の座標情報とを入力する画像入力手段を更に備え、
前記第1格納手段は、前記画像入力手段により入力された前記部分画像と当該部分画像の座標情報とを、前記第1バッファ制御手段の制御により格納することを特徴とする請求項1に記載の画像処理装置。
【請求項3】
圧縮された画像を伸張して出力する圧縮画像伸張手段を更に備え、
前記第1格納手段は、前記圧縮画像伸張手段により伸張された画像の部分画像と、当該部分画像に関する座標情報とを、前記第1バッファ制御手段の制御により格納することを特徴とする請求項1に記載の画像処理装置。
【請求項4】
入力された部分画像の中で、画像処理すべき部分画像の座標範囲の情報を保持する入力領域保持手段を更に備え、
前記第1バッファ制御手段は、前記座標範囲の情報に基づき、前記入力された部分画像の座標が前記画像処理すべき部分画像の座標範囲に含まれるか判定し、
前記第1バッファ制御手段は、前記判定に基づいて、前記入力された部分画像の座標が前記画像処理するべき部分画像の座標範囲に含まれている場合に、前記第1格納手段に、前記部分画像を書き込むように制御することを特徴とする請求項1に記載の画像処理装置。
【請求項5】
出力すべき領域の座標範囲の情報を保持する出力領域保持手段を更に備え、
前記第2バッファ制御手段は、前記変換手段により出力される出力画像の位置情報が、前記出力すべき領域の座標範囲に含まれているか判定し、
前記第2バッファ制御手段は、前記判定に基づいて、前記出力画像の位置情報が前記出力すべき領域の座標範囲に含まれている場合に、前記第2格納手段に、前記出力画像を書き込むように制御することを特徴とする請求項1に記載の画像処理装置。
【請求項6】
第1バッファ制御手段が、部分画像を格納する第1格納手段を制御する第1バッファ制御工程と、
変換手段が、前記第1格納手段に格納された前記部分画像を、出力座標の位置に順次変換する変換工程と、
第2バッファ制御手段が、前記変換工程により出力座標の位置に変換された部分画像を格納する第2格納手段を制御する第2バッファ制御工程と、
を備えることを特徴とする画像処理装置の制御方法。
【請求項7】
請求項6に記載の画像処理装置の制御方法をコンピュータに実行させることを特徴とするプログラム。
【請求項8】
請求項7に記載のプログラムを格納したことを特徴とするコンピュータ可読の記憶媒体。
【請求項1】
部分画像を格納する第1格納手段を制御する第1バッファ制御手段と、
前記第1格納手段に格納された前記部分画像を、出力座標の位置に順次変換する変換手段と、
前記変換手段により出力座標の位置に変換された部分画像を格納する第2格納手段を制御する第2バッファ制御手段と、
を備えることを特徴とする画像処理装置。
【請求項2】
前記部分画像と、当該部分画像の座標情報とを入力する画像入力手段を更に備え、
前記第1格納手段は、前記画像入力手段により入力された前記部分画像と当該部分画像の座標情報とを、前記第1バッファ制御手段の制御により格納することを特徴とする請求項1に記載の画像処理装置。
【請求項3】
圧縮された画像を伸張して出力する圧縮画像伸張手段を更に備え、
前記第1格納手段は、前記圧縮画像伸張手段により伸張された画像の部分画像と、当該部分画像に関する座標情報とを、前記第1バッファ制御手段の制御により格納することを特徴とする請求項1に記載の画像処理装置。
【請求項4】
入力された部分画像の中で、画像処理すべき部分画像の座標範囲の情報を保持する入力領域保持手段を更に備え、
前記第1バッファ制御手段は、前記座標範囲の情報に基づき、前記入力された部分画像の座標が前記画像処理すべき部分画像の座標範囲に含まれるか判定し、
前記第1バッファ制御手段は、前記判定に基づいて、前記入力された部分画像の座標が前記画像処理するべき部分画像の座標範囲に含まれている場合に、前記第1格納手段に、前記部分画像を書き込むように制御することを特徴とする請求項1に記載の画像処理装置。
【請求項5】
出力すべき領域の座標範囲の情報を保持する出力領域保持手段を更に備え、
前記第2バッファ制御手段は、前記変換手段により出力される出力画像の位置情報が、前記出力すべき領域の座標範囲に含まれているか判定し、
前記第2バッファ制御手段は、前記判定に基づいて、前記出力画像の位置情報が前記出力すべき領域の座標範囲に含まれている場合に、前記第2格納手段に、前記出力画像を書き込むように制御することを特徴とする請求項1に記載の画像処理装置。
【請求項6】
第1バッファ制御手段が、部分画像を格納する第1格納手段を制御する第1バッファ制御工程と、
変換手段が、前記第1格納手段に格納された前記部分画像を、出力座標の位置に順次変換する変換工程と、
第2バッファ制御手段が、前記変換工程により出力座標の位置に変換された部分画像を格納する第2格納手段を制御する第2バッファ制御工程と、
を備えることを特徴とする画像処理装置の制御方法。
【請求項7】
請求項6に記載の画像処理装置の制御方法をコンピュータに実行させることを特徴とするプログラム。
【請求項8】
請求項7に記載のプログラムを格納したことを特徴とするコンピュータ可読の記憶媒体。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【公開番号】特開2008−192073(P2008−192073A)
【公開日】平成20年8月21日(2008.8.21)
【国際特許分類】
【出願番号】特願2007−28443(P2007−28443)
【出願日】平成19年2月7日(2007.2.7)
【出願人】(000001007)キヤノン株式会社 (59,756)
【Fターム(参考)】
【公開日】平成20年8月21日(2008.8.21)
【国際特許分類】
【出願日】平成19年2月7日(2007.2.7)
【出願人】(000001007)キヤノン株式会社 (59,756)
【Fターム(参考)】
[ Back to top ]