(57)【要約】本発明は、データの隣接した順次フレームの間のパターン認識を行うための方法および装置を示しており、このデータは種々のタイプの関連していないデータであることができ、あるいは時間シーケンスで関連付けられ、オーディオおよびイメージの両データを各データフレーム内に含むことができる。予測スレッドを使用してデフォルトパターン方向を決定し、その後水平、垂直、対角線および回転方向において異なったスレッドおよび並列処理技術を使用してターゲットフレームの対応したターゲットサーチエリアとの基準フレームからの種々のサーチブロックの間の比較を行った後、パターン認識が行われ、十分な数の整合を獲得していない方向スレッドは終了される。整合が見出された場合、それらはリンクされたリストまたは２進ツリーとして記憶され、その後、あるフレーム内の重複した整合がスーパーセットブロックとして表されるように処理される。
2006502598.tif 000002
【特許請求の範囲】
【請求項１】
各フレームが複数のビットから構成されている複数の順次フレームのビットサイズを圧縮する方法において、
複数の比較されたブロックを獲得するために基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較し、基準フレームは最初は複数の順次フレームの初期フレームに設定されており、ターゲットフレームは最初は複数の順次フレームの後続フレームに設定されており、
圧縮されたターゲットフレームの表現を獲得するために複数の比較されたブロックを使用し、
その後、ターゲットフレームであった後続フレームを基準フレームとして再度指定し、そのターゲットフレームを後続フレームに後続する別の後続フレームとして再度指定し、
比較および使用ステップを繰返すステップを含んでいる方法。
【請求項２】
比較および使用ステップが行われている期間中に、残っている複数の順次フレームのそれぞれが一度ターゲットフレームになるように、再度指定し、繰返すステップを繰返すステップをさらに含んでいる請求項１記載の方法。
【請求項３】
圧縮されたターゲットフレームの表現は、リンクされたリストを使用する請求項１記載の方法。
【請求項４】
比較するステップは、
第１のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを水平方向にトラバースし、
第２のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを垂直方向にトラバースするステップを含んでいる請求項１記載の方法。
【請求項５】
比較するステップは、第３のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを対角線方向にトラバースするステップを含んでいる請求項４記載の方法。
【請求項６】
比較するステップはさらに、第４のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと異なった回転ポジションで比較するためにターゲットフレームをトラバースするステップを含んでいる請求項５記載の方法。
【請求項７】
第１のグループ、第２のグループ、第３のグループおよび第４のグループをトラバースするステップは、並列動作で動作される請求項６記載の方法。
【請求項８】
第１のグループ、第２のグループ、第３のグループおよび第４のグループの１つをトラバースするステップを、第１のグループ、第２のグループ、第３のグループおよび第４のグループの別のものをトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項７記載の方法。
【請求項９】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、第３および第４のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項７記載の方法。
【請求項１０】
予め定められた数は１である請求項９記載の方法。
【請求項１１】
整合は、同じ整合である必要がある請求項９記載の方法。
【請求項１２】
整合は、損失を生じせることができる請求項９記載の方法。
【請求項１３】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、第３および第４のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項７記載の方法。
【請求項１４】
第１のグループ、第２のグループ、第３のグループをトラバースするステップは、並列動作で行われる請求項５記載の方法。
【請求項１５】
第１のグループ、第２のグループおよび第３のグループの１つをトラバースするステップを、第１のグループ、第２のグループおよび第３のグループの別のものをトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項１４記載の方法。
【請求項１６】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、および第３のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項１４記載の方法。
【請求項１７】
予め定められた数は１である請求項１６記載の方法。
【請求項１８】
整合は、同じ整合である必要がある請求項１６記載の方法。
【請求項１９】
整合は、損失を生じせることができる請求項１６記載の方法。
【請求項２０】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２および第３のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、この特定のサーチブロックを終了するステップをさらに含んでいる請求項１４記載の方法。
【請求項２１】
第１のグループおよび第２のグループをトラバースするステップは、並列動作で行われる請求項４記載の方法。
【請求項２２】
第１のグループおよび第２のグループの一方をトラバースするステップを、第１のグループおよび第２のグループの他方をトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項２１記載の方法。
【請求項２３】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１および第２のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項２１記載の方法。
【請求項２４】
予め定められた数は１である請求項２３記載の方法。
【請求項２５】
整合は、同じ整合である必要がある請求項２３記載の方法。
【請求項２６】
整合は、損失を生じせることができる請求項２３記載の方法。
【請求項２７】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１および第２のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、この特定のサーチブロックを終了するステップをさらに含んでいる請求項２１記載の方法。
【請求項２８】
トラバースするステップにおいて、ターゲットフレーム内の順次の異なったポジションが互いに重複するようにターゲットフレームがトラバースされる請求項４記載の方法。
【請求項２９】
順次の異なったポジションは、多くても予め定められた数のビットの行および予め定められた数のビットの列だけ異なっている請求項２８記載の方法。
【請求項３０】
予め定められた数のビットの行は１であり、予め定められた数のビットの列は１である請求項２９記載の方法。
【請求項３１】
ターゲットフレームを水平方向にトラバースするステップおよびターゲットフレームを垂直方向にトラバースするステップの少なくとも一方において、ターゲットフレーム全体がトラバースされる請求項４記載の方法。
【請求項３２】
ターゲットフレーム全体を水平方向にトラバースするステップにおいて、ターゲットフレーム内の異なった垂直ポジションにおいて水平方向におけるパスが繰返され、
ターゲットフレーム全体を垂直方向にトラバースするステップにおいて、ターゲットフレーム内の異なった水平ポジションにおいて垂直方向におけるパスが繰返される請求項３１記載の方法。
【請求項３３】
ターゲットフレーム内の隣接した異なった垂直ポジションおよび隣接した異なった水平ポジションは、多くて予め定められた数のビットの行および予め定められた数のビットの列だけ異なっている請求項３２記載の方法。
【請求項３４】
予め定められた数のビットの行は１であり、予め定められた数のビットの列は１である請求項３３記載の方法。
【請求項３５】
トラバースする各ステップは、異なったプロセッサスレッドを使用して行われる請求項３２記載の方法。
【請求項３６】
トラバースする各ステップは、複数の異なったプロセッサスレッドを使用して実施される請求項３５記載の方法。
【請求項３７】
基準フレームビデオデータをターゲットフレームビデオデータと比較するステップにおいて少なくとも１つのビデオプロセッサスレッドが使用され、少なくとも１つのオーディオプロセッサスレッドが基準フレームオーディオデータをターゲットフレームオーディオデータと比較するために使用される請求項１記載の方法。
【請求項３８】
基準フレームビデオデータをターゲットフレームビデオデータと比較し、基準フレームオーディオデータをターゲットフレームオーディオデータと比較するために、比較するステップにおいて少なくとも１つのプロセッサスレッドが使用される請求項１記載の方法。
【請求項３９】
使用するステップにおいて、損失を生じることなく元の状態と比較して圧縮されたターゲットフレームの表現が獲得される請求項１記載の方法。
【請求項４０】
比較するステップにおいて、サーチブロックはアンド演算を使用してターゲットフレームと比較される請求項１記載の方法。
【請求項４１】
使用するステップにおいて、損失を生じることなく元の状態と比較して圧縮されたターゲットフレームの表現が獲得される請求項１記載の方法。
【請求項４２】
比較するステップにおいて、サーチブロックはアンド演算を使用してターゲットフレームと比較される請求項４１記載の方法。
【請求項４３】
比較するステップにおいて、サーチブロックはオア演算を使用してターゲットフレームと比較される請求項４１記載の方法。
【請求項４４】
比較するステップにおいて、サーチブロックは排他的オア演算を使用してターゲットフレームと比較される請求項４１記載の方法。
【請求項４５】
比較するステップにおいて、サーチブロックは加算演算を使用してターゲットフレームと比較される請求項４１記載の方法。
【請求項４６】
比較するステップにおいて、サーチブロックは減算演算を使用してターゲットフレームと比較される請求項４１記載の方法。
【請求項４７】
比較するステップにおいて、サーチブロックは乗算演算を使用してターゲットフレームと比較される請求項４１記載の方法。
【請求項４８】
比較するステップにおいて、サーチブロックは除算演算を使用してターゲットフレームと比較される請求項４１記載の方法。
【請求項４９】
使用するステップは、表現に対して使用されるスーパーセットブロックを獲得するために複数の比較されたブロックの重複したものを組合せる請求項１記載の方法。
【請求項５０】
比較するステップは、サーチブロックとターゲットフレーム内に存在する対応したターゲットブロックとの間の同じ整合を表す比較されたブロックを追跡するステップを含んでいる請求項１記載の方法。
【請求項５１】
追跡するステップは、基準フレームとターゲットフレームとの間において達成可能な圧縮の量の動的表示を提供するために使用され、比較するステップは、圧縮ターゲット比率を選択するステップをさらに含んでいる請求項５０記載の方法。
【請求項５２】
比較するステップは、ターゲットフレームに関して圧縮ターゲット比率に達したことを動的表示が示したときに中止される請求項５０記載の方法。
【請求項５３】
比較するステップは、表現内で許容されることのできる損失の所望の量を選択するステップをさらに含んでいる請求項５２記載の方法。
【請求項５４】
比較されたブロックは、ターゲットブロック内のビットの割合が所望の損失量に少なくとも等しい場合に、サーチブロックと同じであるとみなされる請求項５３記載の方法。
【請求項５５】
比較するステップは、表現内で許容されることのできる損失の量を選択するステップをさらに含んでいる請求項１記載の方法。
【請求項５６】
比較するステップは、
サーチブロックとターゲットフレームとの間の整合の可能性の推定値を獲得するために予測プロセッサスレッドを起動し、
基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して複数の比較されたブロックを獲得するために使用される少なくとも１つの比較プロセッサスレッドにこの推定値を送付するステップを含んでいる請求項１記載の方法。
【請求項５７】
比較するステップにおいて、比較はビットレベルで行われる請求項１記載の方法。
【請求項５８】
比較するステップにおいて、比較はバイトレベルで行われる請求項１記載の方法。
【請求項５９】
ターゲットフレーム中に存在する冗長なパターンのリンクされたリストを基準フレームから獲得し、基準フレームおよびターゲットフレームがそれぞれ複数のビットから構成されている方法において、
基準フレームの複数のサーチブロック部分のそれぞれをターゲットフレーム内の複数の位置と比較して複数の整合を決定し、
各整合に対して、サーチブロック部分にリンクされた位置識別子によりその整合に対応したターゲットフレームのその部分を表すステップを含んでいる方法。
【請求項６０】
比較するステップは、
サーチブロックとターゲットフレームとの間の整合の可能性の推定値を獲得するために予測プロセッサスレッドを起動し、
基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して複数の比較されたブロックを獲得するために使用される少なくとも１つの比較プロセッサスレッドにこの推定値を送付するステップを含んでいる請求項５９記載の方法。
【請求項６１】
別のターゲットフレームを獲得し、
基準フレームの複数のサーチブロック部分のそれぞれを別のターゲットフレーム内の複数の位置と比較して複数の整合を決定し、
各整合に対して、サーチブロック部分にリンクされた位置識別子によりその整合に対応した別ののターゲットフレームのその部分を表すステップをさらに含んでいる請求項５９記載の方法。
【請求項６２】
基準フレームのサーチブロック部分と整合しないターゲットフレームの位置は、ターゲットフレームに関連した残っているデータとして保存される請求項６１記載の方法。
【請求項６３】
基準フレームのサーチブロック部分と整合しない別のターゲットフレームの位置は、別のターゲットフレームに関連した残っているデータとして保存される請求項６２記載の方法。
【請求項６４】
比較するステップにおいて、損失を生じることなく比較が行われる請求項５９記載の方法。
【請求項６５】
基準フレームのサーチブロック部分と整合しないターゲットフレームの位置は、ターゲットフレームに関連した残っているデータとして保存される請求項６４記載の方法。
【請求項６６】
比較するステップにおいて、損失の導入が許容されて比較が行われる請求項５９記載の方法。
【請求項６７】
許容された損失割合の範囲内の基準フレームのサーチブロック部分と整合しないターゲットフレームの位置は、ターゲットフレームに関連した残っているデータとして保存される請求項６６記載の方法。
【請求項６８】
ターゲットフレーム内の複数の位置はターゲットフレーム全体のトラバーサルを構成しており、基準フレーム内の複数のサーチブロック位置は基準フレーム全体のトラバーサルを構成している請求項５９記載の方法。
【請求項６９】
各フレームは、あるイメージを表す複数のビットを含んでいる請求項５９記載の方法。
【請求項７０】
各フレームは、オーディオを表す別の複数のビットを含んでいる請求項６９記載の方法。
【請求項７１】
比較するステップにおいて、比較はビットレベルで行われる請求項５９記載の方法。
【請求項７２】
比較するステップにおいて、比較はバイトレベルで行われる請求項５９記載の方法。
【請求項７３】
比較するステップは、
第１のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを水平方向にトラバースし、
第２のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを垂直方向にトラバースするステップを含んでいる請求項５９記載の方法。
【請求項７４】
比較するステップは、第３のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを対角線方向にトラバースするステップを含んでいる請求項７３記載の方法。
【請求項７５】
第１のグループ、第２のグループ、第３のグループをトラバースするステップは、並列動作で行われる請求項７４記載の方法。
【請求項７６】
第１のグループ、第２のグループおよび第３のグループの１つをトラバースするステップを、第１のグループ、第２のグループおよび第３のグループの別のものをトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項７５記載の方法。
【請求項７７】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、および第３のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項７５記載の方法。
【請求項７８】
予め定められた数は１である請求項７７記載の方法。
【請求項７９】
整合は、同じ整合である必要がある請求項７７記載の方法。
【請求項８０】
整合は、損失を生じせることができる請求項７７記載の方法。
【請求項８１】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２および第３のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、この特定のサーチブロックを終了するステップをさらに含んでいる請求項７５記載の方法。
【請求項８２】
第１のグループおよび第２のグループをトラバースするステップは、並列動作で行われる請求項７３記載の方法。
【請求項８３】
第１のグループおよび第２のグループの一方をトラバースするステップを、第１のグループおよび第２のグループの他方をトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項８２記載の方法。
【請求項８４】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１および第２のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項８２記載の方法。
【請求項８５】
予め定められた数は１である請求項８４記載の方法。
【請求項８６】
整合は、同じ整合である必要がある請求項８４記載の方法。
【請求項８７】
整合は、損失を生じせることができる請求項８４記載の方法。
【請求項８８】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１および第２のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、この特定のサーチブロックを終了するステップをさらに含んでいる請求項８２記載の方法。
【請求項８９】
トラバースするステップにおいて、ターゲットフレーム内の順次の異なったポジションが互いに重複するようにターゲットフレームがトラバースされる請求項７３記載の方法。
【請求項９０】
順次の異なったポジションは、多くて予め定められた数のビットの行および予め定められた数のビットの列だけ異なっている請求項８９記載の方法。
【請求項９１】
予め定められた数のビットの行は１であり、予め定められた数のビットの列は１である請求項９０記載の方法。
【請求項９２】
ターゲットフレームを水平方向にトラバースするステップおよびターゲットフレームを垂直方向にトラバースするステップの少なくとも一方において、ターゲットフレーム全体がトラバースされる請求項７３記載の方法。
【請求項９３】
ターゲットフレーム全体を水平方向にトラバースするステップにおいて、ターゲットフレーム内の異なった垂直ポジションにおいて水平方向におけるパスが繰返され、
ターゲットフレーム全体を垂直方向にトラバースするステップにおいて、ターゲットフレーム内の異なった水平ポジションにおいて垂直方向におけるパスが繰返される請求項９２記載の方法。
【請求項９４】
ターゲットフレーム内の隣接した異なった垂直ポジションおよび隣接した異なった水平ポジションは、多くて予め定められた数のビットの行および予め定められた数のビットの列だけ異なっている請求項９３記載の方法。
【請求項９５】
予め定められた数のビットの行は１であり、予め定められた数のビットの列は１である請求項９４記載の方法。
【請求項９６】
トラバースする各ステップは、異なったプロセッサスレッドを使用して実施される請求項９３記載の方法。
【請求項９７】
トラバースする各ステップは、複数の異なったプロセッサスレッドを使用して実施される請求項９６記載の方法。
【請求項９８】
基準フレームビデオデータをターゲットフレームビデオデータと比較するステップにおいて少なくとも１つのビデオプロセッサスレッドが使用され、少なくとも１つのオーディオプロセッサスレッドが基準フレームオーディオデータをターゲットフレームオーディオデータと比較するために使用される請求項５９記載の方法。
【請求項９９】
基準フレームビデオデータをターゲットフレームビデオデータと比較し、基準フレームオーディオデータをターゲットフレームオーディオデータと比較するために、比較するステップにおいて少なくとも１つのプロセッサスレッドが使用される請求項５９記載の方法。
【請求項１００】
各フレームが水平、垂直および対角線方向にトラバースされることのできるマトリックスアレイに配列された複数のビットから構成されている複数の順次のフレーム内のパターンをサーチする方法において、
複数の比較されたブロックを獲得するために基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較するステップを含んでおり、基準フレームは複数の順次フレームの最初のフレームに設定されており、ターゲットフレームははじめに、複数の順次フレームの後続フレームに設定されており、比較するステップは、
少なくとも第１のグループのサーチブロックをターゲットフレーム内の対応した水平方向のターゲットブロックと比較するためにターゲットフレームを水平方向にトラバースし、
少なくとも第２のグループのサーチブロックをターゲットフレーム内の対応した垂直方向のターゲットブロックと比較するためにターゲットフレームを垂直方向にトラバースするステップを含んでおり、第２のグループのサーチブロックは第１のグループのサーチブロックと異なっていても異なっていなくてもよい方法。
【請求項１０１】
水平方向および垂直方向にトラバースした結果としてターゲットフレームと基準フレームとの間に十分な数の比較が見出されたか否かを決定し、
十分な数の比較が存在することが決定されなかった場合、第１および第２のグループのサーチブロックのグループと異なっていても、あるいは異なっていなくてもよい第３のグループのサーチブロックのグループをターゲットフレーム内の対応した対角線ターゲットブロックと比較するためにターゲットフレームを対角線方向にトラバースするステップをさらに含んでいる請求項１００記載の方法。
【請求項１０２】
比較するステップは複数の順次フレームについて繰返され、
ターゲットフレームであった後続フレームを基準フレームとして再度指定し、後続フレームに後続する別の後続フレームをターゲットフレームとして再度指定し、
比較するステップを繰返すステップをさらに含んでいる請求項１００記載の方法。
【請求項１０３】
後続フレームに後続する別の後続フレームをターゲットフレームとして再度指定し、
比較するステップが行われている期間中に、残っている複数の順次フレームのそれぞれが一度ターゲットフレームになるように、再度指定し、繰返すステップを反復するステップをさらに含んでいる請求項１００記載の方法。
【請求項１０４】
基準フレームは同じままである請求項１０３記載の方法。
【請求項１０５】
比較するステップは、第３のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを対角線方向にトラバースするステップを含んでいる請求項１００記載の方法。
【請求項１０６】
比較するステップはさらに、第４のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと異なった回転ポジションで比較するためにターゲットフレームをトラバースするステップを含んでいる請求項１０５記載の方法。
【請求項１０７】
第１のグループ、第２のグループ、第３のグループおよび第４のグループをトラバースするステップは、並列動作で行われる請求項１０６記載の方法。
【請求項１０８】
第１のグループ、第２のグループ、第３のグループおよび第４のグループの１つをトラバースするステップを、第１のグループ、第２のグループ、第３のグループおよび第４のグループの別のものをトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項１０７記載の方法。
【請求項１０９】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、第３および第４のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項１０７記載の方法。
【請求項１１０】
予め定められた数は１である請求項１０９記載の方法。
【請求項１１１】
整合は、同じ整合である必要がある請求項１０９記載の方法。
【請求項１１２】
整合は、損失を生じせることができる請求項１０９記載の方法。
【請求項１１３】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、第３および第４のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項１０９記載の方法。
【請求項１１４】
第１のグループ、第２のグループ、第３のグループをトラバースするステップは、並列操作で動作される請求項１０５記載の方法。
【請求項１１５】
第１のグループ、第２のグループおよび第３のグループの１つをトラバースするステップを、第１のグループ、第２のグループおよび第３のグループの別のものをトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項１１４記載の方法。
【請求項１１６】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、および第３のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項１１４記載の方法。
【請求項１１７】
予め定められた数は１である請求項１１６記載の方法。
【請求項１１８】
整合は、同じ整合である必要がある請求項１１６記載の方法。
【請求項１１９】
整合は、損失を生じせることができる請求項１１６記載の方法。
【請求項１２０】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２および第３のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、この特定のサーチブロックを終了するステップをさらに含んでいる請求項１１４記載の方法。
【請求項１２１】
第１のグループおよび第２のグループをトラバースするステップは、並列操作で動作される請求項１００記載の方法。
【請求項１２２】
第１のグループおよび第２のグループの一方をトラバースするステップを、第１のグループおよび第２のグループの他方をトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項１２１記載の方法。
【請求項１２３】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１および第２のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項１２１記載の方法。
【請求項１２４】
予め定められた数は１である請求項１２３記載の方法。
【請求項１２５】
整合は、同じ整合である必要がある請求項１２３記載の方法。
【請求項１２６】
整合は、損失を生じせることができる請求項１２３記載の方法。
【請求項１２７】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１および第２のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、この特定のサーチブロックを終了するステップをさらに含んでいる請求項１２１記載の方法。
【請求項１２８】
トラバースするステップにおいて、ターゲットフレーム内の順次の異なったポジションが互いに重複するようにターゲットフレームがトラバースされる請求項１００記載の方法。
【請求項１２９】
順次の異なったポジションは、多くて予め定められた数のビットの行および予め定められた数のビットの列だけ異なっている請求項１２８記載の方法。
【請求項１３０】
予め定められた数のビットの行は１であり、予め定められた数のビットの列は１である請求項１２９記載の方法。
【請求項１３１】
ターゲットフレームを水平方向にトラバースするステップおよびターゲットフレームを垂直方向にトラバースするステップの少なくとも一方において、ターゲットフレーム全体がトラバースされる請求項１００記載の方法。
【請求項１３２】
ターゲットフレーム全体を水平方向にトラバースするステップにおいて、ターゲットフレーム内の異なった垂直ポジションにおいて水平方向におけるパスが繰返され、
ターゲットフレーム全体を垂直方向にトラバースするステップにおいて、ターゲットフレーム内の異なった水平ポジションにおいて垂直方向におけるパスが繰返される請求項１３１記載の方法。
【請求項１３３】
ターゲットフレーム内の隣接した異なった垂直ポジションおよび隣接した異なった水平ポジションは、多くて予め定められた数のビットの行および予め定められた数のビットの列だけ異なっている請求項１３２記載の方法。
【請求項１３４】
予め定められた数のビットの行は１であり、予め定められた数のビットの列は１である請求項１３３記載の方法。
【請求項１３５】
トラバースする各ステップは、異なったプロセッサスレッドを使用して実施される請求項１３２記載の方法。
【請求項１３６】
トラバースする各ステップは、複数の異なったプロセッサスレッドを使用して実施される請求項１３５記載の方法。
【請求項１３７】
基準フレームビデオデータをターゲットフレームビデオデータと比較するステップにおいて少なくとも１つのビデオプロセッサスレッドが使用され、少なくとも１つのオーディオプロセッサスレッドが基準フレームオーディオデータをターゲットフレームオーディオデータと比較するために使用される請求項１００記載の方法。
【請求項１３８】
基準フレームビデオデータをターゲットフレームビデオデータと比較し、基準フレームオーディオデータをターゲットフレームオーディオデータと比較するために、比較するステップにおいて少なくとも１つのプロセッサスレッドが使用される請求項１００記載の方法。
【請求項１３９】
損失を生じることなく圧縮されたターゲットフレームの表現を獲得するために複数の比較されたブロックを使用するステップをさらに含んでいる請求項１００記載の方法。
【請求項１４０】
比較するステップにおいて、サーチブロックはアンド演算を使用してターゲットフレームと比較される請求項１００記載の方法。
【請求項１４１】
使用するステップにおいて、損失を導入することにより元の状態と比較して圧縮されたターゲットフレームの表現が獲得される請求項１００記載の方法。
【請求項１４２】
比較するステップにおいて、サーチブロックはアンド演算を使用してターゲットフレームと比較される請求項１４１記載の方法。
【請求項１４３】
比較するステップにおいて、サーチブロックはオア演算を使用してターゲットフレームと比較される請求項１４１記載の方法。
【請求項１４４】
比較するステップにおいて、サーチブロックは排他的オア演算を使用してターゲットフレームと比較される請求項１４１記載の方法。
【請求項１４５】
比較するステップにおいて、サーチブロックは加算演算を使用してターゲットフレームと比較される請求項１４１記載の方法。
【請求項１４６】
比較するステップにおいて、サーチブロックは減算演算を使用してターゲットフレームと比較される請求項１４１記載の方法。
【請求項１４７】
比較するステップにおいて、サーチブロックは乗算演算を使用してターゲットフレームと比較される請求項１４１記載の方法。
【請求項１４８】
比較するステップにおいて、サーチブロックは除算演算を使用してターゲットフレームと比較される請求項１４１記載の方法。
【請求項１４９】
圧縮されたターゲットフレームの表現を獲得するために複数の比較されたブロックを使用するステップをさらに含んでおり、この使用するステップにおいて、表現に対して使用されるスーパーセットブロックを獲得するために複数の比較されたブロックの重複したものが組合せられる請求項１００記載の方法。
【請求項１５０】
比較するステップは、サーチブロックとターゲットフレーム内に存在する対応したターゲットブロックとの間の同じ整合を表す比較されたブロックを追跡するステップを含んでいる請求項１００記載の方法。
【請求項１５１】
追跡するステップは、基準フレームとターゲットフレームとの間において達成可能な圧縮の量の動的表示を提供するために使用され、比較するステップは、圧縮ターゲット比率を選択するステップをさらに含んでいる請求項１５０記載の方法。
【請求項１５２】
比較するステップは、ターゲットフレームに関して圧縮ターゲット比率に達したことを動的表示が示したとき、中止される請求項１５０記載の方法。
【請求項１５３】
比較するステップは、表現内で許容されることのできる損失の所望の量を選択するステップをさらに含んでいる請求項１５２記載の方法。
【請求項１５４】
比較されたブロックは、ターゲットブロック内のビットの割合が所望の損失量に少なくとも等しい場合、サーチブロックと同じであるとみなされる請求項１５３記載の方法。
【請求項１５５】
比較するステップは、表現内で許容されることのできる損失の量を選択するステップをさらに含んでいる請求項１００記載の方法。
【請求項１５６】
比較するステップは、
サーチブロックとターゲットフレームとの間の整合の可能性の推定値を獲得するために予測プロセッサスレッドを始動し、
基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して複数の比較されたブロックを獲得するために使用される少なくとも１つの比較プロセッサスレッドにこの推定値を送るステップを含んでいる請求項１００記載の方法。
【請求項１５７】
比較するステップにおいて、比較はビットレベルで行われる請求項１００記載の方法。
【請求項１５８】
比較するステップにおいて、比較はバイトレベルで行われる請求項１００記載の方法。
【請求項１５９】
各フレームがマトリックスアレイに配列された複数のビットから構成されている複数の順次フレーム内のパターンをサーチする方法において、
複数の比較されたブロックを獲得するために基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較ステップを含んでおり、基準フレームは複数の順次フレームの初期フレームに設定されており、ターゲットフレームは最初、複数の順次フレームの後続フレームに設定されており、この比較するステップは、
サーチブロックをターゲットフレーム内の対応したターゲットブロックと比較するためにターゲットフレームを複数の異なった方向にトラバースするステップを含んでおり、このトラバースするステップは、並列に処理される複数の異なったスレッドを起動するステップを含んでおり、異なった各スレッドは異なったサーチブロックおよび異なった方向の少なくとも一方に関して動作し、
そのトラバーサルの結果としてターゲットフレームと基準フレームとの間に十分な数の整合が見出されたか否かを決定するステップを含んでおり、
複数の異なったスレッドのあるものを終了するステップを含んでおり、この終了するステップは、特定のスレッドに関してトラバースした結果十分な数の整合が得られないことが決定された場合にその特定のスレッドに対して発生される方法。
【請求項１６０】
トラバースするステップは、
第１のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを水平方向にトラバースし、
第２のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを垂直方向にトラバースするステップを含んでいる請求項１５９記載の方法。
【請求項１６１】
トラバースするステップは、ターゲットフレームを対角線方向にトラバースして、第３のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと比較するステップを含んでいる請求項１６０記載の方法。
【請求項１６２】
トラバースするステップはさらに、第４のグループの複数の異なったサーチブロックのそれぞれをターゲットフレーム内の異なったポジションと異なった回転ポジションで比較するためにターゲットフレームをトラバースするステップを含んでいる請求項１６１記載の方法。
【請求項１６３】
第１のグループ、第２のグループ、第３のグループおよび第４のグループをトラバースするステップは、並列に動作される請求項１６２記載の方法。
【請求項１６４】
終了するステップは、第１のグループ、第２のグループ、第３のグループおよび第４のグループの１つをトラバースするステップを、第１のグループ、第２のグループ、第３のグループおよび第４のグループの別のものをトラバースするステップを終了する前に終了する請求項１６３記載の方法。
【請求項１６５】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、終了するステップは、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、第３および第４のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了する請求項１６３記載の方法。
【請求項１６６】
予め定められた数は１である請求項１６５記載の方法。
【請求項１６７】
整合は、同じ整合である必要がある請求項１６５記載の方法。
【請求項１６８】
整合は、損失を生じせることができる請求項１６５記載の方法。
【請求項１６９】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、終了するステップは、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、第３および第４のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、その特定のサーチブロックを終了する請求項１６５記載の方法。
【請求項１７０】
第１のグループ、第２のグループ、第３のグループをトラバースするステップは、並列に動作される請求項１６１記載の方法。
【請求項１７１】
終了するステップは、第１のグループ、第２のグループおよび第３のグループの１つをトラバースするステップを、第１のグループ、第２のグループおよび第３のグループの別のものをトラバースするステップを終了する前に終了する請求項１７０記載の方法。
【請求項１７２】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、終了するステップは、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、および第３のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了する請求項１７０記載の方法。
【請求項１７３】
予め定められた数は１である請求項１７２記載の方法。
【請求項１７４】
整合は、同じ整合である必要がある請求項１７２記載の方法。
【請求項１７５】
整合は、損失を生じせることができる請求項１７２記載の方法。
【請求項１７６】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、終了するステップは、ターゲットフレームの予め定められた部分が比較された後で、第１、第２および第３のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、この特定のサーチブロックを終了する請求項１７０記載の方法。
【請求項１７７】
第１のグループおよび第２のグループをトラバースするステップは、並列に動作される請求項１６０記載の方法。
【請求項１７８】
終了するステップは、第１のグループおよび第２のグループの一方をトラバースするステップを、第１のグループおよび第２のグループの他方をトラバースするステップを終了する前に終了する請求項１７７記載の方法。
【請求項１７９】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、終了するステップは、ターゲットフレームの予め定められた部分が比較された後で、第１および第２のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了する請求項１７７記載の方法。
【請求項１８０】
予め定められた数は１である請求項１７９記載の方法。
【請求項１８１】
整合は、同じ整合である必要がある請求項１７９記載の方法。
【請求項１８２】
整合は、損失を生じせることができる請求項１７９記載の方法。
【請求項１８３】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、終了するステップは、ターゲットフレームの予め定められた部分が比較された後で、第１および第２のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、この特定のサーチブロックを終了する請求項１７７記載の方法。
【請求項１８４】
トラバースするステップにおいて、ターゲットフレーム内の順次の異なったポジションが互いに重複するようにターゲットフレームがトラバースされる請求項１６０記載の方法。
【請求項１８５】
順次の異なったポジションは、多くて予め定められた数のビットの行および予め定められた数のビットの列だけ異なっている請求項１８４記載の方法。
【請求項１８６】
予め定められた数のビットの行は１であり、予め定められた数のビットの列は１である請求項１８５記載の方法。
【請求項１８７】
ターゲットフレームを水平方向にトラバースするステップおよびターゲットフレームを垂直方向にトラバースするステップの少なくとも一方において、ターゲットフレーム全体がトラバースされる請求項１６０記載の方法。
【請求項１８８】
ターゲットフレーム全体を水平方向にトラバースするステップにおいて、ターゲットフレーム内の異なった垂直ポジションにおいて水平方向におけるパスが繰返され、
ターゲットフレーム全体を垂直方向にトラバースするステップにおいて、ターゲットフレーム内の異なった水平ポジションにおいて垂直方向におけるパスが繰返される請求項１８７記載の方法。
【請求項１８９】
ターゲットフレーム内の隣接した異なった垂直ポジションおよび隣接した異なった水平ポジションは、多くて予め定められた数のビットの行および予め定められた数のビットの列だけ異なっている請求項１８８記載の方法。
【請求項１９０】
予め定められた数のビットの行は１であり、予め定められた数のビットの列は１である請求項１８９記載の方法。
【請求項１９１】
トラバースする各ステップは、異なったプロセッサスレッドを使用して実施される請求項１８８記載の方法。
【請求項１９２】
トラバースする各ステップは、複数の異なったプロセッサスレッドを使用して実施される請求項１９１記載の方法。
【請求項１９３】
比較するステップにおいて少なくとも１つのビデオプロセッサスレッドが使用されて基準フレームビデオデータをターゲットフレームビデオデータと比較し、少なくとも１つのオーディオプロセッサスレッドが基準フレームオーディオデータをターゲットフレームオーディオデータと比較するために使用される請求項１５９記載の方法。
【請求項１９４】
基準フレームビデオデータをターゲットフレームビデオデータと比較し、基準フレームオーディオデータをターゲットフレームオーディオデータと比較するために、比較するステップにおいて少なくとも１つのプロセッサスレッドが使用される請求項１５９記載の方法。
【請求項１９５】
各フレームが複数のビットから構成されている複数の順次フレームのビットサイズを圧縮する方法において、
複数の比較されたブロックを獲得するために基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較するステップを含んでおり、基準フレームは複数の順次フレームの最初のフレームに設定されており、ターゲットフレームは最初は複数の順次フレームの後続フレームに設定されており、この比較するステップは、比較のための複数の異なったスレッドと、および均一なサイズを有する各スレッド内のサーチブロックとを使用するため、対応した比較されたブロックもまた均一のサイズを有しており、
元の状態から圧縮されたターゲットフレームの表現を獲得するために複数の比較されたブロックを使用するステップを含んでおり、この使用するステップは、
圧縮されることのできる隣接した比較されたブロックが存在するか否かを決定し、
圧縮されることのできる隣接した比較されたブロックの少なくともあるものに対して、そのある隣接した比較されたブロックを含む均一でないサイズの少なくとも１つのスーパーセットブロックを生成するステップを含んでいる方法。
【請求項１９６】
ある隣接した比較されたブロックは、全てのある隣接した比較されたブロックを含んでいる請求項１９５記載の方法。
【請求項１９７】
各スーパーセットブロックがある隣接した比較されたブロックを含んでいる均一でないサイズの複数のスーパーセットブロックが生成され、複数のスーパーセットブロックのそれぞれの中のある隣接した比較されたブロックは互いに隣接していない請求項１９５記載の方法。
【請求項１９８】
圧縮されることのできるある隣接した比較されたブロックは、リンクされたリストを使用して表される請求項１９５記載の方法。
【請求項１９９】
圧縮されることのできるある隣接した比較されたブロックは、２進ツリーを使用して表される請求項１９５記載の方法。
【請求項２００】
各フレームがマトリックスアレイに配列された複数のビットから構成されている複数の順次フレーム内のパターンをサーチする方法において、
複数の比較されたブロックを獲得するために基準フレーム内の複数の異なったサーチブロックをターゲットフレームと損失のある方式で比較するステップを含んでおり、基準フレームは複数の順次フレームの最初のフレームに設定されており、ターゲットフレームは最初に複数の順次フレームの後続フレームに設定されており、この比較するステップは、
第１のサーチブロックに対して、ターゲットフレーム内に存在する比較の割合を示す第１の加重を獲得し、
第１のサーチブロックに重なる第２のサーチブロックに対しては、ターゲットフレーム内に存在する比較の別の割合を示す第２の加重を獲得し、
第１の加重および第２の加重が共にある定められたしきい値を越えた比較の割合を有している場合、低いほうの比較の割合を有する第１および第２のサーチブロックの比較されたブロックの廃棄が行われる方法。
【請求項２０１】
圧縮されることのできる比較されたブロックは、リンクされたリストを使用して表される請求項２００記載の方法。
【請求項２０２】
圧縮されることのできる比較されたブロックは、２進ツリーを使用して表される請求項２００記載の方法。
【請求項２０３】
決定されたしきい値は、選択可能であるように調節されることができる請求項２００記載の方法。
【請求項２０４】
各フレームがマトリックスアレイに配列された複数のビットから構成されている複数の順次フレーム内のパターンをサーチする方法において、
複数の比較されたブロックを獲得するために基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較するステップを含んでおり、基準フレームは複数の順次フレームの最初のフレームに設定されており、ターゲットフレームは最初に複数の順次フレームの後続フレームに設定されており、この比較するステップは、
ターゲットフレームに対して予測された最適ブロックサイズおよび予測された移動方向を得るために基準フレームのマトリックスアレイ内の種々のポジションに異なったブロックサイズを有しているいくつかの異なった予測サーチブロックをターゲットフレーム中の種々の対応した予測ターゲットブロックと比較する予測スレッドを起動し、
予測された移動方向に対応した方向におけるターゲットフレームのトラバーサルを開始するステップを含んでおり、サーチブロックは予測された最適ブロックサイズに対応したサイズを有している方法。
【請求項２０５】
予測された最適ブロックサイズは、８×８バイト乃至１２８×１２８バイトの範囲内である請求項２０４記載の方法。
【請求項２０６】
予測された移動方向は水平、垂直および対角線方向の１つである請求項２０５記載の方法。
【請求項２０７】
予測された移動方向は水平、垂直および対角線方向の１つである請求項２０４記載の方法。
【請求項２０８】
トラバーサルを開始するステップにおいて、トラバーサルはプロセッサスレッドを使用して開始される請求項２０４記載の方法。
【請求項２０９】
トラバーサルを開始するステップにおいてトラバーサルは複数のプロセッサスレッドを使用して開始され、各プロセッサスレッドが予測された移動方向において予測されたブロックサイズによりターゲットフレームをトラバースする請求項２０４記載の方法。
【請求項２１０】
予測された移動方向に対応しない別の方向におけるターゲットフレームの別のトラバーサルを開始するステップをさらに含んでいる請求項２０９記載の方法。
【請求項２１１】
最初のトラバーサルおよび別のトラバーサルの一方を、そのトラバーサルが終了する前に終了するステップをさらに含んでいる請求項２１０記載の方法。
【請求項２１２】
終了するステップは、基準フレームの予め定められた部分を表す異なったサーチブロックによりターゲットフレームをトラバースした後で、比較されたブロックの整合が予め定められた数に達しなかったときに行われる請求項２１０記載の方法。
【請求項２１３】
各フレームが、少なくとも水平および垂直方向にトラバースされることのできるマトリックスアレイに配列された複数のビットから構成されている複数の順次フレーム内のパターンをサーチする方法において、
基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して、複数の比較されたブロックを獲得するステップを含んでおり、基準フレームは複数の順次フレームの最初のフレームに設定されており、ターゲットフレームは最初に複数の順次フレームの後続フレームに設定されており、この比較するステップは、
サーチブロックをターゲットフレーム内の対応したターゲットブロックと比較するためにターゲットフレームを単一のビットの列またはビットの行より大きい段階的増分で少なくとも水平および垂直方向にそれぞれトラバースするステップを含んでおり、このトラバースするステップは、マトリックスアレイのエッジにおけるサーチブロックおよび対応したターゲットブロックに対して、そのサーチブロックおよび対応したターゲットブロックのサイズがトラバースするステップ全体の期間中維持されることができるように、基準フレームおよびターゲットフレームのそれぞれ外側であるサーチブロックおよび対応したターゲットブロック内のビットポジションに同じ情報を埋込むステップを含んでいる方法。
【請求項２１４】
ビデオ情報を表す複数のビットおよびオーディオ情報を表す別の複数のビットからそれぞれ構成された複数の順次および時間関連フレームを獲得し、
複数の比較されたブロックを獲得するために基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較するステップを含んでおり、基準フレームは最初に複数の順次および時間関連フレームの最初のフレームに設定されており、ターゲットフレームは最初に複数の順次および時間関連フレームの後続フレームに設定されており、
さらに、圧縮されたターゲットフレームの表現を獲得するために複数の比較されたブロックを使用するステップを含んでいるパターンをサーチする方法。
【請求項２１５】
比較し、使用するステップが行われている期間中に、残っている複数の順次フレームのそれぞれが一度ターゲットフレームになるように、再度指定し、繰返すステップを反復するステップをさらに含んでいる請求項２１４記載の方法。
【請求項２１６】
獲得するステップは、複数の順次および時間関連フレームのそれぞれの中のビデオ情報とオーディオ情報との間にマーカーを配置するステップをさらに含んでいる請求項２１４記載の方法。
【請求項２１７】
圧縮されたターゲットフレームの表現は、リンクされたリストを使用する請求項２１４記載の方法。
【請求項２１８】
オーディオ情報を表す複数のビットは、カラースペースを使用してオーディオ情報を表し、比較するステップは、
第１のグループの複数の異なったサーチブロックのそれぞれを、ビデオ情報およびオーディオ情報の両方を含むターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを水平方向にトラバースし、
第２のグループの複数の異なったサーチブロックのそれぞれを、ビデオ情報およびオーディオ情報の両方を含むターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを垂直方向にトラバースするステップを含んでいる請求項２１４記載の方法。
【請求項２１９】
比較するステップは、第３のグループの複数の異なったサーチブロックのそれぞれを、ビデオ情報およびオーディオ情報の両方を含むターゲットフレーム内の異なったポジションと比較するためにターゲットフレームを対角線方向にトラバースするステップを含んでいる請求項２１８記載の方法。
【請求項２２０】
比較するステップはさらに、第４のグループの複数の異なったサーチブロックのそれぞれを、ビデオ情報およびオーディオ情報の両方を含むターゲットフレーム内の異なったポジションと異なった回転ポジションで比較するためにターゲットフレームをトラバースするステップを含んでいる請求項２１９記載の方法。
【請求項２２１】
第１のグループ、第２のグループ、第３のグループおよび第４のグループをトラバースするステップは、並列に動作される請求項２２０記載の方法。
【請求項２２２】
第１のグループ、第２のグループ、第３のグループおよび第４のグループの１つをトラバースするステップを、第１のグループ、第２のグループ、第３のグループおよび第４のグループの別のものをトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項２２１記載の方法。
【請求項２２３】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、第３および第４のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項２２１記載の方法。
【請求項２２４】
予め定められた数は１である請求項２２３記載の方法。
【請求項２２５】
整合は、同じ整合である必要がある請求項２２３記載の方法。
【請求項２２６】
整合は、損失を生じせることができる請求項２２３記載の方法。
【請求項２２７】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、第３および第４のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項２２１記載の方法。
【請求項２２８】
第１のグループ、第２のグループ、第３のグループをトラバースするステップは、並列に動作される請求項２１９記載の方法。
【請求項２２９】
第１のグループ、第２のグループおよび第３のグループの１つをトラバースするステップを、第１のグループ、第２のグループおよび第３のグループの別のものをトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項２２８記載の方法。
【請求項２３０】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２、および第３のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項２２８記載の方法。
【請求項２３１】
予め定められた数は１である請求項２３０記載の方法。
【請求項２３２】
整合は、同じ整合である必要がある請求項２３０記載の方法。
【請求項２３３】
整合は、損失を生じせることができる請求項２３０記載の方法。
【請求項２３４】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１、第２および第３のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、この特定のサーチブロックを終了するステップをさらに含んでいる請求項２２８記載の方法。
【請求項２３５】
第１のグループおよび第２のグループをトラバースするステップは、並列に動作される請求項２１８記載の方法。
【請求項２３６】
第１のグループおよび第２のグループの一方をトラバースするステップを、第１のグループおよび第２のグループの他方をトラバースするステップを終了する前に終了するステップをさらに含んでいる請求項２３５記載の方法。
【請求項２３７】
比較するステップはサーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１および第２のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合が予め定められた数に達しなかった場合に、その特定のサーチブロックを終了するステップをさらに含んでいる請求項２３５記載の方法。
【請求項２３８】
予め定められた数は１である請求項２３７記載の方法。
【請求項２３９】
整合は、同じ整合である必要がある請求項２３７記載の方法。
【請求項２４０】
整合は、損失を生じせることができる請求項２３７記載の方法。
【請求項２４１】
比較するステップは、サーチブロックをターゲットフレーム内のターゲットブロックと比較するステップをさらに含んでおり、ターゲットフレームの予め定められた部分が比較された後で、第１および第２のグループをトラバースするステップによって使用されたサーチブロックの特定のものと対応したターゲットブロックとの間の整合の割合より、そのサーチブロックの他のものと対応したターゲットブロックとの間の整合の割合が予め定められた割合だけ大きい場合に、この特定のサーチブロックを終了するステップをさらに含んでいる請求項２３５記載の方法。
【請求項２４２】
トラバースするステップにおいて、ターゲットフレーム内の順次の異なったポジションが互いに重なるようにターゲットフレームがトラバースされる請求項２１８記載の方法。
【請求項２４３】
順次の異なったポジションは、多くて予め定められた数のビットの行および予め定められた数のビットの列だけ異なっている請求項２４２記載の方法。
【請求項２４４】
予め定められた数のビットの行は１であり、予め定められた数のビットの列は１である請求項２４３記載の方法。
【請求項２４５】
ターゲットフレームを水平方向にトラバースするステップおよびターゲットフレームを垂直方向にトラバースするステップの少なくとも一方において、ターゲットフレーム全体がトラバースされる請求項２１８記載の方法。
【請求項２４６】
ターゲットフレーム全体を水平方向にトラバースするステップにおいて、ターゲットフレーム内の異なった垂直ポジションにおいて水平方向におけるパスが繰返され、
ターゲットフレーム全体を垂直方向にトラバースするステップにおいて、ターゲットフレーム内の異なった水平ポジションにおいて垂直方向におけるパスが繰返される請求項２４５記載の方法。
【請求項２４７】
ターゲットフレーム内の隣接した異なった垂直ポジションおよび隣接した異なった水平ポジションは、多くて予め定められた数のビットの行および予め定められた数のビットの列だけ異なっている請求項２４６記載の方法。
【請求項２４８】
予め定められた数のビットの行は１であり、予め定められた数のビットの列は１である請求項２４７記載の方法。
【請求項２４９】
トラバースする各ステップは、異なったプロセッサスレッドを使用して実施される請求項２４６記載の方法。
【請求項２５０】
トラバースする各ステップは、複数の異なったプロセッサスレッドを使用して実施される請求項２４９記載の方法。
【請求項２５１】
基準フレームビデオデータをターゲットフレームビデオデータと比較するステップにおいて少なくとも１つのビデオプロセッサスレッドが使用され、少なくとも１つのオーディオプロセッサスレッドが基準フレームオーディオデータをターゲットフレームオーディオデータと比較するために使用される請求項２１４記載の方法。
【請求項２５２】
基準フレームビデオデータをターゲットフレームビデオデータと比較し、基準フレームオーディオデータをターゲットフレームオーディオデータと比較するために、比較するステップにおいて少なくとも１つのプロセッサスレッドが使用される請求項２１４記載の方法。
【請求項２５３】
使用するステップにおいて、損失を生じることなく元の状態と比較して圧縮されたターゲットフレームの表現が獲得される請求項２１４記載の方法。
【請求項２５４】
比較するステップにおいて、サーチブロックはアンド演算を使用してターゲットフレームと比較される請求項２１４記載の方法。
【請求項２５５】
使用するステップにおいて、損失を導入することにより元の状態と比較して圧縮されたターゲットフレームの表現が獲得される請求項２１４記載の方法。
【請求項２５６】
比較するステップにおいて、サーチブロックはアンド演算を使用してターゲットフレームと比較される請求項２５５記載の方法。
【請求項２５７】
比較するステップにおいて、サーチブロックはオア演算を使用してターゲットフレームと比較される請求項２５５記載の方法。
【請求項２５８】
比較するステップにおいて、サーチブロックは排他的オア演算を使用してターゲットフレームと比較される請求項２５５記載の方法。
【請求項２５９】
比較するステップにおいて、サーチブロックは加算演算を使用してターゲットフレームと比較される請求項２５５記載の方法。
【請求項２６０】
比較するステップにおいて、サーチブロックは減算演算を使用してターゲットフレームと比較される請求項２５５記載の方法。
【請求項２６１】
比較するステップにおいて、サーチブロックは乗算演算を使用してターゲットフレームと比較される請求項２５５記載の方法。
【請求項２６２】
比較するステップにおいて、サーチブロックは除算演算を使用してターゲットフレームと比較される請求項２５５記載の方法。
【請求項２６３】
使用するステップは、表現に対して使用されるスーパーセットブロックを獲得するために複数の比較されたブロックの重複したものを組合せる請求項２１４記載の方法。
【請求項２６４】
比較するステップは、サーチブロックとターゲットフレーム内に存在する対応したターゲットブロックとの間の同じ整合を表す比較されたブロックを追跡するステップを含んでいる請求項２１４記載の方法。
【請求項２６５】
追跡するステップは、基準フレームとターゲットフレームとの間において達成可能な圧縮の量の動的表示を提供するために使用され、比較するステップは、圧縮ターゲット比率を選択するステップをさらに含んでいる請求項２６４記載の方法。
【請求項２６６】
比較するステップは、ターゲットフレームに関して圧縮ターゲット比率に達したことを動的表示が示したとき、中止される請求項２６４記載の方法。
【請求項２６７】
比較するステップは、表現内で許容されることのできる損失の所望の量を選択するステップをさらに含んでいる請求項２６６記載の方法。
【請求項２６８】
比較されたブロックは、ターゲットブロック内のビットの割合が所望の損失量に少なくとも等しい場合に、サーチブロックと同じであるとみなされる請求項２６７記載の方法。
【請求項２６９】
比較するステップは、表現内で許容されることのできる損失の量を選択するステップをさらに含んでいる請求項２１４記載の方法。
【請求項２７０】
比較するステップは、
サーチブロックとターゲットフレームとの間の整合の可能性の推定値を獲得するために予測プロセッサスレッドを起動し、
基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して複数の比較されたブロックを獲得するために使用される少なくとも１つの比較プロセッサスレッドにこの推定値を送るステップを含んでいる請求項２１４記載の方法。
【請求項２７１】
比較するステップにおいて、比較はビットレベルで行われる請求項２１４記載の方法。
【請求項２７２】
比較するステップにおいて、比較はバイトレベルで行われる請求項２１４記載の方法。
【請求項２７３】
各フレームが複数のビットから構成されている複数の順次フレームのビットサイズを圧縮する方法において、
複数の比較されたブロックを獲得するために基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較するステップを含んでおり、基準フレームは最初に開始フレームに設定されており、ターゲットフレームは最初に後続フレームに設定されており、この比較するステップは、
基準フレームと後続フレームとの間の所望の圧縮比に達したか否かを決定し、
所望の圧縮比に達した場合には、比較ステップを終了し、
所望の圧縮比に達しなかった場合には、元の状態と比較して圧縮されたターゲットフレームの表現を獲得するために複数の比較されたブロックを使用するステップを含んでいる方法。
【請求項２７４】
ターゲットフレームであった後続フレームを基準フレームとして再度指定し、そのターゲットフレームを後続フレームに後続する別の後続フレームとして再度指定し、
比較し、決定するステップを繰返すステップをさらに含んでいる請求項２７３記載の方法。
【請求項２７５】
各フレームが複数のビットから構成されている複数の順次フレームに関するパターン認識のための装置において、
予測スレッドを起動して、デフォルトパターン方向を決定し、少なくとも水平および垂直方向において各方向に対して異なったスレッドを使用して基準フレームからの種々のサーチブロックをターゲットフレームの対応したターゲットサーチエリアと比較し、比較整合をリンクされたリストとして獲得し、重なった比較整合を含むスーパーセットブロックを獲得するためにこのリンクされたリストを処理し、結果的に得られた圧縮されたフレームを記憶するためにアプリケーションプログラムを使用するプロセッサと、
結果的に得られた圧縮されたフレームを記憶するメモリとを備えている装置。
【請求項２７６】
予測スレッドを起動して、デフォルトパターン方向を決定し、少なくとも水平および垂直方向において各方向に対して異なったスレッドを使用して基準フレームからの種々のサーチブロックをターゲットフレームの対応したターゲットサーチエリアと比較し、比較整合をリンクされたリストとして獲得し、重なった比較整合を含むスーパーセットブロックを獲得するためにこのリンクされたリストを処理し、結果的に得られた圧縮されたフレームを記憶する、パターン認識を行うために使用可能なコンピュータ読出し可能な媒体上に記憶されたコンピュータプログラムを備えている、プロセッサにより使用可能なコンピュータ読出し可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの隣接したブロック内のパターンを決定するための方法および装置に関する。
【背景技術】
【０００２】
データを圧縮すると共に、その後に、前に圧縮されたデータを圧縮解除する多くの種々の技術が存在している。ＺＩＰ（登録商標）データ圧縮は、ファイルの圧縮およびそれに続く前に圧縮されたデータの圧縮解除を可能にするよく知られている技術の１つの例である。
【０００３】
全ての圧縮技術は、ファイル内に存在することのできる冗長を除去することによりファイルのサイズの減少、あるいはその“圧縮”を試みる。ある圧縮技術と別のものとを区別するものが、冗長を除去するために使用される方法である。一般的に述べると、ある圧縮技術が冗長の除去に成功ると、それだけ一層行われる圧縮の量が増加する。
【０００４】
冗長を除去するために、あるタイプのパターン整合が典型的に使用される。たとえば、映画の連続したフレームにおいて冗長なパターンが時々生じることが知られている。したがって、映画がたとえばＭＰＥＧのようなあるフォーマットにデジタル化されたとき、イメージフレームの元のシーケンスは、イメージフレームの元のシーケンス中に存在する情報を、人間の眼がその再生を受け容れるのに十分な割合だけ含んでいるＩ、ＢおよびＰイメージフレームのＭＰＥＧシーケンスにより置換される。しかしながら、イメージフレームのＭＰＥＧシーケンスを獲得するときに使用される数学的表現はフレームの元のシーケンス内に存在するデータの全てを保存できないので、Ｉ、ＢおよびＰイメージフレームのＭＰＥＧシーケンスに損失が生じる。他の多くの状況でも、冗長なパターンが存在し、これに対してパターン整合操作が冗長を除去するために使用されることができる。ｘ線のような異なったラジオグラフイメージのシーケンスは冗長なパターンを含んでいるであろう。種々の実行可能なまたは実行不可能なファイルの集りの間にも冗長なパターンが含まれる。したがって、明らかに、任意のタイプのデータセットと任意の他のデータセットに共通するパターンを見出すことを試みたとき、両データセットが比較されることができる。このようにして、以下の説明において、データセットが獲得され、別のデータセットと比較されることができる。別のデータセットと比較される各データセットは、そのデータセットからのデータをマトリックスアレイ中に含むあるフレームにフォーマット化されたものとして記述されることとなり、このフレームはその後、別のデータセットからのデータを含む別のフレームと比較されることができる。また、フレームという用語の使用法は、各々が個別のフレーム中にあり、個別のデータセットを構成する映画のイメージの関連した時間シーケンスから容易に理解されるが、この用語は任意のタイプのデータセットに適用可能であり、したがって、意図されるその適用可能性および使用法は、映画からの種々のイメージの場合よりはるかに広いことが認識される。
【０００５】
さらに、冗長なパターンが存在することを理解することと、実際にそれらを見出すこととの間には大きな違いがある。映画のイメージのシーケンスの例で続けると、デジタルデータでは、イメージの少なくとも一部における動きのために各フレームが典型的に異なっていることが明らかである。また、その動きは一時に２以上の方向で発生することができる。多くの方向に存在する動きに関しては、このために、単一の方向に動きが発生したときはるかに効率的に動作するＭＰＥＧのようなパターン認識技術に関する問題が生じる可能性が高い。ＭＰＥＧの場合のさらに複雑な動きを含む隣接したフレームに関しては、このようなフレームは、含まれているデータが少ないＢまたはＰタイプの予測フレームではなく、新しい独立したフレームまたはＩフレームとなることが必要とされることがある。その結果、対応したＭＰＥＧシーケンス内に非常に多くのIフレームが存在する可能性が高くなり、したがってフレームの間に存在しているが見出されなかったそれらのパターンが認識されることが少ないために、行われる圧縮が少なくなる。これは、ＭＰＥＧに関しては多くの理由の組合せのために発生するが、しかし、とくに顕著なものは、限られた運動ベクトル知識および運動ベクトルまたは移動の方向しか存在せず、それは今は見出されていないが存在している限られた運動ベクトル知識とは異なっていることである。
【０００６】
さらに、パターンが決定される方式は、行われる圧縮の量だけでなく、発生する損失の量にも影響を与える。たとえば損失のある圧縮技術であるＭＰＥＧでは、パターンは予め設定されたブロックサイズを使用して位置をつきとめられるので、圧縮を達成するために、多量の損失が許容されなければならない。
【０００７】
さらに、圧縮は、デジタルデータのある部分を数学的表現で表すことによりＭＰＥＧのような技術で行われ、この表現は典型的に元のものに緊密に近似しているが、実際は異なっている。しかしながら、これらの技術により圧縮は得られるが、その圧縮プロセス中に、望ましくないアーティファクトが導入される可能性が高く、そのために、データを後で圧縮解除したときに、たとえば、結果的に得られた画像品質の劣化等の問題が発生する可能性が高い。たとえば、ＭＰＥＧでは、圧縮に使用されたＤＣＴアルゴリズムの限界のために、元のデータ内容の２０％以上の損失が発生することがよく知られている。また、ＬＺＷのような無損失圧縮技術は損失を発生させないが、それらは典型的に大量の圧縮を導入することができない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
したがって、無損失モードでまたは損失モードのどちらで動作しているときでも、データの隣接したフレームの間に存在する冗長パターンの大部分を認識するだけでなく、損失を生じることなく動作することのできるパターン整合技術を有することが望ましい。  
ここに記載されている本発明は、有効なパターン整合技術を提供する。
【課題を解決するための手段】
【０００９】
本発明は、データの隣接した順次フレームの間のパターン認識を行うための方法および装置を記載している。このデータは種々のタイプの関連していないデータであることができ、あるいは時間シーケンスで関連付けられ、オーディオおよびイメージの両データを各データフレーム内に含むことができる。予測スレッドを使用してデフォルトパターン方向を決定し、その後水平、垂直、対角線および回転方向において異なったスレッドおよび並列処理技術を使用して基準フレームからの種々のサーチブロックをターゲットフレームの対応したターゲットサーチエリアと比較した後、パターン認識が行われ、十分な数の整合を獲得していない方向スレッドは終了される。整合が見出された場合、それらはリンクされたリストまたは２進ツリーとして記憶され、その後、あるフレーム内の重複した整合がスーパーセットブロックとして表されるように処理される。
【００１０】
１つの特徴において、本発明は、各フレームが複数のビットから構成されている複数の順次フレームのビットサイズを圧縮する方法を提供する。この方法は、基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して、複数の比較されたブロックを獲得するものであり、基準フレームは最初は複数の順次フレームの最初のフレームに設定されており、ターゲットフレームは最初は複数の順次フレームの後続フレームに設定されている。複数の比較されたブロックは圧縮されたターゲットフレームの表現を獲得するために使用される。その後、基準フレームはターゲットフレームであった後続フレームとして再度指定され、ターゲットフレームは後続フレームに後続する別の後続フレームとして再度指定され、比較し、使用するステップが繰返される。
【００１１】
別の特徴において、ターゲットフレーム中に存在する冗長なパターンのリンクされたリストを基準フレームから獲得する方法が提供され、基準フレームおよびターゲットフレームはそれぞれ複数のビットから構成されている。この方法は、基準フレームの複数のサーチブロック部分のそれぞれをターゲットフレーム内の複数の位置と比較して複数の整合を決定し、各整合に対して、サーチブロック部分にリンクされた位置識別子によりその整合に対応したターゲットフレームのその部分を表すステップを含んでいる。
【００１２】
別の特徴において、複数の順次フレーム内のパターンをサーチする方法が提供され、各フレームは、水平、垂直および対角線方向にトラバースされることのできるマトリックスアレイに配列された複数のビットから構成されている。この方法は、基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して、複数の比較されたブロックを獲得するステップを含んでおり、基準フレームは複数の順次フレームの開始フレームに設定されており、ターゲットフレームははじめに、複数の順次フレームの後続フレームに設定されている。比較するステップは、ターゲットフレームを水平方向にトラバースして少なくとも第１のグループのサーチブロックをターゲットフレーム内の対応した水平方向のターゲットブロックと比較し、ターゲットフレームを垂直方向にトラバースして少なくとも第２のグループのサーチブロックをターゲットフレーム内の対応した垂直方向のターゲットブロックと比較するステップを含んでおり、第２のグループのサーチブロックは第１のグループのサーチブロックと異なっていてもよいし、異なっていなくてもよい。
【００１３】
別の特徴において、本発明は、複数の順次フレーム内のパターンをサーチする方法を提供し、各フレームはマトリックスアレイに配列された複数のビットから構成されている。この方法は、基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して複数の比較されたブロックを獲得するステップを含んでおり、基準フレームは複数の順次フレームの開始フレームに設定されており、ターゲットフレームは最初、複数の順次フレームの後続フレームに設定されている。比較するステップは、ターゲットフレームを複数の異なった方向にトラバースしてサーチブロックをターゲットフレーム内の対応したターゲットブロックと比較するステップを含んでおり、トラバースするステップは、並列に処理される複数の異なったスレッドを起動するステップを含んでおり、異なった各スレッドは異なったサーチブロックおよび異なった方向の少なくとも一方に関して動作し、そのトラバーサルの結果としてターゲットフレームと基準フレームとの間に十分な数の整合が見出されたか否かを決定するステップを含んでいる。その後、複数の異なったスレッドのあるものを終了するステップが発生し、この終了するステップは、特定のスレッドに関してトラバースした結果十分な数の整合が得られないことが決定された場合にその特定のスレッドに対して発生する。
【００１４】
別の特徴において、本発明は、複数の順次フレームのビットサイズを圧縮する方法を提供し、各フレームは複数のビットから構成されている。この方法は、基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して、複数の比較されたブロックを獲得するステップを含んでおり、基準フレームは複数の順次フレームの最初のフレームに設定されており、ターゲットフレームは複数の順次フレームの後続フレームに設定されている。比較するステップは、比較のための複数の異なったスレッドと、および均一なサイズを有する各スレッド内のサーチブロックとを使用するため、対応した比較されたブロックもまた均一のサイズを有している。この方法は複数の比較されたブロックを使用して、元の状態から圧縮されたターゲットフレームの表現を獲得する。使用するステップは、圧縮されることのできる隣接した比較されたブロックが存在するか否かを決定し、圧縮されることのできる隣接した比較されたブロックの少なくともあるものに対して、そのある隣接した比較されたブロックを含む均一でないサイズの少なくとも１つのスーパーセットブロックを生成するステップを含んでいる。
【００１５】
別の特徴において、本発明は、複数の順次フレーム内のパターンをサーチする方法を提供し、各フレームはマトリックスアレイに配列された複数のビットから構成されている。この方法は、基準フレーム内の複数の異なったサーチブロックをターゲットフレームと損失方式で比較して、複数の比較されたブロックを獲得するステップを含んでおり、基準フレームは複数の順次フレームの最初のフレームに設定されており、ターゲットフレームは最初に複数の順次フレームの後続フレームに設定されている。比較するステップは、第１のサーチブロックに対して、ターゲットフレーム内に存在する比較の割合を示す第１の加重を獲得し、第１のサーチブロックに重複する第２のサーチブロックに対しては、ターゲットフレーム内に存在する比較の別の割合を示す第２の加重を獲得するステップを含んでいる。第１の加重および第２の加重が共にある定められたしきい値を越えた比較の割合を有している場合、低いほうの比較の割合を有する第１および第２のサーチブロックの比較されたブロックの廃棄が行われる。
【００１６】
別の特徴において、本発明は、複数の順次フレーム内のパターンをサーチする方法を提供し、各フレームはマトリックスアレイに配列された複数のビットから構成されている。この方法は、基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して、複数の比較されたブロックを獲得するステップを含んでおり、基準フレームは複数の順次フレームの最初のフレームに設定されており、ターゲットフレームは最初に複数の順次フレームの後続フレームに設定されている。比較するステップは、ターゲットフレームに対して予測された最適ブロックサイズおよび予測された移動方向を獲得するために基準フレームのマトリックスアレイ内の種々のポジションに異なったブロックサイズを有しているいくつかの異なった予測サーチブロックをターゲットフレーム中の種々の対応した予測ターゲットブロックと比較する予測スレッドを起動するステップを含んでいる。比較するステップはまた、予測された移動方向に対応した方向におけるターゲットフレームのトラバーサルを起動し、サーチブロックは予測された最適ブロックサイズに対応したサイズを有している。
【００１７】
本発明の別の特徴において、複数の順次フレーム内のパターンをサーチする方法が提供され、各フレームはマトリックスアレイに配列された複数のビットから構成されている。この方法は、基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して、複数の比較されたブロックを獲得するステップを含んでおり、基準フレームは複数の順次フレームの初期フレームに設定されており、ターゲットフレームは最初に複数の順次フレームの後続フレームに設定されている。比較するステップは、ターゲットフレームに対して予測された最適ブロックサイズおよび予測された移動方向を獲得するために基準フレームのマトリックスアレイ内の種々のポジションに異なったブロックサイズを有しているいくつかの異なった予測サーチブロックをターゲットフレーム中の種々の対応した予測ターゲットブロックと比較する予測スレッドを起動するステップを含んでいる。比較するステップはまた、予測された移動方向に対応した方向におけるターゲットフレームのトラバーサルを起動し、サーチブロックは予測された最適ブロックサイズに対応したサイズを有している。
【００１８】
別の特徴において、本発明は、複数の順次フレーム内のパターンをサーチする方法を提供し、各フレームは、少なくとも水平および垂直方向にトラバースされることのできるマトリックスアレイに配列された複数のビットから構成されている。この方法は、基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して、複数の比較されたブロックを獲得するステップを含んでおり、基準フレームは複数の順次フレームの最初のフレームに設定されており、ターゲットフレームは最初に複数の順次フレームの後続フレームに設定されている。比較するステップは、ターゲットフレームを単一のビットの列またはビットの行より大きい段階的増分で少なくとも水平および垂直方向にそれぞれトラバースして、サーチブロックをターゲットフレーム内の対応したターゲットブロックと比較するステップを含んでいる。トラバースするステップは、マトリックスアレイのエッジにおけるサーチブロックおよび対応したターゲットブロックに対して、そのサーチブロックおよび対応したターゲットブロックのサイズがトラバースするステップの全期間中維持されることができるように、基準フレームおよびターゲットフレームのそれぞれ外側であるサーチブロックおよび対応したターゲットブロック内のビットポジションに同じ情報を埋込むステップを含んでいる。
【００１９】
本発明の別の特徴において、パターンをサーチする方法が提供される。この方法は、ビデオ情報を表す複数のビットおよびオーディオ情報を表す別の複数のビットからそれぞれ構成された複数の順次および時間関連フレームを獲得するステップを含んでいる。基準フレーム内の複数の異なったサーチブロックがターゲットフレームと比較され、それによって複数の比較されたブロックが獲得され、基準フレームは最初に複数の順次および時間関連フレームの最初のフレームに設定されており、ターゲットフレームは最初に複数の順次および時間関連フレームの後続フレームに設定されている。複数の比較されたブロックは、圧縮されたターゲットフレームの表現を獲得するために使用される。
【００２０】
別の特徴において、本発明は複数の順次フレームのビットサイズを圧縮する方法を提供し、各フレームは複数のビットから構成されている。この方法は、基準フレーム内の複数の異なったサーチブロックをターゲットフレームと比較して、複数の比較されたブロックを獲得するステップを含んでおり、基準フレームは最初に最初のフレームに設定されており、ターゲットフレームは最初に後続フレームに設定されている。比較するステップは、基準フレームと後続フレームとの間の所望の圧縮比に達したか否かを決定するステップを含んでいる。所望の圧縮比に達した場合、比較するステップは終了される。所望の圧縮比に達しなかった場合、複数の比較されたブロックは、元の状態と比較して圧縮されたターゲットフレームの表現を獲得するために使用される。
【発明を実施するための最良の形態】
【００２１】
本発明のその他の特徴、利点および目的は以下の説明から明らかになるであろう。  
本発明の上記およびその他の特徴および利点は、本発明の非制限的な例示的実施形態による図面を参照として、以下の詳細な説明さらに詳しく記載されている。なお、図面において、同じ参照符号はいくつかの図面にわたって類似した部分を表している。  
本発明は、整合されたパターンを示した結果として圧縮を発生させるが、しかしさらに圧縮されるべき整合されたパターンを表したデータの圧縮もまた可能にするパターン整合方法を提供する。上述したように、本発明は任意のタイプのデジタルデータで動作するために使用されることができるが、これはどのタイプのデジタルデータも他のデジタルデータと比較可能なために、本発明は、映画のデジタルマスターからのビデオイメージのシーケンス、実時間デジタルカメラフィードから得られたイメージのシーケンス、関連付けられた医学的イメージのシーケンス、オーディオコンテンツまたはそれぞれが他のもののコピーであるように意図された冗長なデータ記憶デバイスを表すデータのシーケンスのような、データ内にパターンが存在する可能性が非常に高いアプリケーションに対してとくに重要である。
【００２２】
ビデオイメージのような関連付けられたシーケンスに対する本発明のパターン認識特徴の動作は、イメージを表示し、オーディオを再生するために使用されることのできる元のデジタルデータのフレームについて動作されることが好ましいこともまた認識される。したがって、たとえば、デジタルビデオカメラからのフィードは、それが実時間のものか、または遅延されたものか、あるいはデジタル版の映画であるかにかかわらず、操作されることができる。しかしながら、ＭＰＥＧのようなシーケンスに対して関連付けられたデータを記憶するために以前から知られている圧縮技術が使用されている場合、本発明はこのＭＰＥＧを復号して、元のマスターシーケンスのフレームに最も厳密に整合している対応したシーケンスのフレームを獲得してそれを操作することが好ましい。もっとも、これは、ＭＰＥＧ符号化されたデータがその符号化された形態で操作されることが可能であり、本発明による利点が依然として得られるため、必要ない。
【００２３】
明らかになるように、本発明は任意のタイプのデータを、そのデータがランダムに収集され、前に圧縮された、あるいは前に既知のデータフォーマットにされたものであっても、操作する能力を有しているが、その１つの理由は、パターン認識動作がビットレベルで行われ、データのあるフレーム中のビットとデータの別のフレーム中のビットとの比較が好ましく行われるためである。したがって、たとえば、サーチブロックが画素を使用してイメージを表すデータを含んでおり、各画素が２４ビットとして、１つのフレームで表される場合、対応したサーチブロックエリアが、２４ビットのうちの２２ビットがサーチブロック中の対応した画素において同じであり、２ビットだけが異なったものとしてそれぞれ識別される画素を含んでいるならば、本発明による比較により、この類似度が決定されることができ、また、あらゆる２４ビットの中の少なくとも２２ビットは同じものであるため、以下に説明するように、サーチエリアをサーチブロックと同じものとして識別するリンクされたリストが生成されることが可能であり、著しい圧縮が依然として行われることができ、また、９０％を越える正確度が依然として保持されることができる。
【００２４】
ビデオまたはオーディオのような時間的に関連付けられたデータに関して、種々のフレームの間にはある関係が存在する。ビデオおよびオーディオの両方を含む映画に関しては、映画の中の各イメージに対応して、この映画と同期されなければならないサウンドのその部分はまた対応している。ＭＰＥＧのようなシステム中では、符号化および復号が別々に行われる分離したオーディオストリームを必要とするオーディオの完全に別個の圧縮が存在するが、本発明は、上述したように操作されるデータの“タイプ”を区別しない。したがって、本発明においては、オーディオおよびビデオの両データを含むフレーム内にパターンが存在するか否かを決定するときに、オーディオデータの別個のストリームは必要ない。本発明は、同じフレーム内に存在する両タイプのデータについて動作することにより両者におけるパターンを認識することができる。このデータは、それらの間で何等差別なく操作されることができる。もっとも、以下説明するように、所定のフレーム内のオーディオデータおよびビデオデータを分割することにより、ある利点が得られる。
【００２５】
しかしながら、本発明は、オーディオ情報を含むフレームのシーケンスを用いて作用したとき、必ずしもそうとは限らないが、本出願と同じ日に同じ発明者により出願されて本出願人の代理人参照番号042503/0261933を有する米国特許出願明細書（“Optical Encoding of Audio Data,”）に記載されている技術を使用して変換されたオーディオデータと共に動作することがもっとも好ましい。この別の出願には、オーディオデジタルデータをカラー・スペースデジタルデータに変換する技術が記載されている。
【００２６】
上記の光学的符号化出願明細書において説明されているように、デジタル的にサンプリングされたオーディオ信号は、同じ時間インターバルにより間隔を隔てられた、デジタルオーディオ信号エレメントとも呼ばれるデジタル値のシーケンスである。オーディオおよびビデオデータは異なったフォーマットを有しているため、オーディオデータは通常ビデオデータに付加されず、それと共に符号化されない。光学的符号化は、後でビデオデータと同時に符号化するためにオーディオデータがビデオデータに付加されることができるようにオーディオデータを操作するメカニズムを提供する。とくに、デジタル的にサンプリングされたオーディオ信号エレメントは、可能なカラーのパターンから選択されたカラーにマッピングされる。種々の時点からのオーディオデータは、再生速度を示すヘッダ（示されていない）に基づいて時間的に追跡され、それによってその後適切な時間でのデジタルオーディオエレメントのシーケンスの再生が可能になる。異なった時点で発生し、同じ振幅を有するオーディオ信号は全て、同じカラーがそれらに割当てられる。マッピングのプロセスはカラーを対応したオーディオデータに対して異なった時点で割当てる。マッピングプロセスの後、各オーディオデータは、関連付けられた振幅を有する代りに、カラールックアップテーブルから得られた関連付けられたカラーを有している。したがって、同じ振幅を有するデジタルオーディオ信号エレメントは、同じカラーを有している。また、得られたパレットは、割当てられることのできる可能なカラーのパレットのサブパレットである。
【００２７】
光学的符号化の出願においてデジタル的にサンプリングされた信号エレメントを可能なカラーのパレットから選択されたカラーにマッピングするプロセスは、現在のデジタルオーディオ信号エレメントに対する振幅を読出すことによって始まる。その後、あるカラーは前にその振幅に割当てられたか否かが決定される。あるカラーが前にその振幅に割当てられている場合、そのカラーに対して前に割当てられたカラールックアップが現在のサンプルに割当てられる。あるカラーが前にその振幅に割当てられていない場合、新しいカラールックアップがそのカラーおよび振幅の両方に割当てられ、そのカラーはサブパレットに追加される。サブパレットは、デジタル的にサンプリングされたオーディオ信号エレメントの振幅に割当てられたカラーのセットである。その後、処理すべきデジタルオーディオ信号エレメントがあるか否かが決定される。処理すべきデジタルオーディオ信号エレメントがある場合、プロセスは次のサンプルに進み、現在のサンプルに対する振幅が読み込まれる。プロセスの終りに、サブパレットは、デジタル的にサンプリングされた全てのオーディオ信号エレメントの全ての時間における振幅を記述するために必要とされた全てのカラーを含んでいる。各サンプルについても、振幅の代りに、サブパレットからの関連付けられたカラーが存在する。このプロセスの出力は、サブパレットおよびシーケンスデジタルオーディオ信号エレメントをそれらの変換されたカラーフォーマットで含んでいるフレームである。
【００２８】
増補ビデオフレームが復号された後、カラーオーディオは増補ビデオフレームから分離され、デジタルオーディオ信号エレメントが光学的符号化出願において説明されているように復元されることができる。デジタルオーディオ信号エレメントを復元したとき、現在のデジタルオーディオ信号エレメントに対するデジタルカラー値が読込まれ、対応したデジタルオーディオ値はカラールックアップに基づいて検索される。その後、処理すべきデジタルオーディオ信号エレメントを表すデジタルカラー値があるか否かが決定される。処理すべき値が存在している場合、このプロセスは次のサンプルに進み、現在の振幅に対する振幅が読み込まれる。プロセスの出力はもとのデジタル的にサンプリングされたオーディオ信号である。
【００２９】
カラースペース変換されたオーディオデジタルデータは、ある１つのフレーム内において全てのフレームに対して類似した方式で編成され、以下さらに詳細に説明するように、あるフレーム内のフレームブロックのどれがこのオーディオデータを含んでいるかを示すマーカーが存在していることが好ましい。
【００３０】
図１は、デジタルカメラ、ハードドライブ、ディスク制御装置、または任意のタイプのデータをストリームでダウンストリーム装置120に送信することのできる任意の媒体であることができるデジタル伝送装置110を備えている本発明による例示的にシステム100を示している。示されているように、装置120は、マルチスレッデッド並列動作を行うことのできるプロセッサを備えたコンピュータであることが好ましい。この装置120を使用してパターン認識が行われた後、本発明による出力データを含むストリームの後続的な符号化が行われることができる。また、ネットワーク130と、およびデータが意図されたとおりに使用されることができるように、もとの操作されたデータを再生成するだけでなく、復号を行うこともできる別の装置140とが示されている。これに関して、本出願では、本発明によるパターン認識を達成するために使用される方法を説明する。パターンがひとたび認識され、この明細書に記載されているリンクされたリスト、２進ツリーまたは別のデータ記憶フォーマットを使用して相関されると、この明細書に記載されているようにフォーマット化されたデータから元のデータを獲得することは簡単であることが認識されるであろう。
【００３１】
上記のシステムは、この明細書に記載されている本発明の利点が使用されることのできる１つの方式を示すために与えられているが、これは一例に過ぎない。ここに記載されている発明を実施することのできるプロセッサを備えたコンピュータとは別の単一のコンピュータおよび装置が代りに使用可能であるため、たとえば、異なったコンピュータ装置120および140がそれぞれ構成されることができる。その他多数の変形が可能である。また、述べられているような装置は典型的に、この明細書の教示に基づいて書込まれたプログラム命令と共にＩｎｔｅｌ  Ｐｅｎｔｉｕｍ（Ｒ）４マイクロプロセッサまたはＤＳＰのようなあるタイプのプロセッサを備えることになるが、フィールドプログラム可能なゲートアレイのような、本発明を実施する別のハードウェアもまた使用されことができる。プログラム命令は、Ｃ＋＋または別のコンピュータプログラミング言語で書込まれることが好ましい。繰返し使用される反復ルーチンについては、これらは高速処理のためにアセンブラ言語で書込まれることができる。上述したように、本発明は、以下さらに詳細異に説明するように、１つのフレーム内のマトリックスアレイにフォーマット化されていることが好ましいデータで動作することができる。時間的に関連付けられていないデータに関して、ブロックは、同じデータ量を記憶する能力を有していてもよいし、有していなくてもよいフレームにフォーマット化されることができる。イメージおよびオーディオデータのような時間的に関連付けられたデータに関しては、各イメージおよびオーディオデータを関連付けられたそれは、それ自身のフレームを有することが好ましい。もっとも、それは必須ではない。
【００３２】
図２Ａは、フレームブロック230中に配置されたデータを含むフレームブロック230で分割された代表的なフレームを示している。このデータは時間的に関連付けられていてもよいし、あるいは関連付けられていなくてもよい。
【００３３】
図２Ｂ１は、各イメージに対するデータを含んでおり、そのイメージが対応したオーディオデータだけでなく互いに時間的に関連付けられ、これらのオーディオデータもまたイメージに時間的に関連付けられているデジタル映画であることができるシーケンス210-1，210-2・・・210-ｎの一例を示している。各シーケンス210は、図２Ｂ２に示されている３つのフレーム220によって示されているように、このように時間的に互いに関連付けられたフレーム220を含んでいる。これらのフレーム220は、ある数（この明細書では説明のために２０）のフレームブロック230を有するものとして示されており、そのうちの１５（230V1，23V2・・・23Vn）はビデオイメージデータ用として示されており、その中の５（230A1，230A2・・・230An）はオーディオ情報用として示されている。１つの重要な特徴は、フレームブロック230Vのマトリックスアレイ全体が描かれる必要のあるイメージに対応し、そのフレームブロック230Aはこの図面に示されている下部のような他の場所に配置されることである。マーカー232は、最後のフレームであるイメージフレームブロック（230Nとして示されている）と最初のオーディオフレームブロック（230A1として示されている）との間に配置されることもまた認識される。これは以下さらに詳細に説明するように、イメージおよびオーディオ情報を含むこれらのフレームブロックを識別する容易な方式を可能にし、その結果、それらは以下に説明される異なったスレッドを使用して操作されることができる。マーカーとは、そうでなければデータ中には現れないビットの固有の組合せである。
【００３４】
典型的に、時間的に関連付けられたデータを含むフレームに関して好ましいことに、各フレームは同じデータ量を記憶する能力を有する。もっとも、これは必要なことではない。また、時間的に関連付けられたフレームでは、シーケンスの少なくとも最初のフレームはキーフレームと呼ばれるものになり、ハイムーブメント（ｈｉｇｈ  ｍｏｖｅｍｅｎｔ）ビデオの場合は、シーケンス内の別のフレームもまた、以下に説明するように、キーフレームになることができる
図２Ｃ１および２Ｃ２は、データがフレームブロック230中に位置される方式を示している。したがって、フレーム全体に対するデータは、典型的にそれぞれが同じデータ量を保持することのできるフレームブロック中に配置されるように分割される。
【００３５】
図２Ｃ１は、時間的に関連付けられていないデータを含むフレームブロックを示している。示されているように、この特定の例においては、データは１６ビットワードから形成され、種々のワードは位置されてフレームブロック230の左上隅からスタートし、完成するまで挿入され、図２Ｃ１中の各ドットは、記憶が利用可能である単一のビットポジションを表している。この図には、データを含まないフレームの終りにおけるビットポジションに対するものが、下線をつけられたビットポジションとして示されており、本発明は任意の他の空のビットポジションだけでなくこれらのポジションにもビットレベル０値を埋込むことが好ましい。
【００３６】
図２Ｃ２は、別のフレームと時間的に関連したフレームの一部であってもよいし、そうでなくてもよいイメージデータを含むデータを含むフレームブロックを示している。示されているように、この特定の例において、データは２４ビットのＲＧＢデータであり、したがって画素当り２４ビットである。もちろん、このデータフォーマットは単なる例示のために与えられたものであり、別のデータフォーマットおよびイメージデータで他のタイプが適用可能である。各ビットポジションを表すデータは、フレームブロック内の、レンダー（ｒｅｎｄｅｒ）された部分の画素ポジションに対応したポジションに配置されることが好ましい。もっとも、当然ながら、別の方式が考え出されることができる。図２Ｃ２における各ドットは、再び、記憶が利用可能である単一ビットポジションを表している。
【００３７】
上述したように、オーディオデータを含むデータを含むフレームブロックについて、このデータはＲＧＢデータのようなカラースペースに変換されることが好ましく、したがって図２Ｃ２に示されているイメージデータと同様にして表わされることができる。当然ながら、別のデータフォーマットが使用可能である。各ビットポジションを表すデータは、フレームブロック内の、同じオーディオストリームの別の部分を表す別のデータに時間的に対応したポジションに配置されることが好ましい。もっとも、当然ながら、別の方式が考え出されることができる。
【００３８】
操作されるデータが最初にフレーム内に位置される方式を説明してきたが、今度は、フレームの間に存在するパターンの認識を可能にする本発明の特徴を説明する。とくに、本発明によるパターン認識システムの動作を詳細に説明する前に、特許権を受ける上で個々におよび共同して重要であるサーチングおよびパターン認識ストラテジのある特徴を以下に説明する。これまで述べてきたように、本発明はビットレベルでデータに対して動作する。基準フレーム中のデータのサーチブロックはそれぞれ、上述したようにおよび以下に説明するように、ターゲットフレームの種々のブロックと比較される。整合はマルチビット、バイトおよびマルチバイトレベルでも決定されることができるが、ビットレベルで決定されることが好ましい。整合の決定は、以下に説明するように、垂直、水平、対角線、および回転サーチ技術の組合せを使用し、好ましくは並列に動作すると共に異なったスレッドを使用して、基準フレーム内のビットの代表的なサーチブロックをターゲットフレーム内の種々のポジションと比較するパターン整合動作に基づいている。
【００３９】
説明上、データの元のフレームはオリジナルフレームまたはＯフレームと呼ばれ、フレームが減少されたことを表す必要のあるデータの全体的なサイズが、発見されたパターンのためにさいフレームは減少された、またはＲフレームと呼ばれる。したがって、ここに示されているパターン整合動作が行われた後、ターゲットＯフレームは減少された、またはＲフレームになる。これは、ほとんどの例においてそのフレーム内のデータの表現がその元の形式から減少されるためである。減少されない場合、それはオリジナルのＯフレームであり続け、データは、そのフレームがパターン整合動作の任意のものが行われる前に存在していたデータと同じであることを記述する。減少されないこのような元のＯフレームはここではキーフレームと呼ばれる。したがって、本発明の好ましい実施形態によると、最初のＯフレームは基準フレームとして使用され、この基準フレームからサーチブロックが選ばれ、隣接したターゲットＯフレームと比較される。最初のＯフレームはその元のデータをその元の形式で保持しており、ターゲットＯフレームはおそらく減少されたデータセットまたはＲフレームで記述することができるであろう。
【００４０】
動作において、好ましい実施形態では、以下に説明するように、ひとたび最初の基準ＯフレームがターゲットＯフレームとのそのパターン整合動作を終了すると、ターゲットＯフレームはＲフレームとして表されるが、ターゲットＯフレームは元のＯフレームデータと共に、サーチブロックを獲得するために新しい基準Ｏフレームとして使用され、このサーチブロックはその後選ばれて、次のまたは隣接したＯフレームと比較され、このＯフレームがその後新しいターゲットＯフレームになる。このようにして隣接したフレーム内に存在するパターンを検出することによって、また、移動を有するフレームの場合にはフレーム内に存在するパターンの移動方向を検出することにより、パターン認識が結果的に得られ、それによって、これらのパターンを反映したリンクされたリストが生成されることができる。しかしながら、好ましい実施形態では、新しい基準Ｏフレームおよび新しいターゲットＯフレームは互いにウインドウし、その結果両者が移動するが、最初のＯフレームが基準Ｏフレームであり続けるようにし、後続する複数のＯフレームのそれぞれが、同じ基準Ｏフレームが個々に比較する連続したターゲットＯフレームである等の、別の実施形態もまた存在することが可能であることが認識される。
【００４１】
図３は、データの代表的なＯフレーム内の４つの代表的なフレームブロック230と、そこにおいて規定された代表的なサーチブロック310とをさらに詳細に示している。上述したように、どのタイプのものであっても、それぞれデータのマトリックスアレイを含むフレーム220中にフォーマット化されることが好ましい。そのデータは時間的に、またはその他の方法で関連付けられていない可能性があり、したがって任意のサイズのデータのフレームブロック中にフォーマット化されるが、同じデータ量を記憶する能力を有するフレームブロック230は高速処理をさらに容易なものにするのに役に立つ。しかしながら、以下の本発明の説明においては、本発明のある重要な利点が説明され、それによって理解されることができるように、時間的に関連付けられたデータのフレームを含むビデオと、各フレーム内の種々のデータタイプとに関する特定の例が示されている。したがって、ビデオは、フレームのシーケンスを有するビデオストリームを含んでいる。イメージに対応したイメージデータおよびオーディオデータは、上述したように、適当なシーケンスで同期して一緒に保持されなければならないので、単一のフレームは両タイプのデータを記憶することができる。このような場合、各Ｏフレームは最初に、ビジュアルイメージを再生するために必要とされるビット数と対応したオーディオを再生するために必要とされるビット数とを組合せたものに対応したサイズを有する。
【００４２】
図３はまた、サーチブロック310のサイズがフレームブロック230より小さいことを一般的に示している。サーチブロック310のサイズはＯフレームのサイズおよび操作されている所定のフレームの特定の部分に応じて変化することができるが、種々のフレームサイズに対して有益であると判断されて決定されたサーチブロックの好ましいサイズは、以下の表Ｉに示されている。
【００４３】
表  Ｉ
フレームタイプ                          サーチブロック  
３２０×２４０バイトビデオフレーム        ３２×３２バイトサーチブロック
７２０×４８０バイトビデオフレーム        ６４×６４バイトサーチブロック
１４４０×９６０バイトビデオフレーム    １２８×１２８バイトサーチブロック
オーディオブロック                        ８×８バイトサーチブロック
【００４４】
以下さらに詳細に説明するように、図２Ｂ１に示されているような210A乃至210Dのようなシーケンス内には、パターンがフレーム220内に存在するか否かを決定するために操作される必要のあるフレーム220が存在する。これを行うために、サーチブロックが使用される。サーチブロックのサイズは、それがひとたび決定されると、典型的に同じタイプのデータを含むフレームブロック230に対して同じままである。したがって、イメージデータおよびオーディオデータの両者を有するフレームブロックを含むフレームをサーチするために同じサーチブロックが使用されることができるが、イメージデータを含むフレームブロックをサーチするときは、決定されたサーチブロックサイズを使用し、イメージデータを含むフレームブロックをサーチするときには、別の決定されたサーチブロックサイズを使用することに利点があることが分かっている。そのシーケンスに関して直前および直後のフレームは、上述したように、時間および内容的に関連付けられてもよいが、しかしながら、本発明によるパターン認識のために、関連していないと決定されてもよい。たとえば、フレームのシーケンスの後のある後続フレームは、新しいキーフレームであると決定されてもよい。これは、それがここに記載されているパターン認識のために減少されないためである。このような新しいキーフレームは、以下において明らかになるように、Ｒフレームであると決定された前のフレームのシーケンスとは異なったサイズのサーチブロックを有していることができる。もっとも、時間的に関連付けられたフレーム内のデータに関しては、これは典型的に該当しない。
【００４５】
図３はまた、垂直方向に対応した矢印320と、水平方向に対応した矢印330とを示している。これは、所定の基準Ｏフレーム全体がサーチブロックとして使用される各部分内にデータを有するように、この基準Ｏフレーム内においてサーチブロックウインドウがフレームブロック330を横切って移動されることを示すものである。以下に説明するように、多数のスレッドを使用して動作する能力を有する最近のプロセッサは、異なったスレッドが、以下説明するように異なったサーチブロックを、または異なった方向に同時に処理していることが可能であるように構成されていることが好ましい。異なったサーチブロックが選択される方式に関して、サーチブロックは、サーチブロックの重複したウインドウが存在するように単一のビットポジションだけ移動されることが好ましい。もっとも、選択されたサーチブロックの重複が少なくなり、あるいは存在しないバイトおよびマルチバイト移動だけでなく、２，４，８または最も大きいビット数の移動もまた使用可能である。したがって、単一ビットポジション移動は同じ水平レベルに沿った全てのブロックがサーチされることを保証し、その後サーチブロックウインドウが独立的に垂直下方に移動されることができ、このようにして別のサーチセットがその新しい水平レベルに沿って行われる。当然ながら、サーチブロックが選ばれる順序を選択する別の方式が使用可能である。
【００４６】
図４に示されているように、基準Ｏフレーム220Rからの特定のサーチブロック310がターゲットＯフレーム220Tに適用されたとき、このサーチブロック310は最初に、基準Ｒフレーム220R内の同じポジションにおいてフレームブロック230R内の同じポジションに対応したターゲットＯフレーム220Tのフレームブロック230T内のサーチブロックエリア410において適用される。この最初のポジションにおいて、２進ビット比較は、以下さらに詳細に説明するように、無損失圧縮に対するアンド演算および損失動作のためにここにさらに詳細に説明されている別の演算を使用して、サーチブロック310内のその時間におけるデータと、ターゲットＯフレーム230Tのサーチブロックエリア410内の対応したデータとの間において、ビットレベルで行われる。その最初の比較が終了すると、サーチブロック310はその後、フレーム220R内において、ここに示されているように垂直420、水平430、対角線440、および回転方向を含む種々の別の移動方向に移動され、移動方向に沿ったこのような各ポジションにおいて、サーチウインドウ内でのデータのビットレベルでの別の比較が行われる。
【００４７】
図４はまた、ターゲットフレーム内におけるサーチブロック410の好ましい垂直移動および水平移動方向ならびに１つの好ましい対角線移動方向とを示している。示されているように、ターゲットフレームのサーチエリア410からスタートすると、サーチブロック310は垂直または水平の各移動方向に対して下方または横断方向に移動し、対応した垂直および水平移動方向のそれぞれに対して列または行において一時に１ビット移動することが好ましく、示されている４５°の対角線については、それは１ビット横断方向におよび１ビット下方に移動することが好ましく、これは（１，１）対角線移動と呼ばれることができる。種々の別の角度に対応した対角線移動は、たとえば、（１，２）、（１，３）、（１，４）・・・（１，ｎ）移動および（２，１）、（３，１）、（４，１）・・・（ｎ，１）移動を使用して達成されることができる。折返し矢印によってもまた示されているように、垂直、水平および対角線方向内の種々の画素ポジションは全てサーチされることが可能である。もっとも、以下さらに詳細に説明されるように、このようなサーチは全て必要なく、したがって行われない可能性がある。
【００４８】
サーチウインドウ310がマスターブロックのあるエッジにあるサーチエリア410に適用されたとき、隣接したマスターブロック画素データがあるフレームのエッジで一度使用され、ラップアラウンドの結果として別のサーチが行われる。
【００４９】
エッジにおいて、サーチブロックウインドウの移動が単一ビットである場合、フレーム220Tのエッジにおいてサーチウインドウはフレーム220Tの反対側に進み、別の比較を開始する。しかしながら、サーチブロックウインドウがフレーム220Tのエッジにおいて多数のビットをジャンプした場合には、データはサーチエリア410を充填するのに利用できなくなる。このような場合、サーチエリア410内のデータはゼロを埋込まれるため、サーチブロックウインドウ310のサイズおよびサーチブロックエリア410のサイズは変更が必要ない。
【００５０】
図５は、ターゲットＯフレームフレームブロック230T内において最初のサーチエリア410に適用された基準Ｏフレーム220Rの基準Ｏフレームフレームブロック230Rの例示的な最初のサーチブロック310を示している。この特定のサーチブロック310は２４×２４ビットのブロックとして示されており、このウインドウのサイズは理解ためにのみ使用されている。サーチウインドウ310は３つの連続した水平方向のサーチエリア410、412および414として示されており、ターゲットＯフレーム220上のサーチウインドウ位置を識別するために使用されることのできる左上のビットポジションはそれぞれポジション（３６，２４）、（３７，２４）および（３８，２４）である。類似したこのようなサーチエリアは、（３６，２４）ポジションから（３６，２５）ポジションへのような水平方向移動に対して、および（３６，２４）ポジションから（３７，２５）ポジションへの１−１移動のような対角線方向移動に対して得られる。
【００５１】
図６のＡ乃至Ｄは、図６のＡに示されているパターンに対する、図６のＢ乃至Ｄのそれぞれに示されている９０°、１８０°および２７０°の各ポジションでの例示的な回転パターンサーチングを示している。これらの原理に基づいた回転パターンサーチングは、この明細書において説明されているシフト動作を使用して得られた異なったポジションでの回転によりそのパターン中の回転シフトが検出されるように実施されることができる。
【００５２】
図７Ａ乃至７Ｄは、本発明によるパターン認識を達成するときに使用されるデータおよびヘッダと、結果的に得られたデータフォーマットとを示しており、この結果的に得られたデータフォーマットはその後さらに圧縮されることができる。このデータおよびヘッダは、パターン整合を獲得するために本発明がどのようにして実施されるかを説明するときに、図８Ａ乃至８Ｃのフローチャートと共に使用される。
【００５３】
図８Ａ乃至８Ｃは本発明の好ましい実施形態のフローチャートを示している。ステップ１０に示されているように、初期条件が設定される。これらの初期条件には、全体的な圧縮ターゲット比率、予め定められたカウント値、デフォルトサーチブロックサイズ、損失圧縮が関与する場合の損失割合、デフォルトパターン方向、垂直および水平の両サーチブロックトラバーサルオフセット、および垂直および水平ターゲットサーチエリアオフセットが含まれる。以下において、これらをそれぞれ若干詳しく説明する。
【００５４】
全体的な圧縮ターゲット比率は、ターゲットフレームの所望の全体的な圧縮である。この全体的な圧縮には本発明によるパターン認識によって得られた圧縮が含まれるが、発生するように意図された本発明の技術的範囲外のものである別の圧縮動作もまた含まれる。以下に説明するようにある状況において、非常に多数のパターンが認識された場合、ここに記載されているパターン認識は中止され、その代りに、上述された別の圧縮動作が全ての圧縮に対して使用される。たとえば、映画内のフレームのシーケンスにおいて、２つの隣接したフレームが完全に黒のイメージを（たとえば、導入部クレジットへのプリカーサとして）含んでいる場合、これら２つのイメージは事実上同じなので、全体的な圧縮ターゲット比率は超過されるであろう。
【００５５】
予め定められたカウント値は、サーチブロックを特定の方向にシフトしているスレッド、および整合を見出していないスレッドを終了させるために本発明によって使用される。とくに、基準ブロックのある最小のサーチエリアが、たとえば２０％サーチされた後、おそらく、基準フレームのその２０％のエリア内のサーチブロックの間のいくつかの整合により、ターゲットフレーム内のある数の整合は発見されているであろう。このようにして、予め定められたカウント値はこのカウントを設定するために使用されることができる。このカウントはゼロに設定されることができるが、それはまたある高い整数に設定されることができる。
【００５６】
デフォルトサーチブロックサイズ値は、デフォルトサーチブロックサイズに対してある値を提供する。特定のフレーム内において、２以上のサーチブロックサイズが使用された場合、たとえば、ビデオ情報を含むフレームブロックに対して１つのサーチブロックサイズが使用され、オーディオ情報を含むフレームブロックに対して別のサーチブロックサイズが使用された場合、適合されたサーチブロックサイズの数が規定される。
【００５７】
上述したように、本発明は無損失モードおよび損失モードの両方での動作であることができる。損失モードで動作しているとき、本発明は、損失割合の設定がここに記載されているパター認識動作内で許容されることのできる損失の量を決定することを可能にする。したがって、この損失割合は、初期条件として設定されることができるため、サーチブロックがターゲットフレームのサーチブロックエリアに関してその比較を行っているとき、同じものであるサーチブロックエリア内のビットの数がその損失割合に達した場合に整合が識別される。
【００５８】
デフォルトパターン方向初期条件は、デフォルトパターン方向以外のパターン方向が第１のスレッドに対して使用されることを決定する予測子スレッドの無いターゲットフレームをトラバースするために使用される方向に設定される。
【００５９】
サーチブロックトラバーサルオフセットはまた初期条件として設定される。オフセットの組合せは、異なったタイプのスレッドのそれぞれに対して存在していることが好ましい。たとえば、異なった組合せのサーチブロックトラバーサルオフセットは、異なった水平、垂直、対角線、および回転の各サーチのために使用されることができる。また、異なったサーチブロックトラバーサルオフセットは、あるフレームブロック内のビデオ情報および別のフレームブロック内のオーディオ情報のような異なったフレームブロック内の異なったタイプの情報をサーチしているときに使用されることができる。水平および垂直の両成分に関して設定されているオフセットは、前に使用されたサーチブロックがターゲットフレームのその比較を終了した後に新しいサーチブロックを獲得するために使用される基準フレーム内におけるシフト進行を決定する。種々の進行が使用されることができ、この進行は、ターゲットフレームとの見出される整合の可能性が増加するように、基準フレーム内の種々の可能なポジションのそれぞれに対応した最大数の異なったサーチブロックを含んでいることが好ましい。したがって、サーチブロックトラバーサルオフセットは、前のサーチブロックがターゲットフレームとの比較動作を行った後の基準フレーム内の次のサーチブロックの基準フレームおよびしたがって内容内におけるその位置を決定する。サーチブロックトラバーサルオフセットに基づいたサーチブロックの移動は、上述したように、ビット、マルチビット、バイト、またはマルチバイトであることができる。
【００６０】
ターゲットサーチエリアオフセットは、サーチブロックトラバーサルオフセットに類似した方式で設定される必要のあるオフセットである。このターゲットサーチエリアオフセットは、ターゲットフレームにおけるある特定のサーチブロックエリアとサーチブロックとの比較動作を行った後で特定のサーチブロックがターゲットフレーム内において移動される量を決定する。したがって、たとえば、水平方向に動作しているスレッドを使用して最初の比較動作が行われた後、その水平オフセットは、次の比較動作が行われることができるように、サーチブロックがターゲットフレーム内においてシフトされる量を決定する。その同じサーチブロックは、所定の行における全ての比較動作が行われるようにターゲットフレーム内においてシフトされた後、列オフセットによって決定されたように列方向にシフトされる。その後、上述したように、ターゲットフレーム内のサーチブロックの後続的な移動が水平オフセットに基づいて発生する。ターゲットサーチエリアオフセットに基づくサーチブロックのシフトは、上述したように、ビット、マルチビット、バイト、またはマルチバイトであることができる。
【００６１】
これらの初期条件を設定した後、動作は以下に説明するステップ１２に続く。  
ステップ１２において、これが前に行われている場合、元のフレームはフレームブロックにフォーマット化され、第１のフレームは基準フレームに指定され、次のフレームはターゲットフレームとして指定される。
【００６２】
ステップ１４において、元のフレームを解析する予測子スレッドが起動される。このような元のフレームは、上述したように本発明により使用されたときに、フレームデータに加えてヘッダ情報が処理中に追加され、この明細書の説明から明らかになるように、このヘッダ情報のあるものは保持されて最終的に符号化され、一方他のヘッダ情報は一時的に使用され、その後廃棄される。図７Ａに示されているように、各フレームと関連付けられたフレームデータに加えて、基準フレーム番号またはフレームＩＤは、別のフレーム内におけるそのポインタがこのフレームを参照することができるように記憶される。次のフレームが配置されるメモリ中の場所へのポインタ（すなわち、次のフレームのフレームＩＤ）およびフレームサイズが追加され、各フレームに対するフレームデータと関連付けられる。フレームデータは、上述したように、マトリックスアレイにフォーマット化されることが好ましい。とくに、予測子スレッドは最初の基準フレームと後続するターゲットフレームとの間で、これらのフレームのいくつかの限られたエリアに対して、たとえば、２０等のある数の比較を行う。とくに、比較は、基準フレームの異なった部分に基づいて行われ、異なったサイズのサーチブロックを使用して動作する。サーチブロックのサイズは大幅に変化することができ、異なったサイズの範囲は、フレームのサイズに応じて、８×８バイトから１２８×１２８バイトまたはそれ以上の潜在的に可能な範囲に及ぶ。一般に、フレームが大きくなると、使用されるサーチブロックサイズがそれだけ一層大きくなる。その結果、予測子スレッドは、最初のサーチブロックの好ましい移動方向、使用されるべき予測されるサーチブロックサイズ、および行われた比較において整合が発生したか否かを示す整合割合を決定することができる。
【００６３】
したがって、ステップ１６において、予測子スレッドは少なくとも最初のターゲットフレームを解析しているので、最初の基準フレームと後続するターゲットフレームとの間の比較に関するスレッドが発生することができる。予測子スレッドは別の後続フレームに関して続行している期間中に、サーチ比較動作が最初の基準フレームと後続するターゲットフレームとの間で行われる。予測子スレッドは、以下に説明するように、その後追加される別のスレッドと並列にランしながら続行することが認識される。
【００６４】
上記に示されているように、予測子スレッドは予測された移動方向および予測されたサーチブロックサイズを獲得する。これらは、基準フレームとターゲットフレームとの間の比較のために設定された第１のスレッドに対する設定を開始するために使用される。さらに、予測子スレッドはまた、獲得されたサーチサンプルに基づいて整合割合を獲得する。したがって、たとえば、基準フレームからの２０個の異なったサンプルが、好ましくは基準フレームの特定のエリアに対応した位置およびこれらのエリア（またはターゲットフレーム全体）の周囲のある境界で、ターゲットフレームに整合した場合、いくつかの予測整合が決定されることができる。典型的に、予測整合の数が少ない場合、２つのフレーム間の整合の対応した数はそれほど多くない可能性がある。対照的に、その割合が高く、たとえば、２０個のサンプルのうちの１４個が整合している等の場合には、フレームの間に多くの異なった整合エリアが存在している可能性がはるかに高くなる。これに関して、２つのフレームにおいて解析されているデータがビデオ情報のシーケンスであるとき、少ない数の予測整合はハイモーションシーケンスを示唆し、また、多くの数の予測整合はローモーションシーケンスを示唆する。予測整合の数または割合は、以下に説明するように、特定の移動方向に設定すべきスレッドの数を決定するために使用されることができる。
【００６５】
ステップ１６が終了したとき、予測子スレッドがターゲットフレームに対して予測された移動方向および予測されたサーチブロックサイズに関する情報を提供したか否かが決定される。イエスならば、予測されたサーチブロックサイズおよび予測された移動方向は、設定されている最初のスレッドによって使用されるように渡される。否である場合には、設定されている最初のスレッドはデフォルトサーチブロックサイズおよびデフォルト予測移動方向を使用する。ステップ２０が後続し、第１のスレッドが設定され、そのスレッドに対するサーチブロックサイズ、垂直および水平サーチブロックトラバーサルおよびターゲットサーチエリアオフセット、ならびに予測された移動方向もまた設定される。
【００６６】
ステップ２４はこの第１のスレッドを開始し、ステップ２６が後続する。  
ステップ２６に示されているように、サーチブロックカウンタは起動される。このサーチブロックカウンタは、比較されたサーチブロックとターゲットフレーム内の対応したサーチブロックエリアとの間の整合インスタンスの数を検出するために使用される。サーチブロックと対応したサーチブロックエリアとの間で行われた比較の数は知られているため、行われた比較の数に対するサーチブロックカウンタからのカウントの比は、獲得された整合の割合を示した。
【００６７】
ステップ２６においてサーチブロックカウンタを初期化した後、ステップ２８が後続し、サーチブロックが基準フレームの初期ポジションから得られる。その後、ステップ３２が続く。上述したように、無損失比較に対してアンド演算を使用して、また、損失比較が行われている場合には、整合を決定するためにアンド、オア、乗算、除算およびその他の演算を使用して、整合が存在するかどうかを決定するために初期サーチポジションから得られたサーチブロックがターゲットフレーム内の最初のサーチエリアと比較される。
【００６８】
行われている比較のタイプおよび整合が見出されたか否かに応じて、ステップ３４Ａ、３４Ｂまたは３４Ｃが後続する。ステップ３４Ａにおいて、サーチブロックが整合して同じであり、全てのビットがターゲットフレームの対応したサーチブロックエリア内で見出されたサーチブロックであることを示した場合、サーチブロックカウンタはインクリメントされ、同じ整合が発生したことを示し、ターゲットフレームのサーチブロックエリアにおいてサーチブロックと基準フレームとの間の関係を示すリンクが生成される。しかしながら、損失比較動作が許されるならば、サーチブロックが損失範囲内で整合した場合、ステップ３４Ｂによって示されるように、サーチブロックカウンタはまたインクリメントされ、ターゲットフレームのサーチブロックエリアにおいてサーチブロックと基準フレームとの間の関係を示すリンクが生成される。しかしながら、ステップ３４Ｃにおいて、サーチブロックが損失範囲内で整合しなかった場合、その特定のサーチブロックに対するターゲットフレーム内のサーチブロックエリアはパターン無しとマークされる。したがって、基準フレームのサーチブロックとターゲットフレームのサーチブロックエリアとの間の不十分な関係が認められたために、これは、あたかも整合が存在しなかったかのように扱われ、そのサーチブロックとターゲットフレーム内の別のサーチブロックエリアとの間で比較プロセスが続行することとなる。
【００６９】
その目的を達成するために、サーチブロックがターゲットフレームをトラバースすることができるようにステップ３６が後続し、サーチブロックがこのターゲットフレーム内の次のサーチポジションにシフトされる。これは、上述されたターゲットサーチエリアオフセットを使用して行われる。したがって、たとえば、最初のスレッドが水平方向にサーチするように設定され、水平方向内の行の最後に到達しなかった場合、サーチブロックをターゲットフレーム内の次の隣接したポジションに移動するために水平ターゲットサーチエリアオフセットが使用される。
【００７０】
その後、ステップ３８が続き、このステップは、見出された整合のタイプおよび許される整合動作のタイプに応じて再び使用される。サーチブロックが整合して同じである場合、ステップ３８Ａはサーチブロックカウンタをインクリメントし、ターゲットフレームのサーチブロックエリアにおいてサーチブロックと基準フレームとの間の関係を示すリンクを生成する。しかしながら、サーチブロックが損失範囲内で整合し、損失が許される場合、この比較の結果は、ステップ３８Ｂ１または３８Ｂ２のいずれかにより説明されるように、前のサーチポジションから得られた結果と比較される。ステップ３８Ｂ１において、現在の損失範囲内の結果が前のサーチブロックエリアから得られた前の損失範囲からの結果以下である場合、この特定のサーチブロックエリアはパターンを有しないものとして記録される。しかしながら、現在の損失範囲内の結果が前の損失範囲からの結果より大きい場合には、ステップ３８Ｂ２において、リンクが生成され、前のリンクは破壊される。その後、ステップ３８Ａ、ステップ３８Ｂ１または３８Ｂ２のいずれが使用されたかにかかわらず、ステップ４０が後続する。
【００７１】
ステップ４０において、とくに終了されない限り、ターゲットフレーム全体がサーチされるまで、シフトおよびサーチステップが繰返される。ターゲットフレーム全体がサーチされたとき、新しいサーチブロックは、サーチブロックトラバーサルオフセットを使用してサーチブロックをシフトすることによって獲得され、このシフトは、そのスレッドが終了するまで繰返される。サーチブロック位置を維持するために、基準フレーム内のサーチブロックの初期ポジションの位置決めを行う開始ポジションオフセットが使用されることもまた認識される。さらに、サーチ動作の終りに、特定のサーチブロックを使用して、次のサーチブロックが獲得され、その同じスレッドを使用して操作される。以下説明するように、別のスレッドが生成された結果、基準フレーム内のサーチブロックポジションの移動に対する終了ポジションが獲得され、したがってスレッドの終了が行われる。
【００７２】
シフトおよびサーチ動作が行われている期間中、多数の整合が発生した場合、とくに、オフセットが単一ビットの列または単一ビットの行である場合に、フレームブロック内のサーチを続行する必要のないことが認められている。したがって、ステップ４２に示されているように、所定のフレームブロック内で発生する同じ整合の数がユーザにより予め設定されている場合、サーチブロックの次のシフトは、オフセットによって決定されるのではなく、ターゲットフレーム内の次のフレームブロックの初期ポジションに移動されるものとなる。ターゲットフレーム内の次のフレームブロック内においてさらにサーチが行われる代りに、その特定のフレームブロックのその初期ポジションで整合が生じた場合、ターゲットフレーム内の後続する次のフレームブロックへの移動が繰返されることができる。各フレームブロックの第１のポジションのそれぞれにおいて整合が発生した場合、これは、これらの隣接したフレームブロックの初期ポジションの間の対応したビットポジションの全てもまた、高い確実性で整合することを示す。
【００７３】
以下に説明するステップ４４乃至５０は、シフトおよびサーチ動作が行われている最中に行われる。なお、これらのステップはこの明細書において説明を容易にするために示されたものであり、それらまたはここに記載されている他のステップはこの記載のオーダーポジションで行われる必要のないことが認識されるであろう。
【００７４】
記載されているように、ステップ４４において、ターゲットフレーム中におけるターゲットサーチエリアのシフトがターゲットフレームのエッジにおけるものであり、また、単一ビットポジションより大きい（単一ビットの行または単一ビットの列だけのシフトの場合、重複は生じないため）場合、ターゲットフレームのターゲットサーチエリアは、そのターゲットサーチエリアがターゲットフレームによって充填されない位置に対応した位置に空ビットポジションを有することになる。したがって、このように状況では、サーチブロックはまた、それが同じサイズの対応したターゲットサーチエリアと比較されるようにゼロを埋込まれる。
【００７５】
ステップ４６、４８および５０は、設定されている特定のスレッドを終了するために使用されることのできる３つの異なったタイプのステップを記述している。以下に説明するように、異なったサーチと共に多数のスレッドが並列に動作している。無効である（整合が見出されていない）スレッドのあるものを終了するために、ステップは無効なスレッドを終了するために使用される。ステップ４６により記述されているように、基準フレームの２０％のサーチのような、基準フレームの最小のサーチエリアがサーチされた後、別の方向スレッドがこのスレッドの方向に対応したスレッド以上のイールド（ｙｉｅｌｄｓ）を発生している場合、この特定のスレッドおよび同じ対応した方向移動を有する別のスレッドは終了される。
【００７６】
幾分類似した操作では、ステップ４８において、最小のサーチエリアがカバーされた後、同じ方向にサーチする全てのスレッドが、ゼロまたは上述したように初期条件において設定されたゼロより高いある数であることができるある予め定められたカウント値より低い値を生成した場合、この特定のサーチ方向を有する全てのスレッドが終了される。
【００７７】
最後に、初期条件に関して上述した全体的な圧縮ターゲット比率が満足された場合、現在のスレッドを含む全てのスレッドは終了される。ステップ５０に関して、結果的にステップ５０が行われた場合、ターゲットフレームはその元の状態で保存され、ステップ６２が以下に説明するように後続する。上述したように、本発明によるパターン整合が必要とされず、また、本発明の技術的範囲外である後続する圧縮ルーチンが使用されることができるため、ターゲットフレームはその元の状態で保存される。
【００７８】
上記のステップ４０によって述べられたように、スレッドが終了すると、ステップ５２が後続し、そのスレッドからのデータが、好ましくは整合した比較されたブロックを含むリンクされたリストとしてファイルに書込まれる。これは、減少されたフレームヘッダおよびリンクリストブロックデータを示している図７Ｂおよび７Ｄにより示されている。減少されたフレームに対するデータの識別された各部分はこれらの記載された動作に関する目的にかない、上述したように、ここに記載されている動作の期間中に更新され、使用される情報を含んでいる。フレームＩＤは、タイプＯフレームに対する基準フレーム番号と同じである。次の基準またはキーフレームに対するポインタおよび減少されたＲフレームに対するポインタは、潜在的に後続するフレームに関する動作の結果、それらの位置が決定されたときに追加されることができる。フレーム内の減少されたフレームブロックの数は、動作状態を追跡するために使用されることができる。その後、図７Ｂおよび７Ｃに示されているデータのブロックはフレーム内の各フレームブロックに対して反復し、これらのブロックは、
・次のＲフレームブロックに対するポインタと、
・Ｒフレームに対するＩＤまたは基準番号と、
・損失または無損失整合のいずれが行われたのかを示し、損失整合ならば、システムがここに記載されているステップをさらに迅速に処理することを可能にするのを支援するために使用された場合に有益なものとなることのできる損失割合を示す整合タイプと、
・フレームブロックサイズと、
・ターゲットフレームの整合されたブロック座標とを含んでおり、このターゲットフレームの整合されたブロック座標は、その内容が図７Ｃにさらに詳細に示されており、また整合が見出されたターゲットサーチエリアの位置だけでなく、サーチブロックのサイズおよび位置の両方もまた示している。示されているように、これらの座標は、第１、第２、および第ｎの位置決定されたターゲットサーチエリアポジションを有するリンクされたリストであり、そのサーチブロックに対して整合が生じた（損失または無損失にかかわらず）ターゲットフレーム内の場所を示している。その後、これは各サーチブロックに対して繰返される。
【００７９】
その後、ステップ４６、４８および５０が生成されているスレッドを終了したことを記述すると、ステップ５４はスレッド生成のプロセスを記述する。とくに、上述されているように第１のスレッドを設定した直後、次のブロックサーチオフセットおよび方向もまた予測スレッドから上述したように決定され、新しいスレッドが設定される。この新しいスレッドの設定に関して、いくつかの考慮事項が使用される。これらには、好ましい順序ではないが、以下が含まれる：
・一般に、別のスレッドを異なった方向に設定する前に、新しいスレッドが前に設定されたスレッドから間隔を隔ててこれと同じ方向に設定される；
・新しいスレッドは典型的なデータについては１００キロバイトのデータごとに設定される。もっとも、ハイモーションビデオに対しては、５０キロバイトのデータごとに新しいスレッドが設定されることが好ましい（ローモーションビデオとハイモーションビデオとの相違が上述の予測スレッドから得られる）；
・予測スレッドに基づいてサーチされた初期方向に対応したスレッドを設定した後、スレッドをサーチする典型的なデフォルト順序は水平、垂直、対角線、およびその後回転である；
・設定されるスレッドの数は本質的にプロセッサ制限されるので、設定されるスレッドの数は使用されるプロセッサの制約により制限される。したがって、ステップ５６によって示されているように、追加の各スレッドに対して、ステップ２２乃至５２が繰返される。
【００８０】
ステップ５８によって示されているように、前に並列にランしていたいくつかのスレッドに関して、全てのスレッドが終了された場合、ステップ６０が後続する。その他の場合には、異なったシフト、サーチならびにスレッド生成および終了動作、および関連したステップが上述のように続く。
【００８１】
ステップ６０において、基準フレームのサーチブロックとターゲットフレームのサーチブロックエリアとの間の整合として見出された比較されたブロックの結果として得られたリンクされたリストは、その後、整合されたデータを表すスーパーセットブロックを獲得するために更新される。とくに、図７Ｃに示されている第１、第２、および第ｎの位置決定されたターゲットフレームサーチエリアポジションはスーパーセットブロックを獲得するために崩壊させられる。したがって、いくつかの異なった比較的小さいサイズの整合したブロックが前に存在していたかもしれないが、これらの小さいブロックの間に重複が存在している限り、大きいスーパーセットブロック（必ずしもブロックの形状を有している必要はない）が見出されることができる。
【００８２】
ステップ６２において、スーパーセットブロックを獲得した後、データは再び、好ましくは、基準フレームとターゲットフレームとの間の整合を示すリンクリストの形態で更新され、更新されたデータはこの形態でファイルに保存される。その後、ステップ６４において、ターゲットフレームは基準フレームとして設定され、ステップ６６において、別のフレームが存在する場合、その別のフレームは、ステップ２０乃至６６が繰返されることができるように、新しいターゲットフレームとして設定される。その後、ステップ６８によって示されているように、別のフレームが存在しない場合、プロセスは終了する。したがって、図７Ｄに示されているように、元のフレームおよび減少されたフレームを含むデータのストリームが結果的に得られる。
【００８３】
上記に関して、多くの変形が可能であることが認識される。たとえば、ステップが実施される順序が変更されることができる。また、たとえば、データがプロセス中の種々のポイントで追跡される方法が変更可能であり、リストされたリンクまたは２進ツリーが使用されることが好ましいが、別のデータ記憶方式が実施されることができる。
【００８４】
図９Ａは、無損失整合した場合に同一であるターゲットブロックに整合するサーチブロックの例示的なパターンを示している。図９Ｂは、この例では９０％の、許される損失割合の範囲内の例示的なターゲットブロックを示している。
【００８５】
上記において、損失および無損失の両パターン認識技術が記載され、サーチブロックとサーチエリアとの比較がアンド演算を使用して行われた。無損失パターン認識およびアンド演算またはその論理的に等価なものに関して、これらは無損失圧縮のために必要であるが、実際には、排他的オア，オア、減算または乗算のような別の演算によりもっと良好な結果が得られる可能性がある。
【００８６】
図１に戻ると、上述した演算はコンピュータ180の任意の１つにおいて行われることができ、結果的に得られたストリームはさらに符号化される。このようなさらなる符号化は、たとえば、２０００年１１月２９日に出願され、その権利が本出願人に譲渡された米国特許出願第09/727,096号明細書（“Method And Apparatus For Encoding Information Using Multiple Passes And Decoding In A Single Pass”）に記載されている多重パス符号化、または別の符号化プロセスを使用することができる。ひとたび完全に符号化されると、図１に示されているコンピュータ140のようなあて先装置に送られ、符号化の逆である復号が使用され、その復号プロセスの最後のステップとして、リンクされたリストおよびここに記載されているようなポインタを使用することにより、本発明を使用した結果得られるＯフレームとＲフレームの組合せからＯフレームの元のセットが再生されることができる。認識されたパターンに基づいてリンクされたリストを獲得することに関するこの明細書における詳細な説明を考慮して、当業者は、この圧縮されたデータセットからの元のデータセットが、Ｏフレームとして保存されているＯフレーム内に存在する元のデータを使用してデータを拡張（ｅｘｐａｎｓｉｏｎ）することにより再生され獲得されることができることを認識するであろう。
【００８７】
上記には種々の好ましい実施形態が詳細に記載されているが、当業者は、例示的な実施形態の多くの修正が本発明の新しい教示および利点から実質的に逸脱することなく可能であることを容易に認識するであろう。
【図面の簡単な説明】
【００８８】
【図１】本発明のブロック図。
【図２Ａ】本発明によるフレームにフォーマット化された例示的なデジタルデータの概略図。
【図２Ｂ１】本発明によるフレームにフォーマット化された例示的なデジタルデータの概略図。
【図２Ｂ２】本発明によるフレームにフォーマット化された例示的なデジタルデータの概略図。
【図２Ｃ１】本発明によるフレームにフォーマット化された例示的なデジタルデータの概略図。
【図２Ｃ２】本発明によるフレームにフォーマット化された例示的なデジタルデータの概略図。
【図３】本発明にしたがって動作されたデータのフレーム内のマスターブロックおよびサーチブロックの詳細図。
【図４】最初のＯフレームマスターブロック内の例示的な最初のサーチブロック、後続するＯフレームマスターブロック内の対応した最初のサーチエリア、ならびに本発明にしたがって使用される垂直、水平および対角線パターンサーチ方向を示す概略図。
【図５】例示的なビデオデータストリームフレーム内の後続するＯフレームマスターブロックの一部と、その上で動作する例示的なサーチブロックとを示す概略図。
【図６】本発明にしたがって使用される例示的な回転パターンサーチングを示す概略図。
【図７Ａ】本発明によるパターン認識を行って、その結果、後でさらに圧縮されることのできるデータフォーマットを獲得するときに使用されるデータおよびヘッダを示す概略図。
【図７Ｂ】本発明によるパターン認識を行って、その結果、後でさらに圧縮されることのできるデータフォーマットを獲得するときに使用されるデータおよびヘッダを示す概略図。
【図７Ｃ】本発明によるパターン認識を行って、その結果、後でさらに圧縮されることのできるデータフォーマットを獲得するときに使用されるデータおよびヘッダを示す概略図。
【図７Ｄ】本発明によるパターン認識を行って、その結果、後でさらに圧縮されることのできるデータフォーマットを獲得するときに使用されるデータおよびヘッダを示す概略図。
【図８Ａ】本発明の好ましい実施形態によるパターン認識システムの全体的な動作を示すフロー図。
【図８Ｂ】本発明の好ましい実施形態によるパターン認識システムの全体的な動作を示すフロー図。
【図８Ｃ】本発明の好ましい実施形態によるパターン認識システムの全体的な動作を示すフロー図。
【図９Ａ】本発明の１実施形態による代表的なサーチブロックを示す概略図。
【図９Ｂ】本発明の１実施形態による損失ターゲットブロックを示す概略図。
【図１】
2006502598.tif 000003
【図２Ａ】
2006502598.tif 000004
【図２Ｂ１】
2006502598.tif 000005
【図２Ｂ２】
2006502598.tif 000006
【図２Ｃ１】
2006502598.tif 000007
【図２Ｃ２】
2006502598.tif 000008
【図３】
2006502598.tif 000009
【図４】
2006502598.tif 000010
【図５】
2006502598.tif 000011
【図６】
2006502598.tif 000012
【図７Ａ】
2006502598.tif 000013
【図７Ｂ】
2006502598.tif 000014
【図７Ｃ】
2006502598.tif 000015
【図７Ｄ】
2006502598.tif 000016
【図８Ａ】
2006502598.tif 000017
【図８Ｂ】
2006502598.tif 000018
【図８Ｃ】
2006502598.tif 000019
【図９Ａ】
2006502598.tif 000020
【図９Ｂ】
2006502598.tif 000021
【国際調査報告】
2006502598.tif 000022
2006502598.tif 000023
2006502598.tif 000024
2006502598.tif 000025