(57)【特許請求の範囲】
【請求項１】
ソースフォントデータからフォントフォーマットデータを生成するシステムであって、
コンピュータ読み取り可能媒体内に格納されたグリフ分析ソフトウェアモジュールであって、該グリフ分析ソフトウェアモジュールは、複数のグリフの各グリフに対するグリフデータを含む該ソースフォントデータを分析することをコンピュータデバイスに行わせるように動作可能なコンピュータ実行可能命令を含み、該グリフ分析ソフトウェアモジュールのコンピュータ実行可能命令は、該ソースフォントデータから該複数のグリフに含まれている輪郭を内部輪郭および外部輪郭に分けることと、該分けられた内部輪郭および外部輪郭に基づいて各グリフに対して１組の個別形状を決定することと、該決定に基づいて各グリフに対する個別形状データを取得することとをコンピュータデバイスに行わせるように動作可能な命令を含み、各個別形状は、１つ以上の輪郭を含む、グリフ分析ソフトウェアモジュールと、
コンピュータ読み取り可能媒体内に格納されたグリフ分離ソフトウェアモジュールであって、該グリフ分離ソフトウェアモジュールは、ストロークの第１および第２の辺を定義するための開始点として該個別形状データから一対の点を選択することと、該選択された開始点から該ストロークの該第１および第２の辺の点をインクリメントすることと、該インクリメントされた点が２つ以上のストロークが互いに交差する該グリフにおけるターンに対応する候補点であるか否かを決定することと、該インクリメントされた点が候補点である場合には、ペンの自然な移動を表す移動ベクトルに従って、インクリメントされるべき次の点を複数の潜在的移動先点から選択することと、該開始点と各ストロークに関連付けられた点がインクリメントされた経路とを含むストロークデータを格納することとをコンピュータデバイスに行わせるように動作可能なコンピュータ実行可能命令を含む、グリフ分離ソフトウェアモジュールと、
コンピュータ読み取り可能媒体内に格納された中線抽出ソフトウェアモジュールであって、該中線抽出ソフトウェアモジュールは、
該ストロークデータに含まれる各ストロークに対して、
当該ストロークの該第１の辺の上の各点に対して、当該ストロークの該第２の辺における対応する最も近い点を見つけることと、該第１の辺の上の点と該第２の辺における対応する最も近い点との中点を決定することと、該第１の辺の上の点と該第２の辺における対応する最も近い点との中点を含む中線データを格納することと、
当該ストロークの該第２の辺の上の各点に対して、当該ストロークの該第１の辺における対応する最も近い点を見つけることと、該第２の辺の上の点と該第１の辺における対応する最も近い点との中点を決定することと、該第２の辺の上の点と該第１の辺における対応する最も近い点との中点を含む中線データを格納することと
をコンピュータデバイスに行わせるように動作可能なコンピュータ実行可能命令を含む、中線抽出ソフトウェアモジュールと、
コンピュータ読み取り可能媒体内に格納されたエレメント分析ソフトウェアモジュールであって、該エレメント分析ソフトウェアモジュールは、
２つ以上のグリフに共通のエレメントに対応する共通エレメントデータをソースデータベースから取得することと、
該グリフ分析ソフトウェアモジュールによって決定された各グリフに対する該１組の個別形状のうちの各個別形状に対して、
該個別形状の該中線データを該共通エレメントデータと比較することと、
該個別形状の該中線データが該共通エレメントのデータとマッチする場合に、該個別形状を共通エレメントとして識別するために共通エレメント識別子を使用することと、
該個別形状の該中線データがいずれの共通エレメントデータともマッチしない場合に、特定のグリフに対して一意である一意のエレメントとして該個別形状を識別することと、
該個別形状を一意のエレメントとして識別するために一意のエレメント識別子を使用することと
をコンピュータデバイスに行わせるように動作可能なコンピュータ実行可能命令を含む、エレメント分析ソフトウェアモジュールと
を含む、システム。
【請求項２】
前記グリフ分析ソフトウェアモジュールのコンピュータ実行可能命令は、
前記ソースフォントデータから前記複数のグリフに含まれている輪郭を前記内部輪郭および前記外部輪郭に分けることをコンピュータデバイスに行わせるように動作可能な輪郭分析ソフトウェア命令と、
各グリフに対する前記１組の個別形状を決定することをコンピュータデバイスに行わせるように動作可能な内容分析ソフトウェア命令と
を含む、請求項１に記載のシステム。
【請求項３】
前記グリフ分析ソフトウェアモジュールのコンピュータ実行可能命令は、クラスタ除去プロセスとベジエ円弧低減プロセスと多角形単純化プロセスとを行うことをコンピュータデバイスに行わせるように動作可能なグリフ単純化ソフトウェア命令をさらに含む、請求項１に記載のシステム。
【請求項４】
前記グリフ分析ソフトウェアモジュールのコンピュータ実行可能命令は、各グリフの各個別形状における各点に対して、該点が凸角タイプの点であるか優角タイプの点であるかを決定することと、各グリフの各個別形状における各点に対して、各点に関連付けられた有効な隣接点を決定することとをコンピュータデバイスに行わせるように動作可能な輪郭点分析ソフトウェア命令をさらに含む、請求項１に記載のシステム。
【請求項５】
前記グリフ分離ソフトウェアモジュールのコンピュータ実行可能命令は、
前記移動ベクトルに従って、前記候補点とインクリメントされるべき次の点とをイベントデータとして格納することと、
個別形状データを次にストロークデータに分離するために開始点として該イベントデータを選択することと
をコンピュータデバイスに行わせるように動作可能な命令をさらに含む、請求項１に記載のシステム。
【請求項６】
前記移動ベクトルに従って、インクリメントされるべき次の点を選択することを前記コンピュータデバイスに行わせるように動作可能な命令は、潜在的な移動先点の各々に対して、候補点と既にインクリメントされた点と潜在的な移動先点とを含む三つ組みによって定義される角度と水平角との差を平坦度閾値の値と比較することと、該比較に基づいて該潜在的な移動先点が有効か否かを決定することとをコンピュータデバイスに行わせるように動作可能な命令を含む、請求項１に記載のシステム。
【請求項７】
前記個別形状データから前記開始点を選択することをコンピュータデバイスに行わせるように動作可能な命令は、
各グリフに含まれる点の位置に従って該個別形状データから最初の開始点を識別することと、
該最初の開始点における角度と開始閾値の値とを比較し、該最初の開始点における角度が該開始閾値の値より下であるか否か、または、該開始閾値の値より上であるか否かに基づいて該最初の開始点を分類することと、
該分類された開始点の優先順位を付けて最も優先順位の高い分類された開始点を選択することと
をコンピュータデバイスに行わせるように動作可能な命令を含む、請求項１に記載のシステム。
【請求項８】
前記グリフ分離ソフトウェアモジュールのコンピュータ実行可能命令は、前記個別形状データの分離の後に連結されたストロークの各々に関連付けられた個別データを組み合わせることにより、連結されたストロークに関連付けられた統合データを形成することによって、各グリフに対するストロークデータをマージすることをコンピュータデバイスに行わせるように動作可能な命令をさらに含む、請求項１に記載のシステム。
【請求項９】
前記個別形状データの分離の後に各グリフに対するストロークデータをマージすることをコンピュータデバイスに行わせるように動作可能な命令は、
該ストロークの両辺でイベントが発生するときに、明示的に連結されたストロークを識別することと、
１つのストロークの端点が別のストロークの開始点であるときに、暗示的に連結されたストロークを識別することと、
該明示的に連結されたストロークの各々に関連付けられた個別データを組み合わせることにより、明示的に連結されたストロークに関連付けられた統合データを形成することによって、明示的に連結されたストロークデータをマージすることと、
該暗示的に連結されたストロークの各々に関連付けられた個別データを組み合わせることにより、暗示的に連結されたストロークに関連付けられた統合データを形成することによって、暗示的に連結されたストロークデータをマージすることと
をコンピュータデバイスに行わせるように動作可能な命令を含む、請求項８に記載のシステム。
【請求項１０】
前記エレメント分析ソフトウェアモジュールのコンピュータ実行可能命令は、
前記共通エレメント識別子と、対応する前記抽出された共通エレメントデータに関する前記中線データのシフトおよびスケールとをフォントフォーマットデータ構造に格納することと、
前記一意のエレメントデータを該データ構造に格納することと、
該共通エレメント識別子および前記共通エレメントデータを共通エレメントデータベースに格納することと
をコンピュータデバイスに行わせるように動作可能な命令をさらに含み、
各グリフのスケルトンは、該共通エレメントにマッチする該中線データと前記一意のエレメントとによって定義される、請求項１に記載のシステム。
【請求項１１】
ソースフォントデータからフォントフォーマットデータを生成する方法であって、
複数のグリフの各グリフに対するグリフデータを含む該ソースフォントデータを分析することであって、該ソースフォントデータを分析することは、該ソースフォントデータから該複数のグリフに含まれている輪郭を内部輪郭および外部輪郭に分けることと、該分けられた内部輪郭および外部輪郭に基づいて各グリフに対して１組の個別形状を決定することと、該決定に基づいて各グリフに対する個別形状データを取得することとを含み、各個別形状は、１つ以上の輪郭を含む、ことと、
ストロークの第１および第２の辺を定義するための開始点として該個別形状データから一対の点を選択し、該選択された開始点から該ストロークの該第１および第２の辺の点をインクリメントし、該インクリメントされた点が２つ以上のストロークが互いに交差する該グリフにおけるターンに対応する候補点であるか否かを決定し、該インクリメントされた点が候補点である場合には、ペンの自然な移動を表す移動ベクトルに従って、インクリメントされるべき次の点を複数の潜在的移動先点から選択し、該開始点と各ストロークに関連付けられた点がインクリメントされた経路とを含むストロークデータを格納することと、
該ストロークデータに含まれる各ストロークに対して、
当該ストロークの該第１の辺の上の各点に対して、当該ストロークの該第２の辺における対応する最も近い点を見つけることと、該第１の辺の上の点と該第２の辺における対応する最も近い点との中点を決定することと、該第１の辺の上の点と該第２の辺における対応する最も近い点との中点を含む中線データを格納することと、
当該ストロークの該第２の辺の上の各点に対して、当該ストロークの該第１の辺における対応する最も近い点を見つけることと、該第２の辺の上の点と該第１の辺における対応する最も近い点との中点を決定することと、該第２の辺の上の点と該第１の辺における対応する最も近い点との中点を含む中線データを格納することと、
２つ以上のグリフに共通のエレメントに対応する共通エレメントデータをソースデータベースから取得することと、
該ソースフォントデータを分析するステップにおいて決定された各グリフに対する該１組の個別形状のうちの各個別形状に対して、
該個別形状の該中線データを該共通エレメントデータと比較することと、
該個別形状の該中線データが該共通エレメントのデータとマッチする場合に、該個別形状を共通エレメントとして識別するために共通エレメント識別子を使用することと、
該個別形状の該中線データがいずれの共通エレメントデータともマッチしない場合に、特定のグリフに対して一意である一意のエレメントとして該個別形状を識別することと、
該個別形状を一意のエレメントとして識別するために一意のエレメント識別子を使用することと
を含む、方法。
【請求項１２】
前記ソースフォントデータを分析することは、
前記ソースフォントデータから前記複数のグリフに含まれている輪郭を前記内部輪郭および前記外部輪郭に分けることと、
各グリフに対する前記１組の個別形状を決定することと
を含む、請求項１１に記載の方法。
【請求項１３】
前記ソースフォントデータを分析することは、クラスタ除去プロセスとベジエ円弧低減プロセスと多角形単純化プロセスとを行うことをさらに含む、請求項１２に記載の方法。
【請求項１４】
前記ソースフォントデータを分析することは、各グリフの各個別形状における各点に対して、該点が凸角タイプの点であるか優角タイプの点であるかを決定することと、各グリフの各個別形状における各点に対して、各点と関連付けられた有効な隣接点を決定することとを含む、請求項１２に記載の方法。
【請求項１５】
前記ストロークデータを格納することは、前記移動ベクトルに従って、前記候補点とインクリメントされるべき前記次の点とをイベントデータとして格納することと、前記個別形状データから一対の点を開始点として選択することとを含み、
該個別形状データから一対の点を開始点として選択することは、該個別形状データを次にストロークデータに分離するために開始点として該イベントデータを選択することをさらに含む、請求項１１に記載の方法。
【請求項１６】
前記移動ベクトルに従って、インクリメントされるべき次の点を選択することは、
潜在的な移動先点の各々に対して、候補点と既にインクリメントされた点と潜在的な移動先点とを含む三つ組みによって定義される角度と水平角の差を平坦度閾値の値と比較することと、
該比較に基づいて該潜在的な移動先点が有効か否かを決定することと
を含む、請求項１１に記載の方法。
【請求項１７】
前記個別形状データから前記開始点を選択することは、
各グリフに含まれる点の位置に従って該個別形状データから最初の開始点を識別することと、
該最初の開始点における角度と開始閾値の値とを比較し、該最初の開始点における角度が該開始閾値の値より下であるか否か、または、該開始閾値の値より上であるか否かに基づいて該最初の開始点を分類することと、
該分類された開始点の優先順位を付けることと、
最も優先順位の高い分類された開始点を選択することと
を含む、請求項１１に記載の方法。
【請求項１８】
前記ストロークデータを格納することは、
前記個別形状データの分離の後に連結されたストロークの各々に関連付けられた個別データを組み合わせることにより、連結されたストロークに関連付けられた統合データを形成することによって、各グリフに対するストロークデータをマージすることをさらに含む、請求項１１に記載の方法。
【請求項１９】
前記個別形状データの分離の後に各グリフに対するストロークデータをマージすることは、
該ストロークの両辺でイベントが発生するときに、明示的に連結されたストロークを識別することと、
１つのストロークの端点が別のストロークの開始点であるときに、暗示的に連結されたストロークを識別することと
該明示的に連結されたストロークの各々に関連付けられた個別データを組み合せることにより、明示的に連結されたストロークに関連付けられた統合データを形成することによって、明示的に連結されたストロークデータをマージすることと、
該暗示的に連結されたストロークの各々に関連付けられた個別データを組み合せることにより、暗示的に連結されたストロークに関連付けられた統合データを形成することによって、該暗示的に連結されたストロークデータをマージすることと
を含む、請求項１８に記載の方法。
【請求項２０】
前記共通エレメント識別子と、対応する前記抽出された共通エレメントデータに関する前記中線データのシフトおよびスケールとをフォントフォーマットデータ構造に格納することと、
前記一意のエレメントデータを該グリフデータ構造に格納することと、
該共通エレメント識別子および前記共通エレメントデータを共通エレメントデータベースに格納することと
をさらに含み、
各グリフのスケルトンは、該共通エレメントにマッチする該中線データと前記一意のエレメントとによって定義される、請求項１１に記載の方法。
【請求項２１】
ソースフォントデータからフォントフォーマットデータを生成するシステムであって、
複数のグリフの各グリフに対するグリフデータを含む該ソースフォントデータを分析する手段であって、該ソースフォントデータを分析する手段は、該ソースフォントデータから該複数のグリフに含まれている輪郭を内部輪郭および外部輪郭に分ける手段と、該分けられた内部輪郭および外部輪郭に基づいて各グリフに対して１組の個別形状を決定する手段と、該決定に基づいて各グリフに対する個別形状データを取得する手段とを含み、各個別形状は、１つ以上の輪郭を含む、手段と、
ストロークの第１および第２の辺を定義するための開始点として該個別形状データから一対の点を選択し、該選択された開始点から該ストロークの該第１および第２の辺の点をインクリメントし、該インクリメントされた点が２つ以上のストロークが互いに交差する該グリフにおけるターンに対応する候補点であるか否かを決定し、該インクリメントされた点が候補点である場合には、ペンの自然な移動を表す移動ベクトルに従って、インクリメントされるべき次の点を複数の潜在的移動先点から選択し、該開始点と各ストロークに関連付けられた点がインクリメントされた経路とを含むストロークデータを格納する手段と、
中線データを格納する手段であって、該中線データを格納することは、
該ストロークデータに含まれる各ストロークに対して、
当該ストロークの該第１の辺の上の各点に対して、当該ストロークの該第２の辺における対応する最も近い点を見つけることと、該第１の辺の上の点と該第２の辺における対応する最も近い点との中点を決定することと、該第１の辺の上の点と該第２の辺における対応する最も近い点との中点を含む中線データを格納することと、
当該ストロークの該第２の辺の上の各点に対して、当該ストロークの該第１の辺における対応する最も近い点を見つけることと、該第２の辺の上の点と該第１の辺における対応する最も近い点との中点を決定することと、該第２の辺の上の点と該第１の辺における対応する最も近い点との中点を含む中線データを格納することと
によって行われる、手段と、
２つ以上のグリフに共通のエレメントに対応する共通エレメントデータをソースデータベースから取得し、
該ソースフォントデータを分析する手段によって決定された各グリフに対する該１組の個別形状のうちの各個別形状に対して、
該個別形状の該中線データを該共通エレメントデータと比較し、
該個別形状の該中線データが該共通エレメントのデータとマッチする場合に、該個別形状を共通エレメントとして識別するために共通エレメント識別子を使用し、
該個別形状の該中線データがいずれの共通エレメントデータともマッチしない場合に、特定のグリフに対して一意である一意のエレメントとして該個別形状を識別し、
該個別形状を一意のエレメントとして識別するために一意のエレメント識別子を使用する手段と
を含む、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してスケーラブルストロークフォントに関し、特にスケーラブルストロークフォントを生成しスケーラブルストロークフォントデータをモバイルコンピュータデバイス（「モバイルデバイス」）に格納するシステムおよび方法に関する。
【背景技術】
【０００２】
本出願は２００２年７月３日に出願された米国特許仮出願シリアル番号第６０／３９３，７９５号および２００２年８月１日に出願された米国特許仮出願シリアル番号第６０／４００，３７３号の利益を主張し、上記仮出願の全体を参考のため援用する。
【０００３】
フォントデータなどのテキストデータは代表的にはモバイルデバイス内のメモリ内に格納される。モバイルデバイスは代表的には比較的限られたメモリおよび処理リソースを有するため、モバイルデバイスに格納されたテキストデータの量およびモバイルデバイスのテキストレンダリング能力には限界があることが多い。
【０００４】
３つの基本的なフォントタイプ、すなわちビットマップ、アウトライン、およびストロークである。ビットマップフォントは文字のグラフィック画像として格納され、タイプフェースの各ポイントサイズは別のフォントとして格納される。各文字は画素のアレイ（ビットマップ）として格納される。ビットマップフォントは比較的大量の格納スペースを必要とし、このタイプのフォントをスケーリングしエフェクトを適用することは比較的困難である。
【０００５】
ＴｒｕｅＴｙｐｅ（商標）などのアウトラインフォントは、グリフの形状または輪郭に関する情報から生成される。輪郭は１セットの線および曲線として規定される。アウトラインフォントはビットマップフォントよりもスケーリングおよび他のエフェクトを容易にし、ビットマップよりも必要とする格納スペースが小さい。しかし多くのモバイルデバイスは代表的にはアウトラインフォントの使用を適切に容易にする格納スペースおよび処理要件を有していない。
【０００６】
ストロークフォントはグリフに代表されるような文字の形状がストロークによって表されるフォントである。ストロークは代表的には線および曲線によって規定される。グリフの所与のセット用のストロークフォントデータに必要な格納スペースは代表的には対応するアウトラインフォントデータに必要なものよりもはるかに小さい。しかしストロークフォントは、アウトラインフォントに比べて質が低下したグリフを生成する。したがってストロークベースのフォントをレンダリングする現存のレンダリングエンジンは比較的限定された質のグリフを生成する。
米国特許第５，９１７，５０１号および第５，９８２，３８７号はアウトラインフォント生成装置および方法を開示している。特にアウトラインフォント手法は（１）基本的ストローク（スケルトン）情報を用いて各文字をストロークに分離すること、（２）ストロークを部分に分割すること、（３）各部分の輪郭を規定し文字を部分の集合体として表現すること、および（４）文字を出力する際に、文字を構成する部分の輪郭をビットマップイメージにし、文字のビットマップイメージを出力することを含む。基本的ストローク情報とは、文字の形態の基本的構造に関する情報であり、文字に肉付けする中線に関する情報ではない。
米国特許第６，２８８，７２５号は、ストローク形状制御情報構造と共に用いられるフォント情報構造を教示している。フォント情報データ構造は、１つの文字スタイルの各フォントの表現を容易にし、各ストロークの情報領域の構造は同一である。
米国特許第５，９２０，３２４号は、文字スケルトン情報１６とエレメントスケルトン情報１８とエレメント輪郭形状情報１７とを含むフォントデータを教示している。文字スケルトン形態情報１６は、対応する文字の各エレメント用の複数のフォント間で共用されるスケルトン形態を表す。エレメントスケルトン情報１８は、フォントコードによって指定されたフォント内で用いられるエレメントのスケルトン形態を表す。エレメント輪郭形状情報１７は、フォントコードによって指定されたフォント内のエレメントの輪郭形状を表す。
【発明の開示】
【課題を解決するための手段】
【０００７】
ソースフォントデータからフォントフォーマットデータを生成する方法は、該ソースフォントデータを分析して複数のグリフ用のグリフデータを獲得する工程と、該グリフデータを分離する工程と、該分離されたグリフデータから中線データを抽出する工程と、該中線データを独特エレメントデータおよび共通エレメントデータとして分類する工程と、該独特エレメントデータおよび該共通エレメントデータを該複数のグリフの各グリフに関連づける工程とを含む。
【０００８】
ソースフォントデータからフォントフォーマットデータを生成するシステムは、グリフ分析ソフトウェアモジュールと、グリフ分離ソフトウェアモジュールと、中線抽出ソフトウェアモジュールと、エレメント分析ソフトウェアモジュールとを含む。グリフ分析ソフトウェアモジュールは、該ソースフォントデータを分析して該ソースフォントデータから複数のグリフ用のグリフデータを獲得するように動作可能である。グリフ分離ソフトウェアモジュールは、各グリフ用の該グリフデータを分離してストロークデータにするように動作可能である。中線抽出ソフトウェアモジュールは、該ストロークデータから中線データを抽出するように動作可能である。エレメント分析ソフトウェアモジュールは、該中線データを独特エレメントデータおよび共通データをして分類し、該独特エレメントデータおよび該共通エレメントデータを該複数のグリフの各グリフに関連づけるように動作可能である。
【発明を実施するための最良の形態】
【０００９】
フォントデータは代表的にはコンピュータデバイスに格納され、テキストをグリフとしてレンダリングするために用いられる。フォントは特定のタイプフェースデザインおよびサイズの文字のセットである。タイプフェースとは１セットの印刷された文字の特定のデザインであり、クーリエ、ヘルベチカまたはタイムズローマンなどである。関連する文字は代表的には、ラテン文字、ギリシャ文字、ひらがな、カタカナまたはハングル文字などのスクリプトを含み、これらのサブセットが特定の言語を書くのに用いられる。
【００１０】
グリフとは、文字を表すために用いられる視覚的エレメントである。グリフは文字画像の実際の形状である。フォントおよびスタイルなどのテキスト提示の局面はグリフに当てはまる。例えば、文字「ｃ」のイタリック体のタイムズのフォントおよび文字「ｃ」のボールドのタイムズのフォントはそれぞれ対応するグリフを有する。
【００１１】
テキストをレンダリングする際に用いられるテキストデータを格納するように動作する代表的なコンピュータデバイスは、パーソナルコンピュータまたはモバイル通信デバイスである。図１は、ディスプレイ１０２上にテキストを表示するように動作する一例としてのモバイルデバイス１００のブロック図である。モバイルデバイス１００はアプリケーションプログラム１０４を含む。アプリケーションプログラム１０４は通常ストレージ１０８に格納されており、テキストがディスプレイ１０２上に表示されることを要求するように動作する。レンダリングエンジン１０６はアプリケーションプログラム１０４からの要求を受け取るように動作し、これに応答して、ストレージ１０８からテキストのフォントデータを取り出し、フォントデータをディスプレイ１０２上に表示されるグリフにレンダリングする。
【００１２】
モバイルデバイス１００は携帯電話、ポケットベル、ＰＤＡ、または他のモバイルコンピュータデバイスによって実現され得る。モバイルデバイス１００が通信回路および機能を有していれば、モバイルデバイス１００は代表的には無線ネットワーク１１０と通信するように動作する。ストレージ１０８は１以上のフォーマットでデータを格納するように動作し、データベース、ファイル、ＲＯＭまたはＲＡＭメモリ、ネットワーク格納スペース、またはさらにはフラッシュメモリモジュールなどのレンダリングエンジン用メモリストレージを含み得る。ディスプレイ１０２はＣＲＴモニタ、ＬＣＤモニタ、または他の同様のディスプレイデバイスであり得る。１つのこのような例示的モバイルデバイス１００は、「親指での使用に最適化されたキーボードを有するハンドヘルド電子デバイス」という名称の米国特許第６，２７８，４４２号に開示されたタイプのものであり得、上記特許の全体をここに参考のため援用する。
【００１３】
テキストのフォントデータは、文字の「スケルトン」によって規定されるストロークフォントとして格納され得る。スケルトンは他のグリフと共通であり得るエレメントと、特定のグリフに特有であり得る独特のエレメントとを含む。レンダリングエンジン１０６は、文字のスケルトンをレンダリングしてディスプレイ１０２上に表示するグリフを生成する。
【００１４】
図２は、一例としてのグリフのスケルトンを格納するように動作する小型フォントフォーマットデータ構造２００のブロック図である。対応する複数のグリフを表現するために複数のデータ構造２００が格納され得る。データ構造２００はモバイルデバイス１００上のストレージ１０８内に格納され得る。
【００１５】
データ構造２００は例として、共通エレメント２０２と独特エレメント２１２とを含む。各共通エレメント２０２は、エレメント識別子２０４、シフトＸ値２０６、シフトＹ値２０８、およびスケーリング値２１０を含む。共通エレメント識別し２０４は２以上のグリフに共通であり得るエレメントに対応する。各独特エレメント２１２は、独特エレメント識別子２１４およびエレメント記述２１６を含む。独特エレメント識別子２１４は特定のグリフに独特のエレメントである。特定のグリフは、共通エレメント２０２、独特エレメント２１２、または共通エレメント２０２と独特エレメント２１２との組み合わせによって表現され得る。
【００１６】
エレメントデータベース２５０は、共通エレメント識別子２０４によって識別された共通エレメント２０２用の記述データ２１８を格納する。記述データ２１８とは、エレメントの線および曲線を規定する、Ｘ−Ｙ座標系内の点のセットである。しかし、他の記述データもまた用いられ得る。
【００１７】
図２の一例のデータ構造２００によって表現される特定のグリフは、共通エレメント識別子００１、０２０および４２０によって識別された共通エレメント２０２を含む。しかしエレメントデータベース内の記述データ２１８は共通エレメントの形状を記述するにすぎないため、共通エレメント２０２は代表的には、このような共通エレメント２０２を有する各特定のグリフによって必要とされるように、Ｘ−Ｙ座標系内でシフトしスケーリングされる。したがってシフトＸ値２０６は、Ｘ−Ｙ座標系のｘ軸に沿った共通エレメント２０２のシフトに関するデータを含み、シフトＹ値２０８は、Ｘ−Ｙ座標系のｙ軸に沿った共通エレメント２０２のシフトに関するデータを含む。スケーリングデータ２１０は、特定のグリフによる共通エレメントのスケーリングに関するデータを含む。エレメントの得スケーリングはエレメント２１２のサイズを増大または縮小し得る。
【００１８】
独特エレメント２１２は特定のグリフに独特のエレメントであり、したがってエレメントデータベース２５０には格納されない。各独特エレメント２１２は独特エレメント識別子２１４および記述データ２１６によって表現される。記述データは、独特エレメントの線および曲線を規定する、Ｘ−Ｙ座標系内の点のセットである。
【００１９】
別の実施形態では、独特エレメント２１２はエレメントデータベース２５０に格納され得、対応する独特エレメント識別子２１４によって識別され得る。したがってデータ構造２００は独特エレメント２１２用の独特エレメント識別子２１４のみを格納する。
【００２０】
レンダリングエンジン１０６は、特定のグリフに対する要求に応えて、ストレージ１０８に格納された対応するデータ構造２００にアクセスし、エレメント２０２および２１２によるスケルトンを構築する。スケルトンはその後レンダリングエンジン１０６によるレンダリングのためにフォントデータとして利用される。レンダリングエンジン１０６はその後レンダリング中に、タイプフェースのスタイル、線の太さ、および他の特徴を適用する。別の実施形態では、エレメント２０２および２１２によるスケルトンは、レンダリングエンジン１０６外部の別のアプリケーションまたはプロセスによって構築され得、その後レンダリングエンジン１０６に提供され得る。
【００２１】
複数のフォントがモバイルデバイス１００内で用いられる場合、ストレージ１０８内に別々のエレメントデータベース２５０が格納され得る。各別々のデータベース２５０は特定のフォントに対応し得る。あるいはすべてのフォントデータが単一のデータベース２５０に格納され得る。
【００２２】
図３は、中国語日本語韓国語（「ＣＪＫ」）イデオグラフ３０４の異なるグリフの共通エレメント３０２、およびヨーロッパグリフ３０８の異なるグリフの共通エレメント３０６の反復使用を示す。共通エレメント３０２はＣＪＫイデオグラフ３０４の異なるグリフで示されており、共通エレメント３０６はヨーロッパグリフ３０８の異なるグリフで示されている。各特定のグリフに応じて、共通グリフ３０２および３０６はシフトされスケーリングされる。
【００２３】
図４は、３つの韓国語グリフ４０４、４０６、４０８に用いられる共通エレメント４０２のシフトおよびスケーリングを示す。第１の韓国語グリフ４０４は共通エレメント４０２を、シフトもスケーリングもされていない静止形態で示す。第２の韓国語グリフ４０６は１方側にシフトされた共通エレメント４０２を示す。第３の韓国語グリフ４０８は大きなサイズにスケーリングされた共通エレメント４０２を示す。
【００２４】
図５Ａは、ソースフォントデータからストロークフォントデータを生成する方法のフローチャートを提供する。一実施形態では、ソースフォントデータはアウトラインフォントデータである。アウトラインフォントデータの一例は、ＴｒｕｅＴｙｐｅ（商標）フォント仕様によるフォントデータであり、ＴｒｕｅＴｙｐｅ（商標）フォントファイル「グリフ」テーブルに格納されている。他のアウトラインフォント情報もまた用いられ得る。
【００２５】
各グリフのために、グリフ分析２０００、グリフ分離３０００、中線抽出４０００、エレメント分析５０００、および変換６０００の工程が行われる。図５Ａのプロセスは代表的にはサーバまたはパーソナルコンピュータなどのコンピュータデバイス上で実行されて、モバイルデバイス１００に格納するデータ構造２００およびエレメントデータベース２５０を準備する。図５Ａのプロセスは例えば、コンピュータデバイスにプロセスを実行させるソフトウェアアプリケーションプログラムまたは命令セットの例示的構造を含み得る。プロセスは単一のコンピュータデバイスに実装されてもよいし、コンピュータネットワーク上で通信するいくつかのコンピュータなどのいくつかのコンピュータデバイスに亘って配布されてもよい。
【００２６】
図５Ｂは、グリフ分析工程２０００のより詳細なフローチャートである。グリフ分析工程２０００において、所与のグリフに関する情報が収集されグリフの形状が単純化される。グリフ分析工程２０００は、グリフ単純化２１００、輪郭分析２２００、内容分析２３００、および輪郭点分析２４００を含む。特に述べない限り、輪郭は到底のグリフの多角形状であり、点は頂点である。グリフは、文字「ｌ」に対する以下のグリフのように単一の輪郭を有していてもよいし、シンボル「Θ」に対する以下のグリフのように複数の輪郭を含んでいてもよい。
【００２７】
グリフ単純化の工程において、所与のグリフのアウトラインが単純化される。輪郭分析工程２２００において、所与のグリフの輪郭が内部輪郭群と外部輪郭分とに分けられる。内容分析工程２３００において、所与のグリフの輪郭が処理されて輪郭の内容が決定される。輪郭点分析工程２４００において、各輪郭点に関連するデータが収集される。このデータはデカルト座標、他の点に対する該点の角度、有効隣接点などを含み得る。
【００２８】
図６は、グリフ単純化工程２０００の後の、単純化されなかった形態６００と単純化された形態のグリフを示す線図である。図示するように、グリフ６００は、直線セグメントとベジエ円弧とを含む輪郭６１２、６１４および６１６を含む。グリフ６００の輪郭６１２、６１４および６１６円で囲んだ部分で単純化されて後の工程の処理を単純化する。処理低減が必要でないか処理低減に特に関心がなければ、グリフ単純化工程２１００は省略され得る。
【００２９】
単純化は所与のグリフの形状の冗長点を除去することによって達成される。図５Ｃは例示的単純化プロセスを示す。単純化プロセスは、クラスタ除去プロセス２１０２、ベジエ円弧度低減プロセス２１０４、および多角形単純化プロセス２１０６を含む。他の単純化プロセスもまた用いられ得る。
【００３０】
クラスタ除去プロセス２１０２において、点が近接していて輪郭において有意なセグメントを規定できないというような点の群（「クラスタ」）が、点またはセグメントを除去することにより単純化されて新しいセグメントになる。代表的には、所与のグリフの形状をほとんど又は全く変形することなくグリフ規定から除去され得る比較的短いセグメントまたは点がある。
【００３１】
セグメント除去のために、冗長セグメントの最大長および／または最大角度が規定される。最大長および／または最大角度の特定値はユーザが規定してもよいし、単純化基準に基づいて自動的に決定されてもよい。代表的には最大長および／または最大角度が大きいほど単純化がより追加されるが、視覚的にも変形が追加される。最大長は代表的には所望の最終ストロークフォントの所望の質によって決定される。
【００３２】
特定値以下の長さおよび／または角度を有する直線セグメントは、グリフのアウトラインから１以上の点を除去することにより単純化または除去される。除去プロセスは、すべての輪郭点に対して、一対のｎｉ−ｎｉ＋１頂点によって規定される各セグメントの長さを決定すること及び長さ条件および／または角度条件を満たすセグメントを除去することを反復することによって実行され得る。除去されたセグメントの数がゼロになるまで各輪郭は反復的に処理される。この相互作用プロセスは、グリフのアウトラインの輪郭の各々に対して反復される。
【００３３】
ベジエ円弧度低減プロセス２１０４において、ベジエ円弧が単純化される。ベジエ円弧は、第２（２次ベジエ）または第３（３次ベジエ）度の多項式によって規定される。２次ベジエ円弧は３つの点のシーケンス、すなわちオン曲線−オフ曲線−オン曲線として規定される。３次ベジエ円弧は４つの点のシーケンス、すなわちオン曲線−オフ曲線−オフ曲線−オン曲線として規定される。「度低減」とは、３次円弧を円錐円弧に低減し、それにより多項式を３から２に低減するプロセスである。度低減により、３次円弧の２つのセグメントの交点が判明する。例えば３次円弧が４つの頂点、ｎｉ、ｎｉ＋１、ｎｉ＋２、ｎｉ＋３によって規定されると、ｎｉ−ｉ＋１セグメントとｎｉ＋２−ｎｉ＋３セグメントとの交点が決定される。その後交点は円弧の新しいオフ曲線点として規定され、円弧はさらに、ｎｉ−新しい輪郭／オフ曲線点−ｎｉ＋３として規定される。頂点ｎｉ＋１およびｎｉ＋２は、単一の新しいオフ曲線点に置換される。こうして円弧の開始点および終了点、ならびに輪郭の有意でない点の数が低減される。もちろん他の円弧単純化ルーチンもまた用いられ得る。
【００３４】
多角形単純化プロセス２１０６において、それぞれの側において直接隣接する２点によって規定される線からある距離にある輪郭点が除去される。例えば、直角と、点と２つの隣接する点とによって規定される角度との差が一定の値または「最大角度」未満であった場合に点が除去される。最大角度はユーザが規定してもよいし、グリフ単純化の所望の量にもとづいて自動的に決定されてもよい。
【００３５】
説明のために、所与の３つの頂点ｎｉ−１、ｎｉ、ｎｉ＋１、角度ｎｉ−１−ｎｉ−ｎｉ＋１を求める。この角度と直角との差が最大角度未満であると、ｎｉ点が破棄される。オフ曲線点およびオン曲線点にはそれぞれ２つの閾値がある。例えば、３つの頂点ｎｉ−１、ｎｉ、ｎｉ＋１のｎｉ点がオン曲線であれば、ある最大角度ｓ１が用いられ得、ｎｉ点がオフィウ曲線であれば、別の最大角度ｓ２が用いられ得る。
【００３６】
単純化後、輪郭分析工程２０００において、所与のグリフの輪郭が内部輪郭群と外部輪郭群とに分けられる。図７は、内部輪郭７０４と外部輪郭７０６とを有するグリフ７０２のアウトライン形状２００を示す。内部輪郭７０４は例として外部輪郭７０６内の閉ざされたスペースを規定する。このような形状は「穴」を有する多角形として記載され得る。外部輪郭７０６が多角形の外部境界であり、内部輪郭７０４が多角形内部の「穴」を規定する。
【００３７】
ＴｒｕｅＴｙｐｅ（商標）によると、内部輪郭および外部輪郭は逆の方向に順序立てられると規定される。例えば、外部輪郭方向は時計回りであり内部輪郭方向は反時計回りであるか、またはその逆である。輪郭の方向を決定するために、各輪郭の点が反復され、輪郭の符号を付けられた領域が多角形の面積の公式によって演算される。
【００３８】
【数１】
0004686186.tif 000002
上記式において、Ｖｉは多角形の頂点であり、ｎは多角形の頂点の総数である。得られたｐｏｌｙ＿ａｒｅａの値は、輪郭が時計回りに順序立てられているか反時計回りに順序立てられているかを示す符号を付けられた値である。正の値は反時計回りの方向に対応し、負の符号は時計回りの方向に対応する。面積がゼロであれば、方向は概して規定されず、したがってデフォルトの時計回りまたは反時計回りの方向として設定され得る。一実施形態では、面積がゼロであれば輪郭は反時計回りの方向であると規定される。
【００３９】
分けられた後、所与のグリフの輪郭が処理されて、内容分析工程２３００でその内容が決定される。各外部輪郭は分析されて、内部輪郭がその中に含まれるか否かが決定される。各輪郭はその後それにしたがって分類される。分類によって、各グリフの独立形状が決定され、その後グリフは独立形状の集合体として規定され得る。独立形状の各々は１以上の輪郭を有し、第１の輪郭が外部輪郭であり他の任意の輪郭が内部輪郭である。
【００４０】
内容物は、すべての内容輪郭を取りその点を反復する単一のブルートフォースアルゴリズムによって決定される。他の内容物アルゴリズムもまた用いられ得る。ブルートフォースアルゴリズムでは、各内部輪郭のすべての点が反復されてチェックされ、すべての外部輪郭に関してそれが外部輪郭内にあるか否かが決定される。内部輪郭のすべての点が外部輪郭のうちの１つの内部にあれば、内部輪郭は外部輪郭に完全に内包される。一実施形態では、外部輪郭が内包する輪郭として規定され、内部輪郭が内包される輪郭として規定される。一旦外部輪郭と内部輪郭とが分類されると、所与のグリフは一連の独立形状データ構造として表現される。各データ構造は所与のグリフおよびグリフの内包する輪郭および内包される輪郭に関する情報に対する参照を含む。
【００４１】
輪郭の点はその後、輪郭点分析工程２４００において処理される。生グリフデータに対応する残りの各点に関する他の情報が分析される。図５Ｄの工程２４０２に示すように、分析から点座標が得られる。例えばＴｒｕｅＴｙｐｅ（商標）では、ＴｒｕｅＴｙｐｅ（商標）ファイルから情報が得られる。この情報は点の座標を含み、フォントユニット、点のタイプ（例えばオン曲線かオフ曲線か）、ＴｒｕｅＴｙｐｅ（商標）ファイルからの生グリフデータの点のアレイ中の点のインデックスが特定される。
【００４２】
独立形状の各々の点が分類されて、各点に関する追加の情報が提供される。各点の内角が決定され、この値に基づいて、工程２４０４に示すように、点が突出したタイプか反り返ったタイプかに割り当てられる。工程２４０６に示すように、各々の点の有効な隣接点が決定される。
【００４３】
各点を突出したタイプか反り返ったタイプかに分類する工程において、頂点ｎｉの２つの角度が決定される。１方の角度が内角と分類され、他方の角度が外角と分類される。内角は点およびそれに直接隣接する２つの点によって規定される点であり、多角形の内部または閉じこめられた領域に属する（多角形の頂点をｎｉとすると、ｎｉ−１、ｎｉ、ｎｉ＋１によって規定される三角形がある）。外角は点およびそれに直接隣接する２つの点によって規定される点であり、多角形の外部または閉じこめられていない領域に属する（再び多角形の頂点をｎｉとすると、ｎｉ−１、ｎｉ、ｎｉ＋１によって規定される三角形がある）。
【００４４】
頂点ｎｉにおける２つの角度の合計は３６０度である。頂点ｎｉ点は点ｎｉ−１、ｎｉ、ｎｉ＋１のセットにおいて共通の点である。角度を規定するためには、頂点ｎｉ＋１がｎｉ−１−ｎｉセグメントによって規定される線の第１の側にあるのか第２の側にあるのかが決定される。三角形の符号の付いた領域を決定する公式が用いられ、三角形は３つの頂点ｎｉ−１、ｎｉ、ｎｉ＋１によって規定される。時計回りに方向付けられた輪郭の場合、三角形の面積の正の値は、ｎｉ＋１に対応する三角形の領域がｎｉ−１−ｎｉ頂点対によって規定される線の第１の側にあることに対応する。したがってｎｉは反り返ったタイプである。逆に負の値またはゼロは、ｎｉ頂点がｎｉ＋１−ｎｉ頂点対によって規定される線の右側にあることに対応する。したがってｎｉは突出したタイプである。反時計回りに方向付けられた輪郭の場合、規定は逆である。
【００４５】
角度の値は余弦法則によって決定され得る。したがって鈍内角を有するいずれの点も反り返った点と分類され、鋭内角を有するいずれの点も突出した点と分類される。本発明の一実施形態によると、内角が直角である場合、点は突出した点と規定され得る。別の実施形態では、内角が直角である場合、点は反り返ったと規定され得る。
【００４６】
工程２４０６に示すように、有効な隣接点（「有効隣接点」）は各点に関しても決定される。以下の条件を満たす場合、所与のグリフの輪郭のいずれかの点が他のいずれかの所与の点の有効隣接点である。（１）両方の点が同一の形状に属する場合、すなわち両方の点が内部輪郭または内包される内部輪郭に属する場合、および（２）２つの点によって規定される線セグメントがその独立形状の輪郭の他のいずれのセグメントにも交差しない、すなわち、２つの点によって規定される線セグメントがその独立形状内に完全に内包されている。いずれかの点が上記２つの条件を満たす場合、その点は問題の点の有効隣接点のリストに加えられる。有効隣接点はその後所与の点からの距離に応じて分けられ、最も近い隣接点が第１とランクづけされる。
【００４７】
独立形状の領域はその外部輪郭と内部輪郭との結合によって決定される。
【００４８】
【数２】
0004686186.tif 000003
上記においてＳは独立形状の面積、Ａａｒｅａは独立形状Ｓの外部輪郭の面積、Ｂｉ．．．ｎは独立形状Ｓの内部輪郭の面積である。
【００４９】
所与の点の有効隣接点は所与の点から「見られた」点と特徴づけられる。直線セグメントが引かれて、ある点を所与の点に連結し、２つの点の間の視覚パスを表現する。直線セグメントが独立形状またはその輪郭の別の線セグメントに妨害されなければ、その点は所与の点の有効隣接点である、すなわち、その点は所与の点から「見られて」いる。
【００５０】
図８は、点間の線でグリフ形状を示す線図であり、点８００の有効隣接点および非有効隣接点を図的に説明する。点８００と他の点８０２、８０４、８０６および８０８との間の線は、他の点８０２、８０４、８０６および８０８が点８００の有効隣接点であることｗ示す。他の点８０２、８０４、８０６および８０８は、グリフ形状のいずれのセグメントにも交差することなく点８００から「見られて」おり、点８００と同一の独立形状に属する。点８００と点８１０および８１２との間の線は、第１の点８１０および８２０が点８００の有効隣接点ではないことを示す。なぜなら、点８００と第１の点８１０および８２０とは同一の独立形状に属していないからである。点８００と点８１４および点８１６との間の線は、第２の点８１４および８１６が点８００の有効隣接点ではないことを示す。なぜならこれらの線はグリフ形状のセグメントに交差しているからである。
【００５１】
グリフ分離工程３０００において、グリフは一連の「ストローク」に分離／分解される。ストロークは必ずしも所与のグリフの独立形状の各々に対応しているわけではない。１つの独立形状は複数のストロークに分離／分解される。他に特定しない限り、用語「分離」および「分解」は交換可能に用いられる。
【００５２】
図９は、参照符号９０２、９０４、９０６、９０８、９１０および９１２によって示されるストロークに分離されたサンプルグリフ９００の一例を示す線図である。さらに図示するように、独立形状９１４は参照符号９０６、９０８、９１０によって示される３つのストロークを有する。
【００５３】
ストロークは、文字がペンで引かれるか筆でペイントされる方法に対応する。例えば、いつくかの文字は僅か１つのストロークで引かれ得、他のストロークはいくつかのストロークを必要とする。したがってペンの自然な動きという概念から「動きベクトル」が導かれる。動きベクトルは、ペンの自然な動きに似た同一のパスに沿ったストロークの点に対応する。アウトラインのすべての点が同一のパスに沿っているわけではないため、動きベクトルは、ストロークの動きを規定するためにある点のセットのみに適用される。
【００５４】
図５Ｅは例示的グリフ分離プロセスのフローチャートである。抽出された各ストロークは幾何学的に閉多角形または輪郭と規定される。各ストロークは２つの側、ストロークのすなわち第１の側およびストロークの第２の側を有する。各側は一対の開始および終了点を有し、その側が開始および終了する点を示す。両方の側のすべての点が順に格納されて、第１の側の第１の点から第２の側の最後の点までの順のインクリメントを容易にする。
【００５５】
一実施形態において、各輪郭はアレイデータ構造の点によって表現され得、各点はアレイのエントリーインデックスによって参照され得る。開始点が一対の点を選択することにより決定されて、工程３００２に示すように第１および第２の側を規定し、工程３００４に示すように第１および第２の側の点をインクリメントする。ストロークの第１の側はアレイ内の次のエントリーに移動し、反対の側はアレイ内の前のエントリーに移動する。例えば、第１の側の現在の点が点３であれば、インクリメント先の次の点は点４である。同様に、第２の側の現在の点が点１１であれば、インクリメント先の次の点は点１０である。
【００５６】
点を横断する際に、輪郭の第１および第２の側を規定するパスが点から点に移動する。横断されたパスは点インクリメントセットとして格納され、各点がインクリメントした後、工程３００６に示すように、システムはストロークが閉じているか否かを決定する。第１および第２の側が同一の点で会うと、ストロークプロセスは完了する。他の条件を満たした際にストロークが完了してもよい。
【００５７】
ストロークが閉じていない場合、工程３００８に示すように、各インクリメント点が候補点であるか否かが決定される。候補点は、２つ以上のストロークが互いに交差する可能性のある、アウトライン中のターンまたは角度に対応する。したがってインクリメントする先の次の点は、パスに沿った次の点でないかもしれない。むしろインクリメント先の次の点は、動きベクトルに対応する点であり得る。一実施形態では、候補点は鈍内角を有する反り返った点である。
【００５８】
インクリメント先の次の有効点は「移動先」点である。移動先点は必ずしも候補点の直接の隣接点であるとは限らない。むしろ移動先点は動きベクトルに対応し、現在のストロークが、ストロークを引くために用いられるペンの自然な動きという概念に対応する自然な連続性を受け取る。したがって候補点からパスに沿った移動先点ではない次の点への移動は、ストロークの自然な連続性という概念に違反する。そのため、工程３０１０に示すように、候補点にとっての有効な移動先点は、動きベクトルに基づいて選択され、有効な移動先点は「オカーレンス」または「イベント」として格納される。
【００５９】
逆に、側の現在の点が候補点でない場合、動きベクトルの決定は適用される必要がない。この場合、工程３０１２に示すように、有効な移動先点は動きベクトルとは無関係に選択され得る。
【００６０】
ある側の「移動先」点は、その側の前の点とその側の現在の点とによって形成される線に近接する。点が近接しているか否かは、水平角と、前の点を含む３つの頂点（ｓｉｄｅ＿ｐｒｅｖｉｏｕｓ＿ｐｏｉｎｔ）、現在の点（ｓｉｄｅ＿ｃｕｒｒｅｎｔ＿ｐｏｉｎｔ）、おおび提案された「移動先」点とによって規定される角度との差に基づいて決定される。その差は好ましくは特定された平坦度閾値未満である。各特定のフォントについて、平坦度閾値は異なり得、代表的には１０度から２５度の範囲である。
【００６１】
評価すべきいくつかの提案された移動先点がある一実施形態では、有効な移動先点として選択された点は、その側の現在の点に最も近い点である。評価すべきいくつかの提案された移動先点がある別の実施形態では、有効な移動先点として選択された点は、現在の点との差が平坦度閾値に対して最も低い点である。他の評価基準もまた用いられ得る。
【００６２】
有効な移動先点が見つかれば、有効な移動先点まで移動が続く。工程３０１２に示すように、候補点から有効な移動先点までの移動は「オカーレンス」または「イベント」として格納される。イベントはさらに各側について相互イベントとして分類される。イベントが両方の側で同時に起こったときに相互イベントが記録される。相互イベントは、両方の側の候補点とそれに対応する移動先点の対として格納される。イベントは２つのストロークを連結し、他のストロークの潜在的開始点として作用し得る。
【００６３】
工程３０１４では、所与のストロークのすべての点が処理されたか否か、またはストロークが閉じているか否かが決定される。まだ処理される点が残っているか、ストロークが閉じていない場合、工程３００４〜３０１２が繰り返される。それ以外の場合、工程３０１６において、処理すべきイベントまたはグリフの点が残っているか否かが決定される。残っている場合、工程３０１８に示すように、点の新しいセットが選択され、工程３００４〜３０１６が繰り返される。それ以外の場合、プロセスは完了する。
【００６４】
図１０は、グリフ分離プロセス３０００によって分離された例示的グリフ１０００の線図である。例示的グリフ１０００は点１〜３７によって規定されたアウトライン形状を有する。矩形１００２、１００４、１００６および１００８内に閉じこめられた開始点対は、ストローク１０１０、１０１２、１０１４および１０１６の開始点である。矩形１００６、１００８によって示された点９、３０および３２、３５は、ストローク１０１４および１０１６の開始点であるイベントでもある。円で囲まれた点９、３３、１８、３２および３６は候補点であり、これらの移動先点は、中央の矢印１０１０，１０１２、１０１４および１０１６によって示された各ストロークの方向によると、それぞれ３０、１０、３７、３５および１である。候補点３３はストローク１０１４と１０１６とに共通であり、したがってストローク１０１４の移動先点１０およびストローク１０１６の移動先点３４に関連する。ストローク１０１０、１０１２、１０１４および１０１６の各々は、動きベクトルを示す矢印によって示される。
【００６５】
図５Ｆは、グリフ分離プロセス３０００のより詳細なフローチャートである。工程３０２０において、様々な処理値が設定される。一実施形態では、様々な処理値は、平坦度閾値、開始閾値、開始スパン深さ値、マークされていない点の許容値、およびマークされていないセグメントの許容値を含む。
【００６６】
平坦度閾値は潜在的移動先点を評価するために用いられる。開始閾値値開始スパン深さ値は開始点を決定するために用いられる。マークされていない点の許容値は、所与の形状に関していくつの未処理点が許容されるかを特定するために用いられる。マークされていないセグメントの許容値は、所与の形状に関していくつの未処理セグメントが許容されるかを特定するために用いられる。
【００６７】
その後工程３０２２に示すように、一対の開始点が選択される。一実施形態では、開始点は、ｘ−ｙ軸上の位置に応じて選択される。例えば図１０の点５、６、２１および２２のような最も左の対が開始点として選択される。開始点を選択する他の方法もまた用いられ得る。
【００６８】
開始閾値は点を候補として規定するために用いられる。問題の頂点の角度が開始閾値未満であれば、点は有効な開始点対であり、クリーンな開始点として規定される。両方の角度が開始閾値よりも大きければ、その対は破棄され別の対が取り上げられる。一方の角度が開始閾値よりも大きければ、その角度と３６０度と差である角度が開始閾値と比較される。比較された角度が開始閾値未満であれば、その点の対は有効な開始点対でありダーティな開始点として規定される。
【００６９】
対は直接隣接した点ではない。代表的にはこれらの間に少なくとも１つの点がある。点の数による距離の深さは開始スパン深さ値によって規定される。
【００７０】
開始点を選択するプロセスは、フォントパターンを利用することによって単純化され得る。一実施形態では、フォントパターンが用いられると、フォントパターンによって選択された開始点対が他の対よりも優先される。同様に、クリーン対がダーティ対よりも優先される。すべての可能性のある対を決定した後、工程３０２４で対の優先順位が決められ、工程３０２６において優先順位に応じて選択される。各優先群内では、点間の距離が最も短い対が選択される。
【００７１】
一対の開始点を取り上げた後、工程３０２８に示すように、ストロークの２つの側が規定される。各側は開始点を有し、工程３０３０に示すように、この開始点からのパスに沿ってインクリメントされる。一実施形態では、各形状の点はアレイデータ構造に格納され、パスに沿ってインクリメントされた結果、開始点を格納するアレイセルからアレイ内を反復する。
【００７２】
その後工程３０３２に示すように、点が評価されて候補点か否かが決定される。候補点であった場合、工程３０１０および３０１２に関して上記したように有効な移動先点が決定される。点が候補点でない場合、工程３０３４に示すように、システムはパスに沿って次ぎの点までインクリメントする。非候補点については、両方の側の現在の点が有効な隣接点であれば現在の点がインクリメントされて待ち角度評価を満足し、次の点は別の既に生成されているストロークによっては所有されない。これらの条件は代表的には、候補点でない点にのみ有効である。なぜなら候補点はストロークの交差により、いくつかのストロークによって所有され得るからである。
【００７３】
両方の側の現在の点が有効な隣接点であるか否かを決定するために「見ることができる」ルールが用いられる。見ることができるルールは、各インクリメントにおいて、両方の側の現在の点が互いに「見」れば、すなわち、第１の側の現在の点がその有効隣接点中に第２の側の現在の点を有していれば、満たされる。見ることができるルールの違反は、オカーレンス中に間違った移動先点を選択したこと、またはグリフの形状のレイアウトによって起こり得る。
【００７４】
所与の候補点についての有効移動先点の決定において、見ることができるルールに違反すると、提案された移動先点が破棄される。違反がグリフの形状のレイアウトによって起こった場合、現在の点は破棄されて現在の点に最も近い点が一方の側の有効隣接点リストから選択される。例えば、見ることができるルールに対する違反がストロークの一方の側に沿って移動している間に起こった場合、その側の現在の点が破棄されて他方の側の現在の点の連接点のリストから最初に入手可能な点に置換される。
【００７５】
待ち角度値は、ストロークの両方の側に沿った移動のインクリメントレートを正規化することによって、可能性のある「見ることができる」ルール違反を素子するために用いられる。例えば、第１の側に沿った点が少なければ第１の側は迅速にインクリメントし、点間の距離は第２の側の点に比べて大きい。したがって第２の側はより多くの点を含み、同一のインクリメント数だけ第１の側より遅れている。両方の側の現在の点が近接することを容易にするために、現在の点によって規定された２つの側に対する角度が、待ち角度の各側に関して比較される。一方の側の角度が待ち角度未満であれば、その側の現在の点はインクリメントされず、他方の側の現在の点がインクリメントされる。
【００７６】
図１１は、いくつかの点の待ち角度を示す。矩形は点１〜９によって規定され開始点１〜９を有する。パスは開始点１および９から点２および８までそれぞれインクリメントする。待ち角度α１およびα２は閾値待ち角度（例えば６６度）と比較される。両方の待ち角度α１およびα２とも６６度より大きいため、両方のパスがインクリメントされる。待ち角度α３およびα４が閾値待ち角度と比較される。待ち角度α４は４５度であり待ち角度６６度未満であるため、点７からのパスは点６にインクリメントされないが点３からのパスは点４にインクリメントされる。
【００７７】
両方の側が対応する次の点に移動する毎に、またはオカーレンスまたはイベントが起こった後、システムは、図５Ｆの工程３０３６に示すように、現在処理されているストロークが閉じ得るか否かを決定する。ストロークが閉じることは、２つの側を規定するすべての点、各側の開始点および終了点対、およびイベントを格納するデータ構造を規定する。すべての処理された点は候補点を除いて所有されていると分類される。なぜなら候補点はいつくかのストロークに共通であり得るからである。候補点が共通であるストロークの数はデータ構造に格納され得る。
【００７８】
ストロークを閉じると、工程３０３８に示すように、システムはグリフの形状のいずれかの点が未処理のまま残っているか否かお決定する。例えば、いずれかの点が所有されてもいず候補点でもない場合、その点は処理されていない。イベントが評価されて、処理すべきイベントが残っているか否かが決定される。イベントは列に格納され得、列内の第１のイベントは次のストロークの開始点対として処理される。イベントの列が空であれば、工程３０４０に示すように、新しい開始点が取り上げられて一対の開始点が選択される。処理すべき点がなくなったとき、または未処理の点の数がユーザ規定された値以内となったとき、点処理は完了する。
【００７９】
図１２は図１０のグリフの処理からの例示的ログを示す。ログは分離の処理工程および各ストロークが含む情報を列挙している。例示的グリフの独立形状のすべては反復されて、各形状がストロークに分離される。
【００８０】
グリフ分離３０００の最後の工程は、工程３０４２に示すように、ストロークのマージである。冗長を低減するために、あるストロークは１つに統合され得、小型フォントフォーマット下でのグリフ内の線の数が減少される。マージプロセスは完全に内包されたストローク、明示的に連結されたストロークおよび暗示的に連結されたストロークをサーチする。
【００８１】
完全に内包されたストロークとは、別のストローク内に完全に含まれたストロークである。一実施形態では、ストロークが完全に含まれているか否かの決定は、第１のストロークの全ての点が第２のストロークの点によって規定された領域内に含まれているか否かを決定する工程を含む。ストロークが完全に含まれていれば、破棄される。
【００８２】
明示的に連結されたストロークとは、部分的に相互イベントによって規定されたストロークである。形状の両方の側でイベントが起こると、イベントは相互イベントを規定する。相互イベントは、形状の各側で１対、すなわち２対の点を規定する。各対はその後イベントがイベント列から処理されると、別のストロークの開始点対を規定する。したがって１つの相互イベントは２つのストロークのソースであり得る。これらのストロークは１つにマージして単一のストロークを形成し得る。
【００８３】
図１３は、明示的に連結されたストロークを示す。点１〜２０によって規定されたグリフはストローク１０２０および１０２２を含む。相互イベント１０２４および１０２６はそれぞれ、点１３〜１８および３〜８によって規定されたストロークの開始点である。したがってこれらのストロークは組み合わされて、点３〜８および１３〜１８によって規定された、明示的に連結されたストローク１０２２を形成する。
【００８４】
暗示的に連結されたストロークは、１つのストロークの終了点対が別のストロークの開始点対でもあるときに起こる。ストロークの点は反復されて、ストロークが合致する終了点または開始点を有するか否かが決定される。有していればストロークは単一のストロークにマージされる。
【００８５】
マージ工程の後、分離工程３０００は完了し、中線抽出４０００のプロセスが行われる。中線は、所与の幾何学形状の多角形スケルトンに対応する。例えば矩形の中線は、矩形の長手方向軸に対応する直線であり得る。したがってスケルトンは、形状の概略図を提供するセグメントを含む１以上の線である。所与のグリフをストロークに分解することにより、グリフスケルトンの導出が容易になる。この場合、各ストロークはグリフの最終のストロークベース形状の中線のベースを提供する。中線抽出プロセス４０００において、すべてのストロークの対応する中線が抽出される。抽出された中線９１６は例えば図９に示すように示される。
【００８６】
各ストロークは２つの側と一対の開始点および終了点によって規定される。中線はストロークのすべての点を反復することによって決定される。第１の側の各点について、第２の側からの対応する最も近い点が見つけられる。これらの２つの点によって規定されるセグメントについて、中線が見つけられ中線に追加される。プロセスは第２の側の各点について繰り返される。両方の側が処理された後、両方の中線の長さが計算される。長い方の中線がストロークの中線であると規定される。
【００８７】
最後の中線は、上記したグリフ単純化プロセス２１００に類似の単純化プロセスによって単純化され得る。これは、上記した分離プロセス３０００のマージプロセスに関して上記したものと同様の様式で中線をマージすることにより行われる。
【００８８】
エレメント分析工程５０００において、反復的パターンを有するエレメントを求めてグリフがサーチされる。本発明の一実施形態によると、パターンマッチングによってパターンが反復的であるか否かが決定される。パターンマッチングはパターンのデータベースを用いることによって行われ得る。フォント内で頻繁に起こるパターンがフォントから抽出される。グリフはデータベース内で規定され、合致するパターンを有するグリフの特定のセクションが格納される。パターンマッチングプロセスに先だってデータベースから情報が読み出される。
【００８９】
パターンマッチングプロセスにおいて、所与のグリフの輪郭がデータベースからのパターンと比較される。比較は、形状のあるパラメータを測定する不変機能から得た類似性測定に基づいて行われる。これらのパラメータは代表的には、形状が異なる幾何学的変形を経ても不変のままであり、したがって変形に対して「不変」である。
【００９０】
不変は、同等性、類似性、およびアフィンの変形によって決定され得る。同等性変形は距離を保存する平面の変形である。類似性は形状を保存する平面の変形であり、比例的にスケーリングする変形（ホモセティとしても知られる）を同等性で構成することにより得られる平面の変形である。アフィン変形は、線および平行性を保存する変形である。パターンマッチングに用いられる代表的な変形は、平行移動、比例的スケーリング、および非比例的スケーリングを含み得る。他の変形もまた用いられ得る。
【００９１】
例示的パターンマッチングプロセスは、２次元平面内の平行移動中に２つの形状の類似性を比較する。上記平行移動において、元の形状の全ての点がＸまたはＹ軸に沿って以下の式を満たすようなシフト値だけシフトする。
【００９２】
【数３】
0004686186.tif 000004
上記においてＸｉおよびＹｉは、形状およびパターンのｉ番目の点のＸおよびＹ座標である。オフセットが知られていれば、１つの比較だけが必要であり得る。例えば、Ｘｉ（ｏｒｇ）がＸｉ（ｎｅｗ）から値を差し引くことによって得られ得る。
【００９３】
オフセットが知られていなければ、形状とパターンとの間で追加の比較が必要となり得る。例えば、形状およびパターンの最も右の点が、オフセット値を得るために差し引かれるＸおよびＹ座標と決定される。形状の残りの点が選択され、点のＸおよびＹ座標がオフセット値から差し引かれる。減算の結果パターンの対応する点のＸおよびＹ座標が受け取られると、形状はパターンに類似である。形状のすべての点に関して減算の結果上記の結果が得られると、形状はパターンに類似である。逆に減算の結果ＸおよびＹ座標がパターンの点のＸおよびＹ座標と異なれば、形状はパターンに類似ではない。したがって平行移動変形において、類似形状およびパターンの距離は不変のままである。
【００９４】
各グリフに関して、識別されたパターンは図２に関して上記したように共通エレメント２０２または独特エレメント２１２として識別される。合致パターンが見つからなければ、特定のストロークを記述するために独特エレメントが用いられる。
【００９５】
フォントエレメントを規定するために、ユニコードコンソーシアムによって提供されたフォントデータなどのデータが用いられ得る。例えばイデオグラフを規定するＣＪＫグリフの場合、ラジカルベースのエレメント抽出が用いられ得る。ラジカルとは、ＣＪＫ辞書でのサーチプロセスを単純化するために用いられるストロークまたはイベント完全なイデオグラフである。同様に、ユニコード仕様においても、すべてのイデオグラフはラジカルによってグループ化されている（例えばユニコード仕様の康県ラジカルまたはＣＪＫラジカル補足を参照のこと）。これらのラジカルは抽出される主なエレメントである。パターンマッチングプロセスにおいて用いられるパターンデータは、グリフ、またはラジカルであるグリフの部分を含む。多くのグリフにおいて特定のグリフまたはグリフの一部が繰り返される場合、ＣＪＫのラジカルに加えて、追加のパターンが視覚推測に基づいて規定される。
【００９６】
別の例として韓国語ハングルシラブルの場合、各ハングルシラブルを分解してＪａｍｏ文字にすることを許可する分解ルールが規定されており、これはユニコード仕様にもカバーされている。韓国語において、すべてのハングルシラブルはＪａｍｏ文字からなり、したがってＪａｍｏ文字は韓国語のハングルグリフをこうせいする基本的エレメントと考えられ得る。
【００９７】
他の言語の場合、例えばユニコード正規化チャートが用いられ得る。各構成グリフについて、これらのチャートは、複合グリフが含む単一グリフを規定する。ハングル、日本語、いくつかのＣＪＫイデオグラフ、複合ラテングリフ、および複合アラビアグリフに対する正規化チャートがある。この情報はエレメント分析５０００において小型フォントフォーマットのエレメントを規定するために用いられる。
【００９８】
別の実施形態では、特定のグリフデータなしでパターンマッチングが達成される。各形状が反復されて評価データベースに格納される。システムは、共通データベースに格納されたデータに基づいて共通のエレメントがあるか否かを繰り返し決定する。
【００９９】
変換工程６０００において、アウトラインフォントの幾何学的データが小型フォントフォーマットの仕様に調整される。例えばＴｒｕｅＴｙｐｅ（商標）タイプフェースデザインユニットで特定された元のフォントが小型フォントフォーマットデザインユニットに変換される。この変換は、フォントベースライン、フォントアセントおよびフォントディセントなどの様々なフォントメトリクスに曝され得る。他のメトリクスもまた用いられ得る。
【０１００】
変換工程６０００では、図２を参照して上記したように、データ構造２００のセットおよびデータベース２５０としてフォントデータが格納される。他のエレメントとパターンマッチングされたエレメントはエレメントデータベース２５０内に共通エレメント２０４として格納され、対応するグリフデータ構造２００内で参照される。グリフデータ構造２００は対応するシフトＸ値２０６、シフトＹ値２０８、およびスケーリング値２１０をも格納している。独特エレメント２１２は図２を参照して上記したように、記述データと共に格納されている。別の例示的データ構造は、上記で参照した仮出願第６０／３９３，７９５号に記載されているようにスラングソフトフォントフォーマットである。他のデータ構造および格納アーキテクチャもまた用いられ得る。
【０１０１】
変換工程６０００が完了すると、フォントデータがモバイルデバイス１００に格納されて、図１を参照して上記したようにアプリケーションプログラムまたはレンダリングエンジンと共に用いられ得る。変換工程６０００はエレメント分析工程５０００に組み込まれてもよい。
【０１０２】
本出願のシステムおよび方法をフォントデータを例に述べてきたが、本出願のシステムおよび方法は、グラフィカルデータエンティティ、地図エンティティまたは他の視覚表示エンティティなどの他のデータタイプにも適用され得る。別の実施形態では、本発明のシステムおよび方法の例示的データ構造が小型フォーマットでマップデータを格納するために用いられ得る。例えば、市などの地理的領域が例示的データ構造の小型フォーマットで格納され得、市の地図を再構築するためにレンダリングエンジンによってアクセスされ得る。さらに、モバイルデバイスが位置を変更すると、モバイルデバイスが位置する新しい地理的領域に対する追加のマッピングデータがダウンロードされ得る。
【０１０３】
この書面による記載は本発明を開示するため、および当業者が本発明を実施および使用することを可能にするために、最良の形態を含む説明的実施形態を用いている。他の形態およびデバイスも、それらが請求の範囲の文言または請求の範囲に規定されたものの均等物と変わらないエレメントを有している限り、請求の範囲に含まれる。
【図面の簡単な説明】
【０１０４】
【図１】図１は、例示的モバイルデバイスのブロック図である。
【図２】図２は、小型フォントフォーマットデータ構造のブロック図である。
【図３】図３は、異なるグリフの共通エレメントの反復的使用を示す。
【図４】図４は、共通エレメントのシフトおよびスケーリングを示す。
【図５Ａ】図５Ａは、アウトラインフォントからストロークフォントを生成する方法のフローチャートである。
【図５Ｂ】図５Ｂは、グリフ分析プロセスのより詳細なフローチャートである。
【図５Ｃ】図５Ｃは、例示的単純化プロセスのフローチャートである。
【図５Ｄ】図５Ｄは、内容分析プロセスのより詳細なフローチャートである。
【図５Ｅ】図５Ｅは、例示的グリフ分離プロセスのフローチャートである。
【図５Ｆ】図５Ｆは、グリフ分離プロセスのより詳細なフローチャートである。
【図６】図６は、非単純化形態および単純化形態のグリフを示す。
【図７】図７は、内部輪郭および外部輪郭を有するグリフを示す。
【図８】図８は、点の有効および非有効隣接点を有するグリフを示す。
【図９】図９は、ストロークに分離されたグリフを示す。
【図１０】図１０は、分離されたグリフを示す。
【図１１】図１１は、いくつかの点の待ち角度を示す。
【図１２−１】図１２は、図１０の例示的グリフの処理からの例示的ログを示す。
【図１２−２】図１２は、図１０の例示的グリフの処理からの例示的ログを示す。
【図１２−３】図１２は、図１０の例示的グリフの処理からの例示的ログを示す。
【図１３】図１３は、明示的に連結されたストロークを示す。
【図１】
0004686186.tif 000005
【図２】
0004686186.tif 000006
【図３】
0004686186.tif 000007
【図４】
0004686186.tif 000008
【図５Ａ】
0004686186.tif 000009
【図５Ｂ】
0004686186.tif 000010
【図５Ｃ】
0004686186.tif 000011
【図５Ｄ】
0004686186.tif 000012
【図５Ｅ】
0004686186.tif 000013
【図５Ｆ】
0004686186.tif 000014
【図６】
0004686186.tif 000015
【図７】
0004686186.tif 000016
【図８】
0004686186.tif 000017
【図９】
0004686186.tif 000018
【図１０】
0004686186.tif 000019
【図１１】
0004686186.tif 000020
【図１２−１】
0004686186.tif 000021
【図１２−２】
0004686186.tif 000022
【図１２−３】
0004686186.tif 000023
【図１３】
0004686186.tif 000024