(57)【特許請求の範囲】
【請求項１】
画像処理装置（クライアント）の階層符号データの部分符号データの転送要求に基づいて、画像処理装置（サーバ）の記憶装置に保存された階層符号データの部分符号データを受信する機能を有する画像処理装置（クライアント）であって、受信した前記符号データの一部または全部を記憶装置乃至記憶装置（キャッシュメモリ）に保存し再利用する機能を有し、前記記憶装置（キャッシュメモリ）に保存された符号データの保存容量がオーバーフローを起こした場合において、構造化要素単位で前記記憶装置乃至記憶装置（キャッシュメモリ）に保存される符号データの一部または全部を入れ替える場合にあって、入れ替え単位が階層符号データの指定した階層の指定したレベルに含まれる符号列（パケット）単位であり、
前記入れ替え単位が、階層符号データが使用される場合の符号データの階層毎の使用頻度に基づいて指定され、
前記符号データの階層毎の使用頻度が、該階層符号データが使用される場合の符号データのプログレッション順の使用頻度に基づいて推定されることを特徴とする画像処理システム。
【請求項２】
請求項１に記載の画像処理システムにおいて、前記入れ替えにおいて、保存されていない符号列を含む階層レベルの符号列を優先して入れ替えることを特徴とする画像処理システム。
【請求項３】
請求項１又は２に記載の画像処理システムにおいて、データ符号量を階層レベル毎に算出するデータ符号量算出手段を有し、前記算出されたデータ符号量に基づいて、前記階層符号データの階層レベル単位で符号データを入れ替える手段を有することを特徴とする画像処理システム。
【請求項４】
請求項１乃至３のいずれかに記載の画像処理システムにおいて、前記階層符号データがＪＰＥＧ２０００（ＩＳＯ／ＩＥＣ  １５４４４−１）規格に基づき符号化されたデータであることを特徴とする画像処理システム。
【請求項５】
請求項１乃至４のいずれかに記載の画像処理システムにおいて、前記階層符号データがＪＰＩＰ（ＪＰＥＧ２０００  ｉｍａｇｅ  ｃｏｄｉｎｇ  ｓｙｓｔｅｍ−Ｐａｒｔ９：Ｉｎｔｅｒａｃｔｉｖｉｔｙ  ｔｏｏｌｓ，  ＡＰＩｓ  ａｎｄ  ｐｒｏｔｏｃｏｌｓ）規格に基づき、サーバの記憶装置に保存された符号化画像データの一部である部分符号データをクライアントが受信する部分符号データアクセス機能を有することを特徴とする画像処理システム。
【請求項６】
画像処理装置（クライアント）の階層符号データの部分符号データの転送要求に基づいて、画像処理装置（サーバ）の記憶装置に保存された階層符号データの部分符号データを受信する画像処理装置（クライアント）の画像処理方法であって、受信した前記符号データの一部または全部を記憶装置乃至記憶装置（キャッシュメモリ）に保存し再利用するときに、前記記憶装置（キャッシュメモリ）に保存された符号データの保存容量がオーバーフローを起こした際に、構造化要素単位で前記記憶装置乃至記憶装置（キャッシュメモリ）に保存される符号データの一部または全部を入れ替える場合にあって、入れ替え単位が階層符号データの指定した階層の指定したレベルに含まれる符号列（パケット）単位であり、
前記入れ替え単位が、階層符号データが使用される場合の符号データの階層毎の使用頻度に基づいて指定され、
前記符号データの階層毎の使用頻度が、該階層符号データが使用される場合の符号データのプログレッション順の使用頻度に基づいて推定されることを特徴とする画像処理方法。
【請求項７】
コンピュータに、請求項１乃至５のいずれかに記載の画像処理システムの機能を実現させるためのプログラム。
【請求項８】
コンピュータが読み取り可能な記録媒体であって、請求項７に記載のプログラムを記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理システム、画像処理方法、プログラムおよび記録媒体に関し、特に、キャッシュモデルを用いて部分画像符号化データをアクセス機能を具備する符号化処理装置に関し、ＪＰＩＰ（ＪＰＥＧ２０００  ｉｍａｇｅ  ｃｏｄｉｎｇ  ｓｙｓｔｅｍ−Ｐａｒｔ９：Ｉｎｔｅｒａｃｔｉｖｉｔｙ  ｔｏｏｌｓ，  ＡＰＩｓ  ａｎｄ  ｐｒｏｔｏｃｏｌｓ）実装技術に係る。
【背景技術】
【０００２】
サーバにあるＪＰＥＧ２０００仕様に基づいて符号化された符号データをアクセスする方式として、ＪＰＩＰ（ＪＰＥＧ２０００  ｉｍａｇｅ  ｃｏｄｉｎｇ  ｓｙｓｔｅｍ−Ｐａｒｔ９：Ｉｎｔｅｒａｃｔｉｖｉｔｙ  ｔｏｏｌｓ，  ＡＰＩｓ  ａｎｄ  ｐｒｏｔｏｃｏｌｓ）がある。その仕様には、既にクライアント側に受信された符号データは新たに転送することなく使用することで高速にアクセスできるような仕組みとして、クライアント上に符号データの一部を保存するキャッシュの機能を備えている。
【０００３】
ところで、クライアント側のキャッシュとして記憶可能な記憶容量は制限があるので、記憶しきれない場合は一部削除して新しい優先順位の高いデータを保存する。
ＪＰＩＰ仕様に見られるような、キャッシュなど記憶装置に保存された階層符号データの部分符号データを切り出して参照する機能を有する符号処理システムにおいては、プログレッション順Ａで階層符号データが構成されている場合には、プログレッション順Ａの最上位階層レベルで符号データを切り出して使いわける場合が多い。最上位階層レベル以下の階層の符号列をまとめて削除することが容易に実現できるからである。
【０００４】
例えば、部分領域に対応する画像データに対応する部分符号データ単位でアクセス（参照）する場合は、対応する階層符号データのプログレッション順の最上位階層レベルは領域レベルになっていると、簡単に特定の部分領域の部分符号データを参照または抽出することができるのである。
【０００５】
（１）キャッシュデータの入れ替え戦略に係る先願：
キャッシュのオーバーフロー時のキャッシュデータの削除の最適化に関しては以下の先願がある。
特許文献１は、画像の再生表示はキャッシュデータに基づいて行い再生表示を高速化する。
また、特許文献２は、注目領域から削除する単位領域までの距離に基づいて削除する。
また、特許文献３は、注目領域と移動方向に基づいて削除する。
また、特許文献４は、注目領域とメタデータが付与されている画像領域とに基づいて削除する。
また、特許文献５は、画像データにおける削除対象領域の決定に基づいて削除する。
また、特許文献６は、低解像度データは消去しない。
【０００６】
（２）ＪＰＩＰに係る先願：
特許文献７は、キャッシュがタイル単位に符号データを管理する。共通の（定型）フォーマットを持つ画像データなど構造化文書画像データの場合では、タイル単位ではなく構造単位で画像データを参照することが多い。
また、特許文献８は、ＪＰＰ−ストリームからＪＰＥＧ２０００符号ストリームへ変換する。
【特許文献１】特開２００４−１５２１７２号公報
【特許文献２】特開２００４−１５３５６２号公報
【特許文献３】特開２００４−１４５７６０号公報
【特許文献４】特開２００４−１４５７５９号公報
【特許文献５】特開２００３−２９８８４７号公報
【特許文献６】特開２００３−２２４７０４号公報
【特許文献７】特開２００５−１２６８６号公報
【特許文献８】特開２００４−２７４７５８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明では、係る傾向に基づいて、階層符号データのプログレッション順の使用傾向に基づいて部分符号データがアクセスされるものとして制御し、キャッシュなど高速メモリ上に一時的に保存された符号データを再利用する場合において、キャッシュがオーバーフローを起こしたような場合におけるキャッシュ上に保存する符号データの入れ替え処理に係り、符号データのアクセスにおけるキャッシュデータの符号データのヒット率を高くすることを課題としている。
【０００８】
従来、注目領域あるいはその周辺領域の画像符号データをキャッシュ上に残し、それ以外を入れ替えるという方式が提案されている（特許文献２、３など）。典型的には、矩形領域（ブロック）単位の符号データで判断することが考えられるが、使用の方法によっては、データの入れ替え単位としては、予め固定された矩形領域（ブロック）単位としている。
【０００９】
しかしながら、削減される符号データを考えたとき、使用する符号データの構成は常に固定ではなく、たとえば、特定の周波数成分の符号データのみ重要でないので除去するような場合も考えられ、入れ替え対象とする注目領域に対応する符号データの単位（範囲）を使用状況に適応して柔軟に変更することが問題となる。特に、符号データが階層構造を持ち一部削除することが可能であるＪＰＥＧ２０００規格の符号のような場合には、入れ替えする部分符号データの範囲の決め方が問題となる。
【００１０】
また、殊にキャッシュ上に保存された符号データを入れ替える場合の、適切な入れ替え単位（範囲）の決め方、及びその効率的な処理が課題である。
即ち、アクセスする部分符号データは、符号データの階層構造を生かして、領域単位でアクセスされたり、解像度を上げるためにアクセスしたり複数の目的でアクセスする場合がある。このように符号データが階層構造をもつ場合には、アクセス単位も符号データの階層構造に依存するので、符号データの階層構造を考慮したキャッシュデータの入れ替え処理が必要となる。
【００１１】
また、一般的に、画像データの部分符号データのアクセス単位（範囲）は、符号データの最小符号列（パケット）の集合により構成される。そのため、部分符号データのアクセスにおけるキャッシュデータとして必要とするパケットが全て揃っていないとアップロードしなければならない（ヒットできない）。
したがって、使用する単位の全てのパケットが揃っていないものは、優先的に入れ替え対象とするような考慮も必要である。
【００１２】
本発明では、部分符号データアクセスにおけるキャッシュデータの符号データのヒット率を高くすることを主要目的とし、このような目的を達成すべく、オーバーフロー時のデータ入れ替えの管理を、符号データの使用状況（使用傾向の推定）に基づいて入れ替え単位を適応的に設定することを課題とした。
【課題を解決するための手段】
【００１３】
上述の課題を解決するために、請求項１に記載の画像処理システムの発明は、画像処理装置（クライアント）の階層符号データの部分符号データの転送要求に基づいて、画像処理装置（サーバ）の記憶装置に保存された階層符号データの部分符号データを受信する機能を有する画像処理装置（クライアント）であって、受信した前記符号データの一部または全部を記憶装置乃至記憶装置（キャッシュメモリ）に保存し再利用する機能を有し、前記記憶装置（キャッシュメモリ）に保存された符号データの保存容量がオーバーフローを起こした場合において、構造化要素単位で前記記憶装置乃至記憶装置（キャッシュメモリ）に保存される符号データの一部または全部を入れ替える場合にあって、入れ替え単位が階層符号データの指定した階層の指定したレベルに含まれる符号列（パケット）単位であり、前記入れ替え単位が、階層符号データが使用される場合の符号データの階層毎の使用頻度に基づいて指定され、前記符号データの階層毎の使用頻度が、該階層符号データが使用される場合の符号データのプログレッション順の使用頻度に基づいて推定されることを特徴とする。
【００１５】
請求項２に記載の発明は、請求項１に記載の画像処理システムにおいて、前記入れ替えにおいて、保存されていない符号列を含む階層レベルの符号列を優先して入れ替えることを特徴とする
【００１６】
請求項３に記載の発明は、請求項１又は２に記載の画像処理システムにおいて、データ符号量を階層レベル毎に算出するデータ符号量算出手段を有し、前記算出されたデータ符号量に基づいて、前記階層符号データの階層レベル単位で符号データを入れ替える手段を有することを特徴とする。
請求項４に記載の発明は、請求項１乃至３のいずれかに記載の画像処理システムにおいて、前記階層符号データがＪＰＥＧ２０００（ＩＳＯ／ＩＥＣ  １５４４４−１）規格に基づき符号化されたデータであることを特徴とする。
【００１７】
請求項５に記載の発明は、請求項１乃至４のいずれかに記載の画像処理システムにおいて、前記階層符号データがＪＰＩＰ（ＪＰＥＧ２０００  ｉｍａｇｅ  ｃｏｄｉｎｇ  ｓｙｓｔｅｍ−Ｐａｒｔ９：Ｉｎｔｅｒａｃｔｉｖｉｔｙ  ｔｏｏｌｓ，  ＡＰＩｓ  ａｎｄ  ｐｒｏｔｏｃｏｌｓ）規格に基づき、サーバの記憶装置に保存された符号化画像データの一部である部分符号データをクライアントが受信する部分符号データアクセス機能を有することを特徴とする。
【００１８】
請求項６に記載の画像処理方法の発明は、画像処理装置（クライアント）の階層符号データの部分符号データの転送要求に基づいて、画像処理装置（サーバ）の記憶装置に保存された階層符号データの部分符号データを受信する画像処理装置（クライアント）の画像処理方法であって、受信した前記符号データの一部または全部を記憶装置乃至記憶装置（キャッシュメモリ）に保存し再利用するときに、前記記憶装置（キャッシュメモリ）に保存された符号データの保存容量がオーバーフローを起こした際に、構造化要素単位で前記記憶装置乃至記憶装置（キャッシュメモリ）に保存される符号データの一部または全部を入れ替える場合にあって、入れ替え単位が階層符号データの指定した階層の指定したレベルに含まれる符号列（パケット）単位であり、前記入れ替え単位が、階層符号データが使用される場合の符号データの階層毎の使用頻度に基づいて指定され、前記符号データの階層毎の使用頻度が、該階層符号データが使用される場合の符号データのプログレッション順の使用頻度に基づいて推定されることを特徴とする。
【００１９】
請求項７に記載の画像処理方法の発明は、コンピュータに、請求項１乃至５のいずれかに記載の画像処理システムの機能を実現させるためのプログラムである。
請求項８に記載の画像処理方法の発明は、コンピュータが読み取り可能な記録媒体であって、請求項７に記載のプログラムを記録したことを特徴とする記録媒体である。
【発明の効果】
【００２０】
本発明によれば、クライアント側のキャッシュ上の符号データ（符号列）とサーバ側の元符号データとの間の照合を効率的に施すことができ、部分符号データであっても階層構造を踏まえて容易に照合することができる。
また、キャッシュ上の非連続的に保存された断片的な符号列であっても、符号データとの間で効率的かつ確実に照合することができ、判定するデータ（符号列）の範囲を限定し効率的に照合することができる。
【発明を実施するための最良の形態】
【００２１】
以下、図面を参照して本発明に係る好適な実施形態について詳細に説明する。
まず、ＪＰＥＧ２０００およびＪＰＩＰについて説明する。
【００２２】
（１）ＪＰＥＧ２０００による符号化：
ＪＰＥＧ２０００（ＩＳＯ／ＩＥＣ  １５４４４−１）規格の符号化は、おおよそ以下の手順でなされる。
インターレース画像のフレームデータを、Ｙ，Ｃｒ，Ｃｂの色成分毎のデータに変換し、各色成分の色データに対して、２次元離散ウェーブレット変換を施し、得られるウェーブレット係数に、ＪＰＥＧ２０００に規定のスカラ量子化処理を施し、スカラ量子化されたデータに対しＪＰＥＧ２０００に規定のエントロピー符号化処理（いわゆる係数モデリングによる算術符号化処理）を施した後、ＪＰＥＧ２０００で規定する符号列を生成する。
復号化処理はこの逆の手順である。
【００２３】
勿論、これらの処理は、ハードウェア回路により実現しても良い。処理の高速化が図られる。なお、ＪＰＥＧ２０００に準拠する符号化処理を全てハードウェア回路で実現する画像処理装置は、既に存在する。
【００２４】
図１は、ＪＰＥＧ２０００の基本となる階層符号化アルゴリズムを説明するための図である。色空間変換・逆変換部、２次元ウェーブレット変換・逆変換部、量子化・逆量子化部、エントロピー符号化・復号化部、タグ処理部で構成されている。
ＪＰＥＧアルゴリズムと比較して、最も大きく異なる点の一つは変換方法である。ＪＰＥＧでは離散コサイン変換（ＤＣＴ：Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）を、階層符号化圧縮伸長アルゴリズムでは離散ウェーブレット変換（ＤＷＴ：Ｄｉｓｃｒｅｔｅ  Ｗａｖｅｌｅｔ  Ｔｒａｎｓｆｏｒｍ）を、各々用いている。
ＤＷＴは、ＤＣＴに比べて、高圧縮領域における画質が良いという長所が、ＪＰＥＧの後継アルゴリズムであるＪＰＥＧ２０００で採用された大きな理由の一つとなっている。
【００２５】
また、他の大きな相違点は、後者では、最終段に符号形成を行うために、タグ処理部と呼ばれる機能ブロックが追加されていることである。この部分で、圧縮動作時には圧縮データがコードストリームとして生成され、伸長動作時には伸長に必要なコードストリームの解釈が行われる。そして、コードストリームによって、ＪＰＥＧ２０００は様々な便利な機能を実現できるようになった。
例えば、図２に示した様に、ブロック・ベースでのＤＷＴにおけるオクターブ分割に対応した任意の階層（デコンポジション・レベル）で、静止画像の圧縮伸長動作を自由に停止させることができるようになる。
【００２６】
なお、原画像の入出力部分には、色空間変換部が接続されることが多い。例えば、原色系のＲ（赤）／Ｇ（緑）／Ｂ（青）の各コンポーネントからなるＲＧＢ表色系や、補色系のＹ（黄）／Ｍ（マゼンタ）／Ｃ（シアン）の各コンポーネントからなるＹＭＣ表色系から、ＹＵＶあるいはＹＣｂＣｒ表色系への変換又は逆の変換を行う部分がこれに相当する。
【００２７】
以下、ＪＰＥＧ２０００アルゴリズムについて、少し詳しく説明する。
カラー画像は、一般に、図３に示すように、原画像の各コンポーネント（ここではＲＧＢ原色系）が、矩形をした領域（タイル）によって分割される。そして、個々のタイル、例えば、Ｒ００，Ｒ０１，…，Ｒ１５／Ｇ００，Ｇ０１，…，Ｇ１５／Ｂ００，Ｂ０１，…，Ｂ１５が、圧縮伸長プロセスを実行する際の基本単位となる。従って、圧縮伸長動作は、コンポーネント毎、そしてタイル毎に、独立に行われる。
【００２８】
符号化時には、各コンポーネントの各タイルのデータが、図１の色空間変換部に入力され、色空間変換を施されたのち、２次元ウェーブレット変換部で２次元ウェーブレット変換（順変換）が適用されて周波数帯に空間分割される。
【００２９】
図２には、デコンポジション・レベル数が３の場合の、各デコンポジション・レベルにおけるサブバンドを示している。即ち、原画像のタイル分割によって得られたタイル原画像（０ＬＬ）（デコンポジション・レベル０）に対して、２次元ウェーブレット変換を施し、デコンポジション・レベル１に示すサブバンド（１ＬＬ，１ＨＬ，１ＬＨ，１ＨＨ）を分離する。そして引き続き、この階層における低周波成分１ＬＬに対して、２次元ウェーブレット変換を施し、デコンポジション・レベル２に示すサブバンド（２ＬＬ，２ＨＬ，２ＬＨ，２ＨＨ）を分離する。
【００３０】
順次同様に、低周波成分２ＬＬに対しても、２次元ウェーブレット変換を施し、デコンポジション・レベル３に示すサブバンド（３ＬＬ，３ＨＬ，３ＬＨ，３ＨＨ）を分離する。更に図２では、各デコンポジション・レベルにおいて符号化の対象となるサブバンドを、グレーで表してある。例えば、デコンポジション・レベル数を３とした時、グレーで示したサブバンド（３ＨＬ，３ＬＨ，３ＨＨ，２ＨＬ，２ＬＨ，２ＨＨ，１ＨＬ，１ＬＨ，１ＨＨ）が符号化対象となり、３ＬＬサブバンドは符号化されない。
【００３１】
次いで、指定した符号化の順番で符号化の対象となるビットが定められ、図１の量子化部で対象ビット周辺のビットからコンテキストが生成される。
量子化の処理が終わったウェーブレット係数は、個々のサブバンド毎に、「プレシンクト」と呼ばれる重複しない矩形に分割される。これは、インプリメンテーションでメモリを効率的に使うために導入されたものである。図４に示した様に、一つのプレシンクトは、空間的に一致した３つの矩形領域からなっている。更に、個々のプレシンクトは、重複しない矩形の「コードブロック」に分けられる。これは、エントロピー・コーディングを行う際の基本単位となる。
【００３２】
エントロピー符号化部（図１参照）では、コンテキストと対象ビットから確率推定によって、各コンポーネントのタイルに対する符号化を行う。こうして、原画像の全てのコンポーネントについて、タイル単位で符号化処理が行われる。
【００３３】
エントロピー符号化部で形成される符号データの最小単位は、パケットと呼ばれる。パケットは、プログレッシブ順にシーケンス化され、これが画像ヘッダセグメントのなかの１つで示される。パケットは、あるプログレッシブ順データで、それぞれ、領域、解像度、レイヤ、および色成分によって配列される。即ち、ＪＰＥＧ２０００規格では、画質（レイヤ（Ｌ））、解像度（Ｒ）、コンポーネント（Ｃ）、位置（プレシンクト（Ｐ））という４つの画像の要素の優先順位を変更することによって、以下に示す５通りのプログレッションが定義されている。
【００３４】
・ＬＲＣＰプログレッション：プレシンクト、コンポーネント、解像度レベル、レイヤの順序に復号されるため、レイヤのインデックスが進む毎に画像全面の画質が改善されることになり、画質のプログレッションが実現できる。レイヤプログレッションとも呼ばれる。
【００３５】
・ＲＬＣＰプログレッション：プレシンクト、コンポーネント、レイヤ、解像度レベルの順序に復号されるため、解像度のプログレッションが実現できる。
【００３６】
・ＲＰＣＬプログレッション：レイヤ、コンポーネント、プレシンクト、解像度レベルの順序に復号されるため、ＲＬＣＰ同様、解像度のプログレッションであるが、特定位置の優先度を高くすることができる。
【００３７】
・ＰＣＲＬプログレッション：レイヤ、解像度レベル、コンポーネント、プレシンクトの順序に復号されるため、特定部分の復号が優先されるようになり空間位置のプログレッションが実現できる。
【００３８】
・ＣＰＲＬプログレッション：レイヤ、解像度レベル、プレシンクト、コンポーネントの順序に復号されるため、例えばカラー画像のプログレッシブ復号の際に最初にグレーの画像を再現するようなコンポーネントのプログレッションが実現できる。
【００３９】
このようにＪＰＥＧ２０００規格では、画像は領域（タイルまたはプレシンクトといった画像構成要素）、解像度、階層（レイヤ）、色成分に分割され、それぞれが独立してパケットとして符号化される。これらのパケットはデコードすることなしに、コードストリームから識別され抽出され得るところに特徴がある。
【００４０】
最後に、タグ処理部（符号列形成部）は、エントロピー符号化部からの全符号化データを１本のコードストリームに結合するとともに、それにタグを付加する処理を行う。図５には、コードストリームの構造を簡単に示した。コードストリームの先頭と各タイルを構成する部分タイルの先頭にはヘッダと呼ばれるタグ情報が付加され、その後に、各タイルの符号化データが続く。そして、コードストリームの終端には、再びタグが置かれる。
【００４１】
一方、復号化時には、符号化時とは逆に、各コンポーネントの各タイルのコードストリームから画像データを生成する。図１を用いて簡単に説明する。この場合、タグ処理部は、外部より入力したコードストリームに付加されたタグ情報を解釈し、コードストリームを各コンポーネントの各タイルのコードストリームに分解し、その各コンポーネントの各タイルのコードストリーム毎に復号化処理が行われる。コードストリーム内のタグ情報に基づく順番で復号化の対象となるビットの位置が定められるとともに、逆量子化部で、その対象ビット位置の周辺ビット（既に復号化を終えている）の並びからコンテキストが生成される。
【００４２】
エントロピー復号化部で、このコンテキストとコードストリームから確率推定によって復号化を行い、対象ビットを生成し、それを対象ビットの位置に書き込む。このようにして復号化されたデータは各周波数帯域毎に空間分割されているため、これを２次元ウェーブレット逆変換部で２次元ウェーブレット逆変換を行うことにより、画像データの各コンポーネントの各タイルが復元される。復元されたデータは色空間逆変換部によって元の表色系のデータに変換される。
【００４３】
（２）ＪＰＩＰにおける符号データのやり取り：
サーバにあるＪＰＥＧ２０００符号から、必要な符号だけを受信するためのプロトコルとして国際規格ＪＰＩＰ（ＪＰＥＧ２０００  ｉｍａｇｅ  ｃｏｄｉｎｇ  ｓｙｓｔｅｍ  −  Ｐａｒｔ  ９：Ｉｎｔｅｒａｃｔｉｖｉｔｙ  ｔｏｏｌｓ，ＡＰＩｓ  ａｎｄ  ｐｒｏｔｏｃｏｌｓ）（［“Ｉｎｆｏｒｎａｔｉｏｎ  ｔｅｃｈｎｏｌｏｇｙ−ＪＰＥＧ２０００  ｉｍａｇｅ  ｃｏｄｉｎｇ  ｓｙｓｔｅｍ−Ｐａｒｔ９：Ｉｎｔｅｒａｃｔｉｖｉｔｙ  ｔｏｏｌｓ，ＡＰＩｓ  ａｎｄ  ｐｒｏｔｏｃｏｌｓ”ＩＳＯ／ＩＥＣ  ＦＤＩＳ  １５４４４−９：２００４”］）がある。
【００４４】
このような、階層的な画像を部分的にアクセスするためのプロトコルは、古くは、画像の多重解像度表現であるＦｌａｓｈＰｉｘと、それにアクセスするためのプロトコルであるＩＩＰ（Ｉｎｔｅｒｎｅｔ  Ｉｍａｇｉｎｇ  Ｐｒｏｔｏｃｏｌ）に見ることができる。ＪＰＩＰに係る特許文献としては特許文献１がある。
【００４５】
ＪＰＩＰにおいては、クライアントからの要求（リクエスト）に応じて、サーバは完全な画像ファイル、タイルパートストリーム（ＪＰＴ−ストリーム）またはプレシンクトストリーム（ＪＰＰ−ストリーム）の形式をもつ符号データを戻す（応答する）。
ＪＰＴ−ストリームは、ＪＰＥＧ２０００パート１規格で規定されるタイルパートの組としてサブ画像の符号データを戻す方法である。
一方、ＪＰＰ−ストリームは、ＪＰＥＧ２０００パート１規格で規定されるプレシンクトの組としてサブ画像の符号データを戻す方法である。
【００４６】
ＪＰＴ−ストリームにより順次アクセスした符号データを再生する場合は、タイル分割されたタイル領域毎に順次完全に再生するのに対して、ＪＰＰ−ストリームにより順次アクセスした符号データを再生する場合は、タイル領域に跨った広い領域で、小さい領域（プレシンクト）単位に徐々に再生することができる。すなわち、ＪＰＴ−ストリームのアクセスによる再生では、一時に再生する範囲が画像全体の中であるタイル領域に限定されているのに対し、ＪＰＰ−ストリームのアクセスによる再生では、一時に再生する範囲はタイル領域に限定されず画像全体での再生が可能なのである。
【００４７】
このように、ＪＰＩＰのクライアントは、受信された符号データの部分を識別でき、それらの部分を復号し且つ画像を生成することができるように、タイルパートストリーム又は、プレシンクトストリームの形式で、ＪＰＥＧ２０００コードストリームのサブセットを戻す機能を提供する。
【００４８】
即ち、ＪＰＰ−ストリームは、ＪＰＥＧ２０００コードストリームへ変換され、ＪＰＥＧ２０００デコーダで復号することができる。この変換は、復号されるデータと共に、メインヘッダの全てとタイルヘッダの全てを受信すれば十分である。
【００４９】
ＪＰＰ−ストリームは、メッセージのシーケンスより構成される（図６参照）。各メッセージは、含まれるデータ−ビン情報の形式を示す（メインヘッダ、メタデータ、プレシンクト、又は、タイルヘッダ）。各メッセージは、データ−ビン内の開始位置とメッセージの長さも示す。各メッセージは、その形式、その形式内のインデックス、その形式とインデックスを有する「データ−ビン」へのメッセージのオフセット、及び、メッセージ長を識別するヘッダを有する。
【００５０】
メッセージは、典型的には、データ−ビン全てを含まず、データ−ビンの一部を含む。メッセージには、データ−ビンがどのタイル、コンポーネント、位置及び、解像度データビンに対してであるかを示す識別子を含む。本発明では、タイル、コンポーネント、位置及び、解像度を階層としており、データ−ビンに含まれる符号列（パケット）は、各階層のどのレベル（階層レベル）のデータであるかという情報が対応している。例えば、データ−ビンに含まれるある符号列がタイルＡでコンポーネントがＣｂで位置４で解像度１レベルであることが示されている。
【００５１】
プレシンクトデータ−ビンは、一連のパケットヘッダ（ＰＨ）とパケットデータ（ＰＤ）より構成される（図７参照）。パケットヘッダは、どのコードブロックがパケットのパケットデータ部分内のデータを有するかに関する情報、各符号ブロックに格納されたバイト数に関する情報、及び、各符号ブロックについての符号化パスの数を含む。ＪＰＩＰの標準仕様では、パケットヘッダには、どのコンポーネント、位置、解像度、タイル、あるいは、それが属するレイヤを識別する情報（階層レベル情報）は持っていない。
【００５２】
本発明の一実施例として、先に示したメッセージデータを解析して、パケット単位の階層レベル情報をパケットヘッダに記録してもかまわない。クライアント側でＪＰＰ−ストリーム受信後、これらの情報を記録することもできる。
【００５３】
同様に、ＪＰＩＰの標準仕様では、パケットヘッダの長さに関する明確な情報は持たない。パケットデータの長さは、パケット内の全てのコードブロックにデータの長さを加算することにより決定できる。
本発明の一実施例として、パケットヘッダにこれらのデータ長を計算した結果を保存する構成にすることができる。ＪＰＰ−ストリームに規定された構成によりパケットを抽出することができる。
【００５４】
ＪＰＩＰのプロトコルは、二つの異なるタイプの要求をもっている。サーバがキャッシュモデルを維持する必要がないという意味におけるステートレスリクエストとそれ以外のリクエストがある。
サーバのキャッシュモデルには、それまでにサーバに送信したことについての情報の記録がなされている。
また、クライアントのキャッシュには、サーバから受信した符号データが保存され、サーバは、キャッシュモデルを用いることによって、既に転送した符号データをクライアントに転送することなく、再利用できる。典型的には、クライアントは、断片的に受信したＪＰＥＧ２０００の符号データを、受信した順番にデータをアペンドしキャッシュに保存する。続いて、前述したようにキャッシュしたデータからＪＰＥＧ２０００のシンタックスに準拠したビットストリームを作成し、そのビットストリームをデコードする。
【００５５】
（３）ＪＰＩＰにおけるクライアント、サーバ、及びネットワーク：
図８は、ＪＰＩＰにおけるキャッシュを持ったクライアントサーバモデル構成例であり、図９は、ＪＰＩＰにおけるクライアントサーバネットワークモデル構成例である。
【００５６】
図８は、クライアント及びサーバ間で符号データを通信するネットワーク環境の一実施例を示す。図８に示すように、サーバ１０２は、ある種のネットワークを介してクライアント１０１のような少なくとも１つのクライアントに接続されている。クライアント１０１は、しばしば、人間のユーザにより制御される「プログラム」であるが、しかし、完全に自動化されたシステムでも良い。クライアント１０１は、ある画像のサブセットに対する要求（リクエスト）１１０を発行し、要求１１０に示された方法で対応する符号データを含む応答１１３を受信する。ネットワークの帯域幅又はサーバ１０２の資源又は、ファイル要求の構造のために、クライアント１０１は要求された画像の部分符号データ以外のおおよその符号データを受信し得る。クライアント１０１は、典型的には、キャッシュを用いて、画像の異なる部分の出力に対する要求を発行し、前に受信された符号データに対する追加分の符号データを受信する。
【００５７】
ＪＰＩＰの基本的特徴の一つは、クライアントが既に受信した符号データを繰返すことを避ける能力である。この符号データの再送信を避ける２つの方法がある。
一つ目の方法（図９）としては、クライアント２１１が、サーバ２０３へ送信されクライアントで既に受信された符号データについての情報をもつことで、クライアント２１１は冗長なデータの配信をサーバ２０３に要求しないで済ませ、それにより、サーバ２０３は冗長な符号データを送信しないで済ます方法である。サーバ２０３が、「ステートレス」で動作する場合にあっては、それまでの相互動作を記憶することなく動作する。サーバが、それまでの相互動作を記憶する特別なキャッシュモデルを維持する必要がないことから、一般的には、ステートレスで動作しているということが多い。
【００５８】
二つ目の方法（図８）としては、クライアント１０１とサーバ１０２は、「セッション」を確立し、サーバ１０２は、クライアント１０１へ送られた符号データを記憶しておくキャッシュモデルをもっている。即ち、サーバのキャッシュモデルには、それまでにサーバ１０２に送信したことについての情報の記録がなされている。クライアント１０１のキャッシュには、サーバ１０２から受信した符号データが保存され、サーバ１０２は、キャッシュモデルを用いることによって、既に転送した符号データをクライアント１０１に転送することなく、再利用できる。典型的には、クライアント１０１は、断片的に受信したＪＰＥＧ２０００の符号データを、受信した順番にデータをアペンドしキャッシュに保存する。続いて、前述したようにキャッシュしたデータからＪＰＥＧ２０００のシンタックスに準拠したビットストリームを作成し、そのビットストリームをデコードする。
【００５９】
本発明は、主に、ステートレスな要求を処理する図８に係り、キャッシュ管理部１０８を有することで、キャッシュ１０３のキャッシュデータを管理する。
【００６０】
クライアント１０１は、それまでに要求した符号データの全てを受信する前にさえも、興味のある画像の部分に対応する符号データを変更し得る。あるサーバは、これらの変更を扱うために、前の要求に対する応答を割り込みすることができる。
【００６１】
図９は、典型的なネットワークを示す。図９を参照すると、ネットワークは、複数のクライアント（例えば、クライアント２４０，３１１，３１２）と複数のサーバを含む。単一のサーバは、数１００万の異なるクライアントへ同じ画像の異なる部分を扱い得る。単一のクライアントは、画像と他のデータ（例えば、ＨＴＭＬページ）を、幾つかのサーバから受信する。プロキシサーバは、オリジナルサーバと通信すること無しに幾つかの要求への素早い応答を可能とするために、ネットワーク内に存在し得る。有効な帯域幅と帯域幅のコストは、異なるクライアントと同じサーバの間で又は、異なるサーバの間で広く変わる。
【００６２】
最も一般的に使用されるネットワークは、インターネット又はワールドワイドウェブである。しかし、ＪＰＩＰは、ローカルエリアネットワーク（ＬＡＮ）又は、どのような一般的な相互接続システムにも適用できる。ＪＰＩＰは、ハイパーテキスト転送プロトコル（ＨＴＴＰ）の上で最も一般的に転送されるが、しかし、ＴＣＰ／ＩＰ及びＵＤＰを含む他の転送プロトコルと共に使用されると予想される。
【００６３】
以上のことから、ＪＰＩＰストリームの符号フォーマット（メッセージ）を分析することで、コンポーネント数、レイヤ数、プレシンクトサイズ、デコンポジション分割数などの階層符号データを構成する各階層のレベル数が分かる。また、プログレッション順序についても知ることができる。
【００６４】
図１０は、ＪＰＩＰを使用した場合の出力表示画面例を示す。図１０（Ａ）では、２つのタイルからなるデータが表示されており、例えば、それぞれのタイルをクリックすることによって画像データが表示され、図１０（Ｂ）のような画質の劣ったタイル４枚からなる画像となる。さらに、右下をクリックすることによって、そのタイルの部分画像（図１０（Ｃ））の解像度が変倍され、部分画質レベルが向上する。このように、部分画像データを参照する場合に使用される。部分画像データを参照する都度、表示クライアント側からサーバ側へ符号データを転送要求し再生する。
【００６５】
このようにＪＰＩＰにおいては、クライアント（出力側）では、全ての（階層）符号データではなく、部分符号データを必要としていることを前提としている。そのため、部分符号データからオリジナルの符号データの階層構造を知ることができないという問題があった。
【００６６】
（４）ＪＰＥＧ２０００のコードストリームのフォーマット：
ＪＰＥＧ２０００のコードストリームは、画像についての全てのエントロピー符号化されたデータと、その符号化されたデータを復号するために使用されるべき方法を記述するデータを含む。
コードストリームは、使用されるウェーブレット変換に関する情報、タイルのサイズ、プレシンクトのサイズ、解像度に関する情報、ファイル内のパケットの順序等を含む。コードストリームは、エントロピー符号化されたデータを画像サンプルに復号するのに必要な全てのパラメータを含まなければならない。コードストリームは、例えば、パケットの長さのような、符号化されたデータの部分への高速アクセスを提供する情報も含み得る。
【００６７】
ＪＰＥＧ２０００のコードストリームのフォーマットの概略構成を図１１（Ａ）に示す。ＪＰＥＧ２０００の「コードストリーム」には、いくつかのマーカセグメントをもっている。マーカセグメントとは、一つの２バイト長よりなるマーカとそれに付随するパラメータ群から構成されている。各マーカセグメントには機能、用途、データ長が表されている。コードストリームのフォーマットは符号データの始まりを示すＳＯＣ（Ｓｔａｒｔ  ｏｆ  Ｃｏｄｅｓｔｒｅａｍ）マーカで始まる。ＳＯＣマーカの後には、符号化のパラメータや量子化のパラメータ等を記述したメインヘッダが続き、その後に実際の符号データが続く。
【００６８】
メインヘッダの構成を図１１（Ｂ）に示す。メインヘッダはＣＯＤ，ＱＣＤの必須マーカセグメントと、ＣＯＣ，ＱＣＣ，ＲＧＮ，ＰＯＣ，ＰＰＭ，ＴＬＭ，ＰＬＭ，ＣＲＧ，ＣＯＭのオプションマーカセグメントで構成される。ここで、ＳＩＺマーカセグメントには、コンポーネント数とかタイルサイズなどの非圧縮時の画像の情報が記述され画像コンポーネントの幅と高さについての情報を含む。ＣＯＤとＣＯＣマーカセグメントは、圧縮されたデータはどの様に復号されるべきかを示すパラメータを含む。ＣＯＤマーカにはプログレッション順序、レイヤ数、プレシンクトサイズ、デコンポジション分割数が記述されている。ＱＣＤマーカは量子化に係る情報が記載されている。また、ＣＯＭマーカはコメント等の情報を付加したいときに利用するマーカで、メインヘッダ、タイルヘッダの双方で使用することが可能である。
【００６９】
メインヘッダの後に、一連の「タイルパート」がある。各タイルパートは、特定のタイルと部分を識別する「ＳＯＴ（Ｓｔａｒｔ  ｏｆ  Ｔｉｌｅ−ｐａｒｔ）」マーカセグメントで始まる。各タイルパートについて符号化されたデータには、「ＳＯＴ」マーカセグメントが先行する。「ＳＯＴ」マーカセグメントには、タイルパート数に係る情報を含んでいる。
【００７０】
実際の符号データ（図１２）は、ＳＯＴマーカで始まり、タイルヘッダ、ＳＯＤ（Ｓｔａｒｔ  ｏｆ  ｄａｔａ）マーカ、タイルデータ（符号）で構成される。これら画像全体に相当する符号データの後に、符号の終了を示すＥＯＣ（Ｅｎｄ  ｏｆ  Ｃｏｄｅｓｔｒｅａｍ）マーカが付加される。メインヘッダはＣＯＤ，ＱＣＤの必須マーカセグメントとＣＯＣ，ＱＣＣ，ＲＧＮ，ＰＯＣ，ＰＰＭ，ＴＬＭ，ＰＬＭ，ＣＲＧ，ＣＯＭのオプションマーカセグメントで構成される。
【００７１】
タイルヘッダ構成を図１１（Ｃ）（Ｄ）に示す。同図は、タイルデータの先頭に付加されるマーカセグメント列であり、ＣＯＤ，ＣＯＣ，ＱＣＤ，ＱＣＣ，ＲＧＮ，ＰＯＣ，ＰＰＴ，ＰＬＴ，ＣＯＭのマーカセグメントが使用可能である。一方、図１１（Ｄ）は、タイル内が複数に分割されている場合における分割されたタイルパートの先頭に付加されるマーカセグメント列であり、ＰＯＣ，ＰＰＴ，ＰＬＴ，ＣＯＭのマーカセグメントが使用可能である。タイルヘッダでは必須マーカセグメントはなく、すべてオプションである。
タイルデータ（符号）は、連続したパケットで構成される。コードストリーム中のパケットの順番をプログレッション順序と呼んでいる。
【００７２】
以上のことから、ＪＰＥＧ２０００コードフォーマットを分析することで、コンポーネント数、レイヤ数、プレシンクトサイズ、デコンポジション分割数などの階層符号データを構成する各階層のレベル数がわかる。また、プログレッション順序についても知ることができる。
【００７３】
以上の事実を踏まえて、以下に示した問題解決の考え方に沿って、本発明の実施形態を詳細に説明する。
【００７４】
（Ａ）階層符号データのプログレッション順の使用頻度に基づいて、高頻度で部分符号データをアクセスする単位を推定する。推定された高頻度にアクセスしている階層レベル単位でキャッシュデータのオーバーフロー時の符号データの入れ替えを施す。このようにしてキャッシュのヒット率を改善する。
【００７５】
（Ｂ）キャッシュ上の符号データを、その階層構造が柔軟に変更できるような階層構造を反映したデータ構造にしておき、使用状況に適応的に階層構造を変換できる構造にしておくことで、効率的かつ効果的なキャッシュ制御ができる。
【００７６】
（Ｃ）さらに、キャッシュデータのオーバーフロー時のデータ入れ替えの管理が、キャッシュデータのデータ構造に対応して階層単位で符号データが全て揃っているかいなかを判別し、階層単位でパケットが全て揃っていないという事態をなるべく起こさないようにして、キャッシュのヒット率を改善する。アクセス単位となっているパケットが全て揃っているようにキャッシュデータの入れ替え処理をする。
【００７７】
（５）キャッシュデータオーバーフロー時のデータ入れ替えが階層符号データの構造化要素単位：
本発明の構成では、キャッシュのオーバーフロー時のデータ（符号列）の入れ替え処理単位がアクセス単位である。
【００７８】
図１３は、本発明のキャッシュのオーバーフロー時のデータ（符号列）の入れ替え処理の概念を説明するための図である。図１３では、メモリはキャッシュを含め２個備えているが、一般的な画像処理装置には、高速なアクセスが可能であるキャッシュと通常のアクセス時間のかかる記憶装置と、アクセス時間が遅い外部記憶装置など処理速度の異なるメモリを複数個有しているが、本発明では、主に高速なアクセスが可能なキャッシュのオーバーフロー時の処理について考える。
【００７９】
キャッシュ上の符号データは、構造テーブルで管理しており、符号データの保存先を示している。
新しい符号データをキャッシュに保存する場合に、キャッシュ上の符号データの保存領域が一杯になったときは、次の処理を行うが、本発明では、係る符号データの削除あるいは入れ替えの場合の符号データの単位を調整する方法に着目した。
【００８０】
（Ｂ）符号データの一部を削除し、あるいは、別の記憶装置に該符号データを移し替え、その構造テーブルには、ＮＵＬＬが記入される。
（Ｃ）新たな符号データをキャッシュに書き込む。
（Ｄ）構造テーブルに新しい項目を追加し、該符号データへのアドレス（ポインタ）を書き込む。
【００８１】
図１４は、キャッシュデータオーバーフロー時のデータ入れ替え処理を示すフローチャートである。
保存データ入替え処理は、階層符号データの一部または全部の保存要求待ち（Ｓ１）、終了の指定があれば（Ｓ２／ＹＥＳ）、処理を終了する。一方、保存の要求があれば（Ｓ２／ＮＯ）、保存する符号データの符号量を算出して残符号量と比較する（Ｓ３）。
【００８２】
次に、使用状況（プログレッション順の使用頻度）に基づいてデータ入れ替え単位の階層決定する（Ｓ４，Ｓ５，Ｓ６）。
このために、プログレッション順の使用頻度を算出し（Ｓ４）、使用頻度が最大であるプログレッション順を選択し（Ｓ５）、プログレッション順に合わせた階層構造のキャッシュデータ構造生成処理を実行する（Ｓ６）。
【００８３】
次に、階層レベル毎に保存データ入れ替え処理を行う（Ｓ７〜Ｓ１０）。
先に計算した残符号量が不足ならば（Ｓ７／ＹＥＳ）、入れ替えする階層レベルを決定し（Ｓ８）、階層レベル単位で階層符号データを一部または全部削除して（Ｓ９）、ステップＳ１へ戻る。
一方、残符号量が充分あれば（Ｓ７／ＮＯ）、記憶装置にデータを保存して（Ｓ１０）、ステップＳ１へ戻る。
【００８４】
図１５は、キャッシュデータ（符号列構造）管理のためのデータ構造の基本構成図である。管理テーブルと構造テーブルと符号列保存部よりなる。本実施形態では、構造テーブルは、表形成であるが、後述する別の実施形態（図１６）では、ツリー構造を持っている。
管理テーブルは、符号データ名（ファイル名）、階層数、各階層毎の階層レベル数（階層レベルの最大値）、構造データへのアドレス（ポインタ）により構成されている。階層数により階層レベル数の項目の数が変更される。
この構造テーブルは、階層レベル数の各階層分の組み合わせの全ての項目を含む。符号列の属する各階層の階層レベルに該当する符号データへのポインタの部分に該符号列が保存されている。
【００８５】
図１６あるいは図１７は、キャッシュ管理テーブル、構造テーブルの例である。構造データを表す形式が、ツリー構造であるところが特徴であり、このツリー構造は、前述した図１５のテーブル構造とは互換性がある。即ち、テーブル構造は、ツリー構造へ変換することも、逆も任意に変更することができる。ツリー構造をもつ構造テーブルは、階層ノードにより構成されている。各階層ノードは、階層レベルＮｏと下位階層レベルへの全てのポインタと情報項目より構成されている。最下位の階層では、各階層ノードは階層レベルＮｏと符号列へのポインタ格納領域をもっている。下位階層レベルへの全てのポインタは持っていない。また、符号列がない場合は、該ポインタ格納領域はＮＵＬＬになっている。
【００８６】
ところで、図１５乃至図１７で示した構造データを使用することによって、ある階層レベルに属する符号列を参照することは容易である。符号列に対応してそれの属する階層レベルを知ることが容易であり、かつ、階層毎に階層レベルによって体系化された形式で保存されているからである。
【００８７】
例えば、最上位階層の階層レベルが１である符号データは、符号データに対応した同階層の階層レベルが１である符号列を探せばよいが、図１５のテーブルタイプの構造データにおいては、連続的に並んでいるため参照は高速にできる。一方、図１６の構造データにおいては、階層ノードの該当する階層の階層レベル番号が１である階層ノードから下位階層ノードへのポインタを辿っていくことで該符号列を参照できる。
【００８８】
ツリー構造の構造データにおいては、各階層ノードは、情報項目を持つが、図１７では、下位階層の符号列の符号列の符号量の合計値を記録している。符号列を保存するときに、その符号列の属する階層レベルにあたる階層ノードの同項目の値（符号量の値）をカウントアップすることによって生成する。
【００８９】
図１８は、図１７のキャッシュ構造の生成処理を示すフローチャートである。
キャッシュデータ構造生成処理は、まず、部分符号データの受信を待って、部分符号データを受信する（Ｓ１１）。
【００９０】
次に、部分符号データに含まれる符号列の階層レベルを抽出し（Ｓ１２）、キャッシュデータ管理テーブルへ符号列の最高階層レベル番号を書き込む（断片的な符号列（パケット）群より構造を把握）（Ｓ１３）。
【００９１】
次に、キャッシュの更新処理を行う（Ｓ１４〜Ｓ２２）。
まず、キャッシュデータ管理テーブル上の各階層のレベル数を読み込み（Ｓ１４）、前記レベル数をもつ階層ノードデータを作成する（Ｓ１５）。ここで、階層ノードデータは、次の項目からなっている。
【００９２】
（ｉ）階層レベルＮｏ、
（ｉｉ）下位階層の階層ノードデータへのポインタ、
（ｉｉｉ）下位階層データ有無フラグ、
（ｉｖ）下位階層の符号列の総符号量。
【００９３】
そして、各階層ノードデータの（ｉ）階層レベルＮｏを記載し（Ｓ１６）、各階層ノードデータの（ｉｉ）下位階層の階層ノードデータへのポインタを記載して、この時最下位階層ノードデータの（ｉｉ）下位階層の階層ノードデータへのポインタの初期値はＮＵＬＬとし、また、（ｉｉｉ）下位階層データ有無フラグは０とし、また、（ｉｖ）下位階層の符号列の総符号量は０とする（Ｓ１７）。
【００９４】
次に、保存対象とする符号列毎に順次Ｓ１８〜Ｓ２２の処理をする。
保存対象とする符号列を取得し（Ｓ１８）、対象の符号列がなければ（Ｓ１９／ＮＯ）、ステップＳ１１へ戻る。
一方、（Ｓ１８）、対象の符号列があれば（Ｓ１９／ＹＥＳ）、符号列を保存し（Ｓ２０）、階層ノードデータを上位階層から下位階層へと辿りながら、その符号列の各階層レベルで（ｉ）階層レベルＮｏと一致する最下位の階層ノードデータを探し、該最下位の階層ノードデータの（ｉｉ）下位階層の階層ノードデータへのポインタ先を、符号列が保存されているアドレスとする（Ｓ２１）。この時、上位階層の階層ノードデータから（ｉｉ）下位階層の階層ノードデータへのポインタ先を辿っていった時の階層レベルＮｏが、その符号の階層レベルであるようになっている。
【００９５】
階層ノードデータを上位階層から下位階層へと辿りながら、該最下位の階層ノードデータの（ｉｉ）下位階層の階層ノードデータへのポインタを書き込む時に、辿られた階層ノードデータの（ｉｉｉ）下位階層データ有無フラグに１を加算し、（ｉｖ）下位階層の符号列の総符号量に該符号列の符号量を加え（Ｓ２２）、ステップＳ１８へ戻る。
【００９６】
また、図１９は、キャッシュ管理処理のフローチャートであり、図２０は、キャッシュ更新要求処理のフローチャートである。
図１９のクライアントのキャッシュ管理処理は、キャッシュ管理要求を解析し（Ｓ３１）、この要求に応じて処理する（Ｓ３２）。
【００９７】
キャッシュ更新処理要求の場合には、キャッシュ更新要求処理を行って（Ｓ３３）、処理を終了する。
【００９８】
キャッシュ構造変更処理要求の場合には、キャッシュ構造変更処理を行って（Ｓ３４）、符号データの最上位階層レベルの使用頻度に基づき、最も使用頻度の多い階層レベルを算出し（Ｓ３５）、必要に応じてキャッシュメモリあるいは外部記憶装置の構造データを変更する（符号データの最上位階層レベルの変更）（Ｓ３６）。また、必要に応じて復号処理の許容プログレッションに対応するように構造データを変更して（Ｓ３７）、処理を終了する。
【００９９】
新規生成要求の場合には、キャッシュの新規生成処理を行って（Ｓ３８）、管理データを新たに構築し（Ｓ３９）、符号データを保存して（Ｓ４０）、処理を終了する。
追加保存要求の場合には、追加保存要求処理を行って（Ｓ４２）、構造データに基づいて追加符号データの保存位置を特定し（Ｓ４３）、符号データを保存して（Ｓ４４）、処理を終了する。
【０１００】
参照要求の場合には、参照要求処理を行って（Ｓ４５）、構造データに基づいて符号データの範囲にある符号データを参照して（Ｓ４６）、処理を終了する。
【０１０１】
図２０のキャッシュ更新要求処理は、部分符号データの受信を待って、部分符号データを受信する。（Ｓ５１）。
部分符号データに含まれる符号列の階層レベルを抽出し（Ｓ５２）、キャッシュデータ管理テーブルへの符号列の最高階層レベルを書き込み（断片的な符号列（パケット）群より構造を把握）（Ｓ５３）、構造データテーブルの更新および符号データを書き込んで（Ｓ５４）、ステップＳ５１へ戻る。
【０１０２】
図２１は、入れ替え単位選択システム構成図であり、階層符号データ記録管理に使用するスタンドアローンタイプである。
記録管理装置２０１には、符号データ解析部１０１０、管理テーブル構造テーブル生成処理部１０１１、管理テーブル構造テーブル変更処理部１０１２、管理テーブル構造テーブル参照処理部１０１３、符号データ保存処理部１０１４、及び、データ入れ替え必要性判別部１０１５、入れ替え単位設定部１０１６、入れ替え制御部１０１７を備えている。
【０１０３】
符号データ解析部１０１０では、符号データを解析し、構造を推定するために必要な各符号列の情報（階層数と各階層ごとのその符号列の属するレベル）を抽出する。
管理テーブル構造テーブル生成処理部１０１１では、各符号列の情報（部分符号データに含まれる符号列の階層レベル）を使用して管理テーブルと構造テーブルを生成する。このとき、符号列は、符号データ保存処理部１０１４で保存処理する。管理テーブルと構造テーブルを変更したり（管理テーブル構造テーブル変更処理部１０１２）、あるいは、参照したり（管理テーブル構造テーブル参照処理部１０１３）する機能も具備している。
【０１０４】
キャッシュデータオーバーフロー時のデータ入れ替え処理（図１４）で説明したように、本発明のデータの入れ替え処理は、データ入れ替え必要性判別、データ入れ替え単位の決定および階層レベル毎に保存データ入れ替え処理よりなっている。
データ入れ替え必要性判別部１０１５では、「データ入れ替え必要性判別」を、入れ替え単位設定部１０１６では「データ入れ替え単位の決定」を、入れ替え制御部１０１７では「階層レベル毎に保存データ入れ替え処理」を実行する。
【０１０５】
図２２は、入れ替え単位選択システムの他の構成図であり、クライアントサーバ・キャッシュシステムである。
キャッシュ管理部１０８には、図２１と同様に、符号データ解析部１０１０、管理テーブル構造テーブル生成処理部１０１１、管理テーブル構造テーブル変更処理部１０１２、管理テーブル構造テーブル参照処理部１０１３、符号データ保存処理部１０１４、及び、データ入れ替え必要性判別部１０１５、入れ替え単位設定部１０１６、入れ替え制御部１０１７を備えている。
【０１０６】
（６）入れ替え単位学習機能：
先に示した構造テーブルは、入れ替え単位の柔軟な調整機能をもつ。
図２３は、キャッシュ上の符号データのプログレッションオーダの変更方法を説明するための概念図である。構造テーブルとしては、図１５で説明したテーブルタイプのものを示すが、図１６で示したツリータイプのものであっても同様である。互いに相互変換可能であるからである。構造テーブルの入れ替えとしては、階層レベルＮｏの記載された行の値によって列単位の順番を入れ替えることで実現する。即ち、最上位の階層の階層レベル順に列単位のデータを並び替え、続いて、次の階層の階層レベル順を上位階層のレベル順が損なわないように並び替え、続いて、同様な並び替えを下階層の階層レベルまで繰り返して処理する。
【０１０７】
したがって、これらの構造データを使用することにより入れ替え単位を符号データの階層に基づいて選択制御することができる。
このように、キャッシュデータの入れ替え単位が階層レベル単位であることで、使用状況に合わせたデータの入れ替えができる。階層とは、階層符号データの分割単位である、解像度とか領域とか画質である。また、階層のレベルとは、階層符号データの各階層ごとの分割単位であり、例えば、解像度１、解像度２、・・である。
【０１０８】
図２４は、プログレッションとアクセス単位の関係を説明するための図である。符号データの構成を示し、斜線ブロックが削除対象を示す。例１では、Ｌ３の構造レベルの符号データを削除する。再生画像は画質レベルの調整が加えられ、画質レベルが最上位階層である可能性が大である。
一方、例２では、符号データは領域単位で削除され、領域レベルが最上位階層である可能性が大であると推定する。係る観点により、階層符号データのプログレッション順（階層単位での並び順）は、該符号データで該階層の階層レベル単位で削除される可能性の高さを示すものと推定することができる。
【０１０９】
本発明では、このような思想に基づいて、図２５に示すようなプログレッションを学習するためのテーブルを用いて使用状況の集計をする。図２２の構成例では、サーバ側の、データ構造別使用頻度算出部１０９で集計し、クライアント側へ結果を知らせる。
【０１１０】
図２６は、典型的な使用状況を記録する処理のフローチャートである。
保存データ入替え処理は、サーバにて、ロスレス符号データの構造を記録し（Ｓ６１）、生成符号データのプログレッション順を算出し（Ｓ６２）、使用状況（プログレッション順の使用頻度）を記録し（Ｓ６３）、使用状況記録をクライアントへ転送する（Ｓ６４）。
クライアントでは、サーバから転送された保存データの入替え処理を行う（Ｓ６５）。
【０１１１】
ところで、図２５で示す階層毎の階層レベルの組み合わせパターンは、図１８の符号データの構造把握の処理にあるように、符号列から階層レベル数を推定することができる。
【０１１２】
図２７に同様な、符号データのプログレッション順（階層単位での並び順）に基づいて入替え単位を決定する実現概念図を示す。この例では、階層は、解像度レベル、領域レベル、画質レベルで区分されており、プログレッション順の使用頻度によって最上位階層が解像度であった回数が２回、領域であったのが８回、画質であったのが３回であることから、大きい順番に符号データ入れ替え要求が多いものとして、構造データテーブルを構成し、最上位階層の単位で符号データを入れ替える。まとまって使用される可能性の高い単位でキャッシュ上のデータを入れ替えることでキャッシュのヒット率を改善することができる。
【０１１３】
（７）データ符号量に基づいて入れ替え制御：
図１７は、先に説明したように、図１８を使用して生成したデータ符号量の制御に係るデータ構造例である。図１７の構造テーブルを使用することにより、符号量に基づくキャッシュ上の符号列を入れ替え制御することができる。
【０１１４】
図２８は、データ符号量に基づく入れ替え制御処理のフローチャートである。データ符号量に基づいて階層を選択し符号データ（符号列）を入れ替え制御する。
【０１１５】
クライアントのデータ符号量に基づく入替え処理は、データ入れ替え必要性を判別し（Ｓ７１）、データ入れ替え単位を決定する（Ｓ７２）。
次に、階層レベル毎に保存データ入れ替え処理を行う（Ｓ７３〜Ｓ８４）。
まず、残符号量が充分（残符号量≧必要符号量）ならば（Ｓ７３／ＮＯ）終了する。
一方、不足（残符号量＜必要符号量）ならば（Ｓ７３／ＹＥＳ）、削除階層を（Ｓ７２）で決定した階層として、入れ替えする階層レベルを決定する（Ｓ７４〜Ｓ８３）。
【０１１６】
まず、積算符号量＝０とし（Ｓ７４）、削除階層の階層レベルにある、最上位階層の階層レベル毎の符号量Ａを抽出し（Ｓ７５）、「積算符号量＝積算符号量＋符号量Ａ」を計算する（Ｓ７６）。
【０１１７】
ここで、必要符号量＞積算符号量であれば（Ｓ７７／ＹＥＳ）、該階層レベルを削除対象とし（Ｓ７８）、階層レベル全て完了しており（Ｓ７９／ＹＥＳ）、全階層終了であれば（Ｓ８０／終了）、該符号データの符号列を全て削除対象に設定し（Ｓ８２）、階層レベル単位で階層符号データの一部または全部削除して（Ｓ８４）、終了する。
【０１１８】
一方、全階層未了であれば（Ｓ８０／未了）、削除階層を上位階層として（Ｓ８１）、ステップＳ７４へ戻る。
また、階層レベル未了であれば（Ｓ７９／ＮＯ）、次の階層レベルを設定し（Ｓ８３）、ステップＳ７５へ戻る。
【０１１９】
また、必要符号量≦積算符号量であれば（Ｓ７７／ＮＯ）、階層レベル単位で階層符号データの一部または全部削除して（Ｓ８４）、終了する。
【０１２０】
これにより、データ符号量に基づいて、階層符号データの階層レベル単位で符号データを入れ替える手段を提供する。
【０１２１】
（８）欠落符号列を考慮したキャッシュ入替え：
また、欠けている符号列を含むグループを優先的に入れ替えることもできる。
クライアントの欠落符号列の判別処理は、次のような手順で処理する。
キャッシュデータ管理テーブル上の各階層のレベル数を読み込み、指定の階層レベルＳの階層ノードデータを上位階層から下位階層へと辿りながら、Ｍ番目の階層の階層ノードデータの（ｉｉｉ）下位階層データ有無フラグの値Ｐについて次の判断処理を行う。
【０１２２】
Ｐ＜Ｄ（１）×Ｄ（２）…×Ｄ（Ｍ−１）である場合、指定の階層レベルＳを構成する符号列には欠落符号列を含んでおり、欠落符号列の数はＤ（１）×Ｄ（２）…×Ｄ（Ｍ−１）−１とする。ここで、Ｎをキャッシュデータ管理テーブル上の階層数、ｍ＝１〜Ｎとし、下からｍ番目の階層でＤ（ｍ）個のレベル数とする。
また、Ｐ＞Ｄ（１）×Ｄ（２）…×Ｄ（Ｍ−１）である場合、指定の階層レベルＳを構成する符号列には欠落符号列を含んでいない。欠落符号列の数は０とする。
【０１２３】
図２９は、上記欠落符号列の判別結果を用いて、欠落符号列を考慮したキャッシュ入れ替え制御する処理のフローチャートである。
クライアントのデータ符号量に基づく入れ替え処理は、データ入れ替え必要性を判別し（Ｓ９１）、データ入れ替え単位を決定する（Ｓ９２）。
次に、階層レベル毎に保存データ入れ替え処理を行う（Ｓ９３〜Ｓ１０５）。
まず、残符号量が充分（残符号量≧必要符号量）ならば（Ｓ９３／ＮＯ）終了する。
一方、不足（残符号量＜必要符号量）ならば（Ｓ９３／ＹＥＳ）、削除階層を（Ｓ９２）で決定した階層として、入れ替えする階層レベルを決定する（Ｓ９４〜Ｓ１０４）。
以下、該削除候補の階層について欠落符号列の数を算出し、欠落符号列の数の多い順に階層レベルを選択する（Ｓ９４）。
積算符号量＝０とし（Ｓ９５）、削除階層の階層レベルにある、最上位階層の階層レベル毎の符号量Ａを抽出し（Ｓ９６）、「積算符号量＝積算符号量＋符号量Ａ」を計算する（Ｓ９７）。
【０１２４】
ここで、必要符号量＞積算符号量であれば（Ｓ９８／ＹＥＳ）、該階層レベルを削除対象とし（Ｓ９９）、階層レベル全て完了しており（Ｓ１００／ＹＥＳ）、全階層終了であれば（Ｓ１０１／終了）、該符号データの符号列を全て削除対象に設定し（Ｓ１０３）、階層レベル単位で階層符号データの一部または全部削除して（Ｓ１０５）、終了する。
【０１２５】
一方、全階層未了であれば（Ｓ１０１／未了）、削除階層を上位階層として（Ｓ１０２）、ステップＳ９５へ戻る。
また、階層レベル未了であれば（Ｓ１００／ＮＯ）、次の階層レベルを設定し（Ｓ１０４）、ステップＳ９６へ戻る。
また、必要符号量≦積算符号量であれば（Ｓ９８／ＮＯ）、階層レベル単位で階層符号データの一部または全部削除して（Ｓ１０５）、終了する。
【０１２６】
このように、使用される単位の符号データの符号列が全て揃っていない場合には、使用価値が低いので、優先的に入れ替える手段を提供できる。
【図面の簡単な説明】
【０１２７】
【図１】階層符号化圧縮伸長アルゴリズムの基本の説明図である。
【図２】デコンポジション・レベルとサブバンドの説明図である。
【図３】タイル分割の基本の説明図である。
【図４】プレシンクトとコードブロックの説明図である。
【図５】コードストリームの構造の説明図である。
【図６】プレシンクト・データビンとメッセージとの関係を示す説明図である。
【図７】プレシンクト・データビンの例である。
【図８】キャッシュを持ったクライアントサーバモデルの構成図である。
【図９】クライアントサーバネットワークモデルの構成図である。
【図１０】出力表示例である。
【図１１】ＪＰＥＧ２０００のコードストリームのフォーマットである。
【図１２】ＪＰＥＧ２０００のコードストリームの例である。
【図１３】本発明のキャッシュのオーバーフロー時のデータ（符号列）の入れ替え処理の概念図である。
【図１４】キャッシュデータオーバーフロー時のデータ入れ替え処理を示すフローチャートである。
【図１５】キャッシュデータ（符号列構造）管理のためのデータ構造の基本構成図である。
【図１６】保存データの構造化に係る概念図である。
【図１７】データ符号量の制御に係るデータ構造例である。
【図１８】図１７のキャッシュ構造の生成処理を示すフローチャートである。
【図１９】キャッシュ管理処理のフローチャートである。
【図２０】キャッシュ更新要求処理のフローチャートである。
【図２１】入れ替え単位選択システムの構成図である。
【図２２】入れ替え単位選択システムの他の構成図である。
【図２３】キャッシュ上の符号データのプログレッションオーダの変更方法を説明するための概念図である。
【図２４】プログレッションとアクセス単位の関係の説明図である。
【図２５】保存符号データのプログレッション設定例である。
【図２６】典型的な使用状況を記録する処理のフローチャートである。
【図２７】入れ替え単位の決定の説明図である（まとまって使用される単位でデータ照合）。
【図２８】データ符号量に基づく入れ替え制御処理のフローチャートである。
【図２９】欠落符号列の判別結果を用いて、欠落符号列を考慮したキャッシュ入替え制御する処理のフローチャートである。
【符号の説明】
【０１２８】
１０１，２１１，２１２，２４０，３１１，３１２…クライアント、１０２，２０３…サーバ、１０３，２０３…キャッシュ、１０４…Ｊ２Ｋ復号器、１０５…出力画像、１０６…キャッシュモデル、１０７…Ｊ２Ｋファイル、１０８…キャッシュ管理部、１０９，１０１６０…データ構造別使用頻度算出部、１１０…要求、１１３…応答、１１２，２０２…記憶装置、２１０，３１０…ＬＡＮ、２５０…大規模ネットワーク、１０１０…符号データ解析部、１０１１…管理テーブル構造テーブル生成処理部、１０１２…管理テーブル構造テーブル変更処理部、１０１３…管理テーブル構造テーブル参照処理部、１０１４…符号データ保存処理部、１０１５…データ入れ替え必要性判別部、１０１６…入れ替え単位設定部、１０１７…入れ替え制御部、２０１…記録管理装置。
【図１】
0004773770.tif 000002
【図２】
0004773770.tif 000003
【図３】
0004773770.tif 000004
【図４】
0004773770.tif 000005
【図５】
0004773770.tif 000006
【図６】
0004773770.tif 000007
【図７】
0004773770.tif 000008
【図８】
0004773770.tif 000009
【図９】
0004773770.tif 000010
【図１０】
0004773770.tif 000011
【図１１】
0004773770.tif 000012
【図１２】
0004773770.tif 000013
【図１３】
0004773770.tif 000014
【図１４】
0004773770.tif 000015
【図１５】
0004773770.tif 000016
【図１６】
0004773770.tif 000017
【図１７】
0004773770.tif 000018
【図１８】
0004773770.tif 000019
【図１９】
0004773770.tif 000020
【図２０】
0004773770.tif 000021
【図２１】
0004773770.tif 000022
【図２２】
0004773770.tif 000023
【図２３】
0004773770.tif 000024
【図２４】
0004773770.tif 000025
【図２５】
0004773770.tif 000026
【図２６】
0004773770.tif 000027
【図２７】
0004773770.tif 000028
【図２８】
0004773770.tif 000029
【図２９】
0004773770.tif 000030