(57)【要約】【課題】本発明の目的は、非圧縮及び圧縮データ標準の間でデジタル・イメージを符号化する変換速度を改善するイメージ圧縮デバイス及びプロセスを提供することである。【解決手段】本発明は、離散コサイン変換圧縮プロセス（４８）と共に用いられるデータ圧縮エンコーダ（３８）において実現される。本発明は、受け取ったデータを予測された部分と予測されていない部分とに分割する予測エンジン（４６）を用いることによって、離散コサイン変換を用いる圧縮を強化している。予測された部分は、離散コサイン変換から取り除かれ、ファイルを圧縮するのに要する時間を短縮する。予測エンジンは、部分的に、予測されたブロックを判断するのに用いられるルックアップ・テーブルに依存している。ルックアップ・テーブルを作成するためには、テーブル構築エンジンとデータベース・コンパイラとが用いられる。【選択図】図３
2011103665.tif 000002
【特許請求の範囲】
【請求項１】
イメージ変換システム（３０）であって、
イメージを表す圧縮されていないデータ値のセットを複数のデータ・ブロックへ配分するように構成された配分モジュール（４４）、及び処理された圧縮されていないブロックを計算値の複数のグループへ分割するように構成されたグループモジュール（４５）を有する離散コサイン変換エンジン（４２）と、
複数のルックアップ・テーブルを有する推論エンジン（４６）であって、前記複数のグループの各々に対して、該推論エンジン（４６）は、
該グループに関連するルックアップ・テーブルの部分から複数のレコードを読み出し、
前記複数のレコードのうちのいずれもゼロに等しくない場合、該グループについての圧縮されたデータに対応する予測符号を割当て、
前記複数のレコードのうちの一つがゼロに等しい場合、該グループの予測ができないことを判定し、該グループに対して離散コサイン変換を実行するために前記離散コサイン変換エンジン（４２）へ該グループを戻す
ように構成されている、前記推論エンジンと
を備えるイメージ変換システム。
【請求項２】
請求項１記載のイメージ変換システムであって、前記変換エンジン（４２）は、ＪＰＥＧまたはＭＰＥＧ標準に従って前記圧縮されていないブロックを変換するように構成されている、システム。
【請求項３】
請求項１記載のイメージ変換システムであって、ホフマン変換エンジンを更に備える、システム。
【請求項４】
データ圧縮の方法であって、
イメージを表す圧縮されていないデータ値のセットを複数の圧縮されていないブロックへ配分すること、
前記複数の圧縮されていないブロックの各々に対して、
前記圧縮されていないブロックを処理すること、
前記処理された圧縮されていないブロックを、計算値の複数のグループへ分割すること、
前記複数のグループの各々に対して、
複数のルックアップ・テーブルから複数のレコードを読み出すことであって、各ルックアップ・テーブルは、該グループの計算値のうちの一つと関連している、前記読み出すこと、
前記複数のレコードのいずれもゼロに等しくない場合、該グループについての圧縮データに対応する予測符号を割り当てること、
複数のレコードのうちの一つがゼロに等しい場合、該グループの予測ができないことを判定し、該グループに対して離散コサイン変換を実行すること
を含む方法。
【請求項５】
請求項４記載の方法であって、前記予測符号は、ＪＰＥＧ標準に従うものである、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広くは、データ圧縮装置を構築するシステムに関し、更に詳しくは、イメージの符号化（コーディング）のためのデータ圧縮装置を構築するシステムに関する。
【背景技術】
【０００２】
高速で低価格のマイクロプロセッサが出現したことにより、印刷物、音声及び映像（ビデオ）を伝送するためのデジタル通信装置の開発が急速に成長している。この急速な成長とそのような装置に対する需要とは、デジタル通信に対する需要を満足させる通信帯域幅を提供する現時点での通信ハードウェア・インフラストラクチャの能力を既に追い越してしまっている。デジタル通信システムの分野では、与えられた媒体を介してある時間内に伝送されうるデータの量は、帯域幅（バンド幅）と称される。
【０００３】
利用可能な帯域幅を拡張する方法としては、伝送される情報を表すのに必要なデジタル・データの量を減少させるデータ圧縮技術の実現によるものがある。デジタル圧縮技術は、現時点では、デジタル通信ハードウェアのスループットを増加させる最も一般的な方法である。ハードウェア技術と様々な産業において及び国際的に存在するデジタル・コンピュータ・プラットフォームとが多様であるという現状において、普遍的に実現が可能なデータ圧縮技術を提供する標準が確立されている。
【０００４】
イメージやピクチャがデータによるデジタル形式で表現される映像情報システムの分野では、デジタル・イメージを圧縮するための標準が数多く開発され商業的に受け入れられている。そのような標準の１つとして、ジョイント・フォトグラフィック・エクスパート・グループ（Ｊｏｉｎｔ  Ｐｈｏｔｏｇｒａｐｈｉｃ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ  ＝  ＪＰＥＧ）によって開発されたものがある。このグループは、グレイスケール及びカラー・イメージの圧縮のための国際標準を確立するために形成された国際的な団体である。この圧縮標準は、ＪＰＥＧ標準として知られるようになっているが、この標準では、デジタル・イメージはエンコーダを介して圧縮され、ＪＰＥＧフォーマットとして知られる圧縮形式で表現される。ＪＰＥＧフォーマットで記憶されているイメージは、非圧縮形式で記憶されている同じデジタル・イメージのファイル・サイズと比べて、はるかに小さなファイル・サイズを有する。ＪＰＥＧ標準は、１９９２年９月１８日に、リコメンデーションＴ．８１としてインターナショナル・テレグラム・アンド・テレフォン・コンサルタティブ・コミティ（ＣＣＩＴＴ）によって推奨され、「情報技術−連続トーンのスティル・イメージのデジタル圧縮及び符号化−要求及びガイドラインＩＴＵ−ＴリコメンデーションＴ．８１｜ＩＳＯ１０９１８：１」と題する標準的なＩＳＯ１０９１８：１として、インターナショナル・スタンダーズ・オーガニゼーション・アンド・インターナショナル・エレクトロテクニカル・コミッション（ＩＳＯ／ＩＥＣ）によって公表された。
【０００５】
ＪＰＥＧ標準は、実際には、２つのクラスの圧縮プロセスで構成される。すなわち、損失性（不可逆的、ｌｏｓｓｙ）の圧縮技術と非損失性（可逆的、ｌｏｓｓｌｅｓｓ）の圧縮技術との２つである。損失性の圧縮では、実質的な圧縮は達成されるのであるが、イメージが後に解凍（圧縮解除）されるときにイメージ・データのいくらかの損失が生じる。しかし、その際に生じるイメージの質の損失は最小限であるので、肉眼で見ている限りは、識別不可能であると一般的に考えられている。離散コサイン変換（ＤＣＴ）に基づくプロセスは、損失性であると考えられている。損失性の圧縮を用いているエンコーダ２０（図１）は、一般に、ＤＣＴエンジン２１と、量子化器２２と、エントロピ・コーダ２６とを含む。これらの機能は、ＪＰＥＧ標準において定義されている。第２のクラスでは、非損失性の圧縮が、イメージが解凍される際にイメージの質の損失が生じないＤＣＴとは別の技術を用いて達成される。しかし、非損失性の圧縮は、損失性の圧縮を用いる場合よりも圧縮率が小さい。従って、非損失性の圧縮によって圧縮されたデジタル・イメージは、損失性の標準に従って圧縮された場合の同じイメージと比較すると、より大きなファイル・サイズを有し、通信線を介して転送されるのに要する時間も長くなる。人体の組織に関するイメージの表現におけるどのような小さな変化であっても医学の専門家による疾病の診断に影響を与えうる医療用の画像化技術など、イメージの精度が望まれる分野以外では、ほとんどの画像化アプリケーションは、デジタル伝送のために、損失性の圧縮標準を用いることができる。
【０００６】
ファックス・マシンの間でデジタル・イメージを伝送するというようなリアルタイムでの応用例のいくつかでは、デジタル・イメージを圧縮するＪＰＥＧ標準は、イメージの伝送との関係で、データを同時的に圧縮すること以上の能力を有している。これは、通常のアナログ電話回線はデジタル・データ伝送のためには狭い帯域幅しか有しておらず、それ以外のデジタル通信方法よりも生来的に低速であって、同時的なＪＰＥＧ圧縮プロセスがリアルタイムで生じる以上の時間を提供するという事実に起因する。しかし、コンピュータ・バス及びネットワークやデジタル・テレビ・システムのような、より優れたデジタル・スループットを有する又はデジタル伝送のために設計されているそれ以外のハードウェア通信システムでは、更に大きなスループット及び速度に対する利用可能性及び必要性が求められている。デジタル・テレビ伝送などの通信システムでは、ＪＰＥＧ標準に基づいており動画イメージを圧縮及び伝送するためのムービング・ピクチャーズ・エキスパーツ・グループ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅｓ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ  ＝  ＭＰＥＧ）標準であってもこの時間的な拘束によって制限されているとこの技術分野の当業者は認識している。更に、イメージ・データが、例えば周辺機器からパーソナル・コンピュータに転送される前に、又は、イメージをデジタル・カメラなどに記憶するのに用いるために、ＪＰＥＧイメージを圧縮し記憶するための更に高速な方法が必要になっている。そのような環境においてリアルタイムで従来型のＪＰＥＧ圧縮プロセスが用いられると、従来型のＪＰＥＧ圧縮方法を用いてデジタル・イメージをＪＰＥＧ標準に変換するのに必要な圧縮時間のために、そのような高速通信システムの全体的な通信速度が低下する。
【０００７】
従って、そのような圧縮されたファイルを転送する際に節約される時間は、従来型の圧縮技術によってデジタル・イメージをＪＰＥＧファイル・フォーマットに符号化するのに要する時間だけ部分的に短縮されることが理解されよう。このような時間的な拘束のために、圧縮及び伝送が、迅速に、同時的に及び／又はリアルタイムで生じることを必要とする応用例では、ＪＰＥＧファイル・フォーマットの有効性が制限される。
【０００８】
従って、圧縮されていないファイル標準とＪＰＥＧやＭＰＥＧなどの圧縮されたファイル標準との間で、リアルタイムに遅延なく、しかも高速の通信システムと共に動作しながらデジタル・イメージを変換することができる符号化及び復号化デバイス及びプロセスに対する必要性が存在している。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、非圧縮及び圧縮データ標準の間でデジタル・イメージを符号化する変換速度を改善するイメージ圧縮デバイス及びプロセスを提供することである。
本発明の別の目的は、損失性（ｌｏｓｓｙ）の圧縮プロセスを用いて圧縮されたイメージをデジタル伝送するための変換速度を改善するイメージ圧縮デバイス及びプロセスを提供することである。
【００１０】
本発明の更に別の目的は、ＪＰＥＧ標準の下で圧縮されたイメージを生じさせるのに用いられる損失性の圧縮プロセスにおいて、離散コサイン変換（ＤＣＴ）に要する時間を短縮するイメージ圧縮デバイス及びプロセスを提供することである。
本発明の効果は、損失性の圧縮プロセスから質の高いイメージを提供することができ、圧縮率を向上させることである。
【００１１】
本発明の別の効果は、不要であるが従来の損失性の圧縮の間に実行されていたＤＣＴサイクルを除去することによって、タイミングを向上させることである。
本発明の更に別の効果は、経済的に製造ができ、多様な通信プラットフォームの間での移植性（ポータビリティ）を有することである。
【００１２】
本発明の更に別の効果は、複数のタイプの圧縮されていないデジタル・イメージを区別することができ、第１の組のイメージ・データに対しては損失性の符号化段階を提供し、第２の組のイメージ・データに対しては従来型のＤＣＴを実行することにより、第１の組のデータに対するＤＣＴの使用を除去することである。
【００１３】
通信リンクを介してのデータの伝送を実質的に改善し、イメージのリアルタイムでの通信を確立し維持する能力を実質的に向上させる圧縮デバイス及びプロセスを提供することが本発明の特徴である。
【課題を解決するための手段】
【００１４】
本発明は、データ・セットを非圧縮標準から圧縮標準に変換するデータ圧縮システムであって、前記データ・セットは前記圧縮標準の下で記憶媒体に記憶されているときの方が前記非圧縮標準の下で記憶されているときよりも必要とする空間が小さいようなデータ圧縮システムにおいて実現される。このシステムは、圧縮されていない前記データ・セットを複数の圧縮されていないブロックに配分する手段を含む離散コサイン変換エンジンと、前記ブロックのそれぞれを所定の基準に従って操作し、前記操作されたブロックのそれぞれを所定の組の圧縮されたブロック標準と比較することによって、前記ブロックを予測されたブロックと予測されていないブロックとに分割するように構成された推論エンジンと、前記推論エンジンによってなされた比較に基づき、複数の圧縮されたブロックの中の選択された１つを前記予測されたブロックのそれぞれに割り当てる手段とを備えており、前記離散コサイン変換エンジンは、前記予測されていないブロックを圧縮されたブロックに変換する手段を更に含み、それによって、前記データ・セットを前記圧縮標準の下で記憶することができ、前記選択された圧縮されたブロックの前記予測されたブロックへの割当ては、一般に、前記予測されたブロックが前記変換手段によって圧縮されたかのように見える。
【００１５】
本発明は、データ・セットを非圧縮標準から圧縮標準に変換するデータ圧縮方法であって、前記データ・セットは前記圧縮標準の下で記憶媒体に記憶されているときの方が前記非圧縮標準の下で記憶されているときよりも必要とする空間が小さいようなデータ圧縮方法を含む。この方法は、圧縮されていない前記データ・セットを複数の圧縮されていないブロックに配分するステップと、前記ブロックのそれぞれを所定の基準に従って操作することによって、前記ブロックを予測されたブロックと予測されていないブロックとに分割するステップと、前記操作されたブロックのそれぞれを所定の組の圧縮されたブロック標準と比較するステップと、前記比較に基づき、複数の圧縮されたブロックの中の選択された１つを前記予測されたブロックのそれぞれに割り当てるステップと、離散コサイン変換によって、前記予測されていないブロックを圧縮されたブロックに変換するステップと、を含む。
【００１６】
本発明は、データ・セットを非圧縮標準から圧縮標準に変換するデータ圧縮装置であって、前記データ・セットは前記圧縮標準の下で記憶媒体に記憶されているときの方が前記非圧縮標準の下で記憶されているときよりも必要とする空間が小さいようなデータ圧縮装置を含む。この装置は、圧縮されていない前記データ・セットを複数の圧縮されていないブロックに配分する手段を含む離散コサイン変換エンジンと、前記ブロックのそれぞれを所定の基準に従って操作し、前記操作されたブロックのそれぞれを所定の組の圧縮されたブロック標準と比較することによって、前記ブロックを予測されたブロックと予測されていないブロックとに分割するように構成された推論エンジンと、前記推論エンジンによってなされた比較に基づき、複数の圧縮されたブロックの中の選択された１つを前記予測されたブロックのそれぞれに割り当てる手段と、を備えており、前記離散コサイン変換エンジンは、前記予測されていないブロックを圧縮されたブロックに変換する手段を更に含み、それによって、前記データ・セットを前記圧縮標準の下で記憶することができ、前記選択された圧縮されたブロックの前記予測されたブロックへの割当ては、一般に、前記予測されたブロックが前記変換手段によって圧縮されたかのように見える。
【００１７】
別の好適実施例では、本発明は、デジタル・イメージをＹ、Ｃｂ及びＣｒイメージ・データからＪＰＥＧイメージ・データに変換するデータ圧縮システムであって、前記デジタル・イメージはＪＰＥＧイメージ・データの下で記憶媒体に記憶されているときの方がＹ、Ｃｂ及びＣｒイメージ・データの下で記憶されているときよりも必要とする空間が小さいようなデータ圧縮システムにおいて実現される。このシステムは、圧縮されていない前記デジタル・イメージを複数の圧縮されていない８ｘ８アレイに配分する手段を含む離散コサイン変換エンジンと、前記８ｘ８アレイのそれぞれを所定の基準に従って操作し、前記操作された８ｘ８アレイのそれぞれを所定の組の圧縮された８ｘ８アレイ標準と比較することによって、前記８ｘ８アレイを予測された８ｘ８アレイと予測されていない８ｘ８アレイとに分割するように構成された推論エンジンと、前記推論エンジンによってなされた比較に基づき、複数の圧縮された８ｘ８アレイの中の選択された１つを前記予測された８ｘ８アレイのそれぞれに割り当てる手段と、を備えており、前記離散コサイン変換エンジンは、前記予測されていない８ｘ８アレイを圧縮された８ｘ８アレイに変換する手段を更に含み、それによって、前記デジタル・イメージを前記ＪＰＥＧイメージ・データの下で記憶することができ、前記選択された圧縮された８ｘ８アレイの前記予測された８ｘ８アレイへの割当ては、一般に、前記予測された８ｘ８アレイが前記変換手段によって圧縮されたかのように見える。
【００１８】
別の好適実施例では、データ・セットを圧縮標準の間で変換するデータ圧縮システムであって、前記データ・セットは前記圧縮標準の下で記憶媒体に記憶されているときの方が非圧縮標準の下で記憶されているときよりも必要とする空間が小さいようなデータ圧縮システムにおいて実現される。このシステムは、圧縮されていない前記データ・セットを複数の圧縮されていないブロックに選択的に配分する手段を含む離散コサイン変換エンジンと、前記ブロックのそれぞれを所定の基準に従って操作し、前記操作されたブロックのそれぞれを所定の組の圧縮されたブロック標準と比較することによって、前記ブロックを予測されたブロックと予測されていないブロックとに分割するように構成された推論エンジンと、前記推論エンジンによってなされた比較に基づき、複数の圧縮されたブロックの中の選択された１つを前記予測されたブロックのそれぞれに割り当てる手段とを備えており、前記離散コサイン変換エンジンは、前記予測されていないブロックを圧縮されたブロックに変換する手段を更に含み、それによって、前記データ・セットを前記圧縮標準の下で記憶することができ、前記選択された圧縮されたブロックの前記予測されたブロックへの割当ては、一般に、前記予測されたブロックが前記変換手段によって圧縮されたかのように見え、このシステムは、更に、前記離散コサイン変換エンジン、前記推論エンジン及び前記割当手段を動作させて、前記データ・セットを前記圧縮標準から前記非圧縮標準に変換する手段を更に備えている。
【００１９】
更に別の好適実施例では、本発明は、データ・セットを非圧縮標準から圧縮標準に変換するデータ圧縮システムであって、前記データ・セットは前記圧縮標準の下で記憶媒体に記憶されているときの方が非圧縮標準の下で記憶されているときよりも必要とする空間が小さいようなデータ圧縮システムにおいて実現される。このシステムは、圧縮されていない前記データ・セットを複数の圧縮されていないブロックに配分する手段を含む離散コサイン変換エンジンと、前記ブロックのそれぞれを所定の基準に従って操作し、前記操作されたブロックのそれぞれを所定の組の圧縮されたブロック標準と比較することによって、前記ブロックを予測されたブロックと予測されていないブロックとに分割するように構成された推論エンジンと、前記推論エンジンによってなされた比較に基づき、複数の圧縮されたブロックの中の選択された１つを前記予測されたブロックのそれぞれに割り当てる手段とを備えており、前記離散コサイン変換エンジンは、前記予測されていないブロックを圧縮されたブロックに変換する手段を更に含み、前記推論エンジンは、前記ブロックをサブブロックに分割する手段と、サブブロックの内部において規則的に現れる何らかの組合せを予測する手段とを含み、それによって、前記データ・セットを前記圧縮標準の下で記憶することができ、前記選択された圧縮されたブロックの前記予測されたブロックへの割当ては、一般に、前記予測されたブロックが前記変換手段によって圧縮されたかのように見える。
【００２０】
本発明の上述した及びそれ以外の目的及び効果は、以下のより詳細な説明を添付の図面を参照して読むことによって明らかになるはずである。
【図面の簡単な説明】
【００２１】
【図１】従来技術によるＪＰＥＧエンコーダのブロック図である。
【図２】本発明によるＪＰＥＧエンコーダのブロック図である。
【図３】本発明によるエンコーダのブロック図である。
【図４】データ・コンパイラ・ルーチンの流れ図である。
【図５】テーブル構築ルーチンの流れ図である。
【図６】第１の組の予備的ＤＣＴ計算のテーブルである。
【図７Ａ】第２の組の予備的ＤＣＴ計算のテーブルである。
【図７Ｂ】第２の組の予備的ＤＣＴ計算のテーブルである。
【図８】ＤＣＴ係数を表すデータ・ブロック・セルの第１のグループのテーブルである。
【図９】ＤＣＴ係数を表すデータ・ブロック・セルの第２のグループのテーブルである。
【図１０】ＤＣＴ係数を表すデータ・ブロック・セルの第３のグループのテーブルである。
【図１１】ＤＣＴ係数を表すデータ・ブロック・セルの第４のグループのテーブルである。
【図１２】ゼロ予測ルーチンの流れ図である。
【図１３】非ゼロ予測ルーチンの流れ図である。
【図１４】従来型のジグザグ・テーブルである。
【発明を実施するための形態】
【００２２】
以下の説明では、複数の異なる図面における同じ又は対応する要素を参照するために、同じ参照番号が用いられる。
図２及び図３を参照すると、本発明は、広くは、圧縮されていないデジタル・データの形式でイメージを受け取る入力インターフェース３２を有するエンコーダ３０に関する。イメージは、ＲＢＧやＣＭＹＫフォーマットなど多様なカラー・フォーマットで表されうるから、カラー変換ドライバ３４が、必要である場合には、カラー・イメージを、ＪＰＥＧ標準によって用いられるカラー・イメージのためのＹＣｂＣｒフォーマットに変換する。ユーザが選択可能でＪＰＥＧ標準において開示されているデータ値の従来型のコマンド・セット３６によって、ユーザは、圧縮プロセスの間、何らかの基準を選択することができ、それによって、例えば、ユーザは、希望するイメージの質との関係における希望する圧縮の程度を調整することができる。圧縮エンジン３８は、メモリ４０に接続されており、ＹＣｂＣｒフォーマット・イメージとコマンド・セット・データ値とを受け取って、コマンド・セット・データ値によって決定される基準に従ってイメージ・データを圧縮する。メモリ４０は、好ましくは、圧縮エンジン３８によって圧縮プロセスを実行するのに用いられるプログラム・ソフトウェア及びデータを含む。圧縮エンジン３８は、出力インターフェース３９に接続しており、出力インターフェース３９は、圧縮されたＪＰＥＧフォーマットでのイメージを他のデバイスに伝送する。本発明によるエンコーダ３０は、ソフトウェア又はハードウェア構成として実現することができる。入力及び出力インターフェースは、エンコーダ３０のハードウェア及び／又はソフトウェアとしての実現とは独立に、ハードウェア又はソフトウェアいずれかとして実現されたデバイスと協働することは理解できるであろう。
【００２３】
本発明は、更に、圧縮エンジン３８（図３）と関係する。圧縮エンジン３８は、最初にイメージ・データを８ｘ８のピクセル・ブロック４４に分割し次にＤＣＴ４５のためにデータを初期化するＤＣＴエンジン４２を含む。カラー・イメージの場合には、ピクセルのそれぞれの８ｘ８のグルーピングは、カラー・チャネルＹＣｂＣｒのそれぞれを表すピクセルの３つの８ｘ８ブロックを含む。これらの８ｘ８データ・ブロックは、ＪＰＥＧ標準に従って従来型の態様でイメージから分割される。好ましくは、イメージ・データのブロックへの分割の後で、ＤＣＴエンジンを用いた従来型の圧縮プロセスが中断される（割り込みがなされる）。
【００２４】
予測エンジン４６は、８ｘ８のデータ・ブロックのそれぞれを受け取り、これらのブロックを、又はカラー・イメージの場合には３つのブロックのグループを、予測されたブロックと予測されていないブロックとに分割するように動作する。予測されていないブロックはＤＣＴエンジンに戻され、そこで、これらの予測されていないブロックは、従来型のＪＰＥＧ標準に従い、ＤＣＴ変換４８と量子化器５０とを従来的に用いて作用される。好ましくは、予測されたブロックは、従来型のＤＣＴエンジン４２の下でのそれ以降の処理は受けない。そうではなく、予測されたブロックは、予測符号化エンジン４６によって符号化され、予測されたブロックに対して所定のＪＰＥＧ圧縮されたブロックが割り当てられる。予測されたブロックのそれぞれに対しては、ＤＣＴエンジン４２を用いたブロックの従来型の処理を除去することによって、実質的な時間的な節約が達成される。これは、離散コサイン変換を実行するのに要求される反復的なプロセスが除去されるからである。予測エンジンが動作するのに要求される時間は、ＤＣＴプロセスよりもはるかに短い。従って、１つのイメージに対してほんの僅かなデータ値だけが予測されている場合であっても、著しい時間的な節約が達成される。
【００２５】
好適実施例では、予測エンジンは、２つの代替的な好適実施例として実現されうる。すなわち、ゼロ予測エンジンと非ゼロ予測エンジンとであって、それぞれのエンジンが、規則的に生じることが知られているデータ値の既知の組合せを予測する。ゼロ予測エンジンによるプロセスは、８ｘ８データ・ブロックのそれぞれに一連のテストを行い、これらのブロックが、圧縮された値のすべて又はほとんどがゼロに等しい既知の圧縮結果と一致するかどうかを予測する。非ゼロ予測エンジンによるプロセスでは、データ値は、処理され、圧縮結果が既知である既知のデータ値の組と比較される。第２の段階におけるデータ・セットが既知のデータ値の組と一致する場合には、そのデータ・セットの圧縮結果は、データ値に割り当てられる。予測エンジン４６はゼロ予測エンジン又は非ゼロ予測エンジンのいずれか一方を有していると理解されうる。ゼロ予測エンジンと非ゼロ予測エンジンとのいずれを用いるのかという選択は、エンコーダが用いられる実現環境に依存している。特に、非ゼロ予測エンジンは、データ・テーブルに依拠して８ｘ８データ・ブロックを予測する。このためには、従来型のデジタル信号処理（ＤＳＰ）用集積回路のためのメモリ容量を超える追加的なメモリが必要となり、従って、別個の外部メモリが必要となる。外部メモリが好ましくない場合には、ゼロ予測エンジンの方が好ましいであろう。
【００２６】
また、ＤＳＰ集積回路の強化された特徴が選択に影響することがある。従来型のデバイスによっては、データ・テーブルにとって理想的であるベクトル・アドレシングのために、強化されているものがある。他のＤＳＰ回路でも、ゼロ予測エンジンの処理時間を短縮する強化された特徴を有しているものもある。従って、ゼロ予測エンジンと非ゼロ予測エンジンとのどちらを用いるのかを判断する際には、設計者は、プロセッサのハードウェアとしての特徴とデバイスのメモリ容量とを均衡させなければならない。空間が最重要である場合には、ゼロ予測エンジンが好ましいであろう。メモリが利用可能であるのであれば、非ゼロ予測エンジンが好ましいであろう。
【００２７】
予測エンジン４６は、３つのカテゴリのデータ出力を生じる。すなわち、（１）予測されたブロック、（２）予測されていないブロック及び（３）部分的に予測されたブロックである。予測されたブロックとは、予測が成功し、圧縮結果が予め割り当てられている８ｘ８データ・ブロックである。予測されていないブロックとは、データ値がいずれも予測されず、その中に含まれているデータにはＤＣＴプロセス４８のためにタグが付されているようなブロックである。予測されていないブロックの圧縮は、従来の態様でＤＣＴエンジン４２と量子化器５０とを用いて達成される。部分的に予測されたブロックは、所定の圧縮結果が割り当てられている８ｘ８データ・ブロックの予測された部分を有している。８ｘ８データ・ブロックの予測されていないブロックは、従来の態様でＤＣＴエンジン４２と量子化器５０とを用いて圧縮を行うためにタグが付される。
【００２８】
データの処理は、エントロピ・エンコーダ５６によって完了する。このエンコーダ５６は、好ましくは、ＪＰＥＧ標準によって提供されるホフマン（Ｈｏｆｆｍａｎ）テーブルが従来の態様で用いられホフマン・プロセスの処理を高速化しているホフマン圧縮アルゴリズムに基づいている。好適実施例では、予測されたブロックはエントロピ・エンコーダによって処理されていない。というのは、これらのブロックに割り当てられた圧縮結果はエントロピ・エンコーダ５６の結果を既に含んでいるからである。部分的に予測されたブロックについては、ホフマン・テーブルを修正して、部分的な圧縮結果のために調整された結果を含むようにすることができる。しかし、ホフマン・プロセスは、ＪＰＥＧ標準に記載されているように動作する。
【００２９】
すべての例において、Ｂ領域における予測を仮定する。すなわち、Ｂ１…Ｂ４は予測値を有する。
ＤＣＴ係数のジグザグな順序が図１４に示されている。
【００３０】
数字は、ホフマン・プロセスが開始する前のＤＣＴ係数の最終的な順序を表している。
図１４の係数０…９，１１…１３，１７，１８，２４は、ＡＡ＠領域内にあることに注意すべきである。これ以外のすべての係数は、ＡＢ＠領域にある。
【００３１】
第１の例は次の通りである。Ａ１…Ａ４はどの予測にも等しくなく、Ｂ１…Ｂ４は予測に等しい。ホフマン組合せのために作成されたルックアップテーブルのサイズに応じていくつかのオプションが存在する。
【００３２】
第１のオプションは、係数２４まで通常のホフマンを実行することである。そこからは、ゼロのランレングスと４つの予測符号とを用いて継続し、係数２４ないし６４から結果として完全なホフマン符号を与える５つの層を有するルックアップテーブルに至る。
【００３３】
第２のオプションは、係数１，１８，２４を考慮することである。ＪＰＥＧ仕様において定義されている通常のホフマン符号化プロセスを係数１３まで実行する。そこからは、係数１３までゼロのランレングスを用いて、係数１７，１８，２４と４つの予測符号とをルックアップテーブルに至るまで継続する。ルックアップテーブルの結果は、係数１３ないし６４からの完全なホフマン符号である。
【００３４】
第２の例は次の通りである。Ａ１は予測されており（係数４，１１，１３，２４）、Ａ２…Ａ４はどの予測にも等しくなく、Ｂ１…Ｂ４は予測に等しい。
第１のオプションは、係数１９まで通常のホフマンを実行することである。そこからは、係数１９までのゼロのランレングスと５つの予測符号（Ａ１，Ｂ１…Ｂ４）とを用いてルックアップテーブルに至るまで継続する。
【００３５】
第２のオプションは、係数０まで通常のホフマンを実行することである。そこからは、係数９までゼロのランレングスを用いて、係数１２，１７，１８と５つの予測符号（Ａ１，Ｂ１…Ｂ４）とをルックアップテーブルに至るまで継続する。
【００３６】
第３の例は次の通りである。Ａ１，Ａ２は予測と等しく（係数２，４，７，９，１１，１３，１８，２４）、Ａ３…Ａ４は予測されていない。Ｂ１…Ｂ４は予測に等しい。
第１のオプションは、係数９まで通常のホフマン符号化プロセスを実行することである。そこからは、係数９までのゼロのランレングスを用いて、係数１２，１７と６つの予測符号（Ａ１，Ａ２，Ｂ１…Ｂ４）とをルックアップテーブルに至るまで継続する。
【００３７】
エントロピ・エンコーダ５６の処理の後では、圧縮形式のイメージ・データが、他のデバイスによって用いられるために出力インターフェース３９に伝送される。エンコーダ３０によって提供された圧縮データは、ＪＰＥＧ標準に一致する。従って、従来のＪＰＥＧファイルと共に用いるように設計された任意のハードウェア又はソフトウェア・デバイスが、本発明によって提供されるデータを用いることができる。
予測エンジン−ＤＣＴエンジンの準備：
好適実施例の予測エンジンに更に焦点を合わせると、予測エンジンは、データ・ブロックをそれらがＤＣＴエンジンによる処理の準備ができた後で調べることによって動作する。従って、ＤＣＴエンジンによって従来的に提供される当初のステップを調べることが、まず必要である。既に述べたように、ＤＣＴエンジンは、イメージ・ファイルを、それぞれのブロックが６４ピクセルのイメージ情報を含む８ｘ８のデータ・ブロックに分割する。カラーの場合には、カラー・イメージのそれぞれの成分に対して、別々の８ｘ８のデータ・ブロックが存在する。ＤＣＴエンジンは、更に、８ｘ８のデータ・ブロックのそれぞれを、４つのグループの予備的ＤＣＴ計算値に分割する。ここで、それぞれのグループは、１６個の値で構成されている。グループの選択とその構成は、選択された量子化テーブルに従って決定される。量子化テーブルの選択は、圧縮されたデータ・ファイルのイメージの質と圧縮率とに関係し、変動しうる。好適実施例では、量子化テーブルは、図４に示されているように選択され、Ａ＝４及びＢ＝１６という量子化定数がイメージの質を提供する。ここで、イメージ損失は、人間の目によって検出可能なスレショルドよりも下であることが一般的であり、平均では、１：８の圧縮率を提供する。この特定の量子化テーブルは、ゼロ予測段階にとって望ましい。
【００３８】
データ値を４つのグループのデータ値係数に処理することは、ＤＣＴエンジンによって従来型の態様で行われる。４つのグループがそこから導かれるデータの８ｘ８のブロックは、図５に図解されている。この図５では、情報のそれぞれのピクセルは、値Ｖ（ｉｊ）によって表される。ただし、０から７のローはＡｉ＠で表され、０から７のコラムはＡｊ＠で表される。現在の量子化テーブルのためのＤＣＴ係数を決定することは、それぞれのコラムの成分を次の方法で減算及び加算することによって開始される（？Ｄ＠の値は差すなわち減算のステップを表し、？Ｓ＠の値は和すなわち加算のステップを表す）：
ｊ＝０から７に対しては次のようになる。
【００３９】
【表１】
2011103665.tif 000003
図６を参照すると、計算の結果は、それぞれのコラムに対して同じ８ｘ８のマトリクス形式に保存される。
【００４０】
【表２】
2011103665.tif 000004
当業者であれば理解するように、このプロセスは、異なるコラムに関する計算を同時的に実行することができるようにハードウェア的に実現されてもソフトウェア的に実現されても、その性質上、非常にパラレルである。このプロセスによって形成される８ｘ８のマトリクスは、減算グループと加算グループとを含み、それぞれのグループは、３２個の値からなる８ｘ４のマトリクスで構成される。
【００４１】
これらのグループを更に分割するために、図７Ａ及び図７Ｂに示されているように、加算及び減算のステップが図６の８ｘ８マトリクスに対してコラムの間で実行される。その結果は６４個の値であるが、これらの値は、図８ないし図１１に図解されているように、次のグループに分割可能である。
【００４２】
グループＩは、減算だけが行われた１６個の値を含み、これらは、Ｇ（−）（−）として識別される。図８に図解されているように、グループＩは、ｊ＝０から３に対して、Ｄ０，ｊ，７−ｊ，Ｄ１，ｊ，７−ｊ，Ｄ２，ｊ，７−ｊ，Ｄ３，ｊ，７−ｊとして定義される。これらの１６個の値は、８ｘ８のＤＣＴ係数マトリクスにおいて図８に示されているように配列されている１６個のＤＣＴ係数の値にグループとして一意的に対応する。予測エンジンは、グループＩの値と１６個のＤＣＴ係数との間に１対１の対応を要求することはない。これらの値が、マトリクスの中の示されている位置にある１６個のＤＣＴ係数に集合的に対応していれば十分である。
【００４３】
グループＩＩは、第１に減算が第２に加算が行われた１６個の値を含み、これらは、Ｇ（−）（＋）として識別される。図９に図解されているように、グループＩＩは、ｊ＝０から３に対して、Ｓ０，ｊ，７−ｊ，Ｓ１，ｊ，７−ｊ，Ｓ２，ｊ，７−ｊ，Ｓ３，ｊ，７−ｊとして定義される。これらの１６個の値は、８ｘ８のＤＣＴ係数マトリクスにおいて図９に示されているように配列されている１６個のＤＣＴ係数の値にグループとして一意的に対応する。グループＩの場合と同様に、これらの値については、１対１の対応は要求されない。
【００４４】
グループＩＩＩは、第１に加算が第２に減算が行われた１６個の値を含み、これらは、Ｇ（＋）（−）として識別される。図１０に図解されているように、グループＩＩＩは、ｊ＝０から３に対して、Ｄ４，ｊ，７−ｊ，Ｄ５，ｊ，７−ｊ，Ｄ６，ｊ，７−ｊ，Ｄ７，ｊ，７−ｊとして定義される。これらの１６個の値は、８ｘ８のＤＣＴ係数マトリクスにおいて図１０に示されているように配列されている１６個のＤＣＴ係数の値にグループとして一意的に対応する。
【００４５】
グループＩＶは、加算だけが行われた１６個の値を含み、これらは、Ｇ（＋）（＋）として識別される。グループＩＶは、ｊ＝０から３に対して、Ｓ４，ｊ，７−ｊ，Ｓ５，ｊ，７−ｊ，Ｓ６，ｊ，７−ｊ，Ｓ７，ｊ，７−ｊとして定義される。グループＩないしＩＩＩの場合とは異なり、グループＩＶには、次に示すように１６個の値について減算ステップが実行される第３の演算がなされる：
【００４６】
【表３】
2011103665.tif 000005
図１０に図解されているように、これらの１６個の値は、グループとして、８ｘ８のＤＣＴ係数マトリクスにおける図１０に示されているように配列された１６個のＤＣＴ係数の値に一意的に対応する。
ゼロ予測エンジン：
４組の１６個のＤＣＴ係数に対応する４つのグループの計算は、従来は、すべて、８ｘ８のデータ・ブロックに対して離散コサイン変換を実行する際の予備的なステップとして、ＤＣＴエンジンによってなされる。しかし、ＤＣＴエンジンによるそのような計算が開始される前に、予測エンジンが、これら４つのグループに対して予測動作を実行する。ゼロ予測動作は、図１２に概要が示されており、４つのグループのそれぞれに対して、ゼロ予測テストが実行されている。それぞれのグループに対して、ステップ８０において、最初に、１６個の結果の最大絶対値（ＬＡＶ）がプロセスによって決定される。
【００４７】
この決定は、絶対値が決定される任意の従来型のソート又は比較技術を用いて実行することができる。例えば、プロセスは、次のステップを含みうる。
【００４８】
【表４】
2011103665.tif 000006
上に示されているように、第１の値のグループｌ（ｘ）でシリアルに始まる１６個の値を素早く比較することの結果として、１５のサイクルに続くグループの最大の絶対値を含むＬＡＶが得られる。この分野の当業者であれば理解するように、データ・セットから最大の絶対値を決定するには、これ以外にも従来型の方法が数多く存在する。ある種のハードウェア・デジタル信号処理集積回路に対しては、この絶対値は、回路内部のハードワイアード・コマンドである。
【００４９】
最大絶対値（ＬＡＶ）を決定すると、ステップ８２において、このＬＡＶは、量子化定数Ａの１．５倍よりも小さいか等しいかを決定するために、比較される。好適実施例では、Ａは４に等しく、ＬＡＶは、ＬＡＶ＃６であるかどうかを判断するために比較される。ＬＡＶが１．５＊Ａ以下である場合には、グループＸに対するすべての結果はステップ８４においてゼロにセットされ、次のグループがステップ８６で処理される。そうでない場合には、プログラムは、データのテストを継続する。
【００５０】
ステップ８８における次のテストでは、ＬＡＶが量子化値Ｂの１．５倍以下であるかどうかを比較する。好適実施例では、量子化値Ｂは１６であるから、ＬＡＶはステップ８８においてＬＡＶ＃１８であるかどうかを判断するために比較される。ＬＡＶが１．５＊Ｂ以下である場合には、Ｂに対応する１２個の値はステップ９０においてゼロにセットされ、２４個の値の中の４つの残りの値は、従来型のＤＣＴによる計算のためにタグが付けられる。ＤＣＴエンジンは、予測エンジンの動作中又は完了時における割り込みによって開始される。ＤＣＴエンジンをいつ実現するかという決定は設計事項であって、予測エンジンの動作環境に依存する。次に、プログラムは、ステップ８６において次のグループ（Ｘ）をコールする。以上と異なりＬＡＶが１．５＊Ｂよりも大きい場合には、予測された結果は得られず、１６個の値すべてが、ＤＣＴプロセスによる従来型の圧縮のためのタグが付される。次に、プログラムは、ステップ８６において次のグループ（Ｘ）をコールする。グループ４に対する予測エンジン４６が完了すると、従来型のＤＣＴ処理のためにタグが付されたデータ・ブロックの一部が、ステップ４２において更なる処理のためにＤＣＴエンジンに伝送される。やはり理解されうることであるが、伝統的なＤＣＴ処理４８のためのタグが付された値は、予測エンジン４６がそのシーケンスを終了する間にＤＣＴエンジン４２のパラレルな処理を提供するという発見の後であれば、任意の時点で伝送することができる。
非ゼロ予測エンジン：
すでに述べたように、非ゼロ予測エンジンを、ゼロ予測エンジンに代わりに実現することができる。図１３の流れ図を参照すると、非ゼロ予測エンジンのプロセスは一連のルックアップ・テーブルを有し、それぞれのテーブルはグループＸからの１６個の値の１つに対応している。テーブル・ポインタが従来型の態様で用いられ、テーブルにおける誘導を行っている。非ゼロ予測ルーチンに入ると、テーブル・ポインタは、ステップ９６で初期化され、１６個の値の第１の値を読み出す。次に、非ゼロ予測プロセスは、ステップ９８において、グループＸ（ｙ）で開始するグループＸの値のそれぞれに対するループに入る。ここで、ｙ＝１から１６である。１６個の値のそれぞれに対して、値は、ステップ１００において読み出される。グループＸ（ｙ）の値の大きさは、−７から＋７までの範囲に対応するものに変換される。ステップ１０２では、値が所望の範囲に含まれるかどうかが判断される。値が所望の範囲に含まれている場合には、プログラムは先に進む。そうでない場合には、プログラムはステップ１０４で出ることになり、予測はなされない。ステップ１０２におけるチェックの次には、グループＸ（ｙ）の値がポインタの値に加算され、ステップ１０６においてテーブルの中のレコードを参照（ルックアップ）するのに用いられる。ステップ１０８では、レコードの値がチェックされる。レコードが？ｚｅｒｏ＠である場合には、グループＸに関する予測は存在しない。プログラムは、ステップ１１０において値の次のグループをコールする。そうでなく、値がゼロに等しくない場合には、ポインタは、ステップ１１２においてテーブル・レコード値にセットされる。ステップ１１４においてグループＸの次の値がコールされ、ステップ１００から１１４が、１６個の値すべてが処理されるまで反復される。１６個の非ゼロであるテーブル・レコードを集めることに成功すると、グループＸ（１６）の処理の間のポインタには、グループＸに対する圧縮されたデータに対応する予測符号が割り当てられる。予測エンジンの動作が成功であると、グループＸの値すべてが予測された値であり、グループＸのＤＣＴ処理は不要である。
第２ステージのテーブル・レコードに対する基準：
この技術分野の当業者には明らかであるように、予測エンジンによって実行される第２ステージ５４のシーケンスは、従来型のルックアップ・テーブル・シーケンスである。第２ステージ５４から達成される時間節約パフォーマンスは、第２ステージの各ステップの単純性と、第２ステージのプロセスが非ゼロ・ブロックを予測することを可能にするルックアップ・テーブルの作成とによって得られる。ルックアップ・テーブルは、予測エンジンがハードウェアとして実現されているのかソフトウェアとして実現されているのかというようなアプリケーションに特有の基準に従って変動しうることも理解されるであろう。更に、テーブルは、用いられる量子化の方法に適するように作られる。
【００５１】
一般的に、ルックアップ・テーブルを作成する際には、次の基本的な仮定が用いられる。
１．ＪＰＥＧ標準は、ＤＣＴ係数の特定の組合せが８ｘ８ＤＣＴ係数の与えられたマトリクスにおける結果の平均９０％超で構成されていると想定することによって、情報を圧縮する。
【００５２】
２．これらの共通の組合せは、エントロピ・エンコーダに含まれるホフマン・テーブルにおける少数のビットによって表される。
３．これらの事実に基づくと、例えば、上述のＤＣＴエンジンによって準備されたような１６個の値からなる各グループに対して少数の組合せを選択することが可能である。
【００５３】
４．各グループに対して、？Ｂ＠に対するゼロと１との組合せは図５であり、−７から７までなどのより高い組合せである。
５．共通の組合せを選択するための一般的なルールは、ＪＰＥＧ標準によって提供されるＪＰＥＧホフマン・テーブルに基づいている。？Ｂ＠領域に対しては、共通の組合せのいくつかでは、１つの係数は１又は−１に等しく、Ｂ領域を構成する１２の中の残りの１１の値はゼロである。これにより、この共通の特徴を共有する組合せが、全部で２４あることになる。
【００５４】
６．驚くべきことに、４つのグループの中の１つを構成する１６個の値を調べると、共通のＤＣＴ組合せに対応する共通の組合せは比較的少数しか存在しないことが発見された。ルックアップ・テーブルを有する予測エンジンを構築するシステムは、１９９８年１０月２日に出願された米国特許出願第０９／１６５，５３５号に開示されている。この米国出願は、本出願で援用する。
【００５５】
ＤＣＴ係数の処理を通常のように行った後で、ホフマン・テーブルを最適化することが可能である。最初には、各グループに対するＡ及びＢ領域に予測符号を割り当てる。例えば、グループＩの予測符号はＡ１、Ｂ１であり、グループＩＩの予測符号はＡ２、Ｂ２であり、等である。従って、各グループに割り当てられた予測符号が存在し、１つの予測値が予測のないことを意味することもありうる。
【００５６】
上述の例から、ある点から最後までの完全なホフマン符号を結果的に生じる予測された及び予測されていない結果に基づいてルックアップ・テーブルを作成することができることを理解できるであろう。このテーブルは、データの部分的に予測されたブロックに対するホフマン符号化システムの処理を更に高速化することになる。
符号化のための使用：
本発明による予測エンジンを組み入れたエンコーダは、光スキャナ、デジタル・カメラ、デジタル・ビデオ・ディスク・ドライブなど、様々なイメージ処理装置において用いることができる。このような実現例は、エンコーダが従来型のデジタル信号プロセッサ（ＤＳＰ）において実現するハードウェアの形態で達成できる。あるいは、エンコーダを、汎用コンピュータ上のソフトウェア・アプリケーションと共に用いるソフトウェアとして実現することもできる。ソフトウェアの場合には、エンコーダは、インターネット・ブラウザ、イメージ・ビューワ及びＭＰＥＧプレーヤなどのアプリケーションにおいて用いることができる。
【００５７】
第１の好適なアプリケーションでは、エンコーダは、光スキャナのための通信チップセットと共に含まれる。時間を節約する予測機能を備えたエンコーダによって、スキャナは、従来型のＴｉｆｆファイル・フォーマットの場合、又は、従来型のＪＰＥＧエンコーダを用いるときよりも、はるかに高速で圧縮されたＪＰＥＧイメージを記憶媒体に提供することができる。
【００５８】
第２の好適なアプリケーションでは、エンコーダは、メモリ空間が最重要である際に、デジタル・カメラにおいて実現される。ある実施例では、このビデオ・デバイスは、パーソナル・ビデオ・レコーダ（ＰＶＲ）である。このエンコーダは、ＪＰＥＧイメージのカメラの内部メモリへの転送及び記憶を高速化する。これによって、デジタル・カメラを、従来型の自動アドバンス・カメラや早取り（ｒａｐｉｄ−ｓｈｏｏｔ）カメラをエミュレートするような態様で用いることが可能になる。
ハード・ドライブの圧縮：
本発明の予測エンジンが他の圧縮アプリケーションと共に用いることができることは理解されよう。例えば、ハード・ドライブ・コントローラが記憶媒体とコンピュータ・バスとの間におけるリアルタイムでのデータの記憶及び転送を扱っているハード・ドライブ上へのデータの記憶がある。
【００５９】
そのようなアプリケーションでは、ハード・ドライブに加える前に、様々なタイプのデータを識別及び記憶することが望まれる。考慮されるデータのタイプには、これらに限定されるのではないが、バイナリ・ファイル、テキスト・ファイル、グラフィクス・ファイル、テキスト、バイナリ又はグラフィクスの内容を含みうる圧縮されたバイナリ・ファイルなどが含まれる。識別と圧縮とは、リアルタイムで生じなければならず、そうでなければ、コンピュータ・バスとハード・ドライブとの間におけるデータ転送に遅延が生じる。このようなアプリケーションでは、データのフォーマットを識別する際に、予測エンジンを備えているエンコーダを用いてデータを圧縮することができる。
【００６０】
テーブルを用いた予測エンジンの第２の実施例を用いて、イメージ・ファイルだけでなくバイナリのテキスト及び圧縮ファイルのためのエンコーダを作ることができる。このような予測エンジンは、同様の選択基準に従うのであるが、圧縮方法の追加的な選択と、データのフォーマット又はタイプを表すデータの選択とが必要となる。予測エンジンのための基準は、ハード・ドライブ・コントローラが考慮されている予測エンジンのタイプを選択する能力及び速度を考慮することも必要となる。
低メモリ予測エンジン：
この分野の当業者であれば理解するように、本発明による予測エンジンを、デジタル・カメラなどの小型の装置の場合のような限定されたメモリを有するハードウェア環境において用いることができるような場合は、数多い。そのような環境では、装置のサイズや様々な容量が、予測エンジンに用いることができるメモリの量を制限する。既に述べたように、テーブル・サイズをメモリの拘束を満たすように制限するには、イメージの質とそのイメージを符号化するのに要求される処理時間との間のバランスが必要となる。
【００６１】
幸い、ゼロと１との組合せに対するルックアップテーブルは、低メモリ環境に対して最適化が可能である。以下の手順によって、そのような低メモリ環境に対してルックアップテーブルの情報を最適化するコンパイラの中に別個の副手順として含まれる実現例が明らかになろう。
【００６２】
このプロセスは、１６個の値の４つのグループであるＧ（−）（−）、Ｇ（−）（＋）、Ｇ（＋）（−）、Ｇ（＋）（＋）それぞれに対して独立に作用する。
この最適化は、１６個の値の次のグループを参照することによってもっともよく理解される。ただし、それぞれのｐｉｊは、−５１２から５１２間での値を含み、ｉ＝１から４であり、ｊ＝１から４である。
【００６３】
【表５】
2011103665.tif 000007
生じうる１６個の値の共通の組合せを識別することによって、ルックアップテーブルが最適化される。共通の組合せは、単純な基準に従って共通の値を分離することによって別々に識別される。１６個の値のそれぞれに対して、１０２４（１キロバイト）個のデータ・エントリを有する別個のルックアップテーブルがある。各エントリは、２つのオプションにカテゴリ化（カテゴリ分け）される。
１．「拒絶値」（ｒｅｊｅｃｔ  ｖａｌｕｅ）と、２．この特定の値のＤＣＴ寄与を表す「符号数」（ｃｏｄｅ  ｎｕｍｂｅｒ）と、である。
【００６４】
「拒絶値」と「符号数」とを区別するスレショルドは、用いられたテスト・イメージから収集された統計的な情報に従って選択されるので、変動することがありうる。例えば、汎用的なアプリケーションに対する統計では、ｐ１１が−８０＜＝ｐ１１＜＝８０の範囲の値を有するときには、ゼロと１との組合せの９５％の識別が達成されうる。
【００６５】
従って、ｐ１１に対するテーブル・エントリは、次のようになる。
１．−８０＜＝ｐｉｊ＜＝８０の場合には、テーブル・エントリはＤＣＴ符号数を含む。
２．−８０＞ｐｉｊ＞８０の場合には、テーブル・エントリは拒絶値を含む。
【００６６】
このスレショルド値は、次のような長所を有する。
１．ｐｉｊが特定の値の範囲に含まれるかをチェックし、含まれない場合には、予測エンジンから外に出る。
２．すべての値に対してＤＣＴ結果を前もって計算し、それを、「ＤＣＴ符号数」を用いて表す。
このスレショルド・プロセスは、値のそれぞれに対して実行される。
【００６７】
ルックアップテーブルの値の結果は、次のように定義される。
【００６８】
【表６】
2011103665.tif 000008
ここでは、次のような加算が生じる。
【００６９】
【表７】
2011103665.tif 000009
８つの値それぞれに対して、各エントリに対して同じ構造を有する別個のルックアップテーブルが作成される。ここで、各エントリは、１．拒絶値、又は２．ＤＣＴ符号である。
再び、統計的なデータが、各エントリに対するスレショルド値を決定するのに用いられる。ルックアップテーブルの結果は、次のように表すことができる。
【００７０】
【表８】
2011103665.tif 000010
これらの値には次の加算が行われる。
【００７１】
【表９】
2011103665.tif 000011
再び、このプロセスが反復される。４つの値のそれぞれに対して、各エントリに対して同じ構造を有する別個のルックアップテーブルが作成される。ここで、各エントリは、
１．拒絶値、又は
２．ＤＣＴ符号である。
【００７２】
このプロセス全体は、ＤＣＴ符号がただ１つしか存在しなくなるまで反復される。予測エンジンのルックアップテーブルを作るためにこのプロセスを用いることによって、ルックアップテーブルによって用いられるメモリの量を著しく減少させることができる。ほとんどの一般的な応用例では、ルックアップテーブルは、ほぼ３２キロバイト以下のメモリに維持することができる。
【００７３】
以上で開示した内容は、本発明の単なる例示である。これ以外の構成や方法を、当業者であれば、本発明の精神及び範囲から逸脱することなく実現することができる。
いくつかの特徴や下位の組合せ（サブコンビネーション）は有用であり、特許請求の範囲に記載されているそれ以外の特徴や下位の組合せを参照しなくとも用いることができる。本発明の好適な実施例や応用例を以上で説明したが、当業者には、本発明の目的及び特徴は冒頭の特許請求の範囲によってのみ限定されることは明らかである。
【符号の説明】
【００７４】
３８…データ圧縮エンコーダ、４２…離散コサイン変換エンジン、４６…推論エンジン
【図１】
2011103665.tif 000012
【図２】
2011103665.tif 000013
【図３】
2011103665.tif 000014
【図４】
2011103665.tif 000015
【図５】
2011103665.tif 000016
【図６】
2011103665.tif 000017
【図７Ａ】
2011103665.tif 000018
【図７Ｂ】
2011103665.tif 000019
【図８】
2011103665.tif 000020
【図９】
2011103665.tif 000021
【図１０】
2011103665.tif 000022
【図１１】
2011103665.tif 000023
【図１２】
2011103665.tif 000024
【図１３】
2011103665.tif 000025
【図１４】
2011103665.tif 000026