JPH08101903A

JPH08101903A - イメージ・メモリをコード化する方法

Info

Publication number: JPH08101903A
Application number: JP7210846A
Authority: JP
Inventors: Eric Filliatre; エリツク・フイリアートル; Olivier Pernia; オリビエ・ペルニア
Original assignee: Thales Avionics SAS
Current assignee: Thales Avionics SAS
Priority date: 1994-08-19
Filing date: 1995-08-18
Publication date: 1996-04-16
Also published as: US5790128A; FR2723797A1; EP0697678A1; FR2723797B1

Abstract

(57)【要約】【課題】画面のイメージをリフレッシュするためのメ
モリの描画時間及びプロッティング時間を低減する。【解決手段】イメージは、一様な色を有し輪郭によっ
て区画される表面を備え、輪郭が中線と、中線の画素の
すぐ近くにある画素を中線の両側に備える中線の近傍と
を備え、イメージがさらに、フィラー・プロット済みフ
ィーチャを含み、画面の１つの画素が、ワードを含むメ
モリ・セルと１対１で対応し、現セルの読取りが、対応
する画素を画面上に書き込むために必要な情報の少なく
とも一部を構成し、輪郭に関して再コード化されたメモ
リ・ワードが、輪郭の中線に関係するメモリ・ワードだ
けでなく、各輪郭の近傍に関係するメモリ・ワードも含
み、再コード化された各メモリ・ワードのコードが、再
コード化ビットの書込みの環境を識別する２つの情報ビ
ットを備える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、画面、たとえば画
面の各画素がそのアドレスおよび光度によって定義され
るマトリックス構造画面上のイメージをリフレッシュす
るために使用されるメモリのリアルタイム書込みおよび
読取り用のコード化方法に関する。

【０００２】

【従来の技術及び発明が解決しようとする課題】書込み
機能および読取り機能を実行する公知の装置では、メモ
リは、画面が有する画素と少なくとも同数のセルを有す
る。このメモリの構造は、画面の構造を反映するもので
あり、メモリの基本セルと画面の画素の間に直接的な対
応付けを確立することができる。メモリのセルは、画面
の画素を定義できるようにする情報要素を有する。

【０００３】画面のイメージを更新できるようにする、
たとえば毎秒５０イメージの速度でのメモリの規則的な
読取りでは特定の問題は発生しない。しかし、メモリへ
の書込みと、メモリに含まれている情報要素の更新は、
表現すべきイメージの複雑度に関係する継続時間を有す
る。イメージ・リフレッシング周期に制限された期間内
にこの継続時間を含めることは困難である。具体的に
は、表面の描画またはプロッティングは、図面またはプ
ロッティングを作成するのに必要な時間に大きな影響を
及ぼす。

【０００４】以下では、従来の技術と本発明の両方に関
して、画面のイメージが、それぞれ、表面の外部と内部
を区画する輪郭を有しており、背景上に見える１組の表
面によって定義することができると仮定する。表面は、
フィラー要素を含むこともできる。これは、局所横次元
が少数の画素に限られるｌｏｎｇｉｌｉｎｅａｒ表面で
ある。

【０００５】上述の基準を満たす簡単なイメージを有す
るそのような画面を図１に示す。このイメージは、背景
１を有し、背景上には、２つの表面２および３ならびに
１つのフィラー要素４が見える。表面２および３は、そ
れぞれの輪郭５および６によって区画される。

【０００６】そのようなイメージは、簡単な形の人工水
平線（ａｒｔｉｆｉｃｉａｌｈｏｒｉｚｏｎ）の表示
に対応する。人工水平線が取り付けられた航空機の操縦
の機能として、表面３は地球を表し、表面２は空を表
し、２つの表面の間のフィラー要素４は水平線を表す。
この簡単なケースでは、表面２および３ならびにそのそ
れぞれの輪郭５および６が存在するが、その形状および
表面は変化する。本発明に関する一般的な例でも、同じ
ことが当てはまる。少なくとも局所には、たとえば画面
の水平帯域上には、それぞれ、輪郭が割り当てられた固
定数の表面がある。表面は、場合によっては、一時的に
ゼロであることがある。イメージは、フィラー・プロッ
ト済みフィーチャを任意の位置に含むこともできる。こ
のフィラー・プロット済みフィーチャは、たとえば、ぼ
かし、または英数字の記録、またはシルエットに対応す
る。

【０００７】プロット済みフィーチャまたは図面でメモ
リのセルを塗りつぶすために使用されている知られてい
る方法のうちで、第１の手法は、描画すべき表面外部の
エンベロープを走査することから成る。表面２に関する
そのような外部エンベロープは、点線で示したような輪
郭７によって示されている。次いで、全体として表面２
の輪郭６を規定する画素上にあるセルを塗りつぶす。次
いで、メモリの走査を輪郭７内の表面に制限する。たと
えば、輪郭７によって制限された水平走査である、この
走査時には、走査されるセルの以前の読取りを使用し
て、輪郭７の交差と輪郭７内部にある各セル内の交差を
識別し、表面２用に選択した光度、色、またはグレー・
レベルを記録する。この種の技法では、表面２の輪郭６
は一般に、半輪郭として細分される。これは、凸輪郭形
状に関してのみ有効である。この点は、簡単な形状を有
する表面では検証されることが多い。水平走査の場合、
左側半輪郭および右側半輪郭が検討される。これらの輪
郭は、メモリ・イメージには記録されず、一般に、マス
ク・メモリと呼ばれる追加メモリに記録される。この機
構によって、輪郭のずっと簡単な管理が可能になり、イ
メージ・メモリの内容との矛盾が防止される。

【０００８】そのような方法は、各表面描画時間または
プロッティング時間を、各表面ごとに、輪郭６にできる
だけ近いものとして選択された簡単な輪郭である輪郭７
内に位置する表面を走査するのに必要な時間に制限する
ために使用される。走査ゾーンを区画する輪郭７は、輪
郭６を記録できる最も小さな矩形であることが多い。し
かし、表面２を作成するために使用される時間は、表面
２に対して線形に増加する。

【０００９】知られている第２の手法は、カタログ化さ
れた異なる各表面に追加イメージ・メモリを使用するこ
とから成る。このメモリは、１ビット上で値０または１
でコード化される。このメモリは１つの値を有し、たと
えば表面外部または内部の位置では値が０であり、表面
の輪郭を交差する画素では値が１である。イメージ・メ
モリおよび追加メモリは並行に再読み取りされる。各表
面に関連するイメージ・メモリおよび追加メモリの一実
施例は、図２に示した形状をとる。図２は、図１に示し
たようなイメージの更新に使用されるイメージ・メモリ
の一部を示す。このメモリの各セル８は、画素の色を定
義するために使用される情報要素を、たとえば８ビット
上に含むことができる。セル８のメモリ・ワードの可能
な表示を図３に示す。ワードは１６ビットから成ると仮
定した。最上位８ビットはたとえば光度を表す。最下位
８ビットは、表面の交差を示すために使用することがで
きる。したがって、表面の８つの異なる輪郭に作用する
ことが可能である。この規約では、表面３の輪郭を定義
する画素は、たとえば右からビットを数えたときのビッ
ト３が１であることによって定義される。したがって、
各輪郭およびその色が完全に定義される。

【００１０】画面のイメージを描画またはプロットする
ためにメモリを走査している間、表面３の輪郭の交差
は、３番目のビットの値が１であることを検出すること
によって検出される。この場合、現ラインを走査するた
めに、この画素から始まって、ビット３の値として値１
が検索されるまで、表面３に割り当てられた色の表示が
活動化されていく。これは、表面３が残されることを示
す。

【００１１】この手順によって、特に問題を起こすこと
なく輪郭の交差を処理することができる。しかし、この
手順では、凹形状と凸形状を交互に有する複雑な輪郭を
処理することはできず、表面の外部と内部の間の混乱が
発生する。そのような方法では、表面を描画するのにか
かる時間をかなり低減させることによってハイレベルの
性能が得られることが分かる。これに対して、イメージ
・メモリの再読取り時に複雑な形状の表面の外部と内部
の間の混乱が発生することがある。さらに、輪郭交差の
２進記録向けに計画する必要がある追加メモリの容量
は、表面の数に対して線形に増加する。これによってじ
きに、禁止的なコスト要件および空間要件が発生する。

【００１２】次いで、図３に示した例では、コード化が
最上位８ビット向けに設定された色が、当該の表面に関
して記録されないことが分かる（この観測は、以下で説
明する本発明の基礎である）。このように色が記録され
ないため、描画時間またはプロッティング時間を増加さ
せることができる。色は、画面のイメージをリフレッシ
ュするためのメモリ読取り時に、読取りプロセッサによ
って与えられる。このプロセッサは、右から３番目のビ
ットの値が１であることによって検出された１つの輪
郭、たとえば輪郭３の第１の交差と、輪郭３内部の色と
の関連付けをセットアップする。プロセッサは、同じよ
うに検出されたこの輪郭の第２の交差でこの関連付けを
停止する。最上位８ビット上に色が示されるのは、常
に、表面ではなく意味の主要な部分を表す、フィラー・
プロット済みフィーチャの場合だけである。その結果、
メモリの主要な部分が使用される。メモリのこの部分
は、フィラー・プロット済みフィーチャ以外には使用さ
れない。

【００１３】本発明の第１の目的は、画面のイメージを
リフレッシュするためのメモリの描画時間またはプロッ
ティング時間を低減させることであり、第２の目的は、
１つの同じ描画品質またはプロッティング品質のために
メモリのサイズを低減させることである。

【００１４】好ましい実施例の目的は、効率的なフィラ
ー・プロット済みフィーチャを得て、一方では輪郭交差
を、他方では複雑な表面を効率的に処理することであ
る。他の目的は、異なる表面間の遷移、あるいは表面と
背景の間の遷移、および表面とフィラー要素の間の遷移
に効率的なアンチエリアシング（ａｎｔｉ−ａｌｉａｓ
ｉｎｇ）を施すことである。

【００１５】

【課題を解決するための手段】これらの目的のために、
本発明は、上述の第２の従来技術の手法と同様に、フィ
ラー・プロット済みフィーチャに対応する色が、プロッ
ティングのメモリに記録され読み込まれる方法を使用す
る。表面の場合、従来技術と同様に、メモリにプロット
されるのは表面の輪郭だけである。従来技術の場合と同
様に、各輪郭には、各フィラー・プロット済みフィーチ
ャと同様に優先順位が与えられる。まず、輪郭が優先順
位の昇順でプロットされ、次いで、フィラー・プロット
済みフィーチャが、やはり優先順位の昇順でプロットさ
れる。このプロッティング順によって、１つの同じ画素
を通過する２つ以上のプロット済みフィーチャが重なっ
た場合、前記フィーチャに含まれるこの画素用の情報要
素を、最も重要な情報要素で置換することができる。

【００１６】しかし、本発明によれば、各メモリ・ワー
ドごとに、２ビットが使用される。この２ビットを以下
では、ケース識別ビットと呼ぶ。この２ビットは、値の
４つの組合せのセットアップに使用できる。本願発明者
は、４つのケースのプロット済みフィーチャがあること
を発見した。これらのケースのうちの３つでは、メモリ
に与えられる情報要素の性質は相互に異なる。第４のケ
ースの場合、情報要素は、他の３つのケースのうちの１
つと同じであるが、以下でさらに判明するように、この
第４のケースのコードによって、演算が、すでに処理さ
れた輪郭交差ゾーンで行われているかどうかを確認する
ことができる。したがって、誤って解釈される恐れがあ
るために再処理は許容されない。プロッティングのケー
スを定義する２ビットは、メモリまたは読取りプロセッ
サ内部のメモリ中の、現画素を読み取らなければならな
いのか、それとも色情報要素の後に続く画素を読み取ら
なければならないのかを知るために、メモリの読取りプ
ロセッサによって使用される。

【００１７】次に、識別ビットによって識別される４つ
のケースについて説明する。

【００１８】当該の輪郭プロッティングが、交差を有さ
ない表面の輪郭プロッティングを含む場合、メモリへの
書込みでたとえばコード０１が使用される。ケースの識
別コード用に留保されたメモリ・セル中の位置でこのコ
ードに出会ったときにはいつでも、輪郭ピクセル、また
は輪郭の近傍であるピクセルで演算が行われており、こ
の位置にある輪郭が、他の輪郭との交差もフィラー要素
との交差も有さないことが分る。したがってたとえば、
第１のプロット済み輪郭のすべての画素は識別コード０
１である。第２のプロット済み輪郭が、第１のプロット
済み輪郭との交差点を有さない場合、この２つの輪郭の
それぞれの画素およびその近傍に対応するメモリ・セル
は、識別コード０１を維持する。

【００１９】ｉ次の輪郭がｊ次の輪郭に交差している場
合（ｊ≦ｉ）、２つの輪郭ｉおよびｊに共通のピクセル
およびピクセルの近傍があることを意味する。このこと
は、メモリ・セルが一杯になる前の輪郭のプロッティン
グ時に、このメモリ・セルの読取りが規則正しく実行さ
れるために検出される。この段階で、従来技術と同様
に、メモリの読取りが終了するたびに、イメージ・メモ
リが０にリセットされることを想起されたい。したがっ
て、メモリが空白になるたびにプロッティングが開始さ
れる。異なる輪郭のプロッティングを連続的に実行し、
最高優先順位を有する輪郭プロッティングを最後に実行
することも指定される。フィラー・プロット済みフィー
チャは、輪郭のプロッティングの後に優先順位の昇順に
よって同様に作成され、最高優先順位を有するフィラー
・プロット済みフィーチャが最後に作成される。

【００２０】輪郭ｉのプロッティング時に、すでにロー
ドされているメモリ・セルが検出された場合、現スキャ
ンライン上のセルと、すでにロードされているこのセル
の近傍のライン上のセルの読取りが活動化される。これ
によって、すでに輪郭ｊを表すために使用されている画
素をこの近傍で検出することができる。この近傍のすべ
てのメモリ・セルにコード１０が割り当てられる。輪郭
ｊよりも輪郭ｉが優先されるので、輪郭ｉの定義でも輪
郭ｊの定義でもある役割を果たすメモリ・セルに含まれ
る情報要素は、輪郭ｉ上の情報要素で置換される。この
情報要素を新しい情報要素で上書きすると同時に、識別
コードが０にリセットされる。輪郭ｊの中線の定義であ
る役割を果たすメモリ・セルでは、輪郭ｊが交差された
ことを読取りが示す場合、この目的専用のメモリ・セル
のビット上に、たとえばビット値１が記録される。した
がって、コードが０のままであるメモリ・セルは、プロ
ッティングｉ時に再読取りされたが、情報要素が変更さ
れなかったメモリ・セルである。このセルが新しい輪郭
上のセルであり、あるいはその後にプロットされた新し
いフィラー・フィーチャ上のセルである場合、コード１
０は、光度値の局所シーケンスがすでに処理され、場合
によっては、その後のプロッティングによって上書きさ
れていることを示す。したがって、この情報要素はもは
や、一貫性のある全体を構成せず、誤って解釈される恐
れがあるためにこの情報要素の再処理は許可されない。
言い換えると、輪郭ｊのプロッティング時に記録された
輪郭の交差に関する順次情報はもはや、このような画素
として統合されることはなく、もはや復号してはならな
い。

【００２１】フィラー要素に属することを示すケース識
別コードは００および１１である。

【００２２】コード００は、この値の識別コードを有す
るメモリ・セルに対応する画素が表面上または背景上に
しか存在しないことを示す。メモリの読取り時にこのコ
ードが検出されると、ある色の表面への自動割当て順序
に割込みが発生し、この色が、このために割り当てられ
たメモリ・セル中のビット上に値が読み取られる色で置
換される。

【００２３】コード１１は、この値を有する識別コード
を有するメモリ・セルに対応する画素が輪郭上にあるこ
とを示す。このケースは、書込みを行う前にメモリを規
則正しく読み取ることによって検出される。このケース
では、手順は、前述の２つの輪郭の交差の場合と同じで
ある。メモリ・セルの一部は、輪郭交差情報を書き込む
ためのものとして再割り当てされる。これを実行するう
えで、通常色の記録に使用されるメモリの部分は、フィ
ラー・プロット済みフィーチャの識別コード用に占有さ
れる。この場合に限り、メモリ中の利用可能な空間が小
さいために、色はダウングレード・モードで、すなわち
より少ない数のビット上に記録される。本願出願人が実
施した試験では、これによって画質に影響が及ぶことは
ないことが分かった。

【００２４】要するに、本発明は、画面上に１組の画素
で形成されたイメージをリフレッシュするために周期的
に読み取るように構成されたイメージ・メモリのワード
をコード化する方法において、イメージが、イメージの
背景上に見える表面Ｓ₁，．．．，Ｓ₂，．．．，Ｓ_p
を備え、これらの表面がそれぞれ、一様な色を有し、輪
郭Ｃ₁，．．．，Ｃ₂，．．．，Ｃ_pによって区画さ
れ、輪郭がそれぞれ、少なくとも２つの表面の境界また
は表面と背景の境界に位置する画素を連結する中線と、
少なくとも、中線の画素のすぐ近くにある画素を、中線
の両側に備える中線の近傍とを備え、イメージがさら
に、フィラー・プロット済みフィーチャを含み、画面の
１つの画素が、ワードを含むことができるメモリ・セル
に１対１で対応し、現セルの読取りが、対応する画素を
画面上に書き込むために必要な情報の少なくとも一部を
構成し、各読取り後にイメージ・メモリが消去され、第
１の優先順位が輪郭に割り当てられ、第２の優先順位が
フィラー・プロット済みフィーチャに割り当てられ、最
初に輪郭が記録され、次いでフィラー・プロット済みフ
ィーチャが、このような各プロット済みフィーチャ・タ
イプごとに優先順位の昇順で記録され、最高優先順位を
有するプロット済みフィーチャが最後に記録され、輪郭
に関して再コード化されたメモリ・ワードが、輪郭の中
線に関係するメモリ・ワードだけでなく、各輪郭の近傍
に関係するメモリ・ワードも含み、再コード化された各
メモリ・ワードのコードが、再コード化ビットの書込み
の環境を識別する２つの情報ビットを備える方法に関す
るものである。この２つのビットにより、異なる可能な
値の組合せによって、以下の４つのケースを識別するこ
とができる。

【００２５】− ２ビットの値の第１の組合せによって
識別される第１のケースは、示された画素に関して、前
に書き込まれた輪郭のプロッティング上にないフィラー
・プロット済みフィーチャを識別する。

【００２６】− ２ビットの値の第２の組合せによって
識別される第２のケースは、示された画素に関して、他
の輪郭のプロッティング上にない輪郭プロッティングを
識別する。

【００２７】− ２ビットの値の第３の組合せによって
識別される第３のケースは、示された画素に関して、前
の輪郭の近傍にある輪郭プロッティングを識別する。

【００２８】− ２ビットの値の第４の組合せによって
識別される第４のケースは、示された画素に関して、前
にプロットされた輪郭に共通のフィラー・プロッティン
グを識別する。

【００２９】本発明は、以下の説明および添付の図面か
ら、よりよく理解され、また本発明の他の特徴も明らか
になろう。

【００３０】

【発明の実施の形態】図１ないし図３は、従来技術に関
して既に説明しており、したがってここでは説明しな
い。

【００３１】本発明の好ましい実施例では、２つの表面
間の遷移または表面とフィラー・プロッティングの間の
遷移にマーク付けするように設定されたビット群は、上
述の最初の３つの組合せに関するケースにも使用され
る。この変数の表すもの、この変数がとる相対値、この
変数の使用法について説明する前に、イメージ・メモリ
のメモリ・ワードが、画面が走査される順序で読み取ら
れることを想起しなければならない。したがって、最も
一般的なケースでは、走査はラインごとの走査、たとえ
ば水平走査であり、メモリ・ワードはラインごとに、た
とえば左から右へ読み取られる。上記ではさらに輪郭の
概念を導入した。この概念は、厳密に言えば、２つの表
面間の分離線を表す中線だけでなく、中線の両側に位置
する近傍ゾーンも含む。次に、この近傍の概念を指定す
る。しかしまず、いくつかの点を想起する必要がある。
画面上に示すべきイメージはたとえば、記号ジェネレー
タによって与えられる。このジェネレータは、各輪郭の
座標を点ごとに算出する。これらの点を平滑な線として
連結したものが真の輪郭である。このように算出された
点は必ずしも、画面の画素の中心に対応するわけではな
い。真の輪郭の各点ごとに、この点での輪郭の接線と、
この点での輪郭の法線を定義することができる。この真
の輪郭に関しては、輪郭の近傍は、厳密に言えば、常に
真の輪郭の法線上にある固定長セグメントをシフトする
ことによって生成される表面で形成される。真の輪郭の
接線は、このセグメントのｍｅｄｉａｔｒｉｘである。
画面上で、イメージを作成するのに利用できる唯一の点
は画素である。一般に、輪郭の法線に沿って整列する画
素はない。画面上の近傍は、最も一般的な形では、２本
のラインの間の表面として定義される。第１のライン
は、ｍｅｄｉａｔｒｉｘとして接線を有するセグメント
の一端の点に最も近い画素を連結するラインであり、第
２のラインは、このセグメントの他端に最も近い画素を
連結するラインである。画素の読取り順序を決定する画
面スキャンラインは、輪郭の局所的な割線でも、輪郭の
局所的な接線でもよい。スキャンラインが輪郭の割線で
ある場合、２つのケースを区別することができる。第１
のケースでは、まず輪郭の外側の画素が走査され、輪郭
の画素が走査され、次いで輪郭内の画素が走査される。
第２のケースでは、まず輪郭内の画素が走査され、輪郭
の画素が走査され、次いで輪郭の外側の画素が走査され
る。

【００３２】遷移の変数は、表面の外側の近傍の画素の
場合はより低い値Ｇ_minを有し、表面の内側の近傍の画
素の場合はより高い値Ｇ_maxを有する。中線の画素の場
合、遷移変数は、Ｇ_minの最大値とＧ_maxの最小値の間
の中間値Ｇ₀を有する。

【００３３】その結果、メモリ・ワードごとに画面の画
素に対応するメモリの走査が、輪郭の割線に沿って行わ
れる場合、走査が輪郭の外側から内側へ行われる場合は
シーケンスＧ_minＧ₀Ｇ_maxに出会う。言い換えると、
これは、Ｇの増加する値のシーケンスである。そうでな
い場合、すなわち走査順序の方向が表面の内側から外側
へ向かう方向である場合、シーケンスは、減少する値の
シーケンスになる。

【００３４】したがって、遷移の大きさの値を順序付け
ることによって、表面への入口または表面からの出口が
あるかどうかをイメージ・メモリ読取りプロセッサに通
知することができる。Ｇ_minＧ₀Ｇ_maxなどのシーケン
スが、輪郭をグレーズするスキャンラインを示すことに
も留意されたい。

【００３５】以下で、好ましい実施例では、中間値Ｇ₀
が内部画素の色と外部ピクセルの色の比色の係数を示す
ことができ、そのため階調度を構成し、したがって表面
を平滑化することができることが判明する。

【００３６】後述の好ましい実施例で、本発明による方
法は、図４に示したようなイメージ・メモリのメモリ・
ワードをコード化するように用いられる。図４に示した
装置は、記号ジェネレータ９を有する。グラフィック・
プロセッサは、書込みリンク１１によってイメージ・メ
モリ１０に供給すべきディジタル形の信号を生成する。
この同じプロセッサは、メモリ・プロセッサ・リンク１
２によってイメージ・メモリ１０を読み取るためにも使
用される。このメモリから抽出されるデータ要素は、プ
ロセッサで処理され補足される。プロセッサは、このデ
ータ要素をリンク１３によってマトリックス画面１４に
供給する。メモリ１０は、一方のページ上でプロッティ
ングを作成し、同時に他方を使用して画面をリフレッシ
ュするように、本質的に知られている方法で交互に使用
される２つのページを有する。

【００３７】記号ジェネレータ９はまず、以下のディジ
タル情報の形で点の流れを生成する。

【００３８】− 一対の座標Ｘ、Ｙ − プロット済みフィーチャの接線と画面の局所スキャ
ンラインの間の角度。実施例の場合、画面の走査は標準
的にラインごとに行われ、ラインは軸ベクトルＸに平行
である。

【００３９】− ３つ組・赤緑青（ＲＧＢ）の形の
色第２段階で、プロセッサは、画素の中心の位置とは独立
の座標Ｘ_i、Ｙ_iを有する各点Ｔ_iを、画素の中心の位
置で発生する点Ｐ_iで置換する。

【００４０】点Ｐ_iを求める場合、プロット済みフィー
チャの接線に角度的に最も近い画面の一方の座標軸に平
行な軸をベクトルＴと呼ぶ。したがって、プロット済み
フィーチャの接線が水平軸ベクトルＸと４５°以下の角
度を形成する場合、軸ベクトルＴはベクトルＸ点の軸に
平行である。そうでない場合、軸ベクトルＴは軸ベクト
ルＹに平行である。同様に、プロット済みフィーチャの
法線に角度的に最も近い軸ベクトルＸまたはベクトルＹ
をベクトルＮと呼ぶ。

【００４１】図５は、輪郭Ｃ₁のプロッティングの２つ
の点Ｔ₁およびＴ₂に関して説明したことを示す。点Ｔ
₁の場合、プロット済みフィーチャの接線は、４５°よ
りも大きな水平に対する角度θ₁を形成する。この場
合、軸Ｎ₁は、水平軸ベクトルＸに平行な軸である。点
Ｔ₂では、逆になり、法線Ｎ₂は、Ｔ₂の場合、垂直軸
Ｙに平行である。画素の中心は、格子を形成する垂直ラ
インと水平ラインの交差にある。この格子は、Ｔ₁およ
びＴ₂の近傍にしか示されていない。

【００４２】任意の点Ｔ_iの場合、対応する点Ｐ_iは、
この実施例によれば、点Ｔ_iに最も近い軸Ｎ_iに平行な
画素の中心の線上にあり、この線上で点Ｔ_iでの接線ｔ
_iに最も近いのは画素Ｐ_iである。したがって、図５に
示した点Ｔ₁およびＴ₂の場合、Ｔ₁の外挿された点
は、Ｔ₁に最も近く、この場合は水平な、Ｎ₁に平行な
画素の線上にある点Ｐ₁である。第２に、Ｐ₁は、この
画素の線上で、輪郭Ｃ₁の点Ｔ₁での接線ｔ₁に最も近
い画素である。同様に、Ｔ₂の外挿された点は、Ｔ₂に
最も近く、この場合は垂直な、Ｎ₂に平行な画素の線上
にある点Ｐ₂であり、この線上で、画素Ｐ₂は、輪郭Ｃ
₁の点Ｐ₂での接線ｔ₂に最も近い。

【００４３】上記でさらに、好ましい実施例によれば、
表面輪郭用の遷移係数Ｇが導入され、フィラー・プロッ
ト済みフィーチャが輪郭に重ならないことが判明してい
る。輪郭交差画素でのこの係数の値は、記号ジェネレー
タの出力での対応する点Ｔ_iに対するこの点Ｐ_iの中心
の位置の関数である。

【００４４】値Ｇ_minおよびＧ_maxに関してＧ₀を求め
る典型的な方法を、図６および図７に関して与える。

【００４５】図６は、図５の拡大詳細を示す。これは、
点Ｔ₁およびそれに対応する点Ｐ₁が現れる詳細であ
る。図６で、画面の画素の中心は、等間隔で配置された
水平ラインおよび垂直ラインの交差点にある。画素の表
面は、点線の正方形の形で輪郭によって示されている。
図５の説明で、点Ｔ₁およびその接線ｔ₁では、方向Ｎ
が水平ラインによって形成されることが分かった。点Ｐ
₁は、それ自体が、Ｔ₁に最も近いラインＮと輪郭Ｃ₁
の点Ｔ₁での接線ｔ₁との交差点である、点Ｔ’₁に最
も近い画素の中心である。この実施例では、Ｐ₁の近傍
に位置する点は、Ｐ₁に最も近い点Ｐ₁のラインＮ₁上
でこの点のいずれかの側にある点Ｖ₃、Ｖ₄および
Ｖ₁、Ｖ₂によって形成される。

【００４６】たとえば、輪郭の外側にある点Ｖ₁、Ｖ₂
には遷移係数Ｇ_minが割り当てられ、内側にある点
Ｖ₃、Ｖ₄には遷移係数Ｇ_maxが割り当てられる。輪郭
上にある点Ｐ₁には、Ｇ_minとＧ_maxの間の中間値であ
る係数が割り当てられる。

【００４７】図７は、Ｇ₀の値を求める方法を示す例で
ある。この図は、値Ｇ_minおよびＧ_maxがｙ軸上に表さ
れ、点Ｖ₁、Ｖ₂、Ｔ’₁、Ｐ₁、Ｖ₃、Ｖ₄の間隔が
ｘ軸上に示されたグラフである。ｙ軸の点Ｖ₂、
Ｇ_min、Ｖ₃、Ｇ_maxを連結するセグメントＡＢ上で、
Ｇ₀の値は、ｘ軸の点Ｔ’₁のｙ軸の値である。

【００４８】もちろん、点Ａと点Ｂを連結する他の曲線
を選択し、したがって輪郭の実際の形状を考慮に入れる
ことが可能である。一般に、ガウス曲線が選択される。

【００４９】輪郭の各連続点に関連する遷移変数の値
は、プロッティングの作成に割り当てられた、イメージ
・メモリ中のページに徐々に記録される。このページ
は、最初の書込み動作の前に全体的に０に初期設定され
る。これらの値の連続書込みにより、輪郭の形状に応じ
て、イメージ・メモリ中で値Ｇが重なることがある。し
たがって、これらの値の生成の一貫性を保証し、特にあ
らゆるケースで最終値が同じになるようにする必要があ
る。このため、各画素アドレスごとに、最終的にイメー
ジ・メモリに記録される値は、遷移の最も新しい変数の
値Ｇ₀と輪郭のプロッティングの前の段階で記録された
値Ｇ_rを共に考慮に入れたものである。この値は、あら
ゆる書込み動作の前に規則正しい読取りを実行すること
によって得られ、前の記録を検出するように設定され
る。

【００５０】いくつかの簡単な規則が、イメージ・メモ
リに記録される最終値の計算を支配する。この計算で
は、追加情報要素が必要である。この表面の内側は、輪
郭の湾曲に対して位置決めされる。湾曲の中心が表面内
に位置する場合、輪郭は凹と呼ばれる。そうでない場合
は凸と呼ばれる。この語に関しては以下のとおりであ
る。

【００５１】− 凹輪郭では、最終的に記録される値Ｇ
_fは、２つの値Ｇ₀およびＧ_rのうちの小さい方であ
る。

【００５２】− 凸輪郭では、この２つの値のうちの大
きい方である。

【００５３】図８および図９は、２つの部分に関して説
明したことを示すものであり、一方は凹輪郭を示し（図
８）、他方は凸輪郭を示す（図９）。

【００５４】これらの図は、画面の画素の一部と、対応
するメモリ・セル中のたとえば３ビット（０ないし７）
上に記録された値を示す。これらのセルの位置を指定で
きるようにするために、列にａないしｊの参照符号を付
け、ラインに１ないし１０の参照符号を付けた。

【００５５】図（図８および図９）の輪郭は同じもので
ある。この輪郭で囲まれた表面の位置だけが異なる。図
８および図９の左に位置する図８₁および図９₁はそれ
ぞれ、輪郭の第１の部分を示す。中央に位置する図８₂
および図９₂は、輪郭の第２の部分を示す。これらの部
分のそれぞれでは、輪郭の法線に最も近い画素の行は水
平である。その結果、輪郭の中線に属する各画素ごと
に、中線の右に２つおよび中線の左に２つの同じ線の４
つの画素によって、輪郭の近傍を形成する近傍画素が形
成される。中線の画素を識別するために、これらの画素
に対応するメモリ・スロットに記録された値Ｇ₀を丸で
囲んである。輪郭のプロッティングが、図８₁または図
９₁に示したプロッティングで始まり、次いで、図８₂
または図９₂に示したプロッティングによって拡張され
たと仮定する場合、たとえば、プロット済みフィーチャ
の２つの部分に線８の４つの画素（ｄ８ないしｇ８）が
共通していることが分かる。

【００５６】画素ｄ８ないしｇ８用にすでに記録されて
いる値は、図８₁または図９₁のセルｄ８ないしｇ８に
示されている。図（第８₂または９₂）の輪郭の第２の
部分用に記録する必要がある値は、図８₂のこれらの同
じセルｄ８ないしｇ８に示されている。この第２の部分
のプロッティング時に、輪郭のこの第２の部分の輪郭に
属するセルを規則正しく読み取ることによって、セルｄ
８ないしｇ８への以前の書込みの存在が検出される。図
８に示した凹輪郭の場合、最終値Ｇ_fは、２つの値のう
ちの小さい方、すなわち図８₂に示した計算値のＧ_cま
たは図８₁に示した再読取り値のＧ_rになる。

【００５７】Ｇ_f＝ｍｉｎ（Ｇ_c，Ｇ_r）（１）これによって、たとえばセルｄ８に、輪郭の第２の部分
のこの同じセルに関して算出された値７よりも小さな、
このスロットに関して図８₁で示した値０がロードされ
た、図８₃に示した最終プロッティングがもたらされ
る。

【００５８】凸輪郭の場合、最終的に記録される値Ｇ_f
は、値Ｇ_cまたはＧ_rの最大値である。これによってた
とえば、セルｄ８では、セルｄ８に関して図９₂で示し
たプロッティングの第２の部分の結果として得られる値
０よりも大きな、図９₁の値Ｇ_f＝７（図９₃）がもた
らされる。

【００５９】この輪郭が凹と凸、またはその逆を交互に
形成するものであるとき、湾曲に関する情報の変更は、
湾曲が取り消されるゾーンで行われる。

【００６０】画面上での表示のためのイメージ・メモリ
の再読取り時に、以下のように輪郭の再検出が行われ
る。

【００６１】− メモリの各ラインが左から右に再読取
りされる。

【００６２】− 輪郭内に位置する表面の自動塗りつぶ
しに関する情報が、各ラインの始めごとに非活動状態に
再初期設定される。

【００６３】− 上昇する各Ｇタイプ・シーケンスは、
輪郭が、読み取られた輪郭である、表面への入口を示
す。このシーケンスの右に位置するラインの部分の、こ
の輪郭によって囲まれた表面に予想される色による自動
塗りつぶしがトリガされる。

【００６４】− 下降する各Ｇタイプ・シーケンスは、
表面からの出口を示す。このシーケンスの右に位置する
ラインの部分の自動塗りつぶしが割り込まれる。他のす
べてのシーケンスは、表面のグレージングを示し、塗り
つぶしには影響を及ぼさない。

【００６５】図１０および図１１は、図８および図９で
扱った２つのケースの画面のイメージのプロッティング
に対する読取り時にＧの値のシーケンスがどのように割
り込まれるかを示す。

【００６６】これらの図は、図８₃および図９₃に示し
たのと同じ画面の部分を表す。同じ位置を有するセル
は、同じ座標によって参照される。たとえば、図８₃の
ライン８の場合、００３３００である遭遇したシーケンスは、Ｇ_min Ｇ_min Ｇ_max Ｇ_max Ｇ_min Ｇ_min として解釈される。

【００６７】これは、輪郭のグレージングを伴い、輪郭
の交差を伴わないものである。採用した規約では、一方
が値Ｇ_minであり他方が値Ｇ_maxである２つの値の間の
中間値Ｇ₀によって交差が表され、第１の値Ｇ_minの前
または後にこの値Ｇ_min以下の値が来て、第１の値Ｇ
_maxの後または前にこの第１の値以上の値Ｇ_maxが来る
ことを想起されたい。表面への入口は、Ｇ_min Ｇ_min Ｇ₀ Ｇ_max Ｇ_max の形をとり、出口は、Ｇ_max Ｇ_max Ｇ₀ Ｇ_min Ｇ_min の形をとる。

【００６８】したがって、変数Ｇは引き続き、輪郭また
はフィラー・プロット済みフィーチャの外側から内側へ
増加し、逆のケースでは、減少する。増加または減少は
おそらく、輪郭交差画素に割り当てられた中間値の前ま
たは後に来る値群に関してはゼロである。図８ないし図
１０では、輪郭交差画素の近傍の画素のＧの値は０また
は７である。これは特殊なケースである。遷移は、単調
に増加または減少する値を有する漸進的なものでもよ
い。図１０および図１１の他のラインについては、詳し
く説明しない。変数Ｇの値のシーケンスの解釈の結果を
各ラインのヘッドに示す。

【００６９】次に、本発明の特定の実施例による典型的
なコード化を図１２に関して説明する。

【００７０】色記号のディジタル生成の場合、費用／効
率の妥当な兼合いは、イメージ・メモリ中で画素当り１
６ビットを使用することによって得られることが判明し
ている。一般的な規則として、構成要素の標準化のため
に８の倍数であるビット数を使用することが好ましい。

【００７１】１６ビットでは、本発明を使用する際、フ
ィラー・プロット済みフィーチャのみが存在する画面部
分上にフィラー・プロット済みフィーチャの色を記録す
るために１１ビットを使用することができる。

【００７２】その結果得られるコードを図１２₁に示
す。このコードは２つの識別ビットを有し、この２ビッ
トは値の組合せ００を有する。３ビットは、遷移値Ｇを
記録するために留保され、１１ビットは、赤色および緑
色に４ビットと、青色に３ビットの割合で比色を示すた
めに留保される。

【００７３】フィラー・プロット済みフィーチャが、以
前にプロットされた輪郭と交差する画面の点の場合、プ
ロセスはさらに複雑である。書込みの前にイメージ・メ
モリを再読取りすることによって、この種の構成を検出
することができる。

【００７４】この場合、書込みの前に、現フィラー・プ
ロット済みフィーチャの下方で検出された輪郭またはフ
ィラー・プロット済みフィーチャに関する情報を局所的
に圧縮する必要がある。この圧縮は、書込み中の画素の
右および左に位置する２つの画素に対して実行される。
これらの画素は、輪郭交差情報を検出して復元するため
に読み取られる。上記でさらに判明しているように、こ
の検出機構は、以下でさらに説明し、この典型的な実施
例に関して以下でさらに説明するように、Ｇの値を有す
るシーケンスまたは専用ビットに関する輪郭交差情報の
読取りを使用する。次いで、輪郭交差情報がすでに抽出
されており、交差情報がもしあれば、それが検出された
画素に対して交差ビットが活動化されていることを示す
識別コード１０（図１２−３）がこれらの画素に割り当
てられる。したがって、フィラー・プロット済みフィー
チャに関する一般的な規則として、コード００が使用さ
れる。輪郭の交差が厳密に現在フィラー・プロット済み
フィーチャの画素で検出される特定の例では、識別ビッ
トの組合せ１１（図１２−４）によって、プロット済み
フィーチャの色に関する精度が失われることを犠牲にし
てこの輪郭交差情報を記憶することができる。この精度
の低下が極めて局所的なものであり、全体的な画質に対
しては影響を与えないことに留意されたい。

【００７５】識別コード０１（図１２−２）は、以前に
プロットされた他の輪郭にも属する画素に共通せず、あ
るいは前記画素の近傍でもない輪郭の画素に割り当てら
れる。このコードはさらに、値０１の２識別ビットと、
遷移変数Ｇに割り当てられた３ビットと、現輪郭の番号
を識別する３ビットとを備える。この輪郭番号によっ
て、グラフィック読取りプロセッサは、この輪郭に割り
当てられた色コードを探索することができる。残りの８
ビットは、輪郭交差ビットである。この数は２³に等し
い。この数は、輪郭番号を識別するビットに関して可能
な組合せの数に等しい。交差ビットの数が２ⁿ（ｎは、
輪郭番号の識別に割り当てられたビットの数を表す）に
等しいことが好ましいことは明らかである。というのは
その場合、１６ビットの場合と同様に、すべてのビット
が最適に使用されるからである。しかし、他の構成を検
討することができることが理解されよう。したがって、
２ケース識別ビットと、変数Ｇ用の３ビットと、輪郭番
号用の４ビットとを有する２４ビット上でコード全体を
セットアップする場合、輪郭交差ビットには１５ビット
が残され、２⁴±１を与える。これは、この場合のすべ
てのビットの効率的な使用法である。これに対して、２
識別ビットと、変数Ｇ用の３ビットとを有するケース０
０では、色用に１９ビットが残され、これは一般に過剰
である。このため、この好ましい実施例では、演算は１
６ビット上で行われる。このため、処理は８つの輪郭に
対して効率的に行うことができる。イメージがこれより
も多くの輪郭を有する場合、それぞれ、最大で８つの輪
郭しか有さない、スキャンラインに平行な帯域、たとえ
ば水平帯域としてイメージを分割することができる場合
は、依然として１６ビット・コードを使用することがで
きる。その場合、ラインの簡単なカウンティングによっ
て、グラフィック・プロセッサは各バンドを全体的なイ
メージとして処理することができる。

【００７６】コード１０（図１２−３）はコード０１と
同じであるが、このコードは、それに割り当てられた画
素がすでに再読取りされており、必要に応じて、現プロ
ット済み部分の前に来る輪郭に関して交差ビットがマー
ク付けされていることを示す。この情報の一貫性はおそ
らく、前の記録動作時に破壊されているので、この画素
を再読取りする必要はない。

【００７７】最後に、コード１１（図１２−４）は、輪
郭との交差に位置するフィラー・プロット済みフィーチ
ャに使用される。８ビットは交差ビットである。色は、
赤色に２ビット、緑色に２ビット、および青色に２ビッ
トの６ビット上で圧縮される。

【図面の簡単な説明】

【図１】単一のイメージを有する画面の図である。

【図２】図１のイメージに関連するイメージ・メモリの
概略的図である。

【図３】図２のメモリのセルのメモリ・ワードの概略的
図である。

【図４】本発明を実施するグラフィック・プロセッサの
図である。

【図５】本発明を説明するグラフである。

【図６】本発明を説明するグラフである。

【図７】本発明を説明するグラフである。

【図８】あるタイプの輪郭に関する画面の画素の一部を
示す図である。

【図９】あるタイプの輪郭に関する画面の画素の一部を
示す図である。

【図１０】図８に対応するシーケンスの読取り時の画面
上の解釈を示す図である。

【図１１】図９に対応するシーケンスの読取り時の画面
上の解釈を示す図である。

【図１２】本発明による実施例の典型的なコード化を示
す図である。

フロントページの続き (72)発明者オリビエ・ペルニアフランス国、92400・クールブボワ、リユ・ジイ・ペー・タンボ・50、トムソン− セエスエフ・エス・セ・ペー・イー

Claims

【特許請求の範囲】

【請求項１】画面上に１組の画素で形成されたイメー
ジをリフレッシュするために周期的に読み取るように構
成されたイメージ・メモリのワードをコード化する方法
において、イメージが、イメージの背景上に見える表面
Ｓ₁，．．．，Ｓ₂，．．．，Ｓ_pを備え、これらの表
面がそれぞれ、一様な色を有し、輪郭Ｃ₁，．．．，Ｃ
₂，．．．，Ｃ_pによって区画され、輪郭がそれぞれ、
少なくとも２つの表面の境界または表面と背景の境界に
位置する画素を連結する中線と、少なくとも、中線の画
素のすぐ近傍にある画素を、中線の両側に備える中線の
近傍とを備え、イメージがさらに、フィラー・プロット
済みフィーチャを含み、画面の１つの画素が、ワードを
含むことができるメモリ・セルに１対１で対応し、現在
セルの読取りが、対応する画素を画面上に書き込むため
に必要な情報の少なくとも一部を構成し、各読取り後に
イメージ・メモリが消去され、第１の優先順位が輪郭に
割り当てられ、第２の優先順位がフィラー・プロット済
みフィーチャに割り当てられ、最初に輪郭が記録され、
次いでフィラー・プロット済みフィーチャが、このよう
な各プロット済みフィーチャ・タイプごとに優先順位の
昇順で記録され、最高優先順位を有するプロット済みフ
ィーチャが最後に記録され、輪郭に関して再コード化さ
れたメモリ・ワードが、輪郭の中線に関係するメモリ・
ワードだけでなく、各輪郭の近傍に関係するメモリ・ワ
ードも含み、再コード化された各メモリ・ワードのコー
ドが、再コード化ビットの書込みの環境を識別する２つ
の情報ビットを備え、この２つのビットにより、異なる
可能な値の組合せによって、 − ２ビットの値の第１の組合せによって識別されるケ
ースであって、示された画素に関して、前に書き込まれ
た輪郭のプロッティング上にないフィラー・プロット済
みフィーチャを識別する第１のケースと、 − ２ビットの値の第２の組合せによって識別されるケ
ースであって、示された画素に関して、他の輪郭のプロ
ッティング上にない輪郭プロッティングを識別する第２
のケースと、 − ２ビットの値の第３の組合せによって識別されるケ
ースであって、示された画素に関して、前の輪郭の近傍
にある輪郭プロッティングを識別する第３のケースと、 − ２ビットの値の第４の組合せによって識別されるケ
ースであって、示された画素に関して、前にプロットさ
れた輪郭に共通のフィラー・プロッティングを識別する
第４のケースの４つのケースと、を識別可能であることを特徴とするイメージメモリのコ
ード化方法。
【請求項２】画素がラインおよび列として配置された
画面の場合、画面のプロッティングに対する走査がライ
ンごとに行われ、近傍の画素が、輪郭の中線の画素を含
む画素のラインまたは列上に位置する一定数の画素によ
って構成され、近傍の画素が、中線の画素でのプロット
済みフィーチャの法線が、列によって規定された方向に
角度的に近いときにライン上にあり、そうでない場合に
は列上にあり、中線の両側の近傍の画素の数が等しいこ
とを特徴とする請求項１に記載の方法。
【請求項３】各再コード化メモリ・ワードのコード
が、最初の３つのケースでは、輪郭またはフィラー・プ
ロット済みフィーチャ内の色値と外部に位置する色値の
比を表す変数Ｇを記録するように構成されたビット群を
備えることを特徴とする請求項１に記載の方法。
【請求項４】各再コード化メモリ・ワードが、最初の
３つのケースでは、変数Ｇを記録するように構成された
ビット群を備え、この変数Ｇの値が、輪郭またはフィラ
ー・プロット済みフィーチャの外部から内部への走査方
向へ増加し、逆のケースでは減少することを特徴とする
請求項２に記載の方法。
【請求項５】変数Ｇが、輪郭またはフィラー・プロッ
ト済みフィーチャの内側の色値と輪郭の外側に位置する
色値の比を表すことを特徴とする請求項４に記載の方
法。
【請求項６】第２、第３、および第４のケースの場
合、画面のイメージに関して予想される輪郭の数に等し
い数のビットを含むビット群が、輪郭交差を記録するた
めに留保され、この交差が、群のビットに割り当てられ
た値によって識別され、群の各ビット自体が、１つの輪
郭に１対１で対応することを特徴とする請求項１から５
のいずれか一項に記載の方法。
【請求項７】第２および第３のケースの場合、あるビ
ット群が、輪郭番号の記録用に指定されることを特徴と
する請求項１から５のいずれか一項に記載の方法。
【請求項８】第２および第３のケースの場合、輪郭交
差記録専用のビットの数が２ｎに等しく、ｎが、輪郭番
号の記録用に構成されたビットの数を指定することを特
徴とする請求項６に記載の方法。
【請求項９】第１のケースの場合、コードが、２ケー
ス識別ビットと、変数Ｇの値を示すビット群の他に、色
値を示す他の１つのビット群のみを備えることを特徴と
する請求項３から５のいずれか一項に記載の方法。
【請求項１０】第４のケースの場合、コードが、２ケ
ース識別ビットと輪郭交差ビット群の他に、色値を示す
他の１つのビット群のみを備えることを特徴とする請求
項１に記載の方法。
【請求項１１】第４のケースの場合、コードが、２ケ
ース識別ビットと輪郭交差ビット群の他に、色値を示す
他の１つのビット群のみを備えることを特徴とする請求
項６に記載の方法。