(57)【要約】【課題】一定の精度を確保しつつ、簡単な演算処理で特徴点を検出したい。【解決手段】二次微分値算出部１０は、画像内の注目画素における、右下がり斜め方向の二次微分値および右上がり斜め方向の二次微分値を算出する。評価値算出部２０は、二次微分値算出部１０により算出された、右下がり斜め方向の二次微分値と右上がり斜め方向の二次微分値との絶対値差を第１評価値として算出する。判定部３０は、評価値算出部２０により算出された第１評価値と、第１閾値とを比較することにより、注目画素が画像内の、コーナーまたは斜めエッジに該当するか否か判定する。【選択図】図１
2010039520.tif 000002
【特許請求の範囲】
【請求項１】
画像内の注目画素における、右下がり斜め方向の二次微分値および右上がり斜め方向の二次微分値を算出する二次微分値算出部と、
前記二次微分値算出部により算出された、前記右下がり斜め方向の二次微分値と前記右上がり斜め方向の二次微分値との絶対値差を第１評価値として算出する評価値算出部と、
前記評価値算出部により算出された前記第１評価値と、第１閾値とを比較することにより、前記注目画素が前記画像内の、コーナーまたは斜めエッジに該当するか否か判定する判定部と、
を備えることを特徴とする特徴点検出装置。
【請求項２】
前記二次微分値算出部は、前記注目画素における、水平方向の二次微分値および垂直方向の二次微分値を算出し、
前記評価値算出部は、前記二次微分値算出部により算出された、前記水平方向の二次微分値と前記垂直方向の二次微分値との絶対値差を第２評価値として算出し、
前記判定部は、前記評価値算出部により算出された前記第２評価値と、第２閾値とを比較することにより、前記注目画素が前記画像内の、水平エッジまたは垂直エッジに該当するか否か判定することを特徴とする請求項１に記載の特徴点検出装置。
【請求項３】
前記評価値算出部は、前記注目画素における、前記右下がり斜め方向の二次微分値の絶対値と、前記右上がり斜め方向の二次微分値の絶対値との和を第３評価値として算出し、前記水平方向の二次微分値の絶対値と、前記垂直方向の二次微分値の絶対値との和を第４評価値として算出し、
前記判定部は、前記第３評価値と第３閾値とを比較することにより、前記コーナーまたは前記斜めエッジの強度を判定し、前記第４評価値と第４閾値とを比較することにより、前記水平エッジまたは前記垂直エッジの強度を判定することを特徴とする請求項２に記載の特徴点検出装置。
【請求項４】
画像を複数の部分領域に分割する分割部と、
前記分割部により分割された各部分領域の各画素ごとに、右下がり斜め方向の二次微分値、右上がり斜め方向の二次微分値、水平方向の二次微分値および垂直方向の二次微分値を算出する二次微分値算出部と、
各部分領域の各画素ごとに、前記右下がり斜め方向の二次微分値と前記右上がり斜め方向の二次微分値との絶対値差を第１評価値として算出し、かつ前記水平方向の二次微分値と前記垂直方向の二次微分値との絶対値差を第２評価値として算出する評価値算出部と、
各部分領域ごとに少なくとも一つの特徴点を検出する特徴点検出部と、を備え、
前記特徴点検出部は、
ある部分領域内の各画素の前記第１評価値と、第１閾値とをそれぞれ比較し、前記第１評価値が前記第１閾値を超える画素が前記部分領域内に少なくとも一つ存在する場合、その少なくとも一つの画素を前記部分領域の特徴点候補に決定し、
前記第１評価値が前記第１閾値を超える画素が前記部分領域内に存在しない場合、前記部分領域内の各画素の前記第２評価値と、第２閾値とをそれぞれ比較し、前記第２評価値が前記第２閾値を超える画素が前記部分領域内に少なくとも一つ存在する場合、その少なくとも一つの画素を前記部分領域の特徴点候補に決定することを特徴とする特徴点検出装置。
【請求項５】
前記評価値算出部は、
各画素または前記第１評価値が前記第１閾値を超える画素における、前記右下がり斜め方向の二次微分値の絶対値と、前記右上がり斜め方向の二次微分値の絶対値との和を第３評価値として算出し、
各画素または前記第２評価値が前記第２閾値を超える画素における、前記水平方向の二次微分値の絶対値と、前記垂直方向の二次微分値の絶対値との和を第４評価値として算出し、
前記特徴点検出部は、
前記部分領域において前記第１評価値が前記第１閾値を超える画素が存在する場合、前記第３評価値が最も大きい画素または前記第３評価値の大きい上位複数の画素を前記部分領域の特徴点に決定し、
前記部分領域において前記第１評価値が前記第１閾値を超える画素が存在せず、かつ前記第２評価値が前記第２閾値を超える画素が存在する場合、前記第４評価値が最も大きい画素または前記第４評価値の大きい上位複数の画素を前記部分領域の特徴点に決定することを特徴とする請求項４に記載の特徴点検出装置。
【請求項６】
前記特徴点検出部は、
前記部分領域において前記第１評価値が前記第１閾値を超える画素が存在せず、かつ前記第２評価値が前記第２閾値を超える画素も存在しない場合、前記部分領域内のあらかじめ設定された固定位置の画素を前記部分領域の仮の特徴点に設定するとともに、正規の特徴点が存在しないことを示すフラグを立てることを特徴とする請求項４または５に記載の特徴点検出装置。
【請求項７】
動画像に含まれるフレーム画像内から複数の特徴点を検出する請求項４から６のいずれかに記載の特徴点検出装置と、
前記特徴点検出装置により検出された複数の特徴点のオプティカルフローをそれぞれ算出するオプティカルフロー演算部と、
を備えることを特徴とする動画像処理装置。
【請求項８】
動画像に含まれるフレーム画像内から複数の特徴点を検出する請求項６に記載の特徴点検出装置と、
前記特徴点検出装置により検出された複数の特徴点のオプティカルフローをそれぞれ算出するオプティカルフロー演算部と、
前記フラグが立っている部分領域の特徴点のオプティカルフローを無効とする後処理部と、
を備えることを特徴とする動画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コーナーやエッジなど、画像内の特徴点を検出する特徴点検出装置、およびそれを搭載した動画像処理装置に関する。
【背景技術】
【０００２】
画像処理の前処理として、対象画像から特徴点を検出する処理が広く用いられている。対象画像内の演算対象を全画素ではなく、特徴点として検出された画素に限定すれば演算量を低減することができる。たとえば、オプティカルフロー算出処理の前処理として、特徴点の検出処理が用いられている。オプティカルフローとは、画像内のある点や図形がつぎの瞬間にどのような方向へ、どの程度の距離、移動するかを示すベクトルである。
【０００３】
画像内から特徴点を検出するためによく用いられる手法にＫＬＴ（Kanada-Lucas-Tomashi)法がある。ＫＬＴ法は入力画像上の座標ｃ（ｘ，ｙ）の特徴量Ｈ（ｘ，ｙ）を評価することにより特徴点を求める。ＫＬＴ法では、まず、ガウシアンオペレータにより入力画像が平滑化される。つぎに、一定の大きさの正方形窓Ｗにおいて画像上の輝度Ｉの勾配（Ｉｘ＝∂Ｉ／∂ｘ，Ｉｙ＝∂Ｉ／∂ｙ）を用いて、下記式１に示す行列Ｍを算出する。つぎに、下記式２に示すように行列Ｍの固有値λ１、λ２の最小値を求めることにより、特徴量Ｈ（ｘ，ｙ）を求める。最後にこの特徴量Ｈ（ｘ，ｙ）を評価して特徴点を求める。
【０００４】
【数１】
2010039520.tif 000003
【０００５】
特許文献１は画像中の特徴点を検出するための評価値を計算する画像処理装置を開示する。この画像処理装置は各画素における複数の方向の各々に関して、輝度値の一次空間微分値および二次空間微分値を計算することにより、ノイズ量を推定する。
【特許文献１】特開２００７−２３１５６５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上述したＫＬＴ法は比較的精度よく特徴点を検出することができるが、行列Ｍの固有値λ１、λ２の最小値を求めるなど、複雑な演算処理を必要とする。そのため、ＫＬＴ法による特徴点検出処理をハードウェア資源で構成することは難しい。
【０００７】
本発明はこうした状況に鑑みなされたものであり、その目的は、一定の精度を維持しつつ、簡単な演算処理で特徴点を検出することができる特徴点検出装置、およびそれを搭載した動画像処理装置を提供することにある。
【課題を解決するための手段】
【０００８】
本発明のある態様の特徴点検出装置は、画像内の注目画素における、右下がり斜め方向の二次微分値および右上がり斜め方向の二次微分値を算出する二次微分値算出部と、二次微分値算出部により算出された、右下がり斜め方向の二次微分値と右上がり斜め方向の二次微分値との絶対値差を第１評価値として算出する評価値算出部と、評価値算出部により算出された第１評価値と、第１閾値とを比較することにより、注目画素が画像内の、コーナーまたは斜めエッジに該当するか否か判定する判定部と、を備える。
【０００９】
本発明の別の態様もまた、特徴点検出装置である。この装置は、画像を複数の部分領域に分割する分割部と、分割部により分割された各部分領域の各画素ごとに、右下がり斜め方向の二次微分値、右上がり斜め方向の二次微分値、水平方向の二次微分値および垂直方向の二次微分値を算出する二次微分値算出部と、各部分領域の各画素ごとに、右下がり斜め方向の二次微分値と右上がり斜め方向の二次微分値との絶対値差を第１評価値として算出し、かつ水平方向の二次微分値と垂直方向の二次微分値との絶対値差を第２評価値として算出する評価値算出部と、各部分領域ごとに少なくとも一つの特徴点を検出する特徴点検出部と、を備える。特徴点検出部は、ある部分領域内の各画素の第１評価値と、第１閾値とをそれぞれ比較し、第１評価値が第１閾値を超える画素が部分領域内に少なくとも一つ存在する場合、その少なくとも一つの画素を部分領域の特徴点候補に決定し、第１評価値が第１閾値を超える画素が部分領域内に存在しない場合、部分領域内の各画素の第２評価値と、第２閾値とをそれぞれ比較し、第２評価値が第２閾値を超える画素が部分領域内に少なくとも一つ存在する場合、その少なくとも一つの画素を部分領域の特徴点候補に決定する。
【００１０】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１１】
本発明によれば、一定の精度を確保しつつ、簡単な演算処理で特徴点を検出することができる。
【発明を実施するための最良の形態】
【００１２】
図１は、本発明の実施の形態１に係る特徴点検出装置１００の構成を示すブロック図である。実施の形態１に係る特徴点検出装置１００は、二次微分値算出部１０、評価値算出部２０および判定部３０を備える。これらの構成は、ハードウェア的には、任意のプロセッサ、メモリ、その他のＬＳＩで実現でき、ソフトウェア的にはメモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組み合わせによっていろいろな形で実現できることは、当業者には理解されるところである。
【００１３】
二次微分値算出部１０は、入力された画像内の注目画素における、右下がり斜め方向の二次微分値、右上がり斜め方向の二次微分値、水平方向の二次微分値および垂直方向の二次微分値を算出する。なお、上記注目画素は上記画像内のすべての画素が該当し得る。二次微分値算出部１０は上記注目画素の隣り合う画素を用いて算出してもよいし、一画素おきなど、上記注目画素から二画素以上離れた画素を用いて算出してもよい。なお、本実施の形態における二次微分値を算出するためのオペレータは後述する。
【００１４】
評価値算出部２０は、二次微分値算出部１０により算出された、右下がり斜め方向の二次微分値と右上がり斜め方向の二次微分値との絶対値差を第１評価値として算出し、水平方向の二次微分値と垂直方向の二次微分値との絶対値差を第２評価値として算出する。また、評価値算出部２０は、注目画素における、右下がり斜め方向の二次微分値の絶対値と、右上がり斜め方向の二次微分値の絶対値との和を第３評価値として算出し、水平方向の二次微分値の絶対値と、垂直方向の二次微分値の絶対値との和を第４評価値として算出する。
【００１５】
判定部３０は、評価値算出部２０により算出された第１評価値と、第１閾値とを比較することにより、注目画素が画像内の、コーナーまたは斜めエッジに該当するか否か判定する。より具体的には第１評価値が第１閾値より大きいとき、その注目画素が画像内の、コーナーまたは斜めエッジに該当すると判定する。または、その注目画素が画像内の、コーナーまたは斜めエッジに該当する可能性が高いとして、その注目画素を画像内の、コーナーまたは斜めエッジの候補とする。この判定の原理については後述する。
【００１６】
判定部３０は、評価値算出部２０により算出された第２評価値と、第２閾値とを比較することにより、注目画素が画像内の、水平エッジまたは垂直エッジに該当するか否か判定する。より具体的には第２評価値が第２閾値より大きいとき、その注目画素が画像内の、水平エッジまたは垂直エッジに該当すると判定する。または、その注目画素が画像内の、水平エッジまたは垂直エッジに該当する可能性が高いとして、その注目画素を画像内の、水平エッジまたは垂直エッジの候補とする。
【００１７】
画像内の、コーナー、斜めエッジ、水平エッジおよび垂直エッジは、画像内のオブジェクトの輪郭に出現する。輪郭は画像内の明るさが急激に変化する部分であるため、画像内の明るさの変化を検出することにより、輪郭を検出することができる。本実施の形態ではその明るさの変化を二次微分値として検出している。
【００１８】
判定部３０は、第３評価値と第３閾値とを比較することにより、コーナーまたは斜めエッジの強度を判定する。第３評価値が第３閾値と比較して大きいほど、その強度が強いと判定する。判定部３０は、第４評価値と第４閾値とを比較することにより、水平エッジまたは垂直エッジの強度を判定する。第４評価値が第４閾値と比較して大きいほど、その強度が強いと判定する。第１閾値、第２閾値、第３閾値および第４閾値は、設計者が実験やシミュレーションにより求めた値に設定されることができる。
【００１９】
図２は、実施の形態１に係る、二次微分値の算出に必要なオペレータ１５を示す。このオペレータ１５は、注目画素の係数が−２、およびその周辺画素の係数が＋１である。二次微分値算出部１０は、このオペレータ１５にもとづく四つの一次元フィルタを用いて、右下がり斜め方向（−４５°方向）、右上がり斜め方向（＋４５°方向）、水平方向（０°方向）および垂直方向（＋９０°方向）のそれぞれの二次微分値を算出する。すなわち、下記式３〜６に示すように二次微分値を算出する。
【００２０】
−４５°方向の二次微分値Ｙａ＝Ｉ(i-1,j-1)−２＊Ｉ（i,j）＋Ｉ(i+1,j+1)…（式３）
＋４５°方向の二次微分値Ｙｂ＝Ｉ(i-1,j+1)−２＊Ｉ（i,j）＋Ｉ(i+1,j-1)…（式４）
０°方向の二次微分値Ｙｃ＝Ｉ(i-1,j)−２＊Ｉ（i,j）＋Ｉ(i+1,j)    …（式５）
＋９０°方向の二次微分値Ｙｄ＝Ｉ(i,j+1)−２＊Ｉ（i,j）＋Ｉ(i,j-1)    …（式６）
Ｉは画素の明るさを示す値であり、カラー画像の場合、Ｒ値、Ｂ値およびＧ値の平均値であってもよいし、ＹＣｂＣｒ系の輝度値であってもよい。iは図２に示すように左から右にインクリメントしていく変数である。jは図２に示すように上から下にインクリメントしていく変数である。
【００２１】
図３は、実施の形態１に係る、−４５°方向の二次微分値Ｙａを算出するための一次元フィルタ１５ａを示す図である。この一次元フィルタ１５ａは、加算器１６、乗算器１７および減算器１８を含む。加算器１６はＩ(i-1,j-1)およびＩ(i+1,j+1)を加算する。乗算器１７はＩ（i,j）を２倍にする。減算器１８は加算器１６の出力値と乗算器１７の出力値との差分を算出する。減算器１８の出力値が−４５°方向の二次微分値Ｙａとなる。＋４５°方向の二次微分値Ｙｂ、０°方向の二次微分値Ｙｃ、および＋９０°方向の二次微分値Ｙｄについても同様の構成で求めることができる。
【００２２】
図４は、実施の形態１に係る、画像内の−４５°方向の空間軸Ｓにおける二次微分値Ｙａの推移を示す。すなわち、−４５°方向に連続する各画素の二次微分値Ｙａの推移を示す。各画素の明るさを明と暗に二分類する場合、二次微分値Ｙａが正のとき暗に、二次微分値Ｙａが負のとき明に分類する。二次微分値Ｙａが正から負に大きくゼロクロスする部分が（図４ではｅ１）、暗から明へのエッジ境界となる。同様に、二次微分値Ｙａが負から正に大きくゼロクロスする部分が（図４ではｅ２）、明から暗へのエッジ境界となる。二次微分値Ｙａは注目画素とその両側の隣接画素との間の、二つの明るさの変化が反映された値であるため、エッジ境界の前後で二次微分値Ｙａが正方向および負方向に大きく振れる。＋４５°方向の二次微分値Ｙｂ、０°方向の二次微分値Ｙｃ、および＋９０°方向の二次微分値Ｙｄについても同様の議論があてはまる。
【００２３】
図５は、実施の形態１に係る、第１評価値からコーナーまたは斜めエッジ、および第２評価値から水平エッジまたは垂直エッジを検出する原理を説明するための図である。第１パターンＰ１はコーナーで出現する３×３の画素パターンを示す。第２パターンＰ２もコーナーで出現する３×３の画素パターンを示す。第１パターンＰ１は画素パターンの右上に出現したコーナーを示し、第２パターンＰ２は画素パターンの右下に出現したコーナーを示す。
【００２４】
第３パターンＰ３は右下がりの斜めエッジで出現する３×３の画素パターンを示す。第４パターンＰ４は水平エッジで出現する３×３の画素パターンを示す。第５パターンＰ５は垂直エッジで出現する３×３の画素パターンを示す。図５において、黒丸は各画素の明るさを明と暗に二分類する場合の、暗を示し、白丸は明を示す。
【００２５】
図６は、図５における各パターンＰ１〜Ｐ５の、四方向の二次微分値Ｙａ〜Ｙｄをまとめたテーブル２５を示す。図６では黒丸画素の画素値と白丸画素の画素値との差分の、平均値をαで示す。第１パターンＰ１では−４５°方向の二次微分値Ｙａのみが２αとなり、残りの三方向の二次微分値Ｙｂ、Ｙｃ、Ｙｄはいずれもαである。画素パターンの左下にコーナーが出現した場合も同様の結果となる。第２パターンＰ２では＋４５°方向の二次微分値Ｙｂのみが２αとなり、残りの三方向の二次微分値Ｙａ、Ｙｃ、Ｙｄはいずれもαである。画素パターンの左上にコーナーが出現した場合も同様の結果となる。
【００２６】
２αは注目画素が暗、その両側の隣接画素がいずれも明のときに出現する値である。このように、画素パターン内にコーナーが存在する場合、−４５°方向の二次微分値Ｙａおよび＋４５°方向の二次微分値Ｙｂのどちらかが２αとなり、−４５°方向の二次微分値Ｙａと＋４５°方向の二次微分値Ｙｂとの差分がαとなる。また、０°方向の二次微分値Ｙｃと＋９０°方向の二次微分値Ｙｄとの差分が０となる。
【００２７】
第３パターンＰ３では−４５°方向の二次微分値Ｙａのみが０となり、残りの三方向の二次微分値Ｙｂ、Ｙｃ、Ｙｄはいずれもαである。右上がりの斜めエッジで出現する画素パターンでは、＋４５°方向の二次微分値Ｙｂのみが０となり、残りの三方向の二次微分値Ｙａ、Ｙｃ、Ｙｄはいずれもαである。このように、画素パターン内に斜めエッジが存在する場合、−４５°方向の二次微分値Ｙａおよび＋４５°方向の二次微分値Ｙｂのどちらかが０となり、−４５°方向の二次微分値Ｙａと＋４５°方向の二次微分値Ｙｂとの差分がαとなる。また、０°方向の二次微分値Ｙｃと＋９０°方向の二次微分値Ｙｄとの差分が０となる。
【００２８】
第４パターンＰ４では０°方向の二次微分値Ｙｃのみが０となり、残りの三方向の二次微分値Ｙａ、Ｙｂ、Ｙｄはいずれもαである。第５パターンＰ５では９０°方向の二次微分値Ｙｄのみが０となり、残りの三方向の二次微分値Ｙａ、Ｙｂ、Ｙｃはいずれもαである。このように、画素パターン内に水平エッジまたは垂直エッジが存在する場合、０°方向の二次微分値Ｙｃおよび＋９０°方向の二次微分値Ｙｄのどちらかが０となり、０°方向の二次微分値Ｙｃと＋９０°方向の二次微分値Ｙｄとの差分がαとなる。また、−４５°方向の二次微分値Ｙａと＋４５°方向の二次微分値Ｙｂとの差分が０となる。
【００２９】
ここで、上述した第１評価値Ｅ１、第２評価値Ｅ２、第３評価値Ｅ３および第４評価値Ｅ４の算出式を下記式７〜１０に示す。
【００３０】
第１評価値Ｅ１＝｜Ｙａ−Ｙｂ｜      …（式７）
第２評価値Ｅ２＝｜Ｙｃ−Ｙｄ｜      …（式８）
第３評価値Ｅ３＝｜Ｙａ｜＋｜Ｙｂ｜  …（式９）
第４評価値Ｅ４＝｜Ｙｃ｜＋｜Ｙｄ｜  …（式１０）
【００３１】
このように、第１評価値Ｅ１がαを超えていれば、コーナーまたは斜めエッジが出現した可能性が高いことを認識することができる。また、第３評価値Ｅ３を算出すれば、コーナーか斜めエッジかを分類することも可能である。第３評価値Ｅ３が３αを超えていればコーナーと判定することができる。第３評価値Ｅ３がαを下回っていれば、斜めエッジと判定することができる。設計者はα〜３α内の所定の値を、コーナーと斜めエッジとを分ける第５閾値に設定することができる。
【００３２】
αの値が大きい場合、第３評価値Ｅ３の値も大きくなる。αの値が大きいということは、注目画素とその隣接画素との間の明るさの変化が大きいことを示し、より鮮明な輪郭であることを示す。第３評価値Ｅ３が大きいほど、より鮮明なコーナーであることを示す。すなわち、強度が強いコーナーであることを示す。
【００３３】
また、第２評価値Ｅ２がαを超えていれば、水平エッジまたは垂直エッジが出現した可能性が高いことを認識することができる。また、０°方向の二次微分値Ｙｃと＋９０°方向の二次微分値Ｙｄを参照すれば、水平エッジか垂直エッジかを分類することも可能である。第３評価値Ｅ３と同様に、第４評価値Ｅ４が大きいほど、より鮮明な、水平エッジまたは垂直エッジであることを示す。すなわち、強度が強い、水平エッジまたは垂直エッジであることを示す。
【００３４】
なお、第１評価値Ｅ１〜第４評価値Ｅ４は絶対値で表現されるため、図５に示した第１パターンＰ１〜第５パターンＰ５において、白丸画素と黒丸画素とがすべて反転した画素パターンについても、それぞれ元のパターンと同じ評価値となる。また、注目画素の両側の白丸画素と黒丸画素とが入れ替わっても、同じ二次微分値が算出されるが、自然画像ではそのような画素パターンは非常に少ないといえる。
【００３５】
図７は、実施の形態１に係る特徴点検出装置１００を使用して、フレーム画像内から特徴点を検出する処理の一例を示すフローチャートである。二次微分値を求めるには両側に隣接画素が必要なため、フレーム画像内において、一番上および一番下の水平方向の画素列、ならびに一番左および一番右の垂直方向の画素列に属する画素については二次微分値を算出しない。後述するフレーム画像内のすべての画素とは、これらの画素を除いた画素を指す。
【００３６】
まず、フレーム画像内の任意の画素を注目画素の初期値に設定する。たとえば、上から二番目および左から二番目の画素を初期値とする。判定部３０はその注目画素の第１評価値Ｅ１＝｜Ｙａ−Ｙｂ｜と第１閾値Ｙｔｈ１とを比較する（Ｓ１０）。第１評価値Ｅ１が第１閾値Ｙｔｈ１より大きい場合（Ｓ１０のＹ）、判定部３０は第３評価値Ｅ３＝｜Ｙａ｜＋｜Ｙｂ｜と第３閾値Ｙｔｈ３とを比較する（Ｓ１２）。第３評価値Ｅ３が第３閾値Ｙｔｈ３より大きい場合（Ｓ１２のＹ）、その注目画素を特徴点に設定する（Ｓ１８）。
【００３７】
ステップＳ１０にて第１評価値Ｅ１が第１閾値Ｙｔｈ１以下の場合（Ｓ１０のＮ）、およびステップＳ１２にて第３評価値Ｅ３が第３閾値Ｙｔｈ３以下の場合（Ｓ１２のＮ）、判定部３０はその注目画素の第２評価値Ｅ２＝｜Ｙｃ−Ｙｄ｜と第２閾値Ｙｔｈ２とを比較する（Ｓ１４）。第２評価値Ｅ２が第２閾値Ｙｔｈ２より大きい場合（Ｓ１４のＹ）、判定部３０は第４評価値Ｅ４＝｜Ｙｃ｜＋｜Ｙｄ｜と第４閾値Ｙｔｈ４とを比較する（Ｓ１６）。第４評価値Ｅ４が第４閾値Ｙｔｈ４より大きい場合（Ｓ１６のＹ）、その注目画素を特徴点に設定する（Ｓ１８）。
【００３８】
ステップＳ１４にて第２評価値Ｅ２が第２閾値Ｙｔｈ２以下の場合（Ｓ１４のＮ）、およびステップＳ１６にて第４評価値Ｅ４が第４閾値Ｙｔｈ４以下の場合（Ｓ１６のＮ）、判定部３０はその注目画素を特徴点と判定しない。
【００３９】
判定部３０はこの特徴点に設定すべきか否かの判定がフレーム画像内のすべての画素について終了したか否かを判定する（Ｓ２０）。終了していない場合（Ｓ２０のＮ）、判定部３０はつぎの画素を注目画素に設定する（Ｓ２２）。以下、ステップＳ１０に遷移して上述した判定処理を継続する。終了した場合（Ｓ２０のＹ）、そのフレーム画像における特徴点の検出処理を終了する。
【００４０】
このフローチャートに示すアルゴリズムは、特徴点としてコーナーをエッジより優先したものである。通常、コーナーのほうがエッジより出現頻度が低く、価値が高いためである。なお、コーナーをエッジより優先するアルゴリズム、コーナーのみを検出するアルゴリズム、斜めエッジのみを検出するアルゴリズム、ならびに水平エッジおよび垂直エッジのみを検出するアルゴリズムも当業者であれば、容易に実施可能である。
【００４１】
なお、上記フローチャートには二次微分値算出部１０および評価値算出部２０の処理を明示的に記述していないが、以下に示す二つの処理方法がある。第１の処理方法は、すべての画素について二次微分値算出部１０が四方向の二次微分値Ｙａ、Ｙｂ、Ｙｃ、Ｙｄを算出し、および評価値算出部２０が第１評価値Ｅ１〜第４評価値Ｅ４を算出する処理方法である。
【００４２】
第２の処理方法は、すべての画素について特徴点の判定に必要な限度で、二次微分値算出部１０および評価値算出部２０がそれらの値を算出する処理方法である。たとえば、第１評価値Ｅ１が第１閾値Ｙｔｈ１より大きく、かつ第３評価値Ｅ３が第３閾値Ｙｔｈ３より大きい場合、二次微分値算出部１０は０°方向の二次微分値Ｙｃおよび＋９０°方向の二次微分値Ｙｄを算出せず、評価値算出部２０は第２評価値Ｅ２および第４評価値Ｅ４を算出しない。第２の処理方法は無駄な演算を省くことができる。
【００４３】
以上説明したように実施の形態１によれば、一定の精度を維持しつつ、簡単な演算処理で特徴点を検出することができる。すなわち、右下がり斜め方向の二次微分値と右上がり斜め方向の二次微分値との差分を評価することにより、コーナーまたは斜めエッジを検出することができる。また、水平方向の二次微分値と垂直方向の二次微分値との差分を評価することにより、水平エッジまたは垂直エッジを検出することができる。いずれの場合も、簡単な、四則演算および閾値判定処理のみで検出することができる。また、後述する図９（ａ）、図９（ｂ）に示すようにその検出精度も高い。また、複雑な演算処理を必要としないため、ハードウェア資源で実装することも容易である。
【００４４】
また、コーナーおよびエッジの強度を検出することができ、その強度を特徴点の検出精度の向上や、特徴点の数の調整に利用することができる。具体的には、第３閾値および第４閾値を高く設定することにより、特徴点の検出精度を向上させることができる。すなわち、誤検出を低減することができる。また、フレーム画像内から検出される特徴点の数を減らすことができる。一方、第３閾値および第４閾値を低く設定することにより、フレーム画像内から検出される特徴点の数を増やすことができる。
【００４５】
図８は、本発明の実施の形態２に係る特徴点検出装置１５０の構成を示すブロック図である。実施の形態２に係る特徴点検出装置１５０は、分割部５、二次微分値算出部１０、評価値算出部２０および特徴点検出部４０を備える。
【００４６】
分割部５は、入力されるフレーム画像を複数の部分領域に分割する。この部分領域は縦ｎ画素×横ｍ画素（ｎ，ｍは３以上の整数）の矩形の窓領域であってもよい。なお、上記部分領域は必ずしも矩形である必要はなく、SUSANオペレータで設定されるような円形状の領域であってもよい。
【００４７】
二次微分値算出部１０は、分割部５により分割された各部分領域の各画素ごとに、右下がり斜め方向の二次微分値、右上がり斜め方向の二次微分値、水平方向の二次微分値および垂直方向の二次微分値を算出する。これらの二次微分値の算出方法は、実施の形態１で説明した算出方法と同様である。
【００４８】
評価値算出部２０は、各部分領域の各画素ごとに、右下がり斜め方向の二次微分値と右上がり斜め方向の二次微分値との絶対値差を第１評価値として算出し、水平方向の二次微分値と垂直方向の二次微分値との絶対値差を第２評価値として算出する。
【００４９】
評価値算出部２０は、各画素または第１評価値が第１閾値を超える画素における、右下がり斜め方向の二次微分値の絶対値と、右上がり斜め方向の二次微分値の絶対値との和を第３評価値として算出する。また、評価値算出部２０は、各画素または第２評価値が第２閾値を超える画素における、水平方向の二次微分値の絶対値と、垂直方向の二次微分値の絶対値との和を第４評価値として算出する。なお、第３評価値および第４評価値は、すべての画素について算出されてもよいし、特徴点を検出するために必要な限度で算出されてもよい。
【００５０】
特徴点検出部４０は、各部分領域ごとに少なくとも一つの特徴点を検出する。以下、具体的に説明する。特徴点検出部４０は、ある部分領域内の各画素の第１評価値と、第１閾値とをそれぞれ比較する。第１評価値が第１閾値を超える画素がその部分領域内に少なくとも一つ存在する場合、特徴点検出部４０はその少なくとも一つの画素を部分領域の特徴点候補に決定する。
【００５１】
第１評価値が第１閾値を超える画素がその部分領域内に存在しない場合、特徴点検出部４０は、その部分領域内の各画素の第２評価値と、第２閾値とをそれぞれ比較する。第２評価値が第２閾値を超える画素が部分領域内に少なくとも一つ存在する場合、特徴点検出部４０はその少なくとも一つの画素を部分領域の特徴点候補に決定する。
【００５２】
上記部分領域において第１評価値が第１閾値を超える画素が存在する場合、特徴点検出部４０は第３評価値が最も大きい画素または第３評価値の大きい上位複数の画素を部分領域の特徴点に決定する。各部分領域ごとに二つの特徴点を設定する場合、第３評価値が一番大きい画素と二番目に大きい画素を特徴点に決定する。上記部分領域において第１評価値が第１閾値を超える画素が存在せず、かつ第２評価値が第２閾値を超える画素が存在する場合、特徴点検出部４０は第４評価値が最も大きい画素または第４評価値の大きい上位複数の画素を部分領域の特徴点に決定する。
【００５３】
上記部分領域において第１評価値が第１閾値を超える画素が存在せず、かつ第２評価値が第２閾値を超える画素も存在しない場合、特徴点検出部４０は上記部分領域内のあらかじめ設定された固定位置の画素を上記部分領域の仮の特徴点に設定するとともに、正規の特徴点が存在しないことを示すフラグを立てる。当該固定位置の画素は、各部分領域の中央に位置する画素であってもよいし、左上隅の画素であってもよいし、その他の位置の画素であってもよい。
【００５４】
特徴点検出部４０は、特徴点を検出した部分領域については、その特徴点の位置情報（たとえば、座標値）および画素値を特定するとともに、その部分領域に有効な特徴点が設定されていることを示すフラグを立ててもよい。特徴点検出部４０は、特徴点を検出できず、上記固定位置の画素を設定した部分領域については、その画素の位置情報および画素値を特定するとともに、その部分領域に無効な特徴点が設定されていることを示すフラグを立ててもよい。
【００５５】
図９（ａ）は、実施の形態２に係る特徴点検出装置１５０により特徴点が設定されたフレーム画像を示す図である。図９（ａ）に示すフレーム画像内にはその中央に長方形のオブジェクトが描かれている。図９（ａ）に示すフレーム画像内には上記部分領域として、複数の正方形窓が設定される。ここでは、各正方形窓に一つの特徴点を設定する。正方形窓Ｗ（1,1）〜正方形窓Ｗ（6,1）、正方形窓Ｗ（1,1）〜正方形窓Ｗ（1,5）、正方形窓Ｗ（1,5）〜正方形窓Ｗ（3,5）、および正方形窓Ｗ（6,1）〜正方形窓Ｗ（6,5）には上記オブジェクトが含まれない。それらの正方形窓では上記オブジェクトのコーナーやエッジが検出されない。したがって、それらの正方形窓には固定位置のダミーの特徴点が設定される。図９（ａ）ではそれぞれの正方形窓の中央位置にダミーの特徴点が設定される。
【００５６】
また、正方形窓Ｗ（3,3）および正方形窓Ｗ（4,3）は上記オブジェクトの内部に含まれ、上記オブジェクトのコーナーやエッジを含まない。したがって、それらの正方形窓にも固定位置のダミーの特徴点が設定される。
【００５７】
正方形窓Ｗ（2,2）、正方形窓Ｗ（5,2）、正方形窓Ｗ（2,4）および正方形窓Ｗ（5,4）は、上記オブジェクトのコーナーを含む。したがって、それぞれの正方形窓ではそのコーナー部分に、特徴点Ｆ（2,2）、特徴点Ｆ（5,2）、特徴点Ｆ（2,4）および特徴点Ｆ（5,4）がそれぞれ検出される。正方形窓Ｗ（3,2）、正方形窓Ｗ（4,2）、正方形窓Ｗ（2,3）、正方形窓Ｗ（5,3）、正方形窓Ｗ（3,4）および正方形窓Ｗ（4,4）、正方形窓Ｗ（4,5）および正方形窓Ｗ（5,5）は、上記オブジェクトの水平エッジまたは垂直エッジを含む。したがって、それぞれの正方形窓ではそのエッジ部分に、特徴点Ｆ（3,2）、特徴点Ｆ（4,2）、特徴点Ｆ（2,3）、特徴点Ｆ（5,3）、特徴点Ｆ（3,4）、特徴点Ｆ（4,4）、特徴点Ｆ（4,5）および特徴点Ｆ（5,5）がそれぞれ検出される。
【００５８】
図９（ｂ）は、上記ＫＬＴ法により特徴点が設定されたフレーム画像を示す図である。ＫＬＴ法ではHarrisオペレータが使用される。図９（ｂ）のフレーム画像内に描かれているオブジェクトは図９（ａ）のフレーム画像内に描かれているオブジェクトと同じである。上記オブジェクトのコーナーおよびエッジに特徴点が検出されているが、三箇所、誤検出がある（Ｅ１、Ｅ２およびＥ３参照）。これらの特徴点はコーナーおよびエッジ以外の領域で検出されている。
【００５９】
図１０は、実施の形態２に係る特徴点検出装置１５０を使用して、フレーム画像内から特徴点を検出する処理の一例を示すフローチャートである。このフローチャートに示すアルゴリズムは一つの部分領域内に一つの特徴点を設定するためのものである。したがって、フレーム画像内に設定されたすべての部分領域について、このアルゴリズムが実行される。
【００６０】
まず、対象とする部分領域内の任意の画素を注目画素の初期値に設定する。たとえば、左上隅の画素を初期値とする。特徴点検出部４０はその注目画素の第１評価値Ｅ１＝｜Ｙａ−Ｙｂ｜と第１閾値Ｙｔｈ１とを比較する（Ｓ３０）。第１評価値Ｅ１が第１閾値Ｙｔｈ１より大きい場合（Ｓ３０のＹ）、特徴点検出部４０はその画素を、コーナーおよび斜めエッジの候補に設定する（Ｓ３２）。
【００６１】
第１評価値Ｅ１が第１閾値Ｙｔｈ１以下の場合（Ｓ３０のＮ）、特徴点検出部４０はその注目画素の第２評価値Ｅ２＝｜Ｙｃ−Ｙｄ｜と第２閾値Ｙｔｈ２とを比較する（Ｓ３４）。第２評価値Ｅ２が第２閾値Ｙｔｈ２より大きい場合（Ｓ３４のＹ）、特徴点検出部４０はその画素を、水平エッジおよび垂直エッジの候補に設定する（Ｓ３６）。第２評価値Ｅ２が第２閾値Ｙｔｈ２以下の場合（Ｓ３４のＮ）、特徴点検出部４０はその画素を、特徴点候補に設定しない。
【００６２】
特徴点検出部４０はこの特徴点に設定すべきか否かの判定が上記部分領域内のすべての画素について終了したか否かを判定する（Ｓ３８）。終了していない場合（Ｓ３８のＮ）、特徴点検出部４０はつぎの画素を注目画素に設定する（Ｓ４０）。以下、ステップＳ３０に遷移して上述した判定処理を継続する。終了した場合（Ｓ３８のＹ）、以下の処理を実行する。
【００６３】
特徴点検出部４０はコーナーおよび斜めエッジの候補が存在するか否か判定する（Ｓ４２）。存在する場合（Ｓ４２のＹ）、特徴点検出部４０はコーナーおよび斜めエッジの候補のうち、第３評価値Ｅ３＝｜Ｙａ｜＋｜Ｙｂ｜が最大のものを特徴点に設定し（Ｓ４４）、処理を終了する。コーナーおよび斜めエッジの候補が存在しない場合（Ｓ４２のＮ）、特徴点検出部４０は水平エッジおよび垂直エッジの候補が存在するか否か判定する（Ｓ４６）。存在する場合（Ｓ４６のＹ）、特徴点検出部４０は水平エッジおよび垂直エッジの候補のうち、第４評価値Ｅ４＝｜Ｙｃ｜＋｜Ｙｄ｜が最大のものを特徴点に設定し（Ｓ４８）、処理を終了する。水平エッジおよび垂直エッジの候補が存在しない場合（Ｓ４６のＮ）、特徴点検出部４０はあらかじめ設定された固定画素をダミーの特徴点に設定し（Ｓ５０）、処理を終了する。
【００６４】
このフローチャートに示すアルゴリズムは、一つの部分領域に一つの特徴点を設定するものであるが、一つの部分領域に複数の特徴点を設定するアルゴリズムも当業者であれば、容易に実施可能である。
【００６５】
以上説明したように実施の形態２によれば、実施の形態１の効果と同様の効果を奏する。実施の形態１の効果に加えて以下の効果を奏する。実施の形態２ではフレーム画像を複数の部分領域に分割し、それぞれの部分領域に決まった数の特徴点を設定する。また、特徴点を検出できなかった部分領域についてもダミーの特徴点を設定する。これらにより、フレーム画像内における特徴点の密度または分布を均一化することができる。したがって、特徴点検出装置１５０の後段の処理ブロックをハードウェア資源で設計することが容易となる。
【００６６】
つぎに、実施の形態２に係る特徴点検出装置１５０を適用した動画像処理システムについて説明する。図１１は、実施の形態３に係る動画像処理システム２００の構成を示す。動画像処理システム２００は、撮像部２１０および動画像処理装置２２０を備える。撮像部２１０は、撮像素子６０および信号処理部６２を有する。動画像処理装置２２０は、フレームバッファ７０、対象フレーム選択部７２、参照フレーム選択部７４、オプティカルフロー検出部７６および後処理部８０を有する。オプティカルフロー検出部７６は、特徴点検出装置１５０およびオプティカルフロー演算部７８を含む。
【００６７】
撮像部２１０は、車両などの移動体や、壁や柱などの建造物に搭載され、動画像を撮像して動画像処理装置２２０に出力する。撮像素子６０は、ＣＣＤ（Charge Coupled Devices）センサやＣＭＯＳ（Complementary Metal-Oxide Semiconductor）イメージセンサなどが用いられ、入射光を電気信号に変換し、信号処理部６２に出力する。
【００６８】
信号処理部６２は、撮像素子６０から入力されるアナログ信号をデジタル信号に変換する。また、平滑化フィルタを備え、動画像処理装置２２０に対して出力する画像データに対して平滑化処理を施してもよい。また、その他のノイズ除去処理を施してもよい。
【００６９】
動画像処理装置２２０は、撮像部２１０から入力される画像データからオプティカルフローを検出する。フレームバッファ７０は、ｑ（ｑは自然数）フレーム画像分、格納する領域を持ち、撮像部２１０から入力される画像データを一時格納する。フレームバッファ７０の領域が溢れた場合、先に入力されたフレーム画像から順番に破棄する。フレームバッファ７０に格納されたフレーム画像は、対象フレーム選択部７２および参照フレーム選択部７４に出力される。
【００７０】
対象フレーム選択部７２は、フレームバッファ７０内のフレーム画像を順番にオプティカルフロー検出部７６に出力する。ここで、フレームバッファ７０内のフレーム画像は適宜、間引いて、出力されてもよい。参照フレーム選択部７４は、対象フレーム選択部７２で選択されたフレーム画像の参照フレーム画像を選択し、フレームバッファ７０内から取得する。
【００７１】
オプティカルフロー検出部７６は、上記対象フレーム画像と上記参照フレーム画像とを用いて、オプティカルフローを検出する。特徴点検出装置１５０は、実施の形態２で説明した装置であり、対象フレーム選択部７２により選択された対象フレーム画像内から複数の特徴点を検出する。その際、上述したように部分領域単位で特徴点を検出する。なお、特徴点の検出処理を解像度の異なる複数の階層で実行してもよい。特徴点検出装置１５０は、検出した特徴点の、位置情報および画素値をオプティカルフロー演算部７８に出力する。
【００７２】
オプティカルフロー演算部７８は、特徴点検出装置１５０により検出された、複数の特徴点のオプティカルフローをそれぞれ算出する。オプティカルフロー演算部７８は、対象フレーム選択部７２により選択された対象フレーム画像、特徴点検出装置１５０から入力された特徴点の位置情報および画素値、ならびに参照フレーム選択部７４により選択された参照フレーム画像に基づき、オプティカルフローを算出する。より具体的には、対象フレーム画像内で検出された複数の特徴点にそれぞれ対応する点を、参照フレーム画像内で探索する。
【００７３】
後処理部８０は、オプティカルフロー検出部７６から出力されたオプティカルフローに対して所定の後処理を施す。たとえば、後処理部８０は上述した正規の特徴点が存在しないことを示すフラグが立っている部分領域の特徴点のオプティカルフローを無効とする。
【００７４】
また、後処理部８０は入力されるオプティカルフローから、撮像部２１０自体の移動による成分を差し引く処理を行ってもよい。また、後処理部８０はノイズを除去するため、入力されるオプティカルフローの長さを第６閾値と比較して、有効とすべきオプティカルフローの長さを制限する処理を行ってもよい。ノイズ除去用の第６閾値は、あらかじめ設定された値でもよいし、当該平均値またはその平均値を調整した値であってもよい。また、後処理部８０はオプティカルフロー検出部７６から出力されたオプティカルフローの長さの平均値を算出してもよい。
【００７５】
以上説明したように実施の形態３によれば、オプティカルフロー算出の前処理として、実施の形態２に係る特徴点検出装置１５０を利用して、オプティカルフローの算出対象とすべき特徴点を検出することにより、その算出対象を大幅に減らすことができる。よって、オプティカルフロー算出処理を高速化することが可能である。また、特徴点の密度が均一化されているため、オプティカルフロー検出部７６および後処理部８０をハードウェア資源で構成することが容易である。また、特徴点を検出できなかった部分領域ではオプティカルフローをマスクすることができるため、オプティカルフローの誤検出を低減することができる。
【００７６】
以上、本発明をいくつかの実施形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００７７】
実施の形態１、２では二次微分値を算出する基礎とすべき、注目画素とその両側の周辺画素とが直接、接している例を示したが、注目画素とその両側の周辺画素との間に、一画素または数画素が挿入されていてもよい。
【００７８】
実施の形態３では、オプティカルフロー検出部７６内に実施の形態２に係る特徴点検出装置１５０を搭載する例を説明したが、実施の形態１に係る特徴点検出装置１００を搭載してもよい。また、実施の形態３では特徴点が検出できなかった部分領域における、ダミー特徴点にもとづくオプティカルフローを後処理部８０によりマスクする構成を説明したが、その部分領域ではオプティカルフローの算出自体を無効にする構成も可能である。
【図面の簡単な説明】
【００７９】
【図１】本発明の実施の形態１に係る特徴点検出装置の構成を示すブロック図である。
【図２】実施の形態１に係る、二次微分値の算出に必要なオペレータを示す図である。
【図３】実施の形態１に係る、−４５°方向の二次微分値を算出するための一次元フィルタを示す図である。
【図４】実施の形態１に係る、画像内の−４５°方向の空間軸における二次微分値の推移を示す図である。
【図５】実施の形態１に係る、第１評価値からコーナーまたは斜めエッジ、および第２評価値から水平エッジまたは垂直エッジを検出する原理を説明するための図である。
【図６】図５における各パターンの、四方向の二次微分値をまとめたテーブルを示す図である。
【図７】実施の形態１に係る特徴点検出装置を使用して、フレーム画像内から特徴点を検出する処理の一例を示すフローチャートである。
【図８】本発明の実施の形態２に係る特徴点検出装置の構成を示すブロック図である。
【図９】図９（ａ）は、実施の形態２に係る特徴点検出装置により特徴点が設定されたフレーム画像を示す図である。図９（ｂ）は、上記ＫＬＴ法により特徴点が設定されたフレーム画像を示す図である。
【図１０】実施の形態２に係る特徴点検出装置を使用して、フレーム画像内から特徴点を検出する処理の一例を示すフローチャートである。
【図１１】実施の形態３に係る動画像処理システムの構成を示す図である。
【符号の説明】
【００８０】
５  分割部、  １０  二次微分値算出部、  １５  オペレータ、  １６  加算器、  １７  乗算器、  １８  減算器、  ２０  評価値算出部、  ３０  判定部、  ４０  特徴点検出部、  ６０  撮像素子、  ６２  信号処理部、  ７０  フレームバッファ、  ７２  対象フレーム選択部、  ７４  参照フレーム選択部、  ７６  オプティカルフロー検出部、  ７８  オプティカルフロー演算部、  ８０  後処理部、  ２００  動画像処理システム、  ２１０  撮像部、  ２２０  動画像処理装置。  
【図１】
2010039520.tif 000004
【図２】
2010039520.tif 000005
【図３】
2010039520.tif 000006
【図４】
2010039520.tif 000007
【図５】
2010039520.tif 000008
【図６】
2010039520.tif 000009
【図７】
2010039520.tif 000010
【図８】
2010039520.tif 000011
【図１０】
2010039520.tif 000012
【図１１】
2010039520.tif 000013
【図９】
2010039520.tif 000014