JPH09231352A

JPH09231352A - ピクセル画像マッピング方法

Info

Publication number: JPH09231352A
Application number: JP9002534A
Authority: JP
Inventors: Philip E Jensen; フィリップ・イー・ジェンセン
Original assignee: Hewlett Packard Co
Current assignee: HP Inc
Priority date: 1996-01-30
Filing date: 1997-01-10
Publication date: 1997-09-05
Also published as: DE19703004A1; GB9700084D0; GB2309873B; GB2309873A; US5670981A

Abstract

(57)【要約】【課題】ソース・ピクセル画像を宛先ピクセル空間に変
換する場合に、ソース画像境界内にあるすべての宛先ピ
クセルを１回のパスで表現することを可能にする方法を
提供する。【解決手段】先ず、ソース・ピクセル画像の第１稜線と
第２稜線に関して、宛先ピクセル空間におけるソース画
像稜線の交差座標値を取り出し、その１つを起点座標と
する。次に、起点座標から主軸方向に沿って最初に出会
う宛先ピクセル線と上記第１および第２稜線それぞれと
の交点をクリップ・ポイントとして選択する。次に出会
う宛先ピクセル線に関しても同じ動作を実行する。次
に、最初の宛先ピクセル線に沿った第１の従軸方向のピ
クセルの各々に対し、次の宛先ピクセルがクリップ・ポ
イントを越えるまで、画面表示値を割り当てる。後続の
次々の宛先ピクセル線に関してもその都度従軸方向を反
転させながら、表現すべき宛先ピクセルがなくなるま
で、同様の動作を繰り返す。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ラスタ画像表示に
関するもので、特に、１つのソース画像境界範囲内のす
べての宛先ピクセルが１回のパスで画面表示されるよう
に、ソース・ピクセル画像を宛先ピクセル空間にマップ
する方法に関するものである。

【０００２】

【従来の技術】ラスタ画像表示は、１つの解像度のソー
ス画像を別の解像度の宛先画像に変換する手段をしばし
ば含む。高解像度画像の走査変換が実行される場合、特
に、ソフトウェア走査変換手順が使用される場合、その
ような変換手順は長い時間を要する。そのような走査変
換を実行するハードウェアの使用もまたよく知られてい
るが、ハードウェアを使用して変換動作を実行する時、
ソース・データ・ポイントによって境界を定められてい
る離散的宛先ピクセルの取り扱いに対する単純な決定性
アプローチを持つことが必要である。換言すれば、ソー
ス画像特性を適切に表示するためどの宛先ピクセルが
「オン」にされるべきかあるいは「オフ」にされるべき
かを確実に決定することが必要である。

【０００３】２次元ラスタ宛先格子面上でソース画像線
の近くに位置するピクセル座標を計算することが走査変
換手順の基本的作業である。ソース画像が単一ピクセル
幅より大きい複数線を含む場合、ソース画像を宛先解像
度で可能な限りうまく表示するため、ソース画像の制限
線の範囲内のどのピクセルをオンにすべきかを決定する
いわゆる「充填」手順が実行される。走査変換アルゴリ
ズムを実行する従来技術の戦略は、操作変換される線の
勾配を決定するため乗算を使用する。具体的に云えば、
そのような戦略は、ｘ方向の増分に対してｙ＝ｍｘ＋ｂ
を計算して、増分ｘ、ｙにおけるピクセルを強調表現す
る。しかし、ｍｘの計算は、時間消費的であり、走査変
換プロセスを遅くする。

【０００４】乗算を回避するため、従来技術は、Δｘ＝
１ならばｍ＝Δｙ／Δｘはｍ＝Δｙとなる点に注目し
た。すなわち、ｘにおける１単位の変化が操作変換され
ている線の勾配であるｍだけｙを変化させる。従って、
線上のすべてのポイント(ｘ_i，ｙ_i)に関して、ｘ_i+1＝
ｘ_i＋１であれば、ｙ_i+1＝ｙ_i＋ｍであることが知られ
ている。このように、ｘとｙの次の値は、それらの直前
の値を基にして確定される。従って、各ステップにおい
て、先行ステップに基づいて増分計算が行われる。

【０００５】ブレゼンハム(Bresenham)氏によって教示
された走査変換アルゴリズムは、整数演算のみを使用す
るので魅力的である(このアルゴリズムは、"Fundamenta
ls of Interactive Computer Graphics", Foley et a
l., Addison Wesley, Chapter11, 1983に記載されてい
る)。ブレゼンハム法は、各ステップにおいて決定変数
を使用し、走査変換動作全体を実行するためには囲まれ
た宛先ピクセル空間内で複数のパスを必要とする。ブレ
ゼンハム手順は、走査変換手順がソース画像の境界の外
部へ移動する状況をカバーするため、多数のアドレス・
サイクルの生成を更に必要とする。更にまた、ソース画
像の境界の範囲内で複数のパスが必要とされるので、相
当のメモリがこの手順の間に利用される。

【０００６】

【発明が解決しようとする課題】高解像度画像の表示に
対する要求は常に存在し、特に、表示される画像をユー
ザが変換し、回転させ、拡大縮小させることが可能にさ
れるべき医療分野において、その要求は強い。通常は、
変換、回転および拡大縮小動作は、ソース画像に対して
実行され、次にそのソース画像が宛先解像度に合うよう
に走査変換されて表示される。走査変換の速度を改善す
るため、ソース画像境界の範囲内にあるすべての宛先ピ
クセルを単一のパスで表現することが必要とされる。こ
れは、要するに、単一パスでの宛先データ全体に対する
ソース・データの強度情報を単に保持するだけですむこ
とを意味する。宛先ピクセルを表現するために使用され
るべき正確なデータを決定する問題がそれによって単純
化される。

【０００７】宛先データ全体をカバーする単一のパスに
よって、変換動作が増分アドレス値を使用することが可
能となり、これによって、画像処理サブアセンブリを通
過するデータ量が大幅に減少する。例えば、ソース・ピ
クセル毎にデータ位置およびデータ値を必要とする代わ
りに、次のデータ位置に関するデータ値および「ステッ
プ」情報を使うことだけが必要とされる。また、変換手
順は、すべてのピクセルが表現され、データに「穴」が
ないことを保証しなければならない。「穴」は、ソース
・データの境界の範囲内に存在するのにもかかわらず走
査変換手順によって「オン」にされないピクセルを指
す。

【０００８】

【課題を解決するための手段】本発明は、ソース・ピク
セル画像を宛先ピクセル空間に変換する場合に、ソース
画像の境界の範囲内にあるすべての宛先ピクセルを１回
のパスで表現することを可能にする方法を提供する。該
方法は、先ず、ソース・ピクセル画像の第１稜線と第２
稜線に関して、宛先ピクセル空間におけるソース画像稜
線の交差座標値を取り出す。ソース座標値の中の１つ
が、起点座標として選択される。該方法は、次に、起点
座標から主軸に沿う方向において最初に出会う宛先ピク
セル線を決定する。上記最初に出会った宛先ピクセル線
とソース・データの第１および第２稜線それぞれとの交
点においてクリップ・ポイントが取り出される。更に、
次に出会う宛先ピクセル線に関して同じ動作が実行され
る。次に、最初に出会った宛先ピクセル線に沿った第１
の従軸方向のピクセルの各々に対し、次の宛先ピクセル
が上記当該ピクセル線に関するクリップ・ポイントを越
えるまで、画面表示値が割り当てられる。その後、次に
出会った宛先ピクセル線に沿って位置し、当該ピクセル
線に関して既に取り出されたクリップ・ポイントの範囲
内に入るピクセルに対し画面表示値が割り当てられ、次
の宛先ピクセルがクリップ・ポイントを越えるまで、次
に出会った宛先ピクセル線に沿った第２の従軸方向のピ
クセルの各々に表示値が割り当てられる。上記プロセス
が、ソース・ピクセル画像の境界の範囲内に位置するピ
クセル線に関して繰り返され、その際、従軸方向は宛先
ピクセル線に出会う毎に反転される。当プロセスは、表
現すべき宛先ピクセルがなくなると終了する。

【０００９】

【発明の実施の形態】図１に示される画像処理システム
１０は、ＣＰＵ１２、ソース画像(すなわち源画像)を記
述するデータを記憶するランダム・アクセス・メモリ
(ＲＡＭ)１４、宛先画像に対応するデータを記憶するＲ
ＡＭ１６、および宛先画像データに応じて制御可能でそ
のデータをユーザのために表示する表示装置１８を含
む。ソース・データの回転、変換および拡大縮小を行う
ためユーザがコマンドを入力するキーボード２０がまた
含まれる。

【００１０】ソース画像の宛先画像への変換を実行する
ため、アプリケーション指向型集積回路(すなわちＡＳ
ＩＣ)２２が提供され、それにより、ハードウエアの制
御および走査変換動作を実行する単一パス処理が実施さ
れる。ＡＳＩＣ２２内の各エレメントの機能の詳細は後
述されるが、その概要は次の通りである。アドレス生成
モジュール２４は、ソース画像の基底または起点の座標
および起点で交差する稜線の勾配を記憶する。現在時ピ
クセル・モジュール２６は、処理されつつある現在時ピ
クセルの座標値を記憶する。クリップ・ポイント生成器
２８およびクリップ・ポイント比較モジュール３０は、
連係して動作して、宛先ピクセルがソース画像の境界内
に位置しているか境界外に位置しているかの判断を行
い、それによって、システムが、変換された画像を表現
するためどの宛先ピクセルを強調表示すべきか決定する
ことができる。インターフェース・モジュール３２は、
画像処理システム１０におけるその他のモジュールに対
するバス３４経由の接続手段を提供する。

【００１１】以下の記述によって理解されるように、画
像処理システム１０は、ソース画像ピクセルのグレイス
ケールまたはカラー値を表現するためどの宛先ピクセル
を強調表示すべきか１回のパスで決定する方法を用い
る。具体的に述べれば、ソース画像稜線の境界の範囲内
に位置する宛先ピクセルの各々が、ソース画像データに
従って決定され、引き続いて強調表現される。更に、本
手順は、ステップの再軌跡が不要なように、宛先画像ピ
クセルを順にたどって蛇行して進む。以下、図２ないし
図８に示される例を参照しながら本発明の方法を説明す
る。本発明の方法の動作の流れは、図９ないし図１１に
示される。

【００１２】図２に示されるように、本発明の手順は、
通常の非回転形態で配置された座標値のアレイからなる
ソース画像４０から始まる。画像４０の格子内の稜線の
頂点または交点の各々は、カラー強度を示す何らかのス
カラー値を表すデータ・ポイントのアドレスを表現す
る。図２に示される頂点が、ＸおよびＹ座標方向に１ピ
クセル単位離れているものと見なすことは可能である
が、図２では、それら頂点は表示画面上または表示空間
内の特定の位置を表していない。

【００１３】表示装置１８上での表示のためソース画像
４０を宛先画像へ画像処理システム１０が変換すること
を可能にするため、データの拡大縮小および回転が、ユ
ーザ入力要求に従って実行される。更に、宛先表示空間
に適切に位置づけられるように、データが変換されるこ
ともある。そのような動作は、従来技術において周知の
ものであり、本明細書ではこれ以上記述しない。

【００１４】図３において、ソース画像４０が、その頂
点が宛先ピクセル空間４２において座標値によって表さ
れるように、拡大縮小および回転によって画像４０'へ
変換されたものと仮定されている。ドット４４の各々
は、宛先空間４２におけるピクセル位置を表す。しか
し、稜線頂点４６、４８、５０、５２等はどの宛先ピク
セル位置にも直接該当しないが、宛先ピクセル位置と合
致しない宛先空間４２の座標値によって表現されるとい
う点には注意する必要がある。すなわち、稜線頂点４
６、４８、５０、５２等の各々は、宛先空間４２の非整
数座標値によって表現される。

【００１５】ソース画像頂点値によって定義された境界
の範囲内にどの宛先ピクセル４４が位置しているかを決
定するため、以下の記述においては、１時点で１行の宛
先ピクセル・データが処理対象とされる。ソース・デー
タ値の各々が１回でバス３４へ送り出されるだけであ
る。

【００１６】本発明の記述に先立って、本明細書で使用
するいくつかの用語の意味を述べる。図２ないし図８に
示される例は、Ｘ軸に沿った１次的「描画」方向および
Ｙ軸に沿った２次的「描画」方向を例示している(ソー
ス・データの行は一般的にＸ方向に延び、ソース・デー
タの列は一般的にＹ方向に延びる)。しかし、ソース・
データ画像は、デカルト座標系のどの象限にも配置でき
るので、画像エレメントおよび「描画」方向を完全に定
義するため更に一般的用語が必要とされる。本明細書で
使用する用語は次の通りである。＊主軸：Ｘ軸またはＹ軸のいずれかであるが、「描画」
される方向に依存して定まる。１つの走査線を所与とす
れば、これは、データが次々と受け取られるにつれて線
が引かれる方向である。＊従軸：主軸に対して９０度の角度にある軸である。＊第１稜線：主軸に沿って最も遠くまで戻るポイントで
始まる稜線。＊第２稜線：第１稜線ではない稜線。＊主第１：第１稜線開始ポイントにおける主軸の値。＊従第１：第１稜線開始ポイントにおける従軸の値。＊主第２：第２稜線開始ポイントにおける主軸の値。＊従第２：第２稜線開始ポイントにおける従軸の値。＊勾配主軸：主軸に沿った主軸の１単位の変化に対する
従軸における稜線の変化。＊勾配従軸：従軸に沿った従軸の１単位の変化に対する
主軸における稜線の変化。

【００１７】図４は、ソース座標ポイント４６、４８、
５０および５２によって表現されたソース・データ(お
よび関連稜線)を示す。このケースでは、主軸はＸ方向
に沿い、従軸はＹ方向に沿っている。頂点４６は第１稜
線開始点(ポイント)であり、稜線５４は第１稜線であ
る。頂点５０は第２稜線開始点(ポイント)であり、頂点
５０および５２に接続している稜線５６は第２稜線であ
る。

【００１８】頂点ポイント４６、４８、５０、５２等の
各々は、主および従方向に正確に等距離離れている(す
なわち、データ領域すべては長方形である)。従って、
一旦第１稜線開始ポイントのアドレスが判明すれば、そ
の他の頂点値を生成するためには、ＸおよびＹ方向に１
ステップ値加算するだけでよい。従って、第１稜線開始
ポイントは、初期的に、基底アドレスＸおよび基底アド
レスＹからなる座標値が割り当てられる。第２稜線開始
ポイント５０のアドレスを生成するためには、基底アド
レスＸに基本ステップＸ従軸値を加算し、基底アドレス
Ｙに基本ステップＹ従軸値を加算するだけでよい。基本
ステップ値は、画像４０'が従った回転および拡大縮小
の量を知ることによって引き出される。基本ステップ値
は、アクセスが容易となるように、必要画像回転の量に
従ってアドレス指定されるテーブルに好ましくは含まれ
る。

【００１９】次の第１稜線頂点値を生成するため、第１
稜線開始点のＸ成分に基本ステップＸ主軸値が加えら
れ、第１稜線開始点のＹ成分に基本ステップＹ主軸値が
加えられる。同様の計算が、次の第２稜線点に関しても
実行される。

【００２０】ソース画像を適切に表現するためどの宛先
空間ピクセル４４(図５)が強調表現されるべきかを決定
する前に、第１稜線５４および第２稜線５６の勾配が、
従軸方向の稜線５８の勾配と共に、決定される。勾配主
軸値および勾配従軸値の両者を基本ステップ値を基に決
定することができる。更に、頂点の間の距離は常に整数
単位であるので、勾配値を決定するため乗算動作は必要
とされない。

【００２１】ある１つの宛先空間ピクセルが第１稜線５
４および第２稜線５６の範囲内に位置しているか否かを
判断するため、クリップ・ポイント６０および６２と宛
先ピクセルの座標の比較が行われねばならない(図６参
照)。これらのクリップ・ポイントは、ある１つの宛先
ピクセル列の従軸を規定する線６４と第１稜線５４およ
び第２稜線５６それぞれとの交点を示す。後述のよう
に、宛先ピクセルの各行が対象となる毎に、クリップ・
ポイント６０および６２の計算は行われる。すなわち、
クリップ・ポイントは、個々の宛先ピクセルの処理に先
行して計算されない。

【００２２】初期的には、クリップ・ポイント６０の決
定を開始するため、第１稜線開始ポイント４６の基底ア
ドレスＸ座標値および基底アドレスＹ座標値が利用され
る。初期的には、宛先ピクセルの次に大きい主軸値から
基底アドレスＸ値を減ずることによって、第１稜線開始
ポイント４６から線６４までの距離(主軸差)が計算され
る。次に、主軸差に主軸勾配(すなわち従軸差)が乗じら
れ、距離ｄが決定される。次に、ｄの値が基底アドレス
値Ｙに加算され、クリップ・ポイント６０の座標値が定
められる。後続のクリップ・ポイントはクリップ・ポイ
ント６０から１単位の距離にあるので、クリップ・ポイ
ント６０に主軸勾配を加算するだけで、ソース・データ
領域内の残りのクリップ・ポイントが作成される。第１
稜線開始ポイントを再び通過すると、このプロセスが繰
り返される。第２稜線上のクリップ・ポイントも同じ方
法で生成される。

【００２３】左および右の従軸稜線５８および６６も生
成されなければならない。これらの稜線は、使用する勾
配が従軸勾配である点を除き、上記の第１および第２稜
線に対するものと同様の方法で生成される。基点は、常
に第１稜線開始ポイントである。処理が最初の第２稜線
開始ポイントを通過すると、主軸勾配が再び使用され
る。最後に、次の第１稜線ポイントを通過すると、再び
従軸勾配が使用される。このようにして、宛先ピクセル
線(本例ではピクセル列)の処理が進むにつれ、クリップ
・ポイントが決定され、特定の宛先ピクセルを強調表現
すべきか否か判断する準備が整う。

【００２４】次に図７および図８を参照して、いわゆる
「蛇行」手順を説明する。この手順によって、宛先ピク
セルの各々が逐次アクセスされ、処理され、強調表示ま
たは無視される。この手順は、宛先ピクセル全体を蛇が
進むように逐次処理して行き、再度軌跡をたどることは
ない。この動作は、チップ搭載データ記憶ＲＡＭの容量
を約２５％減少させる。更に、これは、データ領域を出
力するために送られなければならないアドレスの数を最
小にし、それによって画像描出の速度が増加する。この
手順によって必要とされる移動の大部分は、現在時ピク
セルから１ピクセルの範囲内にある。

【００２５】要するに、この手順は、現在時ピクセル位
置の周囲の４つのピクセルを検討することによって処理
を進める。始めに、開始宛先ピクセルが選択される。こ
のピクセルは、稜線に直接隣接していなければならず、
またこの稜線は第１稜線であることが望ましい。次に、
現在時従軸方向が、第１稜線から第２稜線への方向とし
てシステムによって定義される。これは、ピクセルから
ピクセルへの本発明の手順の「移動」の第１の方向を確
立する。

【００２６】図７に示されるように、現在時従軸方向は
ページを下がる方向にあり、手順は宛先ピクセル７０か
ら始まる。本手順は、現在時ポイント７２に到達したと
仮定すれば、先ず、現在時従軸方向でかつ同一のピクセ
ル線に沿って(すなわち共通の主軸値を持つ)１増分離れ
た宛先ピクセル７４を検査する。この宛先ピクセル７４
が既に計算したクリップ・ポイント７６および７８の範
囲内に位置しているか判断する。ピクセル７４がクリッ
プ・ポイントの範囲内にあれば、現在時ピクセル値を宛
先ピクセル７４に増分させ、本手順を繰り返す。ピクセ
ル７４がクリップ・ポイントの範囲内に位置していない
場合、現在時従軸位置に従軸方向に１ステップおよび主
軸方向に１ステップ加えた位置にあるピクセル(例えば
宛先ピクセル８０)を次に検査するピクセルとする。宛
先ピクセル８０がクリップ・ポイント８２および８４の
範囲内に位置していない場合、手順は、同じ現在時従軸
位置で主軸に沿って１ステップ進んだピクセル(例えば
８６)を検査すべき次の宛先ピクセルとする。再び、ピ
クセル８６がクリップ・ポイント８２および８４の範囲
内に位置していない場合、主軸方向に１ステップおよび
現在時従軸方向と反対の第２の従軸方向に１ステップ進
んだ位置にあるピクセル８８が検査される。宛先ピクセ
ル７４が境界外側にあると判明する場合、次のピクセル
線のピクセル８０、８６、８８へ進む前に現在時従軸方
向が反転される点に注意する必要がある。

【００２７】本手順は、図８に示されるように、ピクセ
ル列からピクセル列へ蛇のように移動しながら処理を進
める。各々の列において、境界外へ出ずに進むことがで
きる限り、現在時従軸方向での検査手続きが続行する。
境界外へ出ると、本手順は、次の列のピクセルへ移動
し、現在時従軸方向を反転させ、その行の上のどのピク
セルが第１および第２稜線の境界の範囲内に位置してい
るかを判断し続ける。本手順は、ソース画像領域全体が
強調表現された宛先ピクセルによって埋められるまで続
行する。

【００２８】本手順は、大半のケースに対して有効に作
用するが、すべてではない。従って、「脱出」メカニズ
ムを提供することが必要である。第１に、図７に示され
る逐次的手順でピクセルが何も選択されない場合は、主
軸方向で１ステップ離れかつ第２稜線に最も近い位置に
ある(かつなお境界内にある)ピクセルに移動する。第２
に、図７に示される移動方向２で選択されたピクセル
が、稜線のすぐ次に位置していない場合、本手順は、主
軸方向に１ステップ離れかつ第１稜線に最も近い位置に
あるピクセルに再び移動する。換言すれば、本手順はリ
セットされ、現在次従軸方向は変えず、境界内にあって
主軸方向に１ステップ離れた最上部宛先ピクセルへ移動
する。そのような宛先ピクセルがなければ、本手順は、
同様のプロセスを繰り返し、主軸方向に更に１ステップ
移動する。

【００２９】図９ないし図１１を参照して、ソース画像
データに従って宛先ピクセルを表現するため本発明によ
って使われている手順を記述する。回転動作後も宛先座
標が直交座標的に相対的関係を保っていることを保証す
るため回転に先立って拡大縮小動作が行われることが望
ましい。初期的には、本手順への入力はソース・デーの
回転角度および拡大縮小係数である(ステップ１００)。
入力データを基に、ソフトウェア・ルーチンが現在時主
軸方向を決定する(ステップ１０２)。その方向は、回転
角度を検査しそれが位置する象限によって決定される。
例えば、回転角度が＋４５度と−４５度の間にあれば、
主軸方向は＋Ｘ軸方向にあり、＋４５度と＋１３５度の
間にあれば、主軸方向は＋Ｙ軸方向にあり、その他の方
向も同様に決定される。

【００３０】次に、第１稜線が、主軸方向に最も遠方に
戻る頂点に接続する最も長い稜線として決定される。上
記の頂点は、基底アドレスＸおよび基底アドレスＹから
なる座標を持つ第１稜線開始点である。次に、本手順
は、基本ステップＸ主軸値、基本ステップＹ主軸値、基
本ステップＸ従軸値および基本ステップＹ従軸値を計算
する(ステップ１０４)。これらの値は、ソース座標値か
ら決定されて、宛先空間におけるソース座標の決定を可
能にする。また、これらの値は、勾配主軸値および勾配
従軸値の計算を可能(ステップ１０６)にする。

【００３１】次に、勾配主軸値、勾配従軸値および基底
アドレスが図１のアドレス生成器２４にロードされる
(ステップ１０８)。次に、ステップ１０４で決定された
基底アドレスおよび基本ステップ値を使用して、宛先空
間における第１稜線開始点および第２稜線開始点座標が
決定される(ステップ１１０)。この段階で、図５に示さ
れた画像を定義するデータが取り出された。

【００３２】次に、宛先ピクセルの最初の線(すなわち
列）)に関するクリップ・ポイントを計算するため、基
底アドレスＸおよび基底アドレスＹがアクセスされる。
手順は、主軸方向に「移動」して、宛先ピクセルの列を
通過する線を定義する次の整数主軸座標値を引き出す
(ステップ１１２)。これは、図６に示された「主軸差」
である。次に、勾配主軸値および勾配従軸値を使用し
て、上述のように第１稜線および第２稜線のクリップ・
ポイントが決定される(ステップ１１４)。次の主軸座標
整数値における宛先ピクセルの後続列に関して、同様の
プロセスが繰り返され(ステップ１１６)、本手順の実行
を可能にする。

【００３３】起点として１つのクリップ・ポイント(例
えば図６のクリップ・ポイント６０)を使用して、本手
順は、より小さな整数従軸値を持つ最初の宛先ピクセル
(例えば図６のピクセル６５)に出会うまで、第２稜線５
６方向に移動する(ステップ１１８)。この段階から、本
手順は図８に示された蛇行処理方法の実施を開始する。
現在時従軸方向(下方向)にあって同じ主軸座標値に位置
している次の宛先ピクセル(例えば６７)が第１稜線クリ
ップ・ポイントと第２稜線クリップ・ポイントの範囲内
に位置していれば、当該宛先ピクセルは強調表現される
(ステップ１２０およびステップ１２２)。

【００３４】本手順は、宛先ピクセルの列の下方に移動
し続けて、第１稜線クリップ・ポイントと第２稜線クリ
ップ・ポイントの範囲内にある後続の宛先ピクセルが見
出される限り、それらを強調表現する。しかしながら、
現在時従軸方向の次の宛先ピクセルがクリップ・ポイン
トの外側にあると判明する場合、本手順は、従軸方向に
１ステップ、主軸方向に１ステップ離れた次の宛先ピク
セルを検査して、そのピクセルが当該ピクセル列の２つ
のクリップ・ポイントの範囲内に位置しているか否かを
判断する(ステップ１２４)。もし位置していれば、従軸
方向を反転し、主軸方向の次の整数増分のクリップ・ポ
イントが計算される(ステップ１２６)。次に、当該ピク
セルは強調表現され(ステップ１２２)、本手順はステッ
プ１２０へ戻って処理を継続する。

【００３５】ステップ１２４の判断が否であれば、主軸
方向にのみ１ステップ離れた次の宛先ピクセルを検査し
て、そのピクセルが当該ピクセル列の２つのクリップ・
ポイントの範囲内に位置しているか否かを判断する(ス
テップ１３０)。もし位置していれば、従軸方向を反転
し、主軸方向の次の整数増分のクリップ・ポイントが計
算される(ステップ１２６)。次に、当該ピクセルは強調
表現され(ステップ１２２)、本手順はステップ１２０へ
戻って処理を継続する。

【００３６】ステップ１３０の判断が否であれば、主軸
方向に１ステップ、従軸の現在時方向と逆方向に１ステ
ップ離れた次の宛先ピクセルを検査して、そのピクセル
が当該ピクセル列の２つのクリップ・ポイントの範囲内
に位置しているか否かを判断する(ステップ１３２)。も
し位置していれば、従軸方向を反転し、主軸方向の次の
整数増分のクリップ・ポイントが計算される(ステップ
１２６)。次に、当該ピクセルは強調表現され(ステップ
１２２)、本手順はステップ１２０へ戻って処理を継続
する。

【００３７】ステップ１３２の判断が否であれば、上述
の「脱出」手順を実施するため、主軸方向に１ステップ
移動し、第１稜線に最も近接しかつ当該ピクセル列に関
するクリップ・ポイントの範囲内に位置する宛先ピクセ
ルを探す(ステップ１３４)。そのようなピクセルがあれ
ば(ステップ１３６)、当該ピクセルは強調表現され(ス
テップ１３８)、本手順はステップ１２０へ戻る。その
ようなピクセルがない場合、次のソース・データ行がア
クセスされ(ステップ１４０)、本手順はステップ１０２
へ戻る。

【００３８】現在時ピクセル位置は、図１の現在時ピク
セル・モジュール２６に維持される。クリップ・ポイン
ト生成器２８が、連続する宛先ピクセル列に関するクリ
ップ・ポイント値を決定するために必要とされる計算を
実行し、クリップ比較モジュール３０が、宛先ピクセル
がクリップ・ポイント範囲内に位置するか否かの決定を
可能にする計算を実行する。クリップ比較モジュール３
０の計算結果である出力が、インターフェース・モジュ
ール３２を経由して宛先画像ＲＡＭ１６に直接送られ
る。このような方法で、宛先ピクセルが１回パスで取り
扱われ、ソース・データが同様に逐次処理される。

【００３９】上述の実施形態が本発明の例示の目的のた
めにのみ記述された点は理解されなければならない。当
業者によって本発明の精神および有効範囲を逸脱するこ
となく上述の実施形態に種々の変更および修正を加える
ことは可能であろう。

【００４０】本発明には、例として次のような実施様態
が含まれる。（１）ソース・ピクセル画像を主軸方向および従軸方向
を有する宛先ピクセル空間へマップする方法であって、
上記ソース・ピクセル画像の第１稜線および第２稜線に
関して、ソース画像稜線交点の上記宛先ピクセル空間座
標値を取り出し、かつ、それら交点の１つを起点と定め
るステップ(a)と、上記起点の座標から主軸方向に沿っ
て進んで最初に出会う宛先ピクセル線を決定するステッ
プ(b)と、上記第１稜線および第２稜線それぞれと上記
最初に出会った宛先ピクセル線の交点に位置する２つの
クリップ・ポイントを計算するステップ(c)と、上記最
初に出会った宛先ピクセル線から上記主軸方向に移動し
た位置にある次の宛先ピクセル線を決定するステップ
(d)と、上記第１稜線および第２稜線それぞれと上記次
の宛先ピクセル線の交点に位置する２つのクリップ・ポ
イントを計算するステップ(e)と、上記最初に出会った
宛先ピクセル線に沿って第１の従軸方向に位置するピク
セルの各々に対して、現在時ピクセルの次の宛先ピクセ
ルが当該宛先ピクセル線のクリップ・ポイントを越えな
い限り、画面表示値を割り当てるステップ(f)と、上記
次の宛先ピクセル線にあって当該宛先ピクセル線に関し
て既に計算されたクリップ・ポイントの範囲内にある１
つのピクセルに対して画面表示値を割り当てるステップ
(g)と、上記次の宛先ピクセル線に沿って第２の従軸方
向に位置するピクセルの各々に対して、現在時ピクセル
の次の宛先ピクセルが当該宛先ピクセル線に関するクリ
ップ・ポイントを越えない限り、画面表示値を割り当て
るステップ(h)と、上記ソース画像の境界内にある後続
の宛先ピクセル線に関して、各宛先ピクセル線毎に上記
従軸方向を反転させながら、次の宛先ピクセル線の決
定、そのクリップ・ポイントの取り出しおよびクリップ
ポイント内にある各宛先ピクセルに対する画面表示値の
割り当てを実行する上記(d)から(h)の諸ステップを繰り
返すステップ(i)と、を含むピクセル画像マッピング方
法。

【００４１】（２）上記ステップ(a)における上記開始
点座標が上記主軸に沿った１方向において他のすべての
ソース画像稜線交点座標値から最も遠い位置にある、上
記（１）に記載のピクセル画像マッピング方法。（３）上記ステップ(g)が、上記次に出会う宛先ピクセ
ル線に沿った上記第１の従軸方向において上記現在時従
軸位置から１ステップ離れた位置にある宛先ピクセルが
上記ステップ(e)において取り出された上記クリップ・
ポイントの範囲内にあるか否かを判断するサブステップ
(g1)を含む、上記（２）に記載のピクセル画像マッピン
グ方法。（４）上記ステップ(g)が、上記次に出会う宛先ピクセ
ル線に沿って上記主軸方向に１ステップ離れ上記現在時
ピクセルの従軸位置と同じ位置にある宛先ピクセルが上
記ステップ(e)において取り出された上記クリップ・ポ
イントの範囲内にあるか否かを判断するサブステップ(g
2)を含む、上記（３）に記載のピクセル画像マッピング
方法。（５）上記ステップ(g)が、上記次に出会う宛先ピクセ
ル線に沿って上記現在時ピクセルから上記主軸方向に１
ステップ離れ上記第２の従軸方向に１ステップ離れた位
置にある宛先ピクセルが上記ステップ(e)において取り
出された上記クリップ・ポイントの範囲内にあるか否か
を判断するサブステップ(g3)を含む、上記（４）に記載
のピクセル画像マッピング方法。（６）上記サブステップ(g1)、(g2)および(g3)における
判断がすべて否定的な場合、次の宛先ピクセル線にあっ
て上記第１稜線に最も近い位置で上記クリップ・ポイン
トの範囲内にある宛先ピクセルに表示画面値を割り当て
るステップ(j)、を更に含む上記（５）に記載のピクセ
ル画像マッピング方法。

【００４２】

【発明の効果】本発明によって、画像処理のためのチッ
プ搭載データ記憶ＲＡＭの容量が大幅に減少し、また、
データ出力のためのアドレス数が最小限にとどめられ、
そのため画像描出の速度が向上する。

【図面の簡単な説明】

【図１】本発明を実施するように適合された画像処理シ
ステムのブロック図である。

【図２】宛先空間に表現されるべきソース画像の１例を
示すブロック図である。

【図３】変換、回転および拡大縮小されたソース画像を
示す宛先空間のブロック図である。

【図４】ソース画像の第１および第２稜線の勾配を決定
するために使用される値を示す４個のソース・ピクセル
のブロック図である。

【図５】図３で示された宛先空間の一部で、そのソース
画像の一部を拡大表示したブロック図である。

【図６】クリップ・ポイントの作成方法を示すブロック
図である。

【図７】本発明の方法によって表現されるべき次のピク
セルを決定するため現在時ピクセルから行われるステッ
プのシーケンスを示すブロック図である。

【図８】所定のソース画像の範囲内のすべての宛先ピク
セルを表現する際にとられる経路を示すブロック図であ
る。

【図９】図１０および図１１とともに、本発明の方法を
実行する図１のシステムの機能を表す論理的処理の流れ
図である。

【図１０】図９および図１１とともに、本発明の方法を
実行する図１のシステムの機能を表す論理的処理の流れ
図である。

【図１１】図９および図１０とともに、本発明の方法を
実行する図１のシステムの機能を表す論理的処理の流れ
図である。

【符号の説明】

１０画像処理システム１２ＣＰＵ１４ソース画像ＲＡＭ１６宛先画像ＲＡＭ１８表示装置２０キーボード２２ＡＳＩＣ２４アドレス生成モジュール２６現在時ピクセル生成モジュール２８クリップ・ポイント生成器３０クリップ・ポイント比較モジュール３２インターフェース・モジュール３４システム・バス４０、４０' ソース画像４２宛先ピクセル空間(宛先画像) ４４ドット４６、４８、５０、５２稜線頂点５４第１稜線５６第２稜線５８、６６従軸方向稜線６０、６２、７６、７８、８２、８４クリップ・ポ
イント６４宛先ピクセル列の線６５、６７、７０、７２、７４、８０、８６、８８宛
先ピクセル

Claims

【特許請求の範囲】

【請求項１】ソース・ピクセル画像を主軸方向および従
軸方向を有する宛先ピクセル空間へマップする方法であ
って、上記ソース・ピクセル画像の第１稜線および第２稜線に
関して、ソース画像稜線交点の上記宛先ピクセル空間座
標値を取り出し、かつ、それら交点の１つを起点と定め
るステップと、上記起点の座標から主軸方向に沿って進んで最初に出会
う宛先ピクセル線を決定するステップと、上記第１稜線および第２稜線それぞれと上記最初に出会
った宛先ピクセル線の交点に位置する２つのクリップ・
ポイントを計算するステップと、上記最初に出会った宛先ピクセル線から上記主軸方向に
移動した位置にある次の宛先ピクセル線を決定するステ
ップと、上記第１稜線および第２稜線それぞれと上記次の宛先ピ
クセル線の交点に位置する２つのクリップ・ポイントを
計算するステップと、上記最初に出会った宛先ピクセル線に沿って第１の従軸
方向に位置するピクセルの各々に対して、現在時ピクセ
ルの次の宛先ピクセルが当該宛先ピクセル線のクリップ
・ポイントを越えない限り、画面表示値を割り当てるス
テップと、上記次の宛先ピクセル線にあって当該宛先ピクセル線に
関して既に計算されたクリップ・ポイントの範囲内にあ
る１つのピクセルに対して画面表示値を割り当てるステ
ップと、上記次の宛先ピクセル線に沿って第２の従軸方向に位置
するピクセルの各々に対して、現在時ピクセルの次の宛
先ピクセルが当該宛先ピクセル線に関するクリップ・ポ
イントを越えない限り、画面表示値を割り当てるステッ
プと、上記ソース画像の境界内にある後続の宛先ピクセル線す
べてに関して、各宛先ピクセル線毎に上記従軸方向を反
転させながら、次の宛先ピクセル線の決定、そのクリッ
プ・ポイントの取り出しおよびクリップポイント内にあ
る各宛先ピクセルに対する画面表示値の割り当てを実行
する上記諸ステップを繰り返すステップと、を含むピクセル画像マッピング方法。