情報処理装置、その処理方法及びプログラム
【課題】地図データ上の所定範囲に内包されるデータを検索する際の処理負荷を軽減するようにした技術を提供する。
【解決手段】地表が階層的にメッシュで区分され、該メッシュ各々の位置を文字列で示す地理コードを持ち、上位メッシュを表現する該コードに文字を追加すると下位メッシュの地理コードが示される体系を有する地図データ保持手段と、前記地図データの検索範囲を取得する検索範囲取得手段と、前記検索範囲を覆うメッシュ群を選定するメッシュ群処理手段と、地点情報が設定された複数のデータから該地点情報を示す地理コードを取得する情報取得手段と、前記情報取得手段により取得された地理コードと前記検索範囲を覆うメッシュ群とにおける地理コードを比較することにより、該メッシュ群に内包されるデータを検索する検索手段と、検索により得られた検索結果を出力する出力手段とを具備する。
【解決手段】地表が階層的にメッシュで区分され、該メッシュ各々の位置を文字列で示す地理コードを持ち、上位メッシュを表現する該コードに文字を追加すると下位メッシュの地理コードが示される体系を有する地図データ保持手段と、前記地図データの検索範囲を取得する検索範囲取得手段と、前記検索範囲を覆うメッシュ群を選定するメッシュ群処理手段と、地点情報が設定された複数のデータから該地点情報を示す地理コードを取得する情報取得手段と、前記情報取得手段により取得された地理コードと前記検索範囲を覆うメッシュ群とにおける地理コードを比較することにより、該メッシュ群に内包されるデータを検索する検索手段と、検索により得られた検索結果を出力する出力手段とを具備する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、その処理方法及びプログラムに関する。
【背景技術】
【０００２】
近年、ストレージや記録メディアの大容量化が進み、比較的小規模な機器においても、大量に蓄積されたデータが扱われており、検索機能が必須となりつつある。
【０００３】
例えば、カメラにおいて撮影写真等が格納されるフラッシュメディアでは、現在、容量６４ＧＢのＳＤＸＣ規格のカードが市販されており、１枚１ＭＢの写真が６万枚以上格納されることになる。ＳＤＸＣの規格上は２ＴＢまで拡張可能である。
【０００４】
大量の写真から目的の写真を取得するには、従来のような撮影順の閲覧機能だけでは不十分であり、様々な観点から写真を検索できることが必要となる。例えば、写真を撮影場所に基づいて地図データ上に表示する機能も必要である。
【０００５】
近年、写真にＧＰＳ情報のような緯度・経度が分かる地点情報が付与されるようになってきている。例えば、緯度・経度情報に基づいて検索範囲に内包される地点を検索する地点情報検索を行なえば、地点情報に基づいた写真を検索できる。
【０００６】
地点情報検索には、指定した範囲内に内包される地点のデータを検索する範囲指定検索、指定した位置に空間的に近い地点のデータを近い順にｋ個検索するｋ最近傍検索などがあるが、上述したような地点情報検索は、範囲指定検索の適用例となる。
【０００７】
このような範囲指定検索は、従来から多くの実現方法が存在している。有名な方法としては、Ｒ−ｔｒｅｅがある。Ｒ−ｔｒｅｅは、空間的に近傍にある領域を複数まとめて最小外接矩形（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 ]