(57)【要約】【課題】文字を画像のサンプリンググリッドにアラインする方法を得る。【解決手段】文字のアウトラインが入力ペンコマンドによって指定される。入力ペンコマンドの点と輪郭が求められる。各輪郭の向きが判断される。関連する輪郭の階層関係を示す第１の非循環有向グラフ（ＤＡＧ）が構成される。第１のＤＡＧを使用して部首が求められる。輪郭の単純セグメントが求められ、各部首について独立にマージされる。セグメント対と該セグメント対のヒンティングされた座標が求められる。セグメント対がソートされ、ソートされたセグメント対に関する第２のＤＡＧが構成される。第２のＤＡＧを使用してセグメント対間の衝突が解消される。各部首についてｘフリー点とｙフリー点が求められる。各部首について、セグメント対、ｘフリー点及びｙフリー点が、サンプリンググリッドに独立にフィッティングされ、フィッティングの結果が、出力ペンコマンドに格納される。【選択図】図２Ａ
2010170096.tif 000002
【特許請求の範囲】
【請求項１】
文字を画像のサンプリンググリッドにアラインするための方法であって、前記文字のアウトラインをトレースするオリジナルの経路が、オリジナルの座標を有する入力ペンコマンドによって指定され、前記方法はコンピュータによって実行され、前記方法は、
前記入力ペンコマンドの点及び輪郭を求めるステップと、
各輪郭の向きを判断するステップと、
関連する輪郭の階層関係を示す第１の非循環有向グラフを構成するステップと、
前記第１の非循環有向グラフを使用して、関連する輪郭のグループの部首を求めるステップと、
前記輪郭の単純セグメントを求めるステップと、
前記単純セグメントを各部首について独立にマージするステップと、
マージセグメントに関するセグメント対を求めるステップと、
前記セグメント対に関するヒンティングされた座標を求めるステップと、
前記セグメント対をソートすると共に、前記ソートされたセグメント対に関する第２の非循環有向グラフを構成するステップと、
前記第２の非循環有向グラフを使用して前記セグメント対間の衝突を解消するステップと、
各部首についてｘフリー点及びｙフリー点を求めるステップと、
前記セグメント対、前記ｘフリー点、及び前記ｙフリー点を前記サンプリンググリッドに各部首について独立にフィッティングすると共に、前記フィッティングの結果を、前記ヒンティングされた座標を有する出力ペンコマンドに格納して、前記文字の前記アウトラインを前記画像の前記サンプリンググリッドにアラインするステップと
を含む、文字を画像のサンプリンググリッドにアラインするための方法。
【請求項２】
前記部首は、並列に処理される
請求項１記載の方法。
【請求項３】
前記サンプリンググリッドは、前記画像のピクセルグリッドであり、
前記画像は、スクリーン上に表示される
請求項１記載の方法。
【請求項４】
前記サンプリンググリッドは、前記画像のサブピクセルグリッドであり、
前記画像は、スクリーン上に表示される
請求項１記載の方法。
【請求項５】
前記出力ペンコマンドをレンダリングするステップをさらに含む
請求項１記載の方法。
【請求項６】
前記解消するステップは、欲張りボトムアッププロセスにおいて前記第２の非循環有向グラフをトラバースする
請求項１記載の方法。
【請求項７】
最も上側の水平セグメント対及び最も下側の水平セグメント対、並びに最も左側の垂直セグメント対及び最も右側の垂直セグメント対は、前記サンプリンググリッドにおける最も近接したグリッド点にアラインされる
請求項１記載の方法。
【請求項８】
前記アラインするステップは、
オリジナルの対の幅及び調整された対の幅を求めるステップと、
前記オリジナルの対の幅及び前記調整された対の幅を使用して、前記セグメントを前記サンプリンググリッドにフィッティングするステップとをさらに含む
請求項１記載の方法。
【請求項９】
前記アラインするステップは、
各部首における前記ｘフリー点に対する先行ｘアンカ点及び次ｘアンカ点を求めるステップと、
前記先行ｘアンカ点及び前記次ｘアンカ点を使用して、前記ｘフリー点を前記サンプリンググリッドにフィッティングするステップとをさらに含む
請求項１記載の方法。
【請求項１０】
前記アラインするステップは、
各部首における前記ｙフリー点に対する先行ｙアンカ点及び次ｙアンカ点を求めるステップと、
前記先行ｙアンカ点及び前記次ｙアンカ点を使用して、前記ｘフリー点を前記サンプリンググリッドにフィッティングするステップとをさらに含む
請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、文字をレンダリングすることに関し、より詳細には、アウトラインによって表される文字をグリッドアライン（grid align）することに関する。
【背景技術】
【０００２】
グリッドフィッティング
文字又はグリフを表示及び印刷のためにレンダリングすることは、特に文字が複雑である場合に問題が多い。これは、中国語、日本語、及び韓国語（ＣＪＫ）の文字セットに特に当てはまる。これについては、図１Ａを参照されたい。図示する文字は、Apple Computer社のTrueType Reference Manualに記載されているようなアウトラインによって表される。本発明の目的は、レンダリングする目的でサンプリンググリッド（例えば、ピクセルグリッド又はサブピクセルグリッド）にアウトラインを自動的にアラインすることである。
【０００３】
ヒント
ヒントは、各グリフと共に格納される一組のルール又は手順であり、レンダリング中にそのグリフをどのように修正して、対称性、ストロークの太さ、及びタイプフェースのすべてのグリフにわたる均一な外観のような特徴を保つべきかを指定するための一組のルール又は手順である。ヒンティングには、文字のエッジをサンプリンググリッドにアラインすることが必要とされる。アンチエイリアシングを有しようが有しまいが、小さなスクリーンサイズでは、ヒンティングは、人間の読み手にとって明瞭で読みやすいテキストを生成するのに極めて重要である。ヒンティングは、手動、自動、又はそれらの組み合わせとすることができる。
【０００４】
手動ヒンティングは、多くの労力を必要とし且つ費用を要する。例えば、日本語又は中国語のフォントは１万を超えるグリフを有する可能性があり、これらのフォントの良好にヒンティングされた（well-hinted）タイプフェースを開発するには、数年を要する可能性がある。ヒンティングは、本文活字（body type）のレンダリング品質を改善することに重点を置いているので、ヒントは、任意の経路に沿って配置される活字及びアニメ化された活字には有効ではない傾向がある。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
自動ヒンティングについての現在の方法は、ラテン語のような単純なスクリプトについては妥当な結果を生み出すが、中国語及び日本語のような複雑なスクリプトについては不十分である。その結果、複雑なグリフを有効に取り扱うことができる自動ヒンティング方法が必要とされている。自動ヒンティングでは、労働コストが省かれ、フォントファイルに格納される手動ヒントがもはや必要とされないので、フォントサイズが大幅に削減される。
【課題を解決するための手段】
【０００６】
方法は、文字を画像のサンプリンググリッドにアラインする。ここで、文字のアウトラインをトレースするオリジナルの経路が、オリジナルの座標を有する入力ペンコマンドによって指定される。入力ペンコマンドの点及び輪郭が求められる。各輪郭の向きが判断される。関連する輪郭の階層関係を示す第１の非循環有向グラフ（ＤＡＧ）が構成される。第１のＤＡＧを使用して、関連する輪郭のグループの部首が求められる。輪郭の単純セグメント（simple segment）が求められる。単純セグメントが各部首について独立にマージされる。マージセグメント（merged segment）に関するセグメント対が求められる。セグメント対に関するヒンティングされた座標が求められる。セグメント対がソートされ、ソートされたセグメント対に関する第２のＤＡＧが構成される。第２のＤＡＧを使用してセグメント対間の衝突が解消される。各部首についてｘフリー点及びｙフリー点が求められる。各部首について、セグメント対、ｘフリー（x-free）点、及びｙフリー（y-free）点が、サンプリンググリッドに独立にフィッティングされ、フィッティングの結果が、ヒンティングされた座標を有する出力ペンコマンドに格納され、それによって、文字のアウトラインが画像のサンプリンググリッドにアラインされる。
【図面の簡単な説明】
【０００７】
【図１Ａ】本発明の実施形態に従ってアラインされるアウトライン文字の図である。
【図１Ｂ】文字の相対的アラインメントを有するサンプリンググリッドを示す。
【図２Ａ】本発明の実施形態によるアウトライン文字をアラインするための方法のフロー図である。
【図２Ｂ】本発明の実施形態によるアウトライン文字をアラインするための方法のフロー図である。
【図３】本発明の実施形態による点及び輪郭を有するアウトライン文字の図である。
【図４】本発明の実施形態による部首にグループ化された輪郭の図である。
【図５Ａ】本発明の実施形態による水平セグメントの図である。
【図５Ｂ】本発明の実施形態による水平セグメント及び垂直セグメントの図である。
【発明を実施するための形態】
【０００８】
アラインメント及びグリッドフィッティング
図１Ｂは、本発明の実施形態によるアラインメントを有しないサンプリンググリッド上の中国語文字１１１及びアラインメントを有するサンプリンググリッド上の中国語文字１１２を示す。本発明は、文字内の複数のゾーンを検出及びアラインするので、この方法は、複数アラインメントゾーン（multiple alignment zone）（ＭＡＺ）と呼ばれる。
【０００９】
図２Ａ及び図２Ｂに示すように、文字をサンプリンググリッド（例えば、スクリーン上に表示される画像のピクセルグリッド又はサブピクセルグリッド）にアラインする方法は、文字のアウトラインをトレースするペンコマンドを入力２１３として取り込む。この方法は、ペンコマンドのオリジナルの座標を「ヒンティング」された座標に修正する。
【００１０】
経路
レンダリングされる文字のアウトラインは、経路によって表される。本発明の実施形態による経路は、例えば、moveto、lineto、及びcurvetoといったペンコマンドのシーケンスで構成される。これらのペンコマンドは、文字のためのアウトラインを定義する。Apple Computer社のTrueType Reference Manualを参照されたい。経路表現によって、任意の拡大縮小、回転、及び他の変換が可能になる。
【００１１】
ペンコマンドのシーケンスは、アウトラインをトレースする仮想ペンの移動及び描画を指定し、線セグメント（line segment：線分）及びベジェ曲線セグメントの双方の描画を可能する。各セグメントの終点及び制御点（control vertex）は、浮動小数点画像単位で指定される。
【００１２】
例示のペンコマンドは、以下の通りである。なお、すべての座標（すなわち、ｘ、ｙ、ｃｘ、及びｃｙ）は浮動小数点画像単位で指定されることに留意されたい。
【００１３】
moveto x y -- 新しい経路（すなわち、新しい輪郭）を開始する。このコマンドは、現在の点を（ｘ，ｙ）に設定する。
【００１４】
lineto x y -- 直線セグメントを現在の経路（すなわち、現在の輪郭）に追加する。この線セグメントは、現在の点から（ｘ，ｙ）へ延びる。線セグメントを構成した後、（ｘ，ｙ）が新しい現在の点となる。
【００１５】
curveto cx cy x y -- ベジェ制御点として（ｃｘ，ｃｙ）を使用して、現在の点と（ｘ，ｙ）との間に二次ベジェ曲線セグメントを現在の経路（すなわち、現在の輪郭）に追加する。曲線セグメントを構成した後、（ｘ，ｙ）が新しい現在の点となる。
【００１６】
経路は、文字をレンダリングするためのＴｒｕｅＴｙｐｅ（トゥルータイプ）の規則に従う。これについては、１９９２年１０月１３日にKaasilaに発行された米国特許第５，１５５，８０５明細書「Method and apparatus for moving control points in displaying digital typeface on raster output devices」を参照されたい。この米国特許は、参照により本明細書に援用される。
【００１７】
アラインメント方法の概観
複数アラインメントゾーン（ＭＡＺ）検出及びグリッドフィッティングの方法への入力２１３は、アウトラインベースの文字及びエム当たりのピクセル（ｐｐｅｍ（pixels per em））を表すペンコマンドのシーケンス、及び、文字をレンダリングするのに使用されるエム当たりのピクセル数、すなわち文字のスケールである。この方法は、ペンコマンドの座標を、サンプリンググリッドにアラインする。すなわち、ペンコマンドは自動的にヒンティングされる。
【００１８】
以下の定義及び用語は、本発明のこの説明の理解を容易にするためにいくつかのカテゴリーに編成されている。
【００１９】
点
「点」は、座標（ｘ，ｙ）の２次元集合である。「オンカーブ点（on-curve point）」は、アウトラインベースの文字のアウトライン上に位置する点である。「オフカーブ点（off-curve point）」は、二次ベジェ曲線セグメントのための制御点等、アウトラインベースの文字のアウトライン上に位置する場合もあるし位置しない場合もある点である。
【００２０】
点Ｐの「オリジナルのｘ座標」及び「オリジナルのｙ座標」は、グリッドフィッティングが適用される前の実数値の画像座標における点Ｐのそれぞれｘ座標及びｙ座標である。点Ｐの「ヒンティングされたｘ座標」及び「ヒンティングされたｙ座標」は、グリッドフィッティングが適用された後の実数値の画像座標における点Ｐのそれぞれｘ座標及びｙ座標である。
【００２１】
２つの数値ａとｂとの間の「絶対差」は、｜ａ−ｂ｜、すなわち差（ａ−ｂ）の絶対値である。
【００２２】
２つの点Ｐ１とＰ２との間の「オリジナルのｘ距離」は、点Ｐ１のオリジナルのｘ座標と点Ｐ２のオリジナルのｘ座標との間の絶対差である。２つの点Ｐ１とＰ２との間の「オリジナルのｙ距離」は、点Ｐ１のオリジナルのｙ座標とＰ２のオリジナルのｙ座標との間の絶対差である。
【００２３】
輪郭及び部首
「輪郭」Ｃは、点の順序シーケンスＰ１，Ｐ２，…，Ｐ｛ｎ｝を表す。ここで、ｎは２以上である。輪郭は、アウトラインベースの文字の閉じた経路を規定する。ｉ＜ｊの場合、点Ｐ｛ｉ｝は点Ｐ｛ｊ｝に「先行する」。同様に、ｉ＞ｊの場合、Ｐ｛ｉ｝は点Ｐ｛ｊ｝に「続く」。２つの点Ｐ｛ｉ｝及びＰ｛ｉ＋１｝は「連続する」。点Ｐ｛ｉ｝は点Ｐ｛ｉ＋１｝の「直前に先行し」、点Ｐ｛ｉ＋１｝は点Ｐ｛ｉ｝の「直後に続く」。したがって、点のシーケンスは、輪郭の向きを暗に意味する。
【００２４】
「外側輪郭」は、アウトラインベースの文字の充填領域（filled region：塗りつぶされる領域）の外側境界を規定する輪郭であり、例えば、文字「Ｏ」における外側輪郭である。「内側輪郭」は、アウトラインベースの文字の充填領域の内側境界を規定する輪郭であり、例えば、文字「Ｏ」における内側輪郭である。
【００２５】
非縮退輪郭（non-degenerate contour）Ｃの「バウンディングボックス」は、輪郭Ｃを構成する点のすべてを含む、オリジナルの座標を使用して求められる最小の面積を有する２次元長方形である。縮退輪郭（degenerate contour）Ｃ、すなわち点が共線である輪郭、の「バウンディングボックス」は、輪郭Ｃを構成する点のすべてを含む最短の線セグメントである。
【００２６】
輪郭Ｃの閉じた経路をシーケンシャルな順序でトラバースするときにＣの閉じた経路を規定する点が時計回り方向に従う場合、Ｃは「時計回りに方向付けられている（oriented clockwise）」。同様に、輪郭Ｃの閉じた経路をシーケンシャルな順序でトラバースするときにＣの閉じた経路を規定する点が反時計回り方向に従う場合、Ｃは「反時計回りに方向付けられている（oriented clockwise）」。
【００２７】
Ｐ及びＣを輪郭であるとする。輪郭Ｐが、輪郭Ｃのバウンディングボックスを含む、面積によって測定される最小のバウンディングボックスを有する輪郭である場合で且つその場合に限り、輪郭Ｐは輪郭Ｃの「親」である。Ｐが存在する場合、ＣはＰの「子」である。このようなＰが存在しない場合、Ｃは親輪郭を有しない。親輪郭を有しない輪郭は、「ルート輪郭」と呼ばれる。他のすべての輪郭（すなわち、親輪郭を有する輪郭）は、「内部輪郭（internal contour）」と呼ばれる。輪郭は、最大でも１つの親輪郭を有することができる。
【００２８】
Ａ及びＤを輪郭であるとする。（１）輪郭ＤがＡの子である場合で且つその場合に限り、又は（２）ＤがＣ１の子であり、Ｃ｛ｉ｝がＣ｛ｉ＋１｝の子であり、且つＣ｛ｎ｝はＡの子であるような、輪郭の或る順序シーケンスＣ１，Ｃ２，…，Ｃ｛ｎ｝が存在する場合で且つその場合に限り、ＤはＡの「子孫」である。ここで、ｎは１よりも大きく、ｉは範囲［１，ｎ−１］内にある整数である。ＤがＡの子孫である場合、ＡはＤの「先祖」である。
【００２９】
「部首」は、単一のルート輪郭Ｒ及びＲの子孫のすべてによって規定される関連する輪郭Ｒ，Ｃ１，Ｃ２，…，Ｃ｛ｎ｝の集合である。ここで、ｎは０以上である。すなわち、各Ｃ｛ｉ｝は、Ｒの子孫である。
【００３０】
単純セグメント
「水平単純セグメント」Ｈは、点Ｐ１のオリジナルのｙ座標が点Ｐ２のオリジナルのｙ座標にほぼ等しいような、或る輪郭における２つの連続する点Ｐ１及びＰ２から成る。Ｐ１及びＰ２のオリジナルのｙ座標は、それらの絶対差が所定の定数「ＥＱＵＡＬ＿ＥＰＳ」未満である場合にほぼ等しいとみなされる。ここで、ＥＱＵＡＬ＿ＥＰＳは、実数値の画像単位で指定される。Ｐ１はセグメントＨ内の「第１の点」と呼ばれ、Ｐ２はＨ内の「第２の点」と呼ばれる。
【００３１】
「垂直単純セグメント」Ｖは、点Ｐ１のオリジナルのｘ座標が点Ｐ２のオリジナルのｘ座標にほぼ等しいような、或る輪郭における２つの連続する点Ｐ１及びＰ２から成る。Ｐ１及びＰ２のオリジナルのｘ座標は、それらの絶対差がＥＱＵＡＬ＿ＥＰＳ単位未満である場合にほぼ等しいとみなされる。Ｐ１はセグメントＶ内の「第１の点」と呼ばれ、Ｐ２はＶ内の「第２の点」と呼ばれる。
【００３２】
一般的な用語「単純セグメント」は、水平単純セグメント又は垂直単純セグメントのいずれかを指す。水平単純セグメントＨの第１の点のオリジナルのｘ座標がＨの第２の点のオリジナルのｘ座標未満である場合、Ｈは「左から右に」方向付けられている。セグメントＨの第１の点のオリジナルのｘ座標がＨの第２の点のオリジナルのｘ座標以上である場合、Ｈは「右から左に」方向付けられている。セグメントＨは、セグメントＨが左から右に方向付けられている場合には「増加」しており、セグメントＨが右から左に方向付けられている場合には「減少」している。
【００３３】
垂直単純セグメントＶの第１の点のオリジナルのｙ座標がＶの第２の点のオリジナルのｙ座標未満である場合、Ｖは「下から上に」方向付けられている。Ｖの第１の点のオリジナルのｙ座標がＶの第２の点のオリジナルのｙ座標以上である場合、Ｖは「上から下に」方向付けられている。Ｖは、Ｖが下から上に方向付けられている場合には「増加」しており、Ｖが上から下に方向付けられている場合には「減少」している。
【００３４】
対向する向き
図５Ａに示すように、水平単純セグメントＨ１及びＨ２の対２１８は、（１）Ｈ１が左から右に方向付けられ且つＨ２が右から左に方向付けられている場合、又は（２）Ｈ１が右から左に方向付けられ且つＨ２が左から右に方向付けられている場合のいずれかの場合に「対向する向き」を有する。
【００３５】
垂直単純セグメントＶ１及びＶ２の対は、（１）Ｖ１が下から上に方向付けられ且つＶ２が上から下に方向付けられている場合、又は（２）Ｖ１が上から下に方向付けられ且つＶ２が下から上に方向付けられている場合のいずれかの場合に「対向する向き」を有する。
【００３６】
長さ
水平単純セグメントＨの「長さ」は、Ｈの第１の点のオリジナルのｘ座標とＨの第２の点のオリジナルのｘ座標との間の絶対差である。垂直単純セグメントＶの「長さ」は、Ｖの第１の点のオリジナルのｙ座標とＶの第２の点のオリジナルのｙ座標との間の絶対差である。
【００３７】
勾配
単純セグメントＳの「オリジナルの勾配」は、比ｄｙ／ｄｘである。ここで、ｄｙ＝ｙ２−ｙ１であり、ｄｘ＝ｘ２−ｘ１であり、ｙ１はＳの第１の点のオリジナルのｙ座標であり、ｙ２はＳの第２の点のオリジナルのｙ座標であり、ｘ１はＳの第１の点のオリジナルのｘ座標であり、ｘ２はＳの第２の点のオリジナルのｘ座標である。第１の点及び第２の点が同一のオリジナルのｘ座標を有する垂直単純セグメントは、分母ｄｘが０となるので、未定義のオリジナルの勾配を有する。
【００３８】
マージセグメント
「水平マージセグメント」は、以下の３つの条件、すなわち、（１）Ｈ１，…，Ｈ｛ｎ｝がすべて同じ向きを有する、（２）Ｈ１，…，Ｈ｛ｎ｝がすべて同じ部首に含まれる、及び（３）Ｈ｛ｉ｝及びＨ｛ｊ｝内の第１の点のオリジナルのｙ座標が実数値の画像座標において（２＊ＥＱＵＡＬ＿ＥＰＳ）単位未満だけ異なる、という条件をすべて満たす１つ又は複数の異なる水平単純セグメントＨ１，Ｈ２，…，Ｈ｛ｎ｝から成る。ここで、ｎ≧１であり、ｉ及びｊは範囲［１，ｎ］内の任意の整数である。
【００３９】
水平単純セグメント内の第１の点及び第２の点のオリジナルのｙ座標は、実数値の画像座標においてＥＱＵＡＬ＿ＥＰＳ単位未満だけ異なるので、条件（３）は、Ｈ｛ｉ｝及びＨ｛ｊ｝内の第２の点のオリジナルのｙ座標が実数値の画像座標において（３＊ＥＱＵＡＬ＿ＥＰＳ）単位未満異なることを暗に意味している。ここで、ｉ及びｊは、範囲［１，ｎ］内にある任意の整数である。
【００４０】
「垂直マージセグメント」は、以下の３つの条件、すなわち、（１）Ｖ１，…，Ｖ｛ｎ｝がすべて同じ向きを有する、（２）Ｖ１，…，Ｖ｛ｎ｝がすべて同じ部首に含まれる、及び（３）Ｖ｛ｉ｝及びＶ｛ｊ｝内の第１の点のオリジナルのｘ座標が実数値の画像座標において（２＊ＥＱＵＡＬ＿ＥＰＳ）単位未満だけ異なる、という条件をすべて満たす１つ又は複数の異なる垂直単純セグメントＶ１，Ｖ２，…，Ｖ｛ｎ｝から成る。ここで、ｎ≧１であり、ｉ及びｊは範囲［１，ｎ］内の任意の整数である。
【００４１】
垂直単純セグメント内の第１の点及び第２の点のオリジナルのｘ座標は、実数値の画像座標においてＥＱＵＡＬ＿ＥＰＳ単位未満だけ異なるので、条件（３）は、Ｖ｛ｉ｝及びＶ｛ｊ｝内の第２の点のオリジナルのｘ座標が実数値の画像座標において（３＊ＥＱＵＡＬ＿ＥＰＳ）単位未満だけ異なることを暗に意味している。ここで、ｉ及びｊは、範囲［１，ｎ］内にある任意の整数である。
【００４２】
一般的な用語「マージセグメント」は、水平マージセグメント又は垂直マージセグメントのいずれかを指す。
【００４３】
（１）点Ｐが単純セグメントＳに含まれ、且つ（２）ＳがマージセグメントＭに含まれる場合、点ＰはマージセグメントＭに含まれる。
【００４４】
Ｈを、セグメントＨ内のすべての点にわたる最小のオリジナルのｘ座標がｘＭｉｎであり、セグメントＨ内のすべての点にわたる最大のオリジナルのｘ座標がｘＭａｘである水平マージセグメントであるとする。セグメントＨの「長さ」は、ｘＭａｘとｘＭｉｎとの間の差、すなわちｘＭａｘ−ｘＭｉｎである。
【００４５】
Ｖを、セグメントＶ内のすべての点にわたる最小のオリジナルのｙ座標がｙＭｉｎであり、Ｖ内のすべての点にわたる最大のオリジナルのｙ座標がｙＭａｘである垂直マージセグメントであるとする。セグメントＶの「長さ」は、ｙＭａｘとｙＭｉｎとの間の差、すなわちｙＭａｘ−ｙＭｉｎである。
【００４６】
マージセグメントＭの「オリジナルの勾配」は、オリジナルの勾配ｓ１，ｓ２，…，ｓ｛ｎ｝の集合である。ここで、ｎ≧１であり、ｓ｛ｉ｝は、Ｍにおけるｉ番目の単純セグメントのオリジナルの勾配である。
【００４７】
Ｈ１及びＨ２を、それぞれ長さＬ１及びＬ２を有する水平マージセグメントであるとする。Ｌを、Ｌ１及びＬ２の最大値とする。非数式的には、Ｈ１とＨ２との間の「重なり合い比（overlap ratio）」は、Ｈ１とＨ２との間の水平の重なり合いの量を、長い方のセグメントの長さによって除算したものである。数式的には、Ｈ１とＨ２との間の「重なり合い比」は、（ＭＩＮ（ｘＭａｘ１，ｘＭａｘ２）−ＭＡＸ（ｘＭｉｎ１，ｘＭｉｎ２））／Ｌとして定義される。ここで、ｘＭｉｎ１は、Ｈ１内のすべての点にわたって最小のオリジナルのｘ座標であり、ｘＭｉｎ２は、Ｈ２内のすべての点にわたって最小のオリジナルのｘ座標であり、ｘＭａｘ１は、Ｈ１内のすべての点にわたって最大のオリジナルのｘ座標であり、ｘＭａｘ２は、Ｈ２内のすべての点にわたって最大のオリジナルのｘ座標である。
【００４８】
Ｖ１及びＶ２を、それぞれ長さＬ１及びＬ２を有する垂直マージセグメントであるとする。Ｌを、Ｌ１及びＬ２の最大値とする。非数式的には、Ｖ１とＶ２との間の「重なり合い比」は、Ｖ１とＶ２との間の垂直の重なり合いの量を、長い方のセグメントの長さによって除算したものである。数式的には、Ｖ１とＶ２との間の「重なり合い比」は、（ＭＩＮ（ｙＭａｘ１，ｙＭａｘ２）−ＭＡＸ（ｙＭｉｎ１，ｙＭｉｎ２））／Ｌとして定義される。ここで、ｙＭｉｎ１は、Ｖ１内のすべての点にわたって最小のオリジナルのｙ座標であり、ｙＭｉｎ２は、Ｖ２内のすべての点にわたって最小のオリジナルのｙ座標であり、ｙＭａｘ１は、Ｖ１内のすべての点にわたって最大のオリジナルのｙ座標であり、ｙＭａｘ２は、Ｖ２内のすべての点にわたって最大のオリジナルのｙ座標である。
【００４９】
マージセグメントＭ内の「第１の点」は、Ｍにおける第１の単純セグメント内の第１の点である。マージセグメントは、単純セグメントのリンクリストとして表される。Ｍにおける第１の単純セグメントは、Ｍにおける単純セグメントのリンクリストの第１の要素である。
【００５０】
セグメント対
図５Ａに示すように、「水平セグメント対」２１８は、（１）２つの異なる水平マージセグメントＨ１及びＨ２が同じ部首に含まれ、（２）Ｈ１及びＨ２が対向する向きを有し、且つ（３）Ｈ１の第１の点のオリジナルのｙ座標がＨ２の第１の点のオリジナルのｙ座標未満であるような、２つの異なる水平マージセグメントの対２１８  Ｈ１及びＨ２であり、｛Ｈ１，Ｈ２｝と記述される。Ｈ１は、セグメント対｛Ｈ１，Ｈ２｝の「最小対セグメント（minimum paired segment）」と呼ばれ、Ｈ２は、セグメント対｛Ｈ１，Ｈ２｝の「最大対セグメント（maximum paired segment）」と呼ばれる。Ｈ１及びＨ２は、互いに「対」にされている。
【００５１】
「垂直セグメント対」は、（１）２つの異なる垂直マージセグメントＶ１及びＶ２が同じ部首に含まれ、（２）Ｖ１及びＶ２が対向する向きを有し、且つ（３）Ｖ１の第１の点のオリジナルのｘ座標がＶ２の第１の点のオリジナルのｘ座標未満であるような、２つの異なる垂直マージセグメントＶ１及びＶ２の対であり、｛Ｖ１，Ｖ２｝と記述される。Ｖ１は、セグメント対｛Ｖ１，Ｖ２｝の「最小対セグメント」と呼ばれ、Ｖ２は、セグメント対｛Ｖ１，Ｖ２｝の「最大対セグメント」と呼ばれる。Ｖ１及びＶ２は、互いに「対」にされている。
【００５２】
一般的な用語「セグメント対」５１２は、水平セグメント対又は垂直セグメント対のいずれかを指す。
【００５３】
用語「対セグメント」は、セグメント対の２つのマージセグメントのいずれか一方を指す。
【００５４】
「非対セグメント（unpaired segment）」は、（１）他のどの水平マージセグメントとも対にされていない水平マージセグメント、又は（２）他のどの垂直マージセグメントとも対にされていない垂直マージセグメント、のいずれかである。
【００５５】
セグメントＨを、セグメントＨ内のすべての点にわたる最小のオリジナルのｙ座標がｙＭｉｎであり、セグメントＨ内のすべての点にわたる最大のオリジナルのｙ座標がｙＭａｘである水平マージセグメントであるとする。セグメントＨの「オリジナルの中間ｙ座標」は、ｙＭｉｎ及びｙＭａｘの平均、すなわち０．５＊（ｙＭｉｎ＋ｙＭａｘ）である。
【００５６】
セグメントＶを、セグメントＶ内のすべての点にわたる最小のオリジナルのｘ座標がｘＭｉｎであり、セグメントＶ内のすべての点にわたる最大のオリジナルのｘ座標がｘＭａｘである垂直マージセグメントであるとする。Ｖの「オリジナルの中間ｘ座標」は、ｘＭｉｎ及びｘＭａｘの平均、すなわち０．５＊（ｘＭｉｎ＋ｘＭａｘ）である。
【００５７】
水平セグメント対｛Ｈ１，Ｈ２｝の「第１の対の幅（pair width）」は、Ｈ２の第１の点のオリジナルのｙ座標とＨ１の第１の点のオリジナルのｙ座標との間の差である。垂直セグメント対｛Ｖ１，Ｖ２｝の「第１の対の幅」は、Ｖ２の第１の点のオリジナルのｘ座標とＶ１の第１の点のオリジナルのｘ座標との間の差である。
【００５８】
水平セグメント対｛Ｈ１，Ｈ２｝の「オリジナルの対の幅」は、Ｈ２のオリジナルの中間ｙ座標とＨ１のオリジナルの中間ｙ座標との間の差である。垂直セグメント対｛Ｖ１，Ｖ２｝の「オリジナルの対の幅」は、Ｖ２のオリジナルの中間ｘ座標とＶ１のオリジナルの中間ｘ座標との間の差である。
【００５９】
セグメント対Ｐ１の第１の対の幅がセグメント対Ｐ２の第１の対の幅よりも大きい場合には、Ｐ１はＰ２よりも「太い」。Ｐ１の第１の対の幅がＰ２の第１の対の幅よりも小さい場合には、Ｐ１はＰ２よりも「細い」。
【００６０】
グリッドフィッティングの専門用語
「半整数」は、或る整数ｋについてｎ＝ｋ＋０．５となるような実数の集合の要素ｎである。例えば、−２．５、−１．５、−０．５、０．５、１．５、２．５、及び３．５は、すべて半整数である。
【００６１】
「整数ピクセルグリッド」は、（ｘ，ｙ）の少なくとも一方の要素が整数であるような、実数ｘ及びｙの順序対（ｘ，ｙ）の集合である。例えば、座標（０，０）、（１．５，０）、及び（１．９７，３）は、整数ピクセルグリッド上にあるが、（１．７，１１．２）は、整数ピクセルグリッド上にない。幾何学的には、整数ピクセルグリッドは、例えばｙ＝−２、ｙ＝−１、ｙ＝０、ｙ＝１、及びｙ＝２といった整数水平線の集合、並びに例えばｘ＝−２、ｘ＝−１、ｘ＝０、ｘ＝１、及びｘ＝２といった整数垂直線の集合を含むグリッドである。
【００６２】
「半整数ピクセルグリッド」は、（ｘ，ｙ）の少なくとも一方の要素が半整数であるような、実数ｘ及びｙの順序対（ｘ，ｙ）の集合である。例えば、（０，０．５）、（１．５，０）、及び（１．９７，２．５）は、半整数ピクセルグリッド上にあるが、（１．７，１１．２）は、整数ピクセルグリッド上にない。幾何学的には、半整数ピクセルグリッドは、例えばｙ＝−２．５、ｙ＝−１．５、ｙ＝−０．５、ｙ＝０．５、ｙ＝１．５及びｙ＝２．５といった半整数水平線の集合、並びに例えばｘ＝−２．５、ｘ＝−１．５、ｘ＝−０．５、ｘ＝０．５、ｘ＝１．５、及びｘ＝２．５といった半整数垂直線の集合を含むグリッドである。
【００６３】
衝突の専門用語
垂直線ＶがＡ１又はＢ１のいずれかと交差し且つＶがＡ２又はＢ２のいずれかと交差するような垂直線Ｖが存在する場合、２つの水平セグメント対Ｈ１＝｛Ａ１，Ｂ１｝及びＨ２＝｛Ａ２，Ｂ２｝は「重なり合う」。同様に、水平線ＨがＡ１又はＢ１のいずれかと交差し且つＨがＡ２又はＢ２のいずれかと交差するような水平線Ｈが存在する場合、２つの垂直セグメント対Ｖ１＝｛Ａ１，Ｂ１｝及びＶ２＝｛Ａ２，Ｂ２｝は「重なり合う」。
【００６４】
「水平セグメント対Ｈ＝｛Ｈ１，Ｈ２｝のオリジナルの座標」は、Ｈ１のオリジナルの中間ｙ座標である。同様に、「垂直セグメント対Ｖ＝｛Ｖ１，Ｖ２｝のオリジナルの座標」は、Ｖ１のオリジナルの中間ｘ座標である。
【００６５】
「水平セグメント対Ｈ＝｛Ｈ１，Ｈ２｝のヒンティングされた座標」は、グリッドフィッティングが適用された後の実数値の画像座標におけるＨ１のｙ座標である。「垂直セグメント対Ｖ＝｛Ｖ１，Ｖ２｝のヒンティングされた座標」は、グリッドフィッティングが適用された後の実数値の画像座標におけるＶ１のｘ座標である。
【００６６】
Ｐ１及びＰ２を、オリジナルの座標ｃ１及びｃ２をそれぞれ有するセグメント対とする。Ｐ１及びＰ２は、ｃ１がｃ２以下である場合には「昇順」にあり、ｃ１がｃ２以上である場合には「降順」にある。用語「昇順」及び「降順」は、一般に、任意の個数のセグメント対に適用され、例えば４つのセグメント対に適用される。
【００６７】
Ｐ１、Ｐ２、及びＰ３を、昇順のセグメント対とする。（１）Ｐ１がＰ２と重なり合い、且つ（２）Ｐ２がＰ３と重なり合う場合で且つその場合に限り、Ｐ２はＰ１とＰ３との「間」に位置する。
【００６８】
セグメント対Ｃは、以下の条件、すなわち、（１）Ｃのオリジナルの座標≦Ｐのオリジナルの座標である、（２）ＣがＰに重なり合う、及び（３）ＣとＰとの間にセグメント対がない、の３つすべてが満たされる場合で且つその場合に限り、セグメント対Ｐの「子」又は「子セグメント対」である。
【００６９】
セグメント対Ｐは、セグメント対ＣがＰの子である場合で且つその場合に限り、Ｃの「親」又は「親セグメント対」である。Ｐが複数の子セグメント対を有する場合、それら子セグメント対は、Ｐの「子」と呼ばれる。
【００７０】
（１）セグメント対Ｄがセグメント対Ｐの子である場合で且つその場合に限り、又は（２）Ｄがセグメント対Ｐ１の子であり、セグメント対Ｐ｛ｉ｝がセグメント対Ｐ｛ｉ＋１｝の子であり（ここで、１≦ｉ＜ｎ）、且つセグメント対Ｐｎ（ここで、ｎ≧１）がＰの子であるようなセグメント対の或る順序シーケンスＰ１，Ｐ２，…，Ｐｎが存在する場合で且つその場合に限り、セグメント対Ｄは、セグメント対Ｐの「子孫」である。ＤがＰの子孫である場合、ＰはＤの「先祖」である。
【００７１】
「セグメント対ツリー」は、セグメント対Ｐ、及びＰのすべての子孫によって定義されるセグメント対の集合である。セグメント対Ｐは、セグメント対ツリーの「ルートセグメント対」である。セグメント対ツリーは、セグメント対の非循環有向グラフ（ＤＡＧ）を形成する。
【００７２】
セグメント対Ｐのヒンティングされた座標ｈが、Ｐのオリジナルの座標ｏから０．５を引いたものよりも大きな最小の整数に等しい場合、セグメント対Ｐは「切り上げられる」。すなわち、ｈがｆｌｏｏｒ（ｏ−０．５）＋１に等しい場合、セグメント対Ｐは切り上げられる。関数ｆｌｏｏｒ（引数）は、（引数）以下の最大の整数を生成する。
【００７３】
同様に、Ｐのヒンティングされた座標ｈが、Ｐのオリジナルの座標ｏから０．５を引いたものよりも大きくない最大の整数に等しい場合に、Ｐは「切り捨てられる」。すなわち、ｈがｆｌｏｏｒ（ｏ−０．５）に等しい場合、セグメント対Ｐは切り捨てられる。
【００７４】
レンダリングは、ピクセル中心に位置するサンプルで行われる。したがって、後述する本方法は、例えば０．５、１．５、及び２．５といった半整数に座標をアラインすることによってグリッドフィッティングを行う。「切り上げ」及び「切り下げ」のオーソドックスでない定義は、本方法が、半整数座標の代わりに整数座標を使用して、性能を最適化し、浮動小数点の実施態様と固定小数点の実施態様との間でのコード再利用を最大にすることに起因している。これについては、下記のステップ８〜ステップ１１を参照されたい。
【００７５】
セグメント対ツリー内のあらゆるセグメント対が切り上げられる場合、そのセグメント対ツリーは切り上げられる。同様に、セグメント対ツリー内のあらゆるセグメント対が切り捨てられる場合、そのセグメント対ツリーは切り捨てられる。
【００７６】
或るセグメント対Ｐ１が、別のセグメント対Ｐ２と同じヒンティングされた座標を有する場合、Ｐ１はＰ２に「アライン」されている。
【００７７】
Ｐ１及びＰ２を、Ｐ１のヒンティングされた座標がＰ２のヒンティングされた座標よりも大きくなるような２つのセグメント対であるとする。Ｗを、実数値の画像座標におけるＰ２のオリジナルの対の幅であるとする。（１）セグメント対Ｐ１及びＰ２が重なり合い、且つ（２）それらのヒンティングされた座標が、実数値の画像座標において最大でもＷ単位だけ異なる場合、セグメント対Ｐ１及びＰ２は「衝突（collide）」している。
【００７８】
（１）Ｐ１及びＰ２が衝突し、且つ（２）それらのヒンティングされた座標が実数値の画像座標において正確にＷ単位だけ異なる場合、Ｐ１及びＰ２は「わずかに衝突（barely collide）」している。
【００７９】
アンカ点の専門用語
Ｐが水平対セグメントＨに含まれる点である場合、点Ｐは「ｙアラインされた（y-aligned）」点である。そうでない場合、点Ｐは「ｙフリー」点である。
【００８０】
Ｐが垂直対セグメントＶに含まれる点である場合、点Ｐは「ｘアラインされた（x-aligned）」点である。そうでない場合、点Ｐは「ｘフリー」点である。
【００８１】
輪郭Ｃを、点のシーケンスＰ１，Ｐ２，…，Ｐ｛ｎ｝を含むものとする。ここで、ｎ≧２である。Ｐ｛ｉ｝を、ｘフリー点であるとする。
【００８２】
Ｐ｛ｉ｝の「先行ｘアンカ点（previous x anchor point）」は、Ｐ｛ｉ｝から開始して、Ｐ１からＰ｛ｎ｝へ折り返す点のシーケンス、すなわち、Ｐ｛ｉ｝，Ｐ｛ｉ−１｝，…，Ｐ２，Ｐ１，Ｐ｛ｎ｝，Ｐ｛ｎ−１｝，…，Ｐ｛ｉ＋１｝、を通る逆方向トラバース中に見つけられる最初のｘアラインされた点である。輪郭Ｃが、どのｘアラインされた点も含まない場合、Ｐ｛ｉ｝に対する先行ｘアンカ点は存在しない。
【００８３】
Ｐ｛ｉ｝の「次ｘアンカ点（next x anchor point）」は、Ｐ｛ｉ｝から開始して、Ｐ｛ｎ｝からＰ１へ折り返す点のシーケンス、すなわち、Ｐ｛ｉ｝，Ｐ｛ｉ＋１｝，…，Ｐ｛ｎ−１｝，Ｐ｛ｎ｝，Ｐ１，Ｐ２，…，Ｐ｛ｉ−１｝、を通る順方向トラバース中に見つけられる最初のｘアラインされた点である。輪郭Ｃが、どのｘアラインされた点も含まない場合、Ｐ｛ｉ｝に対する次ｘアンカ点は存在しない。
【００８４】
輪郭Ｃを、点のシーケンスＰ１，Ｐ２，…，Ｐ｛ｎ｝から成る輪郭であるとする。ここで、ｎ≧２である。Ｐ｛ｉ｝を、ｙフリー点であるとする。
【００８５】
Ｐ｛ｉ｝の「先行ｙアンカ点（previous y anchor point）」は、Ｐ｛ｉ｝から開始して、Ｐ１からＰ｛ｎ｝へ折り返す点のシーケンス、すなわち、Ｐ｛ｉ｝，Ｐ｛ｉ−１｝，…，Ｐ２，Ｐ１，Ｐ｛ｎ｝，Ｐ｛ｎ−１｝，…，Ｐ｛ｉ＋１｝、を通る逆方向トラバース中に見つけられる最初のｙアラインされた点である。輪郭Ｃが、どのｙアラインされた点も含まない場合、Ｐ｛ｉ｝に対する先行ｙアンカ点は存在しない。
【００８６】
Ｐ｛ｉ｝の「次ｙアンカ点（next y anchor point）」は、Ｐ｛ｉ｝から開始して、Ｐ｛ｎ｝からＰ１へ折り返す点のシーケンス、すなわち、Ｐ｛ｉ｝，Ｐ｛ｉ＋１｝，…，Ｐ｛ｎ−１｝，Ｐ｛ｎ｝，Ｐ１，Ｐ２，…，Ｐ｛ｉ−１｝、を通る順方向トラバース中に見つけられる最初のｙアラインされた点である。輪郭Ｃが、どのｙアラインされた点も含まない場合、Ｐ｛ｉ｝に対する次ｙアンカ点は存在しない。
【００８７】
ｘフリー点Ｐ、その先行ｘアンカ点Ａ１、及びその次ｘアンカ点Ａ２の間の「オリジナルのｘ比」は、比（ｐｘ−ｘ１）／（ｘ２−ｘ１）である。ここで、ｐｘはＰのオリジナルのｘ座標であり、ｘ１はＡ１のオリジナルのｘ座標であり、ｘ２はＡ２のオリジナルのｘ座標である。オリジナルのｘ比は、Ｐのアンカ点のいずれかが存在しない場合又は（ｘ２−ｘ１）が０である場合には定義されない。
【００８８】
ｙフリー点Ｐ、その先行ｙアンカ点Ａ１、及びその次ｙアンカ点Ａ２の間の「オリジナルのｙ比」は、比（ｐｙ−ｙ１）／（ｙ２−ｙ１）である。ここで、ｐｙはＰのオリジナルのｙ座標であり、ｙ１はＡ１のオリジナルのｙ座標であり、ｙ２はＡ２のオリジナルのｙ座標である。オリジナルのｙ比は、Ｐのアンカ点のいずれかが存在しない場合又は（ｙ２−ｙ１）が０である場合には定義されない。
【００８９】
リンクリストの専門用語
線形リンクリストＬの「ヘッド」及び「テール」は、それぞれＬの最初の要素及び最後の要素である。現在Ｌにない要素Ｅは、ＥをＬの新たなヘッドとすることによってＬに「プリペンド」することができる。同様に、ＥをＬの新たなテールとすることによってＥをＬに「アペンド」することもできる。
【００９０】
アラインメント方法の方策
以下の包括的な説明は、後述する方法に適用される。
【００９１】
本方法は、レンダリング中に動的に起動される。これについては、関連出願を参照されたい。したがって、本方法は、高品質、少ないメモリ消費、及び計算効率性の間の好都合なバランスを達成するように設計される。本方法は、任意のアウトラインベースの文字に対して起動することができるが、ＣＪＫ文字用に設計及び最適化されている。
【００９２】
ＣＪＫアウトラインベースの文字は、主として、水平の特徴及び垂直の特徴で構成される。したがって、本方法は、文字の水平の特徴及び垂直の特徴を検出し、それらをサンプリンググリッドにアラインする。これらの特徴は、本明細書では「セグメント対」と呼ばれる。この正確な定義については、上記のセグメント対の専門用語のセクションを参照されたい。
【００９３】
本方法は、例えば曲線又は対角線といった他の特徴をサンプリンググリッドにアラインしない。サンプリンググリッドにアラインされない座標は、その代わりに、補間を使用してヒンティングされる。この詳細については以下を参照されたい。この全体的な方策によって、高品質及び高ランタイム性能という競合する目標がバランスされる。
【００９４】
コントラスト及び一貫性という２つの目標が競合するものであることから、ＣＪＫアウトラインベースの文字に対して自動グリッドフィッティングを行うことは困難な課題である。高いコントラストは、セグメント対の双方のセグメントをサンプリンググリッドにアラインし、それによって、２つのシャープなエッジを有する水平の特徴又は垂直の特徴を生成することにより達成することができる。
【００９５】
高い一貫性は、水平の特徴及び垂直の特徴が、最終画像にレンダリングされる時に一貫したストロークの太さを有するように見えるよう、グリッドフィッティング中にセグメント対のオリジナルの対の幅を保つことによって達成することができる。セグメント対の双方のセグメントをサンプリンググリッドにアラインするには、一般に、オリジナルの対の幅を修正することが必要とされることから、これら２つの目標は競合する。同様に、オリジナルの対の幅を保つことによって、一般に、セグメント対の双方のセグメントがサンプリンググリッドに同時にアラインされることが妨げられる。
【００９６】
一貫性は、特に、複数の文字がテキストの単一のページ上で共に観察される時に、レンダリングされた文字の全体的な視覚品質にとって、コントラストよりも重要である。詳細に言えば、例えば、セグメント対の双方のセグメントをサンプリンググリッドにアラインする代わりに、セグメント対の２つのセグメントの一方のみをサンプリンググリッドにアラインすることによってコントラストのわずかな低減を受け入れ、それと引き換えに、例えば、セグメント対のオリジナルの対の幅を保つことによって一貫性を有意に増加させることが、多くの場合に好ましい。
【００９７】
この理由から、本方法は、以下を例外として、一般に、グリッドフィッティング中、セグメント対のオリジナルの対の幅を保つ。例えば１ピクセル未満の比較的細いセグメント対は、レンダリングされた時、見ることが困難である。したがって、本方法は、細いセグメント対のオリジナルの対の幅をｐｐｅｍに依存した量だけ増加させ、それによって、一貫性を認識可能に損なうことなく、細い特徴の視認性及びコントラストを増加させる。
【００９８】
例えば３０ｐｐｅｍ以下の小〜中程度のｐｐｅｍでは、セグメント対の双方のセグメントをサンプリンググリッドにアラインすることによって、一般に、結果は魅力的なものでなくなり、一貫性は明らかになくなる。例えば８０ｐｐｅｍ以上の大きなｐｐｅｍでは、セグメント対の双方のセグメントをアラインすることによって、結果がわずかによくなる。しかしながら、大きなｐｐｅｍであっても、一貫性の問題が個々の文字に生じ得る場合がある。この理由から、本方法は、セグメント対の双方のセグメントをサンプリンググリッドに明示的にアラインすることは決して行わない。
【００９９】
図２Ａに示すように、本方法は、アウトラインベースの文字における外側輪郭の向きを求めることを試みる（２０２）。これについては、下記のステップ２を参照されたい。この向きによって、本方法は、後続のステップにおいてセグメント対を正確に検出することが可能になる。本方法は、アウトラインベースの文字におけるすべての外側輪郭が同じ向きを有すると仮定する。アウトラインベースの文字がこの特性を有しない場合、本方法は、セグメント対を正確に検出しない場合がある。
【０１００】
図４に示すように、本方法は、輪郭を「部首」２１５と呼ばれるグループに編成する。部首は、アウトラインベースの文字の空間的に関連したコンポーネントのグループである。数式的な定義については、上記の輪郭及び部首の専門用語を参照されたい。本方法は、独立したアラインメントゾーンを使用して、各部首について別個に且つ独立に特徴検出を行う。これによって、セグメント対が文字の空間的に遠い領域間で形成されることを防止することにより、特徴検出の正確度が改善される。特徴検出中、部首間の依存関係はない。その結果、ハードウェアの実施態様及びマルチコアの実施態様は、部首内の特徴検出を完全に並列に行うことができる。
【０１０１】
本方法は、セグメント対間の「衝突」を検出して解消し、それによって、重要な特徴が視覚的に区別できなくなることを防止する。この詳細については下記を参照されたい。衝突解消は、結果の品質に有意な役割を果たす。本方法は、欲張り法を使用して衝突を解消する。この欲張り法は、計算効率は良いが、常に最適なグリッドフィッティング構成を見つけることができるとは限らない。しかしながら、実際には、この欲張り法は、広範囲の文字にわたって高品質な結果を生み出す。衝突解消中、本方法は、セグメント対間のオリジナルの間隔又はセグメント対間のオリジナルの間隔比率を保つ試みは行わない。
【０１０２】
複数の文字にわたって外観の一貫性を改善するために、本方法は、常に、最も上側の水平セグメント対及び最も下側の水平セグメント対を最も近接したグリッド点にアラインする。同様に、本方法は、常に、最も左側の垂直セグメント対及び最も右側の垂直セグメント対を最も近接したグリッド点にアラインする。この手法によって、例えば衝突解消に起因するさらなるグリッドフィッティング調整が、文字のエッジにおける重要な水平の特徴及び垂直の特徴に影響を与えることが防止され、その結果、複数の文字が共に観察されるときに、それら複数の文字間でのこれらの特徴のアラインメントがより良好なものとなる。
【０１０３】
本方法は、水平セグメント対及び垂直セグメント対を別個に且つ独立にフィッティングする。本方法は、水平セグメント対と垂直セグメント対との間の依存関係を含まないので、ハードウェアの実施態様及びマルチコアの実施態様は、水平セグメント対に対するグリッドフィッティング及び垂直セグメント対に対するグリッドフィッティングを完全に並列に行うことができる。
【０１０４】
本方法は、文字をレンダリングするためのＴｒｕｅＴｙｐｅの規則に従う。ここで、レンダリングは、ピクセル中心に位置するサンプルを使用して行われる。したがって、本方法は、例えば０．５、１．５、及び２．５といった半整数に座標をアラインすることによってグリッドフィッティングを行う。性能を最適化し且つ浮動小数点の実施態様と固定小数点の実施態様との間のコード再利用を最大にするために、本方法のステップ８〜１１（下記参照）は、整数ピクセルグリッドを使用してグリッドフィッティングを行う。半整数のサンプリンググリッドに対応するために、整数のヒンティングされた座標に対して調整を行うことは、本方法のステップ１２（下記参照）で行われる。
【０１０５】
方法の説明
図２Ａ及び図２Ｂは、本発明の実施形態による文字の輪郭を複数アラインメントゾーンにアラインするための方法のステップをより詳細に示す。
【０１０６】
ステップ１。入力ペンコマンド２１３から点２１１及び輪郭２１２を求める（２０１）。図３は、７２個の点及び５つの輪郭を有する文字を示す。
【０１０７】
ステップ２。文字における外側輪郭の向き２１４を判断する（２０２）。輪郭は、時計回りに方向付けられている可能性もあるし、反時計回りに方向付けられている可能性もある。この判断は、以下のステップによって行われる。
【０１０８】
ステップ２ａ。文字内の、最小のオリジナルのｙ座標を有する点であるｐＭｉｎＹを求める。座標ｐＭｉｎＹは、文字の外側輪郭Ｃに含まれる。
【０１０９】
ステップ２ｂ。３つの点（ｐＭｉｎＹ、ｐＭｉｎＹＮ、及びｐＭｉｎＹＰ）によって規定される三角形の符号付き面積Ａを計算する。ここで、ｐＭｉｎＹＮは、ｐＭｉｎＹの直後に続く点であり、ｐＭｉｎＹＰは、ｐＭｉｎＹの直前に先行する点である。
【０１１０】
ステップ２ｃ。Ａが正である場合、輪郭Ｃは時計回りに方向付けられており、ステップ（２ｈ）に進む。
【０１１１】
ステップ２ｄ。Ａが負である場合、輪郭Ｃは反時計回りに方向付けられており、ステップ（２ｈ）に進む。
【０１１２】
ステップ２ｅ。それ以外の場合、Ａは０又はほぼ０であり、したがって、３つの点（ｐＭｉｎＹ、ｐＭｉｎＹＮ、及びｐＭｉｎＹＰ）は、共線であるか又はほぼ共線である。ｐＭｉｎＹＮがｐＭｉｎＹＰの左側にある場合、輪郭Ｃは時計回りに方向付けられ、ステップ（２ｈ）に進む。
【０１１３】
ステップ２ｆ。ｐＭｉｎＹＮがｐＭｉｎＹＰの右側にある場合、輪郭Ｃは反時計回りに方向付けられ、ステップ（２ｈ）に進む。
【０１１４】
ステップ２ｇ。ｐＭｉｎＹＮ及びｐＭｉｎＹＰは、同一のオリジナルのｘ座標を有し、そこで、文字は、ｐＭｉｎＹの周りに縮退する（degenerate around）。３つの点ｐＭｉｎＹ、ｐＭｉｎＹＮ、及びｐＭｉｎＹＰを検査することによってＣの向きを判断することは不可能であり、そこで、Ｃの向きは時計回りであると仮定する。
【０１１５】
ステップ２ｈ。終了。
【０１１６】
輪郭Ｃの向きは、文字におけるすべての外側輪郭の向きであると仮定される。
【０１１７】
ステップ３。部首２１５を求める（２０３）。図４は、図３の輪郭２１２の３つの部首２１５を示す。グリッドフィッティングは、各部首２１５について独立に行われる。部首は、単一のルート輪郭及びその子孫のすべてを含む輪郭の集合である。部首は、以下の２つのステップを使用して求められる。
【０１１８】
ステップ３ａ。各輪郭の親を求める。このステップは、輪郭の非循環有向グラフ（ＤＡＧ）２３５を効果的に構築する。ＤＡＧでは、各輪郭はその親にリンクされる。ルート輪郭は親を有しない。すなわち、ルート輪郭は、ＤＡＧ内の「最も上側」の要素である。
【０１１９】
ステップ３ｂ。各輪郭を含む部首を求める。各輪郭Ｉは、ルート輪郭である唯一の先祖Ｒを有する。親を有しない輪郭が見つかるまで、Ｉの親リンクに繰り返し従うことによって、すなわちＩ→親、Ｉ→親→親等によって、Ｒを求める。この輪郭がＲである。このステップは、「上端」の層のルート輪郭及び「下端」の層の内部輪郭を有する２つの層にＤＡＧ階層を効果的に「平坦化」する。
【０１２０】
ステップ４。単純セグメント２１６を求める（２０４）。水平単純セグメント及び垂直単純セグメントは、点２１１をトラバースし、上述したような水平単純セグメント及び垂直単純セグメントの定義を適用することによって求められる。
【０１２１】
ステップ５。各部首２１５について、マージセグメント２１７を求める（２０５）。各部首Ｒ  ２１５について、上述した水平マージセグメントの定義を適用することによって、Ｒ内の水平単純セグメントを水平マージセグメントにマージする。同様に、各部首Ｒ  ２１５について、上述した垂直マージセグメントの定義を適用することによって、Ｒ内の垂直単純セグメントを垂直マージセグメントにマージする。マージセグメントは、単純セグメントのリンクリストを使用して表される。これらのリンクリスト内では、単純セグメントの順序付けには意義はない。
【０１２２】
ステップ６。各部首Ｒ  ２１５について、Ｒの水平マージセグメントから水平セグメント対２１８を求め（２０６）、Ｒの垂直マージセグメントから垂直セグメント対を求める（２０６）。図５Ａは線セグメント２１６の５つの対２１８を示し、図５Ｂは１つの部首２１５に対するすべての対２１８を示す。
【０１２３】
水平セグメント対は、すべての可能な水平セグメント対｛Ｈ１，Ｈ２｝を考慮する総当り法を使用して求められる。ここで、Ｈ１及びＨ２は、Ｒ内の水平マージセグメントである。｛Ｈ１，Ｈ２｝は、以下の条件のすべてが満たされる場合で且つその場合に限り、有効なセグメント対となる。
【０１２４】
１．｛Ｈ１，Ｈ２｝が、文字の充填領域に及んでいなければならない。これは、（１）Ｈ１が左から右に方向付けられ、文字の外側輪郭が反時計回りに方向付けられている場合、又は（２）Ｈ１が右から左に方向付けられ、文字の外側輪郭が時計回りに方向付けられている場合、のいずれかで起こる。文字の外側輪郭の向きは、上記のステップ２において求められる。
【０１２５】
２．｛Ｈ１，Ｈ２｝の第１の対の幅が、実数値の画像座標において最大でも（ＭＡＸ＿ＷＩＤＴＨ＿ＦＲＡＣ＊ｐｐｅｍ）単位でなければならない。ここで、ｐｐｅｍは、文字をレンダリングするのに使用されるユーザ指定のエム当たりのピクセル数であり、ＭＡＸ＿ＷＩＤＴＨ＿ＦＲＡＣは、指定された所定の定数である。
【０１２６】
３．Ｈ１とＨ２との間の重なり合い比が、少なくともＭＩＮ＿ＯＶＥＲＬＡＰ＿ＲＡＴＩＯでなければならない。ここで、ＭＩＮ＿ＯＶＥＲＬＡＰ＿ＲＡＴＩＯは、指定された所定の定数である。
【０１２７】
４．ｗを、｛Ｈ１，Ｈ２｝の第１の対の幅であるとする。｛Ｈ３，Ｈ２｝の第１の対の幅がｗ未満となるような、Ｒ内の水平マージセグメントＨ３は存在し得ない。同様に、｛Ｈ１，Ｈ３｝の第１の対の幅がｗ未満となるような、Ｒ内の水平マージセグメントＨ３も存在し得ない。直感的に、｛Ｈ１，Ｈ２｝は、Ｈ１又はＨ２のいずれかを含むすべての可能な水平セグメント対にわたり最も細い水平セグメント対でなければならない。
【０１２８】
垂直セグメント対は、ｙ座標の代わりにｘ座標を用いて、水平セグメント対と同じ方法で求められる。
【０１２９】
ステップ７。各部首Ｒ  ２１５について、Ｒ内の各水平セグメント対を、初期化されていない水平セグメント対アレイ２１９にアペンドする（２０７）。同様に、各部首Ｒ  ２１５について、Ｒ内の各垂直セグメント対を、初期化されていない垂直セグメント対アレイにアペンドする。
【０１３０】
ステップ８。水平セグメント対アレイ２１９内の各水平セグメント対のヒンティングされた座標２２０を、その水平セグメント対のオリジナルの座標のフロアを計算することによって求める（２５８）。同様に、垂直セグメント対アレイ内の各垂直セグメント対のヒンティングされた座標を、その垂直セグメント対のオリジナルの座標のフロアを計算することによって求める。このステップにおいて求められるセグメント対のヒンティングされた座標は、衝突を解消するために下記で修正することができる。これについては、ステップ１１を参照されたい。
【０１３１】
ステップ９。水平セグメント対アレイ内の水平セグメント対を昇順にソートする（２５９）。すなわち、オリジナルの座標が減少しない順でソートする。同様に、垂直セグメント対アレイ内の垂直セグメント対を昇順にソートする。すなわち、オリジナルの座標が減少しない順でソートする。このように、アレイ２２１はソートされる。
【０１３２】
ステップ１０。水平セグメント対アレイ内の各水平セグメント対の子セグメント対を識別し（２６０）、非循環有向グラフ（ＤＡＧ）２２２を構成する。同様に、垂直セグメント対アレイ内の各垂直セグメント対の子セグメント対を識別し、対応するＤＡＧを構成する。これらのＤＡＧは、各セグメント対をその子セグメント対にリンクすることによって暗黙的に表される。
【０１３３】
これらのＤＡＧを構成する目的は、ステップ１１においてセグメント対間の衝突を検出して解消することである。セグメント対Ｐと子セグメント対Ｃとの現在のヒンティングされた座標２２０の差がＷ＋２ピクセルよりも大きく異なる場合、ＰとＣとの間の衝突は、衝突解消中に起こり得ない。ここで、Ｗは、Ｃのオリジナルの対の幅を最も近い整数に丸めた（rounded:四捨五入した）ものに等しい。したがって、ランタイム効率を改善するために、ＰとＣとのヒンティングされた座標の差が（Ｗ＋２）ピクセル以下である場合で且つその場合に限り、ＤＡＧ内のリンクがＰとＣとの間に加えられる。
【０１３４】
ステップ１１。欲張りボトムアップ法を使用して、衝突セグメント対を検出し（２６１）、ステップ８において発生した衝突を解消する。視覚的には、衝突セグメント対は、２つの別個のセグメント対ではなく、単一の太いセグメント対であるように見える。衝突は、いくつの場合には、２つのセグメント対が１ピクセルさらに離れるように、それらセグメント対の一方のヒンティングされた座標に＋１又は−１を加えることによって解消することができる。これについては、下記の詳細を参照されたい。
【０１３５】
衝突は、ステップ１０において求められたセグメント対の各ＤＡＧがボトムアップ順で、すなわち最も下側の子孫から最も上側の先祖へ方向付けてトラバースされる、欲張り法を使用して解消される。セグメント対は、ステップ９において昇順にソートされるので、このボトムアップのトラバースは、セグメント対アレイ内の最初のセグメント対から開始してセグメント対アレイ内の各セグメント対を訪問し、セグメント対アレイ内の最後のセグメント対で終了することにより達成される。
【０１３６】
Ｍ１及びＭ２を、セグメント対アレイ内の最初のセグメント対及び最後のセグメント対の現在のヒンティングされた座標であるとする。複数の文字にわたり重要な特徴の一貫したアラインメントを得るために、現在のヒンティングされた座標がＭ１に等しいすべてのセグメント対は、引き続きＭ１に固定される。すなわち、これらのセグメント対は、衝突解消による影響を受けない。同様に、現在のヒンティングされた座標がＭ２に等しいすべてのセグメント対は、引き続きＭ２に固定される。
【０１３７】
セグメント対アレイのボトムアップトラバース中に訪問された各セグメント対Ｐについて、以下のステップを適用する。
【０１３８】
ステップ１１ａ。Ｐの現在のヒンティングされた座標がＭ１に等しい場合、次のセグメント対に進む。
【０１３９】
ステップ１１ｂ。Ｐの現在のヒンティングされた座標がＭ２に等しい場合、Ｐと衝突するＰの各子Ｃについて以下のステップを適用する。
【０１４０】
ステップ１１ｂ１。ＣがＰとわずかに衝突する場合、ステップ（１１ｂ２）に進む。そうでない場合、ステップ（１１ｂ４）に進む。
【０１４１】
ステップ１１ｂ２。Ｃが切り上げられるが、その子のいずれとも衝突することなく切り捨てることができる場合、Ｃを切り捨て、ステップ（１１ｂ５）に進む。
【０１４２】
例：Ｃのオリジナルの座標が３．４である場合、Ｃのヒンティングされた座標は、通常、３．０に「切り上げられる」。切り上げる代わりに「切り捨てる」ことによって、整数２．０が生成される。上記の衝突の専門用語のセクションにおける「切り上げる」及び「切り捨てる」の定義を参照されたい。このステップは、衝突の除去を試み、あらゆる新しい衝突の導入を常に回避する。
【０１４３】
ステップ１１ｂ３。Ｃが切り上げられるが、ルートＣを有するセグメント対ツリーにおいて衝突を何ら生み出すことなく、ルートＣを有するセグメント対ツリーを切り捨てることができる場合、そのセグメントツリーを切り捨て、ステップ（１１ｂ５）に進む。このステップは、衝突の除去を試み、あらゆる新しい衝突の導入を常に回避する。
【０１４４】
ステップ１１ｂ４。ＰがまだＣと衝突する場合、ＣをＰにアラインする。例えば、Ｃのヒンティングされた座標が４．０であり、Ｐのヒンティングされた座標は５．０であり、Ｃの対の幅が１．２ピクセルである場合、Ｃを５．０にアラインする。
【０１４５】
ステップ１１ｂ５。終了。
【０１４６】
ステップ１１ｃ。Ｐの現在のヒンティングされた座標がＭ１とＭ２との間にある場合、Ｐと衝突するＰの各子Ｃについて以下のステップを適用する。
【０１４７】
ステップ１１ｃ１。ＣがＰとわずかに衝突する場合、ステップ（１１ｃ２）に進む。そうでない場合、ステップ（１１ｃ５）に進む。
【０１４８】
ステップ１１ｃ２。Ｃが切り上げられるが、その子のいずれとも衝突することなく切り捨てることができる場合、Ｃを切り捨て、ステップ（１１ｃ６）に進む。例えば、Ｃのオリジナルの座標が３．４である場合、Ｃのヒンティングされた座標は、通常、３．０に「切り上げられる」。切り上げる代わりに「切り捨てる」ことによって、整数２．０が生成される。上記の衝突の専門用語のセクションにおける「切り上げる」及び「切り捨てる」の定義を参照されたい。このステップは、衝突の除去を試み、あらゆる新しい衝突の導入を常に回避する。
【０１４９】
ステップ１１ｃ３。Ｃが切り上げられるが、ルートＣを有するセグメント対ツリーを、セグメント対ツリーにおける衝突を何ら生み出すことなく切り捨てることができる場合、セグメント対ツリーを切り捨て、ステップ（１１ｃ６）に進む。このステップは、衝突の除去を試み、あらゆる新しい衝突の導入を常に回避する。
【０１５０】
ステップ１１ｃ４。Ｐが切り捨てられる場合、Ｐを切り上げて、ステップ（１１ｃ６）に進む。例：Ｐのオリジナルの座標が５．８である場合、Ｐのヒンティングされた座標は、通常、５．０、すなわちｆｌｏｏｒ（５．８−０．５）＝ｆｌｏｏｒ（５．３）＝５．０に切り捨てられる。切り捨てる代わりに切り上げることによって、整数６．０が生成される。このステップは、衝突の除去を試みるが、ＰとＰの親との間の衝突を導入する場合がある。この起こり得る衝突は、ＤＡＧのボトムアップトラバースの後続の繰り返しにおいてＰの親を処理する時に対処される。
【０１５１】
ステップ１１ｃ５。ＰをＣにアラインする。例えば、Ｃのヒンティングされた座標が４．０であり、Ｐのヒンティングされた座標が５．０である場合、Ｐを４．０にアラインする。
【０１５２】
ステップ１１ｃ６。終了し、衝突は、セグメント対のアレイ２２３から除去されている。
【０１５３】
ステップ１１について、ステップ（１１ｂ２）〜（１１ｂ３）及びステップ（１１ｃ２）〜（１１ｃ４）は、セグメント対Ｃ及びＰが少なくともＷ＋１ピクセル離れるようにそれらセグメント対を丸めることを試みる。ここで、Ｗは、Ｃのオリジナルの対の幅である。しかしながら、この方法によって衝突を解消できないいくつかの場合がある。Ｃ及びＰは、これらの場合に視覚的に区別することができないので、ステップ（１１ｂ４）及び（１１ｃ５）は、Ｐ及びＣをアラインし、それによって、２つのセグメント対を同じ座標にアラインすることにより文字の外見を単純にする。ステップ（１１ｂ４）とステップ（１１ｃ５）との間の相違は、前者のステップでは、ＣがＰにアラインされるのに対して、後者のステップでは、ＰがＣにアラインされるということである。
【０１５４】
ステップ１２。水平セグメント対アレイ２２３内の各水平セグメント対｛Ｓ１，Ｓ２｝をグリッドフィッティングする（２６２）。
【０１５５】
ステップ１２ａ。実数値の画像座標における｛Ｓ１，Ｓ２｝のオリジナルの対の幅ｗを求める。
【０１５６】
ステップ１２ｂ。以下の通りに｛Ｓ１，Ｓ２｝の調整された対の幅ｗ'を求める。ｗ'をｗに初期化する。ｗ'が０．５未満である場合、ｗ'を０．５に設定する。ｗ'が１．０未満である場合、ｗ'＝ｗ'＋ｆ＊（１−ｗ'）に設定する。ここで、ｆは、対の幅の調整係数である。値ｆは、（ｐｐｅｍ＊０．０６２５−０．８７５）として計算され、範囲［０，１］にクランプされる。このステップによって、オリジナルの対の幅はｐｐｅｍに依存した量だけ増加され、細いセグメント対の視認性及びコントラストが増加される。
【０１５７】
対の幅の調整係数ｆは、範囲［０，１］内にあり、ｐｐｅｍ＝１４の時は０からの線形ランプとして振る舞い、ｐｐｅｍ＝３０の時は１への線形ランプとして振る舞う。したがって、対の幅の調整係数は、１４ｐｐｅｍで最小となり、３０ｐｐｅｍで最大となる。これらの値は、コントラストと一貫性との間の良好なバランスを達成するために経験的に求められたものである。
【０１５８】
ステップ１２ｃ。以下の通りにＳ１及びＳ２の点をグリッドフィッティングする。ｏｍｙ１及びｏｍｙ２を、それぞれＳ１及びＳ２のオリジナルの中間ｙ座標であるとする。Ｓ１のヒンティングされたｙ座標ｈｙ１は、ステップ８及びステップ１１によりこれに先立って求められている。上記を参照されたい。
【０１５９】
調整された対の幅、すなわちｗ'を、Ｓ１のヒンティングされたｙ座標、すなわちｈｙ１に加えることによって、Ｓ２のヒンティングされたｙ座標ｈｙ２を求める。
【０１６０】
Ｓ１に含まれる各点Ｐについて、（ｈｙ１−ｏｍｙ１＋０．５）をＰのオリジナルのｙ座標に加えることによって、Ｐのヒンティングされたｙ座標を求める。このステップは、Ｓ１のオリジナルの勾配を効果的に保つ。０．５の追加のデルタによって、点Ｐは、半整数ピクセルグリッドにアラインされる。
【０１６１】
Ｓ２に含まれる各点Ｐについて、（ｈｙ２−ｏｍｙ２＋０．５）をＰのオリジナルのｙ座標に加えることによって、Ｐのヒンティングされたｙ座標を求める。このステップは、Ｓ２のオリジナルの勾配を効果的に保つ。０．５の追加のデルタによって、点Ｐは、半整数ピクセルグリッドにアラインされる。
【０１６２】
ｙ座標の代わりにｘ座標を用い、水平セグメント対について上述したのと同じ方法を使用して、垂直セグメント対アレイ内の各垂直セグメント対をグリッドフィッティングする（２６２）。
【０１６３】
ステップ１３。各部首Ｒ  ２１５について、Ｒ内のｘフリー点に対してグリッドフィッティングを行う（２６３）。
【０１６４】
ステップ１３ａ。点Ｐを、Ｒ内のｘフリー点であるとする。Ｐの先行ｘアンカ点Ａ１及びＰの次ｘアンカ点Ａ２を求める。点Ｐは、アンカ点を一切有しない場合がある。すなわち、Ａ１もＡ２も存在しない。
【０１６５】
ステップ１３ｂ。Ｐのアンカ点のいずれもが存在しない場合、ステップ（１３ｇ）に進む。点Ｐは、正確に０個のアンカ点を有するか又は正確に２つのアンカ点を有するかのいずれかである。
【０１６６】
ステップ１３ｃ。Ｐ、Ａ１、及びＡ２の間のオリジナルのｘ比ｘｒを求める。ｘｒが未定義である場合、すなわち、Ａ１及びＡ２が同一のオリジナルのｘ座標を有し、したがって、ｘｒの分母が０である場合、点Ｐと点Ａ１との間のオリジナルのｘ距離を保つことによってＰのヒンティングされたｘ座標を求め、ステップ（１３ｇ）に進む。
【０１６７】
ステップ１３ｄ。ｘｒが０よりも小さい場合、（１）Ｐのオリジナルのｘ座標は、Ａ２のオリジナルのｘ座標よりもＡ１のオリジナルのｘ座標に近く、且つ（２）Ｐのオリジナルのｘ座標は、アンカ点のオリジナルのｘ座標間にない。この場合、点Ｐと点Ａ１との間のオリジナルのｘ距離を保つことによってＰのヒンティングされたｘ座標を求め、ステップ（１３ｇ）に進む。
【０１６８】
ステップ１３ｅ。ｘｒが１よりも大きい場合、（１）Ｐのオリジナルのｘ座標は、Ａ１のオリジナルのｘ座標よりもＡ２のオリジナルのｘ座標に近く、且つ（２）Ｐのオリジナルのｘ座標は、アンカ点のオリジナルのｘ座標間にない。この場合、点Ｐと点Ａ２との間のオリジナルのｘ距離を保つことによってＰのヒンティングされたｘ座標を求め、ステップ（１３ｇ）に進む。
【０１６９】
ステップ１３ｆ。ｘｒは範囲［０，１］内にあり、したがって、Ｐのオリジナルのｘ座標は、（１）Ａ１のオリジナルのｘ座標に等しいか、（２）Ａ２のオリジナルのｘ座標に等しいか、又は（３）アンカ点のオリジナルのｘ座標間にある。アンカ点のヒンティングされたｘ座標間を直線補間することによって、Ｐのヒンティングされたｘ座標を求める。
【０１７０】
ステップ１３ｇ。終了。
【０１７１】
各部首Ｒ  ２１５について、ｘ座標の代わりにｙ座標を用い、ｘフリー点について上述したのと同じ方法を使用して、Ｒ内のｙフリー点に対してグリッドフィッティングを行う（２６３）。
【０１７２】
ステップ１４。点からのヒンティングされたｘ座標及びｙ座標を出力ペンコマンドにコピーする（２６４）。
【０１７３】
この時点で、出力ペンコマンドは、サンプリンググリッドとアラインされており、レンダリング２４０に進むことができる。
【０１７４】
動作環境
本発明は、多数の汎用又は専用のコンピューティングシステム環境又はコンピューティングシステム構成で動作可能である。本発明と共に使用するのに適した既知のコンピューティングシステム、コンピューティング環境、及び／又はコンピューティング構成の例には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルド装置又はラップトップ装置、マルチプロセッサシステム又はマルチコアシステム、グラフィックス処理ユニット（ＧＰＵ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、マイクロコントローラベースシステム、セットトップボックス、プログラマブル民生用電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記システム又は装置の任意のものを含む分散コンピューティング環境等が含まれるが、これらに限定されるものではない。モニタ又は他のタイプの表示装置が、上記システムの任意のものに接続されて、本発明のアラインメントの表示が可能にされる。
【０１７５】
上述したように、本方法は、独立したアラインメントゾーンを使用して、各部首について特徴検出を別個に且つ独立に行う。これによって、セグメント対が文字の空間的に遠い領域間で形成されることを防止することにより、特徴検出の正確度が改善される。特徴検出中、部首間の依存関係はない。その結果、ハードウェアの実施態様及びマルチコアの実施態様は、部首内の特徴検出を完全に並列に行うことができる。例えば、マルチコアプロセッサの或るコアは、或る特定の部首に対して特徴検出を行うことができ、マルチコアプロセッサの別のコアは、異なる特定の部首に対して特徴検出を行うことができる。
【０１７６】
同じく上述したように、本方法は、水平セグメント対と垂直セグメント対との間の依存関係を含まない。その結果、本方法のハードウェアの実施態様及びマルチコアの実施態様は、水平セグメント対及び垂直セグメント対を完全に並列に処理することができる。例えば、マルチコアプロセッサの或るコアは、水平セグメント対に対してアラインメントを行うことができ、マルチコアプロセッサの別のコアは、垂直セグメント対に対してアラインメントを行うことができる。
【０１７７】
本発明を特定の好ましい実施形態を参照して説明してきたが、様々な他の適合及び変更を本発明の精神及び範囲内で行うことができることを理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るような全ての変形及び変更を包含することである。
【図１Ａ】
2010170096.tif 000003
【図１Ｂ】
2010170096.tif 000004
【図２Ａ】
2010170096.tif 000005
【図２Ｂ】
2010170096.tif 000006
【図３】
2010170096.tif 000007
【図４】
2010170096.tif 000008
【図５Ａ】
2010170096.tif 000009
【図５Ｂ】
2010170096.tif 000010
【外国語明細書】
2010170096.tif 000011
2010170096.tif 000012
2010170096.tif 000013
2010170096.tif 000014
2010170096.tif 000015
2010170096.tif 000016
2010170096.tif 000017
2010170096.tif 000018
2010170096.tif 000019
2010170096.tif 000020
2010170096.tif 000021
2010170096.tif 000022
2010170096.tif 000023
2010170096.tif 000024
2010170096.tif 000025
2010170096.tif 000026
2010170096.tif 000027
2010170096.tif 000028
2010170096.tif 000029
2010170096.tif 000030
2010170096.tif 000031
2010170096.tif 000032
2010170096.tif 000033
2010170096.tif 000034
2010170096.tif 000035
2010170096.tif 000036
2010170096.tif 000037
2010170096.tif 000038
2010170096.tif 000039
2010170096.tif 000040
2010170096.tif 000041
2010170096.tif 000042
2010170096.tif 000043
2010170096.tif 000044
2010170096.tif 000045
2010170096.tif 000046
2010170096.tif 000047
2010170096.tif 000048
2010170096.tif 000049
2010170096.tif 000050
2010170096.tif 000051
2010170096.tif 000052
2010170096.tif 000053
2010170096.tif 000054
2010170096.tif 000055
2010170096.tif 000056
2010170096.tif 000057
2010170096.tif 000058
2010170096.tif 000059
2010170096.tif 000060
2010170096.tif 000061