JPH0535250A - 連結連なり（ラン）を使用して小さなサイズの文字ビツトマツプを編集する方法 - Google Patents

Abstract

(57)【要約】 【目的】 小さな文字を正確に表示する。 【構成】 文字を１つ又は複数の経路によって記述する
ようにしてラスタ−装置に文字を表示する方法。経路が
水平画素中心線と交差する交点を識別し、走査線の順に
交点対として２つ１組とする。交点対から画素の連なり
を識別する。画素の２つの連なりの間で衝突を識別し、
文字の完全性を維持しつつ衝突を除去するために修正動
作を実行する。最も一般的な修正動作は、衝突に関わる
画素の中の１つ又は２つ以上を移動又は削除するという
ことである。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】最新のコンピュータシステムで
は、様々な大きさの文字を紙やフィルムにプリントする
か、又はコンピュータのスクリーンに表示することが望
ましい。表示装置又は印刷装置の分解能に比して文字が
大きい場合、読取り可能な文字を形成するためにどの画
像要素、すなわち画素を印刷又は表示すべきかを選択す
るのは相対的に容易であるが、表示装置の分解能に対し
て文字が小さいときには、文字をできる限り明確に且つ
認識可能にするためにどの画素を表示すべきかを選択す
ることははるかに難しくなる。本発明は、低分解能で文
字を読みやすく表示する改良された方法に関する。

【０００２】

【従来の技術】従来は、微妙な曲線や、非常に細い線を
含めて、文字をきわめて詳細に描出できる金属活字を使
用して文字を印刷していた。文字は英数字、東洋系の外
国語文字又は他の外国語文字であって良く、さらには奇
抜なデザインのものでも良い。また、印刷できるポイン
トの大きさも様々である。最新のコンピュータ装置で
は、ビデオ表示端末装置又はラスター印刷装置などのラ
スター装置で文字を規定するか、あるいはマルチピンプ
リントヘッドを使用することにより文字を規定する。文
字は、その文字の理想の形状にできる限り近く似せるた
めに印刷又はターンオンされる一連のドットとして面に
印刷されるか又はビデオスクリーンに表示されることが
可能である。表示装置の分解能に比して文字が十分に小
さい場合、文字を正確に表示するためにどの画素を選択
すべきかを選択するのは、文字が大きいときよりも複雑
になる。代表的なビデオモニターは１インチ当たり約７
２画素を表示できる。この分解能では、約２０画素の高
さもない大半の活字面を読みやすく表示することは困難
である。

【０００３】文字の理想の表示は、通常、非常に高い分
解能の「文字スペース」で輪郭線又は経路により境界を
限定された１つ又は複数の領域として規定される。１つ
の文字は１つ又は複数の連続する黒色領域から構成され
る。たとえば、文字「Ｏ」は１つの閉じたループから構
成されており、文字「ｄ」は線に接続するループから構
成され、文字「ｉ」は、セリフなどの追加の詳細な特徴
を有することもある線からわずかに離間する点という本
質的構成を有する。文字を記述する方法の１つは、文字
の連続する黒色部分それぞれの外縁部の輪郭を規定し、
次に、その輪郭を充填して文字を表示することから成
る。通常、文字は明るい背景の上に暗色のインクで印刷
されるので、充填領域を黒色として表すことができる
が、本発明の方法を、ビデオ表示装置で一般に使用され
ているような暗い背景の色の明るい文字を含めて、数多
くの充填方法の中のいずれかを使用して表示するために
どの画素が候補となるかを確定するために使用できるこ
と、又は異なる色をもつ背景の上の文字も本発明の教示
の中に含まれることは当業者には認められるであろう。
輪郭を１つ又は複数の経路として規定するのが好まし
く、それぞれの経路は、通常、時計回り又は反時計回り
の一方向に追跡される。続いて現れる一連の曲線及び／
又は辺と呼ばれる直線線分として各経路を表すことがで
きる。たとえば、文字「Ｏ」のように黒色領域が内側に
白色スペースを有している場合、それぞれの内側白色ス
ペースを一連の辺から成る経路として規定することもで
きる。

【０００４】文字をラスター装置に表示するときには、
その文字の黒色領域に含まれる画素を表示すべきであ
る。すなわち、それらの画素を面に印刷すべきである
か、又はビデオ表示のためにターンオンすべきである。
分解能が高いか、又は文字が非常に大きい場合、それぞ
れの黒色領域に複数の画素が入っていると考えられ、文
字をごく詳細に表示することが可能である、ところが、
文字を小さく縮小するとき、又は装置の分解能が限定さ
れているときには、黒色領域のいくつかは複数の画素を
包含しなくなり、実際には、１つの画素の一部分にしか
かからないというようなことも起こりうる。分解能が限
定されている装置に小さな文字を表示することは、これ
まで一貫して難問となってきたのである。このことを図
１〜図８には文字「ｎ」，「ｓ」及び「ｅ」の６×７マ
トリクスにおける輪郭により示し、図９、図１０にはイ
タリック体の文字「ｅ」の８×８画素マトリクスにおけ
る輪郭によりそれぞれ示してある。図９では、文字
「ｅ」の輪郭を非常に高い分解能で充填した場合（淡灰
色）と、低い分解能で充填した場合（暗灰色）とを示し
ている。しかしながら、ラスター表示装置は暗灰色に対
応する画素全体をオン／オフすることしかできない。

【０００５】この問題を解決しようとした従来の方法の
１つは中心点充填方式と、１９９０年６月１５日に同じ
発明者が名称「Connected ‐Run Dropout‐Free Center
Point Fill Method For Displaying Characters」の下
に出願した同時係属出願に記載されている改良充填方式
である。数多くの充填方式に関連して起こる問題は、文
字の特徴のいくつかがごく近接して現れることがあると
いう点である。表示装置の分解能が低くなると、選択し
た画素充填方式によっては、実際には接触してはならな
い文字ビットマップの部分を互いに接触させてしまう画
素をターンオンするときがある。その結果、文字の形状
に誤りが発生して、読みやすさの点で著しい欠陥が生じ
る。たとえば、図１，図２及び図３の場合、「ｎ」は脚
部の間に開いたスペースを置くのではなく、底の部分で
閉じてしまっており、また、「ｅ」と「ｓ」の曲線部分
は文字の本体に共に接触して、ビットマップを小さな
「８」のように変えている。図７では、イタリック体の
「ｅ」はｅとは読みにくい。

【０００６】これらの問題を解決する方法の１つは、名
称「Method For Editing CharacterBitmaps at SmallSi
zes 」の米国特許出願第０７−３８８，３３９号に記載
されている。この出願は、中心点充填などの充填規則の
１つを使用して文字の輪郭に従ってどのように画素をタ
ーンオンするか、また、文字を不適正に閉鎖させる画素
をターンオフするか又は移動させることにより表示をど
のように修正するかを説明している。本発明は、文字を
不適正に閉鎖させる画素をターンオフするか又は移動さ
せることにより表示を修正するさらに高速の方法を提供
する。

【０００７】

【発明が解決しようとする課題】本発明の１つの目的
は、小さなサイズで文字をさらに読みやすくするために
文字の外見を修正することである。本発明の別の目的
は、そのような修正のための高速の方法を提供すること
である。

【０００８】

【課題を解決するための手段】本発明は、（１）経路の
形態により確定される順序で画素の連なり（ラン）を数
えあげ、（２）文字ビットマップの中で他の連なりと不
適正に接触する連なりである衝突を探索し、（３）ビッ
トマップをクリーンアップして、そのような不正確な接
点を決定することにより、文字ビットマップの中のいく
つかの形態上の誤りを検出し且つ位置決定する方法を詳
細に説明する。

【０００９】文字ビットアップは、接触すべきではない
にもかかわらず２つの連なりが接触する場所である衝突
を識別し、次に、文字をさらに読みやすく表示するため
に１つ又は複数の画素を移動又は削除することにより、
「クリーンアップ」される。通常、この手順は、従来の
技術に記載されている中心点充填、水平近接充填、連な
り（ラン）連結充填及びＸ屈曲充填などの１つ又は２つ
以上の充填方式を使用して表示するために文字を準備し
た後に実行される。たとえば、１９９０年６月１５日に
同じ発明者が名称「Connected Run Dropout‐Free Cent
er Point FillMethod for Displaying Characters」の
下に出願した米国特許出願を参照。

【００１０】

【実施例】輪郭を利用して文字を表示する概念について
は先に説明した。文字は、背景との間で対比を成す一連
の充填領域によって表示できる。ここでは、便宜上、充
填領域をページ上にインクで印刷した場合のように黒色
領域と呼ぶが、当業者であれば良く知っている数多くの
方法により領域を充填することが可能である。また、黒
色領域にある画素及び画素のランを便宜上「表示する」
ものと説明しているが、実際には、本発明の方法は後に
所望の充填方式を使用して表示するのに備えて画素を選
択する。この明細書に関する限り、黒色領域を完全に充
填するものと仮定し、選択した全ての画素が表示され
る。

【００１１】各黒色領域の輪郭は、順次続いてゆく一連
の曲線又は辺と呼ばれる直線線分から成る閉じた経路に
より規定できる。文字の最大幅の部分を通る任意の方向
へ１点から１本の線を引き、経路との交差の数をカウン
トすることにより、文字の内側部分を背景と区別するこ
とができる。交差の数が奇数であれば、点は文字の中に
あり、数が偶数であれば、点は文字の外にある。先に説
明した通り、文字「Ｏ」のように白色スペースを内包し
ている文字は、そのような内包スペースを規定するため
に、一連の辺から成る追加経路を少なくとも１つ有す
る。文字「ｉ」又は多くの東洋系文字のように、文字は
２つ以上の黒色領域を含んでいても良い。文字について
１つの経路又は一連の経路を規定したならば、その経路
を、たとえば、コンピュータメモリに記憶し、任意の大
きさの文字を表示するために使用することができる。

【００１２】文字の充填 表示スペースと呼ばれることが多い規定の画素領域に文
字を表示するときには、まず、当業者であれば良く知っ
ている方法によって文字の輪郭をスケーリングし、画素
格子の中に配置しなければならない。図７を参照し説明
すると、この場合には、一般に「中心点充填」として知
られている周知の方式に従って、たとえば、画素Ｂ２及
びＢ４のように、中心が文字の輪郭の上にあるか又は輪
郭の内側に入っている画素を選択し、表示している。文
字の大きさに比して表示装置の分解能が相当に低いとき
には、文字のある部分は画素の中心を含まないために
「脱落する」。すなわち、それらの部分は表示されなく
なるので、文字の読みやすさは低減する。図７の場合、
たとえば、画素Ｅ５はたまたま文字の輪郭の内側に含ま
れていないので、表示されず、文字を読みにくくしてい
る。文字のうち、水平中心線とは交差するが画素の中心
を含まない黒色部分を識別することにより、そのような
脱落を検出できる。そして、その水平中心線に沿った辺
に最も近接している画素を表示することにより、脱落を
修正できる。水平近接充填試験を実行する方法は、１９
８９年８月１日に出願され且つ本出願と同一の譲受人に
譲渡された米国特許出願第０７−３８８，３３６号と、
１９９０年６月１５日に本発明の発明者により出願され
且つ同様に同一の譲受人に譲渡された出願「Connected
‐Run Dropout‐Free Center Point Fill Method For D
isplaying Characters」とに記載されている。２番目に
挙げた出願は、連なり連結充填と、Ｘ極値充填という２
つの付加的な充填方式をさらに説明している。

【００１３】上述の方式の好ましい実現形態では、文字
を所望の表示スペース用の画素格子に適合するようにス
ケーリングすると共に、曲線を１つの経路に沿って順に
一連の連結する直線状の辺として平坦化する。〔たとえ
ば、Steven Harrington の「Curves and Fractals 」第
１１章 （Computer Graphics, A Programming Approach
第２版，McGraw‐Hill出版，１９８７年刊）を参
照。〕それぞれの経路を一方向（時計回り又は反時計回
り）に追跡し、交点を辺が画素を中心を通る水平中心線
と交差する点として識別する。辺の終端の点がたまたま
水平中心線の真上に位置している場合には、辺の終点が
交差の点とならないように、終点を上又は下へわずかに
動かす。交点を経路リストに、経路の順番に従って記憶
する。Ｘ極値である辺の終点も識別する。好ましい実現
形態では、Ｙ極値である辺の終点をも識別し、交点と、
Ｘ極値及びＹ極値とを同じ経路リストに含める。当業者
であれば、経路をさらに正確に表すために、経路リスト
にさらに別の終点を含めようとするかもしれない。

【００１４】各走査線における交点の順序を確定し、走
査線の順番に従ってリストとして記憶する。文字の黒色
部分が水平中心線と交差する場所を識別しやすくするた
めに、各走査線における交差を２つ１組にして、「交点
対」を形成する。たとえば、図７で、水平走査線Ｄは画
素Ｄ２の中に１つの交点対を含み、画素Ｄ３と画素Ｄ４
の中の１回ずつの交差から成る第２の交点対を含む。こ
の表示方法の目的は、交点対ごとに１つ又は２つ以上の
水平方向に隣接する画素の連なり（ラン）を確定し、次
に、文字を一連の連結した連なりとして表示するため
に、必要に応じて順に連なりを修正するか、又は連なり
を追加することである。便宜上、連なりを始まりの画素
と、終わりの画素により、たとえば、Ｂ２−Ｂ２又はＢ
３−Ｂ４のように表すことができる。

【００１５】中心点充填方式により画素を表示するとき
には、各交点対を試験し、画素Ｄ２又はＤ３のように、
画素の中心点が交点対の中に入っているか、又は交点と
交差する場合には、その画素を表示する。これにより、
ほとんどの交点対が連なりとして表示されている。図７
の画素Ｅ５及びＥ６のように、交点対が２つの隣接する
画素の中心の間に位置している場合、好ましい実現形態
は交点対の中間点を確定し、その交点対について、その
中間点を含んでいるほうの画素１つの連なり（中心が中
間点により近接しているほうの画素）を表示する。この
プロセスを水平近接充填方式と呼ぶ。中心点充填と水平
近接充填を実行した後、各交点対を少なくとも１つの画
素から成る連なりによって表示する。

【００１６】水平近接充填方式では捕らえられない脱落
もいくつかある。それは、文字の黒色部分が画素の中心
と交差せずに垂直中心線と交差する場合である。米国特
許出願第０７−３８８，３３６号は、そのような脱落を
修正するために水平近接充填試験の変形を使用すること
を含めた方法を説明している。好ましい実現形態では、
１９９０年６月１５日に同じ発明者が出願した同時係属
出願「Connected ‐Run Dropout‐Free Center Point F
ill Method for Displaying Characters 」 に詳細に記
載されている連なり連結充填方式及びＸ極値充填方式に
より、そのような脱落を修正する。

【００１７】連なり連結充填の場合、各交点対をそれぞ
れ隣接している交点対と比較し、隣接する交点対と関連
する連なりを試験して、それらが適正に連結している
か、すなわち、画素の縁に沿って画素同士を接触させて
いるのか又は画素の角で接触させているのかを知る。隣
接する交点対は、対に含まれているそれぞれの交点と関
連する経路を追跡し、各経路に沿った先行交点と、後続
交点とを識別し、それらの交点のそれぞれについて交点
対を見出すことにより識別される。隣接する交点対と関
連する連なりを隣接連なりという。図７に関していえ
ば、交点対１１４−１０３は、２つの隣接する交点対を
有する。経路の順（右回り経路に基づく）にたどると、
交点１１４の次には交点対１０１−１０２の一方である
交点１０１があり、前には交点対１０４−１１３の一方
である交点１１３がある。交点１０３の次には交点１０
４があり、前には交点１０２があるので、交点対１１４
−１０３は２つの隣接交点対１０１−１０２及び１０４
−１１３を有していることになる。交点対１０１−１０
２に隣接する交点対は１つしかない。交点対を試験する
順序としては多くのものが考えられる。本発明の好まし
い形態においては、走査線を順に検査し、各交点対をそ
れが現れる順に試験してゆく。垂直方向に一度だけ、水
平方向に一度だけ目を通せば、同じ２つの隣接交点対の
重複試験を回避できることは当業者には認められるであ
ろう。また、たとえば、文字の形状を１つのＹ極値から
次のＹ極値へとたどることにより交点対を検査できるこ
とも当業者にはわかるであろう。試験すべき交点対の上
方にある又はその右側にある隣接交点対に対して適正に
連結しているか否かを知るために、各交点対を試験す
る。たとえば、図７において、走査線Ｂの最初の交点対
は１０４−１１３であるので、それを上方の画素Ｃ１及
びＣ２にある隣接交点対と、右側の隣接交点対１１４−
１０３とに対して試験する。

【００１８】現在交点対を表示している連なりが隣接交
点対を表示している連なりに連結しているか否かを知る
ために試験を実行する。一方の連なりの中の少なくとも
１つの画素が他方の連なりの中の１つの画素と一辺又は
１つの角を共有する場合、それら２つの連なりは連結し
ている。好ましい実現形態では、画素は正方形であると
考えるが、正方形でない画素の連なりを試験する方法は
当業者には自明であろう。

【００１９】隣接する走査線にあって、１つ又は複数の
表示されない画素によって分離されている２つの隣接連
なりは適正に連結しておらず、その脱落は次の節で説明
する方法を使用して修正される。

【００２０】同じ走査線にあるが、１つ又は複数の表示
されない画素によって分離されている２つの隣接連なり
は、それでも、文字の連続部分により連結していると考
えられる。好ましい実現形態では、そのような２つの隣
接連なりと「隣り合う」連なりがそれらの間に連結を完
全に成立させているならば、２つの隣接連なりは連結し
ていると考える。２つの連なりの一方に関わる交点対の
１つの交点と、第２の連なりの交点対の１つの交点との
間に経路又は水平中心線と交差せずに曲線を描くことが
できるならば、それら２つの連なりは隣り合う連なりで
ある。たとえば、図１を参照すると、隣接連なりＥ２−
Ｅ２（画素Ｅ２の中心が交点対の中に入っている交点対
１４−１５に関わる）とＥ５−Ｅ５（交点対１６−１７
に関わる）は直接には連結していないが、隣り合う連な
りＦ１−Ｆ３（たとえば、交点１０から交点１７又は交
点１４へ水平中心線又は経路と交差せずに線を引くこと
ができる）及びＦ４−Ｆ５を通して連結している。そう
でない場合には、脱落に注目し、以下に説明する方法を
使用してその脱落を修正する。

【００２１】脱落の位置確定 脱落は、既にある連なりを延長するか又は新たな連なり
を作成することにより位置確定される。適正に連結して
いない連なりを連結するときには、２つの走査線を検査
し、いずれかの経路と、それぞれ脱落した画素を含む列
を通る垂直中心線との、垂直交差と呼ばれる交差を識別
する。各列における交差を垂直方向に順に配置し、垂直
中心点を含む１つ又は複数の適切な画素を、必要に応じ
て既にある連なりを延長するか又は新たな連なりを追加
することによって表示する。

【００２２】脱落を位置確定するために、２つの隣接す
る走査線を選択し、順に解析しなければならない。脱落
は同じ走査線にある２つの連なりの間又は隣接する走査
線にある２つの連なりの間に起こりうると考えられる。
隣接する走査線にある連なりの間で脱落が起こっている
場合、それら２つの走査線を使用して次の試験を実行す
る。同じ走査線にある連なりの間で脱落が起こった場合
には、それらの連なりを連結する経路は、いずれも、必
然的にその走査線の水平中心線の上又は下に行く。最も
内側にある交点の間の経路を試験することにより、その
方向を確定し、交点対を含む走査線と、経路により指示
される方向の隣接する走査線とを次の試験を使用して検
査する。たとえば、図７においては、交点対１０５−１
１１及び１１０−１０８の間の経路は交点１０５，１１
１，１１０及び１０８のそれぞれで上へ移り、そこで、
現在走査線Ｆと、上方の走査線Ｇとを関心走査線として
選択し、以下に説明するようにして試験する。

【００２３】関心走査線にある交点の間のあらゆる経路
部分を追跡して、脱落した画素を含む各列を通る垂直中
心線との垂直方向交点に注目する。最も低い経路に沿っ
た最も高い位置の交点と、最も高い経路に沿った最も低
い位置の交点とを特定関心交点として取出し、それら２
つの交点の中間点を見出し、その中間点を含む画素を表
示のために選択し、必要に応じて、たとえば、中間点が
画素境界線にあった場合には、順位決定試験を適用す
る。

【００２４】検査すべき交点対の連結を完了するために
は、可能であれば先に存在している連なりと共に表示す
べき各画素を含めて、１つ又は複数の連なりを幾分調整
することが要求される。連なりの選択と変更は、それぞ
れ新たに表示される画素の中心線に対する各交点の近接
度に目を向ける；常に１つの交点、たとえば、最も左側
の交点を任意に選択する；又は他の適切な試験を実行す
るなどのいくつかの方法の中の１つまたは２つ以上を使
用して実行可能であることは、当業者には明かであろ
う。

【００２５】表示すべき画素を既にある連なりに連結で
きない場合には、新たな交点、すなわち擬似交点を規定
し、２つ１組にする。擬似交点は表示すべき画素を通る
水平中心線にあるべきであり、既にある交点対と重複し
ていてはならない。好ましい実現形態では、擬似交点を
表示すべき画素の水平中心線上で、その画素の垂直中心
線のそれぞれの側に１つおきに、垂直中心線から１画素
単位の二分の一未満離間した、好ましくは相対的に垂直
中心線に近接する位置に形成する。この配置が既にある
交点対と重複する場合には、その重複を避けるように擬
似交点対の位置を調整する。擬似交点対を走査線の順に
含めて、新たな画素を含む連なりを表示する。表示すべ
き２つ以上の画素から成る連なりを単一の擬似交点対に
よってマークすることができる。複雑な形状の場合は、
脱落を位置確定し且つ表示するために、２つ以上の擬似
交点対が必要であろう。本発明の実現に際しては、以下
に説明するように、文字の経路の順に新たな擬似交点を
含めてゆく。

【００２６】極値 文字の中には、分解能が低いとき、上述の充填方式だけ
を使用したのでは容易に表示できないような幅の狭い水
平方向形状を含むものがある。（水平方向）Ｘ極値―デ
ルタＸが符号を変える点を識別するために、スケーリン
グ済み文字、すなわち、所望の表示スペースの画素格子
に合わせてスケーリングした文字を検査する。デルタＸ
は経路に沿った点ごとのＸの変化であり、Ｘが局所水平
方向最大値又は最小値に行き当たるたびに符号を変え、
そこから逆方向に動き始める。デルタＸが０になったと
き又はデルタＸが０ではなくなったとき―これは、垂直
方向形状の最上点及び最下点に相当する―にも、Ｘ極値
はマークされる。しかしながら、Ｘ極値は劇的に変化す
る形状を含んでいる必要はない。たとえば、図７の文字
は、画素Ｄ５及びＦ６に最大Ｘ極値１３０，１３１及び
１３２（Ｆ６には２つ入っている）を含み、画素Ｄ３，
Ｃ１及びＣ２には最小Ｘ極値１３３，１３４及び１３５
をそれぞれ含んでいる。好ましい実現形態では、交点を
識別するときにパスの中でＸ極値を識別し、別個のリス
トに極値を経路の順に記憶する。好ましい実現形態にお
いては、辺終点及び交点のリストの中に極値を入れた。

【００２７】文字を適正に表示するために、まず、先に
説明した中心点充填、水平近接充填及び連なり連結充填
を実行する。後続するパスの中で、表示されている連な
りへの適正な連結の可否を知るため、それぞれの極値を
検査する。各極値を通る経路を順方向及び逆方向に追跡
して、経路の順に最も近い隣接連なりを識別する。極値
が隣接連なりから二分の一画素以内の距離にあれば、そ
れ以上の処理は不要であり、その極値は無視される。

【００２８】その極値から両方向に見て最も近い交点対
までの経路を順方向に追跡し、最も近い隣接連なりと極
値との間の垂直中心線との交差を識別することにより、
残る極値を解析する。先に連なり連結脱落充填方式に関
して説明した通り、各列の垂直交差を順序付けし、中間
点を識別し、既にある連なりを延長し及び／又は擬似交
点対を形成して、新たな連なりを追加することにより１
つ又は複数の画素を表示する。

【００２９】従来の技術との相違点 本発明は、脱落の位置確定に関して、従来の方式より限
定的な処理を必要とする。従来の方式では、既にある連
なりを延長するか、又は必ずしも輪郭の一部であるとは
限らない擬似交点を形成することにより、脱落を位置確
定させていた。本発明によれば、それぞれの連なりをそ
れに隣り合う全ての連なりに連結しなければならない。
すなわち、隣り合う連なりのみを延長（又は形成）する
ことにより脱落を位置確定しなければならない。脱落を
位置確定するための連なりの延長は、全ての連なりでは
なく、隣り合う連なりのみを選択するという点を除い
て、従来と同じ方法を利用して実行される。

【００３０】本発明において新たな連なりを形成すると
きには、従来の方式で擬似交点を形成していたのと同じ
方法を使用して新たな交点対を形成しなければならな
い。その新たな交点対を含む新たな垂直迂回部分によっ
て経路を修正しなければならないのであるが、これは、
新たな交点対が脱落を伴う元の連なりに対して隣り合う
連なりとなるように実行されなければならない。好まし
い実現形態では、元の２つの連なりを連結する経路部分
に垂直迂回部分を追加するか、又は隣り合う連なりを連
結する経路部分と共に垂直迂回部分を含める。これらの
追加経路迂回部分は、垂直交差を確定するときには飛越
しできるように全てマークされている。これにより、連
なり連結充填方式で脱落を位置確定するに際して正しい
画素をさらに正確に補間することができる。

【００３１】たとえば、図７で、元の経路（図示せず）
は走査線Ｇの中心線と交差していなかった。Ｇ５は隣接
連なりＦ３−Ｆ４及びＦ６−Ｆ６の間で脱落していた
が、その脱落は連なり連結充填方式により充填されてい
る。同じ発明者による同時係属出願に記載されている従
来の方法を使用して、擬似交点対１０６−１０７を形成
した。本発明では、３つの点が経路に追加されている。
そのうち２つは交点１０６及び１０７である。第３の点
は、経路の垂直迂回部分を完成するために、それらの交
点の上方に追加された点である。

【００３２】衝突 脱落を充填したならば、クリーンアッププロセスを開始
することができる。衝突は、隣り合う連なりではない２
つの連なりの望ましくない接触である。衝突は３つの異
なる方法により識別される。第１の方法は、一辺で接触
している同じ走査線上の連なりの有無を検査する。本発
明に関する限り、「接触」は２つの連なりが画素の共通
の一辺を共有すること（辺接触）又は画素の一角で互い
に接触すること（角接触）を意味する。図７に関してい
えば、連なりＤ２−Ｄ２と、連なりＤ３−Ｄ４は画素Ｄ
２と画素Ｄ３との間で画素の辺で接触しているので、衝
突を構成することになる。

【００３３】衝突を発見する第２の方法は、（ａ）同一
の走査線上に双方の交点がある場合及び（ｂ）２つの交
点のうち最も左側のものがその交点対の最も左側の交点
であり、２つの交点のうち最も右側のものはその交点対
の最も右側の交点である場合に、経路の順にそれら２つ
の交点の間の全ての経路部分を発見する。たとえば、画
素Ｃ５にある交点１０１及び１０２は経路の順に隣接し
ており、この試験の基準に適合している。画素Ｂ２の交
点１０４と、画素Ｂ４の交点１０３もこの基準に適合し
ている。関心連なりは１つ又は２つある。双方の交点が
同じ交点対にあれば、単一の関心連なりがその交点対を
表示する連なりである。双方の交点が同じ交点対にない
場合には、関心連なりは２つある。それらは、交点の各
々をそれぞれ含んでいる各交点対を表示する２つの連な
りである。２つの交点の、それらを含む経路部分と同じ
側にある隣接する走査線を、他の連なりに関して検査す
る。関心連なりの１つと接触する隣接する走査線上の各
連なりとの衝突が存在する。たとえば、図７で、連なり
Ｄ３−Ｄ４は画素の角で連なりＣ５−Ｃ５と接触する。

【００３４】衝突を識別する第３の方法は、連なりの間
の白色領域の連結性を検査する。それらの領域は、走査
行交点リストを使用して容易に確定できる「白色交点
対」を表示する「白色連なり」であると考えることがで
きる。この手順は、１つの走査線にある白色連なりを、
経路上で対応する白色交点対が隣接している隣接走査線
上の白色連なりと比較する。白色連なりが少なくとも１
つの辺を共有するならば、それらの連なりを連結する。
好ましい実現形態では、白色連なりの間に共通の角があ
るだけでは、それらの白色連なりを連結するには不十分
である。白色連なりを境界限定する連なりを検査し、経
路上で隣接してはいないが、接触し、隣接する白色連な
りにも水平方向に隣接する２つの連なりがあれば、それ
らの連なりは衝突するという。たとえば、連なりＥ３−
Ｅ４、連なりＦ５−Ｆ５とは経路の順に隣接している
が、画素の共通の一辺を共有していない。画素Ｆ６の交
点１１０は画素Ｅ５の交点１０９に隣接している。交点
１１１及び１１２は互いに隣接している。連なりＦ３−
Ｆ４は白色連なりＦ５−Ｆ５に水平方向に隣接してお
り、連なりＥ５−Ｅ５は白色連なりＥ３−Ｅ４に水平方
向に隣接している。連なりＦ３−Ｆ４と連なりＥ５−Ｅ
５は隣接していないが、１つの角で接触しているので、
それらの連なりは衝突を構成する。

【００３５】クリーンアップ 衝突が識別されれば、修正を試みる。衝突状態にある２
つの連なりを「侵害連なり」と呼ぶ。２つの侵害連なり
及び侵害連なりごとの隣り合う連なりの組の形状を使用
して、試みるべき修正動作を確定する。

【００３６】修正動作は、一方又は双方の侵害連なりに
ある画素を移動又は削除することから成る。修正動作は
隣り合う連なりの連結を決して断ち切ってはならない。
数多くの形状について、いくつかの異なる受入れ可能な
修正動作がある。第１の修正動作を試みても失敗する可
能性はあるので、文字中の特定の衝突について２回以上
の修正動作を試みる必要があるだろう。たとえば、画素
を上方へ動かすと、別の連なりと別の衝突を生じさせる
おそれがあり、また、画素を削除すると、別の衝突を発
生させずに衝突が修正されるかもしれない。

【００３７】いずれかの形状について使用する実際の動
作と、それらの動作を試みる順序は、文字の形状の他の
数多くの要因によって決まる。植字者の芸術上の目標、
たとえば、「画素移動」動作が「画素削除」動作より好
ましいか否かなどは重要である。実現形態の制限はある
役割を演じると思われる。たとえば、実現形態がクリー
ンアップ段階の間に新たな連なりを許さない場合には、
「画素移動」動作は制限されるであろう。他の要因も当
業者には明白であろう。

【００３８】本発明の好ましい実現形態は、重なり合わ
ない１つずつの画素の衝突に限定される。それに含まれ
る形状は次の通りである： ａ．同じ走査線にあって、一辺で接触するが重なり合わ
ない２つの連なり； ｂ．異なる走査線にあって、厳密に１つの角で接触する
２つの連なり；及び ｃ．異なる走査線にあって、一辺で接触し、少なくとも
一方の連なりが厳密に１画素の幅である２つの連なり。 本発明の好ましい実現形態はその他の衝突を処理しな
い。

【００３９】上記の条件の１つに適合する衝突につい
て、実際に接触している２つの画素は「侵害」画素であ
ると考えられる。このように、それぞれの衝突は１対の
侵害画素を含む。隣り合う連なりに含まれており、侵害
画素と一辺又は１つの角を共有する表示画素はその侵害
画素の「隣り合う画素」と呼ばれる。本発明のクリーン
アップ方法により削除された画素は、文字にさらにひず
みを生じさせるのを避けるように表示されなくなるので
あるが、尚、隣り合う画素であると考えられる。後に示
す実施例２を参照。

【００４０】解析している侵害画素ごとに、隣り合う画
素の位置と、対のうち他方の侵害画素の位置とを「隣り
合い画素マトリクス」と呼ばれる３×３マトリクスにマ
ッピングする。衝突を修正するために、解析中の侵害画
素について実行できる動作をマトリクスごとに選択し、
下記の一連の指針に従ってそれらの動作に相対「メリッ
ト」値を与える。可能である基本動作は侵害画素を削除
するか又は移動することである。移動は数多くの方向の
中の１つに向かって実行できるであろうが、上方，下方
又は側方であるのが好ましい。メリット値は、動作を試
行する順序を決定するために使用される。隣り合い画素
マトリクスごとに、選択した動作を対応する相対メリッ
ト値と共にデータベース又はルックアップテーブルに記
憶する。尚、侵害画素ごとに選択される動作はその対の
対応する侵害画素に隣り合う画素とは無関係である。こ
の記憶情報を最適化するために、たとえば、動作が選択
されないマトリクスを除外する、マトリクスのいくつか
の回転のみを記憶するなどの方法があることは当業者に
は明かであろう。

【００４１】実際の文字では衝突は次のように修正され
ている。侵害画素ごとに、隣り合い画素マトリクスを確
定し、次に、データベースからメリット値を含めた修正
動作を得る。その結果、双方のマトリクスについて選択
した動作の組合わせリストが作成される。動作をメリッ
ト値の順に、いずれかの動作が成功するまで試行する。
成功する動作がなければ、その衝突を無視する。いくつ
かの動作が同じメリット値を有している場合には、
（ａ）単にリストの次に記されている動作を試行する
か、（ｂ）元の文字における侵害画素の位置に基づいて
動作をピックアップするか、（ｃ）各動作が隣り合い画
素マトリクスの一部として含まれていない近傍の画素に
与える影響を評価するか、又は（ｄ）当業者が認識して
いない他の要因を評価することにより、１つの動作を選
択する。

【００４２】好ましい実現形態においては、特定の隣り
合い画素マトリクスに関する動作を選択するために次の
ような指針を採用した。（ａ）１つの連なりの両端から
それぞれ２つ以上の画素を削除することはできない（こ
れにより、水平に長い形状に対してクリーンアップが及
ぼす影響は最小限に抑えられる），（ｂ）画素は水平方
向又は垂直方向には移動可能であるが、斜めには動けな
い，（ｃ）画素は隣り合う画素に並んだ位置へのみ移動
できる（従って、新たな連なりを形成しない），（ｄ）
画素はまっすぐな形状を湾曲させるようには移動できな
い（まっすぐな形状を湾曲する形状に分裂させた後に文
字が見やすくなるというようなことは起こりえないであ
ろう），（ｅ）通常、形状に「切れ目」を作るように画
素を削除することはできない（たとえば、図１２の画素
Ｄ４は削除不可能である），（ｆ）単独の画素（隣り合
う画素をもたない画素）は削除不可能であり、移動され
ないのが好ましい（たとえば、小文字のｉの点を調整す
るときなどに、幾分かの移動が望ましい場合もある），
（ｇ）特定の隣り合い画素マトリクスについて、ある動
作が元の衝突と同程度に良くない別の衝突を発生させて
しまうと考えられる場合には、そのマトリクスに関して
はその動作を動作リストに含めない。

【００４３】好ましい実現形態では、選択した動作に関
するメリット値を選択するために次のような指針を採用
した： （ａ）移動動作は削除動作より高いメリットを与えられ
る。 （ｂ）ある形状の中央にある画素を移動するより、形状
の端にある画素を移動するほうが良い。 （ｃ）ある形状の中央にある画素を削除するより、形状
の最後の画素を削除するほうが良い。（中央の画素を削
除するときには、連なり間の連結を維持することも必要
である） （ｄ）衝突を発生させない動作は、衝突を残した動作よ
り高いメリットを与えられる。さらに、辺接触は少なく
とも角接触において修正されなければならない。あるい
は、動作は全く選択されない。

【００４４】たとえば、図７を参照すると、連なりＤ２
−Ｄ２は連なりＤ３−Ｄ４と接触している。画素Ｄ２と
画素Ｄ３は一辺で接触しているので、これらは侵害画素
である。画素Ｄ２は隣り合う画素Ｅ２及びＣ２を有し、
そこで、画素Ｄ２に関する隣り合い画素マトリクスは次
のようになる： ．ｘ． . ｘｔ . ｘ. マトリクス中、中心にある「ｘ」は関心侵害画素を表
し、「ｔ」は他方の侵害画素（Ｄ３）を表し、「. 」は
その他の画素（表示されるか否かは無関係）を表す。ま
た、関心侵害画素に隣り合う画素もｘにより表されてい
る。画素Ｄ３に関する隣り合い画素マトリクスは次のよ
うになる： ．．. ｔｘｘ ．．.

【００４５】Ｄ２の隣り合い画素マトリクスについては
動作は選択されなかった（中心の画素を削除すると、表
示される画素が断ち切られてしまい、また、中心の画素
を左へ動かすと、文字の直線部分がひずむと共に、尚も
２つの角衝突、すなわち、Ｃ２−Ｃ２とＤ３−Ｄ３との
衝突並びにＥ２−Ｅ２とＤ３−Ｄ３との衝突をさらに残
すであろう）。Ｄ３に関する隣り合いマトリクスでは、
中心の画素を削除する動作が可能である（侵害画素は連
なりＤ３−Ｄ４の端にある）。侵害画素Ｄ３を斜めに右
上又は左下に移動させることはおそらく可能であろう
が、そのような移動は一般に許容されるものとは見えな
いと思われ、この文字においても新たな接触を発生させ
るであろう。削除のメリットは相対的に低いのである
が、この動作を選択し、修正を実行するために利用し
た。図８に示すように、画素Ｄ３（白色画素として示さ
れている）を削除したので、連なりＤ３−Ｄ４は連なり
Ｄ４−Ｄ４に更新されている。

【００４６】連なりＤ４−Ｄ４（先の修正により更新さ
れた）と、連なりＣ５−Ｃ５も角で衝突している。侵害
画素はＤ４とＣ５である。それらに対応する隣り合い画
素マトリクスは次の通りである： 尚、画素Ｄ３は先の修正で削除されてはいるが、Ｄ４と
隣り合う画素である。

【００４７】Ｄ４に関する隣り合い画素マトリクスは１
つの動作を発生させる。すなわち、移動であるために高
いメリットを有する「上方移動」動作である。Ｃ５に関
する隣り合い画素マトリクスは下方移動（高メリット）
と、削除（低メリット）という２つの動作を発生させ
る。好ましい実現形態では、Ｄ４が形状の中央にあるの
に対し、Ｃ５は端にあるため、Ｃ５移動動作はＤ４移動
動作より高いメリットを有する。「Ｃ５を下方へ移動す
る」動作を試みても、他に衝突は起こらない。従って、
図９に示すように、選択した修正によってＣ５は下方へ
移動し、その結果、連なりＣ５−Ｃ５が削除され、連な
りＢ２−Ｂ４はＢ２−Ｂ５へと延長される。

【００４８】図９に関して説明すると、今度は、第３の
検出方法に従って、連なりＦ３−Ｆ４と連なりＥ５−Ｅ
５との間の角衝突を発見する。侵害画素は画素Ｆ４及び
Ｆ５である。隣り合い画素マトリクスは次の通りであ
る。 Ｆ４の隣り合い画素マトリクスは高メリットの「上方移
動」を実行させる。Ｅ５の隣り合い画素マトリクスは動
作を起こさせない。「Ｆ４を上方へ移動させる」動作は
他に衝突を生じさせないので、図１０に示すように、Ｆ
４は上方へ移動されて、連なりＦ３−Ｆ４をＦ３−Ｆ３
に更新すると共に、連なりＧ５−Ｇ５をＧ４−Ｇ５とな
るように延長する。

【００４９】画素の削除を順序づけする相対メリット
と、画素を削除するより移動することを選択するための
基準を変更できることは当業者には明かであろう。たと
えば、画素を移動すべきか否かの選択を先行する編集の
効果に従って行うことができる。すなわち、移動を回避
できるか否かを知るために、文字の残る部分が編集され
るまでその決定を延期することが可能である。辺衝突と
角衝突がある状況の下では許容されるが、別の状況では
許されないこともあり、それに相応して実行可能な動作
に関わる規則を調整できることは当業者にはわかるであ
ろう。また、衝突をできる限り少なくするため又は排除
するために文字の経路を変更できることも明かであろ
う。

【００５０】ここで説明した方法について、下記の実施
例の中でさらに明瞭に示すように、本発明の教示及び特
許請求の範囲の範囲内に含まれる変形を加えることは当
業者には明白であろうし、当業者であれば、そのような
付加的変形を実施できるであろう。

【００５１】実施例１：図１１を参照すると、連なりＤ
３−Ｄ３と連なりＣ２−Ｃ２は衝突しており、画素Ｄ３
及びＣ２が侵害画素である。隣り合い画素マトリクスは
次の通りである： これらの隣り合い画素マトリクスをデータベースでルッ
クアップして、侵害画素Ｃ２を左又は下方へ移動させる
ことができた。それら２つの移動動作は同じメリットを
有する―マトリクスの中に、どちらを選択すべきかを指
示するものはなかったのである。これらの移動動作はい
ずれも高メリットを有する。侵害画素Ｃ２は削除するこ
とも可能であろう。削除はどの移動動作よりも低いメリ
ットを有するが、Ｃ２の削除は削除としては相対的に高
いメリットを有する。

【００５２】侵害画素Ｄ３はＥ２とＥ４との連結を維持
しているので、これを削除するのは不可能である。これ
を上方へ移動させることができた。この動作は、（ａ）
移動は削除より上であるが、（ｂ）輪郭が曲線である形
状をまっすぐな形状に変えると、文字の外見が変化する
こともありうるため、中程度のメリットを有する。完全
に解析すると、相対メリットにより４つの動作を次のよ
うにランク付けできた。 １．Ｃ２を左へ移動 高メリット ２．Ｃ２を下方へ移動 高メリット（第１の動作と等
しい） ３．Ｄ３を上方へ移動 中メリット ４．Ｃ２を削除 低メリット 動作をメリット順にそれぞれ試行した。好ましい実現形
態では、動作１と動作２との結びつきを動作１を選択す
ることにより分解した。

【００５３】実施例２：この実施例は、削除された画素
が表示されないにもかかわらず、それらの画素を隣り合
う画素マトリクスを含めることの利点を示す。図１２を
参照すると、画素Ｃ４は、共にＣ４−Ｃ４として指示さ
れる２つの互いに重なる連なりによって表示されてい
る。一方の連なりは交点対１２１−１２２に関するもの
であり、他方の連なりは交点対１２３−１２４に関する
ものである。これらの連なりはそれぞれ画素Ｄ４と衝突
する。１２１−１２２と、１２３−１２４とに関する２
つの連なりは同じ隣り合い画素マトリクスを有するので
あるが、あらゆる重複連なりについて必ずそのようにな
るとは限らない。侵害画素はＣ４とＤ４である。隣り合
い画素マトリクスは次の通りである。

【００５４】これらの隣り合い画素マトリクスをルック
アップすると、好ましい実現形態の規則に従えば、侵害
画素Ｄ４を削除又は移動することは不可能であった（削
除すると形状に「切れ目」が生じ、また、移動は不可能
である）。侵害画素Ｃ４はその画素を表示する２つの連
なりから削除可能であるので、Ｃ４を削除した。隣り合
い画素マトリクスが同じであるため、１２１−１２２に
関する連なりと、１２３−１２４に関する連なりの双方
についてこの結果は適正である。好ましい実現形態で
は、それらの交点対はどの画素によっても表示されなく
なるが、経路の順に維持された。

【００５５】さらに図１２を参照すると、連なりＢ５−
Ｂ５と連なりＣ６−Ｃ６も衝突を構成しており、侵害画
素はＢ５とＣ６である。隣り合い画素マトリクスは次の
通りである：

【００５６】画素Ｂ５に関する隣り合い画素マト
リクスを計算するときに、先にステップで削除した画素
Ｃ４を無視したならば、文字は不当にゆがんでしまうと
考えられる。上記のように、画素Ｃ４はＢ５に関する隣
り合い画素マトリクスの中では「（ｘ）」により表され
ている。侵害画素Ｃ６は隣り合う画素をもたないので、
移動又は削除は不可能であった。画素Ｂ５は削除又は移
動できなかった（いずれの動作も、Ｃ４とＡ６との連結
を断ち切る）。動作は全く許されないので、画素Ｂ５及
びＣ６は共に表示されたままである。Ｂ５の隣り合い画
素に画素Ｃ４を含めないと、Ｂ５は削除されてしまい、
Ａ６からＢ４への連結経路を断ち切るであろう。

【００５７】当業者には明白であろうが、先に説明した
ように、本発明全般の趣旨の範囲内で、本発明の衝突識
別及び修正方式の詳細について数多くの変更を実施する
ことができる。従って、本発明の範囲に対して課すべき
唯一の制限は特許請求の範囲に記載されている制限であ
る。

【図面の簡単な説明】

【図１】〜

【図６】単純な中心点充填方式又は変形中心点充填方式
を使用した文字の、本発明の方法を採用する前（図１〜
図３）と、採用した後（図４〜図６）の画素マッピング
を示す図。

【図７】〜

【図１０】本発明の方法を使用する文字「ｅ」の画素マ
ッピングを順に示す図。

【図１１】，

【図１２】本発明を使用する場合の詳細を示す図。

【符号の説明】

１０〜１７ 交点 １０１〜１０５ 交点 １０６，１０７ 擬似交点 １０８〜１１４ 交点 １２１〜１２４ 交点 １３０〜１３２ 最大Ｘ極値 １３３〜１３５ 最小Ｘ極値

フロントページの続き (72)発明者 トーマス・マロイ アメリカ合衆国 94025 カリフオルニア 州・ポートラ ヴアレイ・シヨーニー パ ス・185

Claims (1)

1. 【特許請求の範囲】 【請求項１】 文字を１つ又は複数の経路によって記述
   し、前記経路が水平画素中心線と交差する交点を識別
   し、前記交点を走査線の順に交点対として２つ１組と
   し、前記交点対から画素の連なりを識別するようにして
   ラスター装置に文字を表示する方法において、２つの画
   素の連なりの間の衝突を識別することと、文字の完全性
   を維持しつつ前記衝突を除去するために修正動作を実行
   することとからなる文字ビットマップを編集する方法。