JPH0612051A

JPH0612051A - 画像表示装置

Info

Publication number: JPH0612051A
Application number: JP3084171A
Authority: JP
Inventors: D Adelson Steven; ディーエイデルソンスティーヴン; J Flattarolla Gary; ジェイフラッタローラゲアリー; George L Heron; エルヘロンジョージ
Original assignee: EDOSAN LAB Inc
Current assignee: EDOSAN LAB Inc
Priority date: 1990-04-17
Filing date: 1991-04-16
Publication date: 1994-01-21
Also published as: US5065144A

Abstract

(57)【要約】【目的】小規模のディスプレイとパレットメモリで広
範囲のカラー陰影を提供すること。【構成】画像表示システムにおけるエンコーダが画像
ソースからの明確に表示されたピクセル値をそのミック
スランコード化表現に変化してそれらをディスプレイメ
モリのロケーション内へストアする。ディスプレイ機構
はそのストアされたデータをディスプレイメモリから引
出して、アンチエリアス目的で先に使用されたタイプの
ミックスランコーディングスキームに従ってそれらを解
釈する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はイメージディスプレイ装
置、殊にかかる装置が画像データを記憶する方法に関す
る。

【０００２】

【従来の技術】典型的な電子ディスプレイ装置はＣＲＴ
その他の装置を使用してそれらに提示される画像を一系
列の電圧として表示している。デジタル／アナログ変換
器は上記装置がその画面上にデータを表示する速度と同
一の速度で高速ディスプレイメモリから読取られた画像
データに応じてアナログ電圧の系列を生成する。

【０００３】上記画像は複数の画素、即ちピクセルに編
成される。典型的な画面全体にわたる画像は例えば、一
行あたり６４０ピクセルの４８０行から成るアレイの形
に編成することができる。カラーモニタの場合、各ピク
セルの値は３次元（赤、緑、青）ベクトルとして表現さ
れ、そのベクトルの各成分は例えば８ビットの解像度を
必要とする。従って、その大きさの画像全体にわたって
可能な完全な色レンジを指定するにはその大きさが８ビ
ット／成分×３成分／ベクトル×６４０ベクトル／行×
４８０行オーダの、即ち７メガビット以上のメモリのデ
ィスプレイメモリが必要になる。ディスプレイメモリは
ディスプレイ装置の走査速度に匹敵する程十分高速でな
ければならないから、かかるメモリ条件はディスプレイ
装置のコストを相当増加させることになる。しかし、か
かるコストは低水準システムにとっては許容することが
できない。

【０００４】幸いなことに、ディスプレイメモリの大き
さを小さくする手法が従来より発見されている。その典
型的な手法は「パレットメモリ」を使用することであ
る。パレットメモリによれば、さもなければ例えば８ビ
ット／成分×３成分／ピクセル＝２４ビット／ピクセル
を含まなければならないディスプレイメモリを同じ解像
度を得るためにピクセルあたり例えば４もしくは８ビッ
トしか使用しないで済むことになる。上記パレットメモ
リはディスプレイメモリとデジタル／アナログ変換器と
の間に配置され、ディスプレイメモリの例えば８ビット
出力をその２⁸＝２５６個の２４ビットロケーションの
一つのアドレスとして解釈する。即ち、２ ²⁴の可能なベ
クトルの全てを含む代わりに、それは８ビット方式では
たったの２５６のユーザによって選択される値から成る
「パレット」を含むことになる。ユーザは更に２²⁴の可
能なピクセル値の何れも使用することができるが、任意
の一つの画像中ではそれらのうち２５６しか使用するこ
とができない。かかる範囲の値は大部分のコンピュータ
生成グラフィック分野の表示にとっては十分すぎるた
め、ユーザはシェージングを用いるプログラムから生ず
る天然画像とコンピュータ生成画像を表示するためだけ
にも高水準システムに訴える必要がある。

【０００５】

【発明が解決しようとする課題】本発明は低水準システ
ムが一つの画像中に使用することの可能な陰影の範囲を
若しくは拡大することによって天然画像その他の陰影画
像を表示することができるようにする機構に関する。殊
に、本発明は「ミックスランコーディング」の思想を天
然画像その他の陰影画像に適用するための方法と装置に
関する。

【０００６】ミックスランコーディングの手法は米国特
許第 4,704,605号（１９８７年１１月３日、発明者ステ
ィーブン・Ｄ・エーデルソン、“ピクセルマッピングコ
ンピュータグラフィックにおけるアンチエリアスエッジ
を提供する方法と装置”）に解説されている。上記特許
はコンピュータ生成画像中の異なる色の領域の間にしば
しば現われるぎざぎざのついたエッジを取除く方法につ
いて解説している。上記のぎざぎざのエッジはＣＲＴそ
の他のディスプレイ装置の空間解像度を内在するデータ
の空間周波数レンジに対するナイキスト基準を満たすも
のではないために生ずるものである。 '６０５特許の手
法は、その高い空間周波数成分を除去するために内在デ
ータを従来のように計算集約的に濾波せずにぎざぎざの
ついたエッジを大部分除去するものである。

【０００７】同手法によれば、それぞれの走査線は有限
の厚みを有するものと考えられ、それぞれのピクセルは
有限の幅をもつものと考えられる。従って、水平線と一
定角で一本の走査線を通過するエッジは一つ又はそれ以
上のピクセルを２つに分割する。ディスプレイメモリ
は、エンジがエッジの２辺上の色のミックスとして通過
する各ピクセルを表わす。その混合の比率はピクセルの
何れの部分がエッジの各側にあるかによって決まる。

【０００８】本発明はこの思想を実施するために '６０
５号特許が開示する方法を適用したものである。ミック
スラン・コーディングにおいては一つのエッジが通過す
るピクセルのピクセルワードはピクセルが表示する陰影
の自立的な表示ではない。即ちミックスから得られるの
はピクセル値のパレットメモリアドレスではない。その
代わりに、それは表示さるべきピクセル値がその割合を
ミックスさるべき２つのピクセル値に適用することによ
って計算されなければならないような割合を含む。それ
らの値の少なくとも一つは異なるピクセルに対するピク
セルワードの内容を参照することによって確認されなけ
ればならない。

【０００９】'６０５号特許の方式では、計算装置はデ
ィスプレイとパレットのメモリの出力を受取り、エッジ
の２つの側に対するパレットメモリ値をラッチし、その
エッジピクセルに対してピクセルワードによって表現さ
れる部分に従って２つの色の混合を計算し、その結果得
られる値を全てリアルタイムでＣＲＴディスプレイを制
御するデジタル／アナログ変換器へ加える。その趣旨は
従来の２次元濾波を行なわずにエリアスを除去するため
である。

【００１０】本発明はミックスラン思想を必ずしもエッ
ジでなく必ずしもコンピュータグラフィックスシステム
に発生しなかった画像特徴の表示に拡大するものであ
る。そうする場合、本発明は計算回路の使用によってパ
レットメモリ内にない陰影を表示する、即ち、パレット
メモリ値間に補間された陰影を表示することができると
いう事実を活用するものである。それがミックスランエ
ンコーディングを使用する、従ってそのパレット拡張能
力を得る画像は画像を従来のピクセル・バイ・ピクセル
の方法で表現するソースから得られるのが普通である。
（ピクセル・バイ・ピクセル法とはそれぞれの画像ピク
セルに相当する個々のピクセルロードの各々が表示さる
べきピクセル値を判断するために他のピクセルの値を参
照する必要のない一定の表現形式を含むことを意味する
ものとする。）本発明によれば、ミックスランエンコーダは厳密なピク
セル・バイ・ピクセル表現を「ミックスラン」表現に変
換し、その結果をディスプレイ内にストアする。（ '６
０５号特許はかかる表現に対するコード側は与えてい
る。）変換を実行するために、エンコーダはソースピク
セルワード内をサーチしてミックスラン表現のピクセル
ワードの「ラン」に変換する上で役立つシーケンスを発
見する。かかる表現においては、ランはそれからその内
部の種々のミックスが計算されるはずの一組の、典型的
には２つの値によって特徴づけられる。ミックスラン表
現はラン開始時の２つのピクセルワードとしてほぼピク
セル・バイ・ピクセル方式で特性値を提示するのが普通
であり、その特性値としてそれがランに変換するソース
シーケンスの開始と終了時におけるピクセルを選択す
る。ラン内の残りの中間ピクセルワードはそれらのピク
セル値を部分として表現する。それらは所期のピクセル
値に達するためにそのランの特性値（典型的には２個）
に加えられなければならない。

【００１１】エンコーダは一つの画像を構成するソース
ピクセルワードからの短いシーケンスを検査することか
ら始める。もしそのピクセルがシーケンスが特性値の共
通の組のミックスとしてシーケンスが十分近似可能と評
価すれば、エンコーダはシーケンスが変換を許されるも
のとしてもう一つのソースピクセルワードをそれに加え
ることを認識し、延長されたシーケンスも受け容れ可能
であるかどうかを判断する。もし受け容れ可能であれ
ば、プロセスは進行する。もし否であれば、最後の受け
容れ可能なシーケンスを採用し、一定のランへ変換して
次のシーケンスに対して処理を反復する。

【００１２】その結果、原始画像のミックスランによっ
てコード化された翻訳は通常、主観上原始画像の非常に
近くに現われ、この結果はさもなければ必要とされる３
倍もしくはそれ以上の倍数だけディスプレイメモリの大
きさを大きくする場合のコストと比べて僅かなハードウ
エアコストの増加によって達成することができる。然し
ながら、一定の画像については、我々はこの手法の応用
によっても混合近似が原始画像と１ビットほどしか異な
らない場合でも画像中にストリークが見出されることを
発見した。然しながら、ミックスによって正確に実現可
能なシーケンスのみを受容れるためにはパレットサイズ
の必要条件は過大なものとなる虞れがある。本発明の一
面によれば、我々は近似を受容れるがシーケンス許容基
準の厳格さをシーケンスの長さに依存させることによっ
てかかるストリークの発生を排除することができる。例
えば以下に示す実施例では、最大許容誤差をシーケンス
サイズが大きくなるにつれて小さくすることができる。
この手法によればラン数を増加させずに生成画像の主観
的許容度を著しく向上させることができることが判っ
た。これは明らかに誤差が大きければ長いランよりも短
いランの場合の方がより気づかれなくてすむという理由
によるものである。

【００１３】上記の如く、シーケンスエンドポイントが
特性値として選ばれるコードを使用することができ、デ
ィスプレイメモリラン内へコーディングさるべきソース
シーケンスを選択するプロセスにはソースピクセルワー
ドの候補シーケンスを１ワードだけ繰返し長くし、シー
ケンス中の中間値がそのエンドポイントから補間するこ
とが可能であるかどうかを判断する作業を伴う。もし長
くなったシーケンスの介在するピクセルワードがそのシ
ーケンスの最初と最後のピクセルワード間で補間不可能
であれば、最後の許容可能な長さにドロップバックして
その結果得られるシーケンスを採用してランに翻訳す
る。このアプローチによればミックスランコードにより
適当にコード化された画像が得られるが、一定の画像の
“テクスチャ”領域ではこのアプローチによっては多く
の短いランが生ずることが発見された。これは所要パレ
ットを大きくしがちであるから望ましくない。本発明の
一定の面に従えば、我々はこの問題点を相当軽減するこ
とができる。

【００１４】例えば、本発明の一面によれば（“局部最
大値の無視”と称する）、たとい候補シーケンス自体が
そこから全ての介在値が十分近似化可能なエンドポイン
トを提供せずともソースピクセルワードの候補シーケン
スの長さを延長する場合がある。我々は次のピクセルワ
ードがかかる値を提供することを示す所定基準にそのシ
ーケンスが合致するような状況で長さを延長する。かか
る基準の例は、以下に説明するような意味でシーケンス
の「局部最大値」であるようなピクセル値がシーケンス
内に存在する場合である。もしその他のピクセルが右エ
ンドポイント値の代わりに局部最大値を置換することに
よって他のピクセル値を近似化することができれば、た
といその現在の長さで許容不可能であってもそのシーケ
ンスを長くし続けることができる。

【００１５】平均ランレングスを大きくするもう一つの
方法はガンマ補正を考慮に入れることである。当業者に
は周知の通り、典型的にストアされたピクセル値はＣＲ
Ｔその他のディスプレイ装置上に得られる輝度を表わす
が、これらの輝度はそれらを得るために装置に加えられ
る電圧に対して線形的にではなく指数関数的に関連す
る。従って、所望の輝度を得るにはパレットメモリ（又
は本発明の思想を活用する装置の場合にはデコーダ）と
ディスプレイ装置間にガンマ補正回路を配置する。ガン
マ補正回路は関数Ｖ＝Ｉ^1/Tを効果的に実行する。但
し、Ｖはガンマ補正回路の出力であり、Ｉはその入力、
Ｔはディスプレイ一装置特有のパラメータ（通常２〜
３）である。

【００１６】この関数の結果、入力変化はレンジの若干
部分のそれに対応する出力変化よりも大きく、他の部分
では小さくなる。従って、命令されたピクセル値の変化
によってもＣＲＴに加えられる電圧には実際上の変化は
何ら生じない。我々はもしそれらのミックス近似ピクセ
ル値によって許容可能な限界内にある値から得られるも
のと全く異ならないＣＲＴに対する入力が得られるなら
ば、さもなければ許容不可能なシーケンスを許容するこ
とによってこの事実を考慮することができる。

【００１７】本発明の手法によれば大抵の種類の画像の
良質の翻訳を可能にすることができるが、パレットメモ
リの容量が限られているためにその表示が最初は許容で
きないような一定の画像を存在する。我々はそのような
多くの画像であってもよりゆるやかなエラー基準によっ
てコーディングプロセスを再実行するだけで先に拒否さ
れた候補シーケンスの幾つかを許容可能にし、パレット
の要求条件を軽減することによって首尾良く表示できる
ということを発見した。

【００１８】これらの手法を用いることによって、低水
準ディスプレイシステムが同時に表示可能なピクセル値
の数を著しく拡大することができる。

【００１９】

【実施例】図１はソース１４からランミックスコード化
表現へ画像の通常のピクセル・バイ・ピクセル表現をコ
ード化するエンコーダ１２により識別されるコンピュー
タディスプレイ装置を示す。上記エンコーダは合成ミッ
クスランコード化ピクセルワードをディスプレイメモリ
１６内にストアする。その結果、 '６０５号特許中に解
説のタイプのアンチエリアス目的のディスプレイ機構１
８はそのデータをソース１４がピクセル・バイ・ピクセ
ル形式で供給する画像を表示することができる。

【００２０】ディスプレイ機構１８は大部分従来形のイ
メージジェネレータ２０を使用する。同ジェネレータ２
０は普通リードオンリーメモリの形をしたガンマ補正回
路２４を３つ内蔵し、８ビットピクセル値成分をそれら
の成分が表わす輝度を得るために必要とされるＣＲＴ電
圧の８ビット表示に変換する。ガンマ補正回路２４は、
それぞれその入力を３つのＤ／Ａ変換器２６の対応する
一つに加える。上記Ｄ／Ａ変換器２６はカラーＣＲＴ２
８の赤、緑、青の電子銃のそれぞれ一つに対して制御電
圧を生成する。図面には本発明のカラーバージョンを示
すことにする。何故ならばその広い局面は原則としてモ
ノクロディスプレイにも適用することが可能であるが、
その利益はカラー装置について最も明らかであるからで
ある。

【００２１】同様に従来通り、本システムはディスプレ
イメモリ１６からのピクセルワードの取出しをＣＲＴ２
８の走査と同期させるタイミング回路３２を含む。回路
３２は図１におけるその表現がタイミング入力挿入記号
Λを含む要素の全てを同期化する。即ちタイミング信号
を送る。変換機構３４はディスプレイメモリ１６とイメ
ージジェネレータ２０間に介在させディスプレイメモリ
１６の８ビットランコード化出力をそれぞれが３つの８
ビット成分の形をしたピクセル値ベクトルに変換する。
上記変換機構はそれぞれの成分をガンマ補正回路２４の
異なる一つに加える。エーデルソンの '６０５号特許
（本文中に組込む）はかかる回路とそれらが使用するミ
ックスランコードの例について解説している。従って、
ここではごく簡単にミックスランコードの使用について
論ずることにしよう。然し、そうする前に、本文中に使
用する命名法を若干説明しておくことが有益であろう。

【００２２】本文で使用するピクセル値とは所与のピク
セルの表示即ち、そのグレイカラーもしくは陰影である
か、そのカラーもしくは陰影を明示的に定義するベクト
ル（モノクロ表示の場合にはスカラー）の表示の何れか
を意味するものとする。変換機構３４の出力はピクセル
の表示を明確に定義するからピクセル値となり、ディス
プレイメモリ１６の出力はパレットメモリの内容を参照
することによってのみピクセル値を識別するからそうで
はない。ソース１４の出力もピクセル値を有することが
普通である。

【００２３】ピクセルワードとは一つのピクセルに対す
る画像データである。かくして、変換機構３４の出力は
２４ビットピクセルワードの形に編成される一方、ディ
スプレイメモリ１６の出力は８ビットピクセルワードに
編成される。従来通り、ディスプレイメモリ１６はＣＲ
Ｔ２８の走査と同期して動作し、あたかもＣＲＴ画面上
に各ピクセル用の別個のロケーションを含んでいるかの
ように動作する。実際にはディスプレイメモリ２８内へ
の記憶はその最も小さなアドレッシング可能な単位が幾
つかのピクセルワードを含み、それらピクセルワードが
同時にＲＡＭから取出され、しかも順次ディスプレイメ
モリ出力線上を伝送されるようになったランダムアクセ
スメモリによって行われる。大抵の目的では、その効果
はあたかも幾つかのピクセルワードが個々にアドレッシ
ング可能であるのと同一となる。従ってロケーション
は、たとい別々にアドレッシング不可能であっても一つ
のピクセルワードを含むメモリ部分を指示するために使
用されることになろう。

【００２４】さて、変換機構３４の動作について述べ
る。変換機構３４は殆んど常にサード／ライトメモリで
ある従来のパレットメモリ３６を含む。但し、本発明の
概括的な原理はパレットメモリがリードオンリーメモリ
であるような構成にも適用することができよう。本発明
の概略的な原理を実施するには不要ではあるが、ダイナ
ミックパレットローダ３７（その動作については以下に
説明する）を追加的に使用することができる。さしあた
り、ダイナミックパレットローダは単にディスプレイメ
モリの８ビット出力をそのアドレスとして２５６ロケー
ションパレットメモリ３６へ送るものと考えることがで
きる。それぞれのパレットメモリロケーションは上記の
ように２４ビットを含む。

【００２５】デコーダ３８はディスプレイメモリ１６の
出力と共にパレットメモリの出力を受取る。ディスプレ
イメモリ出力が１９１と２２３の間の値を有しない限
り、デコーダ３８は単にパレットメモリ出力をガンマ補
正回路２４へ送るだけである。従ってそれらのディスプ
レイメモリ出力がない場合、ディスプレイ機構１８は以
下の２つの例外は別として従来通り動作する。第１の例
外は所与のディスプレイメモリ出力ワートに由来するパ
レットメモリ出力ワードの発送をデコーダ３８が次のワ
ードを検査する機会をもつまで遅らせることができる程
上記成分の同期化がずらされる点である。第２の例外
は、もし次のワードが１９１と２２３の間の値を有する
場合、デコーダ３８はその所与のソースに対するパレッ
トメモリ出力を発送しない点である。その代わりデコー
ダは、以下に説明する目的で、それに先行するワードに
対するパレットメモリ出力を反覆する。

【００２６】デコーダ３８は、１９１〜２２３間のディ
スプレイメモリ出力をオプコードとして処理する。若干
の側では、デコーダは１９１のディスプレイメモリ出力
を、以下に述べるような形でパレットメモリ内容を変更
するコマンドとして処理する。デコーダはその値が１９
２と２２３の間にあるディスプレイメモリ出力を最後の
２つの非オプコードディスプレイ出力から得られるパレ
ットＲＡＭ出力のミックスを計算するコマンドとして処
理する。また、ミックスの表示の如きコマンドの最下位
５ビットを解釈する。

【００２７】殊に、１９２〜２２３間のそれぞれのディ
スプレイメモリ出力ｙはｍｎ＝（ｙ _n−１９２）／３２
となるように部分ｍを表現する。この部分
ｍｎのため、最後の２つの非オプコードディスプレイメ
モリ出力Ｘ₁とＸ₂から得られるベクトルＸ₁とＸ₂の
ベクトル混合Ｍ_nが計算される。即ちＭ_n＝ｍｎＸ₁＋（１−ｍｎ）Ｘ₂ 典型的なディスプレイメモリ出力のシーケンスと変換機
構３４の合成出力は以下の通りである。

【００２８】Ｘ₁ Ｘ₂ ｙ₃ ｙ₄ ｙ₅ ｙ₆ ｙ₇ Ｘ₁ Ｘ₁ Ｍ₃ Ｍ₄ Ｍ₅ Ｍ₆ Ｘ₇，但し、Ｘ_nは非オプコード出力で、ｙ_nはミックスを表
現するオプコード出力である。このシーケンス点検によ
って変換機構は単に第１の非オプコードディスプレイメ
モリ出力Ｘ₁がアドレッシングするロケーションのパレ
ットメモリ内容Ｘ ₁を発送するだけであることが判る。
これは、デコーダ３８が前方を見てディスプレイメモリ
の次の出力Ｘ₂も非オプコードワードであることを理解
するためである。然しながら、ディスプレイメモリ出力
Ｘ₂に応じて、変換機構３４は単にＸ₁出力を繰返すの
みである。以下に詳説するように、これはＸ₂出力の次
にはオプコード出力ｙ₃が続き、非オプコードワードに
続くオプコードは何れコーディングプロセスが非オプコ
ード値を含むディスプレイメモリロケーション内に対応
するピクセル中に表示さるべき値ではなくてミックスに
より表示される値の“ラン”の他端に表示さるべき値を
配置したことを示す。

【００２９】考えてみるとこの構成は２つの同一ピクセ
ル値から始まる全てのランを表示する必要があることが
判る。このことはミックスランコーディングスキーマの
柔軟性を担当減ずるように思われるかもしれない。即
ち、２つの隣接するピクセルが同一でない限りランをス
タートすることはできない。然し、実際には同一の又は
殆んど同一の隣接ピクセルは大ていの天然画像では非常
に頻繁に生ずるために、このことは些細な制約にすぎな
い。更に、全てのミックスランコードが同一の隣接ピク
セルの存在を必要とするわけではない。 '６０５号特許
が示すように、他のミックスランコーディングスキーマ
は、たった１つの他のピクセルワード（２個ではない）
に対する参照しか所望混合を生成するために必要でない
ようにミックスとピクセル値の双方を含むピクセルワー
ドを使用する。かかる構成は隣接ピクセルどうしが同一
であることを要せず、本発明の原理はかかるコード化ス
キームの場合にも実施可能である。

【００３０】装置の同期部分、即ち、デコーダ１２の下
流の要素の動作はコンピュータ生成画像のエッジのエリ
アスを除去するために '６０５号特許に記述されるもの
と大部分同一である。然しながら、本発明によれば、現
実のピクセル値としてストア可能な天然画像を表示する
ために同一の機構を使用することができる。本発明の利
点はかかる構成が生成可能なピクセル値の範囲を計算す
ることによって理解すことができる。２５６の可能なデ
ィスプレイメモリ出力のうち、３３がオプコードであ
る。このため２２３のパレット値が残る。３２の異なる
ミックスを乗じ２で割って複製するペア形の２２３値の
組合せの数によって790,000 以上の同時に利用可能な異
なる値を生みだされる。これが従来８ビット方式のばあ
いに利用可能なレンジ（２５６）よりも数オーダ大きな
値であることは明らかである。更に、この範囲はディス
プレイメモリ内の完全な３成分ピクセル値をストアする
（ずっと高価な）装置で利用可能なレンジのほぼ５％に
すぎないけれども、その結果生ずる主観的な画像品質の
差は小さいのが通常で、その差の多くも大ていの場合、
ダイナミックパレットローディング、即ち一回の走査の
最中にパレットの内容を以下に述べるような形で変更す
ることによって除去されることになろう。

【００３１】かかる画像をミックスランコード化法によ
って表示するために、本発明はエンコーダ１２を使用す
る。その下流の回路と異なって、エンコーダ１２はリア
ルタイムで動作する必要はなくパーソナルコンピュータ
やワークステーション中に見出されるような汎用プロセ
ッサ中に具体化されるのが普通であろう。但し、適当な
専用ハードウエアによってその機能をリアルタイムベー
スで実行することができよう。エンコーダはピクセル・
バイ・ピクセル形式で磁気ディスク・ＣＤ・ＲＯＭ又は
光ディスクの如き廉価で低速の媒体中に最初記憶された
画像を処理することになろう。

【００３２】図１は説明を容易にするために種々のシス
テム要素を区別したものであることを強調しておくべき
であろう。同図は回路ボードと集積回路中における通常
の区分けを示すものではない。実際には、タイミング回
路３２は従来パーソナルコンピュータに使用されたタイ
プのビデオ／グラフィック（“ＶＧＡ”）制御ボード中
に設けるのが普通であろう。その同じボードはエンコー
ダ出力をディスプレイメモリ１６へ送り、ディスプレイ
メモリ１６に対して図面に表示されないデータをディス
プレイ１６内へ取り込み、またそこから取出すために必
要なリード／ライト、ストローブ、およびアドレス信号
を加え、その取出されたデータをパレットメモリ３６に
対するアドレスとして発送するために使用されるのが普
通であろう。ＶＧＡコントローラもパレットメモリ３６
に対して正規リアルタイム動作に必要なリード信号とス
トローブ信号を提供し、またエンコーダ（即ちマイクロ
プロセッサ）制御下での初期パレットローディングに必
要とされるストローブ、データ、およびライト信号も供
給することになろう。

【００３３】パレットメモリとＤ／Ａ変換器は従来形デ
ィスプレイ装置内の“ＲＡＭ−ＤＡＣ”シングルチップ
上に設けるのが普通である。ダイナミックのパレットロ
ーダ３７とデコータ３８（その構成は米国特許出願07/4
52,022号（ピクセルベースディスプレイ用ダイナミック
パレットローディングシステム）、１９８９年１２月１
９日）に示す）を介在させるためにはＤ／Ａ変換器２６
から隔ったチップ上にパレットメモリ３６を設ければよ
い。然しながら、かかるチップは従来のＲＡＭ−ＤＡＣ
チップの場合はプラグ間で互換可能な部品として製作で
きるから、パレットメモリ３６、ダイナミックパレット
ローダ３７、デコーダ３８、Ｄ／Ａ変換器２６より成る
シングルチップを製作することが望ましい。

【００３４】エンコーダ１２は図２，３に関して以下に
説明するような形で動作する。図２，３のルーチンの全
体的アプローチはその開始と終了ワードが介在するピク
セルワードによって表現されるピクセル値の全てを近似
させるために補間可能な値を表わすソースピクセルワー
ドシーケンスを識別することでる。上記シーケンスはそ
の後長くなって最早識別することである。上記シーケン
スはその後長くなっ最早この基準を満たさなくなるまで
１ピクセルだけ繰返し延長される。その後、ルーチンは
最後の許容可能なシーケンスに復帰し、それをミックス
ランとし続くコーディングのために採用し、続くピクセ
ルワードについてその手続を繰返す。

【００３５】図２，３のルーチンはステップ６０から始
まる。同ステップ６０ではルーランはそれがソース１４
から受取る画像中の最初のピクセルワードから開始す
る。ステップ６２において、ルーチンはそのワードの次
に少なくとも３つのワードが続き、４ワードシーケンス
を作ることになるかどうかを判断する。一つのランは理
論上２ピクセルワードからしか構成されないことになっ
ているが、３個のランによってはパレットメモリ容量は
節約されないから実際には４個必要である。即ち、もし
最初の２ワードが同一であれば、同ラン中の３ワードは
ミックスランコーディングがなければ２つのパレットエ
ントリーしか必要ではなかろう。従って、もし４ワード
が残らなければ、ルーチンはブロック６４が指示するよ
うに非ミックスベースでコード化するために３コンピュ
ータもしくはそれ以下の残存ワードを採用する。即ち、
次のコーディングプロセスは非オプコードコードを対応
するディスプレイメモリロケーション内に置くことにな
ろう。その後図２，３のルーチンは終了し、パレットメ
モリ割当てと実際のコーディングがスタートする。

【００３６】もし４ワードが残されると、ルーチンはス
テップ６６で最初の２ワードが同一であるか、またはそ
れらを同一に表示することが異論のない程同一に近いも
のであるかを判断する。上記の如く、選ばれたミックス
ランコード中のランは全て２つの同一に表示されるピク
セルからスタートする。もし最初の２ワードが余り異な
ると、それらはランを開始することはできず、ステップ
６８は非ランベースでコード化するために最初のワード
を採用する。即ち、現在のピクセルワードはオプコード
としてストアされもしなければ、ミックス操作中のオペ
ランドの一つとしても使用されることはないであろう。
その後、ルーチンは１ソースピクセルワードだけ画像内
を進み、ステップ６２に復帰する。

【００３７】他方、もしルーチンが殆んど同一のピクセ
ル値を表わす２つの新しいピクセルワードのシーケンス
を発見しなければ、ステップ７０へ進み、第３のワード
をその同一２ワードに加算して候補シーケンスを形成し
た後、ステップ７２で第４のワードを加算する。さて、
その結果得られる候補シーケンスをテストしてミックス
ランへコード化することが適当であるかをテストする態
勢となる。まず、ルーチンは最大エラーを調節する。こ
の最大エラーはパレット値間の補間が原始画像中のピク
セル値に十分近似することが可能であるかどうかを判断
するために使用されることになる基準である。本発明に
よれば、ルーチンはそれが候補シーケンスのサイズによ
って変化するようにこの基準を調節する。同基準は比較
的高い割合のエラーとしてスタートする。即ち、ルーチ
ンはエラーのソースピクセル値の大きさに対する比を判
断し、その結果を最大エラー基準と比較する。候補シー
ケンスのサイズが次のループの通過中に大きくなるにつ
れて、最大エラー基準は小さなパーセンテージに減少
し、その後小さな絶対値となる。

【００３８】従って、出力ランサイズが大きくなるにつ
れて、近似は増々優れたものになる筈である。我々はこ
のアプローチが所与の利用可能なパレットサイズについ
て生成される表示の主観的品質を向上させる傾向のある
ことを発見した。４ロード長のランの場合、我々は１２
％のエラー基準を使用する。即ち、ミックス計算ピクセ
ル値はランが許容可能であるとすれば全て対応するソー
スピクセル値の１２％の範囲内になければならない。こ
の最大エラー基準は１０のランレングスを４％に達する
まで次第に小さくなる。１０を上廻るランレングスの場
合、我々は絶対エラー値を使用する。即ち、既に候補シ
ーケンス中にあるピクセル値に対して４％の値を各成分
の平均に対して付与し、その結果得られる絶対エラー値
を各成分について１５のランレングスでゼロに達するま
で次第に減少する。

【００３９】判断ブロック７６で表わされる次のステッ
プは候補シーケンス中の介在するワードの全てによって
表わされるピクセル値がシーケンス内の最初と最後のピ
クセルワードによって表わされる値から補間可能である
かどうかを判断することである。エラーを定義する方法
は数多く存在するから特定の選択はあまり重要でないこ
とは明らかである。我々が使用する方法は以下の通りで
ある。候補シーケンスが、最初のピクセル値Ｘ_F、最後
のピクセル値Ｘ_L、および中間のピクセル値Ｘ _iを表わ
すピクセルワードから成ると仮定しよう。但し、各ピク
セル値Ｘはベクトル（Ｘ_R、Ｘ_G、Ｘ_B）である。絶対
値に対して適用する基準は０〜３１間にＥ_R＜
Ｅ_{R max}、Ｅ_G＜Ｅ_{G max}およびＥ_B＜Ｅ_{B max}となる
ような０〜３１間に整数ｎが存在しなければならないと
いうことである。

【００４０】但し、Ｅ_R＝｜ｎＸ_FR＋（32−ｎ）×ＬＲ
−32Ｘ_iR｜／３２また、Ｅ_GとＥ_Bは同様に定義される。エラーのパーセ
ンテージについては、Ｅ_{R max}、Ｅ_{G max}、Ｅ_{B max}は
絶対値ではなく割合であり、基準はＥ_R＜Ｅ_{R max}ＸＲ、Ｅ_G＜Ｅ_{G max}ＸＧ、Ｅ_B＜Ｅ_{B max}ＸＢとなる。

【００４１】もし候補シーケンスがこれらの基準を満た
せば、ルーチンはそれを、ブロック７８が示すようにミ
ックスランへコーディングしてさしつかえないものと認
識し、ルーチンはステップ８０へ進み、そこで画像の終
りに達したかどうかを判断する。もし達しておれば、ル
ーチンはブロック８２が示すようにその候補シーケンス
をミックスランにコード化するものとして採用し、プロ
セスは終了する。さもなければ、ルーチンはステップ７
２に戻ってもう一つのピクセルワードを加算して恐らく
もっと低い最大エラー値Ｅ_maxによって処理を反復す
る。この処理は新たなソースピクセルがループ内を通る
毎につけ加えられるという形でルーチンがソースワード
を使い尽くすか、延長シーケンスが最大エラー基準を満
たさなくなるまで継続される。

【００４２】上記延長シーケンスが最大エラー基準を満
たさない場合、ルーチンは、もし特定の実施例が使用す
るとした場合、ブロック８４で表わされるオプションの
ステップへ進む。それについては以下に詳説する。もし
そのステップが省略されると、ルーチンは直接ステップ
８６へ進み、そこで許容可能なソースピクセルのシーケ
ンスで識別されたが採用されなかったものがあるかどう
かを判断する。即ち、現在のベースワードからスタート
する何らかの許容可能なシーケンスを識別したかどうか
を判断する。もし否であれば、ルーチンは現在のベース
ワードで許容可能なシーケンスを形成しようとする試み
を中止する。即ち、現在ベースワードを非ランベースで
コード化するために採用し、ブロック８８と９０が示す
ように次のワードを新たなベースワードとして採用す
る。他方、もし一つもしくはそれ以上の許容可能なシー
ケンスを発見した場合には、ブロック９２が示すよう
に、ミックスランをコーディングするためにまだ採用さ
れていない最後の（最長の）ものを採用し、その採用さ
れたシーケンスに続くワードが新たなベースワードとな
る。

【００４３】その後、ルーチンはステップ６２へ戻り、
プロセスを再び開始する。そのプロセスは非ミックスベ
ース又はミックスランの一部としてであれ全ワードがコ
ーディング用に採用され終るまで反復される。さて、ブ
ロック８４に戻り、ブロックは先に述べなかった基準を
課する。これまで述べたルーチンは広範囲の画像につい
ては十分効果を奏する。然しながら“テクスチャ”のよ
うに見えて多数の短いランを生じさせる傾向のあるタイ
プの一定の画像が存在する。これらはパレットメモリの
容量を急速に消費する。然しながら、我々はかかる画像
の平均ランレングスは通常ステップ８４に例示されるよ
うな手続を使用することによって相当増加させることが
可能なことを発見した。ルーチンは候補シーケンスがス
テップ７６により課せられる基準を満たすことができな
い時、即ち、そのエンドポイントはそれからその中間ピ
クセルの値が補間可能な値を提供する場合、ステップ８
４へ入る。

【００４４】ステップ８４の目的は、中間値が現在のエ
ンドポイントから補間することはできないけれども、シ
ーケンスを延長することによってそれらが補間可能なエ
ンドポイントが得られるという指示についてテストする
ことである。この指示は候補シーケンス内の“局部最大
値”にもとづいている。所与のソースピクセルワード
は、もしシーケンス内の他のピクセル値の全ての赤、
緑、青の成分がシーケンス内の所与ピクセル値と最初の
ピクセル値のそれぞれの赤、緑、青の成分の間にある場
合のシーケンスの局部最大値を表わす。

【００４５】ブロック８４のステップは、まず、かかる
局部最大値が存在するかどうか、また、第２に、他のピ
クセル値が最初のピクセル値と局部最大値間で追加的に
補間可能であるかどうかを判断する。もしそうであれ
ば、ルーチンは、たとい、その現在の長さでは許容され
なくともシーケンスを延長することによって許容可能な
候補シーケンスが、見出せるかどうかを判断することに
取りかかる。

【００４６】一つのシーケンスはもしそれが局部最大値
を含んでいる場合にのみステップ８４の基準を満たすこ
とができることに注意すべきである。しかし、局部最大
値が存在することは許容可能なシーケンスが得られるそ
の他のピクセル値が存在するための必要条件ではない。
即ち、候補シーケンスを延長するとたといそれが局部最
大値を有すさずとも許容可能なシーケンスに変換するこ
とができる。適当するのに簡単であるためにステップ８
４の基準を満たすことができない場合には候補シーケン
スの延長を停止する。

【００４７】しかし、その他の基準も許容可能なシーケ
ンスを発見できるかもしれないという期待をもって許容
不能なシーケンスを延長する価値があるかどうかを判断
するために使用することができる。一つの方法は単に、
３次元空間内の点としてピクセル値全体を考察し、それ
らの点と線の間に最小２乗エラーが生ずる線について解
くことである。もし上記点の全てが線からの最大エラー
距離内にあれば、また残されたエンドポイント値の各成
分がシーケンス内の他の値の対応する成分の全てよりも
大きいか小さいかの何れかであれば、それから中間値で
補間可能な一つの値を更に発見することが可能である。
アルゴリズム上の単純さのために我々はかかる基準を選
ばなかったが、その基準又はそれに類似の基準は図２，
３のブロック８４により表わされるものと容易に代替す
ることができる。

【００４８】また、上記所論はランとしてコード化する
ために採用されたシーケンスが全て生成ランの特性値と
して、即ち、ランポイントの最初の２つのピクセルワー
ドに対するパレットエントリーとして選択されるシーケ
ンスエンドポイント値によってコード化されるという仮
定に基づいている。然しながら、図２，３のルーチンを
修正してランにコード化さるべき各ソースシーケンスの
識別だけでなくそのランの第２の特性値がどのようなも
のであるべきかについての別個の表示をコーディングプ
ロセスにパスするものと想定しよう。即ち、コーディン
グプロセスは右側のエンドポイントを第２の特性値とし
て自動的に採用しなかったと想定しよう。かかる構成で
は、ステップ８４の基準を満たすシーケンスは何れも許
容可能なものとは考えられず、かかるシーケンスに対し
てコーディングプロセスにパスされる値はその局部最大
値となろう。実際、たとい局部最大値が存在せずとも、
上記の代わりの最小２乗基準を満たしたシーケンスはそ
のシーケンス中にはない値を第２の特性値として使用す
ることによって採用することができよう。双方の場合と
も、最後のミックスコードは３２／３２＝１を表わさな
いのが普通であろう。結果として得られる画像の品質を
全く落とさずにステップ６６、７６、８４で課される基
準の厳格さを若干ゆるめる手法は、ガンマ補正回路の非
線形挙動によって値の束が得られるという認識によるも
のである。ステップ６６において２つの隣接ピクセルワ
ードによって表わされる値はその線成分を除いて全て同
一である（それぞれ２５０、２５１の値）と想定しよ
う。もしステップ６０で課せられる基準が始めの２つの
値が厳密に同一でなければならないということであると
した場合、それら２つの隣接値は基準を満たさず、した
がってそれらは許容可能なシーケンスの開始とはなり得
ないであろう。

【００４９】ピクセル値成分生成ＤＡＣ入力００１２３２３１３３７・・・・・・２５０２５３２５１２５３２５２２５４２５３２５４２５４２５５２５５２５５表Ｉ然しながら、表Ｉは、ガンマ補正回路２４がＤ／Ａ変換
器２６に適用するピクセル値成分と生成値間の対応関係
を示し、公称ピクセル値２５０、２５１の差は生成画像
に何らの差も生じさせないことが判る。すなわち、Ｄ／
Ａ変換器は両方の値からの結果が同じであると入力す
る。従って、ステップ６０を修正してそれらの生成ガン
マ補正値が同一であるならば異なるピクセル値を同一で
あると考えることができる。同様な修正はステップ７６
と８４に対して行うことができる。

【００５０】ソースピクセルの各々が非ミックスベース
上又はミックスランの一部としてコード化するために採
用された後に、エンコーダはそれが実際のコード化を実
行する前にパレットメモリを割当てる。即ち、パレット
メモリアドレスをミックスランコードの一部として使用
する前にパレットメモリ中の種々のピクセル値の位置を
知る必要がある。

【００５１】割当ては多くの方法で行うことができる。
我々が考察した一つの方法は３次元（図解例の場合は２
５６×２５６×２５６）のピクセル値空間を各成分範囲
を４つの等しい部分に分割することによって６４の等し
い区域に分割することからスタートする。その後、パレ
ットメモリロケーションが各区域内の最も頻繁に発生す
るエンドポイント値に割当てられる。このステップは多
くとも６４のロケーションを使用する。すなわち、もし
若干の区域が空白であれば、６４より少ない区域を使用
することになる。このステップからスタートするユニー
クなカラーを有する小さな特徴を描くことができる。そ
の後、残りの使用可能なロケーションを残りの別々のエ
ンドポイント値の間に適当な方法で割当てることができ
る。多くの場合、残るエンドポイントの数は残るパレッ
トメモリロケーションの数を上廻ることになろう。かか
る場合には、残るパレット値はエンドポイント概算から
発生するエラーを最小限にする方法に従って選択すべき
である。例えば、我々は“メジアンカット”アプローチ
を使用した。（ヘックベルト“フレームバッファディス
プレイ用のカラー画像の数値化”コンピュータグラフィ
ックス１６，３（１９８２年７月）、PP２９７−３０
７）割当て手続きが完了した後、ミックスランコードの実際
の生成が開始される。殊に、ミックスランエンドポイン
トとして識別された全ピクセルに対応するディスプレイ
メモリロケーションはそれらの各ソースピクセル値もし
くはそれらのピクセル値に最も近いパレット値の何れか
を含むパレットメモリロケーションのパレットメモリア
ドレスをロードされる。その後、ダイミナックパレット
ロードシーケンスを含まない全ての非エンドポイントピ
クセルのロケーションが適当なミックスコードをロード
される。その後、システムは画像を表示することができ
る。

【００５２】パレットが画像の表示全体を通して固定さ
れていれば以下のアプローチを使用する。然しながら、
画像の表示中はパレットをダイミナックにロードする。
即ちその内容を変更することが望ましい。このことを行
うには上記同時係属出願中に説明したタイプの回路を備
えるダイナミックパレットローダ３７を使用する。先に
示した如く、ダイナミックパレットローダ３７は通常は
ディスプレイメモリ１６の出力をそのアドレスとしてパ
レットメモリ３６へただ送るだけである。このことに対
する唯一の例外はディスプレイメモリ出力が１９１（ダ
イナミックパレットローディングを開始すべきコマン
ド）であった時に発生する。ダイナミックパレットロー
ダ３７がこのコードを受取ると、パレットメモリ３６の
読取りを中断する。それと同時に、同様にコード１９１
を受取るデコーダ３８は現在のパレットメモリの出力を
送らない。その代わりに、最後のパレットメモリ出力を
５つのピクセルワードタイムの間繰返す。上記時間はダ
イナミックパレットローダ３７がコード１９１の受取り
に応じて実行する処理の持続時間である。

【００５３】ダイナミックパレットローダ３７がこのコ
ードを受取ると、内部レジスタ内にそれぞれパレットメ
モリ内にストアさるべきピクセル値の赤、緑、青の成分
を表わす次の３つのピクセルワードの内容を一時保持す
る。第４のピクセルワードを受取るに応じてダイナミッ
クパレットローダ３７は保持されたピクセル値を続く第
４のピクセルワードが表わすアドレスのパレットメモリ
ロケーション内へロードする。ダイナミックパレットロ
ーダ３７とデコーダ３８は次の第５のワードが１９１で
ない限り、その正規処理を再開する。

【００５４】図４はダイナミックパレットロードシーケ
ンスを含むミックスランコードピクセルワードの継起状
況を示す。ディスプレイメモリピクセルワードＡとＢ
は、それらがパレットメモリ内にストアされるパレット
メモリロケーション４と２を指定することによってピク
セル値を表現するピクセルミックスコードである。ワー
ドＣはダイナミックパレットロードオプコード１９２で
ある。ワードＤ、ＥおよびＦはそれぞれパレットメモリ
内にストアさるべき非値の赤、緑、青の成分の値を含む
一方、ワードＧはその内部へピクセル値がストアさるべ
きパレットメモリロケーションのアドレス、即ち４を表
わす。従って、ダイナミックパレットローダ３７はピク
セル値（１６，２５５、０）をパレットロケーション４
内へロードし、先にそこにストアされた値を上書きす
る。ワードＨでは、オプコード１９１以来５ワードが発
生しているから、デコーダは最後のピクセル値を反復す
ることを中止し、その代わりにピクセル値をワードＨが
指示するパレットメモリロケーション２内へ発送する。
ワードＩはパレットロケーション４を指示するから、デ
コーダはちょうどロードされたばかりの値であるピクセ
ル値（１６、２５５、０）を生成する。

【００５５】ダイナミックパレットローディングを活用
するシステムでは、エンコーダは図５，６及び７で示す
ようなルーチンを使用してソースピクセルデータをダイ
ナミックパレットロード能力を活用するパレットアドレ
スコードとコマンドを含むディスプレイメモリ内容へ変
換する。このルーチンは図２，３に示すタイプの最初の
パスの結果を処理する。上記パスではミックスランは識
別されているがミックスはまだ計算されてないことが望
ましい。ミックスの計算を遅らせる理由は、それらがパ
レットメモリ内容に幾分依存するからである。それは図
５，６および７の第２のパレットロードパスの判断目的
である。それ故、ダイナミックパレットロードのために
コーディングする状況では“ソースピクセルワード”は
ミックスランコーディングパスの出力となる。

【００５６】エンコーダはダイナミックパレットローデ
ィングに付されるパレットメモリ内の各ロケーションに
対する最終使用値の現在テーブルの使用によってダイナ
ミックパレットローディングのロケーションと内容を判
断する。殊に、ルーチンはラスタ走査順序で画像中を進
み、画像内の種々のピクセルワードに対してパレットメ
モリアドレスを付与する。そうする毎に、ルーチンはそ
れが使用するパレットロケーションに対するその最終使
用エントリーを更新することによってその最終使用エン
トリーがそのパレットロケーションの最近の使用による
画像ロケーションを指定するようにする。

【００５７】かかるテーブルを維持する目的は図５に関
して以下に説明する。図５のルーチンはこのテーブルと
共に２つのポインタを使用する。そのうち、メインポイ
ンタはそのソースピクセル値をルーチンが現在パレット
値と近似させようと試みているピクセルのロケーション
を与える。第２のポインタは“ＤＰＬ”（ダイナミック
パレットローディング）ポインタであって、最後のダイ
ナミックパレットローディングシーケンスの終りを指示
する。ＤＰＬポインタは、そこから画像内のＤＰＬサイ
トの探索が再開されるポイントを表わす。即ち、図５の
所説より明らかとなるように、依然使用可能なＤＰＬサ
イトでＤＰＬポインタに先行するものは存在しない。

【００５８】図５が描くルーチンの最初のステップは初
期化ブロック１０２によって表わされる。このステップ
が表現する行動の大部分はルーチンが使用するテーブル
とカウンタを初期値にセットすることから成る。上記初
期化ステップはまたディスプレイメモリ内容に応じて走
査中に変化するパレットメモリの内容がそれらが同じ画
像の異なる走査における対応する点で呼出される時に異
なる内容を有しないようにするためにとられる行動を含
む。

【００５９】一貫した結果を確保するための一つの方法
は垂直方向にトレースしなおす間にパレットメモリを常
に最初の組の内容にリセットすることであろう。かかる
アプローチはダイナミックパレットローディングシステ
ムでは完全にうまく効果を奏するが、別の方法、即ち、
ダイナミックパレットローディング機構自体を使用し、
したがってダイナミックパレットローディングを実行す
るために行わなければならないハードウエアとソフトウ
エアの収容量を最小限にする方法によって初期化を実行
することが望ましい。

【００６０】ここで我々が使用するアプローチは原始画
像の最初の２本の線の内容を黒にセットすることであ
る。即ち、我々はその内容が通常、画像の重要でない部
分である情報を除去し、それを境界と置換える。その結
果、ダイナミックパレットローディングサイトの２本の
実線が与えられる。何故ならば、それら２本の線中のピ
クセル値の全ては今や同一であるからである。同じ結果
は境界をボトムに置くか、一本の黒い線をトップにお
き、もう一本をボトムに置くことによって得ることがで
きよう。以下に明らかとなるように、これらのダイナミ
ックパレットローディングサイトはその後、ディスプレ
イの情報格納部分の開始時と常に同一のパレットメモリ
内容の初期集合を提供するために使用されることになろ
う。

【００６１】他の初期化ステップをその目的が明らかと
なるにつれて以下に解説する。ブロック１０４は現在の
ピクセル、即ち、メインポインタが識別するピクセルに
対するソースワードを取出す処理を示す。もし先に示唆
するように黒の境界が最初の２本の線上に設けられてお
れば、ルーチンは最初の２本の線をスキップして、初期
化ステップはメインポインタを第３の線の初めにセット
していることになろう。但し、それを最初の線内の最初
のロケーションへセットしても何ら不都合は生じないで
あろう。ルーチンは、ブロック１０６が示すように取出
されたソースワードを点検してそのソースワードが一定
のピクセル値又はミックスを表わすものであるかどうか
を判断する。もしソースピクセルワードがミックスでな
ければ、ルーチンはステップ１０８へ進み、そこでパレ
ットメモリの「現在の」内容、即ちパレットメモリが走
査中のその点に有するはずの内容をサーチする。即ち、
最後に使用されるテーブルの外に、ルーチンは「現在
の」パレットメモリ内容を表わす内容テーブルを維持す
る。ルーチンは何らかのパレットエントリーが許容差内
で現在のピクセルの原始値を近似するかどうかを判断す
る。以下に説明するように、この許容差は一定とする
か、画像の内容に従って変化することができる。

【００６２】何れにせよ、もしルーチンがディスプレイ
の最初の２本の境界線をしてダイナミックパレットロー
ディングによってパレットメモリを適当に塗りつぶさせ
る場合には、ステップ１０８中でダイナミンクローディ
ングに付されるパレットメモリロケーションで境界領域
又はそれに続く領域におけるダイナミックパレットロー
ディングより生じなかった許容可能な内容を有するもの
が存在しないことが重要である。このため、初期化は通
常、この結果を確保する一定の手段を使用することにな
ろう。そうするための一つの方法はパレットメモリロケ
ーションに対して使用中のフラッグを維持してルーチン
が既にダイナミックパレットローディングによってそれ
らに値を付与したかどうかを指示することである。その
後、ステップ１０８はその使用中のフラッグがセットさ
れるパレットメモリロケーションのみを検査することに
なろう。

【００６３】もしステップ１０８の結果が肯定的であれ
ば、即ち、十分現在のソースピクセル値に近似するパレ
ットエントリーが存在すれば、ルーチンはステップ１１
０へ進み、そこでそのエントリーのパレットメモリアド
レスを現在のピクセルに対応するディスプレイメモリロ
ケーション内へ配置する。その後、ルーチンはそのパレ
ットメモリロケーションんに対する最後の使用エントリ
ーを更新する。即ち、そのパレットメモリロケーション
の最終使用エントリーは、パレットメモリロケーション
がメインポインタが現在指定する画像中の点で使用され
たことを示す値にセットされる。以下に見る如く、この
ことによってダイナミックパレットローディング処理が
現在コード化中のピクセルを表示するために使用可能と
なる前にそのパレットメモリロケーションの内容を変更
することが防止されることになろう。

【００６４】その後、ルーチンはステップ１１４へ進
み、そこで画像中のピクセルの全てが点検されたかどう
かが判断される。もし点検されていればルーチンが停止
することはいうまでもない。さもなければ、ルーチンは
メインポインタを進めてブロック１１６が示すように次
のピクセルを指定し、再度ステップ１０６からスタート
する。

【００６５】もしステップ１０８が現在のパレットメモ
リの内容が現在ソースピクセル値と近似していないと判
断すれば、ルーチンはブロック１１８により表現され図
６，７に詳しく示されるＡＳＳＩＧＮＰＡＬＥＴＴＥ
ＥＮＴＲＹ（パレットエントリー付与）サブルーチン
に進む。このサブルーチンの目的は、現在ピクセルに先
行するＤＰＬサイトを発見してＤＰＬコマンドを現在ピ
クセルに対する初期値に十分近似する内容をパレットメ
モリに対してロードするために使用することができるよ
うにすることである。

【００６６】先に述べた如く、ダイナミックパレットロ
ーディングサブルーチンはメインポインタと共にＤＰＬ
ポインタを使用する。ＤＰＬポインタは普通、メインポ
インタが指定するロケーションよりやや背後のロケーシ
ョンを指定しルーチンが次にＤＰＬサイト、即ち、それ
が正規オブジェクトコードロードをＤＰＬコマンドと取
替えることのできるサイトに対するサーチを再開するこ
とになる画像データ内の位置を表わす。ステップ１２０
はＤＰＬポインタが指定するソースワードの次に同一又
は一定の実施例では殆んど同一のソースコードの十分に
長いシーケンスが続くかどうかを判断する。この理由
は、ディスプレイ方式が、ディスプレイメモリがＤＰＬ
コマンドを含むディスプレイのロケーションにおける同
一ピクセル値のシーケンスを表示することによるのはい
うまでもない。それ故、ステップ１２０の基準を満たす
ピクセルワードのシーケンスは潜在的に可能なＤＰＬサ
イトである。

【００６７】最初、ステップ１２０の出力は常にイエス
である。即ち、最初の２本の線は全て黒にセットされて
あるから、最初の２本の線では全てのピクセルワードは
同一である。然しながら、最初の２本の線の後に、この
テストはしばしば失敗するのが普通で、ルーチンはステ
ップ１２２に進み、そこでＤＰＬポインタを増分する。
その後、ステップ１２４において、ルーチンはＤＰＬポ
インタが指定するピクセルシーケンスが依然メインポイ
ンタが指定するピクセルに先行するかどうかを判断す
る。もし否であれば、そのサイトに置かれたコマンドは
パレットメモリ内容を適時に変更してメインポインタが
指定するピクセルの表示に影響を及ぼすことはできな
い。

【００６８】従って、もしＤＰＬポインタがステップ１
２４によって課される基準を満たすことができなけれ
ば、ルーチンは最も近い現在のパレット値を受取らなけ
ればならず、従って、ルーチンはステップ１２６へ進
む。そこでルーチンは、たといその近似が最初ステップ
１０８によって課せられる許容基準を満たすことがなく
とも、その内容が所期のピクセル値に最も近いパレット
メモリロケーションを識別する。ルーチンが選択したパ
レットロケーションの最終使用エントリーを更新してそ
れが現在のピクセルで最後に使用されたとういことを示
すステップ１２７後には、ルーチンは選択されたパレッ
トメモリアドレスを現在のピクセルのオブジェクトワー
ドとして採用し、それを適当なディスプレイメモリロケ
ーション内へ配置する。ブロック１２８はこのステップ
を表わす。その後、サブルーチンは図４のメインループ
へ制御を戻し、当該ループは次のピクセルに進む。

【００６９】他方、もしＤＰＬポインタがステップ１２
４の基準を満たさなければ、ＤＰＬポインタが指定する
ピクセルシーケンスのＤＰＬコマンドは現在のピクセル
に影響を及ぼす可能がある。従って、ルーチンはステッ
プ１２０へ戻り、そこで再び同一ピクセルのシーケンス
を探す。それが探すシーケンスの長さは図解例の場合、
５又は６の何れかである。もしＤＰＬポインタが指定す
るシーケンスの直前にＤＰＬコマンドシーケンスが位置
すれば、第２のＤＰＬコマンド中に表示されるピクセル
値は第１のＤＰＬコマンド中に表示れるものと同一であ
るから、第２のＤＰＬコマンドを収納するには５つの同
一値しか必要でない（しかるに通常は６コンピュータ必
要である）。

【００７０】何れの場合にも、もしソースピクセルワー
ドのシーケンスがテスト１２０にパスすると、ルーチン
は何れのパレットメモリ内容がステップ１２０が識別し
たサイトのＤＰＬコマンドによって安全に変更できるか
を判断するプロセスを開始する。ステップ１３０はダイ
ナミックパレットローディングに付される最初のパレッ
トメモリロケーションに対するエントリーから最終使用
テーブルの検査を開始することを表わす。

【００７１】原則上は図解例のルックアップテーブル目
的で実際に使用される２２３のパレットメモリロケーシ
ョンの全ては“ダイナミックパレットローディング”に
付すことができよう。然しながら、実際には黒を表わす
一定値に対しては最初のパレットメモリロケーションは
保留するからその値をダイナミックパレットロティング
によって変更することはできない。このことは我々の特
別の初期化アプローチのために本構成においては有益で
ある。しかし、他のダイナミックパレットローディング
アプローチは必ずしもかかる一定値を必要としないであ
ろう。最初の黒を含むロケーションにおける変化を防止
するために、本構成ではステップ１３０で言及される
「最初の」パレットテーブルエントリーは実際には第２
のロケーション全体であるが、ダイナミックパレットロ
ーディングに付されるのは最初のものである。

【００７２】ステップ１３２において、ルーチンは最終
使用テーブルエントリーに打診し、ＤＰＬとメインポイ
ンタによって識別される画像ロケーション間に対応する
パレットメモリロケーションが使用さるべきかどうかを
判断する。即ち、ステップ１３２の目的はルーチンが中
間のオブジェクトワードの付与が基づくパレットエント
リーを変更しないようにすることである。テスト１２２
の肯定的な結果はこのパレットメモリロケーションを中
間に使用することがないということを示し、従ってルー
チンはステップ１３４へ進んで、そこでそのロケーショ
ンに対する内容テーブルエントリーを現在のピクセルロ
ケーション、即ち、そのオブジェクトワードをルーチン
が現在判断中のメインポインタより識別されるピクセル
で表示すべく意図されたピクセル値に変更する。これは
そのパレットメモリロケーションの最終使用ロケーショ
ンを変更すると共に、ステップ１３４はそのロケーショ
ンの最終使用フィールドを更新し、その最終的な使用が
それまで現在ピクセルで行われることを示す。

【００７３】その後、ルーチンはステップ１３６へ進
み、そこで適当なダイナミックパレットローディングコ
マンドをＤＰＬポインタが識別するロケーションから始
まるディスプレイメモリロケーションのシーケンス内へ
配置する。従ってそのサイトは最早、その後のダイナミ
ックパレットローディングコマンドのためには使用され
ず、ルーチンはＤＰＬポインタをそのコマンドシーケン
スの終りへ進め、そこで次のＤＰＬサイトに対するサー
チが開始される。ブロック１３８はこのステップを表わ
す。その後、同ルーチンはステップ１２８に進み、そこ
でそのパレットロケーションのアドレスをメインポイン
タが指定するディスプレイメモリロケーション内へ書込
む。前と同様に制御は図５のメインルーチンへ戻され
る。

【００７４】さて今度はステップ１３２へ戻る。ステッ
プ１３２のテストの否定的な結果は検査中のパレットロ
ケーションが識別されたＤＰＬサイトに続くディスプレ
イピクセルで使用するために既に選択されていることを
示す。従って、そのパレットロケーションの内容はその
選択されたＤＰＬサイトでは変更できないから、ルーチ
ンはステップ１４０へ進み、パレットメモリロケーショ
ンの全てが既に検査済みであるかどうかを判断する。

【００７５】既に検査済みであれば、ルーチンはブロッ
ク１４２が示すように、次のパレットメモリロケーショ
ンの最終使用エントリーへ移行し、ステップ１３２のテ
ストを繰返す。これはルーチンが識別されたＤＰＬサイ
トを越えてそれまで使用のために選択されなかったパレ
ットメモリロケーションを発見するまで続けられる。そ
の点でルーチンはステップ３４へ進み、前と同様に続行
する。

【００７６】然しながら、もしルーチンが識別されたＤ
ＰＬサイトのコマンドによって安全に変更可能なロケー
ションを発見することなくパレットメモリロケーション
を使い尽くしてしまう場合、テストステップ１４０の結
果は肯定的であり、ルーチンは識別されたＤＰＬサイト
を拒絶して更に画像中に探しつづける。殊に、ブロック
１４４が示すように、ルーチンはパレットメモリロケー
ションの全ての最終使用エントリー内を探索しつづけ、
最も早いものを発見し、ＤＰＬポインタを最も早い最終
使用エントリーによって示される最終使用のちょうど向
こう側の１ピクセルを識別する値に増分する。いいかえ
れば、ルーチンは最も近い時期に使用されたパレットメ
モリロケーションを識別し、パレットメモリロケーショ
ンの最後の使用の直後に開始すべきＤＰＬサイトの探索
を指示する。その後、再びステップ１２０においてＤＰ
Ｌサイトの探索が開始される。

【００７７】ステップ１２６に関して若干述べておく
と、同ステップではルーチンは、たといパレットエント
リーがステップ１０８の許容差内で所期値に近似しなく
ことも最も近いパレットエントリーを選択する。それは
さもなければ課される忠実度基準からの逸脱を表わすか
ら、ルーチンがこのステップに決して達することがない
ことが望ましいことは明らかである。

【００７８】ルーチンがこの手段に訴えなければならな
い事例の数は、通常、全体の忠実性要件を軽減すること
によって、即ち、ステップ１０２によって課される許容
差は緩和することによって減らすことができる。このた
めＤＰＬサイトが使用される割合は少なくなる。ステッ
プ１２６に訴えることも、同様にしてステップ１２０の
“同一”要件を緩和するか、画像を単色側境界で切り取
るかの何れかによってＤＰＬサイトの数を増加させるこ
とによって減らすことができる。しかし、画像はそれら
が必要とする色の数とそれらが提供するＤＰＬサイトの
数において異なり、一つの画像に必要となる忠実度の犠
牲は別の画像では不要にすることができる。ルーチンが
ステップ１２６へ訴える事例の数を減らし、しかも原始
画像に対する忠実度の全体的レベルをできるだけ高く維
持するためには、これまで述べたルーチンを洗練してそ
の許容差が適応される画像に応じて変化するようにする
ことができる。

【００７９】このことを行う一つの方法は、単にエンコ
ーダを運転してその結果の画像をユーザへ表示し、彼が
ステップ１０２、１２０、又はその両方によって課され
る許容差を調節できるようにするか、境界を付加してそ
れらの幅を調節し画像の主観的品質を最適にすることで
ある。しかしながら、必要とされる人間の介入量を少な
くするために、ルーチンパラメータを自動的に調節する
ための措置をとることができよう。

【００８０】例えば、今やステップ１２０−１２４にお
ける図６，７のパレットエントリー付与ルーチンの一部
であるＤＰＬサイトの探索をステップ１０６と１０８の
間の図５のメインループ内に挿入することもできよう。
このことは次に利用可能なＤＰＬサイトと現在検査中の
ピクセルとの間の距離の指示をステップ１０８の近似テ
ストにとっも利用可能なもきとすることになろう。その
場合、許容差はその距離に依然させることができよう。
許容差は大きな距離に対してはゼロで、距離が大きくな
るにつれて大きくなるようにすることができよう。この
距離値はまたステップ１２０において課されるＤＰＬサ
イト基準の厳格さを変更するために使用することもでき
よう。

【００８１】もちろん、これはその距離におけるＤＰＬ
サイトの数ではなく最初のＤＰＬサイトに対する距離の
みを考慮したものであるから最適許容差レベルを評価す
るための非常に大雑把なアプローチにすぎない。更に詳
細にするにはこの全体的アプローチを使用するが、それ
を若干修正することになろう。ステップ１２０、１２
２、１２４のループにより表わされる本テストにおい
て、ルーチンはＤＰＬサイトが発見された時にループを
退去する。一層の詳細化に従って、ルーチンはどこに最
初のＤＰＬサイトが位置するかを注目するが、その他の
ＤＰＬサイトを探索しつづけ、メインポインタによって
識別されるロケーションに達するまでそれらの総数を追
跡しつづけることになろう。その場合、許容差は最初の
利用可能なサイトと現在ピクセルのロケーション間の距
離にではなく中間のＤＰＬサイトの数に依存することに
なろう。

【００８２】前記アプローチの何れにも適当可能な更に
もう一つの詳細化は、未使用ＤＰＬサイトの全てではな
く、その内容が安全に変更可能なパレットメモリロケー
ションが利用可能であるようなＤＰＬサイトのみを考察
することである。即ち、ステップ１２０−１２４のみの
代わりに、ステップ１０６と１０８の間に挿入されるシ
ーケンスはステップ１２０−１２４、１３０、１３２、
および１４０−１４４となろう。自動的な側部−境界の
調節は境界の大きさを大きくし、ステップ１２４のテス
トの結果が否定的、即ち、ルーチンがＤＰＬサイトを消
した場合について開始することによって行うことができ
よう。

【００８３】我々はこれらの詳細化の結果性能が向上す
ると信ずるけれども、これまでは単純な図解アプローチ
のみを使用してきたにすぎない。上記のダイナミックパ
レットローディングルーチンの解説はこれまでミックス
としてコーディングするために採用されなかったソース
ワードをコーディングすることのみを取扱ってきたにす
ぎない。しかしながら、もしステップ１０６の結果が肯
定的であって現在ピクセルがミックスとしてコード化さ
るべきことを示すならば、ルーチンはステップ１４６へ
進み、そこで現在のピクセルに対して入力さるべきミッ
クス値を計算する。この計算は今や問題のピクセルがそ
の一部であるランの最終ワードに対して付与されたパレ
ット値に基づいている。ミックスランコーディングルー
チンはそのミックス値に先立ってラン中へ２つの「最
終」値を配置したことが想起されるであろう。従ってス
テップ１４６は最後の２つの非ミックスワードに付与さ
れるパレット値を取り出す。

【００８４】許容可能なミックスを計算するために多く
のアプローチが可能である。我々が使用する一つは、最
終値の赤、緑、および青の成分のそれぞれの間の差を計
算し、どの差が最大であるかを判断し、そのミックスを
最大差を生じた成分に従って計算するものである。例え
ば、最終値の赤成分どうしの間の差｜Ｘ_LR−Ｘ_RR｜がそ
れに対応する線と青の差よりも大きいと想定しよう。そ
の場合、そのソース非がＸ_Sである非のミックスは以下
の式で与えられる。

【００８５】３２（Ｘ_SR−Ｘ_LR）／（Ｘ_RR−Ｘ_LR）ステップ１４８において、このミックスのコードは現在
ピクセルのディスプレイメモリロケーション内へ入力さ
れ、ルーチンは次のピクセルへ進む。図５のメインルー
プが全てのピクセルを処理し終ると、コーディングプロ
セスは完了する。本発明の思想は例示したコードと相当
異なるミックスランコードを使用する方式にも適用でき
ることは明らかである。例示コードはそれぞれのランに
対して２つのピクセル特性値を使用し、特性値としてシ
ーケンスのソースピクセル値のうちの２つを使用し、そ
れら２つのソースピクセル値としてシーケンスの左右エ
ンドポイントワードによって表わされるものを選択して
いる。コーディングの観点からはランの特性値として全
てのラン中で同一の位置にそれらピクセル値を採用する
ことが効率的である。もしこのアプローチが採用されれ
ば、もしその所定位置がランのエンドポイントである場
合、画像の小さな領域における陰影は位置と共に大きく
なる傾向があるために最も長いランが得られる。従っ
て、 '６０５号特許に示すコードは、本発明の図解例が
そうするように、それらの特性値としてシーケンスエン
ドポイントの値を使用している。

【００８６】然しながら、これらの特徴の何れもミック
スランコードの必要条件ではない。先に述べたように、
例えば、上記コードは特性値をエンドポイントに限定し
ないコーディングプロセスと共に使用することができ
る。原理上必要なことは、ただコード化された画像が少
なくとも一ワードがそのピクセル値を少なくとも一部、
別のピクセルワードから取得しなければならないピクセ
ルワードの割合として指定するピクセルワードのランを
含むということでしかない。

【００８７】事実、その特性値が一つのシーケンス中の
ソースピクセルワードによって現わされるピクセル値の
全てと異なるようなミックスランコードを想い描くこと
ができよう。その場合、コードは３つもしくはそれ以上
の特性ピクセル値さえもミックスするか、あるいは“ミ
ックス”、即ち別のワードが表わす単一のピクセル値の
割合を使用することが可能である。これら全てはコード
化用のエラー基準を要し、例えば、シーケンスの長さが
大きくなるにつれてエター基準を軽減する手法から全て
利益を受けることになろう。従って、本発明は従来技術
から著しい進歩を表わすのものである。

【図面の簡単な説明】

【図１】本発明の思想を活用する画像表示システムのブ
ロック線図。

【図２】上記システムによって使用されイメージデータ
をピクセル・バイ・ピクセルのコードからミックスラン
コード形へ変換するための思想のフロー線図。

【図３】図２の続き。

【図４】ダイナミックパレットローディングコードを含
むミックスランコードピクセルワードの典型的シーケン
スのダイアグラム。

【図５】パレットメモリアドレスとダイナミックパレッ
トローディングコマンドをディスプレイメモリデータ内
へ組込むために上記システムが使用するルーチンのメイ
ンループのフロー線図。

【図６】図５のメインループが呼出すサブルーチンのフ
ロー線図。

【図７】図６の続き。

【符号の説明】

１４ソース１２エンコーダ１４ディスプレイメモリ３２タイミング回路３７ダイナミックパレットローダ３６アドレスパレットメモリ３８デコーダ

───────────────────────────────────────────────────── フロントページの続き (72)発明者ゲアリージェイフラッタローラアメリカ合衆国ニューハンプシャー州 03054 メリマックロンドンコート 28 (72)発明者ジョージエルヘロンアメリカ合衆国ニューハンプシャー州 03038 デリーコロニーブルックレーン 25

Claims

【特許請求の範囲】

【請求項１】ピクセル値をピクセル・バイ・ピクセル
方式で表現するソース信号によって表わされる画像を表
示する装置において、 A) それぞれの画像ピクセルに対応するスクリーン位置
を備えるスクリーンを有するディスプレイ機構で、それ
ぞれが一定画像中の各ピクセルに相当するランコードピ
クセルワードより成り一定のランコードに従ってピクセ
ル値を表わすことによって画像中の全ピクセルに対応す
るランコードピクセルワードの組がランコードピクセル
ワードの複数のランを備えるようにするランコードピク
セルワードを備え、各ランがその対応するピクセルのピ
クセル値をピクセル値の特性集合の値の集合としてその
値の全てを余分に含むことなく表示するようにし、スク
リーンシーケンス中のスクリーン位置を走査し、ラン中
のランコードピクセルワードが相当する画像ピクセルに
対応する走査されたスクリーン位置に、ランコードに従
ってランが表示するピクセル値のシーケンスを表示する
ためのものと、 B) それぞれのスクリーン位置とそのスクリーン位置が
対応するピクセルに対応するディスプレイメモリロケー
ションを含み、そのディスプレイメモリロケーション内
にランコードに従ってコード化されるピクセル値を格納
する対応するランコードピクセルワードをストアするよ
うに動作し、その対応するスクリーン位置の走査を追跡
するシーケンスで上記ディスプレイメモリロケーション
を走査し、その走査されたメモリロケーションの内容を
表示するディスプレイメモリ出力を生成し、同ディスプ
レイメモリ出力をそのディスプレイ入力としてディスプ
レイ機構へ付与するディスプレイメモリ回路と、 C) ソース信号を受け取るようになったエンコーダで、
それぞれが他のピクセルのピクセル値を参照することな
くその各々の画像ピクセルのピクセル値を表わすように
なった各画像ピクセルと関連するソースピクセルワード
を備え、ソースピクセルワードのシーケンスをランコー
ドに従ってランコードピクセルワードのランにコード化
し、ディスプレイメモリ回路を動作させてランコードピ
クセルワードをそれぞれのランコードピクセルワードが
対応する画像ピクセルに対応するディスプレイメモリロ
ケーション内へストアするものと、から成る前記装置。
【請求項２】エンコーダがシーケンスの長さによって
変化する所定最大エラー内の同一特性値を混合すること
によって近似可能な値を表わすソースピクセルワードの
シーケンスのみをランコードピクセルワードのラン内へ
コード化することによってソースピクセルワードをラン
コードピクセルワードへコード化する請求項１の装置。
【請求項３】最大エラーがシーケンスの長さと共に減
少する請求項２の装置。
【請求項４】上記所定の最大エラーが短いシーケンス
についてはパーセンテージエラーであって、長いシーケ
ンスについては絶対値エラーである請求項３の装置。
【請求項５】エンコーダが以下の如くして、ソースピ
クセルワードをランコードピクセルワードにコード化す
る請求項１の装置。 A) 少なくとも３つのソースピクセルワードのシーケン
スを候補シーケンスとして選択し、そのことによって上
記候補シーケンスが開始ワードと、最終ワードと、少な
くとも一つの中間ワードとより成り、 B) もし全ての中間ワードによって表現されるピクセル
値が候補シーケンスの開始ワードと最終ワードとによっ
て表現されるピクセル値のミックスによって所定の最大
エラー内に近似化可能であれば、その候補シーケンスを
許容可能なシーケンスとして受取り、新たなソースピク
セルワードをその候補シーケンスの最後に加え、このス
テップを次の候補シーケンスについて繰返し、 C) もし中間ピクセルワードによって表現されるピクセ
ル値が全て候補シーケンスの開始ワードと最終ワードに
よって表わされるピクセル値のミックスによって所定の
最大エラー内に近似化できるとは限らない場合、新たな
ソースピクセルを候補シーケンスの終りに付加し、もし
候補シーケンスが可能なピクセル値の存在を指示する所
定の基礎を満たさない場合には先のステップを繰返して
候補シーケンスの最終ワードと中間ワードによって表わ
されるピクセル値が全てその可能なピクセル値と候補シ
ーケンスの開始ワードによって表わされるピクセル値の
ミックスによって近似化できるようにし、もしそのよう
な可能なピクセル値が存在しない場合には、最後の許容
可能候補シーケンスを採用してそこからランコードラン
を生成する。
【請求項６】それから中間候補シーケンスピクセルワ
ードが概算可能な可能ピクセル値の存在の存在を示すも
のとしてエンコーダが使用する所定の基準が、候補シー
ケンスの他のピクセルワードが局部最大限ピクセルワー
ドと候補シーケンスの開始ワードによって表わされるピ
クセル値のミックスによって概算されるように局部最大
限ピクセルワードを含むものである請求項５の装置。
【請求項７】それから中間候補シーケンスピクセルワ
ードが概算可能な可能ピクセル値の存在を示すものとし
てエンコーダが使用する所定の基準が候補シーケンス内
のピクセルワードによって表わされるピクセル値の全て
がそれらピクセル値に適合する最良の最小２乗根を表わ
す線からの所定最大距離内にあることである請求項５の
装置。
【請求項８】それに従ってエンコーダがコード化しデ
ィスプレイ機構が表示するランコードによって各ランに
ついて使用されるピクセル値の特性集合が２つのピクセ
ル値より成る請求項１の装置。
【請求項９】エンコーダがソースピクセルワードのシ
ーケンスをランコードピクセルワードのランにコード化
する際に使用する２つの特性値がソースピクセルワード
のシーケンス中の最初と最後のピクセルワードによって
表現されるものと近似する値である請求項８の装置。
【請求項１０】エンコーダがソースピクセルワードの
シーケンスを第１のランコードピクセルワードが第１の
特性値を表わしラン中の第２のランコードピクセルワー
ドが第２の特性値を表現し、そのランの残りのランコー
ドピクセルワードがソースシーケンスの第３ないし最後
のソースピクセルワードによって表現されるピクセル値
と近似する特性値のミックスを表わすようなランコード
ピクセルワードのランへコード化する請求項９の装置。
【請求項１１】エンコーダがソースピクセルワードの
シーケンスを第１のランコードピクセルワードが第１の
特性値を表わし、ラン中の第２のランコードピクセルワ
ードが第２の特性値を表わし、ランの残るランコードピ
クセルワードがソースシーケンスの第３ないし最終ソー
スピクセルワードによって表わされるピクセル値に近似
する特性値のミックスを表わすようなランコードピクセ
ルワードのランにコード化される請求項８の装置。
【請求項１２】エンコーダがソースピクセルワードの
各シーケンスを、ラン中の第１ランコードピクセルワー
ドがシーケンス中の第１のソースピクセルワードによっ
て表現されるピクセル値に近似するピクセル値を表わす
ようなランコードピクセルワードのランにコード化する
請求項１１の装置。
【請求項１３】ディスプレイ機構が、各ランについ
て、第１と第２の表示ピクセル値がラン中の最初のピク
セルワードによって表現される値であって、残りのディ
スプレイピクセル値の各々が対応するランコードピクセ
ルワードが表わすミックス値に従ってラン中の最初の２
つのピクセル値によって表わされるピクセル値をミック
スすることによって得られる値であるような表示ピクセ
ル値のシーケンスを表示する請求項８の装置。