(57)【要約】【課題】小さいメモリ容量で画像全体が回転した完全な画像データを得る。【解決手段】回転対象の画像を同一サイズの複数の正方形領域に分割し、回転対象の画像を回転したときの該分割された正方形領域単位の移動先を規定した移動規則を求め、該求めた移動規則を１以上の巡回置換の形式に変換する。そして、巡回置換で最初の移動先として規定された正方形領域の画像データを、待避ブロックバッファ３２に移動する移動処理と、画像データが移動されて空き領域となった正方形領域を移動先とする正方形領域の画像データを回転角度だけ回転させた状態で該移動先に移動することを巡回置換に基づいて順に行い、最後の移動先として規定された且つ画像データが移動されて空き領域となった正方形領域に、上記待避ブロックバッファ３２に移動された画像データを移動する回転処理とを巡回置換毎に行なう。【選択図】図８
2009141659.tif 000002
【特許請求の範囲】
【請求項１】
回転対象の画像の画像データを記憶する第１記憶手段と、
前記回転対象の画像を同一サイズの複数の正方形領域に分割する分割手段と、
前記回転対象の画像を回転したときの前記分割された正方形領域単位の移動先を規定した移動規則を求める移動規則導出手段と、
前記求めた移動規則を１以上の巡回置換の形式に変換する変換手段と、
少なくとも前記正方形領域１個分の画像データの記憶が可能な第２記憶手段と、
前記巡回置換で最初の移動先として規定された正方形領域の画像データを前記第１記憶手段から前記第２記憶手段に移動する移動処理と、前記第１記憶手段において画像データが移動されて空き領域となった正方形領域を移動先とする正方形領域の画像データを回転角度だけ回転させた状態で該移動先に移動することを前記巡回置換に基づいて順に行い、最後の移動先として規定され且つ画像データが移動されて空き領域となった正方形領域に前記第２記憶手段に移動された画像データを移動する回転処理と、を前記巡回置換毎に行なう処理手段と、
を備えた画像処理装置。
【請求項２】
回転対象の画像の画像データを記憶する第１記憶手段と、
前記回転対象の画像を同一サイズの複数の正方形領域に分割する分割手段と、
前記回転対象の画像を回転したときの前記分割された正方形領域単位の移動先を規定した移動規則を求める移動規則導出手段と、
前記求めた移動規則を１以上の巡回置換の形式に変換する変換手段と、
少なくとも前記正方形領域１個分の画像データの記憶が可能な第２記憶手段及び第３記憶手段と、
前記巡回置換において移動先として規定された正方形領域に移動するべき画像データを、前記第１記憶手段及び前記第２記憶手段から探し出して前記第３記憶手段に移動する第１移動処理と、前記第１記憶手段において前記移動先として規定された正方形領域に回転処理前の画像データが記憶されている場合に、該画像データを前記第１記憶手段及び前記第２記憶手段の空き領域に移動する第２移動処理と、前記第３記憶手段に移動された画像データを回転角度だけ回転させた状態で前記移動先として規定された正方形領域に移動する回転処理と、を前記巡回置換に基づいて順に行なう処理手段と、
を備えた画像処理装置。
【請求項３】
前記処理手段は、前記第１記憶手段および前記第２記憶手段の空き領域及び該空き領域に対する移動状態を管理する管理テーブルを前記第１移動処理後および前記第２移動処理後に更新する更新処理を更に行ない、該更新処理により更新された最新の管理テーブルを参照して前記第１移動処理および前記第２移動処理を行なう請求項２に記載の画像処理装置。
【請求項４】
前記分割手段は、前記回転対象の画像のサイズが前記正方形領域のサイズの整数倍でない場合には、整数倍となるように前記回転対象の画像の縁辺に余白を付加した状態で、前記回転対象の画像を同一サイズの複数の正方形領域に分割する請求項１〜請求項３のいずれか１項記載の画像処理装置。
【請求項５】
回転対象の画像の画像データを記憶する第１記憶手段、および画像データの一時的な移動先として用いる第２記憶手段を備えたコンピュータを、
前記回転対象の画像を同一サイズの複数の正方形領域に分割する分割手段、
前記回転対象の画像を回転したときの前記分割された正方形領域毎の移動先を規定した移動規則を求める移動規則導出手段、
前記求めた移動規則を１以上の巡回置換の形式に変換する変換手段、および
前記巡回置換で最初の移動先として規定された正方形領域の画像データを前記第１記憶手段から前記第２記憶手段に移動する移動処理と、前記第１記憶手段において画像データが移動されて空き領域となった正方形領域を移動先とする正方形領域の画像データを回転角度だけ回転させた状態で該移動先に移動することを前記巡回置換に基づいて順に行い、最後の移動先として規定され且つ画像データが移動されて空き領域となった正方形領域に前記第２記憶手段に移動された画像データを移動する回転処理と、を前記巡回置換毎に行なう処理手段、
として機能させるためのプログラム。
【請求項６】
回転対象の画像の画像データを記憶する第１記憶手段と、画像データの一時的な移動先として用いる第２記憶手段および第３記憶手段とを備えたコンピュータを、
前記回転対象の画像を同一サイズの複数の正方形領域に分割する分割手段、
前記回転対象の画像を回転したときの前記分割された正方形領域毎の移動先を規定した移動規則を求める移動規則導出手段、
前記求めた移動規則を１以上の巡回置換の形式に変換する変換手段、および
前記巡回置換において移動先として規定された正方形領域に移動するべき画像データを、前記第１記憶手段及び前記第２記憶手段から探し出して前記第３記憶手段に移動する第１移動処理と、前記第１記憶手段において前記移動先として規定された正方形領域に回転処理前の画像データが記憶されている場合に、該画像データを前記第１記憶手段及び前記第２記憶手段の空き領域に移動する第２移動処理と、前記第３記憶手段に移動された画像データを回転角度だけ回転させた状態で前記移動先として規定された正方形領域に移動する回転処理と、を前記巡回置換に基づいて順に行なう処理手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置及びプログラムに関する。
【背景技術】
【０００２】
従来、画像の回転処理を行う場合には、画像データ全体をフレームバッファに保存する必要があり、ハードウエアの負担が大きい。特に、処理後の画像をライン単位(もしくはバンド単位)で処理する事ができず、回転処理後の画像データ全体を保持する必要がある場合は、入力用と出力用の２面分のフレームバッファを持つ必要があった。
【０００３】
ところで、一面分のフレームバッファ（画像メモリ）と比較的小さなワークバッファのみを用いて画像を回転処理する装置として下記特許文献１に記載のような装置が提案されている。この装置では、画像メモリに格納された画像データをブロック単位でバッファメモリに読出し、この画像データを回転させた状態で画像メモリの元の領域に書き戻す。これにより、画像メモリには、各ブロック内では回転が終了した状態ではあるが、画像全体では未回転の状態の画像データが格納される。そして、印刷等の出力を行なう際には、画像メモリから画像回転方向に応じた順序で画像データを読み出すことで最終的に全体が回転した画像を出力する。
【特許文献１】特開２００４−２２２１９９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、画像全体が回転した完全な画像データを得ることができ、回転処理に必要なメモリ容量が少なくて済む画像処理装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
請求項１の発明の画像処理装置は、回転対象の画像の画像データを記憶する第１記憶手段と、前記回転対象の画像を同一サイズの複数の正方形領域に分割する分割手段と、前記回転対象の画像を回転したときの前記分割された正方形領域単位の移動先を規定した移動規則を求める移動規則導出手段と、前記求めた移動規則を１以上の巡回置換の形式に変換する変換手段と、少なくとも前記正方形領域１個分の画像データの記憶が可能な第２記憶手段と、前記巡回置換で最初の移動先として規定された正方形領域の画像データを前記第１記憶手段から前記第２記憶手段に移動する移動処理と、前記第１記憶手段において画像データが移動されて空き領域となった正方形領域を移動先とする正方形領域の画像データを回転角度だけ回転させた状態で該移動先に移動することを前記巡回置換に基づいて順に行い、最後の移動先として規定され且つ画像データが移動されて空き領域となった正方形領域に前記第２記憶手段に移動された画像データを移動する回転処理と、を前記巡回置換毎に行なう処理手段と、を備えている。
【０００６】
請求項２の発明の画像処理装置は、回転対象の画像の画像データを記憶する第１記憶手段と、前記回転対象の画像を同一サイズの複数の正方形領域に分割する分割手段と、前記回転対象の画像を回転したときの前記分割された正方形領域単位の移動先を規定した移動規則を求める移動規則導出手段と、前記求めた移動規則を１以上の巡回置換の形式に変換する変換手段と、少なくとも前記正方形領域１個分の画像データの記憶が可能な第２記憶手段及び第３記憶手段と、前記巡回置換において移動先として規定された正方形領域に移動するべき画像データを、前記第１記憶手段及び前記第２記憶手段から探し出して前記第３記憶手段に移動する第１移動処理と、前記第１記憶手段において前記移動先として規定された正方形領域に回転処理前の画像データが記憶されている場合に、該画像データを前記第１記憶手段及び前記第２記憶手段の空き領域に移動する第２移動処理と、前記第３記憶手段に移動された画像データを回転角度だけ回転させた状態で前記移動先として規定された正方形領域に移動する回転処理と、を前記巡回置換に基づいて順に行なう処理手段と、を前記巡回置換に基づいて順に行なう処理手段と、を備えている。
【０００７】
請求項３の発明は、請求項２に記載の画像処理装置において、前前記第１記憶手段および前記第２記憶手段の空き領域及び該空き領域に対する移動状態を管理する管理テーブルを前記第１移動処理後および前記第２移動処理後に更新する更新処理を更に行ない、該更新処理により更新された最新の管理テーブルを参照して前記第１移動処理および前記第２移動処理を行なうものである。
【０００８】
請求項４の発明は、請求項１〜請求項３のいずれか１項記載の画像処理装置において、前記分割手段は、前記回転対象の画像のサイズが前記正方形領域のサイズの整数倍でない場合には、整数倍となるように前記回転対象の画像の縁辺に余白を付加した状態で、前記回転対象の画像を同一サイズの複数の正方形領域に分割するものである。
【０００９】
請求項５の発明は、回転対象の画像の画像データを記憶する第１記憶手段、および画像データの一時的な移動先として用いる第２記憶手段を備えたコンピュータを、前記回転対象の画像を同一サイズの複数の正方形領域に分割する分割手段、前記回転対象の画像を回転したときの前記分割された正方形領域毎の移動先を規定した移動規則を求める移動規則導出手段、前記求めた移動規則を１以上の巡回置換の形式に変換する変換手段、および前記巡回置換で最初の移動先として規定された正方形領域の画像データを前記第１記憶手段から前記第２記憶手段に移動する移動処理と、前記第１記憶手段において画像データが移動されて空き領域となった正方形領域を移動先とする正方形領域の画像データを回転角度だけ回転させた状態で該移動先に移動することを前記巡回置換に基づいて順に行い、最後の移動先として規定され且つ画像データが移動されて空き領域となった正方形領域に前記第２記憶手段に移動された画像データを移動する回転処理と、を前記巡回置換毎に行なう処理手段、として機能させるためのプログラムである。
【００１０】
請求項６の発明は、回転対象の画像の画像データを記憶する第１記憶手段と、画像データの一時的な移動先として用いる第２記憶手段および第３記憶手段とを備えたコンピュータを、前記回転対象の画像を同一サイズの複数の正方形領域に分割する分割手段、前記回転対象の画像を回転したときの前記分割された正方形領域毎の移動先を規定した移動規則を求める移動規則導出手段、前記求めた移動規則を１以上の巡回置換の形式に変換する変換手段、および前記巡回置換において移動先として規定された正方形領域に移動するべき画像データを、前記第１記憶手段及び前記第２記憶手段から探し出して前記第３記憶手段に移動する第１移動処理と、前記第１記憶手段において前記移動先として規定された正方形領域に回転処理前の画像データが記憶されている場合に、該画像データを前記第１記憶手段及び前記第２記憶手段の空き領域に移動する第２移動処理と、前記第３記憶手段に移動された画像データを回転角度だけ回転させた状態で前記移動先として規定された正方形領域に移動する回転処理と、を前記巡回置換に基づいて順に行なう処理手段、として機能させるためのプログラムである。
【発明の効果】
【００１１】
請求項１の発明によれば、小さいメモリ容量で画像全体が回転した完全な画像データを得ることができる。
【００１２】
請求項２の発明によれば、回転対象の画像の形状が長方形であっても、小さいメモリ容量で画像全体が回転した完全な画像データを得ることができる。
【００１３】
請求項３の発明によれば、容易に使用可能な空き領域を見つけて画像データを移動できる。
【００１４】
請求項４の発明によれば、回転対象の画像のサイズが正方形領域のサイズの整数倍でない場合であっても、問題なく回転処理を行なうことができる。
【００１５】
請求項５の発明によれば、小さいメモリ容量で画像全体が回転した完全な画像データを得ることができる。
【００１６】
請求項６の発明によれば、回転対象の画像の形状が長方形であっても、小さいメモリ容量で画像全体が回転した完全な画像データを得ることができる。
【発明を実施するための最良の形態】
【００１７】
以下、図面を参照して、本発明の実施の形態を詳細に説明する。
【００１８】
図１は、画像処理装置であるコンピュータ１０の概略構成を示すブロック図である。
【００１９】
コンピュータ１０は、図１に示すように、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１２、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１４、及びＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１６を含んで構成されている。
【００２０】
ＣＰＵ１２は、コンピュータ１０の全体の動作を制御し、プログラムに従い後述する画像回転処理を実行する。
【００２１】
ＲＯＭ１４は、コンピュータ１０の起動時に動作するブートプログラムなどが記憶されている不揮発性の記憶装置である。
【００２２】
ＲＡＭ４０は、ＣＰＵ１２が実行するプログラムや、その実行において適宜変化するパラメータ等を記憶する揮発性の記憶装置であり、所謂ワークメモリとして使用されるものである。ＲＡＭ４０の一部の領域は、後述する画像回転処理に必要なソースブロックバッファや待避ブロックバッファの領域として確保される。また、回転処理対象の画像データを保持する領域（フレームバッファ）も確保される。
【００２３】
また、コンピュータ１０には、通信部１８、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）２０、接続ポート２２、及び読取装置２４が設けられており、これらは、バスを介してＣＰＵ１２に信号授受可能に接続されている。
【００２４】
通信部１８は、コンピュータ１０と直接又はネットワークを介して接続された外部装置とデータの送受信を行うものである。コンピュータ１０は、通信部１８を介して、スキャナからスキャンされたデータを受信したり、画像処理を施したデータを画像形成装置へ送信したりするようになっている。
【００２５】
ＨＤＤ２０は、ＯＳ（オペレーティングシステム）、後述する画像処理を実行するためのプログラム、プログラムの実行に用いられるデータ、及び通信部１８を介して外部装置と送受信されるデータ等が格納される不揮発性の記憶装置である。
【００２６】
接続ポート２２は、ＵＳＢ、ＩＥＥＥ１３９４等の接続部を有し、コンピュータ１０に外部機器を接続するためのポートである。この接続ポート２２を介して、ＵＳＢメモリ等の記憶媒体２３をコンピュータ１０に接続することができる。
【００２７】
読取装置２４は、光磁気ディスク、光ディスク、磁気ディスク等の記憶媒体２５が装着され、記憶媒体２５から記憶内容が伝達されるものであり、光磁気ディスクの記憶内容を読み取るための光磁気ディスク装置、光ディスクの記憶内容を読み取るための光ディスク装置、及び磁気ディスクの記憶内容を読み取るための磁気ディスク装置等がある。
【００２８】
このようなコンピュータ１０において、ＣＰＵ１２は、ＨＤＤ２０に記憶されているプログラムを読み出してＲＡＭ１６に格納し、ＲＡＭ１６に格納したプログラムの各々を実行する。本実施形態では、ＣＰＵ１２によりプログラムが実行されることによって、コンピュータ１０において、画像回転処理が実行される。
【００２９】
なお、ここでは、ＣＰＵ１２が実行するプログラムを記憶する記憶媒体は、ＨＤＤ２０に限定されず、例えば、記憶媒体２３，２５であってもよいし、電気通信回線上の搬送波のような伝送媒体であってもよい。
【００３０】
また、コンピュータ１０により回転処理が施されるデータは、記憶媒体２３，２５に記憶されたものであってもよいし、スキャナ等の外部装置から、通信部１８を介してコンピュータ１０に入力されるものであってもよい。
【００３１】
次に、本実施の形態に係るコンピュータ１０で行なわれる、画像回転処理の流れについて図２〜図４を参照し説明する。図２は、ＣＰＵ１２が実行する画像回転処理プログラムのメインルーチンの流れの一例を示すフローチャートである。また、図３は、図２のプログラムで呼び出されるサブルーチン（第１回転処理）の流れを示すフローチャートであり、同じく図４も、図２のプログラムで呼び出されるサブルーチン（第２回転処理）の流れを示すフローチャートである。
【００３２】
ステップ１００では、ＣＰＵ１２は、ＲＡＭ４０のフレームバッファに回転処理対象の画像データを格納し、該格納した画像データの画像を複数の同一サイズの正方形のブロックに分割する。このブロックのサイズは画像データのサイズ及び使用可能なメモリ容量に応じてその都度決定してもよいし、画像データのサイズ及び使用可能なメモリ容量に応じて予め定めておいてもよい。
【００３３】
ここで、図５を参照し、具体的な例を挙げて説明する。図５は、正方形の画像を正方形の小さなブロックで分割した場合の一例を示す図である。図５（Ａ）は回転処理対象の画像の一例を示し、図５（Ｂ）は、図５（Ａ）の画像を２画素×２画素の正方形のブロックで分割したときの状態を示している。なお、ここでは、画素単位の画像データの配列の様子が把握しやすいように、１から３６までの数字を各画素の画像データとして用いた。ＣＰＵ１２は、画像の分割後、図５（Ｃ）に示すように、各々のブロックに対し、その並び順に識別番号を付与する。ここでは、１から９までの数字（以下、ブロックナンバー、ＢＮと呼称）が付与されている。
【００３４】
次に、ステップ１０２で、ＣＰＵ１２は、回転対象の画像を回転したときのブロック単位の移動規則を求める。
【００３５】
図６（Ａ）に、回転前の各ブロックの配列状態の例を示す。これをブロック単位で時計回りに９０度回転すると、各ブロックは図６（Ｂ）のような配列となる。すなわち、
回転前のＢＮ１の領域には回転前のＢＮ７の画像データが移動し、
回転前のＢＮ２の領域には回転前のＢＮ４の画像データが移動し、
回転前のＢＮ３の領域には回転前のＢＮ１の画像データが移動し、
回転前のＢＮ４の領域には回転前のＢＮ８の画像データが移動し、
回転前のＢＮ５の領域には回転前のＢＮ５の画像データがそのまま残り、
回転前のＢＮ６の領域には回転前のＢＮ２の画像データが移動し、
回転前のＢＮ７の領域には回転前のＢＮ９の画像データが移動し、
回転前のＢＮ８の領域には回転前のＢＮ６の画像データが移動し、
回転前のＢＮ９の領域には回転前のＢＮ３の画像データが移動する。
【００３６】
このブロック単位の移動規則を置換の表記法で示すと以下のようになる。
【００３７】
【数１】
2009141659.tif 000003
【００３８】
この表記法において、括弧内の上の列は移動先のＢＮを示し、下の列は該移動先に移動するＢＮ（移動元のＢＮ）を示している。なお、上記では、便宜上、下の列の数字を上の列の数字に置換（移動）するという表記法で移動規則を表現している。
【００３９】
ステップ１０４では、ＣＰＵ１２は、上記求めた移動規則を巡回置換の形式に変換する。ここで、巡回置換とは、例えば、１を２に置換し、２を３に置換し、３を１に置換する場合のように、置換が巡回するものをいう。なお、上記図６（Ａ）、（Ｂ）に示した例において求めた移動規則を巡回置換の形式に変換すると、以下のようになる。
【００４０】
【数２】
2009141659.tif 000004
【００４１】
上記の例では、互いに素である３つの巡回置換の積に変換される。なお、このように巡回置換の形式に変換された各巡回置換毎の移動規則を単に巡回置換と呼称する。
【００４２】
変換された巡回置換のうち、最初の巡回置換（以下、第１巡回置換と呼称）は、ＢＮ７からＢＮ１に移動する移動操作、ＢＮ９からＢＮ７に移動する移動操作、ＢＮ３からＢＮ９に移動する移動操作、ＢＮ１からＢＮ３に移動する移動操作、の４つの移動操作から成り立っている。また、次の巡回置換（以下、第２巡回置換と呼称）は、ＢＮ４からＢＮ２に移動する移動操作、ＢＮ８からＢＮ４に移動する移動操作、ＢＮ６からＢＮ８に移動する移動操作、ＢＮ２からＢＮ６に移動する移動操作、の４つの移動操作から成り立っている。また、最後の巡回置換（以下、第３巡回置換と呼称）は、ＢＮ５からＢＮ５に移動する移動操作から成り立っている。
【００４３】
ステップ１０６では、ＣＰＵ１２は、回転対象の画像が正方形（条件１）か、或いはここで行なう回転処理の回転角度が１８０度（条件２）かを判断する。ＣＰＵ１２は、この２つの条件１，２のうち少なくとも一方を満たしていると判断した場合には（肯定判断）ステップ１０８に移行し、上記求めた各巡回置換毎に第１回転処理を行なう。また、２つの条件のいずれにも該当しない、すなわち画像が長方形且つ回転角度が９０度或いは２７０度の場合には、ＣＰＵ１２は、ステップ１０６で否定判断してステップ１１２に移行し、上記求めた各巡回置換毎に第２回転処理を行なう。第１回転処理及び第２回転処理では、上記求めた各巡回置換に従って、順番にブロック単位で画像データを移動（コピー）していき、最終的に完全な回転画像の画像データを得る。
【００４４】
まずは、ステップ１０８の第１回転処理について、図３のフローチャート及び図７〜図１２の説明図を参照しながら詳細に説明する。ここでは、上記図５に示した正方形の画像を時計回りに９０度回転する場合に行なわれる回転処理を例に挙げる。移動規則及び該移動規則から求められる巡回置換は、上記示した通りである。
【００４５】
図３のステップ１２０では、ＣＰＵ１２は、図７に示すように、第１回転処理に必要なバッファ領域（待避ブロックバッファ３２）をＲＡＭ１４に確保し、巡回置換の最初の移動操作における移動先ブロックの画像データを、回転対象の画像データ全体が格納されたフレームバッファ３０から読み出して該待避ブロックバッファ３２に待避（格納）する。例えば、第１巡回置換で回転処理する場合には、ＢＮ１の画像データを待避ブロックバッファ３２に待避する。
【００４６】
なお、待避ブロックバッファ３２に画像データを待避した後は、元の領域（ＢＮ１の領域）は空き領域となる。なお、待避後に元の領域から画像データを削除するようにしてもよいが、元の領域に画像データを残したままとする、すなわち、コピーすることで待避するようにしてもよい。いずれの場合でも、待避ブロックバッファ３２へ画像データを移動させた後は、元の領域は空き領域として扱う。図７では、画像データの移動状態（置換状態）が明瞭となるように、元の領域から画像データを削除した状態で図示している。なお、後述する図８〜１１においても画像データを移動した場合には、移動元から画像データを削除する形式で図示している。
【００４７】
また、待避ブロックバッファ３２の容量は、少なくとも上記ステップ１００で画像を複数のブロックに分割したときの１個分のブロックサイズと同じサイズがあれば足りる。
【００４８】
ステップ１２２では、ＣＰＵ１２は、これから行なう移動操作が当該巡回置換において最後の移動操作であるか否かを判断する。ここで否定判断された場合には、ステップ１２４に移行する。
【００４９】
ステップ１２４では、巡回置換どおりにフレームバッファ３０から移動元ブロックの画像データを読み出して、所定の回転角度だけ（本例では時計回りに９０度）回転させた状態でフレームバッファ３０の移動先ブロックの領域に書込む。例えば、第１巡回置換における最初の移動操作では、ＣＰＵ１２は、図８に示すように、ＢＮ７の画像データを９０度回転させた状態で、ＢＮ１の領域に書込む。
【００５０】
最後の移動操作までは、ステップ１２２及びステップ１２４の処理が繰り返される。これにより、第１巡回置換では、図８、図９、図１０に示すように各移動操作が順に行なわれることとなる。なお、図９は、ＢＮ９の画像データを９０度回転させた状態で、ＢＮ７の領域に書込んだ状態を示す図であり、図１０は、ＢＮ３の画像データを９０度回転させた状態で、ＢＮ９の領域に書込んだ状態を示す図である。
【００５１】
一方、ステップ１２２で、ＣＰＵ１２は、これから行なう移動操作が最後の移動操作であると判断した場合には、ステップ１２６に移行する。ステップ１２６では、ＣＰＵ１２は、待避ブロックバッファ３２に待避しておいたＢＮ１の画像データを読み出して、時計回りに９０度回転させた状態でフレームバッファ３０の移動先ブロックの領域に書込む。例えば、第１巡回置換では、ＣＰＵ１２は、図１１に示すように、待避ブロックバッファ３２に待避させておいたＢＮ１の画像データを９０度回転させた状態で、ＢＮ３の領域に書込む。このように、ステップ１２６の処理により、巡回置換における最後の移動操作が行なわれる。
【００５２】
１つの巡回置換についての第１回転処理が終了すると、図２のステップ１１０に移行する。ステップ１１０では、ＣＰＵ１２は、全ての巡回置換の第１回転処理が終了したか否かを判断し、まだ終了していないと判断した場合には、ステップ１０８に戻り、次の巡回置換について第１回転処理を行なう。また、ステップ１１０で、全ての巡回置換の第１回転処理が終了したと判断した場合には、画像回転処理のメインルーチンを終了する。これにより、第１巡回置換、第２巡回置換、第３巡回置換のそれぞれについて第１回転処理が行なわれ、最終的には図１２に示すように、フレームバッファ３０に、回転後の完全な画像データが格納される。
【００５３】
一方、図２のステップ１０６で否定判断された場合、すなわち、画像が長方形且つ回転角度が９０度或いは２７０度の場合には、第１回転処理をそのまま施すことはできないため、ステップ１１２で、第２回転処理を行なう。
【００５４】
ここで、画像全体が長方形の場合で回転角度が９０度或いは２７０度（−９０度）の場合に第１回転処理をそのまま行なうことができない理由について、正方形の画像を時計回りに９０度回転する場合と、長方形の画像を時計回りに９０度回転する場合とを比較して、説明する。
【００５５】
まず、図１３を用いて、正方形の画像を時計回りに９０度回転する場合について説明する。図１３（Ａ）は、回転前の画像の一例を示す図である。ここでは、各画素の画像データをＡ〜Ｐのアルファベットを用いて図示した。ところで、画像を構成する各画素の画像データは、実際には一次元に配列されて記憶される。従って、図１３（Ａ）に示す画像の各画素の画像データは、例えば図１３（Ｂ）に示すようなアドレス順（０〜１５の順）でフレームバッファ３０に格納されることとなる。また、この画像データを、２画素×２画素（２行２列）の正方形のブロックで分割すると、図１３（Ｂ）に示すように分割される。
【００５６】
図１３（Ｃ）は、図１３（Ａ）の画像を時計回りに９０度回転したときの画像を示す図であり、図１３（Ｄ）は、回転後の画像データの格納アドレスを示す図である。画像が正方形の場合には、９０度回転しても縦横の長さが変化しないため、図１３（Ｂ）および図１３（Ｄ）に示すように、回転前と回転後とで各ブロック内のアドレスの対応関係が変化しない。従って、第１回転処理のように回転前のブロック単位でそのまま画像データの移動を行なっても何ら問題は発生しない。
【００５７】
次に、図１４を用いて、長方形の画像を時計回りに９０度回転する場合について説明する。図１４（Ａ）は、回転前の画像の一例を示す図である。この画像の各画素の画像データは、図１４（Ｂ）に示すようなアドレス順（０〜２３の順）でフレームバッファ３０に格納される。この画像データを、図１４（Ｂ）に示すように２画素×２画素（２行２列）の正方形のブロックで分割すると、図１４（Ｂ）に示すように分割される。
【００５８】
図１４（Ｃ）は、図１４（Ａ）の画像を時計回りに９０度回転したときの画像を示す図であり、図１４（Ｄ）は、回転後の画像データの格納アドレスを示す図である。これら図から明らかなように、画像が長方形の場合には、９０度回転すると縦横の長さが変化するため、ブロック毎のアドレスがずれる。例えば、図１４（Ｂ）に示すように、回転前では左上の太枠で示したブロックのアドレスは０，１、４、５となるが、図１４（Ｄ）に示すように、回転後では左上のブロックのアドレスは０，１、６、７となる（ブロック内の２ライン目のアドレスが異なっている）。他のブロックも同様である。このように、回転前と回転後とでブロック単位のアドレスが対応しないため、この場合には、第１回転処理のような単純なブロック間のコピーを行なうことができない。
【００５９】
なお、１８０度回転であれば、縦横の長さが変化することはないため、このような問題は発生しない。従って、回転対象の画像が長方形且つ回転角度が９０度または２７０度の場合には、回転前だけでなく回転後のアドレスも考慮した回転処理を施す必要がある。
【００６０】
そこで、本実施の形態では、回転対象の画像が長方形且つ回転角度が９０度または２７０度の場合には図４のフローチャートに示す第２回転処理を行なう。
【００６１】
なお、以下では、図１４（Ａ）に示した長方形の画像を時計回りに９０度回転する場合に行なわれる回転処理を具体例として説明する。この例においても、図２に示したメインフローチャートのステップ１００で回転対象の画像を所定のサイズの（ここでは２画素×２画素、すなわち２行２列）正方形のブロックで分割し、図１５（Ａ）に示すように、各ブロックに１〜６のブロックナンバー（ＢＮ）を付与する。これを時計回りに９０度回転した状態が図１５（Ｂ）である。従って、この例で求められる移動規則は、以下のようになる。
【００６２】
【数３】
2009141659.tif 000005
【００６３】
この移動規則も、上記と同様に、括弧内の上の列が移動先のＢＮを示し、下の列が移動元のＢＮを示している。この移動規則からステップ１０４で求められる巡回置換は、以下の通りである。
【００６４】
【数４】
2009141659.tif 000006
【００６５】
上記例では、１つの巡回置換に変換される。以下、この巡回置換を用いて第２回転処理を行なう。なお、第２回転処理では、各ブロックを構成する行（ライン）にもブロック毎に番号を付す。そして、この番号（以下、ブロックラインナンバー、ＬＮ）をブロックナンバーＢＮと共に用いて、フレームバッファ３０における回転対象の画像データの待避領域や移動領域を、各ブロックのライン単位で指定するものとする。具体的には（ＢＮ，ＬＮ）と指定する。
【００６６】
なお、本実施の形態では、２行２列のブロックで分割するため、各ブロックを構成するラインは２ラインであり、ＬＮとして１ライン目には０を、２ライン目には１を付与する。また、ＢＮは前述したように１〜６までの番号が付与されている。従って、フレームバッファ３０における回転前の各ブロックの各ライン毎の領域を（ＢＮ，ＬＮ）の形式で示すと、図１６（Ｂ）のようになる。
【００６７】
回転前の画像データのアドレスと各ブロックは、図１６（Ａ）に示す関係にあるが、回転後の画像データのアドレスと各ブロックは、図１６（Ｃ）に示すような関係となるため、回転後の各ブロックの各ライン毎の領域を、回転前のブロック及びラインを基準にして（ＢＮ，ＬＮ）の形式で表すと、図１６（Ｄ）のように表される。以下では、（ＢＮ，ＬＮ）をＢＬアドレスと呼称して、通常のアドレスと区別して説明する。
【００６８】
以上説明した事項を前提とした上で、図４に示す第２回転処理について説明する。まず、ステップ１４０では、ＣＰＵ１２は、図１７（Ａ）に示すように、第２回転処理に必要なバッファ領域（ソースブロックバッファ３１、待避ブロックバッファ３２）をＲＡＭ１４に確保する。ソースブロックバッファ３１及び待避ブロックバッファ３２は、それぞれ、上記ステップ１００で画像を複数のブロックに分割したときの１個分のブロックサイズと同じサイズだけ確保される。更に、ＣＰＵ１２は、第２回転処理に用いる待避先アドレス格納テーブルをＲＡＭ１４の所定の領域に生成して初期化処理を行なう。初期化処理により待避先アドレス格納テーブルは図１７（Ｃ）に示すような状態となる。
【００６９】
第１回転処理では、待避ブロックバッファ３２が１つあれば、必要な画像データを待避して順次移動操作することができたが、第２回転処理では、上記説明したように、回転前と回転後とでブロック単位のアドレスが対応しないため、待避先は待避ブロックバッファ３２だけでは不足する。この不足を補うために新たにバッファ領域を設けると、必要なメモリ容量が増大する。そこで、本実施の形態では、画像データの移動操作の過程でフレームバッファ３０に一時的に利用可能な空き領域が発生する点に着目し、これを有効利用しながら巡回置換の移動操作を順次行なうことで第２回転処理を行なう。待避先アドレス格納テーブルは、フレームバッファ３０に発生した空き領域や待避ブロックバッファ３２を待避先として管理するために用いられる。
【００７０】
待避先アドレス格納テーブルは、フラグFa、フラグFb、待避先の領域を表すToData、該ToDataの領域に待避した画像データが元々格納されていた領域を表すFromData、の４つの項目から構成される。
【００７１】
Faは、画像データの待避先としてToDataの領域が使用可能か否かを示すフラグである。Faが０の場合には、ToDataが使用不可能であることを示し、Faが１の場合には、ToDataが使用可能であることを示す。Fbは、有効な画像データがToDataの領域に待避されているか否かを示すフラグである。Fbが０の場合には、有効な画像データがToDataの領域に待避されていない状態であることを示し、Fbが１の場合には、有効な画像データがToDataの領域に待避されている状態であることを示す。
【００７２】
ToDataには、待避先の領域を示すＢＬアドレスが格納される。FromDataには、対応するToDataの領域に待避した画像データが元々格納されていた領域を示すＢＬアドレスが格納される。なお、ToData及びFromDataに格納されるＢＬアドレスは全て回転前のブロック及びラインを基準にしたときのＢＬアドレスとする。また、以下の説明においても、特に断りが無い限り、ＢＬアドレスは、回転前のブロック及びラインを基準にしたときのＢＬアドレスを意味するものとする。
【００７３】
本実施の形態では、便宜上、待避ブロックバッファ３２にはブロックナンバー「０」が付与される。従って、待避ブロックバッファ３２のＢＬアドレスは（０，０）及び（０，１）となる。初期化処理が終了すると待避先アドレス格納テーブルは、図１７（Ｃ）に示すように、待避ブロックバッファ３２の情報のみが登録された状態となる。待避ブロックバッファ３２は常に待避先として使用可能であるため、Faは常に１となる。
【００７４】
図１７（Ｂ）は、フレームバッファ３０上の回転前における画像データの格納状態を模式的に表した図である。ここでは画像データの配列は図１４（Ａ）に等しいが、後述する処理内容が把握しやすいように、縦横の関係を回転後の状態で示した（図１６（Ａ）（Ｃ）も参照。）。この状態から、上記求めた巡回置換の移動操作に従って以下に示す処理を実行する。
【００７５】
ステップ１４２では、ＣＰＵ１２は、待避先アドレス格納テーブルを参照して、巡回置換において、これから行なう移動操作における移動元ブロックの画像データが格納されている領域を探し出す。具体的には、待避先アドレス格納テーブルのFromDataに、移動元ブロックのＢＬアドレスが格納されているか否かを確認し、FromDataに移動元ブロックのＢＬアドレスが格納されていれば、待避先アドレス格納テーブルにおいて当該FromDataに対応して格納されているToDataのＢＬアドレスを探索結果とする。また、待避先アドレス格納テーブルのFromDataに、移動元ブロックのＢＬアドレスが格納されていなければ、移動元ブロックのＢＬアドレスをそのまま探索結果とする（図１６も参照）。
【００７６】
上記説明した巡回置換の例では、最初の移動操作としてＢＮ５をＢＮ１に移動する処理が行なわれるため、ＣＰＵ１２は、回転前のＢＮ５のＢＬアドレス（５，０）、（５，１）を待避先アドレス格納テーブルのFromDataから探し出す。図１７（Ｃ）に示すように、待避先アドレス格納テーブルの初期状態では、FromDataには何も格納されていないため、ＢＮ５の２つのＢＬアドレス（５，０）、（５，１）がそのまま探索結果となる。
【００７７】
ステップ１４４では、ＣＰＵ１２は、上記探索結果が示す領域から移動元ブロックの画像データを読み出して、ソースブロックバッファ３１に格納する。上記説明した例では、探索結果はＢＬアドレス（５，０）、（５，１）であるため、図１８（Ａ）及び（Ｂ）に示すように、フレームバッファ３０のＢＬアドレス（５，０）、（５，１）で指定される領域（この場合には、アドレス１６，１７，２０，２１の領域）から画像データを読出し、ソースブロックバッファ３１に格納する。
【００７８】
なお、ソースブロックバッファ３１に移動元ブロックの画像データを格納した後は、元の領域は空き領域となる。なお、移動後に元の領域から画像データを削除するようにしてもよいが、元の領域に画像データを残したままとする、すなわち、コピーすることで移動するようにしてもよい。いずれの場合でも、画像データを移動させた後は、元の領域は空き領域として扱う。図１８（Ａ）（Ｂ）では、画像データの移動状態（置換状態）が明瞭となるように、元の領域から画像データを削除した状態で図示している。なお、後述する図１９〜図３２も同様に画像データを移動した場合には、移動元から画像データを削除する形式で図示している。
【００７９】
ステップ１４６では、ＣＰＵ１２は、待避先アドレス格納テーブルを更新する。ステップ１４６での更新は、以下の更新ルールに従う。
【００８０】
１）ステップ１４４で、待避ブロックバッファ３２から画像データを読み出した場合には、待避先アドレス格納テーブルの当該読み出した領域に対応するフラグFbを０にする。
【００８１】
２）ステップ１４４で、フレームバッファ３０から画像データを読み出した場合には、待避先アドレス格納テーブルに、当該読みだした領域のＢＬアドレスを新規に登録する。具体的には、待避先アドレス格納テーブルに新たな行を追加して、当該読みだした領域のＢＬアドレスをToDataに格納し、フラグFaを１に、フラグFbを０にして、FromDataは空のままとする。ただし、当該読みだした領域のＢＬアドレスが当該移動操作における移動先ブロックのＢＬアドレスに一致する場合には、新規登録はしない。また、新たな行を追加する場合は、既存の行を走査してFa=0の行があればその行を再利用する事がメモリの節約の上で極めて好ましいが、必須ではない。
【００８２】
３）なお、フレームバッファ３０から画像データを読み出した場合であっても、待避先アドレス格納テーブルに当該読みだした領域のＢＬアドレスが既にToDataとして登録されていた場合には、再度の登録はせずに、対応するフラグFbを０にする。
【００８３】
４）さらに、待避先アドレス格納テーブルに、当該移動操作における移動先ブロックのＢＬアドレスに一致するＢＬアドレスがToDataに格納されていた場合には、そのToDataに対応するフラグFaを０にする。フラグFaを０にすることにより、それ以降、そのToDataのＢＬアドレスの領域は待避先として使用不可能となる。
【００８４】
このような更新ルールに従うと、上記巡回置換の例では、最初の移動操作において、ＢＬアドレス（５，０）、（５，１）で指定される領域から移動元ブロックの画像データを読出してソースブロックバッファ３１に格納した後は、待避先アドレス格納テーブルは、図１８（Ｃ）に示すように変更される。ＢＬアドレス（５，０）（５，１）がToDataとして新規に登録されている。
【００８５】
ステップ１４８では、待避先アドレス格納テーブルを参照して、移動先ブロックの画像データの待避が必要か否かを判断する。その際、移動先ブロックの２つのＢＬアドレスの各々について、それぞれ待避が必要か否かを別個独立に判断する。従って、２つのＢＬアドレスのうち一方に格納された画像データについては待避が必要であると判断され、他方については待避が不要であると判断される場合もあり得る。すなわち、ＣＰＵ１２は、移動先ブロックのライン毎に待避が必要か否かを判断する。待避が必要か否かの判断は、以下の待避ルールに従う。
【００８６】
１）待避先アドレス格納テーブルのToDataに移動先ブロックのＢＬアドレスが登録されており、このToDataに対応するフラグFbが１であれば、当該ＢＬアドレスが示す領域に格納されている画像データを待避すべきであると判断する（ステップ１５０、Ｙ）。
【００８７】
２）移動先ブロックのＢＬアドレスと移動元ブロックのＢＬアドレスとが一致せず、待避先アドレス格納テーブルのFromDataに移動先ブロックのＢＬアドレスが登録されていない場合には、移動先ブロックの当該ＢＬアドレスが示す領域に格納されている画像データを待避すべきであると判断する（ステップ１５０、Ｙ）。
【００８８】
３）上記ルール１及び２のいずれにも該当しない場合には、移動先ブロックのＢＬアドレスについては画像データの待避は不要と判断する（ステップ１５０、Ｎ）。
【００８９】
例えば、待避先アドレス格納テーブルのToDataに移動先ブロックのＢＬアドレスが登録されていても、このToDataに対応するフラグFbが０であれば、当該ＢＬアドレスが示す領域には有効な画像データが格納されていない状態であるため待避は不要であり、単にFaを0にするだけで良い。また、移動先ブロックのＢＬアドレスと移動元ブロックのＢＬアドレスとが一致している場合には、当該ＢＬアドレスの画像データは既にソースブロックバッファ３１に格納済であるため、待避は不要である。
【００９０】
このような待避ルールに従うと、上記巡回置換における最初の移動操作において、移動先ブロックＢＮ１のＢＬアドレスは（１，０）と（２，１）であるため（図１６（Ｄ）参照）、双方とも待避が必要であると判断される。
【００９１】
ステップ１５０で肯定判断された場合には、ステップ１５２で、ＣＰＵ１２は、待避先アドレス格納テーブルを参照して、待避先を決定する。具体的には、待避先アドレス格納テーブルのフラグFaが１、フラグFaが０のToDataに格納されたＢＬアドレスを待避先として決定する。なお、ステップ１５０で２つのＢＬアドレスについて待避先が必要と判断された場合には、待避先を２つ決定する。
【００９２】
例えば、図１８（Ｃ）に示す待避先アドレス格納テーブルでは、登録されているすべてのToDataについて待避先として用いることができ、そのうちの２つ、例えば、（０，０）（１，０）、を待避先として決定する。
【００９３】
ステップ１５４では、ＣＰＵ１２は、移動元ブロックの領域から画像データを読みだして、上記決定した待避先が示す領域に待避（格納）する。（０，０）（１，０）を待避先として決定した場合には、図１９（Ａ）、（Ｂ）に示すように、待避ブロックバッファ３２の（０，０）と（１，０）に移動元ブロックの（１，０）と（２，１）の画像データを格納する。
【００９４】
ステップ１５６では、ＣＰＵ１２は、待避先アドレス格納テーブルを更新する。具体的には、上記待避先のフラグFbを１にし、該待避先に待避した画像データのＢＬアドレスをFromDataに登録する。図１９（Ｃ）に、図１９（Ａ）、（Ｂ）のように画像データを待避した場合の待避先アドレス格納テーブルの更新結果を示す。
【００９５】
ＣＰＵ１２は、ステップ１５６の処理終了後、或いはステップ１５０で否定判断した後は、ステップ１５８に移行し、ソースブロックバッファ３１の画像データを読出し、所定の回転角度（本例では時計回りに９０度）回転させた状態でフレームバッファ３０の移動先ブロックの領域に書込む。上記巡回置換における最初の移動操作では、ＣＰＵ１２は、図２０に示すように、ソースブロックバッファ３１の各画像データを９０度回転させた状態で、移動先ブロックＢＮ１に該当する（１，０）及び（２，１）の領域に書込む。図において、下線が引かれた画像データが、移動操作が終了した書込済の画像データであることを示している。
【００９６】
ステップ１６０では、ＣＰＵ１２は、当該巡回置換の全ての移動操作が終了したか否かを判断する。ここで否定判断された場合には、ステップ１４２に戻り、次の移動操作について上記ステップ１４２〜１５８を繰り返す。また、ステップ１６０で肯定判断された場合には、１つの巡回置換についての第２回転処理が終了したため、図２のステップ１１４に移行する。
【００９７】
ステップ１１４では、ＣＰＵ１２は、全ての巡回置換の回転処理が終了したか否かを判断し、まだ終了していないと判断した場合には、ステップ１１２に戻り、次の巡回置換について第２回転処理を行なう。また、ステップ１１４で、全ての巡回置換の回転処理が終了したと判断した場合には、画像回転処理のメインルーチンを終了する。これにより、上記ステップ１０４で求めた巡回置換の各々について、第２回転処理が行なわれ、最終的には、フレームバッファ３０に、回転後の完全な画像データが格納される。
【００９８】
上記では、巡回置換における最初の移動操作を例示しながら第２回転処理について説明したが、以下、それ以降の移動操作についても、図２１〜図３２を参照しながら簡単に説明する。
【００９９】
＜２番目の移動操作：ＢＮ４をＢＮ５に移動する＞
【０１００】
ＣＰＵ１２は、待避先アドレス格納テーブルのFromDataに、移動元ブロックＢＮ４のＢＬアドレス（４，０）（４，１）が格納されているか否かを確認する（ステップ１４２）。この時点では、図１９（Ｃ）に示すように、FromDataに移動元ブロックＢＮ４のＢＬアドレス（４，０）（４，１）は格納されていないため、ＣＰＵ１２は、図１６および図２１（Ａ）（Ｂ）に示すように、フレームバッファ３０のＢＬアドレス（４，０）、（４，１）で指定される領域（この場合には、アドレス１０，１１，１４，１５の領域）から画像データを読出し、ソースブロックバッファ３１に格納する。
【０１０１】
そして、ＣＰＵ１２は、前述の更新ルールに従って、図２１（Ｃ）に示すように待避先アドレス格納テーブルを更新する（ステップ１４６）。当該読みだした領域のＢＬアドレス（４，０）、（４，１）のうちＢＬアドレス（４，１）については、移動先ブロックのＢＬアドレス（４，１）（５，１）の一方に一致するため、新規登録はされていない。
【０１０２】
次に、ＣＰＵ１２は、待避先アドレス格納テーブルを参照して、前述の待避ルールに従って、移動先ブロックの画像データの待避が必要か否かを判断する（ステップ１４８）。ここでは、移動先ブロックＢＮ５のＢＬアドレス（４，１）（５，１）が示す領域には有効な画像データが格納されていないため、待避は不要と判断される（ステップ１５０、Ｎ）。
【０１０３】
ＣＰＵ１２は、図２２（Ａ）、（Ｂ）に示すように、ソースブロックバッファ３１の画像データを読出し、時計回りに９０度回転させた状態でフレームバッファ３０の移動先ブロックＢＮ５の（４，１）（５，１）の領域に書込む（ステップ１５８）。
【０１０４】
＜３番目の移動操作：ＢＮ６をＢＮ４に移動する＞
【０１０５】
ＣＰＵ１２は、待避先アドレス格納テーブルのFromDataに、移動元ブロックＢＮ６のＢＬアドレス（６，０）（６，１）が格納されているか否かを確認する（ステップ１４２）。この時点では、図２１（Ｃ）に示すように、FromDataに移動元ブロックＢＮ６のＢＬアドレス（６，０）（６，１）は格納されていないため、ＣＰＵ１２は、図１６および図２３（Ａ）（Ｂ）に示すように、フレームバッファ３０のＢＬアドレス（６，０）、（６，１）で指定される領域（この場合には、アドレス１８，１９，２２，２３の領域）から画像データを読出し、ソースブロックバッファ３１に格納する（ステップ１４４）。そして、ＣＰＵ１２は、前述の更新ルールに従って、図２３（Ｃ）に示すように待避先アドレス格納テーブルを更新する（ステップ１４６）。
【０１０６】
次に、ＣＰＵ１２は、待避先アドレス格納テーブルを参照して、前述の待避ルールに従って、移動先ブロックの画像データの待避が必要か否かを判断する（ステップ１４８）。ここでは、移動先ブロックＢＮ４のＢＬアドレス（３，１）（６，０）のうち、待避ルール２に該当する（３，１）の領域の画像データについては待避する必要があると判断する（ステップ１５０、Ｙ）。
【０１０７】
ＣＰＵ１２は、図２３（Ｃ）に示す待避先アドレス格納テーブルにおいて、フラグFaが１、フラグFaが０のToDataに格納されたＢＬアドレスを待避先として決定する。例えば、ＣＰＵ１２は、ＢＬアドレス（５，０）を待避先として決定する（ステップ１５２）。そして、ＣＰＵ１２は、図２４（Ａ），（Ｂ）に示すように、移動元ブロックＢＮ４のＢＬアドレス（３，１）の領域から画像データを読みだして、上記待避先として決定したＢＬアドレス（５，０）の領域に待避（格納）する（ステップ１５４）。
【０１０８】
待避後、図２４（Ｃ）に示すように、ＣＰＵ１２は、待避先アドレス格納テーブルの上記待避先のフラグFbを１にし、該待避先に待避した画像データのＢＬアドレス（３，１）をFromDataに登録する（ステップ１５６）。
【０１０９】
ＣＰＵ１２は、図２５（Ａ）、（Ｂ）に示すように、ソースブロックバッファ３１の画像データを読出し、時計回りに９０度回転させた状態でフレームバッファ３０の移動先ブロックＢＮ４の（３，１）（６，０）の領域に書込む（ステップ１５８）。
【０１１０】
＜４番目の移動操作：ＢＮ２をＢＮ６に移動する＞
【０１１１】
ＣＰＵ１２は、待避先アドレス格納テーブルのFromDataに、移動元ブロックＢＮ２のＢＬアドレス（２，０）（２，１）が格納されているか否かを確認する（ステップ１４２）。この時点では、図２４（Ｃ）に示すように、移動元ブロックＢＮ２のＢＬアドレス（２，１）はFromDataに格納されているため、ＣＰＵ１２は、このFromDataに対応するToDataのＢＬアドレス（０，１）で指定される待避ブロックバッファ３２の領域から画像データを読み出す。また、移動元ブロックＢＮ２のＢＬアドレス（２，０）は、FromDataに格納されていないため、ＣＰＵ１２は、ＢＬアドレス（２，０）で指定される領域（この場合には、アドレス２，３の領域）から画像データを読出す。ＣＰＵ１２は、図２６（Ａ），（Ｂ）に示すように、読みだした画像データを、ソースブロックバッファ３１に格納する（ステップ１４４）。
【０１１２】
そして、ＣＰＵ１２は、前述の更新ルールに従って、図２６（Ｃ）に示すように待避先アドレス格納テーブルを更新する（ステップ１４６）。ここでは、ToData（０，１）に対応するフラグFbが０になり、ToData（５，０）と（６，１）に対応するフラグFaが０になっている。
【０１１３】
次に、ＣＰＵ１２は、待避先アドレス格納テーブルを参照して、前述の待避ルールに従って、移動先ブロックの画像データの待避が必要か否かを判断する（ステップ１４８）。ここでは、移動先ブロックＢＮ６のＢＬアドレス（５，０）（６，１）のうち、待避ルール１に該当する（５，０）の領域の画像データは待避する必要があると判断する（ステップ１５０、Ｙ）。
【０１１４】
ＣＰＵ１２は、図２６（Ｃ）に示す待避先アドレス格納テーブルにおいて、フラグFaが１、フラグFaが０のToDataに格納されたＢＬアドレスを待避先として決定する。例えば、ＣＰＵ１２は、ＢＬアドレス（０，１）を待避先として決定する（ステップ１５２）。そして、ＣＰＵ１２は、図２７（Ａ），（Ｂ）に示すように、ＢＬアドレス（５，０）の領域から画像データを読みだして、上記待避先として決定したＢＬアドレス（０，１）の領域に待避（格納）する（ステップ１５４）。待避後、図２７（Ｃ）に示すように、ＣＰＵ１２は、待避先のフラグFbを１にし、該待避先に待避した画像データのＢＬアドレス（３，１）をFromDataに登録して、待避先アドレステーブルを更新する（ステップ１５６）。
【０１１５】
ＣＰＵ１２は、図２８（Ａ）、（Ｂ）に示すように、ソースブロックバッファ３１の画像データを読出し、時計回りに９０度回転させた状態でフレームバッファ３０の移動先ブロックＢＮ６の（５，０）（６，１）の領域に書込む（ステップ１５８）。
【０１１６】
＜５番目の移動操作：ＢＮ３をＢＮ２に移動する＞
【０１１７】
ＣＰＵ１２は、待避先アドレス格納テーブルのFromDataに、移動元ブロックＢＮ２のＢＬアドレス（３，０）（３，１）が格納されているか否かを確認する（ステップ１４２）。この時点では、図２７（Ｃ）に示すように、移動元ブロックＢＮ３のＢＬアドレス（３，１）はFromDataに格納されているため、ＣＰＵ１２は、このFromDataに対応するToDataのＢＬアドレス（０，１）で指定される待避ブロックバッファ３２の領域から画像データを読み出す。また、移動元ブロックＢＮ３のＢＬアドレス（３，０）は、FromDataに格納されていないため、ＣＰＵ１２は、ＢＬアドレス（３，０）で指定される領域（この場合には、アドレス８，９の領域）から画像データを読出す。ＣＰＵ１２は、図２９（Ａ），（Ｂ）に示すように、読みだした画像データを、ソースブロックバッファ３１に格納する（ステップ１４４）。
【０１１８】
ＣＰＵ１２は、前述の更新ルールに従って、図２９（Ｃ）に示すように待避先アドレス格納テーブルを更新する（ステップ１４６）。ここでは、ToData（０，１）に対応するフラグFbが０になり、ToData（２，０）に対応するフラグFaが０になっている。
【０１１９】
次に、ＣＰＵ１２は、待避先アドレス格納テーブルを参照して、前述の待避ルールに従って、移動先ブロックの画像データの待避が必要か否かを判断する（ステップ１４８）。ここでは、移動先ブロックＢＮ２のＢＬアドレス（２，０）（３，０）が示す領域には有効な画像データが格納されていないため、待避は不要と判断される（ステップ１５０、Ｎ）。
【０１２０】
そして、ＣＰＵ１２は、図３０（Ａ）、（Ｂ）に示すように、ソースブロックバッファ３１の画像データを読出し、時計回りに９０度回転させた状態でフレームバッファ３０の移動先ブロックＢＮ２の（２，０）（３，０）の領域に書込む（ステップ１５８）。
【０１２１】
＜６番目の移動操作：ＢＮ１をＢＮ３に移動する＞
【０１２２】
ＣＰＵ１２は、待避先アドレス格納テーブルのFromDataに、移動元ブロックＢＮ１のＢＬアドレス（１，０）（１，１）が格納されているか否かを確認する（ステップ１４２）。この時点では、図２９（Ｃ）に示すように、移動元ブロックＢＮ１のＢＬアドレス（１，０）はFromDataに格納されているため、ＣＰＵ１２は、このFromDataに対応するToDataのＢＬアドレス（０，０）で指定される待避ブロックバッファ３２の領域から画像データを読み出す。また、移動元ブロックＢＮ１のＢＬアドレス（１，１）は、FromDataに格納されていないため、ＣＰＵ１２は、ＢＬアドレス（１，１）で指定される領域（この場合には、アドレス４，５の領域）から画像データを読出す。ＣＰＵ１２は、図３１（Ａ），（Ｂ）に示すように、読みだした画像データを、ソースブロックバッファ３１に格納する（ステップ１４４）。そして、ＣＰＵ１２は、前述の更新ルールに従って、図３１（Ｃ）に示すように待避先アドレス格納テーブルを更新する（ステップ１４６）。
【０１２３】
次に、ＣＰＵ１２は、待避先アドレス格納テーブルを参照して、前述の待避ルールに従って、移動先ブロックの画像データの待避が必要か否かを判断する（ステップ１４８）。ここでは、移動先ブロックＢＮ３のＢＬアドレス（１，０）（４，０）が示す領域には有効な画像データが格納されていないため、待避は不要と判断される（ステップ１５０、Ｎ）。
【０１２４】
そして、ＣＰＵ１２は、図３２（Ａ）、（Ｂ）に示すように、ソースブロックバッファ３１の画像データを読出し、時計回りに９０度回転させた状態でフレームバッファ３０の移動先ブロックＢＮ３の（１，０）（４，０）の領域に書込む（ステップ１５８）。この時点で、回転処理は終了する。
【０１２５】
このように巡回置換の順に、順次画像データを移動していくことにより、最終的に、図３２（Ｂ）に示すように完全な回転画像がフレームバッファ３０に生成される。
【０１２６】
なお、上記実施の形態では、回転対象の画像のサイズが、ブロックサイズの整数倍である場合を例に挙げて説明したが、画像サイズがブロックサイズの整数倍でない場合は、余白を適切な方向に付加して処理を行なうようにしてもよい。例えば、横方向のブロック数と縦方向のブロック数の比が、２：３や、３：４などの小さな整数比になるようにブロックサイズと余白の幅を選ぶようにする。巡回置換に従って書き込みを行う事で、画像データの退避が発生する確率を大幅に減らす事が出来るが、小さな整数比にする事で、さらにその効果が増すものである。
【０１２７】
なお、回転対象の画像が長方形の場合であっても、余白を付加して正方形の状態にして常に第１回転処理を行なう方法も考えられる。こうした方法は、回転対象の画像が正方形に近い長方形であれば、回転処理の効率は悪化しないが、縦と横の長さが極端に異なる長方形の場合には、上記第２回転処理を行なう場合に比べて、付加すべき余白のサイズも著しく大きくなり、必要なメモリ容量や回転処理に要する手数が増加することがあるため、第２回転処理で行なうほうが好ましい。
【０１２８】
また、上記実施の形態では、回転対象の画像や回転角度に応じて回転処理の方法を異ならせたが、これに限定されず、どのような画像、回転角度であっても、常に第２回転処理を行なうようにしてもよい。
【０１２９】
また、上記実施の形態では、待避先アドレス格納テーブルにおいて、フラグFaを用いて、ToDataに示した領域が使用可能か否かを管理するようにしたが、フラグFaを用いずに使用可能なものだけ待避先アドレス格納テーブルに登録し、使用不能になったときにテーブルから削除するようにしてもよい。
【図面の簡単な説明】
【０１３０】
【図１】画像処理装置であるコンピュータ１０の概略構成を示すブロック図である。
【図２】ＣＰＵが実行する画像回転処理プログラムのメインルーチンの流れの一例を示すフローチャートである。
【図３】図２のプログラムで呼び出されるサブルーチン（第１回転処理）の流れを示すフローチャートである。
【図４】図２のプログラムで呼び出されるサブルーチン（第２回転処理）の流れを示すフローチャートである。
【図５】正方形の画像を正方形の小さなブロックで分割した場合の一例を示す図である。
【図６】（Ａ）は、回転前のブロックの配列状態の例を示す図であり、（Ｂ）は、回転後の配列状態を示す図である。
【図７】ＢＮ１の画像データの待避ブロックバッファに待避した状態を示す図である。
【図８】ＢＮ７の画像データを９０度回転させた状態で、ＢＮ１の領域に書込んだ状態を示す図である。
【図９】ＢＮ９の画像データを９０度回転させた状態で、ＢＮ７の領域に書込んだ状態を示す図である。
【図１０】ＢＮ３の画像データを９０度回転させた状態で、ＢＮ９の領域に書込んだ状態を示す図である。
【図１１】待避ブロックバッファに待避させておいたＢＮ１の各画像データを９０度回転させた状態で、ＢＮ３の領域に書込んだ状態を示す図である。
【図１２】回転処理終了後のフレームバッファの画像データ格納状態を示す図である。
【図１３】（Ａ）は、回転前の画像（正方形）の一例を示す図であり、（Ｂ）は、（Ａ）の画像をブロック分割したときの各ブロックとアドレスとの関係を示す図であり、（Ｃ）は、（Ａ）の画像を時計回りに９０度回転したときの画像を示す図であり、（Ｄ）は、各ブロックとアドレスとの関係を示す図である。
【図１４】（Ａ）は、回転前の画像（長方形）の一例を示す図であり、（Ｂ）は、（Ａ）の画像をブロック分割したときの各ブロックとアドレスとの関係を示す図であり、（Ｃ）は、（Ａ）の画像を時計回りに９０度回転したときの画像を示す図であり、（Ｄ）は、各ブロックとアドレスとの関係を示す図である。
【図１５】（Ａ）は、回転前のブロックの配列状態の例を示す図であり、（Ｂ）は、回転後の配列状態を示す図である。
【図１６】（Ａ）は回転前の画像データのアドレスと各ブロックとの関係を示す図であり、（Ｂ）は、回転前の各ブロックの各ライン毎の領域を（ＢＮ，ＬＮ）の形式で示した図であり、（Ｃ）は、回転後の画像データのアドレスと各ブロックとの関係を示す図であり、（Ｄ）は、回転後の各ブロックの各ライン毎の領域を、回転前のブロック及びラインを基準にして（ＢＮ，ＬＮ）の形式で示した図である。
【図１７】（Ａ）は、ソースブロックバッファ及び待避ブロックバッファを模式的示す図であり、（Ｂ）は、フレームバッファ上の回転前における画像データの格納状態を模式的表す図であり、（Ｃ）は、回転処理前の初期状態の待避先アドレス管理テーブルを示す図である。
【図１８】（Ａ）は、巡回置換の最初の移動操作において、ステップ１４４終了後のソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の最初の移動操作において、ステップ１４４終了後のフレームバッファの画像データ格納状態を模式的に示す図であり、（Ｃ）は、巡回置換の最初の移動操作において、ステップ１４６終了後の待避先アドレス格納テーブルを示す図である。
【図１９】（Ａ）は、巡回置換の最初の移動操作において、ステップ１５４終了後のソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の最初の移動操作において、ステップ１５４終了後のフレームバッファの画像データ格納状態を模式的に示す図であり、（Ｃ）は、巡回置換の最初の移動操作において、ステップ１５６終了後の待避先アドレス格納テーブルを示す図である。
【図２０】（Ａ）は、巡回置換の最初の移動操作が終了したときのソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の最初の移動操作が終了したときのフレームバッファの画像データ格納状態を模式的に示す図である。
【図２１】（Ａ）は、巡回置換の２番目の移動操作において、ステップ１４４終了後のソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の２番目の移動操作において、ステップ１４４終了後のフレームバッファの画像データ格納状態を模式的に示す図であり、（Ｃ）は、巡回置換の２番目の移動操作において、ステップ１４６終了後の待避先アドレス格納テーブルを示す図である。
【図２２】（Ａ）は、巡回置換の２番目の移動操作が終了したときのソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の２番目の移動操作が終了したときのフレームバッファの画像データ格納状態を模式的に示す図である。
【図２３】（Ａ）は、巡回置換の３番目の移動操作において、ステップ１４４終了後のソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の３番目の移動操作において、ステップ１４４終了後のフレームバッファの画像データ格納状態を模式的に示す図であり、（Ｃ）は、巡回置換の３番目の移動操作において、ステップ１４６終了後の待避先アドレス格納テーブルを示す図である。
【図２４】（Ａ）は、巡回置換の３番目の移動操作において、ステップ１５４終了後のソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の３番目の移動操作において、ステップ１５４終了後のフレームバッファの画像データ格納状態を模式的に示す図であり、（Ｃ）は、巡回置換の３番目の移動操作において、ステップ１５６終了後の待避先アドレス格納テーブルを示す図である。
【図２５】（Ａ）は、巡回置換の３番目の移動操作が終了したときのソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の３番目の移動操作が終了したときのフレームバッファの画像データ格納状態を模式的に示す図である。
【図２６】（Ａ）は、巡回置換の４番目の移動操作において、ステップ１４４終了後のソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の４番目の移動操作において、ステップ１４４終了後のフレームバッファの画像データ格納状態を模式的に示す図であり、（Ｃ）は、巡回置換の４番目の移動操作において、ステップ１４６終了後の待避先アドレス格納テーブルを示す図である。
【図２７】（Ａ）は、巡回置換の４番目の移動操作において、ステップ１５４終了後のソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の４番目の移動操作において、ステップ１５４終了後のフレームバッファの画像データ格納状態を模式的に示す図であり、（Ｃ）は、巡回置換の４番目の移動操作において、ステップ１５６終了後の待避先アドレス格納テーブルを示す図である。
【図２８】（Ａ）は、巡回置換の４番目の移動操作が終了したときのソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の４番目の移動操作が終了したときのフレームバッファの画像データ格納状態を模式的に示す図である。
【図２９】（Ａ）は、巡回置換の５番目の移動操作において、ステップ１４４終了後のソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の５番目の移動操作において、ステップ１４４終了後のフレームバッファの画像データ格納状態を模式的に示す図であり、（Ｃ）は、巡回置換の５番目の移動操作において、ステップ１４６終了後の待避先アドレス格納テーブルを示す図である。
【図３０】（Ａ）は、巡回置換の５番目の移動操作が終了したときのソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の５番目の移動操作が終了したときのフレームバッファの画像データ格納状態を模式的に示す図である。
【図３１】（Ａ）は、巡回置換の最後の移動操作において、ステップ１４４終了後のソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の最後の移動操作において、ステップ１４４終了後のフレームバッファの画像データ格納状態を模式的に示す図であり、（Ｃ）は、巡回置換の最後の移動操作において、ステップ１４６終了後の待避先アドレス格納テーブルを示す図である。
【図３２】（Ａ）は、巡回置換の最後の移動操作が終了したときのソースブロックバッファと待避ブロックバッファの画像データ格納状態を模式的に示す図であり、（Ｂ）は、巡回置換の最後の移動操作が終了したときのフレームバッファの画像データ格納状態を模式的に示す図である。
【符号の説明】
【０１３１】
１０  コンピュータ
１２  ＣＰＵ
１４  ＲＡＭ
１６  ＲＯＭ
１８  通信部
２２  接続ポート
２３  記憶媒体
２４  読取装置
２５  記憶媒体
３０  フレームバッファ
３１  ソースブロックバッファ
３２  待避ブロックバッファ
【図１】
2009141659.tif 000007
【図２】
2009141659.tif 000008
【図３】
2009141659.tif 000009
【図４】
2009141659.tif 000010
【図５】
2009141659.tif 000011
【図６】
2009141659.tif 000012
【図７】
2009141659.tif 000013
【図８】
2009141659.tif 000014
【図９】
2009141659.tif 000015
【図１０】
2009141659.tif 000016
【図１１】
2009141659.tif 000017
【図１２】
2009141659.tif 000018
【図１３】
2009141659.tif 000019
【図１４】
2009141659.tif 000020
【図１５】
2009141659.tif 000021
【図１６】
2009141659.tif 000022
【図１７】
2009141659.tif 000023
【図１８】
2009141659.tif 000024
【図１９】
2009141659.tif 000025
【図２０】
2009141659.tif 000026
【図２１】
2009141659.tif 000027
【図２２】
2009141659.tif 000028
【図２３】
2009141659.tif 000029
【図２４】
2009141659.tif 000030
【図２５】
2009141659.tif 000031
【図２６】
2009141659.tif 000032
【図２７】
2009141659.tif 000033
【図２８】
2009141659.tif 000034
【図２９】
2009141659.tif 000035
【図３０】
2009141659.tif 000036
【図３１】
2009141659.tif 000037
【図３２】
2009141659.tif 000038