JP2575595B2 - イメージフレームの圧縮方法及びデータ処理システム - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はデータ処理システム上の
記憶及びデータ処理システム間の伝送のためのビデオ情
報の圧縮に関する。特に、本発明は所定のエラー許容度
内でイメージ（画像）フレームのパターンとライブラリ
パターンとを整合するためのシステム及び方法に関す
る。

【０００２】

【従来の技術】ビデオ信号はフレームのシーケンスから
成り、所定の最小のフレーム率で表示されると（例え
ば、パーソナルコンピュータで１秒あたり15フレームか
ら30フレーム）、そのフレームのシーケンスは観察者に
とって動きの外観をシミュレートする。パーソナルコン
ピュータシステムにおいて、ビデオイメージの各フレー
ムは画素、即ち、「ピクセル(pixel) 」のマトリックス
から成る。一般的なイメージマトリックスは320 列ｘ24
0 行のピクセルを有する。ピクセルは輝度の強度、及び
カラービデオにおいては色が割り当てられるピクチャの
最小の単位である。使用されるデータフォーマットに応
じて、３バイトまでのデータがピクセルで視覚的な情報
を定義するために使用される。フレーム全体の全てのピ
クセルのピクセル毎の色を説明するには、２０万バイト
のデータを必要とする。

【０００３】ビデオセグメントを表示するために当該フ
ルフレームが１秒あたり30フレームで置換されたなら
ば、コンピュータは記憶装置から１秒あたり３千万バイ
トまでのデータを取り出し、ビデオメモリに書き込む必
要がある。現在、そうした大量のデータを渡すために必
要な帯域幅、或いは、直接記憶された数分に値するディ
ジタルビデオ情報より多い情報を保持するための記憶容
量、の双方を有する大容量データ記憶装置は殆どない。
本明細書で用いられるように、帯域幅は補助記憶装置か
ら取り出し可能な単位時間あたりのデータの量を意味す
る。データ圧縮は、リアルタイムで再生するためにビデ
オセグメントの記憶部及び取り出し部で補助記憶装置を
収容し、システムバスのトラフィックを減少するために
用いられる。

【０００４】データ圧縮によって、イメージ又はビデオ
セグメントがフルフレーム再生に必要なデータより実質
的にバイトが少ないデータで伝送及び記憶されるのが可
能になる。データ圧縮は、ディジタル化されたビデオセ
グメントにおけるフレームからフレームへの冗長な情報
を取り除くこと（時間的圧縮）、或いは、個々のフレー
ムにおけるピクセルからピクセルへの冗長な情報を取り
除くこと（空間的圧縮）に基づく。更に、圧縮によっ
て、ピクセルのブロックにおける色を平均化すると共に
輝度の細部を保つことで、色の細部よりも輝度の強度の
細部をよりよく知覚することができる。

【０００５】フレーム相違圧縮方法は、時間的に異なる
瞬間に記録された同じ情景からのディジタルビデオフレ
ーム同士の間に存在する時間的冗長を用いる。これは、
各フレームを符号化するのに必要とされるデータを減少
する。ディジタルビデオフレームのシーケンスからの２
つの連続するフレームが領域毎に比較される。比較プロ
セスは、２つの対応する領域が同じか又は異なるかを決
定する。各領域のサイズ及び位置、比較の正確な性質、
並びに、与えられるしきい値によって同じか、異なるか
の定義は本発明の範囲外である。

【０００６】勿論、１つのフレームはもう１つのフレー
ムの後の時間における点を表す。比較される２つの領域
が同じで、フレームＮ−１のピクセルが既に知られてい
るならばならば、フレームＮからの領域のピクセルは符
号化され、それらのピクセルは記録される必要はない。
２つの領域が異なるときは、後のフレームのピクセルは
符号化及び記憶されなければならない。２つのフレーム
の各領域が比較、符号化及び記憶されると、プロセスは
フレームの次の対へと移動する。再生の間、圧縮解除プ
ロセスは、符号化プロセスと論理的に逆であるプロセス
を用いてディスプレイメモリの現在の状態に各時期で記
憶された情報を追加する。これは、条件補充と称され
る。

【０００７】ティジタル動画ビデオにおいて殆ど時間的
冗長がないときは、この方法は失敗する。しかしなが
ら、１秒あたり30フレームで撮影された花の成長の動画
ビデオシーケンスは大幅な冗長を含み、条件補充を用い
て上手に圧縮する。同様に、動画圧縮アルゴリムが用い
られないならば、移動カメラによって記録されるシーケ
ンスは殆ど冗長を含まず、上手に圧縮しない。

【０００８】だが、イメージを再生するために再生プラ
ットフォームがイメージ部分のライブラリにアクセス可
能ならば、特に伝送において、より大きな圧縮が可能で
ある。当該システムでは、圧縮されたデータは再生プラ
ットフォームで呼び出すコードを備えて、例えば、森の
背景を生成する。圧縮されたビデオストリームのコード
の位置によって、背景にピクセルの位置の選択されたセ
ットを決定する。森の背景、れんが壁、又は砂等のイメ
ージの領域は、タイプによって分類され、標準化された
パターンのブロックに色のタイプ及び輝度のタイプの組
合せとして記憶される。しかしながら、そのようなパタ
ーンをすばやく認識するための方法が欠けていたため
に、圧縮されたビデオストリームを生成する際にライブ
ラリパターンにコードの用途を詰め込んできた。パター
ンを認識するためには、迅速な、非メモリ集中プロセス
が望ましい。

【０００９】エラーが容認されないとき、イメージから
の２進パターンをパターンのテーブルにおける２進パタ
ーンと比較するのは容易である。プロセスは、整合が発
見された、或いは、テーブルが使い尽くされたところま
でパターンの比較を行いながらテーブルを介してループ
する。整合が検出されると、基本単位がテーブルへのオ
フセットによって表示される。しかしながら、エラー許
容度とのパターン整合を実施するのはより一層困難であ
る。１つの実施方法は、基本単位からの２進パターンを
排他的ＯＲ（オア）演算で各テーブル項目（エントリ
ー）と比較することである。排他的ＯＲ演算の出力にお
ける１ビットの数により、パターン同士の間で不整合の
ピクセルの数が決定される。この出力が走査されて、１
ビットからのピクセルの不整合の数を決定する。しかし
ながら、現在のマイクロプロセッサは、概して排他的Ｏ
Ｒ演算を行い、不整合の数をカウントする命令を備えて
いない。従って、プロセスは排他的ＯＲ演算からの結果
となる比較からビットをシフトするのに、一度に１個ず
つ書き込まれなければならない。カウントは、シフトさ
れたビットが１の値のときに増分されなければならな
い。そのような命令のシーケンス（即ち、シフト、テス
ト及び条件的な増分）では、テストされたビットにエラ
ーが多過ぎるか、或いは、ワード全体がテストされるま
でループされなければならない。現在の機械において、
そのようなビデオ圧縮プロセスは受入不可能な程に大き
な処理ロードを示している。

【００１０】また、計算負担は、基本単位からのパター
ンがルックアップテーブルへのオフセットとして使用さ
れる直接ルックアップテーブルを用いることによって減
らすことができる。４ｘ４の矩形領域において、64キロ
バイトのルックアップテーブルが必要とされる。ディジ
タル信号プロセッサに基づく特殊なビデオハードウェア
の中には、そのような比較的大きなルックアップテーブ
ルを支援するような十分なランダムアクセスメモリがな
い。

【００１１】

【発明が解決しようとする課題】本発明の目的は、ビデ
オセグメントの圧縮で使用するための生ビデオフレーム
のパターンを迅速に認識するためのシステム及び方法を
提供することである。

【００１２】本発明のもう１つの目的は、テーブルのパ
ターンに整合又は近似するパターンを表示するビデオデ
ータのフレームの領域でテーブルのパターンにコードを
生成することによって、ディジタル化されたカラービデ
オデータを圧縮するためのシステム及び方法を提供する
ことである。

【００１３】

【課題を解決するための手段と作用】ビデオデータスト
リームにおけるイメージフレームは、ディジタル化され
た色及び輝度のデータが割り当てられた複数のピクセル
を有する。イメージフレームは複数の重なり合わない基
本単位に分割され、各基本単位は複数のピクセルから成
る。以前のフレームからの変化を時間内に示す基本単位
において、異なるディジタル化された色及び輝度のデー
タを備えたピクセルを有する基本単位がパターン整合の
ために選択される。パターン整合のために選択された基
本単位の各ピクセルは、パターン値にマッピングされ
る。パターン値は、基本単位で同じ色及び輝度のデータ
を共用する全てのピクセルで同一である。次に、パター
ン値は基本単位の相対的位置に基づいてグループ化さ
れ、パターン整合テーブル及びエラー条件テーブルの対
応するセットへオフセットを形成する。パターン整合テ
ーブル及びエラー条件テーブルは、全て単一のパターン
のテーブルに関連する。次に、パターン整合テーブル及
びエラー条件テーブルの各対応するセットへのオフセッ
トからの項目は、パターン整合の印を生成するために蓄
積される。次に、印が比較されて、予め選択されたエラ
ー許容度内の基本単位と最も良く整合するパターンを選
択する。整合されたパターンのテーブルへのオフセット
が、所望のコードを提供するために生成される。

【００１４】ディジタル化された色及び輝度のデータが
割り当てられた複数のピクセルを有するイメージフレー
ムを圧縮するための方法は、イメージフレームを複数の
重なり合わない基本単位へ分割するステップを備え、各
基本単位が複数のピクセルから成り、パターン整合のた
めに異なるディジタル化された色及び輝度のデータを備
えたピクセルを有する基本単位を検索するステップと、
検索された基本単位の各ピクセルをパターン値へとマッ
ピングするステップを備え、パターン値が基本単位で同
じ色及び輝度のデータを共用する全てのピクセルにおい
て同一であり、パターン整合テーブル及びエラー条件テ
ーブルの対応するセットのシーケンスを提供するステッ
プと、パターン値をパターン整合テーブル及びエラー条
件テーブルの各対応するセットへのオフセットへグルー
プ化するステップと、パターン整合の印を生成するた
め、オフセットからの項目をパターン整合テーブル及び
エラー条件テーブルの各対応するセットへ蓄積するステ
ップと、から成る。

【００１５】ディジタル化された色及び輝度のデータが
割り当てられた複数のピクセルを有するイメージフレー
ムを圧縮するためのデータ処理システムは、メモリと、
メモリにおいてパターン整合テーブル及びエラー条件テ
ーブルの対応するセットのシーケンスを生成するための
手段と、イメージフレームを複数の重なり合わない基本
単位へ分割するための手段を備え、各基本単位が複数の
ピクセルを含み、パターン整合のために異なるディジタ
ル化された色及び輝度のデータを備えたピクセルを有す
る基本単位を検索するための手段と、検索された基本単
位の各ピクセルをパターン値へとマッピングするための
手段を備え、各値が基本単位で同じ色と輝度のデータを
共用する全てのピクセルにおいて同一であり、パターン
値をパターン整合テーブル及びエラー条件テーブルの各
対応するセットへのオフセットへグループ化するための
手段と、パターン整合の印を生成するため、オフセット
からの項目をパターン整合テーブル及びエラー条件テー
ブルの各対応するセットへ蓄積するための手段と、から
成る。

【００１６】

【実施例】図面、特に図１を参照すると、本発明の方法
に従って使用されるパーソナルコンピュータシステム１
０の外観図が示されている。パーソナルコンピュータシ
ステム１０は、ＩＢＭパーソナルシステム２(Personal
System 2) 又は同様のシステムを使用することによって
提供されるのが好ましいコンピュータ１２を含む。パー
ソナルコンピュータシステム１０は、概してケーブル１
８によってコンピュータに接続されるビデオディスプレ
イ１４及びキーボード１６を含む。ビデオディスプレイ
装置１４及びキーボード１６は、コンピュータ１２への
ユーザ入力を可能にし、ビデオセグメント２０等の知覚
可能なメッセージをユーザに提供するために使用され
る。

【００１７】図２は、パーソナルコンピュータシステム
１０のブロック図である。コンピュータシステム１０
は、コンピュータシステム１０の構成要素同士の間でデ
ータが渡されるシステムバス２２に基づく。システムバ
ス２２へ接続される構成要素の中には、インテル80386
又はより強力なマイクロプロセッサを基本とする中央処
理装置（ＣＰＵ）２４である。ＣＰＵ２４はシステムメ
モリ２６に記憶されたプログラムを実行し、システムメ
モリ２６に記憶されたデータを操作する。圧縮されたビ
デオセグメントは記憶媒体２８に記憶されるか、或い
は、システムバス２２へ接続されたデバイスコントロー
ラ３０を介する伝送チャネルによって伝送される。ビデ
オ情報は、カメラ３４又は他のイメージ生成デバイスに
よって情景３２から捕獲される。アナログディジタル変
換器３６は、アナログビデオ情報を生の、圧縮されてい
ないフレームのシーケンスのため複数のディジタル値
（例えば、ＲＧＢ２４）へ変換する。システム１０は、
伝送の際にリアルタイム方式でビデオフレームを圧縮で
きることが好ましい。

【００１８】図３は、本発明の第１及び第２実施例によ
って符号化される圧縮されたビデオデータストリーム３
８のプロトコルを示す。圧縮の間、生ビデオシーケンス
の各フレームは、基本単位と称される複数の重なり合わ
ない連続する矩形の領域へフレームを分解することによ
って解析される。各基本単位は、Ｘ列ｘＹ行のピクセル
のマトリックスである。一般的に、基本単位はフレーム
からの４ｘ４のピクセルのマトリックスである。圧縮解
除プラットフォームは、各フレームをそのような基本単
位のマトリックスとして処理する。

【００１９】１つのプロトコルにおいて、各基本単位は
４つのタイプ、即ち、無変化、同質、パターン、及び所
定のパターン、の内の１つに対応する。各基本単位のタ
イプは、圧縮されたビデオストリームに指定される。所
定のパターンのタイプの基本単位は、圧縮解除プラット
フォームで使用可能なパターンのテーブルにおけるライ
ブラリパターンに関連する。

【００２０】ストリーム３８のプロトコルにおいて、基
本単位は、（１）複数の行に沿ってＸ方向にシーケンシ
ャルに、或いは、（２）２ｘ２のマトリックスの４つの
部分として、のいずれかによって生じる４部分に編成さ
れる。次に、最後の出力表示の位置がストリーム３８に
おける位置によって決定される。フレームヘッダー４０
に続いて、４部分の基本単位グループを定義する一般的
なバイトヘッダー４２がある。バイトヘッダー４２は４
部分の基本単位グループを定義する。バイトヘッダー４
２は、４つのダイアド（２項）４４、４６、４８及び５
０を含む。各ダイアドは、０から３の４つの値の内の１
つに設定される。各値は、プロトコルによって許可され
る４つの基本単位のタイプの内の１つに対応する。図示
されるように、ダイアド４４は０に設定され、ダイアド
４６は１に設定され、ダイアド４８は２に設定され、ダ
イアド５０は３に設定されて、それらの数の２進表現に
よって示される。シーケンスにおけるダイアドの位置
は、最後のディスプレイフィールドにおいて基本単位の
位置を制御する。無変化の基本単位は、ストリーム３８
においていかなるビデオデータも必要としないので、い
かなるビデオデータも供給されない。従って、ストリー
ム３８のいかなるデータのブロックもダイアド４４に対
応しない。ストリーム３８がフレーム間で使用される場
合、いかなるダイアドも値０を持たない。フレーム間
は、例えば、シーンの変化に対応する空間的圧縮であ
る。

【００２１】ダイアド４６は、同質の基本単位に対応す
ることを示す値１を有する。同質の基本単位は、単一の
色の値によって特徴付けられる基本単位である。同質の
基本単位のスケーリング能力は、出力表示フレームにお
いてスケーリングされたサイズの基本単位に指定された
色を表示することによって得られる。ダイアド４６で色
が指定されなければならないため、ストリーム３８から
のカラーブロック５２はダイアド４６の色を含む。色
は、ＲＧＢ８、ＲＧＢ１６、ＲＧＢ２４フォーマット又
はＹＵＶ１６又はＹＵＶ２４フォーマットとして符号化
されてもよい。ダイアド４８は４部分の第３基本単位に
対応し、所定のパターンの基本単位の発生に対応する値
２に設定されている。ダイアドにおいて値２が発生する
と直ちに、再生プラットフォームはストリーム３８から
次のブロックを取り出し、この次のブロックが所定のパ
ターンのテーブル５６へのインデックスブロック５４に
なる。パターンのテーブルは、複数のビットマップから
成る。ビット位置における各ビットマップは、出力ビデ
オフレームの大きさに１対１で対応する。ビットマップ
は、パターンで定義された第１色と第２色に対応する１
と０のパターンを有する。再生プラットフォームは、カ
ラーブロック５８及びカラーブロック６０からのそれら
の色を取り出し、それぞれをテーブル５６から取り出さ
れたパターンで１と０の値のビットに適用する。

【００２２】第４ダイオード５０は、基本単位が圧縮さ
れたストリーム３８にパターンブロックを有することを
示す値３に設定される。再生プラットフォームはストリ
ームからパターンブロック６２、並びに、スケーリング
された出力基本単位の出力値として２つのカラーブロッ
ク６４及び６６を取り出す。パターンブロック６２の２
進パターンは、基本単位のラスター走査で順序付けられ
る。

【００２３】パターンのテーブル５６の数が制限される
場合、テーブルに確かなことはエスケープコードとして
指定されてもよい。バイトヘッダー６８に続いて、イン
デックスブロックの位置にエスケープコード７０の発生
が示されている。そのようなエスケープコードは、無変
化又は同質の基本単位のランレングスを含む多くのこと
を表すことが可能である。エスケープコードブロックに
続いて、補足のランレングスブロック７２が提供されて
もよい。

【００２４】図４は、本発明の第１及び第２実施例に従
ってパターン整合を実行するために使用されるデータ構
造体を示す。４ｘ４矩形領域７４は、ビデオフレームの
符号化された基本単位における２進ビットパターンを示
す。矩形領域７４は２つのカラー値及び２進パターンを
用いて符号化され、ここで０ビットは２つのカラー値の
内の１つと対応し、１ビットは他の、即ち、残りのカラ
ー値と対応する。２進パターンのビットは、基本単位の
ラスター走査で順序付けられる。

【００２５】所定のパターンの指定は、矩形領域７４に
よって表される基本単位を表すのに必要とされるビット
率を減少するのに使用される。パターンのテーブルは、
予め指定された２進パターンのセットを含む。イメージ
を再生すると直ちに、ビデオストリームから取り出され
た第１色及び第２色はイメージを再生するためにパター
ンのテーブルからパターンに適用されてもよい。２つの
色は、第１色がパターンの０ビットに対応し、第２色が
パターンの１ビットに対応する基本単位に関連して伝送
される。フル（全）パターンを表示するのに必要な１６
ビットによるよりもむしろコードによる所定のパターン
の表示によって、基本単位あたり１バイトのデータを保
管することになる。本発明において、所定のパターンコ
ードは、パターンのテーブルにおいて２進パターンが正
確に整合しないときでさえも、基本単位を表すために用
いられる。パターンのテーブルにおけるパターンの数
は、符号化プロセスの複雑さを減らすために小さく保た
れる。複雑さはパターン整合に対応する問題に関連する
一方、あるエラーの許容度も可能にする。所定のパター
ンを符号化するときに、１６ビット２進パターンの基本
単位をパターンのテーブルにおける各パターンと比較し
て、許容されたエラー内で整合があるかどうかを決定す
る。それぞれの比較はより多くの時間を必要とし、使用
可能なプロセッサ資源により大きな要求を行う。だが、
パターンが慎重に選ばれ、あるエラーも許容されるなら
ば、大きな割合の矩形の基本単位領域はパターンを予め
決定するコードとして符号化されてもよい。本発明にお
いて、矩形の領域の１６ピクセルの内の２個までがエラ
ーとして許容される。

【００２６】本出願はルックアップテーブル技術とマイ
クロプロセッサの動作の組合せを提供すると共に、ピク
セルの不整合を許容する。パターンのテーブルにおいて
所定のパターンの数は、プロセッサデータワードのサイ
ズ（例えば、インテル8086及び80286 方式の機械には16
ビット、インテル80386 及び80486 方式の機械には32ビ
ット) に基づく。４つの潜在的な整合テーブル７６Ａ乃
至７６Ｄ及び４つのエラーテーブル７８Ａ乃至７８Ｄ
が、圧縮プロセスのためにメモリに提供される。４ｘ４
基本単位は、ラスター走査の行に対応して４つのニブル
に分解される。４つの整合テーブル７６Ａ乃至７６Ｄ及
びエラーテーブル７８Ａ乃至７８Ｄの各々は、基本単位
の対応するニブルによってアドレス指定される。換言す
れば、整合テーブル７６Ａ及びエラーテーブル７８Ａは
第１ニブルを用いてアクセスされる等となる。ニブル
は、各々が１６項目から成る整合テーブルへとオフセッ
トされる。幅に関しては、テーブルは使用されるマイク
ロプロセッサのデータワードサイズに対応する。

【００２７】各ニブルにおいて、全ての１６個の所定の
パターンが同時に検査される。テーブルでは、各ビット
位置はパターンのテーブルにおけるパターンに対応す
る。基本単位７４からの４ビットニブルが、１ピクセル
のエラー内において、パターンのテーブルにおけるパタ
ーンの対応する部分と整合する場合、整合テーブルに１
が現れる。整合しなければ、ビット位置に０が現れる。
エラーテーブルも同様にアドレス指定される。ニブルに
エラーがない、或いは、２つのピクセルエラーが発生し
たならば、エラーテーブル項目はテーブルパターンの対
応する位置が０になる。１つのピクセルエラー、或い
は、２つより多いピクセルエラーが発生したならば、エ
ラーテーブルの位置が１になる。これらの結果は、図５
に示される真理値表に要約されている。

【００２８】基本単位７４の行の全てを整合テーブル７
６Ａ乃至７６Ｄ及びエラーテーブル７８Ａ乃至７８Ｄの
パターンと比較すると、基本単位７４の情報は、整合が
なかったならばパターン及び２つのカラー値から成る６
バイトのブロック８０として符号化され、整合したなら
ばインデックスコード及び２つのカラー値から成る５バ
イトブロック８２として符号化される。

【００２９】図６は、ビデオフレームをコードを含む圧
縮されたビデオデータとしてフレームの選択された部分
のパターンのテーブルへと符号化するための準備を行う
プロセスを示している。プロセスはステップ１００で入
力され、ここで生フレームが複数の矩形の、重なり合わ
ない基本単位に分割される。次に、ステップ１０２が実
行され、フレームからの次の（又は第１の）基本単位が
パターンであるかどうかを決定する。基本単位は、２つ
のカラー値を用いて符号化されるならばパターンとして
分類される。この時点で基本単位は、以前のフレームに
おける対応する基本単位からの変化を同時に表すと仮定
される。ステップ１０２からのＮＯ分岐が、同質の基本
単位又は無変化の基本単位等のパターンでない基本単位
に対して続けられる。ステップ１０４は、選択されたプ
ロトコルに従って圧縮されたデータストリームにおける
当該基本単位の符号化を表す。この動作の仕組みは本発
明の範囲外である。ステップ１０６において、フレーム
の最後の基本単位が処理されたかどうかが決定される。
処理されていなければ、プロセスはステップ１０２に戻
り、次の基本単位を検索及び検査する。処理されていれ
ば、プロセスは終了して出る。

【００３０】パターンである基本単位が識別されると、
ステップ１０２からのＹＥＳ分岐が続けられる。ステッ
プ１０８が、基本単位でビットマップを生成するために
実行される。基本単位が２色に分類されるため、０が一
方の色を有するピクセルに適用され、１が他方の色を有
するピクセルに適用される。当業者によって、一方又は
他方の色から成るピクセルへの値の割り当ては任意であ
ることが認識されている。パターン認識の可能性を十分
に利用するため、ステップ１０８によって生成されるパ
ターンの否定が、パターン整合を完了するために計算さ
れなければならない。２進ビットマップの否定を整合す
るには、結果となる圧縮されたデータストリームにおけ
る色の順序を逆にする必要がある。次に、ステップ１１
０において、ビットマップはデータワードを生成するた
めにラスタ走査される。次に、ステップ１１２におい
て、以下に記載されるパターン整合サブプロセスが呼び
出される。パターン整合サブプロセスは、整合が発生し
たか否かの表示を戻す。整合か否かはステップ１１４で
決定され、整合が発生しなければ、ＮＯ分岐がステップ
１１６へと続けられる。ステップ１１６において、使用
されるプロトコルに従って、データワード全体が圧縮さ
れたビデオデータストリームに配置される。ステップ１
１４が整合を検出したならば、ＹＥＳ分岐がステップ１
１８へと続けられ、パターンのテーブルへのインデック
スが使用されるプロトコルに従って圧縮されたビデオデ
ータストリームに配置される。ステップ１１６又はステ
ップ１１８に続いて、ステップ１２０が実行されて、パ
ターンの色を圧縮されたビデオデータストリームへと配
置する。次に、ステップ１０６が実行されて、フレーム
の最後の基本単位が処理されたかどうかが決定される。

【００３１】図７は、基本単位内のパターン整合のプロ
セスの第１実施例を示す。プロセスはステップ１２２で
入力されて、基本単位のビットマップの第１ニブル、即
ち、４ビットセグメントの検索と、取り出される値への
可変オフセットの設定が行われる。ステップ１２４にお
いて、第１整合テーブルからの対応する項目を検索する
のにオフセットが用いられる。次に、ステップ１２６に
おいて、蓄積された整合が整合テーブルから検索された
ばかりの項目に等しく設定される。次に、ステップ１２
８において、第１エラーテーブルからの対応する項目を
検出するのにオフセットが用いられる。ステップ１３０
において、第１の蓄積されたエラーマーカーがエラーテ
ーブルから検索された項目に等しく設定される。

【００３２】第２の蓄積されたエラーマーカーが、ステ
ップ１２６及び１３０の結果を用いて計算されなければ
ならない。ステップ１３２において、蓄積された整合は
位置毎に第１の蓄積されたエラーマーカーと比較され
る。双方のビットが０であるそれらの位置は、基本単位
のパターンが２つのエラー内で整合するパターンのテー
ブルにおけるパターンに対応する。ステップ１３４にお
いて、蓄積された整合ワードはステップ１３２で見つけ
られた位置を含むようにリセットされる。

【００３３】基本単位の第２乃至第４ニブルが、ループ
制御プロセスによって処理される。後で用いられるよう
に、第１ループはステップ１２２乃至１３４と考えられ
る。ループ制御は決定ステップ１３６で実行される。ス
テップ１３６において、もう１つのニブルが処理のため
に残っているかどうかが決定される。残っていなけれ
ば、基本単位の４つのニブル全てをパターンのテーブル
と比較し、少なくとも１つの整合が見つけられる。ＮＯ
分岐がステップ１３８へと続けられ、最適化プロセスが
呼び出されて最良の整合を決定する。ニブルが処理する
ために残っているならば、ＹＥＳ分岐はステップ１３６
からステップ１４０へと続けられる。

【００３４】ステップ１４０において、次のニブルが基
本単位から検索され、可変オフセットがニブルの値に設
定される。ステップ１４２において、オフセットは次の
整合テーブルからの項目を検索するために使用される。
例えば、第２ニブルが処理されているならば第２整合テ
ーブルが使用され、第４ニブルが処理されているならば
第４整合テーブルが使用される。次に、ステップ１４４
において、現在の期間整合（ＭＸ）はステップ１４２か
ら検索された項目に等しく設定される。ステップ１４６
において、次のエラーテーブルからのオフセットでの項
目が検索される。ステップ１４８において、可変現在期
間エラー（ＥＸ）はステップ１４６から検索された項目
に等しく設定される。

【００３５】２つのエラーが表示されるパターンでの決
定が行われる。ステップ１５０において、ステップ１４
４及び１４８の結果は対応するゼロを有する決定された
位置と比較される。これらの位置が以前のループからの
エラーを持たなければ、蓄積された整合マーカーはステ
ップ１５２においてそれらの位置でリセットされない。
ステップ１５２において、蓄積された整合マーカーは、
現在のループで２つより多いエラーを蓄積する位置と、
現在のループにおいて２つより多いエラーを有する位置
とを差し引いた以前のループからの蓄積された整合に等
しくリセットされる。次に、ステップ１５４において、
第２の蓄積されたエラーマーカーは以前のループからの
第２の蓄積されたエラーマーカーと、現在のループで２
つのエラーを蓄積する位置との合計にリセットされる。
ステップ１５６において、第１の蓄積されたエラーマー
カーは現在の期間エラー値と排他的ＯＲ演算された以前
のループからの第１の蓄積されたエラーマーカーにリセ
ットされる。なお、いったん蓄積された整合変数におけ
る対応する位置が０になると、第１の蓄積されたエラー
マーカー及び第２の蓄積されたエラーマーカーにおける
ビット位置の値はいかなる値をとってもよい。パターン
のテーブルの対応するパターンが整合不可能な場合、ス
テップ１５４及び１５６の変数を補正する必要はない。

【００３６】次に、ステップ１５８が実行されて、蓄積
された整合マーカーが０かどうかを決定する。０であれ
ば、いかなるパターン整合も起こらず、プロセスは出
る。蓄積された整合がゼロでなければ、プロセスはステ
ップ１３６に戻り、基本単位においてもう１つのニブル
が処理のために残っているかどうかを決定する。ステッ
プ１５８は、次のステップ１３４に続いて実行されても
よい。

【００３７】表１は、論理的動作をステップとするパタ
ーン整合プロセスを示している。表においてΣはフロー
チャートのＳに対応する。従って、ＭΣは蓄積された整
合に等しく、Ｅ１Σは第１の蓄積されたエラーマーカー
に等しく、Ｅ２Σは第２の蓄積されたエラーマーカーに
等しい。更に、一時的な変数ＭＸ、ＥＸ及びＭ２が使用
される。

【００３８】

【表１】

【００３９】２つのピクセルが２進パターンの同一ニブ
ル内のエラーにあることをプロシージャ（手順）が許容
しないならば、プロセスはピクセルエラーに対する許容
度をやや少なくして更に簡素化される。全体で２つのピ
クセルエラーは、基本単位の異なるニブルで発生した場
合は依然として許容される。そうした省略されたプロセ
スは図８の真理値表を用いる。この表でＸは無関心値を
表している。パターン整合プロセスは図９に示され、ス
テップ１６０で入力されて、データワードの第１ニブル
が検索されて、オフセットが第１ニブルに等しく設定さ
れる。ステップ１６２において、オフセットにおける第
１整合テーブルからの項目が検索される。ステップ１６
４において、蓄積された整合変数が整合テーブルからの
検索された項目に等しく設定される。ステップ１６６に
おいて、オフセットが用いられて、第１エラーテーブル
からの項目を検索する。ステップ１６８において、第１
の蓄積されたエラーマーカーがエラーテーブルからの検
索された項目に等しく設定される。ステップ１７０にお
いて、第２の蓄積されたエラーマーカーが０の値で初期
設定される。

【００４０】この時点で、基本単位からの残りの３つの
ニブルのループ制御が開始する。ステップ１７２は、基
本単位からのもう１つのニブルが処理のために残ってい
るかどうかを決定する。残っていなければ、ステップ１
７４が実行されて、可能な整合セットで最適化プロセス
を呼び出す。

【００４１】もう１つのニブルが処理のために残ってい
るならば、ＹＥＳ分岐がステップ１７２からステップ１
７６へと続けられる。ステップ１７６において、次のニ
ブルが基本単位から検索されて、オフセットがニブルに
等しく設定される。次に、ステップ１７８が実行され
て、オフセットにおいて現在のループに対応する整合テ
ーブルからの項目を検索する。次に、ステップ１８０に
おいて、現在の期間整合の変数が整合テーブルからの検
索された項目に等しく設定される。ステップ１８２にお
いて、オフセットが用いられて、現在のループに対応す
るエラーテーブルから項目を検索する。ステップ１８４
において、現在の期間エラー変数がエラーテーブルから
の検索された項目に等しく設定される。

【００４２】ステップ１８６において、蓄積されたエラ
ー変数は、現在のループで２つより多いエラーを蓄積す
る位置と、現在のループにおいて２つより多いエラーを
有する位置とを差し引いた以前のループからの蓄積され
た整合に等しくリセットされる。ステップ１８８におい
て、第２の蓄積されたエラー変数は以前のループからの
第２の蓄積されたエラー変数と、以前のループ及び現在
のループで２つのエラーを蓄積する位置との合計に等し
くリセットされる。次に、ステップ１９０が実行され
て、以前のループからの第１の蓄積されたエラー変数と
オフセットを用いるエラーテーブルから検索された現在
の期間エラー変数を追加することによって、第１の蓄積
されたエラー変数をリセットする。ステップ１９２にお
いて、蓄積された整合変数が０かどうかが決定される。
また図７に示されたステップ１５８及びステップ１３４
と同様に、ステップ１９２もまたステップ１７０に続い
てもよい。ステップ１９２からのＮＯ分岐は、ステップ
１７２の処理へと戻る。エラー許容度内で整合が見つか
らなければ、ステップ１９２からＹＥＳ分岐が取られ
る。

【００４３】図９のプロセスによって実行される論理的
動作は、表２に挙げられる論理的関係式によって示され
る。

【００４４】

【表２】

【００４５】パターン整合プロセスによる通常の結果、
蓄積された整合変数（ＭΣ）は潜在的なパターン整合を
含み、Ｅ１Σ及びＥ２Σは依然として考慮されているパ
ターンのテーブルからのパターンに対応する位置におい
てそれぞれエラーが１のピクセル及びエラーが２のピク
セルを示している。この時点で、最良の候補パターンが
選択されなければならない。整合として適したパターン
は１より多くてもよい。パターンのテーブルへのオフセ
ットは、最も少ないエラーを有する整合のビット位置に
対応するように設定される。スクリーニングが行われ
て、正確に整合するパターン、或いは、エラーが１ピク
セルだけのパターンよりも２つのピクセルがエラーであ
るパターンが選択されるのを回避する。最初に行われる
検査で、あらゆるパターンが正確に整合したかどうかが
決定される。これは、論理的演算を実行することによっ
て達成される。

【００４６】

【数１】

【００４７】この演算の結果がゼロでないならば、その
結果はビット走査関数への入力として用いられる。１つ
のパターンだけが正確な整合となりうる。結果が０なら
ば、パターンのテーブルにおいて正確な整合がなかっ
た。次にプロシージャは、１つのピクセルエラーをもつ
あらゆるパターンを、２つのピクセルエラーをもつパタ
ーンに対するとして区別するためテストされなければな
らない。論理演算は以下の通りである。

【００４８】

【数２】

【００４９】この演算の結果がゼロでないならば、その
結果はビット走査関数への入力として用いられる。走査
関数の出力は、単一のピクセルがエラーである２進パタ
ーンを表すパターンのテーブルの項目からのパターンイ
ンデックスである。結果が０ならば、先述のプロセスに
は２つのピクセルがエラーであるパターンが見つけられ
る。未修正のＭΣは、パターンへのインデックスを決定
するために走査されてもよい。

【００５０】図１０は、数式（１）及び（２）の論理ス
テップを実行するための論理プロセスを示す。最適化が
ステップ２００を実行する際に入力されて、第１の蓄積
されたエラー変数及び第２の蓄積されたエラー変数の位
置が比較されて、変数のいかなる対応する位置において
も双方が０の項目を有するかどうかが決定される。項目
を有するならば、結果となるワードは対応する位置で１
に設定される。次に、ステップ２０２が実行されて、ス
テップ２００の結果及び蓄積された整合変数に論理ＡＮ
Ｄ演算を実行する。ステップ２０２のこの演算の結果が
ゼロでないならば、ステップ２０４で検出される。結果
がゼロでないことによって、正確な整合が得られたこと
が暗示される。ＹＥＳ分岐がステップ２０４からステッ
プ２０６へと続けられて、ステップ２０２の演算の結果
が非ゼロビットの位置で走査される。いったん見つけら
れると、その位置はテーブルのパターンへのオフセット
を生成するために用いられ、このオフセットは図６の符
号化制御プロセスに戻される。

【００５１】ステップ２０２からのゼロの結果によっ
て、ステップ２０４からのＮＯ分岐はステップ２０８へ
進められる。ステップ２０８において、第２の蓄積され
たエラー変数が否定され、否定された結果が蓄積された
整合変数と共にＡＮＤ演算への入力として使用される。
ステップ２１０において、ステップ２０８の演算の結果
が０と比較される。その結果がゼロでなければ、ＹＥＳ
分岐がステップ２１２へと続けられる。ステップ２１２
において、ステップ２０８の演算の結果が走査されて、
ゼロでないビットの位置を検出する。次に、このビット
位置はパターンのテーブルへのオフセットへ相関され、
符号化のために図６のプロセスへと戻される。ステップ
２１０において０の結果が発見されたならば、ステップ
２１０からのＮＯ分岐はステップ２１４へと続けられ
る。ステップ２１４において、未修正の蓄積された整合
変数はゼロでない結果を有する位置へと走査される。こ
の位置はステップ２１２及びステップ２０６に示される
ように、パターンのテーブルへオフセットを与える。

【００５２】実際、限定された数のパターンによって、
パターンは最小のハミング距離で選択される。これによ
って、最良の適合のための検査が不要になる。１つのパ
ターンだけが正確な整合である、或いは、１つのパター
ンだけがエラー許容度１と整合される、或いは、１つの
パターンだけがエラー許容度２と整合される。これによ
って、基本単位の４つのニブル全てが終了した後、蓄積
された整合値の単純な走査に対するプロシージャが短縮
される。

【００５３】

【発明の効果】本発明は上記より構成され、ビデオセグ
メントの圧縮で使用するための生ビデオフレームのパタ
ーンを迅速に認識するためのシステム及び方法が提供さ
れる。

【図面の簡単な説明】

【図１】パーソナルコンピュータの外観図である。

【図２】ビデオセグメントを圧縮するためのデータ処理
システムのブロック図である。

【図３】圧縮されたビデオセグメントのためのプロトコ
ルの概略図である。

【図４】ディジタルコンピュータで実行されるパターン
認識プロセスに使用されるメモリ構造体のブロック図で
ある。

【図５】パターン認識プロセスによって使用される真理
値表である。

【図６】パターン認識プロセスでビデオフレームを準備
するためのプロセスの論理的フローチャートである。

【図７】ビデオ情報のフレームのローカル領域で可能な
パターン整合を検出するための、本発明の第１実施例に
従ったプロセスの論理的フローチャートである。

【図８】第２のパターン認識プロセスによって使用され
る真理値表である。

【図９】ビデオ情報のフレームのローカル領域で可能な
パターン整合を検出するための、本発明の第２実施例に
従ったプロセスの論理的フローチャートである。

【図１０】図７又は図９のプロセスによって検出された
複数のパターン整合の内の１つを選択するためのプロセ
スの論理的フローチャートである。

【符号の説明】

１０ コンピュータシステム １６ キーボード ２２ システムバス ２４ ＣＰＵ ２６ システムメモリ ２８ 記憶媒体 ３０ デバイスコントローラ ３２ 情景 ３４ カメラ ３６ アナログディジタル変換器

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ボーン スコット アイヴァーソン アメリカ合衆国98103、ワシントン州シ アトル、フレモント レイン 3626、ア パートメント ナンバー306 (72)発明者 ケネス モールス イギリス国エスオー２ ２エフゼット、 サウス ハンプトン、リヴァーサイド パーク、フォレスト ヒルズ ドライヴ 53 (72)発明者 マーク アンドリュー ピートラス アメリカ合衆国33437、フロリダ州ボイ ントンビーチ、アシュレイ レイク ド ライヴ 5056 ナンバー５−38 (72)発明者 アートゥロ オーレリアノ ロドリクエ ズ アメリカ合衆国94002、カリフォルニア 州ベルモント、ベレスフォード アヴェ ニュー 3424

Claims (4)

(57)【特許請求の範囲】
1. 【請求項１】ディジタル化された色および輝度のデータ
   を割り当てられた複数ピクセルを有するイメージ・フレ
   ームを圧縮するための方法であって、 上記イメージ・フレームを複数の重なり合わない基本単
   位（各基本単位は複数ピクセルを有する）へ分割するス
   テップと、 異なるディジタル化された色および輝度のデータを備え
   たピクセルを有する上記基本単位をパターン整合のため
   に、検索するステップと、 検索された上記基本単位の各ピクセルをパターン値にマ
   ッピングするステップであって、上記パターン値は、上
   記基本単位において同じ色および輝度のデータを共有す
   る全ピクセルにおいて同じであり、 一連の関連付けられたパターン整合テーブルおよびエラ
   ー条件テーブルのセットを提供するステップと、 上記関連付けられたパターン整合テーブルおよびエラー
   条件テーブルの各々のセットのオフセットへ上記パター
   ン値をグループ化するステップと、 パターン整合の印を生成するために、上記オフセットか
   らの項目を上記関連付けられたパターン整合テーブルお
   よびエラー条件テーブルの各々のセットに蓄積するステ
   ップと、 を含むことを特徴とするイメージ・フレームを圧縮する
   ための方法。
2. 【請求項２】予め選択されたエラー許容度内の上記基本
   単位と最もよく整合するパターンを捜し出すために、上
   記蓄積するステップの上記印を比較するステップと、 上記パターンを識別する圧縮されたビデオ・ストリーム
   に含まれるコードを生成するステップと、 をさらに含むことを特徴とする請求項１に記載のイメー
   ジ・フレームを圧縮するための方法。
3. 【請求項３】ディジタル化された色および輝度のデータ
   を割り当てられた複数ピクセルを有するイメージ・フレ
   ームを圧縮するためのデータ処理システムであって、 メモリと、 上記メモリに一連の関連付けられたパターン整合テーブ
   ルおよびエラー条件テーブルのセットを作成する手段
   と、 上記イメージ・フレームを複数の重なり合わない基本単
   位（各基本単位は複数ピクセルを有する）へ分割する手
   段と、 異なるディジタル化された色および輝度のデータを備え
   たピクセルを有する上記基本単位をパターン整合のため
   に、検索する手段と、 検索された上記基本単位の各ピクセルをパターン値にマ
   ッピングする手段であって、上記パターン値は、上記基
   本単位において同じ色および輝度のデータを共有する全
   ピクセルにおいて同じであり、 上記関連付けられたパターン整合テーブルおよびエラー
   条件テーブルの各々のセットのオフセットへ上記パター
   ン値をグループ化する手段と、 パターン整合の印を生成するために、上記オフセットか
   らの項目を上記関連付けられたパターン整合テーブルお
   よびエラー条件テーブルの各々のセットに蓄積する手段
   と、 を含むことを特徴とするイメージ・フレームを圧縮する
   ためのデータ処理システム。
4. 【請求項４】予め選択されたエラー許容度内の上記基本
   単位と最もよく整合するパターンを捜し出すために、上
   記蓄積する手段の上記印を比較する手段と、 上記パターンを識別する圧縮されたビデオ・ストリーム
   に含まれるコードを生成する手段と、 をさらに含むことを特徴とする請求項３に記載のイメー
   ジ・フレームを圧縮するためのデータ処理システム。