(57)【特許請求の範囲】
【請求項１】
初期像を表わす像データのアレーを処理するための方法において、
変換フィルタの所定のファミリーを像データのアレーに適用して、変換係数の連続サブ帯域を発生し、
第１ファイルデータ構造体のＮ個のサブセットを容易にデコードして、それに対応する複数Ｎの解像度レベル０ないしＮ−１において初期像を再構成するために、変換係数をエンコードし、そしてそのエンコードされた変換係数を第１ファイルデータ構造体に所定の順序で記憶し、各解像度レベルは、隣接する解像度レベルから第１の所定の非ゼロ解像度ファクタだけ解像度が異なり、
初期像をダウンサンプリングして、初期像より解像度の低いより小さな像を表わす像データの第２アレーを発生し、前記ダウンサンプリングは、前記変換フィルタの所定のファミリーを像データのアレーに適用することとは異なるものであり、
変換フィルタの所定のファミリーを像データの第２アレーに適用して、変換係数の連続サブ帯域を発生し、そして
第２ファイルデータ構造体のＭ個のサブセットを容易にデコードして、それに対応する複数Ｍの解像度レベル０ないしＭ−１において上記より小さな像を再構成するために、変換係数をエンコードし、そしてそのエンコードされた変換係数を第２ファイルデータ構造体に所定の順序で記憶し、各解像度レベルは、隣接する解像度レベルから第２の所定の非ゼロ解像度ファクタだけ解像度が異なり、
複数Ｐの個別の解像度レベルにおいて初期像を再構成するために、上記第１及び第２ファイルデータ構造体は、エンコードされた変換係数を記憶し、但し、Ｐは、Ｎより大きくそしてＭより大きい方法。
【請求項２】
上記第２ファイルデータ構造体に、上記第１ファイルデータ構造体へのリンクを記憶する段階を更に備え、このリンクは、クライアントコンピュータにおいて上記第２ファイルデータ構造体を見ながら上記第１ファイルデータ構造体にアクセスするのに使用されるものである請求項１に記載の方法。
【請求項３】
上記第２ファイルデータ構造体に、この第２ファイルデータ構造体をデコードして上記より小さな像を再構成するためのコンピュータプログラムを埋設する段階を更に備えた請求項２に記載の方法。
【請求項４】
上記第２ファイルデータ構造体に、この第２ファイルデータ構造体をデコードして上記より小さな像を再構成するためのコンピュータプログラムへのリンクを埋設する段階を更に備えた請求項２に記載の方法。
【請求項５】
上記エンコード段階は、変換係数の少なくとも１つのサブ帯域に対するエンコードされた値を、１つ以上のビット平面スレッシュホールドに基づいて２つ以上の部分に分割することを含み、その各部分は、変換係数の少なくとも１つのサブ帯域に対するエンコードされた値のビット平面の各個別の範囲を含み、そして
変換係数の少なくとも１つのサブ帯域に対して、エンコードされた値の最上位部分を像ファイルの第１隣接領域に記憶し、そしてエンコードされた値の最下位部分を像ファイルの第２隣接領域に記憶する請求項１に記載の方法。
【請求項６】
初期像を表わす像データのアレーを処理するための方法において、
変換フィルタの所定のファミリーを像データのアレーに適用して、変換係数の連続サブ帯域を発生し、
第１のファイルのＮ個のサブセットを容易にデコードして、それに対応する複数Ｎの解像度レベル０ないしＮ−１において初期像を再構成するために、変換係数をエンコードし、そしてそのエンコードされた変換係数を第１ファイルデータ構造体に所定の逆解像度順序で記憶し、各解像度レベルｉは、隣接する解像度レベルから４のファクタだけ解像度が異なり、
初期像をダウンサンプリングして、その像より解像度が２2N分の１であるより小さな像を表わす像データの第２アレーを発生し、前記ダウンサンプリングは、前記変換フィルタの所定のファミリーを像データのアレーに適用することとは異なるものであり、
変換フィルタの所定のファミリーを像データの第２アレーに適用して、変換係数の連続サブ帯域を発生し、そして
第２ファイルデータ構造体のＭ個のサブセットを容易にデコードするために、変換係数をエンコードし、そしてそのエンコードされた変換係数を第２ファイルデータ構造体に所定の逆解像度順序で記憶し、それに対応する複数Ｍの解像度レベル０ないしＭ−１においてより小さな像を再構成するようにし、各解像度レベルは、隣接する解像度レベルから４のファクタだけ解像度が異なり、
一連のＮ＋Ｍの解像度レベルにおいて初期像を再構成するために、上記第１及び第２ファイルデータ構造体は、エンコードされた変換係数を記憶し、各解像度レベルは、隣接する解像度レベルから４のファクタだけ解像度が異なる方法。
【請求項７】
上記第２ファイルデータ構造体に、上記第１ファイルデータ構造体へのリンクを記憶する段階を更に備え、このリンクは、クライアントコンピュータにおいて上記第２ファイルデータ構造体を見ながら上記第１ファイルデータ構造体にアクセスするのに使用されるものである請求項６に記載の方法。
【請求項８】
上記第２ファイルデータ構造体に、この第２ファイルデータ構造体をデコードして上記より小さな像を再構成するためのコンピュータプログラムを埋設する段階を更に備えた請求項７に記載の方法。
【請求項９】
上記第２ファイルデータ構造体に、この第２ファイルデータ構造体をデコードして上記より小さな像を再構成するためのコンピュータプログラムへのリンクを埋設する段階を更に備えた請求項７に記載の方法。
【請求項１０】
コンピュータシステムに関連して使用するためのコンピュータプログラム製品であって、コンピュータ読み取り可能な記憶媒体と、そこに埋設されたコンピュータプログラムメカニズムとを備えたコンピュータプログラム製品において、上記コンピュータプログラムメカニズムは、
変換フィルタの所定のファミリーを像データのアレーに適用して、変換係数の連続するサブ帯域を発生する像処理モジュールを備え、
この像処理モジュールは、
第１ファイルデータ構造体のＮ個のサブセットを容易にデコードして、それに対応する複数Ｎの解像度レベル０ないしＮ−１において初期像を再構成するために、変換係数をエンコードし、そしてそのエンコードされた変換係数を第１ファイルデータ構造体に所定の順序で記憶するための命令を含み、各解像度レベルは、隣接する解像度レベルから第１の所定の非ゼロ解像度ファクタだけ解像度が異なり、更に、
初期像をダウンサンプリングして、初期像より解像度の低いより小さな像を表わす像データの第２アレーを発生するための命令であって、前記ダウンサンプリングは、前記変換フィルタの所定のファミリーを像データのアレーに適用することとは異なるものである命令と、
変換フィルタの所定のファミリーを像データの第２アレーに適用して、変換係数の連続するサブ帯域を発生するための命令と、
第２ファイルデータ構造体のＭ個の重畳するサブセットを容易にデコードして、それに対応する複数Ｍの解像度レベル０ないしＭ−１においてより小さな像を再構成するために、変換係数をエンコードし、そしてそのエンコードされた変換係数を第２ファイルデータ構造体に所定の順序で記憶するための命令とを含み、各解像度レベルは、隣接する解像度レベルから第２の所定の非ゼロ解像度ファクタだけ解像度が異なり、
複数Ｐの個別の解像度レベルにおいて初期像を再構成するために、上記第１及び第２ファイルデータ構造体は、エンコードされた変換係数を記憶し、但し、Ｐは、Ｎより大きくそしてＭより大きいコンピュータプログラム製品。
【請求項１１】
上記像処理モジュールは、更に、上記第２ファイルデータ構造体に、上記第１ファイルデータ構造体へのリンクを記憶するための命令を含み、このリンクは、クライアントコンピュータにおいて上記第２ファイルデータ構造体を見ながら上記第１ファイルデータ構造体にアクセスするのに使用されるものである請求項１０に記載のコンピュータプログラム製品。
【請求項１２】
上記像処理モジュールは、更に、上記第２ファイルデータ構造体に、この第２ファイルデータ構造体をデコードして上記より小さな像を再構成するためのコンピュータプログラムを埋設するための命令を含む請求項１１に記載のコンピュータプログラム。
【請求項１３】
上記像処理モジュールは、更に、上記第２ファイルデータ構造体に、この第２ファイルデータ構造体をデコードして上記より小さな像を再構成するためのコンピュータプログラムへのリンクを埋設するための命令を含む請求項１１に記載のコンピュータプログラム製品。
【請求項１４】
上記エンコードする命令は、変換係数の少なくとも１つのサブ帯域に対するエンコードされた値を、１つ以上のビット平面スレッシュホールドに基づいて２つ以上の部分に分割するための命令を含み、その各部分は、変換係数の少なくとも１つのサブ帯域に対するエンコードされた値のビット平面の各個別の範囲を含み、そして
変換係数の少なくとも１つのサブ帯域に対して、エンコードされた値の最上位部分を像ファイルの第１隣接領域に記憶し、そしてエンコードされた値の最下位部分を像ファイルの第２隣接領域に記憶するための命令も含む請求項１０に記載のコンピュータプログラム製品。
【請求項１５】
コンピュータシステムに関連して使用するためのコンピュータプログラム製品であって、コンピュータ読み取り可能な記憶媒体と、そこに埋設されたコンピュータプログラムメカニズムとを備えたコンピュータプログラム製品において、上記コンピュータプログラムメカニズムは、
変換フィルタの所定のファミリーを像データのアレーに適用して、変換係数の連続するサブ帯域を発生する像処理モジュールを備え、
この像処理モジュールは、
ファイルのＮ個のサブセットを容易にデコードして、それに対応する複数Ｎの解像度レベル０ないしＮ−１において初期像を再構成するために、変換係数をエンコードし、そしてそのエンコードされた変換係数を第１ファイルデータ構造体に所定の逆解像度順序で記憶するための命令を含み、各解像度レベルｉは、隣接する解像度レベルから４のファクタだけ解像度が異なり、更に、
初期像をダウンサンプリングして、その像より解像度が２2N分の１であるより小さな像を表わす像データの第２アレーを発生するための命令であって、前記ダウンサンプリングは、前記変換フィルタの所定のファミリーを像データのアレーに適用することとは異なるものである命令と、
変換フィルタの所定のファミリーを像データの第２アレーに適用して、変換係数の連続するサブ帯域を発生するための命令と、
第２ファイルデータ構造体のＭ個のサブセットを容易にデコードして、それに対応する複数Ｍの解像度レベル０ないしＭ−１においてより小さな像を再構成するために、変換係数をエンコードし、そしてそのエンコードされた変換係数を第２ファイルデータ構造体に所定の逆解像度順序で記憶するための命令とを備え、各解像度レベルは、隣接する解像度レベルから４のファクタだけ解像度が異なり、
一連のＮ＋Ｍの解像度レベルにおいて初期像を再構成するために、上記第１及び第２ファイルデータ構造体は、エンコードされた変換係数を記憶し、各解像度レベルは、隣接する解像度レベルから４のファクタだけ解像度が異なるコンピュータプログラム製品。
【請求項１６】
上記像処理モジュールは、更に、上記第２ファイルデータ構造体に、上記第１ファイルデータ構造体へのリンクを記憶するための命令を含み、このリンクは、クライアントコンピュータにおいて上記第２ファイルデータ構造体を見ながら上記第１ファイルデータ構造体にアクセスするのに使用するものである請求項１５に記載のコンピュータプログラム製品。
【請求項１７】
上記像処理モジュールは、更に、上記第２ファイルデータ構造体に、この第２ファイルデータ構造体をデコードして上記より小さな像を再構成するためのコンピュータプログラムを埋設するための命令を含む請求項１６に記載のコンピュータプログラム製品。
【請求項１８】
上記像処理モジュールは、更に、上記第２ファイルデータ構造体に、この第２ファイルデータ構造体をデコードして上記より小さな像を再構成するためのコンピュータプログラムへのリンクを埋設するための命令を含む請求項１６に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピュータシステム、パーソナルデジタルアシスタンス、デジタルカメラ及び他の装置における像の処理、圧縮、通信及び記憶に係り、より詳細には、デジタルエンコードされた像を特定のウインドウサイズ及び多数の解像度で見ることができると共に、プリント、切断及びその他操作することのできる像管理システム及び方法に係る。
【背景技術】
【０００２】
像は、多数の解像度レベルで記憶することができる。低い解像度レベルでエンコードされた像データは、高い解像度レベルのデータより小さく、従って、通信に要する帯域巾は狭くそして記憶に要するメモリは少ない。像が多解像度使用で記憶されるときには、像データを、セット又はサブファイルの順序付けされたグループに分離し、各付加的なサブファイルが、像の解像度をあるレベルから次のレベルへ高めるのに必要な付加的なデータを与えるようにすることが望まれる。
更に、特定のファクタ（例えば４）だけ像の解像度を高めるために、各サブファイルにおける像データの量を、解像度の関連増加にほぼ比例させることも望まれる。例えば、各解像度レベルがその隣接解像度レベルから４のファクタだけ異なる場合には（例えば、レベル０：３２ｘ３２、レベル１：６４ｘ６４、レベル２：１２８ｘ１２８、等々）、各解像度レベルに対するエンコードされた像データの量が、次に高い解像度レベルに対するエンコードされた像データの量の約２５％程度でなければならない。別の観点から、第１レベルから次のレベルへ像の解像度を高めるのに使用されるサブファイルのデータ量は、理想的には、第１レベルに対するサブファイルのデータ量の約３倍でなければならない。
【０００３】
像のウェーブレット圧縮は、多数の解像度レベルを自動的に発生することが良く知られている。特に、Ｎ「層」のウェーブレット変換が像に適用される場合には、Ｎ＋１のデータ解像度レベルが発生され、データの最後のＬＬサブ帯域は、最も低い解像度レベルより成り、そしてデータの全てのサブ帯域は、最も高い解像度レベルを形成する。便宜上、ウェーブレット変換の「層」は、「レベル」とも称される。これら解像度レベルの各々は、その隣接レベルから各空間次元において２のファクタだけ異なる。これら解像度レベルは、最も低い解像度レベルに対してレベル０と示し、最終又は基本像の解像度である最も高い解像度レベルに対してサムネイル(thumbnail)レベルないしレベルＮと示す。
【０００４】
本発明の第１の観点は、２つの観察をベースとする。第１のこのような観察は、従来の及び所有権のあるほとんどのデータ圧縮及びエンコード方法を使用するときに、ウェーブレット圧縮により発生されるＮ個のレベルのデータの量が幾何数列で減少する傾向があることである。例えば、解像度レベル０のデータ量は、典型的に、解像度レベル１のデータ量の約８０％であるが、理想的には、解像度レベル１のデータ量の約２５％でなければならない。その結果、レベル０のデータは、レベル０の像を表示するのに必要なものより著しく多量のデータを含む。
換言すれば、レベル０のデータは、レベル０の低解像度表示として不必要に高いクオリティを与え、それ故、レベル０の解像度レベルで像を表示するのに必要な情報だけを与えることにより潜在的に得られるものより低い圧縮度となる。
【０００５】
第２の観察は、低解像度の像データ係数が、低解像度表示ではなく、全解像度表示に対して量子化されることである。というのは、これらのデータ係数は、像の低解像度表示を発生するのに使用されるだけでなく、像の高解像度表示を発生するときにも使用されるからである。
本発明のこの第１の観点によれば、上述したように、各解像度レベルのサブアレー又はサブファイルにおける像データの量を、その解像度レベルに関連した解像度の増加にほぼ比例させることが望ましい。
【０００６】
本発明の第２の観点は、再生像におけるタイル又はブロック境界の欠点を回避するために、ウェーブレット変換が像のタイル又はブロック境界を横切って従来適用されたという観察をベースとする。ウェーブレット変換は、関連長さを有するＦＩＲ（有限インパルス応答）フィルタとして実施することができる。「長さ」とは、各係数を発生するのに使用されるデータサンプルの数である。ウェーブレット変換は、それらの中心の周りで一般的に対称的であり、ウェーブレット変換を実施するフィルタがタイル又はブロックのエッジにあるときには、典型的にフィルタの半分又はほぼ半分が隣接ブロック又はタイルへと延びる。その結果、像のタイルをウェーブレット変換しながらメモリに隣接タイルの一部分を保持することが通常必要なだけでなく、ウェーブレット変換の各レベルに対して隣接タイルのエッジ係数をメモリに保持することも必要となる。従って、タイル化効果（タイルボーダー効果又は欠陥或いはエッジ欠陥とも称する）を回避すると、典型的に、像に対してウェーブレット変換を実行する装置又はコンピュータのメモリ要求が高まると共に、変換手順の複雑さも高まる。というのは、隣接タイル又はブロックからエッジデータ及び係数のメモリ位置を追跡することが必要になるからである。本発明の第２の観点によれば、隣接ブロックからデータに変換を適用する必要なく、且つ顕著なエッジ欠陥を形成することなく、処理されている像ブロックのデータのみに適用できるウェーブレット又はウェーブレット状変換を得ることが強く要望される。このような変換が得られると、メモリ要求が低減され、像のウェーブレット圧縮が簡単化される。
【０００７】
公知技術では、デジタル像を、一度に全部ではなく、一度に一部分づつ処理して、メモリ要求を低減することが知られている。例えば、像のＪＰＥＧ圧縮及びエンコードに使用されるＤＣＴ変換は、従来、８ｘ８ピクセルのタイルに使用される。しかしながら、像を処理のためにタイル化することに伴う良く知られた問題は、タイル化手順が不所望なタイルボーダー効果を発生することである。ＪＰＥＧ像におけるＤＣＴタイル化のボーダー効果は、タイルのサイズが非常に小さいために、タイル化効果が人間の目に比較的目立たないので、受け入れられると考えられる。
【０００８】
しかしながら、ＤＣＴ変換に代わって、ウェーブレット又はウェーブレット状変換を使用するときには、８ｘ８ピクセルのような非常に小さなタイルを使用することは実用的でない。ウェーブレット状変換は、ＤＣＴ変換よりも非常に良好なデータ圧縮を与えることが示されており、それ故、適度な量のワークメモリを使用しながらタイル化効果を回避できる場合には、ウェーブレット状変換を使用するのが望ましい。
それ故、適度なサイズのタイル、例えば、６４ｘ６４、３２ｘ３２又は６４ｘ３２ピクセルのタイルでウェーブレット状変換を使用して像データを変換すると同時に、不所望なタイル化（タイルボーダー）効果の発生を回避することにより、８ないし２０ＫＢのような適度な量のワークメモリを使用して像を処理する像処理システム及び方法を提供することが望まれる。
【０００９】
本発明の第３の観点は、ウェーブレット係数に適用されるべき最適な量子化レベルが、ある変換サブ帯域から別の変換サブ帯域へと変化するだけでなく、像のある領域から別の領域へも変化するという観察をベースとする。より詳細には、多数の「特徴部」（典型的に水平又は垂直のライン又はエッジにより特徴付けられる）を含む像の領域は、少数の特徴部しかもたない領域より圧縮が困難である。即ち、このような濃密に特徴付けられた像領域は、圧縮データから再生される像領域のクオリティを低下することなく、あまり濃密に特徴付けられない領域のように圧縮することができない。それ故、少数の特徴部しかもたない領域のウェーブレット係数を量子化するのに使用される量子化除数より小さな量子化除数を使用して強く特徴付けられた領域のウェーブレット係数を量子化するような量子化手順を像圧縮及びエンコードシステムに設けることが望まれる。
【発明の開示】
【課題を解決するための手段】
【００１０】
要約すれば、本発明は、ウェーブレット状変換のような所定の変換のファミリーを像のための像データに適用して、変換像データを発生すると共に、この変換像データにデータ圧縮方法を適用して、像ファイルを発生するための像処理システム及び方法を提供する。この像処理システム及び方法は、捕獲された像をタイル化し、それらタイルを所定の順序で処理する。これらタイルは、像データの非重畳部分である。像データの各タイルは、変換層の所定のファミリーを像データのタイルに適用することにより処理され、変換係数の連続するセットが発生される。好ましい実施形態では、変換層は、ウェーブレット状デコンポジション変換のファミリーを次々に適用するもので、処理されているデータアレーの境界においてデータに適用されるエッジフィルタと、データアレーの内部領域においてデータに適用される内部フィルタとを含む。
【００１１】
各変換層により処理される変換係数のセットは、変換係数セットの外部境界に配置されたエッジ係数と、変換係数セットの内部位置に配置された非エッジ係数とを含む。変換係数のセットは、最後の変換層により発生された変換係数の最後のセットと、変換係数の１つ以上の早期セットとを含む。
使用する変換フィルタは、タイルの境界における像データと、変換係数の早期セット各々の境界及びその付近に配置された係数とに適用されて、エッジ係数を発生するための１つ以上のエッジ変換フィルタと、タイルの内部位置における像データと、変換係数の早期セットの内部位置における係数とに適用されて、非エッジ係数を発生するための１つ以上の内部フィルタとを備えている。エッジ変換フィルタは、内部変換フィルタより短いフィルタサポートを有し、そしてエッジ変換フィルタ及び長い内部変換フィルタは、両方とも、タイル内の像データのみに適用され、そして変換の早期セット内の変換係数のみに適用される。
【００１２】
エッジフィルタは、タイルの境界に最も接近した像データム、及び変換係数の各早期セットの境界に最も接近した変換係数を重み付けして、タイル境界欠陥を伴わずに変換係数から像を再生することができる短い低空間周波数のフィルタを含む。
少なくとも幾つかの変換フィルタは、好ましくは、非対称的な境界フィルタであって、各タイルの境界に向かって第１の程度まで延び、そしてタイルの境界から離れる方向に第２の、より長い程度まで延びるが、タイルの境界を越えて延びない。
【００１３】
好ましい実施形態では、上記内部変換フィルタは、処理されているデータアレーの中心又はその付近で２ないし４のハイパス及び２ないし４のローパス係数を発生するための中心フィルタを含む。この中心フィルタは、フィルタスイッチとして働く。２つの異なる形式の内部フィルタが中心フィルタの交互の側に使用される。例えば、内部フィルタは、中心フィルタの一方の側における偶数のデータ位置を中心としてもよいし、中心フィルタの他方の側における奇数のデータ位置を中心としてもよい。
又、像処理システム及び方法は、データ圧縮解除方法及び逆変換を像ファイルに次々に適用して、像ビューアに表示するのに適した再構成像を発生するための像再構成回路又は手順も包含する。
【００１４】
本発明の第２の特徴において、変換係数のセットは、像の空間周波数サブ帯域に対応する。サブ帯域は、それらを発生した変換層に基づいてグループ分けされる。サブ帯域の１つ以上の各グループに対し、像のタイルごとに、１つ以上のパラメータが発生され、その値は、タイルにおける像特徴の密度を表わす。像の各タイルは、１つ以上のパラメータの値に基づいて所定セットのカテゴリーの１つに分類される。タイルの分類に基づいて、タイルに対する量子化ファクタのセットが選択され、そしてタイルの変換係数が、量子化ファクタの選択されたセットでスケーリングされて、タイルに対する量子化された変換係数のセットが発生される。
【００１５】
本発明の第３の特徴においては、量子化された変換係数がエンコードされる。
空間周波数サブ帯域の各グループに対する係数がエンコードされる間に、それら係数のビット平面の最上位セットが第１ビット流において記憶され、そして係数のビット平面の残りの最下位セットが第２ビット流において記憶される。別の観点から、その値が所定のスレッシュホールドを越えるエンコードされた係数の部分（サブ帯域のグループに対する）が第１ビット流において記憶される一方、エンコードされた係数の残りの部分が第２ビット流において記憶される。特定の解像度レベルにおいて像ファイルから像を再構成するときには、その特定の解像度レベルに対応するビット流のみがデコードされ、そして像を再構成するのに使用される。ある解像度レベルに対して、使用されないビット流の１つ以上は、サブ帯域の最下位部分（即ちビット平面）を含み、そのより上位の部分は、その解像度レベルにおいて像を再構成するのに使用されるビット流に含まれる。
【発明を実施するための最良の形態】
【００１６】
本発明の付加的な目的及び特徴は、添付図面を参照した以下の詳細な説明及び特許請求の範囲から容易に明らかとなろう。
本書において、「ウェーブレット」及び「ウェーブレット状」という語は、交換可能に使用される。ウェーブレット状変換とは、一般に、従来のウェーブレット変換と同様の空間周波数特性を有し、ロスなしに可逆であるが、計算効率の良い短いフィルタを有する。
本発明は、上はワークステーション及びサーバーから下はクライアントコンピュータに至るまでの種々のコンピュータシステムを含む種々の像処理装置、及びデジタルカメラのようなアプリケーション特有の専用装置において実施することができる。
【００１７】
多解像度の像をエンコードしそして分配するシステム
図１は、ウェブサーバー１４０及び多数のクライアントコンピュータ１２０を備えていて、インターネットのようなグローバルな通信ネットワーク１１０、或いはローカルエリアネットワークやイントラネットのような他の適当な通信ネットワークを経て、クライアントコンピュータへ多解像度の像１９０を分配するための分散型コンピュータシステムを示している。像エンコードワークステーション１５０は、ウェブサーバーにより分配するための多解像度の像ファイルを準備する。ある実施形態では、ウェブサーバー１４０も、像エンコードワークステーション１５０の像エンコードタスクを実行することができる。
【００１８】
典型的なクライアント装置１２０は、パーソナルデジタルアシスタント、パーソナルコンピュータ、ワークステーション、又は特定タスク専用のコンピュータ制御装置である。クライアント装置１２０は、中央処理ユニット１２２と、メモリ１２４（高速ランダムアクセスメモリや、ディスク記憶装置のような不揮発性メモリを含む）と、通信ネットワーク１１０を経てウェブサーバーへクライアント装置を接続するためのネットワークインターフェイス又は他の通信インターフェイス１２８とを備えているのが好ましい。メモリ１２４は、典型的に、オペレーティングシステム１３２と、ブラウザアプリケーション又は他の像ビューイングアプリケーション１３４と、像デコーダモジュール１８０と、本発明によりエンコードされた多解像度の像ファイル１９０とを記憶する。好ましい実施形態では、ブラウザアプリケーション１３４は、Ｊａｖａ（登録商標）言語プログラムを実行するためのＪａｖａ（登録商標）バーチャルマシンを含むか又はそれに接続され、そして像デコーダモジュールは、Ｊａｖａ（登録商標）アプレットとして実施され、これは、像ファイル１９０と共にクライアント装置へ動的にダウンロードされ、従って、ブラウザは、像ファイルをビューイングのためにデコードすることができる。
【００１９】
ウェブサーバー１４０は、中央処理ユニット１４２と、メモリ１４４（高速ランダムアクセスメモリや、ディスク記憶装置のような不揮発性メモリを含む）と、ウェブサーバーをクライアント装置に接続すると共に通信ネットワーク１１０を経て像エンコードワークステーション１５０に接続するためのネットワークインターフェイス又は他の通信インターフェイス１４８とを含むのが好ましい。メモリ１４４は、通常、多解像度の像ファイル１９０に対する要求を含むｈｔｔｐ要求に応答するためのｈｔｔｐサーバーモジュール１４６を記憶する。ウェブサーバー１４０は、任意であるが、像処理モジュール１６８を、多解像度の像として像をエンコードするためのエンコード手順１７２と共に含む。
【００２０】
コンピュータシステム
図２を参照すれば、像処理ワークステーション１５０は、プログラムされた汎用コンピュータシステムを使用して実施することができる。又、この図は、ウェブサーバーが像処理タスクを実行するときにそのウェブサーバーも示す。コンピュータシステム１５０は、次のものを含む。
−  １つ以上のデータ処理ユニット（ＣＰＵ）１５２；
−  典型的に高速ランダムアクセスメモリ及び不揮発性メモリの両方を含むメモリ１５４；
−  ＣＲＴ又はＬＣＤ型ディスプレイのようなディスプレイ装置１５７を含むユーザインターフェイス１５６；
−  他のコンピュータ及び他の装置と通信するためのネットワーク又は他の通信インターフェイス１５８；
−  デジタルカメラとの間で像をやり取りするデータポート１６０（このような像転送は、ネットワークインターフェイス１５８を経て行うこともできるが）；及び
−  ＣＰＵ１５２、メモリ１５４、ユーザインターフェイス１５６、ネットワークインターフェイス１５８及びデータポート１６０を相互接続するための１つ以上の通信バス。
【００２１】
コンピュータシステムのメモリ１５４は、典型的に次のものを含む手順及びデータを記憶する。
−  基本的なシステムサービスを与えるためのオペレーティングシステム１６２；
−  オペレーティングシステムの一部分であるファイルシステム１６４；
−  像を見て操作するためのユーザレベルプログラムのようなアプリケーションプログラム１６６；
−  本書の対象であるものを含む種々の像処理機能を実行するための像処理モジュール１６８；
−  種々の像を表わす像ファイル１９０；及び
−  像処理及び像再生中に発生される中間結果のための一時的な像データアレー１９２。
【００２２】
又、コンピュータ１５０は、該コンピュータが多解像度の像の像処理及び分配の両方に使用されるときには、ｈｔｔｐサーバーモジュール１４６（図１）も含む。
像処理モジュール１６８は、像エンコーダモジュール１７０及び像デコーダモジュール１８０を含む。像エンコーダモジュール１７０は、多解像度の像ファイル１９０を発生し、その詳細は、以下に述べる。像エンコーダモジュール１７０は、次のものを含む。
−  像を圧縮しそしてエンコードする（別の像ファイルフォーマットの像をデコードすることにより導出される生の像アレー１８９でスタートして）プロセスを制御するエンコーダ制御プログラム１７２；
−  像を表わす像データにウェーブレット状フィルタを適用するためのウェーブレット状変換手順のセット１７４；
−  像に対する変換係数の各ブロック（又は帯域）に適用されるべき量子化除数を決定するためのブロック分類手順１７６；
−  像に対する変換係数を量子化するための量子化手順１７８；及び
−  量子化手順１７８により発生された量子化された変換係数をエンコードするためのエントロピーエンコード手順としても知られている希薄データエンコード手順１７９．
【００２３】
像処理モジュール１６８における手順は、部分的に変換された像及び他の一時的データを、一時的データアレーのセット１９２に記憶する。
像デコーダモジュール１８０は、次のものを含む。
−  像ファイル（又は像ファイルの一部分）をデコードしそして像ファイルのデータにより表わされた像を再生するプロセスを制御するためのデコーダ制御プログラム１８２；
−  像ファイルに記憶されたエンコードされ量子化された変換係数を、量子化された変換係数の対応アレーにデコードするための希薄データデコード手順１８４；
−  像のタイルを表わす変換係数のセットを量子化解除するための量子化解除手順１８６；及び
−  像のタイルを表わす量子化解除された変換係数のセットにウェーブレット状逆フィルタを適用して、像のそのタイルを再生するためのウェーブレット状逆変換手順のセット１８８。
【００２４】
像捕獲及び処理の概要
図３を参照すれば、デジタルカメラの像捕獲メカニズム（図１４）から或いは像スキャナ又は他の装置から得られた生の像データ２００は、「像データをタイル化する」ことにより処理される。より詳細には、生のデータは、タイル２０２のアレーとして処理され、各タイルは、６４ｘ６４（即ち、６４行ｘ６４列）のような所定のサイズを有する。他の実施形態では、３２ｘ３２、１６ｘ３２、１２８ｘ１２８、又は６４ｘ１２８のような他のタイルサイズを使用することもできる。これらのタイルは、像データの非重畳部分である。幾つかのタイルが生の像のエッジからオーバーハングしたとしても、処理されるべき生の像全体をカバーするに充分な数のタイルが使用される。タイルのオーバーハング部分には、ウェーブレット変換プロセス中に境界データ値のコピーが充填されるか、或いはナルデータが充填される。タイルの位置は、像の左上隅の原点に対して特定され、第１座標は、タイルのＹ位置（或いはタイル内のピクセル又は係数）を指示し、そして第２座標は、タイルのＸ位置（或いはタイル内のピクセル又は係数）を指示する。従って、位置０、１２８のタイルは、像の頂部に位置し、最も上のピクセル行の１２８番目のピクセルに原点を有する。
【００２５】
ウェーブレット又はウェーブレット状デコンポジション変換は、像の各タイルに次々に適用され、タイル内の生の像データが変換係数のセットに変換される。
ウェーブレット状デコンポジション変換が、像データの二次元アレーに適用される一次元変換であるときには、変換が、先ず、一方向（例えば、水平方向）に像データに適用されて、係数の中間セットを発生し、次いで、変換が他の方向（例えば、垂直方向）に係数の中間セットに適用されて、係数の最終セットを発生する。係数の最終セットは、ウェーブレット状デコンポジション変換を水平及び垂直の両次元に像データに適用した結果である。
タイルは、所定のラスタ走査順序で処理される。例えば、最上行のタイルが、一端（例えば、左端）から反対端（例えば、右端）へ進みながら処理され、その後、そのすぐ下の次のタイル行を処理し、生の像データのタイルの最下行が処理されるまで続けられる。
【００２６】
各タイルに対する変換係数は、ウェーブレット状デコンポジション変換を次々に適用することにより発生される。生の像データの最初の二次元アレーにウェーブレットデコンポジション変換を最初に適用すると、ＬＬ、ＨＬ１、ＬＨ１及びＨＨ１と示された４つの係数セットが発生される。ウェーブレットデコンポジション変換の各次々の適用は、以前のウェーブレット変換段階によって発生された係数のＬＬセットのみに適用され、４つの新たな係数セットＬＬ、ＨＬｘ、ＬＨｘ、及びＨＨｘが発生される。但し、ｘは、ウェーブレット変換「層」又は繰り返しを表わす。最後のウェーブレットデコンポジション変換繰り返しの後には、１つのＬＬセットしか残らない。発生された係数の全数は、オリジナルのデータアレーにおけるデータサンプルの数に等しい。各変換繰り返しにより発生される異なる係数セットは、層と称される。像に対して発生されるウェーブレット変換層の数は、典型的に、初期像の解像度の関数である。サイズ６４ｘ６４又は３２ｘ３２のタイルの場合には、５つのウェーブレット変換層を実行するのが典型的で、次の１６個の空間周波数サブ帯域のデータを発生する。即ちＬＬ5、ＨＬ5、ＬＨ5、ＨＨ5、ＨＬ4、ＬＨ4、ＨＨ4、ＨＬ3、ＬＨ3、ＨＨ3、ＨＬ2、ＬＨ2、ＨＨ2、ＨＬ1、ＬＨ1、ＨＨ1。変換層の数は、使用するタイルのサイズと、入手できる計算リソースの量の両方に基づき、実施形態ごとに相違する。大きなタイルの場合には、付加的な変換層がおそらく使用され、従って、データの付加的なサブ帯域を形成する。より多くの変換層を実行すると、付加的な計算時間を犠牲にして、良好なデータ圧縮がしばしば得られるが、付加的なタイルエッジ欠陥も発生する。
【００２７】
空間周波数サブ帯域は、次のようにグループ分けされる。サブ帯域グループ０は、ＬＬNサブ帯域に対応し、ここで、Ｎは、像（又は像タイル）に適用される変換層の数である。他の各々のサブ帯域グループｉは、３つのサブ帯域ＬＨi、ＨＬi、及びＨＨiを含む。以下に詳細に述べるように、タイルの変換係数をエンコードするときには、サブ帯域の各グループからの係数が、サブ帯域の他のグループの係数とは別々にエンコードされる。好ましい実施形態では、サブ帯域の各グループにおける係数を表わすために一対のビット流が発生される。ビット流の１つは、サブ帯域のグループにおける係数の最上位ビット平面を表わし、一方、第２のビット流は、サブ帯域のグループに対する係数の残りの最下位ビット平面を表わす。
【００２８】
ウェーブレット状変換の適用により発生されたウェーブレット係数は、変換されたタイルの各サブ帯域における係数を各量子化値（量子化除数とも称される）で除算することにより量子化される（量子化装置１７８により）のが好ましい。
好ましい実施形態では、各サブ帯域に個別の量子化除数が指定される。より詳細には、以下に詳細に述べるように、ブロック分類装置１７６は、像の各タイルにおける特徴の密度を表わす１つ以上の値を発生し、そしてこれら１つ以上の値に基づいて、タイルの種々のサブ帯域における係数を量子化するための量子化除数のテーブルが選択される。
【００２９】
量子化装置１７８により発生される量子化された係数は、希薄データエンコーダ１７９によりエンコードされて、像の各タイルに対しエンコードされたサブ像サブファイル２１０のセットが発生される。好ましい実施形態に使用されるウェーブレット状変換を以下に詳細に説明する。好ましい実施形態のウェーブレット状変換を実行するために回路は、背景情報の参考としてここに取り上げる「System and Method for Performing Wavelet and Inverse Wavelet Like Transformations of Digital Data Using Only Add and Bit Shift Arithmetic Operations」と題する米国特許第５，９０９，５１８号に開示されたウェーブレット変換及びデータ量子化方法に非常に類似している。
【００３０】
好ましい実施形態の希薄データエンコード方法は、「ネスト状直角分割（ＮＱＳ）」と称され、以下に詳細に述べる。この希薄データエンコード方法は、背景情報の参考としてここに取り上げる「System and Method for Scalable Coding of Sparse Data Sets」と題する米国特許第５，９４９、９１１号に開示されたＮＱＳ希薄データエンコード方法の改良形態である。
【００３１】
図３Ｂは、空間周波数サブ帯域を、変換係数をエンコードするのに使用されるＮＱＳサブ帯域へマッピングするところを示す。より詳細には、１つの好ましい実施形態において、７つの空間周波数サブ帯域（ＬＬ5、ＨＬ5、ＬＨ5、ＨＨ5、ＨＬ4、ＬＨ4、ＨＨ4）が、これらサブ帯域における係数をエンコードするために単一のＮＱＳサブ帯域（サブ帯域０）へとマップされる。換言すれば、これら７つの空間周波数サブ帯域における係数は、ＮＱＳエンコード化のために単一のトップレベルブロックとして処理される。１つの好ましい実施形態では、ＮＱＳサブ帯域０、１、２及び３が、４つのトップレベルＮＱＳブロックとしてエンコードされ、その最上位ビット平面は、当該像の最低解像度レベルを表わすビット流において記憶される。
【００３２】
像の解像度レベル及びサブ像
図４を参照すれば、像は、多数の解像度レベル０ないしＮで記憶され、典型的に、各解像度レベルは、その隣接レベルから４の解像度ファクタだけ異なる。換言すれば、像の最高解像度表示（解像度レベルＮ）が情報量Ｘを含む場合には、２番目に高い解像度レベル表示Ｎ−１は、情報量Ｘ／４を含み、３番目に高い解像度レベル表示は、情報量Ｘ／１６を含み、等々となる。像ファイルに記憶される解像度レベルの数は、像の最高解像度表示のサイズと、最低解像度レベルにおいてサムネイル像として受け入れられる最小解像度とに基づく。例えば、全即ち最高解像度の像が約１千６百万ピクセル（例えば、４０９６ｘ４０９６ピクセル像）を有する高鮮明度画像である場合には、７つの解像度レベル：４０９６ｘ４０９６、２０４８ｘ２０４８、１０２４ｘ１０２４、５１２ｘ５１２、２５６ｘ２５６、１２８ｘ１２８及び６４ｘ６４を有するのが適当である。
【００３３】
しかしながら、図４に示すように、本発明の１つの特徴は、多解像度の像が例えば３又は４以上の解像度レベルを有するときには、像が多数の「ベース像」ファイルにおいてエンコード及び記憶され、その各々は、２ないし４の解像度レベルに対するデータを含む。或いは又、全てのベース像が単一のファイルに記憶されてもよく、この場合、各ベース像は、像ファイル内の個別のベース像サブファイル又はサブファイルデータ構造体に記憶される。
【００３４】
各ベース像ファイル（又はサブファイル）は、「ベース像」及び１ないし３個のサブ像（低い解像度レベル）を再構成するためのデータを含む。例えば、図４に示す例では、像が３つのファイルに記憶され、第１ファイルは、最高に鮮明なレベル及びそれより低い２つのレベルを含む３つの解像度レベルにおいて像を記憶し、第２ファイルは、３つの更なる解像度レベル（第４、第５及び第６番目に高い解像度レベル）において像を記憶し、そして第３ファイルは、２つの最低解像度レベルで像を記憶し、全部で８つの解像度レベルとなる。一般に、各次々のファイルは、次に大きなファイルより約２2Xのファクタだけ小さい。但し、Ｘは、大きなファイルにおける解像度レベルの数である。例えば、第１ファイルが３つの解像度レベルを有する場合には、次のファイルは、典型的に、６４（２6）のファクタだけ小さい。
【００３５】
その結果、低い解像度レベルのグループを表わす像ファイルは、相当に小さくなり、従って、全解像度の像データを含む像ファイルよりも著しく速くクライアントコンピュータへ送信される。例えば、クライアントコンピュータのユーザは、最初に、最低の解像度レベル（例えば、３２ｘ３２又は６４ｘ６４）においてサムネイル像のセットをレビューし、クライアントコンピュータは、３つの像ファイルの最も小さいものだけをレビューすればよく、これは、典型的に、最高解像度の像ファイルの約０．０２４％程度のデータしか含まない。ユーザが、より高い解像度で像を見ることを要求するときには、クライアントコンピュータは、最低解像度の像ファイルの約６４倍程度のデータを含む第２の、若干大きな像ファイルを受け取る。この第２のファイルは、ユーザのニーズに充分である３つの解像度レベル（例えば、５１２ｘ５１２、２５６ｘ２５６及び１２８ｘ１２８）を含む。ユーザが更に高い解像度レベルを必要とする場合には、最高解像度ファイルが送信される。システムが使用される環境に基づき、像の売主は、各次々の高い解像度の像ファイルをダウンロードするために付加的な料金を課することができる。
【００３６】
多数の像ファイルは、方形ではなく、長方形であり、そして上記例で使用された方形の像サイズは、本発明の範囲を何ら限定するものではないことに注意されたい。像処理モジュールにより処理される情報の基本的単位は、典型的に６４ｘ６４又は３２ｘ３２のピクセルアレーであるタイルであるが、特定の像は、このようなタイルの任意のサイズのアレーを含んでもよい。更に、像は、タイルサイズの偶数倍でなくてもよい。というのは、エッジタイルは、適宜裁断できるからである。
【００３７】
像の特定の解像度レベルを「サムネイル」像と呼称することは、像が送信されるクライアント装置に依存する。例えば、非常に小さなディスプレイを有するパーソナルデジタルアシスタント又は移動電話へ送信されるサムネイル像は、パーソナルコンピュータへ送信されるサムネイル像より相当に小さく（例えば、そのサイズの１／１６）、そして大型の高鮮明度スクリーンを有する装置へ送信されるサムネイル像は、通常サイズ及び鮮明度を有するパーソナルコンピュータへ送信されるサムネイル像より相当に大きい。像が種々のクライアント装置で潜在的に使用されるときには、各形式の装置が適当なサイズのサムネイル像を最初に受信できるように、像に対して付加的な基本像が発生される。
【００３８】
像がクライアント装置により最初に要求されるときは、クライアント装置が、サムネイル像に対するその要求においてそのウインドウサイズを特定してもよいし、又はサーバーが、サムネイル像データをクライアント装置にダウンロードする前にクライアント装置に問合せすることによりクライアント装置のビューウインドウのサイズを決定してもよい。その結果、各クライアント装置は、その装置に対して適当なサイズにされた最小解像度のサムネイル像を受け取る。
【００３９】
像ファイルデータ構造体
図５Ａないし５Ｅを参照すれば、像の全てのタイルが変換され、圧縮されそしてエンコードされると、それにより得られるエンコードされた像データが像ファイル１９０として記憶される。この像ファイル１９０は、ヘッダデータ１９４と、ベース像サブファイル１９６とも称される一連のベース像データ構造体とを含む。各ベース像サブファイル１９６は、典型的に、２つ以上の解像度レベルで像を表示するためのデータを含む。更に、各ベース像は、個別範囲の解像度レベルをサポートする。多数のベース像及びそれらの各サブ像は、図４に概念的に示されたように、像に対して全範囲の解像度レベルを与える。ベース像レベルによりサポートされる解像度レベルは、好ましい実施形態では、非重畳であるが、別の実施形態では、１つのベース像によりサポートされる解像度レベルが、別のベース像によりサポートされる解像度レベルと重畳する（同じ初期の全解像度の像に対して）。
【００４０】
好ましい実施形態では、各像ファイル１９０は、ファイルがクライアントコンピュータにダウンロードされるときに自動的に呼び出されるアプレット１９９（例えば、Ｊａｖａ（登録商標）アプレット）へのオブジェクトタグ又はアプレットタグのようなリンク１９８を含むｈｔｍｌファイル又は同様にフォーマットされたウェブページである。ヘッダ１９４と、ベース像１９６の選択された１つとは、埋設されたアプレット１９９へのデータ入力として使用され、このアプレットは、像をデコードして、ユーザのパーソナルデジタルアシスタント又はコンピュータのディスプレイにレンダリングする。アプレットの動作は、ユーザにとって透過的であり、ユーザは、自分のコンピュータディスプレイにレンダリングされた像を単に見る。或いは、アプレットは、像ファイルに含まれたベース像サブファイル（１つ又は複数）、サーバーから得られる付加的なベース像サブファイルで得られる解像度レベル、及び像切断オプションのような他のオプションを含むオプションのメニューをユーザに提示してもよい。
【００４１】
別の実施形態では、クライアントワークステーションは、本発明のファイルフォーマットで像をデコードしそしてレンダリングするためのブラウザプラグインアプリケーションのようなアプリケーションを含む。更に、各像ファイル２１０は、プラグインアプリケーションに対応する関連データ形式を有する。像ファイル２１０は、その像ファイルを指す埋設タグ又はオブジェクトタグを含むｈｔｍｌ又は同様にフォーマットされたウェブページと共にダウンロードされる。その結果、ウェブページがクライアントワークステーションにダウンロードされるときに、プラグインアプリケーションが自動的に呼び出されそしてクライアントコンピュータにより実行される。したがって、像ファイルがデコードされてレンダリングされ、そしてプラグインアプリケーションのオペレーションは、ユーザに透過的となる。
【００４２】
図５Ａに示す像ファイル１９０−Ａは、多解像度の像を記憶する１つの考えられる方法を示し、多解像度の像をサーバーに記憶するのに特に適している。クライアントコンピュータでは、図５Ｂに示す像ファイル１９０−Ｂは、１つのベース像１９６しか含まない。更に、クライアントバージョンの像ファイル１９０は、サーバーの像ファイル１９０−Ａへのリンク２０１を含む。リンク２０１は、クライアントコンピュータのユーザが同じ像の他のベース像（他の解像度レベルにある）をダウンロードできるようにするために使用される。或いは又、リンク２１０は、ウェブサーバーから高い解像度のベース像のいずれかを含む像ファイルを要求するためのＪａｖａ（登録商標）スクリプトであってもよい。高い解像度の像ファイルを得るために料金がかかる場合は、このスクリプトは、要求を発しているユーザから支払を得るためにサーバー手順の実行を求める。
【００４３】
更に別の実施形態では、多解像度の像は、図５Ｂに示すフォーマットを各々有する個別のベース像ファイル１９０−Ｂのセットとしてサーバーに記憶される。
これは、変更なしにクライアントコンピュータへダウンロードする準備のできた像ファイル１９０−Ｂを与えるという効果を有する。
図５Ａを再び参照すれば、像ファイルのヘッダ１９４は、種々のベース像サブファイル１９６にアクセスするのに必要な情報を含む。より詳細には、好ましい実施形態では、ヘッダ１９４は、次のものを記憶する。
−  サーバーにおける像ファイルの識別子又はＵＲＬ；
−  ファイルにおけるベース像サブファイル１９６の数を指示するパラメータ値（又は各ベース像が個別ファイルに記憶される実施形態ではベース像ファイルの数）；
−  各ベース像データ構造体のサイズ；及び
−  各ベース像データ構造体に対するオフセットポインタ（又は各ベース像が個別ファイルに記憶される実施形態では各ベース像ファイルに対するポインタ）。
【００４４】
各ベース像サブファイル１９６は、ヘッダ２０４及び一連のビット流２０６を有する。ビット流は、１ａ、１ｂないしＮと示され、但し、Ｎは、当該ベース像によりサポートされた解像度レベルの数である。表示「１ａ」等の意味は、以下に述べる。各ビット流２０６における情報は、以下に詳細に述べる。各ベース像サブファイルのヘッダデータ２０４は、次のものを指示するフィールドを含む。
−  ベース像サブファイルのサイズ（即ち、ベース像サブファイルにより占有された記憶部の量）；
−  ベース像をタイル化するのに使用されるタイルのサイズ（例えば、ピクセルの行列の数）。但し、各タイルは、以下に述べるように、別々に変換されそしてエンコードされる；
−  このベース像サブファイルに対して記憶されるカラーチャンネル成分；
−  ベース像をデコンポーズするのに使用される変換フィルタ（例えば、異なる像には変換フィルタの異なるセットが使用される）；
−  ベース像に対して（即ちベース像の各タイルに対して）エンコードされる空間周波数サブ帯域の数；
−  ベース像によってサポートされる解像度レベル（サブ像とも称される）の数；
−  ベース像に対して（即ちベース像の各タイルに対して）エンコードされるビット流の数；及び
−  各ビット流に対する情報。
【００４５】
ベース像サブファイルにおける各ビット流に対するヘッダ情報は、次のものを含む。
−  像ファイル内（又はベース像サブファイル内）の位置を指示するためのビット流に対するオフセットポインタ；
−  ビット流のサイズ（ビット流にどれほどのデータがあるか）；
−  ビット流に含まれた空間周波数サブ帯域の範囲；
−  ビット流におけるカラーチャンネルの数；
−  ビット流に含まれたビット平面の範囲であって、サブ帯域における係数のビット平面が、意義のある部分と、意義のない部分と、中程度に意義のある部分との間でいかに分割されるかを示すもの；及び
−  ビット流内のタイル２０８に対するオフセットポインタのテーブル。
【００４６】
各ビット流２０６は、一連のタイルサブアレー２０８を含み、その各々は、像の各タイルに対してｉ番目のビット流を含む。ビット流２０６は、ベース像ヘッダ２０４によりベース像に対して特定されたパラメータをオーバーライドするのに使用されるフィールドを有するヘッダ２０９を任意に含む。像ファイルが切断された像を含むときには、その像ファイルに含まれるサブアレー２０８のセットが、切断された像を表わすのに必要なものに制限される。
【００４７】
好ましい実施形態では、像ファイルヘッダ１９４は、「切断された像の境界」を指示するパラメータも含む。これは、像の切断部分に対するデータのみを含む像の部分コピーに対して有用であり、これは、次いで、クライアントコンピュータを使用して像に対してパン及びズーム動作を実行するときに非常に有用である。例えば、ユーザは、像全体の非常に小さな部分だけを非常に高い解像度で要求することができる。この場合に、像の切断部分を表示するのに必要な像のタイルのみが、ユーザのクライアントコンピュータへ送信される像ファイルのバージョンに含まれ、そして切断像境界パラメータを使用して、この情報が、クライアントコンピュータにおいて像をレンダリングする手順へ搬送される。２つの形式の像切断情報、即ち全像ファイルに適用される切断、及び特定のサブ像に適用される更に別の切断が、像ファイルヘッダ１９４によって与えられる。例えば、クライアントコンピュータが最初に像を受信するときには、特定ベース像の最低解像度レベルのサブ像のみを受信し、このサブ像は、典型的に、切断されない（全像に比して）。クライアントが、特定の高い解像度レベルにおいて像の一部分にズームインするときには、クライアントコンピュータで見られるべき像の一部分を発生するのに必要なデータのタイルのみがクライアントコンピュータへ送信され、従って、クライアントの像ズームコマンドに応答してクライアントコンピュータにダウンロードされるサブ像レベル（１つ又は複数）に対する切断境界を指示するために、クライアントコンピュータに記憶された（又はキャッシュ処理された）像ファイルのヘッダに新たな切断パラメータが追加される。
【００４８】
ベース像のビット流ごとにベース像ヘッダに含まれるタイルに対するオフセットポインタのテーブルも、ズーム及びパンの間に使用される。特に、図１５を参照すれば、像ファイルが最初にクライアントコンピュータ又は装置によりダウンロードされるときには（２４０）、高レベルのビット流が非集団化され(unpopulated)、従って、オフセットポインタのテーブルは、最初、ナル値を含む。クライアント装置のユーザが像にズームインするときには、高レベルビット流の種々のタイルに対するデータが、必要に応じてクライアント装置へとダウンロードされ（２４２）、そしてタイルに対するオフセットポインタのテーブルは、クライアントコンピュータにデータがダウンロードされたところのタイルを反映するように更新される。クライアントが、更に、そのズームされた又は高い解像度レベルで像を横切ってパンするときには、情報の付加的なファイルが必要に応じてクライアントコンピュータへ送信され、そしてこの場合も、像ファイルヘッダ１９４における切断情報と、ベース像ヘッダにおけるタイルオフセット情報が、各ビット流に対して記憶されたデータのタイルを反映するように更新される（２４４）。
【００４９】
再び図５Ａ−５Ｅを参照すれば、像ファイル及びベース像サブファイルのヘッダにおける情報は、ファイルのいかなる部分も素早くインデックスすることができ、これは、コンピュータ又は他の装置が、いかなる解像度レベルにおいても、像ファイル１９０の他の部分の内容をデコードする必要なく、像のいかなる部分の開始又は終了も探索できるようにする。これは、例えば、像ファイル１９０を裁断して、ファイルの低像クオリティバージョン又はファイルの切断像バージョンを作成し、通信ネットワークを経て別のコンピュータ又は装置へ送信するとき等に有用である。
【００５０】
以下に述べる説明において、「サブ像」及び「差のサブ像」という語は、ビット流２０６に対して次のように使用される。一般に、ベース像のサブ像は、ビット流１ａから、特定の最後のビット流、例えば、ビット流３までの全てのビット流を含む。隣接ビット流のこのグループは、ここでサブ像と称する像を特定の解像度レベルで再構成するのに必要なデータを構成する。「差のサブ像」とは、あるサブ像レベルから次のサブ像レベルへ像の解像度を高めるのに必要な付加的なビット流より成る。例えば、ビット流１ｃ、２ｂ及び３は、ビット流１ａから２ａを経て発生されるサブ像の解像度を２倍にするのに必要なデータを含むので、一緒に差のサブ像と称される。
【００５１】
図５Ｃを参照すれば、ベース像を表わすエンコードされたデータ１９０−Ｃは、最初に、「タイル順」に記憶される。像ファイル１９０−Ｃは、ヘッダ２２２と、タイルサブファイル２２０のセットとを含む。図５Ｄを参照すれば、各タイルサブファイル２２０は、タイルをエンコードするのに使用される量子化テーブルと、サブファイル内のビット流に対するオフセットポインタと、他の情報とを示すヘッダ２２４を含む。又、各タイルに対するタイルサブファイル２２０は、ビット流サブアレー２２６のセットも含む。各ビット流サブアレー２２６は、タイルのＮＱＳサブ帯域（図３Ｂ参照）の各セットの最上位ビット平面、最下位ビット平面、又は中間のビット平面セットを表わすエンコードされたデータを含む。次のテーブルは、ビット流サブアレーへのビット平面マッピングの一例を示す。
【００５２】
ＮＱＳサブ帯域Ｎｏ．    ０−３        ４、５、６      ７、８、９
解像度                      
１６ｘ１６                Ｓ
３２ｘ３２                Ｓ＋ＭＳ          Ｓ
６４ｘ６４                Ｓ＋ＭＳ＋ＩＳ    Ｓ＋ＩＳ        全部
【００５３】
このテーブルにおいて、Ｓ、ＭＳ及びＩＳに対応するビット平面は、ＮＱＳサブ帯域ごとに異なる。これらビット平面の範囲は、ベース像サブファイルのヘッダにおいて特定される。例えば、ＮＱＳサブ帯域０ないし３の場合に、Ｓは、ビット平面１７ないし７に対応し、ＭＳは、ビット平面６ないし４に対応し、そしてＩＳは、ビット平面３ないし０に対応し、一方、ＮＱＳサブ帯域４ないし６の場合に、Ｓは、ビット平面１６ないし５に対応し、そしてＩＳは、ビット平面４ないし０に対応する。
【００５４】
ビット流１ａ、１ｂ及び１ｃは、ＮＱＳサブ帯域０、１、２及び３の最上位、中間及び最下位ビット平面を各々表わすエンコードされたデータを含む。ビット流２ａ及び２ｂは、ＮＱＳサブ帯域４、５及び６の最上位及び最下位ビット平面を各々表わすエンコードされたデータを含み、これらは、ＬＨ2、ＨＬ2及びＨＨ2サブ帯域に対応する。ビット流３は、ＮＱＳサブ帯域７、８及び９を表わすエンコードされたデータの全てのビット平面を含み、これらは、ＬＨ1、ＨＬ1及びＨＨ1サブ帯域に各々対応する。
タイルサブファイル２２０は、「一時的」なファイルであると考えられる。というのは、エンコードされたタイルデータが、図５Ｃ及び５Ｄのファイルフォーマットから図５Ａに示すファイルフォーマットへ後で再編成されるからである。
【００５５】
図５Ｅは、ベース像サブファイル１９６の特定例を１９６Ａで示す。このベース像サブファイルは、１２個のビット流２０６を含み、これらは、ベース像及び２つの低解像度のサブ像を発生するのに使用される。ベース像は、ウェーブレット変換の５つの層で変換されて、１６個の空間周波数サブ帯域のデータを発生し、これは、ベース像を含む３つのサブ像へとエンコードされ編成されている。サブ像の数は、ある程度任意である。というのは、５つの変換層により発生されるサブ帯域は、６個程度のサブ像を発生するように使用できるからである。しかしながら、このベース像サブファイルを使用して非常に小さなサブ像を発生することは、メモリ又は記憶装置の利用に関して効率的でなく、それ故、小さなベース像サブファイルを使用して、小さなサブ像を発生するのがしばしば好ましい。
【００５６】
図５Ｅにおいて、ベース像は、５つの変換層により処理されているが、それにより得られるデータは、６つではなく、３つのサブ像レベルのみに編成される。
効果的なことに、サブ帯域ＬＬ2を１０個のサブ帯域（ＬＬ5、ＬＨ5、ＨＬ5、ＨＨ5、ＬＨ4、ＨＬ4、ＨＨ4、ＬＨ3、ＨＬ3、ＨＨ3）へと変換する最後の３個の変換層は、余計なサブ像レベルを発生するように使用されない。むしろ、最後の３つの変換層は、良好なデータ圧縮を発生するだけに使用される。
【００５７】
図５Ｅに示すように、像データの５つの変換層が３つのサブ像にマップされたときに、ビット流データサブアレー２０６の、サブ像へのマッピングは、次のようになる。
−  最低レベルのサブ像であるサブ像０は、ＮＱＳサブ帯域０ないし３（図３Ｂ参照）の最上位ビット平面を含むビット流サブアレー２０６−１ａに対応し；  −  サブ像１は、ビット流２０６−１ａ、２０６−１ｂ及び２０５−２ａに対応し、そして
−  ベース像であるサブ像２は、ベース像サブファイルにおける全てのビット流２０６に対応する。
【００５８】
変換層が、図５Ｅに示す例よりも多数のサブ像（サブ像レベル）にマップされるときには、第１ビット流２０６−１ａは、少数の空間周波数サブ帯域しか含まない。
希薄データエンコード技術は、各タイルのサブ帯域のグループごとに変換係数をエンコードするように使用され、従って、ほとんどゼロ値を含むデータのアレーを表わすのに、ほんの僅かなデータしか必要としない。一般に、変換され量子化される像データの高周波数部分（即ちサブ帯域）は、非ゼロ値よりもゼロ値を多く含み、そして非ゼロ値の大部分は、比較的小さな絶対値を有する。それ故、多数のタイルの高レベルビット平面は、非常に僅かな非ゼロビット値で集団化される。
【００５９】
タイル型ウェーブレット変換方法
図６を参照すれば、像ファイルを発生するプロセスは、像捕獲装置により像が捕獲されたときに開始される（ステップ２５０）。像のサイズが可変である場合には、捕獲された像のサイズが決定され、そして像データをカバーするのに必要なタイルの行及び列の数が決定される（ステップ２５２）。像のサイズが常に同じである場合には、ステップ２５２は、不要である。
次いで、像における全てのタイルが所定の順序、例えば、ラスタ走査の順序で処理され、これは、ウェーブレット状のデコンポジション変換を水平及び垂直の両方向にそれらに適用し、それにより得られる変換係数を量子化し、そして最後に、その量子化された変換係数を、希薄データ圧縮及びエンコード手順を使用してエンコードすることにより行われる（ステップ２５４）。各タイルに対するエンコードされたデータは、例えば、図５Ｄに示すフォーマットで、一時的ファイル又はサブファイルに記憶される。
【００６０】
像における全てのタイルが処理された後に、全てのエンコードされたタイルを含む多解像度の像ファイルが不揮発性メモリに記憶される（ステップ２５６）。
より詳細には、一時的ファイルからのエンコードされたタイルデータは、図５Ａに示すファイルフォーマットにおいて、解像度逆転順序で出力ビット流ファイルへと書き込まれる。「解像度逆転順序」とは、像データが、最初に、最低解像度のビット流でファイルに記憶され、その後、次に低い解像度のビット流で記憶され、等々とされることを意味する。
ステップ２５４で使用されるウェーブレット状デコンポジション変換は、図７Ａ、７Ｂ及び７Ｃを参照して以下に詳細に説明する。量子化及び希薄データエンコード段階も、以下に詳細に説明する。
【００６１】
初期像が、典型的に２ないし４つの解像度レベルを含む多解像度の像ファイルとして処理され、エンコードされそして記憶された後に、２つ以上のベース像を像ファイルに含ませるべき場合には（２５７）、以前に発生された多解像度の像ファイルにおけるサブ像レベルの数をＸとすれば、各次元において２Xのファクタだけ小さい新たなベース像を発生するためにオリジナル像がダウンサンプリングされそしてアンチエイリアシングされる（２５８）。従って、新たなベース像は、ベース像の最小の最低解像度のサブ像よりも４のファクタだけ小さくなる。
この新たなベース像は、次いで、以前のベース像と同様に処理されて、像ファイルに追加される付加的な、相当に小さい、エンコードされた多解像度のベース像を発生する。オリジナルのベース像が充分に高い解像度を有していた場合には、第３のベース像は、第２ラウンドのダウンサンプリング及びアンチエイリアシングを実行することにより形成され、そして第３のエンコードされた多解像度のベース像ファイルが像ファイルに記憶される。最後にエンコードされたベース像は、他のものより少数のサブ像レベルを含み、そしてある実施形態では、単一解像度レベルのみを含み、この場合、その像ファイルは、サムネイル像ファイルであるのが効果的である。
【００６２】
別の実施形態では、各エンコードされたベース像は、個別の像ファイルに記憶され、そしてこれら像ファイルは、像ファイルのヘッダに記憶された情報により又はｈｔｍｌ（又はｈｔｍｌ状）リンクにより互いに連結される。
好ましい実施形態では、ダウンサンプリングフィルタは、一次元のＦＩＲフィルタであって、最初に像の行に、次いで、列に適用されるか、又はその逆に適用される。例えば、像が各次元において４のファクタでダウンサンプリングされるべき場合には（解像度が１６のファクタで減少）、ＦＩＲフィルタは、次のフィルタ係数を有する。
フィルタＡ＝（−３  −３  −４  −４  １０  １０  ２９  ２９  ２９
２９  １０  １０  −４  −４  −３  −３）１／１２８
【００６３】
この例示的フィルタは、一度に１４サンプルのセットに適用されて１つのダウンサンプリングされた値を発生し、次いで、４サンプルだけシフトされ、そして再び適用される。これは、初期サンプル（即ちピクセル値）の数をＬとすれば、Ｌ／４のダウンサンプリングされた値が発生されるまで繰り返される。像データアレーのエッジでは、反射されたデータが、像データのエッジを越えて延びるフィルタ係数として使用される。例えば、アレーの左（又は上）エッジでは、第１の６つの係数が、反射されたデータ値に適用され、４つの「２９／１２８」係数が、フィルタされている行（又は列）の最初の４つのピクセル値に適用され、そして最後の６つの係数が、行（又は列）の次の６つのピクセルに適用される。
【００６４】
像が８のファクタでダウンサンプリングされるべき場合には、上記フィルタが４のファクタによるダウンサンプルに適用され、次いで、第２のフィルタが適用されて、像データが別の２のファクタで更にダウンサンプリングされる。この第２のフィルタは、好ましい実施形態では、次のフィルタ係数を有するＦＩＲフィルタである。
フィルタＢ＝（−３  −４  １０  ２９  ２９  １０  −４  −３）１／６４  或いは又、より長いフィルタを使用して、１つのフィルタ通過で８のファクタによるダウンサンプリングを達成することもできる。
【００６５】
上述したダウンサンプリングフィルタは、次の特性を有する。即ち、それらは、ナイキスト周波数の１／４及び１／２に各々カットオフ周波数を有するローパスフィルタであり、各フィルタ係数は、分子が整数でありそして分母が２の正の整数累乗である（正の整数をＮとすれば、２Nの形態の数）簡単な分数で定義される。これらフィルタ特性の結果として、ダウンサンプリングは、像の空間周波数特性を保存しそしてエイリアシング作用を回避しながら、非常に効率的に実行することができる。
ダウンサンプリングフィルタが像データのアレーに適用される順序（即ち、行そして列、又はその逆）は、発生される特定のダウンサンプルされたピクセル値に影響するが、ピクセル値に対する影響は、著しいものではない。本発明の別の実施形態では、他のダウンサンプリングフィルタを使用することもできる。
【００６６】
エッジ、内部及び中心変換フィルタを使用するウェーブレット状の
デコンポジション
図７Ａ−７Ｃは、像データＸ0ないしＸ2n-1のセットにおいてウェーブレット状デコンポジションを実行して、係数Ｌ0ないしＬn-1及びＨ0ないしＨn-1のセットを発生するプロセスを概略的に示す。但し、Ｌ係数は、像データの低空間周波数成分を表わし、そしてＨ係数は、像データの高空間周波数成分を表わす。好ましい実施形態では、適用されるウェーブレット状変換は、実際に、２つのフィルタである。エッジフィルタと称される第１のフィルタＴ１は、発生される変換係数の行又は列において最初の２つ及び最後の２つの係数を発生するのに使用され、そして内部フィルタと称される第２のフィルタＴ２は、発生される変換係数の行又は列において他の全ての係数を発生するのに使用される。エッジフィルタＴ１は、タイル又はブロックのエッジにおけるデータを変換するのに使用される短いフィルタであり、一方、内部フィルタＴ２は、タイル又はブロックのエッジから離れたデータを変換するのに使用される長いフィルタである。エッジフィルタも内部フィルタも、タイル又はブロック以外からのデータは使用しない。その結果、本発明のウェーブレット状変換を像データのアレーに適用するのに必要な作用メモリは、公知システムに比して減少される。同様に、本発明のウェーブレット状変換を実施するための回路及び／又はソフトウェアの複雑さも、公知システムに比して減少される。
【００６７】
好ましい実施形態では、エッジフィルタは、第１及び最後の係数を発生するための第１の非常に短いフィルタ（その「サポート」は、２ないし４つのデータ値をカバーする）と、第２及び最後から２番目の係数を発生するための第２のフィルタとを含む。第２のエッジフィルタは、３ないし６個のデータ値にわたって延びるフィルタサポートを有し、従って、第１のエッジフィルタより若干長いが、内部フィルタＴ２より短い。他の係数を発生するための内部フィルタは、典型的に、７つ以上のデータ値というフィルタサポートを有する。エッジフィルタ、特に、第１及び最後の高空間周波数の係数値を発生するための第１エッジフィルタは、データ圧縮度の低下を犠牲として、隣接タイル又はブロックからのデータを使用せずにエッジ欠陥を最小にするように設計される。換言すれば、本発明のエッジフィルタは、処理されているデータアレーのエッジ値の正確な再生を確保するように設計され、これは、ひいては、データアレーにより表わされた像が再生されるときにエッジ欠陥を最小にする。
【００６８】
好ましい実施形態では、データアレーに適用されるウェーブレット状デコンポジション変換は、変換の層２ないしＮを実行するときに使用されるウェーブレット状変換とは異なる層１のウェーブレット状変換を含む。特に、この層１のウェーブレット状変換は、層２ないしＮに使用されるフィルタよりも短いフィルタサポートを有する短いフィルタを使用する。層１に対して異なるウェーブレット状変換（即ち変換フィルタのセット）を使用する理由の１つは、層１に対して短いフィルタを使用することにより境界欠陥を最小にすることであり、これは、境界欠陥を最小にする傾向となる。層１に対して他の層とは異なるウェーブレット状変換（即ち変換フィルタのセット）を使用する別の理由は、多数のスケーリングされた値を追加することにより導入される丸めエラーを最小にすることである。
層１変換中に生の像データをフィルタリングするときに主として発生する丸めエラーは、エンコードされた像データから再生される像のクオリティを著しく低下させることがある。
【００６９】
好ましい実施形態に使用されるウェーブレット状デコンポジション変換に対する方程式を以下に示す。
層１順方向ウェーブレット状変換
Ｔ１及びＴ２順方向変換（低周波数）：
【数１】
0004707681.tif 000002
Ｔ１順方向変換（エッジフィルタ−高周波数）：
【数２】
0004707681.tif 000003
【００７０】
Ｔ２順方向変換（内部フィルタ−高周波数）：
【数３】
0004707681.tif 000004
層１逆ウェーブレット状変換
Ｔ１逆変換（エッジフィルタ−高周波数）：
【数４】
0004707681.tif 000005
【００７１】
Ｔ２逆変換（内部フィルタ）：
【数５】
0004707681.tif 000006
順方向ウェーブレット状変換：層２ないしＮ
変換レベル２ないしＮ（即ち、レベル１以外の全部）に対する順方向ウェーブレット状デコンポジション変換の好ましい実施形態に対する方程式を次に示す。
「２ｎ」は、変換により処理されているデータの巾をデータサンプル数で測定して示すものであり、「ｎ」は、正の整数であると仮定する。エッジフィルタＴ１は、Ｈ0、Ｈn-1、Ｌ0及びＬn-1に対する方程式により表わされ、そして内部フィルタＴ２より短いフィルタサポートを有する。
【００７２】
別の実施形態では、同じウェーブレット状デコンポジション変換が全ての層に使用される。例えば、層２ないしＮについてここに示すウェーブレット状デコンポジション変換フィルタは、層１デコンポジションについても（即ち生の像データをフィルタリングするのにも）使用される。
【数６】
0004707681.tif 000007
【００７３】
【数７】
0004707681.tif 000008
上述したデコンポジション変換方程式の一般的な形態は、ｎが少なくとも１０であるときしか適用されない。ｎが１０より小さいときには、エッジ項と中間項との間の項に対する幾つかの方程式が落とされる。というのは、発生されるべき係数の数が、これら方程式の使用を必要とするには少な過ぎるからである。例えば、ｎ＝８のときには、Ｌkを発生するための２つの方程式がスキップされる。
【００７４】
変換フィルタの属性の説明
Ｌ0及びＬn-1を発生するためのエッジ変換フィルタＴ１は、入力データアレーのエッジにおいて３つの入力サンプルのみのフィルタサポートを有し、そしてこれら係数の値の７０％が、フィルタされているデータのアレーの真の境界におけるエッジ値Ｘ0又はＸ2n-1に起因するように重み付けされる。エッジ入力データム（即ちアレー境界に最も接近したサンプル）を大きく重み付けすると、タイルに対する変換係数を発生するときにエッジ及び内部フィルタがタイル内のデータにしか適用されないにも関わらず、実質的にタイル境界欠陥を伴わずに変換係数から像を再構成することができる。Ｌ0及びＬn-1を発生するための層１のエッジ変換フィルタＴ１は、これら係数の値の５０％が、フィルタされているデータのアレーの真の境界におけるエッジ値Ｘ2n-1に起因するように重み付けされる。
【００７５】
好ましい実施形態における内部変換フィルタは、フィルタされているデータアレーの内部にわたって均一に適用されるのではない。更に、内部フィルタは、フィルタされているデータアレーの中心又はその付近において４つのハイパス及び４つのローパス係数を発生するための中心フィルタを含む。好ましい実施形態では、中心フィルタは、２つ程度のハイパス及び２つ程度のローパス係数を発生する。中心フィルタは、内部フィルタの左部分と右部分（又は上部と下部）との間を遷移するのに使用される。内部フィルタの２つの形態間の遷移は、ここでは、「フィルタスイッチング」と称される。中心フィルタを除く内部フィルタの半分は、偶数番号のデータ又は係数位置を中心とし、一方、内部フィルタの他の半分は、奇数データ位置のデータを中心とする。（アレーの偶数及び奇数データ位置は、もちろん、交互のデータ位置である。）上記の方程式は、中心フィルタをアレーの中央に配置するものであるが、エッジフィルタと内部フィルタとの間に滑らかな遷移がある限り、中心フィルタは、データアレーの内部のどこに配置されてもよい。当然、逆中心フィルタをある位置に順方向変換フィルタとしてもたせるように逆変換フィルタも定義しなければならない。
【００７６】
層２ないしＮに対する小さなデータアレーのための変換方程式
ｎが４に等しいとき、実行されるべき変換は、次のように表わすことができ、  （Ｘ0、Ｘ1、Ｘ2、Ｘ3、Ｘ4、Ｘ5、Ｘ6、Ｘ7）→
（Ｌ0、Ｌ1、Ｌ2、Ｌ3；Ｈ0、Ｈ1、Ｈ2、Ｈ3）
そして変換方程式の上記一般的セットは、次のように減少される。
【数８】
0004707681.tif 000009
【００７７】
ｎが２に等しいとき、実行されるべき変換は、次のように表わすことができ、  （Ｘ0、Ｘ1、Ｘ2、Ｘ3）→（Ｌ0、Ｌ1；Ｈ0、Ｈ1）
そして変換方程式の上記一般的セットは、次のように減少される。
【数９】
0004707681.tif 000010
【００７８】
逆ウェーブレット状変換：層２ないしＮ
好ましい実施形態に使用される変換層２ないしＮ（即ち層１を除く全部）に対する逆ウェーブレット状変換を次に示す。変換方程式の一般的形態は、ｎが少なくとも１０であるときだけ適用される。ｎが１０より小さいときには、エッジ項と中間項との間の項に対する幾つかの方程式が落とされる。というのは、発生されるべき係数の数が、これら方程式の使用を必要とするには少な過ぎるからである。
【数１０】
0004707681.tif 000011
【数１１】
0004707681.tif 000012
【数１２】
0004707681.tif 000013
【００７９】
ｎが８に等しいときには、逆変換方程式の上記一般的セットは、次のように減少される。
【数１３】
0004707681.tif 000014
【数１４】
0004707681.tif 000015
【００８０】
ｎが４に等しいときに、実行されるべき逆変換は、次のように表わすことができ、
（Ｌ0、Ｌ1、Ｌ2、Ｌ3；Ｈ0、Ｈ1、Ｈ2、Ｈ3）→
（Ｘ0、Ｘ1、Ｘ2、Ｘ3、Ｘ4、Ｘ5、Ｘ6、Ｘ7）
そして逆変換方程式の上記一般的セットは、次のように減少される。
【数１５】
0004707681.tif 000016
【００８１】
ｎが２に等しいときに、実行されるべき逆変換は、次のように表わすことができ、
（Ｌ0、Ｌ1；Ｈ0、Ｈ1）→（Ｘ0、Ｘ1、Ｘ2、Ｘ3、Ｘ4）
そして逆変換方程式の上記一般的セットは、次のように減少される。
【数１６】
0004707681.tif 000017
【００８２】
好ましい実施形態では、逆変換プロセスの各層の間に、偶数位置（即ちＸ2i値）における係数を計算してから、奇数位置（即ちＸ2i+1値）における係数を計算しなければならない。
別の実施形態では、短いＴ１デコンポジション変換を使用して、エッジにおけるデータだけではなく全てのデータがフィルタされる。短いＴ１デコンポジション変換だけを使用すると、計算時間及び複雑さが減少されるが、達成されるデータ圧縮度が低下し、ひいては、像ファイルが大きなものとなる。又、短い変換だけを使用すると、本発明を使用してエンコードされた像を含む像ファイルをデコードするための計算時間も減少される。というのは、像の再構成中にそれに対応する短いＴ１再構成変換しか使用されないからである。
【００８３】
適応ブロック的量子化
図３を参照すれば、ウェーブレット状でコンポジション変換により発生される各ウェーブレット係数は、次のように量子化され、
【数１７】
0004707681.tif 000018
但し、ｑは量子化除数であり、そして次のように量子化解除される。
【数１８】
0004707681.tif 000019
【００８４】
本発明によれば、量子化テーブルを使用して、ウェーブレット係数の各サブ帯域に量子化除数が指定され、従って、圧縮クオリティが制御される。ルミナンス値に対してウェーブレット変換の５つの層（及びクロミナンス値に対して４つの層）が実行される場合には、ルミナンス値に対するデコンポジションに１６個のサブ帯域が存在し、
ＬＬ5、ＨＬ5、ＬＨ5、ＨＨ5、ＨＬ4、ＬＨ4、ＨＨ4、ＨＬ3、ＬＨ3、
ＨＨ3、ＨＬ2、ＬＨ2、ＨＨ2、ＨＬ1、ＬＨ1、ＨＨ1
そしてクロミナンス値に対して１３個のサブ帯域が存在する。
ＬＬ4、ＨＬ4、ＬＨ4、ＨＨ4、ＨＬ3、ＬＨ3、ＨＨ3、ＨＬ2、ＬＨ2、
ＨＨ2、ＨＬ1、ＬＨ1、ＨＨ1
【００８５】
ルミナンス値に対する１つの考えられる量子化テーブルは、次の通りであり、  ｑ＝（１６、１６、１６、１８、１８、１８、２４、２４、２４、３６、
４６、４６、９３、３００、３００、６００）
そしてクロミナンス値については、次の通りである。
ｑ＝（３２、５０、５０、１００、１００、１００、１８０、２００、
２００、４００、７２０、７２０、１４４０）
しかしながら、好ましい実施形態では、量子化ファクタｑは、像の各個々のタイルに対し、タイルにおける像特徴の密度に基づき適応式に選択される。図８を参照すれば、サブ帯域ＬＨk、ＨＬk及びＨＨkのエントリーをｕij(k)、ｖij(k)及びｗij(k)で各々表わす。
【００８６】
図９を参照すれば、ブロック分類モジュールは、タイルの各変換層（例えば、ｋ＝１、２、３、４、５）に対してブロック分類値のセットを次のように計算する。
【数１９】
0004707681.tif 000020
【００８７】
オリジナル像における垂直及び水平の線は、主としてｕij(k)及びｖij(k)により各々表わされる。Ｂkは、オリジナル像（即ちブロック分類装置により評価されているタイルにおける）が多数の特徴（例えば、エッジ及びテクスチャ）を含む場合には大きくなる傾向がある。それ故、Ｂkの値が大きいほど、圧縮欠陥を生じることなく像を圧縮することが困難になる。
２クラスモデルを使用すると、２つの量子化テーブルが設けられる。
Ｑ0＝（１６、１６、１６、１８、１８、１８、３６、３６、３６、７２、
７２、７２、１４４、３００、３００、６００）
Ｑ1＝（１６、３２、３２、３６、３６、３６、７２、７２、７２、１４４、１４４、１４４、２８８、６００、６００、１２００）
但し、Ｑ0は、ブロックの圧縮が「困難」なものとして使用され、そしてＱ1は、ブロックの圧縮が「容易」なものとして使用される。
【００８８】
内部タイル（即ち像の境界にないタイル）は、各々、１つ以上のＢk値を１つ以上の各スレッシュホールド値と比較することに基づき圧縮が「困難」又は「容易」として分類される。例えば、図９に示すように、タイルに対するＢ1が第１スレッシュホールドＴＨ１（例えば６５）と比較される（ステップ２７１）。このＢ1がスレッシュホールドより大きい場合には、タイルが「困難」と分類される（ステップ２７２）。さもなければ、Ｂ5が第２スレッシュホールドＴＨ２（例えば６０）と比較される（ステップ２７３）。このＢ5が第２スレッシュホールドより大きい場合には、タイルが「困難」と分類され（ステップ２７４）、さもなければ、「容易」と分類される（ステップ２７５）。次いで、タイルに対するウェーブレット係数が、ブロック（即ちタイル）分類に対応する量子化テーブルによって特定された量子化除数を使用して量子化される。
【００８９】
好ましい実施形態では、境界タイルは、Ｂ1を、別の高いスレッシュホールド値ＴＨ１Ｂ、例えば、８５と比較することにより分類される。Ｂ1値がこのスレッシュホールドより高い境界タイルは、圧縮が「困難」と分類され、さもなければ、圧縮が「容易」と分類される。
別の実施形態では、３つ以上のブロック分類が指定され、そしてそれに対応するスレッシュホールド値のセットが定義される。Ｂ1及び／又は他のＢi値とこれらスレッシュホールドとの比較に基づき、タイルが指定分類の１つに分類され、そしてそれに対応する量子化テーブルが選択されて、タイル内のサブ帯域に適用されるべき量子化値が決定される。又、Ｓkは、オリジナル像が多数の特徴部を含む場合には大きくなる傾向があり、それ故、ある実施形態では、像タイルを分類するのに、Ｂkではなく、Ｓkが使用される。
【００９０】
意義のある部分と意義のない部分との間を分割する希薄データエンコード
図１０Ａ及び１０Ｂを参照すれば、ベース像のタイルに対する変換係数が発生されそして量子化されると、次の段階は、それにより得られるタイルの係数をエンコードすることである。計算段階２８０のグループが各ＮＱＳサブ帯域に対して繰り返される。各ＮＱＳサブ帯域をエンコードすることにより発生されたビット流は、図５Ａ−５Ｅを参照して上述したように、ビット平面により分割され、そして像ファイルに記憶されるビット流を形成するように一緒にグループ分けされる。
【００９１】
ＭａｘｂｉｔＤｅｐｔｈマスク
図１０Ａを参照すれば、エンコード手順又は装置は、エンコードされるべきＮＱＳサブ帯域におけるデータのブロックの最大ビット深さを決定し（２８６）、これは、ブロックにおける係数値のいずれかをエンコードするに必要な最大ビット数であり、ここでは、最大ビット深さ即ちＭａｘｂｉｔＤｅｐｔｈと称される。ＭａｘｂｉｔＤｅｐｔｈの値は、ブロックにおけるデータ値の絶対値をエンコードするのに必要な最大ビット数を計算することにより決定される。特に、ブロックにおけるエレメントの最大絶対値をＶとし、そして「ｉｎｔ（）」が特定値の整数部分を表わすとすれば、ＭａｘｂｉｔＤｅｐｔｈは、ｉｎｔ（ｌｏｇ２Ｖ）＋１に等しい。各トップレベルブロックに対する最大ビット深さは、対応するビット流（例えば、その係数がエンコードされているところのサブ帯域グループに対する意義のあるビット流）において記憶される。次いで、現在ブロックに対してブロック手順が呼び出される（２８８）。ブロック手順の擬似コード表示がテーブル２に示されている。
【００９２】
各ブロックは、４つのサブブロックを含む（図１１Ａ参照）。図１０Ｂに示すように、ブロック手順は、現在ブロックの４つのサブブロック各々に対してＭａｘｂｉｔＤｅｐｔｈを決定する（３００）。次いで、ＭａｘｂｉｔＤｅｐｔｈマスクを発生しそしてエンコードする（３０１）。このマスクは、４つのビットｍ1、ｍ2、ｍ3及びｍ4を有し、その各々は、対応するサブブロックのＭａｘｂｉｔＤｅｐｔｈが現在（親）ブロックのＭａｘｂｉｔＤｅｐｔｈ  ｍ0に等しい場合だけ規定値（例えば１）にセットされ、さもなければ、０にセットされる。マスクの数学的表示は、次の通りである。
マスク＝（ｍ0＝＝ｍ1）＋（ｍ0＝＝ｍ2）＋（ｍ0＝＝ｍ3）＋（ｍ0＝＝ｍ4）但し、上記式の「＋」は、連結を表わす。
例えば、１０００のマスクは、サブブロック１のみが、現在ブロックのＭａｘｂｉｔＤｅｐｔｈに等しいＭａｘｂｉｔＤｅｐｔｈを有することを指示する。マスクの値は、常に、１と１５との間である。
【００９３】
ＭａｘｂｉｔＤｅｐｔｈマスクは、１５記号のハフマンテーブル（テーブル１を参照）を使用してエンコードされるのが好ましい。明らかなように、１つのサブブロックのみが親ブロックのＭａｘｂｉｔＤｅｐｔｈに等しいＭａｘｂｉｔＤｅｐｔｈを有するような最も一般的なマスクパターンに対応する４つのマスク値が３ビットのみでエンコードされる。
テーブル１
ＭａｘｂｉｔＤｅｐｔｈマスクをエンコードするためのハフマンテーブル
マスク                      ハフマンコード
０００１                            １１１
００１０                            １０１
００１１                          １００１
０１００                            ０１１
０１０１                          ００１１
０１１０                        １００００
０１１１                        ０１００１
１０００                            １１０
１００１                        ０１０００
１０１０                          ０００１
１０１１                        ００１１０
１１００                          ０１０１
１１０１                        ００１１１
１１１０                          ００００
１１１１                        １０００１
【００９４】
サブブロックのＭａｘｂｉｔＤｅｐｔｈ値のエンコード
更に、ステップ３０１は、ＭａｘｂｉｔＤｅｐｔｈが、現在ブロックのＭａｘｂｉｔＤｅｐｔｈ  ｍ0に等しくないサブブロックの各々に対してＭａｘｂｉｔＤｅｐｔｈ値をエンコードすることを含む。例えば、図１１Ａ及び１１Ｂに示すように、現在ブロックのＭａｘｂｉｔＤｅｐｔｈ値が
ｍ1、ｍ2、ｍ3、ｍ4＝５、０、３、２
である場合に、エンコードする必要のあるＭａｘｂｉｔＤｅｐｔｈ値は、ｍ2、ｍ3及びｍ4だけである。というのは、ｍ1のＭａｘｂｉｔＤｅｐｔｈ値は、ＭａｘｂｉｔＤｅｐｔｈマスクから既知であり、そして現在ブロックのＭａｘｂｉｔＤｅｐｔｈ  ｍ0の以前に記憶されそしてエンコードされた値だからである。
ｍ0＝１の場合には、サブブロックのＭａｘｂｉｔＤｅｐｔｈ値をエンコードする必要がないことに注意されたい。というのは、これらの値は、ＭａｘｂｉｔＤｅｐｔｈマスクから完全に既知だからである。
【００９５】
ｍ≠１の場合には、各ｍi≠ｍ0に対して、この手順は、値ｍiを次のようにエンコードする。
−  ｍi＝０、従って、手順は、長さｍ0−１の０のストリングを出力する。
−  さもなければ、手順は、長さｍ0−ｍi−１の０のストリングに続いて１を出力する。
例えば、ｍ0＝５そしてｍ1＝０である場合には、ｍ1が４つの０のストリング：００００としてエンコードされる。ｍ0＝５そしてｍ2＝３の場合には、ｍ2が、（５−３−１＝１）１つの０の後に１が続くストリング：０１としてエンコードされる。
｛ｍ1、ｍ2、ｍ3、ｍ4｝＝｛５、０、３、２｝の例では、ＭａｘｂｉｔＤｅｐｔｈ値が次のようにエンコードされる。
マスク    ｍ2サブブロック    ｍ3サブブロック    ｍ4サブブロック
１１１      ００００             ０１              ００１
【００９６】
次いで、エンコードされているＮＱＳサブ帯域の係数が２つ以上のビット流において記憶されるべき場合には、そのブロックのＭａｘｂｉｔＤｅｐｔｈ値のエンコードされた表示が更に２つの部分に分割され、その各部分は、ある範囲のビット平面に対する情報内容を含む。説明を容易にするために、ここで、意義のある部分及び意義のない部分と称する２つの部分間でＭａｘｂｉｔＤｅｐｔｈ値、マスク及び係数値をいかに分割するかについて詳細に述べる。意義のある部分、中程度に意義のある部分、及び意義のない（又は最も意義の低い）部分に対応する３つのビット平面範囲の間でこれら値を分割するのに同じ技術が使用される。
【００９７】
ＮＱＳサブ帯域の最後のグループを除く各ＮＱＳサブ帯域に対して、係数ビット平面が２つ又は３つの範囲に分割される。２つのビット平面範囲があるときには、２つの範囲を分割するビット平面スレッシュホールドが選択され又は規定される。ビット平面スレッシュホールドより低い各「係数値」（そのＭａｘｂｉｔＤｅｐｔｈ値を含む）の「意義のない」部分は、「意義のない」ビット流２０６に記憶され（図５Ｄを参照）、そして残りの係数は、それに対応する意義のあるビット流２０６に記憶される。ビット平面範囲の選択は、典型的に実験ベースで行われるが、種々のビット平面範囲を使用して多数の像をエンコードし、次いで、種々の解像度レベルに対してビット流間の特定のデータ分割を平均的に達成するビット平面範囲のセットを選択する。例えば、特定の分割は、第１解像度レベル及び次の解像度レベルに対しビット流間でデータをほぼ等しく分割することである。或いは又、特定の分割は、第１の（低い）解像度レベルに対するビット流の４倍程度のデータを含むように第２の解像度レベルに対するビット流を要求してもよい。
最初に、ＭａｘｂｉｔＤｅｐｔｈ値を、意義のある部分と意義のない部分との間で分割することを説明し、次いで、最小サイズブロックに対して係数値をエンコードしそして分割することを説明する。
【００９８】
ブロックのＭａｘｂｉｔＤｅｐｔｈ  ｍ0がスレッシュホールドより低い場合には、ＭａｘｂｉｔＤｅｐｔｈマスクと、サブブロックに対するＭａｘｂｉｔＤｅｐｔｈ値の各ビットとが、ベース像サブファイルの意義のない部分に記憶される。さもなければ、ＭａｘｂｉｔＤｅｐｔｈマスクは、意義のある部分に記憶され、そしてエンコードされたサブブロックのＭａｘｂｉｔＤｅｐｔｈ値の各々が、意義のある部分と意義のない部分との間で次のように分割される。この分割は、次のように取り扱われる。ｍi≧スレッシュホールドの場合には、完全にエンコードされたＭａｘｂｉｔＤｅｐｔｈ値ｍiがサブ像サブファイルの意義のある部分に含まれる。さもなければ、ｍi＝ｍ0を除き、各ＭａｘｂｉｔＤｅｐｔｈ値ｍiのスレッシュホールドビットである第１のｍ0が、サブ像サブファイルの意義のある部分に記憶され、そして各ｍiの残りのビットが（もしあれば）サブ像サブファイルの意義のない部分に記憶される。
係数のビット平面を３つの範囲に分割すべき場合には、２つのビット平面スレッシュホールドが選択又は規定され、そしてＭａｘｂｉｔＤｅｐｔｈマスク及び値が、上記と同じ技術を使用して３つのビット流間に割り当てられる。
【００９９】
最小サイズブロックに対する係数値のエンコード
次いで、現在ブロックのサイズ（即ち現在ブロックにおける係数値の数）が、所定の最小数、例えば、４でない場合には（３０２−ノー）、現在ブロックの４つのサブブロック各々に対するブロック手順が呼び出される（３０３）。これは、繰り返し手順コールである。サブブロックについてのブロック手順が呼び出される結果、サブブロックに対するＭａｘｂｉｔＤｅｐｔｈマスク及び値がエンコードされ、そしてエンコードされているサブ帯域グループのビット流の対へと挿入される。サブブロックが規定の最小サイズでない場合には、そのサブブロックについてブロック手順が繰り返し呼び出され、等々となる。
【０１００】
所定の最小サイズのブロックがブロック手順により処理されるときには（３０２−イエス）、そのブロックに対するＭａｘｂｉｔＤｅｐｔｈマスク及びサブブロックのＭａｘｂｉｔＤｅｐｔｈ値がエンコードされた（３０１）後に、ブロックの係数がエンコードされ、そしてエンコードされた値が、意義のある部分と意義のない部分との間で分割される（３０４）。
ゼロに等しくない各係数は、その符号を示すＰＯＳ／ＮＥＧビットと、付加的なビットのＭａｘｂｉｔＤｅｐｔｈ数とを含む。更に、符号ビット以外の各非ゼロ係数のＭＳＢ（最上位ビット）は、係数に対するＭａｘｂｉｔＤｅｐｔｈ値から既に知られており、実際には、１に等しいことが分かっている。それ故、このＭＳＢは、エンコードする必要がない（又は別の観点から、ＭａｘｂｉｔＤｅｐｔｈ値で既にエンコードされている）。
【０１０１】
最小サイズブロックの各係数に対し、その係数のＭａｘｂｉｔＤｅｐｔｈがスレッシュホールドより小さい場合には、その符号ビットを含む係数の全ビットが意義のない部分にある。さもなければ、符号ビットは、意義のある部分にあり、そして更に、最下位ビット（ＬＳＢ）のスレッシュホールド数より高い最上位ビット（ＭＳＢ）がもしあれば、それも、意義のある部分に含まれる。換言すれば、下限「スレッシュホールド」ビット数が、意義のない部分に割り当てられる。
しかしながら、ＭａｘｂｉｔＤｅｐｔｈがスレッシュホールドに等しい場合には、符号ビットは、それでも、意義のある部分に割り当てられ、そして残りのビットは、意義のない部分に割り当てられる。
【０１０２】
更に、上述したように、各係数の絶対値のＭＳＢは、ＭａｘｂｉｔＤｅｐｔｈマスク及び値から既に知られているので、そのビットは記憶されない。又、ゼロの値をもつ係数は、ゼロである係数のＭａｘｂｉｔＤｅｐｔｈ値からそれらの値が完全に分かるので、エンコードされない。
例えば（図１１Ｃを参照）、ブロックの４つの係数｛３１、０、−５、−２｝を考える。その値は、２進値で、ＰＯＳ１１１１１、０、ＮＥＧ１０１、ＮＥＧ１０であり、そしてスレッシュホールド値は３である。最初に、ゼロ値の係数と、非ゼロ係数のＭＳＢが除去されて、ＰＯＳ１１１１、ＮＥＧ０１、ＮＥＧ０を生じる。次いで、次のように、最下位ビット（符号ビット以外）のスレッシュホールド数が、意義のない部分に割り当てられ、そして残りが、意義のある部分に割り当てられる。
意義のある部分：ＰＯＳ１、ＮＥＧ
意義のない部分：１１１、０１、ＮＥＧ０
意義のある部分は、３１及び−５係数値の最上位ビットを含み、一方、意義のない部分は、３１及び−５係数値の残りのビットと、−２係数値の全てのビットを含む。
【０１０３】
テーブル２
ブロックエンコード手順の擬似コード
0004707681.tif 000021
0004707681.tif 000022
上述したように、係数のビット平面を３つの範囲に分割すべき場合には、２つのビット平面スレッシュホールドが選択され又は予め定められ、そしてエンコードされた係数値が、上記と同じ技術を用いて３つのビット流間に割り当てられる。
【０１０４】
像の再構成
ファイル内のベース像がエンコードされたところの解像度レベル以下の特定の解像度レベルにおいて像ファイルから像を再構成するために、その特定の解像度レベルまでの像ファイルの各ビット流が圧縮解除されそして量子化解除される。
次いで、タイルごとのベースで、再構成された変換係数が逆変換されて、特定の解像度レベルにおいて像データが再構成される。
【０１０５】
図１２を参照すれば、像再構成プロセスは、像ファイルから受け取った像データから像を再構成する（３２０）。像の再構成を実行する手順又は装置のユーザ、或いはユーザに代わって操作する制御手順は、像データに含まれた最大解像度レベル以下の解像度レベルを選択し又は特定する（３２２）。像データファイルのヘッダが読み取られ、像におけるタイル（Ｌ、Ｋ）の数及び配列と、像再構成手順に必要とされる他の情報が決定される（３２３）。ステップ３２４及び３２６は、所与の解像度レベルにおいて像を再構成し、そしてステップ３２８において、再構成された像が表示されるか又はメモリ装置に記憶される。図１３Ａ及び１３Ｂは、特定のサブ像レベルにおいて特定のタイルに対するデータをデコードするための手順の詳細な図である。
【０１０６】
図１２に示す１つの好ましい実施形態では、特定の解像度レベルに関連した像ファイルのデータは、最初にタイルごとのサブファイルに再編成され、各タイルサブファイルは、そのタイルに対するビット流を含む（３２４）。次いで、各タイルのデータが処理される（３２６）。ヘッダ情報が読み取られて、タイルの各トップレベルサブ帯域ブロックに対するＭａｘｂｉｔＤｅｐｔｈ、各サブ像サブ帯域を量子化するのに使用される量子化ファクタ等が決定される。特定解像度レベルにおいて像を再構成するのに必要な各ＮＱＳサブ帯域に対する変換係数が、サブ帯域の順序でデコードされる。１つのＮＱＳサブ帯域において係数をデコードするためのデコードプロセスの詳細を、図１３を参照して以下に説明する。それにより得られるデコードされた係数は、各サブ帯域の量子化ファクタ（ベース像ヘッダにおいて識別されたＱテーブルから得られた）を適用して量子化解除される。それにより得られる量子化解除された係数に逆変換が適用される。量子化解除された変換係数から像を再構成するためのウェーブレット状逆変換は、既に上述したことに注意されたい。
【０１０７】
図１３Ａを参照すれば、特定の解像度レベルにおいて１つのタイルｔに対するデータをデコードするために、１組のステップ３４０を繰り返して、タイルの各ＮＱＳサブ帯域をデコードするが、特定の解像度レベルに必要とされないＮＱＳサブ帯域は除外されると共に、特定の解像度レベルに必要とされないエンコードされた係数値のビット平面を含むビット流も除外される。図５Ｄ及び５Ｅを参照すれば、特定の解像度レベルに必要とされるベース像のビット流だけがデコードされる。デコードされているタイルの特定のトップレベルブロック（ＮＱＳサブ帯域に対応する）に対し、トップレベルブロックのＭａｘｂｉｔＤｅｐｔｈが、タイルアレーのヘッダから（データがタイルアレーへと再編成された場合）又はサブ帯域に対するビット流の始めのデータから決定され（３４６）、次いで、デコードブロック手順が呼び出されて、現在ブロックのデータがデコードされる（３４８）。
【０１０８】
特定のサブ帯域のデータがデコードされた後、そのサブ帯域に対するデコードされた変換係数が、各量子化ファクタを適用して量子化解除される（３５０）。
或いは又、全てのサブ帯域の全ての係数がデコードされた後に、量子化解除が行われてもよい。
ＮＱＳサブ帯域の全ての係数がデコードされて量子化解除されると、逆変換が実行されて、特定の解像度レベルにおいて現在タイルｔに対する像データが再生される。
【０１０９】
別の実施形態では、図１２のステップ３２４は使用されず、そして像ファイルのデータは、タイルアレーへと再編成されない。むしろ、像データは、サブ帯域グループごとに処理され、これは、全てのタイルに対して回復された変換係数を初期の再構成ステップ中に累積して記憶することを必要とする。特定のサブ帯域グループの特定タイルの１つのトップレベルブロックに対するデータをデコードするステップ３４０がタイルごとに繰り返される。より詳細には、特定サブ帯域グループの特定タイルの特定トップレベルブロックに対し、そのトップレベルブロックのＭａｘｂｉｔＤｅｐｔｈが、タイルアレーのヘッダから、又はサブ帯域グループに対するビット流の始めのデータから決定され（３４６）、次いで、デコードブロック手順が呼び出されて、現在ブロックに対するデータがデコードされる（３４８）。
【０１１０】
図１３Ｂを参照すれば、デコードブロック手順（上述した好ましい実施形態及び別の実施形態の両方に適用できる）は、それを適用できるエンコードされたデータアレーにおけるＭａｘｂｉｔＤｅｐｔｈデータをデコードして、現在ブロックの各サブブロックのＭａｘｂｉｔＤｅｐｔｈを決定することにより開始される（３６０）。デコードされているＮＱＳサブ帯域に基づき、ブロックのＭａｘｂｉｔＤｅｐｔｈデータは、上述したように、１つのビット流にあってもよいし、或いは２つ又は３つのビット流間で分割されてもよく、それ故、必要とされる全てのビット流からの適用可能なＭａｘｂｉｔＤｅｐｔｈデータビットが読み取られてデコードされる。現在ブロックのサイズが所定の最小ブロックサイズより大きい場合には（３６２−ノー）、現在ブロックの各サブブロックに対してデコードブロック手順が呼び出される（３６３）。これは、繰り返し手順コールである。サブブロックに対してデコードブロック手順を呼び出す結果として、サブブロックに対するＭａｘｂｉｔＤｅｐｔｈ値がデコードされる。そのサブブロックが所定の最小サイズのものでない場合には、そのサブブロックに対してデコードブロック手順が繰り返し呼び出され、等々となる。
【０１１１】
所定の最小サイズのブロックがデコードブロック手順により処理されるときには（３６２−イエス）、ブロックの係数がデコードされる。デコードされているサブ帯域グループに基づき、ブロックのエンコードされた係数は、上述したように、１つのビット流にあってもよいし、或いは２つ又は３つのビット流間で分割されてもよく、それ故、必要とされる全てのビット流からの適用可能なデータビットが読み取られてデコードされる。
図１３Ａを参照すれば、各タイルの量子化された変換係数は、特定の解像度レベル含まれる全てのＮＱＳサブ帯域に対して再生される。これらの係数が量子化解除された後、既に述べたように、逆変換が各タイルに適用される（３５２）。
【０１１２】
非交番水平及び垂直変換を使用する実施形態
別の好ましい実施形態では、像の各タイルは、先ず、多数（例えば５つ）の水平デコンポジション変換層により処理され、次いで、同様の数の垂直デコンポジション変換層により処理される。同等のこととして、垂直変換層を、水平変換層の前に適用することもできる。本発明の像変換方法のハードウェア実施においては、変換層の順序のこの変更は、（Ａ）データアレーを回転する回数を減少し、又は（Ｂ）作用像アレー（１つ又は複数）における行及び列の役割をスイッチングする回路の必要性を回避するという効果を有する。次々の水平変換を実行するときには、第１の水平変換により発生された低周波数係数の最も左のアレーに第２の水平変換が適用され、そして第２の水平変換により発生された低周波数係数の最も左のアレーに第３の水平変換が適用され、等々となる。従って、水平及び垂直の変換が交互に行われる変換方法の場合の約２倍のデータに第２ないし第Ｎの水平変換が適用される。しかしながら、この余計なデータ処理は、一般に、ハードウェア実施において付加的な処理時間を必要としない。というのは、このような実施においては、水平フィルタが作用像アレーの全ての行に同時に適用されるからである。
【０１１３】
垂直の変換は、作用像アレーの次々に小さくなるサブアレーに連続的に適用される。像データが全ての変換層により（水平及び垂直の両方に）変換された後、上述した量子化及びエンコードステップが、それにより得られた変換係数に適用され、像エンコードプロセスが完了となる。
上述したように、処理されているアレーのエッジから離れた係数に適用される（典型的に長い）変換フィルタとは異なる（そして典型的に短い）変換フィルタが、それらアレーのエッジ付近の係数に適用される。長い変換フィルタを中間に使用することは、短い変換フィルタより良好なデータ圧縮を与えるが、短い変換フィルタは、隣接タイルからのデータ及び係数の必要性を排除する。
【０１１４】
デジタルカメラアーキテクチャー
図１４には、本発明によるデジタルカメラシステム４００の実施形態が示されている。このデジタルカメラシステム４００は、像捕獲装置４０２を備え、例えば、ＣＣＤセンサアレー、又はデジタルエンコードされた情報のアレーとして像を捕獲するのに適した他のメカニズムを備えている。像捕獲装置は、アナログ像情報をデジタル値に変換するためのアナログ／デジタル変換（ＡＤＣ）回路を含むと仮定する。
【０１１５】
作用メモリ４０４、典型的に、ランダムアクセスメモリは、像捕獲装置４０２からデジタルエンコードされた像情報を受け取る。より一般的には、このメモリは、デジタルエンコードされた像を、それがカメラデータ（即ち像）処理回路４０６により変換され圧縮されそしてその他処理される間に、記憶するのに使用される。データ処理回路４０６は、１つの実施形態では、１組の所定の像処理オペレーションを実行するための状態マシンのセットと、固定布線ロジックとで構成される。
【０１１６】
別の実施形態では、データ処理回路４０６は、高速汎用マイクロプロセッサ及び１組のソフトウェア手順を使用して一部分又は完全に実施することができる。
しかしながら、少なくとも２０００年に利用できる技術を使用すると、ある商品の要件である例えば２０画像／秒をカメラで撮影できるに充分なほど高速に全解像度の像（例えば、１２８０ｘ８４０ピクセルのフルカラー像）を処理しそして記憶することは困難である。並列処理技術又は良好に設計されたソフトウェアを使用することにより、低パワーの汎用像データマイクロプロセッサで、デジタルカメラに必要な高速像処理をサポートできる場合には、このような汎用マイクロプロセッサを使用してデータ処理回路４０６を実施することができる。
【０１１７】
各像は、データ処理回路４０６で処理された後に、通常、「フラッシュ」（即ちＥＥＰＲＯＭ）メモリ技術を用いて実施される不揮発性メモリ記憶装置４０８に「像ファイル」として記憶される。この不揮発性メモリ記憶装置４０８は、取り外し可能なメモリカードとして実施されるのが好ましい。これは、カメラのユーザが１つのメモリカードを取り外し、別のメモリカードを差し込み、そして追加の画像を撮影できるようにする。しかしながら、ある実施形態では、不揮発性メモリ記憶装置４０８は、取り外し可能でなくてもよく、この場合に、カメラは、通常、汎用のデスクトップコンピュータのような他の装置と像ファイルをやり取りできるようにするためにデータアクセスポート４１０を有する。取り外し可能な不揮発性メモリ４０８をもつデジタルカメラも、データアクセスポート４１０を含む。
【０１１８】
デジタルカメラ４００は、カメラにコマンドを与えるための１組のボタン４１２を含む。像捕獲ボタンに加えて、通常、ユーザが、撮影されるべき次の画像の画質レベルを選択し、メモリ内の像をスクロールしてカメラの像ビューア４１４で見えるようにし、不揮発性像メモリ４０８から像を削除し、そしてカメラの他の全てのファンクションを呼び出すことができるようにする多数の他のボタンが存在する。このような他のファンクションは、フラッシュ光源を使用し、そして像ファイルをコンピュータとやり取りできるようにすることを含む。これらのボタンは、１つの実施形態では、電気機械的なコンタクトスイッチであるが、他の実施形態では、少なくとも幾つかのボタンが、ユーザインターフェイスディスプレイ４１６又は像ビューア４１４においてタッチスクリーンボタンとして実施されてもよい。
【０１１９】
ユーザインターフェイスディスプレイ４１６は、通常、（Ａ）像ビューア４１４とは個別のＬＣＤディスプレイ装置として実施されるか、又は（Ｂ）像ビューア４１４に表示される像として実施される。不揮発性像メモリ１０８に記憶された像に関するメニュー、ユーザプロンプト及び情報は、ユーザインターフェイスディスプレイ４１６がいかに実施されるかに関わらず、そのディスプレイに表示される。
【０１２０】
像が捕獲され、処理されそして不揮発性像メモリ４０８に記憶された後、それに関連した像ファイルがメモリ４０８から検索されて、像ビューアで見られる。
より詳細には、像ファイルは、その変換され圧縮された形態から、フレームバッファ４１８に記憶するのに適したデータアレーへ変換して戻される。フレームバッファにおける像データは、像ビューア４１４に表示される。日付／時刻回路４２０は、現在の日時を追跡するのに使用され、各記憶された像は、像が撮影された日時で日付スタンプされる。
【０１２１】
更に、図１４を参照すれば、デジタルカメラ４００は、所定の１組のプリミティブなオペレーション、例えば、ある量の像データに変換を適用するのに必要な乗算及び加算演算を実行するためのデータ処理回路４０６と、１組の所定の像取り扱いオペレーションを実行するようにデータ処理回路を制御するための１組の状態マシン４３０−４４２とを含むのが好ましい。１つの実施形態では、デジタルカメラの状態マシンは、次の通りである。
【０１２２】
−  カメラの像捕獲メカニズムから受け取られた像を変換し、圧縮しそして記憶するための１つ以上の状態マシン４３０。この像は、「ビューファインダー」像とも称される。というのは、処理されている像が、一般に、カメラの像ビューア４１４上に見られる像だからである。この１組の状態マシン４３０は、不揮発性像メモリ４０８に記憶される各像ファイルを最初に発生するものである。画像を撮影する前に、ユーザは、カメラのボタン４１２を使用して、記憶されるべき像の画質レベルを指定する。好ましい実施形態では、像エンコード状態マシン４３０は、本発明の１つ以上の特徴を具現化する。
【０１２３】
−  記憶された像ファイルを圧縮解除し、逆変換しそしてカメラの像ビューアに表示するための１つ以上の状態マシン４３２。像データを圧縮解除し、逆変換しそして量子化解除することにより発生された再構成像は、カメラのフレームバッファ４１８に記憶され、従って、像ビューア４１４で見ることができる。
【０１２４】
−  不揮発性像メモリ４０８に記憶された像の数のカウントを更新しそして表示するための１つ以上の状態マシン４３４。像カウントは、ユーザインターフェイスディスプレイ４１６に表示されるのが好ましい。又、この１組の状態マシン４３４は、通常、不揮発性像メモリ４０８の何パーセントが像ファイルで占有されずに残っているか指示し、又は付加的な像を記憶するカメラの能力についての他の指示も与える。カメラが個別のインターフェイスディスプレイ４１６をもたない場合には、このメモリ状態情報が、像ビューア４１４に示され、例えば、像ビューア４１４に示された像に重畳されるか、又はメインビューア像とは個別にビューア４１４の領域に示される。
【０１２５】
−  像捕獲メカニズム４０２により現在「見られている」像が像ビューア４１４に表示されてユーザがその像を見ることができ、像捕獲ボタンが押された場合にその像が記憶されるようなカメラの「ビューファインダー」モードを実施するための１つ以上の状態マシン４３６。これらの状態マシンは、像捕獲装置４０２から受け取られた像を、おそらく生の像データを改善するために適当な補修処理ステップを実行した後に、カメラのフレームバッファ４１８へ転送する。
【０１２６】
−  不揮発性像メモリ４０８から、汎用コンピュータのような外部装置へ像をダウンロードするための１つ以上の状態マシン４３８。
−  汎用コンピュータのような外部装置から不揮発性像メモリ４０８へ像をアップロードするための１つ以上の状態マシン４４０。これは、カメラを像ビューア装置として使用できると共に、メモリカードの像ファイルを転送するためのメカニズムとしても使用できるようにする。
【０１２７】
一般に、本発明は、使用可能な作用メモリの量が、全像を単一のタイルとして処理するには不充分であるか、低メモリ環境を含む種々の環境で製品が機能しなければならないか、低帯域巾の通信チャンネルを経て像を搬送する必要があるか、或いは種々の解像度レベルで像を与えることが必要又は便利であるようないかなる「メモリ保存」状況においても有用である。
本発明を使用してエンコードされた圧縮像を受信するウェブブラウザのようなストリーミングデータ実施形態では、像のサブ像は、像の他の高レベルサブ像のデータが受け取られているときに、オンザフライでデコードされそして圧縮解除される。その結果、圧縮像の１つ以上の低解像度バージョンが再構成されて表示された後に、像の最高解像度バージョンのデータが通信チャンネルを経て受信（及び／又はデコード）される。
【０１２８】
別の実施形態では、上述したウェーブレット状変換とは異なる変換を使用することができる。
別の実施形態では、像タイルを異なる順序で処理することができる。例えば、像タイルは、左から右ではなく、右から左へ処理することができる。同様に、像タイルは、最下行でスタートして最上行に向かって処理を進めることもできる。
【０１２９】
本発明は、コンピュータ読み取り可能な記憶媒体に埋設されたコンピュータプログラムメカニズムを含むコンピュータプログラム製品として実施することができる。例えば、このコンピュータプログラム製品は、図２に示したプログラムモジュールを含むことができる。これらのプログラムモジュールは、ＣＤ−ＲＯＭ、磁気ディスク記憶製品、或いは他のコンピュータ読み取り可能なデータ又はプログラム記憶製品に記憶することができる。又、コンピュータプログラム製品のソフトウェアモジュールは、インターネットを経て、或いはコンピュータデータ信号（ソフトウェアモジュールが埋設された）を搬送波において送信することにより、電気的に配信することもできる。
以上、本発明は、幾つかの特定の実施形態を参照して詳細に説明したが、これは、本発明を単に例示するものであって、これに限定するものではない。特許請求の範囲に規定された本発明の真の精神及び範囲から逸脱せずに、種々の変更がなされ得ることが当業者に明らかであろう。
【図面の簡単な説明】
【０１３０】
【図１】ウェブサーバーと、多数のクライアントコンピュータとを備え、多解像度の像をクライアントコンピュータへ分配するための分散型コンピュータシステムを示すブロック図である。
【図２】本発明の実施形態によるコンピュータシステムのブロック図である。
【図３Ａ】生の像を変換像アレーへ変換しそして変換像アレーを圧縮像ファイルへと圧縮するプロセスを概略的に示す図である。
【図３Ｂ】空間周波数サブ帯域を、変換係数をエンコードするのに使用されるＮＱＳサブ帯域へとマッピングするところを示す図である。
【図４】像の多解像度再生（即ち多数の解像度レベルにおける）を容易にするよう編成された像を表わすエンコードされたデータの概念図である。
【図５Ａ】像記憶データ構造体を示す図である。
【図５Ｂ】像記憶データ構造体を示す図である。
【図５Ｃ】像記憶データ構造体を示す図である。
【図５Ｄ】像記憶データ構造体を示す図である。
【図５Ｅ】像記憶データ構造体を示す図である。
【図６】本発明を適用できる像処理プロセスの高レベルフローチャートである。
【図７Ａ】順方向及び逆方向のウェーブレット状データ変換手順をグラフ的に示す図である。
【図７Ｂ】順方向及び逆方向のウェーブレット状データ変換手順をグラフ的に示す図である。
【図７Ｃ】順方向及び逆方向のウェーブレット状データ変換手順をグラフ的に示す図である。
【図８】デコンポジションウェーブレット又はウェーブレット状変換の多数の層を像データのアレーに適用することにより発生されるウェーブレット係数の空間周波数サブ帯域を示す図である。
【図９】像のブロックに対して量子化除数のセットを選択するためのブロック分類方法を示すフローチャートである。
【図１０Ａ】像のブロックに対する変換係数をエンコードするための手順のフローチャートである。
【図１０Ｂ】像のブロックに対する変換係数をエンコードするための手順のフローチャートである。
【図１１Ａ】エンコードされた像の各ブロック及びサブブロックにおける変換係数をエンコードするのに必要なビットの数を表わす値、好ましい実施形態ではＭａｘｂｉｔＤｅｐｔｈ値と称する、をエンコードする方法を示す図である。
【図１１Ｂ】エンコードされた像の各ブロック及びサブブロックにおける変換係数をエンコードするのに必要なビットの数を表わす値、好ましい実施形態ではＭａｘｂｉｔＤｅｐｔｈ値と称する、をエンコードする方法を示す図である。
【図１１Ｃ】エンコードされた像の各ブロック及びサブブロックにおける変換係数をエンコードするのに必要なビットの数を表わす値、好ましい実施形態ではＭａｘｂｉｔＤｅｐｔｈ値と称する、をエンコードする方法を示す図である。
【図１２】本発明を適用できる圧縮像再構成プロセスの高レベルフローチャートである。
【図１３Ａ】像に対する変換係数をデコードし、そして係数から像を再構成するための手順を示すフローチャートである。
【図１３Ｂ】像に対する変換係数をデコードし、そして係数から像を再構成するための手順を示すフローチャートである。
【図１４】本発明の１つ以上の特徴を具現化できるデジタルカメラのブロック図である。
【図１５】サムネイル像をダウンロードし、その像においてズームインし、そして像の新たな部分へパンするクライアントコンピュータの概念的フローチャートである。
【図１】
0004707681.tif 000023
【図２】
0004707681.tif 000024
【図３Ａ】
0004707681.tif 000025
【図３Ｂ】
0004707681.tif 000026
【図４】
0004707681.tif 000027
【図５Ａ】
0004707681.tif 000028
【図５Ｂ】
0004707681.tif 000029
【図５Ｃ】
0004707681.tif 000030
【図５Ｄ】
0004707681.tif 000031
【図５Ｅ】
0004707681.tif 000032
【図６】
0004707681.tif 000033
【図７Ａ】
0004707681.tif 000034
【図７Ｂ】
0004707681.tif 000035
【図７Ｃ】
0004707681.tif 000036
【図８】
0004707681.tif 000037
【図９】
0004707681.tif 000038
【図１０Ａ】
0004707681.tif 000039
【図１０Ｂ】
0004707681.tif 000040
【図１１Ａ】
0004707681.tif 000041
【図１１Ｂ】
0004707681.tif 000042
【図１１Ｃ】
0004707681.tif 000043
【図１２】
0004707681.tif 000044
【図１３Ａ】
0004707681.tif 000045
【図１３Ｂ】
0004707681.tif 000046
【図１４】
0004707681.tif 000047
【図１５】
0004707681.tif 000048