(57)【要約】【課題】  チャートなどの視覚データオブジェクトに関連するラベルレイアウトを最適化するためのアルゴリズムを提供する。【解決手段】  ラベルはまず、ラベルを形状として定義するチャート定義ファイル内に置かれる。ラベルの初期レイアウトが作成され、採点される。次いで、形状は、最適なスコアに最も近いスコアを有するレイアウトに対応するラベルの最適レイアウトが取得されるまで、繰返し操作される。次いで、最適レイアウトは、画面上に視覚データオブジェクトをレンダリングする際に使用される。【選択図】  図２
2006114013.tif 000002
【特許請求の範囲】
【請求項１】
視覚データオブジェクトに関連するラベルを自動的に配置するためのコンピュータ実施方法であって、
前記ラベルの第１のレイアウトを判断することと、
前記第１レイアウトを採点して、第１のスコアを判断することと、
前記ラベルの第２のレイアウトを判断することと、
前記第２レイアウトを採点して、第２のスコアを判断することと、
前記第１スコアを前記第２スコアと比較することと、
前記第１スコアの前記第２スコアとの前記比較に応じて、前記視覚データオブジェクトをレンダリングするために選択されたレイアウトとして、前記第１レイアウトおよび前記第２レイアウトのうちの１つを続行することとを含むことを特徴とするコンピュータ実施方法。
【請求項２】
前記第１レイアウトを採点して、前記第１のスコアを判断することは、目標関数を実行することをさらに含み、前記目標関数は、前記第１レイアウトが採点される目標を提供することを特徴とする請求項１に記載のコンピュータ実施方法。
【請求項３】
前記目標は、前記ラベルの重なりを最小化することに対応することを特徴とする請求項２に記載のコンピュータ実施方法。
【請求項４】
前記目標は、前記ラベルから前記チャート内のその関連アンカーへの距離を最小化することに対応することを特徴とする請求項２に記載のコンピュータ実施方法。
【請求項５】
前記第１レイアウトを採点して、前記第１のスコアを判断することは、前記第１レイアウトに関連するスコアを最適レイアウトに関連する別のスコアと比較することをさらに含むことを特徴とする請求項１に記載のコンピュータ実施方法。
【請求項６】
前記第１レイアウトおよび前記第２レイアウトのうちの１つを続行することは、最適レイアウトに最も密接に対応するレイアウトを続行することをさらに含むことを特徴とする請求項５に記載のコンピュータ実施方法。
【請求項７】
前記ラベルの第２のレイアウトを判断することは、摂動関数を実行することをさらに含み、前記摂動関数は、１組の制約に従って前記第１レイアウトを変更することを特徴とする請求項１に記載のコンピュータ実施方法。
【請求項８】
前記摂動関数は、前記チャート内に含まれる単一のラベルの側面を調整することに対応することを特徴とする請求項７に記載のコンピュータ実施方法。
【請求項９】
最適レイアウトに近似するレイアウトが達成されるまで、前記ラベルの追加のレイアウトを判断し、前記追加レイアウトを採点する複数の反復を繰り返すことをさらに含むことを特徴とする請求項１に記載のコンピュータ実施方法。
【請求項１０】
チャートをレンダリングするためのシステムであって、
チャート要素で前記チャートを定義するように構成されたチャートオブジェクトと、
形状をレンダリングするように動作可能なグラフィックモジュールと、
前記チャートオブジェクトに基づいて形状ベースチャート定義を生成するように動作可能なチャート作成モジュールであって、前記形状ベースチャート定義は、前記グラフィックモジュールによってレンダリングされ得る形状で前記チャートを定義するチャート作成モジュールと、
最適レイアウトに従って、前記チャート内に前記チャートに関連するラベルを自動的に配置するラベル最適化と
を含むことを特徴とするシステム。
【請求項１１】
前記ラベル最適化アプリケーションは、
前記ラベルの第１のレイアウトを判断し、
前記第１レイアウトを採点して、第１のスコアを判断し、
前記ラベルの第２のレイアウトを判断し、
前記第２レイアウトを採点して、第２のスコアを判断し、
前記第１スコアを前記第２スコアと比較し、
前記第１スコアの前記第２スコアとの前記比較に応じて、前記視覚データオブジェクトをレンダリングするために選択されたレイアウトとして、前記第１レイアウトおよび前記第２レイアウトのうちの１つを続行するためのコンピュータ実行可能命令を含むことを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記第１レイアウトを採点して、前記第１のスコアを判断することは、目標関数を実行することをさらに含み、前記目標関数は、前記第１レイアウトが採点される目標を提供することを特徴とする請求項１１に記載のシステム。
【請求項１３】
前記第１レイアウトを採点して、前記第１のスコアを判断することは、前記第１レイアウトに関連するスコアを最適レイアウトに関連する別のスコアと比較することをさらに含むことを特徴とする請求項１１に記載のシステム。
【請求項１４】
前記ラベルの第２のレイアウトを判断することは、摂動関数を実行することをさらに含み、前記摂動関数は、１組の制約に従って前記第１レイアウトを変更することを特徴とする請求項１１に記載のシステム。
【請求項１５】
最適レイアウトに近似するレイアウトが達成されるまで、前記ラベルの追加のレイアウトを判断し、前記追加レイアウトを採点する複数の反復を繰り返すことをさらに含むことを特徴とする請求項１１に記載のシステム。
【請求項１６】
視覚データオブジェクトに関連するラベルを自動的に配置するコンピュータ実行可能命令を含むコンピュータ読取り可能媒体であって、前記命令は、
前記ラベルの第１のレイアウトを判断することと、
前記第１レイアウトを採点して、第１のスコアを判断することと、
前記ラベルの第２のレイアウトを判断することと、
前記第２レイアウトを採点して、第２のスコアを判断することと、
前記第１スコアを前記第２スコアと比較することと、
前記第１スコアの前記第２スコアとの前記比較に応じて、前記視覚データオブジェクトをレンダリングするために選択されたレイアウトとして、前記第１レイアウトおよび前記第２レイアウトのうちの１つを続行することとを含むことを特徴とするコンピュータ読取り可能媒体。
【請求項１７】
前記第１レイアウトを採点して、前記第１のスコアを判断することは、目標関数を実行することをさらに含み、前記目標関数は、前記第１レイアウトが採点される目標を提供することを特徴とする請求項１６に記載のコンピュータ読取り可能媒体。
【請求項１８】
前記第１レイアウトを採点して、前記第１のスコアを判断することは、前記第１レイアウトに関連するスコアを最適レイアウトに関連する別のスコアと比較することをさらに含むことを特徴とする請求項１６に記載のコンピュータ読取り可能媒体。
【請求項１９】
前記第１レイアウトおよび前記第２レイアウトのうちの１つを続行することは、最適レイアウトに最も密接に対応するレイアウトを続行することをさらに含むことを特徴とする請求項１８に記載のコンピュータ読取り可能媒体。
【請求項２０】
前記ラベルの第２のレイアウトを判断することは、摂動関数を実行することをさらに含み、前記摂動関数は、１組の制約に従って前記第１レイアウトを変更することを特徴とする請求項１６に記載のコンピュータ読取り可能媒体。
【請求項２１】
最適レイアウトに近似するレイアウトが達成されるまで、前記ラベルの追加のレイアウトを判断し、前記追加レイアウトを採点する複数の反復を繰り返すことをさらに含むことを特徴とする請求項１６に記載のコンピュータ読取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、チャート上の自動ラベル配置のためのシステムおよび方法に関する。
【背景技術】
【０００２】
チャートは、数値データのグラフィカル表現である。チャートは、複雑なデータを簡潔な容易に理解できる形で提示するのに特に有用である。今日のデスクトップ出版環境では、ユーザは、チャートを用いて印象的なプレゼンテーションを作成することができる。チャートは、ワシントン州、レッドモンドのＭＩＣＲＯＳＯＦＴ  ＣＯＲＰＯＲＡＴＩＯＮ社からの「ＥＸＣＥＬ」（登録商標）などのアプリケーションプログラム内に入力される、基礎となるデータに基づく。次いで、その基礎となるデータを使用して、円グラフ、棒グラフ、ヒストグラム、線グラフなど、複数の異なるフォーマットでデータのチャートを作成することができる。さらに、チャートの各部分は、情報を伝えるのに非常に重要であるチャートの外観を向上させるための関連する色、テクスチャ、および他の効果を有し得る。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
チャート内に含まれるラベルは、チャートの視覚機能および表示に寄与する。ユーザが自動データラベル機能をアクティブ化する場合、数個より多いデータ点を含むチャートは、読むのが難しくなり得る。一般に、以前に提供された自動チャートラベル付けアルゴリズムは、チャート領域を使用するように最適化されていない重なり合うテキストおよびラベルの位置決めをもたらす。したがって、代替の方法が求められている。
【課題を解決するための手段】
【０００４】
本発明の実施形態は、チャートおよびグラフ上のラベル配置を最適化することによって上述の制限を解決するシステムおよび方法に関する。
【０００５】
ラベルの最適化は、１組の制約に基づいて、ラベルの指定された位置決めを採点するアルゴリズムに従って提供される。ラベルの現在の位置決めが一定の制約によりよく適合するほど、チャートのスコアはよくなる。このアルゴリズムは、複数回、関数を呼び出すことによってスコアをできるだけ小さくしようと試み、呼び出される度に該関数が単一のラベルを再配置する。本発明の一実装では、手作業で配置されたラベルは、最適化プロセス時の考慮対象から除外される。
【０００６】
本発明のある態様では、最適化プロセスの関数は、チャートまたはグラフのラベルおよびアンカーに作用する目標関数すなわちスコア関数、および摂動関数に従って定義される。アンカーは、円グラフの特定のスライス、バブルチャートのバブル、または使用されるチャートに応じた他の要素など、関連するラベルを含むチャートの表示要素を指す。目標関数は、それによってチャートが採点され得る最適化の目標を定義する関数を指す。たとえば、目標関数は、ラベル重なりの最小化、アンカーのエッジからの距離の最小化、ラベル配置の最適化のための他の目標、およびその目標の可能な組合せに対応し得る。摂動関数は、チャート上のラベルの調整についての制限を定義する関数を指す。たとえば、摂動関数は、ラベルの再配置についての範囲制限、ラベルに関して行われ得る変更のタイプの制限されたサブセット、および他の制限を定義し得る。
【発明を実施するための最良の形態】
【０００７】
次に本発明について、その一部を形成しており、また図示することによって本発明を実施するための特定の例示的な実施形態を示す添付の図面を参照して、本明細書中で以下により完全に説明する。しかし、本発明は、多くの異なる形で実施されることができ、本明細書で述べる諸実施形態に限定されるものと解釈すべきでなく、こうした実施形態は、本開示が徹底的で完全なものとなり、また当業者に本発明の範囲を完全に伝えるものとなるように提供されている。本発明は、他にもあるが特に、方法または装置として実施され得る。したがって、本発明は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態、あるいはソフトウェアとハードウェアの側面を組み合わせた実施形態の形を取り得る。したがって、以下の詳細な説明は、限定的な意味で取るべきでない。
【０００８】
（例示的なオペレーティング環境）
図１を参照すると、本発明を実施するための例示的なシステムが、コンピューティングデバイス１００などのコンピューティングデバイスを含んでいる。コンピューティングデバイス１００は、クライアント、サーバ、モバイル装置、または他の任意のコンピューティングデバイスとして構成され得る。非常に基本的な構成では、コンピューティングデバイス１００は一般に、少なくとも１つの処理ユニット１０２およびシステムメモリ１０４を含む。厳密な構成、およびコンピューティングデバイスのタイプに応じて、システムメモリ１０４は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭ、フラッシュメモリなど）あるいはその２つの何らかの組合せであり得る。システムメモリ１０４は一般に、オペレーティングシステム１０５、１つまたは複数のアプリケーション１０６を含み、またプログラムデータ１０７を含み得る。ある実施形態では、アプリケーション１０６は、本発明の機能を実施するためのチャートラベル最適化アプリケーション１２０を含む。図１で、この基本的な構成は、破線１０８内のこうした構成要素によって示されている。
【０００９】
コンピューティングデバイス１００は、追加の特徴または機能を有し得る。たとえば、コンピューティングデバイス１００は、たとえば磁気ディスク、光ディスクまたはテープなど、追加のデータストレージ（取り外し式および／または固定式）をも含み得る。図１で、こうした追加のストレージは、取り外し式ストレージ１０９および固定式ストレージ１１０によって示されている。コンピュータ記憶媒体は、コンピュータ読出し可能命令、データ構造体、プログラムモジュール、または他のデータなどの情報を格納するための任意の方法または技術で実装された揮発性と不揮発性、取り外し式と固定式の媒体を含み得る。システムメモリ１０４、取り外し式ストレージ１０９および固定式ストレージ１１０はすべて、コンピュータ記憶媒体の例である。コンピュータ記憶媒体には、それだけに限らないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ：ｄｉｇｉｔａｌ  ｖｅｒｓａｔｉｌｅ  ｄｉｓｋ）または他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、または他の磁気ストレージ、あるいは所望の情報を格納するために使用することができ、またはコンピューティングデバイス１００からアクセスすることができる他の任意の媒体が含まれる。こうした任意のコンピュータ記憶媒体は、装置１００の一部であり得る。コンピューティングデバイス１００は、キーボード、マウス、ペン、音声入力デバイス、タッチ入力デバイスなどの入力デバイス１１２をも含み得る。表示装置、スピーカ、プリンタなどの出力デバイス１１４もまた含まれ得る。
【００１０】
コンピューティングデバイス１００は、装置がたとえばネットワークを介して他のコンピューティングデバイス１１８と通信することを可能にする通信接続１１６をも含む。通信接続１１６は、通信媒体の一例である。通信媒体は一般に、コンピュータ読取り可能命令、データ構造体、プログラムモジュール、または搬送波や他のトランスポート機構などの変調されたデータ信号内の他のデータによって実装されることができ、また任意の情報送達媒体を含む。用語「変調されたデータ信号」は、信号の情報を復号するなどのやり方でその特性の１つまたは複数が設定されまたは変更された信号を意味する。限定のためではなく、例を挙げると、通信媒体には、有線ネットワークや直接有線接続などの有線媒体、ならびに音響などの無線媒体、ＲＦ、赤外線、および他の無線媒体が含まれる。本明細書では、用語コンピュータ読取り可能媒体は、記憶媒体と通信媒体の両方を含む。
【００１１】
（自動ラベル配置を最適化するための例示的な実施形態）
本明細書では、用語「チャート」および「視覚データオブジェクト」は、円グラフ、バブルチャート、線グラフ、時系列図、折線グラフ、棒グラフ、写真、デジタル画像、および関連ラベルを含み得る他のオブジェクトなどの様々な視覚オブジェクトを表すために同義に用いられている。
【００１２】
本発明の実施形態は、チャート上のラベル位置を最適化するためのアルゴリズムの使用に関する。本発明は、１組の可能なレイアウトからラベルの最適なレイアウトを探索するための関数を使用する。レイアウト問題を探索として組み立てるために、本発明は、初期レイアウト、および２つの関数、すなわち評価基準に基づいてレイアウトの品質を査定する目標関数、および探索空間内に新しいレイアウトをもたらすように所与のレイアウトを操作する摂動関数を定義する。スコア関数と摂動関数の両方が、レイアウトに関する１組の制約によって定義される。こうした２つの関数が与えられると、最適なレイアウトを判断するために、探索が実施され得る。ある実施形態では、シミュレートされたアニーリング方法が、最適レイアウトを判断するためのランダム探索アルゴリズムとして使用される。
【００１３】
制約は、２つの組、すなわちハード制約およびソフト制約に分けられ得る。ハード制約は、任意の許容可能なレイアウトについて必要とされる特性からなり、したがって、ハード制約は、可能なレイアウトの空間を制限する。それとは異なり、ソフト制約は、必須ではないが、最終的なレイアウトに望まれる特性からなる。ハード制約は一般に、ハード制約を満たすレイアウトだけを生成するように設計された摂動関数を介して課される。スコア関数は、所与のレイアウトがソフト制約をどれほどよく達成しているかをチェックする。
【００１４】
アルゴリズムを用いて、１組のデータが、チャート領域内のラベル位置を最適化しながらチャートにラベルを自動的に投入するために使用され得る。
【００１５】
図２に、本発明によるラベル位置最適化が行われる前および後の、自動ラベル付けされた円グラフの例示的なビューを示す。
【００１６】
ビュー２１０は、円グラフ内に含まれるデータ点の数のせいで、円グラフ上のラベルが重なり合っていることを示している。重なり合うテキストによって、すべてのラベル、および円グラフの諸要素とのその関連付けを視覚的に見分けることが難しくなる。
【００１７】
ビュー２２０は、本発明の最適化アルゴリズムを実行することによってラベル付けが改善された円グラフをもたらしている。円グラフの読みやすさは、チャート空間内のラベルの位置を最適化することによって大幅に改善されている。このアルゴリズムによって、一部のラベルは、それが関連するアンカー（スライス）から離され、他のラベルは、より近くに移動され、あるいはさらにそのアンカーの中央に置かれ、またはある程度その中央に置かれている。他のラベルは、ラベルをその関連アンカーに視覚的にリンクするために引出し線が追加されている。ビュー２２０は、このアルゴリズムが、チャートのラベルの最適レイアウトを提供するための様々な方法を使用することを示している。
【００１８】
図３に、本発明によるラベル位置最適化が行われる前および後の、自動ラベル付けされたバブルチャートの例示的なビューを示す。
【００１９】
ビュー３１０は、バブルチャート上のラベルが、その関連アンカーの判断が不可能であり得るように配置され得ることを示している。さらに、ラベルのテキストは、バブルのエッジに重なり合うテキストを含み、チャート内のバブルの表示を最適化するように配置されないことがある。
【００２０】
ビュー３２０は、本発明の最適化アルゴリズムを実行するとによってラベル付けが改善されたバブルチャートである。バブルチャートの読みやすさは、チャート空間内のラベル位置を最適化することによって大幅に改善されている。このアルゴリズムによって、一部のラベルはそれが関連するアンカー（バブル）から離され、他のラベルは、より近くに移動され、あるいはさらにそのアンカーの中央に置かれ、またはある程度その中央に置かれている。他のラベルは、関連するアンカーからある距離だけそれを移動するが、ラベルをその関連アンカーに視覚的にリンクするために引出し線が追加されている。ビュー３２０は、このアルゴリズムが、円グラフについて使用される様々な方法に類似した、バブルチャートのラベルの最適レイアウトを提供するための様々な方法を使用することを示している。
【００２１】
図４に、本発明によるラベル位置最適化が行われる前および後の、自動ラベル付けされた時系列チャートの例示的なビューを示す。
【００２２】
ビュー４１０は、提供された空間内に含まれるデータ点の数のせいで、時系列チャート上のラベルが重なり合っていることを示している。さらに、本発明の恩恵を得ない自動ラベル付けアルゴリズムは、時系列上のデータ点からのテキストのスペーシングを変更できるほど知的ではない。
【００２３】
ビュー４２０は、本発明の最適化アルゴリズムを実行することによってラベル付けが改善された時系列チャートである。時系列チャートの読みやすさは、チャート空間内のラベル位置を最適化することによって大幅に改善されている。このアルゴリズムは、チャート空間の使用を最適化するために、チャート空間全体を通してテキストフォーマットを変更し、ラベルを移動している。ビュー４２０は、このアルゴリズムが、上記で示した円グラフおよびバブルチャートの例について使用される様々な方法に類似した、時系列チャートのラベルの最適レイアウトを提供するための様々な方法を使用することを示している。
【００２４】
図２〜４に示す実施形態以外の実施形態が、本発明に従って提供され得る。たとえば、本発明は、折線グラフ上、写真内、または他の視覚データオブジェクトと併せたラベルの位置を最適化するために使用され得る。
【００２５】
図５に、本発明による、チャート生成およびラベル位置最適化を実施するための例示的なチャート作成システム５００を示す。システム５００内には、ドキュメント５０４へのアクセスを提供するアプリケーションプログラム５０２、コンピュータモニタ画面５０８上にドキュメント５０４をレンダリングするためのグラフィックモジュール５０６が含まれる。
【００２６】
本明細書では、ドキュメント５０４は、テキストおよびグラフィックなどのユーザ読取り可能情報を含むコンピュータ読取り可能ファイルである。ドキュメント５０４は、アプリケーションプログラム５０２のユーザインターフェースを介してユーザによって表示され、編集され得る。ドキュメントの例示的なタイプには、それだけに限らないが、スプレッドシート、プレゼンテーション、または従来のテキストドキュメントが含まれる。したがって、ドキュメントのタイプに応じて、アプリケーションプログラム５０２は、それだけに限らないが、たとえば、ＭＩＣＲＯＳＯＦＴ「ＷＯＲＤ」（登録商標）、「ＰＯＷＥＲＰＯＩＮＴ」（登録商標）、「ＥＸＣＥＬ」（登録商標）または他のアプリケーションプログラムであり得る。たとえば、画面５０８上に示すように、ドキュメント５０４は、常にではないがしばしば「ＰＯＷＥＲＰＯＩＮＴ」（登録商標）に関連する「プレゼンテーション」であり得る。
【００２７】
本説明に特に関係があるのは、プレゼンテーション内のチャート５１０である。図１の特定の実装内で示されるチャート５１０は、カラムチャートである。他の実装によれば、チャート５１０は、カラムチャートに限らず、他の任意のタイプのチャート、たとえば、それだけに限らないが、円グラフ、線グラフ、分布図、写真、または他の視覚データオブジェクトなどであり得る。チャート５１０内の様々なデータは元来、ドキュメント５０４によって指定されている。ドキュメント５０４は、チャートオブジェクト５１２と呼ばれるチャート定義でチャート５１０を指定する。
【００２８】
チャートオブジェクト５１２は、チャート要素に関して、チャート５１０を定義する。一般にチャート要素は、チャートの側面を表すデータ単位である。一般にチャート要素は、チャートが伝える情報、またはチャートのタイプに関するチャートの側面を表す。例示的なチャート要素には、（たとえばバーチャートの）バー、チャート軸、チャートの凡例、チャートタイトル、チャートラベル、要素カラー、テキストフォント、要素位置、データソースなどが含まれる。チャート要素は、ラベルに関するアンカーと称され得る。チャートオブジェクト５１２のある実装は、１組の拡張可能マークアップ言語（ＸＭＬ：ｅｘｔｅｎｓｉｂｌｅ  ｍａｒｋｕｐ  ｌａｎｇｕａｇｅ）である。例示するため、チャートオブジェクト５１２からの例示的なＸＭＬを以下に示す。
【００２９】
【表１−１】
2006114013.tif 000003
【００３０】
【表１−２】
2006114013.tif 000004
【００３１】
【表１−３】
2006114013.tif 000005
【００３２】
【表１−４】
2006114013.tif 000006
【００３３】
ドキュメント５０４は一般に、それだけに限らないが、テキスト、およびフォーマット設定情報を含む他のドキュメントデータ５１４をも含む。ある実装によれば、アプリケーションプログラム５０２が起動され、ドキュメント５０４が開かれると、チャートオブジェクト５１２は、レンダリングのために、グラフィクモジュール５０６のグラフィックインターフェース５１６に渡される。
【００３４】
グラフィックインターフェース５１６は、どのタイプのグラフィックがチャートオブジェクト５１２によって表現されているか判断する。グラフィックインターフェース５１６によって取り扱われるグラフィックのタイプには、それだけに限らないが、ダイアグラム、チャートまたは任意の形状が含まれる。チャートオブジェクト５１２は、それがチャートを定義することを示す識別子を含む。チャート識別子に基づいて、グラフィックインターフェース５１６は、チャートオブジェクト５１２がチャートを定義すると判断し、それをチャート作成モジュール５１８に送信する。
【００３５】
チャート作成モジュール１１８は、グラフィックモジュール５０６が画面５０８にチャート５１０をレンダリングするために使用する形にチャートオブジェクト５１２を変換する変換エンジン５２０を含む。具体的には、変換エンジン５２０は、チャートオブジェクト５１２を形状ベースのチャート定義５２２に変換する。その名前が示唆するように、形状ベースチャート定義５２２は、チャート要素ではなく、形状に関してチャートを定義する。形状を使用すると、グラフィックと対話するための機構を可能にすることによって、チャートレンダリングプロセス、チャートの外観、およびチャート操作が向上し得る。
【００３６】
変換プロセスでは、変換エンジン５２０は、複数の操作を実施する。たとえば、変換エンジン５２０は、チャートオブジェクト５１２内で参照されるデータソースからチャート５１０を構成するデータ（数値データなど）を取り出す。データソースは、ドキュメント５０４自体、またはそれだけに限らないが、別のドキュメント、データベース、ファイル、インターネット、キューなどの何らかの他のソースであり得る。変換エンジン５２０は、データに加えて、データがどのようにフォーマットされるかを表す数値フォーマット設定情報を取り出し得る。数値フォーマット設定情報は、それだけに限らないが、通貨記号、小数点の数、パーセンテージまたは分数フォーマット、あるいは日付および時間フォーマットが含まれる。
【００３７】
変換エンジン５２０は、チャート要素を、線、長方形、円、三角形などの形状に変換する。形状は、チャート要素の視覚的外観を単純に表現するデータ単位であり、基礎となる数値チャートデータに結び付いておらず、またはそれに依存しない。したがって、たとえば、チャートオブジェクト５１２内のバーは形状ベースチャート定義５２２内の四角形に変換され、チャート軸は線に変換されるなどである。
【００３８】
さらに、変換エンジン５２０は、ユーザによる関連形状の操作を容易にするために、選択された関連形状をグループ化する。グラフィックインターフェース５１６は、ユーザが関連形状のグループと対話できるようにする関数を提供する。変換エンジン５２０は、それだけに限らないが、関連データラベルおよび関連データシリーズなどの関連チャート要素をグループ化することによってこうした関数を利用する。データを取り出し、チャート要素を形状に変換し、また関連形状をグループ化した後に、変換エンジン５２０は、形状ベースチャート定義５２２を生成する。
【００３９】
形状ベースチャート定義５２２の一実装は、ＸＭＬコードで構成される。説明するために、例示的な形状ベースチャート定義５２２からのＸＭＬコードを以下に示す。
【００４０】
【表２−１】
2006114013.tif 000007
【００４１】
【表２−２】
2006114013.tif 000008
【００４２】
【表２−３】
2006114013.tif 000009
【００４３】
【表２−４】
2006114013.tif 000010
【００４４】
【表２−５】
2006114013.tif 000011
【００４５】
【表２−６】
2006114013.tif 000012
【００４６】
【表２−７】
2006114013.tif 000013
【００４７】
【表２−８】
2006114013.tif 000014
【００４８】
グラフィックインターフェース５１６は、形状ベースチャート定義５２２を受信し、形状ベースチャート定義によって指定された１組の形状として、チャート５１０を画面５０８上にレンダリングする。グラフィックインターフェース５１６は一般に、オペレーティングシステムまたは表示コントローラ関数への呼出しを行うことによってレンダリングを実施する。たとえば、ＷＩＮＤＯＷＳ（登録商標）オペレーティングシステム内で、グラフィックインターフェース５１６は、グラフィック表示インターフェース（ＧＤＩ＋）への呼出しを行い得る。
【００４９】
図示するように、グラフィックモジュール５０６は、１組のグラフィックサービス５２４を含む。グラフィックサービス５２４は、チャート５１０を操作するためにアプリケーションプログラムによってアクセス可能なサービスを含む。グラフィックサービス５２４は、サービスにアクセスするための１つまたは複数のアプリケーションプログラミングインターフェース（ＡＰＩ：ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｉｎｔｅｒｆａｃｅ）を提供する。
【００５０】
グラフィックモジュール５０６が形状をレンダリングするので、グラフィックサービス５２４は、チャート５１０を操作するための高いレベルの関数を提供することができる。グラフィックサービス５２４は、たとえば、チャート内の形状に対してベクトルグラフィック機能を実施する。例示すると、四角形は、それを新しい位置で再描画するために複数の低レベル関数を呼び出すのではなく、形状を移動するグラフィックサービス５２４の単一の関数を呼び出すことによって容易に移動され得る。さらに、グラフィックモジュール５０６は、形状の操作／編集、および外観がアプリケーションプログラム間で一貫性があるように、複数のアプリケーションプログラムに共通している。したがって、グラフィックモジュール５０６は、アプリケーションプログラム５０２のタイプに関係なく、チャート５１０内の形状を編集するためのグラフィックユーザインターフェースを提示し得る。
【００５１】
ラベル最適化５２６は、システム５００内の本発明を対象とするコードである。ラベル最適化５２６は、形状ベースチャート定義５２２を受信し、最適化アルゴリズムに従ってラベル位置を最適化する。上述したように、形状ベースチャート定義５２２によって、ラベルを、ラベルの再描画を必要とする他の低レベル関数によってではなく、その形状によってそれが定義されているので、容易に移動することができる。ラベル最適化５２６は、ラベルの位置決めを最適化するために、チャート５１０が画面５０８上にレンダリングされる前または後に使用され得る。たとえば、最適化アルゴリズムによるラベルの位置決めは、レンダリングされるあらゆるチャートについて自動的に行われ得る。それとは異なり、ラベルの最適化は、ユーザ選択に従って提供されることができ、ラベルが最適化されることをユーザが肯定的に選択する。ある実施形態では、ユーザによって手作業で配置されるラベルは、最適化プロセス時に無視される。
【００５２】
用語モジュールは、１つまたは複数の指定された機能を実施するように動作可能であるコンポーネントを表すために一般的な意味で使用される。モジュールは、様々なやり方および形で実装され得る。たとえば、モジュールは、速度、コスト、サイズなどの要因に応じて、ハードウェア、ソフトウェア、ファームウェア、あるいはハードウェア、ソフトウェアおよび／またはファームウェアの様々な組合せで、またはそれとして実装され得る。限定ではなく、たとえば、ある実装では、システム１００内の各モジュールは、コンピュータ読取り可能媒体内に格納されており、また図１に関して上述したコンピューティングシステムなどのコンピューティングシステム上で実行されるダイナミックリンクライブラリ（ＤＬＬ：ｄｙｎａｍｉｃ  ｌｉｎｋ  ｌｉｂｒａｒｙ）などのソフトウェアを含む。
【００５３】
図６に、本発明のよる、ラベルの最適なレイアウトに対応する視覚データオブジェクトのレイアウトを判断するための例示的な疑似コードを示す。
【００５４】
例示的なアルゴリズム６００の実装は、複数の異なる関数の仕様を必要とする。ＩｎｉｔｉａｌｉｚｅＬａｙｏｕｔ（）関数は、それぞれの視覚要素について初期配置を定義し、それによって、探索のための開始点を提供する。ＰｅｒｔｕｒｂＬａｙｏｕｔ（）関数は、上述した摂動関数に対応し、所与のレイアウトを新しいレイアウトに変更するための方法を提供する。ＲｅｖｅｒｔＬａｙｏｕｔ（）関数は、ＰｅｒｔｕｒｂＬａｙｏｕｔ（）関数の動作を、新しいレイアウトから前のレイアウトに戻るように反転させる。Ｒａｎｄｏｍ（）関数は、０．０と１．０の間の数を返す。最後に、上述した目標関数に対応するＳｃｏｒｅＬａｙｏｕｔ（）関数は、現レイアウトが最適なものにどれほど近似しているかを計算する。ある実施形態では、終了条件は、使用可能なレイアウト、最適レイアウトにレイアウトが近似すること、および他の要因を実現するための時間制限に従って変化し得る。別の実施形態では、スコアは、正のものと定義され、スコアが下がるほど、レイアウトはよくなる。したがって、目標は、使用される制約に従ってスコアを最小化することである。使用されるレイアウトにとって許容できるスコアは、アルゴリズムの終了条件に依存する。
【００５５】
疑似コード内に示すように、アルゴリズムは、探索空間内のすべての良い動きを受け付け、また温度Ｔの指数関数である確率で、悪い動きをも同様に受け付ける。アルゴリズムが進行するにつれて、Ｔは、強固になり(annealed)（または減少され）、悪い動きを受け付ける確率の減少がもたらされる。このようにして悪い動きを受け付けることによって、アルゴリズムは、スコア関数におけるローカル最小値(minima)から脱出することができる。
【００５６】
ラベルの最適レイアウトをもたらすために定義される制約には、アンカーからの距離の最小化、ラベルの重なりの最小化、要素との重なりの最小化、フォント制約、方位の制約、およびラベルがどのように操作され得るかに影響を及ぼす他の制限が含まれ得る。任意の数の制約が、表示可能な空間でその位置を最適化するようにラベルを操作するためのアルゴリズムに与えられ得る。
【００５７】
上記の明細、例およびデータは、本発明の構成の製造および使用についての完全な説明を提供している。本発明の精神および範囲から逸脱せずに、本発明の多くの実施形態が作られ得るので、本発明は、添付の特許請求の範囲にある。
【図面の簡単な説明】
【００５８】
【図１】本発明の例示的な一実施形態で使用され得る例示的なコンピューティングデバイスを示す図である。
【図２】本発明によるラベル位置最適化が行われる前および後の、自動ラベル付けされた円グラフの例示的なビューを示す図である。
【図３】本発明によるラベル位置最適化が行われる前および後の、自動ラベル付けされたバブルチャートの例示的なビューを示す図である。
【図４】本発明によるラベル位置最適化が行われる前および後の、自動ラベル付けされた時系列チャートの例示的なビューを示す図である。
【図５】本発明による、チャート生成およびラベル位置最適化を実施するための例示的なチャート作成システム５００を示す図である。
【図６】本発明による、ラベルの最適なレイアウトに対応する視覚データオブジェクトのレイアウトを判断するため例示的な疑似コードを示す図である。
【符号の説明】
【００５９】
１００  コンピューティングデバイス
１０２  処理ユニット
１０４  システムメモリ
１０５  オペレーティングシステム
１０６  アプリケーション
１０７  プログラムデータ
１０９  取り外し式ストレージ
１１０  固定式ストレージ
１１２  入力デバイス
１１４  出力デバイス
１１６  通信接続
１１８  他のコンピューティングデバイス
１２０  チャートラベル最適化
５０２  アプリケーションプログラム
５０４  ドキュメント
５０６  グラフィックモジュール
５１２  チャートオブジェクト
５１４  他のドキュメントデータ
５１６  グラフィックインターフェース
５１８  チャート作成モジュール
５２０  変換エンジン
５２２  形状ベースチャート定義
５２４  グラフィックサービス
５２６  ラベル最適化
【図１】
2006114013.tif 000015
【図２】
2006114013.tif 000016
【図３】
2006114013.tif 000017
【図４】
2006114013.tif 000018
【図５】
2006114013.tif 000019
【図６】
2006114013.tif 000020
【外国語明細書】
2006114013000001.pdf