(57)【特許請求の範囲】
【請求項１】
装置（１０、１３０）により遂行され、第１のデータ（Ｄ１）を圧縮し、対応する圧縮された第２のデータ（Ｄ２）を生成する方法であって、
（ｉ）前記装置のコンピュータハードウェアを用いて前記第１のデータをデータブロック（１１０、ＤＢ）の構成に配置することと；
（ｉｉ）前記データブロック（１１０、ＤＢ）を記述する１つ以上のパラメータを計算すること、ただし前記１つ以上のパラメータは、前記データブロック（１１０、ＤＢ）のサブ部分を記述する複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）を有し、該複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）は、ＭＡＲ（振幅比の平均）、平均、標準偏差、分散、振幅、中央値、最頻値、最小値、最大値、ＣＲＣ、ハッシュ、レベル量の少なくとも１つを含む、前記計算することと；
（ｉｉｉ）前記１つ以上のパラメータに関連するカテゴリに基づいて、１つ以上のデータベースを検索し、検索された要素（１２０、Ｅ）と前記データブロック（１１０、ＤＢ）とをマッチングさせること、但し前記データブロック（１１０、ＤＢ）は、前記対応する要素（１２０、Ｅ）に、前記複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）を利用することによって対応させられることと；
（ｉｖ）マッチングした前記データブロックと前記要素に対し、参照値（Ｒ）を含むデータセットを生成すること、前記参照値は前記要素を識別し、かつ、前記カテゴリを含む、前記生成することと；
（ｖ）前記カテゴリを含む前記参照値を含む前記データセット含めて、前記圧縮された第２のデータを生成することと；
を含むことを特徴とする方法。
【請求項２】
前記（ｉｉｉ）において、１つ以上の変換が適用される前記データブロック（ＤＢ）に対して検索が行われ、前記１つ以上の変換を示す情報が、前記圧縮された第２のデータに含められることを特徴とする、請求項１に記載の方法。
【請求項３】
前記１つ以上の変換は、反転変換、回転変換、拡大縮小変換、並べ替え変換の少なくとも１つを含むことを特徴とする、請求項１または２に記載の方法。
【請求項４】
前記データブロックおよび前記要素の形状を記述する１つ以上のパラメータの関数によって、前記データブロックを対応する要素（Ｅ、１２０）にマッチングさせることを特徴とする、請求項１から３のいずれかに記載の方法。
【請求項５】
前記第１のデータを圧縮し、前記第１のデータは、音声データ、動画データ、画像データ、グラフィクスデータ、地震データ、心電図（Electrocardiogram：ＥＣＧ）測定データ、数字データ、文字データ、テキストデータ、Ｅｘｃｅｌタイプの表データ、ＡＳＣＩＩデータ、Ｕｎｉｃｏｄｅ文字データ、バイナリデータ、ニュースデータ、コマーシャルデータ、多次元データの少なくとも１つを含むことを特徴とする、請求項１から４のいずれかに記載の方法。
【請求項６】
関連付けられた前記パラメータ（ｐ１、ｐ２、…）は、反転変換、回転変換、拡大縮小変換、並べ替え変換の少なくとも１つを記述することを特徴とする、請求項１から５のいずれかに記載の方法。
【請求項７】
前記複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）を、複数のルックアップテーブルを介して処理することによって、前記データブロックをその要素（Ｅ、１２０）とマッチングさせることを特徴とする、請求項１から６のいずれかに記載の方法。
【請求項８】
装置の処理ハードウェアによって実行されると、前記装置に、請求項１から７のいずれかに記載の方法を遂行させるように構成されるコンピュータ可読命令を含む、コンピュータプログラム。
【請求項９】
処理手段及び記憶手段を備える装置であって、前記記憶手段はプログラム命令を格納し、前記プログラム命令は、前記処理手段に実行されると、前記装置に、請求項１から７のいずれかに記載の方法を遂行させるように構成される、装置。
【請求項１０】
装置（３０、１３０）により遂行され、第２のデータ（Ｄ２）を伸張し、対応する伸張された第３のデータ（Ｄ３）を生成する方法であって、
（ｉ）前記第２のデータから、カテゴリを含む１つ以上の参照値（Ｒ）を抽出すること、ただし前記カテゴリは、データブロック（１１０、ＤＢ）を記述する１つ以上のパラメータに関し、前記１つ以上のパラメータは、前記データブロック（１１０、ＤＢ）のサブ部分を記述する複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）を有し、該複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）は、ＭＡＲ（振幅比の平均）、平均、標準偏差、分散、振幅、中央値、最頻値、最小値、最大値、ＣＲＣ、ハッシュ、レベル量の少なくとも１つを含む、前記抽出することと；
（ｉｉ）前記１つ以上の参照値に対応する１つ以上の要素（Ｅ、１２０）に関する前記カテゴリを利用することと；
（ｉｉｉ）前記（ｉｉ）からの前記カテゴリに当てはまる前記１つ以上の要素のうち、前記参照値により識別される要素を照合して、対応するデータブロック構成（ＤＢ、１１０）を生成することと；
（ｉｖ）前記（ｉｉｉ）からの前記データブロック構成を含む前記伸張された第３のデータを出力する、
ことを特徴とする方法。
【請求項１１】
前記第２のデータを伸張し、前記第２のデータは、音声データ、動画データ、画像データ、グラフィクスデータ、地震データ、心電図（Electrocardiogram：ＥＣＧ）測定データ、数字データ、文字データ、テキストデータ、Ｅｘｃｅｌタイプの表データ、ＡＳＣＩＩデータ、Ｕｎｉｃｏｄｅ文字データ、バイナリデータ、ニュースデータ、コマーシャルデータ、多次元データの少なくとも１つを含むことを特徴とする、請求項１０に記載の方法。
【請求項１２】
関連付けられたパラメータ（ｐ１、ｐ２、…）は、反転変換、回転変換、拡大縮小変換、並べ替え変換の少なくとも１つを記述することを特徴とする、請求項１０または１１に記載の方法。
【請求項１３】
装置の処理ハードウェアによって実行されると、前記装置に、請求項１０から１２のいずれかに記載の方法を遂行させるように構成されるコンピュータ可読命令を含む、コンピュータプログラム。
【請求項１４】
処理手段及び記憶手段を備える装置であって、前記記憶手段はプログラム命令を格納し、前記プログラム命令は、前記処理手段に実行されると、前記装置に、請求項１０から１２のいずれかに記載の方法を遂行させるように構成される、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、データを圧縮し、対応する圧縮データを生成する装置に関する。本開示は、前述の装置を用いてデータを圧縮し、対応する圧縮データを生成する方法にも関する。また本開示は、前述の装置を備えるシステムおよびコーデック、ならびに圧縮データを伸張して対応する伸張データを生成する、対応する装置に関する。さらに本開示は、前述の方法を実行するために、処理ハードウェアを備えるコンピュータ装置によって実行可能なコンピュータ可読命令が格納された非一時的コンピュータ可読格納媒体を含む、コンピュータプログラム製品にも関する。前記データは、取り込まれた画像データ、音声データ、動画データ、グラフィクスデータ、測定データ、センサデータ、デオキシリボ核酸（Deoxyribo Nucleic Acid：ＤＮＡ）データ、ゲノムデータなどに関するが、これらに限定されない。
【背景】
【０００２】
データ圧縮はよく知られた技術であり、データの通信時に消費される通信ネットワークリソースや、データの格納時に消費されるデータ格納容量を削減することを可能にする。データ圧縮は、データ圧縮を適用しても情報が失われない場合は可逆圧縮、または、データ圧縮を適用するとある程度の情報が失われる場合は非可逆圧縮とすることができる。ソースデータを圧縮して対応する圧縮データを生成する際は、多くの場合、そのソースデータの１つ以上の部分を表す１つ以上の要素（Ｅ）を用いると有利である。これには例えば、対応する１つ以上の要素（Ｅ）を一意に定義する１つ以上の参照コード（Ｒ）を用いる。
【０００３】
非常に高度なデータ処理方法が米国特許出願第１３／７１５，４０５号に記載されている。この方法を用いると、多数の様々なデータベースおよびデータベース要素（Ｅ）を用いて、ソースデータ内に存在するあらゆる種類のデータブロックを圧縮できる。しかしながら、このような高度な方法に、例えば、データベース要素の形状に関わる課題に関する改良などの、さらなる改良を加えることが可能である。米国特許出願第１３／７１５，４０５号に記載のデータ生成器について、１つのルックアップテーブルを用いて、静的データベースまたは動的データベースのデータベース要素からデータブロックを、より高速に検索する方法が記載されている。
【０００４】
既知のデータベースは、ソースデータ内に存在するすべての異なる種類のデータブロックの処理には効率的に用いられないことが多い。例えば、データベース内の参照をカテゴリ分けするのに可能な方法がない場合、データベース内の検索が低速になる。既知のデータベース参照機構では、参照のカテゴリ分けに、適切な構成要素を用いることができないことが多い。例えば、大量のデータブロック値を比較することなく類似の形状を検索できるように、ソースデータ内に存在するデータブロックの形状を記述する、といったことがなされない。また、既知のデータベースに検索すべき構成要素が多数含まれている場合、そのデータベース上で実行されるデータブロック検索が非常に低速になり、かなり大量の計算リソースを要する。一方、データベースに少数の選択された構成要素しか含まれていない場合、十分な量の異なるデータブロックを用いて高品質なデータ圧縮を行うことができない。
【０００５】
さらに生じる問題として、データブロックに関して検索を実行するために、データベースのサイズを最適化する必要がある。従来の既知のデータベースに含まれる任意のデータは、そのデータベース内の他のデータと密接に関連していることが多く、それらすべての検索が必要になる可能性がある。
【０００６】
英国特許公開公報第２３６２０５５号（Clearstream Tech Ltd.）（「Image Compression using a Codebook」（符号表を用いた画像圧縮））には、画像データを処理する装置が記載されている。この装置は、受信画像を、画素を含む複数のデータブロックに分割する構成を備える。またこの装置は、相互に異なる所定の組合せの画素を含む複数のデータブロックを格納する符号表構成を備える。符号表において、各組み合わせは対応する一意の識別データに関連付けられる。さらにこの装置は、画像の各データブロックと格納されたデータブロックを比較して、画像のデータブロック内の画素の組合せと実質的にマッチングする画素の組み合わせを符号表構成から識別する構成を備える。また、マッチングする組み合わせに関連付けられた一意の識別データを出力する構成も備える。動作としては、この装置は符号表構成内で、格納されている各データブロックを検索する必要がある。この動作は、符号表構成に大量のデータブロックが格納されている場合は特に、計算集約的でリソースを消費するタスクとなる。
【０００７】
米国特許公開公報第５８３８８３３号（Minolta Co. Ltd.）（「Fractal image compression method and device, and fractal image restoration method and device」（フラクタル画像の圧縮方法および装置、およびフラクタル画像の復元方法および装置））には、画像をデータブロックに分割し、データブロック間の相似性を検出することによってデータブロックを符号化して圧縮する画像圧縮方法を用いる装置が記載されている。前述の相似性検出において、画像にエッジがある場合はデータブロックのサイズを変更してデータブロックを比較することで、相似性検出すなわち比較の速度を向上させる。画像のデータブロックは、画像の他の部分ではなく事前に格納された画像パターンと比較される。これには圧縮データではなく生データが用いられる。さらに、最相似領域を可能なかぎり高速に検出する可能性を高めるために検査領域が用いられる。
【０００８】
米国特許公開公報第５８３８８３３号に記載されている方法は、フラクタルを利用して画像を符号化するように設計されていることを理解されたい。そのため、採用されているシステムは実際にはデータベースを備えておらず、代わりに、符号化する画像の内容に基づいて変域ブロックから動的な「データベース」を生成する。この際、ブロックの符号化において、生成された同じ変域ブロックが、同じ画像の他の領域にも用いられるようにする。米国特許公開公報第５８３８８３３号はデータブロックに言及しており、本開示の実施形態とはやや異なる。米国特許公開公報第５８３８８３３号は動画やその他のタイプのデータには言及しておらず、前の画像の変域ブロックを次の画像の符号化に用いることができると示唆してもいない。また、記載されているシステムにおいて静的データベースは用いられない。
【０００９】
これらの先行技術文献に採用されている技術は、例えば移動通信装置内の、少ないコンピューティングリソースを用いて画像データなどのデータを高解像度に符号化する際の効果が不十分である。
【摘要】
【００１０】
本開示は、改良された方法でデータを圧縮し、対応する圧縮データを生成するように動作する装置を提供することを目的とする。
【００１１】
また本開示は、改良された方法でデータを圧縮し、対応する圧縮データを生成する方法を提供することを目的とする。
【００１２】
第１の態様によると、第１のデータ（Ｄ１）を圧縮して、対応する圧縮された第２のデータ（Ｄ２）を生成する装置であって、
（ｉ）前記第１のデータ（Ｄ１）をデータブロック構成に配置し、
（ｉｉ）前記データブロック（１１０、ＤＢ）を記述する１つ以上のパラメータを計算し、前記１つ以上のパラメータに関連するカテゴリに基づいて、１つ以上のデータベースおよび／またはデータベース要素を検索し、前記１つ以上のデータベース（１３０）内で、前記データブロック（１１０、ＤＢ）と対応する要素（１２０、Ｅ）をマッチングさせ、
（ｉｉｉ）マッチングした前記データブロック（ＤＢ）と前記要素（Ｅ）に対し、参照値（Ｒ）を含むデータセットを生成し、前記参照値（Ｒ）は前記要素（Ｅ）を識別し、かつ、前記カテゴリまたは前記カテゴリに関する情報を含み、
（ｉｖ）前記カテゴリまたは前記カテゴリに関する情報を含む前記参照値（Ｒ）を含めて、前記圧縮された第２のデータ（Ｄ２）を生成する、
ように動作するデータ処理構成を備えることを特徴とする装置が提供される。
【００１３】
本発明は、例えばエンコーダとして実装される装置が、要素（Ｅ）をデータブロック（ＤＢ）にマッチングさせる際に、カテゴリ情報や「ゲートゴリ（gategory）」情報などの個別の情報を用いるように動作することで、例えば、要素Ｅのデータベースを小規模にできることによって、マッチングのための検索をより効率的にするものである。
【００１４】
本発明において、この検索はカテゴリを利用して実行される。またこの検索は、後述するように、データベース要素のカテゴリをデータブロックにマッチングさせるために必要な変換に基づいて実行することもできる。カテゴリと変換の両方は、符号化された圧縮データを提供する際に含めることができる。カテゴリを用いるとマルチレベルの検索プロセスになり、パフォーマンスが向上する、すなわち、カテゴリを用いることで高速に検索を行い、その後、検索されたカテゴリに基づいて任意のデータブロック（ＤＢ）の検索を行う。要素のマッチングは任意の従来の方法を用いて行うことができるが、カテゴリ分けを行うだけで、マッチングさせるのに十分である場合がある。
【００１５】
検索するデータベースは、静的データベースおよび／または動的データベースであることを理解されたい。静的データベースは、その要素、すなわちデータブロックが、相互に同様の方法で常に決定および／または計算されるデータベースである。すなわち、その要素は、要求され動作に用いられるタイミングに関係なく、不変である。換言すると、同じインデックスおよび同じパラメータを用いて任意の同じ静的データベース内で検索を実行すると、要求に対して、常に対応する同じ要素、すなわちデータブロックが受信される。これに対し、動的データベースは、包含する要素を交換可能および／または新しい要素を追加可能である。このため、要素が要求されるタイミングに応じて、動的データベース内で実行される検索では非常に異なる要素、すなわちデータブロックが検出されることがある。これは動的データベースが検索されるタイミングによって異なる。このことは、本開示の実施形態によると、データブロックを記述するパラメータであって、それに基づいてデータベースとその要素をカテゴリ分けできるパラメータの計算が、静的データベース内では１回のみ行われ、動的データベース内では連続的に行われることを意味する。これは、動的データベース内のデータベース要素が変更されるためである（要素を追加および削除可能）。
【００１６】
また、任意の要素を要求する際に用いられるパラメータは、任意の要素と共に用いられる１つ以上の変換に関する情報を含んでもよいことも理解されたい。さらに、データベース要素への参照に、対応して用いられるカテゴリおよび／または用いられる変換の情報を含めてもよい。カテゴリを用いると、前述のとおり、より小規模のデータベースを用いることが可能になる。あるいは、あるデータブロックの例では、データベースカテゴリを有利にも用いて、特定のデータベース内で任意のデータブロックを検索する必要があるかどうかを決定するための高速な検査が可能になる。
【００１７】
任意のデータブロックのカテゴリ、および任意のデータベースまたはその個々の要素のカテゴリを利用すると、その任意のデータブロックの検索に有利にも用いられる変換の種類に関する情報を、１つ以上の特定のデータベース要素と共に、高速に受信できる。適切な変換が特定されたら、任意のデータブロックに対する残りの検索を、より効率的かつ集中的に行うことができ、それによって、必要とされる全体的な計算タスクが削減される。
【００１８】
動的データベースは、静的データベースからの要素を含むように作成することもできる。この場合、通常は、元の静的データベース参照に必要なビット数より少ないビット数で、動的データベース参照を表現することができる。これに対応して、動的データベースの最新バージョンを後で一時的に再利用したい場合に、その動的データベースに基づいて新しい静的データベースを作成できる。動的データベースから静的データベースを作成する際、動的データベースの既存の参照を変更しないで保つことができる。あるいは、例えば、カテゴリ分けおよび／またはより高速な検索のために、動的データベースの要素を再配置することもできる。再配置する場合、それらの要素の新しい参照が有利にも発行される。
【００１９】
任意のデータブロックの符号化において、データベース符号化法に加えて他の符号化方法も用いることができる。他の方法の例として、直流（Direct Current：ＤＣ）（オフセット）、離散コサイン変換（Discrete Cosine Transform：ＤＣＴ）、スライド、ライン、内挿法、外挿法、マルチレベル符号化、予測法、デルタベースの方法などがある。また、これらすべての符号化方法は、そのままで用いることも、追加情報、すなわち、残差情報などの補助情報と共に用いることもできる。符号化されるデータブロック同士のサイズおよび形状は異なってもよいことを理解されたい。データブロックのサイズおよび形状は、エンコーダに対応するデコーダに既知であっても、エンコーダが、例えば分割／結合ビット、および／または座標、および／または他の何らかの関連する情報と共に、ブロック、そのサイズおよび形状に関する情報を提供してもよい。
【００２０】
データベース内で最適なデータベース要素を検索する際、または、任意のデータブロックの最適な符号化方法を計算する際、その選択は、例えば、レート歪み（Rate Distortion：ＲＤ）値に基づいてもよい。ＲＤ値を用いて、例えば２×２、１６×１６、６４×６４などの異なるサイズのデータブロックの符号化結果同士を比較し、そのデータブロックの符号化に用いるのに最適な選択肢を見つけることができる。ＲＤ値は、以下の式１に示すように計算すると有利である。
［式１］
ＲＤ＝Ｄ＋Ｒ＊Ｌ
式中の記号の意味は次のとおりである。
Ｌ＝    ラグランジェ乗数
Ｄ＝    元のデータブロックと、対応する復号化データブロックとの間の歪みＤ（例えば差の絶対値の和（Sum of Absolute Difference：ＳＡＤ）、差の二乗の和（Sum of Squared Difference：ＳＳＤ））
Ｒ＝    方法またはデータベース要素によって用いられるデータサイズＲ
【００２１】
ラグランジェ乗数「Ｌ」の値は、符号化に対して望まれる品質の程度によって異なる。ラグランジェ乗数が小さいと、高い再構築品質に有利であるが、エンコーダから対応するデコーダに送信されるデータのサイズが大きくなる。ラグランジェ乗数が大きいと、小さいサイズのデータの送信に有利であるが、デコーダにおいて再構築される出力の品質が低下する。任意のデータブロックに対して得られるＲＤ値が小さいほど、その要素または符号化方法は元のデータブロックによりよく対応し、用いられる符号化ビットが可能なかぎり少なくなる。
【００２２】
しかしながら、エンコーダからデコーダにデータを伝達する際に可逆的な符号化が必要とされる場合、歪みは許容されない。可逆的な符号化では、データサイズ「Ｒ」値のみに基づいて選択が行われ、任意のデータブロックを完全に可逆的再構築する要素または方法のみが、符号化計算において用いられる。選択の基準にデータサイズ「Ｒ」値だけが用いられる場合、対応する元のデータブロックと同一のデータブロックを再構築でき、かつ、エンコーダから対応するデコーダに伝達される符号化ビットの量を最小にしてそれを行うことができる、特定の要素または方法が選択される。
【００２３】
本発明は、データブロックの個別のコピー、例えば反転されたコピーや回転されたコピーをデータベースに格納する必要ない場合、例えばエンコーダとして実装される装置に用いられるデータベースがさらに最適化されるという点で、さらに有利である。つまり、データベース内に格納する必要があるデータベース要素の量が少なくなり、これらのデータベース要素から、より多くのデータブロックを検出および再構築することが可能になる。このようなブロックの変換の例として、添付の図５Ａから図５Ｅを参照されたい。
【００２４】
前記（ｉｉ）において前記装置は、前記データブロック（ＤＢ）および前記要素（Ｅ）の形状を記述する１つ以上のパラメータの関数として、前記データブロック（ＤＢ）を対応する要素（Ｅ）にマッチングさせるように動作してもよい。形状、平均、標準偏差、否定、平均の加算／減算、標準偏差の加算／減算などのカテゴリに基づく検索を成功させるために、前記ブロックに用いる１つ以上の変換を検索して決定することも有利である。
【００２５】
前記装置は前記第１のデータ（Ｄ１）を圧縮するように動作し、前記第１のデータ（Ｄ１）は、音声データ、動画データ、画像データ、グラフィクスデータ、地震データ、心電図（Electrocardiogram：ＥＣＧ）データ、測定データ、数字データ、文字データ、テキストデータ、Ｅｘｃｅｌタイプの表データ、ＡＳＣＩＩまたはＵｎｉｃｏｄｅ文字データ、バイナリデータ、ニュースデータ、コマーシャルデータ、多次元データ、デオキシリボ核酸（Deoxyribo Nucleic Acid：ＤＮＡ）データ、ゲノムデータなどの少なくとも１つを含んでもよい。前記第１のデータ（Ｄ１）は、例えば、１つ以上のセンサによって生成されてもよく、前記データ（Ｄ１）が、光の空間分布および／または角分布や、遺伝生物学的物質における原子グループの配置などの実際の物理的変数を表してもよい。
【００２６】
前記装置の動作において、関連付けられた前記パラメータ（ｐ１、ｐ２、…）は、反転変換、回転変換、拡大縮小変換、並べ替え変換、否定変換、平均の加算／減算／乗算／除算を伴う変換、標準偏差の加算／減算／乗算／除算を伴う変換、否定変換、平均変換の加算／減算、標準偏差変換の加算／減算の少なくとも１つを記述してもよい。平均を加算または減算するデータベースの例として、その要素がゼロ平均となるように生成されているデータベースが挙げられる。これらのデータベース要素は、対応する形状を含むデータブロックの符号化に容易に用いることができる。そのデータブロックの元の値の平均が大きいか小さいかにかかわらず、要素の参照とその要素の平均値のみを送信すればよい。乗算および除算を用いると、振幅の影響をブロックから容易に排除できる。これにより、特定の形状の複数のデータブロックは、データベース内で１回のみ検出すればよい。デコーダにおける対応する復号化プロセス内で、すなわち、デコーダにおいて画像が再構築される際に、回転や鏡像化などを用いることによって、この同じ形状のデータを別の向きへと移動させることができるためである。
【００２７】
前記装置は、前記データブロック（ＤＢ）および／または前記要素（Ｅ）のサブ部分を記述する複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）を利用し、前記複数のパラメータ（Ａ１、Ａ２、…、ＡＮ）を用いてマッチングを行うことによって、前記データブロック（ＤＢ）をその要素（Ｅ）とマッチングさせるように動作してもよい。また、前記装置は、前記複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）を、複数のルックアップテーブル（Look-Up Table：ＬＵＴ）を介して処理することによって、前記データブロック（ＤＢ）をその要素（Ｅ）とマッチングさせるように動作してもよい。さらに、前記装置は、前記要素（Ｅ）およびその関連付けられた参照値（Ｒ）を用いることで、前記データブロック（ＤＢ）を表現するために必要であって前記データブロック（ＤＢ）および／または前記要素（Ｅ）に適用可能な１つ以上の変換に実質的に関係なく、前記データブロック（ＤＢ）をその要素（Ｅ）とマッチングさせるように動作してもよい。複数の変換を前記データブロック（ＤＢ）に適用可能であってもよい。
【００２８】
前記装置の動作において、前記複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）は、ＭＡＲ（振幅比の平均）、平均、標準偏差、分散、振幅、中央値、最頻値、最小値、最大値、ＣＲＣ、ハッシュ、レベル量などの少なくとも１つを含んでもよい。
【００２９】
第２の態様によると、第１のデータ（Ｄ１）を圧縮して、対応する圧縮された第２のデータ（Ｄ２）を生成する方法であって、
（ｉ）前記装置のコンピュータハードウェアを用いて前記第１のデータ（Ｄ１）をデータブロック構成（ＤＢ）に配置し、
（ｉｉ）前記データブロック（１１０、ＤＢ）を記述する１つ以上のパラメータを計算し、前記１つ以上のパラメータに関連するカテゴリに基づいて、１つ以上のデータベースおよび／またはデータベース要素を検索し、前記１つ以上のデータベース（１３０）内で、前記データブロック（１１０、ＤＢ）と対応する要素（１２０、Ｅ）をマッチングさせ、
（ｉｉｉ）マッチングした前記データブロック（ＤＢ）と前記要素（Ｅ）に対し、参照値（Ｒ）を含むデータセットを生成し、前記参照値（Ｒ）は前記要素（Ｅ）を識別し、かつ、前記カテゴリまたは前記カテゴリに関する情報を含み、
（ｉｖ）前記カテゴリまたは前記カテゴリに関する情報を含む前記参照値（Ｒ）を含めて、前記圧縮された第２のデータ（Ｄ２）を生成する、
ことを特徴とする方法が提供される。
【００３０】
前記方法は、前記データブロック（ＤＢ）および前記要素（Ｅ）の形状を記述する１つ以上のパラメータの関数として、前記データブロック（ＤＢ）を対応する要素（Ｅ）にマッチングさせてもよい。
【００３１】
前記方法は、前記第１のデータ（Ｄ１）を圧縮し、前記第１のデータ（Ｄ１）は、音声データ、動画データ、画像データ、グラフィクスデータ、地震データ、ＥＣＧデータ、測定データ、数字データ、文字データ、テキストデータ、Ｅｘｃｅｌタイプの表データ、ＡＳＣＩＩまたはＵｎｉｃｏｄｅ文字データ、バイナリデータ、ニュースデータ、コマーシャルデータ、多次元データ、ＤＮＡデータ、ゲノムデータなどの少なくとも１つを含んでもよい。
【００３２】
前記方法において、関連付けられた前記パラメータ（ｐ１、ｐ２、…）は、反転変換、回転変換、拡大縮小変換、並べ替え変換の少なくとも１つを記述してもよい。
【００３３】
前記方法は、前記データブロック（ＤＢ）および／または前記要素（Ｅ）のサブ部分を記述する複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）を利用し、前記複数のパラメータ（Ａ１、Ａ２、…、ＡＮ）を用いてマッチングを行うことによって、前記データブロック（ＤＢ）をその要素（Ｅ）とマッチングさせてもよい。また、前記方法は、前記複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）を、複数のルックアップテーブルを介して処理することによって、前記データブロック（ＤＢ）をその要素（Ｅ）とマッチングさせてもよい。さらに、前記方法は、前記要素（Ｅ）およびその関連付けられた参照値（Ｒ）を用いることで、前記データブロック（ＤＢ）を表現するために必要であって前記データブロック（ＤＢ）および／または前記要素（Ｅ）に適用可能な１つ以上の変換に実質的に関係なく、前記データブロック（ＤＢ）をその要素（Ｅ）とマッチングさせてもよい。さらに、前記方法において、前記複数のサブ部分パラメータ（Ａ１、Ａ２、…、ＡＮ）は、ＭＡＲ（振幅比の平均）、平均、標準偏差、分散、振幅、中央値、最頻値、最小値、最大値、ＣＲＣ、ハッシュ、レベル量などの少なくとも１つを含んでもよい。
【００３４】
第３の態様によると、第２の態様に従う方法を実行するために、処理ハードウェアを備えるコンピュータ装置によって実行可能なコンピュータ可読命令が格納された非一時的コンピュータ可読格納媒体を含む、コンピュータプログラム製品が提供される。
【００３５】
第４の態様によると、第２のデータ（Ｄ２）を伸張して、対応する伸張された第３のデータ（Ｄ３）を生成する装置であって、
（ｉ）前記第２のデータ（Ｄ２）から、カテゴリまたは前記カテゴリに関する情報を含む１つ以上の参照値（Ｒ）を抽出し、
（ｉｉ）前記１つ以上の参照値（Ｒ）に対応する１つ以上の要素（Ｅ）に関する前記１つ以上のカテゴリを利用し、
（ｉｉｉ）前記（ｉｉ）からの前記１つ以上のカテゴリに当てはまる前記１つ以上の要素（Ｅ）を照合して、対応するデータブロック構成（ＤＢ）を生成し、
（ｉｖ）前記（ｉｉｉ）からの前記データブロック構成（ＤＢ）を含む前記伸張された第３のデータ（Ｄ３）を出力する、
ように動作するデータ処理構成を備えることを特徴とする装置が提供される。
【００３６】
前記装置は前記第２のデータ（Ｄ２）を伸張するように動作し、前記第２のデータ（Ｄ２）は、音声データ、動画データ、画像データ、グラフィクスデータ、地震データ、ＥＣＧデータ、測定データ、数字データ、文字データ、テキストデータ、Ｅｘｃｅｌタイプの表データ、ＡＳＣＩＩまたはＵｎｉｃｏｄｅ文字データ、バイナリデータ、ニュースデータ、コマーシャルデータ、多次元データ、ＤＮＡデータ、ゲノムデータなどの少なくとも１つを含んでもよい。
【００３７】
前記装置の動作において、関連付けられたパラメータ（ｐ１、ｐ２、…）は、反転変換、回転変換、拡大縮小変換、並べ替え変換の少なくとも１つを記述してもよい。
【００３８】
第５の態様によると、装置を用いて、第２のデータ（Ｄ２）を伸張して、対応する伸張された第３のデータ（Ｄ３）を生成する方法であって、
（ｉ）前記第２のデータ（Ｄ２）から、カテゴリまたは前記カテゴリに関する情報を含む１つ以上の参照値（Ｒ）を抽出し、
（ｉｉ）前記１つ以上の参照値（Ｒ）に対応する１つ以上の要素（Ｅ）に関する前記１つ以上のカテゴリを利用し、
（ｉｉｉ）前記（ｉｉ）からの前記１つ以上のカテゴリに当てはまる前記１つ以上の要素（Ｅ）を照合して、対応するデータブロック構成（ＤＢ）を生成し、
（ｉｖ）前記（ｉｉｉ）からの前記データブロック構成（ＤＢ）を含む前記伸張された第３のデータ（Ｄ３）を出力する、
ことを特徴とする方法が提供される。
【００３９】
前記方法は、前記第２のデータ（Ｄ２）を伸張し、前記第２のデータ（Ｄ２）は、音声データ、動画データ、画像データ、グラフィクスデータ、地震データ、ＥＣＧデータ、測定データ、数字データ、文字データ、テキストデータ、Ｅｘｃｅｌタイプの表データ、ＡＳＣＩＩまたはＵｎｉｃｏｄｅ文字データ、バイナリデータ、ニュースデータ、コマーシャルデータ、多次元データ、ＤＮＡデータ、ゲノムデータなどの少なくとも１つを含んでもよい。
【００４０】
前記方法において、関連付けられたパラメータ（ｐ１、ｐ２、…）は、反転変換、回転変換、拡大縮小変換、並べ替え変換の少なくとも１つを記述してもよい。
【００４１】
第６の態様によると、第５の態様に従う方法を実行するために、処理ハードウェアを備えるコンピュータ装置によって実行可能なコンピュータ可読命令が格納された非一時的コンピュータ可読格納媒体を含む、コンピュータプログラム製品が提供される。
【００４２】
比較的小さい複数のルックアップテーブル（ＬＵＴ）を用いて、データブロックを、データベース内の対応するデータベース要素へと効果的に指し示す、例えば関連付けできることは、既知ではないことを理解されたい。ルックアップテーブルでは、用いられるデータベース要素の検索参照に、より大きな値のセットが使用される、すなわち、すべての部分参照を合わせると大量のビットが使用されるが、このような手法を用いると、データメモリ内に格納される１つ以上のルックアップテーブルのサイズを削減できる。
【００４３】
また、本発明は、同じデータベース要素（Ｅ）を異なる複数のデータブロックに用いることを可能にする。これは、データベース要素の形状情報とマッチングさせるために、可能であれば任意のデータブロックを最初に鏡像化、反転、または並べ替えした場合でも可能である。このような鏡像化、反転、または並べ替えは、その任意のデータブロックを記述する１つ以上の前述のパラメータによって識別されると有利である。
【００４４】
本発明は、データベース要素（Ｅ）をより容易に区別可能にする一方で、類似する形状を有する類似度の高い複数のデータブロックをデータベース要素によって表現することを可能にする。データベース要素（Ｅ）の形状およびデータブロック（ＤＢ）の形状の利用により、任意のデータベース内で精度と速度の高いデータブロック検索を行うことが可能になる。形状情報もデータベース参照に関して格納する場合、データベースブロックは常に一意に用いられることが望ましく、それによって再構築が正確になる。
【００４５】
また、本発明は、データベース参照に関して、データベース要素（Ｅ）、すなわちデータブロック（ＤＢ）の形状を記述する方法を提供する。これによって、データベース要素（Ｅ）がより容易に区別可能になり、データベース内の検索がより高速かつ正確になる。形状情報を含むデータベース参照によってデータベースからデータブロックを検索すると、形状情報を含まない参照によってデータベースからデータブロックを検索する場合と比べて、多くの要素（Ｅ）を並行してチェックする必要がなくなる。そのため、形状情報を含むデータベース要素（Ｅ）すなわちデータブロックは、データベースにおいてより適切である。
【００４６】
さらに、ブロックの内容が不完全な場合でも、形状が他の要素と類似する要素（Ｅ）は、異なる形状を有する要素より有利である。データベース要素の形状は、１つ以上の部分ブロック参照要素を用いて、ブロックに対して指定できると有利である。同じデータベース要素（Ｅ）を鏡像化、反転、回転、または並べ替えしたバージョンを用いることも可能である。これによって、データベースを格納するために必要なメモリ量を削減する一方で、大量の異なるデータベース要素（Ｅ）を利用可能にすることができる。また、各データベース要素に固有のデータ値を含めることができ、これによって、符号化、すなわち圧縮される情報のタイプに対してより適切な内容を含めることができる。
【００４７】
本発明は、比較的少数のデータベース要素によって多数のありうる再構築ブロックを表現することを可能にする。また、本発明は、形状を記述するサブブロック内の情報を用いて、類似の参照値を有するデータブロックの区別を容易にする方法も提供する。サブブロック内のこの形状情報によって、データベース内におけるデータブロック検索が高速になる。形状情報は、参照値（Ｒ）に含めて直接、または修正して提供してもよい。データベース要素（Ｅ）を検索する際、前述のとおり、データブロック（ＤＢ）の形状、平均、標準偏差などのカテゴリを利用して検索を実行すると有利である。形状情報によって、任意のデータブロックが、対応する可能性のあるデータベース要素に十分に類似しているかを検証するために必要なデータ値比較に必要とされるデータ値の数が削減される。この比較は依然として必要なこともあるが、データブロック内のサブブロックおよびデータブロック要素に基づく形状情報を利用できない既知の方法に比べて、比較されるデータベース要素の量は大幅に削減される。
【００４８】
前述のとおり、データベースを用いて、本開示の実施形態に用いられる多くの異なる方法の実行を高速にすることができる。例えば、データベースは、音声認識、楽譜認識またはテキスト認識（光学式文字読み取り装置（Optical Character Reader：ＯＣＲ）、例えば、塩基対に関するゲノム研究、エコー除去、ファントム画像の除去、画像からの余分なオブジェクトの除去におけるパターン認識などに用いることができる。また、これらの方法は、例えば画素撮像センサ、電気泳動リボ核酸（Ribonucleic Acid：ＲＮＡ）またはＤＮＡ読み出し装置などの、１つ以上のセンサを用いて取得されるデータに有利に適用される。
【００４９】
ここで、例えばファントム画像や余分なオブジェクトやエコーを除去する場合、そのような除去の結果として生じる対応するデータの欠損部分を、代わりのデータで置き換える必要がある。例えば、データベース参照に基づいて、画像の背景部分を用いて適切なデータを作成し、ファントム画像の除去された部分に置き換えることができる。エコー除去についても同様のことが当てはまる。この場合、エコーが除去された音声データのシーケンスには、エコーを除いた元の音声データのみが含まれる。このような除去は、例えば音声データの場合、畳み込み分析によって実行してもよい。これは、元の音声データを一時的に遅延させたまたはフィルタした一連のバージョンを重ね合わせてエコーを作成することを記述する関数を逆にしたものである。ただしこのプロセスは、画像の場合より音声データの場合のほうが、より単純である。エコーを実際に認識する必要があり、音声信号から実際に除去することができるからである。これに対し、画像から単にオブジェクトを除去することは、通常はそれほど単純ではない。それによって、オブジェクトが除去された空の領域、例えば黒い領域が生じるためである。もちろん、ある音声信号のシーケンスからある人の発話が除去されたら、その部分を例えば快適雑音や、除去後に残された何らかの音声信号によって置き換える必要がある。
【００５０】
そのような状況では、例えば、１つのデータベース要素（Ｅ）が常に１つの英数字または１つの楽譜記号に対応するようにデータベースを作成し、テキスト認識や楽譜の生成を、要素（Ｅ）への参照に直接基づいて実行できるようにする。また、多種多様な変換をデータベースと共に用いることができるため、白い背景上の暗色のテキストに、特定の状況において、黒い背景上の白いテキストと同じデータベースを用いることができる。これは、そのデータベースが否定と組み合わせて用いられる場合である。同様に、テキストが鏡像化変換を経て受信された場合、データベース内にあり、かつ鏡像化と組み合わせて用いられる形状に基づいて、そのテキストを容易に認識し、容易に符号化することができる。
【００５１】
第７の態様によると、第１のデータ（Ｄ１）を圧縮して、対応する圧縮された第２のデータ（Ｄ２）を生成する装置であって、
（ｉ）前記第１のデータ（Ｄ１）をデータブロック構成（ＤＢ）に配置し、
（ｉｉ）１つ以上のゲートゴリを用いて、１つ以上のデータベース内で、前記データブロック（ＤＢ）とマッチングする対応する要素（Ｅ）を検索し、
（ｉｉｉ）マッチングした前記データブロック（ＤＢ）と前記要素（Ｅ）に対し、参照値（Ｒ）およびそれに関連付けられたパラメータ（ｐ１、ｐ２、…）を含むデータセットを生成し、前記参照値（Ｒ）は前記要素（Ｅ）を識別し、前記パラメータ（ｐ１、ｐ２、…）は前記１つ以上のゲートゴリを定義し、
（ｉｖ）前記参照値（Ｒ）およびそれに関連付けられ、前記１つ以上のゲートゴリを定義するパラメータ（ｐ１、ｐ２、…）を含めて、前記圧縮された第２のデータ（Ｄ２）を生成する、
ように動作するデータ処理構成を備えることを特徴とする装置が提供される。
【００５２】
第８の態様によると、第２のデータ（Ｄ２）を伸張して、対応する伸張された第３のデータ（Ｄ３）を生成する装置であって、
（ｉ）前記第２のデータ（Ｄ２）から、１つ以上の参照値（Ｒ）およびそれに関連付けられ、１つ以上のゲートゴリを定義する１つ以上のパラメータ（ｐ１、ｐ２、…）を抽出し、
（ｉｉ）前記１つ以上の参照値（Ｒ）に対応する１つ以上の要素（Ｅ）に関する前記１つ以上のゲートゴリを利用し、
（ｉｉｉ）前記（ｉｉ）からの前記１つ以上のゲートゴリに当てはまる前記１つ以上の要素（Ｅ）を照合して、対応するデータブロック構成（ＤＢ）を生成し、
（ｉｖ）前記（ｉｉｉ）からの前記データブロック構成（ＤＢ）を含む前記伸張された第３のデータ（Ｄ３）を出力する、
ように動作するデータ処理構成を備えることを特徴とする装置が提供される。
【００５３】
第７の態様および／または第８の態様の装置において、前記１つ以上のゲートゴリは形状に基づき、関連付けられた１つ以上のデータブロックに関する前記１つ以上のゲートゴリは、前記１つ以上のデータブロックが回転および／または反転されても変更されないようにしてもよい。
【００５４】
本発明の特徴は、添付の特許請求の範囲に定義される本発明の範囲を逸脱しないかぎりにおいて、様々に組み合わせ可能であることを理解されたい。
【図面の簡単な説明】
【００５５】
以下、本開示における実施形態を、単なる例示として、かつ添付の図面を参照して説明する。
【００５６】
【図１】ソースデータＤ１を圧縮して対応する圧縮データＤ２を生成する第１の装置と、圧縮データＤ２を伸張して対応する伸張データＤ３を生成する第２の装置の図である。第１の装置と第２の装置を組み合わせてコーデックとして機能させることができる。
【図２】図１の第１の装置内で実行されるデータ圧縮の手順を示す図である。
【図３】図１の第２の装置内で実行されるデータ伸張の手順を示す図である。
【図４】任意の要素Ｅまたは任意のデータブロックＤＢを特徴づけて、複数の平均値などの複数の特徴パラメータを導出するために実行される、変換などの複数の計算を示す図である。この特徴パラメータは、図１の第１の装置および第２の装置において、例えば要素Ｅのグループに対してデータベース検索を実行する際に、データブロックＤＢを対応する要素Ｅとマッチングさせるために用いられる。
【図５Ａ】データベース内の要素Ｅのカテゴリ分けに形状情報を利用する様々な方法を示す図である。図５Ａは、画像の例示的データブロックを示す。
【図５Ｂ】データベース内の要素Ｅのカテゴリ分けに形状情報を利用する様々な方法を示す図である。図５Ｂは、図５Ａの例示的データブロックに、回転や鏡像化などの様々な変換を適用し、さらにサブブロックの平均ビット値および分散ビット値の例を含めたものを示す。
【図５Ｃ】データベース内の要素Ｅのカテゴリ分けに形状情報を利用する様々な方法を示す図である。図５Ｃは、画像のデータブロックの別の例を示す。
【図５Ｄ】データベース内の要素Ｅのカテゴリ分けに形状情報を利用する様々な方法を示す図である。図５Ｄは、図５Ｃの例示的データブロックに様々なサンプリングを適用し、さらにサブブロックの平均ビット値および分散ビット値の例を含めたものを示す。
【図５Ｅ】データベース内の要素Ｅのカテゴリ分けに形状情報を利用する様々な方法を示す図である。図５Ｅは、ベイヤー型、ランダム、重複などの他のサンプリングの例を示す。
【００５７】
添付図面において下線の引かれた番号は、その番号が位置するアイテムやその番号が隣接するアイテムを表すために使用される。下線が引かれていない番号は、その番号と線で結ばれて特定されるアイテムに関連している。番号に下線が引かれず矢印と共に記されている場合、その番号は矢印が指すアイテム全般を特定するために使用される。
【例示的実施形態の説明】
【００５８】
以下に本開示の実施形態の概要を示し、その後、実施形態の具体的な例を詳細に示す。図１を参照すると、データエンコーダ１０は、入力データＤ１を圧縮して対応する圧縮データＤ２を生成するように動作する。圧縮データＤ２は、符号２０で示されるデータキャリアおよび／または通信ネットワークを介してデータデコーダ３０に伝達される。データデコーダ３０は、圧縮データＤ２を伸張して対応する伸張データＤ３を生成するように動作する。入力データＤ１と伸張データＤ３は相互に実質的に類似していてもよい。エンコーダ１０とデコーダ３０は組み合わされてコーデック４０を形成する。入力データＤ１は、例えば、音声データ、動画データ、画像データ、グラフィクスデータ、地震データ、心電図（Electrocardiogram：ＥＣＧ）データ、測定データ、数字データ、文字データ、テキストデータ、Ｅｘｃｅｌタイプの表データ、ＡＳＣＩＩまたはＵｎｉｃｏｄｅ文字データ、バイナリデータ、ニュースデータ、コマーシャルデータ、多次元データ、デオキシリボ核酸（Deoxyribo Nucleic Acid：ＤＮＡ）データ、ゲノムデータなどの少なくとも１つであることが有利である。
【００５９】
エンコーダ１０において、入力データＤ１は１次元データブロックまたは多次元データブロックを用いて圧縮される。また、エンコーダ１０は、データ圧縮の実行に用いられる既知の検索手法より高速に、１つ以上のデータベース内でデータブロック検索を実行するように動作すると有利である。エンコーダ１０において実行される検索は、例えば、ＭＡＲ（Mean in Amplitude Ratio：振幅比の平均）、平均、標準偏差、分散、振幅、最頻値、中央値、最小値、最大値、インデックス、レベル量など、１つ以上のパラメータの比較に基づく。さらに、エンコーダ１０は検索された任意のデータブロックの形状を考慮すると有利である。このように、エンコーダ１０は、データブロック検索の実行中に生じるあいまいさを実質的に回避する追加の計算を実行するように構成される。対応して、デコーダ３０も同様に構成される。これについては詳細に後述する。
【００６０】
データベースを用いて、入力データＤ１内のすべてのデータブロックを符号化または圧縮し、それに応じてデコーダにおいて復号化および伸張する必要があるわけではないことを理解されたい。他の方法を、本開示に従う方法と組み合わせて用いることも可能である。他の方法には、ＤＣ変換（「直流」、すなわち一定のオフセット）、スライド法、ライン法、ＤＣＴ（離散コサイン変換）、マルチレベル法などの少なくとも１つが含まれるが、これらに限らない。本開示の実施形態を実行するには、より良いデータ圧縮率を達成するために、本開示に従う方法を用いて入力データＤ１内の少なくとも１つのデータブロックを符号化または圧縮し、それに応じてデコーダにおいて復号化および伸張すればよい。
【００６１】
巡回冗長検査（Cyclic Redundancy Check：ＣＲＣ）値およびハッシュ値の計算を利用して、データブロックを定義するための参照値の一部として用いることが可能なパラメータを生成することが知られている。しかし、そのようなパラメータはデータブロックの形状の記述にあまり適していない。データブロックは必ずしも矩形でなくてもよく、より複雑な形状であってもよいことを理解されたい。例えば、任意のデータブロックの形状を少し変更すると、完全に異なるＣＲＣ値またはハッシュ値が計算される。また、第１の任意のデータブロックおよび第２の任意のデータブロックから計算されたＣＲＣ値またはハッシュ値の差異が少なくても、第１のデータブロックと第２のデータブロック同士が類似しているというわけではない。
【００６２】
概要として、次に図２を参照すると、エンコーダ１０においてＤ１が受信され、例えばデータブロックＤＢ、１１０を含むデータブロック構成として表現される。データＤ１の符号化において、エンコーダ１０は、符号１３０によって示される１つ以上のデータベースを利用する。１つ以上のデータベース１３０において、要素Ｅ、例えば要素Ｅ、１２０は対応する参照値Ｒによって識別される。エンコーダ１０は比較構成１４０を用いて、データブロックＤＢを１つ以上のデータベース１３０の要素Ｅとマッチングさせる。このようなマッチングは計算リソースを要する可能性があるが、その結果として、参照値Ｒと共にパラメータｐ１、ｐ２、…によって示される情報を含む符号化データＤ２が生成される。これらのパラメータは、要素Ｅに適用されて、マッチングするデータブロックＤＢを表すことができるようにする１つ以上の変換を示す。デコーダ３０においてデータＤ２を復号化する際に、参照ＲがデータＤ２から抽出され、対応する要素Ｅが１つ以上のデータベースから識別されて、データＤ２から抽出されたパラメータｐ１、ｐ２、…に定義されたとおり適切に変換され、復号化データＤ３の構築に適切なデータブロックＤＢが生成される。この再構築プロセスを図３に示す。図３は、データの復号化によるデータＤ１の再構築を示している。すなわち、復号化データＤ３は、エンコーダ１０に提供されたデータＤ１に類似している。
【００６３】
１つ以上のデータベース１３０は、以下の少なくとも１つのように構成されてもよい。
（ｉ）エンコーダ１０に統合されている
（ｉｉ）デコーダ３０に統合されている
（ｉｉｉ）空間的に、エンコーダ１０および／またはデコーダ３０のリモートである
（ｉｖ）エンコーダ１０とデコーダ３０間で共有されている
【００６４】
また、１つ以上のデータベース１３０の一部がエンコーダ１０および／またはデコーダ３０のローカルにあり、別の部分が空間的にエンコーダ１０および／またはデコーダ３０のリモートであってもよい。
【００６５】
図４を参照すると、本開示の実施形態で用いられる検索プロセスにおいて、任意のデータブロックＤＢまたは要素Ｅが計算パラメータＡを用いて比較される。計算パラメータＡはデータブロックＤＢまたは要素Ｅのサブ領域に対応し、例えばパラメータＡ１〜Ａ４は、データブロックＤＢすなわちまたは要素Ｅの４分割部分それぞれに対応する。エンコーダ１０による検索は、データブロックＤＢのパラメータＡ１〜Ａ４を要素のパラメータＥと比較することで実行されると有利である。このような手法は、１つ以上のデータベース１３０内の要素Ｅが、データブロックＤＢに関連する何らかの方法、例えば反転、鏡像化、回転、拡大縮小などで変換される場合にうまく対処できる。これについては詳細に後述する。４分割されたサブ領域は例示にすぎず、例えば８分割など、領域の他の分割方法も可能であることを理解されたい。１つ以上のデータベース１３０は、ソリッドステートメモリ内、１つ以上のサーバ内、光学データ記憶媒体内、磁気記憶媒体内、１ビットのデータが１つの量子で表現される量子データ記憶装置内など、１つ以上の形式で実装されてもよい。１つ以上のデータベース１３０は、空間的に、エンコーダおよび／またはデコーダのローカルであってもよい。または、１つ以上のデータベース１３０は、例えば１つ以上のデータ通信ネットワークに接続され、空間的に、エンコーダおよび／またはデコーダのリモートであってもよい。
【００６６】
ＣＲＣ値またはハッシュ値を表現するために用いられるビット量に応じて、１つ以上の異なるデータブロックＤＢから、相互に類似するＣＲＣ値またはハッシュ値が生成されることがある。このようなＣＲＣ値またはハッシュ値が、データブロックを記述するパラメータとみなされることがある。また、少量のビットで表現されるＣＲＣ値またはハッシュ値には量子化エラーが生じる場合がある。任意の一対のＣＲＣ値またはハッシュ値同士が類似していても、それぞれが対応するデータブロック同士が類似しているわけではない。その任意の一対のＣＲＣ値またはハッシュ値が完全に同じではない場合、データブロック同士は大きく異なることが多い。任意のデータブロック内の１つの値をわずかに変更するだけで、そのＣＲＣ値またはハッシュ値は完全に違うものになる。したがって、本開示の実施形態の実行において、例えばデータブロックの形状をなんらかの方法で記述できるパラメータ値によってデータブロック間の類似性を記述するために、改良された方法が必要であることを理解されたい。
【００６７】
本開示の実施形態において、特に可逆圧縮での符号化が望まれる場合、これらのＣＲＣ値およびハッシュ値をインデックスの代わりに用いてもよい。実際は、定義が容易であるため、エンコーダ１０およびデコーダ３０においてインデックスを用いたほうが有利である。すなわちインデックスのほうが、必要とする計算リソースが少なく、順序通りに進められる。これは、データベースに十分な領域がある場合、そのデータベースに新しい要素を常に挿入できるということである。使用済みのＣＲＣ値またはハッシュ値が存在する場合、それが既に使用されている可能性があり、データベースに新しい要素を挿入することはできない。
【００６８】
ハッシュ値またはＣＲＣ値は、主として可逆的なデータブロックの検索に用いられると有利であるが、量子化を利用すると、非可逆的なデータブロックの検索にも用いられる。しかしながら、非可逆的なデータブロックでは誤検出が生じるという問題がある。一方、非可逆的なデータブロックでは、比較的小さな変更でも、データブロックをマッチングさせる際の誤りの原因となる可能性がある。このため、本開示の方法の実行において、非可逆的なデータブロックの場合はインデックス、ＣＲＣ、またはハッシュによって定義された領域全体を常に検索する必要があり、可逆的なデータブロックの場合は、検出すなわちマッチングがその差分絶対値を算出することによって検証されると有利である。
【００６９】
さらに、以下に詳細に説明する本開示の実施形態では、同じ任意のデータベース要素を異なる複数のデータブロックに用いることが可能である。これは、データベース要素の形状情報とマッチングさせるために、可能であればデータブロックを最初に鏡像化、反転、または並べ替えした場合でも可能である。このような実施形態を図５Ａから図５Ｄに示している。
【００７０】
したがって、概要として、本開示の実施形態では、データベース要素をより容易に区別可能にする一方で、相互に類似する形状を有する相互に類似する多数のデータブロックをデータベース要素によって表現することを可能にする。データベース要素およびデータブロックの形状に関する形状情報の利用により、データベース内で精度と速度の高いデータブロック検索を行うことが可能になり、データブロックを介してデータを記述し、データベース要素と関連付け、その参照値を対応する圧縮データに含めることで、高速かつ計算効率の高いデータ圧縮が行われる。形状情報もデータベース参照に格納する場合、データベースブロックは常に一意に用いられ、デコーダ３０における再構築が正確になる。
【００７１】
データブロックおよびデータベース要素は、通常は複数のデータ値を含む。ＭＡＲ（振幅比の平均）、平均、標準偏差、分散、振幅、中央値、最頻値、最小値、最大値、インデックス、レベル量などのパラメータがデータブロックまたはデータベース要素に対して定義される場合、類似するデータブロックのデータ値またはデータベース要素の値が異なる順序であったとしても、パラメータは類似する値を有する。そのようなパラメータはデータブロック値の形状または順序に依存しないので、１つ以上のデータベースを検索して、それらの中の対応する要素にデータブロックをマッチングさせるために用いるには、あまり適していないことがある。そのような状況に対処するために、本開示の実施形態では、以下で詳細に説明する高度な計算を利用している。
【００７２】
データブロックが、重複の有無にかかわらず複数の部分に分割される場合、例えば本開示の実施形態では、データブロックの形状もより正確に検出することができる。異なる部分から生成される検索目的のパラメータが類似している場合、データ値の形状または順序もデータベース要素とその対応するデータブロック間でかなり類似したものになる。次の例では、本開示に従う方法がどのように機能するかを示す。
【００７３】
データベースは、データ値を１次元データブロックまたは多次元データブロックで表現することができる。１次元データブロックは１次元サブブロックまたはセクションに分割でき、２次元データブロックは２次元サブブロックまたはセクションに分割できる。１次元データブロックにセクションを作成し、例えば２次元データの走査線行を表現することで、１次元データブロックから２次元データブロックを作成することもできる。同様に、２次元データをすべて行として表現することで、結果として１次元データブロックを作成することができる。
【００７４】
１次元データブロックが、以下の式２の数列に示すような１６個の値を含む場合、これらの１次元データブロック値は、以下の式３の数列に示すように４つのデータグループとして表現できる。
［式２］
１０，２０，２５，３０，１０，１５，２０，２５，１５，１５，１５，２０，２０，１５，１０，２０    
［式３］
１０，２０，２５，３０；  １０，１５，２０，２５；  １５，１５，１５，２０；  ２０，１５，１０，２０
【００７５】
また、これらの値は以下のような第１の２次元データブロックとして表現できる。
［式４］
１０，２０，２５，３０，
１０，１５，２０，２５，
１５，１５，１５，２０，
２０，１５，１０，２０                            
【００７６】
この第１の２次元データブロックが、垂直軸を中心に前述の方法で水平方向に反転されると、第２のデータブロック値は以下のようになる。
［式５］
３０，２５，２０，１０，
２５，２０，１５，１０，
２０，１５，１５，１５，
２０，１０，１５，２０                            
【００７７】
例えば、式４および式５両方のデータブロックの平均をそれぞれ算出すると、その結果は同じになる。これを以下に示す。
［式６］
平均１＝平均２＝（３＊１０＋５＊１５＋５＊２０＋２＊２５＋１＊３０）／１６＝１７．８１２５
【００７８】
しかしながら、このデータブロックの４分割部分、すなわち、それぞれ４つのサンプルを含む４つのサブブロックそれぞれの平均を算出した場合、類似する平均値が異なるデータブロックから得られ、それらのデータブロックは異なる分割部分に相当する。これを以下に示す。
［式７］
平均１_１＝平均２_２＝（１０＋２０＋１０＋１５）／４＝１３．７５
平均１_２＝平均２_１＝（２５＋３０＋２０＋２５）／４＝２５
平均１_３＝平均２_４＝（１５＋１５＋２０＋１５）／４＝１６．２５
平均１_４＝平均２_３＝（１５＋２０＋１０＋２０）／４＝１６．２５    
【００７９】
結果として、比較の際に、すなわち、任意のデータブロックを１つ以上のデータベースに含まれる要素とマッチングさせるための検索の際に、これらの４分割部分の平均値のみを用いることで、データブロック同士を容易に区別することができる。そのような検索において、第１のデータブロックがデータベース内に存在し、そのデータベース内で第２のデータブロックを検索するという状況がありうる。第２のデータブロックの４分割部分それぞれの平均値が水平方向に反転されている場合、それらの値が第１のブロックの４分割部分それぞれの平均値と類似している状況を検出することも可能である。
【００８０】
データブロックのサンプルの選び方（すなわちサブブロックの選び方、つまり選択の方法）は、様々であってよい。例えば前述の４行×４列の２Ｄデータブロックの例では、４つの行、４つの列、水平方向の２つの２分割部分、垂直方向の２つの２分割部分、それぞれ４個のサンプルを有する２本の異なる対角線、それぞれ６個のサンプルを有する２つの異なる三角形、それぞれ１０個のサンプルを有する２本の異なる対角線を用いることができる。実施例によっては、データブロックやデータベース要素の形状パラメータを定義するために、任意の組み合わせを用いてもよい。
【００８１】
データＤ１内のデータ値の順序が変更されると、異なるブロックとして検出される可能性があるため、「サンプリング」を用いることは適切である。サンプリングでは一貫したデータベースとならない可能性があるが、単純で効率的な方法でデータブロック同士が区別される。
【００８２】
本開示の実施形態において、ビットまたは値を作成し、すべてのデータブロックサンプルの平均と比較して、以下のようになっている４分割部分を示してもよい。
（ｉ）同じ平均値を有する。例えば０または１
（ｉｉ）より大きい平均を有する。例えば１
（ｉｉｉ）より小さい平均を有する。例えば０
例えば、この単純なバイナリの場合では、ビットは第１のデータブロックにおいて０，１，０，０であり、第２のデータブロックにおいて１，０，０，０である。
【００８３】
本発明の実施形態において、平均を、または平均同士の差異をより正確に指定するために、各４分割部分、すなわち各サブブロックに対してより多くのビットを用いてもよい。この例を次に示す。
［式８］
Ｘ＝サブブロックの平均−ブロック全体の平均                
【００８４】
Ｘ＞４の場合、（その時点で）使用済みバイナリ１１が存在する。４≧Ｘ＞０の場合、（その時点で）使用済みバイナリ１０が存在する。ここで「＞」は「より大きい」を、「≧」は「以上」を意味する。また、０≧Ｘ＞-４の場合、（その時点で）使用済みバイナリ０１が存在し、-４≧Ｘの場合、（その時点で）使用済みバイナリ００が存在する。結果として、第１のデータブロックのビットは００，１１，０１，０１となり、第２のデータブロックのビットは１１，００，０１，０１となる。例えば、データの最大値が３１であり、ありうる値が０〜３１の範囲、すなわち５ビットデータで定義され、３ビットが平均を表すために用いられる場合、Ｘ＝平均／４である。ここで、第１のデータブロックの値は３，６，４，４＝０１１，１１０，１００，１００、第２のデータブロックの値は６，３，４，４＝１１０，０１１，１００，１００と表現できる。
【００８５】
データベース要素が平均を持たない値として、すなわちゼロ平均の形式でデータベースに格納される場合、サブブロック内のサンプルの合計も、ブロック平均より小さい、すなわち負の値を、またはブロック平均より大きい、すなわち正の値を、サブブロックが含むことを示すことを理解されたい。
【００８６】
また、平均値の代わりに、ＭＡＲ（振幅比の平均）、標準偏差、分散、振幅、中央値、最頻値、最小値、最大値、ＣＲＣ、ハッシュ、レベル量などの他のパラメータを用いてサブブロックを記述してもよい。例えば、各４分割部分、すなわちサブブロックのパラメータ値を、第１のデータブロックにおいて１０、２０、１５、１０とし、第２のデータブロックにおいて２０、１０、１０、１５とする。データブロックの形状をより正確に定義するために、例えば異なるサブブロックごとに異なる値を用いるなど、複数の部分を用いてもよい。
【００８７】
これらの生成された形状値、すなわちビットは、エンコーダ１０から送信される参照値の一部として用いられると有利であり、前述の１つ以上のデータベース内におけるデータブロック検索を高速にするためのみに用いられても有利である。送信される参照値にもこれらの値が用いられる場合、データベース参照に必要なインデックス値の範囲が明らかに削減される一方で、依然として、大量の異なるデータベース要素をデータベース内で一意にかつ効率的に参照することができる。対応するデータベース要素の選択された記述は、送信されるデータベース参照内に反転ビット、回転ビット、鏡像化ビット、並べ替え情報ビットなどを用いることでも提供可能である。また、そのような情報アイテムを組み合わせて、以下のことを意味するようにしてもよい。
（ｉ）    「０００」：通常の状態
（ｉｉ）    「００１」：水平方向に反転
（ｉｉｉ）    「０１０」：垂直方向に反転
（ｉｖ）    「０１１」：右方向に９０度回転
（ｖ）    「１００」：左方向に９０度回転
（ｖｉ）    「１０１」：１８０度回転、すなわち、水平方向または垂直方向に反転
（ｖｉｉ）    「１１０」：０２１３の順序の４分割部分
（ｖｉｉｉ）    「１１１」：３１２０の順序の４分割部分
【００８８】
この情報はエンコーダ１０においてエントロピー符号化、すなわち他の部分参照情報と同様の方法で符号化されてもよい。
【００８９】
否定値を用いてもよく、この種の情報もエンコーダ１０とデコーダ３０の間で送信可能である。また、否定値は元のデータブロック値に用いても、異なるブロック値に用いてもよい。例えば、第１のデータブロックに対して、この例では０〜３１の範囲の値で否定ブロックを生成した場合、値は以下のようになる。
［式９］
２１，１１，０６，０１，
２１，１６，１１，０６，
１６，１６，１６，１１，
１１，１６，２１，１１                            
【００９０】
その後、このデータブロックの平均を以下のように計算してもよい。
［式１０］
平均３＝（３＊２１＋５＊１６＋５＊１１＋２＊６＋１＊１）／１６＝１３．１８７５＝３１−平均１
【００９１】
同様に、データブロックの各４分割部分、すなわち、それぞれ４つのサンプルを含む４つのサブブロックの平均値を計算すると、データブロックの４分割部分の平均値は以下のようになる。
［式１１］
平均３_１＝（２１＋１１＋２１＋１６）／４＝１７．２５＝３１−平均１_１
平均３_２＝（６＋１＋１１＋６）／４＝６＝３１−平均１_２
平均３_３＝（１６＋１６＋１１＋１６）／４＝１４．７５＝３１−平均１_３
平均３_４＝（１６＋１１＋２１＋１１）／４＝１４．７５＝３１−平均１_４
【００９２】
また、否定値を含むデータブロックは、前述の１つ以上のデータベース内で非常に効率的に検索可能である。ほかにも多数の他のタイプのデータブロックを、データベース参照によって記述したり、提供された任意のブロック参照に基づいて作成したりすることができる。これらの他のタイプのデータブロックは何らかの種類の形状情報を含んでもよく、また、参照されるデータベース要素値を指定された方法で変更し、それによって、結果として生じるデータをデコーダ３０において再構築する際に用いられるデータブロックを変更するような、他の情報を含んでもよい。
【００９３】
１つ以上のデータベースにおけるデータブロック検索に形状情報を用いる場合、すべてのデータベース要素に対して形状情報、すなわちサブブロック参照値を事前に算出して利用可能にしておくと有利である。検索されるデータブロック、または少なくともその参照値を修正し、そのデータブロックまたは少なくともその修正された参照値の検出を１つ以上のデータベースで試みることによって、反転、回転、否定などの様々な組み合わせを検索することができる。反転、回転、否定などの変換の例を図５Ａから図５Ｅに示す。
【００９４】
参照値は、例えば前述のように実装されている特定の要素（Ｅ）を、または複数の要素（Ｅ）を用いる場合は要素（Ｅ）のグループを、データベース内で個別に指す値であることを理解されたい。一方、大きいデータブロックに関する「形状」情報は、その大きいデータブロックの参照値を記述する。例えば、その大きいデータブロック内のサブブロックの特性がこれに当たる。つまり、通常はビット値である形状情報は、そのサブブロックのサイズに対応するデータベース内の要素を実際に指すわけではなく、大きいデータブロックのサブブロックの属性、すなわちパラメータから構築できる。必要に応じて、サブブロックの属性から参照値を構築して、そのサブブロックと同じサイズのデータブロック用のデータベースに提供してもよい。しかしながら、異なる方式を有利にも用いてもよく、この場合、データベース要素または要素のグループを実際に指す方法であってもよい。換言すれば、ここで共通の要因は属性であるので、大規模なデータベース内でデータブロックが検出されず、後に、より小規模なデータベース内でそのデータブロックを検索する必要があっても、それらの属性を算出することが賢明かつ効率的である。
【００９５】
エンコーダ１０において用いられる全体的な符号化方法と、対応してデコーダ３０において用いられる全体的な方法に応じて、形状情報用のサブブロックを有利にも作成してもよい。例えば、１６×１６、８×８、および４×４のデータベースが利用可能であることが分かっている場合、４×４ブロックの、さらには２×２ブロックのすべての参照値を直ちに計算し、その後、作成したそれらの参照値に基づいて８×８および１６×１６ブロックの参照値を計算することができる。ここで、１６×１６ブロックに対するすべての参照値が利用可能になり、同様にサブブロックの参照値、例えばそのブロックをより正確に記述する８×８の４分割部分の参照値も利用可能になる。これら１６個の４×４ブロックは、形状をより正確に定義するために１つの１６×１６ブロックに用いてもよいことを理解されたい。また、サンプリングを用いて様々な属性、すなわちパラメータ値を算出してもよい。これは理論上、サブブロックが実際には存在せず、サブブロック内にあったものか、サンプルされたものかに関係なく、元のデータブロックから選択されたサンプルであることを意味する。しかしながら、当該データベース内で検索を実行する必要があり、そのデータベースがサブブロックデータを含む場合、サブブロックの属性を算出する必要がある。属性は常に算出することが有利であり、それによって検索を高速に実行できる。ベイヤー型サンプリングを用いる実施形態を図５Ｅに示す。
【００９６】
原則として、４×４ブロックに対応する要素を含む任意のデータベースは、音声および画像／動画の両方に用いることができる。ただし、動画と比較して音声信号は非常に異なるふるまいをすることが多い。そのため、通常は、音声データ専用のデータベースを作成すると有利である。音声データではデータ値のビット深度は例えば１６／２４ビットより大きく、画像ではビット深度は多くの場合８ビットであるが、実際は１０／１２／１４／１６ビットも用いることができる。別のカラーチャネル値をインターリーブ形式で用いて、例えば、３チャネルの組み合わせに２４ビット値を用いることもできる。
【００９７】
しかしながら、そのような、８ビット値のカラーチャネル３つを含む２４ビットのデータベースは、２４ビットの音声サンプルを含むデータベースとはやや異なる。３つのカラーチャネルのインターリーブされた８ビット値を含む２４ビットのデータベースの場合、その３つの８ビット値、例えば平均が常に個別に計算されるのに対し、例えば平均を示す、２４ビットの１つの値を含む音声データベース要素は、変換において１つの値として処理されるように、すべての変換を実行すると有利である。
【００９８】
データブロックは、例えばエンコーダ１０におけるデータの符号化の際に拡大または縮小されてもよく、この際、用いられる拡大縮小アルゴリズムが適切に実行されれば、妥当な方法によって、データブロックまたはそのサブブロックの参照値は変更されないことを理解されたい。また、軽微な変更を、例えば振幅に対して行ってもよい。これは、少量のデータ値では、大量のデータ値で表現できる同じ周波数情報を表現できない、すなわち、データ内容のエイリアシングなしではないためである。
【００９９】
例えば符号化データＤ２内に含めて送信された、すなわち静的な、データベース要素参照値に形状情報が追加される場合、その参照は、例えば、８ビットの平均値、３ビットの振幅、振幅に依存する３ビットの標準偏差、４ビットの形状情報（すなわち４分割部分の平均差）、４ビットの形状情報（すなわち垂直方向スライスの振幅）、３ビットのブロック順序値、反転値、回転値、否定情報、および、類似の参照値に対する異なる組み合わせとして２ビットのインデックスを含んでもよい。
【０１００】
形状情報は動的データベース要素と共に用いてよいことを理解されたい。静的データベースとは一定量の静的要素を含むデータベースであり、動的データベースにおいては、データベース要素が動的に変更、すなわちデータベースに対して挿入されたり削除されたりする。
【０１０１】
データベース要素またはデータブロックの検索は、１つまたは複数のルックアップテーブル（Look-Up Table：ＬＵＴ）を用いて行うこともできる。高速なデータベース検索を実行するために、データベース要素および／またはデータブロックをサブ要素またはサブブロックに分割してもよい。その場合、参照値の組合せから、すなわちサブ要素またはサブブロックの複数のデータ値から、１つの計算参照値を算出、すなわち計算すると有利である。検索に用いられるルックアップテーブルが１つのみの場合、そのテーブルは、特定の量の計算参照値、およびデータベース要素へのポインタ、またはデータベース要素を一意に記述する送信される参照値を格納するのに十分なサイズである必要がある。本開示の実施形態において、データベース内でデータブロック（Data Block：ＤＢ）に関する変換を検索する際は、形状、平均、標準偏差などのカテゴリに基づいて検索される。
【０１０２】
検索に複数のルックアップテーブルを用いてもよいが、その場合、計算参照値は、他の使用されているルックアップテーブルの計算参照とは異なるデータ値または異なるアルゴリズムを用いて計算する必要がある。複数のルックアップテーブルの計算参照値は各サブ要素または各サブブロックに関連付けることが望ましく、そうでない場合、エンコーダ１０における符号化において、また同様にデコーダ３０における復号化において、達成可能な精度が低下しやすい。
【０１０３】
送信される参照値のサイズはデータベース要素に最適に算出、すなわち計算し、その値を検索してデータブロックを検出することが有利である。検索後、参照値は通常、符号化データＤ２に書き込まれまたは送信されるため、エンコーダ１０において実行される符号化プロセスに必要な量以上のビットを用いるべきではなく、データベース要素を一意に識別するのに十分な量だけにすべきである。計算データベース参照によって、より正確な参照が有利に用いられ、データブロックに対するデータ要素の高速検索が可能になる。そのため、計算データベース参照は１つのデータベース要素に対応し、１つのルックアップテーブル内の他の計算参照値から区別することができる。
【０１０４】
各データベース要素は、複数の計算参照を有してもよい。１つの計算参照によってルックアップテーブル内の複数のデータベース要素を「提供する」ことも可能である。計算参照が短いと、用いられるルックアップテーブルも小さくなる。ただしその場合、複数のテーブルの結果を比較し、有効なデータベース要素のみを、すべてのルックアップテーブルの計算参照に対して利用可能にする必要がある。例えば、４×４データブロックは４つの対応する２×２サブ要素またサブブロックで構成され、各サブ要素またはサブブロックはそれぞれ固有の計算データベース参照値を有する。この参照値は、形状、ＭＡＲ（振幅比の平均）、平均、標準偏差、分散、振幅、中央値、最頻値、最小値、最大値、ＣＲＣ、ハッシュ、レベル量などの複数のデータ値を含んでもよい。サブ要素の組み合わせ、すなわちすべてのサブブロックの各計算参照値は、時系列番号、またはデータベース要素へのポインタ、または送信される参照値と共に固有のルックアップテーブルに格納される。
【０１０５】
データベース要素から任意のデータブロックを検索する場合、すべてのサブ要素またはそのデータブロックのすべてのサブブロックが、計算参照値を介してルックアップテーブル内の対応する同じデータベース要素にリンクされていれば、成功が表示される。これは、既知のタイプの検索方法と比べて非常に高速な検索方法であるが、完全に正確というわけではない。利用されている「鳩の巣原理」のため、すべての場合において真になることはできない。後述の付属書類の参照文献［１］を参照されたい。１つまたは複数のテーブルによる高速な検索方法を用いると、結果の１つ以上のデータベース要素がソースデータブロックとの比較によって確認された後、受け入れられて、エンコーダ１０において符号化データＤ２へと符号化されると有利である。
【０１０６】
エンコーダ１０およびデコーダ３０は、例えばパーソナルコンピュータ、ファブレットコンピュータ、タブレットコンピュータ、スマートフォン、消費者向け視聴覚装置、ゲーム装置、科学用計測器、通信システム、車両、航空機、衛星、データ通信システム、車載装置、自動車装置などの広範な装置に利用できる。エンコーダ１０およびデコーダ３０は、データ処理ハードウェアを用いて、例えば、非一時的コンピュータ可読データ格納媒体および／またはカスタマイズされたデジタルハードウェアに記録された１つ以上のソフトウェア製品を実行するように動作するコンピュータハードウェアを用いて実行されると有利である。
【０１０７】
本開示の実施形態は、デコーダ３０内にありうる大量の再構築ブロックを、より少量のデータベース要素によって表現することを可能にする。また、本開示の実施形態は、形状を記述するサブブロック内の情報を用いて、類似の参照値を有するデータブロックの区別を容易にする方法も利用する。この形状情報によって、１つ以上のデータベース内におけるデータブロック検索が高速になる。形状情報は、参照値に含めて直接、または修正して提供してもよい。形状情報によって、データブロックがデータベース要素に十分に類似しているかを検証するために必要なデータ値同士の比較の量が削減される。この比較は依然として必要なこともあるが、データブロック内のサブブロックおよびデータブロック要素に基づく形状情報を利用しない既知の方法に比べて、比較されるデータベース要素の量は大幅に削減される。
【０１０８】
本開示の実施形態において、形状情報は個別のカテゴリ要素として参照内で提供され、１つ以上の変換を定義する変換情報、およびそのような変換情報の利用に関する情報の提供は伴わない。また、そのような実施形態において、サブブロックの属性情報により、例えば、サブブロックの分散を記述するビットパターン、例えば１，１，０，０を作成できる。このパターンは、対応するメインブロックにおいて、２つの４分割部分、すなわち左上および右上の４分割部分は分散の大きい情報を含み、他の２つの４分割部、すなわち左下および右下は均一なサブブロックであることを意味している。このような手法は、図５Ａから図５Ｅの形状の例に見られるように、データベース要素を記述する新しい４ビットのカテゴリ（「カテゴリ」はデータベース内の検索目的に使用されているため、検索動作中にデータゲーティングを実行するためのものとして、「ゲートゴリ」と呼ぶ）を可能にする。これらによって、「１」ビットおよび「０」ビットの量がいくつかの他のブロック内で同じであって、関連するビットの順序が異なる場合、以下のことが可能になる。
（ｉ）    データベース内の検索の高速化
（ｉｉ）    参照の提供への利用
（ｉｉｉ）    １つ以上の変換における推定または見積もりの有効化
例えば、別のブロックのビットパターンが０，１，０，１、すなわち右上および右下のサブブロックに分散が含まれ、左上および左下が均一である場合、そのようなタイプのブロックは、前述のタイプのデータベース要素に対応できる可能性がある。すなわち、右方向への９０度回転を伴う変換の対象となる１，１，０，０ブロックに対するデータベース要素である。
【０１０９】
前述の「ゲートゴリ」は、サブブロックの分割方法に応じて様々な量のビットを含んでもよい。カテゴリのビットパターンにおける通常のビット数は、前述の例に用いたビット数４に加えて、２、８、３、５である。同様に、「ゲートゴリ」も、データベース検索時に関係する様々なタイプの閾値情報を記述してもよい。前述の例では、ビットパターン内のビットは常に、サブブロック内の大きい分散値か小さい分散値を記述するものであるが、ビットパターン内のビットは、大きい平均値や小さい平均値、または該当する任意のサブブロックの他の特性を記述してもよい。
【０１１０】
データブロック、データベース、またはデータベース要素の「カテゴリ」は、そのデータブロック、データベース、またはデータベース要素の異なる特性、すなわちパラメータに基づいて１つ以上の「ゲートゴリ」を含んでもよいことを理解されたい。
【０１１１】
そのような手法により、形状に依存する新しいタイプの要素、すなわち関連付けられたブロックが回転または反転された場合に変更され、そのような変更が予測可能である要素が提供されることを理解されたい。これに比べて、ＣＲＣ値やハッシュ値ではそのような利点が得られない。ＣＲＣ値およびハッシュ値の変更は、関連付けられたブロックの回転、反転、ノイズの混入がある場合は予測できない。
【０１１２】
均一なサブブロックの数を記述する２ビットを用いることで、前述の「ゲートゴリ」を提供することもできる。「均一なサブブロック」とは、顕著な分散を含まないサブブロックである。この場合、値０、１、２、および３が有効であり、値４はブロック全体が均一であることを意味するので、これは通常はデータベースを利用して符号化されない。あるいは、このブロックがデータベースを利用して符号化される場合、ゲートゴリはすべての属性によって定義できる。換言すれば、サブブロックのゲートゴリは不要である。この例ではゲートゴリも、形状、例えば均一な要素を含むサブブロック数などに基づくが、ブロックが回転または反転されてもゲートゴリは変更されない。
【０１１３】
前述の例および説明ではデータブロックに言及しているが、データブロックに用いられるプロセスおよび変換はデータのパケットに用いることもできる。パケットの例として、音声フレームや音声サンプルのチャンクなどの音声パケットがある。音声パケットも、例えば２つ、３つ、または４つのサブパケットに分割することができる。したがって前述の例は、権利保護の範囲を限定するものではない。例えば、音声パケットは、周波数に関して分割され、音声フーリエ成分の比較とマッチングに基づいて検索されるように、そのフーリエ高調波成分に応じて分割されてもよい。画像の空間フーリエ周波数にも同様のことが当てはまる。
【０１１４】
添付の特許請求の範囲に定義される発明の範囲を逸脱することなく、前述した本発明の実施形態への修正が可能である。本発明の記述と特許請求の範囲で用いられる「含む」、「備える」、「包含する」、「構成される」、「有する」、「存在する」などの表現は、包括的構成であると解釈されることを意図しており、明示的に記載されていないアイテムや部品、構成要素も含まれうることを意図している。単数による表記は、複数の場合も関連すると解釈される。添付の特許請求の範囲における括弧内の数字は、請求項の理解を助けることを意図したものであり、これらの請求項によって定義される発明の範囲を限定するように解釈されるべきではない。
【０１１５】
［付録］
参照文献：
[１]    Pigeonhole principle（鳩の巣原理）  ウィキペディア、フリー百科事典（英語版）（２０１３年１０月２日アクセス）。URL: http://en.wikipedia.org/wiki/Pigeonhole_principle
【図１】
0006457558.tif 000002
【図２】
0006457558.tif 000003
【図３】
0006457558.tif 000004
【図４】
0006457558.tif 000005
【図５Ａ】
0006457558.tif 000006
【図５Ｂ】
0006457558.tif 000007
【図５Ｃ】
0006457558.tif 000008
【図５Ｄ】
0006457558.tif 000009
【図５Ｅ】
0006457558.tif 000010