(57)【要約】  この発明に係る文字列配置描画装置は、文字列の数、文字列が沿う道路ノード列および文字列の配置候補点を含む文字列データを記憶する文字列データ記憶部と、文字列データ記憶部から文字列データを取得する文字列データ取得部と、取得された文字列データから処理対象の文字列を特定する処理対象文字列特定部と、取得された文字列データから配置候補点を取得する候補点取得部と、取得された配置候補点の中から処理対象とする配置候補点を特定する処理対象候補点特定部と、文字列を配置候補点から道路ノード列に沿って配置する文字列配置部と、文字列を評価する評価関数値を算出する評価関数算出部と、算出された評価関数値のうちの最小の評価関数値および該評価関数値に対応する文字列の配置を保存する最小評価関数値保存部と、保存された配置を有する文字列を描画する文字列描画部を備えている。
2013186897.tif 000002
【特許請求の範囲】
【請求項１】
文字列の数、文字列が沿う道路ノード列および文字列の配置候補点を含む文字列データを記憶する文字列データ記憶部と、
前記文字列データ記憶部から文字列データを取得する文字列データ取得部と、
前記文字列データ取得部で取得された文字列データの中から処理対象とする文字列を特定する処理対象文字列特定部と、
前記文字列データ取得部で取得された文字列データの中から配置候補点を取得する候補点取得部と、
前記候補点取得部で取得された配置候補点の中から処理対象とする配置候補点を特定する処理対象候補点特定部と、
前記処理対象文字列特定部から送られてくる文字列を、前記処理対象候補点特定部から送られてくる配置候補点から、前記文字列データ取得部から送られてくる文字列データに含まれる道路ノード列に沿って配置する文字列配置部と、
前記文字列配置部で配置された文字列を評価する評価関数値を算出する評価関数算出部と、
前記評価関数算出部で算出された評価関数値のうちの最小の評価関数値および該評価関数値に対応する文字列の配置を保存する最小評価関数値保存部と、
前記最小評価関数値保存部によって保存された配置の文字列を描画する文字列描画部
とを備えた文字列配置描画装置。
【請求項２】
評価関数算出部は、
文字列配置部から送られてくる文字列同士の間隔により文字列の可読性を評価する文字列間隔関数値を算出する文字列間隔関数算出部と、
前記文字列配置部から送られてくる文字列が沿う道路の角度変化を評価する道路角度関数値を算出する道路角度関数算出部と、
前記文字列配置部から送られてくる文字列と表示範囲との関係を評価する表示範囲関数値を算出する表示範囲関数算出部と、
前記文字列間隔関数算出部からの文字列間隔関数値、前記道路角度関数算出部からの道路角度関数値および前記表示範囲関数算出部からの表示範囲関数値によって評価関数値を更新する評価関数値更新部
とを備えたことを特徴とする請求項１記載の文字列配置描画装置。
【請求項３】
最小評価関数値保存部は、
文字列間隔関数算出部で算出された文字列間隔関数値のうち、文字列同士の重なりを回避して文字列の可読性を高めるような最小の文字列間隔関数値を保存し、
道路角度関数算出部で算出された道路角度関数値のうち、平坦でない道路への文字列配置を回避するような最小の道路角度関数値を保存し、
表示範囲関数算出部で算出された表示範囲関数値のうち、表示範囲外への文字列配置を回避するような表示範囲関数値を保存する
ことを特徴とする請求項２記載の文字列配置描画装置。
【請求項４】
処理対象文字列特定部は、文字列データ取得部で取得された文字列データの中から配置位置を変更する文字列を選択する
ことを特徴とする請求項１記載の文字列配置描画装置。
【請求項５】
処理対象候補点特定部は、候補点取得部で取得された配置候補点の中から、表示範囲内に含まれる配置候補点を処理対象として選択する
ことを特徴とする請求項１記載の文字列配置描画装置。
【請求項６】
文字列配置部は、表示範囲の中心に文字列を移動させて配置する
ことを特徴とする請求項１記載の文字列配置描画装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、道路名称等の文字列を地図上に動的に配置する文字列配置描画装置に関する。
【背景技術】
【０００２】
従来、道路名称等の文字列を、文字列の配置を開始する点（以下、「文字列配置開始点」という）から、道路線（以下、「道路ノード列」という）に沿って配置する文字列配置機能を有する地図表示装置が知られている。【０００３】
この地図表示装置では、文字列配置開始点が適切でない場合は、
（１）文字列同士の重なり
（２）文字の表示角度の変化による可読性の低下
（３）文字列の密集による可読性の低下
（４）表示範囲の変化により文字列の一部が欠ける
などといった問題が起きる。【０００４】
そこで、上述した（１）および（２）の問題を解決するために、非特許文献１は、可読性が高い位置に文字列配置開始点を変更する技術を開示している。この技術においては、文字列同士の重複を示す関数および文字列が沿う道路ノード列の角度変化を示す関数によって構成される評価関数の値を最小化することにより、最適な文字列配置開始点が求められる。【０００５】
また、上述した（３）の問題を解決するために、特許文献１は、表示範囲の変化に応じて動的に文字列の位置を変更する技術を開示している。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−７７４２８号公報
【非特許文献】
【０００７】
【非特許文献１】Shawn Edmondson，“A General Cartographic Labeling Algorithm”，The International Journal for Geographic Information and Geovisualization, Volume 33，Number 4/ Winter 1996
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１に開示された技術を用いれば、上述した（１）および（２）の問題を解決できるが、上述した（３）の問題、つまり文字列の密集による可読性低下を避けることはできない。また、特許文献１に開示された技術では、上述した（１）〜（３）の問題を考慮して文字列の配置位置を決めている訳ではないので、これらの問題の発生を避けることはできない。【０００９】
このように、上述した（１）〜（４）の問題のうち、一部の問題を避ける技術は知られているものの、（１）〜（４）の問題全てを同時に避けることはできない。【００１０】
この発明は、上述した（１）〜（４）の問題全てを避けるためになされたものであり、文字列の重複、文字列が沿う道路の角度変化だけでなく、文字列の密集度合い、文字列と表示範囲の関係も加味して文字列を最適な位置に配置できる文字列配置描画装置を提供することを課題とする。
【課題を解決するための手段】
【００１１】
この発明に係る文字列配置描画装置は、文字列の数、文字列が沿う道路ノード列および文字列の配置候補点を含む文字列データを記憶する文字列データ記憶部と、文字列データ記憶部から文字列データを取得する文字列データ取得部と、文字列データ取得部で取得された文字列データの中から処理対象とする文字列を特定する処理対象文字列特定部と、文字列データ取得部で取得された文字列データの中から配置候補点を取得する候補点取得部と、候補点取得部で取得された配置候補点の中から処理対象とする配置候補点を特定する処理対象候補点特定部と、処理対象文字列特定部から送られてくる文字列を、処理対象候補点特定部から送られてくる配置候補点から、文字列データ取得部から送られてくる文字列データに含まれる道路ノード列に沿って配置する文字列配置部と、文字列配置部で配置された文字列を評価する評価関数値を算出する評価関数算出部と、評価関数算出部で算出された評価関数値のうちの最小の評価関数値および該評価関数値に対応する文字列の配置を保存する最小評価関数値保存部と、最小評価関数値保存部によって保存された配置の文字列を描画する文字列描画部を備えている。
【発明の効果】
【００１２】
この発明に係る文字列配置描画装置によれば、文字列の重複、文字列が沿う道路の角度変化だけでなく、文字列の密集度合い、文字列と表示範囲の関係も加味して文字列を最適な位置に配置できる。
【図面の簡単な説明】
【００１３】
【図１】この発明の実施の形態１に係る文字列配置描画装置の構成を示すブロック図である。
【図２】この発明の実施の形態１に係る文字列配置描画装置の動作を示すフローチャートである。
【図３】この発明の実施の形態１に係る文字列配置描画装置で使用される道路ノード列、配置候補点および時刻ｔ＋αにおける表示範囲の関係を示す図である。
【図４】この発明の実施の形態１に係る文字列配置描画装置で使用される時刻ｔにおける表示範囲、道路ノード列、および、文字列の関係を示す図である。
【図５】この発明の実施の形態１に係る文字列配置描画装置で使用される時刻ｔ＋αにおける表示範囲と文字列の関係を示す図である。
【図６】この発明の実施の形態１に係る文字列配置描画装置において、配置候補点Ｃ（２）から道路ノード列に沿って文字列を配置する様子を示す図である。
【図７】図２のステップＳＴ１９で行われる評価関数処理の詳細を示すフローチャートである。
【図８】この発明の実施の形態１に係る文字列配置描画装置における文字列間隔関数値の分布の例を示す図である。
【図９】この発明の実施の形態１に係る文字列配置描画装置における道路角度関数値の分布の例を示す図である。
【図１０】この発明の実施の形態１に係る文字列配置描画装置における表示範囲関数値の分布の例を示す図である。
【図１１】この発明の実施の形態１に係る文字列配置描画装置において文字列を配置候補点Ｃ（３）から配置した例を示す図である。
【図１２】この発明の実施の形態１に係る文字列配置描画装置において文字列を配置候補点Ｃ（４）から配置した例を示す図である。
【図１３】この発明の実施の形態１に係る文字列配置描画装置において文字列を配置候補点Ｃ（５）から配置した例を示す図である。
【図１４】この発明の実施の形態１に係る文字列配置描画装置において、各配置候補点から配置した文字列と評価関数値の対応を示す図である。
【図１５】一般の文字列配置描画装置が有する道路名称等の文字列を文字列配置開始点から道路線に沿って配置する機能を説明するための図である。
【図１６】一般の文字列配置描画装置で発生する文字列同士の重なりを説明するための図である。
【図１７】一般の文字列配置描画装置で発生する文字の表示角度の変化による可読性の低下を説明するための図である。
【図１８】一般の文字列配置描画装置で発生する文字列の密集による可読性の低下を説明するための図である。
【図１９】一般の文字列配置描画装置で発生する表示範囲の変化により文字列の一部が欠ける様子を説明するための図である。
【図２０】非特許文献１に開示された文字列同士の重複を示す関数を説明するための図である。
【図２１】非特許文献１に開示された文字列が沿う道路ノード列の角度変化を示す関数を説明するための図である。
【図２２】特許文献１に開示された技術を用いて文字列の配置位置を変更する例を示す図である。
【発明を実施するための形態】
【００１４】
以下、この発明の実施の形態を、図面を参照しながら詳細に説明する。
実施の形態１．
図１は、この発明の実施の形態１に係る文字列配置描画装置の構成を示すブロック図である。この文字列配置描画装置は、文字列データ記憶部１１、文字列データ取得部１２、表示範囲データ記憶部１３、処理対象文字列特定部１４、候補点取得部１５、処理対象候補点特定部１６、文字列配置部１７、評価関数算出部１８、最小評価関数値保存部１９、文字列描画部２０、最小評価関数値データ記憶部２１および文字列配置データ記憶部２２を備えている。
【００１５】
文字列データ記憶部１１は、文字列データを記憶する。文字列データは、文字列の数、各文字列の文字数、各文字の横幅および縦幅、文字列が沿う道路ノード列、および、各文字列の配置候補点を含む。
【００１６】
文字列データ取得部１２は、文字列データ記憶部１１から文字列データを取得する。この文字列データ取得部１２で取得された文字列データは、処理対象文字列特定部１４、候補点取得部１５および文字列配置部１７に送られる。
【００１７】
表示範囲データ記憶部１３は、文字列を表示する範囲を表示範囲データとして記憶する。この表示範囲データ記憶部１３に記憶されている表示範囲データは、処理対象文字列特定部１４および評価関数算出部１８を構成する表示範囲関数算出部２５（詳細は後述）によって読み出される。
【００１８】
処理対象文字列特定部１４は、文字列データ取得部１２から送られてきた文字列データの中の文字列と、表示範囲データ記憶部１３から読み出した表示範囲データによって示される表示範囲との関係から、配置位置の変更が必要な文字列を選択して特定する。この処理対象文字列特定部１４で特定された文字列は、処理対象文字列として候補点取得部１５および文字列配置部１７に送られる。この処理対象文字列特定部１４で文字列を選択することにより、処理負荷の軽減が可能になっている。
【００１９】
候補点取得部１５は、文字列データ取得部１２から送られてくる文字列データに含まれる配置候補点の中から、処理対象文字列特定部１４から送られてくる処理対象文字列（配置位置の変更処理の対象となる文字列）の配置候補点を取得する。この候補点取得部１５で取得された配置候補点は、処理対象候補点特定部１６に送られる。
【００２０】
処理対象候補点特定部１６は、候補点取得部１５から送られてきた配置候補点の中から処理対象とする配置候補点、具体的には、表示範囲内に含まれる配置候補点を選択して特定する。この処理対象候補点特定部１６で特定された配置候補点は、文字列配置部１７に送られる。この処理対象候補点特定部１６で配置候補点を選択することにより、処理負荷の軽減が可能になっている。
【００２１】
文字列配置部１７は、処理対象文字列特定部１４から送られてくる処理対象文字列を、処理対象候補点特定部１６から送られてくる配置候補点から、文字列データ取得部１２から送られてくる文字列データに含まれる道路ノード列に沿って配置する。この文字列配置部１７で配置された文字列は、評価関数算出部１８に送られる。
【００２２】
評価関数算出部１８は、文字列配置部１７から送られてくる配置された文字列の可読性を評価するための評価関数を算出する。この評価関数算出部１８で算出された評価関数は、最小評価関数値保存部１９に送られる。
【００２３】
ここで、評価関数算出部１８について、さらに詳細に説明する。評価関数算出部１８は、文字列間隔関数算出部２３、道路角度関数算出部２４、表示範囲関数算出部２５および評価関数値更新部２６を備えている。
【００２４】
文字列間隔関数算出部２３は、文字列配置部１７から送られてくる文字列同士の間隔により文字列の可読性を評価する関数値（以下、「文字列間隔関数値」という）を算出する。この文字列間隔関数算出部２３で算出された文字列間隔関数値は、評価関数値更新部２６に送られる。
【００２５】
道路角度関数算出部２４は、文字列配置部１７から送られてくる文字列を配置する道路の角度変化を評価する関数値（以下、「道路角度関数値」という）を算出する。この道路角度関数算出部２４で算出された道路角度関数値は、評価関数値更新部２６に送られる。
【００２６】
表示範囲関数算出部２５は、表示範囲データ記憶部１３から読み出した表示範囲データによって示される表示範囲と、文字列配置部１７から送られてくる文字列の関係を評価する関数値（以下、「表示範囲関数値」という）を算出する。この表示範囲関数算出部２５で算出された表示範囲関数値は、評価関数値更新部２６に送られる。
【００２７】
評価関数値更新部２６は、文字列間隔関数算出部２３から送られてきた文字列間隔関数値、道路角度関数算出部２４から送られてきた道路角度関数値および表示範囲関数算出部２５から送られてきた表示範囲関数値によって評価関数値を更新する。この評価関数値更新部２６で更新された評価関数値は、最小評価関数値保存部１９に送られる。
【００２８】
最小評価関数値保存部１９は、評価関数算出部１８から送られてきた評価関数値のうちの最も小さい評価関数値を最小評価関数値データ記憶部２１に保存する。具体的には、最小評価関数値保存部１９は、文字列間隔関数算出部２３で算出された文字列間隔関数値のうち、文字列同士の重なりを回避して文字列の可読性を高めることができるものを保存し、道路角度関数算出部２４で算出された道路角度関数値のうち、平坦でない道路への文字列配置を回避するような最小の道路角度関数値を保存し、さらに、表示範囲関数算出部２５で算出された表示範囲関数値のうち、表示範囲外への文字列配置を回避するような表示範囲関数値を保存する。また、最小評価関数値保存部１９は、最小評価関数値データ記憶部２１に保存した評価関数値に対応する文字列の配置、つまり、最も小さい評価関数値が算出された時の文字列の配置を文字列配置データ記憶部２２に保存する。
【００２９】
文字列描画部２０は、最小評価関数値保存部１９が評価関数値および文字列の配置を保存した場合に、文字列配置データ記憶部２２から文字列を読み出して描画する。
【００３０】
次に、上記のように構成される実施の形態１に係る文字列配置描画装置の動作を説明する。図２は、文字列配置描画装置の動作を示すフローチャートである。なお、この図２に示す処理は、所定時間間隔またはフレーム毎に行うことができるが、ここでは、一定時間αの間隔で行うものとし、前回に処理を行った時刻をｔとする。
【００３１】
以下においては、文字列データは、文字列『ＧＯＯＤ』および文字列『ＮＥＥＤ』を含み、各文字の横幅および縦幅はそれぞれ１０および２０とし、文字列『ＧＯＯＤ』が沿う道路ノード列はＰ（１）＝（１００，−２０）、Ｐ（２）＝（１００，１２５）、Ｐ（３）＝（２２０，１２５）とし、文字列『ＮＥＥＤ』が沿う道路ノード列はＰ（４）＝（０，７５）、Ｐ（５）＝（２００，７５）とする。
【００３２】
また、評価関数計算用のパラメータＲＯＡＤ＿ＡＮＧＬＥ＿ＣＯＶＡＲＩＡＮＣＥ（以下、「ＲＣ」と略する）を下記（１）式とし、ＬＡＢＥＬ＿ＯＶＥＲＬＡＰ＿ＣＯＶＡＲＩＡＮＣＥ（以下、「ＬＣ」と略する）を下記（２）式とし、ＲＯＡＤ＿ＡＮＧＬＥ＿ＳＣＡＬＥ（以下、「ＲＳ」と略する）を「１」とし、ＬＡＢＥＬ＿ＯＶＥＲＬＡＰ＿ＳＣＡＬＥ（以下、「ＬＳ」と略する）を「１」とし、ＤＩＳＰＬＡＹ＿ＡＲＥＡ＿ＳＣＡＬＥ（以下、「ＤＳ」と略する）を「４」とし、ＤＩＳＰＬＡＹ＿ＡＲＥＡ＿ＦＵＮＣＴＩＯＮ＿ＳＣＡＬＥ（以下、「ＤＦＳ」と略する）を「０．１」とする。
2013186897.tif 000003
【００３３】
また、時刻ｔにおける表示範囲をＲｔ（１）＝（０，−２０）、Ｒｔ（２）＝（２００，−２０）、Ｒｔ（３）＝（２００，１８０）、Ｒｔ（４）＝（０，１８０）とし、時刻ｔから一定時間αだけ経過した時刻ｔ＋αにおける表示範囲をＲｔ＋α（１）＝（０，０）、Ｒｔ＋α（２）＝（２００，０）、Ｒｔ＋α（３）＝（２００，２００）、Ｒｔ＋α（４）＝（０，２００）とする。
【００３４】
また、文字列『ＧＯＯＤ』の配置候補点をＣ（１）＝（１００，−２０）、Ｃ（２）＝（１００，６０）、Ｃ（３）＝（１００，１１５）、Ｃ（４）＝（１２０，１２５）、Ｃ（５）＝（１８０，１２５）とする。
【００３５】
また、時刻ｔにおける文字列『ＧＯＯＤ』の配置は、Ｌｔ（１）＝（１００，−２０）、Ｌｔ（２）＝（１００，−１０），Ｌｔ（３）＝（１００，０）、Ｌｔ（４）＝（１００，１０）とする。Ｌｔ（１）、Ｌｔ（２）、Ｌｔ（３）およびＬｔ（４）は、文字列『ＧＯＯＤ』を構成する文字『Ｇ』、『Ｏ』、『Ｏ』および『Ｄ』の左下座標をそれぞれ示し、文字は道路に沿って配置されている。
【００３６】
同様に、時刻ｔにおける文字列『ＮＥＥＤ』の配置は、Ｌｔ（５）＝（８０，７５）、Ｌｔ（６）＝（９０，７５）、Ｌｔ（７）＝（１００，７５）、Ｌｔ（８）＝（１１０，７５）とする。Ｌｔ（５）、Ｌｔ（６）、Ｌｔ（７）およびＬｔ（８）は、文字列『ＮＥＥＤ』を構成する文字『Ｎ』、『Ｅ』、『Ｅ』および『Ｄ』の左下座標をそれぞれ示し、文字は道路に沿って配置されている。
【００３７】
図３は、道路ノード列Ｐ（１）〜Ｐ（３）と、文字列『ＧＯＯＤ』の配置候補点Ｃ（１）〜Ｃ（５）と、時刻ｔ＋αにおける表示範囲との関係を示している。また、図４は、時刻ｔにおける表示範囲と、道路ノード列Ｐ（１）〜Ｐ（３）と、文字列『ＧＯＯＤ』との関係を示している。
【００３８】
この文字列配置描画装置においては、時刻ｔ＋αになったタイミングで、図２のフローチャートに示す処理が開始される。時刻ｔにおける表示範囲Ｒｔ（１）〜Ｒｔ（４）は、時刻ｔ＋αにおいて表示範囲Ｒｔ＋α（１）〜Ｒｔ＋α（４）に変化する。図５は、時刻ｔ＋αにおける表示範囲Ｒｔ＋α（１）〜Ｒｔ＋α（４）と文字列の関係を示している。なお、図５の中の文字列の配置位置は、図２のフローチャートに示す処理が実行される前の位置である。
【００３９】
処理が開始されると、まず、文字列データが取得される（ステップＳＴ１１）。すなわち、文字列データ取得部１２は、文字列データ記憶部１１から文字列データを取得する。この場合、文字列『ＧＯＯＤ』、文字列『ＮＥＥＤ』、これらの文字列配置に関わる配置候補点、および、道路ノード列が取得される。この取得された文字列データは、処理対象文字列特定部１４、候補点取得部１５および文字列配置部１７に送られる。
【００４０】
次いで、処理対象文字列の特定が行われる（ステップＳＴ１２）。すなわち、処理対象文字列特定部１４は、文字列データ取得部１２から送られてきた文字列データの中の文字列と、表示範囲データ記憶部１３から読み出した表示範囲データによって示される表示範囲との関係から、配置位置の変更が必要な文字列を特定する。具体的には、処理対象文字列特定部１４は、以下の条件を満たす文字列を特定する。
＜条件１＞時刻ｔでは配置不可能であったが、時刻ｔ＋αになって表示範囲内に配置可能になった文字列
＜条件２＞一部または全部が表示範囲外になった文字列
【００４１】
図５に示した例の場合、文字列『ＧＯＯＤ』と『ＮＥＥＤ』のうち、文字列『ＧＯＯＤ』のみが上述した条件に該当する。すなわち、文字列『ＧＯＯＤ』は、時刻ｔ＋αにおいて、１文字目と２文字目が表示範囲外になるため、条件２に該当する。
【００４２】
処理対象文字列が特定されると、次いで、ステップＳＴ１３とステップＳＴ２４との間の処理が処理対象文字列数の分だけ繰り返し実行され、特定された文字列の配置位置が変更される。
【００４３】
この繰り返し処理では、まず、配置候補点が取得される（ステップＳＴ１４）。すなわち、候補点取得部１５は、ステップＳＴ１１で文字列データ取得部１２によって取得された文字列データに含まれる配置候補点の中から、処理対象文字列特定部１４から送られてくる処理対象文字列（配置位置の変更処理の対象となる文字列）の配置候補点を取得する。図５に示した例の場合、文字列『ＧＯＯＤ』の配置候補点Ｃ（１）〜Ｃ（５）（図３参照）が取得される。
【００４４】
次いで、処理対象候補点が特定される（ステップＳＴ１５）。すなわち、処理対象候補点特定部１６は、候補点取得部１５から送られてきた配置候補点の中から配置候補点を特定し、この特定した配置候補点を文字列配置部１７に送る。上記配置候補点の特定は、具体的には以下の条件３を満たすか否かを判定することにより行うことができる。
＜条件３＞表示範囲内に含まれる配置候補点（表示範囲よりも大きな範囲を用いることもできる）
【００４５】
なお、この実施の形態１では、表示範囲内の配置候補点を特定する処理を行うものとして説明するが、上記条件３の括弧内に示すように、表示範囲よりも大きな範囲で処理対象文字列の配置候補点を特定することもできる。
【００４６】
図５に示した例の場合、文字列『ＧＯＯＤ』の配置候補点Ｃ（１）〜Ｃ（５）のうち、Ｃ（１）は表示範囲外となるため、処理対象文字列の配置候補点は、Ｃ（２）〜Ｃ（５）となる。
【００４７】
次いで、最小評価関数値が最大値（ＭＡＸ）に設定される（ステップＳＴ１６）。すなわち、評価関数算出部１８は、以下で算出する最小評価関数値を最大値に初期化する。その後、ステップＳＴ１７とステップＳＴ２３との間の処理を、処理対象とする候補点（処理候補点）の数の分だけ繰り返して実行し、処理対象文字列の配置候補点毎の処理が行われる。
【００４８】
具体的には、まず、文字列の配置が行われる（ステップＳＴ１８）。すなわち、文字列配置部１７は、処理対象文字列特定部１４から送られてくる処理対象の文字列を、処理対象候補点特定部１６から送られてくる配置候補点から、文字列データ取得部１２から送られてくる文字列データに含まれる道路ノード列に沿って配置する。上述した例の場合、まず、配置候補点Ｃ（２）から道路ノード列に沿って文字列が配置される。この様子を図６に示す。文字『Ｇ』、『Ｏ』、『Ｏ』および『Ｄ』の中心座標は、それぞれ（１１０，６５）、（１１０，７５）、（１１０，８５）および（１１０，９５）である。
【００４９】
次いで、評価関数算出が行われる（ステップＳＴ１９）。すなわち、評価関数算出部１８は、評価関数を算出する。評価関数を（３）式に示す。（３）式中の文字列間隔関数値、道路角度関数値および表示範囲関数値は、文字列間隔関数算出部２３、道路角度関数算出部２４および表示範囲関数算出部２５においてそれぞれ算出されて評価関数値更新部２６に送られる。ここで、文字列間隔関数値は、文字列同士の重なり度合いを示す値である。また、道路角度関数値は、文字列の沿う道路の角度変化を示す値である。また、表示範囲関数値は、文字列と表示範囲の関係を示す値である。
【００５０】
評価関数値更新部２６は、文字列間隔関数算出部２３、道路角度関数算出部２４および表示範囲関数算出部２５からそれぞれ送られてくる文字列間隔関数値、道路角度関数値および表示範囲関数値を加算し、最終的に（３）式で示される評価関数値Ｆが算出される。
2013186897.tif 000004
【００５１】
ここで、ステップＳＴ１９において、評価関数算出部１８で行われる評価関数算出処理の詳細を、図７に示すフローチャートを参照しながら説明する。
【００５２】
評価関数算出処理では、まず、評価関数値Ｆが「０」に初期化される（ステップＳＴ３１）。その後、ステップＳＴ３２とステップＳＴ３７との間の処理が文字数分だけ繰り返して実行され、評価関数が算出される。
【００５３】
具体的には、まず、文字列間隔関数が算出される（ステップＳＴ３３）。すなわち、文字列間隔関数算出部２３は、文字列間隔関数値を求め、評価関数値更新部２６に送る。文字列間隔関数値は、下記（４）式により求めることができる。（４）式中のＬａｂｅｌＮｕｍは、既に配置されている文字列数、ＣｈａｒａｃｔｅｒＮｕｍｊはｊ番目の文字列に含まれる文字数を示す。また、Ｋ（ｕ，Ａ）は、下記（５）式に示すガウスカーネルを示す。ｘnは処理対象文字列のｎ番目の文字の中心座標、ｘ’ｊｉはｊ番目の文字列中のｉ番目の文字の中心座標を示す。
2013186897.tif 000005
【００５４】
上述した例の場合、既に配置されている文字列は『ＮＥＥＤ』のみであるため、ＬａｂｅｌＮｕｍ＝１となる。また、文字列『ＮＥＥＤ』の文字数は４であるため、ＣｈａｒａｃｔｅｒＮｕｍ1は４となる。また、処理対象文字列の１番目の文字（ｎ＝１）の処理であるため、ｘ1＝（１１０，６５）である。これらを用いて（４）式を計算すると、文字列間隔関数値は、１．６６４９となる。
【００５５】
なお、この例の場合の文字列間隔関数値の分布は、図８に示すようになり、既に配置されている文字列『ＮＥＥＤ』の付近に高い値を有する。
【００５６】
次いで、道路角度関数が算出される（ステップＳＴ３４）。すなわち、道路角度関数算出部２４は、道路角度関数値を求め、評価関数値更新部２６に送る。道路角度関数値は、下記（６）式により求めることができる。（６）式中のＲｏａｄＮｕｍは、始点・終点以外の道路のノード数、ｘ”ｉはｉ番目のノードの位置を示す。また、ＲｏａｄＡｎｇｌｅは、道路ノード列の角度変化をラジアンで示したものである。
2013186897.tif 000006
【００５７】
上述した例の場合、文字列『ＧＯＯＤ』が沿う道路ノード列の、始点・終点以外の道路ノード数は１であるため、ＲｏａｄＮｕｍ＝１となり、始点・終点以外のノードはＰ（２）となる。また、角度Ｐ（１）Ｐ（２）Ｐ（３）はπ／２であるため、ＲｏａｄＡｎｇｌｅ＝π／２となる。この際、ＲｏａｄＡｎｇｌｅは、π以下の値を取るようにする。これらを用いて（６）式を計算すると、道路角度関数値は、１．３４０４×ｅ−１６となる。
【００５８】
なお、この例の場合の道路角度関数値の分布は、図９に示すようになり、始点・終点以外のノードＰ（２）の位置にピークを有する。
【００５９】
次いで、表示範囲関数が算出される（ステップＳＴ３５）。すなわち、表示範囲関数算出部２５は、表示範囲関数値を求め、評価関数値更新部２６に送る。表示範囲関数値は、下記（７）式により求めることができる。（７）式中のｄｉｓｔｎ１は処理対象文字列のｎ番目の文字の中心座標と、表示範囲の左辺との距離、ｄｉｓｔｎ２、ｄｉｓｔｎ３、およびｄｉｓｔｎ４は、同様に、ｎ番目の文字の中心座標と、表示範囲の上辺、右辺および下辺との距離をそれぞれ示す。また、Ｋ’（Ａ，Ｂ）は、下記（８）式に示すシグモイド関数、αｎｉは、下記（９）式に示すように、文字列の位置と表示範囲の位置関係により変化する値である。
2013186897.tif 000007
2013186897.tif 000008
2013186897.tif 000009
【００６０】
上述した例の場合、ｘ1＝（１１０，６５）は左辺の右、上辺の下、右辺の左、下辺の上に存在するため、αｎ１〜αｎ４の値は全て−１になる。また、左辺、上辺、右辺、下辺との距離ｄｉｓｔ１１〜ｄｉｓｔ１４は、以下に示す値となる。
・ｄｉｓｔ１１＝１１０
・ｄｉｓｔ１２＝６５
・ｄｉｓｔ１３＝９０
・ｄｉｓｔ１４＝１３５
これらを用いて（７）式を計算すると、０．００６６となる。
【００６１】
なお、この場合の表示範囲関数値の分布は、図１０に示すようになり、表示範囲内は低い値を有し、表示範囲外は高い値を有する。
【００６２】
次いで、評価関数の更新が行われる（ステップＳＴ３６）。すなわち、評価関数値更新部２６は、文字列間隔関数算出部２３から送られてきた文字列間隔関数値、道路角度関数算出部２４から送られてきた道路角度関数値および表示範囲関数算出部２５から送られてきた表示範囲関数値を用いて（３）式のシグマ（Σ）内を計算し、評価関数値Ｆを更新する。その結果、評価関数値Ｆ＝Ｆ＋ｌｏｇ（１．６６４９）＋ｌｏｇ（１．３４０４×ｅ−１６）＋ｌｏｇ（０．００６６）となり、評価関数値Ｆは−１３．７２５７となる。
【００６３】
これらの処理が文字毎に繰り返されて、評価関数値Ｆが更新され、配置候補点Ｃ（２）から配置された文字列の評価関数値が求められる。ここで求められる、評価関数値は−７３．２０９６となる。
【００６４】
その後、図２のフローチャートに示す処理に戻り、評価関数値が最小であるかどうか、つまり「最小評価関数値＞評価関数値」であるかどうかが調べられる（ステップＳＴ２０）。このステップＳＴ２０において、評価関数値が最小であることが判断されると、文字列配置の保存が行われる（ステップＳＴ２１）。すなわち、最小評価関数値保存部１９は、その時点の文字列の配置を、文字列配置データ記憶部２２に保存する。
【００６５】
次いで、最小評価関数値の更新が行われる（ステップＳＴ２２）。すなわち、最小評価関数値保存部１９は、評価関数値は最小であるため、最小評価関数値データ記憶部２１に保存されている評価関数値を、評価関数算出部１８で算出された評価関数値に置き換えることにより更新する。
【００６６】
一方、上記ステップＳＴ２０において、評価関数値が最小でないことが判断されると、ステップＳＴ２１およびステップＳＴ２２の処理はスキップされる。
【００６７】
以下同様にして、図１１に示すような配置候補点Ｃ（３）から配置した文字列、図１２に示すような配置候補点Ｃ（４）から配置した文字列、および、図１３に示すような配置候補点Ｃ（５）から配置した文字列に対しても同様に評価関数値を計算し、評価関数値が最小か否かを判定する。図１４に各配置候補点から配置した文字列と、評価関数値の対応を示す。
【００６８】
上述したステップＳＴ１３〜ステップＳＴ２４の間の処理が終了すると、次いで、文字列の描画が行われる（ステップＳＴ２５）。すなわち、文字列描画部２０は、配置候補点Ｃ（４）から配置した文字列の評価関数値が最も低いため、Ｃ（４）から配置した文字列を文字列配置データ記憶部１２から読み出して描画する。その後、処理は終了する。
【００６９】
文字列配置描画装置は、一般に、図１５に示すように、道路名称等の文字列を、文字列の配置を開始する点（文字列配置開始点）から、道路線（道路ノード列）に沿って配置する機能を有するが、背景技術の欄で示したように、文字列配置開始点が適切でないことに起因する４つの問題、つまり
（１）図１６に示すような文字列同士の重なり
（２）図１７に示すような文字の表示角度の変化による可読性の低下
（３）図１８に示すような文字列の密集による可読性の低下
（４）図１９に示すような表示範囲の変化により文字列の一部が欠ける
という問題を有する。しかしながら、上述した実施の形態１に係る文字列配置描画装置によれば、このような問題を解消できる。
【００７０】
また、上述した非特許文献１に開示された技術では、図２０に示すような文字列同士の重複を示す関数と、図２１に示すような文字列が沿う道路ノード列の角度変化を示す関数で構成された（１０）式に示す評価関数値ｆを最小化することにより、最適な文字列配置開始点が求められる。
2013186897.tif 000010
なお、（１０）式中のα1とα2は、ｏｖｅｒｌａｐ（ｉ）とｆｌａｔｎｅｓｓ（ｉ）の値を調整するパラメータであり、Ｓｔｒｉｎｇ＿Ｎｕｍは文字列数を示す。
【００７１】
この評価関数ｆを用いれば、（１）文字列同士の重複と（２）文字列が沿う道路の角度変化による可読性低下という問題は回避できるが、（３）文字列の密集による可読性低下という問題を回避できない。しかしながら、この実施の形態１に係る文字列配置描画装置によれば、（３）文字列の密集による可読性低下という問題をも回避できる。
【００７２】
また、（４）の問題を解決するために、特許文献１に開示された技術では、表示範囲の変化に応じて動的に文字列の位置を変更することができるが、（１）〜（３）の問題は考慮されていない。図２２は特許文献１に開示された技術を用いて、文字列の配置位置を変更する例を示す。図２２（ａ）は、時刻ｔにおける文字列の配置を示す。また、図２２（ｂ）は、時刻ｔから時間αだけ経過し、表示範囲が変化したことを示す。表示範囲の変化により、文字列『東海道』は、配置位置が変更される。図２２（ｂ）は、特許文献１に開示された技術では、（１）文字列同士の重複を加味して位置を変更しないため、他の文字列と重なる。これに対し、実施の形態１に係る文字列配置描画装置によれば、このような問題を回避できる。
【００７３】
以上説明したように、実施の形態１に係る文字列配置描画装置の特徴は、文字列『ＮＥＥＤ』との重なりがある配置候補点Ｃ（２）から配置した文字列、道路の角度変化が大きく可読性が低いＣ（３）から配置した文字列、表示範囲外に配置される配置候補点Ｃ（５）から配置した文字列に比べ、これらの問題がない配置候補点Ｃ（４）から配置した文字列の評価関数値が最も低くなっている点である。背景技術の欄に示した（１）〜（４）の問題がない場合、評価関数値が低くなり、（１）〜（４）のいずれかの問題がある場合には、評価関数値が高くなるので、最適な位置に文字列を配置することができる。
【００７４】
なお、文字列配置部１７は、文字列の重なり等を考慮しながら、表示範囲の中心に文字列を移動させて配置するように構成できる。この構成によれば、文字列の配置位置の変更回数を減らすことができる。
【００７５】
なお、本願発明はその発明の範囲内において、実施の形態の任意の構成要素の変形、もしくは実施の形態の任意の構成要素の省略が可能である。
【産業上の利用可能性】
【００７６】
この発明は、文字列の可読性を向上させるとともに、文字の位置決めを高速に行うことができるので、カーナビゲーションシステムまたは携帯機器などで行われる地図表示に好適である。
【符号の説明】
【００７７】
１１  文字列データ記憶部、１２  文字列データ取得部、１３  表示範囲データ記憶部、１４  処理対象文字列特定部、１５  候補点取得部、１６  処理対象候補点特定部、１７  文字列配置部、１８  評価関数算出部、１９  最小評価関数値保存部、２０  文字列描画部、２１  最小評価関数値データ記憶部、２２  文字列配置データ記憶部、２３  文字列間隔関数算出部、２４  道路角度関数算出部、２５  表示範囲関数算出部、２６  評価関数値更新部。
【図１】
2013186897.tif 000011
【図２】
2013186897.tif 000012
【図３】
2013186897.tif 000013
【図４】
2013186897.tif 000014
【図５】
2013186897.tif 000015
【図６】
2013186897.tif 000016
【図７】
2013186897.tif 000017
【図８】
2013186897.tif 000018
【図９】
2013186897.tif 000019
【図１０】
2013186897.tif 000020
【図１１】
2013186897.tif 000021
【図１２】
2013186897.tif 000022
【図１３】
2013186897.tif 000023
【図１４】
2013186897.tif 000024
【図１５】
2013186897.tif 000025
【図１６】
2013186897.tif 000026
【図１７】
2013186897.tif 000027
【図１８】
2013186897.tif 000028
【図１９】
2013186897.tif 000029
【図２０】
2013186897.tif 000030
【図２１】
2013186897.tif 000031
【図２２】
2013186897.tif 000032
【手続補正書】
【提出日】平成26年5月29日(2014.5.29)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
この発明に係る文字列配置描画装置は、文字列を、文字列の配置候補点から道路ノード列に沿って配置する文字列配置部と、文字列配置部で配置された文字列同士の間隔により文字列の可読性を評価する評価関数値を算出する評価関数算出部と、評価関数算出部で算出された評価関数値を用いて文字列を描画する文字列描画部を備えている。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
文字列を、当該文字列の配置候補点から道路ノード列に沿って配置する文字列配置部と、
前記文字列配置部で配置された文字列同士の間隔により前記文字列の可読性を評価する評価関数値を算出する評価関数算出部と、
前記評価関数算出部で算出された評価関数値を用いて前記文字列を描画する文字列描画部と、
を備えた文字列配置描画装置。
【請求項２】
前記評価関数算出部は、前記文字列が沿う道路の角度変化を評価する道路角度関数値を算出する道路角度関数算出部と、前記文字列と表示範囲との関係を評価する表示範囲関数値を算出する表示範囲関数算出部とを具備してなり、前記道路角度関数値および前記表示範囲関数値を用いて前記評価関数値を更新する評価関数値更新部を設けたことを特徴とする請求項１記載の文字列配置描画装置。
【請求項３】
前記評価関数算出部と前記文字列描画部間に、前記評価関数値および当該評価関数値に対応する前記文字列の配置を保存する評価関数値保存部を設けたことを特徴とする請求項１記載の文字列配置描画装置。
【請求項４】
前記評価関数値保存部は、文字列同士の重なりを回避して前記文字列の可読性を高めるような文字列間隔関数値を保存し、前記文字列が沿う道路の角度変化を評価する道路角度関数値のうち平坦でない道路への文字列配置を回避するような前記道路角度関数値を保存すると共に、前記表示範囲関数値のうち前記表示範囲外への前記文字列配置を回避するような前記表示範囲関数値を保存することを特徴とする請求項３記載の文字列配置描画装置。
【請求項５】
文字列データを記憶する文字列データ記憶部から処理対象とする前記文字列を取得して特定すると共に、前記文字列の配置位置を特定する処理対象文字列特定部を設けたことを特徴とする請求項１記載の文字列配置描画装置。
【請求項６】
前記文字列データは、前記文字列の数、前記文字列が沿う道路ノード列および前記文字列の配置候補点を含むものであることを特徴とする請求項５記載の文字列配置描画装置。
【請求項７】
前記表示範囲内に含まれる前記配置候補点を処理対象として選択する処理対象候補点特定部を設けたことを特徴とする請求項２記載の文字列配置描画装置。
【請求項８】
前記文字列配置部は、表示範囲の中心に前記文字列を移動させて配置することを特徴とする請求項１記載の文字列配置描画装置。
【手続補正書】
【提出日】平成27年7月24日(2015.7.24)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
この発明に係る文字列配置描画装置は、文字列を、文字列の配置候補点から道路ノード列に沿って配置する文字列配置部と、文字列配置部で配置された文字列同士の間隔による前記文字列の可読性、および文字列と表示範囲との関係を評価する評価関数値を算出する評価関数算出部と、評価関数算出部で算出された評価関数値を用いて文字列を描画する文字列描画部を備えている。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
文字列を、当該文字列の配置候補点から道路ノード列に沿って配置する文字列配置部と、
前記文字列配置部で配置された文字列同士の間隔による前記文字列の可読性、および前記文字列と表示範囲との関係を評価する評価関数値を算出する評価関数算出部と、
前記評価関数算出部で算出された評価関数値を用いて前記文字列を描画する文字列描画部と、
を備えた文字列配置描画装置。
【請求項２】
前記評価関数算出部は、前記文字列が沿う道路の角度変化を評価する評価関数値を算出し、
前記文字列描画部は、前記文字列同士の間隔による前記文字列の可読性、前記文字列と表示範囲との関係、および前記文字列が沿う道路の角度変化を評価する前記評価関数値を用いて前記文字列を描画することを特徴とする請求項１記載の文字列配置描画装置。
【請求項３】
前記評価関数値を更新する評価関数値更新部を設けたことを特徴とする請求項１記載の文字列配置描画装置。
【請求項４】
前記評価関数算出部と前記文字列描画部間に、最小の評価関数値および当該評価関数値に対応する前記文字列の配置を保存する評価関数値保存部を設けたことを特徴とする請求項１記載の文字列配置描画装置。
【請求項５】
前記評価関数値保存部は、文字列同士の重なりを回避して前記文字列の可読性を高めるような評価関数値を保存し、前記文字列が沿う道路の角度変化を評価する評価関数値のうち平坦でない道路への文字列配置を回避するような評価関数値を保存すると共に、前記文字列と表示範囲との関係を評価する評価関数値のうち前記表示範囲外への前記文字列配置を回避するような評価関数値を保存することを特徴とする請求項４記載の文字列配置描画装置。
【請求項６】
文字列データを記憶する文字列データ記憶部から処理対象とする前記文字列を取得して特定すると共に、前記文字列の配置位置を特定する処理対象文字列特定部を設けたことを特徴とする請求項１記載の文字列配置描画装置。
【請求項７】
前記文字列データは、前記文字列の数、前記文字列が沿う道路ノード列および前記文字列の配置候補点を含むものであることを特徴とする請求項６記載の文字列配置描画装置。
【請求項８】
前記表示範囲内に含まれる前記配置候補点を処理対象として選択する処理対象候補点特定部を設けたことを特徴とする請求項１記載の文字列配置描画装置。
【請求項９】
前記文字列配置部は、表示範囲の中心に前記文字列を移動させて配置することを特徴とする請求項１記載の文字列配置描画装置。
【国際調査報告】
2013186897.tif 000033
2013186897.tif 000034
2013186897.tif 000035
2013186897.tif 000036