(57)【要約】      （修正有）【課題】画像間の対応点情報の量を低減させつつ中間フレームの画質を維持できる対応点情報圧縮方法を提供する。【解決手段】第１の画像の画素について、その第２の画像における対応画素を比較的密に記述する原始マップファイルＭＦＡを読み込むステップと、第１の画像をメッシュ分割し、各メッシュの頂点に当たる画素についてのみ対応画素を残すことによって原始マップファイルを圧縮し、対応画素を比較的疎に記述する簡素化マップファイルＭＦＢを生成するステップと、を含み、前記生成するステップは、前記メッシュを非正則に分割し、原始マップファイルと簡素化マップファイルの差違に起因する誤差を低減するように前記メッシュを細分化するステップと、を有する。【選択図】        図１
2004297416.tif 000002
【特許請求の範囲】
【請求項１】
第１の画像の画素について、その第２の画像における対応画素を比較的密に記述する原始マップファイルを読み込むステップと、
第１の画像をメッシュ分割し、各メッシュの頂点に当たる画素についてのみ対応画素を残すことによって原始マップファイルを圧縮し、対応画素を比較的疎に記述する簡素化マップファイルを生成するステップと、
を含み、前記生成するステップは、前記メッシュを非正則に分割することを特徴とする対応点情報圧縮方法。
【請求項２】
請求項１に記載の方法において、前記生成するステップは、簡素化マップファイルと原始マップファイルの差違に起因する誤差を低減するよう前記メッシュを細分化する対応点情報圧縮方法。
【請求項３】
請求項２に記載の方法において、前記誤差が大きな領域についてメッシュを再分割する対応点情報圧縮方法。
【請求項４】
請求項１に記載の方法において、前記生成するステップは、第１の画像をふたつの三角形に分割し、分割によって得られた三角形のうち所定の三角形を再分割する処理を繰り返すことにより、前記メッシュを生成する対応点情報圧縮方法。
【請求項５】
請求項４に記載の方法において、前記所定の三角形として、当該三角形の領域における誤差が大きなものが選択されることを特徴とする対応点情報圧縮方法。
【請求項６】
請求項５に記載の方法において、前記誤差は、前記所定の三角形の３個の頂点画素の対応画素から非頂点画素の対応画素の位置を導出したとき、導出された位置と、前記非頂点画素の対応画素の本来の位置との誤差として求められる対応点情報圧縮方法。
【請求項７】
請求項４に記載の方法において、三角形を分割したとき、その分割によって新たに生じた三角形の頂点が他の三角形の辺上に置かれたとき、当該他の三角形を分割し、いずれの三角形についても辺上に別の三角形の頂点が存在しない状態を維持する対応点情報圧縮方法。
【請求項８】
第１の画像の画素について、その第２の画像における対応画素を比較的密に記述する原始マップファイルを読み込むステップと、
第１の画像をメッシュ分割し、各メッシュの頂点に当たる画素についてのみ対応画素を残すことによって原始マップファイルを圧縮し、対応画素を比較的疎に記述する簡素化マップファイルを生成するステップと、
を含み、前記生成するステップは、前記メッシュを所定の条件が満たされるまで細分化し、その結果得られたメッシュについて前記簡素化マップファイルを生成することを特徴とする対応点情報圧縮方法。
【請求項９】
請求項８に記載の方法において、前記所定の条件として、簡素化マップファイルと原始マップファイルの差違に起因する誤差が所定のしきい値以内に収まることを設定した対応点情報圧縮方法。
【請求項１０】
請求項８に記載の方法において、前記所定の条件として、メッシュによって分割される領域の数が所定のしきい値以内に収まることを設定した対応点情報圧縮方法。
【請求項１１】
請求項８に記載の方法において、前記所定の条件として、簡素化マップファイルのデータサイズが所定のしきい値以内に収まることを設定した対応点情報圧縮方法。
【請求項１２】
請求項８に記載の方法において、前記所定の条件として、前記細分化のための分割の回数が所定のしきい値以内に収まることを設定した対応点情報圧縮方法。
【請求項１３】
第１の画像の画素について、その第２の画像における対応画素を比較的密に記述する原始マップファイルを読み込む入力部と、
第１の画像をメッシュ分割し、各メッシュの頂点に当たる画素についてのみ対応画素を残すことによって原始マップファイルを圧縮し、対応画素を比較的疎に記述する簡素化マップファイルを生成する制御部と、
を含み、前記制御部は、前記メッシュを非正則に分割することを特徴とする対応点情報圧縮装置。
【請求項１４】
第１の画像の画素について、その第２の画像における対応画素を比較的密に記述する原始マップファイルを読み込む入力部と、
第１の画像をメッシュ分割し、各メッシュの頂点に当たる画素についてのみ対応画素を残すことによって原始マップファイルを圧縮し、対応画素を比較的疎に記述する簡素化マップファイルを生成する制御部と、
を含み、前記制御部は、前記メッシュを所定の条件が満たされるまで細分化し、その結果得られたメッシュについて前記簡素化マップファイルを生成することを特徴とする対応点情報圧縮装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、対応点情報圧縮技術に関する。この発明はとくに、画像間の対応点情報を圧縮する方法と装置に関する。
【０００２】
【従来の技術】
動画像のデータを圧縮する際、ある程度時間的に離れた画像フレーム間の対応点を検出し、この対応点情報をもとに画像フレーム間を補間して生成することにより、画像フレームを間引く技術が知られている。特許文献１はそうした技術である。なお、間引かれないでそのまま利用される画像フレームを以下「キーフレーム」とよび、キーフレーム間の補間で生成される画像フレームを以下「中間フレーム」とよぶ。
【０００３】
【特許文献１】
特許第２９２７３５０号公報  （全文）
【０００４】
【発明が解決しようとする課題】
特許文献１では、キーフレーム間で画素単位の対応点を検出しており、対応点情報の量が比較的大きくなる。これを単純に間引くことも考えられるが、その場合、当然中間フレームの画質とのトレードオフになる。
【０００５】
本発明はこうした実情に鑑みてなされたものであり、対応点情報の量を低減させつつ中間フレームの画質を維持できる技術の提供を目的とする。
【０００６】
【課題を解決するための手段】
本発明のある態様は、対応点情報圧縮方法に関し、第１の画像の画素について、その第２の画像における対応画素を比較的密に記述する原始マップファイルを読み込むステップと、第１の画像をメッシュ分割し、各メッシュの頂点に当たる画素についてのみ対応画素を残すことによって原始マップファイルを圧縮し、対応画素を比較的疎に記述する簡素化マップファイルを生成するステップとを含み、前記生成するステップは、前記メッシュを非正則に分割する。
【０００７】
前記生成するステップは、簡素化マップファイルと原始マップファイルの差違に起因する誤差を低減するよう前記メッシュを細分化してもよい。また、誤差が大きな領域についてメッシュを再分割してもよい。
【０００８】
前記生成するステップは、第１の画像をふたつの三角形に分割し、分割によって得られた三角形のうち所定の三角形を再分割する処理を繰り返すことにより、前記メッシュを生成してもよい。また、所定の三角形として、当該三角形の領域における誤差が大きなものが選択されてもよい。この誤差は、前記所定の三角形の３個の頂点画素の対応画素から非頂点画素の対応画素の位置を導出したとき、導出された位置と、前記非頂点画素の対応画素の本来の位置との誤差として求められてもよい。
【０００９】
三角形を分割したとき、その分割によって新たに生じた三角形の頂点が他の三角形の辺上に置かれたとき、当該他の三角形を分割し、いずれの三角形についても辺上に別の三角形の頂点が存在しない状態を維持してもよい。
【００１０】
本発明の別の態様も対応点情報圧縮方法に関し、第１の画像の画素について、その第２の画像における対応画素を比較的密に記述する原始マップファイルを読み込むステップと、第１の画像をメッシュ分割し、各メッシュの頂点に当たる画素についてのみ対応画素を残すことによって原始マップファイルを圧縮し、対応画素を比較的疎に記述する簡素化マップファイルを生成するステップとを含み、前記生成するステップは、前記メッシュを所定の条件が満たされるまで細分化し、その結果得られたメッシュについて前記簡素化マップファイルを生成する。
【００１１】
所定の条件として、簡素化マップファイルと原始マップファイルの差違に起因する誤差が所定のしきい値以内に収まること、メッシュによって分割される領域の数が所定のしきい値以内に収まること、簡素化マップファイルのデータサイズが所定のしきい値以内に収まること、細分化のための分割の回数が所定のしきい値以内に収まることなどを設定してもよい。
【００１２】
本発明のさらに別の態様は、対応点情報圧縮装置に関し、第１の画像の画素について、その第２の画像における対応画素を比較的密に記述する原始マップファイルを読み込む入力部と、第１の画像をメッシュ分割し、各メッシュの頂点に当たる画素についてのみ対応画素を残すことによって原始マップファイルを圧縮し、対応画素を比較的疎に記述する簡素化マップファイルを生成する制御部とを含み、前記制御部は、前記メッシュを非正則に分割する。
【００１３】
本発明のさらに別の態様も対応点情報圧縮装置に関し、第１の画像の画素について、その第２の画像における対応画素を比較的密に記述する原始マップファイルを読み込む入力部と、第１の画像をメッシュ分割し、各メッシュの頂点に当たる画素についてのみ対応画素を残すことによって原始マップファイルを圧縮し、対応画素を比較的疎に記述する簡素化マップファイルを生成する制御部とを含み、前記制御部は、前記メッシュを所定の条件が満たされるまで細分化し、その結果得られたメッシュについて前記簡素化マップファイルを生成する。
【００１４】
【発明の実施の形態】
図１は、実施の形態に係る対応点情報生成装置１０の構成を示す。この装置１０は、キーフレームＫＦ１，２を格納している保持部１８と、キーフレームＫＦ１，２間で画像マッチングをとり、対応点情報を記述した原始マップファイルＭＦＡを生成するるマッチングプロセッサ２２と、原始マップファイルＭＦＡを圧縮する圧縮装置１２とを含む。
【００１５】
圧縮装置１２は、原始マップファイルＭＦＡを入力する入力部１４と、原始マップファイルＭＦＡに圧縮処理を施す制御部１６を含む。
【００１６】
マッチングプロセッサ２２による画像間マッチングは、例えば本出願人に係る特許第２９２７３５０号の特異点を用いた画素単位のマッチングによる。ただし、これ以外に、オプティカルフローその他の方法を利用してもよい。
【００１７】
原始マップファイルＭＦＡは、ある程度密に画素間の対応を記述する。ここでは、第１キーフレームＫＦ１の各画素について、その画素が第２キーフレームＫＦ２のいずれの画素に対応するかを動きベクトルで記述している。
【００１８】
図２は、原始マップファイルＭＦＡの構成を示す。各画素ｐ（ｉ，ｊ）が第２キーフレームＫＦ２で対応する画素にどう移動するかがベクトルｖｉｊで示される。例えば、第１キーフレームＫＦ１の座標（１０，１５）の画素が第２キーフレームＫＦ２で座標（２０，１７）の画素に対応する場合、この画素のベクトルは（１０，−２）と記述される。
【００１９】
原始マップファイルＭＦＡはすべての点、すなわちすべての画素について対応情報を持っている。しかし、制御部１６は対応情報をもたせる画素を一部に限定することで簡素化マップファイルＭＦＢを生成する。対応情報をもつ画素を「独立画素」とよぶ。独立画素以外の画素（「従属画素」とよぶ）の対応情報は、独立画素の対応情報から必要なときに補間で求めることができる。この補間で従属画素の対応情報を求めるとき、当然ながら、当該従属画素が最初に原始マップファイルＭＦＡにおいてもっていた対応情報との誤差が小さいことが望ましい。そのため、制御部１６は、その誤差を評価し、誤差が小さくなるよう独立画素を決めていく。
【００２０】
図３は原始マップファイルＭＦＡ全体を模式的に示す。誤差評価のために、補間の概要を示す。いま、原始マップファイルＭＦＡを画像に見立て、それを中央の斜線でふたつの三角形に分割する。いま、同図において上側の三角形の頂点Ａ、Ｂ、Ｃは、それぞれ当該位置にある画素に対応し、それぞれ対応情報としてベクトルｖａ、ｖｂ、ｖｃをもつ。三角形ＡＢＣについては、独立画素がＡＢＣの３点しかない。任意の点Ｐのベクトルｖｐは以下の式で求められる。
【００２１】
ｖｐ＝Ｓａ・ｖａ＋Ｓｂ・ｖｂ＋Ｓｃ・ｖｃ
ただし、Ｓａ、Ｓｂ、Ｓｃはそれぞれ三角形ＰＢＣ、ＰＡＣ、ＰＡＢの面積であり、Ｓａ＋Ｓｂ＋Ｓｃ＝１に正規化する。こうして求められたｖｐと、点Ｐが原始マップファイルＭＦＡにおいて持っていたベクトルｖｐ＿ｏｒｉｇｉｎａｌの差の絶対値を点Ｐにおける誤差「Ｅｐ」と表記する。
【００２２】
三角形ＡＢＣ全体としての誤差を評価する。評価は、三角形ＡＢＣ内のすべての点ＰについてＥｐを計算し、その最大値をもって三角形ＡＢＣの「誤差評価値」とし、以下、誤差評価値を三角形の「エネルギー」とよぶ。ただし、エネルギーは、すべての点Ｐの誤差の絶対値の平均や、同二乗平均など、いくつか代案がある。
【００２３】
簡素化マップファイルＭＦＢの生成は、トップダウンで行う。すなわち、最初は最小限の独立画素を仮定し、それらの独立画素でできるメッシュに含まれる三角形について、そのエネルギーが大きいものから順に再分割し、メッシュを細分化していく。メッシュの頂点が独立画素として追加されていく。細分化を停止する条件は、
１．簡素化マップファイルＭＦＢと原始マップファイルＭＦＡの差違に起因する誤差、すなわちその時点でメッシュに含まれる三角形の最大エネルギーが所定のしきい値以内に収まること
２．メッシュに含まれる三角形の数が所定のしきい値以内に収まること
３．簡素化マップファイルＭＦＢのデータサイズが所定のしきい値以内に収まること
４．細分化のための分割の回数が所定のしきい値以内に収まること
などである。
【００２４】
図４は、１回目の分割（Ｓ１０）を示す。マスターラインｍｌにより、原始マップファイルＭＦＡをふたつの三角形に分ける。便宜上、上下の三角形をそれぞれＬ、Ｒと表す。図５は２回目以降の分割で現れる三角形にＬ、Ｒを与えるルールを示し、直角三角形の斜辺を下にしたとき、右の小さな三角形をＲ、左をＬとする。
【００２５】
図６は、２回目の分割（Ｓ１２）を示す。分割される三角形は、その時点で最大エネルギーをもつものである。ここでは、三角形Ｒが最大エネルギーをもつとし、それが分割される。その結果、三角形Ｒから半分のサイズの三角形が生じ、これらを三角形ＲＲ、ＲＬと表記する。
【００２６】
この時点で、点Ｐ１のごとく、三角形Ｌの斜辺上にメッシュの頂点が現れる。三角形の辺上に別の三角形の頂点（こうした頂点を孤立頂点という）が現れると、後の補間で不都合が生じうる。すなわち、三角形Ｌについてはその３個の頂点から補間をするが、三角形ＲＲ、ＲＬについては、点Ｐ１を含む頂点からそれぞれ補間をするため、点Ｐ１において不連続な補間結果が生じる。そこで制御部１６は、ある三角形の頂点が別の三角形の辺上に現れたら、その孤立頂点が存在しなくなるまで、前記別の三角形のほうを分割する。図６の場合、図７のごとく、点Ｐ２によって三角形Ｌを三角形ＬＬとＬＲへ分割する（Ｓ１４）。
【００２７】
図８は、さらに次の分割（Ｓ１６）を示す。ここでは点Ｐ３が独立画素に追加され、三角形ＲＬがふたつの三角形ＲＬＬとＲＬＲに分割されている。図９は同様の処理（Ｓ１８）で、三角形ＲＬＲが三角形ＲＬＲＲとＲＬＲＬに分割される。ここで、点Ｐ４が孤立頂点であるから、図１０のごとく、次の処理（Ｓ２０）により、点Ｐ５を設けて三角形ＬＲＲとＬＲＬを分け、後者をさらに三角形ＬＲＬＬとＬＲＬＲへ分ける。
【００２８】
図１１は、三角形の分割をツリーで示す。先頭の○はルートで、Ｓ１０でＬとＲが生成され、Ｓ１２でＲの下のＬとＲが生成され、以下同様である。孤立頂点の判定は、処理上は単純であり、ツリーの１層目と２層目で形成される段階（これを第１ステージの意味でＳＴ１と表記する）で、ノードが「Ｌ→Ｌ」または「Ｒ→Ｒ」と続いたら、この経路のＬとＲを反転された経路をツリーに追加する。これは、マスターラインｍｌをはさんでＬとＲが対象に現れる事実を利用している。図１１の場合、ＳＴ１において、Ｒ→Ｒとつづくので、Ｌ→Ｌを追加している。この経路がＳ１４における孤立頂点の解消に当たり、経路の追加が図１２に示される。
【００２９】
同様に、３層目と４層目で形成される段階ＳＴ２で、図１１のいちばん右の経路にＲ→Ｒが生じているため、この経路全体である「Ｒ→Ｌ→Ｒ→Ｒ」を反転させた「Ｌ→Ｒ→Ｌ→Ｌ」を図１３のごとく追加している。これがＳ２０における孤立頂点の解消に当たる。なお、孤立頂点の解消は、三角形を分割するたびに実行する。
【００３０】
孤立頂点解消処理を一般化すると、むしろツリーのリーフ、すなわち末端から辿ることが簡単であり、以下のようになる。ただし、層の奇遇は図１１に従う。
【００３１】
「ツリーのリーフからたどり、偶数層からひとつ上の奇数層に、Ｒ→ＲまたはＬ→Ｌが続くとき、それらふたつのノードと、その経路に含まれ、それらふたつのノードよりもルートに近い側にあるすべてのノードのＬとＲを反転させた経路を追加する」
【００３２】
なお、こうして最終的に得られたツリーは、既知の手法で、例えば、上および左から順に、「子をもつノードはゼロ」「リーフであるノードは１」として符号化することができる。この符号化データと、ツリーで符号化された順にノードの対応情報を並べたデータとを併せれば、これが簡素化マップファイルＭＦＢとなる。
【図面の簡単な説明】
【図１】実施の形態に係る対応点情報生成装置の構成を示す図である。
【図２】原始マップファイルＭＦＡの構成を示す図である。
【図３】補間による対応情報の導出手順を示す図である。
【図４】メッシュ分割の手順を示す図である。
【図５】メッシュ分割の手順を示す図である。
【図６】メッシュ分割の手順を示す図である。
【図７】メッシュ分割の手順を示す図である。
【図８】メッシュ分割の手順を示す図である。
【図９】メッシュ分割の手順を示す図である。
【図１０】メッシュ分割の手順を示す図である。
【図１１】最終的に得られた簡素化マップファイルＭＦＢの構成を示す図である。
【図１２】孤立頂点を解消する手順を示す図である。
【図１３】孤立頂点を解消する手順を示す図である。
【符号の説明】
１２  圧縮装置、  １４  入力部、  １６  制御部、  ２２  マッチングプロセッサ。
【図１】
2004297416.tif 000003
【図２】
2004297416.tif 000004
【図３】
2004297416.tif 000005
【図４】
2004297416.tif 000006
【図５】
2004297416.tif 000007
【図６】
2004297416.tif 000008
【図７】
2004297416.tif 000009
【図８】
2004297416.tif 000010
【図９】
2004297416.tif 000011
【図１０】
2004297416.tif 000012
【図１１】
2004297416.tif 000013
【図１２】
2004297416.tif 000014
【図１３】
2004297416.tif 000015