(57)【要約】  各要素と前の要素との間の差が計算される（３０３）画像の画像データを圧縮する方法であって、差を所定の相関値と比較するステップ（３０４）と、差とビットプレーンに関連付けられている（３０５）所定の相関値とが等しいならば、第１の値がビットプレーンに記録されるステップ（３０８）と、差と所定の相関値とが等しくないならば、第２の値がビットプレーンに記録されるステップ（３０９）とを備える方法である。第１の値がビットプレーンに記録されている場合、要素の値は記憶されず（３１０）、第２の値がビットプレーンに存在する場合、要素の値が記憶される（３１１）。圧縮された画像は、ビットプレーンとビットプレーンインデックスの両方を使用して伸長され得る。【選択図】  図３
2009516985.tif 000002
【特許請求の範囲】
【請求項１】
各画像要素と前の画像要素との間の相関を計算し、画像の画像データの圧縮率を高める方法であって、
前記相関を所定の相関値と比較し、
前記相関と前記所定の相関値とが等しい場合、第１の値を記録し、
前記相関と前記所定の相関値とが等しくない場合、第２の値を記録するステップと
を備える、方法。
【請求項２】
前記第１の値及び前記第２の値がビットプレーンに記録される、請求項１に記載の方法。
【請求項３】
前記第１の値が記録される場合、前記画像要素の値を記憶せず、前記第２の値が記録される場合に、前記画像要素の値を記憶する、請求項１に記載の方法。
【請求項４】
前記所定の相関値を前記ビットプレーンに関連付けるステップをさらに備える、請求項２に記載の方法。
【請求項５】
前記所定の相関値が−８から＋８までの値である、請求項１に記載の方法。
【請求項６】
別個のビットプレーンが使用される所定の相関値毎に前記差の比較を繰り返すステップをさらに備える、請求項５に記載の方法。
【請求項７】
前記第１の値が１であり、前記第２の値が０である、請求項１に記載の方法。
【請求項８】
前記画像要素の各々が画素である、請求項１に記載の方法。
【請求項９】
前記画像要素の各々を前の画像要素と比較し、当該画像要素と前記前の画像要素が互いの所定のレンジに収まる場合、前記前の画像要素と等しくなるように当該画像要素を修正する初期ステップをさらに備え、
前記画像の非可逆圧縮を可能にさせるため反復性が高められる、請求項１に記載の方法。
【請求項１０】
前記比較が、左から右へ、その後に上から下へラスタ順に実行される、請求項１に記載の方法。
【請求項１１】
前記比較が、垂直と対角とから構成される群のうちの一方であり、非ラスタ順に実行される、請求項１に記載の方法。
【請求項１２】
反復符号化圧縮法（ＲＣＣ）、反復符号化圧縮予測法（ＲＣＣＰ）、適応反復符号化法（ＲＣＣＡ）、及び、多次元反復符号化圧縮法から構成される群のうちのいずれか１つに従って前記画像データを変換するステップをさらに備える、請求項１に記載の方法。
【請求項１３】
前記画像を複数のタイルに分割するステップをさらに備える、請求項１に記載の方法。
【請求項１４】
ネットワークを介して前記タイルをストリーム化するステップをさらに備える、請求項１３に記載の方法。
【請求項１５】
複数のデータ要素の各々と前のデータ要素との間の相関を計算して、前記複数のデータ要素を備えるデータの圧縮率を高める方法であって、
前記相関を所定の相関値と比較し、
前記相関と前記所定の相関値とが等しい場合、第１の値を記録し、
前記相関と前記所定の相関値とが等しくない場合、第２の値を記録するステップと
を備える、方法。
【請求項１６】
各画像要素と前の画像要素との間の相関が計算される、画像の画像データを圧縮するシステムであって、
前記相関を所定の相関値と比較し、前記相関と前記所定の相関値とが等しい場合、第１の値をビットプレーンに記録し、前記相関と前記所定の値とが等しくない場合、第２の値を前記ビットプレーンに記録する圧縮モジュールと、
前記ビットプレーン内の前記第１の値及び前記第２の値をビットプレーンインデックスに符号化するエンコーダと
を備え、
前記圧縮された画像が前記ビットプレーンインデックス及び前記ビットプレーンを使用して伸長され得る、システム。
【請求項１７】
前記圧縮された画像及び前記ビットプレーンが記憶媒体に記憶され、前記圧縮された画像が前記圧縮された画像のストリーム化を可能にするため複数個のタイルとして記憶される、請求項１６に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像の画像データを圧縮する方法に関係する。
【関連出願の相互参照】
【０００２】
発明の名称：ＲＥＰＥＴＩＴＩＯＮ  ＣＯＤＥＤ  ＣＯＭＰＲＥＳＳＩＯＮ  ＦＯＲ  ＨＩＧＨＬＹ  ＣＯＲＲＥＬＡＴＥＤ  ＩＭＡＧＥ  ＤＡＴＡ
出願番号：ＰＣＴ／ＩＮ０３／０００４９  ２００３年３月７日出願
発明者：Ａｒｖｉｎｄ  Ｔｈｉａｇａｒａｊａｎ
発明の名称：ＣＯＭＰＲＥＳＳＩＮＧ  ＩＭＡＧＥ  ＤＡＴＡ
出願番号：ＰＣＴ／ＳＧ２００４／０００４１１  ２００４年１２月１５日出願
発明者：Ａｒｖｉｎｄ  Ｔｈｉａｇａｒａｊａｎ
【発明の背景】
【０００３】
反復符号化圧縮法（ＲＣＣ）は、データの圧縮率を高めるために本発明者によって発明された技術である。ＲＣＣは、参照によって内容が本書に引用されている２件の先行出願された相互に関連する出願に開示されている。
【０００４】
ＲＣＣは符号化反復に基づいて非常にすばらしい圧縮レベルを実現する。たとえば、各画素が８ビットによって表現されている画素値のデータ系列を考える。
【表１】
2009516985.tif 000003
【０００５】
ＲＣＣを使用すると、このデータ系列は本例では３２％圧縮可能である。
【０００６】
しかし、さらなる圧縮が望ましい。
【発明の概要】
【０００７】
第１の好ましい態様では、各要素と前の要素との間の差が計算され、画像の画像データを圧縮する方法であって、
差を所定の相関値と比較し、差と所定の相関値とが等しい場合に、第１の値が記録され、差と所定の相関値とが等しくない場合に、第２の値が記録されるステップを備える方法が提供される。
【０００８】
第１の値及び第２の値はビットプレーンに記録されることがある。
【０００９】
第１の値が記録される場合、要素の値は記憶されず、第２の値が記録される場合、要素の値が記憶される。
【００１０】
この方法は、所定の相関値をビットプレーンに関連付けるステップをさらに備えてもよい。
【００１１】
所定の相関値は、−８から＋８までの値でもよい。
【００１２】
この方法は、所定の相関値毎に差の圧縮を反復するステップをさらに備え、所定の相関値毎に別個のビットプレーンが使用される。
【００１３】
第１の値は１であり、第２の値は０であることがある。各要素は画素でもよい。
【００１４】
この方法は、各画像要素を前の画像要素と比較し、画像要素と前の画像要素が互いの所定のレンジ内にあるならば、前の画像要素と等しくなるように画像要素を修正する初期ステップをさらに備えてもよく、画像の非可逆圧縮を可能にさせるため反復性が高められる方法である。
【００１５】
比較は、ラスタ順に、すなわち、左から右、そして、上から下の順に実行されることがある。
【００１６】
比較は非ラスタ順に実行されることがあり、比較は垂直と対角とから構成される群のうちの１つである。
【００１７】
この方法は、反復符号化圧縮法（ＲＣＣ）、反復符号化圧縮予測法（ＲＣＣＰ）、適応反復符号化法（ＲＣＣＡ）、及び、多次元反復符号化圧縮法から構成される群のうちのいずれか１つに従って画像データを変換するステップをさらに備えてもよい。
【００１８】
この方法は、画像を複数のタイルに分割するステップをさらに備えてもよい。
【００１９】
この方法は、ネットワークを介してタイルをストリーム化するステップをさらに備えてもよい。
【００２０】
第２の態様では、各要素と前の要素との間の差が計算され、複数のデータ要素を備えるデータを圧縮する方法であって、
差を所定の相関値と比較し、差と所定の相関値とが等しい場合、第１の値が記録され、差と所定の相関値とが等しくない場合、第２の値が記録されるステップを備える方法が提供される。
【００２１】
第３の態様では、各要素と前の要素との間の差が計算され、画像の画像データを圧縮するシステムであって、
差を所定の相関値と比較し、差と所定の相関値とが等しい場合、第１の値がビットプレーンに記録され、差と所定の値とが等しくない場合、第２の値がビットプレーンに記録される圧縮モジュールと、
ビットプレーン内の第１の値及び第２の値をビットプレーンインデックスに符号化するエンコーダと、
を備え、圧縮された画像がビットプレーンインデックス及びビットプレーンを使用して伸長され得る、システムが提供される。
【００２２】
圧縮された画像及びビットプレーンは記憶媒体に記憶されてもよく、圧縮された画像は圧縮された画像のストリーム化を可能にするため複数個のタイルとして記憶される。
【００２３】
以下、発明の実施形態を添付図面を参照して説明する。
【図面に沿っての詳細な説明】
【００２４】
図面及び以下の説明は、本発明が実施されるかもしれない適当なコンピューティング環境の簡単な、一般的な説明を行うこと目的としている。必須ではないが、発明は、パーソナルコンピュータ、ラップトップコンピュータ、ノートブックコンピュータ、タブレットコンピュータ、ＰＤＡなどのようなコンピュータによって実行されるプログラムモジュールのようなコンピュータ実行可能な命令の一般的な状況で説明されている。一般的に、プログラムモジュールは、特有のタスクを実行するか、又は、特有の抽象的なデータ型を実装するためにルーチン、プログラム、文字、コンポーネント、データ構造体を含む。当業者が認めるように、本発明は、ハンドヘルド装置、マルチプロセッサシステム、マイクロプロセッサベース又はプログラマブル家電製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータなどのその他のコンピュータシステムコンフィギュレーションを用いて実施されることがある。本発明は、タスクが通信ネットワークを介してリンクされているリモートプロセッシング装置によって実行される分散コンピューティング環境でも実施されることがある。分散コンピューティング環境では、プログラムモジュールはローカルメモリ記憶装置及びリモートメモリ記憶装置の両方に置かれることがある。
【００２５】
画像データは高度に相関している。すなわち、少なからず、画像内の隣接データ値は本質的に反復性がある。隣接データ値に反復性がないならば、少なからず、隣接データ値は何らかの形で相互に関連付けられている。
【００２６】
８ビット階調画像では、画素値は、２５６個の別個の階調レベルを与えるために０から２５５まで変化する。各画素は８ビットで表現されている。カラー画像の場合、画素値は、ＲＧＢ画像の２５６個の別個のカラーレベルを与えるために０（黒）から２５５（最も明るい赤）まで変化する。カラー画像に反復性は殆ど存在しないが、隣接画素値間には依然として重要な相関が存在している。隣接画素値間の差は、殆どの場合に、図２に示されているような限定されたレンジ内に収まることが見出されている。
【００２７】
図１を参照して、画素領域のデータ系列の最上行が一実施形態として使用される。
【表２】
2009516985.tif 000004
【００２８】
ＲＣＣが適用される場合：
【表３】
2009516985.tif 000005
このデータ系列には反復性がないため、すべての値が記憶される必要があるので、ＲＣＣは効率的でない。
【００２９】
図３を参照して、反復相関符号化方法が説明される。画素は、画像マトリックスにおいて水平方向（ラスタ順）に走査される（３０１）。各要素及びこの要素の前の要素が比較される（３０２）。要素とこの要素の前の要素との間の差は、要素の値を前の要素の値から減算することにより計算される（３０３）。データ系列中の最初の要素に対して、計算は実行されず、最初の要素の値が記録される。
【００３０】
図１の実施形態を使用すると、データ系列及び隣接要素間の相関は次の通りである。
【表４】
2009516985.tif 000006
【００３１】
次に、相関値がこの１回目の走査に対して選択され、隣接要素間の相関又は差と比較される（３０４）。たとえば、１回目の走査は、＋１という相関値を用いて実行される。相関値はビットプレーンに関連付けられる（３０５）。ビットプレーンは画素値の指標ではない。データ系列中の隣接要素の相関と相関値との間で比較が実行される（３０６）。相関と相関値とが等しいならば（３０７）、１がビットプレーンに記録される（３０８）。そうでなければ、０がビットプレーンに記録される（３０９）。
【表５】
2009516985.tif 000007
【００３２】
符号化中に、データ系列は、ビットプレーンに０が存在するならば、その位置に要素の値を記憶することにより（３１１）符号化され、ビットプレーンに１が存在するならば、値は記憶されない。
【００３３】
データ系列に対し９×８＝７２ビットを記憶するのではなく、６×８ビット＝４８ビットと、値の相関を符号化するためにビットプレーンに対する９ビットとだけが記憶される。よって、実現される圧縮は、（７２−５７）÷７２＝２１％である。
【００３４】
２回目の走査は−１という相関値を用いて実行される（３１２）。
【表６】
2009516985.tif 000008
【００３５】
データ系列に対し９×８＝７２ビットを記憶するのではなく、５×８ビット＝４０ビットと、値の相関を符号化するためにビットプレーンに対する９ビットとだけが記憶される。よって、実現される圧縮は、（７２−４９）÷７２＝３２％である。
【００３６】
走査毎に、別々のビットプレーンが使用される。隣接画素値間の差は殆どの場合に−８から＋８のレンジに収まる。よって、最大で１６個のビットプレーンが使用され、プロセスは各相関値を網羅するために１６回実行される。
【００３７】
複数のビットプレーンが使用される場合には、多次元ビットプレーンが圧縮率を高めるために使用されることがある。本実施形態を使用すると、多次元ビットプレーンは、第１のビットプレーンと第２のビットプレーンの結合を実行する。２進数の加算、又は、ＯＲ演算が２つのビットプレーンに実行され、可逆圧縮多次元ビットプレーンとして記憶される。
【００３８】
上記の実施形態と同じ実施形態を使用すると次の通りである。
【表７】
2009516985.tif 000009
【表８】
2009516985.tif 000010
【００３９】
多次元ビットプレーンは次の通りである。
【表９】
2009516985.tif 000011
【００４０】
ＮＯＴ演算が多次元ビットプレーンと原画像マトリックスとの間で実行される。ＯＲ演算とＮＯＴ演算の両方は、画像データの完全性を維持し、変換の無損失性を保存する。
【表１０】
2009516985.tif 000012
【表１１】
2009516985.tif 000013
【００４１】
多次元ビットプレーンは、画像画素データを所定の相関値と比較することにより作成された全ビットプレーンの統合されたビットプレーン表現である。その結果、（所定の相関値のレンジに基づく）ビットプレーンのレンジ全体は、削減された数のビットプレーンで表現されるので、画像データの圧縮率がさらに高められる。
【００４２】
したがって、原画像データは１つ以上のビットプレーンに分解され、画像のインデックスと共に記憶される。再構成はインデックス及びビットプレーンを使用して無損失で行われる。
【００４３】
復号化するために、ビットプレーンは検査される。ビットプレーンのある位置に０が記憶されているならば、値が記憶されている。この値は、原画像マトリックスの要素を再生するために取り出される。ビットプレーンのある位置に１が記憶されているならば、値は記憶されていない。値が記憶されていない場合には、原画像マトリックスを再生するために、ビットプレーンに関連付けられている相関値が現在の要素の値を決定するため前の要素に加算される。
【００４４】
図１の実施形態を再度使用すると、復号化されたデータは次の通りである。
【表１２】
2009516985.tif 000014
【００４５】
復号化後：
【表１３】
2009516985.tif 000015
【００４６】
図４を参照して、画像の画像データ４０１を圧縮する典型的なシステム４００が記載されている。各要素と前の要素との間の差はシステム４００によって計算される。システム４００は、一般的に、比較モジュール４１０及びエンコーダ４２０を備える。比較モジュール４１０は、差を所定の相関値と比較し、差と所定の相関値とが等しいならば、第１の値がビットプレーン４３０に記録され、差と所定の相関値とが等しくないならば、第２の値がビットプレーン４３０に記録される。エンコーダ４２０は、ビットプレーン４３０内の第１の値及び第２の値をビットプレーンインデックスに変換し、画像データを圧縮する。圧縮された画像４４０及びビットプレーン４３０は記憶媒体４５０に記憶される。圧縮された画像４４０は、ユーザ４７０への画像のストリーム化を可能にさせるため、別個のタイル４６０として記憶されることがある。圧縮された画像４４０は、ビットプレーンインデックス及びビットプレーン４３０を使用して伸長され得る。
【００４７】
画像データは、静止カメラ又はビデオカメラのようなアナログ画像捕捉装置４０３から供給されることがある。この場合には、デジタル画像スキャナでもよいアナログ・デジタル変換器４０２が必要とされる。そうでなければ、画像が既にデジタル形式であるならば、画像はシステム４００の比較モジュール４１０へそのまま入力されることがある。
【００４８】
可逆システムについて説明されているが、非可逆圧縮が可能であると考えられる。１つの方法は原画像マトリックス内の反復性を高めることである。隣接画素間の差が所与の任意のスレッショルド値より小さいならば、隣接画素は同一化される。このことは、画像データ中の反復の回数をさらに増加させるので、ＲＣＣ適用後の圧縮率もまた増大させる。スレッショルドの値は特有のアプリケーション及びシステムの要件に応じて変えられ得る。スレッショルドがより高くなると、圧縮率がより良くなり、再構成された画像の品質の損失もまたより高くなる。
【００４９】
さらに、ＲＣＣ予測変換法（ＲＣＣＰ）及びＲＣＣ適応変換法（ＲＣＣＡ）が、圧縮率を高めるために本発明と一緒に使用されることがある。ＲＣＣＰ及びＲＣＣＡは、参照によって本明細書に内容が引用されているＰＣＴ／ＳＧ２００４／０００４１１に開示されている。
【００５０】
反復相関符号化は、ウェブページに、又は、ＭＭＳメッセージを用いて携帯電話機に表示される画像のようなストリーミングアプリケーションにも適用されることがある。ストリーミングアプリケーションでは、画像は、画像ソースからユーザまでネットワーク経由でストリーム化される。画像ソースは分散データベースでもよい。このアプリケーションでは、画像はより小さなタイルに分割され、各タイルは（反復相関符号化後に）圧縮形式でユーザへ送信されることがある。複数のタイルは、ネットワークの帯域幅を最大限に発揮するため複数のサーバーによって同時に送信されることがある。最初に、タイルは、インターレース方式のような所定のスキームに従って送信され、又は、画像の５つのタイル毎に１つのタイルが最初に送信され、タイルは最初に画像の中心から周辺の方へ徐々に送信される。代替的に、最初に送信されるべきタイルはランダムに選択される。送信順序は、ユーザによって遮断されるまで、このように継続する。タイルの送信は、直観的であること、かつ、対話的であることが可能であり、それによって、ユーザがズームインするか、又は、最初に検査することを望む画像の特定の部分を選択するならば、選択された部分の範囲内のタイルは、画像の他のタイルより高い優先順位で送信される。選択された部分に隣接するタイルは次の優先順位が付与され、選択された部分からなお一層離れている残りのタイルはより低い優先順位が付与される。したがって、ユーザへのタイルの送信は、ユーザの選択又は行為によって決定された優先順位に従って順序付けられる。よって、ユーザが関心を持っている画像の該当部分は、表示のために、画像が典型的に左から右、上から下へラスタ順に再生される従来の方法よりも速く再生される。従来の方法では、関心のあるエリアが画像の右下隅に位置しているならば、ユーザは送信全体が終了するまで待機しなければならない。
【００５１】
当業者によって認められるように、多数の変形及び／又は変更が、広範に記載されているような発明の範囲又は精神から逸脱することなく、特定の実施形態に明らかにされているような発明になされる。本実施形態は、したがって、あらゆる面で、例示的であり、かつ、非限定的であるとみなされるべきである。
【図面の簡単な説明】
【００５２】
【図１】カラー画像のサンプル内での８１画素領域の説明図である。
【図２】典型的なカラー画像の相関値の分布を説明するグラフである。
【図３】本発明の好ましい実施形態による反復相関符号化のプロセスフローチャートである。
【図４】本発明の好ましい実施形態による反復相関符号化のシステムアーキテクチャ図である。
【図１】
2009516985.tif 000016
【図２】
2009516985.tif 000017
【図３】
2009516985.tif 000018
【図４】
2009516985.tif 000019
【手続補正書】
【提出日】平成20年2月29日(2008.2.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画像の画像データの圧縮率を高める方法であって、
各画像要素と前の画像要素との間の相関を計算するステップと、
前記相関を所定の相関値と比較し、
前記相関と前記所定の相関値とが等しい場合、第１の値を記録し、
前記相関と前記所定の相関値とが等しくない場合、第２の値を記録するステップと
を備える、方法。
【請求項２】
前記第１の値及び前記第２の値がビットプレーンに記録される、請求項１に記載の方法。
【請求項３】
前記第１の値が記録される場合、前記画像要素の値を記憶せず、前記第２の値が記録される場合に、前記画像要素の値を記憶する、請求項１に記載の方法。
【請求項４】
前記所定の相関値を前記ビットプレーンに関連付けるステップをさらに備える、請求項２に記載の方法。
【請求項５】
前記所定の相関値が−８から＋８までの値である、請求項１に記載の方法。
【請求項６】
別個のビットプレーンが使用される所定の相関値毎に前記差の比較を繰り返すステップをさらに備える、請求項５に記載の方法。
【請求項７】
前記第１の値が１であり、前記第２の値が０である、請求項１に記載の方法。
【請求項８】
前記画像要素の各々が画素である、請求項１に記載の方法。
【請求項９】
前記画像要素の各々を前の画像要素と比較し、当該画像要素と前記前の画像要素が互いの所定のレンジに収まる場合、前記前の画像要素と等しくなるように当該画像要素を修正する初期ステップをさらに備え、
前記画像の非可逆圧縮を可能にさせるため反復性が高められる、請求項１に記載の方法。
【請求項１０】
前記比較が、左から右へ、その後に上から下へラスタ順に実行される、請求項１に記載の方法。
【請求項１１】
前記比較が、垂直と対角とから構成される群のうちの一方であり、非ラスタ順に実行される、請求項１に記載の方法。
【請求項１２】
反復符号化圧縮法（ＲＣＣ）、反復符号化圧縮予測法（ＲＣＣＰ）、適応反復符号化法（ＲＣＣＡ）、及び、多次元反復符号化圧縮法から構成される群のうちのいずれか１つに従って前記画像データを変換するステップをさらに備える、請求項１に記載の方法。
【請求項１３】
前記画像を複数のタイルに分割するステップをさらに備える、請求項１に記載の方法。
【請求項１４】
ネットワークを介して前記タイルをストリーム化するステップをさらに備える、請求項１３に記載の方法。
【請求項１５】
圧縮されたデータを形成するために、前記ビットプレーン内の反復をビットプレーンインデックスに符号化し、前記画像データの画像データ値を符号化するステップをさらに備える、請求項４に記載の方法。
【請求項１６】
複数のデータ要素を備えるデータの圧縮率を高める方法であって、
前記データ要素の各々と前のデータ要素との間の相関を計算するステップと、
前記相関を所定の相関値と比較し、
前記相関と前記所定の相関値とが等しい場合、第１の値を記録し、
前記相関と前記所定の相関値とが等しくない場合、第２の値を記録するステップと
を備える、方法。
【請求項１７】
各画像要素と前の画像要素との間の相関が計算される、画像の画像データを圧縮するシステムであって、
前記相関を所定の相関値と比較し、前記相関と前記所定の相関値とが等しい場合、第１の値をビットプレーンに記録し、前記相関と前記所定の値とが等しくない場合、第２の値を前記ビットプレーンに記録する圧縮モジュールと、
前記ビットプレーン内の前記第１の値及び前記第２の値をビットプレーンインデックスに符号化するエンコーダと
を備え、
前記圧縮された画像が前記ビットプレーンインデックス及び前記ビットプレーンを使用して伸長され得る、システム。
【請求項１８】
前記圧縮された画像及び前記ビットプレーンが記憶媒体に記憶され、前記圧縮された画像が前記圧縮された画像のストリーム化を可能にするため複数個のタイルとして記憶される、請求項１７に記載のシステム。
【国際調査報告】
2009516985.tif 000020
2009516985.tif 000021
2009516985.tif 000022