JPH0426149B2 - - Google Patents
Info
- Publication number
- JPH0426149B2 JPH0426149B2 JP59192755A JP19275584A JPH0426149B2 JP H0426149 B2 JPH0426149 B2 JP H0426149B2 JP 59192755 A JP59192755 A JP 59192755A JP 19275584 A JP19275584 A JP 19275584A JP H0426149 B2 JPH0426149 B2 JP H0426149B2
- Authority
- JP
- Japan
- Prior art keywords
- image
- bits
- bytes
- rotation
- buffer
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T3/00—Geometric image transformations in the plane of the image
- G06T3/60—Rotation of whole images or parts thereof
- G06T3/602—Rotation of whole images or parts thereof by block rotation, e.g. by recursive reversal or rotation
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Image Processing (AREA)
- Editing Of Facsimile Originals (AREA)
Description
〔産業上の利用分野〕
本発明はデイジタル・イメージ処理方法、特に
イメージ回転に関する。 〔従来技術〕 代表的な従来技術を下記に示す。 (a) 米国特許第3976872号で開示された機能の中
にイメージを90度回転する方法がある。しかし
ながら、この特許では、本発明のように、イメ
ージのビツト・グループを検査し、ビツト・グ
ループがすべて同じ値であるかどうかを判断す
る動作を含む、イメージを90度回転する方法が
示されてはいない。 (b) 米国特許第3968475号は、イメージを分割し
て、２進データ・アレイの空間を含むサンプ
ル・アレイの領域の各々に挿入することによ
り、２進イメージからデータを取出すデイジタ
ル・プロセツサを開示している。この特許で
は、いくつかの所定の角度の１つを選択してイ
メージ回転を行なうが、本発明による方法のよ
うに、サンプル・グループの全ビツトが同じで
あるかどうかを判断するための、サンプル・グ
ループの検査を含む左右90度のイメージ回転方
法は示されてはいない。 (c) 米国特許第4052699号では、ｎロー、ｎカラ
ムを有するマトリツクスにビデオ・データを記
憶するイメージ処理システムが開示されてい
る。イメージは、前に水平ワードとして書込ま
れたビデオ・データを、ワードごとに垂直にア
クセスすることにより、漸次に90度回転され
る。しかしながら、この特許の方法および装置
は、本発明による方法のように、グループ内の
全ビツトが同じであるかどうかを判断する、回
転されるワードのグループの検査を行なわな
い。 (d) 米国特許第4168488号は、ワードで構成され
たイメージを回転する装置を開示している。こ
の装置では、バツフアを複数の正方形部分に分
割し、それぞれにイメージの各部分が書込まれ
る。この特許は、イメージを90度にわたつて回
転する装置を示しているが、本発明による方法
のような、サブイメージにある全ビツトが同じ
値であるかどうかを判断するためサブイメージ
を検査する動作を含む方法が示されていない。 (e) 米国特許第4225929号は、イメージを中心点
の周りに回転させる装置を含むコード変換器を
開示しているが、この特許では、本発明による
方法のような、全ビツトが同じであるかどうか
を判断するためサブイメージのビツトを検査す
る動作が含まれていない。 (f) 米国特許第4271476号は、印刷または他の処
理のため水平走査形式のイメージを垂直走査形
式のイメージに回転する装置を開示している。
この特許による装置は、イメージを複数の部分
に分割してから各部分を順次に回転する。しか
しながら、この特許では、本発明による方法の
ような、全ビツトが同じであるかどうかを判断
するため各部分を検査する動作を含む方法は示
されていない。 (g) EPO特許出願第081096号は、イメージをプ
リンタに印刷する動作を制御するためのイメー
ジ回転制御回路を開示している。この制御回路
が記憶するのは全表示ではなく、１回に１行だ
けであつて、記憶された行は、印刷のため水平
行から垂直行へ、またはその逆に変換される。
しかしながら、この特許出願では、本発明によ
る方法のような、画素を表わす全ビツトが同じ
てあるかどうかを判断するため、イメージの一
部分を検査する動作を含む、イメージを90度回
転する方法は示されていない。 (h) IBM Technical Disclosure Bulletin、
Vol.18、No.８、January1976、p.2640の論文
は、外形圧縮データを用いたイメージ回転方法
を示しているが、この論文には、本発明による
方法のような、全ビツドが同じであるかどうか
を判断するためイメージの複数の部分を検査す
る動作は含まれていない。 (i) IBM Technical Disclosure Bulletin、
Vol.13、No.11、April1971、p.3267の論文は、
２次元の２進イメージで軸を高速で変換する動
作を実行する方法を示しているが、この論文に
は、本発明による方法のような、全ビツトが同
じであるかどうかを判断するためイメージの複
数の部分を検査する動作は含まれていない。 (j) IBM Technical Disclosure Bulletin、
Vol.18、No.８、January1976、p.2633の論文
は、特に、４×４のキヤラクタ・アレイのイメ
ージを回転するイメージ方向づけのシフト・レ
ジスタ・システムを示しているが、この論文に
は、本発明による方法のような、全ビツトが同
じであるかどうかを判断する、イメージの複数
部分を検査する動作は含まれていない。 以上のように、前述の従来技術はどれも、本発
明の方法について教示もしなければ示唆もしな
い。 〔発明が解決しようとする問題点〕 本発明の目的は、イメージを高速に回転する方
法を提供することである。 〔問題点を解決するための手段〕 本発明が解決しようとする問題点は次のステツ
プを含む方法によつて解決される： イメージを、ｒロー（横列）×ｃカラム（縦行）
に配列されたラスタ形式で記憶し、ローの各々の
イメージ情報をバイト当りｂビツトの複数のバイ
トに書込み、ラスタ形式のローの各々がｃ／ｂバ
イトを含むようにし； ｎロー×ｍカラムのイメージ・ブロツクを一時
記憶領域に移し； イメージ・ブロツクの各々を、回転可能な大き
さのバイト・グループに分割し； グループごとに全ビツトが同じ値であるかどう
かを判断し； 全ビツトが同じ値を持たないグループの各々を
回転し； 回転したグループの各々を、ラスタ記憶装置の
出力領域に書込み； イメージの残りのすべてのブロツクについて前
述のステツプを反復実行する。 更に問題点は、前述のステツプによるイメージ
の回転に、下記のステツプを加えた方法によつて
解決される： イメージを元の場所で回転しようとする場合
は、イメージ・ブロツクを取去つたことによつて
空になつた空間を埋めるように残りのバイトを移
す。 〔作用〕 本発明の方法により、イメージは： ｒロー×ｃカラムに配列されたラスタ形式で記
憶され、ローの各々のイメージ情報はバイト当り
ｂビツトの複数のバイトに書込まれてラスタ形式
のローの各々にはｃ／ｂバイトが含まれ、ｎロー
×ｍカラムのイメージ・ブロツクは一時記憶領域
に移され、イメージ・ブロツクの各々は回転可能
な大きさのバイト・グループに分割され、グルー
プごとに全ビツトが同じ値であるかどうかが判断
され、全ビツトが同じ値を持たないグループの
各々が回転され、回転したグループの各々はラス
タ記憶装置の出力領域に書込まれ、イメージの残
りすべてのブロツクについて前述のステツプが反
復実行されることにより回転される。 〔実施例〕 本発明による方法は、イメージを右回りまたは
左回りに90度回転する。記憶装置に記憶されたイ
メージは、ローを左から右へ、イメージの上部か
ら下部へ読取られるものとする。回転は元の場所
で実行されてもよく（第２図）、又は出力イメー
ジは元のイメージが占有している記憶領域にオー
バラツプしない別個の記憶領域を占有する（第３
図、第４図）。希望するならば、より大きいイメ
ージの長方形の部分を取出して回転し、もう１つ
のより大きいイメージの部分として書込むことが
できる。本発明による方法では、若し、呼出しル
ーチンが元のイメージと出力イメージに同じアド
レスを供給するなら、元の場所で回転が実行され
る。若し、出力イメージのアドレスが元のイメー
ジのアドレスに等しくないから、回転は元の場所
では実行されず、入力イメージは回転によつて変
更されず、元のイメージと出力イメージとはオー
バラツプしてはならない。基本的な２つのタイプ
の回転を第２図と第３図に示す。 第２図に示す例では、回転されたイメージは、
回転前の元のイメージを収容していた記憶領域を
占有する。このタイプの回転の場合、垂直カラム
のビツトはバイト単位にパツクされて回転され、
出力イメージのローはバイトの端数で終了しては
ならないので、ロー数（ｒ）は８の倍数でなけれ
ばならない。以下、回転前または回転後のイメー
ジを含む記憶領域をイメージ領域と呼ぶ。 第３図の例でば、元のイメージと回転されたイ
メージは別個のイメージ領域を占有し、元のイメ
ージは回転動作によつて変更されることはない。
若し、ロー数が８の倍数でないなら、回転された
イメージの右端には、バイト境界まで０を埋込
む。元のイメージ領域と、回転後のイメージ領域
は、（同じ幅であつてもよいが）元のイメージと
回転されたイメージよりもそれぞれ幅が広くなけ
ればならない。若し、元のイメージの最初と最後
のバイトの間の記憶領域（両端のバイトを含む）
が、出力イメージの最初と最後のバイトの間の記
憶領域（両端のバイトを含む）にオーバラツプす
るなら、元のイメージ領域と出力のイメージ領域
とは等しいに違いない。 第４図の例は、元のイメージと回転されたイメ
ージとが同じイメージ領域にある場合を示す。 記憶装置に書込まれている２進イメージを右回
りまたは左回りに90度回転するため、本発明の方
法による回転アルゴリズムでは、（８×８バイト
単位を用い、一般に２進イメージには“０”ビツ
ト（白い画素）しか含まない大きな領域があるこ
とを利用した高速の回転アルゴリズムのような）
斬新な方法の組合せを使用し、従来の方法よりも
かなり速い（４倍から８倍の）動作をする。 以下、左回りの回転の場合について詳細に説明
する。右回りの回転をするのに必要な変更につい
ては、その概要を最後に説明する。イメージを構
成するビツトは８ビツトを１バイトとしてパツク
され記憶されている。ビツト全部の操作は計算上
割高になるので、イメージは８×８ビツトのブロ
ツクに分割される。８×８ビツトのブロツク内の
ビツトは、比較的効率的に回転できる。回転の結
果、８×８ビツトのブロツクは記憶装置で再配列
され、回転プロセスを完了する。 元の場所における回転の場合のブロツク再配列
は、第５図に示すように進められる。入力イメー
ジのローの各々の最初の32バイトは一時記憶領域
にコピーされる（32バイト以外の任意のバイト数
を用いてもよい。この数は回転アルゴリズムを実
行するのに必要な一時記憶領域の容量を制御す
る。）。記憶領域にある入力イメージの各々のロー
の残りのバイトは、一時記憶領域にコピーされた
各ローの最初の32バイトの除去によつて空白にな
つた部分を埋めるように圧縮され、その結果、入
力イメージの末尾に生じた空白には、一時記憶バ
ツフアから挿入すべきデータが収容される。この
空になつた空間は、（後述の理由から）消去され、
一時記憶領域からのデータは回転されてから、前
記空になつた空間に書込まれ、出力イメージの最
後の256カラム（32バイト）を形成する。（イメー
ジの回転は左回りであるので、元のイメージの左
端のデータは、出力イメージの下部に移され、各
ローから取出された32バイト、すなわち256ビツ
トのデータは、出力イメージの256カラムを生じ
る。） 次いで、各ローからの次の32バイトが一時記憶
領域にコピーされ、入力イメージのローの残りの
データは前と同様に圧縮される。既に生成されて
いる出力イメージの256カラムはそのままである
ので、この場合生じる空の空間は出力イメージの
最後の256カラムの直前に生じる。この領域も消
去され、一時記憶バツフアのデータが回転されて
から書込まれる。 以上のプロセスが、入力イメージからのデータ
がなくなるまで続けられる。前述のように、元の
イメージのローの大きさは、32の倍数でなくても
よい。32の倍数でない場合は、最後の回転動作
は、入力イメージの残りのバイト数にのみ作用す
る。 若し、入力イメージと出力イメージとが同じ記
憶領域を占有しないならば、出力イメージは、回
転が始まる前に消去できる。各ローからの連続す
る32バイト・グループは一時記憶領域にコピーし
てから処理するが、入力イメージは各々のコピー
動作後に圧縮されず、そのままの状態を保持す
る。入力イメージが圧縮しなくてもよいので、こ
のタイプの回転は、元の場所での回転よりも僅か
に速い。 一時記憶領域からのデータが回転して出力アレ
イの最終的な場所に入るごとに、個々の８×８ビ
ツトのブロツクの回転が行なわれる。一時記憶領
域のデータは、４バイト幅のカラムで処理される
（各ローのデータのバイト数が４の倍数ではない
場合は別個に扱われるが、プロセスはほぼ同じで
ある。）。入力イメージの８カラムが同時に処理さ
れる。問題は、基本的には４×８バイト（32×８
ビツト）のイメージを取出し、その中の４つの８
×８ビツトのブロツクを回転してから出力アレイ
に配列することである。 このプロセスの最初のステツプは、32×８ビツ
トのブロツク内のビツトが全０であるかどうかを
判断することである。若し、全０なら、回転のた
めの処理は不要である。その理由は、回転によつ
て生じる出力が全０のブロツクであり、回転され
たブロツクが書込まれる出力アレイの領域もあら
かじめ全０にセツトされているからである。この
場合、不要な処理を識別・省略することにより、
通常、８×８ビツトのブロツクを回転するのに実
行時間の大部分が使用されている回転アルゴリズ
ムの速度をあげることができる。これは、32×８
ビツトのブロツクが全０で、回転を省略できる場
合が、イメージの約1/3（漢字または詰込まれた
テキストの場合）から、4/5以上（図面によつて、
または比較的まばらなテキスト、例えばメモの場
合）にわたつて生じるからである。 若し、32×８ビツトのブロツクに非０ビツトが
あれば、このブロツクを４つの８×８ビツトのブ
ロツクに分割し、それぞれのブロツクを検査し
て、全０のブロツクがあるかどうかを調べる。若
し、全０のブロツクがあれば、そのブロツクは前
述のように回転のための処理は省略される。全０
でないブロツクの場合は、第６図に示したアルゴ
リズムを用いてブロツクを回転する。このアルゴ
リズムの詳細について説明する。簡単に言えば、
８バイトをニブル単位に分割し、第１表と第２表
に示すような索引表のセツトを索引するのに用い
る。これらの索引表は、上位ニブルまたは下位ニ
ブルについて索引した値を合計すると、その結果
が回転されたブロツクの最初または最後の４バイ
トを生じるように構成されている。第７図に索引
表の使用例を示す。 イメージ全体を回転するほか、このアルゴリズ
ムは、１つのイメージの長方形部分を取出して回
転し、別のイメージの長方形部分に挿入するのに
使用できる。この動作は、入力イメージの、回転
される領域の部分ではないローの部分のデータを
飛ばし、かつ、同様に出力イメージのローの間に
適切な容量のスペースを残すことによつて行なわ
れるが、このタイプの回転は、元の場所で、第６
図に示したアルゴリズムによつて実行することは
できない。それができるのは、入力イメージと出
力イメージとが別個の場合だけである。 最後に、右回りの回転の実行について説明す
る。この場合は、単にイメージのデータを左から
右へではなく、右から左への順序で移す（すなわ
ち、各ローの最後の32バイトを一時記憶領域にコ
ピーする）コピー／圧縮プロセスを実行し、一時
記憶領域のデータを回転することにより、（左端
ではなく）右端の８×８ビツトのブロツクを回転
して出力イメージの下部に挿入する。８×８ビツ
トのブロツクの回転で用いる索引表についても、
左回りではなく右回りの回転を生じるように変更
する。 下記の第１表、第２表に示す前述の８×８ビツ
トのブロツクを回転する際に用いる索引表のセツ
トは16進値に初期設定されている：
イメージ回転に関する。 〔従来技術〕 代表的な従来技術を下記に示す。 (a) 米国特許第3976872号で開示された機能の中
にイメージを90度回転する方法がある。しかし
ながら、この特許では、本発明のように、イメ
ージのビツト・グループを検査し、ビツト・グ
ループがすべて同じ値であるかどうかを判断す
る動作を含む、イメージを90度回転する方法が
示されてはいない。 (b) 米国特許第3968475号は、イメージを分割し
て、２進データ・アレイの空間を含むサンプ
ル・アレイの領域の各々に挿入することによ
り、２進イメージからデータを取出すデイジタ
ル・プロセツサを開示している。この特許で
は、いくつかの所定の角度の１つを選択してイ
メージ回転を行なうが、本発明による方法のよ
うに、サンプル・グループの全ビツトが同じで
あるかどうかを判断するための、サンプル・グ
ループの検査を含む左右90度のイメージ回転方
法は示されてはいない。 (c) 米国特許第4052699号では、ｎロー、ｎカラ
ムを有するマトリツクスにビデオ・データを記
憶するイメージ処理システムが開示されてい
る。イメージは、前に水平ワードとして書込ま
れたビデオ・データを、ワードごとに垂直にア
クセスすることにより、漸次に90度回転され
る。しかしながら、この特許の方法および装置
は、本発明による方法のように、グループ内の
全ビツトが同じであるかどうかを判断する、回
転されるワードのグループの検査を行なわな
い。 (d) 米国特許第4168488号は、ワードで構成され
たイメージを回転する装置を開示している。こ
の装置では、バツフアを複数の正方形部分に分
割し、それぞれにイメージの各部分が書込まれ
る。この特許は、イメージを90度にわたつて回
転する装置を示しているが、本発明による方法
のような、サブイメージにある全ビツトが同じ
値であるかどうかを判断するためサブイメージ
を検査する動作を含む方法が示されていない。 (e) 米国特許第4225929号は、イメージを中心点
の周りに回転させる装置を含むコード変換器を
開示しているが、この特許では、本発明による
方法のような、全ビツトが同じであるかどうか
を判断するためサブイメージのビツトを検査す
る動作が含まれていない。 (f) 米国特許第4271476号は、印刷または他の処
理のため水平走査形式のイメージを垂直走査形
式のイメージに回転する装置を開示している。
この特許による装置は、イメージを複数の部分
に分割してから各部分を順次に回転する。しか
しながら、この特許では、本発明による方法の
ような、全ビツトが同じであるかどうかを判断
するため各部分を検査する動作を含む方法は示
されていない。 (g) EPO特許出願第081096号は、イメージをプ
リンタに印刷する動作を制御するためのイメー
ジ回転制御回路を開示している。この制御回路
が記憶するのは全表示ではなく、１回に１行だ
けであつて、記憶された行は、印刷のため水平
行から垂直行へ、またはその逆に変換される。
しかしながら、この特許出願では、本発明によ
る方法のような、画素を表わす全ビツトが同じ
てあるかどうかを判断するため、イメージの一
部分を検査する動作を含む、イメージを90度回
転する方法は示されていない。 (h) IBM Technical Disclosure Bulletin、
Vol.18、No.８、January1976、p.2640の論文
は、外形圧縮データを用いたイメージ回転方法
を示しているが、この論文には、本発明による
方法のような、全ビツドが同じであるかどうか
を判断するためイメージの複数の部分を検査す
る動作は含まれていない。 (i) IBM Technical Disclosure Bulletin、
Vol.13、No.11、April1971、p.3267の論文は、
２次元の２進イメージで軸を高速で変換する動
作を実行する方法を示しているが、この論文に
は、本発明による方法のような、全ビツトが同
じであるかどうかを判断するためイメージの複
数の部分を検査する動作は含まれていない。 (j) IBM Technical Disclosure Bulletin、
Vol.18、No.８、January1976、p.2633の論文
は、特に、４×４のキヤラクタ・アレイのイメ
ージを回転するイメージ方向づけのシフト・レ
ジスタ・システムを示しているが、この論文に
は、本発明による方法のような、全ビツトが同
じであるかどうかを判断する、イメージの複数
部分を検査する動作は含まれていない。 以上のように、前述の従来技術はどれも、本発
明の方法について教示もしなければ示唆もしな
い。 〔発明が解決しようとする問題点〕 本発明の目的は、イメージを高速に回転する方
法を提供することである。 〔問題点を解決するための手段〕 本発明が解決しようとする問題点は次のステツ
プを含む方法によつて解決される： イメージを、ｒロー（横列）×ｃカラム（縦行）
に配列されたラスタ形式で記憶し、ローの各々の
イメージ情報をバイト当りｂビツトの複数のバイ
トに書込み、ラスタ形式のローの各々がｃ／ｂバ
イトを含むようにし； ｎロー×ｍカラムのイメージ・ブロツクを一時
記憶領域に移し； イメージ・ブロツクの各々を、回転可能な大き
さのバイト・グループに分割し； グループごとに全ビツトが同じ値であるかどう
かを判断し； 全ビツトが同じ値を持たないグループの各々を
回転し； 回転したグループの各々を、ラスタ記憶装置の
出力領域に書込み； イメージの残りのすべてのブロツクについて前
述のステツプを反復実行する。 更に問題点は、前述のステツプによるイメージ
の回転に、下記のステツプを加えた方法によつて
解決される： イメージを元の場所で回転しようとする場合
は、イメージ・ブロツクを取去つたことによつて
空になつた空間を埋めるように残りのバイトを移
す。 〔作用〕 本発明の方法により、イメージは： ｒロー×ｃカラムに配列されたラスタ形式で記
憶され、ローの各々のイメージ情報はバイト当り
ｂビツトの複数のバイトに書込まれてラスタ形式
のローの各々にはｃ／ｂバイトが含まれ、ｎロー
×ｍカラムのイメージ・ブロツクは一時記憶領域
に移され、イメージ・ブロツクの各々は回転可能
な大きさのバイト・グループに分割され、グルー
プごとに全ビツトが同じ値であるかどうかが判断
され、全ビツトが同じ値を持たないグループの
各々が回転され、回転したグループの各々はラス
タ記憶装置の出力領域に書込まれ、イメージの残
りすべてのブロツクについて前述のステツプが反
復実行されることにより回転される。 〔実施例〕 本発明による方法は、イメージを右回りまたは
左回りに90度回転する。記憶装置に記憶されたイ
メージは、ローを左から右へ、イメージの上部か
ら下部へ読取られるものとする。回転は元の場所
で実行されてもよく（第２図）、又は出力イメー
ジは元のイメージが占有している記憶領域にオー
バラツプしない別個の記憶領域を占有する（第３
図、第４図）。希望するならば、より大きいイメ
ージの長方形の部分を取出して回転し、もう１つ
のより大きいイメージの部分として書込むことが
できる。本発明による方法では、若し、呼出しル
ーチンが元のイメージと出力イメージに同じアド
レスを供給するなら、元の場所で回転が実行され
る。若し、出力イメージのアドレスが元のイメー
ジのアドレスに等しくないから、回転は元の場所
では実行されず、入力イメージは回転によつて変
更されず、元のイメージと出力イメージとはオー
バラツプしてはならない。基本的な２つのタイプ
の回転を第２図と第３図に示す。 第２図に示す例では、回転されたイメージは、
回転前の元のイメージを収容していた記憶領域を
占有する。このタイプの回転の場合、垂直カラム
のビツトはバイト単位にパツクされて回転され、
出力イメージのローはバイトの端数で終了しては
ならないので、ロー数（ｒ）は８の倍数でなけれ
ばならない。以下、回転前または回転後のイメー
ジを含む記憶領域をイメージ領域と呼ぶ。 第３図の例でば、元のイメージと回転されたイ
メージは別個のイメージ領域を占有し、元のイメ
ージは回転動作によつて変更されることはない。
若し、ロー数が８の倍数でないなら、回転された
イメージの右端には、バイト境界まで０を埋込
む。元のイメージ領域と、回転後のイメージ領域
は、（同じ幅であつてもよいが）元のイメージと
回転されたイメージよりもそれぞれ幅が広くなけ
ればならない。若し、元のイメージの最初と最後
のバイトの間の記憶領域（両端のバイトを含む）
が、出力イメージの最初と最後のバイトの間の記
憶領域（両端のバイトを含む）にオーバラツプす
るなら、元のイメージ領域と出力のイメージ領域
とは等しいに違いない。 第４図の例は、元のイメージと回転されたイメ
ージとが同じイメージ領域にある場合を示す。 記憶装置に書込まれている２進イメージを右回
りまたは左回りに90度回転するため、本発明の方
法による回転アルゴリズムでは、（８×８バイト
単位を用い、一般に２進イメージには“０”ビツ
ト（白い画素）しか含まない大きな領域があるこ
とを利用した高速の回転アルゴリズムのような）
斬新な方法の組合せを使用し、従来の方法よりも
かなり速い（４倍から８倍の）動作をする。 以下、左回りの回転の場合について詳細に説明
する。右回りの回転をするのに必要な変更につい
ては、その概要を最後に説明する。イメージを構
成するビツトは８ビツトを１バイトとしてパツク
され記憶されている。ビツト全部の操作は計算上
割高になるので、イメージは８×８ビツトのブロ
ツクに分割される。８×８ビツトのブロツク内の
ビツトは、比較的効率的に回転できる。回転の結
果、８×８ビツトのブロツクは記憶装置で再配列
され、回転プロセスを完了する。 元の場所における回転の場合のブロツク再配列
は、第５図に示すように進められる。入力イメー
ジのローの各々の最初の32バイトは一時記憶領域
にコピーされる（32バイト以外の任意のバイト数
を用いてもよい。この数は回転アルゴリズムを実
行するのに必要な一時記憶領域の容量を制御す
る。）。記憶領域にある入力イメージの各々のロー
の残りのバイトは、一時記憶領域にコピーされた
各ローの最初の32バイトの除去によつて空白にな
つた部分を埋めるように圧縮され、その結果、入
力イメージの末尾に生じた空白には、一時記憶バ
ツフアから挿入すべきデータが収容される。この
空になつた空間は、（後述の理由から）消去され、
一時記憶領域からのデータは回転されてから、前
記空になつた空間に書込まれ、出力イメージの最
後の256カラム（32バイト）を形成する。（イメー
ジの回転は左回りであるので、元のイメージの左
端のデータは、出力イメージの下部に移され、各
ローから取出された32バイト、すなわち256ビツ
トのデータは、出力イメージの256カラムを生じ
る。） 次いで、各ローからの次の32バイトが一時記憶
領域にコピーされ、入力イメージのローの残りの
データは前と同様に圧縮される。既に生成されて
いる出力イメージの256カラムはそのままである
ので、この場合生じる空の空間は出力イメージの
最後の256カラムの直前に生じる。この領域も消
去され、一時記憶バツフアのデータが回転されて
から書込まれる。 以上のプロセスが、入力イメージからのデータ
がなくなるまで続けられる。前述のように、元の
イメージのローの大きさは、32の倍数でなくても
よい。32の倍数でない場合は、最後の回転動作
は、入力イメージの残りのバイト数にのみ作用す
る。 若し、入力イメージと出力イメージとが同じ記
憶領域を占有しないならば、出力イメージは、回
転が始まる前に消去できる。各ローからの連続す
る32バイト・グループは一時記憶領域にコピーし
てから処理するが、入力イメージは各々のコピー
動作後に圧縮されず、そのままの状態を保持す
る。入力イメージが圧縮しなくてもよいので、こ
のタイプの回転は、元の場所での回転よりも僅か
に速い。 一時記憶領域からのデータが回転して出力アレ
イの最終的な場所に入るごとに、個々の８×８ビ
ツトのブロツクの回転が行なわれる。一時記憶領
域のデータは、４バイト幅のカラムで処理される
（各ローのデータのバイト数が４の倍数ではない
場合は別個に扱われるが、プロセスはほぼ同じで
ある。）。入力イメージの８カラムが同時に処理さ
れる。問題は、基本的には４×８バイト（32×８
ビツト）のイメージを取出し、その中の４つの８
×８ビツトのブロツクを回転してから出力アレイ
に配列することである。 このプロセスの最初のステツプは、32×８ビツ
トのブロツク内のビツトが全０であるかどうかを
判断することである。若し、全０なら、回転のた
めの処理は不要である。その理由は、回転によつ
て生じる出力が全０のブロツクであり、回転され
たブロツクが書込まれる出力アレイの領域もあら
かじめ全０にセツトされているからである。この
場合、不要な処理を識別・省略することにより、
通常、８×８ビツトのブロツクを回転するのに実
行時間の大部分が使用されている回転アルゴリズ
ムの速度をあげることができる。これは、32×８
ビツトのブロツクが全０で、回転を省略できる場
合が、イメージの約1/3（漢字または詰込まれた
テキストの場合）から、4/5以上（図面によつて、
または比較的まばらなテキスト、例えばメモの場
合）にわたつて生じるからである。 若し、32×８ビツトのブロツクに非０ビツトが
あれば、このブロツクを４つの８×８ビツトのブ
ロツクに分割し、それぞれのブロツクを検査し
て、全０のブロツクがあるかどうかを調べる。若
し、全０のブロツクがあれば、そのブロツクは前
述のように回転のための処理は省略される。全０
でないブロツクの場合は、第６図に示したアルゴ
リズムを用いてブロツクを回転する。このアルゴ
リズムの詳細について説明する。簡単に言えば、
８バイトをニブル単位に分割し、第１表と第２表
に示すような索引表のセツトを索引するのに用い
る。これらの索引表は、上位ニブルまたは下位ニ
ブルについて索引した値を合計すると、その結果
が回転されたブロツクの最初または最後の４バイ
トを生じるように構成されている。第７図に索引
表の使用例を示す。 イメージ全体を回転するほか、このアルゴリズ
ムは、１つのイメージの長方形部分を取出して回
転し、別のイメージの長方形部分に挿入するのに
使用できる。この動作は、入力イメージの、回転
される領域の部分ではないローの部分のデータを
飛ばし、かつ、同様に出力イメージのローの間に
適切な容量のスペースを残すことによつて行なわ
れるが、このタイプの回転は、元の場所で、第６
図に示したアルゴリズムによつて実行することは
できない。それができるのは、入力イメージと出
力イメージとが別個の場合だけである。 最後に、右回りの回転の実行について説明す
る。この場合は、単にイメージのデータを左から
右へではなく、右から左への順序で移す（すなわ
ち、各ローの最後の32バイトを一時記憶領域にコ
ピーする）コピー／圧縮プロセスを実行し、一時
記憶領域のデータを回転することにより、（左端
ではなく）右端の８×８ビツトのブロツクを回転
して出力イメージの下部に挿入する。８×８ビツ
トのブロツクの回転で用いる索引表についても、
左回りではなく右回りの回転を生じるように変更
する。 下記の第１表、第２表に示す前述の８×８ビツ
トのブロツクを回転する際に用いる索引表のセツ
トは16進値に初期設定されている：
【表】
【表】
本発明により、イメージを従来より４倍から８
倍の高速で右回りまたは左回りに90度回転するこ
とができる。
倍の高速で右回りまたは左回りに90度回転するこ
とができる。
第１図は本発明の方法の流れ図、第２図は本発
明の方法による元の場所での回転の概略図、第３
図は本発明の方法による元の場所以外での回転の
概要図、第４図は本発明の方法によるサブイメー
ジの回転の概要図、第５図は本発明の方法による
イメージ回転のバイト再配列の概要図、第６図は
本発明の方法によるニブル回転の概要図、第７図
は本発明の方法に従つて８×８ビツトのブロツク
を回転するための方法を示す図である。 １１０……ラスタ形式によるイメージ記憶ステ
ツプ、１２０……一時記憶領域への複数バイト書
込みステツプ、１３０……回転可能な大きさのバ
イト・グループへの分割ステツプ、１４０……グ
ループごとの全ビツト検査ステツプ、１５０……
グループ回転、１６０……出力領域へのグループ
書込み、１７０……残りのブロツクの有無検査。
明の方法による元の場所での回転の概略図、第３
図は本発明の方法による元の場所以外での回転の
概要図、第４図は本発明の方法によるサブイメー
ジの回転の概要図、第５図は本発明の方法による
イメージ回転のバイト再配列の概要図、第６図は
本発明の方法によるニブル回転の概要図、第７図
は本発明の方法に従つて８×８ビツトのブロツク
を回転するための方法を示す図である。 １１０……ラスタ形式によるイメージ記憶ステ
ツプ、１２０……一時記憶領域への複数バイト書
込みステツプ、１３０……回転可能な大きさのバ
イト・グループへの分割ステツプ、１４０……グ
ループごとの全ビツト検査ステツプ、１５０……
グループ回転、１６０……出力領域へのグループ
書込み、１７０……残りのブロツクの有無検査。
Claims (1)
- 【特許請求の範囲】 １ イメージを回転する方法であつて、 前記イメージを、バイト当りｂビツトを有しｒ
行ｃ列のイメージを表すバイトのシーケンスとし
てラスタ形式でイメージ・バツフアに記憶し、 前記イメージを各々ｒ行を有するブロツクのシ
リーズから構成されるように縦列に分割し、 前記イメージ・バイトの１つのブロツクを一時
記憶バツフアにコピーし、 前記イメージ・バツフア中において未コピーの
イメージ・バイトをコピー済みバイトの領域に上
書きすることによつて、前記イメージ・バツフア
の再配列を行ない、コピー済みブロツクの再書き
込みのための空白領域を形成し、 前記一時記憶バツフアに記憶されたブロツク内
のビツトがすべて同値であるかどうかを判断し、 前記一時記憶バツフアに記憶されたブロツク内
のビツトがすべて同値である場合には、前記イメ
ージ・バツフアの空白領域に転送してラスタ形式
でブロツクを記憶し、 前記一時記憶バツフアに記憶されたブロツク内
のビツトがすべて同値でない場合にはバイトを回
転のためのｍ×ｍビツトのグループに分割し、 前記グループごとに、全ビツトが同値であるか
どうかを決定し、 全ビツトが同値ではないグループの各々を回転
し、 前記各グループを前記イメージ・バツフアの空
白領域に転送してラスタ形式で各グループを記憶
し、 上記ステツプを上記未コピーのバイト・ブロツ
クに適用して、各々が回転後の形式でイメージ・
バツフアに再記憶されるまで上記各ステツプを繰
り返すことを特徴とするイメージ回転方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US06/567,214 US4627020A (en) | 1983-12-30 | 1983-12-30 | Method for rotating a binary image |
| US567214 | 1983-12-30 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS60146367A JPS60146367A (ja) | 1985-08-02 |
| JPH0426149B2 true JPH0426149B2 (ja) | 1992-05-06 |
Family
ID=24266210
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59192755A Granted JPS60146367A (ja) | 1983-12-30 | 1984-09-17 | イメ−ジ回転方法 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US4627020A (ja) |
| EP (1) | EP0149119B1 (ja) |
| JP (1) | JPS60146367A (ja) |
| CA (1) | CA1222081A (ja) |
| DE (1) | DE3484736D1 (ja) |
Families Citing this family (35)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6172327A (ja) * | 1984-09-17 | 1986-04-14 | Casio Comput Co Ltd | 画像メモリのアドレス分配方式 |
| US4658430A (en) * | 1984-12-27 | 1987-04-14 | International Business Machines Corp. | System for rotating binary images |
| CA1252902A (en) * | 1985-10-31 | 1989-04-18 | David R. Pruett | Method for rotating a binary image |
| DE3650717T2 (de) * | 1985-12-13 | 1999-09-16 | Canon K.K., Tokio/Tokyo | Bildverarbeitungsgerät und -verfahren mit Blöcken von komprimierten Daten |
| US4797852A (en) * | 1986-02-03 | 1989-01-10 | Intel Corporation | Block shifter for graphics processor |
| JPH0715706B2 (ja) * | 1986-03-27 | 1995-02-22 | 日本電気株式会社 | メモリ制御装置 |
| DE3713627A1 (de) * | 1986-04-23 | 1987-10-29 | Casio Computer Co Ltd | Bildspeicherschaltung, insbesondere zur verwendung beim drehen von bilddaten |
| JPS6329791A (ja) * | 1986-07-23 | 1988-02-08 | ミノルタ株式会社 | 文字画像発生装置のフオント変換方式 |
| US4783834A (en) * | 1987-02-20 | 1988-11-08 | International Business Machines Corporation | System for creating transposed image data from a run end or run length representation of an image |
| JP2692081B2 (ja) * | 1987-06-12 | 1997-12-17 | ミノルタ株式会社 | 画像メモリのアドレス制御方式 |
| US5224041A (en) * | 1988-02-02 | 1993-06-29 | Canon Kabushiki Kaisha | Electronic dictionary for outputting words in the opposite order in which they are searched |
| US5111192A (en) * | 1989-12-20 | 1992-05-05 | Xerox Corporation | Method to rotate a bitmap image 90 degrees |
| US5581773A (en) * | 1992-05-12 | 1996-12-03 | Glover; Michael A. | Massively parallel SIMD processor which selectively transfers individual contiguously disposed serial memory elements |
| US5450604A (en) * | 1992-12-18 | 1995-09-12 | Xerox Corporation | Data rotation using parallel to serial units that receive data from memory units and rotation buffer that provides rotated data to memory units |
| CA2121402C (en) * | 1994-04-15 | 1999-02-09 | Albert Z. Zhao | System for fast 90-degree rotation of bi-level images |
| US5671440A (en) * | 1994-08-08 | 1997-09-23 | Eastman Kodak Company | Color image data reorientation and format conversion system |
| US5670982A (en) * | 1995-02-08 | 1997-09-23 | International Business Machines Corporation | System for fast 90-degree rotation of bi-level images |
| US5912995A (en) * | 1996-06-06 | 1999-06-15 | Sun Microsystems, Inc. | Method and apparatus for rotating or transposing a binary image |
| US5946222A (en) * | 1996-12-20 | 1999-08-31 | Oak Technology, Inc. | Method and apparatus for performing a masked byte addition operation |
| US5870581A (en) * | 1996-12-20 | 1999-02-09 | Oak Technology, Inc. | Method and apparatus for performing concurrent write operations to a single-write-input register file and an accumulator register |
| US6223181B1 (en) | 1997-07-31 | 2001-04-24 | Oak Technology, Inc. | Memory conserving and compression technique-compatible image rotation system |
| US5986672A (en) * | 1997-10-14 | 1999-11-16 | Minnesota, Mining And Manufacturing 3M Center | Method and system for forming a rotated image on an imaging element using limited system resources |
| US6208767B1 (en) * | 1998-09-01 | 2001-03-27 | Xerox Corporation | Hardware rotation of images with line sorting in L*A*B* color space |
| US6496199B1 (en) * | 1999-10-01 | 2002-12-17 | Koninklijke Philips Electronics N.V. | Method for storing and retrieving data that conserves memory bandwidth |
| US6941019B1 (en) | 2000-05-10 | 2005-09-06 | International Business Machines Corporation | Reentry into compressed data |
| US7146053B1 (en) | 2000-05-10 | 2006-12-05 | International Business Machines Corporation | Reordering of compressed data |
| US7164489B2 (en) * | 2001-10-19 | 2007-01-16 | Seiko Epson Corporation | Rectangular partitioning in printing rotated images |
| US7376286B2 (en) * | 2002-09-18 | 2008-05-20 | Nxp B.V. | Block-based rotation of arbitrary-shaped images |
| US7876977B2 (en) * | 2006-02-15 | 2011-01-25 | Conexant Systems, Inc. | Image processor and method of image rotation |
| EP1840820A1 (en) | 2006-03-28 | 2007-10-03 | Research In Motion Limited | Method and apparatus for transforming images to accommodate screen orientation |
| US8437805B2 (en) | 2006-03-28 | 2013-05-07 | Research In Motion Limited | Method and apparatus for transforming images to accommodate screen orientation |
| JP2007293606A (ja) * | 2006-04-25 | 2007-11-08 | Matsushita Electric Ind Co Ltd | 画像処理装置 |
| KR101037624B1 (ko) * | 2009-06-19 | 2011-05-30 | (주)실리콘화일 | 메모리를 사용하지 않고 구현되는 이미지 회전 방법 및 장치 |
| US9561008B2 (en) | 2010-12-28 | 2017-02-07 | General Electric Company | Method of displaying image |
| JP6200664B2 (ja) | 2013-03-12 | 2017-09-20 | 株式会社Pfu | 画像データ処理装置、画像データ処理方法及び画像データ処理プログラム |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB1547119A (en) * | 1977-12-09 | 1979-06-06 | Ibm | Image rotation apparatus |
| US4245321A (en) * | 1979-02-16 | 1981-01-13 | The United States Of America As Represented By The Secretary Of The Navy | Rotating raster generator |
| US4267555A (en) * | 1979-06-29 | 1981-05-12 | International Business Machines Corporation | Rotatable raster scan display |
| US4271476A (en) * | 1979-07-17 | 1981-06-02 | International Business Machines Corporation | Method and apparatus for rotating the scan format of digital images |
| JPS59167772A (ja) * | 1983-03-11 | 1984-09-21 | Ricoh Co Ltd | 画像デ−タ回転装置 |
-
1983
- 1983-12-30 US US06/567,214 patent/US4627020A/en not_active Expired - Fee Related
-
1984
- 1984-09-17 JP JP59192755A patent/JPS60146367A/ja active Granted
- 1984-11-15 CA CA000467899A patent/CA1222081A/en not_active Expired
- 1984-12-11 DE DE8484115005T patent/DE3484736D1/de not_active Expired - Lifetime
- 1984-12-11 EP EP84115005A patent/EP0149119B1/en not_active Expired
Also Published As
| Publication number | Publication date |
|---|---|
| US4627020A (en) | 1986-12-02 |
| JPS60146367A (ja) | 1985-08-02 |
| DE3484736D1 (de) | 1991-07-25 |
| EP0149119A3 (en) | 1987-12-02 |
| CA1222081A (en) | 1987-05-19 |
| EP0149119B1 (en) | 1991-06-19 |
| EP0149119A2 (en) | 1985-07-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0426149B2 (ja) | ||
| EP0221418B1 (en) | Improved method for rotating a binary image | |
| EP0216501B1 (en) | Digital image rotation | |
| EP0403122B1 (en) | Processor controlled image overlay | |
| JPS60113582A (ja) | 中間調画像処理方法 | |
| US6018354A (en) | Method for accessing banks of DRAM | |
| JPH0426151B2 (ja) | ||
| JPH08315599A (ja) | メモリの試験システム | |
| JPH0551945B2 (ja) | ||
| JPS61103189A (ja) | デ−タ転送方法 | |
| JPS6053373A (ja) | 階調情報処理方法 | |
| JPS642993B2 (ja) | ||
| EP0569218A2 (en) | Circuit for rotating a ditigal image | |
| US5269003A (en) | Memory architecture for storing twisted pixels | |
| JPH06214859A (ja) | デジタルデータベース及びデジタルデータベース格納・取り出し・訂正方法 | |
| CN100354892C (zh) | 图像边缘过滤处理 | |
| US5119331A (en) | Segmented flash write | |
| JPS6037930B2 (ja) | 情報記憶装置 | |
| JPH0751370B2 (ja) | 像形成装置 | |
| JP3629873B2 (ja) | 画像処理装置 | |
| JPS6271990A (ja) | 画像情報記憶方法 | |
| JPH08202324A (ja) | 画像データ記憶制御装置 | |
| JPS58129473A (ja) | メモリ制御方式 | |
| JPS63239542A (ja) | 画像メモリ装置および画像処理装置 | |
| EP0358374A2 (en) | Data transfer between memories |