(57)【特許請求の範囲】
【請求項１】
第一の画像における関心領域の輪郭情報に基づき、前記関心領域の輪郭線の上または近傍から少なくとも三点の特徴点を選出する選出手段と、
前記選出手段が選出した、前記第一の画像における特徴点間の連結関係を記憶する記憶手段と、
前記選出手段が選出した、前記第一の画像における特徴点それぞれに対応する、前記第一の画像と異なる時刻または異なる視点で撮像された第二の画像の対応点を探索する探索手段と、
前記記憶手段に記憶された連結関係に基づき、前記探索手段が検出した対応点のうち前記連結関係にある二点の一方をトレースの始点、他方を前記トレースの終点として、前記二点間においてエッジ強度が大きい画素を順次トレースし、前記第一の画像における関心領域に対応する前記第二の画像における関心領域の輪郭線を抽出する抽出手段とを有し、
前記抽出手段は、前記トレースにおける注目点の画素に隣接する近傍画素について前記エッジ強度を比較する際に、前記注目点と前記終点の位置関係に応じて決まる前記トレースの進行方向、前記進行方向に直交する方向、および、前記進行方向と前記直交する方向に挟まれた方向への進行を許可するマスキングを前記近傍画素に施して、前記トレースの進行方向を制限することを特徴とする画像処理装置。
【請求項２】
前記抽出手段は、前記第二の画像における関心領域の輪郭線を抽出するために、前記探索手段が検出した対応点の少なくとも一部を用いることを特徴とする請求項1に記載された画像処理装置。
【請求項３】
前記選出手段による特徴点の選出は、前記関心領域の輪郭線の形状情報に基づき行われることを特徴とする請求項1または請求項2に記載された画像処理装置。
【請求項４】
前記選出手段による特徴点の選出は、前記関心領域の輪郭線の上または近傍の画像情報に基づき行われることを特徴とする請求項1または請求項2に記載された画像処理装置。
【請求項５】
前記抽出手段は、前記始点および終点の対応点を入れ替えて、前記トレースを双方向に行い、それらトレース結果の何れかを用いて前記第二の画像における関心領域の輪郭線を抽出することを特徴とする請求項1から請求項4の何れか一項に記載された画像処理装置。
【請求項６】
前記選出手段は、前記双方向のトレース結果が一致する区間に基づき、新たな特徴点を選出することを特徴とする請求項5に記載された画像処理装置。
【請求項７】
前記抽出手段は、前記直交する方向に比べて、前記進行方向および前記挟まれた方向に前記トレースが進行し易いように重み付けされたマスクを前記マスキングに利用することを特徴とする請求項1から請求項6の何れか一項に記載された画像処理装置。
【請求項８】
前記マスキングは、前記注目点が前記終点に常に近付くように、前記トレースを視野制限することを特徴とする請求項1から請求項6の何れか一項に記載された画像処理装置。
【請求項９】
前記マスキングは、前記注目点がその軌跡に戻らないように、前記トレースを視野制限することを特徴とする請求項1から請求項6の何れか一項に記載された画像処理装置。
【請求項１０】
前記抽出手段は、異なる視野制限特性を有する複数組のマスクを備え、トレース区間の画像情報に応じて前記複数組のマスクを選択的に使用して前記マスキングを行うことを特徴とする請求項1から請求項6の何れか一項に記載された画像処理装置。
【請求項１１】
前記抽出手段は、異なる重み付けが施された複数組のマスクを備え、トレース区間の画像情報に応じて前記複数組のマスクを選択的に使用して前記マスキングを行うことを特徴とする請求項1から請求項6の何れか一項に記載された画像処理装置。
【請求項１２】
第一の画像における関心領域の輪郭情報に基づき、前記関心領域の輪郭線の上または近傍から少なくとも三点の特徴点を選出する選出ステップと、
前記選出ステップで選出した、第一の画像における特徴点間の連結関係をメモリに格納する格納ステップと、
前記選出ステップで選出した、前記第一の画像における特徴点それぞれに対応する、前記第一の画像と異なる時刻または異なる視点で撮像された第二の画像の対応点を探索する探索ステップと、
前記メモリに格納された連結関係に基づき、前記探索ステップで検出した対応点のうち前記連結関係にある二点の一方をトレースの始点、他方を前記トレースの終点として、前記二点間においてエッジ強度が大きい画素を順次トレースし、前記第一の画像における関心領域に対応する前記第二の画像における関心領域の輪郭線を抽出する抽出ステップとを有し、
前記抽出ステップにおいて、前記トレースにおける注目点の画素に隣接する近傍画素について前記エッジ強度を比較する際に、前記注目点と前記終点の位置関係に応じて決まる前記トレースの進行方向、前記進行方向に直交する方向、および、前記進行方向と前記直交する方向に挟まれた方向への進行を許可するマスキングを前記近傍画素に施して、前記トレースの進行方向を制限することを特徴とする画像処理方法。
【請求項１３】
コンピュータ装置を請求項1から請求項11の何れか一項に記載された画像処理装置の各手段として機能させるプログラムが記録されたことを特徴とするコンピュータが読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像処理装置およびその方法に関し、例えば、動画像または多視点画像における関心領域を抽出する画像処理装置およびその方法に関する。
【０００２】
【従来の技術】
複数枚の画像のセットから特定の関心領域を自動抽出する代表的な技術には(1)動きベクトルを利用する手法、(2)動的輪郭モデルに基づく手法がある。以下に、手法1、2それぞれに属する例を具体的に説明する。
【０００３】
［動きベクトルを用いる手法］
動画像の動き補償フレーム間予測符号化においては、入力画像を予め定めた大きさのブロックに分割し、ブロック単位に動き補償フレーム間予測を行うことが一般的である。これに対し、本特許は、予め定めた閾値より予測誤差が大きなブロックは、異なる動きをする物体の境界を含む可能性があるとして、そのブロックを細分割し、細分割された部分単位に、動き補償フレーム間予測符号化を行う手段を有する。つまり、動きの異なる被写体間の境界部の解像度を高めることで、符号化効率を上げようとする。
【０００４】
●特許第2616552号（動画像の符号化・復号装置）
入力画像の画素ごとに得た動きベクトルを用いて、動き補償フレーム間予測を行う符号化・復号装置である。入力画像から被写体領域の輪郭線データを検出する手段を有し、画素ごとの動きベクトルを内挿演算で求める際、その内挿演算に異なる物体の動きベクトルを用いないようにして、輪郭線近傍の急峻な動きベクトルの変化をより正確に再現し、符号化効率を改善しようとする。
【０００５】
●特開平8-335268号（領域袖出方法）
入力動画像の前フレームで関心領域の輪郭が与えられたとして、前フレームと現フレームとの間でブロックマッチングを行い、輪郭上の特徴点の動きベクトルを推定する。次に、動きベクトルの推定結果から、現フレームにおける輪郭の候補位置を決定する。その輪郭候補領域内で、現フレームのグラディエントベクトル場を計算する。最後に、そのグラディエントベクトル場のベクトルの大きさが大きい点を通過するような三次スプライン曲線を生成することにより、関心領域を抽出する。
【０００６】
［動的輪郭モデルに基づく手法］
M. Kass, A. Witkin, D. Terzopoulos, "Snakes: Active Contour Models", International Journal of Computer Vision, Vol. 1, No. 4, p. 321-331, 1988に記載されるSnakesと呼ばれる動的輪郭モデルは、輪郭の形状に応じて与えられるエネルギ（内部エネルギ）、画像の性質に応じて与えられるエネルギ（画像エネルギ）、および、外部から与えられるエネルギ（外部エネルギ）の総和が最小になるように輪郭を収縮、変形することにより、関心領域の輪郭線を抽出する。内部エネルギは輪郭線の形状が滑らかなほど小さな値を、画像エネルギは輪郭線上の画像のエッジ強度が高いほど小さな値を、外部エネルギは輪郭線が外部から与えられた点に近いほど小さな値をそれぞれ取るように定義される。
【０００７】
【発明が解決しようとする課題】
上記の技術にはそれぞれ以下のような問題がある。
【０００８】
(1)特許第2500439号：輪郭線の解像度が低い
輪郭近傍でブロックサイズを小さくして解像度を上げても、所詮、ブロック単位の解像度に過ぎず、画素単位の輪郭データを正確に求めることはできない。また、ブロックを再分割したか否かを判別するための付加情報がブロックごとに発生してしまい、圧縮率を低下させる原因になる。
【０００９】
(2)特許第2616552号：輪郭検出の精度が低い
四種類の輪郭検出方法が説明されているが、それぞれ次の問題がある。
【００１０】
前フレームと現フレームとの差分データから輪郭を抽出する方法は、差分量が大きい領域は抽出できても、差分量が大きい領域内から輪郭線を検出するには、細線化など、何らかの後処理が必要になる。
【００１１】
前フレームの輪郭データと現フレームの輪郭データとの差分から輪郭を抽出する方法は、上記の方法と同様に、差分量が大きい領域は抽出できても、差分量が大きい領域内から輪郭線を検出するには、細線化など、何らかの後処理が必要になる。
【００１２】
登録された背景画像との差分から輪郭を抽出する方法は、背景が固定されていて、汎用性がない。
【００１３】
予め動きベクトルを検出し、その分布が急激に変化する場所から輪郭を抽出する方法は、動きベクトルを検出するブロック単位の解像度でしか輪郭線が求まらない。
【００１４】
(3)特開平8-335268号：画素単位の解像度が得られない
輪郭データの部分部分をスプライン関数で表現するので、画素単位の正確さで被写体の輪郭を抽出することはできない。
【００１５】
(4)動的輪郭モデルに基づく手法
第一に汎用性に乏しい。輪郭モデルの挙動を決定するパラメータ、すなわち、内部エネルギ、画像エネルギおよび外部エネルギの各項の重み係数を、入力画像ごとに経験的に設定しなければならず、汎用性に欠ける。
【００１６】
第二に輪郭の初期設定に敏感である。正確な初期位置を与えなければならず、輪郭の初期設定の精度が低いと、上記のエネルギ分布の極小値に陥り易く、なかなか正しい輪郭に収束しない。
【００１７】
第三に計算量が多く高速処理が困難である。輪郭上の一つの節点の移動方向を決定するためには、その節点が動き得るすべての方向にある近傍点について、上記のエネルギを求め、かつ、その演算を輪郭線上のすべての節点で行わなければならないので、処理の高速化が難しい。
【００１８】
第四に輪郭近傍の偽エッジやノイズの影響を受け易い。エッジ強度の高い画素を選択するように画像エネルギが定義されるので、真の輪郭線上のエッジ強度より輪郭線近傍の偽エッジやノイズの強度が高いと、これを誤選択してしまう。
【００１９】
本発明は、上述の問題を解決するためのものであり、動画像または多視点画像など複数の画像に跨がる関心領域を高速、高精度に抽出することを目的とする。
【００２０】
【課題を解決するための手段】
本発明は、前記の目的を達成する一手段として、以下の構成を備える。
【００２１】
本発明にかかる画像処理装置は、第一の画像における関心領域の輪郭情報に基づき、前記関心領域の輪郭線の上または近傍から少なくとも三点の特徴点を選出する選出手段と、前記選出手段が選出した、前記第一の画像における特徴点間の連結関係を記憶する記憶手段と、前記選出手段が選出した、前記第一の画像における特徴点それぞれに対応する、前記第一の画像と異なる時刻または異なる視点で撮像された第二の画像の対応点を探索する探索手段と、前記記憶手段に記憶された連結関係に基づき、前記探索手段が検出した対応点のうち前記連結関係にある二点の一方をトレースの始点、他方を前記トレースの終点として、前記二点間においてエッジ強度が大きい画素を順次トレースし、前記第一の画像における関心領域に対応する前記第二の画像における関心領域の輪郭線を抽出する抽出手段とを有し、前記抽出手段は、前記トレースにおける注目点の画素に隣接する近傍画素について前記エッジ強度を比較する際に、前記注目点と前記終点の位置関係に応じて決まる前記トレースの進行方向、前記進行方向に直交する方向、および、前記進行方向と前記直交する方向に挟まれた方向への進行を許可するマスキングを前記近傍画素に施して、前記トレースの進行方向を制限することを特徴とする。
【００２３】
本発明にかかる画像処理方法は、第一の画像における関心領域の輪郭情報に基づき、前記関心領域の輪郭線の上または近傍から少なくとも三点の特徴点を選出する選出ステップと、前記選出ステップで選出した、第一の画像における特徴点間の連結関係をメモリに格納する格納ステップと、前記選出ステップで選出した、前記第一の画像における特徴点それぞれに対応する、前記第一の画像と異なる時刻または異なる視点で撮像された第二の画像の対応点を探索する探索ステップと、前記メモリに格納された連結関係に基づき、前記探索ステップで検出した対応点のうち前記連結関係にある二点の一方をトレースの始点、他方を前記トレースの終点として、前記二点間においてエッジ強度が大きい画素を順次トレースし、前記第一の画像における関心領域に対応する前記第二の画像における関心領域の輪郭線を抽出する抽出ステップとを有し、前記抽出ステップにおいて、前記トレースにおける注目点の画素に隣接する近傍画素について前記エッジ強度を比較する際に、前記注目点と前記終点の位置関係に応じて決まる前記トレースの進行方向、前記進行方向に直交する方向、および、前記進行方向と前記直交する方向に挟まれた方向への進行を許可するマスキングを前記近傍画素に施して、前記トレースの進行方向を制限することを特徴とする。
【００２４】
【発明の実施の形態】
以下、本発明にかかる一実施形態の画像処理装置を図面を参照して詳細に説明する。
【００２５】
なお、以下で説明する輪郭抽出により抽出された関心領域の画像データは、例えば、周波数領域のデータに変換された後、他の領域と異なる量子化方法または量子化テーブルにより量子化され、可変長符号化されるなどの画像処理が施される。
【００２６】
【第１実施形態】
［構成］
図1は第1実施形態の機能構成例を示すブロック図である。
【００２７】
図1において、10は入力画像内の関心領域の輪郭を抽出する輪郭抽出部、20は抽出された輪郭上、または、その近傍に存在する複数の特徴点を選出する特徴点選出部、25は選出された特徴点同士の連結関係を記憶する特徴点連結関係記憶部、30は複数の特徴点の各対応点を、他の時刻または他の視点から撮像して得られた画像中で探索する対応点探索部、40は入力画像を記憶する画像メモリ、50は新たに求まった複数の特徴点のアドレスを一定時間保持するディレイ回路である。
【００２８】
なお、本発明は、図1に示す構成をもつ装置だけでなく、汎用のパーソナルコンピュータやワークステーション上で次のステップを有するプログラムコードを実行することで実現可能である。つまり、少なくとも、画像の関心領域の輪郭を抽出する輪郭抽出ステップ、抽出された輪郭線上の特徴点を選出する特徴点選出ステップ、特徴点の連結関係をメモリに記憶させるステップ、特徴点の対応点を他の画像内で探索する対応点探索ステップ、および、対応点を輪郭抽出ステップに供給するステップを備え、複数枚の画像に跨がる関心領域を順次抽出するプログラムコードである。
【００２９】
以下、図1の各機能構成を動作順に説明する。
【００３０】
まず、輪郭抽出部10に、基準になる画像における関心領域の初期輪郭情報が与えられる。動画や連写画像などの時系列画像が入力される場合は、オペレータが初期画像内における関心領域の輪郭線上の要所要所を指示してもよいし、時間的に連続する二枚の画像間の差分データを用いることもできる。なお、関心領域の初期輪郭情報を獲得する方法は、限定されるものではなく、本発明の主旨に反しない範囲であれば、いかなる方法でもよい。
【００３１】
輪郭線上の要所要所が特徴点あるいは制御点として与えられた際の特徴点間の輪郭抽出方法は後述する。なお、本実施形態では、入力画像として時系列画像を説明するが、多視点画像であっても構わない。
【００３２】
特徴点選出部20は、輪郭線上またはその近傍領域で輪郭線の特徴をよく表す点を選出する。図2は代表点の選出方法を説明するフローチャートである。
【００３３】
輪郭線を表す閉曲線のアドレスデータが入力されると、図2に示すステップS1で、その閉曲線の形状を解析する。ディジタル画像中の直線、曲線、閉曲線などの線を表現する方法としてフリーマンのチェーンコードが知られている。その原理を、図3および図4を参照して説明する。図3はディジタル画像上のハート型の閉曲線を表し、その閉曲線内部が画像の関心領域である。図4は八方向の量子化コードを示し、輪郭線上で隣接する画素同士の位置関係を数値化するためのものである。図3に示す点Aを始点として、時計回りに図中の閉曲線を記述すると、00066000201006…になる。
【００３４】
次に、ステップS2で、フリーマンのチェーンコードから輪郭線の向きが急峻に変化する点を選出する。例えば、コードが0から6、6から0、0から2、2から0などに変化する点は、輪郭線の軌跡が90度折れ曲がっていることを示し、容易に輪郭線のコーナを検出することができる。ただし、輪郭線の軌跡が90度折れ曲がっている点は輪郭上には多数存在し得る。例えば、斜め45度方向の直線は、64646464…のように細かい周期で90度の屈曲を繰り返す。そこで、所定以下の周期で繰り返す屈曲部からは特徴点を選出しないようにする。
【００３５】
特徴点の数を適切な数に保つには、このほか、フリーマンのチェーンコードに間引き処理を施したり、画像自体の解像度を低くするなどの処理が有効である。図5は図3に示したディジタル画像の解像度を水平、垂直両方向ともに1/2に低下させた様子を示している。原画像の四画素を一画素とする粗い画素単位で、図5に示す点A'を始点として、時計回りにフリーマンのチェーンコードを作成し、輪郭線の軌跡が大きく向きを変える点を抽出する。低解像度化により、大局的に特徴的な点は残り、不必要に細かい屈曲点は除去される。
【００３６】
また、屈曲の角度が90度未満の鋭角コーナおよび135度以上の鈍角コーナはもらさず特徴点とする。また、閉曲線が生成されるように最低三点の特徴点を選定する。
【００３７】
特徴点連結関係記憶部25は、前記特徴点選出部20により選出された特徴点同士の連結関係を記憶する。図6は、図5に示す閉曲線上から選出された九個の特徴点を示す図で、特徴点はハッチングで示されている。各特徴点はフリーマンのチェーンコードを作成した順に、すなわち、A'点を始点として時計回りに、No.1からNo.9までラベリングされている。ラベリング番号が連番の特徴点、または、最初(No.1)と最後(No.9)の特徴点は、輪郭追跡するためのペアであることを意味する。各特徴点に割り当てられたラベリング番号は、後段の対応点探索部30において、現フレームの特徴点の対応点を次フレーム内で探索した時に、そのまま引き継がれる。
【００３８】
次に、図2に示すステップS3におけるラベリングの更新方法を、図7および図8を用いて、前後する輪郭抽出部10、対応点探索部30などと関連付けながら説明する。
【００３９】
図7(a)はある時刻における関心領域の輪郭線である。特徴点としては、図示された三点A、BおよびCが選出されている。この輪郭線のデータは、図8(a)に示すように、ある特徴点を先頭とした一次元の配列に格納される。そして、選出された特徴点A、BおよびCは、その配列順に従い、No.1、No.2およびNo.3とラベリングされる。
【００４０】
図7(b)は一定時間後の関心領域の輪郭線で、形状が変化している様子が示されている。特徴点A、BおよびCそれぞれの対応点は、後述する対応点探索部30によりA'、B'およびC'と求められる。輪郭抽出部10は、その対応点A'、B'およびC'を通過点として、関心領域の一定時間後の輪郭線を抽出する。輪郭抽出直後の輪郭線データは、図8(b)に示すように、一定時間前の先頭の特徴点Aをそのまま先頭とした一次元配列である。ここで、特徴点選出部20の働きにより、図8(b)に示す輪郭データから新たな特徴点D、EおよびFが選出される。図8(c)は、先頭の特徴点Dが先頭になるようにアドレスをシフトして表示したものである。新たな特徴点D, EおよびFは、その配列順に従い、新たにNo.1、No.2およびNo.3とラベリングされ特徴点連結関係記憶部25に記憶される。また、新たな特徴点D、EおよびFは、対応点探索部30による次の対応点探索のための新しい基準画素になる。
【００４１】
以上説明したように、図2に示すステップS3では、被写体の形状変化に応じて、特徴点の更新、消去および追加の作業（ラベリングの更新）が自動的に行われる。
【００４２】
対応点探索部30は、特徴点抽出部20により抽出された複数の特徴点に対応する各対応点を次フレーム内で探索する。特徴点の対応付けは、各特徴点とその近傍画素からなるブロックを用いたブロックマッチングで高速に行うことができる。しかし、その対応付け方法は、ブロックマッチングに限られるものではなく、本発明の主旨を逸脱しない範囲であれば、いかなる方法でもよい。
【００４３】
画像メモリ40は、例えばフレームメモリのような画像データを一時記憶する記憶装置で、輪郭抽出部10における輪郭抽出動作は、画像メモリ40に蓄積された画像データを読み出しながら行われる。また、ディレイ回路50は、対応点探索部30において抽出された最新画像における特徴点のアドレスデータを一時記憶し、輪郭抽出部10が画像メモリ40から読み込む画像データに同期させるためのものである。
【００４４】
［輪郭抽出部］
次に、輪郭抽出部10の内部処理を詳細に説明する。図9は輪郭抽出部10の内部構成例を示すブロック図である。
【００４５】
エッジ抽出部90は、画像メモリ40から供給される画像からエッジ成分を抽出する。エッジトレース部100は、連結関係にある二点の特徴点のうち、一方の特徴点を始点、もう一方の特徴点を終点として、エッジ強度の大きい画素を順次追跡する。このエッジトレースの過程で、フリーマンのチェーンコードが自動的に生成され、後段の特徴点選出部20へエッジトレースの結果とともに供給される。
【００４６】
エッジ抽出部90におけるエッジ抽出方法は、SobelオペレータやLaplacianオペレータなどに代表される空間微分処理で行ってもよいし、PrewittオペレータやKirschオペレータなどのようなテンプレートマッチングで行ってもよい。つまり、エッジ抽出の目的が達成できれば、いかなる手法でもよい。なお、エッジ抽出の演算量を減らすために、エッジ抽出処理を輪郭抽出区間と、後述する目隠しマスクで決定される輪郭追跡可能範囲に限定することができる。さらに、エッジ抽出部90をエッジトレース部100内に組み込み、エッジ強度を比較する近傍画素のアドレスが決定した瞬間に、その近傍画素に対してのみエッジ抽出を行ってもよい。
【００４７】
図10はエッジトレース部100の内部処理を最もよく表すフローチャートである。
【００４８】
抽出したい輪郭区間を設定し(S110)、設定された輪郭区間の始点を注目点の初期位置として、また、終点を輪郭追跡の目標点として、両端点（始点および終点）をセットする(S120)。次に、注目点と目標点との位置関係を算出し(S130)、注目点の近傍画素に視野制限を加える目隠しマスクを作成し(S140)、注目点の近傍画素からエッジ強度最大の画素を探索し(S150)、探索された輪郭画素を新しい注目点としてセットする(S160)。そして、ステップS170で、新しい注目点が目標点と一致するか否かを判断する。
【００４９】
輪郭線データは、注目点のアドレス（座標値）を記録することにより構築され、フリーマンのチェーンコードは注目点の移動方向を逐次記録することにより生成される。
【００５０】
次に、図10に示す各ステップの処理を詳細に説明する。
【００５１】
ステップS110における輪郭抽出区間の設定は、輪郭追跡を行う初期画面において、オペレータがマウスのようなポインティングデバイスを用いて抽出したい輪郭区間を挟む両端点を指定することで実現される。具体的には、オペレータが画面上のマウスカーソルを移動して、抽出したい輪郭区間の端点近傍にマウスカーソルを置き、マウスボタンを押せばよい。初期画面以降は、対応点探索部30から供給される連結関係にある特徴点の組により輪郭抽出区間が設定される。
【００５２】
初期画面のステップS120では、マウスボタンが押された瞬間、マウスカーソルが指示する位置を中心に一定距離内にある画素の中で、最もエッジ強度の強い画素が探索される。同様に、初期画面以降のステップS120では、対応点探索部30から供給される連結関係にある特徴点を中心に一定距離内にある画素の中で、最もエッジ強度の強い画素が探索される。探索された画素の位置は端点と定められ、最初に指定された点が始点、次に指定された点が終点にセットされる。なお、始点は注目点の初期位置であり、終点は輪郭追跡における目標点である。
【００５３】
ステップ130では、注目点と目標点との位置関係を算出する。具体的には、目標点を基準として、注目点と目標点とがなす角を求める。注目点の座標を(x0,y0)、目標点の座標を(x1,y1)とすると、二点のなす角θは(1)式で表される。
θ = tan-1{(y0 - y1)/(x0 - x1)}  …(1)
(1)式で算出される角θは、図11に示すように、45度刻みの八方向、すなわち、方向1（-22.5から+22.5度）、方向2（22.5から67.5度）、方向3（67.5から112.5度）、方向4（112.5から157.5度）、方向5（157.5から180度、かつ、-180から-157.5度）、方向6（-157.5から-112.5度）、方向7（-112.5から-67.5度）および方向8（-67.5から-22.5度）の何れかに分類される。なお、(1)式の演算はルックアップテーブルを用いて高速に実行することができる。
【００５４】
ステップS140では、上記の八方向に応じた、図12に示される目隠しマスクにより、輪郭線を追跡中の注目点を中心とする近傍八画素がマスキングされる。図12において、注目点の位置は×印で示され、「1」は移動可能な画素を示し、「0」は移動禁止の画素、つまりマスキングされた画素を示す。この目隠しマスクは、進行可能な画素が五画素、進行禁止の画素が三画素であり、かなり自由な輪郭線追跡を許容しつつ、確実に目標点へ収束するような制約を与える。
【００５５】
ステップS150では、ステップS140でマスキングされなかった近傍画素中で、最大のエッジ強度をもつ画素が探索される。ステップS160では、ステップS150で探索された画素である次の注目点へ一画素移動する。
【００５６】
図13は本実施形態による輪郭追跡の移動可能な範囲を示す図である。
【００５７】
輪郭の追跡可能範囲は、目標点Bに対して後退する方向を除き、自由な追跡を許容する。注目点Cが始点Aにある瞬間、すなわち、輪郭追跡の開始時は最大で八角形aの範囲を移動できる。しかし、注目点Cが終点（目標点）Bに到達するまで、その八角形aの範囲内で注目点Cを自由に移動できるわけではなく、注目点Cが例えば八角形bの輪郭に達した後、移動できる領域は八角形bの範囲内に限定される。このように、目標点Bに近付くほど、移動可能範囲の八角形が漸次縮小し、確実に目標点Bに到達するように動作する。
【００５８】
ステップS170では、注目点Cが終点Bに達したか否かが判定される。終点Bに達していない場合は、ステップS130に戻り、新しい注目点Cに対してステップS130からS160の処理が繰り返され、ステップS170で注目点Cが終点Bに達したと判定されると輪郭抽出処理が終了する。
【００５９】
本実施形態では、前記の目隠しマスクのほかに、補助的に後退を防止するマスクを設けている。
【００６０】
図14は、輪郭線A-Bとその区間を追跡中の注目点Cを表す図である。注目点Cが図14に示された位置に到達した時、目標点である終点Bとの位置関係が157.5から180度、かつ、-180から-157.5度の方向5に属するため、前述したように、方向5の目隠しマスクによりbおよびh（上下）方向、f（右）方向、c（右上）方向、並びに、i（左下）方向への進行が許される。図14の例では、エッジが注目点Cの上の画素bおよび下の画素hに存在するので、進路は上下二方向に限られる。この時、画素hのエッジ強度が画素bのエッジ強度よりも高いと「エッジ強度の大きい画素を順次追跡する」というルールおよび目隠しマスクだけでは、輪郭追跡が前進できなくなる。
【００６１】
上記の問題に対応するために、本実施形態においては、輪郭追跡の進行方向を制限する目隠しマスクのほかに、輪郭追跡が過去の輪郭追跡経路に戻らないように、つまり後退しないように注目点Cに対して後退防止の視野制限を補助的に加える。すなわち、注目点Cが図14に示す位置に到達した瞬間、注目点Cは画素hから画素eへ移動してきたわけであるから、進行方向に対して後方にあたる画素g、hおよびiへ進まないように視野制限する。
【００６２】
なお、上記では、近傍画素を注目点Cに隣接する八画素と説明したが、細部の輪郭追跡が必要ない場合や、より滑らかに輪郭を抽出したい場合などは、注目点Cから二画素以上離れた近傍画素を用いて同様に処理することも可能である。
【００６３】
このように、第1実施形態によれば、次の効果を得ることができる。
(1)輪郭抽出処理は局部的なエッジ強度の比較になり、特徴点の対応点探索は局部的な類似点の探索になるので、処理速度が速く、複数の画像から共通する関心領域を高速に抽出することができる。
(2)輪郭抽出処理において、注目点が移動する度に視野を制限する目隠しマスクが適宜設定されるので、自由度の高い輪郭追跡経路を確保しつつ、確実に終点（目標点）へ到達することができ、信頼性が高い。
(3)輪郭抽出処理における輪郭追跡の拘束条件が「目標点に対して後退しない」だけであるから、トレース経路の自由度が極めて高く、曲率変化の緩やかな輪郭線においては目標点に背後から到達するような大回りの輪郭も追跡可能である。その結果、輪郭抽出の始点および終点の間を広く設定することができ、特徴点の数が少なくて済み、対応点を探索する処理がより高速化される。
(4)新たに抽出される輪郭線の形状に基づき、毎回、新しい特徴点を選出するので、形状変化を伴う関心領域を抽出することができる。
【００６４】
【第２実施形態】
以下、本発明にかかる第2実施形態の画像処理装置を説明する。なお、本実施形態において、第1実施形態と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００６５】
図15は第2実施形態の輪郭抽出部10の詳細な構成例を示すブロック図で、図9に示した第1実施形態の輪郭抽出部10の構成に、エッジトレース部100に異なる輪郭抽出特性を与える輪郭抽出特性選択部200が追加されている。
【００６６】
第1実施形態では、輪郭追跡の拘束条件を極力緩くし、追跡経路の自由度を最大限に確保した。従って、輪郭線のエッジ強度がその近傍のエッジやノイズの強度よりも相対的に大きい場合、第1実施形態の輪郭追跡は極めて効果的である。しかし、輪郭線近傍のエッジやノイズの強度が、輪郭線のエッジ強度よりも大きい場合は、視野が広い分、トレースを誤る可能性が高くなる。
【００６７】
第2実施形態では、図12に示した目隠しマスク、および、図16に示す目隠しマスクの両方をもたせ、何れかのマスクを選択的に使用する。図12に示す目隠しマスクは、五方向の追跡が許容されるが、図16に示す目隠しマスクの追跡可能な方向は三方向に絞られている。これは、輪郭追跡に対して「目標点に対して常に近付く」という拘束条件を与えたことに等しい。従って、図16に示す目隠しマスクによれば、図12に示す目隠しマスクによる処理に比べて、輪郭追跡の経路の自由度が小さくなる分、輪郭近くにある輪郭以外のエッジを誤検出する可能性が小さくなり、安定性が高い。
【００６８】
図17は図16に示す目隠しマスクを使用した時の輪郭追跡可能範囲を示す図である。図17に示す範囲aは注目点Cが始点Aにある時の、範囲bは注目点Cが範囲bの輪郭上にある時の追跡可能範囲を示す。このように、注目点Cが目標点Bに近付くほど、逐次追跡可能範囲が縮小し、最後は、確実に目標点Bに到達する。
【００６９】
輪郭抽出特性選択部200は、輪郭抽出部10により得られるエッジ画像の、連結関係にある特徴点に挟まれた部分領域におけるエッジの強度、コントラストおよび分散などに応じて、輪郭抽出特性を選択する。また、異なる輪郭抽出特性で、つまり異なる目隠しマスクを用いたエッジトレースを並行して行わせ、抽出された輪郭線の滑らかさ、エッジ強度およびコントラストなどをから、所望の輪郭追跡結果を選択することもできる。
【００７０】
このように、第2実施形態によれば、第1実施形態の効果に加えて、次の効果を得ることができる。
(5)より視野制限の厳しい目隠しマスクを設けることにより、輪郭線の近くにある、輪郭線以外の強いエッジやノイズに惑わされ難くなり、エッジ強度の低い輪郭線、ノイジィな画像の輪郭線などを安定に追跡することができる。
(6)輪郭以外のエッジが強い時は図16に示す目隠しマスクを、輪郭線のエッジが強い時は図12に示す目隠しマスクを選択的に使用して、輪郭抽出特性を適応的に変化させることができるので、輪郭抽出の適用範囲を拡げることができる。
【００７１】
【第３実施形態】
上述した第1および第2実施形態では、注目点の近傍画素へ二値のマスキングを行ったが、第3実施形態では二値のマスキングだけではなく、多値の重み付けを行って輪郭抽出特性をより滑らかに変更する。
【００７２】
図18は多値の重み付けを行った方向5の目隠しマスクの一例を示す図である。勿論、図18に示す重み付け係数は一例であり、より細かく変化させることも可能である。図18(a)および(c)に示す目隠しマスクはそれぞれ、図12および図16に示す目隠しマスクと同等である。また、図18(b)に示す目隠しマスクは図12と図16に示すものの中間的な拘束条件を有し、図18(d)に示す目隠しマスクは図16に示すものより厳しい拘束条件を有する。
【００７３】
従って、注目点の近傍画素における各エッジ強度の大きさに明確な差がない場合、すなわち、エッジが途切れている個所やコントラストが低い個所では図18(a)や(b)に示す重み付けされた目隠しマスクを選択的に使用することで、目標点へ向かう方向をより優先させた輪郭追跡を継続することができる。また、逆の特性をもつ個所では図18(c)や(d)に示す重み付けされた目隠しマスクを選択的に使用すればよい。
【００７４】
このように、第3実施形態によれば、第1および第2実施形態の効果に加えて、次の効果を得ることができる。
(7)エッジが明確でない個所においても目標点に向かうように輪郭追跡を継続することができる。
(8)異なる重み付け係数を有する目隠しマスクを複数備え、輪郭周辺の画像の状態に応じて自由に選択することができるので、あらゆる画像輪郭に対して適用可能になる。
【００７５】
【第４実施形態】
上述した第1から第3実施形態では、始点から終点へ向かう一方向の輪郭追跡を説明した。しかし、一方向の輪郭追跡を行うとエッジの分岐路で誤った方向へ進む可能性がある。そこで、第4実施形態では、始点と終点を入れ替えて、逆向きの輪郭追跡も行う。この双方向トレースの効果を図19および図20を用いて説明する。
【００７６】
図19および図20には、真の輪郭線と、その輪郭線に重なるようにして存在する背景のエッジとが示されている。ここでは、背景エッジの方がエッジ強度が大きいとする。図19では、始点Aは図の下側に、終点Bは図の上側にあり、輪郭は図の下側から上側へ追跡される。図19に示す方向（以下「正方向」と呼ぶ）で輪郭線を追跡すると、トレースは、よりエッジ強度が強い背景エッジの方向へ進み、目隠しマスクの働きにより途中で背景エッジから離れ、図19に示すように終点Bへ向かう。つまり、図19は典型的なエッジトレースの失敗例を示している。
【００７７】
一方、図20では、始点Aと終点Bの組み合わせを図19とは逆にしたので、輪郭追跡は図の上側から下側へ図19とは逆方向に進む。従って、図19ではエッジの分岐点であった点が、図20ではエッジの合流点に変化する。勿論、目隠しマスクにより目標点Bから遠ざかる方向へトレースすることはできないので、トレースは、合流点で背景エッジの方向へ折り返すことはなく、より強い背景エッジが存在するにもかかわらず、正しい輪郭を抽出することができる。
【００７８】
図21は第4実施形態の処理を示すフローチャートである。
【００７９】
ステップS300で図10に示す輪郭追跡を行い、ステップS301でその信頼性を評価する。この評価は、輪郭線の滑らかさ、輪郭線上のエッジ強度の平均値、または、輪郭線の長さ（パスレングス）などを単独に用いて行うか、あるいは、これらを重み付き加重するなどして総合的に行う。次に、ステップS302で始点と終点を入れ替え、ステップS303で再び図10に示す輪郭追跡を行い、ステップS304でその信頼性を評価する。そして、ステップS305で両方向の輪郭追跡結果の評価結果を比較して、より信頼性の高い輪郭追跡結果を出力する。
【００８０】
このように、第4実施形態によれば、第1から第3実施形態の効果に加えて、次の効果を得ることができる。
(9)双方向の輪郭追跡を行い、より輪郭らしい追跡結果を選択することで、輪郭線と交わる「輪郭以外のエッジ」の影響を受け難い極めて安定した輪郭追跡が実現される。
(10)第4実施形態では、エッジの分岐点に着目して双方向の輪郭追跡の有効性を説明した。勿論「エッジの分岐点」は逆にみれば「エッジの合流点」であるから、「目標点に向かって進む」や「過去の進行方向に逆行しない」などの拘束条件を実現するマスク処理と組み合わせることで「輪郭以外のエッジ」の影響を受け難い極めて安定した輪郭追跡が実現される。しかし、第4実施形態の双方向の輪郭追跡においてマスク処理は必須ではない。抽出したい輪郭部の両端点近傍に鮮明なエッジがない場合など、両端点近傍の輪郭追跡経路が復路と往路とで異なり、その結果、両方向の輪郭追跡結果が全く異なる経路になることがある。このような場合でも、双方向の輪郭追跡結果の何れか一方は、真の輪郭線を抽出するので、一方向の輪郭追跡と比べて確実に有利である。
【００８１】
【第５実施形態】
第1実施形態では、輪郭線上の特徴点選出方法として、輪郭線の形状情報であるフリーマンのチェーンコードを利用した。第5実施形態では、輪郭線の形状情報のほかに、輪郭線の上または近傍の画像情報を利用する。具体的な画像情報として輪郭線を構成する各画素がもつエッジの強度を参照する。つまり、輪郭線の形状情報に基づき輪郭線上の特徴点の候補を選出し、特徴点のエッジ強度により優先付けを行う。エッジ強度の高い特徴点ほど、次フレームでの対応点探索がより高精度に行えるので、優先度を上げる。優先付け結果を用いて、関心領域を抽出するシステムの処理能力に応じて定まる特徴点数の上限個だけ、特徴点を選抜する。
【００８２】
また、第5実施形態は、第1実施形態において説明した、低解像度化された画像から抽出された特徴点に対応する高解像度の原画像の画素を決定する場合にも有用である。つまり、低解像度画像において特徴点として選択された「原画像の四画素からなる粗い一画素領域」から最も信頼性の高い原画像の一画素を選択する場合は、原画像の四画素それぞれのエッジ強度を比較すればよく、最もエッジ強度の高い画素が自動的に選択される。
【００８３】
第5実施形態の特徴点選出方法によれば、次の特有の効果が得られる。
(11)多くの特徴点候補から予め定められた個数の特徴点を選抜する際の指針を与えることができる。
(12)多くの特徴点候補から信頼性の高い特徴点を選抜することができる。
(13)低解像度画像の特徴点から対応する高解像度画像の特徴点を求めることができる。
【００８４】
【第６実施形態】
第1実施形態では、輪郭線の形状情報であるフリーマンのチェーンコードを利用して輪郭線上の特徴点を選出する方法を説明し、第5実施形態では、輪郭線の形状情報のほかに、輪郭線の上または近傍の画像情報を利用する例を説明した。第6実施形態では、第4実施形態を利用して、双方向のトレース結果から特徴点を選出する方法を説明する。
【００８５】
第4実施形態の原理を図19および図20を参照して説明する。図19に示す正方向のトレースにおいては、輪郭線に交わる背景エッジの分岐点で、よりエッジ強度の高い背景エッジのトレースが開始される。しかし、分岐点までのトレースは正しい。一方、図20に示す逆方向のトレースにおいては、分岐点は真の輪郭線と背景エッジとの合流点であるから、分岐点は輪郭追跡に対し何ら悪影響を与えない。正方向および逆方向のトレース結果を比較すると、図19の始点Aと分岐点との間のトレース結果は一致し、分岐点と図19の終点Bとの間のトレース結果は一致しない。第6実施形態は、双方向のトレースを行いトレース結果が一致する区間の端点を特徴点とする。
【００８６】
つまり、図19に示す分岐点を特徴点にすれば、トレースの脱線を引き起こす分岐点をなくすことができ、信頼性の高い特徴点を選出することができる。勿論、第6実施形態を、第1または第5実施形態と組み合わせれば、さらに、特徴点の信頼性を向上させることができる。
【００８７】
第6実施形態によれば、次の特有の効果が得られる。
(14)輪郭線の形状やエッジ強度だけでは選出できない特徴点を漏れなく選出することができる。とくに、背景や関心領城内部に強いエッジが存在する場合に有効である。
【００８８】
【第７実施形態】
第1実施形態の対応点探索部30は、各特徴点およびその近傍画素からなるブロックを用いるブロックマッチングを単独に行う。一方、動きベクトルを検出するLSIが開発され、画像内の綿密な動きベクトルをリアルタイムに検出することができる。このような動きベクトル検出用のLSIを併用すれば、現時点で選出された特徴点により次フレームにおける探索範囲を限定することができ、次の特有な効果を得ることができる。
(15)特徴点近傍の動きベクトルの分布から、次フレームにおける対応点探索の範囲をおおよそ限定することができ、対応点探索の無駄を省き、処理効率が向上するとともに、特徴点の誤対応を減らすことができる。
【００８９】
【発明の効果】
以上説明したように、本発明によれば、動画像または多視点画像など複数の画像にまたがる関心領域を高速、高精度に抽出することができる。
【図面の簡単な説明】
【図１】第1実施形態の機能構成例を示すブロック図、
【図２】代表点の選出方法を説明するフローチャート、
【図３】ディジタル画像中の線を表現するフリーマンのチェーンコードの原理を説明する図、
【図４】ディジタル画像中の線を表現するフリーマンのチェーンコードの原理を説明する図、
【図５】図3に示すディジタル画像の解像度を水平、垂直両方向ともに1/2に低下させた様子を示す図、
【図６】図5に示す閉曲線上から選出された九個の特徴点を示す図、
【図７】図2に示すラベリングの更新方法を説明する図、
【図８】図2に示すラベリングの更新方法を説明する図、
【図９】輪郭抽出部の内部構成例を示すブロック図、
【図１０】図9に示すエッジトレース部の内部処理を最もよく表すフローチャート、
【図１１】注目点と目標点とがなす角の分類を示す図、
【図１２】目隠しマスクの例を示す図、
【図１３】輪郭追跡の移動可能な範囲を示す図、
【図１４】輪郭線とその区間を追跡中の注目点を表す図、
【図１５】第2実施形態の輪郭抽出部の詳細な構成例を示すブロック図、
【図１６】目隠しマスクの他の例を示す図、
【図１７】図16に示す目隠しマスクを使用した時の輪郭追跡可能範囲を示す図、
【図１８】多値の重み付けを行った目隠しマスクの一例を示す図、
【図１９】双方向トレースの効果を説明する図、
【図２０】双方向トレースの効果を説明する図、
【図２１】第4実施形態の処理を示すフローチャートである。
【図１】
0004612760.tif 000002
【図２】
0004612760.tif 000003
【図３】
0004612760.tif 000004
【図４】
0004612760.tif 000005
【図５】
0004612760.tif 000006
【図６】
0004612760.tif 000007
【図７】
0004612760.tif 000008
【図８】
0004612760.tif 000009
【図９】
0004612760.tif 000010
【図１０】
0004612760.tif 000011
【図１１】
0004612760.tif 000012
【図１２】
0004612760.tif 000013
【図１３】
0004612760.tif 000014
【図１４】
0004612760.tif 000015
【図１５】
0004612760.tif 000016
【図１６】
0004612760.tif 000017
【図１７】
0004612760.tif 000018
【図１８】
0004612760.tif 000019
【図１９】
0004612760.tif 000020
【図２０】
0004612760.tif 000021
【図２１】
0004612760.tif 000022