JP5013040B2

JP5013040B2 - 動き探索方法

Info

Publication number: JP5013040B2
Application number: JP2005284116A
Authority: JP
Inventors: 眞弓奥村; 真生濱本; 勇一郎村地; 純一宮越; 哲郎松野; 雅彦吉本
Original assignee: MegaChips Corp; Kobe University NUC
Current assignee: MegaChips Corp; Kobe University NUC
Priority date: 2005-09-29
Filing date: 2005-09-29
Publication date: 2012-08-29
Anticipated expiration: 2025-09-29
Also published as: US20090034620A1; WO2007037053A1; JP2007096804A

Description

本発明は、画像処理によって動き補償を行うための動き探索方法に関する。

高能率符号化方式の一つであるＨ．２６４（ＭＰＥＧ−４Ｐａｒｔ１０、あるいはＡＶＣ（Advanced Video Coding）とも呼ばれている）では、ブロックサイズが異なる７種類の探索ブロックと、画素精度が異なる３種類の補間画像とを用いて、動き補償を行うことが可能である。

従来の全探索法によると、最も密な補間画像内で、全種類の探索ブロックの各々を用いて探索を行うことにより、各探索ブロックに関して最適動きベクトルがそれぞれ求められる。

なお、ブロックサイズが異なる複数種類の探索ブロックを用いた動き探索に関する技術は、例えば下記特許文献１〜５に開示されている。

特開２００４−１８６８９７号公報特開２００４−４８５５２号公報米国特許出願公開第２００４／０１２０４００号明細書米国特許出願公開第２００４／０１９０６１６号明細書米国特許出願公開第２００４／０２１８６７５号明細書

しかしながら、従来の全探索法によると、各探索ブロック毎の最適動きベクトルの適合性は高くなるが、動き探索のための演算量が非常に多くなるという問題がある。

本発明はかかる問題を解決するために成されたものであり、全探索法と比較して動き探索のための演算量を低減し得る動き探索方法を得ることを目的とする。

第１の発明に係る動き探索方法は、（ａ）動き探索の対象であるマクロブロック内に、粗探索ブロックと、前記粗探索ブロック内に含まれるように前記粗探索ブロックを複数に分割した複数の細探索ブロックとを設定するステップと、（ｂ）第１画像内で、前記粗探索ブロックを用いて探索を行うことにより、前記マクロブロック内における前記粗探索ブロックとの類似度が最も高い、最適点を求めるステップと、（ｃ）前記第１画像よりも密な第２画像内で、前記最適点の周辺領域に関して、前記粗探索ブロックを用いて探索を行うことにより、前記粗探索ブロックに関する最適動きベクトルを求めるステップと、（ｄ）前記ステップ（ｃ）を実行する際に併せて実行され、前記第２画像内で、前記最適点の前記周辺領域に関して、前記複数の細探索ブロックの各々を用いて探索を行うことにより、前記複数の細探索ブロックの各々に関する最適動きベクトルを求めるステップとを備え、前記ステップ（ｃ）においては、前記ステップ（ｄ）で前記複数の細探索ブロックの各々に関して求めた類似度の合計として、前記最適点の前記周辺領域内の各点における前記粗探索ブロックの類似度が求められることを特徴とする。

また、第２の発明に係る動き探索方法は、第１の発明に係る動き探索方法において特に、前記粗探索ブロックは、第１粗探索ブロックと、前記第１粗探索ブロック内に含まれるように前記第１粗探索ブロックを複数に分割した第２粗探索ブロック及び第３粗探索ブロックとを含み、前記ステップ（ｂ）は、（ｂ−１）前記第１画像内で、前記第１粗探索ブロックを用いて探索を行うことにより、前記マクロブロック内における前記第１粗探索ブロックとの類似度が最も高い、第１最適点を求めるステップと、（ｂ−２）前記第１画像内で、前記第２粗探索ブロックを用いて探索を行うことにより、前記マクロブロック内における前記第２粗探索ブロックとの類似度が最も高い、第２最適点を求めるステップと、（ｂ−３）前記第１画像内で、前記第３粗探索ブロックを用いて探索を行うことにより、前記マクロブロック内における前記第３粗探索ブロックとの類似度が最も高い、第３最適点を求めるステップとを有し、前記ステップ（ｃ）は、（ｃ−１）前記第２画像内で、前記第１最適点の周辺領域に関して、前記第１粗探索ブロックを用いて探索を行うことにより、前記第１粗探索ブロックに関する最適動きベクトルを求めるステップと、（ｃ−２）前記第２画像内で、前記第２最適点の周辺領域に関して、前記第２粗探索ブロックを用いて探索を行うステップと、（ｃ−３）前記第２画像内で、前記第３最適点の周辺領域に関して、前記第３粗探索ブロックを用いて探索を行うステップと、（ｃ−４）前記ステップ（ｃ−１）を実行する際に併せて実行され、前記第２画像内で、前記第１最適点の前記周辺領域に関して、前記第２粗探索ブロック及び前記第３粗探索ブロックをそれぞれ用いて探索を行うステップとを有し、前記ステップ（ｃ−１）においては、前記ステップ（ｃ−４）で前記第２粗探索ブロック及び前記第３粗探索ブロックに関してそれぞれ求めた類似度の合計として、前記第１最適点の前記周辺領域内の各点における前記第１粗探索ブロックの類似度が求められることを特徴とする。

第３の発明に係る動き探索方法は、第２の発明に係る動き探索方法において特に、前記第１最適点と前記第２最適点とが一致する場合、前記ステップ（ｃ−２）の実行は省略されることを特徴とする。

第１の発明に係る動き探索方法によれば、細探索ブロックに関しては、ステップ（ｂ）で求められた最適点の周辺領域に関してのみ探索が行われる。従って、複数の細探索ブロックを用いて第２補間画像内の全ての領域を対象とした探索を行うという処理が不要となるため、動き探索のための演算量を低減することが可能となる。

しかも、ステップ（ａ）では粗探索ブロック内に含まれるように複数の細探索ブロックが設定されているため、粗探索ブロックの類似度は、複数の細探索ブロックの各々に関して求めた類似度の合計として求めることができる。その結果、粗探索ブロックの類似度を独自に求める必要がないため、動き探索のための演算量をさらに低減することができる。

第２の発明に係る動き探索方法によれば、ステップ（ｃ−４）において、第１最適点の周辺領域に関して第２粗探索ブロック及び第３粗探索ブロックを用いて探索を行うため、第２粗探索ブロック及び第３粗探索ブロックに関して動き探索の範囲を広げることができる。

しかも、第１粗探索ブロック内に含まれるように第２粗探索ブロック及び第３粗探索ブロックが設定されているため、第１粗探索ブロックの類似度は、第２粗探索ブロック及び第３粗探索ブロックに関して求めた類似度の合計として求めることができる。その結果、第１粗探索ブロックの類似度を独自に求める必要がないため、動き探索のための演算量を低減することができる。

第３の発明に係る動き探索方法によれば、第１最適点と第２最適点とが一致する場合、第２最適点の周辺領域に関する第２粗探索ブロックを用いた探索の実行は省略される。従って、動き探索のための演算量をさらに低減することができる。

以下、高能率符号化方式の一つであるＨ．２６４を対象として、本発明の実施の形態について説明する。なお、本発明は、Ｈ．２６４に限らず、ブロックサイズが異なる複数種類の探索ブロックと、画素精度が異なる複数種類の補間画像とを用いて、動き補償を行うことが可能な、全ての符号化方式について適用可能である。

図１は、本発明の実施の形態に係る動き探索方法における処理の流れを示すフローチャートである。

まず、ステップＳＰ１において、探索ブロックの設定を行う。図２に示すように、Ｈ．２６４では、動き探索の対象であるマクロブロック内に、ブロックサイズが異なる７種類の探索ブロック（横１６画素×縦１６画素、横１６画素×縦８画素、横８画素×縦１６画素、横８画素×縦８画素、横８画素×縦４画素、横４画素×縦８画素、横４画素×縦４画素）を設定することが可能である。本実施の形態に係る動き探索方法では、これらの中から任意の探索ブロックを選択し、粗探索ブロックと細探索ブロックとを設定する。

例えば図３に示すように、横１６画素×縦１６画素の探索ブロックＢＬ１と、横１６画素×縦８画素の探索ブロックＢＬ２，ＢＬ３とを粗探索ブロックＧ１として設定し、横８画素×縦８画素の探索ブロックＢＬ４〜ＢＬ７を細探索ブロックＧ２として設定する。ここで、細探索ブロックは、粗探索ブロック内に含まれるように、粗探索ブロックを複数に分割した探索ブロックとして設定される。つまり、図３を参照して、細探索ブロックＢＬ４〜ＢＬ７は粗探索ブロックＢＬ１内に含まれており、細探索ブロックＢＬ４，ＢＬ５は粗探索ブロックＢＬ２内に含まれており、細探索ブロックＢＬ６，ＢＬ７は粗探索ブロックＢＬ３内に含まれている。

あるいは図３の代わりに、例えば図４，５に示すように粗探索ブロックＧ１と細探索ブロックＧ２とを設定してもよい。図４，５のいずれにおいても、細探索ブロックＧ２は、粗探索ブロックＧ１内に含まれるように、粗探索ブロックＧ１を複数に分割した探索ブロックとして設定されている。

以下、本実施の形態では、図３に示したような粗探索ブロックＧ１及び細探索ブロックＧ２が設定された場合を例にとり説明する。

次に、図１に示したステップＳＰ２において、補間画像の設定を行う。Ｈ．２６４では、画素精度が異なる３種類の補間画像（整数画素精度、１／２画素精度、１／４画素精度）を用いることが可能である。本実施の形態に係る動き探索方法では、これらの中から任意の補間画像を選択し、疎な補間画像と密な補間画像とを設定する。

例えば図６に示すように、整数画素精度の補間画像を疎な補間画像Ｉ１として設定し、１／２画素精度の補間画像を密な補間画像Ｉ２として設定する。あるいは図７に示すように、整数画素精度の補間画像を疎な補間画像Ｉ１として設定し、１／４画素精度の補間画像を密な補間画像Ｉ２として設定する。あるいは図８に示すように、１／２画素精度の補間画像を疎な補間画像Ｉ１として設定し、１／４画素精度の補間画像を密な補間画像Ｉ２として設定する。

次に、図１に示したステップＳＰ３において、ステップＳＰ１で設定された粗探索ブロックＧ１と、ステップＳＰ２で設定された疎な補間画像Ｉ１とを用いて、探索を行う。具体的には、疎な補間画像Ｉ１内で、図３に示した探索ブロックＢＬ１〜ＢＬ３を用いた探索を順に行う。かかる探索は、どのような方法によって行ってもよい。例えば、勾配法のような探索アルゴリズムを用いて、疎な補間画像Ｉ１を対象とした探索を探索ブロックＢＬ１について行い、疎な補間画像Ｉ１内の探索が実行された各点に関して、マクロブロック内の探索ブロックＢＬ１との類似度（例えばＳＡＤ（差分絶対値和）。但し、ＳＡＤ以外の指標を用いたり、さらに付加項を加えて類似度を求めることも可能。以下同様。）を求める。そして、ＳＡＤが最も小さくなる点を、探索ブロックＢＬ１に関する最適点（以下「最適点Ｐ１」と称す）として求める。同様に、探索ブロックＢＬ２についても最適点（以下「最適点Ｐ２」と称す）が求められ、探索ブロックＢＬ３についても最適点（以下「最適点Ｐ３」と称す）が求められる。

次に、図１に示したステップＳＰ４において、ステップＳＰ１で設定された粗探索ブロックＧ１と、ステップＳＰ２で設定された密な補間画像Ｉ２とを用いて、探索を行う。ステップＳＰ４での探索は、ステップＳＰ３での探索とは異なり、補間画像の全領域を対象とした探索は行わず、ステップＳＰ３で求めた最適点の周辺領域に関してのみ行われる。

例えば探索ブロックＢＬ１に関しては、密な補間画像Ｉ２内で、最適点Ｐ１の周辺領域（横方向及び縦方向の各々にプラスマイナス数画素程度）に関してのみ、探索ブロックＢＬ１を用いた探索が行われる。具体的には、最適点Ｐ１の周辺領域の各点について、マクロブロック内の探索ブロックＢＬ１とのＳＡＤ（以下「ＳＡＤ１」と称す）を求める。そして、ＳＡＤ１が最も小さくなる点を示す動きベクトルが、探索ブロックＢＬ１に関する最適動きベクトル（以下「最適動きベクトルＭＶ１」と称す）として求められる。

ここで、ＳＡＤ１を求めるにあたっては、最適点Ｐ１の周辺領域の各点について、探索ブロックＢＬ１を構成する探索ブロックＢＬ４〜ＢＬ７の各ＳＡＤ（以下「ＳＡＤ４」〜「ＳＡＤ７」と称す）をそれぞれ求め、ＳＡＤ４〜ＳＡＤ７の合計値としてＳＡＤ１の値を求める。つまり、ＳＡＤ１＝ＳＡＤ４＋ＳＡＤ５＋ＳＡＤ６＋ＳＡＤ７ということである。

同様に探索ブロックＢＬ２に関しては、密な補間画像Ｉ２内で、最適点Ｐ２の周辺領域に関して、探索ブロックＢＬ２を用いた探索が行われる。具体的には、最適点Ｐ２の周辺領域の各点について、マクロブロック内の探索ブロックＢＬ２とのＳＡＤ（以下「ＳＡＤ２」と称す）を求める。そして、ＳＡＤ２が最も小さくなる点を示す動きベクトルが、探索ブロックＢＬ２に関する最適動きベクトル（以下「最適動きベクトルＭＶ２」と称す）として求められる。

ここで、ＳＡＤ２を求めるにあたっては、最適点Ｐ２の周辺領域の各点について、探索ブロックＢＬ２を構成する探索ブロックＢＬ４，ＢＬ５のＳＡＤ４，ＳＡＤ５をそれぞれ求め、ＳＡＤ４，ＳＡＤ５の合計値としてＳＡＤ２の値を求める。つまり、ＳＡＤ２＝ＳＡＤ４＋ＳＡＤ５ということである。

同様に探索ブロックＢＬ３に関しては、密な補間画像Ｉ２内で、最適点Ｐ３の周辺領域に関して、探索ブロックＢＬ３を用いた探索が行われる。具体的には、最適点Ｐ３の周辺領域の各点について、マクロブロック内の探索ブロックＢＬ３とのＳＡＤ（以下「ＳＡＤ３」と称す）を求める。そして、ＳＡＤ３が最も小さくなる点を示す動きベクトルが、探索ブロックＢＬ３に関する最適動きベクトル（以下「最適動きベクトルＭＶ３」と称す）として求められる。

ここで、ＳＡＤ３を求めるにあたっては、最適点Ｐ３の周辺領域の各点について、探索ブロックＢＬ３を構成する探索ブロックＢＬ６，ＢＬ７のＳＡＤ６，ＳＡＤ７をそれぞれ求め、ＳＡＤ６，ＳＡＤ７の合計値としてＳＡＤ３の値を求める。つまり、ＳＡＤ３＝ＳＡＤ６＋ＳＡＤ７ということである。

最適動きベクトルＭＶ１，ＭＶ２を求める際に複数のＳＡＤ４が求められているため、これら複数のＳＡＤ４の中でその値が最も小さくなる点を示す動きベクトルが、探索ブロックＢＬ４に関する最適動きベクトル（以下「最適動きベクトルＭＶ４」と称す）として求められる。探索ブロックＢＬ５に関する最適動きベクトル（以下「最適動きベクトルＭＶ５」と称す）についても同様である。

また、最適動きベクトルＭＶ１，ＭＶ３を求める際に複数のＳＡＤ６が求められているため、これら複数のＳＡＤ６の中でその値が最も小さくなる点を示す動きベクトルが、探索ブロックＢＬ６に関する最適動きベクトル（以下「最適動きベクトルＭＶ６」と称す）として求められる。探索ブロックＢＬ７に関する最適動きベクトル（以下「最適動きベクトルＭＶ７」と称す）についても同様である。

ところで、図３に示した例では粗探索ブロックＧ１として探索ブロックＢＬ１及び探索ブロックＢＬ２，ＢＬ３が設定されているが、探索ブロックＢＬ２，ＢＬ３は探索ブロックＢＬ１内に含まれるため、粗探索ブロックＧ１を、探索ブロックＢＬ１が属する第１の粗探索ブロックＧ１ａと、探索ブロックＢＬ２，ＢＬ３が属する第２の粗探索ブロックＧ１ｂとに分類することもできる。

従って、粗探索ブロックＧ１の探索を行う際に細探索ブロックＧ２の探索を併せて行うという上記のアルゴリズムと同様に、第１の粗探索ブロックＧ１ａの探索を行う際に第２の粗探索ブロックＧ１ｂの探索を併せて行うこともできる。具体的には、ステップＳＰ４で最適点Ｐ１の周辺領域に関して探索ブロックＢＬ１を用いた探索を行う際に、探索ブロックＢＬ２，ＢＬ３を用いた探索を併せて行うこともできる。つまり、探索ブロックＢＬ２のＳＡＤ２はＳＡＤ４＋ＳＡＤ５として求められ、探索ブロックＢＬ３のＳＡＤ３はＳＡＤ６＋ＳＡＤ７として求められ、探索ブロックＢＬ１のＳＡＤ１はＳＡＤ２＋ＳＡＤ３＝ＳＡＤ４＋ＳＡＤ５＋ＳＡＤ６＋ＳＡＤ７として求められるため、探索ブロックＢＬ１を用いた探索を行う際に、探索ブロックＢＬ２，ＢＬ３を用いた探索を併せて行うことができる。

この場合、探索ブロックＢＬ２に関する最適動きベクトルＭＶ２は、最適点Ｐ２の周辺領域に関する探索結果と、最適点Ｐ１の周辺領域に関する探索結果とに基づいて、ＳＡＤ２が最も小さくなる点を示す動きベクトルとして求められる。同様に、探索ブロックＢＬ３に関する最適動きベクトルＭＶ３は、最適点Ｐ３の周辺領域に関する探索結果と、最適点Ｐ１の周辺領域に関する探索結果とに基づいて、ＳＡＤ３が最も小さくなる点を示す動きベクトルとして求められる。これにより、探索ブロックＢＬ２，ＢＬ３に関する探索範囲を広げることができるため、動きベクトルＭＶ２，ＭＶ３をより正確に求めることが可能となる。

なお、例えば、ステップＳＰ３で求めた最適点Ｐ１と最適点Ｐ２とが一致する場合には、ステップＳＰ４において、探索ブロックＢＬ２を用いた探索を行う必要はない。最適点Ｐ１と最適点Ｐ２とが一致するため、探索ブロックＢＬ１を用いた探索を行う際に、探索ブロックＢＬ２を用いた探索を併せて行うことができるからである。探索ブロックＢＬ２を用いた探索を省略することにより、動き探索のための演算量を低減することができる。

次に、図１に示したステップＳＰ５において、ブロック分割方式毎の動きベクトルの適合度を比較することにより、最も適合性の高いブロック分割方式を求める。つまり、密な補間画像Ｉ２内の各点について、ＳＡＤ１と、ＳＡＤ２＋ＳＡＤ３と、ＳＡＤ４＋ＳＡＤ５＋ＳＡＤ６＋ＳＡＤ７とを比較する。そして、ＳＡＤの値が最も小さくなる分割方式が、その点についての最適なブロック分割方式として選択され、その結果に基づいて、動き探索の対象であるマクロブロックの動きベクトルが求められる。

このように本実施の形態に係る動き探索方法によれば、細探索ブロックＧ２に属する探索ブロックＢＬ４〜ＢＬ７に関しては、ステップＳＰ３で求められた最適点Ｐ１〜Ｐ３の周辺領域に関して探索が行われる。従って、探索ブロックＢＬ４〜ＢＬ７の各々を用いて密な補間画像Ｉ２内の全領域を対象とした探索を行うという処理が不要となるため、動き探索のための演算量を低減することが可能となる。

しかも、ステップＳＰ１では粗探索ブロックＧ１内に含まれるように複数の細探索ブロックＧ２が設定されているため、粗探索ブロックＧ１のＳＡＤは、複数の細探索ブロックＧ２の各々に関して求めたＳＡＤの合計として求めることができる。その結果、粗探索ブロックＧ１のＳＡＤを独自に求める必要がないため、動き探索のための演算量をさらに低減することができる。

なお、本実施の形態に係る動き探索方法では、全探索法に比べて細探索ブロックＧ２に関する動き探索が簡易化されているが、全探索法による場合と比較しての画質の劣化の度合いが非常に小さいことが、発明者らのシミュレーションによって確認されている。

本発明の実施の形態に係る動き探索方法における処理の流れを示すフローチャートである。Ｈ．２６４で使用可能な７種類の探索ブロックを示す図である。粗探索ブロック及び細探索ブロックの設定例を示す図である。粗探索ブロック及び細探索ブロックの設定例を示す図である。粗探索ブロック及び細探索ブロックの設定例を示す図である。疎な補間画像及び密な補間画像の設定例を示す図である。疎な補間画像及び密な補間画像の設定例を示す図である。疎な補間画像及び密な補間画像の設定例を示す図である。

符号の説明

Ｇ１粗探索ブロック
Ｇ１ａ第１の粗探索ブロック
Ｇ１ｂ第２の粗探索ブロック
Ｇ２細探索ブロック
ＢＬ１〜ＢＬ７探索ブロック
Ｉ１疎な補間画像
Ｉ２密な補間画像

Claims

（ａ）動き探索の対象であるマクロブロック内に、粗探索ブロックと、前記粗探索ブロック内に含まれるように前記粗探索ブロックを複数に分割した複数の細探索ブロックとを設定するステップと、
（ｂ）第１画像内で、前記粗探索ブロックを用いて探索を行うことにより、前記マクロブロック内における前記粗探索ブロックとの類似度が最も高い、最適点を求めるステップと、
（ｃ）前記第１画像よりも密な第２画像内で、前記最適点の周辺領域に関して、前記粗探索ブロックを用いて探索を行うことにより、前記粗探索ブロックに関する最適動きベクトルを求めるステップと、
（ｄ）前記ステップ（ｃ）を実行する際に併せて実行され、前記第２画像内で、前記最適点の前記周辺領域に関して、前記複数の細探索ブロックの各々を用いて探索を行うことにより、前記複数の細探索ブロックの各々に関する最適動きベクトルを求めるステップと
を備え、
前記ステップ（ｃ）においては、前記ステップ（ｄ）で前記複数の細探索ブロックの各々に関して求めた類似度の合計として、前記最適点の前記周辺領域内の各点における前記粗探索ブロックの類似度が求められる、動き探索方法。
前記粗探索ブロックは、第１粗探索ブロックと、前記第１粗探索ブロック内に含まれるように前記第１粗探索ブロックを複数に分割した第２粗探索ブロック及び第３粗探索ブロックとを含み、
前記ステップ（ｂ）は、
（ｂ−１）前記第１画像内で、前記第１粗探索ブロックを用いて探索を行うことにより、前記マクロブロック内における前記第１粗探索ブロックとの類似度が最も高い、第１最適点を求めるステップと、
（ｂ−２）前記第１画像内で、前記第２粗探索ブロックを用いて探索を行うことにより、前記マクロブロック内における前記第２粗探索ブロックとの類似度が最も高い、第２最適点を求めるステップと、
（ｂ−３）前記第１画像内で、前記第３粗探索ブロックを用いて探索を行うことにより、前記マクロブロック内における前記第３粗探索ブロックとの類似度が最も高い、第３最適点を求めるステップと
を有し、
前記ステップ（ｃ）は、
（ｃ−１）前記第２画像内で、前記第１最適点の周辺領域に関して、前記第１粗探索ブロックを用いて探索を行うことにより、前記第１粗探索ブロックに関する最適動きベクトルを求めるステップと、
（ｃ−２）前記第２画像内で、前記第２最適点の周辺領域に関して、前記第２粗探索ブロックを用いて探索を行うステップと、
（ｃ−３）前記第２画像内で、前記第３最適点の周辺領域に関して、前記第３粗探索ブロックを用いて探索を行うステップと、
（ｃ−４）前記ステップ（ｃ−１）を実行する際に併せて実行され、前記第２画像内で、前記第１最適点の前記周辺領域に関して、前記第２粗探索ブロック及び前記第３粗探索ブロックをそれぞれ用いて探索を行うステップと
を有し、
前記ステップ（ｃ−１）においては、前記ステップ（ｃ−４）で前記第２粗探索ブロック及び前記第３粗探索ブロックに関してそれぞれ求めた類似度の合計として、前記第１最適点の前記周辺領域内の各点における前記第１粗探索ブロックの類似度が求められる、請求項１に記載の動き探索方法。
前記第１最適点と前記第２最適点とが一致する場合、前記ステップ（ｃ−２）の実行は省略される、請求項２に記載の動き探索方法。