(57)【要約】【課題】時系列映像から特徴点の位置を追跡する場合に、より正確な追跡をする。【解決手段】第１時刻の画像の横方向微分値と縦方向微分値とに基づいて前記第１時刻の画像内の点のコーナーらしさを示すコーナー度を前記第１時刻の画像内の点毎に算出するコーナー度算出部と、前記第１時刻の１時刻前である第２時刻の画像内の特徴点を中心とする第１の大きさの範囲の輝度値と、前記第２時刻の画像内の特徴点に対する前記第１時刻の画像における予測位置を中心とする第２の大きさの範囲内の点を中心点とする前記第１の大きさの範囲の輝度値とに基づく輝度の一致度、及び、前記第１時刻の画像内の前記第１の大きさの範囲の中心点におけるコーナー度に基づく総合一致度を算出し、前記総合一致度が最大となる前記第１の大きさの範囲の中心点を、前記第２時刻の画像内の特徴点に対する前記第１時刻の画像内の追跡位置とする照合処理部とを備える特徴点追跡装置とする。【選択図】図２
2015095179.tif 000002
【特許請求の範囲】
【請求項１】
第１時刻の画像の横方向微分値と縦方向微分値とに基づいて、前記第１時刻の画像内の点のコーナーらしさを示すコーナー度を前記第１時刻の画像内の点毎に算出するコーナー度算出部と、
前記第１時刻の１時刻前である第２時刻の画像内の特徴点を中心とする第１の大きさの範囲の輝度値と、前記第２時刻の画像内の特徴点に対する前記第１時刻の画像における予測位置を中心とする第２の大きさの範囲内の点を中心点とする前記第１の大きさの範囲の輝度値とに基づく輝度の一致度、及び、前記第１時刻の画像内の前記第１の大きさの範囲の中心点におけるコーナー度に基づく総合一致度を算出し、前記総合一致度が最大となる前記第１の大きさの範囲の中心点を、前記第２時刻の画像内の特徴点に対する前記第１時刻の画像内の追跡位置とする照合処理部と、
を備える特徴点追跡装置。
【請求項２】
前記照合処理部は、前記輝度の一致度が最大となる前記第１の大きさの範囲の中心点を仮追跡点として算出し、
前記照合処理部は、前記総合一致度を、前記第１時刻の１時刻前である第２時刻の画像内の特徴点を中心とする第１の大きさの範囲の輝度値と、前記第１時刻の画像の前記仮追跡点を中心点とする第３の大きさの範囲内の点を中心点とする前記第１の大きさの範囲の輝度値とに基づく輝度の一致度、及び、前記第１時刻の画像内の前記第１の大きさの範囲の中心点におけるコーナー度に基づいて算出し、
前記第３の大きさの範囲は、前記第２の大きさの範囲よりも小さい
請求項１に記載の特徴点追跡装置。
【請求項３】
第１時刻及び前記第１時刻の１時刻前である第２時刻の入力画像の横方向微分値を画素値とする横方向エッジ画像と縦方向微分値を画素値とする縦方向エッジ画像とを取得し、前記第１時刻の前記横方向エッジ画像と前記第１時刻の前記縦方向エッジ画像とに基づいて、前記第１時刻の画像内の点のコーナーらしさを示すコーナー度を前記第１時刻の画像内の点毎に算出するコーナー度算出部と、
前記第２時刻の画像内の特徴点を中心とする第１の大きさの範囲の横方向微分値及び縦方向微分値と、前記第２時刻の画像内の特徴点に対する前記第１時刻の画像における予測位置を中心とする第２の大きさの範囲内の点を中心とする前記第１の大きさの範囲の横方向微分値及び縦方向微分値とに基づくエッジ形状の一致度、及び、前記第１時刻の画像内の前記第１の大きさの範囲の中心点におけるコーナー度とに基づく総合一致度を算出し、前記総合一致度が最大となる前記第１の大きさの範囲の中心点を、前記第２時刻の画像内の特徴点に対する追跡位置とする照合処理部と、
を備える特徴点追跡装置。
【請求項４】
前記照合処理部は、前記エッジ形状の一致度が最大となる前記第１の大きさの範囲の中心点を仮追跡点として算出し、
前記照合処理部は、前記総合一致度を、前記第１時刻の１時刻前である第２時刻の画像内の特徴点を中心とする第１の大きさの範囲の横方向微分値及び縦方向微分値と、前記第１時刻の画像の前記仮追跡点を中心点とする第３の大きさの範囲内の点を中心点とする前記第１の大きさの範囲の横方向微分値及び縦方向微分値とに基づく輝度の一致度、及び、前記第１時刻の画像内の前記第１の大きさの範囲の中心点におけるコーナー度に基づいて算出し、
前記第３の大きさの範囲は、前記第２の大きさの範囲よりも小さい
請求項３に記載の特徴点追跡装置。
【請求項５】
前記第１時刻の画像の横方向微分値を画素値とする横方向エッジ画像を生成し、前記第
１時刻の画像の縦方向微分値を画素値とする縦方向エッジ画像を生成し、前記第２時刻の画像の横方向微分値を画素値とする横方向エッジ画像を生成し、前記第２時刻の画像の縦方向微分値を画素値とする縦方向エッジ画像を生成するエッジ検出部と、
を備える請求項３または４に記載の特徴点追跡装置。
【請求項６】
コンピュータが、
第１時刻の画像の横方向微分値と縦方向微分値とに基づいて、前記第１時刻の画像内の点のコーナーらしさを示すコーナー度を前記第１時刻の画像内の点毎に算出し、
前記第１時刻の１時刻前である第２時刻の画像内の特徴点を中心とする第１の大きさの範囲の輝度値と、前記第２時刻の画像内の特徴点に対する前記第１時刻の画像における予測位置を中心とする第２の大きさの範囲内の点を中心点とする前記第１の大きさの範囲の輝度値とに基づく輝度の一致度、及び、前記第１時刻の画像内の前記第１の大きさの範囲の中心点におけるコーナー度に基づく総合一致度を算出し、前記総合一致度が最大となる前記第１の大きさの範囲の中心点を、前記第２時刻の画像内の特徴点に対する前記第１時刻の画像内の追跡位置とする
ことを実行する特徴点追跡方法。
【請求項７】
コンピュータが、
前記輝度の一致度が最大となる前記第１の大きさの範囲の中心点を仮追跡点として算出し、
前記総合一致度を、前記第１時刻の１時刻前である第２時刻の画像内の特徴点を中心とする第１の大きさの範囲の輝度値と、前記第１時刻の画像の前記仮追跡点を中心点とする第３の大きさの範囲内の点を中心点とする前記第１の大きさの範囲の輝度値とに基づく輝度の一致度、及び、前記第１時刻の画像内の前記第１の大きさの範囲の中心点におけるコーナー度に基づいて算出することを実行し、
前記第３の大きさの範囲は、前記第２の大きさの範囲よりも小さい
請求項６に記載の特徴点追跡方法。
【請求項８】
コンピュータが、
第１時刻及び前記第１時刻の１時刻前である第２時刻の入力画像の横方向微分値を画素値とする横方向エッジ画像と縦方向微分値を画素値とする縦方向エッジ画像とを取得し、
前記第１時刻の前記横方向エッジ画像と前記第１時刻の前記縦方向エッジ画像とに基づいて、前記第１時刻の画像内の点のコーナーらしさを示すコーナー度を前記第１時刻の画像内の点毎に算出し、
前記第２時刻の画像内の特徴点を中心とする第１の大きさの範囲の横方向微分値及び縦方向微分値と、前記第２時刻の画像内の特徴点に対する前記第１時刻の画像における予測位置を中心とする第２の大きさの範囲内の点を中心とする前記第１の大きさの範囲の横方向微分値及び縦方向微分値とに基づくエッジ形状の一致度、及び、前記第１時刻の画像内の前記第１の大きさの範囲の中心点におけるコーナー度とに基づく総合一致度を算出し、前記総合一致度が最大となる前記第１の大きさの範囲の中心点を、前記第２時刻の画像内の特徴点に対する追跡位置とする
ことを実行する特徴点追跡方法。
【請求項９】
コンピュータが、
前記エッジ形状の一致度が最大となる前記第１の大きさの範囲の中心点を仮追跡点として算出し、
前記総合一致度を、前記第１時刻の１時刻前である第２時刻の画像内の特徴点を中心とする第１の大きさの範囲の横方向微分値及び縦方向微分値と、前記第１時刻の画像の前記仮追跡点を中心点とする第３の大きさの範囲内の点を中心点とする前記第１の大きさの範囲の横方向微分値及び縦方向微分値とに基づく輝度の一致度、及び、前記第１時刻の画像
内の前記第１の大きさの範囲の中心点におけるコーナー度に基づいて算出することを実行し、
前記第３の大きさの範囲は、前記第２の大きさの範囲よりも小さい
請求項８に記載の特徴点追跡方法。
【請求項１０】
コンピュータが、さらに、
前記第１時刻の画像の横方向微分値を画素値とする横方向エッジ画像を生成し、前記第１時刻の画像の縦方向微分値を画素値とする縦方向エッジ画像を生成し、前記第２時刻の画像の横方向微分値を画素値とする横方向エッジ画像を生成し、前記第２時刻の画像の縦方向微分値を画素値とする縦方向エッジ画像を生成する
こと実行する請求項８または９に記載の特徴点追跡方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特徴点追跡装置、及び、特徴点追跡方法に関する。
【背景技術】
【０００２】
移動体に取り付けたカメラで撮影した映像から特徴点を抽出し、時系列映像から特徴点の位置を追跡する技術がある。
【０００３】
移動体追跡のための画像処理方法として、次のような方法が知られている。第一時刻の映像から特徴点が抽出され、得られた各々の特徴点を中心として小領域が設定される。第二時刻以降の各時刻の映像について、個々の小領域ごとの映像輝度パターンの類似性（一致性）を用いた照合が行われることによって、第一時刻で定めた特徴点の追跡が行われる（第１の方法）。特徴点は、通常、追跡を正確に行うために物体の角を示すコーナー点である。
【０００４】
また、時系列の各時刻での映像について、あらかじめコーナー点（特徴点）を抽出しておき、コーナー点を対象に、コーナー点を中心に小領域を設けて、小領域内の映像輝度パターンの類似性を用いて照合を行い、追跡を行う画像処理方法（第２の方法）も知られている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−０３９６１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、第１の方法では、第一時刻で特徴点を定めておき、第二時刻以降の時刻では小領域の映像輝度パターンの類似性を用いて追跡を行う。そのため、長時間に渡った追跡では、移動体の移動にともない対象物と移動体とのカメラとの相対的な位置関係が変化することがある。これによって、小領域内の輝度映像パターンの見え方が徐々に変化し、追跡している小領域の中心位置（追跡位置）が、第一時刻で定めた特徴点の位置とずれることがある。その結果、追跡位置が徐々にずれてしまうという問題がある。
【０００７】
図１は、特徴点と追跡位置との関係の例を示す図である。図１の例では、時刻ｔ１の画像、時刻ｔ２の画像、時刻ｔ３の画像、時刻ｔ４の画像が表される。ここで、ｔ１＜ｔ２＜ｔ３＜ｔ４である。図１の例では、直方体状の物体の一部が画像に現れている。時刻ｔ＝ｔ１の画像において、直方体の角の１つを特徴点とする。図１の例では、画像の一致度に基づいて追跡を行うので、追跡位置が特徴点である直方体の角の位置から徐々にずれている。
【０００８】
また、第２の方法では、あらかじめ定めたコーナー点（特徴点）を対象に照合を行うので、照合で得られた追跡結果には、時系列的に追跡位置がずれてしまう問題は生じない。しかしながら、一般に、コーナー点が得られるか否かは周囲の輝度パターンの変化に敏感で、移動体の移動に伴って対象物の見え方が変化すると、周期の輝度パターンが変化し、コーナー点が得られなくなることが多い。コーナー点は、着目位置を中心とする小領域内でのコーナー度が極大となる箇所として定められる。コーナー度は、着目位置を中心とする小領域内で輝度映像の水平方向微分値と垂直方向微分値とから定められる。安定したコーナー点を定めるには、着目位置周辺の小領域の大きさを大きく定めることが求められ、
見え方に変化が生じると輝度映像の微分値が大きく変動するため、小領域内の起動映像の微分値から定めるコーナー度が敏感に変化する。さらに、検出されていたコーナー点のコーナー度が極大を示さなくなり、コーナー点が検出されにくくなる。よって、移動体が移動しながら長時間で追跡を行う場合には、途中でコーナー点が得られなくなり、追跡に失敗することがある。
【０００９】
本発明の一態様は、時系列映像から特徴点の位置を追跡する場合に、より正確な追跡をすることを課題とする。
【課題を解決するための手段】
【００１０】
本発明の一態様は、
第１時刻の画像の横方向微分値と縦方向微分値とに基づいて、前記第１時刻の画像内の点のコーナーらしさを示すコーナー度を前記第１時刻の画像内の点毎に算出するコーナー度算出部と、
前記第１時刻の１時刻前である第２時刻の画像内の特徴点を中心とする第１の大きさの範囲の輝度値と、前記第２時刻の画像内の特徴点に対する前記第１時刻の画像における予測位置を中心とする第２の大きさの範囲内の点を中心点とする前記第１の大きさの範囲の輝度値とに基づく輝度の一致度、及び、前記第１時刻の画像内の前記第１の大きさの範囲の中心点におけるコーナー度に基づく総合一致度を算出し、前記総合一致度が最大となる前記第１の大きさの範囲の中心点を、前記第２時刻の画像内の特徴点に対する前記第１時刻の画像内の追跡位置とする照合処理部と、
を備える特徴点追跡装置とする。
【００１１】
開示の態様は、プログラムが情報処理装置によって実行されることによって実現されてもよい。即ち、開示の構成は、上記した態様における各手段が実行する処理を、情報処理装置に対して実行させるためのプログラム、或いは当該プログラムを記録したコンピュータ読み取り可能な記録媒体として特定することができる。また、開示の構成は、上記した各手段が実行する処理を情報処理装置が実行する方法をもって特定されてもよい。
【発明の効果】
【００１２】
本発明の一態様によれば、時系列映像から特徴点の位置を追跡する場合に、より正確な追跡をすることができる。
【図面の簡単な説明】
【００１３】
【図１】図１は、特徴点と追跡位置との関係の例を示す図である。
【図２】図２は、実施形態１の特徴点追跡装置の構成例を示す図である。
【図３】図３は、特徴点抽出装置を実現するコンピュータの例を示す図である。
【図４】図４は、特徴点抽出装置１００の時系列での追跡処理の動作フローの例を示す図である。
【図５】図５は、Ｓｏｂｅｌの横微分オペレータの例を示す図である。
【図６】図６は、Ｓｏｂｅｌの縦微分オペレータの例を示す図である。
【図７】図７は、新規コーナー点リストＮＬＩＳＴの例を示す図である。
【図８】図８は、照合処理部１１４における照合処理の動作フローの例（１）を示す図である。
【図９】図９は、照合処理部１１４における照合処理の動作フローの例（２）を示す図である。
【図１０】図１０は、照合処理部１１４における照合処理の動作フローの例（３）を示す図である。
【図１１】図１１は、照合処理部１１４における照合処理の動作フローの例（４）を示す図である。
【図１２】図１２は、照合処理部１１４における照合処理の動作フローの例（５）を示す図である。
【図１３】図１３は、１時刻前の画像Ｉ１及び現時刻での画像Ｉ２の例を示す図である。
【図１４】図１４は、特徴点追加削除部の動作フローの例を示す図である。
【図１５】図１５は、特徴点追加削除部における特徴点の削除処理の動作フローの例（１）を示す図である。
【図１６】図１６は、特徴点追加削除部における特徴点の削除処理の動作フローの例（２）を示す図である。
【図１７】図１７は、特徴点追加削除部における特徴点の削除処理の動作フローの例（３）を示す図である。
【図１８】図１８は、特徴点追加削除部における特徴点の追加処理の動作フローの例（１）を示す図である。
【図１９】図１９は、特徴点追加削除部における特徴点の追加処理の動作フローの例（２）を示す図である。
【図２０】図２０は、特徴点追加削除部における特徴点の追加処理の動作フローの例（３）を示す図である。
【図２１】図２１は、実施形態２の特徴点追跡装置の構成例を示す図である。
【図２２】図２２は、特徴点抽出装置２００の時系列での追跡処理の動作フローの例を示す図である。
【図２３】図２３は、照合処理部２１４における照合処理の動作フローの例（１）を示す図である。
【図２４】図２４は、照合処理部２１４における照合処理の動作フローの例（２）を示す図である。
【図２５】図２５は、照合処理部２１４における照合処理の動作フローの例（３）を示す図である。
【図２６】図２６は、照合処理部２１４における照合処理の動作フローの例（４）を示す図である。
【図２７】図２７は、照合処理部２１４における照合処理の動作フローの例（５）を示す図である。
【図２８】図２８は、照合処理部２１４における照合処理の動作フローの例（６）を示す図である。
【図２９】図２９は、照合処理部２１４における照合処理の動作フローの例（７）を示す図である。
【図３０】図３０は、照合処理部２１４における照合処理の動作フローの例（８）を示す図である。
【図３１】図３１は、照合処理部２１４における照合処理の動作フローの例（９）を示す図である。
【図３２】図３２は、仮追跡処理における照合範囲の例を示す図である。
【図３３】図３３は、真追跡処理における照合範囲の例を示す図である。
【図３４】図３４は、実施形態３の特徴点追跡装置の構成例を示す図である。
【図３５】図３５は、特徴点抽出装置３００の時系列での追跡処理の動作フローの例を示す図である。
【図３６】図３６は、実施形態４の特徴点追跡装置の構成例を示す図である。
【図３７】図３７は、特徴点抽出装置４００の時系列での追跡処理の動作フローの例を示す図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照して実施形態について説明する。実施形態の構成は例示であり、開示の構成は、開示の実施形態の具体的構成に限定されない。開示の構成の実施にあたって、
実施形態に応じた具体的構成が適宜採用されてもよい。
【００１５】
〔実施形態１〕
画像において、物体の角をなす部分は、コーナー点としての特性、すなわち、コーナー度が局所的に極大値を取るという条件を満たさなくとも、コーナー度としては高い値を取る。そこで、本実施形態の方法は、特徴点の追跡において、着目位置を中心とする小領域内の輝度パターンの一致性に加えて、当該小領域内でコーナー度も高い値を示す箇所を最良一致箇所とする。従来の輝度パターンの一致性に基づく照合では、元の特徴点（コーナー点）を位置ずれなく追跡するための仕組みが無い。これに対して、本実施形態の方法は、画像の一致性とともに、コーナー度も高いことを考慮することで、元の特徴点の選定基準であるコーナーとしての特性を保証し、追跡結果としてコーナー点からのずれを抑えるものである。
【００１６】
本実施形態の方法では、コーナーである特性の保証に、コーナー度の小領域内の分布パターンではなく、各照合中心位置でのコーナー度値を用いることが特徴である。これは、対象物の見え方の変化に伴いコーナー度の分布は敏感に変化するため、真に対応する箇所であっても画像のパターン一致性は高くないためである。
【００１７】
具体的には、ある時刻（時刻ｔ１とする）の映像から特徴点（コーナー点）を定める。時刻ｔ２（ｔ２＞ｔ１）の映像を対象に、コーナー度分布を定めておき、前時刻（時刻ｔ１）の特徴点各々について、現時刻（時刻ｔ２）での映像内を走査する。そして、前時刻の特徴点位置を中心とする小領域内の映像パターンと現時刻の各走査位置を中心とする小領域内の映像パターンとの一致性Ｓ１と、その走査位置でのコーナー度値との積として定められる総合一致度Ｓ２とする。走査の結果、総合一致度Ｓ２が最も高くなる箇所を最良一致箇所として定め、特徴点の追跡を行う。
【００１８】
（構成例）
図２は、実施形態１の特徴点追跡装置の構成例を示す図である。特徴点追跡装置１００は、映像入力部１０２、映像ＤＢ（Data Base、データベース）１０４、コーナー度算出
部１０６、コーナー点検出部１０８、特徴点追加削除部１１０、特徴点ＤＢ１１２、照合処理部１１４を含む。
【００１９】
映像入力部１０２は、カメラで撮影された外界映像を入力し所望のデジタル映像データに変換し、コーナー度算出部１０６、照合処理部１１４、および、映像ＤＢ１０４に送出する。
【００２０】
映像ＤＢ１０４は、現時刻の映像データと、１時刻前の映像データとを保持する。１時刻とは、例えば、フレームレートが３０フレーム／秒の映像データにおいては、１／３０秒である。
【００２１】
コーナー度算出部１０６は、映像データから映像の各位置でのコーナーらしさを表すコーナー度の分布を算出しコーナー点検出部１０８および照合処理部１１４に出力する。
【００２２】
コーナー点検出部１０８は、コーナー度分布を入力にして、コーナー点（特徴点）を抽出する。
【００２３】
特徴点追加削除部１１０は、抽出されたコーナー点列と特徴点ＤＢ１１２に保存される時系列的な追跡点とから新規の特徴点を追加するとともに追跡不適な点を削除する。
【００２４】
特徴点ＤＢ１１２は、時系列的に追跡する特徴点を保存する。
【００２５】
照合処理部１１４は、現時刻の映像と映像ＤＢ１０４に保持される１時刻前の映像とについて、特徴点ＤＢ１１２に保持される特徴点各々について、両映像とコーナー度分布とを用いて照合処理によって追跡を行う。
【００２６】
特徴点追跡装置１００は、映像中の特徴点を時系列的に追跡した追跡結果（画像中の特徴点の位置）を外部に出力する。
【００２７】
特徴点抽出装置１００は、パーソナルコンピュータ（ＰＣ、Personal Computer）のよ
うな汎用のコンピュータまたはサーバマシンのような専用のコンピュータを使用して実現可能である。また、特徴点抽出装置１００は、ワークステーション（ＷＳ、Work Station）、ＰＤＡ（Personal Digital Assistant）のような専用または汎用のコンピュータ、あるいは、コンピュータを搭載した電子機器を使用して実現可能である。また、特徴点抽出装置１００は、スマートフォン、携帯電話、カーナビゲーション装置のような専用または汎用のコンピュータ、あるいは、コンピュータを搭載した電子機器を使用して実現可能である。カーナビゲーション装置は、例えば、自動車等に搭載される。
【００２８】
図３は、特徴点抽出装置を実現するコンピュータの例を示す図である。図３のコンピュータ１０００は、プロセッサ１００２、主記憶装置１００４、及び、二次記憶装置１００６や、通信インタフェース装置のような周辺装置２０００とのインタフェース装置１００８を含む。主記憶装置１００４及び二次記憶装置１００６は、コンピュータ読み取り可能な記録媒体である。
【００２９】
コンピュータ１０００は、プロセッサが記録媒体に記憶されたプログラムを主記憶装置１００４の作業領域にロードして実行し、プログラムの実行を通じて周辺機器が制御されることによって、所定の目的に合致した機能を実現することができる。
【００３０】
プロセッサ１００２は、例えば、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）である。主記憶装置１００４は、例えば、ＲＡＭ（Random Access
Memory）やＲＯＭ（Read Only Memory）を含む。
【００３１】
二次記憶装置１００６は、例えば、ＥＰＲＯＭ（Erasable Programmable ROM）、ハー
ドディスクドライブ（ＨＤＤ、Hard Disk Drive）である。また、二次記憶装置１００６
は、リムーバブルメディア、即ち可搬記録媒体を含むことができる。リムーバブルメディアは、例えば、ＵＳＢ（Universal Serial Bus）メモリ、あるいは、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）のようなディスク記録媒体である。
【００３２】
インタフェース装置１００８は、例えば、ＬＡＮ（Local Area Network）インタフェースボードや、無線通信のための無線通信回路である。
【００３３】
周辺装置２０００は、上記の二次記憶装置や通信インタフェース装置の他、キーボードやポインティングデバイスのような入力装置や、ディスプレイ装置やプリンタのような出力装置を含む。また、入力装置は、カメラのような映像や画像の入力装置や、マイクロフォンのような音声の入力装置を含むことができる。また、出力装置は、スピーカのような音声の出力装置を含むことができる。カメラは、例えば、自動車等に搭載されるカメラである。
【００３４】
特徴点抽出装置１００を実現するコンピュータは、プロセッサが二次記憶装置に記憶されているプログラムを主記憶装置にロードして実行することによって、映像入力部１０２、コーナー度算出部１０６、コーナー点検出部１０８、特徴点追加削除部１１０、照合処
理部１１４としての機能を実現する。一方、映像ＤＢ１０４および特徴点ＤＢ１１２は、主記憶装置または二次記憶装置の記憶領域に設けられる。
【００３５】
特徴点抽出装置１００の各ユニットは、ハードウェアの構成要素、ソフトウェアの構成要素、又は、これらの組み合わせとして、それぞれ実現され得る。
【００３６】
ハードウェアの構成要素は、ハードウェア回路であり、例えば、ＦＰＧＡ（Field Programmable Gate Array）、特定用途向け集積回路（ＡＳＩＣ）、ゲートアレイ、論理ゲー
トの組み合わせ、アナログ回路等がある。
【００３７】
ソフトウェアの構成要素は、ソフトウェアとして所定の処理を実現する部品である。ソフトウェアの構成要素は、ソフトウェアを実現する言語、開発環境等を限定する概念ではない。
【００３８】
プログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくても、並列的または個別に実行される処理を含む。
【００３９】
（動作例）
図４は、特徴点抽出装置１００の時系列での追跡処理の動作フローの例を示す図である。
【００４０】
ステップＳ１０１では、特徴点抽出装置１００の映像入力部１０２は、外界を撮影するカメラ等から映像を取得し、デジタル映像に変換して映像ＤＢ１０４に現時刻の映像を登録するとともに、デジタル映像を次ステップ処理に出力する。
【００４１】
ステップＳ１０２では、コーナー度算出部１０６は、現時刻のデジタル映像から映像中の各位置でコーナーらしさを表すコーナー度を算出し、コーナー度分布を生成する。生成されたコーナー度分布は、コーナー点検出部１０８および照合処理部１１４に送られる。
【００４２】
ステップＳ１０３では、コーナー点検出部１０８は、コーナー度分布を用いてコーナー度が局所的に極大となる箇所を特定し、特定した箇所をコーナー点として次段処理に送る。
【００４３】
ステップＳ１０４では、照合処理部１１４は、映像情報として現時刻の入力映像と映像ＤＢに保持する１時刻前の映像と、前段処理で求まったコーナー度分布と、特徴点ＤＢ１１２に保持される１時刻前までの追跡特徴点情報を取得する。照合処理部１１４は、取得した情報を用いて、１時刻前の追跡特徴点に対する現時刻での対応する位置を算出し、装置出力として装置外に追跡位置（画像の座標値）を出力するとともに、後段処理に追跡結果を出力する。
【００４４】
ステップＳ１０３及びステップＳ１０４は、並列に実行されても、ステップＳ１０４が先に実行されてもよい。
【００４５】
ステップＳ１０５では、特徴点追加削除部１１０は、ステップＳ１０３で得られた現時刻で得られた特徴点列と、ステップＳ１０４で得られた現時刻での追跡特徴点列を入力として、新規特徴点の追加と追跡不要な特徴点の削除を行うことで特徴点ＤＢ１１２を更新し、次時刻での照合処理の準備を行う。
【００４６】
ステップＳ１０６では、特徴点抽出装置１００は、映像の入力が終了したか否かを判定
する。映像の入力が終了した場合（Ｓ１０６；ＹＥＳ）、処理が終了する。映像の入力が終了していない場合（Ｓ１０６；ＮＯ）、処理がステップＳ１０１に戻って、繰り返される。
【００４７】
次に、図４の動作フローの各処理について、詳細に説明する。
【００４８】
映像入力部１０２は、映像入力・ＤＢ登録処理を行う。映像入力部１０２は、時系列的に入力される映像を、所望のデジタル形式映像（デジタル映像データ）に変換し、映像ＤＢ１０４に登録する。映像入力部１０２は、後段処理に、デジタル形式映像を出力する。映像ＤＢ１０４は、２つの時刻の映像データを保持する。即ち、映像ＤＢ１０４は、現時刻の映像データと１時刻前の映像データとを保持する。映像入力部１０２は、映像ＤＢ１０４内にあるその時点での“１時刻前”の映像データを破棄し、映像ＤＢ１０４内のその時点での“現時刻”の映像データを、映像ＤＢ１０４内の“１時刻前”の映像データに移す。さらに、映像入力部１０２は、現時刻で入力された新たな映像データを、映像ＤＢ１０４内の“現時刻”の映像データとして保存する。
【００４９】
なお、所望のデジタル形式映像とは、後段のコーナー度算出に適した映像のことを指し、たとえば、画像の各位置（画素）でモノクロの８ビットの諧調を持つ格子状の映像データなどである。
【００５０】
コーナー度算出部１０６は、モノクロ映像データを入力として、各画素位置でコーナーらしさの度合いを表すコーナー度を算出する。
【００５１】
コーナー度算出部１０６は、画像内の各点について、映像の縦方向及び横方向の微分処理を行う。コーナー度算出部１０６は、画像中の各画素位置を中心として、例えばＳｏｂｅｌオペレータのような縦方向と横方向のそれぞれの微分オペレータを作用させ、画素位置（ｘ，ｙ）ごとに縦方向及び横方向の微分値（それぞれｄｘ（ｘ，ｙ）、ｄｙ（ｘ，ｙ）とする）を算出する。具体的には、入力画像をＩ（ｘ，ｙ）とし、Ｓｏｂｅｌの横方向微分オペレータをｆｘ（ａ，ｂ）、縦方向微分オペレータをｆｙ（ａ，ｂ）とするとき、次の式により画像の各位置（ｘ，ｙ）での横微分値ｄｘ（ｘ，ｙ）と縦微分値ｄｙ（ｘ，ｙ）が得られる。
【数１】
2015095179.tif 000003
【数２】
2015095179.tif 000004
【００５２】
図５は、Ｓｏｂｅｌの横微分オペレータの例を示す図である。Ｓｏｂｅｌの横微分オペレータｆｘ（ａ，ｂ）は、−１≦ａ≦１，−１≦ｂ≦１の３×３で定義され、図５で示されるような係数を有する。
【００５３】
図６は、Ｓｏｂｅｌの縦微分オペレータの例を示す図である。Ｓｏｂｅｌの縦微分オペレータｆｙ（ａ，ｂ）は、−１≦ａ≦１，−１≦ｂ≦１の３×３で定義され、図６で示さ
れるような係数を有する。
【００５４】
ただし、ｄｘ（ｘ，ｙ）、ｄｙ（ｘ，ｙ）は、映像の各画素位置での微分量であればよく、Ｓｏｂｅｌオペレータ以外のオペレータが使用されてもよい。
【００５５】
次に、コーナー度算出部１０６は、微分値の局所積分量の算出を行う。コーナー度算出部１０６は、画像の各点（ｘ，ｙ）の位置に対して、Ｎ×Ｎの矩形領域の積分値として次の３変量（ｇ１１，ｇ１２，ｇ１３）を算出する。ただし、Ｎは奇数値で、Ｎ＝２×ｎ＋１とする。すなわち、ｎは矩形領域の１辺の大きさの１／２相当の大きさを表す。一例として、ｎ＝２、Ｎ＝５である。ただし、ｎおよびＮの大きさは、これらに限定されるものではない。
【数３】
2015095179.tif 000005
【数４】
2015095179.tif 000006
【数５】
2015095179.tif 000007
コーナー度算出部１０６は、３変量（ｇ１１，ｇ１２，ｇ１３）を用いて、画像各点（ｘ，ｙ）の位置に対して、コーナー度Ｃ（ｘ，ｙ）を、次のように、算出する。
【数６】
2015095179.tif 000008
【００５６】
コーナー点検出部１０８は、コーナー点検出処理を行う。コーナー度が３画素×３画素の領域の中心点で極大となるとき、当該中心点がコーナー点である。コーナー点検出部１０８は、先に求めたコーナー度Ｃ（ｘ，ｙ）を入力として、画像各点（ｘ，ｙ）の位置に対して、その位置を中心とする３×３の範囲内を調べる。コーナー点検出部１０８は、範囲内で着目画素位置のコーナー度が極大となる場合に、その位置（ｘ，ｙ）を現時刻の新規コーナー点として、新規コーナー点リスト（新規特徴点リスト）ＮＬＩＳＴに画素位置（ｘ，ｙ）を追加すると共に、新規コーナー点数ＮＮを１だけ増やす。
【００５７】
図７は、新規コーナー点リストＮＬＩＳＴの例を示す図である。新規コーナー点リストＮＬＩＳＴは、コーナー点を識別する番号と、当該コーナー点のｘ座標およびｙ座標とを対応づけて格納する。ＮＮは、新規コーナー点リストＮＬＩＳＴに格納されるコーナー点の数である。
【００５８】
照合処理部１１４は、特徴点の照合処理を行う。映像ＤＢ１０４に保存されている１時刻前の映像をＩ１（ｘ，ｙ）、現時刻の映像をＩ２（ｘ，ｙ）とする。Ｉ１及びＩ２は、例えば、映像の輝度である。また、コーナー度算出部１０６で得られた現時刻の映像に対するコーナー度の分布をＣ（ｘ，ｙ）とし、特徴点ＤＢ１１２に保存されている１時刻前までの追跡特徴点リストをＦＬＩＳＴとする。なお、ＦＬＩＳＴは、特徴点数ＮＦで、ＦＬＩＳＴリスト内のｉ番目の追跡特徴点を取り出す操作として、ＦＧＥＴ（ＦＬＩＳＴ，ｉ）を定義する。また、ＦＧＥＴ（ＦＬＩＳＴ，ｉ）は、ＦＬＩＳＴリスト内のｉ番目の追跡特徴点の画像上での座標値（Ｐｘｉ，Ｐｙｉ）を返す。また、ＦＳＥＴ（ＦＬＩＳＴ，ｉ，ｘ，ｙ）は、ＦＬＩＳＴリスト内のｉ番目の追跡特徴点の位置を、（ｘ，ｙ）に設定するものとする。ここで、ＦＬＩＳＴは、先のＮＬＩＳＴと同じ形式のリストである。
【００５９】
図８、図９、図１０、図１１、図１２は、照合処理部１１４における照合処理の動作フローの例を示す図である。図８の「Ａ１」、「Ａ２」、「Ａ３」は、それぞれ、図９の「Ａ１」、「Ａ２」、「Ａ３」と接続する。図９の「Ｂ１」、「Ｂ２」、「Ｂ３」、「Ｂ４」、「Ｂ５」、「Ｂ６」、「Ｂ７」は、それぞれ、図１０の「Ｂ１」、「Ｂ２」、「Ｂ３」、「Ｂ４」、「Ｂ５」、「Ｂ６」、「Ｂ７」と接続する。図１０の「Ｃ１」、「Ｃ２」、「Ｃ３」、「Ｃ４」、「Ｃ５」、「Ｃ６」、「Ｃ７」、「Ｃ８」、「Ｃ９」は、それぞれ、図１１の「Ｃ１」、「Ｃ２」、「Ｃ３」、「Ｃ４」、「Ｃ５」、「Ｃ６」、「Ｃ７」、「Ｃ８」、「Ｃ９」と接続する。図１１の「Ｄ１」、「Ｄ２」、「Ｄ３」は、それぞれ、図１２の「Ｄ１」、「Ｄ２」、「Ｄ３」と接続する。
【００６０】
ステップＳ１１０１では、照合処理部１１４は、ｉに０を、ＮＭに０を代入する。ｉは、追跡する特徴点の番号に相当する。ステップＳ１１０２では、照合処理部１１４は、ｉが特徴点数ＮＦ未満であるか否かを判定する。ここで、照合処理部１１４は、すべての追跡特徴点について探索を行ったか否かを確認する。ｉが特徴点数ＮＦ以上である（ｉが特徴点数ＮＦになった）場合（Ｓ１１０２；ＮＯ）、処理が終了する。ｉが特徴点数ＮＦ未満である場合（Ｓ１１０２；ＹＥＳ）、処理がステップＳ１１０３に進む。
【００６１】
ステップＳ１１０３では、照合処理部１１４は、ｉ番目の追跡特徴点の座標を、ＦＬＩＳＴから取得する。ＦＬＩＳＴは、特徴点ＤＢ１１２に格納される。照合処理部１１４は、取得した追跡特徴点の座標を、（Ｐｘｉ，Ｐｙｉ）とする。ここで取得した、ｉ番目の追跡特徴点の座標（Ｐｘｉ，Ｐｙｉ）は、１時刻前の座標である。
【００６２】
ステップＳ１１０４では、照合処理部１１４は、Ｓ１ｍａｘに−１を代入し、Ｓ２ｍａｘに−１を代入する。また、ｉ番目の特徴点（追跡特徴点）の現時刻での予測位置（ｑｘ，ｑｙ）は、ＰＲ（ｉ，Ｐｘｉ，Ｐｙｉ）で与えられるものとする。照合処理部１１４は、ＰＲ（ｉ，Ｐｘｉ，Ｐｙｉ）を算出する。ＰＲは、位置予測のための手続きを表す。予測位置（ｑｘ，ｑｙ）は、例えば、２時刻前の追跡特徴点の位置を（ｒｘ２，ｒｙ２）、１時刻前の追跡特徴点の位置を（ｒｘ１，ｒｙ１）とするとき、線形予測値としてｑｘ＝ｒｘ１＋（ｒｘ１−ｒｘ２）、ｑｙ＝ｒｙ１＋（ｒｙ１−ｒｙ２）等で与えられる。位置予測を用いない場合、ｑｘ＝Ｐｘｉ，ｑｙ＝Ｐｙｉとすればよい。
【００６３】
ステップＳ１１０５では、照合処理部１１４は、ｓｙにｑｙ−Ｍｙを代入する。座標（ｓｘ，ｓｙ）は、探索している座標（走査位置）を表す。照合処理部１１４は、予測位置（ｑｘ，ｑｙ）を中心に、横、縦、それぞれ、Ｍｘ、Ｍｙの変動幅で現時刻の画像Ｉ２内での探索を行う。探索範囲は、予測位置（ｑｘ，ｑｙ）を中心に、横幅２Ｍｘ、縦幅２Ｍｙである。
【００６４】
探索に際しては、照合処理部１１４は、先の探索範囲内を走査しながら、探索範囲内の
探索（走査）位置（ｓｘ，ｓｙ）を中心に幅２Ｒ、高さ２Ｒの映像比較用の小領域を設ける。照合処理部１１４は、当該小領域と同じ大きさの小領域を１時刻前での画像Ｉ１の追跡特徴点位置（Ｐｘｉ，Ｐｙｉ）を中心に設ける。照合処理部１１４は、探索範囲内の各走査位置において、小領域内の映像一致度Ｓ１（＝定数−ＳＡＤ（Sum of absolute difference）値）を算出する。ＳＡＤ値は、小領域内での各位置での輝度差の絶対値和を表す。映像一致度Ｓ１は、定数からＳＡＤ値を引くことで、一致度が高いほど、大きな値を取るように調整している。映像一致度Ｓ１は、これに限定されず、例えば、ＳＡＤ値の逆数でもよい。さらに、照合処理部１１４は、小領域内の各位置での輝度差に小領域の中心位置におけるコーナー度を掛けたものの総和Ｓ２（総合一致度）を算出する。そして、照合処理部１１４は、各走査位置において、Ｓ１が閾値ＴＨ以上の場合、一致性が十分で照合として信頼性が高いので、探索範囲内において総合一致度Ｓ２が最大となる位置（ｍｘ，ｍｙ）を算出し、照合済特徴点リストＭＬＩＳＴに追加する。一方、照合処理部１１４は、総合一致度Ｓ１が閾値ＴＨ未満のときは、一致性が低く特徴点として信頼性が低いので、ｉ番目の特徴点は追跡失敗とみなし、照合済特徴点リストＭＬＩＳＴに追加しない。
【００６５】
照合処理部１１４は、総合一致度Ｓ２の算出において、小領域内での各位置での一致度を求める際に、輝度の一致度ｖ及びコーナーらしさｃを求める。輝度の一致度ｖ及びコーナーらしさｃは、次のように求められる。
【数７】
2015095179.tif 000009
ここで、（ｊ１，ｉ１）は１時刻前の追跡特徴点（Ｐｘｉ，Ｐｙｉ）を中心として小領域を設けた場合の小領域内での位置を表す。（ｊ２，ｉ２）は、現時刻の探索走査における同小領域内での位置を表す。（ｓｘ，ｓｙ）は、現時刻の探索走査の中心位置を表す。また、Ａは、所定の正の定数である。Ｉ１（ｘ，ｙ）は、１時刻前の画像Ｉ１における座標（ｘ，ｙ）の輝度値である。Ｉ２（ｘ，ｙ）は、現時刻の画像Ｉ２における座標（ｘ，ｙ）の輝度値である。
【００６６】
具体的には、照合処理部１１４は、次のように処理する。
【００６７】
ステップＳ１１０６では、照合処理部１１４は、ｓｙがｑｙ＋Ｍｙ以下であるか否かを判定する。ｓｙがｑｙ＋Ｍｙを超えると、座標（ｓｘ，ｓｙ）は探索範囲外である。ｓｙがｑｙ＋Ｍｙを超えている場合（Ｓ１１０６；ＮＯ）、処理がステップＳ１１２２に進む。ｓｙがｑｙ＋Ｍｙ以下である場合（Ｓ１１０６；ＹＥＳ）、処理がステップＳ１１０７に進む。ステップＳ１１０７では、照合処理部１１４は、ｓｘにｑｘ−Ｍｘを代入する。
【００６８】
ステップＳ１１０８では、照合処理部１１４は、ｓｘがｑｘ＋Ｍｘ以下であるか否かを判定する。ｓｘがｑｙ＋Ｍｘを超えると、座標（ｓｘ，ｓｙ）は探索範囲外である。ｓｘがｑｘ＋Ｍｘを超えている場合（Ｓ１１０８；ＮＯ）、処理がステップＳ１１２１に進む。ｓｘがｑｘ＋Ｍｘ以下である場合（Ｓ１１０８；ＹＥＳ）、処理がステップＳ１１０９に進む。
【００６９】
ステップＳ１１０９では、照合処理部１１４は、Ｓ１に０、Ｓ２に０を代入する。ステップＳ１１１０では、照合処理部１１４は、ｉ１にＰｙｉ−Ｒ、ｉ２にｓｙ−Ｒを代入する。ステップＳ１１１１では、照合処理部１１４は、ｉ１がＰｙｉ＋Ｒ以下であるか否かを判定する。ｉ１がＰｙｉ＋Ｒより大きい場合（Ｓ１１１１；ＮＯ）、処理がＳ１１１８
に進む。ｉ１がＰｙｉ＋Ｒ以下である場合（Ｓ１１１１；ＹＥＳ）、処理がＳ１１１２に進む。
【００７０】
ステップＳ１１１２では、照合処理部１１４は、ｊ１にＰｘｉ−Ｒ、ｊ２にｓｘ−Ｒを代入する。
【００７１】
ステップＳ１１１３では、照合処理部１１４は、ｊ１がＰｘｉ＋Ｒ以下であるか否かを判定する。ｊ１がＰｘｉ＋Ｒより大きい場合（Ｓ１１１３；ＮＯ）、処理がＳ１１１７に進む。ｊ１がＰｘｉ＋Ｒ以下である場合（Ｓ１１１３；ＹＥＳ）、処理がＳ１１１４に進む。
【００７２】
ステップＳ１１１４では、照合処理部１１４は、ｖにＡ−｜Ｉ１（ｊ１，ｉ１）−Ｉ２（ｊ２，ｉ２）｜、ｃにＣ（ｓｘ，ｓｙ）を代入する。ｖは、輝度の一致度である。ｖが大きいほど輝度の一致度が高い。ｃは、コーナーらしさである。
【００７３】
ステップＳ１１１５では、照合処理部１１４は、Ｓ１にＳ１＋ｖ、Ｓ２にＳ２＋ｖ×ｃを代入する。ステップＳ１１１６では、照合処理部１１４は、ｊ１にｊ１＋１、ｊ２にｊ２＋１を代入し、処理がステップＳ１１１３に戻る。
【００７４】
ステップＳ１１１７では、照合処理部１１４は、ｉ１にｉ１＋１、ｉ２にｉ２＋１を代入し、処理がＳ１１１１に戻る。
【００７５】
ステップＳ１１１８では、照合処理部１１４は、Ｓ２がＳ２ｍａｘを超えているか否かを判定する。Ｓ２がＳ２ｍａｘを超えていない場合（Ｓ１１１８；ＮＯ）、処理がステップＳ１１２０に進む。Ｓ２がＳ２ｍａｘを超えている場合（Ｓ１１１８；ＹＥＳ）、処理がステップＳ１１１９に進む。
【００７６】
ステップＳ１１１９では、照合処理部１１４は、Ｓ１ｍａｘにＳ１、Ｓ２ｍａｘにＳ２を代入する。また、照合処理部１１４は、ｍｘにｓｘ、ｍｙにｓｙを代入する。
【００７７】
ステップＳ１１２０では、照合処理部１１４は、ｓｘにｓｘ＋１を代入し、処理がステップＳ１１０８に戻る。
【００７８】
ステップＳ１１２１では、照合処理部１１４は、ｓｙにｓｙ＋１を代入し、処理がステップＳ１１０６に戻る。
【００７９】
ステップＳ１１２２では、照合処理部１１４は、Ｓ１ｍａｘが所定の閾値ＴＨを超えているか否かを判定する。Ｓ１ｍａｘが所定の閾値を超えていない場合（Ｓ１１２２；ＮＯ）、処理がステップＳ１１２４に進む。この場合、ｉ番目の特徴点は追跡失敗とみなされ、照合済特徴点リストＭＬＩＳＴに追加されない。Ｓ１ｍａｘが所定の閾値を超えている場合（Ｓ１１２２；ＹＥＳ）、処理がステップＳ１１２３に進む。
【００８０】
ステップＳ１１２３では、照合処理部１１４は、ｉ番目の追跡特徴点の座標（ｍｘ，ｍｙ）を、照合済み特徴点リストＭＬＩＳＴに追加する。ＮＭは、当該特徴点に付けられる新たな番号である。照合処理部１１４は、ＮＭにＮＭ＋１を代入し、処理がステップＳ１１２４に進む。
【００８１】
ステップＳ１１２４では、照合処理部１１４は、ｉにｉ＋１を代入し、処理がステップＳ１１０２に戻る。
【００８２】
図１３は、１時刻前の画像Ｉ１及び現時刻での画像Ｉ２の例を示す図である。図１３の１時刻前の画像Ｉ１は、１時刻前の追跡特徴点（Ｐｘｉ，Ｐｙｉ）を中心として、幅２Ｒ高さ２Ｒの照合の小領域を有する。図１３の現時刻の画像Ｉ２は、予測位置（ｑｘ，ｑｙ）を中心として、幅２Ｍｘ高さ２Ｍｙの探索範囲を含む。また、図１３の現時刻の画像Ｉ２は、探索範囲の一部を含む幅２Ｒ高さ２Ｒの照合の小領域を有する。
【００８３】
特徴点追加削除部１１０は、時系列での照合済み特徴点リストＭＬＩＳＴ（特徴点数ＮＭ）、現時刻での新規特徴点リストＮＬＩＳＴ（特徴点数ＮＮ）を入力として、特徴点の追加および削除を行う。
【００８４】
図１４は、特徴点追加削除部の動作フローの例を示す図である。特徴点追加削除部１１０は、特徴点の削除処理を行い（Ｓ１２０１）、特徴点の追加処理を行う（Ｓ１２０２）。
【００８５】
次に、特徴点追加削除部１１０における特徴点の削除処理について説明する。
【００８６】
図１５、図１６、図１７は、特徴点追加削除部における特徴点の削除処理の動作フローの例を示す図である。図１５の「Ｅ１」、「Ｅ２」、「Ｅ３」、「Ｅ４」は、それぞれ、図１６の「Ｅ１」、「Ｅ２」、「Ｅ３」、「Ｅ４」と接続する。図１６の「Ｆ１」、「Ｆ２」、「Ｆ３」、「Ｆ４」、「Ｆ５」、「Ｆ６」、「Ｆ７」は、それぞれ、図１７の「Ｆ１」、「Ｆ２」、「Ｆ３」、「Ｆ４」、「Ｆ５」、「Ｆ６」、「Ｆ７」と接続する。
【００８７】
ステップＳ１３０１では、特徴点追加削除部１１０は、ｉに０、ＮＦに０を代入する。
【００８８】
ステップＳ１３０２では、特徴点追加削除部１１０は、ｉがＮＭ未満であるか否かを判定する。ｉがＮＭ以上である場合（Ｓ１３０２；ＮＯ）、処理が終了する。ｉがＮＭ未満である場合（Ｓ１３０２；ＹＥＳ）、処理がステップＳ１３０３に進む。
【００８９】
ステップＳ１３０３では、特徴点追加削除部１１０は、特徴点ＤＢ１１２のＭＬＩＳＴからｉ番目の照合特徴点の座標を取得し、（Ｐｘｉ，Ｐｙｉ）とする。
【００９０】
ステップＳ１３０４では、特徴点追加削除部１１０は、Ｐｘｉが０未満、かつ、Ｐｙｉが０未満であるか否かを判定する。Ｐｘｉが０未満、かつ、Ｐｙｉが０未満である場合（Ｓ１３０４；ＹＥＳ）、処理がステップＳ１３１４に進む。Ｐｘｉが０以上、または、Ｐｙｉが０以上である場合（Ｓ１３０４；ＮＯ）、処理がステップＳ１３０５に進む。Ｐｘｉが０未満、かつ、Ｐｙｉが０未満であることは、当該座標で示される特徴点が無効点であることを示す。
【００９１】
ステップＳ１３０５では、特徴点追加削除部１１０は、ｊにｉ＋１を代入する。
【００９２】
スッテプＳ１３０６では、特徴点追加削除部１１０は、ｊがＮＭ未満であるか否かを判定する。ｊがＮＭ未満でない場合（Ｓ１３０６；ＮＯ）、処理がステップＳ１３１３に進む。ｊがＮＭ未満である場合（Ｓ１３０６；ＹＥＳ）、処理がステップＳ１３０７に進む。
【００９３】
ステップＳ１３０７では、特徴点追加削除部１１０は、特徴点ＤＢ１１２のＭＬＩＳＴからｊ番目の照合特徴点の座標を取得し、（Ｐｘｊ，Ｐｙｊ）とする。
【００９４】
ステップＳ１３０８では、特徴点追加削除部１１０は、Ｐｘｊが０未満、かつ、Ｐｙｊが０未満であるか否かを判定する。Ｐｘｊが０未満、かつ、Ｐｙｊが０未満である場合（
Ｓ１３０８；ＹＥＳ）、処理がステップＳ１３１２に進む。Ｐｘｊが０以上、または、Ｐｙｊが０以上である場合（Ｓ１３０８；ＮＯ）、処理がステップＳ１３０９に進む。Ｐｘｊが０未満、かつ、Ｐｙｊが０未満であることは、当該座標で示される特徴点が無効点であることを示す。
【００９５】
ステップＳ１３０９では、特徴点追加削除部１１０は、ｉ番目の照合特徴点とｊ番目の照合特徴点との距離Ｌを算出する。距離Ｌは次のように求められる。
【数８】
2015095179.tif 000010
ステップＳ１３１０では、特徴点追加削除部１１０は、ステップＳ１３０９で求めた距離Ｌが所定の閾値ＴＨ＿Ｌ未満であるか否かを判定する。距離Ｌが閾値ＴＨ＿Ｌ以上である場合（Ｓ１３１０；ＮＯ）、処理がステップＳ１３１２に進む。距離Ｌが閾値ＴＨ＿Ｌ未満である場合（Ｓ１３１０；ＹＥＳ）、処理がステップＳ１３１１に進む。
【００９６】
ステップＳ１３１１では、特徴点追加削除部１１０は、ｊ番目の照合特徴点を無効値に設定する。具体的には、特徴点追加削除部１１０は、ＭＬＩＳＴのｊ番目の点の座標を無効値である（−１，−１）に設定する。このように設定された当該ｊ番目の特徴点は、無効点となる。
【００９７】
ステップＳ１３１２では、特徴点追加削除部１１０は、ｊにｊ＋１を代入し、処理がステップＳ１３０６に戻る。
【００９８】
ステップＳ１３１３では、特徴点追加削除部１１０は、ｉ番目の照合特徴点をＦＬＩＳＴに追加する。具体的には、特徴点追加削除部１１０は、ＦＬＩＳＴのＮＦ番目の特徴点として座標（Ｐｘｉ，Ｐｙｉ）を追加する。また、特徴点追加削除部１１０は、ＮＦにＮＦ＋１を代入する。
【００９９】
ステップＳ１３１４では、特徴点追加削除部１１０は、ｉにｉ＋１を代入して、処理がステップＳ１３０２に戻る。
【０１００】
図１５、図１６、図１７の削除処理によって、特徴点追加削除部１１０は、追跡によって正しく照合された特徴点の中で、すべての他の特徴点との間の距離が閾値ＴＨ＿Ｌ以上離れたものについて、最終的に追跡特徴点リストＦＬＩＳＴに登録する（特徴点数ＮＦ）。
【０１０１】
次に、特徴点追加削除部１１０における特徴点の追加処理について説明する。
【０１０２】
図１８、図１９、図２０は、特徴点追加削除部における特徴点の追加処理の動作フローの例を示す図である。図１８の「Ｇ１」、「Ｇ２」、「Ｇ３」、「Ｇ４」、「Ｇ５」は、それぞれ、図１９の「Ｇ１」、「Ｇ２」、「Ｇ３」、「Ｇ４」、「Ｇ５」と接続する。図１９の「Ｈ１」、「Ｈ２」、「Ｈ３」、「Ｈ４」は、それぞれ、図２０の「Ｈ１」、「Ｈ２」、「Ｈ３」、「Ｈ４」と接続する。
【０１０３】
ステップＳ１４０１では、特徴点追加削除部１１０は、ｉに０を代入する。
【０１０４】
ステップＳ１４０２では、特徴点追加削除部１１０は、ｉがＮＮ未満であるか否かを判定する。ｉがＮＮ以上である場合（Ｓ１４０２；ＮＯ）、処理が終了する。ｉがＮＮ未満
である場合（Ｓ１４０２；ＹＥＳ）、処理がステップＳ１４０３に進む。
【０１０５】
ステップＳ１４０３では、特徴点追加削除部１１０は、ＮＬＩＳＴからｉ番目の新規特徴点の座標を取得し、（Ｐｘｉ，Ｐｙｉ）とする。
【０１０６】
ステップＳ１４０４では、特徴点追加削除部１１０は、ｊに０を代入する。
【０１０７】
ステップＳ１４０５では、特徴点追加削除部１１０は、ｊがＮＦ未満であるか否かを判定する。ｊがＮＦ以上である場合（Ｓ１４０５；ＮＯ）、処理がステップＳ１４１０に進む。ｊがＮＦ未満である場合（Ｓ１４０５；ＹＥＳ）、処理がステップＳ１４０６に進む。
【０１０８】
ステップＳ１４０６では、特徴点追加削除部１１０は、ＦＬＩＳＴからｊ番目の追跡特徴点の座標を取得し、（Ｐｘｊ，Ｐｙｊ）とする。
【０１０９】
ステップＳ１４０７では、特徴点追加削除部１１０は、ｉ番目の新規点とｊ番目の追跡特徴点との距離Ｌを算出する。距離Ｌは次のように求められる。
【数９】
2015095179.tif 000011
ステップＳ１４０８では、特徴点追加削除部１１０は、ステップＳ１４０８で求めた距離Ｌが所定の閾値ＴＨ＿Ｌ未満であるか否かを判定する。距離Ｌが閾値ＴＨ＿Ｌ以上である場合（Ｓ１４０８；ＮＯ）、処理がステップＳ１４１１に進む。距離Ｌが閾値ＴＨ＿Ｌ未満である場合（Ｓ１４０８；ＹＥＳ）、処理がステップＳ１４０９に進む。
【０１１０】
ステップＳ１４０９では、特徴点追加削除部１１０は、ｊにｊ＋１を代入して、処理がステップＳ１４０５に戻る。
【０１１１】
ステップＳ１４１０では、特徴点追加削除部１１０は、ｉ番目の新規特徴点を追跡特徴点リストＦＬＩＳＴに追加する。具体的には、特徴点追加削除部１１０は、ＮＦ番目の特徴点として、座標（Ｐｘｉ，Ｐｙｉ）をＦＬＩＳＴに登録する。また、特徴点追加削除部１１０は、ＮＦにＮＦ＋１を代入する。
【０１１２】
ステップＳ１４１１では、特徴点追加削除部１１０は、ｉにｉ＋１を代入して、処理がステップＳ１４０２に戻る。
【０１１３】
図１８、図１９、図２０の追加処理によって、特徴点追加削除部１１０は、ＮＬＩＳＴに含まれる新規特徴点の中で、すべての他の特徴点（ＦＬＩＳＴに含まれる特徴点）との間の距離が閾値ＴＨ＿Ｌ以上離れたものについて、追跡特徴点リストＦＬＩＳＴに登録する。
【０１１４】
（実施形態１の作用、効果）
特徴点追跡装置１００は、時系列で入力される画像からコーナー度を算出し、コーナー点を検出する。特徴点追跡装置１００は、小領域の画像（輝度）の一致度と小領域の中心点のコーナー度とに基づいて総合一致度を算出し、特徴点を追跡する。特徴点追跡装置１００は、小領域の輝度の一致度が高く、かつ、小領域の中心点のコーナー度が高い小領域の中心点を、追跡特徴点とすることで、特徴点を追跡する。
【０１１５】
コーナーらしさｃは、コーナー度分布Ｃ（ｘ，ｙ）を用いて、設定した小領域の中心位置（ｓｘ，ｓｙ）に対して求めてられており、小領域内でのコーナー度の分布形状を用いていない。ある点のコーナー度の値は、当該ある点の周囲の縦横それぞれの微分パターンを評価して求めるので、対象の映り方の変化に対して敏感である。コーナー度分布のある位置に小領域を設けた場合、対象の移動によってその小領域内のコーナー度の分布パターンは大きく変化する。そのため、小領域内のすべての点のコーナー度を反映させると、例え、輝度の一致度が大きくても、コーナー度が小さくなり総合一致度Ｓ２が低下する。
【０１１６】
一方、コーナー度は、周辺のコーナー度分布のパターン形状は異なっても、各位置での値は定性的にコーナーらしさを評価する指標として意味があるものである。そこで、照合処理部１１４は、探索範囲内の走査で着目している中心位置（ｓｘ，ｓｙ）でのコーナーらしさ（＝元のコーナー特徴としての度合い）を用いて総合一致度Ｓ２を算出する。これによって、特徴点追跡装置１００は、周囲のコーナー度分布の形状の変化が大きくとも、コーナーとしての特性を維持しつつ映像パターンとして最も一致する箇所を定めることをでき、時系列での追跡においても位置ずれを抑えた追跡することをできる。
【０１１７】
特徴点追跡装置１００によれば、移動体に取り付けたカメラ等で撮影した映像から特徴点を検出し時系列映像から特徴点の位置を追跡する場合、時系列的な見え方の変化に追従しつつ、追跡する特徴点の位置のずれを抑えて、長時間に渡るより正確な追跡を実現できる。
【０１１８】
〔実施形態２〕
次に実施形態２について説明する。実施形態２は、実施形態１との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。
【０１１９】
（構成例）
図２１は、本実施形態の特徴点追跡装置の構成例を示す図である。特徴点追跡装置２００は、映像入力部２０２、映像ＤＢ２０４、コーナー度算出部２０６、コーナー点検出部２０８、特徴点追加削除部２１０、特徴点ＤＢ２１２、照合処理部２１４を含む。照合処理部２１４は、仮追跡処理部２２２、真追跡処理部２２４を含む。
【０１２０】
映像入力部２０２は、カメラで撮影された外界映像を入力し所望のデジタル映像データに変換し、コーナー度算出部２０６、照合処理部２１４、および、映像ＤＢ２０４に送出する。
【０１２１】
映像ＤＢ２０４は、現時刻と１時刻前の映像データを保持する。
【０１２２】
コーナー度算出部２０６は、映像データから映像の各位置でのコーナーらしさを表すコーナー度の分布を算出しコーナー点検出部２０８および照合処理部２１４に出力する。
【０１２３】
コーナー点検出部２０８は、コーナー度分布を入力にして、コーナー点（特徴点）を抽出する。
【０１２４】
特徴点追加削除部２１０は、抽出されたコーナー点列と特徴点ＤＢ２１２に保存される時系列的な追跡点とから新規の特徴点を追加するとともに追跡不適な点を削除する。
【０１２５】
特徴点ＤＢ２１２は、時系列的に追跡する特徴点を保存する。
【０１２６】
照合処理部２１４は、仮追跡処理部２２２及び真追跡処理部２２４を含む。仮追跡処理部２２２は、１時刻前の映像と現時刻の映像とを用いて仮の追跡対応位置を算出する。真
追跡処理部２２４は、仮追跡処理部２２２で求めた仮の対応位置を中心に局所的な範囲で１時刻前の映像と現時刻の映像とコーナー度とを用いて最良一致箇所を定める。
【０１２７】
特徴点追跡装置２００は、映像中の特徴点を時系列的に追跡した追跡結果（画像中の特徴点の位置）を外部に出力する。
【０１２８】
（動作例）
図２２は、特徴点抽出装置２００の時系列での追跡処理の動作フローの例を示す図である。
【０１２９】
ステップＳ２０１では、特徴点抽出装置２００の映像入力部２０２は、外界を撮影するカメラ等から映像を取得し、デジタル映像に変換して映像ＤＢ２０４に現時刻の映像を登録するとともに、デジタル映像を次ステップ処理に出力する。
【０１３０】
ステップＳ２０２では、コーナー度算出部２０６は、現時刻のデジタル映像から映像中の各位置でコーナーらしさを表すコーナー度を算出し、コーナー度分布を生成する。生成されたコーナー度分布は、コーナー点検出部２０８および照合処理部２１４に送られる。
【０１３１】
ステップＳ２０３では、コーナー点検出部２０８は、コーナー度分布を用いてコーナー度が局所的に極大となる箇所を特定し、特定した箇所をコーナー点として次段処理に送る。
【０１３２】
ステップＳ２０４では、照合処理部２１４の仮追跡処理部２２２は、映像情報として現時刻の入力映像と映像ＤＢ１０４に保持する１時刻前の映像と、特徴点ＤＢ２１２に保持される１時刻前までの追跡特徴点情報とを取得する。仮追跡処理部２２２は、取得した情報を用いて、映像情報の類似性に基づき１時刻前の追跡特徴点に対する現時刻での仮の対応位置を算出する。
【０１３３】
ステップＳ２０５では、照合処理部２１４の真追跡処理部２２４は、仮の対応位置を中心とした局所的な探索を行う。真追跡処理部２２４は、局所的な探索によって、映像情報の類似性に加えて前段処理で求まったコーナー度分布から得られるコーナー度を加味した総合類似性に基づき１時刻前の追跡特徴点に対する現時刻での真の対応位置を算出する。真追跡処理部２２４は、装置出力として装置外に追跡位置（画像の座標値）を出力するとともに、後段処理に追跡結果を出力する。
【０１３４】
ステップＳ２０３と、ステップＳ２０４及びステップＳ２０５とは、並列に実行されても、ステップＳ２０４及びステップＳ２０５が先に実行されてもよい。
【０１３５】
ステップＳ２０６では、特徴点追加削除部２１０は、ステップＳ２０３で得られた現時刻で得られた特徴点列と、ステップＳ２０４及びステップＳ２０５で得られた現時刻での追跡特徴点列を受信する。特徴点追加削除部２１０は、これらの特徴点列および追跡特徴点列を入力として、新規特徴点の追加と追跡不要な特徴点の削除を行うことで特徴点ＤＢ２１２を更新し、次時刻での照合処理の準備を行う。
【０１３６】
ステップＳ２０７では、特徴点抽出装置２００は、映像の入力が終了したか否かを判定する。映像の入力が終了した場合（Ｓ２０７；ＹＥＳ）、処理が終了する。映像の入力が終了していない場合（Ｓ２０７；ＮＯ）、処理がステップＳ２０１に戻って、繰り返される。
【０１３７】
次に、図２２の動作フローの各処理について、詳細に説明する。
【０１３８】
映像入力部２０２における映像入力・ＤＢ登録処理は、実施形態１の映像入力部１０２における映像入力・ＤＢ登録処理と同様である。コーナー度算出部２０６におけるコーナー度算出処理は、実施形態１のコーナー度算出部１０６におけるコーナー度算出処理と同様である。コーナー点検出部２０８におけるコーナー点検出処理は、実施形態１のコーナー点検出部１０８におけるコーナー点検出処理と同様である。
【０１３９】
照合処理部２１４は、特徴点の照合処理を行う。映像ＤＢ２０４に保存されている１時刻前の映像をＩ１（ｘ，ｙ）、現時刻の映像をＩ２（ｘ，ｙ）とする。Ｉ１及びＩ２は、例えば、映像の輝度である。また、コーナー度算出部２０６で得られた現時刻の映像に対するコーナー度の分布をＣ（ｘ，ｙ）とし、特徴点ＤＢ２１２に保存されている１時刻前までの追跡特徴点リストをＦＬＩＳＴとする。なお、ＦＬＩＳＴは、特徴点数ＮＦで、ＦＬＩＳＴ内のｉ番目の追跡特徴点を取り出す操作として、ＦＧＥＴ（ＦＬＩＳＴ，ｉ）を定義する。また、ＦＧＥＴ（ＦＬＩＳＴ，ｉ）は、ＦＬＩＳＴ内のｉ番目の追跡特徴点の画像上での座標値（Ｐｘｉ，Ｐｙｉ）を返す。また、ＦＳＥＴ（ＦＬＩＳＴ，ｉ，ｘ，ｙ）は、ＦＬＩＳＴ内のｉ番目の追跡特徴点の位置を、（ｘ，ｙ）に設定するものとする。
【０１４０】
図２３、図２４、図２５、図２６、図２７、図２８、図２９、図３０、図３１は、照合処理部２１４における照合処理の動作フローの例を示す図である。図２３の「Ｉ１」、「Ｉ２」、「Ｉ３」は、それぞれ、図２４の「Ｉ１」、「Ｉ２」、「Ｉ３」と接続する。図２４の「Ｊ１」、「Ｊ２」、「Ｊ３」、「Ｊ４」、「Ｊ５」、「Ｊ６」、「Ｊ７」は、それぞれ、図２５の「Ｊ１」、「Ｊ２」、「Ｊ３」、「Ｊ４」、「Ｊ５」、「Ｊ６」、「Ｊ７」と接続する。図２５の「Ｋ１」、「Ｋ２」、「Ｋ３」、「Ｋ４」、「Ｋ５」、「Ｋ６」、「Ｋ７」、「Ｋ８」、「Ｋ９」は、それぞれ、図２６の「Ｋ１」、「Ｋ２」、「Ｋ３」、「Ｋ４」、「Ｋ５」、「Ｋ６」、「Ｋ７」、「Ｋ８」、「Ｋ９」と接続する。図２６の「Ｌ１」、「Ｌ２」、「Ｌ３」は、それぞれ、図２７の「Ｌ１」、「Ｌ２」、「Ｌ３」と接続する。図２７の「Ｍ１」、「Ｍ２」、「Ｍ３」、「Ｍ４」、「Ｍ５」、「Ｍ６」は、それぞれ、図２８の「Ｍ１」、「Ｍ２」、「Ｍ３」、「Ｍ４」、「Ｍ５」、「Ｍ６」と接続する。図２８の「Ｎ１」、「Ｎ２」、「Ｎ３」、「Ｎ４」、「Ｎ５」、「Ｎ６」、「Ｎ７」、「Ｎ８」、「Ｎ９」、「ＮＡ」は、それぞれ、図２９の「Ｎ１」、「Ｎ２」、「Ｎ３」、「Ｎ４」、「Ｎ５」、「Ｎ６」、「Ｎ７」、「Ｎ８」、「Ｎ９」、「ＮＡ」と接続する。図２９の「Ｏ１」、「Ｏ２」、「Ｏ３」、「Ｏ４」、「Ｏ５」、「Ｏ６」、「Ｏ７」、「Ｏ８」は、それぞれ、図３０の「Ｏ１」、「Ｏ２」、「Ｏ３」、「Ｏ４」、「Ｏ５」、「Ｏ６」、「Ｏ７」、「Ｏ８」と接続する。図３０の「Ｐ１」、「Ｐ２」、「Ｐ３」、「Ｐ４」は、それぞれ、図３１の「Ｐ１」、「Ｐ２」、「Ｐ３」、「Ｐ４」と接続する。
【０１４１】
ステップＳ２１０１では、照合処理部２１４の仮追跡処理部２２２は、ｉに０を、ＮＭに０を代入する。ステップＳ２１０２では、照合処理部２１４の仮追跡処理部２２２は、ｉが特徴点数ＮＦ未満であるか否かを判定する。ここで、照合処理部２１４の仮追跡処理部２２２は、すべての追跡特徴点について探索を行ったか否かを確認する。ｉが特徴点数ＮＦ以上である（ｉが特徴点数ＮＦになった）場合（Ｓ２１０２；ＮＯ）、処理が終了する。ｉが特徴点数ＮＦ未満である場合（Ｓ２１０２；ＹＥＳ）、処理がステップＳ２１０３に進む。
【０１４２】
ステップＳ２１０３では、照合処理部２１４の仮追跡処理部２２２は、ｉ番目の追跡特徴点の座標を、ＦＬＩＳＴから取得する。ＦＬＩＳＴは、特徴点ＤＢ２１２に格納される。照合処理部２１４の仮追跡処理部２２２は、取得した追跡特徴点の座標を、（Ｐｘｉ，Ｐｙｉ）とする。ここで取得した、ｉ番目の追跡特徴点の座標（Ｐｘｉ，Ｐｙｉ）は、１時刻前の座標である。
【０１４３】
ステップＳ２１０４では、照合処理部２１４の仮追跡処理部２２２は、Ｓ１ｍａｘに−１を代入し、Ｓ２ｍａｘに−１を代入する。また、ｉ番目の特徴点（追跡特徴点）の現時刻での予測位置（ｑｘ，ｑｙ）は、ＰＲ（ｉ，Ｐｘｉ，Ｐｙｉ）で与えられるものとする。照合処理部２１４の仮追跡処理部２２２は、ＰＲ（ｉ，Ｐｘｉ，Ｐｙｉ）を算出する。ＰＲは、位置予測のための手続きを表す。予測位置（ｑｘ，ｑｙ）は、例えば、２時刻前の追跡特徴点の位置を（ｒｘ２，ｒｙ２）、１時刻前の追跡特徴点の位置を（ｒｘ１，ｒｙ１）とするとき、線形予測値としてｑｘ＝ｒｘ１＋（ｒｘ１−ｒｘ２）、ｑｙ＝ｒｙ１＋（ｒｙ１−ｒｙ２）等で与えられる。位置予測を用いない場合、ｑｘ＝Ｐｘｉ，ｑｙ＝Ｐｙｉとすればよい。
【０１４４】
ステップＳ２１０５では、照合処理部２１４の仮追跡処理部２２２は、ｓｙにｑｙ−Ｍｙを代入する。座標（ｓｘ，ｓｙ）は、探索している座標（走査位置）を表す。照合処理部２１４の仮追跡処理部２２２は、予測位置（ｑｘ，ｑｙ）を中心に、横、縦、それぞれ、Ｍｘ、Ｍｙの変動幅で現時刻の画像Ｉ２内での探索を行う。探索範囲は、予測位置（ｑｘ，ｑｙ）を中心に、横幅２Ｍｘ、縦幅２Ｍｙである。当該探索範囲は、仮追跡の探索範囲である。
【０１４５】
探索に際しては、照合処理部２１４の仮追跡処理部２２２は、仮追跡の探索範囲内を走査しながら、探索範囲内の探索（走査）位置（ｓｘ，ｓｙ）を中心に幅２Ｒ，高さ２Ｒの映像比較用の小領域を設ける。照合処理部２１４の仮追跡処理部２２２は、当該小領域と同じ大きさの小領域を１時刻前での画像Ｉ１の追跡位置（Ｐｘｉ，Ｐｙｉ）を中心に設ける。照合処理部２１４の仮追跡処理部２２２は、探索範囲内の各走査位置において、小領域内の映像一致度Ｓ１（＝定数−ＳＡＤ値）を算出する。照合処理部２１４の仮追跡処理部２２２は、仮追跡の探索範囲内を走査しながら、最大のＳ１値を与える位置を仮の追跡位置（ｍｘ，ｍｙ）として取得する。ただし、最大のＳ１が閾値ＴＨ未満のときは、一致性が低く照合として信頼性が低いので、ｉ番目の特徴点は追跡失敗とみなし、照合済特徴点リストＭＬＩＳＴに追加しない。一方、最大のＳ１が閾値ＴＨ以上の場合、一致性が十分で照合として信頼性が高いので、第２ステップの真追跡処理に移る。
【０１４６】
具体的には、照合処理部２１４の仮追跡処理部２２２は、次のように処理する。
【０１４７】
ステップＳ２１０６では、仮追跡処理部２２２は、ｓｙがｑｙ＋Ｍｙ以下であるか否かを判定する。ｓｙがｑｙ＋Ｍｙを超えると、座標（ｓｘ，ｓｙ）は探索範囲外である。ｓｙがｑｙ＋Ｍｙを超えている場合（Ｓ２１０６；ＮＯ）、処理がステップＳ２１２２に進む。ｓｙがｑｙ＋Ｍｙ以下である場合（Ｓ２１０６；ＹＥＳ）、処理がステップＳ２１０７に進む。ステップＳ２１０７では、照合処理部１１４は、ｓｘにｑｘ−Ｍｘを代入する。
【０１４８】
ステップＳ２１０８では、仮追跡処理部２２２は、ｓｘがｑｘ＋Ｍｘ以下であるか否かを判定する。ｓｘがｑｙ＋Ｍｘを超えると、座標（ｓｘ，ｓｙ）は探索範囲外である。ｓｘがｑｘ＋Ｍｘを超えている場合（Ｓ２１０８；ＮＯ）、処理がステップＳ２１２１に進む。ｓｘがｑｘ＋Ｍｘ以下である場合（Ｓ２１０８；ＹＥＳ）、処理がステップＳ２１０９に進む。
【０１４９】
ステップＳ２１０９では、仮追跡処理部２２２は、Ｓ１に０を代入する。ステップＳ２１１０では、仮追跡処理部２２２は、ｉ１にＰｙｉ−Ｒ、ｉ２にｓｙ−Ｒを代入する。ステップＳ２１１１では、仮追跡処理部２２２は、ｉ１がＰｙｉ＋Ｒ以下であるか否かを判定する。ｉ１がＰｙｉ＋Ｒより大きい場合（Ｓ２１１１；ＮＯ）、処理がＳ２１１８に進む。ｉ１がＰｙｉ＋Ｒ以下である場合（Ｓ２１１１；ＹＥＳ）、処理がＳ２１１２に進む
。
【０１５０】
ステップＳ２１１２では、仮追跡処理部２２２は、ｊ１にＰｘｉ−Ｒ、ｊ２にｓｘ−Ｒを代入する。
【０１５１】
ステップＳ２１１３では、仮追跡処理部２２２は、ｊ１がＰｘｉ＋Ｒ以下であるか否かを判定する。ｊ１がＰｘｉ＋Ｒより大きい場合（Ｓ２１１３；ＮＯ）、処理がＳ２１１７に進む。ｊ１がＰｘｉ＋Ｒ以下である場合（Ｓ２１１３；ＹＥＳ）、処理がＳ２１１４に進む。
【０１５２】
ステップＳ２１１４では、仮追跡処理部２２２は、ｖにＡ−｜Ｉ１（ｊ１，ｉ１）−Ｉ２（ｊ２，ｉ２）｜、ｃにＣ（ｓｘ，ｓｙ）を代入する。ｖは、輝度の一致度である。ｃは、コーナーらしさである。
【０１５３】
ステップＳ２１１５では、仮追跡処理部２２２は、Ｓ１にＳ１＋ｖを代入する。ステップＳ２１１６では、仮追跡処理部２２２は、ｊ１にｊ１＋１、ｊ２にｊ２＋１を代入し、処理がステップＳ２１１３に戻る。
【０１５４】
ステップＳ２１１７では、仮追跡処理部２２２は、ｉ１にｉ１＋１、ｉ２にｉ２＋１を代入し、処理がＳ２１１１に戻る。
【０１５５】
ステップＳ２１１８では、仮追跡処理部２２２は、Ｓ１がＳ１ｍａｘを超えているか否かを判定する。Ｓ１がＳ１ｍａｘを超えていない場合（Ｓ２１１８；ＮＯ）、処理がステップＳ２１２０に進む。Ｓ１がＳ１ｍａｘを超えている場合（Ｓ２１１８；ＹＥＳ）、処理がステップＳ２１１９に進む。
【０１５６】
ステップＳ２１１９では、仮追跡処理部２２２は、Ｓ１ｍａｘにＳ１を代入する。また、仮追跡処理部２２２は、ｍｘにｓｘ、ｍｙにｓｙを代入する。
【０１５７】
ステップＳ２１２０では、仮追跡処理部２２２は、ｓｘにｓｘ＋１を代入し、処理がステップＳ２１０８に戻る。
【０１５８】
ステップＳ２１２１では、仮追跡処理部２２２は、ｓｙにｓｙ＋１を代入し、処理がステップＳ２１０６に戻る。
【０１５９】
ステップＳ２１２２では、仮追跡処理部２２２は、Ｓ１ｍａｘが所定の閾値ＴＨを超えているか否かを判定する。Ｓ１ｍａｘが所定の閾値を超えていない場合（Ｓ２１２２；ＮＯ）、処理がステップＳ２１４２に進む。この場合、ｉ番目の特徴点は追跡失敗とみなされ、照合済特徴点リストＭＬＩＳＴに追加されない。Ｓ１ｍａｘが所定の閾値を超えている場合（Ｓ２１２２；ＹＥＳ）、処理がステップＳ２１２３に進む。
【０１６０】
ステップＳ２１２３以降は、照合処理部２１４の真追跡処理部２２４による真追跡処理である。真追跡処理では、真追跡処理部２２４は、仮の追跡位置（仮追跡点）（ｍｘ，ｍｙ）を中心に縦横それぞれにＬｘ，Ｌｙの変動幅（真追跡の探索範囲）で現時刻の画像Ｉ２内での探索を行う。ただし、仮の追跡位置（仮追跡点）の近傍が探索されれば十分であるので、Ｌｘ，Ｌｙは、Ｍｘ，Ｍｙに比べて小さい値となる。例えば、Ｌｘ＝Ｌｙ＝１とすることができる。探索に際しては、真追跡処理部２２４は、先の真追跡の探索範囲内を走査しながら、その位置を中心に幅２Ｒ，高さ２Ｒの映像比較用の小領域を設ける。真追跡処理部２２４は、当該小領域と同じ大きさの小領域を１時刻前での画像Ｉ１の追跡位置（Ｐｘｉ，Ｐｙｉ）を中心に設ける。真追跡処理部２２４は、探索範囲内の各走査位置に
おいて、小領域内の映像一致度Ｓ１（＝定数−ＳＡＤ値）に小領域の中心位置におけるコーナー度Ｃを掛けたものの総和Ｓ２（総合一致度）を算出する。真追跡処理部２２４は、先の真追跡の探索範囲内を走査しながら、最大のＳ２値を与える位置を真の追跡位置（ｔｘ，ｔｙ）として取得する。
【０１６１】
真追跡処理部２２４は、総合一致度Ｓ２の算出において、小領域内での各位置での一致度を求める際に、輝度の一致度ｖ及びコーナーらしさｃを求める。輝度の一致度ｖ及びコーナーらしさｃは、次のように求められる。
【数１０】
2015095179.tif 000012
ここで、（ｊ１，ｉ１）は１時刻前の追跡特徴点（Ｐｘｉ，Ｐｙｉ）を中心として小領域を設けた場合の小領域内での位置を表す。（ｊ２，ｉ２）は、現時刻の探索走査における同小領域内での位置を表す。（ｓｘ，ｓｙ）は、現時刻の探索走査の中心位置を表す。また、Ａは、所定の正の定数である。Ｉ１（ｘ，ｙ）は、１時刻前の画像Ｉ１における座標（ｘ，ｙ）の輝度値である。Ｉ２（ｘ，ｙ）は、現時刻の画像Ｉ２における座標（ｘ，ｙ）の輝度値である。
【０１６２】
具体的には、照合処理部２１４の真追跡処理部２２４は、次のように処理する。
【０１６３】
ステップＳ２１２３では、真追跡処理部２２４は、Ｓ２ｍａｘに−１を代入する。ステップＳ２１２４では、真追跡処理部２２４は、ｓｙにｍｙ−Ｌｙを代入する。
【０１６４】
ステップＳ２１２５では、真追跡処理部２２４は、ｓｙがｍｙ＋Ｌｙ以下であるか否かを判定する。ｓｙがｍｙ＋Ｌｙを超えると、座標（ｓｘ，ｓｙ）は探索範囲外である。ｓｙがｍｙ＋Ｌｙを超えている場合（Ｓ２１２５；ＮＯ）、処理がステップＳ２１４１に進む。ｓｙがｍｙ＋Ｌｙ以下である場合（Ｓ２１２５；ＹＥＳ）、処理がステップＳ２１２６に進む。ステップＳ２１２６では、照合処理部１１４は、ｓｘにｍｘ−Ｌｘを代入する。
【０１６５】
ステップＳ２１２７では、真追跡処理部２２４は、ｓｘがｍｘ＋Ｌｘ以下であるか否かを判定する。ｓｘがｍｙ＋Ｌｘを超えると、座標（ｓｘ，ｓｙ）は探索範囲外である。ｓｘがｍｘ＋Ｌｘを超えている場合（Ｓ２１２７；ＮＯ）、処理がステップＳ２１４０に進む。ｓｘがｍｘ＋Ｌｘ以下である場合（Ｓ２１２７；ＹＥＳ）、処理がステップＳ２１２８に進む。
【０１６６】
ステップＳ２１２８では、真追跡処理部２２４は、Ｓ２に０を代入する。ステップＳ２１２９では、真追跡処理部２２４は、ｉ１にＰｙｉ−Ｒ、ｉ２にｓｙ−Ｒを代入する。ステップＳ２１３０では、真追跡処理部２２４は、ｉ１がＰｙｉ＋Ｒ以下であるか否かを判定する。ｉ１がＰｙｉ＋Ｒより大きい場合（Ｓ２１３０；ＮＯ）、処理がＳ２１３７に進む。ｉ１がＰｙｉ＋Ｒ以下である場合（Ｓ２１３０；ＹＥＳ）、処理がＳ２１３１に進む。
【０１６７】
ステップＳ２１３１では、真追跡処理部２２４は、ｊ１にＰｘｉ−Ｒ、ｊ２にｓｘ−Ｒを代入する。
【０１６８】
ステップＳ２１３２では、真追跡処理部２２４は、ｊ１がＰｘｉ＋Ｒ以下であるか否か
を判定する。ｊ１がＰｘｉ＋Ｒより大きい場合（Ｓ２１３２；ＮＯ）、処理がＳ２１３６に進む。ｊ１がＰｘｉ＋Ｒ以下である場合（Ｓ２１３２；ＹＥＳ）、処理がＳ２１３３に進む。
【０１６９】
ステップＳ２１３３では、真追跡処理部２２４は、ｖにＡ−｜Ｉ１（ｊ１，ｉ１）−Ｉ２（ｊ２，ｉ２）｜、ｃにＣ（ｓｘ，ｓｙ）を代入する。ｖは、輝度の一致度である。ｃは、コーナーらしさである。
【０１７０】
ステップＳ２１３４では、真追跡処理部２２４は、Ｓ２にＳ２＋ｖ×ｃを代入する。ステップＳ２１３５では、真追跡処理部２２４は、ｊ１にｊ１＋１、ｊ２にｊ２＋１を代入し、処理がステップＳ２１３２に戻る。
【０１７１】
ステップＳ２１３６では、真追跡処理部２２４は、ｉ１にｉ１＋１、ｉ２にｉ２＋１を代入し、処理がＳ２１３０に戻る。
【０１７２】
ステップＳ２１３７では、真追跡処理部２２４は、Ｓ２がＳ２ｍａｘを超えているか否かを判定する。Ｓ２がＳ２ｍａｘを超えていない場合（Ｓ２１３７；ＮＯ）、処理がステップＳ２１３９に進む。Ｓ２がＳ２ｍａｘを超えている場合（Ｓ２１３７；ＹＥＳ）、処理がステップＳ２１３８に進む。
【０１７３】
ステップＳ２１３８では、真追跡処理部２２４は、Ｓ１ｍａｘにＳ１、Ｓ２ｍａｘにＳ２を代入する。また、真追跡処理部２２４は、ｔｘにｓｘ、ｔｙにｓｙを代入する。
【０１７４】
ステップＳ２１３９では、真追跡処理部２２４は、ｓｘにｓｘ＋１を代入し、処理がステップＳ２１２７に戻る。
【０１７５】
ステップＳ２１４０では、真追跡処理部２２４は、ｓｙにｓｙ＋１を代入し、処理がステップＳ２１２５に戻る。
【０１７６】
ステップＳ２１４１では、真追跡処理部２２４は、ｉ番目の追跡特徴点の座標（ｔｘ，ｔｙ）を、照合済み特徴点リストＭＬＩＳＴに追加する。ＮＭは、当該特徴点に付けられる新たな番号である。真追跡処理部２２４は、ＮＭにＮＭ＋１を代入し、処理がステップＳ２１４２に進む。
【０１７７】
ステップＳ２１４２では、真追跡処理部２２４は、ｉにｉ＋１を代入し、処理がステップＳ２１０２に戻る。
【０１７８】
図３２は、仮追跡処理における照合範囲の例を示す図である。図３２の例では、１時刻前の画像Ｉ１では、１時刻前のｉ番目の追跡位置（特徴点）（Ｐｘｉ，Ｐｙｉ）を中心とし、幅２Ｒ高さ２Ｒの領域が照合の小領域となる。現時刻の画像Ｉ２では、ｉ番目の予測位置（ｑｘ，ｑｙ）を中心として幅２Ｍｘ、高さ２Ｍｙの領域が仮追跡での探索範囲となる。また、仮追跡での探索範囲の一部を含む幅２Ｒ高さ２Ｒの領域が照合の小領域となる。
【０１７９】
図３３は、真追跡処理における照合範囲の例を示す図である。図３３の例では、１時刻前の画像Ｉ１では、１時刻前のｉ番目の追跡位置（特徴点）（Ｐｘｉ，Ｐｙｉ）を中心とし、幅２Ｒ高さ２Ｒの領域が照合の小領域となる。現時刻の画像Ｉ２では、ｉ番目の仮追跡位置（ｍｘ，ｍｙ）を中心として幅２Ｌｘ、高さ２Ｌｙの領域が真追跡での探索範囲となる。また、真追跡での探索範囲の一部を含む幅２Ｒ高さ２Ｒの領域が照合の小領域となる。現時刻の画像では、ｉ番目の予測位置（ｑｘ，ｑｙ）を中心として幅２Ｍｘ、高さ２
Ｍｙの領域が仮追跡での探索範囲となる。また、真追跡での探索範囲の一部を含む幅２Ｒ高さ２Ｒの領域が照合の小領域となる。
【０１８０】
特徴点追加削除部２１０における削除処理、追加処理は、実施形態１の特徴点追加削除部１１０における削除処理、追加処理と同様である。
【０１８１】
（実施形態２の作用、効果）
特徴点追跡装置２００は、１時刻前の画像の特徴点を中心とする小領域と、現時刻の画像の予測位置を中心とする探索範囲内の点を中心とする小領域との輝度の一致度を算出する。特徴点追跡装置２００は、輝度の一致点がもっとも大きい点を仮の追跡位置として取得する。特徴点追跡装置２００は、仮の追跡位置を中心とする所定の領域内で、総合一致度Ｓ２が最大となる点を探索し、最大となる点を追跡位置とする。即ち、特徴点追跡装置２００は、輝度の一致度を求める領域（範囲）を段階的に絞り込む。特徴点追跡装置２００は、総合一致度Ｓ２を算出する範囲を小さくすることで、計算負荷を削減することができる。
【０１８２】
〔実施形態３〕
次に実施形態３について説明する。実施形態３は、実施形態１、実施形態２との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。
【０１８３】
図３４は、実施形態３の特徴点追跡装置の構成例を示す図である。特徴点追跡装置３００は、映像入力部３０２、エッジ検出部３０３、映像ＤＢ３０４、コーナー度算出部３０６、コーナー点検出部３０８、特徴点追加削除部３１０、特徴点ＤＢ３１２、照合処理部３１４を含む。
【０１８４】
映像入力部３０２は、カメラで撮影された外界映像を入力し所望のデジタル映像データに変換し、エッジ検出部３０３に出力する。
【０１８５】
エッジ検出部３０３は、入力された画像から映像の縦および横のエッジを検出する。エッジ検出部３０３は、検出したエッジ画像を、コーナー度算出部３０６、照合処理部３１４、および、映像ＤＢ３０４に送出する。
【０１８６】
映像ＤＢ３０４は、現時刻と１時刻前のエッジ画像データを保持する。
【０１８７】
コーナー度算出部３０６は、エッジ画像データから映像の各位置でのコーナーらしさを表すコーナー度の分布を算出しコーナー点検出部３０８および照合処理部３１４に出力する。
【０１８８】
コーナー点検出部３０８は、コーナー度分布を入力にして、コーナー点（特徴点）を抽出する。
【０１８９】
特徴点追加削除部３１０は、抽出されたコーナー点列と特徴点ＤＢ３１２に保存される時系列的な追跡点とから新規の特徴点を追加するとともに追跡不適な点を削除する。
【０１９０】
特徴点ＤＢ３１２は、時系列的に追跡する特徴点を保存する。
【０１９１】
照合処理部３１４は、現時刻のエッジ画像と映像ＤＢ３０４に保持される１時刻前のエッジ画像とについて、特徴点ＤＢ３１２に保持される特徴点各々について、両エッジ画像とコーナー度分布とを用いて照合処理によって追跡を行う。
【０１９２】
特徴点追跡装置３００は、エッジ画像中の特徴点を時系列的に追跡した追跡結果（画像中の特徴点の位置）を外部に出力する。
【０１９３】
（動作例）
図３５は、特徴点抽出装置３００の時系列での追跡処理の動作フローの例を示す図である。
【０１９４】
ステップＳ３０１では、特徴点抽出装置３００の映像入力部３０２は、外界を撮影するカメラ等から映像を取得し、デジタル映像に変換して、後段に出力する。
【０１９５】
ステップＳ３０２では、エッジ検出部３０３は、入力された映像からエッジを検出して、映像ＤＢ１０４に現時刻のエッジ画像を登録するとともに、エッジ画像を次ステップ処理に出力する。
【０１９６】
ステップＳ３０３では、コーナー度算出部３０６は、現時刻のエッジ画像から映像中の各位置でコーナーらしさを表すコーナー度を算出し、コーナー度分布を生成する。生成されたコーナー度分布は、コーナー点検出部３０８および照合処理部３１４に送られる。
【０１９７】
ステップＳ３０４では、コーナー点検出部３０８は、コーナー度分布を用いてコーナー度が局所的に極大となる箇所を特定し、特定した箇所をコーナー点として次段処理に送る。
【０１９８】
ステップＳ３０５では、照合処理部３１４は、映像情報として現時刻の入力映像と映像ＤＢに保持する１時刻前の映像と、前段処理で求まったコーナー度分布と、特徴点ＤＢ３１２に保持される１時刻前までの追跡特徴点情報を取得する。照合処理部３１４は、取得した情報を用いて、１時刻前の追跡特徴点に対する現時刻での対応する位置を算出し、装置出力として装置外に追跡位置（画像の座標値）を出力するとともに、後段処理に追跡結果を出力する。
【０１９９】
ステップＳ３０４及びステップＳ３０５は、並列に実行されても、ステップＳ３０５が先に実行されてもよい。
【０２００】
ステップＳ３０６では、特徴点追加削除部３１０は、ステップＳ３０４で得られた現時刻で得られた特徴点列と、ステップＳ３０５で得られた現時刻での追跡特徴点列を入力として、新規特徴点の追加と追跡不要な特徴点の削除を行うことで特徴点ＤＢ３１２を更新し、次時刻での照合処理の準備を行う。
【０２０１】
ステップＳ３０７では、特徴点抽出装置３００は、映像の入力が終了したか否かを判定する。映像の入力が終了した場合（Ｓ３０７；ＹＥＳ）、処理が終了する。映像の入力が終了していない場合（Ｓ３０７；ＮＯ）、処理がステップＳ３０１に戻って、繰り返される。
【０２０２】
次に、図３５の動作フローの各処理について、詳細に説明する。
【０２０３】
映像入力部３０２は、映像入力処理を行う。映像入力部３０２は、時系列的に入力される映像を、所望のデジタル形式映像（デジタル映像データ）に変換し、エッジ検出部３０３に出力する。
【０２０４】
なお、所望のデジタル形式映像とは、後段のコーナー度算出に適した映像のことを指し
、たとえば、画像の各位置（画素）でモノクロの８ビットの諧調を持つ格子状の映像データなどである。
【０２０５】
エッジ検出部３０３は、入力される濃淡を示すデジタル映像から、映像の各点位置での縦方向および横方向の微分値を算出して、エッジ画像を生成し、当該エッジ画像を映像ＤＢ３０４に登録する。エッジ検出部３０３は、生成したエッジ画像を、コーナー度算出部３０６、照合処理部３１４に出力する。
【０２０６】
エッジ検出部３０３は、入力された画像内の各点について、縦方向および横方向の微分処理を行う。エッジ検出部３０３は、画像中の各画素位置を中心として、例えばＳｏｂｅｌオペレータのような縦方向と横方向のそれぞれの微分オペレータを作用させ、画素位置（ｘ，ｙ）ごとに縦方向及び横方向の微分値（それぞれｄｘ（ｘ，ｙ）、ｄｙ（ｘ，ｙ）とする）を算出する。具体的には、入力画像をＩ（ｘ，ｙ）とし、Ｓｏｂｅｌの横方向微分オペレータをｆｘ（ａ，ｂ）、縦方向微分オペレータをｆｙ（ａ，ｂ）とするとき、次の式により画像の各位置（ｘ，ｙ）での横微分値ｄｘ（ｘ，ｙ）と縦微分値ｄｙ（ｘ，ｙ）が得られる。
【数１１】
2015095179.tif 000013
【数１２】
2015095179.tif 000014
【０２０７】
横微分オペレータｆｘ（ａ，ｂ）は、例えば、図５に示されるＳｏｂｅｌの横微分オペレータと同様である。立て微分オペレータｆｙ（ａ，ｂ）は、例えば、図６に示されるＳｏｂｅｌの横微分オペレータと同様である。ｄｘ（ｘ，ｙ）、ｄｙ（ｘ，ｙ）は、映像の各画素位置での微分量であればよく、Ｓｏｂｅｌオペレータ以外のオペレータが使用されてもよい。
【０２０８】
このようにして、エッジ検出部３０３は、横微分値ｄｘ（ｘ，ｙ）を画素値として有する横微分映像Ｄｘ（横方向エッジ画像）を出力する。また、エッジ検出部３０３は、縦微分画像ｄｙ（ｘ，ｙ）を画素値として有する縦微分映像Ｄｙ（縦方向エッジ画像）を出力する。横方向エッジ画像及び縦方向エッジ画像を総称して、エッジ画像ともいう。
【０２０９】
映像ＤＢ３０４は、２つの時刻のエッジ画像データを保持する。即ち、映像ＤＢ３０４は、現時刻のエッジ画像データと１時刻前のエッジ画像データとを保持する。エッジ検出部３０３は、映像ＤＢ３０４内にあるその時点での“１時刻前”のエッジ画像データを破棄し、映像ＤＢ３０４内のその時点での“現時刻”のエッジ画像データを、映像ＤＢ３０４内の“１時刻前”のエッジ画像データに移す。さらに、エッジ検出部３０３は、現時刻で入力された新たなエッジ画像データを、映像ＤＢ３０４内の“現時刻”のエッジ画像データとして保存する。
【０２１０】
コーナー度算出部３０６は、微分値の局所積分量の算出を行う。コーナー度算出部３０６は、画像の各点（ｘ，ｙ）の位置に対して、Ｎ×Ｎの矩形領域の積分値として次の３変
量（ｇ１１，ｇ１２，ｇ１３）を算出する。コーナー度算出部３０６は、横方向エッジ画像Ｄｘの画素値ｄｘ（ｘ，ｙ）及び縦方向エッジ画像Ｄｙの画素値ｄｙ（ｘ，ｙ）を用いて、実施形態１のコーナー度算出部１０６と同様に、３変量（ｇ１１，ｇ１２，ｇ１３）を算出する。
【０２１１】
コーナー度算出部３０６は、３変量（ｇ１１，ｇ１２，ｇ１３）を用いて、画像各点（ｘ，ｙ）の位置に対して、コーナー度Ｃ（ｘ，ｙ）を、次のように、算出する。コーナー度算出部３０６は、実施形態１のコーナー度算出部１０６と同様に、コーナー度Ｃ（ｘ，ｙ）を算出する。
【０２１２】
コーナー点検出部３０８は、実施形態１のコーナ点検出部１０８と同様にして、コーナー点検出処理を行う。
【０２１３】
照合処理部３１４は、特徴点の照合処理を行う。映像ＤＢ３０４に保存されている１時刻前のエッジ画像をＤｘ１（ｘ，ｙ）及びＤｙ１（ｘ，ｙ）、現時刻のエッジ画像をＤｘ２（ｘ，ｙ）及びＤｙ２（ｘ，ｙ）とする。また、コーナー度算出部３０６で得られた現時刻のエッジ画像に対するコーナー度の分布をＣ（ｘ，ｙ）とし、特徴点ＤＢ３１２に保存されている１時刻前までの追跡特徴点リストをＦＬＩＳＴとする。なお、ＦＬＩＳＴは、特徴点数ＮＦで、ＦＬＩＳＴリスト内のｉ番目の追跡特徴点を取り出す操作として、ＦＧＥＴ（ＦＬＩＳＴ，ｉ）を定義する。また、ＦＧＥＴ（ＦＬＩＳＴ，ｉ）は、ＦＬＩＳＴリスト内のｉ番目の追跡特徴点の画像上での座標値（Ｐｘｉ，Ｐｙｉ）を返す。また、ＦＳＥＴ（ＦＬＩＳＴ，ｉ，ｘ，ｙ）は、ＦＬＩＳＴリスト内のｉ番目の追跡特徴点の位置を、（ｘ，ｙ）に設定するものとする。ここで、ＦＬＩＳＴは、ＮＬＩＳＴと同じ形式のリストである。
【０２１４】
照合処理部３１４における照合処理の動作フローは、実施形態１の照合処理部１１４における照合処理の動作フロー（図８、図９、図１０、図１１、図１２）と共通点を有する。ここでは、相違点について説明する。
【０２１５】
照合処理部３１４には、映像Ｉ１、Ｉ２の代わりに、エッジ画像Ｄｘ１、Ｄｙ１、Ｄｘ２、Ｄｙ２が入力される。また、輝度の一致度ｖの代わりにエッジ形状の一致度ｖが使用される。エッジの形状の一致度ｖは、次のように定義される。
【数１３】
2015095179.tif 000015
特徴点追加削除部３１０における削除処理、追加処理は、実施形態１の特徴点追加削除部１１０における削除処理、追加処理と同様である。
【０２１６】
（実施形態３の作用、効果）
特徴点追跡装置３００は、入力画像からエッジ画像を生成する。特徴量追跡装置３００は、エッジ画像を用いて、コーナー度算出処理、照合処理を行う。特徴点追跡装置３００は、小領域のエッジ画像の一致度と小領域の中心点のコーナー度とに基づいて総合一致度を算出し、特徴点を追跡する。特徴点追跡装置１００は、小領域のエッジ画像の一致度が高く、かつ、小領域の中心点のコーナー度が高い小領域の中心点を、追跡特徴点とすることで、特徴点を追跡する。
【０２１７】
コーナーらしさｃは、コーナー度分布Ｃ（ｘ，ｙ）を用いて、設定した小領域の中心位置（ｓｘ，ｓｙ）に対して求めてられており、小領域内でのコーナー度の分布形状を用いていない。ある点のコーナー度の値は、当該ある点の周囲の縦横それぞれの微分パターン
を評価して求めるので、対象の映り方の変化に対して敏感である。コーナー度分布のある位置に小領域を設けた場合、対象の移動によってその小領域内のコーナー度の分布パターンは大きく変化する。そのため、小領域内のすべての点のコーナー度を反映させると、例え、エッジ画像の一致度が大きくても、コーナー度が小さくなり総合一致度Ｓ２が低下する。
【０２１８】
一方、コーナー度は、周辺のコーナー度分布のパターン形状は異なっても、各位置での値は定性的にコーナーらしさを評価する指標として意味があるものである。そこで、照合処理部３１４は、探索範囲内の走査で着目している中心位置（ｓｘ，ｓｙ）でのコーナーらしさ（＝元のコーナー特徴としての度合い）を用いて総合一致度Ｓ２を算出する。これによって、特徴点追跡装置３００は、周囲のコーナー度分布の形状の変化が大きくとも、コーナーとしての特性を維持しつつエッジ画像のパターンとして最も一致する箇所を定めることをでき、時系列での追跡においても位置ずれを抑えた追跡することをできる。
【０２１９】
〔実施形態４〕
次に実施形態４について説明する。実施形態４は、実施形態１、実施形態２、実施形態３との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。
【０２２０】
（構成例）
図３６は、本実施形態の特徴点追跡装置の構成例を示す図である。特徴点追跡装置４００は、映像入力部４０２、エッジ検出部４０３、映像ＤＢ４０４、コーナー度算出部４０６、コーナー点検出部４０８、特徴点追加削除部４１０、特徴点ＤＢ４１２、照合処理部４１４を含む。
【０２２１】
映像入力部４０２は、カメラで撮影された外界映像を入力し所望のデジタル映像データに変換し、エッジ検出部４０３に出力する。
【０２２２】
エッジ検出部４０３は、入力された画像から映像の縦および横のエッジを検出する。エッジ検出部４０３は、検出したエッジ画像を、コーナー度算出部４０６、照合処理部４１４、および、映像ＤＢ４０４に送出する。
【０２２３】
映像ＤＢ４０４は、現時刻と１時刻前のエッジ画像データを保持する。
【０２２４】
コーナー度算出部４０６は、エッジ画像データから映像の各位置でのコーナーらしさを表すコーナー度の分布を算出しコーナー点検出部４０８および照合処理部４１４に出力する。
【０２２５】
コーナー点検出部４０８は、コーナー度分布を入力にして、コーナー点（特徴点）を抽出する。
【０２２６】
特徴点追加削除部４１０は、抽出されたコーナー点列と特徴点ＤＢ４１２に保存される時系列的な追跡点とから新規の特徴点を追加するとともに追跡不適な点を削除する。
【０２２７】
特徴点ＤＢ４１２は、時系列的に追跡する特徴点を保存する。
【０２２８】
照合処理部４１４は、仮追跡処理部４２２及び真追跡処理部４２４を含む。仮追跡処理部４２２は、１時刻前の映像と現時刻の映像とを用いて仮の追跡対応位置を算出する。真追跡処理部４２４は、仮追跡処理部４２２で求めた仮の対応位置を中心に局所的な範囲で１時刻前の映像と現時刻の映像とコーナー度とを用いて最良一致箇所を定める。
【０２２９】
特徴点追跡装置４００は、エッジ画像中の特徴点を時系列的に追跡した追跡結果（画像中の特徴点の位置）を外部に出力する。
【０２３０】
（動作例）
図３７は、特徴点抽出装置４００の時系列での追跡処理の動作フローの例を示す図である。
【０２３１】
ステップＳ４０１では、特徴点抽出装置４００の映像入力部４０２は、外界を撮影するカメラ等から映像を取得し、デジタル映像に変換して、後段に出力する。
【０２３２】
ステップＳ４０２では、エッジ検出部４０３は、入力された映像からエッジを検出して、映像ＤＢ４０４に現時刻のエッジ画像を登録するとともに、エッジ画像を次ステップ処理に出力する。
【０２３３】
ステップＳ４０３では、コーナー度算出部４０６は、現時刻のエッジ画像から映像中の各位置でコーナーらしさを表すコーナー度を算出し、コーナー度分布を生成する。生成されたコーナー度分布は、コーナー点検出部４０８および照合処理部４１４に送られる。
【０２３４】
ステップＳ４０４では、コーナー点検出部４０８は、コーナー度分布を用いてコーナー度が局所的に極大となる箇所を特定し、特定した箇所をコーナー点として次段処理に送る。
【０２３５】
ステップＳ４０５では、照合処理部４１４の仮追跡処理部４２２は、映像情報として現時刻の入力映像と映像ＤＢ４０４に保持する１時刻前のエッジ画像と、特徴点ＤＢ４１２に保持される１時刻前までの追跡特徴点情報とを取得する。仮追跡処理部４２２は、取得した情報を用いて、映像情報の類似性に基づき１時刻前の追跡特徴点に対する現時刻での仮の対応位置を算出する。
【０２３６】
ステップＳ４０６では、照合処理部４１４の真追跡処理部４２４は、仮の対応位置を中心とした局所的な探索を行う。真追跡処理部４２４は、局所的な探索によって、映像情報の類似性に加えて前段処理で求まったコーナー度分布から得られるコーナー度を加味した総合類似性に基づき１時刻前の追跡特徴点に対する現時刻での真の対応位置を算出する。真追跡処理部４２４は、装置出力として装置外に追跡位置（画像の座標値）を出力するとともに、後段処理に追跡結果を出力する。
【０２３７】
ステップＳ４０４と、ステップＳ４０５及びステップＳ４０６とは、並列に実行されても、ステップＳ４０５及びステップＳ４０６が先に実行されてもよい。
【０２３８】
ステップＳ４０７では、特徴点追加削除部４１０は、ステップＳ４０４で得られた現時刻で得られた特徴点列と、ステップＳ４０５及びステップＳ４０６で得られた現時刻での追跡特徴点列を受信する。特徴点追加削除部４１０は、これらの特徴点列および追跡特徴点列を入力として、新規特徴点の追加と追跡不要な特徴点の削除を行うことで特徴点ＤＢ３１２を更新し、次時刻での照合処理の準備を行う。
【０２３９】
ステップＳ４０８では、特徴点抽出装置４００は、映像の入力が終了したか否かを判定する。映像の入力が終了した場合（Ｓ４０８；ＹＥＳ）、処理が終了する。映像の入力が終了していない場合（Ｓ４０８；ＮＯ）、処理がステップＳ４０１に戻って、繰り返される。
【０２４０】
次に、図３７の動作フローの各処理について、詳細に説明する。
【０２４１】
映像入力部４０２における映像入力処理は、実施形態３の映像入力部３０２における映像入力処理と同様である。
【０２４２】
エッジ検出部４０３におけるエッジ検出、ＤＢ登録処理は、実施形態３のエッジ検出部３０３におけるエッジ検出、ＤＢ登録処理と同様である。
【０２４３】
コーナー度算出部４０６におけるコーナー度算出処理は、実施形態３のコーナー度算出部３０６におけるコーナー度算出処理と同様である。
【０２４４】
照合処理部４１４における照合処理の動作フローは、実施形態２の照合処理部２１４における照合処理の動作フロー（図２３、図２４、図２５、図２６、図２７、図２８、図２９、図３０、図３１）と共通点を有する。ここでは、相違点について説明する。
【０２４５】
照合処理部４１４には、映像Ｉ１、Ｉ２の代わりに、エッジ画像Ｄｘ１、Ｄｙ１、Ｄｘ２、Ｄｙ２が入力される。また、輝度の一致度ｖの代わりにエッジ形状の一致度ｖが使用される。エッジの形状の一致度ｖは、次のように定義される。
【数１４】
2015095179.tif 000016
特徴点追加削除部４１０における削除処理、追加処理は、実施形態１の特徴点追加削除部１１０における削除処理、追加処理と同様である。
【０２４６】
（実施形態４の作用、効果）
特徴点追跡装置４００は、１時刻前の画像の特徴点を中心とする小領域と、現時刻の画像の予測位置を中心とする探索範囲内の点を中心とする小領域とのエッジ画像の一致度を算出する。特徴点追跡装置２００は、エッジ画像の一致点がもっとも大きい点を仮の追跡位置として取得する。特徴点追跡装置２００は、仮の追跡位置を中心とする所定の領域内で、総合一致度Ｓ２が最大となる点を探索し、最大となる点を追跡位置とする。特徴点追跡装置４００は、総合一致度Ｓ２を算出する範囲を小さくすることで、計算負荷を削減することができる。
【０２４７】
以上の各実施形態は、可能な限りこれらを組み合わせて実施され得る。
【符号の説明】
【０２４８】
１００      特徴点追跡装置
１０２        映像入力部
１０４        映像ＤＢ
１０６        コーナー度算出部
１０８        コーナー点検出部
１１０        特徴点追加削除部
１１２        特徴点ＤＢ
１１４        照合処理部
２００      特徴点追跡装置
２０２        映像入力部
２０４        映像ＤＢ
２０６        コーナー度算出部
２０８        コーナー点検出部
２１０        特徴点追加削除部
２１２        特徴点ＤＢ
２１４        照合処理部
２２２          仮追跡処理部
２２４          真追跡処理部
３００      特徴点追跡装置
３０２        映像入力部
３０３        エッジ検出部
３０４        映像ＤＢ
３０６        コーナー度算出部
３０８        コーナー点検出部
３１０        特徴点追加削除部
３１２        特徴点ＤＢ
３１４        照合処理部
４００      特徴点追跡装置
４０２        映像入力部
４０３        エッジ検出部
４０４        映像ＤＢ
４０６        コーナー度算出部
４０８        コーナー点検出部
４１０        特徴点追加削除部
４１２        特徴点ＤＢ
４１４        照合処理部
４２２          仮追跡処理部
４２４          真追跡処理部
【図２】
2015095179.tif 000017
【図３】
2015095179.tif 000018
【図４】
2015095179.tif 000019
【図５】
2015095179.tif 000020
【図６】
2015095179.tif 000021
【図７】
2015095179.tif 000022
【図８】
2015095179.tif 000023
【図９】
2015095179.tif 000024
【図１０】
2015095179.tif 000025
【図１１】
2015095179.tif 000026
【図１２】
2015095179.tif 000027
【図１３】
2015095179.tif 000028
【図１４】
2015095179.tif 000029
【図１５】
2015095179.tif 000030
【図１６】
2015095179.tif 000031
【図１７】
2015095179.tif 000032
【図１８】
2015095179.tif 000033
【図１９】
2015095179.tif 000034
【図２０】
2015095179.tif 000035
【図２１】
2015095179.tif 000036
【図２２】
2015095179.tif 000037
【図２３】
2015095179.tif 000038
【図２４】
2015095179.tif 000039
【図２５】
2015095179.tif 000040
【図２６】
2015095179.tif 000041
【図２７】
2015095179.tif 000042
【図２８】
2015095179.tif 000043
【図２９】
2015095179.tif 000044
【図３０】
2015095179.tif 000045
【図３１】
2015095179.tif 000046
【図３２】
2015095179.tif 000047
【図３３】
2015095179.tif 000048
【図３４】
2015095179.tif 000049
【図３５】
2015095179.tif 000050
【図３６】
2015095179.tif 000051
【図３７】
2015095179.tif 000052
【図１】
2015095179.tif 000053