情報処理装置、その処理方法及びプログラム
【課題】地理情報検索を行なう際の処理負荷を軽減する技術を提供する。
【解決手段】地図データ保持手段と、地図データ上で検索対象となる地点を示す着目地点の地理コードを取得する着目地点取得手段と、地図データ上で検索を行なう範囲を示す検索対象領域を覆うメッシュ群のうち、着目地点を示す地理コードの文字列と一致する地理コードの文字列を有する１又は複数のメッシュを検索結果の候補として取得する候補取得手段と、検索結果の候補として取得された１又は複数のメッシュのうち、検索対象領域に完全に内包されていないメッシュに対して着目地点を内包しているか否かを判定し、当該着目地点が内包されていない１又は複数のメッシュをメッシュ群から除外する除外手段と、検索結果の候補から除外が行なわれた後の１又は複数のメッシュを検索結果として出力する出力手段とを具備する。
【解決手段】地図データ保持手段と、地図データ上で検索対象となる地点を示す着目地点の地理コードを取得する着目地点取得手段と、地図データ上で検索を行なう範囲を示す検索対象領域を覆うメッシュ群のうち、着目地点を示す地理コードの文字列と一致する地理コードの文字列を有する１又は複数のメッシュを検索結果の候補として取得する候補取得手段と、検索結果の候補として取得された１又は複数のメッシュのうち、検索対象領域に完全に内包されていないメッシュに対して着目地点を内包しているか否かを判定し、当該着目地点が内包されていない１又は複数のメッシュをメッシュ群から除外する除外手段と、検索結果の候補から除外が行なわれた後の１又は複数のメッシュを検索結果として出力する出力手段とを具備する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、その処理方法及びプログラムに関する。
【背景技術】
【０００２】
近年、ストレージや記録メディアの大容量化が進み、比較的小規模な機器においても、大量に蓄積されたデータが扱われており、検索機能が必須となりつつある。
【０００３】
例えば、カメラにおいて撮影写真等が格納されるフラッシュメディアでは、現在、容量６４ＧＢのＳＤＸＣ規格のカードが市販されており、１枚１ＭＢの写真が６万枚以上格納されることになる。ＳＤＸＣの規格上は２ＴＢまで拡張可能である。
【０００４】
大量の写真から目的の写真を取得するには、従来のような撮影順の閲覧機能だけでは不十分であり、様々な観点から写真を検索できることが必要となる。その検索の方法の１つとしてメタデータ検索がある。例えば、写真に撮影場所の住所やランドマークのメタデータが付与されていれば、住所やランドマークの情報から写真を検索できる。そのためには、写真にメタデータを付与する機能が必要となる。
【０００５】
近年、カメラにＧＰＳ機能が搭載されるようになってきており、撮影場所の緯度・経度が分かる地理情報を写真に付与できるようになってきている。住所やランドマークの示す地理領域の辞書をカメラに内蔵し、緯度・経度情報に基づいて撮影地点を内包する地理領域を検索する地理情報検索が必要となってきている。
【０００６】
地理情報検索には、指定した範囲内に内包される地点のデータを検索する範囲指定検索、指定した位置に空間的に近い地点のデータを近い順にｋ個検索するｋ最近傍検索などがある。
【０００７】
範囲指定検索は、従来から多くの実現方法が存在している。有名な方法としては、Ｒ−ｔｒｅｅがある。Ｒ−ｔｒｅｅは、空間的に近傍にある領域を複数まとめて最小外接矩形（MBR：Minimum Bounding Rectangle）を求め、それをインデクスに保持することによって高速に検索を行なう方法である。領域のまとまりが多数あれば、それらを更に複数まとめたまとまりを作って、インデクスを階層化していく。
【０００８】
また、ｋ最近傍検索も多くの実現方法が存在している。特許文献１には、指定された地点から近傍する所定数の地点を検索する技術について言及されている。より具体的には、指定地点を含む小領域及びその小領域と隣接する小領域を検索対象小領域群として当該小領域群に含まれる地点と指定地点との距離を一つずつ計算し、最も近い地点から所定数の検索結果を得る。
【０００９】
その他、緯度・経度座標を文字列に符号化する方法も提案されている（特許文献２参照）。この手法では、緯度・経度の座標値（浮動小数点数）から整数、整数から文字列、緯度と経度との両方からそれぞれ変換された文字列を連接して符号化している。また、別の提案では、整数化された緯度及び経度の情報を１ビットずつ交互に組み合わせて文字列に符号化する方式や、この符号化方式を利用して指定領域内にある地点を検索する方法も提案されている。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００３−２４２１５１号公報
【特許文献２】米国特許出願公開第２００５／００２３５２４号
【発明の概要】
【発明が解決しようとする課題】
【００１１】
Ｒ−ｔｒｅｅ方式は、文字列検索用のインデクスとは異なる専用のインデクス機構を保持し制御する方式であり、特に、処理能力の低い装置（例えば、組み込み機器）にとっては処理負担が大きくなってしまう。
【００１２】
また、特許文献１に開示された手法では、指定地点に近い地点を検索することしかできない、そのため、住所やランドマークを付与するような、指定地点が不定形の領域に内包されている地点の検索を行なうことはできない。
【００１３】
本発明は、上記課題に鑑みてなされたものであり、地理情報検索を行なう際の処理負荷を軽減するようにした技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するため、本発明の一態様による情報処理装置は、地表が階層的にメッシュで区分されるとともに、該メッシュ各々の位置を示す地理コードが文字列で表現され、上位メッシュを表現する地理コードに文字を追加することで下位メッシュの地理コードを示す地理コード体系を有する地図データを保持する保持手段と、前記地図データ上で検索対象となる地点を示す着目地点の地理コードを取得する着目地点取得手段と、前記地図データ上で検索を行なう範囲を示す検索対象領域を覆うメッシュ群のうち、前記着目地点を示す地理コードの文字列と一致する地理コードの文字列を有する１又は複数のメッシュを検索結果の候補として取得する候補取得手段と、前記検索結果の候補として取得された１又は複数のメッシュのうち、前記検索対象領域に完全に内包されていないメッシュに対して前記着目地点を内包しているか否かを判定し、当該着目地点が内包されていない１又は複数のメッシュを前記メッシュ群から除外する除外手段と、前記検索結果の候補から前記除外が行なわれた後の１又は複数のメッシュを検索結果として出力する出力手段とを具備する。
【発明の効果】
【００１５】
本発明によれば、地理情報検索を行なう際の処理負荷を軽減することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施の形態に係る情報処理装置１０の構成の一例を示す図。
【図２】地理情報検索を行なう際の処理の概要を示す図。
【図３】本実施形態に係る地図データの一例を示す図。
【図４】検索対象領域を覆うメッシュの一例を示す図。
【図５】テーブル４１〜４３の構成の一例を示す図。
【図６】図１に示す情報処理装置１０の処理の流れの一例を示すフローチャート。
【図７】図６のＳ１０４に示す領域検索処理の流れの一例を示すフローチャート。
【図８】図６のＳ１０５に示す領域登録処理の流れの一例を示すフローチャート。
【図９】変形例の一例を示す図。
【発明を実施するための形態】
【００１７】
以下、本発明に係る実施の形態について添付図面を参照して詳細に説明する。
【００１８】
図１は、本発明の一実施の形態に係る情報処理装置１０の構成の一例を示す図である。
【００１９】
情報処理装置１０は、ＣＰＵ１１と、入力部１２と、出力部１３と、撮像部１４と、通信部１５と、バス１６と、ＲＯＭ１７と、ＲＡＭ１８と、外部記憶媒体１９とが具備して構成される。
【００２０】
ＣＰＵ（Central Processing Unit）１１は、例えば、ＲＯＭ１７に格納されたプログラムに従って、情報処理装置１０における処理を統括制御する。ＣＰＵ１１においては、例えば、検索処理、領域登録処理、画面制御処理、写真撮影処理等のための演算、論理判断等を行ない、バス１６を介してバスに接続された各デバイスを制御する。
【００２１】
バス１６は、アドレス信号やコントロール信号等を転送する。また、各デバイス間のデータ転送も行なう。
【００２２】
入力部１２は、例えば、ボタンやタッチパネル等で実現され、ユーザからの各種指示を装置内に入力する。出力部１３は、液晶ディスプレイ等で実現され、ユーザに向けて各種情報を出力（表示）する。なお、出力部１３による出力は、例えば、印刷により実現されても良いし、音声により実現されても良い。
【００２３】
撮像部１４は、例えば、撮像センサ等で実現され、映像を読み取って電子データに変換する。通信部１５は、例えば、ネットワークコントローラ等で実現され、有線又は無線の通信路を介して外部装置との間でデータ交換を行なう。
【００２４】
ＲＯＭ（Read Only Memory）１７は、不揮発性メモリである。ＣＰＵ１１により実行される各種プログラム（ブートプログラム２１、システムの制御プログラム２２）等の他、各種処理で参照される各種初期データ２３、地図データ２４等が格納される。
【００２５】
ＲＡＭ（Random Access Memory）１８は、読み書き可能なメモリである。ＲＡＭ１８は、各デバイスからの各種データの一次記憶に用いられる。ＲＡＭ１８には、各種ワーク領域３１の他、スタック３２等が格納される。
【００２６】
外部記憶媒体１９は、例えば、ＳＤカード、ＣＦカード等のフラッシュメディアで実現される。外部記憶媒体１９は、ブロック単位で一括消去可能な大容量の不揮発性メモリであり、大量のデータを変更可能に記憶する。なお、外部記憶媒体１９は、上述したカード等に限られず、ハードディスク等で代用することもできる。外部記憶媒体１９には、メッシュテーブル４１、詳細インデクステーブル４２、領域テーブル４３等が格納され、必要に応じて随時内容が修正される。
【００２７】
ここで、ＣＰＵ１１には、その機能的な構成として、☆と、☆とが実現される。なお、これら構成は、例えば、ＣＰＵ１１がＲＯＭ１７等に格納されたプログラムを実行することにより実現される。
【００２８】
領域登録部５０は、検索対象となる領域（検索対象領域）を登録する。検索対象領域は、例えば、入力部１２を介したユーザの指示により指定される。
【００２９】
着目地点取得部５１は、着目地点（のメッシュコード）を取得する。着目地点は、検索対象となる地図データ上の地点を示す。なお、詳細については後述するが、本実施形態に係わる地図データは、地表が階層的にメッシュで区分される。また、メッシュ各々の位置を示す地理コードが文字列で表現される。下位メッシュは、上位メッシュを表現する地理コードに文字が追加されることで表現される。
【００３０】
検索部５２は、着目地点を示す地理コードの文字列と、検索対象領域を覆うメッシュ群の地理コードの文字列とを比較し、所定のメッシュの検索を行なう機能を果たし、候補取得部６１と、除外部６２とを具備して構成される。候補取得部６１は、検索対象領域を覆うメッシュ群の中から着目地点を内包する１又は複数のメッシュを検索結果の候補として取得する。除外部６２は、メッシュの検索結果の候補の中から、所定の条件に従っていずれかのメッシュを除外する。
【００３１】
以上が、情報処理装置１０における機能的な構成についての説明である。なお、本実施形態においては、情報処理装置１０が撮像部１４を有する撮像装置（例えば、デジタルカメラやデジタルビデオカメラ）等に適用される場合について説明するが、これに限られない。情報処理装置１０は、例えば、通信装置や画像表示装置等の種々の装置に組み込み装置として適用されても良い。
【００３２】
また、上述した説明では、ＣＰＵ１１がプログラムを実行することで各種処理が実行される場合について説明したが、これに限られず、例えば、ＣＰＵと協調して動作するＡＳＩＣなどの制御回路が各種処理を実行しても良い。また、ＣＰＵと制御回路との協調動作によって各種処理が実行されてもよい。また、ＣＰＵは単一である必要はなく、複数であっても良い。この場合、複数のＣＰＵは分散して処理を実行する。また、複数のＣＰＵは単一のコンピュータに配置されていても良いし、物理的に異なる複数のコンピュータに配置されていても良い。なお、ＣＰＵがプログラムを実行することで実現される処理が専用の回路によって実現されても良い。
【００３３】
次に、図２を用いて、地点を含む領域を検索する地理情報検索を行なう際の処理の概要について説明する。
【００３４】
ここで、着目地点２０１を含む領域を検索する場合について説明する。この場合、着目地点２０１を内包する検索対象領域２０３及び２０６が検索の結果としてヒットする。これに対し、検索対象領域２０２、２０４及び２０５は、着目地点２０１を内包しないためヒットしない。
【００３５】
ここで、領域２０３及び領域２０４の関係に着目してみる。すなわち、領域２０３の中心が領域２０４の中心より遠いにもかかわらず、遠い方の領域２０３がヒットして、近い方の領域２０４がヒットしていないことに注意が必要である。このような検索は、写真に地名のメタデータを付与した場合などには必須である。例えば、「広尾」付近で撮影した写真には、中心地が近い「六本木」は付与されないが、中心地が遠い広域地名の「東京都」は付与される場合がある。
【００３６】
次に、図３（ａ）及び図３（ｂ）を用いて、本実施形態に係る地図データについて説明する。本実施形態においては、地図データは、地表を階層的なメッシュで区分し、緯度・経度情報に基づいてメッシュの位置を地理コードで表現する地理コード体系を有する。地理コードは文字列で表現される。
【００３７】
まず、図３（ａ）を用いて、緯度・経度情報を地理コードに変換する処理の一例について説明する。
【００３８】
緯度・経路情報を地理コードに変換する際には、まず、地表を緯度又は経度の方向に沿って２分割していき、分割の度に当該分割された地表に０又は１のビットを割り当てる。緯度及び経度のそれぞれに対して、そのビットを大分割から順番に並べてビット列を作成し、当該ビット列をメッシュの緯度情報３０１及び経度情報３０２とする。このように生成されたビット列に対して、経度、緯度の順番で先頭から交互に１ビットずつ選択していき、ビット列３０３を生成する。ビット列３０３を先頭から５ビットずつに分割し、変換表３０４に従って５ビット単位に当該ビット列を文字コードに変換する。これにより、地理コード３０５が得られる。
【００３９】
各メッシュは、地表の分割回数に応じて階層的に詳細化されたものになる。詳細化されたメッシュほど、緯度・経度情報のビット数が多くなり、変換後の文字列の文字数も多くなる。そのため、文字数がメッシュの精度を表現することになるので、メッシュの精度を文字列の文字数と定義することができる。このようにして生成されたメッシュの地理コードをメッシュコードと呼ぶ。
【００４０】
次に、図３（ｂ）を用いて、メッシュが構成する階層構造の一例について説明する。
【００４１】
メッシュ３０６は“ｅ”が表現する精度＝１（すなわち、文字数＝１）のメッシュを示している。当該メッシュ３０６内の１文字を“ｅ”に付加することによって、下位メッシュに３２分割することができる。
【００４２】
次の１文字が“７”の場合は、精度＝２のメッシュ３０７になり、メッシュコードが“ｅ７”となる。メッシュ３０７を拡大して示したものがメッシュ３０８になる。この場合にも同様に、次の１文字を付加することによって下位メッシュに３２分割することができる。
【００４３】
次の１文字が“ｓ”の場合は、精度＝３のメッシュ３０９となり、メッシュコードは“ｅ７ｓ”となる。すなわち、メッシュコードの文字数に応じてメッシュが階層化されていることが分かる。メッシュコードの文字数が同じ階層に属しているか否かを示すことになる。
【００４４】
ここで、表３１０は、このように階層化されたメッシュが表現する地理領域の概略面積の一例を示している。表３１０によれば、精度＝３のメッシュは、１５６ｋｍ×１５６ｋｍの矩形領域を表現することが示されている。また、精度を大きくすれば、より詳細な地理領域が表現されることが分かる。例えば、精度１２のメッシュコードであれば、事実上、地図データ上の特定の地点を表現できることになる。本実施形態においては、地点を特定する場合、システム上最も詳細な精度のメッシュコードで表現する。
【００４５】
次に、図４を用いて、検索対象領域を覆うメッシュの一例について説明する。
【００４６】
ここで、符号４０１は、検索対象領域を指している。この領域４０１を覆うメッシュは、メッシュ１〜メッシュ１７として示されている。各メッシュは、異なる階層に属すこともある。例えば、メッシュ８は他のメッシュよりも面積が大きいが、これは、複数の下位メッシュが統合されて階層が１段階上がった上位メッシュとなっているからである。
【００４７】
ここで、黒丸で示す地点４０２を着目地点とした検索を行なった場合、領域４０１はヒット領域となる。バツ印で示す地点４０３を着目地点とした検索を行なった場合、領域４０１はヒット領域とならない。ここで、メッシュのうち、検索対象領域内に完全に内包されるメッシュ（例えば、符号４０４）を完全内包メッシュと呼び、検索対象領域に部分的に内包されるメッシュ（例えば、符号４０５）を部分内包メッシュと呼ぶ。
【００４８】
地点４０３が着目地点の場合、メッシュ群に基づいて検索対象領域４０１を検索すると、メッシュ６がヒットする。ところが、メッシュ６は、部分内包メッシュであり、地点４０３が領域４０１の外側にある。そのため、その後実施される詳細チェックにおいて、地点４０３は、領域４０１に内包されないことが判明し、メッシュ６は検索結果から除かれることになる。このような詳細チェックによって最終的に検索結果から外れるが、処理途中では検索結果の候補とされる検索結果を「偽検索結果」と呼ぶ。
【００４９】
次に、図５を用いて、メッシュテーブル４１、詳細インデクステーブル４２、領域テーブル４３の構成の一例について説明する。
【００５０】
メッシュテーブル４１は、検索対象領域を覆うメッシュ群を管理する。カラム５０２には、各メッシュのメッシュコードが保持される。カラム５０３には、検索対象領域のＩＤが保持される。このＩＤを用いて領域テーブル４３を参照することにより、領域の詳細な情報が入手される。カラム５０４には、各メッシュの領域を検索対象領域が完全に内包するか否かを示すフラグ（「完全フラグ」と呼ぶ）が保持される。完全に内包されるときには（「完全内包」と呼ぶ）、“１”が保持され、部分的に内包されるときには（「部分内包」と呼ぶ）、“０”が保持される。カラム５０５には、部分内包のメッシュを更に詳細化したメッシュ群を管理する詳細インデクステーブル４２へのリンクが保持される。すなわち、メッシュテーブル４１には、検索対象領域と、完全フラグと、詳細インデクステーブル４２へのリンクとが対応付けて管理されている。
【００５１】
領域テーブル４３は、検索対象領域の地理的範囲を管理する。なお、ここでは、領域が矩形で構成されるものとして説明する。カラム５０７には、検索対象領域のＩＤが保持される。カラム５０８には、検索対象領域の左上地点のメッシュコードが保持される。カラム５０９には、検索対象領域の右下地点のメッシュコードが保持される。
【００５２】
詳細インデクステーブル４２は、部分内包メッシュを下位階層のメッシュに細分化して詳細化したメッシュ群を管理する。カラム５１１には、詳細化されたメッシュのメッシュコードが保持される。カラム５１２には、そのメッシュに対応する検索対象領域のＩＤが保持される。
【００５３】
ここで、上述した処理についてフローチャートを用いて説明する。図６は、図１に示す情報処理装置１０における処理の流れの一例を示す図である。この処理は、例えば、ＣＰＵ１１が、ＲＯＭ１７に格納されたプログラムを読み出し実行することにより実現される。
【００５４】
この処理では、情報処理装置１０は、ＣＰＵ１１において、まず、システムの初期化処理が行なわれる（Ｓ１０１）。すなわち、各種パラメータの初期化や初期画面の表示等が行なわれる。
【００５５】
その後、情報処理装置１０は、ＣＰＵ１１において、タッチパネル等の入力部１２から何らかのイベントが発生するまで待機する（Ｓ１０２）。イベントが発生すると、情報処理装置１０は、ＣＰＵ１１において、このイベントを判別し、イベントの種類に応じて各種の処理に分岐する。
【００５６】
ここで、領域検索処理を示すイベントであれば（Ｓ１０３で領域検索）、情報処理装置１０は、当該イベントに従って領域検索処理を行なう（Ｓ１０４）。また、領域登録処理を示すイベントであれば（Ｓ１０３で領域登録）、情報処理装置１０は、当該イベントに従って領域登録処理を行なう（Ｓ１０５）。それ以外のイベントであれば（Ｓ１０３でその他イベント）、情報処理装置１０は、各種イベントに対応した処理を行なう（Ｓ１０６）。なお、他のイベントとしては、画面制御処理、写真撮影処理などが挙げられる。
【００５７】
その後、情報処理装置１０は、出力部１３において、各処理の処理結果等をユーザに出力する。例えば、検索結果の表示、エラーがあった場合のエラー表示、正常な処理が行なわれた場合の画面表示等が行なわれる。
【００５８】
次に、図７を用いて、図６のＳ１０４に示す領域検索処理の流れの一例について説明する。すなわち、検索対象領域内で着目地点を内包する地理領域（１又は複数のメッシュ）を検索する際の処理について説明する。
【００５９】
この処理が開始すると、情報処理装置１０は、まず、着目地点取得部５１において、着目地点の取得を行なう（Ｓ２０１）。すなわち、着目地点を示すメッシュコードを取得する。着目地点は、例えば、入力部１２を介したユーザの指示により指定される。
【００６０】
続いて、情報処理装置１０は、候補取得部６１において、Ｓ２０１の処理で取得したメッシュコードを検索文字列として検索結果の候補の取得を行なう（Ｓ２０２、Ｓ２０３）。すなわち、検索文字列の少なくとも一部（前方文字列）と一致するメッシュコードを持つメッシュをメッシュテーブル４１から検索して取得し、それを検索結果の候補とする。
【００６１】
情報処理装置１０は、除外部６２において、検索結果の候補として取得されたメッシュの完全フラグをチェックする。すなわち、各メッシュが、完全内包メッシュであるか、部分内包メッシュであるかを判定する。
【００６２】
判定の結果、完全内包メッシュであれば（Ｓ２０４でＹＥＳ）、情報処理装置１０は、Ｓ２０８の処理に進む。一方、部分内包メッシュであれば（Ｓ２０４でＮＯ）、情報処理装置１０は、除外部６２において、着目地点と検索対象領域との位置関係の詳細チェックを行なう（Ｓ２０５）。すなわち、Ｓ２０３の処理で取得されたメッシュに含まれる着目地点が、検索対象領域内であるか否かをチェックする。このチェックでは、まず、詳細インデクステーブル４２から該当のメッシュの下位階層のメッシュ群を取得し、当該メッシュ群のうち着目地点を含むメッシュを取得する。そして、当該メッシュが検索対象領域内に内包されるか否かを判定する。これにより、検索対象領域内に内包されていなければ、Ｓ２０３の処理で検索されたメッシュは、偽検索結果であると判定される。
【００６３】
詳細チェックの結果、着目地点を内包しない、すなわち、偽検索結果であった場合（Ｓ２０６でＹＥＳ）、情報処理装置１０は、除外部６２において、当該偽検索結果を除外した後（Ｓ２０７）、Ｓ２０８の処理に進む。すなわち、偽検索結果となったメッシュを除外する。
【００６４】
一方、偽検索結果でなければ（Ｓ２０６でＮＯ）、情報処理装置１０は、検索部５２において、検索文字列の末尾を１文字削除する（Ｓ２０８）。すなわち、着目地点のメッシュの階層を１段階広範な領域に引き上げる。これにより、着目地点のメッシュコードの前方文字列とメッシュコードとが一致する、より広範なメッシュをメッシュテーブル４１から取得できることになる。
【００６５】
情報処理装置１０は、検索部５２において、１文字削除の結果、検索文字列の長さが「０」になったか否かを判定する。文字列の長さが「０」でなければ（Ｓ２０９でＮＯ）、より広範なメッシュの前方一致検索を行なうため、情報処理装置１０は、再度、Ｓ２０３の処理を行なう。すなわち、Ｓ２０３〜Ｓ２０８の処理は、文字列の長さが「０」になるまで繰り返し行なわれる。
【００６６】
一方、文字の長さが「０」であれば（Ｓ２０９でＹＥＳ）、情報処理装置１０は、出力部１３において、これまでに取得された検索結果の候補を正式な検索結果として出力した後（Ｓ２１０）、この処理を終了する。
【００６７】
次に、図８を用いて、図６のＳ１０５に示す領域登録処理の流れの一例について説明する。すなわち、検索対象領域となる領域を登録する際の処理について説明する。
【００６８】
この処理が開始すると、情報処理装置１０は、領域登録部５０において、まず、指定された領域を検索対象領域として領域テーブル４３に登録する（Ｓ３０１）。検索対象領域は、例えば、入力部１２を介したユーザの指示により指定される。そして、情報処理装置１０は、領域登録部５０において、当該検索対象領域を覆うメッシュ群を求める（Ｓ３０２）。
【００６９】
情報処理装置１０は、領域登録部５０において、Ｓ３０２の処理で求められたメッシュ群をメッシュテーブル４１に登録するとともに（Ｓ３０３）、当該メッシュ群の中に部分内包メッシュがあるか否かを判定する。
【００７０】
判定の結果、部分内包メッシュがなければ（Ｓ３０４でＮＯ）、情報処理装置１０は、この処理を終了する。部分内包メッシュがあれば（Ｓ３０４でＹＥＳ）、情報処理装置１０は、領域登録部５０において、当該メッシュを下位階層のメッシュに細分化（すなわち詳細化）する（Ｓ３０５）。そして、当該細分化されたメッシュ群を詳細インデクステーブル４２に登録した後（Ｓ３０６）、この処理を終了する。
【００７１】
以上説明したように本実施形態によれば、通常の文字列検索のインデクス機構を流用して、前方一致検索を行なうことにより、着目地点を内包する検索対象領域を検索する際の処理負荷を軽減できる。更に、部分内包メッシュを詳細化した詳細インデクステーブルを設けることにより、詳細チェックの処理をより高速化できる。
【００７２】
なお、従来の技術において緯度・経度等に基づいた地理情報検索を行なう場合、テキスト検索のインデクスとは別の構造を持った専用インデクスが必要となっていたため、特に、組込み機器においてはリソースの負担が大きかった。
【００７３】
（実施形態２）
次に、実施形態２について説明する。上述した実施形態１においては、検索対象領域４０１が矩形形状である場合について説明したが、これに限られない。実施形態２においては、検索対象領域の形状の一例として、当該領域が円形である場合について説明する。例えば、図９（ａ）に示すように、検索対象領域４０６が円形であっても良い。この場合にも上記同様に、完全内包メッシュ６（符号４０７）と部分内包メッシュ１２（符号４０８）とがある。
【００７４】
図９（ｂ）には、検索対象領域４０６が円形である場合のメッシュテーブル４１及び、それからリンクされる領域テーブル４３の構成の一例が示される。なお、メッシュテーブル４１の構成は、図５で示した構成と同じ構成となる。
【００７５】
領域テーブル４３は、円形の検索対象領域４０６を管理する。カラム５１５には、検索対象領域のＩＤが保持される。カラム５１６には、検索対象領域（円）の中心地点のメッシュコードが保持される。カラム５１７には、円の半径距離が保持される。
【００７６】
また、上述した実施形態１で説明した図７のＳ２０５の詳細チェックにおいては、円形である検索対象領域の中心から着目地点までの距離を求め、それが半径以下であるか否かを比較することにより詳細チェックを行なう。このように構成することで、検索対象領域が円形の場合であっても、実施形態１と同様の処理が行なえる。
【００７７】
以上が本発明の代表的な実施形態の一例であるが、本発明は、上記及び図面に示す実施形態に限定することなく、その要旨を変更しない範囲内で適宜変形して実施できるものである。
【００７８】
また、本発明は、例えば、システム、装置、方法、プログラム若しくは記憶媒体等としての実施態様を採ることもできる。具体的には、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。
【００７９】
（その他の実施形態）
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【技術分野】
【０００１】
本発明は、情報処理装置、その処理方法及びプログラムに関する。
【背景技術】
【０００２】
近年、ストレージや記録メディアの大容量化が進み、比較的小規模な機器においても、大量に蓄積されたデータが扱われており、検索機能が必須となりつつある。
【０００３】
例えば、カメラにおいて撮影写真等が格納されるフラッシュメディアでは、現在、容量６４ＧＢのＳＤＸＣ規格のカードが市販されており、１枚１ＭＢの写真が６万枚以上格納されることになる。ＳＤＸＣの規格上は２ＴＢまで拡張可能である。
【０００４】
大量の写真から目的の写真を取得するには、従来のような撮影順の閲覧機能だけでは不十分であり、様々な観点から写真を検索できることが必要となる。その検索の方法の１つとしてメタデータ検索がある。例えば、写真に撮影場所の住所やランドマークのメタデータが付与されていれば、住所やランドマークの情報から写真を検索できる。そのためには、写真にメタデータを付与する機能が必要となる。
【０００５】
近年、カメラにＧＰＳ機能が搭載されるようになってきており、撮影場所の緯度・経度が分かる地理情報を写真に付与できるようになってきている。住所やランドマークの示す地理領域の辞書をカメラに内蔵し、緯度・経度情報に基づいて撮影地点を内包する地理領域を検索する地理情報検索が必要となってきている。
【０００６】
地理情報検索には、指定した範囲内に内包される地点のデータを検索する範囲指定検索、指定した位置に空間的に近い地点のデータを近い順にｋ個検索するｋ最近傍検索などがある。
【０００７】
範囲指定検索は、従来から多くの実現方法が存在している。有名な方法としては、Ｒ−ｔｒｅｅがある。Ｒ−ｔｒｅｅは、空間的に近傍にある領域を複数まとめて最小外接矩形（MBR：Minimum Bounding Rectangle）を求め、それをインデクスに保持することによって高速に検索を行なう方法である。領域のまとまりが多数あれば、それらを更に複数まとめたまとまりを作って、インデクスを階層化していく。
【０００８】
また、ｋ最近傍検索も多くの実現方法が存在している。特許文献１には、指定された地点から近傍する所定数の地点を検索する技術について言及されている。より具体的には、指定地点を含む小領域及びその小領域と隣接する小領域を検索対象小領域群として当該小領域群に含まれる地点と指定地点との距離を一つずつ計算し、最も近い地点から所定数の検索結果を得る。
【０００９】
その他、緯度・経度座標を文字列に符号化する方法も提案されている（特許文献２参照）。この手法では、緯度・経度の座標値（浮動小数点数）から整数、整数から文字列、緯度と経度との両方からそれぞれ変換された文字列を連接して符号化している。また、別の提案では、整数化された緯度及び経度の情報を１ビットずつ交互に組み合わせて文字列に符号化する方式や、この符号化方式を利用して指定領域内にある地点を検索する方法も提案されている。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００３−２４２１５１号公報
【特許文献２】米国特許出願公開第２００５／００２３５２４号
【発明の概要】
【発明が解決しようとする課題】
【００１１】
Ｒ−ｔｒｅｅ方式は、文字列検索用のインデクスとは異なる専用のインデクス機構を保持し制御する方式であり、特に、処理能力の低い装置（例えば、組み込み機器）にとっては処理負担が大きくなってしまう。
【００１２】
また、特許文献１に開示された手法では、指定地点に近い地点を検索することしかできない、そのため、住所やランドマークを付与するような、指定地点が不定形の領域に内包されている地点の検索を行なうことはできない。
【００１３】
本発明は、上記課題に鑑みてなされたものであり、地理情報検索を行なう際の処理負荷を軽減するようにした技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するため、本発明の一態様による情報処理装置は、地表が階層的にメッシュで区分されるとともに、該メッシュ各々の位置を示す地理コードが文字列で表現され、上位メッシュを表現する地理コードに文字を追加することで下位メッシュの地理コードを示す地理コード体系を有する地図データを保持する保持手段と、前記地図データ上で検索対象となる地点を示す着目地点の地理コードを取得する着目地点取得手段と、前記地図データ上で検索を行なう範囲を示す検索対象領域を覆うメッシュ群のうち、前記着目地点を示す地理コードの文字列と一致する地理コードの文字列を有する１又は複数のメッシュを検索結果の候補として取得する候補取得手段と、前記検索結果の候補として取得された１又は複数のメッシュのうち、前記検索対象領域に完全に内包されていないメッシュに対して前記着目地点を内包しているか否かを判定し、当該着目地点が内包されていない１又は複数のメッシュを前記メッシュ群から除外する除外手段と、前記検索結果の候補から前記除外が行なわれた後の１又は複数のメッシュを検索結果として出力する出力手段とを具備する。
【発明の効果】
【００１５】
本発明によれば、地理情報検索を行なう際の処理負荷を軽減することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施の形態に係る情報処理装置１０の構成の一例を示す図。
【図２】地理情報検索を行なう際の処理の概要を示す図。
【図３】本実施形態に係る地図データの一例を示す図。
【図４】検索対象領域を覆うメッシュの一例を示す図。
【図５】テーブル４１〜４３の構成の一例を示す図。
【図６】図１に示す情報処理装置１０の処理の流れの一例を示すフローチャート。
【図７】図６のＳ１０４に示す領域検索処理の流れの一例を示すフローチャート。
【図８】図６のＳ１０５に示す領域登録処理の流れの一例を示すフローチャート。
【図９】変形例の一例を示す図。
【発明を実施するための形態】
【００１７】
以下、本発明に係る実施の形態について添付図面を参照して詳細に説明する。
【００１８】
図１は、本発明の一実施の形態に係る情報処理装置１０の構成の一例を示す図である。
【００１９】
情報処理装置１０は、ＣＰＵ１１と、入力部１２と、出力部１３と、撮像部１４と、通信部１５と、バス１６と、ＲＯＭ１７と、ＲＡＭ１８と、外部記憶媒体１９とが具備して構成される。
【００２０】
ＣＰＵ（Central Processing Unit）１１は、例えば、ＲＯＭ１７に格納されたプログラムに従って、情報処理装置１０における処理を統括制御する。ＣＰＵ１１においては、例えば、検索処理、領域登録処理、画面制御処理、写真撮影処理等のための演算、論理判断等を行ない、バス１６を介してバスに接続された各デバイスを制御する。
【００２１】
バス１６は、アドレス信号やコントロール信号等を転送する。また、各デバイス間のデータ転送も行なう。
【００２２】
入力部１２は、例えば、ボタンやタッチパネル等で実現され、ユーザからの各種指示を装置内に入力する。出力部１３は、液晶ディスプレイ等で実現され、ユーザに向けて各種情報を出力（表示）する。なお、出力部１３による出力は、例えば、印刷により実現されても良いし、音声により実現されても良い。
【００２３】
撮像部１４は、例えば、撮像センサ等で実現され、映像を読み取って電子データに変換する。通信部１５は、例えば、ネットワークコントローラ等で実現され、有線又は無線の通信路を介して外部装置との間でデータ交換を行なう。
【００２４】
ＲＯＭ（Read Only Memory）１７は、不揮発性メモリである。ＣＰＵ１１により実行される各種プログラム（ブートプログラム２１、システムの制御プログラム２２）等の他、各種処理で参照される各種初期データ２３、地図データ２４等が格納される。
【００２５】
ＲＡＭ（Random Access Memory）１８は、読み書き可能なメモリである。ＲＡＭ１８は、各デバイスからの各種データの一次記憶に用いられる。ＲＡＭ１８には、各種ワーク領域３１の他、スタック３２等が格納される。
【００２６】
外部記憶媒体１９は、例えば、ＳＤカード、ＣＦカード等のフラッシュメディアで実現される。外部記憶媒体１９は、ブロック単位で一括消去可能な大容量の不揮発性メモリであり、大量のデータを変更可能に記憶する。なお、外部記憶媒体１９は、上述したカード等に限られず、ハードディスク等で代用することもできる。外部記憶媒体１９には、メッシュテーブル４１、詳細インデクステーブル４２、領域テーブル４３等が格納され、必要に応じて随時内容が修正される。
【００２７】
ここで、ＣＰＵ１１には、その機能的な構成として、☆と、☆とが実現される。なお、これら構成は、例えば、ＣＰＵ１１がＲＯＭ１７等に格納されたプログラムを実行することにより実現される。
【００２８】
領域登録部５０は、検索対象となる領域（検索対象領域）を登録する。検索対象領域は、例えば、入力部１２を介したユーザの指示により指定される。
【００２９】
着目地点取得部５１は、着目地点（のメッシュコード）を取得する。着目地点は、検索対象となる地図データ上の地点を示す。なお、詳細については後述するが、本実施形態に係わる地図データは、地表が階層的にメッシュで区分される。また、メッシュ各々の位置を示す地理コードが文字列で表現される。下位メッシュは、上位メッシュを表現する地理コードに文字が追加されることで表現される。
【００３０】
検索部５２は、着目地点を示す地理コードの文字列と、検索対象領域を覆うメッシュ群の地理コードの文字列とを比較し、所定のメッシュの検索を行なう機能を果たし、候補取得部６１と、除外部６２とを具備して構成される。候補取得部６１は、検索対象領域を覆うメッシュ群の中から着目地点を内包する１又は複数のメッシュを検索結果の候補として取得する。除外部６２は、メッシュの検索結果の候補の中から、所定の条件に従っていずれかのメッシュを除外する。
【００３１】
以上が、情報処理装置１０における機能的な構成についての説明である。なお、本実施形態においては、情報処理装置１０が撮像部１４を有する撮像装置（例えば、デジタルカメラやデジタルビデオカメラ）等に適用される場合について説明するが、これに限られない。情報処理装置１０は、例えば、通信装置や画像表示装置等の種々の装置に組み込み装置として適用されても良い。
【００３２】
また、上述した説明では、ＣＰＵ１１がプログラムを実行することで各種処理が実行される場合について説明したが、これに限られず、例えば、ＣＰＵと協調して動作するＡＳＩＣなどの制御回路が各種処理を実行しても良い。また、ＣＰＵと制御回路との協調動作によって各種処理が実行されてもよい。また、ＣＰＵは単一である必要はなく、複数であっても良い。この場合、複数のＣＰＵは分散して処理を実行する。また、複数のＣＰＵは単一のコンピュータに配置されていても良いし、物理的に異なる複数のコンピュータに配置されていても良い。なお、ＣＰＵがプログラムを実行することで実現される処理が専用の回路によって実現されても良い。
【００３３】
次に、図２を用いて、地点を含む領域を検索する地理情報検索を行なう際の処理の概要について説明する。
【００３４】
ここで、着目地点２０１を含む領域を検索する場合について説明する。この場合、着目地点２０１を内包する検索対象領域２０３及び２０６が検索の結果としてヒットする。これに対し、検索対象領域２０２、２０４及び２０５は、着目地点２０１を内包しないためヒットしない。
【００３５】
ここで、領域２０３及び領域２０４の関係に着目してみる。すなわち、領域２０３の中心が領域２０４の中心より遠いにもかかわらず、遠い方の領域２０３がヒットして、近い方の領域２０４がヒットしていないことに注意が必要である。このような検索は、写真に地名のメタデータを付与した場合などには必須である。例えば、「広尾」付近で撮影した写真には、中心地が近い「六本木」は付与されないが、中心地が遠い広域地名の「東京都」は付与される場合がある。
【００３６】
次に、図３（ａ）及び図３（ｂ）を用いて、本実施形態に係る地図データについて説明する。本実施形態においては、地図データは、地表を階層的なメッシュで区分し、緯度・経度情報に基づいてメッシュの位置を地理コードで表現する地理コード体系を有する。地理コードは文字列で表現される。
【００３７】
まず、図３（ａ）を用いて、緯度・経度情報を地理コードに変換する処理の一例について説明する。
【００３８】
緯度・経路情報を地理コードに変換する際には、まず、地表を緯度又は経度の方向に沿って２分割していき、分割の度に当該分割された地表に０又は１のビットを割り当てる。緯度及び経度のそれぞれに対して、そのビットを大分割から順番に並べてビット列を作成し、当該ビット列をメッシュの緯度情報３０１及び経度情報３０２とする。このように生成されたビット列に対して、経度、緯度の順番で先頭から交互に１ビットずつ選択していき、ビット列３０３を生成する。ビット列３０３を先頭から５ビットずつに分割し、変換表３０４に従って５ビット単位に当該ビット列を文字コードに変換する。これにより、地理コード３０５が得られる。
【００３９】
各メッシュは、地表の分割回数に応じて階層的に詳細化されたものになる。詳細化されたメッシュほど、緯度・経度情報のビット数が多くなり、変換後の文字列の文字数も多くなる。そのため、文字数がメッシュの精度を表現することになるので、メッシュの精度を文字列の文字数と定義することができる。このようにして生成されたメッシュの地理コードをメッシュコードと呼ぶ。
【００４０】
次に、図３（ｂ）を用いて、メッシュが構成する階層構造の一例について説明する。
【００４１】
メッシュ３０６は“ｅ”が表現する精度＝１（すなわち、文字数＝１）のメッシュを示している。当該メッシュ３０６内の１文字を“ｅ”に付加することによって、下位メッシュに３２分割することができる。
【００４２】
次の１文字が“７”の場合は、精度＝２のメッシュ３０７になり、メッシュコードが“ｅ７”となる。メッシュ３０７を拡大して示したものがメッシュ３０８になる。この場合にも同様に、次の１文字を付加することによって下位メッシュに３２分割することができる。
【００４３】
次の１文字が“ｓ”の場合は、精度＝３のメッシュ３０９となり、メッシュコードは“ｅ７ｓ”となる。すなわち、メッシュコードの文字数に応じてメッシュが階層化されていることが分かる。メッシュコードの文字数が同じ階層に属しているか否かを示すことになる。
【００４４】
ここで、表３１０は、このように階層化されたメッシュが表現する地理領域の概略面積の一例を示している。表３１０によれば、精度＝３のメッシュは、１５６ｋｍ×１５６ｋｍの矩形領域を表現することが示されている。また、精度を大きくすれば、より詳細な地理領域が表現されることが分かる。例えば、精度１２のメッシュコードであれば、事実上、地図データ上の特定の地点を表現できることになる。本実施形態においては、地点を特定する場合、システム上最も詳細な精度のメッシュコードで表現する。
【００４５】
次に、図４を用いて、検索対象領域を覆うメッシュの一例について説明する。
【００４６】
ここで、符号４０１は、検索対象領域を指している。この領域４０１を覆うメッシュは、メッシュ１〜メッシュ１７として示されている。各メッシュは、異なる階層に属すこともある。例えば、メッシュ８は他のメッシュよりも面積が大きいが、これは、複数の下位メッシュが統合されて階層が１段階上がった上位メッシュとなっているからである。
【００４７】
ここで、黒丸で示す地点４０２を着目地点とした検索を行なった場合、領域４０１はヒット領域となる。バツ印で示す地点４０３を着目地点とした検索を行なった場合、領域４０１はヒット領域とならない。ここで、メッシュのうち、検索対象領域内に完全に内包されるメッシュ（例えば、符号４０４）を完全内包メッシュと呼び、検索対象領域に部分的に内包されるメッシュ（例えば、符号４０５）を部分内包メッシュと呼ぶ。
【００４８】
地点４０３が着目地点の場合、メッシュ群に基づいて検索対象領域４０１を検索すると、メッシュ６がヒットする。ところが、メッシュ６は、部分内包メッシュであり、地点４０３が領域４０１の外側にある。そのため、その後実施される詳細チェックにおいて、地点４０３は、領域４０１に内包されないことが判明し、メッシュ６は検索結果から除かれることになる。このような詳細チェックによって最終的に検索結果から外れるが、処理途中では検索結果の候補とされる検索結果を「偽検索結果」と呼ぶ。
【００４９】
次に、図５を用いて、メッシュテーブル４１、詳細インデクステーブル４２、領域テーブル４３の構成の一例について説明する。
【００５０】
メッシュテーブル４１は、検索対象領域を覆うメッシュ群を管理する。カラム５０２には、各メッシュのメッシュコードが保持される。カラム５０３には、検索対象領域のＩＤが保持される。このＩＤを用いて領域テーブル４３を参照することにより、領域の詳細な情報が入手される。カラム５０４には、各メッシュの領域を検索対象領域が完全に内包するか否かを示すフラグ（「完全フラグ」と呼ぶ）が保持される。完全に内包されるときには（「完全内包」と呼ぶ）、“１”が保持され、部分的に内包されるときには（「部分内包」と呼ぶ）、“０”が保持される。カラム５０５には、部分内包のメッシュを更に詳細化したメッシュ群を管理する詳細インデクステーブル４２へのリンクが保持される。すなわち、メッシュテーブル４１には、検索対象領域と、完全フラグと、詳細インデクステーブル４２へのリンクとが対応付けて管理されている。
【００５１】
領域テーブル４３は、検索対象領域の地理的範囲を管理する。なお、ここでは、領域が矩形で構成されるものとして説明する。カラム５０７には、検索対象領域のＩＤが保持される。カラム５０８には、検索対象領域の左上地点のメッシュコードが保持される。カラム５０９には、検索対象領域の右下地点のメッシュコードが保持される。
【００５２】
詳細インデクステーブル４２は、部分内包メッシュを下位階層のメッシュに細分化して詳細化したメッシュ群を管理する。カラム５１１には、詳細化されたメッシュのメッシュコードが保持される。カラム５１２には、そのメッシュに対応する検索対象領域のＩＤが保持される。
【００５３】
ここで、上述した処理についてフローチャートを用いて説明する。図６は、図１に示す情報処理装置１０における処理の流れの一例を示す図である。この処理は、例えば、ＣＰＵ１１が、ＲＯＭ１７に格納されたプログラムを読み出し実行することにより実現される。
【００５４】
この処理では、情報処理装置１０は、ＣＰＵ１１において、まず、システムの初期化処理が行なわれる（Ｓ１０１）。すなわち、各種パラメータの初期化や初期画面の表示等が行なわれる。
【００５５】
その後、情報処理装置１０は、ＣＰＵ１１において、タッチパネル等の入力部１２から何らかのイベントが発生するまで待機する（Ｓ１０２）。イベントが発生すると、情報処理装置１０は、ＣＰＵ１１において、このイベントを判別し、イベントの種類に応じて各種の処理に分岐する。
【００５６】
ここで、領域検索処理を示すイベントであれば（Ｓ１０３で領域検索）、情報処理装置１０は、当該イベントに従って領域検索処理を行なう（Ｓ１０４）。また、領域登録処理を示すイベントであれば（Ｓ１０３で領域登録）、情報処理装置１０は、当該イベントに従って領域登録処理を行なう（Ｓ１０５）。それ以外のイベントであれば（Ｓ１０３でその他イベント）、情報処理装置１０は、各種イベントに対応した処理を行なう（Ｓ１０６）。なお、他のイベントとしては、画面制御処理、写真撮影処理などが挙げられる。
【００５７】
その後、情報処理装置１０は、出力部１３において、各処理の処理結果等をユーザに出力する。例えば、検索結果の表示、エラーがあった場合のエラー表示、正常な処理が行なわれた場合の画面表示等が行なわれる。
【００５８】
次に、図７を用いて、図６のＳ１０４に示す領域検索処理の流れの一例について説明する。すなわち、検索対象領域内で着目地点を内包する地理領域（１又は複数のメッシュ）を検索する際の処理について説明する。
【００５９】
この処理が開始すると、情報処理装置１０は、まず、着目地点取得部５１において、着目地点の取得を行なう（Ｓ２０１）。すなわち、着目地点を示すメッシュコードを取得する。着目地点は、例えば、入力部１２を介したユーザの指示により指定される。
【００６０】
続いて、情報処理装置１０は、候補取得部６１において、Ｓ２０１の処理で取得したメッシュコードを検索文字列として検索結果の候補の取得を行なう（Ｓ２０２、Ｓ２０３）。すなわち、検索文字列の少なくとも一部（前方文字列）と一致するメッシュコードを持つメッシュをメッシュテーブル４１から検索して取得し、それを検索結果の候補とする。
【００６１】
情報処理装置１０は、除外部６２において、検索結果の候補として取得されたメッシュの完全フラグをチェックする。すなわち、各メッシュが、完全内包メッシュであるか、部分内包メッシュであるかを判定する。
【００６２】
判定の結果、完全内包メッシュであれば（Ｓ２０４でＹＥＳ）、情報処理装置１０は、Ｓ２０８の処理に進む。一方、部分内包メッシュであれば（Ｓ２０４でＮＯ）、情報処理装置１０は、除外部６２において、着目地点と検索対象領域との位置関係の詳細チェックを行なう（Ｓ２０５）。すなわち、Ｓ２０３の処理で取得されたメッシュに含まれる着目地点が、検索対象領域内であるか否かをチェックする。このチェックでは、まず、詳細インデクステーブル４２から該当のメッシュの下位階層のメッシュ群を取得し、当該メッシュ群のうち着目地点を含むメッシュを取得する。そして、当該メッシュが検索対象領域内に内包されるか否かを判定する。これにより、検索対象領域内に内包されていなければ、Ｓ２０３の処理で検索されたメッシュは、偽検索結果であると判定される。
【００６３】
詳細チェックの結果、着目地点を内包しない、すなわち、偽検索結果であった場合（Ｓ２０６でＹＥＳ）、情報処理装置１０は、除外部６２において、当該偽検索結果を除外した後（Ｓ２０７）、Ｓ２０８の処理に進む。すなわち、偽検索結果となったメッシュを除外する。
【００６４】
一方、偽検索結果でなければ（Ｓ２０６でＮＯ）、情報処理装置１０は、検索部５２において、検索文字列の末尾を１文字削除する（Ｓ２０８）。すなわち、着目地点のメッシュの階層を１段階広範な領域に引き上げる。これにより、着目地点のメッシュコードの前方文字列とメッシュコードとが一致する、より広範なメッシュをメッシュテーブル４１から取得できることになる。
【００６５】
情報処理装置１０は、検索部５２において、１文字削除の結果、検索文字列の長さが「０」になったか否かを判定する。文字列の長さが「０」でなければ（Ｓ２０９でＮＯ）、より広範なメッシュの前方一致検索を行なうため、情報処理装置１０は、再度、Ｓ２０３の処理を行なう。すなわち、Ｓ２０３〜Ｓ２０８の処理は、文字列の長さが「０」になるまで繰り返し行なわれる。
【００６６】
一方、文字の長さが「０」であれば（Ｓ２０９でＹＥＳ）、情報処理装置１０は、出力部１３において、これまでに取得された検索結果の候補を正式な検索結果として出力した後（Ｓ２１０）、この処理を終了する。
【００６７】
次に、図８を用いて、図６のＳ１０５に示す領域登録処理の流れの一例について説明する。すなわち、検索対象領域となる領域を登録する際の処理について説明する。
【００６８】
この処理が開始すると、情報処理装置１０は、領域登録部５０において、まず、指定された領域を検索対象領域として領域テーブル４３に登録する（Ｓ３０１）。検索対象領域は、例えば、入力部１２を介したユーザの指示により指定される。そして、情報処理装置１０は、領域登録部５０において、当該検索対象領域を覆うメッシュ群を求める（Ｓ３０２）。
【００６９】
情報処理装置１０は、領域登録部５０において、Ｓ３０２の処理で求められたメッシュ群をメッシュテーブル４１に登録するとともに（Ｓ３０３）、当該メッシュ群の中に部分内包メッシュがあるか否かを判定する。
【００７０】
判定の結果、部分内包メッシュがなければ（Ｓ３０４でＮＯ）、情報処理装置１０は、この処理を終了する。部分内包メッシュがあれば（Ｓ３０４でＹＥＳ）、情報処理装置１０は、領域登録部５０において、当該メッシュを下位階層のメッシュに細分化（すなわち詳細化）する（Ｓ３０５）。そして、当該細分化されたメッシュ群を詳細インデクステーブル４２に登録した後（Ｓ３０６）、この処理を終了する。
【００７１】
以上説明したように本実施形態によれば、通常の文字列検索のインデクス機構を流用して、前方一致検索を行なうことにより、着目地点を内包する検索対象領域を検索する際の処理負荷を軽減できる。更に、部分内包メッシュを詳細化した詳細インデクステーブルを設けることにより、詳細チェックの処理をより高速化できる。
【００７２】
なお、従来の技術において緯度・経度等に基づいた地理情報検索を行なう場合、テキスト検索のインデクスとは別の構造を持った専用インデクスが必要となっていたため、特に、組込み機器においてはリソースの負担が大きかった。
【００７３】
（実施形態２）
次に、実施形態２について説明する。上述した実施形態１においては、検索対象領域４０１が矩形形状である場合について説明したが、これに限られない。実施形態２においては、検索対象領域の形状の一例として、当該領域が円形である場合について説明する。例えば、図９（ａ）に示すように、検索対象領域４０６が円形であっても良い。この場合にも上記同様に、完全内包メッシュ６（符号４０７）と部分内包メッシュ１２（符号４０８）とがある。
【００７４】
図９（ｂ）には、検索対象領域４０６が円形である場合のメッシュテーブル４１及び、それからリンクされる領域テーブル４３の構成の一例が示される。なお、メッシュテーブル４１の構成は、図５で示した構成と同じ構成となる。
【００７５】
領域テーブル４３は、円形の検索対象領域４０６を管理する。カラム５１５には、検索対象領域のＩＤが保持される。カラム５１６には、検索対象領域（円）の中心地点のメッシュコードが保持される。カラム５１７には、円の半径距離が保持される。
【００７６】
また、上述した実施形態１で説明した図７のＳ２０５の詳細チェックにおいては、円形である検索対象領域の中心から着目地点までの距離を求め、それが半径以下であるか否かを比較することにより詳細チェックを行なう。このように構成することで、検索対象領域が円形の場合であっても、実施形態１と同様の処理が行なえる。
【００７７】
以上が本発明の代表的な実施形態の一例であるが、本発明は、上記及び図面に示す実施形態に限定することなく、その要旨を変更しない範囲内で適宜変形して実施できるものである。
【００７８】
また、本発明は、例えば、システム、装置、方法、プログラム若しくは記憶媒体等としての実施態様を採ることもできる。具体的には、複数の機器から構成されるシステムに適用してもよいし、また、一つの機器からなる装置に適用してもよい。
【００７９】
（その他の実施形態）
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【特許請求の範囲】
【請求項１】
地表が階層的にメッシュで区分されるとともに、該メッシュ各々の位置を示す地理コードが文字列で表現され、上位メッシュを表現する地理コードに文字を追加することで下位メッシュの地理コードを示す地理コード体系を有する地図データを保持する保持手段と、
前記地図データ上で検索対象となる地点を示す着目地点の地理コードを取得する着目地点取得手段と、
前記地図データ上で検索を行なう範囲を示す検索対象領域を覆うメッシュ群のうち、前記着目地点を示す地理コードの文字列と一致する地理コードの文字列を有する１又は複数のメッシュを検索結果の候補として取得する候補取得手段と、
前記検索結果の候補として取得された１又は複数のメッシュのうち、前記検索対象領域に完全に内包されていないメッシュに対して前記着目地点を内包しているか否かを判定し、当該着目地点が内包されていない１又は複数のメッシュを前記メッシュ群から除外する除外手段と、
前記検索結果の候補から前記除外が行なわれた後の１又は複数のメッシュを検索結果として出力する出力手段と
を具備することを特徴とする情報処理装置。
【請求項２】
前記候補取得手段は、
前記着目地点を示す地理コードの文字列の長さが０になるまで、該文字列を１文字ずつ削除して前記着目地点を示す地理コードの文字列を用いた検索を繰り返し行ない、
前記除外手段は、
前記候補取得手段による検索が行なわれる度に前記除外を繰り返し行ない、
前記出力手段は、
前記地理コードの文字列の長さが０になった場合に、それまでに取得された検索結果を出力する
ことを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記検索対象領域を覆うメッシュ群それぞれの地理コードの文字列と、前記検索対象領域に完全に内包されているか否かを示す情報とを対応付けて管理するメッシュテーブルと、
前記メッシュテーブルに管理されるメッシュ群のうち、前記検索対象領域に完全に内包されていないメッシュの下位階層のメッシュに関する情報を管理する詳細インデクステーブルと
を更に具備し、
前記候補取得手段は、
前記メッシュテーブルを用いて前記検索結果の候補を取得し、
前記除外手段は、
前記詳細インデクステーブルを用いて前記除外を行なう
ことを特徴とする請求項１又は２記載の情報処理装置。
【請求項４】
情報処理装置の処理方法であって、
取得手段が、地表が階層的にメッシュで区分されるとともに、該メッシュ各々の位置を示す地理コードが文字列で表現され、上位メッシュを表現する地理コードに文字を追加することで下位メッシュの地理コードを示す地理コード体系を有する地図データを取得する工程と、
着目地点取得手段が、前記地図データ上で検索対象となる地点を示す着目地点の地理コードを取得する工程と、
候補取得手段が、前記地図データ上で検索を行なう範囲を示す検索対象領域を覆うメッシュ群のうち、前記着目地点を示す地理コードの文字列と一致する地理コードの文字列を有する１又は複数のメッシュを検索結果の候補として取得する工程と、
除外手段が、前記検索結果の候補として取得された１又は複数のメッシュのうち、前記検索対象領域に完全に内包されていないメッシュに対して前記着目地点を内包しているか否かを判定し、当該着目地点が内包されていない１又は複数のメッシュを前記メッシュ群から除外する工程と、
出力手段が、前記検索結果の候補から前記除外が行なわれた後の１又は複数のメッシュを検索結果として出力する工程と
を含むことを特徴とする情報処理装置。
【請求項５】
コンピュータを、
地表が階層的にメッシュで区分されるとともに、該メッシュ各々の位置を示す地理コードが文字列で表現され、上位メッシュを表現する地理コードに文字を追加することで下位メッシュの地理コードを示す地理コード体系を有する地図データを保持する保持手段、
前記地図データ上で検索対象となる地点を示す着目地点の地理コードを取得する着目地点取得手段、
前記地図データ上で検索を行なう範囲を示す検索対象領域を覆うメッシュ群のうち、前記着目地点を示す地理コードの文字列と一致する地理コードの文字列を有する１又は複数のメッシュを検索結果の候補として取得する候補取得手段、
前記検索結果の候補として取得された１又は複数のメッシュのうち、前記検索対象領域に完全に内包されていないメッシュに対して前記着目地点を内包しているか否かを判定し、当該着目地点が内包されていない１又は複数のメッシュを前記メッシュ群から除外する除外手段、
前記検索結果の候補から前記除外が行なわれた後の１又は複数のメッシュを検索結果として出力する出力手段
として機能させるためのプログラム。
【請求項１】
地表が階層的にメッシュで区分されるとともに、該メッシュ各々の位置を示す地理コードが文字列で表現され、上位メッシュを表現する地理コードに文字を追加することで下位メッシュの地理コードを示す地理コード体系を有する地図データを保持する保持手段と、
前記地図データ上で検索対象となる地点を示す着目地点の地理コードを取得する着目地点取得手段と、
前記地図データ上で検索を行なう範囲を示す検索対象領域を覆うメッシュ群のうち、前記着目地点を示す地理コードの文字列と一致する地理コードの文字列を有する１又は複数のメッシュを検索結果の候補として取得する候補取得手段と、
前記検索結果の候補として取得された１又は複数のメッシュのうち、前記検索対象領域に完全に内包されていないメッシュに対して前記着目地点を内包しているか否かを判定し、当該着目地点が内包されていない１又は複数のメッシュを前記メッシュ群から除外する除外手段と、
前記検索結果の候補から前記除外が行なわれた後の１又は複数のメッシュを検索結果として出力する出力手段と
を具備することを特徴とする情報処理装置。
【請求項２】
前記候補取得手段は、
前記着目地点を示す地理コードの文字列の長さが０になるまで、該文字列を１文字ずつ削除して前記着目地点を示す地理コードの文字列を用いた検索を繰り返し行ない、
前記除外手段は、
前記候補取得手段による検索が行なわれる度に前記除外を繰り返し行ない、
前記出力手段は、
前記地理コードの文字列の長さが０になった場合に、それまでに取得された検索結果を出力する
ことを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記検索対象領域を覆うメッシュ群それぞれの地理コードの文字列と、前記検索対象領域に完全に内包されているか否かを示す情報とを対応付けて管理するメッシュテーブルと、
前記メッシュテーブルに管理されるメッシュ群のうち、前記検索対象領域に完全に内包されていないメッシュの下位階層のメッシュに関する情報を管理する詳細インデクステーブルと
を更に具備し、
前記候補取得手段は、
前記メッシュテーブルを用いて前記検索結果の候補を取得し、
前記除外手段は、
前記詳細インデクステーブルを用いて前記除外を行なう
ことを特徴とする請求項１又は２記載の情報処理装置。
【請求項４】
情報処理装置の処理方法であって、
取得手段が、地表が階層的にメッシュで区分されるとともに、該メッシュ各々の位置を示す地理コードが文字列で表現され、上位メッシュを表現する地理コードに文字を追加することで下位メッシュの地理コードを示す地理コード体系を有する地図データを取得する工程と、
着目地点取得手段が、前記地図データ上で検索対象となる地点を示す着目地点の地理コードを取得する工程と、
候補取得手段が、前記地図データ上で検索を行なう範囲を示す検索対象領域を覆うメッシュ群のうち、前記着目地点を示す地理コードの文字列と一致する地理コードの文字列を有する１又は複数のメッシュを検索結果の候補として取得する工程と、
除外手段が、前記検索結果の候補として取得された１又は複数のメッシュのうち、前記検索対象領域に完全に内包されていないメッシュに対して前記着目地点を内包しているか否かを判定し、当該着目地点が内包されていない１又は複数のメッシュを前記メッシュ群から除外する工程と、
出力手段が、前記検索結果の候補から前記除外が行なわれた後の１又は複数のメッシュを検索結果として出力する工程と
を含むことを特徴とする情報処理装置。
【請求項５】
コンピュータを、
地表が階層的にメッシュで区分されるとともに、該メッシュ各々の位置を示す地理コードが文字列で表現され、上位メッシュを表現する地理コードに文字を追加することで下位メッシュの地理コードを示す地理コード体系を有する地図データを保持する保持手段、
前記地図データ上で検索対象となる地点を示す着目地点の地理コードを取得する着目地点取得手段、
前記地図データ上で検索を行なう範囲を示す検索対象領域を覆うメッシュ群のうち、前記着目地点を示す地理コードの文字列と一致する地理コードの文字列を有する１又は複数のメッシュを検索結果の候補として取得する候補取得手段、
前記検索結果の候補として取得された１又は複数のメッシュのうち、前記検索対象領域に完全に内包されていないメッシュに対して前記着目地点を内包しているか否かを判定し、当該着目地点が内包されていない１又は複数のメッシュを前記メッシュ群から除外する除外手段、
前記検索結果の候補から前記除外が行なわれた後の１又は複数のメッシュを検索結果として出力する出力手段
として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−２５６１２０（Ｐ２０１２−２５６１２０Ａ）
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願番号】特願２０１１−１２７６５６（Ｐ２０１１−１２７６５６）
【出願日】平成２３年６月７日（２０１１．６．７）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願日】平成２３年６月７日（２０１１．６．７）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]