WO2005122593A1

WO2005122593A1 - 動画符号化方法および動画復号方法

Info

Publication number: WO2005122593A1
Application number: PCT/JP2005/005941
Authority: WO
Inventors: Shinichi Yamashita; Masuharu Endo; Kozo Akiyoshi; Nobuo Akiyoshi
Original assignee: Monolith Co Ltd
Current assignee: Monolith Co Ltd
Priority date: 2004-06-14
Filing date: 2005-03-29
Publication date: 2005-12-22
Anticipated expiration: 2006-12-14
Also published as: EP1765020A1; EP1765020A4; CN1957616A; TW200612756A; JPWO2005122593A1; KR20070026515A; US20070206672A1

Abstract

　ＭＰＥＧで動画を高い圧縮率で符号化するとブロックノイズが顕著になる。第１、第２キーフレーム（Ｆ０、Ｆ４）間でマッチングを計算し、対応点情報（Ｍ０－４）を生成する。この対応点情報をもとに、仮想の第２キーフレーム（Ｆ４’）を生成する。現実の第２キーフレーム（Ｆ４）と仮想の第２キーフレーム（Ｆ４’）との差分を差分符号化器ＤＥで圧縮符号化する。Ｆ０、Ｍ０－４、および、圧縮符号化された差分Δ４をキーフレームＦ０、Ｆ４間の符号化データとして出力する。

Description

明細書

動画符号化方法および動画復号方法

技術分野

[0001] この発明は、画像処理技術に関し、とくにマッチングを用いた動画符号ィ匕技術および動画復号技術に関する。

背景技術

[0002] MPEG (Motion Picture Experts Group)は動画圧縮のひとつの標準技術である。

MPEGでは、ブロックマッチングが利用される。このマッチングは、ブロック間の差分が最小になるようブロック探索を行う。そのため、差分は確かに小さくなる力必ずしもフレーム間で本来対応しあう領域どおしが対応づけられるわけではない。

発明の開示

発明が解決しょうとする課題

[0003] MPEGでは、圧縮率を上げようとすると、いわゆるブロックノイズが問題になる。このノイズの発生を抑え、フレーム間コヒーレンシに注目した圧縮率をさらに上げるためには、現状のブロックマッチングベースの技術を改める必要である。求める技術は、本来対応しあう領域なり画素なりが正しく対応するよう符号ィ匕すべきであり、また、単純なブロックマッチングは避けることが望まし!/、。

本発明の目的は、この課題を解決する動画符号化および復号技術を提供することにある。

課題を解決するための手段

[0004] 本発明は画像マッチング技術を利用する。この技術は本出願人が先に特許第 292

7350号にて提案した技術 (以下「前提技術」という）を利用することができる。本発明の動画符号化方法は、以下の処理を実行する。

[0005] a) 1以上の画像フレームを間に挟む第 1、第 2キーフレーム間でマッチングを計算し、第 1、第 2キーフレーム間の対応点情報を生成するステップと、

b) 第 1、第 2キーフレーム間の対応点情報をもとに第 1キーフレームに含まれる画素を移動させることによって、仮想の第 2キーフレームを生成するステップと、 c) 現実の第 2キーフレームと仮想の第 2キーフレームとの差分を圧縮符号ィ匕するステップと、

d) 第 1キーフレーム、第 1、第 2キーフレーム間の対応点情報、および、現実の第 2キーフレームと仮想の第 2キーフレーム間で圧縮符号ィ匕された差分をこれらのキーフレーム間の符号ィ匕データとして出力するステップ。

[0006] 一方、本発明の動画復号方法は、以下の処理を実行する。

k) 1以上の画像フレームを間に挟む第 1、第 2キーフレーム間の対応点情報、および第 1キーフレームを取得するステップと、

1) 第 1、第 2キーフレーム間の対応点情報をもとに、第 1キーフレームに含まれる画素を移動させることによって、仮想の第 2キーフレームを生成するステップと、 m) 予め符号ィ匕側にて求められた現実の第 2キーフレームと仮想の第 2キーフレームとの差分の圧縮符号化データを取得するステップと、

o) 取得された差分の圧縮符号化データと前記仮想の第 2キーフレームとから、改良された仮想の第 2キーフレームを生成するステップと、

P) 第 1、第 2キーフレーム間の対応点情報をもとに、第 1キーフレームと改良された仮想の第 2キーフレーム間で補間計算をすることにより、これらのキーフレームの間に存在すべき中間フレームを生成するステップと、

q) 第 1キーフレーム、生成された中間フレーム、改良された仮想の第 2キーフレームをこれらのキーフレーム間の復号データとして出力するステップ。

[0007] 本発明の動画符号化方法は、さらに前記 a)のステップにおけるマッチングの正確さを評価するステップを備え、評価の結果に依存して、前記 c)のステップにおける圧縮スキームを切り替えてもよい。評価するステップでは、キーフレーム間のマッチングェネルギー値に着目してマッチングの正確さを評価してもよい。マッチングエネルギーとは、例えば後述する前提技術を利用した画像マッチングにおいて算出される、対応点どうしの距離と画素値の違いに基づく値である。

[0008] 本発明の別の態様は、動画符号化方法である。この方法は、第 1、第 2画像フレーム間で、領域ベースの画像マッチングを計算し、そのマッチング結果を利用して、少なくとも第 3画像フレームを符号ィ匕する方法であって、画像マッチングの結果の良否を領域ごとに判定するステップと、第 3画像フレームの符号ィ匕プロセスにおいて、判定するステップにおいて判定された良否に基づき、領域ごとに量子化スキームを選択するステップとを備える。

[0009] 以上の各ステップを入れ替えたり、方法と装置の間で表現を一部または全部入れ替え、または追加したり、表現をコンピュータプログラム、記録媒体等に変更したものもまた、本発明として有効である。

発明の効果

[0010] 本発明によれば、比較的高!、圧縮率を実現しつつ、動画の画質が高まる。

図面の簡単な説明

[0011] [図 1]図 1 (a)と図 1 (b)は、ふたりの人物の顔に平均化フィルタを施して得られる画像、図 1 (c)と図 1 (d)は、ふたりの人物の顔に関して前提技術で求められるの画像、図 1 (e)と図 1 (f)は、ふたりの人物の顔に関して前提技術で求められる ρ⁽⁵' ^υの画像、図 1 (g)と図 1 (h)は、ふたりの人物の顔に関して前提技術で求められる ρ⁽⁵' の画像、図 1 (i)と図 1 (j)は、ふたりの人物の顔に関して前提技術で求められる ρ⁽⁵' ³⁾の画像をそれぞれディスプレイ上に表示した中間調画像の写真である。

[図 2]図 2 (R)はもとの四辺形を示す図、図 2 (A)、図 2 (B)、図 2 (C)、図 2 (D)、図 2 ( Ε)はそれぞれ相続四辺形を示す図である。

[図 3]始点画像と終点画像の関係、および第 mレベルと第 m— 1レベルの関係を相続四辺形を用いて示す図である。

[図 4]パラメータ 7?とエネルギー Cの関係を示す図である。

[図 5]図 5 (a)、図 5 (b)は、ある点に関する写像が全単射条件を満たすか否力を外積計算から求める様子を示す図である。

[図 6]前提技術の全体手順を示すフローチャートである。

[図 7]図 6の S1の詳細を示すフローチャートである。

[図 8]図 7の S10の詳細を示すフローチャートである。

[図 9]第 mレベルの画像の一部と、第 m— 1レベルの画像の一部の対応関係を示す図である。

[図 10]前提技術で生成された始点階層画像を示す図である。 [図 11]図 6の S2に進む前に、マッチング評価の準備の手順を示す図である。

[図 12]図 6の S2の詳細を示すフローチャートである。

[図 13]第 0レベルにおいて副写像を決定する様子を示す図である。

[図 14]第 1レベルにおいて副写像を決定する様子を示す図である。

[図 15]図 12の S21の詳細を示すフローチャートである。

[図 16]ある f (^m， s)について λを変えながら求められた f (^m，（ λ =i Δ λ )に対応するェネルギー c (^m' ^s)の挙動を示す図である。

f

[図 17] r?を変えながら求められた f(ⁿ) ( r? =1 Δ r? ) (i = 0, 1, · · ·)に対応するエネルギ一 C(ⁿ⁾の挙動を示す図である。

f

[図 18]改良後の前提技術において第 mレベルにおける副写像を求めるフローチヤ一トである。

[図 19]実施の形態に係る動画の符号ィ匕装置および復号装置の構成および処理を示す図である。

[図 20]実施の形態に係る差分符号化器およびノイズリデューサの構成を示す図である。

符号の説明

[0012] Fx 現実の画像フレーム、 CPF 画像マッチングプロセッサ、 DE 差分符号ィ匕器、 NR ノイズリデューサ、 DD 差分復号器、 INT 補間プロセッサ、 Fx，仮想の画像フレーム、 Fx" 改良された仮想の画像フレーム、 Mx—y 対応点情報ファイル

発明を実施するための最良の形態

[0013] はじめに、実施の形態で利用する多重解像度特異点フィルタ技術とそれを用いた画像マッチングを「前提技術」として詳述する。これらの技術は本出願人がすでに特許第 2927350号を得ている技術であり、本発明との組合せに最適である。ただし、実施の形態で採用可能な画像マッチング技術はこれに限られない。図 19以降、前提技術を利用した画像処理技術を具体的に説明する。

[前提技術の実施の形態]

[0014] 最初に [1]で前提技術の要素技術を詳述し、 [2]で処理手順を具体的に説明する。さらに [3]で前提技術に基づき改良を施した点について述べる。

[1]要素技術の詳細

[1. 1]イントロダクション

[0015] 特異点フィルタと呼ばれる新たな多重解像度フィルタを導入し、画像間のマツチングを正確に計算する。オブジェクトに関する予備知識は一切不要である。画像間のマツチングの計算は、解像度の階層を進む間、各解像度において計算される。その際、粗いレベル力も精細なレベルへと順に解像度の階層を迪つていく。計算に必要なパラメータは、人間の視覚システムに似た動的計算によって完全に自動設定される。画像間の対応点を人手で特定する必要はない。

[0016] 本前提技術は、例えば完全に自動的なモーフイング、物体認識、立体写真測量、ボリュームレンダリング、少ないフレーム力の滑らかな動画像の生成などに応用できる。モーフイングに用いる場合、与えられた画像を自動的に変形することができる。ボリュームレンダリングに用いる場合、断面間の中間的な画像を正確に再構築すること力 Sできる。断面間の距離が遠ぐ断面の形状が大きく変化する場合でも同様である。

[1. 2]特異点フィルタの階層

[0017] 前提技術に係る多重解像度特異点フィルタは、画像の解像度を落としながら、しかも画像に含まれる各特異点の輝度及び位置を保存することができる。ここで画像の幅を N、高さを Mとする。以下簡単のため、 N = M = 2ⁿ(nは自然数）と仮定する。また、区間 [0, N] CRを Iと記述する。 (i, j)における画像の画素を p と記述する（i, j ei)

U， j)

[0018] ここで多重解像度の階層を導入する。階層化された画像群は多重解像度フィルタで生成される。多重解像度フィルタは、もとの画像に対して二次元的な探索を行って特異点を検出し、検出された特異点を抽出してもとの画像よりも解像度の低い別の画像を生成する。ここで第 mレベルにおける各画像のサイズは 2^mX 2^m(0≤m≤n)とする。特異点フィルタは次の 4種類の新たな階層画像を nから下がる方向で再帰的に構築する。

[0019] [数 1] (τη,η) · i · ( (m+1,0) (m+1,0)、 - ( (m+1,0) fm+1,0) \\

P¾ = mi (S f ¾),^ ¾， ;:¾₊₁₎))

(式 1 ) _ _ ゝ

[数 2]

とする。以降これら 4つの画像を副画像 (サブイメージ）と呼ぶ。 min max x+lをそれぞれ α及び j8と記述すると、副画像はそれぞれ以下のように記述できる。

τ-, (m, 0) ( ヽ ( ヽ (m+1, 0)

P = a ） a {y) p

P^(m'¹⁾=a(x) ^ (y)p^(m+1'¹⁾

P^(m'²⁾=^ (x) a(y)p^(m+1'²)

P^(m'³⁾=^ (x) ^ (y)p^(m+1'³⁾

[0020] すなわち、これらは aと 13のテンソル積のようなものと考えられる。副画像はそれぞれ特異点に対応している。これらの式から明らかなように、特異点フィルタはもとの画像について 2X2画素で構成されるブロックごとに特異点を検出する。その際、各プロックのふたつの方向、つまり縦と横について、最大画素値または最小画素値をもつ点を探索する。画素値として、前提技術では輝度を採用するが、画像に関するいろいろな数値を採用することができる。ふたつの方向の両方について最大画素値となる画素は極大点、ふたつの方向の両方について最小画素値となる画素は極小点、ふたつの方向の一方について最大画素値となるとともに、他方について最小画素値となる画素は鞍点として検出される。

[0021] 特異点フィルタは、各ブロックの内部で検出された特異点の画像 (ここでは 1画素）でそのブロックの画像 (ここでは 4画素）を代表させることにより、画像の解像度を落とす。特異点の理論的な観点力もすれば、 ex (X) a (y)は極小点を保存し、 β (X) β (y )は極大点を保存し、 a (χ) β (y)及び |8 (χ) a (y)は鞍点を保存する。

[0022] はじめに、マッチングをとるべき始点（ソース）画像と終点（デスティネーション)画像に対して別々に特異点フィルタ処理を施し、それぞれ一連の画像群、すなわち始点階層画像と終点階層画像を生成しておく。始点階層画像と終点階層画像は、特異点の種類に対応してそれぞれ 4種類ずつ生成される。

[0023] この後、一連の解像度レベルの中で始点階層画像と終点階層画像のマッチングがとられていく。まず p^(m' ^ωを用いて極小点のマッチングがとられる。次に、その結果に基づき、 P^(m' "を用いて鞍点のマッチングがとられ、 p^(m' を用いて他の鞍点のマッチングがとられる。そして最後に p^(m' ³⁾を用いて極大点のマッチングがとられる。

[0024] 図 1 (c)と図 1 (d)はそれぞれ図 1 (a)と図 1 (b)の副画像 ρ⁽⁵' ^ωを示している。同様に、図 1 (e)と図 1 (f)は ρ⁽⁵' "、 01 (g)と図 1 (h)は ρ⁽⁵' ²)、図 1 (i)と図 1 (j)は ρ⁽⁵' ³⁾をそれぞれ示している。これらの図からわかるとおり、副画像によれば画像の特徴部分のマッチングが容易になる。まず ρ⁽⁵' ^ωによって目が明確になる。目は顔の中で輝度の極小点だ力である。 ρ⁽⁵' "によれば口が明確になる。口は横方向で輝度が低いためである。 ρ⁽⁵' ²⁾によれば首の両側の縦線が明確になる。最後に、 ρ⁽⁵' ³⁾によって耳ゃ頰の最も明るい点が明確になる。これらは輝度の極大点だ力もである。

[0025] 特異点フィルタによれば画像の特徴が抽出できるため、例えばカメラで撮影された画像の特徴と、予め記録しておいたいくつかのオブジェクトの特徴を比較することにより、カメラに映った被写体を識別することができる。

[1. 3]画像間の写像の計算

[0026] 始点画像の位置 (i, j)の画素を ρ^ω と書き、同じく終点画像の位置 (k, 1)の画素

, ])

を q⁽ⁿ⁾ で記述する。 i, j, k, 1EIとする。画像間の写像のエネルギー（後述）を定義

(k, 1)

する。このエネルギーは、始点画像の画素の輝度と終点画像の対応する画素の輝度の差、及び写像の滑ら力さによって決まる。最初に最小のエネルギーを持つ p^(m' ^G)と q(_m， 0)間の写像 _f °) . _p (_m, o)_→q (_m, «が計算される。 f ⁰⁾に基づき、最小エネルギーを持つ P^(m，、 q^(m' "間の写像 f^(m， "が計算される。この手続は、 p^(m， ^¾と q^(m， ^¾の間の写像 f(^m' ³⁾の計算が終了するまで続く。各写像 ί^(1η' ^ΰ = 0, 1, 2,…；)を副写像と呼ぶことにする。の計算の都合のために、 iの順序は次式のように並べ替えることができる。並べ替えが必要な理由は後述する。

[0027] [数 3]

，び (り〕 (m ( )

P →マ

(式 3 )

ここで σ (i) e {0, 1, 2, 3}である。

[1. 3. 1]全単射

[0028] 始点画像と終点画像の間のマッチングを写像で表現する場合、その写像は両画像間で全単射条件を満たすべきである。両画像に概念上の優劣はなぐ互いの画素が全射かつ単射で接続されるべきだ力もである。し力しながら通常の場合とは異なり、ここで構築すべき写像は全単射のデジタル版である。前提技術では、画素は格子点によって特定される。

[0029] 始点副画像 (始点画像にっ、て設けられた副画像)から終点副画像 (終点画像にっヽて設けられた副画像)への写像は、 f^(m' ^s)： l/2ⁿ"^m X l/2ⁿ"^m→l/2ⁿ"^m X l/2ⁿ "^m(s = 0, 1, · ··)によって表される。ここで、 f^(m' ^s) (i, j) = (k, 1)は、始点画像の p^(m' ^s) が終点画像の q^(m' ^s) に写像されることを意味する。簡単のために、 f (i, j) = (k

(i, j) (k, 1)

, 1)が成り立つとき画素 q を q と記述する。

(k, 1) f(i, j)

[0030] 前提技術で扱う画素 (格子点)のようにデータが離散的な場合、全単射の定義は重要である。ここでは以下のように定義する（i, i' , j, j ' , k, 1は全て整数とする)。まず始めに、始点画像の平面において Rによって表記される各正方形領域、

画

(式 4 )

を考える（i=0, · ··, 2^m— l、j = 0, · ··, 2^m— 1)。ここで Rの各辺（エッジ）の方向を以下のように定める。

[0031] [数 5]

(m,s) (m,3) _{m,3) _{m,_S)

(式 5 ) この正方形は写像 fによって終点画像平面における四辺形に写像されなければならない。 _f(_m.s) _(R)によって示される四辺形、

[0032] [数 6]

は、以下の全単射条件を満たす必要がある。

1.四辺形 ¹"' ^s) (R)のエッジは互いに交差しない。

2. f^(m'^s) (R)のエッジの方向は Rのそれらに等しい（図 2の場合、時計回り）。

3.緩和条件として収縮写像（リトラクシヨン: retractions)を許す。

[0033] 何らかの緩和条件を設けないかぎり、全単射条件を完全に満たす写像は単位写像しかないためである。ここでは f^(m， ^s) (R)のひとつのエッジの長さが 0、すなわち f^(m， ^s) ( R)は三角形になってもよい。しかし、面積が 0となるような図形、すなわち 1点または 1 本の線分になってはならない。図 2 (R)がもとの四辺形の場合、図 2(A)と図 2(D)は全単射条件を満たすが、図 2(B)、図 2(C)、図 2(E)は満たさない。

[0034] 実際のインプリメンテーションでは、写像が全射であることを容易に保証すベぐさらに以下の条件を課してもよい。つまり始点画像の境界上の各画素は、終点画像において同じ位置を占める画素に写影されるというものである。すなわち、 f(i, j) = (i, j) ( ただし i=0, i=2^m-l, j = 0, j = 2^m— 1の 4本の線上）である。この条件を以下「付加条件」とも呼ぶ。

[1.3.2]写像のエネルギー

[1.3.2.1]画素の輝度に関するコスト

[0035] 写像 fのエネルギーを定義する。エネルギーが最小になる写像を探すことが目的である。エネルギーは主に、始点画像の画素の輝度とそれに対応する終点画像の画素の輝度の差で決まる。すなわち、写像 f^(m'^s)の点 (i, j)におけるエネルギー C^(m'^s)

(i， j) は次式によって定まる。

[0036] [数 7]

. ') = 1^¾))ー )1² (式 _{7 )} ここで、 V(p(^m'^s) )及び V(q(^m'^s) )はそれぞれ画素 p(^m'^s) 及び q(^m'^s) の輝度である。 fのトータルのエネルギー c(^m'^s)は、マッチングを評価するひとつの評価式であり、つぎに示す c(^m' ^s) の合計で定義できる。

(i,j)

[数 8]

0 = ∑ ∑ ) ぱ 8 )

i=Q j=0

[1.3.2.2]滑らかな写像のための画素の位置に関するコスト

[0037] 滑らかな写像を得るために、写像に関する別のエネルギー Dfを導入する。このエネルギ一は画素の輝度とは関係なぐ p^(m' ^s) および q^(m' ^s) の位置によって決まる (i

(i, j) f (i, j)

=0, ···, 2^m-l, j = 0, ···, 2^m - 1)。点 (i, j)における写像 f^(m'^s)のエネルギー D^(m'^s) は次式で定義される。

, ])

[0038] [数 9]

"(W)

卞 ("）（式 _{9 )} ただし、係数パラメータ 7?は 0以上の実数であり、また、

[数 10]

/( ( 1² (式 1 o〉

[数 11] ||(/ — ( : )- '，/)— 川²

(式 1 1 ) とする。ここで、

[数 12]

(式丄 _{2 )} であり、 i， < 0および j， < 0に対して f (i，， j，）は 0と決める。 Eは (i, j)及び f (i, j)の距

0

離で決まる。 Eは画素があまりにも離れた画素へ写影されることを防ぐ。ただし Eは、

0 0 後に別のエネルギー関数で置き換える。 Eは写像の滑ら力さを保証する。 Eは、 p

1 1 の変位とその隣接点の変位の間の隔たりを表す。以上の考察をもとに、マッチングを評価する別の評価式であるエネルギー Dは次式で定まる。 [0039] [数 13]

，'一 τη二 i j— 2^m— 1

( ） (式 1 3 )

[1. 3. 2. 3]写像の総エネルギー

[0040] 写像の総エネルギー、すなわち複数の評価式の統合に係る総合評価式は λ C^(m' ^s)

+ D^(m' ^s)で定義される。ここで係数パラメータ λは 0以上の実数である。目的は総合 f f

評価式が極値をとる状態を検出すること、すなわち次式で示す最小エネルギーを与える写像を見、だすことである。

[0041] [数 14] mm λυ) ' + D) (式 1 4 )

[0042] λ =0及び 7? =0の場合、写像は単位写像になることに注意すべきである（すなわち、全ての i=0, · ··, 2^m— 1及び j = 0, · ··, 2^m— 1に対して f^(m' ^s) (i, j) = (i, j)となる）。後述のごとぐ本前提技術では最初に λ =0及び r? =0の場合を評価するため、写像を単位写像力も徐々に変形していくことができる。仮に総合評価式の λの位置を変えて C^(m' ^s) + l D^(m' ^s)と定義したとすれば、 λ =0及び r? =0の場合に総合評価

f f

式が c ^(m' ^s)だけになり、本来何等関連のない画素どうしが単に輝度が近いというだけ

f

で対応づけられ、写像が無意味なものになる。そうした無意味な写像をもとに写像を変形していってもまったく意味をなさない。このため、単位写像が評価の開始時点で最良の写像として選択されるよう係数パラメータの与えかたが配慮されている。

[0043] オプティカルフローもこの前提技術同様、画素の輝度の差と滑ら力さを考慮する。しかし、オプティカルフローは画像の変換に用いることはできない。オブジェクトの局所的な動きしか考慮しな、ためである。前提技術に係る特異点フィルタを用いることによって大域的な対応関係を検出することができる。

[1. 3. 3]多重解像度の導入による写像の決定

[0044] 最小エネルギーを与え、全単射条件を満足する写像 f を多重解像度の階層を用

min

ヽて求める。各解像度レベルにぉヽて始点副画像及び終点副画像間の写像を計算する。解像度の階層の最上位 (最も粗いレベル)からスタートし、各解像度レベルの写像を、他のレベルの写像を考慮に入れながら決定する。各レベルにおける写像の候補の数は、より高い、つまりより粗いレベルの写像を用いることによって制限される。より具体的には、あるレベルにおける写像の決定に際し、それよりひとつ粗いレベルにおいて求められた写像が一種の拘束条件として課される。

まず、

[数 15]

'， j") = ([i]，[i]) (式 ^{1 5})

が成り立つとき、 p(^m_1， s) 、 q^(m_1' をそれぞれ p(^m，、 q^(m' の parent α',Γ) (i'.j') (i,j) (i,j)

と呼ぶことにする。 [x]は χを越えな!/、最大整数である。また p^(m' ^s) 、 q^(m' ^s) をそ

(i, j) (i, j) れぞれ p(^m_1'^s) 、 q^(m_1'^s) の childと呼ぶ。関数 parentG, j)は次式で定義さ

(ί', j') (i'.j')

れる。

[数 16] parent{i,j) = ([-j, [^\) (式 1 6 )

[0045] p^(m' ^s) と q^(m' ^s) の間の写像 f ^(m' ^s)は、エネルギー計算を行って最小になったも

(i, j) (k, 1)

のを見つけることで決定される。 f(^m'^s)(i, j) = (k, 1)の値は f(^m_1'^s)(m=l, 2, ···, n) を用いることによって、以下のように決定される。まず、 q^(m'^s)

(k, 1)は次の四辺形の内部になければならな!/ヽとヽぅ条件を課し、全単射条件を満たす写像のうち現実性の高いものを絞り込む。

[0046] [数 17]

(m,s) tm,s) (m,_S) ( ,_a)

(式 1 7)

_ _ ゝ

[数 18]

g^{m'^s)( ) = f^{m~ ³⁾{parent(i )) + ^'^(paren^ ) + (1,1)))

(式 1 8 ) である。こうして定めた四辺形を、以下 p^(m'^s) ..の相続 (inherited)四辺形と呼ぶことにする。相続四辺形の内部において、エネルギーを最小にする画素を求める。

[0047] 図 3は以上の手順を示している。同図において、始点画像の A, B, C, Dの画素は、第 m— 1レベルにおいてそれぞれ終点画像の Α', Β', C, D，へ写影される。画素 p^(m'^s) は、相続四辺形 A'B'C'D'の内部に存在する画素 q^(m'^s) へ写影され

(i, j) f(m) (i, j)

なければならない。以上の配慮により、第 m— 1レベルの写像から第 mレベルの写像への橋渡しがなされる。

[0048] 先に定義したエネルギー Eは、第 mレベルにおける副写像 f ^(m' °)を計算するため

0

に、次式に置き換える。

[数 19]

Εο_{ί, = \\ ^ ^) -9^ )\\² (式 _{1 9 )}

また、副写像 f ^(m' ^s)を計算するためには次式を用いる。

[数 20]

¾ = ― /( , i)H² ≤り _{2 0} )

[0049] こうしてすべての副写像のエネルギーを低い値に保つ写像が得られる。式 20により、異なる特異点に対応する副写像が、副写像どうしの類似度が高くなるように同一レベル内で関連づけられる。式 19は、 f^(m'^s) (i, j)と、第 m— 1レベルの画素の一部と考えた場合の (i, j)が射影されるべき点の位置との距離を示して、る。

[0050] 仮に、相続四辺形 A'B'C'D'の内部に全単射条件を満たす画素が存在しない場合は以下の措置をとる。まず、 A'B'C'D'の境界線力もの距離が L (始めは L=l)である画素を調べる。それらのうち、エネルギーが最小になるものが全単射条件を満たせば、これを f^(m'^s) (i, j)の値として選択する。そのような点が発見される力、または L がその上限の L^(m)maxに到達するまで、 Lを大きくしていく。 L^(m)maxは各レベル mに対して固定である。そのような点が全く発見されない場合、全単射の第 3の条件を一時的に無視して変換先の四辺形の面積がゼロになるような写像も認め、 f^(m' ^s) (i, j)を決定する。それでも条件を満たす点が見つ力ない場合、つぎに全単射の第 1及び第 2条件を外す。

[0051] 多重解像度を用いる近似法は、写像が画像の細部に影響されることを回避しつつ、画像間の大域的な対応関係を決定するために必須である。多重解像度による近似法を用いなければ、距離の遠い画素間の対応関係を見いだすことは不可能である。その場合、画像のサイズはきわめて小さなものに限定しなければならず、変化の小さな画像しか扱うことができない。さらに、通常写像に滑らかさを要求するため、そうした画素間の対応関係を見つけに《している。距離のある画素から画素への写像のェネルギ一は高いためである。多重解像度を用いた近似法によれば、そうした画素間の適切な対応関係を見いだすことができる。それらの距離は、解像度の階層の上位レベル（粗、レベル）にお!/、て小さ!/、ためである。

[1. 4]最適なパラメータ値の自動決定

[0052] 既存のマッチング技術の主な欠点のひとつに、パラメータ調整の困難さがある。大抵の場合、パラメータの調整は人手作業によって行われ、最適な値を選択することはきわめて難しい。前提技術に係る方法によれば、最適なパラメータ値を完全に自動決定することができる。

[0053] 前提技術に係るシステムはふたつのパラメータ、 λ及び 7?を含む。端的にいえば、 λは画素の輝度の差の重みであり、 7}は写像の剛性を示している。これらのパラメ一タの値は初期値が 0であり、まず =0に固定して λを 0から徐々に増加させる。 λの値を大きくしながら、し力も総合評価式 (式 14)の値を最小にする場合、各副写像に関する c^(m' ^s)の値は一般に小さくなつていく。このことは基本的にふたつの画像がよ

f

りマッチしなければならないことを意味する。しかし、えが最適値を超えると以下の現象が発生する。

1.本来対応すべきではない画素どうしが、単に輝度が近いというだけで誤って対応づけられる。

2.その結果、画素どうしの対応関係がお力しくなり、写像がくずれはじめる。

3.その結果、式 14において D^(m' ^s)が急激に増加しょうとする。

f

4.その結果、式 14の値が急激に増カロしょうとするため、 D^(m' ^s)の急激な増加を抑制

f

するよう f^(m' ^s)が変化し、その結果 C^(m' ^s)が増加する。

f

[0054] したがって、 λを増加させながら式 14が最小値をとるという状態を維持しつつ C^(m' ^s) が減少力も増加に転じる閾値を検出し、そのえを 7? =0における最適値とする。つぎに r?を少しずつ増やして C(^m' ^s)の挙動を検査し、後述の方法で 7?を自動決定する。

f

その 7?に対応して λも決まる。

[0055] この方法は、人間の視覚システムの焦点機構の動作に似ている。人間の視覚システムでは、一方の目を動かしながら左右両目の画像のマッチングがとられる。ォブジェタトがはっきりと認識できるとき、その目が固定される。

[1. 4. 1]えの動的決定

[0056] λは 0から所定の刻み幅で増加されていき、えの値が変わる度に副写像が評価さ

(m, s)

れる。式 14のごとく、総エネルギーはえ C D^(m， ^s)によって定義される。式 9の D

(m, s)

は滑ら力さを表すもので、理論的には単位写像の場合に最小になり、写像が歪むほど Eも Eも増加していく。 Eは整数であるから、 D^(m' ^s)の最小刻み幅は 1である

(m, s)

二のため、現在のの変化 (減少量)が 1以上でなければ、写像を変化さ

(i, j)

せることによって総エネルギーを減らすことはできない。なぜなら、写像の変化に伴つて D^(m' ^s)は 1以上増加するため、 λ C^(m' ^s) 力 Si以上減少しない限り総エネルギー f (i, j)

は減らないためである。

(m, s)

[0057] 二の条件のもと、えの増加に伴い、正常な場合に C が減少することを示す。

(i, j)

(m, s) (m, s)

C のヒストグラムを h(i)と記述する。 Mi)はエネルギー c が eある画素

(i, j) (i, j) の数である。 λ ΐ≥ιが成り立つため例えば 1 = 1/ λの場合を考える。えがえからえまで微小量変化するとき、

2

[数 21]

Α = ∑

(式

で示される Α個の画素力

[数 22]

(式 2 2 )

のエネルギーを持つより安定的な状態に変化する。ここでは仮に、これらの画素のェネルギ一がすべてゼロになると近似している。この式は C^(m' ^s)の値が、 [数 23] dC^{{ 3)} = -i (式 2 3 )

だけ変化することを示し、その結果、

[数 24] dC^[^^s) ― h{l)

一^ (式 24)

が成立する。 h(l) >0であるから、通常 c^(m'^s)は減少する。しかし、

f λが最適値を越えようとするとき、上述の現象、つまり c^(m'^s)の増加が発生する。この現象を検出するこ f

とにより、えの最適値を決定する。

なお、 H(h>0)及び kを定数とするとき、

[0058] [数 25]

H

h{l) = Η = (式 2 5) と仮定すれば、

[0059] [数 26] d\ ² (式 26). が成り立つ。このとき k≠— 3であれば、

[数 27]

C^{{ ,a)} = G + 〔式 2 7)

(3/2 + fc/2)^^3/m/2

となる。これが c^(m'^s)の一般式である

f (Cは定数)。

[0060] えの最適値を検出する際、さらに安全を見て、全単射条件を破る画素の数を検査してもよい。ここで各画素の写像を決定する際、全単射条件を破る確率を pと仮定す

0 る。この場合、

[0061] [数 28] d ₌ ^ (式 28)

8λ λ³/² が成立して、るため、全単射条件を破る画素の数は次式の率で増加する。

[数 29]

p一 ^k(^l)Po

(式 2 9 )

従って、

[数 30] ( ^{= 1} (式^{3 0} )

は定数である。仮に Ml) =Hl^kを仮定するとき、例えば、

[0062] [数 31]

_SoA3/₃₊t/2 ₌ (式 _{3 1} )

は定数になる。しかしえが最適値を越えると、上の値は急速に増加する。この現象を検出し、 B λ

0 ^3/2+k/2Z2^mの値が異常値 Β を越えるかどうかを検査し、 λの最適

Othres

値を決定することができる。同様に、 B λ

1 ^3/2+k/2Z2^mの値が異常値 Β を越える

lthres

力どうかを検査することにより、全単射の第 3の条件を破る画素の増加率 Bを確認する。ファクター 2^mを導入する理由は後述する。このシステムはこれら 2つの閾値に敏感ではない。これらの閾値は、エネルギー ¹"' ^s)の観察では検出し損なった写像の過

f

度の歪みを検出するために用いることができる。

[0063] なお実験では、副写像 f ^(m' ^s)を計算する際、もし λが 0. 1を越えたら f ^(m' ^s)の計算は止めて f^(m' ^s+1)の計算に移行した。え〉 0. 1のとき、画素の輝度 255レベル中のわず力「3」の違いが副写像の計算に影響したためであり、 λ >0. 1のとき正しい結果を得ることは困難だったためである。

[1. 4. 2]ヒス卜グラム h (l)

[0064] C^(m， ^s)の検査はヒストグラム h (1)に依存しな、。全単射及びその第 3の条件の検査

f

の際、 h (1)に影響を受けうる。実際に（ λ , C^(m' ^s) )をプロットすると、 kは通常 1付近に

f

ある。実験では k= lを用い、 B X ²t λ ²を検査した。仮に kの本当の値が 1未満で

0 1

あれば、 B λ ²と B λ ²は定数にならず、ファクター λ ^(1_k)/2に従って徐々に増加する

0 1

。 h(l)が定数であれば、例えばファクタ一はえ ^1/2である。しかし、こうした差は閾値 B thresを正しく設定することによって吸収することができる。

[0065] ここで次式のごとく始点画像を中心が（X , y )、半径 rの円形のオブジェクトであると

0 0

仮定する。

[数 32]

ψ ^ - χ₀)² + 0 - νο)²) - o)² + U - y_D < r)

0 {otherwise) '.

(式 3 2 )

'方、終点画像は、次式のごとく中心 (X , y )、半径カ^のオブジェクトであるとする

[0066] [数 33]

. - χ γ + 一 _yi ≤ τ)

_

(otherwise)

(式 3 3 )

[0067] ここで c (x)は c (x) =x^kの形であるとする。中心 (X , y )及び (X , y )が十分遠い場

0 0 1 1

合、ヒストグラム h(l)は次式の形となる。

[数 34]

(り c ^ ( ）（式 _{3 4} )

[0068] k= 1のとき、画像は背景に埋め込まれた鮮明な境界線を持つオブジェクトを示す。

このオブジェクトは中心が暗ぐ周囲にいくに従って明るくなる。 k=— lのとき、画像は曖昧な境界線を持つオブジェクトを表す。このオブジェクトは中心が最も明るぐ周囲にいくに従って暗くなる。一般のオブジェクトはこれらふたつのタイプのオブジェクトの中間にあると考えてもさして一般性を失わない。したがって、 kは一 l≤k≤lとして大抵の場合をカバーでき、式 27が一般に減少関数であることが保障される。

[0069] なお、式 34からわ力るように、 rは画像の解像度に影響されること、すなわち rは 2m に比例することに注意すべきである。このために [1. 4. 1]においてファクター 2mを導入した。

[1. 4. 3] 7?の動的決定

[0070] ノメータ 7?も同様の方法で自動決定できる。はじめに 7? =0とし、最も細かい解像度における最終的な写像 f W及びエネルギー C⁽ⁿ⁾を計算する。つづいて、 7?をある値

Δ r?だけ増加させ、再び最も細かい解像度における最終写像 f⁽ⁿ⁾及びエネルギー C⁽ ^Π)を計算し直す。この過程を最適値が求まるまで続ける。 7?は写像の剛性を示す。次 f

式の重みだからである。

[0071] [数 35] = II/^<W ， Λ— /(^m'^s— ¹ ， li²

(式 3 5 )

[0072] ηが 0のとき、 D⁽ⁿ⁾は直前の副写像と無関係に決定され、現在の副写像は弾性的

f

に変形され、過度に歪むことになる。一方、 r?が非常に大きな値のとき、 D⁽ⁿ⁾は直前

f の副写像によってほぼ完全に決まる。このとき副写像は非常に剛性が高ぐ画素は同じ場所に射影される。その結果、写像は単位写像になる。 ηの値が 0から次第に増えるとき、後述のごとく C⁽ⁿ⁾は徐々に減少する。しかし 7?の値が最適値を越えると、図 4 に示すとおり、エネルギーは増加し始める。同図の X軸は 7?、 Y軸は Cである。

[0073] この方法で C⁽ⁿ⁾を最小にする最適な 7?の値を得ることができる。しかし、 λの場合に比べていろいろな要素が計算に影響する結果、 C⁽ⁿ⁾は小さく揺らぎながら変化す

f

る。えの場合は、入力が微小量変化するたびに副写像を 1回計算しなおすだけだが、 r?の場合はすべての副写像が計算しなおされるためである。このため、得られた C⁽ ⁿ⁾ fの値が最小であるかどうかを即座に判断することはできない。最小値の候補が見つかれば、さらに細かい区間を設定することによって真の最小値を探す必要がある。

[1. 5]スーパーサンプリング

[0074] 画素間の対応関係を決定する際、自由度を増やすために、 f^(m' ^s)の値域を R XRに拡張することができる (Rは実数の集合)。この場合、終点画像の画素の輝度が補間され、非整数点、

[0075] [数 36]

' • ^s) (i,j) ) (式 3 6 )

における輝度を持つ f^(m' ^s)が提供される。つまりスーパーサンプリングが行われる。実験では、 f^(m' s)は整数及び半整数値をとることが許され、

[数 37] (式 3 7 )

は、

[数 38]

(V(& + ^(¾ ( ) )) ² (. 3 8 )

によって与えられた。

[1. 6]各画像の画素の輝度の正規ィ匕

[0076] 始点画像と終点画像がきわめて異なるオブジェクトを含んで、るとき、写像の計算に元の画素の輝度がそのままでは利用しにくい。輝度の差が大きいために輝度に関するエネルギー c^(m' ^s)が大きくなりすぎ、正しい評価がしづらいためである。

f

[0077] 例えば、人の顔と猫の顔のマッチングをとる場合を考える。猫の顔は毛で覆われており、非常に明るい画素と非常に暗い画素が混じっている。この場合、ふたつの顔の間の副写像を計算するために、まず副画像を正規化する。すなわち、最も暗い画素の輝度を 0、最も明るいそれを 255に設定し、他の画素の輝度は線形補間によって求めておく。

[1. 7]インプリメンテーション

[0078] 始点画像のスキャンに従って計算がリニアに進行する帰納的な方法を用いる。始めに、 1番上の左端の画素 (i, j) = (0, 0)について f(^m' ^s)の値を決定する。次に iを 1ずつ増やしながら各 f ^(m' ^s) (i, j)の値を決定する。 iの値が画像の幅に到達したとき、 jの値を 1増やし、 iを 0に戻す。以降、始点画像のスキャンに伴い f^(m' ^s) (i, j)を決定していく。すべての点について画素の対応が決まれば、ひとつの写像 f(^m' ^s)が決まる。ある p について対応点 q が決まれば、つぎに p の対応点 q が決めら

(i, j) f (i, j) (i, j + 1) f (i, j + 1)

れる。この際、 q の位置は全単射条件を満たすために、 q の位置によって制

f (i, j + 1) f (i, j)

限される。したがって、先に対応点が決まる点ほどこのシステムでは優先度が高くなる

。つねに (0, 0)が最も優先される状態がつづくと、求められる最終の写像に余計な偏向が加わる。本前提技術ではこの状態を回避するために、 f^(m' ^s)を以下の方法で決めていく。

[0079] まず（s mod 4)が 0の場合、 (0, 0)を開始点と U及び jを徐々に増やしながら決めていく。 (s mod 4)が 1の場合、最上行の右端点を開始点とし、 iを減少、 jを増加させながら決めていく。 (s mod 4)が 2のとき、最下行の右端点を開始点とし、 i及び jを減少させながら決めていく。 (s mod 4)が 3の場合、最下行の左端点を開始点とし、 iを増カロ、 jを減少させながら決めていく。解像度が最も細かい第 nレベルには副写像という概念、すなわちパラメータ sが存在しないため、仮に s = 0及び s = 2であるとしてふたつの方向を連続的に計算した。

[0080] 実際のインプリメンテーションでは、全単射条件を破る候補に対してペナルティを与えることにより、候補 (k, 1)の中からできる限り全単射条件を満たす f^(m' ^s) (i, j) (m=0 , · · ·, η)の値を選んだ。第 3の条件を破る候補のエネルギー D (k、 1)には φを掛け、一方、第 1または第 2の条件を破る候補には φを掛ける。今回は φ = 2、 φ = 10000 0を用いた。

[0081] 前述の全単射条件のチェックのために、実際の手続として (k, l) =f^(m' ^s) (i, j)を決定する際に以下のテストを行った。すなわち f(^m' ^s) (i, j)の相続四辺形に含まれる各格子点 (k, 1)に対し、次式の外積の z成分が 0以上になるかどうかを確かめる。

[数 39]

^{W = A} ^ (式 3 9 )

こ _ ゝ

[数 40]

^Ά _ 3 ') ( 一（式 4 0 )

[数 41]

Ώ一 ^m^^a) J^)

D― - i)Y(W)

(式 4 1 )

である（ここでベクトルは三次元ベクトルとし、 z軸は直交右手座標系にお、て定義される）。もし Wが負であれば、その候補については D^(m' ^s) 〖こ φを掛けることによつ

(k, 1)

てペナルティを与え、できるかぎり選択しな、ようにする。

[0082] 図 5 (a)、図 5 (b)はこの条件を検査する理由を示している。図 5 (a)はペナルティのない候補、図 5(b)はペナルティがある候補をそれぞれ表す。隣接画素 (i, j + 1)に対する写像 f ^(m' ^s) (i, j + 1)を決定する際、 Wの z成分が負であれば始点画像平面上におヽて全単射条件を満足する画素は存在しな!ヽ。なぜなら、 q^(m' ^s) は隣接する

(k, 1)

四辺形の境界線を越えるためである。

[1. 7. 1]副写像の順序

[0083] インプリメンテーションでは、解像度レベルが偶数のときには σ (0) =0、 σ (1) = 1 、 σ (2) =2、 σ (3) =3、 σ (4) =0を用い、奇数のときは σ (0) =3、 σ (1) =2、 σ ( 2) =1、 σ (3) =0、 σ (4) =3を用いた。このことで、副写像を適度にシャッフルした。なお、本来副写像は 4種類であり、 sは 0〜3のいずれかである。しかし、実際には s =4に相当する処理を行った。その理由は後述する。

[1.8]補間計算

[0084] 始点画像と終点画像の間の写像が決定された後、対応しあう画素の輝度が補間される。実験では、トライリニア補間を用いた。始点画像平面における正方形 ρ ρ

(i, j) (i + 1, p p が終点画像平面上の四辺形 q q q q に射影さ j) (i, j + l) (i + 1, j + 1) f(i, j) f(i+l, j) f (i, j + D f (i+1, j + 1) れると仮定する。簡単のため、画像間の距離を 1とする。始点画像平面からの距離が t(0≤t≤l)である中間画像の画素 r(x, y, t) (0≤x≤N— 1, 0≤y≤M— 1)は以下の要領で求められる。まず画素 r(x, y, t)の位置（ただし x, y, tER)を次式で求める。

[0085] [数 42]

= (1 - dx)(l - dy)(l - t)(i ) + (1 - dx)(l - dy)tf(i,j)

+ dx(l - y)(l - + l ) + dx(l - dy)tf(i + l,j)

+ (1— dx)dy{l一 t)(i,j + 1) + (1 - dx)dytf(i,j + 1)

+ dxdy{l一 t){i + 1)+ dxdytf(i + l,j + 1)

(式 4 2 )

つづいて r(x, y, t)における画素の輝度が次の式を用いて決定される

[0086] [数 43] V{r{x,y,i)) - (1- dx)(l― dy){l一 i)V(_P(£J)) + (1 - dx)(l - dy)tV{q ₎)

+

(式 4 3 ) ' ここで dx及び dyはパラメータであり、 0から 1まで変化する。

[1.9]拘束条件を課したときの写像

[0087] V、ままでは拘束条件力 Sレ、つさ、存在しな、場合の写像の決定を述べた。しかし、始点画像と終点画像の特定の画素間に予め対応関係が規定されているとき、これを拘束条件としたうえで写像を決定することができる。

[0088] 基本的な考えは、まず始点画像の特定の画素を終点画像の特定の画素に移す大まかな写像によって始点画像を大まかに変形し、しかる後、写像 fを正確に計算する

[0089] まず始めに、始点画像の特定の画素を終点画像の特定の画素に射影し、始点画像の他の画素を適当な位置に射影する大まかな写像を決める。すなわち、特定の画素に近い画素は、その特定の画素が射影される場所の近くに射影されるような写像である。ここで第 mレベルの大まかな写像を F^(m)と記述する。

[0090] 大まかな写像 Fは以下の要領で決める。まず、いくつかの画素について写像を特定する。始点画像について n個の画素、

s

[数 44]

P(i0j0)? (¾lJl)' ···, P(in_s- jn_s-l)

(式 4 4) を特定するとき、以下の値を決める。

[数 45] (式 4 5)

始点画像の他の画素の変位量は、 P (h=0, ···, n 1)の変位に重み付けを

(ih, jh s

して求められる平均である。すなわち画素 p は、終点画像の以下の画素に射影される。

[0092] [数 46]

(式 4 6) こし^ ~ゝ _、 ^f ゝ

[数 47] weightk{i ) =

total wetan i,, ) (式 47)

[数 48] total we%gnt\%^j) = > 一んー (式 4 8)

ん =o

とする。

[0093] つづ、て、 F^(m)に近、候補写像 fがより少な 1、エネルギーを持つように、その

(m, s)

のエネルギー D(^m'^s) を変更する。正確には、が¹"' s' . Jま、

(i， Jリ

[数 49] v(i ) ―

τ リ + L

(式 49)

である。ただし、

[数 50]

(式 5 0 ) であり、 κ , ≥0とする。最後に、前述の写像の自動計算プロセスにより、 fを完全決定する。

ここで、 f ^(m， ^s) (i,j)が F^(m) (i,j)に十分近いとき、つまりそれらの距離が、

[数 51]

(式 5 1 )

以内であるとき、 E ^(m' ^s) 力^になることに注意すべきである。そのように定義した理

2 (i, j)

由は、各 f^(m' ^s) (i,j)が F^(m) (i,j)に十分近い限り、終点画像において適切な位置に落ち着くよう、その値を自動的に決めたいためである。この理由により、正確な対応関係を詳細に特定する必要がなぐ始点画像は終点画像にマッチするように自動的にマツビングされる。

[2]具体的な処理手順

[1]の各要素技術による処理の流れを説明する。

[0095] 図 6は前提技術の全体手順を示すフローチャートである。同図のごとぐまず多重解像度特異点フィルタを用いた処理を行!ヽ（S 1)、つづヽて始点画像と終点画像のマツチングをとる（S2)。ただし、 S2は必須ではなく、 S1で得られた画像の特徴をもとに画像認識などの処理を行ってもょ、。

[0096] 図 7は図 6の S1の詳細を示すフローチャートである。ここでは S2で始点画像と終点画像のマッチングをとることを前提としている。そのため、まず特異点フィルタによって始点画像の階層化を行い（S 10)、一連の始点階層画像を得る。つづいて同様の方法で終点画像の階層化を行い（S 11)、一連の終点階層画像を得る。ただし、 S10と S 11の順序は任意であるし、始点階層画像と終点階層画像を並行して生成して、くことちでさる。

[0097] 図 8は図 7の S10の詳細を示すフローチャートである。もとの始点画像のサイズは 2ⁿ

X 2ⁿとする。始点階層画像は解像度が細かいほうから順に作られるため、処理の対象となる解像度レベルを示すパラメータ mを nにセットする（S100)。つづいて第 mレベルの画像 ρ^(κι'^ω、 p ^ p^(m'²⁾、 p^(m'³⁾から特異点フィルタを用いて特異点を検出し (S101)、それぞれ第 m— 1レベルの画像 p(^m_1'。)、 p(^m_1' ^υ、 p(^m_1' ²)、 p(^m_1'³)を生成する（S102)。ここでは m=nであるため、 p(^m' )=p(^m' =ρ^(ιη' ²)=p(^m， ³)=p(ⁿ)であり、ひとつの始点画像力も 4種類の副画像が生成される。

[0098] 図 9は第 mレベルの画像の一部と、第 m— 1レベルの画像の一部の対応関係を示している。同図の数値は各画素の輝度を示す。同図のは〜のっの画像を象徴するもので、 p^(m_1'^G)を生成する場合には、 p^(m'^s)は p^(m'^G)であると考える。 [1.2]で示した規則により、 p(^m_1' )は例えば同図で輝度を記入したブロックにつ V、て、そこに含まれる 4画素のうち「3」、 p^(m_1' "は「8」、 p^(m_1' ²)は「6」、 p^(m_1' ³)を「1 0」をそれぞれ取得し、このブロックをそれぞれ取得したひとつの画素で置き換える。したがって、第 m— 1レベルの副画像のサイズは 2^m_1 X 2^m_1になる。

[0099] つづいて mをデクリメントし（図 8の S103)、 mが負になっていないことを確認し（SI 04)、 S101に戻ってつぎに解像度の粗い副画像を生成していく。この繰り返し処理の結果、 m=0、すなわち第 0レベルの副画像が生成された時点で S10が終了する。第 0レベルの副画像のサイズは 1 X 1である。

[0100] 図 10は S 10によって生成された始点階層画像を n= 3の場合について例示している。最初の始点画像のみが 4つの系列に共通であり、以降特異点の種類に応じてそれぞれ独立に副画像が生成されていく。なお、図 8の処理は図 7の S11にも共通であり、同様の手順を経て終点階層画像も生成される。以上で図 6の S1による処理が完了する。

[0101] 前提技術では、図 6の S2に進むためにマッチング評価の準備をする。図 11はその手順を示している。同図のごとぐまず複数の評価式が設定される（S30)。 [1.3.2 . 1]で導入した画素に関するエネルギー C^(m'^s)と [1.3.2.2]で導入した写像の滑 f

らかさに関するエネルギー D^(m'^s)がそれである。つぎに、これらの評価式を統合して f

総合評価式を立てる（S31)。 [1.3.2.3]で導入した総エネルギーえ C(^m'^s) +D^(m' f s⁾がそれであり、 [1.3.2.2]で導入した r?を用いれば、

f

[0102] [数 52]

^∑∑ C '、 _(i , J) + Ε。 , =) _(i , _{j} + E l} s) となる。ただし、総和は i、； jについてそれぞれ 0、 1· ··、 2^m— 1で計算する。以上でマツチング評価の準備が整う。

[0103] 図 12は図 6の S2の詳細を示すフローチャートである。 [1]で述べたごとぐ始点階層画像と終点階層画像のマッチングは互いに同じ解像度レベルの画像どうしでとられる。画像間の大域的なマッチングを良好にとるために、解像度が粗いレベルから順にマッチングを計算する。特異点フィルタを用いて始点階層画像および終点階層画像を生成してヽるため、特異点の位置や輝度は解像度の粗ヽレベルでも明確に保存されており、大域的なマッチングの結果は従来に比べて非常に優れたものになる。

[0104] 図 12のごとぐまず係数パラメータ 7?を 0、レベルパラメータ mを 0に設定する（S20) 。つづいて、始点階層画像中の第 mレベルの 4つの副画像と終点階層画像中の第 m レベルの 4つの副画像のそれぞれの間でマッチングを計算し、それぞれ全単射条件を満たし、かつエネルギーを最小にするような 4種類の副写像 f(^m' ^s) (s = 0, 1, 2, 3) を求める（S21)。全単射条件は [1. 3. 3]で述べた相続四辺形を用いて検査される。この際、式 17、 18が示すように、第 mレベルにおける副写像は第 m—lレベルのそれらに拘束されるため、より解像度の粗いレベルにおけるマッチングが順次利用されていく。これは異なるレベル間の垂直的参照である。なお、いま m=0であってそれより粗、レベルはな、が、この例外的な処理は図 13で後述する。

一方、同一レベル内における水平的参照も行われる。 [1. 3. 3]の式 20のごとぐ f^(m ' ³)は f(^m， ²)に、 f(^m， ²)は f(^m， "に、 f(^m， ^υは f(^m， °)に、それぞれ類似するように決める。その理由は、特異点の種類が違っても、それらがもともと同じ始点画像と終点画像に含まれている以上、副写像がまったく異なるという状況は不自然だ力である。式 20からゎ力るように、副写像どうしが近いほどエネルギーは小さくなり、マッチングが良好とみなされる。

[0105] なお、最初に決めるべき f^(m' ^G)については同一のレベルで参照できる副写像がないため、式 19に示すごとくひとつ粗いレベルを参照する。ただし、実験では f(^m' ³⁾まで求まった後、これを拘束条件として ί^(1η' ^ωを一回更新するという手続をとつた。これは式 2 0に s=4を代入し、 f^(m' ⁴⁾を新たな f^(m' ^G)とすることに等しい。产，と，の関連度が低くなり過ぎる傾向を回避するためであり、この措置によって実験結果がより良好になつた。この措置にカ卩え、実験では [1. 7. 1]に示す副写像のシャッフルも行った。これも本来特異点の種類ごとに決まる副写像どうしの関連度を密接に保つ趣旨である。また、処理の開始点に依存する偏向を回避するために、 sの値にしたがって開始点の位置を変える点は [1. 7]で述べたとおりである。

[0106] 図 13は第 0レベルにおいて副写像を決定する様子を示す図である。第 0レベルでは各副画像がただひとつの画素で構成されるため、 4つの副写像 ^ί( ' ^s)はすべて自動的に単位写像に決まる。図 14は第 1レベルにおいて副写像を決定する様子を示す図である。第 1レベルでは副画像がそれぞれ 4画素で構成される。同図ではこれら 4 画素が実線で示されている。いま、 p ⁽¹' ^s)の点 Xの対応点を q⁽¹' ^s)の中で探すとき、以下の手順を踏む。

1.第 1レベルの解像度で点 Xの左上点 a、右上点 b、左下点 c、右下点 dを求める。

[0107] 2.点 a〜dがひとつ粗いレベル、つまり第 0レベルにおいて属する画素を探す。図 1

4の場合、点 a〜dはそれぞれ画素 A〜Dに属する。ただし、画素 A〜Cは本来存在しない仮想的な画素である。

[0108] 3.第 0レベルですでに求まっている画素 A〜Dの対応点 A，〜D，を q⁽¹' ^s)の中にプロットする。画素 A'〜C 'は仮想的な画素であり、それぞれ画素 A〜Cと同じ位置にあるちのとする。

[0109] 4.画素 Aの中の点 aの対応点 a'が画素 A，の中にあるとみなし、点 a'をプロットする

。このとき、点 aが画素 Aの中で占める位置（この場合、右下）と、点 a'が画素 A'の中で占める位置が同じであると仮定する。

5. 4と同様の方法で対応点 b '〜d 'をプロットし、点 a'〜d 'で相続四辺形を作る。

[0110] 6.相続四辺形の中でエネルギーが最小になるよう、点 Xの対応点 x 'を探す。対応点 x 'の候補として、例えば画素の中心が相続四辺形に含まれるものに限定してもよい。図 14の場合、 4つの画素がすべて候補になる。

[0111] 以上がある点 Xの対応点の決定手順である。同様の処理を他のすべての点について行い、副写像を決める。第 2レベル以上のレベルでは、次第に相続四辺形の形が崩れて、くと考えられるため、図 3に示すように画素 A'〜D 'の間隔が空ヽて、く状況が発生する。 [0112] こうして、ある第 mレベルの 4つの副写像が決まれば、 mをインクリメントし（図 12の S 22)、 m力^!を超えて!/、な! /、ことを確力めて（S23)、 S21に戻る。以下、 S21に戻るたびに次第に細かい解像度のレベルの副写像を求め、最後に S21に戻ったときに第 n レベルの写像 f⁽ⁿ⁾を決める。この写像は 7? =0に関して定まったものであるから、 f⁽ⁿ⁾ ( r? =0)と書く。

[0113] つぎに異なる 7?に関する写像も求めるベぐ 7?を Δ 7?だけシフトし、 mをゼロクリアする（S24)。新たな 7?が所定の探索打切り値 7? を超えていないことを確認し (S25)

max

、 S21に戻り、今回の 7?に関して写像 f⁽ⁿ⁾ ( 7? = Δ 7? )を求める。この処理を繰り返し、 S21で f⁽ⁿ⁾ =i A 7? ) (i=0, 1, · · ·)を求めていく。 ηが η を超えたとき S26に進

max

み、後述の方法で最適な r? = r? を決定し、 f⁽ⁿ⁾ ( η = η )を最終的に写像 f (ⁿ⁾とす

opt opt

る。

[0114] 図 15は図 12の S21の詳細を示すフローチャートである。このフローチャートにより、ある定まった r?について、第 mレベルにおける副写像が決まる。副写像を決める際、前提技術では副写像ごとに最適な λを独立して決める。

[0115] 同図のごとぐまず sとえをゼロクリアする（S210)。つぎに、そのときのえについて（および暗に 7?について)エネルギーを最小にする副写像 f^(m' ^s)を求め（S211)、これを f ^(m' ^s) ( λ =0)と書く。異なる λに関する写像も求めるベぐ λを Δ λだけシフトし、新たなえが所定の探索打切り値えを超えていないことを確認し (S213)、 S211に

max

戻り、以降の繰り返し処理で产' ³⁾ (ぇ= 1 ぇ）（1= 0, 1 , ···)を求める。えがえを

max 超えたとき S214に進み、最適な λ = λ を決定し、 &- ^s) ( = λ )を最終的に写

opt opt

像 f(^m' ^s)とする (S214)。

[0116] つぎに、同一レベルにおける他の副写像を求めるベぐ λをゼロクリアし、 sをインクリメントする（S215)。 sが 4を超えていないことを確認し（S216)、 S211に戻る。 s=4 になれば上述のごとく f^(m' ³⁾を利用して f ^(m' ^ωを更新し、そのレベルにおける副写像の決定を終了する。

[0117] 図 16は、ある mと sについて λを変えながら求められた f(^m' ^s) ( =i A λ ) (i=0, 1, …；)に対応するエネルギー C(^m' ^s)の挙動を示す図である。 [1. 4]で述べたとおり、 λ

f

が増加すると通常 c^(m'^s)は減少する。しかし、えが最適値を超えると c^(m'^s)は増加に転じる。そこで本前提技術では c^(m' ^s)が極小値をとるときの λをえと決める。同図 f opt

のように λ > λ の範囲で再度 c^(m， ^s)が小さくなつていつても、その時点ではすでに opt f

写像がくずれていて意味をなさないため、最初の極小点に注目すればよい。 λ

optは副写像ごとに独立して決めて、き、最後に f ⁽ⁿ⁾につ、てもひとつ定まる。

[0118] 一方、図 17は、 7?を変えながら求められた f(ⁿ) ( r? =1Δ r? ) (i = 0, 1, · · · )に対応するエネルギー C⁽ⁿ⁾の挙動を示す図である。ここでも ηが増加すると通常 C⁽ⁿ⁾は減少 f f するが、 r?が最適値を超えると C⁽ⁿ⁾は増加に転じる。そこで C⁽ⁿ⁾が極小値をとるとき f f

の ηを η と決める。図 17は図 4の横軸のゼロ付近を拡大した図と考えてよい。 η opt opt が決まれば f⁽ⁿ⁾を最終決定することができる。

[0119] 以上、本前提技術によれば種々のメリットが得られる。まずエッジを検出する必要がないため、エッジ検出タイプの従来技術の課題を解消できる。また、画像に含まれるオブジェ外に対する先験的な知識も不要であり、対応点の自動検出が実現する。特異点フィルタによれば、解像度の粗ヽレベルでも特異点の輝度や位置を維持することができ、オブジェクト認識、特徴抽出、画像マッチングに極めて有利である。その結果、人手作業を大幅に軽減する画像処理システムの構築が可能となる。

なお、本前提技術について次のような変形技術も考えられる。

(1)前提技術では始点階層画像と終点階層画像の間でマッチングをとる際にパラメータの自動決定を行った力この方法は階層画像間ではなぐ通常の 2枚の画像間のマッチングをとる場合全般に利用できる。

[0120] たとえば 2枚の画像間で、画素の輝度の差に関するエネルギー Eと画素の位置的

0

なずれに関するエネルギー Eのふたつを評価式とし、これらの線形和 E = α Ε +

1 tot 0

Eを総合評価式とする。この総合評価式の極値付近に注目して αを自動決定する。つまり、いろいろな αについて Ε が最小になるような写像を求める。それらの写像の tot

うち、 αに関して Eが極小値をとるときの αを最適パラメータと決める。そのパラメータに対応する写像を最終的に両画像間の最適マッチングとみなす。

[0121] これ以外にも評価式の設定にはいろいろな方法があり、例えば 1ZEと 1ZEのよ

1 2 うに、評価結果が良好なほど大きな値をとるものを採用してもよい。総合評価式も必ずしも線形和である必要はなぐ η乗和 (η=2、 1/2, 1、一 2など）、多項式、任意の関数などを適宜選択すればよい。

[0122] ノラメータも、 aのみ、前提技術のごとく 7?とえのふたつの場合、それ以上の場合など、いずれでもよい。パラメータが 3以上の場合はひとつずつ変化させて決めていく

(2)本前提技術では、総合評価式の値が最小になるよう写像を決めた後、総合評価式を構成するひとつの評価式である C^(m' ^s)が極小になる点を検出してパラメータを決

f

定した。しかし、こうした二段回処理の代わりに、状況によっては単に総合評価式の最小値が最小になるようにパラメータを決めても効果的である。その場合、例えば α Ε + β Εを総合評価式とし、 α + β = 1なる拘束条件を設けて各評価式を平等に扱

0 1

うなどの措置を講じてもよい。パラメータの自動決定の本質は、エネルギーが最小になるようにパラメータを決めて、く点にあるからである。

(3)前提技術では各解像度レベルで 4種類の特異点に関する 4種類の副画像を生成した。しかし、当然 4種類のうち 1、 2、 3種類を選択的に用いてもよい。例えば、画像中に明るい点がひとつだけ存在する状態であれば、極大点に関する f^(m' ³⁾だけで階層画像を生成しても相応の効果が得られるはずである。その場合、同一レベルで異なる副写像は不要になるため、 sに関する計算量が減る効果がある。

(4)本前提技術では特異点フィルタによってレベルがひとつ進むと画素が 1Z4になつた。例えば 3 X 3で 1ブロックとし、その中で特異点を探す構成も可能であり、その場合、レベルがひとつ進むと画素は 1Z9になる。

(5)始点画像と終点画像力 Sカラーの場合、それらをまず白黒画像に変換し、写像を計算する。その結果求められた写像を用いて始点のカラー画像を変換する。それ以外の方法として、 RGBの各成分につ、て副写像を計算してもよ!/、。

[3]前提技術の改良点

[0123] 以上の前提技術を基本とし、マッチング精度を向上させるためのいくつかの改良がなされている。ここではその改良点を述べる。

[3. 1]色情報を考慮に入れた特異点フィルタおよび副画像

[0124] 画像の色情報を有効に用いるために、特異点フィルタを以下のように変更した。まず色空間としては、人間の直感に最も合致するといわれている HISを用いた。但し色を輝度に変換する際は、輝度 Iに代わり人間の目の感度に最も近いといわれている輝度 Yを選択した。

[0125] [数 53]

2R-G-R

-― tan

H■

2π

R + G + B

7 = 0.299x^ + 0.587xG+0.114xB (式 53

[0126] ここで画素 aにおける Y (輝度）を Y(a)、 S (彩度）を S (a)として、次のような記号を定義する。

[数 54]

■(Y(a)≤Y(b))

Y(a,b)

(Y(a) >Y(b))

■(Y(a)≥Y(b))

βΛα

■(Y(a)<Y(b))

■(S(a)≥S(b))

(S(a)<S(b)) (式 54)

上の定義を用いて以下のような 5つのフィルタを用意する。

[数 55]

0,3)

^UY ^UY \F(2i,2 j)， (2i,2 j+l) ， ^UY (2+1,2 j)， (2i+l,2 j+l) "

j)， (2+1,2 j+l) "

(式 55) このうち上力も 4つのフィルタは改良前の前提技術におけるフィルタとほぼ同じで、輝度の特異点を色情報も残しながら保存する。最後のフィルタは色の彩度の特異点をこちらも色情報を残しながら保存する。

[0129] これらのフィルタによって、各レベルにつき 5種類の副画像（サブイメージ）が生成される。なお、最も高いレベルの副画像は元画像に一致する。

[0130] [数 56]

_ _n (H,l) _ ( », 2) _ ( n,3) _ (n, 4) _

(式 5 6 )

[3. 2]エッジ画像およびその副画像

[0131] 輝度微分 (エッジ）の情報をマッチングに利用するため、さらに一次微分エッジ検出フィルタを用いる。このフィルタはあるオペレータ Gとの畳み込み積分で実現できる。第 nレベルの画像の、水平方向、垂直方向の微分に対応した 2種類のフィルタをそれぞれ以下のように表す。

[数 57]

(式 _{5 7} )

[0132] ここで Gは画像解析においてエッジ検出に用いられる一般的なオペレータを適用することが可能である力演算スピードなども考慮して以下のようなオペレータを選択した。

[0133] [数 58]

(式 5 8 )

次にこの画像を多重解像度化する。フィルタにより 0を中心とした輝度をもつ画像が生成されるため、次のような平均値画像が副画像としては最も適切である。 [数 59]

, (m+l,h) (m+l,h) (m+l,h) (m+l,h)

^ (2ί, 2ί) ^(2;,2 +1) ^ ^/(2;+l,2 ) ^ -^(2;+1,2 +1)

(式 5 9 )

[0135] 式 59の画像は後述する Forward Stage,すなわち初回副写像導出ステージの計算の際、エネルギー関数のうち新たに導入された輝度微分 (エッジ)の差によるエネルギ一に用いられる。

エッジの大きさ、すなわち絶対値も計算に必要なため、以下のように表す。

[0136] [数 60]

(式 6 0 ) この値は常に正であるため、多重解像度化には最大値フィルタを用、る。

[0137] [数 61] Y

+l)ノノ

(式 6 1 )

式 61の画像は後述する Forward Stageの計算の際、計算する順序を決定するのに用いられる。

[3. 3]計算処理手順

[0138] 計算は最も粗い解像度の副画像カゝら順に行う。副画像は 5つあるため、各レベルの解像度において計算は複数回行われる。これをターンと呼び、最大計算回数を tで表すことにする。各ターンは前記 Forward Stageと、副写像再計算ステージである Refinement Stageという二つのエネルギー最小化計算から構成される。図 18は第 mレベルにおける副写像を決める計算のうち改良点に係るフローチャートである。

[0139] 同図のごとぐ sをゼロクリアする（S40)。つぎに Forward Stage (S41)において始点画像 P力も終点画像 qへの写像 f^(m' ^s)および、終点画像 qから始点画像 pへの写像 g^(m、 ^S)を順次、エネルギー最小化によって求める。以下、写像 f^(m' ^S)の導出について記述する。ここで最小化するエネルギーは、改良後の前提技術においては、対応する画素値によるエネルギー Cと、写像の滑らかさによるエネルギー Dの和である。

[0140] [数 62] m /in ( + ( )) ^ (式.り ₉2 , )

[0141] エネルギー Cは、輝度の差によるエネルギー C (前記改良前の前提技術における

I

エネルギー Cと等価）と、色相、彩度によるエネルギー C、輝度微分 (エッジ)の差に

C

よるエネルギー cで構成され、以下のように表される。

E

[0142] [数 63]

( ,ゾ) = |r(d)

))「

σ (z, ) = C{ (z, ) + ψθ^ ( , J) + eC ( , J) (式 ₆ 3 ) ここでパラメータえ、 φおよび Θは 0以上の実数であり、本改良後の技術においては定数である。ここでこれらのパラメータを定数とできるのは、新たに導入された

Refinement Stageにより、パラメータに対する結果の安定性が向上したためである。また、エネルギー Cは副写像 f^(m' ^s)の種類 sに関わらず、座標と解像度のレベルによつ

E

て決定する値である。

[0143] エネルギー Dは前記改良前の前提技術と同じものを用いる。ただし前記改良前の前提技術において、写像の滑らかさを保証するエネルギー Eを導出する際、隣接する画素のみを考慮していた力 S、周囲の何画素を考慮するかをパラメータ dで指定できるように改良した。

[0144] [数 64]

( , j) =∑ ∑ \ ((f fa i)) -― a ( , j))― if ff(f，ゾ D '）-— ( , f r\ ))\\|

(式 6 4 )

[0145] 次の Refinement Stageに備えて、このステージでは終点画像 qから始点画像への写像 g(^m' ^s)も同様に計算する。

[0146] Refinement Stage (S42)では Forward Stageにおいて求めた双方向の写像 f(^m， ^s)および g^(m' ^s)を基に、より妥当な写像 f，^(m' ^s)を求める。ここでは新たに定義されるェネルギー Mにつ!/、てエネルギー最小化計算を行う。エネルギー Mは終点画像から始点画像への写像 gとの整合度 Mと、もとの写像との差 Mより構成され、 Mを最小とする

0 1

ような f' が求められる。

[0147] [数 65]

M /,ゾ) = || z,ノ) - (/,川²

(式 _{6 5 )}

[0148] 対称性を損なわないように、終点画像 qから始点画像 pへの写像 g' (^m' ^s)も同様の方法で求めておく。

その後、 sをインクリメントし（S43)、 sが tを超えていないことを確認し（S44)、次のターンの Forward Stage (S41)に進む。その際前記 Eを次のように置き換えてエネルギ

0

一最小化計算を行う。

[0149] [数 66]

Ei(i ) =

(式 6 6 )

[3. 4]写像の計算順序

[0150] 写像の滑らかさを表すエネルギー Eを計算する際、周囲の点の写像を用いるため、それらの点がすでに計算されているかどうかがエネルギーに影響を与える。すなわち、どの点から順番に計算するかによって、全体の写像の精度が大きく変化する。そこでエッジの絶対値画像を用いる。エッジの部分は情報量を多く含むため、エッジの絶対値が大きいところ力先に写像計算を行う。このことによって、特に二値画像のような画像に対して非常に精度の高い写像を求めることができるようになった。

[動画符号化と復号に関する実施の形態]

以上の前提技術を一部利用した動画処理の具体例を述べる。

[0151] 図 19は、動画の符号化装置と復号装置の構成および処理を示す。同図上段が符号化装置、下段が復号装置に関する。

[1]符号化装置の構成

[0152] CPF : 前提技術の Critical Point Filter,すなわち特異点フィルタを用いる画像マツチングプロセッサ。キーフレーム間のマッチングを画素単位で計算し、対応点情報を出力する。この情報はファイルとして出力される。このファイルは、ソース側のキーフレ一ムの各画素がデスティネーション側のキーフレームのいずれの画素に対応する力を記述する。したがって、このファイルをもとに、これらのキーフレーム間で対応しあう画素の位置と画素値を内挿計算すれば、ふたつのキーフレーム間のモーフイング画像が得られる。なお、このファイルをソース側のキーフレームだけに作用させて内挿計算をすれば、単にソース側のキーフレームの各画素をこのファイルに記述した対応画素の位置へ徐々に移動させるモーフイング画像が得られる。この場合、対応画素間で位置だけが内挿されたことになる。

[0153] なお、 CPFの代わりに、広く画像マッチングプロセッサを利用することができるが、本実施の形態の趣旨からいえば、精度が高い画素マッチングが理想的であり、前提技術はその条件を満たす。

[0154] DE： Differential Encoder差分（誤差）符号化器。ふたつの画像フレーム間の差分をハフマン符号化その他の統計手法に基づき可変長符号化する。

[0155] NR : maskable Noise Reducerノイズリデューサ。人間の視覚では微細な変化を認識できないことが多い。たとえば輝度の変化の激しい部分、つまり輝度の空間周波数成分が高い成分が強い領域では、輝度変化の誤差は視覚的には把握されない。動画情報にはさまざまな形でノイズが重畳しており、そのようなデータは視覚的には単にノイズとして認識されるだけで画像としての意味を持たなヽ。そのような視覚的無意味なランダム情報、すなわち「視覚的マスク情報」を無視することが、より高い圧縮率を達成するために重要である。

[0156] 現在のブロックマッチングにおける量子化は、輝度値に関する視覚的マスク情報を利用したものであるが、輝度値以外にもいくつかの視覚的マスク情報が存在する。 N Rは、空間位置情報ならびに時間位置情報に関する視覚的マスクを利用する。空間位置情報の視覚的マスクは、位置情報に関して、輝度変化が複雑な画像の場合は空間周波数の位相成分が視覚的に認識されにくいという事実を利用する。時間位置情報の視覚的マスクは、時間方向での変化が激し、部分では時間方向にデータの変化がずれたとしても、視覚的にはその差が認識されにくい事実を利用する。これらは、ずれも所定のしき、値との比較して検出する。

[0157] 少なくともブロックマッチングと差分符号化という現在の MPEGのスキームでは、これらのマスクを積極的に利用することは困難である。これに対し、前提技術における復号処理は、視覚的な不自然さをもたらすような不連続性を回避するために、動画上の変化をトリリニアその他の補間で生成するものであり、それは誤差を輝度方向だけでなぐ空間方向や時間方向に散らして視覚的に目立たなくする働きを持つ。 NR は前提技術との組合せにぉ、て有用である。

[0158] DD： Differential Decoder差分 (誤差)復号器。 DEで符号化された差分を復号し、その差分が生じた画像フレームに加算することで、その画像フレームの精度を高める

[0159] なお、これらのほかに、ある単一のキーフレームに対応点情報を作用させ、そのキ一フレームの画素移動だけ力仮想的に別のキーフレームを生成する機能が存在する。以下、この機能を実現する機能ブロックを画素シフタとよぶ。

[2]符号化処理

[0160] 図 19において、「F0」等は処理の対象となる動画の各フレーム、「M0—4」は CPF によって生成された F0と F4間の対応点情報を示す。符号ィ匕は以下の手順で進む。

[0161] a) 1以上の画像フレーム（F1〜F3)を間に挟む第 1、第 2キーフレーム（F0、F4) 間で CPFによってマッチングを計算し、第 1、第 2キーフレーム間の対応点情報 (M0 4)を生成するステップ。

b) 第 1、第 2キーフレーム間の対応点情報 (M0— 4)をもとに、画素シフタによって第 1キーフレーム (F0)に含まれる画素を移動させて仮想の第 2キーフレーム (F4，）を生成するステップ。

c) 現実の第 2キーフレーム（F4)と仮想の第 2キーフレーム（F4， )との差分を NR 機能付き DE (DE + NRと表記)で圧縮符号化するステップ。

d) 第 1キーフレーム (FO)、第 1、第 2キーフレーム間の対応点情報 (MO— 4)、および、現実の第 2キーフレームと仮想の第 2キーフレーム間で圧縮符号ィ匕された差分 ( Δ 4)をこれらのキーフレーム (FO、 F4)間の符号ィ匕データとして出力するステップ。出力先は記録媒体、伝送媒体を問わない。実際には後述の j)で出力される情報と一体となり、動画符号ィ匕データとして記録媒体等に出力される。

[0162] つづ!/、て、第 2キーフレーム（F4)以降につ!、て以下の処理を行う。

e) 現実の第 2キーフレーム (F4)と仮想の第 2キーフレーム (F4， )間で圧縮符号化された差分（ Δ 4)を DDで復号するステップ。

f) 復号された差分と前記仮想の第 2キーフレーム (F4' )とから、改良された仮想の第 2キーフレーム（F4")を DDで生成するステップ。

g) 1以上の画像フレーム（F5〜F7)を間に挟む第 2、第 3キーフレーム（F4、 F8) 間で CPFによってマッチングを計算し、第 2、第 3キーフレーム間の対応点情報 (M4 8)を生成するステップ。

h) 第 2、第 3キーフレーム間の対応点情報 (M4— 8)をもとに、画素シフタによって、改良された仮想の第 2キーフレーム (F4")に含まれる画素を移動させることによつて、仮想の第 3キーフレーム（F8， )を生成するステップ。

i) 現実の第 3キーフレーム (F8)と仮想の第 3キーフレーム (F8， )との差分を DE + NRで圧縮符号化するステップ。

j) 第 2、第 3キーフレーム間の対応点情報 (M4— 8)、および現実の第 3キーフレームと仮想の第 3キーフレーム間で圧縮符号ィ匕された差分（ Δ 8)をこれらのキーフレーム (F4、 F8)間の符号ィ匕データとして出力するステップ。出力先は一般に d)の出力先と同じである。

[0163] 以下、さらに後続のキーフレームについて、図 19のフレーム F9以下に示すごとく、順次前記の e)から j)のステップを繰り返し、所定のグループ終了キーフレームに到達したときに繰り返し処理を終了する。グループ終了キーフレームは、 MPEGでいう 1G OPの終了フレームに相当する。したがって、このフレームの次のフレームが新たなグループの先頭フレームとして新たに第 1キーフレームと見なされ、 a)以下の処理が繰り返される。以上の処理により、 MPEGでいう GOPに相当するグループ（以下、単にグループとよぶ）について、キーフレーム（MPEGでいう Iピクチャ）に相当する画像は 1枚のみ符号化および伝送すればょ、。

[3]復号装置の構成

符号化側にもましてシンプルな構成である。

DD : 符号化装置の DDと同じ。

INT: INTerpolator ネ ΐ間プロセッサ。

[0164] これらの他に符号化側同様の画素シフタが存在する。ふたつの画像フレームと対応点情報から内挿処理による中間フレームを生成する。

[4]復号処理

復号は以下の手順で進む。

[0165] k) 1以上の画像フレーム（F1〜F3)を間に挟む第 1、第 2キーフレーム（F0、F4) 間の対応点情報 (MO— 4)、および第 1キーフレーム (F0)を取得するステップ。取得は伝送媒体、記録媒体のいずれからでもよい。

1) 第 1、第 2キーフレーム間の対応点情報 (M0— 4)をもとに、画像シフタによって第 1キーフレーム (F0)に含まれる画素を移動させることによって、仮想の第 2キーフレーム（F4，）を生成するステップ。

m) 予め符号ィ匕側にて 1)同様の処理により、仮想の第 2キーフレーム (F4' )が生成され、符号ィ匕側でこれと現実の第 2キーフレーム (F4)との差分の圧縮符号化データ（ Δ 4)を生成して、るため、これを取得するステップ。

o) 取得された差分の圧縮符号化データ（ Δ 4)を DDで復号し、仮想の第 2キーフレーム (F4，）と加算して、改良された仮想の第 2キーフレーム (F4，，）を生成するステップ。

P) 第 1、第 2キーフレーム間の対応点情報 (M0— 4)をもとに、 INTによって、第 1 キーフレーム (F0)と改良された仮想の第 2キーフレーム (F4")間で補間計算をすることにより、これらのキーフレーム（FO、 F4")の間に存在すべき中間フレーム（Fl"〜 F3")を生成するステップ。

q) 第 1キーフレーム (FO)、生成された中間フレーム (F1"〜F3")、改良された仮想の第 2キーフレーム（F4")をこれらのキーフレーム間の復号データとして表示装置等へ出力するステップ。

[0166] つづ!/、て、第 2キーフレーム（F4)以降につ!、て以下の処理を行う。

r) 1以上の画像フレーム（F5〜F7)を間に挟む第 2、第 3キーフレーム（F4、 F8) 間の対応点情報 (M4— 8)を取得するステップ。

s) 第 2、第 3キーフレーム間の対応点情報 (M4— 8)をもとに、画素シフタによって、改良された仮想の第 2キーフレーム (F4")に含まれる画素を移動させることによつて、仮想の第 3キーフレーム（F8， )を生成するステップ。

t) 予め符号ィ匕側にて s)同様の処理により、符号ィ匕側でも仮想の第 3キーフレーム (F8， )が生成され、符号化側でこれと現実の第 3キーフレーム (F8)との差分の圧縮符号化データ（ Δ 8)を生成しており、これを取得するステップ。

u) 取得された差分の圧縮符号化データ（ Δ 8)と仮想の第 3キーフレーム (F8 ' )とから、 DDによって、改良された仮想の第 3キーフレーム (F8")を生成するステップ。

V) 第 2、第 3キーフレーム間の対応点情報 (M4— 8)をもとに、 INTによって、改良された仮想の第 2キーフレーム (F4")と改良された仮想の第 3キーフレーム (F8")間で補間計算をすることにより、これらのキーフレームの間に存在すべき中間フレーム（ F5，〜F7， )を生成するステップ。

w) 改良された仮想の第 2キーフレーム（F4")、生成された中間フレーム（F5'〜F 7，）、改良された仮想の第 3キーフレーム（F8，，）をこれらのキーフレーム（F4"、 F8") 間の復号データとして表示装置などへ出力するステップ。

[0167] 以下、さらに後続のキーフレームについて、図 19のフレーム F9以降に示すごとく、順次前記の r)力も w)のステップを繰り返し、グループ終了キーフレームに到達したときに繰り返し処理を終了する。このフレームの次のフレームが新たなグループの先頭フレームとして新たに第 1キーフレームと見なされ、 k)以下の処理が繰り返される。

[5]本実施の形態によるメリット [0168] 画像マッチングに前提技術の CPFを利用する場合、マッチング精度が高いため、本実施の形態で実現される圧縮率が高くなる。なぜなら、 DE + NRによって圧縮すべき差分が最初力小さぐかつ統計的な偏りが大きくなるためである。

[0169] 同様に、 CPFを用いる場合、この符号ィ匕方法はブロックマッチングを用いないので、圧縮率を高めても MPEGで問題となるブロックノイズがでない。もちろん、 CPF以外の画像マッチングでも、ブロックノイズがでなヽ処理方法を採用すればよ!ヽ。

[0170] もともと MPEGは差分の最小化しか考慮しないが、 CPFは本来対応すべき個所を検出するため、究極的には MPEGよりも高い圧縮率が実現できる。

[0171] 符号ィ匕装置は画像マッチングプロセッサ、ノイズリダクション機能付き差分符号化器、差分復号器、画素シフタで構成でき、簡易である。また、ノイズリダクション機能はォプショナルな機能であり、これはなくともよい。同様に、復号装置も補間プロセッサ、差分復号器、画素シフタで構成でき、簡素である。とくに、復号装置は画像マッチングを行う必要もなぐ処理量が軽い。

[0172] 仮想のキーフレームを生成するたびに、それと現実のキーフレームの差分を Δ 4、

Δ 8などのように符号ィ匕データへ取り込むため、グループごとに 1枚しか完全な形のキーフレームを符号ィ匕しないにもかかわらず、長い動画を再生しても誤差の蓄積がない。

[6]変形技術

[0173] 第 1、第 2キーフレーム (FO、 F4)間のマッチング計算をして対応点情報ファイルを生成する際、それらキーフレーム間に存在する中間フレーム (F1〜F3)も考慮してもよい（図 19の破線矢印）。その場合、 CPFは FOと Fl、 F1と F2、 F2と F3、 F3と F4のそれぞれの組につ!、てマッチングを計算し、 4個のファイル（仮に部分ファイル MO〜 M3とよぶ）を生成する。つづいて、これら 4個のファイルを統合してひとつの対応点情報ファイルとして出力すればよい。

[0174] 統合のために、まず、 FOの各画素が MOによって F1上のどこへ移動するかを特定する。つづいて、 F1上で特定された画素が Mlによって F2上のどこへ移動するかを特定する。これを F4まで行えば、 4個の部分ファイルにより、 FOと F4の対応がより正確になる。 FOと F4は多少距離があり、それらの間よりも隣接する画像フレーム間のマツチング精度のほうが一般に高いためである。

[0175] なお、この方法は最終的に F0と F4のマッチング精度を改善するものである力対応点情報ファイルを時間の関数として表現してもよい。その場合、部分ファイルを統合せず、 4個の状態のまま、これらを対応点情報ファイルとみなして復号側へ提供すればよい。復号側は FO、 F4、 MOから Flを生成し、 FO、 F4、 MO、 Mlから F2を生成し、という繰り返し処理でより正確な動画を復号できる。

[0176] (第 2実施形態）

本発明の他の実施形態は、図 19の符号ィ匕装置に関する。ここでは、画像マツチングの正確性を示す尺度として画像のマッチングエネルギーを導入し、これを DE + N Rにおけるノイズリダクション等に利用する。以下、適宜図 19を用いて説明する力特に言及しない構成、機能については第 1実施形態と同様である。

[0177] ここでいうマッチングエネルギーとは、対応点どうしの距離と画素値の違いで定まるものであり、例えば前提技術における式 49に示されている。本実施形態では、 CPF における画像マッチングの際得られるこのマッチングエネルギーをいわば副産物として利用する。前提技術の画像マッチングでは、キーフレーム間の各画素につき、写像のエネルギーが最小となるものを対応点として検出する。前提技術のこのような特徴に着目すれば、マッチングエネルギーの低い画素に関しては良好なマッチングがとれており、一方マッチングエネルギーの高い箇所については、当然キーフレーム間で位置や画素値の変化の大きい画素であったはずである力場合によってはマッチングエラーがあった可能性もあると評価できる。以下詳説するが、本実施形態ではマツチング精度の高い部分については差分の圧縮率を高める。また別の例では、マツチングェラーが推定される画素に関する差分情報を高く圧縮しても良い。

[0178] [1]符号化処理

本実施形態の符号化装置では、 CPFが第 1、第 2のキーフレームのマッチングを計算する際に、併せて両フレーム間で対応しあう各画素のマッチングエネルギーを取得し、第 1のキーフレーム（FO)上に各画素のマッチングエネルギーを記述したエネルギーマップを生成する。同様に、その他の隣接しあうキーフレーム間でもエネルギ一マップを生成する。すなわち、エネルギーマップとは、キーフレーム間の対応点それぞれのマッチングエネルギーを、基本的には前のキーフレームの各画素に関して記述したデータである。なお、エネルギーマップは前後のキーフレームのうち、後のキーフレーム上に表しても良い。エネルギーマップは不図示の経路により CPFから D E + NRに送られる。 DE + NRでは、このエネルギーマップを利用してキーフレーム間のマッチングの良否を評価し、それに基づいて、仮想のキーフレームと現実のキーフレームの差分を適応的に圧縮符号化する。なお、 DE + NRには、エネルギーマツプの他、対応点情報ファイルも不図示の経路で送られて、る。

[0179] 図 20は、本実施形態に係る図 19の DE + NRの構成を示す図である。図 20の DE

+NRは差分計算器 10と、差分圧縮部 12と、エネルギー取得部 14と、判定部 16とを備える。このうち、前 2者が専ら DEに相当し、後 2者が専ら NRに相当する。以下第 1 のキーフレーム（F0)と第 2のキーフレーム（F4)およびその中間の画像フレーム（F1 〜F3)を符号ィ匕する際の DE + NRの動作を説明する力後続の各キーフレーム、画像フレームの符号化においても、 DE + NRの動作は同様である。

[0180] 差分計算器 10は、現実の第 2キーフレーム (F4)と仮想の第 2キーフレーム (F4，）を取得して、位置的に対応しあう画素どうしの画素値の差分をとる。これにより、各画素が両キーフレーム間の画素値の差をもつ一種の画像が形成され、これを差分画像と呼ぶ。差分画像はエネルギー取得部 14へと送られる。また、エネルギー取得部 14 には、現実の第 1キーフレーム（F0)と現実の第 2キーフレーム（F4)の間のエネルギ一マップ及び対応点情報（M0— 4)力図 19の CPF力も入力される。エネルギー取得部 14は、これらを利用して差分画像のマッチングエネルギーを取得する。

[0181] まず、取得部 14は、第 1、第 2キーフレーム間の対応点情報 (M0— 4)を CPFから取得する。これを利用して、差分画像力も仮想の第 2キーフレーム (F4，）、第 1キーフレーム（F0)とたどっていくことで、差分画像のどの画素が第 1キーフレーム（F0)のどの画素をシフトしたものに対応している力、対応関係を取得する。その上で第 1キーフレーム上に表されたエネルギーマップ上の各画素のエネルギーを参照し、差分画像の各画素に対応する第 1キーフレーム（F0)上の画素のマッチングエネルギーを、差分画像の各画素のマッチングエネルギーとして取得する。差分画像のマッチングエネルギーはこうして求められる。 [0182] エネルギー取得部 14は、差分画像のマッチングエネルギーを判定部 16へと送る。判定部 16は差分画像の各画素のマッチングエネルギーを利用して、差分画像のうち高圧縮対象領域を判定し、いずれの領域を高圧縮すべき力の情報を圧縮部 12へと通知する。判定は例えば以下のように行われる。判定部 16は、差分画像を 16X16画素単位のブロックに分割し、各ブロックに含まれる画素の全てについてマッチングェネルギーを所定のしきい値と比較する。比較の結果、ブロック内の全ての画素のマツチングェネルギーがしき、値以下であった場合は、その領域を高圧縮対象ブロックと判定する。

[0183] 圧縮部 12は、差分画像を JPEG形式にて圧縮する。この際、判定部 16から通知された高圧縮対応領域の情報を利用し、圧縮率を通常の領域と高圧縮対応領域との間で適応的に変化させる。具体的には、高圧縮対象ブロックは DCT係数の量子化幅を通常のブロックに比べて大きくする処理などが利用できる。別の例では、差分画像では、高圧縮対象ブロックの画素値を 0にしてしまつてから JPEG圧縮をかける処理を行ってもよい。いずれにせよ、マッチングエネルギーが低い領域を高圧縮する理由は以下の考え方による。

[0184] すなわち、上述のごとくマッチングエネルギーの低い画素は、キーフレーム間のマツチング結果が良好であるとみなせる。従って、差分画像のうちマッチングエネルギーが低、部分に関しては、現実の第 2のキーフレーム (F4)と仮想の第 2のキーフレーム (F4' )の間に差分は本来生じにくぐ差分が生じているとすればそれはノイズであると考えてよい。よって、差分画像においてマッチングエネルギーが低い領域は、高圧縮による情報の欠落を気にすることなぐ他の領域に比べて大幅に圧縮できる。一方、マッチングエネルギーの大きい領域については、マッチングにエラーが生じている可能性もあり、仮想の第 2キーフレーム (F4，）と現実の第 2キーフレーム (F4)の差分は復号において重要な情報であるため、圧縮率を低くとどめ、復号時の正確性を優先する。

[0185] [2]第 2実施形態によるメリット

以上の処理を経て、圧縮部 18は、現実の第 2キーフレーム (F4)と仮想の第 2キーフレーム (F4' )の圧縮符号化された差分（ Δ 4)を出力する。本実施形態による符号化装置によれば、現実のキーフレームと仮想のキーフレームの差分情報を、符号ィ匕画像をより原画像に忠実に、正確な復号を行うための重要性に応じて適応的に圧縮可能であり、復号の正確性を保ちつつ高い符号ィ匕効率が実現できる。重要性とは、もちろん、本実施形態でも第 1実施形態に係るメリットを享受できる。

[0186] [3]第 2実施形態の変形技術

本実施形態の変形例として、マッチングエネルギーの大きい画素、中でも近傍の画素の対応傾向と著しく異なる対応傾向を示す画素はマッチングエラーを起こしている場合が多いと経験的に認められることから、マッチングエネルギーが周囲の画素と比ベ大幅に異なる画素をマッチングエラーと評価し、これをノイズリダクションに導入することもできる。この場合、 DE+NRは、第 2キーフレーム（F4)の各画素のマッチングエネルギーを、例えば自身を中心とする 9X9画素のブロック内の、他の画素のマッチングエネルギーの平均と比較する。比較の結果両者の差が所定のしき、値を超えて V、る場合、そのような画素はマッチングエラーをおこして、ると判定してもよ、。

[0187] エラーを起こしている対応情報は復号側にとって無意味なデータであると考えることができ、現実の第 2キーフレーム (F4)と仮想の第 2キーフレーム (F4，）間の差分情報中では、マッチングエラーを起こしている画素に関するデータはノイズといえる。よつて、高圧縮による情報の欠落への配慮を不要とし、 DE + NRは、現実のキーフレームと仮想のキーフレーム間の差分画像のうち、現実のキーフレーム間のマッチングエラーに対応する画素を他の画素に比べて高い率で圧縮する。なお、マッチングェラーの判定は、例えば、周囲の画素の動きベクトルの傾向と、注目する画素の動きべタトルの傾向を比較し、注目する画素の動きベクトルが周囲の傾向と著しく異なるか否かをもって行なっても良い。

[0188] 第 2実施形態においても、第 1実施形態と同様に、第 1、第 2キーフレーム (FO、 F4 )間の中間フレーム（F1〜F3)を考慮し、これら全ての画像フレームの隣り合うそれぞれの組にっ、てマッチングを計算して対応点情報ファイル (MO〜M3)を生成し、それらを統合して第 1、第 2キーフレーム (FO、 F1)間で一つの対応点情報ファイルを得る変形技術が考えられる。第 1実施形態の変形技術同様、マッチング精度を向上し、正確な動画復号が実現できる。 [0189] さらに、この変形技術では、各画像フレーム間のマッチングエネルギーを計算してそれをシーンチェンジ検出等に応用可能である。シーンチェンジ検出に係る構成は以下のとおりである。まず、 CPFは FOと Fl、 F1と F2、 F2と F3, F3と F4' · 'それぞれの組について、マッチング計算をおこない、その副産物としてエネルギーマップ、 EO 、 Ε1、 Ε2、 Ε3 · · ·を取得する。ここで、ある画像フレーム全体の画素に係るマツチングエネルギーの平均をとり、それを所定のシーンチェンジ検出用しきい値と比較し、その直後の画像を新たなグループとすればょ、。例えば F5と F6の間のエネルギーマップ Ε5に基づき、 F5と F6のマッチングに係る F5の各画素のマッチングエネルギ一を平均した結果、その値がキーフレーム追加用しきい値を越えたとする。この場合、直後のキーフレームすなわち F6以下を新たなグループとし、 F6が次のグループの第 1キーフレームとすればよい。マッチングエネルギーが大きい場合、画像間に大きな変化があつたと考えることができるためである。これにより、自動的なシーンチェンジの検出ができ、シーンチェンジに対応してグループの選定が可能となる。

[0190] 各エネルギーマップに基づいて、各画像フレーム内画素の平均マッチングェネルギーを計算して、これを累積的に加算していき、その値が所定のしきい値を越えた時点でその画像フレームを新たにキーフレームとして登録しても良い。画像フレーム間の変化量の累積がある一定値を越えた時点でキーフレームを追加できれば、より復号時の画質の向上がはかれるためである。

産業上の利用可能性

[0191] 以上のように、本発明は動画の圧縮符号ィ匕および復号に利用することができる。

Claims

請求の範囲

[1] a) 1以上の画像フレームを間に挟む第 1、第 2キーフレーム間でマッチングを計算し、第 1、第 2キーフレーム間の対応点情報を生成するステップと、

b) 第 1、第 2キーフレーム間の対応点情報をもとに当該キーフレームに含まれる画素を移動させることによって、仮想の第 2キーフレームを生成するステップと、 c) 現実の第 2キーフレームと仮想の第 2キーフレームとの差分を圧縮符号ィ匕するステップと、

d) 第 1キーフレーム、第 1、第 2キーフレーム間の対応点情報、および、現実の第 2キーフレームと仮想の第 2キーフレーム間で圧縮符号ィ匕された差分をこれらのキーフレーム間の符号ィ匕データとして出力するステップと、

を備える動画符号化方法。

[2] 請求項 1に記載の方法において、さらに、

e) 現実の第 2キーフレームと仮想の第 2キーフレーム間で圧縮符号化された差分を復号するステップと、

f) 復号された差分と前記仮想の第 2キーフレームとから、改良された仮想の第 2キ一フレームを生成するステップと、

g) 1以上の画像フレームを間に挟む第 2、第 3キーフレーム間でマッチングを計算し、第 2、第 3キーフレーム間の対応点情報を生成するステップと、

h) 第 2、第 3キーフレーム間の対応点情報をもとに、改良された仮想の第 2キーフレームに含まれる画素を移動させることによって、仮想の第 3キーフレームを生成するステップと、

i)現実の第 3キーフレームと仮想の第 3キーフレームとの差分を圧縮符号ィ匕するステツプと、

j)第 2、第 3キーフレーム間の対応点情報、および現実の第 3キーフレームと仮想の第 3キーフレーム間で圧縮符号化された差分をこれらのキーフレーム間の符号ィ匕データとして出力するステップと、

を備える動画符号化方法。

[3] 請求項 2に記載の方法において、さらに後続のキーフレームについて、順次前記の e)から j)のステップを繰り返す動画符号化方法。

[4] 請求項 3に記載の方法にお、て、前記の e)から j)のステップを所定のグループ終了キーフレームに到達したときに終了し、当該グループ終了キーフレームの次のキーフレームを新たに第 1キーフレームと見なして前記の a)以下の処理を繰り返す動画符号化方法。

[5] k) 1以上の画像フレームを間に挟む第 1、第 2キーフレーム間の対応点情報、および第 1キーフレームを取得するステップと、

1) 第 1、第 2キーフレーム間の対応点情報をもとに第 1キーフレームに含まれる画素を移動させることによって、仮想の第 2キーフレームを生成するステップと、 m) 予め符号ィ匕側にて求められた現実の第 2キーフレームと仮想の第 2キーフレームとの差分の圧縮符号化データを取得するステップと、

q) 第 1キーフレーム、生成された中間フレーム、改良された仮想の第 2キーフレームをこれらのキーフレーム間の復号データとして出力するステップと、

を備える動画復号方法。

[6] 請求項 5に記載の方法において、さらに、

r) 1以上の画像フレームを間に挟む第 2、第 3キーフレーム間の対応点情報を取得するステップと、

s) 第 2、第 3キーフレーム間の対応点情報をもとに、改良された仮想の第 2キーフレームに含まれる画素を移動させることによって、仮想の第 3キーフレームを生成するステップと、

t) 予め符号ィ匕側にて求められた現実の第 3キーフレームと仮想の第 3キーフレームとの差分の圧縮符号化データを取得するステップと、

u) 取得された差分の圧縮符号化データと前記仮想の第 3キーフレームとから、改良された仮想の第 3キーフレームを生成するステップと、

V) 第 2、第 3キーフレーム間の対応点情報をもとに、改良された仮想の第 2キーフレームと改良された仮想の第 3キーフレーム間で補間計算をすることにより、これらのキーフレームの間に存在すべき中間フレームを生成するステップと、

w) 改良された仮想の第 2キーフレーム、生成された中間フレーム、改良された仮想の第 3キーフレームをこれらのキーフレーム間の復号データとして出力するステツプと、

を備える動画復号方法。

[7] 請求項 6に記載の方法において、さらに後続のキーフレームについて、順次前記の r)カゝら w)のステップを繰り返す動画復号方法。

[8] 請求項 7に記載の方法にお、て、前記の!：)力も w)のステップを所定のグループ終了キーフレームに到達したときに終了し、当該グループ終了キーフレームの次のキーフレームを新たに第 1キーフレームと見なして前記の k)以下の処理を繰り返す動画復号方法。

[9] 請求項 1に記載の方法をコンピュータに実行せしめることを特徴とするコンピュータプログラム。

[10] 請求項 5に記載の方法をコンピュータに実行せしめることを特徴とするコンピュータプログラム。

[11] 前記 a)のステップにおけるマッチングの正確さを評価するステップをさらに備え、評価の結果に依存して、前記 c)のステップにおける圧縮スキームを切り替えることを特徴とする請求項 1から 4のいずれか〖こ記載の動画符号ィ匕方法。

[12] 前記現実の第 2キーフレームと仮想の第 2キーフレームとの差分のうち、前記評価するステップにおいて前記第 1、第 2キーフレーム間のマッチング精度が高いと判断された領域に対応する部分の圧縮率を高くすることを特徴とする請求項 11に記載の動画符号化方法。

[13] 前記評価するステップでは、前記対応点情報を生成するステップにおいて相互に対応するとされた前記第 1、第 2キーフレーム間の各点のうち、対応傾向を示すパラメータが近接する点のものと比べて所定のしきい値以上に異なる点をマッチングエラーとして検出し、

前記現実の第 2キーフレームと仮想の第 2キーフレームとの差分のうち、マッチングエラーが検出された領域に対応する部分の圧縮率を高くすることを特徴とする請求項 11に記載の動画符号化方法。

[14] 前記評価するステップでは、マッチングエネルギー値に着目してマッチングの正確さを評価することを特徴とする請求項 11から 13のいずれかに記載の動画符号化方法。

[15] 前記マッチングエネルギーは対応点の位置と画素値の双方に基づ、て導出されることを特徴とする請求項 14に記載の動画符号ィ匕方法。

[16] 前記第 1、第 2キーフレーム及び間に挟まれる画像フレームの全てについて隣り合う画像フレームどうしのマッチングをさらに計算するステップと、

前記計算するステップで得られる各画像間のマッチングエネルギーを計算して、各画像フレームのマッチングエネルギーに関するパラメータを取得するステップと、前記パラメータを累積的に加算するステップと、

加算の結果が所定のしきい値を越える画像フレームを新たにキーフレームとして登録するステップと、

をさらに備えることを特徴とする請求項 1から 4、 11から 15のいずれかに記載の動画符号化方法。

[17] 前記第 2キーフレーム以降の各画像フレームについても、隣り合う画像フレームどうしでマッチングを計算し、マッチングエネルギーに関するパラメータの累積的な加算値が前記しきい値を越えた場合はその直前の画像フレームを新たにキーフレームとして登録することを特徴とする請求項 16に記載の動画符号ィ匕方法。

[18] 画像フレームの全てについて隣り合う画像どうしのマッチングをさらに計算するステップと、

前記計算するステップで得られる各画像フレーム間のマッチングエネルギーに基づいて各画像フレームのマッチングエネルギーに関するパラメータを取得するステップと、

前記パラメータが、所定のしき、値を越える画像フレームを前記グループ終了キーフレームとするステップと、

をさらに備えることを特徴とする請求項 4に記載の動画符号化方法。

第 1、第 2画像フレーム間で、領域ベースの画像マッチングを計算し、そのマツチング結果を利用して、少なくとも第 3画像フレームを符号ィ匕する方法であって、画像マッチングの結果の良否を領域ごとに判定するステップと、

第 3画像フレームの符号ィ匕プロセスにお、て、前記判定するステップにお!/、て判定された良否に基づき、領域ごとに量子化スキームを選択するステップと、

を備える動画符号化方法。