(57)【特許請求の範囲】
【請求項１】
１つまたは複数の階層からなり、１つの節は１つ下の階層に１つまたは複数の葉または節を持ち、該１つまたは複数の葉または節が初期値から始まる連番の位置番号が付されて区別された木構造の同一階層内の複数の葉または節の位置情報を符号化する符号化装置であって、
当該複数の葉または節の位置情報が、前記木構造の根から前記同一階層にある葉または節に至るまでに経由する分岐可能な階層の葉または節に付された前記位置番号の値の列で与えられ、前記同一階層の先頭の葉または節の位置情報は任意の手法により符号化されるものであり、
前記同一階層にある複数の葉または節のうち、前記先頭の葉または節以外の葉または節について、ある葉または節とそのひとつ前の葉または節とがどの階層で分岐したかをそれぞれの位置情報を比較して判定する分岐階層判定手段と、
前記分岐のあった階層に対応する符号を、該葉または節の位置情報のひとつ前の葉または節の位置情報からの更新内容を示す位置情報符号として出力する位置情報符号化手段とを備えたことを特徴とする符号化装置。
【請求項２】
前記請求項１に記載の符号化装置において、
前記木構造内の分岐可能な階層数を算出する階層数算出手段と、
該分岐可能な階層数に基づき、位置情報符号に必要なビット数を算出するビット数算出手段とを備え、
前記位置情報符号化手段は、前記算出されたビット数内で符号化することを特徴とする符号化装置。
【請求項３】
１つまたは複数の階層からなり、１つの節は１つ下の階層に１つまたは複数の葉または節を持ち、該１つまたは複数の葉または節が初期値から始まる連番の位置番号が付されて区別された木構造の同一階層内の複数の葉または節の位置情報を符号化する符号化方法であって、
当該複数の葉または節の位置情報が、前記木構造の根から前記同一階層にある葉または節に至るまでに経由する分岐可能な階層の葉または節に付された前記位置番号の値の列で与えられ、前記同一階層の先頭の葉または節の位置情報は任意の手法により符号化されるものであり、
前記同一階層にある複数の葉または節のうち、前記先頭の葉または節以外の葉または節について、ある葉または節とそのひとつ前の葉または節とがどの階層で分岐したかをそれぞれの位置情報を比較して判定し、
前記分岐のあった階層に対応する符号を、該葉または節の位置情報のひとつ前の葉または節の位置情報からの更新内容を示す位置情報符号として出力することを特徴とする符号化方法。
【請求項４】
１つまたは複数の階層からなり、１つの節は１つ下の階層に１つまたは複数の葉または節を持ち、該１つまたは複数の葉または節が初期値から始まる連番の位置番号が付されて区別された木構造によって構成され、前記木構造の根から同一階層にある葉または節に至るまでに経由する分岐可能な階層の葉または節に付された前記位置番号の値の列によって与えられる所定の同一階層の複数の葉または節の位置情報について、当該階層の先頭位置以外のある葉または節の位置情報を当該葉または節のひとつ前の葉または節の位置情報からの更新内容を示す位置情報符号によって符号化した位置情報符号を復号する復号装置であって、
前記位置情報符号から、ある葉または節とそのひとつ前の葉または節とが分岐した階層を判定する分岐階層判定手段と、
前記判定により判定した分岐階層に基づいて、当該階層に対応する前記ひとつ前の葉または節の位置情報の該分岐した階層の位置番号に対しては１を加算し、同前記ひとつ前の葉または節の位置情報の該分岐した階層より下の全ての階層の位置番号に対しては初期値に初期化する処理を行うことで、前記ひとつ前の葉または節の位置情報から該葉または節の位置情報を求める位置情報更新手段を備え、前記所定の階層の先頭位置の位置情報に基づいて順次前記同一階層の複数の葉または節の位置情報符号を復号することを特徴とする復号装置。
【請求項５】
１つまたは複数の階層からなり、１つの節は１つ下の階層に１つまたは複数の葉または節を持ち、該１つまたは複数の葉または節が初期値から始まる連番の位置番号が付されて区別された木構造によって構成され、前記木構造の根から前記同一階層にある葉または節に至るまでに経由する分岐可能な階層の葉または節に付された前記位置番号の値の列によって与えられる所定の同一階層の複数の葉または節の位置情報について、先頭位置以外の当該階層のある葉または節の位置情報を当該葉または節のひとつ前の葉または節の位置情報からの更新内容を示す位置情報符号によって符号化された位置情報符号を復号する復号方法であって、
前記先頭位置の次の位置情報符号から、当該葉または節が前記先頭位置の葉または節から分岐した階層を判定し、
前記判定により判定した分岐階層に基づいて、当該階層に対応する前記先頭位置の葉または節の位置情報の該分岐した階層の位置番号に対しては１を加算し、同先頭位置の葉または節の位置情報の該分岐した階層より下の全ての階層の位置番号に対しては初期値に初期化する処理を行い、
前記葉または節の次の葉または節についての位置情報符号から当該葉または節とそのひとつ前の前記葉または節とが分岐した階層を判定することにより前記同一階層の複数の葉または節の位置情報符号を順次復号することを特徴とする復号方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、木構造を有する情報の葉または節の位置情報を符号化し、また復号する技術に関し、より詳細には、葉または節の位置情報を効率的に符号化／復号する装置及び方法に関するものである。
【０００２】
【従来の技術】
木構造によるデータ表現手法は、情報処理のさまざまな分野で使用されている。この一例として、ＭＰＥＧ−７最終委員会草案（ＦＣＤ）で用いられている動画像コンテンツ検索情報の表現手法がある。一般に、動画像コンテンツは１つまたは複数のシーンによって構成され、さらに各シーンは１つまた複数のショット、あるいはさらに別のシーンによって構成される、というように階層性を有している。
【０００３】
ＭＰＥＧ−７では、動画像コンテンツの検索時の利便性を高めるために、ショットの動き強度や色頻度などの特徴を示す検索情報を各ショットに付加する際の記述手法が規定されているが、前記階層性を表現するため、図１１に示すような木構造からなる表現手法を用いている。
【０００４】
図１１に示す例では、動画像コンテンツはシーン＃１とシーン＃２の２つのシーンから構成され、さらにシーン＃１はショット＃１−１からショット＃１−５までの５つのショットから構成されている。シーン＃２はショット＃２−１のみから構成されている。また、それぞれのショットには検索情報が付加されている。
【０００５】
木構造としては、動画像コンテンツが根にあたり、シーン及びショットが節にあたる。節の中でも、シーンの階層は根から見て最初の分岐先に相当するので、第１階層の節にあたる。また、ショットの階層は第２階層の節にあたる。そして、各検索情報が葉にあたる。また各シーン、各ショットは番号の小さいものほど前のシーン、ショットに相当する。
【０００６】
ここで、葉にあたる検索情報をまとめて保存したいという要求があった場合、検索情報自体を保存するだけでは十分ではなく、その検索情報の位置情報を同時に保存する必要がある。言い換えると、その検索情報がシーン番号何番のショット番号何番に関するものであるかという情報が必要となる。この位置情報の表現手法として、ＭＰＥＧ−７最終委員会草案で用いられているものを以下に説明する。
【０００７】
前記委員会草案では、ある節の下層に位置するすべての節について順に１番、２番と連番をつけ、根から葉に至るまでに経由する全ての節について、該連番を列挙することで位置情報を表現している。
【０００８】
この位置情報生成方法の具体例を検索情報＃１−３の場合について説明する。まず第１階層を見ると、検索情報＃１−３が属するシーン＃１は、根にあたる動画像コンテンツにぶら下がった一番左側の節である。このため、第１階層の位置情報は１番となる。
【０００９】
次に、第２階層を見ると、検索情報＃１−３が属するショット＃１−３は１階層上の節にあたるシーン＃１にぶら下がった節の中で左から３番目の節である。このため、第２階層での位置情報は３番となり、第１階層とあわせて（１、３）が該検索情報＃１−３の位置情報となる（厳密には、これは節の位置情報を表している。検索情報の階層は第３階層の葉にあたるが、図１１ではショット１つに対して検索情報の数が１つに限られているために、節の位置情報がそのまま葉である検索情報の位置情報として与えられる。葉が複数付される場合にはさらに葉の番号が追加される）。
【００１０】
尚、以降の説明中においては、上述のような形式による位置情報を絶対形式による位置情報と呼ぶこととする。この形式で全ての葉の位置情報を一意に表現することが可能である。
【００１１】
続いて、この絶対形式で位置情報を保存するのに必要なビット数を算出する。各階層にある全ての節を表現するのに必要なビット数を算出するには、最大の分岐可能数を知る必要がある。例えば、第１階層、第２階層とも各節について最大で８分岐までできるとすれば、各階層の節を表現するのにそれぞれ３ビット必要になる。
【００１２】
従って、１つの葉の位置情報を保存するためには、３×２＝６ビットが必要となる。図１１においては６つの葉が存在しており、全ての葉の位置情報を保存するには、６ビット×６＝３６ビットが必要となる。以上の規則にしたがって、図１１における全ての検索情報の位置情報を符号化した例を図１２に示す。
【００１３】
【発明が解決しようとする課題】
しかしながら、上述した従来の技術においては、全ての葉または節について絶対的な位置情報を符号化するため、１階層の最大分岐数が増加するに従って、葉または節の位置情報を保存するためのビット量が増加するという問題がある。一般には、ひとつの動画像コンテンツには非常に多数のシーンまたはショットが含まれているため、最大の分岐可能数も膨大な数になり、この問題は無視できない。
【００１４】
本発明は、上記課題に鑑みてなされたものであり、少ないビット数で効率良く葉または節の位置情報を符号化／復号することができる符号化／復号装置及び方法を提供するものである。
【００１５】
【問題を解決するための手段】
本願の第１の発明は、１つまたは複数の階層からなり、１つの節は１つ下の階層に１つまたは複数の葉または節を持ち、該１つまたは複数の葉または節が初期値から始まる連番の位置番号が付されて区別された木構造の同一階層内の複数の葉または節の位置情報を符号化する符号化装置であって、当該複数の葉または節の位置情報が、前記木構造の根から前記同一階層にある葉または節に至るまでに経由する分岐可能な階層の葉または節に付された前記位置番号の値の列で与えられ、前記同一階層の先頭の葉または節の位置情報は任意の手法により符号化されるものであり、前記同一階層にある複数の葉または節のうち、前記先頭の葉または節以外の葉または節について、ある葉または節とそのひとつ前の葉または節とがどの階層で分岐したかをそれぞれの位置情報を比較して判定する分岐階層判定手段と、前記分岐のあった階層に対応する符号を、該葉または節の位置情報のひとつ前の葉または節の位置情報からの更新内容を示す位置情報符号として出力する位置情報符号化手段とを備えた符号化装置を特徴とする。
【００１６】
本願の第２の発明は、さらに、前記木構造内の分岐可能な階層数を算出する階層数算出手段と、該分岐可能な階層数に基づき、位置情報符号に必要なビット数を算出するビット数算出手段とを備え、前記位置情報符号化手段は、前記算出されたビット数内で符号化することを特徴とする。
【００１８】
本願の第３の発明は、１つまたは複数の階層からなり、１つの節は１つ下の階層に１つまたは複数の葉または節を持ち、該１つまたは複数の葉または節が初期値から始まる連番の位置番号が付されて区別された木構造の同一階層内の複数の葉または節の位置情報を符号化する符号化方法であって、当該複数の葉または節の位置情報が、前記木構造の根から前記同一階層にある葉または節に至るまでに経由する分岐可能な階層の葉または節に付された前記位置番号の値の列で与えられ、前記同一階層の先頭の葉または節の位置情報は任意の手法により符号化されるものであり、前記同一階層にある複数の葉または節のうち、前記先頭の葉または節以外の葉または節について、ある葉または節とそのひとつ前の葉または節とがどの階層で分岐したかをそれぞれの位置情報を比較して判定し、前記分岐のあった階層に対応する符号を、該葉または節の位置情報のひとつ前の葉または節の位置情報からの更新内容を示す位置情報符号として出力する符号化方法を特徴とする。
【００１９】
本願の第４の発明は、１つまたは複数の階層からなり、１つの節は１つ下の階層に１つまたは複数の葉または節を持ち、該１つまたは複数の葉または節が初期値から始まる連番の位置番号が付されて区別された木構造によって構成され、前記木構造の根から同一階層にある葉または節に至るまでに経由する分岐可能な階層の葉または節に付された前記位置番号の値の列によって与えられる所定の同一階層の複数の葉または節の位置情報について、当該階層の先頭位置以外のある葉または節の位置情報を当該葉または節のひとつ前の葉または節の位置情報からの更新内容を示す位置情報符号によって符号化した位置情報符号を復号する復号装置であって、前記位置情報符号から、ある葉または節とそのひとつ前の葉または節とが分岐した階層を判定する分岐階層判定手段と、前記判定により判定した分岐階層に基づいて、当該階層に対応する前記ひとつ前の葉または節の位置情報の該分岐した階層の位置番号に対しては１を加算し、同前記ひとつ前の葉または節の位置情報の該分岐した階層より下の全ての階層の位置番号に対しては初期値に初期化する処理を行うことで、前記ひとつ前の葉または節の位置情報から該葉または節の位置情報を求める位置情報更新手段を備え、前記所定の階層の先頭位置の位置情報に基づいて順次前記同一階層の複数の葉または節の位置情報符号を復号する復号装置を特徴とする。
【００２１】
本願の第５の発明は、１つまたは複数の階層からなり、１つの節は１つ下の階層に１つまたは複数の葉または節を持ち、該１つまたは複数の葉または節が初期値から始まる連番の位置番号が付されて区別された木構造によって構成され、前記木構造の根から前記同一階層にある葉または節に至るまでに経由する分岐可能な階層の葉または節に付された前記位置番号の値の列によって与えられる所定の同一階層の複数の葉または節の位置情報について、先頭位置以外の当該階層のある葉または節の位置情報を当該葉または節のひとつ前の葉または節の位置情報からの更新内容を示す位置情報符号によって符号化された位置情報符号を復号する復号方法であって、前記先頭位置の次の位置情報符号から、当該葉または節が前記先頭位置の葉または節から分岐した階層を判定し、前記判定により判定した分岐階層に基づいて、当該階層に対応する前記先頭位置の葉または節の位置情報の該分岐した階層の位置番号に対しては１を加算し、同先頭位置の葉または節の位置情報の該分岐した階層より下の全ての階層の位置番号に対しては初期値に初期化する処理を行い、前記葉または節の次の葉または節についての位置情報符号から当該葉または節とそのひとつ前の前記葉または節とが分岐した階層を判定することにより前記同一階層の複数の葉または節の位置情報符号を順次復号する復号方法を特徴とする。
【００２２】
【発明の実施の形態】
以下、本発明の第１の実施形態に係る符号化装置について、図１乃至図３、図１１を用いて説明する。
【００２３】
本実施形態においては、図１１に示した木構造を有する動画像コンテンツの検索情報（葉）及びその位置情報を符号化対象とした場合について説明する。但し、本発明によって新たに開示されるのは、このうち位置情報の符号化／復号についてである。図１１において、該動画像コンテンツはシーン＃１とシーン＃２の２つのシーンから構成され、さらにシーン＃１はショット＃１−１からショット＃１−５までの５つのショットから構成されている。シーン＃２はショット＃２−１のみから構成されている。また、それぞれのショットには検索情報が付加されている。木構造としては、各シーン及び各ショットが節にあたり、各検索情報が葉にあたる。また各シーン、各ショットは番号の小さいものほど前のシーン、前のショットに相当する。
【００２４】
図１１の検索情報を利用した動画像コンテンツの検索を行うためには、従来技術として上述したように、各検索情報に絶対形式で表した位置情報を付加しておけば良い。これにより、シーン番号をキーとした検索にも、ショット番号をキーとした検索にも柔軟に対応することができる。しかし、動画像コンテンツ内の検索情報のみを順に並べて保存したり伝送したりする場合、位置情報をより効率良く符号化する必要が生ずる。この必要性を満たすため、図１に示した本実施形態による位置情報符号化装置を用いる。
【００２５】
本実施形態の概略構成を示す図１において、階層数判定部１０１では、木構造が根から符号化対象となる検索情報（葉）に至るまでに分岐可能な階層を何階層持っているかを判定する。図１１の木構造は２階層の分岐可能な層を有しているので、２が出力される。尚、図１１の木構造の例では、全ての節の階層が分岐可能な階層となっているが、本実施形態の対象とする木構造はこれに限られるものではなく、例えば分岐が許されない節の階層が存在しても構わない。その場合は、分岐可能な節の階層のみを数えるものとする。
【００２６】
また、図１１の木構造の例では、最下層の葉の階層で分岐不可（１つのショットが１つの検索情報しか持たない）となっているが、本実施形態の対象とする木構造はこれに限られるものではなく、分岐が許される（１つのショットが複数の検索情報を持つ）としてもよい。その場合には、葉の階層も分岐可能な階層として数えられるものとする。
【００２７】
ビット数算出部１０２では、階層数判定部１０１から得られる階層数に基づいて、位置情報を表現するのに必要なビット数を計算する。ビット数は以下の＜式１＞によって算出される数以上で最も近い整数として与えられる。
【００２８】
ｌｏｇ２（階層数＋１）・・・＜式１＞
すなわち、図１１の木構造に対しては、ｌｏｇ２（２＋１）以上で最も近い整数であるから、２が出力される。
【００２９】
尚、本実施形態においては、階層数判定部１０１及びビット数算出部１０２を備えたものについて説明しているが、本発明の位置情報符号化装置にはこれらの構成要素は必ずしも必要でなく、例えば予め必要ビット数を規定しておく方法も考えられる。
【００３０】
前位置情報保存部１０３には、１つ前に入力された位置情報が保存されている。位置情報とは、例えば図１１の動画像コンテンツでは、葉にあたる各検索情報がどのシーンのどのショットに属しているかを示す情報であり、より具体的には、動画像コンテンツを木構造と見た場合の絶対形式による位置情報が考えられる。
【００３１】
一例として、検索情報＃１−３はシーン番号１番の中のショット番号３番に属していることから、絶対形式の位置情報としては（１、３）となる。ただし、該入力となる位置情報はシーン番号、ショット番号に限られるものではなく、例えば各シーン、各ショットの開始時間などを使用する方法も可能である。
【００３２】
また、図１１において、最初の葉は検索情報＃１−１であり、以下検索情報＃１−２、＃１−３、＃１−４、＃１−５、＃２−１の順となることから、例えば検索情報＃１−３の位置情報を符号化する際に、前位置情報保存部１０３に保存されている位置情報は検索情報＃１−２の位置情報ということになる。
【００３３】
分岐階層判定部１０４では、入力されてきた位置情報と、前位置情報保存部１０３に保存されている位置情報とを比較し、両者がどの階層で分岐したかを判定してその階層を示す情報を出力する。分岐した階層とは、図１１の木構造で見た場合、入力されてきた位置情報および前位置情報保存部１０３に保存されている位置情報に対応する検索情報のそれぞれまで木構造を根から辿ったときに、枝分かれして初めて異なる節に分かれる階層を指す。上記の絶対形式の位置情報では、左から順に値を見て、初めて値が異なった箇所が分岐階層にあたる。
【００３４】
例えば、入力されてきた位置情報が絶対形式で（１、３）に属するものである場合を例にとると、前位置情報保存部１０３には（１、２）に属する位置情報が保存されているので、両者の間には分岐可能な一番下の階層、すなわちショットの階層で分岐が発生し、それより上の階層はまったく同一であることがわかる。従って、分岐階層判定部１０４は、一番下の階層を示す情報として例えば１を出力する。
【００３５】
或いは、入力されてきた位置情報が（２、１）に属するものであれば、前位置情報保存部１０３には（１、５）に属する位置情報が保存されており、両者の間には下から２番目の分岐可能な階層、すなわちシーンの階層で分岐が発生していることがわかるので、下から２番目の階層を示す情報として例えば２を出力する。
【００３６】
尚、本実施形態では、ひとつ前の位置情報と入力された位置情報とを比較することにより、分岐階層を判定する手法をとっているが、本発明の位置情報符号化装置はこれに限られるものではなく、例えば木構造の規則性が予め判明しているような場合であれば、入力された位置情報のみから分岐階層を判定することも可能であり、この場合には前位置情報保存部１０３は不要となる。
【００３７】
位置情報符号化部１０５は、分岐階層判定部１０４から出力される階層に対応する符号を、ビット数算出部１０２から出力されるビット数内で生成し、これを位置情報符号として出力する。ただし、最初に入力された位置情報については変化を判定することができないため、シーン番号、ショット番号を直接出力するなどして対応する。
【００３８】
また、最後の位置情報、すなわち検索情報＃２−１の位置情報を符号化して出力した後には、位置情報がこれ以上無いことを示す終了コードを出力する。或いは、別の例として、図１１の木構造の一部を切り出してきて本実施形態の符号化装置への入力とした場合、例えばシーン＃１以下を切り出してきた場合には、検索情報＃１−５の位置情報を符号化した後に終了コードを出力するものとする。以上に基づいた具体的な符号割り当ての例を表１に示す。
【００３９】
【表１】
0004120980.tif 000002
【００４０】
次に、本実施形態の位置情報符号化装置と表１の符号割り当てに基づいて、図１１に示す動画像コンテンツの検索情報の位置情報を符号化した例を図２に示す。
【００４１】
尚、本実施形態では、ビット数算出部１０２から出力されたビット数は、位置情報符号化部１０５が符号化を行う際に参照するのみで、位置情報符号化装置から明示的に出力されてはいないが、位置情報符号の中にこのビット数情報を含めて出力する手法も考えられる。
【００４２】
また、本実施形態では、図１１に示したシーン１階層、ショット１階層の２階層の木構造を対象としたが、本発明の位置情報符号化装置はこれに限られるものではなく、任意の構成、階層数の木構造の位置情報符号化に利用することができる。例えば、１つのシーンがさらに複数のシーンに分割される場合もありうるが、本発明の位置情報符号化装置はこのような場合にも問題なく適用することが可能である。
【００４３】
或いは、図３に示すようなより複雑な木構造に対しても適用することも可能である。図３においては、シーン＃２の下にさらにシーン＃２−１とシーン＃２−２が存在し、このうちシーン＃２−１はショット＃２−１−１とショット＃２−１−２から構成されている。この場合、同一の階層に属する検索情報のみを抽出した上で、本発明の位置情報符号化装置を適用することにより、効率的な位置情報の符号化を実現することができる。
【００４４】
例えば、検索情報＃１−１から＃１−５までは同一の階層に属しているため、これらの検索情報の位置情報を符号化するに際しては、本発明の位置情報符号化装置で直接取り扱うことができる。一方、検索情報＃２−１−１から＃２−１−２までは検索情報＃１−１から＃１−５とは別の階層に属しているため、検索情報＃１−１から＃１−５と同時に取り扱うことはできないものの、検索情報＃２−１−１と＃２−１−２は同一の階層に属しているため、同様にして取り扱うことができる。
【００４５】
以上のとおり、本実施形態では、木構造の葉の位置情報をそのまま記述するのではなく、１つ前の葉の位置情報との変化点のみを記述することにしているので、上記従来例による位置情報の表現手法より少ないビット数で効率良く位置情報を符号化することができる。
【００４６】
図１１に示した検索情報の位置情報を符号化する例において、従来例による方法が図１２に示すとおり３６ビットを必要としているのに対し、本実施形態による方法では図２に示すとおり１６ビットしか必要としない。この例における両者の差はわずかであるが、実際にはひとつの動画コンテンツに属するシーンの数は数百にも及ぶことが十分考えられ、この場合には両者の間の差は非常に大きくなる。
【００４７】
次に、本発明の第２の実施形態に係る復号装置について、図４を用いて説明する。本実施形態の位置情報復号装置においては、図２に示した位置情報符号を入力とした場合について説明する。図２の位置情報符号は、図１１の木構造における検索情報（葉）の位置情報を符号化した位置情報符号であり、上述した第１の実施形態の位置情報符号化装置で符号化することができるが、これに限定されるものではない。
【００４８】
本実施形態の概略構成を示す図４において、階層数判定部５０１は、復号対象の木構造が分岐可能な階層を何階層持っているかを判定する。ビット数算出部５０２は、階層数判定部５０１の判定した階層数から、符号化された位置情報が何ビットから生成されているかを算出する。これらの詳細な動作は、図１とともに上述した第１の実施形態における階層数判定部１０１、ビット数算出部１０２と同様であるので、ここでは省略する。
【００４９】
尚、本発明の復号装置には、階層数判定部５０１及びビット数算出部５０２は必ずしも必要ではなく、例えばビット数算出部５０２から出力されるビット数にあたる情報が位置情報符号の中に含めて符号化されていれば、それをビット数算出部５０２の出力の代用とすることも可能である。
【００５０】
前位置情報保存部５１１には、現在復号対象の位置情報の１つ前に復号された位置情報が保存されている。分岐階層判定部５１２では、ビット数算出部５０２から出力されたビット数に基づいて、現在復号対象の位置情報と前位置情報保存部５１１に保存されている位置情報とがどの階層で分岐したかを判定する。例えば、図２において左から６番目のブロックの符号が復号対象であった場合、現在の復号対象の符号が１０であることから、表１より下から２番目の階層、すなわちシーンの階層で分岐があったことがわかる。
【００５１】
位置情報更新部５１３は、前位置情報保存部５１１に保存されている位置情報の中で、分岐階層判定部５１２から出力された階層の位置番号を１増加させ、その上で、該階層より下の全ての階層の位置番号を初期値に初期化する。該階層より上の階層の位置番号はそのまま保持する。ここでの位置番号とは、例えば絶対形式で表わされた位置情報の場合は、各階層内の節に振られた連続番号に相当する。
【００５２】
例えば、図２において左から６番目のブロックが復号対象であった場合、前位置情報保存部５１１には５番目のブロックの符号から復号された検索情報＃１−５の位置情報である（１、５）が保存されている。
【００５３】
分岐階層判定部５１２からは、分岐があった階層が下から２番目の階層である旨が出力されてくるので、下から２番目の階層の位置番号を１加算して（２、５）とする。その上で、下から２番目の階層より下の階層、すなわちシーンより下の階層の位置番号を初期値である１に初期化し（２、１）とする。
【００５４】
これによって、最終的に出力される位置情報は（２、１）となり、検索情報＃２−１の位置情報が正しく復号されたことになる。この位置情報は、次の符号の復号に備えて、前位置情報保存部５１１に保存される。最後に、分岐階層判定部５１２が終了コードを受け取った時点で、位置情報の復号を終了する。
【００５５】
次に、本発明の第３の実施形態に係る符号化装置について、図５及び図６を用いて説明する。
【００５６】
図５は本実施形態の概略構成を示す機能ブロック図である。なお、図５中に示された位置情報符号化部６０５の内部構成は図１で与えられるものとする。図６は本実施形態の符号化装置の符号化対象であり、木構造を有する動画像コンテンツの検索情報を示す説明図である。図６のものは、図１１とともに上述したものと類似しているため、その差異のみを説明する。すなわち、図６においては、ショット＃１−３に属する検索情報が欠落している。言い換えると、ショット＃１−３の節には葉が存在しない。
【００５７】
尚、本実施形態では、葉にあたる検索情報が欠落している例を挙げて説明するが、本発明の位置情報符号化装置は、他の種類の検索情報が混在していてこれを区別したい場合等にも適用することが可能である。
【００５８】
例えば、図６におけるシーン＃１−１、＃１−２、＃１−４及び＃１−５には検索情報Ａが記述されている一方、シーン＃１−３には検索情報Ａは記述されておらず、代わりに検索情報Ｂが記述されている場合である。この構成の動画像コンテンツ検索情報で、検索情報Ａに関する位置情報のみを取り出して使用する場合も、本実施形態における検索情報が欠落している例と同様に取り扱うことができる。
【００５９】
図６に示すような葉の欠落があった場合、位置情報符号化部６０５は、欠落の有無にかかわらずに連番として位置情報を符号化しておき、欠落があった箇所については別手段で符号化することにより、位置情報を破綻なく符号化することができる。この別手段の具体的手法としては、図６における検索情報を符号化する際に、該欠落があった箇所に検索情報の代わりに欠落情報を符号化する手法が可能である。
【００６０】
欠落位置判定部６０１は、入力された位置情報が絶対形式で連番となっておらず欠番がある場合に、スイッチ６０２を操作する。具体的には、連番となっている場合には、スイッチ６０２を検索情報符号化部６０３側に操作し、検索情報符号が出力されるようにする。
【００６１】
一方、欠番となっている場合には、スイッチ６０２を欠落情報生成部６０４側に操作し、検索情報符号の代わりに、欠落情報符号が出力されるようにする。この時、位置情報符号化部６０５は該欠番に対応する位置情報符号を出力する。これにより、欠落部分については、欠落情報が記載された検索情報符号を得ることができ、したがって欠番の位置を知ることができる。
【００６２】
尚、本実施形態においては、検索情報符号化部６０３を備えているが、本発明の符号化装置はこれに限られるものではなく、例えば検索情報はまったく符号化せずに、そのままの形で出力することも可能である。本発明では、検索情報自体の符号化／復号については言及しない。
【００６３】
また、本実施形態では、欠落情報を検索情報符号に含めて符号化しているが、本発明の符号化装置はこれに限られるものではなく、例えば欠落のある葉の絶対形式による位置情報を別手段で符号化するものも考えられる。
【００６４】
次に、本発明の第４の実施形態に係る復号装置について、図７を用いて説明する。尚、第２の実施形態と同一部分には同一符号を付し、その説明は省略する。
【００６５】
本実施形態においては、図６に示した木構造に対して符号化された情報を入力とした場合について説明する。ここで、本実施形態の入力となる位置情報符号及び検索情報符号は、例えば図５とともに上述した第３の実施形態の位置情報及び検索情報符号化装置によって符号化された位置情報符号及び検索情報符号が挙げられるが、これに限定されるものではない。また、本実施形態で取り扱うことが可能な木構造も、図６のものに限定されない。
【００６６】
本実施形態の概略構成を示す図７において、検索／欠落情報復号部８０１では、入力された検索情報符号を復号する。ここで、検索情報が復号された場合には、検索情報を出力する。一方、欠落情報が復号された場合には、位置情報更新部８０２にその旨を通知し、検索情報は出力しない。
【００６７】
位置情報更新部８０２は、図４とともに上述した第２の実施形態における位置情報更新部５１３に類似した動作をする。異なるのは、検索／欠落情報復号部８０１から欠落情報が復号された旨が通知されると、その部分の位置情報を出力せず、次の位置情報の復号に進むことである。これによって、検索情報が欠落している部分を正しくスキップして、処理を続けることが可能となる。
【００６８】
尚、本実施形態においては、位置情報更新部８０２内で欠落情報に伴うスキップ処理を行っているが、本発明の復号装置はこれに限られるものではなく、例えば位置情報更新部８０２には、図４の位置情報更新部５１３とまったく同一の動作をさせておき、欠落の通知が行われた葉については位置情報を利用しないという方法を用いることも可能である。
【００６９】
次に、本発明の第５の実施形態に係る符号化装置について、図８及び図９を用いて説明する。図８は本実施形態の概略構成を示す機能ブロック図である。なお、図８における位置情報符号化部６０５の内部構成も、上述した第３の実施形態を示す図５と同様に、図１で与えられるものとする。
【００７０】
本実施の形態においても、第３の実施形態と同様に、図６に示した検索情報の欠落を含む木構造を有した検索情報の位置情報を符号化対象とする。第３の実施形態と本実施形態との差異を説明すると、上記第３の実施形態では欠落情報を検索情報符号に含めて符号化しているのに対し、本実施形態では欠落情報を位置情報符号に含めて符号化する点が異なっている。
【００７１】
図８で示された位置情報符号化装置において、欠落位置判定部８１１は、入力された位置情報を監視し、位置情報の欠落が判定されるとスイッチ８１２を切替えて欠落コードが位置情報符号に加えられるようにする。その後、スイッチ８１２を元の位置に戻し、欠落位置に対応する位置情報の符号を位置情報符号化部６０５から得て位置情報符号に加える。すなわち、欠落位置では、対応する位置情報を表す符号の直前に欠落を示す欠落コードが付加される。言い換えると、欠落コードは、欠落コードの次に来る符号によって更新される位置に検索情報の欠落があることを表す。
【００７２】
表２に、位置情報の欠落を示す欠落コードを含めた位置情報に対する符号割り当ての例を示す。
【００７３】
【表２】
0004120980.tif 000003
【００７４】
この場合、位置情報を表現するためのビット数は、階層数に加えて終了コードと欠落コードを表すのに必要なビット数であるため、以下の＜式２＞によって算出される数以上で最も近い整数として与えられる。
【００７５】
ｌｏｇ２（階層数＋２）・・・＜式２＞
すなわち、図６の木構造に対しては、ｌｏｇ２（２＋２）以上で最も近い整数であるから、ビット数２が与えられる。（このビット数は位置情報符号化部６０５の内部構成のビット数算出部１０２で算出される。）
図９に、表２の符号を使って図６に示した検索情報の位置情報を符号化した位置情報符号の例を示す。
【００７６】
図９において、＃１−３の位置情報符号の直前に入れられた欠落コードは、欠落コードの直後の＃１−３の位置情報符号で表された位置で検索情報が欠落していることを示す。このようにして、図６に示したような欠落のある検索情報についても、位置情報を符号化することができる。
【００７７】
次に、本発明の第６の実施形態に係る復号装置について、図１０を用いて説明する。なお、第２あるいは第４の実施形態と同一部分には同一符号を付し、その説明は省略する。
【００７８】
本実施形態の位置情報復号装置では、図９に示した位置情報符号を入力とした場合について説明する。図９の位置情報符号は、図６に示した木構造を有する検索情報における検索情報（葉）の位置情報を符号化した位置情報符号であり、上述した第５の実施形態の位置情報符号化装置によって得ることができるが、本実施形態の入力となる位置情報符号はこれに限定されるものではない。また、本実施形態で取り扱うことが可能な木構造も、図６のものに限定されない。
【００７９】
本実施形態の概略構成を示す図１０において、ビット数算出部１００１は、階層数判定部５０１の判定した階層数から、＜式２＞に従って位置情報符号のビット数を算出する。第２あるいは第４の実施形態と同様、本発明の復号装置には、階層数判定部５０１及びビット数算出部１００１は必ずしも必要ではない。例えば該ビット数が位置情報符号の中に含めて符号化されていれば、ビット数算出部１００１の出力の代わりにそれを利用すればよい。
【００８０】
本実施形態の概略構成を示す図１０において、分岐階層／欠落判定部１００２は、上記ビット数分の位置情報符号を順に読み込み、分岐階層を示す位置情報符号であるか、欠落コードであるか、または終了コードであるかを判定する。分岐階層を示す位置情報符号であれば、分岐する階層を判定して位置情報更新部８０２に出力する。欠落コードであれば、欠落処理部１００３にそれを通知する。終了コードであれば復号を終了する。
【００８１】
欠落処理部１００３は、欠落コードが復号された旨を受け取ると、一旦保持し、位置情報更新部８０２が次に入力された位置情報符号を用いて位置情報を更新する際に欠落を通知する。位置情報更新部８０２は、第４の実施形態と同様に、欠落が通知されるとその部分の位置情報を出力せず、次の位置情報の復号に進む。この処理によって、欠落箇所にあたる位置情報は出力されることなく、正しい位置情報のみが出力されて得ることができる。
【００８２】
尚、本実施形態においても、第４の実施形態と同様、復号装置での処理は位置情報更新部８０２内で行う欠落に伴ったスキップ処理に限られるものではない。例えば位置情報更新部８０２には図４の位置情報更新部５１３とまったく同一の動作をさせておき、欠落の通知が行われた葉については位置情報を利用しないという方法を用いることも可能である。
【００８３】
以上説明した本発明の第１乃至第６の実施形態では、符号化対象として動画像コンテンツの検索情報を用いた場合について説明したが、本発明はこれに限られるものではなく、木構造を有し、かつ同一階層の各節または葉の間に順序関係があるあらゆるデータに対して適用することが可能である。
【００８４】
また、以上で説明した本発明の第１乃至第６の実施形態では、木構造中の検索情報にあたる葉の位置情報を符号化／復号する装置／方法を示したが、この符号化／復号する装置／方法は、そのまま木構造中の節の位置情報を符号化／復号する場合にも適用することができる。このことは、位置情報を符号化／復号する各節に対して、その節の下位に連結している節または葉を全て取り去った時に（あるいはその節とその節の下位に連結している節または葉を全て一まとめにして１つの葉と捉えた時に）、位置情報を符号化／復号するそれぞれの節を葉に見立てることができることから、明らかである。
【００８５】
すなわち、本発明は、木構造を有し、かつ同一階層の各節または葉の間に順序関係があるあらゆるデータの葉または節の位置情報に対して、適用することが可能である。
【００８６】
【発明の効果】
本発明によれば、木構造の葉または節の位置情報をそのまま記述するのではなく、１つ前の葉または節の位置情報との変化点のみを記述することとしているので、少ないビット数で効率良く位置情報を符号化／復号することができる。
【００８７】
また、葉または節が連番状に存在することを仮定している場合であっても、葉または節の欠落に関する情報を通知することにより、葉または節の位置情報を正しく符号化／復号することが可能である。
【図面の簡単な説明】
【図１】本発明の第１の実施形態にかかる符号化装置の概略構成を示す機能ブロック図である。
【図２】本発明の第１の実施形態にかかる符号化装置によって符号化された位置情報符号を示す説明図である。
【図３】本発明の第１の実施形態において用いる木構造を有する検索情報の別の形態例を示す説明図である。
【図４】本発明の第２の実施形態にかかる復号装置の概略構成を示す機能ブロック図である。
【図５】本発明の第３の実施形態にかかる符号化装置の概略構成を示す機能ブロック図である。
【図６】本発明の第３乃至第６の実施形態において用いる木構造を有する検索情報の例を示す説明図である。
【図７】本発明の第４の実施形態にかかる復号装置の概略構成を示す機能ブロック図である。
【図８】本発明の第５の実施形態にかかる符号化装置の概略構成を示す機能ブロック図である。
【図９】本発明の第５の実施形態にかかる符号化装置によって符号化された位置情報符号を示す説明図である。
【図１０】本発明の第６の実施形態にかかる復号装置の概略構成を示す機能ブロック図である。
【図１１】木構造を有する検索情報の一形態例を示す説明図である。
【図１２】従来技術によって符号化された位置情報符号を示す説明図である。
【符号の説明】
１０１  階層数判定部
１０２  ビット数算出部
１０３  前位置情報保存部
１０４  分岐階層判定部
１０５  位置情報符号化部
５０１  階層数判定部
５０２  ビット数算出部
５１１  前位置情報保存部
５１２  分岐階層判定部
５１３  位置情報更新部
６０１  欠落位置判定部
６０２  スイッチ
６０３  検索情報符号化部
６０４  欠落情報生成部
６０５  位置情報符号化部
８０１  検索／欠落情報復号部
８０２  位置情報更新部
８１１  欠落位置判定部
８１２  スイッチ
１００１  ビット数算出部
１００２  分岐階層／欠落判定部
１００３  欠落処理部
【図１】
0004120980.tif 000004
【図２】
0004120980.tif 000005
【図３】
0004120980.tif 000006
【図４】
0004120980.tif 000007
【図５】
0004120980.tif 000008
【図６】
0004120980.tif 000009
【図７】
0004120980.tif 000010
【図８】
0004120980.tif 000011
【図９】
0004120980.tif 000012
【図１０】
0004120980.tif 000013
【図１１】
0004120980.tif 000014
【図１２】
0004120980.tif 000015