(57)【要約】【課題】最適なフレームの順番を求めること。【解決手段】多視点画像情報を映像形式に変換し映像符号化方式によって符号化する符号化装置であって、多視点画像情報を構成する各視点の画像である視点画像間の相関を示す指標値を算出する指標値算出部と、指標値に基づいて、映像全体として映像の変化を滑らかにする視点画像の順番を求め、求めた順番で視点画像を並べて映像形式のフレームとし、符号化対象の映像情報を生成する映像生成部と、を備える符号化装置。【選択図】図１
2020167479.tif 000002
【特許請求の範囲】
【請求項１】
多視点画像情報を映像形式に変換し映像符号化方式によって符号化する符号化装置であって、
前記多視点画像情報を構成する各視点の画像である視点画像間の相関を示す指標値を算出する指標値算出部と、
前記指標値に基づいて、前記映像全体として前記映像の変化を滑らかにする前記視点画像の順番を求め、求めた前記順番で前記視点画像を並べて前記映像形式のフレームとし、符号化対象の映像情報を生成する映像生成部と、
を備える符号化装置。
【請求項２】
前記指標値は、前記視点画像が類似しているほど小さい値となり、
前記映像生成部は、
全ての隣接する前記視点画像間に対して前記指標値算出部が算出する前記指標値の合計値を最小、または、略最小にする前記順番を求める、請求項１に記載の符号化装置。
【請求項３】
前記映像生成部は、前記映像符号化方式における参照構造を参照することなく、前記順番を求める、請求項１又は２に記載の符号化装置。
【請求項４】
多視点画像情報を映像形式に変換し映像符号化方式によって符号化する符号化方法であって、
前記多視点画像情報を構成する各視点の画像である視点画像間の相関を示す指標値を算出する指標値算出ステップと、
前記指標値に基づいて、前記映像全体として前記映像の変化を滑らかにする前記視点画像の順番を求め、求めた前記順番で前記視点画像を並べて前記映像形式のフレームとし、符号化対象の映像情報を生成する映像生成ステップと、
を有する符号化方法。
【請求項５】
請求項１から３のいずれか一項に記載の符号化装置としてコンピュータを実行させるための符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置、符号化方法、及び符号化プログラムに関する。
【背景技術】
【０００２】
ライトフィールドイメージは、同一の被写体を異なる視点から撮影した複数の視点画像を含む情報である。ライトフィールドイメージは、例えば、行列状に並べた複数のマイクロレンズを用いて撮影することにより得られる画像である。図２０に示す多視点画像情報３００は、ライトフィールドイメージを視点ごとに分解することにより得られる画像情報である。
【０００３】
多視点画像情報３００は、複数の視点画像３００−０，３００−１，…，３００−ｍ，…（ここで、ｍは１以上の整数である）を含んでいる。以下、多視点画像情報３００に含まれるいずれか１つの視点画像を示す場合、視点画像３００−ｍという。複数の視点画像３００−０，３００−１，…の各々は、例えば、Ｖｅｓｐａという同一の被写体を撮影した画像である。複数の視点画像３００−０，３００−１，３００−２，…は、行列状に並べた複数のマイクロレンズの各々によって撮影されているため、各々が少しずつ異なる画像になっている。
【０００４】
この多視点画像情報３００を、ＨＥＶＣ（High Efficiency Vide Coding）のような映像符号化方式によって符号化して容量を圧縮する技術が提案されている。例えば、図２０に示すように多視点画像情報３００に含まれる視点画像３００−０，３００−１，…の各々を映像情報のフレームのように並べて映像形式情報３１０に変換する。ＨＥＶＣ符号化器４０１が、映像形式情報３１０に対して符号化の処理を行い、ビットストリーム３２０を生成する。
【０００５】
復元を行う場合、ＨＥＶＣ復号化器４０２がビットストリーム３２０に対して復号化の処理を行い、復元映像形式情報３３０を復元する。復元した復元映像形式情報３３０のフレームを元の配置に戻すように平面状に並べることで復元多視点画像情報３４０が得られる。
【０００６】
多視点画像情報３００に含まれる視点画像３００−０，３００−１，…の各々を映像情報のフレームのように並べる手法として、例えば、図２１に示すＲａｓｔｅｒという手法がある。なお、図２１において、多視点画像情報３００において、横方向が水平方向の視点の移動を示しており、縦方向が垂直方向の視点の移動を示している。
【０００７】
Ｒａｓｔｅｒの場合、多視点画像情報３００の最も上の左端から右方向に視点画像３００−ｍを選択し、右端に到達すると、１段下の左端から右方向に視点画像３００−ｍを選択することを繰り返す。これにより、系列に並べられた複数の視点画像３００−０，３００−１，３００−２，…が得られることになり、この系列を時系列とみなすことにより映像形式情報３１０が得られることになる。
【０００８】
Ｒａｓｔｅｒ以外にも、例えば、図２２（ａ）に示すＺｉｇｚａｇ、図２２（ｂ）に示すＣｉｒｃｕｌａｒ、図２２（ｃ）に示すＵ−Ｓｈａｐｅなどの手法がある。なお、図２１、及び図２２において、フレーム番号が小さい箇所の色を濃くし、フレーム番号が大きくなるにつれて色を薄くしている。
【０００９】
このように多視点画像情報３００からＲａｓｔｅｒ等の一定のルールにしたがって視点画像３００−ｍを読み出す手法ではなく、適応的に視点画像３００−ｍを読み出す手法が、非特許文献１に開示されている。
【００１０】
非特許文献１では、ＨＥＶＣにおいて符号化されるフレームの順番を考慮したＬＦ−ＣＡＥ(Light Fields Content-Adaptive Encoding)と呼ばれる手法が提案されている。ここで、ＨＥＶＣにおいて符号化されるフレームの順番とは、ＨＥＶＣのインター予測符号化における参照構造にしたがって定められるフレームの参照順のことである。
【００１１】
図２３は、ＨＥＶＣにおけるＬｏｗ＿Ｄｅｌａｙ＿Ｂの場合の参照構造を示す図である。図２３において、ｆ０，ｆ１，ｆ２，…は、フレーム番号を示している。また、フレーム内のＩは、Ｉ（Intra）ピクチャを示しており、Ｂは、Ｂ（Bidirectionally Predictive）ピクチャを示している。Ｌｏｗ＿Ｄｅｌａｙ＿Ｂの場合、最初のＩピクチャのフレームｆ０以外のフレームｆ１，ｆ２，…は、インター予測符号化の際に過去のフレームのみを参照する。
【００１２】
フレームｆ１，ｆ２，…の各々の参照先は、矢印によって示す通りであり、例えば、フレームｆ１については、Ｉピクチャであるフレームｆ０が参照先となる。フレームｆ２については、Ｉピクチャであるフレームｆ０と、フレームｆ１が参照先となる。フレームｆ３については、図２３においてハッチングで示すように、Ｉピクチャであるフレームｆ０と、フレームｆ２が参照先となる。
【００１３】
これに対して、図２４は、ＨＥＶＣにおけるＲａｎｄｏｍ＿Ａｃｃｅｓｓの場合の参照構造を示す図である。Ｒａｎｄｏｍ＿Ａｃｃｅｓｓの場合、インター予測符号化の際に過去と未来のフレームを参照する。例えば、フレームｆ３の場合、矢印にしたがってフレームｆ２，ｆ４が参照先となる。更に、フレームｆ２，ｆ４の参照先であるフレームｆ０，ｆ８もフレームｆ３に関連する参照先となる。また、更に、フレームｆ８の参照先であるフレームｆ１６もフレームｆ３に関連する参照先となる。
【００１４】
また、フレームｆ１０については、図２４においてハッチングで示すように、フレームｆ８，ｆ１２が参照先となる。更に、フレームｆ８，ｆ１２の参照先であるフレームｆ０，ｆ１６もフレームｆ１０に関連する参照先となる。図２４では、一例として、ランダムアクセスの単位であるＧＯＰ(Group Of Pictures)に含まれるフレームが１７個の場合を示している。ＧＯＰに含まれるフレームの数は、１７個以外であってもよく、例えば、３３個などの数にすることもできる。
【００１５】
ＬＦ−ＣＡＥでは、上記のいずれかの参照構造にしたがって視点画像３００−ｍを並べる順番を決めていく際、参照する２つのフレーム間の差を示す指標値として、ＳＡＤ（Sum Of Absolute Differences）という値を定義している。ＳＡＤは、２つのフレームをＩ、Ｔとした場合、次式（１）によって定義される指標値である。
【００１６】
【数１】
2020167479.tif 000003
【００１７】
上記の式（１）に示されるようにＳＡＤとは、２つのフレームＩ，Ｔに含まれるピクセルごとの誤差の絶対値の和である。そのため、フレームＩと、フレームＴの画像が類似しているほど小さい値になり、フレームＩと、フレームＴの画像が同一の場合「０」となる。例えば、図２５に示すように、ｎ番目のフレームｆｎまで順番が確定しているとする。また、対象とする参照構造がＬｏｗ＿Ｄｅｌａｙ＿Ｂであり、ｎ＋１番目のフレームｆｎ＋１の参照先が、フレームｆｎとフレームｆｎ−２であるとする。
【００１８】
ＬＦ−ＣＡＥでは、順番が確定してない視点画像群の中から任意に１つの視点画像３００−ｍを選択し、選択した視点画像３００−ｍと一方の参照先であるフレームｆｎのＳＡＤを算出する。また、選択した視点画像３００−ｍと他方の参照先であるフレームｆｎ−２のＳＡＤを算出する。算出した２個のＳＡＤの合計値を算出し、算出したＳＡＤの合計値を最小にする視点画像３００−ｍをｎ＋１番目のフレームｆｎ＋１として確定する。これを一般化すると、次式（２）となる。
【００１９】
【数２】
2020167479.tif 000004
【００２０】
上記の式（２）においてＬは、順番が確定していない視点画像群を示しており、Ｒは、参照先のフレーム群を示している。ＬＦ−ＣＡＥでは、全ての視点画像３００−ｍの順番が確定するまで、式（２）による順番の確定を繰り返す。これにより、Ｌｏｗ＿Ｄｅｌａｙ＿Ｂの参照構造を考慮した順番で並んだ視点画像３００−０，３００−１，…を得ることができる。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】Ruhan Conceicao, Marcelo Porto, Bruno Zatt, Luciano Agostini,” LF-CAE: CONTEXT-ADAPTIVE ENCODING FOR LENSLET LIGHT FIELDS USING HEVC”, IEEE, ICIP 2018, pp3174-3178.
【発明の概要】
【発明が解決しようとする課題】
【００２２】
しかしながら、上記の非特許文献１に記載のＬＦ−ＣＡＥでは、参照構造によって定められる参照先のフレームと、参照元のフレームとのＳＡＤの合計値に基づいて、フレームの順番を求めている。そのため、局所的には符号化に最適なフレームの順番になっているが、全体として符号化に最適なフレームの順番になっていない場合もある。
【００２３】
また、ＬＦ−ＣＡＥでは、図２５に示したｎ＋１番目のフレームｆｎ＋１としていずれかの視点画像３００−ｍを選択すると、その選択が最適であるか否かを再考することも行っていない。したがって、ＬＦ−ＣＡＥによって並べた場合の符号化効率は、多視点画像情報３００において、最適な並びにすることによって得られる符号化効率から大きく乖離する可能性があるという問題がある。
【００２４】
上記事情に鑑み、本発明は、最適なフレームの順番を求めることができる技術の提供を目的としている。
【課題を解決するための手段】
【００２５】
本発明の一態様は、多視点画像情報を映像形式に変換し映像符号化方式によって符号化する符号化装置であって、前記多視点画像情報を構成する各視点の画像である視点画像間の相関を示す指標値を算出する指標値算出部と、前記指標値に基づいて、前記映像全体として前記映像の変化を滑らかにする前記視点画像の順番を求め、求めた前記順番で前記視点画像を並べて前記映像形式のフレームとし、符号化対象の映像情報を生成する映像生成部と、を備える符号化装置である。
【００２６】
本発明の一態様は、上記の符号化装置であって、前記指標値は、前記視点画像が類似しているほど小さい値となり、前記映像生成部は、全ての隣接する前記視点画像間に対して前記指標値算出部が算出する前記指標値の合計値を最小、または、略最小にする前記順番を求める。
【００２７】
本発明の一態様は、上記の符号化装置であって、前記映像生成部は、前記映像符号化方式における参照構造を参照することなく、前記順番を求める。
【００２８】
本発明の一態様は、多視点画像情報を映像形式に変換し映像符号化方式によって符号化する符号化方法であって、前記多視点画像情報を構成する各視点の画像である視点画像間の相関を示す指標値を算出する指標値算出ステップと、前記指標値に基づいて、前記映像全体として前記映像の変化を滑らかにする前記視点画像の順番を求め、求めた前記順番で前記視点画像を並べて前記映像形式のフレームとし、符号化対象の映像情報を生成する映像生成ステップと、を有する符号化方法である。
【００２９】
本発明の一態様は、上記の符号化装置としてコンピュータを実行させるための符号化プログラムである。
【発明の効果】
【００３０】
本発明により、最適なフレームの順番を求めることができる。
【図面の簡単な説明】
【００３１】
【図１】本発明の一実施形態における符号化装置の構成を示すブロック図である。
【図２】実施形態におけるＳＡＤの合計であるＬｅｎｇｔｈを示す図である。
【図３】実施形態の符号化装置による処理の流れを示すフローチャートである。
【図４】実施形態の順番算出処理（貪欲法）のフローチャートである。
【図５】実施形態において貪欲法による視点画像の順番を求める処理を示す図である。
【図６】巡回セールスマン問題における２−ｏｐｔ法を示す図である。
【図７】実施形態の順番算出処理（２−ｏｐｔ法）のフローチャートである。
【図８】実施形態において２−ｏｐｔ法による視点画像の順番を求める処理を示す図（その１）である。
【図９】実施形態において２−ｏｐｔ法による視点画像の順番を求める処理を示す図（その２）である。
【図１０】実施形態において２−ｏｐｔ法による視点画像の順番を求める処理を示す図（その３）である。
【図１１】実施形態において２−ｏｐｔ法による視点画像の順番を求める処理を示す図（その４）である。
【図１２】実施形態において２−ｏｐｔ法による視点画像の順番を求める処理を示す図（その５）である。
【図１３】Ｖｅｓｐａの視点画像に対してＬＦ−ＣＡＥ（Ｌｏｗ＿Ｄｅｌａｙ＿Ｂ）と本実施形態「手法１」及び「手法２」を適用した場合に求められた視点画像の順番を示す図である。
【図１４】Ｍａｇｎｅｔｓの視点画像に対してＬＦ−ＣＡＥ（Ｌｏｗ＿Ｄｅｌａｙ＿Ｂ）と本実施形態「手法１」及び「手法２」を適用した場合に求められた視点画像の順番を示す図である。
【図１５】Ｍａｇｎｅｔｓの画像の一例である。
【図１６】視点画像を並べる手法の種類ごとの各多視点画像情報におけるＬｅｎｇｔｈの値を示す図である。
【図１７】視点画像を並べる手法の種類ごとの各多視点画像情報におけるＢＤ−ｒａｔｅ（Ｌｏｗ  Ｄｅｌａｙ  Ｂ）の値を示す図である。
【図１８】視点画像を並べる手法の種類ごとの各多視点画像情報におけるＢＤ−ｒａｔｅ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ）の値を示す図である。
【図１９】視点画像を並べる手法の種類ごとの各多視点画像情報におけるＢＤ−ｒａｔｅ（Ｌｏｗ  Ｄｅｌａｙ  Ｂ及びＲａｎｄｏｍ  Ａｃｃｅｓｓ）の値を示す図である。
【図２０】多視点画像情報をＨＥＶＣによって符号化及び復号化する構成を示す図である。
【図２１】Ｒａｓｔｅｒの手法に基づく視点画像の並べ方を示す図である。
【図２２】Ｚｉｇｚａｇ、Ｃｉｒｃｕｌａｒ、Ｕ−Ｓｈｐａｅの手法の場合の視点画像の順番を示す図である。
【図２３】Ｌｏｗ＿Ｄｅｌａｙ＿Ｂの参照構造を示す図である。
【図２４】Ｒａｎｄｏｍ＿Ａｃｃｅｓｓの参照構造を示す図である。
【図２５】ＬＦ−ＣＡＥの手法に基づく視点画像の並べ方を示す図である。
【発明を実施するための形態】
【００３２】
以下、本発明の実施形態について図面を参照して説明する。
図１は、本発明における符号化装置１の構成を示すブロック図である。符号化装置１は、指標値算出部１１、映像生成部１２、及び符号化処理部１３を備える。
【００３３】
符号化装置１が符号化の対象とする多視点画像情報１００は、Ｎ個の視点画像１００−０，１００−１，…，１００−ｐ，…，１００−（Ｎ−１）を含んでいる。ここで、ｐは、０〜Ｎ−１の整数であり、Ｎは、少なくとも２以上の整数である。以下、多視点画像情報１００に含まれるいずれか１つの視点画像を示す場合、視点画像１００−ｐという。
【００３４】
指標値算出部１１は、２つの視点画像１００−ｐの間のＳＡＤを算出する。映像生成部１２は、視点画像１００−０〜１００−（Ｎ−１）の順番を求め、求めた順番にしたがって各フレームに連続するフレーム番号を付与して映像情報を生成する。映像生成部１２は、順番算出部１２−１とフレーム番号付与部１２−２を備える。
【００３５】
順番算出部１２−１は、図２に示すように、隣接する２つの視点画像１００−ｐの間のＳＡＤの合計値であるＬｅｎｇｔｈを最小にするＮ個の視点画像１００−０〜１００−（Ｎ−１）の順番を求める。順番算出部１２−１は、例えば、巡回セールスマン問題を解くことにより、Ｌｅｎｇｔｈを最小にするＮ個の視点画像１００−０〜１００−（Ｎ−１）の順番を求める。
【００３６】
ここで、巡回セールスマン問題とは、複数の都市を１回だけ通過する場合の最短経路を求める組み合わせ最適問題である。順番算出部１２−１は、多視点画像情報１００に含まれる視点画像１００−０〜１００−（Ｎ−１）の各々を巡回セールスマン問題の都市とみなし、ＳＡＤを都市間の距離とみなして巡回セールスマン問題を解く演算を行う。
【００３７】
Ｌｅｎｇｔｈが最小であるということは、視点画像１００−０〜１００−（Ｎ−１）の各々を映像のフレームとして捉えた場合、映像全体として映像の変化が滑らか、または、緩やかになっていることを示している。ＨＥＶＣのインター予測符号化方式では、映像の変化が滑らか、または、緩やかである方が、符号化効率が良くなることが知られている。
【００３８】
本実施形態では、順番算出部１２−１は、２通りの手法によって巡回セールスマン問題を解く演算を行う。「手法１」は、貪欲法を適用する手法である。「手法２」は、貪欲法によって求めた順番で並べた視点画像１００−０〜１００−（Ｎ−１）に対して更に２−ｏｐｔを適用する手法である。
【００３９】
フレーム番号付与部１２−２は、順番算出部１２−１が求めた順番にしたがって、各フレームに連続するフレーム番号ｆ０，ｆ１，ｆ２，…，ｆＮ−１を付与する。符号化処理部１３は、映像生成部１２が生成した映像情報に含まれるフレームをフレーム番号の順にしたがってＨＥＶＣのインター予測符号化によって符号化の処理を行い、符号化によって得られるビットストリームの情報を出力する。なお、上記のＬｅｎｇｔｈを、フレーム番号を用いて数式で示すと次式（３）となる。
【００４０】
【数３】
2020167479.tif 000005
【００４１】
（符号化装置による処理）
図３は、符号化装置１による処理の流れを示すフローチャートである。映像生成部１２の順番算出部１２−１は、多視点画像情報１００を取り込み、取り込んだ多視点画像情報１００に含まれるＮ個の視点画像１００−０〜１００−（Ｎ−１）を読み出す（ステップＳａ１）。
【００４２】
順番算出部１２−１は、順番算出処理のサブルーチンの処理、すなわち上記した「手法１」または「手法２」によって巡回セールスマン問題を解く演算を行い、Ｌｅｎｇｔｈを最小にする視点画像１００−ｐの順番を求める（ステップＳａ２）。符号化処理部１３は、フレーム番号付与部１２−２が付与したフレーム番号の順番にしたがって視点画像１００−ｐに対してＨＥＶＣのインター予測符号化の処理を行い、符号化によって得られるビットストリームの情報を出力する（ステップＳａ３）。
【００４３】
以下、ステップＳａ２において、順番算出部１２−１が行う順番算出処理の「手法１」または「手法２」のそれぞれの処理の流れについて説明する。
【００４４】
（手法１：貪欲法による巡回セースルマン問題を解く手法）
図４は、貪欲法による順番算出処理の流れを示すフローチャートである。順番算出部１２−１は、例えば、多視点画像情報１００の中心の視点画像１００−０を最初のフレームとする（なお、視点画像の符号の枝番号と、視点画像の順番とは、関連するものではないが、ここでは、説明の便宜上、中心の視点画像の符号を１００−０とする）。フレーム番号付与部１２−２は、最初のフレームとなる視点画像１００−０にフレーム番号「ｆ０」を付与する（ステップＳｂ１）。順番算出部１２−１は、順番の確定していない視点画像１００−ｐが存在するか否かを判定する（ステップＳｂ２）。
【００４５】
ここでは、最初のフレームとした視点画像１００−０以外の視点画像１００−１〜１００−（Ｎ−１）が順番の確定していない視点画像１００−ｐとして存在するため、順番算出部１２−１は、順番の確定していない視点画像１００−ｐが存在すると判定する（ステップＳｂ１、Ｙｅｓ）。
【００４６】
順番算出部１２−１は、順番の確定した最後のフレームである視点画像１００−０と、順番の確定していない視点画像１００−１〜１００−（Ｎ−１）の各々との組み合わせを指標値算出部１１に出力する。
【００４７】
指標値算出部１１は、順番算出部１２−１から視点画像１００−０と、視点画像１００−１〜１００−（Ｎ−１）の各々との組み合わせを受けると、例えば、最初に、視点画像１００−０と、視点画像１００−１との間のＳＡＤを算出する。指標値算出部１１は、同様に、視点画像１００−０と、視点画像１００−２〜１００−（Ｎ−１）の各々との間のＳＡＤを算出する。指標値算出部１１は、算出した全てのＳＡＤを順番算出部１２−１に出力する。順番算出部１２−１は、図５に示すように、指標値算出部１１から受けたＳＡＤの中で最小のＳＡＤとなる視点画像１００−ｐを、次のフレームとする（ステップＳｂ３）。
【００４８】
フレーム番号付与部１２−２は、順番算出部１２−１が次のフレームとした視点画像１００−ｐに対して、「ｆ０」の次のフレーム番号「ｆ１」を付与する（ステップＳｂ４）。なお、ステップＳｂ３，Ｓｂ４の処理を数式で示すと次式（４）となる。
【００４９】
【数４】
2020167479.tif 000006
【００５０】
なお、上記の式（４）において、Ｌは、順番の確定していない視点画像群である。
【００５１】
順番算出部１２−１は、ステップＳｂ３において次のフレームとした視点画像１００−ｐを順番の確定した最後のフレームとしてステップＳｂ２からの処理を行う。
【００５２】
順番算出部１２−１が、ステップＳｂ２において、順番の確定していない視点画像１００−ｐが存在しないと判定した場合（ステップＳｂ２）、順番算出処理のサブルーチンを終了し、図３のステップＳａ３の処理が行われる。
【００５３】
図４に示した貪欲法による順序算出処理により、１つ前の視点画像１００−ｐとのＳＡＤが最小となる視点画像１００−０〜１００−（Ｎ−１）の順番が求められることになる。
【００５４】
（手法２：２−ｏｐｔ法による巡回セースルマン問題を解く手法）
次に、図６から図１２を参照しつつ２−ｏｐｔ法による順番算出処理について説明する。最初に巡回セールスマン問題における２−ｏｐｔ法について説明する。例えば、図６（ａ）に示すように、５つの都市３０，３１，３２，３３，３４が、４つの経路４０，４１，４２，４３で接続されているとする。２−ｏｐｔ法とは、経路４０，４１，４２，４３の中から任意に２つの経路を選択し、選択した経路を交換した場合、距離が短くなれば、選択した経路を選択するという手法である。例えば、図６（ｂ）に示すように、都市３０，３１の間の経路４０を都市３０，３３の間の経路４５と交換し、都市３３，３４の間の経路４３を都市３１，３４の間の経路４４と交換する。交換した経路４４と経路４５の合計距離が、交換前の経路４０と経路４３の合計距離よりも短ければ、経路４４，４５を選択する。
【００５５】
図７は、２−ｏｐｔ法による順番算出処理の流れを示すフローチャートである。順番算出部１２−１は、貪欲法による順番算出処理、すなわち、図４に示したステップＳｂ１〜Ｓｂ４の処理を全ての視点画像１００−０〜１００−（Ｎ−１）に対して行う（ステップＳｃ１）。
【００５６】
順番算出部１２−１は、貪欲法によって定めた順番において隣接する２つの視点画像１００−ｐの全ての組み合わせを指標値算出部１１に出力する。指標値算出部１１は、順番算出部１２−１から受けた隣接する２つの視点画像１００−ｐごとのＳＡＤを算出し、算出した全てのＳＡＤを順番算出部１２−１に出力する。順番算出部１２−１は、指標値算出部１１が出力する全てのＳＡＤを合計してＬｅｎｇｔｈを算出し、算出したＬｅｎｇｔｈを変数Ｌに代入する（ステップＳｃ２）。
【００５７】
ステップＳｃ１において順番算出部１２−１は、求めた順番にしたがって視点画像１００−ｐの各々に対してフレーム番号ｆ０，ｆ１，…，ｆＮ−１を付与している。順番算出部１２−１は、フレーム番号ｆ０，ｆ１，…，ｆＮ−１のｆの添え字を「ｉ」とし、ｉ＝１〜Ｎ−２について、ステップＳｃ３〜Ｓｃ９の処理を繰り返し行う（ループＬｃ１ｓ〜Ｌｃ１ｅ）。
【００５８】
順番算出部１２−１は、フレーム番号ｆ０，ｆ１，…，ｆＮ−１のｆの添え字を「ｋ」とし、ｋ＝ｉ＋１〜Ｎ−１について、ステップＳｃ３〜Ｓｃ９の処理を繰り返し行う（ループＬｃ２ｓ〜Ｌｃ２ｅ）。
【００５９】
以下、ステップＳｃ３〜Ｓｃ９の処理について、図８から図１２に示す具体例を参照しつつ説明する。一例として、視点画像の数であるＮが「５」であるとする。また、分かりやすさのため、ステップＳｃ１の処理において、順番算出部１２−１が求めた順番が、視点画像１００−０，１００−１、１００−２，１００−３，１００−４の順であるとする。したがって、視点画像１００−０，１００−１、１００−２，１００−３，１００−４の各々には、フレーム番号ｆ０，ｆ１，ｆ２，ｆ３，ｆ４が付与されている。
【００６０】
順番算出部１２−１は、配列φに対してフレーム番号ｆ０，ｆ１，…ｆｉ−１の各々に対応する視点画像１００−ｐを格納する（ステップＳｃ３）。ｉ＝１である場合、順番算出部１２−１は、配列φに対してフレーム番号ｆ０に対応する視点画像１００−０を格納する。
【００６１】
順番算出部１２−１は、配列φに対してフレーム番号ｆｋ，ｆｋ−１，…ｆｉの各々に対応する視点画像１００−ｐを格納する（ステップＳｃ４）。ｉ＝１、ｋ＝２である場合、順番算出部１２−１は、配列φに対してフレーム番号ｆ２，ｆ１に対応する視点画像１００−２，１００−１を格納する。
【００６２】
順番算出部１２−１は、配列φに対してフレーム番号ｆｋ＋１，ｆｋ＋２，…ｆＮ−１の各々に対応する視点画像１００−ｐを格納する（ステップＳｃ５）。ｉ＝１、ｋ＝２である場合、順番算出部１２−１は、配列φに対してフレーム番号ｆ３，ｆ４に対応する視点画像１００−３，１００−４を格納する。
【００６３】
この時点で、配列φには、図９に示すように、先頭から視点画像１００−０，１００−２，１００−１，１００−３，１００−４が格納されている。すなわち、視点画像１００−０と視点画像１００−１の間の経路が、視点画像１００−０と視点画像１００−２の間の経路に交換され、視点画像１００−２と視点画像１００−３の間の経路が、視点画像１００−１と視点画像１００−３の間の経路に交換されていることになる。
【００６４】
順番算出部１２−１は、配列φに格納されている順番において隣接する２つの視点画像１００−ｐの全ての組み合わせを指標値算出部１１に出力する。指標値算出部１１は、順番算出部１２−１から受けた隣接する２つの視点画像１００−ｐごとのＳＡＤを算出し、算出した全てのＳＡＤを順番算出部１２−１に出力する。順番算出部１２−１は、指標値算出部１１が出力する全てのＳＡＤを合計してＬｅｎｇｔｈを算出する（ステップＳｃ６）。
【００６５】
順番算出部１２−１は、算出したＬｅｎｇｔｈが、その時点での変数Ｌの値未満であるか否かを判定する（ステップＳｃ７）。順番算出部１２−１は、算出したＬｅｎｇｔｈが、変数Ｌの値未満でないと判定した場合（ステップＳｃ７、Ｎｏ）、ｋに「１」を加えて、ループ処理Ｌｃ２ｓ〜Ｌｃ２ｅの次の処理を行う。
【００６６】
順番算出部１２−１は、算出したＬｅｎｇｔｈが、変数Ｌの値未満であると判定した場合（ステップＳｃ７、Ｙｅｓ）、変数Ｌに算出したＬｅｎｇｔｈを代入する（ステップＳｃ８）。順番算出部１２−１は、配列φを配列Ｆに記憶させ（ステップＳｃ９）、ｋに「１」を加えて、ループ処理Ｌｃ２ｓ〜Ｌｃ２ｅの次の処理を行う。
【００６７】
次のステップＳｃ３〜Ｓｃ５では、ｉ＝１、ｋ＝３であるため、順番算出部１２−１は、図１０に示すように、配列φの先頭から視点画像１００−０，１００−３，１００−２，１００−１，１００−４を格納する。また、その次のステップＳｃ３〜Ｓｃ５では、ｉ＝１、ｋ＝４であるため、順番算出部１２−１は、図１１に示すように、配列φの先頭から視点画像１００−０，１００−４，１００−３，１００−２，１００−１を格納する。
【００６８】
次のステップＳｃ３〜Ｓｃ５では、ｉの値が１増えて、ｉ＝２、ｋ＝３となるため、順番算出部１２−１は、図１２に示すように、配列φの先頭から視点画像１００−０，１００−１，１００−３，１００−２，１００−４を格納する。
【００６９】
このようにして、全てのｉについての処理が終了すると、配列Ｆには、Ｌｅｎｇｔｈが最小値であった場合の順番でＮ個の視点画像１００−０，１００−１，…が格納されていることになる。フレーム番号付与部１２−２は、配列Ｆに格納されているＮ個の視点画像１００−０，１００−１，…に対して先頭から順に連続するフレーム番号ｆ０，ｆ１，…を付与する（ステップＳｃ１０）。
【００７０】
上記の実施形態の構成により、符号化装置１において指標値算出部１１は、多視点画像情報１００を構成する各視点の画像である視点画像１００−ｐ間の相関を示す指標値であるＳＡＤを算出する。映像生成部１２は、ＳＡＤに基づいて、映像全体として映像の変化を滑らかにする視点画像１００−ｐの順番を求め、求めた順番で視点画像１００−ｐを並べて映像形式のフレームとし、符号化対象の映像情報を生成する。符号化処理部１３は、ＨＥＶＣによって映像情報を符号化する。より詳細には、映像生成部１２は、視点画像１００−ｐを並べた際の全ての隣接する視点画像１００−ｐ間のＳＡＤの合計が最小になる順番を、映像全体として映像の変化を滑らかにする順番として求めている。さらに、また、映像生成部１２は、視点画像１００−ｐを並べた際の全ての隣接する視点画像１００−ｐ間のＳＡＤの合計が最小になる順番を求める際、視点画像１００−ｐの各々を都市とみなし、ＳＡＤを都市間の距離とみなして巡回セールスマン問題を解くことにより順番を求めている。
【００７１】
上述したようにＨＥＶＣのインター予測符号化方式では、映像の変化が滑らか、または、緩やかである方が、符号化効率が良くなることが知られている。符号化装置１の映像生成部１２は、ＳＡＤに基づいて、映像全体として映像の変化が滑らかになる順番で視点画像１００−ｐを並べている。したがって、符号化装置１は、視点画像を映像のフレームとし、ＨＥＶＣによって符号化する際、より良い符号化効率が得られるように最適なフレームの順番を求めることを可能としている。また、非特許文献１の技術ではＨＥＶＣの参照構造を参照して視点画像１００−ｐの順番を求めているが、符号化装置１では、参照構造を考慮せずに視点画像１００−ｐの順番を求めることを可能としている。
【００７２】
（実験結果）
上述した符号化装置１による効果を評価するために以下の条件で実験を行った。
【００７３】
（１）多視点画像情報の種類：１４種類の多視点画像情報を評価対象とした。１４種類の多視点画像情報の名称は、「Ｖｅｓｐａ」、「Ｆｌｏｗｅｒｓ」、「Ｄｅｓｋｔｏｐ」、「Ｂｉｋｅｓ」、「Ａｎｋｙ」、「Ｂｏｏｋｓ」、「Ｃｏｌｏｒ」、「Ｄａｎｇｅｒ」、「Ｆｏｕｎｔａｉｎ」、「Ｆｒｉｅｎｄｓ」、「Ｇａｍｅ」、「Ｍａｇｎｅｔｓ」、「Ｐｉｌｌａｒｓ」、「Ｒｅｆｌｅｃｔｉｎｇ」である。１４種類の多視点画像情報に含まれる視点数は、１９３視点であり、視点ごとの画素数は、６４５×４３２である。
【００７４】
（２）ＨＥＶＣのインター予測符号化の条件：参照構造は、「Ｌｏｗ＿Ｄｅｌａｙ＿Ｂ」と「Ｒａｎｄｏｍ＿Ａｃｃｅｓｓ」の２種類である。また、ＱＰ(Quantization Parameter)値は、「２２」，「２７」，「３２」，「３７」の４点である。
【００７５】
（３）視点画像を並べる手法の種類：「Ｒａｓｔｅｒ」、「Ｚｉｇｚａｇ」、「Ｃｉｒｃｕｌｒ」、「Ｕ−Ｓｈａｐｅ」、「ＬＦ−ＣＡＥ」、「本実施形態『手法１』（貪欲法を適用する手法）」、及び「本実施形態『手法２』（貪欲法の後に２−ｏｐｔ法を適用する手法）」の７種類の手法を適用した。なお、（１）に示した多視点画像情報において、Ｒａｓｔｅｒ以外は、視点画像１００−０，１００−１，…の順番を記録した１９３Ｂｙｔｅのデータファイルが関連付けられているものとする。
【００７６】
（４）評価指標：「Ｌｅｎｇｔｈ」と「ＢＤ(Bjontegaard Delta-rate)−ｒａｔｅ」の２つの指標で行った。
【００７７】
図１３（ａ），（ｂ），（ｃ）は、多視点画像情報として、図２０に示した「Ｖｅｓｐａ」を適用した場合に、ＬＦ−ＣＡＥ、本実施形態「手法１」、及び本実施形態「手法２」によって得られた視点画像１００−ｐの順番を示した図である。図１３において、フレーム番号が小さい箇所の色を濃くし、フレーム番号が大きくなるにつれて色を薄くしている。
【００７８】
図１３（ａ），（ｂ），（ｃ）のそれぞれのＬｅｎｇｔｈは、「１１６０５５７９２」、「１１７８４９０８５」、「１１６０５５７９２」であり、ＬＦ−ＣＡＥ及び本実施形態「手法２」のＬｅｎｇｔｈが同一の値になっている。
【００７９】
これに対して、図１４（ａ），（ｂ），（ｃ）は、多視点画像情報として、図１５に示す「Ｍａｇｎｅｔｓ」を適用した場合に、ＬＦ−ＣＡＥ、本実施形態「手法１」、及び本実施形態「手法２」によって得られた視点画像１００−ｐの順番を示した図である。図１４でも、図１３と同様に、フレーム番号が小さい箇所の色を濃くし、フレーム番号が大きくなるにつれて色を薄くしている。
【００８０】
図１４（ａ），（ｂ），（ｃ）のそれぞれのＬｅｎｇｔｈは、「１０４５６４３０９」、「１０６９２２４８５」、「１０４２４９０７６」であり、本実施形態「手法２」のＬｅｎｇｔｈが最小値になっている。
【００８１】
図１６は、評価指標を「Ｌｅｎｔｇｈ」とした場合の比較結果を示す図である。図１６において、横軸は、多視点画像情報の種類を示しており、縦軸は、視点画像を並べる手法の種類を示している。なお、Ｌｅｎｇｔｈの値は、Ｒａｓｔｅｒの場合のＬｅｎｇｔｈの値を基準に正規化を行っている。また、右端の列は、視点画像を並べる手法の種類ごとのＬｅｎｇｔｈの平均値を示している。
【００８２】
また、縦軸のＬＦ−ＣＡＥ（Ｌｏｗ  Ｄｅｌａｙ  Ｂ）は、非特許文献１に開示されている技術においてＨＥＶＣの参照構造をＬｏｗ＿Ｄｅｌａｙ＿Ｂとした場合を示しており、ＬＦ−ＣＡＥ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ）は、非特許文献１に開示されている技術においてＨＥＶＣの参照構造をＲａｎｄｏｍ＿Ａｃｃｅｓｓとした場合を示している。
【００８３】
横軸の右端の「平均」の列における視点画像を並べる手法の種類ごとの平均値の値を参照すると、本実施形態「手法２」が、最小値の「８４．６」になっていることがわかる。また、本実施形態「手法１」の値「８７．０」は、ＬＦ−ＣＡＥ（Ｌｏｗ  Ｄｅｌａｙ  Ｂ）の「８５．７」よりは大きい値になっているが、それ以外の視点画像を並べる手法の種類よりは小さい値になっていることがわかる。
【００８４】
図１７、図１８、図１９は、評価指標を「ＢＤ−ｒａｔｅ」とした場合の比較結果を示す図である。ＢＤ−ｒａｔｅは、同一のＰＳＮＲ（Peak Signal to Noise Ratio）とした場合の符号量の削減率を示す値である。図１７は、ＨＥＶＣの参照構造をＬｏｗ＿Ｄｅｌａｙ＿Ｂとした場合の結果を示しており、ＲａｓｔｅｒのＢＤ−ｒａｔｅを基準に正規化を行っている。
【００８５】
図１７の右端の列の平均値を参照すると、ＬＦ−ＣＡＥ（Ｌｏｗ  Ｄｅｌａｙ  Ｂ）のＢＤ−ｒａｔｅが「−１．５３」になっており、最大の符号量削減率を示しているが、本実施形態「手法２」のＢＤ−ｒａｔｅも「−１．４１」であり、ＬＦ−ＣＡＥ（Ｌｏｗ  Ｄｅｌａｙ  Ｂ）の次に高い符号量の削減率を示していることがわかる。
【００８６】
図１８は、ＨＥＶＣの参照構造をＲａｎｄｏｍ＿Ａｃｃｅｓｓとした場合の結果を示しており、ＲａｓｔｅｒのＢＤ−ｒａｔｅを基準に正規化を行っている。
【００８７】
図１８の右端の列の平均値を参照すると、本実施形態「手法２」のＢＤ−ｒａｔｅが「−１３．１９」になっており、最大の符号量削減率を示していることがわかる。また、本実施形態「手法１」のＢＤ−ｒａｔｅが「−１０．４３」になっており、本実施形態「手法２」の次に高い符号量の削減率を示していることがわかる。
【００８８】
図１９は、前半の行にＨＥＶＣの参照構造をＬｏｗ＿Ｄｅｌａｙ＿Ｂとした場合の結果を示し、後半の行にＨＥＶＣの参照構造をＲａｎｄｏｍ＿Ａｃｃｅｓｓとした場合の結果を示し、ＨＥＶＣの参照構造をＬｏｗ＿Ｄｅｌａｙ＿Ｂとした場合のＲａｓｔｅｒのＢＤ−ｒａｔｅを基準に正規化を行っている。
【００８９】
図１９の右端の列の平均値を参照すると、Ｒａｎｄｏｍ＿Ａｃｃｅｓｓの場合の本実施形態「手法２」のＢＤ−ｒａｔｅが「−３３．４１」になっており、最大の符号量削減率を示していることがわかる。また、Ｒａｎｄｏｍ＿Ａｃｃｅｓｓの場合の本実施形態「手法１」のＢＤ−ｒａｔｅが「−３１．３１」になっており、Ｒａｎｄｏｍ＿Ａｃｃｅｓｓの場合の本実施形態「手法２」の次に高い符号量の削減率を示していることがわかる。
【００９０】
また、ＬＦ−ＣＡＥでは、Ｌｏｗ＿Ｄｅｌａｙ＿Ｂの場合のＢＤ−ｒａｔｅが「−１．５３」であるのに対し、Ｒａｎｄｏｍ＿Ａｃｃｅｓｓの場合のＢＤ−ｒａｔｅが「−７．８８」であり、符号量の削減率においてそれほど大きな差が出ていない。これに対して、本実施形態「手順１」では、Ｌｏｗ＿Ｄｅｌａｙ＿Ｂの場合のＢＤ−ｒａｔｅが「３．２５」であるのに対し、Ｒａｎｄｏｍ＿Ａｃｃｅｓｓの場合のＢＤ−ｒａｔｅが「−３３．３１」である。また、本実施形態「手順２」でも、Ｌｏｗ＿Ｄｅｌａｙ＿Ｂの場合のＢＤ−ｒａｔｅが「−１．４１」であるのに対し、Ｒａｎｄｏｍ＿Ａｃｃｅｓｓの場合のＢＤ−ｒａｔｅが「−３３．４１」であり、「手順１」及び「手順２」の両方において、Ｒａｎｄｏｍ＿Ａｃｃｅｓｓの方が高い符号量の削減率になっていることがわかる。
【００９１】
したがって、本実施形態「手法２」は、ＢＤ−ｒａｔｅの評価指標において、ＨＥＶＣの参照構造がＬｏｗ＿Ｄｅｌａｙ＿Ｂの場合、ＬＦ−ＣＡＥよりも若干低い符号量削減率となっているが、それ以外の評価指標においては、最も優れた効果を示しているということがいえる。
【００９２】
なお、上記の実施形態では、映像生成部１２の順番算出部１２−１は、巡回セールスマン問題によって、視点画像１００−ｐの順番を求めるようにしている。巡回セールスマン問題では、都市の数が多くなるとＮＰ(Non-deterministic Polynomial time)困難になり、厳密な最適解を求めることが難しいことが知られている。したがって、図３に示したステップＳａ２の順番算出処理において、Ｌｅｎｇｔｈを最小にする順番を順番算出部１２−１が求めるとしているが、視点画像１００−ｐの数が増えると、Ｌｅｎｇｔｈを最小にする順番を求めることが困難な場合がある。その場合には、順番算出部１２−１は、Ｌｅｎｇｔｈを略最小にする順番を求めることになる。
【００９３】
また、上記の実施形態では、指標値算出部１１は、相関を示す指標値としてＳＡＤを算出しているが、視点画像間の差の合計値や、視点画像間の距離の総和を求めることができるのであれば、どのような指標値を算出するようにしてもよい。
【００９４】
また、上記の実施形態では、巡回セールスマン問題を解く手法として貪欲法と２−Ｏｏｐｔ法を用いているが、他の手法を用いるようにしてもよい。
【００９５】
また、上記の実施形態では、順番算出部１２−１は、巡回セールスマン問題を解くことによって、Ｌｅｎｇｔｈを最小、または略最小にする視点画像１００−ｐの順番を求めているが、巡回セールスマン問題の手法に限られるものではない。Ｌｅｎｇｔｈを最小、または略最小にする視点画像１００−ｐの順番を求められるのであれば、巡回セールスマン問題以外の手法を用いるようにしてもよい。
【００９６】
また、上記の実施形態では、図４に示したステップＳｂ１の処理において、多視点画像情報１００の中心の視点画像１００−ｐを最初のフレームとしているが、中心以外の視点画像１００−ｐを最初のフレームとしてもよい。
【００９７】
また、上記の実施形態では、映像符号化方式としてＨＥＶＣを適用しているが、ＨＥＶＣ以外の映像符号化方式を適用するようにしてもよい。
【００９８】
上述した実施形態における符号化装置１をコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＦＰＧＡ（Field Programmable Gate Array）等のプログラマブルロジックデバイスを用いて実現されるものであってもよい。
【００９９】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【０１００】
１…符号化装置，１１…指標値算出部，１２…映像生成部，１２−１…順番算出部，１２−２…フレーム番号付与部，１３…符号化処理部
【図１】
2020167479.tif 000007
【図２】
2020167479.tif 000008
【図３】
2020167479.tif 000009
【図４】
2020167479.tif 000010
【図５】
2020167479.tif 000011
【図６】
2020167479.tif 000012
【図７】
2020167479.tif 000013
【図８】
2020167479.tif 000014
【図９】
2020167479.tif 000015
【図１０】
2020167479.tif 000016
【図１１】
2020167479.tif 000017
【図１２】
2020167479.tif 000018
【図１３】
2020167479.tif 000019
【図１４】
2020167479.tif 000020
【図１５】
2020167479.tif 000021
【図１６】
2020167479.tif 000022
【図１７】
2020167479.tif 000023
【図１８】
2020167479.tif 000024
【図１９】
2020167479.tif 000025
【図２０】
2020167479.tif 000026
【図２１】
2020167479.tif 000027
【図２２】
2020167479.tif 000028
【図２３】
2020167479.tif 000029
【図２４】
2020167479.tif 000030
【図２５】
2020167479.tif 000031