(57)【要約】【課題】全探索法と比較して動き探索のための演算量を低減し得る動き探索方法を得る。【解決手段】ステップＳＰ１において、粗探索ブロックＧ１と細探索ブロックＧ２とを設定する。ステップＳＰ２において、任意の補間画像を選択して設定する。ステップＳＰ３において、ステップＳＰ１で設定された細探索ブロックＧ２と、ステップＳＰ２で設定された補間画像Ｉ１とを用いて、探索を行う。ステップＳＰ４において、ステップＳＰ１で設定された粗探索ブロックＧ１を用いて探索を行う。ステップＳＰ４での探索は、ステップＳＰ３での探索とは異なり、補間画像Ｉ１の全領域を対象とした探索は行わず、ステップＳＰ３で求めた最適点Ｐ２〜Ｐ５に関して行われる。【選択図】図１
2007096805.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）動き探索の対象であるマクロブロック内に、粗探索ブロックと、前記粗探索ブロックを複数に分割した第１及び第２の細探索ブロックとを設定するステップと、
（ｂ）前記第１の細探索ブロックを用いて探索を行うことにより、前記第１の細探索ブロックに関する第１の最適動きベクトルを求めるステップと、
（ｃ）前記第２の細探索ブロックを用いて探索を行うことにより、前記第２の細探索ブロックに関する第２の最適動きベクトルを求めるステップと、
（ｄ）前記ステップ（ｂ）及び（ｃ）の結果に基づき、前記第１の最適動きベクトルで示される前記第１の最適点と、前記第２の最適動きベクトルで示される第２の最適点とに関して、前記粗探索ブロックを用いて探索を行うことにより、前記粗探索ブロックに関する第３の最適動きベクトルを求めるステップと
を備える、動き探索方法。
【請求項２】
前記ステップ（ｄ）においては、前記第１の最適点と前記第２の最適点との中間点に関しても、前記粗探索ブロックを用いて探索が行われる、請求項１に記載の動き探索方法。
【請求項３】
前記ステップ（ａ）において、前記第１及び第２の細探索ブロックは、前記粗探索ブロック内に含まれるように設定されており、
前記ステップ（ｄ）においては、前記ステップ（ｂ）及び（ｃ）で前記第１及び第２の細探索ブロックの各々に関して求めた類似度の合計値として、前記第１及び第２の最適点の各々に関する前記粗探索ブロックの類似度が求められる、請求項１又は２に記載の動き探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理によって動き補償を行うための動き探索方法に関する。
【背景技術】
【０００２】
高能率符号化方式の一つであるＨ．２６４（ＭＰＥＧ−４  Ｐａｒｔ１０、あるいはＡＶＣ（Advanced Video Coding）とも呼ばれている）では、ブロックサイズが異なる７種類の探索ブロックと、画素精度が異なる３種類の補間画像とを用いて、動き補償を行うことが可能である。
【０００３】
従来の全探索法によると、最も密な補間画像内で、全種類の探索ブロックの各々を用いて探索を行うことにより、各探索ブロックに関して最適動きベクトルがそれぞれ求められる。
【０００４】
なお、ブロックサイズが異なる複数種類の探索ブロックを用いた動き探索に関する技術は、例えば下記特許文献１〜５に開示されている。
【０００５】
【特許文献１】特開２００４−１８６８９７号公報
【特許文献２】特開２００４−４８５５２号公報
【特許文献３】米国特許出願公開第２００４／０１２０４００号明細書
【特許文献４】米国特許出願公開第２００４／０１９０６１６号明細書
【特許文献５】米国特許出願公開第２００４／０２１８６７５号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来の全探索法によると、各探索ブロック毎の最適動きベクトルの適合性は高くなるが、動き探索のための演算量が非常に多くなるという問題がある。
【０００７】
本発明はかかる問題を解決するために成されたものであり、全探索法と比較して動き探索のための演算量を低減し得る動き探索方法を得ることを目的とする。
【課題を解決するための手段】
【０００８】
第１の発明に係る動き探索方法は、（ａ）動き探索の対象であるマクロブロック内に、粗探索ブロックと、前記粗探索ブロックを複数に分割した第１及び第２の細探索ブロックとを設定するステップと、（ｂ）前記第１の細探索ブロックを用いて探索を行うことにより、前記第１の細探索ブロックに関する第１の最適動きベクトルを求めるステップと、（ｃ）前記第２の細探索ブロックを用いて探索を行うことにより、前記第２の細探索ブロックに関する第２の最適動きベクトルを求めるステップと、（ｄ）前記ステップ（ｂ）及び（ｃ）の結果に基づき、前記第１の最適動きベクトルで示される前記第１の最適点と、前記第２の最適動きベクトルで示される第２の最適点とに関して、前記粗探索ブロックを用いて探索を行うことにより、前記粗探索ブロックに関する第３の最適動きベクトルを求めるステップとを備える。
【０００９】
第２の発明に係る動き探索方法は、第１の発明に係る動き探索方法において特に、前記ステップ（ｄ）においては、前記第１の最適点と前記第２の最適点との中間点に関しても、前記粗探索ブロックを用いて探索が行われることを特徴とする。
【００１０】
第３の発明に係る動き探索方法は、第１又は第２の発明に係る動き探索方法において特に、前記ステップ（ａ）において、前記第１及び第２の細探索ブロックは、前記粗探索ブロック内に含まれるように設定されており、前記ステップ（ｄ）においては、前記ステップ（ｂ）及び（ｃ）で前記第１及び第２の細探索ブロックの各々に関して求めた類似度の合計値として、前記第１及び第２の最適点の各々に関する前記粗探索ブロックの類似度が求められることを特徴とする。
【発明の効果】
【００１１】
第１の発明に係る動き探索方法によれば、粗探索ブロックに関しては、ステップ（ｂ）で求められた第１の最適動きベクトルで示される第１の最適点、及び、ステップ（ｃ）で求められた第２の最適動きベクトルで示される第２の最適点に関してのみ探索が行われる。従って、粗探索ブロックを用いて全ての領域を対象とした探索を行うという処理が不要となるため、動き探索のための演算量を低減することが可能となる。
【００１２】
第２の発明に係る動き探索方法によれば、第１の最適点と第２の最適点との中間点に関しても粗探索ブロックを用いて探索を行うことにより、粗探索ブロックの探索範囲を広げることができ、粗探索ブロックに関する第３の最適動きベクトルをより正確に求めることが可能となる。
【００１３】
第３の発明に係る動き探索方法によれば、ステップ（ａ）において第１及び第２の細探索ブロックは粗探索ブロック内に含まれるように設定されているため、ステップ（ｄ）において、粗探索ブロックの類似度は、第１及び第２の細探索ブロックの各々に関して求めた類似度の合計値として求めることができる。その結果、粗探索ブロックの類似度を独自に求める必要がないため、動き探索のための演算量をさらに低減することができる。
【発明を実施するための最良の形態】
【００１４】
以下、高能率符号化方式の一つであるＨ．２６４を対象として、本発明の実施の形態について説明する。なお、本発明は、Ｈ．２６４に限らず、ブロックサイズが異なる複数種類の探索ブロックを用いて動き補償を行うことが可能な、全ての符号化方式について適用できる。
【００１５】
図１は、本発明の実施の形態に係る動き探索方法における処理の流れを示すフローチャートである。
【００１６】
まず、ステップＳＰ１において、探索ブロックの設定を行う。図２に示すように、Ｈ．２６４では、動き探索の対象であるマクロブロック内に、ブロックサイズが異なる７種類の探索ブロック（横１６画素×縦１６画素、横１６画素×縦８画素、横８画素×縦１６画素、横８画素×縦８画素、横８画素×縦４画素、横４画素×縦８画素、横４画素×縦４画素）を設定することが可能である。本実施の形態に係る動き探索方法では、これらの中から任意の探索ブロックを選択し、粗探索ブロックと細探索ブロックとを設定する。
【００１７】
例えば図３に示すように、横１６画素×縦１６画素の探索ブロックＢＬ１を粗探索ブロックＧ１として設定し、横１６画素×縦８画素の探索ブロックＢＬ２，ＢＬ３と、横８画素×縦１６画素の探索ブロックＢＬ４，ＢＬ５とを細探索ブロックＧ２として設定する。ここで、細探索ブロックＢＬ２，ＢＬ３は、粗探索ブロックＢＬ１内に含まれるように、粗探索ブロックＢＬ１を複数に分割した探索ブロックとして設定されている。細探索ブロックＢＬ４，ＢＬ５についても同様である。
【００１８】
あるいは図３の代わりに、例えば図４，５に示すように粗探索ブロックＧ１と細探索ブロックＧ２とを設定してもよい。図４，５のいずれにおいても、細探索ブロックＧ２は、粗探索ブロックＧ１内に含まれるように、粗探索ブロックＧ１を複数に分割した探索ブロックとして設定されている。
【００１９】
以下、本実施の形態では、図３に示したような粗探索ブロックＧ１及び細探索ブロックＧ２が設定された場合を例にとり説明する。
【００２０】
次に、図１に示したステップＳＰ２において、補間画像の設定を行う。図６に示すように、Ｈ．２６４では、整数画素精度の補間画像Ｉ１と、１／２画素精度の補間画像Ｉ２と、１／４画素精度の補間画像Ｉ３とを用いることが可能である。本実施の形態に係る動き探索方法では、これらの中から任意の補間画像を選択する。
【００２１】
以下、本実施の形態では、整数画素精度の補間画像Ｉ１が選択された場合を例にとり説明する。
【００２２】
次に、図１に示したステップＳＰ３において、ステップＳＰ１で設定された細探索ブロックＧ２と、ステップＳＰ２で設定された補間画像Ｉ１とを用いて、探索を行う。具体的には、補間画像Ｉ１内で、図３に示した探索ブロックＢＬ２〜ＢＬ５を用いた探索を順に行う。例えば探索ブロックＢＬ２に関して、補間画像Ｉ１を対象とした探索を探索ブロックＢＬ２について行い、補間画像Ｉ１内の探索が実行された各点について、マクロブロック内の探索ブロックＢＬ２との類似度（例えばＳＡＤ（差分絶対値和）。但し、ＳＡＤ以外の指標を用いたり、さらに付加項を加えて類似度を求めることも可能。以下同様。）を求める。そして、ＳＡＤが最も小さくなる点を、探索ブロックＢＬ２に関する最適点Ｐ２（図７参照）として求める。また、最適点Ｐ２を示す動きベクトルを、探索ブロックＢＬ２に関する最適動きベクトル（以下「最適動きベクトルＭＶ２」と称す）として求める。同様にして、探索ブロックＢＬ３について最適点Ｐ３及び最適動きベクトルＭＶ３が求められ、探索ブロックＢＬ４について最適点Ｐ４及び最適動きベクトルＭＶ４が求められ、探索ブロックＢＬ５について最適点Ｐ５及び最適動きベクトルＭＶ５が求められる。
【００２３】
次に、図１に示したステップＳＰ４において、ステップＳＰ１で設定された粗探索ブロックＧ１を用いて探索を行う。ステップＳＰ４での探索は、ステップＳＰ３での探索とは異なり、補間画像Ｉ１の全領域を対象とした探索は行わず、ステップＳＰ３で求めた最適点Ｐ２〜Ｐ５に関して行われる。
【００２４】
具体的には、最適点Ｐ２〜Ｐ５の各点について、マクロブロック内の探索ブロックＢＬ１とのＳＡＤをそれぞれ求める。そして、これら複数のＳＡＤのうち、その値が最も小さくなる最適点が、探索ブロックＢＬ１に関する最適点として求められる。また、その最適点を示す動きベクトルが、探索ブロックＢＬ１に関する最適動きベクトル（以下「最適動きベクトルＭＶ１」と称す）として求められる。
【００２５】
ここで、上記のステップＳＰ３では、補間画像Ｉ１の全領域について、探索ブロックＢＬ２のＳＡＤ（以下「ＳＡＤ２」と称す）及び探索ブロックＢＬ３のＳＡＤ（以下「ＳＡＤ３」と称す）が求められている。このように補間画像Ｉ１の全領域についてＳＡＤ２及びＳＡＤ３が求められている場合には、ステップＳＰ４で探索ブロックＢＬ１のＳＡＤ（以下「ＳＡＤ１」と称す）を求めるにあたっては、最適点Ｐ２〜Ｐ５の各点について、ＳＡＤ２，ＳＡＤ３の合計値としてＳＡＤ１の値を求めることができる。つまり、ＳＡＤ１＝ＳＡＤ２＋ＳＡＤ３ということである。これにより、探索ブロックＢＬ１のＳＡＤを独自に求める必要がないため、動き探索のための演算量をさらに低減することができる。但し、ＳＡＤ２，ＳＡＤ３の代わりに、探索ブロックＢＬ４のＳＡＤ（以下「ＳＡＤ４」と称す）及び探索ブロックＢＬ５のＳＡＤ（以下「ＳＡＤ５」と称す）の合計値として、ＳＡＤ１を求めてもよい。つまり、ＳＡＤ１＝ＳＡＤ４＋ＳＡＤ５ということである。
【００２６】
なお、探索ブロックＢＬ１を用いた探索を、最適点Ｐ２〜Ｐ５のみに関して行うのではなく、図７に示すように、最適点Ｐ２と最適点Ｐ３との中間点Ｍ１に重なる点Ｐ６、最適点Ｐ４と最適点Ｐ５との中間点Ｍ２に近接する点Ｐ７〜Ｐ１０、中間点Ｍ１と中間点Ｍ２との中間点Ｍ３に近接する点Ｐ１１、あるいは点Ｐ２〜Ｐ１１の周辺領域（横方向及び縦方向の各々についてプラスマイナス数画素程度）に関しても、探索ブロックＢＬ１を用いた探索を行ってもよい。さらに、点Ｐ２〜Ｐ１１に加えて、前フレームに関する最適動きベクトルＭＶ１によって示されていた最適点等の他の候補点（あるいはその周辺領域）に関しても、探索ブロックＢＬ１を用いた探索を行ってもよい。これにより、探索ブロックＢＬ１の探索範囲を広げることができるため、探索ブロックＢＬ１に関する最適動きベクトルＭＶ１をより正確に求めることが可能となる。
【００２７】
次に、図１に示したステップＳＰ５において、ブロック分割方式毎の動きベクトルの適合度を比較することにより、最も適合性の高いブロック分割方式を求める。つまり、補間画像Ｉ１内の各点について、ＳＡＤ１と、ＳＡＤ２＋ＳＡＤ３と、ＳＡＤ４＋ＳＡＤ５とを比較する。そして、ＳＡＤの値が最も小さくなる分割方式が、その点についての最適なブロック分割方式として選択され、その結果に基づいて、動き探索の対象であるマクロブロックの動きベクトルが求められる。
【００２８】
このように本実施の形態に係る動き探索方法によれば、ステップＳＰ３で細探索ブロックＢＬ２〜ＢＬ５を用いた探索を行い、粗探索ブロックＧ１に属する探索ブロックＢＬ１に関しては、ステップＳＰ３で求められた最適点Ｐ２〜Ｐ５に関して探索が行われる。従って、探索ブロックＢＬ１を用いて補間画像Ｉ１内の全領域を対象とした探索を行うという処理が不要となるため、動き探索のための演算量を低減することが可能となる。
【００２９】
しかも、ステップＳＰ１では粗探索ブロックＧ１内に含まれるように複数の細探索ブロックＧ２が設定されているため、粗探索ブロックＧ１のＳＡＤは、複数の細探索ブロックＧ２の各々に関して求めたＳＡＤの合計として求めることができる。その結果、粗探索ブロックＧ１のＳＡＤを独自に求める必要がないため、動き探索のための演算量をさらに低減することができる。
【００３０】
なお、本実施の形態に係る動き探索方法では、全探索法に比べて粗探索ブロックＧ１に関する動き探索が簡易化されているが、全探索法による場合と比較しての画質の劣化の度合いが非常に小さいことが、発明者らのシミュレーションによって確認されている。
【図面の簡単な説明】
【００３１】
【図１】本発明の実施の形態に係る動き探索方法における処理の流れを示すフローチャートである。
【図２】Ｈ．２６４で使用可能な７種類の探索ブロックを示す図である。
【図３】粗探索ブロック及び細探索ブロックの設定例を示す図である。
【図４】粗探索ブロック及び細探索ブロックの設定例を示す図である。
【図５】粗探索ブロック及び細探索ブロックの設定例を示す図である。
【図６】Ｈ．２６４で使用可能な３種類の補間画像を示す図である。
【図７】粗探索ブロックの探索点を示す図である。
【符号の説明】
【００３２】
Ｇ１  粗探索ブロック
Ｇ２  細探索ブロック
ＢＬ１〜ＢＬ５  探索ブロック
Ｉ１〜Ｉ３  補間画像
【図１】
2007096805.tif 000003
【図２】
2007096805.tif 000004
【図３】
2007096805.tif 000005
【図４】
2007096805.tif 000006
【図５】
2007096805.tif 000007
【図６】
2007096805.tif 000008
【図７】
2007096805.tif 000009