図1を参照すると、本発明の実施の形態に 係る映像信号符号化装置100の一例は、画像入 力装置101と、データ記憶装置102と、データ処 理装置103と、符号出力装置104とから構成され ている。

 画像入力装置101は、符号化の対象となる� ��像信号を入力する装置であり、例えば図示� ��ないコンピュータのディスプレイ画面のカ� ��ー映像信号をアナログキャプチャあるいは� ��ィジタルキャプチャし、データ記憶装置102� ��記憶する。キャプチャされた1画面分の映像 信号は、フレームあるいは画面データと呼ぶ 。

 データ記憶装置102は、画像入力装置101か� ��入力されたフレームを記憶する符号化対象� ��レーム記憶部111、符号化対象フレーム記憶� ��111に記憶したフレームの符号化に使用する� ��照フレームを記憶する参照フレーム記憶部1 12、フレームの符号化の過程で適宜参照更新� ��れる各種データを保持する作業域113を有す� ��。

 データ処理装置103は、データ記憶装置102� ��記憶された符号化対象フレームの符号化を� ��う装置であり、移動ベクトル検出部121、移� ��領域検出部122、動き補償部123、更新領域検� ��域設定部124、更新領域検出部125および領域� ��号化部126を備えている。各部は、概略以下� ��ような機能を有する。

 移動ベクトル検出部121は、符号化対象フ� ��ームとその直前のフレームとを比較して、� ��要な1つの移動ベクトルを検出する機能を有 する。主要な移動ベクトルとは、換言すれば 、1以上の移動ベクトルの内の支配的なもの� �意味する。例えば、コンピュータの画面で� �図スクロールとマウスカーソル移動が同時� �発生した場合、移動領域の大部分は地図ス� �ロールによるものが占めるため、地図スク� �ールによる移動ベクトルが主要な移動ベク� �ルとなる。

 移動領域検出部122は、符号化対象フレー� ��とその直前のフレームとの何れにも存在す� ��同一または類似の画像領域であって、画面� ��での位置が移動ベクトル検出部121で検出さ� ��た移動ベクトルだけ変化している画像領域� ��移動領域として検出する機能を有する。

 動き補償部123は、移動領域検出部122で検� ��された移動領域について、符号化対象フレ� ��ムの符号化に使用する参照フレーム内で移� ��ベクトルが示す移動先へ複写を行い、動き� ��償後の参照フレームを生成する機能を有す� ��。

 更新領域検出域設定部124は、フレーム上� ��1以上の更新領域検出域を設定する機能を有 する。

 更新領域検出部125は、更新領域検出域設� ��部124により設定された更新領域検出域毎に� ��動き補償後の参照フレームと符号化対象フ� ��ームとが相違する領域を更新領域として検� ��する機能を有する。

 領域符号化部126は、更新領域検出部125で� ��出された更新領域を画像として任意の符号� ��方式によって符号化した符号を生成する。

 符号出力装置104は、データ記憶装置102の� ��業域113から符号化対象フレームについて生� ��された符号を読み出して出力する装置であ� ��、例えば図示しないクライアント端末と通� ��する通信装置などで構成される。1つの符号 化対象フレームについて生成された符号には 、領域符号化部126で生成された更新領域の符 号、移動ベクトル検出部121と移動領域検出部 122で検出された移動領域情報(移動元の領域� �座標と移動ベクトル)とが含まれる。

 上記の移動ベクトル検出部121、移動領域� ��出部122、動き補償部123、更新領域検出域設� ��部124、更新領域検出部125および領域符号化� ��126は、データ処理装置103を構成するコンピ� ��ータとその上で動作するプログラムとで実� ��することができる。プログラムは、CD-ROM等� ��コンピュータ可読記録媒体に記録されて提� ��され、コンピュータの立ち上げ時などにコ� ��ピュータに読み取られ、コンピュータの動� ��を制御することにより、コンピュータ上に� ��記の各部を実現する。

 次に本実施の形態に係る映像信号符号化� ��置100の全体的な動作を説明する。

 映像信号符号化装置100の画像入力装置101� ��、符号化対象となるフレームをキャプチャ� ��、データ記憶装置102の符号化対象フレーム� ��憶部111に現フレームとして記憶する(図2の� �テップS101)。

 次に、移動ベクトル検出部121は、現フレ� ��ムと、参照フレーム記憶部112に記憶された� ��に符号化を終えた直前のフレーム(参照フレ ーム)とを比較し、主要な1つの移動ベクトル� ��検出する(ステップS102)。例えば、図3の現フ レーム131と参照フレーム132との比較から図示 した移動ベクトル134が支配的であれば、移動 ベクトル134が主要な移動ベクトルとして検出 される。検出された移動ベクトル134の情報は 作業域113に一時的に保存される。

 次に移動領域検出部122は、現フレームか� ��移動ベクトルが検出された場合(ステップS10 3でYES)、現フレームと参照フレームとの何れ� ��も存在する同一または類似の画像領域であ� ��て、画面上での位置が移動ベクトル検出部1 21で検出された移動ベクトルだけ変化してい� ��画像領域を移動領域として検出する(ステッ プS104)。例えば、図3の現フレーム131と参照フ レーム132とにおいて、領域135と領域136とが同 一または類似の画像領域であった場合、領域 135、136が移動領域として検出される。検出さ れた移動領域135、136の座標情報は作業域113に 一時的に保存される。

 次に動き補償部123は、移動領域が検出さ� ��た場合(ステップS105でYES)、参照フレーム上� ��移動前の移動領域の画像を移動ベクトルが� ��す移動後の位置へ複写する動き補償を行う� ��とにより、参照フレーム記憶部112を更新す� ��(ステップS106)。例えば図3の場合、参照フレ ーム132上で、領域136を現フレーム131における 領域135に相当する位置にコピーする。これに より、図3の動き補償後の参照フレーム137が� �成される。

 ただし、移動ベクトルが検出されなかっ� ��場合(ステップS103でNO)、移動領域の検出と� �き補償は実行されない。また、移動ベクト� �が検出されても移動領域の検出に失敗した� �合(ステップS105でNO)、動き補償は実行されな い。

 次に更新領域検出域設定部124は、更新領� ��を検出する1以上の更新領域検出域をフレー ム上に設定する(ステップS107)。次に、更新領 域検出部125は、更新領域検出域設定部124によ り設定された更新領域検出域毎に、参照フレ ームと現フレームとが相違する領域を更新領 域として検出する(ステップS108)。これにより 、例えば図3の場合、更新領域138及び139が検� �される。検出された更新領域138及び139の座� �情報は作業域113に一時的に保存される。

 次に領域符号化部126は、更新領域検出部1 25で検出された更新領域を画像として符号化� ��た符号を生成する(ステップS109)。生成され� ��符号は、作業域113に記憶された更新領域の� ��標情報に対応付けて一時的に保存される。

 符号出力装置104は、データ記憶装置102の� ��業域113から現フレームについて生成された� ��報、すなわち各更新領域の座標情報とその� ��号および移動領域情報(移動元の領域の座標 情報と移動ベクトル)を読み出し、出力する(� ��テップS110)。例えば、図3の場合、更新領域1 38の座標情報とその符号、更新領域139の座標� ��報とその符号、移動領域136の座標情報と移� ��ベクトル134が、現フレームに関する符号情� ��として出力される。

 符号情報からフレームを復号する場合、� ��号化と逆の手順で行う。例えば図3の現フレ ーム131を参照フレーム132と符号情報とから復 号する場合、まず、参照フレーム132の移動領 域136を移動ベクトル134が示す場所へ複写して 動き補償後の参照フレーム137を生成する。そ の後、この参照フレームに対して、符号情報 から復号した更新領域138および更新領域139を 反映することにより、現フレーム131を生成す る。

 次にデータ処理装置103が備える各部につ� ��て説明する。ここで、動き補償部123はコピ� ��手段で実現でき、また領域符号化部126は、� ��測符号化、変換符号化、ベクトル量子化、� ��ントロピー符号化など周知の画像符号化技� ��で実現できるため、以下では、移動ベクト� ��検出部121、移動領域検出部122、更新領域検� ��域設定部124および更新領域検出部125につい� ��詳細に説明する。

(1)移動ベクトル検出部121
 図4を参照すると、移動ベクトル検出部121の 第1の実施例は、エッジ抽出部201、特徴点抽� �部202、特徴点ペア抽出部203および移動ベク� �ル算出部204から構成される。各々は、概ね� �下のような機能を有する。

 エッジ抽出部201は、現フレームおよび参� ��フレーム内で画素値の変化が大きい点をエ� ��ジ点として抽出する機能を有する。エッジ� ��とは、予め定められた直交する2方向(上と� �、左と下、下と右、右と上、斜め左上と斜� �左下、斜め左下と斜め右下、斜め右下と斜� �右上、斜め右上と斜め左上)の隣接画素との� ��素値の差分が共に予め設定された閾値以上� ��違している画素である。画素値の差分は例� ��ばR、G、Bの各成分毎に求め、その何れかの� ��分の差分が閾値以上であれば、2つの画素の 画素値の差分が閾値以上相違していると判断 する。

 特徴点抽出部202は、現フレームおよび参� ��フレーム中から抽出されたエッジ点のうち� ��他の1以上のエッジ点との位置関係が当該フ レームにおいて一意(ユニークとも言う)なエ� ��ジ点(すなわち、他の1以上のエッジ点との� �置関係が当該フレームにおいて唯一度しか� �れないエッジ点)を特徴点として抽出する機� ��を有する。本実施例では、他の1以上のエッ ジ点として、フレームのラスタスキャン順で 直前に現れた1つのエッジ点を用いる。しか� �、他の実施例として、直前1つ目のエッジ点� ��直前2つ目のエッジ点のように複数のエッジ 点を用いても良い。一般に、直前1つのエッ� �点だけを用いるよりも直前複数のエッジ点� �用いた方が、当該フレームにおいて他のエ� �ジ点との位置関係がユニークになるエッジ� �の個数を少なくできるため、後述するよう� �ハッシュ値を使う場合のハッシュ値のビッ� �数を少なくできる利点がある。

 エッジ点と他のエッジ点との位置関係を� ��定するデータとしては、エッジ点同士の距� ��を画素数で表現した値を使用することがで� ��る。また、距離そのものでなく、距離を表� ��ビット列の下位何ビットかをハッシュ値と� ��、このハッシュ値がユニークなエッジ点を� ��徴点として抽出するようにしても良い。本� ��施例では、距離を表すビット列のたとえば� ��位11ビットをハッシュ値として使用する。

 特徴点ペア抽出部203は、他のエッジ点と� ��位置関係が同一の特徴点のペアを現フレー� ��および参照フレームから抽出する機能を有� ��る。好ましくは、特徴点ペア抽出部203は、� ��のエッジ点との位置関係が同一かつ画素値� ��差が閾値以下の特徴点のペアを抽出する。

 移動ベクトル算出部204は、現フレームお� ��び参照フレームから抽出された特徴点のペ� ��の座標値の差分を移動ベクトルとして算出� ��る機能を有する。好ましくは、移動ベクト� ��算出部204は、移動ベクトル候補生成部205と� ��動ベクトル選択部206とで構成される。

 移動ベクトル候補生成部205は、現フレー� ��と参照フレームから抽出された特徴点のペ� ��が複数存在する場合、各特徴点のペア毎に� ��標値の差分を移動ベクトル候補として生成� ��る機能を有する。

 移動ベクトル選択部206は、移動ベクトル� ��補のうち最も頻出する移動ベクトル候補を� ��動ベクトルとして選定する機能を有する。

 次に本実施例の移動ベクトル検出部121の� ��作を説明する。

 移動ベクトル検出部121のエッジ抽出部201� ��、符号化対象フレーム記憶部111に記憶され� ��現フレームの先頭の画素に注目し(図5のス� �ップS201)、注目中の画素がエッジ点かどうか を判定する(ステップS202)。エッジ点でなけれ ば、ラスタスキャン方向の順で次の画素に注 目を移し(ステップS206)、注目中の画素がエッ ジ点かどうかを判定する(ステップS202)。

 注目中の画素がエッジ点であれば(ステッ プS202でYES)、注目中の画素の座標値と画素値� ��組をエッジ点情報として作業域113に一時的� ��保存する(ステップS203)。次に、作業域113に� ��存されている直前のエッジ点との距離を求� ��、その距離の下位11ビットをハッシュ値と� �て算出し(ステップS204)、作業域113に記憶さ� �ている現フレームに対応するハッシュテー� �ルを更新する(ステップS205)。例えば図6に示� ��ように、ラスタスキャン順に処理を進めて� ��画素P(1,1)に続き画素P(5,1)がエッジ点として� ��出された場合、画素P(5,1)と画素P(1,1)の距離� ��画素数にして4なので、値4のハッシュ値が� �出され、当該エッジ点の情報がハッシュテ� �ブルに登録される。

 図7を参照すると、現フレームに対応する ハッシュテーブルの一例は、0~2047の各ハッシ ュ値に1対1に対応するエントリを有し、各エ� ��トリに、出現頻度、最終出現座標、画素値� ��登録される。出現頻度の初期値は0、最終出 現座標および画素値の初期値はNULLである。� �ッジ抽出部201は、ステップS205のハッシュテ� ��ブルの更新処理において、算出したハッシ� ��値を持つエントリの出現頻度を1だけインク リメントし、検出したエッジ点の座標値と画 素値を最終出現座標および画素値の欄に記録 する。例えば前述した画素P(5,1)の場合、図7� �ハッシュ値4のエントリにおける出現頻度が1 だけインクリメントされ、また画素P(5,1)の座 標値と画素値とが同エントリに記録される。

 エッジ抽出部201は、以上のような処理を� ��フレームの最後の画素まで繰り返し実行す� ��。

 エッジ抽出部201の処理が完了すると(ステ ップS207でYES)、特徴点抽出部202は、現フレー� ��に対応するハッシュテーブルを参照して、� ��現頻度が1になっているエントリに座標値と 画素値とが記録されているエッジ点を特徴点 としてすべて抽出する(ステップS208)。例えば 、エッジ抽出部201の処理完了時点の現フレー ムに対応するハッシュテーブルが図7に示し� �ものであった場合、画素P(5,1)が1つの特徴点� ��して抽出される。

 次に特徴点ペア抽出部203は、現フレーム� ��対応するハッシュテーブルおよび前フレー� ��に対応するハッシュテーブルを参照して、� ��ッシュ値が同一の特徴点のペアをすべて抽� ��する(ステップS209)。ここで、前フレームに� ��応するハッシュテーブルは、前フレームが� ��フレームとして処理された際にエッジ抽出� ��201により作成され、作業域113に記憶されて� ��る。例えば前フレームに対応するハッシュ� ��ーブルが図8に示すような内容になっている 場合、図7に示した現フレームから特徴点と� �て抽出された画素P(5,1)とハッシュ値が同じ4� ��画素P(5,8)が前フレームに存在するため、前� ��レームにおける画素P(5,8)と現フレームにお� ��る画素P(5,1)のペアが、1つの特徴点のペアと して抽出される。

 次に特徴点ペア抽出部203は、ステップS209 で抽出した特徴点のペアのうち、R、G、Bの各 色成分の差分が何れも予め設定された閾値以 下となるペアは対応可能性が高いので残し、 それ以外の特徴点のペアは除外する(ステッ� �S210)。特徴点ペア抽出部203は、残した特徴点 のペアの情報を作業域113に記録する。

 次に移動ベクトル算出部204の移動ベクト� ��候補生成部205は、作業域113から特徴点のペ� ��の情報を読み出し、各ペア毎に座標値の差� ��を移動ベクトル候補として生成する(ステッ プS211)。例えば前述したP(5,8)とP(5,1)の特徴点� ��ペアの場合、(0,-7)が移動ベクトル候補とし� ��生成される。なお、静止ベクトルは無視す� ��ため、差分が(0,0)となる場合は候補から外� �。移動ベクトル候補生成部205は、移動ベク� �ル候補の情報を作業域113に記録する。

 次に、移動ベクトル選択部206は、作業域1 13から移動ベクトル候補の情報を読み出し、� ��じ移動ベクトル候補の総数をカウントする� ��とにより各移動ベクトル候補の出現頻度を� ��め、最も頻出する移動ベクトル候補を主要� ��移動ベクトルの推定値として選択する(ステ ップS212)。そして、移動ベクトル選択部206は� ��移動ベクトルの検出結果を作業域113に記録� ��る(ステップS213)。

 移動ベクトル選択部206が作業域113に記録� ��た検出結果の一例を図9に示す。この例では 、推定した移動ベクトル以外に最頻出の移動 ベクトル候補の算出元となった特徴点のペア のリストが検出結果に含まれている。図10は� ��検出結果に含まれる特徴点のペアを前フレ� ��ムおよび現フレームにプロットしたイメー� ��と、推定された移動ベクトルとの関係を示� ��。このように、最頻出の移動ベクトル候補� ��ら推定される移動ベクトルは、現フレーム� ��存在する1以上の移動ベクトルのうちの主要 な移動ベクトルとなる。

 このように本実施例の移動ベクトル検出� ��121によれば、コンピュータ画面の映像信号� ��ら高速かつ高精度に主要な移動ベクトルを� ��出することができる。その理由は、第1に、 各画素ブロックで様々なベクトルを探索する 必要がなく、エッジ点や特徴点の抽出と比較 により移動ベクトルを求めていること、第2� �、フレーム内ではラスタスキャン順の処理� �なるためにメモリアクセスの局所性が高い� �と、第3に、ブロック単位ではなく画面全体� ��比較するため、ウィンドウ等、比較的大き� ��オブジェクト単位での移動ベクトルが主要� ��移動ベクトルとして検出できること、第4に 、エッジ点を元にベクトルを検出しているた め移動元と移動先で画素値が正確に一致する 必要はなく、アナログキャプチャしたノイズ の多い映像信号にも対応可能であることによ る。

 反面、本実施例の移動ベクトル検出部121� ��、(1)同時に複数のベクトルは検出しない、( 2)サブピクセル単位や変形を伴うオブジェク� ��の移動ベクトルは検出しない、(3)エッジの� ��ないオブジェクトの移動ベクトルは検出し� ��いという制約がある。しかし、(1)と(2)はコ� ��ピュータ画面で生じる可能性は低く、(3)の� ��うな領域はそのまま画像として符号化して� ��符号量が小さくなるため大きな問題とはな� ��ない。

(2)移動領域検出部122
 図11を参照すると、移動領域検出部122の第1� ��実施例は、初期候補決定部301と移動領域決� ��部302とから構成される。各々は、概ね以下� ��ような機能を有する。

 初期候補決定部301は、移動領域の初期候� ��を決定する機能を有する。

 移動領域決定部302は、初期候補決定部301� ��決定された移動領域の初期候補および初期� ��補の移動領域のサイズを変更した1以上の他 の移動領域の候補のうちから動き補償部123の 動き補償に使用する移動領域を決定する機能 を有する。

 次に本実施例の移動領域検出部122の動作� ��説明する。

 移動領域検出部122の初期候補決定部301は� ��初期候補の移動領域を決定する(図12のステ� ��プS301)。初期候補を決定する方法の一例と� �て、移動ベクトル検出部121が移動ベクトル� �推定に使用した移動ベクトル候補の算出元� �なった特徴点群に外接する矩形を移動領域� �初期候補とする方法がある。例えば、移動� �クトル検出部121の移動ベクトル選択部206が� �9に示したような検出結果を生成した場合、� ��動領域検出部122は、作業域113から上記の検� ��結果に記述された特徴点を前フレームおよ� ��現フレーム毎に読み出す。例えば、移動領� ��検出部122は、図13の前フレームに示すよう� �特徴点群に外接する矩形を移動前の移動領� �とする。そして、移動領域検出部122は、図13 の現フレームに示すように特徴点群に外接す る矩形を移動後の移動領域として検出する。 検出した初期候補の移動領域の情報は作業域 113に一時的に記録される。

 初期候補を決定する方法の他の例として� ��、移動ベクトル検出部121が移動ベクトルの� ��定に使用した移動ベクトル候補に含まれる� ��徴点群中の何れか3つ以上の特徴点に外接す る矩形を移動領域の初期候補とする方法、フ レーム全体を移動領域の初期候補とする方法 などがある。

 次に移動領域検出部122の移動領域決定部3 02は、初期候補および他の候補のうちから動� ��補償に使用する移動領域を決定する(ステッ プS302)。以下、移動領域決定部302の構成例に� ��いて詳細に説明する。

(A)移動領域決定部302の例1
 この例1の移動領域決定部302の処理例を図14A 及び図14Bに示す。まず移動領域決定部302は、 決定された初期候補の移動領域および移動ベ クトルに基づいて実際に動き補償を行って各 画素値を比較し、正しく平行移動したもので あるかどうかを確認する。具体的には、動き 補償によって低減される符号量と、動き補償 によって増加する符号量のどちらが大きくな るかを、移動領域が動き補償に使用する移動 領域として適している程度および適していな い程度をそれぞれ示すメリット値およびデメ リット値を評価尺度として使用して、以下の ような手法で推定する(ステップS311、S312)。� �こで、メリット値は、移動領域が動き補償� �使用する移動領域として適している程度を� �す評価尺度、デメリット値は、移動領域が� �き補償に使用する移動領域として適してい� �い程度を示す評価尺度であり、何れも初期� �は0である。

(ア)「動き補償後の画素値」と「真の画素値� ��とが異なる場合(例えばR、G、Bの各成分毎の 差分の何れかが予め設定された閾値以上異な る場合)、動き補償によって符号量が増える� �能性があると見做し、デメリット値を1増や� ��。
(イ)「動き補償後の画素値」と「真の画素値� ��とが異ならない場合(例えばR、G、Bの各成分 毎の差分の何れもが予め設定された閾値以上 異ならない場合)で、かつ、その座標の画素� �その隣接する画素との間に閾値以上の輝度� �配がある場合(例えば、上画素および左画素� ��の差分の合計値が閾値以上になる場合や、� ��画素または左画素との差分が閾値以上にな� ��場合など)、動き補償によって符号量が低減 できる可能性があると見做し、メリット値を 1増やす。ここで、隣接する画素との間に閾� �以上の輝度勾配があることを条件に加えて� �る理由は、輝度勾配がある点が含まれる箇� �は差分による符号化では一般に符号量が増� �るためである。
(ウ)初期候補の移動領域全体に対して、上記� ��ア、イの処理を行い、メリット値がデメリ� ��ト値より大きければ、移動領域として採用� ��、そうでなければ棄却する。

 なお、メリット値およびデメリット値を� ��素値の比較結果に応じて加算し、最終的な� ��リット値とデメリット値とを比較する処理� ��、メリット値およびデメリット値の何れか� ��方だけを使用して加算と減算を使い分ける� ��法と等価である。具体的には、まず、動き� ��償後の画素値と真の画素値との差分が所定� ��閾値以上となる画素が検出される毎にメリ� ��ト値を所定値だけ減算(またはデメリット値 を所定値だけ加算)する。次に、動き補償後� �画素値と真の画素値との差分が所定の閾値� �り小さな画素であって且つ隣接する画素と� �間に閾値以上の輝度勾配がある画素が検出� �れる毎にメリット値を所定値だけ加算(また� ��デメリット値を所定値だけ減算)する処理を 行う。これにより、最終的なメリット値(ま� �はデメリット値)の値の正、負を判定するよ� ��にしても良い。

 移動領域の初期候補が棄却された場合(ス テップS312でNO)、本例ではもはや移動領域の� �出は一切行われず、移動領域の検出が失敗� �た旨の検出結果を作業域113に記録して(ステ� ��プS323)、図14A及び図14Bの処理を終了する。

 他方、移動領域の初期候補が採用された� ��合(ステップS312でYES)、以下の手順により、� ��域を更に上下左右へ拡張可能かどうかを調� ��る。

(I)移動領域の各ラインについて、領域を右 に広げた際に「動き補償後の画素値」と「真 の画素値」とが一致する(差分が閾値以下に� �る)連続画素数を調べ、連続画素数の最小値� ��右への最大拡大幅として、右端を確定する( ステップS313)。例えば図15に示すように、初� �候補の右端を右に広げた際、1ライン目と3ラ イン目は3画素連続して、残りの全ラインは2� ��素連続して、それぞれ「動き補償後の画素� ��」と「真の画素値」とが一致したとすると� ��右への最大拡大幅は連続画素数の最小値で� ��る2画素とする。

(II)右への拡大方法と同様の方法で、移動� �域の左への最大拡大幅を算出し、左端を確� �する(ステップS314)。

(III)上記の(I)および(II)の処理を行った後の 移動領域に対して、更に、領域を1ラインず� �上に拡大していく(ステップS315~S318)。具体的 には、前述の(ア)、(イ)と同様の方式で、1ラ� ��ン拡大した場合のメリット値、デメリット� ��を計算し(ステップS315、S316)、メリット値が デメリット値より大きければ(ステップS317でY ES)、ステップS315に戻って、更に次のライン� �ついても同様の処理を行う。また、メリッ� �値がデメリット値よりも大きくなければ、1� ��イン拡大前の上端を移動領域の上端に確定� ��る(ステップS318)。

(IV)上への拡大と同様の方法で、移動領域� �下に拡大していって、下端を確定する(図14B� ��ステップS319~S322)。

 最後に移動領域決定部302は、拡大後の移� ��領域の座標情報を含む検出結果を作業域113� ��記録し(ステップS323)、図14A及び図14Bの処理� ��終える。

 ここで、移動領域の左右への拡大と上下� ��の拡大とで異なる手法を採用している理由� ��、同じライン上の複数の画素へのメモリア� ��セスは高速に行えるが、異なるライン上の� ��素へのメモリアクセスには時間がかかるた� ��である。つまり、左右への拡大を上下と同� ��に1列ずつ順に拡大していくと、1列拡大す� �だけでも移動領域の全ラインにわたるメモ� �アクセスが必要になるためである。しかし� �このようなメモリアクセス時間が問題とな� �ない状況の下では、移動領域の左右への拡� �を上下への拡大と同じ手法で行っても良い� �逆に、移動領域の上下への拡大を、左右へ� �拡大に使用した簡易な手法で行うようにし� �も良い。

 この例1の移動領域決定部302によれば、初 期候補決定部301で決定された初期候補の妥当 性を定量的に判定することができるため、不 適切な移動領域を使った動き補償を防止する ことができる。また、初期候補が妥当な場合 、符号量の削減効果が大きい、よりサイズの 大きな移動領域を探索することができる。

(B)移動領域決定部302の例2
 この例2の移動領域決定部302の処理例を図16A 及び図16Bに示す。例2が例1と相違するところ� ��、次の通りである。例1では初期候補よりサ イズの大きな移動領域だけを探索した。これ に対して、例2では、移動領域が真の移動領� �よりも大きな領域として過剰に検出されて� �る可能性を考慮して、まず各辺毎に領域の� �小の可能性を判定し、過剰検出されていな� �辺については例1と同様に拡大していくよう� ��した。

 まず移動領域決定部302は、例1と同様の方 法により初期候補の移動領域の妥当性を判定 する(ステップS331、S332)。移動領域の初期候� �が棄却された場合(ステップS332でNO)、本例で も例1と同様にもはや移動領域の検出は一切� �われず、移動領域の検出が失敗した旨の検� �結果を作業域113に記録して(ステップS357)、� �16A及び図16Bの処理を終了する。

 他方、移動領域の初期候補が採用された� ��合(ステップS332でYES)、以下の手順により、� ��域を更に上下左右から縮小可能かどうか、� ��下左右へ拡張可能かどうかを調べる。

 まず移動領域決定部302は、初期候補の移� ��領域の右からの最大縮小幅を算出する(ステ ップS333)。具体的には、移動領域の各ライン� ��ついて、領域を右から狭めた際に「動き補� ��後の画素値」と「真の画素値」とが一致し� ��い(差分が閾値以上になる)連続画素数を調� �、連続画素数の最小値を右からの最大縮小� �として、右端を確定する。例えば図17に示す ように、初期候補の右端を右から狭めた際、 1ライン目と4ライン目と5ライン目は3画素連� �して、残りの全ラインは2画素連続して、そ� ��ぞれ「動き補償後の画素値」と「真の画素� ��」とが一致しなかったとすると、右からの� ��大縮小幅は連続画素数の最小値である2画素 とする。

 次に移動領域決定部302は、最大縮小幅が0 か否かを判定し(ステップS334)、最大縮小幅が 0でなければ、例えば図17に示すように、初期 候補の右端から最大縮小幅だけ狭めた箇所を 移動領域の右端として確定する(ステップS335) 。また、最大縮小幅が0であれば、例1と同様� ��方法で移動領域の右への最大拡大幅を算出� ��、右端を確定する(ステップS336)。

 次に移動領域決定部302は、初期領域の左� ��からも右端と同様に最大縮小幅を算出し(ス テップS337)、最大縮小幅が0でなければ、最大 縮小幅から左端を確定する(ステップS338、339) 。また、最大縮小幅が0であれば、例1と同様� ��方法で左端からの最大拡張幅を算出して、� ��端を確定する(ステップS340)。

 次に移動領域決定部302は、移動領域を上� ��ら1ライン縮小し、前述の(ア)、(イ)と同様� �方式で、1ライン縮小した場合のメリット値� ��デメリット値を計算する(ステップS341、S342) 。メリット値がデメリット値より小さければ (ステップS343でYES)、更に次のラインについて も同様の縮小処理を繰り返す(ステップS344~S34 6)。そして、メリット値がデメリット値より� ��小さくないことが検出された場合、1ライン 縮小前の上端を移動領域の上端に確定する(� �テップS347)。他方、ステップS343でメリット� �がデメリット値より小さくないと判定した� �合、例1と同様の方法で移動領域の上への最� ��拡張幅を算出し、上端を確定する(ステップ S348)。

 次に移動領域決定部302は、移動領域の下� ��らも上からと同様の処理を行う(ステップS34 9~S356)。

 最後に移動領域決定部302は、上下左右の� ��部が確定した移動領域の座標情報を含む検� ��結果を作業域113に記録し(ステップS357)、図1 6A及び図16Bの処理を終える。

 ここで、移動領域の左右からの縮小と上� ��からの縮小とで異なる手法を採用している� ��由は、同じライン上の複数の画素へのメモ� ��アクセスは高速に行えるが、異なるライン� ��の画素へのメモリアクセスには時間がかか� ��ためである。つまり、左右への縮小を上下� ��同様に1列ずつ順に行っていくと、1列縮小� �るだけでも移動領域の全ラインにわたるメ� �リアクセスが必要になるためである。しか� �、このようなメモリアクセス時間が問題と� �らない状況の下では、移動領域の左右から� �縮小を上下からの縮小と同じ手法で行って� �良い。逆に、移動領域の上下からの縮小を� �左右からの縮小に使用した簡易な手法で行� �ようにしても良い。

 この例2の移動領域決定部302によれば、初 期候補決定部301で決定された初期候補の妥当 性を定量的に判定することができるため、不 適切な移動領域を使った動き補償を防止する ことができる。また、初期候補が妥当な場合 、まず上下左右からの縮減を試みるため、初 期候補の移動領域が真の移動領域よりも大き な領域として過剰に検出されていた場合に、 過剰検出分を削減することが可能になる。更 に、過剰検出の可能性がない辺については、 符号量の削減効果が大きい、よりサイズの大 きな移動領域へと拡大していくことが可能と なる。

(C)移動領域決定部302の例3
 この例3の移動領域決定部302の処理例を図18� ��示す。例3が例2と相違するところは、例2で� ��初期候補について計算したメリット値がデ� ��リット値を下回っていた場合にもはや移動� ��域の検出を断念していたのに対して、例3で は、移動領域が真の移動領域よりも極めて過 大に検出されている可能性を考慮して、各辺 毎に領域の縮小の可能性を判定していくよう にした点にある。

 まず移動領域決定部302は、例2と同様の方 法により初期候補の移動領域の妥当性を判定 する(ステップS361、S362)。移動領域の初期候� �が棄却されなかった場合(ステップS362でYES)� �処理ステップS363は、例2のステップS333~S356と 同じである。

 他方、移動領域の初期候補が棄却された� ��合(ステップS362でNO)、以下の手順により、� �域を更に上下左右から縮小可能かどうかを� �べる。

 まず移動領域決定部302は、例2と同様の方 法で、初期候補の移動領域の右からの最大縮 小幅を算出する(ステップS364)。次に移動領域 決定部302は、最大縮小幅が移動領域の横幅に 等しいか否かを判定し(ステップS365)、最大縮 小幅が移動領域の横幅に等しければ、移動領 域の検出に失敗したとして、その旨の検出結 果を生成し(ステップS365でYES、ステップS372)� �図18の処理を終了する。最大縮小幅が移動領 域の横幅に等しくなければ、初期候補の右端 から最大縮小幅だけ狭めた箇所を移動領域の 右端として確定する(ステップS366)。

 次に移動領域決定部302は、初期領域の左� ��からも右端と同様に最大縮小幅を算出し、� ��端を確定する(ステップS367)。

 次に移動領域決定部302は、移動領域の上� ��らの最大縮小幅を例2と同様の方法で算出す る(ステップS368)。もし、最大縮小幅が移動領 域の縦幅に等しければ、移動領域の検出に失 敗したとして、その旨の検出結果を生成し(� �テップS369でYES、ステップS372)、図18の処理を 終了する。最大縮小幅が移動領域の縦幅に等 しくなければ、最大縮小幅から移動領域の上 端を確定する(ステップS370)。

 次に移動領域決定部302は、移動領域の下� ��らも上からと同様に最大縮小幅を算出し、� ��端を確定する(ステップS371)。

 最後に移動領域決定部302は、上下左右の� ��部が確定した移動領域の座標情報を含む検� ��結果を作業域113に記録し(ステップS372)、図1 8の処理を終える。

 この例3の移動領域決定部302によれば、初 期候補決定部301で決定された初期候補の妥当 性を定量的に判定することができるため、不 適切な移動領域を使った動き補償を防止する ことができる。また、初期候補が棄却された 場合であっても、縮小の可能性を探索するた め、初期候補の移動領域が真の移動領域より も極めて過大に検出されていた場合でも移動 領域を可能な限り検出することが可能になる 。さらに、例2と同様に、初期候補が妥当な� �合、まず上下左右からの縮小を試みるため� �初期候補の移動領域が真の移動領域よりも� �きな領域として過剰に検出されていた場合� �、過剰検出分を削減することが可能になる� �同様に、過剰検出の可能性がない辺につい� �は、符号量の削減効果が大きい、よりサイ� �の大きな移動領域へと拡大していくことが� �能となる。

(D)移動領域決定部302の例4
 この例4の移動領域決定部302の処理例を図19A 及び図19Bに示す。例4が例2と相違するところ� ��、例2では初期候補について妥当性の判定を 行い、妥当と判定した場合に移動領域の縮小 、拡大を試行するのに対して、例4では、初� �候補の妥当性の判定を省略し、初期候補の� �小、拡大を試行する点にある。

 まず移動領域決定部302は、例2と同様の方 法で、初期候補の移動領域の右からの最大縮 小幅を算出する(ステップS381)。次に移動領域 決定部302は、最大縮小幅が移動領域の横幅に 等しいか否かを判定し(ステップS382)、最大縮 小幅が移動領域の横幅に等しければ(ステッ� �S382でNO)、移動領域の検出に失敗したとして� ��その旨の検出結果を生成し(ステップS399)、� ��19A及び図19Bの処理を終了する。

 最大縮小幅が移動領域の横幅に等しくな� ��れば(ステップS382でYES)、移動領域決定部302� ��、最大縮小幅が0かどうかを判定し(ステッ� �S383)、0でなければ、初期候補の右端から最� �縮小幅だけ狭めた箇所を移動領域の右端と� �て確定する(ステップS384)。また、最大縮小� �が0であれば、移動領域決定部302は、例2と同 様の方法で右への最大拡大幅を算出し、右端 を確定する(ステップS385)。

 次に移動領域決定部302は、例2と同様の方 法で初期候補の移動領域の左からの最大縮小 幅を算出し(ステップS386)、最大縮小幅が0で� �ければ(ステップS387でNO)、初期候補の左端か ら最大縮小幅だけ狭めた箇所を移動領域の左 端として確定する(ステップS388)。また、最大 縮小幅が0であれば、移動領域決定部302は、� �2と同様の方法で左への最大拡大幅を算出し� ��左端を確定する(ステップS389)。

 次に移動領域決定部302は、移動領域の上� ��らの最大縮小幅を例2と同様の方法で算出す る(ステップS390)。もし、最大縮小幅が移動領 域の縦幅に等しければ、移動領域の検出に失 敗したとして、その旨の検出結果を生成し(� �テップS391でYES、S399)、図19A及び図19Bの処理� �終了する。最大縮小幅が移動領域の縦幅に� �しくなければ、最大縮小幅が0かどうかを判� ��し(ステップS391でNO、ステップS392)、0でなけ れば、初期候補の上端から最大縮小幅だけ狭 めた箇所を移動領域の上端として確定する(� �テップS393)。また、最大縮小幅が0であれば� �移動領域決定部302は、例2と同様の方法で上� ��の最大拡大幅を算出し、上端を確定する(ス テップS394)。

 次に移動領域決定部302は、移動領域の下� ��らの最大縮小幅を例2と同様の方法で算出し (ステップS395)、0でなければ、初期候補の下� �から最大縮小幅だけ狭めた箇所を移動領域� �下端として確定する(ステップS396でNO、S397)� �また、最大縮小幅が0であれば、移動領域決� ��部302は、例2と同様の方法で下への最大拡大 幅を算出し、下端を確定する(ステップS398)。

 最後に移動領域決定部302は、上下左右の� ��部が確定した移動領域の座標情報を含む検� ��結果を作業域113に記録し(ステップS399)、図1 9A及び図19Bの処理を終える。

 この例4の移動領域決定部302によれば、初 期候補決定部301で決定された初期候補の妥当 性を定量的に判定していないので、処理量を 削減することができる。また、まず上下左右 からの縮小を試みるため、初期候補の移動領 域が真の移動領域よりも大きな領域として過 剰に検出されていた場合に、過剰検出分を削 減することが可能になる。同様に、過剰検出 の可能性がない辺については、符号量の削減 効果が大きい、よりサイズの大きな移動領域 へと拡大していくことが可能となる。ただし 、初期候補の移動領域の妥当性を判定してい ないため、例えばドーナツ型の穴の部分が移 動前後で全く相違するような領域を移動領域 として検出する可能性がある。

(3)更新領域検出域設定部124
 図20を参照すると、更新領域検出域設定部12 4の第1の実施例は、移動領域有無判定部401と� ��移動方向判定部402と、分割部403とから構成� ��れる。各々は、概ね以下のような機能を有� ��る。

 移動領域有無判定部401は、移動領域検出� ��122で移動領域が検出されたか否かを判定す� ��機能を有する。

 移動方向判定部402は、移動領域検出部122� ��検出された移動領域の移動方向を判定する� ��能を有する。

 分割部403は、移動領域有無判定部401およ� ��移動方向判定部402の判定結果に従って画面� ��割の必要性の判定および画面分割による更� ��領域検出域の設定を行う機能を有する。

 次に本実施例の更新領域検出域設定部124� ��第1の処理例を説明する。

 更新領域検出域設定部124の移動領域有無� ��定部401は、移動領域検出部122の検出結果を� ��業域113から読み出して解析することにより� ��移動領域が検出されたかどうかを判定し、� ��定結果を移動方向判定部402および分割部403� ��通知する(図21のステップS501)。

 移動方向判定部402は、移動方向を判定す� ��(ステップS502)。具体的には、移動方向判定� ��402は、まず、移動領域が検出された旨の通� ��を移動領域有無判定部401から受け取る。次� ��、移動方向判定部402は、作業域113から読み� ��された移動領域検出部122の検出結果に含ま� ��る移動前の移動領域の座標と移動後の移動� ��域の座標とを比較する移動方向が、画面の� ��から下へ向かう成分を含む方向(以下、下方 向と言う)、画面の下から上へ向かう成分を� �む方向(以下、上方向と言う)の何れであるか を判定する。そして、移動方向判定部402は、 判定結果を分割部403に通知する。判定結果に は、移動方向以外に、下方向の場合には移動 後の移動領域の上端の座標、上方向の場合に は移動後の移動領域の下端の座標が含まれる 。なお、下方向でもなく、上方向でもない左 右方向の場合の扱い方としては、例えば、下 方向あるいは上方向の何れかに含めることが 考えられる。

 分割部403は、移動領域有無判定部401から� ��動領域が検出されなかった旨の通知を受け� ��場合、画面全体を1つの更新領域検出域に設 定する(ステップS503)。また、移動領域有無判 定部401から移動領域が検出された旨の通知を 受けた場合、移動方向判定部402からの通知に 従って画面を分割する(ステップS504~S506)。具� ��的には、移動方向が下方向であれば、移動� ��の移動領域の上端で画面を2分割し、各分割 領域をそれぞれ1つの更新領域検出域に設定� �る。また、移動方向が上方向であれば、移� �後の移動領域の下端で画面を2分割し、各分� ��領域をそれぞれ1つの更新領域検出域に設定 する。その後、更新領域検出域毎に更新領域 検出部125による更新領域の検出が行われる。

 第1の処理例の更新領域検出域設定部124に よる効果を説明する。以下では、移動方向が 下方向の場合について説明しているが、上方 向の場合も同様の効果が得られる。また、以 降の効果を説明する図において、斜線部は差 分画素を示す。また、以降の効果を説明する 図において、同一の要素については同一の符 号を付し、重複した説明は省略する。

 図22の左上は、画面R1において移動領域R11 から移動領域R12へ移動したこと、つまり、移 動領域が下方向に移動したことを示す。図22� ��右上は、画面R2全体を更新領域検出域に設� �した場合を示す。このとき、移動前の移動� �域R21に相当する領域全体が更新領域として� �出される。また、移動後の移動領域R20は、� �出されない。これに対して本例にかかる図22 の右下は、移動後の移動領域R30の上端で画面 R3が分割線L221により2分割され、各々の更新� �域検出域で更新領域R31及びR32の検出が行わ� �るため、更新領域の合計面積を最小限に抑� �ることができ、符号量の削減が可能になる� �

 次に本実施例の更新領域検出域設定部124� ��第2の処理例を説明する。

 更新領域検出域設定部124の移動領域有無� ��定部401は、第1の処理例と同様に移動領域が 検出されたかどうかを判定し、判定結果を移 動方向判定部402および分割部403へ通知する(� �23のステップS511)。

 移動方向判定部402は、第1の処理例と同様 に、移動領域が検出された旨の通知を移動領 域有無判定部401から受け取ると、移動方向が 下方向、上方向の何れであるかを判定し、判 定結果を分割部403に通知する(ステップS512)。 判定結果には、移動方向以外に、移動方向が 下方向の場合も上方向の場合も共に、移動後 の移動領域の上下端の座標が含まれる。

 分割部403は、移動領域有無判定部401から� ��動領域が検出されなかった旨の通知を受け� ��場合、第1の処理例と同様に画面全体を1つ� �更新領域検出域に設定する(ステップS513)。� �た、移動領域有無判定部401から移動領域が� �出された旨の通知を受けた場合、移動方向� �定部402からの通知に従って画面を分割する(� ��テップS514~S516)。具体的には、移動方向が下 方向および上方向とも、移動後の移動領域の 上下端で画面を3分割し、各分割領域をそれ� �れ1つの更新領域検出域に設定する。その後� ��更新領域検出域毎に更新領域検出部125によ� ��更新領域の検出が行われる。

 次に、本処理例の更新領域検出域設定部1 24による効果を説明する。以下では、移動方� ��が下方向の場合について説明しているが、� ��方向の場合も同様の効果が得られる。

 図24の左上及び右上は、図22の左上及び右 上と同様である。これに対して本例にかかる 図24の右下は、移動後の移動領域R30の上下端� ��画面R3が分割線L241及びL242により3分割され� �各々の更新領域検出域で更新領域R31及びR32� �検出が行われるため、更新領域の合計面積� �最小限に抑えることができ、符号量の削減� �可能になる。

 また、図25の左上は、画面R1において検出 された移動領域R13が実際の移動領域R12よりも 小さかった場合を示す。図25の右上は、図21� �第1の処理例を適用し、移動後の上端のみで� ��面R2を分割線L251により2分割した場合を示す 。この場合、図25の右上に示すように検出さ� ��た移動領域R20aを含み、無駄に大きな更新領 域R22及びR23が検出されてしまう。これに対し て本例にかかる図25の右下は、移動後の移動� ��域R30aの上下端で画面R3が分割線L252及びL253� �より3分割され、各々の更新領域検出域で更� ��領域R331、R332、R333及びR334の検出が行われる ため、更新領域の合計面積を小さくでき、そ の分、符号量の削減が可能になる。

 次に本実施例の更新領域検出域設定部124� ��第3の処理例を説明する。

 更新領域検出域設定部124の移動領域有無� ��定部401は、第2の処理例と同様に移動領域が 検出されたかどうかを判定し、判定結果を移 動方向判定部402および分割部403へ通知する(� �26のステップS521)。

 移動方向判定部402は、第2の処理例と同様 に、移動領域が検出された旨の通知を移動領 域有無判定部401から受け取ると、移動方向が 下方向、上方向の何れであるかを判定し、判 定結果を分割部403に通知する(ステップS522)。 判定結果には、移動方向以外に、移動方向が 下方向の場合には移動後の移動領域の上下端 および移動前の移動領域の下端の座標が含ま れ、移動方向が上方向の場合には移動後の移 動領域の上下端および移動前の移動領域の上 端の座標が含まれる。

 分割部403は、移動領域有無判定部401から� ��動領域が検出されなかった旨の通知を受け� ��場合、第2の処理例と同様に画面全体を1つ� �更新領域検出域に設定する(ステップS523)。� �た、移動領域有無判定部401から移動領域が� �出された旨の通知を受けた場合、移動方向� �定部402からの通知に従って画面を分割する(� ��テップS524~S526)。具体的には、移動方向が下 方向の場合、移動後の移動領域の上下端と移 動前の移動領域の下端で画面を4分割し、各� �割領域をそれぞれ1つの更新領域検出域に設� ��する。また、移動方向が上方向の場合、移� ��後の移動領域の上下端と移動前の移動領域� ��上端で画面を4分割し、各分割領域をそれぞ れ1つの更新領域検出域に設定する。その後� �更新領域検出域毎に更新領域検出部125によ� �更新領域の検出が行われる。

 次に、本処理例の更新領域検出域設定部1 24による効果を説明する。以下では、移動方� ��が下方向の場合について説明しているが、� ��方向の場合も同様の効果が得られる。

 図27の左上及び右上は、図22の左上及び右 上と同様である。これに対して本例にかかる 図27の右下は、移動後の移動領域R30の上下端� ��よび移動前の移動領域の下端で画面R3が分� �線L271、L272及びL273により4分割され、各々の� ��新領域検出域で更新領域R31及びR32の検出が� ��われるため、更新領域の合計面積を最小限� ��抑えることができ、符号量の削減が可能に� ��る。

 また、図28の左上は、図25の左上と同様で ある。図28の右上は、図21の第1の処理例を適� ��し、移動後の上端のみで画面R2を分割線L281� ��より2分割した場合を示す。この場合、図28� ��右上に示すように検出された移動領域R20aを 含み、無駄に大きな更新領域R22及びR23が検出 されてしまう。これに対して本例にかかる図 28の右下は、移動後の移動領域R30bの上下端お よび移動前の移動領域の下端で画面R3が分割� ��L281、L282及びL283により4分割され、各々の更 新領域検出域で更新領域の検出が行われるた め、更新領域の合計面積を小さくでき、その 分、符号量の削減が可能になる。

 さらに、図29の左上は、画面R1において検 出された移動領域R14が実際の移動領域R12より も大きかった場合を示す。図29の右上は、図2 1の第1の処理例を適用し、移動後の上端のみ� ��画面R2を分割線L291により2分割した場合を示 す。この場合、図29の右上に示すように検出� ��れた移動領域R20bを含み、無駄に大きな更新 領域R24及びR25が検出されてしまう。また、図 29の右下は、図23の第2の処理例を適用し、移� ��後の移動領域R30cの上下端のみで画面R3を分� ��線L292及びL293により3分割した場合を示す。� ��の場合、図29の右下に示すように検出され� �移動領域R30cを含み、更新領域R351及びR352が� �や冗長になる。これに対して本例にかかる� �29の左下は、移動後の移動領域R40の上下端お よび移動前の移動領域の下端で画面R4が分割� ��L294、L295及びL296により4分割され、各々の更 新領域検出域で更新領域R41、R42及びR43の検出 が行われるため、第2の処理例に比べて更新� �域の合計面積を小さくでき、その分、符号� �の削減が可能になる。ただし、過剰検出さ� �る領域の面積がそれほど大きくないならば� �第2の処理例の方が更新領域の個数が少なく� ��る利点がある。

 図30を参照すると、更新領域検出域設定� �124の第2の実施例は、移動領域有無判定部411� ��、移動領域重複判定部412と、移動方向判定� ��413と、分割部414とから構成される。各々は� ��概ね以下のような機能を有する。

 移動領域有無判定部411および移動方向判� ��部413は、更新領域検出域設定部124の第1の実 施例における移動領域有無判定部401および移 動方向判定部402と同じ機能を有する。

 移動領域重複判定部412は、移動領域検出� ��122で検出された移動前後の移動領域の重な� ��の可能性の有無を判定する機能を有する。

 分割部414は、移動領域有無判定部411、移� ��領域重複判定部412および移動方向判定部413� ��判定結果に従って画面分割の必要性の判定� ��よび画面分割による更新領域検出域の設定� ��行う機能を有する。

 次に本実施例の更新領域検出域設定部124� ��処理例を説明する。

 更新領域検出域設定部124の移動領域有無� ��定部411は、第1の実施例の移動領域有無判定 部401と同様に移動領域が検出されたかどうか を判定し、判定結果を移動領域重複判定部412 および分割部414へ通知する(図31のステップS53 1)。

 移動領域重複判定部412は、移動前後の移� ��領域が重なっていないかを判定する(ステッ プS532)。具体的には、移動領域重複判定部412� ��、まず、移動領域が検出された旨の通知を� ��動領域有無判定部401から受け取る。次に、� ��動領域重複判定部412は、作業域113から移動� ��域検出部122の検出結果に含まれる移動前の� ��動領域の座標と移動後の移動領域の座標と� ��読み出す。そして、移動領域重複判定部412� ��、移動前の移動領域を上下左右に所定幅δ� �け拡大した領域と、移動後の移動領域を上� �左右に所定幅δだけ拡大した領域とが少なく とも一部で重なるかどうかを調べる。その後 、移動領域重複判定部412は、重なる場合には 移動領域の重複ありの判定結果を、重ならな い場合には移動領域の重複なしの判定結果を 移動方向判定部413および分割部414に通知する 。ここで、所定幅δは、移動領域の検出不足� ��生じる程度に応じて事前に設定される。

 移動方向判定部413は、移動方向を判定す� ��(ステップS533)。具体的には、移動方向判定� ��413は、まず、移動領域の重複なしの通知を� ��動領域重複判定部412から受け取る。次に、� ��動方向判定部413は、作業域113から読み出さ� ��た移動領域検出部122の検出結果に含まれる� ��動前の移動領域の座標と移動後の移動領域� ��座標とを比較することにより、移動方向が� ��方向、上方向の何れであるかを判定する。� ��して、移動方向判定部413は、判定結果を分� ��部414に通知する(ステップS533)。判定結果に� ��、第1の実施例における移動方向判定部402と 同様に移動方向以外に、画面を分割する座標 が含まれる。

 分割部414は、移動領域有無判定部411から� ��動領域が検出されなかった旨の通知を受け� ��場合、および移動領域重複判定部412から移� ��領域の重複なしの通知を受けた場合、画面� ��体を1つの更新領域検出域に設定する(ステ� �プS534)。他方、移動領域有無判定部411から移 動領域が検出された旨の通知を受けると共に 、移動領域重複判定部412から移動領域の重複 ありの通知を受けた場合、移動方向判定部413 からの通知に従って第1の実施例の分割部403� �第1の処理例、第2の処理例および第3の処理� �の何れかと同じように画面を分割して更新� �域検出域を設定する(ステップS535~S537)。その 後、更新領域検出域毎に更新領域検出部125に よる更新領域の検出が行われる。

 この第2の実施例の更新領域検出域設定部 124によれば、移動前後の移動領域が重なって いる可能性がない場合には画面を分割しない ので、更新領域の分割数の増加を抑えること ができる。

 図32を参照すると、更新領域検出域設定� �124の第3の実施例は、移動領域有無判定部501� ��、分割部502とから構成される。各々は、概� ��以下のような機能を有する。

 移動領域有無判定部501は、移動領域検出� ��122で移動領域が検出されたか否かを判定す� ��機能を有する。

 分割部502は、移動領域有無判定部501の判� ��結果に従って画面分割の必要性の判定およ� ��画面分割による更新領域検出域の設定を行� ��機能を有する。

 次に本実施例の更新領域検出域設定部124� ��第1の処理例を説明する。

 更新領域検出域設定部124の移動領域有無� ��定部501は、移動領域検出部122の検出結果を� ��業域113から読み出して解析することにより� ��移動領域が検出されたかどうかを判定し、� ��定結果を分割部502へ通知する(図33のステッ� ��S601)。

 分割部502は、移動領域有無判定部501から� ��動領域が検出されなかった旨の通知を受け� ��場合、画面全体を1つの更新領域検出域に設 定する(ステップS602)。また、移動領域有無判 定部401から移動領域が検出された旨の通知を 受けた場合、作業域113から移動領域検出部122 の検出結果に含まれる移動後の移動領域の座 標を読み出し、移動後の移動領域の上下端で 画面を3分割し(ステップS603)、各分割領域を� �れぞれ1つの更新領域検出域に設定する(ステ ップS604)。その後、更新領域検出域毎に更新� ��域検出部125による更新領域の検出が行われ� ��。

 第3の実施例の更新領域検出域設定部124の 第1の処理例による効果を説明する。以下で� �、移動方向が下方向の場合について説明し� �いるが、上方向の場合も同様の効果が得ら� �る。

 図34の左上及び右上は、図22の左上及び右 上と同様である。これに対して本例にかかる 図34の右下は、移動後の移動領域R30の上下端� ��画面R3が分割線L341及びL342により3分割され� �各々の更新領域検出域で更新領域R31及びR32� �検出が行われるため、更新領域の合計面積� �最小限に抑えることができ、符号量の削減� �可能になる。

 また、図35の左上は、図25の左上と同様で ある。図35の右上は、画面R2全体を更新領域� �出域に設定した場合を示す。この場合、図35 の右上に示すように検出された移動領域R20c� �含み、移動前後の移動領域を包含するよう� �移動領域R26が検出されてしまう。これに対� �て本例にかかる図35の右下は、移動後の移動 領域R30aの上下端で画面R3が分割線L351及びL352� ��より3分割され、各々の更新領域検出域で更 新領域R331、R332、R333及びR334の検出が行われ� �ため、更新領域の合計面積を小さくでき、� �の分、符号量の削減が可能になる。

 次に本実施例の更新領域検出域設定部124� ��第2の処理例を説明する。

 更新領域検出域設定部124の移動領域有無� ��定部501は、第1の処理例と同様に移動領域が 検出されたかどうかを判定し、判定結果を分 割部502へ通知する(図36のステップS611)。

 分割部502は、移動領域有無判定部501から� ��動領域が検出されなかった旨の通知を受け� ��場合、第1の処理例と同様に画面全体を1つ� �更新領域検出域に設定する(ステップS612)。� �た、移動領域有無判定部501から移動領域が� �出された旨の通知を受けた場合、作業域113� �ら移動領域検出部122の検出結果に含まれる� �動前後の移動領域の座標を読み出し、移動� �の移動領域の上下端と移動後の移動領域の� �下端とで画面を5分割し(ステップS613)、各分� ��領域をそれぞれ1つの更新領域検出域に設定 する(ステップS614)。その後、更新領域検出域 毎に更新領域検出部125による更新領域の検出 が行われる。

 第3の実施例の更新領域検出域設定部124の 第2の処理例による効果を説明する。以下で� �、移動方向が下方向の場合について説明し� �いるが、上方向の場合も同様の効果が得ら� �る。

 図37の左上及び右上は、図22の左上及び右 上と同様である。これに対して本例にかかる 図37の右下は、移動前後の移動領域R30の上下� ��で画面R3が分割線L371、L372、L373及びL374によ� ��5分割され、各々の更新領域検出域で更新領 域R31及びR32の検出が行われるため、更新領域 の合計面積を最小限に抑えることができ、符 号量の削減が可能になる。

 また、図38の左上及び右上は、図35の左上 及び右上と同様である。これに対して本例に かかる図38の右下は、移動前後の移動領域R30d の上下端で画面R3が分割線L381、L382、L383及びL 384により5分割され、各々の更新領域検出域� �更新領域R361、R362、R363、R364、R365、R366及びR3 67の検出が行われるため、更新領域の合計面� ��を小さくでき、その分、符号量の削減が可� ��になる。

 さらに、図39の左上は、図29の左上と同様 である。図39の右上は、図35の右上と同様で� �る。また、図39の右下は、第1の処理例を適� �し、移動後の移動領域R30cの上下端で画面R3� �分割線L391及びL392により3分割した場合を示� �。この場合、図39の右下に示すように検出さ れた移動領域R30cを含み、冗長な更新領域R351� ��びR352が検出される。これに対して本例にか かる図39の左下は、移動前後の移動領域R40の� ��下端で画面R4が分割線L393、L394、L395及びL396� ��より5分割され、各々の更新領域検出域で更 新領域R41、R42及びR43の検出が行われるため、 更新領域の合計面積を小さくでき、その分、 符号量の削減が可能になる。

 図40を参照すると、更新領域検出域設定� �124の第4の実施例は、移動領域有無判定部511� ��、移動領域重複判定部512と、分割部513とか� ��構成される。各々は、概ね以下のような機� ��を有する。

 移動領域有無判定部511は、更新領域検出� ��設定部124の第3の実施例における移動領域有 無判定部501と同じ機能を有する。

 移動領域重複判定部512は、移動領域検出� ��122で検出された移動前後の移動領域の重な� ��の可能性の有無を判定する機能を有する。

 分割部513は、移動領域有無判定部511およ� ��移動領域重複判定部512の判定結果に従って� ��面分割の必要性の判定および画面分割によ� ��更新領域検出域の設定を行う機能を有する� ��

 次に本実施例の更新領域検出域設定部124� ��処理例を説明する。

 更新領域検出域設定部124の移動領域有無� ��定部511は、第3の実施例の移動領域有無判定 部501と同様に移動領域が検出されたかどうか を判定し、判定結果を移動領域重複判定部512 および分割部513へ通知する(図41のステップS62 1)。

 移動領域重複判定部512は、移動前後の移� ��領域が重なっていないかを判定する(ステッ プS622)。具体的には、移動領域重複判定部512� ��、まず、移動領域が検出された旨の通知を� ��動領域有無判定部511から受け取る。次に、� ��動領域重複判定部512は、作業域113から移動� ��域検出部122の検出結果に含まれる移動前後� ��移動領域の座標を読み出す。そして、移動� ��域重複判定部512は、移動前の移動領域を上� ��左右に所定幅δだけ拡大した領域と、移動� �の移動領域を上下左右に所定幅δだけ拡大し た領域とが少なくとも一部で重なるかどうか を調べる。その後、移動領域重複判定部512は 、重なる場合には移動領域の重複ありの判定 結果を、重ならない場合には移動領域の重複 なしの判定結果を分割部513に通知する。ここ で、所定幅δは、移動領域の検出不足の生じ� ��程度に応じて事前に設定される。

 分割部513は、移動領域有無判定部512から� ��動領域が検出されなかった旨の通知を受け� ��場合、および移動領域重複判定部512から移� ��領域の重複なしの通知を受けた場合、画面� ��体を1つの更新領域検出域に設定する(ステ� �プS623)。他方、移動領域有無判定部512から移 動領域が検出された旨の通知を受けると共に 、移動領域重複判定部512から移動領域の重複 ありの通知を受けた場合、第3の実施例の分� �部502の第1の処理例および第2の処理例の何れ かと同じように画面を3分割または5分割して� ��新領域検出域を設定する(ステップS624、S625) 。その後、更新領域検出域毎に更新領域検出 部125による更新領域の検出が行われる。

 この第4の実施例の更新領域検出域設定部 124によれば、移動前後の移動領域が重なって いる可能性がない場合には画面を分割しない ので、更新領域の分割数の増加を抑えること ができる。

(4)更新領域検出部125
 図42を参照すると、更新領域検出部125の第1� ��実施例は、画素比較部601および更新領域抽� ��部602から構成され、更新領域検出域設定部1 24により設定された各々の更新領域検出域毎� ��、動き補償後の参照フレームと現フレーム� ��の差分領域である更新領域を検出する。画� ��比較部601および更新領域抽出部602は、概ね� ��下のような機能を有する。

 画素比較部601は、処理対象とする更新領� ��検出域毎に、動き補償後の参照フレームと� ��フレームとにおける同じ位置の画素の値の� ��分を、第1の閾値および第1の閾値よりも大� �な値の第2の閾値と比較する機能を有する。

 更新領域抽出部602は、処理対象とする更� ��領域検出域毎に、第1の閾値より大きな差分 が検出された画素の塊のうち、第2の閾値よ� �大きな差分が検出された画素を含む塊を更� �領域として抽出する機能を有する。

 次に本実施例の更新領域検出部125の動作� ��説明する。

 更新領域検出部125は、更新領域検出域設� ��部124が設定した更新領域検出域の情報を作� ��域113から読み出し、そのうちの1つの更新領 域検出域に注目する(図43のステップS701)。次� ��、注目中の更新領域検出域から更新領域の� ��出を行い、抽出結果を作業域113に保存する( ステップS702)。更新領域検出部125は、1つの更 新領域検出域からの更新領域の抽出処理を終 えると、次の1つの更新領域検出域に注目を� �し(ステップS703)、上述した処理と同様の処� �を繰り返す。全ての更新領域検出域からの� �新領域の抽出処理を終えると(ステップS704で YES)、図43の処理を終える。

 次にステップS702で実行される処理につい て、図44A及び図44Bのフローチャートを参照し て詳細に説明する。

 まず更新領域検出部125は、更新領域の抽� ��処理に使用する上端バッファ、下端バッフ� ��およびフラグバッファの初期化を行う(ステ ップS711)。各バッファはフレームの各列に1対 1に対応するエントリを有する。このうち、� �端バッファは、第1の閾値より大きな差分が� ��出された最上位行の行番号を各列毎に保持� ��るために使用し、下端バッファは、第1の閾 値より大きな差分が検出された最下位行の行 番号を各列毎に保持するために使用する。ま た、フラグバッファは、第2の閾値より大き� �差分が検出されたか否かを示すフラグを各� �毎に保持する。

 以降、更新領域検出部125の画素比較部601� ��よって以下のような処理が実行される。

 まず画素比較部601は、動き補償後の参照� ��レームと現フレームとの更新領域検出域に� ��まれる複数の画素のペアのうち、先頭の画� ��のペアに注目する(S712)。例えば、図45に示� �ように、注目中の更新領域検出域がフレー� �の1行目から始まる場合、動き補償後の参照� ��レームの画素P(0,0)と現フレームの画素P(0,0)� ��ペアに注目する。

 次に画素比較部601は、注目中の画素のペ� ��の画素値の差分を計算する(ステップS713)。� ��に、差分を第1の閾値と比較し(ステップS714) 、差分が第1の閾値より大きければ、上端バ� �ファおよび下端バッファを更新する(ステッ� ��S715)。具体的には、上端バッファについて� �、注目中の画素が位置する列に対応する上� �バッファのエントリがNULLであれば当該エン� ��リに注目中の画素が位置する行の番号を記� ��し、NULLでなく既に行番号が記録されていれ ばそのままにする。他方、下端バッファにつ いては、注目中の画素が位置する列に対応す る下端バッファのエントリに無条件に注目中 の画素が位置する行の番号を記録する。

 次に画素比較部601は、差分を第2の閾値と 比較し(ステップS716)、差分が第2の閾値より� �きければ、フラグバッファを更新する(ステ� ��プS717)。具体的には、注目中の画素が位置� �る列に対応するフラグバッファのエントリ� �無条件に1を記録する。

 次に画素比較部601は、双方のフレームに� ��ける同じ行の次の列の画素のペアに注目を� ��し(ステップS718)、ステップS713に戻る。差分 が第1の閾値より大きくない場合、上端バッ� �ァおよび下端バッファの更新は行わない。� �た、差分が第1の閾値より大きくても第2の閾 値より大きくなければ、フラグバッファの更 新は行わない。

 ここで、画素値の差分の計算は、例えばR 、G、Bの各成分毎に行う。また、第1および第 2の閾値との比較は、各成分の差分毎に行い� �少なくとも1つの成分の差分が閾値より大き� ��れば、画素値の差分が閾値より大きいと判� ��する。

 その後、画素比較部601は、注目中の更新� ��域検出域の1行分の画素のペアについての処 理を終える(ステップS719でYES)。そして、画素 比較部601は、処理の開始時点または更新領域 抽出部602を過去に呼び出していれば前回の呼 び出し時点から第1の閾値より大きな差分が� �く検出されなかった行の連続数、つまり非� �新行の連続数をカウントする(ステップS720)� �続いて、画素比較部601は、予め設定された� �値Lと非更新行の連続数とを比較する(ステッ プS721)。ここで、閾値Lは更新領域の過分割を 避けるために1以上の値(例えば8)に設定され� �。もし、非更新行の連続数が閾値Lを超えて� ��れば、更新領域抽出範囲の先頭行と最終行� ��を指定して、更新領域抽出部602を呼び出し� ��列分割による更新領域の検出処理を行わせ� ��(ステップS722)。更新領域の抽出範囲の先頭� ��は、更新領域抽出部602を過去に呼び出して� ��なければフレームの先頭行であり、呼び出� ��ていれば、前回の呼び出し時に指定した最� ��行の次の行である。また、更新領域の抽出� ��囲の最終行は、現時点において最後の列の� ��素の処理を終えた行である。

 画素比較部601は、更新領域抽出部602の処� ��が完了すると、フレームの次の行の先頭の� ��素のペアに注目を移し(ステップS723)、ステ� ��プS713に戻る。

 なお、画素比較部601は、非更新行の連続� ��が閾値Lを超えていなければ、更新領域抽出 部602は呼び出さずに、フレームの次の行の先 頭の画素のペアに注目を移し(ステップS723)、 ステップS713に戻る。

 さらに、画素比較部601は、注目中の更新� ��域検出域の最後の行の最後の画素のペアま� ��処理を終える(ステップS724でYES)。そして、� ��素比較部601は、処理の開始時点または更新� ��域抽出部602を過去に呼び出していれば前回� ��呼び出し時点から後に第1の閾値より大きな 差分が検出された行が存在したかどうかを判 定する(ステップS725)。ここで、存在しなかっ た場合には図44A及び図44Bの処理を終了する。 また、存在した場合には、更新領域抽出範囲 の先頭行と最終行とを指定して、更新領域抽 出部602を呼び出し(ステップS726)、列分割によ る更新領域の検出処理の完了後に図44A及び図 44Bの処理を終了する。更新領域の抽出範囲の 先頭行は、更新領域抽出部602を過去に呼び出 していなければフレームの先頭行であり、呼 び出していれば、前回の呼び出し時に指定し た最終行の次の行である。また更新領域の抽 出範囲の最終行はフレームの最終行である。

 図45の上側に描いたマトリクスは、動き� �償後の参照フレームと現フレームとの差分� �況の一例を示しており、1つの枡目が1つの画 素のペアの差分状況を示す。また、空白の枡 目は差分が第1の閾値よりも小さいことを、� �ッチングを施した枡目は差分が第1の閾値よ� ��大きく第2の閾値より小さいことを、黒く塗 りつぶした枡目は差分が第2の閾値より大き� �ことをそれぞれ示す。このような状況の下� �、フレームの9行目までの範囲について画素� ��較部601で上述したような動作が行われると� ��上端バッファ、下端バッファおよびフラグ� ��ッファには、図45の下側に示すような内容� �記録される。ここで、上端バッファおよび� �端バッファ中の数値は行の番号を示し、記� �「-」はNULLを示す。また、フラグバッファ中 の0、1はフラグの値を示し、第2の閾値を超え たことは値1で示される。そして、上記閾値L� ��例えば3行とすると、9行目までの処理を終� �た時点で非更新行の連続数が4となり、閾値L を超えるので、更新領域抽出部602が呼び出さ れることになる。

 次に、更新領域抽出部602が実行する列分� ��による更新領域の検出処理について、図46� �フローチャートを参照して説明する。

 更新領域抽出部602は、上端バッファまた� ��下端バッファを参照して、今回の呼び出し� ��指定された更新領域抽出範囲から更新列(差 分画素が存在した列のまとまり)と非更新列(� ��分画素が存在しなかった列のまとまり)を抽 出する(ステップS731)。例えば図45の場合、上� ��バッファのエントリを列0から順に参照する と、NULLが1つ連続しているので、0列を非更新 列(0-0)として抽出し、次に数値が記録された� ��ントリが5つ連続しているので、1列から5列� ��でを更新列(1-5)として抽出する。以下同様� �、非更新列(6-7)、更新列(8-9)、非更新列(10-14) 、更新列(15-16)等を抽出する。

 次に更新領域抽出部602は、更新領域の過� ��割を避けるために、所定列数W以下の非更新 列を間にして互いに隣接する更新列を1つの� �新列に結合する(ステップS732)。例えば、Wを3 とすると、図45の場合、更新列(1-5)と更新列(8 -9)は更新列(1-9)として結合される。

 次に更新領域抽出部602は、フラグバッフ� ��を参照して、フラグの値が全て0の更新列を 非更新列に変更する(ステップS733)。例えば図 45の場合、結合後の更新列(1-9)についてフラ� �バッファ中の列1~列9に対応するフラグを参� �すると、値1が含まれているので、更新列(1-9 )はそのままとする。他方、更新列(15-16)につ� ��てフラグバッファ中の列15-16に対応するフ� �グを参照すると、すべて値0なので、更新列( 15-16)はノイズによって生じた可能性が高いと 判断して非更新列に変更される。

 次に更新領域抽出部602は、各更新列毎に� ��差分画素が発生する最上端と最下端の行を� ��べ、その更新列の左端と右端と合わせて、� ��新領域を定める更新矩形を確定する(ステッ プS734)。この処理により、更新列(1-9)につい� �は、上端バッファを参照すると最上端は2、� ��端バッファを参照すると最下端は5、その更 新列の左端は1、右端は9なので、更新矩形を� ��上および右下の端点で規定する場合、左上� ��点(2,1)、右下端点(5,9)として求められる。こ うして求められた更新領域の情報(更新矩形� �座標)は、更新領域検出結果の一部として作� ��域113に記録される。

 次に更新領域抽出部602は、上端バッファ� ��下端バッファおよびフラグバッファの初期� ��を行い(ステップS735)、図46の処理を終了す� �。なお、図46の処理では、所定列数W以下の� �更新列を間にして互いに隣接する更新列を1� ��の更新列に結合した後、第2の閾値を超える 画素が存在しない更新列を非更新列に変更し た。しかし、それとは逆に、第2の閾値を超� �る画素が存在しない更新列を非更新列に変� �した後、所定列数W以下の非更新列を間にし� ��互いに隣接する更新列を1つの更新列に結合 する処理を行うようにしても良い。

 次に本実施例の更新領域検出部125の効果� ��説明する。

 本実施例の更新領域検出部125によれば、� ��ナログキャプチャされたコンピュータ画面� ��更新領域を精度良く検出することができる� ��その理由は、第1の閾値とそれより大きな第 2の閾値との2種類の閾値を使用し、第1の閾値 より大きな差分が検出された画素の塊のうち 、第2の閾値より大きな差分が検出された画� �を含む塊を更新領域として抽出するためで� �る。これにより、第1の閾値だけを使用して� ��新領域を検出した場合に起こり易い更新領� ��の過度検出が防止でき、かつ、第2の閾値だ けを使用して更新領域を検出した場合に起こ り易い更新領域の検出不足が防止できる。

 具体的には、例えば動画などのグラデー� ��ョン部に画素変化があった場合、単一の画� ��値の変化量だけを参照しても、画素が描画� ��新されたのか、アナログキャプチャに伴う� ��イズによる画素値変動なのかを識別するこ� ��は難しい。こうした理由から単一の閾値で� ��、動画において更新領域の検出に失敗する� ��合があった。例えば、画面中央の動画ウィ� ��ドウのみが前後フレーム1、2で更新されて� �る図47に示す実験例では、更新領域として中 央の動画ウィンドウ全体が検出されることが 望ましい。しかし、小さな値の閾値だけを使 用すると、図47の左下に示すように検出領域� ��過大となり、逆に大きな値の閾値だけを使� ��すると、図47の右下に示すように検出領域� �不足した。検出が過大になると、画面更新� �僅かな場合にも符号量が増大してしまう。� �た、検出漏れが複数フレームにわたって発� �すると、検出に成功した領域と検出漏れし� �領域との間で、輝度不連続な境界が知覚さ� �るようになる。

 これに対して、差分判定用の閾値を2種類 (大と小)設定した本実施例の更新領域検出部1 25によれば、図48の実験例に示すように、中� �の動画ウィンドウ全体を過不足なく更新領� �として検出することができた。

 また本実施例の更新領域検出部125によれ� ��、更新領域検出域内に存在する全ての更新� ��域に外接する1つの矩形で更新領域を検出す る手法に較べて、更新領域を無駄に大きく検 出することを防止できる。

 また本実施例の更新領域検出部125によれ� ��、コンピュータ画面の更新領域を高速に検� ��することができる。その理由は、フレーム� ��各列について差分画素の上端および下端の� ��標を保持する上端および下端バッファと、� ��照フレームと現フレームの画素をラスタス� ��ャン順に比較して、差分が第1の閾値以上と なる画素が見つかったら上端および下端バッ ファの該当列の上端および下端の座標を書き 換える画素比較部601と、非更新行が所定行連 続したら上端および下端バッファを参照して 更新領域を確定する更新領域抽出部602とを備 えており、いわゆる1パス処理で更新領域の� �出が行えるためである。

 以上、本発明の移動領域検出装置を映像� ��号符号化装置に適用した実施の形態及び実� ��例について説明したが、本発明は、上述し� ��実施の形態及び実施例に限定されるもので� ��ない。本発明の構成や詳細には、既に述べ� ��本発明の要旨を逸脱しない範囲において種� ��の変更が可能であることは勿論である。

 尚、本発明の他の実施の形態には、以下の� ��のも含まれる。
(付記1)
 前フレームと現フレームの何れにも存在す� ��同一または類似の画像領域であって画面上� ��の位置が変化している画像領域を移動領域� ��して検出する移動領域検出装置において、
 移動領域の初期候補を決定する初期候補決� ��手段と、
 前記初期候補決定手段で決定された移動領� ��の初期候補および該初期候補の移動領域の� ��イズを変更した1以上の他の移動領域の候補 のうちから動き補償に使用する移動領域を決 定する移動領域決定手段とを備えることを特 徴とする移動領域検出装置。
(付記2)
 前記移動領域決定手段は、移動領域の初期� ��補の各辺毎に、動き補償を行った場合の動� ��補償後の画素値と真の画素値との比較結果� ��従って、拡大可能な最大拡大幅を算出して� ��大後の辺の位置を確定する拡大処理を行う� ��とを特徴とする付記1に記載の移動領域検出 装置。
(付記3)
 前記移動領域決定手段は、初期候補の移動� ��域を使って動き補償を行った場合の動き補� ��後の画素値と真の画素値との比較結果に従� ��て、初期候補を棄却するか否かを決定し、� ��期候補を棄却しないと決定した場合に前記� ��大処理を行うことを特徴とする付記2に記載 の移動領域検出装置。
(付記4)
 前記移動領域決定手段は、初期候補を棄却� ��ないと決定した場合に、移動領域の初期候� ��の各辺毎に、動き補償を行った場合の動き� ��償後の画素値と真の画素値との比較結果に� ��って、移動領域として縮小可能な最大縮小� ��を算出し、最大縮小幅が0でなければ最大縮 小幅により縮小後の辺の位置を確定する縮小 処理を行い、最大縮小幅が0でない辺につい� �前記拡大処理を行うことを特徴とする付記3� ��記載の移動領域検出装置。
(付記5)
 前記移動領域決定手段は、初期候補を棄却� ��ると決定した場合に、移動領域の初期候補� ��各辺毎に、動き補償を行った場合の動き補� ��後の画素値と真の画素値との比較結果に従� ��て、移動領域として縮小可能な最大縮小幅� ��算出して縮小後の辺の位置を確定する縮小� ��理を行うことを特徴とする付記3に記載の移 動領域検出装置。
(付記6)
 前記移動領域決定手段は、移動領域の初期� ��補の各辺毎に、動き補償を行った場合の動� ��補償後の画素値と真の画素値との比較結果� ��従って、移動領域として縮小可能な最大縮� ��幅を算出し、最大縮小幅が0でなければ最大 縮小幅により縮小後の辺の位置を確定する縮 小処理を行い、最大縮小幅が0でない辺につ� �て前記拡大処理を行うことを特徴とする付� �2に記載の移動領域検出装置。
(付記7)
 前記移動領域決定手段は、移動領域が動き� ��償に使用する移動領域として適している程� ��および適していない程度をそれぞれ示すメ� ��ット値およびデメリット値を評価尺度とし� ��使用し、動き補償後の画素値と真の画素値� ��の差分が所定の閾値以上となる画素が検出� ��れる毎に前記デメリット値を所定値だけ加� ��し、動き補償後の画素値と真の画素値との� ��分が所定の閾値より小さな画素であって且� ��隣接する画素との間に閾値以上の輝度勾配� ��ある画素が検出される毎に前記メリット値� ��所定値だけ加算する処理を、初期候補の移� ��領域の全体について行い、最終的に得られ� ��前記メリット値と前記デメリット値との比� ��結果に基づいて、初期候補を棄却するか否� ��を決定することを特徴とする付記3に記載の 移動領域検出装置。
(付記8)
 前記移動領域決定手段は、移動領域の各辺� ��に、所定の画素幅単位で拡大可能か否かを� ��定し、該判定に際しては、移動領域が動き� ��償に使用する移動領域として適している程� ��および適していない程度をそれぞれ示すメ� ��ット値およびデメリット値を評価尺度とし� ��使用し、動き補償後の画素値と真の画素値� ��の差分が所定の閾値以上となる画素が検出� ��れる毎に前記デメリット値を所定値だけ加� ��し、動き補償後の画素値と真の画素値との� ��分が所定の閾値より小さな画素であって且� ��隣接する画素との間に閾値以上の輝度勾配� ��ある画素が検出される毎に前記メリット値� ��所定値だけ加算する処理を、拡大した移動� ��域の全体について行い、最終的に得られた� ��記メリット値と前記デメリット値との比較� ��果に基づいて、拡大の可否を判断すること� ��特徴とする付記2に記載の移動領域検出装置 。
(付記9)
 前記移動領域決定手段は、移動領域の各辺� ��に、所定の画素幅単位で縮小可能か否かを� ��定し、該判定に際しては、移動領域が動き� ��償に使用する移動領域として適している程� ��および適していない程度をそれぞれ示すメ� ��ット値およびデメリット値を評価尺度とし� ��使用し、動き補償後の画素値と真の画素値� ��の差分が所定の閾値以上となる画素が検出� ��れる毎に前記デメリット値を所定値だけ加� ��し、動き補償後の画素値と真の画素値との� ��分が所定の閾値より小さな画素であって且� ��隣接する画素との間に閾値以上の輝度勾配� ��ある画素が検出される毎に前記メリット値� ��所定値だけ加算する処理を、縮小した移動� ��域の全体について行い、最終的に得られた� ��記メリット値と前記デメリット値との比較� ��果に基づいて、縮小の可否を判断すること� ��特徴とする付記3に記載の移動領域検出装置 。
(付記10)
 他の1以上のエッジ点との位置関係がフレー ム内で一意なエッジ点を特徴点として前フレ ームおよび現フレームから抽出し、前フレー ムおよび現フレームにおいて同じ一意な位置 関係を持つ特徴点のペアを抽出する移動ベク トル検出手段を備え、
 前記初期候補決定手段は、前記移動ベクト� ��検出手段で抽出された特徴点のペアのうち� ��前フレームに存在する特徴点の外接矩形を� ��フレームにおける移動領域の初期候補、前� ��移動ベクトル検出手段で抽出された特徴点� ��ペアのうちの現フレームに存在する特徴点� ��外接矩形を現フレームにおける移動領域の� ��期候補とすることを特徴とする付記1に記載 の移動領域検出装置。
(付記11)
 前フレームと現フレームの何れにも存在す� ��同一または類似の画像領域であって画面上� ��の位置が変化している画像領域を移動領域� ��して検出する移動領域検出方法において、
 a)初期候補決定手段が、移動領域の初期候� �を決定するステップと、
 b)移動領域決定手段が、前記初期候補決定� �段で決定された移動領域の初期候補および� �初期候補の移動領域のサイズを変更した1以� ��の他の移動領域の候補のうちから動き補償� ��使用する移動領域を決定するステップとを� ��むことを特徴とする移動領域検出方法。
(付記12)
 前記移動領域決定手段は、移動領域の初期� ��補の各辺毎に、動き補償を行った場合の動� ��補償後の画素値と真の画素値との比較結果� ��従って、拡大可能な最大拡大幅を算出して� ��大後の辺の位置を確定する拡大処理を行う� ��とを特徴とする付記11に記載の移動領域検� �方法。
(付記13)
 前記移動領域決定手段は、初期候補の移動� ��域を使って動き補償を行った場合の動き補� ��後の画素値と真の画素値との比較結果に従� ��て、初期候補を棄却するか否かを決定し、� ��期候補を棄却しないと決定した場合に前記� ��大処理を行うことを特徴とする付記12に記� �の移動領域検出方法。
(付記14)
 前記移動領域決定手段は、初期候補を棄却� ��ないと決定した場合に、移動領域の初期候� ��の各辺毎に、動き補償を行った場合の動き� ��償後の画素値と真の画素値との比較結果に� ��って、移動領域として縮小可能な最大縮小� ��を算出し、最大縮小幅が0でなければ最大縮 小幅により縮小後の辺の位置を確定する縮小 処理を行い、最大縮小幅が0でない辺につい� �前記拡大処理を行うことを特徴とする付記13 に記載の移動領域検出方法。
(付記15)
 前記移動領域決定手段は、初期候補を棄却� ��ると決定した場合に、移動領域の初期候補� ��各辺毎に、動き補償を行った場合の動き補� ��後の画素値と真の画素値との比較結果に従� ��て、移動領域として縮小可能な最大縮小幅� ��算出して縮小後の辺の位置を確定する縮小� ��理を行うことを特徴とする付記13に記載の� �動領域検出方法。
(付記16)
 前記移動領域決定手段は、移動領域の初期� ��補の各辺毎に、動き補償を行った場合の動� ��補償後の画素値と真の画素値との比較結果� ��従って、移動領域として縮小可能な最大縮� ��幅を算出し、最大縮小幅が0でなければ最大 縮小幅により縮小後の辺の位置を確定する縮 小処理を行い、最大縮小幅が0でない辺につ� �て前記拡大処理を行うことを特徴とする付� �12に記載の移動領域検出方法。
(付記17)
 前記移動領域決定手段は、移動領域が動き� ��償に使用する移動領域として適している程� ��および適していない程度をそれぞれ示すメ� ��ット値およびデメリット値を評価尺度とし� ��使用し、動き補償後の画素値と真の画素値� ��の差分が所定の閾値以上となる画素が検出� ��れる毎に前記デメリット値を所定値だけ加� ��し、動き補償後の画素値と真の画素値との� ��分が所定の閾値より小さな画素であって且� ��隣接する画素との間に閾値以上の輝度勾配� ��ある画素が検出される毎に前記メリット値� ��所定値だけ加算する処理を、初期候補の移� ��領域の全体について行い、最終的に得られ� ��前記メリット値と前記デメリット値との比� ��結果に基づいて、初期候補を棄却するか否� ��を決定することを特徴とする付記13に記載� �移動領域検出方法。
(付記18)
 前記移動領域決定手段は、移動領域の各辺� ��に、所定の画素幅単位で拡大可能か否かを� ��定し、該判定に際しては、移動領域が動き� ��償に使用する移動領域として適している程� ��および適していない程度をそれぞれ示すメ� ��ット値およびデメリット値を評価尺度とし� ��使用し、動き補償後の画素値と真の画素値� ��の差分が所定の閾値以上となる画素が検出� ��れる毎に前記デメリット値を所定値だけ加� ��し、動き補償後の画素値と真の画素値との� ��分が所定の閾値より小さな画素であって且� ��隣接する画素との間に閾値以上の輝度勾配� ��ある画素が検出される毎に前記メリット値� ��所定値だけ加算する処理を、拡大した移動� ��域の全体について行い、最終的に得られた� ��記メリット値と前記デメリット値との比較� ��果に基づいて、拡大の可否を判断すること� ��特徴とする付記12に記載の移動領域検出方� �。
(付記19)
 前記移動領域決定手段は、移動領域の各辺� ��に、所定の画素幅単位で縮小可能か否かを� ��定し、該判定に際しては、移動領域が動き� ��償に使用する移動領域として適している程� ��および適していない程度をそれぞれ示すメ� ��ット値およびデメリット値を評価尺度とし� ��使用し、動き補償後の画素値と真の画素値� ��の差分が所定の閾値以上となる画素が検出� ��れる毎に前記デメリット値を所定値だけ加� ��し、動き補償後の画素値と真の画素値との� ��分が所定の閾値より小さな画素であって且� ��隣接する画素との間に閾値以上の輝度勾配� ��ある画素が検出される毎に前記メリット値� ��所定値だけ加算する処理を、縮小した移動� ��域の全体について行い、最終的に得られた� ��記メリット値と前記デメリット値との比較� ��果に基づいて、縮小の可否を判断すること� ��特徴とする付記13に記載の移動領域検出方� �。
(付記20)
 c)移動ベクトル検出手段が、他の1以上のエ� ��ジ点との位置関係がフレーム内で一意なエ� ��ジ点を特徴点として前フレームおよび現フ� ��ームから抽出し、前フレームおよび現フレ� ��ムにおいて同じ一意な位置関係を持つ特徴� ��のペアを抽出するステップを含み、
 前記初期候補決定手段は、前記移動ベクト� ��検出手段で抽出された特徴点のペアのうち� ��前フレームに存在する特徴点の外接矩形を� ��フレームにおける移動領域の初期候補、前� ��移動ベクトル検出手段で抽出された特徴点� ��ペアのうちの現フレームに存在する特徴点� ��外接矩形を現フレームにおける移動領域の� ��期候補とすることを特徴とする付記11に記� �の移動領域検出方法。
(付記21)
 前フレームと現フレームの何れにも存在す� ��同一または類似の画像領域であって画面上� ��の位置が変化している画像領域を移動領域� ��して検出するコンピュータを、
 移動領域の初期候補を決定する初期候補決� ��手段と、
 前記初期候補決定手段で決定された移動領� ��の初期候補および該初期候補の移動領域の� ��イズを変更した1以上の他の移動領域の候補 のうちから動き補償に使用する移動領域を決 定する移動領域決定手段として機能させるた めの移動領域検出プログラムを前記コンピュ ータに読取可能に記録するプログラム記録媒 体。
(付記22)
 前記移動領域決定手段は、移動領域の初期� ��補の各辺毎に、動き補償を行った場合の動� ��補償後の画素値と真の画素値との比較結果� ��従って、拡大可能な最大拡大幅を算出して� ��大後の辺の位置を確定する拡大処理を行う� ��とを特徴とする付記21に記載の移動領域検� �プログラムを記録するプログラム記録媒体� �
(付記23)
 前記移動領域決定手段は、初期候補の移動� ��域を使って動き補償を行った場合の動き補� ��後の画素値と真の画素値との比較結果に従� ��て、初期候補を棄却するか否かを決定し、� ��期候補を棄却しないと決定した場合に前記� ��大処理を行うことを特徴とする付記22に記� �の移動領域検出プログラムを記録するプロ� �ラム記録媒体。
(付記24)
 前記移動領域決定手段は、初期候補を棄却� ��ないと決定した場合に、移動領域の初期候� ��の各辺毎に、動き補償を行った場合の動き� ��償後の画素値と真の画素値との比較結果に� ��って、移動領域として縮小可能な最大縮小� ��を算出し、最大縮小幅が0でなければ最大縮 小幅により縮小後の辺の位置を確定する縮小 処理を行い、最大縮小幅が0でない辺につい� �前記拡大処理を行うことを特徴とする付記23 に記載の移動領域検出プログラムを記録する プログラム記録媒体。
(付記25)
 前記移動領域決定手段は、初期候補を棄却� ��ると決定した場合に、移動領域の初期候補� ��各辺毎に、動き補償を行った場合の動き補� ��後の画素値と真の画素値との比較結果に従� ��て、移動領域として縮小可能な最大縮小幅� ��算出して縮小後の辺の位置を確定する縮小� ��理を行うことを特徴とする付記23に記載の� �動領域検出プログラムを記録するプログラ� �記録媒体。
(付記26)
 前記移動領域決定手段は、移動領域の初期� ��補の各辺毎に、動き補償を行った場合の動� ��補償後の画素値と真の画素値との比較結果� ��従って、移動領域として縮小可能な最大縮� ��幅を算出し、最大縮小幅が0でなければ最大 縮小幅により縮小後の辺の位置を確定する縮 小処理を行い、最大縮小幅が0でない辺につ� �て前記拡大処理を行うことを特徴とする付� �22に記載の移動領域検出プログラムを記録す るプログラム記録媒体。
(付記27)
 前記移動領域決定手段は、移動領域が動き� ��償に使用する移動領域として適している程� ��および適していない程度をそれぞれ示すメ� ��ット値およびデメリット値を評価尺度とし� ��使用し、動き補償後の画素値と真の画素値� ��の差分が所定の閾値以上となる画素が検出� ��れる毎に前記デメリット値を所定値だけ加� ��し、動き補償後の画素値と真の画素値との� ��分が所定の閾値より小さな画素であって且� ��隣接する画素との間に閾値以上の輝度勾配� ��ある画素が検出される毎に前記メリット値� ��所定値だけ加算する処理を、初期候補の移� ��領域の全体について行い、最終的に得られ� ��前記メリット値と前記デメリット値との比� ��結果に基づいて、初期候補を棄却するか否� ��を決定することを特徴とする付記23に記載� �移動領域検出プログラムを記録するプログ� �ム記録媒体。
(付記28)
 前記移動領域決定手段は、移動領域の各辺� ��に、所定の画素幅単位で拡大可能か否かを� ��定し、該判定に際しては、移動領域が動き� ��償に使用する移動領域として適している程� ��および適していない程度をそれぞれ示すメ� ��ット値およびデメリット値を評価尺度とし� ��使用し、動き補償後の画素値と真の画素値� ��の差分が所定の閾値以上となる画素が検出� ��れる毎に前記デメリット値を所定値だけ加� ��し、動き補償後の画素値と真の画素値との� ��分が所定の閾値より小さな画素であって且� ��隣接する画素との間に閾値以上の輝度勾配� ��ある画素が検出される毎に前記メリット値� ��所定値だけ加算する処理を、拡大した移動� ��域の全体について行い、最終的に得られた� ��記メリット値と前記デメリット値との比較� ��果に基づいて、拡大の可否を判断すること� ��特徴とする付記22に記載の移動領域検出プ� �グラムを記録するプログラム記録媒体。
(付記29)
 前記移動領域決定手段は、移動領域の各辺� ��に、所定の画素幅単位で縮小可能か否かを� ��定し、該判定に際しては、移動領域が動き� ��償に使用する移動領域として適している程� ��および適していない程度をそれぞれ示すメ� ��ット値およびデメリット値を評価尺度とし� ��使用し、動き補償後の画素値と真の画素値� ��の差分が所定の閾値以上となる画素が検出� ��れる毎に前記デメリット値を所定値だけ加� ��し、動き補償後の画素値と真の画素値との� ��分が所定の閾値より小さな画素であって且� ��隣接する画素との間に閾値以上の輝度勾配� ��ある画素が検出される毎に前記メリット値� ��所定値だけ加算する処理を、縮小した移動� ��域の全体について行い、最終的に得られた� ��記メリット値と前記デメリット値との比較� ��果に基づいて、縮小の可否を判断すること� ��特徴とする付記23に記載の移動領域検出プ� �グラムを記録するプログラム記録媒体。
(付記30)
 前記コンピュータを、さらに、
 他の1以上のエッジ点との位置関係がフレー ム内で一意なエッジ点を特徴点として前フレ ームおよび現フレームから抽出し、前フレー ムおよび現フレームにおいて同じ一意な位置 関係を持つ特徴点のペアを抽出する移動ベク トル検出手段として機能させ、
 前記初期候補決定手段は、前記移動ベクト� ��検出手段で抽出された特徴点のペアのうち� ��前フレームに存在する特徴点の外接矩形を� ��フレームにおける移動領域の初期候補、前� ��移動ベクトル検出手段で抽出された特徴点� ��ペアのうちの現フレームに存在する特徴点� ��外接矩形を現フレームにおける移動領域の� ��期候補とすることを特徴とする付記21に記� �の移動領域検出プログラムを記録するプロ� �ラム記録媒体。
(付記31)
 前フレームと現フレームを比較して移動ベ� ��トルを検出する移動ベクトル検出手段と、
 前フレームと現フレームとの何れにも存在� ��る同一または類似の画像領域であって、画� ��上での位置が前記移動ベクトル検出手段で� ��出された移動ベクトルだけ変化している画� ��領域を移動領域として検出する移動領域検� ��手段と、
 前記移動領域検出手段で検出された移動領� ��を前フレーム上の移動ベクトルが示す移動� ��に複写する動き補償手段と、
 動き補償後の前フレームと現フレームとが� ��違する領域を更新領域として検出する更新� ��域検出手段と、
 前記更新領域検出手段で検出された更新領� ��を画像として符号化する領域符号化手段と� ��備えた映像信号符号化装置であって、
 前記移動領域検出手段として、付記1に記載 の移動領域検出装置を使用した映像信号符号 化装置。
(付記32)
 前記更新領域検出手段が更新領域を検出す� ��更新領域検出域を、フレーム上に設定する� ��新領域検出域設定手段を備えることを特徴� ��する付記31記載の映像信号符号化装置。

 この出願は、2008年2月14日に出願された日 本出願特願2008-033042を基礎とする優先権を主� ��し、その開示の全てをここに取り込む。