JPH05204363A

JPH05204363A - ドットマトリクス装置における輪郭字体文字生成のための高速垂直走査−変換・充填方法及びその装置

Info

Publication number: JPH05204363A
Application number: JP4190262A
Authority: JP
Inventors: Jim C K Lo; ジム・シイ・ケイ・ロ; James C Y Lung; ジェイムズ・シイ・ワイ・ラング
Original assignee: Destiny Technology Corp
Current assignee: Destiny Technology Corp
Priority date: 1991-07-12
Filing date: 1992-06-25
Publication date: 1993-08-13
Also published as: US5276790A; TW211608B

Abstract

(57)【要約】【目的】走査線とポリセグメントとの交差点の計算を
頻繁に要求しないで画像スパンの個々の遷移画素を確定
すること。【構成】ドットマトリクス装置において輪郭字体文字
を生成する高速垂直走査−変換及び充填方法及びその装
置は、スプラインデータを正規化ポリセグメントデータ
に変換する正規化ポリセグメント生成エンジンと、各ポ
リセグメントに対する遷移画素の場所を識別するか又は
識別を実行できないことを指示するデシジョンテーブル
遷移器装置（ＤＴ）、各ポリセグメントに対する遷移画
素の位置を計算する交差遷移計算装置（ＩＴ）、及び正
規化ポリセグメントデータと、ＤＴ装置及びＩＴ装置か
ら受信した入力とに応答して、各遷移画素のＸ座標及び
Ｙ座標に対応する信号を発生するように動作する遷移画
素座標生成装置から構成される垂直走査変換エンジン
と、ｘ及びｙ座標セグメントに応答して、ビットマップ
印刷装置及びビットマップ表示装置を駆動するときに使
用するためのビットマップ化文字画像データを生成する
ように動作するパリティ充填エンジンとを含む。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般に、電子的に記憶
されている画像データをドットマトリクス出力装置を駆
動するために使用できる形態に変換する方法及び装置に
関する。本発明は、特に、陰極線管及びドット印刷装置
などのドットマトリクス出力装置を含む効率の良い実時
間処理システムにおいてスプライン輪郭フォーマットの
文字／図形の形状充填を実行するために使用される走査
−変換理論を実現する改良された方法及び装置に関し、
そのような方法及び装置では、画像データを図形／数学
的フォーマットから表示装置又は印刷装置用のフォーマ
ット（すなわち、一連のドット／画素）に変換する。

【０００２】

【従来の技術】元の輪郭フォーマットから何らかの二次
元形状を生成するために要求される２つの不可欠なプロ
セスは、「走査−変換」と、「形状−充填」である。走
査−変換は、表示すべき画像輪郭の数学的表示に整合す
る装置画素ドットのパターンを選択するプロセスであ
り、充填は、走査−変換プロセスから生成された輪郭画
素ドットにより境界を規定された内側領域の中に入る装
置画素ドットをターンオンするプロセスである。今日の
適用状態を見ると、画像の大半は、たとえば、活版印刷
文字などは充填の使用を要求するが、従来の技術による
多くの走査−変換方法は画質や性能を最適化しない。印
刷又は表示される文字は真正のデザインを許容しうる速
度で複製することが望ましい。様々な活版印刷デザイナ
ーは活字のデザインを記憶するためにベクトル，アー
ク，Ｂｅｚｉｅｒｓ、Ｂスプラインなどの様々に異なる
フォーマットを選択できるのであるが、市販の製品は様
々に異なるフォーマットに対していくつかの独立した方
法を使用するのではなく、利用できる様々な字体規格に
適応するために１組の普遍的な走査−変換・充填方法を
使用することがより望ましい。

【０００３】Ｊ．Ｅ．Ｂｒｅｓｅｎｈａｍによる科学論
文「ＡｌｇｏｒｉｔｈｍｆｏｒＣｏｍｐｕｔｅｒＣ
ｏｎｔｒｏｌｏｆａＤｉｇｉｔａｌＰｌｏｔｔ
ｅｒ」（ＩＢＭＳｙｓｔｅｍｓＪｏｕｒｎａｌ第４
巻第１号、１９６５年刊）の中に報告されているこの分
野の初期の研究によれば、文字輪郭形状を充填する走査
−変換方法は実際の文字デザインより黒く、肉太の形状
を生成し、また、ポイントサイズが小さいとき及び／又
は特定の画像ごとに利用可能な画素の数に制約のある低
分解能のラスタ装置の場合には視覚的に最も目立つ悪影
響をうける。その数のＢｒｅｓｅｎｈａｍの研究論文
「ＡＬｉｎｅａｒＡｌｇｏｒｉｔｈｍｆｏｒＩ
ｎｃｒｅｍｅｎｔａｌＤｉｇｉｔａｌＤｉｓｐｌａ
ｙｏｆＣｉｒｃｕｌａｒＡｒｃｓ」（Ｃｏｍｍｕｎ
ｉｃａｔｉｏｎｏｆｔｈｅＡＣＭ，２０（２），１
９７７年２月刊、１００〜１０６ページ；Ｊ．Ｄ．Ｆｏ
ｌｅｙとＡ．ＶａｎＤａｍの「Ｆｕｎｄａｍｅｎｔａ
ｌｓｏｆＩｎｔｅｒａｃｔｉｖｅＣｏｍｐｕｔｅ
ｒＧｒａｐｈｉｃｓ」，Ａｄｄｉｓｏｎ−Ｗｅｓｌｅ
ｙＰｕｂｌｉｓｈｉｎｇＣｏ．，１９８２年刊，４
３３〜４３６，４６１ページをさらに参照）には、特定
のアーク活字に特に適用される走査−変換概念が記載さ
れている。充填方法についてなされた研究は走査−変換
プロセスに関する研究とは別であったので、それらの独
立した発見を組合わせて、首尾一貫した矛盾のない解決
方法を提供することはできない。

【０００４】１９８６年１２月２日にシゲキ・ツジオカ
他に対し発行された名称「ＦｉｌｌｅｄＳｈａｐｅｄ
ＧｅｎｅｒａｔｉｎｇＡｐｐａｒａｔｕｓ」の米国
特許第４，６２６，８３８号には、多角形充填機能をよ
り速い速度で実行するために、内側充填及びパリティ走
査線充填の概念をハードウェアモジュールにおいて採用
する方法が開示されている。ツジオカの構成では、マイ
クロプロセッサを使用して、Ｂｒｅｓｅｎｈａｍアルゴ
リズムの走査−変換機能を実行する。マイクロプロセッ
サにより生成されたポリセグメントをハードウェア充填
モジュールに供給する。このモジュールは１つの「充填
開始／終了点生成回路」と、１つの「充填開始／終了点
メモリ」と、１つの「輪郭メモリ」と、１つの「充填回
路」とを具備する。モジュールに供給した結果、内側ビ
ットマップが得られ、そのビットマップは「再生メモ
リ」に書込まれて、陰極線管（ＣＲＴ）に表示される。
ツジオカ他の方法では、ポリセグメントを表わす座標値
は整数の形態をとる。整数値は「充填開始／終了点生成
回路」へ送られ、そこで、ポリセグメントの線分ごとに
充填開始点のアドレスと、充填終了点のアドレスとを計
算する。座標は整数であって、実数形態ではないので、
文字のセリフなどの微妙な曲線の性質はプロセスの中で
失われてしまうこともあるだろう。ツジオカ他の方法に
おいては、多角形の内側を充填し且つ多角形の輪郭をペ
イントするために、「輪郭メモリ」と「充填開始／終了
点メモリ」という２つの別個のメモリを使用する。

【０００５】１９８８年５月１７日にＡｄｒｉａｎＨ
ａｗｅｓへ発行された名称「ＡｒｅａＦｉｌｌｉｎｇ
ＨａｒｄｗａｒｅｆｏｒａＣｏｌｏｒＧｒａ
ｐｈｉｃｓＦｒａｍｅＢｕｆｆｅｒ」の米国特許第
４，７４５，５７５号には、領域充填を実行するための
ハードウェアを使用する方式が記載されている。マイク
ロプロセッサを使用して、Ｂｒｅｓｅｎｈａｍの走査−
変換アルゴリズムを実行する。走査−変換用マイクロプ
ロセッサにより生成されたポリセグメントをハードウェ
ア充填モジュールに供給する。Ｈａｗｅｓの方法は多角
形領域の輪郭を記憶するために単一の補助メモリを使用
し、走査−変換される多角形に関連するあらゆる水平充
填スパンについて充填開始点と、充填終了点の情報を記
憶する。この構成はＢｒｅｓｅｎｈａｍの整数アルゴリ
ズムに基づいているので、これを輪郭字体に適用したと
きにはツジオカ他の方法と同じ画質の問題が生じる。た
だし、Ｈａｗｅｓの構成では１組のメモリが省略されて
いる。

【０００６】Ｒ．Ｄ．Ｈｅｒｓｈによる科学論文「Ｖｅ
ｒｔｉｃａｌＳｃａｎ−Ｃｏｎｖｅｒｓｉｏｎｆｏ
ｒＦｉｌｌｉｎｇＰｕｒｐｏｓｅｓ」（Ｐｒｏｃｅ
ｅｄｉｎｇＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓＩ
ｎｔｅｒｎａｔｉｏｎａｌ８８，ジュネーブ，Ｓｐｒｉ
ｎｇｅｒＶｅｒｌａｇ，１９８８年刊）は、走査−変
換方法の研究について報告しており、走査・変換及び充
填の方式の互いに矛盾する問題を解決するための方法を
記載している。スプラインを、非整数の頂点を有する可
変長のポリセグメントに細分する。ポリセグメントと走
査線との交差点から、アルゴリズムは始まりと終わりの
標識として水平スパンごとに２つの遷移画素を確定す
る。各遷移画素は黒から白又は白から黒への色の変化を
指示する。２つの遷移画素の間には内側画素があり、内
側画素は「パリティ走査線充填方法」を適用することに
より充填される。交差点を計算し且つ遷移画素の場所を
規定するために実行される幾何学的計算は、多くの時間
を要する。分解能が高くなるにつれて、実行すべき計算
は多くなる。

【０００７】１９９０年６月２６日にＣｈｒｉｓｔｏｐ
ｈｅｒＨａｓｓｅｔｔへ発行された名称「Ｍｅｔｈｏ
ｄａｎｄＡｐｐａｒａｔｕｓｆｏｒＥｎｈａｎ
ｃｅｄＳｐｅｅｄＧｒａｐｈｉｃＩｍａｇｅＰ
ｒｏｃｅｓｓｉｎｇ」の米国特許第４，９３７，７６１
号には、ハードウェアを使用して輪郭字体を描出する方
法が記載されている。Ｈａｓｓｅｔｔの方法では、線又
は曲線を走査−変換（Ｈａｓｓｅｔｔの特許においては
「不連続点変換」という用語で表わしている）してポリ
セグメントを得た後に、そのポリセグメントを表わす座
標値を実数で符号化する。Ｈａｓｓｅｔｔの方法によれ
ば、走査−変換したポリセグメントをターゲットマーキ
ングエンジンの座標分解能にさらに変換する。その「変
換」プロセスの間に、ポリセグメントに対してスケーリ
ングアップ演算又はスケーリングダウン演算を適用して
も良い。Ｈａｓｓｅｔｔの方法はディザリング方式を利
用して、ポリラインセグメントを平滑化し、それらのセ
グメントを「変換」過程の間にさらに走査−変換する。
最終的な走査−変換、ディザリング済みのポリセグメン
トをディザリング済み画像輪郭形状及び充填すべき内側
画素のマップとして分離し、その後、それらを組合わせ
てラスタオペレータに入力する。Ｈａｓｓｅｔｔの方法
は、走査−変換した座標値の小数部を保持することによ
り、輪郭点の確定と、充填開始点及び充填終了点の確定
に際しさらに高い精度を示す。ところが、輪郭点と、充
填開始点／充填終了点とを記憶するために２つの別個の
メモリが必要である。最終ビットマップ画像は、輪郭画
像と、全ての開始点／終了点をパリティ充填することに
よって得られる充填画像とを組合わせることにより形成
される。オブジェクトの輪郭は従来通りの走査−変換ア
ルゴリズム（１例としてＢｒｅｓｅｎｈａｍのアルゴリ
ズムを使用する）により生成されるので、Ｈａｓｓｅｔ
ｔの方式においてビットマップ画像の画質を向上させる
ためにディザリング方式を使用する。

【０００８】

【発明が解決しようとする課題】本発明の目的は、走査
線とポリセグメントとの交差点の計算を頻繁に要求する
ことなく、画像走査スパンの個々の遷移画素を確定する
ための垂直走査−変換プロセスを加速する装置及び方法
を提供することである。

【０００９】

【課題を解決するための手段】簡単にいえば、本発明の
好ましい一実施例は、スプラインデータを正規化ポリセ
グメントデータに変換する正規化ポリセグメント生成エ
ンジンと、各ポリセグメントに対して遷移画素の場所を
識別するか又は識別を実行できないことを指示するデシ
ジョンテーブル（決定表）遷移器（ＤＴ）装置、各ポリ
セグメントに対して遷移画素の位置を計算する交差点遷
移計算装置（ＩＴ）及び正規化ポリセグメントデータ
と、ＤＴ装置及びＩＴ装置から受信した入力とに応答し
て、各遷移画素のＸ座標とＹ座標に対応する信号を発生
するように動作する遷移画素座標生成装置から構成され
る垂直走査変換エンジンと、Ｘ及びＹ座標セグメントに
応答して、ビットマップ印刷装置又はビットマップ表示
装置を駆動するときに使用するためのビットマップ化文
字画像データを生成するように動作するパリティ充填エ
ンジンとを含む。

【００１０】輪郭文字スプラインを不連続画素表示にさ
らに良く近似するために、本発明はポリセグメントを１
つの画素の対角線より短い長さに制限する。現在開始点
から次の到達点までの距離がｘ変位及びｙ変位に関して
１つの画素の対角線より長くならないように保証するこ
とを先取する「適応制御」と呼ばれる正規化プロセスを
利用しているために、それらのポリセグメントは「正規
化ポリセグメント」と呼ばれる。全てのポリセグメント
を正規化した後、本発明の装置の回路はより高い効率を
示すことができ、また、設計サイズの縮小を実現するこ
とができる。

【００１１】正規化ポリセグメントの概念を採用する
と、現在点（ＣＰ）ごとに、それについて可能な次の点
（ＮＰ）は現在画素の中に位置するか又は現在画素に隣
接する８つの画素の中に位置することになるので、問題
を解決する労力の範囲は狭まる。曲線を近似する精度を
増すために、各画素を４つの象限に分割する。従って、
現在画素の４つの象限の中の１つにある開始点（ＣＰ）
から到達しうる点は、現在画素と隣接する画素の中にあ
る３６の象限の内側に入ると考えられる。そのあらゆる
組合わせを１４４個のエントリを有するデシジョンテー
ブルにマッピングする。

【００１２】適応制御した正規化ポリセグメントと、デ
シジョンテーブルにおいて実現される垂直走査−変換方
式との組合わせは高画質の文字画像充填を可能にすると
共に、曲線のゆがみを最小限に抑えることにより活字デ
ザインの保全性を維持する。対を成すＤＴとＩＴは、従
来の計算集中方法と比較して、遷移画素を求める速度を
増す。本発明及びその装置は様々な輪郭字体フォーマッ
トを支援するための高速出力及び真正に近い画質を提供
する。

【００１３】

【実施例】本発明は、オブジェクトの多種多様な図形／
数学的フォーマットを表示又は印刷すべきラスタ画像に
変換するプロセスをスピードアップするために、レーザ
ープリンタ、陰極線管、電子写真印刷機などの様々なド
ットマトリクス装置に適用することができる垂直走査方
法及び垂直走査装置に関する。ここで説明する装置は、
特に、本発明を実現することにより実現されるレーザー
プリンタ及び表示装置のための回路を指向している。そ
のような回路は実時間アプリケーションでマルチフォー
マット輪郭字体文字生成を処理することができる。しか
しながら、同一の方式を使用して走査−変換プロセスを
改善するために、他のドットマトリクスアプリケーショ
ンやドットマトリクス装置にも本発明を適応できること
は言うまでもない。

【００１４】直覚的にいえば、画素は印刷紙の上又はＣ
ＲＴ画面に現れる実際の出力ビットである。デスクトッ
プ出版の分野における近年の開発によって、エンドユー
ザーは印刷又は表示すべき文書を構成するための書体、
スタイル、ポイントサイズ及び充填方法（シェーディン
グ、パターン充填など）を選択する上で、多大な融通性
と自由を与えられることになった。それらの異なる活字
に関する入力フォーマットは、アーク、Ｂｅｚｉｅｒな
どの好ましいフォーマットを有すると思われる様々な活
字製造会社／字体設計者が記憶させたデータである。本
発明は、均一な方式であるポリセグメントを使用して様
々な字体フォーマットを処理することにより、入力の互
換性を与える。さらに、実時間で処理しなければならな
いデータや活字の量は膨大なものとなりうるので、本発
明では、性能を向上させる一方で、ポイントサイズが小
さいとき又は分解能が低いときでも高い視覚的読みやす
さと高い画質を発揮させるために、小さな正規化ポリセ
グメントと、デシジョンテーブルとを利用する。

【００１５】ポイントサイズが小さいとき、文字形状を
形成するために利用できる画素の数は限られる。文字形
状を生成し、充填する方式は、その文字を読む者に対す
る視学的印象を大きく左右する。図１及び図２は、印刷
サンプルの２つの例を示す。図１は、１０１及び１０２
で示す活字の色の濃い肉太の文字を生成するＢｒｅｓｅ
ｎｈａｍの走査−変換方法を使用して生成されたプリン
トを示す。これと比較して、本発明の垂直走査−変換方
法は、１０３及び１０４で示すように、よりあざやかな
文字を生成する。２つの例は共に４ポイント、８ポイン
ト及び１２ポイントのサイズを使用する。ポイントサイ
ズ４では、垂直走査−変換方法はＢｒｅｓｅｎｈａｍの
方法より読みやすい文字を生成する。ポイントサイズ８
及び１２では、Ｂｒｅｓｅｎｈａｍのサンプルは正規設
計の書体ではなく肉太の書体のように見える。

【００１６】図３は、輪郭の周囲の色（黒又は白）がそ
れら２つの走査−変換方法によりどのようにして確定さ
れるかを図式的に示す。１１１で示すＢｒｅｓｅｎｈａ
ｍの走査−変換方法の場合、輪郭１１３の上に位置する
全ての画素は色の濃い境界画素１１５である。境界画素
の内側の画素は内側画素１１５と呼ばれて、充填され
る。Ｂｒｅｓｅｎｈａｍの方法は輪郭と、２つの隣接す
る画素中心との距離１１４を比較する。画素中心から境
界輪郭までの距離が短いほうの画素を「オン」（黒色充
填）として確定する。これに対し、１１２で示す垂直走
査−変換がオンする境界画素１１７の数は少ない。輪郭
の内側に入る画素面積が５０％を越える画素のみを黒色
充填する。Ｂｒｅｓｅｎｈａｍの方法ではオンされる
が、垂直走査−変換ではオンされない画素を陰影のない
破線の円１１８により示してある。図４に示すように、
垂直走査−変換は、画素面積の５０％を越えて充填経路
１３１，１３２に入る画素のみをオンする。この方式
は、画素の中心が輪郭の内側に入っているならば、その
内側に面積の５０％を越える面積が入っている確率は非
常に高いことを示唆する。画素１３３の面積の５０％未
満の部分しか充填経路の内側に入っていない場合には、
その画素は白色のままである。それとは対照的に、Ｂｒ
ｅｓｅｎｈａｍの方法は充填部分の中の面積を測定する
のではなく、オン（１３６）又はオフ（１３５）の特性
を確定するために、輪郭１３４から画素中心までの距離
１３７を測定する。輪郭１３４の傾きが４５度未満であ
る場合、輪郭を水平に近いセグメントであると考え、輪
郭セグメントの垂直方向に上と下に位置する２つの隣接
画素１３５，１３６を比較する。垂直に近い輪郭セグメ
ント１４１の場合、Ｂｒｅｓｅｎｈａｍの方法はセグメ
ント１４１に隣接する２つの水平画素１３８，１４０を
比較する。

【００１７】本発明はポリセグメント方式を利用して様
々な字体フォーマットを処理する。図５に破線で示すス
プライン１５１（湾曲輪郭セグメント）を、より短いポ
リセグメント１５２と呼ばれる直線に分割して、スプラ
イン曲線に近似させる。ポリセグメントに分割する方法
は、後に、高画質と高速動作を得るための決定的な過程
であることがわかる。それらのポリセグメントは走査線
との交差点を生成するために使用される。

【００１８】図６に示すように、走査線１６１とポリセ
グメントとが交差するところ１６２，１６４には、必
ず、遷移画素として選択された画素１６３，１６５があ
る。遷移画素は、中心点が交差箇所のすぐ右側に位置し
ている画素として定義される。遷移画素は充填すべき水
平スパンの始まり又は水平スパンの終わりの後の１つの
画素、言いかえれば色の変化（黒から白、又は白から
黒）を表わす。

【００１９】図７に示すように、１つのスパンの第１の
遷移画素１７１は充填プロセスの始まりを指示する。充
填プロセスは、次の画素が他方の遷移画素１７３である
と予測するまで継続する。１つのスパンで充填すべき最
後の画素は、対を成す遷移画素のうち第２の遷移画素１
７３の前に位置する画素１７２である。

【００２０】ところが、ポリセグメント方式は図８及び
図９に示すような異なる結果を生じる場合がある。図８
では、ポリセグメント２２１，２２２の長さが異なり、
一部のポリセグメントは他のポリセグメントよりはるか
に長い。図９では、全てのポリセグメント２３１，２３
２が１つの画素の対角線の長さより短い長さを有する。
それらのセグメントは、本発明の装置に設けられた適応
制御サブシステムにより正規化されている。含まれるポ
リセグメントの数が多くなればデータの量は増えるが、
それぞれの交差事象の複雑さは軽減される。本発明の装
置ではパイプライン方式を採用しているので、簡略化さ
れた構成によって得られる性能の向上はデータ流れのオ
ーバヘッドをしのぐ。

【００２１】以下に詳細に説明するが、本発明を具現化
した装置に対する入力は基準化文字輪郭データの形態を
とる。先に示唆した通り、まず、Ｌｉｅｎ他の名称「Ｍ
ｅｔｈｏｄａｎｄＡｐｐａｒａｔｕｓｆｏｒＲ
ｅｎｄｅｒｉｎｇＶｅｃｔｏｒｓＵｓｉｎｇＢｒ
ｅｓｅｎｈａｍＰａｒａｍｅｔｅｒｓ」による米国特
許第４，８５５，９３５号に記載されているような適切
なポリセグメント生成エンジンを使用して、輪郭データ
を正規化ポリセグメントに変換する。次に、垂直走査−
変換を実行して、印刷装置又は表示装置を駆動するとき
に使用するためのビットマップ化画像データを生成す
る。ここで、本発明の好ましい実施例を説明する前に、
いくつかの用語を定義すると共に、垂直走査−変換プロ
セスの機能を説明する。

【００２２】ドットマトリクス装置においては、１つの
画素が独立した単位であり、黒色又は白色のいずれかを
表わすために整数値を有する。ところが、輪郭形状を近
似するためにさらに精密な計算を行うときには、各画素
を非整数、すなわち、小数又は整数と小数により測定し
ても良い。図１０の場合、ｘ，ｙ座標を使用して画素２
４０を規定している。１つの画素は１単位の幅（ｘ方
向）と、１単位の高さ（ｙ方向）とを有するといわれ
る。この定義によれば、画素の中心２４２は（ｘ＋０．
５，ｙ＋０．５）の場所値を有し、点２４４（ｘ，ｙ）
はその画素の開始アドレスである。境界の定義に関して
いえば、隣接する画素が共用しうる共通の境界は存在し
ない。図１１に示す通り、各画素は左辺２５０と、底辺
２５２とを「所有」している。従って、それら２つの辺
の上に位置する点は、いずれも、現在画素の一部である
と考えられる。現在画素の上辺２５４はその上方の画素
に属し、右辺２５６はその右側にある画素に属する。こ
の境界定義は、起こりうる重複条件に起因するあいまい
さを回避する。

【００２３】遷移画素（ＴＸ）の決定実行プロセスを管
理し且つあいまいなケースを識別するために、図１２及
び図１３に示すように各画素２８０を４つの象限に分割
する。それら４つの象限は左周りの方向にＱ１（２８
１），Ｑ２（２８２），Ｑ３（２８３），Ｑ４（２８
４）とラベル付けされている。画素に関する境界定義を
象限にも適用する。境界に沿って付した数字からわかる
通り、Ｑ１及びＱ２の上部の境界２８５（図１３）はそ
の上の画素２８７の象限Ｑ３及びＱ４に「属し」てい
る。また、右側の境界２８６はその右側の画素２８８の
象限Ｑ２及びＱ３に「属し」ている。

【００２４】方向特性によってポリセグメントを定義す
るために、図１４を参照する。各ポリセグメント３００
は「現在画素」ＣＸ３０４の中に位置する開始点ＣＰ３
０２と、「次画素」ＮＸ３０８の中に位置する終端点Ｎ
Ｐ３０６とを有する。画素ＣＸは４つの象限、すなわ
ち、ｃ１，ｃ２，ｃ３，ｃ４を有し、画素ＮＰもｎ１，
ｎ２，ｎ３及びｎ４の４つの象限を有する。正規化ポリ
セグメント３００には、現在点ＣＰがいかにして次の点
ＮＰに向かって動くかに応じて、方向を割り当てられ
る。

【００２５】図１５は、ＮＸ方向の定義を示す。詳細に
いえば、現在画素ＣＸの中に開始点ＣＰを有するポリセ
グメントは、Ｅ，ＮＥ，Ｎ，ＮＷ，Ｗ，ＳＷ，Ｓ，ＳＥ
とラベル付けされた隣接画素の中の１つの中か、又はＣ
Ｘ自体の中に次の点ＮＰを有する。従って、ポリセグメ
ントの方向は次の点が入っている隣接画素の磁針方向と
して指定される。

【００２６】図１６に示すように、その方向と座標系と
を組合わせることにより、各ポリセグメントの場所と方
向をデシジョンテーブルに記録できる。現在画素は開始
点が位置しうる４つの象限を有し且つ９画素の範囲内に
３６の着陸点を有しているので、終端点の組合わせは１
４４通りある。デシジョンテーブルをコンパクトにし且
つ実際の事象に幾何学的に対応させるために、デシジョ
ンテーブルのあらゆる情報は考えられる９つのＮＸ画素
の３６個の象限の４つの内角に蓄積される。本発明は、
それらの象限にＸ方向には「１〜１２」、ｙ方向には
「ａ〜ｌ」と索引付けすることにより、記録保持方式を
実行する。それらの索引は１４４個の記憶セルを表わ
し、各セルは２ｊ，８ｄなどのポインタを有する。たと
えば、図１６に示すように、１つのポリセグメント３２
０は１つの特定の次画素ＮＸの第２の象限ｎ２で終わ
る。開始点が現在画素ＣＸの第２の象限ｃ２で始まる場
合、このポリセグメントのＩＤはｃ２−−＞ｎ２とな
り、取り出して拡大した画素ＮＸの中に表わしてあるよ
うに、画素ＮＸの第２の象限ｎ２の左上角に位置するセ
ルに記憶される。同様に、現在画素の第４の象限のＣＰ
で始まり、次画素ＮＸの第１の象限のＮＰで終わる第２
のポリセグメント３２２は、対応するＩＤｃ４−−＞ｎ
１を有し、それは象限ｎ１の右下角のセルに記憶され
る。方向とＣＸ−ＮＸの関係づけに従って、各ポリセグ
メントの動き（場所と方向）に対応する決定（デシジョ
ン）（ＩＤ）はあらかじめ規定され、そのｘとｙにより
識別されるセルに記憶される。たとえば、ポリセグメン
ト３２０及び３２２に関する決定はテーブルの場所９ｉ
及び１２ｊにそれぞれ記憶されることになる。

【００２７】可能である１４４の決定を全て検査するこ
とにより、ポリセグメントの解析を７つの明確に異なる
決定に分類できることが明らかとなる。図１７には、そ
れら７つの決定を判断トリーの形で記載してある。可能
な決定は図中符号３４０〜３５２により表わされてい
る。唯一つの決定は「非確定」であり、さらに解析を要
求する。「無意味」決定は、ポリセグメントの長さが１
つの画素の寸法の「正規化ポリセグメント」制約を越え
るようなものである。その他の型のポリセグメントに関
する遷移画素は、デシジョンテーブル単独で確定でき
る。

【００２８】図１８は、長さが１画素の対角線を越える
ポリセグメント４００に関する「無意味」型の決定の１
例を示す。全てのポリセグメントは、以下に説明するよ
うに、適応制御により正規化されているので、このケー
スは起こるはずがない。図１９のポリセグメントはあい
まいなケースである。すなわち、画素中心の右側の交差
点４０２は遷移画素として現在画素の右側に位置する画
素を選択することを要求するが、中心の左側の交差点４
０４は遷移画素として現在画素を選択することを要求す
る。この型をデシジョンテーブルにより直ちに確定し
て、確定的決定を得るのは不可能であり、別の方法でこ
れを処理しなければならない。

【００２９】図２０及び図２１は、決定の型の別の２つ
の例を示す。「ＴＸ存在せず」は、走査線４１０と全く
交差しないポリセグメントに関する決定である。「ＴＸ
はＣＸである」は、点４１２及び４１４における交差を
表わす決定であって、遷移画素として現在画素ＣＸを選
択することを要求する。

【００３０】図２２は、交差点４１６及び４１８が現在
画素の右側の画素（ＣＸ＋１）を遷移画素として選択す
ることを要求する場合を示す。図２３は、次画素ＮＸを
遷移画素として選択させるような交差点４２０及び４２
２の型を示し、従って、「ＴＸはＮＸである」。最後の
決定の型は、図２４に示す「ＴＸは（ＮＸ＋１）であ
る」。この場合、交差点４２４及び４２６は次画素の右
側の画素（すなわち、ＮＸ＋１）を遷移画素として識別
させる。

【００３１】図２５は、４３０として、１４４個の決定
エントリを余すところなくマッピングした図表である。
各エントリは特定の決定の型を表わす簡略記号により表
示されている。１４４個のエントリのうち、４４個のエ
ントリは「無意味」である。残る１００個の有意味エン
トリのうち、「非決定」であるのはわずか２８個であ
る。これは、正規の全ポリセグメントの約２８パーセン
トはこのデシジョンテーブルにより処理できないことを
示唆している。本発明が特定して適用される輪郭字体文
字生成の用途では、あいまいな事象は稀であるので、そ
の比は通常は２８パーセントよりさらに低い。

【００３２】図１６は、終端点を指定したポリセグメン
トに分割されている曲線の１例を示す。開始点４５０
と、終端点４５２とを有するポリセグメント４４８はｃ
３−−＞Ｓ：ｎ３とタグ付けされている。すなわち、そ
の開始点は現在画素の第３の象限に位置し、また、終端
点は次画素の第３の象限に位置し、移動方向は南に向か
っている。図１６の定義に従えば、このポリセグメント
に関する決定は５ｌに「記憶」される。同様に、ポリセ
グメント４５４及び４５６に関する決定は５ｊにそれぞ
れ記憶される。

【００３３】図２７では、デシジョンテーブル方式を適
用することにより曲線を充填している。曲線は１７個の
ポリセグメントに分割されており、そのうち２つのポリ
セグメント、すなわち、ポリセグメント４５６及び４５
８のみが「？」で指示するように「非決定」であり、デ
シジョンテーブルルックアップ方式を越える追加計算を
要求する。

【００３４】デシジョンテーブルは、標準的な境界定義
に従う一般的なケースと、いくつかの特殊なケースとを
解決するためにエントリによってあらかじめ確定され
る。たとえば、図２８に示す通り、遷移画素は走査線４
６２と平行ではないポリセグメント４６０により確定さ
れる。走査線４６０上の４６４のような水平のポリセグ
メントは走査線の上方又は下方の水平ポリセグメント、
すなわち、ｃ１−−＞Ｅ：ｎ２として取り扱われ、その
決定は、ポリセグメントが走査線上にあるか否かにかか
わらず、テーブルの場所＜１０ｅ＞に記憶されて、「Ｔ
Ｘ存在せず」の決定を指示する。テーブルがそのような
条件の下で遷移画素を遷移させてしまう場合には、衝突
の状況が起こり、いくつかの特定の遷移画素をオン，オ
フとドグルさせて、後の充填プロセスを侵害するであろ
う。

【００３５】「非決定」の場合には、交差点の厳密な位
置を規定するために幾何学的計算を採用しなければなら
ない。許容しうる精度をもってＴＸについての決定を実
行するために、計算に際して部分画素格子システムを導
入する。部分画素格子の単位は１つの画素の１６分の１
であり、これは図２９及び図３０に示すようにデータを
記録するために１６ビット語を使用する。初めの１２ビ
ット（Ｉ０〜Ｉ１１）は整数部として使用されるが、そ
の符号は正，負のいずれであっても良い。言いかえれ
ば、第１のビットＩ１１は符号ビットであり、第２のビ
ットＩ１０から１２番目のビットＩ０までは整数値であ
る。１６ビット語のうち下位の４ビットＦ０〜Ｆ３は小
数部を表わすために使用される。従って、図３０に指示
する通り、１つの画素座標値は符号と、整数部と、小数
部とから構成されている。有効画素値の範囲は−２０４
８×０から２０４７×１５までであり、この２０４７×
１５は整数部２０４７と、小数部１５／１６とを有する
数を表わす。

【００３６】次に、図面の図２２を参照すると、５００
は輪郭字体文字発生器の形態をとる本発明の実現形態を
示す。これは、基本的には、５０４で示す基準化文字輪
郭スプラインデータ入力を受信し、５０６で示すように
正規化ポリセグメントデータと呼ばれる６つの対応する
情報を生成する正規化ポリセグメント生成エンジン５０
２と；正規化ポリセグメントデータに応答して、５１０
及び５１１で示す遷移画素座標データと、５１２で示す
ような、現在データ入力が遷移画素を識別しないことを
指示する代替表示とを生成する垂直走査変換エンジン５
０８と；５１０，５１１及び５１２の入力に応答して、
５１６で示す文字ビットマップデータを生成するパリテ
ィ充填エンジン５１４という３つの主要機能素子から構
成されている。

【００３７】指示した通り、正規化ポリセグメント生成
エンジン５０２により生成される出力５０６は、現在ポ
リセグメント開始点ＣＰのｘ座標及びｙ座標の整数部と
小数部（図２９及び図３０）を表わす２つの１６ビット
語ＣＰｘ及びＣＰｙと、現在ポリセグメント終端点ＮＰ
のｘ座標及びｙ座標を表わす２つの１６ビット語ＮＰｘ
及びＮＰｙと、現在ポリセグメントの傾きのｘ成分ｄｘ
とｙ成分ｄｙをそれぞれ示す２組の５データビットとか
ら構成されている。成分ｄｘはＮＰｘ−ＣＰｘの小数部
に対応する４つのデータビットと、符号ビットＩ１１
（図２９）とから構成されている。同様に、成分ｄｙは
ＮＰｙ−ＣＰｙの小数部に対応する４つのデータビット
と、符号ビットとから構成されている。

【００３８】垂直走査変換エンジン５０８はデシジョン
テーブル遷移器（ＤＴ）装置５１８と、交差点遷移器
（ＩＴ）装置５２０と、出力装置５２２という３つの基
本機能素子から構成されている。ＤＴ装置５１８は、本
質的には、図２５に示す１４４の決定を実現する「ルッ
クアップテーブル」であり、５２４で示す１０ビット入
力に応答して、図１７に示す判断トリーに対応する４つ
の１ビット出力を生成するように動作する。すなわち、
出力として、信号線５３０の表示はＤＴ装置により遷移
画素の決定を実行できるか否か（すなわち、現在画素デ
ータが「決定」であり、従って、テーブル出力は「真」
であるか否か）を示し、信号線５３２の表示は遷移画素
ＴＸが現在画素ＣＸに関連している又は次画素ＮＸに関
連していることを示し、信号線５３４の表示は遷移画素
ＴＸが信号線５３２のデータ、現在画素ＣＸ又は次画素
ＮＸのいずれかに従属すること、あるいは現在画素の右
側の画素（ＣＸ＋１）又は次画素の右側の画素（ＮＸ＋
１）であることを示し、最後に、信号線５１２の表示は
いずれかの遷移画素がＣＸ，ＣＸ＋１，ＮＸ又はＮＸ＋
１の中に存在するか否かを示す。

【００３９】交差点遷移器（ＩＴ）装置５２０は、５２
６で示す１９ビット入力からＣＸ，ＣＸ＋１，ＮＸ又は
ＮＸ＋１が遷移画素であるか否かを数学的に判定し、遷
移画素であれば、信号線５３６及び５３８に識別出力を
発生する計算装置である。ところが、ＩＴ装置５２０の
動作はＤＴ装置５１８と比べてはるかに遅いので、信号
線５３０のデータがテーブル出力は「非決定」であるこ
とを指示しない限り、ＩＴ装置の出力は無視される。

【００４０】出力装置５２２は、信号線５３０の入力に
応答して信号線５３２及び５３４のデータの２つのビッ
ト又は信号線５３６及び５３８の２つのビットのいずれ
かを選択し、５４０で示す画素座標データ入力の４８ビ
ットを操作して、信号線５１０及び５１１へ遷移画素座
標データを発生する論理回路を含む。

【００４１】先に指示したように、ＤＴ装置５１８は図
２５の１４４個のエントリを含むマップ４３０を図３２
に示す真理値表によって実現するために回路符号化方式
を使用する。本発明はスイッチ理論の周知のＫａｒｎａ
ｕｇｈマップ方式を利用して、構成を簡略にしている。
その結果、図３３に示す論理回路が得られる。図３３の
中で入力信号に付した接尾辞「Ｆ３」は入力語の小数部
の最上位ビットを指示し、接尾辞「Ｉ０」は入力語の整
数部の最下位ビットを指示する。図３１に示したような
ｄｘ及びｄｙの符号ビットはｄｘ_sign，ｄｙ_signとして
指示されている。Ｘ座標値のけた上げ又は借り（ＣＰｘ
Ｉ０とＮＰｘＩ０の排他的論理和）は「ｃｂｘ」であ
り、また、ｃｂｙはｙ座標値のけた上げ又は借り（ＣＰ
ｙとＮＰｘＩ０の排他的論理和）を示す。ＤＴ装置５１
８は５２４で示すような１０個の入力信号を受信し、次
の４つの出力信号を発生する。

【００４２】（１）信号線５１２の「ｎｏ＿ＴＸ＿ａｔ
＿ａｌｌ」は、交差点が存在していなければ１に等し
く、そうでなければ０である；（２）信号線５３０の「ｄｅｔｅｒｍｉｎｉｓｔｉｃ」
は、ＤＴ装置がＴＸを確定することができる場合は１に
等しくそうでなければ０である；（３）信号線５３２の「ＮＸ＿ＤＴ」は、遷移画素のｘ
座標ＴＸｘがＮＸｘ又は（ＮＸｘ＋１）であれば１に等
しく、ＴＸｘがＣＸｘ又は（ＣＸｘ＋１）であれば０で
ある；（４）信号線５３４の「ｒｉｇｈｔ＿ＤＴ」は、ＴＸｘ
がＣＸ又はＮＸの右側の次画素アドレスであれば１に等
しく、ＴＸｘがＣＸ又はＮＸであれば０である。

【００４３】図３４には、５５０として１つの交差点の
拡大図を示し、ＩＴ装置５２０が交差点を幾何学的に位
置規定するために使用するアルゴリズムを表示してあ
る。ドットマトリクス装置においてそのような走査線と
ポリセグメントとの交差点を見出すために、幾何学を利
用して交差点ＩＰを求めることができる。ポリセグメン
トは所定の方法により生成されるので、ポリセグメント
上のそれぞれの点の座標を記録することができる。従っ
て、既知の因子として現在点ＣＰと次の点ＮＰがあり、
走査線がｄｙの値を確定するための固定因子であると
き、ｄｘは容易に取り出される。ＣＰ＋（ｄｘ，ｄｙ）＝ＮＰＣＰ＋（ｄｘ′，ｄｙ′）＝ＩＰ

【００４４】ＤＴ装置５１８と並行して動作するＩＴ装
置５２０はポリセグメントと交差走査線との交差点５５
１のＸ座標（ＩＰｘ）を計算する。そのプロセスは、Ｉ
Ｐｘが現在画素中心の右側にあるか又は左側にあるかを
結論づけ、次に、ＴＸｘを確定することができる。ｄｘ′＝（ｄｙ′^*ｄｘ）／ｄｙＩＰｘ＝ＣＰｘ＋ｄｘ

【００４５】図３５は、そのプロセスをいかにして実現
するかを示すブロック線図である。ＩＴ装置５２０はｄ
ｙ′＝ＩＰｙ−ＣＰｙの計算を開始する。２つの条件を
検査する：（１）｜ｄｙ′｜＞０であれば、ｄｙ′_sign＝ｄｙ_sign （２）｜ｄｙ′｜＝０であれば、ｄｙ′_sign＝０（すなわち、ｄｙ′はｄｙと同じ符号を有する）ＩＰｙはｙ座標値に関しては常に画素中心レベルに位置
しているので、ＩＰｙはｄｙ′_sign固定小数値を有し、
従って、ＩＰｙＦは［３．．０］＝１０００である。こ
のようにして、４ビット２の補数器５６０と、４ビット
加算器５６２とによりｄｙ′の値を計算することができ
る。

【００４６】（１）｜ｄｘ′｜＞０であれば、ｄｘ′
_sign＝ｄｘ_signであり且つ（２）｜ｄｘ′｜＝０であれ
ば、ｄｘ_sign＝０であるので、ｄｘ′も常にｄｘと同じ
符号を有する。（ｄｙ′^*ｄｘ）及び［（ｄｙ′*ｄｘ）
／ｄｙ］を計算するプロセスの間、符号ビットを一時的
に無視することができる。そして、絶対値を計算した
後、ｄｘ′にｄｘ符号ビットを割り当てることによりｄ
ｘ′の符号ビットを回復できる。従って、４ビット絶対
値発生器５６４でｄｘをその絶対値｜ｄｘ｜に変換し、
単純な４×４アレイ乗算器５６６を使用して、（｜ｄ
ｙ′｜^*｜ｄｘ｜）の値を計算することができる。同じ
方式を適用することにより、４ビット絶対値発生器５６
８でｄｙをその絶対値｜ｄｙ｜に変換し、単純な８×４
除算器５７０を使用して、絶対値｜ｄｘ′｜を計算す
る。最後に、４ビット絶対値発生器５７２で、ｄｘ符号
ビットを組込み、右の２の補数値に変換することによ
り、｜ｄｘ′｜をｄｘ′に変換する。｜ｄｘ′｜＝０の
ときにｄｘ′_signを０に設定するために、２入力ＡＮＤ
ゲート５７４と、４入力ＯＲゲート５７６とが必要であ
る。

【００４７】５ビット２進加算器５７８は、遷移画素の
アドレスを確定するために使用される。ＣＰｘ_sign ＣＰｘＦ３ＣＰｘＦ２ＣＰｘＦ１ＣＰｘＦ０＋ｄｘ′_sign ｄｘ′３ｄｘ′２ｄｘ′１ｄｘ′０ ──────────────────────────────────── ＝Ｉ_sign ＩＰｘＦ３ＩＰｘＦ２ＩＰｘＦ１ＩＰｘＦ０従って、比較器５８０の２つの出力信号はＩＰｘＦ３に
等しい「ｒｉｇｈｔ＿ＩＴ」と、ＣＰｘ_signとＩ_signの
排他的論理和に等しい「ＮＸ＿ＩＴ」とである。ＮＸ＿
ＩＴは、ＴＸｘがＮＸｘに相対している場合は１に設定
され、ＴＸｘがＣＸｘに相対している場合には０に設定
される。信号「ｒｉｇｈｔ＿ＩＴ」は、ＴＸｘがＣＸ又
はＮｘのすぐ右側の画素である場合は１に設定され、Ｔ
ＸがＣＸ又はＮＸである場合には０に設定される。

【００４８】図３６に示される出力装置５２２は、信号
線５４０の入力データとして１２ビット整数項ＣＰｘ
Ｉ，ＮＰｘＩ，ＣＰｙＩ及びＮＰｙＩを使用してＣＸ又
はＮＸに関して遷移アドレスＴＸを選択するために必要
な論理を含む。走査線が所定のポリセグメントと交差す
る場合、遷移画素ＴＸｙのｙ座標はＣＸｙ又はＮＸｙの
いずれかと等しく、一方、遷移画素ＴＸｘのｘ座標はＣ
Ｘｘ，ＣＸｘ＋１，ＮＸｘ又はＮＸｘ＋１に等しい。先
に指示した通り、ＴＸｙはＤＴ装置（ＮＸ＿ＤＴ信号）
からの入力５３２によってのみ確定される。信号線５３
０の入力「ｄｅｔｅｒｍｉｎｉｓｔｉｃ」が１に等しけ
れば、ＴＸｘをＤＴ装置により信号線５３２の入力「Ｎ
Ｘ＿ＤＴ」と、信号線５３４の「ｒｉｇｈｔ＿ＤＴ」と
を経て確定できる。そうでない場合には、ＴＸｘはＩＴ
装置により信号線５３６の入力「ＮＸ＿ＩＴ」と、信号
線５３８の「ｒｉｇｈｔ＿ＩＴ」とを経て確定される。
マルチプレクサ５９０〜５９６は適切な入力信号を選択
するために使用され、１２ビット加算器５９８は、ＴＸ
ｘがＣＸｘ＋１又はＮＸｘ＋１に等しいとき、その入力
オペランドの値に１を加算する。

【００４９】図形オブジェクトの全ての遷移画素を確定
した後、パリティ充填エンジン５１４によりパリティ走
査線充填方式を使用して内側の充填を実行することがで
きる。すなわち、１対の遷移画素のうち第１の遷移画素
から始めて、第１の遷移画素を含めた画素に黒色を書込
み、１対の遷移画素のうち第２の遷移画素から始めて、
第２の遷移画素を含めた画素に白色を書込む。レーザー
プリンタ又は表示装置における文字生成プロセスをスピ
ードアップする装置に関して本発明を説明したが、プロ
ッタ，植字装置又は他の同様の装置などの他のドットマ
トリクス装置にも本発明を実現できることは当業者には
理解されるであろう。従って、特許請求の範囲は本発明
の真の趣旨の中に含まれるあらゆる変更，変形及び用途
を対象にするものである。

【図面の簡単な説明】

【図１】Ｂｒｅｓｅｎｈａｍの走査−変換方法と、本発
明の適応制御を伴う垂直走査−変換方法とを比較して示
す図。

【図２】Ｂｒｅｓｅｎｈａｍの走査−変換方法と、本発
明の適応制御を伴う垂直走査−変換方法とを比較して示
す図。

【図３】Ｂｒｅｓｅｎｈａｍの方法と、本発明の垂直走
査−変換方法とから得られる画素配列を示す拡大図。

【図４】Ｂｒｅｓｅｎｈａｍの方法と、本発明の垂直走
査−変換方法とが境界セグメントに沿って画素の色（黒
色又は白色）をいかにして確定するかを示す図。

【図５】活字の形状を近似するためにスプラインをいか
にしてより小さなポリセグメント片に分解するかを示す
図。

【図６】走査線とポリセグメントとの交差点の位置を規
定することにより遷移画素を確定する方法を示す図。

【図７】遷移画素を識別した後の充填の結果を示す図。

【図８】様々な長さのポリセグメントによって充填され
た文字を示す図。

【図９】長さが全て１つの画素の対角線より短い正規化
ポリセグメントによって充填された文字を示す図。

【図１０】ｘ，ｙ座標系における画素単位の定義を示す
図。

【図１１】ｘ，ｙ座標系における画素単位の定義を示す
図。

【図１２】象限及び境界の定義を示す図。

【図１３】象限及び境界の定義を示す図。

【図１４】ポリセグメントの動きの規約を示す図。

【図１５】ポリセグメントの動きの方向を示す図。

【図１６】現在画素（ＣＸ）と考えられる９つの次画素
（ＮＸ）の場所の関係を、象限及びポリセグメントの方
向の概念と、デシジョンテーブルの情報をいかにしてＮ
Ｘ象限に記憶するかということと共に示す図。

【図１７】デシジョンテーブルエントリの可能な全ての
決定の型を示す図。

【図１８】ポリセグメントの型と、それに関連する決定
カテゴリのいくつかの例を示す図。

【図１９】ポリセグメントの型と、それに関連する決定
カテゴリのいくつかの例を示す図。

【図２０】ポリセグメントの型と、それに関連する決定
カテゴリのいくつかの例を示す図。

【図２１】ポリセグメントの型と、それに関連する決定
カテゴリのいくつかの例を示す図。

【図２２】ポリセグメントの型と、それに関連する決定
カテゴリのいくつかの例を示す図。

【図２３】ポリセグメントの型と、それに関連する決定
カテゴリのいくつかの例を示す図。

【図２４】ポリセグメントの型と、それに関連する決定
カテゴリのいくつかの例を示す図。

【図２５】完全なデシジョンテーブルのレイアウトを示
す図。

【図２６】ポリセグメントの動きデータをいかにして、
どこに記録するかの１例を示す図。

【図２７】図２６に示したのと同じ例のデシジョンテー
ブルとの対照検査後の結果を示す図。

【図２８】１つの境界条件と、それに対する特別の規則
を示す図。

【図２９】１６ビットデータ語のフォーマットを示す
図。

【図３０】画素スペースを表わすためのシステムを示す
図。

【図３１】本発明に従った輪郭字体文字発生器の実現形
態を示すブロック線図。

【図３２】図３５のデシジョンテーブルを具体化した真
理値表を示す図。

【図３３】図３２の真理値表を論理回路に設計した場合
を示す図。

【図３４】走査線−ポリセグメント交差点の場所を規定
するために使用される数学的方法を示す図。

【図３５】ＩＴ装置の論理回路構成を示す図。

【図３６】図３１に示した出力装置の主要な機能素子を
示すブロック線図。

【符号の説明】

５００輪郭字体文字発生器５０２正規化ポリセグメント生成エンジン５０８垂直走査変換エンジン５１４パリティ充填エンジン５１８デシジョンテーブル遷移器（ＤＴ）装置５２０交差点遷移器（ＩＴ）装置５２２出力装置

フロントページの続き (72)発明者ジェイムズ・シイ・ワイ・ラングアメリカ合衆国 95129 カリフォルニア州・サンホゼ・キャスルグレンアヴェニュ・5574

Claims

【特許請求の範囲】

【請求項１】スプライン輪郭フォーマットの画像デー
タをドットマトリクス印刷装置及び／又はドットマトリ
クス表示装置を駆動するのに適するビットマップ化デー
タに変換する装置において、スプラインデータを、各ポリセグメントの長さが印刷又
は表示すべき１つの画素の寸法に対して所定の関係を有
するような正規化ポリセグメントデータに変換する正規
化ポリセグメントデータ生成手段と；前記正規化ポリセ
グメントデータに応答して、１列分の画素の中の各画素
の特定の１点を通過する基準線と交差する各ポリセグメ
ントに対して、データ状態の遷移が起こる画素として定
義される遷移画素の場所を規定する遷移画素データを発
生するように動作する垂直走査変換手段と；前記遷移画
素データに応答して、それに対応するビットマップ化デ
ータを生成するように動作するパリティ走査充填手段と
を具備する装置。
【請求項２】スプライン輪郭フォーマットの画像デー
タをドットマトリクス印刷装置及び／又はドットマトリ
クス表示装置を駆動するのに適するビットマップ化デー
タに変換する方法において、スプラインデータを、各ポリセグメントの長さが印刷又
は表示すべき１つの画素の寸法に対して所定の関係を有
するような正規化ポリセグメントデータに変換する過程
と；前記正規化ポリセグメントデータを使用して、１列
分の画素の中の各画素の特定の１点を通過する基準線と
交差する各ポリセグメントに対して、データ状態の遷移
が起こる画素として定義される遷移画素の場所を規定す
る遷移画素データを発生する過程と；前記遷移画素デー
タを使用して、それに対応するビットマップ化データを
生成する過程とから成る方法。