JP2007243337A

JP2007243337A - 動画像符号化方法及び動画像符号化装置とプログラムならびに媒体

Info

Publication number: JP2007243337A
Application number: JP2006059988A
Authority: JP
Inventors: Atsushi Hatao; 敦史幡生
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2006-03-06
Filing date: 2006-03-06
Publication date: 2007-09-20
Anticipated expiration: 2026-03-06
Also published as: JP4677932B2

Abstract

【課題】圧縮効率の低下を避けながら計算量の低減と制御を可能にする動画像符号化方法および装置ならびにプログラムの提供。
【解決手段】符号化コストの計算処理を、計算量の少ない第１コスト計算処理と、精度の高い第２コスト計算処理の２つに分割し、マクロブロックを符号化する際は、各々の符号化タイプに関する第１符号化コストを計算し、得られた結果に基づいて優先符号化タイプを１つ選択し、次に、優先符号化タイプに関する第２符号化コストだけを計算し、得られた結果から、他のタイプに関する第２コスト計算をスキップするか否か判定する。スキップの場合は、第２符号化コストの計算に要する計算量が削減される。さらに、当該マクロブロックに割り当てられた計算量を基に、前記のスキップ率を制御することで、圧縮効率と計算量のバランスがとれ、計算量を制御可能な動画像符号化処理が実現される。
【選択図】図１

Description

本発明は、圧縮効率の低下を少なく抑えながら計算量を削減し、計算量の制御が可能になる動画像符号化方法および装置ならびにプログラムを提供することを目的とする。

大量の動画像データを効率良く圧縮符号化する方法として予測符号化、変換符号化、量子化、可変長符号化等の技術を組み合わせた方法が広く利用されている。代表例としては、ＩＴＵ−Ｔで勧告化されたＨ．２６１、Ｈ．２６３方式や、ＩＳＯ／ＩＥＣＪＴＣ１／ＳＣ２９／ＷＧ１１（ＭＰＥＧ）で規格化されたＭＰＥＧ−１，２，４方式があり、最新の方式としては、ＩＴＵ−ＴとＭＰＥＧが共同で規格化したＨ．２６４／ＭＰＥＧ−４ＡＶＣ方式がある。

これらの符号化方式では、入力された動画像をマクロブロックと呼ばれる特定サイズの小ブロック（例えば１６ｘ１６画素）に分解し、マクロブロックを単位として予測符号化、変換符号化、量子化、可変長符号化等の処理を施すことで、動画像を圧縮する。

予測符号化は、ブロック信号を周辺信号から予測した結果と、当該ブロック信号の差分を符号化することで、出力信号の電力を抑え圧縮効率を高める方法であり、時間または空間方向に強い相関を持つ動画像に対し有効な圧縮手法である。予測する対象として、画素信号ではなく、変換符号化や量子化の出力信号を予測する場合もある。

予測符号化は、大別して、
・時間的に異なる別のフレーム（参照フレーム）から予測信号を生成するインター予測と、
・当該ブロックと同一のフレームから生成するイントラ予測と、
の二つのタイプがある。

インター予測は、動き補償に基づく予測方法が広く利用されている。動き補償は、（符号化済みの）参照フレームから画素をサンプリングして予測画像を生成する処理であり、・１枚のフレームから予測する片方向（Ｐタイプ）予測、
・２枚のフレームから作成された予測画像を合成する双方向（Ｂタイプ）予測、
がある。

参照フレームにおけるサンプル位置と予測されるブロック位置の差分は、「動きベクトル」と呼ばれる。整数画素の動きベクトルだけでなく、２分の１画素や４分の１画素単位の小数で指定された位置からサンプリングを行う小数動き補償技術も開発されている。

符号化時に利用可能な予測の種類（Ｐタイプ、Ｂタイプ）、ブロックサイズ、動きベクトル精度は、符号化方式ごとに定義されている。

例えばＨ．２６４方式のbaseline profileは、Ｐタイプのインター予測を利用し、動きベクトルの精度は４分の１画素である。予測ブロックのサイズは、最小で４×４画素から最大１６×１６画素まで選択可能であり、１６×１６画素のマクロブロックを、図６に示すパターンで複数のサブブロックに分割する。

イントラ予測は、ブロック画像またはブロック画像に変換を施した係数、量子化信号を、同一フレーム内のローカルデコード画像またはローカルデコード時の中間信号から予測する処理である。

例えばＭＰＥＧ−４方式simple profileでは、離散コサイン変換後のＤＣ係数とＡＣ係数を左または上側に位置するブロックの変換係数から予測する。予測のブロックサイズは８×８画素である。

Ｈ．２６４方式baseline profileでは、上方または左方向に位置するマクロブロックのローカルデコード画像から画像信号を予測する。予測単位は、輝度画像の場合１６×１６画素または４×４画素から選択可能であり（図７（ａ）参照）、色差信号は８×８画素である（図７（ｂ）参照）。

予測方法は、縦、横、斜め方向の補間予測、ＤＣ予測、平面予測など複数のモードが定義され、輝度１６×１６画素の場合４モード、輝度４×４画素の場合９モード、色差８×８画素の場合４モードから最適なモードをブロック毎に選択可能である。

このようなイントラ／インター予測符号化を用いて、動画像の画質を落とさずに効率良く圧縮を行うには、動画像符号化装置またはプログラムにおいて、
・予測タイプ（イントラ、インター）、
・予測パラメータ（サブブロック分割モード、動きベクトル、イントラ予測モード）
を適切に選択することが重要である。

具体的には、
・入力画像に類似した予測画像が生成され、かつ、
・予測パラメータの符号化に要するビット数も少ない、
予測モードの選択が必要である。

予測モードの選択が不適切である場合、予測誤差の符号量が増加し、かつ量子化誤差による画質劣化が増大する。

多くの動画像符号化装置または符号化プログラムでは、イントラ／インター予測の適切さを表す符号化コスト関数を定義して、このコスト関数を最小化するパラメータを探索する方法で、各マクロブロックの予測符号化モード、予測パラメータを決定する。

例えば、Ｈ．２６４のリファレンスエンコーダＪＭ（Joint Meeting）は、次式（１）に示すRD_costを符号化コスト関数として用いる。

RD_cost = D+λ×Ｒ
・・・（１）

式（１）において、
Ｄは、予測画像と入力画像の差分を評価する指標であり、ＪＭでは、予測画像と入力画像間における信号差分の絶対値の総和（ＳＡＤ：差分絶対値和）が用いられる。
Ｒは、予測パラメータを符号化するために必要なビット数であり、サブブロック分割モード、動きベクトル、イントラ予測モードを表現するための符号量を含む。
λは、ＲをＤに換算するための係数であり、量子化ステップサイズに依存して設定される。

このような符号化コスト関数に基づき予測モードとパラメータを決定する手順として、始めにインター予測のコスト最小化パラメータ探索と、イントラ予測のコスト最小化パラメータ探索を行い、その結果得られた符号化コスト最小値を比較して、利用する予測タイプ（インター、イントラ）を決定するのが、一つの自然なフローである。

図２は、このような符号化モード決定フローの第１例（「従来例１」ともいう）を示す図である。

動画像符号化装置は、小ブロック画像を入力し符号化を開始すると、ステップＳ２０１で、インター予測パラメータと符号化コスト最小値の計算処理（動きベクトル探索）を行う。

次に、ステップＳ２０２で、イントラ予測パラメータと符号化コストの決定処理を行う。

ステップＳ２０３のタイプ判定処理では、ステップＳ２０１で得られたインター符号化コストと、ステップＳ２０２で得られたイントラ符号化コストとを比較し、その大小関係から、当該ブロックをインター符号化（ステップＳ２０４）、イントラ符号化（ステップＳ２０５）するかを決定する。

インター予測符号化に関するコスト・パラメータ計算（ステップＳ２０１）の実際は、動きベクトル探索と呼ばれる探索処理である。圧縮効率を高めるために好適な動きベクトル探索方法は、選択可能な全てのサブブロック分割モード、動きベクトル値の組み合わせに対して符号化コスト関数を計算し、最小にするパラメータを得る方法（全探索法）である。

しかしながら、全探索法は、評価すべき予測パラメータ数が膨大になるため、現実的に使用することは、困難である。

例えば、式（１）の符号化コスト関数RD_costを、１６×１６画素のブロックに対して計算すると、画素数である１６×１６＝２５６回の差分計算が必要である。

動きベクトルの水平・垂直座標を−１６から＋１６画素まで変えながら、ＲＤ＿ｃｏｓｔを計算すると、ベクトル座標の精度が整数であったとしても、１個の小ブロックあたり、（２×１６＋１）×（２×１６＋１）＝１０８９回のコスト関数の計算が必要であり、差分計算の画素数は、約２８万回に達する。

さらに、動きベクトルの精度が、２分の１、４分の１画素になると、計算量は、４倍、１６倍に増加し、さらにサブブロック分割モードの組み合わせも考慮すると、膨大な計算量になる。

そこで、動きベクトル探索については、従来より、様々な計算量削減方法が利用されている。そのうちの代表的な方法を以下に示す。

・粗い精度（例えば１画素や２画素等）で動きベクトルを求めた後、そのベクトル近傍を詳細な精度（例えば小数画素）で探索する。

・周囲の探索済み動きベクトルを元に動きベクトルの探索範囲を絞り込む。

・複数個のサブブロックの動きベクトル探索範囲を、一定範囲内に絞り込む。

一方、イントラ予測符号化に関するパラメータ探索処理（ステップＳ２０２）は、選択可能な予測パラメータの個数がインター予測のパラメータよりも少ないため、全探索法が有力な探索手法である。

特にＨ．２６４よりも以前に開発された符号化方式は、選択可能なイントラ予測モードの個数が小数に限定されており、例えばＭＰＥＧ−４方式において、符号化時に選択できるイントラ予測パラメータはＡＣ係数の予測を有効にするか否かだけであり、２通りのRD_cost計算するだけでよい。

しかしながら、Ｈ．２６４方式baseline profileでは、選択可能なイントラ予測モード数が多く、かつ、予測単位も４×４画素か１６×１６画素かを選択可能である。このため、全探索法に基づくイントラ予測パラメータ探索処理（ステップＳ２０２）は、相応の計算量を要する処理である。

以上説明した第１例は、予測符号化タイプおよびパラメータを決定するための有力な方法の一つである。しかしながら、予測パラメータの探索に要する計算量が大きいために、このフローを簡略化した方法で探索が行われる例もある。

図３は、動画像符号化装置が入力ブロックの符号化タイプを決定するフローの第２例（「従来例２」ともいう）を示す。この例は、図２に示した前記第１例と異なり、インター符号化コストとパラメータの探索処理が、ステップＳ３０１とＳ３０４の２つに分かれている。また、イントラ符号化コストとパラメータの探索処理が、ステップＳ３０２とＳ３０５の２つに分かれている。

ステップＳ３０１の第１インター符号化コスト・パラメータ計算は、ステップＳ３０４の第２インター符号化コスト・パラメータ計算よりも粗い精度で、インター符号化コストを求める処理である。例えば、ステップＳ３０４が、１／４画素精度で動きベクトルを求めてＲＤ_cost最小値を計算するのに対して、ステップＳ３０１では、整数画素の粗い精度で動きベクトルを求めてRD_cost最小値を計算するとする。

同様に、ステップＳ３０２の第１イントラ符号化コスト・パラメータ計算は、ステップＳ３０５の第２イントラ符号化コスト・パラメータ計算よりも粗い精度でイントラ符号化コストを求める処理である。例えば、ステップＳ３０２は、画像の平滑さと相関のある特徴量からイントラ符号化コストを推定する計算処理であり、ステップＳ３０３は、全探索法に基づき実際に全てのイントラ予測画像を作成してからRD_cost最小値を求める処理であるとする。

ここで、第２例における、ステップＳ３０１とＳ３０２の処理に必要な計算量は、それぞれ、ステップＳ３０４、Ｓ３０５よりも少ないものとする。また、ステップＳ３０１とＳ３０２、Ｓ３０４、Ｓ３０５に要する計算量の総和は、前記第１例における、ステップＳ２０１，Ｓ２０２に要する計算量の総和と同程度であるとする。

前記第２例の前記第１例に対する相違点を説明すると、図２の前記第１例が、イントラ符号化コストとインター符号化コストを計算し終えてから、符号化タイプを決定するのに対して、図３の第２例では、粗い精度で求められたイントラ符号化コストとインター符号化コストを元に符号化タイプを決定することが異なる。

前記第２例の符号化タイプ選択は、前記第１例よりも、不適切なタイプを選択する可能性が高く、結果的に圧縮効率は低下する。

しかしながら、ステップＳ３０３でインター符号化タイプが選択された場合はに、ステップＳ３０５の第２イントラ符号化コスト・パラメータ計算を省略することができる。また、ステップＳ３０３でイントラ符号化タイプが選択された場合は、ステップＳ３０４の第２インター符号化コスト・パラメータ計算を省略することができる。すなわち、いずれのタイプが選択された場合でも、第２例の符号化に必要な計算量は第１例よりも小さくなる。

図４は、動画像符号化装置が、入力ブロックの符号化タイプを決定するまでのフローの第３例（「従来例３」ともいう）を示す。

この第３例は、前記第２例と同様に、イントラ符号化パラメータおよび符号化コストの計算処理が、ステップＳ４０２とＳ４０５の２つに分かれており、必要な計算量と符号化コスト計算の精度が異なっている。

しかし、インター符号化コスト・パラメータ計算については、ステップＳ４０１の１箇所で実行する。

この第３例では、ステップＳ４０１とＳ４０２でそれぞれ計算されたインター符号化コストとイントラ符号化コストを、ステップＳ４０３で比較し、当該ブロックが高い確率でインター符号化されると判断される場合には、ステップＳ４０７に進み、第２イントラ符号化コスト・パラメータ計算をスキップする。

ステップＳ４０３において、当該ブロックがインター符号化される確信が得られない場合は、ステップＳ４０５に進み、イントラ符号化コスト・パラメータの計算を実行して、Ｓ４０６で符号化タイプを判定する。

このタイプ判定は、前記第２例のステップＳ３０３と同等の精度で実行できる。

この第３例の一つの特徴は、ステップＳ４０３におけるイントラスキップ判定率を高めることにより、前記第１例よりも計算量を削減できることである。

また、ステップＳ４０３におけるイントラスキップ判定の誤り（本来イントラ符号化すべきブロックをインターと判断する確率）を低く抑えられれば、前記第１例と同程度の圧縮効率を保つことが可能である。

動きの少ない画像シーンでは、時間方向に強い相関を持つことが多く、ステップＳ４０３におけるイントラスキップが有効に機能する確率が高いことが期待される。

なお、非特許文献３には、Ｈ．２６４符号化において、前記第３例のフローでイントラスキップを行う手法の検討が記載されており、演算量低減の有効性が示されている。

ISO/IEC 14496-2: "INFORMATION TECHNOLOGY CODING OF AUDIOVISUAL OBJECTS Part 2: Visual", 2001. ISO/IEC 14496-10: "Coding of audiovisual objects - Part10: Advanced Video Coding", 2003. 清水智之他, "H.264符号化処理におけるIntra/Interモード判定に関する一検討," 電子情報通信学会総合大会, D-11-51, 2004.

前述したように、当該ブロックの符号化タイプをインターかイントラのいずれかに決定するまでのフローとして、両方のタイプの符号化コストを正確に計算してからタイプを決定する第１例は、圧縮効率および符号化画質の面で好適な方法であるが、計算量が大きい、という問題がある。

簡略な方法で計算されたイントラ符号化コストとインター符号化コストを用いて符号化タイプを決定する前記第２例（図３参照）は、前記第１例（図２参照）よりも計算量を少なくすることが可能であるが、簡略化によるタイプ判定の誤りによって符号化効率が低下する場合がある。

簡略な方法で計算されたイントラ符号化コストを用いて、イントラ評価のスキップを判断する従来の第３例は、時間相関の高い画像入力に対しては効果的であり、画質を落とさずに計算量を削減することが可能である。しかしながら、激しいパンやシーンチェンジにより時間相関が低下すると、イントラ評価がスキップされる符号化ブロックの割合が減少するため、計算量の削減効果が得られなくなる。

更に、前記第３例（図４参照）において、イントラ評価のスキップ率が入力画像に依存して変動することは、実時間で動画像符号化を行う場合に問題になることがある。最悪の場合でも、１フレームの損失もなく符号化を処理させるためには、前記第１例の符号化を実時間処理させるだけの性能が装置に要求される。

これを防ぐために、前記第３例の改良として、イントラ評価のスキップ率を一定に保つことで計算量の変動を抑える方法も考えられる。しかしながら、イントラ符号化すべき画像ブロックをインター符号化する確率が高まるため、結果的に圧縮効率を損なう場合がある。

したがって、本発明の目的は、圧縮効率の低下を避けつつ、より少ない計算量で符号化タイプの選択を行う動画像符号化方法または装置ならびにプログラムを提供することにある。上記目的に加えて、入力画像に依存した計算量の変動を低減する、ことも本発明の目的である。

本願で開示される発明は、上記課題を解決するため、概略以下の構成とされる。

本発明の１つの側面（アスペクト）に係る方法は、動画像を小ブロックに分割しイントラ符号化とインター符号化のいずれかを用いて符号化する動画像符号化方法であって、前記小ブロックを符号化する際、インター及びイントラの各々のタイプで符号化する場合の第１の符号化コストを計算し、得られた第１の符号化コストの結果に基づき優先符号化タイプを１つ選択し、前記優先符号化タイプで符号化される場合の第２の符号化コストを計算し、得られた結果に基づいて前記優先符号化タイプ以外のタイプに関する第２の符号化コスト計算をスキップするか否か判定し、判定の結果、前記第２の符号化コスト計算をスキップする場合には、前記小ブロックを、選択された前記優先符号化タイプで符号化する、ことを特徴とする。

本発明においては、各々のタイプで符号化する場合の前記第１の符号化コストの算出に要する計算量が、前記第２の符号化コストの算出に要する計算量よりも少ない。

本発明に係る方法においては、
（ａ）前記優先符号化タイプとしてイントラ符号化とインター符号化のいずれか一方を選択し、
（ｂ）前記優先符号化タイプとしてイントラ符号化が選択された場合、イントラタイプに関する第２の符号化コストを計算し、
（ｃ）前記ステップ(ｂ)で得られた第２の符号化コストの値と、インタータイプで符号化する場合の前記第１の符号化コスト値から、インタータイプで符号化する場合の第２の符号化コストの計算をスキップするか否か判定し、
（ｄ）前記ステップ（ｃ）での判定の結果、インタータイプで符号化する場合の第２の符号化コスト計算をスキップする場合は、前記小ブロックの符号化タイプとしてイントラ符号化を選択し、
（ｅ）前記ステップ（ｃ）での判定の結果、インタータイプで符号化する場合の第２の符号化コスト計算をスキップしない場合には、インタータイプで符号化する場合の第２の符号化コストを計算し、
（ｆ）ステップ(ｅ)で得られたインタータイプに関する第２の符号化コストの値と、前記ステップ（ｂ）で得られたイントラタイプに関する第２の符号化コスト値とに基づいて、前記小ブロックの符号化タイプとして、インター又はイントラ符号化を選択し、
（ｇ）前記ステップ（ａ）で前記優先符号化タイプとしてインタータイプが選択された場合、インタータイプに関する第２の符号化コストを計算し、
（ｈ）前記ステップ（ｇ）で得られたインタータイプに関する第２の符号化コストの値と、イントラタイプで符号化する場合の前記第１の符号化コスト値から、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップするか否か判定し、
（ｉ）前記ステップ（ｈ）の判定の結果、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップする場合には、前記小ブロックの符号化タイプとしてインタータイプを選択し、
（ｊ）前記ステップ（ｈ）の判定の結果、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップしない場合には、イントラタイプで符号化する場合の第２の符号化コストを計算し、
（ｋ）前記ステップ（ｊ）で得られたイントラタイプに関する第２の符号化コストの値と、前記ステップ（ｇ）で得られたインタータイプに関する第２の符号化コスト値とに基づいて、前記小ブロックの符号化タイプとして、インター又はイントラ符号化を選択する。

本発明においては、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で、第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を、前記スキップ率制御パラメータの制御に利用する。

本発明においては、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を利用して、前記優先符号化タイプの選択条件を修正する。

本発明においては、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数を計数した結果を、前記スキップ率制御パラメータの制御に利用する。

本発明においては、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数とを計数した結果を利用して、前記優先符号化タイプの選択条件を修正する。

本発明においては、前記小ブロックよりも後で符号化される１個以上の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する、ことを特徴とする。

本発明においては、前記小ブロックを含む複数個の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する。

本発明の別の側面に係る動画像符号化装置は、動画像を小ブロックに分割しイントラ符号化とインター符号化のいずれかを用いて符号化する装置であり、インター符号する場合の第１及び第２の符号化コストをそれぞれ計算する第１及び第２のインター符号化コストパラメータ決定手段と、イントラ符号化する場合の第１及び第２の符号化コストをそれぞれ計算する第１及び第２のイントラ符号化コストパラメータ決定手段と、前記小ブロックをインター符号化するインター符号化手段と、前記小ブロックをイントラ符号化するイントラ符号化手段と、制御手段と、を備えている。前記制御手段は、前記小ブロックを符号化する際、前記第１インター符号化コストパラメータ決定手段と前記第１イントラ符号化コストパラメータ決定手段での各第１の符号化コストの結果に基づき、優先符号化タイプとして、インター又はイントラ符号化を選択し、前記第２インター符号化コストパラメータ決定手段と前記第２イントラ符号化コストパラメータ決定手段のうち選択された前記優先符号化タイプに対応する一方が第２の符号化コストを計算し、得られた第２の符号化コストの計算結果に基づいて、前記第２インター符号化コストパラメータ決定手段と前記第２イントラ符号化コストパラメータ決定手段のうち前記優先符号化タイプとして選択されなかった他方のタイプに対応する他方による第２の符号化コスト計算をスキップするか否か判定し、判定の結果、前記第２の符号化コスト計算をスキップする場合には、前記第２インター符号化コストパラメータ決定手段と前記第２イントラ符号化コストパラメータ決定手段のうち前記優先符号化タイプとして選択されなかった他方のタイプに対応する他方による第２の符号化コスト計算を省略して、前記小ブロックを、前記優先符号化タイプである、インター又はイントラタイプに対応した符号化手段で符号化する。本発明において、前記第１の符号化コストの算出に要する計算量が、前記第２の符号化コストの算出に要する計算量よりも少ない、ことを特徴とする。

本発明において、前記制御手段は、前記優先符号化タイプとしてイントラ符号化とインター符号化のいずれか一方を選択し、
イントラ符号化が前記優先符号化タイプとして選択された場合、前記第２のイントラ符号化コストパラメータ決定手段にて第２の符号化コストを計算し、
前記制御手段は、
前記第２のイントラ符号化コストパラメータ決定手段による第２の符号化コストの値と、前記第１のインター符号化コストパラメータ決定手段による前記第１の符号化コストの値とから、前記第２のインター符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップするか否か判定し、
前記判定の結果、前記第２のインター符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップする場合には、前記小ブロックの符号化タイプとして、イントラを選択し、
前記判定の結果、前記第２のインター符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップしない場合には、前記第２のインター符号化コストパラメータ決定手段にて第２の符号化コストを計算し、
前記第２のインター符号化コストパラメータ決定手段による前記第２の符号化コストの値と、前記第２のイントラ符号化コストパラメータ決定手段による前記第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプを選択し、
前記優先符号化タイプとして、インタータイプが選択された場合、前記第２のインター符号化コストパラメータ決定手段にて第２の符号化コストを計算し、
前記第２のインター符号化コストパラメータ決定手段による第２の符号化コストの値と前記第１のイントラ符号化コストパラメータ決定手段による第１の符号化コストの値とから、前記第２のイントラ符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップするか否か判定し、
前記判定の結果、前記第２のイントラ符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップする場合には、前記小ブロックの符号化タイプとしてインタータイプを選択し、
前記第２のイントラ符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップしない場合には、前記第２のイントラ符号化コストパラメータ決定手段にて第２の符号化コストを計算し、
前記第２のイントラ符号化コストパラメータ決定手段による第２の符号化コストの値と前記第２のインター符号化コストパラメータ決定手段による第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプを選択する、制御を行う。

本発明において、前記制御手段は、前記第２の符号化コスト計算のスキップ率と相関を持つスキップ率制御パラメータを、符号化タイプ毎に備え、前記小ブロックの符号化に利用可能な計算量又は処理時間の割当に応じて、前記制御パラメータを調整することで、符号化に要する計算量を制御するようにしてもよい。

本発明において、前記制御手段は、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で、第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を、前記スキップ率制御パラメータの制御に利用するようにしてもよい。

本発明において、前記制御手段は、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を利用して、前記優先符号化タイプの選択条件を修正する、ようにしてもよい。

本発明において、前記制御手段は、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数を計数した結果を、前記スキップ率制御パラメータの制御に利用するようにしてもよい。

本発明において、前記制御手段は、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数とを計数した結果を利用して、前記優先符号化タイプの選択条件を修正する、ようにしてもよい。

本発明において、前記制御手段は、前記小ブロックよりも後で符号化される１個以上の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する、ようにしてもよい。

本発明において、前記制御手段は、前記小ブロックを含む複数個の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用するようにしてもよい。

本発明の別の側面（アスペクト）に係るコンピュータプログラムは、動画像を小ブロックに分割しイントラ符号化とインター符号化のいずれかを用いて符号化する動画像符号化装置を構成するコンピュータに、
前記小ブロックを符号化する際、
インター及びイントラの各々のタイプで符号化する場合の第１の符号化コストを計算し、
得られた第１の符号化コストの結果に基づき優先符号化タイプを１つ選択する処理と、
前記優先符号化タイプで符号化される場合の第２の符号化コストを計算する処理と、
得られた結果に基づいて前記優先符号化タイプ以外のタイプに関する第２の符号化コスト計算をスキップするか否か判定し、判定の結果、前記第２の符号化コスト計算をスキップする場合には、前記小ブロックを、選択された前記優先符号化タイプで符号化する処理と、
を実行させるプログラムよりなる。前記各々のタイプで符号化する場合の前記第１の符号化コストの算出に要する計算量が、前記第２の符号化コストの算出に要する計算量よりも少ない。

本発明に係るコンピュータプログラムにおいて、
（ａ）前記優先符号化タイプとしてイントラ符号化とインター符号化のいずれか一方を選択する処理と、
（ｂ）前記優先符号化タイプとしてイントラ符号化が選択された場合、イントラタイプに関する第２の符号化コストを計算する処理と、
（ｃ）前記ステップ(ｂ)で得られた第２の符号化コストの値と、インタータイプで符号化する場合の前記第１の符号化コスト値から、インタータイプで符号化する場合の第２の符号化コストの計算をスキップするか否か判定する処理と、
（ｄ）前記ステップ（ｃ）での判定の結果、インタータイプで符号化する場合の第２の符号化コスト計算をスキップする場合は、前記小ブロックの符号化タイプとしてイントラ符号化を選択する処理と、
（ｅ）前記ステップ（ｃ）での判定の結果、インタータイプで符号化する場合の第２の符号化コスト計算をスキップしない場合には、インタータイプで符号化する場合の第２の符号化コストを計算する処理と、
（ｆ）前記ステップ(ｅ)で得られたインタータイプに関する第２の符号化コストの値と、前記ステップ（ｂ）で得られたイントラタイプに関する第２の符号化コスト値とに基づいて、前記小ブロックの符号化タイプとして、インター又はイントラ符号化を選択する処理と、
（ｇ）前記ステップ（ａ）で前記優先符号化タイプとしてインタータイプが選択された場合、インタータイプに関する第２の符号化コストを計算する処理と、
（ｈ）前記ステップ（ｇ）で得られたインタータイプに関する第２の符号化コストの値と、イントラタイプで符号化する場合の前記第１の符号化コスト値から、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップするか否か判定する処理と、
（ｉ）前記ステップ（ｈ）の判定の結果、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップする場合には、前記小ブロックの符号化タイプとしてインタータイプを選択する処理と、
（ｊ）前記ステップ（ｈ）の判定の結果、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップしない場合には、イントラタイプで符号化する場合の第２の符号化コストを計算する処理と、
（ｋ）前記ステップ（ｊ）で得られたイントラタイプに関する第２の符号化コストの値と、前記ステップ（ｇ）で得られたインタータイプに関する第２の符号化コスト値とに基づいて、前記小ブロックの符号化タイプとして、インター又はイントラ符号化を選択する処理と
を前記コンピュータに実行させるプログラムよりなる。

本発明に係るコンピュータプログラムにおいて、前記第２の符号化コスト計算のスキップ率と相関を持つスキップ率制御パラメータを、符号化タイプ毎に備え、
前記小ブロックの符号化に利用可能な計算量又は処理時間の割当に応じて、前記制御パラメータを調整することで、符号化に要する計算量を制御する処理を前記コンピュータに実行させるようにしてもよい。

本発明に係るコンピュータプログラムにおいて、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で、第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を、前記スキップ率制御パラメータの制御に利用する処理を前記コンピュータに実行させるようにしてもよい。

本発明に係るコンピュータプログラムにおいて、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を利用して、前記優先符号化タイプの選択条件を修正する処理を前記コンピュータに実行させるようにしてもよい。

本発明に係るコンピュータプログラムにおいて、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数を計数した結果を、前記スキップ率制御パラメータの制御に利用する処理を前記コンピュータに実行させるようにしてもよい。

本発明に係るコンピュータプログラムにおいて、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数とを計数した結果を利用して、前記優先符号化タイプの選択条件を修正する処理を前記コンピュータに実行させるようにしてもよい。

本発明に係るコンピュータプログラムにおいて、前記小ブロックよりも後で符号化される１個以上の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する処理を前記コンピュータに実行させるようにしてもよい。

本発明に係るコンピュータプログラムにおいて、前記小ブロックを含む複数個の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する、処理を前記コンピュータに実行させるようにしてもよい。

本発明によれば、従来手法よりも、計算量と圧縮効率の両面でバランスが取れた符号化を実現可能としている。その理由は、本発明においては、符号化コスト計算を、計算量の少ない第１符号化コスト計算と、より精度の高い第２符号化コスト計算の２つに分割しておき、当該小ブロックを符号化する際、始めに、各々の符号化タイプに関する第１符号化コストを計算し、得られた結果に基づいて、優先符号化タイプを１つ選択する。次に、優先選択された符号化タイプに関する第２符号化コストだけを計算し、得られた結果によっては優先タイプ以外の符号化タイプに関する第２符号化コスト計算をスキップし、これにより、第１符号化コストの計算だけで符号化タイプを決定可能な小ブロックに対しては、第２符号化コスト計算のスキップにより計算量を削減し、判定が難しいブロックに対しては、第２符号化コストを計算して正確な選択を行うためである。

本発明によれば、入力画像内での符号化タイプ分布が変動しても、計算量の変動が少なく抑えられる。これは、本発明による動画像符号化方法、装置においては、イントラ、インター双方の符号化タイプに関して、第２符号化コスト計算のスキップ判定を行っているためである。

さらに本発明によれば、計算量と圧縮効率のバランスを制御し、計算量の変動を安定化させることができる。これは、本発明においては、第２符号化コスト計算のスキップ率と相関を持つスキップ率制御パラメータを備え、このスキップ率制御パラメータを、当該小ブロックの符号化に利用可能な計算量の割当に応じて制御するためである。

さらに本発明によれば、符号化に要する計算量の推定を可能とし、計算量の制御を安定させる。これは、本発明においては、各々の符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２符号化コスト計算がスキップされた小ブロックの個数と、優先タイプとして選択された上で第２符号化コスト計算がスキップされずに優先符号化タイプと異なるタイプで符号化された小ブロックの個数を計数した結果を、前記スキップ率制御パラメータの制御に利用するようにしたためである。

本発明によれば、優先符号化タイプ選択の誤りを補正でき、符号化効率を高めることができる。これは、本発明においては、各々の符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２符号化コスト計算がスキップされた小ブロックの個数と、優先タイプとして選択された上で第２符号化コスト計算がスキップされずに優先符号化タイプと異なるタイプで符号化された小ブロックの個数を計数した結果を、優先符号化タイプ選択基準の調整に利用する構成としたためである。

本発明によれば、これから符号化する１個以上の小ブロックに対して、各々のタイプの出現頻度とタイプ判定が難しい小ブロックの出現率が推定できるため、計算量の制御を安定化させることができる。これは、本発明においては、小ブロックよりも後で符号化される１個以上の小ブロックに対して、各々の符号化タイプに関する第１符号化コストを予め計算し、得られた結果を、優先符号化タイプの選択とキップ率制御パラメータの制御に利用しているためである。

本発明を実施するための最良の形態について図面を参照して以下に説明する。

＜第１実施形態＞
本発明の第１実施形態を説明する。説明を具体的にするため、H.264方式baseline方式に基づく動画像符号化を行う装置を想定するが、同様にインター予測とイントラ予測により動画像を符号化する装置であれば、他の符号化方式を利用していても本実施形態は適用可能である。

図５は、本発明の第１実施形態に係る動画像符号化装置の構成を示すブロック図である。図５を参照すると、第１実施形態に係る動画像符号化装置は、入力された動画像データを蓄積する入力画像蓄積手段５０１と、入力画像蓄積手段５０１に蓄積された動画像データを所定画素数のマクロブロック（１６×１６画素）に分割して取り出す小ブロック分割手段５０２を備える。また、符号化済みのブロックのローカルデコード画像を蓄積するローカルデコード画像蓄積手段５０４を備える。

制御手段５０５は、各手段の動作と入力マクロブロックの符号化タイプを決定し、必要な指示を各手段に伝送する。符号化タイプの決定方法については、後述する。

符号化タイプ選択部５１２は、制御手段５０５が選択したタイプで符号化された符号化データを出力し、ローカルデコード画像をローカルデコード画像蓄積手段５０４に出力する。

第１インター符号化コスト・パラメータ決定手段５０６は、小ブロック分割手段５０２に入力された小ブロック画像をインター符号化する際の予測パラメータ（予測モード、サブブロック分割モード、動きベクトル座標）の探索を行いながら、インター符号化タイプに関する第１符号化コスト（RD_cost_inter1）を算出する。

第２インター符号化コスト・パラメータ決定手段５０７は、小ブロック分割手段５０２に入力された小ブロック画像をインター符号化する際の予測パラメータの探索を行い、インター符号化タイプに関する第２符号化コスト（RD_cost_inter2）を算出する。第２インター符号化コスト・パラメータ決定手段５０７によるパラメータ探索は、第１インター符号化コスト・パラメータ決定手段５０６のパラメータ探索の結果を利用することも可能である。

計算量削減の効果を得るためには、第１インター符号化コスト・パラメータ決定手段５０６により符号化コストを計算するために必要な計算量が、第２インター符号化コスト・パラメータ決定手段５０７により符号化コストを計算するために必要な合計の計算量（手段５０７で手段５０６の計算結果を用いる場合は、両者の合計とする）よりも小さいことが望ましい。その代わり、第１インター符号化コスト・パラメータ決定手段５０６により計算された符号化コスト（RD_cost_inter1）は、多少の誤差を含んでいても構わない。

この例では、第１インター符号化コスト・パラメータ決定手段５０６によるインター予測パラメータ探索は、整数画素精度の動きベクトル探索処理であるものとする。サブブロック分割は考慮せず、16×16画素のブロックによる探索であるとする。

符号化コストRD_cost_inter1は、このような範囲を探索して得られた、上式（１）のRD_costであるものとする。

また、第２インター符号化コスト・パラメータ決定手段５０７によるインター予測パラメータ探索は、第１インター符号化コスト・パラメータ決定手段５０６で得られた動きベクトルの近傍を、4分の1画素精度で探索する動きベクトル探索であるものとする。

16×16画素以外のサブブロック分割モードも全て評価する。符号化コストRD_cost_inter2は、このような探索の結果得られたRD_cost（上式（１）参照）であるとする。

インター符号化手段５０８は、第２インター符号化コスト・パラメータ決定手段５０７により決定された予測パラメータに基づいて、当該小ブロックを所定の方法で、インター符号化する。より詳しくは、インター符号化手段５０８は、入力画像と予測画像と差分を計算し、これに対し所定の変換と量子化、可変長符号化等を施して符号化データを生成する。また、インター符号化手段５０８は、逆量子化と逆変換を施して得られた信号に予測画像を加算することで、ローカルデコード画像を作成する。得られたデコード画像は、ローカルデコード画像蓄積手段５０４に格納される。

具体的には、H.264 方式で規定された方法に従って、符号化データとローカルデコード画像を生成する。

１枚のフレームを符号化し終えた後は、次のフレームを符号化する前に、ローカルデコード画像蓄積手段５０４に格納されたローカルデコード画像に、ループフィルタを施しておく。

以上と同様に、第１イントラ符号化コスト・パラメータ決定手段５０９は、小ブロック分割手段５０２に入力された小ブロック画像を、イントラ符号化する際の予測パラメータ（予測モード、サブブロック分割モード）の探索を行いながら、イントラ符号化タイプに関する第１符号化コスト（RD_cost_intra1）を算出する。

第２イントラ符号化コスト・パラメータ決定手段５１０は、手段５０２に入力された小ブロック画像をイントラ符号化する際の予測パラメータの探索を行い、イントラ符号化タイプに関する第２符号化コスト（RD_cost_intra2）を算出する。第２イントラ符号化コスト・パラメータ決定手段５１０によるパラメータ探索は、第１イントラ符号化コスト・パラメータ決定手段５０９の探索結果を利用することも可能である。

計算量削減効果を得るために、第１イントラ符号化コスト・パラメータ決定手段５０９により符号化コストを計算するために必要な計算量は、第２イントラ符号化コスト・パラメータ決定手段５１０により符号化コストを計算するために必要な合計の計算量（手段５１０で、手段５０９の計算結果を用いる場合は、両者の合計とする）よりも小さいとする。その代わり、第１イントラ符号化コスト・パラメータ決定手段５０９により計算された符号化コスト（RD_cost_intra1）は、多少の誤差を含んでいても構わない。

この例では、第１イントラ符号化コスト・パラメータ決定手段５０９は、イントラ予測画像の生成と予測モードの決定を行わず、符号化コストの推定値だけを計算する。

具体的には、次式（２）に示すRD_cost_intra1を計算する。

RD_cost_intra1 = θINTRA1×DIFF+λ×Ｒ
・・・（２）

式（２）において、
DIFFは入力画像内で水平方向に隣接する画素同士の差分と、垂直方向に隣接する画素の差分に関して、絶対値の総和を計算した値である。
θINTRA1は、正の重み係数である。
λは、式（１）のRD_costと同じ値である。
Rは、イントラマクロブロックのヘッダ長平均値である。

これに対し、第２イントラ符号化コスト・パラメータ決定手段５１０は、H.264方式において利用可能な全てのイントラ予測モードとサブブロック分割モードに対して、式（１）のRD_costを計算し、これを最小化する予測パラメータを求める。

具体的には、
（Ｉ）輝度１６×１６画素単位のイントラ予測モード探索、
（II）輝度４×４画素単位のイントラ予測モード探索、
（III）輝度イントラ予測のブロックサイズ選択、
（IV）色差８×８画素単位のイントラ予測モード探索、
の順で探索を行う。

（I）と（IV）のイントラ予測モード探索は、符号化済みの周辺マクロブロック画像から４種類の予測画像を生成し、RD_costを最小化する予測モードを選択する。

（II）のイントラ予測モード探索は、４×４画素の輝度画像を１個ずつラスタスキャン順に取り出して、RD_costを最小化する予測モードを９通りの中から選択する処理を１６個分繰り返す。このとき、後で符号化される４×４画素ブロックの予測画像の生成にローカルデコード画像の生成が必要なため、４×４画素ブロック単位でH.264方式で規定されるデコード画像作成処理（予測差分の変換・量子化、逆量子化・逆変換、予測画像の加算）を実行する。

（III）の予測ブロックサイズ選択は、（I）で計算されたRD_cost最小値と、（II）で計算されたRD_cost最小値を比較して、小さい方のサブブロックサイズを選択する処理である。

容易に分かるように、第１イントラ符号化コスト・パラメータ決定手段５０９により計算されたRD_cost_intra1は、第２イントラ符号化コスト・パラメータ決定手段５１０が出力するRD_cost_intra2よりも不正確な符号化コストである。しかしながら、RD_cost_intra1の計算量は、RD_cost_intra2に比べて小さい。

イントラ符号化手段５１１は、第２イントラ符号化コスト・パラメータ決定手段５１０により決定された予測パラメータに基づいて、当該小ブロックを所定の方法で、インター符号化する。より詳細には、イントラ符号化手段５１１は、入力画像と予測画像と差分を計算し、これに対し所定の変換と量子化、可変長符号化等を施して符号化データを生成する。また、イントラ符号化手段５１１は、逆量子化と逆変換を施して得られた信号に予測画像を加算することで、ローカルデコード画像を作成する。得られたデコード画像は、ローカルデコード画像蓄積手段５０４に格納される。

具体的には、Ｈ．２６４方式で規定された方法に従って符号化データとローカルデコード画像を生成する。ただし、輝度成分の予測ブロックサイズが４×４画素のときは、既に手段５１０によって予測差分の量子化信号とローカルデコード画像が作成されているので、これを、第２イントラ符号化コスト・パラメータ決定手段５１０から受け取って可変長符号化処理とローカルデコード画像の蓄積のみを行う。

１枚のフレームを符号化し終えた後は、次のフレームを符号化する前に、ローカルデコード画像蓄積手段５０４に格納されたローカルデコード画像にループフィルタを施しておく。

以上の構成において、第１、第２のインター符号化コスト・パラメータ決定手段５０６、５０７の動作は、前記説明した例に限定されない。

例えば、第１インター符号化コスト・パラメータ決定手段５０６は、水平、垂直ともに2分の１に縮小された画像を利用して２画素精度で動きベクトルを探索し、得られた結果から第１インター符号化コストを計算してもよい。この場合、整数画素精度の探索は、第２インター符号化コスト・パラメータ決定手段５０７で実行する。

別の例として、手段５０６は、周囲の符号化済みマクロブロックから予測された１個以上の動きベクトルや、座標値が０である動きベクトル（当該ブロックと同じ位置を参照する）においてのみ符号化コストを計算して、得られたコスト最小値を第１のインター符号化コストとしても良い。この場合、残りの動きベクトル探索処理を手段５０７が実行する。

第１インター符号化コスト・パラメータ決定手段５０６における予測パラメータ選択において、サブブロック分割モードの評価選択まで実行し、その結果から第１インター符号化コストを計算してもよい。あるいは、２分の１画素精度の動きベクトルまで決定するようにしても構わない。

第１インター符号化コスト・パラメータ決定手段５０６おける予測パラメータ選択に、符号化に利用できる複数の参照フレームから１枚を選択する処理が含まれていても構わない。Ｈ．２６４符号化方式ではインター予測で利用する参照フレームを符号化済みの複数のフレームから選択可能である（マルチフレーム参照）。

第１インター符号化コスト・パラメータ決定手段５０６おける予測パラメータ選択処理が、スキップ符号化タイプを最初に探索し、得られた符号化コストが閾値よりも小さい場合に他の動きベクトル探索を省略する手順であっても構わない。スキップ符号化タイプは、インター符号化タイプの一種であり、周囲の符号化済み動きベクトルから予測された動きベクトルを用いて１６×１６画素の単位でインター予測を行う。

本実施形態は、H.264 baseline profileに基づく動画像符号化装置を想定しているが、例えばmain profileであり、インターレース画像を符号化する場合は、手段５０６おける予測パラメータ選択で、利用可能なインターレース符号化モードを選択する処理が含まれていても構わない。

第１および第２のインター符号化コストの計算式は、上式（１）に限定されない。例えば、予測画像と入力画像の差分に関する絶対値の和でなく、その２乗の和でも良い。あるいは差分信号に対してブロック単位の整数変換を施して得られた信号の絶対値の和を利用しても良い。

同様に、第１、第２のイントラ符号化コスト・パラメータ決定手段５０９、５１０の動作も、前記説明した例に限定されない。

例えば、第１イントラ符号化コスト・パラメータ決定手段５０９は、イントラ予測画像を生成せずに符号化コストの推定値を求めたが、出現頻度の高い一部のイントラ予測モードに関しては予測画像を実際に計算してもよい。より具体的には、輝度４×４画素単位の水平方向予測、垂直方向予測、直流信号予測については、予測画像を生成して入力画像との差分を計算して、これを符号化コスト評価に用いる例が考えられる。

第１イントラ符号化コストの計算式は、式２に限定されない。例えば、DIFFとして水平方向に隣接する画素同士の差分と、垂直方向に隣接する画素の差分に関して、その２乗の総和を計算した値を用いてもよい。あるいは、隣接画素の差分に関する分散を利用してもよい。隣接画素の差分ではなく、入力画像の分散を利用してもよい。

他にも、イントラ予測モード毎に異なる符号化コスト関数を利用しても良く、例えば入力画像における水平、垂直、斜め方向の信号変化を計算し、これを符号化コストの評価指標に加えてもよい。

同様にして、第２イントラ符号化コスト・パラメータ決定手段５１０の動作も前記例に限定されない。例えば、全ての予測モードに関して探索を行わずに、（II）輝度４×４画素単位のイントラ予測モード探索のみを実行して、その中で得られる符号化コスト最小値を第２のイントラ符号化コストとしてもよい。

あるいは、４×４画素の輝度画像に関するデコード画像作成処理を省くために、デコード画像ではなく入力画像からイントラ予測画像を生成して、イントラモードの選択と符号化コストの計算を行ってもよい。

イントラ予測モード選択処理の一部を、イントラ符号化手段５１１で行ってもよい。例えば、（Ｉ）輝度１６×１６画素単位のイントラ予測モード探索と（IV）色差８×８画素単位のイントラ予測モード探索に関しては、第２イントラ符号化コスト・パラメータ決定手段５１０ではなく、イントラ符号化手段５１１で実行する。

以上の構成からなる第１実施形態の動画像符号化装置に関して、全体の動作を図１のフローチャートに従い説明する。

第１実施形態の動画像符号化装置は、マクロブロックの符号化が開始されると、ステップＳ１０１で、第１インター符号化コスト・パラメータ決定手段５０６を用いて、第１インター符号化コストRD_cost_inter1を計算する。

ステップＳ１０２に進み、第１イントラ符号化コスト・パラメータ決定手段５０９を用いて第１イントラ符号化コストRD_cost_intra1を計算する。

次に、ステップＳ１０３において、次式（３）に示す条件式が成立するか判定する。

RD_cost_inter1＜α1 ×RD_cost_intra1＋β1 ・・・（３）

パラメータα1は、1付近の値、
β1は、０付近の値が設定される制御パラメータである。

ステップＳ１０３において、条件式（３）が成立する場合、すなわち、RD_cost_inter1がRD_cost_intra1よりも小さい場合には（第１インター符号化コストが、第１イントラ符号化コストよりも小）、優先符号化タイプとして、インタータイプを選択し、ステップＳ１０４に進む。

ステップＳ１０３において、条件式（３）が成立しない場合は、優先符号化タイプとして、イントラタイプを選択し、ステップＳ１０５に進む。

ステップＳ１０４に進んだ場合、第２インター符号化コスト・パラメータ決定手段５０７を用いて第２インター符号化コストRD_cost_inter2を計算し、ステップＳ１０６に進む。

ステップＳ１０６では、ステップＳ１０１とステップＳ１０４でそれぞれ計算された結果を用いて、第２イントラ符号化コストの計算をスキップするか否かを判定する。

判定の結果、第２イントラ符号化コストの計算をスキップする場合には、ステップＳ１１１に進み、当該マクロブロックを手段５０８を用いてインター符号化する。第２イントラ符号化コストの計算をスキップしない場合には、ステップＳ１０８で、第２イントラ符号化コストを計算し、ステップＳ１１０に進む。

ステップＳ１０６におけるスキップ判定は、例えば次式（４）で表す条件式が成立する場合に、イントラ符号化コスト計算をスキップするとする。

RD_cost_inter2 ＜ αINTRA_SKIP×RD_cost_intra1+βINTRA_SKIP
・・・（４）

上式（４）において、
αINTRA_SKIP（＞０）とβINTRA_SKIPは、スキップ率を制御するパラメータである。αINTRA_SKIPまたはβINTRA_SKIPを大きくすると、スキップ率が増加する。

ステップＳ１０５に進んだ場合、第２イントラ符号化コスト・パラメータ決定手段５１０を用いて第２イントラ符号化コストRD_cost_intra2を計算し、ステップＳ１０７に進む。

ステップＳ１０７では、ステップＳ１０２とステップＳ１０５でそれぞれ計算された符号化コストを用いて、第２インター符号化コストの計算をスキップするか否かを判定する。

第２インター符号化コストの計算をスキップする場合は、ステップＳ１１２に進み、当該マクロブロックを、イントラ符号化手段５１１を用いてイントラ符号化する。

第２インター符号化コストの計算をスキップしない場合には、ステップＳ１０９で第２インター符号化コストを計算し、ステップＳ１１０に進む。

ステップＳ１０７における、第２インター符号化コストの計算のスキップ判定は、例えば、次式（５）で表す条件式が成立する場合に、インター符号化コスト計算をスキップするとする。

RD_cost_intra2 ＜ αINTER_SKIP×RD_cost_inter1+βINTER_SKIP
・・・（５）

だたし、αINTER_SKIP（＞０）、βINTER_SKIPはスキップ率を制御するパラメータである。αINTER_SKIPまたはβINTER_SKIPを大きくすると、スキップ率が増加する。

ステップＳ１１０に進んだ場合、イントラ、インター双方のタイプに関する第２符号化コスト、RD_cost_inter2と、RD_cost_intra2の大小を比較する。

RD_cost_inter2がRD_cost_intra2よりも小さい場合には、ステップＳ１１１に進み、インター符号化手段５０８により当該マクロブロックをインター符号化する。

RD_cost_inter2がRD_cost_intra2以上の場合は、ステップＳ１１２に進み、イントラ符号化手段５１１によりイントラ符号化する。

なお、本実施形態では、第２符号化コスト計算のスキップ判定式の例として、式（４）、式（５）を例示したが、本発明はかかる式に限定されるものでなく、別の関係式でもあってもよい。また、複数の判定式の組み合わせによって決定される判定としてもよい。

別の例として、次式（６）に示すように、入力画像から計算された特徴量Diffを含む項γINTER_SKIP×Diff が加わっていてもよい。

RD_cost_intra2 ＜ αINTER_SKIP×RD_cost_inter1-γINTER_SKIP×Diff+βINTER_SKIP
・・・（６）

上式（６）におけるDiffは、第１インター符号化コストRD_cost_inter1が含むコスト計算誤差の上限を推定する指標である。これは、動きベクトルを微小に動かした場合の符号化コスト関数変化の上限に相関があることを利用している。パラメータγINTER_SKIPは、第２符号化コスト計算における動きベクトル探索範囲に依存して決定される。

スキップ判定の例として、次式（７）のように、乱数によって生成される項ΔINTER_SKIP×zを含んでいてもよい。

RD_cost_intra2 ＜ RD_cost_inter1+ΔINTER_SKIP×z+βINTER_SKIP
・・・（７）

ただし、zは平均０、分散１の正規分布に従うように生成された乱数とする。式（７）の判定式の成否は確率的に決定される。

別の方法として、はじめに式（４）の判定によってスキップ判定を行い、スキップ条件が成立しない場合に限り、一様乱数とパラメータεINTER_SKIPの比較を行う方法がある。

z ＜ εINTER_SKIP
・・・（７a）

式（７ａ）による方法の利点は、スキップ率をパラメータεINTER_SKIPにより、容易に制御可能であることである。

類似の方法として、乱数の代わりに、マクロブロックに付けられた番号を整定数で割り算し、その結果得られる剰余を利用してスキップ率を判定する方法であってもよい。

第１実施形態に従う動画像符号化装置の計算量と画質の関係を説明するため、従来技術として説明した３つの例と比較する。

ここで、図２の第１例の符号化コスト・パラメータ計算処理は、本実施形態の第２符号化コスト・パラメータ計算処理（第１符号化コスト・パラメータ計算処理の結果を利用する場合は、第１の計算処理も含む）に等しいとする。

図３の第２例の第１、第２符号化コスト・パラメータ計算は、本実施形態の計算と等しいとする。

図４の第３例におけるインター符号化コスト・パラメータ計算処理は、本実施形態のインター第１符号化コスト・パラメータ計算処理と第２計算処理に等しいとする。

第３例における、第１、第２イントラ符号化コスト・パラメータ計算は、本実施形態の計算と等しいとし、イントラスキップ判定も本実施形態と等価であるとする。

本実施形態の符号化装置は、入力されたマクロブロックを下記の６通りのうち、いずれかの手順で符号化する。

手順１：インター優先→スキップ →インター符号化
手順２：インター優先→スキップ無し→インター符号化
手順３：インター優先→スキップ無し→イントラ符号化
手順４：イントラ優先→スキップ無し→インター符号化
手順５：イントラ優先→スキップ無し→イントラ符号化
手順６：イントラ優先→スキップ →イントラ符号化

なお、手順１は、ステップＳ１０３でインター優先→ステップＳ１０６でスキップ→ステップＳ１１１でインター符号化が行われるパスに対応する。手順２は、ステップＳ１０３でインター優先→ステップＳ１０６でスキップ無し→ステップＳ１１０でインター符号化を選択しステップＳ１１１でインター符号化が行われるパスに対応する。手順３は、ステップＳ１０３でインター優先→ステップＳ１０６でスキップ無し→ステップＳ１１０でイントラ符号化を選択しステップＳ１１２でイントラ符号化が行われるパスに対応する。手順４は、ステップＳ１０３でイントラ優先→ステップＳ１０７でスキップ無し→ステップＳ１１０でインター符号化を選択しステップＳ１１１でインター符号化が行われるパスに対応する。手順５は、ステップＳ１０３でイントラ優先→ステップＳ１０７でスキップ無し→ステップＳ１１０でイントラ符号化を選択しステップＳ１１２でイントラ符号化が行われるパスに対応する。手順６は、ステップＳ１０３でイントラ優先→ステップＳ１０７でスキップ→ステップＳ１１２でイントラ符号化が行われるパスに対応する。

上記６つの手順で、符号化タイプを決定するまでに要する計算量を比較する。比較において、図１のステップＳ１１１とＳ１１２における符号化処理の計算量は除外し、スキップ判定に必要な計算量は無視できるものとする。

図１のステップＳ１０１〜Ｓ１０３の優先符号化タイプの選択に要する計算量をＣ１、
図１のステップＳ１０４またはＳ１０９で必要とする計算量をＣＩＮＴＥＲ、
図１のステップＳ１０５またはＳ１０８で必要とする計算量をＣＩＮＴＲＡとする。

また、
C1 + CINTER+ CINTRA=CFULLとおく。

手順１〜６の計算量は以下の表のようになる。

手順１と手順６は、第２符号化パラメータの探索処理がスキップされるため、他の手順よりも計算量が少ない。手順２〜５の計算量は同等である。

手順Ｎ（Ｎ＝１，２，．．．，６）で符号化されるマクロブロック個数の割合をＰ（Ｎ）で表すと、マクロブロックあたりの平均計算量Ｃは、次式（８）で表される。

C = CFULL −P(1)×CINTRA−P(6)×CINTER ・・・（８）

式（８）から、Ｃは、P(1)とP(6)、すなわち、第２符号化コスト計算がスキップされるマクロブロックの割合を高くすることで削減することが可能である。

以下では、説明を簡単にするため、
CINTER= CINTRA=C2
とする。

また、スキップ率P(1)+P(6)をPSKIPとおく。

平均計算量Ｃは、次式（９）で表される。

C = CFULL −PSKIP×C2 ・・・（９）

式（９）において、スキップ率PSKIP は0以上１以下であるから、平均計算量Cは、(CFULL-C2)以上、CFULL以下の値をとる。

スキップ率PSKIPは、スキップ判定（式（４）、式（５））のパラメータ
αINTER_SKIP、
βINTER_SKIP、
αINTRA_SKIP、
βINTRA_SKIP
により調整することができる。

本実施形態では、スキップされない場合に計算される第２符号化コストはスキップ前に計算される第１符号化コストよりも精度が高いことを仮定しているため、スキップ率を下げると、圧縮効率が向上する。

スキップ率PSKIPを０まで下げると、本実施形態は、第１符号化コストの計算を除いて、図２の第１例と等価な動作になり、圧縮効率も最も高い。

逆に、スキップ率PSKIPを大きくすると、圧縮効率は低下する。PSKIPを最大値の１まで上げると、本実施形態は、図３の第２例と等価な動作になる。

図８は、これらの関係を模式的に示す図であり、横軸を平均演算量（計算量）とし、縦軸を平均的な圧縮効率としたグラフである。圧縮効率は、同一ビットレートにおける画質、または同一画質における圧縮性能を示している。

従来例１（図２の第１例）と従来例２（図３の第２例）は、グラフ内の点で示され、従来例１の圧縮効率と計算量は、従来例２のそれらよりも高い。

本実施形態は、従来例１と従来例２の間を連続的に結ぶ曲線上の一点に相当する。

スキップ率PSKIPの調整により、曲線上を動かすことが可能である。

さらに、スキップ判定条件とスキップ率制御パラメータの関係が適切に設定されているならば、スキップ率PSKIPを０の状態から少しずつ増加させると、スキップさせても、圧縮効率が低下しにくいマクロブロックが優先的にスキップされることになる。このため、本実施形態の計算量と圧縮効率を示す曲線は上に凸な形状になり、計算量の削減に対して圧縮効率の低下が少ない左上側の点をとることができる。

従来例３(図４の第３例)との比較を行う。従来例３のフローを本実施形態に当てはめると、優先符号化タイプとして、常にインターを選択する本実施形態と等価である。このため、インター符号化されるマクロブロック数の多い画像入力に対しては、本実施形態と従来例３の計算量および圧縮効率は変わらない。

しかしながら、イントラ符号化されるマクロブロックが多い画像を入力すると、従来例３では、イントラ符号化コスト計算のスキップ率が低下し計算量が増加する。

これに対して、本実施形態では、インター符号化のスキップ判定が機能するため、従来例３に比べて計算量が増加しない。

これは、本実施形態の計算量が少ないだけでなく、変動が抑制されて安定性が向上することを意味する。

従来例３においても、イントラスキップ判定のパラメータαINTRA_SKIP, βINTRA_SKIPを調整することでスキップ率を高めることが可能である。

しかし、本来は、イントラ符号化すべきマクロブロックをインター符号化することになるため、圧縮効率が低下する。

図８のグラフでは、従来例３の曲線は、本発明の曲線よりも下側に位置する結果になる。

以上説明したように本発明の実施形態によれば、従来手法よりも計算量が少ない、もしくは同一の計算量で圧縮効率の高い動画像符号化を行うことが可能である。

あるいは、入力画像の性質の変化に対して計算量の変動が少ない安定した動画像符号化を行うことが可能である。

図１に処理、図５に構成を示した第１実施形態の動画像符号化装置は、動画像符号化装置を構成するコンピュータ（ＣＰＵ、プロセッサ）上で実行されるコンピュータプログラムでその処理、機能を実現するようにしてもよいことは勿論である。なお、このコンピュータプログラムは、不図示の記録媒体、あるいは他の伝送媒体等からコンピュータの主メモリにロードして実行するようにしてもよく、あるいは、ＲＯＭ等に格納されたファームウエアであってもよい。後述する実施形態についても同様である。

＜第２実施形態＞
次に、本発明の第２実施形態を説明する。第２実施形態に係る動画像符号化装置は第１実施形態に類似した構成である。図５に示す符号化手段を備え、図１に示すフローでマクロブロックの符号化処理が実行される。

本実施形態が第１実施形態と異なる点は、動画像符号化に要する計算量の制御が行われる点である。このため、本実施形態に従う動画像符号化装置は、各フレームの符号化に要する処理時間の目標を設定する手段、処理時間を制御する手段、処理時間を計測する手段を備える。

処理時間制御や符号化効率改良のための計測手段として、本実施形態の装置は、制御部内に判定手順に関連付けられたマクロブロック計数カウンタ（不図示）を６組用意する。

判定手順とは、図１に示すフローでマクロブロックを符号化する際に通過するパスであり、下記の６通りがある。

それぞれの手順を通過したマクロブロック個数を、フレーム単位や、あるいは所定個数のマクロブロック単位で、マクロブロック計数カウンタ（不図示）で計測する。

説明のため、Ｔ番目のフレームの符号化において、手順Ｎ（Ｎ１，２，．．．，６）のパスを通って符号化されたマクロブロックの割合をP(T,N)で表す。

すると、フレームＴの符号化に要する平均計算量C(T)を、P(T,N)を用いて次式（１０）で表すことが可能である。

C(T) = (P(T,1)+ P(T,2)+ P(T,4))×CINTER_FULL
+(P(T,3)+ P(T,5)+ P(T,6))×CINTRA_FULL
−P(T,1)×CINTRA−P(T,6)×CINTER
・・・（１０）

CINTER_FULLとCINTRA_FULLは、スキップ無しでインター符号化を行った場合の平均計算量であり、CINTERとCINTRAはスキップにより削減される平均計算量である。

P(T,N)は、スキップ判定（図１のＳ１０６、Ｓ１０７）のスキップ率制御パラメータαINTER_SKIP, βINTER_SKIP,αINTRA_SKIP, βINTRA_SKIP（式（４）、式（５））を変更することで制御が可能である。

制御パラメータを大きくすると、スキップ率が増加し、小さくすると減少する関係がある。

しかしながら、P(T,N)の値は入力画像の性質に依存して変化するため、目標とする計算量からスキップ率制御パラメータの値を設定することはできない。

動画像の時間相関に着目すると、フレームＴとフレーム（Ｔ＋１）が同じフレームタイプである場合、同一のスキップ率制御パラメータで符号化を行った場合に得られるP(T,N)とP(T+1,N)にも時間相関があると考えられる。

そこで、P(T+1,N)をP(T,N)で予測することで、制御パラメータを修正しない場合の計算量C(T+1)を推定する。

後は、計算量C(T+1)の推測結果と目標値の差分を評価して、目標値が推測値よりも大きい場合はスキップ率を高める調整を行い、逆の場合は、スキップ率を小さくする制御を行う。

本実施形態では、以上に加えて、符号化タイプ判定の精度を向上させるために、優先符号化タイプ選択（図１のＳ１０３）判定式のパラメータα1, β1（式（３））を調整する。

α1, β1を大きくすると、インター符号化タイプが選択され易くなり、α1, β1を小さくすると、イントラ符号化タイプが選択され易くなる。

手順１乃至手順６の６種類の符号化タイプ判定手順の中で、優先符号化タイプと、実際に符号化されたタイプが異なる手順３と手順４は、優先符号化タイプの判定を間違えていた場合の実行パスであり、これにより優先符号化タイプ判定の誤り率を計測できる。

そこで、インターの選択誤り率とイントラの選択誤り率の差を評価して、この差が大きい場合は誤り率の高いタイプが選択されにくくなるようにα1, β1を調整する。

具体的には、次式（１１）が閾値よりも大きい場合に、α1、β1を微小に下げ、次式（１１）が閾値よりも小さい場合には、α1、 β1を少し大きくする。

・・・（１１）

図９は、本実施形態に従う動画像符号化装置が１フレームを符号化する際の処理フローを示す図である。図９において、２重線で囲まれたステップＳ１００１、Ｓ１００５、Ｓ１００７、Ｓ１００８は、通常の動画像符号化と変わらない処理である。その他のステップは、計算量を制御するための処理である。

具体的に手順を説明する。本実施形態に従う符号化装置は、ステップＳ１００１のフレーム符号化開始処理において、１フレームを符号化するために必要な処理を行う。これは、フレームの符号化パラメータ設定、符号量制御の設定、制御変数や作業領域の確保や初期化、フレームヘッダ出力処理など、通常必要とされる様々な符号化開始処理を含む。

次にステップＳ１００２の目標演算量設定において、当該フレームの符号化に関する目標処理時間と最大処理時間を設定し、それに合わせて、スキップ率制御パラメータを調整する。目標時間と最大時間は、画像シーケンス全体で目標とする平均演算量、これまでのフレーム符号化に要した処理時間の合計、バッファリングにより許容される遅延時間、外部要因による時間制約を考慮して決定される。

ステップＳ１００３の判定手順計数カウンタクリアにおいて、判定手順に関連付けられたマクロブロック計数カウンタを０にクリアする。

ステップＳ１００４からＳ１００７は、マクロブロック符号化処理の繰り返しであるフレーム内のマクロブロック個数だけ、ステップＳ１００４乃至ステップＳ１００６の処理を繰り返す。

ステップＳ１００４の判定パラメータ調整処理は、スキップ率制御パラメータをマクロブロック毎に更新する処理である。ステップＳ１００２において設定したパラメータでは、処理時間を目標通りに制御できず、最大処理時間を超過する可能性が高い場合や、外部要因により処理時間制約を変更したい場合に更新を行う。

ステップＳ１００５のマクロブロック符号化処理では、マクロブロックを実際に符号化する。その手順については、前記第１実施形態で説明した通りである。

ステップＳ１００６の判定手順計数カウンタをインクリメントは、ステップＳ１００５でマクロブロックを符号化した結果、実際に通過した判定手順に対応するマクロブロック計数カウンタを１増やす。

ステップＳ１００７で最後のマクロブロックの符号化が終了したか否かを判定し、全てのマクロブロックの符号化が終了すると、ステップＳ１００８のピクチャ符号化終了処理において、フレーム出力終了に必要な処理を実行する。フレームフッタの出力、制御変数の更新、作業領域の解放などを行う。また必要であれば、ローカルデコード画像にループフィルタを施す処理も実行する。

以上のフレーム符号化処理を完了すると、ステップＳ１００９の計算量制御状態更新において当該フレームの符号化に要した時間を推定し、処理時間を管理する手段の内部状態を更新する。

また、優先符号化タイプ選択の誤り率をもとに、優先タイプ選択のパラメータα1, β1を調整する。

なお、以上説明した実施例において、スキップ率制御パラメータαINTER_SKIP, βINTER_SKIP,αINTRA_SKIP, βINTRA_SKIPの調整については、別の方法であっても構わない。

例えば、設定したスキップ率パラメータと、その結果得られたスキップ率の履歴を複数個のマクロブロックやフレーム単位で残しておき、これを利用する方法がある。過去のパラメータとスキップ率の相関関係から、パラメータ変更後のスキップ率を予測し、これが目標量に近くなるよう、αINTER_SKIP, βINTER_SKIPを調整する。

あるいは、式（５）のスキップ判定で利用したRD_cost_intra2とRD_cost_inter1の数値に関するヒストグラムを作成し、この結果に基づいてパラメータ変更後のスキップ率を予測する方法がある。これは、パラメータとスキップ率の相関にもとづく前記の方法よりも、より正確な予測が可能である。

ここで、ヒストグラムの計測区間は、フレーム単位でなく複数のフレームであっても構わない。あるいは、複数個のマクロブロックでも構わない。ヒストグラムを算出する際の数値に関する区間の大きさも適当に選択可能である。

ヒストグラム化する数値については、RD_cost_intra2とRD_cost_inter1のペアに関する２次元数値ではなく、２つの値の差もしくは比に関する１次元数値のヒストグラムを作成する方法でも構わない。

他には、以前に説明したように、スキップ判定条件に、乱数やマクロブロック番号の剰余を導入することで、スキップ率の制御を容易にする方法も有力である。

以上と同様に、優先符号化タイプ選択判定式のパラメータα1, β1に関しても、本実施例とは異なる調整方法を利用してもよい。

例えば、式（３）、式（４）、式（５）とスキップされなかった場合の符号化タイプ判定で利用された数値RD_cost_inter1, RD_cost_intra1,RD_cost_inter2, RD_cost_intra2に関するヒストグラムを作成し、このヒストグラムに基づいて式（１１）が０に近くなるようにパラメータα1,β1を決定するのが一つの方法である。

以上説明したように、第２実施形態にもとづく動画像符号化装置は、計算量を制御するパラメータ調整手段と計算量を測定する手段を備えるため、計算量を動的に制御することが可能である。

また、優先符号化タイプの選択誤り率を測定した結果を、選択判定式の調整に利用するため、圧縮効率を向上させることが可能である。

＜第３実施形態＞
本発明の第３実施形態を説明する。本発明の第３実施形態に係る動画像符号化装置は、前記した第２実施形態に類似した構成であり動作も類似しているため、相違点のみを説明する。

図１０は、本実施形態に係る動画像符号化装置のフレーム符号化の手順を示す図である。図１１は、本実施形態におけるマクロブロックの符号化処理の手順を示す図である。前記第２実施形態のフレーム符号化手順を示した図９と、本実施形態の手順を示した図１０との相違点は、ステップＳ１１０２〜Ｓ１１０３の繰り返し処理で、第１符号化コストの計算を事前に１フレーム分まとめて計算する点であり、その結果、ステップＳ１１０６におけるマクロブロック符号化処理が、図１１に示す手順に修正される。

前記第２実施形態のマクロブロック符号化処理手順を示す図１と、図１１との相違点は、図１１においては、第１インター符号化コスト計算、第１イントラ符号化コスト計算を実行しない点である。

本実施形態では、第１符号化コスト(RD_cost_intra1、 RD_cost_inter1)を、予め１フレーム分計算するため、フレーム内の優先符号化タイプの分布を事前に知ることが可能である。

この結果を利用すれば、これから実行する符号化処理の計算量制御をより正確にすることが可能である。

例えば前記第２実施形態では、フレーム（Ｔ＋１）の計算量Ｃ（Ｔ＋１）を、フレームＴの符号化結果から予測するために、
P(T+1,N)≒P(T,N)
であることを仮定して予測が行われる。

P(T,N)は、タイプ判定手順Ｎ（Ｎ１，２，．．．，６）のパスを通って符号化されるマクロブロック数の割合である。

本発明の第３実施形態では、優先符号化タイプの出現割合の変化率を基にして、P(T+1,N)の予測値を補正する。

予測式を次式（１２）に示す。

・・・（１２）

QINTER(T), QINTRA(T)は、フレームＴにおける優先符号化タイプ出現率であり、
QINTER(T)=P(T,1)+ P(T,2)+ P(T,3),
QINTRA(T)=P(T,4)+ P(T,5)+ P(T,6)
・・・（１３）
である。

他には、RD_cost_intra1とRD_cost_inter1の差分が閾値よりも小さい、または比が１に近いマクロブロック数をフレーム単位で計数することで、第２符号化コスト計算のスキップ率変化を事前に予測することが可能である。

スキップ率が急上昇する可能性が高い場合は、スキップ率が高まるようにスキップ判定のパラメータを調整することで、計算量が目標値よりも極端に大きくなることを防ぐことができる。

なお、本実施形態を説明する例では、事前に第１符号化コストを計算するマクロブロックの個数を１フレーム分としたが、これは、１フレームに満たない複数個のマクロブロックであっても、複数のフレームにまたがる複数個の小ブロックであっても適用可能である。理想的には、事前計算する個数を増やすほど、安定した計算量制御が可能になる。

以上、本実施形態による動画像符号化装置は、第１符号化コストの事前計算により、計算量制御を安定化させる効果がある。

本発明の実施形態の作用効果について説明する。

符号化コスト計算を、計算量の少ない第１符号化コスト計算と、より精度の高い第２符号化コスト計算の２つに分割しておき、当該小ブロックを符号化する際、始めに、各々の符号化タイプに関する第１符号化コストを計算し、得られた結果に基づいて、優先符号化タイプを１つ選択する。次に、優先選択された符号化タイプに関する第２符号化コストだけを計算し、得られた結果によっては優先タイプ以外の符号化タイプに関する第２符号化コスト計算をスキップする。

これにより、第１符号化コストの計算だけで符号化タイプを決定可能な小ブロックに対しては、第２符号化コスト計算のスキップにより計算量を削減し、判定が難しいブロックに対しては、第２符号化コストを計算して正確な選択を行う。

その結果、本発明による動画像符号化方法、装置は、従来手法よりも、計算量と圧縮効率の両面でバランスが取れた符号化方法となっている。

また、本発明による動画像符号化方法、装置においては、イントラ、インター双方の符号化タイプに関して、第２符号化コスト計算のスキップ判定を行っている。

これにより、本発明による動画像符号化方法、装置においては、入力画像内での符号化タイプ分布が変動しても、計算量の変動が少なく抑えられる効果がある。

さらに本発明による動画像符号化方法、装置においては、第２符号化コスト計算のスキップ率と相関を持つスキップ率制御パラメータを備え、このスキップ率制御パラメータを、当該小ブロックの符号化に利用可能な計算量の割当に応じて制御する。

これにより、本発明による動画像符号化方法は、計算量と圧縮効率のバランスを制御し、計算量の変動を安定化させる効果がある。

さらに本発明による動画像符号化方法、装置においては、各々の符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２符号化コスト計算がスキップされた小ブロックの個数と、優先タイプとして選択された上で第２符号化コスト計算がスキップされずに優先符号化タイプと異なるタイプで符号化された小ブロックの個数を計数した結果を、前記スキップ率制御パラメータの制御に利用する。

これにより符号化に要する計算量の推定が可能になるため、本発明による動画像符号化方法は、計算量の制御が安定する効果がある。

さらに本発明による動画像符号化方法、装置においては、各々の符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２符号化コスト計算がスキップされた小ブロックの個数と、優先タイプとして選択された上で第２符号化コスト計算がスキップされずに優先符号化タイプと異なるタイプで符号化された小ブロックの個数を計数した結果を、優先符号化タイプ選択基準の調整に利用する。

これにより優先符号化タイプ選択の誤りを補正できるため、本発明による動画像符号化方法は、符号化効率を高める効果がある。

さらに本発明による動画像符号化方法、装置においては、当該小ブロックよりも後で符号化される１個以上の小ブロックに対して、各々の符号化タイプに関する第１符号化コストを予め計算し、得られた結果を、優先符号化タイプの選択とスキップ率制御パラメータの制御に利用する。

これにより、これから符号化する１個以上の小ブロックに対して、各々のタイプの出現頻度とタイプ判定が難しい小ブロックの出現率が推定できるため、本発明による動画像符号化方法は、計算量の制御を安定化させる効果がある。

以上、本発明を上記実施例に即して説明したが、本発明は上記実施例の構成にのみ制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。

本発明の第１実施形態に係る符号化タイプ判定手順を示すフロー図である。従来例１の符号化タイプ判定手順を示すフロー図である。従来例２の符号化タイプ判定手順を示すフロー図である。従来例３の符号化タイプ判定手順を示すフロー図である。本発明の第１実施形態に係る動画像符号化装置の構成を示す図である。Ｈ．２６４方式におけるインター予測のサブブロック分割モードを説明する模式図である。Ｈ．２６４方式におけるイントラ予測のサブブロック分割モードを説明する模式図である。従来例と本発明の計算量と圧縮効率を比較して説明するための図である。本発明の第２実施形態に係る動画像符号化装置の処理手順を示すフロー図である。本発明の第３実施形態に係る動画像符号化装置の処理手順を示すフロー図である。本発明の第３実施形態に係る符号化タイプ判定手順を示すフロー図である。

符号の説明

５０１入力画像蓄積手段
５０２小ブロック分割手段
５０４ローカルデコード画像蓄積手段
５０５制御手段
５０６第１インター符号コスト・パラメータ決定手段
５０７第１インター符号コスト・パラメータ決定手段
５０８インター符号化手段
５０９第１イントラ符号コスト・パラメータ決定手段
５１０第２イントラ符号コスト・パラメータ決定手段
５１１イントラ符号化手段
５１２符号化タイプ選択部

Claims

動画像を小ブロックに分割しイントラ符号化とインター符号化のいずれかを用いて符号化する動画像符号化方法であって、前記小ブロックを符号化する際、
インター及びイントラの各々のタイプで符号化する場合の第１の符号化コストを計算し、
得られた第１の符号化コストの結果に基づき優先符号化タイプを１つ選択し、
前記優先符号化タイプで符号化される場合の第２の符号化コストを計算し、
得られた結果に基づいて前記優先符号化タイプ以外のタイプに関する第２の符号化コスト計算をスキップするか否か判定し、判定の結果、前記第２の符号化コスト計算をスキップする場合には、前記小ブロックを、選択された前記優先符号化タイプで符号化する、ことを特徴とする、動画像符号化方法。
前記各々のタイプで符号化する場合の前記第１の符号化コストの算出に要する計算量が、前記第２の符号化コストの算出に要する計算量よりも少ない、ことを特徴とする、請求項１に記載の動画像符号化方法。
（ａ）前記優先符号化タイプとしてイントラ符号化とインター符号化のいずれか一方を選択し、
（ｂ）前記優先符号化タイプとしてイントラ符号化が選択された場合、イントラタイプに関する第２の符号化コストを計算し、
（ｃ）前記ステップ(ｂ)で得られた第２の符号化コストの値と、インタータイプで符号化する場合の前記第１の符号化コストの値から、インタータイプで符号化する場合の第２の符号化コストの計算をスキップするか否か判定し、
（ｄ）前記ステップ（ｃ）での判定の結果、インタータイプで符号化する場合の第２の符号化コスト計算をスキップする場合は、前記小ブロックの符号化タイプとしてイントラ符号化を選択し、
（ｅ）前記ステップ（ｃ）での判定の結果、インタータイプで符号化する場合の第２の符号化コスト計算をスキップしない場合には、インタータイプで符号化する場合の第２の符号化コストを計算し、
（ｆ）前記ステップ(ｅ)で得られたインタータイプに関する第２の符号化コストの値と、前記ステップ（ｂ）で得られたイントラタイプに関する第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプとして、インター又はイントラ符号化を選択し、
（ｇ）前記ステップ（ａ）で前記優先符号化タイプとしてインタータイプが選択された場合、インタータイプに関する第２の符号化コストを計算し、
（ｈ）前記ステップ（ｇ）で得られたインタータイプに関する第２の符号化コストの値と、イントラタイプで符号化する場合の前記第１の符号化コストの値から、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップするか否か判定し、
（ｉ）前記ステップ（ｈ）の判定の結果、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップする場合には、前記小ブロックの符号化タイプとしてインタータイプを選択し、
（ｊ）前記ステップ（ｈ）の判定の結果、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップしない場合には、イントラタイプで符号化する場合の第２の符号化コストを計算し、
（ｋ）前記ステップ（ｊ）で得られたイントラタイプに関する第２の符号化コストの値と、前記ステップ（ｇ）で得られたインタータイプに関する第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプとして、インター又はイントラ符号化を選択する、ことを特徴とする、請求項１に記載の動画像符号化方法。
前記第２の符号化コスト計算のスキップ率と相関を持つスキップ率制御パラメータを、符号化タイプ毎に備え、
前記小ブロックの符号化に利用可能な計算量又は処理時間の割当に応じて、前記制御パラメータを調整することで、符号化に要する計算量を制御する、ことを特徴とする、請求項１乃至３のいずれか一に記載の動画像符号化方法。
符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で、第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を、前記スキップ率制御パラメータの制御に利用する、ことを特徴とする、請求項４に記載の動画像符号化方法。
符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を利用して、前記優先符号化タイプの選択条件を修正する、ことを特徴とする、請求項４に記載の動画像符号化方法。
符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数を計数した結果を、前記スキップ率制御パラメータの制御に利用する、ことを特徴とする、請求項４に記載の動画像符号化方法。
符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数とを計数した結果を利用して、前記優先符号化タイプの選択条件を修正する、ことを特徴とする、請求項４に記載の動画像符号化方法。
前記小ブロックよりも後で符号化される１個以上の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する、ことを特徴とする、請求項４に記載の動画像符号化方法。
前記小ブロックを含む複数個の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する、ことを特徴とする、請求項９に記載の動画像符号化方法。
前記インター及びイントラの各々のタイプで符号化する場合の第１の符号化コストを、予め１フレーム分計算しておく、ことを特徴とする、請求項１に記載の動画像符号化方法。
前記優先符号化タイプとしてインター符号化が選択され、イントラタイプで符号化する場合の第２の符号化コスト計算をスキップし、前記小ブロックの符号化タイプとしてインター符号化を選択する第１の手順と、
インター符号化が優先符号化タイプとして選択され、インタトラタイプで符号化する場合の第２の符号化コスト計算をスキップせず、イントラタイプに関する前記第２の符号化コストの値と、インタータイプに関する前記第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプとしてインター符号化を選択する第２の手順、又はイントラ符号化を選択する第３の手順と、
前記優先符号化タイプとしてイントラ符号化が選択され、インタータイプで符号化する場合の第２の符号化コスト計算をスキップし、前記小ブロックの符号化タイプとしてイントラ符号化を選択する第４の手順と、
前記優先符号化タイプとしてイントラ符号化が選択され、インタータイプで符号化する場合の第２の符号化コスト計算をスキップせず、インタータイプに関する前記第２の符号化コストの値と、イントラタイプに関する前記第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプとして、インター符号化を選択する第５の手順、又はイントラ符号化を選択する第６の手順について、
それぞれの前記手順を通過した前記小ブロックの個数を、フレーム単位やあるいは所定個数の小ブロック単位で計数カウンタで計測し、前記手順のパスを通過して符号化された前記小ブロックの個数の割合より１フレームの符号化に要する平均計算量を導出する、ことを特徴とする、請求項７乃至１０のいずれか一に記載の動画像符号化方法。
動画像を小ブロックに分割しイントラ符号化とインター符号化のいずれかを用いて符号化する動画像符号化装置であって、
インター符号する場合の第１及び第２の符号化コストをそれぞれ計算する第１及び第２のインター符号化コストパラメータ決定手段と、
イントラ符号化する場合の第１及び第２の符号化コストをそれぞれ計算する第１及び第２のイントラ符号化コストパラメータ決定手段と、
前記小ブロックをインター符号化するインター符号化手段と、
前記小ブロックをイントラ符号化するイントラ符号化手段と、
制御手段と、
を備え、
前記小ブロックを符号化する際、
前記制御手段は、前記第１インター符号化コストパラメータ決定手段と前記第１イントラ符号化コストパラメータ決定手段での各第１の符号化コストの結果に基づき、優先符号化タイプとして、インター又はイントラ符号化を選択し、
前記第２インター符号化コストパラメータ決定手段と前記第２イントラ符号化コストパラメータ決定手段のうち選択された前記優先符号化タイプに対応する一方が第２の符号化コストを計算し、
得られた第２の符号化コストの計算結果に基づいて、前記第２インター符号化コストパラメータ決定手段と前記第２イントラ符号化コストパラメータ決定手段のうち前記優先符号化タイプとして選択されなかった他方のタイプに対応する他方による第２の符号化コスト計算をスキップするか否か判定し、判定の結果、前記第２の符号化コスト計算をスキップする場合には、前記第２インター符号化コストパラメータ決定手段と前記第２イントラ符号化コストパラメータ決定手段のうち前記優先符号化タイプとして選択されなかった他方のタイプに対応する他方による第２の符号化コスト計算を省略して、前記小ブロックを、前記優先符号化タイプである、インター又はイントラタイプに対応した符号化手段で符号化する、ことを特徴とする、動画像符号化装置。
前記第１の符号化コストの算出に要する計算量が、前記第２の符号化コストの算出に要する計算量よりも少ない、ことを特徴とする、請求項１３に記載の動画像符号化装置。
前記制御手段は、前記優先符号化タイプとしてイントラ符号化とインター符号化のいずれか一方を選択し、
イントラ符号化が前記優先符号化タイプとして選択された場合、前記第２のイントラ符号化コストパラメータ決定手段にて第２の符号化コストを計算し、
前記制御手段は、
前記第２のイントラ符号化コストパラメータ決定手段による第２の符号化コストの値と、前記第１のインター符号化コストパラメータ決定手段による前記第１の符号化コストの値とから、前記第２のインター符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップするか否か判定し、
前記判定の結果、前記第２のインター符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップする場合には、前記小ブロックの符号化タイプとして、イントラを選択し、
前記判定の結果、前記第２のインター符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップしない場合には、前記第２のインター符号化コストパラメータ決定手段にて第２の符号化コストを計算し、
前記第２のインター符号化コストパラメータ決定手段による前記第２の符号化コストの値と、前記第２のイントラ符号化コストパラメータ決定手段による前記第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプを選択し、
前記優先符号化タイプとして、インタータイプが選択された場合、前記第２のインター符号化コストパラメータ決定手段にて第２の符号化コストを計算し、
前記第２のインター符号化コストパラメータ決定手段による第２の符号化コストの値と前記第１のイントラ符号化コストパラメータ決定手段による第１の符号化コストの値とから、前記第２のイントラ符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップするか否か判定し、
前記判定の結果、前記第２のイントラ符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップする場合には、前記小ブロックの符号化タイプとしてインタータイプを選択し、
前記第２のイントラ符号化コストパラメータ決定手段による第２の符号化コストの計算をスキップしない場合には、前記第２のイントラ符号化コストパラメータ決定手段にて第２の符号化コストを計算し、
前記第２のイントラ符号化コストパラメータ決定手段による第２の符号化コストの値と前記第２のインター符号化コストパラメータ決定手段による第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプを選択する、ことを特徴とする、請求項１３に記載の動画像符号化装置。
前記制御手段は、前記第２の符号化コスト計算のスキップ率と相関を持つスキップ率制御パラメータを、符号化タイプ毎に備え、前記小ブロックの符号化に利用可能な計算量又は処理時間の割当に応じて、前記制御パラメータを調整することで、符号化に要する計算量を制御する、ことを特徴とする、請求項１３乃至１５のいずれか一に記載の動画像符号化装置。
前記制御手段は、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で、第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を、前記スキップ率制御パラメータの制御に利用する、ことを特徴とする、請求項１６に記載の動画像符号化装置。
前記制御手段は、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を利用して、前記優先符号化タイプの選択条件を修正する、ことを特徴とする、請求項１６に記載の動画像符号化装置。
前記制御手段は、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数を計数した結果を、前記スキップ率制御パラメータの制御に利用する、ことを特徴とする、請求項１６に記載の動画像符号化装置。
前記制御手段は、符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数とを計数した結果を利用して、前記優先符号化タイプの選択条件を修正する、ことを特徴とする、請求項１６に記載の動画像符号化装置。
前記制御手段は、前記小ブロックよりも後で符号化される１個以上の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する、ことを特徴とする、請求項１６に記載の動画像符号化装置。
前記制御手段は、前記小ブロックを含む複数個の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する、ことを特徴とする、請求項２１に記載の動画像符号化装置。
前記優先符号化タイプとしてインター符号化が選択され、イントラタイプで符号化する場合の第２の符号化コスト計算をスキップし、前記小ブロックの符号化タイプとしてインター符号化を選択する第１の手順と、
インター符号化が優先符号化タイプとして選択され、インタトラタイプで符号化する場合の第２の符号化コスト計算をスキップせず、イントラタイプに関する前記第２の符号化コストの値と、インタータイプに関する前記第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプとしてインター符号化を選択する第２の手順、又はイントラ符号化を選択する第３の手順と、
前記優先符号化タイプとしてイントラ符号化が選択され、インタータイプで符号化する場合の第２の符号化コスト計算をスキップし、前記小ブロックの符号化タイプとしてイントラ符号化を選択する第４の手順と、
前記優先符号化タイプとしてイントラ符号化が選択され、インタータイプで符号化する場合の第２の符号化コスト計算をスキップせず、インタータイプに関する前記第２の符号化コストの値と、イントラタイプに関する前記第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプとして、インター符号化を選択する第５の手順、又はイントラ符号化を選択する第６の手順について、
それぞれの前記手順を通過した前記小ブロックの個数を、フレーム単位やあるいは所定個数の小ブロック単位で計数カウンタで計測し、前記手順のパスを通過して符号化された前記小ブロックの個数の割合より１フレームの符号化に要する平均計算量を導出する、ことを特徴とする、請求項１７乃至２０のいずれか一に記載の動画像符号化装置。
動画像を小ブロックに分割しイントラ符号化とインター符号化のいずれかを用いて符号化する動画像符号化装置を構成するコンピュータに、
前記小ブロックを符号化する際、
インター及びイントラの各々のタイプで符号化する場合の第１の符号化コストを計算し、
得られた第１の符号化コストの結果に基づき優先符号化タイプを１つ選択する処理と、
前記優先符号化タイプで符号化される場合の第２の符号化コストを計算する処理と、
得られた結果に基づいて前記優先符号化タイプ以外のタイプに関する第２の符号化コスト計算をスキップするか否か判定し、判定の結果、前記第２の符号化コスト計算をスキップする場合には、前記小ブロックを、選択された前記優先符号化タイプで符号化する処理と、
を実行させるプログラム。
前記各々のタイプで符号化する場合の前記第１の符号化コストの算出に要する計算量が、前記第２の符号化コストの算出に要する計算量よりも少ない、ことを特徴とする請求項２４記載のプログラム。
請求項２４記載のプログラムにおいて、
（ａ）前記優先符号化タイプとしてイントラ符号化とインター符号化のいずれか一方を選択する処理と、
（ｂ）前記優先符号化タイプとしてイントラ符号化が選択された場合、イントラタイプに関する第２の符号化コストを計算する処理と、
（ｃ）前記ステップ(ｂ)で得られた第２の符号化コストの値と、インタータイプで符号化する場合の前記第１の符号化コストの値から、インタータイプで符号化する場合の第２の符号化コストの計算をスキップするか否か判定する処理と、
（ｄ）前記ステップ（ｃ）での判定の結果、インタータイプで符号化する場合の第２の符号化コスト計算をスキップする場合は、前記小ブロックの符号化タイプとしてイントラ符号化を選択する処理と、
（ｅ）前記ステップ（ｃ）での判定の結果、インタータイプで符号化する場合の第２の符号化コスト計算をスキップしない場合には、インタータイプで符号化する場合の第２の符号化コストを計算する処理と、
（ｆ）前記ステップ(ｅ)で得られたインタータイプに関する第２の符号化コストの値と、前記ステップ（ｂ）で得られたイントラタイプに関する第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプとして、インター又はイントラ符号化を選択する処理と、
（ｇ）前記ステップ（ａ）で前記優先符号化タイプとしてインタータイプが選択された場合、インタータイプに関する第２の符号化コストを計算する処理と、
（ｈ）前記ステップ（ｇ）で得られたインタータイプに関する第２の符号化コストの値と、イントラタイプで符号化する場合の前記第１の符号化コストの値から、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップするか否か判定する処理と、
（ｉ）前記ステップ（ｈ）の判定の結果、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップする場合には、前記小ブロックの符号化タイプとしてインタータイプを選択する処理と、
（ｊ）前記ステップ（ｈ）の判定の結果、イントラタイプで符号化する場合の第２の符号化コストの計算をスキップしない場合には、イントラタイプで符号化する場合の第２の符号化コストを計算する処理と、
（ｋ）前記ステップ（ｊ）で得られたイントラタイプに関する第２の符号化コストの値と、前記ステップ（ｇ）で得られたインタータイプに関する第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプとして、インター又はイントラ符号化を選択する処理と
を前記コンピュータに実行させるプログラム。
請求項２４乃至２６のいずれか一に記載のプログラムにおいて、
前記第２の符号化コスト計算のスキップ率と相関を持つスキップ率制御パラメータを、符号化タイプ毎に備え、
前記小ブロックの符号化に利用可能な計算量又は処理時間の割当に応じて、前記制御パラメータを調整することで、符号化に要する計算量を制御する処理を前記コンピュータに実行させるプログラム。
請求項２７に記載のプログラムにおいて、
符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で、第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を、前記スキップ率制御パラメータの制御に利用する処理を前記コンピュータに実行させるプログラム。
請求項２７に記載のプログラムにおいて、
符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされた小ブロックの個数と、を計数した結果を利用して、前記優先符号化タイプの選択条件を修正する処理を前記コンピュータに実行させるプログラム。
請求項２７に記載のプログラムにおいて、
符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数を計数した結果を、前記スキップ率制御パラメータの制御に利用する処理を前記コンピュータに実行させるプログラム。
請求項２７に記載のプログラムにおいて、
符号化タイプに関し、そのタイプが優先符号化タイプとして選択された小ブロックの個数と、優先タイプとして選択された上で第２の符号化コスト計算がスキップされず、そのタイプと異なるタイプで符号化された小ブロックの個数とを計数した結果を利用して、前記優先符号化タイプの選択条件を修正する処理を前記コンピュータに実行させるプログラム。
請求項２７に記載のプログラムにおいて、
前記小ブロックよりも後で符号化される１個以上の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する処理を前記コンピュータに実行させるプログラム。
請求項３２に記載のプログラムにおいて、
前記小ブロックを含む複数個の小ブロックに対して、各々の符号化タイプに関する第１の符号化コストを計算して得られた結果を、前記優先符号化タイプの選択と前記スキップ率制御パラメータの制御に利用する、処理を前記コンピュータに実行させるプログラム。
請求項２９乃至３１のいずれか一に記載のプログラムにおいて、
前記優先符号化タイプとしてインター符号化が選択され、イントラタイプで符号化する場合の第２の符号化コスト計算をスキップし、前記小ブロックの符号化タイプとしてインター符号化を選択する第１の手順と、
インター符号化が優先符号化タイプとして選択され、インタトラタイプで符号化する場合の第２の符号化コスト計算をスキップせず、イントラタイプに関する前記第２の符号化コストの値と、インタータイプに関する前記第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプとしてインター符号化を選択する第２の手順、又はイントラ符号化を選択する第３の手順と、
前記優先符号化タイプとしてイントラ符号化が選択され、インタータイプで符号化する場合の第２の符号化コスト計算をスキップし、前記小ブロックの符号化タイプとしてイントラ符号化を選択する第４の手順と、
前記優先符号化タイプとしてイントラ符号化が選択され、インタータイプで符号化する場合の第２の符号化コスト計算をスキップせず、インタータイプに関する前記第２の符号化コストの値と、イントラタイプに関する前記第２の符号化コストの値とに基づいて、前記小ブロックの符号化タイプとして、インター符号化を選択する第５の手順、又はイントラ符号化を選択する第６の手順について、
それぞれの前記手順を通過した前記小ブロックの個数を、フレーム単位やあるいは所定個数の小ブロック単位で計数する処理と、
前記手順のパスを通過して符号化された前記小ブロックの個数の割合より１フレームの符号化に要する平均計算量を導出する処理と、
を前記コンピュータに実行させるプログラム。