(57)【特許請求の範囲】
【請求項１】
第１の画像を出力するための第１のデータから、前記第１の画像がアフィン変換された第２の画像を出力するための第２のデータを生成する装置であって、
前記第１のデータが格納された第１の記録媒体から、前記第１の画像の隣接する第１の原走査線および第２の原走査線に含まれる複数の画素を出力するための原走査線データを取得する第１の入力ユニットと、
前記原走査線データから、前記第２の画像の複数の画素を出力するための画素データを生成する補間演算ユニットとを有し、
前記画素データには、前記第２の画像の複数の走査線の線分に含まれる複数の画素を出力するための線分データが含まれており、
さらに、それぞれの線分データを含むブロックデータを入出力単位として第２の記録媒体に格納する第１の出力ユニットと、
前記第２の記録媒体から、前記第２の画像の走査線を出力するための複数の線分データを含む複数のブロックデータを取得する第２の入力ユニットと、
前記第２の画像の走査線に含まれる複数の画素を出力するための走査線データを前記第２のデータとして第３の記録媒体に格納する第２の出力ユニットとを有し、さらに、
前記第１の出力ユニットは、前記ブロックデータを、前記第２の画像の走査線の順番で読みだされるようにアドレスを変えて、前記第２の記録媒体に格納する、装置。
【請求項２】
請求項１において、前記第１の出力ユニットは、前記ブロックデータを固定長で前記第２の記録媒体に格納する、装置。
【請求項３】
請求項２において、前記第１の出力ユニットは、前記ブロックデータをバースト長で前記第２の記録媒体に格納する、装置。
【請求項４】
第１の画像を出力するための第１のデータから、前記第１の画像がアフィン変換された第２の画像を出力するための第２のデータを生成する装置であって、
前記第１のデータが格納された第１の記録媒体から、前記第１の画像の隣接する第１の原走査線および第２の原走査線に含まれる複数の画素を出力するための原走査線データを取得する第１の入力ユニットと、
前記原走査線データから、前記第２の画像の複数の画素を出力するための画素データを生成する補間演算ユニットとを有し、
前記画素データには、前記第２の画像の複数の走査線の線分に含まれる複数の画素を出力するための線分データが含まれており、
さらに、それぞれの線分データを含むブロックデータを入出力単位として第２の記録媒体に格納する第１の出力ユニットと、
前記第２の記録媒体から、前記第２の画像の走査線を出力するための複数の線分データを含む複数のブロックデータを取得する第２の入力ユニットと、
前記第２の画像の走査線に含まれる複数の画素を出力するための走査線データを前記第２のデータとして第３の記録媒体に格納する第２の出力ユニットとを有し、さらに、
前記第２の入力ユニットは、前記ブロックデータを、前記第２の画像の走査線の順番で読みだすようにアドレスを変えて、前記第２の記録媒体から取得する、装置。
【請求項５】
第１の画像を出力するための第１のデータから、前記第１の画像がアフィン変換された第２の画像を出力するための第２のデータを生成する装置であって、
前記第１のデータが格納された第１の記録媒体から、前記第１の画像の隣接する第１の原走査線および第２の原走査線に含まれる複数の画素を出力するための原走査線データを取得する第１の入力ユニットと、
前記原走査線データから、前記第２の画像の複数の画素を出力するための画素データを生成する補間演算ユニットとを有し、
前記画素データには、前記第２の画像の複数の走査線の線分に含まれる複数の画素を出力するための線分データが含まれており、
さらに、それぞれの線分データを含むブロックデータを入出力単位として第２の記録媒体に格納する第１の出力ユニットと、
前記第２の記録媒体から、前記第２の画像の走査線を出力するための複数の線分データを含む複数のブロックデータを取得する第２の入力ユニットと、
前記第２の画像の走査線に含まれる複数の画素を出力するための走査線データを前記第２のデータとして第３の記録媒体に格納する第２の出力ユニットとを有し、さらに、
前記補間演算ユニットは、副走査方向の補間により、それぞれの線分データに含まれる複数の画素を出力するためのデータを並列に生成する第１の演算回路と、
走査方向の補間により、それぞれの線分データに含まれる複数の画素を出力するためのデータを並列に生成する第２の演算回路とを含み、
前記第１の出力ユニットは、前記第１の演算回路から出力された線分データを含むブロックデータを前記第２の記録媒体に格納し、
前記第２の演算回路は、前記第２の入力ユニットにより取得された線分データを走査方向に補正して、補正後の線分データを生成する、装置。
【請求項６】
第１の画像を出力するための第１のデータから、前記第１の画像がアフィン変換された第２の画像を出力するための第２のデータを生成する装置であって、
前記第１のデータが格納された第１の記録媒体から、前記第１の画像の隣接する第１の原走査線および第２の原走査線に含まれる複数の画素を出力するための原走査線データを取得する第１の入力ユニットと、
前記原走査線データから、前記第２の画像の複数の画素を出力するための画素データを生成する補間演算ユニットとを有し、
前記画素データには、前記第２の画像の複数の走査線の線分に含まれる複数の画素を出力するための線分データが含まれており、
さらに、それぞれの線分データを含むブロックデータを入出力単位として第２の記録媒体に格納する第１の出力ユニットと、
前記第２の記録媒体から、前記第２の画像の走査線を出力するための複数の線分データを含む複数のブロックデータを取得する第２の入力ユニットと、
前記第２の画像の走査線に含まれる複数の画素を出力するための走査線データを前記第２のデータとして第３の記録媒体に格納する第２の出力ユニットとを有し、
前記補間演算ユニットは、副走査方向の補間により、それぞれの線分データに含まれる複数の画素を出力するためのデータを並列に生成する第１の演算回路を含み、
当該装置は、さらに、回路を再構成可能な再構成可能ユニットと、前記再構成可能ユニットに回路を構成する制御ユニットとを有し、
前記制御ユニットは、前記再構成可能ユニットに、前記第１の入力ユニット、前記第１の演算回路、および前記第１の出力ユニットを含む第１段階の回路を構成し、第２段階として、前記第２の入力ユニット、および前記第２の出力ユニットを含む第２段階の回路を構成する、装置。
【請求項７】
回路を再構成可能な再構成可能ユニットと、前記再構成可能ユニットに回路を構成する制御ユニットとを有する装置を、前記制御ユニットにより制御する方法であって、
第１の画像を出力するための第１のデータから、前記第１の画像がアフィン変換された第２の画像を出力するための第２のデータを生成することを有し、
前記生成することは、
前記再構成可能ユニットに第１段階の回路を構成することと、
前記再構成可能ユニットに第２段階の回路を構成することとを含み、
前記第１段階の回路は、
前記第１のデータが格納された第１の記録媒体から、前記第１の画像の隣接する第１の原走査線および第２の原走査線に含まれる複数の画素を出力するための原走査線データを取得する第１の入力ユニットと、
前記原走査線データから、前記第２の画像の複数の画素を出力するための画素データを生成する補間演算ユニットとを含み、
前記画素データには、前記第２の画像の複数の走査線の線分に含まれる複数の画素を出力するための線分データが含まれており、
さらに、前記第１段階の回路は、それぞれの線分データを含むブロックデータを入出力単位として第２の記録媒体に格納する第１の出力ユニットを含み、
前記第２段階の回路は、
前記第２の記録媒体から、前記第２の画像の走査線を出力するための複数の線分データを含む複数のブロックデータを取得する第２の入力ユニットと、
前記第２の画像の走査線に含まれる複数の画素を出力するための走査線データを前記第２のデータとして第３の記録媒体に格納する第２の出力ユニットとを含む、方法。
【請求項８】
第１の画像を出力するための第１のデータから、前記第１の画像がアフィン変換された第２の画像を出力するための第２のデータを生成する方法であって、
前記第１のデータが格納された第１の記録媒体から、前記第１の画像の隣接する第１の原走査線および第２の原走査線に含まれる複数の画素を出力するための原走査線データを取得することと、
前記原走査線データから、前記第２の画像の複数の画素を出力するための画素データを生成することとを有し、
前記画素データには、前記第２の画像の複数の走査線の線分に含まれる複数の画素を出力するための線分データが含まれており、
さらに、それぞれの線分データを含むブロックデータを入出力単位として第２の記録媒体に前記第２の画像の走査線の順番で読みだされるようにアドレスを変えて格納することと、
前記第２の記録媒体から、前記第２の画像の走査線を出力するための複数の線分データを含む複数のブロックデータを取得することと、
前記第２の画像の走査線に含まれる複数の画素を出力するための走査線データを前記第２のデータとして第３の記録媒体に格納することとを有する、方法。
【請求項９】
請求項８において、前記格納することは、前記第２の記録媒体に、前記ブロックデータを固定長で格納することを含む、方法。
【請求項１０】
請求項８において、前記格納することは、前記第２の記録媒体に、前記ブロックデータをバースト長で格納することを含む、方法。
【請求項１１】
第１の画像を出力するための第１のデータから、前記第１の画像がアフィン変換された第２の画像を出力するための第２のデータを生成する方法であって、
前記第１のデータが格納された第１の記録媒体から、前記第１の画像の隣接する第１の原走査線および第２の原走査線に含まれる複数の画素を出力するための原走査線データを取得することと、
前記原走査線データから、前記第２の画像の複数の画素を出力するための画素データを生成することとを有し、
前記画素データには、前記第２の画像の複数の走査線の線分に含まれる複数の画素を出力するための線分データが含まれており、
さらに、それぞれの線分データを含むブロックデータを入出力単位として第２の記録媒体に格納することと、
前記第２の記録媒体から、前記第２の画像の走査線を出力するための複数の線分データを含む複数のブロックデータを、前記第２の画像の走査線の順番で読みだすようにアドレスを変えて取得することと、
前記第２の画像の走査線に含まれる複数の画素を出力するための走査線データを前記第２のデータとして第３の記録媒体に格納することとを有する、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アフィン変換された画像を出力するためのデータを生成する装置に関するものである。
【背景技術】
【０００２】
平面図形（立体図形の投影も含む）から平面図形への変換の１つとしてアフィン変換が知られている。アフィン変換は、平行線が平行線に変換される変換であり、図形を所定の角度回転させたり、スキュー補正を施すためなどに用いられる。
【０００３】
アフィン変換においては、ｘ−ｙ座標系により生成された画像データ（輝度データなどを含む）を、ｘ−ｙ座標系をθ回転したｗ−ｚ座標系における画像データに変換する。回転座標系は、以下の式（Ａ）で表わされる。Ｒ（θ）はアフィン変換行列である。
（ｗ，ｚ）=Ｒ（θ）（ｘ，ｙ）    ・・・（Ａ）
【０００４】
画像データはライン（走査線）上に記憶されているＲＧＢの輝度データであり、回転座標系における第Ｚ番目のラインデータを形成するには、以下の式（Ｂ）により、メモリに記憶されるとびとびのアドレスへアクセスしなければならず、処理速度を向上することが難しい。
ｘ＝Ｒ^(-1)（θ）（ｗ，Ｚ）
ｙ＝Ｒ^(-1)（θ）（ｗ，Ｚ）    ・・・（Ｂ）
【０００５】
特許文献１では、画像データは大容量低速メモリからブロック単位で読みだされ、小容量高速メモリに格納される。アドレス生成部で生成されたアドレスにしたがってさらに読み出され、補間演算を行う演算部でスキュー補正がおこなわれる。アドレス生成部は、入力画像の傾きに応じた角度でメモリから斜め方向にブロック単位で読みだすべく、その少数部を所定の精度で近似してアドレスを順次生成し、かつ、アドレスを精度に応じた周期で所定量だけ増減することで近似によるアドレスの累積誤差を抑制する。一方、小容量高速メモリからは、補正後の画素に隣接する４点の画像データの座標を、アフィン逆行列を用いて演算し、取得している。
【特許文献１】特開２００５−３５２７０３
【発明の開示】
【発明が解決しようとする課題】
【０００６】
特許文献１に記載された技術では、大容量低速メモリから小容量高速メモリにブロック単位で読みだされる。しかしながら、小容量高速メモリからは、補正する画素毎に、補正に必要なデータを読み出す必要があり、ランダムアクセスを必要とする。したがって、データを入出力する処理時間が、画像データを変換するための処理時間のクリティカルパスおよび／またはボトルネックとなり、画像処理に要する時間をさらに短縮することが難しい。
【０００７】
コピー機や画像を編集するアプリケーションにおいて、画像の微小な傾きを補正する処理（スキュー補正処理）の頻度は高く、この処理を高速で行えることは重要である。２度以下あるいは１度以下の画像の傾きであっても、直線部分が斜めに表示されることは、特にデジタル化された画像では目立つことが多い。また、微小な傾きを補正した画像を繰り返し表示することにより、ユーザは適切に傾きが補正された画像を選択することが可能となる。
【課題を解決するための手段】
【０００８】
本発明の一態様は、第１の画像を出力するための第１のデータから、第１の画像がアフィン変換された第２の画像を出力するための第２のデータを生成する装置である。この装置は、第１のデータが格納された第１の記録媒体から、第１の画像の隣接する第１の原走査線および第２の原走査線に含まれる複数の画素を出力するための原走査線データを取得する第１の入力ユニットと、原走査線データから、第２の画像の複数の画素を出力するための画素データを生成する補間演算ユニットとを有する。画素データには、第２の画像の複数の走査線の線分に含まれる複数の画素を出力するための線分データが含まれている。この装置は、さらに、それぞれの線分データを含むブロックデータを入出力単位として第２の記録媒体に格納する第１の出力ユニットと、第２の記録媒体から、第２の画像の走査線を出力するための複数の線分データを含む複数のブロックデータを取得する第２の入力ユニットと、第２の画像の走査線に含まれる複数の画素を出力するための走査線データを第２のデータとして第３の記録媒体に格納する第２の出力ユニットとを有する。
【０００９】
第１の画像の第１の走査線と第２の走査線とに含まれる画素を用いて生成（補間）された複数の画素（アフィン変換後の画素）は、第１の走査線と第２の走査線との間に存在する画素であり、第２の画像の複数の走査線の一部（線分）に含まれる画素となる。アフィン変換は平行線を平行線に変換する処理であり、基本的にはそれらの線分が重なることはなく、変換する角度が適当な範囲内であれば、１つの線分に、走査方向（主走査方向）に隣接する複数の画素が含まれる。すなわち、原走査線データから生成される画素データには、複数の線分データが含まれ、それぞれの線分データには複数の画素を出力するためのデータが含まれる。したがって、線分単位で、複数の画素を出力するためのデータ（線分データ）をメモリなどの記録媒体にいったん格納し、第２の画像の走査線の順番に線分データを読み出して第２の画像の走査線データを生成することにより、画素を出力するためのデータを、画素毎にランダムに読み出す処理を省くことができる。このため、アフィン変換を含めた画像処理におけるデータの入出力時間を短縮できる。
【００１０】
走査方向は、画像を出力するための走査方向に限らず、この装置において、画像データを入力するための方向であっても良い。それぞれの線分データを含むブロックデータを入出力単位とすることは、１つの線分データを１つのブロックデータに含めて格納しても良く、１つの線分データを複数のブロックデータに分けて格納しても良い。
【００１１】
第１の出力ユニットは、ブロックデータを固定長で第２の記録媒体に格納することが望ましい。データの入出力時間をさらに短縮できる可能性がある。第１の出力ユニットは、ブロックデータをバースト長で第２の記録媒体に格納することが望ましい。データの入出力時間をさらに短縮できる可能性がある。線分データが圧縮などの処理により可変長であっても、パディングデータを付加するなどの処理により、固定長で入出力することが可能である。
【００１２】
本発明の一形態において、第１の出力ユニットは、ブロックデータを、第２の画像の走査線の順番で読みだされるようにアドレスを変えて、第２の記録媒体に格納する。第２の入力ユニットは、シーケンシャルにブロックデータを読み込み、第２の出力ユニットは、第２の画像の走査線データを出力できる。
【００１３】
本発明の他の形態において、第２の入力ユニットは、ブロックデータを、第２の画像の走査線の順番で読みだすようにアドレスを変えて、第２の記録媒体から取得する。第１の出力ユニットは、ブロックデータをシーケンシャルに出力できる。
【００１４】
本発明のさらに異なる他の形態において、補間演算ユニットは、副走査方向の補間により、それぞれの線分データに含まれる複数の画素を出力するためのデータを並列に生成する第１の演算回路を含む。並列処理により、演算処理に要する時間を短縮できる。補間演算ユニットは、走査方向の補間により、それぞれの線分データに含まれる複数の画素を出力するためのデータを並列に生成する第２の演算回路をさらに含む。
【００１５】
第１の出力ユニットは、第１の演算回路から出力された線分データを含むブロックデータを第２の記録媒体に格納し、第２の演算回路は、第２の入力ユニットにより取得された線分データを走査方向に補正して、補正後の線分データを生成することが可能である。この装置では、ブロックデータを第２の記録媒体に入出力することを要するので、補間演算を２段階に分けて実行しても良く、回路を再構成可能なデバイスに実装する場合に、演算に要するハードウェアリソースの専有量を削減できる。
【００１６】
すなわち、本装置は、回路を再構成可能な再構成可能ユニットと、再構成可能ユニットに回路を構成する制御ユニットとを有することが望ましい。制御ユニットは、再構成可能ユニットに、第１の入力ユニット、第１の演算回路、および第１の出力ユニットを含む第１段階の回路を構成し、第２段階として、第２の入力ユニット、および第２の出力ユニットを含む第２段階の回路を構成する。第２の演算回路は、この処理のために使用可能な再構成可能ユニットのハードウェアリソースの量により、第１段階の回路に含めても良く、第２段階の回路に含めても良い。
【００１７】
本発明の他の態様の１つは、回路を再構成可能な再構成可能ユニットと、再構成可能ユニットに回路を構成する制御ユニットとを有する装置を、制御ユニットにより制御する方法である。この方法は、第１の画像を出力するための第１のデータから、第１の画像がアフィン変換された第２の画像を出力するための第２のデータを生成することを有する。さらに、生成することは、再構成可能ユニットに第１段階の回路を構成することと、再構成可能ユニットに第２段階の回路を構成することとを含む。
【００１８】
第１段階の回路は、第１のデータが格納された第１の記録媒体から、第１の画像の隣接する第１の原走査線および第２の原走査線に含まれる複数の画素を出力するための原走査線データを取得する第１の入力ユニットと、原走査線データから、第２の画像の複数の画素を出力するための画素データを生成する補間演算ユニットとを含む。画素データには、第２の画像の複数の走査線の線分に含まれる複数の画素を出力するための線分データが含まれている。さらに、第１段階の回路は、それぞれの線分データを含むブロックデータを入出力単位として第２の記録媒体に格納する第１の出力ユニットを含む。
【００１９】
第２段階の回路は、第２の記録媒体から、第２の画像の走査線を出力するための複数の線分データを含む複数のブロックデータを取得する第２の入力ユニットと、第２の画像の走査線に含まれる複数の画素を出力するための走査線データを第３の記録媒体に格納する第２の出力ユニットと含む。
【００２０】
本発明のさらなる態様の１つは、第１の画像を出力するための第１のデータから、第１の画像がアフィン変換された第２の画像を出力するための第２のデータを生成する方法であって、以下の工程を含む。
１．  第１のデータが格納された第１の記録媒体から、第１の画像の隣接する第１の原走査線および第２の原走査線に含まれる複数の画素を出力するための原走査線データを取得すること。
２．  原走査線データから、第２の画像の複数の画素を出力するための画素データを生成すること。画素データには、第２の画像の複数の走査線の線分に含まれる複数の画素を出力するための線分データが含まれている。
３．  それぞれの線分データを含むブロックデータを入出力単位として第２の記録媒体に格納すること。
４．  第２の記録媒体から、第２の画像の走査線を出力するための複数の線分データを含む複数のブロックデータを取得すること。
５．  第２の画像の走査線に含まれる複数の画素を出力するための走査線データを第３の記録媒体に格納すること。
【００２１】
第２の記録媒体には、ブロックデータを固定長で格納することが望ましく、バースト長で格納することがさらに望ましい。
【００２２】
１つの形態において、第２の記録媒体には、ブロックデータを、第２の画像の走査線の順番で読みだされるようにアドレスを変えて格納する。他の形態においては、第２の記録媒体から、ブロックデータを、第２の画像の走査線の順番で読みだすようにアドレスを変えて取得する。
【発明を実施するための最良の形態】
【００２３】
図１は、本発明の一実施形態である、画像データを生成する装置の基本構成ブロック図である。この画像処理装置あるいは生成装置５０は、回路を再構成可能なデバイス（処理装置）１を用いて実現されている。生成装置５０としての機能は、第１段階の回路５１と、第２段階の回路５２とに分けて、処理装置１の再構成可能領域１０に構成される。この装置５０は、第１の画像Ｇ１を出力するための第１のデータＤ１から、第１の画像Ｇ１がアフィン変換された第２の画像Ｇ２を出力するための第２のデータＤ２を生成する装置である。装置５０は、記録媒体であるメモリ５９を有し、メモリ５９には、第１のデータＤ１と、第２のデータＤ２と、さらに、中間段階のデータＭＤが格納されるようになっている。再構成可能領域１０に構成される第１段階の回路５１は、メモリ５９からデータを読み取る第１の入力ユニット６１と、補間演算を行う第１の補間演算ユニット６３と、第１の補間演算ユニットにより生成されたデータを複数のブロックに分ける（ブロック化する）ブロックデータ生成部６６と、それらのブロックをメモリ５９の所定のアドレスに書き込む第１の出力ユニット６２と、第１段階の制御情報生成ユニット６９とを含む。
【００２４】
第１の入力ユニット６１は、メモリ５９の第１のデータＤ１から、第１の画像Ｇ１の隣接する第１の原走査線および第２の原走査線（以降では、第１のラインＬ１および第２のラインＬ２）に含まれる複数の画素を出力するための原走査線データＥ１を取得する。第１の補間演算ユニット６３は、原走査線データＥ１から、第２の画像Ｇ２の複数の画素を出力するための画素データＰ１を生成するためのユニットである。本例の第１の補間演算ユニット６３は、特に、原走査線データＥ１に含まれる第１および第２のラインのデータから副走査方向の補間を行い、第２の画像Ｇ２の画素データＰ１を生成する。後述するように、第１の画像Ｇ１の、第１および第２のラインのデータを補間して生成される画素データＰ１には、第２の画像Ｇ２の複数の走査線の線分ＬＳに含まれる複数の画素を出力するための線分データＬＳＤが含まれている。第１の出力ユニット６２は、それぞれの線分データＬＳＤを含むブロックデータを入出力単位とし、中間段階のデータＭＤの一部としてメモリ５９に格納する。
【００２５】
再構成可能領域１０に構成される第２段階の回路５２は、メモリ５９から線分データＬＳＤを読み込む第２の入力ユニット７１と、第２の補間演算ユニット７３と、読み出された線分データＬＳＤから第２の画像Ｇ２を出力するため走査線データを生成するラインデータ生成ユニット７６と、第２のデータＤ２をメモリ５９に格納する第２の出力ユニット７２と、第２段階の制御情報生成ユニット７９とを含む。
【００２６】
第２の入力ユニット７１は、メモリ５９から、第２の画像Ｇ２の走査線Ｌ３を出力するための複数の線分データＬＳＤを含む複数のブロックデータを順番に取得する。第２の補間演算ユニット７３は、走査方向の補間を行い、線分データＬＳＤを補正または再生成する。第２の出力ユニット７２は、走査線Ｌ３に含まれる複数の画素を出力するための走査線データを第２のデータＤ２の一部としてメモリ５９に格納する。
【００２７】
制御情報生成ユニット６９および７９は、ユーザあるいはアプリケーションプログラムなどにより与えられる回転角度によりメモリ５９に対して入出力するためのブロックサイズを適切に決め、入出力のアドレスを生成あるいは管理するための情報を各ユニットに提供する。
【００２８】
図２ないし図４を参照して、この生成装置５０において、座標ｘ−ｙで示される原画像（第１の画像）をアフィン変換して、座標ｗ−ｚで示される第２の画像を生成する基本的なアルゴリズムを説明する。この生成装置５０は、微小角回転、たとえば、回転角θが±２度程度以内のアフィン変換（微小角アフィン変換）を高速に行うことを目的としたものである。たとえば、Ａ４版（２１０ｍｍ×２９７ｍｍ）の原画像（第１の画像）Ｇ１を解像度３００ＤＰＩでスキャナーにより読み込んだ場合、画素数２５２０×３５６０（合計９Ｍ画素）の画像データ（第１のデータ）Ｄ１が得られる。また、各々の画素を表示する輝度データは８ビットとする。ここで、第１の画像Ｇ１の短辺（Ｘ方向）をスキャン方向として、ある角度θだけ回転させ、Ｗ方向をスキャン方向（走査方向、Ｚ方向を副走査方向）とする第２の画像Ｇ２を得る。
【００２９】
図２に示すように、第１の画像Ｇ１の副走査方向Ｙに隣接し、走査方向Ｘに延びた２つの走査線（ライン）ＯＬ１およびＯＬ２に含まれる複数の画素のデータを補間して、第２の画像Ｇ２の画素を生成する。この場合、第１の画像Ｇ１の２つの走査線（以降では原ライン）ＯＬ１およびＯＬ２の間には、第２の画像Ｇ２の複数の走査線（以降では、ラインまたはニューライン）Ｌ（ｎ）からＬ（ｎ＋ｉ）の線分ＬＳ（ｎ（１））から線分ＬＳ（ｎ＋ｉ（ｉ＋１））（ｉおよびｎは整数）に含まれる画素が生成される。図２には、原ラインＯＬ１およびＯＬ２の間に、３つのラインＬｎ〜Ｌｎ＋２の線分ＬＳ（ｎ（１））、ＬＳ（ｎ＋１（２））およびＬＳ（ｎ＋２（３））が含まれる場合を模式的に示している。３００ＤＰＩの第１のデータＤ１においては、第１の画像Ｇ１の隣接する原走査線ＯＬ１およびＯＬ２の間には、回転角θが１度の場合は、第２の画像Ｇ２の４４個の走査線の線分ＬＳが含まれ、回転角θが２度の場合は、８８個の走査線の線分ＬＳが含まれる。
【００３０】
生成装置５０は、回転角θが２度の場合には、第１の画像Ｇ１の画像データＤ１の原ラインＯＬ１およびＯＬ２に含まれる画素の輝度データを含む原走査線データＥ１を読み込む。次に、８８個の変換後の走査線の線分ＬＳを演算し、それぞれの線分データＬＳＤを固定長８ワードのブロックデータとしてメモリ５９に格納する。すなわち、１つの線分ＬＳには２９個または２８個の画素の輝度データが含まれ、１つの線分データＬＳＤは２３２ビットまたは２２４ビットのデータとなる。このため、生成装置５０は、８ワード（２５６ビット）に足らない部分はパディングし、８ワードの固定長のブロックデータとしてメモリ５９に格納する。８ワードのブロックデータは、メモリ５９のバースト単位の１つであり、高速で入出力することができる。
【００３１】
図３に示すように、生成装置５０は、メモリ５９の画像データ（データファイル）Ｄ１から、副走査方向Ｙの原走査線データＥ１を連続して読み込み、走査方向（主走査方向、走査線方向）Ｘに補間を行って線分データを生成してブロックデータ化し、メモリ５９に、中間データ（データファイル）ＭＤとして格納する。画像データＤ１から、２ライン分の原画像データＥ１を読み込んでも良い。また、生成装置５０にラインバッファを用意し、１ライン分の原画像データＥ１を読み込み、ラインバッファに残された前のライン分の原画像データと合わせて、実質的に２ライン分の原画像データを取得するようにしても良い。生成装置５０は、第１の画像Ｇ１の１画像分のデータＤ１について、この処理を繰り返し、第２の画像Ｇ２に含まれる線分データを生成して、中間データファイルＭＤに格納する。線分データＬＳＤが生成され、中間データファイルＭＤに格納される順番は、例えば、ＬＳＤ（ｎ（１））、ＬＳＤ（ｎ＋１（２））、ＬＳＤ（ｎ＋２（３））、ＬＳＤ（ｎ＋１（１）、ＬＳＤ（ｎ＋２（２））、ＬＳＤ（ｎ＋３（３））というようになる。
【００３２】
図４に示すように、生成装置５０は、メモリ５９の中間データファイルＭＤから、線分データを含むブロックデータを、第２の画像Ｇ２の走査線Ｌ３に従って読みだす。たとえば、中間データファイルＭＤから読みだされる順番は、ＬＳＤ（ｎ（１））、ＬＳＤ（ｎ（２））、ＬＳＤ（ｎ（３））、ＬＳＤ（ｎ＋１（１））、ＬＳＤ（ｎ＋１（２））、ＬＳＤ（ｎ＋１（３））というようになる。生成装置５０は、さらに、読みだした複数の線分データＬＳＤから１つの走査線データを生成し、メモリ５９の画像データファイルＤ２に格納し、第２の画像Ｇ２を出力するための画像データＤ２を生成する。
【００３３】
図５に示すように、線分データＬＳＤｎ（１）は、パディングデータｐｄが加えられて、固定長のバーストサイズ（８ワード）のブロックデータＢＤ（ｎ（１））として、中間データファイルＭＤに格納される。他の線分データＬＳについても同様である。したがって、個々のブロックデータＢＤのメモリ５９に対する入出力は高速に行われる。それとともに、入出力アドレスを指定することにより所望のブロックデータＢＤをメモリ５９の適当なアドレスにランダムに格納でき、また、所望のブロックデータＢＤをランダムに取得できる。この入出力は、メモリ５９に対するランダムアクセスではなく、ブロック単位のバーストアクセスであり、メモリ５９に対する入出力は最速で行われる。
【００３４】
図６（ａ）および（ｂ）に、中間データファイルＭＤにブロックデータＢＤを格納する２つの例を示している。図６（ａ）は、第２の画像Ｇ２の走査線データを生成するときにブロックデータＢＤを中間データファイルＭＤからシーケンシャルに読み出せるようにしたものである。図６（ｂ）は、第１の画像Ｇ１の走査線データから線分データＬＳＤを生成した順番でシーケンシャルにブロックデータＢＤを中間データファイルＭＤに格納するようにしたものである。
【００３５】
Ａ４版（２１０ｍｍ×２９７ｍｍ）の原画像（第１の画像）Ｇ１を解像度３００ＤＰＩでスキャナーにより読み込んだ場合、回転角θが±２度であれば、上述したように、１つの線分データＬＳＤは２３２ビットまたは２２４ビットなので、８ワードをバーストサイズとする固定長のブロックデータＢＤにパッキングすることが望ましい。回転角θが±１度であれば、１つの線分データＬＳＤのデータ量は倍になるので、１６ワードをバーストサイズする固定長のブロックデータＢＤにパッキンすることが望ましい。メモリ５９の使用効率も、アクセス効率も高い。１６ワード固定長のブロックデータＢＤの代わりに、２つの８ワード固定長のブロックデータＢＤを用いて線分データＬＳＤを格納しても良い。
【００３６】
回転角θが±２度から±１度の間は、１つの線分データＬＤＳを１６ワード固定長のブロックデータＢＤにパッキングしても良く、２つの８ワード固定長のブロックデータＢＤに分けてパッキングしても良い。回転角θが±１度から０度の間は、１つの線分データＬＤＳを２またはそれ以上の１６ワード固定長のブロックデータＢＤに分けてパッキングすることが望ましい。回転角θが±２度を超える場合は、１つの線分データＬＳＤを８ワード固定長のブロックデータＢＤにパッキンすることができる。ただし、回転角θが大きくなると、パディングデータｄｐが増加し、ブロックデータＢＤの利用効率が減少する。この明細書では、１つのブロックデータＢＤに複数の線分データＬＳＤを含まないことをベースとして説明している。すなわち、１つの線分データＬＳＤは、それに関連づけられた１つまたは複数（通常は２つ）のブロックデータＢＤに含まれている。１つのブロックデータＢＤに複数の線分データＬＳＤをパッキングすることを除外しないが、１つの線分データＬＳＤを入出力するためにメモリにアクセスする回数が増加傾向になるので、本明細書に記載の方法および装置は、回転角θが微小、例えば±２度以下の画像処理に適している。
【００３７】
図７に、生成装置５０における処理をフローチャートにより示している。まず、ステップ８０において、再構成可能な処理装置１の再構成可能領域（再構成可能ユニット）１０に、第１段階の回路５１を再構成する。第１段階の回路５１は、第１の入力ユニット６１と、第１の補間演算ユニット６３と、ブロックデータ生成ユニット６６と、第１の出力ユニット６２と、制御情報生成ユニット６９とを含む。この例では、第１画像Ｇ１の走査線データから、第２の画像Ｇ２の複数の画素を出力するための画素データを生成する処理は、第１段階と、第２段階とに分かれて実行される。したがって、画素データを生成するための補間演算ユニットは、第１の補間演算ユニット６３と、第２の補間演算ユニット７３とに分けて、再構成される。
【００３８】
ステップ８１において、第１の入力ユニット６１が、メモリ５９の第１のデータファイルＤ１から原走査線データＥ１を取得する。ステップ８２において、第１の補間演算ユニット６３が、原走査線データＥ１に含まれている原走査線の画素データから第２の画像Ｇ２を出力するための走査線の線分データＬＳＤを生成する。
【００３９】
図８から図１０に、ステップ８２において行われる第１の補間処理の概要を示している。図８に示すように、第１の補間処理は、副走査方向Ｙに隣り合う第１の画像Ｇ１の２つの画素データ（輝度データ）Ｐ（ｎ−１、ｉ）およびＰ（ｎ、ｉ）を重みづけ補間し、第２の画像Ｇ２の画素データＰ´（ｎ、ｉ）を生成する。補間式は、図９に示す式（１）である。パラメータＷｅｉｇｈｔは、回転角θにより決まる。また、ブロック先頭のオフセットａは、図１０に示すように、原走査線ＯＬの左端の画素を中心に旋回角θを定義した場合は、左端の線分ＬＳについてはゼロである。原走査線ＯＬの中心の画素を中心に旋回させたり、右端の画素を中心に旋回させても良い。その場合は、回転の中心となる画素についてオフセットａはゼロになる。
【００４０】
この例では、４つの画素Ｐ´（ｎ、０）からＰ´（ｎ、３）により左端の線分ＬＳ（１）が構成される。したがって、線分データＬＳＤは、４つの画素データを含み、これらは再構成可能領域１０の演算エレメントを用いて並列に計算される。制御情報生成ユニット６９は、回転角θ、解像度、画像のサイズなどの条件により、原走査線の間に生成される第２の画像Ｇ２の線分の数、１つの線分に含まれる画素数（ドット数）など、補間計算と、ブロック化に必要な情報を提供する。ステップ８３において、ブロックデータ生成ユニット６６は、画素データのみで所定の長さのブロックデータＢＤが構成できれば、そのまま処理の数の画素の画素データＰ´を纏めてブロックデータＢＤとする。画素データのみでは不足する場合は、パディングデータを加えて、固定長（バーストサイズ）のブロックデータＢＤを生成する。ステップ８３において、さらに、第１の出力ユニット６２は、制御情報生成ユニット６９からの指示（アドレス）により、ブロックデータＢＤをメモリ５９の中間データファイルＭＤの中で、所定の順番となるように格納する。格納する順番の例は、図６（ａ）および（ｂ）で説明した方法である。また、第１の出力ユニット６２は、メモリ５９とバーストモードでアクセスし、高速でデータを出力する。
【００４１】
ステップ８４において、第１の画像Ｇ１の画像データＤ１に含まれる原走査線データが終了するまで、ステップ８１から８３の処理を繰り返す。画像データＤ１に含まれる原走査線データを用いて重みづけ補間する処理が終了すると、ステップ８５において、再構成可能な処理装置１の再構成可能領域１０に、第２段階の回路５２を再構成する。この生成装置５０が搭載（実装）されている再構成可能デバイス１は、ダイナミックリコンフィグラブルデバイスであり、再構成可能領域１０の回路構成を、第１段階の回路５１から第２段階の回路５２に１クロック（サイクル）で変更できる。第２段階の回路５２は、第２の入力ユニット７１と、第２の補間演算ユニット７３と、ラインデータ生成ユニット７６と、第２の出力ユニット７２と、制御情報生成ユニット７９とを含む。
【００４２】
ステップ８５において、第２の入力ユニット７１が、メモリ５９の中間データファイルＭＤから、制御情報生成ユニット７９が生成するアドレスに基づき、線分データＬＳＤを含むブロックデータＢＤを、回転後の走査線に含まれる順番で読み込む。第２の入力ユニット７１は、メモリ５９とバーストモードでアクセスし、高速でブロックデータＢＤを読み込む（取得する）。第２の入力ユニット７１は、ブロックデータＢＤにパディングデータｐｄが含まれていれば、ブロックデータＢＤから線分データＬＳＤを抜き出して、あるいはパディングデータｐｄを除いて、第２の補間演算ユニット７３に供給する。ステップ８７において、第２の補間演算ユニット７３は、走査方向（走査線方向）Ｗの補間演算（第２の補間）を行う。
【００４３】
図１１および図１２に、ステップ８７において行われる第２の補間処理の概要を示している。図１１に示すように、第２の補間処理は、回転後の走査方向Ｗに隣り合う画素データＰ´ｎ（ｉ）と、Ｐ´ｎ（ｉ＋１）を重みづけ補間して、第２の画像Ｇ２を出力するための画素データＰ´´ｎ（ｉ）を生成する。補間式は、図１２に示す式（２）である。３００ＤＰＩ、回転角θが２度の場合、原走査線のＸ方向の画素位置と、回転後の走査線のＷ方向の画素位置との差は１ライン当たり１画素未満（０．１％未満）なので、ほとんど無視できる程度である。したがって、この第２の補間処理は省いても良い。省いた場合、第２の画像Ｇ２は、走査方向Ｗに０．１％程度膨らんだ位置の輝度が表示されるので、第２の画像Ｇ２は走査方向Ｗに０．１％程度収縮した画像になる。第２の補間処理は走査方向Ｗの画素位置に合わせて輝度データ（画素データ）を補間し、回転した第２の画像Ｇ２の膨張収縮を抑制する。
【００４４】
ステップ８８において、ラインデータ生成ユニット７６が、第２の補間処理が行われた画素データＰ´´を走査方向Ｗの順番で組み合わせ、回転後の走査線データ（ラインデータ）を生成する。さらに、ステップ８８において、第２の出力ユニット７２は、メモリ５９の第２のデータファイルＤ２に走査線データを順番に格納する。ステップ８９において、中間データファイルＭＤに格納されたブロックデータＢＤが終了するまで、ステップ８６から８８を繰り返す。このようにして、生成装置５０は、第１の画像Ｇ１を角度θだけ回転させた第２の画像Ｇ２を出力するための画像データＤ２を生成する。この例では、画像データなどを格納する記録媒体として共通のメモリ５９が用いられているが、異なる記録媒体であっても良い。たとえば、再構成可能領域１０に含まれるＲＡＭエレメントを中間データファイルＭＤの格納先としても良い。
【００４５】
図１３（ａ）に、再構成可能な処理装置（再構成可能デバイス）１の一例を示している。このデバイス１は、本願の出願人が開発したＤＡＰＤＮＡと称する半導体集積回路装置である。このデバイス１は、ＤＡＰと呼ばれるＲＩＳＣコアモジュール２と、ＤＮＡと呼ばれるダイナミックリコンフィグラブルデータフローアクセレレータ３とを含む。デバイス１は、ＤＡＰ２およびＤＮＡ３に加え、ＤＮＡ３のダイレクト入出力用のインターフェイス４と、ＰＣＩインターフェイス５と、ＳＤＲＡＭインターフェイス６と、ＤＭＡコントローラ７と、その他の周辺デバイス８と、これらを接続するための高速スイッチングバス（内部バス）９とを含む。ＰＣＩインターフェイス５および／またはＳＤＲＡＭインターフェイス６には、大容量記録媒体、例えば、ＲＡＭディスク５９ｂ、フラッシュメモリ５９ａなどを接続し、画像データなどを格納できる。
【００４６】
ＤＡＰ２は、デバッグインターフェイス４２ａと、ＲＩＳＣコア４２ｂと、命令キャッシュ４２ｃと、データキャッシュ４２ｄとを含む。ＤＮＡ３は、３７６個のＰＥ（ＰＥｓ、処理エレメント）が２次元に配置されたＰＥマトリクス１０と、このＰＥマトリクス１０に含まれるＰＥｓの機能および／または接続を変えてＰＥマトリクス１０を再構成するためのコンフィグレーションデータ１８が格納されるコンフィグレーションメモリ１９とを含む。ＰＥマトリクス１０は、回路を再構成可能なユニット、すなわち、再構成可能領域に相当する。また、このＰＥマトリクス１０の構成は、ＤＡＰ２により制御され、ＤＡＰ２は制御ユニットに相当する。
【００４７】
コンフィグレーションメモリ１９は、複数バンクの構成になっている。例えば、図１３（ｂ）に示すように、ＰＥマトリクス１０には、フォアグラウンドバンクに格納されるコンフィグレーションデータ１８により第１の機能（データフロー、回路デザイン）１７ａが構成される。また、異なるバックグラウンドバンクにそれぞれ格納されるコンフィグレーションデータにより、第２の機能１７ｂおよび第３の機能１７ｃがそれぞれ構成される。メモリ１９のバンクを切り替えることにより、ＰＥマトリクス１０には、第１の機能１７ａに変わって第２の機能１７ｂまたは第３の機能１７ｃが再構成される。ＰＥマトリクス１０の再構成は、例えば、１サイクル（クロックサイクル）でダイナミックに行なわれる。このようにＰＥマトリクス１０は、回路を構成するための複数のエレメントと、これらのエレメントを接続するための内部配線とを含む再構成ユニットであり、内部配線によりエレメントの接続を変えることによりＰＥマトリクス１０に含まれる回路を再構成できる。
【００４８】
図１３（ｃ）は、ＰＥマトリクス１０に回路を再構成する一例である。あるアプリケーション、例えばＭＰＥＧデコーダを時分割した複数の機能（サブファンクション）を、ＰＥマトリクス１０に時分割で再構成し、ＭＰＥＧデコーダの機能を専用回路（専用ハードウェア）で提供する。このような使用により、再構成可能なデータ処理装置であるデバイス１を用いて、多くのハードウエア資源を必要とするアプリケーションを、少ないハードウエア資源で実行できる。
【００４９】
図１３（ｄ）は、ＰＥマトリクス１０に回路を構成する他の例の一つである。再生方式が異なるアプリケーションを実行するために、複数の機能がそれぞれ実現されるようにＰＥマトリクス１０を再構成できる。このような使用により、多くのアプリケーションを共通のハードウエア（デバイス）１を用いて実行できる。このデバイス１は、プログラムレベル（命令レベル）ではなく、データフローレベル（データパスレベル、ハードウエアレベル）で多数の機能を切り換えて実装できるので、専用のハードウエアに匹敵する速度で処理を行うことができる。
【００５０】
図１４に、ＰＥマトリクス１０の配列を拡大して示している。処理エレメントＰＥは、全体として、１６×２４のマトリクスを構成するように配置されている。なお、ＰＥのいくつかは、２個分のＰＥのスペースを占め、全体として３７６個のＰＥがＰＥマトリクス１０に配置されている。これらのＰＥは、さらに、それぞれ８×８のＰＥからなる６つのグループに区分けされている。これらのグループをセグメントＳと称し、ＰＥマトリクス１０の左上から右下に向かって順番にセグメントＳ０からセグメントＳ５が配置されている。各々のセグメントＳ０〜Ｓ５に含まれるＰＥは、１サイクルの遅延の範囲内でデータを送受信可能なイントラセグメントコネクションで接続されている。また、セグメントＳ０〜Ｓ５の内、隣接するセグメントは、後述するディレイエレメントを介してインターセグメントコネクションにより接続されている。
【００５１】
図１４に示したＰＥのうち、「ＥＸ」で始まるＰＥは、ＥＸＥエレメントと呼ばれ、算術演算、論理演算および２入力の比較機能を含む演算用のエレメントである。「ＥＸＣ」は、ＣＭＰＳＢ命令を搭載し、「ＥＸＦ」は、ＦＦ１命令を搭載し、「ＥＸＭ」は、乗算命令を搭載し、「ＥＸＲ」はＢＲＥＶ命令を搭載し、「ＥＸＳ」は、ＢＳＷＡＰ命令を搭載するというように、タイプ毎に固有の演算機能も含んでいる。
【００５２】
「ＤＬ」で始まるＰＥは、ディレイエレメントであり、１−８クロックの間の遅延をそれぞれ設定できる。「ＤＬＥ」は、セグメント内のデータ遅延用であり、「ＤＬＶ」は縦方向のセグメント間のデータ送受信用であり、「ＤＬＨ」は横方向のセグメント間のデータ送受信用であり、「ＤＬＸ」は縦横方向のセグメント間のデータ送受信用のエレメントである。
【００５３】
「ＲＡＭ」と表示されたＰＥは、ＤＮＡの内部メモリとして使用されるエレメント（メモリエレメント）である。「ＬＤＢ」と表示されたＰＥは、データ入力用のＤＮＡ内部バッファであり、入力インターフェイスあるいは入力ユニットを構成するために用いられる。「ＳＴＢ」と表示されたＰＥは、データ出力用のＤＮＡ内部バッファであり、出力インターフェイスあるいは出力ユニットを構成するために用いられる。「Ｃ１６Ｅ」と表示されたＰＥは、ＤＮＡ内部バッファに対するアドレス生成エレメントである。「Ｃ３２Ｅ」と表示されたＰＥは、外部メモリ空間に対するアドレス生成エレメントである。「ＬＤＸ」と表示されたＰＥは、ＤＮＡダイレクトＩ／Ｏからのデータ入力用エレメントである。「ＳＴＸ」と表示されたＰＥは、ＤＮＡダイレクトＩ／Ｏへのデータ出力用エレメントである。ＰＥマトリクス１０において、ＬＤＢおよびＬＤＸは、外部からデータを入力するための入力インターフェイスとして使用でき、ＳＴＢおよびＳＴＸは、外部へデータを出力するための出力インターフェイスとして使用できる。
【００５４】
図１５に、ＰＥの一例として、ＥＸＭエレメント（「ＥＸＭ」）の概略構成をブロック図により示している。ＥＸＭエレメントは、ＡＬＵ１１ａと、ＭＵＬ（１６×１６）１１ｂと、ＦＦ１１ｃなどを含む。このＥＸＭエレメントは、ＤＮＡ３のコンフィグレーションメモリ１９に格納されたコンフィグレーションデータ１８により、算術演算、論理演算、２入力の比較機能、さらには、乗算のいずれか、または複合した命令を実行するように構成できる。また、複数のＦＦ１１ｃを内蔵しているので、エレメントＰＥに対するデータの入力から出力までのレイテンシを制御することが可能であり、ディレイエレメント（ＤＬＥ）の数が不足する構成では、ディレイエレメントとしての機能をセットすることも可能である。
【００５５】
図１６に、ＰＥの他の例として、ＲＡＭエレメント（「ＲＡＭ」）の概略構成をブロック図により示している。このＲＡＭエレメントは、データ格納用メモリエレメントであり、１６ＫＢ（３２ビット×４０９６ワード）のＲＡＭモジュール１２ａと、アドレス入力用のアドレスレジスタ（ＦＦ）１２ｂ、ラッチ１２ｃ、データ入力用のライトデータレジスタ（ＦＦ）１２ｄ、ラッチ１２ｅ、データ出力用のリードデータレジスタ（ＦＦ）１２ｆを含む。ＲＡＭモジュール１２ａのリードとライトの制御は、アドレスデータおよび／またはリードデータとともに入力されるトークンの値により行なわれる。アドレス入力からリードデータの出力までは、ＥＸＥエレメントと同様に３クロックサイクル程度で可能になっており、ＰＥマトリクス１０に含まれる他のタイプのＰＥと同様のレイテンシで、データの入出力が可能である。このＲＡＭエレメントは、ＤＮＡ３のコンフィグレーションメモリ１９に格納されたコンフィグレーションデータ１８により、３２ビットモード、デュアルポート３２ビットモード、ＦＩＦＯモード、１６ビットモード、８ビットモード、さらに、ＦＳＭ（フィードバックステートモード）でデータ入力および／または出力するように構成できる。
【００５６】
ＲＡＭエレメントのアクセスアドレスの生成には、ＥＸＥエレメント、カウンタエレメントであるＣ１６Ｅおよび／またはＣ３２Ｅを使用することができ、ＰＥマトリクス１０のルーティングマトリクス（マトリクスバス）を通じて、ＲＡＭエレメントに入力できる。したがって、ＲＡＭエレメントへの入出力は、ＰＥマトリクス１０に再構成される回路により制御できる。
【００５７】
ＰＥマトリクス１０は、複数のＰＥと、それらを接続するためのルーティングマトリクス（配線群）２０を含む。ルーティングマトリクス２０は、セグメントＳ内のＰＥを接続するための第１レベルの配線群（第１レベルのルーティングマトリクス、イントラコネクト）２１と、ディレイエレメントを介して隣接するセグメントＳの間を接続するための第２レベルの配線群（第２レベルのルーティングマトリクス、インターコネクト）とを含む。ルーティングマトリクス２０によるＰＥｓの接続はコンフィグレーションデータ１８により制御できる。したがって、ＰＥマトリクス１０には、コンフィグレーションデータ１８により、複数のＰＥのそれぞれの機能を変更すること、および／または、ルーティングマトリクス２０の少なくとも一部の接続を変更することにより、異なる回路（データパス、データフロー）を再構成できる。
【００５８】
図１７に、セグメントＳの内部のＰＥｓを接続するための第１レベルの配線群２１の構成の一例を示している。第１レベルのルーティングマトリクス２１は、セグメントＳ０に含まれる８×８個のＰＥｓを接続するために、１２８の縦方向のバス２３と、６４の横方向のバス２４とを含む。縦方向のバス２３は、１６のグループに分けられ、それぞれ８のバスを含む２つのＶ−バス２３ｘおよび２３ｙがペアとなり、ＰＥｓの縦の列（コラム）に沿って、その列の両側に配置されている。横方向のバス２４は８のグループに分けられ、それぞれ８のバスを含むＨ−バス２４がＰＥの横方向の行（ライン）に沿って配置されている。Ｖ−バス２３ｘおよび２３ｙには、８−１のバスセレクタ（マルチプレクサ、ＭＵＸ）２５がそれぞれのＰＥに対応して設けられており、それぞれのＰＥに対してデータの入力を可能としている。
【００５９】
Ｈ−バス２４には、Ｈ−バス２４とＶ−バス２３ｘおよび２３ｙのそれぞれの交差に対応して、８−１のバスセレクタ（マルチプレクサ、ＭＵＸ）２６が設けられている。したがって、１つのＨ−バス２４から１つのデータセットを、そのＨ−バス２４と交差している１つのＶ−バス２３ｘまたは２３ｙに出力できる。逆も可能である。Ｈ−バス２４に含まれるバスのそれぞれには、そのラインのＰＥｓの出力が接続される。したがって、Ｖ−バス２３ｘおよび２３ｙと、Ｈ−バス２４とを介することにより、セグメントＳに含まれるＰＥｓを接続できる。これらのＶ−バス２３ｘおよび２３ｙ、およびＨ−バス２４を含む第１レベルのバス２１により接続できる範囲、すなわち、各セグメントＳ０〜Ｓ５内のＰＥの間では１サイクル（１クロック）以内にデータを送受信できる。したがって、タイミング的には、例えば、セグメントＳ０に含まれるＰＥｓは、いずれも等価である。このため、同一セグメント内であれば、回路を構成するために、いずれのＰＥを選択して機能を割り付けても、タイミングの検討は不要であり、タイミング的には、セグメント内のＰＥｓを用いて、所定の回路を自由に配置および配線できる。
【００６０】
第２レベルのルーティングマトリクスにより、隣接するセグメント同士、例えば、セグメントＳ１およびＳ２にそれぞれ含まれている接続用のエレメントＤＬＨが接続される。それぞれのＤＬＨは、それぞれのセグメント内部の第１レベルのルーティングマトリクス２１に接続している。したがって、異なるセグメントに含まれるＰＥは、第２レベルのルーティングマトリクスを介して接続することができる。接続用のディレイエレメントＤＬＨは、第１レベルのルーティングマトリクス２１に含まれるバスのインターフェイスとして機能する。したがって、第１レベルのルーティングマトリクス２１に含まれるバスを、セグメント毎に独立して使用できる。一方、セグメント間でデータを入出力する必要があるときは、接続用のディレイエレメントＤＬＨに含まれる複数のＦＦを介してデータを入出力する必要があり、クロックに同期した２サイクル以上の遅延が新たに加わる。
【００６１】
このように、第１レベルのルーティングマトリクス２１のみを用いてＰＥを接続する場合、ＰＥｓの間は１サイクル（第１の遅延）の範囲内で接続されることが保証され、タイミングの検証は不用である。これに対し、第２レベルのルーティングマトリクスを介してＰＥを接続する場合は、２サイクル以上の遅延が加わる。第２レベルのルーティングマトリクスを介して接続する場合の遅延は、ディレイエレメントＤＬＨの設定に依存する。例えば、ＤＬＨの遅延量を制御することにより、第２のルーティングマトリクスを２回使用する信号と、１回使用する信号とをシンクロナイズできる。他の接続用のディレイエレメントＤＬＶおよびＤＬＸを介して隣接するときも同様である。
【００６２】
図１８に、再構成領域であるＰＥマトリクス１０に構成される第１段階の回路５１の一例を示している。この例では、第１の入力ユニット６１は、入力バッファＬＤＢを用いてライン単位の原走査線データＥ１を取得し、さらに、ＲＡＭエレメントをラインバッファとして使用して第１の補間演算ユニット６３に２ライン分のデータを供給するように構成される。第１の補間演算ユニット６３では、ＥＸエレメントを用いて掛け算および足し算を含む演算回路が構成される。第１の補間演算ユニット６３では、ブロックデータＢＤに含まれる線分データＬＳＤの複数の画素のデータを生成する処理がパイプラインで行われるように回路が構成されている。このため、原走査線データＥ１の読み込みに続いて、線分データＬＳＤが連続的に、パイプライン方式で、例えば、１サイクル毎に出力される。
【００６３】
ブロックデータ生成ユニット６６では、ＥＸエレメントを用いてセレクタを含む回路が構成される。第１の出力ユニット６２では、出力バッファＳＴＢを用いて回路が構成される。ブロックデータ生成ユニット６６および第１の出力ユニット６２では、２系統のブロックデータＢＤをハンドリングする回路が並列に用意されている。線分データＳＬＤをブロックデータＢＤにするときにパディングデータｐｄを追加する処理に時間を要するので、パイプラインが破綻する可能性があるからである。しかしながら、第１の出力ユニット６２よりブロックデータＢＤをメモリ５９にバーストライトすることにより、待ち時間なく、ブロックデータＢＤをメモリ５９に格納できる。
【００６４】
制御情報生成ユニット６９では、ＥＸエレメントを用いて座標をカウントするためのカウンタが構成され、ＲＡＭエレメントを用いて定数テーブルが構成されている。定数データには、解像度、回転角θにより決まる線分の情報と、補間計算のための各種パラメータと、線分データをブロック化するための情報などが含まれる。
【００６５】
図１９に、第１段階の回路５１の主なポイントにおいてデータが転送される様子を模式的に示している。第１の入力ユニット６１は、第１の画像データＤ１から連続的に原走査線データを取得し（ポイントＡ）、バッファを用いて２ライン分のデータＬＤ１およびＬＤ２を出力する（ポイントＢ）。ブロックデータ生成ユニット６６においては、第１の補間演算ユニット６３から連続的に出力される線分データＬＳＤにパディングデータｐｄを付加してブロックデータＢＤを出力する（ポイントＣ）。第１の出力ユニット６２は、それらのブロックデータＢＤをメモリ５９の所定のアドレスにバーストライトする。
【００６６】
図２０に、ＰＥマトリクス１０に構成される第２段階の回路５２の一例を示している。この例では、第２の入力ユニット７１は、入力バッファＬＤＢを用いてブロックデータＢＤを走査線の順番で取得し、さらに、ＤＥＬエレメントにより、走査方向Ｗに隣接する２つの画素のデータを第２の補間演算ユニット７３に供給されるようにしている。第２の補間演算ユニット７３では、ＥＸエレメントを用いて掛け算および足し算を含む演算回路が構成される。第２の補間演算ユニット７３では、ブロックデータＢＤに含まれる線分データＬＳＤの複数の画素のデータを生成する処理がパイプライン方式で行われるように回路が構成されている。このため、第２の補間処理がされた線分データＳＬＤが連続的に、パイプライン方式で、例えば、１サイクル毎に出力される。
【００６７】
ラインデータ生成ユニット７６では、ＥＸエレメントを用いてセレクタを含む回路が構成され、ゲーティングすることによりブロックデータＢＤに含まれているパディングデータｐｄを取り除けるようになっている。ＤＥＬエレメントは、制御情報と待ち合わせのためのものである。第２の出力ユニット７２では、出力バッファＳＴＢを用いて回路が構成される。
【００６８】
制御情報生成ユニット７９には、ＥＸエレメントを用いて座標をカウントするためのカウンタが構成され、ＲＡＭエレメントを用いて定数テーブルが構成されている。第１段階の回路５１と同様に、定数データには、解像度、回転角θにより決まる線分の情報と、補間計算のための各種パラメータと、ブロックデータＢＤから線分データＬＳＤを抽出するための情報などが含まれる。
【００６９】
図２１に、第２段階の回路５２の主なポイントにおいてデータが転送される様子を模式的に示している。第２の入力ユニット７１は、メモリ５９の所定のアドレスから取得したブロックデータＢＤと、そのブロックデータＢＤを１または複数クロックだけシフトした２系統のブロックデータＢＤを出力する（ポイントＢ）。ラインデータ生成ユニット７６においては、第２の補間演算ユニット７３から出力されるブロックデータからパディングデータｐｄを取り除き、線分データＬＳＤのみを出力する。第２の出力ユニット７２は、それらの線分データＬＳＤを順番にメモリ５９に格納し、第２の画像データＤ２を生成する。
【００７０】
図２２に示したように、第１の画像Ｇ１を単純に回転すると見栄えが悪くなる。このため、ラインデータ生成ユニット７６は、回転画像調整部としての機能を備えている。すなわち、図２２における領域Ｒ１〜Ｒ４の部分は回転後の表示では見栄えを悪くし、不要と考えられる。このため、ラインデータ生成ユニット７６は、パディングデータＰｄをカットするゲーティングの機能を用いて領域Ｒ１〜Ｒ４のデータを出力しない（削除する）。この処理は制御情報生成ユニット７９により出力される制御情報をもとに行う。
【００７１】
図２３は、生成装置５０の他の例を示す基本構成ブロック図である。この生成装置５０も、回路を再構成可能な処理装置（再構成可能デバイス）１を用いて実現されている。再構成可能領域であるＰＥマトリクス１０に構成される第１段階の回路５１は、第１の入力ユニット６１と、補間演算ユニット６５と、第１の出力ユニット６２と、制御情報生成ユニット６９とを含む。補間演算ユニット６５は、第１の補間演算ユニット６３と、第２の補間演算ユニット７３と、特異点処理部６４とを含む。第１の補間演算ユニット６３と、第２の補間演算ユニット７３とは、線分ＬＳ毎に、上述したように、走査方向に補間処理を行っても良い。また、２次元的に隣合う４画素に囲まれる長方形の領域内に属する回転後の画素の輝度データ（画素データ）を４画素の距離を重みづけパラメータとして補間により求めることができる。この長方形領域に回転後の画素が１つしか含まれない場合だけではなく、回転後の画素が０個ないし２個含まれる場合も起こりうる。０個ないし２個含まれる場合を特異点と呼ぶ。回転後の画素が１つしか含まれない場合は、上述してきた処理のみで対応できる。しかしながら、回転後の画素が０個または２個の場合は特異点処理が必要となる。
【００７２】
第２段階の回路５２は、第２の入力ユニット７１と、ラインデータ生成ユニット７６と、第２の出力ユニット７２と、制御情報生成ユニット７９とを含む。回転後の画素データを生成する補間演算は、第１段階の回路５１ですべて行っているので、この第２段階の回路５２は、回転後の走査方向Ｗの順番でブロックデータＢＤを読み込み、ラインデータ化して出力するだけになる。この例では、ブロックデータＢＤを走査方向Ｗに読み出すためのアドレス生成機能を第２段階の回路５２に含めて、第１段階の回路５１のハードウェア的な負荷を減らしている。すなわち、第１の出力ユニット６２は、回転前の走査方向Ｘの順番でブロックデータＢＤをメモリ５９の中間データファイルＭＤに格納する。第２の入力ユニット７１は、アドレス生成を行い、ブロックデータＢＤを飛び飛びに取得し、回転後の走査方向Ｗの順番でブロックデータＢＤをメモリ５９から取得する。
【００７３】
以上に説明したように、これらの生成装置５０においては、アフィン変換された画像を生成するために、メモリ５９に対してバーストアクセスおよびシリアルアクセスするだけで良い。個々の画素データを取得するためにメモリ５９に対してランダムアクセスする必要がない。したがって、データを入出力する処理時間が、画像データを変換するための処理時間のクリティカルパスおよび／またはボトルネックとなることを抑制できる。たとえば、図１９に示すように、ブロックデータＢＤをメモリ５９に書き込むために補間演算処理を止める必要はなく、メモリに対する入出力がクリティカルパスになるのが避けられている。したがって、アフィン変換を要する画像処理の時間を短縮できる。
【００７４】
上記にて開示した画像処理方法は、メモリの利用効率などの点から、３００ＤＰＩ程度の解像度の画像であれば±数度以下の微小回転を含む画像処理に適している。この程度の微小回転を伴う画像処理は、スキュー角の補正などに多用されており、画像処理を高速化できることは有効である。また、上記にて開示した画像処理を、±数度以上の大きな回転を伴う画像処理に適用することも可能である。また、微小回転をなんどか繰り返すことにより、所望の角度だけ画像を回転することも可能である。
【００７５】
また、上記の生成装置は、メモリにブロックデータを書き込む第１段階の回路と、メモリからブロックデータを読み込む第２段階の回路とに分けて、再構成可能なデバイス、特に、ダイナミックリコンフィグラブルデバイスを用いて実現している。しかしながら、第１段階の回路と、第２段階の回路とを同時に構成しても良く、また、ＦＰＧＡあるいはＡＳＩＣを用いて、これらの回路を固定的に実装しても良い。また、メモリに対するブロックデータへの入出力は、ダブルポートメモリなどを用いることにより、適当な処理間隔をおいて、並列に実行することも可能である。
【図面の簡単な説明】
【００７６】
【図１】本発明の実施形態の生成装置のブロック図。
【図２】アフィン変換することにより線分が生成されることを示す図。
【図３】変換前の走査線のデータを補間して変換後の線分のデータを生成することを示す図。
【図４】変換後の線分のデータを組み合わせて、変換後の走査線のデータを生成することを示す図。
【図５】線分のデータをブロックデータ化することを示す図。
【図６】図６（ａ）および（ｂ）は、ブロックデータをメモリに格納する異なる例を示す図。
【図７】生成装置の処理を示すフローチャート。
【図８】副走査方向に補間して線分のデータを生成する様子を示す図。
【図９】副走査方向の補間式を示す図。
【図１０】走査線の左端を中心に回転したときの左端の線分のデータを生成する様子を示す図。
【図１１】走査方向にさらに補間して線分のデータを生成する様子を示す図。
【図１２】走査方向の補間式を示す図。
【図１３】図１３（ａ）は、再構成可能なデバイスの一例の概略構成を示し、図１３（ｂ）は、ＰＥマトリクス（再構成可能領域）の概略を示し、図１３（ｃ）および図１３（ｄ）は、ＰＥマトリクスを動的に再構成する様子を示す。
【図１４】ＰＥマトリクスに配置されたＰＥのタイプを示す図。
【図１５】ＰＥの１つのタイプのＥＸＭの構成を示すブロック図。
【図１６】ＰＥの１つのタイプのＲＡＭの構成を示すブロック図。
【図１７】セグメント内の配線（イントラセグメント配線）を示す図。
【図１８】第１段階の回路の一例を示すブロック図。
【図１９】第１段階の回路においてデータが転送される様子を示す図。
【図２０】第２段階の回路の一例を示すブロック図。
【図２１】第２段階の回路においてデータが転送される様子を示す図。
【図２２】画像を回転したときに、はみ出た部分の削除を行うことを示す図。
【図２３】本発明の実施形態の生成装置の異なる例を示すブロック図。
【符号の説明】
【００７７】
１  ダイナミックリコンフィグラブルデバイス
１０  ＰＥマトリクス（再構成ユニット）
５０  生成装置（画像処理装置）
５１  第１段階の回路
５２  第２段階の回路
【図１】
0004936223.tif 000002
【図２】
0004936223.tif 000003
【図３】
0004936223.tif 000004
【図４】
0004936223.tif 000005
【図５】
0004936223.tif 000006
【図６】
0004936223.tif 000007
【図７】
0004936223.tif 000008
【図８】
0004936223.tif 000009
【図９】
0004936223.tif 000010
【図１０】
0004936223.tif 000011
【図１１】
0004936223.tif 000012
【図１２】
0004936223.tif 000013
【図１３】
0004936223.tif 000014
【図１４】
0004936223.tif 000015
【図１５】
0004936223.tif 000016
【図１６】
0004936223.tif 000017
【図１７】
0004936223.tif 000018
【図１８】
0004936223.tif 000019
【図１９】
0004936223.tif 000020
【図２０】
0004936223.tif 000021
【図２１】
0004936223.tif 000022
【図２２】
0004936223.tif 000023
【図２３】
0004936223.tif 000024