Loading article…
自動ラベル配置（テキスト配置または名前配置とも呼ばれる）とは、地図や図表上にラベルを自動的に配置するコンピュータ手法のことである。これは、ラベルのタイポグラフィデザインにも関連する。
地理地図に描かれる典型的な特徴は、線状の特徴（道路など）、面状の特徴（国、区画、森林、湖など）、点状の特徴（村、都市など）です。地図上の特徴を地理的に正確に描写することに加え、読者がどの名前がどの特徴を表しているかを即座に理解できるように、これらの特徴を識別する名前を配置することが非常に重要です。
テキストの自動配置は、地図作成やGIS（地理情報システム）において最も難しく、複雑で、時間のかかる問題の一つです。チャートやグラフなどの他の種類のコンピュータ生成グラフィックでも、ラベルの適切な配置が必要です。言うまでもなく、エンジニアリング図面や、スプレッドシート（ Microsoft Excelなど）や計算ソフトウェア（Mathematicaなど）といった、これらの図面やチャートを作成する専門的なプログラムでも同様です。
ラベルを安易に配置すると、ラベルが過度に重なり合い、地図が読みにくく、場合によっては読み取れなくなってしまう。そのため、GISでは各ラベルの配置をいくつか用意し、多くの場合、ラベルのサイズ変更、回転、あるいは削除（非表示）のオプションも提供する必要がある。そして、重なりが最小限に抑えられ、かつ他の望ましい特性も満たす配置を選択する。ごく単純な設定を除けば、この問題はNP困難である。
ルールベースのアルゴリズムは、経験豊富な人間の地図製作者を模倣しようとします。何世紀にもわたり、地図製作者は地図作成とラベル配置の技術を発展させてきました。たとえば、経験豊富な地図製作者は、長い道路の場合は道路名を一度だけ配置するのではなく、複数回繰り返します。また、海岸に非常に近い地点で表されたオーシャンシティの場合、地図製作者はそれが沿岸の町であることを強調するために、陸地に「オーシャンシティ」というラベルを配置します。[ 1 ]
地図製作者は、1962 年にスイスの地図製作者エドゥアルト・イムホフが列挙したような、受け入れられた慣習や規則に基づいて作業します。[ 2 ]例えば、ニューヨーク市、ウィーン、ベルリン、パリ、東京などは、優先度の高いラベルであるため、国の地図に表示されなければなりません。これらが配置されると、地図製作者は次に重要な種類のラベル、例えば主要道路、河川、その他の大都市などを配置します。各段階で、(1) テキストが読者がそれを特徴と容易に関連付けられるように配置されていること、(2) ラベルが地図上に既に配置されているラベルと重なっていないことを確認します。
しかし、特定のラベル配置問題が数学的最適化問題として定式化できる場合、ルールベースのアルゴリズムを使用するよりも、数学を使用して問題を解決する方が通常は優れています。[ 3 ]
最も単純な貪欲アルゴリズムは、連続するラベルを、ラベルの重なりが最小限になるような位置にマップ上に配置します。非常に単純な問題であっても結果は完璧ではありませんが、処理速度は非常に高速です。
やや複雑なアルゴリズムでは、局所最適化を利用して配置評価関数の局所最適解に到達します。各反復処理で単一のラベルの配置位置を別の位置に移動し、結果が改善される場合はその移動を維持します。ラベル密度が高すぎないマップでは、このアルゴリズムは十分に機能します。さらに複雑なバリエーションでは、2つ以上のラベルを同時に移動しようとします。アルゴリズムは、何らかの局所最適解に到達すると終了します。
単純なアルゴリズムであるシミュレーテッドアニーリングは、比較的良好なパフォーマンスで良い結果をもたらします。局所最適化のように機能しますが、結果が悪化する場合でも変更を保持する可能性があります。そのような変更を保持する確率は、 どこ評価関数の変化であり、は温度です。温度はアニーリングスケジュールに従って徐々に下げられます。温度が高いときは、シミュレーテッドアニーリングはラベルの配置をほぼランダムに変更し、局所最適解から抜け出すことができます。その後、うまくいけば非常に良い局所最適解が見つかると、局所最適化と同様の動作をします。シミュレーテッドアニーリングソリューションを開発する際の主な課題は、適切な評価関数と適切なアニーリングスケジュールを選択することです。一般的に、冷却が速すぎるとソリューションが劣化し、冷却が遅すぎるとパフォーマンスが低下しますが、スケジュールは通常、1つ以上のパラメータを持つかなり複雑なアルゴリズムです。
直接探索アルゴリズムのもう1つのクラスは、遺伝的アルゴリズムなどのさまざまな進化アルゴリズムです。
実際の地図で重要な単純な最適化の 1 つは、ラベルのセットを独立して解決できるより小さなセットに分割することです。2 つのラベルは、可能な配置のいずれかで重なる可能性がある場合、競合関係にあります。この関係の推移閉包により、ラベルのセットは、場合によってははるかに小さなセットに分割されます。均一かつ密にラベル付けされた地図では、通常、単一のセットにラベルの大部分が含まれますが、ラベル付けが均一でない地図では、非常に大きなパフォーマンス上の利点をもたらす可能性があります。たとえば、世界地図にラベルを付ける場合、アメリカ大陸はユーラシア大陸とは独立してラベル付けされます。
地図のラベル付け問題が、残りの各ラベルが配置可能な位置が2つしかない状況に還元できる場合、2充足可能性のインスタンスを使用して、競合する配置のペアを回避する配置を見つけることで効率的に解決できます。より複雑なタイプの問題に対するいくつかの正確なラベル配置アルゴリズムと近似ラベル配置アルゴリズムは、この原理に基づいています。[ 4 ]
自動ラベル配置アルゴリズムは、候補ラベルの集合から最大の非連結集合を見つけるためのアルゴリズムをどれでも使用できます。また、さまざまなグラフ解法や整数計画法など、他のアルゴリズムも使用できます。
地図ラベル配置問題のいくつかのバージョンは、複数の選択肢を持つ整数計画問題（MCIP）として定式化できます。その目的関数は、個々のラベルを最適な配置位置から移動させて重なりを避けるための数値ペナルティの合計を最小化することです。問題の制約は、各ラベルを地図上の有限個の許容位置のいずれかに配置すること（または、他のラベルを配置できるように地図から削除すること）です。
このMCIPのほぼ最適な解は、ラグランジュ緩和法を用いて最適化問題の双対定式化を解くことで、通常、実用的な計算時間で見つけることができます。[ 5 ]
地図ラベル問題に対する最初の商業的解決策は、MCIP問題として定式化され、ラグランジュ緩和法によって解決され、石油産業の基本地図上に油井と地震探査発破点のラベルを配置することであった。[ 6 ]
最初の解が発表されて以来、このMCIPを他の地図作成用途で解決するために、多くの数学的最適化アルゴリズムが提案され、使用されてきました。
