ラベル配置装置
【課題】ユーザからの見栄え、認識のしやすさ、使いやすさを考慮した複数ラベル配置をすることができる複数ラベル配置装置を提供する。
【解決手段】複数の地点それぞれの地図上における位置情報及び地点の属性を示すラベルのデータを地点ごとに格納する格納手段１０６と、格納手段に格納された位置情報及びラベルに基づいて、地図上の地点の位置にラベルを地点ごとに配置する配置手段１０５と、配置手段によって配置されたそれぞれのラベルに対して、複数ラベル配置のための所定の条件を満たすか否かを判断する判断手段１０４と、判断手段によって所定の条件を満たさないと判断された場合、配置されたラベルの配置調整を行う調整手段１０４とを備える。
【解決手段】複数の地点それぞれの地図上における位置情報及び地点の属性を示すラベルのデータを地点ごとに格納する格納手段１０６と、格納手段に格納された位置情報及びラベルに基づいて、地図上の地点の位置にラベルを地点ごとに配置する配置手段１０５と、配置手段によって配置されたそれぞれのラベルに対して、複数ラベル配置のための所定の条件を満たすか否かを判断する判断手段１０４と、判断手段によって所定の条件を満たさないと判断された場合、配置されたラベルの配置調整を行う調整手段１０４とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地点の属性を示すラベルを地図上に配置するラベル配置装置に関する。
【背景技術】
【０００２】
一般的な地図サービスでは、ＰＯＩ（Point of Interest）について点＋地名などのラベルで提示するのが基本である。それ以上の内容は、ユーザがクリックしてポップアップによって提示するなどで個別の提示が行われる。大量のＰＯＩが対象の場合は非常に煩雑である。また、原理的に地図を最初に見た段階では、テキスト情報などは含まれていないので、内容を把握するためにはいくつかのステップによる検索やブラウズ操作が必要である。これに対して、ＧＩＳ（Geographic Information System）などでは、定量化された属性を点分布で提示したり、集計された代表点でのシンボル提示をしたり、それを補完したサーフェイスによる等高線で提示したり、いろいろな方法がある。
【０００３】
表示する内容は様々であるが、ＧＩＳなどは、地物あるいはエリアに割り当てられた定量化された値を提示するための方法である。一度に複数の属性の分布を提示することもできるが、数個の分布を表示しただけでも解読が難しい複雑な図になってしまう傾向がある。一方、各属性で、際立った場所にだけラベルを配置するようにすれば、この問題に対処できる。ところが、地名のように、基本的に、同じラベルが１地点にしか現れないような場合は単純な方法でよいが、上記の属性のように多数存在し、かつ、必ずしも１箇所に集約表示できないような場合（ある程度分布が散らばっている場合）には、ラベルの数が多くなりすぎる傾向になり、対処が必要である。つまり表示すべき属性が多いので代表点だけを提示したいが、１つの代表点だけではその属性の分布を表しきれないような場合には従来にない特別な配慮が必要となる。
【０００４】
例えば、「東京」、「神奈川」などの属性（ラベル）は代表的な１つの点で表現してもよいが、「リアス式海岸」、「日の出スポット」、「景勝地」、「観光船」、「松の群生地」などのラベルは、分布が散らばっているため１箇所で現せず、また無数に属性が存在するため、同時に表わそうとすると非常に煩雑かつ解読の難しい地図になってしまう。また、分布が重なるため一方のラベルが他方のラベルと競合してしまう可能性が高い。これらを、ユーザが判読しやすく、かつ、実際の分布の情報を損なわずに伝える調整手段が必要である。なお、地名のように単一の属性が１箇所にしか現れないような場合には、一例として下記の特許文献１に開示された手法が用いられる。
【０００５】
上述したような課題を解決するために、エリアに対応したラベルを何らかの方法で要約表示させることで、地図上で事前にエリアごとのおおまかなラベルを把握できるようにする方法が考えられる。これには以下のような方法がある。１つ目の方法は、あらかじめ決められた属性（ラベル）ごとの地図を提示する方法である。２つ目の方法は、地図上に代表的なラベルを提示する方法である。３つ目の方法は、地図上でまずエリアを明示的に分割し、各々のエリアにラベルを提示する方法である。
【０００６】
１つ目の方法は、属性ごとにその分布を提示するのみであるが、内容がテキストの場合、すべての属性を表示させ内容を把握させることは不可能である。ラベルを限定して地図上に分布を表示させることもできるが、これは既存の等高線描画などを用いればよい。複数の地図表示を切り替えることになり操作が煩雑になる。２つ目の方法は、１つ目の方法で得られた各属性（テキスト）の等高線の最高点にラベルを配置するなどで比較的容易に実現できる。１つ目の方法に比べ一画面で把握できる点で優れている。ただし、ラベル同士が重なり合う場合は視認性が悪くなる恐れがある。
【０００７】
３つ目の方法は、地図において、あらかじめエリアを分割してラベルを配置するものである。これによりラベルの視認性は向上する。３つ目の方法では、散在する点（面やエリアの代表点を含む）データ（例えば、地物、観測点などのデータ）の分布に基づいたエリア分割をする際、点データの地図上での近接度（距離）と点データの属性の近接度（例えば、似た種類の店舗、似た植生、似た世代分布、似た口コミ、ガイド文章など）を元にクラスタリング（グルーピング）する（特許文献２を参照）。
【０００８】
特許文献２に開示された技術によれば、双方（地図上での近接度と属性の近接度）を元にしたクラスタリングにより、内容に基づいた均質な内容であるとともに、地図上である程度まとまった（目で見てわかりやすい）エリアが得られる。この技術は地図上で簡単な要約マップを作るアプリケーションに応用できる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開平９−２３７０３４号公報（要約）
【特許文献２】特開２００８−２２４９９３号公報（要約）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、２つ目、３つ目の方法において共に課題がある。すなわち、扱うデータなどによっては、ラベル配置をする際にラベルの重なりを必ず回避できるとは限らず、最適なラベル配置とならないことがある。
【００１１】
本発明は、上記の問題点に鑑み、ユーザからの見栄え、認識のしやすさ、使いやすさを考慮したラベル配置をすることができるラベル配置装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、本発明によれば、複数の地点それぞれの地図上における位置情報及び前記地点の属性を示すラベルのデータを前記地点ごとに格納する格納手段と、前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、前記地図上の前記地点の位置に前記ラベルを前記地点ごとに配置する配置手段と、前記配置手段によって配置されたそれぞれのラベルに対して、複数ラベル配置のための所定の条件を満たすか否かを判断する判断手段と、前記判断手段によって前記所定の条件を満たさないと判断された場合、配置された前記ラベルの配置調整を行う調整手段とを、備えるラベル配置装置が提供される。この構成により、ユーザからの見栄え、認識のしやすさ、使いやすさを考慮したラベル配置をすることができる。なお、ここでの調整手段は、すべてのラベルが所定の条件を満たすまでラベルの配置調整をしてもよく、ある程度のところでラベルの配置調整を止めてもよい。また、ここでのラベルのデータは、テキストデータでもよく、記号などを示すデータでもよい。
【００１３】
また、本発明のラベル配置装置において、前記調整手段が、ラベルの削除、統合、移動のうちのいずれか１つを行うことによって前記ラベルの配置調整を行うことは、本発明の好ましい態様である。この構成により、地図上での視認性を向上させることができる。
【００１４】
また、本発明のラベル配置装置において、前記調整手段が、前記地図上での前記ラベルの所定の視認性が確保できる範囲内で、前記配置手段によって配置されたそれぞれのラベルの前記地図上での配置位置の正確度を最適化させるように、前記ラベルの配置調整を行うことは、本発明の好ましい態様である。この構成により、視認性及び忠実性の双方を反映させることができる。
【００１５】
また、本発明のラベル配置装置において、前記配置手段が、前記ラベルを前記地点ごとに配置しない場合、前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、所定のクラスタリング処理を行い、クラスタごとに前記ラベルを配置し、前記調整手段が、前記配置手段によって配置されたそれぞれのクラスタの前記地図上での所定のまとまりの良さが確保できる範囲内で、前記地図上での前記クラスタの内容の正確度が最適化されるように、前記クラスタの配置調整を行うことは、本発明の好ましい態様である。この構成により、視認性及び忠実性の双方を反映させることができる。
【００１６】
また、本発明のラベル配置装置において、前記調整手段が、前記最適化のためのパラメータを算出する際、ラベル配置又はクラスタの見た目の複雑さを示す所定の情報の初期値をもって前記パラメータを推定することは、本発明の好ましい態様である。この構成により、複数のパラメータ算出の処理を減らすことができる。
【００１７】
また、本発明のラベル配置装置において、前記調整手段が、前記配置手段によって配置されたそれぞれのラベルの前記地図上での配置位置の所定の正確度が確保できる範囲内で、前記地図上での前記ラベルの視認性を最適化させるように、前記ラベルの配置調整を行うことは、本発明の好ましい態様である。この構成により、正確性の乖離をある程度抑え、地理的に関連の深い属性グループを抽出できる。
【００１８】
また、本発明のラベル配置装置において、前記配置手段が、前記ラベルを前記地点ごとに配置しない場合、前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、所定のクラスタリング処理を行い、クラスタごとに前記ラベルを配置し、前記調整手段が、前記地図上での前記クラスタの内容の所定の正確度が確保できる範囲内で、前記配置手段によって配置されたそれぞれのクラスタの前記地図上でのまとまりの良さを最適化させるように、前記クラスタの配置調整を行うことは、本発明の好ましい態様である。この構成により、正確性の乖離をある程度抑え、地理的に関連の深い属性グループを抽出できる。
【発明の効果】
【００１９】
本発明のラベル配置装置は、上記構成を有し、ユーザからの見栄え、認識のしやすさ、使いやすさを考慮したラベル配置をすることができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態に係るラベル配置装置の構成の一例を示す構成図である。
【図２】本発明の実施の形態における複数の属性をいくつかの属性にまとめることについて説明するための図である。
【図３】本発明の実施の形態における個別の属性分布から別々にラベル位置を求める方法について説明するための図である。
【図４】本発明の実施の形態における各属性について空間的な補完を用いて構成される場について説明するための図である。
【図５】本発明の実施の形態におけるエリアを介したラベル位置の決定方法について説明するための図である。
【図６】本発明の実施の形態におけるエリア分割を行ったあとメンバーの属性からラベルを得る方法について説明するための図である。
【図７ａ】本発明の実施の形態における地理クラスタリングの様子を示す図である。
【図７ｂ】本発明の実施の形態における意味クラスタリングの様子を示す図である。
【図７ｃ】本発明の実施の形態における地理意味クラスタリングの様子を示す図である。
【図８ａ】本発明の実施の形態におけるラベルＡ、Ｂにおいて異種のラベル間の最近隣ラベルの関係を示す図である。
【図８ｂ】本発明の実施の形態におけるラベルＡ、Ｂにおいて同種のラベル間の最近隣ラベルの関係を示す図である。
【図９ａ】本発明の実施の形態におけるラベルの再配置の一例について説明するための図である。
【図９ｂ】本発明の実施の形態におけるラベルの再配置の一例について説明するための他の図である。
【図１０】本発明の実施の形態におけるパラメータ最適化手法を説明するためのドロネー図を示す図である。
【図１１】本発明の実施の形態におけるクラスタの良さと忠実度とのトレードオフの概念を示す図である。
【図１２】本発明の実施の形態におけるパラメータ最適化の例について説明するための図である。
【図１３】本発明の実施の形態におけるパラメータ最適化の処理フローの一例を示すフローチャートである。
【発明を実施するための形態】
【００２１】
本発明の実施の形態に係るラベル配置装置の構成の一例について図１を用いて説明する。ラベル配置装置は、地図描画部１０１、地図描画エンジン１０２、地図ＤＢ（Data Base）１０３、ラベル配置部１０４、ラベル抽出部１０５、ＰＯＩ ＤＢ１０６、クラスタリング機能部１０７、エリア抽出部１０８から構成されている。なお、クラスタリング機能部１０７及びエリア抽出部１０８は後述するクラスタリング処理を行う場合には必要な構成要素である。地図描画部１０１は、地図描画エンジン１０２によって地図ＤＢ１０３から検索された地図情報を不図示の表示部（ディスプレイなど）に表示させるものである。また、地図描画部１０１は、後述するラベル配置部１０４によって再配置されたラベルを地図上に表示させるものである。地図描画エンジン１０２は、地図ＤＢ１０３から所望の地図情報を検索し、取得するものである。地図ＤＢ１０３は地図情報を格納するものである。
【００２２】
ＰＯＩ ＤＢ１０６は、ＰＯＩに関する位置情報及び属性の情報（属性情報）をＰＯＩごとに格納するデータベースである。ここで、１つのＰＯＩに対して属性情報は１つに限らず、複数の属性情報があってもよい。ラベル抽出部１０５は、ＰＯＩ ＤＢ１０６からＰＯＩに関する位置情報及び属性情報を取得し、地図上の該当する位置にＰＯＩの属性（ラベル）をそれぞれ配置するものである。ここで配置されたＰＯＩの属性群をラベリング候補とする。なお、キーワードの属性の場合はそのままキーワードをラベルとすることができる。他の属性では数値などを用いることになり、数値は表示上、記号の大小や色でマッピングすることになる。
【００２３】
また、ラベル抽出部１０５は、ＰＯＩ ＤＢ１０６からＰＯＩに関する位置情報及び属性情報を取得し、地図上の該当する位置にＰＯＩの属性をそれぞれ配置するのではなく、図２に示すように、複数の属性（Ａ１〜Ａｎ）をいくつかの属性（Ｂ１〜Ｂｍ）にまとめて配置するようにしてもよい。この場合、主成分分析、クラスタリングなどを用いて新しい（数を抑えた）属性の組を定義する。新しい属性の値は、元の属性の値を反映したものでなくてはならない。
【００２４】
例えば、キーワードベクトル空間の場合は、ＰＯＩ（文書）ごとに存在するキーワードの数を元に、よく共起するキーワードをまとめるという処理をLatent Semantic Indexing(ＳＶＤ（Singular Value Decomposition：特異値分解）を利用したキーワードベクトル次元縮退方法)を利用して行う。縮退されたキーワードベクトルは新しい属性であり、元のキーワード属性の線形結合になっている。そのため、重みの高い元のキーワードを代表ラベルとして採用することができる。
【００２５】
ラベル配置部１０４は、ラベリング候補に対して所定の処理を行うことによって最終的なラベルの配置（再配置又は配置調整）を行うものである。なお、ラベル抽出部１０５がラベルを抽出するのみで、ラベルを配置する処理及び再配置する処理をラベル配置部１０４が行うようにしてもよい。また、ラベルを再配置する際、ラベル配置部１０４が所定の条件（後述する閾値ｔなど）を満たすか否かを判断してから再配置するようにしてもよく、判断に関してはラベル配置装置の他の構成要素が判断するようにしてもよい。
【００２６】
ここで、ラベルの配置方法について説明する。ラベルを地図上で配置するために、ＰＯＩの各属性データから、地理的な分布を元に配置する。単一属性（例えば住宅、工場など）や複数の属性をまとめた合成属性（複数のキーワードをまとめた属性など）を用いてもよい。
【００２７】
また、個別の属性分布から別々にラベル位置を求める方法について説明する。属性と座標データより直接ラベル位置を求めることができる。方法として、例えば分布の極大点にラベルを配置する。具体的には、当該属性が最大値（または極大値）をとるＰＯＩ上にラベルを配置する。代表点が複数になる可能性もある。また、他の方法として、例えば分布の中心にラベルを配置する。具体的には、各ＰＯＩの重心などに配置する。ＰＯＩ属性の値による加重重心をとってもよい。この方法では簡易にラベル位置が決められる。その様子を図３に示す。
【００２８】
上記の場合、単一のＰＯＩのみで属性（例えば、青）が０以上である場合は単一ＰＯＩの要約ラベルとなる。また、複数の属性（例えば、赤と青）について属性が０以上である場合は、そのＰＯＩは赤、青双方の分布にカウントされる。また、テキストのベクトル空間モデル（単語別のカウントベクトル）を元にするような場合、属性の数が数万と非常に多く、各属性のうち際立ったもののみを提示する必要がある。そのような場合はあらかじめ文書要約技術（例えば、ＴＦ／ＩＤＦによる単語重要度計算）などで候補となる属性（単語）を絞り込む必要がある。また、この重要度を元に、後述のラベル再配置時のラベル削除や統合の条件の一部とすることもできる。
【００２９】
次に、属性エリアを求めてラベル位置を決める方法について説明する。ラベルを生成する元となるデータは、各点が複数の属性をもつ点分布である。各属性がスカラ値を持つとすると、各属性（ここでは赤、青の属性）について空間的な補完を用いて図４のような場が構成できる。補完方法には、ＴＩＮ（Triangulated Irregular Network）を構成して等高線を得る方法、線形、スプライン補完を利用するものなどがある。得られた場にあるＺ値で等高線を描けば図４のようなエリアが得られる。ただし、図４のように必ずしも互いに排他的なエリアになるとは限らない。
【００３０】
例えば、この場の極大点付近にラベルを配置することでラベル位置を規定できる。ラベル位置の決定方法には以下の方法がある。点分布から求める場合とほぼ同じであるが、排他的エリアを定義することで、重なり合った（多種の属性が混在する）エリアを除外して配置でき、ある属性のみが際立ったエリアを代表点に取ることができるなどのメリットがある。
【００３１】
その方法として、例えば分布の極大点にラベルを配置する。具体的には、各点のうち周囲より大きいもの（点）を選択する。閾値を設定し、極大点から特に高いものを選択する（図５のＡ１参照）。他の方法として、例えば分布の中心にラベルを配置する。具体的には、ある閾値以上の分布ポリゴンの重心などに配置する（図５のＡ２参照）。他の方法として、例えば排他的エリアの中心にラベルを配置する。具体的には、その属性値だけが存在するエリアの中心にラベルを配置する（図５のＡ３参照）。応用として、行政区画など面（ポリゴン）のデータに対するクラスタリング（代表点を用いれば点のクラスタリングに帰結できる）など可能である。
【００３２】
次に、エリア分割を行ったあとメンバーの属性からラベルを得る方法について説明する。上述したエリアを求める方法として特許文献２に開示された技術のように、地理意味クラスタリングを行い、対象ラベルをクラスタ集合内の要約により求める方法もある。上記方法では属性（または合成属性）はあらかじめ選択されているが、特許文献２に開示された方法では、まず属性（意味）と地理（緯度経度座標）の双方を考慮してクラスタリングしてエリアを求め、既定されたエリアにて代表的な属性（ラベル）を得る。最終的には、エリアとそのラベルが提示されるアプリケーションとなっている（図６参照）。
【００３３】
地理意味クラスタリングは、属性（例えば、単語空間）ベクトルに、地図空間ベクトル（緯度経度）を追加してクラスタリングを行う。単語空間ベクトルと地図空間ベクトルを統合することで、地理的に近接しているＰＯＩの中から、意味的に近いＰＯＩを優先的に選んでクラスタ化する。クラスタリングの手法としては一般的なクラスタリング手法でよくＳＯＭ、k-means法、ＥＭアルゴリズムなどがある。地理的なベクトルと意味的なベクトルの合成方法は、単純に他方のベクトルに加重をかける方法、多くのクラスタリングで定義される、距離（類似度）（ユークリッド距離、コサイン類似度など）を、地理空間、意味空間別々に定義してその類似度に加重をかける方法がある。これらの加重を地理意味比とする。
【００３４】
地理的な属性のみを使ってクラスタリングを行うと（図７（ａ）参照）単に地理的な近接度でクラスタリングを行い、エリアごとの均質さは保証されない。一方、意味的なクラスタリングを行うと（図７（ｂ）参照）見た目上、非常にわかりにくい（飛び地などの多い）エリアとなり見た目が犠牲になる。そこで、双方の折衷を行い、双方を加味したクラスタリングを行うことで、見た目にもまとまりよく、かつ内容がなるべく均質なエリアが得られる（図７（ｃ）参照）。地理意味比の調整によって最適な地理意味クラスタリングが得られると考えられる。
【００３５】
次に、ラベルの配置変更方法について説明する。上述したように分布が１箇所に集中することは稀であり、複数の極値が存在するのが普通である。単純に上述した方法でラベル表示を行うと実体を忠実に表示しているが、煩雑な見栄えになりがちである。上述した方法で得られたラベル位置のみを図８に示す。図８（ａ）は、ラベルＡ、Ｂにおいて異種のラベル間の最近隣ラベルの関係を示し、図８（ｂ）はラベルＡ、Ｂにおいて同種のラベル間の最近隣ラベルの関係を示している。この場合、ラベル同士が近すぎて判別しづらい、冗長なラベルがあるなど問題がある。ここでは点の属性データから得られたラベルのみならず、下地となる基本地図のラベルとの重なり合いも同様に考慮することができる（ラベル集合Ｃを導入すればよい）。
【００３６】
上述した問題を解決する方法（上述したラベル配置部１０４による）として以下のものがある。１つ目としては、異種のラベルの最近隣点の片方を削除する方法である。具体的には、最近隣のラベルＡ、Ｂ間の距離が閾値ｔ以下の場合、Ａ、Ｂの各値（あらかじめ決められた各属性が有するスカラ値）の大きなもののみを残す（例えば、図８（ａ）の円内の片方を削除）。２つ目としては、異種のラベルの最近隣点同士を遠ざける方法である。具体的には、最近隣のＡ、Ｂ間の距離が閾値ｔ以下の場合、Ａ、Ｂ間の距離がｔになるように遠ざける（図９（ａ）参照）。３つ目としては、最近隣のラベルとの併合を行う方法である。具体的には、最近隣の同種のラベルとの間に他種のラベルが無い場合、同種のラベル間の距離が閾値ｔ以下のラベルを併合し、両ラベル間の中心点に新たなラベルを配置する。なお、後述する指標を組み合わせて適切な閾値を設定してもよい。
【００３７】
ここで、ラベルを削除、統合する際の閾値ｔを設定するためのラベルの重要度の指標がいくつか存在し、その指標に対する内容には以下のようなものがある。例えば、指標として異種間距離（ｔ１）があり、異種のラベルとどの程度離れているかで判断される。離れているラベルほど削除されにくい。他には、指標として同種間距離（ｔ２）があり、同種のラベルとどの程度離れているかで判断される。離れているラベルほど統合されにくい。他には、指標として同種代表度（ｔ３）があり、どの程度そのラベル種を代表しているラベルかで判断される。ラベル種を代表しているほど削除されにくい。例えば、１／ラベル個数とすれば同種ラベルが少なくなるほど代表度が増す。
【００３８】
他には、指標としてラベル標高（ｔ４）があり、極値ベースの方法でラベル位置を決定した場合に、そのＺ座標（標高）で判断される。高いほど削除されにくい。他には、指標としてラベル影響範囲（ｔ５）があり、エリアベースの方法でラベル位置を決定した場合に、元となるエリアの広さで判断される。広いほど削除されにくい。他には、指標としてラベル重要度（ｔ６）があり、ラベル種そのものに重要度が付与されている場合、その重要度で判断される。重要度が高いほど削除されにくい。他には、指標としてラベル重複度（ｔ７）があり、近隣（半径t以内など）のラベルとの類似度で判断される。類似度が高いほど削除されやすい。
【００３９】
これらの各指標うち、いくつかあるいはすべてを極性（削除されやすいか、されにくいか）を考慮して線形結合などで合成した値を用いて、適切な閾値を設定する。この場合の合成指標をtoptとする。
【００４０】
次に、パラメータの最適化手法について説明する。最適な閾値ｔの決定は表示する属性の組み合わせ、表示する場所などに大きく影響されるため、一意に決められない。表示するデータによりｔを最適化するための指標として、結果表示の複雑さを用いる。結果表示の複雑さと内容表示の忠実さはしばしばトレードオフとなる。すなわち、tを大きくして比較的離れたラベル同士を併合、削除してしまうため、複雑さを抑えることができるが、忠実さは損なわれる。逆にtを小さくして極近接したラベルのみしか併合削除しないとなると、複雑さは大きなまま変化しないが、忠実さは維持される。これについても上述のエリア分割方法での地理意味比に相当するようなパラメータの調整によって最適な値を設定することになる。
【００４１】
ここでの複雑さの指標としては、ラベルの集合をクラスタとみなして、クラスタのよさに対する指標（後述のＣＨインデクスなど）が利用できる。また、図９の実線、破線で記したネットワークのような際近隣グラフ（ドロネー図（図１０）など）を作成し、グラフ上の同種ラベルの隣接関係などを用いた指標も利用できる。例えば図９（ｂ）では、ラベルＡ同士の間にＢ同士を結ぶリンクが交差しており、そのような交差の数をカウントすることで、ラベル配置の分散や見た目の複雑さを定義できる。
【００４２】
一方、上述したエリア分割を行ったあとメンバーの属性からラベルを得る方法を用いてエリアを生成、ラベル表示する場合は、エリア表示の最適化を行う必要がある。この方法では地理意味比を変えながら最適化する。この際ＣＨ（Calinski Harabasz）指標、空間的自己相関などのクラスタの良さ(クラスタ内のばらつきが少なく、他のクラスタとの距離が遠い)に閾値を設け、その中で忠実度（属性による近接度を採用する度合い）を最大化する。その概念図を図１１に示す。
【００４３】
ここで、パラメータ最適化の例について説明する。上記のステップにおいて実際のデータを用いると、地理意味比において以下のようなＣＨ比の変化がみえる（図１２参照）。ＣＨ比による閾値を設定すれば判読しやすいエリアを得ることができる。なお、ＣＨ指数については以下を参照。
http://www.msi.co.jp/vmstudio/materials/tech/cluster.htmlなど参照。
【００４４】
よってＣＨ指数は、クラスタ間のばらつきが良く、クラスタ内の近接度が高いという指標となり、クラスタリング結果の良し悪しの指標として用いられる。この他Hartigan Validation、Ratkowsky and Lance Validation、Dunn’s Validity Indexなどでも同様の効果が得られると思われる。クラスタ（エリア）を介さず直接ラベルを提示する場合は同一種のラベルをクラスタとみなせばよい。
【００４５】
なお、上記で求めた最適値が、与えられたデータセット上で複雑さの初期値（例えば、ＴＨ＝０（位置再配置を全く行わない）の時のＣＨ指数など）と強い相関があるなら、最適値を初期値の関係を求め、複数の試行を行わず一意に最適値を推定可能である。
【００４６】
ここで、パラメータ最適化の処理フローの一例を図１３に示す。ラベル削除及びクラスタリングのパラメータ双方についての最適化方法を示す。複雑さが最大となるような初期値（ラベル削除の場合は全く削除しない状態：閾値０、クラスタリングの場合は意味属性のみを考慮する比率）を初期値として設定する。そして、徐々にパラメータを、複雑さを緩和する方向へ変更していき、許容できる複雑さになるまで繰り返す。初めて許容できる複雑さになった時点が最適値（最適なパラメータ）となる。
【００４７】
以上より、地理的分布のみならず可視化されるべき次元は他のものを対象にできる。また、同様の手法で、多次元データにおいて可視化されるべき、あるいは分割の対象となるべき次元セット（上記では地理座標、画像、レイアウトされたテキストの座標（２、３次元）、時系列観測データにおける時刻（１次元）など）のある空間―属性クラスタリングを行う場合に応用できる。例えば、観測される生物構成、歴史的出来事による年代のクラスタリング、人間の行動の時系列をクラスタリングする場合などが考えられる。
【００４８】
点（ＰＯＩ）に関する属性についてはテキストのみならず、以下のような属性値やその組み合わせに応用可能である。クラスタリングを適切に行えるなら特にスカラ量でなくてもよい（ジャンルなど）。例えば、地物の属性（ジャンル、人口、売り上げ、地価、植生、鉱物資源分布、地理的に関連付けられた、音声、画像、動画などのマルチメディア情報やその特性量など）がある。また、点だけでなく、線（道路など）、面（行政区画など）、立体（ビルなど）なども代表点を定義して同様のことが可能である。また、画面、誌面上での文字、写真、ブロック、ウィンドウなどや、時間的地点の属性（時系列測定データ、年表）などがある。
【産業上の利用可能性】
【００４９】
本発明に係るラベル配置装置は、ユーザからの見栄え、認識のしやすさ、使いやすさを考慮したラベル配置をすることができるため、地点の属性を示すラベルを地図上に配置するラベル配置装置などに有用である。
【符号の説明】
【００５０】
１０１ 地図描画部
１０２ 地図エンジン部
１０３ 地図ＤＢ
１０４ ラベル配置部（判断手段、調整手段）
１０５ ラベル抽出部（配置手段）
１０６ ＰＯＩ ＤＢ（格納手段）
１０７ クラスタリング機能部
１０８ エリア抽出部
【技術分野】
【０００１】
本発明は、地点の属性を示すラベルを地図上に配置するラベル配置装置に関する。
【背景技術】
【０００２】
一般的な地図サービスでは、ＰＯＩ（Point of Interest）について点＋地名などのラベルで提示するのが基本である。それ以上の内容は、ユーザがクリックしてポップアップによって提示するなどで個別の提示が行われる。大量のＰＯＩが対象の場合は非常に煩雑である。また、原理的に地図を最初に見た段階では、テキスト情報などは含まれていないので、内容を把握するためにはいくつかのステップによる検索やブラウズ操作が必要である。これに対して、ＧＩＳ（Geographic Information System）などでは、定量化された属性を点分布で提示したり、集計された代表点でのシンボル提示をしたり、それを補完したサーフェイスによる等高線で提示したり、いろいろな方法がある。
【０００３】
表示する内容は様々であるが、ＧＩＳなどは、地物あるいはエリアに割り当てられた定量化された値を提示するための方法である。一度に複数の属性の分布を提示することもできるが、数個の分布を表示しただけでも解読が難しい複雑な図になってしまう傾向がある。一方、各属性で、際立った場所にだけラベルを配置するようにすれば、この問題に対処できる。ところが、地名のように、基本的に、同じラベルが１地点にしか現れないような場合は単純な方法でよいが、上記の属性のように多数存在し、かつ、必ずしも１箇所に集約表示できないような場合（ある程度分布が散らばっている場合）には、ラベルの数が多くなりすぎる傾向になり、対処が必要である。つまり表示すべき属性が多いので代表点だけを提示したいが、１つの代表点だけではその属性の分布を表しきれないような場合には従来にない特別な配慮が必要となる。
【０００４】
例えば、「東京」、「神奈川」などの属性（ラベル）は代表的な１つの点で表現してもよいが、「リアス式海岸」、「日の出スポット」、「景勝地」、「観光船」、「松の群生地」などのラベルは、分布が散らばっているため１箇所で現せず、また無数に属性が存在するため、同時に表わそうとすると非常に煩雑かつ解読の難しい地図になってしまう。また、分布が重なるため一方のラベルが他方のラベルと競合してしまう可能性が高い。これらを、ユーザが判読しやすく、かつ、実際の分布の情報を損なわずに伝える調整手段が必要である。なお、地名のように単一の属性が１箇所にしか現れないような場合には、一例として下記の特許文献１に開示された手法が用いられる。
【０００５】
上述したような課題を解決するために、エリアに対応したラベルを何らかの方法で要約表示させることで、地図上で事前にエリアごとのおおまかなラベルを把握できるようにする方法が考えられる。これには以下のような方法がある。１つ目の方法は、あらかじめ決められた属性（ラベル）ごとの地図を提示する方法である。２つ目の方法は、地図上に代表的なラベルを提示する方法である。３つ目の方法は、地図上でまずエリアを明示的に分割し、各々のエリアにラベルを提示する方法である。
【０００６】
１つ目の方法は、属性ごとにその分布を提示するのみであるが、内容がテキストの場合、すべての属性を表示させ内容を把握させることは不可能である。ラベルを限定して地図上に分布を表示させることもできるが、これは既存の等高線描画などを用いればよい。複数の地図表示を切り替えることになり操作が煩雑になる。２つ目の方法は、１つ目の方法で得られた各属性（テキスト）の等高線の最高点にラベルを配置するなどで比較的容易に実現できる。１つ目の方法に比べ一画面で把握できる点で優れている。ただし、ラベル同士が重なり合う場合は視認性が悪くなる恐れがある。
【０００７】
３つ目の方法は、地図において、あらかじめエリアを分割してラベルを配置するものである。これによりラベルの視認性は向上する。３つ目の方法では、散在する点（面やエリアの代表点を含む）データ（例えば、地物、観測点などのデータ）の分布に基づいたエリア分割をする際、点データの地図上での近接度（距離）と点データの属性の近接度（例えば、似た種類の店舗、似た植生、似た世代分布、似た口コミ、ガイド文章など）を元にクラスタリング（グルーピング）する（特許文献２を参照）。
【０００８】
特許文献２に開示された技術によれば、双方（地図上での近接度と属性の近接度）を元にしたクラスタリングにより、内容に基づいた均質な内容であるとともに、地図上である程度まとまった（目で見てわかりやすい）エリアが得られる。この技術は地図上で簡単な要約マップを作るアプリケーションに応用できる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開平９−２３７０３４号公報（要約）
【特許文献２】特開２００８−２２４９９３号公報（要約）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、２つ目、３つ目の方法において共に課題がある。すなわち、扱うデータなどによっては、ラベル配置をする際にラベルの重なりを必ず回避できるとは限らず、最適なラベル配置とならないことがある。
【００１１】
本発明は、上記の問題点に鑑み、ユーザからの見栄え、認識のしやすさ、使いやすさを考慮したラベル配置をすることができるラベル配置装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、本発明によれば、複数の地点それぞれの地図上における位置情報及び前記地点の属性を示すラベルのデータを前記地点ごとに格納する格納手段と、前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、前記地図上の前記地点の位置に前記ラベルを前記地点ごとに配置する配置手段と、前記配置手段によって配置されたそれぞれのラベルに対して、複数ラベル配置のための所定の条件を満たすか否かを判断する判断手段と、前記判断手段によって前記所定の条件を満たさないと判断された場合、配置された前記ラベルの配置調整を行う調整手段とを、備えるラベル配置装置が提供される。この構成により、ユーザからの見栄え、認識のしやすさ、使いやすさを考慮したラベル配置をすることができる。なお、ここでの調整手段は、すべてのラベルが所定の条件を満たすまでラベルの配置調整をしてもよく、ある程度のところでラベルの配置調整を止めてもよい。また、ここでのラベルのデータは、テキストデータでもよく、記号などを示すデータでもよい。
【００１３】
また、本発明のラベル配置装置において、前記調整手段が、ラベルの削除、統合、移動のうちのいずれか１つを行うことによって前記ラベルの配置調整を行うことは、本発明の好ましい態様である。この構成により、地図上での視認性を向上させることができる。
【００１４】
また、本発明のラベル配置装置において、前記調整手段が、前記地図上での前記ラベルの所定の視認性が確保できる範囲内で、前記配置手段によって配置されたそれぞれのラベルの前記地図上での配置位置の正確度を最適化させるように、前記ラベルの配置調整を行うことは、本発明の好ましい態様である。この構成により、視認性及び忠実性の双方を反映させることができる。
【００１５】
また、本発明のラベル配置装置において、前記配置手段が、前記ラベルを前記地点ごとに配置しない場合、前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、所定のクラスタリング処理を行い、クラスタごとに前記ラベルを配置し、前記調整手段が、前記配置手段によって配置されたそれぞれのクラスタの前記地図上での所定のまとまりの良さが確保できる範囲内で、前記地図上での前記クラスタの内容の正確度が最適化されるように、前記クラスタの配置調整を行うことは、本発明の好ましい態様である。この構成により、視認性及び忠実性の双方を反映させることができる。
【００１６】
また、本発明のラベル配置装置において、前記調整手段が、前記最適化のためのパラメータを算出する際、ラベル配置又はクラスタの見た目の複雑さを示す所定の情報の初期値をもって前記パラメータを推定することは、本発明の好ましい態様である。この構成により、複数のパラメータ算出の処理を減らすことができる。
【００１７】
また、本発明のラベル配置装置において、前記調整手段が、前記配置手段によって配置されたそれぞれのラベルの前記地図上での配置位置の所定の正確度が確保できる範囲内で、前記地図上での前記ラベルの視認性を最適化させるように、前記ラベルの配置調整を行うことは、本発明の好ましい態様である。この構成により、正確性の乖離をある程度抑え、地理的に関連の深い属性グループを抽出できる。
【００１８】
また、本発明のラベル配置装置において、前記配置手段が、前記ラベルを前記地点ごとに配置しない場合、前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、所定のクラスタリング処理を行い、クラスタごとに前記ラベルを配置し、前記調整手段が、前記地図上での前記クラスタの内容の所定の正確度が確保できる範囲内で、前記配置手段によって配置されたそれぞれのクラスタの前記地図上でのまとまりの良さを最適化させるように、前記クラスタの配置調整を行うことは、本発明の好ましい態様である。この構成により、正確性の乖離をある程度抑え、地理的に関連の深い属性グループを抽出できる。
【発明の効果】
【００１９】
本発明のラベル配置装置は、上記構成を有し、ユーザからの見栄え、認識のしやすさ、使いやすさを考慮したラベル配置をすることができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態に係るラベル配置装置の構成の一例を示す構成図である。
【図２】本発明の実施の形態における複数の属性をいくつかの属性にまとめることについて説明するための図である。
【図３】本発明の実施の形態における個別の属性分布から別々にラベル位置を求める方法について説明するための図である。
【図４】本発明の実施の形態における各属性について空間的な補完を用いて構成される場について説明するための図である。
【図５】本発明の実施の形態におけるエリアを介したラベル位置の決定方法について説明するための図である。
【図６】本発明の実施の形態におけるエリア分割を行ったあとメンバーの属性からラベルを得る方法について説明するための図である。
【図７ａ】本発明の実施の形態における地理クラスタリングの様子を示す図である。
【図７ｂ】本発明の実施の形態における意味クラスタリングの様子を示す図である。
【図７ｃ】本発明の実施の形態における地理意味クラスタリングの様子を示す図である。
【図８ａ】本発明の実施の形態におけるラベルＡ、Ｂにおいて異種のラベル間の最近隣ラベルの関係を示す図である。
【図８ｂ】本発明の実施の形態におけるラベルＡ、Ｂにおいて同種のラベル間の最近隣ラベルの関係を示す図である。
【図９ａ】本発明の実施の形態におけるラベルの再配置の一例について説明するための図である。
【図９ｂ】本発明の実施の形態におけるラベルの再配置の一例について説明するための他の図である。
【図１０】本発明の実施の形態におけるパラメータ最適化手法を説明するためのドロネー図を示す図である。
【図１１】本発明の実施の形態におけるクラスタの良さと忠実度とのトレードオフの概念を示す図である。
【図１２】本発明の実施の形態におけるパラメータ最適化の例について説明するための図である。
【図１３】本発明の実施の形態におけるパラメータ最適化の処理フローの一例を示すフローチャートである。
【発明を実施するための形態】
【００２１】
本発明の実施の形態に係るラベル配置装置の構成の一例について図１を用いて説明する。ラベル配置装置は、地図描画部１０１、地図描画エンジン１０２、地図ＤＢ（Data Base）１０３、ラベル配置部１０４、ラベル抽出部１０５、ＰＯＩ ＤＢ１０６、クラスタリング機能部１０７、エリア抽出部１０８から構成されている。なお、クラスタリング機能部１０７及びエリア抽出部１０８は後述するクラスタリング処理を行う場合には必要な構成要素である。地図描画部１０１は、地図描画エンジン１０２によって地図ＤＢ１０３から検索された地図情報を不図示の表示部（ディスプレイなど）に表示させるものである。また、地図描画部１０１は、後述するラベル配置部１０４によって再配置されたラベルを地図上に表示させるものである。地図描画エンジン１０２は、地図ＤＢ１０３から所望の地図情報を検索し、取得するものである。地図ＤＢ１０３は地図情報を格納するものである。
【００２２】
ＰＯＩ ＤＢ１０６は、ＰＯＩに関する位置情報及び属性の情報（属性情報）をＰＯＩごとに格納するデータベースである。ここで、１つのＰＯＩに対して属性情報は１つに限らず、複数の属性情報があってもよい。ラベル抽出部１０５は、ＰＯＩ ＤＢ１０６からＰＯＩに関する位置情報及び属性情報を取得し、地図上の該当する位置にＰＯＩの属性（ラベル）をそれぞれ配置するものである。ここで配置されたＰＯＩの属性群をラベリング候補とする。なお、キーワードの属性の場合はそのままキーワードをラベルとすることができる。他の属性では数値などを用いることになり、数値は表示上、記号の大小や色でマッピングすることになる。
【００２３】
また、ラベル抽出部１０５は、ＰＯＩ ＤＢ１０６からＰＯＩに関する位置情報及び属性情報を取得し、地図上の該当する位置にＰＯＩの属性をそれぞれ配置するのではなく、図２に示すように、複数の属性（Ａ１〜Ａｎ）をいくつかの属性（Ｂ１〜Ｂｍ）にまとめて配置するようにしてもよい。この場合、主成分分析、クラスタリングなどを用いて新しい（数を抑えた）属性の組を定義する。新しい属性の値は、元の属性の値を反映したものでなくてはならない。
【００２４】
例えば、キーワードベクトル空間の場合は、ＰＯＩ（文書）ごとに存在するキーワードの数を元に、よく共起するキーワードをまとめるという処理をLatent Semantic Indexing(ＳＶＤ（Singular Value Decomposition：特異値分解）を利用したキーワードベクトル次元縮退方法)を利用して行う。縮退されたキーワードベクトルは新しい属性であり、元のキーワード属性の線形結合になっている。そのため、重みの高い元のキーワードを代表ラベルとして採用することができる。
【００２５】
ラベル配置部１０４は、ラベリング候補に対して所定の処理を行うことによって最終的なラベルの配置（再配置又は配置調整）を行うものである。なお、ラベル抽出部１０５がラベルを抽出するのみで、ラベルを配置する処理及び再配置する処理をラベル配置部１０４が行うようにしてもよい。また、ラベルを再配置する際、ラベル配置部１０４が所定の条件（後述する閾値ｔなど）を満たすか否かを判断してから再配置するようにしてもよく、判断に関してはラベル配置装置の他の構成要素が判断するようにしてもよい。
【００２６】
ここで、ラベルの配置方法について説明する。ラベルを地図上で配置するために、ＰＯＩの各属性データから、地理的な分布を元に配置する。単一属性（例えば住宅、工場など）や複数の属性をまとめた合成属性（複数のキーワードをまとめた属性など）を用いてもよい。
【００２７】
また、個別の属性分布から別々にラベル位置を求める方法について説明する。属性と座標データより直接ラベル位置を求めることができる。方法として、例えば分布の極大点にラベルを配置する。具体的には、当該属性が最大値（または極大値）をとるＰＯＩ上にラベルを配置する。代表点が複数になる可能性もある。また、他の方法として、例えば分布の中心にラベルを配置する。具体的には、各ＰＯＩの重心などに配置する。ＰＯＩ属性の値による加重重心をとってもよい。この方法では簡易にラベル位置が決められる。その様子を図３に示す。
【００２８】
上記の場合、単一のＰＯＩのみで属性（例えば、青）が０以上である場合は単一ＰＯＩの要約ラベルとなる。また、複数の属性（例えば、赤と青）について属性が０以上である場合は、そのＰＯＩは赤、青双方の分布にカウントされる。また、テキストのベクトル空間モデル（単語別のカウントベクトル）を元にするような場合、属性の数が数万と非常に多く、各属性のうち際立ったもののみを提示する必要がある。そのような場合はあらかじめ文書要約技術（例えば、ＴＦ／ＩＤＦによる単語重要度計算）などで候補となる属性（単語）を絞り込む必要がある。また、この重要度を元に、後述のラベル再配置時のラベル削除や統合の条件の一部とすることもできる。
【００２９】
次に、属性エリアを求めてラベル位置を決める方法について説明する。ラベルを生成する元となるデータは、各点が複数の属性をもつ点分布である。各属性がスカラ値を持つとすると、各属性（ここでは赤、青の属性）について空間的な補完を用いて図４のような場が構成できる。補完方法には、ＴＩＮ（Triangulated Irregular Network）を構成して等高線を得る方法、線形、スプライン補完を利用するものなどがある。得られた場にあるＺ値で等高線を描けば図４のようなエリアが得られる。ただし、図４のように必ずしも互いに排他的なエリアになるとは限らない。
【００３０】
例えば、この場の極大点付近にラベルを配置することでラベル位置を規定できる。ラベル位置の決定方法には以下の方法がある。点分布から求める場合とほぼ同じであるが、排他的エリアを定義することで、重なり合った（多種の属性が混在する）エリアを除外して配置でき、ある属性のみが際立ったエリアを代表点に取ることができるなどのメリットがある。
【００３１】
その方法として、例えば分布の極大点にラベルを配置する。具体的には、各点のうち周囲より大きいもの（点）を選択する。閾値を設定し、極大点から特に高いものを選択する（図５のＡ１参照）。他の方法として、例えば分布の中心にラベルを配置する。具体的には、ある閾値以上の分布ポリゴンの重心などに配置する（図５のＡ２参照）。他の方法として、例えば排他的エリアの中心にラベルを配置する。具体的には、その属性値だけが存在するエリアの中心にラベルを配置する（図５のＡ３参照）。応用として、行政区画など面（ポリゴン）のデータに対するクラスタリング（代表点を用いれば点のクラスタリングに帰結できる）など可能である。
【００３２】
次に、エリア分割を行ったあとメンバーの属性からラベルを得る方法について説明する。上述したエリアを求める方法として特許文献２に開示された技術のように、地理意味クラスタリングを行い、対象ラベルをクラスタ集合内の要約により求める方法もある。上記方法では属性（または合成属性）はあらかじめ選択されているが、特許文献２に開示された方法では、まず属性（意味）と地理（緯度経度座標）の双方を考慮してクラスタリングしてエリアを求め、既定されたエリアにて代表的な属性（ラベル）を得る。最終的には、エリアとそのラベルが提示されるアプリケーションとなっている（図６参照）。
【００３３】
地理意味クラスタリングは、属性（例えば、単語空間）ベクトルに、地図空間ベクトル（緯度経度）を追加してクラスタリングを行う。単語空間ベクトルと地図空間ベクトルを統合することで、地理的に近接しているＰＯＩの中から、意味的に近いＰＯＩを優先的に選んでクラスタ化する。クラスタリングの手法としては一般的なクラスタリング手法でよくＳＯＭ、k-means法、ＥＭアルゴリズムなどがある。地理的なベクトルと意味的なベクトルの合成方法は、単純に他方のベクトルに加重をかける方法、多くのクラスタリングで定義される、距離（類似度）（ユークリッド距離、コサイン類似度など）を、地理空間、意味空間別々に定義してその類似度に加重をかける方法がある。これらの加重を地理意味比とする。
【００３４】
地理的な属性のみを使ってクラスタリングを行うと（図７（ａ）参照）単に地理的な近接度でクラスタリングを行い、エリアごとの均質さは保証されない。一方、意味的なクラスタリングを行うと（図７（ｂ）参照）見た目上、非常にわかりにくい（飛び地などの多い）エリアとなり見た目が犠牲になる。そこで、双方の折衷を行い、双方を加味したクラスタリングを行うことで、見た目にもまとまりよく、かつ内容がなるべく均質なエリアが得られる（図７（ｃ）参照）。地理意味比の調整によって最適な地理意味クラスタリングが得られると考えられる。
【００３５】
次に、ラベルの配置変更方法について説明する。上述したように分布が１箇所に集中することは稀であり、複数の極値が存在するのが普通である。単純に上述した方法でラベル表示を行うと実体を忠実に表示しているが、煩雑な見栄えになりがちである。上述した方法で得られたラベル位置のみを図８に示す。図８（ａ）は、ラベルＡ、Ｂにおいて異種のラベル間の最近隣ラベルの関係を示し、図８（ｂ）はラベルＡ、Ｂにおいて同種のラベル間の最近隣ラベルの関係を示している。この場合、ラベル同士が近すぎて判別しづらい、冗長なラベルがあるなど問題がある。ここでは点の属性データから得られたラベルのみならず、下地となる基本地図のラベルとの重なり合いも同様に考慮することができる（ラベル集合Ｃを導入すればよい）。
【００３６】
上述した問題を解決する方法（上述したラベル配置部１０４による）として以下のものがある。１つ目としては、異種のラベルの最近隣点の片方を削除する方法である。具体的には、最近隣のラベルＡ、Ｂ間の距離が閾値ｔ以下の場合、Ａ、Ｂの各値（あらかじめ決められた各属性が有するスカラ値）の大きなもののみを残す（例えば、図８（ａ）の円内の片方を削除）。２つ目としては、異種のラベルの最近隣点同士を遠ざける方法である。具体的には、最近隣のＡ、Ｂ間の距離が閾値ｔ以下の場合、Ａ、Ｂ間の距離がｔになるように遠ざける（図９（ａ）参照）。３つ目としては、最近隣のラベルとの併合を行う方法である。具体的には、最近隣の同種のラベルとの間に他種のラベルが無い場合、同種のラベル間の距離が閾値ｔ以下のラベルを併合し、両ラベル間の中心点に新たなラベルを配置する。なお、後述する指標を組み合わせて適切な閾値を設定してもよい。
【００３７】
ここで、ラベルを削除、統合する際の閾値ｔを設定するためのラベルの重要度の指標がいくつか存在し、その指標に対する内容には以下のようなものがある。例えば、指標として異種間距離（ｔ１）があり、異種のラベルとどの程度離れているかで判断される。離れているラベルほど削除されにくい。他には、指標として同種間距離（ｔ２）があり、同種のラベルとどの程度離れているかで判断される。離れているラベルほど統合されにくい。他には、指標として同種代表度（ｔ３）があり、どの程度そのラベル種を代表しているラベルかで判断される。ラベル種を代表しているほど削除されにくい。例えば、１／ラベル個数とすれば同種ラベルが少なくなるほど代表度が増す。
【００３８】
他には、指標としてラベル標高（ｔ４）があり、極値ベースの方法でラベル位置を決定した場合に、そのＺ座標（標高）で判断される。高いほど削除されにくい。他には、指標としてラベル影響範囲（ｔ５）があり、エリアベースの方法でラベル位置を決定した場合に、元となるエリアの広さで判断される。広いほど削除されにくい。他には、指標としてラベル重要度（ｔ６）があり、ラベル種そのものに重要度が付与されている場合、その重要度で判断される。重要度が高いほど削除されにくい。他には、指標としてラベル重複度（ｔ７）があり、近隣（半径t以内など）のラベルとの類似度で判断される。類似度が高いほど削除されやすい。
【００３９】
これらの各指標うち、いくつかあるいはすべてを極性（削除されやすいか、されにくいか）を考慮して線形結合などで合成した値を用いて、適切な閾値を設定する。この場合の合成指標をtoptとする。
【００４０】
次に、パラメータの最適化手法について説明する。最適な閾値ｔの決定は表示する属性の組み合わせ、表示する場所などに大きく影響されるため、一意に決められない。表示するデータによりｔを最適化するための指標として、結果表示の複雑さを用いる。結果表示の複雑さと内容表示の忠実さはしばしばトレードオフとなる。すなわち、tを大きくして比較的離れたラベル同士を併合、削除してしまうため、複雑さを抑えることができるが、忠実さは損なわれる。逆にtを小さくして極近接したラベルのみしか併合削除しないとなると、複雑さは大きなまま変化しないが、忠実さは維持される。これについても上述のエリア分割方法での地理意味比に相当するようなパラメータの調整によって最適な値を設定することになる。
【００４１】
ここでの複雑さの指標としては、ラベルの集合をクラスタとみなして、クラスタのよさに対する指標（後述のＣＨインデクスなど）が利用できる。また、図９の実線、破線で記したネットワークのような際近隣グラフ（ドロネー図（図１０）など）を作成し、グラフ上の同種ラベルの隣接関係などを用いた指標も利用できる。例えば図９（ｂ）では、ラベルＡ同士の間にＢ同士を結ぶリンクが交差しており、そのような交差の数をカウントすることで、ラベル配置の分散や見た目の複雑さを定義できる。
【００４２】
一方、上述したエリア分割を行ったあとメンバーの属性からラベルを得る方法を用いてエリアを生成、ラベル表示する場合は、エリア表示の最適化を行う必要がある。この方法では地理意味比を変えながら最適化する。この際ＣＨ（Calinski Harabasz）指標、空間的自己相関などのクラスタの良さ(クラスタ内のばらつきが少なく、他のクラスタとの距離が遠い)に閾値を設け、その中で忠実度（属性による近接度を採用する度合い）を最大化する。その概念図を図１１に示す。
【００４３】
ここで、パラメータ最適化の例について説明する。上記のステップにおいて実際のデータを用いると、地理意味比において以下のようなＣＨ比の変化がみえる（図１２参照）。ＣＨ比による閾値を設定すれば判読しやすいエリアを得ることができる。なお、ＣＨ指数については以下を参照。
http://www.msi.co.jp/vmstudio/materials/tech/cluster.htmlなど参照。
【００４４】
よってＣＨ指数は、クラスタ間のばらつきが良く、クラスタ内の近接度が高いという指標となり、クラスタリング結果の良し悪しの指標として用いられる。この他Hartigan Validation、Ratkowsky and Lance Validation、Dunn’s Validity Indexなどでも同様の効果が得られると思われる。クラスタ（エリア）を介さず直接ラベルを提示する場合は同一種のラベルをクラスタとみなせばよい。
【００４５】
なお、上記で求めた最適値が、与えられたデータセット上で複雑さの初期値（例えば、ＴＨ＝０（位置再配置を全く行わない）の時のＣＨ指数など）と強い相関があるなら、最適値を初期値の関係を求め、複数の試行を行わず一意に最適値を推定可能である。
【００４６】
ここで、パラメータ最適化の処理フローの一例を図１３に示す。ラベル削除及びクラスタリングのパラメータ双方についての最適化方法を示す。複雑さが最大となるような初期値（ラベル削除の場合は全く削除しない状態：閾値０、クラスタリングの場合は意味属性のみを考慮する比率）を初期値として設定する。そして、徐々にパラメータを、複雑さを緩和する方向へ変更していき、許容できる複雑さになるまで繰り返す。初めて許容できる複雑さになった時点が最適値（最適なパラメータ）となる。
【００４７】
以上より、地理的分布のみならず可視化されるべき次元は他のものを対象にできる。また、同様の手法で、多次元データにおいて可視化されるべき、あるいは分割の対象となるべき次元セット（上記では地理座標、画像、レイアウトされたテキストの座標（２、３次元）、時系列観測データにおける時刻（１次元）など）のある空間―属性クラスタリングを行う場合に応用できる。例えば、観測される生物構成、歴史的出来事による年代のクラスタリング、人間の行動の時系列をクラスタリングする場合などが考えられる。
【００４８】
点（ＰＯＩ）に関する属性についてはテキストのみならず、以下のような属性値やその組み合わせに応用可能である。クラスタリングを適切に行えるなら特にスカラ量でなくてもよい（ジャンルなど）。例えば、地物の属性（ジャンル、人口、売り上げ、地価、植生、鉱物資源分布、地理的に関連付けられた、音声、画像、動画などのマルチメディア情報やその特性量など）がある。また、点だけでなく、線（道路など）、面（行政区画など）、立体（ビルなど）なども代表点を定義して同様のことが可能である。また、画面、誌面上での文字、写真、ブロック、ウィンドウなどや、時間的地点の属性（時系列測定データ、年表）などがある。
【産業上の利用可能性】
【００４９】
本発明に係るラベル配置装置は、ユーザからの見栄え、認識のしやすさ、使いやすさを考慮したラベル配置をすることができるため、地点の属性を示すラベルを地図上に配置するラベル配置装置などに有用である。
【符号の説明】
【００５０】
１０１ 地図描画部
１０２ 地図エンジン部
１０３ 地図ＤＢ
１０４ ラベル配置部（判断手段、調整手段）
１０５ ラベル抽出部（配置手段）
１０６ ＰＯＩ ＤＢ（格納手段）
１０７ クラスタリング機能部
１０８ エリア抽出部
【特許請求の範囲】
【請求項１】
複数の地点それぞれの地図上における位置情報及び前記地点の属性を示すラベルのデータを前記地点ごとに格納する格納手段と、
前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、前記地図上の前記地点の位置に前記ラベルを前記地点ごとに配置する配置手段と、
前記配置手段によって配置されたそれぞれのラベルに対して、複数ラベル配置のための所定の条件を満たすか否かを判断する判断手段と、
前記判断手段によって前記所定の条件を満たさないと判断された場合、配置された前記ラベルの配置調整を行う調整手段とを、
備えるラベル配置装置。
【請求項２】
前記調整手段は、ラベルの削除、統合、移動のうちのいずれか１つを行うことによって前記ラベルの配置調整を行う請求項１に記載のラベル配置装置。
【請求項３】
前記調整手段は、前記地図上での前記ラベルの所定の視認性が確保できる範囲内で、前記配置手段によって配置されたそれぞれのラベルの前記地図上での配置位置の正確度を最適化させるように、前記ラベルの配置調整を行う請求項１又は２に記載のラベル配置装置。
【請求項４】
前記配置手段は、前記ラベルを前記地点ごとに配置しない場合、前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、所定のクラスタリング処理を行い、クラスタごとに前記ラベルを配置し、
前記調整手段は、前記配置手段によって配置されたそれぞれのクラスタの前記地図上での所定のまとまりの良さが確保できる範囲内で、前記地図上での前記クラスタの内容の正確度を最適化させるように、前記クラスタの配置調整を行う請求項１に記載のラベル配置装置。
【請求項５】
前記調整手段は、前記最適化のためのパラメータを算出する際、ラベル配置又はクラスタの見た目の複雑さを示す所定の情報の初期値をもって前記パラメータを推定する請求項３又は４に記載のラベル配置装置。
【請求項６】
前記調整手段は、前記配置手段によって配置されたそれぞれのラベルの前記地図上での配置位置の所定の正確度が確保できる範囲内で、前記地図上での前記ラベルの視認性を最適化させるように、前記ラベルの配置調整を行う請求項１又は２に記載のラベル配置装置。
【請求項７】
前記配置手段は、前記ラベルを前記地点ごとに配置しない場合、前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、所定のクラスタリング処理を行い、クラスタごとに前記ラベルを配置し、
前記調整手段は、前記地図上での前記クラスタの内容の所定の正確度が確保できる範囲内で、前記配置手段によって配置されたそれぞれのクラスタの前記地図上でのまとまりの良さを最適化させるように、前記クラスタの配置調整を行う請求項１に記載のラベル配置装置。
【請求項１】
複数の地点それぞれの地図上における位置情報及び前記地点の属性を示すラベルのデータを前記地点ごとに格納する格納手段と、
前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、前記地図上の前記地点の位置に前記ラベルを前記地点ごとに配置する配置手段と、
前記配置手段によって配置されたそれぞれのラベルに対して、複数ラベル配置のための所定の条件を満たすか否かを判断する判断手段と、
前記判断手段によって前記所定の条件を満たさないと判断された場合、配置された前記ラベルの配置調整を行う調整手段とを、
備えるラベル配置装置。
【請求項２】
前記調整手段は、ラベルの削除、統合、移動のうちのいずれか１つを行うことによって前記ラベルの配置調整を行う請求項１に記載のラベル配置装置。
【請求項３】
前記調整手段は、前記地図上での前記ラベルの所定の視認性が確保できる範囲内で、前記配置手段によって配置されたそれぞれのラベルの前記地図上での配置位置の正確度を最適化させるように、前記ラベルの配置調整を行う請求項１又は２に記載のラベル配置装置。
【請求項４】
前記配置手段は、前記ラベルを前記地点ごとに配置しない場合、前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、所定のクラスタリング処理を行い、クラスタごとに前記ラベルを配置し、
前記調整手段は、前記配置手段によって配置されたそれぞれのクラスタの前記地図上での所定のまとまりの良さが確保できる範囲内で、前記地図上での前記クラスタの内容の正確度を最適化させるように、前記クラスタの配置調整を行う請求項１に記載のラベル配置装置。
【請求項５】
前記調整手段は、前記最適化のためのパラメータを算出する際、ラベル配置又はクラスタの見た目の複雑さを示す所定の情報の初期値をもって前記パラメータを推定する請求項３又は４に記載のラベル配置装置。
【請求項６】
前記調整手段は、前記配置手段によって配置されたそれぞれのラベルの前記地図上での配置位置の所定の正確度が確保できる範囲内で、前記地図上での前記ラベルの視認性を最適化させるように、前記ラベルの配置調整を行う請求項１又は２に記載のラベル配置装置。
【請求項７】
前記配置手段は、前記ラベルを前記地点ごとに配置しない場合、前記格納手段に格納された前記位置情報及び前記ラベルに基づいて、所定のクラスタリング処理を行い、クラスタごとに前記ラベルを配置し、
前記調整手段は、前記地図上での前記クラスタの内容の所定の正確度が確保できる範囲内で、前記配置手段によって配置されたそれぞれのクラスタの前記地図上でのまとまりの良さを最適化させるように、前記クラスタの配置調整を行う請求項１に記載のラベル配置装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７ａ】
【図７ｂ】
【図７ｃ】
【図８ａ】
【図８ｂ】
【図９ａ】
【図９ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７ａ】
【図７ｂ】
【図７ｃ】
【図８ａ】
【図８ｂ】
【図９ａ】
【図９ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１０−２３７３５５（Ｐ２０１０−２３７３５５Ａ）
【公開日】平成２２年１０月２１日（２０１０．１０．２１）
【国際特許分類】
【出願番号】特願２００９−８４１３６（Ｐ２００９−８４１３６）
【出願日】平成２１年３月３１日（２００９．３．３１）
【出願人】（５０２３２４０６６）株式会社デンソーアイティーラボラトリ (332)
【Ｆターム（参考）】
【公開日】平成２２年１０月２１日（２０１０．１０．２１）
【国際特許分類】
【出願日】平成２１年３月３１日（２００９．３．３１）
【出願人】（５０２３２４０６６）株式会社デンソーアイティーラボラトリ (332)
【Ｆターム（参考）】
[ Back to top ]