(57)【要約】  文字列配置部４が複数の候補点から配置した複数の文字列間の文字間隔に対する評価を示す文字間隔関数値を算出する文字間隔関数算出部５１と、文字列配置部４が配置した文字列が沿う道路ノード列の角度に対する評価を示す道路角度関数値を算出する道路角度関数算出部５２と、文字間隔関数算出部５１が算出した文字間隔関数値、および道路角度関数算出部５２が算出した道路角度関数値に基づいて評価関数値を算出する評価関数値算出部５３とを備えた。
2013024505.tif 000002
【特許請求の範囲】
【請求項１】
配置対象である文字列に関する文字列データおよび当該文字列を配置する道路ノード列に関する道路ノード列データを取得するデータ取得部と、
前記データ取得部が取得した文字列データおよび道路ノード列データに基づいて、前記道路ノード列上に前記文字列を配置するための複数の候補点を作成する候補点作成部と、
前記候補点作成部が作成した複数の候補点から前記文字列を配置する文字列配置部と、
前記文字列配置部による文字列の配置に対する評価を示す評価関数値を算出する評価関数算出部と、
前記評価関数算出部が算出した評価関数値のうち、最小値である最小評価関数値と、当該最小評価関数値における文字列配置および文字列配置開始点を記憶させる最小評価関数値保存部とを備え、
前記評価関数算出部は、
前記文字列配置部が複数の候補点から配置した複数の文字列間の文字間隔に対する評価を示す文字間隔関数値を算出する文字間隔関数算出部と、
前記文字列配置部が配置した文字列が沿う道路ノード列の角度に対する評価を示す道路角度関数値を算出する道路角度関数算出部と、
前記文字間隔関数算出部が算出した文字間隔関数値、および前記道路角度関数算出部が算出した道路角度関数値に基づいて前記評価関数値を算出する評価関数値算出部とを備えた文字列配置装置。
【請求項２】
前記候補点作成部は、
前記道路ノード列における所定の道路ノード間を繋ぐリンクの長さを算出する第１のリンク長算出部と、
前記第１のリンク長算出部が算出した道路ノード間を繋ぐリンクの長さを加算して更新し、前記道路ノード列の全長を算出するリンク全長更新部と、
前記リンク全長更新部が算出した前記道路ノード列の全長、および予め設定された前記候補点作成部が作成する候補点数に基づいて、候補点作成間隔を算出する候補点間隔算出部と、
前記道路ノード列上に、前記候補点間隔算出部が算出した候補点作成間隔で複数の候補点を作成する作成部とを備えたことを特徴とする請求項１記載の文字列配置装置。
【請求項３】
前記文字列配置部は、
前記文字列の先頭の文字の配置位置を決定する初期文字位置決定部と、
前記初期文字位置決定部が決定した先頭の文字の配置位置により決定される、前記文字列を配置する所定の道路ノード間を繋ぐリンクの角度を算出するリンク角度算出部と、
前記初期文字位置決定部が決定した先頭の文字の配置位置、および前記リンク角度算出部が算出したリンクの角度に基づいて、前記文字列を構成する各文字の配置位置を算出する文字配置位置算出部と、
前記文字配置位置算出部が算出した前記各文字の配置位置が前記リンク上に存在するか判定を行う文字リンク外判定部と、
前記文字リンク外判定部において、前記各文字の配置位置が前記リンク上に存在すると判定された場合に、前記各文字の配置位置に基づいて配置座標を設定し、設定した配置座標に前記各文字を配置する文字配置部とを備えたことを特徴とする請求項１記載の文字列配置装置。
【請求項４】
前記文字列配置部は、
前記文字配置部が前記各文字を配置した配置座標が、前回設定した文字の配置座標に重なるか判定を行う重なり判定部と、
前記重なり判定部において、前記配置座標が前回設定した文字の配置座標に重なると判定された場合に、前記初期文字位置決定部が決定したパラメータに所定定数を加算して更新するパラメータ更新部とを備えたことを特徴とする請求項３記載の文字列配置装置。
【請求項５】
前記文字間隔関数算出部は、
前記文字列配置部が配置した複数の文字列のうち、初めに配置した文字列であるか判定を行う初期文字列判定部と、
前記初期文字列判定部において、初めに配置した文字列でないと判定された文字列について、その他の文字列との文字間隔を示すガウス関数値を算出する第１のガウス関数値算出部と、
前記第１のガウス関数値算出部が算出したガウス関数値を用いて、前記文字列間隔関数値を更新する文字間隔関数更新部とを備えたことを特徴とする請求項１記載の文字列配置装置。
【請求項６】
前記道路角度関数算出部は、
前記文字列と当該文字列を配置する道路ノード列との関係を示すガウス関数値を算出する第２のガウス関数値算出部と、
前記第２のガウス関数値算出部が算出したガウス関数値を用いて、前記道路角度関数値を更新する道路角度関数更新部とを備えたことを特徴とする請求項１記載の文字列配置装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、地図などの図形上に文字列を配置する文字列配置装置に関するものである。
【背景技術】
【０００２】
従来の地図表示装置は、道路名称等の文字列を、文字列の配置を開始する点(以下、文字列配置開始点と称する)から、道路線(以下、道路ノード列と称する)に沿って配置する機能を備えている（例えば、図２１参照）。この場合、文字列配置開始点が適切でなければ、図２２（ａ）に示す文字列同士の重なり、図２２（ｂ）に示す文字の表示角度の変化による可読性の低下、図２２（ｃ）に示す文字列の密集による可読性の低下が起こる。【０００３】
図２２（ａ）に示す文字列同士の重なり、および図２２（ｂ）に示す可読性の低下を解決する方法として、例えば非特許文献１には可読性が高い位置に文字列配置開始点を変更する方法が記載されている。具体的には、図２３（ａ）に示す文字列同士の重複を示す関数overlap(i)と、図２３（ｂ）に示す文字列が沿う道路ノード列の角度変化を示す関数flatness(i)で構成される、以下の式（１）で示す評価関数ｆを最小化することにより、文字列配置開始点を変更する方法である。なお、式（１）中のα１とα２はoverlap(i)とflatness(i)の値を調整するパラメータであり、String_numは文字列数を示す。
2013024505.tif 000003
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Shawn Edmondson, “A General Cartographic Labeling Algorithm”, The International Journal for Geographic Information and Geovisualization, Volume 33, Number 4/ Winter 1996
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した非特許文献１の方法は、図２２（ａ）で示した文字列同士の重複、および図２２（ｂ）で示した文字列が沿う道路の角度変化による可読性低下を解決する方法であるため、図２２（ｃ）に示す文字列の密集による可読性低下を避けることができないという課題があった。【０００６】
この発明は、上記のような課題を解決するためになされたもので、文字列の重複、文字の表示角度の変化だけでなく、文字列の密集度合いも加味して文字列配置開始点を最適な位置に変更する文字列配置装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
この発明に係る文字列配置装置は、配置対象である文字列に関する文字列データおよび当該文字列を配置する道路ノード列に関する道路ノード列データを取得するデータ取得部と、データ取得部が取得した文字列データおよび道路ノード列データに基づいて、道路ノード列上に文字列を配置するための複数の候補点を作成する候補点作成部と、候補点作成部が作成した複数の候補点から文字列を配置する文字列配置部と、文字列配置部による文字列の配置に対する評価を示す評価関数値を算出する評価関数算出部と、評価関数算出部が算出した評価関数値のうち、最小値である最小評価関数値と、当該最小評価関数値における文字列配置および文字列配置開始点を記憶させる最小評価関数値保存部とを備え、評価関数算出部は、文字列配置部が複数の候補点から配置した複数の文字列間の文字間隔に対する評価を示す文字間隔関数値を算出する文字間隔関数算出部と、文字列配置部が配置した文字列が沿う道路ノード列の角度に対する評価を示す道路角度関数値を算出する道路角度関数算出部と、文字間隔関数算出部が算出した文字間隔関数値、および道路角度関数算出部が算出した道路角度関数値に基づいて評価関数値を算出する評価関数値算出部とを備えるものである。
【発明の効果】
【０００８】
この発明によれば、文字列同士の重なり、および文字の表示角度の変化による可読性の低下を抑制すると共に、文字列の密集を抑制することが可能となり、文字列の視認性を向上させることができる。
【図面の簡単な説明】
【０００９】
【図１】実施の形態１による文字列配置装置の構成を示すブロック図である。
【図２】実施の形態１による文字列配置装置の動作を示すフローチャートである。
【図３】実施の形態１による文字列配置装置の候補点作成部の構成を示すブロック図である。
【図４】実施の形態１による文字列配置装置の文字列配置部の構成を示すブロック図である。
【図５】実施の形態１による文字列配置装置の評価関数算出部の構成を示すブロック図である。
【図６】文字列を配置する道路ノード列の関係を示す図である。
【図７】実施の形態１による文字列配置装置の候補点作成部の動作を示すフローチャートである。
【図８】実施の形態１による文字列配置装置の候補点作成結果を示す図である。
【図９】実施の形態１による文字列配置装置の文字列配置部の動作を示すフローチャートである。
【図１０】実施の形態１による文字列配置装置の配置結果を示す図である。
【図１１】実施の形態１による文字列配置装置の配置結果を示す図である。
【図１２】実施の形態１による文字列配置装置の配置結果を示す図である。
【図１３】実施の形態１による文字列配置装置の配置結果を示す図である。
【図１４】実施の形態１による文字列配置装置の評価関数算出部の動作を示すフローチャートである。
【図１５】実施の形態１による文字列配置装置のリンク角度の算出例を示す説明図である。
【図１６】実施の形態１による文字列配置装置の配置例を示す図である。
【図１７】実施の形態１による文字列配置装置の配置例を示す図である。
【図１８】実施の形態１による文字列配置装置の候補点作成結果を示す図である。
【図１９】実施の形態１による文字列配置装置の配置例を示す図である。
【図２０】実施の形態１による文字列配置装置の配置例を示す図である。
【図２１】従来の文字列の配置を示す説明図である。
【図２２】従来の文字列の配置を示す説明図である。
【図２３】従来の文字列の配置の可読性向上を示す説明図である。
【発明を実施するための形態】
【００１０】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
実施の形態１．
図１は、この発明の実施の形態１による文字列配置装置の構成を示すブロック図である。
文字列配置装置１００は、文字列データ記憶部１、文字列データ取得部（データ取得部）２、候補点作成部３、文字列配置部４、評価関数算出部５、最小評価関数値保存部６、最小評価関数値データ記憶部７、文字列配置データ記憶部８および文字列配置開始点データ記憶部９で構成されている。
【００１１】
文字列データ記憶部１は、複数の文字列のデータ集合を記憶する記憶領域であって、文字列の個数、各々の文字列が含む文字数、文字毎の横幅・縦幅、文字列が沿う道路ノード列を格納する。文字列データ取得部２は、文字列データ記憶部１に記憶された文字列データを取得する。候補点作成部３は、文字列が沿う道路ノード上に文字列の配置候補（以下、候補点と称する）を複数作成する。文字列配置部４は、文字列を候補点から道路ノード列に沿って配置する。
【００１２】
評価関数算出部５は、配置した文字列の可読性を数値化する。最小評価関数値保存部６は、評価関数が最小値となる際の評価関数値、文字列配置および文字列配置開始点を各記憶領域に格納させる。最小評価関数値データ記憶部７は、最小の評価関数値を保存する記憶領域である。文字列配置データ記憶部８は、最小の評価関数値を取る時の文字列配置を保存する記憶領域である。文字列配置開始点データ記憶部９は、評価関数値が最小の時の文字列配置開始点を保存する記憶領域である。
【００１３】
次に、文字列配置装置の動作について説明する。
図２は、この発明の実施の形態１による文字列配置装置の動作を示すフローチャートである。
文字列データ取得部２は、文字列データ記憶部１を参照し、配置する文字列データを取得する（ステップＳＴ１）。候補点作成部３は、ステップＳＴ１で取得した文字列が沿う道路ノード列上に、当該文字列を配置する候補点を作成する（ステップＳＴ２）。文字列配置部４は、ステップＳＴ２で作成された候補点から道路ノード列に沿って文字列を配置する（ステップＳＴ３）。さらに文字列配置部４は、ステップＳＴ３の配置結果を参照し、道路ノード列に沿って文字列の配置が可能か否か判断する（ステップＳＴ４）。例えば、道路ノード列から文字列がはみ出しているなどの場合には、配置不可能であると判断するなどである。道路ノード列に沿って文字列の配置が不可能であると判断した場合（ステップＳＴ４；ＮＯ）、処理を終了する。
【００１４】
一方、道路ノード列に沿って文字列の配置が可能である場合（ステップＳＴ４；ＹＥＳ）、評価関数算出部５は配置した文字列の評価関数値を算出する（ステップＳＴ５）。最小評価関数値保存部６は、ステップＳＴ５で算出された評価関数値が、最小評価関数値データ記憶部７に既に記憶されている最小評価関数値mini_cost未満であるか判定を行う（ステップＳＴ６）。評価関数値が最小評価関数値mini_cost以上である場合（ステップＳＴ６；ＮＯ）には、処理を終了する。一方、評価関数値が最小評価関数値mini_cost未満である場合（ステップＳＴ６；ＹＥＳ）には、最小評価関数値保存部６が、ステップＳＴ５で算出された評価関数値を最小評価関数値データ記憶部７に格納する（ステップＳＴ７）と共に、文字列配置に関するデータおよび文字列配置開始点に関するデータを文字列配置データ記憶部８および文字列配置開始点データ記憶部９に格納し（ステップＳＴ８）、処理を終了する。
【００１５】
続いて、文字列配置装置１００のより詳細な構成および動作について説明する。
図３から図５は文字列配置装置１００の各構成をより詳細に示したブロック図であり、図３は候補点作成部３の構成を示すブロック図、図４は文字列配置部４の構成を示すブロック図、図５は評価関数算出部５の構成を示すブロック図である。
まず、図３に示すように、候補点作成部３は、道路ノード列中の２つのノードを結ぶリンクの長さを算出する第１のリンク長算出部３１と、第１のリンク長算出部３１で算出したリンクの長さを加算して道路ノード列の全長を求めるリンク全長更新部３２と、リンクの全長から候補点の間隔を算出する候補点間隔算出部３３と、道路ノード列上に候補点を作成する作成部３４と、設定されたリンク長が所定の条件を満たさない場合に、ノードを更新してリンクの長さを算出する第２のリンク長算出部３５と、第２のリンク長算出部３５が算出したリンクの長さに基づいてリンク長を更新する距離更新部３６と、候補点間隔（cand_gap）、候補点番号（cand_idx）、道路ノード列の先頭ノードから所定のノードを繋ぐリンク長（dist）など、候補点に関する情報を記憶する情報記憶部３７で構成される。
【００１６】
次に、図４に示すように、文字列配置部４は、文字列の１文字目の位置を設定する初期文字位置決定部４１と、リンクの角度を算出するリンク角度算出部４２と、文字の配置位置を算出する文字配置位置算出部４３と、文字がリンク外か否かを判定する文字リンク外判定部４４と、文字の配置を設定する文字配置部４５と、前に配置した文字との重なりを判定する重なり判定部４６と、文字がリンク上に存在し、且つ文字の重なりがない場合に文字の配置に必要なパラメータを更新する第１のパラメータ更新部（パラメータ更新部）４７と、文字がリンク外に位置している場合に文字の配置に必要なパラメータを更新する第２のパラメータ更新部４８で構成される。
【００１７】
次に、図５に示すように、評価関数算出部５は、文字列同士の文字間隔が文字列の可読性に与える影響を示す関数値を算出する文字間隔関数算出部５１と、道路の角度が文字列の可読性に与える影響示す関数値を算出する道路角度関数算出部５２と、評価関数値を算出する評価関数値算出部５３で構成される。さらに、文字間隔関数算出部５１は、初めの文字列か否かを判定する初期文字列判定部５４と、ガウス関数の値を算出する第１のガウス関数値算出部５５と、文字列同士の文字間隔が文字列の可読性に与える影響を示す関数値を更新する文字間隔関数更新部５６で構成されている。また、道路角度関数算出部５２は、ガウス関数の値を算出する第２のガウス関数値算出部５７と、道路の角度が文字列の可読性に与える影響を示す関数値を更新する道路角度関数更新部５８で構成されている。
【００１８】
次に、候補点作成部３、文字列配置部４および評価関数算出部５の詳細な動作について説明する。なお、以下の動作説明では、道路ノード列に配置する文字列データは、文字列「String11」および文字列「String2」から成るデータであり、各々の文字の横幅は全て５であり、縦幅は全て１０として説明を行う。また、文字列「String11」および文字列「String2」が配置される道路ノード列の関係を図６に示す。文字列「String11」が沿う道路ノード列Ｐ（０）−Ｐ（２）は、ノードＰ（０）＝（１０，２０）、ノードＰ（１）＝（１０，５０）、ノードＰ（２）＝（１００，５０）で構成される。同様に文字列「String2」が沿う道路ノード列Ｐ（３）−Ｐ（５）は、ノードＰ（３）＝（５０，７０）、ノードＰ（４）＝（５０，１０）、ノードＰ（５）＝（１１０，１０）で構成される。さらに、STEP_SIZEを１とし、CANDIDATE_NUM（候補点数）を３とし、Σを以下の式（２）とし、Ｈを以下の式（３）とし、ＲＣを１とし、ＳＣを１とする。
2013024505.tif 000004
【００１９】
まず、図２で示したフローチャートのステップＳＴ１として、文字列データ取得部２が、文字列データ記憶部１から１つ目の文字列「String11」と、２つ目の文字列「String2」と、各々の文字列が配置される道路ノード列Ｐ（０）−Ｐ（２）および道路ノード列Ｐ（３）−Ｐ（５）と、各々の文字列を構成する各文字の横幅および縦幅を取得する。次に、１つ目の文字列「String11」の配置最適化を行う。その方法として、まず候補点作成部３が文字列「String11」が沿う道路ノード列Ｐ（０）−Ｐ（２）上にあらかじめ設定されたCANDIDATE_NUM個の候補点、すなわち３つの候補点を等間隔に作成する。
【００２０】
具体的な候補点作成方法を、図７のフローチャートを参照しながら説明する。図７は、実施の形態１による文字列配列装置の候補点作成部の動作を示すフローチャートである。
候補点作成部３の第１のリンク長算出部３１は、情報記憶部３７に記憶された各ノード情報を参照し、ｎ番目のノードＰ（ｎ）とｎ＋１番目のノードＰ（ｎ＋１）を繋ぐリンクの長さを算出する（ステップＳＴ１１）。リンク全長更新部３２は、第１のリンク長算出部３１がリンク長を算出すると、前回算出したリンク全長に加算してリンク全長（total_dist）の値を更新する（ステップＳＴ１２）。
【００２１】
第１のリンク長算出部３１は、道路ノード列を構成する全てのリンクの長さを算出したか判定を行う（ステップＳＴ１３）。全てのノードについてリンクの長さを算出していない場合（ステップＳＴ１３；ＮＯ）には、ステップＳＴ１１の処理に戻り、上述した処理を繰り返す。一方、全てのノードについてリンクの長さを算出した場合（ステップＳＴ１３；ＹＥＳ）には、候補点間隔算出部３３は情報記憶部３７を参照して候補点数（CANDIDATE_NUM）を取得し、以下の式（４）に基づいて候補点の間隔を算出し、算出した候補点間隔（cand_gap）を情報記憶部３７に記憶させる（ステップＳＴ１４）。
ｃａｎｄ＿ｇａｐ＝ｔｏｔａｌ＿ｄｉｓｔ／ＣＡＮＤＩＤＡＴＥ＿ＮＵＭ・・・（４）
【００２２】
次に、作成部３４は、情報記憶部３７を参照して候補点間隔（cand_gap）、候補点番号（cand_idx）、道路ノード列の先頭ノードから所定のノードを繋ぐリンク長（dist）に関する情報を取得し、候補点が以下の式（５）で示す条件を満たすか判定を行う（ステップＳＴ１５）。
ｄｉｓｔ＞ｃａｎｄ＿ｉｄｘ×ｃａｎｄ＿ｇａｐ・・・（５）
なお、候補点番号（cand_idx）の初期値は０であり、初期のリンク長(dist)は、道路ノード列の先頭ノードと、当該先頭ノードの次の位置に配置されたノードを繋ぐリンクの長さとなる。当該初期条件は予め情報記憶部３７に記憶されているものとする。
【００２３】
上記式（５）の条件を満たす場合（ステップＳＴ１５；ＹＥＳ）、作成部３４は道路ノード列の先頭ノードから、当該道路ノード列に沿って、候補点番号（cand_idx）×候補点間隔（cand_gap）離れた位置に候補点Ｑを作成する（ステップＳＴ１６）。その後作成部３４は、CANDIDATE_NUM個全ての候補点Ｑを作成したか否か判定を行う（ステップＳＴ１７）。全ての候補点を作成した場合（ステップＳＴ１７；ＹＥＳ）には、処理を終了する。一方、全ての候補点Ｑを作成していない場合（ステップＳＴ１７；ＮＯ）、候補点番号を１加算して情報記憶部３７に記憶させ（cand_idx+1、ステップＳＴ１８）、ステップＳＴ１５の処理に戻る。
【００２４】
また、上記式（５）の条件を満たさない場合（ステップＳＴ１５；ＮＯ）、ステップＳＴ１５の判定処理におけるノード番号に１を加算し（ステップＳＴ１９）、加算後のノードと、当該加算後のノードの次の位置に配置されたノードとを繋ぐリンクの長さを算出する（ステップＳＴ２０）。距離更新部３６は、ステップＳＴ１５の判定処理に用いたリンク長（dist）にステップＳＴ２０で新たに算出したリンクの長さを加算し、リンク長（dist）を更新する（ステップＳＴ２１）。なお、ステップＳＴ１９からステップＳＴ２１で更新された情報は、情報記憶部３７に記憶される。その後、フローチャートはステップＳＴ１５の処理に戻る。
【００２５】
次に、図７に示したフローチャートに沿って、図６で示した具体例を用いて説明を行う。
ステップＳＴ１１として、第１のリンク長算出部３１は、０番目のノードＰ（０）と１番目のノードＰ（１）のノードを繋ぐリンクの長さ：３０を算出する。ステップＳＴ１２として、リンク全長更新部３２は前回までに算出したリンク全長：０にリンクの長さ：３０を加算して、リンク全長を更新する。同様に、１番目のノードＰ（１）と２番目のノードＰ（２）のノードを繋ぐリンクの長さ：９０を算出し、リンク全長：１２０に更新する。ステップＳＴ１３で道路ノード列Ｐ（０）−Ｐ（２）を構成する全てのリンクの長さを算出したと判定されると、ステップＳＴ１４として、候補点間隔算出部３３は情報記憶部３７を参照して候補点数（CANDIDATE_NUM）＝３を取得し、候補点間隔（cand_gap）：１２０／３＝４０を算出する。
【００２６】
ステップＳＴ１５として、作成部３４は情報記憶部３７を参照して候補点間隔（cand_gap）：４０、候補点番号（cand_idx）：０（初期値）、リンク長（dist）：３０（初期リンク（Ｐ（０），Ｐ（１））を取得し、候補点Ｑ（０）が上記式（５）の条件を満たすか判定を行う。図６の例では、３０＞０×４０であることから、式（５）の条件を満たすと判定する。
【００２７】
ステップＳＴ１６として、作成部３４は開始ノードＰ（０）から０×４０＝０離れた位置に候補点Ｑ（０）を作成する。即ち、０番目の候補点Ｑ（０）は、Ｐ（０）と同一地点となる。なお、候補点Ｑ（０）は、位置（１０，２０）、候補点Ｑ（０）が存在するリンク（Ｐ（０），Ｐ（１））の開始ノードのインデックス：０、候補点が存在するリンクの開始ノードＰ（０）からの距離：０となる。ステップＳＴ１７として、作成部３４は全ての候補点を作成していないと判定し、ステップ１８として候補点番号に１加算して候補点Ｑ（１）とし、ステップＳＴ１５の処理に戻る。
【００２８】
続いて、候補点Ｑ（１）の作成処理について説明する。
ステップＳＴ１５として、作成部３４は情報記憶部３７を参照して候補点間隔（cand_gap）：４０、候補点番号（cand_idx）：１、リンク長（dist）：３０（初期リンク（Ｐ（０），Ｐ（１））を取得し、候補点Ｑ（１）が上記式（５）の条件を満たすか判定を行う。図６の例では、３０＜１×４０であることから、式（５）の条件を満たさないと判定する。そこでステップＳＴ１９，２０として、ノードＰ（０）のノード番号に１を加算してノードＰ（１）とし、ノードＰ（１）とノードＰ（２）とを繋ぐリンクの長さ：９０を算出する。ステップＳＴ２１として、距離更新部３６は、上述したステップＳＴ１５の判定処理に用いたリンク長（dist）：３０に算出したリンク長：９０を加算した値をリンク長（dist）：１２０に更新する。更新した情報を情報記憶部３７に記憶させた後、ステップＳＴ１５の処理に戻る。
【００２９】
ステップＳＴ１５として、作成部３４は情報記憶部３７を参照して候補点間隔（cand_gap）：４０、候補点番号（cand_idx）：１、リンク長（dist）：１２０（リンク（Ｐ（０），Ｐ（２）））を取得し、候補点Ｑ（１）が上記式（５）の条件を満たすか判定を行う。図６の例では、１２０＞１×４０であることから、式（５）の条件を満たすと判定する。ステップＳＴ１６として、作成部３４は開始ノードＰ（０）から１×４０＝４０離れた位置に候補点Ｑ（１）を作成する。その後、ステップＳＴ１７として、作成部３４は全ての候補点を作成していないと判定し、ステップ１８として候補点番号に１加算して候補点Ｑ（２）とし、ステップＳＴ１５の処理に戻る。候補点Ｑ（２）を作成するまで、上述した処理を繰り返し行う。
【００３０】
図６に示した道路ノード列Ｐ（０）−Ｐ（２）に対して候補点を作成した結果を図８に示している。また、図８に示した３つの候補点Ｑ（０），Ｑ（１），Ｑ（２）の位置関係は以下に示すとおりである。
候補点Ｑ（０）  位置：（１０，２０）、開始ノードのインデックス：０、開始ノードからの距離：０
候補点Ｑ（１）  位置：（２０，５０）、開始ノードのインデックス：１、開始ノードからの距離：１０
候補点Ｑ（２）  位置：（６０，５０）、開始ノードのインデックス：１、開始ノードからの距離：５０
【００３１】
次に、候補点作成部３が作成した候補点Ｑに、文字列配置部４が文字列を配置する動作について説明する。
図９は、実施の形態１による文字列配置装置の文字列配置部の動作を示すフローチャートである。
なお、以下では、候補点Ｑが存在するリンクＲ（Ｑ）の開始ノードのインデックスをroad_idxとし、候補点Ｑが存在する道路ノード列の先頭ノードから候補点Ｑまでの距離をdistと記載する。
【００３２】
初期文字位置決定部４１は、処理開始時にroad_idxとdistの初期設定を行う（ステップＳＴ３１）。次にリンク角度算出部４２は、road_idx（ｎ）番目のノードとroad_idx（ｎ＋１）番目のノードを繋ぐリンクの角度θを算出する（ステップＳＴ３２）。ここでリンクの角度θは、Ｘ軸方向を０°、Ｙ軸方向を９０°とし、リンク（road_idx（ｎ），road_idx（ｎ＋１））の角度、即ちベクトル（road_idx（ｎ），road_idx（ｎ＋１））の角度とする。文字配置位置算出部４３は、road_idx（ｎ）番目のノードからθ方向に、dist分離れた位置を文字配置位置として算出する（ステップＳＴ３３）。
【００３３】
文字リンク外判定部４４は、文字配置位置がリンク（road_idx（ｎ），road_idx（ｎ＋１））上に存在するか判定を行う（ステップＳＴ３４）。文字配置位置がリンク（road_idx（ｎ），road_idx（ｎ＋１））上に存在する場合（ステップＳＴ３４；ＹＥＳ）、文字配置部４５が文字の配置位置を決定する（ステップＳＴ３５）。具体的な処理としては、まずステップＳＴ３３で文字配置位置算出部４３が算出した文字列配置位置の座標を文字の左下座標に設定する。さらに、次の式（６）に基づいて文字の左上座標、右下座標、右上座標を算出する。
【００３４】
2013024505.tif 000005
【００３５】
なお、式（６）において、char_idxは、文字列を構成する文字の配置順を示すインデックスである。さらに、H(char_idx)はchar_idx番目の文字の縦幅、W(char_idx)はchar_idx番目の文字の横幅、LD(char_idx)はchar_idx番目の文字の左下座標、LT(char_idx)はchar_idx番目の文字の左上座標、RD(char_idx)はchar_idx番目の文字の右下座標、RT(char_idx)はchar_idx番目の文字の右上座標を示す。
【００３６】
重なり判定部４６は、ステップＳＴ３５で決定した配置位置が、前回の処理で配置した文字と重なるか判定を行う（ステップＳＴ３６）。文字の重なりがない場合（ステップＳＴ３６；ＮＯ）、第１のパラメータ更新部４７が、distにchar_idx番目の文字の横幅を加算すると共に、char_idxを「１」増加させる（ステップＳＴ３７）。その後、第１のパラメータ更新部４７は、文字列を構成する全ての文字の配置位置を求めたか否か判定を行う（ステップＳＴ３８）。全ての文字の配置位置を求めた場合（ステップＳＴ３８；ＹＥＳ）処理を終了する。一方、全ての文字の配置位置を求めていない場合（ステップＳＴ３８；ＮＯ）、第１のパラメータ更新部４７は、文字配置位置算出部４３に対して、ステップＳＴ３７で更新したパラメータに基づき再度配置位置の算出を指示する（ステップＳＴ３９）。その後、ステップＳＴ３３の処理に戻り、上述した処理を繰り返す。
【００３７】
一方、文字の重なりがある場合（ステップＳＴ３６；ＹＥＳ）、重なり判定部４６はdistにSTEP_SIZEを加算し（ステップＳＴ４０）、文字配置位置算出部４３に対して、ステップＳＴ４０で加算したパラメータに基づき再度配置位置の算出を指示する（ステップＳＴ４１）。その後、ステップＳＴ３３の処理に戻り、上述した処理を繰り返す。
【００３８】
さらに、文字配置位置がリンク上の存在していない場合（ステップＳＴ３４；ＮＯ）、第２のパラメータ更新部４８においてパラメータの更新を行う（ステップＳＴ４２）。具体的には、第２のパラメータ更新部４８が、distからリンク（road_idx（ｎ），road_idx（ｎ＋１））の長さを引いた値をdistに更新すると共に、road_idxに１を加算した後、文字配置位置算出部４３に対して、更新したパラメータに基づき再度配置位置の算出を指示する（ステップＳＴ４３）。その後、ステップＳＴ３２の処理に戻り、上述した処理を繰り返す。
【００３９】
次に、図９に示したフローチャートに沿って、図６および図８で示した具体例を用いて説明を行う。
まず、ステップＳＴ３１として、初期文字位置決定部４１は、road_idxとdistの初期設定を行い、候補点Ｑ（０）の開始ノードのインデックス：０をroad_idx、道路ノード列Ｐ（０）−Ｐ（２）の先頭ノードＰ（０）から候補点Ｑまでの距離：０をdistとする。ステップＳＴ３２として、リンク角度算出部４２は、リンク（Ｐ（０），Ｐ（１））の角度θ＝９０°を算出する。ステップＳＴ３３として、文字配置位置算出部４３は、road_idx＝０番目のノードからθ＝９０°の方向にdist＝０離れた位置ＬＤ(０)＝(１０，２０)を文字列配置位置として算出する。
【００４０】
ステップＳＴ３４の判定処理において、文字リンク外判定部４４は、ＬＤ(０)がリンク（Ｐ（０），Ｐ（１））上に存在すると判定する。ステップＳＴ３５として、文字配置部４５は、文字列「String11」の０番目の文字「S」の配置位置を決定する。まずＬＤ(０)を文字「S」の左下座標に設定し、次にＬＴ(０)＝(０，２０)を文字「S」の左上座標に設定する。その後、ＲＤ(０)＝(１０，２５)を文字「S」の右下座標に設定する。最後にＲＴ(０)＝(０，２５)を文字「S」の右上座標に設定する。文字「S」の外接矩形の配置を図１０に示す。ステップＳＴ３６として、重なり判定部４６がステップＳＴ３５で配置した文字「S」と前回配置した文字の重なりを判定するが、この例では前回配置した文字が存在しないことから、重なりは無いと判定する。
【００４１】
ステップＳＴ３７として第１のパラメータ更新部４７は、distに０番目の横幅「５」を付加してdist＝０＋５＝５とし、char_idxに「１」を付加してchar_idx＝０＋１＝１とする。ステップＳＴ３８として、第１のパラメータ更新部４７は、文字列を構成する全ての文字の配置位置を求めていないと判定するため、ステップＳＴ３９として文字配置位置算出部４３に更新後のパラメータに基づいて、再度配置位置の算出を指示し、ステップＳＴ３３の処理に戻る。
【００４２】
ステップＳＴ３９の指示を受けた文字配置位置算出部４３は、２文字目「ｔ」の文字配置位置を算出する。算出は、ステップＳＴ３７で更新したdist＝５、およびchar_idx＝１に基づいて行われる。ステップＳＴ３３として文字配置位置算出部４３は、位置ＬＤ（１）＝（１０，２５）を文字列配置位置として算出する。さらにステップＳＴ３４からステップＳＴ３６の処理を行い、ＬＤ（１）はリンク（Ｐ（０），Ｐ（１））上に存在し、２文字目「t」の左下座標、左上座標、右下座標、右上座標は、それぞれＬＤ（１）＝（１０，２５）、ＬＴ（１）＝（０，２５）、ＲＤ（１）＝（１０，３０）、ＲＴ（１）＝（０，３０）となる。２文字目「t」の外接矩形の配置を図１１に示す。ステップＳＴ３６において、１文字目に配置した文字と、２文字目に配置した文字が重なっていると判定されるため、ステップＳＴ４０として重なり判定部４６がdistにSTEP_SIZE＝１を加算し、ステップＳＴ４１として加算後のパラメータに基づいて再度２文字目「t」の文字配置位置を算出するように文字配置位置算出部４３に指示する。
【００４３】
再度ステップＳＴ３３からステップＳＴ３６の処理を繰り返し、２文字目「ｔ」の文字配置位置を算出する。算出は、ステップＳＴ４０で加算されたdist＝６、およびchar_idx＝１に基づいて行われる。図１２に、上述した処理を繰り返し２文字目ＬＤ（１）から６文字目ＬＤ（５）までを配置した結果を示している。なお、図１２では、各文字の左下座標のみを記載している。
【００４４】
６文字目を配置した後、文字配置位置算出部４３は文字列「String11」の７文字目「1」の配置位置を算出する。この時、dist＝３５、cand_idx＝６、road_idx＝０であるため、road_idx番目のノードからθの方向にdist離れた位置は、ＬＤ（６）＝（１０，５５）となる。ステップＳＴ３４として、文字リンク外判定部４４は配置位置（１０，５５）がリンク（Ｐ（０），Ｐ（１））外であると判定し、ステップＳＴ４２として第２のパラメータ更新部４８がパラメータの更新を行う。具体的には、０番目のノードと１番目のノードを繋ぐリンクの長さは「３０」であるため、dist＝３５−３０＝５に更新され、road_idx＝０＋１＝１となる。その後ステップＳＴ４３として、第２のパラメータ更新部４８により更新されたパラメータに基づいて、再度配置位置の算出を指示し、ステップＳＴ３２の処理に戻る。
【００４５】
ステップＳＴ３２として、リンク角度算出部４２は更新されたパラメータに基づいて、リンク（Ｐ（１），Ｐ（２））の角度θ＝０°を算出する。以降、上記と同様の処理を行い、７文字目および８文字目の配置を行い、ステップＳＴ３８の判定処理において、全ての文字の配置位置を求めたと判定され、処理を終了する。全ての文字を配置した結果を図１３に示している。図１３においても、各文字の左下座標のみを記載している。
【００４６】
次に、配置した文字列が可読性に与える影響を示す評価関数値を算出する方法について説明する。図１４は、実施の形態１による文字列配置装置の評価関数算出部の動作を示すフローチャートである。
まず、文字間隔関数算出部５１は、既に配置が決定した文字列（０番目からstring_idx-1番目の文字列)と、string_idx(n)番目の文字列との文字間隔を示す関数である文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）を算出する。具体的には、文字間隔関数算出部５１の初期文字列判定部５４が、string_idx＝０、またはstring_idx≧１であるか判定を行う（ステップＳＴ５１）。ステップＳＴ５１においてstring_idx＝０であると判定した場合、文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）に「１」を設定し（ステップＳＴ５２）、道路角度関数算出部５２の処理に進む。
【００４７】
一方、ステップＴ５１においてstring_idx≧１以上であると判定した場合、文字間隔関数更新部５６が以下の式（７）に基づいて文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1})算出を行い（ステップＳＴ５３）、道路角度関数算出部５２の処理に進む。
2013024505.tif 000006
上記式（７）において、Ｃｓｔｒｉｎｇ＿ｉｄｘ、Ｃｓｔｒｉｎｇ＿ｉｄｘ２は、それぞれstring_idx番目、string_idx２番目の文字列の文字数を示している。また、式（７）におけるｘｃｈａｒ＿ｉｄｘ、ｘｃｈａｒ＿ｉｄｘ２はそれぞれ、char_idx番目、char_idx2番目の文字の中心座標を示す。
【００４８】
なお、上記式（７）中のＮ´（ｘｃｈａｒ＿ｉｄｘ｜ｘｃｈａｒ＿ｉｄｘ２）は、第１のガウス関数出部５５により以下の式（８）に基づいて算出される。
2013024505.tif 000007
上記式（８）において、ｘｃｈａｒ＿ｉｄｘ、ｘｃｈａｒ＿ｉｄｘ２はそれぞれ、char_idx番目、char_idx2番目の文字の中心座標を示し、ＳＣは定数、Ｈ−１は共分散行列を示している。
【００４９】
道路角度関数更新部５８は、以下の式（９）に基づいて道路角度関数値Ｐ(Rstring_idx｜Sstring_idx）を算出する（ステップＳＴ５４）。
2013024505.tif 000008
上記式（９）中のＮｏｓｔｒｉｎｇ＿ｉｄｘは、string_idx番目の文字列が沿う道路ノード列のノード数、μｒｏａｄ＿ｉｄｘは道路ノード列中のroad_idx番目のノードの座標を示す。
【００５０】
なお、上記式（９）中のＮ(ｘchar_idx|μroad_idx)は、第２のガウス関数値算出部５７により以下の式（１０）に基づいて算出される。
2013024505.tif 000009
【００５１】
上記式（１０）において、ｘchar_idx、μroad_idxは位置座標を示すベクトルであり、ｘchar_idxはchar_idx番目の文字の中心、μroad_idxはroad_idx番目の道路ノードを示す。また、Ｔは転置を示し、Σ-1はΣの逆行列を示す。なお、上記式（１０）におけるAngle(road_idx)は、road_idx-1番目のノードとroad_idx番目のノードを繋ぐリンクと、road_idx+1番目のノードとroad_idx番目のノードを繋ぐリンクの角度変化を示す。Angle(road_idx)の算出例を図１５に示す。図１５におけるR(road_idx)は、road_idx番目の道路ノードを示す。図１５に示すように、２つのリンクの角度変化が、リンクの角度変化となる。
【００５２】
評価関数値算出部５３は、ステップＳＴ５２またはステップＳＴ５３で算出された文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1})、およびステップＳＴ５４で算出された道路角度関数値Ｐ(Rstring_idx｜Sstring_idx）を用いて、以下の式（１１）に基づいて評価関数値Ｆを算出する（ステップＳＴ５５）。
2013024505.tif 000010
算出した評価関数値Ｆは、最小評価関数値保存部６に出力され（ステップＳＴ５６）、処理を終了する。
【００５３】
次に、図１４で示したフローチャートに沿って、図１３で示した具体例を用いて説明を行う。
ステップＳＴ５１として、初期文字列判定部５４はstring_idx=0、あるいはstring_idx≧1以上であるか判定を行う。まず、初回の判定であることから、ここではstring_idx=0となり、ステップＳＴ５２として文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）に「１」を設定する。
【００５４】
続いて、ステップＳＴ５４として、道路角度関数更新部５８は上記式（９）に基づいてＰ(Rstring_idx｜Sstring_idx）の値を、2.36036×10-85と算出する。その後、道路角度関数更新部５８はchar_idxおよびroad_idxを更新してステップＳＴ５４の処理を繰り返し、最終的にＰ(Rstring_idx｜Sstring_idx）＝0.000777442との値を得る。
【００５５】
ステップＳＴ５５として、評価関数値算出部５３は、ステップＳＴ５２で算出した文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）＝１、およびステップＳＴ５４で最終的に得た道路角度関数値Ｐ(Rstring_idx｜Sstring_idx）＝0.000777442に基づいて、上述した式（１１）に基づいて評価関数値の算出を行い、評価関数値Ｆ＝log0.000777442+log1＝-3.109331764を得る。ステップＳＴ５６として、算出した評価関数値Ｆを最小評価関数値保存部６に出力する。最小評価関数値保存部６は、算出された評価関数値Ｆがmin_cost未満であると判定し、min_costの値にＦ＝-3.109331764を設定して最小評価関数値データ記憶部７に格納すると共に、０番目の文字列の文字列開始点にＱ（０）を設定して文字列配置開始点データ記憶部９に格納し、図１３で示した文字列配置を文字列配置データ記憶部８に格納し、処理を終了する。
【００５６】
その後、上述した処理を繰り返し、文字列配置部４において、１番目の候補点Ｑ（１）から０番目の文字列を配置する。この場合の配置例を図１６に示す。評価関数値算出部５３は、図１６に示した配置例について評価関数値Ｆを算出する。この例では、評価関数値Ｆ＝-19.48284883となり、当該評価関数値Ｆを最小評価関数値保存部６に出力する。最小評価関数値保存部６は、評価関数値Ｆがmini_cost未満であることから、mini_costの値を-19.48284883に更新し、文字列開始点にＱ（１）を設定し、図１６で示した文字列配置を文字列データ記憶部７に格納し、処理を終了する。
【００５７】
さらに、同様の処理を繰り返し、２番目の候補点Ｑ（２）から文字列を配置する。この場合、７文字目までは図１７に示すように配置される。その後、文字列配置部４の文字配置位置算出部４３において、８文字目の文字の配置位置を算出する。ここでのdist＝１０１、road_idx＝１である。そのため、road_idx番目のノードＰ（１）から、road_idx番目のノードとroad_idx+1番目のノードを繋ぐリンクに沿ってdist離れた位置ＬＤ（７）を求める。計算の結果、ＬＤ（７）＝（１０１，５０）となる。
【００５８】
その後、文字リンク外判定部４４にて、ＬＤ（７）がリンク外か否かを判定する。ＬＤ（７）はリンク外であるため、第２のパラメータ更新部４８にてdistを更新する。この場合、dist＝１に更新される。その後、８文字目を配置するリンクは存在しないため、処理を終了する。即ち、候補点Ｑ（２）から文字列「String11」を配置することは不可能であるため、評価関数の算出は行わない。このように、０番目の文字列の文字列配置開始点を決定する。この場合、文字列「String11」の０番目の文字列の文字列配置開始点はＱ（１）となる。また、Ｑ（１）から道路ノード列に沿って配置した文字列配置（図１６参照）は、１番目以降の文字列の文字列配置開始点の最適化に用いる。
【００５９】
０番目の文字列「String11」の文字列配置点が決定されると、次に１番目の文字列である「String2」に対しても同様の処理を行う。まず、候補点作成部３において１番目の文字列が沿う道路リンク上に候補点を作成する。この場合、図１８に示すように、３つの候補点Ｑ（３）、Ｑ（４）、Ｑ（５）が作成される。続いて文字列配置部４が候補点Ｑ（３）から１番目の文字列を配置する（図１９参照）。その後、評価関数算出部５において評価関数値Ｆの算出を行う。
【００６０】
具体的には、ステップＳＴ５１として、初期文字列判定部５４はstring_idx＝１と判定し、ステップＳＴ５３として文字間隔関数更新部５６は上記式（７）に基づいて、文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）の値を、5.1×10-264と算出する。その後、文字間隔関数更新部５６の処理を繰り返して、文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）を更新し、最終的にＰ(Sstring_idx｜{Sstring_idx-1}）＝0.040705との値を得る。
【００６１】
続いて、ステップＳＴ５４として、道路角度関数更新部５８はＰ(Rstring_idx｜Sstring_idx）の値を、1.96618×10-53と算出する。ステップＳＴ５５として、評価関数値算出部５３は、文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）＝0.040705、および道路角度関数値Ｐ(Rstring_idx｜Sstring_idx）＝1.96618×10-53に基づいて、上述した式（１１）に基づいて評価関数値Ｆの算出を行う。この場合、Ｆ＝log1.96618×10-53+log0.040705＝-52.7063767-1.3936＝-54.0999767となる。ステップＳＴ５６として、算出した評価関数値Ｆを最小評価関数値保存部６に出力する。
【００６２】
その後、最小評価関数値保存部６は、算出された評価関数値Ｆがmin_cost未満であると判定し、min_cost＝-54.0999767、１番目の文字列の文字列配置開始点はＱ（３）と設定して最小評価関数値データ記憶部７および文字列配置開始点データ記憶部９に格納すると共に、図１９に示した文字列配置を文字列配置データ記憶部８に格納する。
【００６３】
その後、同様に文字列配置部４において、候補点Ｑ（４）から1番目の文字列「String2」を配置する（図２０参照）。文字間隔関数算出部５１は文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1})＝2.7947×10-166と算出する。その後、道路角度関数算出部５２において道路角度関数値Ｐ(Rstring_idx｜Sstring_idx）＝0.002850205と算出する。評価関数値算出部５３は、これらの値を用いて上述した式（１１）に基づいて評価関数値Ｆを算出する。この場合Ｆ＝log2.7947×10-166+log0.002850205＝-165.55367-2.244093909＝-167.7977639となる。最小評価関数値保存部６は、算出された評価関数値Ｆがmin_cost未満であると判定し、min_cost＝-167.7977639、１番目の文字列の文字列配置開始点はＱ（４）と設定する。
【００６４】
同様に、文字列配置部４において、Ｑ（５）から文字列を配置する。この場合、文字列をＱ（５）から配置すると、道路リンクの長さ不足となり配置することができないため、文字列配置失敗となり処理を終了する。上述した処理により、文字列「String2」の１番目の文字列の文字列配置開始点がＱ（４）に決定される。
【００６５】
以上のように、この実施の形態１によれば、評価関数算出部５に、文字列同士の文字間隔が文字列の可読性に与える影響を示す関数値を算出する文字間隔関数算出部５１を設けるように構成したので、文字列同士の重なり、および文字列が沿う道路の角度変化に加え、文字列同士の間隔が広くなるように、文字列の文字列配置開始点を最適位置に設定することができる。これにより、文字列同士の間隔が広がり、文字列の密集を抑制し、文字列の視認性を向上させることができる。
【００６６】
また、この実施の形態１によれば、文字間隔関数値を算出する際にガウス関数値を算出する第１のガウス関数値算出部５５を備えるように構成したので、道路ノードと既に配置した文字の中心座標にガウス分布を配置し、文字列同士の間隔が広くなるように、文字列配置開始点を最適位置に変更することができる。
【００６７】
なお、本願発明はその発明の範囲内において、実施の形態の任意の構成要素の変形、もしくは実施の形態の任意の構成要素の省略が可能である。
【産業上の利用可能性】
【００６８】
この発明に係る文字列配置装置は、表示装置などにおける視認性向上に利用することができると共に、ユーザの視認性を向上させたナビゲーション装置への適用などにも活用することができる。
【符号の説明】
【００６９】
１  文字列データ記憶部、２  文字列データ取得部、３  候補点作成部、４  文字列配置部、５  評価関数算出部、６  最小評価関数値保存部、７  最小評価関数値データ記憶部、８  文字列配置データ記憶部、９  文字列配置開始点データ記憶部、３１  第１のリンク長算出部、３２  リンク全長更新部、３３  候補点間隔算出部、３４  作成部、３５  第２のリンク長算出部、３６  距離更新部、３７  情報記憶部、４１  初期文字位置決定部、４２  リンク角度算出部、４３  文字配置位置算出部、４４  文字リンク外判定部、４５  文字配置部、４６  重なり判定部、４７  第１のパラメータ更新部、４８  第２のパラメータ更新部、５１  文字間隔関数算出部、５２  道路角度関数算出部、５３  評価関数値算出部、５４  初期文字列判定部、５５  第１のガウス関数値算出部、５６  文字間隔関数更新部、５７  第２のガウス関数値算出部、５８  道路角度関数更新部、１００  文字列配置装置。
【図１】
2013024505.tif 000011
【図２】
2013024505.tif 000012
【図３】
2013024505.tif 000013
【図４】
2013024505.tif 000014
【図５】
2013024505.tif 000015
【図６】
2013024505.tif 000016
【図７】
2013024505.tif 000017
【図８】
2013024505.tif 000018
【図９】
2013024505.tif 000019
【図１０】
2013024505.tif 000020
【図１１】
2013024505.tif 000021
【図１２】
2013024505.tif 000022
【図１３】
2013024505.tif 000023
【図１４】
2013024505.tif 000024
【図１５】
2013024505.tif 000025
【図１６】
2013024505.tif 000026
【図１７】
2013024505.tif 000027
【図１８】
2013024505.tif 000028
【図１９】
2013024505.tif 000029
【図２０】
2013024505.tif 000030
【図２１】
2013024505.tif 000031
【図２２】
2013024505.tif 000032
【図２３】
2013024505.tif 000033
【手続補正書】
【提出日】平成25年10月2日(2013.10.2)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、地図などの図形上に文字列を配置する文字列配置装置に関するものである。
【背景技術】
【０００２】
従来の地図表示装置は、道路名称等の文字列を、文字列の配置を開始する点(以下、文字列配置開始点と称する)から、道路線(以下、道路ノード列と称する)に沿って配置する機能を備えている（例えば、図２１参照）。この場合、文字列配置開始点が適切でなければ、図２２（ａ）に示す文字列同士の重なり、図２２（ｂ）に示す文字の表示角度の変化による可読性の低下、図２２（ｃ）に示す文字列の密集による可読性の低下が起こる。
【０００３】
図２２（ａ）に示す文字列同士の重なり、および図２２（ｂ）に示す可読性の低下を解決する方法として、例えば非特許文献１には可読性が高い位置に文字列配置開始点を変更する方法が記載されている。具体的には、図２３（ａ）に示す文字列同士の重複を示す関数overlap(i)と、図２３（ｂ）に示す文字列が沿う道路ノード列の角度変化を示す関数flatness(i)で構成される、以下の式（１）で示す評価関数ｆを最小化することにより、文字列配置開始点を変更する方法である。なお、式（１）中のα1とα2はoverlap(i)とflatness(i)の値を調整するパラメータであり、String_numは文字列数を示す。
2013024505.tif 000034
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Shawn Edmondson, “A General Cartographic Labeling Algorithm”, The International Journal for Geographic Information and Geovisualization, Volume 33, Number 4/ Winter 1996
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した非特許文献１の方法は、図２２（ａ）で示した文字列同士の重複、および図２２（ｂ）で示した文字列が沿う道路の角度変化による可読性低下を解決する方法であるため、図２２（ｃ）に示す文字列の密集による可読性低下を避けることができないという課題があった。
【０００６】
この発明は、上記のような課題を解決するためになされたもので、文字列の重複、文字の表示角度の変化だけでなく、文字列の密集度合いも加味して文字列配置開始点を最適な位置に変更する文字列配置装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
この発明に係る文字列配置装置は、道路ノード列上の複数の候補点に配置した文字列の配置に対する評価を示す評価関数値を算出する評価関数算出部を備えた文字列配置装置において、評価関数算出部は、複数の候補点に配置した複数の文字列間の文字間隔に対する評価を示す文字間隔関数値を算出する文字間隔関数算出部と、複数の候補点に配置した文字列が沿う道路ノード列の角度に対する評価を示す道路角度関数値を算出する道路角度関数算出部と、文字間隔関数値および道路角度関数値に基づいて評価関数値を算出する評価関数値算出部とを備えるものである。
【発明の効果】
【０００８】
この発明によれば、文字列同士の重なり、および文字の表示角度の変化による可読性の低下を抑制すると共に、文字列の密集を抑制することが可能となり、文字列の視認性を向上させることができる。
【図面の簡単な説明】
【０００９】
【図１】実施の形態１による文字列配置装置の構成を示すブロック図である。
【図２】実施の形態１による文字列配置装置の動作を示すフローチャートである。
【図３】実施の形態１による文字列配置装置の候補点作成部の構成を示すブロック図である。
【図４】実施の形態１による文字列配置装置の文字列配置部の構成を示すブロック図である。
【図５】実施の形態１による文字列配置装置の評価関数算出部の構成を示すブロック図である。
【図６】文字列を配置する道路ノード列の関係を示す図である。
【図７】実施の形態１による文字列配置装置の候補点作成部の動作を示すフローチャートである。
【図８】実施の形態１による文字列配置装置の候補点作成結果を示す図である。
【図９】実施の形態１による文字列配置装置の文字列配置部の動作を示すフローチャートである。
【図１０】実施の形態１による文字列配置装置の配置結果を示す図である。
【図１１】実施の形態１による文字列配置装置の配置結果を示す図である。
【図１２】実施の形態１による文字列配置装置の配置結果を示す図である。
【図１３】実施の形態１による文字列配置装置の配置結果を示す図である。
【図１４】実施の形態１による文字列配置装置の評価関数算出部の動作を示すフローチャートである。
【図１５】実施の形態１による文字列配置装置のリンク角度の算出例を示す説明図である。
【図１６】実施の形態１による文字列配置装置の配置例を示す図である。
【図１７】実施の形態１による文字列配置装置の配置例を示す図である。
【図１８】実施の形態１による文字列配置装置の候補点作成結果を示す図である。
【図１９】実施の形態１による文字列配置装置の配置例を示す図である。
【図２０】実施の形態１による文字列配置装置の配置例を示す図である。
【図２１】従来の文字列の配置を示す説明図である。
【図２２】従来の文字列の配置を示す説明図である。
【図２３】従来の文字列の配置の可読性向上を示す説明図である。
【発明を実施するための形態】
【００１０】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
実施の形態１．
図１は、この発明の実施の形態１による文字列配置装置の構成を示すブロック図である。
文字列配置装置１００は、文字列データ記憶部１、文字列データ取得部（データ取得部）２、候補点作成部３、文字列配置部４、評価関数算出部５、最小評価関数値保存部６、最小評価関数値データ記憶部７、文字列配置データ記憶部８および文字列配置開始点データ記憶部９で構成されている。
【００１１】
文字列データ記憶部１は、複数の文字列のデータ集合を記憶する記憶領域であって、文字列の個数、各々の文字列が含む文字数、文字毎の横幅・縦幅、文字列が沿う道路ノード列を格納する。文字列データ取得部２は、文字列データ記憶部１に記憶された文字列データを取得する。候補点作成部３は、文字列が沿う道路ノード上に文字列の配置候補（以下、候補点と称する）を複数作成する。文字列配置部４は、文字列を候補点から道路ノード列に沿って配置する。
【００１２】
評価関数算出部５は、配置した文字列の可読性を数値化する。最小評価関数値保存部６は、評価関数が最小値となる際の評価関数値、文字列配置および文字列配置開始点を各記憶領域に格納させる。最小評価関数値データ記憶部７は、最小の評価関数値を保存する記憶領域である。文字列配置データ記憶部８は、最小の評価関数値を取る時の文字列配置を保存する記憶領域である。文字列配置開始点データ記憶部９は、評価関数値が最小の時の文字列配置開始点を保存する記憶領域である。
【００１３】
次に、文字列配置装置の動作について説明する。
図２は、この発明の実施の形態１による文字列配置装置の動作を示すフローチャートである。
文字列データ取得部２は、文字列データ記憶部１を参照し、配置する文字列データを取得する（ステップＳＴ１）。候補点作成部３は、ステップＳＴ１で取得した文字列が沿う道路ノード列上に、当該文字列を配置する候補点を作成する（ステップＳＴ２）。文字列配置部４は、ステップＳＴ２で作成された候補点から道路ノード列に沿って文字列を配置する（ステップＳＴ３）。さらに文字列配置部４は、ステップＳＴ３の配置結果を参照し、道路ノード列に沿って文字列の配置が可能か否か判断する（ステップＳＴ４）。例えば、道路ノード列から文字列がはみ出しているなどの場合には、配置不可能であると判断するなどである。道路ノード列に沿って文字列の配置が不可能であると判断した場合（ステップＳＴ４；ＮＯ）、処理を終了する。
【００１４】
一方、道路ノード列に沿って文字列の配置が可能である場合（ステップＳＴ４；ＹＥＳ）、評価関数算出部５は配置した文字列の評価関数値を算出する（ステップＳＴ５）。最小評価関数値保存部６は、ステップＳＴ５で算出された評価関数値が、最小評価関数値データ記憶部７に既に記憶されている最小評価関数値mini_cost未満であるか判定を行う（ステップＳＴ６）。評価関数値が最小評価関数値mini_cost以上である場合（ステップＳＴ６；ＮＯ）には、処理を終了する。一方、評価関数値が最小評価関数値mini_cost未満である場合（ステップＳＴ６；ＹＥＳ）には、最小評価関数値保存部６が、ステップＳＴ５で算出された評価関数値を最小評価関数値データ記憶部７に格納する（ステップＳＴ７）と共に、文字列配置に関するデータおよび文字列配置開始点に関するデータを文字列配置データ記憶部８および文字列配置開始点データ記憶部９に格納し（ステップＳＴ８）、処理を終了する。
【００１５】
続いて、文字列配置装置１００のより詳細な構成および動作について説明する。
図３から図５は文字列配置装置１００の各構成をより詳細に示したブロック図であり、図３は候補点作成部３の構成を示すブロック図、図４は文字列配置部４の構成を示すブロック図、図５は評価関数算出部５の構成を示すブロック図である。
まず、図３に示すように、候補点作成部３は、道路ノード列中の２つのノードを結ぶリンクの長さを算出する第１のリンク長算出部３１と、第１のリンク長算出部３１で算出したリンクの長さを加算して道路ノード列の全長を求めるリンク全長更新部３２と、リンクの全長から候補点の間隔を算出する候補点間隔算出部３３と、道路ノード列上に候補点を作成する作成部３４と、設定されたリンク長が所定の条件を満たさない場合に、ノードを更新してリンクの長さを算出する第２のリンク長算出部３５と、第２のリンク長算出部３５が算出したリンクの長さに基づいてリンク長を更新する距離更新部３６と、候補点間隔（cand_gap）、候補点番号（cand_idx）、道路ノード列の先頭ノードから所定のノードを繋ぐリンク長（dist）など、候補点に関する情報を記憶する情報記憶部３７で構成される。
【００１６】
次に、図４に示すように、文字列配置部４は、文字列の１文字目の位置を設定する初期文字位置決定部４１と、リンクの角度を算出するリンク角度算出部４２と、文字の配置位置を算出する文字配置位置算出部４３と、文字がリンク外か否かを判定する文字リンク外判定部４４と、文字の配置を設定する文字配置部４５と、前に配置した文字との重なりを判定する重なり判定部４６と、文字がリンク上に存在し、且つ文字の重なりがない場合に文字の配置に必要なパラメータを更新する第１のパラメータ更新部（パラメータ更新部）４７と、文字がリンク外に位置している場合に文字の配置に必要なパラメータを更新する第２のパラメータ更新部４８で構成される。
【００１７】
次に、図５に示すように、評価関数算出部５は、文字列同士の文字間隔が文字列の可読性に与える影響を示す関数値を算出する文字間隔関数算出部５１と、道路の角度が文字列の可読性に与える影響示す関数値を算出する道路角度関数算出部５２と、評価関数値を算出する評価関数値算出部５３で構成される。さらに、文字間隔関数算出部５１は、初めの文字列か否かを判定する初期文字列判定部５４と、ガウス関数の値を算出する第１のガウス関数値算出部５５と、文字列同士の文字間隔が文字列の可読性に与える影響を示す関数値を更新する文字間隔関数更新部５６で構成されている。また、道路角度関数算出部５２は、ガウス関数の値を算出する第２のガウス関数値算出部５７と、道路の角度が文字列の可読性に与える影響を示す関数値を更新する道路角度関数更新部５８で構成されている。
【００１８】
次に、候補点作成部３、文字列配置部４および評価関数算出部５の詳細な動作について説明する。なお、以下の動作説明では、道路ノード列に配置する文字列データは、文字列「String11」および文字列「String2」から成るデータであり、各々の文字の横幅は全て５であり、縦幅は全て１０として説明を行う。また、文字列「String11」および文字列「String2」が配置される道路ノード列の関係を図６に示す。文字列「String11」が沿う道路ノード列Ｐ（０）−Ｐ（２）は、ノードＰ（０）＝（１０，２０）、ノードＰ（１）＝（１０，５０）、ノードＰ（２）＝（１００，５０）で構成される。同様に文字列「String2」が沿う道路ノード列Ｐ（３）−Ｐ（５）は、ノードＰ（３）＝（５０，７０）、ノードＰ（４）＝（５０，１０）、ノードＰ（５）＝（１１０，１０）で構成される。さらに、STEP_SIZEを１とし、CANDIDATE_NUM（候補点数）を３とし、Σを以下の式（２）とし、Ｈを以下の式（３）とし、ＲＣを１とし、ＳＣを１とする。
2013024505.tif 000035
【００１９】
まず、図２で示したフローチャートのステップＳＴ１として、文字列データ取得部２が、文字列データ記憶部１から１つ目の文字列「String11」と、２つ目の文字列「String2」と、各々の文字列が配置される道路ノード列Ｐ（０）−Ｐ（２）および道路ノード列Ｐ（３）−Ｐ（５）と、各々の文字列を構成する各文字の横幅および縦幅を取得する。次に、１つ目の文字列「String11」の配置最適化を行う。その方法として、まず候補点作成部３が文字列「String11」が沿う道路ノード列Ｐ（０）−Ｐ（２）上にあらかじめ設定されたCANDIDATE_NUM個の候補点、すなわち３つの候補点を等間隔に作成する。
【００２０】
具体的な候補点作成方法を、図７のフローチャートを参照しながら説明する。図７は、実施の形態１による文字列配列装置の候補点作成部の動作を示すフローチャートである。
候補点作成部３の第１のリンク長算出部３１は、情報記憶部３７に記憶された各ノード情報を参照し、ｎ番目のノードＰ（ｎ）とｎ＋１番目のノードＰ（ｎ＋１）を繋ぐリンクの長さを算出する（ステップＳＴ１１）。リンク全長更新部３２は、第１のリンク長算出部３１がリンク長を算出すると、前回算出したリンク全長に加算してリンク全長（total_dist）の値を更新する（ステップＳＴ１２）。
【００２１】
第１のリンク長算出部３１は、道路ノード列を構成する全てのリンクの長さを算出したか判定を行う（ステップＳＴ１３）。全てのノードについてリンクの長さを算出していない場合（ステップＳＴ１３；ＮＯ）には、ステップＳＴ１１の処理に戻り、上述した処理を繰り返す。一方、全てのノードについてリンクの長さを算出した場合（ステップＳＴ１３；ＹＥＳ）には、候補点間隔算出部３３は情報記憶部３７を参照して候補点数（CANDIDATE_NUM）を取得し、以下の式（４）に基づいて候補点の間隔を算出し、算出した候補点間隔（cand_gap）を情報記憶部３７に記憶させる（ステップＳＴ１４）。
ｃａｎｄ＿ｇａｐ＝ｔｏｔａｌ＿ｄｉｓｔ／ＣＡＮＤＩＤＡＴＥ＿ＮＵＭ・・・（４）
【００２２】
次に、作成部３４は、情報記憶部３７を参照して候補点間隔（cand_gap）、候補点番号（cand_idx）、道路ノード列の先頭ノードから所定のノードを繋ぐリンク長（dist）に関する情報を取得し、候補点が以下の式（５）で示す条件を満たすか判定を行う（ステップＳＴ１５）。
ｄｉｓｔ＞ｃａｎｄ＿ｉｄｘ×ｃａｎｄ＿ｇａｐ・・・（５）
なお、候補点番号（cand_idx）の初期値は０であり、初期のリンク長(dist)は、道路ノード列の先頭ノードと、当該先頭ノードの次の位置に配置されたノードを繋ぐリンクの長さとなる。当該初期条件は予め情報記憶部３７に記憶されているものとする。
【００２３】
上記式（５）の条件を満たす場合（ステップＳＴ１５；ＹＥＳ）、作成部３４は道路ノード列の先頭ノードから、当該道路ノード列に沿って、候補点番号（cand_idx）×候補点間隔（cand_gap）離れた位置に候補点Ｑを作成する（ステップＳＴ１６）。その後作成部３４は、CANDIDATE_NUM個全ての候補点Ｑを作成したか否か判定を行う（ステップＳＴ１７）。全ての候補点を作成した場合（ステップＳＴ１７；ＹＥＳ）には、処理を終了する。一方、全ての候補点Ｑを作成していない場合（ステップＳＴ１７；ＮＯ）、候補点番号を１加算して情報記憶部３７に記憶させ（cand_idx+1、ステップＳＴ１８）、ステップＳＴ１５の処理に戻る。
【００２４】
また、上記式（５）の条件を満たさない場合（ステップＳＴ１５；ＮＯ）、ステップＳＴ１５の判定処理におけるノード番号に１を加算し（ステップＳＴ１９）、加算後のノードと、当該加算後のノードの次の位置に配置されたノードとを繋ぐリンクの長さを算出する（ステップＳＴ２０）。距離更新部３６は、ステップＳＴ１５の判定処理に用いたリンク長（dist）にステップＳＴ２０で新たに算出したリンクの長さを加算し、リンク長（dist）を更新する（ステップＳＴ２１）。なお、ステップＳＴ１９からステップＳＴ２１で更新された情報は、情報記憶部３７に記憶される。その後、フローチャートはステップＳＴ１５の処理に戻る。
【００２５】
次に、図７に示したフローチャートに沿って、図６で示した具体例を用いて説明を行う。
ステップＳＴ１１として、第１のリンク長算出部３１は、０番目のノードＰ（０）と１番目のノードＰ（１）のノードを繋ぐリンクの長さ：３０を算出する。ステップＳＴ１２として、リンク全長更新部３２は前回までに算出したリンク全長：０にリンクの長さ：３０を加算して、リンク全長を更新する。同様に、１番目のノードＰ（１）と２番目のノードＰ（２）のノードを繋ぐリンクの長さ：９０を算出し、リンク全長：１２０に更新する。ステップＳＴ１３で道路ノード列Ｐ（０）−Ｐ（２）を構成する全てのリンクの長さを算出したと判定されると、ステップＳＴ１４として、候補点間隔算出部３３は情報記憶部３７を参照して候補点数（CANDIDATE_NUM）＝３を取得し、候補点間隔（cand_gap）：１２０／３＝４０を算出する。
【００２６】
ステップＳＴ１５として、作成部３４は情報記憶部３７を参照して候補点間隔（cand_gap）：４０、候補点番号（cand_idx）：０（初期値）、リンク長（dist）：３０（初期リンク（Ｐ（０），Ｐ（１））を取得し、候補点Ｑ（０）が上記式（５）の条件を満たすか判定を行う。図６の例では、３０＞０×４０であることから、式（５）の条件を満たすと判定する。
【００２７】
ステップＳＴ１６として、作成部３４は開始ノードＰ（０）から０×４０＝０離れた位置に候補点Ｑ（０）を作成する。即ち、０番目の候補点Ｑ（０）は、Ｐ（０）と同一地点となる。なお、候補点Ｑ（０）は、位置（１０，２０）、候補点Ｑ（０）が存在するリンク（Ｐ（０），Ｐ（１））の開始ノードのインデックス：０、候補点が存在するリンクの開始ノードＰ（０）からの距離：０となる。ステップＳＴ１７として、作成部３４は全ての候補点を作成していないと判定し、ステップ１８として候補点番号に１加算して候補点Ｑ（１）とし、ステップＳＴ１５の処理に戻る。
【００２８】
続いて、候補点Ｑ（１）の作成処理について説明する。
ステップＳＴ１５として、作成部３４は情報記憶部３７を参照して候補点間隔（cand_gap）：４０、候補点番号（cand_idx）：１、リンク長（dist）：３０（初期リンク（Ｐ（０），Ｐ（１））を取得し、候補点Ｑ（１）が上記式（５）の条件を満たすか判定を行う。図６の例では、３０＜１×４０であることから、式（５）の条件を満たさないと判定する。そこでステップＳＴ１９，２０として、ノードＰ（０）のノード番号に１を加算してノードＰ（１）とし、ノードＰ（１）とノードＰ（２）とを繋ぐリンクの長さ：９０を算出する。ステップＳＴ２１として、距離更新部３６は、上述したステップＳＴ１５の判定処理に用いたリンク長（dist）：３０に算出したリンク長：９０を加算した値をリンク長（dist）：１２０に更新する。更新した情報を情報記憶部３７に記憶させた後、ステップＳＴ１５の処理に戻る。
【００２９】
ステップＳＴ１５として、作成部３４は情報記憶部３７を参照して候補点間隔（cand_gap）：４０、候補点番号（cand_idx）：１、リンク長（dist）：１２０（リンク（Ｐ（０），Ｐ（２）））を取得し、候補点Ｑ（１）が上記式（５）の条件を満たすか判定を行う。図６の例では、１２０＞１×４０であることから、式（５）の条件を満たすと判定する。ステップＳＴ１６として、作成部３４は開始ノードＰ（０）から１×４０＝４０離れた位置に候補点Ｑ（１）を作成する。その後、ステップＳＴ１７として、作成部３４は全ての候補点を作成していないと判定し、ステップ１８として候補点番号に１加算して候補点Ｑ（２）とし、ステップＳＴ１５の処理に戻る。候補点Ｑ（２）を作成するまで、上述した処理を繰り返し行う。
【００３０】
図６に示した道路ノード列Ｐ（０）−Ｐ（２）に対して候補点を作成した結果を図８に示している。また、図８に示した３つの候補点Ｑ（０），Ｑ（１），Ｑ（２）の位置関係は以下に示すとおりである。
候補点Ｑ（０）  位置：（１０，２０）、開始ノードのインデックス：０、開始ノードからの距離：０
候補点Ｑ（１）  位置：（２０，５０）、開始ノードのインデックス：１、開始ノードからの距離：１０
候補点Ｑ（２）  位置：（６０，５０）、開始ノードのインデックス：１、開始ノードからの距離：５０
【００３１】
次に、候補点作成部３が作成した候補点Ｑに、文字列配置部４が文字列を配置する動作について説明する。
図９は、実施の形態１による文字列配置装置の文字列配置部の動作を示すフローチャートである。
なお、以下では、候補点Ｑが存在するリンクＲ（Ｑ）の開始ノードのインデックスをroad_idxとし、候補点Ｑが存在する道路ノード列の先頭ノードから候補点Ｑまでの距離をdistと記載する。
【００３２】
初期文字位置決定部４１は、処理開始時にroad_idxとdistの初期設定を行う（ステップＳＴ３１）。次にリンク角度算出部４２は、road_idx（ｎ）番目のノードとroad_idx（ｎ＋１）番目のノードを繋ぐリンクの角度θを算出する（ステップＳＴ３２）。ここでリンクの角度θは、Ｘ軸方向を０°、Ｙ軸方向を９０°とし、リンク（road_idx（ｎ），road_idx（ｎ＋１））の角度、即ちベクトル（road_idx（ｎ），road_idx（ｎ＋１））の角度とする。文字配置位置算出部４３は、road_idx（ｎ）番目のノードからθ方向に、dist分離れた位置を文字配置位置として算出する（ステップＳＴ３３）。
【００３３】
文字リンク外判定部４４は、文字配置位置がリンク（road_idx（ｎ），road_idx（ｎ＋１））上に存在するか判定を行う（ステップＳＴ３４）。文字配置位置がリンク（road_idx（ｎ），road_idx（ｎ＋１））上に存在する場合（ステップＳＴ３４；ＹＥＳ）、文字配置部４５が文字の配置位置を決定する（ステップＳＴ３５）。具体的な処理としては、まずステップＳＴ３３で文字配置位置算出部４３が算出した文字列配置位置の座標を文字の左下座標に設定する。さらに、次の式（６）に基づいて文字の左上座標、右下座標、右上座標を算出する。
【００３４】
2013024505.tif 000036
【００３５】
なお、式（６）において、char_idxは、文字列を構成する文字の配置順を示すインデックスである。さらに、H(char_idx)はchar_idx番目の文字の縦幅、W(char_idx)はchar_idx番目の文字の横幅、LD(char_idx)はchar_idx番目の文字の左下座標、LT(char_idx)はchar_idx番目の文字の左上座標、RD(char_idx)はchar_idx番目の文字の右下座標、RT(char_idx)はchar_idx番目の文字の右上座標を示す。
【００３６】
重なり判定部４６は、ステップＳＴ３５で決定した配置位置が、前回の処理で配置した文字と重なるか判定を行う（ステップＳＴ３６）。文字の重なりがない場合（ステップＳＴ３６；ＮＯ）、第１のパラメータ更新部４７が、distにchar_idx番目の文字の横幅を加算すると共に、char_idxを「１」増加させる（ステップＳＴ３７）。その後、第１のパラメータ更新部４７は、文字列を構成する全ての文字の配置位置を求めたか否か判定を行う（ステップＳＴ３８）。全ての文字の配置位置を求めた場合（ステップＳＴ３８；ＹＥＳ）処理を終了する。一方、全ての文字の配置位置を求めていない場合（ステップＳＴ３８；ＮＯ）、第１のパラメータ更新部４７は、文字配置位置算出部４３に対して、ステップＳＴ３７で更新したパラメータに基づき再度配置位置の算出を指示する（ステップＳＴ３９）。その後、ステップＳＴ３３の処理に戻り、上述した処理を繰り返す。
【００３７】
一方、文字の重なりがある場合（ステップＳＴ３６；ＹＥＳ）、重なり判定部４６はdistにSTEP_SIZEを加算し（ステップＳＴ４０）、文字配置位置算出部４３に対して、ステップＳＴ４０で加算したパラメータに基づき再度配置位置の算出を指示する（ステップＳＴ４１）。その後、ステップＳＴ３３の処理に戻り、上述した処理を繰り返す。
【００３８】
さらに、文字配置位置がリンク上の存在していない場合（ステップＳＴ３４；ＮＯ）、第２のパラメータ更新部４８においてパラメータの更新を行う（ステップＳＴ４２）。具体的には、第２のパラメータ更新部４８が、distからリンク（road_idx（ｎ），road_idx（ｎ＋１））の長さを引いた値をdistに更新すると共に、road_idxに１を加算した後、文字配置位置算出部４３に対して、更新したパラメータに基づき再度配置位置の算出を指示する（ステップＳＴ４３）。その後、ステップＳＴ３２の処理に戻り、上述した処理を繰り返す。
【００３９】
次に、図９に示したフローチャートに沿って、図６および図８で示した具体例を用いて説明を行う。
まず、ステップＳＴ３１として、初期文字位置決定部４１は、road_idxとdistの初期設定を行い、候補点Ｑ（０）の開始ノードのインデックス：０をroad_idx、道路ノード列Ｐ（０）−Ｐ（２）の先頭ノードＰ（０）から候補点Ｑまでの距離：０をdistとする。ステップＳＴ３２として、リンク角度算出部４２は、リンク（Ｐ（０），Ｐ（１））の角度θ＝９０°を算出する。ステップＳＴ３３として、文字配置位置算出部４３は、road_idx＝０番目のノードからθ＝９０°の方向にdist＝０離れた位置ＬＤ(０)＝(１０，２０)を文字列配置位置として算出する。
【００４０】
ステップＳＴ３４の判定処理において、文字リンク外判定部４４は、ＬＤ(０)がリンク（Ｐ（０），Ｐ（１））上に存在すると判定する。ステップＳＴ３５として、文字配置部４５は、文字列「String11」の０番目の文字「S」の配置位置を決定する。まずＬＤ(０)を文字「S」の左下座標に設定し、次にＬＴ(０)＝(０，２０)を文字「S」の左上座標に設定する。その後、ＲＤ(０)＝(１０，２５)を文字「S」の右下座標に設定する。最後にＲＴ(０)＝(０，２５)を文字「S」の右上座標に設定する。文字「S」の外接矩形の配置を図１０に示す。ステップＳＴ３６として、重なり判定部４６がステップＳＴ３５で配置した文字「S」と前回配置した文字の重なりを判定するが、この例では前回配置した文字が存在しないことから、重なりは無いと判定する。
【００４１】
ステップＳＴ３７として第１のパラメータ更新部４７は、distに０番目の横幅「５」を付加してdist＝０＋５＝５とし、char_idxに「１」を付加してchar_idx＝０＋１＝１とする。ステップＳＴ３８として、第１のパラメータ更新部４７は、文字列を構成する全ての文字の配置位置を求めていないと判定するため、ステップＳＴ３９として文字配置位置算出部４３に更新後のパラメータに基づいて、再度配置位置の算出を指示し、ステップＳＴ３３の処理に戻る。
【００４２】
ステップＳＴ３９の指示を受けた文字配置位置算出部４３は、２文字目「ｔ」の文字配置位置を算出する。算出は、ステップＳＴ３７で更新したdist＝５、およびchar_idx＝１に基づいて行われる。ステップＳＴ３３として文字配置位置算出部４３は、位置ＬＤ（１）＝（１０，２５）を文字列配置位置として算出する。さらにステップＳＴ３４からステップＳＴ３６の処理を行い、ＬＤ（１）はリンク（Ｐ（０），Ｐ（１））上に存在し、２文字目「t」の左下座標、左上座標、右下座標、右上座標は、それぞれＬＤ（１）＝（１０，２５）、ＬＴ（１）＝（０，２５）、ＲＤ（１）＝（１０，３０）、ＲＴ（１）＝（０，３０）となる。２文字目「t」の外接矩形の配置を図１１に示す。ステップＳＴ３６において、１文字目に配置した文字と、２文字目に配置した文字が重なっていると判定されるため、ステップＳＴ４０として重なり判定部４６がdistにSTEP_SIZE＝１を加算し、ステップＳＴ４１として加算後のパラメータに基づいて再度２文字目「t」の文字配置位置を算出するように文字配置位置算出部４３に指示する。
【００４３】
再度ステップＳＴ３３からステップＳＴ３６の処理を繰り返し、２文字目「ｔ」の文字配置位置を算出する。算出は、ステップＳＴ４０で加算されたdist＝６、およびchar_idx＝１に基づいて行われる。図１２に、上述した処理を繰り返し２文字目ＬＤ（１）から６文字目ＬＤ（５）までを配置した結果を示している。なお、図１２では、各文字の左下座標のみを記載している。
【００４４】
６文字目を配置した後、文字配置位置算出部４３は文字列「String11」の７文字目「1」の配置位置を算出する。この時、dist＝３５、cand_idx＝６、road_idx＝０であるため、road_idx番目のノードからθの方向にdist離れた位置は、ＬＤ（６）＝（１０，５５）となる。ステップＳＴ３４として、文字リンク外判定部４４は配置位置（１０，５５）がリンク（Ｐ（０），Ｐ（１））外であると判定し、ステップＳＴ４２として第２のパラメータ更新部４８がパラメータの更新を行う。具体的には、０番目のノードと１番目のノードを繋ぐリンクの長さは「３０」であるため、dist＝３５−３０＝５に更新され、road_idx＝０＋１＝１となる。その後ステップＳＴ４３として、第２のパラメータ更新部４８により更新されたパラメータに基づいて、再度配置位置の算出を指示し、ステップＳＴ３２の処理に戻る。
【００４５】
ステップＳＴ３２として、リンク角度算出部４２は更新されたパラメータに基づいて、リンク（Ｐ（１），Ｐ（２））の角度θ＝０°を算出する。以降、上記と同様の処理を行い、７文字目および８文字目の配置を行い、ステップＳＴ３８の判定処理において、全ての文字の配置位置を求めたと判定され、処理を終了する。全ての文字を配置した結果を図１３に示している。図１３においても、各文字の左下座標のみを記載している。
【００４６】
次に、配置した文字列が可読性に与える影響を示す評価関数値を算出する方法について説明する。図１４は、実施の形態１による文字列配置装置の評価関数算出部の動作を示すフローチャートである。
まず、文字間隔関数算出部５１は、既に配置が決定した文字列（０番目からstring_idx-1番目の文字列)と、string_idx(n)番目の文字列との文字間隔を示す関数である文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）を算出する。具体的には、文字間隔関数算出部５１の初期文字列判定部５４が、string_idx＝０、またはstring_idx≧１であるか判定を行う（ステップＳＴ５１）。ステップＳＴ５１においてstring_idx＝０であると判定した場合、文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）に「１」を設定し（ステップＳＴ５２）、道路角度関数算出部５２の処理に進む。
【００４７】
一方、ステップＴ５１においてstring_idx≧１以上であると判定した場合、文字間隔関数更新部５６が以下の式（７）に基づいて文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1})算出を行い（ステップＳＴ５３）、道路角度関数算出部５２の処理に進む。
2013024505.tif 000037
上記式（７）において、Ｃstring_idx、Ｃstring_idx2は、それぞれstring_idx番目、string_idx２番目の文字列の文字数を示している。また、式（７）におけるｘchar_idx、ｘchar_idx2はそれぞれ、char_idx番目、char_idx2番目の文字の中心座標を示す。
【００４８】
なお、上記式（７）中のＮ´（ｘchar_idx｜ｘchar_idx2）は、第１のガウス関数出部５５により以下の式（８）に基づいて算出される。
2013024505.tif 000038
上記式（８）において、ｘchar_idx、ｘchar_idx2はそれぞれ、char_idx番目、char_idx2番目の文字の中心座標を示し、ＳＣは定数、Ｈ-1は共分散行列を示している。
【００４９】
道路角度関数更新部５８は、以下の式（９）に基づいて道路角度関数値Ｐ(Rstring_idx｜Sstring_idx）を算出する（ステップＳＴ５４）。
2013024505.tif 000039
上記式（９）中のＮｏstring_idxは、string_idx番目の文字列が沿う道路ノード列のノード数、μroad_idxは道路ノード列中のroad_idx番目のノードの座標を示す。
【００５０】
なお、上記式（９）中のＮ(ｘchar_idx|μroad_idx)は、第２のガウス関数値算出部５７により以下の式（１０）に基づいて算出される。
2013024505.tif 000040
【００５１】
上記式（１０）において、ｘchar_idx、μroad_idxは位置座標を示すベクトルであり、ｘchar_idxはchar_idx番目の文字の中心、μroad_idxはroad_idx番目の道路ノードを示す。また、Ｔは転置を示し、Σ-1はΣの逆行列を示す。なお、上記式（１０）におけるAngle(road_idx)は、road_idx-1番目のノードとroad_idx番目のノードを繋ぐリンクと、road_idx+1番目のノードとroad_idx番目のノードを繋ぐリンクの角度変化を示す。Angle(road_idx)の算出例を図１５に示す。図１５におけるR(road_idx)は、road_idx番目の道路ノードを示す。図１５に示すように、２つのリンクの角度変化が、リンクの角度変化となる。
【００５２】
評価関数値算出部５３は、ステップＳＴ５２またはステップＳＴ５３で算出された文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1})、およびステップＳＴ５４で算出された道路角度関数値Ｐ(Rstring_idx｜Sstring_idx）を用いて、以下の式（１１）に基づいて評価関数値Ｆを算出する（ステップＳＴ５５）。
2013024505.tif 000041
算出した評価関数値Ｆは、最小評価関数値保存部６に出力され（ステップＳＴ５６）、処理を終了する。
【００５３】
次に、図１４で示したフローチャートに沿って、図１３で示した具体例を用いて説明を行う。
ステップＳＴ５１として、初期文字列判定部５４はstring_idx=0、あるいはstring_idx≧1以上であるか判定を行う。まず、初回の判定であることから、ここではstring_idx=0となり、ステップＳＴ５２として文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）に「１」を設定する。
【００５４】
続いて、ステップＳＴ５４として、道路角度関数更新部５８は上記式（９）に基づいてＰ(Rstring_idx｜Sstring_idx）の値を、2.36036×10-85と算出する。その後、道路角度関数更新部５８はchar_idxおよびroad_idxを更新してステップＳＴ５４の処理を繰り返し、最終的にＰ(Rstring_idx｜Sstring_idx）＝0.000777442との値を得る。
【００５５】
ステップＳＴ５５として、評価関数値算出部５３は、ステップＳＴ５２で算出した文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）＝１、およびステップＳＴ５４で最終的に得た道路角度関数値Ｐ(Rstring_idx｜Sstring_idx）＝0.000777442に基づいて、上述した式（１１）に基づいて評価関数値の算出を行い、評価関数値Ｆ＝log0.000777442+log1＝-3.109331764を得る。ステップＳＴ５６として、算出した評価関数値Ｆを最小評価関数値保存部６に出力する。最小評価関数値保存部６は、算出された評価関数値Ｆがmin_cost未満であると判定し、min_costの値にＦ＝-3.109331764を設定して最小評価関数値データ記憶部７に格納すると共に、０番目の文字列の文字列開始点にＱ（０）を設定して文字列配置開始点データ記憶部９に格納し、図１３で示した文字列配置を文字列配置データ記憶部８に格納し、処理を終了する。
【００５６】
その後、上述した処理を繰り返し、文字列配置部４において、１番目の候補点Ｑ（１）から０番目の文字列を配置する。この場合の配置例を図１６に示す。評価関数値算出部５３は、図１６に示した配置例について評価関数値Ｆを算出する。この例では、評価関数値Ｆ＝-19.48284883となり、当該評価関数値Ｆを最小評価関数値保存部６に出力する。最小評価関数値保存部６は、評価関数値Ｆがmini_cost未満であることから、mini_costの値を-19.48284883に更新し、文字列開始点にＱ（１）を設定し、図１６で示した文字列配置を文字列データ記憶部７に格納し、処理を終了する。
【００５７】
さらに、同様の処理を繰り返し、２番目の候補点Ｑ（２）から文字列を配置する。この場合、７文字目までは図１７に示すように配置される。その後、文字列配置部４の文字配置位置算出部４３において、８文字目の文字の配置位置を算出する。ここでのdist＝１０１、road_idx＝１である。そのため、road_idx番目のノードＰ（１）から、road_idx番目のノードとroad_idx+1番目のノードを繋ぐリンクに沿ってdist離れた位置ＬＤ（７）を求める。計算の結果、ＬＤ（７）＝（１０１，５０）となる。
【００５８】
その後、文字リンク外判定部４４にて、ＬＤ（７）がリンク外か否かを判定する。ＬＤ（７）はリンク外であるため、第２のパラメータ更新部４８にてdistを更新する。この場合、dist＝１に更新される。その後、８文字目を配置するリンクは存在しないため、処理を終了する。即ち、候補点Ｑ（２）から文字列「String11」を配置することは不可能であるため、評価関数の算出は行わない。このように、０番目の文字列の文字列配置開始点を決定する。この場合、文字列「String11」の０番目の文字列の文字列配置開始点はＱ（１）となる。また、Ｑ（１）から道路ノード列に沿って配置した文字列配置（図１６参照）は、１番目以降の文字列の文字列配置開始点の最適化に用いる。
【００５９】
０番目の文字列「String11」の文字列配置点が決定されると、次に１番目の文字列である「String2」に対しても同様の処理を行う。まず、候補点作成部３において１番目の文字列が沿う道路リンク上に候補点を作成する。この場合、図１８に示すように、３つの候補点Ｑ（３）、Ｑ（４）、Ｑ（５）が作成される。続いて文字列配置部４が候補点Ｑ（３）から１番目の文字列を配置する（図１９参照）。その後、評価関数算出部５において評価関数値Ｆの算出を行う。
【００６０】
具体的には、ステップＳＴ５１として、初期文字列判定部５４はstring_idx＝１と判定し、ステップＳＴ５３として文字間隔関数更新部５６は上記式（７）に基づいて、文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）の値を、5.1×10-264と算出する。その後、文字間隔関数更新部５６の処理を繰り返して、文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）を更新し、最終的にＰ(Sstring_idx｜{Sstring_idx-1}）＝0.040705との値を得る。
【００６１】
続いて、ステップＳＴ５４として、道路角度関数更新部５８はＰ(Rstring_idx｜Sstring_idx）の値を、1.96618×10-53と算出する。ステップＳＴ５５として、評価関数値算出部５３は、文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1}）＝0.040705、および道路角度関数値Ｐ(Rstring_idx｜Sstring_idx）＝1.96618×10-53に基づいて、上述した式（１１）に基づいて評価関数値Ｆの算出を行う。この場合、Ｆ＝log1.96618×10-53+log0.040705＝-52.7063767-1.3936＝-54.0999767となる。ステップＳＴ５６として、算出した評価関数値Ｆを最小評価関数値保存部６に出力する。
【００６２】
その後、最小評価関数値保存部６は、算出された評価関数値Ｆがmin_cost未満であると判定し、min_cost＝-54.0999767、１番目の文字列の文字列配置開始点はＱ（３）と設定して最小評価関数値データ記憶部７および文字列配置開始点データ記憶部９に格納すると共に、図１９に示した文字列配置を文字列配置データ記憶部８に格納する。
【００６３】
その後、同様に文字列配置部４において、候補点Ｑ（４）から1番目の文字列「String2」を配置する（図２０参照）。文字間隔関数算出部５１は文字間隔関数値Ｐ(Sstring_idx｜{Sstring_idx-1})＝2.7947×10-166と算出する。その後、道路角度関数算出部５２において道路角度関数値Ｐ(Rstring_idx｜Sstring_idx）＝0.002850205と算出する。評価関数値算出部５３は、これらの値を用いて上述した式（１１）に基づいて評価関数値Ｆを算出する。この場合Ｆ＝log2.7947×10-166+log0.002850205＝-165.55367-2.244093909＝-167.7977639となる。最小評価関数値保存部６は、算出された評価関数値Ｆがmin_cost未満であると判定し、min_cost＝-167.7977639、１番目の文字列の文字列配置開始点はＱ（４）と設定する。
【００６４】
同様に、文字列配置部４において、Ｑ（５）から文字列を配置する。この場合、文字列をＱ（５）から配置すると、道路リンクの長さ不足となり配置することができないため、文字列配置失敗となり処理を終了する。上述した処理により、文字列「String2」の１番目の文字列の文字列配置開始点がＱ（４）に決定される。
【００６５】
以上のように、この実施の形態１によれば、評価関数算出部５に、文字列同士の文字間隔が文字列の可読性に与える影響を示す関数値を算出する文字間隔関数算出部５１を設けるように構成したので、文字列同士の重なり、および文字列が沿う道路の角度変化に加え、文字列同士の間隔が広くなるように、文字列の文字列配置開始点を最適位置に設定することができる。これにより、文字列同士の間隔が広がり、文字列の密集を抑制し、文字列の視認性を向上させることができる。
【００６６】
また、この実施の形態１によれば、文字間隔関数値を算出する際にガウス関数値を算出する第１のガウス関数値算出部５５を備えるように構成したので、道路ノードと既に配置した文字の中心座標にガウス分布を配置し、文字列同士の間隔が広くなるように、文字列配置開始点を最適位置に変更することができる。
【００６７】
なお、本願発明はその発明の範囲内において、実施の形態の任意の構成要素の変形、もしくは実施の形態の任意の構成要素の省略が可能である。
【符号の説明】
【００６８】
１  文字列データ記憶部、２  文字列データ取得部、３  候補点作成部、４  文字列配置部、５  評価関数算出部、６  最小評価関数値保存部、７  最小評価関数値データ記憶部、８  文字列配置データ記憶部、９  文字列配置開始点データ記憶部、３１  第１のリンク長算出部、３２  リンク全長更新部、３３  候補点間隔算出部、３４  作成部、３５  第２のリンク長算出部、３６  距離更新部、３７  情報記憶部、４１  初期文字位置決定部、４２  リンク角度算出部、４３  文字配置位置算出部、４４  文字リンク外判定部、４５  文字配置部、４６  重なり判定部、４７  第１のパラメータ更新部、４８  第２のパラメータ更新部、５１  文字間隔関数算出部、５２  道路角度関数算出部、５３  評価関数値算出部、５４  初期文字列判定部、５５  第１のガウス関数値算出部、５６  文字間隔関数更新部、５７  第２のガウス関数値算出部、５８  道路角度関数更新部、１００  文字列配置装置。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
道路ノード列上の複数の候補点に配置した文字列の配置に対する評価を示す評価関数値を算出する評価関数算出部を備えた文字列配置装置において、
前記評価関数算出部は、
前記複数の候補点に配置した複数の文字列間の文字間隔に対する評価を示す文字間隔関数値を算出する文字間隔関数算出部と、
前記複数の候補点に配置した文字列が沿う道路ノード列の角度に対する評価を示す道路角度関数値を算出する道路角度関数算出部と、
前記文字間隔関数値および前記道路角度関数値に基づいて前記評価関数値を算出する評価関数値算出部とを備えた
ことを特徴とする文字列配置装置。
【請求項２】
前記文字列に関する文字列データおよび前記道路ノード列に関する道路ノード列データを取得するデータ取得部と、
前記文字列データおよび前記道路ノード列データに基づいて、前記道路ノード列上に前記複数の候補点を作成する候補点作成部と、
前記複数の候補点に前記文字列を配置する文字列配置部と、
予め記憶した最小評価関数値未満の前記評価関数値を新たな前記最小評価関数値として記憶するとともに、当該最小評価関数値における文字列配置および文字列配置開始点を記憶させる最小評価関数値保存部とを備えた
ことを特徴とする請求項１記載の文字列配置装置。
【請求項３】
前記候補点作成部は、
前記道路ノード列における所定の道路ノード間を繋ぐリンクの長さを算出する第１のリンク長算出部と、
前記第１のリンク長算出部が算出した道路ノード間を繋ぐリンクの長さを加算して更新し、前記道路ノード列の全長を算出するリンク全長更新部と、
前記リンク全長更新部が算出した前記道路ノード列の全長、および予め設定された前記候補点作成部が作成する候補点数に基づいて、候補点作成間隔を算出する候補点間隔算出部と、
前記道路ノード列上に、前記候補点間隔算出部が算出した候補点作成間隔で複数の候補点を作成する作成部とを備えた
ことを特徴とする請求項２記載の文字列配置装置。
【請求項４】
前記文字列配置部は、
前記文字列の先頭の文字の配置位置を決定する初期文字位置決定部と、
前記初期文字位置決定部が決定した先頭の文字の配置位置により決定される、前記文字列を配置する所定の道路ノード間を繋ぐリンクの角度を算出するリンク角度算出部と、
前記初期文字位置決定部が決定した先頭の文字の配置位置、および前記リンク角度算出部が算出したリンクの角度に基づいて、前記文字列を構成する各文字の配置位置を算出する文字配置位置算出部と、
前記文字配置位置算出部が算出した前記各文字の配置位置が前記リンク上に存在するか判定を行う文字リンク外判定部と、
前記文字リンク外判定部において、前記各文字の配置位置が前記リンク上に存在すると判定された場合に、前記各文字の配置位置に基づいて配置座標を設定し、設定した配置座標に前記各文字を配置する文字配置部とを備えた
ことを特徴とする請求項２記載の文字列配置装置。
【請求項５】
前記文字列配置部は、
前記文字配置部が前記各文字を配置した配置座標が、前回設定した文字の配置座標に重なるか判定を行う重なり判定部と、
前記重なり判定部において、前記配置座標が前回設定した文字の配置座標に重なると判定された場合に、前記初期文字位置決定部が決定したパラメータに所定定数を加算して更新するパラメータ更新部とを備えた
ことを特徴とする請求項４記載の文字列配置装置。
【請求項６】
前記文字間隔関数算出部は、
前記文字列配置部が配置した複数の文字列のうち、初めに配置した文字列であるか判定を行う初期文字列判定部と、
前記初期文字列判定部において、初めに配置した文字列でないと判定された文字列について、その他の文字列との文字間隔を示すガウス関数値を算出する第１のガウス関数値算出部と、
前記第１のガウス関数値算出部が算出したガウス関数値を用いて、前記文字列間隔関数値を更新する文字間隔関数更新部とを備えた
ことを特徴とする請求項２記載の文字列配置装置。
【請求項７】
前記道路角度関数算出部は、
前記文字列と当該文字列を配置する道路ノード列との関係を示すガウス関数値を算出する第２のガウス関数値算出部と、
前記第２のガウス関数値算出部が算出したガウス関数値を用いて、前記道路角度関数値を更新する道路角度関数更新部とを備えた
ことを特徴とする請求項１記載の文字列配置装置。
【手続補正書】
【提出日】平成26年8月22日(2014.8.22)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
この発明に係る文字列配置装置は、ノード列上の複数の候補点に配置した文字列の配置に対する評価を示す評価関数値を算出する評価関数算出部を備えた文字列配置装置において、評価関数算出部は、複数の候補点に配置した文字列と、複数の候補点が配置されたノード列とは異なるノード列上に配置された文字列との距離を評価するための文字間隔関数値を算出する文字間隔関数算出部と、複数の候補点に配置した文字列が沿うノード列の角度に対する評価を示す角度関数値を算出する角度関数算出部と、文字間隔関数値および角度関数値に基づいて、複数の候補点に配置した文字列の評価関数値を算出する評価関数値算出部と、評価関数値算出部で算出された複数の評価関数値同士の比較に基づいて複数の候補点のうちいずれの候補点に文字列を配置するかを決定する評価関数値保存部とを備えるものである。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
続いて、文字列配置装置１００のより詳細な構成および動作について説明する。
図３から図５は文字列配置装置１００の各構成をより詳細に示したブロック図であり、図３は候補点作成部３の構成を示すブロック図、図４は文字列配置部４の構成を示すブロック図、図５は評価関数算出部５の構成を示すブロック図である。
まず、図３に示すように、候補点作成部３は、道路ノード列中の２つのノードを結ぶリンクの長さを算出する第１のリンク長算出部３１と、第１のリンク長算出部３１で算出したリンクの長さを加算して道路ノード列の全長を求めるリンク全長更新部３２と、道路ノード列の全長から候補点の間隔を算出する候補点間隔算出部３３と、道路ノード列上に候補点を作成する作成部３４と、設定されたリンク長が所定の条件を満たさない場合に、ノードを更新してリンクの長さを算出する第２のリンク長算出部３５と、第２のリンク長算出部３５が算出したリンクの長さに基づいてリンク長を更新する距離更新部３６と、候補点間隔（cand_gap）、候補点番号（cand_idx）、道路ノード列の先頭ノードから所定のノードを繋ぐリンク長（dist）など、候補点に関する情報を記憶する情報記憶部３７で構成される。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
具体的な候補点作成方法を、図７のフローチャートを参照しながら説明する。図７は、実施の形態１による文字列配置装置の候補点作成部の動作を示すフローチャートである。
候補点作成部３の第１のリンク長算出部３１は、情報記憶部３７に記憶された各ノード情報を参照し、ｎ番目のノードＰ（ｎ）とｎ＋１番目のノードＰ（ｎ＋１）を繋ぐリンクの長さを算出する（ステップＳＴ１１）。リンク全長更新部３２は、第１のリンク長算出部３１がリンク長を算出すると、前回算出したリンク全長に加算してリンク全長（total_dist）の値を更新する（ステップＳＴ１２）。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ノード列上の複数の候補点に配置した文字列の配置に対する評価を示す評価関数値を算出する評価関数算出部を備えた文字列配置装置において、
前記評価関数算出部は、
前記複数の候補点に配置した文字列と、前記複数の候補点が配置されたノード列とは異なるノード列上に配置された文字列との距離を評価するための文字間隔関数値を算出する文字間隔関数算出部と、
前記複数の候補点に配置した文字列が沿うノード列の角度に対する評価を示す角度関数値を算出する角度関数算出部と、
前記文字間隔関数値および前記角度関数値に基づいて、前記複数の候補点に配置した文字列の前記評価関数値を算出する評価関数値算出部と、
前記評価関数値算出部で算出された複数の前記評価関数値同士の比較に基づいて前記複数の候補点のうちいずれの候補点に文字列を配置するかを決定する評価関数値保存部とを備えた
ことを特徴とする文字列配置装置。
【請求項２】
前記文字列に関する文字列データおよび前記ノード列に関するノード列データを取得するデータ取得部と、
前記文字列データおよび前記ノード列データに基づいて、前記ノード列上に前記複数の候補点を作成する候補点作成部と、
前記複数の候補点に前記文字列を配置する文字列配置部と、
予め記憶した最小評価関数値未満の前記評価関数値を新たな前記最小評価関数値として記憶するとともに、当該最小評価関数値における文字列配置および文字列配置開始点を記憶させる最小評価関数値保存部とを備えた
ことを特徴とする請求項１記載の文字列配置装置。
【請求項３】
前記候補点作成部は、
前記ノード列における所定のノード間を繋ぐリンクの長さを算出する第１のリンク長算出部と、
前記第１のリンク長算出部が算出したノード間を繋ぐリンクの長さを加算して更新し、前記ノード列の全長を算出するリンク全長更新部と、
前記リンク全長更新部が算出した前記ノード列の全長、および予め設定された前記候補点作成部が作成する候補点数に基づいて、候補点作成間隔を算出する候補点間隔算出部と、
前記ノード列上に、前記候補点間隔算出部が算出した候補点作成間隔で複数の候補点を作成する作成部とを備えた
ことを特徴とする請求項２記載の文字列配置装置。
【請求項４】
前記文字列配置部は、
前記文字列の先頭の文字の配置位置を決定する初期文字位置決定部と、
前記初期文字位置決定部が決定した先頭の文字の配置位置により決定される、前記文字列を配置する所定のノード間を繋ぐリンクの角度を算出するリンク角度算出部と、
前記初期文字位置決定部が決定した先頭の文字の配置位置、および前記リンク角度算出部が算出したリンクの角度に基づいて、前記文字列を構成する各文字の配置位置を算出する文字配置位置算出部と、
前記文字配置位置算出部が算出した前記各文字の配置位置が前記リンク上に存在するか判定を行う文字リンク外判定部と、
前記文字リンク外判定部において、前記各文字の配置位置が前記リンク上に存在すると判定された場合に、前記各文字の配置位置に基づいて配置座標を設定し、設定した配置座標に前記各文字を配置する文字配置部とを備えた
ことを特徴とする請求項２記載の文字列配置装置。
【請求項５】
前記文字列配置部は、
前記文字配置部が前記各文字を配置した配置座標が、前回設定した文字の配置座標に重なるか判定を行う重なり判定部と、
前記重なり判定部において、前記配置座標が前回設定した文字の配置座標に重なると判定された場合に、前記初期文字位置決定部が決定したパラメータに所定定数を加算して更新するパラメータ更新部とを備えた
ことを特徴とする請求項４記載の文字列配置装置。
【請求項６】
前記文字間隔関数算出部は、
前記文字列配置部が配置した複数の文字列のうち、初めに配置した文字列であるか判定を行う初期文字列判定部と、
前記初期文字列判定部において、初めに配置した文字列でないと判定された文字列について、前記複数の候補点が配置されたノード列とは異なるノード列上に配置された文字列との距離を評価するためのガウス関数値を算出する第１のガウス関数値算出部と、
前記第１のガウス関数値算出部が算出したガウス関数値を用いて、前記文字間隔関数値を更新する文字間隔関数更新部とを備えた
ことを特徴とする請求項２記載の文字列配置装置。
【請求項７】
前記角度関数算出部は、
前記文字列と当該文字列を配置するノード列との関係を示すガウス関数値を算出する第２のガウス関数値算出部と、
前記第２のガウス関数値算出部が算出したガウス関数値を用いて、前記角度関数値を更新する角度関数更新部とを備えた
ことを特徴とする請求項１記載の文字列配置装置。
【国際調査報告】
2013024505.tif 000042
2013024505.tif 000043
2013024505.tif 000044