(57)【要約】      （修正有）【課題】ナビゲーションノードに関連するマルチメディアデータを細分化する方法を提供する。【解決手段】ノード（Ｎ'ｉ）は、関連するデータアイテム（Ｄ'ｉ）と少なくとも１つ次のノードとへのアクセスを制御する。ノードとそれに関連するデータとは、一時セル（Ｃ'ｔ）にグループ化され、一時セルは、開始ノード及びこのノードに関連するデータを有し、一時セルにグループ化された各ノードは、一時セルのサイズが閾値に達するまでこの一時セルに既に含まれているノードに追従し、一対の２つのノードに関連するデータに共通のデータの数に依存したパラメータを最小化する、一時セルの互いに追従する一対のノードが、識別され、決定セルは、一対の第１のノードに関連するデータより先に一時セルにグループ化されたデータで形成される。【選択図】図２
2004254272.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲーションノード（Ｎ’５，Ｎ’６，Ｎ’７，…Ｎ’１１）に関連するマルチメディアデータ（Ｄ’５，Ｄ’６，Ｄ’７，…Ｄ’１１）を細分化する方法であって、ノード（Ｎ’ｉ）は、関連するデータアイテム（Ｄ’ｉ）と少なくとも１つ次のノード（Ｎ’ｉ＋１）とへのアクセスを制御する方法において、
ノード（Ｎ’６，Ｎ’７，Ｎ’８及びＮ’９）と連続する形態でそれに関連するデータ（Ｄ’６，Ｄ’７，Ｄ’８及びＤ’９）とが、一時セル（Ｃ’ｔ）にグループ化され、該一時セル（Ｃ’ｔ）は、開始ノード（Ｎ’５）及びこのノードに関連するデータ（Ｄ’５）を有し、前記一時セルにグループ化された各ノード（Ｎ’ｉ＋１）は、該一時セルのサイズが閾値に達するまでこの一時セルに既に含まれているノード（Ｎ’ｉ）に追従し、
一対の２つのノード（Ｎ’７，Ｎ’８）に関連するデータ（Ｄ’７，Ｄ’８）に共通のデータ（Ｄ’ｃ）の数に依存したパラメータ（Ｔｉ）を最小化するように、前記一時セル（Ｃ’ｔ）の互いに追従する一対のノード（Ｎ’７，Ｎ’８）が、識別され、決定セル（Ｃ’５，Ｃ’６，Ｃ’７）が、該一対の第１のノード（Ｎ’７）に関連する該データ（Ｄ’７）より先に、前記一時セルにグループ化されたデータ（Ｄ’５，Ｄ’６，Ｄ’７）で形成されることを特徴とするマルチメディアデータを細分化する方法。
【請求項２】
前記識別された一対の２つのノード（Ｎ’７，Ｎ’８）に関連する前記データ（Ｄ’７，Ｄ’８）に共通のデータ（Ｄ’ｃ）の数に比例して、一対のノードによって最小化される前記パラメータ（Ｔｉ）が、決定されることを特徴とする請求項１に記載の方法。
【請求項３】
前記一時セルの閾値サイズは、このセルにグループ化されるデータの量の関数として、又は、このセルにグループ化されるノードの数の関数として決定されることを特徴とする請求項１又は２に記載の方法。
【請求項４】
第１の細分化中に行われる操作を繰り返すことによって第２のノード（Ｎ’ｉ＋１）に追従するデータ（Ｄ’ｉ）の細分化を実行するために、開始ノードとして又は未だグループ化されていない他のノードとして識別された前記一対の第２のノード（Ｎ’ｉ＋１）が用いられることを特徴とする請求項１から３のいずれか１項に記載の方法。
【請求項５】
前記パラメータ（Ｔｉ）は、前記識別された一対のノード（Ｎ’７，Ｎ’８）の１つに関連するデータ（Ｄ’７，Ｄ’８）の量に反比例するように決定されることを特徴とする請求項１から３のいずれか１項に記載の方法。
【請求項６】
前記パラメータ（Ｔｉ）は、前記識別された一対のノード（Ｎ’７，Ｎ’８）の第１のノード（Ｎ’７）より先に前記一時セルにグループ化されたノードの数（ｉ−５）と、前記一時セル内のノードの数（Ｔ）との比に比例して決定されることを特徴とする請求項１から５のいずれか１項に記載の方法。
【請求項７】
前記マルチメディアデータは、音声文書、映像文書、プログラム、テキスト文書の少なくとも１つに関するデータを有することを特徴とする請求項１から６のいずれか１項に記載の方法。
【請求項８】
前記映像データは、２又は３次元画像の画像、連続画像、パノラマ、図形データの中の少なくとも１つに対応することを特徴とする請求項６に記載の方法。
【請求項９】
場面又は対象物の視点、隣接するノードに関する画像はこれら場面又はこれら対象物に近接した視点に対応することを特徴とする請求項８に記載の方法。
【請求項１０】
ナビゲーションノードが、特性及び／又は機能の関数としてこれらデータに関係し、これらデータの圧縮が冗長データを削除することによって実行され、維持されたデータは、削除された該データに関連するノードに関係し、これらデータは請求項１から９のいずれか１つに従う細分化方法によって細分化されることを特徴とするマルチメディアデータを細分化する方法。
【請求項１１】
前記データが実画像及び合成画像に関する映像データを有し、前記ナビゲーションノードは、実画像に関するデータへのアクセスを課すことによってマルチメディアデータに関係することを特徴とする請求項９に記載の方法。
【請求項１２】
プログラムがコンピュータ上で実行されるとき、請求項１から１１のいずれか１つに従うマルチメディアデータを細分化する方法のステップを実行するためのプログラムコード指令を有することを特徴とするコンピュータプログラム。
【請求項１３】
データアイテムに関連するノードを用いてデータアイテムにアクセスする手段と、
前ノードと称される第１のノードから、次ノードと称される第２のノードへのアクセスを決定する手段とを有するナビゲーションノードに関連するマルチメディアデータを細分化する装置において、
予め決められた開始ノードで開始し、一時セル内に、このセルが閾値サイズに達するまで関係するノードが互いに追従するデータをグループ化する手段と、
一対の２つのノードに関連するデータに共通のデータの数に比例したパラメータを最小化する一対の次ノードを識別する手段と、
一対の第１のノードとそのノードより前のノードとに関連するデータを有するセルを形成する手段とを有し、
請求項１から１１のいずれか１項に記載の方法を実現するための装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチメディアデータ、特にナビゲーションノードに関連するデータを細分化する方法及び装置に関する。
【０００２】
【従来の技術】
インターネットネットワークのような通信ネットワークを経由して送信されたデータのスループット及びこれらデータの多様性は、多様な性質のデータを送信又は受信するために、これらネットワークを用いる端末及びサーバの数をますます増加している。その多様な性質とは、例えば、音声及び／又は映像文書、プログラム、テキスト、２又は３次元画像を符号化した図形データ、又は新しいデータへのアクセスを可能にするハイパーリンクを有するテキストなどに関する。
【０００３】
文書が種々の性質のデータを有するとき、これら文書及びこれらデータは、以下ではマルチメディアと称される。
【０００４】
符号化／復号化、送信、受信及び／又は表示のような、データＤ０，Ｄ１，Ｄ２，Ｄ３及びＤ４（図１）に対して行われる操作は、これらデータがセルＣ０，Ｃ１，Ｃ２／３及びＣ４にグループ化され又は細分化されると、実行がより簡単でより速い。
【０００５】
このような細分化は、例えば、送信中にこれらデータの多重化を実行したり、又は、受信時に処理を直列に実行することを可能にする。
【０００６】
換言すると、データのセルへの細分化は、例えばバンド幅のように、ネットワークの制限された伝送資源の使用と、データを処理する種々の端末及びサーバの制限されたメモリ容量及び計算容量の使用を最適化する。
【０００７】
さらに、ナビゲーションノードＮ０，Ｎ１，Ｎ２，Ｎ３及びＮ４をデータＤ０，Ｄ１，Ｄ２，Ｄ３及びＤ４に関連づけて後者のアクセスの順番を決定することが知られている。この目的のために、各ノードＮｉは、それに関連するデータＤｉを識別する手段と、少なくとも１つ次のノードＮ（ｉ＋１）を識別する手段とを有する。換言すると、ノードＮ（ｉ＋１）及びそれに関連するデータＤ（ｉ＋１）へのアクセスは、前のノードＮｉで開始される。
【０００８】
図１に示されるように、各セルＣｉはこのセルＣｉに含まれるデータＤｉに関連するノードＮｉを含むことができる。
【０００９】
ナビゲーショングラフは、ノードＮｉが単一の前ノードＮｉ−１及び単一の次ノードＮｉ＋１に接続されるような連続したノードから構成されることができる。この場合、このようなグラフは線形又は１次元といわれる。
【００１０】
反対に、グラフは、ノードＮ１又はＮ４のような、いくつかのノードに接続されるノードを有することができる。その時、ナビゲーショングラフは、非線形又は多次元であるといわれる。この場合、２つのノードＮ２及びＮ４は、同一のノードＮ１の次ノードであってもよい。（それぞれ２つのノードＮ１及びＮ３は、同一のノードＮ４の前ノードであってもよい。）さらに、ノードＮ１はノードＮ０の次であり、ノードＮ２、ノードＮ４及びＮ０は、以下では、Ｎ１の隣接するノードと称される。
【００１１】
異なるセルＣｉ及びＣｋが、同一又は冗長データＤｉ及びＤｋを有するとき、これらセルＣｉ及びＣｋは冗長であるといわれる。これらのような冗長データは、しばしば、同一のデータが種々の用途に用いられるマルチメディア文書に用いられる。例えば、電子ブックにおいて、同一の画像が種々の異なったページの表示に用いられる。この場合、画像に関するデータは、これらページに関係する各セルに存在する。
【００１２】
図形データに関する他の例において、対象物を符号化するデータが、この対象物を有する場面の特別の視点に特有のセルに存在することができる。
【００１３】
しかしながら、冗長セルの処理は同一のデータの繰り返し処理を引き起こすので、データの処理をより速くかつ簡単にするために、データの細分化中に、冗長セルの生成を制限するほうがよい。例えば、冗長セルの送信は、冗長データの繰り返し送信を必要とする。
【００１４】
換言すると、マルチメディアデータの細分化を最適化するために、同一又は冗長データを同一のセルにグループ化するほうがよい。
【００１５】
１組のデータをセルに細分化するために、セルに含まれるデータの量を細分化パラメータとして考慮することによってデータセルを形成することは既知である。換言すると、データセルは、そのセルが一定のサイズに達するまで、隣接するデータをセルにグループ化することによって生成される。このような方法は、冗長セルの形成を避けるように、データの細分化を最適化しないという欠点を有する。
【００１６】
これらデータに関連するナビゲーションノードを用いること、及びこれらデータの特性及び／又は用途を考慮することもまた既知である。この目的のために、各ノードＮｉは、同一の特性又は同一の用途に関するデータをグループ化することによって細分化を可能にするように、ノードに関連するデータの特性及び／又は用途を決定する手段を有する。したがって、文書が数ページのテキストを有するとき、これらページに関するテキストデータＤｉは、セルＣｋのデータＤｉが文書のページｋに特有であるように細分化されてもよい。
【００１７】
その結果、セルＣｋの送信は、文書のページｋに関するデータＤｋを有することとなる。この場合、例えば、第１のデータセルＣ１，Ｃ２，…及びＣｋの受信は、連続するページが送信されている間に、ユーザがページ１，２，…ｋを処理することを可能にする。
【００１８】
他の例によると、３次元における画像を符号化するデータは、一般に、場面及び／又は対象物に関する視点の関数として細分化される。例えば、セルＣｋは、第１の視点に従って場面の表示を構成してもよく、一方、次のセルＣｋ＋１、即ちセルＣｋからアクセスできるセルは、第１のセルＣｋから第２のセルＣｋ＋１への切り替えが視点の変位に対応するように、第１に近接する第２の視点に関するデータを有してもよい。
【００１９】
他の例によると、データがいくつかのメモリ空間（ｒｏｏｍ）を有する常駐域（ｒｅｓｉｄｅｎｃｅ）を符号化するとき、セルＣｋのデータＤｉは、この常駐域のメモリ空間に関係してもよく、一方、次のセルＣｋ＋１のデータＤｎは隣接するメモリ空間に関係してもよい。この場合、セルＣｋから次のセルＣｋ＋１への切り替えは１つのメモリ空間から隣接するメモリ空間への切り替えを表すこととなる。
【００２０】
しかしながら、これら細分化方法は、細分化されたデータの特性及び／又は用途を考慮にいれ、その結果、それらは、図形データ及び音声のような多様な用途が同時に必要とされる種々の性質のマルチメディアデータを細分化するために用いられない。
【００２１】
３次元における画像に関するデータの細分化を実行するために、既知の細分化アルゴリズムは、各ノードが、関連するデータによって符号化される場面及び／又は対象物の視点に関する指示を有するような表示基準を用いる。例えば、雑誌ＳＩＧＧ−ＧＲＡＰＨ，９１に記載の‘Ｖｉｓｉｂｉｌｉｔｙ  ｐｒｅｐｒｏｃｅｓｓｉｎｇ  ｆｏｒ  ｉｎｔｅｒａｃｔｉｖｅ  ｗａｌｋｔｈｒｏｕｇｈｓ’の記事で、ＴＥＬＬＥＲ及びＳＥＱＵＩＮによって述べられている既知の対象物調査アルゴリズムは、画像において符号化された対象物を識別するために実行され、特有なセルをこの対象物に関するデータに割り当てる。
【００２２】
しかしながら、この文書で述べられている方法は、ビルの環境のような、建築環境に特有であり、セルＣｋは、壁のような垂直のパーティションによって制限される画像に関する性質の図形画像を有するように、あらかじめ定義されている。したがって、建築以外の分野に関する図形データを細分化することはできない。したがって、上記に述べた方法に類似する方法で、マルチメディアデータを細分化することはできない。
【００２３】
１９９８年１１月１２日に発行されたＭＤＥＩＡ  ＤＥＳＩＧＮ  ＧＥＳ  ＭＵＬＴＩＭＥＤＩＡ＆ＯＮＬＩＮＥ  ＰＵＢ  による独国特許１９７２３１０２‘Ｖｅｒｆａｈｒｅｎ  ｚｕｍ  Ｄａｒｓｔｅｉｌｅｎ  ｖｏｎ  ｕｎｄ  ｎａｖｉｇｉｅｒｅｎ  ｉｎ  ｕｍｆａｎｇｒｅｉｃｈｅｎ，Ｇｒａｆｉｋｅｌｅｌｍｅｎｔｅ  ｅｎｔｈａｌｔｅｎｄｅｎ  Ｄａｔｅｉｅｎ’は、２次元図形位地図に関する地図データを各セルＣｋに割り当てるデータを細分化する方法を開示している。この細分化方法は、上記に述べられた方法に類似する方法で、細分化されたデータ、即ち２次元地図データの特性に依存するという欠点を有する。さらに、この方法は、上記に述べられたように、同一のセルにグループ化するほうがよい冗長データの場合を処理しない。
【００２４】
同様に、マイクロソフト社の国際特許出願第ＷＯ−００１６３０７‘Ｍｅｔｈｏｄ  ａｎｄ  ａｐｐａｒａｔｕｓ  ｆｏｒ  ｖｉｓｕａｌｉｓｉｎｇ  ａｎｄ  ｅｘｐｌｏｒｉｎｇ  ｌａｒｇｅ  ｈｉｅｒａｒｃｈｉｃａｌ  ｓｔｒｕｃｔｕｒｅｓ’は、細分化を目的として、ナビゲーショングラフをデータに割り当てることができる方法を開示している。しかしながら、このような細分化は、先行する階層が確立されるデータ間のみに適用されることができる。さらに、冗長関数としてデータの細分化を最適化することはできない。
【００２５】
最後の例において、２０００年１月１１日に公開された米国特許６０１４６７１（ＩＢＭ）‘Ｉｎｔｅｒａｃｔｉｖｅ  ｒｅｔｒｉｅｖａｌ  ａｎｄ  ｃａｔｃｈｉｎｇ  ｏｆ  ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ  ｄａｔａ  ｕｓｉｎｇ  ｖｉｅｗ  ｅｌｅｍｅｎｔｓ’は、画像、特に衛星通信から得られる画像を細分化することができ、空間又は時間の基準に従ってナビゲーショングラフを生成することができる方法を開示している。上記に述べられた特許に類似する方法で、この特許は、冗長マルチメディアデータの場合を考慮しない性質のデータに関する細分化方法を述べている。
【００２６】
【発明が解決しようとする課題】
本発明は、これら欠点を改善するもので、ナビゲーショングラフによって機能及び／又は特性とは無関係に、マルチメディアデータ即ち種々の性質の冗長データを細分化可能にする。
【００２７】
【課題を解決するための手段】
より詳細には、本発明は、ナビゲーションノードに関連するマルチメディアデータを細分化する方法であって、ノードは、関連するデータアイテムと少なくとも１つ次のノードとへのアクセスを制御する方法において、
ノードと連続する形態でそれに関連するデータとが、開始ノード及びこのノードに関連するデータを有する一時セルにグループ化され、一時セルにグループ化された各ノードは、一時セルのサイズが閾値に達するまでこの一時セルに既に含まれているノードに追従し、
一対の２つのノードに関連するデータに共通のデータの数に依存したパラメータを最小化するように、一時セルの互いに追従する一対のノードが、識別され、決定セルが、一対の第１のノードに関連するデータより先に一時セルにグループ化されたデータで形成されることを特徴とするマルチメディアデータを細分化する方法に関する。
【００２８】
このような方法によって、マルチメディアデータは、特性及び用途とは無関係に細分化することができ、この細分化はデータに関連するナビゲーションノードの使用に基づく。
【００２９】
さらに、一時セルのサイズを制限する基準の関数として、サイズがデータの多重化送信のような使用に適応するセルを生成するように閾値を決定することができる。
【００３０】
さらに、一対の２つのノードに関連するデータに共通のデータの数に比例した細分化パラメータの使用が、実質的に単独のセル即ち別々に、例えば端末による受信に続いて処理されることができるセルを形成する。
【００３１】
最後に、本発明に従う方法は、冗長データが一般に同一のセルに含まれることとなるので冗長データについて最適化されるセルを生成し、その結果、上記に述べたように処理を容易にする。換言すると、本発明に従う方法によって生成される冗長セルの数は、一般的に、既知の細分化の方法によって生成される冗長セルの数より少ない。
【００３２】
１つの実施形態において、識別された一対の２つのノードに関連するデータに共通のデータの数に比例して、一対のノードによって最小化されるパラメータが、決定される。
【００３３】
１つの実施形態において、一時セルの閾値サイズは、このセルにグループ化されるデータの量の関数として、又は、このセルにグループ化されるノードの数の関数として決定される。
【００３４】
１つの実施形態において、第１の細分化中に行われる操作を繰り返すことによって第２のノードに追従するデータの細分化を行うために、開始ノードとして又は未だグループ化されていない他のノードとして、識別された一対の第２のノードが用いられる。
【００３５】
１つの実施形態において、パラメータが、識別された一対のノードの１つに関連するデータの量に反比例するように決定される。
【００３６】
１つの実施形態において、パラメータが、識別された一対のノードの第１のノードより先に一時セルにグループ化されたノードの数と、一時セル内のノードの数との比に比例して決定される。
【００３７】
１つの実施形態において、マルチメディアデータは、音声文書、映像文書、プログラム、テキスト文書の少なくとも１つに関するデータを有する。
【００３８】
この場合、１つの実施形態によると、映像データは、２又は３次元画像の画像、連続画像、パノラマ、図形データの中の少なくとも１つに対応する。
【００３９】
１つの実施形態によると、場面又は対象物の視点、隣接するノードに関する画像は、これら場面又はこれら対象物に近接した視点に対応する。
【００４０】
本発明はまた、ナビゲーショングラフに関係しないマルチメディアデータを細分化する方法に関する。このような方法は、ナビゲーションノードが、特性及び／又は機能の関数としてこれらデータに関係し、これらデータの圧縮は冗長データを削除することによって実行され、維持されたデータは、削除されたデータに関連するノードに関係し、これらデータは上記に述べられた細分化方法の実施形態のいずれか１つに従う細分化方法によって細分化されることを特徴とする。
【００４１】
１つの実施形態において、データが実画像及び合成画像とに関する映像データを有し、ナビゲーションノードは、実画像に関するデータへのアクセスを課すことによってマルチメディアデータに関係する。
【００４２】
本発明はまた、プログラムがコンピュータ上で実行されるとき、上記で定義された細分化方法の実施形態の１つに従うマルチメディアデータを細分化する方法のステップを実行するためのプログラムコード指令を含むコンピュータプログラムに関する。
【００４３】
本発明はまた、データアイテムに関連するノードを用いてデータアイテムにアクセスする手段と、
前ノードと称される第１のノードから、次ノードと称される第２のノードへのアクセスを決定する手段とを有するナビゲーションノードに関連するマルチメディアデータを細分化する装置において、
予め決められた開始ノードで開始し、一時セル内に、このセルが閾値サイズに達するまで関係したノードが互いに追従するデータをグループ化する手段と、
一対の２つのノードに関連するデータに共通のデータの数に比例したパラメータを最小化する一対の次ノードを識別する手段と、
一対の第１のノードとそのノードより前のノードとに関連するデータを有するセルを形成する手段とを有し、
本発明に従う方法を実現するための装置に関する。
【００４４】
１つの実施形態において、装置は、識別された一対の２つのノードに関連するデータに共通のデータの数に比例してパラメータを決定する手段を有する。
【００４５】
１つの実施形態によると、装置は、一時セルにグループ化されるデータの量の関数として、又は、一時セルにグループ化されるノードの数の関数として、一時セルの閾値サイズを決定する手段を有する。
【００４６】
１つの実施形態によると、装置は、第１の細分化中に行われる操作を繰り返すことによって、第２のノードに追従するデータの細分化を実行するための開始ノードとして、識別された一対の第２のノードを用いる手段を有する。
【００４７】
１つの実施形態において、装置は、識別された一対のノードの１つに関連するデータの量に反比例するようにパラメータを決定する手段を有する。
【００４８】
１つの実施形態によると、装置は、識別された一対のノードの第１のノードより先に一時セルにグループ化されるノードの数と、一時セル内のノードの数との比に比例してパラメータを決定する手段を有する。
【００４９】
１つの実施形態において、装置は、音声文書、映像文書、プログラムの少なくとも１つに関するマルチメディアデータを処理する手段を有する。
【００５０】
この場合、１つの実施形態によると、装置は、２又は３次元画像の画像、連続画像の少なくとも１つに対応する映像データを処理する手段を有する。
【００５１】
１つの実施形態によると、場面又は対象物の視点に関する画像において、装置は、隣接するノードがこれら場面又はこれら対象物に近接した視点に対応するようなノードを処理する手段を有する。
【００５２】
１つの実施形態によると、マルチメディアデータを細分化する装置は、ナビゲーションノードが特性及び／又は機能の関数としてこれらデータに関連する手段と、冗長データを削除することによってこれらデータの圧縮を行い、維持されたデータが、削除されたデータに関連するノードに関係する手段と、上記に述べられた実施形態のいずれか１つに従う細分化方法によってこれらデータを細分化する手段とを有する。
【００５３】
この場合、１つの実施形態によると、データは実画像と合成画像とに関する映像データを有し、装置は、ナビゲーションノードが実画像に関するデータへのアクセスを課すようにマルチメディアデータに関係する手段を有する。
【００５４】
本発明の他の特徴と利点は、添付された図面を参照して、以下に述べられる実施形態の形式を何ら限定しない説明で明らかになる。
【００５５】
【発明の実施の形態】
再度述べると、本発明は、ノードＮ’５，Ｎ’６，Ｎ’７，Ｎ’８，Ｎ’９，Ｎ’１０及びＮ’１１を有するナビゲーショングラフに関連するマルチメディアデータＤ’５，Ｄ’６，Ｄ’７，Ｄ’８，Ｄ’９，Ｄ’１０及びＤ’１１（図２）を細分化し、各ノードＮ’ｉは、上記に述べたように、それに関連するデータＤ’ｉへのアクセスを決定する。
【００５６】
しかしながら、細分化されるマルチメディアデータＤ’ｉは、初めは、ナビゲーショングラフに関係しないことが可能である。この場合、マルチメディアデータを細分化する前にこのグラフを生成することが必要である。
【００５７】
このような生成は、例えば、データＤ’ｉを有する文書の機能として実行することができる。従って、ハイパーテキストリンク及び画像を有するページで構成されるマルチメディア文書を考慮し、ナビゲーショングラフは、セルをこの文書の各ページに割り当てることによって生成することができ、一方、各セルのノードは各ページの種々のデータに対応する。
【００５８】
マルチメディアデータが場面及び対象物の画像に関する場合、ナビゲーショングラフは、表示された同一の場面又は同一の対象物の種々の可能な視点に関係するノードから構成することができる。
【００５９】
この場合、映像ゲームのような多数の用途は、場面を表示するために実画像に関するマルチメディアデータを用いることに留意しなければならない。したがって、処理が合成画像に関するデータの処理より簡単でかつ速いこれら実データへのアクセスを制限するように、ナビゲーショングラフを生成することは効果的であってもよい。
【００６０】
他の例において、データがコンピュータ援用設計ツールに関し、及び、設計に用いられる種々の要素又はアイテムの機能としてデータの階層（ｈｉｅｒａｒｃｈｉｚａｔｉｏｎ）を有する場合、ナビゲーショングラフは、この階層の代表的なノードから構成することができる。
【００６１】
一般的な方法において、データがグリッド又はファイル構造のような既に存在している構造に従って構成される場合、ナビゲーショングラフはこの元の構造から得られることができる。
【００６２】
マルチメディアデータがナビゲーショングラフに関係するとき、これらデータの圧縮は、このナビゲーショングラフによって実行される。これを実行するために、冗長データＤ’ｉ及びＤ’ｎは、データ例えばＤ’ｎを削除し、ノードＮ’ｉ及びＮ’ｎを、以下Ｄ’ｉ／Ｄ’ｎと表される残っているデータＤ’ｉに関係させることによって処理され、識別される。したがって、図２では、ノードＮ’９及びＮ’８はデータＤ’８／Ｄ’９に関係する。同様に、ノードＮ’５及びＮ’６（それぞれノードＮ’６及びＮ’７）はデータＤ’５／Ｄ’６（それぞれＤ’６／Ｄ’７）に関係する。
【００６３】
他の圧縮形式も可能である。従って、ナビゲーショングラフに関連する画像表示に関するデータの場合において、Ｔｈｏｍｓｏｎ  Ｍｕｌｔｉｍｅｄｉａにより１９９９年９月１７日に出願された仏国特許第９９１１６７１の‘Ｐｒｏｃｅｄｅ  ｄｅ  ｃｏｎｓｔｒｕｃｔｉｏｎ  ｄ’ｕｎ  ｍｏｄｅｌｅ  ｄｅ  ｓｃｅｎｅ  ３Ｄ  ｐａｒ  ａｎａｌｙｓｅ  ｄｅ  ｓｅｑｕｅｎｃｅ  ｄ’ｉｍａｇｅｓ’［Ｍｅｔｈｏｄ  ｏｆ  ｃｏｎｓｔｒｕｃｔｉｎｇ  ａ  ３Ｄ  ｓｃｅｎｅ  ｍｏｄｅｌ  ｂｙ  ａｎａｌｙｓｉｎｇ  ｉｍａｇｅ  ｓｅｑｕｅｎｃｅｓ］は、３次元における画像に関し、ナビゲーショングラフに関連するデータの圧縮を実行する手段を開示している。
【００６４】
３次元画像に基づく説明を含み、ナビゲーショングラフが関係する映像データベースのために、既に引用された仏国特許第９９１１６７１は、どの情報が視点の再構築に必要であるか、及び、どの情報がこのノードに関連するのに必要であるかを決定するようにナビゲーションノードの可視性に関する情報を追加する手順を述べている。
【００６５】
この圧縮ステップの後、マルチメディアデータＤ’５，Ｄ’６，Ｄ’７，Ｄ’８，Ｄ’９，Ｄ’１０及びＤ’１１は、種々のデータセルＣ’ｉに細分化される。本発明によると、この細分化は、以下の操作を行うことによって実行される。
【００６６】
第１に、開始ノードＮ’５が決定され、このノードＮ’５から、全組のデータＤ’５，Ｄ’６，Ｄ’７，Ｄ’８，Ｄ’９，Ｄ’１０及びＤ’１１が細分化のためにアクセスされる。この開始ノードを介して、それに続くノードＮ’６，Ｎ’７，Ｎ’８，Ｎ’９，Ｎ’１０及びＮ’１１がアクセスされる。
【００６７】
図２に示されるように、本発明に従う細分化方法は非線形ナビゲーショングラフに関連するデータに適応し、ノードＮ’５は、２つのノードＮ’６とＮ’７に関係することが強調される。
【００６８】
その後、連続して選択されたデータＤ’５，Ｄ’６，Ｄ’７，Ｄ’８，Ｄ’９が、開始ノードＮ’５で開始し、開始ノードＮ’５又は関連するデータが一時セルに既にグループ化されたノードに隣接するノードに関係するデータを考慮することによって一時セルＣｔにグループ化される。例えば、ノードＮ’５に隣接するノードＮ’６に関連するデータＤ’６は、一時セルＣ’ｔにグループ化される。その後、ノードＮ’５に同じく隣接するノードＮ’７に関連するデータＤ’７がグループ化される。
【００６９】
同様に、データＤ’８及びデータＤ’９は、一時セルＣ’ｔに含まれるノードに隣接するためにそれらに関連するノードＮ’８及びＮ’９を考慮することによって、一時セルＣｔに連続してグループ化される。この例において、データに関連するノードもまた、一時セルにグループ化される。
【００７０】
このようなグループ化は、一時セルに含まれるデータＤ’５，Ｄ’６，Ｄ’７，Ｄ’８，Ｄ’９の数が閾値に達するまで行われる。変形において、一時セルの限界サイズは、この一時セルに含まれるノードの数の関数として決定される。
【００７１】
一時セルが閾値サイズに達したとき、識別された一対の２つのノード（Ｎ’７，Ｎ’８）に関連するデータ（Ｄ’７，Ｄ’８）に共通のデータＤ’ｃの数に比例したパラメータＴｉを最小化する一対の連続ノード（Ｎ’７，Ｎ’８）、即ち第１のノードＮ’７が、次ノードである第２のノードＮ’８に先行する一対の連続ノードが、識別される。この例において、このパラメータＴｉは、
Ｔｉ＝（（Ｔ−（ｉ−５））／Ｔ）＊ｒｉ
である。
【００７２】
ここで、Ｔは一時セルＣ’ｔに含まれる全ノードの数であり、ｉ−５は一対のノードに関係する第１のノードＮ’７より先に一時セルにグループ化されたノードの数であり、ｒｉはＤ’７とＤ’８に共通のデータの数Ｄ’ｃと、一対のノードＮ’７及びＮ’８の１つに関連するデータの数Ｄ’ｍａｘとの比に等しい。
【００７３】
最後に、一対の第１のノードＮ’７に関連するデータまで、連続して一時セルにグループ化されるデータ（Ｄ’５，Ｄ’６，Ｄ’７）を有する決定セルＣ’５／６／７が、形成される。
【００７４】
その後、上記に述べられた操作を繰り返すことによって新しい決定セルが形成され、識別された一対の第２ノード（Ｎ’８）が開始ノードとして用いられる。
【００７５】
本発明の変形において、識別された一対のこのノード（Ｎ’８）以外のノードが、開始ノードとして用いられる。
【００７６】
本発明に従う方法は、決定セルの限界が、２つの隣接するノードに共通のデータの数に比例したパラメータＴｉを最小化する一対のノード（Ｎ’７，Ｎ’８）即ちセルの間にはどの冗長データもない又はほとんどない一対のノードを利用して得られるので、冗長セルの形成を制限する傾向にあることは明らかである。
【００７７】
換言すると、本発明に従う方法は、冗長データを決定セルＣ’５／６／７にグループ化する傾向にあり、それによって、上記に述べたように、処理を容易にする。
【００７８】
その後、識別された一対（Ｎ’７，Ｎ’８）の第２のノードＮ’８とそのノードに追従するノード（Ｎ’９，Ｎ’１０，…Ｎ’ｚ）とに関連するデータの細分化は、新しい一時セルを形成するために開始ノードとして識別された一対の第２のノード（Ｎ’８）を用いる間、上記に述べられた操作を繰り返すことによって実行される。
【００７９】
上記に述べられたように、本発明の変形において、識別された一対の第２のノード以外のノードは、新しい細分化のための開始ノードとして用いられる。
【図面の簡単な説明】
【図１】既知の方法におけるマルチメディアデータに関連するノードを有するセルを表している。
【図２】本発明に従って細分化されたマルチメディアデータに関連するノードを有するセルを表している。
【符号の説明】
Ｎ０、Ｎ１、Ｎ２、Ｎ３、Ｎ４、Ｎ’５、Ｎ’６、Ｎ’７、Ｎ’８、Ｎ’９、Ｎ’１０、Ｎ’１１  ノード
Ｄ０、Ｄ１、Ｄ２、Ｄ３、Ｄ４、Ｄ１０、Ｄ１１  データ
Ｄ’５／Ｄ’６、Ｄ’５／Ｄ’７、Ｄ’８／Ｄ’９  データ
Ｃ０、Ｃ１、Ｃ２、Ｃ３、Ｃ４  セル
Ｃ’５／６／７  決定セル
Ｃｔ  一時セル
【図１】
2004254272.tif 000003
【図２】
2004254272.tif 000004
【外国語明細書】
2004254272.tif 000005
2004254272.tif 000006
2004254272.tif 000007
2004254272.tif 000008
2004254272.tif 000009
2004254272.tif 000010
2004254272.tif 000011
2004254272.tif 000012
2004254272.tif 000013
2004254272.tif 000014
2004254272.tif 000015
2004254272.tif 000016
2004254272.tif 000017
2004254272.tif 000018
2004254272.tif 000019
2004254272.tif 000020
2004254272.tif 000021
2004254272.tif 000022
2004254272.tif 000023
2004254272.tif 000024
2004254272.tif 000025
2004254272.tif 000026
2004254272.tif 000027
2004254272.tif 000028
2004254272.tif 000029
2004254272.tif 000030
2004254272.tif 000031