(57)【特許請求の範囲】
【請求項１】
８ビット×８ラインのイメージデータを９０度回転する画像処理装置であって、
８ラインの上半分の連続するイメージデータを第１のメモリに格納し、８ラインの下半分の連続するイメージデータを第２のメモリに格納する第１処理手段と、
前記第１のメモリに格納されたイメージデータを７ビット以内でＮビットシフトし、８ビット間隔の第１注目ビット以外をマスクしたイメージデータと、前記第２のメモリに格納されたイメージデータをＮとは４ビット差のＭビットシフトし、前記第１注目ビットに対してＭ−Ｎビットずれた位置の第２注目ビット以外をマスクしたイメージデータとの論理和をとったイメージデータを第３のメモリに格納する第２処理手段と、
前記第２処理手段によりマスクされなかったイメージデータを１バイトに加工すべく、前記第３のメモリに格納されたイメージデータと前記第３のメモリに格納されたイメージデータを所定量シフトさせたイメージデータとの論理和をとる第３処理手段と、
前記第２処理手段によるシフト量Ｎ及びＭを順次１ずつを変更した処理と、第３処理手段による処理とを８回実行させる手段と
を有することを特徴とする画像処理装置。
【請求項２】
前記第２処理手段は、前記第１のメモリに格納されたイメージデータをＮビット左シフトし、注目ビット以外をマスクしたイメージデータと、前記第２のメモリに格納されたイメージデータをＭビット右シフトし、注目ビット以外をマスクしたイメージデータとの論理和をとったイメージデータを第３のメモリに格納し、
前記第３処理手段は、前記第３のメモリに格納されたイメージデータと前記第３のメモリに格納されたイメージデータを７ビット右シフトさせたイメージデータとの論理和をとり第３メモリに格納し、前記第３のメモリに格納されたイメージデータと前記第３のメモリに格納されたイメージデータを１４ビット右シフトさせたイメージデータとの論理和をとり第３メモリに格納することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記第３処理手段による処理には、前記第３のメモリに格納されたイメージデータと、前記第３のメモリに格納されたイメージデータを７ビット右シフトさせたイメージデータとの論理和をとり、該論理和結果と、該論理和結果を１４ビット右シフトさせたイメージデータとの論理和をとる処理が含まれることを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記イメージデータに基づきイメージを出力する出力手段を有することを特徴とする請求項１乃至３の何れかに記載の画像処理装置。
【請求項５】
前記出力手段は印刷手段であることを特徴とする請求項４に記載の画像処理装置。
【請求項６】
８ビット×８ラインのイメージデータを９０度回転する画像処理方法であって、
８ラインの上半分の連続するイメージデータを第１のメモリに格納し、８ラインの下半分の連続するイメージデータを第２のメモリに格納する第１処理工程と、
前記第１のメモリに格納されたイメージデータを７ビット以内でＮビットシフトし、８ビット間隔の第１注目ビット以外をマスクしたイメージデータと、前記第２のメモリに格納されたイメージデータをＮとは４ビット差のＭビットシフトし、前記第１注目ビットに対してＭ−Ｎビットずれた位置の第２注目ビット以外をマスクしたイメージデータとの論理和をとったイメージデータを第３のメモリに格納する第２処理工程と、
前記第２処理工程によりマスクされなかったイメージデータを１バイトに加工すべく、前記第３のメモリに格納されたイメージデータと前記第３のメモリに格納されたイメージデータを所定量シフトさせたイメージデータとの論理和をとる第３処理工程と、
前記第２処理工程によるシフト量Ｎ及びＭを順次１ずつを変更した処理と、第３処理工程による処理とを８回実行させる工程と
を有することを特徴とする画像処理方法。
【請求項７】
前記第２処理工程では、前記第１のメモリに格納されたイメージデータをＮビット左シフトし、注目ビット以外をマスクしたイメージデータと、前記第２のメモリに格納されたイメージデータをＭビット右シフトし、注目ビット以外をマスクしたイメージデータとの論理和をとったイメージデータを第３のメモリに格納し、
前記第３処理工程では、前記第３のメモリに格納されたイメージデータと前記第３のメモリに格納されたイメージデータを７ビット右シフトさせたイメージデータとの論理和をとり第３メモリに格納し、前記第３のメモリに格納されたイメージデータと前記第３のメモリに格納されたイメージデータを１４ビット右シフトさせたイメージデータとの論理和をとり第３メモリに格納することを特徴とする請求項６に記載の画像処理方法。
【請求項８】
前記第３処理工程による処理には、前記第３のメモリに格納されたイメージデータと、前記第３のメモリに格納されたイメージデータを７ビット右シフトさせたイメージデータとの論理和をとり、該論理和結果と、該論理和結果を１４ビット右シフトさせたイメージデータとの論理和をとる処理が含まれることを特徴とする請求項６に記載の画像処理方法。
【請求項９】
前記イメージデータに基づきイメージを出力する出力工程を有することを特徴とする請求項６乃至８の何れかに記載の画像処理方法。
【請求項１０】
前記出力工程は印刷工程であることを特徴とする請求項９に記載の画像処理方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は与えられたビットマップの任意の領域の画像に対してプロセッサのソフトウェアにより９０°×ｎ（ｎ＝１，２，３）の回転したビットマップ画像の描画を行なう画像処理方法及びその装置に関するものである。
【０００２】
【従来の技術】
従来、与えられたビットマップの任意の領域の画像に対してプロセッサのソフトウェアにより９０°×ｎ（ｎ＝１，２，３）の回転したビットマップ画像の描画を行なうビットマップ回転方法には次のような方式があった。なお、以下、回転角度は反時計方向への回転角を表わし、ことわりのない限りビット７側が左の画素になるものとする。
【０００３】
図５は従来の９０°回転の主要部分を抜粋である。
【０００４】
回転処理は１バイト×８ライン（８×８画素）の８バイトをブロックを処理単位とする。図において、p_from／p_toは、それぞれ処理するブロックの入出力のポインタであり、添数[n]によりnバイト分バイアスされたアドレスを指し示す。例えばp_from[2]は、p_from[0]よりも２バイト分進んだアドレスを指し示すことになる。row_from／row_toは、それぞれ回転前と回転後の画像の１ラインのバイト数であり、workは回転処理のための作業用変数である。
【０００５】
ステップＳ５１は初期化であり、回転しようとするブロックを指し示すポインタや回転されたブロックを指し示すポインタ等の変数の初期化を行う。
【０００６】
ステップＳ５２は回転処理の本体であり、回転処理した１ブロック（８バイト）のデータを生成する為に、もとになるブロックの８バイトのデータを毎回アクセスして１画素ずつ変数workに移して変数workに回転後のデータを生成し、ポインタp_toのバッファに書き込みを行なう。
【０００７】
ステップＳ５２では処理前ブロック（８行×８列）の各列を処理後ブロックの各行に移し変えている。ステップＳ５２−１では、処理前ブロックの最も右側の列の画素を、処理後ブロックの最も上段の行に移動する。なお、左右上下といった言葉は、８画素×８画素のブロックを視覚的に考えた場合の対応する位置を示している。この際の移動のしかたは、処理前ブロックの最右列の上端の画素を処理後ブロックの最上行の左端に移動し、順次処理前ブロックにおける直前に処理された画素の下の画素を、処理後ブロックにおける直前に処理された画素の右側に配置するように行う。同様にステップＳ５２−２では処理前ブロックの右側から２番目の列を処理後ブロックの２番目の行に移動する。このようにして１つのブロックについて９０°回転を行う。
【０００８】
ステップＳ５２が終わるとステップＳ５１に戻って次のブロックを処理する。
【０００９】
図６に１８０度回転の従来例を示す。図６（ａ）は２５６バイトのルックアップテーブル（ＬＵＴ）を用いた場合であり、図６（ｂ）は９０度回転の従来例と同じ様に１画素単位にコピー／ペーストを繰り返すものである。ＬＵＴを用いた例では、処理前ブロックを行すなわち１バイト単位でＬＵＴ"table"で変換し、それを変換後のブロックとしている。ＬＵＴ"table"は、先頭からのバイト単位のオフセット値を、２進数として１８０°回転させた値を内容として有する。例えば"table"の０ｘ０５バイト目は、それを１８０度回転した値０ｘＡ０となる。このため、ステップＳ６０２においては、ポインタp_toの指し示す処理後ブロックに、ポインタp_fromにより指し示されるバイトを１８０度回転した値が与えられる。１行処理後とにポインタp_fromを１行分進め、ポインタp_toを１行分戻して８行分処理すれば１ブロックの回転がおわる。
【００１０】
また、図６（ｂ）では、ステップＳ６１２において、処理前ブロックの１行（１バイト）を左右反転、すなわち１８０度回転させる。これを回転前ブロックの各行について上段から順次行い、それを回転後ブロックの下段から組み入れれば１８０度回転したブロックが得られる。
【００１１】
ちなみに９０度回転の場合もＬＵＴを用いて処理することも考えられる。
【００１２】
【発明が解決しようとする課題】
しかしながら従来の方式では１ビット単位で処理するため遅く、またビット単位の処理を行うためには対象のビットを含む処理単位、例えばバイト単位でデータをアクセスする必要がある。そのため回転したデータ１バイト生成するために毎回８バイトのデータアクセスを行なうために更に低速になる。それはデータキャッシュを持たないシステムでは更に顕著になる。そして１６bitプロセッサでは１６bit演算、３２bitプロセッサでは３２bit演算ができるにもかかわらず実際に演算に使用されている部分は８bit（１BYTE）の箇所だけであり無駄が多い。
【００１３】
ＬＵＴを用いた場合ではデータのアクセス回数が増えるため高速に処理するためにはデータキャッシュがあるのが望ましい。またＬＵＴを用いて更に高速にするためにテーブルサイズを大きくして例えば１バイト単位で変換するのではなく２バイト単位で変換する様にＬＵＴのアクセス回数を減らした場合、１バイト単位のテーブルの５１２倍となってしまうテーブルサイズの増加量に比べてＬＵＴのアクセス回数が１／２にしかならず極めて非効率である。逆にデータキャッシュを持つシステムではキャッシュヒット率が低下して遅くなることが考えられる。
【００１４】
本発明は上記従来例に鑑みてなされたもので、
・複数バイトにまたがる分割されたブロックのデータを多バイト長の変数にまとめて格納して処理することにより一回の演算で複数の画素を処理することが可能となり全体の演算回数を減らすことができる画像処理方法及びその装置、あるいは、
・回転のための画素の組み替えを小部分から段階的に行なうことにより演算回数を減らすことができる画像処理方法及びその装置、あるいは、
・ブロックの処理順番を回転処理をする元の画像のアドレスが連続する順番で行なうことによりデータキャッシュの容量に対してキャッシュヒット率が高くなり速度が向上させることができる画像処理方法及びその装置を提供することを目的とする。
【００１５】
【課題を解決するための手段】
上記目的を達成するために本発明の画像処理方法は次のような構成からなる。即ち、８ビット×８ラインのイメージデータを９０度回転する画像処理装置であって、８ラインの上半分の連続するイメージデータを第１のメモリに格納し、８ラインの下半分の連続するイメージデータを第２のメモリに格納する第１処理手段と、前記第１のメモリに格納されたイメージデータを７ビット以内でＮビットシフトし、８ビット間隔の第１注目ビット以外をマスクしたイメージデータと、前記第２のメモリに格納されたイメージデータをＮとは４ビット差のＭビットシフトし、前記第１注目ビットに対してＭ−Ｎビットずれた位置の第２注目ビット以外をマスクしたイメージデータとの論理和をとったイメージデータを第３のメモリに格納する第２処理手段と、前記第２処理手段によりマスクされなかったイメージデータを１バイトに加工すべく、前記第３のメモリに格納されたイメージデータと前記第３のメモリに格納されたイメージデータを所定量シフトさせたイメージデータとの論理和をとる第３処理手段と、前記第２処理手段によるシフト量Ｎ及びＭを順次１ずつを変更した処理と、第３処理手段による処理とを８回実行させる手段とを有する。
【００１７】
【第１実施例】
図１４は、本発明の実施例である画像の回転処理を実現するためのシステムの構成図である。図１４において、ＣＰＵ１は、メモリに格納されたプログラムを実行することでシステム全体を制御して画像の回転処理等の処理を行う。ＲＯＭ２は、ＣＰＵ１の制御プログラム（後述するフローチャートに係るプログラムも含む）やデータを格納する。ＲＡＭ３は、ＣＰＵ１の作業用データや回転する画像と回転後の画像を格納する。スキャナ４は画像を入力する。ディスプレイ５は画像を表示する。記憶デバイス６は磁気ディスク装置等で構成され、画像やプログラム、その他のデータを格納する。プリンタ７は画像などの印刷出力を行う。入出力インターフェース（Ｉ／Ｆ）８は外部機器と接続して入出力を行う。これらのブロックのうち、後述する画像回転を行うものとして次のようなものがある。
【００１８】
＜プリンタ＞
まず、入出力インターフェース８などから入力されたページ記述言語のデータをＲＡＭ３に格納する。ＣＰＵ１はそれを解釈しながらＲＡＭ３に描画し、描画されたビットマップデータをプリンタ７に送り紙に印刷する。プリンタ７においては、ビットマップデータを回転させたり、ビットマップフォントを回転させたり、あるいはＡ３プリンタでＡ４の出力を行う場合などに画像の回転処理を行う。
【００１９】
＜ファイリング装置＞
図１４では、記憶デバイス６がファイリング装置に該当することになる。スキャナ４で読み込まれた原稿画像を格納してその文字認識を行うインテリジェントファイリング装置の場合、原稿の向きが正しくない場合には原稿画像を回転させる必要がある。
【００２０】
＜ＣＰＵ＞
スキャナ４や記憶デバイス６から読み込んだ画像をＲＡＭ３に格納し、回転処理してディスプレイ５に表示などを行う。
【００２１】
このように、必要に応じて画像の回転処理が行われる。この回転処理は次のような手順で実現される。
【００２２】
＜回転処理の手順＞
図１は本発明による画像の回転処理を最もよく表した図である。
【００２３】
本実施例における処理は１バイト×８ライン（８×８画素）のブロックを処理単位とする。変数p_from／p_toはそれぞれ処理するブロックの入出力のポインタである。変数row_from／row_toはそれぞれ回転前と回転後の画像の１ラインのバイト数である。例えばp_fromがあるブロックの最上行を指しているとすれば、そのブロックの次の行は、その上の行のアドレスに画像の１ライン分のサイズrow_fromを加えたアドレスとなる。変数work／tmp1／tmp2は回転処理のための作業用変数である。ここでuint32は４バイト長整数であらかじめ定義されているものとする。
【００２４】
図において、ステップＳ１１は初期化であり、処理するブロックの読み出しと書き込みのポインタ等の変数の初期化を行なう。すなわち、変数p_fromには回転前ブロックのアドレスを、変数p_toには回転後ブロックのアドレスを格納する。
【００２５】
ステップＳ１２は処理するブロックの全データを読み出して１バイト長よりも大きな変数にまとめて格納するパッキング処理である。図２（ａ）のように１バイト×８ラインの各ラインのバイトデータを、上４行とした４行とに分けてそれぞれtmp1とtmp2の変数に順次格納する。
【００２６】
ステップＳ１３はその変数tmp1とtmp2とから回転後のデータを順次生成して書き込みを行なう処理である。
【００２７】
図３はステップＳ１３の主要部分であるbitcombine()マクロの処理概要を表したものである。
【００２８】
ステップＳ１２により、変数tmp1とtmp2に１バイト×８ライン（第７〜０ライン）の画素データが４バイトずつパッキングされて格納されている。ステップＳ１３では、この第７ラインから第０ラインのバイトデータの各ＬＳＢ（最下位桁）の画素データを取り出して回転処理した１バイトデータを取り出す。９０度回転した状態では、このＬＳＢが番号順にならんで１行を形成することになる。なお、説明の便宜上、各バイトのＬＳＢにはラインの番号と一致した値を書き込んである。また、疑問符はその値を問わないことを示す。
【００２９】
まず操作１は、状態１に示された変数tmp1とtmp2とからＬＳＢ７からＬＳＢ０の各画素データを取り出して変数workに格納する論理操作である。この操作では、tmp1の内容を４ビット左シフトし、その値と１６進数のマスクデータmask2=0x10101010との論理積をとる。これにより、変数tmp1に格納された値が４ビット左シフトされ、元の４ビットのＬＳＢ７，６，５，４以外は０となっている。また、変数tmep2の内容と１６進数のマスクデータmask1=0x01010101との論理積をとる。このため、tmp2の内容はＬＳＢ以外のビットはすべて０になっている。このようにシフト及びマスクされたtmp1と、マスクされたtmp2との論理和を計算して変数workに得られるのが状態２に示した値である。この操作においてビット７とビット３との位置関係、６と２との位置関係、５と１との位置関係、４と０との位置関係が回転後の位置関係と同じく配置された状態になる。
【００３０】
次に操作２によって、状態２として示された変数workの値と、それを７ビット右シフトした値との論理和を計算する。その結果、変数workは状態３のように再配置され、このうちＬＳＢ７と６と３と２の位置関係と、ＬＳＢ５と４と１と０の位置関係が、回転後の位置関係の通りに配置される。
【００３１】
最後に操作３によって、状態３として示された変数workの値と、それを１４ビット右シフトした値との論理和を計算する。その結果、変数workは状態４のように再配置され、変数workの最下位８ビットに回転後の第１行目の画素データが得られる。
【００３２】
以上の操作で回転前ブロックの最右列を回転後ブロックの最上行におきかえることができる。１ブロックについて行うには、上記説明におけるＬＳＢを１画素ずつ上位桁に移しつつ、同様の操作を行う。画素を移すには、上記操作１における変数tmp1およびtmp2に対するシフト量を減らしていき、対象となる桁が状態２のビット０〜７のようになるようシフト操作すれば良い。こうして得られた状態４の下位１バイトが９０度回転された行となる。
【００３３】
なお、図１のフローチャートをより説明的に示す図が図１５及び図１６である。図１５において、ステップＳ１５１はステップＳ１１に相当し、図２（ａ）の処理を行う。ステップＳ１５２〜Ｓ１５５はステップＳ１３に相当する処理である。ステップＳ１３では各列に対してそれぞれ論理操作を行うように記述しているが、図１５では列の番号をｎとして一般化してるため、ループ処理が加わっている。図１６はステップＳ１５３を詳細に説明するもので、図１でいうところのマクロbitcombine()における処理、すなわち図３に説明された手順を、図３に即して記述したものである。
【００３４】
図１６では、まずパックされた３２ビットのtmp1を、（４−ｎ）ビット左シフトしてその第４，１２，２０，２８ビットを残してすべて０とする。ここでｎは回転しようとする列（桁）を示す。また、ｎ−４が負となった場合は、シフトの方向を反転する。次にステップＳ１６２において、tmp2をｎビット右シフトして、第０，８，１６，２４ビットを残して０とする。ステップＳ１６３ではステップＳ１６１とＳ１６２とで得られた結果の論理和を計算する。ここまでが図３の操作１である。
【００３５】
ステップＳ１６４乃至Ｓ１６６は、それぞれ操作２，３として説明したままの内容である。
【００３６】
このように、ブロックの各ラインをラインごとに扱わず、連続するデータに置き換えてから論理操作を行うことで、画素の組み替えが１回の操作によって１箇所ずつではなく複数の箇所で並列的に処理されるため高速になるのである。
【００３７】
さらに詳しく説明すると、例えば変数tmp1とtmp2にそれぞれ４バイトをパッキングして格納する事によって１バイト×８ラインのデータから必要画素をマスクして取り出すにしても、１回の論理演算（ＡＮＤ演算）によって複数画素（例では４画素）を取り出せる。また変数tmp1とtmp2のデータのパッキング方法も回転後のビットの並びに合わせてあるため、操作２，３に示すような段階的な画素の組み替えができるのである。
【００３８】
変数tmp1とtmp2であるが、図３のようにビット０の場合だけではなく、各桁の回転データを取り出すときにも再利用できるため、この値を保存しておけば、以後、画像データをアクセスすることなしに残りの７バイト（ライン）の回転データを生成できる。このため、データキャッシュを持たないシステムで実行したとしてもレジスタ変数にtmp1とtmp2とを割り付ければ、メモリアクセスなしに回転データを生成できるため非常に高速である。また複数の画像データをパッキングすることにより変数の数が削減でき、レジスタ変数への割り付けが容易であるという効果もある。また、レジスタ変数への割り付けができなくても、データアクセスの回数が１／４（１バイト単位のアクセスが４バイト単位のアクセスとなるため８回が２回となる）になるのでやはり高速である。
【００３９】
詳細に計算すると１バイト×８ラインの１ブロックを回転処理するため、パッキングのための各バイトデータのリードアクセスが各１回、パッキングされたデータから回転後の１バイトデータを生成するための演算回数が各８または９回、生成された回転データのライトアクセスが各１回となる。ちなみに図３の例でいうと操作１が４演算、操作２と３がそれぞれ２演算である。即ち、画像データのアクセス回数が最小限に押さえられ、かつ回転処理が１画素あたり１演算強ですむのである。
【００４０】
ステップＳ１３が終了するとステップＳ１１に戻って次のブロックを処理するのであるが、次のブロックは処理した前のブロックに隣接した左右のブロックか上下のブロックになると考えられる。図４（ａ）のように１バイト×８ラインのブロックａからブロックｙの２５ブロックを１から２５の順に処理した場合と図４（ｂ）の様な順番でブロックａ〜ｙを１から２５の順に処理した場合を考える。データキャッシュを利用する場合、データキャッシュの性質として、１バイトの読み出しであってもデータバスが３２ビットのプロセッサであれば少なくともその１バイトを含む３２ビットデータバス上の４バイトをキャッシュメモリ内に取り込む。そのため例えばブロックｍの中の１バイトを読み込んだ場合には、ブロックｌとブロックｎのデータがキャッシュメモリ内に取り込まれるのである。ブロックａのデータキャッシュの効果が現れるのはブロックｂを処理するときであるため、図４（ａ）のようにブロックａ，ｆ，ｋ，ｐ，ｕ，ｂ…の順番でブロックを処理した場合、間のブロックｆ，ｋ，ｐ，ｕの処理のときにデータキャッシュの内容が更新されてブロックｂの処理の時にはミスヒットする確率が高くなる。そのため図４（ｂ）のような順番で処理したほうがデータキャッシュのヒット率が高い。つまり小容量のデータキャッシュでも効果を発揮するのである。従って図４（ｃ）に示す様にブロックの構成が左上のブロック４１に図示するライン構成であれば、斜線部のブロックを処理した後は左右のどちらかのブロック（丸印の方向）を処理することが望ましい。ブロックの処理順番を回転処理をする元の画像のアドレスが連続する順番で行なうのである。
【００４１】
図１で示したのは１バイト×８ラインの１ブロックのデータが全て揃っている場合であるが、画像の端のようにデータが揃わない場合は以下のようにすればよい。
【００４２】
まず８ラインのデータが揃わない場合はステップＳ１２（あるいはステップＳ１５１）において変数tmp1とtmp2の欠落に該当する部分を空白で処理を行う。また、１バイト中の８画素が足りない場合は、ステップＳ１３において８つのbitcombine（）マクロがあるが欠落部分に該当するbitcombine（）マクロを実行しないように制御すればよい。これはステップＳ１５３において、欠落したｎに対しては処理を実行しないことをに相当する。
［上記実施例のバリエーション］
上記実施例のマクロbitcobine()、すなわち図１６に示した処理手順を以下の様に変更しても同じ結果が得られる。
【００４３】
ステップＳ１６１において３２ビット変数tmp1をシフトした後の第４，１２，２０，２８ビット以外のビットを０にしているが、０ではなく１にする。また、同様にステップＳ１６２において第０，８，１６，２４ビット以外のビットを０にしているがこれも１にする。さらに、ステップＳ１６３では論理和を計算するが、論理積を計算する。この操作の結果、図３の状態２のブランクの桁は、０ではなく１で充填されることになる。後のステップは図１６と同様である。
【００４４】
これを図１の上段のbitcombine()と同様に表記すると次の様になる。
mask1=0xfefefefe;
mask2=0xefefefef;
#definebitcombine(pat1,pat2)\
work=((pat1)|mask2)&((pat2)|mask1);\
work&=work>>14;\
work&=work>>7;
この例では、１ブロックのライン数が８にみたない場合に、足りない部分の画素が１となる。これは黒画素の意味が０の場合と１の場合があるため、余白部分を白又は黒にしたい場合、この例と図１の例とを使い分けると良い。
【００４５】
【第２実施例】
［１８０度回転］
図７は本発明に係る画像処理装置を、画像の１８０度回転に適用した例である。
【００４６】
変数p_from／p_toは処理するブロックの入出力のポインタである。変数row_from／row_toは回転前と回転後の横方向バイト数であり、workは回転処理のための作業用変数である。変数rem1は端処理のための値で画像の端が１バイトの境界にあわなかった場合のシフト量を格納しておく。rem2は（３２−rem1）の固定値である。
【００４７】
ステップＳ７１は初期化であり、処理するブロックの読み出しと書き込みのポインタ等の変数の初期化を行なう。処理は４バイト×１ラインを単位とする。
【００４８】
ステップＳ７２は処理するブロックの全データを読み出して１バイト長よりも大きい変数にまとめて格納するパッキング処理である。パッキングされたデータは変数workに格納される。変数rem1が０でない場合はステップＳ７２の「work＝（work＞＞rem1）｜（（unit32）p_from[0]＜＜rem2）；」の処理を行って端を合わせる処理をする。この式の意味するところは、変数workの内容を桁合わせすべき桁数rem1分右シフトした値と、ポインタp_from[0]の指し示す値を３２ビット化してrem2桁分だけ左シフトした値との論理和を計算するということである。ちなみに同様の処理は従来例の処理でも必要であるが説明を簡単にするため省略した。なお、ここで行うべき右シフト演算は論理シフト演算であり、シフトされて空いた桁には０が充填されるシフト演算である。
【００４９】
ステップＳ７３はその変数から回転後のデータを順次生成して書き込みを行う処理である。ステップＳ７３が終わるとステップＳ７１に戻って次のブロックを処理する。
【００５０】
図８はこの図７のステップＳ７３のbitcombine()マクロを説明するための図である。説明を簡単にするために１バイトデータのビット回転で説明する。まず変数workには状態１のように７から０のビットデータが並んでいる。操作１によって変数workの７と６、５と４、３と２、１と０の各画素データが交換されて変数workは状態２となる。次に操作２によって変数workの内容が再配置されこのうち６−７と４−５，２−３と０−１の画素データが交換され変数workは状態３となる。最後に操作３によって変数workの内容が再配置されこのうち４−７，０−３の画素データが交換され変数workは状態４となり回転処理は終了する。即ち、段階的に画素の組み替えが１回の操作によって複数の箇所を処理するようになるため高速になるのである。ちなみに操作１から３の順番はどのようにしても結果は同じくなる。回転処理の対象となる変数workは４バイトの変数であり、ステップＳ７２によりブロックの上半分又は下半分の４バイトが変数workにパックされているため、ステップＳ７３の処理では図８に示した操作が変数work内の４バイトに対して同時に施される。
【００５１】
この処理時間を詳しく計算すると操作１から３はそれぞれ５演算で１５演算となる。従来例の図６（ｂ）では２１演算であるためこれだけでも高速であるが、更に変数workには４バイト分格納されていて同時に処理が行えるため更に高速となる。１ビットあたりの演算数は１５／３２で約０．５演算となる。加えてこのアルゴリズムはＬＵＴのように余分なデータアクセスをしないためデータキャッシュを持たないシステムで実行しても速度低下が小さい。図８からもわかるように１８０度回転では複数バイトのデータをパッキングしなくても画素の組み替えを小部分から段階的に行えるため必ずしもパッキングが必要というわけではない。
【００５２】
図７で示したのは４バイト×１ラインの１ブロックのデータが全て揃っている場合であるが、画像の端のようにデータが揃わない時は以下のようにすればよい。まず４バイトのデータが揃わない場合はステップＳ７２において変数workの欠落に該当する部分を空白で処理を行なう。次にステップＳ７３においてbitcombine（）マクロにおいて同じように処理し、データの有効部分のみの書き込みを行なうように制御すればよい。
【００５３】
図１７は図７の処理をより説明的に示したものであり、図１８は図７におけるマクロbitcombineを説明するものである。
【００５４】
図１７において、まず、回転しようとするブロックの上半分４バイトを変数workにパックする（Ｓ１７１）。これが半端なブロックであれば、半端な部分を空白で充填処理する（Ｓ１７３）。次にブロック内の第ｎライン目を上位桁と下位桁とを逆順にする（Ｓ１７５）。これは図１８に示したもので、図８の処理そのものである。このステップＳ１７５の処理を変数workにパックされた４ラインについて行い、上４ラインが終了したならした４ラインについても同様に処理をステップＳ１７１からくり返し行って（Ｓ１７９）、１ブロックの１８０度回転が終了する。
【００５５】
図１８においては、まずステップＳ１８１でパックされた４バイトの内、互いに隣り合う奇数桁と偶数桁とを入れ替え（操作１）、次にステップＳ１８２で入れ替えられた２ビットを組として、更に隣接する奇数番目の組と偶数番目の組とを入れ替える（操作２）。ステップＳ１８３では同様にステップＳ１８２で入れ替えられた２ビットずつを組とする４ビットを組にして、互いに隣接する奇数番目の組と偶数番目の組とを入れ替える（操作３）。これでパックされた４バイトについて、上位桁と下位桁の入れ替えが完了する。この、回転前ブロックにおける第ｎ番目のラインを、回転後ブロックにおける（７−ｎ）ラインとして格納すれば、１ラインのの回転が完了する。
【００５６】
【第３実施例】
［ビット０が左の場合の９０度回転］
第１の実施例ではビット７が左の画素となる場合の９０度回転を示したがビット０が左の場合の例を図９に示す。動作は実施例１とほぼ同じ処理であるが、ステップＳ９２における処理では、図２（ｂ）に示すようにデータのパッキング方法が逆になり、また、図１のステップＳ１３においてbitcombine()マクロにより列→行に変換されたラインの順番が逆になるだけである。すなわち、図１の処理においてはＬＳＢが右端の桁であるためそれが第１ラインになるように回転したが、図９においては左端桁がＬＳＢとなるため、それが第１ラインとなるように図３とは逆に左端の桁からまず取り出してラインを形成し、それを第１ラインとする。
【００５７】
このようにすることで、ビット０が左端であっても同様に９０度回転処理ができる。
【００５８】
【第４実施例】
［２７０度回転］
ビット７が左画素となる場合が図９と同じで、ビット０が左画素となる場合は図１と同じくなる。９０度回転と異なる点はステップＳ１１またはステップＳ９１のポインタの初期化で処理するブロックの順番だけである。これは、図１の処理と図９の処理とでは、ビットの並びだけを考えた場合には反対向きの回転となっていることからも明らかである。
【００５９】
［６４ｂｉｔ演算での高速化した例］
実施例１では３２ビット演算を使用した場合であるが６４ビット演算を行えるプロセッサを使用した場合の例を図１０に示す。ここでuint６４は８バイト長整数であらかじめ定義されているものとする。
【００６０】
この処理は、本質的には図３あるいは図１５、図１６で説明した処理と変わるものではないが、６４桁を並列に処理できるため、図３におけるtmp1とtmp2とを１つの変数workにまとめることができる、という点を利用したものである。すなわち、図３の状態１ではブロックの上４バイトとした４バイトを２つの４バイト変数に分けてパッキングしたが、図１０のステップＳ１０２ではこれをまとめて１ブロック分８バイトをパッキングする。すなわち、図１０ではtmp1,tmp2は連続する変数workに相当するため、変数workを３２桁（４バイト分）右シフトした値が変数tmp1に相当する。従って、図３の操作１は、変数workの上位３２ビットを４桁シフトして下位３２ビットと論理和をとることに相当する（対象外の桁にはマスクする処理も含まれる）。
【００６１】
このように、実施例１ではbitcombine（）マクロでの演算数が８または９であったが、この実施例の図１０では、図３の操作１の処理がシフトと論理和の計算できとなるため、更に演算数が減って７または８となる。
【００６２】
このように、従来例のアルゴリズムではプロセッサの並行処理する桁数に関らず８ビット単位での処理を行うため、プロセッサが進化しても高速化の余地はないが、本発明ではプロセッサが進化すればそれに合わせてさらに高速化が行える。
【００６３】
またこの実施例では、実施例１の変数tmp1，tmp2，mask1，mask2が変数tmp，maskに削減される利点が有る。ところでこの図１０のbitcombine（）マクロの「「work|=work＞＞28;work｜=14;work|=work＞＞7;」の部分は図１とは順番が逆であるが処理結果は同じになる。すなわち、この「」内の処理は図３で説明した桁をシフトして重ねあわせるという操作１〜操作３に相当するが、これら操作は逆の順序で処理しても得られる結果は同じであるということである。
【００６４】
【第５実施例】
［多値画像回転］
図１１に１画素２ビットの場合の９０度回転の処理方法を示す。１バイト×４ラインを１ブロックとして処理するのであるが、これは第１の実施例として示した回転処理を、２ビットを１まとまりとして行うものである。すなわち、ステップ１１２では４ライン３２バイトを１つの変数tmpにパッキングする。図１９は図１１のステップＳ１１３における、回転後の第１ライン目を形成する１ラインの回転処理の模式図である。ステップＳ１１２により変数tmpは図１９の状態１のようにパッキングされた状態になる。この後、６桁右シフトして、各バイトの右端２桁以外を０でマスクする（操作１）。ここで６桁シフトするのは上位２ビットを処理の対象としているためで、最下位２ビットならシフトする必要はないし、その上の２ビットならば２桁右シフトするし、更にその上の２ビットならば４桁右シフトすれば良い。こうして状態２となったデータが得られる。この状態は何番目のラインであろうとも同一である。
【００６５】
次に、状態２のデータを右に６桁シフトし、状態２のデータとの論理和を計算して（操作２）、状態３のデータを得る。。更に、状態３のデータを１２桁右シフトして状態３のデータとの論理和を計算し（操作３）、状態４のデータを得る。この最下位１バイトが回転後の１ラインとなる。
【００６６】
以上の操作を４ライン全てについて行い、得られたラインを処理前の桁に応じたラインとして格納すれば、９０度回転した画像データが得られる。図１９では、上位桁が上位ラインとなり、下位桁が下位ラインとなるように回転している。このように、基本的には第１実施例と同じ要領であるが、捜査対象の桁数が１ビットではなく、２ビットである点において異なる。
【００６７】
以上のように本発明は多値画像でも適用できる。
【００６８】
【第６実施例】
［複数ライン処理］
図１２に１画素２ビットの場合の９０度回転の処理方法を示す。図１と同じの変数tmp1,tmp2を使って、ステップＳ１２２では「tmp1｜＝tmp1＜＜１４；tmp2｜＝tmp2＜＜１４；」の処理によりステップＳ１２３において同じ演算を繰り返すのを防いでいる。その結果bitcombine（）マクロにおいて変数workには回転後のデータが２ライン分生成される。
【００６９】
図２０はその様子を示す図である。まず、ステップＳＳ１２２において、状態１のように、回転前ブロックの第１ライン目（記号ａで示す）と第２ライン目（記号ｂ）とが、変数tmp2にセットされる。すなわち、tmp１の下位１６バイトに第２ラインと第１ラインを順に格納し（その他の桁は０にしておく）、その値と、それを１４ビット左シフトした値との論理和を変数tmp2に格納する。変数tmp1も同様にして第３ラインと第４ラインとを格納する。
【００７０】
これら状態１の変数にたいし、まずtmp2の値を４桁右シフトして各バイトの下２ビット以外を０とし、tmp1の値を各バイトの上から３ビット目と４ビット目以外を０とする（操作１）。なお、変数tmp1,tmp2の値はこの後の処理のために変えないようにしておくことが望ましい。
【００７１】
こうして得られる状態２の値に対して、両者の論理和を計算して（操作２）、状態４の値を得、状態３の値と、その値を６桁右シフトした値との論理和を計算すると（操作３）、状態４の値が得られる。
【００７２】
状態４では、回転前のブロックを２ビットずつ９０度回転した後のラインが２つ得られている。即ち、第１ラインが第２バイト目として、第２ラインが第４バイト目として得られる。
【００７３】
以上の操作を、回転後の第３、第４ラインに対しても行う。そのためには、状態２としてあたえる２つの値として、それぞれ図２０よりも４桁ずつ左にずらし、図２０に示したようにビット７，６あるいはビット５，４に代えて、ビット３，２あるいはビット１，０をそれぞれ置き換えれば良い。この結果、操作２，操作３で回転後の第３、第４ラインが得られる。
【００７４】
【第７実施例】
［複数ブロック処理］
図１３に１画素４ビットの場合の９０度回転の処理方法を示す。実施例１に従うと１画素が４ビットの場合は１バイト×２ラインがブロックになるが、このままであると３２ビットの変数にパッキングすると２バイト分が空白となり演算の１／２は無駄になる。そこで２ブロック分の２バイト×２ラインを変数tmpにパッキングして処理を行なう。このパッキングを行うのがステップＳ１３２である。ここでは、２ブロック目の第１ライン、２ブロック目の第２ライン、１ブロック目の第１ライン、１ブロック目の第２ラインの順で４バイト変数tmpにパッキングする。
【００７５】
図２１はこの様子を示している。まず、４ビット１画素の２つのブロックＡ，Ｂについて、各画素ａ１−ａ４，ｂ１−ｂ４を図２１のように考える。これをステップＳ１３２で状態１のようにパッキングする。これを操作１により３２ビットの変数tmpに下位から１画素（４ビット）ずつ格納する。同じくworkにtmpに格納しなかった画素を４桁右シフトして格納する。この結果状態２のようになる。こうして得られたtmpの値と、その値を４桁右シフトした値との論理和を計算し、変数tmpに格納する（操作３）。変数workについても同じ操作を行う。こうして得られた状態３の両変数を、順にworkの第２バイト、tempの第２バイト、workの第４バイト、tmpの第４バイトを回転後の２つのブロックとして格納すれば、ブロックＡとＢとをまとめて９０度回転した画像をえることができる。
【００７６】
これによりトータルの演算回数とループ回数が減るため高速に処理が行える。またパッキングするための変数を複数用意すればさらにループ回数が削減される。
【００７７】
さらに６４ビット演算が可能であるプロセッサを使用するのであればそれだけで処理できるブロック数が倍になる。例えば１画素４ビットの場合だけではなく図１１のような１画素２ビットの場合でも２ブロックを同時に処理するように変更することは容易である。
【００７８】
尚、本発明は、複数の機器から構成されるシステムに適用しても、１つの機器から成る装置に適用しても良い。また、本発明はシステム或は装置にプログラムを供給することによって達成される場合にも適用できることはいうまでもない。
【００７９】
【発明の効果】
以上説明したように、本発明に係る画像処理方法及びその装置によれば、
・複数バイトにまたがるビットマップ上のデータを多バイト長の変数にまとめて格納することにより複数バイトを同時に処理することが可能となり演算回数を減らすことができる。よって複数画素を同時に処理することが可能となるため１画素あたりの演算回数が削減され処理時間を短縮できる。
【００８０】
・従来例では実行するプロセッサを３２ビットから６４ビットに変更しても動作周波数やキャッシュ内容や内部アーキテクチャの向上などの変更がない限り高速にはならない。しかし本発明では演算のビット幅が増えるだけでそれを積極的に利用して高速化がはかれる。そのため従来例との差はさらに大きくすることができる。
【００８１】
・データアクセス回数が少ないのでデータキャッシュが少ないシステムで速度低下が小さい。同様の理由により、データキャッシュを持たないシステムでも速度低下が小さい。
【００８２】
・ブロックの処理順番を回転処理をする元の画像のアドレスが連続する順番で行なうことによりデータキャッシュの容量に対してキャッシュヒット率が高くなり速度が向上する。
【００８３】
・複数のバイトにまたがる画像データを多バイト長の変数にまとめて格納することにより分けて格納するよりも変数のすうを削減でき、それによりコンパイラがその変数をレジスタ変数に割り振ることが容易になるという効果がある。
【００８４】
【図面の簡単な説明】
【図１】本発明の第１の実施例である９０度回転の処理の手順を示す図である。
【図２】第１実施例によるデータパッキングの図である。
【図３】第１実施例の９０度回転処理の手順を示す図である。
【図４】第１実施例のブロック処理の順序を示す図である。
【図５】ブロックの９０度回転の従来例の手順を示す図である。
【図６】ブロックの１８０度回転の従来例の手順を示す図である。
【図７】第２実施例のブロックの１８０度回転の手順を示す図である。
【図８】第２実施例の１８０度回転を説明する図である。
【図９】第４実施例の２７０度回転の手順を示す図である。
【図１０】第１実施例の処理を６４ビットプロセッサで行う場合の処理の手順を示す図である。
【図１１】第５実施例による１画素が２ビットの場合のブロックを９０度回転する処理手順を示す図である。
【図１２】第６実施例による複数ラインを同時処理する場合の処理手順を示す図である。
【図１３】第７実施例による、複数ブロックを同時に処理場合の処理手順を示す図である。
【図１４】実施例の画像処理を行うシステムの構成図である。
【図１５】本発明の第１の実施例である９０度回転の処理の手順を示す図である。
【図１６】本発明の第１の実施例である９０度回転の処理の手順を示す図である。
【図１７】本発明の第２の実施例である１８０度回転の処理の手順を示す図である。
【図１８】本発明の第２の実施例である１８０度回転の処理の手順を示す図である。
【図１９】第５実施例による１画素が２ビットの場合のブロックを９０度回転する様子を示す図である。
【図２０】第５実施例による１画素が２ビットの場合のブロックを９０度回転するもうひとつの様子を示す図である。
【図２１】第７実施例による、複数ブロックを同時に処理する場合のブロックの様子を示す図である。
【図１】
0003706656.tif 000002
【図２】
0003706656.tif 000003
【図３】
0003706656.tif 000004
【図４】
0003706656.tif 000005
【図５】
0003706656.tif 000006
【図６】
0003706656.tif 000007
【図７】
0003706656.tif 000008
【図８】
0003706656.tif 000009
【図９】
0003706656.tif 000010
【図１０】
0003706656.tif 000011
【図１１】
0003706656.tif 000012
【図１２】
0003706656.tif 000013
【図１３】
0003706656.tif 000014
【図１４】
0003706656.tif 000015
【図１５】
0003706656.tif 000016
【図１６】
0003706656.tif 000017
【図１７】
0003706656.tif 000018
【図１８】
0003706656.tif 000019
【図１９】
0003706656.tif 000020
【図２０】
0003706656.tif 000021
【図２１】
0003706656.tif 000022