(57)【要約】有理数表現された複数の位置情報について、差分符号化による位置情報の符号化／復号を可能とする、複数位置情報の符号化装置であって、有理数表現されて、数値の大小順に並んだ複数の位置情報を、予め決められた順序関係を設けて、その順序関係に従う順に複数の位置情報を並べ替える位置情報並替部（１０１）を備える。位置情報が決められた順序関係に従って並べ替えられることで、整数表現された位置情報と同様に、差分符号化による複数位置情報の符号化が可能となる。
2004070955.tif 000002
【特許請求の範囲】
【請求項１】
木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化装置であって、
符号化する複数の位置情報を所定の順序関係に従って並び替える並び替え手段と、
前記並び替え手段から出力された複数の位置情報の、連続する２つの位置情報から、前記所定の順序関係に従って分岐階層を判定する判定手段と、
前記分岐階層に対応する符号を出力する符号化手段と、
を備えることを特徴とする符号化装置。
【請求項２】
木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化装置であって、
符号化する複数の位置情報が所定の順序関係に従って並んだものであり、
前記符号化する複数の位置情報の、連続する２つの位置情報から、前記所定の順序関係に従って分岐階層を判定する判定手段と、
前記分岐階層に対応する符号を出力する符号化手段と、
を備えることを特徴とする符号化装置。
【請求項３】
前記複数の位置情報は、有理数で表現された有理数位置情報であって、
前記所定の順序関係は、有理数の解像度の大小順に従って決められていることを特徴とする、請求項１又は２に記載の符号化装置。
【請求項４】
木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化装置であって、
符号化する複数の位置情報に基づいて位置情報の値の増加幅を決める増加幅決定手段と、
前記増加幅を符号化して符号を出力する増加幅符号化手段と、
前記符号化する複数の位置情報の連続する２つの位置情報から、分岐階層を判定する判定手段と、
前記分岐階層に対応する符号を出力する分岐階層符号化手段と、
を備えることを特徴とする符号化装置。
【請求項５】
前記複数の位置情報は、有理数で表現された有理数位置情報であって、
前記増加幅は、前記複数の位置情報が全て符号化可能となるように、前記分岐階層毎に決めることを特徴とする、請求項４に記載の符号化装置。
【請求項６】
前記木構造は検索情報を表すものであり、前記符号化する複数の位置情報に対応する葉又は節は、前記検索情報に含まれる同種の要素に対応した葉又は節であることを特徴とする、請求項１乃至５のいずれか１に記載の符号化装置。
【請求項７】
木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化方法であって、
符号化する複数の位置情報を所定の順序関係に従って並び替える並び替えステップと、
前記並び替えステップから出力された複数の位置情報の、連続する２つの位置情報から、前記所定の順序関係に従って分岐階層を判定する判定ステップと、
前記分岐階層に対応する符号を出力する符号化ステップと、
を有することを特徴とする符号化方法。
【請求項８】
木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化方法であって、
符号化する複数の位置情報が所定の順序関係に従って並んだものであり、
前記符号化する複数の位置情報の、連続する２つの位置情報から、前記所定の順序関係に従って分岐階層を判定する判定ステップと、
前記分岐階層に対応する符号を出力する符号化ステップと、
を有することを特徴とする符号化方法。
【請求項９】
前記複数の位置情報は、有理数で表現された有理数位置情報であって、
前記所定の順序関係は、有理数の解像度の大小順に従って決められていることを特徴とする、請求項７又は８に記載の符号化方法。
【請求項１０】
木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化方法であって、
符号化する複数の位置情報に基づいて位置情報の値の増加幅を決める増加幅決定ステップと、
前記増加幅を符号化して符号を出力する増加幅符号化ステップと、
前記符号化する複数の位置情報の連続する２つの位置情報から、分岐階層を判定する判定ステップと、
前記分岐階層に対応する符号を出力する分岐階層符号化ステップと、
を有することを特徴とする符号化方法。
【請求項１１】
前記複数の位置情報は、有理数で表現された有理数位置情報であって、
前記増加幅は、前記複数の位置情報が全て符号化可能となるように、前記分岐階層毎に決めることを特徴とする、請求項１０に記載の符号化方法。
【請求項１２】
前記木構造は検索情報を表すものであり、前記符号化する複数の位置情報に対応する葉又は節は、前記検索情報に含まれる同種の要素に対応した葉又は節であることを特徴とする、請求項７乃至１１のいずれか１に記載の符号化方法。
【請求項１３】
木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報が符号化された位置情報符号列を復号する復号装置であって、
復号された位置情報を逐次保持する保持手段と、
前記位置情報符号に基づいて、連続する２つの位置情報の分岐階層を判定する判定手段と、
前記保持手段で保持された位置情報に対して、前記分岐階層に対応する位置情報の値を所定の順序関係に従って１つ分増加させる復号手段と、
を備えることを特徴とする復号装置。
【請求項１４】
当該復号装置は、さらに、
複数の前記復号された位置情報を、数値の大小順に従って並び替える並び替え手段を備えることを特徴とする、請求項１３に記載の復号装置。
【請求項１５】
前記並び替え手段は、さらに、
前記復号された位置情報の各々に振られる、数値の大小順を表した連続番号を計算する計算手段を含むことを特徴とする、請求項１４に記載の復号装置。
【請求項１６】
前記複数の位置情報は、有理数で表現された有理数位置情報であって、
前記所定の順序関係は、有理数の解像度の大小順に従って決められていることを特徴とする、請求項１３乃至１５のいずれか１に記載の復号装置。
【請求項１７】
木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報が符号化された位置情報符号列を復号する復号装置であって、
位置情報の値の増加幅を復号する増加幅復号手段と、
復号された位置情報を逐次保持する保持手段と、
前記位置情報符号に基づいて、連続する２つの位置情報の分岐階層を判定する判定手段と、
前記保持手段で保持された位置情報に対して、前記分岐階層に対応する位置情報の値を前記増加幅分増加させる位置情報復号手段と、
を備えることを特徴とする復号装置。
【請求項１８】
前記木構造は検索情報を表すものであり、前記復号される位置情報に対応する葉又は節は、前記検索情報に含まれる同種の要素に対応した葉又は節であることを特徴とする、請求項１３乃至１７のいずれか１に記載の復号装置。
【請求項１９】
木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報が符号化された位置情報符号列を復号する復号方法であって、
復号された位置情報を逐次保持する保持ステップと、
前記位置情報符号に基づいて、連続する２つの位置情報の分岐階層を判定する判定ステップと、
前記保持ステップで保持された位置情報に対して、前記分岐階層に対応する位置情報の値を所定の順序関係に従って１つ分増加させる復号ステップと、
を有することを特徴とする復号方法。
【請求項２０】
当該復号方法は、さらに、
複数の前記復号された位置情報を、数値の大小順に従って並び替える並び替えステップを有することを特徴とする、請求項１９に記載の復号方法。
【請求項２１】
前記並び替えステップは、さらに、
前記復号された位置情報の各々に振られる、数値の大小順を表した連続番号を計算する計算ステップを含むことを特徴とする、請求項２０に記載の復号方法。
【請求項２２】
前記複数の位置情報は、有理数で表現された有理数位置情報であって、
前記所定の順序関係は、有理数の解像度の大小順に従って決められていることを特徴とする、請求項１９乃至２１のいずれか１に記載の復号方法。
【請求項２３】
木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報が符号化された位置情報符号列を復号する復号方法であって、
位置情報の値の増加幅を復号する増加幅復号ステップと、
復号された位置情報を逐次保持する保持ステップと、
前記位置情報符号に基づいて、連続する２つの位置情報の分岐階層を判定する判定ステップと、
前記保持ステップで保持された位置情報に対して、前記分岐階層に対応する位置情報の値を前記増加幅分増加させる位置情報復号ステップと、
を備えることを特徴とする復号方法。
【請求項２４】
前記木構造は検索情報を表すものであり、前記復号される位置情報に対応する葉又は節は、前記検索情報に含まれる同種の要素に対応した葉又は節であることを特徴とする、請求項１９乃至２３のいずれか１に記載の復号方法。
【請求項２５】
請求項１乃至６のいずれか１に記載の符号化装置として、コンピュータを機能させるためのプログラム。
【請求項２６】
請求項７乃至１２のいずれか１に記載の符号化方法をコンピュータに実行させるためのプログラム。
【請求項２７】
請求項１３乃至１８のいずれか１に記載の復号装置として、コンピュータを機能させるためのプログラム。
【請求項２８】
請求項１９乃至２４のいずれか１に記載の復号方法をコンピュータに実行させるためのプログラム。
【請求項２９】
請求項２５乃至２８のいずれか１に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】  本発明は、符号化装置、符号化方法、復号装置、復号方法、プログラム、及び記録媒体に関し、より詳細には、木構造中の葉及び／又は節に関する位置情報を複数まとめて効率的に符号化／復号する、符号化装置、符号化方法、復号装置、復号方法、プログラム、及び記録媒体に関する。
【背景技術】  木構造によるデータ表現は、情報処理のさまざまな分野で使用されている。その代表的な例が、動画像コンテンツに対応して与えられる検索情報の木構造表現である。
図２６は、従来技術による動画像コンテンツに対応して与えられた木構造を有する検索情報の一例を示す図である。
１つの動画像コンテンツが１つ又は複数のシーンによって構成され、また１つのシーンが１つ又は複数のショットによって構成されるとする。そして各々のショットには、ショット別の動き強度や色頻度、又はショットの内容を表す要約文といったショットの特徴を表すデータが与えられるとすると、この動画像コンテンツの検索情報は、図２６に示すような木構造で表される。
図２６で示す例は、動画像コンテンツが３つのシーン（＃０，＃１，＃２）からなり、各々のシーンがさらに３つのショット（＃０，＃１，＃２）で構成され、それぞれのショット毎に動き強度を表すデータが付加された場合の検索情報を表したものである。本例では、動き強度を強＝３、中＝２、弱＝１の３値をとるデータとして示している。
木構造としては、動画像コンテンツが根にあたり、シーン、ショット、及びデータの種別を示した動き強度のタグ情報が節にあたり、実際の動き強度を表すデータが葉にあたる。シーンは根から見て最初の分岐位置、即ち第１階層の節であり、ショットは第２階層の節である。無論、図２６は一例であり、動画像コンテンツ及びその検索情報は、もっと複雑な階層構造を持つことが多い。
このような動画像コンテンツの検索情報を扱う際、各葉にあたる検索データの各々を随時取り出して伝送する、又は保存するといった要求がある。その場合、取り出された各データはそれ自体では個々の識別ができないため、各データに識別のための情報が付加される。例えば、図２６におけるデータ２６０１は、それ自体では単なる「１」という数値に過ぎず、そのデータがシーン番号何番のショット番号何番に関するどういった種別の検索情報を表したデータであるかといった識別情報があって初めて、検索データとして利用することができる。
動画像コンテンツの検索情報など、マルチメディアコンテンツの内容記述の国際規格であるＭＰＥＧ−７では、この検索データ＝葉に対する識別情報を、木構造の根からその葉に至るまでに経由する木の経路の情報で与える。ＭＰＥＧ−７では、この経路の情報を「枝符号（Ｔｒｅｅ  Ｂｒａｎｃｈ  Ｃｏｄｅ）」と呼んでいる。例えば、図２６のデータ２６０１は、
／シーン＃０／ショット＃０／動き強度
と表すことで一意に特定される。同様に、データ２６０２は
／シーン＃０／ショット＃１／動き強度
データ２６０４は
／シーン＃１／ショット＃０／動き強度
と表される。これは節の場合でも同様であり、各節に対する識別情報も、木構造の根からその節に至るまでに経由する木の経路の情報で与えられる。
上述した識別情報の中で、「シーン」、「ショット」、「動き強度」といった情報は、検索情報の要素種別を表す情報である。一方、「０」、「１」といった数で与えられている情報は、同じ要素がある節から枝分かれした時の個々の要素を区別するために付けられた識別番号で、木構造中の葉や節の位置を決定することから「位置情報」と呼ばれる。ＭＰＥＧ−７では、これらの要素種別情報と位置情報とが個々に符号化されて、検索データと共に扱われる。
上述したように、データ２６０１〜２６０９のそれぞれの識別情報は、同じ要素種別情報を持ち、位置情報のみが異なっている。ＭＰＥＧ−７では、このような位置情報のみ異なる識別情報が付された複数の検索データを、まとめて伝送する又は保存するためのデータ形式が規定されている。そして、ＭＰＥＧ−７ではそのため、複数の異なる位置情報を差分符号化する、以下の位置情報符号化／復号技術が規定されている。
図２７は、従来技術によるＭＰＥＧ−７に従った差分符号化による位置情報符号化装置の概略構成を示す機能ブロック図である。また、図２８は、従来技術による位置情報の符号化装置で符号化される位置情報及び符号化された位置情報符号列の一例を示す図で、図２６の各動き強度データ２６０１〜２６０９の識別情報から位置情報を抜き出して示したものと、それらを符号化して得られる位置情報符号列との関係を示す図である。
図２６中の隣り合う２つの検索データである葉２６０１と葉２６０２について、木構造の根２６１０からそれぞれの葉２６０１、２６０２に至るまでに経由する木の経路を比較すると、根（動画像コンテンツ）から第１階層の節（シーン＃０）までが共通であり、シーン＃０より下、即ち第２階層の節（ショット＃０とショット＃１）以降で枝が分かれていることが判る。この枝分かれした直後の階層を、隣り合う２つの葉に対する「分岐階層」と呼ぶ。葉２６０１と葉２６０２に対する分岐階層は、第２階層、即ちショットの階層である。同様に、隣り合う２つの葉２６０３と葉２６０４とでは、２つの経路は根（動画像コンテンツ）のみが共通であり、第１階層の節（シーン＃０とシーン＃１）で既に分岐が起こっているため、隣り合う２つの葉２６０３と葉２６０４に対する分岐階層は第１階層、即ちシーンの階層となる。
この分岐階層は、図２８に示したような識別情報から抜き出された位置情報どうしの関係で見た場合、隣り合う２つの位置情報における各階層の値を上位の階層から下位の階層へと順に比較していった時、最初に値が変化した階層に相当する。従来技術における差分符号化は、この時の位置情報の値の変化が常に１づつの増加であることを前提として、位置情報の値の変化を、どの階層の値が増加したか、という情報に置き換え、その分岐階層の情報を符号化してやることで元の位置情報を符号化するものである。こうした差分符号化では、存在する分岐階層数分が符号化によって区別できればよいことから、位置情報をそのまま符号化するのに比べて情報の圧縮がなされる。
先頭位置情報符号化部２７０２は、先頭の位置情報を、差分を用いない通常の方式で符号化する。図２８では、１変数あたり５ビットとし、先頭の位置情報（０，０）を５ビット×２＝１０ビットの符号として与えた。同時に、この先頭の位置情報（０，０）は、前位置情報保持部２７０３に入力されて保持され、次の位置情報（０，１）の符号化に利用される。
分岐階層判定部２７０４は、入力されてくる次に符号化する位置情報と、前位置情報保持部２７０３に保持されている位置情報とを比較し、それらを基に分岐階層の判定を行って、その判定結果を差分位置情報符号化部２７０５に出力する。図２８で、次に符号化する第２の位置情報（０，１）と、前位置情報保持部２７０３に保持されている位置情報（０，０）とでは、第１階層、即ちシーンの階層の値は同じであり、第２階層、即ちショットの階層の位置情報の値が増加しているため、第２階層＝ショットの階層で分岐していることが判る。この判定結果を差分位置情報符号化部２７０５に出力する。
差分位置情報符号化部２７０５は、分岐階層判定部２７０４の判定結果に従って位置情報符号を選択し出力する。ここでの場合、分岐階層判定部２７０４で（０，１）と（０，０）との分岐階層が第２階層と判定されたため、図２８に示されるように分岐階層が第２階層であることを表す符号（第２階層を１増加することを示す位置情報符号）“１０”が与えられている。同様に、第３の位置情報（０，２）にも第２階層を表す符号“１０”が与えられる。次に第４の位置情報（１，０）は、第３の位置情報（０，２）と比較すると、第１階層、即ちシーンの階層の位置情報の値が増加しているため、第１階層＝シーンの階層で分岐していることが判る。このため、分岐階層が第１階層であることを表す符号（第１階層を１増加することを示す位置情報符号）“０１”を与える。こうして最後まで符号化して得られる位置情報符号列が、図２８に示した位置情報符号列である。符号列の最後には、続く位置情報が無い、即ち符号の終了を示す終了符号“１１”が付加されている。
なお、図２８で用いた分岐階層に対応する位置情報符号を図２９に示す。
図３０は、従来技術の差分符号化による位置情報の復号装置の概略構成を示す機能ブロック図である。
まず、先頭位置情報復号部３００１で、先頭の位置情報を、通常の復号方式で復号する。復号された位置情報は、前位置情報保持部３００２に入力して保持される。次に、分岐階層判定部３００３で位置情報符号を読み込む。そして、読み込まれた符号に基づいて分岐階層を判定し、判定結果を差分位置情報復号部３００４に送る。そして、差分位置情報復号部３００４で、分岐階層判定部３００３の判定結果から、前位置情報保持部３００２に保持された位置情報の値を更新して、更新した位置情報を出力すると共に、前位置情報保持部３００２で更新後の位置情報を保持する。これを、終了符号が読み込まれるまで繰り返す。
前位置情報保持部３００２に先頭の位置情報（０，０）が復号され保持された状態で、分岐階層判定部３００３は符号“１０”を読み込む。符号“１０”は第２階層で分岐したことを示す符号であるため、差分位置情報復号部３００４で（０，０）の第２階層の値を１増加させ、次の位置情報（０，１）が求められる。同様に（０，２）まで復号され、前位置情報保持部３００２に保持された状態で、次に、分岐階層判定部３００３には符号“０１”が読み込まれる。符号“０１”は第１階層で分岐したことを示す符号であるため、差分位置情報復号部３００４では前位置情報保持部３００２に保持された（０，２）の第１階層の位置情報を１増加させる。また同時に、第１階層の値が変わったため、それより下の階層の位置情報は初期の値０に設定する。こうして次の位置情報（１，０）が得られる。この処理を最後まで行い、終了符号“１１”が読み込まれた時点で復号を終了する。
ところで、昨今、上述した位置情報を有理数で表現することが行われつつある。例えば、図２に示すように、位置情報を全て０より大きく１未満の有理数、ここでは「２のべき乗分の自然数（分母が２のべき乗数、分子が自然数）」といった値で表す。これは、既に存在する葉又は節の位置の間にさらに葉又は節を任意に追加する、といった処理を可能とするために導入されるものである。
例えば、図２６において、シーン＃０の下のショット＃０とショット＃１の間に別のショットを追加することはそのままではできず、追加するためにはショット＃１以降のショットの番号を付け直すなどの処理を加えなければならなかった。一方、図２のように位置情報を有理数表現とした場合では、シーン＃（１／４）の下のショット＃（１／４）とショット＃（１／２）の間に新たにショットを追加したければ、新たなショットの位置情報を３／８とすることで、既存のショットに手を加えずに新たなショットの追加ができる。
【発明の開示】
上述したＭＰＥＧ−７で規定されている複数の位置情報をまとめて差分符号化／復号する位置情報の符号化／復号技術は、位置情報が整数で与えられ、隣り合う位置情報の間隔が一定量、即ち１であることを前提にしたものである。この前提があるため、どの階層で分岐したかのみを符号化情報として符号化することができた。
一方、上述した有理数表現による位置情報では、隣り合う位置情報間の間隔が任意に変わる。例えば、位置１／４の次の位置情報は、１／２であることもあれば３／８であることもあり、あるいは５／１６であってもよい。従って、上述のごとき整数表現された位置情報で成立した前提は、有理数表現された位置情報には当てはまらず、このため、ＭＰＥＧ−７で規定された複数位置情報の符号化／復号技術を有理数表現された位置情報に直接適用することはできなかった。
本発明は、上述のごとき実情に鑑みてなされたものであり、有理数表現された、複数の葉及び／又は節の位置情報であっても、差分符号化／復号することが可能な、符号化装置及び方法、復号装置及び方法、符号化プログラム、復号プログラム、並びにそれらプログラムを記録したコンピュータ読み取り可能な記録媒体を提供することをその目的とする。
本願の第１の発明は、木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化装置であって、符号化する複数の位置情報を所定の順序関係に従って並び替える並び替え手段と、前記並び替え手段から出力された複数の位置情報の、連続する２つの位置情報から、前記所定の順序関係に従って分岐階層を判定する判定手段と、前記分岐階層に対応する符号を出力する符号化手段とを備えたことを特徴とする。
本願の第２の発明は、木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化装置であって、符号化する複数の位置情報が所定の順序関係に従って並んだものであり、前記符号化する複数の位置情報の、連続する２つの位置情報から、前記所定の順序関係に従って分岐階層を判定する判定手段と、前記分岐階層に対応する符号を出力する符号化手段とを備えたことを特徴とする。
本願の第３の発明は、さらに、前記第１又は第２の発明において、前記複数の位置情報が、有理数で表現された有理数位置情報であって、前記所定の順序関係は、有理数の解像度の大小順に従って決めることを特徴とする。
本願の第４の発明は、木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化装置であって、符号化する複数の位置情報に基づいて位置情報の値の増加幅を決める増加幅決定手段と、前記増加幅を符号化して符号を出力する増加幅符号化手段と、前記符号化する複数の位置情報の連続する２つの位置情報から、分岐階層を判定する判定手段と、前記分岐階層に対応する符号を出力する分岐階層符号化手段とを備えたことを特徴とする。
本願の第５の発明は、さらに、前記第４の発明において、前記複数の位置情報が、有理数で表現された有理数位置情報であって、前記増加幅は、前記複数の位置情報が全て符号化可能となるように、前記分岐階層毎に決めることを特徴とする。
本願の第６の発明は、さらに、前記第１乃至第５のいずれか１の発明において、前記木構造が検索情報を表すものであり、前記符号化する複数の位置情報に対応する葉又は節が、前記検索情報に含まれる同種の要素に対応した葉又は節であることを特徴とする。
本願の第７の発明は、木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化方法であって、符号化する複数の位置情報を所定の順序関係に従って並び替える並び替えステップと、前記並び替えステップから出力された複数の位置情報の、連続する２つの位置情報から、前記所定の順序関係に従って分岐階層を判定する判定ステップと、前記分岐階層に対応する符号を出力する符号化ステップとを備えたことを特徴とする。
本願の第８の発明は、木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化方法であって、符号化する複数の位置情報が所定の順序関係に従って並んだものであり、前記符号化する複数の位置情報の、連続する２つの位置情報から、前記所定の順序関係に従って分岐階層を判定する判定ステップと、前記分岐階層に対応する符号を出力する符号化ステップとを備えたことを特徴とする。
本願の第９の発明は、さらに、前記第７又は第８の発明において、前記複数の位置情報が、有理数で表現された有理数位置情報であって、前記所定の順序関係は、有理数の解像度の大小順に従って決めることを特徴とする。
本願の第１０の発明は、木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報を符号化する符号化方法であって、符号化する複数の位置情報に基づいて位置情報の値の増加幅を決める増加幅決定ステップと、前記増加幅を符号化して符号を出力する増加幅符号化ステップと、前記符号化する複数の位置情報の連続する２つの位置情報から、分岐階層を判定する判定ステップと、前記分岐階層に対応する符号を出力する分岐階層符号化ステップと、を有することを特徴とする。
本願の第１１の発明は、さらに、前記第１０の発明において、前記複数の位置情報が、有理数で表現された有理数位置情報であって、前記増加幅は、前記複数の位置情報が全て符号化可能となるように、前記分岐階層毎に決めることを特徴とする。
本願の第１２の発明は、さらに、前記第７乃至第１１のいずれか１の発明において、前記木構造が検索情報を表すものであり、前記符号化する複数の位置情報に対応する葉又は節が、前記検索情報に含まれる同種の要素に対応した葉又は節であることを特徴とする。
本願の第１３の発明は、木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報が符号化された位置情報符号列を復号する復号装置であって、復号された位置情報を逐次保持する保持手段と、前記位置情報符号に基づいて、連続する２つの位置情報の分岐階層を判定する判定手段と、前記保持手段で保持された位置情報に対して、前記分岐階層に対応する位置情報の値を所定の順序関係に従って１つ分増加させる復号手段とを備えたことを特徴とする。
本願の第１４の発明は、さらに、複数の前記復号された位置情報を、数値の大小順に従って並び替える並び替え手段を備えたことを特徴とする。
本願の第１５の発明は、さらに、前記第１４の発明において、前記並び替え手段が、前記復号された位置情報の各々に振られる、数値の大小順を表した連続番号を計算する計算手段を含むことを特徴とする。
本願の第１６の発明は、さらに、前記第１３乃至第１５のいずれか１の発明において、前記複数の位置情報が、有理数で表現された有理数位置情報であって、前記所定の順序関係は、有理数の解像度の大小順に従って決められていることを特徴とする。
本願の第１７の発明は、木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報が符号化された位置情報符号列を復号する復号装置であって、位置情報の値の増加幅を復号する増加幅復号手段と、復号された位置情報を逐次保持する保持手段と、前記位置情報符号に基づいて、連続する２つの位置情報の分岐階層を判定する判定手段と、前記保持手段で保持された位置情報に対して、前記分岐階層に対応する位置情報の値を前記増加幅分増加させる位置情報復号手段とを備えたことを特徴とする。
本願の第１８の発明は、さらに、前記第１３乃至第１７のいずれか１の発明において、前記木構造が検索情報を表すものであり、前記復号される位置情報に対応する葉又は節が、前記検索情報に含まれる同種の要素に対応した葉又は節であることを特徴とする。
本願の第１９の発明は、木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報が符号化された位置情報符号列を復号する復号方法であって、復号された位置情報を逐次保持する保持ステップと、前記位置情報符号に基づいて、連続する２つの位置情報の分岐階層を判定する判定ステップと、前記保持ステップで保持された位置情報に対して、前記分岐階層に対応する位置情報の値を所定の順序関係に従って１つ分増加させる復号ステップとを備えたことを特徴とする。
本願の第２０の発明は、さらに、前記第１９の発明において、複数の前記復号された位置情報を、数値の大小順に従って並び替える並び替えステップを備えたことを特徴とする。
本願の第２１の発明は、さらに、前記第２０の発明において、前記並び替えステップが、前記復号された位置情報の各々に振られる、数値の大小順を表した連続番号を計算する計算ステップを含むことを特徴とする。
本願の第２２の発明は、さらに、前記第１９乃至第２１のいずれか１の発明において、前記複数の位置情報が、有理数で表現された有理数位置情報であって、前記所定の順序関係は、有理数の解像度の大小順に従って決められていることを特徴とする。
本願の第２３の発明は、木構造中の同一の階層にある複数の葉及び／又は節に対応する複数の位置情報が符号化された位置情報符号列を復号する復号方法であって、位置情報の値の増加幅を復号する増加幅復号ステップと、復号された位置情報を逐次保持する保持ステップと、前記位置情報符号に基づいて、連続する２つの位置情報の分岐階層を判定する判定ステップと、前記保持ステップで保持された位置情報に対して、前記分岐階層に対応する位置情報の値を前記増加幅分増加させる位置情報復号ステップとを備えたことを特徴とする。
本願の第２４の発明は、さらに、前記第１９乃至第２３のいずれか１の発明において、前記木構造が検索情報を表すものであり、前記復号される位置情報に対応する葉又は節が、前記検索情報に含まれる同種の要素に対応した葉又は節であることを特徴とする。
本願の第２５の発明は、前記第１乃至第６のいずれか１の発明における符号化装置として、コンピュータを機能させるためのプログラムである。
本願の第２６の発明は、前記第７乃至第１２のいずれか１の発明における符号化方法をコンピュータに実行させるためのプログラムである。
本願の第２７の発明は、前記第１３乃至第１８のいずれか１の発明における復号装置として、コンピュータを機能させるためのプログラムである。
本願の第２８の発明は、前記第１９乃至第２４のいずれか１の発明における復号方法をコンピュータに実行させるためのプログラムである。
本願の第２９の発明は、前記第２５乃至第２８のいずれか１の発明におけるプログラムを記録したコンピュータ読み取り可能な記録媒体である。
本発明によれば、数値の大小順で見た場合にはその順序関係が一意に特定できない有理数表現された複数の位置情報について、予め決められる値どうしの新たな順序関係を設け、複数の位置情報をその順序関係に従って並べ替えることによって、整数表現による位置情報の場合と同様に差分符号化による複数位置情報の符号化／復号が可能である。また、並べ替え後において、符号化／復号する複数の位置情報が新たな順序関係に対して連番になっていない場合でも、欠落位置を表す情報を使って通知することにより、同様に差分符号化による複数位置情報の符号化／復号が可能である。
また、本発明によれば、数値の大小順で見た場合にはその順序関係が一意に特定できない有理数表現された複数の位置情報について、数値の大小順に見た時の値の増加幅を決め、符号化して位置情報の符号と共に与えることで、整数表現による位置情報の場合と同様に差分符号化による複数位置情報の符号化／復号が可能である。また、与えられた値の増加幅を用いて値を増加させた時に、本来無かった欠落位置が発生した場合でも、欠落位置を表す情報を使って通知することにより、同様に差分符号化による複数位置情報の符号化／復号が可能である。
【図面の簡単な説明】  図１は、本発明の第１の実施形態にかかる位置情報の符号化装置の概略構成を示す機能ブロック図である。
図２は、位置情報が有理数表現で与えられた木構造を有する検索情報の一例を示す図である。
図３は、本発明の第１の実施形態において、図２に示した検索情報の各データに対応する識別情報、該識別情報から抽出された位置情報、及び該位置情報を並べ替えた並べ替え後の位置情報を示す図である。
図４Ａは、本発明の第１の実施形態において、有理数表現された位置情報の値の順序関係を示す図である。
図４Ｂは、本発明の第１の実施形態において、図４Ａの順序関係の決定方法を示す図である。
図５は、本発明の第１の実施形態にかかる位置情報の符号化装置の一構成例で符号化される位置情報及び符号化された位置情報符号列の一例を示す図である。
図６は、本発明の第１の実施形態にかかる位置情報の符号化装置の一構成例で用いた位置情報符号を示す図であり、図５で用いた位置情報符号を示す図でもある。
図７は、位置情報が有理数表現で与えられた木構造を有する検索情報の別の例を示す図である。
図８は、本発明の第１の実施形態において、図７に示した検索情報の各データに対応する識別情報、該識別情報から抽出された位置情報、及び該位置情報を並べ替えた並べ替え後の位置情報を示す図である。
図９は、本発明の第１の実施形態にかかる位置情報の符号化装置の一構成例で符号化される位置情報及び符号化された位置情報符号列の別の例を示す図である。
図１０は、本発明の第１の実施形態にかかる位置情報の符号化方法を説明するためのフロー図である。
図１１は、本発明の第１の実施形態にかかる位置情報復号装置の概略構成を示す機能ブロック図である。
図１２は、本発明の第１の実施形態にかかる位置情報復号装置で、復号時の位置情報の並べ替え処理の一動作例を示した説明図である。
図１３は、本発明の第１の実施形態にかかる位置情報復号装置で、復号時の位置情報の並べ替え処理の機能構成を示した機能ブロック図である。
図１４は、本発明の第１の実施形態にかかる位置情報復号装置で、復号時の位置情報の並べ替え処理で扱う積算順情報の例を示した図である。
図１５は、本発明の第１の実施形態にかかる位置情報復号装置で、復号時の位置情報の並べ替え処理で扱う積算順情報の別の例を示した図である。
図１６は、本発明の第１の実施形態にかかる位置情報の復号方法を説明するためのフロー図である。
図１７は、本発明の第２の実施形態にかかる位置情報の符号化装置の概略構成を示す機能ブロック図である。
図１８は、本発明の第２の実施形態にかかる位置情報の符号化装置の一構成例で符号化される位置情報及び符号化された位置情報符号列の一例を示す図である。
図１９は、位置情報が有理数表現で与えられた木構造を有する検索情報の更に別の例を示す図である。
図２０は、本発明の第２の実施形態にかかる位置情報の符号化装置の一構成例で符号化される位置情報及び符号化された位置情報符号列の別の例を示す図である。
図２１は、本発明の第２の実施形態にかかる位置情報の符号化装置の一構成例で符号化される位置情報及び符号化された位置情報符号列の更に別の例を示す図である。
図２２は、本発明の第２の実施形態にかかる位置情報の符号化方法を説明するためのフロー図である。
図２３は、本発明の第２の実施形態にかかる位置情報復号装置の概略構成を示す機能ブロック図である。
図２４は、本発明の第２の実施形態にかかる位置情報の復号方法を説明するためのフロー図である。
図２５は、一般的な情報処理装置の構成例を示す図で、本発明にかかる装置を説明するための図である。
図２６は、従来技術による動画像コンテンツに対応して与えられた木構造を有する検索情報の一例を示す図である。
図２７は、従来技術によるＭＰＥＧ−７に従った位置情報の符号化装置の概略構成を示す機能ブロック図である。
図２８は、従来技術による位置情報の符号化装置で符号化される位置情報及び符号化された位置情報符号列の一例を示す図である。
図２９は、図２８で用いた位置情報符号を示す図である。
図３０は、従来技術による位置情報の復号装置の概略構成を示す機能ブロック図である
【発明を実施するための最良の形態】（第１の実施形態）
以下、本発明の第１の実施形態にかかる位置情報の符号化装置について、図１乃至図９を用いて説明する。
図１は、本発明の第１の実施形態にかかる位置情報符号化装置の概略構成を示す機能ブロック図である。
本発明の第１の実施形態にかかる位置情報符号化装置は、位置情報並替部１０１、先頭位置情報符号化部１０２、前位置情報保持部１０３、分岐階層判定部１０４、並びに差分位置情報符号化部１０５で構成される。上述のごとくＭＰＥＧ−７では、要素種別情報と位置情報とが個々に符号化されて、検索データと共に扱われるが、本発明は、このうち位置情報の符号化に関するものである。勿論、本発明にかかる符号化は、ＭＰＥＧ−７に限定されるものではない。なお、本発明としては、ここで説明する位置情報符号化を含む符号化を行う符号化装置としての形態も採り得る。
図２は、位置情報が有理数表現で与えられた木構造を有する検索情報の一例を示す図である。
本実施形態では、図２に示されたように、有理数表現されている木構造中の位置情報を符号化並びに復号する。なお、整数表現されている木構造中の位置情報に対しても、本発明にかかる符号化／復号装置及び方法が適用可能なことは言及するまでもない。図２は動画像コンテンツに対応する検索情報を表しており、動画像コンテンツ２１０が３つのシーンで構成され、各シーンが３つのショットで構成されて、かつ、それぞれのショットには動き強度を示す検索データが付加されているとしたものである。
図３は、本発明の第１の実施形態において、図２に示した検索情報の各データに対応する識別情報、該識別情報から抽出された位置情報、及び該位置情報を並べ替えた並べ替え後の位置情報を示す図である。図３では、図２の検索情報に含まれる各検索データ２０１〜２０９に対応する識別情報３０１と、それらの識別情報から抜き出した位置情報３０２とを示している。
本発明の符号化並びに復号が適用される位置情報は、図３に示されるように、同じ要素種別情報を持ち、位置情報のみが異なっている複数の識別情報の、それらに含まれる位置情報である。図２は動画像コンテンツの検索情報の一例であるが、実際の動画像コンテンツは、１つのシーンが複数のシーンへ、またそれら各々のシーンがさらに別の複数のシーンへと再帰的に分解されるなど、複雑な階層構造を持ち、それに伴って検索情報も複雑な階層構造を持つことが多い。またショットだけでなく、各シーンに対して、又は動画像コンテンツ全体に対して検索データが付されることもある。しかし、そのように複雑な階層構造を持った検索情報であっても、本発明の位置情報符号化並びに復号は同様に適用可能である。加えて、図３の例は、検索データ＝葉に対応する位置情報を抜き出したものであるが、これは節の場合でも全く同様である。即ち、検索情報に含まれる複数の検索データ＝葉、又は複数の節に対応して得られる複数の識別情報が、同じ要素種別情報からなり、位置情報のみが異なっているものであれば、本発明の位置情報符号化並びに復号を適用することができる。また、動画像コンテンツ以外の、音響コンテンツやテキストといった他のマルチメディアコンテンツに対する検索情報や、あるいは検索情報以外の情報であっても、木構造を持つ情報であれば原理的に適用可能である。
図１に示した本実施形態にかかる位置情報符号化装置の機能構成のうち、本発明の最も特徴となる機能構成は、符号化を行う前段に設けた位置情報並替部１０１である。以下、位置情報並替部１０１の処理について説明する。
符号化しようとする各位置情報が有理数表現になることによって、従来例に示した差分符号化による位置情報符号化ができなくなる理由は、位置情報が有理数になることによって、ある１つの位置情報の値から見た時に、それに続く次の位置情報の値が一意に決定できなくなることにある。整数表現であれば、０の次は１、１の次は２、と次の位置情報の値が一意に決まる。一方、有理数表現では、例えば、位置情報１／４の次に来る位置情報は１／２であることもあれば３／８である場合もあり、あるいは５／１６であるかもしれない。
図４Ａ及び図４Ｂは、本発明の第１の実施形態において、有理数表現された位置情報の値の順序関係、及びその決定方法を示す図である。
本発明では、この問題を解決するために、有理数で表された位置情報の値に対して、予め決められる順序関係を設ける。この例では、「２のべき乗分の自然数（分母が２のべき乗数、分子が自然数）」で表される有理数の位置情報を扱い、その位置情報の値の順序関係を、「１／２→１／４→３／４→１／８→３／８→５／８→７／８→１／１６→・・・」（図４Ａを参照）のように定義した。
この順序付けは、図４Ｂに示すように、０を超え１未満の「２のべき乗分の自然数」について、解像度が低いものから解像度が高いものへと先に順序付けを行い（ｉ）、さらに同一の解像度内では値の大小に従い小さい値から大きい値へと順序付けを行った（ｉｉ）ものである。ここで言う有理数、「２のべき乗分の自然数」に対する解像度とは、その値域０〜１を半分、更にその半分、と順に分割して有理数を求めていった時の分割数に当り、少ない分割数で現れる値ほど解像度が低く、逆に分割を多く繰り返すことで現れる値が解像度の高い有理数ということになる。もっと端的に言えば、分母になる２のべき乗数の値の大きさが解像度と対応している。このように定義することで、初期値１／２から始まり解像度が高い有理数値へと一意に順序付けが行われ、数値的な大小関係だけでは未定とされていた個々の有理数値に対して、次に続くべき値が明確に規定されることとなる。
位置情報並替部１０１は、こうして規定された新たな順序関係、図４Ａに従って、それぞれの位置情報を並べ替える。この順序関係、図４Ａに従って、図３の位置情報３０２について並べ替えを行ったのが、同じく図３に示した並べ替え後の位置情報３０３である。並べ替えは、それぞれの階層に付された位置情報の値に基づき、上位の階層から、その階層の値について図４Ａの順に従って並ぶように位置情報を並べ替え、その階層での位置情報の値が同一であるものについては、階層を１つ下ってまた図４Ａの順に従って並べ替える、という操作を再帰的に繰り返すことでなされる。あるいは、階層毎に位置情報の値を比較するのでなく、葉又は節におけるすべての階層の位置情報の値をまとめて扱うことによって位置情報の並べ替えを行ってもよい。例えば、ある葉又は節の位置情報と、別の葉又は節の位置情報との大小関係を定義し、その大小関係に従って、葉又は節の位置情報に対して、クイックソート等の既存のソートアルゴリズムを適用することによって位置情報の並べ替えを行うことができる。無論、同様の並べ替えが実行できる並べ替え方法であればよく、並べ替えの方法はここに示したものに限定されるものではない。
また、本実施形態では、位置情報が全て抜き出されて数値の大小順に従って並べられた状態をつくり、その後でそれらの位置情報を並べ替えるとしているが、位置情報並替部１０１が行う並べ替え処理は、必ずしもそのような段階を踏んだ処理である必要はない。例えば、位置情報を抜き出してくる段階で、あるいはそれ以前に、まとめて扱うべき検索データを選択し抜き出してくる段階において、図４Ａに従った順序で逐次それらを抜き出してくるといった処理も可能である。このような処理も広く位置情報並替部１０１で行う並べ替え処理の一種であると考えてよい。
位置情報並替部１０１で位置情報を並べ替えた以降は、従来の整数表現された位置情報の符号化と同様の処理で、差分符号化を実行する。先頭位置情報符号化部１０２は、並べ替え後の位置情報における先頭の位置情報を、差分を用いない通常の方式で符号化する。この先頭の位置情報はまた、前位置情報保持部１０３に記録され、次の位置情報の符号化で利用される。
図５は、本発明の第１の実施形態にかかる位置情報の符号化装置の一構成例で符号化される位置情報及び符号化された位置情報符号列の一例を示す図である。
図５に示す、図３に示したのと同一の並べ替え後の位置情報と、それらを符号化して得られる位置情報符号化列とに基づいて、動作を説明する。
始めに、並べ替えられた後の先頭の位置情報（１／２，１／２）については、差分符号化を行うために必要な前位置の情報が無いため、通常の方式で符号化する。図５では、１変数あたり５ビットとし、５ビット×２＝１０ビットで符号化して与えている。本発明では、この先頭の位置情報に関する符号化方式については特に言及しない。
前位置情報保持部１０３は、１つ前に処理された位置情報を記録し、次の位置情報の符号化を行う際に出力して提供する。図５で、（１／２，１／２）の次に符号化される位置情報は（１／２，１／４）である。即ち、（１／２，１／４）を符号化する際には、前位置情報保持部１０３には位置情報（１／２，１／２）が記録され保持されている。
分岐階層判定部１０４は、入力されてきた位置情報と、前位置情報保持部１０３に保持されている位置情報とを比較し、両者がどの階層で分岐したかを判定して、その判定結果を差分位置情報符号化部１０５へ出力する。そして、差分位置情報符号化部１０５は、分岐階層判定部１０４から出力された判定結果に基づいて、分岐階層に対応した位置情報符号を出力する。
分岐階層とは、木構造で見た場合に、入力されてきた位置情報及び前位置情報保持部１０３に保存されている位置情報の２つの位置情報について、対応する検索情報の木を根から葉に向けてそれぞれ辿ったときに、枝分かれして初めて異なる節又は葉に分かれる、その節又は葉の階層を指す。もっと端的に言えば、図５のように、位置情報の値を上位の階層から下位の階層へと順に見ていき、位置情報の値が最初に変化する階層を指す。
例えば、入力されてきた位置情報が（１／２，１／４）で前位置情報保持部１０３に記録されているのが（１／２，１／２）の場合、それらは第１階層については値が等しく、第２階層で初めて値が異なっている。このことから、それらは第２階層、即ちショットの階層で分岐が発生しており、それより上の階層、即ちシーンの階層は同一であることがわかる。従ってこの場合には、分岐階層判定部１０４は、第２階層を示す情報を判定結果として出力する。
ここで、さらに正確には、分岐した階層の位置情報、ここではショットの階層の位置情報が１／２から１／４に、図４Ａの順序関係からみて正しく１つ分だけ更新されていることを確かめる必要がある。この結果、更新が正しくなかった場合については、後述する図７乃至図９と共に示す別の例の中で説明する。
また、入力されてきた位置情報が（１／４，１／２）で、前位置情報保持部１０３には位置情報（１／２，３／４）が記録されている場合には、それら２つの位置情報は第１階層で既に値が異なっている。このことから、それらは第１階層、すなわちシーンの階層で分岐が発生していることがわかるので、第１階層を示す情報を判定結果として出力する。
ここで、さらに正確には、分岐した階層の位置情報、ここではシーンの階層の位置情報が１／２から１／４に、図４Ａの順序関係からみて正しく１つ分だけ更新されていることを確かめる必要がある。またこの場合では、シーンの階層で分岐が起こっているため、それより下位の階層、すなわちショットの階層の位置情報が、初期値１／２になっているかを確かめる必要がある。このことは、上位の階層で分岐が起こったため、つまり違う節に移ったために、その違う節を起点とする下位の階層には本来、初期値から始まる新たな位置情報が節又は葉に付されるべきであることが前提となっている。この、ショットの階層の位置情報が初期値１／２以外の値であった場合の処理についても、後述する図７乃至図９と共に示す別の例の中で説明する。
差分位置情報符号化部１０５は、分岐階層判定部１０４から出力される判定結果に基づいて、分岐階層に対応する位置情報符号を出力する。図５で、符号化する位置情報が（１／２，１／４）で前位置情報が（１／２，１／２）の場合、分岐階層判定部１０４の判定結果を受けて、差分位置情報符号化部１０５は、分岐階層が第２階層であることを示す位置情報符号“１０”を出力する。この位置情報符号“１０”は、復号の際に、第２階層が分岐階層であることから、第２階層の位置情報の値を図４Ａの順序関係に従って１つ分増加させることを意味する符号である。あるいは、符号化する位置情報が（１／４，１／２）で前位置情報が（１／２，３／４）の場合には、分岐階層判定部１０４の判定結果を受けて、差分位置情報符号化部１０５は、分岐階層が第１階層であることを示す位置情報符号“０１”を出力する。この位置情報符号“０１”は、復号の際に、第１階層が分岐階層であることから、第１階層の位置情報の値を図４Ａの順序関係に従って１つ分増加させると共に、第１階層より下の階層、本例では第２階層、の位置情報の値を図４Ａの順序関係における初期値１／２とすることを意味する符号である。
図６は、本発明の第１の実施形態にかかる位置情報の符号化装置の一構成例で用いた位置情報符号を示す図であり、図５で用いた位置情報符号を示す図でもある。
図６に例示する位置情報符号は、符号化された位置情報とその前に処理された位置情報との各々に対応した木がどの階層で分岐したかを表す符号であり、その符号のビット長は、木構造中の分岐可能な階層の数によって決められる。検索データに付される識別情報として見た場合には、識別情報に含まれる位置情報の数、即ち位置情報を取り得る検索情報の要素の数が分岐可能な階層数にあたる。
検索データの識別情報に含まれた位置情報の符号化では、位置情報の符号化と共に、要素種別情報も符号化されて、符号化された位置情報と共に蓄積又は伝送されるのが普通である。そのため、この要素種別情報を参照することで、符号化側、復号側共に分岐可能な階層数を知ることができ、特に符号のビット長を通知しなくても符号化側、復号側共に符号のビット長を知ることができる。一方、分岐可能な階層数を示す上記要素種別情報のような情報が付随しない位置情報を符号化する場合には、符号のビット長を示す情報を生成して符号化された位置情報と共に蓄積又は伝送するとしてもよい。なお、上述の符号のビット長の決定は、図１に示した符号化装置における符号化処理とは別途行うため、図示していない。
図３の識別情報３０１の場合、分岐可能な階層数（位置情報を持った要素数）は２であり、符号のビット長は、＜階層数＞２＋＜欠落符号＞１＋＜終了符号＞１＝４を表現可能な最小ビット長、即ち２ビットの符号として与えられる。
欠落符号“００”は、位置情報に欠落があることを示す特殊符号である。検索データに対応する識別情報中の位置情報として見た場合、実際に欠落符号によって示されるのは、欠落符号の後に続く位置情報符号で更新させた位置に、対応する検索データが無いということである。このことは、後述の図７乃至図９と共に示す例の中で詳しく説明する。
符号化する最後の位置情報、すなわち図５では位置情報（３／４，３／４）を符号化して出力した後は、位置情報がこれ以上無いことを示す終了符号“１１”を出力し、符号化を終了する。
この例では、木に含まれるデータ２０１〜２０９の全ての位置情報について符号化したが、必ずしも木に含まれる全ての位置情報を符号化するとは限らない。木構造の任意の一部を切り出して符号化することも可能である。木構造における時間的に後の位置情報だけを切り出して符号化する場合、例えば図２で第１のシーンに含まれる位置情報を除いて第２、第３のシーンのみで符号化したい場合には、先頭の位置情報を第２のシーンの先頭に変えればよい。木構造における時間的に前の位置情報だけを符号化する場合、例えば図２で第３のシーンに含まれる位置情報を除いて第１、第２のシーンのみで符号化する場合には、第１、第２のシーンに含まれる位置情報を符号化した時点で終了符号を加え、符号化を終了すればよい。木構造の時間的に真中の一部を切り出す場合には、それらを組合せればよい。これら変更される符号化の先頭位置や終了符号により強制終了される符号化の終了位置は、木構造中の任意の位置とすることが可能である。
次に、欠落がある場合の木構造の位置情報符号化について、図７乃至図９を例として説明する。
図７は、位置情報が有理数表現で与えられた木構造を有する検索情報の別の例を示す図、図８は、本発明の第１の実施形態において、図７に示した検索情報の各データに対応する識別情報、該識別情報から抽出された位置情報、及び該位置情報を並べ替えた並べ替え後の位置情報を示す図である。また、図９は、本発明の第１の実施形態にかかる位置情報の符号化装置の一構成例で符号化される位置情報及び符号化された位置情報符号列の別の例を示す図である。
ここでは、図７の動画像コンテンツ７１０に対応する検索情報に含まれるデータ７０１〜７０７の位置情報について符号化する。図７の検索情報は、位置情報（１／２，１２／４）及び（３／４，１／２）に対応するショットに動き強度を表す検索データが付されていない、即ち欠落のある検索情報の例である。図３に示した例と同様に、図８には、データ７０１〜７０７に対応する識別情報８０１と、それらの識別情報から抜き出した位置情報８０２、及びそれらの位置情報を図４Ａの順序関係に従って並べ替えた後の位置情報８０３とを示している。さらに図９には、図８と同一の並べ替え後の位置情報と、生成される位置情報符号列とを示している。
図９で、位置情報（１／２，３／４）を符号化する際の動作を説明する。
（１／２，３／４）が分岐階層判定部１０４に入力されてきた時点では、前位置情報保持部１０３にはその前段で処理された位置情報（１／２，１／２）が保持されている。そして、この前位置情報に基づいて、分岐階層を判定する。
（１／２，１／２）と（１／２，３／４）とでは、第１階層の値が同一であり、第２階層で値が異なるため、第２階層で分岐が起こっていることが判る。但しここで、第２階層の位置情報の値が図４Ａに従って１つ分だけ更新されているかを判定すると、１／２の次に来る値は図４Ａの順序関係では１／４であるのに対し、入力された位置情報は３／４であるために、位置の抜け、即ち欠落があることが判る。そこで、分岐階層判定部１０４は、分岐階層が第２階層であることを示す情報と共に、欠落があることを示す情報を差分位置情報符号化部１０５に対し出力する。同時に、分岐階層判定部１０４では、欠落が無いと仮定した時の（１／２，１／２）の次の位置情報（１／２，１／４）を生成して、前位置情報保持部１０３に送り記録する。この状態から、再度位置情報（１／２，３／４）の符号化を行う。
差分位置情報符号化部１０５では、分岐階層判定部１０４から受け取った判定結果、即ち、欠落があること、分岐階層が第２階層であることを受けて、対応する欠落符号“００”及び位置情報符号“１０”を出力する。
再度（１／２，３／４）が符号化される時点で前位置情報保持部１０３に記録されているのは、分岐階層判定部１０４で生成された（１／２，１／４）である。（１／２，１／４）と（１／２，３／４）とでは、第１階層の値が同一であり、第２階層で値が異なるため、第２階層で分岐が起こっていることが判る。さらに、第２階層の位置情報の値は１／４から３／４へとなっているため、図４Ａに従って正しく１つ分だけ更新されていることが判る。このため、分岐階層判定部１０４からは分岐階層が第２階層であることを示す情報のみが差分位置情報符号化部１０５に送られる。差分位置情報符号化部１０５では、分岐階層判定部１０４からの判定結果に基づき、第２階層を示す位置情報符号“１０”が出力される。
また、図９で、位置情報（３／４，１／４）を符号化する際の動作を説明する。
（３／４，１／４）が分岐階層判定部１０４に入力されてきた時点では、前位置情報保持部１０３にはその前段で処理された位置情報（１／４，３／４）が保持されている。
（１／４，３／４）と（３／４，１／４）とでは、第１階層で既に値が異なるため、第１階層で分岐が起こっていることが判る。ここで、第１階層の位置情報は、１／４から３／４へと、図４Ａに従って正しく１つ分だけ更新されていることが判る。次にここで、第２階層の位置情報の値が図４Ａに従い初期値１／２になっているかを判定すると、入力された位置情報は１／４であるために、位置の抜け、即ち欠落があることが判る。そこで、分岐階層判定部１０４は、分岐階層が第１階層であることを示す情報と共に、欠落があることを示す情報を差分位置情報符号化部１０５に対し出力する。同時に、分岐階層判定部１０４では、欠落が無いと仮定した時の位置情報（３／４，１／２）を生成して、前位置情報保持部１０３に送り記録する。この状態から、再度位置情報（３／４，１／４）の符号化を行う。
差分位置情報符号化部１０５では、分岐階層判定部１０４から受け取った判定結果、即ち、欠落があること、分岐階層が第１階層であることを受けて、対応する欠落符号“００”及び位置情報符号“０１”を出力する。
再度（３／４，１／４）が符号化される時点で前位置情報保持部１０３に記録されているのは、分岐階層判定部１０４で生成された（３／４，１／２）である。（３／４，１／２）と（３／４，１／４）とでは、第１階層の値が同一であり、第２階層で値が異なるため、第２階層で分岐が起こっていることが判る。さらに、第２階層の位置情報の値は、１／２から１／４へ、図４Ａに従って正しく１つ分だけ更新されていることが判る。このため、分岐階層判定部１０４からは分岐階層が第２階層であることを示す情報が差分位置情報符号化部１０５に送られる。差分位置情報符号化部１０５では、分岐階層判定部１０４からの判定結果に基づき、第２階層を示す位置情報符号“１０”が出力される。
このようにして、欠落がある木構造の位置情報であっても差分符号化することができる。さらに、この欠落符号を能動的に使うことで、木構造を有する検索情報に含まれている同種の検索データを任意に取捨選択した上でグループ化することや、一部をトリミングした上で伝送する、記録するといった操作が可能である。
図１０は、本発明の第１の実施形態にかかる位置情報の符号化方法を説明するためのフロー図である。
本発明の第１の実施形態にかかる位置情報符号化方法は、位置情報並替ステップ（ステップＳ１）、先頭位置情報符号化ステップ（ステップＳ２）、前位置情報保持ステップ（ステップＳ３）、分岐階層判定ステップ（ステップＳ６）、並びに差分位置情報符号化ステップ（ステップＳ８）を含んでなる。本発明の第１の実施形態にかかる符号化方法も、位置情報の符号化に関するものであり、本発明としては、ここで説明する位置情報符号化を含む符号化を行う符号化方法としての形態も採り得る。
始めに、符号化する複数の位置情報を、図４Ａに示した順序関係に従って並べ替える（ステップＳ１）。次に、並べ替えた後の先頭の位置情報を通常の方式で符号化する（ステップＳ２）。それと同時に、先頭の位置情報は、次の位置情報を符号化するための前位置情報として保持される（ステップＳ３）。
符号化すべき次の位置情報があるか否かを判定する（ステップＳ４）。ある場合には、その符号化すべき位置情報を読み込む（ステップＳ５）。読み込まれた符号化すべき位置情報と、保持されている前位置情報とを比較し、分岐階層を判定する（ステップＳ６）。この時、この２つの位置情報の間に欠落があるか否かを判定する（ステップＳ７）。欠落の判定方法については、既に符号化装置で説明したように、位置情報が図４Ａの順序関係に従っているか否かにより判定される。
欠落が無ければ、分岐階層に対応する位置情報符号を出力し（ステップＳ８）、符号化が済んだ位置情報を再び前位置情報として保持し（ステップＳ３）、同様の処理を続ける。
欠落がある場合には、まず欠落符号を出力した（ステップＳ９）後に、分岐階層に対応する位置情報符号を出力する（ステップＳ８）。次に、前位置情報として保持された位置情報から、欠落が無いと仮定した場合に得られる次の位置情報を生成し、その欠落位置情報を前位置情報として保持する（ステップＳ１０）。その後、再び、前位置情報と既に読み込まれている符号化すべき位置情報とで分岐階層を判定する（ステップＳ６）。即ち、処理される符号化すべき位置情報は、欠落があると判定された場合には再び同じ位置情報を符号化することになる。以降、同様に欠落の有無が判定され、欠落があれば欠落符号の出力（ステップＳ９）以降の処理を、欠落が無いと判定された場合には位置情報符号を出力した（ステップＳ８）後、この符号化済の位置情報を前位置情報として（ステップＳ３）符号化を続ける。
符号化すべき次の位置情報が無いと判定されたら（ステップＳ４）、終了符号を出力し（ステップＳ１１）、符号化を終了する。
なお、以上の説明から、本発明の第１の実施形態にかかる符号化装置及び方法で有理数表現の位置情報を符号化した際に最も符号化効率が高くなるのは、位置情報の欠落が全く無い場合、即ち、符号化する複数の有理数表現された位置情報の値が予め決められた有理数の順序関係、図４Ａの順序関係に従って連続して与えられている場合である。このことから、逆に、図４Ａに示すような予め決められた有理数の順序関係を、複数の、同じ要素種別情報を持った検索データ（葉又は節）に位置情報を割り当てる際に用いることが考えられる。
これから位置情報を与えようとする、複数の、同じ要素種別情報を持った検索データ（葉又は節）の個数をＭ個とした時、図４Ａの順序関係に従って先頭からＭ個の値を選び、それらを数値の大小順に並び替えて、それぞれの検索データの位置情報として割り当てる。例えば、これから位置情報を与えようとする、複数の、同じ要素種別情報を持った検索データ（葉又は節）が５個である場合、図４Ａの順序関係に従って先頭からの５個、１／２，１／４，３／４，１／８，３／８が選ばれ、これらを数値の大小順、１／８，１／４，３／８，１／２，３／４に並び替えて、それぞれの検索データに対応する位置情報の値として割り当てる。
それぞれの有理数値が個々に符号化される場合、概して、解像度の低い有理数値（分母の値が小さい有理数値）ほど短い符号で符号化される。このことから、図４Ａのような順序関係を用いた有理数位置情報の値の割り当ては、本発明の実施形態のように複数の位置情報をまとめて差分符号化する以外にも、検索データ（葉又は節）に付される有理数位置情報をそれぞれ別個に符号化した際、位置情報にかかる符号の符号長が全体で最小となる、という効果がある。
あるいは、図４Ａの順序関係に従った位置情報の割り当ては、以下のような処理を行うことでも同様に実現される。
まず、割り当てようとする位置情報の個数Ｍから、その個数を表すために必要な最低解像度（最小の分母値）Ｎを決定する。図４Ａの例では、Ｎは２のべき乗数であり、また解像度Ｎで表される位置情報は１／Ｎから（Ｎ−１）／ＮまでのＮ−１個であるため、Ｍ＜＝Ｎ−１を満たす最小の２のべき乗数が求めるＮとなる。ここで、Ｍ＝Ｎ−１の時は、１／Ｎから（Ｎ−１）／Ｎまでの値をＭ個の位置情報に割り当て、処理を終了する。
Ｍ＝Ｎ−１でない場合には、次に、その解像度Ｎの更に１つ低い解像度Ｎ’を求め、差分数Ｍ’＝Ｍ−（Ｎ’−１）を計算する。Ｎ’−１は解像度Ｎ’で表される位置情報の個数である。即ち、この差分数Ｍ’は、割り当てようとするＭ個の位置情報のうち、解像度Ｎ’では表せない位置情報の個数、即ち、分母がＮとなる位置情報の個数を表す。よって、Ｍ個の位置情報は、解像度Ｎ’で表されるＮ’−１個の値、ｎ／Ｎ’（ここでｎ＝１，２，・・・，Ｎ’−１）と、分母がＮの位置情報のうち小さい方からＭ’個の値、ｎ／Ｎ（ここでｎ＝１，３，・・・，２Ｍ’−１）とを合わせたものとなる。今、Ｎは２のべき乗数であるから、分母がＮの位置情報の分子は、通分できない値、即ち奇数となっている。
図４Ｂを見ると、これらの値の大小関係は、小さい方から、１／Ｎ，１／Ｎ’（即ち２／Ｎ），３／Ｎ，２／Ｎ’（即ち４／Ｎ），・・・，（Ｍ’−１）／Ｎ’（即ち（２Ｍ’−２）／Ｎ），（２Ｍ’−１）／Ｎ，Ｍ’／Ｎ’（即ち２Ｍ’／Ｎ），（Ｍ’＋１）／Ｎ’，（Ｍ’＋２）／Ｎ’，・・・，（Ｎ’−１）／Ｎ’であることが判る。即ち、これらの値は、１／Ｎから始まって１／Ｎずつ増えていくＭ’／Ｎ’（即ち２Ｍ’／Ｎ）までの２Ｍ’個の値と、そこから１／Ｎ’ずつ増えていく残り（Ｎ’−１）／Ｎ’までのＭ−２Ｍ’個の値からなっている。これらの値の増加幅１／Ｎ，１／Ｎ’を「ステップ幅」と呼ぶ。そこで、１／Ｎを初期値として、ステップ幅１／Ｎずつ加えていくことで先頭から２Ｍ’個の値を求め、更にそこからステップ幅１／Ｎ’ずつ加えていき、残りの値を個数Ｍ個になるまで求めることによって、図４Ａの順序関係に従う先頭からＭ個の位置情報の値を求めることができる。例えば、これから位置情報を与えようとする、複数の、同じ要素種別情報を持った検索データ（葉又は節）が５個である場合、解像度Ｎ＝８、解像度Ｎ’＝４、差分数Ｍ’＝２となり、１／８を初期値として２Ｍ’＝４個の値、１／８，１／４，３／８，１／２が求まり、そこから１／４を加えることで５個目の値３／４が求まる。
つまり、この方法は、２つのステップ幅１／Ｎ，１／Ｎ’と、そのステップ幅を切り換える所定の位置２Ｍ’を与えることで、図４Ａの順序関係で先頭からＭ個の位置情報の値を、数値の大小順のままで求めるものである。この方法では、得られた位置情報の値を後から数値の大小順に並べ替える動作が不要になるため、図４Ａの順序関係に従った位置情報の値の割り当てを高速に行うことができる。また、ステップ幅の切り換え位置を指定するＭ’の値に上記で得られた差分数よりも大きな値を設定することで、割り当てられる位置情報の値を小さい値の方に偏らせたりすることもできる。但しこの時、２Ｍ’は個数Ｍを越えない。
次に、本発明の第１の実施形態にかかる位置情報の復号装置について、図１１を用いて説明する。
図１１は、本発明の第１の実施形態にかかる位置情報復号装置の概略構成を示す機能ブロック図である。
本発明の第１の実施形態にかかる位置情報復号装置は、先頭位置情報復号部１１０１、前位置情報保持部１１０２、分岐階層判定部１１０３、差分位置情報復号部１１０４、並びに位置情報並替部１１０５で構成される。上述のごとくＭＰＥＧ−７では、要素種別情報と位置情報とが個々に符号化されて、検索データと共に扱われるが、本発明は、このうち位置情報の復号に関するものである。勿論、本発明にかかる復号は、ＭＰＥＧ−７に限定されるものではない。なお、本発明としては、ここで説明する位置情報復号を含む復号を行う復号装置としての形態も採り得る。
図１１に示した本実施形態にかかる位置情報復号装置の機能構成のうち、本発明の最も特徴となる機能構成は、位置情報の復号を行った後段に設けられた位置情報並替部１１０５である。
位置情報並替部１１０５は、前段の差分位置情報復号部１１０４までに復号されて得られた、図４Ａの順序関係に従って並んだ有理数表現の位置情報を、元の数値の大小に基づく順に並べ替えるものである。本明細中に示したように、扱われるのが検索情報に含まれる各検索データ（あるいは節）に対応した位置情報の場合、検索データ（あるいは節）は元の木構造に含まれたままの順に並んだ状態で扱うことが多く、またその方が扱い易いと考えられるため、上記のように対応する位置情報を元の順に並び替える必要がある。
位置情報並替部１１０５で位置情報を並べ替える前段までに行われる復号処理は、従来の整数表現された位置情報での復号の処理と同様である。位置情報並替部１１０５の動作については後で詳しく脱明する。
始めに、先頭位置情報復号部１１０１は、先頭の位置情報を復号し、その位置情報を出力する。ここで行われるのは通常の方式で符号化された位置情報の復号であり、符号化同様、この動作については本発明では特に言及しない。
本実施形態の位置情報復号装置の動作を、図５に示した位置情報符号列を入力とした場合で説明する。図５の位置情報符号列は、上述した図１の位置情報符号化装置により図２に示した検索情報に含まれる各検索データ２０１〜２０９の位置情報を符号化して得られたものであるが、本実施形態の復号装置で復号される位置情報符号列は特に図１の符号化装置で生成される符号列に限定されるものではない。
先頭位置情報復号部１１０１で復号されて得られた先頭の位置情報（１／２，１／２）は、位置情報並替部１１０５に入力されると共に、前位置情報保持部１１０２に記録されて保持される。前位置情報保持部１１０２には、現在復号しようとする位置情報に対して、１つ前に復号処理された位置情報が記録され保持されている。
分岐階層判定部１１０３は、入力される位置情報符号列の１つ１つの位置情報符号を順次読み込み、分岐階層を判定、即ちどの階層の位置情報の値を更新させるかを判定し、判定結果を差分位置情報復号部１１０４に送る。なお、分岐階層判定部１１０３で順次読み込むべき位置情報符号のビット長は、位置情報の階層数によって決まるものである。符号化装置の説明でも述べたように、検索データの識別情報に含まれた位置情報の復号では、符号化された位置情報、即ち位置情報符号列と共に、要素種別情報が符号化されて共に蓄積又は伝送されているのが普通である。そこで、この要素種別情報を復号し解析して分岐可能な要素数を求めることで、位置情報の階層数を知り、読み込む位置情報符号のビット長を知ることができる。あるいはビット長を示す情報が別途位置情報符号列と共に与えられているような場合には、その情報を用いて読み込む位置情報符号のビット長を知ることができる。これらビット長の判定処理は、図１１に示した復号装置における復号処理とは別途行われるため、図示していない。
差分位置情報復号部１１０４は、前位置情報保持部１１０２に保持されている位置情報を読み込み、分岐階層判定部１１０３からの判定結果に基づいて、位置情報の値を、図４Ａの順序関係に従って更新する。即ち、差分位置情報復号部１１０４は、前位置情報保持部１１０２に記録されている位置情報に対して、分岐階層判定部１１０３の判定結果に基づき分岐階層の位置情報の値を図４Ａの順序関係に従って１つ分増加させ、かつその分岐階層より下位にある階層については、全ての階層の位置情報の値を図４Ａの順序関係における初期値１／２とする。その分岐階層より上位の階層の位置情報の値はそのまま保持する。
（１／２，１／２）が先頭位置情報復号部１１０１で復号され、前位置情報保持部１１０２に記録されている状態で、次に読み込まれる位置情報符号は“１０”である。分岐階層判定部１１０３では、この符号“１０”が第２階層、即ちショットの階層で分岐があることを示す符号であることを判定し、差分位置情報復号部１１０４では、その判定結果に基づいて第２階層＝ショットの階層の位置情報の値を図４Ａの順序関係に従い１つ分更新する。図４Ａにおいて１／２の次の値は１／４であるため、（１／２，１／２）から第２階層の位置情報の値を更新した位置（１／２，１／４）が得られる。
また、（１／２，３／４）が前位置情報保持部１１０２に記録されている状態で、次に位置情報符号“０１”が読み込まれる。分岐階層判定部１１０３では、この符号“０１”が第１階層、即ちシーンの階層で分岐があることを示す符号であることを判定し、差分位置情報復号部１１０４では、その判定結果に基づいて第１階層＝シーンの階層の位置情報の値を図４Ａの順序関係に従って１つ分更新する。それと共に、それより下位の階層、即ち第２階層＝ショットの階層の位置情報の値を、図４Ａの順序関係での初期値１／２とする。図４Ａにおいて１／２の次の値は１／４であるため、（１／２，３／４）から第１及び第２階層の位置情報の値を更新した位置（１／４，１／２）が得られる。
そして、差分位置情報復号部１１０４で得られた位置情報は、位置情報並替部１１０５へと出力されると共に、前位置情報保持部１１０２へと送られ記録されて、次の位置情報の復号に利用される。
分岐階層判定部１１０３で終了符号“１１”が読み込まれたら、位置情報の復号を終了し、引き続き位置情報並替部１１０５で位置情報の並べ替えを行う。
位置情報並替部１１０５では、差分位置情報復号部１１０４で復号され出力された有理数表現の位置情報が、図４Ａの順序関係に従って並んでいることから、本来の数値の大小による順序関係に従った順へと位置情報の並べ替えを行う。ここで例示した図５の位置情報符号列を復号した例では、既に示した図３の並べ変え後の位置情報３０３から、並べ替え前の位置情報３０２の順へと並べ替えが行われることになる。並べ替えは、上位の階層から順に、その階層での位置情報の値が数値の大小順になるように位置情報を並べ替え、その階層での位置情報の値が同一であるものについては、階層を１つ下ってまた数値の大小順に並べ替える、という操作を再帰的に繰り返すことでなされる。この操作は、上記の符号化装置で位置情報を図４Ａに従った順に並べ替えた時の操作と同じである。あるいは、階層毎に位置情報の値を比較するのではなく、葉又は節におけるすべての階層の位置情報の値をまとめて扱うことによって位置情報の並べ替えを行ってもよい。例えば、ある葉又は節の位置情報と、別の葉又は節の位置情報との大小関係を定義し、その大小関係に従って、葉又は節の位置情報に対して、クイックソート等の既存のソートアルゴリズムを適用することによって位置情報の並べ替えを行うことができる。無論、同様の並べ替えが行える並べ替え方法であればよく、並べ替えの方法はここに示したものに限定されるものではない。
ここで、並べ替え方法の一例として、差分位置情報復号部１１０４から出力される有理数表現された位置情報の値並びに出力順が図４Ａの順序関係に従っていることを利用した復号時の位置情報の並べ替え処理を、図１２乃至図１５と共に説明する。
図１２は、ここで説明する復号時の並べ替え処理の一動作例を図示した説明図である。この並べ替え処理は位置情報並替部１１０５の内部で行われる。
図１２中、１２０１は差分位置情報復号部１１０４で復号され出力された１０個の位置情報（分岐可能な階層数は３）を示しており、これらは上から、復号された順、即ち図４Ａの順序関係に従った順に並んでいる。
図１２に示した並べ替え処理では、これら復号された位置情報のそれぞれに、数値の大小順を表す（０から始まる）連続した番号を最終的に振る。この番号を「インデックス」と呼ぶ（図１２中の１２０３を参照）。位置情報のそれぞれに対しインデックスが振られれば、その値に従って位置情報を並べ替えることができる。このため、位置情報並替部１１０５の内部構成として、図１３に代表されるインデックスの計算部が用意される。図１２では並べ替えを行う位置情報１２０１の数が１０個のため、与えられるインデックス１２０３の値は０から９までとなっているが、位置情報の数に合わせて、例えば１５個の場合は０から１４まで、３０個の場合は０から２９までのインデックスが振られる。これら各位置情報に振られるインデックスの値は、以下のようにして求められる。
図１３は、それぞれの位置情報に付されるインデックスの値を計算するために、ある階層のある１つの分岐位置で行う処理を、装置の機能構成として表した機能ブロック図である。即ち図１３は、位置情報並替部１１０５の内部構成となるインデックス計算部の、更に内部構成を表した例である。図１３の処理は、位置情報計数部１３０１、更新幅算出部１３０２、インデックス値更新部１３０３の３つで構成され、復号された位置情報と、１つ上の階層で処理された計数値並びにインデックス値を入力として、新たな計数値及び更新されたインデックス値を出力する。また、更新幅算出部１３０２には別途、積算順情報１３０４が入力される。この処理を全階層の全分岐位置に対し行うことで、各位置情報に対応したインデックスが得られる。
位置情報計数部１３０１は、復号された位置情報と１つ上の階層での計数値を入力とし、ある階層のある分岐位置において、その階層の位置情報の値が同じになっている位置情報の個数を、それぞれの値について計数する。図１２の１２０２が計数結果の例を示している。但し、計数結果１２０２には全ての階層及び分岐位置での計数結果を示してある。
例えば、第１階層（の分岐位置）では、１０個の位置情報のうち、第１階層で値１／２をとる位置情報が６個、値１／４をとる位置情報が４個あることを計数する。また、第２階層の第１の分岐位置（第１階層の値が１／２である上から６個の位置情報）では、６個の位置情報のうち、第２階層で値１／２をとる位置情報が４個、値１／４をとる位置情報が２個あることを計数する。つまり、ここで言う「分岐位置」とは、木構造として見た時、対象とする階層より１つ上の階層にある１つの節を起点として、その下にぶら下がっている全ての要素（葉又は節）に対応する位置情報の集合を指し、位置情報の値に基づいて言えば、対象とする階層より上位の階層に全く同じ値を持った位置情報の集合を指している。そして、各分岐位置に含まれる位置情報の個数は、入力された１つ上の階層の計数値によって与えられる。なお、図１２の第１階層については、根にぶら下がっている要素、即ち全ての要素の位置情報が第１階層の「分岐位置」とされる。
計数する位置情報の値の出現順は、即ち復号順であるから、どの分岐位置であっても必ず図４Ａの順序関係に従っている。このため、上記の計数処理は、常に図４Ａに従って計数値を求めるものとし、値に抜けがある（出現しない値が途中にある）場合にはその値の出現個数を０と計数する。即ち、得られた計数結果は、どの分岐位置であっても、１個目の計数値は必ず図４Ａの最初の値１／２の出現個数であり、２個目の計数値は必ず図４Ａの２番目の値１／４の出現個数を表すものとする。こうして計数された結果を、更新幅算出部１３０２及びインデックス値更新部１３０３へ出力する。また、出力して次の階層での処理に利用する。
更新幅算出部１３０２は、位置情報計数部１３０１から受け取った計数値に基づいて、対象とする階層の位置情報の値に応じた、各位置情報のインデックス値の更新幅を求める。
ある分岐位置について、ある値を対象の階層に持つ位置情報に対するインデックス値の更新幅は、その値より小さい値をその階層に持った位置情報が幾つあるかによって決定される。例えば、ある分岐位置で対象の階層に値１／４，１／２，３／４を持つ位置情報がそれぞれＭ１個，Ｍ２個，Ｍ３個あった場合、値１／２を持つ位置情報の前にはＭ１個の値１／４を持った位置情報があるために、値１／２を持つ位置情報には値１／４を持つ位置情報のインデックスにＭ１だけ加えたインデックスを付ける必要がある。従って、値１／２を持った位置情報に対するインデックス値の更新幅はＭ１となる。また同じ理由から、値３／４を持った位置情報に対する更新幅はＭ１＋Ｍ２で与えられる。これら位置情報の個数Ｍ１，Ｍ２，Ｍ３は位置情報計数部１３０１で得られた各計数値にあたる。即ち、位置情報計数部１３０１で得られた各計数値を数値の大小順に積算していくことによって、それぞれの位置情報の値に対応した更新幅が得られる。
上記の積算処理を行うためには、位置情報計数部１３０１で得られた計数値を数値の大小順に読み出す必要がある。一方、既に説明したように、位置情報計数部１３０１で計数される各計数値は、図４Ａの順序関係に従って各位置情報値の出現個数を表したものであることがわかっている。このことから、位置情報の値どうしを互いに比較しなくとも、計数値の得られた順によってそれらの値の大小関係を知ることが可能である。値どうしの比較を行わないため、計算量を少なく抑えることができる。このための情報が、積算順情報１３０４である。
図１４乃至図１５と共に積算順情報１３０４について説明する。図１４の表１４０１及び図１５の表１５０１はいずれも積算順情報１３０４の例である。例えば、計数された位置情報の値が図４Ａの順序関係で３／４までの３個だった場合、それらの値の大小順は図１４の表１４０１に示すように小さい方から、２番目の値（１／４），１番目の値（１／２），３番目の値（３／４）の順であるから、その順に計数値を積算すればよい。計数された位置情報の値が７／８までの７個なら、それらの大小は図１５の表１５０１の順であり、同じくその順に計数値を積算すればよい。即ち、図４Ａの順序関係でどこまでの位置情報が計数（復号）されるかで、計数順（復号順）に対するそれらの大小順が一意に定まる。この計数順に対する大小順の情報を「積算順情報」と呼ぶ。
仮に、計数された位置情報の値が図４Ａの順序関係で１／４までの２つであった場合、これら２つの位置情報の値に対する積算順情報を用意して用いてもよい。同様に、全ての位置情報の値について、図４Ａの順序関係でその値までの位置情報の値に対する積算順情報を用意しておくことが可能である。但し、全ての位置情報の値について積算順情報を用意しておくためには多くのメモリを必要とし、場合によっては適切でない。そこで、Ｎを２のべき乗数とした時、図４Ａの順序関係で（Ｎ−１）／Ｎまでの位置情報の値に対して与えられる複数の積算順情報のみを用意し、（Ｎ−１）／Ｎ以外の位置情報の値に対する積算順情報は、用意されている複数の（Ｎ−１）／Ｎに対する積算順情報のいずれかを参照することで積算順を決めるといったこともできる。
図４Ａの順で最後に復号された位置情報の値に対して、その値以上の（Ｎ−１）／Ｎに対応する積算順情報であれば、積算順を決めるのに利用することができる。更に、余分な積算処理を最小に抑えるためには、その値以上でかつ最小の（Ｎ−１）／Ｎを選んで、対応する積算順情報を使うものとする。この時Ｎは、最後に復号されたの値の分母の値に等しい。例えば、ある分岐位置で復号された位置情報の値が１／２，１／４の２個の場合には、最後に復号された値１／４の分母４であるから、３／４までの復号順情報、即ち図１４の表１４０１を利用する。また、位置情報の値が１／２，１／４，３／４，１／８の４個の場合には、値１／８の分母８であるから、７／８までの復号順情報、図１５の表１５０１を利用する。そして、積算順情報１３０４で示された順に位置情報計数部１３０１で得られた計数値を積算し、位置情報の各値に対応するインデックス値の更新幅を求める。その際、復号値にない値については、対応する計数値を０として積算する。そして、得られた更新幅をインデックス値更新部１３０３へ出力する。
インデックス値更新部１３０３は、更新幅算出部１３０２で得られた更新幅と位置情報計数部１３０１で得られた計数結果、及び１つ上の階層の計数値とを用いて、各位置情報に付されているインデックスの値を更新する。
位置情報計数部１３０１で得られた最初の計数値は、対象の階層に値１／２を持つ位置情報の個数を表すため、分岐位置にある位置情報のうち、先頭から最初の計数値個分の位置情報について、更新幅算出部１３０２で得られた値１／２に対応する更新幅でインデックスの値を更新する。この時、分岐位置の先頭は、入力された１つ上の階層の計数値から求める。同様に、２番目以降の計数値についても処理する。
図１２の計数結果１２０２とインデックス及び更新幅１２０３とで、第１階層及び第２階層の分岐位置での処理を例に、更新幅算出部１３０２及びインデックス値更新部１３０３の処理を説明する。
はじめに、各位置情報のインデックスの初期値を０に設定する。
第１階層で復号された位置情報の値は１／２，１／４の２つであるから、積算順情報１３０４には図１４の表１４０１を用いる。図１４の表１４０１における積算順情報で、最初の位置情報値１／４については、インデックス値の更新幅を０とする。次に、更新幅算出部１３０２で、更新幅０に値１／４に対応する計数値４を加算し、表１４０１の次の値１／２に対するインデックス値の更新幅４を求める。図１２の計数結果１２０２とインデックス（及び更新幅）１２０３の例では、第１階層には次の値３／４が無いが、仮に次の値３／４があった場合には、更新幅算出部１３０２で、更新幅４に値１／２に対応する計数値６を更に加算し、表１４０１に従った次の値３／４に対する更新幅１０を求める。
インデックス値更新部１３０３では、第１の計数値６に基づいて、先頭から６個の位置情報に付されているインデックス値０（初期値）に、値１／２に対応する更新幅４を加え、更新されたインデックス値４が求まる。次に、第２の計数値に対応する続く４個の位置情報のインデックス値０に、値１／４に対応する更新幅０を加え、更新されたインデックス値０とする。
同様に、第２階層の第１の分岐位置（上から６個の位置情報）で復号された位置情報の値は１／２、１／４の２つであるから、積算順情報１３０４には図１４の表１４０１を用いる。表１４０１の積算順情報で、最初の位置情報値１／４については、インデックス値の更新幅を０とする。次に、更新幅算出部１３０２で、更新幅０に値１／４に対応する計数値２を加算し、表１４０１の次の値１／２に対するインデックス値の更新幅２を求める。
インデックス値更新部１３０３では、第１の計数値４に基づいて、先頭から４個の位置情報に付されているインデックス値４に、値１／２に対応する更新幅２を加え、更新されたインデックス値６が求まる。次に、第２の計数値に対応する続く２個の位置情報のインデックス値４に、値１／４に対応する更新幅０を加え、更新されたインデックス値４とする。
第２階層の第２の分岐位置（下の４個の位置情報）では、積算順情報１３０４に図１４の表１４０１を用い、更新幅算出部１３０２で、位置情報値１／４に対する更新幅０、値１／２に対する更新幅１を求める。
インデックス値更新部１３０３では、位置情報計数部１３０１で得られた計数値に従い、分岐位置の先頭から３個の位置情報に更新幅１を加えてインデックス値１に、残りの位置情報に更新幅０を加えてインデックス値０にインデックスを更新する。この時、第２階層の第２の分岐位置の先頭は、入力された１つ上の階層の計数値によって求められる。
計数結果１２０２の第１階層の２つの計数値、６と４は、そのまま第２階層の２つの分岐位置における位置情報の個数を表している。そのため、第２階層の第２の分岐位置の先頭は、第１の分岐位置の位置情報の個数６に１を足した、７となる。こうして分岐位置の先頭が特定され、分岐位置に含まれる各位置情報のインデックスを更新することができる。無論、計数値としてでなく、各分岐位置の先頭の位置に変換した情報を保持して上位の階層から受け取るようにしてもよい。
この処理を、各階層の各分岐位置に対して同様に実行する。図１２の１２０３は、こうして上位の階層から順に実行した場合の、各階層での更新後のインデックス値とそれぞれの分岐位置で求められる更新幅の値（括弧内）とを記している。最も下位の第３階層では、各位置情報の値が１回づつ出現するため、１づつの差を持ったインデックス値が最終的に得られる。こうして得られたインデックスが位置情報の順序関係を表すものであり、このインデックスに従って読み出すことで位置情報の並び替えを行うことができる。この並べ替えられた位置情報が、図１１の位置情報並替部１１０５からの出力となる。
上記の処理では、処理の都度、更新幅の値を加えてインデックス値を逐次更新していく例を示したが、これ以外にも、各階層の更新幅を別途求めておき、最後に各階層の更新幅の値を合計するとしてもよい。
また、図１３と共に説明した上記の処理では、分岐位置毎に、位置情報の計数処理，積算処理，インデックス値の更新処理を行うとしているが、位置情報の計数処理を全ての階層の全ての分岐位置について先に行い、求めた計数値を図１２の計数結果１２０２のように全て保持してそれ以降の処理に利用するとしてもよい。この場合、計数結果を保持するためのメモリが余分に必要となるが、他の階層の計数結果を任意の時点で利用できるため、上記の例のように階層順に処理する必要がなく、処理する階層の順番や分岐位置の順番を任意に変えることができるようになる。また更に、この計数処理を全ての位置情報の復号後に行うのでなく、位置情報の復号を行いながら同時に計数することも可能である。
説明した位置情報の並べ替え処理（インデックス値の計算方法）は、復号される位置情報の値が図４Ａの順序関係に従うことを反映した積算順情報１３０４を用いることで、復号された各々の値どうしを比較しなくとも並べ替えを行うことができ、計算処理が軽減される利点がある。また、上記の方法では、更新幅算出部１３０２での処理が位置情報の出現個数の積算処理であるため、欠落し、出現しなかった位置情報の値が途中にあった場合でも、その位置情報の出現個数を０と計数することによって、全く同じ枠組みで処理を行うことができる。このため、特に分岐処理等を必要とせず、以下に示すような位置情報の欠落があった場合でも並べ替えの処理を高速に行うことが可能である。
ここでは、復号時の並べ替え処理に特化して並べ替え方法を説明したが、説明した並べ替え方法は、符号化時の並べ替え処理に対しても同様にして用いることができる。その場合には、積算順情報１３０４を、図１４や図１５に示した「図４Ａの順」から「数値の大小順」へと変換するものでなく、符号化処理に対応した「数値の大小順」から「図４Ａの順」へと変換するものに入れ替えるだけでよい。また、ここでは、本実施形態で使用した「２のべき乗分の自然数（分母が２のべき乗数、分子が自然数）」の有理数表現された位置情報を例として示したが、この並べ替え処理は他の有理数表現された位置情報にも、あるいは有理数表現でなくとも並べ替えが必要な任意の位置情報に対して、同様に適用可能である。
次に、欠落がある場合の木構造の位置情報の復号の例として、図９に示した位置情報符号列の復号の動作について説明しておく。
位置情報（１／２，１／２）が前位置情報保持部１１０２に記録された時点で、次に分岐階層判定部１１０３で読み込まれる位置情報符号は、欠落を表す欠落符号“００”である。この場合、分岐階層判定部１１０３は、次に来る位置情報が欠落位置であることを、差分位置情報復号部１１０４に通知し、次の位置情報符号“１０”を読み込む。今度の位置情報は第２階層の分岐を示す符号であるから、その判定結果を差分位置情報復号部１１０４に通知する。
差分位置情報復号部１１０４では、次の更新位置が欠落位置であること、そしてその更新する分岐階層は第２階層であることを受け取る。差分位置情報復号部１１０４では、前位置情報保持部１１０２に保持された位置情報（１／２，１／２）から、第２階層の値を図４Ａの順序関係に従って１つ分、１／２から１／４に更新し、更新された位置情報（１／２，１／４）を得るが、これが欠落位置であると通知されているため、位置情報並替部１１０５には出力せずに、前位置情報保持部１１０２にのみ、その値（１／２，１／４）を出力し保持する。
次に読み込まれる位置情報符号は“１０”であることから、分岐階層判定部１１０３では次の分岐階層が第２階層であることを判定し、その結果を差分位置情報復号部１１０４に通知する。
差分位置情報復号部１１０４は、分岐階層が第２階層であることを受け取り、前位置情報保持部１１０２に保持された位置情報（１／２，１／４）の第２階層の値を図４Ａの順序関係に従って、１／４から３／４に更新し、（１／２，３／４）が得られる。これは欠落位置ではないため、位置情報並替部１１０５に出力される。こうして、次の位置情報が正しく復号される。
また、位置情報（１／４，３／４）が前位置情報保持部１１０２に記録された時点で、次に分岐階層判定部１１０３で読み込まれる位置情報符号は、欠落を表す欠落符号“００”である。分岐階層判定部１１０３は、次に来る位置情報が欠落位置であることを、差分位置情報復号部１１０４に通知し、次の位置情報符号“０１”を読み込む。今度の位置情報は第１階層の分岐を示す符号であるから、その判定結果を差分位置情報復号部１１０４に通知する。
差分位置情報復号部１１０４では、次の更新位置が欠落位置であること、そしてその更新する分岐階層は第１階層であることを受け取る。差分位置情報復号部１１０４では、前位置情報保持部１１０２に保持された位置情報（１／４，３／４）から、第１階層の値を図４Ａの順序関係に従って１つ分、１／４から３／４に更新し、かつ第２階層の値を図４Ａの順序関係での初期値１／２とすることで、更新された位置情報（３／４，１／２）を得るが、これが欠落位置であると通知されているため、位置情報並替部１１０５には出力せずに、前位置情報保持部１１０２にのみ、その値（３／４，１／２）を出力し保持する。
次に読み込まれる位置情報符号は“１０”であることから、分岐階層判定部１１０３では次の分岐階層が第２階層であることを判定し、その結果を差分位置情報復号部１１０４に通知する。
差分位置情報復号部１１０４は、分岐階層が第２階層であることを受け取り、前位置情報保持部１１０２に保持された位置情報（３／４，１／２）の第２階層の値を図４Ａの順序関係に従って、１／２から１／４に更新し、（３／４，１／４）が得られる。これは欠落位置ではないため、位置情報並替部１１０５に出力される。こうして、次の位置情報が正しく復号される。
検索情報に含まれる検索データ（あるいは節）の位置情報を扱うような場合、復号された位置情報は、検索データ（あるいは節）のそれぞれに対応するものであり、それら検索データ（あるいは節）が元の木構造中での出現順、即ち数値の大小順、に並んで扱われる、例えばその順に伝送されるあるいは蓄積されることは多い。そのような場合に、本発明は、並べ替えによって数値の大小順に並んだ元の順の位置情報が得られることで検索データ（あるいは節）との対応がとれ、各検索データ（あるいは節）の識別ができることになる。
また、検索データ（あるいは節）が、元の木構造中での出現順序か、もしくは位置情報と同様に図４Ａに従った順序に並び替えられて扱われるかが選択できるような場合には、検索データ（あるいは節）が並び替えられているか否かを示したフラグを別途設けて、位置情報符号列と共に伝送又は蓄積し、そのフラグの値に従って、位置情報並替部１１０５で位置情報の並べ替えを行うか否かを選択できるようにしてもよい。
図１６は、本発明の第１の実施形態にかかる位置情報の復号方法を説明するためのフロー図である。
本発明の第１の実施形態にかかる位置情報復号方法は、先頭位置情報復号ステップ（ステップＳ２１）、前位置情報保持ステップ（ステップＳ２２）、分岐階層判定／差分位置情報復号ステップ（ステップＳ２６）、並びに位置情報並替ステップ（ステップＳ２９）を含んでなる。本発明の第１の実施形態にかかる復号方法も、位置情報の復号に関するものであり、本発明としては、ここで説明する位置情報復号を含む復号を行う復号方法としての形態も採り得る。
始めに、先頭の位置情報を通常の方式で復号する（ステップＳ２１）。そして、復号された先頭の位置情報を前位置情報として保持する（ステップＳ２２）。
次に、位置情報符号を読み込む（ステップＳ２３）。そして、読み込まれた位置情報符号に対して、まず、終了符号か否かを判定する（ステップＳ２４）。終了符号でない場合、次に、欠落符号か否かを判定する（ステップＳ２５）。
欠落符号でない場合には、その位置情報符号に基づいて分岐階層を判定し、その判定結果に基づいて位置情報を更新、即ち次の位置の位置情報を求める（ステップＳ２６）。ここで行う次の位置情報を求める処理は、既に復号装置の説明で示したように、分岐階層については位置情報の値を図４Ａの順序関係に従って１つ分増加させ、分岐階層より下位の階層については図４Ａでの初期値１／２を、分岐階層より上層については変更無しとして行うものである。そして、得られた位置情報を出力する（ステップＳ２７）と共に、それを前位置情報として保持し（ステップＳ２２）、同様の処理を続ける。
欠落符号であると判定された場合には、次の位置情報符号を読み込む（ステップＳ２８）。そして、読み込まれた位置情報符号から分岐階層を判定し、上記と同様にして次の位置情報を求める（ステップＳ２６）。但し、ここで求められた位置情報は欠落位置であるため、出力はされずに、単に次の前位置情報として保持されて（ステップＳ２２）、以下同様の処理を続ける。
読み込まれた位置情報符号が終了符号と判定されたら（ステップＳ２４）、最後に復号され出力された位置情報を数値の大小順に並べ替えて（ステップＳ２９）、復号が完了する。
なお、本発明の実施形態にかかる符号化／復号装置及び方法では、有理数表現された位置情報として、「２のべき乗分の自然数」で与えられるものを例としてあげたが、有理数表現の位置情報はこれに限られるものではない。例えば「３のべき乗分の自然数（分母が３のべき乗数、分子が自然数）」などでも同様に処理できる。また、本発明の実施形態の「２のべき乗分の自然数」は当然０を含んでいないが、０を位置情報の取り得る値としてここに含めることもできる。その場合、図４Ａの順序関係は、０が１／２の前に置かれて、初期値が０となる。あるいは有理数以外でも同様に、そのままでは順序関係が決定されず、並べ替えを行うことで順序付けが可能といった性質を持つ位置情報であれば、本発明を適用可能である。本発明の本質は、本来、数値上の順序関係からは、ある値に対して次に更新される値が一意に特定できないような位置情報が存在した場合に、それを予め定められる順序関係を規定して、その決められた順序関係に従うように位置情報を並べ替えることによって、整数表現による位置情報の場合と同様に差分符号化による複数位置情報の符号化／復号を可能とした点にある。
（第２の実施形態）
次に、本発明の第２の実施形態にかかる位置情報の符号化装置について、図１７乃至図２１を用いて説明する。
図１７は、本発明の第２の実施形態にかかる位置情報符号化装置の概略構成を示す機能ブロック図である。
本発明の第２の実施形態にかかる位置情報符号化装置は、先頭位置情報符号化部１７０２、前位置情報保持部１７０３、ステップ幅決定部１７０１、ステップ幅符号化部１７０６、分岐階層判定部１７０４、並びに差分位置情報符号化部１７０５で構成される。このうち、先頭位置情報符号化部１７０２，前位置情報保持部１７０３，及び差分位置情報符号化部１７０５については、図１と共に説明した第１の実施形態にかかる位置情報符号化装置を構成する機能ブロックにおける先頭位置情報符号化部１０２，前位置情報保持部１０３，差分位置情報符号化部１０５と同一のものである。
既に説明した第１の実施形態では、図２に示すような木構造を有する検索情報の有理数表現された複数の位置情報を符号化するために、位置情報が取り得る有理数の値に関した固有の順序関係を予め定義し、その順序関係に従って符号化する複数の位置情報を並べ替えることとした。この並べ替えにより、ある位置情報の値に対する次の位置情報の値が一意となることで、有理数表現された位置情報であっても整数表現の位置情報と同様の差分符号化を可能とした。このため、図１に示した第１の実施形態にかかる位置情報符号化装置は位置情報並替部１０１を備え、また、並べ替えられた位置情報を元の数値の大小順に戻すために図１１に示した第１の実施形態にかかる位置情報復号装置は位置情報並替部１１０５を備えた。
これに対し、第２の実施形態では、位置情報の順序関係は数値の大小順のままとし、代わりに有理数の値の増加するステップ幅を求めて、位置情報符号と共に符号化／復号することによって差分符号化／復号を可能とする。従って、第１の実施形態に示すような並べ替え処理を必要としない有理数位置情報の差分符号化／復号が可能となる。更に、以下で詳しく説明するように、本実施形態では、各階層に対して固定のステップ幅を決定して与え、かつ、このステップ幅を、ある階層で分岐した時にそれより下位の階層に与える位置情報の初期値を兼ねるとすることで、符号化／復号処理をより簡単化すると共に、符号化効率の低下を抑えている。このため、図１７に示した第２の実施形態にかかる位置情報符号化装置は、図１の位置情報並替部１０１の代わりにステップ幅決定部１７０１及びステップ幅符号化部１７０６を備え、また、後述する図２３に示した第２の実施形態にかかる位置情報復号装置は、図１１の位置情報並替部１１０５の代わりにステップ幅復号部２３０５を備える。
以下、第２の実施形態にかかる位置情報符号化装置、符号化方法、復号装置並びに復号方法を順を追って説明するが、これらの説明は、既に述べた第１の実施形態にかかる位置情報符号化装置、符号化方法、復号装置及び方法での説明を前提とし、重複する箇所については適宜省略して説明する。従って、第１の実施形態で記載した限定等の詳細な記載を本実施形態では改めて記載しないが、特に断らない限り、第１の実施形態で記載した限定等の記載は第２の実施形態にもそのまま当てはまるものとする。
図１８は、本発明の第２の実施形態にかかる位置情報符号化装置の一構成例で符号化される位置情報（図２に示した検索情報の各データに対応する識別情報に含まれる位置情報）と、それらを符号化して得られる位置情報符号列との一例を示した図である。以下、図１８に基づいて、図１７に示す本発明の第２の実施形態にかかる位置情報符号化装置の動作を説明する。
先頭位置情報符号化部１７０２は、符号化する複数の位置情報のうち、先頭の位置情報を、差分を用いない通常の方式で符号化する。図１８では、先頭の位置情報（１／４，１／４）を、１変数あたり５ビットとし５×２＝１０ビットで符号化して与えている。第１の実施形態と同様、本発明では先頭の位置情報に関する符号化方式については特に言及しない。
前位置情報保持部１７０３は、１つ前に処理された位置情報を記録し、次の位置情報の符号化を行う際に出力して提供する。はじめに、符号化された先頭の位置情報（１／４，１／４）が記録され保持される。
ステップ幅決定部１７０１は、数値の大小順に並んだ位置情報の値に対し、ある値から次の値への増加幅にあたる固定の「ステップ幅」を各階層について求めて、ステップ幅符号化部１７０６及び分岐階層判定部１７０４に出力する。
あるステップ幅に対して、そのステップ幅を初期値とし、同じくそのステップ幅の値を順次加えていくと、そのステップ幅によって表現可能な位置情報の値が決まる。ある階層に対するステップ幅は、その階層に付された全ての位置情報の値が表現可能となるように値を設定する。また、余分な位置情報の符号化を避け効率良く位置情報を符号化するため、ステップ幅はできるだけ大きな値を選ぶ。本実施形態では以下に、「２のべき乗分の自然数（分母が２のべき乗数、分子が自然数）」の有理数で表現された位置情報に対して、「２のべき乗分の１（分母が２のべき乗数、分子が１）」で表されるステップ幅を用いた例を示す。無論、有理数の表現がこれに限らないのと同様に、ステップ幅の表現はこれに限るものではない。
図１８で符号化する位置情報のうち、第１階層に存在している位置情報の値は１／４，１／２，３／４であるため、初期値１／４とし、同じくステップ幅１／４として値を更新していけば、これらの値を含むことができる。第２階層に存在している位置情報の値も同じく１／４，１／２，３／４であるため、第２階層のステップ幅も同じく１／４と設定される。仮に、存在する位置情報の値が１／４，１／２，５／８であったとすれば，初期値＝ステップ幅＝１／４で値５／８を表現することはできない。この場合には，初期値＝ステップ幅＝１／８と設定することによって，１／４，１／２，５／８の値を含むことができる。
上記の「２のべき乗分の１」で表されるステップ幅については、もっと単純に、同じ階層に存在している位置情報の値を図４Ａの順序関係に従って並べ、最後尾に位置した値の解像度＝分母の値によって求めることができる。ステップ幅は＜最後尾の値の分母値＞分の１である。これは、図４Ａの順序関係に従って位置情報の値を並べると最後尾の値の解像度が最も高いために、それより解像度が低い（または同じ）他の値がその解像度で表せることが保証されるためである。
なお、本実施形態の例では用いていないが、ある階層にある全ての位置情報の値を数値の大小関係に従って並べ、隣り合う２つの値どうしで差分を計算し、それらの差分値及び最小の位置情報の値についての最大公約数となる値を求めることで、更に効率の良いステップ幅を設定することも可能である。
例えば、位置情報の値として３／１６，３／８，３／４のみが使われているような場合には，３／１６と３／８との差分値３／１６，３／８と３／４との差分値３／８，及び最小の位置情報値３／１６とで最大公約数をとると３／１６となる。従って，この値を位置情報の値のステップ幅及び初期値に設定することができ，効率良く３つの値３／１６，３／８，３／４を表すことができる。
ステップ幅符号化部１７０６は、ステップ幅決定部１７０１で決定された各階層に対応するステップ幅を符号化して出力する。符号化は、各階層に対応するステップ幅のそれぞれについて行い、前述の先頭位置情報の符号化と同様、通常の方式で符号化される。図１８では、第１階層のステップ幅１／４、第２階層のステップ幅１／４が各々５ビットで符号化されて与えられている。ステップ幅の符号化方式についても、先頭位置情報の符号化方式と同様、本発明では特に言及しない。
なお、本実施形態では、ステップ幅の符号化を先頭位置情報の符号化の後に行うとしているが、これに限らず、先頭位置情報の前に処理することもできる。また、後述するように、ここで規定されるステップ幅の値は、差分符号化／復号で分岐階層の位置情報の値を更新する際、分岐階層より下の階層の位置情報に与える位置情報の初期値としても利用される。
分岐階層判定部１７０４で行う処理は、基本的に、従来の整数表現された位置情報に対する符号化で行う処理と同等である。異なる点は、整数表現された位置情報ではステップ幅が固定「１」であったのに対して、ステップ幅決定部１７０１で求めたステップ幅を用いる点、及び、整数表現された位置情報では初期値が０であったのに対し、位置情報の初期値に同じくステップ幅決定部１７０１で求めたステップ幅の値を用いる点にある。第１の実施形態にかかる位置情報符号化装置で詳しく説明したのと同様、図１７の符号化装置においては、ステップ幅の値は欠落の判定に用いられる。
分岐階層判定部１７０４は、入力されてくる符号化すべき位置情報と、前位置情報保持部１７０３に保持されている位置情報とを比較し、それらを基に分岐階層の判定を行って、その判定結果を差分位置情報符号化部１７０５に出力する。かつ、この時、分岐階層判定部１７０４では、ステップ幅決定部１７０１から出力されるステップ幅の値に基づいて、第１の実施形態で説明したのと同様にして欠落を判定し、出力する。
差分位置情報符号化部１７０５は、分岐階層判定部１７０４での判定結果（分岐階層及び欠落の有無）に従って位置情報符号を選択し、出力する。
図１８で２番目の位置情報（１／４，１／２）を符号化する際、前位置情報保持部１７０３には、１つ前に符号化された位置情報（１／４，１／４）が保持されている。これらを比較すると、第１階層、即ちシーンの階層の値は同じであり、第２階層、即ちショットの階層の位置情報の値が増加している。更にこの時、第２階層の位置情報の値は１／４から１／２へ、第２階層のステップ幅１／４分増加しているため、欠落無く分岐していることが判る。この判定結果を差分位置情報符号化部１７０５に出力し、差分位置情報符号化部１７０５からは、第２階層に対応する位置情報符号“１０”が出力される。なお、位置情報符号の種類並びに位置情報符号のビット長に関しては、第１の実施形態での説明がそのまま適用される。
図１８で４番目の位置情報（１／２，１／４）を符号化する際、前位置情報保持部１７０３には、１つ前に符号化された位置情報（１／４，３／４）が保持されている。これらを比較すると、第１階層、即ちシーンの階層で位置情報の値が増加している。更にこの時、第１階層の位置情報の値は１／４から１／２へ、第１階層のステップ幅１／４分増加しており、かつ、第２階層の値は、第２階層のステップ幅と同じ初期値１／４になっているため、欠落無く分岐していることが判る。この判定結果を差分位置情報符号化部１７０５に出力し、差分位置情報符号化部１７０５からは、第１階層に対応する位置情報符号“０１”が出力される。
上述の分岐階層判定部１７０４における判定で、欠落があると判定された場合には、既に第１の実施形態で図９と共に説明したように、欠落符号を用いた同様の位置情報の符号化を行えばよい。特に、図１９に、欠落符号を用いた符号化が必要となる木構造を持った検索情報の例を示す。図１９では、動画像コンテンツ１９１０が２つのシーンからなり、１つめのシーン（シーン＃１／４）が３つのショットから、２つめのシーン（シーン＃１／２）が４つのショットからなる例を示しており、シーン＃１／４の各ショットには位置情報の値として１／４，１／２，３／４が，シーン＃１／２の４つのショットには位置情報１／８，１／４，３／８，１／２が振られている。この場合、初期値＝ステップ幅＝１／８と設定することで全ての値を更新値に含むことができるため、ステップ幅は１／８となる。
図２０には、図１９に示された検索情報の各データ１９０１〜１９０７に対応する識別情報から抜き出された位置情報と、それらの位置情報を符号化した位置情報符号列の例を示している。この例で、シーン＃１／４を構成する各ショットの位置情報は１／４，１／２，３／４であり、それらのみではステップ幅１／４が適当と考えられるが、全体としてステップ幅は１／８と設定されたため、本来無い位置（１／４，３／８）、（１／４，５／８）が欠落位置として現れ、符号化されている。
上記のような冗長を軽減するための方法として、図２１に示したように、木が分岐する毎にステップ幅を求めなおして、符号化して与えることが可能である。ここで木が分岐した時に符号化されるステップ幅は、分岐階層より下に存在する階層について与える。図２１では、第１階層で分岐した場合に、第１階層より下の階層、即ち第２階層に対するステップ幅を符号化して与えている。階層数が増えれば、分岐した時に与えるステップ幅の数も増える。つまり、仮に３つの階層があり、第１階層で分岐が起きた場合には、第２階層、第３階層に対応する２つのステップ幅を符号化して与えることになる。
図２２は、本発明の第２の実施形態にかかる位置情報の符号化方法、特に、図１８及び図２０の位置情報符号列の例と共に説明した符号化装置の動作に対応する位置情報の符号化方法を説明するためのフロー図である。
図２２に示した本発明の第２の実施形態にかかる位置情報符号化方法は、図１０に示した第１の実施形態にかかる位置情報符号化方法に対して、位置情報並替ステップ（ステップＳ１）を無くし、代わりにステップ幅符号化ステップ（ステップＳ３２）の追加と、欠落判定ステップ（ステップＳ７）を、得られたステップ幅に基づく欠落判定ステップ（ステップＳ３７）に変更して構成される。その他の処理は第１の実施形態にかかる位置情報符号化方法の処理と同じであり、図１０のステップＳ２，Ｓ３，Ｓ４，Ｓ５，Ｓ６，Ｓ８，Ｓ９，Ｓ１０，Ｓ１１が、それぞれ図２２のステップＳ３１，Ｓ３３，Ｓ３４，Ｓ３５，Ｓ３６，Ｓ３８，Ｓ３９，Ｓ４０，Ｓ４１に対応する。
次に、本発明の第２の実施形態にかかる位置情報の復号装置を、図２３に基づいて説明する。
図２３は、本発明の第２の実施形態にかかる位置情報復号装置の概略構成を示す機能ブロック図である。
本発明の第２の実施形態にかかる位置情報の復号装置は、先頭位置情報復号部２３０１、前位置情報保持部２３０２、ステップ幅復号部２３０５、分岐階層判定部２３０３、並びに差分位置情報復号部２３０４からなる。このうち、先頭位置情報復号部２３０１，前位置情報保持部２３０２，分岐階層判定部２３０３については、図１１と共に説明した第１の実施形態にかかる位置情報復号装置を構成する機能ブロックにおける先頭位置情報復号部１１０１，前位置情報保持部１１０２，分岐階層判定部１１０３と同一のものである。
本実施形態の位置情報復号装置において、ステップ幅復号部２３０５及び差分位置情報復号部２３０４を除く動作は、従来の整数表現された位置情報の復号処理と基本的に変わらない。ここでは、本実施形態にかかる位置情報復号装置の動作を、図１８に示した位置情報符号列を入力した場合で説明する。
先頭位置情報復号部２３０１は、先頭の位置情報を復号し、その位置情報を出力する。第１の実施形態と同様に、通常の方式で符号化された位置情報の復号であり、その動作については本発明では特に言及しない。
図１８の位置情報符号列のうち、先頭の１０ビット（５ビット×階層数２）から先頭の位置情報（１／４，１／４）が復号され、前位置情報保持部２３０２に記録されて保持される。
次に、ステップ幅復号部２３０５は、各階層に対応するステップ幅の値を復号して求める。図１８では、先頭位置情報の符号に続くステップ幅の符号１０ビット（５ビット×階層数２）を読み込み、第１階層のステップ幅１／４、第２階層のステップ幅１／４を復号する。復号された各階層のステップ幅の値は、差分位置情報復号部２３０４へ出力されて、位置情報を復号するのに使用される。
ステップ幅も、先頭の位置情報と同様、通常の方式で符号化／復号されるものである。従って、その動作については本発明では特に言及しない。ここでは、上記の先頭位置情報の各符号のビット数５ビット、ステップ幅の各符号のビット数５ビットが、符号化する方式によって定まるものである。
分岐階層判定部２３０３は、位置情報符号を順次読み込み、位置情報が示す分岐階層を差分位置情報復号部２３０４に通知する。またこの時、第１の実施形態にかかる位置情報復号装置の説明で述べたのと同様に、欠落符号を読み込んで、欠落位置の処理を行うこともできる。
図１８の位置情報符号列に対し、ステップ幅復号部２３０５でステップ幅の復号を行ったのち、分岐階層判定部２３０３は位置情報符号“１０”を読み込む。位置情報符号“１０”は、第２階層、即ちショットの階層が分岐していることを示した符号であり、この判定結果が差分位置情報復号部２３０４に通知される。なお、位置情報符号の種類並びに位置情報符号のビット長に関しては、第１の実施形態での説明がそのまま適用される。
差分位置情報復号部２３０４では、前位置情報保持部２３０２に保持されている１つ前の位置情報と分岐階層判定部２３０３から得られる判定結果に基づいて、位置情報を復号する。この時、ステップ幅復号部２３０５で復号されて得られているステップ幅が、有理数表現された位置情報の値の更新幅、及び、上位階層で分岐した際に下位階層に与える位置情報の初期値として利用される。
上記“１０”が第２階層、即ちショットの階層で分岐していることが判定された時点で、前位置情報保持部２３０２には、先頭位置情報復号部２３０１で復号された位置情報（１／４，１／４）が保持されている。差分位置情報復号部２３０４では、この保持されている位置情報に対し、分岐階層にあたる第２階層の値に、ステップ幅復号部２３０５で得られた第２階層のステップ幅１／４を加える。こうして位置情報（１／４，１／２）が復号され、出力されると共に、この値が前位置情報保持部２３０２で保持される。
図１８で位置情報（１／４，３／４）が復号され前位置情報保持部２３０２に保持されている時点で、次に、分岐階層判定部２３０３には、位置情報符号“０１”が読み込まれる。位置情報符号“０１”は、第１階層、即ちシーンの階層で分岐があることを示した符号であり、判定結果が差分位置情報復号部２３０４に出力される。
差分位置情報復号部２３０４では、分岐階層判定部２３０３から通知される判定結果に基づいて、前位置情報保持部２３０２に保持されている位置情報（１／４，３／４）に対して、分岐階層にあたる第１階層の位置情報の値をステップ幅復号部２３０５で得られている第１階層のステップ幅１／４分増加させると共に、分岐階層より下の階層となる第２階層については、第２階層のステップ幅１／４を初期値として与える。この結果、位置情報（１／２，１／４）が復号される。復号された位置情報（１／２，１／４）は出力されると共に、前位置情報保持部２３０２に入力されて保持される。
これを、分岐階層判定部２３０３で終了符号“１１”が読み込まれるまで行い、終了符号が読み込まれたら復号を終了する。
次に、図２０に基づいて、欠落がある場合の復号処理を説明する。第１の実施形態での説明と同様に、本実施形態でも欠落符号を用いて、欠落のある複数の位置情報の復号を行うことができる。
ステップ幅を復号するまでの処理は、上記で図１８に基づいて説明した復号処理と同じである。図２０の位置情報符号列では、ステップ幅復号部２３０５で第１階層のステップ幅１／４、第２階層のステップ幅１／８が復号されて得られる。
図２０の位置情報符号列に対し、ステップ幅復号部２３０５でステップ幅の復号を行ったのち、分岐階層判定部２３０３は位置情報符号“００”を読み込む。位置情報符号“００”は、位置の欠落を表す欠落符号である。このため、位置の欠落があることを差分位置情報復号部２３０４に通知すると共に、分岐階層判定部２３０３は次の位置情報符号“１０”を読み込む。位置情報符号“１０”は、第２階層、即ちショットの階層が分岐していることを示した符号であり、この判定結果が差分位置情報復号部２３０４に通知される。
差分位置情報復号部２３０４では、前位置情報保持部２３０２に保持されている１つ前の位置情報と分岐階層判定部２３０３から得られる判定結果に基づいて、次の位置情報を復号する。今、判定結果として、分岐階層が第２階層であること、及びその位置が欠落位置であることが通知されている。
前位置情報保持部２３０２には、位置情報（１／４，１／４）が保持されている。この保持されている位置情報に対し、分岐階層にあたる第２階層の値に、ステップ幅復号部２３０５で得られている第２階層のステップ幅１／８を加えて、位置情報（１／４，３／８）が復号される。但し、この位置は欠落位置であることが通知されている。このため、この位置情報は復号された位置情報として外部に出力されることなく、前位置情報保持部２３０２にのみ記録されて保持される。
次に、分岐階層判定部２３０３は位置情報符号“１０”を読み込む。位置情報符号“１０”は、第２階層、即ちショットの階層が分岐していることを示した符号であり、判定結果が差分位置情報復号部２３０４に通知される。
この時点で、前位置情報保持部２３０２には、位置情報（１／４，３／８）が保持されている。この保持されている位置情報に対し、分岐階層にあたる第２階層の値に、ステップ幅復号部２３０５で得られている第２階層のステップ幅１／８を加えて、位置情報（１／４，１／２）が復号される。この位置は欠落位置ではないため、この位置情報は復号された位置情報として外部に出力されると共に、前位置情報保持部２３０２で保持される。このようにして、位置の欠落がある場合にも、正しい位置情報が復号されて得られる。
次に、図２１の位置情報符号列に対する復号処理について説明する。
位置情報（１／４，３／４）を復号するまでの処理は、上記で図１８に基づいて説明した復号処理と同じである。図２１の位置情報符号列では、先頭の位置情報（１／４，１／４）が復号されたのち、ステップ幅復号部２３０５で第１階層のステップ幅１／４、第２階層のステップ幅１／４が復号され、以降読み込まれる位置情報符号“１０”、“１０”によって位置情報（１／４，１／２）、（１／４，３／４）が順次復号されて出力される。
次に、分岐階層判定部２３０３では位置情報符号“０１”が読み込まれる。位置情報符号“０１”は、第１階層が分岐階層であることを示した符号である。
図２１の位置情報符号列は、分岐階層が決定された時、その分岐階層より下にある階層に対して、新たにステップ幅を符号化するようにして符号化されたものである。第１階層が分岐階層である場合、その直後には、第１階層より下の階層、即ち第２階層に対してのステップ幅が符号化されて与えられている。このため、第１階層が分岐階層であると判断された時点で、第２階層のステップ幅にあたる符号５ビットがステップ幅復号部２３０５に読み込まれ、新たな第２階層のステップ幅１／８が復号されて得られる。
上記の例で第２階層が分岐階層である場合に新たなステップ幅の復号が無いのは、第２階層より下に位置する階層が無いためであるとも言える。なお、上記の例は第１、第２の２つの階層での例であるが、例えば第１から第３の３つの階層からなる位置情報で、第１階層が分岐階層であると判定された場合には、その直後に続く第２階層、第３階層のステップ幅を符号化した符号を復号する。即ち、分岐階層より下にある階層数分のステップ幅を復号する。更に階層数が増えても同様である。
前位置情報保持部２３０２には位置情報（１／４，３／４）が保持されている。差分位置情報復号部２３０４では、この保持されている位置情報に対し、分岐階層にあたる第１階層の値に、ステップ幅復号部２３０５で得られている第１階層のステップ幅１／４を加える。かつ、分岐階層より下に位置する第２階層について、ステップ幅復号部２３０５で新たに復号されて得られた第２階層のステップ幅１／８を、初期値として与える。こうして位置情報（１／２，１／８）が復号されて得られる。
復号された位置情報（１／２，１／８）は出力されると共に、前位置情報保持部２３０２に入力されて保持される。次に分岐階層判定部２３０３で読み込まれるのは、第２階層が分岐階層であることを示す位置情報符号“１０”である。差分位置情報復号部２３０４では、前位置情報保持部２３０２に保持されている位置情報（１／２，１／８）に対し、第２階層のステップ幅１／８を加えて、次の位置情報（１／２，１／４）を復号して得る。
以降、（１／２，３／８）、（１／２，１／２）が復号されたのち、終了符号“１１”が読み込まれて復号を終了する。
図２１で示した、ステップ幅を枝が分岐する都度符号化／復号する方式は、枝毎に位置情報の値の付け方にムラがあるような木を符号化する場合に、図２０で示した欠落符号を使う方式に比べて、符号化効率の低下を抑える効果がある。また、以上説明した本実施形態で符号化／復号されるステップ幅は、位置情報の値の増加幅と初期値とを兼ねるものとした。本発明では、このように値の増加幅と初期値とを共通化することによって、符号化効率の低下を抑えつつ有理数表現された位置情報の差分符号化を可能とするものである。あるいは、ステップ幅と初期値とを共通化せず、各々符号化することも可能である。この場合、上記図２１と共に説明した実施形態に対して、分岐階層より下の階層数分のステップ幅を符号化／復号する、とした点を、分岐階層より下の階層数分のステップ幅及び初期位置の値を符号化／復号する、と置き換えることで実現される。このようにすれば、初期位置の値とステップ幅の値とにずれがある場合に、より無駄の少ない符号化／復号が行える。
また、極端な例としては、全ての位置情報符号について、ステップ幅を同時に符号化して添付し、ステップ幅を自由に変えて符号化／復号する位置情報の差分符号化／復号方式を構成することもできる。
図２４は、本発明の第２の実施形態にかかる位置情報の復号方法、特に、図１８及び図２０の位置情報符号列の例と共に説明した復号装置の動作に対応する位置情報の復号方法を説明するためのフロー図である。
図２４に示した本発明の第２の実施形態にかかる位置情報復号方法は、図１６に示した第１の実施形態にかかる位置情報復号方法に対して、位置情報並替ステップ（ステップＳ２９）を無くし、代わりにステップ幅復号ステップ（ステップＳ５２）の追加と、差分位置情報復号ステップ（ステップＳ２６）を、復号して得られたステップ幅に基づく差分位置情報復号ステップ（ステップＳ５７）に変更して構成される。その他の処理は第１の実施形態にかかる位置情報復号方法の処理と同じであり、図１６のステップＳ２１，Ｓ２２，Ｓ２３，Ｓ２４，Ｓ２５，Ｓ２７，Ｓ２８が、それぞれ図２４のステップＳ５１，Ｓ５３，Ｓ５４，Ｓ５５，Ｓ５６，Ｓ５８，Ｓ５９に対応する。
なお、本発明の第１の実施形態に示した位置情報並替部１０１を備える位置情報符号化装置と、本発明の第２の実施形態に示したステップ幅決定部１７０１及びステップ幅符号化部１７０６を備える位置情報符号化装置とは、別個に実施されるものとして記載したが、これに限らず、それらの機能ブロックをいずれも備えた位置情報符号化装置を構成することもできる。その際、位置情報の並べ替え（位置情報並替部１０１での処理）を伴う符号化を行ったか、ステップ幅の符号化（ステップ幅決定部１７０１及びステップ幅符号化部１７０６での処理）を伴う符号化を行ったかを示したフラグを用意して、そのフラグの値を位置情報符号列と共に記録する。あるいは、位置情報符号列の属性情報として、位置情報符号列と別個のストリーム又はファイルに記録するとしてもよい。
また、第１の実施形態に示した位置情報並替部１１０５を備える位置情報復号装置と、第２の実施形態に示したステップ幅復号部２３０５を備える位置情報復号装置とを、別個の実施とせず、それらの機能ブロックをいずれも備えた位置情報復号装置を構成することもできる。この位置情報復号装置は、上記の、位置情報符号化装置によって記録されたフラグを受け取り、フラグの値に従って、並べ替え（位置情報並替部１１０５での処理）を伴う復号を行うか、ステップ幅の復号（ステップ幅復号部２３０５での処理）を伴う復号を行うかを切替える。
既に示したように、第１の実施形態に示した位置情報の符号化装置及び復号装置では、並べ替えを行うことにより、数値上の順序関係からは更新値が一意に特定できない有理数表現による位置情報であっても、整数表現の位置情報と同様に差分符号化による位置情報の符号化／復号を可能とする。また、第２の実施形態に示した位置情報の符号化装置及び復号装置では、ステップ幅を符号化し位置情報符号と共に記録することで、元の位置情報の順序関係を保持したまま差分符号化が行え、直観的に理解が容易な位置情報の符号化／復号が可能である、といった異なる効果を持つ。このため、フラグを用いて切替えることにより、状況に応じて適切な符号化方式を選択して利用することが可能となる。
また同様に、第１の実施形態に示した位置情報並替ステップＳ１を有する位置情報符号化方法と、第２の実施形態に示したステップ幅符号化ステップＳ３２を有する位置情報符号化方法とから、それらのステップをいずれも有した位置情報符号化方法を構成することもできる。また、第１の実施形態に示した位置情報並替ステップＳ２９を有する位置情報復号方法と、第２の実施形態に示したステップ幅復号ステップＳ５２を有する位置情報復号方法とから、それらのステップをいずれも有した位置情報復号方法を構成することもできる。
以上、本発明の位置情報の符号化装置及び方法、位置情報の復号装置及び方法を中心に各実施形態を説明してきたが、本発明は、上述した各実施形態における装置（符号化装置及び／又は復号装置）としてコンピュータを機能させるための、あるいはコンピュータに上述した各実施形態における方法（符号化方法及び／又は復号方法）の処理手順を実行させるためのプログラムとしても、あるいは、そのプログラムを記録したコンピュータ読み取り可能な記録媒体としての形態も可能である。
本発明にかかる装置として、コンピュータを機能させるためにそのコンピュータに組み込まれるプログラムは、上述した各装置における各部（各手段に対応）としてコンピュータのＣＰＵやＭＰＵを動作させるよう記述を行うか、若しくは、上述した各方法における各ステップの処理をＣＰＵやＭＰＵに実行させるよう記述を行うかなどして、容易に実現可能である。
図２５は、一般的な情報処理装置の構成例を示す図で、本発明にかかる装置を説明するための図である。
本発明にかかる装置における各種情報の処理について、図２５に示す一般的な情報処理装置の構成例を参照して説明する。本発明にかかる装置で取り扱われる情報は、その何れの装置においてもその処理時に一時的にＲＡＭ２５０２に蓄積され、その後画像データベース等の構成データとして各種ＲＯＭ２５０３に格納される。また、本発明にかかる装置としてコンピュータを機能させるためのプログラムを、ＲＯＭ２５０３に蓄積し、ＣＰＵ２５０１が読み出すことによって実行される。また、処理の途中経過や途中結果は、表示装置２５０５を通してユーザに提示され、必要な場合には、キーボード，マウス（ポインティングデバイス）等からユーザが処理に必要なパラメータを入力指定すればよい。このプログラムは、ユーザが使用する際に容易となるような表示装置２５０５用のグラフィカルユーザインターフェースを備えるようにするとよい。また、その他の処理の実行中に作られる中間データもＲＡＭ２５０２に蓄積され、必要に応じて、ＣＰＵ２５０１によって読み出し、修正・書き込みが行われる。なお、ＣＰＵ２５０１，ＲＡＭ２５０２，ＲＯＭ２５０３，入力装置２５０４，表示装置（ＣＲＴ，ＬＣＤ等）２５０５，出力装置（印刷装置，通信装置等）２５０６は、バス２５０７により接続されるか、各要素の一部がＬＡＮ等のネットワークを介して接続されていればよい。また、通信装置は通信回線によって他の装置とデータの遣り取りを行うための装置である。
次に、本発明による位置情報の符号化／復号の機能を実現するためのプログラムやデータを記憶した記録媒体の実施形態を説明する。記録媒体としては、具体的には、ＣＤ−ＲＯＭ、光磁気ディスク、ＤＶＤ−ＲＯＭ、ＦＤ、フラッシュメモリ、メモリスティック、及びその他各種ＲＯＭやＲＡＭ等が想定でき、これら記録媒体に上述した本発明の各実施形態の装置の機能をコンピュータに実行させ、位置情報の符号化／復号の機能を実現するためのプログラムを記録して流通させることにより、当機能の実現を容易にする。そしてコンピュータ等の情報処理装置に上述のごとくの記録媒体を装着して情報処理装置によりプログラムを読み出すか、若しくは情報処理装置が備えている記録媒体に当プログラムを記憶させておき、必要に応じて読み出すことにより、本発明にかかる位置情報の符号化／復号の機能を実行することができる。
【図１】
2004070955.tif 000003
【図２】
2004070955.tif 000004
【図３】
2004070955.tif 000005
2004070955.tif 000006
【図５】
2004070955.tif 000007
【図６】
2004070955.tif 000008
【図７】
2004070955.tif 000009
【図８】
2004070955.tif 000010
【図９】
2004070955.tif 000011
【図１０】
2004070955.tif 000012
【図１１】
2004070955.tif 000013
【図１２】
2004070955.tif 000014
【図１３】
2004070955.tif 000015
【図１４】
2004070955.tif 000016
【図１５】
2004070955.tif 000017
【図１６】
2004070955.tif 000018
【図１７】
2004070955.tif 000019
【図１８】
2004070955.tif 000020
【図１９】
2004070955.tif 000021
【図２０】
2004070955.tif 000022
【図２１】
2004070955.tif 000023
【図２２】
2004070955.tif 000024
【図２３】
2004070955.tif 000025
【図２４】
2004070955.tif 000026
【図２５】
2004070955.tif 000027
【図２６】
2004070955.tif 000028
【図２７】
2004070955.tif 000029
【図２８】
2004070955.tif 000030
【図２９】
2004070955.tif 000031
【図３０】
2004070955.tif 000032
【国際調査報告】
2004070955.tif 000033
2004070955.tif 000034
2004070955.tif 000035
2004070955.tif 000036