マッチング表評価システム、その方法及びプログラム
【課題】マッチング処理の方針に適したマッチング表を評価できるマッチング表評価システム、その方法及びプログラムを提供する。
【解決手段】配置図の格子分割における分割パラメタを生成する分割パラメタ生成手段と、分割パラメタに基づいて、配置図を格子領域に分割し、マッチング表を生成するマッチング表生成手段とを有し、分割評価手段は評価関数に基づいて、マッチング表を評価し、予め定められた条件を満たすか否かを判断し、条件を満たさない場合には分割パラメタ生成手段に新たな分割パラメタを生成させる。
【解決手段】配置図の格子分割における分割パラメタを生成する分割パラメタ生成手段と、分割パラメタに基づいて、配置図を格子領域に分割し、マッチング表を生成するマッチング表生成手段とを有し、分割評価手段は評価関数に基づいて、マッチング表を評価し、予め定められた条件を満たすか否かを判断し、条件を満たさない場合には分割パラメタ生成手段に新たな分割パラメタを生成させる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マッチング表評価システム、その方法及びプログラムに関する。
【背景技術】
【０００２】
交通管制や物流管理などでは、車や人が送信する位置情報をサーバに収集し、得られた位置情報を用いて、車や人が現在位置している道路や建物を特定する処理が大量に行われており、このような処理をマッチング処理と呼ぶ。
【０００３】
車や人の位置情報を送信する例としてプローブカーやGPS付き携帯端末がある。プローブカーやGPS付き携帯端末のような移動可能でサーバに位置座標を送信する物体を以下移動体と呼ぶ。また、道路や建物のような地図上に位置が記録されている物体を以下対象オブジェクトと呼ぶ。
【０００４】
マッチング処理では、移動体と最も近い対象オブジェクトを、現在位置している対象オブジェクトとして特定する。そのために、全ての対象オブジェクトについて、移動体と対象オブジェクトとの間の距離を計算し、距離が最小の対象オブジェクトを判定する必要がある。
【０００５】
しかし、地図上の全ての対象オブジェクトとの距離を計算する処理には時間がかかるため、対象オブジェクトが配置された領域を格子状に分割して（以下、格子分割と記載する）、距離計算の対象とする対象オブジェクト数を減らす手法がある。この方法では、マッチング処理の前に対象オブジェクトが配置された領域を格子分割し、各格子内の領域（以下、格子領域と記載する）のに存在する対象オブジェクトを事前に求めておく。そして、この処理で求められる、各格子とその格子領域内部の対象オブジェクトとの対応表を、以下マッチング表と呼ぶ。
【０００６】
マッチング表の例を図１に示す。図１はマッチング表の例を説明する説明図である。
【０００７】
図１の例に示すマッチング表では、格子と、その格子領域内部の対象オブジェクトのIDとを対応付けている。図１（ａ）のように、配置図の領域上に対象オブジェクト 1、 2、 3、 4、 5が分布しているときは、図１（ｂ）のようなマッチング表になる。尚、以下の説明において、少なくともマッチング処理を行う領域とこの領域内に存在する対象オブジェクトの位置との関係を示したものを配置図と記載する。
【０００８】
マッチング処理時には、まず、移動体の位置を含む格子を決定する。例えば、配置図上にxy直交座標系が導入されており、x軸、y軸に平行な正方形の格子により格子分割されている時、移動体の位置を含む格子は、移動体のx、y座標を格子の辺の長さで除算することで求めることができる。
【０００９】
次に、マッチング表を引き、移動体の位置を含む格子領域に存在する対象オブジェクトを求め、求めた対象オブジェクトと移動体との距離計算を行う。
【００１０】
このようにマッチング表を用いることで、距離計算の回数を減らす。
【００１１】
特許文献１には移動体の速度や進行方向など、移動体の情報を使用して格子分割を行い、マッチング表を生成する装置が記載されている。
【特許文献１】特開2007-304944号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
一方、最適なマッチング表はマッチング処理の方針により異なる。最適性の基準の一例として、マッチング処理の速度が高いほど良いという方針の場合、マッチング速度が最大になるマッチング表が最適である。また、マッチング表で使用される記憶容量が小さいほど良いという方針の場合、マッチング表で使用する記憶容量が最小になるマッチング表が最適である。従って、マッチング表の選択は、マッチング処理の方針に合致する必要がある。
【００１３】
しかし、特許文献1の技術は、このような事情を考慮しておらず、マッチング処理の方針に適したマッチング表を選択する為にマッチング表を評価するという概念がなかった。
【００１４】
そこで、本発明は上記課題に鑑みて発明されたものであって、その目的は、マッチング処理の方針に適したマッチング表を評価できるマッチング表評価システム、その方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００１５】
上記課題を解決する本発明は、対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価する分割評価手段を有するマッチング表評価システムである。
【００１６】
上記課題を解決する本発明は、対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価するマッチング表評価方法である。
【００１７】
上記課題を解決する本発明は、対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価するマッチング表評価処理を情報処理装置に実行させるプログラムである。
【発明の効果】
【００１８】
本発明によれば、マッチング処理の方針に適したマッチング表を得ることができる。
【発明を実施するための最良の形態】
【００１９】
＜第１の実施の形態＞
第１の実施の形態を説明する。
【００２０】
まず、マッチング表について説明する。尚、以下の説明において、少なくともマッチング処理を行う領域とこの領域内に存在する対象オブジェクトの位置との関係を示したものを配置図と記載し、この配置図の領域を格子状に分割することを格子分割と記載する。
【００２１】
図１にマッチング表の例を示す。
【００２２】
図１の例に示すマッチング表では、格子と、その格子領域内部の対象オブジェクトのIDとを対応付けている。図１（ａ）のように、配置図の領域上に対象オブジェクト 1、 2、 3、 4、 5が分布しているときは、図１（ｂ）のようなマッチング表になる。前記は一例であり、これに限るものではない。また、前記の例では対象オブジェクトは建物など面であるものとしたが、道路などの線でも、特定の地点などを表す点でも構わない。また、前記の例では配置図やマッチング表の領域を平面としたが、2次元平面に限らない。例えば、曲面や3次元空間でも構わない。
【００２３】
このようなマッチング表において、最適なマッチング表はマッチング処理の具体的な方針により異なる。上述したように、マッチング処理の速度が高いほど良いという方針の場合、マッチング速度が最大になるマッチング表が最適である。また、マッチング表で使用される記憶容量が小さいほど良いという方針の場合、マッチング表で使用される記憶容量が最小になるマッチング表が最適である。
【００２４】
例えば、対象オブジェクトの密度に対して格子が大きく格子分割が粗い場合、距離計算の回数はあまり減らない。逆に、対象オブシェクとの密度に対して格子が小さく格子分割が細かい場合、これよりも少し粗い格子分割と比べて距離計算の回数はあまり変わらないにもかかわらず、格子数が多くなるため、より大きな記憶容量が使用される。
【００２５】
図２を参照して前記の問題について説明する。図２中のMT01a、 MT01b、 MT02a、 MT02bは対象オブジェクトの配置と格子分割との関係を模式的に示した説明図である。
【００２６】
MT01aとMT01bは同一の配置図で格子分割の間隔（格子の１辺の長さ）のみ異なる。MT02aとMT02bも同一の配置図で格子分割の間隔（格子の１辺の長さ）のみ異なる。
【００２７】
MT01aとMT01bの配置図では、中央部に対象オブジェクトが多く存在しているため、MT01aによる格子分割では、中央の格子内の対象オブジェクトの数が格子分割を行わない場合とほとんど変わらない。そのため、MT01aのように粗い格子分割では、格子分割を行わない場合と比べて距離計算の回数がほとんど減少しない。よって、MT01aを使用したマッチング処理は低速である。
【００２８】
そこで、MT01bのようにより細かく格子分割を行うことで、1つの格子領域内部に含まれる対象オブジェクトの数が減少する。その結果、距離計算の回数が減少するため、より高速なマッチング処理が実現される。よって、マッチング処理の速度が高速なほど良いとい方針の場合には、MT01bは適切なマッチング表である。
【００２９】
一方、MT02aとMT02bの配置図では、MT02aによる格子分割は細か過ぎる。MT02aとMT02bとは、いずれも各格子領域内部に1つの対象オブジェクトしか存在していない。そのため、MT02aの距離計算の回数と、MT02bの距離計算の回数とは変わらないので、マッチング処理の速度は変わらない。しかし、マッチング表MT02aは格子数が多いために、使用する記憶容量は MT02bよりも大きい。よって、マッチング処理の速度が同じならば、マッチング表で使用される記憶容量が少ないほど良いという方針であるならば、MT02aは適切なマッチング表ではない。
【００３０】
図２の例において MT01b、MT02b のマッチング表を、マッチング処理の方針に適したマッチング表を選ぶことは、配置図上の対象オブジェクトの分布を考慮しなければならない。
【００３１】
そこで、本実施の形態では、マッチング処理の方針に適したマッチング表を得る為に、マッチング表の対象オブジェクトの位置的な分布を考慮した評価関数によって、マッチング表を評価する。
【００３２】
続いて、第１の実施の形態におけるマッチング表評価システムを説明する。
【００３３】
図３は、第１の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【００３４】
図３に示すマッチング表評価システムは、配置記憶手段100と、制約記憶手段101と、分割パラメタ生成手段130と、分割パラメタ記憶手段122と、マッチング表生成手段103と、分割評価手段11と、マッチング表記憶手段12とを備える。
【００３５】
配置記憶手段100は、配置図の情報（以下、配置図情報と記載する）を記憶する。配置図情報は、少なくともマッチング処理を行う領域の範囲の情報と、前記の領域内に存在する対象オブジェクトの位置情報とを含む情報である。
【００３６】
配置記憶手段100が記憶する配置図情報の一例を示す説明図を図４に示す。図４の示す例において、配置図の領域は長方形とし、緯度と経度とによる座標系が導入されているものとする。また、1つの対象オブジェクトは配置図上の1点であるとする。
【００３７】
配置図情報は配置図の表現する範囲を表す配置図領域情報T010と、配置図の上に存在する対象オブジェクトの位置情報を表す配置図上対象オブジェクト情報T011とによって構成される。
【００３８】
配置図領域情報T010は、図４（ａ）に示すように原点T0101とサイズT0102とで構成される。原点T0101は配置図の領域の原点の座標を表す。サイズT0102は、配置図の領域の縦横のサイズを表す。
【００３９】
配置図上対象オブジェクト情報T011は、図４（ｂ）に示すように識別子であるIDT0111と座標T0112との組で構成される。IDT0111は、配置図上に存在する対象オブジェクトの識別子である。座標T0112は対象オブジェクトの存在する位置の座標を表す。
【００４０】
尚、上述の例では対象オブジェクトを点として扱っているが、対象オブジェクトを線として扱っても、面として扱ってもよい。対象オブジェクトを線として扱う場合、対象オブジェクトを長さ一定の線分で表し、配置図情報上は中心の位置と方向で表現してもよい。また、対象オブジェクトを線分で表し、配置図情報上は両端の位置で表現してもよい。対象オブジェクトを面として扱う場合、例えば、対象オブジェクトを円で表し、配置図情報上は中心の位置と半径で表現してもよい。また、対象オブジェクトを長方形で表し、配置図情報上は各頂点の位置で表現してもよい。また、複雑な形状の領域については、円や長方形の組み合わせで表現してもよい。更に、マッチング表を3次元空間で考える場合、点として扱っても、線や面として扱っても、3次元の空間として扱ってもよい。前記は一例であり、これらに限るものではない。
【００４１】
制約記憶手段101は、配置図を格子領域に分割する際に用いる分割パラメタを生成する時の格子分割の制約条件が記憶されている。
【００４２】
制約記憶手段101に記憶されている格子分割の制約条件の一例を示す説明図を図５に示す。
【００４３】
図５が示す例において、格子分割の制約条件は分割パラメタの制約リストT100であり、最大格子サイズT1001、最小格子サイズT1002、格子分割の刻み幅T1003により構成される。最大格子サイズT1001は分割パラメタ生成手段130が生成する格子サイズの最大値である。最小格子サイズT1002は分割パラメタ生成手段130が生成する格子サイズの最小値である。
【００４４】
図５が示す例において、最大格子サイズは500m、最小格子サイズは100mである。格子サイズ刻み幅T1003は、生成する格子サイズ間の差である。
【００４５】
すなわち、生成する格子サイズを、L(1)、L(2)、L(3)、…、L(n) (ただし、L(1)>L(2)>L(3)>……>L(n))、格子サイズ刻み幅を、ΔLとおくと、
L(2)=L(1)-ΔL、L(3)=L(2)-ΔL、……、L(n)=L(n-1)-ΔLである。
【００４６】
図５が示す例では、格子サイズ 500m、 490m、 480m、……、100mが分割パラメタとして許容される。
【００４７】
制約条件には、格子サイズの取り得る範囲や、格子分割の起点の範囲、分割パラメタの刻み幅もある。また、例えば、分割パラメタ間の比や分割パラメタの個数等を制約条件としても構わない。また、前記は一例であり、制約条件はこれらに限るものではない。
【００４８】
分割パラメタ生成手段130は、配置図の格子分割における分割パラメタを生成する。そして、分割パラメタ生成手段130は、分割パラメタ初期値生成手段121と、分割パラメタ更新手段123とを備える。
【００４９】
分割パラメタ初期値生成手段121は、配置図の分割パラメタの初期値を制約記憶手段101に記憶されている制約を満たすように生成する。分割パラメタとしては、例えば、格子のサイズや格子分割の起点がある。また、格子のサイズは縦横で別のパラメタでも構わない。尚、上述の分割パラメタは一例であり、分割パラメタはこれらに限るものではない。
【００５０】
分割パラメタ記憶手段122には、分割パラメタ初期値生成手段121や後述する分割パラメタ更新手段123で生成された分割パラメタが記憶される。尚、分割パラメタ記憶手段122は最後に生成された分割パラメタだけを記憶しても、以前に生成した分割パラメタを記憶していても構わない。
【００５１】
マッチング表生成手段103は、配置記憶手段100から配置図領域情報T010と配置図上対象オブジェクト情報T011とを取得し、分割パラメタ記憶手段122から分割パラメタを取得する。そして、取得した分割パラメタに基づいて、配置図領域情報T010と配置図上対象オブジェクト情報T011とに基づいて特定される配置図を格子領域に分割し、マッチング表を生成する。
【００５２】
分割評価手段11は、入力されたマッチング表に対し、評価関数の値を配置図上の対象オブジェクトの分布に基づき計算する。
【００５３】
ここで、評価関数について説明する。
【００５４】
評価関数は、対象オブジェクトの分布に基づき、マッチング処理の方針に合致する指標を示すようなものであればよい。
【００５５】
例えば、評価関数は、マッチング表が持つ全格子の数に対する対象オブジェクトが1つ以下である格子の数の割合とし、評価関数値が最大のマッチング表を適するものとしてもよい。格子領域内部に含まれる対象オブジェクトが1つの場合、距離計算が不要であるため、この評価関数は、移動体が対象オブジェクトの存在する格子領域内部に均一に分布する場合の、マッチング処理時に距離計算が不要である確率を示している。よって、この評価関数の値が大きい程、高速にマッチング処理できると期待でき、マッチング処理を高速に行いたい場合のマッチング表を評価するのに適する。
【００５６】
また、評価関数は、格子(i、j)に対する移動体の存在確率p(i、j)を予め与えておき、格子(i、j)の領域に含まれる対象オブジェクト数n(i、j)としたときに、Σp(i、j)n(i、j) と定義し、前記評価関数が最小のマッチング表を適するものとしてもよい。この評価関数は、マッチング処理における距離計算の回数の期待値を示している。よって、この評価関数の値が小さい程高速にマッチング処理できると期待でき、マッチング処理を高速に行いたい場合のマッチング表を評価するのに適する。
【００５７】
上述した評価関数は一例であり、マッチング処理を高速に行いたい場合や、マッチング表で使用される記憶容量を少なくしたい場合等、適時マッチング処理の方針にかなう評価関数を導入する。
【００５８】
分割評価手段11は、マッチング処理の方針に適したマッチング表を得る為に、入力されたマッチング表の評価関数の値を計算し、評価関数の値に基づいて、そのマッチング表を評価する。そして、予め定められた分割パラメタの更新の終了条件（マッチング処理の方針に合ったマッチング表である条件）を判定する。終了条件を満たさず動作を続行する場合は、新しい分割パラメタを生成する指示を、分割パラメタ更新手段123に通知する。
【００５９】
マッチング表記憶手段12は、分割評価手段11で、分割パラメタの更新の終了が判断され、マッチング処理の方針に適すると判断されたマッチング表が記憶される。
【００６０】
分割パラメタ更新手段123は、分割評価手段11の指示を受け、新しい分割パラメタを生成し、分割パラメタ記憶手段122に記憶する。
【００６１】
次に、図６のフローチャートを参照して、本実施の形態のマッチング表評価システムの動作を説明する。
【００６２】
図６は、本実施の形態のマッチング表評価システムの動作の一例を示すフローチャートである。
【００６３】
本実施の形態のマッチング表評価システムでは、まず、分割パラメタ初期値生成手段121が制約記憶手段101から、格子分割の制約条件を取得する(ステップS301)。
【００６４】
次に、分割パラメタ初期値生成手段121は、取得した制約条件を満たすような分割パラメタを1つまたは複数生成する(ステップS302)。
【００６５】
分割パラメタ初期値生成手段121は生成した分割パラメタを分割パラメタ記憶手段122に格納する(ステップS303)。
【００６６】
マッチング表生成手段103は、配置記憶手段100から配置図情報を取得し、分割パラメタ記憶手段122から分割パラメタを取得する(ステップS311)。その後、マッチング表生成手段103は、ステップS311で取得した分割パラメタに基づいて、配置図の領域を格子分割し、マッチング表を生成する(ステップS312)。そして、ステップS312で生成したマッチング表をマッチング表記憶手段12に保存する(ステップS313)。
【００６７】
分割評価手段11は、ステップS312で生成した各マッチング表について、対象オブジェクトの分布に基づく評価関数を計算する(ステップS321)。そして、計算した評価関数値に基づいて、予め定めた終了条件を満たしているか判定する(ステップS331)。そして、終了条件を満たさない場合、分割評価手段11は、制約に基づく新しい分割パラメタの生成を分割パラメタ更新手段123に指示する。
【００６８】
分割パラメタ更新手段123は、制約に基づく新しい分割パラメタを生成し(ステップS332)、生成した分割パラメタを分割パラメタ記憶手段122に格納する(ステップS333)。
【００６９】
そして、ステップS331において、終了条件を満たすまで、ステップS3111〜S313、S321、S331〜S333を繰り返す。
【００７０】
次に、本実施の形態のマッチング表評価システム具体的な動作例を説明する。
【００７１】
尚、以下の説明において、分割パラメタpによるマッチング表に対する評価関数の値をf(p)とおく。第n回目のマッチング表生成に使用する分割パラメタをp(n)とおく。そして、マッチング処理の方針として、処理がなるべく高速に、かつ、記憶容量が少なくなるようにバランスの取れたマッチング表を用いるものとし、評価関数fが最小値をとるようなマッチング表がマッチング処理の方針に適したマッチング表であるものとする。
【００７２】
まず、分割パラメタ初期値生成手段121は、分割パラメタの初期値p(0)を決定する(ステップS301〜S303)。
【００７３】
尚、分割パラメタ初期値生成手段121は、分割パラメタの範囲を制約し、初期値p(0)を、その制約された分割パラメタの範囲からランダムに選んでもよい。また、予め初期値p(0)を制約記憶手段101に格納しておいてもよい。また、初期値p(0)は1つに限られず、分割パラメタ初期値生成手段121は初期値p(0)を複数生成してもよい。また、前記は一例であり、これらに限るものではない。
【００７４】
マッチング表生成手段103は、分割パラメタの初期値p(0)により、配置図を格子分割してマッチング表を生成する(ステップS311〜S313)。その後、分割評価手段11は生成したマッチング表に対して評価関数値f(p0)を計算する(ステップS321)。
【００７５】
評価関数の計算後、分割評価手段11は、終了条件を判定する(ステップS331)。本実施例では、判定ステップS331への到達回数nが2回目以降でかつ、前回の分割パラメタとの差の絶対値|p(n)-p(n-1)|が所定の閾値ε未満であるかを判定する。
【００７６】
閾値εについて、図７を用いて説明する。図７は、分割パラメタpと評価関数fとの関係のグラフの一例を示す説明図である。閾値εは、例えば、評価関数fが図７に示されるような下に凸の所定関数であり、分割パラメタが反復法により求められる場合、評価関数の値f(p)が最小値として許容され、かつ、分割パラメタpに対して十分小さい定数として定義される。
【００７７】
尚、|(f(p(n))-f(p(n-1)))/f(p(n))|が閾値ε未満であるかを判定してもよい。また、前記の終了条件は一例であり、これに限るものではない。
【００７８】
終了条件を満たさない場合、分割評価手段11は、分割パラメタ更新手段123に、新しい分割パラメタの生成を指示する。
【００７９】
分割パラメタ更新手段123は新しい分割パラメタを生成して、その値に更新する(ステップS332)。新しい分割パラメタは、反復法、例えば、ニュートン法により、
p(n)=p(n-1)-f'(p(n-1))/f''(p(n-1))
で生成される。ただし、f'、f''はそれぞれ評価関数fの導関数、2次導関数とする。
【００８０】
または、新しい分割パラメタはセカント法により、
p(n)=p(n-1)-f'(p(n-1))(p(n-1)-p(n-2))/(f'(p(n-1))-f'(p(n-2)))
としてもよい。
【００８１】
もしくは、fの導関数を容易に求められない場合、補間法を使用してもよい。
【００８２】
前記は一例であり、これらに限るものではない。
【００８３】
新しい分割パラメタp(n)を生成後、分割パラメタ更新手段123はp(n)を分割パラメタ記憶手段122に格納する(ステップS333)。
【００８４】
そして、ステップS331において、終了条件を満たすまで、ステップS3111〜S313、S321、S331〜S333を繰り返す。
【００８５】
尚、分割パラメタ初期値生成手段121や分割パラメタ更新手段123で生成する分割パラメタは複数であってもよい。例えば、n回目の動作で分割パラメタp(n)、p(n)+Δpを生成し、f'(p(n))を (f(p(n)+Δp)-f(p(n)))/Δp で近似してもよい。また、前記は一例であり、これに限るものではない。
【００８６】
図７では分割パラメタが1次元の例を示しているが、分割パラメタが多次元で、ステップS332では最急降下法や共役勾配法により新しいパラメタを生成してもよい。また、前記は一例であり、これに限るものではない。
【００８７】
本実施の形態によれば、マッチング表における対象オブジェクトの位置的な分布を考慮した評価関数に基づいてマッチング表を評価するので、マッチング処理の指針に合ったマッチング表を生成することができる。
【００８８】
また、生成したマッチング表の評価関数の値やその変化を利用できるので、簡単な初期値、制約条件によって、マッチング処理の指針に合ったマッチング表を生成することができる。
【００８９】
更に、評価関数の値やその変化を利用して、分割パラメタの生成を繰り返すので、分割パラメタの取る範囲が広い場合や分割パラメタの次元数が多い場合でも、現実的な時間で、マッチング処理の指針に合ったマッチング表を生成することができる。
＜第２の実施の形態＞
第２の実施の形態を説明する。
【００９０】
図８は、第２の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【００９１】
図８に示すマッチング表評価システムは、配置記憶手段100と、制約記憶手段101と、分割パラメタ生成手段102と、マッチング表生成手段103と、分割評価手段11と、マッチング表記憶手段12を備える。なお、図８において第１の実施の形態と同じ構成部分については、図１と同じ符号を付し、説明を省略する。
【００９２】
分割パラメタ生成手段102は、配置図を格子領域に分割する分割パラメタを、制約記憶手段101に記憶されている制約を満たすように生成する。分割パラメタは、例えば、格子のサイズや格子分割の起点がある。格子のサイズは縦横で別のパラメタでも構わない。また、前記は一例であり、分割パラメタはこれらに限るものではない。
【００９３】
次に、図９のフローチャートを参照して、本実施の形態のマッチング表評価システムの動作を説明する。図９は、本実施の形態のマッチング表評価システムの動作を示すプローチャートである。
【００９４】
第２の実施の形態のマッチング表評価システムは、まず、分割パラメタ生成手段102が制約記憶手段101から格子分割の制約条件を取得する(ステップS201)。
【００９５】
次に、分割パラメタ生成手段102は、取得した制約条件を満たすような分割パラメタを複数生成する(ステップS202)。
【００９６】
その後、マッチング表生成手段103は、配置記憶手段100から配置図情報を取得し、分割パラメタ生成手段102からステップS202で生成した分割パラメタを取得する(ステップS211)。
【００９７】
次にマッチング表生成手段103は、ステップS211で取得した分割パラメタに基づいて、配置図の領域を格子分割し、ステップS202で生成した分割パラメタの個数分のマッチング表を生成する(ステップS212)。
【００９８】
そして、分割評価手段11は、ステップS212で生成した各マッチング表について、マッチング表に記録されている対象オブジェクトの位置的な分布に基づく評価関数を計算する(ステップS221)。最後に、分割評価手段11がステップS221の結果から適するマッチング表を選び、このマッチング表をマッチング表記憶手段12に格納する(ステップS222)。
【００９９】
本実施の形態によるマッチング表の生成の動作をより具体的に説明する。
【０１００】
例えば、格子分割の制約条件が、格子サイズの最大値Lmax、格子サイズの最小値Lmin、格子サイズの刻み幅ΔLによって与えられているとする。
【０１０１】
また、配置図は正方形の格子により格子分割されるものとし、分割パラメタは格子サイズ(格子の1辺の長さ)とする。
【０１０２】
配置図情報は図１０のようなものであるとする。
【０１０３】
まず、分割パラメタ生成手段102の動作(ステップS201、S202)を説明する。
【０１０４】
分割パラメタ生成手段102は、制約記憶手段101から、Lmax、Lmin、ΔLを読み込む(ステップS201)。
【０１０５】
次に、分割パラメタ生成手段102は、格子サイズを、L3=Lmax、L2=Lmax-ΔL、L1=L2-ΔL=Lmax-2ΔL、……、Ln=Lmax-nΔLのように生成する。
【０１０６】
格子サイズの生成は Ln が Ln-ΔL<Lmin≦Ln となるまで、繰り返される(ステップS202)。
【０１０７】
以下、ステップS202により、格子サイズL1>L2>L3が生成された、すなわちL3-ΔL<Lmin≦L3 として説明する。
【０１０８】
次に、マッチング表生成手段103の動作(ステップS211、S212)を説明する。
【０１０９】
前記の例では、マッチング表生成手段103は図１０の配置図情報とステップS202により生成された格子サイズL1、L2、L3を取得する(ステップS211)。
【０１１０】
この分割パラメタL1、L2、L3を用いて、マッチング表生成手段103は、配置図領域を格子分割してマッチング表を生成する(ステップS212)。
【０１１１】
図１２はマッチング表生成手段103の動作の一例を示す説明図である。
【０１１２】
マッチング表生成手段103は、ステップS212で、格子サイズL1、L2、L3から、図１１のMT21、MT22、MT23のようなマッチング表を生成する。
【０１１３】
次に、分割評価手段11の動作(ステップS221、S222)を説明する。尚、ステップS212で取得したマッチング表をMT21、 MT22、 MT23、評価関数をfとおき、評価関数fが最小の時にマッチング表が適するものとする。
【０１１４】
まず、各マッチング表に対する評価関数値 f(MT21)、 f(MT22)、 f(MT23)を計算する。
【０１１５】
ステップS221における評価関数値の計算の一例を、図１2を参照して説明する。
【０１１６】
図１２は評価関数値の計算を模式的に示す説明図である。
【０１１７】
ステップS212で取得したマッチング表をMT21、 MT22、 MT23とし、黒丸が対象オブジェクトを表すとする。
【０１１８】
評価関数は、マッチング表MTに対して、対象オブジェクトが存在する格子における対象オブジェクト数の平均F(MT)と格子の1辺の長さL(MT)の組g(MT)=(F(MT)、 L(MT))とする。
【０１１９】
評価関数gの大小関係は任意のマッチング表MT1、MT2に対して、F(MT1)<F(MT2)ならばg(MT1)<g(MT2)とし、F(MT1)=F(MT2)の場合、L(MT1)>L(MT2)ならばg(MT1)<g(MT2)とする。
【０１２０】
F(MT)は、移動体が対象オブジェクトの存在する格子領域内部に均一に分布するときのマッチング処理における距離計算の回数の期待値を表す。
【０１２１】
L(MT)はマッチング表の格子数の2乗に反比例するので、マッチング表が使用する記憶容量の2乗に反比例する。よって、g(MT)が小さい程、高速なマッチング処理が可能で使用する記憶容量が小さい、良いマッチング表といえる。
【０１２２】
本例では、マッチング表MT21、 MT22、 MT23の格子サイズをそれぞれL1、 L2、 L3とおくと、L3<L2<L1 である。
【０１２３】
マッチング表MT21において、建物が存在する格子は、格子(0、1)、 (1、0)であり、格子(0、1)に1つ対象オブジェクトが存在し、格子(1、0)に2つ対象オブジェクトが存在する。よって、F(MT21)=3/2=1.5である。
【０１２４】
同様に、マッチング表MT22において、建物が存在する格子は、格子(0、2)、 (1、1)、(2、0)であり、それぞれの格子に1つ対象オブジェクトが存在する。よって、F(MT22)=3/3=1である。
【０１２５】
同様に、マッチング表MT23において、建物が存在する格子は格子(0、3)、 (2、0)、 (2、2)、 (3、2)であり、それぞれの格子に1つ対象オブジェクトが存在する。よって、F(MT23)=1である。
【０１２６】
ステップS222の動作を詳細に説明する。
【０１２７】
評価関数fが最小の時にマッチング表が適するものとする。
【０１２８】
ステップS222による評価関数値 g (MT21)、 g (MT22)、g (MT23)を比較することで、マッチング表を求め、マッチング表記憶手段12に格納する。
【０１２９】
ステップS222の動作の一例を図１２を参照して説明する。
【０１３０】
3つのマッチング表に対応する対象オブジェクトが存在する格子における対象オブジェクト数の平均F(MT)は、F(MT21)=3/2=1.5、F(MT22)=3/3=1、F(MT23)=1である。畑がって、マッチング表MT22、 MT23が平均対象オブジェクト数Fを最小にする。そして、ふたつのマッチング表の格子サイズLは L3<L2である。よって、分割評価手段11は、評価関数g(MT22)=(F(MT22)、 L(MT22))が最小と判断し、この、評価関数g(MT22)に対応するマッチング表MT22を適したマッチング表として選ぶ。
【０１３１】
なお、前記の評価関数は一例であり、これらに限るものではない。
【０１３２】
評価関数は、対象オブジェクトの分布に基づき、マッチング処理の方針に合致する指標を示すようなものであればよい。
【０１３３】
例えば、評価関数は、マッチング表が持つ全格子の数に対する対象オブジェクトが1つ以下である格子の数の割合とし、評価関数値が最大のマッチング表を適するものとしてもよい。格子領域内部に含まれる対象オブジェクトが1つの場合、距離計算が不要であるため、この評価関数は、移動体が対象オブジェクトの存在する格子領域内部に均一に分布する場合の、マッチング処理時に距離計算が不要である確率を示している。よって、この評価関数の値が大きい程、高速にマッチング処理できると期待でき、マッチング処理を高速に行いたい場合のマッチング表を評価するのに適する。
【０１３４】
また、評価関数は、格子(i、j)に対する移動体の存在確率p(i、j)を予め与えておき、格子(i、j)の領域に含まれる対象オブジェクト数n(i、j)としたときに、Σp(i、j)n(i、j) と定義し、前記評価関数が最小のマッチング表を適するものとしてもよい。この評価関数は、マッチング処理における距離計算の回数の期待値を示している。よって、この評価関数の値が小さい程高速にマッチング処理できると期待でき、マッチング処理を高速に行いたい場合のマッチング表を評価するのに適する。
【０１３５】
上述した評価関数は一例であり、マッチング処理を高速に行いたい場合や、マッチング表で使用される記憶容量を少なくしたい場合等、適時マッチング処理の方針にかなう評価関数を導入する。
【０１３６】
本実施の形態によれば、マッチング表生成手段103が配置図を分割するため、事前に配置図を分割したマッチング表を複数準備することなく、マッチング処理の方針に適したマッチング表を生成することができる。
＜第３の実施の形態＞
図１３は、第３の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【０１３７】
図１３に示すマッチング表評価システムは、マッチング表候補記憶手段10と、分割評価手段11と、マッチング表記憶手段12を備える。
【０１３８】
マッチング表候補記憶手段10は、複数のマッチング表を記憶する。例えば、図１に示すようなマッチング表が記憶されている。
【０１３９】
分割評価手段11は、入力されたマッチング表に対し、与えられた評価関数の値を配置図上の対象オブジェクトの分布に基づき計算する。
【０１４０】
評価関数の値を計算した結果から、最適なマッチング表を選択し、それを出力する。
【０１４１】
マッチング表記憶手段12は、分割評価手段11が選択したマッチング表を記憶する。
【０１４２】
次に、図１４のフローチャートを参照して、本実施の形態のマッチング表評価システムの動作を説明する。図１４は、第３の実施の形態のマッチング表評価システムの動作を示すフローチャートである。
【０１４３】
本実施の形態のマッチング表評価システムでは、まず、分割評価手段11がマッチング表候補記憶手段10から、マッチング表候補記憶手段10に記憶されている複数のマッチング表を取得する(ステップS11)。
【０１４４】
次に、分割評価手段11が、ステップS11で取得したそれぞれのマッチング表について、マッチング表に記録されている対象オブジェクトの位置的な分布に基づく評価関数を計算する(ステップS12)。
【０１４５】
最後に、分割評価手段11がステップS12の結果から適するマッチング表を選び、このマッチング表をマッチング表記憶手段12に格納する(ステップS13)。
【０１４６】
ステップS12、ステップS13は、上述した第２の実施の形態におけるステップS221、S222と同様なものなので、詳細な説明は省略する。
【０１４７】
本実施の形態によれば、マッチング処理の方針に合ったマッチング表を得ることができる。理由は、対象オブジェクトの分布を考慮した評価関数により、複数のマッチング表を評価して、その中からマッチング表を選択するからである。
【実施例１】
【０１４８】
実施例１を説明する。
【０１４９】
実施例１は、第１の実施の形態をネットワークサービスに適用し、具体的な数値を用いた例である。
【０１５０】
図２２は実施例１の構成を示すブロック図である。
【０１５１】
実施例１は、データ記憶装置として磁気ディスク記憶装置600と、データ処理装置としてサーバコンピュータ610と、移動体620と、ネットワーク630とを、備えている。
【０１５２】
磁気ディスク記憶装置600は、配置記憶手段100と、制約記憶手段101と、分割パラメタ記憶手段122と、マッチング表記憶手段12とを備えている。
【０１５３】
サーバコンピュータ610は、分割パラメタ初期値生成手段121と、マッチング表生成手段103と、分割評価手段11と、分割パラメタ更新手段123とを備えている。
【０１５４】
サーバコンピュータ610と移動体620とは、ネットワーク630を介して、データの通信を行うように構成されている。
【０１５５】
本実施例１では、移動体620からのマッチング処理の要求に応答して、処理がなるべく高速に、かつ、記憶容量が少なくなるようなマッチング表を選択するものとする。また、移動体620の位置情報から、移動体620をほぼ中心とする所定の範囲の配置図を選択するそして、その配置図は1つの頂点を原点(0、0)とする直行座標系が導入されており、配置図の表す領域には、図１５に示すように5つの対象オブジェクトが分布しているものとする。この配置図において、対象オブジェクトを半径10の円板で近似し、円板の中心の座標で表現するとする。
【０１５６】
配置記憶手段100において、対象オブジェクトの配置情報は図１６に示すように記憶されている。本実施例では、座標(0、0)を起点として、対象オブジェクトが配置された配置図の領域を正方形の格子で分割し、分割パラメタは格子サイズとする。
【０１５７】
格子分割の制約は格子サイズとし、最大格子サイズと最小格子サイズとの間で制約を受けるものとする。また、格子分割の終了条件はステップS311からステップS333までの繰り返しにおける格子サイズの差分が予め設定されている最小値となった場合とする。そして、本実施例１では、制約記憶手段101には、図１７に示すように、最大格子サイズLmax=500、最小格子サイズLmin=100、格子サイズの差分の最小値Δmin=50が記憶されているものとする。
【０１５８】
本実施例１において、評価関数は、マッチング表中に対象オブジェクトが1つ存在する格子数／マッチング表中の全格子数とする。そして、評価関数が最大であるマッチング表が移動体620のマッチング処理に適したものとする。以下、格子サイズLに対する評価関数値をF(L)とおく。
【０１５９】
本実施例１では、格子サイズを2分法により求めるものとし、分割パラメタの初期値は最大格子サイズ、最小格子サイズ、最大格子サイズと最小格子サイズの中央値とする。
【０１６０】
まず、分割パラメタ初期値生成手段121は制約記憶手段101から制約条件として、Lmax=500、Lmin=100、Δmin=50を読み込む(ステップS301)。
【０１６１】
次に、分割パラメタの初期値として、最大格子サイズLmax、最小格子サイズLminの中央値を計算し、(500+100)/2=300を得る。
【０１６２】
その結果、分割パラメタの初期値として格子サイズ(100、300、500)を生成し(ステップS302)、分割パラメタ記憶手段122に記憶する(ステップS303)。
【０１６３】
マッチング表生成手段103は、格子サイズのリストと、図16に示す配置図情報を取得する(ステップS311)。
【０１６４】
格子サイズのリストと配置図情報を取得した後、マッチング表生成手段103は配置図を分割する(ステップS312)。ステップS312により、マッチング表生成手段103は図１８に示すマッチング表を得る。
【０１６５】
図１８(a)は格子サイズ500で格子分割したマッチング表、図１８(b)は格子サイズ100で格子分割したマッチング表、図１８(c)は格子サイズ300で格子分割したマッチング表である。
【０１６６】
マッチング表生成手段103は、生成したマッチング表をマッチング表記憶手段12に格納する(ステップS313)。
【０１６７】
分割評価手段11は、図１８のマッチング表に対し、評価関数値を計算する(ステップS321)。
【０１６８】
図１８(a)には対象オブジェクト数が1である格子が0個存在し（中央の対象オブジェクトが各格子に属するので、各格子の対象オブジェクト数は２である）、格子数は4なので、評価関数値F(500)=0/4=0.0000である。図１８(b)には対象オブジェクト数が1である格子が8個存在し（中央の対象オブジェクトが属する格子数は4である）、格子数は100なので、評価関数値F(100)=8/100=0.0800である。図１８(b)には対象オブジェクト数が1である格子が5個存在し、格子数は16なので、評価関数値F(300)=5/16=0.3125である。
【０１６９】
分割パラメタの生成は1回目なので、終了しない(ステップS331)。
【０１７０】
次に格子分割する格子サイズとして、(100+300)/2=200とする(ステップS332)。
【０１７１】
格子サイズ200を分割パラメタ記憶手段122に格納する(ステップS333)。
【０１７２】
ステップS311〜S333までの1回目の処理の後、第2回目のマッチング表の生成、評価を行う。
【０１７３】
格子サイズ(200、300、500)によるマッチング表を生成し、マッチング表記憶手段12に格納する(ステップS311〜S313)。
【０１７４】
次に、格子サイズ(200、300、500)のマッチング表に対し、評価関数Fの値を求める。
【０１７５】
格子サイズ200で配置図を分割すると、図１９に示すように、対象オブジェクト数が1である格子は5個存在し、格子数は25なので、評価関数値F(200)=5/25=0.200である(ステップS321)。
【０１７６】
格子サイズの差は|300-200|=100>50（=Δmin）なので、終了しない(ステップS331)。
【０１７７】
F(500)<F(200)<F(300)なので、次に格子分割する分割サイズとして、(300+500)/2=400とし、分割パラメタ記憶手段122に格納する(ステップS332〜S333)。
【０１７８】
3回目のマッチング表の生成、評価を行う。
【０１７９】
格子サイズ(300、400、500)によりマッチング表を生成し、マッチング表記憶手段12に格納する(ステップS311〜S313)。
【０１８０】
新たに生成したマッチング表に対し、評価関数値を求める。格子サイズ400で配置図を分割すると、図２０に示すように、対象オブジェクト数が1である格子は3個存在し、格子数は9なので、F(400)=3/9=0.3333である(ステップS321)。
【０１８１】
格子サイズの差は|300-400|=100>50（=Δmin）なので、終了しない(ステップS331)。
【０１８２】
F(500)<F(300)<F(400)なので、次に格子分割する分割サイズとして、(400+300)/2=350とし、分割パラメタ記憶手段122に格納する(ステップS332〜S333)。
【０１８３】
4回目のマッチング表の生成、評価を行う。
【０１８４】
格子サイズ(300、350、400)によりマッチング表を生成し、マッチング表記憶手段12に格納する(ステップS311〜S313)。
【０１８５】
新たに生成したマッチング表に対し、評価関数値を求める。
【０１８６】
格子サイズ350で配置図を分割すると、図２１に示すように、対象オブジェクト数が1である格子は5個存在し、格子数は9なので、F(350)=5/9=0.5556である(ステップS321)。
【０１８７】
格子サイズの差は|400-350|=50（=Δmin）なので、終了する(ステップS331)。
【０１８８】
このようにして、評価関数が最大である格子サイズ350のマッチング表を得る。
【０１８９】
上述した実施の形態及び実施例において説明した、分割評価手段１１、分割パラメタ生成手段１０２、マッチング表生成手段１０３、分割パラメタ初期値生成手段１２１、分割パラメタ更新手段１２３は、プログラムによって動作するコンピュータによっても実現できる。
【０１９０】
以上好ましい実施の形態及び実施例をあげて本発明を説明したが、本発明は必ずしも上記実施の形態及び実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形し実施することが出来る。
【産業上の利用可能性】
【０１９１】
本発明は、大量の移動体の位置情報を象オブジェクトに対応付ける処理を行う用途に好適に適用できる。
【図面の簡単な説明】
【０１９２】
【図１】図１はマッチング表のデータ構造の例を示す説明図である。
【図２】図２はマッチング表の例を模式的に示す説明図である。
【図３】図３は第１の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【図４】図４は配置記憶手段100が記憶する配置図情報の一例を示す説明図である。
【図５】図５は制約記憶手段101に記憶されている格子分割の制約条件の一例を示した図である。
【図６】図６は第１の実施の形態におけるマッチング表評価システムの動作を示すフローチャートである。
【図７】図７は分割パラメタと評価関数との関係のグラフの一例を示す説明図である。
【図８】図８は第２の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【図９】図９は第２の実施の形態のマッチング表評価システムの動作を示すプローチャートである。
【図１０】図１０は配置図情報の一例を模式的に示す説明図である。
【図１１】図１１はマッチング表生成手段による格子分割の一例を示す説明図である。
【図１２】図１２は評価関数値の計算を模式的に示す説明図である。
【図１３】図１３は、第３の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【図１４】図１４は第３の実施の形態のマッチング表評価システムの動作を示すフローチャートである。
【図１５】図１５は実施例１における配置図情報を示す説明図である。
【図１６】図１６は実施例１における配置記憶手段100が記憶する配置図を示す説明図である。
【図１７】図１７は実施例１における制約記憶手段101が記憶する制約を示す説明図である。
【図１８】図１８は実施例１における配置図の1回目の格子分割を模式的に示す説明図である。
【図１９】図１９は実施例１における配置図の2回目の格子分割を模式的に示す説明図である。
【図２０】図２０は実施例１における配置図の3回目の格子分割を模式的に示す説明図である。
【図２１】図２１は実施例１における配置図の4回目の格子分割を模式的に示す説明図である。
【図２２】図２２は実施例１の構成を示すブロック図である。
【符号の説明】
【０１９３】
１１ 分割評価手段
１２ マッチング表記憶手段
１３ マッチング表候補記憶手段
１００ 配置記憶手段
１０１ 制約記憶手段
１０２ 分割パラメタ生成手段
１０３ マッチング表生成手段
１２１ 分割パラメタ初期値生成手段
１２２ 分割パラメタ記憶手段
１２３ 分割パラメタ更新手段
１３０ 分割パラメタ生成手段
【技術分野】
【０００１】
本発明は、マッチング表評価システム、その方法及びプログラムに関する。
【背景技術】
【０００２】
交通管制や物流管理などでは、車や人が送信する位置情報をサーバに収集し、得られた位置情報を用いて、車や人が現在位置している道路や建物を特定する処理が大量に行われており、このような処理をマッチング処理と呼ぶ。
【０００３】
車や人の位置情報を送信する例としてプローブカーやGPS付き携帯端末がある。プローブカーやGPS付き携帯端末のような移動可能でサーバに位置座標を送信する物体を以下移動体と呼ぶ。また、道路や建物のような地図上に位置が記録されている物体を以下対象オブジェクトと呼ぶ。
【０００４】
マッチング処理では、移動体と最も近い対象オブジェクトを、現在位置している対象オブジェクトとして特定する。そのために、全ての対象オブジェクトについて、移動体と対象オブジェクトとの間の距離を計算し、距離が最小の対象オブジェクトを判定する必要がある。
【０００５】
しかし、地図上の全ての対象オブジェクトとの距離を計算する処理には時間がかかるため、対象オブジェクトが配置された領域を格子状に分割して（以下、格子分割と記載する）、距離計算の対象とする対象オブジェクト数を減らす手法がある。この方法では、マッチング処理の前に対象オブジェクトが配置された領域を格子分割し、各格子内の領域（以下、格子領域と記載する）のに存在する対象オブジェクトを事前に求めておく。そして、この処理で求められる、各格子とその格子領域内部の対象オブジェクトとの対応表を、以下マッチング表と呼ぶ。
【０００６】
マッチング表の例を図１に示す。図１はマッチング表の例を説明する説明図である。
【０００７】
図１の例に示すマッチング表では、格子と、その格子領域内部の対象オブジェクトのIDとを対応付けている。図１（ａ）のように、配置図の領域上に対象オブジェクト 1、 2、 3、 4、 5が分布しているときは、図１（ｂ）のようなマッチング表になる。尚、以下の説明において、少なくともマッチング処理を行う領域とこの領域内に存在する対象オブジェクトの位置との関係を示したものを配置図と記載する。
【０００８】
マッチング処理時には、まず、移動体の位置を含む格子を決定する。例えば、配置図上にxy直交座標系が導入されており、x軸、y軸に平行な正方形の格子により格子分割されている時、移動体の位置を含む格子は、移動体のx、y座標を格子の辺の長さで除算することで求めることができる。
【０００９】
次に、マッチング表を引き、移動体の位置を含む格子領域に存在する対象オブジェクトを求め、求めた対象オブジェクトと移動体との距離計算を行う。
【００１０】
このようにマッチング表を用いることで、距離計算の回数を減らす。
【００１１】
特許文献１には移動体の速度や進行方向など、移動体の情報を使用して格子分割を行い、マッチング表を生成する装置が記載されている。
【特許文献１】特開2007-304944号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
一方、最適なマッチング表はマッチング処理の方針により異なる。最適性の基準の一例として、マッチング処理の速度が高いほど良いという方針の場合、マッチング速度が最大になるマッチング表が最適である。また、マッチング表で使用される記憶容量が小さいほど良いという方針の場合、マッチング表で使用する記憶容量が最小になるマッチング表が最適である。従って、マッチング表の選択は、マッチング処理の方針に合致する必要がある。
【００１３】
しかし、特許文献1の技術は、このような事情を考慮しておらず、マッチング処理の方針に適したマッチング表を選択する為にマッチング表を評価するという概念がなかった。
【００１４】
そこで、本発明は上記課題に鑑みて発明されたものであって、その目的は、マッチング処理の方針に適したマッチング表を評価できるマッチング表評価システム、その方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００１５】
上記課題を解決する本発明は、対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価する分割評価手段を有するマッチング表評価システムである。
【００１６】
上記課題を解決する本発明は、対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価するマッチング表評価方法である。
【００１７】
上記課題を解決する本発明は、対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価するマッチング表評価処理を情報処理装置に実行させるプログラムである。
【発明の効果】
【００１８】
本発明によれば、マッチング処理の方針に適したマッチング表を得ることができる。
【発明を実施するための最良の形態】
【００１９】
＜第１の実施の形態＞
第１の実施の形態を説明する。
【００２０】
まず、マッチング表について説明する。尚、以下の説明において、少なくともマッチング処理を行う領域とこの領域内に存在する対象オブジェクトの位置との関係を示したものを配置図と記載し、この配置図の領域を格子状に分割することを格子分割と記載する。
【００２１】
図１にマッチング表の例を示す。
【００２２】
図１の例に示すマッチング表では、格子と、その格子領域内部の対象オブジェクトのIDとを対応付けている。図１（ａ）のように、配置図の領域上に対象オブジェクト 1、 2、 3、 4、 5が分布しているときは、図１（ｂ）のようなマッチング表になる。前記は一例であり、これに限るものではない。また、前記の例では対象オブジェクトは建物など面であるものとしたが、道路などの線でも、特定の地点などを表す点でも構わない。また、前記の例では配置図やマッチング表の領域を平面としたが、2次元平面に限らない。例えば、曲面や3次元空間でも構わない。
【００２３】
このようなマッチング表において、最適なマッチング表はマッチング処理の具体的な方針により異なる。上述したように、マッチング処理の速度が高いほど良いという方針の場合、マッチング速度が最大になるマッチング表が最適である。また、マッチング表で使用される記憶容量が小さいほど良いという方針の場合、マッチング表で使用される記憶容量が最小になるマッチング表が最適である。
【００２４】
例えば、対象オブジェクトの密度に対して格子が大きく格子分割が粗い場合、距離計算の回数はあまり減らない。逆に、対象オブシェクとの密度に対して格子が小さく格子分割が細かい場合、これよりも少し粗い格子分割と比べて距離計算の回数はあまり変わらないにもかかわらず、格子数が多くなるため、より大きな記憶容量が使用される。
【００２５】
図２を参照して前記の問題について説明する。図２中のMT01a、 MT01b、 MT02a、 MT02bは対象オブジェクトの配置と格子分割との関係を模式的に示した説明図である。
【００２６】
MT01aとMT01bは同一の配置図で格子分割の間隔（格子の１辺の長さ）のみ異なる。MT02aとMT02bも同一の配置図で格子分割の間隔（格子の１辺の長さ）のみ異なる。
【００２７】
MT01aとMT01bの配置図では、中央部に対象オブジェクトが多く存在しているため、MT01aによる格子分割では、中央の格子内の対象オブジェクトの数が格子分割を行わない場合とほとんど変わらない。そのため、MT01aのように粗い格子分割では、格子分割を行わない場合と比べて距離計算の回数がほとんど減少しない。よって、MT01aを使用したマッチング処理は低速である。
【００２８】
そこで、MT01bのようにより細かく格子分割を行うことで、1つの格子領域内部に含まれる対象オブジェクトの数が減少する。その結果、距離計算の回数が減少するため、より高速なマッチング処理が実現される。よって、マッチング処理の速度が高速なほど良いとい方針の場合には、MT01bは適切なマッチング表である。
【００２９】
一方、MT02aとMT02bの配置図では、MT02aによる格子分割は細か過ぎる。MT02aとMT02bとは、いずれも各格子領域内部に1つの対象オブジェクトしか存在していない。そのため、MT02aの距離計算の回数と、MT02bの距離計算の回数とは変わらないので、マッチング処理の速度は変わらない。しかし、マッチング表MT02aは格子数が多いために、使用する記憶容量は MT02bよりも大きい。よって、マッチング処理の速度が同じならば、マッチング表で使用される記憶容量が少ないほど良いという方針であるならば、MT02aは適切なマッチング表ではない。
【００３０】
図２の例において MT01b、MT02b のマッチング表を、マッチング処理の方針に適したマッチング表を選ぶことは、配置図上の対象オブジェクトの分布を考慮しなければならない。
【００３１】
そこで、本実施の形態では、マッチング処理の方針に適したマッチング表を得る為に、マッチング表の対象オブジェクトの位置的な分布を考慮した評価関数によって、マッチング表を評価する。
【００３２】
続いて、第１の実施の形態におけるマッチング表評価システムを説明する。
【００３３】
図３は、第１の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【００３４】
図３に示すマッチング表評価システムは、配置記憶手段100と、制約記憶手段101と、分割パラメタ生成手段130と、分割パラメタ記憶手段122と、マッチング表生成手段103と、分割評価手段11と、マッチング表記憶手段12とを備える。
【００３５】
配置記憶手段100は、配置図の情報（以下、配置図情報と記載する）を記憶する。配置図情報は、少なくともマッチング処理を行う領域の範囲の情報と、前記の領域内に存在する対象オブジェクトの位置情報とを含む情報である。
【００３６】
配置記憶手段100が記憶する配置図情報の一例を示す説明図を図４に示す。図４の示す例において、配置図の領域は長方形とし、緯度と経度とによる座標系が導入されているものとする。また、1つの対象オブジェクトは配置図上の1点であるとする。
【００３７】
配置図情報は配置図の表現する範囲を表す配置図領域情報T010と、配置図の上に存在する対象オブジェクトの位置情報を表す配置図上対象オブジェクト情報T011とによって構成される。
【００３８】
配置図領域情報T010は、図４（ａ）に示すように原点T0101とサイズT0102とで構成される。原点T0101は配置図の領域の原点の座標を表す。サイズT0102は、配置図の領域の縦横のサイズを表す。
【００３９】
配置図上対象オブジェクト情報T011は、図４（ｂ）に示すように識別子であるIDT0111と座標T0112との組で構成される。IDT0111は、配置図上に存在する対象オブジェクトの識別子である。座標T0112は対象オブジェクトの存在する位置の座標を表す。
【００４０】
尚、上述の例では対象オブジェクトを点として扱っているが、対象オブジェクトを線として扱っても、面として扱ってもよい。対象オブジェクトを線として扱う場合、対象オブジェクトを長さ一定の線分で表し、配置図情報上は中心の位置と方向で表現してもよい。また、対象オブジェクトを線分で表し、配置図情報上は両端の位置で表現してもよい。対象オブジェクトを面として扱う場合、例えば、対象オブジェクトを円で表し、配置図情報上は中心の位置と半径で表現してもよい。また、対象オブジェクトを長方形で表し、配置図情報上は各頂点の位置で表現してもよい。また、複雑な形状の領域については、円や長方形の組み合わせで表現してもよい。更に、マッチング表を3次元空間で考える場合、点として扱っても、線や面として扱っても、3次元の空間として扱ってもよい。前記は一例であり、これらに限るものではない。
【００４１】
制約記憶手段101は、配置図を格子領域に分割する際に用いる分割パラメタを生成する時の格子分割の制約条件が記憶されている。
【００４２】
制約記憶手段101に記憶されている格子分割の制約条件の一例を示す説明図を図５に示す。
【００４３】
図５が示す例において、格子分割の制約条件は分割パラメタの制約リストT100であり、最大格子サイズT1001、最小格子サイズT1002、格子分割の刻み幅T1003により構成される。最大格子サイズT1001は分割パラメタ生成手段130が生成する格子サイズの最大値である。最小格子サイズT1002は分割パラメタ生成手段130が生成する格子サイズの最小値である。
【００４４】
図５が示す例において、最大格子サイズは500m、最小格子サイズは100mである。格子サイズ刻み幅T1003は、生成する格子サイズ間の差である。
【００４５】
すなわち、生成する格子サイズを、L(1)、L(2)、L(3)、…、L(n) (ただし、L(1)>L(2)>L(3)>……>L(n))、格子サイズ刻み幅を、ΔLとおくと、
L(2)=L(1)-ΔL、L(3)=L(2)-ΔL、……、L(n)=L(n-1)-ΔLである。
【００４６】
図５が示す例では、格子サイズ 500m、 490m、 480m、……、100mが分割パラメタとして許容される。
【００４７】
制約条件には、格子サイズの取り得る範囲や、格子分割の起点の範囲、分割パラメタの刻み幅もある。また、例えば、分割パラメタ間の比や分割パラメタの個数等を制約条件としても構わない。また、前記は一例であり、制約条件はこれらに限るものではない。
【００４８】
分割パラメタ生成手段130は、配置図の格子分割における分割パラメタを生成する。そして、分割パラメタ生成手段130は、分割パラメタ初期値生成手段121と、分割パラメタ更新手段123とを備える。
【００４９】
分割パラメタ初期値生成手段121は、配置図の分割パラメタの初期値を制約記憶手段101に記憶されている制約を満たすように生成する。分割パラメタとしては、例えば、格子のサイズや格子分割の起点がある。また、格子のサイズは縦横で別のパラメタでも構わない。尚、上述の分割パラメタは一例であり、分割パラメタはこれらに限るものではない。
【００５０】
分割パラメタ記憶手段122には、分割パラメタ初期値生成手段121や後述する分割パラメタ更新手段123で生成された分割パラメタが記憶される。尚、分割パラメタ記憶手段122は最後に生成された分割パラメタだけを記憶しても、以前に生成した分割パラメタを記憶していても構わない。
【００５１】
マッチング表生成手段103は、配置記憶手段100から配置図領域情報T010と配置図上対象オブジェクト情報T011とを取得し、分割パラメタ記憶手段122から分割パラメタを取得する。そして、取得した分割パラメタに基づいて、配置図領域情報T010と配置図上対象オブジェクト情報T011とに基づいて特定される配置図を格子領域に分割し、マッチング表を生成する。
【００５２】
分割評価手段11は、入力されたマッチング表に対し、評価関数の値を配置図上の対象オブジェクトの分布に基づき計算する。
【００５３】
ここで、評価関数について説明する。
【００５４】
評価関数は、対象オブジェクトの分布に基づき、マッチング処理の方針に合致する指標を示すようなものであればよい。
【００５５】
例えば、評価関数は、マッチング表が持つ全格子の数に対する対象オブジェクトが1つ以下である格子の数の割合とし、評価関数値が最大のマッチング表を適するものとしてもよい。格子領域内部に含まれる対象オブジェクトが1つの場合、距離計算が不要であるため、この評価関数は、移動体が対象オブジェクトの存在する格子領域内部に均一に分布する場合の、マッチング処理時に距離計算が不要である確率を示している。よって、この評価関数の値が大きい程、高速にマッチング処理できると期待でき、マッチング処理を高速に行いたい場合のマッチング表を評価するのに適する。
【００５６】
また、評価関数は、格子(i、j)に対する移動体の存在確率p(i、j)を予め与えておき、格子(i、j)の領域に含まれる対象オブジェクト数n(i、j)としたときに、Σp(i、j)n(i、j) と定義し、前記評価関数が最小のマッチング表を適するものとしてもよい。この評価関数は、マッチング処理における距離計算の回数の期待値を示している。よって、この評価関数の値が小さい程高速にマッチング処理できると期待でき、マッチング処理を高速に行いたい場合のマッチング表を評価するのに適する。
【００５７】
上述した評価関数は一例であり、マッチング処理を高速に行いたい場合や、マッチング表で使用される記憶容量を少なくしたい場合等、適時マッチング処理の方針にかなう評価関数を導入する。
【００５８】
分割評価手段11は、マッチング処理の方針に適したマッチング表を得る為に、入力されたマッチング表の評価関数の値を計算し、評価関数の値に基づいて、そのマッチング表を評価する。そして、予め定められた分割パラメタの更新の終了条件（マッチング処理の方針に合ったマッチング表である条件）を判定する。終了条件を満たさず動作を続行する場合は、新しい分割パラメタを生成する指示を、分割パラメタ更新手段123に通知する。
【００５９】
マッチング表記憶手段12は、分割評価手段11で、分割パラメタの更新の終了が判断され、マッチング処理の方針に適すると判断されたマッチング表が記憶される。
【００６０】
分割パラメタ更新手段123は、分割評価手段11の指示を受け、新しい分割パラメタを生成し、分割パラメタ記憶手段122に記憶する。
【００６１】
次に、図６のフローチャートを参照して、本実施の形態のマッチング表評価システムの動作を説明する。
【００６２】
図６は、本実施の形態のマッチング表評価システムの動作の一例を示すフローチャートである。
【００６３】
本実施の形態のマッチング表評価システムでは、まず、分割パラメタ初期値生成手段121が制約記憶手段101から、格子分割の制約条件を取得する(ステップS301)。
【００６４】
次に、分割パラメタ初期値生成手段121は、取得した制約条件を満たすような分割パラメタを1つまたは複数生成する(ステップS302)。
【００６５】
分割パラメタ初期値生成手段121は生成した分割パラメタを分割パラメタ記憶手段122に格納する(ステップS303)。
【００６６】
マッチング表生成手段103は、配置記憶手段100から配置図情報を取得し、分割パラメタ記憶手段122から分割パラメタを取得する(ステップS311)。その後、マッチング表生成手段103は、ステップS311で取得した分割パラメタに基づいて、配置図の領域を格子分割し、マッチング表を生成する(ステップS312)。そして、ステップS312で生成したマッチング表をマッチング表記憶手段12に保存する(ステップS313)。
【００６７】
分割評価手段11は、ステップS312で生成した各マッチング表について、対象オブジェクトの分布に基づく評価関数を計算する(ステップS321)。そして、計算した評価関数値に基づいて、予め定めた終了条件を満たしているか判定する(ステップS331)。そして、終了条件を満たさない場合、分割評価手段11は、制約に基づく新しい分割パラメタの生成を分割パラメタ更新手段123に指示する。
【００６８】
分割パラメタ更新手段123は、制約に基づく新しい分割パラメタを生成し(ステップS332)、生成した分割パラメタを分割パラメタ記憶手段122に格納する(ステップS333)。
【００６９】
そして、ステップS331において、終了条件を満たすまで、ステップS3111〜S313、S321、S331〜S333を繰り返す。
【００７０】
次に、本実施の形態のマッチング表評価システム具体的な動作例を説明する。
【００７１】
尚、以下の説明において、分割パラメタpによるマッチング表に対する評価関数の値をf(p)とおく。第n回目のマッチング表生成に使用する分割パラメタをp(n)とおく。そして、マッチング処理の方針として、処理がなるべく高速に、かつ、記憶容量が少なくなるようにバランスの取れたマッチング表を用いるものとし、評価関数fが最小値をとるようなマッチング表がマッチング処理の方針に適したマッチング表であるものとする。
【００７２】
まず、分割パラメタ初期値生成手段121は、分割パラメタの初期値p(0)を決定する(ステップS301〜S303)。
【００７３】
尚、分割パラメタ初期値生成手段121は、分割パラメタの範囲を制約し、初期値p(0)を、その制約された分割パラメタの範囲からランダムに選んでもよい。また、予め初期値p(0)を制約記憶手段101に格納しておいてもよい。また、初期値p(0)は1つに限られず、分割パラメタ初期値生成手段121は初期値p(0)を複数生成してもよい。また、前記は一例であり、これらに限るものではない。
【００７４】
マッチング表生成手段103は、分割パラメタの初期値p(0)により、配置図を格子分割してマッチング表を生成する(ステップS311〜S313)。その後、分割評価手段11は生成したマッチング表に対して評価関数値f(p0)を計算する(ステップS321)。
【００７５】
評価関数の計算後、分割評価手段11は、終了条件を判定する(ステップS331)。本実施例では、判定ステップS331への到達回数nが2回目以降でかつ、前回の分割パラメタとの差の絶対値|p(n)-p(n-1)|が所定の閾値ε未満であるかを判定する。
【００７６】
閾値εについて、図７を用いて説明する。図７は、分割パラメタpと評価関数fとの関係のグラフの一例を示す説明図である。閾値εは、例えば、評価関数fが図７に示されるような下に凸の所定関数であり、分割パラメタが反復法により求められる場合、評価関数の値f(p)が最小値として許容され、かつ、分割パラメタpに対して十分小さい定数として定義される。
【００７７】
尚、|(f(p(n))-f(p(n-1)))/f(p(n))|が閾値ε未満であるかを判定してもよい。また、前記の終了条件は一例であり、これに限るものではない。
【００７８】
終了条件を満たさない場合、分割評価手段11は、分割パラメタ更新手段123に、新しい分割パラメタの生成を指示する。
【００７９】
分割パラメタ更新手段123は新しい分割パラメタを生成して、その値に更新する(ステップS332)。新しい分割パラメタは、反復法、例えば、ニュートン法により、
p(n)=p(n-1)-f'(p(n-1))/f''(p(n-1))
で生成される。ただし、f'、f''はそれぞれ評価関数fの導関数、2次導関数とする。
【００８０】
または、新しい分割パラメタはセカント法により、
p(n)=p(n-1)-f'(p(n-1))(p(n-1)-p(n-2))/(f'(p(n-1))-f'(p(n-2)))
としてもよい。
【００８１】
もしくは、fの導関数を容易に求められない場合、補間法を使用してもよい。
【００８２】
前記は一例であり、これらに限るものではない。
【００８３】
新しい分割パラメタp(n)を生成後、分割パラメタ更新手段123はp(n)を分割パラメタ記憶手段122に格納する(ステップS333)。
【００８４】
そして、ステップS331において、終了条件を満たすまで、ステップS3111〜S313、S321、S331〜S333を繰り返す。
【００８５】
尚、分割パラメタ初期値生成手段121や分割パラメタ更新手段123で生成する分割パラメタは複数であってもよい。例えば、n回目の動作で分割パラメタp(n)、p(n)+Δpを生成し、f'(p(n))を (f(p(n)+Δp)-f(p(n)))/Δp で近似してもよい。また、前記は一例であり、これに限るものではない。
【００８６】
図７では分割パラメタが1次元の例を示しているが、分割パラメタが多次元で、ステップS332では最急降下法や共役勾配法により新しいパラメタを生成してもよい。また、前記は一例であり、これに限るものではない。
【００８７】
本実施の形態によれば、マッチング表における対象オブジェクトの位置的な分布を考慮した評価関数に基づいてマッチング表を評価するので、マッチング処理の指針に合ったマッチング表を生成することができる。
【００８８】
また、生成したマッチング表の評価関数の値やその変化を利用できるので、簡単な初期値、制約条件によって、マッチング処理の指針に合ったマッチング表を生成することができる。
【００８９】
更に、評価関数の値やその変化を利用して、分割パラメタの生成を繰り返すので、分割パラメタの取る範囲が広い場合や分割パラメタの次元数が多い場合でも、現実的な時間で、マッチング処理の指針に合ったマッチング表を生成することができる。
＜第２の実施の形態＞
第２の実施の形態を説明する。
【００９０】
図８は、第２の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【００９１】
図８に示すマッチング表評価システムは、配置記憶手段100と、制約記憶手段101と、分割パラメタ生成手段102と、マッチング表生成手段103と、分割評価手段11と、マッチング表記憶手段12を備える。なお、図８において第１の実施の形態と同じ構成部分については、図１と同じ符号を付し、説明を省略する。
【００９２】
分割パラメタ生成手段102は、配置図を格子領域に分割する分割パラメタを、制約記憶手段101に記憶されている制約を満たすように生成する。分割パラメタは、例えば、格子のサイズや格子分割の起点がある。格子のサイズは縦横で別のパラメタでも構わない。また、前記は一例であり、分割パラメタはこれらに限るものではない。
【００９３】
次に、図９のフローチャートを参照して、本実施の形態のマッチング表評価システムの動作を説明する。図９は、本実施の形態のマッチング表評価システムの動作を示すプローチャートである。
【００９４】
第２の実施の形態のマッチング表評価システムは、まず、分割パラメタ生成手段102が制約記憶手段101から格子分割の制約条件を取得する(ステップS201)。
【００９５】
次に、分割パラメタ生成手段102は、取得した制約条件を満たすような分割パラメタを複数生成する(ステップS202)。
【００９６】
その後、マッチング表生成手段103は、配置記憶手段100から配置図情報を取得し、分割パラメタ生成手段102からステップS202で生成した分割パラメタを取得する(ステップS211)。
【００９７】
次にマッチング表生成手段103は、ステップS211で取得した分割パラメタに基づいて、配置図の領域を格子分割し、ステップS202で生成した分割パラメタの個数分のマッチング表を生成する(ステップS212)。
【００９８】
そして、分割評価手段11は、ステップS212で生成した各マッチング表について、マッチング表に記録されている対象オブジェクトの位置的な分布に基づく評価関数を計算する(ステップS221)。最後に、分割評価手段11がステップS221の結果から適するマッチング表を選び、このマッチング表をマッチング表記憶手段12に格納する(ステップS222)。
【００９９】
本実施の形態によるマッチング表の生成の動作をより具体的に説明する。
【０１００】
例えば、格子分割の制約条件が、格子サイズの最大値Lmax、格子サイズの最小値Lmin、格子サイズの刻み幅ΔLによって与えられているとする。
【０１０１】
また、配置図は正方形の格子により格子分割されるものとし、分割パラメタは格子サイズ(格子の1辺の長さ)とする。
【０１０２】
配置図情報は図１０のようなものであるとする。
【０１０３】
まず、分割パラメタ生成手段102の動作(ステップS201、S202)を説明する。
【０１０４】
分割パラメタ生成手段102は、制約記憶手段101から、Lmax、Lmin、ΔLを読み込む(ステップS201)。
【０１０５】
次に、分割パラメタ生成手段102は、格子サイズを、L3=Lmax、L2=Lmax-ΔL、L1=L2-ΔL=Lmax-2ΔL、……、Ln=Lmax-nΔLのように生成する。
【０１０６】
格子サイズの生成は Ln が Ln-ΔL<Lmin≦Ln となるまで、繰り返される(ステップS202)。
【０１０７】
以下、ステップS202により、格子サイズL1>L2>L3が生成された、すなわちL3-ΔL<Lmin≦L3 として説明する。
【０１０８】
次に、マッチング表生成手段103の動作(ステップS211、S212)を説明する。
【０１０９】
前記の例では、マッチング表生成手段103は図１０の配置図情報とステップS202により生成された格子サイズL1、L2、L3を取得する(ステップS211)。
【０１１０】
この分割パラメタL1、L2、L3を用いて、マッチング表生成手段103は、配置図領域を格子分割してマッチング表を生成する(ステップS212)。
【０１１１】
図１２はマッチング表生成手段103の動作の一例を示す説明図である。
【０１１２】
マッチング表生成手段103は、ステップS212で、格子サイズL1、L2、L3から、図１１のMT21、MT22、MT23のようなマッチング表を生成する。
【０１１３】
次に、分割評価手段11の動作(ステップS221、S222)を説明する。尚、ステップS212で取得したマッチング表をMT21、 MT22、 MT23、評価関数をfとおき、評価関数fが最小の時にマッチング表が適するものとする。
【０１１４】
まず、各マッチング表に対する評価関数値 f(MT21)、 f(MT22)、 f(MT23)を計算する。
【０１１５】
ステップS221における評価関数値の計算の一例を、図１2を参照して説明する。
【０１１６】
図１２は評価関数値の計算を模式的に示す説明図である。
【０１１７】
ステップS212で取得したマッチング表をMT21、 MT22、 MT23とし、黒丸が対象オブジェクトを表すとする。
【０１１８】
評価関数は、マッチング表MTに対して、対象オブジェクトが存在する格子における対象オブジェクト数の平均F(MT)と格子の1辺の長さL(MT)の組g(MT)=(F(MT)、 L(MT))とする。
【０１１９】
評価関数gの大小関係は任意のマッチング表MT1、MT2に対して、F(MT1)<F(MT2)ならばg(MT1)<g(MT2)とし、F(MT1)=F(MT2)の場合、L(MT1)>L(MT2)ならばg(MT1)<g(MT2)とする。
【０１２０】
F(MT)は、移動体が対象オブジェクトの存在する格子領域内部に均一に分布するときのマッチング処理における距離計算の回数の期待値を表す。
【０１２１】
L(MT)はマッチング表の格子数の2乗に反比例するので、マッチング表が使用する記憶容量の2乗に反比例する。よって、g(MT)が小さい程、高速なマッチング処理が可能で使用する記憶容量が小さい、良いマッチング表といえる。
【０１２２】
本例では、マッチング表MT21、 MT22、 MT23の格子サイズをそれぞれL1、 L2、 L3とおくと、L3<L2<L1 である。
【０１２３】
マッチング表MT21において、建物が存在する格子は、格子(0、1)、 (1、0)であり、格子(0、1)に1つ対象オブジェクトが存在し、格子(1、0)に2つ対象オブジェクトが存在する。よって、F(MT21)=3/2=1.5である。
【０１２４】
同様に、マッチング表MT22において、建物が存在する格子は、格子(0、2)、 (1、1)、(2、0)であり、それぞれの格子に1つ対象オブジェクトが存在する。よって、F(MT22)=3/3=1である。
【０１２５】
同様に、マッチング表MT23において、建物が存在する格子は格子(0、3)、 (2、0)、 (2、2)、 (3、2)であり、それぞれの格子に1つ対象オブジェクトが存在する。よって、F(MT23)=1である。
【０１２６】
ステップS222の動作を詳細に説明する。
【０１２７】
評価関数fが最小の時にマッチング表が適するものとする。
【０１２８】
ステップS222による評価関数値 g (MT21)、 g (MT22)、g (MT23)を比較することで、マッチング表を求め、マッチング表記憶手段12に格納する。
【０１２９】
ステップS222の動作の一例を図１２を参照して説明する。
【０１３０】
3つのマッチング表に対応する対象オブジェクトが存在する格子における対象オブジェクト数の平均F(MT)は、F(MT21)=3/2=1.5、F(MT22)=3/3=1、F(MT23)=1である。畑がって、マッチング表MT22、 MT23が平均対象オブジェクト数Fを最小にする。そして、ふたつのマッチング表の格子サイズLは L3<L2である。よって、分割評価手段11は、評価関数g(MT22)=(F(MT22)、 L(MT22))が最小と判断し、この、評価関数g(MT22)に対応するマッチング表MT22を適したマッチング表として選ぶ。
【０１３１】
なお、前記の評価関数は一例であり、これらに限るものではない。
【０１３２】
評価関数は、対象オブジェクトの分布に基づき、マッチング処理の方針に合致する指標を示すようなものであればよい。
【０１３３】
例えば、評価関数は、マッチング表が持つ全格子の数に対する対象オブジェクトが1つ以下である格子の数の割合とし、評価関数値が最大のマッチング表を適するものとしてもよい。格子領域内部に含まれる対象オブジェクトが1つの場合、距離計算が不要であるため、この評価関数は、移動体が対象オブジェクトの存在する格子領域内部に均一に分布する場合の、マッチング処理時に距離計算が不要である確率を示している。よって、この評価関数の値が大きい程、高速にマッチング処理できると期待でき、マッチング処理を高速に行いたい場合のマッチング表を評価するのに適する。
【０１３４】
また、評価関数は、格子(i、j)に対する移動体の存在確率p(i、j)を予め与えておき、格子(i、j)の領域に含まれる対象オブジェクト数n(i、j)としたときに、Σp(i、j)n(i、j) と定義し、前記評価関数が最小のマッチング表を適するものとしてもよい。この評価関数は、マッチング処理における距離計算の回数の期待値を示している。よって、この評価関数の値が小さい程高速にマッチング処理できると期待でき、マッチング処理を高速に行いたい場合のマッチング表を評価するのに適する。
【０１３５】
上述した評価関数は一例であり、マッチング処理を高速に行いたい場合や、マッチング表で使用される記憶容量を少なくしたい場合等、適時マッチング処理の方針にかなう評価関数を導入する。
【０１３６】
本実施の形態によれば、マッチング表生成手段103が配置図を分割するため、事前に配置図を分割したマッチング表を複数準備することなく、マッチング処理の方針に適したマッチング表を生成することができる。
＜第３の実施の形態＞
図１３は、第３の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【０１３７】
図１３に示すマッチング表評価システムは、マッチング表候補記憶手段10と、分割評価手段11と、マッチング表記憶手段12を備える。
【０１３８】
マッチング表候補記憶手段10は、複数のマッチング表を記憶する。例えば、図１に示すようなマッチング表が記憶されている。
【０１３９】
分割評価手段11は、入力されたマッチング表に対し、与えられた評価関数の値を配置図上の対象オブジェクトの分布に基づき計算する。
【０１４０】
評価関数の値を計算した結果から、最適なマッチング表を選択し、それを出力する。
【０１４１】
マッチング表記憶手段12は、分割評価手段11が選択したマッチング表を記憶する。
【０１４２】
次に、図１４のフローチャートを参照して、本実施の形態のマッチング表評価システムの動作を説明する。図１４は、第３の実施の形態のマッチング表評価システムの動作を示すフローチャートである。
【０１４３】
本実施の形態のマッチング表評価システムでは、まず、分割評価手段11がマッチング表候補記憶手段10から、マッチング表候補記憶手段10に記憶されている複数のマッチング表を取得する(ステップS11)。
【０１４４】
次に、分割評価手段11が、ステップS11で取得したそれぞれのマッチング表について、マッチング表に記録されている対象オブジェクトの位置的な分布に基づく評価関数を計算する(ステップS12)。
【０１４５】
最後に、分割評価手段11がステップS12の結果から適するマッチング表を選び、このマッチング表をマッチング表記憶手段12に格納する(ステップS13)。
【０１４６】
ステップS12、ステップS13は、上述した第２の実施の形態におけるステップS221、S222と同様なものなので、詳細な説明は省略する。
【０１４７】
本実施の形態によれば、マッチング処理の方針に合ったマッチング表を得ることができる。理由は、対象オブジェクトの分布を考慮した評価関数により、複数のマッチング表を評価して、その中からマッチング表を選択するからである。
【実施例１】
【０１４８】
実施例１を説明する。
【０１４９】
実施例１は、第１の実施の形態をネットワークサービスに適用し、具体的な数値を用いた例である。
【０１５０】
図２２は実施例１の構成を示すブロック図である。
【０１５１】
実施例１は、データ記憶装置として磁気ディスク記憶装置600と、データ処理装置としてサーバコンピュータ610と、移動体620と、ネットワーク630とを、備えている。
【０１５２】
磁気ディスク記憶装置600は、配置記憶手段100と、制約記憶手段101と、分割パラメタ記憶手段122と、マッチング表記憶手段12とを備えている。
【０１５３】
サーバコンピュータ610は、分割パラメタ初期値生成手段121と、マッチング表生成手段103と、分割評価手段11と、分割パラメタ更新手段123とを備えている。
【０１５４】
サーバコンピュータ610と移動体620とは、ネットワーク630を介して、データの通信を行うように構成されている。
【０１５５】
本実施例１では、移動体620からのマッチング処理の要求に応答して、処理がなるべく高速に、かつ、記憶容量が少なくなるようなマッチング表を選択するものとする。また、移動体620の位置情報から、移動体620をほぼ中心とする所定の範囲の配置図を選択するそして、その配置図は1つの頂点を原点(0、0)とする直行座標系が導入されており、配置図の表す領域には、図１５に示すように5つの対象オブジェクトが分布しているものとする。この配置図において、対象オブジェクトを半径10の円板で近似し、円板の中心の座標で表現するとする。
【０１５６】
配置記憶手段100において、対象オブジェクトの配置情報は図１６に示すように記憶されている。本実施例では、座標(0、0)を起点として、対象オブジェクトが配置された配置図の領域を正方形の格子で分割し、分割パラメタは格子サイズとする。
【０１５７】
格子分割の制約は格子サイズとし、最大格子サイズと最小格子サイズとの間で制約を受けるものとする。また、格子分割の終了条件はステップS311からステップS333までの繰り返しにおける格子サイズの差分が予め設定されている最小値となった場合とする。そして、本実施例１では、制約記憶手段101には、図１７に示すように、最大格子サイズLmax=500、最小格子サイズLmin=100、格子サイズの差分の最小値Δmin=50が記憶されているものとする。
【０１５８】
本実施例１において、評価関数は、マッチング表中に対象オブジェクトが1つ存在する格子数／マッチング表中の全格子数とする。そして、評価関数が最大であるマッチング表が移動体620のマッチング処理に適したものとする。以下、格子サイズLに対する評価関数値をF(L)とおく。
【０１５９】
本実施例１では、格子サイズを2分法により求めるものとし、分割パラメタの初期値は最大格子サイズ、最小格子サイズ、最大格子サイズと最小格子サイズの中央値とする。
【０１６０】
まず、分割パラメタ初期値生成手段121は制約記憶手段101から制約条件として、Lmax=500、Lmin=100、Δmin=50を読み込む(ステップS301)。
【０１６１】
次に、分割パラメタの初期値として、最大格子サイズLmax、最小格子サイズLminの中央値を計算し、(500+100)/2=300を得る。
【０１６２】
その結果、分割パラメタの初期値として格子サイズ(100、300、500)を生成し(ステップS302)、分割パラメタ記憶手段122に記憶する(ステップS303)。
【０１６３】
マッチング表生成手段103は、格子サイズのリストと、図16に示す配置図情報を取得する(ステップS311)。
【０１６４】
格子サイズのリストと配置図情報を取得した後、マッチング表生成手段103は配置図を分割する(ステップS312)。ステップS312により、マッチング表生成手段103は図１８に示すマッチング表を得る。
【０１６５】
図１８(a)は格子サイズ500で格子分割したマッチング表、図１８(b)は格子サイズ100で格子分割したマッチング表、図１８(c)は格子サイズ300で格子分割したマッチング表である。
【０１６６】
マッチング表生成手段103は、生成したマッチング表をマッチング表記憶手段12に格納する(ステップS313)。
【０１６７】
分割評価手段11は、図１８のマッチング表に対し、評価関数値を計算する(ステップS321)。
【０１６８】
図１８(a)には対象オブジェクト数が1である格子が0個存在し（中央の対象オブジェクトが各格子に属するので、各格子の対象オブジェクト数は２である）、格子数は4なので、評価関数値F(500)=0/4=0.0000である。図１８(b)には対象オブジェクト数が1である格子が8個存在し（中央の対象オブジェクトが属する格子数は4である）、格子数は100なので、評価関数値F(100)=8/100=0.0800である。図１８(b)には対象オブジェクト数が1である格子が5個存在し、格子数は16なので、評価関数値F(300)=5/16=0.3125である。
【０１６９】
分割パラメタの生成は1回目なので、終了しない(ステップS331)。
【０１７０】
次に格子分割する格子サイズとして、(100+300)/2=200とする(ステップS332)。
【０１７１】
格子サイズ200を分割パラメタ記憶手段122に格納する(ステップS333)。
【０１７２】
ステップS311〜S333までの1回目の処理の後、第2回目のマッチング表の生成、評価を行う。
【０１７３】
格子サイズ(200、300、500)によるマッチング表を生成し、マッチング表記憶手段12に格納する(ステップS311〜S313)。
【０１７４】
次に、格子サイズ(200、300、500)のマッチング表に対し、評価関数Fの値を求める。
【０１７５】
格子サイズ200で配置図を分割すると、図１９に示すように、対象オブジェクト数が1である格子は5個存在し、格子数は25なので、評価関数値F(200)=5/25=0.200である(ステップS321)。
【０１７６】
格子サイズの差は|300-200|=100>50（=Δmin）なので、終了しない(ステップS331)。
【０１７７】
F(500)<F(200)<F(300)なので、次に格子分割する分割サイズとして、(300+500)/2=400とし、分割パラメタ記憶手段122に格納する(ステップS332〜S333)。
【０１７８】
3回目のマッチング表の生成、評価を行う。
【０１７９】
格子サイズ(300、400、500)によりマッチング表を生成し、マッチング表記憶手段12に格納する(ステップS311〜S313)。
【０１８０】
新たに生成したマッチング表に対し、評価関数値を求める。格子サイズ400で配置図を分割すると、図２０に示すように、対象オブジェクト数が1である格子は3個存在し、格子数は9なので、F(400)=3/9=0.3333である(ステップS321)。
【０１８１】
格子サイズの差は|300-400|=100>50（=Δmin）なので、終了しない(ステップS331)。
【０１８２】
F(500)<F(300)<F(400)なので、次に格子分割する分割サイズとして、(400+300)/2=350とし、分割パラメタ記憶手段122に格納する(ステップS332〜S333)。
【０１８３】
4回目のマッチング表の生成、評価を行う。
【０１８４】
格子サイズ(300、350、400)によりマッチング表を生成し、マッチング表記憶手段12に格納する(ステップS311〜S313)。
【０１８５】
新たに生成したマッチング表に対し、評価関数値を求める。
【０１８６】
格子サイズ350で配置図を分割すると、図２１に示すように、対象オブジェクト数が1である格子は5個存在し、格子数は9なので、F(350)=5/9=0.5556である(ステップS321)。
【０１８７】
格子サイズの差は|400-350|=50（=Δmin）なので、終了する(ステップS331)。
【０１８８】
このようにして、評価関数が最大である格子サイズ350のマッチング表を得る。
【０１８９】
上述した実施の形態及び実施例において説明した、分割評価手段１１、分割パラメタ生成手段１０２、マッチング表生成手段１０３、分割パラメタ初期値生成手段１２１、分割パラメタ更新手段１２３は、プログラムによって動作するコンピュータによっても実現できる。
【０１９０】
以上好ましい実施の形態及び実施例をあげて本発明を説明したが、本発明は必ずしも上記実施の形態及び実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形し実施することが出来る。
【産業上の利用可能性】
【０１９１】
本発明は、大量の移動体の位置情報を象オブジェクトに対応付ける処理を行う用途に好適に適用できる。
【図面の簡単な説明】
【０１９２】
【図１】図１はマッチング表のデータ構造の例を示す説明図である。
【図２】図２はマッチング表の例を模式的に示す説明図である。
【図３】図３は第１の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【図４】図４は配置記憶手段100が記憶する配置図情報の一例を示す説明図である。
【図５】図５は制約記憶手段101に記憶されている格子分割の制約条件の一例を示した図である。
【図６】図６は第１の実施の形態におけるマッチング表評価システムの動作を示すフローチャートである。
【図７】図７は分割パラメタと評価関数との関係のグラフの一例を示す説明図である。
【図８】図８は第２の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【図９】図９は第２の実施の形態のマッチング表評価システムの動作を示すプローチャートである。
【図１０】図１０は配置図情報の一例を模式的に示す説明図である。
【図１１】図１１はマッチング表生成手段による格子分割の一例を示す説明図である。
【図１２】図１２は評価関数値の計算を模式的に示す説明図である。
【図１３】図１３は、第３の実施の形態におけるマッチング表評価システムの構成を示すブロック図である。
【図１４】図１４は第３の実施の形態のマッチング表評価システムの動作を示すフローチャートである。
【図１５】図１５は実施例１における配置図情報を示す説明図である。
【図１６】図１６は実施例１における配置記憶手段100が記憶する配置図を示す説明図である。
【図１７】図１７は実施例１における制約記憶手段101が記憶する制約を示す説明図である。
【図１８】図１８は実施例１における配置図の1回目の格子分割を模式的に示す説明図である。
【図１９】図１９は実施例１における配置図の2回目の格子分割を模式的に示す説明図である。
【図２０】図２０は実施例１における配置図の3回目の格子分割を模式的に示す説明図である。
【図２１】図２１は実施例１における配置図の4回目の格子分割を模式的に示す説明図である。
【図２２】図２２は実施例１の構成を示すブロック図である。
【符号の説明】
【０１９３】
１１ 分割評価手段
１２ マッチング表記憶手段
１３ マッチング表候補記憶手段
１００ 配置記憶手段
１０１ 制約記憶手段
１０２ 分割パラメタ生成手段
１０３ マッチング表生成手段
１２１ 分割パラメタ初期値生成手段
１２２ 分割パラメタ記憶手段
１２３ 分割パラメタ更新手段
１３０ 分割パラメタ生成手段
【特許請求の範囲】
【請求項１】
対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価する分割評価手段を有するマッチング表評価システム。
【請求項２】
配置図の格子分割における分割パラメタを生成する分割パラメタ生成手段と、
前記分割パラメタに基づいて、配置図を格子領域に分割し、マッチング表を生成するマッチング表生成手段とを有し、
前記分割評価手段は、前記評価関数に基づいて、前記生成されたマッチング表を評価し、予め定められた条件を満たすか否かを判断し、条件を満たさない場合には前記分割パラメタ生成手段に分割パラメタを更新させ、
前記分割パラメタ生成手段は、前記分割評価手段の指示により、新たな分割パラメタを生成する
請求項１に記載のマッチング表評価システム。
【請求項３】
少なくとも一以上の、配置図の格子分割における分割パラメタを生成する分割パラメタ生成手段と、
前記少なくとも一以上の分割パラメタに基づいて、配置図を格子領域に分割し、少なくとも一以上のマッチング表を生成するマッチング表生成手段とを有し、
前記分割評価手段は、前記評価関数に基づいて、前記生成された少なくとも一以上のマッチング表を評価し、マッチング表を選択する
請求項１に記載のマッチング表評価システム。
【請求項４】
少なくとも一以上のマッチング表が記憶された記憶手段と、
前記評価関数に基づいて、前記少なくとも一以上のマッチング表を評価し、マッチング表を選択する
請求項１に記載のマッチング表評価システム。
【請求項５】
対象オブジェクトの配置図の情報が記憶された配置記憶手段と、
格子分割の制約条件が記憶された制約記憶手段とを有し、
前記分割パラメタ生成手段は、前記制約条件に基づいて分割パラメタを生成し、
前記マッチング表生成手段は、対象オブジェクトの配置図の情報及び前記分割パラメタに基づいて、配置図を格子領域に分割し、マッチング表を生成する
請求項２又は請求項３のマッチング表評価システム。
【請求項６】
前記分割評価手段は、マッチング表が持つ全格子の数に対する対象オブジェクトが1つである格子の数の割合を評価関数とし、前記評価関数値が最大のマッチング表を適切なものとして評価する
請求項１から請求項５のいずれかに記載のマッチング表評価システム。
【請求項７】
前記分割評価手段は、
マッチング表に対して、対象オブジェクトが存在する格子における対象オブジェクト数の平均と、前記マッチング表の格子の1辺の長さとの組を評価関数とし、
前記対象オブジェクトが存在する格子における対象オブジェクト数の平均が最も小さく、前記平均が等しい場合には、前記マッチング表の格子の1辺の長さが大きい、評価関数に対応するマッチング表を適切なものとして評価する
請求項１から請求項５のいずれかに記載のマッチング表評価システム。
【請求項８】
対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価するマッチング表評価方法。
【請求項９】
配置図の格子分割における分割パラメタを生成し、
前記分割パラメタに基づいて、配置図を格子領域に分割し、マッチング表を生成し、
前記評価関数に基づいて、前記生成されたマッチング表を評価し、予め定められた条件を満たすか否かを判断し、
条件を満たさない場合には、分割パラメタを更新し、新たなマッチング表を生成して評価し、マッチング表の評価が条件を満たすまで行う
請求項８に記載のマッチング表評価方法。
【請求項１０】
少なくとも一以上の、配置図の格子分割における分割パラメタを生成し、
前記少なくとも一以上の分割パラメタに基づいて、配置図を格子領域に分割し、少なくとも一以上のマッチング表を生成し、
前記評価関数に基づいて、前記生成された少なくとも一以上のマッチング表を評価し、マッチング表を選択する
請求項８に記載のマッチング表評価方法。
【請求項１１】
前記評価関数に基づいて、予め用意された少なくとも一以上のマッチング表を評価し、マッチング表を選択する
請求項８に記載のマッチング表評価方法。
【請求項１２】
前記評価関数は、マッチング表が持つ全格子の数に対する対象オブジェクトが1つである格子の数の割合であり、前記評価関数値が最大のマッチング表を適切なものとして評価する
請求項８から請求項１１のいずれかに記載のマッチング表評価方法。
【請求項１３】
前記評価関数は、マッチング表に対して、対象オブジェクトが存在する格子における対象オブジェクト数の平均と、前記マッチング表の格子の1辺の長さとの組であり、
前記対象オブジェクトが存在する格子における対象オブジェクト数の平均が最も小さく、前記平均が等しい場合には、前記マッチング表の格子の1辺の長さが大きい、評価関数に対応するマッチング表を適切なものとして評価する
請求項８から請求項１１のいずれかに記載のマッチング表評価方法。
【請求項１４】
対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価するマッチング表評価処理を情報処理装置に実行させるプログラム。
【請求項１５】
前記マッチング表評価処理は、
配置図の格子分割における分割パラメタを生成する分割パラメタ生成処理と、
前記分割パラメタに基づいて、配置図を格子領域に分割し、マッチング表を生成するマッチング表生成処理と、
前記評価関数に基づいて、前記生成されたマッチング表を評価し、予め定められた条件を満たすか否かを判断する評価処理と、
条件を満たすまで、分割パラメタ生成処理、マッチング表生成処理及び評価処理を繰り返す処理と
を有する請求項１４に記載のプログラム。
【請求項１６】
前記マッチング表評価処理は、
少なくとも一以上の、配置図の格子分割における分割パラメタを生成する処理と、
前記少なくとも一以上の分割パラメタに基づいて、配置図を格子領域に分割し、少なくとも一以上のマッチング表を生成する処理と、
前記評価関数に基づいて、前記生成された少なくとも一以上のマッチング表を評価し、マッチング表を選択する処理と
を有する請求項１４に記載のプログラム。
【請求項１７】
前記マッチング表評価処理は、前記評価関数に基づいて、予め用意された少なくとも一以上のマッチング表を評価し、マッチング表を選択する処理である請求項１４に記載のプログラム。
【請求項１８】
前記評価関数は、マッチング表が持つ全格子の数に対する対象オブジェクトが1つである格子の数の割合であり、
前記マッチング表評価処理は、前記評価関数値が最大のマッチング表を適切なものとして評価する処理である
請求項１４から請求項１７のいずれかに記載のプログラム。
【請求項１９】
前記評価関数は、マッチング表に対して、対象オブジェクトが存在する格子における対象オブジェクト数の平均と、前記マッチング表の格子の1辺の長さとの組であり、
前記マッチング表評価処理は、前記対象オブジェクトが存在する格子における対象オブジェクト数の平均が最も小さく、前記平均が等しい場合には、前記マッチング表の格子の1辺の長さが大きい、評価関数に対応するマッチング表を適切なものとして評価する処理である
請求項１４から請求項１７のいずれかに記載のプログラム。
【請求項１】
対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価する分割評価手段を有するマッチング表評価システム。
【請求項２】
配置図の格子分割における分割パラメタを生成する分割パラメタ生成手段と、
前記分割パラメタに基づいて、配置図を格子領域に分割し、マッチング表を生成するマッチング表生成手段とを有し、
前記分割評価手段は、前記評価関数に基づいて、前記生成されたマッチング表を評価し、予め定められた条件を満たすか否かを判断し、条件を満たさない場合には前記分割パラメタ生成手段に分割パラメタを更新させ、
前記分割パラメタ生成手段は、前記分割評価手段の指示により、新たな分割パラメタを生成する
請求項１に記載のマッチング表評価システム。
【請求項３】
少なくとも一以上の、配置図の格子分割における分割パラメタを生成する分割パラメタ生成手段と、
前記少なくとも一以上の分割パラメタに基づいて、配置図を格子領域に分割し、少なくとも一以上のマッチング表を生成するマッチング表生成手段とを有し、
前記分割評価手段は、前記評価関数に基づいて、前記生成された少なくとも一以上のマッチング表を評価し、マッチング表を選択する
請求項１に記載のマッチング表評価システム。
【請求項４】
少なくとも一以上のマッチング表が記憶された記憶手段と、
前記評価関数に基づいて、前記少なくとも一以上のマッチング表を評価し、マッチング表を選択する
請求項１に記載のマッチング表評価システム。
【請求項５】
対象オブジェクトの配置図の情報が記憶された配置記憶手段と、
格子分割の制約条件が記憶された制約記憶手段とを有し、
前記分割パラメタ生成手段は、前記制約条件に基づいて分割パラメタを生成し、
前記マッチング表生成手段は、対象オブジェクトの配置図の情報及び前記分割パラメタに基づいて、配置図を格子領域に分割し、マッチング表を生成する
請求項２又は請求項３のマッチング表評価システム。
【請求項６】
前記分割評価手段は、マッチング表が持つ全格子の数に対する対象オブジェクトが1つである格子の数の割合を評価関数とし、前記評価関数値が最大のマッチング表を適切なものとして評価する
請求項１から請求項５のいずれかに記載のマッチング表評価システム。
【請求項７】
前記分割評価手段は、
マッチング表に対して、対象オブジェクトが存在する格子における対象オブジェクト数の平均と、前記マッチング表の格子の1辺の長さとの組を評価関数とし、
前記対象オブジェクトが存在する格子における対象オブジェクト数の平均が最も小さく、前記平均が等しい場合には、前記マッチング表の格子の1辺の長さが大きい、評価関数に対応するマッチング表を適切なものとして評価する
請求項１から請求項５のいずれかに記載のマッチング表評価システム。
【請求項８】
対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価するマッチング表評価方法。
【請求項９】
配置図の格子分割における分割パラメタを生成し、
前記分割パラメタに基づいて、配置図を格子領域に分割し、マッチング表を生成し、
前記評価関数に基づいて、前記生成されたマッチング表を評価し、予め定められた条件を満たすか否かを判断し、
条件を満たさない場合には、分割パラメタを更新し、新たなマッチング表を生成して評価し、マッチング表の評価が条件を満たすまで行う
請求項８に記載のマッチング表評価方法。
【請求項１０】
少なくとも一以上の、配置図の格子分割における分割パラメタを生成し、
前記少なくとも一以上の分割パラメタに基づいて、配置図を格子領域に分割し、少なくとも一以上のマッチング表を生成し、
前記評価関数に基づいて、前記生成された少なくとも一以上のマッチング表を評価し、マッチング表を選択する
請求項８に記載のマッチング表評価方法。
【請求項１１】
前記評価関数に基づいて、予め用意された少なくとも一以上のマッチング表を評価し、マッチング表を選択する
請求項８に記載のマッチング表評価方法。
【請求項１２】
前記評価関数は、マッチング表が持つ全格子の数に対する対象オブジェクトが1つである格子の数の割合であり、前記評価関数値が最大のマッチング表を適切なものとして評価する
請求項８から請求項１１のいずれかに記載のマッチング表評価方法。
【請求項１３】
前記評価関数は、マッチング表に対して、対象オブジェクトが存在する格子における対象オブジェクト数の平均と、前記マッチング表の格子の1辺の長さとの組であり、
前記対象オブジェクトが存在する格子における対象オブジェクト数の平均が最も小さく、前記平均が等しい場合には、前記マッチング表の格子の1辺の長さが大きい、評価関数に対応するマッチング表を適切なものとして評価する
請求項８から請求項１１のいずれかに記載のマッチング表評価方法。
【請求項１４】
対象オブジェクトの位置的な分布を考慮した評価関数に基づいて、マッチング表を評価するマッチング表評価処理を情報処理装置に実行させるプログラム。
【請求項１５】
前記マッチング表評価処理は、
配置図の格子分割における分割パラメタを生成する分割パラメタ生成処理と、
前記分割パラメタに基づいて、配置図を格子領域に分割し、マッチング表を生成するマッチング表生成処理と、
前記評価関数に基づいて、前記生成されたマッチング表を評価し、予め定められた条件を満たすか否かを判断する評価処理と、
条件を満たすまで、分割パラメタ生成処理、マッチング表生成処理及び評価処理を繰り返す処理と
を有する請求項１４に記載のプログラム。
【請求項１６】
前記マッチング表評価処理は、
少なくとも一以上の、配置図の格子分割における分割パラメタを生成する処理と、
前記少なくとも一以上の分割パラメタに基づいて、配置図を格子領域に分割し、少なくとも一以上のマッチング表を生成する処理と、
前記評価関数に基づいて、前記生成された少なくとも一以上のマッチング表を評価し、マッチング表を選択する処理と
を有する請求項１４に記載のプログラム。
【請求項１７】
前記マッチング表評価処理は、前記評価関数に基づいて、予め用意された少なくとも一以上のマッチング表を評価し、マッチング表を選択する処理である請求項１４に記載のプログラム。
【請求項１８】
前記評価関数は、マッチング表が持つ全格子の数に対する対象オブジェクトが1つである格子の数の割合であり、
前記マッチング表評価処理は、前記評価関数値が最大のマッチング表を適切なものとして評価する処理である
請求項１４から請求項１７のいずれかに記載のプログラム。
【請求項１９】
前記評価関数は、マッチング表に対して、対象オブジェクトが存在する格子における対象オブジェクト数の平均と、前記マッチング表の格子の1辺の長さとの組であり、
前記マッチング表評価処理は、前記対象オブジェクトが存在する格子における対象オブジェクト数の平均が最も小さく、前記平均が等しい場合には、前記マッチング表の格子の1辺の長さが大きい、評価関数に対応するマッチング表を適切なものとして評価する処理である
請求項１４から請求項１７のいずれかに記載のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１０−１２２１３１（Ｐ２０１０−１２２１３１Ａ）
【公開日】平成２２年６月３日（２０１０．６．３）
【国際特許分類】
【出願番号】特願２００８−２９７５３６（Ｐ２００８−２９７５３６）
【出願日】平成２０年１１月２１日（２００８．１１．２１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２２年６月３日（２０１０．６．３）
【国際特許分類】
【出願日】平成２０年１１月２１日（２００８．１１．２１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]