(57)【要約】【課題】  演算量を比較的少なくしつつ、動きベクトルを高い信頼性で検出する。【解決手段】  参照フレーム画像内に設けられた探索範囲２３２内の３つの代表点２２１ａ、２２１ｂ、２２１ｃから構成された６８個のトリプレットパターンの中から、対象ブロックと参照ブロックとの画素値の差分演算に基づいて、対象ブロックと最も相関性の高いトリプレットパターンを抽出する。次に、抽出されたトリプレットパターンに関連して定められた複数の候補ベクトルの中から、対象ブロックと最も相関性の高い候補ベクトル１０８を抽出する。最後に、抽出された候補ベクトル１０８及びその上下左右の画素を終点とする４つの候補ベクトルの中から、対象ブロックと最も相関性の高い候補ベクトル１０９を抽出する。【選択図】図４
2005244436.tif 000002
【特許請求の範囲】
【請求項１】
符号化対象フレーム画像内の画素群である対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、
前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出手段とを備えていることを特徴とする動きベクトル検出装置。
【請求項２】
符号化対象フレーム画像を記憶する対象フレーム記憶手段と、
参照フレーム画像を記憶する参照フレーム記憶手段と、
前記対象フレーム記憶手段に記憶された符号化対象フレーム画像から、画素群である対象ブロックを順次抽出する対象ブロック抽出手段と、
前記対象ブロック抽出手段によって抽出された対象ブロックごとに、前記参照フレーム記憶手段に記憶された参照フレーム画像から、互いに一又は複数画素ずつ変位した画素群である複数の参照ブロックであって、その代表点が当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に位置している複数の参照ブロックを抽出する参照ブロック抽出手段と、
前記複数の参照ブロックから選択された２以上の参照ブロックの代表点を包含しており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンを記憶するパターン記憶手段と、
前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記パターン記憶手段に記憶された前記複数のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、
前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出する第１の候補ベクトル抽出手段とを備えていることを特徴とする動きベクトル検出装置。
【請求項３】
前記第１の候補ベクトル抽出手段で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似した一又は複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出する第２の候補ベクトル抽出手段をさらに備えていることを特徴とする請求項２に記載の動きベクトル検出装置。
【請求項４】
前記パターン記憶手段に記憶されたパターンの数が、前記パターン記憶手段に記憶された全パターンを構成する代表点の数よりも多いことを特徴とする請求項２に記載の動きベクトル検出装置。
【請求項５】
前記パターン記憶手段に記憶された各パターンが、他の一又は複数の前記パターンの少なくともいずれか１つと一部において重なり合っていることを特徴とする請求項２に記載の動きベクトル検出装置。
【請求項６】
前記対象フレーム記憶手段又は前記参照フレーム記憶手段に記憶されたフレーム画像がどのような種類の動画像に係るものであるかを判定する判定手段と、
前記判定手段による判定結果に基づいて、前記パターン記憶手段に記憶された前記複数のパターンのうちの少なくとも１つの前記パターンの形状を変更するパターン変更手段とをさらに備えていることを特徴とする請求項２に記載の動きベクトル検出装置。
【請求項７】
前記パターン記憶手段に記憶された各パターンに関連して複数の候補ベクトルを記憶する候補ベクトル記憶手段をさらに備えており、
前記第１の候補ベクトル抽出手段が、前記パターン抽出手段で抽出されたパターンに関連して前記候補ベクトル記憶手段に記憶された複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出することを特徴とする請求項２に記載の動きベクトル検出装置。
【請求項８】
符号化対象フレーム画像において当該対象ブロックの周辺にある複数のブロックにそれぞれ係る既知である複数の周辺動きベクトルに基づいて、前記パターン記憶手段に記憶された複数のパターンに優先順位を割り付ける優先順位割付手段をさらに備えており、
前記パターン抽出手段が、前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記優先順位割付手段によって前記優先順位が割り付けられた複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付手段が優先順位を割り付けた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出することを特徴とする請求項２に記載の動きベクトル検出装置。
【請求項９】
前記優先順位割付手段が、符号化対象フレーム画像において当該対象ブロックの周辺にある複数のブロックにそれぞれ係る既知である複数の周辺動きベクトルに基づいて、前記パターン記憶手段に記憶された複数のパターン及び前記複数の周辺動きベクトルによって定義された一又は複数のパターンに優先順位を割り付け、
前記パターン抽出手段が、前記優先順位割付手段によって前記優先順位が割り付けられた２以上のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが前記所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付手段が優先順位を割り付けた２以上のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出することを特徴とする請求項８に記載の動きベクトル検出装置。
【請求項１０】
符号化対象フレーム画像において当該対象ブロックの周辺にある複数のブロックにそれぞれ係る既知である複数の周辺動きベクトルに基づいて、前記パターン記憶手段に記憶された複数のパターンの中から、探索すべき２以上のパターンを選択するパターン選択手段をさらに備えており、
前記パターン抽出手段が、前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記パターン選択手段で選択された探索すべき２個以上のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出することを特徴とする請求項２に記載の動きベクトル検出装置。
【請求項１１】
符号化対象フレーム画像において前記対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記所定探索範囲内に定められており且つそれぞれに前記パターン記憶手段に記憶された複数のパターンのうちの少なくとも２個のパターンが関連づけられた同心状の複数のリングの中から、探索すべき一又は複数のリングを選択する探索リング選択手段をさらに備えており、
前記パターン抽出手段が、前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記探索リング選択手段で選択された探索すべき一又は複数のリングに関連づけられた２個以上のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出することを特徴とする請求項２に記載の動きベクトル検出装置。
【請求項１２】
前記一又は複数の周辺動きベクトルの代表値を、参照動きベクトルとして導出する参照動きベクトル導出手段と、
前記参照動きベクトル導出手段で導出された参照動きベクトル分だけ前記所定探索範囲をシフトする探索範囲変更手段とをさらに備えており、
前記探索リング選択手段が、前記一又は複数の周辺動きベクトルに基づいて、前記探索範囲変更手段によってシフトされた前記所定探索範囲内に定められた前記複数のリングの中から、探索すべき一又は複数のリングを選択することを特徴とする請求項１１に記載の動きベクトル検出装置。
【請求項１３】
整数ピクセル精度で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似したサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付ける優先順位割付手段と、
前記優先順位割付手段によって前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付手段が優先順位を割り付けた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出するサブピクセル抽出手段とをさらに備えていることを特徴とする請求項２又は３に記載の動きベクトル検出装置。
【請求項１４】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、探索すべき一又は複数のパターンを選択する探索パターン選択手段と、
前記探索パターン選択手段で選択された探索すべき一又は複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、
前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出手段とを備えていることを特徴とする動きベクトル検出装置。
【請求項１５】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれに一次元パターン又は二次元パターンである複数のパターンが関連づけられた同心状の複数のリングの中から、探索すべき一又は複数のリングを選択する探索リング選択手段と、
前記探索リング選択手段で選択された探索すべき一又は複数のリングに関連づけられた複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、
前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する第１の候補ベクトル抽出手段とを備えていることを特徴とする動きベクトル検出装置。
【請求項１６】
前記一又は複数の周辺動きベクトルの代表値を、参照動きベクトルとして導出する参照動きベクトル導出手段と、
前記所定探索範囲を、前記参照動きベクトル導出手段で導出された参照動きベクトル分だけシフトする探索範囲変更手段とをさらに備えており、
前記探索リング選択手段が、前記一又は複数の周辺動きベクトルに基づいて、前記探索範囲変更手段によってシフトされた前記所定探索範囲内に定められた前記複数のリングの中から、探索すべき一又は複数のリングを選択することを特徴とする請求項１５に記載の動きベクトル検出装置。
【請求項１７】
前記第１の候補ベクトル抽出手段で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似した一又は複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する第２の候補ベクトル抽出手段をさらに備えていることを特徴とする請求項１５又は１６に記載の動きベクトル検出装置。
【請求項１８】
参照動きベクトルの絶対値、前記一又は複数の周辺動きベクトルの評価差分、及び、前記所定探索範囲を参照動きベクトル分だけシフトした後の探索中心点におけるＳＡＤ値の少なくともいずれか１つを導出する評価値演算手段と、
前記評価値演算手段における演算結果に基づいて、前記第２の候補ベクトル抽出手段による候補ベクトルの抽出を行うか否かを判断する判断手段とをさらに備えていることを特徴とする請求項１６に記載の動きベクトル検出装置。
【請求項１９】
参照動きベクトルの絶対値、前記一又は複数の周辺動きベクトルの評価差分、及び、前記所定探索範囲を参照動きベクトル分だけシフトした後の探索中心点におけるＳＡＤ値の少なくともいずれか１つを導出する評価値演算手段をさらに備えており、
前記探索リング選択手段が、前記評価値演算手段における演算結果に基づいて、探索すべき一又は複数のリングを選択することを特徴とする請求項１６に記載の動きベクトル検出装置。
【請求項２０】
符号化対象フレーム画像を記憶する対象フレーム記憶手段と、
参照フレーム画像を記憶する参照フレーム記憶手段と、
前記対象フレーム記憶手段に記憶された符号化対象フレーム画像から、画素群である対象ブロックを順次抽出する対象ブロック抽出手段と、
符号化対象フレーム画像において前記対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルの代表値を、参照動きベクトルとして導出する参照動きベクトル導出手段と、
前記対象ブロック抽出手段によって抽出された対象ブロックごとに、前記参照フレーム記憶手段に記憶された参照フレーム画像から、互いに一又は複数画素ずつ変位した画素群である複数の参照ブロックであって、その代表点が当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に位置している複数の参照ブロックを抽出する参照ブロック抽出手段と、
前記複数の参照ブロックから選択された２以上の参照ブロックの代表点を包含しており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンを記憶するパターン記憶手段と、
前記所定探索範囲を、前記参照動きベクトル導出手段で導出された参照動きベクトル分だけシフトする探索範囲変更手段と、
前記一又は複数の周辺動きベクトルに基づいて、前記探索範囲変更手段によってシフトされた前記所定探索範囲内に定められており且つそれぞれに前記パターン記憶手段に記憶された複数のパターンのうちの少なくとも２個のパターンが関連づけられた同心状の複数のリングの中から、探索すべき一又は複数のリングを選択する探索リング選択手段と、
前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記探索リング選択手段で選択された探索すべき一又は複数のリングに関連づけられた２個以上のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、
前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出手段とを備えていることを特徴とする動きベクトル検出装置。
【請求項２１】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンに優先順位を割り付ける優先順位割付手段と、
前記優先順位割付手段によって前記優先順位が割り付けられた前記複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付手段が優先順位を割り付けた前記複数のリングに関連づけられた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出するパターン抽出手段と、
前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出手段とを備えていることを特徴とする動きベクトル検出装置。
【請求項２２】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれに一次元パターン又は二次元パターンである複数のパターンが関連づけられた同心状の複数のリングに優先順位を割り付ける優先順位割付手段と、
前記優先順位割付手段によって前記優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付手段が優先順位を割り付けた前記複数のリングに関連づけられた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出するパターン抽出手段と、
前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出手段とを備えていることを特徴とする動きベクトル検出装置。
【請求項２３】
前記一又は複数の周辺動きベクトルの代表値を、参照動きベクトルとして導出する参照動きベクトル導出手段と、
前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲を、前記参照動きベクトル導出手段で導出された参照動きベクトル分だけシフトする探索範囲変更手段とをさらに備えており、
前記優先順位割付手段が、前記一又は複数の周辺動きベクトルに基づいて、前記探索範囲変更手段によってシフトされた前記所定探索範囲内に定められた前記複数のリングに優先順位を割り付けることを特徴とする請求項２２に記載の動きベクトル検出装置。
【請求項２４】
符号化対象フレーム画像内の画素群である対象ブロックに対して整数ピクセル精度で導出された候補ベクトル、及び、当該抽出された候補ベクトルに近似したサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付ける優先順位割付手段と、
前記優先順位割付手段によって前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが第１の所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付手段が優先順位を割り付けた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出する第１のサブピクセル抽出手段とを備えていることを特徴とする動きベクトル検出装置。
【請求項２５】
前記第１のサブピクセル抽出手段が、
前記優先順位割付手段が優先順位を割り付けた候補ベクトルの数より小さい所定番目以前に探索中の候補ベクトルが前記第１の所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付手段が優先順位を割り付けた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、前記対象ブロックと最も相関性の高い候補ベクトルとして抽出し、
前記所定番目よりも後に探索中の候補ベクトルが第２の所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、探索済みの一又は複数の候補ベクトルの中で第３の所定条件を満たすものを、前記対象ブロックと最も相関性の高い候補ベクトルとして抽出することを特徴とする請求項２４に記載の動きベクトル検出装置。
【請求項２６】
前記第１の所定条件が前記第２の所定条件よりもクリアしにくい条件であることを特徴とする請求項２５に記載の動きベクトル検出装置。
【請求項２７】
前記第１のサブピクセル抽出手段で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似し且つ当該抽出された候補ベクトルよりもさらに高精度なサブピクセル精度の一又は複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する第２のサブピクセルベクトル抽出手段をさらに備えていることを特徴とする請求項２４に記載の動きベクトル検出装置。
【請求項２８】
前記第２のサブピクセル抽出手段が、前記第１のサブピクセル抽出手段で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似し且つ当該抽出された候補ベクトルよりもさらに高精度なサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付け、前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが第４の所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、優先順位が割り付けられた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出することを特徴とする請求項２７に記載の動きベクトル検出装置。
【請求項２９】
符号化対象フレーム画像を記憶する対象フレーム記憶手段と、
参照フレーム画像を記憶する参照フレーム記憶手段と、
前記対象フレーム記憶手段に記憶された符号化対象フレーム画像から、画素群である対象ブロックを順次抽出する対象ブロック抽出手段と、
前記対象ブロック抽出手段によって抽出された対象ブロックごとに、前記参照フレーム記憶手段に記憶された参照フレーム画像から、互いに一又は複数画素ずつ変位した画素群である複数の参照ブロックであって、その代表点が当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に位置している複数の参照ブロックを抽出する参照ブロック抽出手段と、
前記複数の参照ブロックから選択された２以上の参照ブロックの代表点を包含しており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンを記憶するパターン記憶手段と、
前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記パターン記憶手段に記憶された前記複数のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、
前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを整数ピクセル精度で抽出する候補ベクトル抽出手段と、
整数ピクセル精度で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似したサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付ける優先順位割付手段と、
前記優先順位割付手段によって前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付手段が優先順位を割り付けた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出するサブピクセル抽出手段とを備えていることを特徴とする動きベクトル検出装置。
【請求項３０】
符号化対象フレーム画像内の画素群である対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えていることを特徴とする動きベクトル検出方法。
【請求項３１】
符号化対象フレーム画像から、画素群である対象ブロックを順次抽出する対象ブロック抽出ステップと、
前記対象ブロック抽出ステップにおいて抽出された対象ブロックごとに、参照フレーム画像から、互いに一又は複数画素ずつ変位した画素群である複数の参照ブロックであって、その代表点が当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に位置している複数の参照ブロックを抽出する参照ブロック抽出ステップと、
前記対象ブロック抽出ステップにおいて抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出ステップにおいて抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記複数の参照ブロックから選択された２以上の参照ブロックの代表点を包含しており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えていることを特徴とする動きベクトル検出方法。
【請求項３２】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、探索すべき一又は複数のパターンを選択する探索パターン選択ステップと、
前記探索パターン選択ステップにおいて選択された探索すべき一又は複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えていることを特徴とする動きベクトル検出方法。
【請求項３３】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれに一次元パターン又は二次元パターンである複数のパターンが関連づけられた同心状の複数のリングの中から、探索すべき一又は複数のリングを選択する探索リング選択ステップと、
前記探索リング選択ステップにおいて選択された探索すべき一又は複数のリングに関連づけられた複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えていることを特徴とする動きベクトル検出方法。
【請求項３４】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンに優先順位を割り付ける優先順位割付ステップと、
前記優先順位割付ステップにおいて前記優先順位が割り付けられた前記複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付ステップにおいて優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えていることを特徴とする動きベクトル検出方法。
【請求項３５】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれに一次元パターン又は二次元パターンである複数のパターンが関連づけられた同心状の複数のリングに優先順位を割り付ける優先順位割付ステップと、
前記優先順位割付ステップにおいて前記優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付ステップにおいて優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えていることを特徴とする動きベクトル検出方法。
【請求項３６】
符号化対象フレーム画像内の画素群である対象ブロックに対して整数ピクセル精度で導出された候補ベクトル、及び、当該抽出された候補ベクトルに近似したサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付ける優先順位割付ステップと、
前記優先順位割付ステップにおいて前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが第１の所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付ステップにおいて優先順位が割り付けられた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出するサブピクセル抽出ステップとを備えていることを特徴とする動きベクトル検出方法。
【請求項３７】
符号化対象フレーム画像内の画素群である対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとをコンピュータに実行させることが可能である動きベクトル検出プログラム。
【請求項３８】
請求項３７に記載の動きベクトル検出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項３９】
符号化対象フレーム画像から、画素群である対象ブロックを順次抽出する対象ブロック抽出ステップと、
前記対象ブロック抽出ステップにおいて抽出された対象ブロックごとに、参照フレーム画像から、互いに一又は複数画素ずつ変位した画素群である複数の参照ブロックであって、その代表点が当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に位置している複数の参照ブロックを抽出する参照ブロック抽出ステップと、
前記対象ブロック抽出ステップにおいて抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出ステップにおいて抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記複数の参照ブロックから選択された２以上の参照ブロックの代表点を包含しており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとをコンピュータに実行させることが可能である動きベクトル検出プログラム。
【請求項４０】
請求項３９に記載の動きベクトル検出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項４１】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、探索すべき一又は複数のパターンを選択する探索パターン選択ステップと、
前記探索パターン選択ステップにおいて選択された探索すべき一又は複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えていることを特徴とする動きベクトル検出方法。
【請求項４２】
請求項４１に記載の動きベクトル検出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項４３】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれに一次元パターン又は二次元パターンである複数のパターンが関連づけられた同心状の複数のリングの中から、探索すべき一又は複数のリングを選択する探索リング選択ステップと、
前記探索リング選択ステップにおいて選択された探索すべき一又は複数のリングに関連づけられた複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとをコンピュータに実行させることが可能である動きベクトル検出プログラム。
【請求項４４】
請求項４３に記載の動きベクトル検出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項４５】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンに優先順位を割り付ける優先順位割付ステップと、
前記優先順位割付ステップにおいて前記優先順位が割り付けられた前記複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付ステップにおいて優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えていることを特徴とする動きベクトル検出方法。
【請求項４６】
請求項４５に記載の動きベクトル検出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項４７】
符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれに一次元パターン又は二次元パターンである複数のパターンが関連づけられた同心状の複数のリングに優先順位を割り付ける優先順位割付ステップと、
前記優先順位割付ステップにおいて前記優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付ステップにおいて優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出するパターン抽出ステップと、
前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとをコンピュータに実行させることが可能である動きベクトル検出プログラム。
【請求項４８】
請求項４７に記載の動きベクトル検出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項４９】
符号化対象フレーム画像内の画素群である対象ブロックに対して整数ピクセル精度で導出された候補ベクトル、及び、当該抽出された候補ベクトルに近似したサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付ける優先順位割付ステップと、
前記優先順位割付ステップにおいて前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが第１の所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付ステップにおいて優先順位が割り付けられた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出するサブピクセル抽出ステップとをコンピュータに実行させることが可能である動きベクトル検出プログラム。
【請求項５０】
請求項４９に記載の動きベクトル検出プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像の符号化手法である動き補償予測符号化において用いられる動きベクトルを検出するための動きベクトル検出装置、動きベクトル検出方法、動きベクトル検出プログラム及びこれを記録した記録媒体に関する。
【背景技術】
【０００２】
動画像の符号化においては、符号化効率を上げるために、符号化対象フレームと、直前フレームなどの符号化対象フレームの前後の一又は複数のフレーム（以下、「参照フレーム」という）との差分を符号化するフレーム間予測符号化技術が用いられる。フレーム間予測符号化を行うに当たって単純に符号化対象フレームと参照フレームとの差分を取るようにすると、両フレームの画像内容が大きく異なる場合には、差分値が大きくなって、符号化効率が悪くなる。そのため、符号化対象フレームと参照フレームと比較して画像の動きを検出し、参照フレームを検出された画像の動きに対応させてシフトしてから差分を取ることで、符号化対象フレームを効率的に符号化することが行われている。このシフト分を一般的に「動きベクトル」という。
【０００３】
動きベクトルを検出するための一つの手法として、ブロックマッチング法がある。ブロックマッチング法では、図３５に示すように、符号化対象フレーム画像２１０を、それぞれが複数の画素２１１からなり且つ所定サイズ（図３５において、１０画素×１０画素の正方形）を有する複数のブロック２１２に分割し、その中から動きベクトル検出対象となるブロック（対象ブロック）２１４を順次抽出する。そして、対象ブロック２１４の画素値と、対象ブロック２１４に関して参照フレーム画像２２０内に設けられた探索範囲内に代表点２２１（以下の説明において、各ブロックの代表点がブロックの左上角にあるものとして説明する）があり且つ対象ブロック２１４と同じ大きさを有する複数のブロック（参照ブロック）２２２の画素値との差分絶対値和（ＳＡＤ：Sum of Absolute Difference）をそれぞれ計算する。そして、複数の参照ブロック２２２の中から、差分絶対値和が最も小さくなる参照ブロック２２４を当該対象ブロック２１４と最も相関性の高い参照ブロックとして抽出し、抽出された参照ブロック２２４と対象ブロック２１４との空間的な位置ずれを動きベクトル２３０として検出する。
【０００４】
図３６は、ブロックマッチング法における探索範囲の一例について説明するための模式図である。本例において、探索範囲２３２は、対象ブロック２１４を参照フレーム画像２２０内の同じ位置に配置したときの対象ブロック２１４の代表点２１３の位置（探索中心点）２３４を中心とした１４画素×１４画素の正方形領域である。したがって、ブロックマッチング法の一つであるいわゆるフルサーチ法では、正方形領域の各格子点２３５と探索中心点２３４との間を結ぶ線分を動きベクトルの候補ベクトルとして、２２５個（１５×１５）の候補ベクトルにそれぞれ関連した（つまり、候補ベクトルの終点を代表点とした）２２５個の参照ブロック２２２について差分絶対値和の演算が行われる。そのため、演算量が膨大になって、動画像符号化処理中における動きベクトル検出処理の占める割合が非常に大きくなる。
【０００５】
これに対して、上述した方法よりも演算量を低減させることができる動きベクトルの検出方法がいくつか報告されている。その代表的な方法として、非特許文献１には、段階的探索法であるＴＳＳ（Three Step Search）法が記載されている。図３７に示すように、ＴＳＳ法では、探索範囲２３２内において探索中心点２３４の周りに互いに離隔した複数の点（探索中心点を中心とした正方形を形成する８個の点）２３６（図３７において(1)として描かれている）を定義し、探索中心点２３４及び各点２３６と探索中心点２３４とを結ぶ線分をそれぞれ一次候補ベクトルとして、一次候補ベクトルにそれぞれ関連した参照ブロックについて対象ブロックとの画素値の差分絶対値和を求める。そして、差分絶対値和が最小の点を抽出し、抽出された点を新たな探索中心点２３７とする。さらに、探索中心点２３７の周りに互いの離隔距離がより小さい複数の点２３８（図３７において(2)として描かれている）を定義し、探索中心点２３７及び各点２３８と探索中心点２３４とを結ぶ線分をそれぞれ二次候補ベクトルとして、二次候補ベクトルにそれぞれ関連した参照ブロックについて対象ブロックとの画素値の差分絶対値和を求める。そして、差分絶対値和が最小の点を抽出し、抽出された点を新たな探索中心点２３９とする。さらに、探索中心点２３９の周りに互いの離隔距離がより小さい複数の点２４０（図３７において(3)として描かれている）を定義し、探索中心点２３９及び各点２４０と探索中心点２３４とを結ぶ線分をそれぞれ三次候補ベクトルとして、三次候補ベクトルにそれぞれ関連した参照ブロックについて対象ブロックとの画素値の差分絶対値和を求める。そして、差分絶対値和が最小の点２４１と最初の探索中心点２３４とを結ぶ線分を動きベクトル２４２として検出する。ＴＳＳ法によると、差分絶対値和が計算される参照ブロックの数が減るために、演算量が低減されて動きベクトルを迅速に求めることが可能となる。
【０００６】
【非特許文献１】T.Koga, K. Linuma, A. Hirano, Y. Iijima, and T. Ishiguro,  "Motion-Compensated Interframe Coding for Video Conferencing"  NTC 81 Proceeding, (米国),  １９８１年１２月,  p. G5.3.1--5
【発明の開示】
【発明が解決しようとする課題】
【０００７】
次世代の動画像符号化規格であるＨ．２６４においては、２以上のフレームを参照フレームとする多フレーム間予測と、サブピクセル精度（例えば１／２精度又は１／４画素精度）の動き補償とが採用されている。多フレーム間予測では、過去の数フレームを参照フレームとして動きベクトル検出がそれぞれ行われ、そのうちで差分絶対値和が最小となる動きベクトルが選択される。そのため、すべての参照フレームに同じ広さの探索範囲が設定されたのでは、演算量が膨大になる。そこで、Ｈ．２６４における多フレーム間予測では、直前フレームに対しては広い探索範囲が設定され、その他の参照フレームに対しては、直前フレームで検出した動きベクトルを中心とした狭い探索範囲が設定される。また、Ｈ．２６４において、サブピクセル精度の動きベクトルを検出するには、まず整数ピクセル精度で動きベクトルが検出され、検出された整数ピクセル精度の動きベクトルを候補ベクトルとし、この候補ベクトルに近似したサブピクセル精度の候補ベクトルの中から差分絶対値和が最小となるものが動きベクトルとして抽出される。
【０００８】
上記の説明から理解されるように、多フレーム間予測技術では直前フレームの動きベクトル検出が、サブピクセル精度の動き補償技術では整数ピクセル精度の動きベクトル検出が高い信頼性で行われることを前提としており、その検出信頼性が低ければ最終的に検出される動きベクトルも信頼性の低いものとなってしまう。したがって、直前フレームの動きベクトルや整数ピクセル精度の動きベクトル検出の信頼性は極めて高いものでなければならない。しかしながら、上述したＴＳＳ法では、演算量を大幅に低減しているために、場合によっては、検出された動きベクトルが理想的なものと大きくずれてしまうことがある。
【０００９】
また、整数ピクセル精度の動きベクトル検出後に行われるサブピクセル精度の動きベクトル検出においても、高い信頼性と少ない演算量との両立を図りつつ動きベクトルを検出可能とすることは、ハードウェア負荷を低減させる上で重要である。
【００１０】
そこで、本発明の一つの目的は、演算量を比較的少なくしつつ、動きベクトルを高い信頼性で検出することが可能な動きベクトル検出装置、動きベクトル検出方法、動きベクトル検出プログラム及びこれを記録した記録媒体を提供することである。
【００１１】
本発明の別の目的は、演算量を比較的少なくしつつ、サブピクセル精度の動きベクトルを高い信頼性で検出することが可能な動きベクトル検出装置、動きベクトル検出方法、動きベクトル検出プログラム及びこれを記録した記録媒体を提供することである。
【課題を解決するための手段及び発明の効果】
【００１２】
本発明の動きベクトル検出装置は、符号化対象フレーム画像内の画素群である対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出手段とを備えている。
【００１３】
別の観点において、本発明の動きベクトル検出装置は、符号化対象フレーム画像を記憶する対象フレーム記憶手段と、参照フレーム画像を記憶する参照フレーム記憶手段と、
前記対象フレーム記憶手段に記憶された符号化対象フレーム画像から、画素群である対象ブロックを順次抽出する対象ブロック抽出手段と、前記対象ブロック抽出手段によって抽出された対象ブロックごとに、前記参照フレーム記憶手段に記憶された参照フレーム画像から、互いに一又は複数画素ずつ変位した画素群である複数の参照ブロックであって、その代表点が当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に位置している複数の参照ブロックを抽出する参照ブロック抽出手段と、前記複数の参照ブロックから選択された２以上の参照ブロックの代表点を包含しており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンを記憶するパターン記憶手段と、前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記パターン記憶手段に記憶された前記複数のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出する第１の候補ベクトル抽出手段とを備えている。
【００１４】
本発明の動きベクトル検出方法は、符号化対象フレーム画像内の画素群である対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えている。
【００１５】
別の観点において、本発明の動きベクトル検出方法は、符号化対象フレーム画像から、画素群である対象ブロックを順次抽出する対象ブロック抽出ステップと、前記対象ブロック抽出ステップにおいて抽出された対象ブロックごとに、参照フレーム画像から、互いに一又は複数画素ずつ変位した画素群である複数の参照ブロックであって、その代表点が当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に位置している複数の参照ブロックを抽出する参照ブロック抽出ステップと、前記対象ブロック抽出ステップにおいて抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出ステップにおいて抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記複数の参照ブロックから選択された２以上の参照ブロックの代表点を包含しており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えている。
【００１６】
この構成によると、所定探索範囲内から最初に一次元パターン又は二次元パターンが抽出されるので、上述したＴＳＳ法のように最初に点が抽出される場合と比較して、次に行われる候補ベクトル抽出段階において、画像の実際の動きにより即した複数の候補ベクトルの中から１つの候補ベクトルを抽出することが可能となる。したがって、抽出された候補ベクトルが理想的な動きベクトルに近い信頼性の高いものとなり、しかも、フルサーチが行われる場合と比較して、演算量を少なくすることができる。なお、このようにして抽出された候補ベクトルを、検出された動きベクトルとしてもよいし、さらに次の段階で候補ベクトルを抽出するために用いてもよい。
【００１７】
本発明の動きベクトル検出装置は、前記第１の候補ベクトル抽出手段で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似した一又は複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出する第２の候補ベクトル抽出手段をさらに備えていてよい。これによると、抽出された候補ベクトルが理想的な動きベクトルにさらに近い信頼性の高いものとなる。なお、このようにして抽出された候補ベクトルを、検出された動きベクトルとしてもよいし、さらに次の段階で候補ベクトルを抽出するために用いてもよい。
【００１８】
本発明の動きベクトル検出装置において、前記パターン記憶手段に記憶されたパターンの数が、前記パターン記憶手段に記憶された全パターンを構成する代表点の数よりも多いことが好ましい。これによって、より好適なパターンを抽出することが可能となる。
【００１９】
本発明の動きベクトル検出装置において、前記パターン記憶手段に記憶された各パターンが、他の一又は複数の前記パターンの少なくともいずれか１つと一部において重なり合っていることが好ましい。これによると、最初のパターン抽出で適切でないパターンが選択されたとしても次の段階でのリカバリーが可能となって、動きベクトルをさらに信頼性高く検出することが可能となる。
【００２０】
本発明の動きベクトル検出装置は、前記対象フレーム記憶手段又は前記参照フレーム記憶手段に記憶されたフレーム画像がどのような種類の動画像に係るものであるかを判定する判定手段と、前記判定手段による判定結果に基づいて、前記パターン記憶手段に記憶された前記複数のパターンのうちの少なくとも１つの前記パターンの形状を変更するパターン変更手段とをさらに備えていてよい。これによると、動画像の種類に応じた形状のパターンを用いることが可能となるため、動きベクトルをさらに信頼性高く検出することが可能となる。
【００２１】
本発明の動きベクトル検出装置は、前記パターン記憶手段に記憶された各パターンに関連して複数の候補ベクトルを記憶する候補ベクトル記憶手段をさらに備えていてよい。このとき、前記第１の候補ベクトル抽出手段が、前記パターン抽出手段で抽出されたパターンに関連して前記候補ベクトル記憶手段に記憶された複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出することが好ましい。これによると、各パターンに適した複数の候補ベクトルを用意しておくことが可能となるので、動きベクトルをさらに信頼性高く検出することが可能となる。
【００２２】
本発明の動きベクトル検出装置は、符号化対象フレーム画像において当該対象ブロックの周辺にある複数のブロックにそれぞれ係る既知である複数の周辺動きベクトルに基づいて、前記パターン記憶手段に記憶された複数のパターンに優先順位を割り付ける優先順位割付手段をさらに備えていてよい。このとき、前記パターン抽出手段が、前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記優先順位割付手段によって前記優先順位が割り付けられた複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付手段が優先順位を割り付けた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出することが好ましい。これによると、すべてのパターンの探索が終了していない時点であっても対象ブロックと最も相関性の高いパターンを抽出可能であるので、さらに演算量の低減を図ることが可能となる。また、複数の周辺動きベクトルを用いることによって、抽出される可能性の高いパターンに早い優先順位を割り付けることが可能となるので、さらに演算量の低減を図ることが可能となる。
【００２３】
また、前記優先順位割付手段が、符号化対象フレーム画像において当該対象ブロックの周辺にある複数のブロックにそれぞれ係る既知である複数の周辺動きベクトルに基づいて、前記パターン記憶手段に記憶された複数のパターン及び前記複数の周辺動きベクトルによって定義された一又は複数のパターンに優先順位を割り付けてよい。そして、このとき、前記パターン抽出手段が、前記優先順位割付手段によって前記優先順位が割り付けられた２以上のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが前記所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付手段が優先順位を割り付けた２以上のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出してよい。これによると、パターン記憶手段に記憶された複数のパターンだけではなく、複数の周辺動きベクトルによって定義された一又は複数のパターンが対象ブロックと最も相関性の高いパターンとして抽出され得るので、より好適なパターンを抽出することが可能となる。
【００２４】
本発明の動きベクトル検出装置は、符号化対象フレーム画像において当該対象ブロックの周辺にある複数のブロックにそれぞれ係る既知である複数の周辺動きベクトルに基づいて、前記パターン記憶手段に記憶された複数のパターンの中から、探索すべき２以上のパターンを選択するパターン選択手段をさらに備えていてよい。このとき、前記パターン抽出手段が、前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記パターン選択手段で選択された探索すべき２個以上のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出することが好ましい。これによると、周辺動きベクトルを参照することによって探索されるパターン数を削減することができるので、さらに演算量の低減を図ることが可能となる。
【００２５】
本発明の動きベクトル検出装置は、符号化対象フレーム画像において前記対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記所定探索範囲内に定められており且つそれぞれに前記パターン記憶手段に記憶された複数のパターンのうちの少なくとも２個のパターンが関連づけられた同心状の複数のリングの中から、探索すべき一又は複数のリングを選択する探索リング選択手段をさらに備えていてよい。このとき、前記パターン抽出手段が、前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記探索リング選択手段で選択された探索すべき一又は複数のリングに関連づけられた２個以上のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出することが好ましい。これによると、周辺動きベクトルを参照することによって探索されるパターン数を削減することができるので、さらに演算量の低減を図ることが可能となる。
【００２６】
この場合、前記一又は複数の周辺動きベクトルの代表値を、参照動きベクトルとして導出する参照動きベクトル導出手段と、前記参照動きベクトル導出手段で導出された参照動きベクトル分だけ前記所定探索範囲をシフトする探索範囲変更手段とをさらに備えていてよい。そして、前記探索リング選択手段が、前記一又は複数の周辺動きベクトルに基づいて、前記探索範囲変更手段によってシフトされた前記所定探索範囲内に定められた前記複数のリングの中から、探索すべき一又は複数のリングを選択することが好ましい。これによると、抽出される候補ベクトルが比較的小さなベクトルになる可能性が高くなるため、どのリングを選択するかの条件として最も内側のリングの選択条件だけを用意し、リング選択を少ない演算量で行ったとしても、適切なリングを選択できる可能性が高くなる。
【００２７】
本発明の動きベクトル検出装置は、整数ピクセル精度で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似したサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付ける優先順位割付手段と、前記優先順位割付手段によって前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付手段が優先順位を割り付けた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出するサブピクセル抽出手段とをさらに備えていてよい。これによると、演算量を比較的少なくしつつ、サブピクセル精度の動きベクトルを高い信頼性で検出することが可能となる。
【００２８】
別の観点において、本発明の動きベクトル検出装置は、符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、探索すべき一又は複数のパターンを選択する探索パターン選択手段と、前記探索パターン選択手段で選択された探索すべき一又は複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出手段とを備えている。
【００２９】
別の観点において、本発明の動きベクトル検出方法は、符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンの中から、探索すべき一又は複数のパターンを選択する探索パターン選択ステップと、前記探索パターン選択ステップにおいて選択された探索すべき一又は複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えている。
【００３０】
また、別の観点において、本発明の動きベクトル検出装置は、符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれに一次元パターン又は二次元パターンである複数のパターンが関連づけられた同心状の複数のリングの中から、探索すべき一又は複数のリングを選択する探索リング選択手段と、前記探索リング選択手段で選択された探索すべき一又は複数のリングに関連づけられた複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する第１の候補ベクトル抽出手段とを備えている。
【００３１】
本発明の動きベクトル検出装置は、さらに別の観点では、符号化対象フレーム画像を記憶する対象フレーム記憶手段と、参照フレーム画像を記憶する参照フレーム記憶手段と、前記対象フレーム記憶手段に記憶された符号化対象フレーム画像から、画素群である対象ブロックを順次抽出する対象ブロック抽出手段と、符号化対象フレーム画像において前記対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルの代表値を、参照動きベクトルとして導出する参照動きベクトル導出手段と、前記対象ブロック抽出手段によって抽出された対象ブロックごとに、前記参照フレーム記憶手段に記憶された参照フレーム画像から、互いに一又は複数画素ずつ変位した画素群である複数の参照ブロックであって、その代表点が当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に位置している複数の参照ブロックを抽出する参照ブロック抽出手段と、前記複数の参照ブロックから選択された２以上の参照ブロックの代表点を包含しており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンを記憶するパターン記憶手段と、前記所定探索範囲を、前記参照動きベクトル導出手段で導出された参照動きベクトル分だけシフトする探索範囲変更手段と、前記一又は複数の周辺動きベクトルに基づいて、前記探索範囲変更手段によってシフトされた前記所定探索範囲内に定められており且つそれぞれに前記パターン記憶手段に記憶された複数のパターンのうちの少なくとも２個のパターンが関連づけられた同心状の複数のリングの中から、探索すべき一又は複数のリングを選択する探索リング選択手段と、前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記探索リング選択手段で選択された探索すべき一又は複数のリングに関連づけられた２個以上のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出手段とを備えている。
【００３２】
別の観点では、本発明の動きベクトル検出方法は、符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれに一次元パターン又は二次元パターンである複数のパターンが関連づけられた同心状の複数のリングの中から、探索すべき一又は複数のリングを選択する探索リング選択ステップと、前記探索リング選択ステップにおいて選択された探索すべき一又は複数のリングに関連づけられた複数のパターンの中から、前記対象ブロックと最も相関性の高いパターンを抽出するパターン抽出ステップと、前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えている。
【００３３】
この構成によると、所定探索範囲内から最初に一次元パターン又は二次元パターンが抽出されるので、上述したＴＳＳ法のように最初に点が抽出される場合と比較して、次の段階において、画像の実際の動きにより即した複数の候補ベクトルの中から１つの候補ベクトルを抽出することが可能となる。したがって、抽出された候補ベクトルが理想的な動きベクトルに近い信頼性の高いものとなり、しかも、周辺動きベクトルを参照することによって探索されるパターン数を削減することができるので、フルサーチが行われる場合と比較して、演算量を非常に少なくすることができる。なお、このようにして抽出された候補ベクトルを、検出された動きベクトルとしてもよいし、さらに次の段階で候補ベクトルを抽出するために用いてもよい。
【００３４】
本発明の動きベクトル検出装置は、前記一又は複数の周辺動きベクトルの代表値を、参照動きベクトルとして導出する参照動きベクトル導出手段と、前記所定探索範囲を、前記参照動きベクトル導出手段で導出された参照動きベクトル分だけシフトする探索範囲変更手段とをさらに備えていてよい。このとき、前記探索リング選択手段が、前記一又は複数の周辺動きベクトルに基づいて、前記探索範囲変更手段によってシフトされた前記所定探索範囲内に定められた前記複数のリングの中から、探索すべき一又は複数のリングを選択することが好ましい。これによると、抽出される候補ベクトルが比較的小さなベクトルになる可能性が高くなるため、どのリングを選択するかの条件として最も内側のリングの選択条件だけを用意し、リング選択を少ない演算量で行ったとしても、適切なリングを選択できる可能性が高くなる。
【００３５】
本発明の動きベクトル検出装置は、前記第１の候補ベクトル抽出手段で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似した一又は複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する第２の候補ベクトル抽出手段をさらに備えていてよい。これによると、抽出された候補ベクトルが理想的な動きベクトルにさらに近い信頼性の高いものとなる。なお、このようにして抽出された候補ベクトルを、検出された動きベクトルとしてもよいし、さらに次の段階で候補ベクトルを抽出するために用いてもよい。
【００３６】
本発明の動きベクトル検出装置は、参照動きベクトルの絶対値、前記一又は複数の周辺動きベクトルの評価差分、及び、前記所定探索範囲を参照動きベクトル分だけシフトした後の探索中心点におけるＳＡＤ値の少なくともいずれか１つを導出する評価値演算手段と、前記評価値演算手段における演算結果に基づいて、前記第２の候補ベクトル抽出手段による候補ベクトルの抽出を行うか否かを判断する判断手段とをさらに備えていてよい。これによると、最初に抽出された候補ベクトルが十分に信頼性の高いものであると判断される場合に２回目の候補ベクトル抽出を行わなくて済むので、過剰な計算が行われるのを防止することができる。
【００３７】
本発明の動きベクトル検出装置は、参照動きベクトルの絶対値、前記一又は複数の周辺動きベクトルの評価差分、及び、前記所定探索範囲を参照動きベクトル分だけシフトした後の探索中心点におけるＳＡＤ値の少なくともいずれか１つを導出する評価値演算手段をさらに備えていてよい。このとき、前記探索リング選択手段が、前記評価値演算手段における演算結果に基づいて、探索すべき一又は複数のリングを選択することが好ましい。これによると、各周辺動きベクトルの絶対値などに基づいて、比較的少ない演算量及び高い信頼性で探索すべき一又は複数のリングを選択することが可能となる。
【００３８】
別の観点において、本発明の動きベクトル検出装置は、符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンに優先順位を割り付ける優先順位割付手段と、前記優先順位割付手段によって前記優先順位が割り付けられた前記複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付手段が優先順位を割り付けた前記複数のリングに関連づけられた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出するパターン抽出手段と、前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出手段とを備えている。
【００３９】
別の観点において、本発明の動きベクトル検出方法は、符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンに優先順位を割り付ける優先順位割付ステップと、前記優先順位割付ステップにおいて前記優先順位が割り付けられた前記複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付ステップにおいて優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出するパターン抽出ステップと、前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えている。
【００４０】
また、別の観点において、本発明の動きベクトル検出装置は、符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれに一次元パターン又は二次元パターンである複数のパターンが関連づけられた同心状の複数のリングに優先順位を割り付ける優先順位割付手段と、前記優先順位割付手段によって前記優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付手段が優先順位を割り付けた前記複数のリングに関連づけられた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出するパターン抽出手段と、前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出手段とを備えている。
【００４１】
また、別の観点において、本発明の動きベクトル検出方法は、符号化対象フレーム画像内の画素群である対象ブロックの周辺にある一又は複数のブロックにそれぞれ係る既知である一又は複数の周辺動きベクトルに基づいて、当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に定められており且つそれぞれに一次元パターン又は二次元パターンである複数のパターンが関連づけられた同心状の複数のリングに優先順位を割り付ける優先順位割付ステップと、前記優先順位割付ステップにおいて前記優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンを前記優先順位にしたがって順に探索し、探索中のパターンが所定条件を満たした場合には、すべてのパターンの探索が終了していない時点であっても以後のパターンの探索を行わず、前記優先順位割付ステップにおいて優先順位が割り付けられた前記複数のリングに関連づけられた複数のパターンの中から、当該探索中のパターンを、当該対象ブロックと最も相関性の高いパターンとして抽出するパターン抽出ステップと、前記パターン抽出ステップにおいて抽出されたパターンに関連して定められた複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する候補ベクトル抽出ステップとを備えている。
【００４２】
この構成によると、所定探索範囲内から最初に一次元パターン又は二次元パターンが抽出されるので、上述したＴＳＳ法のように最初に点が抽出される場合と比較して、次に行われる候補ベクトル抽出段階において、画像の実際の動きにより即した複数の候補ベクトルの中から１つの候補ベクトルを抽出することが可能となる。したがって、抽出された候補ベクトルが理想的な動きベクトルに近い信頼性の高いものとなり、しかも、フルサーチが行われる場合と比較して、演算量を少なくすることができる。さらに、すべてのパターンの探索が終了していない時点であっても対象ブロックと最も相関性の高いパターンを抽出可能であるので、さらなる演算量の低減を図ることが可能となる。また、複数の周辺動きベクトルを用いることによって、抽出される可能性の高いパターンに早い優先順位を割り付けることが可能となるので、より一層の演算量の低減を図ることが可能となる。なお、このようにして抽出された候補ベクトルを、検出された動きベクトルとしてもよいし、さらに次の段階で候補ベクトルを抽出するために用いてもよい。
【００４３】
本発明の動きベクトル検出装置は、前記一又は複数の周辺動きベクトルの代表値を、参照動きベクトルとして導出する参照動きベクトル導出手段と、前記対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲を、前記参照動きベクトル導出手段で導出された参照動きベクトル分だけシフトする探索範囲変更手段とをさらに備えていてよい。このとき、前記優先順位割付手段が、前記一又は複数の周辺動きベクトルに基づいて、前記探索範囲変更手段によってシフトされた前記所定探索範囲内に定められた前記複数のリングに優先順位を割り付けることが好ましい。これによると、抽出される候補ベクトルが比較的小さなベクトルになる可能性が高くなるため、どのリングを選択するかの条件として最も内側のリングの選択条件だけを用意し、リング選択を少ない演算量で行ったとしても、適切なリングを選択できる可能性が高くなる。
【００４４】
また、別の観点において、本発明の動きベクトル検出装置は、符号化対象フレーム画像内の画素群である対象ブロックに対して整数ピクセル精度で導出された候補ベクトル、及び、当該抽出された候補ベクトルに近似したサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付ける優先順位割付手段と、前記優先順位割付手段によって前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが第１の所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付手段が優先順位を割り付けた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出する第１のサブピクセル抽出手段とを備えている。
【００４５】
さらに別の観点において、本発明の動きベクトル検出装置は、符号化対象フレーム画像を記憶する対象フレーム記憶手段と、参照フレーム画像を記憶する参照フレーム記憶手段と、前記対象フレーム記憶手段に記憶された符号化対象フレーム画像から、画素群である対象ブロックを順次抽出する対象ブロック抽出手段と、前記対象ブロック抽出手段によって抽出された対象ブロックごとに、前記参照フレーム記憶手段に記憶された参照フレーム画像から、互いに一又は複数画素ずつ変位した画素群である複数の参照ブロックであって、その代表点が当該対象ブロックに関して参照フレーム画像内に設けられた所定探索範囲内に位置している複数の参照ブロックを抽出する参照ブロック抽出手段と、前記複数の参照ブロックから選択された２以上の参照ブロックの代表点を包含しており且つそれぞれが一次元パターン又は二次元パターンである複数のパターンを記憶するパターン記憶手段と、前記対象ブロック抽出手段によって抽出された対象ブロックの画素値と、当該対象ブロックに関連して前記参照ブロック抽出手段によって抽出された複数の参照ブロックの画素値との差分演算に基づいて、前記パターン記憶手段に記憶された前記複数のパターンの中から、当該対象ブロックと最も相関性の高いパターンを抽出するパターン抽出手段と、前記パターン抽出手段で抽出されたパターンに関連して定められた複数の候補ベクトルの中から、当該対象ブロックと最も相関性の高い候補ベクトルを整数ピクセル精度で抽出する候補ベクトル抽出手段と、整数ピクセル精度で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似したサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付ける優先順位割付手段と、前記優先順位割付手段によって前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付手段が優先順位を割り付けた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出するサブピクセル抽出手段とを備えている。
【００４６】
さらに別の観点において、本発明の動きベクトル検出方法は、符号化対象フレーム画像内の画素群である対象ブロックに対して整数ピクセル精度で導出された候補ベクトル、及び、当該抽出された候補ベクトルに近似したサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付ける優先順位割付ステップと、前記優先順位割付ステップにおいて前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付ステップにおいて優先順位が割り付けられた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出するサブピクセル抽出ステップとを備えている。
【００４７】
この構成によると、すべての候補ベクトルの探索が終了していない時点であっても対象ブロックと最も相関性の高い候補ベクトルを抽出可能であるので、演算量を比較的少なくしつつ、サブピクセル精度の動きベクトルを高い信頼性で検出することが可能となる。
【００４８】
本発明の動きベクトル検出装置において、前記第１のサブピクセル抽出手段は、前記優先順位割付手段が優先順位を割り付けた候補ベクトルの数より小さい所定番目以前に探索中の候補ベクトルが前記第１の所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、前記優先順位割付手段が優先順位を割り付けた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、前記対象ブロックと最も相関性の高い候補ベクトルとして抽出してよい。そして、このとき、前記第１のサブピクセル抽出手段は、前記所定番目よりも後に探索中の候補ベクトルが第２の所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、探索済みの一又は複数の候補ベクトルの中で第３の所定条件を満たすものを、前記対象ブロックと最も相関性の高い候補ベクトルとして抽出してよい。このようにすることで、演算量を抑制しつつ、さらに高い信頼性を実現することが可能となる。
【００４９】
この場合、前記第１の所定条件が前記第２の所定条件よりもクリアしにくい条件であることが好ましい。これにより、さらに信頼性を高めることができる。
【００５０】
本発明の動きベクトル検出装置は、前記第１のサブピクセル抽出手段で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似し且つ当該抽出された候補ベクトルよりもさらに高精度なサブピクセル精度の一又は複数の候補ベクトルの中から、前記対象ブロックと最も相関性の高い候補ベクトルを抽出する第２のサブピクセルベクトル抽出手段をさらに備えていてよい。これにより、さらに高精度での動きベクトル検出が可能となる。
【００５１】
この場合、前記第２のサブピクセル抽出手段が、前記第１のサブピクセル抽出手段で抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似し且つ当該抽出された候補ベクトルよりもさらに高精度なサブピクセル精度の一又は複数の候補ベクトルに優先順位を割り付け、前記優先順位が割り付けられた２以上の候補ベクトルを前記優先順位にしたがって順に探索し、探索中の候補ベクトルが第４の所定条件を満たした場合には、すべての候補ベクトルの探索が終了していない時点であっても以後の候補ベクトルの探索を行わず、優先順位が割り付けられた２以上の候補ベクトルの中から、当該探索中の候補ベクトルを、当該対象ブロックと最も相関性の高い候補ベクトルとして抽出してよい。このようにすることで、さらに演算量を抑制することが可能となる。
【００５２】
また、本発明の動きベクトル検出プログラムは、コンピュータにそれぞれ上述したような動きベクトル検出方法を実行させることが可能なプログラムであり、本発明のコンピュータ読み取り可能な記録媒体は、このようなプログラムを格納したものであって、これらのプログラム及び記録媒体は、対応する上記動きベクトル検出方法とそれぞれ同様の作用効果を奏する。記録媒体としては、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）ディスク、フレキシブルディスク（ＦＤ）、ＭＯ（Magneto Optical）ディスクなどのリムーバブル型記録媒体や、ハードディスクなどの固定型記録媒体を用いることができる。
【００５３】
なお、本発明の動きベクトル検出プログラムは、上記のような記録媒体に記録して配布可能である他、有線又は無線の電気通信手段によってインターネットなどの通信ネットワークを介して配布可能である。ここで、コンピュータは、パーソナルコンピュータのような汎用型に限らず、ＤＶＤ（Digital Versatile Disc）レコーダなどの特定用途を有する装置に組み込まれたものであってもよい。
【発明を実施するための最良の形態】
【００５４】
以下、本発明の好適な実施の形態について、図面を参照しつつ説明する。
【００５５】
＜実施の形態１＞
（動きベクトル検出の概略）
まず、本発明の実施の形態１による動きベクトル検出方法の概略について説明する。この動きベクトル検出方法においては、図３５で説明したように、まず、符号化対象フレーム画像２１０から、１０画素×１０画素の対象ブロック２１４を１つ抽出する。そして、抽出された対象ブロック２１４について、６８個のトリプレットパターン（Triplet Pattern）１１１〜１１９（図５〜図１３参照）の中から、対象ブロック２１４と最も相関性の高いトリプレットパターンを抽出する。６８個のトリプレットパターンのそれぞれは、対象ブロック２１４に関して参照フレーム画像２２０内に設けられた探索範囲内に位置する３個の点から構成されている。
【００５６】
次に、抽出された１つのトリプレットパターン１１１〜１１９に関連して定められた複数の候補ベクトルの中から、対象ブロック２１４と最も相関性の高い候補ベクトルを抽出する。さらに、このようにして抽出された候補ベクトル及びこれに近似した一又は複数の候補ベクトルの中から、対象ブロック２１４と最も相関性の高い候補ベクトルを抽出する。このようにして抽出された候補ベクトルが、当該対象ブロックの動きベクトルとして最終的に検出される。引き続いて、対象フレーム画像内に未処理の対象ブロックが残っている場合には、次に処理される対象ブロックが抽出されて同様の処理が繰り返して行われる。
【００５７】
（装置構成）
本実施の形態による動きベクトル検出装置の構成について、図１に示す機能ブロック図を参照しつつ説明する。図１に示す動きベクトル検出装置１は、対象フレーム画像が記憶される対象フレーム記憶部１１と、参照フレーム画像が記憶される参照フレーム記憶部１２とを有している。
【００５８】
対象フレーム記憶部１１には、動きベクトル検出装置１の外部から、動画像を構成する各フレームのうち符号化処理対象となるフレーム画像が順次供給される。そして、対象フレーム記憶部１１に記憶されたフレーム画像は、その処理が終了すると消去されるか又は参照フレーム記憶部１２へと送られ、そこに記憶される。参照フレーム記憶部１２には、対象フレーム記憶部１１又は動きベクトル検出装置１の外部から供給された、対象フレーム画像の直前のフレーム画像が参照フレーム画像として記憶される。参照フレーム記憶部１２には、直前のフレーム画像以外のフレーム画像が記憶されてもよいが、本実施の形態においては、対象フレーム画像の直前のフレーム画像だけが参照フレーム画像として参照フレーム記憶部１２に記憶されると仮定する。
【００５９】
動きベクトル検出装置１は、対象フレーム記憶部１１及び参照フレーム記憶部１２に加えて、トリプレットパターン記憶部１６及び候補ベクトル記憶部１７を有している。トリプレットパターン記憶部１６は、図５〜図１３に描かれた６８個のトリプレットパターン１１１〜１１９を記憶している。候補ベクトル記憶部１７は、図１４〜図２２に描かれた多数の候補ベクトルの終点位置を、各トリプレットパターン１１１〜１１９に関連させて記憶している。トリプレットパターン記憶部１６に記憶されたトリプレットパターン１１１〜１１９及び候補ベクトル記憶部１７に記憶された候補ベクトルの終点位置は、多くの種類の動画像に共通して高い信頼性で動きベクトルを検出可能となるように実験を繰り返すことによって選択されたものである。
【００６０】
また、動きベクトル検出装置１は、対象フレーム画像から対象ブロックを抽出する対象ブロック抽出部１３と、参照フレーム画像から参照ブロックを抽出する参照ブロック抽出部１４とを有している。対象ブロック抽出部１３は、図３５で説明したように、対象フレーム画像２１０を、それぞれが複数の画素２１１からなり且つ所定サイズ（例えば、８画素×８画素又は１６画素×１６画素、図３５では、１０画素×１０画素）を有する複数のブロック２１２に分割して、動きベクトル検出対象となる対象ブロック２１４を順次抽出する。
【００６１】
参照ブロック抽出部１４は、図３５で説明したように、参照フレーム画像２２０から、対象ブロック２１４と同じ大きさを有する参照ブロック２２２を抽出する。このとき抽出される参照ブロック２２２の代表点２２１は、抽出された対象ブロック２１４に関して参照フレーム画像２２０内に設けられた探索範囲２３２（図４参照）内にあって、しかも探索中心点２３４に対して点対称に分布している。参照ブロック２２２の抽出に当たっては、トリプレットパターン記憶部１６に記憶されたトリプレットパターンに包含された代表点２２１の位置や候補ベクトル記憶部１７に記憶された候補ベクトルの終点位置などが参照される。
【００６２】
さらに、動きベクトル検出装置１は、パターン抽出部１９と、候補ベクトル抽出部２１とを有している。パターン抽出部１９は、ＴＳＡＤ（Triplet SAD）値演算部１９ａと、ＴＳＡＤ値記憶部１９ｂと、トリプレットパターン決定部１９ｃとを有している。ＴＳＡＤ値演算部１９ａは、対象ブロック抽出部１３で抽出された対象ブロックについて、トリプレットパターン記憶部１６に記憶されたトリプレットパターンごとに、参照ブロック抽出部１４で抽出された参照ブロックを参照してＴＳＡＤ値を導出する。ＴＳＡＤ値の詳細については後述する。ＴＳＡＤ値演算部１９ａで導出されたＴＳＡＤ値は、ＴＳＡＤ値記憶部１９ｂに順次格納される。トリプレットパターン決定部１９ｃは、ＴＳＡＤ値記憶部１９ｂに６８個のＴＳＡＤ値が格納された後に、その中から最小のＴＳＡＤ値に係るトリプレットパターンを決定する。このようにして決定されたトリプレットパターンがパターン抽出部１９において抽出されたトリプレットパターンであり、当該トリプレットパターンの識別情報が探索制御部２２に供給される。
【００６３】
候補ベクトル抽出部２１は、ＳＡＤ値演算部２１ａと、ＳＡＤ値記憶部２１ｂと、候補ベクトル決定部２１ｃとを有している。ＳＡＤ値演算部２１ａは、対象ブロック抽出部１３で抽出された対象ブロックについて、パターン抽出部１９で抽出されたトリプレットパターンに関連して定められた複数の候補ベクトルの終点位置を代表点とする各参照ブロックに関するＳＡＤ値を導出する。ＳＡＤ値演算部２１ａで導出されたＳＡＤ値は、ＳＡＤ値記憶部２１ｂに順次格納される。候補ベクトル決定部２１ｃは、トリプレットパターンごとに定められた所定個のＳＡＤ値がＳＡＤ値記憶部２１ｂに格納された後に、その中から最小のＳＡＤ値に係る候補ベクトルを決定する。このようにして決定された候補ベクトルが候補ベクトル抽出部２１において抽出された候補ベクトルであり、当該候補ベクトルの識別情報が探索制御部２２に供給される。
【００６４】
さらに、候補ベクトル抽出部２１は、同様の処理をもう一度行う。つまり、候補ベクトル抽出部２１において、ＳＡＤ値演算部２１ａは、対象ブロック抽出部１３で抽出された対象ブロックについて、上述のようにして候補ベクトル抽出部２１で抽出された候補ベクトル及びこれに近似した４個の候補ベクトルの終点位置を代表点とする各参照ブロックに関するＳＡＤ値を導出する。ＳＡＤ値演算部２１ａで導出されたＳＡＤ値は、ＳＡＤ値記憶部２１ｂに順次格納される。候補ベクトル決定部２１ｃは、合計５個のＳＡＤ値がＳＡＤ値記憶部２１ｂに格納された後に、その中から最小のＳＡＤ値に係る候補ベクトルを決定する。
【００６５】
探索制御部２２は、パターン抽出部１９において抽出されたトリプレットパターンの識別情報をトリプレットパターン決定部１９ｃから受け取り、その識別情報を参照ブロック抽出部１４に供給する。参照ブロック抽出部１４は、探索制御部２２から識別情報が供給されたトリプレットパターンに関連して定められた各候補ベクトルの終点（図１４〜図２２参照）が代表点２２１の位置であり且つ対象ブロック２１４と同じ大きさを有する複数の参照ブロックを、参照フレーム画像２２０から抽出する。このとき、候補ベクトル記憶部１７に記憶された候補ベクトルの終点位置が参照される。
【００６６】
また、探索制御部２２は、候補ベクトル抽出部２１において抽出された候補ベクトルの識別情報を候補ベクトル決定部２１ｃから受け取り、その識別情報を参照ブロック抽出部１４に供給する。参照ブロック抽出部１４は、探索制御部２２から識別情報が供給された候補ベクトルの終点及びその上下左右に隣接した各画素が代表点の位置であり且つ対象ブロック２１４と同じ大きさを有する５個の参照ブロックを、参照フレーム画像２２０から抽出する。
【００６７】
動きベクトル検出装置１には、対象フレーム記憶部１１及び参照フレーム記憶部１２に記憶されたフレーム画像がどのような種類の動画像に係るものであるかを判定する画像種類判定部２５が含まれている。ここで画像の種類とは、動画像の特性から、動きベクトルの大きさや方向の類似度が高いとあらかじめ判断されたグループである。画像種類判定部２５は、一例として、動画像が「激しい動き」、「ゆっくりした動き」、「平均的な動き」の３つのうちのいずれの種類であるかを判定する。画像種類判定部２５における判定結果は、パターン変更部２６に与えられる。パターン変更部２６は、画像種類判定部２５における判定結果に基づいて、トリプレットパターン記憶部１６に記憶された６８個のトリプレットパターンのうちの少なくとも１つのトリプレットパターンの形状を変更する。また、パターン変更部２６は、形状が変更されたトリプレットパターンに係る候補ベクトル記憶部１７の記憶内容も併せて変更する。
【００６８】
図２は、図１に機能ブロック図として描かれた動きベクトル検出装置１の実際の装置構成の一例を描いた模式図である。図２において、ＣＰＵ（Central Processing Unit）３１は、対象ブロック抽出部１３、参照ブロック抽出部１４、ＴＳＡＤ値演算部１９ａ、トリプレットパターン決定部１９ｃ、ＳＡＤ値演算部２１ａ、候補ベクトル決定部２１ｃ、探索制御部２２、画像種類判定部２５、パターン変更部２６などとして機能する。一例としてＤＲＡＭ（Dynamic Random Access Memory）であるメモリ３２は、対象フレーム記憶部１１、参照フレーム記憶部１２、トリプレットパターン記憶部１６、候補ベクトル記憶部１７、ＴＳＡＤ値記憶部１９ｂ、ＳＡＤ値記憶部２１ｂ、動きベクトル記憶部２４などとして機能する。ハードディスク３３は、ＣＰＵ３１やメモリ３２を動きベクトル検出装置１として機能させるためのプログラムを含む各種のソフトウェアを格納している。つまり、これらのソフトウェア及びＣＰＵ３１などのハードウェアが組み合わされることによって、上述の各部１１〜２６が構築されている。一変形例として、メモリ３２の記憶内容の一部がＣＰＵ３１内の記憶部又はハードディスク３３に記憶されてもよい。さらに、ハードディスク３３に代えて、ハードディスク３３以外の不揮発性記憶装置（例えばＲＯＭ（Read Only Memory））を用いてもよい。また、図２に示す３つの部材３１〜３３は、必ずしも１つの筐体に収納されている必要はなく、２以上の筐体に分かれて収納されていてもよい。その場合、これら２以上の筐体がインターネットなどのネットワークによって接続されていてもよい。そのほか、図２に示した装置構成以外の構成を適宜採用することが可能である。
【００６９】
（動きベクトル検出手順）
次に、本実施の形態による動きベクトルの検出方法を、図３に示すフローチャートにしたがって説明する。前処理として、対象フレーム記憶部１１及び参照フレーム記憶部１２にそれぞれフレーム画像を記憶する。そして、記憶されたフレーム画像がどのような種類の動画像に係るものであるかを画像種類判定部２５によって判定する。そして、その結果に基づいて、トリプレットパターン記憶部１６に記憶された６８個のトリプレットパターンのうちの少なくとも１つのトリプレットパターンの形状を変更する。このとき、形状が変更されたトリプレットパターンに係る候補ベクトル記憶部１７の記憶内容も併せて変更する場合がある。
【００７０】
ステップＳ１では、図３５で説明したように、対象ブロック抽出部１３が、符号化対象フレーム画像２１０を、それぞれが複数の画素２１１からなり且つ所定サイズ（図３５では、１０画素×１０画素）を有する複数のブロック２１２に分割し、その中から動きベクトル検出対象となる対象ブロック２１４を抽出する。
【００７１】
次に、パターン抽出部１９が、図５〜図１３に示す６８個のトリプレットパターンの中から、対象ブロックと最も相関性の高いトリプレットパターンを抽出する。最初にその準備として、ステップＳ２において、参照ブロック抽出部１４が、対象ブロック抽出部１３で抽出された対象ブロックについて、対象ブロック２１４と同じ大きさを有する３個の参照ブロックを参照フレーム画像２２０から抽出する。これら３個の参照ブロックの代表点２２１は、図４に示すように、対象ブロック２１４に関して参照フレーム画像内に設けられた探索範囲２３２内に位置している。さらに、ステップＳ２で抽出された３個の参照ブロックに係る３つの代表点２２１は、６８個のトリプレットパターン１１１〜１１９のうちの共通の一つを構成している。本実施の形態において、６８個のトリプレットパターン１１１〜１１９は、合計２５個の代表点２２１によって構成されており、これらは探索中心点２３４に対して点対称に分布している。
【００７２】
ここで、探索領域２３２及びトリプレットパターン１１１〜１１９について、より詳細に説明する。探索領域２３２は、対象ブロック２１４を参照フレーム２２０内の同じ位置に配置したときの対象ブロック２１４の代表点２１３の位置（探索中心点）２３４を中心とした１４画素×１４画素の正方形領域である。本実施の形態において、ステップＳ２で抽出される参照ブロックの代表点２２１となり得るのは、探索中心点２３４及びこれを取り囲むように隣接した２画素×２画素の内側正方形の各頂点にある８点とからなる９点（符号２２１ａ）と、探索中心点２３４を中心とした６画素×６画素の中央正方形の各頂点及び各辺の中点とからなる８点（符号２２１ｂ）と、探索中心点２３４を中心とした１２画素×１２画素の外側正方形の各頂点及び各辺の中点とからなる８点（符号２２１ｃ）との合計２５点である。
【００７３】
探索範囲２３２には、これら２５個の代表点２２１ａ、２２１ｂ、２２１ｃから適宜選択された３点から構成されたトリプレットパターンが６８個定義されている。図５〜図１０、図１２及び図１３の各図に、トリプレットパターンを８個ずつ示し、図１１に４個のトリプレットパターンを示す。
【００７４】
図５に描かれた８個のトリプレットパターン１１１のそれぞれは、探索中心点２３４と、内側正方形の頂点に位置する１個の代表点２２１ａと、内側正方形の辺の中点に位置する１個の代表点２２１ａとを頂点とした直角二等辺三角形パターンである。図６に描かれた８個のトリプレットパターン１１２のそれぞれは、内側正方形の頂点に位置する１個の代表点２２１ａと、中央正方形の頂点に位置する１個の代表点２２１ｂと、中央正方形の辺の中点に位置する１個の代表点２２１ｂとを頂点とした三角形パターンである。図７に描かれた８個のトリプレットパターン１１３のそれぞれは、内側正方形の頂点に位置する１個の代表点２２１ａと、内側正方形の辺の中点に位置する１個の代表点２２１ａと、中央正方形の辺の中点に位置する１個の代表点２２１ｂとを頂点とした直角三角形パターンである。図８に描かれた８個のトリプレットパターン１１４のそれぞれは、中央正方形の頂点に位置する１個の代表点２２１ｂと、外側正方形の辺の中点に位置する１個の代表点２２１ｃと、外側正方形の頂点に位置する１個の代表点２２１ｃとを頂点とした直角二等辺三角形パターンである。図９に描かれた８個のトリプレットパターン１１５のそれぞれは、中央正方形の頂点に位置する１個の代表点２２１ｂと、中央正方形の辺の中点に位置する１個の代表点２２１ｂと、外側正方形の辺の中点に位置する１個の代表点２２１ｃとを頂点とした直角三角形パターンである。図１０に描かれた８個のトリプレットパターン１１６のそれぞれは、探索中心点２３４と、中央正方形の頂点に位置する１個の代表点２２１ｂと、中央正方形の辺の中点に位置する１個の代表点２２１ｂとを頂点とした直角二等辺三角形パターンである。図１１に描かれた４個のトリプレットパターン１１７のそれぞれは、探索中心点２３４と、中央正方形の隣接した辺の中点に位置する２個の代表点２２１ｂとを頂点とした直角二等辺三角形パターンである。図１２に描かれた８個のトリプレットパターン１１８のそれぞれは、１個の代表点２２１ａと、これに対応した位置にある１個の代表点２２１ｂと、これに対応した位置にある１個の代表点２２１ｃとを結ぶ放射状に延びた線分パターンである。図１３に描かれた８個のトリプレットパターン１１８のそれぞれは、探索中心点２３４と、１個の代表点２２１ａと、これに対応した位置にある１個の代表点２２１ｂとを結ぶ放射状に延びた線分パターンである。
【００７５】
続いて、ステップＳ３において、ＴＳＡＤ値演算部１９ａが、トリプレットパターンに関して定義された差分絶対値和の和（ＴＳＡＤ）をそれぞれ計算し、ＴＳＡＤ値記憶部１９ｂがその値を記憶する。ここで、各トリプレットパターンに関して差分絶対値和の和ＴＳＡＤは、以下の式（１）によって定義される。
ＴＳＡＤ＝ＳＡＤv1＋ＳＡＤv2＋ＳＡＤv3      （１）
【００７６】
式（１）において、ｖ１、ｖ２、ｖ３は、各トリプレットパターンに関連した３つの代表点２２１と探索中心点２３４とを結ぶベクトル（候補ベクトル）を意味している。すなわち、ＳＡＤv1、ＳＡＤv2、ＳＡＤv3は、対象ブロックの画素値（具体的には演算量を低減させるために輝度値のみ）と、候補ベクトルがそれぞれｖ１、ｖ２、ｖ３のときの参照ブロックの画素値との差分の絶対値をブロック内のすべての画素について足し合わせた値である。続いて、ステップＳ４において、トリプレットパターン決定部１９ｃが、６８個すべてのＴＳＡＤ値の算出が終了したか否かを判断し、終了していなければ（Ｓ４：ＮＯ）、ステップＳ２に戻る。終了していれば（Ｓ４：ＹＥＳ）、ステップＳ５に進む。
【００７７】
ステップＳ５では、トリプレットパターン決定部１９ｃが、算出された６８個の中の最小ＴＳＡＤ値に係るトリプレットパターンを抽出する。上記のように定義されたＴＳＡＤが最小となるトリプレットパターンは、上述した６８個のトリプレットパターンの中で、対象ブロックと最も相関性が高いトリプレットパターンであるといえる。図４に示す例では、６８個のトリプレットパターンの中から図８に示すトリプレットパターン１１４（図４において、その３つの頂点を黒四角で示す）が、対象ブロックと最も相関性の高いトリプレットパターンとして抽出されている。
【００７８】
次に、候補ベクトル抽出部２１が、上記のようにして抽出されたトリプレットパターンに関連して定められた複数の候補ベクトルの中から、対象ブロックと最も相関性の高い候補ベクトルを抽出する。図１４〜図２２に、図５〜図１３にそれぞれ描かれた複数のトリプレットパターンのうちの１つに関連して定められた複数の候補ベクトルの終点位置を示す。
【００７９】
例えば、図１４には、図５に描かれた１つのトリプレットパターン１１１に関連して定められたものとして、６個の候補ベクトルの終点位置が描かれている。その内訳は、図５に示す１つのトリプレットパターン１１１の頂点を構成する３個の点（黒四角で示す）と、これら３点のうちで内側正方形の頂点及び辺の中点に位置する２個の代表点２２１ａを結ぶ方向と平行に配列され且つこれら２個の代表点２２１ａの外側に隣接した３個の点（三角で示す）とである。図５に示された他の７つのトリプレットパターン１１１に関連して定められた６個の候補ベクトルの終点位置については、図１４に示された６個の終点位置から対称性により明らかであるため、図示及び説明を省略する。また、図１５〜図２２に示す終点位置についても、上記の説明及び対応するトリプレットパターンの形状を考慮すると明らかであるため、詳細な説明を省略する。
【００８０】
抽出したトリプレットパターンに関連して定められた複数の候補ベクトルの中から、対象ブロックと最も相関性の高い候補ベクトルを抽出するために、最初にその準備として、参照ブロック抽出部１４が、ステップＳ６において、参照フレーム画像２２０から、１つの参照ブロックを抽出する。ここで抽出される参照ブロックの代表点２２１は、抽出されたトリプレットパターンに関連して定められた複数の候補ベクトルの中のいずれか１つの候補ベクトルの終点（図１４〜図２２参照）に位置している。しかも、抽出される参照ブロックは、対象ブロックと同じ大きさを有している。図４に示す例では、最初に抽出されたトリプレットパターン１１４に関連して定められた１０個の候補ベクトル（図１４参照）に関連した１０個の参照ブロックの中のいずれか１つが抽出されている。
【００８１】
続いて、ＳＡＤ値演算部２１ａが、ステップＳ７において、対象ブロックの画素値（輝度値）と、ステップＳ６で抽出された参照ブロックの画素値との差分の絶対値をブロック内のすべての画素について足し合わせた値（差分絶対値和ＳＡＤ）を算出し、ＳＡＤ値記憶部２１ｂがその値を記憶する。そして、候補ベクトル決定部２１ｃが、ステップＳ５で抽出されたトリプレットパターンに関連したすべての参照ブロックについてＳＡＤ値の算出が終了したか否かをステップＳ８において判断し、終了していなければ（Ｓ８：ＮＯ）、ステップＳ６に戻る。終了していれば（Ｓ８：ＹＥＳ）、ステップＳ９に進む。
【００８２】
ステップＳ９では、候補ベクトル決定部２１ｃが、算出されたすべてのＳＡＤ値の中の最小ＳＡＤ値に係る参照ブロックに対応した候補ベクトルを抽出する。このようにして抽出された候補ベクトルは、最初に抽出されたトリプレットパターンに関連して定められた複数の候補ベクトルの中で、対象ブロックと最も相関性の高い候補ベクトルであるといえる。図４に示す例では、最初に抽出されたトリプレットパターン１１４に関連して定められた１０個の候補ベクトル（図１４参照）の中から、トリプレットパターン１１４の重心に近い位置を終点とした候補ベクトル１０８が抽出されている。
【００８３】
次に、候補ベクトル抽出部２１が、上記のようにして抽出された候補ベクトル、及び、当該抽出された候補ベクトルに近似した一又は複数の候補ベクトルの中から、対象ブロックと最も相関性の高い候補ベクトルを抽出する。具体的には、上記のようにして抽出された候補ベクトル、及び、この候補ベクトルの終点の上下左右に隣接した各画素を終点とした４つの候補ベクトルの合計５個の候補ベクトルの中から、対象ブロックと最も相関性の高い候補ベクトルを抽出する。
【００８４】
最初にその準備として、ステップＳ１０において、参照ブロック抽出部１４が、参照フレーム画像２２０から１個の参照ブロックを抽出する。ここで抽出される参照ブロックの代表点２２１は、ステップＳ９で抽出された候補ベクトルの終点位置（図１４〜図２２参照）及びその上下左右に隣接した４画素の位置のうちのどこかにある。しかも、抽出される参照ブロックは、対象ブロックと同じ大きさを有している。図４に示す例では、ステップＳ９で抽出された候補ベクトル１０８の終点及びその上下左右に隣接した４個の画素のいずれかを代表点とした５個の参照ブロックのうちのいずれかが抽出される。
【００８５】
続いて、ＳＡＤ値演算部２１ａが、ステップＳ１１において、対象ブロックの画素値（輝度値のみ）と、ステップＳ１０で抽出された参照ブロックの画素値との差分の絶対値をブロック内のすべての画素について足し合わせた値（差分絶対値和ＳＡＤ）を算出し、ＳＡＤ値記憶部２１ｂがその値を記憶する。そして、候補ベクトル決定部２１ｃが、ステップＳ９で抽出された候補ベクトルに関連した５個の参照ブロックについてＳＡＤ値の算出が終了したか否かをステップＳ１２において判断し、終了していなければ（Ｓ１２：ＮＯ）、ステップＳ１０に戻る。終了していれば（Ｓ１２：ＹＥＳ）、ステップＳ１３に進む。
【００８６】
ステップＳ１３では、候補ベクトル決定部２１ｃが、算出された５個のＳＡＤ値の中の最小ＳＡＤ値に係る参照ブロックに対応した候補ベクトルを抽出する。このようにして抽出された候補ベクトルは、ステップＳ９で抽出された候補ベクトル及びこれに近似した４個の候補ベクトルの合計５個の候補ベクトルの中で、対象ブロックと最も相関性の高い候補ベクトルであるといえる。図４に示す例では、最初に抽出された候補ベクトル１０８及びこれに近似した４個の候補ベクトルの合計５個の候補ベクトルの中から、候補ベクトル１０８の終点の右側に隣接した画素の位置を終点とした候補ベクトル１０９が抽出されている。そして、本実施の形態では、この候補ベクトル１０９が最終的な動きベクトルとして検出される。
【００８７】
以上説明した本実施の形態によると、探索範囲２３２内から最初に一次元パターン又は二次元パターンであるトリプレットパターン１１１〜１１９が抽出されるので、図３７で説明したＴＳＳ法のように最初に点が抽出される場合と比較して、より画像の実際の動きに即した複数の候補ベクトルの中から１つの候補ベクトルをステップＳ９において抽出することが可能となる。したがって、ステップＳ９で抽出される候補ベクトルが理想的な動きベクトルに近い信頼性の高いものである確率が高くなり、ステップＳ１３で抽出される候補ベクトルが理想的な動きベクトルにさらに近い信頼性の高いものである確率が高くなる。よって、Ｈ．２６４の多フレーム間予測において直前フレームの動きベクトル検出の信頼性が極めて高くなるため、直前フレーム以外の参照フレームに対しては直前フレームで検出した動きベクトルを中心とした狭い探索範囲を設定したとしても、十分な信頼性で動きベクトルを検出することが可能となる。同様に、Ｈ．２６４のサブピクセル精度の動きベクトル検出において整数ピクセル精度での動きベクトル検出精度が高くなるために、サブピクセル精度での動きベクトル検出の信頼性も向上する。しかも、フルサーチが行われる場合と比較して、演算量を少なくすることができる。
【００８８】
また、本実施の形態では、図４に示す２５個の代表点２２１からそれよりも多い６８個のトリプレットパターンが構成されているので、２５個の代表点２２１から２５個以下のトリプレットパターンが構成されている場合と比較して、ステップＳ５で抽出されるトリプレットパターンとしてより好適なトリプレットパターンを抽出することが可能である。
【００８９】
しかも、本実施の形態では、図５〜図１３に示すトリプレットパターン１１１〜１１９に互いに部分的に重なり合っているものがある。例えば、図３に示すトリプレットパターン１１２は、図１０に示すトリプレットパターン１１６、及び、図１１に示すトリプレットパターン１１７と一部において重なっている。これによると、ステップＳ５で適切でないトリプレットパターンが抽出されたとしても、ステップＳ９の候補ベクトル抽出でのリカバリーが可能となって、動きベクトルをさらに信頼性高く検出することが可能である。
【００９０】
さらに、本実施の形態では、画像種類判定部２５によって処理する動画像の種類を判定し、その判定結果に基づいてトリプレットパターン記憶部１６に記憶されたトリプレットパターンの形状を変更するので、動画像の種類に応じた形状のパターンを用いることが可能となるため、動きベクトルをさらに信頼性高く検出することが可能である。
【００９１】
加えて、本実施の形態では、候補ベクトル記憶部１７がトリプレットパターン記憶部１６に記憶されたトリプレットパターンに関連して複数の候補ベクトルを記憶しているので、候補ベクトル抽出部２１がステップＳ９において候補ベクトルを抽出する際に、各トリプレットパターンに適した複数の候補ベクトルをあらかじめ用意しておくことができるので、動きベクトルをさらに信頼性高く検出することが可能である。
【００９２】
＜実施の形態２＞
次に、本発明の実施の形態２について説明する。本実施の形態は、実施の形態１におけるステップＳ２からステップＳ５までの代替手順に関するものであって、対象フレーム画像内において対象ブロックの周辺にある複数のブロックにそれぞれ係る既知である複数の動きベクトル（本明細書において、「周辺動きベクトル」と称することがある）を利用してトリプレットパターンをより少ない演算量で抽出することを可能とするものである。
【００９３】
通常、対象フレーム画像内においては、最も左上にあるブロックから始まって同じ水平ライン内にあるブロックを右へと動きベクトルを検出して行き、順次下のラインにあるブロックの動きベクトルを同様に検出して行く。したがって、図２３に示すように、対象フレーム画像内において対象ブロック２１４の上、右上、左に隣接する３つのブロック２１２ａ、２１２ｂ、２１２ｃの動きベクトルＭＶ１、ＭＶ２、ＭＶ３は、対象ブロック２１４の動きベクトルＭＶを検出しようとする際には検出済みであって既知となっている。
【００９４】
本実施の形態による動きベクトル検出装置の構成について、図２４に示す機能ブロック図を参照しつつ説明する。なお、図２４に描かれた部材のうち図１と同じ部材については同じ符号を付してその説明を省略する。また、図２４において、候補ベクトル抽出部２１、探索制御部２２、動きベクトル記憶部２４、画像種類判定部２５及びパターン変更部２６の図示を省略している。図２４に示す動きベクトル検出装置４０は、実施の形態１に係る動きベクトル検出装置１が有する各機能部１１〜２６に加えて、周辺動きベクトル記憶部４１、トリプレットパターン作成部４２、トリプレットパターン選択部４３、及び、閾値記憶部４４を有している。
【００９５】
周辺動きベクトル記憶部４１は、対象ブロック２１４に対して図２３に示すような位置関係にある３つのブロックの動きベクトル（周辺動きベクトル）ＭＶ１、ＭＶ２、ＭＶ３を記憶する。トリプレットパターン作成部４２は、周辺動きベクトル記憶部４１に記憶された３つの周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３の終点を頂点とした付加トリプレットパターンＴＰ（図２６参照）を作成する。トリプレットパターン作成部４２が作成した付加トリプレットパターンＴＰは、元の６８個のトリプレットパターンと共にトリプレットパターン記憶部１６に記憶される。閾値記憶部４４は、トリプレットパターン決定部１９ｃが決定したトリプレットパターンに係るＴＳＡＤ値と比較される所定の閾値ｔｈαを記憶する。
【００９６】
トリプレットパターン選択部４３は、トリプレットパターン記憶部１６の記憶内容に基づいて、元の６８個のトリプレットパターンの中からトリプレットパターン作成部４２が作成した付加トリプレットパターンＴＰと少なくとも一部において重なるもの、及び、付加トリプレットパターンＴＰそのものを選択する。言い換えると、トリプレットパターン選択部４３は、付加トリプレットパターンＴＰ及び図５〜図１３に示す６８個のトリプレットパターンの合計６９個のトリプレットパターンに、選択されたものが早い優先順位となり且つ選択されないものが遅い優先順位となるように優先順位を割り付ける優先順位割付手段である。この点については、後で詳述する。
【００９７】
次に、本実施の形態による動きベクトルの検出方法を、図２５に示すフローチャートにしたがって説明する。ステップＳ１までの処理とステップＳ６以降の処理とは図３で説明したものと同様であるため、ここではその間の処理だけを説明する。また、本実施の形態では、前処理として、実施の形態１で説明したものに加えて、周辺動きベクトル記憶部４１に３つの周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３を記憶させておき、閾値記憶部４４に閾値ｔｈαを記憶させておく。
【００９８】
まず、ステップＳ２１では、図４と同様の探索範囲２３２が描かれた図２６に示すように、付加トリプレットパターン作成部４２が、周辺動きベクトル記憶部４１に記憶された３つの周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３の始点を同じとしたときにこれらの終点を結ぶ付加トリプレットパターンＴＰを作成する。作成された付加トリプレットパターンＴＰは、トリプレットパターン記憶部１６に記憶される。
【００９９】
続いて、ステップＳ２２において、トリプレットパターン選択部４３が、トリプレットパターン記憶部１６の記憶内容に基づいて、元の６８個のトリプレットパターンの中からトリプレットパターン作成部４２が作成した付加トリプレットパターンＴＰと少なくとも一部において重なるもの、及び、付加トリプレットパターンＴＰそのものを選択する。例えば、付加トリプレットパターンＴＰが図２６に示すようなものである場合、図５〜図１３に示す６８個のトリプレットパターンの中から、図８に示す２つのトリプレットパターン１１４と、図１２に示す１つのトリプレットパターン１１８とが選択されると共に、付加トリプレットパターンＴＰが選択される。したがって、この場合、トリプレットパターン選択部４３は、選択された４個のトリプレットパターンに優先順位”１”を、残りのトリプレットパターンに優先順位”２”を割り付けたことになる。
【０１００】
次に、パターン抽出部１９が、付加トリプレットパターンＴＰ及び図５〜図１３に示す６８個のトリプレットパターンの合計６９個のトリプレットパターンの中から、対象ブロックと最も相関性の高いトリプレットパターンを抽出する。最初にその準備として、ステップＳ２３において、参照ブロック抽出部１４が、トリプレットパターン選択部４３が選択したトリプレットパターンごとに、トリプレットパターンを構成する３個の代表点を代表点とした参照ブロックを参照フレーム画像２２０から３個ずつ抽出する。これら参照ブロックは、対象ブロック２１４と同じ大きさを有しており、その代表点２２１は、図４に示すように、対象ブロック２１４に関して参照フレーム画像内に設けられた探索範囲２３２内に位置している。さらに、ＴＳＡＤ値演算部１９ａが、このように抽出された参照ブロックを３個ずつ参照して、トリプレットパターン選択部４３が選択した各トリプレットパターンに関して定義された差分絶対値和の和（ＴＳＡＤ）を式（１）に基づいてそれぞれ計算し、ＴＳＡＤ値記憶部１９ｂがその値を記憶する。
【０１０１】
トリプレットパターン選択部４３が選択した複数のトリプレットパターンに関するＴＳＡＤ値の算出がすべて終了すると、続いて、ステップＳ２４において、トリプレットパターン決定部１９ｃが、算出された複数のトリプレットパターンの中の最小ＴＳＡＤ値に係るトリプレットパターンを決定する。
【０１０２】
ステップＳ２５では、トリプレットパターン決定部１９ｃが、ステップＳ２４で決定されたトリプレットパターンに係るＴＳＡＤ値（最小ＴＳＡＤ値）が閾値記憶部４４に記憶された閾値ｔｈα未満か否かを判断する。最小ＴＳＡＤ値が閾値ｔｈα以上であると判断されると（Ｓ２５：ＹＥＳ）、トリプレットパターン選択部４３が選択したもの以外のトリプレットパターンについてはＴＳＡＤ値を計算することなくステップＳ２６に進む。
【０１０３】
一方、最小ＴＳＡＤ値が閾値ｔｈα未満であると判断されると（Ｓ２５：ＮＯ）、ステップＳ２７の処理に移行する。ステップＳ２７では、参照ブロック抽出部１４が、トリプレットパターン記憶部１６に記憶されたトリプレットパターンごとに、トリプレットパターンを構成する３個の代表点を代表点とした参照ブロックを参照フレーム画像２２０から３個ずつ抽出する。さらに、ＴＳＡＤ値演算部１９ａが、このように抽出された参照ブロックを３個ずつ参照して、トリプレットパターン記憶部１６に記憶された６９個の各トリプレットパターンに関して定義された差分絶対値和の和（ＴＳＡＤ）を式（１）に基づいてそれぞれ計算し、ＴＳＡＤ値記憶部１９ｂがその値を記憶する。続いて、ステップＳ２８において、トリプレットパターン決定部１９ｃが、算出された６９個のトリプレットパターンの中の最小ＴＳＡＤ値に係るトリプレットパターンを決定し、ステップＳ２６に進む。ステップＳ２６では、トリプレットパターン決定部１９ｃが、ステップＳ２４又はステップＳ２８で決定されたトリプレットパターンを、合計６９個のトリプレットパターンの中で対象ブロックと最も相関性が高いトリプレットパターンとして抽出する。その後、図３のステップＳ６に進んで、上述したのと同様の処理を行う。
【０１０４】
以上説明した本実施の形態によると、実施の形態１と同様の利点が得られる。しかも、トリプレットパターンに優先順位を割り付け、優先順位の早いトリプレットパターンが所定条件を満たせば、パターン抽出部１９が優先順位の遅いトリプレットパターンの探索を行わないようにしているために、パターン抽出部１９におけるトリプレットパターンの抽出を少ない演算量にて行うことが可能である。
【０１０５】
また、対象ブロックはその周辺にあるブロックの動きベクトルに近似した動きベクトルを有することが多いと考えられるので、トリプレットパターン選択部４３によって選択されるトリプレットパターンは、パターン抽出部１９において抽出される可能性が高いといえる。したがって、さらなる演算量の低減を実現することができる。また、パターン抽出部１９によって抽出され得るパターン数が実施の形態１よりも１個だけ増えて６９個となっているので、トリプレットパターンとしてより好適なトリプレットパターンを抽出することが可能である。
【０１０６】
＜実施の形態２の変形例＞
ここで、上述した実施の形態２の変形例について説明する。本変形例では、図２５に示すステップＳ２５、ステップＳ２７及びステップＳ２８の処理を行わない。したがって、ステップＳ２４で最小ＴＳＡＤ値を有するとして決定されたトリプレットパターンを、ステップＳ２６において抽出する。つまり、トリプレットパターン選択部４３は、６９個のトリプレットパターンに優先順位を割り付けるのではなく、これら６９個のトリプレットパターンの中から、探索すべき２以上のトリプレットパターンを選択するのである。この変形例によると、３つの周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３を参照することによってＴＳＡＤ値が算出されるトリプレットパターンの数を削減することができるので、さらに演算量の低減を図ることが可能となる。
【０１０７】
＜実施の形態３＞
次に、本発明の実施の形態３について説明する。本実施の形態は、実施の形態２で説明した周辺動きベクトルと、探索範囲内に定められた同心状で正方形の３つのリングとを用いて、より少ない演算量で動きベクトルが検出できるようにするものである。
【０１０８】
最初に、本実施の形態で用いる３つのリングについて、図２７を参照して説明する。図２７に示す探索範囲２３２内には、探索中心点２３４を中心として同心状に正方形の３つのリング１３１、１３２、１３３が描かれている。内側リング１３１は、探索中心点２３４に隣接した８個の代表点２２１ａを結んだものである。中央リング１３２は、８個の代表点２２１ｂを結んだものである。外側リング１３３は、８個の代表点２２１ｃを結んだものである。
【０１０９】
各リング１３１、１３２、１３３には、図５〜図１３に描かれた６８個のトリプレットパターン１１１〜１１９のうちの２個以上が関連づけられている。言い換えると、リング１３３とリング１３２との間、リング１３２とリング１３１との間、リング１３１の内側の各領域は、６８個のトリプレットパターン１１１〜１１９のうちの２個以上と少なくとも一部において重なり合っている。具体的には、リング１３３とリング１３２との間の領域は、図８に示すトリプレットパターン１１４、図９に示すトリプレットパターン１１５、図１２に示すトリプレットパターン１１８とそれぞれ少なくとも一部において重なり合っている。リング１３２とリング１３１との間の領域は、図６に示すトリプレットパターン１１２、図７に示すトリプレットパターン１１３、図１０に示すトリプレットパターン１１６、図１１に示すトリプレットパターン１１７、図１２に示すトリプレットパターン１１８、図１３に示すトリプレットパターン１１９とそれぞれ少なくとも一部において重なり合っている。そして、リング１３１の内側の領域は、図５に示すトリプレットパターン１１１、図１０に示すトリプレットパターン１１６、図１１に示すトリプレットパターン１１７、図１３に示すトリプレットパターン１１９とそれぞれ少なくとも一部において重なり合っている。本実施の形態では、以下に詳細を述べるように、周辺動きベクトルを利用することによって、３つのリング１３１、１３２、１３３の中から探索すべき一又は複数のリングを選択し、選択されたリング１３１、１３２、１３３に関連づけられた複数のトリプレットパターンの中から、対象ブロックと最も相関性の高いトリプレットパターンを抽出する。
【０１１０】
次に、本実施の形態による動きベクトル検出装置の構成について、図２８に示す機能ブロック図を参照しつつ説明する。なお、図２８に描かれた部材のうち図１と同じ部材については同じ符号を付してその説明を省略する。また、図２８において、画像種類判定部２５及びパターン変更部２６の図示を省略している。図２８に示す動きベクトル検出装置５０は、実施の形態１に係る動きベクトル検出装置１が有する各機能部１１〜２６に加えて、周辺動きベクトル記憶部５１、参照動きベクトル演算部５２、探索範囲変更部５３、評価値演算部５４、及び、探索条件決定部５５を有している。
【０１１１】
周辺動きベクトル記憶部５１は、対象ブロック２１４に対して図２３に示すような位置関係にある３つのブロックの動きベクトル（周辺動きベクトル）ＭＶ１、ＭＶ２、ＭＶ３を記憶する。参照動きベクトル演算部５２は、周辺動きベクトル記憶部５１に記憶された周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３の中間値ベクトルＭＶｐ（参照動きベクトル）を導出する。ここで、ＭＶ１＝（mv1x, mv1y）、ＭＶ２＝（mv2x, mv2y）、ＭＶ３＝（mv3x, mv3y）と表記すると、中間値ベクトルＭＶｐ＝intermidia｛ＭＶ１，ＭＶ２，ＭＶ３｝＝（MVpx, MVpy）は、以下の式（２）、（３）のように定義される。
MVpx＝mv1x + mv2x + mv3x - min(mv1x, mv2x, mv3x) - max(mv1x, mv2x, mv3x)  （２）
MVpy＝mv1y + mv2y + mv3y - min(mv1y, mv2y, mv3y) - max(mv1y, mv2y, mv3y)  （３）
【０１１２】
探索範囲変更部５３は、参照フレーム画像内の探索範囲２３２を中間値ベクトルＭＶｐ＝（MVpx, MVpy）だけシフトする。このことは、対象ブロックの動きベクトルが周辺動きベクトルに近いということを仮定すると、検出される動きベクトルがリング１付近を終点位置とする比較的小さなベクトルになる可能性が高くなることを意味する。
【０１１３】
評価値演算部５４は、周辺動きベクトル記憶部５１に記憶された周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３、及び、参照動きベクトル演算部５２が導出した中間値ベクトルＭＶｐに基づいて、
（ａ）中間値ベクトルＭＶｐのｘｙ各成分の絶対値（abs[MVpx], abs[MVpy]）、
（ｂ）周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３の評価差分（mvpx, mvpy）＝ (max(mv1x, mv2x, mv3x) - min(mv1x, mv2x, mv3x), max(mv1y, mv2y, mv3y) - min(mv1y, mv2y, mv3y))、及び、
（ｃ）参照フレーム画像２２０内の探索範囲２３２を中間値ベクトルＭＶｐ分だけシフトした後の探索中心点２３４におけるＳＡＤ値を対象ブロックの画素数で割った商である平均コストcost：Ｈ．２６４のようにブロック内の画素数が変化し得る場合には画素数に依存しない平均コストを算出するのが有効であるが、画素数が一定の場合にはＳＡＤ値を算出してもよい）、
をそれぞれ算出する。
【０１１４】
探索条件決定部５５は、評価値演算部５４が算出した絶対値、評価差分及び平均コストなどに基づいて、探索条件を決定する。ここで、探索条件とは、どのリングを探索するかということと、図３のステップＳ９に相当する段階及びステップＳ１３に相当する段階のどちらの段階で動きベクトルの検出を終了するかということである。
【０１１５】
次に、本実施の形態による動きベクトルの検出方法を、図２９に示すフローチャートにしたがって説明する。本実施の形態では、前処理として、実施の形態１で説明したものに加えて、周辺動きベクトル記憶部４１に３つの周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３を記憶させておき、探索条件決定部５５にいくつかの閾値ｔｈを含む判断条件を記憶させておく。
【０１１６】
まず、実施の形態１のステップＳ１と同様に対象ブロック抽出部１３が対象ブロック２１４を抽出した後、ステップＳ３１において、参照動きベクトル演算部５２が、周辺動きベクトル記憶部５１に記憶された周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３の中間値ベクトルＭＶｐを導出する。導出された中間値ベクトルＭＶｐは、探索制御部２２、探索範囲変更部５３及び評価値演算部５４に与えられる。
【０１１７】
続いて、ステップＳ３２において、探索範囲変更部５３が、参照フレーム画像内の探索範囲２３２を中間値ベクトルＭＶｐ＝（MVpx, MVpy）だけシフトするような制御信号を探索制御部２２に供給する。
【０１１８】
次に、ステップＳ３３において、評価値演算部５４が、周辺動きベクトル記憶部５１に記憶された周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３及び参照動きベクトル演算部５２が導出した中間値ベクトルＭＶｐに基づいて、上記（ａ）、（ｂ）、（ｃ）の値を算出する。算出された値は、探索条件決定部５５に与えられる。さらに、探索条件決定部５５は、評価値演算部５４が算出した絶対値、評価差分及び平均コストなどに基づいて、探索条件を決定する。ここで、探索条件決定部５５での処理について、図３０を参照してより詳細に説明する。
【０１１９】
まず、ステップＳ３３１では、上述したように、探索条件決定部５５は、上記（ａ）、（ｂ）、（ｃ）の値を算出する。次に、ステップＳ３３２において、探索条件決定部５５は、評価差分（mvpx, mvpy）が０であり、なおかつ、絶対値（abs[MVpx], abs[MVpy]）が閾値ｔｈaより小さい又は平均コストcostが閾値ｔｈbより小さいという条件が満たされるかどうかを判断する。この条件は、以下の式（４）によって表される。
（mvpx ＝ mvpy ＝ ０）  ａｎｄ   [｛（abs[MVpx] ＜ｔｈa）ａｎｄ（abs[MVpy]＜ｔｈa）] ｏｒ｛cost＜ｔｈb｝]      （４）
【０１２０】
式（４）を満たす場合（Ｓ３３２：ＹＥＳ）、動きベクトルがシフト後の探索中心点２３４にある可能性が高いので、ステップＳ３３３において、探索条件決定部５５は、中間値ベクトルＭＶｐを動きベクトルに決定する。ここで閾値ｔｈa、ｔｈbは、誤判断を最小限とするために、非常に小さい値としている。
【０１２１】
式（４）を満たさない場合（Ｓ３３２：ＮＯ）、ステップＳ３３４の処理に移行する。ステップＳ３３４において、探索条件決定部５５は、評価差分（mvpx, mvpy）が０ではなく、なおかつ、平均コストcostが閾値ｔｈbより小さいという条件が満たされるかどうかを判断する。この条件は、以下の式（５）によって表される。
（mvpx ＝ mvpy ≠ ０）  ａｎｄ （cost＜ｔｈb）    （５）
【０１２２】
式（５）を満たす場合（Ｓ３３４：ＹＥＳ）、動きベクトルがシフト後の探索中心点２３４の近傍にある可能性が高いので、ステップＳ３３５において、探索条件決定部５５は、内側リング１３１に含まれる９個の代表点２２１ａをそれぞれ代表点とする参照ブロックだけについてＳＡＤ値を算出し、その中で最小のＳＡＤ値に係る代表点２２１ａを終点位置とするベクトルを動きベクトルとする旨を決定する。
【０１２３】
式（５）を満たさない場合（Ｓ３３４：ＮＯ）、ステップＳ３３６の処理に移行する。ステップＳ３３６において、探索条件決定部５５は、評価差分（mvpx, mvpy）が０であり、なおかつ、絶対値（abs[MVpx], abs[MVpy]）が閾値ｔｈa以上で同時に平均コストcostが閾値ｔｈb以上という条件が満たされるかどうかを判断する。この条件は、以下の式（６）によって表される。
（mvpx ＝ mvpy ＝ ０）  ａｎｄ   [｛（abs[MVpx] ≧ｔｈa）ａｎｄ（abs[MVpy]≧ｔｈa）] ａｎｄ｛cost≧ｔｈb｝]      （６）
【０１２４】
式（６）を満たす場合（Ｓ３３６：ＹＥＳ）、動きベクトルがシフト後の探索中心点２３４の近傍にある可能性が非常に高いので、ステップＳ３３７において、探索条件決定部５５は、内側リング１３１を探索すべきリングとして選択する（つまり、中央リング１３２及び外側リング１３３を探索しない）と共に、動きベクトル検出を図３のステップＳ９に相当する段階までで終了する旨を決定する。
【０１２５】
式（６）を満たさない場合（Ｓ３３６：ＮＯ）、ステップＳ３３８の処理に移行する。ステップＳ３３８において、探索条件決定部５５は、評価差分（mvpx, mvpy）が０より大きく閾値ｔｈc未満という条件が満たされるかどうかを判断する。この条件は、以下の式（７）によって表される。
（０＜mvpx＜ｔｈc）ａｎｄ（０＜ mvpy ＜ｔｈc）      （７）
【０１２６】
式（７）を満たす場合（Ｓ３３８：ＹＥＳ）、動きベクトルがシフト後の探索中心点２３４の近傍にある可能性がやや高いので、ステップＳ３３９において、探索条件決定部５５は、内側リング１３１を探索すべきリングとして選択すると共に、動きベクトル検出を図３のステップＳ１３に相当する段階まで行う旨を決定する。
【０１２７】
式（７）を満たさない場合（Ｓ３３８：ＮＯ）、ステップＳ３４０の処理に移行する。ステップＳ３４０において、探索条件決定部５５は、参照フレーム画像２２０（ref）が直前フレーム画像よりも前のフレーム画像（直前フレーム画像を含まない）であって、なおかつ、平均コストcostが閾値ｔｈb未満という条件が満たされるかどうかを判断する。この条件は、以下の式（８）によって表される。
（ref ＞０）  ａｎｄ  （cost＜ｔｈb）    （８）
【０１２８】
式（８）を満たす場合（Ｓ３４０：ＹＥＳ）、ステップＳ３３４との比較から明らかなように評価差分が０であり、検出対象である動画像は同じフレーム画像が繰り返される動画像（繰り返し画像）である可能性が高いと考えられる。したがって、動きベクトルがシフト後の探索中心点２３４にある可能性が高いので、ステップＳ３４１において、探索条件決定部５５は、中間値ベクトルＭＶｐを動きベクトルに決定する。
【０１２９】
式（８）を満たさない場合（Ｓ３４０：ＮＯ）、ステップＳ３４２の処理に移行する。ステップＳ３４２において、探索条件決定部５５は、評価差分（mvpx, mvpy）が内側リング１３１と中央リング１３２との距離Ｌ未満であり、なおかつ、平均コストcostが閾値ｔｈd未満という条件が満たされるかどうかを判断する。この条件は、ｔｈLを距離Ｌに相当する閾値とすると、以下の式（９）によって表される。
｛（mvpx＜ｔｈL）ａｎｄ（mvpy ＜ｔｈL）｝ａｎｄ（cost＜ｔｈd）  （９）
【０１３０】
式（９）を満たす場合（Ｓ３４２：ＹＥＳ）、動きベクトルの終点がシフト後の探索範囲２３２の外側リング１３３よりも内側に位置する可能性が高いので、ステップＳ３４３において、探索条件決定部５５は、内側リング１３１及び中央リング１３２を探索すべきリングとして選択する（つまり、外側リング１３３を探索しない）と共に、動きベクトル検出を図３のステップＳ１３に相当する段階まで行う旨を決定する。
【０１３１】
式（９）を満たさない場合（Ｓ３４２：ＮＯ）、動きベクトルの終点がシフト後の探索範囲２３２のどこにある可能性が高いかを限定せずに、ステップＳ３４４において、探索条件決定部５５は、すべてのリング１３１、１３２、１３３を探索すべきリングとして選択すると共に、動きベクトル検出を図３のステップＳ１３に相当する段階まで行う旨を決定する。
【０１３２】
ステップＳ３３３、３３５、３３７、３３９、３４１、３４３、３４４のいずれかが終了すると、図２９のステップＳ３４に進む。ステップＳ３４では、ステップＳ３３の探索条件決定処理において、動きベクトルが既に決定されているかどうかを判断する。具体的には、ステップＳ３３２又はステップＳ３４０において、式（４）又は式（８）の条件を満たしたと判断された場合に、ステップＳ３３３又はステップＳ３４１において動きベクトルが中間値ベクトルＭＶｐであると既に決定されているので（Ｓ３４：ＹＥＳ）、ステップＳ３５をスキップして動きベクトル検出処理を終了する。
【０１３３】
一方、動きベクトルが決定されていない場合には（Ｓ３４：ＮＯ）、ステップＳ３５に進む。ステップＳ３５では、ステップＳ３３５、３３７、３３９、３４３、３４４のいずれかで決定された探索条件にしたがって、動きベクトル検出装置５０が動きベクトルを検出する。このときの具体的な手順の概略は、実施の形態１で説明したのと同様であるため、ここでは詳細な説明を省略する。ただし、本実施の形態において、探索対象となるトリプレットパターンは実施の形態１で説明したのとは相違して６８個ではなく、ステップＳ３３で探索対象として選択されたリングに関連づけられたものだけである。また、動きベクトルの検出も常にステップＳ１３まで行うのではなく、場合によってはステップＳ３３での決定にしたがってステップＳ９までで終了する。なお、本実施の形態では、ステップＳ３５の動きベクトル検出処理において検出された動きベクトルから中間値ベクトルＭＶｐを引いたものが実際の動きベクトルとなる。
【０１３４】
以上説明した本実施の形態によると、実施の形態１と同様の利益が得られる。特に、本実施の形態は、周辺動きベクトルを参照することによって探索されるトリプレットパターン数を削減することができるので、動きベクトル検出における演算量が大幅に低減されるという点で利益が大きい。
【０１３５】
また、探索範囲２３２を中間値ベクトルＭＶｐ分だけシフトさせるので、抽出される候補ベクトルが比較的小さなベクトルになる可能性が高くなる。したがって、どのリングを選択するかの条件として例えばステップＳ３３６及びステップＳ３３８の２つのような内側リング１３１の選択条件だけを用意しておき、リング選択を少ない演算量で行ったとしても、適切なリングを選択できる可能性が高くなる。
【０１３６】
さらに、評価値演算部５４が算出した絶対値、評価差分及び平均コストなどに基づいて、最初に抽出された候補ベクトルが十分に信頼性の高いものであると判断される場合に図３のステップＳ１０以降の処理を行わないようにしているので、過剰な計算が行われるのを防止することができる。
【０１３７】
しかも、評価値演算部５４が算出した絶対値、評価差分及び平均コストなどに基づいて探索すべきリング１３１、１３２、１３３を選択しているので、比較的少ない演算量及び高い信頼性で探索すべきリング１３１、１３２、１３３を選択することが可能である。
【０１３８】
＜実施の形態３の変形例１＞
ここで、上述した実施の形態３の変形例１について説明する。本変形例では、図２９に示すステップＳ３３において、探索すべきリングを選択するのではなく、周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３に基づいて、３つのリング１３１、１３２、１３３に優先順位を割り付ける。その後、図２５のステップＳ２３以下で説明したような処理を行う。つまり、早い優先順位を割り付けられたリングに関連づけられたトリプレットパターンのＴＳＡＤ値を算出し（Ｓ２３）、その中で最小ＴＳＡＤ値を有するトリプレットパターンを決定する（Ｓ２４）。そして、最小ＴＳＡＤ値が所定の閾値未満であれば（Ｓ２５：ＹＥＳ）、当該最小ＴＳＡＤ値を有するトリプレットパターンを抽出する（Ｓ２６）。一方、最小ＴＳＡＤ値が所定の閾値以上であれば（Ｓ２５：ＮＯ）、優先順位に関係なくすべてのリングに関連づけられたトリプレットパターンのＴＳＡＤ値を算出し（Ｓ２７）、その中で最小ＴＳＡＤ値を有するトリプレットパターンを決定する（Ｓ２８）。そして、当該最小ＴＳＡＤ値を有するトリプレットパターンを抽出する（Ｓ２６）。
【０１３９】
＜実施の形態３の変形例２＞
ここで、上述した実施の形態３の変形例２について説明する。本変形例では、図２７に示した３つのリング１３１、１３２、１３３を用いることなく、実施の形態３においてトリプレットパターンを選択する、或いは、上記変形例１においてトリプレットパターンに優先順位を割り付ける。そのとき、Ｓ３３の探索条件決定段階において、実施の形態２で説明したような周辺動きベクトルＭＶ１、ＭＶ２、ＭＶ３を参照するという手法を用いることによって、６８個のトリプレットパターンの中から、２以上のトリプレットパターンを選択する、或いは、６８個のトリプレットパターンに優先順位を割り付ける。
【０１４０】
＜実施の形態４＞
次に、本発明の実施の形態４について説明する。本実施の形態による動きベクトル検出方法は、実施の形態１〜実施の形態３で説明したような方法によって候補ベクトルが抽出された後などの整数ピクセル精度での動きベクトルが既知であるときに、サブピクセル精度で動きベクトルを検出するためにさらに行われるものである。
【０１４１】
最初に、従来技術におけるサブピクセル精度での動きベクトル検出の概要について、図３１を参照して説明する。図３１は、整数ピクセル精度で検出された候補ベクトルの終点、及び、その周囲に点対称に配置された１／２ピクセル精度での８個の候補ベクトルの各終点の位置を示した図である。図３１において、整数ピクセル精度で検出された終点を代表点と同じく符号２２１で表し、１／２ピクセル精度での８個の候補ベクトルの各終点を２４１と表す。
【０１４２】
終点２２１は、その右下にある画素２１１（符号２１１ａで表す）を左上角の画素とした正方形ブロックの代表点である。１／２ピクセル精度での各終点２４１は、整数ピクセル精度での隣り合う若しくは対角関係にある２つの格子点２３５の中央にあって、その右下にある２個の画素２１１の上下半分ずつの結合領域又は４個の画素２１１の１／４ずつの結合領域を仮想的に左上角の画素とした正方形ブロックの代表点である。例えば、(2)と記された終点２４１は、画素２１１ａの下半分の領域と、画素２１１ａの下側に隣接する画素２１１ｂの上半分の領域との結合領域を仮想的に左上角の画素（画素値は、画素２１１ａの画素値と画素２１１ｂの画素値との平均値）とした正方形ブロックの代表点である。(7)と記された終点２４１は、画素２１１ａの左上１／４の領域と、画素２１１ａの上側に隣接する画素２１１ｃの左下１／４の領域と、終点２２１を挟んで画素２１１ａの反対側にある画素２１１ｄの右下１／４の領域と、画素２１１ａの左側に隣接する画素２１１ｅの右上１／４の領域との結合領域を仮想的に左上角の画素（画素値は、４つの画素２１１ａ、２１１ｃ、２１１ｄ、２１１ｅの平均値）とした正方形ブロックの代表点である。各終点２４１を代表点とする参照ブロックを構成する各画素は、２個の画素２１１又は４個の画素２１１の平均の画素値を有する仮想的なものとなる。
【０１４３】
従来技術において、１／２ピクセル精度での動きベクトル検出を行う場合、(1)と記された整数ピクセル精度で検出された候補ベクトルの終点２２１から始まって、残り８個の終点２４１について図３１に示す(2)〜(9)の順番で、各終点を代表点とする参照ブロックのＳＡＤ値をすべて計算する。このとき、参照ブロックを構成する各画素は、上述のように隣接する２画素又は４画素の画素値の平均値として与えられる。そして、計算された９個のＳＡＤ値の中で最小ＳＡＤ値に係る代表点を、１／２ピクセル精度での動きベクトルの終点とする。
【０１４４】
従来技術において、１／４ピクセル精度での動きベクトル検出を行う場合、１／２ピクセル精度での動きベクトル検出で行ったことと同様の手順をもう一度行う。そのために、１／２ピクセル精度での候補ベクトルの各終点の周囲に、１／４ピクセル精度での８個の候補ベクトルの各終点を定める。この場合、１／４ピクセル精度での各終点を代表点とする参照ブロックを構成する各画素は、２個の画素２１１又は４個の画素２１１の画素値をその構成面積比で重み付けした画素値を有する仮想的なものとなる。そして、１／２ピクセル精度での動きベクトル検出の場合と同様に、１／４ピクセル精度での９個すべての終点について参照ブロックのＳＡＤ値を計算し、計算された９個のＳＡＤ値の中で最小ＳＡＤ値に係る代表点を、１／４ピクセル精度での動きベクトルの終点とする。
【０１４５】
しかしながら、このように常に９個のＳＡＤ値を計算するのは演算負担が大きい。そこで、本実施の形態では、１／２ピクセル精度での動きベクトル検出を行う場合、終点２２１及びその周囲にある１／２ピクセル精度での各終点２４１の合計９点と探索中心点２３４とを結ぶ９個の候補ベクトルに優先順位を割り付ける。本発明者らが数種類の動画像を用いて実験した結果、整数ピクセル精度で抽出された候補ベクトルの終点２２１及びその上下左右に位置する１／２ピクセル精度での４個の終点２４１と探索中心点２３４とを結ぶ５個の候補ベクトルが、終点２２１の右上、右下、左上、左下に位置する１／２ピクセル精度での４個の終点２４１と探索中心点２３４とを結ぶ４個の候補ベクトルよりも候補ベクトルとして抽出される可能性が高いことが分かった。
【０１４６】
そこで、本実施の形態では、９個の候補ベクトルに、図３２に示すような優先順位を割り付ける。すなわち、整数ピクセル精度での終点２２１を有する候補ベクトルに優先順位(1)を、整数ピクセル精度での終点２２１の上下左右に位置する１／２ピクセル精度での終点２４１を有する４個の候補ベクトルに優先順位(2)〜(5)を、整数ピクセル精度での終点２２１の右上、右下、左上、左下に位置する１／２ピクセル精度での終点２４１を有する４個の候補ベクトルに優先順位(6)〜(9)をそれぞれ割り付ける。そして、優先順位(5)までの候補ベクトルの探索において所定条件を満たす候補ベクトルがあれば、その候補ベクトルを１／２ピクセル精度での動きベクトルとして検出する。１／４ピクセル精度での候補ベクトル検出においても、同様の処理を行う。
【０１４７】
次に、本実施の形態による動きベクトル検出装置の構成について、図３３に示す機能ブロック図を参照しつつ説明する。なお、図３３に描かれた部材のうち図１と同じ部材については同じ符号を付してその説明を省略する。図３３において、探索制御部２２の図示を省略している。図３３に示す動きベクトル検出装置６０は、実施の形態１に係る動きベクトル検出装置１が有する参照ブロック抽出部１４、トリプレットパターン記憶部１６、候補ベクトル記憶部１７、パターン抽出部１９、候補ベクトル抽出部２１、画像種類判定部２５及びパターン変更部２６を有しておらず、実施の形態１に係る動きベクトル検出装置１が有していないサブピクセル参照ブロック抽出部６１、優先順位割付部６２、整数精度探索結果記憶部６３、候補ベクトル記憶部６４、サブピクセル抽出部６５及び閾値記憶部６６を有している。
【０１４８】
サブピクセル参照ブロック抽出部６１は、参照フレーム記憶部１２に記憶された参照フレーム画像から、１／２ピクセル精度又は１／４ピクセル精度で参照ブロックを抽出する。サブピクセル参照ブロック抽出部６１は、整数ピクセル精度で検出された１つの候補ベクトルについて１／２ピクセル精度の参照ブロックを８個抽出し、１／２ピクセル精度で検出された１つの候補ベクトルについて１／４ピクセル精度の参照ブロックを８個抽出する。サブピクセル参照ブロック抽出部６１は、参照ブロックを抽出するに当たって、整数精度探索結果記憶部６３及び候補ベクトル記憶部６４の記憶内容を参照する。
【０１４９】
優先順位割付部６２は、図３２に示した９個の終点２２１、２３１に関して、サブピクセル参照ブロック抽出部６４において、どのような優先順位で参照ブロックを抽出するかを割り付ける。
【０１５０】
整数精度探索結果記憶部６３は、参照フレーム画像内における整数ピクセル精度での候補ベクトルの終点２２１の位置を記憶する。候補ベクトル記憶部６４は、整数ピクセル精度での候補ベクトルの終点２２１に対して、図３２に示すような関係にある８個の１／２ピクセル精度での終点２４１の位置を記憶していると共に、１／２ピクセル精度での候補ベクトルの終点２４１に対して８個の１／４ピクセル精度での終点２４２（図３２において、(8)と記された終点２４１の周囲に例示する）の位置を記憶している。
【０１５１】
サブピクセル抽出部６５は、ＳＡＤ値演算部６５ａと、ＳＡＤ値記憶部６５ｂと、候補ベクトル決定部６５ｃとを有している。ＳＡＤ値演算部６５ａは、対象ブロック抽出部１３で抽出された対象ブロックについて、サブピクセル参照ブロック抽出部６４で抽出された参照ブロックに関するＳＡＤ値をそれぞれ導出する。ＳＡＤ値演算部６５ａで導出されたＳＡＤ値は、ＳＡＤ値記憶部６５ｂに順次格納される。候補ベクトル決定部６５ｃは、整数ピクセル精度又は１／２ピクセル精度で検出された１つの候補ベクトルについて９個のＳＡＤ値がＳＡＤ値記憶部６５ｂに格納された後に、その中から最小のＳＡＤ値に係る候補ベクトルを決定する。このようにして決定された候補ベクトルがサブピクセル抽出部２１６５において抽出された候補ベクトルであり、当該候補ベクトルの識別情報が探索制御部２２に供給される。
【０１５２】
閾値記憶部６６は、ＳＡＤ値演算部６５ａが算出したＳＡＤ値と比較される所定の閾値ｔｈ１、ｔｈ２を記憶する。ここで、閾値ｔｈ１は閾値ｔｈ２よりも小さい。
【０１５３】
次に、本実施の形態による動きベクトルの検出方法を、図３４に示すフローチャートにしたがって説明する。前処理として、対象フレーム記憶部１１及び参照フレーム記憶部１２にそれぞれフレーム画像を記憶すると共に、整数精度探索結果記憶部６３及び閾値記憶部６６にそれぞれ所定の情報を記憶する。さらに、前処理として、図３５で説明したように、対象ブロック抽出部１３が、符号化対象フレーム画像２１０を、それぞれが複数の画素２１１からなり且つ所定サイズを有する複数のブロック２１２に分割し、その中から動きベクトル検出対象となる対象ブロック２１４を抽出する。
【０１５４】
ステップＳ４１では、優先順位割付部６２が、整数精度探索結果記憶部６３が記憶した整数精度の終点２２１及びその周囲の８個の１／２ピクセル精度での終点２４１に関して、図３２に示したような優先順位(1)〜(9)を割り付ける。割り付けられた優先順位(1)〜(9)は、候補ベクトル記憶部６４に記憶される。
【０１５５】
続いて、ステップＳ４２において、探索制御部２２が、優先順位を表すパラメータＮを１に初期化する。そして、ステップＳ４３において、パラメータＮが５を超えるかどうか（６以上かどうか）を探索制御部２２が判断し、パラメータＮが５を超えないのであれば（Ｓ４３：ＮＯ）、ステップＳ４４に移行する。
【０１５６】
ステップＳ４４では、サブピクセル参照ブロック抽出部６１が、整数精度探索結果記憶部６３及び候補ベクトル記憶部６４の記憶内容を参照しつつ、パラメータＮに係る参照ブロックを抽出する。そして、ＳＡＤ値演算部６５ａがその参照ブロックについてのＳＡＤ値を算出する。算出されたＳＡＤ値は、ＳＡＤ値記憶部６５ｂに記憶される。
【０１５７】
次に、ステップＳ４５において、候補ベクトル決定部６５ｃが、ステップＳ４４で算出されたＳＡＤ値と閾値記憶部６６に記憶された閾値ｔｈ１とを比較する。その結果、ＳＡＤ値が閾値ｔｈ１未満である場合には（Ｓ４５：ＹＥＳ）、ステップＳ４６に進む。ステップＳ４６では、候補ベクトル決定部６５ｃが、探索中のパラメータＮの候補ベクトルを動きベクトルとして決定し、その動きベクトルに関する識別情報を動きベクトル記憶部２４に記憶する。
【０１５８】
ＳＡＤ値が閾値ｔｈ１以上である場合には（Ｓ４５：ＮＯ）、ステップＳ４７に進んでパラメータＮを１だけインクリメントしてステップＳ４３に戻る。
【０１５９】
ステップＳ４３でパラメータＮが６以上であれば（Ｓ４３：ＹＥＳ）、ステップＳ４８に移行する。ステップＳ４８では、パラメータＮが９を超えるかどうか（１０以上かどうか）を探索制御部２２が判断し、パラメータＮが９を超えないのであれば（Ｓ４８：ＮＯ）、ステップＳ４９に移行する。
【０１６０】
ステップＳ４９では、サブピクセル参照ブロック抽出部６１が、パラメータＮに係る参照ブロックを抽出し、ＳＡＤ値演算部６５ａがその参照ブロックについてのＳＡＤ値を算出する。算出されたＳＡＤ値は、ＳＡＤ値記憶部６５ｂに記憶される。
【０１６１】
そして、ステップＳ５０において、候補ベクトル決定部６５ｃが、ステップＳ４９で算出されたＳＡＤ値と閾値記憶部６６に記憶された閾値ｔｈ２とを比較する。その結果、ＳＡＤ値が閾値ｔｈ２未満である場合には（Ｓ５０：ＹＥＳ）、ステップＳ５１に進む。
【０１６２】
ステップＳ５１では、候補ベクトル決定部６５ｃが、優先順位(1)の候補ベクトルに係るＳＡＤ値（ＳＡＤ(1)）が９個のＳＡＤ値の中の最小値であるかどうかを判断する。その結果、ＳＡＤ(1)が最小ＳＡＤ値であれば（Ｓ５１：ＹＥＳ）、ステップＳ５２に進む。
【０１６３】
ステップＳ５２では、候補ベクトル決定部６５ｃが優先順位(1)の候補ベクトルを動きベクトルとして決定し、その動きベクトルに関する識別情報を動きベクトル記憶部２４に記憶する。
【０１６４】
ステップＳ５０でＳＡＤ値が閾値ｔｈ２以上である場合（Ｓ５０：ＮＯ）、及び、ステップＳ５１でＳＡＤ(1)が最小ＳＡＤ値でない場合（Ｓ５１：ＮＯ）には、ステップＳ５３に進んでパラメータＮを１だけインクリメントしてステップＳ４８に戻る。
【０１６５】
ステップＳ４８でパラメータＮが１０以上と判断されると（Ｓ４８：ＹＥＳ）、ステップＳ５４に進む。ステップＳ５４では、候補ベクトル決定部６５ｃが、ＳＡＤ値記憶部６５ｂに記憶された９個のＳＡＤ値の中で最小ＳＡＤ値に係る候補ベクトルを動きベクトルとして決定し、その動きベクトルに関する識別情報を動きベクトル記憶部２４に記憶する。以上のようにして、１／２ピクセル精度で動きベクトルを検出することができる。
【０１６６】
なお、１／４ピクセル精度で動きベクトルを検出する場合には、上述の処理を２回行えばよい。その際、１／２ピクセル精度で検出された動きベクトル（候補ベクトル）は、動きベクトル記憶部２４に記憶されるのではなく、探索制御部２２に与えられる。
【０１６７】
以上説明した本実施の形態によると、サブピクセル精度の候補ベクトルに優先順位を与えることによって、パラメータＮが５以下のときには、すべての候補ベクトルの探索が終了していない時点であっても対象ブロックと最も相関性の高い候補ベクトルを抽出可能であるので、演算量を比較的少なくしつつ、サブピクセル精度の動きベクトルを高い信頼性で検出することが可能となる。さらに、本実施の形態では、パラメータＮが６から９の場合にも途中で探索を終了して対象ブロックと最も相関性の高い候補ベクトルを抽出可能であるので、演算量を抑制しつつ、さらに高い信頼性を実現することが可能となる。
【０１６８】
また、閾値記憶部６６が記憶した２つの閾値ｔｈ１、ｔｈ２に関して、閾値ｔｈ１が閾値ｔｈ２よりも小さいという関係があるので、ステップＳ４５はステップＳ５０よりもクリアしにくい。これにより、動きベクトル検出の信頼性をさらに高めることができる。
【０１６９】
また、１／４ピクセル精度で動きベクトルを検出することにより、１／２ピクセル精度でのときよりもさらに高精度での動きベクトル検出が可能となる。そして、１／４ピクセル精度での動きベクトル検出も、実質的に１／２ピクセル精度のときと同様に優先順位を割り付けた処理が行われる。したがって、すべての候補ベクトルの探索が終了していない時点であっても対象ブロックと最も相関性の高い候補ベクトルを抽出可能であるので、演算量を比較的少なくしつつ、サブピクセル精度の動きベクトルを高い信頼性で検出することが可能となる。
【０１７０】
＜その他の変形例＞
以上、本発明の好適な実施の形態について説明したが、本発明は上述の実施の形態に限られるものではなく、特許請求の範囲に記載した限りにおいて様々な設計変更が可能なものである。例えば、上述の実施の形態においてブロックは１０画素×１０画素の固定サイズであるとしたが、ブロックは抽出されるブロックごとにサイズが変化する可変サイズブロックであってもよい。さらに、ブロックの形状は、実施の形態で用いた正方形に限られない。
【０１７１】
また、パターンの形状も実施の形態のように三角形や一直線に限られない。二次元パターンが四角形以上の多角形であってもよいし、一次元パターンが一直線ではなく折れ曲がった直線であってもよい。また、面領域から線分が飛び出したような一次元パターンと二次元パターンとが結合したパターンであってもよい。ただし、三角形とすることで演算量を抑えることができるという利点がある。さらに、実施の形態１で、トリプレットパターンの数が探索範囲２３２内の代表点２２１の数２５個以下であってもよい。また、トリプレットパターン同士が一部において重なっていなくてもよい。さらに、実施の形態１において候補ベクトル記憶部１７がなくてもよい。その場合、ステップＳ５で抽出されたトリプレットパターンごとに、その都度これに関連した候補ベクトルを選択すればよい。
【０１７２】
代表点はブロックの左上角に限らず、ブロック内のどこにあってもよい。また、探索範囲の形状も任意の形状に変更してよい。また、代表点は探索中心点２３４の周りに点対称に分布していなくてもよい。その数も任意の数に変更可能である。
【０１７３】
トリプレットパターンや候補ベクトルを抽出する際に行われる演算は、差分絶対値和演算に限らず差分二乗和演算であってもよいし、その他の差分演算であってもよい。また、その際に用いられる画素値は、輝度信号値に色差信号値を含むものであってもよいし、色差信号値だけであってもよい。
【０１７４】
また、本発明は、Ｈ．２６４での使用に限らず様々な動画像符号化技術に適用可能である。
【０１７５】
実施の形態１ではステップＳ１３まで行って動きベクトルを検出しているが、ステップＳ９までの処理で動きベクトルを検出してもよい。あるいは、ステップＳ１３の後にステップＳ１０〜ステップＳ１３の処理を一又は複数回行って得られた候補ベクトルを動きベクトルとして検出してもよい。
【０１７６】
また、実施の形態２において、トリプレットパターン選択部４３が周辺動きベクトル以外の情報に基づいてトリプレットパターンに優先順位を割り付けてもよい。さらに、実施の形態２において、付加トリプレットパターンを２個以上作成してもよい。また、実施の形態２において、トリプレットパターン選択部４３が付加トリプレットパターンを選択しなくてもよい。
【０１７７】
実施の形態３において、探索範囲をシフトしなくてもよい。さらに、実施の形態３において、図３０のステップの一部を省略してもよい。例えば、ステップＳ３４０とステップＳ３４１とを省略した場合には、ステップＳ３３８の条件を満たさなければステップＳ３４２に進む。また、実施の形態３において、探索条件（検出されるリングの選択及び探索段階の決定）は、評価差分などとは別の評価値にしたがって決定されてもよい。また、評価値は１つだけを用いてもよい。また、リングを正方形以外の任意の形状に変更してもよいし、リングの数を増減してもよい。。
【０１７８】
さらに、実施の形態３において、常にステップＳ９で探索を終了してもよい。また、実施の形態３において、探索すべきリングのみを選択し、探索段階までは決めなくてもよい。その場合、常に同じ探索段階までの探索が行われる。また、実施の形態では参照動きベクトルとして上記式（２）、（３）に基づいて中間値ベクトルＭＶｐを算出しているが、これ以外の計算を行って参照動きベクトルを導出してもよい。つまり、参照動きベクトルは、複数の周辺動きベクトルの代表値であればよく、例えば平均値、中央値、最頻値などであってもよい。
【０１７９】
また、実施の形態４において、候補ベクトルに割り付ける優先順位を画像の種類に応じて変更してもよい。また、実施の形態４において、ステップＳ４９からステップＳ５２までの処理を省略してもよい。さらに、１／２ピクセル精度又は１／４ピクセル精度以外のサブピクセル精度で候補ベクトルを検出してもよい。
【図面の簡単な説明】
【０１８０】
【図１】本発明の実施の形態１による動きベクトル検出装置の構成を示す機能ブロック図である。
【図２】図１に機能ブロック図として描かれた動きベクトル検出装置の実際の装置構成の一例を描いた模式図である。
【図３】本発明の実施の形態１による動きベクトルの検出方法を示すフローチャートである。
【図４】対象ブロックに関して参照フレーム画像内に設けられた探索範囲を描いた模式図である。
【図５】探索範囲内に定義された８個のトリプレットパターンの模式図である。
【図６】探索範囲内に定義された８個のトリプレットパターンの模式図である。
【図７】探索範囲内に定義された８個のトリプレットパターンの模式図である。
【図８】探索範囲内に定義された８個のトリプレットパターンの模式図である。
【図９】探索範囲内に定義された８個のトリプレットパターンの模式図である。
【図１０】探索範囲内に定義された８個のトリプレットパターンの模式図である。
【図１１】探索範囲内に定義された４個のトリプレットパターンの模式図である。
【図１２】探索範囲内に定義された８個のトリプレットパターンの模式図である。
【図１３】探索範囲内に定義された８個のトリプレットパターンの模式図である。
【図１４】図５に描かれた８個のトリプレットパターンのうちの１つに関連して定められた複数の候補ベクトルの終点位置を示す模式図である。
【図１５】図６に描かれた８個のトリプレットパターンのうちの１つに関連して定められた複数の候補ベクトルの終点位置を示す模式図である。
【図１６】図７に描かれた８個のトリプレットパターンのうちの１つに関連して定められた複数の候補ベクトルの終点位置を示す模式図である。
【図１７】図８に描かれた８個のトリプレットパターンのうちの１つに関連して定められた複数の候補ベクトルの終点位置を示す模式図である。
【図１８】図９に描かれた８個のトリプレットパターンのうちの１つに関連して定められた複数の候補ベクトルの終点位置を示す模式図である。
【図１９】図１０に描かれた８個のトリプレットパターンのうちの１つに関連して定められた複数の候補ベクトルの終点位置を示す模式図である。
【図２０】図１１に描かれた４個のトリプレットパターンのうちの１つに関連して定められた複数の候補ベクトルの終点位置を示す模式図である。
【図２１】図１２に描かれた８個のトリプレットパターンのうちの１つに関連して定められた複数の候補ベクトルの終点位置を示す模式図である。
【図２２】図１３に描かれた８個のトリプレットパターンのうちの１つに関連して定められた複数の候補ベクトルの終点位置を示す模式図である。
【図２３】対象ブロックの上、右上、左に隣接する３つのブロックの動きベクトル（周辺動きベクトル）について説明するための模式図である。
【図２４】本発明の実施の形態２による動きベクトル検出装置の構成を示す機能ブロック図である。
【図２５】本発明の実施の形態２による動きベクトルの検出方法を示すフローチャートである。
【図２６】本発明の実施の形態２において用いる付加トリプレットパターンについて説明するための模式図である。
【図２７】本発明の実施の形態３において用いる３つのリングについて説明するための模式図である。
【図２８】本発明の実施の形態３による動きベクトル検出装置の構成を示す機能ブロック図である。
【図２９】本発明の実施の形態３による動きベクトルの検出方法を示すフローチャートである。
【図３０】図２９のステップＳ３３の詳細を示すフローチャートである。
【図３１】整数ピクセル精度で検出された候補ベクトルの終点、及び、その周囲に点対称に配置された１／２ピクセル精度での８個の候補ベクトルの各終点の位置を示した図である。
【図３２】本発明の実施の形態４による動きベクトルの検出方法にしたがって優先順位が割り付けられた１／２ピクセル精度での９個の候補ベクトルの終点位置を描いた図である。
【図３３】本発明の実施の形態４による動きベクトル検出装置の構成を示す機能ブロック図である。
【図３４】本発明の実施の形態４による動きベクトルの検出方法を示すフローチャートである。
【図３５】ブロックマッチング法について説明するための図である。
【図３６】ブロックマッチング法における探索範囲の一例について説明するための模式図である。
【図３７】ブロックマッチング法の一つであるＴＳＳ法について説明するための模式図である。
【符号の説明】
【０１８１】
１、４０、５０、６０  動きベクトル検出装置
１１  対象フレーム記憶部
１２  参照フレーム記憶部
１３  対象ブロック抽出部
１４  参照ブロック抽出部
１６  トリプレットパターン記憶部
１７  候補ベクトル記憶部
１９  パターン抽出部
１９ａ  ＴＳＡＤ値演算部
１９ｂ  ＴＳＡＤ値記憶部
１９ｃ  トリプレットパターン決定部
２１  候補ベクトル抽出部
２１ａ  ＳＡＤ値演算部
２１ｂ  ＳＡＤ値記憶部
２１ｃ  候補ベクトル決定部
２２  探索制御部
２５  画像種類判定部
２６  パターン変更部
３１  ＣＰＵ
３２  メモリ
３３  ハードディスク
４１  周辺動きベクトル記憶部
４２  トリプレットパターン作成部
４３  トリプレットパターン選択部
４４  閾値記憶部
５１  周辺動きベクトル記憶部
５２  参照動きベクトル演算部
５３  探索範囲変更部
５４  評価値演算部
５５  探索条件決定部
６１  サブピクセル参照ブロック抽出部
６２  優先順位割付部
６３  整数精度探索結果記憶部
６４  候補ベクトル記憶部
６５  サブピクセル抽出部
６６  閾値記憶部
１０８、１０９  候補ベクトル
１１１〜１１９  トリプレットパターン
１３１  内側リング
１３２  中央リング
１３３  外側リング
２１０  符号化対象フレーム画像
２１１  画素
２１２  ブロック
２１４  対象ブロック
２２０  参照フレーム画像
２２１、２２１ａ、２２１ｂ、２２１ｃ  代表点
２２２、２２４  参照ブロック
２３０  動きベクトル
２３２  探索範囲
２３４  探索中心点
２３５  格子点
２４１、２４２  終点
【図１】
2005244436.tif 000003
【図２】
2005244436.tif 000004
【図３】
2005244436.tif 000005
【図４】
2005244436.tif 000006
【図５】
2005244436.tif 000007
【図６】
2005244436.tif 000008
【図７】
2005244436.tif 000009
【図８】
2005244436.tif 000010
【図９】
2005244436.tif 000011
【図１０】
2005244436.tif 000012
【図１１】
2005244436.tif 000013
【図１２】
2005244436.tif 000014
【図１３】
2005244436.tif 000015
【図１４】
2005244436.tif 000016
【図１５】
2005244436.tif 000017
【図１６】
2005244436.tif 000018
【図１７】
2005244436.tif 000019
【図１８】
2005244436.tif 000020
【図１９】
2005244436.tif 000021
【図２０】
2005244436.tif 000022
【図２１】
2005244436.tif 000023
【図２２】
2005244436.tif 000024
【図２３】
2005244436.tif 000025
【図２４】
2005244436.tif 000026
【図２５】
2005244436.tif 000027
【図２６】
2005244436.tif 000028
【図２７】
2005244436.tif 000029
【図２８】
2005244436.tif 000030
【図２９】
2005244436.tif 000031
【図３０】
2005244436.tif 000032
【図３１】
2005244436.tif 000033
【図３２】
2005244436.tif 000034
【図３３】
2005244436.tif 000035
【図３４】
2005244436.tif 000036
【図３５】
2005244436.tif 000037
【図３６】
2005244436.tif 000038
【図３７】
2005244436.tif 000039