(57)【要約】      （修正有）【課題】文書に応じ最適フォントのマッピングの実現。【解決手段】課題文書の１つまたは複数の文書フォントに自動フォントマッピングを実行し、上記１つまたは複数の文書フォントを少なくとも１つの置換フォントにマッピングする。フォントマッピングは、少なくとも１つの文書固有フォントマッピング制限によって制限され、文書は、少なくとも１つの置換フォントを用いてレンダリングされる。自動フォントマッピングは、１つまたは複数の文書フォントと、対応するマッピングされた少なくとも１つの置換フォントとの類似性を測定する目的関数の制約付き最適化を実行し、制約付き最適化は、少なくとも１つの文書固有フォントマッピング制限により制約される。該制約を基礎として、自動フォントマッピングは、レンダリングに利用可能なフォント集合の部分集合を選択することと、レンダリングに利用可能なフォント集合の選択された部分集合毎に最適化を実行する。【選択図】図１
2011238224.tif 000002
【特許請求の範囲】
【請求項１】
文書の１つまたは複数の文書フォントに自動フォントマッピングを実行し、前記１つまたは複数の文書フォントを少なくとも１つの置換フォントにマッピングすることと、
前記文書を、前記少なくとも１つの置換フォントを用いてレンダリングすることを含み、
前記フォントマッピングは少なくとも１つの文書固有フォントマッピング制限によって制限される方法。
【請求項２】
前記自動フォントマッピングを実行することは、
前記文書のＭ個の異なる文書フォントについて、前記Ｍ個の異なる文書フォントをＭ個の異なる置換フォントにマッピングするために自動フォントマッピングを実行することを含み、Ｍは２以上であり、
前記少なくとも１つの文書固有フォントマッピング制限は、Ｍ個の異なる置換フォントを要求する、請求項１に記載の方法。
【請求項３】
前記自動フォントマッピングを実行することは、
前記１つまたは複数の文書フォントと、対応するマッピングされた少なくとも１つの置換フォントとの類似性を測定する目的関数の制約付き最適化を実行することを含み、前記制約付き最適化は、少なくとも１つの文書固有フォントマッピング制限を具現する少なくとも１つの制約によって制約される、請求項１及び請求項２のいずれか１項に記載の方法。
【請求項４】
システムであって、
文書のＭ個の異なるフォントを少なくともＭ個の置換フォントに、少なくとも１つの文書固有フォントマッピング制限によって制限されるマッピングでマッピングするように構成されるデジタル処理デバイスを備える自動フォントマッピングサブシステムであって、前記デジタル処理デバイスは、前記１つまたは複数の文書フォントと、対応するマッピングされた少なくともＭ個の置換フォントとの類似性を測定する目的関数の制約付き最適化を実行するように構成され、前記制約付き最適化は、少なくとも１つの文書固有フォントマッピング制限を具現する少なくとも１つの上限または下限によって制約され、前記少なくとも１つの上限または下限は置換フォントの数について下限Ｍを含む自動フォントマッピングサブシステムと、
前記文書を、前記少なくとも１つの置換フォントを用いてレンダリングするように構成されるレンダリングサブシステムとを備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
下記は、文書印刷の技術、文書表示の技術、文書レンダリングの技術及び関連技術に関する。
【背景技術】
【０００２】
文字、数字、アジアの文字、等々のようなキャラクタを備えるテキストを含む文書は、典型的には、数字コードまたは他の抽象的表現によって表されるキャラクタで記憶される。文書が表示または印刷のためにレンダリングされる際には、テキストは、画面への表示、物理ページへのプリントまたは他の人間が感知できるレンダリング用に適切なフォントに変換される。文書は、フォントタイプ、フォントサイズ、フォント特性（例えば、下線引き、斜体、太字、上付きまたは下付き、等々）等のフォント情報、並びにレンダリングされたテキストを画面、印刷ページまたは他のレンダリング空間へ配置することを決定するに足る情報を含む。
【０００３】
文書作成システムとして人気のあるタイプは、「見たものが、手に入るもの」と口語的に、またはＷＹＳＩＷＹＧと称される。ＷＹＳＩＷＹＧシステムでは、文書は、文書作成中に、予期されるその最終的な表示または印刷と同じ方法で表示される。テキストに対しては、これは、テキストが、人間である文書作成者によって選択されるフォントのタイプ、サイズ及び特性を用いて示されることを意味する。このような目的で、ワードプロセシングアプリケーション、ドキュメントパブリッシングソフトウェア、ウェブページ開発ソフトウェア、等々のようなＷＹＳＩＷＹＧ文書生成アプリケーションまたはソフトウェアは、文書生成プロセスの間に選択用及びＷＹＳＩＷＹＧ表示用に利用可能なフォント集合を含む。或いは、文書生成アプリケーションまたはソフトウェアはより低いレベルで動作する場合もあるが、この場合、人間であるユーザはフォントのタイプ、サイズ及び特性を指定するものの、文書作成プロセスの間に文書をＷＹＳＩＷＹＧフォーマットでは見ない。このようなシステムの一例が、ＬａＴｅＸエディタである。このようなアプリケーションにはＷＹＳＩＷＹＧインタフェースは含まれていないが、文書生成アプリケーションまたはソフトウェアはやはり選択可能なフォント集合を提供し、よって、フォントタイプを含む最終的なレンダリングは、文書生成アプリケーションまたはソフトウェアを介して人間であるユーザにより規定される。
【０００４】
ウェブブラウザ、印刷エンジンまたは関連のソフトウェアまたはファームウェア、ポータブルドキュメントフォーマット（ＰＤＦ）ファイル生成器、等々のような文書レンダリングシステムは、生成文書を最終的な表示または印刷用にレンダリングする。この文書レンダリングシステムも、典型的には、レンダリングシステムがレンダリングすることのできるフォント集合を含む。
【０００５】
最新の文書生成及びレンダリングシステムは、典型的には、利用可能な何百、何千、何万、またはそれ以上のフォントを含む。しかしながら、時には、生成文書に使用されているフォントがレンダリングシステムでは利用できないことが発生する。このような場合には、利用できないフォントを最終的な文書レンダリング用の利用可能な類似フォントで置換するフォント置換（フォントマッピングとも呼ばれる）を実行することが知られている。このような目的で、例えば、Ｍａｒｔｉｎ  Ｓｏｌｌｉ著「コンテンツベースの画像検索に関するトピック−フォントと色彩感情」Ｌｉｎｋoｐｉｎｇ大学、論文番号１３９７（２００９年２月、文書ＬＩＵ−ＴＥＫ−ＬＩＣ−２００９：５、ｈｔｔｐ：／／ｌｉｕ．ｄｉｖａ−ｐｏｒｔａｌ．ｏｒｇ／ｓｍａｓｈ／ｇｅｔ／ｄｉｖａ２：１７４８８５／ＦＵＬＬＴＥＸＴ０１にて閲覧可能、最終アクセスは２０１０年３月４日）において開示されているような様々な自動フォント類似性メトリックが存在し、これは、このメトリックにより測定されるものと同様のフォントを自動的に選択するために使用可能である。上記文献は、本参照によりその全体が開示に含まれる。マッピングは要求に応じて生成されてもよく、例えば、レンダリングアプリケーションが文書内で利用できないフォントに遭遇すると、レンダリングエンジンに利用可能な類似の置換フォントを位置決めするために類似度が適用される場合がある。或いは、マッピングは、フォントの類似度を基礎として先験的に生成されかつルックアップテーブルとして格納される場合もあり、よって、利用できないフォントに遭遇すると、ルックアップテーブルの参照によって置換フォントが即座に同定（即ち、マッピング）される。
【発明の概要】
【課題を解決するための手段】
【０００６】
以下、フォントの改良されたマッピング方法及び装置を開示する。
【０００７】
本明細書において例示的な例として開示されている幾つかの例示的実施形態において、ある方法は、文書の１つまたは複数の文書フォントに自動フォントマッピングを実行し、この１つまたは複数の文書フォントを少なくとも１つの置換フォントにマッピングすることと、この少なくとも１つの置換フォントを用いて文書をレンダリングすることを含み、上記フォントマッピングは、少なくとも１つの文書固有フォントマッピング制限によって制限される。
【０００８】
本明細書において例示的な例として開示されている幾つかの例示的実施形態において、直前の段落における方法では、自動フォントマッピングは、上記１つまたは複数の文書フォントと、対応する少なくとも１つのマッピングされた置換フォントとの類似性を測定する目的関数の制約付き最適化を実行することを含み、上記制約付き最適化は、少なくとも１つの文書固有フォントマッピング制限を具現する少なくとも１つの制約によって制約される。本明細書において例示的な例として開示されている幾つかの例示的実施形態において、直前の段落における方法では、自動フォントマッピングは、レンダリングに利用可能なフォント集合の部分集合を少なくとも１つの文書固有フォントマッピング制限を基礎として選択することと、上記１つまたは複数の文書フォントと、対応する少なくとも１つのマッピングされた置換フォントとの類似性を測定する目的関数の最適化を実行することを含み、上記最適化は、レンダリングに利用可能なフォント集合の選択された部分集合毎に行われる。
【０００９】
本明細書において例示的な例として開示されている幾つかの例示的実施形態において、あるシステムは、デジタル処理デバイスによって具現されかつ文書の１つまたは複数の文書フォントを少なくとも１つの置換フォントへ少なくとも１つの文書固有フォントマッピング制限によって制限されるマッピングによってマップするように構成される自動フォントマッピングサブシステムと、上記少なくとも１つの置換フォントを用いて上記文書をレンダリングするように構成されるレンダリングサブシステムとを備える。
【図面の簡単な説明】
【００１０】
【図１】本明細書に開示されているフォント置換を含む文書処理システムを示す線図である。
【図２】アプリケーションプログラムプラグインを使用する文書処理システムの例示的実装を示す線図である。
【図３】図１のシステムによりフォント置換処理の間に適切に生成される例示的なユーザインタフェースディスプレイを示す線図である。
【図４】図１のシステムによりフォント置換処理の間に適切に生成される例示的なユーザインタフェースディスプレイを示す線図である。
【図５】図１のシステムによりフォント置換処理の間に適切に生成される例示的なユーザインタフェースディスプレイを示す線図である。
【発明を実施するための形態】
【００１１】
本明細書において、フォント類似度を基礎として置換フォントを選択する既存のフォントマッピングアプローチの欠点は、これらのマッピングアプローチが、レンダリングされている特定の文書を参照することなく概して包括的に動作する点にあることが認識されている。即ち、文書固有の考慮事項は考慮されない。これは、概して問題とされてきていないが、その理由は、適切なフォント類似性メトリックによって測定される最もよく類似するフォントの選択は最適結果を与えるものと予期されていることにある。
【００１２】
しかしながら、本明細書においては、文書固有インスタンスによっては、これが事実でないことが認識されている。例えば、文書によっては、異なるタイプのテキストコンテンツを表現するために異なるフォントが意図的に使用される。単なる例示的な一例として、演劇の台本では、異なる役者に帰属するせりふコンテンツが異なるフォントを用いて区別される場合がある。フォントマッピングがこれらの異なる文書フォントを１つの最も類似する置換フォントにマッピングすれば、異なる文書フォントを用いて符号化された関連情報は失われる。別の文書固有の考慮事項は、レンダリングコストである可能性がある。フォントの中には、版権が取得されている、または別途で独占所有権が取得されている可能性のあるものがあり、よって文書内でこのようなフォントを使用すれば、例えばプリントアウト当たり、文書のダウンロード当たり、ページ当たりまたは他の基準で課金されるライセンス料金が生じる場合がある。よって、ライセンスコストは、文書のページ数、文書のコピー印刷数、文書のダウンロード見込み回数または他の文書固有情報に依存する。
【００１３】
他の文書固有の考慮事項は、所定の文書に対する所定のフォントの使用に不利に働く場合がある。例えば、独占所有権のあるフォント集合は、特定のクラスのアプリケーションまたはユーザに対してのみ使用を許諾される場合があり、よってそのクラスに属さない文書に使用されるべきではない。所定のフォントもまた、そのサイズに起因して望ましくない場合がある。例えば、レンダリングされるテキストユニットを（例えば行または行数、ページまたはページ数、等々で測定されるような）割り付けられた空間に適合できないほど大きくするフォントは、望ましくない場合がある。
【００１４】
図１を参照すると、改良されたフォント置換を有する文書処理システムが開示されている。文書処理システムは、ディスプレイ１２または他のユーザインタフェース出力デバイスとキーボード１４、マウス（不図示）または他のユーザインタフェース入力デバイスとを有する例示的なコンピュータ１０等の１つまたは複数のコンピュータによって適切に実装される。１つまたは複数のコンピュータには、１つまたは複数のデスクトップコンピュータ、１つまたは複数のノートブックコンピュータ、１つまたは複数のネットワークサーバ、１つまたは複数のインターネットサーバまたはこれらの様々な組合せが含まれてもよい。また、文書処理システムの一部または全てを、マーキングエンジン（例えば、デジタル処理ケイパビリティを有する多機能印刷デバイス）等の１つまたは複数の他のデジタル処理デバイス上に実装することも企図される。
【００１５】
引き続き図１を参照すると、コンピュータ１０または別のデジタル処理デバイスまたは協働するデジタル処理デバイスグループ上に適切に実装される文書生成及び／または処理アプリケーション２０は、テキストコンテンツを含む文書２２を生成または処理する。文書２２の生成／処理の一部として、アプリケーション２０は、合計ページ数、合計段落数、等々のような文書の特徴２４を定量化する。またアプリケーション２０は、文書２２内に使用されている文書フォント２６の集合も追跡する。文書フォント２６は、置換されることが許容されるフォント、または埋め込まれたフォントをレンダリングのために常に利用可能であるように、フォントが内部に文書と共に格納される、または文書と共に送信される埋め込みフォントを含んでもよい。
【００１６】
またアプリケーション２０は、ユーザインタフェース２８も実装し、それを介して人間であるユーザが、文書２２を作成し、修正し、印刷し、または別途操作するためにアプリケーション２０と相互に作用する。実施形態によっては、ユーザインタフェース２８は、文書フォント２６を用いてコンピュータ１０のディスプレイ１２上へ文書２２のレンダリングを表示するグラフィカルな「見たものが、手に入るもの」またはＷＹＳＩＷＹＧインタフェースである。他の実施形態では、ユーザインタフェースはテキストベースの、または他のインタフェースである。
【００１７】
何らかの時点で、文書２２はレンダリングされるべきものである。本明細書で使用しているように、「レンダリング」という用語は文書の物理的印刷を包含し、かつポータブルドキュメントフォーマット（ＰＤＦ）ファイル、ポストスクリプト（ＰＳ）ファイル、等々のような印刷対応フォーマットへの文書２２のレンダリングも包含する。このような目的で、レンダリングサブシステム３０が設けられる。レンダリングサブシステム３０は、文書２２の物理的印刷を生成するマーキングエンジンを含んでもよく、または、レンダリングサブシステム３０はＰＤＦファイル生成器等のソフトウェア専用コンポーネントであってもよい。何れの場合も、レンダリングサブシステム３０は、文書２２を印刷対応フォーマットに変換するレンダリングエンジン３２を含む。レンダリングエンジン３２は、コンピュータ１０によって、または別のデジタル処理デバイスによって具現されてもよい。例えば、多機能印刷デバイスの場合、レンダリングエンジン３２は、全体的または部分的に、多機能印刷デバイスの専用プロセッサによって具現されてもよく、かつ／または全体的または部分的に、印刷対応ファイルを生成するサーバコンピュータ、等々によって具現されてもよい。またレンダリングシステム３０は、レンダリングに利用可能なフォント集合３４へのアクセスも含み、またはこれを有する。フォント集合３４の幾つかの、または全てのフォントは、レンダリングシステム３０に（例えば、多機能印刷デバイスのメモリに）格納されてもよい。フォント集合３４の幾つかの、または全てのフォントは、レンダリングシステム３０から遠隔的に、例えばデジタルネットワークまたはインターネットを介してアクセス可能なサーバにおいて格納されてもよい。
【００１８】
レンダリングに利用可能なフォント集合３４は、概して文書生成／処理アプリケーション２０に利用可能なフォント集合とは異なってもよく、よって文書フォント２６は、レンダリングに利用可能なフォント集合３４に含まれない１つまたは複数のフォントを含んでもよい。典型的には、このような利用できないフォントはレンダリングされ得ない。
【００１９】
事例によっては、文書フォントは文書２２と共に埋め込まれる埋め込みフォントであってもよく、文書と共にレンダリングサブシステム３０へ伝達される。レンダリングサブシステム３０に埋め込みフォントを処理する能力があれば、埋め込みフォントは、フォント集合３４に含まれていなくてもレンダリングされることが可能である。しかしながら、埋め込みフォントはレンダリングサブシステム３０によって判読できないフォーマットで埋め込まれる場合があることに起因して、これは必ずしも作動するとは限らない。レンダリングサブシステム３０が埋め込みフォントを処理することができなければ（かつ埋め込みフォントがフォント集合３４に含まれていなければ）、文書２２と共に埋め込まれているにも関わらず、埋め込みフォントはレンダリングサブシステム３０によってレンダリングされ得ない。
【００２０】
従って、文書フォントがレンダリングのために置換されてもよい理由の１つは、文書フォントがレンダリング用に利用できない場合があることにある。しかしながら、文書フォント２６のフォントがフォント集合３４において利用可能であるとしても、またはレンダリングサブシステム３０によって読取り可能なフォーマットで埋め込まれているとしても、なお、文書を個人化する、視力が限られている人用に可読性を上げる、フォントのライセンスコストを下げる、所定の文書タイプ用に使用されるべきフォントを指定する組織的一律基準との適合性を保証する、等々のような何らかの他の理由で、文書フォントを置換フォントにマッピングすることが望ましい場合がある。
【００２１】
上記に鑑みて、マッピングされるべきフォント集合の個々についてフォントマッピングを実行するフォントマッピングサブシステム４０が設けられる。マッピングされるべきフォント集合は、文書フォント２６のうちの１つ、２つ、３つ以上または全てを含んでもよい。マッピングは、レンダリングに利用可能なフォント集合３４から選択される置換フォントに対して行われる。またフォントマッピングサブシステム４０は、任意選択として、１つまたは複数の文書固有フォントマッピング制限４４も受信する。例示として、これらの制限４４は、各フォントが異なる置換フォントにマッピングされるという要件、印刷コストに対する制約（例えば、これはフォントのライセンス料金により影響される場合がある）、レンダリングされるフォントサイズに対する制限（例えば、単行のタイトルはレンダリングされたテキストでも単行のままであると求めることによって定量化される）、等々を含んでもよい。
【００２２】
フォントマッピングサブシステム４０の出力は、マッピングされるべき文書フォントの各々についてレンダリングに利用可能なフォント集合３４から最適に選択される置換フォントを指示する最適化されたフォントマッピング４８である。最適化されたフォントマッピング４８は、任意選択として、人間であるユーザによりアプリケーション２０のユーザインタフェース２８を介して調査されかつ認証され、または修正される。任意選択である認証の後、最適化されたフォントマッピング４８は、アプリケーション２０においてフォント置換サブモジュール５０により処理される。アプリケーション２０において置換フォントが利用可能であれば、フォント置換サブモジュール５０は、置換フォントをフォントマッピング４８が指定する通りに使用するためにアプリケーション２０における任意のＷＹＳＩＷＹＧレンダリングを更新する。アプリケーション２０において置換フォントが利用できなければ、フォント置換サブモジュール５０は、任意選択として、欠けている置換フォントをフォントデータベースまたは他のソースからダウンロードして入手することを試行し、次いでＷＹＳＩＷＹＧレンダリングを更新する。アプリケーション２０において置換フォントが利用できず、かつ入手不可であれば置換は実行されないが、好適には、任意のＷＹＳＩＷＹＧレンダリングは、置換フォントの不在に起因してＷＹＳＩＷＹＧレンダリングはプリントアウト、ＰＤＦファイルまたは他のレンダリングを精確には示さない場合があることを示す注釈によってフラグされる。何れの場合も、文書２２がレンダリング（即ち、印刷、ＰＤＦファイル生成、ＰＳファイル生成、等々）用にレンダリングサブシステム３０へ送信される場合、適切には、レンダリングにおいて使用するための任意の１つまたは複数の置換フォントを指定するためにフォントマッピング４８が包含される。
【００２３】
次に、引き続き図１を参照して、フォントマッピングサブシステム４０について詳述する。フォントマッピングサブシステム４０は、文書２２の１つまたは複数の文書フォント２６が少なくとも１つの置換フォントにマッピングされる文書固有フォントマッピングを実行し、フォントマッピングは、少なくとも１つの文書固有フォントマッピング制限４４によって制限される。フォントマッピングは、文書フォント２６と（フォント対類似性メトリック６０によって測定される）その置換物との間の視覚的類似性を考慮し、かつ１つまたは複数の文書指定フォントマッピング制限４４も考慮する。
【００２４】
フォント対類似性メトリック６０は、適切にはｓ（ｉ，π（ｉ））形式の類似性メトリックによって具現される。但し、ｉは文書フォントを示し、かつπ（ｉ）は置換フォントへのマッピング（候補）を示し、よってπ（ｉ）は考慮中の置換フォント（候補）を示す。類似性メトリックｓ（−，−）は、様々な方法で具現されることが可能である。実施形態によっては、各フォントｉ，π（ｉ）で書かれた基準サンプルテキストは、そのエレメントが基準サンプルテキストの選択された定量的特性を表す特徴（例えば、特徴ベクトル）の集合を抽出するために処理され、かつ関数ｓ（−，−）は、フォントｉ及びフォントπ（ｉ）の特徴集合を受信しかつこれらの特徴ベクトル間の類似性または距離（例えば、コサイン類似度、ユークリッド距離、等々）または他の比較測度を計算する。他の実施形態では、関数ｓ（−，−）は、フォント対の類似値を表にするルックアップテーブルとして具現される。このようなルックアップテーブルは、距離メトリックまたはこれに類似するものを用いて計算されることが可能であり、或いは手動で、例えばフォント対の類似性または相違に関する人間の主観的判断に基づいて生成されることが可能である。さらに、類似性関数ｓ（−，−）は、（例えば、コサイン類似度を用いて取得されるような）連続関数である可能性もあれば、不連続または離散関数である可能性もあることは留意される。
【００２５】
ある例示的な実施形態では、あるフォントに関する特徴ベクトルは下記のように計算される。ある文字集合（例えば、文字集合｛Ａ−Ｚ，ａ−ｚ，０−９｝）の各記号は、レンダリング文字のビットマップを生成することによって電子的にレンダリングされ、各ビットマップについて特徴集合が計算される。あるアプローチでは、これらの特徴は、傾斜方位の１２８次元のヒストグラムである。次に、フォントを表す特徴ベクトルを取得するために、文字毎の特徴集合が連結される。関数ｓ（ｉ，π（ｉ））は、フォントｉ，π（ｉ）を表す特徴ベクトルの類似度（例えば、コサイン類似度）を測定する。
【００２６】
文書固有フォントマッピング制限４４のうちの幾つかは、適切には、最適化制約６２として表現されてもよい。例えば、文書を印刷するためのライセンス料金の上限を含む制限は、フォントマッピング最適化に対する上限制約として表現されてもよい。例示的な別の例として、異なる２つの文書フォントを同一の置換フォントにマッピングすることを禁じる制限は、異なる置換フォントの合計数に対する下限として表現されることが可能である。
【００２７】
文書固有フォントマッピング制限４４のうちの幾つかは、考慮中の置換フォント集合をフィルタリングすることによってより良く表現されてもよい。このような目的で、フォントマッピングサブシステム４０は、フォントマッピングにおいて使用するためのレンダリングに利用可能なフォント集合３４の部分集合を選択する利用可能フォント部分集合セレクタ６４を含む。例えば、利用可能フォント部分集合セレクタ６４は、選択される利用可能置換フォントの部分集合から、文書２２が属する文書タイプの文書の印刷において使用を認められない所定のフォントを除外してもよい。
【００２８】
ある適切な実施形態では、フォントマッピングサブシステム４０は、マッピングされるべき文書フォントと、対応するマッピングされた少なくとも１つの置換フォントとの類似性を測定する目的関数６８の制約付き最適化を実行することによってフォントマッピングを実行する最適化エンジン６６を含み、上記制約付き最適化は、文書固有フォントマッピング制限４４のうちの１つまたはそれ以上を具現する１つまたは複数の最適化制約６２によって制約される。制約付き最適化は、レンダリングに利用可能なフォント集合３４の個々の部分集合に対応し、上記部分集合は、セレクタ６４により、文書固有フォントマッピング制限４４のうちの１つまたはそれ以上を基礎として選択される。
【００２９】
フォントマッピングサブシステム４０により適切に実行されるフォントマッピングの例示的な実施形態は、下記の通りである。ｆはマッピングされるべき文書フォント２６の集合を示すものとし、かつＦは利用可能フォント部分集合セレクタ６４により選択されるレンダリングに利用可能なフォント集合３４の部分集合を示すものとする。従って、Ｆは、レンダリングに利用可能なフォント集合３４と同延であるか、レンダリングに利用可能なフォント集合３４の選択された部分集合の何れかである。ｆとＦとの共通部分は、空集合である場合も、空集合でない場合もある。π：ｆ→Ｆは、フォントマッピング（候補）を示すものとする。πｏｐｔ：ｆ→Ｆは、フォントマッピングサブシステム４０により決定されるべき最適化されたフォントマッピング４８を示すものとする。
【００３０】
目的関数６８は、マッピングされるべき文書フォントの集合ｆと、置換フォントの集合（候補）Ｆとの間の類似性を測定する。ｓ：ｆ×Ｆ→Ｒを、マッピングされるべき文書フォントと置換フォントの集合Ｆの置換フォントとの間の類似性を測定する関数であるものとする。ｓ（ｉ，π（ｉ））は、文書フォントｉとその（マッピングされる）置換フォント（候補）π（ｉ）との間の類似性を示すものとする。目的関数６８の適切な実施形態は、
【数１】
2011238224.tif 000003
である。よって、最適化されたフォントマッピング４８を下記の制約付き最適化として書き表すことができる。
【数２】
2011238224.tif 000004
但し、｛ｇ（ｆ，π）｝は最適化制約６２の集合を示す。方程式（１）及び（２）は、類似度ｓ（ｉ，π（ｉ））が増加していること、即ち、より大きい値のｓ（ｉ，π（ｉ））は、文書フォントｉとその置換フォント（候補）π（ｉ）との間のより大きい類似性を示すことを想定している。反対に、ｓ（ｉ，π（ｉ））が低減していて、より小さい値のｓ（ｉ，π（ｉ））がフォントｉとπ（ｉ）との間のより大きい類似性を示していれば、方程式（１）及び（２）のｍａｘ項及びａｒｇ  ｍａｘ項は、適切にはｍｉｎ項及びａｒｇｍｉｎ項によって置換される。
【００３１】
本明細書で使用しているように、「最適」及び「最大」及び「最小」等の用語は、自動最適化アルゴリズムまたは自動最大化アルゴリズムまたは自動最小化アルゴリズムによって生成される出力を包含するものとして理解されるべきであり、これらの出力は、必ずしも大域的な最適値、最大値または最小値でなくてもよい。例えば、方程式（１）を解くと、目的関数の局所的最大値が発生する場合がある。技術上知られるように、このような局所的極値は容認できるものである場合があり、或いは、局所的極値が容認できないものであれば、より良い結果を得るために、異なる開始値を用いて最適化（または最大化または最小化）が再度実行されてもよい。
【００３２】
制約の集合｛ｇ（ｆ，π）｝に適切に包含される幾つかの例示的な制約は、下記の通りである。
【００３３】
任意選択として含まれる１つの制約は、フォントマッピングの前後で文書２２内に同数のフォントが存在することを保証する。即ち、２つの文書フォントは、同じ置換フォントにマッピングされ得ない。この制約は、次のように表すことができる。
【数３】
2011238224.tif 000005
方程式（３）は、文書フォント２６の集合の全文書フォントがマッピングされることを想定し、即ち、ｆは文書フォント２６の集合の全ての文書フォントを含むことを想定している。これが当てはまらない場合には、¬ｆが、文書フォント２６の集合のうちのマッピングされていない文書フォント、即ちｆに含まれていない文書フォントの集合を示すものとする。従って、文書フォント２６の集合はｆと¬ｆとの和集合であり、かつｆと¬ｆとの共通部分は空である。これらの定義を用いれば、方程式（３）は、
【数４】
2011238224.tif 000006
へと一般化されることが可能である。第２の項
【数５】
2011238224.tif 000007
を実装する１つの方法は、利用可能フォント部分集合セレクタ６４を使用して可能な置換フォントの集合Ｆから集合¬ｆ内の任意のフォントを除外することであり、方程式（３）の制約は、この後に使用されることが可能である。言い替えれば、方程式（３）は、フォントの集合¬ｆが可能な置換フォントとして利用不可にされることによって使用可能である。
【００３４】
任意選択として包含される別の制約は、ライセンスコストに関連している。フォントの中にはライセンス料金を伴うものがあることから、新規文書については合計ライセンス料金をキャッピングすることが望ましい場合がある。ｃ（π（ｉ））を所定の置換フォント（候補）π（ｉ）に関連づけられるコストであるものとし、かつＣをコストの上限であるものとする。但し、コストはＵ．Ｓ．ドル、ＥＵユーロまたは他の適切な通貨単位または通貨換算で測定される。合計ライセンスコストの制約は、
【数６】
2011238224.tif 000008
と書き表すことができる。文書フォント２６の集合の全文書フォントがマッピングされるわけではないとすれば（即ち、集合¬ｆが空でなければ）、上記制約は、
【数７】
2011238224.tif 000009
のように書き表すことができる。但し、Ｃ’は、
【数８】
2011238224.tif 000010
によって与えられる。ここで、方程式（５）の引き算項はマッピングπに依存せず、よってＣ’は最適化の実行に先立って予め計算されることが可能である。
【００３５】
フォントｍのコストｃ（ｍ）は、所定の文書に関して固定されてもよい（即ち、文書当たりのライセンス料金）。一方で、コストｃ（ｍ）は、文書のレンダリングにおけるフォントｍの使用量を定量化する文書パラメータに機能的に依存している場合もある。例えば、文書のレンダリングにおけるフォントｍの使用量を定量化する上記文書パラメータは、文書のレンダリングにおける文書ページ数、文書のレンダリングにおける文書コピー数、文書のレンダリングにおける文書ページ数と文書コピー数との積、等々であってもよい。
【００３６】
既に述べたように、幾つかの文書固有フォントマッピング制限は、利用可能フォント部分集合セレクタ６４に可能な置換フォントの集合Ｆをレンダリングに利用可能なフォント集合３４の部分集合として選択させることによってより良く実装される。方程式（３’）に関連して既に述べたように、これが有益である１つの状況は、文書フォントの中にマッピングされないものがある場合にはマッピングによってフォント数を変えてはならない、という制限を実装することにある。この場合、セレクタ６４は、マッピングされない文書フォントの集合¬ｆの構成要素である任意のフォントをＦから除外する。
【００３７】
利用可能フォント部分集合セレクタ６４によって適切に実装される他の文書固有フォントマッピング制限は、置換フォントに対するサイズ制限である。例えば、文書固有制限は、テキストの所定の部分は割り当てられた空間内に嵌らなければならない、ということであってもよい。例示的な例として、タイトルは単行に嵌らなければならない、または、段落は指定された行数（任意選択として、さらにプラスマイナス数行の指定された余白）内に嵌らなければならない、という制限を実施することが望まれる場合もある。実装に際して、セレクタ６４は、適切には、レンダリングに利用可能なフォント集合３４の各フォントを用いて（例示として）タイトルを電子的にレンダリングし、レンダリングされるタイトルが長すぎれば、そのフォントを可能な置換フォントの集合Ｆから除外する。
【００３８】
実施形態によっては、最適化エンジン６６によって実行される制約付き最適化は、線形プログラミング（ＬＰ）アルゴリズムによって実行される。本明細書において示しているように、実施形態によっては、制約付き最適化は整数線形プログラミング（ＩＬＰ）アルゴリズムによって実行されることが可能である。例示的な例として、０−１線形プログラミング（０−１ＬＰ）アルゴリズムによって実行される制約付き最適化について述べる。この場合、目的関数６８は方程式（２）において述べた通りであり、制約の集合｛ｇ（ｆ，π）｝は、方程式（３）の制約（先に述べたように、マッピングされないフォントは、セレクタ６４の使用によってＦからマッピングされないフォント¬ｆを除外するように対処される）及び方程式（４）または（４’）の制約を含む。０−１ＬＰアルゴリズムは、変数が２進値をとるタイプのＩＬＰである。
【００３９】
０−１ＬＰの説明に際して、Ｍをマッピングされるべき文書フォントの集合ｆの濃度であるものとし（即ち、Ｍは文書フォントの集合ｆにおけるフォント数である）、かつＮを可能な置換フォントの集合Ｆの濃度であるものとする。所定の文書フォントｉ∈ｆの置換フォント（候補）π（ｉ）∈Ｆへのマッピングｉ→π（ｉ）は、Ｎ次元二値ベクトルｖｉを用いて適切に符号化される。このベクトルｖｉは、指数π（ｉ）に対応する単一の非ゼロ値を有する。従って、マッピングされるべき全ての文書フォントｆの大域的なマッピングは、全てのｉ∈ｆのベクトルｖｉを連結することによってＭ×Ｎ次元二値ベクトルＶとして符号化されることが可能である。連結されたこのベクトルＶは、正確にＭ個の非ゼロ値を有する。
【００４０】
さらに、ｓｉは、文書フォントｉ∈ｆとＦにおける全フォントとの間の類似性のＮ次元ベクトルを示すものとする。Ｓは、Ｍ個のベクトルｓｉ，ｉ＝１，．．．，Ｍを連結して得られるＭ×Ｎ次元ベクトルを示すものとする。これらの定義を用いれば、方程式（１）の目的関数は、
【数９】
2011238224.tif 000011
として書き直すことができる。但し、上付き文字Ｔは転置演算を示す。
【００４１】
方程式（３）の制約は、以下のように０−１ＬＰ形式で符号化されることが可能である。ｅｋは、指数ｋに単一の非ゼロ値を有するＮ次元二値ベクトルを示すものとする。Ｅｋは、ベクトルｅｋのＭ個のインスタンスを連結して得られるＭ×Ｎ次元ベクトルを示すものとする。ｆにおける２フォントがＦにおける同一フォントにマッピングされないこと（これは、方程式（３）の制約の意向である）を保証するために、下記の０−１ＬＰ制約、
【数１０】
2011238224.tif 000012
が実施される。故に、方程式（３）の制約の実施は、０−１ＬＰ形式でのＮ個の制約の実施に変わる。
【００４２】
方程式（４）の制約は、以下のように０−１ＬＰ形式で符号化されることが可能である。γは、可能な置換フォントの集合Ｆの各フォントに関連づけられるコストを含むＮ次元ベクトルを示すものとする。Γは、ベクトルγのＭ個のインスタンスを連結して得られるＭ×Ｎ次元ベクトルを示すものとする。方程式（４）の制約を実施するために、即ち、ライセンス料金の合計コストがＣ以下であることを保証するために、下記の０−１ＬＰ制約、
【数１１】
2011238224.tif 000013
が実施される。同様に、マッピングされないフォントの集合¬ｆが空でない事例、即ち方程式（４’）の事例では、０−１ＬＰ制約
【数１２】
2011238224.tif 000014
が実施される。
【００４３】
方程式（６）の目的関数を制約
【数１３】
2011238224.tif 000015
及び／または
【数１４】
2011238224.tif 000016
の下で最大化することは、０−１ＬＰ問題である。これは、問題を多項時間で解くことができる一般的アルゴリズムが存在しないＮＰ困難問題である。しかしながら、緩和アルゴリズム及び分枝限定アルゴリズムを基礎とする方法は、この目的関数を正確に、または近似的に最適化するために適切に使用される。例えば、「線形プログラミング緩和法」ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｌｉｎｅａｒ＿ｐｒｏｇｒａｍｍｉｎｇ＿ｒｅｌａｘａｔｉｏｎ（最終アクセス、２０１０年２月１７日）を参照されたい。
【００４４】
文書固有フォントマッピング制限の中には、利用可能フォント部分集合セレクタ６４によって適切に実装されるものがある。例示的な例として、ある特定の制約について、即ち、全てのタイトルは単行に嵌らなければならない、という制約について考察されたい。文書フォントｉで書かれている文書２２内のタイトルに対するこの制限を実装するために、タイトルは、レンダリングに利用可能なフォント集合３４の各フォントを用いて電子的にレンダリングされる。電子的にレンダリングされるタイトルが２行以上を占有するフォントは何れも、セレクタ６４によって可能な置換フォントの集合Ｆから除外される。これは、探索空間のサイズを短縮する（即ち、可能な置換フォントの集合Ｆの濃度Ｎを下げること。これにより０−１ＬＰ実装の計算コストが下がる）以外には０−１ＬＰ実装に影響しない。
【００４５】
図２を参照すると、アプリケーションプログラムプラグインを使用する例示的な実装が線図で示されている。図２のシステムは、ユーザのウェブブラウザまたは他の文書エディタ（例えば、Ｍｉｃｒｏｓｏｆｔ  ＷｏｒｄまたはＡｄｏｂｅ    Ａｃｒｏｂａｔ）にインストールされるプラグイン８０と、計算を実行しかつフォント置換要求に応答できるウェブサービスを管理するセントラルサーバ８２と、図示されているようにサーバ８２に位置決めされる、またはサーバ８２によってアクセス可能なフォントのデータベース８４とを含む。フォントのデータベース８４は事前に計算された特徴で指数づけされ、かつテキストタグで注釈を付けられる。
【００４６】
プラグイン８０は、文書２２について、図１の文書生成／処理アプリケーション２０の文書及びフォント分析機能を実行する。文書２２内で使用されている全てのフォント（または埋め込みフォントの参照）が抽出される。また、合計ページ数、段落数、等々のような文書レベルの特徴も計算される。プラグイン８０は、クエリ定式化も実行する。フォント置換要求は、文書内で検出されるフォントのリストが存在しなければ、またはユーザが置換セッションを開始する意向であれば定式化される。後者の場合、ユーザは任意選択として、フォント置換セッションを明示的に、例えば最大ライセンス料金を指定することによってパラメータ化する選択肢を与えられる。
【００４７】
サーバ８２では、リスナ機能が提供される。図示されているサーバ８２は、ウェブサーバである。サーバ８２によって実行されるウェブアプリケーションは、予め画定されたポート上での接続を待機する。このアプリケーションは、フォントのデータベース８４に問合せを行って、最適化手順を開始することができる。サーバ８２は、図１のフォントマッピングサブシステム４０のフォント対類似性メトリック６０に類似するフォント類似性評価機能も提供する。２つのフォントを所与として、フォント間の視覚的類似性を示す数値が視覚的特徴及び単純な距離測度を用いて計算される。
【００４８】
プラグイン８０またはサーバ８２もしくはこれらの双方は、文書固有制限の構成機能を提供する。制限の集合は（図１の最適化制約６２に類似する）制約として、かつ／または（図１の利用可能フォント部分集合セレクタ６４によって実装されるタイプの）フォント選択基準として構成される。制約または選択基準は、制約のタイプに依存して手動で、または自動的に構成される。典型的な制約は、文書を刊行するためにユーザにより準備される文書当たりの最大コストを表すライセンス料金限度を含む。他の制約は、適切には、フォント置換動作後に維持されなければならない合計ページ数等が自動的に表される。
【００４９】
サーバ８２は、フォントマッピング（即ち、置換フォント選択）機能を提供する。置換フォントは、制約６２の下で目的関数６８を最大化する（図１のフォントマッピングサブシステム４０を参照して本明細書に記述したような）最適化を用いて計算される。本明細書に記述している例示的実施形態では、最適化は、０−１線形プログラミング（０−１ＬＰ）問題として適切に定式化される。選択されたフォントは、サーバ８２から、要求を定式化したプラグイン８０へ伝達される。
【００５０】
プラグイン８０では、フォント置換機能が提供される。置換されるべきフォントは、サーバ８２により提案される置換フォントで置換される。置換フォントがユーザのマシン内で入手できなければ、プラグインは不在のフォントをダウンロードする許可を求める。
【００５１】
図３を参照すると、文書固有フォントマッピング制限を規定するユーザ提供情報を獲得するために、適切には図１のユーザインタフェース２８によって使用されるユーザインタフェースダイアログウィンドウ９０が示されている。ダイアログウィンドウ９０の上部には、文書名、文書クラス及びレンダリングエンジンが明示されている。文書クラスは、任意選択として、利用可能フォント部分集合セレクタ６４によって適用される置換フォントフィルタリングのための文書固有基準を提供する。例示的な例として、「商用／ウィジェット部門」の例示的な文書クラスは、可能な置換フォントの集合Ｆから商業目的での使用を認可されていない所定のフォントを除外する基準を提供する場合がある。レンダリングエンジンは、典型的には、レンダリングに利用可能なフォント集合３４を決定する。
【００５２】
また、ダイアログウィンドウ９０は、文書フォントをそのステータス（「利用可能」、「利用不可」または「非許諾」）及び、適用可能であれば、ページ当たりのライセンスコスト（図３及び図４では、非ゼロのフォントライセンスコストが定量的値ではなく塗りつぶされたボックスで図示されていることに留意されたい）と共に記載している。このリストの最左欄は、各フォントがマッピングされるべきかどうかをユーザが選択できる選択ボックスも提供している。従って、この例示的な例において、マッピングされるべきフォント集合ｆは３つのフォント、「Ｏｐｅｎ  Ｓａｎ  Ｓｅｒｉｆ」、「Ｏｐｅｎ  ＦａｎｃｙＢｏｌｄ」及び「Ｏｌｄ  Ｅｔｒｕｓｃａｎ」を含み、一方でマッピングされないフォント集合¬ｆは単一のフォント、即ち「Ａｒｉａｌ」を含む。
【００５３】
文書フォントのリストの下に示されているオプションでは、ユーザは、２つの文書フォントを同一のレンダリングフォントで置換することを認可されるべきかどうかを選択することができる。このオプションは「いいえ」であるように選択されて示されているが、これは、方程式（３）の制約が実装されるべきものであることを示す（¬ｆに属するマッピングされない「Ａｒｉａｌ」フォントは、セレクタ６４の行動によって可能な置換フォントの集合Ｆから除外されている）。次のオプションである、「タイトルを一行に保持するか？」は、現時点で「はい」として選択されている。従って、この場合も、セレクタ６４は、そのフォントがタイトルを２行（またはそれ以上）のテキストとしてレンダリングする文書「ＮｅｗＷｉｄｇｅｔＰｒｅｓｓＲｅｌｅａｓｅ．ｏｄｔ」の任意の一行タイトルについては、そのフォントを全て可能な置換フォントの集合Ｆから除外するために使用される。最後のユーザオプションは最大ライセンス料金を指定することであるが、これは現時点で文書コピー当たり＄０．２０に設定されて示されている。
【００５４】
図４を参照すると、適切には図３のダイアログウィンドウ９０の入力に従って実行されるフォントマッピングの結果を表示するユーザインタフェースダイアログウィンドウ９２の例示的な例が示されている。マッピングされない「Ａｒｉａｌ」フォントは、「Ａｒｉａｌ」で「置換」される（従って、Ａｒｉａｌフォントを「マッピングしない」、を実装する）ものとして示されている。「Ｏｐｅｎ  Ｓａｎ  Ｓｅｒｉｆ」フォントはマッピングに利用可能であったが、最適化されたフォントマッピングによってこのＯｐｅｎ  Ｓａｎ  Ｓｅｒｉｆフォントは変わらずに保たれた。残りの２フォントは、新しいフォントにマッピングされる。ダイアログウィンドウ９２の下側では、ユーザに、「認可して印刷」、「認可」（フォントマッピングを格納するが、文書を即座には印刷しない）、「プレビュー」（ユーザレビュー用に、置換フォントによるレンダリングをディスプレイ１２上に表示する）、「再マッピング」（図３のダイアログウィンドウ９０へ戻る）及び「キャンセル」を含む幾つかの選択可能なオプションが提供される。
【００５５】
図５は、可能なフォントマッピングの別の結果を示す。この場合、ダイアログウィンドウ９４はユーザに、「要求されたマッピングは、文書コピー当たり＄０．２０の許容される最大ライセンス料金を達成できなかったために実行できませんでした。Ａｒｉａｌフォントをライセンス料金がより低いフォントに置換することを提案します」と通知する。このダイアログウィンドウ９４は、本明細書に開示されている制約付き最適化アプローチの優位点を示し、即ち、制約付き最適化が失敗すると、通常、どの制約が充足され得なかったかを決定することができる。この場合、方程式（４’）の制約は、マッピングされないＡｒｉａｌフォントのライセンス料金（方程式（５）に従って方程式（４’）におけるＣ´に影響する）が高すぎたという理由で充足され得なかった。本例において、達成不可能な制約の検出は、Ｃ’が「Ａｒｉａｌ」フォントのライセンス料金に起因して負であったならば自明であった可能性がある。ダイアログウィンドウ９４の下部において、ユーザには、「再マッピング」（図３のダイアログウィンドウ９０へ戻る）または「キャンセル」の選択肢が与えられる。
【図１】
2011238224.tif 000017
【図２】
2011238224.tif 000018
【図３】
2011238224.tif 000019
【図４】
2011238224.tif 000020
【図５】
2011238224.tif 000021