(57)【要約】  符号化技術は、３以上の画像フレームを含む画像グループの両端画像フレーム間でマッチング計算を実行するステップと、マッチング計算の結果得られた両端画像フレーム間の対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成するステップと、仮想的に生成された中間画像フレームのうちいずれかが、現実の中間画像フレームと許容値以上の差分を有するか否かを所定の判定基準のもとで判定するステップと、許容値以上の差分を有する中間画像フレームが存在すると判定された場合、その中間画像フレームの画像上において差分が大きい領域を特定するステップと、特定された領域に関する差分情報と、両端画像フレームのうち少なくとも一方と、対応点情報とを含む符号化データを生成するステップとを含む。
2007069350.tif 000002
【特許請求の範囲】
【請求項１】
画像フレームの列を降順または昇順にＦ０、Ｆ１、・・・、Ｆｎ−１、Ｆｎ（ｎは２以上の整数）と表記し、画像フレームＦｉ、Ｆｊ（ｉ，ｊ＝０，１，・・・，ｎ）間で対応しあう点の位置関係を示す対応点情報をＭｉ−ｊと表記するとき、
ａ）Ｆ０とＦｎ間でマッチングを計算してＭ０−ｎを生成するステップと、
ｂ）Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ上でｐ０に対応する点ｐｎを算出するステップと、
ｃ）ステップｂをＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１、点ｐ２の集合を利用して仮想的なＦ２、・・・、点ｐｎの集合を利用して仮想的なＦｎをそれぞれ生成するステップと、
ｄ）仮想的なＦ１と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組に対し、その組に含まれる画像フレーム間の差分が大きな組Ｓｋ（ｋ＝１，・・・，ｎ）の有無を所定の判定基準をもとに判定するステップと、
ｅ）差分が大きな組Ｓｋが存在する場合、少なくとも、Ｆｈ（ｈ＝０，１，・・・，ｋ−１）とＦｋ間でマッチングを計算してＭｈ−ｋを生成するステップと、
ｆ）Ｍｈ−ｋの情報を利用し、Ｍ０−ｎを修正するステップと、
ｇ）少なくともＦ０と修正されたＭ０−ｎを含む形式の符号化データを出力するステップと、
を含むことを特徴とする画像符号化方法。
【請求項２】
請求項１に記載の方法において、ステップｄは、画像フレーム間の差分の大きさを所定の領域単位で判定することを特徴とする画像符号化方法。
【請求項３】
請求項１に記載の方法において、ステップｅは、
ｅ１）差分が大きな組Ｓｋが存在する場合、Ｆ０とＦ１間のＭ０−１、Ｆ１とＦ２間のＭ１−２、・・・、Ｆｋ−１とＦｋ間のＭ（ｋ−１）−ｋをそれぞれ求めるステップと、
ｅ２）Ｍ０−１、Ｍ１−２、・・・、Ｍ（ｋ−１）−ｋを統合してＭ０−ｋを生成するステップと、
を含むことを特徴とする画像符号化方法。
【請求項４】
請求項３に記載の方法において、ステップｅ２は、Ｍ０−１によってｐ０に対応するｐ１を求め、Ｍ１−２によってｐ１に対応するｐ２を求め、・・・、Ｍ（ｋ−１）−ｋによってｐｋ−１に対応するｐｋを求め、ｐ０に対応する点をｐ１、ｐ２、・・・、ｐｋと順に特定することにより、最終的にｐ０に対応するｐｋを特定してＭ０−ｋを生成することを特徴とする画像符号化方法。
【請求項５】
請求項４に記載の方法において、ステップｆは、Ｍ０−ｋの情報を利用し、ｐ０がｐｋを経てｐｎへ至る軌跡を示す形式にて、修正されたＭ０−ｎを生成することを特徴とする画像符号化方法。
【請求項６】
請求項１に記載の方法において、ステップｄにて差分が大きな組Ｓｋが存在することが判明した場合、ステップｇはＦ０と修正されたＭ０−ｎに加え、組Ｓｋにおける差分の情報を含む形式の符号化データを出力することを特徴とする画像符号化方法。
【請求項７】
請求項６に記載の方法において、組Ｓｋにおける差分の情報は、画像フレームの中で差分が大きかった領域についてのみ符号化データへ含められることを特徴とする画像符号化方法。
【請求項８】
請求項７に記載の方法において、差分とともに、少なくともｋの値と前記領域の位置情報が符号化データへ含められることを特徴とする画像符号化方法。
【請求項９】
請求項８に記載の方法において、差分は圧縮処理を受けた後、符号化データへ含められることを特徴とする画像符号化方法。
【請求項１０】
画像フレームの列を降順または昇順にＦ０、Ｆ１、・・・、Ｆｎ−１、Ｆｎ（ｎは２以上の整数）と表記し、画像フレームＦｉ、Ｆｊ（ｉ，ｊ＝０，１，・・・，ｎ）間で対応しあう点の位置関係を示す対応点情報をＭｉ−ｊと表記するとき、
Ｆ０とＦｎ間でマッチングを計算してＭ０−ｎを生成するマッチング処理部と、
Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ上でｐ０に対応する点ｐｎを算出する処理をＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１、点ｐ２の集合を利用して仮想的なＦ２、・・・、点ｐｎの集合を利用して仮想的なＦｎをそれぞれ生成する中間フレーム生成部と、
仮想的なＦ１と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組に対し、その組に含まれる画像フレーム間の差分が大きな組Ｓｋ（ｋ＝１，・・・，ｎ）の有無を所定の判定基準をもとに判定する判定部と、
を備え、前記マッチング処理部は、差分が大きな組Ｓｋが存在する場合、少なくとも、Ｆｈ（ｈ＝０，１，・・・，ｋ−１）とＦｋ間でマッチングを計算してＭｈ−ｋを生成し、このＭｈ−ｋの情報を利用してＭ０−ｎを修正し、本装置はさらに、少なくともＦ０と修正されたＭ０−ｎを含む形式の符号化データを出力する出力部を含むことを特徴とする画像符号化装置。
【請求項１１】
３以上の画像フレームを含む画像グループの両端画像フレーム間でマッチング計算を実行するステップと、
マッチング計算の結果得られた両端画像フレーム間の対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成するステップと、
画像上のいずれかの領域について、仮想的に生成された中間画像フレームのうちいずれかが、現実の中間画像フレームと許容値以上の差分を有するか否かを所定の判定基準のもとで判定する判定ステップと、
両端画像フレームのうち少なくとも一方と、対応点情報とを含む符号化データを生成し、さらに、前記判定ステップにおいて、許容値以上の差分を有する領域が存在すると判定された場合には、その領域に関する差分情報を前記符号化データに含めて生成するステップと、
を含むことを特徴とする画像符号化方法。
【請求項１２】
３以上の画像フレームを含む画像グループの両端画像フレーム間でマッチング計算を実行するマッチング処理部と、
マッチング計算の結果得られた両端画像フレーム間の対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する中間フレーム生成部と、
画像上のいずれかの領域について、仮想的に生成された中間画像フレームのうちいずれかが、現実の中間画像フレームと許容値以上の差分を有するか否かを所定の判定基準のもとで判定する判定部と、
両端画像フレームのうち少なくとも一方と、対応点情報とを含む符号化データを出力し、さらに、前記判定部において、許容値以上の差分を有する領域が存在すると判定された場合には、その領域に関する差分情報を出力する出力部と、
を含むことを特徴とする画像符号化装置。
【請求項１３】
画像フレームの列を降順または昇順にＦ０、Ｆ１、・・・、Ｆｎ−１、Ｆｎ（ｎは２以上の整数）と表記し、画像フレームＦｉ、Ｆｊ（ｉ，ｊ＝０，１，・・・，ｎ）間で対応しあう点の位置関係を示す対応点情報をＭｉ−ｊと表記するとき、
ｐ）少なくともＦ０、Ｍ０−ｎおよび所定の差分情報を含む形式の符号化データを入力するステップと、
ｑ）Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ−１上でｐ０に対応する点ｐｎ−１を算出するステップと、
ｒ）ステップｑをＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１、点ｐ２の集合を利用して仮想的なＦ２、・・・、点ｐｎの集合を利用して仮想的なＦｎをそれぞれ生成するステップと、
ｓ）仮想的なＦ１と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組のうち、前記差分情報が与えられているＳｋ（ｋ＝１，・・・，ｎ）を特定するステップと、
ｔ）仮想的なＦｋに対し、前記差分情報によって定まる差分を加算することにより、修正された仮想的なＦｋを生成するステップと、
ｕ）復号結果として、Ｆ０、仮想的なＦ１、仮想的なＦ２、・・・、修正された仮想的なＦｋ、仮想的なＦｋ＋１、・・・、仮想的なＦｎ−１を出力するステップと、
を含むことを特徴とする画像復号方法。
【請求項１４】
請求項１３に記載の方法において、前記差分情報は画像フレーム間の差分が大きな領域についてのみ差分を記述しており、ステップｔは差分を加算する際、前記領域の位置情報を特定することを特徴とする画像復号方法。
【請求項１５】
請求項１３に記載の方法において、前記差分情報は圧縮されており、ステップｔは前記差分情報を伸長してから加算することを特徴とする画像復号方法。
【請求項１６】
請求項１３に記載の方法において、Ｍ０−ｎは、ｐ０がｐｋを経てｐｎへ至る軌跡を示す形式にて生成されていることを特徴とする画像復号方法。
【請求項１７】
画像フレームの列を降順または昇順にＦ０、Ｆ１、・・・、Ｆｎ−１、Ｆｎ（ｎは２以上の整数）と表記し、画像フレームＦｉ、Ｆｊ（ｉ，ｊ＝０，１，・・・，ｎ）間で対応しあう点の位置関係を示す対応点情報をＭｉ−ｊと表記するとき、
少なくともＦ０、Ｍ０−ｎおよび所定の差分情報を含む形式の符号化データを入力する入力部と、
Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ−１上でｐ０に対応する点ｐｎ−１を算出する処理をＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１、点ｐ２の集合を利用して仮想的なＦ２、・・・、点ｐｎの集合を利用して仮想的なＦｎをそれぞれ生成する中間フレーム生成部と、
仮想的なＦ１と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組のうち、前記差分情報が与えられているＳｋ（ｋ＝１，・・・，ｎ）を特定する特定部と、
仮想的なＦｋに対し、前記差分情報によって定まる差分を加算することにより、修正された仮想的なＦｋを生成する中間フレーム修正部と、
復号結果として、Ｆ０、仮想的なＦ１、仮想的なＦ２、・・・、修正された仮想的なＦｋ、仮想的なＦｋ＋１、・・・、仮想的なＦｎ−１を出力する出力部と、
を含むことを特徴とする画像復号装置。
【請求項１８】
３以上の画像フレームを含む画像グループの両端画像フレームのうちの一方と、それら両端画像フレーム間の対応点情報と、所定の差分情報とを含む符号化データを入力するステップと、
前記対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成するステップと、
仮想的に生成された中間画像フレームそれぞれとそれに対応する現実の中間画像フレームとによる組のうち、差分が大きな組として符号化データ内に記述された組の中間画像フレームの画像上にて差分が大きい領域を特定するステップと、
差分が大きな組に含まれる仮想的な画像フレームに対し、前記領域における差分を加算することにより、修正された仮想的な画像フレームを生成するステップと、
復号結果として、両端画像フレームのうちの一方と、差分が大きな組については修正された仮想的な中間画像フレームと、それ以外の組については仮想的な中間画像フレームとを復号データとして出力するステップと、
を含むことを特徴とする画像復号方法。
【請求項１９】
３以上の画像フレームを含む画像グループの両端画像フレームのうちの一方と、それら両端画像フレーム間の対応点情報と、所定の差分情報とを含む符号化データを入力する入力部と、
前記対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する中間フレーム生成部と、
仮想的に生成された中間画像フレームそれぞれとそれに対応する現実の中間画像フレームとによる組のうち、差分が大きな組として符号化データ内に記述された組の中間画像フレームの画像上にて差分が大きい領域を特定する領域特定部と、
差分が大きな組に含まれる仮想的な画像フレームに対し、前記領域における差分を加算することにより、修正された仮想的な画像フレームを生成する中間フレーム修正部と、
復号結果として、両端画像フレームのうちの一方と、差分が大きな組については修正された仮想的な中間画像フレームと、それ以外の組については仮想的な中間画像フレームとを復号データとして出力する出力部と、
を含むことを特徴とする画像復号装置。
【請求項２０】
請求項１１に記載の画像符号化方法の各ステップをコンピュータに実行せしめることを特徴とするコンピュータプログラム。
【請求項２１】
請求項１８に記載の画像復号方法の各ステップをコンピュータに実行せしめることを特徴とするコンピュータプログラム。
【請求項２２】
画像符号化ユニットと画像復号ユニットとを有する画像処理システムにおいて、
画像符号化ユニットは、
３以上の画像フレームを含む画像グループの両端画像フレーム間でマッチング計算を実行するマッチング処理部と、
マッチング計算の結果得られた両端画像フレーム間の対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する符号化側中間フレーム生成部と、
画像上のいずれかの領域について、仮想的に生成された中間画像フレームのうちいずれかが、現実の中間画像フレームと許容値以上の差分を有するか否かを所定の判定基準のもとで判定する判定部と、
両端画像フレームのうち少なくとも一方と、対応点情報とを含む符号化データをメモリへ書き込み、さらに許容値以上の差分を有する領域が存在すると判定された場合、その領域に関する差分情報を書き込む書込制御部とを備え、
画像復号ユニットは、
前記メモリから符号化データを読み出す読出制御部と、
符号化データに含まれる画像フレームのデータと対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する復号側中間フレーム生成部と、
符号化データに差分情報が含まれる領域を特定する領域特定部と、
特定された領域を含む仮想的な画像フレームに対し、前記領域における差分を加算することにより、修正された仮想的な画像フレームを生成する中間フレーム修正部と、
復号結果として、両端画像フレームのうちの一方または双方と、前記領域を含む仮想的な画像フレームについては修正された仮想的な中間画像フレームと、前記領域を含まない仮想的な画像フレームについてはその仮想的な中間画像フレーム自体とを復号データとして出力する出力部と、
を含むことを特徴とする画像処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、画像、とくに動画像の符号化および復号技術に関する。
【背景技術】
【０００２】
ＭＰＥＧ（Motion Picture Experts Group）は動画圧縮のひとつの標準技術である。ＭＰＥＧでは、ブロックマッチングが利用される。このマッチングは、ブロック間の差分が最小になるようブロック探索を行う。そのため、差分は確かに小さくなるが、必ずしもフレーム間で本来対応しあう領域どうしが対応づけられるわけではない。
【特許文献１】特許第２９２７３５０号
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ＭＰＥＧでは、圧縮率を上げようとすると、いわゆるブロックノイズが問題になる。このノイズの発生を抑え、フレーム間コヒーレンシに注目した圧縮率をさらに上げるためには、現状のブロックマッチングベースの技術を改める必要がある。求める技術は、本来対応しあう領域なり画素なりが正しく対応するよう符号化すべきであり、また、単純なブロックマッチングは避けることが望ましい。
【課題を解決するための手段】
【０００４】
この発明の目的は以下のとおりである。まず、ＭＰＥＧで問題になるブロックノイズが出ない動画像圧縮技術、すなわち動画像符号化技術を提供する。また、その動画像符号化技術に対応する動画像復号技術を提供する。他の目的として、ＭＰＥＧとは異なる画像マッチング技術を利用する新しい動画像符号化および復号技術を提供する。さらに他の目的として、ＭＰＥＧ同様の画像マッチング技術を用いつつ、全体として異なる画像符号化および復号技術を提供する。【０００５】
本発明の画像符号化方法のある態様は、第１、第２の画像フレーム間の対応点情報をもとに補間計算によって中間画像フレームを生成する。この中間画像フレームと現実に存在する中間画像フレームとの差分が大きい場合、実際にそのような差分が大きい領域を画像内で特定する。つぎに、特定された領域に関する差分情報と、少なくとも第１または第２の画像フレームのデータと、対応点情報とを含む形で符号化データを生成する。復号技術は逆のプロセスをたどる。【０００６】
以上の各ステップを入れ替えたり、方法と装置の間で表現を一部または全部入れ替え、または追加したり、表現をコンピュータプログラム、記録媒体等に変更したものもまた、本発明として有効である。
【発明の効果】
【０００７】
本発明により、上記目的に対応する効果が得られる。
【図面の簡単な説明】
【０００８】
【図１】図１（ａ）と図１（ｂ）は、ふたりの人物の顔に平均化フィルタを施して得られる画像、図１（ｃ）と図１（ｄ）は、ふたりの人物の顔に関して前提技術で求められるｐ（５，０）の画像、図１（ｅ）と図１（ｆ）は、ふたりの人物の顔に関して前提技術で求められるｐ（５，１）の画像、図１（ｇ）と図１（ｈ）は、ふたりの人物の顔に関して前提技術で求められるｐ（５，２）の画像、図１（ｉ）と図１（ｊ）は、ふたりの人物の顔に関して前提技術で求められるｐ（５，３）の画像をそれぞれディスプレイ上に表示した中間調画像の写真である。
【図２】図２（Ｒ）はもとの四辺形を示す図、図２（Ａ）、図２（Ｂ）、図２（Ｃ）、図２（Ｄ）、図２（Ｅ）はそれぞれ相続四辺形を示す図である。
【図３】始点画像と終点画像の関係、および第ｍレベルと第ｍ−１レベルの関係を相続四辺形を用いて示す図である。
【図４】パラメータηとエネルギーＣｆの関係を示す図である。
【図５】図５（ａ）、図５（ｂ）は、ある点に関する写像が全単射条件を満たすか否かを外積計算から求める様子を示す図である。
【図６】前提技術の全体手順を示すフローチャートである。
【図７】図６のＳ１の詳細を示すフローチャートである。
【図８】図７のＳ１０の詳細を示すフローチャートである。
【図９】第ｍレベルの画像の一部と、第ｍ−１レベルの画像の一部の対応関係を示す図である。
【図１０】前提技術で生成された始点階層画像を示す図である。
【図１１】図６のＳ２に進む前に、マッチング評価の準備の手順を示す図である。
【図１２】図６のＳ２の詳細を示すフローチャートである。
【図１３】第０レベルにおいて副写像を決定する様子を示す図である。
【図１４】第１レベルにおいて副写像を決定する様子を示す図である。
【図１５】図１２のＳ２１の詳細を示すフローチャートである。
【図１６】あるｆ（ｍ，ｓ）についてλを変えながら求められたｆ（ｍ，ｓ）（λ＝ｉΔλ）に対応するエネルギーＣ（ｍ，ｓ）ｆの挙動を示す図である。
【図１７】ηを変えながら求められたｆ（ｎ）（η＝ｉΔη）（ｉ＝０，１，…）に対応するエネルギーＣ（ｎ）ｆの挙動を示す図である。
【図１８】改良後の前提技術において第ｍレベルにおける副写像を求めるフローチャートである。
【図１９】第１の実施の形態に係る画像符号化技術のフローおよび画像符号化装置の構成を示す図である。
【図２０】図２０（ａ）〜（ｃ）は、対象画像フレームの例を示す図である。
【図２１】第１の実施の形態に係る画像符号化技術のデータフォーマットを示す図である。
【図２２】第１の実施の形態に係る画像復号技術のフローおよび画像復号装置の構成を示す図である。
【図２３】第２の実施の形態に係る画像復号技術のフローおよび画像復号装置の構成を示す図である。
【図２４】第２の実施の形態に係る画像復号技術のフローおよび画像復号装置の構成を示す図である。
【図２５】実施の形態に係る図２３のＤＥ＋ＮＲの構成を示す図である。
【発明を実施するための最良の形態】
【０００９】
以下の実施の形態では、画像マッチング技術を用いる。この技術は本出願人が先に特許第２９２７３５０号にて提案した技術（以下「前提技術」という）を利用することができる。ただし、それ以外のマッチング技術を用いてもよい。以下、いずれの態様においても、いずれかの個所で述べた変形例や配慮は、別の個所における同様の技術に適用してもよいものとする。【００１０】
はじめに、実施の形態で利用する多重解像度特異点フィルタ技術とそれを用いた画像マッチング処理を「前提技術」として詳述する。【００１１】
[前提技術の実施の形態]
最初に［１］で前提技術の要素技術を詳述し、［２］で処理手順を具体的に説明する。さらに［３］で前提技術に基づき改良を施した点について述べる。
［１］要素技術の詳細
［１．１］イントロダクション
特異点フィルタと呼ばれる新たな多重解像度フィルタを導入し、画像間のマッチングを正確に計算する。オブジェクトに関する予備知識は一切不要である。画像間のマッチングの計算は、解像度の階層を進む間、各解像度において計算される。その際、粗いレベルから精細なレベルへと順に解像度の階層を辿っていく。計算に必要なパラメータは、人間の視覚システムに似た動的計算によって完全に自動設定される。画像間の対応点を人手で特定する必要はない。【００１２】
本前提技術は、例えば完全に自動的なモーフィング、物体認識、立体写真測量、ボリュームレンダリング、少ないフレームからの滑らかな動画像の生成などに応用できる。モーフィングに用いる場合、与えられた画像を自動的に変形することができる。ボリュームレンダリングに用いる場合、断面間の中間的な画像を正確に再構築することができる。断面間の距離が遠く、断面の形状が大きく変化する場合でも同様である。【００１３】
［１．２］特異点フィルタの階層
前提技術に係る多重解像度特異点フィルタは、画像の解像度を落としながら、しかも画像に含まれる各特異点の輝度及び位置を保存することができる。ここで画像の幅をＮ、高さをＭとする。以下簡単のため、Ｎ＝Ｍ＝２ｎ（ｎは自然数）と仮定する。また、区間［０，Ｎ］⊂ＲをＩと記述する。（ｉ，ｊ）における画像の画素をｐ（ｉ，ｊ）と記述する（ｉ，ｊ∈Ｉ）。【００１４】
ここで多重解像度の階層を導入する。階層化された画像群は多重解像度フィルタで生成される。多重解像度フィルタは、もとの画像に対して二次元的な探索を行って特異点を検出し、検出された特異点を抽出してもとの画像よりも解像度の低い別の画像を生成する。ここで第ｍレベルにおける各画像のサイズは２ｍ×２ｍ（０≦ｍ≦ｎ）とする。特異点フィルタは次の４種類の新たな階層画像をｎから下がる方向で再帰的に構築する。
【数１】
2007069350.tif 000003
ただしここで、
【数２】
2007069350.tif 000004
とする。以降これら４つの画像を副画像（サブイメージ）と呼ぶ。ｍｉｎｘ≦ｔ≦ｘ＋１、ｍａｘｘ≦ｔ≦ｘ＋１をそれぞれα及びβと記述すると、副画像はそれぞれ以下のように記述できる。【００１５】
Ｐ（ｍ，０）＝α（ｘ）α（ｙ）ｐ（ｍ＋１，０）
Ｐ（ｍ，１）＝α（ｘ）β（ｙ）ｐ（ｍ＋１，１）
Ｐ（ｍ，２）＝β（ｘ）α（ｙ）ｐ（ｍ＋１，２）
Ｐ（ｍ，３）＝β（ｘ）β（ｙ）ｐ（ｍ＋１，３）
すなわち、これらはαとβのテンソル積のようなものと考えられる。副画像はそれぞれ特異点に対応している。これらの式から明らかなように、特異点フィルタはもとの画像について２×２画素で構成されるブロックごとに特異点を検出する。その際、各ブロックのふたつの方向、つまり縦と横について、最大画素値または最小画素値をもつ点を探索する。画素値として、前提技術では輝度を採用するが、画像に関するいろいろな数値を採用することができる。ふたつの方向の両方について最大画素値となる画素は極大点、ふたつの方向の両方について最小画素値となる画素は極小点、ふたつの方向の一方について最大画素値となるとともに、他方について最小画素値となる画素は鞍点として検出される。【００１６】
特異点フィルタは、各ブロックの内部で検出された特異点の画像（ここでは１画素）でそのブロックの画像（ここでは４画素）を代表させることにより、画像の解像度を落とす。特異点の理論的な観点からすれば、α（ｘ）α（ｙ）は極小点を保存し、β（ｘ）β（ｙ）は極大点を保存し、α（ｘ）β（ｙ）及びβ（ｘ）α（ｙ）は鞍点を保存する。【００１７】
はじめに、マッチングをとるべき始点（ソース）画像と終点（デスティネーション）画像に対して別々に特異点フィルタ処理を施し、それぞれ一連の画像群、すなわち始点階層画像と終点階層画像を生成しておく。始点階層画像と終点階層画像は、特異点の種類に対応してそれぞれ４種類ずつ生成される。【００１８】
この後、一連の解像度レベルの中で始点階層画像と終点階層画像のマッチングがとれらていく。まずｐ（ｍ，０）を用いて極小点のマッチングがとられる。次に、その結果に基づき、ｐ（ｍ，１）を用いて鞍点のマッチングがとられ、ｐ（ｍ，２）を用いて他の鞍点のマッチングがとられる。そして最後にｐ（ｍ，３）を用いて極大点のマッチングがとられる。【００１９】
図１（ｃ）と図１（ｄ）はそれぞれ図１（ａ）と図１（ｂ）の副画像ｐ（５，０）を示している。同様に、図１（ｅ）と図１（ｆ）はｐ（５，１）、図１（ｇ）と図１（ｈ）はｐ（５，２）、図１（ｉ）と図１（ｊ）はｐ（５，３）をそれぞれ示している。これらの図からわかるとおり、副画像によれば画像の特徴部分のマッチングが容易になる。まずｐ（５，０）によって目が明確になる。目は顔の中で輝度の極小点だからである。ｐ（５，１）によれば口が明確になる。口は横方向で輝度が低いためである。ｐ（５，２）によれば首の両側の縦線が明確になる。最後に、ｐ（５，３）によって耳や頬の最も明るい点が明確になる。これらは輝度の極大点だからである。【００２０】
特異点フィルタによれば画像の特徴が抽出できるため、例えばカメラで撮影された画像の特徴と、予め記録しておいたいくつかのオブジェクトの特徴を比較することにより、カメラに映った被写体を識別することができる。【００２１】
［１．３］画像間の写像の計算
始点画像の位置（ｉ，ｊ）の画素をｐ（ｎ）（ｉ，ｊ）と書き、同じく終点画像の位置（ｋ，ｌ）の画素をｑ（ｎ）（ｋ，ｌ）で記述する。ｉ，ｊ，ｋ，ｌ∈Ｉとする。画像間の写像のエネルギー（後述）を定義する。このエネルギーは、始点画像の画素の輝度と終点画像の対応する画素の輝度の差、及び写像の滑らかさによって決まる。最初に最小のエネルギーを持つｐ（ｍ，０）とｑ（ｍ，０）間の写像ｆ（ｍ，０）：ｐ（ｍ，０）→ｑ（ｍ，０）が計算される。ｆ（ｍ，０）に基づき、最小エネルギーを持つｐ（ｍ，１）、ｑ（ｍ，１）間の写像ｆ（ｍ，１）が計算される。この手続は、ｐ（ｍ，３）とｑ（ｍ，３）の間の写像ｆ（ｍ，３）の計算が終了するまで続く。各写像ｆ（ｍ，ｉ）（ｉ＝０，１，２，…）を副写像と呼ぶことにする。ｆ（ｍ，ｉ）の計算の都合のために、ｉの順序は次式のように並べ替えることができる。並べ替えが必要な理由は後述する。【００２２】
【数３】
2007069350.tif 000005
ここでσ（ｉ）∈｛０，１，２，３｝である。【００２３】
［１．３．１］全単射
始点画像と終点画像の間のマッチングを写像で表現する場合、その写像は両画像間で全単射条件を満たすべきである。両画像に概念上の優劣はなく、互いの画素が全射かつ単射で接続されるべきだからである。しかしながら通常の場合とは異なり、ここで構築すべき写像は全単射のディジタル版である。前提技術では、画素は格子点によって特定される。【００２４】
始点副画像（始点画像について設けられた副画像）から終点副画像（終点画像について設けられた副画像）への写像は、ｆ（ｍ，ｓ）：Ｉ／２ｎ−ｍ×Ｉ／２ｎ−ｍ→Ｉ／２ｎ−ｍ×Ｉ／２ｎ−ｍ（ｓ＝０，１，…）によって表される。ここで、ｆ（ｍ，ｓ）（ｉ，ｊ）＝（ｋ，ｌ）は、始点画像のｐ（ｍ，ｓ）（ｉ，ｊ）が終点画像のｑ（ｍ，ｓ）（ｋ，ｌ）に写像されることを意味する。簡単のために、ｆ（ｉ，ｊ）＝（ｋ，ｌ）が成り立つとき画素ｑ（ｋ，ｌ）をｑｆ（ｉ，ｊ）と記述する。【００２５】
前提技術で扱う画素（格子点）のようにデータが離散的な場合、全単射の定義は重要である。ここでは以下のように定義する（ｉ，ｉ’，ｊ，ｊ’，ｋ，ｌは全て整数とする）。まず始めに、始点画像の平面においてＲによって表記される各正方形領域、
【数４】
2007069350.tif 000006
を考える（ｉ＝０，…，２ｍ−１、ｊ＝０，…，２ｍ−１）。ここでＲの各辺（エッジ）の方向を以下のように定める。
【数５】
2007069350.tif 000007
この正方形は写像ｆによって終点画像平面における四辺形に写像されなければならない。ｆ（ｍ，ｓ）（Ｒ）によって示される四辺形、
【数６】
2007069350.tif 000008
は、以下の全単射条件を満たす必要がある。【００２６】
１．四辺形ｆ（ｍ，ｓ）（Ｒ）のエッジは互いに交差しない。  
２．ｆ（ｍ，ｓ）（Ｒ）のエッジの方向はＲのそれらに等しい（図２の場合、時計回り）。  
３．緩和条件として収縮写像（リトラクション：retractions）を許す。【００２７】
何らかの緩和条件を設けないかぎり、全単射条件を完全に満たす写像は単位写像しかないためである。ここではｆ（ｍ，ｓ）（Ｒ）のひとつのエッジの長さが０、すなわちｆ（ｍ，ｓ）（Ｒ）は三角形になってもよい。しかし、面積が０となるような図形、すなわち１点または１本の線分になってはならない。図２（Ｒ）がもとの四辺形の場合、図２（Ａ）と図２（Ｄ）は全単射条件を満たすが、図２（Ｂ）、図２（Ｃ）、図２（Ｅ）は満たさない。【００２８】
実際のインプリメンテーションでは、写像が全射であることを容易に保証すべく、さらに以下の条件を課してもよい。つまり始点画像の境界上の各画素は、終点画像において同じ位置を占める画素に写影されるというものである。すなわち、ｆ（ｉ，ｊ）＝（ｉ，ｊ）（ただしｉ＝０，ｉ＝２ｍ−１，ｊ＝０，ｊ＝２ｍ−１の４本の線上）である。この条件を以下「付加条件」とも呼ぶ。【００２９】
［１．３．２］写像のエネルギー
［１．３．２．１］画素の輝度に関するコスト
写像ｆのエネルギーを定義する。エネルギーが最小になる写像を探すことが目的である。エネルギーは主に、始点画像の画素の輝度とそれに対応する終点画像の画素の輝度の差で決まる。すなわち、写像ｆ（ｍ，ｓ）の点（ｉ，ｊ）におけるエネルギーＣ（ｍ，ｓ）（ｉ，ｊ）は次式によって定まる。
【数７】
2007069350.tif 000009
ここで、Ｖ（ｐ（ｍ，ｓ）（ｉ，ｊ））及びＶ（ｑ（ｍ，ｓ）ｆ（ｉ，ｊ））はそれぞれ画素ｐ（ｍ，ｓ）（ｉ，ｊ）及びｑ（ｍ，ｓ）ｆ（ｉ，ｊ）の輝度である。ｆのトータルのエネルギーＣ（ｍ，ｓ）は、マッチングを評価するひとつの評価式であり、つぎに示すＣ（ｍ，ｓ）（ｉ，ｊ）の合計で定義できる。
【数８】
2007069350.tif 000010
［１．３．２．２］滑らかな写像のための画素の位置に関するコスト
滑らかな写像を得るために、写像に関する別のエネルギーＤｆを導入する。このエネルギーは画素の輝度とは関係なく、ｐ（ｍ，ｓ）（ｉ，ｊ）およびｑ（ｍ，ｓ）ｆ（ｉ，ｊ）の位置によって決まる（ｉ＝０，…，２ｍ−１，ｊ＝０，…，２ｍ−１）。点（ｉ，ｊ）における写像ｆ（ｍ，ｓ）のエネルギーＤ（ｍ，ｓ）（ｉ，ｊ）は次式で定義される。
【数９】
2007069350.tif 000011
ただし、係数パラメータηは０以上の実数であり、また、
【数１０】
2007069350.tif 000012
【数１１】
2007069350.tif 000013
とする。ここで、
【数１２】
2007069350.tif 000014
であり、ｉ’＜０およびｊ’＜０に対してｆ（ｉ’，ｊ’）は０と決める。Ｅ０は（ｉ，ｊ）及びｆ（ｉ，ｊ）の距離で決まる。Ｅ０は画素があまりにも離れた画素へ写影されることを防ぐ。ただしＥ０は、後に別のエネルギー関数で置き換える。Ｅ１は写像の滑らかさを保証する。Ｅ１は、ｐ（ｉ，ｊ）の変位とその隣接点の変位の間の隔たりを表す。以上の考察をもとに、マッチングを評価する別の評価式であるエネルギーＤｆは次式で定まる。
【数１３】
2007069350.tif 000015
［１．３．２．３］写像の総エネルギー
写像の総エネルギー、すなわち複数の評価式の統合に係る総合評価式はλＣ（ｍ，ｓ）ｆ＋Ｄ（ｍ，ｓ）ｆで定義される。ここで係数パラメータλは０以上の実数である。目的は総合評価式が極値をとる状態を検出すること、すなわち次式で示す最小エネルギーを与える写像を見いだすことである。
【数１４】
2007069350.tif 000016
λ＝０及びη＝０の場合、写像は単位写像になることに注意すべきである（すなわち、全てのｉ＝０，…，２ｍ−１及びｊ＝０，…，２ｍ−１に対してｆ（ｍ，ｓ）（ｉ，ｊ）＝（ｉ，ｊ）となる）。後述のごとく、本前提技術では最初にλ＝０及びη＝０の場合を評価するため、写像を単位写像から徐々に変形していくことができる。仮に総合評価式のλの位置を変えてＣ（ｍ，ｓ）ｆ＋λＤ（ｍ，ｓ）ｆと定義したとすれば、λ＝０及びη＝０の場合に総合評価式がＣ（ｍ，ｓ）ｆだけになり、本来何等関連のない画素どうしが単に輝度が近いというだけで対応づけられ、写像が無意味なものになる。そうした無意味な写像をもとに写像を変形していってもまったく意味をなさない。このため、単位写像が評価の開始時点で最良の写像として選択されるよう係数パラメータの与えかたが配慮されている。【００３０】
オプティカルフローもこの前提技術同様、画素の輝度の差と滑らかさを考慮する。しかし、オプティカルフローは画像の変換に用いることはできない。オブジェクトの局所的な動きしか考慮しないためである。前提技術に係る特異点フィルタを用いることによって大域的な対応関係を検出することができる。【００３１】
［１．３．３］多重解像度の導入による写像の決定
最小エネルギーを与え、全単射条件を満足する写像ｆｍｉｎを多重解像度の階層を用いて求める。各解像度レベルにおいて始点副画像及び終点副画像間の写像を計算する。解像度の階層の最上位（最も粗いレベル）からスタートし、各解像度レベルの写像を、他のレベルの写像を考慮に入れながら決定する。各レベルにおける写像の候補の数は、より高い、つまりより粗いレベルの写像を用いることによって制限される。より具体的には、あるレベルにおける写像の決定に際し、それよりひとつ粗いレベルにおいて求められた写像が一種の拘束条件として課される。【００３２】
まず、
【数１５】
2007069350.tif 000017
が成り立つとき、ｐ（ｍ−１，ｓ）（ｉ’，ｊ’）、ｑ（ｍ−１，ｓ）（ｉ’，ｊ’）をそれぞれｐ（ｍ，ｓ）（ｉ，ｊ）、ｑ（ｍ，ｓ）（ｉ，ｊ）のｐａｒｅｎｔと呼ぶことにする。［ｘ］はｘを越えない最大整数である。またｐ（ｍ，ｓ）（ｉ，ｊ）、ｑ（ｍ，ｓ）（ｉ，ｊ）をそれぞれｐ（ｍ−１，ｓ）（ｉ’，ｊ’）、ｑ（ｍ−１，ｓ）（ｉ’，ｊ’）のｃｈｉｌｄと呼ぶ。関数ｐａｒｅｎｔ（ｉ，ｊ）は次式で定義される。
【数１６】
2007069350.tif 000018
ｐ（ｍ，ｓ）（ｉ，ｊ）とｑ（ｍ，ｓ）（ｋ，ｌ）の間の写像ｆ（ｍ，ｓ）は、エネルギー計算を行って最小になったものを見つけることで決定される。ｆ（ｍ，ｓ）（ｉ，ｊ）＝（ｋ，ｌ）の値はｆ（ｍ−１，ｓ）（ｍ＝１，２，…，ｎ）を用いることによって、以下のように決定される。まず、ｑ（ｍ，ｓ）（ｋ，ｌ）は次の四辺形の内部になければならないという条件を課し、全単射条件を満たす写像のうち現実性の高いものを絞り込む。
【数１７】
2007069350.tif 000019
ただしここで、
【数１８】
2007069350.tif 000020
である。こうして定めた四辺形を、以下ｐ（ｍ，ｓ）（ｉ，ｊ）の相続（inherited）四辺形と呼ぶことにする。相続四辺形の内部において、エネルギーを最小にする画素を求める。【００３３】
図３は以上の手順を示している。同図において、始点画像のＡ，Ｂ，Ｃ，Ｄの画素は、第ｍ−１レベルにおいてそれぞれ終点画像のＡ’，Ｂ’，Ｃ’，Ｄ’へ写影される。画素ｐ（ｍ，ｓ）（ｉ，ｊ）は、相続四辺形Ａ’Ｂ’Ｃ’Ｄ’の内部に存在する画素ｑ（ｍ，ｓ）ｆ（ｍ）（ｉ，ｊ）へ写影されなければならない。以上の配慮により、第ｍ−１レベルの写像から第ｍレベルの写像への橋渡しがなされる。【００３４】
先に定義したエネルギーＥ０は、第ｍレベルにおける副写像ｆ（ｍ，０）を計算するために、次式に置き換える。
【数１９】
2007069350.tif 000021
また、副写像ｆ（ｍ，ｓ）を計算するためには次式を用いる。
【数２０】
2007069350.tif 000022
こうしてすべての副写像のエネルギーを低い値に保つ写像が得られる。式２０により、異なる特異点に対応する副写像が、副写像どうしの類似度が高くなるように同一レベル内で関連づけられる。式１９は、ｆ（ｍ，ｓ）（ｉ，ｊ）と、第ｍ−１レベルの画素の一部と考えた場合の（ｉ，ｊ）が射影されるべき点の位置との距離を示している。【００３５】
仮に、相続四辺形Ａ’Ｂ’Ｃ’Ｄ’の内部に全単射条件を満たす画素が存在しない場合は以下の措置をとる。まず、Ａ’Ｂ’Ｃ’Ｄ’の境界線からの距離がＬ（始めはＬ＝１）である画素を調べる。それらのうち、エネルギーが最小になるものが全単射条件を満たせば、これをｆ（ｍ，ｓ）（ｉ，ｊ）の値として選択する。そのような点が発見されるか、またはＬがその上限のＬ（ｍ）ｍａｘに到達するまで、Ｌを大きくしていく。Ｌ（ｍ）ｍａｘは各レベルｍに対して固定である。そのような点が全く発見されない場合、全単射の第３の条件を一時的に無視して変換先の四辺形の面積がゼロになるような写像も認め、ｆ（ｍ，ｓ）（ｉ，ｊ）を決定する。それでも条件を満たす点が見つからない場合、つぎに全単射の第１及び第２条件を外す。【００３６】
多重解像度を用いる近似法は、写像が画像の細部に影響されることを回避しつつ、画像間の大域的な対応関係を決定するために必須である。多重解像度による近似法を用いなければ、距離の遠い画素間の対応関係を見いだすことは不可能である。その場合、画像のサイズはきわめて小さなものに限定しなければならず、変化の小さな画像しか扱うことができない。さらに、通常写像に滑らかさを要求するため、そうした画素間の対応関係を見つけにくくしている。距離のある画素から画素への写像のエネルギーは高いためである。多重解像度を用いた近似法によれば、そうした画素間の適切な対応関係を見いだすことができる。それらの距離は、解像度の階層の上位レベル（粗いレベル）において小さいためである。【００３７】
［１．４］最適なパレメータ値の自動決定
既存のマッチング技術の主な欠点のひとつに、パレメータ調整の困難さがある。大抵の場合、パラメータの調整は人手作業によって行われ、最適な値を選択することはきわめて難しい。前提技術に係る方法によれば、最適なパラメータ値を完全に自動決定することができる。【００３８】
前提技術に係るシステムはふたつのパレメータ、λ及びηを含む。端的にいえば、λは画素の輝度の差の重みであり、ηは写像の剛性を示している。これらのパラメータの値は初期値が０であり、まずη＝０に固定してλを０から徐々に増加させる。λの値を大きくしながら、しかも総合評価式（式１４）の値を最小にする場合、各副写像に関するＣ（ｍ，ｓ）ｆの値は一般に小さくなっていく。このことは基本的にふたつの画像がよりマッチしなければならないことを意味する。しかし、λが最適値を超えると以下の現象が発生する。【００３９】
１．本来対応すべきではない画素どうしが、単に輝度が近いというだけで誤って対応づけられる。  
２．その結果、画素どうしの対応関係がおかしくなり、写像がくずれはじめる。【００４０】
３．その結果、式１４においてＤ（ｍ，ｓ）ｆが急激に増加しようとする。  
４．その結果、式１４の値が急激に増加しようとするため、Ｄ（ｍ，ｓ）ｆの急激な増加を抑制するようｆ（ｍ，ｓ）が変化し、その結果Ｃ（ｍ，ｓ）ｆが増加する。【００４１】
したがって、λを増加させながら式１４が最小値をとるという状態を維持しつつＣ（ｍ，ｓ）ｆが減少から増加に転じる閾値を検出し、そのλをη＝０における最適値とする。つぎにηを少しづつ増やしてＣ（ｍ，ｓ）ｆの挙動を検査し、後述の方法でηを自動決定する。そのηに対応してλも決まる。【００４２】
この方法は、人間の視覚システムの焦点機構の動作に似ている。人間の視覚システムでは、一方の目を動かしながら左右両目の画像のマッチングがとられる。オブジェクトがはっきりと認識できるとき、その目が固定される。【００４３】
［１．４．１］λの動的決定
λは０から所定の刻み幅で増加されていき、λの値が変わる度に副写像が評価される。式１４のごとく、総エネルギーはλＣ（ｍ，ｓ）ｆ＋Ｄ（ｍ，ｓ）ｆによって定義される。式９のＤ（ｍ，ｓ）ｆは滑らかさを表すもので、理論的には単位写像の場合に最小になり、写像が歪むほどＥ０もＥ１も増加していく。Ｅ１は整数であるから、Ｄ（ｍ，ｓ）ｆの最小刻み幅は１である。このため、現在のλＣ（ｍ，ｓ）（ｉ，ｊ）の変化（減少量）が１以上でなければ、写像を変化させることによって総エネルギーを減らすことはできない。なぜなら、写像の変化に伴ってＤ（ｍ，ｓ）ｆは１以上増加するため、λＣ（ｍ，ｓ）（ｉ，ｊ）が１以上減少しない限り総エネルギーは減らないためである。【００４４】
この条件のもと、λの増加に伴い、正常な場合にＣ（ｍ，ｓ）（ｉ，ｊ）が減少することを示す。Ｃ（ｍ，ｓ）（ｉ，ｊ）のヒストグラムをｈ（ｌ）と記述する。ｈ（ｌ）はエネルギーＣ（ｍ，ｓ）（ｉ，ｊ）がｌ２である画素の数である。λｌ２≧１が成り立つために、例えばｌ２＝１／λの場合を考える。λがλ１からλ２まで微小量変化するとき、  
【数２１】
2007069350.tif 000023
で示されるＡ個の画素が、  
【数２２】
2007069350.tif 000024
のエネルギーを持つより安定的な状態に変化する。ここでは仮に、これらの画素のエネルギーがすべてゼロになると近似している。この式はＣ（ｍ，ｓ）ｆの値が、  
【数２３】
2007069350.tif 000025
だけ変化することを示し、その結果、  
【数２４】
2007069350.tif 000026
が成立する。ｈ（ｌ）＞０であるから、通常Ｃ（ｍ，ｓ）ｆは減少する。しかし、λが最適値を越えようとするとき、上述の現象、つまりＣ（ｍ，ｓ）ｆの増加が発生する。この現象を検出することにより、λの最適値を決定する。【００４５】
なお、Ｈ（ｈ＞０）及びｋを定数とするとき、  
【数２５】
2007069350.tif 000027
と仮定すれば、  
【数２６】
2007069350.tif 000028
が成り立つ。このときｋ≠−３であれば、  
【数２７】
2007069350.tif 000029
となる。これがＣ（ｍ，ｓ）ｆの一般式である（Ｃは定数）。【００４６】
λの最適値を検出する際、さらに安全を見て、全単射条件を破る画素の数を検査してもよい。ここで各画素の写像を決定する際、全単射条件を破る確率をｐ０と仮定する。この場合、  
【数２８】
2007069350.tif 000030
が成立しているため、全単射条件を破る画素の数は次式の率で増加する。
【数２９】
2007069350.tif 000031
従って、  
【数３０】
2007069350.tif 000032
は定数である。仮にｈ（ｌ）＝Ｈｌｋを仮定するとき、例えば、  
【数３１】
2007069350.tif 000033
は定数になる。しかしλが最適値を越えると、上の値は急速に増加する。この現象を検出し、Ｂ０λ３／２＋ｋ／２／２ｍの値が異常値Ｂ０ｔｈｒｅｓを越えるかどうかを検査し、λの最適値を決定することができる。同様に、Ｂ１λ３／２＋ｋ／２／２ｍの値が異常値Ｂ１ｔｈｒｅｓを越えるかどうかを検査することにより、全単射の第３の条件を破る画素の増加率Ｂ１を確認する。ファクター２ｍを導入する理由は後述する。このシステムはこれら２つの閾値に敏感ではない。これらの閾値は、エネルギーＣ（ｍ，ｓ）ｆの観察では検出し損なった写像の過度の歪みを検出するために用いることができる。【００４７】
なお実験では、副写像ｆ（ｍ，ｓ）を計算する際、もしλが０．１を越えたらｆ（ｍ，ｓ）の計算は止めてｆ（ｍ，ｓ＋１）の計算に移行した。λ＞０．１のとき、画素の輝度２５５レベル中のわずか「３」の違いが副写像の計算に影響したためであり、λ＞０．１のとき正しい結果を得ることは困難だったためである。【００４８】
［１．４．２］ヒストグラムｈ（ｌ）
Ｃ（ｍ，ｓ）ｆの検査はヒストグラムｈ（ｌ）に依存しない。全単射及びその第３の条件の検査の際、ｈ（ｌ）に影響を受けうる。実際に（λ，Ｃ（ｍ，ｓ）ｆ）をプロットすると、ｋは通常１付近にある。実験ではｋ＝１を用い、Ｂ０λ２とＢ１λ２を検査した。仮にｋの本当の値が１未満であれば、Ｂ０λ２とＢ１λ２は定数にならず、ファクターλ（１−ｋ）／２に従って徐々に増加する。ｈ（ｌ）が定数であれば、例えばファクターはλ１／２である。しかし、こうした差は閾値Ｂ０ｔｈｒｅｓを正しく設定することによって吸収することができる。【００４９】
ここで次式のごとく始点画像を中心が（ｘ０，ｙ０）、半径ｒの円形のオブジェクトであると仮定する。  
【数３２】
2007069350.tif 000034
一方、終点画像は、次式のごとく中心（ｘ１，ｙ１）、半径がｒのオブジェクトであるとする。  
【数３３】
2007069350.tif 000035
ここでｃ（ｘ）はｃ（ｘ）＝ｘｋの形であるとする。中心（ｘ０，ｙ０）及び（ｘ１，ｙ１）が十分遠い場合、ヒストグラムｈ（ｌ）は次式の形となる。  
【数３４】
2007069350.tif 000036
ｋ＝１のとき、画像は背景に埋め込まれた鮮明な境界線を持つオブジェクトを示す。このオブジェクトは中心が暗く、周囲にいくに従って明るくなる。ｋ＝−１のとき、画像は曖昧な境界線を持つオブジェクトを表す。このオブジェクトは中心が最も明るく、周囲にいくに従って暗くなる。一般のオブジェクトはこれらふたつのタイプのオブジェクトの中間にあると考えてもさして一般性を失わない。したがって、ｋは−１≦ｋ≦１として大抵の場合をカバーでき、式２７が一般に減少関数であることが保障される。【００５０】
なお、式３４からわかるように、ｒは画像の解像度に影響されること、すなわちｒは２ｍに比例することに注意すべきである。このために［１．４．１］においてファクター２ｍを導入した。【００５１】
［１．４．３］ηの動的決定
パラメータηも同様の方法で自動決定できる。はじめにη＝０とし、最も細かい解像度における最終的な写像ｆ（ｎ）及びエネルギーＣ（ｎ）ｆを計算する。つづいて、ηをある値Δηだけ増加させ、再び最も細かい解像度における最終写像ｆ（ｎ）及びエネルギーＣ（ｎ）ｆを計算し直す。この過程を最適値が求まるまで続ける。ηは写像の剛性を示す。次式の重みだからである。
【数３５】
2007069350.tif 000037
ηが０のとき、Ｄ（ｎ）ｆは直前の副写像と無関係に決定され、現在の副写像は弾性的に変形され、過度に歪むことになる。一方、ηが非常に大きな値のとき、Ｄ（ｎ）ｆは直前の副写像によってほぼ完全に決まる。このとき副写像は非常に剛性が高く、画素は同じ場所に射影される。その結果、写像は単位写像になる。ηの値が０から次第に増えるとき、後述のごとくＣ（ｎ）ｆは徐々に減少する。しかしηの値が最適値を越えると、図４に示すとおり、エネルギーは増加し始める。同図のＸ軸はη、Ｙ軸はＣｆである。【００５２】
この方法でＣ（ｎ）ｆを最小にする最適なηの値を得ることができる。しかし、λの場合に比べていろいろな要素が計算に影響する結果、Ｃ（ｎ）ｆは小さく揺らぎながら変化する。λの場合は、入力が微小量変化するたびに副写像を１回計算しなおすだけだが、ηの場合はすべての副写像が計算しなおされるためである。このため、得られたＣ（ｎ）ｆの値が最小であるかどうかを即座に判断することはできない。最小値の候補が見つかれば、さらに細かい区間を設定することによって真の最小値を探す必要がある。【００５３】
［１．５］スーパーサンプリング
画素間の対応関係を決定する際、自由度を増やすために、ｆ（ｍ，ｓ）の値域をＲ×Ｒに拡張することができる（Ｒは実数の集合）。この場合、終点画像の画素の輝度が補間され、非整数点、  
【数３６】
2007069350.tif 000038
における輝度を持つｆ（ｍ，ｓ）が提供される。つまりスーパーサンプリングが行われる。実験では、ｆ（ｍ，ｓ）は整数及び半整数値をとることが許され、  
【数３７】
2007069350.tif 000039
は、  
【数３８】
2007069350.tif 000040
によって与えられた。【００５４】
［１．６］各画像の画素の輝度の正規化
始点画像と終点画像がきわめて異なるオブジェクトを含んでいるとき、写像の計算に元の画素の輝度がそのままでは利用しにくい。輝度の差が大きいために輝度に関するエネルギーＣ（ｍ，ｓ）ｆが大きくなりすぎ、正しい評価がしづらいためである。【００５５】
例えば、人の顔と猫の顔のマッチングをとる場合を考える。猫の顔は毛で覆われており、非常に明るい画素と非常に暗い画素が混じっている。この場合、ふたつの顔の間の副写像を計算するために、まず副画像を正規化する。すなわち、最も暗い画素の輝度を０、最も明るいそれを２５５に設定し、他の画素の輝度は線形補間によって求めておく。【００５６】
［１．７］インプリメンテーション
始点画像のスキャンに従って計算がリニアに進行する帰納的な方法を用いる。始めに、１番上の左端の画素（ｉ，ｊ）＝（０，０）についてｆ（ｍ，ｓ）の値を決定する。次にｉを１ずつ増やしながら各ｆ（ｍ，ｓ）（ｉ，ｊ）の値を決定する。ｉの値が画像の幅に到達したとき、ｊの値を１増やし、ｉを０に戻す。以降、始点画像のスキャンに伴いｆ（ｍ，ｓ）（ｉ，ｊ）を決定していく。すべての点について画素の対応が決まれば、ひとつの写像ｆ（ｍ，ｓ）が決まる。
あるｐ（ｉ，ｊ）について対応点ｑｆ（ｉ，ｊ）が決まれば、つぎにｐ（ｉ，ｊ＋１）の対応点ｑｆ（ｉ，ｊ＋１）が決められる。この際、ｑｆ（ｉ，ｊ＋１）の位置は全単射条件を満たすために、ｑｆ（ｉ，ｊ）の位置によって制限される。したがって、先に対応点が決まる点ほどこのシステムでは優先度が高くなる。つねに（０，０）が最も優先される状態がつづくと、求められる最終の写像に余計な偏向が加わる。本前提技術ではこの状態を回避するために、ｆ（ｍ，ｓ）を以下の方法で決めていく。【００５７】
まず（ｓ ｍｏｄ ４）が０の場合、（０，０）を開始点としｉ及びｊを徐々に増やしながら決めていく。（ｓ ｍｏｄ ４）が１の場合、最上行の右端点を開始点とし、ｉを減少、ｊを増加させながら決めていく。（ｓ ｍｏｄ ４）が２のとき、最下行の右端点を開始点とし、ｉ及びｊを減少させながら決めていく。（ｓ ｍｏｄ ４）が３の場合、最下行の左端点を開始点とし、ｉを増加、ｊを減少させながら決めていく。解像度が最も細かい第ｎレベルには副写像という概念、すなわちパラメータｓが存在しないため、仮にｓ＝０及びｓ＝２であるとしてふたつの方向を連続的に計算した。【００５８】
実際のインプリメンテーションでは、全単射条件を破る候補に対してペナルティを与えることにより、候補（ｋ，ｌ）の中からできる限り全単射条件を満たすｆ（ｍ，ｓ）（ｉ，ｊ）（ｍ＝０，…，ｎ）の値を選んだ。第３の条件を破る候補のエネルギーＤ（ｋ、ｌ）にはφを掛け、一方、第１または第２の条件を破る候補にはψを掛ける。今回はφ＝２、ψ＝１０００００を用いた。【００５９】
前述の全単射条件のチェックのために、実際の手続として（ｋ，ｌ）＝ｆ（ｍ，ｓ）（ｉ，ｊ）を決定する際に以下のテストを行った。すなわちｆ（ｍ，ｓ）（ｉ，ｊ）の相続四辺形に含まれる各格子点（ｋ，ｌ）に対し、次式の外積のｚ成分が０以上になるかどうかを確かめる。
【数３９】
2007069350.tif 000041
ただしここで、  
【数４０】
2007069350.tif 000042
【数４１】
2007069350.tif 000043
である（ここでベクトルは三次元ベクトルとし、ｚ軸は直交右手座標系において定義される）。もしＷが負であれば、その候補についてはＤ（ｍ，ｓ）（ｋ，ｌ）にψを掛けることによってペナルティを与え、できるかぎり選択しないようにする。【００６０】
図５（ａ）、図５（ｂ）はこの条件を検査する理由を示している。図５（ａ）はペナルティのない候補、図５（ｂ）はペナルティがある候補をそれぞれ表す。隣接画素（ｉ，ｊ＋１）に対する写像ｆ（ｍ，ｓ）（ｉ，ｊ＋１）を決定する際、Ｗのｚ成分が負であれば始点画像平面上において全単射条件を満足する画素は存在しない。なぜなら、ｑ（ｍ，ｓ）（ｋ，ｌ）は隣接する四辺形の境界線を越えるためである。【００６１】
［１．７．１］副写像の順序
インプリメンテーションでは、解像度レベルが偶数のときにはσ（０）＝０、σ（１）＝１、σ（２）＝２、σ（３）＝３、σ（４）＝０を用い、奇数のときはσ（０）＝３、σ（１）＝２、σ（２）＝１、σ（３）＝０、σ（４）＝３を用いた。このことで、副写像を適度にシャッフルした。なお、本来副写像は４種類であり、ｓは０〜３のいずれかである。しかし、実際にはｓ＝４に相当する処理を行った。その理由は後述する。【００６２】
［１．８］補間計算
始点画像と終点画像の間の写像が決定された後、対応しあう画素の輝度が補間される。実験では、トライリニア補間を用いた。始点画像平面における正方形ｐ（ｉ，ｊ）ｐ（ｉ＋１，ｊ）ｐ（ｉ，ｊ＋１）ｐ（ｉ＋１，ｊ＋１）が終点画像平面上の四辺形ｑｆ（ｉ，ｊ）ｑｆ（ｉ＋１，ｊ）ｑｆ（ｉ，ｊ＋１）ｑｆ（ｉ＋１，ｊ＋１）に射影されると仮定する。簡単のため、画像間の距離を１とする。始点画像平面からの距離がｔ（０≦ｔ≦１）である中間画像の画素ｒ（ｘ，ｙ，ｔ）（０≦ｘ≦Ｎ−１，０≦ｙ≦Ｍ−１）は以下の要領で求められる。まず画素ｒ（ｘ，ｙ，ｔ）の位置（ただしｘ，ｙ，ｔ∈Ｒ）を次式で求める。
【数４２】
2007069350.tif 000044
つづいてｒ（ｘ，ｙ，ｔ）における画素の輝度が次の式を用いて決定される。
【数４３】
2007069350.tif 000045
ここでｄｘ及びｄｙはパラメータであり、０から１まで変化する。【００６３】
［１．９］拘束条件を課したときの写像
いままでは拘束条件がいっさい存在しない場合の写像の決定を述べた。しかし、始点画像と終点画像の特定の画素間に予め対応関係が規定されているとき、これを拘束条件としたうえで写像を決定することができる。【００６４】
基本的な考えは、まず始点画像の特定の画素を終点画像の特定の画素に移す大まかな写像によって始点画像を大まかに変形し、しかる後、写像ｆを正確に計算する。【００６５】
まず始めに、始点画像の特定の画素を終点画像の特定の画素に射影し、始点画像の他の画素を適当な位置に射影する大まかな写像を決める。すなわち、特定の画素に近い画素は、その特定の画素が射影される場所の近くに射影されるような写像である。ここで第ｍレベルの大まかな写像をＦ（ｍ）と記述する。【００６６】
大まかな写像Ｆは以下の要領で決める。まず、いくつかの画素について写像を特定する。始点画像についてｎｓ個の画素、  
【数４４】
2007069350.tif 000046
を特定するとき、以下の値を決める。  
【数４５】
2007069350.tif 000047
始点画像の他の画素の変位量は、ｐ（ｉｈ，ｊｈ）（ｈ＝０，…，ｎｓ−１）の変位に重み付けをして求められる平均である。すなわち画素ｐ（ｉ，ｊ）は、終点画像の以下の画素に射影される。
【数４６】
2007069350.tif 000048
ただしここで、  
【数４７】
2007069350.tif 000049
【数４８】
2007069350.tif 000050
とする。【００６７】
つづいて、Ｆ（ｍ）に近い候補写像ｆがより少ないエネルギーを持つように、その写像ｆのエネルギーＤ（ｍ，ｓ）（ｉ，ｊ）を変更する。正確には、Ｄ（ｍ，ｓ）（ｉ，ｊ）は、  
【数４９】
2007069350.tif 000051
である。ただし、  
【数５０】
2007069350.tif 000052
であり、κ，ρ≧０とする。最後に、前述の写像の自動計算プロセスにより、ｆを完全に決定する。【００６８】
ここで、ｆ（ｍ，ｓ）（i,j)がＦ（ｍ）（i,j）に十分近いとき、つまりそれらの距離が、  
【数５１】
2007069350.tif 000053
以内であるとき、Ｅ２（ｍ，ｓ）（ｉ，ｊ）が０になることに注意すべきである。そのように定義した理由は、各ｆ（ｍ，ｓ）（i,j）がＦ（ｍ）（i,j）に十分近い限り、終点画像において適切な位置に落ち着くよう、その値を自動的に決めたいためである。この理由により、正確な対応関係を詳細に特定する必要がなく、始点画像は終点画像にマッチするように自動的にマッピングされる。
［２］具体的な処理手順
［１］の各要素技術による処理の流れを説明する。    
図６は前提技術の全体手順を示すフローチャートである。同図のごとく、まず多重解像度特異点フィルタを用いた処理を行い（Ｓ１）、つづいて始点画像と終点画像のマッチングをとる（Ｓ２）。ただし、Ｓ２は必須ではなく、Ｓ１で得られた画像の特徴をもとに画像認識などの処理を行ってもよい。【００６９】
図７は図６のＳ１の詳細を示すフローチャートである。ここではＳ２で始点画像と終点画像のマッチングをとることを前提としている。そのため、まず特異点フィルタによって始点画像の階層化を行い（Ｓ１０）、一連の始点階層画像を得る。つづいて同様の方法で終点画像の階層化を行い（Ｓ１１）、一連の終点階層画像を得る。ただし、Ｓ１０とＳ１１の順序は任意であるし、始点階層画像と終点階層画像を並行して生成していくこともできる。【００７０】
図８は図７のＳ１０の詳細を示すフローチャートである。もとの始点画像のサイズは２ｎ×２ｎとする。始点階層画像は解像度が細かいほうから順に作られるため、処理の対象となる解像度レベルを示すパラメータｍをｎにセットする（Ｓ１００）。つづいて第ｍレベルの画像ｐ（ｍ，０）、ｐ（ｍ，１）、ｐ（ｍ，２）、ｐ（ｍ，３）から特異点フィルタを用いて特異点を検出し（Ｓ１０１）、それぞれ第ｍ−１レベルの画像ｐ（ｍ−１，０）、ｐ（ｍ−１，１）、ｐ（ｍ−１，２）、ｐ（ｍ−１，３）を生成する（Ｓ１０２）。ここではｍ＝ｎであるため、ｐ（ｍ，０）＝ｐ（ｍ，１）＝ｐ（ｍ，２）＝ｐ（ｍ，３）＝ｐ（ｎ）であり、ひとつの始点画像から４種類の副画像が生成される。【００７１】
図９は第ｍレベルの画像の一部と、第ｍ−１レベルの画像の一部の対応関係を示している。同図の数値は各画素の輝度を示す。同図のｐ（ｍ，ｓ）はｐ（ｍ，０）〜ｐ（ｍ，３）の４つの画像を象徴するもので、ｐ（ｍ−１，０）を生成する場合には、ｐ（ｍ，ｓ）はｐ（ｍ，０）であると考える。［１．２］で示した規則により、ｐ（ｍ−１，０）は例えば同図で輝度を記入したブロックについて、そこに含まれる４画素のうち「３」、ｐ（ｍ−１，１）は「８」、ｐ（ｍ−１，２）は「６」、ｐ（ｍ−１，３）を「１０」をそれぞれ取得し、このブロックをそれぞれ取得したひとつの画素で置き換える。したがって、第ｍ−１レベルの副画像のサイズは２ｍ−１×２ｍ−１になる。【００７２】
つづいてｍをデクリメントし（図８のＳ１０３）、ｍが負になっていないことを確認し（Ｓ１０４）、Ｓ１０１に戻ってつぎに解像度の粗い副画像を生成していく。この繰り返し処理の結果、ｍ＝０、すなわち第０レベルの副画像が生成された時点でＳ１０が終了する。第０レベルの副画像のサイズは１×１である。【００７３】
図１０はＳ１０によって生成された始点階層画像をｎ＝３の場合について例示している。最初の始点画像のみが４つの系列に共通であり、以降特異点の種類に応じてそれぞれ独立に副画像が生成されていく。なお、図８の処理は図７のＳ１１にも共通であり、同様の手順を経て終点階層画像も生成される。以上で図６のＳ１による処理が完了する。【００７４】
前提技術では、図６のＳ２に進むためにマッチング評価の準備をする。図１１はその手順を示している。同図のごとく、まず複数の評価式が設定される（Ｓ３０）。［１．３．２．１］で導入した画素に関するエネルギーＣ（ｍ，ｓ）ｆと［１．３．２．２］で導入した写像の滑らかさに関するエネルギーＤ（ｍ，ｓ）ｆがそれである。つぎに、これらの評価式を統合して総合評価式を立てる（Ｓ３１）。［１．３．２．３］で導入した総エネルギーλＣ（ｍ，ｓ）ｆ＋Ｄ（ｍ，ｓ）ｆがそれであり、［１．３．２．２］で導入したηを用いれば、
【数５２】
2007069350.tif 000054
となる。ただし、総和はｉ、ｊについてそれぞれ０、１…、２ｍ−１で計算する。以上でマッチング評価の準備が整う。【００７５】
図１２は図６のＳ２の詳細を示すフローチャートである。［１］で述べたごとく、始点階層画像と終点階層画像のマッチングは互いに同じ解像度レベルの画像どうしでとられる。画像間の大域的なマッチングを良好にとるために、解像度が粗いレベルから順にマッチングを計算する。特異点フィルタを用いて始点階層画像および終点階層画像を生成しているため、特異点の位置や輝度は解像度の粗いレベルでも明確に保存されており、大域的なマッチングの結果は従来に比べて非常に優れたものになる。【００７６】
図１２のごとく、まず係数パラメータηを０、レベルパラメータｍを０に設定する（Ｓ２０）。つづいて、始点階層画像中の第ｍレベルの４つの副画像と終点階層画像中の第ｍレベルの４つの副画像のそれぞれの間でマッチングを計算し、それぞれ全単射条件を満たし、かつエネルギーを最小にするような４種類の副写像ｆ（ｍ，ｓ）（ｓ＝０，１，２，３）を求める（Ｓ２１）。全単射条件は［１．３．３］で述べた相続四辺形を用いて検査される。この際、式１７、１８が示すように、第ｍレベルにおける副写像は第ｍ−１レベルのそれらに拘束されるため、より解像度の粗いレベルにおけるマッチングが順次利用されていく。これは異なるレベル間の垂直的参照である。なお、いまｍ＝０であってそれより粗いレベルはないが、この例外的な処理は図１３で後述する。
一方、同一レベル内における水平的参照も行われる。［１．３．３］の式２０のごとく、ｆ（ｍ，３）はｆ（ｍ，２）に、ｆ（ｍ，２）はｆ（ｍ，１）に、ｆ（ｍ，１）はｆ（ｍ，０）に、それぞれ類似するように決める。その理由は、特異点の種類が違っても、それらがもともと同じ始点画像と終点画像に含まれている以上、副写像がまったく異なるという状況は不自然だからである。式２０からわかるように、副写像どうしが近いほどエネルギーは小さくなり、マッチングが良好とみなされる。【００７７】
なお、最初に決めるべきｆ（ｍ，０）については同一のレベルで参照できる副写像がないため、式１９に示すごとくひとつ粗いレベルを参照する。ただし、実験ではｆ（ｍ，３）まで求まった後、これを拘束条件としてｆ（ｍ，０）を一回更新するという手続をとった。これは式２０にｓ＝４を代入し、ｆ（ｍ，４）を新たなｆ（ｍ，０）とすることに等しい。ｆ（ｍ，０）とｆ（ｍ，３）の関連度が低くなり過ぎる傾向を回避するためであり、この措置によって実験結果がより良好になった。この措置に加え、実験では［１．７．１］に示す副写像のシャッフルも行った。これも本来特異点の種類ごとに決まる副写像どうしの関連度を密接に保つ趣旨である。また、処理の開始点に依存する偏向を回避するために、ｓの値にしたがって開始点の位置を変える点は［１．７］で述べたとおりである。【００７８】
図１３は第０レベルにおいて副写像を決定する様子を示す図である。第０レベルでは各副画像がただひとつの画素で構成されるため、４つの副写像ｆ（０，ｓ）はすべて自動的に単位写像に決まる。図１４は第１レベルにおいて副写像を決定する様子を示す図である。第１レベルでは副画像がそれぞれ４画素で構成される。同図ではこれら４画素が実線で示されている。いま、ｐ（１，ｓ）の点ｘの対応点をｑ（１，ｓ）の中で探すとき、以下の手順を踏む。【００７９】
１．第１レベルの解像度で点ｘの左上点ａ、右上点ｂ、左下点ｃ、右下点ｄを求める。  
２．点ａ〜ｄがひとつ粗いレベル、つまり第０レベルにおいて属する画素を探す。図１４の場合、点ａ〜ｄはそれぞれ画素Ａ〜Ｄに属する。ただし、画素Ａ〜Ｃは本来存在しない仮想的な画素である。  
３．第０レベルですでに求まっている画素Ａ〜Ｄの対応点Ａ’〜Ｄ’をｑ（１，ｓ）の中にプロットする。画素Ａ’〜Ｃ’は仮想的な画素であり、それぞれ画素Ａ〜Ｃと同じ位置にあるものとする。  
４．画素Ａの中の点ａの対応点ａ’が画素Ａ’の中にあるとみなし、点ａ’をプロットする。このとき、点ａが画素Ａの中で占める位置（この場合、右下）と、点ａ’が画素Ａ’の中で占める位置が同じであると仮定する。  
５．４と同様の方法で対応点ｂ’〜ｄ’をプロットし、点ａ’〜ｄ’で相続四辺形を作る。  
６．相続四辺形の中でエネルギーが最小になるよう、点ｘの対応点ｘ’を探す。対応点ｘ’の候補として、例えば画素の中心が相続四辺形に含まれるものに限定してもよい。図１４の場合、４つの画素がすべて候補になる。【００８０】
以上がある点ｘの対応点の決定手順である。同様の処理を他のすべての点について行い、副写像を決める。第２レベル以上のレベルでは、次第に相続四辺形の形が崩れていくと考えられるため、図３に示すように画素Ａ’〜Ｄ’の間隔が空いていく状況が発生する。【００８１】
こうして、ある第ｍレベルの４つの副写像が決まれば、ｍをインクリメントし（図１２のＳ２２）、ｍがｎを超えていないことを確かめて（Ｓ２３）、Ｓ２１に戻る。以下、Ｓ２１に戻るたびに次第に細かい解像度のレベルの副写像を求め、最後にＳ２１に戻ったときに第ｎレベルの写像ｆ（ｎ）を決める。この写像はη＝０に関して定まったものであるから、ｆ（ｎ）（η＝０）と書く。【００８２】
つぎに異なるηに関する写像も求めるべく、ηをΔηだけシフトし、ｍをゼロクリアする（Ｓ２４）。新たなηが所定の探索打切り値ηｍａｘを超えていないことを確認し（Ｓ２５）、Ｓ２１に戻り、今回のηに関して写像ｆ（ｎ）（η＝Δη）を求める。この処理を繰り返し、Ｓ２１でｆ（ｎ）（η＝ｉΔη）（ｉ＝０，１，…）を求めていく。ηがηｍａｘを超えたときＳ２６に進み、後述の方法で最適なη＝ηｏｐｔを決定し、ｆ（ｎ）（η＝ηｏｐｔ）を最終的に写像ｆ（ｎ）とする。【００８３】
図１５は図１２のＳ２１の詳細を示すフローチャートである。このフローチャートにより、ある定まったηについて、第ｍレベルにおける副写像が決まる。副写像を決める際、前提技術では副写像ごとに最適なλを独立して決める。【００８４】
同図のごとく、まずｓとλをゼロクリアする（Ｓ２１０）。つぎに、そのときのλについて（および暗にηについて）エネルギーを最小にする副写像ｆ（ｍ，ｓ）を求め（Ｓ２１１）、これをｆ（ｍ，ｓ）（λ＝０）と書く。異なるλに関する写像も求めるべく、λをΔλだけシフトし、新たなλが所定の探索打切り値λｍａｘを超えていないことを確認し（Ｓ２１３）、Ｓ２１１に戻り、以降の繰り返し処理でｆ（ｍ，ｓ）（λ＝ｉΔλ）（ｉ＝０，１，…）を求める。λがλｍａｘを超えたときＳ２１４に進み、最適なλ＝λｏｐｔを決定し、ｆ（ｍ，ｓ）（λ＝λｏｐｔ）を最終的に写像ｆ（ｍ，ｓ）とする（Ｓ２１４）。【００８５】
つぎに、同一レベルにおける他の副写像を求めるべく、λをゼロクリアし、ｓをインクリメントする（Ｓ２１５）。ｓが４を超えていないことを確認し（Ｓ２１６）、Ｓ２１１に戻る。ｓ＝４になれば上述のごとくｆ（ｍ，３）を利用してｆ（ｍ，０）を更新し、そのレベルにおける副写像の決定を終了する。【００８６】
図１６は、あるｍとｓについてλを変えながら求められたｆ（ｍ，ｓ）（λ＝ｉΔλ）（ｉ＝０，１，…）に対応するエネルギーＣ（ｍ，ｓ）ｆの挙動を示す図である。［１．４］で述べたとおり、λが増加すると通常Ｃ（ｍ，ｓ）ｆは減少する。しかし、λが最適値を超えるとＣ（ｍ，ｓ）ｆは増加に転じる。そこで本前提技術ではＣ（ｍ，ｓ）ｆが極小値をとるときのλをλｏｐｔと決める。同図のようにλ＞λｏｐｔの範囲で再度Ｃ（ｍ，ｓ）ｆが小さくなっていっても、その時点ではすでに写像がくずれていて意味をなさないため、最初の極小点に注目すればよい。λｏｐｔは副写像ごとに独立して決めていき、最後にｆ（ｎ）についてもひとつ定まる。【００８７】
一方、図１７は、ηを変えながら求められたｆ（ｎ）（η＝ｉΔη）（ｉ＝０，１，…）に対応するエネルギーＣ（ｎ）ｆの挙動を示す図である。ここでもηが増加すると通常Ｃ（ｎ）ｆは減少するが、ηが最適値を超えるとＣ（ｎ）ｆは増加に転じる。そこでＣ（ｎ）ｆが極小値をとるときのηをηｏｐｔと決める。図１７は図４の横軸のゼロ付近を拡大した図と考えてよい。ηｏｐｔが決まればｆ（ｎ）を最終決定することができる。【００８８】
以上、本前提技術によれば種々のメリットが得られる。まずエッジを検出する必要がないため、エッジ検出タイプの従来技術の課題を解消できる。また、画像に含まれるオブジェクトに対する先験的な知識も不要であり、対応点の自動検出が実現する。特異点フィルタによれば、解像度の粗いレベルでも特異点の輝度や位置を維持することができ、オブジェクト認識、特徴抽出、画像マッチングに極めて有利である。その結果、人手作業を大幅に軽減する画像処理システムの構築が可能となる。【００８９】
なお、本前提技術について次のような変形技術も考えられる。  
（１）前提技術では始点階層画像と終点階層画像の間でマッチングをとる際にパラメータの自動決定を行ったが、この方法は階層画像間ではなく、通常の２枚の画像間のマッチングをとる場合全般に利用できる。【００９０】
たとえば２枚の画像間で、画素の輝度の差に関するエネルギーＥ０と画素の位置的なずれに関するエネルギーＥ１のふたつを評価式とし、これらの線形和Ｅｔｏｔ＝αＥ０＋Ｅ１を総合評価式とする。この総合評価式の極値付近に注目してαを自動決定する。つまり、いろいろなαについてＥｔｏｔが最小になるような写像を求める。それらの写像のうち、αに関してＥ１が極小値をとるときのαを最適パラメータと決める。そのパラメータに対応する写像を最終的に両画像間の最適マッチングとみなす。【００９１】
これ以外にも評価式の設定にはいろいろな方法があり、例えば１／Ｅ１と１／Ｅ２のように、評価結果が良好なほど大きな値をとるものを採用してもよい。総合評価式も必ずしも線形和である必要はなく、ｎ乗和（ｎ＝２、１／２、−１、−２など）、多項式、任意の関数などを適宜選択すればよい。【００９２】
パラメータも、αのみ、前提技術のごとくηとλのふたつの場合、それ以上の場合など、いずれでもよい。パラメータが３以上の場合はひとつずつ変化させて決めていく。
（２）本前提技術では、総合評価式の値が最小になるよう写像を決めた後、総合評価式を構成するひとつの評価式であるＣ（ｍ，ｓ）ｆが極小になる点を検出してパラメータを決定した。しかし、こうした二段回処理の代わりに、状況によっては単に総合評価式の最小値が最小になるようにパラメータを決めても効果的である。その場合、例えばαＥ０＋βＥ１を総合評価式とし、α＋β＝１なる拘束条件を設けて各評価式を平等に扱うなどの措置を講じてもよい。パラメータの自動決定の本質は、エネルギーが最小になるようにパラメータを決めていく点にあるからである。
（３）前提技術では各解像度レベルで４種類の特異点に関する４種類の副画像を生成した。しかし、当然４種類のうち１、２、３種類を選択的に用いてもよい。例えば、画像中に明るい点がひとつだけ存在する状態であれば、極大点に関するｆ（ｍ，３）だけで階層画像を生成しても相応の効果が得られるはずである。その場合、同一レベルで異なる副写像は不要になるため、ｓに関する計算量が減る効果がある。
（４）本前提技術では特異点フィルタによってレベルがひとつ進むと画素が１／４になった。例えば３×３で１ブロックとし、その中で特異点を探す構成も可能であり、その場合、レベルがひとつ進むと画素は１／９になる。
（５）始点画像と終点画像がカラーの場合、それらをまず白黒画像に変換し、写像を計算する。その結果求められた写像を用いて始点のカラー画像を変換する。それ以外の方法として、ＲＧＢの各成分について副写像を計算してもよい。
［３］前提技術の改良点
以上の前提技術を基本とし、マッチング精度を向上させるためのいくつかの改良がなされている。ここではその改良点を述べる。【００９３】
［３．１］色情報を考慮に入れた特異点フィルタおよび副画像
画像の色情報を有効に用いるために、特異点フィルタを以下のように変更した。まず色空間としては、人間の直感に最も合致するといわれているＨＩＳを用い、色を輝度に変換する式には、人間の目の感度に最も近いといわれているものを選んだ。
【数５３】
2007069350.tif 000055
ここで画素ａにおけるＹ（輝度）をＹ(ａ)として、次のような記号を定義する。
【数５４】
2007069350.tif 000056
上の定義を用いて以下のような５つのフィルタを用意する。
【数５５】
2007069350.tif 000057
このうち上から４つのフィルタは改良前の前提技術におけるフィルタとほぼ同じで、輝度の特異点を色情報も残しながら保存する。最後のフィルタは色の彩度の特異点をこちらも色情報を残しながら保存する。【００９４】
これらのフィルタによって、各レベルにつき５種類の副画像（サブイメージ）が生成される。なお、最も高いレベルの副画像は元画像に一致する。
【数５６】
2007069350.tif 000058
［３．２］エッジ画像およびその副画像
輝度微分（エッジ）の情報をマッチングに利用するため、一次微分エッジ検出フィルタを用いる。このフィルタはあるオペレータＨとの畳み込み積分で実現できる。
【数５７】
2007069350.tif 000059
ここでＨは演算スピードなども考慮し、以下のようなオペレータを用いた。
【数５８】
2007069350.tif 000060
次にこの画像を多重解像度化する。フィルタにより０を中心とした輝度をもつ画像が生成されるため、次のような平均値画像が副画像としては最も適切である。
【数５９】
2007069350.tif 000061
式５９の画像は後述するForward Stage、すなわち初回副写像導出ステージの計算の際、エネルギー関数に用いられる。【００９５】
エッジの大きさ、すなわち絶対値も計算に必要である。
【数６０】
2007069350.tif 000062
この値は常に正であるため、多重解像度化には最大値フィルタを用いる。
【数６１】
2007069350.tif 000063
式６１の画像は後述するForward Stageの計算の際、計算する順序を決定するのに用いられる。【００９６】
［３．３］計算処理手順
計算は最も粗い解像度の副画像から順に行う。副画像は５つあるため、各レベルの解像度において計算は複数回行われる。これをターンと呼び、最大計算回数をｔで表すことにする。各ターンは前記Forward Stageと、副写像再計算ステージであるRefinement Stageという二つのエネルギー最小化計算から構成される。図１８は第ｍレベルにおける副写像を決める計算のうち改良点に係るフローチャートである。【００９７】
同図のごとく、sをゼロクリアする（Ｓ４０）。つぎにForward Stage（Ｓ４１）において始点画像ｐから終点画像ｑへの写像ｆ(ｍ，ｓ)をエネルギー最小化によって求める。ここで最小化するエネルギーは、対応する画素値によるエネルギーＣと、写像の滑らかさによるエネルギーＤの線形和である。【００９８】
エネルギーＣは、輝度の差によるエネルギーＣＩ（前記改良前の前提技術におけるエネルギーＣと等価）と、色相、彩度によるエネルギーＣＣ、輝度微分（エッジ）の差によるエネルギーＣＥで構成され、それぞれ次のように表される。
【数６２】
2007069350.tif 000064
エネルギーＤは前記改良前の前提技術と同じものを用いる。ただし前記改良前の前提技術において、写像の滑らかさを保証するエネルギーＥ１を導出する際、隣接する画素のみを考慮していたが、周囲の何画素を考慮するかをパラメータｄで指定できるように改良した。
【数６３】
2007069350.tif 000065
次のRefinement Stageに備えて、このステージでは終点画像ｑから始点画像ｐへの写像ｇ（ｍ，ｓ）も同様に計算する。【００９９】
Refinement Stage（Ｓ４２）ではForward Stageにおいて求めた双方向の写像ｆ（ｍ，ｓ）およびｇ（ｍ，ｓ）を基に、より妥当な写像ｆ’（ｍ，ｓ）を求める。ここでは新たに定義されるエネルギーＭについてエネルギー最小化計算を行う。エネルギーＭは終点画像から始点画像への写像ｇとの整合度Ｍ０と、もとの写像との差Ｍ１より構成される。
【数６４】
2007069350.tif 000066
対称性を損なわないように、終点画像ｑから始点画像ｐへの写像ｇ’（ｍ，ｓ）も同様の方法で求めておく。【０１００】
その後、ｓをインクリメントし（Ｓ４３）、ｓがｔを超えていないことを確認し（Ｓ４４）、次のターンのForward Stage（Ｓ４１）に進む。その際前記Ｅ０を次のように置き換えてエネルギー最小化計算を行う。
【数６５】
2007069350.tif 000067
［３．４］写像の計算順序
写像の滑らかさを表すエネルギーＥ１を計算する際、周囲の点の写像を用いるため、それらの点がすでに計算されているかどうかがエネルギーに影響を与える。すなわち、どの点から順番に計算するかによって、全体の写像の精度が大きく変化する。そこでエッジの絶対値画像を用いる。エッジの部分は情報量を多く含むため、エッジの絶対値が大きいところから先に写像計算を行う。このことによって、特に二値画像のような画像に対して非常に精度の高い写像を求めることができるようになった。【０１０１】
前提技術では２枚のキーフレーム間のマッチングをとって対応する位置情報（以下、「対応点情報」ともいう）を生成し、この位置情報をもとに中間フレームを生成した。キーフレームはマッチングの対象となる画像であり、前提技術では始点画像および終点画像と表現されている。この技術は動画の圧縮に利用でき、現実に実験ではＭＰＥＧを超える画質と圧縮率の両立が確認されはじめている。【０１０２】
（第１の実施の形態）
以下、第１の実施の形態に係る符号化技術、復号化技術について順に説明する。
［１］画像符号化技術
はじめに、図１９を参照しつつ、第１の実施の形態に係る画像符号化技術について説明する。図１９は、本画像符号化技術のフローを示すものであり、また同時に、後述する画像符号化装置の構成を示すものである。なお、図中、様々な処理を行う機能ブロックとして記載される各要素は、ハードウェア的には、ＣＰＵ、メモリ、その他のＬＳＩで構成することができ、ソフトウェア的には、メモリにロードされたプログラムなどによって実現される。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組合せによっていろいろな形で実現できることは当業者には理解されるところであり、いずれかに限定されるものではない。また、図中、同一のブロックが複数箇所に現れる場合、必ずしも同一のブロックが複数存在することを意味するものではなく、１つのブロックが複数回使用されることを意味する場合もある。
（１）処理の対象となる画像フレームの列（以下単に「対象画像フレーム」という）を降順または昇順にＦ０、Ｆ１、・・・、Ｆｎ−１、Ｆｎ（ｎは２以上の整数）と表記する。また、画像フレームＦｉ、Ｆｊ（ｉ，ｊ＝０，１，・・・，ｎ）間で対応しあう点の位置関係を示す対応点情報をＭｉ−ｊと表記する。画像フレームＦｉ上の点を総括的にｐｉと書くことにする。対象画像フレームは時間的に等間隔でもよいし、そうでなくともよい。このとき、符号化技術は以下のステップを実行する。【０１０３】
ステップａ
画像フレームＦ０とＦｎ間でマッチングを計算して対応点情報Ｍ０−ｎを生成する。マッチングは画像フレーム間で対応しあう領域や点などを特定するための処理である。前提技術を用いる場合、マッチングは画素ベースで行われ、ＭＰＥＧ同様のマッチングにはブロックマッチングが用いられる。画像フレームＦ０上の点ｐ０と画像フレームＦｎ上の点ｐｎが対応しあうとき、最も簡単な対応点情報Ｍ０−ｎの記述例は「ｐ０→ｐｎ」である。これを実際には画像内座標（以下単に「座標」という）で記述する。点ｐｉが具体的にはｐｉ０、ｐｉ１・・で構成され、これらが互いに対応しあうとき、対応点情報Ｍ０−ｎの記述例は以下のようになる。
「ｐ００→ｐｎ０／ｐ０１→ｐｎ１／ｐ０２→ｐｎ２／・・」【０１０４】
ステップｂ
画像フレームＦ０上の点ｐ０を対応点情報Ｍ０−ｎによって画像フレームＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、画像フレームＦ１上で点ｐ０に対応する点ｐ１、画像フレームＦ２上で点ｐ０に対応する点ｐ２、・・・、画像フレームＦｎ上でｐ０に対応する点ｐｎを算出する。対象画像フレームが時間的に等間隔なら「ｎ分割」はｎ等分であるが、そうでない場合は、画像フレーム間の時間比に応じた分割比による分割となる。例えば、ｐ０の座標が（ｘ０，ｙ０）で、ｐｎのそれが（ｘｎ，ｙｎ）であり、かつ対象画像フレームが等間隔の場合、ｐｉの座標は以下にように一般化される。
（（ｘｎ−ｘ０）・ｉ／ｎ＋ｘ０，（ｙｎ−ｙ０）・ｉ／ｎ＋ｙ０）
これはいわゆる内挿による座標計算である。なお、この記述はＦ０とＦｎとの対応点どうしを直線補間する例だが、後述のごとく、曲線による補間もある。【０１０５】
ステップｃ
ステップｂを画像フレームＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的な画像フレームＦ１’、点ｐ２の集合を利用して仮想的な画像フレームＦ２’、・・・、点ｐｎの集合を利用して仮想的な画像フレームＦｎ’をそれぞれ生成する。「所定数の点」の例は、画像フレームを構成する全画素である。ただ、その場合は計算量も大きくなるので、例えば画像フレームのｘ、ｙ方向に数画素に１画素を抽出してもよい。これは画像フレームをメッシュに分割し、メッシュの格子点に当たる画素だけを抽出することと同じである。例えばｘ、ｙ方向とも５画素に１画素を取り出せば、「所定数の点」は全画素数の１／２５となる。【０１０６】
「所定数」が全画素数ではない場合、対応点の計算がなされなかった点の対応点（仮に非格子点という）は、計算がされた対応点（仮に格子点という）をもとに補間により計算される。例えば、画像フレームＦ０上の非格子点が同Ｆ０上のふたつの格子点の間にあり、前者の位置ベクトルをｐ、後二者のそれをｑ、ｒとし、ｐ＝（１−α）ｑ＋αｒと記述できるとき、画像フレームＦｎ上で点ｐに対応する点ｐ’は、同Ｆｎ上でそれぞれｑ、ｒに対応する点ｑ’、ｒ’を用いて、ｐ’＝（１−α）ｑ’＋αｒ’と書くことができる。これを一般化し、非格子点を３つの格子点で記述する方法がバイリニア補間として知られている。これを利用すればよい。【０１０７】
ステップｄ
仮想的な画像フレームＦ１’と現実の画像フレームＦ１の組Ｓ１、仮想的な画像フレームＦ２’と現実の画像フレームＦ２の組Ｓ２、・・・、仮想的な画像フレームＦｎ’と現実の画像フレームＦｎの組Ｓｎの各組に対し、その組に含まれる画像フレーム間の差分が大きな組Ｓｋ（ｋ＝１，・・・，ｎ）の有無を所定の判定基準をもとに判定する。
「所定の判定基準」は、単に差分を所定のしきい値と比較しそれを超える場合を「大きい」としてもよい。すなわち、差分そのものに着目してもよい。ここでしきい値は実験で定めればよく、以下ほかのパラメータについても同様のことがいえる。【０１０８】
別の「判定基準」として、前提技術で計算したエネルギーの値、すなわち差分の大きさを示唆する物理量を用いてもよい。エネルギーは対応点どうしの位置が遠いほど大きく、画素値が離れるほど大きくなる。したがって、一般には、エネルギーが大きいほど対応が正確に捉えられていない可能性が高い。対応が正確でなければ差分も増える傾向がある。そのため、画像フレーム間のエネルギー値が所定のしきい値より大きければ差分が大きいと判定してもよい。【０１０９】
ステップｅ，ｆ
差分が大きな組Ｓｋが存在する場合、少なくとも、画像フレームＦｈ（ｈ＝０，１，・・・，ｋ−１）と画像フレームＦｋ’間でマッチングを計算して対応点情報Ｍｈ−ｋを生成する。つづいて、対応点情報Ｍｈ−ｋの情報を利用し、対応点情報Ｍ０−ｎを修正する（以下、修正前の対応点情報Ｍ０−ｎを単に「原Ｍ０−ｎ」あるいは「Ｍ０−ｎ」とよび、修正された対応点情報Ｍ０−ｎを「修正Ｍ０−ｎ」あるいは「Ｍ０−ｎ’」とよぶ）。一例として、ｈ＝０とすればＭ０−ｋが求められ、点ｐ０に対応する点ｐｋが求まる。修正Ｍ０−ｎは例えば「ｐ０→ｐｋ→ｐｎ」とされ、これは折れ線形式の表現である。これにより、点ｐ０はｐｋを経てｐｎに至るため、原Ｍ０−ｎによる直線形式の表現よりＳｋの差分は小さくなる。なお、修正Ｍ０−ｎは、折れ線ではなく曲線形式でもよい。その場合、「ｐ０→ｐｋ→ｐｎ」ないしその近似が実現されるよう例えばスプライン曲線で軌跡を記述すればよい。【０１１０】
ステップｇ
少なくとも画像フレームＦ０と修正Ｍ０−ｎを含む形式の符号化データを出力する。画像フレームＦ０と修正Ｍ０−ｎがあれば、画像フレームＦ０上の点ｐ０をｐｋを経てｐｎへ至らしめることができるため、符号化データとして成立する。符号化データには画像フレームＦｎのデータを含めてもよい。その場合、単にｐ０が移動するだけでなく、画素値も内挿補間で変化させることができる。点ｐ０の画素値をＶｐ０、点ｐｎのそれをＶｐｎとすると、点ｐｉの画素値Ｖｐｉは以下のように内挿計算できる。非格子点については座標の場合同様バイリニア補間で求めればよい。
Ｖｐｉ＝（Ｖｐｎ−Ｖｐ０）・ｉ／ｎ＋Ｖｐ０【０１１１】
ただし、もともと点ｐ０とｐｎは画素値もある程度近いから対応点として検出されたと考えることができるため、画素値の変化の記述は必須ではない。そのため、画像フレームＦ０とＦｎのうちＦ０だけでも符号化データとして成り立つ。【０１１２】
以上の方法によれば、比較的小さなデータで比較的高い画質を実現することができる。なぜなら、画像フレームとしては最低１枚のデータがあればよく、修正Ｍ０−ｎは「所定数の点」を適当に減らすことにより、そのデータ量が大幅に減る。したがって、データ総量は小さいながら、差分が大きなＳｋについては原Ｍ０−ｎを修正して対応するため、画質が大幅に改善される。この事実は実験によっても確認されている。【０１１３】
（２）ステップｄは、画像フレーム間の差分の大きさを所定の領域単位で判定するものとする。領域は例えば単純に画像フレームをメッシュ分割して得られる。領域の大きさは実験で画質とデータ量の組合せから選択すればよい。
ステップｄで領域単位の判定をする場合、仮想的な画像フレームＦｋ’と現実の画像フレームＦｋ間で対応しあう、すなわち位置的に同じ領域間の差分が所定のしきい値より大きくなるとき、Ｓｋを「差分の大きな組」と判定する。この場合、仮想的な画像フレームＦｋ’と現実の画像フレームＦｋ間の画像フレーム全体にわたる差分の総計が大きいとは限らないし、その必要もない。あくまでも差分が大きな領域を見出せばよい。なお、ここでも差分そのものに着目することに代え、またはそれに加え、領域ごとにエネルギーの総計を計算し、これをしきい値と比較してもよい。以下、実施の形態では画像フレーム全体ではなく、領域ごとの比較をするものとする。【０１１４】
図２０（ａ）〜（ｄ）は、対象画像フレームの例を示す図である。領域ごとの比較が特に有効なのは、図２０（ａ）〜（ｃ）に示すように、対象画像フレームが「ボールのバウンド」を映しており、図２０（ａ）の画像フレームＦ０はバウンド前、図２０（ｃ）の画像フレームＦｎはバウンド後、図２０（ｂ）の画像フレームＦｋがバウンドの瞬間に対応するような場合である。原Ｍ０−ｎを用いてＦ１、Ｆ２、・・・を補間で生成しても、ボールはバウンド前の位置からバウンド後の位置へ直線的に移動するのみであり、不自然である。図２０（ａ）〜（ｃ）には、実際のボールの軌道が実線で、原Ｍ０−ｎを用いて補間により生成した場合のボールの軌道が破線で示される。領域ごとに差分を計算すれば、しきい値の調整により、Ｓｋなり、その前後の組なりを検出することができる。たとえば、図２０（ａ）〜（ｃ）の例では、画像フレームＦｋにおいて、実際のボールＢｋと、補間により生成されたボールの位置Ｂｋ’を含む領域の差分がしきい値を超え、Ｓｋが検出される。それらが検出できれば、修正Ｍ０−ｎに反映できるため、ボールのバウンドの様子をより的確に表現することができる。図２０（ｄ）は、修正Ｍ０−ｎにもとづいて再現されるボールの軌道を示している。【０１１５】
なお、差分が大きい領域は同一のＳｋにおいて複数検出されてもよい。例えば画像フレームＦ０上の点ｐ００は差分の大きい領域Ａ、点ｐ０１は差分の大きな別の領域Ｂに含まれるとする。この場合も修正Ｍ０−ｎは「ｐ００→ｐｎ０／ｐ０１→ｐｎ１／・・」と形式となり、結局、領域が複数検出されても修正Ｍ０−ｎの形式自体には影響しない。同様の理由で、複数の領域が異なる組に検出されてもよい。【０１１６】
（３）ステップｅは、以下のサブステップを含んでもよい。
ｅ１）差分が大きな組Ｓｋが存在する場合、画像フレームＦ０とＦ１間の対応点情報Ｍ０−１、Ｆ１とＦ２間のＭ１−２、・・・、Ｆｋ−１とＦｋ間のＭ（ｋ−１）−ｋをそれぞれ求める。
ｅ２）Ｍ０−１、Ｍ１−２、・・・、Ｍ（ｋ−１）−ｋを統合してＭ０−ｋを生成する。
これは既述した。【０１１７】
（４）ステップｅ２は、対応点情報Ｍ０−１によって点ｐ０に対応するｐ１を求め、対応点情報Ｍ１−２によって点ｐ１に対応するｐ２を求め、・・・、対応点情報Ｍ（ｋ−１）−ｋによって点ｐｋ−１に対応するｐｋを求め、ｐ０に対応する点をｐ１、ｐ２、・・・、ｐｋと順に特定することにより、最終的にｐ０に対応するｐｋを特定してＭ０−ｋを生成してもよい。これは既述した。【０１１８】
（５）ステップｆは、対応点情報Ｍ０−ｋの情報を利用し、点ｐ０がｐｋを経てｐｎへ至る軌跡を示す形式にて、修正Ｍ０−ｎを生成してもよい。これは既述した。【０１１９】
（６）ステップｄにて差分が大きな組Ｓｋが存在することが判明した場合、ステップｇは画像フレームＦ０と修正Ｍ０−ｎに加え、組Ｓｋにおける差分の情報を含む形式の符号化データを出力してもよい。例えば組Ｓｋの領域Ａの差分が大きい場合、原Ｍ０−ｎを修正Ｍ０−ｎへ変更するだけでは完全な画質が得られないことも考えられる。その場合、まずは対応点情報Ｍ０−ｎの修正によって差分を相当量削減したうえで、さらに残余の差分を符号化データへ領域Ａの差分を記述してもよい。この場合、符号化データのフォーマットは、例えば以下のようになる。【０１２０】
図２１は、第１の実施の形態に係る画像符号化技術における符号化データのフォーマットを示す図である。符号化データＤ１は、画像フレーム（i）と、修正された対応点情報（ii）と、存否ビット（iii）と、差分情報(iv)と、ｋの値(v)と、領域の位置／形状方法(vi)と、を含んで構成される。各データの内容は、以下の通りである。
ｉ）Ｆ０のデータ、またはＦ０＋Ｆｎのデータ
ii）修正Ｍ０−ｎ（折れ線、曲線などの形式）
iii）差分情報の有無を示す「存否ビット」
iv）差分情報（画像データの形式）
v）ｋの値（複数の場合はｋ１、ｋ２、・・・）
vi）領域の位置／形状情報（複数の場合はＡ１（ｋ１）、Ａ２（ｋ２）、・・）【０１２１】
ここで、差分情報は、「仮想的なＦｋ’と現実のＦｋの領域Ａに関するデータ」であり、領域Ａの画像データの形式をとる。存否ビットが差分情報の存在を肯定する場合にかぎり差分情報は有効であり、否定する場合、後述の画像復号の際に差分情報以下の情報が無視される。
差分情報は画像データの形のため、既知の圧縮手法によって圧縮してから符号化データへ格納されることが望ましい。差分情報は画像としては意味を持たないものであり、ゼロを中心にきれいな統計的偏りがでやすいため、比較的高い圧縮率が実現できる点でも有利である。
ｋの値と、領域の位置／形状情報は、差分情報がいずれの組Ｓｋのいずれの個所に関するものであるかを示す。復号装置では、ｋの値と領域の位置／形状情報を手がかりに差分を適切に加算する。【０１２２】
（７）組Ｓｋにおける差分情報は、画像フレームの中で差分が大きかった領域についてのみ符号化データへ含められる。これは既述した。【０１２３】
（８）差分とともに、少なくともｋの値と領域Ａの位置情報が符号化データへ含められる。これは既述した。【０１２４】
（９）差分は圧縮処理を受けた後、符号化データへ含められる。これは既述した。
（１０）画像符号化装置のある態様は以下の構成を含む。各構成の処理動作自体は既述した。
・マッチング処理部２０
Ｆ０とＦｎ間でマッチングを計算してＭ０−ｎを生成する。
・中間フレーム生成部２２
Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ上でｐ０に対応する点ｐｎを算出する処理をＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１’、点ｐ２の集合を利用して仮想的なＦ２’、・・・、点ｐｎの集合を利用して仮想的なＦｎ’をそれぞれ生成する。【０１２５】
・判定部２４
仮想的なＦ１’と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組に対し、その組に含まれる画像フレーム間の差分が大きな組Ｓｋ（ｋ＝１，・・・，ｎ）の有無を所定の判定基準をもとに判定する。
以上の構成のもと、マッチング処理部は、差分が大きな組Ｓｋが存在する場合、少なくとも、Ｆｈ（ｈ＝０，１，・・・，ｋ−１）とＦｋ間でマッチングを計算してＭｈ−ｋを生成し、このＭｈ−ｋの情報を利用してＭ０−ｎを修正する。本装置はさらに、少なくともＦ０と修正Ｍ０−ｎを含む形式の符号化データを出力する出力部４０を含む。【０１２６】
（１１）画像符号化方法の別の態様は以下の処理をなす。
処理１：  ３以上の画像フレームを含む画像グループの両端画像フレーム間でマッチング計算を実行する。両端画像フレームの例は既述のＦ０、Ｆｎである。
処理２：  マッチング計算の結果得られた両端画像フレーム間の対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する。この例は既述の内挿補間によるＦ１’、Ｆ２’、・・の生成である。【０１２７】
処理３：  画像上のいずれかの領域について、仮想的に生成された中間画像フレームのうちいずれかが、現実の中間画像フレームと許容値以上の差分を有するか否かを所定の判定基準のもとで判定する。すなわち、ふたつの画像フレーム間で、領域を単位とする比較を行う。この例は組Ｓkとして既述した。ここでは「許容値以上の差分」といっており、許容値未満であれば、処理４はスキップできる。
処理４：  両端画像フレームのうち少なくとも一方と、対応点情報とを含む符号化データを生成する。許容値以上の差分を有する領域が存在すると判定された場合、その領域に関する差分情報をあわせて生成する。これは既述した。【０１２８】
（１２）画像符号化装置の別の態様は以下の構成を含む。各構成による処理は既述した。
・マッチング処理部２０
３以上の画像フレームを含む画像グループの両端画像フレーム間でマッチング計算を実行する。
・中間フレーム生成部２２
マッチング計算の結果得られた両端画像フレーム間の対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する。【０１２９】
・判定部２４
画像上のいずれかの領域について、仮想的に生成された中間画像フレームのうちいずれかが、現実の中間画像フレームと許容値以上の差分を有するか否かを所定の判定基準のもとで判定する。
・出力部２６
両端画像フレームのうち少なくとも一方と、対応点情報とを含む符号化データを出力する。許容値以上の差分を有する領域が存在すると判定された場合、その領域に関する差分情報をあわせて出力する。【０１３０】
［２］画像復号技術
第１の実施の形態に係る画像復号技術は、［１］の画像符号化技術によって生成された符号化データを復号するよう作用する。したがって、［１］の技術と以下の技術の組合せを有する画像符号化・復号システムは実施の形態の変形例である。以下、全体の通し番号を付して説明する。【０１３１】
図２２は、本画像復号技術のフローを示すものであり、また同時に、後述する画像復号装置の構成を示すものである。【０１３２】
（１３）実施の形態に係る画像復号方法のある態様は以下のステップを実行する。
ｐ）少なくともＦ０、Ｍ０−ｎおよび所定の差分情報を含む形式の符号化データを入力する。所定の差分情報は、例えば（６）の「iv）差分情報（画像データの形式）」である。
ｑ）Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ−１上でｐ０に対応する点ｐｎ−１を算出する。ステップbと同様である。【０１３３】
ｒ）ステップｑをＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１’、点ｐ２の集合を利用して仮想的なＦ２’、・・・、点ｐｎの集合を利用して仮想的なＦｎ’をそれぞれ生成する。ステップｃと同様である。
ｓ）仮想的なＦ１’と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組のうち、前記差分情報が与えられているＳｋ（ｋ＝１，・・・，ｎ）を特定する。この特定は、例えば（６）の「iii）差分情報の有無を示す「存否ビット」」および／または「v）ｋの値（複数の場合はｋ１、ｋ２、・・・）」によって行う。【０１３４】
ｔ）仮想的なＦｋ’に対し、差分情報によって定まる差分を加算することにより、修正された仮想的なＦｋ’’を生成する。差分の加算に当たっては、（６）の「vi）領域の位置／形状情報（複数の場合はＡ１（ｋ１）、Ａ２（ｋ２）、・・）」を参照する。
ｕ）復号結果として、Ｆ０、仮想的なＦ１’、仮想的なＦ２’、・・・、修正された仮想的なＦｋ’’、仮想的なＦｋ＋１’、・・・、仮想的なＦｎ−１’をこの順に、すなわち表示順に出力する。Ｆｎについては、仮想的なほうを出力してもよいが、現実のＦｎが存在する場合はそれを出力してもよい。出力先は例えば表示制御ユニットであり、そのユニットで表示装置用に変換される。実施の形態のある態様の画像復号装置は、そうした表示制御ユニットおよび表示装置まで有するものとする。【０１３５】
（１４）差分情報は画像フレーム間の差分が大きな領域についてのみ差分を記述しており、ステップｔは差分を加算する際、前記領域の位置情報を特定する。これは既述した。
（１５）差分情報は圧縮されており、ステップｔは差分情報を伸長してから加算してもよい。
（１６）Ｍ０−ｎは、ｐ０がｐｋを経てｐｎへ至る軌跡を示す形式にて生成されていてよい。すなわち、ここでいうＭ０−ｎは原Ｍ０−ｎではなく、符号化側で生成された修正Ｍ０−ｎということである。この態様によれば、画質が改善される。【０１３６】
（１７）実施の形態に係る画像復号装置は以下の構成を含む。
・入力部３０
少なくともＦ０、Ｍ０−ｎおよび所定の差分情報を含む形式の符号化データを入力する。入力部はどのようなインタフェイスでもよいし、符号化データが格納されたメモリからそれを読み出す読出制御部であってもよい。
・中間フレーム生成部３２
Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ−１上でｐ０に対応する点ｐｎ−１を算出する処理をＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１’、点ｐ２の集合を利用して仮想的なＦ２’、・・・、点ｐｎの集合を利用して仮想的なＦｎ’をそれぞれ生成する。【０１３７】
・特定部３４
仮想的なＦ１’と現実のＦ１の組Ｓ１、仮想的なＦ２’と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎ’と現実のＦｎの組Ｓｎの各組のうち、前記差分情報が与えられているＳｋ（ｋ＝１，・・・，ｎ）を特定する。特定の方法の例は既述した。
・中間フレーム修正部３６
仮想的なＦｋ’に対し、前記差分情報によって定まる差分を加算することにより、修正された仮想的なＦｋ’’を生成する。
・出力部３８
復号結果として、Ｆ０、仮想的なＦ１’、仮想的なＦ２’、・・・、修正された仮想的なＦｋ’’、仮想的なＦｋ＋１、・・・、仮想的なＦｎ−１’を出力する。出力先は表示装置用のデータないし信号を生成する表示制御ユニットでもよい。
本装置はさらに、この表示制御ユニットを含んでもよいし、さらに表示装置自体を含んでもよい。【０１３８】
（１８）実施の形態に係る画像復号方法の別の態様は以下の処理を実行する。
処理１：  ３以上の画像フレームを含む画像グループの両端画像フレームのうちの一方と、それら両端画像フレーム間の対応点情報と、所定の差分情報とを含む符号化データを入力する。
処理２：  前記対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する。
処理３：  仮想的に生成された中間画像フレームそれぞれとそれに対応する現実の中間画像フレームとによる組のうち、差分が大きな組として符号化データ内に記述された組の中間画像フレームの画像上にて差分が大きい領域を特定する。
処理４：  差分が大きな組に含まれる仮想的な画像フレームに対し、前記領域における差分を加算することにより、修正された仮想的な画像フレームを生成する。
処理５：  復号結果として、両端画像フレームのうちの一方と、差分が大きな組については修正された仮想的な中間画像フレームと、それ以外の組については仮想的な中間画像フレームとを復号データとして出力する。【０１３９】
（１９）実施の形態に係る画像復号装置の別の態様は以下の構成を含む。
・入力部３０
３以上の画像フレームを含む画像グループの両端画像フレームのうちの一方と、それら両端画像フレーム間の対応点情報と、所定の差分情報とを含む符号化データを入力する。
・中間フレーム生成部３２
前記対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する。【０１４０】
・領域特定部３４’
仮想的に生成された中間画像フレームそれぞれとそれに対応する現実の中間画像フレームとによる組のうち、差分が大きな組として符号化データ内に記述された組の中間画像フレームの画像上にて差分が大きい領域を特定する。特定方法の例は既述した。
・中間フレーム修正部３６
差分が大きな組に含まれる仮想的な画像フレームに対し、前記領域における差分を加算することにより、修正された仮想的な画像フレームを生成する。
・出力部３８
復号結果として、両端画像フレームのうちの一方と、差分が大きな組については修正された仮想的な中間画像フレームと、それ以外の組については仮想的な中間画像フレームとを復号データとして出力する。ここでも（１７）同様の変形例がある。【０１４１】
（２０）（１１）に記載の画像符号化方法、またはそれ以外の個所に記載した画像符号化方法の各ステップをコンピュータプログラムによってコンピュータに実行せしめてもよい。
（２１）（１８）に記載の画像復号方法、またはそれ以外の個所に記載した画像復号方法の各ステップをコンピュータプログラムによってコンピュータに実行せしめてもよい。【０１４２】
（２２）実施の形態に係る画像処理システムは画像符号化ユニット（図１９の１００）と画像復号ユニット（図２２の２００）とを有する。このシステムは例えばハードディスクを用いた動画像録画再生装置として利用できる。まず画像符号化ユニットは以下の構成を有する。
・マッチング処理部２０
３以上の画像フレームを含む画像グループの両端画像フレーム間でマッチング計算を実行する。
・符号化側中間フレーム生成部２２
マッチング計算の結果得られた両端画像フレーム間の対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する。
・判定部２４
画像上のいずれかの領域について、仮想的に生成された中間画像フレームのうちいずれかが、現実の中間画像フレームと許容値以上の差分を有するか否かを所定の判定基準のもとで判定する。【０１４３】
・書込制御部（２６）
両端画像フレームのうち少なくとも一方と、対応点情報とを含む符号化データをメモリ（図示せず）へ書き込む。許容値以上の差分を有する領域が存在すると判定された場合、その領域に関する差分情報もあわせて書き込む。【０１４４】
一方、画像復号ユニットは以下の構成を有する。
・読出制御部（３０）
前記のメモリから符号化データを読み出す。
・復号側中間フレーム生成部３２
符号化データに含まれる画像フレームのデータと対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する。なお、符号化側中間フレーム生成部と同じ構成を共用してもよい。その場合、符号化側のマッチング処理部の出力と、復号側の読出制御部の出力のいずれかを選択して中間フレーム生成部へ入力するセレクタを設けてもよい。このセレクタは、符号化の際にはマッチング処理部の出力、復号の際には読出制御部の出力をそれぞれ選択する。【０１４５】
・領域特定部３４
符号化データに差分情報が含まれている領域を特定する。その方法の例は既述した。
・中間フレーム修正部３６
特定された領域を含む仮想的な画像フレームに対し、前記領域における差分を加算することにより、修正された仮想的な画像フレームを生成する。【０１４６】
・出力部３８
復号結果として、両端画像フレームのうちの一方または双方と、前記領域を含む仮想的な画像フレームについては修正された仮想的な中間画像フレームと、前記領域を含まない仮想的な画像フレームについてはその仮想的な中間画像フレーム自体とを復号データとして出力する。【０１４７】
（第２の実施の形態）
以下、第２の実施の形態に係る符号化技術、復号化技術について順に説明する。図２３は、第２の実施の形態に係る画像符号化装置の構成を示すものであり、また同時に、当該画像符号化技術のフローを示すものである。【０１４８】
［１］符号化装置の構成
ＣＰＦ：  前提技術のCritical Point Filter、すなわち特異点フィルタを用いる画像マッチングプロセッサ。キーフレーム間のマッチングを画素単位で計算し、対応点情報を出力する。この情報はファイルとして出力される。このファイルは、ソース側のキーフレームの各画素がデスティネーション側のキーフレームのいずれの画素に対応するかを記述する。したがって、このファイルをもとに、これらのキーフレーム間で対応しあう画素の位置と画素値を内挿計算すれば、ふたつのキーフレーム間のモーフィング画像が得られる。なお、このファイルをソース側のキーフレームだけに作用させて内挿計算をすれば、単にソース側のキーフレームの各画素をこのファイルに記述した対応画素の位置へ徐々に移動させるモーフィング画像が得られる。この場合、対応画素間で位置だけが内挿されたことになる。【０１４９】
なお、ＣＰＦの代わりに、広く画像マッチングプロセッサを利用することができるが、本実施の形態の趣旨からいえば、精度が高い画素マッチングが理想的であり、前提技術はその条件を満たす。【０１５０】
ＤＥ： Differential Encoder 差分（誤差）符号化器。ふたつの画像フレーム間の差分をハフマン符号化その他の統計手法に基づき可変長符号化する。【０１５１】
ＮＲ： maskable Noise Reducer ノイズリデューサ。人間の視覚では微細な変化を認識できないことが多い。たとえば輝度の変化の激しい部分、つまり輝度の空間周波数成分が高い成分が強い領域では、輝度変化の誤差は視覚的には把握されない。動画情報にはさまざまな形でノイズが重畳しており、そのようなデータは視覚的には単にノイズとして認識されるだけで画像としての意味を持たない。そのような視覚的無意味なランダム情報、すなわち「視覚的マスク情報」を無視することが、より高い圧縮率を達成するために重要である。【０１５２】
現在のブロックマッチングにおける量子化は、輝度値に関する視覚的マスク情報を利用したものであるが、輝度値以外にもいくつかの視覚的マスク情報が存在する。ＮＲは、空間位置情報ならびに時間位置情報に関する視覚的マスクを利用する。空間位置情報の視覚的マスクは、位置情報に関して、輝度変化が複雑な画像の場合は空間周波数の位相成分が視覚的に認識されにくいという事実を利用する。時間位置情報の視覚的マスクは、時間方向での変化が激しい部分では時間方向にデータの変化がずれたとしても、視覚的にはその差が認識されにくい事実を利用する。これらはいずれも所定のしきい値との比較して検出する。【０１５３】
少なくともブロックマッチングと差分符号化という現在のＭＰＥＧのスキームでは、これらのマスクを積極的に利用することは困難である。これに対し、前提技術における復号処理は、視覚的な不自然さをもたらすような不連続性を回避するために、動画上の変化をトリリニアその他の補間で生成するものであり、それは誤差を輝度方向だけでなく、空間方向や時間方向に散らして視覚的に目立たなくする働きを持つ。ＮＲは前提技術との組合せにおいて有用である。【０１５４】
ＤＤ： Differential Decoder 差分（誤差）復号器。ＤＥで符号化された差分を復号し、その差分が生じた画像フレームに加算することで、その画像フレームの精度を高める。【０１５５】
ＤＣ： Differential Comparator 差分比較器。仮想的なＦ１’と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組に対し、その組に含まれる画像フレーム間の差分が大きな組Ｓｋ（ｋ＝１，・・・，ｎ）の有無を所定の判定基準をもとに判定する。【０１５６】
なお、これらのほかに、ある単一のキーフレームに対応点情報を作用させ、そのキーフレームの画素移動だけから仮想的に別のキーフレームを生成する機能が存在する。以下、この機能を実現する機能ブロックを画素シフタとよぶ。【０１５７】
なお、第２の実施の形態におけるＣＰＦおよびＤＣは、それぞれ第１の実施の形態におけるマッチング処理部２０および判定部２４に対応させることができる。【０１５８】
［２］符号化処理
図２３において、「Ｆ０」等は処理の対象となる動画の各フレーム、「Ｍ０−ｎ」はＣＰＦによって生成されたＦ０とＦｎ間の対応点情報を示す。符号化は以下の手順で進む。以下では、ｎ＝４の場合について説明する。また、図２３において、ｎ２＝８である。【０１５９】
ａ）  １以上の画像フレーム（Ｆ１〜Ｆ３）を間に挟む第１、第２キーフレーム（Ｆ０、Ｆ４）間でＣＰＦによってマッチングを計算し、第１、第２キーフレーム間の対応点情報（Ｍ０−４）を生成するステップ。
ｂ−１）  第１、第２キーフレーム間の対応点情報（Ｍ０−４）をもとに、修正Ｍ０−４’を生成するステップ。修正Ｍ０−４’の生成については、第１の実施の形態において既述した技術を利用すればよい。
ｂ−２）  第１、第２キーフレーム間の修正された対応点情報（Ｍ０−４’）をもとに、画素シフタによって第１キーフレーム（Ｆ０）に含まれる画素を移動させて仮想の第２キーフレーム（Ｆ４’）を生成するステップ。
ｃ）  現実の第２キーフレーム（Ｆ４）と仮想の第２キーフレーム（Ｆ４’）との差分をＮＲ機能付きＤＥ（ＤＥ＋ＮＲと表記）で圧縮符号化するステップ。
ｄ）  第１キーフレーム（Ｆ０）、第１、第２キーフレーム間の修正された対応点情報（Ｍ０−４’）、および、現実の第２キーフレームと仮想の第２キーフレーム間で圧縮符号化された差分（Δ４）をこれらのキーフレーム（Ｆ０、Ｆ４）間の符号化データとして出力するステップ。出力先は記録媒体、伝送媒体を問わない。実際には後述のｊ）で出力される情報と一体となり、動画符号化データとして記録媒体等に出力される。【０１６０】
ステップｂ−１）について詳細に説明する。図１９で説明したように、現実のフレームＦｉと、対応する仮想フレームＦｉ’の差分Ｓｉから、その組に含まれる画像フレーム間の差分が大きな組Ｓｋ（ｋ＝１，・・・，ｎ）の有無を所定の判定基準をもとに判定する。
判定結果は、ＤＥ＋ＮＲへと出力され、組Ｓｋの差分が圧縮され、差分情報でΔｋとして出力される。【０１６１】
また、差分情報が存在する組を示すｋの値が、ＣＰＦへと出力される。ＣＰＦは、フレームＦ０〜Ｆｋの間の隣接するフレーム同士の対応点情報を算出する。すなわち、Ｆ０とＦ１、Ｆ１とＦ２、Ｆ３とＦ４、…、Ｆｋ−１とＦｋとの間の対応点情報（Ｍ０−１、Ｍ１−２、Ｍ２−３、…）を算出する。結合器ＣＯＮＣＡＴは、これらの対応点情報を結合して、対応点情報Ｍ０−ｋを出力する。対応点情報Ｍ０−ｋは、ステップａ）にて生成された対応点情報Ｍ０−ｋと合成されて、修正された対応点情報Ｍ０−ｎ’が生成される。【０１６２】
つづいて、第２キーフレーム（Ｆ４）以降について以下の処理を行う。
ｅ）  現実の第２キーフレーム（Ｆ４）と仮想の第２キーフレーム（Ｆ４’）間で圧縮符号化された差分（Δ４）をＤＤで復号するステップ。
ｆ）  復号された差分と前記仮想の第２キーフレーム（Ｆ４’）とから、改良された仮想の第２キーフレーム（Ｆ４”）をＤＤで生成するステップ。
ｇ）  １以上の画像フレーム（Ｆ５〜Ｆ７）を間に挟む第２、第３キーフレーム（Ｆ４、Ｆ８）間でＣＰＦによってマッチングを計算し、第２、第３キーフレーム間の対応点情報（Ｍ４−８）を生成するステップ。
ｈ−１）  第２、第３キーフレーム間の対応点情報（Ｍ４−８）をもとに、（Ｍ４−８’）を生成するステップ。
ｈ−２）  第２、第３キーフレーム間の修正された対応点情報（Ｍ４−８’）をもとに、画素シフタによって、改良された仮想の第２キーフレーム（Ｆ４”）に含まれる画素を移動させることによって、仮想の第３キーフレーム（Ｆ８’）を生成するステップ。
ｉ）  現実の第３キーフレーム（Ｆ８）と仮想の第３キーフレーム（Ｆ８’）との差分をＤＥ＋ＮＲで圧縮符号化するステップ。
ｊ）  第２、第３キーフレーム間の修正された対応点情報（Ｍ４−８’）、および現実の第３キーフレームと仮想の第３キーフレーム間で圧縮符号化された差分（Δ８）をこれらのキーフレーム（Ｆ４、Ｆ８）間の符号化データとして出力するステップ。出力先は一般にｄ）の出力先と同じである。【０１６３】
以下、さらに後続のキーフレームについて、順次前記のｅ）からｊ）のステップを繰り返し、所定のグループ終了キーフレームに到達したときに繰り返し処理を終了する。グループ終了キーフレームは、ＭＰＥＧでいう１ＧＯＰの終了フレームに相当する。したがって、このフレームの次のフレームが新たなグループの先頭フレームとして新たに第１キーフレームと見なされ、ａ）以下の処理が繰り返される。以上の処理により、ＭＰＥＧでいうＧＯＰに相当するグループ（以下、単にグループとよぶ）について、キーフレーム（ＭＰＥＧでいうＩピクチャ）に相当する画像は１枚のみ符号化および伝送すればよい。【０１６４】
［３］復号装置の構成
図２４は、第２の実施の形態に係る画像復号技術のフローおよび画像復号装置の構成を示す図である。
符号化側にもましてシンプルな構成である。  
ＤＤ：  符号化装置のＤＤと同じ。  
ＩＮＴ：  INTerpolator  補間プロセッサ。【０１６５】
これらの他に符号化側同様の画素シフタが存在する。ふたつの画像フレームと対応点情報から内挿処理による中間フレームを生成する。
［４］復号処理
復号は以下の手順で進む。ここでも、ｎ＝４、ｎ２＝８として説明する。【０１６６】
ｋ）  １以上の画像フレーム（Ｆ１〜Ｆ３）を間に挟む第１、第２キーフレーム（Ｆ０、Ｆ４）間の修正された対応点情報（Ｍ０−４’）、および第１キーフレーム（Ｆ０）を取得するステップ。取得は伝送媒体、記録媒体のいずれからでもよい。
ｌ）  第１、第２キーフレーム間の修正された対応点情報（Ｍ０−４’）をもとに、画像シフタによって第１キーフレーム（Ｆ０）に含まれる画素を移動させることによって、仮想の第２キーフレーム（Ｆ４’）を生成するステップ。
ｍ）  予め符号化側にてｌ）同様の処理により、仮想の第２キーフレーム（Ｆ４’）が生成され、符号化側でこれと現実の第２キーフレーム（Ｆ４）との差分の圧縮符号化データ（Δ４）を生成しているため、これを取得するステップ。
ｏ）  取得された差分の圧縮符号化データ（Δ４）をＤＤで復号し、仮想の第２キーフレーム（Ｆ４’）と加算して、改良された仮想の第２キーフレーム（Ｆ４’’）を生成するステップ。
ｐ）  第１、第２キーフレーム間の修正された対応点情報（Ｍ０−４’）をもとに、ＩＮＴによって、第１キーフレーム（Ｆ０）と改良された仮想の第２キーフレーム（Ｆ４”）間で補間計算をすることにより、これらのキーフレーム（Ｆ０、Ｆ４”）の間に存在すべき中間フレーム（Ｆ１’〜Ｆ３’）を生成するステップ。
ｑ）  第１キーフレーム（Ｆ０）、生成された中間フレーム（Ｆ１’〜Ｆ３’）、改良された仮想の第２キーフレーム（Ｆ４”）をこれらのキーフレーム間の復号データとして表示装置等へ出力するステップ。【０１６７】
つづいて、第２キーフレーム（Ｆ４）以降について以下の処理を行う。  
ｒ）  １以上の画像フレーム（Ｆ５〜Ｆ７）を間に挟む第２、第３キーフレーム（Ｆ４、Ｆ８）間の修正された対応点情報（Ｍ４−８’）を取得するステップ。
ｓ）  第２、第３キーフレーム間の修正された対応点情報（Ｍ４−８’）をもとに、画素シフタによって、改良された仮想の第２キーフレーム（Ｆ４”）に含まれる画素を移動させることによって、仮想の第３キーフレーム（Ｆ８’）を生成するステップ。
ｔ）  予め符号化側にてｓ）同様の処理により、符号化側でも仮想の第３キーフレーム（Ｆ８’）が生成され、符号化側でこれと現実の第３キーフレーム（Ｆ８）との差分の圧縮符号化データ（Δ８）を生成しており、これを取得するステップ。
ｕ）  取得された差分の圧縮符号化データ（Δ８）と仮想の第３キーフレーム（Ｆ８’）とから、ＤＤによって、改良された仮想の第３キーフレーム（Ｆ８”）を生成するステップ。
ｖ）  第２、第３キーフレーム間の修正された対応点情報（Ｍ４−８’）をもとに、ＩＮＴによって、改良された仮想の第２キーフレーム（Ｆ４”）と改良された仮想の第３キーフレーム（Ｆ８”）間で補間計算をすることにより、これらのキーフレームの間に存在すべき中間フレーム（Ｆ５’〜Ｆ７’）を生成するステップ。
ｗ）  改良された仮想の第２キーフレーム（Ｆ４”）、生成された中間フレーム（Ｆ５’〜Ｆ７’）、改良された仮想の第３キーフレーム（Ｆ８”）をこれらのキーフレーム（Ｆ４”、Ｆ８”）間の復号データとして表示装置などへ出力するステップ。【０１６８】
以下、さらに後続のキーフレームについて、順次前記のｒ）からｗ）のステップを繰り返し、グループ終了キーフレームに到達したときに繰り返し処理を終了する。このフレームの次のフレームが新たなグループの先頭フレームとして新たに第１キーフレームと見なされ、ｋ）以下の処理が繰り返される。
［５］本実施の形態によるメリット【０１６９】
第２の実施の形態に係る符号化、復号化技術によれば、第１の実施の形態に係る符号化、復号化技術に加えて、以下のメリットを享受できる。【０１７０】
画像マッチングに前提技術のＣＰＦを利用する場合、マッチング精度が高いため、本実施の形態で実現される圧縮率が高くなる。なぜなら、ＤＥ＋ＮＲによって圧縮すべき差分が最初から小さく、かつ統計的な偏りが大きくなるためである。【０１７１】
同様に、ＣＰＦを用いる場合、この符号化方法はブロックマッチングを用いないので、圧縮率を高めてもＭＰＥＧで問題となるブロックノイズがでない。もちろん、ＣＰＦ以外の画像マッチングでも、ブロックノイズがでない処理方法を採用すればよい。【０１７２】
もともとＭＰＥＧは差分の最小化しか考慮しないが、ＣＰＦは本来対応すべき個所を検出するため、究極的にはＭＰＥＧよりも高い圧縮率が実現できる。【０１７３】
符号化装置は画像マッチングプロセッサ、ノイズリダクション機能付き差分符号化器、差分復号器、画素シフタで構成でき、簡易である。また、ノイズリダクション機能はオプショナルな機能であり、これはなくともよい。同様に、復号装置も補間プロセッサ、差分復号器、画素シフタで構成でき、簡素である。とくに、復号装置は画像マッチングを行う必要もなく、処理量が軽い。【０１７４】
仮想のキーフレームを生成するたびに、それと現実のキーフレームの差分をΔ４、Δ８などのように符号化データへ取り込むため、グループごとに１枚しか完全な形のキーフレームを符号化しないにもかかわらず、長い動画を再生しても誤差の蓄積がない。【０１７５】
［６］変形技術【０１７６】
第１、第２キーフレーム（Ｆ０、Ｆ４）間のマッチング計算をして対応点情報ファイルを生成する際、それらキーフレーム間に存在する中間フレーム（Ｆ１〜Ｆ３）も考慮してもよい。その場合、ＣＰＦはＦ０とＦ１、Ｆ１とＦ２、Ｆ２とＦ３、Ｆ３とＦ４のそれぞれの組についてマッチングを計算し、４個のファイル（仮に部分ファイルＭ０〜Ｍ３とよぶ）を生成する。つづいて、これら４個のファイルを統合してひとつの対応点情報ファイルとして出力すればよい。【０１７７】
統合のために、まず、Ｆ０の各画素がＭ０によってＦ１上のどこへ移動するかを特定する。つづいて、Ｆ１上で特定された画素がＭ１によってＦ２上のどこへ移動するかを特定する。これをＦ４まで行えば、４個の部分ファイルにより、Ｆ０とＦ４の対応がより正確になる。Ｆ０とＦ４は多少距離があり、それらの間よりも隣接する画像フレーム間のマッチング精度のほうが一般に高いためである。【０１７８】
なお、この方法は最終的にＦ０とＦ４のマッチング精度を改善するものであるが、対応点情報ファイルを時間の関数として表現してもよい。その場合、部分ファイルを統合せず、４個の状態のまま、これらを対応点情報ファイルとみなして復号側へ提供すればよい。復号側はＦ０、Ｆ４、Ｍ０からＦ１を生成し、Ｆ０、Ｆ４、Ｍ０、Ｍ１からＦ２を生成し、という繰り返し処理でより正確な動画を復号できる。【０１７９】
（第３の実施の形態）
本発明の他の実施形態は、図２３の符号化装置に関する。ここでは、画像マッチングの正確性を示す尺度として画像のマッチングエネルギーを導入し、これをＤＥ＋ＮＲにおけるノイズリダクション等に利用する。以下、適宜図２３を用いて説明するが、特に言及しない構成、機能については第２の実施の形態と同様である。【０１８０】
ここでいうマッチングエネルギーとは、対応点どうしの距離と画素値の違いで定まるものであり、例えば前提技術における式４９に示されている。本実施形態では、ＣＰＦにおける画像マッチングの際得られるこのマッチングエネルギーをいわば副産物として利用する。前提技術の画像マッチングでは、キーフレーム間の各画素につき、写像のエネルギーが最小となるものを対応点として検出する。前提技術のこのような特徴に着目すれば、マッチングエネルギーの低い画素に関しては良好なマッチングがとれており、一方マッチングエネルギーの高い箇所については、当然キーフレーム間で位置や画素値の変化の大きい画素であったはずであるが、場合によってはマッチングエラーがあった可能性もあると評価できる。以下詳説するが、本実施形態ではマッチング精度の高い部分については差分の圧縮率を高める。また別の例では、マッチングエラーが推定される画素に関する差分情報を高く圧縮しても良い。【０１８１】
［１］符号化処理
本実施形態の符号化装置では、ＣＰＦが第１、第２のキーフレームのマッチングを計算する際に、併せて両フレーム間で対応しあう各画素のマッチングエネルギーを取得し、第１のキーフレーム（Ｆ０）上に各画素のマッチングエネルギーを記述したエネルギーマップを生成する。同様に、その他の隣接しあうキーフレーム間でもエネルギーマップを生成する。すなわち、エネルギーマップとは、キーフレーム間の対応点それぞれのマッチングエネルギーを、基本的には前のキーフレームの各画素に関して記述したデータである。なお、エネルギーマップは前後のキーフレームのうち、後のキーフレーム上に表しても良い。エネルギーマップは不図示の経路によりＣＰＦからＤＥ＋ＮＲに送られる。ＤＥ＋ＮＲでは、このエネルギーマップを利用してキーフレーム間のマッチングの良否を評価し、それに基づいて、仮想のキーフレームと現実のキーフレームの差分を適応的に圧縮符号化する。なお、ＤＥ＋ＮＲには、エネルギーマップの他、対応点情報ファイルも不図示の経路で送られている。【０１８２】
図２５は、本実施形態に係る図２３のＤＥ＋ＮＲの構成を示す図である。図２５のＤＥ＋ＮＲは差分計算器１０と、差分圧縮部１２と、エネルギー取得部１４と、判定部１６とを備える。このうち、前２者が専らＤＥに相当し、後２者が専らＮＲに相当する。以下第１のキーフレーム（Ｆ０）と第２のキーフレーム（Ｆ４）およびその中間の画像フレーム（Ｆ１〜Ｆ３）を符号化する際のＤＥ＋ＮＲの動作を説明するが、後続の各キーフレーム、画像フレームの符号化においても、ＤＥ＋ＮＲの動作は同様である。【０１８３】
差分計算器１０は、現実の第２キーフレーム（Ｆ４）と仮想の第２キーフレーム（Ｆ４’）を取得して、位置的に対応しあう画素どうしの画素値の差分をとる。これにより、各画素が両キーフレーム間の画素値の差をもつ一種の画像が形成され、これを差分画像と呼ぶ。差分画像はエネルギー取得部１４へと送られる。また、エネルギー取得部１４には、現実の第１キーフレーム（Ｆ０）と現実の第２キーフレーム（Ｆ４）の間のエネルギーマップ及び対応点情報（Ｍ０−４）が、図２３のＣＰＦから入力される。エネルギー取得部１４は、これらを利用して差分画像のマッチングエネルギーを取得する。【０１８４】
まず、取得部１４は、第１、第２キーフレーム間の対応点情報（Ｍ０−４）をＣＰＦから取得する。これを利用して、差分画像から仮想の第２キーフレーム（Ｆ４’）、第１キーフレーム（Ｆ０）とたどっていくことで、差分画像のどの画素が第１キーフレーム（Ｆ０）のどの画素をシフトしたものに対応しているか、対応関係を取得する。その上で第１キーフレーム上に表されたエネルギーマップ上の各画素のエネルギーを参照し、差分画像の各画素に対応する第１キーフレーム（Ｆ０）上の画素のマッチングエネルギーを、差分画像の各画素のマッチングエネルギーとして取得する。差分画像のマッチングエネルギーはこうして求められる。【０１８５】
エネルギー取得部１４は、差分画像のマッチングエネルギーを判定部１６へと送る。判定部１６は差分画像の各画素のマッチングエネルギーを利用して、差分画像のうち高圧縮対象領域を判定し、いずれの領域を高圧縮すべきかの情報を圧縮部１２へと通知する。判定は例えば以下のように行われる。判定部１６は、差分画像を１６Ｘ１６画素単位のブロックに分割し、各ブロックに含まれる画素の全てについてマッチングエネルギーを所定のしきい値と比較する。比較の結果、ブロック内の全ての画素のマッチングエネルギーがしきい値以下であった場合は、その領域を高圧縮対象ブロックと判定する。【０１８６】
圧縮部１２は、差分画像をＪＰＥＧ形式にて圧縮する。この際、判定部１６から通知された高圧縮対応領域の情報を利用し、圧縮率を通常の領域と高圧縮対応領域との間で適応的に変化させる。具体的には、高圧縮対象ブロックはＤＣＴ係数の量子化幅を通常のブロックに比べて大きくする処理などが利用できる。別の例では、差分画像では、高圧縮対象ブロックの画素値を０にしてしまってからＪＰＥＧ圧縮をかける処理を行ってもよい。いずれにせよ、マッチングエネルギーが低い領域を高圧縮する理由は以下の考え方による。【０１８７】
すなわち、上述のごとくマッチングエネルギーの低い画素は、キーフレーム間のマッチング結果が良好であるとみなせる。従って、差分画像のうちマッチングエネルギーが低い部分に関しては、現実の第２のキーフレーム（Ｆ４）と仮想の第２のキーフレーム（Ｆ４’）の間に差分は本来生じにくく、差分が生じているとすればそれはノイズであると考えてよい。よって、差分画像においてマッチングエネルギーが低い領域は、高圧縮による情報の欠落を気にすることなく、他の領域に比べて大幅に圧縮できる。一方、マッチングエネルギーの大きい領域については、マッチングにエラーが生じている可能性もあり、仮想の第２キーフレーム（Ｆ４’）と現実の第２キーフレーム（Ｆ４）の差分は復号において重要な情報であるため、圧縮率を低くとどめ、復号時の正確性を優先する。【０１８８】
［２］第３の実施の形態によるメリット
以上の処理を経て、圧縮部１８は、現実の第２キーフレーム（Ｆ４）と仮想の第２キーフレーム（Ｆ４’）の圧縮符号化された差分（Δ４）を出力する。本実施形態による符号化装置によれば、現実のキーフレームと仮想のキーフレームの差分情報を、符号化画像をより原画像に忠実に、正確な復号を行うための重要性に応じて適応的に圧縮可能であり、復号の正確性を保ちつつ高い符号化効率が実現できる。重要性とは、もちろん、本実施形態でも第１実施形態に係るメリットを享受できる。【０１８９】
［３］第３の実施の形態の変形技術
本実施形態の変形例として、マッチングエネルギーの大きい画素、中でも近傍の画素の対応傾向と著しく異なる対応傾向を示す画素はマッチングエラーを起こしている場合が多いと経験的に認められることから、マッチングエネルギーが周囲の画素と比べ大幅に異なる画素をマッチングエラーと評価し、これをノイズリダクションに導入することもできる。この場合、ＤＥ+ＮＲは、第２キーフレーム（Ｆ４）の各画素のマッチングエネルギーを、例えば自身を中心とする９Ｘ９画素のブロック内の、他の画素のマッチングエネルギーの平均と比較する。比較の結果両者の差が所定のしきい値を超えている場合、そのような画素はマッチングエラーをおこしていると判定してもよい。【０１９０】
エラーを起こしている対応情報は復号側にとって無意味なデータであると考えることができ、現実の第２キーフレーム（Ｆ４）と仮想の第２キーフレーム（Ｆ４’）間の差分情報中では、マッチングエラーを起こしている画素に関するデータはノイズといえる。よって、高圧縮による情報の欠落への配慮を不要とし、ＤＥ＋ＮＲは、現実のキーフレームと仮想のキーフレーム間の差分画像のうち、現実のキーフレーム間のマッチングエラーに対応する画素を他の画素に比べて高い率で圧縮する。なお、マッチングエラーの判定は、例えば、周囲の画素の動きベクトルの傾向と、注目する画素の動きベクトルの傾向を比較し、注目する画素の動きベクトルが周囲の傾向と著しく異なるか否かをもって行なっても良い。【０１９１】
第３実施形態においても、第２実施形態と同様に、第１、第２キーフレーム（Ｆ０、Ｆ４）間の中間フレーム（Ｆ１〜Ｆ３）を考慮し、これら全ての画像フレームの隣り合うそれぞれの組についてマッチングを計算して対応点情報ファイル（Ｍ０〜Ｍ３）を生成し、それらを統合して第１、第２キーフレーム（Ｆ０、Ｆ１）間で一つの対応点情報ファイルを得る変形技術が考えられる。第１実施形態の変形技術同様、マッチング精度を向上し、正確な動画復号が実現できる。【０１９２】
さらに、この変形技術では、各画像フレーム間のマッチングエネルギーを計算してそれをシーンチェンジ検出等に応用可能である。シーンチェンジ検出に係る構成は以下のとおりである。まず、ＣＰＦはＦ０とＦ１、Ｆ１とＦ２、Ｆ２とＦ３，Ｆ３とＦ４・・・それぞれの組について、マッチング計算をおこない、その副産物としてエネルギーマップ、Ｅ０、Ｅ１、Ｅ２、Ｅ３・・・を取得する。ここで、ある画像フレーム全体の画素に係るマッチングエネルギーの平均をとり、それを所定のシーンチェンジ検出用しきい値と比較し、その直後の画像を新たなグループとすればよい。例えばＦ５とＦ６の間のエネルギーマップＥ５に基づき、Ｆ５とＦ６のマッチングに係るＦ５の各画素のマッチングエネルギーを平均した結果、その値がキーフレーム追加用しきい値を越えたとする。この場合、直後のキーフレームすなわちＦ６以下を新たなグループとし、Ｆ６が次のグループの第１キーフレームとすればよい。マッチングエネルギーが大きい場合、画像間に大きな変化があったと考えることができるためである。これにより、自動的なシーンチェンジの検出ができ、シーンチェンジに対応してグループの選定が可能となる。【０１９３】
各エネルギーマップに基づいて、各画像フレーム内画素の平均マッチングエネルギーを計算して、これを累積的に加算していき、その値が所定のしきい値を越えた時点でその画像フレームを新たにキーフレームとして登録しても良い。画像フレーム間の変化量の累積がある一定値を越えた時点でキーフレームを追加できれば、より復号時の画質の向上が図れるためである。
【産業上の利用可能性】
【０１９４】
本発明は、画像圧縮処理技術の分野に利用することができる。
【図１】
2007069350.tif 000068
【図２】
2007069350.tif 000069
【図３】
2007069350.tif 000070
【図４】
2007069350.tif 000071
【図５】
2007069350.tif 000072
【図６】
2007069350.tif 000073
【図７】
2007069350.tif 000074
【図８】
2007069350.tif 000075
【図９】
2007069350.tif 000076
【図１０】
2007069350.tif 000077
【図１１】
2007069350.tif 000078
【図１２】
2007069350.tif 000079
【図１３】
2007069350.tif 000080
【図１４】
2007069350.tif 000081
【図１５】
2007069350.tif 000082
【図１６】
2007069350.tif 000083
【図１７】
2007069350.tif 000084
【図１８】
2007069350.tif 000085
【図１９】
2007069350.tif 000086
【図２０】
2007069350.tif 000087
【図２１】
2007069350.tif 000088
【図２２】
2007069350.tif 000089
【図２３】
2007069350.tif 000090
【図２４】
2007069350.tif 000091
【図２５】
2007069350.tif 000092
【手続補正書】
【提出日】平成19年3月20日(2007.3.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画像フレームの列を降順または昇順にＦ０、Ｆ１、・・・、Ｆｎ−１、Ｆｎ（ｎは２以上の整数）と表記し、画像フレームＦｉ、Ｆｊ（ｉ，ｊ＝０，１，・・・，ｎ）間で対応しあう点の位置関係を示す対応点情報をＭｉ−ｊと表記するとき、
ａ）Ｆ０とＦｎ間でマッチングを計算してＭ０−ｎを生成するステップと、
ｂ）Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ上でｐ０に対応する点ｐｎを算出するステップと、
ｃ）ステップｂをＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１、点ｐ２の集合を利用して仮想的なＦ２、・・・、点ｐｎの集合を利用して仮想的なＦｎをそれぞれ生成するステップと、
ｄ）仮想的なＦ１と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組に対し、その組に含まれる画像フレーム間の差分が大きな組Ｓｋ（ｋ＝１，・・・，ｎ）の有無を所定の判定基準をもとに判定するステップと、
ｅ）差分が大きな組Ｓｋが存在する場合、少なくとも、Ｆｈ（ｈ＝０，１，・・・，ｋ−１）とＦｋ間でマッチングを計算してＭｈ−ｋを生成するステップと、
ｆ）Ｍｈ−ｋの情報を利用し、Ｍ０−ｎを修正するステップと、
ｇ）復号側においてステップｂ、ｃと同様の手順によりＦ０と修正されたＭ０−ｎを利用して仮想的なＦ１’、Ｆ２’、・・・Ｆｋ’、・・・Ｆｎ−１’を生成するために、少なくともＦ０と修正されたＭ０−ｎを含み、Ｆｋを含まない形式の符号化データを出力するステップと、
を含むことを特徴とする画像符号化方法。
【請求項２】
請求項１に記載の方法において、ステップｄは、画像フレーム間の差分の大きさを所定の領域単位で判定することを特徴とする画像符号化方法。
【請求項３】
請求項１に記載の方法において、ステップｅは、
ｅ１）差分が大きな組Ｓｋが存在する場合、Ｆ０とＦ１間のＭ０−１、Ｆ１とＦ２間のＭ１−２、・・・、Ｆｋ−１とＦｋ間のＭ（ｋ−１）−ｋをそれぞれ求めるステップと、
ｅ２）Ｍ０−１、Ｍ１−２、・・・、Ｍ（ｋ−１）−ｋを統合してＭ０−ｋを生成するステップと、
を含むことを特徴とする画像符号化方法。
【請求項４】
請求項３に記載の方法において、ステップｅ２は、Ｍ０−１によってｐ０に対応するｐ１を求め、Ｍ１−２によってｐ１に対応するｐ２を求め、・・・、Ｍ（ｋ−１）−ｋによってｐｋ−１に対応するｐｋを求め、ｐ０に対応する点をｐ１、ｐ２、・・・、ｐｋと順に特定することにより、最終的にｐ０に対応するｐｋを特定してＭ０−ｋを生成することを特徴とする画像符号化方法。
【請求項５】
請求項４に記載の方法において、ステンプｆは、Ｍ０−ｋの情報を利用し、ｐ０がｐｋを経てｐｎへ至る軌跡を示す形式にて、修正されたＭ０−ｎを生成することを特徴とする画像符号化方法。
【請求項６】
請求項１に記載の方法において、ステップｄにて差分が大きな組Ｓｋが存在することが判明した場合、ステップｇはＦ０と修正されたＭ０−ｎに加え、組Ｓｋにおける差分の情報を含む形式の符号化データを出力することを特徴とする画像符号化方法。
【請求項７】
請求項６に記載の方法において、組Ｓｋにおける差分の情報は、画像フレームの中で差分が大きかった領域についてのみ符号化データへ含められることを特徴とする画像符号化方法。
【請求項８】
請求項７に記載の方法において、差分とともに、少なくともｋの値と前記領域の位置情報が符号化データへ含められることを特徴とする画像符号化方法。
【請求項９】
請求項８に記載の方法において、差分は圧縮処理を受けた後、符号化データへ含められることを特徴とする画像符号化方法。
【請求項１０】
画像フレームの列を降順または昇順にＦ０、Ｆ１、・・・、Ｆｎ−１、Ｆｎ（ｎは２以上の整数）と表記し、画像フレームＦｉ、Ｆｊ（ｉ，ｊ＝０，１・・・，ｎ）間で対応しあう点の位置関係を示す対応点情報をＭｉ−ｊと表記するとき、
Ｆ０とＦｎ間でマッチングを計算してＭ０−ｎを生成するマッチング処理部と、
Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ上でｐ０に対応する点ｐｎを算出する処理をＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１、点ｐ２の集合を利用して仮想的なＦ２、・・・、点ｐｎの集合を利用して仮想的なＦｎをそれぞれ生成する中間フレーム生成部と、
仮想的なＦ１と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組に対し、その組に含まれる画像フレーム間の差分が大きな組Ｓｋ（ｋ＝１，・・・，ｎ）の有無を所定の判定基準をもとに判定する判定部と、
を備え、前記マッチング処理部は、差分が大きな組Ｓｋが存在する場合、少なくとも、Ｆｈ（ｈ＝０，１，・・・，ｋ−１）とＦｋ間でマッチングを計算してＭｈ−ｋを生成し、このＭｈ−ｋの情報を利用してＭ０−ｎを修正し、
本装置はさらに、復号側においてＦ０と修正されたＭ０−ｎを利用して仮想的なＦ１’、Ｆ２’、・・・Ｆｋ’、・・・Ｆｎ−１’を生成するために、少なくともＦ０と修正されたＭ０−ｎを含み、Ｆｋを含まない形式の符号化データを出力する出力部を含むことを特徴とする画像符号化装置。
【請求項１１】
３以上の画像フレームを含む画像グループの両端画像フレーム間でマッチング計算を実行するステップと、
マッチング計算の結果得られた両端画像フレーム間の対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成するステップと、
画像上のいずれかの領域について、仮想的に生成された中間画像フレームのうちいずれかが、現実の中間画像フレームと許容値以上の差分を有するか否かを所定の判定基準のもとで判定する判定ステップと、
両端画像フレームのうち少なくとも一方と、対応点情報とを含む符号化データを生成し、さらに、前記判定ステップにおいて、許容値以上の差分を有する領域が存在すると判定された場合には、その領域に関する差分情報を前記符号化データに含めて生成するステップと、
を含むことを特徴とする画像符号化方法。
【請求項１２】
３以上の画像フレームを含む画像グループの両端画像フレーム間でマッチング計算を実行するマッチング処理部と、
マッチング計算の結果得られた両端画像フレーム間の対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する中間フレーム生成部と、
画像上のいずれかの領域について、仮想的に生成された中間画像フレームのうちいずれかが、現実の中間画像フレームと許容値以上の差分を有するか否かを所定の判定基準のもとで判定する判定部と、
両端画像フレームのうち少なくとも一方と、対応点情報とを含む符号化データを出力し、さらに、前記判定部において、許容値以上の差分を有する領域が存在すると判定された場合には、その領域に関する差分情報を出力する出力部と、
を含むことを特徴とする画像符号化装置。
【請求項１３】
画像フレームの列を降順または昇順にＦ０、Ｆ１、・・・、Ｆｎ−１、Ｆｎ（ｎは２以上の整数）と表記し、画像フレームＦｉ、Ｆｊ（ｉ，ｊ＝０，１，・・・，ｎ）間で対応しあう点の位置関係を示す対応点情報をＭｉ−ｊと表記するとき、
ｐ）少なくともＦ０、Ｍ０−ｎおよび所定の差分情報を含む形式の符号化データを入力するステップと、
ｑ）Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路をｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ−１上でｐ０に対応する点ｐｎ−１を算出するステップと、
ｒ）ステップｑをＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１、点ｐ２の集合を利用して仮想的なＦ２、・・・、点ｐｎの集合を利用して仮想的なＦｎをそれぞれ生成するステップと、
ｓ）仮想的なＦ１と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組のうち、前記差分情報が与えられているＳｋ（ｋ＝１，・・・，ｎ）を特定するステップと、
ｔ）仮想的なＦｋに対し、前記差分情報によって定まる差分を加算することにより、修正された仮想的なＦｋを生成するステップと、
ｕ）復号結果として、Ｆ０、仮想的なＦ１、仮想的なＦ２、・・・、修正された仮想的なＦｋ、仮想的なＦｋ＋１、・・・、仮想的なＦｎ−１を出力するステップと、
を含むことを特徴とする画像復号方法。
【請求項１４】
請求項１３に記載の方法において、前記差分情報は画像フレーム間の差分が大きな領域についてのみ差分を記述しており、ステップｔは差分を加算する際、前記領域の位置情報を特定することを特徴とする画像復号方法。
【請求項１５】
請求項１３に記載の方法において、前記差分情報は圧縮されており、ステップｔは前記差分情報を伸長してから加算することを特徴とする画像復号方法。
【請求項１６】
請求項１３に記載の方法において、Ｍ０−ｎは、ｐ０がｐｋを経てｐｎへ至る軌跡を示す形式にて生成されていることを特徴とする画像復号方法。
【請求項１７】
画像フレームの列を降順または昇順にＦ０、Ｆ１、・・・、Ｆｎ−１、Ｆｎ（ｎは２以上の整数）と表記し、画像フレームＦｉ、Ｆｊ（ｉ，ｊ＝０，１，・・・，ｎ）間で対応しあう点の位置関係を示す対応点情報をＭｉ−ｊと表記するとき、
少なくともＦ０、Ｍ０−ｎおよび所定の差分情報を含む形式の符号化データを入力する入力部と、
Ｆ０上の点ｐ０をＭ０−ｎによってＦｎ上の対応する点ｐｎに移動させる経路ｎ分割し、Ｆ１上でｐ０に対応する点ｐ１、Ｆ２上でｐ０に対応する点ｐ２、・・・、Ｆｎ−１上でｐ０に対応する点ｐｎ−１を算出する処理をＦ０上の所定数の点について実行することにより、当該所定数の点に対応する点ｐ１の集合を利用して仮想的なＦ１、点ｐ２の集合を利用して仮想的なＦ２、・・・、点ｐｎの集合を利用して仮想的なＦｎをそれぞれ生成する中間フレーム生成部と、
仮想的なＦ１と現実のＦ１の組Ｓ１、仮想的なＦ２と現実のＦ２の組Ｓ２、・・・、仮想的なＦｎと現実のＦｎの組Ｓｎの各組のうち、前記差分情報が与えられているＳｋ（ｋ＝１，・・・，ｎ）を特定する特定部と、
仮想的なＦｋに対し、前記差分情報によって定まる差分を加算することにより、修正された仮想的なＦｋを生成する中間フレーム修正部と、
復号結果として、Ｆ０、仮想的なＦ１、仮想的なＦ２、・・・、修正された仮想的なＦｋ、仮想的なＦｋ＋１、・・・、仮想的なＦｎ−１を出力する出力部と、
を含むことを特徴とする画像復号装置。
【請求項１８】
３以上の画像フレームを含む画像グループの両端画像フレームのうちの一方と、それら両端画像フレーム間の対応点情報と、所定の差分情報とを含む符号化データを入力するステップと、
前記対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成するステップと、
仮想的に生成された中間画像フレームそれぞれとそれに対応する現実の中間画像フレームとによる組のうち、差分が大きな組として符号化データ内に記述された組の中間画像フレームの画像上にて差分が大きい領域を特定するステップと、
差分が大きな組に含まれる仮想的な画像フレームに対し、前記領域における差分を加算することにより、修正された仮想的な画像フレームを生成するステップと、
復号結果として、両端画像フレームのうちの一方と、差分が大きな組については修正された仮想的な中間画像フレームと、それ以外の組については仮想的な中間画像フレームとを復号データとして出力するステップと、
を含むことを特徴とする画像復号方法。
【請求項１９】
３以上の画像フレームを含む画像グループの両端画像フレームのうちの一方と、それら両端画像フレーム間の対応点情報と、所定の差分情報とを含む符号化データを入力する入力部と、
前記対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する中間フレーム生成部と、
仮想的に生成された中間画像フレームそれぞれとそれに対応する現実の中間画像フレームとによる組のうち、差分が大きな組として符号化データ内に記述された組の中間画像フレームの画像上にて差分が大きい領域を特定する領域特定部と、
差分が大きな組に含まれる仮想的な画像フレームに対し、前記領域における差分を加算することにより、修正された仮想的な画像フレームを生成する中間フレーム修正部と、
復号結果として、両端画像フレームのうちの一方と、差分が大きな組については修正された仮想的な中間画像フレームと、それ以外の組については仮想的な中間画像フレームとを復号データとして出力する出力部と、
を含むことを特徴とする画像復号装置。
【請求項２０】
請求項１１に記載の画像符号化方法の各ステップをコンピュータに実行せしめることを特徴とするコンピュータプログラム。
【請求項２１】
請求項１８に記載の画像復号方法の各ステップをコンピュータに実行せしめることを特徴とするコンピュータプログラム。
【請求項２２】
画像符号化ユニットと画像復号ユニットとを有する画像処理システムにおいて、
画像符号化ユニットは、
３以上の画像フレームを含む画像グループの両端画像フレーム間でマッチング計算を実行するマッチング処理部と、
マッチング計算の結果得られた両端画像フレーム間の対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する符号化側中間フレーム生成部と、
画像上のいずれかの領域について、仮想的に生成された中間画像フレームのうちいずれかが、現実の中間画像フレームと許容値以上の差分を有するか否かを所定の判定基準のもとで判定する判定部と、
両端画像フレームのうち少なくとも一方と、対応点情報とを含む符号化データをメモリへ書き込み、さらに許容値以上の差分を有する領域が存在すると判定された場合、その領域に関する差分情報を書き込む書込制御部とを備え、
画像復号ユニットは、
前記メモリから符号化データを読み出す読出制御部と、
符号化データに含まれる画像フレームのデータと対応点情報をもとに、両端画像フレームに挟まれる中間画像フレームを内挿補間によって仮想的に生成する復号側中間フレーム生成部と、
符号化データに差分情報が含まれる領域を特定する領域特定部と、
特定された領域を含む仮想的な画像フレームに対し、前記領域における差分を加算することにより、修正された仮想的な画像フレームを生成する中間フレーム修正部と、
復号結果として、両端画像フレームのうちの一方または双方と、前記領域を含む仮想的な画像フレームについては修正された仮想的な中間画像フレームと、前記領域を含まない仮想的な画像フレームについてはその仮想的な中間画像フレーム自体とを復号データとして出力する出力部と、
を含むことを特徴とする画像処理システム。
【国際調査報告】
2007069350.tif 000093
2007069350.tif 000094
2007069350.tif 000095
2007069350.tif 000096