JPH11224331A - ラスタ画像生成装置およびラスタ画像生成方法 - Google Patents
ラスタ画像生成装置およびラスタ画像生成方法Info
- Publication number
- JPH11224331A JPH11224331A JP10025295A JP2529598A JPH11224331A JP H11224331 A JPH11224331 A JP H11224331A JP 10025295 A JP10025295 A JP 10025295A JP 2529598 A JP2529598 A JP 2529598A JP H11224331 A JPH11224331 A JP H11224331A
- Authority
- JP
- Japan
- Prior art keywords
- image
- partial
- space
- raster
- memory
- 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.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims description 74
- 230000015654 memory Effects 0.000 claims abstract description 221
- 238000012545 processing Methods 0.000 claims abstract description 50
- 230000009467 reduction Effects 0.000 claims abstract description 49
- 238000006243 chemical reaction Methods 0.000 claims description 113
- 230000009466 transformation Effects 0.000 claims description 56
- PXFBZOLANLWPMH-UHFFFAOYSA-N 16-Epiaffinine Natural products C1C(C2=CC=CC=C2N2)=C2C(=O)CC2C(=CC)CN(C)C1C2CO PXFBZOLANLWPMH-UHFFFAOYSA-N 0.000 claims description 33
- 238000001514 detection method Methods 0.000 claims description 16
- 238000009877 rendering Methods 0.000 claims description 5
- 238000013519 translation Methods 0.000 claims description 4
- 238000013507 mapping Methods 0.000 claims description 2
- 230000001131 transforming effect Effects 0.000 claims description 2
- 239000000872 buffer Substances 0.000 abstract description 24
- 238000010586 diagram Methods 0.000 description 29
- 238000005070 sampling Methods 0.000 description 15
- 229920000740 poly(D-lysine) polymer Polymers 0.000 description 14
- 238000007906 compression Methods 0.000 description 7
- 230000006835 compression Effects 0.000 description 7
- 239000011159 matrix material Substances 0.000 description 7
- 230000002441 reversible effect Effects 0.000 description 4
- 239000004065 semiconductor Substances 0.000 description 4
- 230000001174 ascending effect Effects 0.000 description 3
- 230000006866 deterioration Effects 0.000 description 3
- 238000012546 transfer Methods 0.000 description 3
- 235000010724 Wisteria floribunda Nutrition 0.000 description 2
- 239000013256 coordination polymer Substances 0.000 description 2
- 230000006837 decompression Effects 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000013139 quantization Methods 0.000 description 2
- 230000001360 synchronised effect Effects 0.000 description 2
- PCTMTFRHKVHKIS-BMFZQQSSSA-N (1s,3r,4e,6e,8e,10e,12e,14e,16e,18s,19r,20r,21s,25r,27r,30r,31r,33s,35r,37s,38r)-3-[(2r,3s,4s,5s,6r)-4-amino-3,5-dihydroxy-6-methyloxan-2-yl]oxy-19,25,27,30,31,33,35,37-octahydroxy-18,20,21-trimethyl-23-oxo-22,39-dioxabicyclo[33.3.1]nonatriaconta-4,6,8,10 Chemical compound C1C=C2C[C@@H](OS(O)(=O)=O)CC[C@]2(C)[C@@H]2[C@@H]1[C@@H]1CC[C@H]([C@H](C)CCCC(C)C)[C@@]1(C)CC2.O[C@H]1[C@@H](N)[C@H](O)[C@@H](C)O[C@H]1O[C@H]1/C=C/C=C/C=C/C=C/C=C/C=C/C=C/[C@H](C)[C@@H](O)[C@@H](C)[C@H](C)OC(=O)C[C@H](O)C[C@H](O)CC[C@@H](O)[C@H](O)C[C@H](O)C[C@](O)(C[C@H](O)[C@H]2C(O)=O)O[C@H]2C1 PCTMTFRHKVHKIS-BMFZQQSSSA-N 0.000 description 1
- 241000255777 Lepidoptera Species 0.000 description 1
- 238000013459 approach Methods 0.000 description 1
- 230000015572 biosynthetic process Effects 0.000 description 1
- 230000015556 catabolic process Effects 0.000 description 1
- 239000003086 colorant Substances 0.000 description 1
- 238000013144 data compression Methods 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
- 238000006731 degradation reaction Methods 0.000 description 1
- 230000007274 generation of a signal involved in cell-cell signaling Effects 0.000 description 1
- 230000007774 longterm Effects 0.000 description 1
- 230000002123 temporal effect Effects 0.000 description 1
Landscapes
- Image Processing (AREA)
- Storing Facsimile Image Data (AREA)
- Editing Of Facsimile Originals (AREA)
- Compression Of Band Width Or Redundancy In Fax (AREA)
Abstract
(57)【要約】
【課題】 スキャンドイメージの処理に必要なメモリを
大幅に削減し、低価格なラスタ画像生成装置および方法
を提供する。 【解決手段】 スキャンドイメージの回転、拡縮、アフ
ィン変換、クリッピング処理、イメージ上へのラインア
ートの重ね書き処理等において、ソース画像入力時に、
ソース画像を必要に応じて縮小し、部分画像に分割し、
デバイス画像の描画に寄与する部分のみを符号化するこ
とでデータ量を縮小する。デバイス画像のラスタスキャ
ンの際に逆サンプリングを用いて部分画像の参照順を決
定し、ラスタスキャンと同期を取り、参照順に従って部
分画像の符号を復号してラスタスキャンの際に必要な部
分画像のみを保持し、それらに対して逆サンプリングを
行ってアフィン変換とスキャンドイメージの輪郭内部の
画素出力を行う。
大幅に削減し、低価格なラスタ画像生成装置および方法
を提供する。 【解決手段】 スキャンドイメージの回転、拡縮、アフ
ィン変換、クリッピング処理、イメージ上へのラインア
ートの重ね書き処理等において、ソース画像入力時に、
ソース画像を必要に応じて縮小し、部分画像に分割し、
デバイス画像の描画に寄与する部分のみを符号化するこ
とでデータ量を縮小する。デバイス画像のラスタスキャ
ンの際に逆サンプリングを用いて部分画像の参照順を決
定し、ラスタスキャンと同期を取り、参照順に従って部
分画像の符号を復号してラスタスキャンの際に必要な部
分画像のみを保持し、それらに対して逆サンプリングを
行ってアフィン変換とスキャンドイメージの輪郭内部の
画素出力を行う。
Description
【０００１】
【発明の属する技術分野】本発明は、プリンタあるいは
ラスタ出力装置用のラスタ画像データの生成方法あるい
は描画を行うための画像描画装置に関する。特に、ラス
タ入力画像に関して、画像にアフィン変換を施し、任意
の形状に切り抜き、出力画像上の任意の場所に描画する
ためのラスタ画像生成装置およびラスタ画像生成方法に
関する。
ラスタ出力装置用のラスタ画像データの生成方法あるい
は描画を行うための画像描画装置に関する。特に、ラス
タ入力画像に関して、画像にアフィン変換を施し、任意
の形状に切り抜き、出力画像上の任意の場所に描画する
ためのラスタ画像生成装置およびラスタ画像生成方法に
関する。
【０００２】
【従来の技術】文字データの他に、直線、曲線、多角形
等のグラッフィックデータ（これらをラインアートと呼
ぶ）や、写真、手書き文書、印刷物等をスキャン入力し
たスキャンドイメージをプリンタ等に出力するための画
像記述方法としてページ記述言語（以下ではＰＤＬと略
記する）が広く用いられている。代表的なＰＤＬとして
Ｘｅｒｏｘ社のＩｎｔｅｒｐｒｅｓｓ（Ｘｅｒｏｘ社の
登録商標）、ＡｄｏｂｅＳｙｓｔｅｍｓ社のＰｏｓｔＳ
ｃｒｉｐｔ（Ａｄｏｂｅ Ｓｙｓｔｅｍｓ社の登録商
標）が知られている。Ｉｎｔｅｒｐｒｅｓｓの詳細につ
いては、Ｓ．Ｊ．ＨａｒｒｉｇｔｏｎとＲ．Ｒ．Ｂｕｃ
ｋｌｅｙ著「ＩＮＴＥＲＰＲＥＳＳ：Ｔｈｅ Ｓｏｕｒ
ｃｅ Ｂｏｏｋ−Ｔｈｅ Ｄｏｃｕｍｅｎｔ ａｎｄ
ＰａｇｅＤｅｓｃｒｉｐｔｉｏｎ Ｌａｎｇｕａｇｅ
ｆｏｒ ＰｅｒｆｏｒｍａｎｃｅＰｒｉｎｔｉｎｇ−」
Ｂｒｅｎｄｙ（１９８８），邦訳「インタープレス−電
子出版のためのページ記述言語−」丸善（１９８９）に
記載されている。ＰｏｓｔＳｃｒｉｐｔの詳細について
は、Ａｄｏｂｅ Ｓｙｓｔｅｍｓ著「ＰｏｓｔＳｃｒｉ
ｐｔ Ｌａｎｇｕａｇｅ Ｒｅｆｅｒｅｎｃｅ Ｍａｎ
ｕａｌ Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ」Ａｄｄｉｓｏ
ｎ−Ｗｅｓｌｅｙ（１９９０），邦訳「ページ記述言語
ＰｏｓｔＳｃｒｉｐｔリファレンス・マニュアル第２
版」アスキー（１９９１）に記載されている。
等のグラッフィックデータ（これらをラインアートと呼
ぶ）や、写真、手書き文書、印刷物等をスキャン入力し
たスキャンドイメージをプリンタ等に出力するための画
像記述方法としてページ記述言語（以下ではＰＤＬと略
記する）が広く用いられている。代表的なＰＤＬとして
Ｘｅｒｏｘ社のＩｎｔｅｒｐｒｅｓｓ（Ｘｅｒｏｘ社の
登録商標）、ＡｄｏｂｅＳｙｓｔｅｍｓ社のＰｏｓｔＳ
ｃｒｉｐｔ（Ａｄｏｂｅ Ｓｙｓｔｅｍｓ社の登録商
標）が知られている。Ｉｎｔｅｒｐｒｅｓｓの詳細につ
いては、Ｓ．Ｊ．ＨａｒｒｉｇｔｏｎとＲ．Ｒ．Ｂｕｃ
ｋｌｅｙ著「ＩＮＴＥＲＰＲＥＳＳ：Ｔｈｅ Ｓｏｕｒ
ｃｅ Ｂｏｏｋ−Ｔｈｅ Ｄｏｃｕｍｅｎｔ ａｎｄ
ＰａｇｅＤｅｓｃｒｉｐｔｉｏｎ Ｌａｎｇｕａｇｅ
ｆｏｒ ＰｅｒｆｏｒｍａｎｃｅＰｒｉｎｔｉｎｇ−」
Ｂｒｅｎｄｙ（１９８８），邦訳「インタープレス−電
子出版のためのページ記述言語−」丸善（１９８９）に
記載されている。ＰｏｓｔＳｃｒｉｐｔの詳細について
は、Ａｄｏｂｅ Ｓｙｓｔｅｍｓ著「ＰｏｓｔＳｃｒｉ
ｐｔ Ｌａｎｇｕａｇｅ Ｒｅｆｅｒｅｎｃｅ Ｍａｎ
ｕａｌ Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ」Ａｄｄｉｓｏ
ｎ−Ｗｅｓｌｅｙ（１９９０），邦訳「ページ記述言語
ＰｏｓｔＳｃｒｉｐｔリファレンス・マニュアル第２
版」アスキー（１９９１）に記載されている。
【０００３】スキャンドイメージ部分の画像は、画素の
２次元集合であるラスタで表現される。ラスタは直交座
標上に画素を配置したデータ構造である。ラスタの入出
力は、画素をまずＸ軸方向に走査しながら１行分入力あ
るいは出力し、次いで走査をＹ軸方向に１行ずらして同
様に１行分入力あるいは出力する。これを全ての行につ
いて行うことで画像の入力あるいは出力を達成する。Ｘ
軸方向の走査を主走査、Ｙ軸方向の走査を副走査ともい
う。
２次元集合であるラスタで表現される。ラスタは直交座
標上に画素を配置したデータ構造である。ラスタの入出
力は、画素をまずＸ軸方向に走査しながら１行分入力あ
るいは出力し、次いで走査をＹ軸方向に１行ずらして同
様に１行分入力あるいは出力する。これを全ての行につ
いて行うことで画像の入力あるいは出力を達成する。Ｘ
軸方向の走査を主走査、Ｙ軸方向の走査を副走査ともい
う。
【０００４】ＰＤＬでは、画像出力デバイスの解像度と
は独立にラインアートとスキャンドイメージの画像デー
タを取り扱うことが出来るよう設計されている。例え
ば、ＰｏｓｔＳｃｒｉｐｔではユーザが定義した任意の
空間（ユーザ空間）でラインアートを記述でき、Ｐｏｓ
ｔＳｃｒｉｐｔ処理系がＩＯＴの解像度に依存したデバ
イス空間に変換する。スキャンドイメージデータについ
ては任意の解像度のラスタを入力しそれをデバイス空間
に変換する。スキャンドイメージとして入力されるラス
タ画像をソース画像とも呼び、ＰＤＬでは任意の数のソ
ース画像を１枚の出力画像（デバイス画像と呼ぶ）に描
画することができる。
は独立にラインアートとスキャンドイメージの画像デー
タを取り扱うことが出来るよう設計されている。例え
ば、ＰｏｓｔＳｃｒｉｐｔではユーザが定義した任意の
空間（ユーザ空間）でラインアートを記述でき、Ｐｏｓ
ｔＳｃｒｉｐｔ処理系がＩＯＴの解像度に依存したデバ
イス空間に変換する。スキャンドイメージデータについ
ては任意の解像度のラスタを入力しそれをデバイス空間
に変換する。スキャンドイメージとして入力されるラス
タ画像をソース画像とも呼び、ＰＤＬでは任意の数のソ
ース画像を１枚の出力画像（デバイス画像と呼ぶ）に描
画することができる。
【０００５】ＰｏｓｔＳｃｒｉｐｔには３つの空間、す
なわち、ユーザ空間，デバイス空間，ソース空間が有
る。ＰｏｓｔＳｃｒｉｐｔは無限のサイズと精度のユー
ザ空間に対して描画を行う。デバイス空間はイメージを
出力するデバイスに依存した有限の範囲と精度を有する
空間である。ユーザ空間からデバイス空間への写像はア
フィン変換を用いて定義され、その変換マトリクスをＭ
１とする。ソース空間は画素が１辺の長さ１の正方形と
なるように定義された空間で、ユーザ空間との関係はユ
ーザ空間からソース空間へのアフィン変換Ｍ２を用いて
定義される。従ってソース空間からデバイス空間へのア
フィン変換Ｍは、まずソース空間からユーザ空間へアフ
ィン変換Ｍ２-1を行い（アフィン変換Ｍ２-1は変換Ｍ２
の逆変換である）、次いでユーザ空間からデバイス空間
へアフィン変換Ｍ１を行えばよい。したがって、ソース
空間からデバイス空間へのアフィン変換Ｍは、Ｍ２-1お
よびＭ１によって下式のように表現される。
なわち、ユーザ空間，デバイス空間，ソース空間が有
る。ＰｏｓｔＳｃｒｉｐｔは無限のサイズと精度のユー
ザ空間に対して描画を行う。デバイス空間はイメージを
出力するデバイスに依存した有限の範囲と精度を有する
空間である。ユーザ空間からデバイス空間への写像はア
フィン変換を用いて定義され、その変換マトリクスをＭ
１とする。ソース空間は画素が１辺の長さ１の正方形と
なるように定義された空間で、ユーザ空間との関係はユ
ーザ空間からソース空間へのアフィン変換Ｍ２を用いて
定義される。従ってソース空間からデバイス空間へのア
フィン変換Ｍは、まずソース空間からユーザ空間へアフ
ィン変換Ｍ２-1を行い（アフィン変換Ｍ２-1は変換Ｍ２
の逆変換である）、次いでユーザ空間からデバイス空間
へアフィン変換Ｍ１を行えばよい。したがって、ソース
空間からデバイス空間へのアフィン変換Ｍは、Ｍ２-1お
よびＭ１によって下式のように表現される。
【０００６】
【数１】Ｍ＝Ｍ１・Ｍ２-1 である。
【０００７】また、ソース空間の座標（ｘ，ｙ）とデバ
イス空間の座標（Ｘ，Ｙ）は下記に示す式で結び付けら
れる。
イス空間の座標（Ｘ，Ｙ）は下記に示す式で結び付けら
れる。
【０００８】
【数２】（Ｘ，Ｙ，１）T＝Ｍ・（ｘ，ｙ，１）T （ｘ，ｙ，１）T＝Ｍ-1・（Ｘ，Ｙ，１）T なお、ここで（ｖ1，ｖ2，ｖ3）Tはベクトル（ｖ1，
ｖ2，ｖ3）の転置を意味する。
ｖ2，ｖ3）の転置を意味する。
【０００９】アフィン変換マトリクスＭの具体的な内容
は、下式に示すものである。
は、下式に示すものである。
【００１０】
【数３】
【００１１】であり、各要素は任意の値（ただし逆行列
Ｍ-1が存在せねばならない）を取りうる。
Ｍ-1が存在せねばならない）を取りうる。
【００１２】拡大／縮小，回転は要素ａ，ｂ，ｃ，ｄに
より表現され、平行移動は要素ｕ，ｖで表現される。
より表現され、平行移動は要素ｕ，ｖで表現される。
【００１３】
【数４】Ｘ＝ａｘ＋ｂｙ＋ｕ Ｙ＝ｃｘ＋ｄｙ＋ｖ
【００１４】
【数５】下記の条件、 ａｄ−ｂｃ≠０
【００１５】が成立する時には逆変換マトリクスＭ-1が
存在し、逆変換マトリクスＭ-1の各要素を下記の様に、
存在し、逆変換マトリクスＭ-1の各要素を下記の様に、
【００１６】
【数６】
【００１７】と書くと、それぞれの要素は下記に示すよ
うに記述できる。
うに記述できる。
【００１８】
【数７】ａ’＝ ｄ／（ａｄ−ｂｃ） ｂ’＝−ｂ／（ａｄ−ｂｃ） ｃ’＝−ｃ／（ａｄ−ｂｃ） ｄ’＝ ａ／（ａｄ−ｂｃ） ｕ’＝（ｂｖ−ｄｕ）／（ａｄ−ｂｃ） ｖ’＝（ｃｕ−ａｖ）／（ａｄ−ｂｃ）
【００１９】したがってデバイス空間の座標（Ｘ，Ｙ）
から、ソース空間上の対応する座標（ｘ，ｙ）を容易に
求めることができる。
から、ソース空間上の対応する座標（ｘ，ｙ）を容易に
求めることができる。
【００２０】
【数８】ｘ＝ａ’Ｘ＋ｂ’Ｙ＋ｕ’ ｙ＝ｃ’Ｘ＋ｄ’Ｙ＋ｖ’
【００２１】デバイス画像の座標（Ｘ，Ｙ）の画素を決
定するためには上式を用いてソース画像の座標（ｘ，
ｙ）を求めてその画素を読み出せばよい。これを逆サン
プリングと呼ぶ。
定するためには上式を用いてソース画像の座標（ｘ，
ｙ）を求めてその画素を読み出せばよい。これを逆サン
プリングと呼ぶ。
【００２２】ＰＤＬで記述された画像表現を描画処理し
画像出力デバイスに出力する為の画素情報を作る技術
は、例えば、小野澤らにより著された「複数のページ記
述言語に対応するデコンポーザ」富士ゼロックステクニ
カルレポート，Ｎｏ．８，ｐｐ．６１−６８，（１９９
３）や、堀らにより発明され特開平５−２２４６３７号
公報において公開された技術がある。
画像出力デバイスに出力する為の画素情報を作る技術
は、例えば、小野澤らにより著された「複数のページ記
述言語に対応するデコンポーザ」富士ゼロックステクニ
カルレポート，Ｎｏ．８，ｐｐ．６１−６８，（１９９
３）や、堀らにより発明され特開平５−２２４６３７号
公報において公開された技術がある。
【００２３】これらの技術は一般に計算機システム上で
処理ステップを記述したソフトウェアを用いて実施する
ことが可能である。
処理ステップを記述したソフトウェアを用いて実施する
ことが可能である。
【００２４】特開平５−２２４６３７号公報に開示され
る技術では、ＰＤＬを入力部にて入力し、インタプリタ
でＰＤＬを解釈実行する。その結果、描画情報はデバイ
ス空間の走査線上のセグメント情報として記憶手段に格
納される。走査線上の連続画素が同一属性を持つ線分を
セグメントとする。ラインアートで描画されるデバイス
画素に関しては、画素が同じ色を有するとき同一属性と
する。スキャンドイメージで描画されるデバイス画素に
関しては、同一のソース画像に由来する場合同一属性と
する。セグメント情報は、Ｃ言語風に記述すると、例え
ば次のような結合リスト構造を有するデータ構造を持
つ。
る技術では、ＰＤＬを入力部にて入力し、インタプリタ
でＰＤＬを解釈実行する。その結果、描画情報はデバイ
ス空間の走査線上のセグメント情報として記憶手段に格
納される。走査線上の連続画素が同一属性を持つ線分を
セグメントとする。ラインアートで描画されるデバイス
画素に関しては、画素が同じ色を有するとき同一属性と
する。スキャンドイメージで描画されるデバイス画素に
関しては、同一のソース画像に由来する場合同一属性と
する。セグメント情報は、Ｃ言語風に記述すると、例え
ば次のような結合リスト構造を有するデータ構造を持
つ。
【００２５】
【数９】
【００２６】走査線上のセグメントは左（Ｘ座標値の小
さいほう）から右（Ｘ座標値の大きいほう）へ結合リス
トで表現されている。セグメント１個が結合リストのノ
ード１個で表現される。セグメントはＸ座標Ｘ０からＸ
１までの範囲に存在し、ポインタｐｐでその画素値は指
し示される。あるセグメントのノードのｎｅｘｔフィー
ルドは右隣のセグメントのノードを指している。走査線
上の右端のノードでは、右端であることを示すためにｎ
ｅｘｔフィールドに特別な値、例えばＮＵＬＬ（＝０）
を入れる。ｄｐフィールドはセグメントがラインアート
の描画に由来するか、スキャンドイメージの描画に由来
するかを示す。スキャンドイメージの場合、セグメント
の左端画素はポインタｐｐで示されるアドレス、その右
隣の画素はｐｐ＋１のアドレス、更に右隣の画素はｐｐ
＋２のアドレスという形で画素をアクセスする。
さいほう）から右（Ｘ座標値の大きいほう）へ結合リス
トで表現されている。セグメント１個が結合リストのノ
ード１個で表現される。セグメントはＸ座標Ｘ０からＸ
１までの範囲に存在し、ポインタｐｐでその画素値は指
し示される。あるセグメントのノードのｎｅｘｔフィー
ルドは右隣のセグメントのノードを指している。走査線
上の右端のノードでは、右端であることを示すためにｎ
ｅｘｔフィールドに特別な値、例えばＮＵＬＬ（＝０）
を入れる。ｄｐフィールドはセグメントがラインアート
の描画に由来するか、スキャンドイメージの描画に由来
するかを示す。スキャンドイメージの場合、セグメント
の左端画素はポインタｐｐで示されるアドレス、その右
隣の画素はｐｐ＋１のアドレス、更に右隣の画素はｐｐ
＋２のアドレスという形で画素をアクセスする。
【００２７】デバイス画像は複数の走査線で構成され
る。デバイス画像の高さすなわち走査線数をＨＤとす
る。デバイス画像全体表現するためには、上記データ構
造へのポインタから構成される要素数ＨＤの配列ｄｅｖ
Ｉｍａｇｅを設け、Ｙ番目の配列要素がデバイス空間の
Ｙ座標がＹの走査線の左端のセグメントのノードへのポ
インタとなるように配列ｄｅｖＩｍａｇｅを設定する。
この配列の定義をＣ言語ふうに記述すると以下のように
なる。
る。デバイス画像の高さすなわち走査線数をＨＤとす
る。デバイス画像全体表現するためには、上記データ構
造へのポインタから構成される要素数ＨＤの配列ｄｅｖ
Ｉｍａｇｅを設け、Ｙ番目の配列要素がデバイス空間の
Ｙ座標がＹの走査線の左端のセグメントのノードへのポ
インタとなるように配列ｄｅｖＩｍａｇｅを設定する。
この配列の定義をＣ言語ふうに記述すると以下のように
なる。
【００２８】
【数１０】ｓｔｒｕｃｔ ｅｄｇｅ＿ｌｉｓｔ＊ ｄｅ
ｖＩｍａｇｅ［ＨＤ］；
ｖＩｍａｇｅ［ＨＤ］；
【００２９】特開平５−２２４６３７号公報に記載の技
術では、ビデオ信号生成部でセグメントの情報を走査順
に読み出し、画素へのポインタを用いて出力画素を読み
出し、出力部へ送る。ここの一般的な処理手順をＣ言語
ふうに記述すると以下のようになる。
術では、ビデオ信号生成部でセグメントの情報を走査順
に読み出し、画素へのポインタを用いて出力画素を読み
出し、出力部へ送る。ここの一般的な処理手順をＣ言語
ふうに記述すると以下のようになる。
【００３０】
【数１１】
【００３１】ソース画像をイメージ変換部にてイメージ
変換後、デバイス画像用に変換されたスキャンドイメー
ジ画像はページメモリにサイズがＷＤ×ＨＤ画素の画像
として走査順に格納されている。スキャンドイメージの
セグメントのノードのｐｐはページメモリに格納された
画素を指している。その画素は該セグメントの左端画素
に対応する画素である。
変換後、デバイス画像用に変換されたスキャンドイメー
ジ画像はページメモリにサイズがＷＤ×ＨＤ画素の画像
として走査順に格納されている。スキャンドイメージの
セグメントのノードのｐｐはページメモリに格納された
画素を指している。その画素は該セグメントの左端画素
に対応する画素である。
【００３２】特開平５−２２４６３７号公報で開示され
る従来技術では、イメージ変換部で拡大、縮小と、回転
といったアフィン変換を含む変形処理を行う。ラスタ画
像のアフィン変換については既に多くの技術が知られて
いるが、大まかに下記４種類に分類できる。
る従来技術では、イメージ変換部で拡大、縮小と、回転
といったアフィン変換を含む変形処理を行う。ラスタ画
像のアフィン変換については既に多くの技術が知られて
いるが、大まかに下記４種類に分類できる。
【００３３】Ａ）斜交軸変換と、９０°回転と、拡大／
縮小とを組み合せたもの。例えば特開昭６２−１７７６
７５に開示され、ソース画像を９０°回転し、縮小をと
もなった斜交軸変換を行い、−９０°回転し、拡大をと
もなった斜交軸変換を行うことで、任意の拡大／縮小と
回転を実現する。上記一連の処理において、処理ステッ
プ間では各処理の入力側の画像と出力側の画像ををそれ
ぞれバッファメモリに格納する必要がある。従って、す
くなくとも画像２面分のページメモリを設ける必要があ
る。
縮小とを組み合せたもの。例えば特開昭６２−１７７６
７５に開示され、ソース画像を９０°回転し、縮小をと
もなった斜交軸変換を行い、−９０°回転し、拡大をと
もなった斜交軸変換を行うことで、任意の拡大／縮小と
回転を実現する。上記一連の処理において、処理ステッ
プ間では各処理の入力側の画像と出力側の画像ををそれ
ぞれバッファメモリに格納する必要がある。従って、す
くなくとも画像２面分のページメモリを設ける必要があ
る。
【００３４】Ｂ）ソース画像の画素をデバイス画像上の
対応する場所にコピーするもの。ソース座標からデバイ
ス座標を決定することを順サンプリングと呼ぶ。具体的
には図２２ａに示すように、ソース画像の画素座標
（ｘ，ｙ）を変換マトリクスＭで線形変換してデバイス
空間の座標（Ｘ，Ｙ）を求め、デバイス空間の画素位置
にソース画像の該画素をコピーするものである。例えば
特開昭６１−８８３７４、特開昭６２−２００７４、特
開昭６２−１３９０８２、特開昭６３−１８４８７８、
特開平４−５５９８６、特開平５−２５０４６６等に開
示されている。この技術では、入力画像の走査順に処理
できるので、処理済画像用のページメモリを設ける必要
がある。
対応する場所にコピーするもの。ソース座標からデバイ
ス座標を決定することを順サンプリングと呼ぶ。具体的
には図２２ａに示すように、ソース画像の画素座標
（ｘ，ｙ）を変換マトリクスＭで線形変換してデバイス
空間の座標（Ｘ，Ｙ）を求め、デバイス空間の画素位置
にソース画像の該画素をコピーするものである。例えば
特開昭６１−８８３７４、特開昭６２−２００７４、特
開昭６２−１３９０８２、特開昭６３−１８４８７８、
特開平４−５５９８６、特開平５−２５０４６６等に開
示されている。この技術では、入力画像の走査順に処理
できるので、処理済画像用のページメモリを設ける必要
がある。
【００３５】Ｃ）デバイス座標に対応するソース座標を
求めソース画像を読みデバイス画像の画素を得るもの。
デバイス座標からソース座標を決定することを逆サンプ
リングと呼ぶ。具体的には図２２ｂに示すように、デバ
イス空間の画素座標（Ｘ，Ｙ）を逆変換マトリクスＭ-1
で線形変換してソース空間での座標（ｘ，ｙ）を求め、
ソース画像の該画素をデバイス空間（Ｘ，Ｙ）にコピー
するものである。例えば特開昭６２−１４５４８３、特
開昭６２−２５６０８９、特開６３−１１６１９３、特
開昭６３−１２９４７６、特開平４−６４１７７等に開
示されている。この技術では処理前画像用ページメモリ
が必要である。更に、特開平５−２２４６３７の技術に
組合わせるためには別のページメモリが必要なので、合
計画像２面分のページメモリを設ける必要がある。
求めソース画像を読みデバイス画像の画素を得るもの。
デバイス座標からソース座標を決定することを逆サンプ
リングと呼ぶ。具体的には図２２ｂに示すように、デバ
イス空間の画素座標（Ｘ，Ｙ）を逆変換マトリクスＭ-1
で線形変換してソース空間での座標（ｘ，ｙ）を求め、
ソース画像の該画素をデバイス空間（Ｘ，Ｙ）にコピー
するものである。例えば特開昭６２−１４５４８３、特
開昭６２−２５６０８９、特開６３−１１６１９３、特
開昭６３−１２９４７６、特開平４−６４１７７等に開
示されている。この技術では処理前画像用ページメモリ
が必要である。更に、特開平５−２２４６３７の技術に
組合わせるためには別のページメモリが必要なので、合
計画像２面分のページメモリを設ける必要がある。
【００３６】Ｄ）拡大／縮小を行うステップと、回転を
行うステップとの２ステップでアフィン変換を行う。、
処理ステップ間では各処理の入力側の画像と出力側の画
像ををそれぞれページメモリに格納する必要があるた
め、画像２面分のページメモリを設ける必要がある。
行うステップとの２ステップでアフィン変換を行う。、
処理ステップ間では各処理の入力側の画像と出力側の画
像ををそれぞれページメモリに格納する必要があるた
め、画像２面分のページメモリを設ける必要がある。
【００３７】上記いずれの技術を用いても画像全体を格
納するページメモリを少なくとも１個必要とする。
納するページメモリを少なくとも１個必要とする。
【００３８】
【発明が解決しようとする課題】特開平５−２２４６３
７の技術では、描画情報をセグメントで表現することに
よりデバイス画像形成に必要なメモリのサイズを削減で
きるが、削減に有効な部分はラインアートとして描画さ
れた部分のみである。スキャンドイメージの描画の為に
は、アフィン変換の為と画像そのものを保持するために
少なくとも画像１面分のメモリ（これをページメモリと
呼ぶ）が必要である。例えば解像度６００ＳＰＩでＡ４
サイズのフルカラーラスタデータを１画素をシアン、マ
ゼンタ、イエロー、ブラックの４色計４Ｂｙｔｅで表現
するとデデータ量は約１４０ＭＢｙｔｅとなる。
７の技術では、描画情報をセグメントで表現することに
よりデバイス画像形成に必要なメモリのサイズを削減で
きるが、削減に有効な部分はラインアートとして描画さ
れた部分のみである。スキャンドイメージの描画の為に
は、アフィン変換の為と画像そのものを保持するために
少なくとも画像１面分のメモリ（これをページメモリと
呼ぶ）が必要である。例えば解像度６００ＳＰＩでＡ４
サイズのフルカラーラスタデータを１画素をシアン、マ
ゼンタ、イエロー、ブラックの４色計４Ｂｙｔｅで表現
するとデデータ量は約１４０ＭＢｙｔｅとなる。
【００３９】ページメモリは一般に半導体メモリ特にＤ
ＲＡＭ（ダイナミック・ランダム・アクセス・メモリ）
を用いて構成される。ＤＲＡＭを用いるのは半導体メモ
リの中では安価なメモリデバイスであるからである。し
かし、Ａ４サイズ画像で１４０ＭＢｙｔｅ、Ａ３サイズ
画像で２８０ＭＢｙｔｅものメモリを設けることはＤＲ
ＡＭを用いてもたいへん高価である。
ＲＡＭ（ダイナミック・ランダム・アクセス・メモリ）
を用いて構成される。ＤＲＡＭを用いるのは半導体メモ
リの中では安価なメモリデバイスであるからである。し
かし、Ａ４サイズ画像で１４０ＭＢｙｔｅ、Ａ３サイズ
画像で２８０ＭＢｙｔｅものメモリを設けることはＤＲ
ＡＭを用いてもたいへん高価である。
【００４０】計算機において、大きなデータをそのデー
タサイズよりも小さなメモリを用いて処理する技術とし
て仮想記憶が知られている。仮想記憶の一般原理につい
てはＪｏｈｎ Ｌ．Ｈｅｎｎｅｓｓｙ ＆ Ｄａｖｉｄ
Ａ．Ｐａｔｔｅｒｓｏｎ両氏によるテキストブック
“Ｃｏｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ ＡＱ
ｕａｎｔｉｔａｔｉｖｅ Ａｐｐｒｏａｃｈ”，Ｓｅｃ
ｏｎｄ Ｅｄｉｔｉｏｎ；１９９６；Ｍｏｒｇａｎ Ｋ
ａｕｆｍａｎｎ Ｐｕｂｌｉｓｈｅｒｓ，Ｉｎｃ．の
５．７章に記載されているので説明を省略する。ページ
メモリを仮想記憶技術を用いて構成すると、Ａ４サイズ
で１４０ＭＢｙｔｅのデータを主記憶と２次記憶を構成
する磁気ディスクとの間で転送することになるが、磁気
ディスクの読み書きのスピードはたかだか１０ＭＢｙｔ
ｅ／ｓｅｃなので、主記憶と２次記憶間の往復の転送に
要する時間は２８秒以上かかる。仮想記憶の導入により
半導体メモリをより安価な磁気ディスクに置き換えるこ
とでコストは改善されるが処理速度が低下するという別
の問題が発生する。
タサイズよりも小さなメモリを用いて処理する技術とし
て仮想記憶が知られている。仮想記憶の一般原理につい
てはＪｏｈｎ Ｌ．Ｈｅｎｎｅｓｓｙ ＆ Ｄａｖｉｄ
Ａ．Ｐａｔｔｅｒｓｏｎ両氏によるテキストブック
“Ｃｏｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ ＡＱ
ｕａｎｔｉｔａｔｉｖｅ Ａｐｐｒｏａｃｈ”，Ｓｅｃ
ｏｎｄ Ｅｄｉｔｉｏｎ；１９９６；Ｍｏｒｇａｎ Ｋ
ａｕｆｍａｎｎ Ｐｕｂｌｉｓｈｅｒｓ，Ｉｎｃ．の
５．７章に記載されているので説明を省略する。ページ
メモリを仮想記憶技術を用いて構成すると、Ａ４サイズ
で１４０ＭＢｙｔｅのデータを主記憶と２次記憶を構成
する磁気ディスクとの間で転送することになるが、磁気
ディスクの読み書きのスピードはたかだか１０ＭＢｙｔ
ｅ／ｓｅｃなので、主記憶と２次記憶間の往復の転送に
要する時間は２８秒以上かかる。仮想記憶の導入により
半導体メモリをより安価な磁気ディスクに置き換えるこ
とでコストは改善されるが処理速度が低下するという別
の問題が発生する。
【００４１】特開昭６２−１５４１５２、特開平７−１
２１６９０に開示される技術では、画像をブロックに分
割して小画像を作成し小画像毎に圧縮して磁気ディスク
に記憶し、処理に必要な部分を伸張して画素として主記
憶に格納する。これにより２次記憶との間のデータ転送
量を減すことが可能になるが、新たな画像領域が主記憶
に無く、かつ、主記憶にその領域をロードする空き領域
が無い場合には、まず現在使用中の領域の一つを選び、
選ばれた領域を圧縮し、圧縮データを２次記憶に送るこ
とで主記憶に新たな画像領域のためのスペースを作り、
２次記憶より該領域の圧縮データを読み出し、それを伸
張して画像に戻し、それを主記憶の該エリアに書き込
む。その後、主記憶での画像領域不在により中断してい
た処理を再開する。したがって、画像の圧縮と伸張処理
をシーケンシャルに行わねばならない為、処理時間が長
くなるという問題が発生する。また、画像処理のシーケ
ンスによっては特定の小画像について圧縮／伸張を何度
も繰り返すケースも発生するため、その部分の画像は画
像の圧縮／伸張にともない画質が劣化する問題もある。
なぜならば画像を効率よく圧縮するためしばしば非可逆
圧縮が用いられるためである。
２１６９０に開示される技術では、画像をブロックに分
割して小画像を作成し小画像毎に圧縮して磁気ディスク
に記憶し、処理に必要な部分を伸張して画素として主記
憶に格納する。これにより２次記憶との間のデータ転送
量を減すことが可能になるが、新たな画像領域が主記憶
に無く、かつ、主記憶にその領域をロードする空き領域
が無い場合には、まず現在使用中の領域の一つを選び、
選ばれた領域を圧縮し、圧縮データを２次記憶に送るこ
とで主記憶に新たな画像領域のためのスペースを作り、
２次記憶より該領域の圧縮データを読み出し、それを伸
張して画像に戻し、それを主記憶の該エリアに書き込
む。その後、主記憶での画像領域不在により中断してい
た処理を再開する。したがって、画像の圧縮と伸張処理
をシーケンシャルに行わねばならない為、処理時間が長
くなるという問題が発生する。また、画像処理のシーケ
ンスによっては特定の小画像について圧縮／伸張を何度
も繰り返すケースも発生するため、その部分の画像は画
像の圧縮／伸張にともない画質が劣化する問題もある。
なぜならば画像を効率よく圧縮するためしばしば非可逆
圧縮が用いられるためである。
【００４２】今日のゼログラフィ技術を用いた画像出力
装置は、富士ゼロックス株式会社が製造販売するＤｏｃ
ｕ Ｃｏｌｏｒ ４０４０画像出力装置のように１秒に
４０枚のフルカラー出力が可能なものがある。このよう
な高速の画像出力装置を効率よく利用するためにはＰＤ
Ｌ処理側も１枚あたり１．５秒以下で処理を行うことが
望まれる。すなわちスキャンドイメージの描画も１．５
秒以下で処理する必要がある。
装置は、富士ゼロックス株式会社が製造販売するＤｏｃ
ｕ Ｃｏｌｏｒ ４０４０画像出力装置のように１秒に
４０枚のフルカラー出力が可能なものがある。このよう
な高速の画像出力装置を効率よく利用するためにはＰＤ
Ｌ処理側も１枚あたり１．５秒以下で処理を行うことが
望まれる。すなわちスキャンドイメージの描画も１．５
秒以下で処理する必要がある。
【００４３】ラスタは２次元構造を持った画素の集合体
であるが、計算機システムのメモリは１次元構造を取っ
ている。そこで、ラスタをメモリに格納する際には、通
常、主走査方向に１行分の画素をメモリの連続する場所
に格納し、そこに連続する場所に次の行の画素を１行分
格納し、それ以降の行も同様に格納する。このため、あ
る画素（ただし画像の左右両端を除く）の左右にある画
素はメモリ上でも隣接するアドレスに格納されるが、あ
る画素の上下にある画素は画素１行分に相当するアドレ
ス（これをＡＷとする）離れた場所に格納される。解像
度６００ＳＰＩのＡ４サイズの画像では１行は約５００
０画素（横長配置の場合）あるいは約７０００画素（縦
長配置の場合）となる。従って１画素を４Ｂｙｔｅとす
るとＡＷは縦置きの場合約２００００Ｂｙｔｅ相当、横
置きの場合約２８０００Ｂｙｔｅ相当となる。
であるが、計算機システムのメモリは１次元構造を取っ
ている。そこで、ラスタをメモリに格納する際には、通
常、主走査方向に１行分の画素をメモリの連続する場所
に格納し、そこに連続する場所に次の行の画素を１行分
格納し、それ以降の行も同様に格納する。このため、あ
る画素（ただし画像の左右両端を除く）の左右にある画
素はメモリ上でも隣接するアドレスに格納されるが、あ
る画素の上下にある画素は画素１行分に相当するアドレ
ス（これをＡＷとする）離れた場所に格納される。解像
度６００ＳＰＩのＡ４サイズの画像では１行は約５００
０画素（横長配置の場合）あるいは約７０００画素（縦
長配置の場合）となる。従って１画素を４Ｂｙｔｅとす
るとＡＷは縦置きの場合約２００００Ｂｙｔｅ相当、横
置きの場合約２８０００Ｂｙｔｅ相当となる。
【００４４】±９０°回転のアフィン変換は、ｙ軸方向
に順次画素を読み出しｘ軸方向に画素を書き込むあるい
は出力することで実現できる。メモリからの画素の読み
出しはアドレスＡＷ分のとびとびの場所に発生する。
に順次画素を読み出しｘ軸方向に画素を書き込むあるい
は出力することで実現できる。メモリからの画素の読み
出しはアドレスＡＷ分のとびとびの場所に発生する。
【００４５】±Ｎ×１８０°（Ｎは整数）を除く任意の
角度の回転を伴うアフィン変換では、ソース画像上で走
査線に沿って画素を読み出し座標変換後のデバイス画像
に格納する場合の書き込み先アドレス、あるいはデバイ
ス画像上で走査線に沿った画素を逆変換を用いてソース
画像から読み出す場合の読み出し先アドレスは、メモリ
上ではとびとびの場所に発生する。書き込み先アドレス
あるいは読み出し先アドレス距離は角度に依存するがお
おむねＡＷのオーダーである。
角度の回転を伴うアフィン変換では、ソース画像上で走
査線に沿って画素を読み出し座標変換後のデバイス画像
に格納する場合の書き込み先アドレス、あるいはデバイ
ス画像上で走査線に沿った画素を逆変換を用いてソース
画像から読み出す場合の読み出し先アドレスは、メモリ
上ではとびとびの場所に発生する。書き込み先アドレス
あるいは読み出し先アドレス距離は角度に依存するがお
おむねＡＷのオーダーである。
【００４６】今日の高性能計算機のＣＰＵは３００ＭＨ
ｚ以上すなわちサイクルタイム３．３ｎｓ以下で動作
し、複数（２〜３）命令を１サイクルで実行することが
できる。このようなＣＰＵでは約１サイクルに１回メモ
リアクセス命令を実行することになる。一方メインメモ
リを構成するＤＲＡＭのロウ・アドレス・サイクルタイ
ムは１００ｎｓ程度、カラム・アドレス・アクセスタイ
ムは高速ページモードのＤＲＡＭで４０ｎｓ程度、ＥＤ
Ｏ（Ｅｘｔｅｎｄｅｄ Ｄａｔａ Ｏｕｔｐｕｔ）モー
ドのＤＲＡＭで２５ｎｓ程度、Ｓｙｎｃｈｒｏｍｏｕｓ
ＤＲＡＭの場合１０ｎｓ程度である。ＣＰＵのメモリ
アクセスレートとＤＲＡＭのレートとの間には大きな開
きがあり、ＣＰＵがいくら高速でもＤＲＡＭのアクセス
時には待ちが発生し処理速度は大幅に低下してしまう。
この問題を解決するために今日の計算機ではキャッシュ
メモリを用いた階層化記憶機構を採用している。キャッ
シュメモリの一般原理についてはＪｏｈｎ Ｌ．Ｈｅｎ
ｎｅｓｓｙ ＆ ＤａｖｉｄＡ．Ｐａｔｔｅｒｓｏｎ両
氏によるテキストブック“Ｃｏｍｐｕｔｅｒ Ａｒｃｈ
ｉｔｅｃｔｕｒｅ Ａ Ｑｕａｎｔｉｔａｔｉｖｅ Ａ
ｐｐｒｏａｃｈ”，Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ；１
９９６；Ｍｏｒｇａｎ ＫａｕｆｍａｎｎＰｕｂｌｉｓ
ｈｅｒｓ，Ｉｎｃ．の５．２章に記載されているので説
明を省略するが、一般にＣＰＵのメモリアクセスパター
ンには、ある時刻にアクセスしたメモリ・ロケーション
をその後アクセスする確率は高いという時間的局所性
と、あるメモリロケーションをアクセスしたらその近傍
をアクセスする確率は高いという空間的局所性がある。
一方、半導体メモリには、小容量のメモリはアクセスタ
イムが小さいすなわち速いが、大容量のメモリはアクセ
スタイムが大きいすなわち遅いという性質がある。ＣＰ
ＵとＤＲＡＭの間に小容量の高速メモリを１層もしくは
複数層に配置し、ＣＰＵが参照するデータを小容量高速
メモリに置くよう制御する。この小容量高速メモリをキ
ャッシュメモリと呼ぶ。ＣＰＵがアクセスを要求するデ
ータがキャッシュメモリにあればキャッシュメモリから
データを供給する。データがキャッシュメモリに無い場
合はＤＲＡＭで構成されるメインメモリを読み、ＣＰＵ
が読み出し要求した語とその近傍の語からなるブロック
をまとめてキャッシュメモリに書き込み、ＣＰＵへ読み
出した語を返す。今日の高性能計算機ではＣＰＵチップ
上にＣＰＵと同じクロックで動作する１’ｓｔキャッシ
ュメモリを設け、チップ外にＣＰＵよりも遅いクロック
で動作する２’ｎｄキャッシュを設けることが多い。
１’ｓｔキャッシュのサイズは１６ＫＢｙｔｅ〜６４Ｋ
Ｂｙｔｅ程度、２’ｎｄキャッシュは１’ｓｔキャッシ
ュよりも大きく２５６ＫＢｙｔｅ〜１ＭＢｙｔｅ程度で
ある。
ｚ以上すなわちサイクルタイム３．３ｎｓ以下で動作
し、複数（２〜３）命令を１サイクルで実行することが
できる。このようなＣＰＵでは約１サイクルに１回メモ
リアクセス命令を実行することになる。一方メインメモ
リを構成するＤＲＡＭのロウ・アドレス・サイクルタイ
ムは１００ｎｓ程度、カラム・アドレス・アクセスタイ
ムは高速ページモードのＤＲＡＭで４０ｎｓ程度、ＥＤ
Ｏ（Ｅｘｔｅｎｄｅｄ Ｄａｔａ Ｏｕｔｐｕｔ）モー
ドのＤＲＡＭで２５ｎｓ程度、Ｓｙｎｃｈｒｏｍｏｕｓ
ＤＲＡＭの場合１０ｎｓ程度である。ＣＰＵのメモリ
アクセスレートとＤＲＡＭのレートとの間には大きな開
きがあり、ＣＰＵがいくら高速でもＤＲＡＭのアクセス
時には待ちが発生し処理速度は大幅に低下してしまう。
この問題を解決するために今日の計算機ではキャッシュ
メモリを用いた階層化記憶機構を採用している。キャッ
シュメモリの一般原理についてはＪｏｈｎ Ｌ．Ｈｅｎ
ｎｅｓｓｙ ＆ ＤａｖｉｄＡ．Ｐａｔｔｅｒｓｏｎ両
氏によるテキストブック“Ｃｏｍｐｕｔｅｒ Ａｒｃｈ
ｉｔｅｃｔｕｒｅ Ａ Ｑｕａｎｔｉｔａｔｉｖｅ Ａ
ｐｐｒｏａｃｈ”，Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ；１
９９６；Ｍｏｒｇａｎ ＫａｕｆｍａｎｎＰｕｂｌｉｓ
ｈｅｒｓ，Ｉｎｃ．の５．２章に記載されているので説
明を省略するが、一般にＣＰＵのメモリアクセスパター
ンには、ある時刻にアクセスしたメモリ・ロケーション
をその後アクセスする確率は高いという時間的局所性
と、あるメモリロケーションをアクセスしたらその近傍
をアクセスする確率は高いという空間的局所性がある。
一方、半導体メモリには、小容量のメモリはアクセスタ
イムが小さいすなわち速いが、大容量のメモリはアクセ
スタイムが大きいすなわち遅いという性質がある。ＣＰ
ＵとＤＲＡＭの間に小容量の高速メモリを１層もしくは
複数層に配置し、ＣＰＵが参照するデータを小容量高速
メモリに置くよう制御する。この小容量高速メモリをキ
ャッシュメモリと呼ぶ。ＣＰＵがアクセスを要求するデ
ータがキャッシュメモリにあればキャッシュメモリから
データを供給する。データがキャッシュメモリに無い場
合はＤＲＡＭで構成されるメインメモリを読み、ＣＰＵ
が読み出し要求した語とその近傍の語からなるブロック
をまとめてキャッシュメモリに書き込み、ＣＰＵへ読み
出した語を返す。今日の高性能計算機ではＣＰＵチップ
上にＣＰＵと同じクロックで動作する１’ｓｔキャッシ
ュメモリを設け、チップ外にＣＰＵよりも遅いクロック
で動作する２’ｎｄキャッシュを設けることが多い。
１’ｓｔキャッシュのサイズは１６ＫＢｙｔｅ〜６４Ｋ
Ｂｙｔｅ程度、２’ｎｄキャッシュは１’ｓｔキャッシ
ュよりも大きく２５６ＫＢｙｔｅ〜１ＭＢｙｔｅ程度で
ある。
【００４７】回転を伴うアフィン変換の逆サンプリング
におけるキャッシュメモリの動作を説明する。ここでは
回転角を９０°とする。この場合１デバイス画素毎にソ
ース座標上をΔｘ＝０，Δｙ＝１移動して画素を逆サン
プリングする。ある画素の逆サンプリングの際には以下
に示す動作が生じる。その画素はそれ以前にアクセスさ
れていないのでキャッシュミスが発生し、メインメモリ
のＤＲＡＭに読み出しが発生し、その間ＣＰＵは停止す
る。キャッシュの制御システムは該画素と隣接アドレス
に格納されているその左右（ｘ軸方向）の画素も読み出
しキャッシュメモリに格納する。ＣＰＵは次の画素（デ
バイス空間上での右隣り）の逆サンプリングとしてソー
ス空間上１行下の画素をアクセスする。その画素はまだ
キャッシュに格納されていないので再びキャッシュミス
が発生し、ＣＰＵはＤＲＡＭからの読み出しを待つ。デ
バイス空間の走査線上を逆サンプリングする過程ではこ
のように全画素のアクセスにおいてキャッシュがミス
し、ＣＰＵはＤＲＡＭの動作を待つことになる。ＣＰＵ
は次いでデバイス空間上１行下の走査線の逆サンプリン
グを行う。この場合の逆サンプリング先の画素は上行の
走査線の画素の逆サンプリングの際にキャッシュメモリ
に格納された。しかし、キャッシュメモリのサイズは有
限であり、１走査線上の画素は通常キャシュのエントリ
数（ブロックの数）よりも多いため、一旦キャッシュに
格納された画素はその後のキャッシュミスによりキャッ
シュメモリから追い出されてしまいこの時点ではキャッ
シュに存在しない。従って、再びキャッシュミスが発生
する。この走査線上の画素全てに同様なキャッシュミス
が発生し、逆サンプリングの度にＤＲＡＭから画素を読
むことになる。以上述べたことは全走査線に発生し、Ｃ
ＰＵはキャッシュから直ちに画素値を受け取れず、遅い
ＤＲＡＭを待って処理を進めることになる。１走査線分
に相当するアドレス上の距離ではＤＲＡＭはカラムアド
レスのみを変える高速モードが使えるアドレス範囲を越
えている為ＤＲＡＭアクセス毎にロウアドレスを新たに
あたえねばならない。その場合のＤＲＡＭの動作速度は
たかだか１０ＭＨｚ程度である。ＣＰＵは３００ＭＨｚ
のクロックで動作可能だが逆サンプリング過程ではキャ
ッシュメモリが全く働かないため、実質１０ＭＨｚのＤ
ＲＡＭの動作スピードで全体の処理がすすむ。
におけるキャッシュメモリの動作を説明する。ここでは
回転角を９０°とする。この場合１デバイス画素毎にソ
ース座標上をΔｘ＝０，Δｙ＝１移動して画素を逆サン
プリングする。ある画素の逆サンプリングの際には以下
に示す動作が生じる。その画素はそれ以前にアクセスさ
れていないのでキャッシュミスが発生し、メインメモリ
のＤＲＡＭに読み出しが発生し、その間ＣＰＵは停止す
る。キャッシュの制御システムは該画素と隣接アドレス
に格納されているその左右（ｘ軸方向）の画素も読み出
しキャッシュメモリに格納する。ＣＰＵは次の画素（デ
バイス空間上での右隣り）の逆サンプリングとしてソー
ス空間上１行下の画素をアクセスする。その画素はまだ
キャッシュに格納されていないので再びキャッシュミス
が発生し、ＣＰＵはＤＲＡＭからの読み出しを待つ。デ
バイス空間の走査線上を逆サンプリングする過程ではこ
のように全画素のアクセスにおいてキャッシュがミス
し、ＣＰＵはＤＲＡＭの動作を待つことになる。ＣＰＵ
は次いでデバイス空間上１行下の走査線の逆サンプリン
グを行う。この場合の逆サンプリング先の画素は上行の
走査線の画素の逆サンプリングの際にキャッシュメモリ
に格納された。しかし、キャッシュメモリのサイズは有
限であり、１走査線上の画素は通常キャシュのエントリ
数（ブロックの数）よりも多いため、一旦キャッシュに
格納された画素はその後のキャッシュミスによりキャッ
シュメモリから追い出されてしまいこの時点ではキャッ
シュに存在しない。従って、再びキャッシュミスが発生
する。この走査線上の画素全てに同様なキャッシュミス
が発生し、逆サンプリングの度にＤＲＡＭから画素を読
むことになる。以上述べたことは全走査線に発生し、Ｃ
ＰＵはキャッシュから直ちに画素値を受け取れず、遅い
ＤＲＡＭを待って処理を進めることになる。１走査線分
に相当するアドレス上の距離ではＤＲＡＭはカラムアド
レスのみを変える高速モードが使えるアドレス範囲を越
えている為ＤＲＡＭアクセス毎にロウアドレスを新たに
あたえねばならない。その場合のＤＲＡＭの動作速度は
たかだか１０ＭＨｚ程度である。ＣＰＵは３００ＭＨｚ
のクロックで動作可能だが逆サンプリング過程ではキャ
ッシュメモリが全く働かないため、実質１０ＭＨｚのＤ
ＲＡＭの動作スピードで全体の処理がすすむ。
【００４８】以上述べたケースはＣＰＵのキャシュメモ
リが作用できない特別なケースではない。Δｙ≠０のと
きにはメインメモリ上のとびとびのメモリロケーション
にアクセスが発生するので同様にキャッシュメモリの効
果は無い。唯一Δｙ＝０のときのみは連続するアドレス
方向にアクセスが発生するので、キャッシュメモリの先
読み効果（空間的局所性）が有効に作用する。しかし、
一般のプログラム実行時のキャッシュ動作に比較すると
キャッシュミスははるかに多い。
リが作用できない特別なケースではない。Δｙ≠０のと
きにはメインメモリ上のとびとびのメモリロケーション
にアクセスが発生するので同様にキャッシュメモリの効
果は無い。唯一Δｙ＝０のときのみは連続するアドレス
方向にアクセスが発生するので、キャッシュメモリの先
読み効果（空間的局所性）が有効に作用する。しかし、
一般のプログラム実行時のキャッシュ動作に比較すると
キャッシュミスははるかに多い。
【００４９】解像度６００ＳＰＩ，Ａ４サイズの画像で
は、逆サンプリングのキャッシュミスに伴う３５×１０
6回のメインメモリへの読み出しが発生する。ＤＲＡＭ
のロウ・アドレス・サイクルタイムは１００ｎｓ（ｍｉ
ｎ）程度なのでＤＲＡＭアクセスのみで合計３．４秒か
かる。ほかにＤＲＡＭのコントローラのオーバヘッド時
間とシステムバスのオーバーヘッド時間とがかかるので
ＣＰＵの待ち時間の総和は更に長くなる。ＣＰＵは他の
処理のためにも時間を要する。したがって画像出力装置
に見合った性能すなわち１．５秒／枚で画像を処理でき
ない。ＤＲＡＭのアクセスがボトルネックとなっている
のでマルチプロセッサ技術を用いてＣＰＵの数を増やし
ても改善できない。
は、逆サンプリングのキャッシュミスに伴う３５×１０
6回のメインメモリへの読み出しが発生する。ＤＲＡＭ
のロウ・アドレス・サイクルタイムは１００ｎｓ（ｍｉ
ｎ）程度なのでＤＲＡＭアクセスのみで合計３．４秒か
かる。ほかにＤＲＡＭのコントローラのオーバヘッド時
間とシステムバスのオーバーヘッド時間とがかかるので
ＣＰＵの待ち時間の総和は更に長くなる。ＣＰＵは他の
処理のためにも時間を要する。したがって画像出力装置
に見合った性能すなわち１．５秒／枚で画像を処理でき
ない。ＤＲＡＭのアクセスがボトルネックとなっている
のでマルチプロセッサ技術を用いてＣＰＵの数を増やし
ても改善できない。
【００５０】
【課題を解決するための手段】上述したような従来技術
の有する様々な課題を解決するために、本発明のラスタ
画像生成装置およびラスタ画像生成方法は、以下に説明
するような構成を有することを特徴とする。
の有する様々な課題を解決するために、本発明のラスタ
画像生成装置およびラスタ画像生成方法は、以下に説明
するような構成を有することを特徴とする。
【００５１】本発明のラスタ画像生成方法は、ラスタ画
像を複数の部分画像に分割する画像分割ステップと、画
像分割ステップにおいて得られた部分画像を符号化し該
部分画像の符号を得る符号化ステップと、符号化ステッ
プにおいて得られた部分画像の符号の復号順を決定する
復号順決定ステップと、復号順決定ステップにおいて決
定された順番に従って、部分画像の符号を復号し、部分
画像をメモリ手段に格納する復号ステップと、第１の座
標空間で表現された幾何情報を第２の座標空間に変換す
る座標空間変換ステップと、第２の座標空間での幾何位
置に対応するメモリ手段上のアドレスを生成するアドレ
ス生成ステップと、アドレス生成ステップにおいて生成
されたアドレスを用いてメモリ手段を読み出すステップ
とを有することを特徴とする。
像を複数の部分画像に分割する画像分割ステップと、画
像分割ステップにおいて得られた部分画像を符号化し該
部分画像の符号を得る符号化ステップと、符号化ステッ
プにおいて得られた部分画像の符号の復号順を決定する
復号順決定ステップと、復号順決定ステップにおいて決
定された順番に従って、部分画像の符号を復号し、部分
画像をメモリ手段に格納する復号ステップと、第１の座
標空間で表現された幾何情報を第２の座標空間に変換す
る座標空間変換ステップと、第２の座標空間での幾何位
置に対応するメモリ手段上のアドレスを生成するアドレ
ス生成ステップと、アドレス生成ステップにおいて生成
されたアドレスを用いてメモリ手段を読み出すステップ
とを有することを特徴とする。
【００５２】また、本発明のラスタ画像生成方法におい
て、第１の座標空間はデバイス空間であり、第２の座標
空間はソース空間であって、座標空間変換ステップは、
デバイス空間上でのスキャンドイメージの描画幾何形状
を形成するラスタスキャン情報をソース空間へ逆変換
し、ソース空間での幾何情報すなわちラスタスキャン情
報を得るステップであり、アドレス生成ステップは、座
標空間変換ステップにおいて得たソース空間上でのラス
タスキャン情報を用いてデバイス空間のスキャンドイメ
ージの画素に対応するメモリ手段上の部分画像の画素の
アドレス情報を生成するステップであり、該アドレス情
報を用いて順にメモリ手段から画素を読み出してデバイ
ス空間でのスキャンドイメージの画素を順に獲得する構
成を有することを特徴とする。
て、第１の座標空間はデバイス空間であり、第２の座標
空間はソース空間であって、座標空間変換ステップは、
デバイス空間上でのスキャンドイメージの描画幾何形状
を形成するラスタスキャン情報をソース空間へ逆変換
し、ソース空間での幾何情報すなわちラスタスキャン情
報を得るステップであり、アドレス生成ステップは、座
標空間変換ステップにおいて得たソース空間上でのラス
タスキャン情報を用いてデバイス空間のスキャンドイメ
ージの画素に対応するメモリ手段上の部分画像の画素の
アドレス情報を生成するステップであり、該アドレス情
報を用いて順にメモリ手段から画素を読み出してデバイ
ス空間でのスキャンドイメージの画素を順に獲得する構
成を有することを特徴とする。
【００５３】また、本発明のラスタ画像生成方法は、さ
らに画像分割ステップにおいて得られた部分画像と、ラ
スタ画像生成装置に入力される描画情報から得られる幾
何形状との重なり合いを調べる重なり検出ステップと、
重なり検出ステップでの重なり検出結果に応じて、デバ
イス画像の描画に寄与する部分画像を選択する部分画像
選択ステップとを有し、符号化ステップは、部分画像選
択ステップにおいて選択された部分画像についてのみ符
号化し部分画像の符号を得るステップであることを特徴
とする。
らに画像分割ステップにおいて得られた部分画像と、ラ
スタ画像生成装置に入力される描画情報から得られる幾
何形状との重なり合いを調べる重なり検出ステップと、
重なり検出ステップでの重なり検出結果に応じて、デバ
イス画像の描画に寄与する部分画像を選択する部分画像
選択ステップとを有し、符号化ステップは、部分画像選
択ステップにおいて選択された部分画像についてのみ符
号化し部分画像の符号を得るステップであることを特徴
とする。
【００５４】また、本発明のラスタ画像生成方法におい
て、重なり検出ステップは、描画情報からスキャンドイ
メージの輪郭情報を読み出し、読み出されたスキャンド
イメージの描画の際に指定されたアフィン変換の逆変換
を実行して、輪郭情報をスキャンドイメージのソース空
間に写像し、該写像されたソース空間の輪郭の内側部分
あるいは該輪郭上に重なる部分画像の領域を検出するス
テップであることを特徴とする。
て、重なり検出ステップは、描画情報からスキャンドイ
メージの輪郭情報を読み出し、読み出されたスキャンド
イメージの描画の際に指定されたアフィン変換の逆変換
を実行して、輪郭情報をスキャンドイメージのソース空
間に写像し、該写像されたソース空間の輪郭の内側部分
あるいは該輪郭上に重なる部分画像の領域を検出するス
テップであることを特徴とする。
【００５５】さらに、本発明のラスタ画像生成方法は、
ラスタ画像の縮小を実行して縮小ラスタ画像を生成する
縮小ラスタ画像生成ステップを有し、画像分割ステップ
は、該縮小ラスタ画像生成ステップにおいて生成された
縮小ラスタ画像について部分画像への分割を実行するこ
とを特徴とする。
ラスタ画像の縮小を実行して縮小ラスタ画像を生成する
縮小ラスタ画像生成ステップを有し、画像分割ステップ
は、該縮小ラスタ画像生成ステップにおいて生成された
縮小ラスタ画像について部分画像への分割を実行するこ
とを特徴とする。
【００５６】また、本発明のラスタ画像生成装置は、ラ
スタ画像を複数の部分画像に分割する画像分割手段と、
画像分割手段によって生成された部分画像を符号化し部
分画像の符号を得る符号化手段と、符号化手段によって
生成された部分画像の符号を復号しメモリ手段に格納す
る復号手段と、第１の座標空間で表現された幾何情報を
第２の座標空間に変換する座標空間変換手段と、第２の
座標空間での幾何位置に対応するメモリ手段上のアドレ
スを生成するアドレス変換手段と、符号化手段によって
生成された部分画像の符号を復号する復号順を決定する
復号順決定手段とを備え、復号順決定手段により決定し
た復号順に従って復号された部分画像をメモリ手段に格
納し、第１の座標空間の幾何情報を座標変換手段に与え
その出力をアドレス変換手段に供給して得たメモリアド
レスを用いてメモリ手段に格納された部分画像の画素を
読み出す構成を有することを特徴とする。
スタ画像を複数の部分画像に分割する画像分割手段と、
画像分割手段によって生成された部分画像を符号化し部
分画像の符号を得る符号化手段と、符号化手段によって
生成された部分画像の符号を復号しメモリ手段に格納す
る復号手段と、第１の座標空間で表現された幾何情報を
第２の座標空間に変換する座標空間変換手段と、第２の
座標空間での幾何位置に対応するメモリ手段上のアドレ
スを生成するアドレス変換手段と、符号化手段によって
生成された部分画像の符号を復号する復号順を決定する
復号順決定手段とを備え、復号順決定手段により決定し
た復号順に従って復号された部分画像をメモリ手段に格
納し、第１の座標空間の幾何情報を座標変換手段に与え
その出力をアドレス変換手段に供給して得たメモリアド
レスを用いてメモリ手段に格納された部分画像の画素を
読み出す構成を有することを特徴とする。
【００５７】また、本発明のラスタ画像生成装置におい
て、第１の座標空間はデバイス空間であり、第２の座標
空間はソース空間であって、座標空間変換手段は、デバ
イス空間上でのスキャンドイメージの描画幾何形状を形
成するラスタスキャン情報をソース空間へ逆変換し、ソ
ース空間での幾何情報すなわちラスタスキャン情報を得
る手段であり、アドレス変換手段は、座標空間変換手段
において得たソース空間上でのラスタスキャン情報を用
いてデバイス空間のスキャンドイメージの画素に対応す
るメモリ手段上の部分画像の画素のアドレス情報を生成
する手段であり、アドレス変換手段によって生成された
アドレス情報を用いて順にメモリ手段から画素を読み出
してデバイス空間でのスキャンドイメージの画素を順に
獲得する構成を有することを特徴とする。
て、第１の座標空間はデバイス空間であり、第２の座標
空間はソース空間であって、座標空間変換手段は、デバ
イス空間上でのスキャンドイメージの描画幾何形状を形
成するラスタスキャン情報をソース空間へ逆変換し、ソ
ース空間での幾何情報すなわちラスタスキャン情報を得
る手段であり、アドレス変換手段は、座標空間変換手段
において得たソース空間上でのラスタスキャン情報を用
いてデバイス空間のスキャンドイメージの画素に対応す
るメモリ手段上の部分画像の画素のアドレス情報を生成
する手段であり、アドレス変換手段によって生成された
アドレス情報を用いて順にメモリ手段から画素を読み出
してデバイス空間でのスキャンドイメージの画素を順に
獲得する構成を有することを特徴とする。
【００５８】また、本発明のラスタ画像生成装置は、さ
らに画像分割手段において生成された部分画像と、ラス
タ画像生成装置に入力される描画情報から得られる幾何
形状との重なり合いを検出する重なり検出手段を有し、
重なり検出手段での重なり検出結果に応じて、デバイス
画像の描画に寄与する部分画像を選択して、該選択され
た部分画像についてのみ符号化手段によって符号化し部
分画像の符号を得ることを特徴とする。
らに画像分割手段において生成された部分画像と、ラス
タ画像生成装置に入力される描画情報から得られる幾何
形状との重なり合いを検出する重なり検出手段を有し、
重なり検出手段での重なり検出結果に応じて、デバイス
画像の描画に寄与する部分画像を選択して、該選択され
た部分画像についてのみ符号化手段によって符号化し部
分画像の符号を得ることを特徴とする。
【００５９】さらに本発明のラスタ画像生成装置は、画
像分割手段において生成された部分画像と、ラスタ画像
生成装置に入力される描画情報から得られる幾何形状と
の重なり合いを検出する重なり検出手段を有し、重なり
検出手段での重なり検出結果に応じて部分画像を選択的
に分割手段で読み出して、該読み出された部分画像につ
いて符号化手段で符号化することを特徴とする。
像分割手段において生成された部分画像と、ラスタ画像
生成装置に入力される描画情報から得られる幾何形状と
の重なり合いを検出する重なり検出手段を有し、重なり
検出手段での重なり検出結果に応じて部分画像を選択的
に分割手段で読み出して、該読み出された部分画像につ
いて符号化手段で符号化することを特徴とする。
【００６０】さらに本発明のラスタ画像生成装置におい
て、重なり検出手段は、描画情報からスキャンドイメー
ジの輪郭情報を読み出し、読み出されたスキャンドイメ
ージの描画の際に指定されたアフィン変換の逆変換を実
行して、輪郭情報をスキャンドイメージのソース空間に
写像し、該写像されたソース空間の輪郭の内側部分ある
いは該輪郭上に重なる部分画像の領域を検出する構成を
有することを特徴とする。
て、重なり検出手段は、描画情報からスキャンドイメー
ジの輪郭情報を読み出し、読み出されたスキャンドイメ
ージの描画の際に指定されたアフィン変換の逆変換を実
行して、輪郭情報をスキャンドイメージのソース空間に
写像し、該写像されたソース空間の輪郭の内側部分ある
いは該輪郭上に重なる部分画像の領域を検出する構成を
有することを特徴とする。
【００６１】さらに本発明のラスタ画像生成装置は、ラ
スタ画像の縮小を実行して縮小ラスタ画像を生成する縮
小手段を有し、画像分割手段は、縮小手段において生成
された縮小ラスタ画像について部分画像への分割を実行
することを特徴とする。
スタ画像の縮小を実行して縮小ラスタ画像を生成する縮
小手段を有し、画像分割手段は、縮小手段において生成
された縮小ラスタ画像について部分画像への分割を実行
することを特徴とする。
【００６２】さらに本発明のラスタ画像生成装置は、復
号手段を用いて実行される部分画像の復号タイミング位
置と、座標変換手段において変換が実行される第１の座
標空間の変換タイミング位置とを同期させて動作する構
成としたことを特徴とする。
号手段を用いて実行される部分画像の復号タイミング位
置と、座標変換手段において変換が実行される第１の座
標空間の変換タイミング位置とを同期させて動作する構
成としたことを特徴とする。
【００６３】さらに本発明のラスタ画像生成装置は、ア
ドレス変換手段に第２の座標空間とメモリアドレスとを
関係づけるテーブルを持ち、該テーブルは、入力ラスタ
画像ごと、個々に独立したテーブルによって構成されて
いることを特徴とする。
ドレス変換手段に第２の座標空間とメモリアドレスとを
関係づけるテーブルを持ち、該テーブルは、入力ラスタ
画像ごと、個々に独立したテーブルによって構成されて
いることを特徴とする。
【００６４】請求項１、２および５に記載の発明では、
ソースラスタ画像をそのままあるいは縮小した上で複数
の所定の大きさの部分画像に分割する。ここで分割され
た部分画像を部分画像毎に符号化し、元の部分画像より
もデータ量が小さな符号を得る。符号をメモリ手段に格
納する。デバイス画像をラスタ順に走査した場合に前記
部分画像が走査上に出現する順番を調べ、その順を部分
画像符号の復号順とする。この復号順に従い、符号を復
号し部分画像を再生しメモリ手段の所定の場所に格納す
る。デバイス空間を第１の座標空間、ソース空間を第２
の座標空間とする。デバイス空間上でのスキャンドイメ
ージの描画幾何形状を形成するラスタスキャン情報をソ
ース空間へ逆変換し、ソース空間での幾何情報すなわち
ラスタスキャン情報を得る。ここで得たソース空間上で
のラスタスキャン情報を用いてデバイス空間のスキャン
ドイメージの画素に対応するメモリ手段上の部分画像の
画素のアドレス情報を生成する。このアドレス情報を用
いて順にメモリ手段より画素を読み出してデバイス空間
でのスキャンドイメージの画素を順に得る。
ソースラスタ画像をそのままあるいは縮小した上で複数
の所定の大きさの部分画像に分割する。ここで分割され
た部分画像を部分画像毎に符号化し、元の部分画像より
もデータ量が小さな符号を得る。符号をメモリ手段に格
納する。デバイス画像をラスタ順に走査した場合に前記
部分画像が走査上に出現する順番を調べ、その順を部分
画像符号の復号順とする。この復号順に従い、符号を復
号し部分画像を再生しメモリ手段の所定の場所に格納す
る。デバイス空間を第１の座標空間、ソース空間を第２
の座標空間とする。デバイス空間上でのスキャンドイメ
ージの描画幾何形状を形成するラスタスキャン情報をソ
ース空間へ逆変換し、ソース空間での幾何情報すなわち
ラスタスキャン情報を得る。ここで得たソース空間上で
のラスタスキャン情報を用いてデバイス空間のスキャン
ドイメージの画素に対応するメモリ手段上の部分画像の
画素のアドレス情報を生成する。このアドレス情報を用
いて順にメモリ手段より画素を読み出してデバイス空間
でのスキャンドイメージの画素を順に得る。
【００６５】請求項３、４および５の発明では、ソース
ラスタ画像をそのままあるいは縮小した上で複数の所定
の大きさの部分画像に分割する。ソース画像がデバイス
空間上で描画される部分の幾何形状を求め、この幾何形
状と部分画像とが重なり合う関係にあるか否かを調べ
る。重なり合い関係にある部分画像についてはそれらを
部分画像毎に符号化し、元の部分画像よりもデータ量が
小さな符号を得る。符号をメモリ手段に格納する。デバ
イス画像をラスタ順に走査した場合に前記部分画像が走
査上に出現する順番を調べ、その順を部分画像符号の復
号順とする。この復号順に従い、符号を復号し部分画像
を再生しメモリ手段の所定の場所に格納する。デバイス
空間を第１の座標空間、ソース空間を第２の座標空間と
する。デバイス空間上でのスキャンドイメージの描画幾
何形状を形成するラスタスキャン情報をソース空間へ逆
変換し、ソース空間での幾何情報すなわちラスタスキャ
ン情報を得る。ここで得たソース空間上でのラスタスキ
ャン情報を用いてデバイス空間のスキャンドイメージの
画素に対応するメモリ手段上の部分画像の画素のアドレ
ス情報を生成する。このアドレス情報を用いて順にメモ
リ手段より画素を読み出してデバイス空間でのスキャン
ドイメージの画素を順に得る。
ラスタ画像をそのままあるいは縮小した上で複数の所定
の大きさの部分画像に分割する。ソース画像がデバイス
空間上で描画される部分の幾何形状を求め、この幾何形
状と部分画像とが重なり合う関係にあるか否かを調べ
る。重なり合い関係にある部分画像についてはそれらを
部分画像毎に符号化し、元の部分画像よりもデータ量が
小さな符号を得る。符号をメモリ手段に格納する。デバ
イス画像をラスタ順に走査した場合に前記部分画像が走
査上に出現する順番を調べ、その順を部分画像符号の復
号順とする。この復号順に従い、符号を復号し部分画像
を再生しメモリ手段の所定の場所に格納する。デバイス
空間を第１の座標空間、ソース空間を第２の座標空間と
する。デバイス空間上でのスキャンドイメージの描画幾
何形状を形成するラスタスキャン情報をソース空間へ逆
変換し、ソース空間での幾何情報すなわちラスタスキャ
ン情報を得る。ここで得たソース空間上でのラスタスキ
ャン情報を用いてデバイス空間のスキャンドイメージの
画素に対応するメモリ手段上の部分画像の画素のアドレ
ス情報を生成する。このアドレス情報を用いて順にメモ
リ手段より画素を読み出してデバイス空間でのスキャン
ドイメージの画素を順に得る。
【００６６】請求項６，７および１１に記載の発明で
は、ソース空間のラスタ画像を分割手段を用いてそのま
まあるいは所定の縮小率で縮小した上で、所定の大きさ
の複数の部分画像に分割する。各々の部分画像を符号化
手段に供給し部分画像の符号を得る。符号化することで
データ量を小さくする。部分画像の符号をメモリ手段に
格納する。復号順決定手段はデバイス画像をラスタ順に
走査した場合に前記部分画像が走査上に出現する順番を
調べ、その順を部分画像符号の復号順とする。復号手段
は復号順決定手段が決定した復号順に従って、部分画像
の符号を復号し部分画像を作る。その部分画像はメモリ
手段の所定の場所に格納される。デバイス空間を第１の
座標空間、ソース空間を第２の座標空間とする。座標変
換手段は、デバイス空間で表現されたスキャンドイメー
ジの描画幾何形状を形成するラスタスキャン情報を入力
し、ソース空間へ逆変換し、ソース空間での幾何情報す
なわちラスタスキャン情報を出力する。アドレス生成手
段は、ソース空間でのラスタスキャン情報を入力し、デ
バイス空間のスキャンドイメージの画素に対応するメモ
リ手段上の部分画像の画素のアドレス情報を生成する。
このアドレス情報を用いてメモリ手段に格納された部分
画像の画素を順次読み出すことで、デバイス画像のスキ
ャンドイメージ部の画素を得る。
は、ソース空間のラスタ画像を分割手段を用いてそのま
まあるいは所定の縮小率で縮小した上で、所定の大きさ
の複数の部分画像に分割する。各々の部分画像を符号化
手段に供給し部分画像の符号を得る。符号化することで
データ量を小さくする。部分画像の符号をメモリ手段に
格納する。復号順決定手段はデバイス画像をラスタ順に
走査した場合に前記部分画像が走査上に出現する順番を
調べ、その順を部分画像符号の復号順とする。復号手段
は復号順決定手段が決定した復号順に従って、部分画像
の符号を復号し部分画像を作る。その部分画像はメモリ
手段の所定の場所に格納される。デバイス空間を第１の
座標空間、ソース空間を第２の座標空間とする。座標変
換手段は、デバイス空間で表現されたスキャンドイメー
ジの描画幾何形状を形成するラスタスキャン情報を入力
し、ソース空間へ逆変換し、ソース空間での幾何情報す
なわちラスタスキャン情報を出力する。アドレス生成手
段は、ソース空間でのラスタスキャン情報を入力し、デ
バイス空間のスキャンドイメージの画素に対応するメモ
リ手段上の部分画像の画素のアドレス情報を生成する。
このアドレス情報を用いてメモリ手段に格納された部分
画像の画素を順次読み出すことで、デバイス画像のスキ
ャンドイメージ部の画素を得る。
【００６７】請求項８、１０および１１の発明では、ソ
ース空間のラスタ画像を分割手段を用いてそのままある
いは所定の縮小率で縮小した上で、所定の大きさの複数
の部分画像に分割する。重なり検出手段は、ソース画像
がデバイス空間上で描画される部分の幾何形状を求め、
この幾何形状と部分画像とが重なり合う関係にあるか否
かを調べる。符号化手段は、重なり検出手段で重なり合
いを検出した部分画像について、各々の部分画像を入力
し符号化を行い部分画像の符号を得る。符号化すること
でデータ量を小さくする。部分画像の符号をメモリ手段
に格納する。復号順決定手段はデバイス画像をラスタ順
に走査した場合に前記部分画像が走査上に出現する順番
を調べ、その順を部分画像符号の復号順とする。復号手
段は復号順決定手段が決定した復号順に従って、部分画
像の符号を復号し部分画像を作る。その部分画像はメモ
リ手段の所定の場所に格納される。デバイス空間を第１
の座標空間、ソース空間を第２の座標空間とする。座標
変換手段は、デバイス空間で表現されたスキャンドイメ
ージの描画幾何形状を形成するラスタスキャン情報を入
力し、ソース空間へ逆変換し、ソース空間での幾何情報
すなわちラスタスキャン情報を出力する。アドレス生成
手段は、ソース空間でのラスタスキャン情報を入力し、
デバイス空間のスキャンドイメージの画素に対応するメ
モリ手段上の部分画像の画素のアドレス情報を生成す
る。このアドレス情報を用いてメモリ手段に格納された
部分画像の画素を順次読み出すことで、デバイス画像の
スキャンドイメージ部の画素を得る。
ース空間のラスタ画像を分割手段を用いてそのままある
いは所定の縮小率で縮小した上で、所定の大きさの複数
の部分画像に分割する。重なり検出手段は、ソース画像
がデバイス空間上で描画される部分の幾何形状を求め、
この幾何形状と部分画像とが重なり合う関係にあるか否
かを調べる。符号化手段は、重なり検出手段で重なり合
いを検出した部分画像について、各々の部分画像を入力
し符号化を行い部分画像の符号を得る。符号化すること
でデータ量を小さくする。部分画像の符号をメモリ手段
に格納する。復号順決定手段はデバイス画像をラスタ順
に走査した場合に前記部分画像が走査上に出現する順番
を調べ、その順を部分画像符号の復号順とする。復号手
段は復号順決定手段が決定した復号順に従って、部分画
像の符号を復号し部分画像を作る。その部分画像はメモ
リ手段の所定の場所に格納される。デバイス空間を第１
の座標空間、ソース空間を第２の座標空間とする。座標
変換手段は、デバイス空間で表現されたスキャンドイメ
ージの描画幾何形状を形成するラスタスキャン情報を入
力し、ソース空間へ逆変換し、ソース空間での幾何情報
すなわちラスタスキャン情報を出力する。アドレス生成
手段は、ソース空間でのラスタスキャン情報を入力し、
デバイス空間のスキャンドイメージの画素に対応するメ
モリ手段上の部分画像の画素のアドレス情報を生成す
る。このアドレス情報を用いてメモリ手段に格納された
部分画像の画素を順次読み出すことで、デバイス画像の
スキャンドイメージ部の画素を得る。
【００６８】請求項９、１０および１１の発明では、ソ
ース空間のラスタ画像を分割手段を用いてそのままある
いは所定の縮小率で縮小した上で、所定の大きさの複数
の部分画像に分割する。重なり検出手段は、ソース画像
がデバイス空間上で描画される部分の幾何形状を求め、
この幾何形状と部分画像とが重なり合う関係にあるか否
かを調べる。分割手段は、重なり検出手段で重なりを検
出した部分画像について部分画像作り、部分画像を符号
化手段へ出力する。符号化手段は、各々の部分画像を入
力し符号化を行い部分画像の符号を得る。符号化するこ
とでデータ量を小さくする。部分画像の符号をメモリ手
段に格納する。復号順決定手段はデバイス画像をラスタ
順に走査した場合に前記部分画像が走査上に出現する順
番を調べ、その順を部分画像符号の復号順とする。復号
手段は復号順決定手段が決定した復号順に従って、部分
画像の符号を復号し部分画像を作る。その部分画像はメ
モリ手段の所定の場所に格納される。デバイス空間を第
１の座標空間、ソース空間を第２の座標空間とする。座
標変換手段は、デバイス空間で表現されたスキャンドイ
メージの描画幾何形状を形成するラスタスキャン情報を
入力し、ソース空間へ逆変換し、ソース空間での幾何情
報すなわちラスタスキャン情報を出力する。アドレス生
成手段は、ソース空間でのラスタスキャン情報を入力
し、デバイス空間のスキャンドイメージの画素に対応す
るメモリ手段上の部分画像の画素のアドレス情報を生成
する。このアドレス情報を用いてメモリ手段に格納され
た部分画像の画素を順次読み出すことで、デバイス画像
のスキャンドイメージ部の画素を得る。
ース空間のラスタ画像を分割手段を用いてそのままある
いは所定の縮小率で縮小した上で、所定の大きさの複数
の部分画像に分割する。重なり検出手段は、ソース画像
がデバイス空間上で描画される部分の幾何形状を求め、
この幾何形状と部分画像とが重なり合う関係にあるか否
かを調べる。分割手段は、重なり検出手段で重なりを検
出した部分画像について部分画像作り、部分画像を符号
化手段へ出力する。符号化手段は、各々の部分画像を入
力し符号化を行い部分画像の符号を得る。符号化するこ
とでデータ量を小さくする。部分画像の符号をメモリ手
段に格納する。復号順決定手段はデバイス画像をラスタ
順に走査した場合に前記部分画像が走査上に出現する順
番を調べ、その順を部分画像符号の復号順とする。復号
手段は復号順決定手段が決定した復号順に従って、部分
画像の符号を復号し部分画像を作る。その部分画像はメ
モリ手段の所定の場所に格納される。デバイス空間を第
１の座標空間、ソース空間を第２の座標空間とする。座
標変換手段は、デバイス空間で表現されたスキャンドイ
メージの描画幾何形状を形成するラスタスキャン情報を
入力し、ソース空間へ逆変換し、ソース空間での幾何情
報すなわちラスタスキャン情報を出力する。アドレス生
成手段は、ソース空間でのラスタスキャン情報を入力
し、デバイス空間のスキャンドイメージの画素に対応す
るメモリ手段上の部分画像の画素のアドレス情報を生成
する。このアドレス情報を用いてメモリ手段に格納され
た部分画像の画素を順次読み出すことで、デバイス画像
のスキャンドイメージ部の画素を得る。
【００６９】請求項１２の発明では、復号手段が復号順
決定手段が決定した復号順に従って部分画像の符号を復
号し部分画像を復元しメモリ手段に格納するタイミング
と、第１の座標空間すなわちデバイス空間での描画情報
を走査線順に読み出し座標変換手段で第２の座標空間す
なわちソース空間へ逆変換し座標変換手段が更に該座標
値をメモリ手段の該アドレスに変換しメモリ手段をアク
セスする一連の処理のタイミングとを同期させる。
決定手段が決定した復号順に従って部分画像の符号を復
号し部分画像を復元しメモリ手段に格納するタイミング
と、第１の座標空間すなわちデバイス空間での描画情報
を走査線順に読み出し座標変換手段で第２の座標空間す
なわちソース空間へ逆変換し座標変換手段が更に該座標
値をメモリ手段の該アドレスに変換しメモリ手段をアク
セスする一連の処理のタイミングとを同期させる。
【００７０】請求項１３の発明では、アドレス変換手段
はソース画像毎に独立したアドレス変換テーブルを参照
して、第２の座標空間すなわちソース空間での該部分画
像位置からメモリ手段での該部分画像の格納場所を得
て、該画素のアドレスを計算し、該画素の値を得る。
はソース画像毎に独立したアドレス変換テーブルを参照
して、第２の座標空間すなわちソース空間での該部分画
像位置からメモリ手段での該部分画像の格納場所を得
て、該画素のアドレスを計算し、該画素の値を得る。
【００７１】
【発明の実施の形態】以下本発明のラスタ画像生成方法
およびラスタ画像生成装置の詳細を３つの実施例により
説明する。
およびラスタ画像生成装置の詳細を３つの実施例により
説明する。
【００７２】［実施例１］まず、第１の実施例のラスタ
画像生成方法およびラスタ画像生成装置の処理の手順を
図１を用いて説明する。処理は途中でプロセスをフォー
クし、複数のプロセスが同期を取りつつ協調動作して処
理を行う。
画像生成方法およびラスタ画像生成装置の処理の手順を
図１を用いて説明する。処理は途中でプロセスをフォー
クし、複数のプロセスが同期を取りつつ協調動作して処
理を行う。
【００７３】処理手順の最初のステップＳ０１では、描
画情報が記述されたＰＤＬを入力する。次にステップＳ
０２で、入力されたＰＤＬをインタプリタで解釈実行す
る。インタプリタがスキャンドイメージの描画要求を検
出すると、ステップＳ１０からＳ１３までの一連の処理
からなるプロセスをフォークし、そのプロセスはＳ０３
以降のステップと並行に動作する。
画情報が記述されたＰＤＬを入力する。次にステップＳ
０２で、入力されたＰＤＬをインタプリタで解釈実行す
る。インタプリタがスキャンドイメージの描画要求を検
出すると、ステップＳ１０からＳ１３までの一連の処理
からなるプロセスをフォークし、そのプロセスはＳ０３
以降のステップと並行に動作する。
【００７４】ステップＳ１０ではスキャンドイメージの
画像を入力する。画像はラスタデータあるいはデータ圧
縮のため符号の形式で入力される。後者の場合、ここの
ステップで符号を復号しラスタデータにする。以降この
ラスタデータをソース画像とする。ステップＳ１１では
ソース画像を、６４×６４画素の正方形の部分画像でタ
イル状に分割する。なお、分割の際にインタープリタの
指示により、ソース画像を縮小したうえで６４×６４画
素の部分画像に分割することもある。縮小を行った場合
は、縮小後の画像を以降ソース画像と見なして処理す
る。ステップＳ１２では部分画像毎に画像を符号化す
る。その際に、後述のステップＳ２０にて作られた重な
り情報を参照し、該部分画像の符号化条件がＴＲＵＥの
時のみ符号化を行う。ここで作られた符号は、ステップ
１３にて部分画像の場所に応じたメモリロケーションに
書き込まれる。各部分画像の符号化と符号の書き込みが
全て完了したら、このプロセスは終了する。
画像を入力する。画像はラスタデータあるいはデータ圧
縮のため符号の形式で入力される。後者の場合、ここの
ステップで符号を復号しラスタデータにする。以降この
ラスタデータをソース画像とする。ステップＳ１１では
ソース画像を、６４×６４画素の正方形の部分画像でタ
イル状に分割する。なお、分割の際にインタープリタの
指示により、ソース画像を縮小したうえで６４×６４画
素の部分画像に分割することもある。縮小を行った場合
は、縮小後の画像を以降ソース画像と見なして処理す
る。ステップＳ１２では部分画像毎に画像を符号化す
る。その際に、後述のステップＳ２０にて作られた重な
り情報を参照し、該部分画像の符号化条件がＴＲＵＥの
時のみ符号化を行う。ここで作られた符号は、ステップ
１３にて部分画像の場所に応じたメモリロケーションに
書き込まれる。各部分画像の符号化と符号の書き込みが
全て完了したら、このプロセスは終了する。
【００７５】ステップＳ０２におけるインタープリタの
実行の結果、ＰＤＬの描画情報に応じて各種の描画指
令、例えば文字の描画、直線の描画、曲線の描画、閉空
間の塗りつぶし等の指令がステップＳ０３に送られる。
ステップＳ０３では前記描画指令に基づいてデバイス空
間での描画情報が形成される。実施例では特開平５−２
２４６３７号公報において開示される技術と同様の技術
を用いており、描画情報はデバイス空間の走査線上のセ
グメント情報として生成され記録される。インタープリ
タが１ページ分の描画の終了を検出すると、３つのプロ
セスをフォークする。一つはステップＳ２０からＳ２１
までの一連の処理からなるプロセスで、二つめはステッ
プＳ２２からＳ２４までの一連の処理からなるプロセス
で、三つめはステップＳ３０からＳ３４までの一連の処
理からなるプロセスである。
実行の結果、ＰＤＬの描画情報に応じて各種の描画指
令、例えば文字の描画、直線の描画、曲線の描画、閉空
間の塗りつぶし等の指令がステップＳ０３に送られる。
ステップＳ０３では前記描画指令に基づいてデバイス空
間での描画情報が形成される。実施例では特開平５−２
２４６３７号公報において開示される技術と同様の技術
を用いており、描画情報はデバイス空間の走査線上のセ
グメント情報として生成され記録される。インタープリ
タが１ページ分の描画の終了を検出すると、３つのプロ
セスをフォークする。一つはステップＳ２０からＳ２１
までの一連の処理からなるプロセスで、二つめはステッ
プＳ２２からＳ２４までの一連の処理からなるプロセス
で、三つめはステップＳ３０からＳ３４までの一連の処
理からなるプロセスである。
【００７６】ステップＳ２０では、ソース画像を分割し
た各部分画像がデバイス画像のスキャンドイメージ部分
の描画に寄与するかを調べる。ＰｏｓｔＳｃｒｉｐｔの
ようなＰＤＬでは、ソース画像をアフィン変換した後に
任意の図形形状で切り抜いた上でデバイス画像上に描画
する。更に、デバイス画像上に描画した後に、スキャン
ドイメージ画像上に任意のラインアートを重ね書きする
こともある。このため、デバイス空間でのスキャンドイ
メージ部分の輪郭形状は任意の形状となる。この輪郭形
状の内側あるいは輪郭形状と交差する部分画像に存在す
る画素のみがデバイス画像の描画に貢献する。描画に無
効な部分画像をステップＳ１２にて符号化しステップＳ
１３にてメモリに書きこんでも意味がない。そこで有効
な部分画像すなわち部分画像と任意の形状の閉領域との
重ね合わせを検出し、それを符号化条件すなわち重なり
情報としてステップＳ１２に通知する。
た各部分画像がデバイス画像のスキャンドイメージ部分
の描画に寄与するかを調べる。ＰｏｓｔＳｃｒｉｐｔの
ようなＰＤＬでは、ソース画像をアフィン変換した後に
任意の図形形状で切り抜いた上でデバイス画像上に描画
する。更に、デバイス画像上に描画した後に、スキャン
ドイメージ画像上に任意のラインアートを重ね書きする
こともある。このため、デバイス空間でのスキャンドイ
メージ部分の輪郭形状は任意の形状となる。この輪郭形
状の内側あるいは輪郭形状と交差する部分画像に存在す
る画素のみがデバイス画像の描画に貢献する。描画に無
効な部分画像をステップＳ１２にて符号化しステップＳ
１３にてメモリに書きこんでも意味がない。そこで有効
な部分画像すなわち部分画像と任意の形状の閉領域との
重ね合わせを検出し、それを符号化条件すなわち重なり
情報としてステップＳ１２に通知する。
【００７７】ステップＳ２１では有効な部分画像の集合
をデバイス画像に写像し、デバイス空間の走査線を上か
ら下へ走査した際に、走査線上に新たに出現する部分画
像を調べる。走査線毎に新規出現部分画像の一覧を記載
した表を用意する。この表では部分画像は走査線順にソ
ートされ並んでいる。デバイス画像の出力では走査線順
にスキャンし画素を出力するので、この表を利用し、走
査線Ｙの出力の前に走査線Ｙにて新規に出力する部分画
像を復号すればよい。従って、この表の作成が復号順の
決定となる。復号順情報はステップＳ２２に伝えられ
る。ステップＳ２１が完了したらこのプロセスは終了す
る。
をデバイス画像に写像し、デバイス空間の走査線を上か
ら下へ走査した際に、走査線上に新たに出現する部分画
像を調べる。走査線毎に新規出現部分画像の一覧を記載
した表を用意する。この表では部分画像は走査線順にソ
ートされ並んでいる。デバイス画像の出力では走査線順
にスキャンし画素を出力するので、この表を利用し、走
査線Ｙの出力の前に走査線Ｙにて新規に出力する部分画
像を復号すればよい。従って、この表の作成が復号順の
決定となる。復号順情報はステップＳ２２に伝えられ
る。ステップＳ２１が完了したらこのプロセスは終了す
る。
【００７８】ステップＳ２２ではステップＳ２１で作成
された復号順情報を用いて、ステップＳ１３にてメモリ
書き込まれた部分画像の符号をメモリより読み出す。ス
テップＳ２３では符号を復号し部分画像を復元し、ステ
ップ２４で部分画像をメモリに書き込む。復号順情報に
記載された部分画像全てに関して符号のメモリ読み出し
／復号／画像のメモリ書き込みの処理が完了したらこの
プロセスは完了する。
された復号順情報を用いて、ステップＳ１３にてメモリ
書き込まれた部分画像の符号をメモリより読み出す。ス
テップＳ２３では符号を復号し部分画像を復元し、ステ
ップ２４で部分画像をメモリに書き込む。復号順情報に
記載された部分画像全てに関して符号のメモリ読み出し
／復号／画像のメモリ書き込みの処理が完了したらこの
プロセスは完了する。
【００７９】ステップＳ３０とＳ３３は描画情報である
画素セグメントにより選択的に起動される。画素セグメ
ントがラインアートのものの場合は、ステップＳ３３に
て１＋Ｘ１−Ｘ０個（ただし、Ｘ０はセグメント左端の
Ｘ座標、Ｘ１は右端）の同じ色の画素を作り、ステップ
Ｓ３４で出力する。画素セグメントがスキャンドイメー
ジの場合は、まずステップＳ３０にてデバイス空間での
セグメントの始点から終点までの各画素の座標をソース
空間に座標変換しソース空間上での該画素の座標を得
る。次いでステップＳ３１で各ソース座標値を該画素の
メモリ上でのアドレスに変換し、そのアドレスを用いて
ステップＳ３２にてメモリより画素を読み出し、ステッ
プＳ３４にて出力する。ステップＳ３４にてメモリより
読み出す画素はステップＳ２４にてメモリに書き込まれ
た画素である。以上の処理を１ページ分、すなわち、最
初の走査線から最後の走査線まで、走査線上の左端のセ
グメントから順に右端のセグメントについて行う。１ペ
ージ分の処理が完了したらこのプロセスは終了する。
画素セグメントにより選択的に起動される。画素セグメ
ントがラインアートのものの場合は、ステップＳ３３に
て１＋Ｘ１−Ｘ０個（ただし、Ｘ０はセグメント左端の
Ｘ座標、Ｘ１は右端）の同じ色の画素を作り、ステップ
Ｓ３４で出力する。画素セグメントがスキャンドイメー
ジの場合は、まずステップＳ３０にてデバイス空間での
セグメントの始点から終点までの各画素の座標をソース
空間に座標変換しソース空間上での該画素の座標を得
る。次いでステップＳ３１で各ソース座標値を該画素の
メモリ上でのアドレスに変換し、そのアドレスを用いて
ステップＳ３２にてメモリより画素を読み出し、ステッ
プＳ３４にて出力する。ステップＳ３４にてメモリより
読み出す画素はステップＳ２４にてメモリに書き込まれ
た画素である。以上の処理を１ページ分、すなわち、最
初の走査線から最後の走査線まで、走査線上の左端のセ
グメントから順に右端のセグメントについて行う。１ペ
ージ分の処理が完了したらこのプロセスは終了する。
【００８０】本発明の第１の実施例の全体のブロック図
を図２に示す。本実施例では、ＣＰＵ１とＩ／Ｏ手段２
とメモリ４とをバス３で接続した計算機システム上に構
成されている。ＣＰＵ１はメモリ４に格納されたプログ
ラムの命令語を読み出し実行する。プログラムの実行の
過程で、メモリ４に格納された各種データがＣＰＵ１に
ロードされ、プログラムに従って各種演算が行われ、結
果がメモリ４に格納される。Ｉ／Ｏ手段２は、キーボー
ド、ＣＲＴディスプレイ、磁気ディスク、フロッピィデ
ィスクドライブ、ＣＤ−ＲＯＭドライブ、ネットワーク
Ｉ／Ｆ等である。キーボードとＣＲＴディスプレイはオ
ペレータが計算機システムを操作するために用いられ
る。磁気ディスクは各種データをファイルとして長期的
あるいは一時的に格納するために用いる。フロッピィデ
ィスクドライブはフロッピィディスクを読み書きするた
めに用い、主な利用目的はシステムの初期化や故障診断
の為のプログラムをロードすることである。ＣＤ−ＲＯ
ＭドライブはＣＤ−ＲＯＭを読む為に用い、各種のアプ
リケーションプログラム等をインストールするために使
う。
を図２に示す。本実施例では、ＣＰＵ１とＩ／Ｏ手段２
とメモリ４とをバス３で接続した計算機システム上に構
成されている。ＣＰＵ１はメモリ４に格納されたプログ
ラムの命令語を読み出し実行する。プログラムの実行の
過程で、メモリ４に格納された各種データがＣＰＵ１に
ロードされ、プログラムに従って各種演算が行われ、結
果がメモリ４に格納される。Ｉ／Ｏ手段２は、キーボー
ド、ＣＲＴディスプレイ、磁気ディスク、フロッピィデ
ィスクドライブ、ＣＤ−ＲＯＭドライブ、ネットワーク
Ｉ／Ｆ等である。キーボードとＣＲＴディスプレイはオ
ペレータが計算機システムを操作するために用いられ
る。磁気ディスクは各種データをファイルとして長期的
あるいは一時的に格納するために用いる。フロッピィデ
ィスクドライブはフロッピィディスクを読み書きするた
めに用い、主な利用目的はシステムの初期化や故障診断
の為のプログラムをロードすることである。ＣＤ−ＲＯ
ＭドライブはＣＤ−ＲＯＭを読む為に用い、各種のアプ
リケーションプログラム等をインストールするために使
う。
【００８１】メモリ４は計算機システムの主記憶であ
る。ＰＤＬのインタープリタ１０はプログラムの形態で
メモリ４に格納されている。描画情報生成手段１１、重
なり検出手段１２、復号順決定手段１３も同様にプログ
ラムの形態でメモリ４に格納されている。これらはＣＰ
Ｕ１によって実行され。
る。ＰＤＬのインタープリタ１０はプログラムの形態で
メモリ４に格納されている。描画情報生成手段１１、重
なり検出手段１２、復号順決定手段１３も同様にプログ
ラムの形態でメモリ４に格納されている。これらはＣＰ
Ｕ１によって実行され。
【００８２】ネットワークＩ／Ｆを用いてＰＤＬで記述
した画像情報を受信し、磁気ディスクに格納する。それ
を磁気ディスクから読み出しメモリ４に格納する。イン
タープリタ１０はメモリ４上のＰＤＬ記述を解釈し実行
する。インタープリタ１０は実行の結果として、描画指
令を描画情報生成手段１１に与える。描画情報生成手段
１１は、各種描画指令をデバイス空間の解像度の描画情
報に変換する。フォント、グラフィクス、スキャンドイ
メージの描画指令は、特開平５−２２４６３７に開示さ
れる技術を用いて、デバイス空間の走査線に沿ったセグ
メント情報に変換され、描画情報１６としてメモリ４に
格納される。本実施例では特開平５−２２４６３７とは
異なり、スキャンドイメージの外接矩形の処理は行う
が、スキャンドイメージそのものについてはここでは処
理しない。
した画像情報を受信し、磁気ディスクに格納する。それ
を磁気ディスクから読み出しメモリ４に格納する。イン
タープリタ１０はメモリ４上のＰＤＬ記述を解釈し実行
する。インタープリタ１０は実行の結果として、描画指
令を描画情報生成手段１１に与える。描画情報生成手段
１１は、各種描画指令をデバイス空間の解像度の描画情
報に変換する。フォント、グラフィクス、スキャンドイ
メージの描画指令は、特開平５−２２４６３７に開示さ
れる技術を用いて、デバイス空間の走査線に沿ったセグ
メント情報に変換され、描画情報１６としてメモリ４に
格納される。本実施例では特開平５−２２４６３７とは
異なり、スキャンドイメージの外接矩形の処理は行う
が、スキャンドイメージそのものについてはここでは処
理しない。
【００８３】重なり検出手段１２は、メモリ４に格納さ
れた描画情報１６を読み出し、スキャンドイメージの輪
郭情報と部分画像との重なりを検出し、部分画像毎の重
なり情報１４をメモリ４に格納する。重なり検出の詳細
については後段で詳細に説明する。
れた描画情報１６を読み出し、スキャンドイメージの輪
郭情報と部分画像との重なりを検出し、部分画像毎の重
なり情報１４をメモリ４に格納する。重なり検出の詳細
については後段で詳細に説明する。
【００８４】復号順決定手段１３は、メモリ４に格納さ
れた重なり情報１４を読み出し、部分画像の符号を復号
する際の復号順を決定し、復号順情報１５をメモリ４に
格納する。復号順の決定の詳細については後段で詳細に
説明する。
れた重なり情報１４を読み出し、部分画像の符号を復号
する際の復号順を決定し、復号順情報１５をメモリ４に
格納する。復号順の決定の詳細については後段で詳細に
説明する。
【００８５】ネットワークＩ／Ｆを用いてスキャンドイ
メージの画像データを入力し、一旦磁気ディスクに格納
する。それを磁気ディスクから読み出し、バス３を経由
し、画像入力手段２０に与える。画像入力手段２０は縮
小手段２１と行バッファ２４と結合している。行バッフ
ァ手段２４は更に分割手段２２と結合している。分割手
段２２の出力は符号化手段２３に供給されるよう構成さ
れている。符号化手段２３の出力である部分画像の符号
１７はメモリ４に格納される。縮小手段２１はラスタ画
像を行バッファ２４に書き込む際に画像を縮小する。符
号化手段２３は、符号化の際にメモリ４に格納された重
なり情報１４を参照して、符号化すべき部分画像につい
てのみ符号化を行う。
メージの画像データを入力し、一旦磁気ディスクに格納
する。それを磁気ディスクから読み出し、バス３を経由
し、画像入力手段２０に与える。画像入力手段２０は縮
小手段２１と行バッファ２４と結合している。行バッフ
ァ手段２４は更に分割手段２２と結合している。分割手
段２２の出力は符号化手段２３に供給されるよう構成さ
れている。符号化手段２３の出力である部分画像の符号
１７はメモリ４に格納される。縮小手段２１はラスタ画
像を行バッファ２４に書き込む際に画像を縮小する。符
号化手段２３は、符号化の際にメモリ４に格納された重
なり情報１４を参照して、符号化すべき部分画像につい
てのみ符号化を行う。
【００８６】復号手段２５は、メモリ４に格納された復
号順情報１５に基づいて、メモリ４に格納された該部分
画像の符号１７をバス３を経由し入力し、復号し、該部
分画像を作り、それをメモリ２８に格納する。
号順情報１５に基づいて、メモリ４に格納された該部分
画像の符号１７をバス３を経由し入力し、復号し、該部
分画像を作り、それをメモリ２８に格納する。
【００８７】座標変換手段２６はメモリ４に格納されて
いる描画情報１６のスキャンドイメージに関連するセグ
メント情報を入力し、デバイス空間で表現されたセグメ
ント上の画素の座標をソース空間上の線分上の画素の座
標に変換する。ラインアートに関連するセグメント情報
は座標変換手段２６とアドレス変換手段２７とメモリ２
８を通らず直接画像出力手段２９に供給される。座標変
換手段２６の出力であるソース空間の座標情報はアドレ
ス変換手段２７に供給される。アドレス変換手段２７
は、ソース空間の座標情報をメモリ２８上の該当する部
分画像の該当する画素のアドレスに変換し、アドレスを
メモリ手段２８に送る。メモリ手段２８は、アドレス変
換手段２７から与えられたアドレスでメモリ上の部分画
像の画素を読み出し、読み出した画素を画像出力手段２
９に供給する。画像出力手段２９はラインアートのセグ
メント情報からラインアートの画素を生成し、スキャン
ドイメージの画素と組み合せて出力画像としてＩＯＴ
（Ｉｍａｇｅ ＯｕｔｐｕｔＴｅｒｍｉｎａｌ：画像出
力装置）へ出力する。
いる描画情報１６のスキャンドイメージに関連するセグ
メント情報を入力し、デバイス空間で表現されたセグメ
ント上の画素の座標をソース空間上の線分上の画素の座
標に変換する。ラインアートに関連するセグメント情報
は座標変換手段２６とアドレス変換手段２７とメモリ２
８を通らず直接画像出力手段２９に供給される。座標変
換手段２６の出力であるソース空間の座標情報はアドレ
ス変換手段２７に供給される。アドレス変換手段２７
は、ソース空間の座標情報をメモリ２８上の該当する部
分画像の該当する画素のアドレスに変換し、アドレスを
メモリ手段２８に送る。メモリ手段２８は、アドレス変
換手段２７から与えられたアドレスでメモリ上の部分画
像の画素を読み出し、読み出した画素を画像出力手段２
９に供給する。画像出力手段２９はラインアートのセグ
メント情報からラインアートの画素を生成し、スキャン
ドイメージの画素と組み合せて出力画像としてＩＯＴ
（Ｉｍａｇｅ ＯｕｔｐｕｔＴｅｒｍｉｎａｌ：画像出
力装置）へ出力する。
【００８８】次に第１の実施例の各手段についてより詳
細に説明する。
細に説明する。
【００８９】描画情報生成手段１１は、インタープリタ
１０が指示したフォント、グラフィクス、スキャンドイ
メージの輪郭等を、デバイス空間の解像度での形状に変
換し、デバイス空間の走査線上のセグメントで表現す
る。実施例の描画情報生成手段１１は、従来技術で説明
したデータ構造に類似した構造を用いてデバイス画像の
全走査線上の全セグメントを表現し、描画情報１６とし
てメモリ４に格納する。本実施例では描画情報の生成は
特開平５−２２４６３７に開示される技術と同様の技術
で行う。
１０が指示したフォント、グラフィクス、スキャンドイ
メージの輪郭等を、デバイス空間の解像度での形状に変
換し、デバイス空間の走査線上のセグメントで表現す
る。実施例の描画情報生成手段１１は、従来技術で説明
したデータ構造に類似した構造を用いてデバイス画像の
全走査線上の全セグメントを表現し、描画情報１６とし
てメモリ４に格納する。本実施例では描画情報の生成は
特開平５−２２４６３７に開示される技術と同様の技術
で行う。
【００９０】その結果、例えば図３に示すデバイス画像
の走査線Ｙ１に関する描画情報１６は図４に例示する様
なかたちで表現される。全走査線は配列ｄｅｖＩｍａｇ
ｅ［］よりアクセス可能である。配列ｄｅｖＩｍａｇｅ
［］は走査線数ＨＤの要素を持ち、各配列要素は各走査
線の左端セグメントのノードへのポインタである。走査
線Ｙ１について走査する場合はまずｄｅｖＩｍａｇｅ
［Ｙ１］を読み出し、走査線左端のセグメントのノード
へのポインタを得る。次にそのポインタを用いて左端の
セグメントのノードを得る。Ｘ座標が０からＸ１−１ま
での左端セグメントＳｅｇ１の色はラインアートの白で
あり、ノード内のポインタｐｐは白い画素をさし、ｄｐ
は０、ｎｅｘｔは右隣のセグメントのノードを指す。左
から２番目のセグメントＳｅｇ２は文字「Ａ」の一部で
あり、Ｘ座標はＸ１からＸ２−１まで、ラインアートに
由来し、色は灰色である。左から３番目のセグメントＳ
ｅｇ３はＸ座標Ｘ２からＸ３−１までを占め文字「Ａ」
の背景部分でラインラートで色は白である。左から４番
目のセグメントＳｅｇ４はＸ座標Ｘ３からＸ４−１まで
を占め文字「Ａ」の一部でラインラートで色は灰色であ
る。左から５番目のセグメントＳｅｇ５はＸ座標Ｘ４か
らＸ５−１までを占めラインラートで色は白である。左
から６番目のセグメントＳｅｇ６はＸ座標Ｘ５からＸ６
−１までを占めスキャンドイメージに由来する。左から
７番目のセグメントＳｅｇ７は右端のセグメントであり
Ｘ座標Ｘ６からＷＤ−１までを占めラインラートで色は
白である。描画情報１６には各セグメントの情報すなわ
ち、セグメントの左端と右端のＸ座標値（それぞれｘ０
とｘ１）、セグメントの色情報等へのポインタｐｐ、セ
グメントがラインアートあるいはスキャンドイメージに
由来することを示すフラグｄｐ、右隣りのセグメントの
ノードへのポインタｎｅｘｔが該セグメントのノードに
格納されている。従来技術ではポインタｐｐは画素デー
タへのポインタであったが、実施例ではｐｐはラインア
ートのセグメントでは画素データへのポインタ、スキャ
ンドイメージのセグメントでは後述のテーブルへのポイ
ンタである。セグメントＳｅｇ１，Ｓｅｇ３，Ｓｅｇ
５，Ｓｅｇ７はラインアート由来の白のセグメントなの
で、それぞれのノードのｐｐは白い画素値のデータを格
納するエリアへのポインタを有し、ｄｐには０が入る。
セグメントＳｅｇ２とＳｅｇ４はラインラート由来の灰
色のセグメントなので、それぞれのノードのｐｐには灰
色の画素値を格納するエリアへのポインタを有し、ｄｐ
には０が入る。セグメントＳｅｇ６はスキャンドイメー
ジに由来するセグメントであり、ｐｐにはメモリ２８に
格納される部分画像へのポインタのテーブルへのポイン
タが格納され、ｄｐにはスキャンドイメージのセグメン
トを示す為１が設定される。右端のセグメントＳｅｇ７
にはｎｅｘｔにＮＵＬＬが設定される。
の走査線Ｙ１に関する描画情報１６は図４に例示する様
なかたちで表現される。全走査線は配列ｄｅｖＩｍａｇ
ｅ［］よりアクセス可能である。配列ｄｅｖＩｍａｇｅ
［］は走査線数ＨＤの要素を持ち、各配列要素は各走査
線の左端セグメントのノードへのポインタである。走査
線Ｙ１について走査する場合はまずｄｅｖＩｍａｇｅ
［Ｙ１］を読み出し、走査線左端のセグメントのノード
へのポインタを得る。次にそのポインタを用いて左端の
セグメントのノードを得る。Ｘ座標が０からＸ１−１ま
での左端セグメントＳｅｇ１の色はラインアートの白で
あり、ノード内のポインタｐｐは白い画素をさし、ｄｐ
は０、ｎｅｘｔは右隣のセグメントのノードを指す。左
から２番目のセグメントＳｅｇ２は文字「Ａ」の一部で
あり、Ｘ座標はＸ１からＸ２−１まで、ラインアートに
由来し、色は灰色である。左から３番目のセグメントＳ
ｅｇ３はＸ座標Ｘ２からＸ３−１までを占め文字「Ａ」
の背景部分でラインラートで色は白である。左から４番
目のセグメントＳｅｇ４はＸ座標Ｘ３からＸ４−１まで
を占め文字「Ａ」の一部でラインラートで色は灰色であ
る。左から５番目のセグメントＳｅｇ５はＸ座標Ｘ４か
らＸ５−１までを占めラインラートで色は白である。左
から６番目のセグメントＳｅｇ６はＸ座標Ｘ５からＸ６
−１までを占めスキャンドイメージに由来する。左から
７番目のセグメントＳｅｇ７は右端のセグメントであり
Ｘ座標Ｘ６からＷＤ−１までを占めラインラートで色は
白である。描画情報１６には各セグメントの情報すなわ
ち、セグメントの左端と右端のＸ座標値（それぞれｘ０
とｘ１）、セグメントの色情報等へのポインタｐｐ、セ
グメントがラインアートあるいはスキャンドイメージに
由来することを示すフラグｄｐ、右隣りのセグメントの
ノードへのポインタｎｅｘｔが該セグメントのノードに
格納されている。従来技術ではポインタｐｐは画素デー
タへのポインタであったが、実施例ではｐｐはラインア
ートのセグメントでは画素データへのポインタ、スキャ
ンドイメージのセグメントでは後述のテーブルへのポイ
ンタである。セグメントＳｅｇ１，Ｓｅｇ３，Ｓｅｇ
５，Ｓｅｇ７はラインアート由来の白のセグメントなの
で、それぞれのノードのｐｐは白い画素値のデータを格
納するエリアへのポインタを有し、ｄｐには０が入る。
セグメントＳｅｇ２とＳｅｇ４はラインラート由来の灰
色のセグメントなので、それぞれのノードのｐｐには灰
色の画素値を格納するエリアへのポインタを有し、ｄｐ
には０が入る。セグメントＳｅｇ６はスキャンドイメー
ジに由来するセグメントであり、ｐｐにはメモリ２８に
格納される部分画像へのポインタのテーブルへのポイン
タが格納され、ｄｐにはスキャンドイメージのセグメン
トを示す為１が設定される。右端のセグメントＳｅｇ７
にはｎｅｘｔにＮＵＬＬが設定される。
【００９１】デバイス画像におけるスキャンドイメージ
部分は、図５の５１２×５１２画素の正方形のソース画
像ａｂｃｄをアフィン変換し、図６に示すようなデバイ
ス空間上の平行四辺形ＡＢＣＤを得て、それを長方形Ｅ
ＦＧＨでクリッピングし、内側をデバイス画像上に描画
したものである。
部分は、図５の５１２×５１２画素の正方形のソース画
像ａｂｃｄをアフィン変換し、図６に示すようなデバイ
ス空間上の平行四辺形ＡＢＣＤを得て、それを長方形Ｅ
ＦＧＨでクリッピングし、内側をデバイス画像上に描画
したものである。
【００９２】ソース画像ａｂｃｄは８×８個の部分画像
に分割出来る。部分画像をデバイス空間に写像すると図
６に示す８×８個の平行四辺形になる。
に分割出来る。部分画像をデバイス空間に写像すると図
６に示す８×８個の平行四辺形になる。
【００９３】ソース画像がＢｘ×Ｂｙ個の部分画像に分
割出来る場合、重なり情報１４は図７に示すようにＢｘ
×Ｂｙ個の要素を持つテーブルとして構成され、メモリ
４に格納されている。テーブルのエントリは１（真）ま
たは０（偽）の論理値を格納する。
割出来る場合、重なり情報１４は図７に示すようにＢｘ
×Ｂｙ個の要素を持つテーブルとして構成され、メモリ
４に格納されている。テーブルのエントリは１（真）ま
たは０（偽）の論理値を格納する。
【００９４】重なり検出手段１２は、まず重なり情報１
４のテーブルの全エントリを０にする。その後、重なり
検出手段１２は、メモリ４に格納された描画情報１６よ
りスキャンドイメージの輪郭情報を読み出し、それを該
スキャンドイメージの描画の際に指定されたアフィン変
換の逆変換を施し、輪郭情報をスキャンドイメージのソ
ース空間に写像する。デバイス画像のスキャンドイメー
ジ部分の描画に貢献する画素は逆変換された輪郭形状の
内側にある。従って、逆変換された外形形状の内側に存
在する部分画像あるいは輪郭上に存在する部分画像のみ
がデバイス画像の描画に寄与する。従って、重なり検出
手段１２はそのような部分画像を選べばよい。部分画像
の選択は次のように行う。描画情報１６中のスキャンド
イメージのセグメントを順次読み出し、該セグメントを
逆変換し、ソース空間に写像する。セグメントはデバイ
ス空間で幅Ｘ１−Ｘ０、高さ１の長方形なので、逆変換
するとソース空間上では平行四辺形となる。この平行四
辺形と重なる部分画像を見つける。これは部分画像の解
像度で平行四辺形を描画すること、すなわち、平行四辺
形を部分画像の精度で解像度変換することに等しい。図
形の解像度変換については多くの技術が知られており、
例えばＪａｍｅｓ Ｄ．ＦｏｌｅｙとＡｎｄｒｉｅｓ
Ｖａｎ Ｄａｍ共著のテキストブック「コンピュータ・
グラフクス」の１１章に代表的な技術が記載されてい
る。本実施例では１１．７章に記載されているスキャン
・ライン・アルゴリズムを用いて解像度変換を行う。解
像度変換の結果、該平行四辺形のと重なる部分画像が検
出される。図８は図５のソース画像の部分画像において
逆変換された輪郭形状ｅｆｇｈと重なる部分画像をグレ
ーで示している。細長い平行四辺形はデバイス空間のセ
グメントを逆変換したものである。セグメントの平行四
辺形毎に部分画像との重なりを検出し、重なっていた部
分画像の和集合をとればよい。重なり検出手段１２は、
重なり情報１４のテーブルにおいて、検出された部分画
像に対応するエントリに１を書き込む。重なり検出手段
１２は描画情報１６の全スキャンドイメージ由来のセグ
メントに関して以上の処理を行う。処理終了後、重なり
情報１４にはデバイス画像に寄与する部分画像全てのエ
ントリに１が書き込まれている。図５のソース画像にア
フィン変換とクリッピングを行い図６のデバイス画像と
した場合の重なり情報１４を図９に例として示す。
４のテーブルの全エントリを０にする。その後、重なり
検出手段１２は、メモリ４に格納された描画情報１６よ
りスキャンドイメージの輪郭情報を読み出し、それを該
スキャンドイメージの描画の際に指定されたアフィン変
換の逆変換を施し、輪郭情報をスキャンドイメージのソ
ース空間に写像する。デバイス画像のスキャンドイメー
ジ部分の描画に貢献する画素は逆変換された輪郭形状の
内側にある。従って、逆変換された外形形状の内側に存
在する部分画像あるいは輪郭上に存在する部分画像のみ
がデバイス画像の描画に寄与する。従って、重なり検出
手段１２はそのような部分画像を選べばよい。部分画像
の選択は次のように行う。描画情報１６中のスキャンド
イメージのセグメントを順次読み出し、該セグメントを
逆変換し、ソース空間に写像する。セグメントはデバイ
ス空間で幅Ｘ１−Ｘ０、高さ１の長方形なので、逆変換
するとソース空間上では平行四辺形となる。この平行四
辺形と重なる部分画像を見つける。これは部分画像の解
像度で平行四辺形を描画すること、すなわち、平行四辺
形を部分画像の精度で解像度変換することに等しい。図
形の解像度変換については多くの技術が知られており、
例えばＪａｍｅｓ Ｄ．ＦｏｌｅｙとＡｎｄｒｉｅｓ
Ｖａｎ Ｄａｍ共著のテキストブック「コンピュータ・
グラフクス」の１１章に代表的な技術が記載されてい
る。本実施例では１１．７章に記載されているスキャン
・ライン・アルゴリズムを用いて解像度変換を行う。解
像度変換の結果、該平行四辺形のと重なる部分画像が検
出される。図８は図５のソース画像の部分画像において
逆変換された輪郭形状ｅｆｇｈと重なる部分画像をグレ
ーで示している。細長い平行四辺形はデバイス空間のセ
グメントを逆変換したものである。セグメントの平行四
辺形毎に部分画像との重なりを検出し、重なっていた部
分画像の和集合をとればよい。重なり検出手段１２は、
重なり情報１４のテーブルにおいて、検出された部分画
像に対応するエントリに１を書き込む。重なり検出手段
１２は描画情報１６の全スキャンドイメージ由来のセグ
メントに関して以上の処理を行う。処理終了後、重なり
情報１４にはデバイス画像に寄与する部分画像全てのエ
ントリに１が書き込まれている。図５のソース画像にア
フィン変換とクリッピングを行い図６のデバイス画像と
した場合の重なり情報１４を図９に例として示す。
【００９５】復号順決定手段１３は、まず、部分画像の
４個の頂点のうち、デバイス空間に変換した際にＹ座標
値が最小となる頂点を選び出し、それを部分画像の代表
点とする。復号順決定手段１３はメモリ４に格納された
重なり情報１４よりデバイス画像の描画に寄与する全部
分画像（ｘＢ，ｙＢ）について、代表点の座標（６４・
ｘＢ＋ｘｏｆｆ，６４・ｙＢ＋ｙｏｆｆ）をアフィン変
換し、Ｙ座標値Ｙ（ｘＢ，ｙＢ）と部分画像番号（ｘ
Ｂ，ｙＢ）の組を得る。ここで、ｘｏｆｆとｙｏｆｆは
次のように与えられる。
４個の頂点のうち、デバイス空間に変換した際にＹ座標
値が最小となる頂点を選び出し、それを部分画像の代表
点とする。復号順決定手段１３はメモリ４に格納された
重なり情報１４よりデバイス画像の描画に寄与する全部
分画像（ｘＢ，ｙＢ）について、代表点の座標（６４・
ｘＢ＋ｘｏｆｆ，６４・ｙＢ＋ｙｏｆｆ）をアフィン変
換し、Ｙ座標値Ｙ（ｘＢ，ｙＢ）と部分画像番号（ｘ
Ｂ，ｙＢ）の組を得る。ここで、ｘｏｆｆとｙｏｆｆは
次のように与えられる。
【００９６】
【表１】
【００９７】次に、各部分画像のＹ（ｘＢ，ｙＢ）の値
に関して昇順にソートし、結果を復号順情報１５として
メモリ４に格納する。
に関して昇順にソートし、結果を復号順情報１５として
メモリ４に格納する。
【００９８】以上の過程を、図５のソース画像にアフィ
ン変換とクリッピングを施し図６に示す様にデバイス画
像に描画する場合を例に説明する。この例では部分画像
の左上頂点が部分画像の代表点となる。従ってアフィン
変換後の代表点のＹ座標値Ｙ（ｘＢ，ｙＢ）は、
ン変換とクリッピングを施し図６に示す様にデバイス画
像に描画する場合を例に説明する。この例では部分画像
の左上頂点が部分画像の代表点となる。従ってアフィン
変換後の代表点のＹ座標値Ｙ（ｘＢ，ｙＢ）は、
【００９９】
【数１２】Ｙ（ｘＢ，ｙＢ）＝６４・ｃ・ｘＢ＋６４・
ｄｙ・Ｂ＋ｖ となる。ここでｃ，ｄ，ｖはアフィン変換のパラメータ
である。
ｄｙ・Ｂ＋ｖ となる。ここでｃ，ｄ，ｖはアフィン変換のパラメータ
である。
【０１００】デバイス画像のスキャンドイメージの描画
寄与する部分画像は図８に灰色で示した部分であり、こ
れらのＹ（ｘＢ，ｙＢ）をそれぞれ計算し、昇順に並べ
た時の部分画像の順番は、（２，０），（１，１），
（０，２），（３，０），（２，１），（１，２），
（０，３），．．．．．となる。復号順決定手段１３
は、この順番に従って、Ｙ（ｘＢ，ｙＢ）の値と部分画
像番号（ｘＢ，ｙＢ）を図１１に示すような形で復号順
情報１５としてメモリ４に格納する。
寄与する部分画像は図８に灰色で示した部分であり、こ
れらのＹ（ｘＢ，ｙＢ）をそれぞれ計算し、昇順に並べ
た時の部分画像の順番は、（２，０），（１，１），
（０，２），（３，０），（２，１），（１，２），
（０，３），．．．．．となる。復号順決定手段１３
は、この順番に従って、Ｙ（ｘＢ，ｙＢ）の値と部分画
像番号（ｘＢ，ｙＢ）を図１１に示すような形で復号順
情報１５としてメモリ４に格納する。
【０１０１】デバイス画像の出力時の走査はＹ＝０の走
査線より始まり、Ｙの値を１づづ増し、ＨＤ−１に達す
るまで行う。従って、出力時の走査において、デバイス
画像に貢献する部分画像が走査線と交差する最初の点は
部分画像の代表点である。また、Ｙ（ｘＢ，ｙＢ）が小
さな値をとる部分画像より順に走査線上に現れる。従っ
て部分画像の代表点のＹ（ｘＢ，ｙＢ）値で昇順にソー
トした順に部分画像の符号を復号して部分画像に戻し、
走査線Ｙのスキャンを行う前に部分画像が復元されてい
るように制御する。これにより、走査線Ｙのスキャン時
荷はスキャンドイメージの画素を直ちに得ることができ
る。図１０を例にすると、デバイス空間の走査線Ｙを０
から順に走査する場合、まずＹ＝Ｙ（１，１）までに部
分画像（１，１）の符号を復号しておく。Ｙ＝Ｙ（０，
２）までに部分画像（０，２）を復号しておく以下同様
に部分画像（３，０），（２，１），（１，２），
（０，３），．．．．をそれぞれＹ＝Ｙ（ｘＢ，ｙＢ）
になる前に復号しておく。このように、Ｙ（ｘＢ，ｙ
Ｂ）でソートした順に部分画像の符号を復号すること
で、デバイス画像の走査時までに部分画像を用意するが
可能となる。
査線より始まり、Ｙの値を１づづ増し、ＨＤ−１に達す
るまで行う。従って、出力時の走査において、デバイス
画像に貢献する部分画像が走査線と交差する最初の点は
部分画像の代表点である。また、Ｙ（ｘＢ，ｙＢ）が小
さな値をとる部分画像より順に走査線上に現れる。従っ
て部分画像の代表点のＹ（ｘＢ，ｙＢ）値で昇順にソー
トした順に部分画像の符号を復号して部分画像に戻し、
走査線Ｙのスキャンを行う前に部分画像が復元されてい
るように制御する。これにより、走査線Ｙのスキャン時
荷はスキャンドイメージの画素を直ちに得ることができ
る。図１０を例にすると、デバイス空間の走査線Ｙを０
から順に走査する場合、まずＹ＝Ｙ（１，１）までに部
分画像（１，１）の符号を復号しておく。Ｙ＝Ｙ（０，
２）までに部分画像（０，２）を復号しておく以下同様
に部分画像（３，０），（２，１），（１，２），
（０，３），．．．．をそれぞれＹ＝Ｙ（ｘＢ，ｙＢ）
になる前に復号しておく。このように、Ｙ（ｘＢ，ｙ
Ｂ）でソートした順に部分画像の符号を復号すること
で、デバイス画像の走査時までに部分画像を用意するが
可能となる。
【０１０２】画像入力手段２０は、入力された画像デー
タが符号化されたデータの時には画像の符号を復号しラ
スタデータの形式にし、スキャン順に画素を縮小手段に
供給する。実施例においてはスキャンドイメージの圧縮
にしばしば用いられるＪＰＥＧ符号用のデコーダを備え
ている。
タが符号化されたデータの時には画像の符号を復号しラ
スタデータの形式にし、スキャン順に画素を縮小手段に
供給する。実施例においてはスキャンドイメージの圧縮
にしばしば用いられるＪＰＥＧ符号用のデコーダを備え
ている。
【０１０３】ソース画像のサイズを幅ＷＳ，高さＨＳと
する。縮小後のソース画像のサイズを幅Ｗｉ，高さＨｉ
とする。ｘ軸方向の画像の縮小率をｎｘ、ｙ軸方向の画
像の縮小率をｎｙとする。ｎｘが３の場合画像はｘ軸方
向に１／３のサイズに縮小される。ｎｙが２の場合画像
はｙ軸方向に１／２のサイズに縮小される。
する。縮小後のソース画像のサイズを幅Ｗｉ，高さＨｉ
とする。ｘ軸方向の画像の縮小率をｎｘ、ｙ軸方向の画
像の縮小率をｎｙとする。ｎｘが３の場合画像はｘ軸方
向に１／３のサイズに縮小される。ｎｙが２の場合画像
はｙ軸方向に１／２のサイズに縮小される。
【０１０４】縮小手段２１と分割手段２２と行バッファ
２４は互いに結合しており、これらをまとめてブロック
図１２に示す。行バッファ２４はＲＡＭで構成されてお
り、縮小手段２１にて生成された書き込みアドレスのメ
モリ位置に入力画素を書き込む。書き込みは縮小手段２
１にて生成されたライトイネーブル信号ＷＥにより制御
される。読み出しアドレスは分割手段２２よりＲＡＭに
供給され、該画素が出力され、画素は符号化手段２３に
送られる。行バッファは縮小後のソース画像の走査線を
６４本格納することができる。実施例では合計５１２Ｋ
×４バイトのＳＲＡＭを用いており、１行の長さは最大
８Ｋ（８１９２）画素となっている。１画素は４バイト
で４色成分までサポートできる。
２４は互いに結合しており、これらをまとめてブロック
図１２に示す。行バッファ２４はＲＡＭで構成されてお
り、縮小手段２１にて生成された書き込みアドレスのメ
モリ位置に入力画素を書き込む。書き込みは縮小手段２
１にて生成されたライトイネーブル信号ＷＥにより制御
される。読み出しアドレスは分割手段２２よりＲＡＭに
供給され、該画素が出力され、画素は符号化手段２３に
送られる。行バッファは縮小後のソース画像の走査線を
６４本格納することができる。実施例では合計５１２Ｋ
×４バイトのＳＲＡＭを用いており、１行の長さは最大
８Ｋ（８１９２）画素となっている。１画素は４バイト
で４色成分までサポートできる。
【０１０５】縮小手段２１には、ソース画像の画素のｘ
座標位置をカウントするｘＳカウンタ２１０、ｙ座標位
置をカウントするｙＳカウンタ２１１、ｎｘカウンタ２
１２、ｎｙカウンタ２１３、縮小後のソース画像のｘ座
標位置をカウントするｘｉカウンタ２１４、縮小後のソ
ース画像のｙ座標位置をカウントするｙｉカウンタ２１
５、ＡＮＤゲート２１６、アドレス生成器２１７とが備
えられている。
座標位置をカウントするｘＳカウンタ２１０、ｙ座標位
置をカウントするｙＳカウンタ２１１、ｎｘカウンタ２
１２、ｎｙカウンタ２１３、縮小後のソース画像のｘ座
標位置をカウントするｘｉカウンタ２１４、縮小後のソ
ース画像のｙ座標位置をカウントするｙｉカウンタ２１
５、ＡＮＤゲート２１６、アドレス生成器２１７とが備
えられている。
【０１０６】図１３に示す縮小手段の動作のタイミング
図とともに縮小手段２１の動作を説明する。
図とともに縮小手段２１の動作を説明する。
【０１０７】ｘｓカウンタ２１０は画素を入力するごと
に０からＷＳ−１まで１つづつ増加する。ＷＳ−１に達
した時に新たな画素を入力すると０に戻る。これはソー
ス画像を１行入力終えたことを意味し、１行入力終了は
ｙＳカウンタ２１１とｎｙカウンタに通知される。
に０からＷＳ−１まで１つづつ増加する。ＷＳ−１に達
した時に新たな画素を入力すると０に戻る。これはソー
ス画像を１行入力終えたことを意味し、１行入力終了は
ｙＳカウンタ２１１とｎｙカウンタに通知される。
【０１０８】ｙＳカウンタ２１１はソース画像を１行入
力するごとに０からＨＳ−１まで１つづつ増加する。Ｈ
Ｓ−１のときに１行入力が完了したら０にもどる。これ
はソース画像の入力の完了を意味する。
力するごとに０からＨＳ−１まで１つづつ増加する。Ｈ
Ｓ−１のときに１行入力が完了したら０にもどる。これ
はソース画像の入力の完了を意味する。
【０１０９】ｎｘカウンタ２１２は１画素入力するごと
に０からｎｘ−１までカウントアップし、ｎｘ−１に達
したら画素入力で再び０に戻る。ｎｘカウンタの値が０
を示すとき、それｘｉカウンタ２１４とＡＮＤゲート２
１６に通知される。ｎｘカウンタはソース画像のｘ方向
縮小の際に画素を間引くタイミングを示す。ｎｘカウン
タの値が０以外の時には画素を間引く。例えば、ｎｘ＝
２の場合ｎｘカウンタが１の時には画素を間引く。従っ
てソース画像はｘ軸方向に１／２に縮小する。ｎｘ＝３
の場合ｎｘカウンタが１〜２の時には画素を間引く。こ
れによりソース画像はｘ軸方向に１／３に縮小する。ソ
ース画像の縮小を行わない時にはｎｘとして１を設定す
る。この場合ｎｘカウンタは常に０を保つのでｘ軸方向
の画素間引きは発生せず、ソース画像のｘ軸方向の縮小
は生じない。
に０からｎｘ−１までカウントアップし、ｎｘ−１に達
したら画素入力で再び０に戻る。ｎｘカウンタの値が０
を示すとき、それｘｉカウンタ２１４とＡＮＤゲート２
１６に通知される。ｎｘカウンタはソース画像のｘ方向
縮小の際に画素を間引くタイミングを示す。ｎｘカウン
タの値が０以外の時には画素を間引く。例えば、ｎｘ＝
２の場合ｎｘカウンタが１の時には画素を間引く。従っ
てソース画像はｘ軸方向に１／２に縮小する。ｎｘ＝３
の場合ｎｘカウンタが１〜２の時には画素を間引く。こ
れによりソース画像はｘ軸方向に１／３に縮小する。ソ
ース画像の縮小を行わない時にはｎｘとして１を設定す
る。この場合ｎｘカウンタは常に０を保つのでｘ軸方向
の画素間引きは発生せず、ソース画像のｘ軸方向の縮小
は生じない。
【０１１０】ｘｉカウンタ２１４はｎｘカウンタ＝０の
通知毎に０からＷｉ−１まで１つづつ増加する。Ｗｉ−
１の時にｎｘカウンタ＝０の通知を受けたら０に戻る。
これは縮小後のソース画像の１行が終わったことを意味
し、これはアドレス生成器２１７に通知される。
通知毎に０からＷｉ−１まで１つづつ増加する。Ｗｉ−
１の時にｎｘカウンタ＝０の通知を受けたら０に戻る。
これは縮小後のソース画像の１行が終わったことを意味
し、これはアドレス生成器２１７に通知される。
【０１１１】ｎｙカウンタ２１３はソース画像１行入力
するごとに０からｎｙ−１までカウントアップし、ｎｙ
−１に達したらソース画像１行の入力の通知で再び０に
戻る。ｎｙカウンタの値が０を示す時、それはｙｉカウ
ンタ２１５とＡＮＤゲート２１６に通知される。ｎｙカ
ウンタはソース画像のｙ方向縮小の際に画素を間引くタ
イミングを示す。ｎｙカウンタの値が０以外の時には画
素を間引く。例えば、ｎｙ＝２の場合ｎｙカウンタが１
の時には走査線を間引く。従ってソース画像はｙ軸方向
に１／２に縮小する。ｎｙ＝３の場合ｎｙカウンタが１
〜２の時には走査線を間引く。これによりソース画像は
ｙ軸方向に１／３に縮小する。ソース画像の縮小を行わ
ない時にはｎｙとして１を設定する。この場合ｎｙカウ
ンタは常に０を保つのでｙ軸方向の走査線の間引きは発
生せず、ソース画像のｙ軸方向の縮小は生じない。
するごとに０からｎｙ−１までカウントアップし、ｎｙ
−１に達したらソース画像１行の入力の通知で再び０に
戻る。ｎｙカウンタの値が０を示す時、それはｙｉカウ
ンタ２１５とＡＮＤゲート２１６に通知される。ｎｙカ
ウンタはソース画像のｙ方向縮小の際に画素を間引くタ
イミングを示す。ｎｙカウンタの値が０以外の時には画
素を間引く。例えば、ｎｙ＝２の場合ｎｙカウンタが１
の時には走査線を間引く。従ってソース画像はｙ軸方向
に１／２に縮小する。ｎｙ＝３の場合ｎｙカウンタが１
〜２の時には走査線を間引く。これによりソース画像は
ｙ軸方向に１／３に縮小する。ソース画像の縮小を行わ
ない時にはｎｙとして１を設定する。この場合ｎｙカウ
ンタは常に０を保つのでｙ軸方向の走査線の間引きは発
生せず、ソース画像のｙ軸方向の縮小は生じない。
【０１１２】ｙｉカウンタ２１４はｎｙカウンタ＝０の
通知毎に０からＨｉ−１まで１つづつ増加する。Ｈｉ−
１の時にｎｙカウンタ＝０の通知を受けたら０に戻る。
これはソース画像入力の完了を意味する。ｙｉカウンタ
２１４は更に、６４行毎の入力完了も検出する。６４行
毎の入力完了およびソース画像の入力完了は分割手段２
２に通知される。
通知毎に０からＨｉ−１まで１つづつ増加する。Ｈｉ−
１の時にｎｙカウンタ＝０の通知を受けたら０に戻る。
これはソース画像入力の完了を意味する。ｙｉカウンタ
２１４は更に、６４行毎の入力完了も検出する。６４行
毎の入力完了およびソース画像の入力完了は分割手段２
２に通知される。
【０１１３】ＡＮＤゲート２１６はｎｘカウンタ＝０か
つｎｙカウンタ＝０の条件を検出する。この条件が真の
とき該入力画素はｘおよびｙ方向のいずれにも間引かな
い画素である。したがってＡＮＤゲート２１６の出力を
行バッファ２４のＲＡＭへのライトイネーブル信号ＷＥ
として供給する。ＷＥ信号荷より、ＲＡＭはこの時の入
力画素を書き込む。その際の書き込み先アドレスについ
ては以下で詳細に説明する。
つｎｙカウンタ＝０の条件を検出する。この条件が真の
とき該入力画素はｘおよびｙ方向のいずれにも間引かな
い画素である。したがってＡＮＤゲート２１６の出力を
行バッファ２４のＲＡＭへのライトイネーブル信号ＷＥ
として供給する。ＷＥ信号荷より、ＲＡＭはこの時の入
力画素を書き込む。その際の書き込み先アドレスについ
ては以下で詳細に説明する。
【０１１４】アドレス生成器２１７は、ｘｉカウンタ２
１４の値とｙｉカウンタ２１５の値を利用し、下記に示
す様にアドレスを生成する。
１４の値とｙｉカウンタ２１５の値を利用し、下記に示
す様にアドレスを生成する。
【０１１５】
【数１３】書き込みアドレス＝８１９２×（ｙｉカウン
タの値％６４）＋ｘｉカウンタの値
タの値％６４）＋ｘｉカウンタの値
【０１１６】ここで「％」は剰余を取る演算を意味す
る。行バッファのＲＡＭの連続する８Ｋ語を縮小後のソ
ース画像の１行に固定的に割当てている。行バッファの
ＲＡＭにおける画素の割当てを図１４に模式的に示す。
ＲＡＭの最初の８１９２語には、縮小後のソース画像の
１行目、６５行目、１２９行目、１９３行目．．．が格
納される。２行目、６６行目等はその次の８１９２語に
格納される。以下同様に６４行目、１２８行目等がＲＡ
Ｍの最後の８１９２語に格納される。従って図１４から
わかるように行バッファのＲＡＭには横１列分の部分画
像が格納される。
る。行バッファのＲＡＭの連続する８Ｋ語を縮小後のソ
ース画像の１行に固定的に割当てている。行バッファの
ＲＡＭにおける画素の割当てを図１４に模式的に示す。
ＲＡＭの最初の８１９２語には、縮小後のソース画像の
１行目、６５行目、１２９行目、１９３行目．．．が格
納される。２行目、６６行目等はその次の８１９２語に
格納される。以下同様に６４行目、１２８行目等がＲＡ
Ｍの最後の８１９２語に格納される。従って図１４から
わかるように行バッファのＲＡＭには横１列分の部分画
像が格納される。
【０１１７】分割手段２２にはアドレス生成器２２０と
ｘＢカウンタ２２１とｙＢカウンタ２２２とが設けられ
ている。
ｘＢカウンタ２２１とｙＢカウンタ２２２とが設けられ
ている。
【０１１８】アドレス生成器は、ｙｉカウンタ２１４の
６４行の入力完了の通知を受けることで起動され、行バ
ッファのＲＡＭの画素アドレスを生成する。生成された
アドレスはＲＡＭに供給され、ＲＡＭから画素を読み出
し、出力画素として符号化手段２３に送る。画素の読み
出しは符号化手段２３から供給される画素出力ストロー
ブ信号によって同期するよう制御される。画素ストロー
ブ信号はアドレス生成器２２０に与えられるよう構成さ
れており、アドレス生成器２２０は画素ストローブ信号
がアサートされている時のみ画素読み出しアドレスを更
新する。アドレス生成器２２０はＲＡＭに格納された部
分画像を左から右へ（図１４参照）、部分画像について
は部分画像内の６４個の８×８画素ブロックを図１５ａ
に示すような順に、８×８画素ブロック内の画素につい
ては図１５ｂに示すような順で読み出す様にアドレスを
生成する。すなわち、読み出しアドレスは、
６４行の入力完了の通知を受けることで起動され、行バ
ッファのＲＡＭの画素アドレスを生成する。生成された
アドレスはＲＡＭに供給され、ＲＡＭから画素を読み出
し、出力画素として符号化手段２３に送る。画素の読み
出しは符号化手段２３から供給される画素出力ストロー
ブ信号によって同期するよう制御される。画素ストロー
ブ信号はアドレス生成器２２０に与えられるよう構成さ
れており、アドレス生成器２２０は画素ストローブ信号
がアサートされている時のみ画素読み出しアドレスを更
新する。アドレス生成器２２０はＲＡＭに格納された部
分画像を左から右へ（図１４参照）、部分画像について
は部分画像内の６４個の８×８画素ブロックを図１５ａ
に示すような順に、８×８画素ブロック内の画素につい
ては図１５ｂに示すような順で読み出す様にアドレスを
生成する。すなわち、読み出しアドレスは、
【０１１９】
【数１４】読み出しアドレス＝６４ｘＢ＋Ｏｆｆｓｅｔ
１（ｘ’，ｙ’）＋Ｏｆｆｓｅｔ２（ｘ”，ｙ”） となる。
１（ｘ’，ｙ’）＋Ｏｆｆｓｅｔ２（ｘ”，ｙ”） となる。
【０１２０】ここでｘＢは部分画像のｘ座標方向の番号
であり、ｘ’，ｙ’はそれぞれ８×８画素ブロックの
ｘ，ｙ座標方向のブロック番号、ｘ”，ｙ”はそれぞれ
８×８画素ブロック内の座標位置とすると、Ｏｆｆｓｅ
ｔ１（ｘ’，ｙ’）とＯｆｆｓｅｔ２（ｘ”，ｙ”）は
それぞれ、
であり、ｘ’，ｙ’はそれぞれ８×８画素ブロックの
ｘ，ｙ座標方向のブロック番号、ｘ”，ｙ”はそれぞれ
８×８画素ブロック内の座標位置とすると、Ｏｆｆｓｅ
ｔ１（ｘ’，ｙ’）とＯｆｆｓｅｔ２（ｘ”，ｙ”）は
それぞれ、
【０１２１】
【数１５】 Ｏｆｆｓｅｔ１（ｘ’，ｙ’）＝６５５３６ｙ’＋８
ｘ’ Ｏｆｆｓｅｔ２（ｘ”，ｙ”）＝８１９２ｙ”＋ｘ” である。
ｘ’ Ｏｆｆｓｅｔ２（ｘ”，ｙ”）＝８１９２ｙ”＋ｘ” である。
【０１２２】変数ｘＢ，ｘ’，ｙ’，ｘ”，ｙ”の制御
アルゴリズムをＣ言語風に記述すると下記の様になる。
アルゴリズムをＣ言語風に記述すると下記の様になる。
【０１２３】
【数１６】
【０１２４】この様な順番で画素を読み出すことで、部
分画像内部の画素を後述の符号化手段２３のためのラス
タ・ブロック変換して読み出すことができる。
分画像内部の画素を後述の符号化手段２３のためのラス
タ・ブロック変換して読み出すことができる。
【０１２５】ｘＢカウンタ２２１はｙｉカウンタ２１４
の６４行入力完了通知により０にクリアされる。ｘＢの
カウントアップはｘＢカウンタ２２１が行う。部分画像
内の６４×６４画素を読み出すたびにｘＢの値は１増加
する。ｘＢの値は０から縮小後のソース画像の１走査線
上に乗る部分画像数Ｂｘより１つ小さな値までインクリ
メントされる。最後にｘＢ＝Ｂｘとなる時に、横１列分
の部分画像を出力し終えたことをｙＢカウンタ２２２に
通知する。ｘＢ＝Ｂｘのときには読み出しアドレスの生
成は行われない。その後ｙｉカウンタ２１４の６４行入
力完了通知がきて０にクリアされる。
の６４行入力完了通知により０にクリアされる。ｘＢの
カウントアップはｘＢカウンタ２２１が行う。部分画像
内の６４×６４画素を読み出すたびにｘＢの値は１増加
する。ｘＢの値は０から縮小後のソース画像の１走査線
上に乗る部分画像数Ｂｘより１つ小さな値までインクリ
メントされる。最後にｘＢ＝Ｂｘとなる時に、横１列分
の部分画像を出力し終えたことをｙＢカウンタ２２２に
通知する。ｘＢ＝Ｂｘのときには読み出しアドレスの生
成は行われない。その後ｙｉカウンタ２１４の６４行入
力完了通知がきて０にクリアされる。
【０１２６】ｙＢカウンタ２２２はソース画像の入力の
際に０にクリアされ、ｘＢカウンタ２２１が横１列分の
部分画像を出力し終えたことを通知する毎に値を＋１イ
ンクリメントする。
際に０にクリアされ、ｘＢカウンタ２２１が横１列分の
部分画像を出力し終えたことを通知する毎に値を＋１イ
ンクリメントする。
【０１２７】図１６に示すように縮小後のソース画像の
左上を原点として一致させて部分画像が配置される。部
分画像は縮小後のソース画像を覆う様に配置される。す
なわち、ＢｘはＷｉ−１＜６４Ｂｘを満たす最小の整数
となる。同様にＢｙはＨｉ−１＜６４Ｂｙを満たす最小
の整数となる。部分画像切り出しの順は左上隅の部分画
像よりまず横方向に切り出していき、右端まで達したら
１行下の部分画像を同様にきりだし、以降同様に最終行
まで行う。
左上を原点として一致させて部分画像が配置される。部
分画像は縮小後のソース画像を覆う様に配置される。す
なわち、ＢｘはＷｉ−１＜６４Ｂｘを満たす最小の整数
となる。同様にＢｙはＨｉ−１＜６４Ｂｙを満たす最小
の整数となる。部分画像切り出しの順は左上隅の部分画
像よりまず横方向に切り出していき、右端まで達したら
１行下の部分画像を同様にきりだし、以降同様に最終行
まで行う。
【０１２８】ｘＢカウンタとｙＢカウンタは部分画像
（ｘＢ，ｙＢ）の座標番号を示しており、出力画素とと
もに符号化手段２３に送られる。
（ｘＢ，ｙＢ）の座標番号を示しており、出力画素とと
もに符号化手段２３に送られる。
【０１２９】符号化手段２３は、ＪＰＥＧ（Ｊｏｉｎｔ
Ｐｈｏｔｏｇｒａｐｈｉｃ Ｅｘｐｅｒｔ Ｇｒｏｕ
ｐ）のベースライン・プロセス・アルゴリズムを用い
る。このアルゴリズムは画像を８×８画素のブロックに
分割し、ブロックに離散コサイン変換を施した後に量子
化をしハフマン符号化するものである。アルゴリズムと
実施の詳細に関しては例えばＣＱ出版発行の月刊誌イン
ターフェースの１９９１年１２月号１６０〜１８２ペー
ジに記載されているのでここでは説明を省略する。ＪＰ
ＥＧはスキャンドイメージの標準的な圧縮／伸張アルゴ
リズムであり、符号化することでデータ量を平均１／１
０に削減することができる。分割手段２２により行バッ
ファ２４より図１５に示す順に読み出された画素は符号
化手段１３に入力する。符号化手段は８×８画素ブロッ
ク単位に離散コサイン変換と量子化とハフマン符号化を
行う。符号出力はメモリ４に書き込まれる。メモリ４上
には図１７に示すように部分画像の座標番号（ｘＢ，ｙ
Ｂ）のテーブルが設けられている。符号はｌｉｎｋ部分
と符号格納部から構成される結合リスト構造のデータ構
造に格納される。このデータ構造のｌｉｎｋ部は４バイ
トで次のノードへのポインタが格納される。末端のノー
ドのｌｉｎｋ部には末端を示すマークとしてＮＵＬＬが
格納される。符号格納部は６０バイトである。１個のノ
ードの符号格納部に格納しきれない符号はｌｉｎｋ部が
指す次のノードの符号格納部に格納される。末端のノー
ドの符号格納部には未使用部分があるかもしれない。部
分画像符号の末端には符号の終わりを示す為のＥＯＣ
（Ｅｎｄ Ｏｆ Ｃｏｄｅ）符号が入る。符号化手段２
３は部分画像（ｘＢ，ｙＢ）の符号の生成の際に以下の
様に動作し、符号をメモリ４に格納していく。
Ｐｈｏｔｏｇｒａｐｈｉｃ Ｅｘｐｅｒｔ Ｇｒｏｕ
ｐ）のベースライン・プロセス・アルゴリズムを用い
る。このアルゴリズムは画像を８×８画素のブロックに
分割し、ブロックに離散コサイン変換を施した後に量子
化をしハフマン符号化するものである。アルゴリズムと
実施の詳細に関しては例えばＣＱ出版発行の月刊誌イン
ターフェースの１９９１年１２月号１６０〜１８２ペー
ジに記載されているのでここでは説明を省略する。ＪＰ
ＥＧはスキャンドイメージの標準的な圧縮／伸張アルゴ
リズムであり、符号化することでデータ量を平均１／１
０に削減することができる。分割手段２２により行バッ
ファ２４より図１５に示す順に読み出された画素は符号
化手段１３に入力する。符号化手段は８×８画素ブロッ
ク単位に離散コサイン変換と量子化とハフマン符号化を
行う。符号出力はメモリ４に書き込まれる。メモリ４上
には図１７に示すように部分画像の座標番号（ｘＢ，ｙ
Ｂ）のテーブルが設けられている。符号はｌｉｎｋ部分
と符号格納部から構成される結合リスト構造のデータ構
造に格納される。このデータ構造のｌｉｎｋ部は４バイ
トで次のノードへのポインタが格納される。末端のノー
ドのｌｉｎｋ部には末端を示すマークとしてＮＵＬＬが
格納される。符号格納部は６０バイトである。１個のノ
ードの符号格納部に格納しきれない符号はｌｉｎｋ部が
指す次のノードの符号格納部に格納される。末端のノー
ドの符号格納部には未使用部分があるかもしれない。部
分画像符号の末端には符号の終わりを示す為のＥＯＣ
（Ｅｎｄ Ｏｆ Ｃｏｄｅ）符号が入る。符号化手段２
３は部分画像（ｘＢ，ｙＢ）の符号の生成の際に以下の
様に動作し、符号をメモリ４に格納していく。
【０１３０】１） まず未使用のノードを１個取り出
し、そのアドレスを前記テーブルの場所（ｘＢ，ｙＢ）
に格納する。 ２） そのノードの符号格納部に符号を順に書き込んで
いく。 ３） もし符号格納部にＥＯＣ符号を書きおえたら、ノ
ードのｌｉｎｋ部にＮＵＬＬを書き込み部分画像（ｘ
Ｂ，ｙＢ）の符号符号書き込みは終了する。 ４） もしＥＯＣ符号を書きおえる前に符号格納部が一
杯になったら、新しい未使用ノードを１個とりだし、そ
のアドレスを現ノードのｌｉｎｋ部に書き込み、以降新
しいノードについてステップ２）へ行き処理を繰り返
す。
し、そのアドレスを前記テーブルの場所（ｘＢ，ｙＢ）
に格納する。 ２） そのノードの符号格納部に符号を順に書き込んで
いく。 ３） もし符号格納部にＥＯＣ符号を書きおえたら、ノ
ードのｌｉｎｋ部にＮＵＬＬを書き込み部分画像（ｘ
Ｂ，ｙＢ）の符号符号書き込みは終了する。 ４） もしＥＯＣ符号を書きおえる前に符号格納部が一
杯になったら、新しい未使用ノードを１個とりだし、そ
のアドレスを現ノードのｌｉｎｋ部に書き込み、以降新
しいノードについてステップ２）へ行き処理を繰り返
す。
【０１３１】このようにすることで、可変長符号を効率
よくメモリ４に格納出来、かつ、簡単に部分画像の符号
を読み出すことができる。
よくメモリ４に格納出来、かつ、簡単に部分画像の符号
を読み出すことができる。
【０１３２】符号化手段２３は、更に、部分画像（ｘ
Ｂ，ｙＢ）の符号化を行う際にはメモリ４に格納された
重なり情報１４のテーブル（図７参照）を参照し、（ｘ
Ｂ，ｙＢ）に対応する要素が１の時すなわち論理的に真
の時にのみ符号化を行い、０すなわち偽のときには分割
手段２２から供給される画素を捨てる。この場合図８に
示されるテーブルの該当箇所には符号が無いことを意味
するＮＵＬＬが書き込まれる。
Ｂ，ｙＢ）の符号化を行う際にはメモリ４に格納された
重なり情報１４のテーブル（図７参照）を参照し、（ｘ
Ｂ，ｙＢ）に対応する要素が１の時すなわち論理的に真
の時にのみ符号化を行い、０すなわち偽のときには分割
手段２２から供給される画素を捨てる。この場合図８に
示されるテーブルの該当箇所には符号が無いことを意味
するＮＵＬＬが書き込まれる。
【０１３３】復号化手段２５は、走査線番号Ｙを参照
し、メモリ４に格納された復号順情報１５の該走査線に
関連する部分画像番号（ｘＢ，ｙＢ）を読み出す。メモ
リ４に格納された部分画像の符号１７のテーブル（図１
７参照）から（ｘＢ，ｙＢ）を利用して該部分画像の符
号の結合リスト構造体をアクセスする。結合リスト構造
体のノード部分の符号格納部より符号を読み、ＪＰＥＧ
ベースライン・アルゴリズムの復号器に符号を供給す
る。ノードのｌｉｎｋ部がＮＵＬＬならば符号格納部の
６０バイトを復号器に供給した後、該部分画像の符号の
復号を終える。ノード部がＮＵＬＬではないならば符号
格納部の６０バイト全てを復号器に供給した後、ｌｉｎ
ｋ部をたどり次のノードについて同様の処理を行う。ｌ
ｉｎｋ部がＮＵＬＬの場合復号器は符号格納分の６０バ
イトのデコード途中でＥＯＣ符号を発見する。復号器は
ＥＯＣ符号後のデータを捨てる。復号化手段２５は６４
×６４画素の部分画像の画素を得て、メモリ２８に格納
する。
し、メモリ４に格納された復号順情報１５の該走査線に
関連する部分画像番号（ｘＢ，ｙＢ）を読み出す。メモ
リ４に格納された部分画像の符号１７のテーブル（図１
７参照）から（ｘＢ，ｙＢ）を利用して該部分画像の符
号の結合リスト構造体をアクセスする。結合リスト構造
体のノード部分の符号格納部より符号を読み、ＪＰＥＧ
ベースライン・アルゴリズムの復号器に符号を供給す
る。ノードのｌｉｎｋ部がＮＵＬＬならば符号格納部の
６０バイトを復号器に供給した後、該部分画像の符号の
復号を終える。ノード部がＮＵＬＬではないならば符号
格納部の６０バイト全てを復号器に供給した後、ｌｉｎ
ｋ部をたどり次のノードについて同様の処理を行う。ｌ
ｉｎｋ部がＮＵＬＬの場合復号器は符号格納分の６０バ
イトのデコード途中でＥＯＣ符号を発見する。復号器は
ＥＯＣ符号後のデータを捨てる。復号化手段２５は６４
×６４画素の部分画像の画素を得て、メモリ２８に格納
する。
【０１３４】座標変換手段２６の構成を図１８に示す。
図１８に示すように座標変換手段２６は、４個の乗算器
２６０１，２６０２，２６０３，２６０４と、６個の加
算器２６０５，２６０６，２６０７，２６０８，２６１
３，２６１４と、２個のセレクタ２６０９，２６１０
と、２個のレジスタ２６１１，２６１２と、減算器２６
１５と、ダウンカウンタ２６１６と、制御回路２６１７
とを備えている。座標変換手段２６は、逆変換すなわち
デバイス空間からソース空間への座標変換のパラメータ
（ａ’，ｂ’，ｃ’，ｄ’，ｕ’，ｖ’）を入力する。
これらパラメータはインタプリタ１０がアフィン変換の
パラメータより計算して座標変換手段２６に供給する。
座標変換手段２６は、更に、セグメントのＹ座標値Ｙ、
セグメントの左端Ｘ座標値Ｘ０、右端Ｘ座標値Ｘ１を入
力する。
図１８に示すように座標変換手段２６は、４個の乗算器
２６０１，２６０２，２６０３，２６０４と、６個の加
算器２６０５，２６０６，２６０７，２６０８，２６１
３，２６１４と、２個のセレクタ２６０９，２６１０
と、２個のレジスタ２６１１，２６１２と、減算器２６
１５と、ダウンカウンタ２６１６と、制御回路２６１７
とを備えている。座標変換手段２６は、逆変換すなわち
デバイス空間からソース空間への座標変換のパラメータ
（ａ’，ｂ’，ｃ’，ｄ’，ｕ’，ｖ’）を入力する。
これらパラメータはインタプリタ１０がアフィン変換の
パラメータより計算して座標変換手段２６に供給する。
座標変換手段２６は、更に、セグメントのＹ座標値Ｙ、
セグメントの左端Ｘ座標値Ｘ０、右端Ｘ座標値Ｘ１を入
力する。
【０１３５】乗算器２６０１，２６０２と加算器２６０
５，２６０７とは図１１に示す様に接続されており、こ
れらを用いて、
５，２６０７とは図１１に示す様に接続されており、こ
れらを用いて、
【０１３６】
【数１７】ｘ０＝ａ’・Ｘ０＋ｂ’・Ｙ＋ｕ’ を求める。
【０１３７】また、乗算器２６０３，２６０４と加算器
２６０６，２６０８とは図１８に示す様に接続されてお
り、これらを用いて、
２６０６，２６０８とは図１８に示す様に接続されてお
り、これらを用いて、
【０１３８】
【数１８】ｙ０＝ｃ’・Ｘ０＋ｄ’・Ｙ＋ｖ’ を求める。（ｘ０，ｙ０）はセグメントの左端点（Ｘ
０，Ｙ）をソース空間上に逆変換した座標である。
０，Ｙ）をソース空間上に逆変換した座標である。
【０１３９】制御回路２６１７は、セグメントの左端点
（Ｘ０，Ｙ）が入力され（ｘ０，ｙ０）が計算された時
に、セレクタ２６０９と２６１０を制御し、ｘ０とｙ０
の値をそれぞれレジスタ２６１１と２６１２にロードす
るよう制御する。レジスタ２６１１は座標変換後のソー
ス空間のｘ座標、レジスタ２６１２は座標変換後のソー
ス空間のｙ座標を保持し、それぞれの出力をアドレス変
換手段２７へ出力する。デバイス空間での右方向への１
画素の移動すなわちベクトル（１，０）の移動は、ソー
ス空間ではベクトル（ａ’，ｃ’）の移動に相当する。
そこで、加算器２６１３を用いてレジスタ２６１１の値
とａ’とを加えることで次の画素のｘ座標値を、加算器
２６１４を用いてレジスタ２６１２の値と’とを加える
ことで次の画素の座標値を求めることできる。
（Ｘ０，Ｙ）が入力され（ｘ０，ｙ０）が計算された時
に、セレクタ２６０９と２６１０を制御し、ｘ０とｙ０
の値をそれぞれレジスタ２６１１と２６１２にロードす
るよう制御する。レジスタ２６１１は座標変換後のソー
ス空間のｘ座標、レジスタ２６１２は座標変換後のソー
ス空間のｙ座標を保持し、それぞれの出力をアドレス変
換手段２７へ出力する。デバイス空間での右方向への１
画素の移動すなわちベクトル（１，０）の移動は、ソー
ス空間ではベクトル（ａ’，ｃ’）の移動に相当する。
そこで、加算器２６１３を用いてレジスタ２６１１の値
とａ’とを加えることで次の画素のｘ座標値を、加算器
２６１４を用いてレジスタ２６１２の値と’とを加える
ことで次の画素の座標値を求めることできる。
【０１４０】減算器２６１５はＸ１とＸ０を入力し、セ
グメントの両端のＸ座標値の差を取り、セグメント長に
関する情報Ｘ１−Ｘ０を得、ダウンカウンタ２６１６に
供給する。ダウンカウンタ２６１６は値を調べ、値が０
より大きい間カウンタの値を１づつ減らしていき、０の
場合には信号ｚｅｒｏに１を出力し、値を０のまま保
つ。ダウンカウンタ２６１６はセグメント上の画素数分
の繰り返しを制御するために用いる。信号ｚｅｒｏ＝１
の時はセグメントの右端画素を処理していることを意味
し、制御回路は新たなセグメントのデータが入力される
まで処理をｘとｙの生成を停止するよう制御信号を生成
する。
グメントの両端のＸ座標値の差を取り、セグメント長に
関する情報Ｘ１−Ｘ０を得、ダウンカウンタ２６１６に
供給する。ダウンカウンタ２６１６は値を調べ、値が０
より大きい間カウンタの値を１づつ減らしていき、０の
場合には信号ｚｅｒｏに１を出力し、値を０のまま保
つ。ダウンカウンタ２６１６はセグメント上の画素数分
の繰り返しを制御するために用いる。信号ｚｅｒｏ＝１
の時はセグメントの右端画素を処理していることを意味
し、制御回路は新たなセグメントのデータが入力される
まで処理をｘとｙの生成を停止するよう制御信号を生成
する。
【０１４１】座標変換手段２６は、０からＨＤ−１まで
１づつ増加する走査線番号Ｙを受けて、各走査線毎にメ
モリ４に格納された描画情報１６から該走査線に関連す
るセグメント情報を、走査線の左端のセグメントから右
隣のセグメントへ順次読み出す。走査線上のセグメント
情報は既に説明したように結合リスト形式のデータ構造
で表現されており、左セグメントから右セグメントへポ
インタで結合している。配列ｄｅｖＩｍａｇｅは走査線
番号をインデックスとしてアクセスする配列で、各要素
にはその走査線の左端のセグメントに関連するノードへ
のポインタが格納されている。走査線上のセグメントの
座標変換手段は以下の手順で動作する。
１づつ増加する走査線番号Ｙを受けて、各走査線毎にメ
モリ４に格納された描画情報１６から該走査線に関連す
るセグメント情報を、走査線の左端のセグメントから右
隣のセグメントへ順次読み出す。走査線上のセグメント
情報は既に説明したように結合リスト形式のデータ構造
で表現されており、左セグメントから右セグメントへポ
インタで結合している。配列ｄｅｖＩｍａｇｅは走査線
番号をインデックスとしてアクセスする配列で、各要素
にはその走査線の左端のセグメントに関連するノードへ
のポインタが格納されている。走査線上のセグメントの
座標変換手段は以下の手順で動作する。
【０１４２】１．走査線番号Ｙを用いてｄｅｖＩｍａｇ
ｅ［Ｙ］を読み出し左端のセグメントのノードのアドレ
スを得る。
ｅ［Ｙ］を読み出し左端のセグメントのノードのアドレ
スを得る。
【０１４３】２．該ノードのアドレスを利用し該ノード
の内容を読む。これによりノードの左端Ｘ座標Ｘ０、右
端Ｘ座標Ｘ１、ポインタｐｐ、フラグｄｐ、右隣のノー
ドへのポインタｎｅｘｔを得る。
の内容を読む。これによりノードの左端Ｘ座標Ｘ０、右
端Ｘ座標Ｘ１、ポインタｐｐ、フラグｄｐ、右隣のノー
ドへのポインタｎｅｘｔを得る。
【０１４４】３．フラグｄｐが０ならば、該ノードはラ
インアートのノードであり、ポインタｐｐでメモリ４を
アクセスして画素の値Ｐを得て、データのセット（Ｘ１
−Ｘ０＋１，Ｐ）を画像出力手段２９に供給する。Ｘ１
−Ｘ０＋１はセグメント長である。
インアートのノードであり、ポインタｐｐでメモリ４を
アクセスして画素の値Ｐを得て、データのセット（Ｘ１
−Ｘ０＋１，Ｐ）を画像出力手段２９に供給する。Ｘ１
−Ｘ０＋１はセグメント長である。
【０１４５】フラグｄｐが０でないならば、該ノードは
スキャンドイメージのノードであるので、既に説明した
手段でデバイス空間座標からソース空間座標に変換した
Ｘ１−Ｘ０＋１個の座標値をアドレス変換手段２７に供
給し、ポインタｐｐの値もアドレス変換手段２７に供給
する。
スキャンドイメージのノードであるので、既に説明した
手段でデバイス空間座標からソース空間座標に変換した
Ｘ１−Ｘ０＋１個の座標値をアドレス変換手段２７に供
給し、ポインタｐｐの値もアドレス変換手段２７に供給
する。
【０１４６】４． ポインタｎｅｘｔを調べる。ＮＵＬ
Ｌならば右側にセグメントは無いので処理を終了する。
ＮＵＬＬでないならばｎｅｔｘｔの値を新たなノードの
アドレスとし、上記処理ステップ２へ行く。
Ｌならば右側にセグメントは無いので処理を終了する。
ＮＵＬＬでないならばｎｅｔｘｔの値を新たなノードの
アドレスとし、上記処理ステップ２へ行く。
【０１４７】１本の走査線上のセグメントの座標変換が
終わったら、座標変換手段２６は走査線信号Ｙにより次
の走査線に関するセグメントの座標変換を指示されるの
を待つ。
終わったら、座標変換手段２６は走査線信号Ｙにより次
の走査線に関するセグメントの座標変換を指示されるの
を待つ。
【０１４８】メモリ２８にはデバイス画像の出力中の走
査線と重なり合う部分画像が格納される。図１９に示す
ようにメモリ２８には更に部分画像の座標（ｘＢ，ｙ
Ｂ）と部分画像が格納されているアドレスを結び付ける
アドレス変換テーブル２８０が格納されている。アドレ
ス変換テーブル２８０はｘＢとｙＢを用いてアクセスす
るテーブルで、そこにはメモリ２８に格納されている部
分画像（ｘＢ，ｙＢ）のアドレスが格納されている。ア
ドレス変換手段２７は、座標変換手段２６より、デバイ
ス空間の画素毎にポインタｐｐの値と座標変換後のソー
ス空間での座標値（ｘ，ｙ）とを入力する。画素の座標
（ｘ，ｙ）から該画素が属する部分画像（ｘＢ，ｙＢ）
を決定するのは容易である。ｘ，ｙをそれぞれ６４で割
って商をｘＢ，ｙＢとすればよい。部分画像内の画素の
座標位置（ｘｏｆｆｓｅｔ，ｙｏｆｆｓｅｔ）はｘ，ｙ
をそれぞれ６４で割ったときの余りをｘｏｆｆｓｅｔ，
ｙｏｆｆｓｅｔとする。具体的には、ｘの下位６ｂｉｔ
をｘｏｆｆｓｅｔとし、残りの上位ｂｉｔをｘＢとす
る。同様にｙの下位６ｂｉｔをｙｏｆｆｓｅｔとし、残
りの上位ｂｉｔをｙＢとする。
査線と重なり合う部分画像が格納される。図１９に示す
ようにメモリ２８には更に部分画像の座標（ｘＢ，ｙ
Ｂ）と部分画像が格納されているアドレスを結び付ける
アドレス変換テーブル２８０が格納されている。アドレ
ス変換テーブル２８０はｘＢとｙＢを用いてアクセスす
るテーブルで、そこにはメモリ２８に格納されている部
分画像（ｘＢ，ｙＢ）のアドレスが格納されている。ア
ドレス変換手段２７は、座標変換手段２６より、デバイ
ス空間の画素毎にポインタｐｐの値と座標変換後のソー
ス空間での座標値（ｘ，ｙ）とを入力する。画素の座標
（ｘ，ｙ）から該画素が属する部分画像（ｘＢ，ｙＢ）
を決定するのは容易である。ｘ，ｙをそれぞれ６４で割
って商をｘＢ，ｙＢとすればよい。部分画像内の画素の
座標位置（ｘｏｆｆｓｅｔ，ｙｏｆｆｓｅｔ）はｘ，ｙ
をそれぞれ６４で割ったときの余りをｘｏｆｆｓｅｔ，
ｙｏｆｆｓｅｔとする。具体的には、ｘの下位６ｂｉｔ
をｘｏｆｆｓｅｔとし、残りの上位ｂｉｔをｘＢとす
る。同様にｙの下位６ｂｉｔをｙｏｆｆｓｅｔとし、残
りの上位ｂｉｔをｙＢとする。
【０１４９】描画情報生成手段１１はスキャンドイメー
ジのセグメントのノードのポインタｐｐにアドレス変換
テーブル２８０のアドレスを格納するよう動作する。従
ってアドレス変換手段２７は座標変換手段により渡され
たポインタｐｐを用いてメモリ２８内のアドレス変換テ
ーブルの場所を知る。（ｘ，ｙ）より得た（ｘＢ，ｙ
Ｂ）を用いてアドレス変換テーブルの該エントリを読み
出し、メモリ２８にある該部分画像のベースアドレスを
得る。ベースアドレスと（ｘｏｆｆｓｅｔ，ｙｏｆｆｓ
ｅｔ）を用いて該画素のアドレスを決定し、メモリ２８
の該アドレスを読み出す。読み出された画素は画像出力
手段２９に送られる。
ジのセグメントのノードのポインタｐｐにアドレス変換
テーブル２８０のアドレスを格納するよう動作する。従
ってアドレス変換手段２７は座標変換手段により渡され
たポインタｐｐを用いてメモリ２８内のアドレス変換テ
ーブルの場所を知る。（ｘ，ｙ）より得た（ｘＢ，ｙ
Ｂ）を用いてアドレス変換テーブルの該エントリを読み
出し、メモリ２８にある該部分画像のベースアドレスを
得る。ベースアドレスと（ｘｏｆｆｓｅｔ，ｙｏｆｆｓ
ｅｔ）を用いて該画素のアドレスを決定し、メモリ２８
の該アドレスを読み出す。読み出された画素は画像出力
手段２９に送られる。
【０１５０】図１９は、走査線Ｙ上のスキャンドイメー
ジのセグメントが部分画像（０，２），（１，２），
（１，１），（２，１），（２，０）を通る時のメモリ
２８の内容を模式的に示している。
ジのセグメントが部分画像（０，２），（１，２），
（１，１），（２，１），（２，０）を通る時のメモリ
２８の内容を模式的に示している。
【０１５１】画像出力手段２９は、セグメントがスキャ
ンドイメージに由来する場合、アドレス変換手段２８に
よってメモリ２８から読み出された画素をそのまま出力
する。セグメントがラインアートに由来する場合、画像
変換手段２６から得た画素情報Ｐとセグメントの長さＬ
を用いて、画素値ＰをＬ回出力する。画像出力手段２９
からはデバイス画像の画素がラスタスキャン順に出力さ
れ、出力画素はＩＯＴに送られ、紙やＣＲＴ上に画像を
形成する。
ンドイメージに由来する場合、アドレス変換手段２８に
よってメモリ２８から読み出された画素をそのまま出力
する。セグメントがラインアートに由来する場合、画像
変換手段２６から得た画素情報Ｐとセグメントの長さＬ
を用いて、画素値ＰをＬ回出力する。画像出力手段２９
からはデバイス画像の画素がラスタスキャン順に出力さ
れ、出力画素はＩＯＴに送られ、紙やＣＲＴ上に画像を
形成する。
【０１５２】ここで改めて縮小手段２１の用途を説明す
る。図２１のａに示すようなソース画像を仮定する。説
明のためにこのソース画像は８×８画素のサイズとす
る。このソース画像を−４５°の回転とｘ，ｙ両方向と
も１／（２√２）の縮小を行いデバイス画像に描画する
ものとする。その際のデバイス空間での走査線を逆変換
した直線が図２１ａの斜めの直線である。直線上の黒点
はデバイス空間の画素の位置、すなわち、逆サンプリン
グの際にデバイス画像のセグメントを逆変換しソース画
像の画素をサンプリングする場所である。この例のよう
に縮小率が１／２よりも大きい場合、ソース画像上の飛
び飛びの位置の画素のみが読み出される。図２１ａの例
では、ソース画像には合計６４画素あるが、サンプリン
グされてデバイス画像の形成に寄与する画素は８画素の
みである。全画素の７／８は無駄である。これら無駄な
画素を沢山含む部分画像を行バッファ２４から読み出し
符号化手段２３で符号化し符号をメモリ４に格納する
と、行バッファ２４からの読み出し時間が余分にかか
り、符号化手段２３での処理時間が長くなり、符号サイ
ズも大きくなるのでメモリ４への書き込み時間も長くな
り、部分画像の符号１７格納の為の領域も多く必要であ
る。また、メモリ４からの符号の読み出し時間も長くな
り、復号化手段２５での処理時間も長くなる。また、走
査線上のスキャンドイメージのセグメントはより多くの
部分画像と重なる為、メモリ２８にはより多くの部分画
像を格納せねばならず、メモリ２８のサイズを大きくせ
ねばならない。すなわち、メモリサイズが大きくなりコ
ストが増大するという問題と処理時間が長くなるという
問題が発生する。この問題はアフィン変換の縮小率が大
きいほど深刻になる。
る。図２１のａに示すようなソース画像を仮定する。説
明のためにこのソース画像は８×８画素のサイズとす
る。このソース画像を−４５°の回転とｘ，ｙ両方向と
も１／（２√２）の縮小を行いデバイス画像に描画する
ものとする。その際のデバイス空間での走査線を逆変換
した直線が図２１ａの斜めの直線である。直線上の黒点
はデバイス空間の画素の位置、すなわち、逆サンプリン
グの際にデバイス画像のセグメントを逆変換しソース画
像の画素をサンプリングする場所である。この例のよう
に縮小率が１／２よりも大きい場合、ソース画像上の飛
び飛びの位置の画素のみが読み出される。図２１ａの例
では、ソース画像には合計６４画素あるが、サンプリン
グされてデバイス画像の形成に寄与する画素は８画素の
みである。全画素の７／８は無駄である。これら無駄な
画素を沢山含む部分画像を行バッファ２４から読み出し
符号化手段２３で符号化し符号をメモリ４に格納する
と、行バッファ２４からの読み出し時間が余分にかか
り、符号化手段２３での処理時間が長くなり、符号サイ
ズも大きくなるのでメモリ４への書き込み時間も長くな
り、部分画像の符号１７格納の為の領域も多く必要であ
る。また、メモリ４からの符号の読み出し時間も長くな
り、復号化手段２５での処理時間も長くなる。また、走
査線上のスキャンドイメージのセグメントはより多くの
部分画像と重なる為、メモリ２８にはより多くの部分画
像を格納せねばならず、メモリ２８のサイズを大きくせ
ねばならない。すなわち、メモリサイズが大きくなりコ
ストが増大するという問題と処理時間が長くなるという
問題が発生する。この問題はアフィン変換の縮小率が大
きいほど深刻になる。
【０１５３】縮小手段２１は、アフィン変換の縮小率が
大きい場合に用いる。図２１ｂは縮小手段２１にｎｘ＝
２，ｎｙ＝２を設定し図２１ａのソース画像をｘ方向に
１／２、ｙ方向に１／２に縮小して得た縮小後のソース
が像である。縮小手段２１で縮小を行った場合、インタ
プリタ１０と描画情報生成手段１１は縮小手段２１での
縮小を考慮し、縮小後のソース画像をあたかもソース画
像と見なして描画情報１６等を作成し、座標変換手段２
６に供給する逆変換パラメータ（ａ’，ｂ’，ｃ’，
ｄ’，ｕ’，ｖ’）を決定する。図２１ｂの縮小画像で
は合計１６個の画素の内８個の画素がデバイス画像の描
画に寄与する。このため、ソース画像の縮小を行わない
場合に比べ、処理時間は短縮し、符号と部分画像を格納
するためのメモリ領域も小さくすることができる。
大きい場合に用いる。図２１ｂは縮小手段２１にｎｘ＝
２，ｎｙ＝２を設定し図２１ａのソース画像をｘ方向に
１／２、ｙ方向に１／２に縮小して得た縮小後のソース
が像である。縮小手段２１で縮小を行った場合、インタ
プリタ１０と描画情報生成手段１１は縮小手段２１での
縮小を考慮し、縮小後のソース画像をあたかもソース画
像と見なして描画情報１６等を作成し、座標変換手段２
６に供給する逆変換パラメータ（ａ’，ｂ’，ｃ’，
ｄ’，ｕ’，ｖ’）を決定する。図２１ｂの縮小画像で
は合計１６個の画素の内８個の画素がデバイス画像の描
画に寄与する。このため、ソース画像の縮小を行わない
場合に比べ、処理時間は短縮し、符号と部分画像を格納
するためのメモリ領域も小さくすることができる。
【０１５４】［実施例２］第２の実施例のブロック図を
図２０に示す。本実施例はＩＩＴ（画像入力装置）で入
力したラスタ画像を０°もしくは９０°回転し、拡大／
縮小してＩＯＴに出力する為の装置（複写機）に実施し
たものである。本実施例は第１の実施例と似ているが、
入力画像は直接画像入力手段２０に供給される。また、
メモリ４には描画情報生成手段１１と符号順決定手段１
３のためのプログラムが格納されている。ＣＰＵが前者
のプログラムを実行すると、描画情報１６がメモリ４に
格納される。ＣＰＵ１が後者プログラムを実行すると、
復号順情報１５が作成され、メモリ４に格納される。
図２０に示す。本実施例はＩＩＴ（画像入力装置）で入
力したラスタ画像を０°もしくは９０°回転し、拡大／
縮小してＩＯＴに出力する為の装置（複写機）に実施し
たものである。本実施例は第１の実施例と似ているが、
入力画像は直接画像入力手段２０に供給される。また、
メモリ４には描画情報生成手段１１と符号順決定手段１
３のためのプログラムが格納されている。ＣＰＵが前者
のプログラムを実行すると、描画情報１６がメモリ４に
格納される。ＣＰＵ１が後者プログラムを実行すると、
復号順情報１５が作成され、メモリ４に格納される。
【０１５５】拡大／縮小率と回転角は複写機のパネルの
ボタンによって指定される。これら情報はＩ／Ｏ手段２
を通じて入力しする。
ボタンによって指定される。これら情報はＩ／Ｏ手段２
を通じて入力しする。
【０１５６】描画情報生成手段１１は拡大／縮小率と回
転角をもとに出力画像の形状を計算し、セグメント情報
を作成し描画情報１６としてメモリ４に格納する。第２
の実施例では、デバイス画像には、上下左右のマージン
部分の白い領域とデバイス画像中央部に位置する入力し
たスキャンドイメージとが描画される。上マージンと下
マージン部分のの各走査線には幅がＷＤの白セグメント
が１個のみ存在する。それ以外の部分の各走査線には、
３個のセグメントが存在し、左端セグメントは左マージ
ンの幅を持った白セグメント、真ん中のセグメントは入
力画像として入力したスキャンドイメージのセグメン
ト、右端セグメントは右マージンの幅を持った白セグメ
ントである。描画情報生成手段１１は、更に、拡大／縮
小率と回転角とから縮小手段の縮小率ｎｘとｎｙと逆変
換パラメータ（ａ’，ｂ’，ｃ’，ｄ’，ｕ’，ｖ’）
を計算し、ｎｘとｎｙを縮小手段２１に設定し、逆変換
パラメータを座標変換手段２６に設定する。
転角をもとに出力画像の形状を計算し、セグメント情報
を作成し描画情報１６としてメモリ４に格納する。第２
の実施例では、デバイス画像には、上下左右のマージン
部分の白い領域とデバイス画像中央部に位置する入力し
たスキャンドイメージとが描画される。上マージンと下
マージン部分のの各走査線には幅がＷＤの白セグメント
が１個のみ存在する。それ以外の部分の各走査線には、
３個のセグメントが存在し、左端セグメントは左マージ
ンの幅を持った白セグメント、真ん中のセグメントは入
力画像として入力したスキャンドイメージのセグメン
ト、右端セグメントは右マージンの幅を持った白セグメ
ントである。描画情報生成手段１１は、更に、拡大／縮
小率と回転角とから縮小手段の縮小率ｎｘとｎｙと逆変
換パラメータ（ａ’，ｂ’，ｃ’，ｄ’，ｕ’，ｖ’）
を計算し、ｎｘとｎｙを縮小手段２１に設定し、逆変換
パラメータを座標変換手段２６に設定する。
【０１５７】復号順決定手段１３は回転角をもとに復号
順を決定する。０°の回転の場合、まずＢｘ個の部分画
像（ｎ，０）（ｎ＝０からＢｘ−１まで）を復号し、そ
の後順次各６４ライン間にＢｘ個の部分画像（ｎ，１）
（ｎ＝０からＢｘ−１まで）、部分画像（ｎ，２）（ｎ
＝０からＢｘ−１まで）、部分画像（ｎ，３）（ｎ＝０
からＢｘ−１まで）、を復号し、最後に部分画像（ｎ，
Ｂｙ−１）（ｎ＝０からＢｘ−１まで）を復号するの
で、以上の順番と走査線番号とを復号順情報１５として
メモリ手段４に格納する。９０°の回転の場合、まずＢ
ｙ個の部分画像（Ｂｘ−１，ｎ）（ｎ＝０からＢｙ−１
まで）を復号し、その後順次各６４ライン間にＢｙ個の
部分画像（Ｂｘ−２，ｎ）（ｎ＝０からＢｙ−１ま
で）、部分画像（Ｂｘ−３，ｎ）（ｎ＝０からＢｙ−１
まで）、部分画像（Ｂｘ−４，ｎ）（ｎ＝０からＢｙ−
１まで）、を復号し、最後に部分画像（０，ｎ）（ｎ＝
０からＢｙ−１まで）を復号するので、以上の順番と走
査線番号とを復号順情報１５としてメモリ手段４に格納
する。
順を決定する。０°の回転の場合、まずＢｘ個の部分画
像（ｎ，０）（ｎ＝０からＢｘ−１まで）を復号し、そ
の後順次各６４ライン間にＢｘ個の部分画像（ｎ，１）
（ｎ＝０からＢｘ−１まで）、部分画像（ｎ，２）（ｎ
＝０からＢｘ−１まで）、部分画像（ｎ，３）（ｎ＝０
からＢｘ−１まで）、を復号し、最後に部分画像（ｎ，
Ｂｙ−１）（ｎ＝０からＢｘ−１まで）を復号するの
で、以上の順番と走査線番号とを復号順情報１５として
メモリ手段４に格納する。９０°の回転の場合、まずＢ
ｙ個の部分画像（Ｂｘ−１，ｎ）（ｎ＝０からＢｙ−１
まで）を復号し、その後順次各６４ライン間にＢｙ個の
部分画像（Ｂｘ−２，ｎ）（ｎ＝０からＢｙ−１ま
で）、部分画像（Ｂｘ−３，ｎ）（ｎ＝０からＢｙ−１
まで）、部分画像（Ｂｘ−４，ｎ）（ｎ＝０からＢｙ−
１まで）、を復号し、最後に部分画像（０，ｎ）（ｎ＝
０からＢｙ−１まで）を復号するので、以上の順番と走
査線番号とを復号順情報１５としてメモリ手段４に格納
する。
【０１５８】ＩＩＴにて原稿をスキャンして作ったラス
タデータは入力画像として画像入力手段２０に供給され
る。画像入力手段２０は入力した画像データを縮小手段
２１に供給する。縮小手段２１と行バッファ２４と分割
手段２２は第１の実施例で説明したのと同様に作用し、
部分画像を切り出し画素を符号化手段２３に順次供給す
る。
タデータは入力画像として画像入力手段２０に供給され
る。画像入力手段２０は入力した画像データを縮小手段
２１に供給する。縮小手段２１と行バッファ２４と分割
手段２２は第１の実施例で説明したのと同様に作用し、
部分画像を切り出し画素を符号化手段２３に順次供給す
る。
【０１５９】符号化手段２３は部分画像を無条件に符号
化し部分画像の符号１７をメモリ４に格納する。複写機
では入力したスキャンドイメージの全てを出力すること
が殆どなので、選択的に部分画像の符号化を行っても符
号化を省略できる部分画像はほとんど無い。そこで、第
２の実施例の符号化手段２３では選択的な符号化を行わ
ない。符号化アルゴリズムおよび符号のメモリ４への書
き込み方は第１の実施例で説明したのと同じである。
化し部分画像の符号１７をメモリ４に格納する。複写機
では入力したスキャンドイメージの全てを出力すること
が殆どなので、選択的に部分画像の符号化を行っても符
号化を省略できる部分画像はほとんど無い。そこで、第
２の実施例の符号化手段２３では選択的な符号化を行わ
ない。符号化アルゴリズムおよび符号のメモリ４への書
き込み方は第１の実施例で説明したのと同じである。
【０１６０】復号手段２５、座標変換手段２６、アドレ
ス変換手段２７、メモリ２８、画像出力手段２９は第１
の実施例と同じ構成を持ち、これらは第１の実施例と同
様に動作する。すなわち、復号順情報１５を読み、デバ
イス画像の出力用走査線番号Ｙに同期して部分画像の符
号を復号しメモリ２８に格納する。同時に走査線番号Ｙ
の走査線上のセグメントの情報を描画情報１６より読み
出し、座標変換手段２７でセグメントをソース空間での
画素座標に変換し、アドレス変換手段２７で画素座標を
メモリ２８のアドレスに変換し、そのアドレスを用いて
メモリ２８に格納されている部分画像の画素を読み出し
画像出力手段２９に供給し、出力画像としてＩＯＴに出
力する。
ス変換手段２７、メモリ２８、画像出力手段２９は第１
の実施例と同じ構成を持ち、これらは第１の実施例と同
様に動作する。すなわち、復号順情報１５を読み、デバ
イス画像の出力用走査線番号Ｙに同期して部分画像の符
号を復号しメモリ２８に格納する。同時に走査線番号Ｙ
の走査線上のセグメントの情報を描画情報１６より読み
出し、座標変換手段２７でセグメントをソース空間での
画素座標に変換し、アドレス変換手段２７で画素座標を
メモリ２８のアドレスに変換し、そのアドレスを用いて
メモリ２８に格納されている部分画像の画素を読み出し
画像出力手段２９に供給し、出力画像としてＩＯＴに出
力する。
【０１６１】［実施例３］第３の実施例では、図２３に
示すようにメモリ２８にソース画像毎にアドレス変換テ
ーブルを設ける。図２４の走査線Ｙ１上のセグメントは
図２５に例示するような形で描画情報としてメモリ４に
格納されている。
示すようにメモリ２８にソース画像毎にアドレス変換テ
ーブルを設ける。図２４の走査線Ｙ１上のセグメントは
図２５に例示するような形で描画情報としてメモリ４に
格納されている。
【０１６２】第３の実施例の座標変換手段２６のブロッ
ク図を図２６に示す。新たにＣＡＭ（Ｃｏｎｔｅｎｔ
Ａｄｄｒｅｓｓ Ｍｅｍｏｒｙ）手段２６１８が設けら
れている。ＣＡＭ手段２６１８の入力には描画情報１６
から読み出したセグメントのノードのｐｐの値（アドレ
ス変換テーブルのアドレス）が入力し、ＣＡＭ手段２６
１８の出力から逆変換パラメータ（ａ’，ｂ’，ｃ’，
ｄ’，ｕ’，ｖ’）が供給されるよう構成されている。
ＣＡＭ手段のエントリのタグ部にはソース画像に対応す
るアドレス変換テーブルのアドレスが格納され、データ
部には逆変換パラメータが格納されている。ＣＡＭ手段
は入力されたｐｐの値と各エントリのタグ部との一致を
調べ、一致したエントリのデータ部を出力する。
ク図を図２６に示す。新たにＣＡＭ（Ｃｏｎｔｅｎｔ
Ａｄｄｒｅｓｓ Ｍｅｍｏｒｙ）手段２６１８が設けら
れている。ＣＡＭ手段２６１８の入力には描画情報１６
から読み出したセグメントのノードのｐｐの値（アドレ
ス変換テーブルのアドレス）が入力し、ＣＡＭ手段２６
１８の出力から逆変換パラメータ（ａ’，ｂ’，ｃ’，
ｄ’，ｕ’，ｖ’）が供給されるよう構成されている。
ＣＡＭ手段のエントリのタグ部にはソース画像に対応す
るアドレス変換テーブルのアドレスが格納され、データ
部には逆変換パラメータが格納されている。ＣＡＭ手段
は入力されたｐｐの値と各エントリのタグ部との一致を
調べ、一致したエントリのデータ部を出力する。
【０１６３】インタプリタ１０と描画情報生手段とは、
ソース画像ごとのアドレス変換テーブルのアドレスと逆
変換パラメータとを座標変換手段２６のＣＡＭ手段に格
納する。
ソース画像ごとのアドレス変換テーブルのアドレスと逆
変換パラメータとを座標変換手段２６のＣＡＭ手段に格
納する。
【０１６４】座標変換手段２６はセグメントのノードを
読み出し、ｐｐの値でＣＡＭ手段を読み出し逆変換パラ
メータを得る。ソース画像毎にアドレス変換テーブルが
存在するので、ｐｐの値はソース画像毎にユニークな値
となる。従って、ソース画像毎に逆変換パラメータを得
ることが出来、座標変換手段２６はソース画像毎に異な
る逆変換を実施出来る。逆変換で得たソース座標値とｐ
ｐの値はアドレス変換手段２７に渡される。
読み出し、ｐｐの値でＣＡＭ手段を読み出し逆変換パラ
メータを得る。ソース画像毎にアドレス変換テーブルが
存在するので、ｐｐの値はソース画像毎にユニークな値
となる。従って、ソース画像毎に逆変換パラメータを得
ることが出来、座標変換手段２６はソース画像毎に異な
る逆変換を実施出来る。逆変換で得たソース座標値とｐ
ｐの値はアドレス変換手段２７に渡される。
【０１６５】アドレス変換手段２７は、ｐｐの値を用い
てソース画像毎にユニークなアドレス変換テーブルを用
いてメモリ２８での画素のアドレスをえる。画素のアド
レスの作り方は第１の実施例で説明したので省略する。
てソース画像毎にユニークなアドレス変換テーブルを用
いてメモリ２８での画素のアドレスをえる。画素のアド
レスの作り方は第１の実施例で説明したので省略する。
【０１６６】［他の実施形態］以上説明した実施例では
行バッファ２４とメモリ４とメモリ２８とを備えている
が、本発明ではこれらは物理的に分離したメモリ手段で
ある必要はなく、１個あるいは２個のメモリ手段を共有
していてもよい。
行バッファ２４とメモリ４とメモリ２８とを備えている
が、本発明ではこれらは物理的に分離したメモリ手段で
ある必要はなく、１個あるいは２個のメモリ手段を共有
していてもよい。
【０１６７】以上説明した実施例では、縮小手段は整数
単位縮小しかできないが、本発明はこれに限定されるも
のではなく、任意の割合の縮小を行うように縮小手段を
構成してもよい。また、その際に隣接画素を用いた補間
を行うように縮小手段と行バッファと分割手段を構成す
ることもできる。このように構成すると縮小に伴う画質
劣化（例えばジャギーやモアレ）を減らすことができ
る。
単位縮小しかできないが、本発明はこれに限定されるも
のではなく、任意の割合の縮小を行うように縮小手段を
構成してもよい。また、その際に隣接画素を用いた補間
を行うように縮小手段と行バッファと分割手段を構成す
ることもできる。このように構成すると縮小に伴う画質
劣化（例えばジャギーやモアレ）を減らすことができ
る。
【０１６８】以上説明した実施例では、アドレス変換手
段は逆変換で得たソース空間の座標値の直近の画素をメ
モリ２８より読み出し画像出力手段に供給するよう構成
されているが、本発明はこれに限定されるものではな
く、ソース空間の座標値に隣接する画素を補完して画素
値を得るように構成してもよい。このように構成すると
アフィン変換に伴う画質劣化（例えばジャギー）を減ら
すことができる。
段は逆変換で得たソース空間の座標値の直近の画素をメ
モリ２８より読み出し画像出力手段に供給するよう構成
されているが、本発明はこれに限定されるものではな
く、ソース空間の座標値に隣接する画素を補完して画素
値を得るように構成してもよい。このように構成すると
アフィン変換に伴う画質劣化（例えばジャギー）を減ら
すことができる。
【０１６９】以上説明した実施例では、描画情報１６は
デバイス画像の走査線のセグメントとして描画情報を保
持し座標変換手段２６は線分の座標変換を行うよう構成
されているが、本発明はこれに限定されるものではな
く、例えば、走査線に並行な台形、長方形、三角形を描
画情報の保持に用いてもよい。
デバイス画像の走査線のセグメントとして描画情報を保
持し座標変換手段２６は線分の座標変換を行うよう構成
されているが、本発明はこれに限定されるものではな
く、例えば、走査線に並行な台形、長方形、三角形を描
画情報の保持に用いてもよい。
【０１７０】以上説明した実施例では、部分画像をサイ
ズ６４×６４画素の正方形としたが、本発明はこれに限
定されるものではなく、正方形を長方形としてもよく、
またサイズを変えてもよい。部分画像のサイズを２のべ
き乗とすると、ソース空間の座標値からの部分画像の番
号と部分画像内の画素位置の計算が容易になるの。部分
画像のサイズを大きくすると、各種テーブルのサイズを
小さく出来るが、メモリ２８にて部分画像を保持するた
めのエリアが大きくなる。一方、部分画像のサイズを小
さくすると、各種テーブルのサイズは大きくなるが、メ
モリ２８にて部分画像を保持するためのエリアは小さく
なる。６００ＳＰＩのＡ４〜Ａ３サイズの画像を扱う場
合には６４×６４画素の部分画像がコストと性能の点で
好ましい。
ズ６４×６４画素の正方形としたが、本発明はこれに限
定されるものではなく、正方形を長方形としてもよく、
またサイズを変えてもよい。部分画像のサイズを２のべ
き乗とすると、ソース空間の座標値からの部分画像の番
号と部分画像内の画素位置の計算が容易になるの。部分
画像のサイズを大きくすると、各種テーブルのサイズを
小さく出来るが、メモリ２８にて部分画像を保持するた
めのエリアが大きくなる。一方、部分画像のサイズを小
さくすると、各種テーブルのサイズは大きくなるが、メ
モリ２８にて部分画像を保持するためのエリアは小さく
なる。６００ＳＰＩのＡ４〜Ａ３サイズの画像を扱う場
合には６４×６４画素の部分画像がコストと性能の点で
好ましい。
【０１７１】
【発明の効果】上述したように、この発明によれば、ス
キャンドイメージの回転、拡大縮小、あるいはより一般
的なアフィン変換処理や、スキャンドイメージの任意の
外形形状によるクリッピング処理や、スキャンドイメー
ジの上にラインアートを重ね書きする処理等において、
ソース画像入力時に、ソース画像を必要に応じて縮小し
たうえでソース画像を部分画像に分割し、デバイス画像
の描画に寄与する部分画像のみを符号化することでデー
タ量を縮小して保持し、デバイス画像のラスタスキャン
の際に逆サンプリングを用いて部分画像を参照する順を
決定しておき、ラスタスキャンと同期を取りつつ前記順
に従って部分画像の符号を復号することで、画像のラス
タスキャンの際に必要な部分画像のみを画像として保持
し、それらに対して逆サンプリングを行うことで、アフ
ィン変換とスキャンドイメージの輪郭内部の画素の出力
を行う。こうすることで、スキャンドイメージの処理に
必要なメモリを大幅に削減することができ低価格な処理
装置をうることができる。また、符号化によりスキャン
ドイメージのデータ量を減らすことで転送時間を減らす
ことができるので、前記画像処理を高速に実行できる。
また、部分画像は１回符号化され１回復号されるだけな
ので、非可逆圧縮アルゴリズムを用いても画像の劣化を
最小限に押さえることができる。
キャンドイメージの回転、拡大縮小、あるいはより一般
的なアフィン変換処理や、スキャンドイメージの任意の
外形形状によるクリッピング処理や、スキャンドイメー
ジの上にラインアートを重ね書きする処理等において、
ソース画像入力時に、ソース画像を必要に応じて縮小し
たうえでソース画像を部分画像に分割し、デバイス画像
の描画に寄与する部分画像のみを符号化することでデー
タ量を縮小して保持し、デバイス画像のラスタスキャン
の際に逆サンプリングを用いて部分画像を参照する順を
決定しておき、ラスタスキャンと同期を取りつつ前記順
に従って部分画像の符号を復号することで、画像のラス
タスキャンの際に必要な部分画像のみを画像として保持
し、それらに対して逆サンプリングを行うことで、アフ
ィン変換とスキャンドイメージの輪郭内部の画素の出力
を行う。こうすることで、スキャンドイメージの処理に
必要なメモリを大幅に削減することができ低価格な処理
装置をうることができる。また、符号化によりスキャン
ドイメージのデータ量を減らすことで転送時間を減らす
ことができるので、前記画像処理を高速に実行できる。
また、部分画像は１回符号化され１回復号されるだけな
ので、非可逆圧縮アルゴリズムを用いても画像の劣化を
最小限に押さえることができる。
【０１７２】復号手段２５の部分画像の復号タイミング
と、座標変換手段２６とアドレス変換手段２７の走査線
に関するタイミングとの同期を取ることで、座標変換手
段２６とアドレス変換手段２７が部分画像を必要とする
直前に復号手段２５で復号しメモリ２８に格納できるた
め、メモリ２８の部分画像の格納の為に必要なエリアの
サイズを最小限にすることができ、装置のコストを下げ
ることが出来る。復号手段２５と座標変換手段２６およ
びアドレス変換手段２７とは同時に動作可能なように構
成されているて、更に、出力走査時に走査線をスキャン
するときには部分画像が復元されてメモリ２８に格納さ
れているので、座標変換手段２６とアドレス変換手段２
７は直ちにメモリ２８を読むことが可能となり、処理を
高速化することができる。
と、座標変換手段２６とアドレス変換手段２７の走査線
に関するタイミングとの同期を取ることで、座標変換手
段２６とアドレス変換手段２７が部分画像を必要とする
直前に復号手段２５で復号しメモリ２８に格納できるた
め、メモリ２８の部分画像の格納の為に必要なエリアの
サイズを最小限にすることができ、装置のコストを下げ
ることが出来る。復号手段２５と座標変換手段２６およ
びアドレス変換手段２７とは同時に動作可能なように構
成されているて、更に、出力走査時に走査線をスキャン
するときには部分画像が復元されてメモリ２８に格納さ
れているので、座標変換手段２６とアドレス変換手段２
７は直ちにメモリ２８を読むことが可能となり、処理を
高速化することができる。
【０１７３】縮小手段２１を用いてあらかじめソース画
像を縮小した上で部分画像を作ることができるので、部
分画像画像の数を減らすことが出来る。これにより、メ
モリ４に格納する部分画像の符号の総量を減らすことが
可能となる。また、メモリ２８に格納すべき部分画像数
を減らすことが出来るのでメモリ２８の部分画像の格納
の為に必要なエリアのサイズを最小限にすることができ
る。これらメモリサイズの減少により、装置のコストを
下げることが出来る。また、部分画像のデータの総量も
減るため、データ転送時間が減り、処理を高速化するこ
とができる。
像を縮小した上で部分画像を作ることができるので、部
分画像画像の数を減らすことが出来る。これにより、メ
モリ４に格納する部分画像の符号の総量を減らすことが
可能となる。また、メモリ２８に格納すべき部分画像数
を減らすことが出来るのでメモリ２８の部分画像の格納
の為に必要なエリアのサイズを最小限にすることができ
る。これらメモリサイズの減少により、装置のコストを
下げることが出来る。また、部分画像のデータの総量も
減るため、データ転送時間が減り、処理を高速化するこ
とができる。
【０１７４】メモリ２８にソース画像毎にアドレス変換
テーブルを格納し、描画情報１６におけるスキャンドイ
メージのセグメントにはのアドレス変換テーブルへのポ
インタには該セグメントに関連するアドレス変換テーブ
ルへのポインタを格納するようにした。アドレス変換手
段２７は、ソース画像毎にアドレス変換を行うことがで
きる。これにより、デバイス画像に任意の数のソース画
像を同時に描画する場合においても、メモリの使用量を
減らしてコストを削減でき、処理を高速化でき、像の劣
化を最小限に押さえることができる。
テーブルを格納し、描画情報１６におけるスキャンドイ
メージのセグメントにはのアドレス変換テーブルへのポ
インタには該セグメントに関連するアドレス変換テーブ
ルへのポインタを格納するようにした。アドレス変換手
段２７は、ソース画像毎にアドレス変換を行うことがで
きる。これにより、デバイス画像に任意の数のソース画
像を同時に描画する場合においても、メモリの使用量を
減らしてコストを削減でき、処理を高速化でき、像の劣
化を最小限に押さえることができる。
【図１】 本発明の実施例１の処理のステップを示すフ
ローチャートを示す図である。
ローチャートを示す図である。
【図２】 本発明の実施例１のブロック図を示す図であ
る。
る。
【図３】 デバイス画像の例を示す図である。
【図４】 図２における走査線Ｙ１の描画情報の内部表
現を示す図である。
現を示す図である。
【図５】 ソース画像の例を示す図である。
【図６】 デバイス空間上でのソース画像とデバイス画
像の関係を示す図である。
像の関係を示す図である。
【図７】 重なり情報の表現形式を示す図である。
【図８】 部分画像と輪郭形状の重なりを示す図であ
る。
る。
【図９】 重なり情報の例を示す図である。
【図１０】 復号の順番を説明する図である。
【図１１】 復号順情報の例を示す図である。
【図１２】 縮小手段と分割手段と行バッファの構成を
示すブロック図を示す図である。
示すブロック図を示す図である。
【図１３】 縮小手段と分割手段と行バッファの動作を
示すタイミング図である。
示すタイミング図である。
【図１４】 行バッファ内のアドレスと使い方を示す図
である。
である。
【図１５】 画素の読み出し順序を示す図である。
【図１６】 部分画像の切り出し順序を示す図である。
【図１７】 部分画像の符号のメモリ内での格納を示す
図である。
図である。
【図１８】 座標変換手段のブロック図である。
【図１９】 アドレス変換テーブルと部分画像の関係を
示す図である。
示す図である。
【図２０】 本発明の第２の実施例のブロック図であ
る。
る。
【図２１】 縮小手段の作用の説明図である。
【図２２】 アフィン変換と逆変換の説明図である。
【図２３】 第３の実施例でのアドレス変換テーブルと
部分画像の関係を示す図である。
部分画像の関係を示す図である。
【図２４】 デバイス画像の例を示す図である。
【図２５】 図２３における走査線Ｙ１の描画情報の内
部表現を示す図である。
部表現を示す図である。
【図２６】 第３の実施例での座標変換手段の実施例を
示す図である。
示す図である。
１ ＣＰＵ、２ Ｉ／Ｏ手段、３ バス、４ メモリ、
１０ インタープリタ、１１ 描画情報生成手段、１２
重なり検出手段、１３ 復号順決定手段、１４ 重な
り情報、１５ 復号順情報、１６ 描画情報、１７ 分
割画像の符号、２０ 画像入力手段、２１ 縮小手段、
２２ 分割手段、２３ 符号化手段、２４ 行バッフ
ァ、２５ 復号手段、２６ 座標変換手段、２７ アド
レス変換手段、２８ メモリ、２９ 画像出力手段、２
６０１，２６０２，２６０３，２６０４ 乗算器、２６
０５，２６０４，２６０７，２６０８，２６１３，２６
１４ 加算器、２６０９，２６１０ セレクタ、２６１
１，２６１２ レジスタ、２６１５ 減算器、２６１６
ダウンカウンタ、２６１７ 制御回路
１０ インタープリタ、１１ 描画情報生成手段、１２
重なり検出手段、１３ 復号順決定手段、１４ 重な
り情報、１５ 復号順情報、１６ 描画情報、１７ 分
割画像の符号、２０ 画像入力手段、２１ 縮小手段、
２２ 分割手段、２３ 符号化手段、２４ 行バッフ
ァ、２５ 復号手段、２６ 座標変換手段、２７ アド
レス変換手段、２８ メモリ、２９ 画像出力手段、２
６０１，２６０２，２６０３，２６０４ 乗算器、２６
０５，２６０４，２６０７，２６０８，２６１３，２６
１４ 加算器、２６０９，２６１０ セレクタ、２６１
１，２６１２ レジスタ、２６１５ 減算器、２６１６
ダウンカウンタ、２６１７ 制御回路
Claims (13)
- 【請求項１】 ラスタ画像生成装置におけるラスタ画像
生成方法であり、 ラスタ画像を複数の部分画像に分割する画像分割ステッ
プと、 前記画像分割ステップにおいて得られた部分画像を符号
化し該部分画像の符号を得る符号化ステップと、 前記符号化ステップにおいて得られた部分画像の符号の
復号順を決定する復号順決定ステップと、 前記復号順決定ステップにおいて決定された順番に従っ
て、前記部分画像の符号を復号し、前記部分画像をメモ
リ手段に格納する復号ステップと、 第１の座標空間で表現された幾何情報を第２の座標空間
に変換する座標空間変換ステップと、 前記第２の座標空間での幾何位置に対応する前記メモリ
手段上のアドレスを生成するアドレス生成ステップと、 前記アドレス生成ステップにおいて生成されたアドレス
を用いてメモリ手段を読み出すステップとを有すること
を特徴とするラスタ画像生成方法。 - 【請求項２】 前記第１の座標空間はデバイス空間であ
り、前記第２の座標空間はソース空間であって、 前記座標空間変換ステップは、デバイス空間上でのスキ
ャンドイメージの描画幾何形状を形成するラスタスキャ
ン情報をソース空間へ逆変換し、ソース空間での幾何情
報すなわちラスタスキャン情報を得るステップであり、 前記アドレス生成ステップは、前記座標空間変換ステッ
プにおいて得たソース空間上でのラスタスキャン情報を
用いてデバイス空間のスキャンドイメージの画素に対応
する前記メモリ手段上の部分画像の画素のアドレス情報
を生成するステップであり、 該アドレス情報を用いて順に前記メモリ手段から画素を
読み出してデバイス空間でのスキャンドイメージの画素
を順に獲得する構成を有することを特徴とする請求項１
に記載のラスタ画像生成方法。 - 【請求項３】 前記ラスタ画像生成方法は、さらに、 前記画像分割ステップにおいて得られた部分画像と、前
記ラスタ画像生成装置に入力される描画情報から得られ
る幾何形状との重なり合いを調べる重なり検出ステップ
と、 前記重なり検出ステップでの重なり検出結果に応じて、
デバイス画像の描画に寄与する部分画像を選択する部分
画像選択ステップとを有し、 前記符号化ステップは、前記部分画像選択ステップにお
いて選択された部分画像についてのみ符号化し部分画像
の符号を得るステップであることを特徴とする請求項１
または２記載のラスタ画像生成方法。 - 【請求項４】 前記重なり検出ステップは、前記描画情
報からスキャンドイメージの輪郭情報を読み出し、読み
出されたスキャンドイメージの描画の際に指定されたア
フィン変換の逆変換を実行して、前記輪郭情報を前記ス
キャンドイメージのソース空間に写像し、該写像された
ソース空間の輪郭の内側部分あるいは該輪郭上に重なる
前記部分画像の領域を検出するステップであることを特
徴とする請求項３記載のラスタ画像生成方法。 - 【請求項５】 前記ラスタ画像生成方法は、さらに、 ラスタ画像の縮小を実行して縮小ラスタ画像を生成する
縮小ラスタ画像生成ステップを有し、 前記画像分割ステップは、該縮小ラスタ画像生成ステッ
プにおいて生成された縮小ラスタ画像について部分画像
への分割を実行することを特徴とする請求項１乃至４い
ずれかに記載のラスタ画像生成方法。 - 【請求項６】 ラスタ画像生成装置において、 ラスタ画像を複数の部分画像に分割する画像分割手段
と、 前記画像分割手段によって生成された部分画像を符号化
し部分画像の符号を得る符号化手段と、 前記符号化手段によって生成された部分画像の符号を復
号しメモリ手段に格納する復号手段と、 第１の座標空間で表現された幾何情報を第２の座標空間
に変換する座標空間変換手段と、 前記第２の座標空間での幾何位置に対応する前記メモリ
手段上のアドレスを生成するアドレス変換手段と、 前記符号化手段によって生成された部分画像の符号を復
号する復号順を決定する復号順決定手段とを備え、 前記復号順決定手段により決定した復号順に従って復号
された部分画像を前記メモリ手段に格納し、前記第１の
座標空間の幾何情報を前記座標変換手段に与えその出力
を前記アドレス変換手段に供給して得たメモリアドレス
を用いて前記メモリ手段に格納された部分画像の画素を
読み出す構成を有することを特徴とするラスタ画像生成
装置。 - 【請求項７】 前記第１の座標空間はデバイス空間であ
り、前記第２の座標空間はソース空間であって、 前記座標空間変換手段は、デバイス空間上でのスキャン
ドイメージの描画幾何形状を形成するラスタスキャン情
報をソース空間へ逆変換し、ソース空間での幾何情報す
なわちラスタスキャン情報を得る手段であり、 前記アドレス変換手段は、前記座標空間変換手段におい
て得たソース空間上でのラスタスキャン情報を用いてデ
バイス空間のスキャンドイメージの画素に対応する前記
メモリ手段上の部分画像の画素のアドレス情報を生成す
る手段であり、 前記アドレス変換手段によって生成されたアドレス情報
を用いて順に前記メモリ手段から画素を読み出してデバ
イス空間でのスキャンドイメージの画素を順に獲得する
構成を有することを特徴とする請求項６に記載のラスタ
画像生成装置。 - 【請求項８】 前記ラスタ画像生成装置は、さらに、 前記画像分割手段において生成された部分画像と、前記
ラスタ画像生成装置に入力される描画情報から得られる
幾何形状との重なり合いを検出する重なり検出手段を有
し、 前記重なり検出手段での重なり検出結果に応じて、デバ
イス画像の描画に寄与する部分画像を選択して、該選択
された部分画像についてのみ前記符号化手段によって符
号化し部分画像の符号を得ることを特徴とする請求項６
または７に記載のラスタ画像生成装置。 - 【請求項９】 前記ラスタ画像生成装置は、 前記画像分割手段において生成された部分画像と、前記
ラスタ画像生成装置に入力される描画情報から得られる
幾何形状との重なり合いを検出する重なり検出手段を有
し、 前記重なり検出手段での重なり検出結果に応じて部分画
像を選択的に前記分割手段で読み出して、該読み出され
た部分画像について前記符号化手段で符号化することを
特徴とする請求項６または７に記載のラスタ画像生成装
置。 - 【請求項１０】 前記重なり検出手段は、前記描画情報
からスキャンドイメージの輪郭情報を読み出し、読み出
されたスキャンドイメージの描画の際に指定されたアフ
ィン変換の逆変換を実行して、前記輪郭情報を前記スキ
ャンドイメージのソース空間に写像し、該写像されたソ
ース空間の輪郭の内側部分あるいは該輪郭上に重なる前
記部分画像の領域を検出する構成を有することを特徴と
する請求項８または９記載のラスタ画像生成装置。 - 【請求項１１】 前記ラスタ画像生成装置は、さらに、 ラスタ画像の縮小を実行して縮小ラスタ画像を生成する
縮小手段を有し、 前記画像分割手段は、前記縮小手段において生成された
縮小ラスタ画像について部分画像への分割を実行するこ
とを特徴とする請求項６乃至１０いずれかに記載のラス
タ画像生成装置。 - 【請求項１２】 前記ラスタ画像生成装置において、前
記復号手段を用いて実行される部分画像の復号タイミン
グ位置と、前記座標変換手段において変換が実行される
第１の座標空間の変換タイミング位置とを同期させて動
作する構成としたことを特徴とする請求項６乃至１１い
ずれかに記載のラスタ画像生成装置。 - 【請求項１３】 前記ラスタ画像生成装置において、前
記アドレス変換手段に第２の座標空間とメモリアドレス
とを関係づけるテーブルを持ち、該テーブルは、入力ラ
スタ画像ごと、個々に独立したテーブルによって構成さ
れていることを特徴とする請求項６乃至１２いずれかに
記載のラスタ画像生成装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10025295A JPH11224331A (ja) | 1998-02-06 | 1998-02-06 | ラスタ画像生成装置およびラスタ画像生成方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10025295A JPH11224331A (ja) | 1998-02-06 | 1998-02-06 | ラスタ画像生成装置およびラスタ画像生成方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11224331A true JPH11224331A (ja) | 1999-08-17 |
Family
ID=12162039
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10025295A Pending JPH11224331A (ja) | 1998-02-06 | 1998-02-06 | ラスタ画像生成装置およびラスタ画像生成方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH11224331A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7474928B2 (en) * | 2005-04-15 | 2009-01-06 | Autodesk Canada Co. | Hybrid vector/raster based paint |
| JP2009110368A (ja) * | 2007-10-31 | 2009-05-21 | Brother Ind Ltd | 画像処理プログラム |
| US8139082B2 (en) | 2005-05-02 | 2012-03-20 | Canon Kabushiki Kaisha | Image processing apparatus and its control method, and program |
-
1998
- 1998-02-06 JP JP10025295A patent/JPH11224331A/ja active Pending
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7474928B2 (en) * | 2005-04-15 | 2009-01-06 | Autodesk Canada Co. | Hybrid vector/raster based paint |
| US8139082B2 (en) | 2005-05-02 | 2012-03-20 | Canon Kabushiki Kaisha | Image processing apparatus and its control method, and program |
| JP2009110368A (ja) * | 2007-10-31 | 2009-05-21 | Brother Ind Ltd | 画像処理プログラム |
| US8320016B2 (en) | 2007-10-31 | 2012-11-27 | Brother Kogyo Kabushiki Kaisha | Image processing method for fast fill-in of a figure and computer readable medium therefor |
| US8472077B2 (en) | 2007-10-31 | 2013-06-25 | Brother Kogyo Kabushiki Kaisha | Image processing method for fast fill-in of a figure and computer readable medium therefor |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR100597879B1 (ko) | 비트맵데이터라인세그먼트를검색하는구분적인-선형직접메모리억세스어드레싱모드를사용하여,프린트될비트맵데이터의래스터화된라인을구성하는방법및장치 | |
| US7142213B2 (en) | Graphics drawing device and method | |
| JPH0863144A (ja) | フォント処理装置及びフォント処理方法 | |
| US5867612A (en) | Method and apparatus for the fast scaling of an image | |
| US8659620B2 (en) | Methods and apparatus for rendering images | |
| US5889893A (en) | Method and apparatus for the fast rotation of an image | |
| JPH08297737A (ja) | 任意図形クリッピング方法および装置 | |
| JP3791259B2 (ja) | アウトラインスムージング処理方法 | |
| US5537131A (en) | Character generating method and apparatus | |
| EP1014306B1 (en) | Antialiased high-resolution frame buffer architecture | |
| JP3037854B2 (ja) | 文字生成方法及びその装置 | |
| KR100302163B1 (ko) | 문자 생성 방법 및 장치 | |
| JP3009525B2 (ja) | ベクトル画像描画装置 | |
| JP2634851B2 (ja) | 画像処理装置 | |
| JPH11224331A (ja) | ラスタ画像生成装置およびラスタ画像生成方法 | |
| JP2726271B2 (ja) | パッチ化システム | |
| US6101290A (en) | Bandwidth efficient image transformations on a multiprocessor | |
| JP4325812B2 (ja) | ベクター画像描画回路およびベクター画像描画方法 | |
| KR900002631B1 (ko) | 화상데이터의 처리방법 및 장치 | |
| JP3211591B2 (ja) | イメージ処理装置 | |
| JP3350324B2 (ja) | キャラクタ出力装置 | |
| JP2006031160A (ja) | グラフィックオブジェクト処理方法 | |
| JP3365068B2 (ja) | 画像処理装置 | |
| JP2004326528A (ja) | 画像処理装置及び画像処理方法 | |
| JP2814709B2 (ja) | 描画データ作成装置 |