(57)【要約】【課題】符号化効率の高い符号化構造を低演算量で求めること。【解決手段】入力映像情報から取得されるフレーム群から、予め定められる３枚以上の枚数の連続するフレームを含む参照グループを生成し、生成する参照グループの最初と最後のフレームの間のいずれか１つの判定対象フレームと、最初と最後のフレームとの参照関係を結合するか否かを判定し、判定結果に基づいて、フレーム群に含まれるフレームのピクチャタイプを選定し、結合すると判定された参照グループの最初のフレーム、または最後のフレームが判定対象フレームとなるように、当該参照グループを含み予め定められる３枚以上の枚数よりも多い枚数の連続するフレームを含む新たな参照グループを生成する。【選択図】図２
2018182394.tif 000002
【特許請求の範囲】
【請求項１】
フレーム間予測符号化を行う映像符号化装置であって、
入力映像情報から取得されるフレーム群から、予め定められる３枚以上の枚数の連続するフレームを含む参照グループを生成する参照グループ生成部と、
前記参照グループ生成部が生成する前記参照グループの最初と最後の前記フレームの間のいずれか１つの判定対象フレームと、最初と最後の前記フレームとの参照関係を結合するか否かを判定する結合判定部と、
前記結合判定部の判定結果に基づいて、前記フレーム群に含まれる前記フレームのピクチャタイプを選定するピクチャタイプ選定部と、を備え、
前記参照グループ生成部は、
前記結合判定部により結合すると判定された前記参照グループの最初の前記フレーム、または最後の前記フレームが前記判定対象フレームとなるように、当該参照グループを含み前記予め定められる３枚以上の枚数よりも多い枚数の連続するフレームを含む新たな前記参照グループを生成する映像符号化装置。
【請求項２】
前記参照グループ生成部は、
隣接する２つの前記参照グループの双方において前記結合判定部が前記判定対象フレームと最初と最後の前記フレームとの参照関係を結合すると判定する場合、前記隣接する２つの前記参照グループを結合して前記新たな参照グループを生成し、隣接する２つの前記参照グループの各々の前記判定対象フレームの参照先となる最初と最後の前記フレームのうち重複する前記フレームを前記新たな参照グループの前記判定対象フレームとする、請求項１に記載の映像符号化装置。
【請求項３】
前記参照グループ生成部は、
前記フレーム群の先頭の前記フレームを起点として前記予め定められる３枚以上の枚数の連続するフレームを含む前記参照グループを最初の前記参照グループとして生成し、
前記結合判定部が、前記参照グループの前記判定対象フレームと最初と最後の前記フレームとの参照関係を結合すると判定する場合、当該参照グループの最後の前記フレームを起点として前記予め定められる３枚以上の枚数の連続するフレームを含む隣接する前記参照グループを生成し、
前記結合判定部が、前記参照グループの前記判定対象フレームと前記最初と最後のフレームとの参照関係を結合しないと判定する場合、前記判定対象フレームを起点として前記予め定められる３枚以上の枚数の連続するフレームを含む隣接する前記参照グループを生成し、
前記隣接する２つ前記参照グループを結合して前記新たな参照グループを生成する場合、前記新たな参照グループの最後のフレームを起点として前記予め定められる３枚以上の枚数の連続するフレームを含む隣接する前記参照グループを生成する、請求項２に記載の映像符号化装置。
【請求項４】
前記参照グループ生成部は、
前記参照グループに隣接する他の参照グループを生成する際、当該参照グループの最後の前記フレームが、前記隣接する他の参照グループの最初の前記フレームとなるように重複させて前記予め定められる３枚以上の枚数の連続するフレームを含む前記参照グループを生成する、請求項２に記載の映像符号化装置。
【請求項５】
前記入力映像情報から前記フレーム群を取得し、取得した前記フレーム群の最初のフレームをＩピクチャとして選定するＩピクチャ選定部を備え、
前記ピクチャタイプ選定部は、
前記結合判定部が、前記判定対象フレームと前記最初と最後のフレームとの参照関係を結合すると判定する場合、前記判定対象フレームを前記最初と最後のフレームを参照フレームとするＢピクチャとして選定し、
前記Ｉピクチャ、または前記Ｂピクチャとして選定されていない前記フレームを前記Ｐピクチャとして選定し、前記フレーム群の表示順において、選定した前記フレームに最も近い過去の前記Ｐピクチャの前記フレームを、選定した前記フレームの前記参照フレームとし、選定した前記フレームに最も近い過去の前記Ｐピクチャの前記フレームがない場合、前記Ｉピクチャの前記フレームを、選定した前記フレームの前記参照フレームとする、請求項１から４のいずれか一項に記載の映像符号化装置。
【請求項６】
前記予め定められる３枚以上の枚数は、３枚である、請求項１から５のいずれか一項に記載の映像符号化装置。
【請求項７】
フレーム間予測符号化を行う映像符号化装置であって、
入力映像情報から取得されるフレーム群から、３枚の連続するフレームを含む参照グループを生成する参照グループ生成部と、
前記参照グループ生成部が生成する前記参照グループの最初と最後の前記フレームの間の判定対象フレームと、前記最初と最後のフレームとの参照関係を結合するか否かを判定する結合判定部と、
前記結合判定部の判定結果に基づいて、前記フレーム群に含まれる前記フレームのピクチャタイプを選定するピクチャタイプ選定部と、
を備える映像符号化装置。
【請求項８】
フレーム間予測符号化を行う映像符号化装置であって、
入力映像情報から取得されるフレーム群から、３枚の連続するフレームを含む参照グループを生成する参照グループ生成部と、
前記参照グループ生成部が生成する前記参照グループの最初と最後の前記フレームの間の判定対象フレームと、前記最初と最後のフレームとの参照関係を結合するか否かを判定する結合判定部と、
前記結合判定部の判定結果に基づいて、前記フレーム群に含まれる前記フレームのピクチャタイプを選定するピクチャタイプ選定部と、を備え、
前記参照グループ生成部は、
前記結合判定部により結合すると判定された２つの前記参照グループにおいて、各々の前記判定対象フレームの参照先となる最初と最後の前記フレームのいずれかが重複している場合、２つの前記参照グループを結合して新たな前記参照グループとし、重複している前記フレームを前記新たな参照グループの前記判定対象フレームとする映像符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像符号化装置に関する。
【背景技術】
【０００２】
映像符号化の標準規格として、Ｈ．２６４／ＡＶＣ(Advanced Video Coding)やＨ．２６５／ＨＥＶＣ(High Efficiency Video Coding)と呼ばれる映像符号化方式が策定されている。ＨＥＶＣでは、イントラピクチャであるＩ(Intra)ピクチャと、インターピクチャであるＰ(Predictive)ピクチャと、Ｂ(Bi-directional predictive)ピクチャという複数のピクチャタイプが定義されている。各フレームには、いずれかのピクチャタイプが割り当てられる。
【０００３】
Ｉピクチャは、通常、数フレームごとに定められるピクチャタイプであり、符号化対象フレーム内の符号化済み画素から予測するイントラ予測モードのみが適用されるピクチャタイプである。Ｐピクチャ及びＢピクチャは、イントラ予測モードか、または、符号化済みフレームから予測するインター予測モードが選択的に適用されるピクチャタイプである。Ｐピクチャは、時系列の過去のフレームを参照フレームとするのに対して、Ｂピクチャは、過去と未来のフレームを参照フレームとする。
【０００４】
Ｉピクチャから次のＩピクチャまでのフレーム群をＧＯＰ（Group Of Picture）といい、ＧＯＰごとに、Ｉピクチャの間隔や参照構造等の符号化構造を自由に設定することができる。代表的な符号化構造として、図１７に示す低遅延符号化の符号化構造と、図１８に示すランダムアクセス符号化の符号化構造があり、一般に、ランダムアクセス符号化の方が、符号化効率が高いと言われている。
【０００５】
符号化構造を定める際、ＩピクチャまたはＰピクチャ間隔を符号化する映像に応じて適応的に定めることで、符号化効率を向上させることができる。例えば、図１９に示すような、映像の途中でシーンチェンジがある映像フレームのシーケンスに対して、固定されたＩピクチャまたはＰピクチャ間隔よりもシーンチェンジに合わせて適応的にＩピクチャまたはＰピクチャとなるフレームを選択していくことで符号化効率が向上する。
【０００６】
また、その他にも、図２０や図２１に示すような参照構造を階層的に設定する等、適応的に参照構造を変化させることで符号化効率の向上を図ることができる。例えば、図２０に示す適応構造１と図２１に示す適応構造２とを比較した場合、図２１に示す適応構造２の方が、最大階層が２階層になっていることから、参照フレーム間の距離が小さくなっており、符号化効率の向上が期待される。
【０００７】
更に高い符号化効率を有する符号化構造を選択する手法も提案されている（例えば、非特許文献１及び２参照）。以下に、提案されている代表的な２つの技術について説明する。非特許文献１に示す技術では、符号化構造は、以下の手順にしたがって定められる。原画像を、縦横それぞれ１／２サイズに縮小する（ステップＳｘ１）。最初のフレームをＩピクチャとして符号化し、基準フレームとする（ステップＳｘ２）。Ｎ枚先までの各フレームに対して、Ｐピクチャとした場合のコストを算出し、算出したコストが最小となったフレームをＰピクチャとする。ここで、コストとは、フレームの各符号化ブロックをイントラ予測モード及びインター予測モードにより符号化した際の小さい方の符号化コストの全ブロックの総和である（ステップＳｘ３）。
【０００８】
基準フレームと、ステップＳｘ３でＰピクチャとして選択したフレームとの間に、それらを参照する中間フレームを定義する。基準フレームと中間フレームとの間に位置するフレームに対して、これらのフレームを基準フレームと中間フレームとを参照するＢピクチャとした場合のコストを算出する。また、中間フレームとＰピクチャとの間に位置するフレームに対して、これらのフレームを中間フレームとＰピクチャとを参照するＢピクチャとした場合のコストを算出する。算出したコストが最小となる組み合わせを最終的な符号化構造として選択する（ステップＳｘ４）。ステップＳｘ３でＰピクチャとしたフレームを基準フレームとし、ステップＳｘ３及びＳｘ４を繰り返し実行して適応的に符号化構造を定めていく。
【０００９】
非特許文献２に記載の技術では、符号化構造は、以下の手順にしたがって定められる。１枚目のフレームをＩピクチャとして符号化する（ステップＳｙ１）。Ｉピクチャと次のフレームとの間で動き探索を行い、各符号化ブロックの動きベクトルをＳ１（ｋ）（ただし、１≦ｋ≦Ｎｂｌｋ：Ｎｂｌｋは、フレーム内のブロック数）とする（ステップＳｙ２）。
【００１０】
ｎ枚目（ｎ≧３）の各フレームに対して１枚目のフレームとの間で動き探索を行い、各符号化ブロックの動きベクトルをフレーム間距離で割ったものをＳｎ（ｋ）とする（ステップＳｙ３）。動きベクトル差の平均（Ｅ＝Σ（Ｓ１−Ｓｎ）／Ｎｂｌｋ）を算出する（ステップＳｙ４）。予め定められた閾値をｔｈとし、Ｅ＜ｔｈであれば、ｎ枚目のフレームをＢピクチャとし、そうでなければ、Ｐピクチャとする（ステップＳｙ５）。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】“VideoLAN, a project and a non-profit organization”、[online]、VideoLAN Organization、［平成２９年３月１７日検索］、インターネット（URL:https://www.videolan.org/developers/x265.html）
【非特許文献２】Adriana Dumitras and Barry G. Haskell,“I/P/B FRAME TYPE DECISION BY COLLINEARITY OF DISPLACEMENTS”, 2004 International Conference on Image Processing(ICIP), p2769-p2772
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上記の手順に示すように、非特許文献１に記載の技術では、縮小画像を用いているとはいえ、実際の符号化に近い処理を複数の組み合わせに対して行っている。また、計算結果が無駄になる組み合わせも生じており、結果的に、演算量が多い手法になってしまっているという問題がある。また、非特許文献１に記載の技術では、Ｂピクチャの階層として２階層を割り当てることを前提としており、この技術に対して、符号化効率の良いより深い階層構造を適用しようとすると、組み合わせ数が増大してしまうという問題がある。
【００１３】
非特許文献２に記載の技術においても、判定の際の計算結果が無駄になる組み合わせが存在するため、演算量が多いという問題がある。また、非特許文献２に記載の技術では、Ｂピクチャの階層として１階層分しか適用できないという問題がある。また、非特許文献２に記載の技術では、動きベクトルのみを判定に用いているため、複雑な映像に対して精度良く判定することができず、符号化効率が悪いという問題がある。
【００１４】
上記事情に鑑み、本発明は、符号化効率の高い符号化構造を低演算量で求めることができる技術の提供を目的としている。
【課題を解決するための手段】
【００１５】
本発明の一態様は、フレーム間予測符号化を行う映像符号化装置であって、入力映像情報から取得されるフレーム群から、予め定められる３枚以上の枚数の連続するフレームを含む参照グループを生成する参照グループ生成部と、前記参照グループ生成部が生成する前記参照グループの最初と最後の前記フレームの間のいずれか１つの判定対象フレームと、最初と最後の前記フレームとの参照関係を結合するか否かを判定する結合判定部と、前記結合判定部の判定結果に基づいて、前記フレーム群に含まれる前記フレームのピクチャタイプを選定するピクチャタイプ選定部と、を備え、前記参照グループ生成部は、前記結合判定部により結合すると判定された前記参照グループの最初の前記フレーム、または最後の前記フレームが前記判定対象フレームとなるように、当該参照グループを含み前記予め定められる３枚以上の枚数よりも多い枚数の連続するフレームを含む新たな前記参照グループを生成する映像符号化装置である。
【００１６】
本発明の一態様は、上記の映像符号化装置であって、前記参照グループ生成部は、隣接する２つの前記参照グループの双方において前記結合判定部が前記判定対象フレームと最初と最後の前記フレームとの参照関係を結合すると判定する場合、前記隣接する２つの前記参照グループを結合して前記新たな参照グループを生成し、隣接する２つの前記参照グループの各々の前記判定対象フレームの参照先となる最初と最後の前記フレームのうち重複する前記フレームを前記新たな参照グループの前記判定対象フレームとする。
【００１７】
本発明の一態様は、上記の映像符号化装置であって、前記参照グループ生成部は、前記フレーム群の先頭の前記フレームを起点として前記予め定められる３枚以上の枚数の連続するフレームを含む前記参照グループを最初の前記参照グループとして生成し、前記結合判定部が、前記参照グループの前記判定対象フレームと最初と最後の前記フレームとの参照関係を結合すると判定する場合、当該参照グループの最後の前記フレームを起点として前記予め定められる３枚以上の枚数の連続するフレームを含む隣接する前記参照グループを生成し、前記結合判定部が、前記参照グループの前記判定対象フレームと前記最初と最後のフレームとの参照関係を結合しないと判定する場合、前記判定対象フレームを起点として前記予め定められる３枚以上の枚数の連続するフレームを含む隣接する前記参照グループを生成し、前記隣接する２つ前記参照グループを結合して前記新たな参照グループを生成する場合、前記新たな参照グループの最後のフレームを起点として前記予め定められる３枚以上の枚数の連続するフレームを含む隣接する前記参照グループを生成する。
【００１８】
本発明の一態様は、上記の映像符号化装置であって、前記参照グループ生成部は、前記参照グループに隣接する他の参照グループを生成する際、当該参照グループの最後の前記フレームが、前記隣接する他の参照グループの最初の前記フレームとなるように重複させて前記予め定められる３枚以上の枚数の連続するフレームを含む前記参照グループを生成する。
【００１９】
本発明の一態様は、上記の映像符号化装置であって、前記入力映像情報から前記フレーム群を取得し、取得した前記フレーム群の最初のフレームをＩピクチャとして選定するＩピクチャ選定部を備え、前記ピクチャタイプ選定部は、前記結合判定部が、前記判定対象フレームと前記最初と最後のフレームとの参照関係を結合すると判定する場合、前記判定対象フレームを前記最初と最後のフレームを参照フレームとするＢピクチャとして選定し、前記Ｉピクチャ、または前記Ｂピクチャとして選定されていない前記フレームを前記Ｐピクチャとして選定し、前記フレーム群の表示順において、選定した前記フレームに最も近い過去の前記Ｐピクチャの前記フレームを、選定した前記フレームの前記参照フレームとし、選定した前記フレームに最も近い過去の前記Ｐピクチャの前記フレームがない場合、前記Ｉピクチャの前記フレームを、選定した前記フレームの前記参照フレームとする。
【００２０】
本発明の一態様は、上記の映像符号化装置であって、前記予め定められる３枚以上の枚数は、３枚である。
【００２１】
本発明の一態様は、入力映像情報から取得されるフレーム群から、３枚の連続するフレームを含む参照グループを生成する参照グループ生成部と、前記参照グループ生成部が生成する前記参照グループの最初と最後の前記フレームの間の判定対象フレームと、前記最初と最後のフレームとの参照関係を結合するか否かを判定する結合判定部と、前記結合判定部の判定結果に基づいて、前記フレーム群に含まれる前記フレームのピクチャタイプを選定するピクチャタイプ選定部と、を備える映像符号化装置である。
【００２２】
本発明の一態様は、フレーム間予測符号化を行う映像符号化装置であって、入力映像情報から取得されるフレーム群から、３枚の連続するフレームを含む参照グループを生成する参照グループ生成部と、前記参照グループ生成部が生成する前記参照グループの最初と最後の前記フレームの間の判定対象フレームと、前記最初と最後のフレームとの参照関係を結合するか否かを判定する結合判定部と、前記結合判定部の判定結果に基づいて、前記フレーム群に含まれる前記フレームのピクチャタイプを選定するピクチャタイプ選定部と、を備え、前記参照グループ生成部は、前記結合判定部により結合すると判定された２つの前記参照グループにおいて、各々の前記判定対象フレームの参照先となる最初と最後の前記フレームのいずれかが重複している場合、２つの前記参照グループを結合して新たな前記参照グループとし、重複している前記フレームを前記新たな参照グループの前記判定対象フレームとする映像符号化装置である。
【発明の効果】
【００２３】
本発明により、符号化効率の高い符号化構造を低演算量で求めることが可能となる。
【図面の簡単な説明】
【００２４】
【図１】本発明の第１の実施形態による映像符号化装置の構成を示すブロック図である。
【図２】同実施形態の符号化構造構築部の構成を示すブロック図である。
【図３】同実施形態の符号化構造構築処理の流れを示すフローチャートである。
【図４】同実施形態の結合判定処理の流れを示すフローチャートである。
【図５】同実施形態の符号化構造構築処理の具体例を示す図（その１）である。
【図６】同実施形態の符号化構造構築処理の具体例を示す図（その２）である。
【図７】同実施形態の符号化構造構築処理の具体例を示す図（その３）である。
【図８】同実施形態の符号化構造構築処理の具体例を示す図（その４）である。
【図９】同実施形態の結合判定処理の具体例を示す図である。
【図１０】同実施形態の結合判定処理の具体例において算出した評価値を示す図である。
【図１１】本発明の第２の実施形態の符号化構造構築部の構成を示すブロック図である。
【図１２】同実施形態の符号化構造構築処理の流れを示すフローチャート（その１）である。
【図１３】同実施形態の符号化構造構築処理の流れを示すフローチャート（その２）である。
【図１４】同実施形態の符号化構造構築処理の具体例を示す図（その１）である。
【図１５】同実施形態の符号化構造構築処理の具体例を示す図（その２）である。
【図１６】同実施形態の符号化構造構築処理の具体例を示す図（その３）である。
【図１７】インター予測符号化における低遅延符号化の符号化構造を示す図である。
【図１８】インター予測符号化におけるランダムアクセス符号化の符号化構造を示す図である。
【図１９】インター予測符号化における固定構造と適応構造の違いを示す図である。
【図２０】インター予測符号化における適応構造を説明するための図（その１）である。
【図２１】インター予測符号化における適応構造を説明するための図（その２）である。
【発明を実施するための形態】
【００２５】
（第１の実施形態）
以下、本発明の実施形態について図面を参照して説明する。図１は、本発明の第１の実施形態における映像符号化装置１の構成を示すブロック図である。映像符号化装置１は、符号化構造構築部１０、減算器１１、直交変換・量子化部１２、可変長符号化部１３、逆量子化・逆直交変換部１４、加算器１５、イントラ予測部１６、ループフィルタ部１７、復号ピクチャ記憶部１８、インター予測部１９、及びイントラ・インター切替スイッチ部２０を備える。
【００２６】
符号化構造構築部１０は、外部から入力映像情報を取り込み、取り込んだ入力映像情報から予め定められるＧＯＰのサイズにしたがう枚数のフレームを選択してフレーム群を生成する。また、符号化構造構築部１０は、生成したフレーム群の各フレームのピクチャタイプ、参照構造などを選定して符号化構造を構築する。また、符号化構造構築部１０は、構築した符号化構造が示す符号化順序にしたがってＣＵ（Coding Unit）ブロック単位で符号化対象フレームを出力する。
【００２７】
減算器１１は、符号化構造構築部１０が出力する符号化対象フレームの画像情報と、イントラ・インター切替スイッチ部２０を介してイントラ予測部１６、またはインター予測部１９が出力する予測画像情報との差を算出する。また、減算器１１は、算出した差に基づく差分画像情報を直交変換・量子化部１２に出力する。
【００２８】
直交変換・量子化部１２は、減算器１１が出力する差分画像情報に対して、直交変換と量子化を行い、可変長符号化部１３と逆量子化・逆直交変換部１４に出力する。可変長符号化部１３は、直交変換・量子化部１２が出力する量子化係数を可変長符号化して符号化データを生成し、生成した符号化データを外部に出力する。
【００２９】
逆量子化・逆直交変換部１４は、直交変換・量子化部１２が出力する量子化係数に対して、逆量子化と逆直交変換を行って差分画像情報を復号して加算器１５に出力する。加算器１５は、逆量子化・逆直交変換部１４が出力する復号差分画像情報と、イントラ・インター切替スイッチ部２０を介してイントラ予測部１６、またはインター予測部１９が出力する予測画像情報との和を算出する。また、加算器１５は、算出した和に基づく復号画像情報をイントラ予測部１６とループフィルタ部１７に出力する。
【００３０】
イントラ予測部１６は、加算器１５が出力する復号画像情報を参照フレームとして、符号化対象フレームに含まれる符号化対象ブロックのイントラ予測画像情報を生成する。
【００３１】
ループフィルタ部１７は、加算器１５が出力する復号画像情報にループフィルタを適用し、ループフィルタを適用した復号画像情報を復号ピクチャ記憶部１８に書き込んで記憶させる。インター予測部１９は、復号ピクチャ記憶部１８に記憶されている復号画像情報を参照フレームとして、符号化構造構築部１０が出力する符号化対象フレームに含まれる符号化対象ブロックのインター予測画像情報を生成する。
【００３２】
イントラ・インター切替スイッチ部２０は、符号化対象ブロックの予測モードに応じて、イントラ予測部１６とインター予測部１９とを切り替えて、イントラ予測部１６が出力するイントラ予測画像情報、またはインター予測部１９が出力するインター予測画像情報を減算器１１と加算器１５に出力する。
【００３３】
上記の構成により、映像符号化装置１は、外部から取り込んだ入力映像情報からフレーム群を生成し、生成したフレーム群の符号化対象フレームごとにラスタースキャンしてＣＵブロックを生成する。映像符号化装置１は、生成した各ＣＵブロックを符号化対象ブロックとしてラスタースキャン順に繰り返し符号化を行い、符号化対象ブロックごとの符号化データを出力する。映像符号化装置１は、この処理を入力映像情報から生成する全てのフレーム群に含まれるフレームに対して繰り返し行うことにより、符号化対象入力映像情報を符号化する。
【００３４】
符号化の過程において、インター予測部１９でＰピクチャのフレームの符号化を行うためには、Ｐピクチャのフレームに対する参照フレームが予め復号ピクチャ記憶部１８に記憶されている必要がある。また、Ｂピクチャのフレームの符号化を行うためには、Ｂピクチャのフレームに対する２つの参照フレームが予め復号ピクチャ記憶部１８に記憶されている必要がある。符号化構造構築部１０は、これらの符号化の順序の要求を満たすような符号化構造の構築を行う。
【００３５】
図２は、符号化構造構築部１０の構成を示すブロック図である。符号化構造構築部１０は、符号化対象フレーム選択部１０１、Ｉピクチャ選定部１０２、参照グループ生成部１０３、結合判定部１０４、ピクチャタイプ選定部１０５、ピクチャタイプ記憶部１０６、及びブロック出力部１０７を備える。
【００３６】
符号化対象フレーム選択部１０１は、入力映像情報から予め定められるＧＯＰのサイズにしたがう枚数のフレームを選択してフレーム群を生成してＩピクチャ選定部１０２とブロック出力部１０７に出力する。Ｉピクチャ選定部１０２は、フレーム群の最初のフレームをＩピクチャとして選定し、最初のフレームを起点フレームとしてフレーム群を参照グループ生成部１０３に出力する。
【００３７】
参照グループ生成部１０３は、フレーム群の先頭のフレームを起点として所定の枚数（例えば、３枚）の連続するフレームを選択し、選択した所定の枚数の連続するフレームの組み合わせを最初の参照グループとして生成する。また、参照グループ生成部１０３は、その後に起点となるフレームから所定の枚数の連続するフレームを選択し、選択した所定の枚数の連続するフレームの組み合わせを参照グループとして生成する。また、参照グループ生成部１０３は、隣接する２つの参照グループが共に結合判定部１０４によって結合すると判定されている場合、隣接する２つの参照グループを結合して新たな参照グループを生成する。
【００３８】
また、参照グループ生成部１０３は、生成した参照グループの情報、すなわち参照グループに含まれるフレームの画像情報、及び参照グループに含まれるフレームのフレームをフレーム群において特定するフレーム番号等の情報を結合判定部１０４とピクチャタイプ選定部１０５に出力する。
【００３９】
結合判定部１０４は、参照グループ生成部１０３が生成して出力する参照グループに含まれるフレームを結合するか否かを判定する。ここで、参照グループに含まれるフレームを結合するとは、最初と最後のフレームの間のフレームである判定対象フレームを、最初と最後のフレームを参照フレームとするＢピクチャとすることである。結合判定部１０４は、評価値算出部１１０、評価値判定部１１１、及び判定結果記憶部１１２を備える。
【００４０】
評価値算出部１１０は、参照グループ生成部１０３が生成した参照グループの評価値を算出する。ここで、評価値は、以下のようにして算出される３つのインターコストの値である。なお、インターコストは、例えば、フレーム間において動き探索を行った場合の誤差に関する評価値であり、例えば、絶対誤差和の最小値等が適用され、この評価値は、ＲＤ(Rate-Distortion)コストのような実際に符号化を行わないと得られない符号化コストとは異なる値である。ここで、絶対誤差和の最小値とは、動きベクトルを複数検出して、動きベクトルごとの絶対誤差和を算出して得られた値の中で最も小さい値を表す。
【００４１】
まず、最初のフレームと、最初と最後のフレームの間の判定対象フレームと、最後のフレームをそれぞれ、Ｓフレーム、Ｍフレーム、Ｅフレームとする。参照グループが、所定の枚数（例えば、３枚）の連続するフレームを含む場合、判定対象フレームは、中間のフレームとなり、後述するように２つの隣接する参照グループが結合される場合、判定対象フレームは、表示順で１つ前の参照グループの最後のフレームとなる。
【００４２】
Ｍフレームに対して予め定められる所定のブロックサイズ単位でＳフレームを参照フレームとした場合の片方向インターコストの全ブロックの総和（以下、Ｌ０コストという）を算出する。次に、Ｍフレームに対して予め定められる所定のブロックサイズ単位でＥフレームを参照フレームとした場合の片方向インターコストの全ブロックの総和（以下、Ｌ１コストという）を算出する。更に、Ｍフレームに対して予め定められる所定のブロックサイズ単位でＳフレームとＥフレームを参照フレームとした場合の双方向インターコストの全ブロックの総和（以下、Ｂｉコストという）を算出する。
【００４３】
評価値判定部１１１は、評価値算出部１１０が算出したＬ０コスト、Ｌ１コスト、Ｂｉコストに基づいて、参照グループのフレームを結合すべきか否か、すなわちＭフレームを、ＳフレームとＥフレームを参照フレームとするＢピクチャとするか否かを判定する結合判定処理を行う。評価値判定部１１１は、判定結果を参照グループを示す情報に対応付けて判定結果記憶部１１２に書き込んで記憶させ、また、判定結果をピクチャタイプ選定部１０５に出力する。判定結果記憶部１１２は、参照グループごとに評価値判定部１１１が判定した判定結果を記憶する。
【００４４】
ピクチャタイプ選定部１０５は、結合判定部１０４が出力する判定結果にしたがって、参照グループ生成部１０３が生成した参照グループに含まれるフレームのピクチャタイプを選定する。また、ピクチャタイプ選定部１０５は、参照グループ生成部１０３が、連続する３枚のフレームを選択できないと判定した場合、残りのフレームをＰピクチャとして選定する。また、ピクチャタイプ選定部１０５は、全てのフレームについて、ピクチャタイプを選定した後、Ｐピクチャとして選定したフレームに対して、当該フレームに表示順で最も近い過去のＰピクチャとして選定されたフレームを当該フレームの参照フレームとして選定する。
【００４５】
ここで、表示順で最も近い過去のＰピクチャとは、Ｉピクチャとなる最初のフレームから表示順に連続番号を付与していった場合、参照フレームを割り当てるフレームよりも若い番号で最も近いＰピクチャのことである。また、表示順で最も近い過去のＰピクチャがない場合、ピクチャタイプ選定部１０５は、Ｉピクチャを参照フレームとして選定する。
【００４６】
ピクチャタイプ記憶部１０６は、Ｉピクチャ選定部１０２がＩピクチャとして選定したフレームを示す情報に対応付けてＩピクチャのピクチャタイプを示す情報を記憶する。また、ピクチャタイプ記憶部１０６は、ピクチャタイプ選定部１０５が選定したＢピクチャまたはＰピクチャのピクチャタイプを示す情報を、参照フレームを示す情報とともに、各フレームを示す情報に対応付けて記憶する。
【００４７】
ブロック出力部１０７は、符号化対象フレーム選択部１０１が出力するフレーム群を受けて、一時的に内部の記憶領域に書き込んで記憶する。また、ブロック出力部１０７は、ピクチャタイプの選定が完了し符号化構造が定められると、定められた符号化構造に基づく順番で内部の記憶領域からフレームを読み出し、読み出したフレームの各々をラスタースキャンの順にＣＵブロックに分解して符号化対象ブロックとして出力する。
【００４８】
（第１の実施形態の符号化構造構築処理）
次に、第１の実施形態の符号化構造構築部１０による処理について説明する。図３は、符号化構造構築部１０による符号化構造構築処理の流れを示すフローチャートである。また、図４は、符号化構造構築処理において呼び出される結合判定部１０４による結合判定処理のサブルーチンの流れを示すフローチャートである。
【００４９】
符号化対象フレーム選択部１０１は、入力映像情報から予め定められるＧＯＰのサイズにしたがう枚数のフレームを選択してフレーム群を生成し、生成したフレーム群をＩピクチャ選定部１０２とブロック出力部１０７に出力する。Ｉピクチャ選定部１０２は、フレーム群の最初のフレームのピクチャタイプをＩピクチャとして選定し、当該フレームをＩピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。また、Ｉピクチャ選定部１０２は、最初のフレームを起点フレームとし、フレーム群を参照グループ生成部１０３に出力する（ステップＳ１０１）。
【００５０】
参照グループ生成部１０３は、起点フレームを起点として、フレーム群から連続する３枚のフレームを選択することができるか否かを判定する（ステップＳ１０２）。参照グループ生成部１０３は、連続する３枚のフレームを選択することができると判定した場合（ステップＳ１０２−ＹＥＳ）、参照グループ生成部１０３は、連続する３枚のフレームを表示順にＡ，Ｂ，Ｃフレームとして含む参照グループを生成する。なお、当該参照グループにおいて判定対象フレームは、Ｂフレームとなる。
【００５１】
参照グループ生成部１０３は、生成した参照グループを結合判定部１０４とピクチャタイプ選定部１０５に出力する（ステップＳ１０５）。結合判定部１０４は、参照グループ生成部１０３が出力する参照グループに含まれるＡ，Ｂ，ＣフレームをＳ，Ｍ，Ｅフレームとして結合判定処理を行う（ステップＳ１０６）。
【００５２】
（結合判定部による結合判定処理）
図４に示す結合判定処理のサブルーチンにおいて、評価値算出部１１０は、Ｓフレーム、Ｍフレーム、Ｅフレームに基づいて、Ｌ０コスト、Ｌ１コスト、Ｂｉコストの３つの評価値を算出する（ステップＳ２０１）。
【００５３】
評価値判定部１１１は、ＢｉコストとＬ１コストのうち値が小さい方を選択し（ステップＳ２０２）、選択した値をＬ０で除算して相対値を算出する（ステップＳ２０３）。なお、ＢｉコストとＬ１コストの値が同じ場合、いずれを選択してもよいため、いずれか一方を選択する。ステップＳ２０２とＳ２０３の処理を数式で示すと以下の式（１）となる。
【００５４】
相対値＝ｍｉｎ（Ｂｉコスト，Ｌ１コスト）／Ｌ０コスト・・・（１）
【００５５】
評価値判定部１１１は、算出した相対値の大きさを予め定められる相対評価用閾値Ｔｈ＿ｍｉｎ及びＴｈ＿ｍａｘに基づいて判定する（ステップＳ２０４）。評価値判定部１１１は、算出した相対値が、Ｔｈ＿ｍｉｎの値未満であると判定した場合（ステップＳ２０４：＜Ｔｈ＿ｍｉｎ）、参照グループに含まれるフレームを結合することを示す「Ｔｒｕｅ」を出力する（ステップＳ２０５）。一方、評価値判定部１１１は、算出した相対値が、Ｔｈ＿ｍａｘの値を超過していると判定した場合（ステップＳ２０４：＞Ｔｈ＿ｍａｘ）、参照グループに含まれるフレームを結合しないことを示す「Ｆａｌｓｅ」を出力する（ステップＳ２０６）。
【００５６】
一方、評価値判定部１１１は、算出した相対値が、Ｔｈ＿ｍｉｎの値以上で、かつＴｈｍａｘの値以下であると判定した場合（ステップＳ２０４：≧Ｔｈ＿ｍｉｎかつ≦Ｔｈ＿ｍａｘ）、Ｂｉコストの値の大きさを予め定められる絶対評価用閾値Ｔｈ＿ａｂｓに基づいて判定する（ステップＳ２０７）。評価値判定部１１１は、Ｂｉコストの値が、Ｔｈ＿ａｂｓの値未満であると判定した場合（ステップＳ２０７：＜Ｔｈ＿ａｂｓ）、参照グループに含まれるフレームを結合することを示す「Ｔｒｕｅ」を出力する（ステップＳ２０８）。一方、評価値判定部１１１は、Ｂｉコストの値が、Ｔｈ＿ａｂｓの値以上と判定した場合（ステップＳ２０７：≧Ｔｈ＿ａｂｓ）、参照グループに含まれるフレームを結合しないことを示す「Ｆａｌｓｅ」を出力する（ステップＳ２０６）。
【００５７】
評価値判定部１１１は、ステップＳ２０５，Ｓ２０６，Ｓ２０８の処理において、参照グループを示す情報に対応付けて判定結果を示す「Ｔｒｕｅ」または「Ｆａｌｓｅ」の情報を判定結果記憶部１１２に書き込んで記憶させて、結合判定処理のサブルーチンを終了する。
【００５８】
図３に戻り、ピクチャタイプ選定部１０５は、結合判定部１０４が出力する判定結果を判定する（ステップＳ１０７）。ピクチャタイプ選定部１０５は、判定結果が「Ｆａｌｓｅ」の場合（ステップＳ１０７−Ｆａｌｓｅ）、参照グループのＢフレームのピクチャタイプをＰピクチャとして選定し、ＢフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。ピクチャタイプ選定部１０５は、Ｂフレームを起点フレームとする情報を参照グループ生成部１０３に出力する（ステップＳ１０８）。参照グループ生成部１０３は、ピクチャタイプ選定部１０５が出力するＢフレームを起点フレームとする情報を受けた場合、Ｂフレームを起点フレームとしてステップＳ１０２の処理に進む。
【００５９】
一方、ピクチャタイプ選定部１０５は、判定結果が「Ｔｒｕｅ」の場合（ステップＳ１０７−Ｔｒｕｅ）、ＢフレームのピクチャタイプをＡフレームとＣフレームを参照フレームとするＢピクチャとして選定し、ＢフレームをＢピクチャとして選定したことを示す情報、及びＡフレームとＣフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。また、ピクチャタイプ選定部１０５は、ＣフレームのピクチャタイプをＰピクチャとして選定し、ＣフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。ピクチャタイプ選定部１０５は、判定結果が「Ｔｒｕｅ」の参照グループを示す情報を参照グループ生成部１０３に出力する（ステップＳ１０９）。
【００６０】
参照グループ生成部１０３は、ピクチャタイプ選定部１０５が出力する判定結果が「Ｔｒｕｅ」の参照グループを示す情報を受けた場合、結合判定部１０４の判定結果記憶部１１２を参照する。参照グループ生成部１０３は、判定結果記憶部１１２に記憶されている情報に基づいて、表示順において、処理中の参照グループの１つ前の参照グループの判定結果が、「Ｔｒｕｅ」であるか否かを判定する（ステップＳ１１０）。
【００６１】
参照グループ生成部１０３は、表示順において、処理中の参照グループの１つ前の参照グループの判定結果が、「Ｔｒｕｅ」でないと判定した場合（ステップＳ１１０−ＮＯ）、Ｃフレームを起点フレームとして（ステップＳ１１６）、ステップＳ１０２の処理に進む。
【００６２】
参照グループ生成部１０３は、表示順において、処理中の参照グループの１つ前の参照グループの判定結果が、「Ｔｒｕｅ」であると判定した場合（ステップＳ１１０−ＹＥＳ）、新たな参照グループを生成する。すなわち、参照グループ生成部１０３は、１つ前の参照グループの最初のフレームと最後のフレームをそれぞれ、αフレーム、βフレームとし、処理中の参照グループの最後のフレームをγフレームとし、α、β、γフレームを含む新たな参照グループを生成する。なお、βフレームは、処理中の参照グループの最初のＡフレームでもあり、当該参照グループにおける判定対象フレームとなる。参照グループ生成部１０３は、生成した新たな参照グループの情報を結合判定部１０４とピクチャタイプ選定部１０５に出力する（ステップＳ１１１）。
【００６３】
結合判定部１０４は、参照グループ生成部１０３が出力する参照グループに含まれるα，β，γフレームに対して結合判定処理を行う。評価値算出部１１０は、α，β，γフレームのそれぞれをＳ，Ｍ，Ｅフレームとして図４に示す結合判定処理を行う（ステップＳ１１２）。
【００６４】
ピクチャタイプ選定部１０５は、結合判定部１０４が出力する判定結果を判定する（ステップＳ１１３）。ピクチャタイプ選定部１０５は、判定結果が「Ｆａｌｓｅ」の場合（ステップＳ１１３−Ｆａｌｓｅ）、新たな参照グループの最後のフレームであるγフレーム、すなわち結合前の処理中の参照グループのＣフレームを起点フレームとすることを示す情報を参照グループ生成部１０３に出力する（ステップＳ１１５）。参照グループ生成部１０３は、ピクチャタイプ選定部１０５が出力するＣフレームを起点フレームとすることを示す情報を受けて、Ｃフレームを起点フレームとして（ステップＳ１１６）、ステップＳ１０２の処理に進む。
【００６５】
一方、ピクチャタイプ選定部１０５は、判定結果が「Ｔｒｕｅ」の場合（ステップＳ１１３−Ｔｒｕｅ）、βフレームのピクチャタイプをαフレームとγフレームを参照フレームとするＢピクチャとして選定し、βフレームをＢピクチャとして選定したことを示す情報、及びαフレームとγフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。また、ピクチャタイプ選定部１０５は、γフレームのピクチャタイプをＰピクチャとして選定し、γフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ１１４）。
【００６６】
ピクチャタイプ選定部１０５は、新たな参照グループの最後のフレームであるγフレーム、すなわち結合前の処理中の参照グループのＣフレームを起点フレームとすることを示す情報を参照グループ生成部１０３に出力する（ステップＳ１１５）。参照グループ生成部１０３は、ピクチャタイプ選定部１０５が出力するＣフレームを起点フレームとすることを示す情報を受けて、Ｃフレームを起点フレームとして（ステップＳ１１６）、ステップＳ１０２の処理に進む。
【００６７】
一方、ステップＳ１０２において、参照グループ生成部１０３は、連続する３枚のフレームを選択することができないと判定した場合（ステップＳ１０２−ＮＯ）、フレーム群の残りのフレームをＰピクチャとして選定させる指示情報をピクチャタイプ選定部１０５に出力する。
【００６８】
ピクチャタイプ選定部１０５は、参照グループ生成部１０３から当該指示情報を受けて、残りのフレームのピクチャタイプをＰピクチャとして選定し、残りのフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ１０３）。ピクチャタイプ選定部１０５は、Ｐピクチャとして選定したフレームの各々に対して、当該フレームに表示順で最も近い過去のＰピクチャのフレームを参照フレームとして選定する。表示順で最も近い過去のＰピクチャがない場合、Ｉピクチャを当該フレームの参照フレームとして選定する。ピクチャタイプ選定部１０５は、各Ｐピクチャに対して選定した参照フレームの情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ１０４）。
【００６９】
これにより、ピクチャタイプ記憶部１０６に、最終的に構築された符号化構造の情報が記憶されることになる。ブロック出力部１０７は、内部の記憶領域に一時的に符号化対象フレーム選択部１０１から受けたフレーム群を記憶しており、ピクチャタイプ記憶部１０６に記憶されている符号化構造に基づく順番で内部の記憶領域からフレームを読み出す。ブロック出力部１０７は、読み出したフレームの各々をラスタースキャンの順にＣＵブロックに分解して符号化対象ブロックとして出力し、符号化構造構築部１０は、１つのフレーム群についての処理を終了する。
【００７０】
（第１の実施形態の符号化構造処理の具体例）
次に、図５から図８を参照しつつ、図５（ａ）に示すフレーム群に、図３に示した第１の実施形態の符号化構造構築処理を適用した場合の例について説明する。符号化対象フレーム選択部１０１が、入力映像情報から図５（ａ）に示すフレーム群を生成する。当該フレーム群は、フレーム番号８とフレーム番号９のフレームにおいてシーンチェンジが含まれている。
【００７１】
図５（ｂ）に示すように、Ｉピクチャ選定部１０２は、フレーム番号０のフレームのピクチャタイプをＩピクチャとして選定し、当該フレームをＩピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。また、Ｉピクチャ選定部１０２は、フレーム番号０のフレームを起点フレームとする（ステップＳ１０１）。
【００７２】
参照グループ生成部１０３は、フレーム番号０のフレームを起点フレームとして、フレーム番号０，１，２の３枚の連続するフレームを選択する（ステップＳ１０２−ＹＥＳ）。参照グループ生成部１０３は、フレーム番号０，１，２のフレームをフレームＡ，Ｂ，Ｃとして含む参照グループ３０１を生成し、生成した参照グループ３０１の情報を結合判定部１０４とピクチャタイプ選定部１０５に出力する（ステップＳ１０５）。なお、参照グループ３０１において判定対象フレームは、フレーム番号１のフレームとなる。
【００７３】
結合判定部１０４は、参照グループ３０１に対して図４に示す結合判定処理を行い、ここでは、シーンチェンジがないため、評価値判定部１１１は、「Ｔｒｕｅ」を出力したとする（ステップＳ１０６）。ピクチャタイプ選定部１０５は、結合判定部１０４が出力する判定結果が、「Ｔｒｕｅ」であるため（ステップＳ１０７−Ｔｒｕｅ）、フレーム番号１のフレームのピクチャタイプをフレーム番号０とフレーム番号２のフレームを参照フレームとするＢピクチャとして選定する。ピクチャタイプ選定部１０５は、フレーム番号２のフレームをＢピクチャとして選定したことを示す情報、及びフレーム番号０とフレーム番号２のフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。
【００７４】
また、ピクチャタイプ選定部１０５は、フレーム番号２のフレームのピクチャタイプをＰピクチャとして選定し、フレーム番号２のフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。ピクチャタイプ選定部１０５は、判定結果が「Ｔｒｕｅ」の参照グループ３０１を示す情報を参照グループ生成部１０３に出力する（ステップＳ１０９）。
【００７５】
図５（ｃ）に示すように、参照グループ生成部１０３は、判定結果記憶部１１２を参照し、参照グループ３０１に対して１つ前の参照グループが存在しないため（ステップＳ１１０−ＮＯ）、フレーム番号２のフレームを起点フレームとして（ステップＳ１１６）、フレーム番号２，３，４の３枚の連続するフレームを選択する（ステップＳ１０２−ＹＥＳ）。参照グループ生成部１０３は、フレーム番号２，３，４のフレームをフレームＡ，Ｂ，Ｃとして含む参照グループ３０２を生成し、生成した参照グループ３０２の情報を結合判定部１０４とピクチャタイプ選定部１０５に出力する（ステップＳ１０５）。なお、参照グループ３０２において判定対象フレームは、フレーム番号３のフレームとなる。
【００７６】
結合判定部１０４は、参照グループ３０２に対して図４に示す結合判定処理を行い、ここでも、シーンチェンジがないため、評価値判定部１１１は、「Ｔｒｕｅ」を出力したとする（ステップＳ１０６）。ピクチャタイプ選定部１０５は、結合判定部１０４が出力する判定結果が、「Ｔｒｕｅ」であるため（ステップＳ１０７−Ｔｒｕｅ）、フレーム番号３のフレームのピクチャタイプをフレーム番号２とフレーム番号４のフレームを参照フレームとするＢピクチャとして選定する。ピクチャタイプ選定部１０５は、フレーム番号３のフレームをＢピクチャとして選定したことを示す情報、及びフレーム番号２とフレーム番号４のフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。
【００７７】
また、ピクチャタイプ選定部１０５は、フレーム番号４のピクチャタイプをＰピクチャとして選定し、フレーム番号４のフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。ピクチャタイプ選定部１０５は、判定結果が「Ｔｒｕｅ」の参照グループ３０２を示す情報を参照グループ生成部１０３に出力する（ステップＳ１０９）。
【００７８】
図６（ｄ）に示すように、参照グループ生成部１０３は、判定結果記憶部１１２を参照し、参照グループ３０２に対して１つ前の参照グループ３０１の判定結果が「Ｔｒｕｅ」であると判定する（ステップＳ１１０−ＹＥＳ）。参照グループ生成部１０３は、フレーム番号０，２，４のフレームをフレームα，β，γとして含む参照グループ３０３を生成する。なお、参照グループ３０３において判定対象フレームは、フレーム番号２のフレームとなる。参照グループ生成部１０３は、生成した参照グループ３０３の情報を結合判定部１０４とピクチャタイプ選定部１０５に出力する（ステップＳ１１１）。
【００７９】
結合判定部１０４は、参照グループ３０３に対して図４に示す結合判定処理を行い、ここでも、シーンチェンジがないため、評価値判定部１１１は、「Ｔｒｕｅ」を出力したとする（ステップＳ１１２）。ピクチャタイプ選定部１０５は、判定結果が「Ｔｒｕｅ」であるため（ステップＳ１１３−Ｔｒｕｅ）、フレーム番号２のフレームのピクチャタイプをフレーム番号０とフレーム番号４のフレームを参照フレームとするＢピクチャとして選定する。
【００８０】
ピクチャタイプ記憶部１０６には、既に、フレーム番号２のフレームについて、Ｐピクチャであることを示す情報が書き込まれている。そのため、ピクチャタイプ選定部１０５は、フレーム番号２のフレームをＢピクチャとして選定したことを示す情報、及びフレーム番号０とフレーム番号４のフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に上書きして記憶させる（ステップＳ１１４）。ピクチャタイプ選定部１０５は、次の起点フレームとなるフレーム番号４を示す情報を参照グループ生成部１０３に出力する（ステップＳ１１５）。
【００８１】
図６（ｅ）に示すように、参照グループ生成部１０３は、フレーム番号４のフレームを起点フレームとして（ステップＳ１１６）、フレーム番号４，５，６の３枚の連続するフレームを選択する（ステップＳ１０２−ＹＥＳ）。参照グループ生成部１０３は、フレーム番号４，５，６のフレームをフレームＡ，Ｂ，Ｃとして含む参照グループ３０４を生成し、生成した参照グループ３０４の情報を結合判定部１０４とピクチャタイプ選定部１０５に出力する（ステップＳ１０５）。なお、参照グループ３０４において判定対象フレームは、フレーム番号５のフレームとなる。
【００８２】
結合判定部１０４は、参照グループ３０４に対して図４に示す結合判定処理を行い、ここでも、シーンチェンジがないため、評価値判定部１１１は、「Ｔｒｕｅ」を出力したとする（ステップＳ１０６）。ピクチャタイプ選定部１０５は、結合判定部１０４が出力する判定結果が、「Ｔｒｕｅ」であるため（ステップＳ１０７−Ｔｒｕｅ）、フレーム番号５のフレームのピクチャタイプをフレーム番号４とフレーム番号６のフレームを参照フレームとするＢピクチャとして選定する。ピクチャタイプ選定部１０５は、フレーム番号５のフレームをＢピクチャとして選定したことを示す情報、及びフレーム番号４とフレーム番号６のフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。
【００８３】
また、ピクチャタイプ選定部１０５は、フレーム番号６のピクチャタイプをＰピクチャとして選定し、フレーム番号６のフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。ピクチャタイプ選定部１０５は、判定結果が「Ｔｒｕｅ」の参照グループ３０４を示す情報を参照グループ生成部１０３に出力する（ステップＳ１０９）。
【００８４】
図６（ｆ）に示すように、参照グループ生成部１０３は、判定結果記憶部１１２を参照し、参照グループ３０４に対して１つ前の参照グループ３０３の判定結果が「Ｔｒｕｅ」であると判定する（ステップＳ１１０−ＹＥＳ）。参照グループ生成部１０３は、フレーム番号０，４，６のフレームをフレームα，β，γとして含む参照グループ３０５を生成する。なお、参照グループ３０５において判定対象フレームは、フレーム番号４のフレームとなる。参照グループ生成部１０３は、生成した参照グループ３０５の情報を結合判定部１０４とピクチャタイプ選定部１０５に出力する（ステップＳ１１１）。
【００８５】
結合判定部１０４は、参照グループ３０５に対して図４に示す結合判定処理を行い、ここでも、シーンチェンジがないため、評価値判定部１１１は、「Ｔｒｕｅ」を出力したとする（ステップＳ１１２）。ピクチャタイプ選定部１０５は、判定結果が「Ｔｒｕｅ」であるため（ステップＳ１１３−Ｔｒｕｅ）、フレーム番号４のフレームのピクチャタイプをフレーム番号０とフレーム番号６のフレームを参照フレームとするＢピクチャとして選定する。
【００８６】
ピクチャタイプ記憶部１０６には、既に、フレーム番号４のフレームについて、Ｐピクチャであることを示す情報が書き込まれている。そのため、ピクチャタイプ選定部１０５は、フレーム番号４のフレームをＢピクチャとして選定したことを示す情報、及びフレーム番号０とフレーム番号６のフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に上書きして記憶させる（ステップＳ１１４）。ピクチャタイプ選定部１０５は、次の起点フレームとなるフレーム番号６を示す情報を参照グループ生成部１０３に出力する（ステップＳ１１５）。
【００８７】
図７（ｇ）に示すように、参照グループ生成部１０３は、フレーム番号６のフレームを起点フレームとして（ステップＳ１１６）、フレーム番号６，７，８の３枚の連続するフレームを選択する（ステップＳ１０２−ＹＥＳ）。参照グループ生成部１０３は、フレーム番号６，７，８のフレームをフレームＡ，Ｂ，Ｃとして含む参照グループ３０６を生成し、生成した参照グループ３０６の情報を結合判定部１０４とピクチャタイプ選定部１０５に出力する（ステップＳ１０５）。なお、参照グループ３０６において判定対象フレームは、フレーム番号７のフレームとなる。
【００８８】
結合判定部１０４は、参照グループ３０６に対して図４に示す結合判定処理を行い、ここでも、シーンチェンジがないため、評価値判定部１１１は、「Ｔｒｕｅ」を出力したとする（ステップＳ１０６）。ピクチャタイプ選定部１０５は、結合判定部１０４が出力する判定結果が、「Ｔｒｕｅ」であるため（ステップＳ１０７−Ｔｒｕｅ）、フレーム番号７のフレームのピクチャタイプをフレーム番号６とフレーム番号８のフレームを参照フレームとするＢピクチャとして選定する。ピクチャタイプ選定部１０５は、フレーム番号７のフレームをＢピクチャとして選定したことを示す情報、及びフレーム番号６とフレーム番号８のフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。
【００８９】
また、ピクチャタイプ選定部１０５は、フレーム番号８のピクチャタイプをＰピクチャとして選定し、フレーム番号８のフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。ピクチャタイプ選定部１０５は、判定結果が「Ｔｒｕｅ」の参照グループ３０６を示す情報を参照グループ生成部１０３に出力する（ステップＳ１０９）。
【００９０】
図７（ｈ）に示すように、参照グループ生成部１０３は、判定結果記憶部１１２を参照し、参照グループ３０６に対して１つ前の参照グループ３０５の判定結果が「Ｔｒｕｅ」であると判定する（ステップＳ１１０−ＹＥＳ）。参照グループ生成部１０３は、フレーム番号０，６，８のフレームをフレームα，β，γとして含む参照グループ３０７を生成する。なお、参照グループ３０７において判定対象フレームは、フレーム番号６のフレームとなる。参照グループ生成部１０３は、生成した参照グループ３０７の情報を結合判定部１０４とピクチャタイプ選定部１０５に出力する（ステップＳ１１１）。
【００９１】
結合判定部１０４は、参照グループ３０７に対して図４に示す結合判定処理を行い、ここでも、シーンチェンジがないため、評価値判定部１１１は、「Ｔｒｕｅ」を出力したとする（ステップＳ１１２）。ピクチャタイプ選定部１０５は、判定結果が「Ｔｒｕｅ」であるため（ステップＳ１１３−Ｔｒｕｅ）、フレーム番号６のフレームのピクチャタイプをフレーム番号０とフレーム番号８のフレームを参照フレームとするＢピクチャとして選定する。
【００９２】
ピクチャタイプ記憶部１０６には、既に、フレーム番号６のフレームについて、Ｐピクチャであることを示す情報が書き込まれている。そのため、ピクチャタイプ選定部１０５は、フレーム番号６のフレームをＢピクチャとして選定したことを示す情報、及びフレーム番号０とフレーム番号８のフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に上書きして記憶させる（ステップＳ１１４）。ピクチャタイプ選定部１０５は、次の起点フレームとなるフレーム番号８を示す情報を参照グループ生成部１０３に出力する（ステップＳ１１５）。
【００９３】
図７（ｉ）に示すように、参照グループ生成部１０３は、フレーム番号８のフレームを起点フレームとして（ステップＳ１１６）、フレーム番号８，９，１０の３枚の連続するフレームを選択する（ステップＳ１０２−ＹＥＳ）。参照グループ生成部１０３は、フレーム番号８，９，１０のフレームをフレームＡ，Ｂ，Ｃとして含む参照グループ３０８を生成し、生成した参照グループ３０８の情報を結合判定部１０４とピクチャタイプ選定部１０５に出力する（ステップＳ１０５）。なお、参照グループ３０８において判定対象フレームは、フレーム番号９のフレームとなる。
【００９４】
結合判定部１０４は、参照グループ３０８に対して図４に示す結合判定処理を行う。図５（ａ）に示したように、フレーム番号８とフレーム番号９の間ではシーンチェンジがあるため、ここでは、評価値判定部１１１は、「Ｆａｌｓｅ」を出力したとする（ステップＳ１０６）。ピクチャタイプ選定部１０５は、結合判定部１０４が出力する判定結果が、「Ｆａｌｓｅ」であるため（ステップＳ１０７−Ｆａｌｓｅ）、フレーム番号９のフレームのピクチャタイプをＰピクチャとして選定する。ピクチャタイプ選定部１０５は、フレーム番号９のフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。ピクチャタイプ選定部１０５は、フレーム番号９のフレームを起点フレームとする（ステップＳ１０８）。
【００９５】
図８（ｊ）に示すように、参照グループ生成部１０３は、フレーム番号９のフレームを起点として３枚の連続するフレームを選択することができない（ステップＳ１０２−ＮＯ）。参照グループ生成部１０３は、残りのフレームであるフレーム番号１０のフレームのピクチャタイプをＰピクチャとして選定する指示情報をピクチャタイプ選定部１０５に出力する。ピクチャタイプ選定部１０５は、当該指示情報を受けて、フレーム番号１０のフレームをＰピクチャとして選定し、フレーム番号１０のフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ１０３）。
【００９６】
ピクチャタイプ選定部１０５は、ピクチャタイプ記憶部１０６に記憶されている情報を参照し、Ｐピクチャとして選定されている、フレーム番号８，９，１０のフレームについて、表示順で最も近い過去のＰピクチャのフレームを参照フレームとして選定する。表示順で最も近い過去のＰピクチャがない場合、Ｉピクチャのフレームを参照フレームとして選定する。ピクチャタイプ選定部１０５は、選定した参照フレームを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ１０４）。
【００９７】
フレーム番号８のフレームについては、表示順で最も近い過去のＰピクチャがないため、フレーム番号０のＩピクチャのフレームが参照フレームとなる。フレーム番号９のフレームについては、表示順で最も近い過去のＰピクチャは、フレーム番号８のフレームとなる。フレーム番号１０のフレームについては、表示順で最も近い過去のＰピクチャは、フレーム番号９のフレームとなる。
【００９８】
ピクチャタイプ記憶部１０６に記憶されている情報に基づいて構築された符号化構造を階層化すると、図８（ｋ）に示すような、４階層のＢピクチャの階層構造を有する符号化構造となる。
【００９９】
（結合判定処理の具体例）
次に、図９及び図１０を参照しつつ、結合判定部１０４による結合判定処理の例について説明する。図９は、結合判定処理を適用するＳ，Ｍ，Ｅフレームの例であり、図９（ｉ）は、Ｓ，Ｍ，Ｅフレームの３枚のフレームにおいてシーンチェンジがない例であり、（ｉｉ）は、ＭフレームとＥフレームの間でシーンチェンジがある例であり、（ｉｉｉ）は、ＳフレームとＭフレームの間でシーンチェンジがある例である。図９（ｉｖ）と（ｖ）は、ＳフレームからＥフレームにわたって部分的にシーンチェンジがある例である。
【０１００】
この例において、相対評価用閾値Ｔｈ＿ｍｉｎ，Ｔｈ＿ｍａｘとして、それぞれ「０．８」，「１．２」が定められており、絶対評価用閾値Ｔｈ＿ａｂｓとして、「３５０」が定められているとする。
【０１０１】
図９（ｉ）の場合、結合判定部１０４の評価値算出部１１０は、Ｌ０，Ｌ１，Ｂｉコストの評価値として、図１０に示すように、それぞれ「１５０」、「１５０」、「１００」を算出する（ステップＳ２０１）。評価値判定部１１１により式（１）を適用すると、相対値＝ｍｉｎ（１００，１５０）／１５０＝１００／１５０＝２／３となる（ステップＳ２０２，Ｓ２０３）。２／３＜０．８であるため（ステップＳ２０４、＜Ｔｈ＿ｍｉｎ）、評価値判定部１１１は、「Ｔｒｕｅ」を出力する（ステップＳ２０５）。
【０１０２】
図９（ｉｉ）の場合、結合判定部１０４の評価値算出部１１０は、Ｌ０，Ｌ１，Ｂｉコストの評価値として、図１０に示すように、それぞれ「１５０」、「５００」、「４００」を算出する（ステップＳ２０１）。評価値判定部１１１により式（１）を適用すると、相対値＝ｍｉｎ（４００，５００）／１５０＝４００／１５０＝８／３となる（ステップＳ２０２，Ｓ２０３）。８／３＞１．２であるため（ステップＳ２０４、＞Ｔｈ＿ｍａｘ）、評価値判定部１１１は、「Ｆａｌｓｅ」を出力する（ステップＳ２０６）。
【０１０３】
図９（ｉｉｉ）の場合、結合判定部１０４の評価値算出部１１０は、Ｌ０，Ｌ１，Ｂｉコストの評価値として、図１０に示すように、それぞれ「５００」、「１５０」、「４００」を算出する（ステップＳ２０１）。評価値判定部１１１により式（１）を適用すると、相対値＝ｍｉｎ（４００，１５０）／５００＝１５０／５００＝０．３となる（ステップＳ２０２，Ｓ２０３）。０．３＜０．８であるため（ステップＳ２０４、＜Ｔｈ＿ｍｉｎ）、評価値判定部１１１は、「Ｔｒｕｅ」を出力する（ステップＳ２０５）。
【０１０４】
図９（ｉｖ）の場合、結合判定部１０４の評価値算出部１１０は、Ｌ０，Ｌ１，Ｂｉコストの評価値として、図１０に示すように、それぞれ「３００」、「４００」、「３００」を算出する（ステップＳ２０１）。評価値判定部１１１により式（１）を適用すると、相対値＝ｍｉｎ（３００，４００）／３００＝３００／３００＝１となる（ステップＳ２０２，Ｓ２０３）。０．８≦１≦１．２であるため（ステップＳ２０４、≧Ｔｈ＿ｍｉｎかつ≦Ｔｈ＿ｍａｘ）、評価値判定部１１１は、Ｂｉコストの値の大きさを絶対評価用閾値に基づいて判定する（ステップＳ２０７）。Ｂｉコストの値「３００」＜Ｔｈ＿ａｂｓ「３５０」であるため（ステップＳ２０７、＜Ｔｈ＿ａｂｓ）、評価値判定部１１１は、「Ｔｒｕｅ」を出力する（ステップＳ２０８）。
【０１０５】
図９（ｖ）の場合、結合判定部１０４の評価値算出部１１０は、Ｌ０，Ｌ１，Ｂｉコストの評価値として、図１０に示すように、それぞれ「４００」、「５００」、「４００」を算出する（ステップＳ２０１）。評価値判定部１１１により式（１）を適用すると、相対値＝ｍｉｎ（４００，５００）／４００＝４００／４００＝１となる（ステップＳ２０２，Ｓ２０３）。０．８≦１≦１．２であるため（ステップＳ２０４、≧Ｔｈ＿ｍｉｎかつ≦Ｔｈ＿ｍａｘ）、評価値判定部１１１は、Ｂｉコストの値の大きさを絶対評価用閾値に基づいて判定する（ステップＳ２０７）。Ｂｉコストの値「４００」≧Ｔｈ＿ａｂｓ「３５０」であるため（ステップＳ２０７、≧Ｔｈ＿ａｂｓ）、評価値判定部１１１は、「Ｆａｌｓｅ」を出力する（ステップＳ２０６）。
【０１０６】
上記の第１の実施形態の構成により、符号化構造構築部１０において、符号化対象フレーム選択部１０１が、入力映像情報から予め定められるＧＯＰのサイズにしたがう枚数のフレームを選択してフレーム群を生成する。Ｉピクチャ選定部１０２は、フレーム群の最初のフレームをＩピクチャとして選定し、起点フレームとする。参照グループ生成部１０３は、起点フレームを起点として３枚の連続するフレームを選択し、選択した３枚のフレームをＡ，Ｂ，Ｃフレームとして参照グループを生成する。結合判定部１０４は、判定対象フレームであるＢフレームと、ＡとＣフレームの参照関係を結合するか否かを判定する。ピクチャタイプ選定部１０５は、評価値判定部１１１が、Ｂフレームと、ＡとＣフレームの参照関係を結合すると判定した場合、Ｂフレームを、ＡとＣフレームを参照フレームとするＢピクチャとして選定する。すなわち、符号化構造構築部１０では、実際の符号化を行うような演算を行っておらず、フレーム群から選択した参照グループに含まれる３つのフレームに基づいて、参照関係を結合するか否かを判定している。このため、第１の実施形態の符号化構造構築部１０では、符号化効率の高い符号化構造を低演算量で求めることが可能となる。
【０１０７】
また、参照グループ生成部１０３は、結合判定部１０４が、判定対象フレームと最初と最後のフレームの参照関係を結合すると判定した隣接する２つの参照グループを結合して重複するフレームを判定対象フレームとする新たな参照グループを生成することを繰り返す。結合判定部１０４は、参照グループ生成部１０３が、新たに生成した参照グループのα，β，γフレームに基づいて、結合判定処理を行う。また、第１の実施形態の符号化構造構築部１０では、２階層以上の深い階層の符号化構造を構築することが可能となっており、符号化効率を向上させることが可能となっている。例えば、上述したように、図８（ｋ）の例では、４階層のＢピクチャの階層構造を有する符号化構造を構築することができることを示している。
【０１０８】
（第２の実施形態）
図１１は、本発明の第２の実施形態による符号化構造構築部１０ａの構成を示すブロック図である。符号化構造構築部１０ａは、第１の実施形態の映像符号化装置１の符号化構造構築部１０に置き換えて適用される機能部である。なお、第２の実施形態の符号化構造構築部１０ａが適用される場合、映像符号化装置の符号を「１」に替えて「１ａ」で表すものとする。第２の実施形態において、第１の実施形態と同一の構成については、同一の符号を付し、以下、第１の実施形態の符号化構造構築部１０と異なる構成について説明する。
【０１０９】
符号化構造構築部１０ａは、符号化対象フレーム選択部１０１、Ｉピクチャ選定部１０２ａ、参照グループ生成部１０３ａ、結合判定部１０４、ピクチャタイプ選定部１０５ａ、ピクチャタイプ記憶部１０６、ブロック出力部１０７、及び参照グループ記憶部１０８を備える。
【０１１０】
符号化構造構築部１０ａにおいて、Ｉピクチャ選定部１０２ａは、フレーム群の最初のフレームをＩピクチャとして選定する。参照グループ生成部１０３ａは、初期値をｉ＝０、ｊ＝０とし、フレーム群からフレーム番号が「２ｊ」，「２ｊ＋２ｉ」，「２ｊ＋２（ｉ＋１）」の３枚のフレームを含む参照グループを生成することができなくなるまで、ｊに１を加算しつつ、ｊがＮ／２未満の間繰り返す。ここで、Ｎの値は、フレーム群に含まれるフレームに付与されるフレーム番号の最大値であり、フレーム群のフレーム数から「１」減算した値である。
【０１１１】
また、参照グループ生成部１０３ａは、選択したフレーム番号が「２ｊ」，「２ｊ＋２ｉ」，「２ｊ＋２（ｉ＋１）」のフレームの組み合わせの各々において、３つのフレームをＡ，Ｂ，Ｃフレームとし、Ａ，Ｂ，Ｃフレームを含む、ｉとｊのインデックスが付いた参照グループＲｅｆ［ｉ］［ｊ］を生成する（ただし、Ａ，Ｂ，Ｃフレームを含む参照グループを生成する場合、ｉ＝０に固定され、ｊのみが変数となる）。また、参照グループ生成部１０３ａは、生成した参照グループＲｅｆ［０］［ｊ］を参照グループ記憶部１０８に書き込んで記憶させる。
【０１１２】
また、参照グループ生成部１０３ａは、初期値をｉ＝１，ｊ＝０として、参照グループＲｅｆ［ｉ−１］［ｊ］とＲｅｆ［ｉ−１］［ｊ＋１］の両方において、結合判定部１０４が判定した判定結果が「Ｔｒｕｅ」となっている組み合わせの検出を、ｊに２を加算しつつ、ｊがＮ／２未満の間繰り返すことを、更に、ｉに１加算しつつ、ｉがｄｅｐｔｈ＿ｍａｘ未満の間繰り返し行う。ここで、ｄｅｐｔｈ＿ｍａｘは、予め定めらえる構築する符号化構造の階層数を示す値であり、３階層の場合、ｄｅｐｔｈ＿ｍａｘは、「３」となる。
【０１１３】
また、参照グループ生成部１０３ａは、検出した参照グループＲｅｆ［ｉ−１］［ｊ］とＲｅｆ［ｉ−１］［ｊ＋１］の組み合わせの各々において、Ｒｅｆ［ｉ−１］［ｊ］の最初と最後のフレームと、Ｒｅｆ［ｉ−１］［ｊ＋１］の最後のフレームの３つのフレームをα，β，γフレームとして選択する。また、参照グループ生成部１０３ａは、選択したα，β，γフレーム含む新たな参照グループを参照グループＲｅｆ［ｉ］「ｊ／２」として参照グループ記憶部１０８に書き込んで記憶させる。
【０１１４】
ピクチャタイプ選定部１０５ａは、結合判定部１０４が出力する判定結果にしたがって、参照グループＲｅｆ［ｉ］［ｊ］に含まれるフレームのピクチャタイプを選定する。また、ピクチャタイプ選定部１０５ａは、参照グループ生成部１０３ａが、フレーム番号が「２ｊ」，「２ｊ＋２ｉ」，「２ｊ＋２（ｉ＋１）」のフレームを選択できないと判定した場合、残りのフレームをＰピクチャとして選定する。
【０１１５】
また、ピクチャタイプ選定部１０５ａは、全てのフレームについて、ピクチャタイプを選定した後、Ｐピクチャとして選定したフレームに対して、当該フレームに表示順で最も近い過去のＰピクチャとして選定されたフレームを当該フレームの参照フレームとして選定する。表示順で最も近い過去のＰピクチャがない場合、Ｉピクチャのフレームを当該フレームの参照フレームとして選定する。参照グループ記憶部１０８は、参照グループ生成部１０３ａが生成した参照グループＲｅｆ［ｉ］［ｊ］を記憶する。
【０１１６】
（第２の実施形態の符号化構造構築処理）
次に、第２の実施形態の符号化構造構築部１０ａによる処理について説明する。図１２及び図１３は、符号化構造構築部１０による符号化構造構築処理の流れを示すフローチャートである。図１２と図１３に示す処理は、符号Ａで示される箇所で処理が接続される連続した処理である。図１２に示す符号Ａで示される箇所に至るまでの処理は、ｉ＝０で示される１階層目の符号化構造を構築する処理であり、図１３に示す処理は、ｉ＝１，２で示される２階層目、３階層目の符号化構造を構築する処理である。
【０１１７】
符号化対象フレーム選択部１０１は、入力映像情報から予め定められるＧＯＰのサイズにしたがう枚数のフレームを選択してフレーム群を生成する。符号化対象フレーム選択部１０１は、生成したフレーム群に対して表示順に「０」からフレーム番号を付与してＩピクチャ選定部１０２ａとブロック出力部１０７に出力する。Ｉピクチャ選定部１０２ａは、フレーム群の最初のフレーム、すなわちフレーム番号０のフレームのピクチャタイプをＩピクチャとして選定する。Ｉピクチャ選定部１０２ａは、フレーム番号０のフレームをＩピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ３０１）。
【０１１８】
参照グループ生成部１０３ａは、ｉ＝０，ｊ＝０とし（ステップＳ３０２）、フレーム群からフレーム番号が「２ｊ」，「２ｊ＋２ｉ」，「２ｊ＋２（ｉ＋１）」の３つのフレームを選択できるか否かを判定する（ステップＳ３０３）。
【０１１９】
参照グループ生成部１０３ａは、３枚のフレームを選択することができると判定した場合（ステップＳ３０３−ＹＥＳ）、参照グループ生成部１０３ａは、３枚のフレームを表示順にＡ，Ｂ，Ｃフレームとして含む参照グループＲｅｆ［０］［ｊ］を生成する。参照グループ生成部１０３ａは、生成した参照グループＲｅｆ［０］［ｊ］を参照グループ記憶部１０８に書き込んで記憶させる（ステップＳ３０５）。なお、当該参照グループにおいて判定対象フレームは、Ｂフレームとなる。
【０１２０】
結合判定部１０４は、参照グループ生成部１０３ａによって参照グループ記憶部１０８に参照グループＲｅｆ［０］［ｊ］の情報が書き込まれると、書き込まれた参照グループＲｅｆ［０］［ｊ］に含まれるＡ，Ｂ，ＣフレームをＳ，Ｍ，Ｅフレームとして図４に示す結合判定処理を行う（ステップＳ３０６）。
【０１２１】
ピクチャタイプ選定部１０５ａは、結合判定部１０４が出力する判定結果を判定する（ステップＳ３０７）。ピクチャタイプ選定部１０５ａは、判定結果が「Ｆａｌｓｅ」の場合（ステップＳ３０７−Ｆａｌｓｅ）、参照グループＲｅｆ［０］［ｊ］のＢフレームとＣフレームのピクチャタイプをＰピクチャとして選定する。ピクチャタイプ選定部１０５ａは、参照グループＲｅｆ［０］［ｊ］のＢフレームとＣフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ３０８）。
【０１２２】
一方、ピクチャタイプ選定部１０５ａは、判定結果が「Ｔｒｕｅ」の場合（ステップＳ３０７−Ｔｒｕｅ）、参照グループＲｅｆ［０］［ｊ］のＢフレームのピクチャタイプをＡフレームとＣフレームを参照フレームとするＢピクチャとして選定する。ピクチャタイプ選定部１０５ａは、参照グループＲｅｆ［０］［ｊ］のＢフレームをＢピクチャとして選定したことを示す情報、及びＡフレームとＣフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。また、ピクチャタイプ選定部１０５ａは、参照グループＲｅｆ［０］［ｊ］のＣフレームのピクチャタイプをＰピクチャとして選定する。ピクチャタイプ選定部１０５ａは、参照グループＲｅｆ［０］［ｊ］のＣフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ３０９）。
【０１２３】
ステップＳ３０８及びステップＳ３０９の処理の後、ピクチャタイプ選定部１０５ａは、処理を継続する指示情報を参照グループ生成部１０３ａに出力する。参照グループ生成部１０３ａは、ｊの値に「１」を加算し（ステップＳ３１０）、ｊの値がＮ／２未満か否かを判定する（ステップＳ３１１）。参照グループ生成部１０３ａは、ｊの値がＮ／２未満であると判定した場合（ステップＳ３１１−ＹＥＳ）、ステップＳ３０３からの処理を繰り返す。一方、参照グループ生成部１０３ａは、ｊの値がＮ／２未満でないと判定した場合（ステップＳ３１１−ＮＯ）、符号Ａで示される箇所を介して図１３に示す処理を開始する。
【０１２４】
一方、参照グループ生成部１０３ａは、３枚のフレームを選択することができないと判定した場合（ステップＳ３０３−ＮＯ）、フレーム群の残りのフレームをＰピクチャとして選定させる指示情報をピクチャタイプ選定部１０５ａに出力する。ピクチャタイプ選定部１０５ａは、参照グループ生成部１０３ａから当該指示情報を受けて、残りのフレームのピクチャタイプをＰピクチャとして選定し、残りのフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ３０４）。参照グループ生成部１０３ａは、当該指示情報をピクチャタイプ選定部１０５ａに出力し、その後、符号Ａで示される箇所を介して図１３に示す処理を開始する。
【０１２５】
図１３に示すように、参照グループ生成部１０３ａは、ｉ＝１，ｊ＝０とし（ステップＳ３１２）、結合判定部１０４の判定結果記憶部１１２を参照し、参照グループＲｅｆ［ｉ−１］［ｊ］と、Ｒｅｆ［ｉ−１］［ｊ＋１］の判定結果が共に「Ｔｒｕｅ」であるか否かを判定する（ステップＳ３１３）。参照グループ生成部１０３ａは、参照グループＲｅｆ［ｉ−１］［ｊ］と、Ｒｅｆ［ｉ−１］［ｊ＋１］の判定結果が共に「Ｔｒｕｅ」でないと判定した場合（ステップＳ３１３−ＮＯ）、処理をステップＳ３１８に進める。
【０１２６】
一方、参照グループ生成部１０３ａは、参照グループＲｅｆ［ｉ−１］［ｊ］と、Ｒｅｆ［ｉ−１］［ｊ＋１］の判定結果が共に「Ｔｒｕｅ」であると判定した場合（ステップＳ３１３−ＹＥＳ）、参照グループＲｅｆ［ｉ−１］［ｊ］の最初と最後のフレームと、参照グループＲｅｆ［ｉ−１］［ｊ＋１］の最後のフレームの３つのフレームをα，β，γフレームとして選択する。参照グループ生成部１０３ａは、選択したα，β，γフレームを含む参照グループＲｅｆ［ｉ］［ｊ／２］を生成し、生成した参照グループＲｅｆ［ｉ］［ｊ／２］を参照グループ記憶部１０８に書き込んで記憶させる（ステップＳ３１４）。
【０１２７】
結合判定部１０４は、参照グループ生成部１０３ａによって参照グループ記憶部１０８に参照グループＲｅｆ［ｉ］［ｊ／２］の情報が書き込まれると、書き込まれた参照グループＲｅｆ［ｉ］［ｊ／２］に含まれるα，β，γフレームをＳ，Ｍ，Ｅフレームとして図４に示す結合判定処理を行う（ステップＳ３１５）。
【０１２８】
ピクチャタイプ選定部１０５ａは、結合判定部１０４が出力する判定結果を判定する（ステップＳ３１６）。ピクチャタイプ選定部１０５ａは、判定結果が「Ｆａｌｓｅ」の場合（ステップＳ３１６−Ｆａｌｓｅ）、処理をステップＳ３１８に進める指示情報を参照グループ生成部１０３ａに出力する。
【０１２９】
一方、ピクチャタイプ選定部１０５ａは、判定結果が「Ｔｒｕｅ」の場合（ステップＳ３１６−Ｔｒｕｅ）、参照グループＲｅｆ［ｉ］［ｊ／２］のβフレームのピクチャタイプをαフレームとγフレームを参照フレームとするＢピクチャとして選定する。ピクチャタイプ選定部１０５ａは、参照グループＲｅｆ［ｉ］［ｊ／２］のβフレームをＢピクチャとして選定したことを示す情報、及びαフレームとγフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。また、ピクチャタイプ選定部１０５ａは、参照グループＲｅｆ［ｉ］［ｊ／２］のγフレームのピクチャタイプをＰピクチャとして選定する。ピクチャタイプ選定部１０５ａは、参照グループＲｅｆ［ｉ］［ｊ／２］のγフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。ピクチャタイプ選定部１０５ａは、処理をステップＳ３１８に進める指示情報を参照グループ生成部１０３ａに出力する（ステップＳ３１７）。
【０１３０】
参照グループ生成部１０３ａは、ｊの値に「２」を加算し（ステップＳ３１８）、ｊの値がＮ／２未満であるか否かを判定する（ステップＳ３１９）。参照グループ生成部１０３ａは、ｊの値がＮ／２未満であると判定した場合（ステップＳ３１９−ＹＥＳ）、ステップＳ３１３からの処理を繰り返す。
【０１３１】
一方、参照グループ生成部１０３ａは、ｊの値がＮ／２未満でないと判定した場合（ステップＳ３１９−ＮＯ）、ｉの値に「１」を加算し、ｊ＝０とする（ステップＳ３２０）。
参照グループ生成部１０３ａは、ｉの値が、ｄｅｐｔｈ＿ｍａｘ（ここでは、ｄｅｐｔｈ＿ｍａｘ＝３）未満であるか否かを判定する（ステップＳ３２１）。参照グループ生成部１０３ａは、ｉの値が、ｄｅｐｔｈ＿ｍａｘ未満であると判定した場合（ステップＳ３２１−ＹＥＳ）、ステップＳ３１３からの処理を繰り返す。一方、参照グループ生成部１０３ａは、ｉの値が、ｄｅｐｔｈ＿ｍａｘ未満でないと判定した場合（ステップＳ３２１−ＮＯ）、ピクチャタイプ選定部１０５ａに、Ｐピクチャのフレームに対する参照フレームを選択させる指示情報を出力する。
【０１３２】
ピクチャタイプ選定部１０５ａは、当該指示情報を受けて、Ｐピクチャとして選定したフレームの各々に対して、当該フレームに表示順で最も近い過去のＰピクチャのフレームを当該フレームの参照フレームとして選定する。表示順で最も近い過去のＰピクチャがない場合、Ｉピクチャのフレームを当該フレームの参照フレームとして選定する。ピクチャタイプ選定部１０５ａは、各Ｐピクチャに対して選定した参照フレームの情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ３２２）。
【０１３３】
これにより、ピクチャタイプ記憶部１０６に、最終的に構築された符号化構造の情報が記憶されることになる。ブロック出力部１０７は、内部の記憶領域に一時的に符号化対象フレーム選択部１０１から受けたフレーム群を記憶しており、ピクチャタイプ記憶部１０６に記憶されている符号化構造に基づく順番で内部の記憶領域からフレームを読み出す。ブロック出力部１０７は、読み出したフレームの各々をラスタースキャンの順にＣＵブロックに分解して符号化対象ブロックとして出力し、符号化構造構築部１０ａは、１つのフレーム群についての処理を終了する。
【０１３４】
（第２の実施形態の符号化構造構築処理の具体例）
次に、図１４から図１６を参照しつつ、図１４（ａ）に示すフレーム群に、図１２及び図１３に示した第２の実施形態の符号化構造構築処理を適用した場合の例について説明する。符号化対象フレーム選択部１０１が、入力映像情報から図１４（ａ）に示すフレーム群を生成する。当該フレーム群は、フレーム番号４とフレーム番号５のフレームにおいてシーンチェンジが含まれている。
【０１３５】
図１４（ｂ）に示すように、Ｉピクチャ選定部１０２ａによってフレーム番号０のフレームがＩピクチャとして選定された後、参照グループ生成部１０３ａによって、フレーム番号（０，１，２）のフレームを含む参照グループＲｅｆ［０］［０］が参照グループ記憶部１０８に書き込まれる（ステップＳ３０３，Ｓ３０５）。結合判定部１０４は、参照グループ記憶部１０８に書き込まれた参照グループＲｅｆ［０］［０］に対して図４に示す結合判定処理を行い、ここでは、シーンチェンジがないため、結合判定部１０４の評価値判定部１１１が「Ｔｒｕｅ」を出力したとする（ステップＳ３１５）。
【０１３６】
ピクチャタイプ選定部１０５ａは、結合判定部１０４が出力する判定結果が、「Ｔｒｕｅ」であるため、フレーム番号１のフレームのピクチャタイプをフレーム番号０とフレーム番号２のフレームを参照フレームとするＢピクチャとして選定する。ピクチャタイプ選定部１０５は、フレーム番号２のフレームをＢピクチャとして選定したことを示す情報、及びフレーム番号０とフレーム番号２のフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる。
【０１３７】
また、ピクチャタイプ選定部１０５ａは、フレーム番号２のフレームのピクチャタイプをＰピクチャとして選定し、フレーム番号２のフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ３０９）。
【０１３８】
参照グループ生成部１０３ａは、ｊの値がＮ／２未満の間、ｊに１を加算し、フレーム番号（２，３，４）のフレームを含む参照グループＲｅｆ［０］［１］、フレーム番号（４，５，６）のフレームを含む参照グループＲｅｆ［０］［２］、フレーム番号（６，７，８）のフレームを含む参照グループＲｅｆ［０］［３］、フレーム番号（８，９，１０）のフレームを含む参照グループＲｅｆ［０］［４］を参照グループ記憶部１０８に書き込んで記憶させていく。結合判定部１０４は、新たな参照グループが参照グループ記憶部１０８に書き込まれるごとに、図４に示す結合判定処理を行う。その結果、図１４（ｂ）に示すように、シーンチェンジを含む参照グループＲｅｆ［０］［２］については、判定結果として「Ｆａｌｓｅ」を出力し、参照グループＲｅｆ［０］［２］以外については「Ｔｒｕｅ」を出力する。
【０１３９】
その結果、ピクチャタイプ選定部１０５ａは、フレーム番号１〜１０のフレームについて図１４（ｂ）に示すようなピクチャタイプを選定する。すなわち、結合判定部１０４によって、「Ｔｒｕｅ」と判定された参照グループＲｅｆ［０］［０］，Ｒｅｆ［０］［１］，Ｒｅｆ［０］［３］、Ｒｅｆ［０］［４］の各々の判定対象フレームのＢフレームは、各々のＡとＣのフレームを参照するＢピクチャとして選定され、Ｃフレームは、Ｐピクチャとして選定される。これに対して、結合判定部１０４によって、「Ｆａｌｓｅ」と判定された参照グループＲｅｆ［０］［２］のフレームは、ＢフレームとＣフレームは、Ｐピクチャとして選定される。
【０１４０】
参照グループ生成部１０３ａが、図１３に示すように、ｉ＝１，ｊ＝０として（ステップＳ３１２）、最初に、結合判定部１０４の判定結果記憶部１１２に記憶されている参照グループＲｅｆ［０］［０］と、参照グループＲｅｆ［０］［１］の判定結果を参照する。参照グループＲｅｆ［０］［０］と、参照グループＲｅｆ［０］［１］の判定結果は、共に「Ｔｒｕｅ」であるため（ステップＳ３１３−ＹＥＳ）、参照グループ生成部１０３ａは、参照グループＲｅｆ［０］［０］の最初と最後のフレーム、及び参照グループＲｅｆ［０］［１］の最後のフレーム、すなわちフレーム番号０，２，４のフレームをα、β，γフレームとして含む参照グループＲｅｆ［１］［０］を生成する。
【０１４１】
図１５（ｃ）に示すように、参照グループ生成部１０３ａは、生成した参照グループＲｅｆ［１］［０］を参照グループ記憶部１０８に書き込んで記憶させる（ステップＳ３１４）。結合判定部１０４は、参照グループ記憶部１０８に書き込まれた参照グループＲｅｆ［１］［０］に対して図４に示す結合判定処理を行い、ここでは、シーンチェンジがないため、評価値判定部１１１は、「Ｔｒｕｅ」を出力したとする（ステップＳ３１５）。ピクチャタイプ選定部１０５ａは、判定結果が「Ｔｒｕｅ」であるため（ステップＳ３１６−Ｔｒｕｅ）、参照グループＲｅｆ［１］［０］の判定対象フレームであるフレーム番号２のフレームのピクチャタイプをフレーム番号０とフレーム番号４のフレームを参照フレームとするＢピクチャとして選定する。
【０１４２】
ピクチャタイプ記憶部１０６には、既に、フレーム番号２のフレームについて、Ｐピクチャであることを示す情報が書き込まれている。そのため、ピクチャタイプ選定部１０５ａは、フレーム番号２のフレームをＢピクチャとして選定したことを示す情報、及びフレーム番号０とフレーム番号４のフレームが参照フレームであることを示す情報をピクチャタイプ記憶部１０６に上書きして記憶させる。
【０１４３】
また、ピクチャタイプ選定部１０５ａは、γフレームであるフレーム番号４のフレームのピクチャタイプをＰピクチャとして選定する。ピクチャタイプ記憶部１０６には、既に、フレーム番号４のフレームについて、Ｐピクチャであることを示す情報が書き込まれているが、ピクチャタイプ選定部１０５ａは、フレーム番号４のフレームをＰピクチャとして選定したことを示す情報をピクチャタイプ記憶部１０６に上書きして記憶させる（ステップＳ３１７）。
【０１４４】
参照グループ生成部１０３ａは、ｊの値に２を加算してｊ＝２とし（ステップＳ３１８）、ｊの値がＮ／２（Ｎ＝１０）未満であるため（ステップＳ３１９−ＹＥＳ）、結合判定部１０４の判定結果記憶部１１２に記憶されている参照グループＲｅｆ［０］［２］と、参照グループＲｅｆ［０］［３］の判定結果を参照する。参照グループＲｅｆ［０］［２］の判定結果は「Ｆａｌｓｅ」であるため、参照グループ生成部１０３ａは、参照グループＲｅｆ［０］［２］と、参照グループＲｅｆ［０］［３］の判定結果が共に「Ｔｒｕｅ」でないと判定する（ステップＳ３１３−ＮＯ）。したがって、図１５（ｃ）に、説明の便宜上示している参照グループＲｅｆ［１］［１］は、参照グループ生成部１０３ａによって生成されないことになる。
【０１４５】
参照グループ生成部１０３ａは、ｊの値に２を加算してｊ＝４とし（ステップＳ３１８）、ｊの値がＮ／２（Ｎ＝１０）未満であるため（ステップＳ３１９−ＹＥＳ）、参照グループＲｅｆ［０］［４］と、参照グループＲｅｆ［０］［５］の判定結果を参照しようとする。しかし、参照グループＲｅｆ［０］［５］が存在しないため、参照グループ生成部１０３ａは、参照グループＲｅｆ［０］［４］と、参照グループＲｅｆ［０］［５］の判定結果が、共に「Ｔｒｕｅ」でないと判定する（ステップＳ３１３−ＮＯ）。参照グループ生成部１０３ａは、ｊの値に２を加算してｊ＝６とし（ステップＳ３１８）、ｊの値がＮ／２（Ｎ＝１０）未満ではなくなるため（ステップＳ３１９−ＮＯ）、ｉの値に「１」を加算してｉ＝１とし、ｊ＝０とする（ステップＳ３２０）。
【０１４６】
ｉの値は、ｄｅｐｔｈ＿ｍａｘ（ｄｅｐｔｈ＿ｍａｘ＝３）未満であるため（ステップＳ３２１−ＹＥＳ）、参照グループ生成部１０３ａは、結合判定部１０４の判定結果記憶部１１２に記憶されている参照グループＲｅｆ［１］［０］と、参照グループＲｅｆ［１］［１］の判定結果を参照しようとする。しかし、前述の通り、参照グループＲｅｆ［１］［１］は生成されていないため、参照グループ生成部１０３ａは、参照グループＲｅｆ［０］［４］と、参照グループＲｅｆ［０］［５］の判定結果が、共に「Ｔｒｕｅ」でないと判定する（ステップＳ３１３−ＮＯ）。したがって、図１５（ｄ）に、説明の便宜上示している参照グループＲｅｆ［２］［０］は、参照グループ生成部１０３ａによって生成されないことになる。
【０１４７】
その後、ステップＳ３１８及びＳ３１９の処理が、ｊがＮ／２未満でなくなるまで繰り返され、更にステップＳ３２０においてｉの値に「１」が加えられｉ＝２，ｊ＝０となる。ｉの値は、ｄｅｐｔｈ＿ｍａｘ未満であるため（ステップＳ３２１−ＹＥＳ）、処理が継続されるが、前述の通り、図１５（ｄ）に示す参照グループＲｅｆ［２］［０］は、参照グループ生成部１０３ａによって生成されていないため、ステップＳ３１３の判定は、「ＮＯ」となる。再び、ステップＳ３１８及びＳ３１９の処理が、ｊが、Ｎ／２未満でなくなるまで繰り替えされ、ステップＳ３２０においてｉの値に「１」が加えられて、ｉ＝３，ｊ＝０となる。参照グループ生成部１０３ａは、ｉの値が、ｄｅｐｔｈ＿ｍａｘ未満でなくなるため（ステップＳ３２１−ＮＯ）、ピクチャタイプ選定部１０５ａに、Ｐピクチャのフレームに対する参照フレームを選択させる指示情報を出力する。
【０１４８】
ピクチャタイプ選定部１０５ａは、当該指示情報を受けて、Ｐピクチャとして選定したフレームの各々に対して、当該フレームに表示順で最も近い過去のＰピクチャのフレームを当該フレームの参照フレームとして選定する。表示順で最も近い過去のＰピクチャがない場合、Ｉピクチャのフレームを当該フレームの参照フレームとして選定する。ピクチャタイプ選定部１０５ａは、各Ｐピクチャに対して選定した参照フレームの情報をピクチャタイプ記憶部１０６に書き込んで記憶させる（ステップＳ３２２）。これにより、ピクチャタイプ記憶部１０６に、図１６（ｅ）に示す、２階層のＢピクチャの階層構造を有する符号化構造が記憶されることになる。
【０１４９】
上記の第２の実施形態の構成により、符号化構造構築部１０ａにおいて、符号化対象フレーム選択部１０１が、入力映像情報から予め定められるＧＯＰのサイズにしたがう枚数のフレームを選択してフレーム群を生成する。Ｉピクチャ選定部１０２ａは、フレーム群の最初のフレームをＩピクチャとして選定する。参照グループ生成部１０３ａは、ｉ＝０、ｊ＝０とし、フレーム群からフレーム番号が「２ｊ」，「２ｊ＋２ｉ」，「２ｊ＋２（ｉ＋１）」のフレームをｊに「１」を加算しつつ繰り返し選択し、選択した３枚のフレームをＡ，Ｂ，Ｃフレームとして含む参照グループＲｅｆ［０］［ｊ］を生成する。結合判定部１０４は、判定対象フレームであるＢフレームと、ＡとＣフレームの参照関係を結合するか否かを判定する。ピクチャタイプ選定部１０５ａは、評価値判定部１１１が、Ｂフレームと、ＡとＣフレームの参照関係を結合すると判定した場合、Ｂフレームを、ＡとＣフレームを参照フレームとするＢピクチャとして選定する。すなわち、符号化構造構築部１０ａでは、実際の符号化を行うような演算を行っておらず、フレーム群から選択した参照グループＲｅｆ［ｉ］［ｊ］に含まれる３つのフレームに基づいて、参照関係を結合するか否かを判定している。このため、第２の実施形態の符号化構造構築部１０ａでは、符号化効率の高い符号化構造を低演算量で求めることが可能となる。
【０１５０】
また、参照グループ生成部１０３ａは、評価値判定部１１１が、判定対象フレームと最初と最後のフレームの参照関係を結合すると判定した隣接する２つの参照グループを結合して重複するフレームを判定対象フレームとする新たな参照グループを生成することを繰り返す。結合判定部１０４は、参照グループ生成部１０３ａが、新たに生成した参照グループのα，β，γフレームに基づいて、結合判定処理を行う。これにより、第２の実施形態の符号化構造構築部１０ａでは、２階層以上の深い階層の符号化構造を構築することが可能となっており、符号化効率を向上させることが可能となっている。
【０１５１】
上記の第１及び第２の実施形態の符号化構造構築部１０，１０ａでは、判定対象フレームと、最初と最後のフレームの３つのフレームに基づいて、これらを結合するか否かの結合判定を行っている。そのため、実際の符号化を行うような多くの演算量を必要としていない。また、結合すると判定した場合、結合判定において用いた最後と最初のフレームをそのまま判定対象フレームの参照フレームとしているので、算出した結果を実際の符号化で再利用することができている。その結果として、第１及び第２の実施形態の符号化構造構築部１０，１０ａでは、非特許文献１及び２に記載の技術よりも、大幅に演算量を削減することができている。
【０１５２】
また、上記の第１及び第２の実施形態において、結合判定部１０４は、Ｌ０コスト、Ｌ１コスト、Ｂｉコストという３つの評価値に基づいて、参照グループの判定対象フレームと、最初と最後のフレームの参照関係を結合するか否かを判定しているが、本発明は、当該実施の形態に限られない。Ｌ０コスト、Ｌ１コスト、Ｂｉコストという評価値以外の評価値に基づいて、参照グループの判定対象フレームと、最初と最後のフレームの参照関係を結合するか否かを判定し、「Ｔｒｕｅ」または「Ｆａｌｓｅ」を出力する構成を適用してもよい。
【０１５３】
なお、上記の第１及び第２の実施形態では、結合判定の結果にしたがって、ＢフレームをＰピクチャとして選定したり、ＣフレームをＰピクチャとして選定したり、γフレームをＰピクチャとして選定したり、また、３つのフレームを選択することができない場合に、残りのフレームをＰピクチャとして選定したりしているが、本発明の構成は、当該実施の形態に限られない。例えば、Ｉピクチャから予め定められる間隔で、事前にＰピクチャとするフレームを選定しておいてもよいし、結合判定の結果、Ｂピクチャとするフレームを全て選定した後、ＩピクチャとＢピクチャのフレーム以外のフレームをＰピクチャとするようにしてもよい。
【０１５４】
また、上記の第１及び第２の実施形態では、３枚の連続するフレームを参照グループとして生成するようにしているが、３枚以上であってもよい。
【０１５５】
また、上記の第１及び第２の実施形態では、隣接する参照グループにおいて重複するフレームが１枚になるように、隣接する参照グループを生成するようにしているが、１枚以上のフレームが重複するように隣接する参照グループを生成してもよい。複数枚のフレームが重複する場合、重複しているフレームのいずれかから判定対象フレームが選択されることになる。
【０１５６】
また、上記の第１及び第２の実施形態において参照グループ生成部１０３，１０３ａは、隣接する参照グループの判定結果に基づいて、新たな参照グループを生成して２階層以上の符号化構造を構築するようになっているが、１階層のみを構築する処理を行うようにしてもよい。
【０１５７】
また、上記の第１及び第２の実施形態において参照グループ生成部１０３，１０３ａは、表示順で過去の隣接する参照グループを結合して新たな参照グループを生成するようにしているが、本発明の実施の形態は、当該実施の形態に限られない。例えば、表示順で未来の隣接する参照グループを結合してもよいし、過去と未来の双方で隣接する参照グループを結合してもよい。
【０１５８】
また、上記の第１及び第２の実施形態において、評価値判定部１１１は、相対評価用閾値であるＴｈ＿ｍｉｎ及びＴｈ＿ｍａｘ、並びに絶対評価用閾値であるＴｈ＿ａｂｓに基づく判定を行っている。この判定において、評価値判定部１１１は、Ｔｈ＿ｍｉｎ未満であるか否か、Ｔｈ＿ｍａｘを超過しているか否か、Ｔｈ＿ａｂｓ未満であるか否かに基づく判定を行っているが、未満であるか否か、超過しているか否かという判定は、一例であり、Ｔｈ＿ｍｉｎ以下であるか否か、Ｔｈ＿ｍａｘ以上であるか否か、Ｔｈ＿ａｂｓ以下であるか否かに基づいて判定するようにしてもよい。
【０１５９】
上述した第１及び第２の実施形態における映像符号化装置１，１ａをコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＦＰＧＡ（Field Programmable Gate Array）等のプログラマブルロジックデバイスを用いて実現されるものであってもよい。
【０１６０】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【０１６１】
１０…符号化構造構築部，１０１…符号化対象フレーム選択部，１０２…Ｉピクチャ選定部，１０３…参照グループ生成部，１０４…結合判定部，１０５…ピクチャタイプ選定部，１０６…ピクチャタイプ記憶部，１０７…ブロック出力部，１１０…評価値算出部，１１１…評価値判定部，１１２…判定結果記憶部
【図１】
2018182394.tif 000003
【図２】
2018182394.tif 000004
【図３】
2018182394.tif 000005
【図４】
2018182394.tif 000006
【図５】
2018182394.tif 000007
【図６】
2018182394.tif 000008
【図７】
2018182394.tif 000009
【図８】
2018182394.tif 000010
【図９】
2018182394.tif 000011
【図１０】
2018182394.tif 000012
【図１１】
2018182394.tif 000013
【図１２】
2018182394.tif 000014
【図１３】
2018182394.tif 000015
【図１４】
2018182394.tif 000016
【図１５】
2018182394.tif 000017
【図１６】
2018182394.tif 000018
【図１７】
2018182394.tif 000019
【図１８】
2018182394.tif 000020
【図１９】
2018182394.tif 000021
【図２０】
2018182394.tif 000022
【図２１】
2018182394.tif 000023