画像一致点検出装置、画像一致点検出方法および記録媒体
【課題】簡易な処理手順で正確かつ高速に画像の一致点検出を行う画像一致点検出装置を提供する。
【解決手段】画像一致点検出装置１０は、パターン検出部１１と、パターン蓄積部１２と、特徴点抽出部１３と、一致点検出部１４とを有する。パターン蓄積部１２は、画像に含まれるパターン情報をパターン番号ごとに分類し、パターン番号と、同一のパターン番号の出現回数と、パターン番号に対応するパターン位置に関する情報とを蓄積する。特徴点抽出部１３は、画像におけるパターン番号の出現回数が１回だけであるパターン情報を特徴点パターン情報として抽出する。一致点検出部１４は、複数の画像のそれぞれについて特徴点パターン情報として抽出されたパターン情報のパターン番号が一致しているか否かを判断し、一致しているパターン番号を一致点情報として検出する。
【解決手段】画像一致点検出装置１０は、パターン検出部１１と、パターン蓄積部１２と、特徴点抽出部１３と、一致点検出部１４とを有する。パターン蓄積部１２は、画像に含まれるパターン情報をパターン番号ごとに分類し、パターン番号と、同一のパターン番号の出現回数と、パターン番号に対応するパターン位置に関する情報とを蓄積する。特徴点抽出部１３は、画像におけるパターン番号の出現回数が１回だけであるパターン情報を特徴点パターン情報として抽出する。一致点検出部１４は、複数の画像のそれぞれについて特徴点パターン情報として抽出されたパターン情報のパターン番号が一致しているか否かを判断し、一致しているパターン番号を一致点情報として検出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のビットマップ画像に含まれる画像の一致点情報を検出する画像一致点検出装置に関する。
【背景技術】
【０００２】
従来の画像一致点検出手法は、多くの画素値に対してＳＡＤ（絶対差分和：Sum Absolute Difference）などの演算を行い、画像の差分が小さくなる点を探して画像の一致を検出している（特許文献１参照）。
【０００３】
ところが、ＳＡＤでは、複数の画素値同士を直接比較する必要があり、一つの一致点を見つけ出すだけでも多くの画素値同士を比較しなければならず、演算量が膨大になるという問題がある。
【０００４】
このため、画像を縮小して解像度を下げることで比較するデータ量を減らし、徐々に解像度を上げて一致探索するような手法が考案されている（特許文献２参照）。ところが、特許文献２の手法でも、画像値同士の比較を行う必要があり、演算量を大幅に減らすのは困難である。また、周期パターンでの誤検出やノイズの問題などもあり、一致点検出の精度が低いのが現状である。さらに、カメラの傾きによる画像の回転や、カメラの前後方向の移動やズームによる拡縮までを考慮に入れようとすると、さらに比較回路が増えて演算量が増大する。
【０００５】
一方、特許文献３には、所定数の特徴点を自動抽出して、画像のカメラの揺れに起因するブレを補正する手法が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−３９４９１号公報
【特許文献２】特開平１０−１３６３０４号公報
【特許文献３】特開２００５−２９５４９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
一致点（特徴点）を数多く抽出するほど、カメラの移動やブレを正確に特定することができるが、多くの一致点を検出することは演算量を増大させてしまう。したがって、コストやサイズが増大したりして利用できる用途が限定されるか、あるいは追従できるカメラや被写体の動きの範囲を限定せざるを得ないのが現状である。
【０００８】
また、一致点を検出する処理に先だって、ノイズ除去処理や被写体の明るさの変化なども考慮に入れなければ実用にならないため、ＲＲＦ（Radical Reach Filter）などを使用するなどの工夫を行う必要があり、さらなる演算量の増加を招く。
【０００９】
本発明は、上述した課題に鑑みてなされたものであり、その目的は、簡易な処理手順で正確かつ高速に画像の一致点検出を行う画像一致点検出装置、画像一致点検出方法および記録媒体を提供することにある。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、本発明の一態様によれば、複数のビットマップ画像のそれぞれにおける複数画素からなる画素ブロックのパターン画像を、前記画素ブロック内の全画素のビット数の総和である本来の画素ビット数以下のビット数で画素ブロックの特徴を表現する数値であるパターン番号で表現し、前記画素ブロックの前記パターン番号と前記画素ブロックの位置を表すパターン位置とを組にしたパターン情報を前記画素ブロックごとに検出するパターン検出部と、
前記複数のビットマップ画像のそれぞれに含まれる前記パターン情報を前記パターン番号により分類し、前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを格納するパターン蓄積部と、
前記複数のビットマップ画像のそれぞれについて、前記パターン蓄積部に格納された情報を用いて、前記パターン番号の出現回数が１回だけの前記パターン情報を特徴点パターン情報として抽出する特徴点抽出部と、
前記複数のビットマップ画像のそれぞれについて前記特徴点パターン情報として抽出された前記パターン情報の前記パターン番号が一致しているか否かを判断し、一致している前記パターン番号を含む複数の前記パターン情報を一致点情報として検出する一致点検出部と、を備えることを特徴とする画像一致点検出装置が提供される。
【発明の効果】
【００１１】
本発明によれば簡易な処理手順で正確かつ高速に画像の一致点検出を行うことができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施形態に係る画像一致点検出装置を備えたビデオカメラの概略構成を示すブロック図。
【図２】画像一致点検出装置１０の内部構成の一例を示すブロック図。
【図３】パターン検出部１１が行う前処理の一例を示すフローチャート。
【図４】パターン番号素の検出に利用される４画素の位置の一例を示す図。
【図５】２値画像が入力された場合の前処理の一例を示すフローチャート。
【図６】画素ブロックの一例を示す図。
【図７】パターン番号生成処理の一例を示すフローチャート。
【図８】第１のパターン蓄積処理における蓄積バッファのデータ構造を示す図。
【図９】パターン蓄積部１２が行う第１のパターン蓄積処理の一例を示すフローチャート。
【図１０】図９に続くフローチャート。
【図１１】第２のパターン蓄積処理における蓄積バッファのデータ構造を示す図。
【図１２】パターン蓄積部１２が行う第２のパターン蓄積処理の一例を示すフローチャート。
【図１３】図１２に続くフローチャート。
【図１４】図１３に続くフローチャート。
【図１５】第３のパターン蓄積処理における蓄積バッファのデータ構造を示す図。
【図１６】パターン蓄積部１２が行う第３のパターン蓄積処理の一例を示すフローチャート。
【図１７】図１６に続くフローチャート。
【図１８】図１７に続くフローチャート。
【図１９】第１の特徴点抽出処理における特徴点バッファのデータ構造を示す図。
【図２０】第１の特徴点抽出処理の一例を示すフローチャート。
【図２１】第２の特徴点抽出処理の一例を示すフローチャート。
【図２２】第３の特徴点抽出処理の一例を示すフローチャート。
【図２３】パターン画像の観測確率の予測処理を行うパターン確率算出部１５を備えた画像一致点検出装置１０の内部構成の一例を示すブロック図。
【図２４】パターン番号素と観測確率との対応関係を示すテーブルの一例を示す図。
【図２５】パターン確率算出部１５が行う処理の一例を示すフローチャート。
【図２６Ａ】蓄積制御処理の一例を示すフローチャート。
【図２６Ｂ】図２６Ａに続くフローチャート。
【図２６Ｃ】図２６Ｂに続くフローチャート。
【図２６Ｄ】図２６Ｃに続くフローチャート。
【図２６Ｅ】図２６Ｄに続くフローチャート。
【図２７】一致点情報のデータ構造を示す図。
【図２８】一致点検出部１４が行う一致点検出処理の一例を示すフローチャート。
【図２９】一致点検出情報に基づく画像変換の手法を模式的に示す図。
【図３０】ＬＵＴをグラフ化した一例を示す図。
【図３１】図２９で画像変換した後の３つのコマ画像のそれぞれに重み付けを行う例を示す図。
【図３２】露出を変えながら撮影した３枚のコマ画像Ａ，Ｂ，Ｃの重み付けの一例を模式的に説明する図。
【図３３】ピント位置に合わせて重みを調整する手法を模式的に示す図。
【発明を実施するための形態】
【００１３】
以下、図面を参照しながら、本発明の実施形態について詳細に説明する。
【００１４】
（本実施形態の基本原理）
まず、本実施形態による画像一致点検出の基本原理を説明する。本実施形態によれば、複数のビットマップ画像から一致点を見つける際に、ビットマップ画像を構成する画素値同士を直接比較する必要がない。本実施形態では、各々のビットマップ画像から抽出された特徴点パターン情報のみを比較して一致点を検出する。このため、画像を構成する画素の画素値または、画素値をフィルタリング演算した結果同士を比較するのに比べて、圧倒的に少ない処理量で一致点検出を行える。
【００１５】
本実施形態の基本原理の理解を助けるために例えを紹介する。例えば、人間にリンゴが写真内の右側に写っているものと、左側に写っているものを順に見せると、瞬時にリンゴが右から左に移ったことが認識される。人間は画素の集合体であるビットマップの比較を行わずして、これを達成している。このとき、リンゴがどのにあったかという非常に少ない情報だけを覚えている。本実施形態の手法はこれに似ている。本実施形態によれば、右側にリンゴが写っている最初の写真から、リンゴの表面や輪郭だけに含まれている特徴点の相対的な大小関係を表すパターン番号とパターン位置（座標）を抽出し、左側にリンゴが写っている写真からも同様の情報を抽出する。そして、これらの２種類の情報を比較することで、同一の特徴を持つ位置を抽出して、一致点として決定する。
【００１６】
ここでもし、リンゴが大量に写っている写真を人間に見せた場合を想定すると、人間は、もはやリンゴの位置を記憶するのは得策ではないと判断し、代わりにその絵の特徴的な部分を記憶する。本実施形態による手法は、まさにこれに似た動作を行う。
【００１７】
本実施形態が特徴的なのは、複雑な画像の画素情報の相対的な大小関係をパターン番号という単なる１つの数値に置き換えてしまうユニークなパターン検出手法を採用することである。そしてもう一つの特徴は、これらの数値を画像の多くの場所から検出したのち、その画像(または検出対象領域)にたった１箇所しかないパターン番号を抽出して特徴点とする特徴点抽出手法を採用することである。複数の数値からたった１回しか現れなかった数値を抜き出すのはたやすいことである。なお、実際には、複数回現れたパターンであっても、その範囲が狭い範囲にとどまっている場合には１箇所から検出されたとみなして良い。
【００１８】
このような特徴点を抽出することは大きな意味を持つ。画像の中から、特徴的な部分のみを抜き出すことになるためである。先のリンゴの例でいえば、その画像にリンゴが１個しかなければ、リンゴの上の画素から検出されたパターン情報が抽出されることになるし、リンゴが大量に写っているならば、他の特徴的な部分が抽出されることになる。つまり、画像の絵柄に応じて自動的に見つけやすい部分が特定され、その位置を記録するということが行われ、しかもその特徴的な情報は数値（パターン番号）と座標値（パターン位置）の羅列であるため、画像データそのものを比較するのに比べて処理コストが圧倒的に少なくなる。
【００１９】
本実施形態は、特徴的な部分が自動的に特定されて抽出される仕組みを持つため、一致点検出処理を高精度で、かつ非常に少ない演算量で実現できる。
【００２０】
さらに、本実施形態の変形例として、ビットマップ画像中から検出されたパターン番号から、１箇所にしか検出されなかったパターン番号の抽出を高速化するために、良く現れるパターンを排除して蓄積する工夫を行うことも可能である。
【００２１】
本実施形態によれば、画像をたった一度スキャンするだけで、他の画像との一致点を検出するための軽量なデータ（特徴点パターン情報）を収集できる。しかも、ノイズなどの影響を受けにくいため、従来必要であったノイズ除去処理に代表される前処理を行う必要もない。さらに、周期的に同じパターンが続く部分での誤検出が自動的に防止される。このため、デジタルカメラなどに応用する場合には、処理の前段である検波ロジックにこれを組み込むことが可能になり、低コストでリアルタイムに画像の一致点検出を行うことができ、手ぶれ補正をはじめとするさまざまな機能を低コストで実現することが容易になる。
【００２２】
（本実施形態の具体的な構成および処理動作）
以下、本実施形態について、より詳細に説明する。図１は本発明の一実施形態に係る画像一致点検出装置を備えたビデオカメラの概略構成を示すブロック図である。図１のビデオカメラは、画像を撮像する撮像素子１と、撮像素子１で撮像した画像をデジタル画素データに変換するＡ／Ｄ変換器２と、デジタル画素データに対して各種画像処理を行う画像処理回路３と、画像処理後のデジタル画素データを符号化する符号化装置４とを備えている。本実施形態に係る画像一致点検出装置１０は、画像処理装置の内部に設けられている。この画像処理装置では、上述した検波処理と画像処理を行うものであり、本実施形態に係る画像一致点検出装置１０の処理は検波処理の一部として行ってもよいし、画像処理の一部として行ってもよい。
【００２３】
図２は画像一致点検出装置１０の内部構成の一例を示すブロック図である。図２の画像一致点検出装置１０は、パターン検出部１１と、パターン蓄積部１２と、特徴点抽出部１３と、一致点検出部１４とを有する。
【００２４】
パターン検出部１１は、ビットマップ画像（以下、単に画像と呼ぶ）に含まれる画素ブロックごとに、画素ブロックのパターン情報を表すパターン番号を計算して、そのパターン情報の位置（パターン位置）とともに出力する。パターン番号とは、画像中の隣接する複数画素からなる画素ブロックのパターン画像を、画素ブロック内の全画素のビット数の総和である本来の画素ビット数以下のビット数で画素ブロックの特徴を表す数値（つまり、数値が完全に一致するか不一致かの比較によって、画像の特徴の一致が検出できる性質を持つ数値）で表現したものである。パターン検出部１１が出力するパターン番号とパターン位置を組にしたものはパターン情報と呼ばれる。パターン検出部１１は、パターン情報を画素ブロックごとに検出する。
【００２５】
パターン蓄積部１２は、画像に含まれるパターン情報をパターン番号ごとに分類し、パターン番号と、同一のパターン番号の出現回数と、それぞれのパターン番号に対応するパターン位置に関する情報とを蓄積する。
【００２６】
特徴点抽出部１３は、パターン蓄積部１２に蓄積された各種情報を用いて、画像におけるパターン番号の出現回数が１回だけであるパターン情報を特徴点パターン情報として抽出する。
【００２７】
一致点検出部１４は、複数の画像のそれぞれについて特徴点パターン情報として抽出されたパターン情報のパターン番号が一致しているか否かを判断し、一致しているパターン番号を一致点情報として検出する。
【００２８】
パターン検出部１１は、まず最初に、パターン番号素を検出する前処理を行う。パターン番号素とは、注目画素を含む周囲複数画素内のエッジの配置パターンを表すビット列信号である。前処理は、入力される画像の種類によって、処理内容が異なる。まずは、カラー画像、ベイヤ画像およびモノクロ多階調画像の場合の処理について説明する。
【００２９】
図３はパターン検出部１１が行う前処理の一例を示すフローチャートである。この前処理では、まず、カラー画像の場合は、Ｒ，Ｇ，ＢまたはＣ，Ｍ，Ｙ等で表される各色の画素値から輝度値を計算してモノクロ多階調画像に変換するか、またはＲ，Ｇ，Ｂ，Ｃ，Ｍ，Ｙのうちのいずれか１つの色の画素値を抜き出してモノクロ多階調画像に変換する。
【００３０】
このとき、撮像素子１がベイヤ配列の場合は、Ｒ，ＧｉｎＲ，ＧｉｎＢ，Ｂのいずれか、あるいはＣ，Ｍ，Ｙ，Ｇのいずれかの画素値に基づいて、解像度が縦横ともに半分になったモノクロ多階調画像に変換するか、あるいはデモザイク処理を行って輝度値を計算してモノクロ多階調画像に変換してから処理を行う。
【００３１】
撮像素子１がハニカム配列の場合は、正方画素変換後、あるいは奇数ラインか偶数ラインのみを抽出してモノクロ多階調正方画素に変換してから行えばよい。
【００３２】
注目画素の画素位置をｘ，ｙとして、その画素値をp(x, y)とすると、注目画素と、右、下、斜め右下の４画素値は、p(x, y)、p(x+1, y)、p(x, y+1)、p(x+1, y+1)で表される。図４は、これら４画素の位置の一例を示す図である。これら４画素値の和は以下の（１）で表される。
Sum ＝p(x, y) + p(x+1, y) + p(x, y+1) + p(x+1, y+1) …（１）
ここで、以下の（２）〜（４）式に基づいて、ｄ、Ｔ０、Ｔ１を計算する。
d＝Sum／16 …（２）
T0＝Sum／4−d …（３）
T1＝Sum／4＋d …（４）
パターン番号素は４ビットのビット列信号であり、以下の基準でビット値が定まる。以下では、パターン番号素をn(x, y)と表す。
p(x, y)がT0以上でT1以下なら、Bit0を０、そうでなければ１とする。
p(x+1, y)がT0以上でT1以下なら、Bit1を０、そうでなければ１とする。
p(x, y+1)がT0以上でT1 以下なら、Bit2を０、そうでなければ１とする。
p(x+1, y+1)がT0以上でT1以下なら、Bit3を０、そうでなければ１とする。
【００３３】
以下、前処理の具体的な処理手順を図３を用いて順に説明する。まず、上記（１）式に従って、注目画素を含む周囲４画素の画素値の和を計算する（ステップＳ１）。次に、（２）式に従って許容度（allowance）ｄを計算する（ステップＳ２）。次に、（３）式に従って下側閾値Ｔ０を計算する（ステップＳ３）。次に、（４）式に従って上側閾値Ｔ１を計算する（ステップＳ４）。
【００３４】
次に、注目画素値p(x, y)が下側閾値T0と上側閾値T1の範囲内にあるか否かを判定する（ステップＳ５）上記範囲外の場合は、パターン番号素の最下位ビットBit0を１に設定する（ステップＳ６）。なお、パターン番号素ｎは、初期状態では０とする。
【００３５】
次に、注目画素の右隣の画素値p(x+1, y)が上記範囲内にあるか否かを判定する（ステップＳ７）。上記範囲外の場合は、パターン番号素のBit1を１に設定する（ステップＳ８）。
【００３６】
ステップＳ７で上記範囲内と判定された場合、またはステップＳ８の処理が終わった場合は、注目画素の下隣の画素値p(x, y+1)が上記範囲内にあるか否かを判定する（ステップＳ９）。上記範囲外の場合は、パターン番号素のBit2を１に設定する（ステップＳ１０）。
【００３７】
ステップＳ９で上記範囲内と判定された場合、またはステップＳ１０の処理が終わった場合は、注目画素の斜め右下の画素値p(x+1, y+1)が上記範囲内にあるか否かを判定する（ステップＳ１１）。上記範囲外の場合は、パターン番号素のBit3を１に設定する（ステップＳ１２）。以上で、図３の処理は終了する。
【００３８】
次に、パターン検出部１１に入力される画像が２値画像の場合の前処理について説明する。この前処理では、p(x, y)が０か、それ以外（通常は１）の２つの値しか取らないため、以下のようにパターン番号素n(x, y)を設定する。
p(x, y)が０ならば、Bit0を０、そうでなければ１とする。
p(x+1, y) が０ならば、Bit1を０、そうでなければ１とする。
p(x, y+1) が０ならば、Bit2を０、そうでなければ１とする。
p(x+1, y+1)が０ならば、Bit3を０、そうでなければ１とする。
【００３９】
図５は２値画像が入力された場合の前処理の一例を示すフローチャートである。まず、p(x, y)が０か否かを判定し（ステップＳ２１）、０でなければパターン番号素のBit0を１に設定する（ステップＳ２２）。なお、パターン番号素ｎは、初期状態では０とする。
【００４０】
ステップＳ２１で０と判定された場合、またはステップＳ２２の処理が終わると、p(x+1, y)が０か否かを判定し（ステップＳ２３）、０でなければパターン番号素のBit1を１に設定する（ステップＳ２４）。
【００４１】
ステップＳ２３で０と判定された場合、またはステップＳ２４の処理が終わると、p(x, y+1)が０か否かを判定し（ステップＳ２５）、０でなければパターン番号素のBit2を１に設定する（ステップＳ２６）。
【００４２】
ステップＳ２５で０と判定された場合、またはステップＳ２６の処理が終わると、p(x+1, y+1)が０か否かを判定し（ステップＳ２７）、０でなければパターン番号素のBit3を１に設定する（ステップＳ２８）。以上で、図５の処理は終了する。
【００４３】
パターン検出部１１は、図３または図５の前処理が終わると、パターン番号生成処理を行う。パターン番号生成処理では、処理対象のパターン番号素ｎ（ｘ，ｙ）を中心とする周囲３×３個のパターン番号素（以下、画素ブロック）のビットパターンの種類を表すパターン番号を生成する。
【００４４】
図６は画素ブロックの一例を示す図である。画素ブロック内の計９個のパターン番号素は、n(x-2, y-2)、n(x, y-2)、n(x+2, y-2)、n(x-2, y)、n(x, y)、n(x+2, y)、n(x-2, y+2)、n(x, y+2)、n(x+2, y+2)である。各パターン番号素は４ビットで表され、これら４ビットのパターン番号素を９個並べた計３６ビットのビット列がパターン番号となる。パターン番号は、以下の式で表される。
パターン番号＝n(x-2, y-2) ×２３２＋n(x, y-2) ×２２８＋n(x+2, y-2) ×２２４
＋n(x-2, y)×２２０＋n(x, y)×２１６＋n(x+2, y)×２１２＋n(x-2, y+2) ×２８
＋n(x, y+2) ×２４＋n(x+2, y+2) …（５）
（５）式からわかるように、パターン番号は０から２３６−１までの値を取る。
【００４５】
パターン検出部１１は、（５）式で表されるパターン番号と、このパターン番号の画素ブロックの画像中の位置を示すパターン位置とを組にしたパターン情報を生成する。このパターン情報はパターン蓄積部１２に送られる。
【００４６】
図７は上述したパターン番号生成処理の一例を示すフローチャートである。まず、(x-2, y-2)位置のパターン番号素n(x-2, y-2)をpat_idに入力する（ステップＳ３１）。次に、pat_idを左に４ビットシフトし、(x, y-2)位置のパターン番号素を加算する（ステップＳ３２）。次に、pat_idを左に４ビットシフトし、(x+2, y-2)位置のパターン番号素を加算する（ステップＳ３３）。次に、pat_idを左に４ビットシフトし、(x-2, y)位置のパターン番号素を加算する（ステップＳ３４）。次に、pat_idを左に４ビットシフトし、(x, y)位置のパターン番号素を加算する（ステップＳ３５）。次に、pat_idを左に４ビットシフトし、(x+2, y)位置のパターン番号素を加算する（ステップＳ３６）。次に、pat_idを左に４ビットシフトし、(x-2, y+2)位置のパターン番号素を加算する（ステップＳ３７）。次に、pat_idを左に４ビットシフトし、(x, y+2)位置のパターン番号素を加算する（ステップＳ３８）。次に、pat_idを左に４ビットシフトし、(x+2, y+2)位置のパターン番号素を加算する（ステップＳ３９）。
【００４７】
以上で、パターン検出部１１の処理動作の概略説明は終りであるが、一つの画素ブロックから複数種類のパターン情報を生成してもよい。この場合、複数種類の前処理部を設けて、それぞれの前処理部が互いに異なるパターン番号素を生成するようにする必要がある。
【００４８】
例えば、上述した（２）式のｄを、ｄ＝Sum／８としてパターン番号素を生成する処理を追加で行えば、同一の画像でありながら、生成されるパターン番号素を複数種類設けることができ、結果として、パターン番号も変えることができ、複数種類のパターン情報を生成することができる。
【００４９】
上述したｄを変えるということは、画像の中にエッジ情報が含まれるかどうかの判断基準を変えることであり、例えばｄを大きくすることは、エッジとみなす輝度の差のスレッショルドが大きくなるため、よりはっきりしたエッジのみがパターン番号のビットに反映されることになり、結果ノイズの影響を受けにくくなるため、ノイズの多い画像においては、一致点検出の精度の向上につながる。
【００５０】
このように、複数の許容度（閾値）ｄのそれぞれごとに、パターン番号と、同一のパターン番号の出現回数とそれぞれのパターン番号に対応するパターン位置に関する情報とを蓄積することで、どのような画像に対しても、良好な一致点検出結果が得られる。
【００５１】
例えば、ノイズが多い高感度撮影された映像の場合は、ｄを小さくすると、ノイズに反応してしまうため、ｄは大きくするのが望ましい。ところが、単にｄを大きくしただけだと、ノイズは少ないがエッジがはっきりしない画像では、エッジを正しく検出できないおそれがある。この２つの要求を満足させるためには、同一画像に対して、ｄを小さくして得られたパターン番号とｄを大きくして得られたパターン番号をともに重複しないで二種類設ければよい。例えば、ｄを小さくした場合のパターン番号を０〜２３６−１の範囲内の数値とし、ｄを大きくした場合のパターン番号を２３６〜２３７−１の範囲内の数値とする。これにより、両者のパターン番号は重複しなくなり、同一画像について、二種類の異なる基準で二種類のパターン番号を生成できる。これにより、例えばノイズの影響を受けにくくなり、かつ不鮮明なエッジでも確実に検出できるようになる。
【００５２】
上述した例では、ｄの大きさを変えることで、二種類の重複しないパターン番号を生成したが、全く異なるアルゴリズムで複数種類のパターン番号を重複しないように生成してもよい。これらの異なるアルゴリズムで生成された複数種類のパターン番号を用いて一致点検出を行うことで、個々のアルゴリズムで生成したパターン番号を用いて一致点検出を行った場合に得られる効果を組み合わせた効果が得られる。
【００５３】
上述したように、パターン検出部１１は、３×３個のパターン番号素を含む画素ブロックを単位としてパターン検出処理を行うが、各パターン番号素は周囲の４画素のエッジ情報を考慮に入れた４ビットのビット列であり、結局、本実施形態では、縦６画素×横６画素の画素ブロックを単位としてパターン検出処理を行うことになる。
【００５４】
パターン検出部１１が一つの画素ブロックの処理が終了すると、次の画素ブロックのパターン検出処理を行うことになる。この場合、画素ブロックを画素単位でずらして新たな画素ブロックを設定するのが望ましいが、処理の簡略化と高速化の観点で、画素ブロック同士が重なり合わないように新たな画素ブロックを設定してもよい。
【００５５】
ただし、画像中のある物体が１画素だけ移動した場合を考えると、１画素単位で画素ブロックをずらしながらパターン検出処理を行わないと、その物体の移動を正しく検出できなくなる。したがって、画素ブロックの設定単位を間引く場合は、ローパスフィルタ処理等の何らかの画像処理を前段に設けるのが望ましい。
【００５６】
なお、パターン番号素は必ずしも４ビットのビット列である必要はないし、周辺の計４画素以外の画素情報を用いてパターン番号素を検出してもよい。また、パターン番号を検出する単位となる画素ブロックのサイズも、必ずしも３×３画素サイズには限定されない。
【００５７】
＜第１のパターン蓄積処理＞
次に、パターン蓄積部１２の処理動作を説明する。パターン蓄積部１２は、パターン検出部１１で検出されたパターン番号の数分の蓄積バッファ（不図示）を有する。図８は第１のパターン蓄積処理における蓄積バッファのデータ構造を示す図である。蓄積バッファは、パターン番号pat_idと、パターン位置x, yと、同じパターン番号のパターン情報を蓄積した回数を示す計数値cntとを格納する。
【００５８】
個々の蓄積バッファの計数値cntは、パターン情報の蓄積を開始する前に０に初期化される。蓄積バッファにパターン情報を格納する際には、同じパターン番号のパターン情報がすでに格納されているか否かを確認する。この確認処理は、計数値cntが０か否かで判断する。すでに格納されている場合、すなわち計数値cntが０以外の場合は、計数値cntをインクリメントする。なお、本明細書では、１だけ数を増やすことを単に「インクリメントする」と呼ぶ。
【００５９】
このとき、計数値cntが０であれば、蓄積バッファ内に新たなパターン番号pat_idと、対応するパターン位置x, yを格納し、計数値cntを１にする。
【００６０】
このような処理を繰り返して、画像内のすべての画素ブロックについて、パターン情報と計数値cntを蓄積バッファに格納し終えると、パターンの蓄積処理は終了する。
【００６１】
図９および図１０はパターン蓄積部１２が行う第１のパターン蓄積処理の一例を示すフローチャートである。まず、蓄積バッファ上の位置を表す変数ｉを０に初期化する（ステップＳ４１）。次に、ｉ番目の蓄積バッファstockの計数値cntを０に初期化する（ステップＳ４２）。次に、変数ｉをインクリメントする（ステップＳ４３）。次に、変数ｉが蓄積バッファstockの総数より小さいか否かを判定する（ステップＳ４４）。小さい場合はステップＳ４２に戻って、残りの蓄積バッファstockの係数値cntを初期化する。
【００６２】
変数ｉが蓄積バッファstockの総数以上であれば、蓄積バッファstockに格納したパターン番号pat_idの総数stock_maxを０に初期化する（ステップＳ４５）。
【００６３】
次に、パターン検出部１１で検出されたパターン番号上の位置を表す変数ｊを０に初期化する（ステップＳ４６）。次に、変数ｉを再度０に初期化する（ステップＳ４７）。
【００６４】
このように、ステップＳ４１〜Ｓ４７では、全ての蓄積バッファstockの初期化を行う。
【００６５】
次に、パターン検出部１１で検出されたパターン番号pat_idがｉ番目の蓄積バッファstockのパターン番号pat_idと一致するか否かを判定する（ステップＳ４８）。一致しない場合は、次の蓄積バッファstockを検出するために、変数ｉをインクリメントする（ステップＳ４９）。
【００６６】
次に、まだ比較していない蓄積バッファstockのパターン番号pat_idが残っているか否かを判定する（ステップＳ５０）。残っている場合は、ステップＳ４８に戻る。残っていない場合は、パターン検出部１１で検出されたパターン番号pat_idを新たな蓄積バッファに蓄積バッファに格納する（ステップＳ５１）。次に、そのパターン番号pat_idに対応するパターン位置を同じ蓄積バッファに格納する（ステップＳ５２）。そして、その蓄積バッファの計数値cntを１に設定する（ステップＳ５３）。次に、蓄積バッファの総数stock_maxをインクリメントする（ステップＳ５４）。
【００６７】
一方、ステップＳ４８で、一致すると判定された場合は、蓄積バッファstockの計数値cntをインクリメントする（ステップＳ５５）。
【００６８】
ステップＳ５４またはＳ５５の処理が終わると、変数ｊをインクリメントする（ステップＳ５６）。
【００６９】
次に、パターン検出部１１で検出されたパターン番号の総数が変数ｊより大きいか否かを判定する（ステップＳ５７）。大きい場合は、ステップＳ４７以降の処理を行う。大きくない場合は、蓄積処理を終了する。
【００７０】
＜第２のパターン蓄積処理＞
上述したパターン蓄積部１２内の各蓄積バッファは図８の情報を格納したが、格納する情報は図８に限定されない。図１１は第２のパターン蓄積処理における蓄積バッファのデータ構造を示す図である。図１１の蓄積バッファは、パターン番号pat_idと、パターン位置ｘの最大値max_xと、パターン位置ｙの最大値max_yと、パターン位置ｘの最小値min_xと、パターン位置ｙの最小値min_yと、パターン位置ｘの積算値sum_xと、パターン位置ｙの積算値sum_yと、格納した回数を示す計数値cntとを有する。
【００７１】
この場合の蓄積バッファも、パターン検出部１１で検出されたパターン番号の数分だけ設けられる。蓄積バッファへの格納を開始する前に、すべての蓄積バッファの計数値cntが０に初期化される。
【００７２】
パターン蓄積部１２は、蓄積バッファにパターン情報を格納する際には、同じパターン番号のパターン情報がすでに格納されているか否かを確認し、すでに格納されている場合には、新たに格納しようとするパターン位置x, yを、累積和sum_x, sum_yにそれぞれ加算する。また、このパターン位置xが最大値max_xより大きければmax_xをｘに置き換え、パターン位置ｙが最大値max_yより大きければmax_yをｙに置き換える。同様に、パターン位置ｘが最小値min_xより小さければmin_xをｘに置き換え、パターン位置ｙが最小値min_xより小さければmin_yをｙに置き換える。さらに、計数値cntをインクリメントする。
【００７３】
一方、上記確認を行った結果、まだ格納されていない場合は、新たな蓄積バッファのpat_idに格納対象のパターン番号pat_idを格納し、sum_x, max_x, min_xのいずれにも格納対象のパターン位置ｘを格納し、sum_y, max_y, min_yのいずれにも格納対象のパターン情報ｙを格納する。さらに、計数値cntを１に設定する。
【００７４】
このようにして、画像内のすべての画素ブロックについてのパターン情報を格納し終わったら、パターン蓄積処理は終了する。
【００７５】
図１２〜図１４はパターン蓄積部１２が行う第２のパターン蓄積処理の一例を示すフローチャートである。まず、蓄積バッファ上の位置を表す変数ｉを０に初期化する（ステップＳ６１）。次に、ｉ番目の蓄積バッファstockの計数値cntを０に初期化する（ステップＳ６２）。次に、変数ｉをインクリメントする（ステップＳ６３）。次に、変数ｉが蓄積バッファstockの総数未満か否かを判定する（ステップＳ６４）。総数未満の場合はステップＳ６２に戻る。
【００７６】
ステップＳ６４で、総数に達したと判定された場合は、パターン番号の総数stock_maxを０に初期化する（ステップＳ６５）。次に、パターン検出部１１で検出されたパターン番号上の位置を示す変数ｊを０に初期化する（ステップＳ６６）。次に、変数ｉを再度０に初期化する（ステップＳ６７）。
【００７７】
次に、パターン検出部１１で検出されたパターン情報のパターン番号pat_idが蓄積バッファstockのパターン番号pat_idと一致するか否かを判定する（ステップＳ６８）。一致する場合は、パターン検出部１１で検出されたパターン位置ｘをsum_xに加算し（ステップＳ６９）、パターン位置ｙをsum_yに加算する（ステップＳ７０）。
【００７８】
次に、パターン検出部１１で検出されたパターン位置ｘはmax_xより大きいか否かを判定し（ステップＳ７１）、大きい場合にはmax_xをｘに置き換える（ステップＳ７２）。
【００７９】
次に、パターン検出部１１で検出されたパターン位置ｘはmin_xより小さいか否かを判定し（ステップＳ７３）、小さい場合にはmin_xをｘに置き換える（ステップＳ７４）。
【００８０】
次に、パターン検出部１１で検出されたパターン位置ｙはmax_yより大きいか否かを判定し（ステップＳ７５）、大きい場合にはmax_yをｙに置き換える（ステップＳ７６）。
【００８１】
次に、パターン検出部１１で検出されたパターン位置ｙはmin_yより小さいか否かを判定し（ステップＳ７７）、小さい場合にはmin_yをｙに置き換える（ステップＳ７８）。
【００８２】
次に、蓄積バッファstockの計数値cntをインクリメントする（ステップＳ７９）。次に、変数ｊをインクリメントする（ステップＳ８０）。
【００８３】
次に、パターン検出部１１で検出されたパターン番号の総数が変数ｊより大きいか否かを判定する（ステップＳ８１）。大きくなければ処理を終了し、大きければステップＳ６７以降の処理を行う。
【００８４】
一方、上述したステップＳ６８で一致しないと判定されると、変数ｉをインクリメントする（ステップＳ８２）。次に、パターン検出部１１で検出されたパターン情報のパターン番号との比較をまだ行っていない蓄積バッファが残っているか否かを判定する（ステップＳ８３）。残っている場合にはステップＳ６８以降の処理を行う。残っていない場合は、パターン検出部１１で検出されたパターン番号pat_idを蓄積バッファに格納し（ステップＳ８４）、対応するパターン位置ｘをsum_x, max_x, min_xにそれぞれ格納する（ステップＳ８５〜Ｓ８７）。また、対応するパターン位置ｙをsum_y, max_y, min_yにそれぞれ格納する（ステップＳ８８〜Ｓ９０）。次に、計数値cntを１に設定し（ステップＳ９１）、蓄積バッファの種類を示す変数stock_maxをインクリメントし（ステップＳ９２）、その後にステップＳ８０以降の処理を行う。
【００８５】
＜第３のパターン蓄積処理＞
第２のパターン蓄積処理のように、パターン位置x, yの最大値と最小値を格納する代わりに、パターン位置ｘの２乗の積算値sum_x2とパターン位置ｙの２乗の積算値sum_y2を格納してもよい。
【００８６】
図１５は第３のパターン蓄積処理における蓄積バッファのデータ構造を示す図である。図示のように、蓄積バッファは、パターン番号pat_idと、パターン位置ｘの積算値sum_xと、パターン位置ｙの積算値sum_yと、パターン位置ｘの２乗の積算値sum_x2と、パターン位置ｙの２乗の積算値sum_y2と、蓄積バッファに格納した回数を示す計数値cntとを有する。
【００８７】
パターン蓄積部１２は、蓄積バッファにすでに格納されたデータが存在する場合は、sum_x, sum_yにそれぞれパターン位置x, yを加算し、sum_x2にｘの２乗を加算し、sum_y2にｙの２乗を加算し、計数値cntをインクリメントする。
【００８８】
蓄積バッファにまだ格納されていないパターン番号の場合は、新たな蓄積バッファのパターン番号pat_idに、格納対象のパターン情報のpat_idを格納し、sum_x, sum_yに格納対象のパターン情報のパターン位置x, yをそれぞれ格納し、sum_x2, sum_y2に格納対象のパターン情報のｘの２乗とｙの２乗をそれぞれ格納し、cntを１に設定する。このようにして、画像内のすべての検出位置のパターン情報を格納し終えたら、パターン蓄積処理は終了する。
【００８９】
図１６〜図１８はパターン蓄積部１２が行う第３のパターン蓄積処理の一例を示すフローチャートである。ステップＳ１０１〜Ｓ１１０は図１２および図１３のステップＳ６１〜Ｓ７０と共通するため、説明を省略する。
【００９０】
ステップＳ１１０の処理が終わると、パターン位置ｘの２乗をsum_x2に加算する（ステップＳ１１１）。次に、パターン位置ｙの２乗をsum_y2に加算する（ステップＳ１１２）。その後、ステップＳ１１３〜Ｓ１１９は、図１３および図１４のステップＳ７９〜Ｓ８５と共通するため、説明を省略する。
【００９１】
ステップＳ１１９の処理が終わると、次に、対応するパターン位置ｙをsum_yに格納し（ステップＳ１２０）、対応するパターン位置ｘの２乗をsum_x2に格納し（ステップＳ１２１）、対応するパターン位置ｙの２乗をsum_y2に格納する（ステップＳ１２２）。その後、計数値cntを１に初期化し（ステップＳ１２３）、蓄積バッファの種類を示す変数stock_maxをインクリメントする（ステップＳ１２４）。
【００９２】
ステップＳ１２４の後にステップＳ１１４に移行する。
【００９３】
以上で、パターン蓄積部１２の処理動作の説明は終りである。次に、特徴点抽出部１３の処理動作を説明する。特徴点抽出部１３の処理動作として、以下の第１〜第３の特徴点抽出処理が考えられる。
【００９４】
＜第１の特徴点抽出処理＞
第１の特徴点抽出処理は、図８のデータ構造の蓄積バッファに対応するものであり、第１のパターン蓄積処理の後に行われる。特徴点抽出部１３は、図８のデータ構造の蓄積バッファを走査し、計数値cntが１の情報を抽出して、特徴点バッファ（不図示）に格納する。
【００９５】
図１９は第１の特徴点抽出処理における特徴点バッファのデータ構造を示す図である。図１９の特徴点バッファには、パターン番号pat_idと、パターン位置ｘと、パターン位置ｙとが格納される。
【００９６】
図２０は第１の特徴点抽出処理の一例を示すフローチャートである。まず、蓄積バッファstock上の位置を示す変数ｉと、特徴点バッファpatinfo上の位置を示す変数ｊをともに０に初期化する（ステップＳ１３１）。
【００９７】
次に、ｉ番目の蓄積バッファ内の計数値cntが１か否かを判定する（ステップＳ１３２）。１であれば、その蓄積バッファ内のパターン番号pat_idとパターン位置x, yを、特徴点バッファpatinfoに格納する（ステップＳ１３３、Ｓ１３４）。続いて、変数ｊとｉをインクリメントする（ステップＳ１３５、Ｓ１３６）。
【００９８】
次に、変数ｉが蓄積バッファの総数未満か否かを判定し（ステップＳ１３７）、総数未満であれば、ステップＳ１３２に移行し、総数に達すると処理を終わる。
【００９９】
＜第２の特徴点抽出処理＞
第２の特徴点抽出処理は、図１１のデータ構造の蓄積バッファに対応するものであり、第２のパターン蓄積処理の後に行われる。特徴点抽出部１３は、図１１のデータ構造の蓄積バッファを走査し、計数値cntが１の蓄積バッファか、あるいは以下の３つの条件を満たす蓄積バッファを抽出する。そして、抽出した蓄積バッファ内の情報を特徴点バッファに格納する。
１）計数値cntが２以上
２）最大値max_x−最小値min_x＜ｄｘ
３）最大値max_y−最小値min_y＜ｄｙの情報
【０１００】
第２の特徴点抽出処理における特徴点バッファのデータ構造は図１９と同じであるが、パターン位置ｘには、パターン位置ｘの総和sum_xを計数値cntで割った値sum_x／cntが格納され、パターン位置ｙには、パターン位置ｙの総和sum_yを計数値cntで割った値sum_y／cntが格納される。
【０１０１】
ここで、上述したｄｘ、ｄｙは、特徴点か否かを判断するための閾値である。画像中の離れた場所に同一パターンが存在する場合は、そのパターンは特徴点として機能しない可能性が高いので、排除する。一方、同一パターンが画像中の狭い範囲内しか存在しない場合は、そのパターンを特徴点とみなして、同一パターンの検出位置を平均化した位置を、そのパターン位置とする。
【０１０２】
このような処理は、焦点が合っていないぼやけた部分では、近接した位置に同一パターンが発見されることが多いことへの対応策である。
【０１０３】
複数の画像を合成する場合など、画像の一致をより厳密に行うために画像全域で一致点をなるべく多く見つけ出したい場合には、ｄｘとｄｙに例えば１〜５程度の数値を与えて実行するのが望ましい。
【０１０４】
また、手ぶれ補正など、それほど多くの一致点を検出しなくて済む場合は、ｄｘとｄｙを０に設定すれば、画像中の一箇所のみに存在した画素配置を抽出することになる。この場合は、第１の特徴点抽出処理と等価な処理となるため、処理コストの少ない第１の特徴点抽出処理を実行するのが望ましい。
【０１０５】
図２１は第２の特徴点抽出処理の一例を示すフローチャートである。まず、蓄積バッファstock上の位置を示す変数ｉと、特徴点バッファpatinfo上の位置を示す変数ｊをともに０に初期化する（ステップＳ１４１）。
【０１０６】
次に、ｉ番目の蓄積バッファstock内の計数値cntが１か、あるいは、max_x−min_x＜ｄｘかつmax_y−min_y＜ｄｙかを判定する（ステップＳ１４２）。ステップＳ１４２の判定がＹｅｓの場合は、ｊ番目の特徴点バッファpatinfoに、ｉ番目の蓄積バッファstock内のパターン番号pat_idを格納する（ステップＳ１４３）。次に、同じ特徴点バッファpatinfoに、同じ蓄積バッファstock内の情報を用いて計算されたsum_x／cntとsum_y／cntを格納する（ステップＳ１４４、Ｓ１４５）。
【０１０７】
次に、変数ｊ、ｉをインクリメントする（ステップＳ１４６、Ｓ１４７）。次に、変数ｉが蓄積バッファの総数に達したか否かを判定し（ステップＳ１４８）、達していなければ、ステップＳ１４２以降の処理を行い、達した場合は処理を終了する。
【０１０８】
＜第３の特徴点抽出処理＞
第３の特徴点抽出処理は、図１５のデータ構造の蓄積バッファに対応するものであり、第３のパターン蓄積処理の後に行われる。特徴点抽出部１３は、図１５のデータ構造の蓄積バッファを走査し、計数値cntが１の蓄積バッファか、あるいは以下の３つの条件を満たす蓄積バッファを抽出する。そして、抽出した蓄積バッファ内の情報を特徴点バッファに格納する。
１）計数値cntが２以上
２）標準偏差stdev_x＝√((cnt＊sum_x2−sum_x＊sum_x)／cnt／(cnt−1)＜ｄｘ
３）標準偏差stdev_y＝√((cnt＊sum_y2−sum_y＊sum_y)／cnt／(cnt−1)＜ｄｙ
【０１０９】
第３の特徴点抽出処理における特徴点バッファのデータ構造は図１９と同じであるが、パターン位置ｘにはsum_x／cntが格納され、パターン位置ｙにはsum_y／cntが格納される。すなわち、第２の特徴点抽出処理と同様である。
【０１１０】
第３の特徴点抽出処理も、第２の特徴点抽出処理と同様に、画像中の近接した場所のみに同一パターンが存在する場合には特徴点とみなす。近接した場所かどうかを判断するためにパターン位置x, yの標準偏差stdev_x, stdev_yを閾値と比較する点が第２の特徴点抽出処理と異なる。
【０１１１】
図２２は第３の特徴点抽出処理の一例を示すフローチャートである。蓄積バッファstockの種類を示す変数ｉと、特徴点バッファpatinfoの種類を示す変数ｊをともに０に初期化する（ステップＳ１５１）。
【０１１２】
次に、ｉ番目の蓄積バッファstock内の計数値cntが１か否かを判定する（ステップＳ１５２）。１であれば、ｊ番目の特徴点バッファに、ｉ番目の蓄積バッファ内のパターン番号pat_idと、sum_x／cntと、sum_y／cntとを格納する（ステップＳ１５３〜Ｓ１５５）。
【０１１３】
次に、変数ｉ，ｊをインクリメントする（ステップＳ１５６，Ｓ１５７）。次に、変数ｉが蓄積バッファの総数に達したか否かを判定し（ステップＳ１５８）、達していなければステップＳ１５２に戻り、達した場合には処理を終了する。
【０１１４】
一方、ステップＳ１５２で１でないと判定された場合は、標準偏差stdev_x＝√((cnt＊sum_x2−sum_x＊sum_x)／cnt／(cnt−1)＜ｄｘか否かを判定する（ステップＳ１５９）。判定がＹｅｓの場合は、標準偏差stdev_y＝√((cnt＊sum_y2−sum_y＊sum_y)／cnt／(cnt−1)＜ｄｙか否かを判定する（ステップＳ１６０）。
【０１１５】
ステップＳ１６０でＹｅｓと判定された場合はステップＳ１５３に移行し、ステップＳ１５９またはＳ１６０でＮｏと判定された場合はステップＳ１５７に移行する。
【０１１６】
上述した第１、第２または第３の特徴点抽出処理によって、特徴点バッファに格納されたデータが特徴点パターン情報patInfoとなる。
【０１１７】
＜パターン観測確率算出処理＞
上述したパターン蓄積部１２は、パターン番号を検出すべきビットマップ画像の全画素数分の蓄積バッファを設けることを念頭に置いた。ところが、実際には、同じパターン番号を持つ画素ブロックのパターン情報は同じ蓄積バッファに格納されるため、必ずしも、ビットマップ画像の全画素数分の蓄積バッファを用意する必要はない。この場合、蓄積バッファの数を予め制限して、すべての蓄積バッファを使い終わった時点でパターン蓄積部１２の蓄積処理を終了するか、あるいは蓄積バッファに格納するパターン情報を予め制限して、有用なパターン情報のみを蓄積バッファに格納してもよい。
【０１１８】
画素ブロック内のパターン番号の観測確率を予め予測して、観測確率が低いパターン画像に関するパターン情報のみを蓄積することで、蓄積されるパターン情報の数を減らすことも考えられる。観測確率が低いパターン画像のみに限定する理由は、観測確率の低いパターン番号はまれにしか出現しないことを意味するから、特徴的である可能性が高いためである。
【０１１９】
このようなパターン画像の観測確率の予測は、上述したパターン蓄積部１２が処理を行う前に行う必要がある。図２３はパターン画像の観測確率の予測処理を行うパターン確率算出部１５を備えた画像一致点検出装置１０の内部構成の一例を示すブロック図である。図示のように、パターン検出部１１とパターン蓄積部１２の間にパターン確率算出部１５が設けられ、これ以外の構成は図２と同じである。
【０１２０】
画像の中に、あるパターン番号のパターン画像が含まれる確率は、各画像ごとに異なるが、パターン確率算出部１５は、蓄積バッファの数を減らして処理の高速化を図るために設けられるものであり、単に蓄積バッファへのパターン情報の格納を行うか否かを示す情報のみを出力すればよい。
【０１２１】
本実施形態では、６×６＝３６画素からなる画素ブロックを、３×３＝９個のパターン番号素の組合せで表現している。したがって、各パターン番号素が観測される確率を９個分掛け合わせて得られる乗算値を閾値と比較することにより、その画素ブロックのパターン情報を蓄積するべきか否かを判断すればよい。
【０１２２】
パターン番号素は、０〜１５の数値を取り得るため、予め代表的な画像について、各パターン番号素の観測確率を求めて、テーブル化しておく。図２４はパターン番号素と観測確率との対応関係を示すテーブルの一例を示す図である。このようなテーブルをルックアップテーブル（以下、ＬＵＴ）として参照することで、容易に観測確率を算出できる。
【０１２３】
図２５はパターン確率算出部１５が行う処理の一例を示すフローチャートである。このフローチャートは、パターン番号を検出する単位である画素ブロックごとに行われる。まず、パターン番号素の種類を表す変数ｉｄｓを初期化する（ステップＳ１６１）。ここでは、新たなパターン番号素の値pat_idを変数ｉｄｓに代入する。
【０１２４】
次に、パターン観測確率pat_probを１に初期化する（ステップＳ１６２）。次に、確率を求めたパターン番号素の総数を表す変数ｉを０に初期化する（ステップＳ１６３）。
【０１２５】
次に、変数ｉｄｓを１６で割った余りを変数ｎに代入する（ステップＳ１６４）。次に、変数ｉｄｓに対応する確率LUT(u)をＬＵＴから参照し、パターン観測確率pat_probと掛け合わせる（ステップＳ１６５）。次に、変数ｉｄｓを更新するために、（ids−ｎ）／１６を変数ｉｄｓに代入する（ステップＳ１６６）。次に、変数ｉをインクリメントする（ステップＳ１６７）。
【０１２６】
次に、変数ｉがパターン番号素の総数に達したか否かを判定する（ステップＳ１６８）。達していなければステップＳ１６４以降の処理を行う。変数ｉがパターン番号素の総数に達した場合は、パターン観測確率pat_probが求まったことを示しており、このパターン観測確率pat_probが予め定めた閾値未満か否かを判定する（ステップＳ１６９）。
【０１２７】
パターン観測確率pat_probが閾値未満であれば、上述した第１，第２または第３のパターン蓄積処理を行う（ステップＳ１７０）。一方、閾値以上であれば、その画素ブロックのパターン情報はパターン蓄積部１２には蓄積しないものと決定する（ステップＳ１７１）。
【０１２８】
図２５の処理では、パターン観測確率pat_probの大きさにより、パターン蓄積を行うか否かを判断している。ところが、画像によっては、細かな模様が数多く含まれているものや、逆にコントラストが低い画像や夜景のように暗い画像もある。したがって、図２５の処理では、細かな模様が数多く含まれている画像は数多くのパターン情報が蓄積され、コントラストが低い画像等はあまり蓄積されない結果となる。
【０１２９】
パターン蓄積部１２内の蓄積バッファをできるだけ最大限使うためには、画像の種類ごとに異なる適切な閾値を設定しなければならないが、そのためには、閾値を決定する処理を別個に行わなければならず、処理速度の高速化という観点から不利である。
【０１３０】
そこで、図２５の処理によって得られたパターン観測確率pat_probを複数の段階に分類し（段階分類部）、各段階ごとに蓄積バッファを設けて、蓄積バッファを使用するか否かを各段階ごとに判断することで、蓄積バッファの使用量を制限することが考えられる。
【０１３１】
この場合、対応する段階またはそれ以下の段階に属する特徴点パターン情報の候補の数を計測する（特徴点候補計数部）。次に、特徴点パターン情報の候補のパターン番号と、同一のパターン番号の出現回数と、各パターン番号に対応するパターン位置に関する情報とを、複数の蓄積バッファに分けて格納するようにする。その際、特徴点候補計数部で計測された数が所定の閾値未満であれば、対応する蓄積バッファへの格納を許可し、特徴点候補計測部で計測された数が閾値より大きければ、対応する段階以上（つまり、観測確率の高い段階）のすべての蓄積バッファへの格納を禁止する。図２６Ａ、図２６Ｂ、図２６Ｃおよび図２６Ｄはこの種の蓄積制御処理の一例を示すフローチャートである。
【０１３２】
図２６Ａは、図９のステップＳ４２、図１２のステップＳ６２または図１６のステップＳ１０２の処理に代わるものであり、段階ごとに設けられる複数の蓄積バッファをすべてクリアする処理を行う。
【０１３３】
まず、段階を表す変数ｋを０に設定する（ステップＳ４２−１）。次に、ｋ番目の段階の蓄積バッファstockを使用すべく、stockポインタを設定する（ステップＳ４２−２）。
【０１３４】
次に、ｋ番目の段階のｉ番目の蓄積バッファstockの計測数cntを０に設定（クリア）する（ステップＳ４２−３）。次に、変数ｋをインクリメントし（ステップＳ４２−４）、すべての段階（例えば、１６段階）の蓄積バッファstockすべてをクリアしたか否かを判定し、判定がＮｏの場合はステップＳ４２−２に戻り、Ｙｅｓの場合は図９のステップＳ４３、図１２のステップＳ６３または図１６のステップＳ１０３に移行する。
【０１３５】
図２６Ｂは、図９のステップＳ４６、図１２のステップＳ６６または図１６のステップＳ１０６の処理に代わるものであり、すべての段階の特徴点パターン情報の候補数（以下、特徴点候補数）ccntと蓄積バッファへの格納を許可するか否かを設定するための蓄積許可フラグFlagを初期化する。
【０１３６】
まず、パターン検出部１１で検出されたパターン番号上の位置を表す変数ｊを０に設定する（ステップＳ４６−１）。次に、段階を表す変数ｋを０に設定する（ステップＳ４６−２）。次に、ｋ番目の段階の特徴点候補数ccnt[k]を０に設定する（ステップＳ４６−３）。次に、ｋ番目の段階の蓄積許可フラグFlag[k]を許可状態（例えば１）に設定する（ステップＳ４６−４）。次に、変数ｋをインクリメントする（ステップＳ４６−５）。
【０１３７】
次に、１６段階全ての特徴点候補数ccnt[k]と蓄積許可フラグFlag[k]を初期化したか否かを判定し（ステップＳ４６−６）、判定がＮｏの場合はステップＳ４６−３に戻り、判定がＹｅｓの場合は、図９のステップＳ４７、図１２のステップＳ６７または図１６のステップＳ１０７の処理を行う。
【０１３８】
図２６Ｃは、図９のステップＳ４７、図１２のステップＳ６７または図１６のステップＳ１０７の処理に代わるものであり、蓄積許可フラグFlagが許可状態のときのみ、蓄積バッファへの格納を行うものである。
【０１３９】
まず、蓄積バッファstock上の位置を示す変数ｉを０に設定する（ステップＳ４７−１）。次に、パターン番号pat_id[j]からパターン観測確率pat_probを算出する（ステップＳ４７−２）。ここでは、図２５の処理を実行する。
【０１４０】
次に、算出したパターン観測確率pat_probから段階LEVを算出する（ステップＳ４７−３）。パターン観測確率pat_probの最大値は５３９であり、log１０５３９＝約１５であるため、段階LEVは、０〜１５の範囲内の１６段階を示す値となる。
【０１４１】
次に、段階LEVの蓄積バッファへの格納が許可されているか否かを判定する（ステップＳ４７−４）。ここでは、蓄積許可Flagの値で判断する。許可されていなければ、図１０のステップＳ５６、図１３のステップＳ８０または図１７のステップＳ１１４に移行し、許可されていれば、LEV番目の段階の蓄積バッファにパターン番号等を格納する設定を行う（ステップＳ４７−５）。その後、図１０のステップＳ４８、図１２のステップＳ６８または図１７のステップＳ１０８の処理を行う。
【０１４２】
図２６Ｄは、図１０のステップＳ５５、図１３のステップＳ７９または図１７のステップＳ１１３の処理に代わるものであり、パターン検出部１１で検出されたパターン番号pat_idがｉ番目の蓄積バッファstockのパターン番号pat_idと一致した場合には、特徴点パターン情報ではなくなることから、特徴点候補数ccnt[LEV]をデクリメントするものである。
【０１４３】
まず、計数値cntをインクリメントし（ステップＳ５５−１）、次に、特徴点候補数ccnt[LEV]をデクリメントする（ステップＳ５５−２）。その後、図１０のステップＳ５６、図１３のステップＳ８０または図１７のステップＳ１１４の処理を行う。
【０１４４】
図２６Ｅは、図１０のステップＳ５４、図１４のステップＳ９２または図１８のステップＳ１２４の処理に代わるものであり、特徴点候補数が閾値以上か否かを判定して、蓄積バッファ部への格納制御と蓄積許可フラグFlagの設定を行う。
【０１４５】
まず、蓄積バッファ部の総数stock_maxをインクリメントする（ステップＳ５４−１）。次に、段階LEVの特徴点候補数ccnt[LEV]をインクリメントする（ステップＳ５４−２）。次に、各段階の特徴点候補数数ccnt[LEV]の和を求める計数値sum_ccntに、ccnt[LEV]を代入する（ステップＳ５４−３）。
【０１４６】
次に、段階を表す変数ｋを０に設定する（ステップＳ５４−４）。次に、計数値sum_ccntに、ｋ段階の特徴点候補数を加算する（ステップＳ５４−５）。次に、変数ｋをインクリメントする（ステップＳ５４−６）。
【０１４７】
次に、段階LEVよりもパターン観測確率の低い段階の特徴点候補数の加算が終了したか否かを判定する（ステップＳ５４−７）。この判定がＮｏであればステップＳ５４−５に戻り、Ｙｅｓであれば、特徴点候補数の和sum_ccntが閾値以上か否かを判定する（ステップＳ５４−８）。
【０１４８】
ステップＳ５４−８の判定がＹｅｓであれば、変数ｋを次の段階の値に設定する（ステップＳ５４−９）。次に、段階ｋの蓄積許可フラグFlagを０に設定する（ステップＳ５４−１０）。次に、変数ｋをインクリメントする（ステップＳ５４−１１）。
【０１４９】
次に、パターン観測確率が最も高い段階まで処理したか否かを判定し（ステップＳ５４−１２）、判定がＮｏであればステップＳ５４−１０に戻り、判定がＹｅｓの場合、あるいはステップＳ５４−８の判定がＮｏの場合は、図１０のステップＳ５５、図１３のステップＳ８０または図１７のステップＳ１１４に移行する。
【０１５０】
＜一致点検出処理＞
次に、一致点検出処理について説明する。まずは、２つの画像から抽出された特徴点の情報を利用して一致点を検出する例を説明する。３つ以上の画像間での一致点検出は、そのうちの２つの画像について、まず一致点の検出を行い、その検出結果と、まだ一致点検出を行っていない残りの一つの画像との間で一致点を検出し、その検出結果を利用して、さらに残りの一つの画像との間で一致点検出を行うといった処理を繰り返せばよい。
【０１５１】
話を戻して、２つの画像間での一致点の検出処理について説明する。ここで、画像Ａから得られた特徴点パターン情報をpatInfoA、画像Ｂから得られた特徴点パターン情報をpatInfoBとする。
【０１５２】
特徴点パターン情報patInfoAに、複数の特徴点に関するパターン情報が格納されている場合には、その一つ一つのパターンに対応するパターン番号を、特徴点パターン情報patInfoBに格納されているすべての特徴点パターン情報のパターン番号と照合し、共通して含まれるパターン番号と、そのパターン位置とを抽出する。
【０１５３】
ここで、特徴点パターン情報patInfoAから抽出されたパターン位置をａ、特徴点パターン情報patInfoBから抽出されたパターン位置をｂとすると、画像Ａでは位置ａに写っていたものが画像Ｂでは位置ｂに写っていたことになる。
【０１５４】
このようにして、共通するパターン番号を持つ特徴点パターン情報をすべて抽出することにより、画像ＡとＢの間での対応する位置情報を複数得ることができる。もちろん、場合によっては、一つしか得られない場合や、一つも得られない場合もあり得る。
【０１５５】
一致点検出部１４は、上記の処理手順で図２７のような一致点情報を検出する。図２７の一致点情報は、パターン番号pat_idと、画像Ａの位置ｘの値ｘ０と、同画像Ａの位置ｙの値ｙ０と、画像Ｂの位置ｘの値ｘ１と、同画像Ｂの位置ｙの値ｙ１とを有する。
【０１５６】
ここで、パターン番号pat_idは、さらに別の画像との間で一致点検出を行う場合には必要となるが、２つの画像間での一致点検出だけを行うのであれば、必ずしも必要ない。
【０１５７】
図２８は一致点検出部１４が行う一致点検出処理の一例を示すフローチャートである。まず、画像Ａに対して、上述した第１、第２または第３の特徴点抽出処理を行って得た特徴点パターン情報patInfoAを取得する（ステップＳ１９１）。同様に、画像Ｂに対しても特徴点パターン情報patInfoBを取得する（ステップＳ１９２）。
【０１５８】
次に、特徴点パターン情報patInfoA上の位置を表す変数ｉと、一致点の数を表す変数ｋをともに０に初期化する（ステップＳ１９３）。同様に、特徴点パターン情報patInfoB上の位置を表す変数ｊを０に初期化する（ステップＳ１９４）。
【０１５９】
次に、ｉ番目の特徴点パターン情報patInfoAのパターン番号と、ｊ番目の特徴点パターン情報patInfoBのパターン番号とが一致するか否かを判定する（ステップＳ１９５）。両者が一致しない場合は、変数ｊをインクリメントする（ステップＳ１９６）。変数ｊが特徴点パターン情報patInfoBの総数に達したか否かを判定する（ステップＳ１９７）。達しなかった場合はステップＳ１９５以降の処理を行い、達した場合は変数ｉをインクリメントする（ステップＳ１９８）。
【０１６０】
変数ｉは特徴点パターン情報patInfoAの総数に達したか否かを判定する（ステップＳ１９９）。達していなければステップＳ１９４以降の処理を行い、達した場合は処理を終わる。
【０１６１】
一方、ステップＳ１９５で両者のパターン番号が一致したと判定されると、図２７のような一致点情報を追加する（ステップＳ２００）。次に、一致点情報の数を表す変数ｋをインクリメントし（ステップＳ２０１）、ステップＳ１９８以降の処理を行う。
【０１６２】
＜画像の移動、回転、拡縮＞
一致点検出部１４により検出された一致点情報は、種々の目的で利用できるが、ここでは、２つの画像Ａ，Ｂ間の一致点検出情報に基づいて、画像Ａが画像Ｂに近づくように、画像Ａの移動、回転および拡縮の少なくとも一つの処理を行う例を説明する。
【０１６３】
画像Ａ中の座標(x, y)に対して何らかの座標変換を行った後の座標を(x', y')とする。
【０１６４】
例えば、座標(x, y)を移動量dx, dyで平行移動した後の座標(x', y')は、以下の（６）式で表される。この（６）式では、変換元の二次元座標に、ｚ＝１を補って３次元のベクトルとして、３×３の行列Ｇを用いて変換を行う。
【数１】
【０１６５】
座標(x, y)を原点の回りにθ度回転させた後の座標(x', y')は、以下の（７）式で表される。
【数２】
【０１６６】
座標(x, y)を原点を不動点とする拡縮率ｆで拡縮した後の座標(x', y')は、以下の（８）式で表される。
【数３】
【０１６７】
上述した（６）〜（８）式を組み合わせた変換式は、以下の（９）式で表される。
【数４】
【０１６８】
上記（９）式の右辺の３×３行列を３つ乗算して得られる行列Ｇは、移動、回転および拡縮の処理をまとめて実施するものである。
【０１６９】
ここで、ｐ＝(x, y)からｑ＝(x', y')の変換をｇとしたときに、ｑ＝ｇ(ｐ)と表すことにする。
【０１７０】
ここで、一致点検出部１４で検出された一致点情報のｎ番目の画像Ａ上の位置をＡn、画像Ｂ上の対応位置をＢnとすると、
Ｂ0＝ｇ(Ａ0)
Ｂ1＝ｇ(Ａ1)
…
Ｂn＝ｇ(Ａn)
となる変換ｇを求めれば、変換ｇの具体的内容である移動量dx, dyや、回転角度θ、拡縮率ｆを検出できる。
【０１７１】
あるいは、ベクトルｖの長さの二乗をLen2(v)と表記する。このLen2(v)は、ベクトルｖ同士の内積により算出可能である。このLen2(v)を用いると、画像Ａの位置と対応する画像Ｂの位置の距離の二乗和は、以下の（１０）式で表される。
Len2(Ｂ0−ｇ(Ａ0))＋Len2(Ｂ1−ｇ(Ａ1))＋…＋Len2(Ｂn−ｇ(Ａn)) …（１０）
【０１７２】
（１０）式が小さくなるように、変換ｇの移動量dx, dyと、回転角度θと、拡縮率ｆとを求めれば、移動量、回転量および拡縮率を算出できる。
（１０）式の計算は、いわゆる収束計算によって行えばよい。
【０１７３】
あるいは、行列Ｇの代わりに、下記のような行列Ｈを用いて処理を行う方法もある。
【０１７４】
変換後の位置Ｂ0＝Ｈ＊変換元の位置Ａ0
変換後の位置Ｂ1＝Ｈ＊変換元の位置Ａ1
…
変換後の位置Ｂn＝Ｈ＊変換元の位置Ａn …（１１）
【０１７５】
上記（１１）式は、変換前の位置０、１、…、ｎを列ベクトルに持つ３行ｎ＋１列の行列Ａに行列Ｈを乗算して、変換後の位置０、１、…、ｎを列ベクトルに持つ３行ｎ＋１列の行列Ｂを得るものであり、Ｂ＝Ｈ＊Ａで表すことができる。
【０１７６】
通常、逆行列とは、正方行列のみに存在するが、正方でないｎ＋１行３列の行列Ａinvが、Ａ＊Ａinv＝３×３の単位行列となるとき、Ａinvは疑似逆行列と呼ばれる。
【０１７７】
このＡinvを、上述したＢ＝Ｈ＊Ａの両辺に左側から掛け合わせると、以下の（１２）式が得られる。
Ｂ＊Ａinv＝Ｈ＊Ａ＊Ａinv …（１２）
Ａ＊Ａinvは単位行列であるため、上記（１２）式は（１３）式のように変換される。
Ｂ＊Ａinv＝Ｈ＊単位行列＝Ｈ …（１３）
【０１７８】
この（１３）式により、行列Ｈが確定する。行列Ｈにより行われる変換は、移動、回転、拡縮のみならず、より複雑な変換をも含む。Ｈによる変換は、上述したように、２次元座標を３次元のｚ＝１面に置き換えて空間一次変換を行うすべての自由度を含む変換である。この行列Ｈによる画像変換を行い、その結果に基づいて行列Ｈが求まってしまえば、移動、回転、拡縮、その他のすべての自由度を含む変換を行える。
【０１７９】
移動、回転、拡縮以外の変換としては、例えば、正方形を平行四辺形にするような変換や、縦と横で異なる倍率の拡縮なども行うことができる。これにより、例えば被写体が回転している方向だけに拡縮を行う場合に対しても追従でき、処理能力が許せば、行列Ｈを用いた手法の方が望ましいかもしれない。この場合は、Ｇを計算する必要はなくなる。
【０１８０】
一方、移動、回転、拡縮等の既存の画像処理系を利用する場合は、上述したように、行列Ｇの移動量dx, dy、回転角度θおよび拡縮率ｆを求めればよい。また、移動量dx, dy、回転角度θおよび拡縮率ｆのうち、少なくとも一つを処理するように設計してもよい。
【０１８１】
３つ以上の画像について、移動、回転または拡縮を行う場合も同様の手順で行列ＧまたはＨを求めればよい。例えば、画像Ａ，Ｂの他に画像Ｃがあり、画像Ｃ上の位置をＣ0〜Ｃnで表記する場合、上述した（１０）式の代わりに、以下の（１４）式を求める。
【０１８２】
Len2(Ｂ0−ｇ(Ａ0))＋Len2(Ｃ0−ｇ(Ａ0))＋Len2(Ｂ1−ｇ(Ａ1))＋Len2(Ｃ1−ｇ(Ａ1))＋…＋Len2(Ｂn−ｇ(Ａn))＋Len2(Ｃn−ｇ(Ａn)) …（１４）
上記（１４）式により、変換後の画像Ａと、画像ＢおよびＣとの一致点の距離の二乗の和を小さくするようにすれば、画像ＢとＣの平均的な位置に画像Ａを合わせることになる。さらに、画像Ｄとの一致点も処理すると、画像Ａを画像Ｂ，Ｃ，Ｄの平均的な位置に合わせることになる。この性質を利用すると、デジタルビデオカメラの手ぶれ補正処理に応用することができる。
【０１８３】
図２９は上述した一致点検出情報に基づく画像変換の手法を模式的に示す図である。図２９では、３つのコマ画像Ａ，Ｂ，Ｃの一致点を合わせて、一致点の位置が重なり合うように画像変換を行う例を示している。例えば、コマ画像Ａ，Ｂ，Ｃ中のりんごの部分が一致点として検出されたとする。この場合、上述した行列ＧまたはＨを用いて、画像変換が行われる。その後、画像変換後の３つのコマ画像中の一致点同士が重なり合うように画像合成が行われる。
【０１８４】
本実施形態をビデオカメラに適用する場合、各コマ（フレームまたはフィールド）画像に対して上述した第１、第２または第３の特徴点抽出処理を行い、最近の数コマ（例えば２〜６０コマ程度）を参照コマとして、直前のコマを処理対象とする。
【０１８５】
上述した（１４）式が小さくなるように処理を行うと、参照コマに対する平均的な位置に、処理対象コマが合致または近づくように変換が行われ、手ぶれによる画像の移動回転拡縮が平滑化されることになる。このことは、例えばフレームレートが３０コマ／秒のカメラで最近の３０コマを参照コマとして実行した場合、１秒分の動きが平滑化された映像に対して合わせられることを意味する。すなわち、細かな振動を画像から取り除くことになり、手ぶれまたは被写体ブレを緩和することができる。
【０１８６】
なお、参照コマから一致点検出を行う場合、特徴点パターン情報だけを保持しておけばよく、画像データ自体を保持する必要はない点でも本実施形態は優れている。例えば、参照コマ数が多いほど瞬間的な移動によるブレは平滑化されることになり、６０コマ程度に増やした場合でも、画像そのものを保持しておく必要はなく、メモリ消費も少なくて実装が容易である。
【０１８７】
従来のコマ間での移動情報（フレーム間差分による移動情報）を積算しながら処理する方式では、画像同士を比較するために、最近の画像と直前の画像とを比較するのが精一杯であり、フレーム間差分を最小化するように移動量などを計算していた。本実施形態によれば、誤差の蓄積を防止できるだけでなく、時間的に離れた複数のコマとの比較も行うため、検出精度が極めて高くなる。
【０１８８】
この結果、本実施形態によれば、手ぶれ補正効果が大きくなり、誤動作も少なくなる。また、移動だけでなく、カメラの傾き（回転）や前後またはズーム（拡縮）ブレも緩和できる。
【０１８９】
上述した手法により複数の画像の一致点検出と画像変換を行うことで、同一画素位置に同一の物体が写されるように変換することができる。このような画像変換処理を行うことで、種々の利点が得られる。
【０１９０】
一つには、ノイズの低減効果である。ランダムノイズは、不規則に発生するために低減が難しいノイズであるが、不規則に発生する性質を利用すると、複数の画像を重ね合わせることで、低減が可能である。このとき、画像を重ね合わせる手法には種々のものがあるが、以下では、平均化と中間値を算出する手法を説明する。
【０１９１】
画像変換された複数画像の同一画素位置を平均化して得られる画像は、同一の物体が同一の画像位置に写っているため、平均化によりその物体から得られる信号Ｓは変化しない。一方、ノイズは不規則であるため、平均化する画素数に応じて低減される。したがって、画像変換された複数画像を合成する場合は、平均化した画素数に応じてＳ／Ｎが向上し、ノイズを低減することができる。
【０１９２】
一方、ランダムノイズは不規則であり、正規分布することが予めわかっている。このため、画像変換された複数画像を合成する際に、中間値を用いることによってもノイズを低減できる。この場合、周辺の画素ではなく、複数画素の合成に応用しているため、中間値フィルタをかけた場合によく見られるように、画像のヌメヌメ感は発生するおそれはない。
【０１９３】
なお、上述した平均化の際に、必要に応じて重み付けを行ってもよい。以下では、重み付けの一例を説明する。
【０１９４】
露出を変えながら撮影された一連の画像を合成すると、ノイズを低減できる他に、ダイナミックレンジを拡大できるという効果がある。
【０１９５】
明るく撮影された画像の方がノイズが少ないため、平均時の重みを大きくし、暗く撮影されている画像では重みを小さくする。ただし、明るい画像中で色または輝度が飽和している部分は白とびが発生しているため、重みを０にする。
【０１９６】
輝度が次第に明るくなって、飽和に至るまでのグラデーション領域で、急激な重みの変化が発生することで違和感が出ないように、飽和点手前から徐々に重みを下げていく。
【０１９７】
このような重み付けを行うには、ピクセル値の大きさに応じて重みが増し、飽和点の手前から重みが減少し、飽和点で０になるような関数によって重みを算出するのが望ましい。この種の関数の具体的な実装例として、最も処理量が小さく、かつ自由度の高いものは、ルックアップテーブルである。
【０１９８】
図３０はルックアップテーブル（以下、ＬＵＴ）をグラフ化した一例を示す図である。図３０では、画素値を０〜２５５とし、重みの範囲も０〜２５５としている。Ｒ，Ｇ，Ｂの各色ごとに、個別あるいは共通のＬＵＴを引いて、画素値に対応する重みを設定すればよい。
【０１９９】
図３１は重み付けの一例を模式的に説明する図である。図３１は図２９で画像変換した後の３つのコマ画像のそれぞれに重み付けを行う例を示している。コマ画像中の特定画素位置について、コマ画像ごとに別個の重み付けを行う。例えば、コマ画像Ａの特定画素位置の画素値が１３０の場合、ＬＵＴを引くことにより、重み２００を取得する。同様に、コマ画像Ｂの特定画素位置の画素値が１２０であれば重み１９０を取得し、コマ画像Ｃの特定画素位置の画素値が１２５であれば重み１９５を取得する。そして、以下の（１５）式により、合成画素値を算出する。
【数５】
【０２００】
本実施形態をデジタルスチルカメラに適用すれば、露出違いで撮影された一連の画像からダイナミックレンジが広くて、かつ階調性が豊かで、ノイズも少ない画像を記録することができる。
【０２０１】
図３２は露出を変えながら撮影した３枚のコマ画像Ａ，Ｂ，Ｃの重み付けの一例を模式的に説明する図である。コマ画像Ａ，Ｂ，Ｃの順に露出が低くなっているものとする。コマ画像Ａ，Ｂは露出が高いため、一部が白飛びしている。白飛びしている画素領域（画素値＝２５５）は重みが０に設定され、この画素領域については、白飛びしていないコマ画像Ｃは０でないので、合成結果はＣの画像データが使われる。
【０２０２】
コマ画像Ｃは一部が黒つぶれしている。黒つぶれした画素領域は、黒つぶれしていないコマ画像ＡまたはＢの重みよりも小さく設定されるため、結果Ａが優先され、Ｂ，Ｃの順に低い重みで合成される。
【０２０３】
なお、上述した重みづけは他の画像には依存しないため、一連の映像を同時に参照せずに重みを決定でき、必要に応じて逐次重み付けを行いながら合成画像を蓄積することができる。これにより同時に必要な作業用メモリ量を削減できる。
【０２０４】
例えば、作業用メモリには、画素数分の画素の合計値SumR, SumG, SumB と重みの合計値 SumFact を格納し、０に初期化しておく。先の変換処理によって変換済みの映像が入力されたら各画素値から重み(Fact)を算出して、Ｒ画素値と重みFactの乗算値をSumRに足しこむ、同様に、Ｇ画素値と重みFactの乗算値をSumGに足しこむ。同様に、Ｂ画素値と重みFactをSumBに足しこむ。SumFact には Fact を足しこむ。
【０２０５】
このようにして、一連の画像のすべてのピクセルの足しこみ処理が完了したら、各画素の SumR, SumG, SumB を SumFact で除算して、平均化された画素値が得られる。
【０２０６】
なお、ここで SumFact で除算する代わりに、例えば SumFact/4 で除算すると、画像合成前の画像よりも４倍大きな画素値が得られる。例えば、４枚の画像を合成している場合には、４倍程度階調性が増しているので、４倍大きな画素値を取り出すことで、豊かな階調を得ることもできる。
【０２０７】
本実施形態の他の応用は、ピント位置を変化させながら撮影された一連の画像から、できるだけ広い範囲にピントがあった画像を生成することである。これもまた、画素毎に設定された重みによる加重平均を利用する。
【０２０８】
このとき、ピントが合っている箇所ほど大きな重みとなり、ピントが合っていない箇所ほど重みが小さくなるように重みづけされて平均化すれば良い。これにもさまざまな手法が考えられるが、以下では、高い周波数が含まれている部分ほどピントが合っていると判断し、大きな重みを設定する例を説明する。
【０２０９】
処理対象画像に対して、（１５）式の行列で表される高周波検出フィルタを通すと、高周波が多く含まれている部分ほど大きな値が算出される。
【数６】
【０２１０】
算出された値の絶対値または、２乗値を重みとすれば良い。この際、カラー画像であっても、Ｒ，Ｇ，Ｂごとに別個に処理を行う必要はなく、予めＲ，Ｇ，Ｂから輝度（例えば、輝度Y=(3R+6G+B)/10）を求めてからフィルタリングすると、全体の処理量が小さくなり有利である。
【０２１１】
なお、このフィルタリングは、あくまでも重みの算出のためのものであるから、ここでの輝度の計算は厳密である必要はない。処理量を少なくしたい場合には、さらに計算を簡略化しても構わない。(例:Y＝(R＋2G＋B)／4)
図３３はピント位置に合わせて重みを調整する手法を模式的に示す図である。コマ画像Ａは人間にピントが合っており、コマ画像Ｂは木にピントが合っており、コマ画像Ｃは山にピントが合っているものとする。したがって、人間の写っている画素領域では、コマ画像Ａの重みが大きくなり、木が写っている画素領域では、コマ画像Ｂの重みが大きくなり、山が写っている画素領域では、コマ画像Ｃの重みが大きくなる。
【０２１２】
これにより、近くから遠くまで全体的にピントが合った画像が得られる。
【０２１３】
上述したように、本実施形態によれば、少ない演算量かつ高速に精度の高い一致点を大量に検出することが可能であり、従来の方法の欠点である演算量という問題点を克服できる。局部的な画素値の相対的な大小関係を許容値（閾値）を考慮するため、画像のさまざまなノイズ（ランダムノイズ、圧縮時のブロックノイズやモスキートノイズ）だけでなく、画像の傾きや拡縮（像倍率の変化）に対しても寛容であり、画像１の位置ａは、画像２の位置ｂに対応するというようなベクトル情報を複数提供でき、平行移動だけでなく、回転や拡縮も検出でき、さらには、上述した特許文献３による３次元カメラベクトルを特定してさらに高度なブレ補正を行う用途にも応用可能である。また、高速であるが故に、１対複数画像での一致点検出や、複数対複数の一致点検出も短時間に終わらせることが可能であり、結果より多くの一致検出結果を得ることができ、さらには一致点検出の精度向上が見込める。
【０２１４】
本実施形態を応用することで、上述した一致点検出機能を持つ画像処理装置、デジタルスチルカメラおよびデジタルビデオカメラ等を提供することができるが、本実施形態の適用範囲はこれだけに留まらない。本実施形態では、処理量を増大させることなく、数多くの一致点を検出できるため、動画映像から動くものだけを発見する場合においても、より小さな移動体を検出できたり、精度が高いことから、それを追跡する場合においても有利である。対象物の動きに追従してズーミングしたり、車に搭載されたビデオカメラからの画像を処理して、近づく人間や物体を警告したり、入って来た人を追いかける監視カメラなど、応用範囲は広範囲に及ぶ。
【０２１５】
すなわち、本実施形態は、複数の画像から、精度の高い一致点を高速かつ少ない演算量で検出できるため、本実施形態を利用すれば、種々の特徴を持つ応用製品を生み出せる。
【０２１６】
本発明の態様は、上述した個々の実施形態に限定されるものではなく、当業者が想到しうる種々の変形も含むものであり、本発明の効果も上述した内容に限定されない。すなわち、特許請求の範囲に規定された内容およびその均等物から導き出される本発明の概念的な思想と趣旨を逸脱しない範囲で種々の追加、変更および部分的削除が可能である。
【０２１７】
上述した実施形態で説明した画像一致点検出装置の少なくとも一部は、ハードウェアで構成してもよいし、ソフトウェアで構成してもよい。ソフトウェアで構成する場合には、画像一致点検出装置の少なくとも一部の機能を実現するプログラムをフレキシブルディスクやＣＤ−ＲＯＭ等の記録媒体に収納し、コンピュータに読み込ませて実行させてもよい。記録媒体は、磁気ディスクや光ディスク等の着脱可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記録媒体でもよい。
【０２１８】
また、画像一致点検出装置の少なくとも一部の機能を実現するプログラムを、インターネット等の通信回線（無線通信も含む）を介して頒布してもよい。さらに、同プログラムを暗号化したり、変調をかけたり、圧縮した状態で、インターネット等の有線回線や無線回線を介して、あるいは記録媒体に収納して頒布してもよい。
【符号の説明】
【０２１９】
１ 撮像素子
２ Ａ／Ｄ変換器
３ 画像処理回路
４ 符号化装置
１０ 画像一致点検出装置
１１ パターン検出部
１２ パターン蓄積部
１３ 特徴点抽出部
１４ 一致点検出部
１５ パターン確率算出部
【技術分野】
【０００１】
本発明は、複数のビットマップ画像に含まれる画像の一致点情報を検出する画像一致点検出装置に関する。
【背景技術】
【０００２】
従来の画像一致点検出手法は、多くの画素値に対してＳＡＤ（絶対差分和：Sum Absolute Difference）などの演算を行い、画像の差分が小さくなる点を探して画像の一致を検出している（特許文献１参照）。
【０００３】
ところが、ＳＡＤでは、複数の画素値同士を直接比較する必要があり、一つの一致点を見つけ出すだけでも多くの画素値同士を比較しなければならず、演算量が膨大になるという問題がある。
【０００４】
このため、画像を縮小して解像度を下げることで比較するデータ量を減らし、徐々に解像度を上げて一致探索するような手法が考案されている（特許文献２参照）。ところが、特許文献２の手法でも、画像値同士の比較を行う必要があり、演算量を大幅に減らすのは困難である。また、周期パターンでの誤検出やノイズの問題などもあり、一致点検出の精度が低いのが現状である。さらに、カメラの傾きによる画像の回転や、カメラの前後方向の移動やズームによる拡縮までを考慮に入れようとすると、さらに比較回路が増えて演算量が増大する。
【０００５】
一方、特許文献３には、所定数の特徴点を自動抽出して、画像のカメラの揺れに起因するブレを補正する手法が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−３９４９１号公報
【特許文献２】特開平１０−１３６３０４号公報
【特許文献３】特開２００５−２９５４９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
一致点（特徴点）を数多く抽出するほど、カメラの移動やブレを正確に特定することができるが、多くの一致点を検出することは演算量を増大させてしまう。したがって、コストやサイズが増大したりして利用できる用途が限定されるか、あるいは追従できるカメラや被写体の動きの範囲を限定せざるを得ないのが現状である。
【０００８】
また、一致点を検出する処理に先だって、ノイズ除去処理や被写体の明るさの変化なども考慮に入れなければ実用にならないため、ＲＲＦ（Radical Reach Filter）などを使用するなどの工夫を行う必要があり、さらなる演算量の増加を招く。
【０００９】
本発明は、上述した課題に鑑みてなされたものであり、その目的は、簡易な処理手順で正確かつ高速に画像の一致点検出を行う画像一致点検出装置、画像一致点検出方法および記録媒体を提供することにある。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、本発明の一態様によれば、複数のビットマップ画像のそれぞれにおける複数画素からなる画素ブロックのパターン画像を、前記画素ブロック内の全画素のビット数の総和である本来の画素ビット数以下のビット数で画素ブロックの特徴を表現する数値であるパターン番号で表現し、前記画素ブロックの前記パターン番号と前記画素ブロックの位置を表すパターン位置とを組にしたパターン情報を前記画素ブロックごとに検出するパターン検出部と、
前記複数のビットマップ画像のそれぞれに含まれる前記パターン情報を前記パターン番号により分類し、前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを格納するパターン蓄積部と、
前記複数のビットマップ画像のそれぞれについて、前記パターン蓄積部に格納された情報を用いて、前記パターン番号の出現回数が１回だけの前記パターン情報を特徴点パターン情報として抽出する特徴点抽出部と、
前記複数のビットマップ画像のそれぞれについて前記特徴点パターン情報として抽出された前記パターン情報の前記パターン番号が一致しているか否かを判断し、一致している前記パターン番号を含む複数の前記パターン情報を一致点情報として検出する一致点検出部と、を備えることを特徴とする画像一致点検出装置が提供される。
【発明の効果】
【００１１】
本発明によれば簡易な処理手順で正確かつ高速に画像の一致点検出を行うことができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施形態に係る画像一致点検出装置を備えたビデオカメラの概略構成を示すブロック図。
【図２】画像一致点検出装置１０の内部構成の一例を示すブロック図。
【図３】パターン検出部１１が行う前処理の一例を示すフローチャート。
【図４】パターン番号素の検出に利用される４画素の位置の一例を示す図。
【図５】２値画像が入力された場合の前処理の一例を示すフローチャート。
【図６】画素ブロックの一例を示す図。
【図７】パターン番号生成処理の一例を示すフローチャート。
【図８】第１のパターン蓄積処理における蓄積バッファのデータ構造を示す図。
【図９】パターン蓄積部１２が行う第１のパターン蓄積処理の一例を示すフローチャート。
【図１０】図９に続くフローチャート。
【図１１】第２のパターン蓄積処理における蓄積バッファのデータ構造を示す図。
【図１２】パターン蓄積部１２が行う第２のパターン蓄積処理の一例を示すフローチャート。
【図１３】図１２に続くフローチャート。
【図１４】図１３に続くフローチャート。
【図１５】第３のパターン蓄積処理における蓄積バッファのデータ構造を示す図。
【図１６】パターン蓄積部１２が行う第３のパターン蓄積処理の一例を示すフローチャート。
【図１７】図１６に続くフローチャート。
【図１８】図１７に続くフローチャート。
【図１９】第１の特徴点抽出処理における特徴点バッファのデータ構造を示す図。
【図２０】第１の特徴点抽出処理の一例を示すフローチャート。
【図２１】第２の特徴点抽出処理の一例を示すフローチャート。
【図２２】第３の特徴点抽出処理の一例を示すフローチャート。
【図２３】パターン画像の観測確率の予測処理を行うパターン確率算出部１５を備えた画像一致点検出装置１０の内部構成の一例を示すブロック図。
【図２４】パターン番号素と観測確率との対応関係を示すテーブルの一例を示す図。
【図２５】パターン確率算出部１５が行う処理の一例を示すフローチャート。
【図２６Ａ】蓄積制御処理の一例を示すフローチャート。
【図２６Ｂ】図２６Ａに続くフローチャート。
【図２６Ｃ】図２６Ｂに続くフローチャート。
【図２６Ｄ】図２６Ｃに続くフローチャート。
【図２６Ｅ】図２６Ｄに続くフローチャート。
【図２７】一致点情報のデータ構造を示す図。
【図２８】一致点検出部１４が行う一致点検出処理の一例を示すフローチャート。
【図２９】一致点検出情報に基づく画像変換の手法を模式的に示す図。
【図３０】ＬＵＴをグラフ化した一例を示す図。
【図３１】図２９で画像変換した後の３つのコマ画像のそれぞれに重み付けを行う例を示す図。
【図３２】露出を変えながら撮影した３枚のコマ画像Ａ，Ｂ，Ｃの重み付けの一例を模式的に説明する図。
【図３３】ピント位置に合わせて重みを調整する手法を模式的に示す図。
【発明を実施するための形態】
【００１３】
以下、図面を参照しながら、本発明の実施形態について詳細に説明する。
【００１４】
（本実施形態の基本原理）
まず、本実施形態による画像一致点検出の基本原理を説明する。本実施形態によれば、複数のビットマップ画像から一致点を見つける際に、ビットマップ画像を構成する画素値同士を直接比較する必要がない。本実施形態では、各々のビットマップ画像から抽出された特徴点パターン情報のみを比較して一致点を検出する。このため、画像を構成する画素の画素値または、画素値をフィルタリング演算した結果同士を比較するのに比べて、圧倒的に少ない処理量で一致点検出を行える。
【００１５】
本実施形態の基本原理の理解を助けるために例えを紹介する。例えば、人間にリンゴが写真内の右側に写っているものと、左側に写っているものを順に見せると、瞬時にリンゴが右から左に移ったことが認識される。人間は画素の集合体であるビットマップの比較を行わずして、これを達成している。このとき、リンゴがどのにあったかという非常に少ない情報だけを覚えている。本実施形態の手法はこれに似ている。本実施形態によれば、右側にリンゴが写っている最初の写真から、リンゴの表面や輪郭だけに含まれている特徴点の相対的な大小関係を表すパターン番号とパターン位置（座標）を抽出し、左側にリンゴが写っている写真からも同様の情報を抽出する。そして、これらの２種類の情報を比較することで、同一の特徴を持つ位置を抽出して、一致点として決定する。
【００１６】
ここでもし、リンゴが大量に写っている写真を人間に見せた場合を想定すると、人間は、もはやリンゴの位置を記憶するのは得策ではないと判断し、代わりにその絵の特徴的な部分を記憶する。本実施形態による手法は、まさにこれに似た動作を行う。
【００１７】
本実施形態が特徴的なのは、複雑な画像の画素情報の相対的な大小関係をパターン番号という単なる１つの数値に置き換えてしまうユニークなパターン検出手法を採用することである。そしてもう一つの特徴は、これらの数値を画像の多くの場所から検出したのち、その画像(または検出対象領域)にたった１箇所しかないパターン番号を抽出して特徴点とする特徴点抽出手法を採用することである。複数の数値からたった１回しか現れなかった数値を抜き出すのはたやすいことである。なお、実際には、複数回現れたパターンであっても、その範囲が狭い範囲にとどまっている場合には１箇所から検出されたとみなして良い。
【００１８】
このような特徴点を抽出することは大きな意味を持つ。画像の中から、特徴的な部分のみを抜き出すことになるためである。先のリンゴの例でいえば、その画像にリンゴが１個しかなければ、リンゴの上の画素から検出されたパターン情報が抽出されることになるし、リンゴが大量に写っているならば、他の特徴的な部分が抽出されることになる。つまり、画像の絵柄に応じて自動的に見つけやすい部分が特定され、その位置を記録するということが行われ、しかもその特徴的な情報は数値（パターン番号）と座標値（パターン位置）の羅列であるため、画像データそのものを比較するのに比べて処理コストが圧倒的に少なくなる。
【００１９】
本実施形態は、特徴的な部分が自動的に特定されて抽出される仕組みを持つため、一致点検出処理を高精度で、かつ非常に少ない演算量で実現できる。
【００２０】
さらに、本実施形態の変形例として、ビットマップ画像中から検出されたパターン番号から、１箇所にしか検出されなかったパターン番号の抽出を高速化するために、良く現れるパターンを排除して蓄積する工夫を行うことも可能である。
【００２１】
本実施形態によれば、画像をたった一度スキャンするだけで、他の画像との一致点を検出するための軽量なデータ（特徴点パターン情報）を収集できる。しかも、ノイズなどの影響を受けにくいため、従来必要であったノイズ除去処理に代表される前処理を行う必要もない。さらに、周期的に同じパターンが続く部分での誤検出が自動的に防止される。このため、デジタルカメラなどに応用する場合には、処理の前段である検波ロジックにこれを組み込むことが可能になり、低コストでリアルタイムに画像の一致点検出を行うことができ、手ぶれ補正をはじめとするさまざまな機能を低コストで実現することが容易になる。
【００２２】
（本実施形態の具体的な構成および処理動作）
以下、本実施形態について、より詳細に説明する。図１は本発明の一実施形態に係る画像一致点検出装置を備えたビデオカメラの概略構成を示すブロック図である。図１のビデオカメラは、画像を撮像する撮像素子１と、撮像素子１で撮像した画像をデジタル画素データに変換するＡ／Ｄ変換器２と、デジタル画素データに対して各種画像処理を行う画像処理回路３と、画像処理後のデジタル画素データを符号化する符号化装置４とを備えている。本実施形態に係る画像一致点検出装置１０は、画像処理装置の内部に設けられている。この画像処理装置では、上述した検波処理と画像処理を行うものであり、本実施形態に係る画像一致点検出装置１０の処理は検波処理の一部として行ってもよいし、画像処理の一部として行ってもよい。
【００２３】
図２は画像一致点検出装置１０の内部構成の一例を示すブロック図である。図２の画像一致点検出装置１０は、パターン検出部１１と、パターン蓄積部１２と、特徴点抽出部１３と、一致点検出部１４とを有する。
【００２４】
パターン検出部１１は、ビットマップ画像（以下、単に画像と呼ぶ）に含まれる画素ブロックごとに、画素ブロックのパターン情報を表すパターン番号を計算して、そのパターン情報の位置（パターン位置）とともに出力する。パターン番号とは、画像中の隣接する複数画素からなる画素ブロックのパターン画像を、画素ブロック内の全画素のビット数の総和である本来の画素ビット数以下のビット数で画素ブロックの特徴を表す数値（つまり、数値が完全に一致するか不一致かの比較によって、画像の特徴の一致が検出できる性質を持つ数値）で表現したものである。パターン検出部１１が出力するパターン番号とパターン位置を組にしたものはパターン情報と呼ばれる。パターン検出部１１は、パターン情報を画素ブロックごとに検出する。
【００２５】
パターン蓄積部１２は、画像に含まれるパターン情報をパターン番号ごとに分類し、パターン番号と、同一のパターン番号の出現回数と、それぞれのパターン番号に対応するパターン位置に関する情報とを蓄積する。
【００２６】
特徴点抽出部１３は、パターン蓄積部１２に蓄積された各種情報を用いて、画像におけるパターン番号の出現回数が１回だけであるパターン情報を特徴点パターン情報として抽出する。
【００２７】
一致点検出部１４は、複数の画像のそれぞれについて特徴点パターン情報として抽出されたパターン情報のパターン番号が一致しているか否かを判断し、一致しているパターン番号を一致点情報として検出する。
【００２８】
パターン検出部１１は、まず最初に、パターン番号素を検出する前処理を行う。パターン番号素とは、注目画素を含む周囲複数画素内のエッジの配置パターンを表すビット列信号である。前処理は、入力される画像の種類によって、処理内容が異なる。まずは、カラー画像、ベイヤ画像およびモノクロ多階調画像の場合の処理について説明する。
【００２９】
図３はパターン検出部１１が行う前処理の一例を示すフローチャートである。この前処理では、まず、カラー画像の場合は、Ｒ，Ｇ，ＢまたはＣ，Ｍ，Ｙ等で表される各色の画素値から輝度値を計算してモノクロ多階調画像に変換するか、またはＲ，Ｇ，Ｂ，Ｃ，Ｍ，Ｙのうちのいずれか１つの色の画素値を抜き出してモノクロ多階調画像に変換する。
【００３０】
このとき、撮像素子１がベイヤ配列の場合は、Ｒ，ＧｉｎＲ，ＧｉｎＢ，Ｂのいずれか、あるいはＣ，Ｍ，Ｙ，Ｇのいずれかの画素値に基づいて、解像度が縦横ともに半分になったモノクロ多階調画像に変換するか、あるいはデモザイク処理を行って輝度値を計算してモノクロ多階調画像に変換してから処理を行う。
【００３１】
撮像素子１がハニカム配列の場合は、正方画素変換後、あるいは奇数ラインか偶数ラインのみを抽出してモノクロ多階調正方画素に変換してから行えばよい。
【００３２】
注目画素の画素位置をｘ，ｙとして、その画素値をp(x, y)とすると、注目画素と、右、下、斜め右下の４画素値は、p(x, y)、p(x+1, y)、p(x, y+1)、p(x+1, y+1)で表される。図４は、これら４画素の位置の一例を示す図である。これら４画素値の和は以下の（１）で表される。
Sum ＝p(x, y) + p(x+1, y) + p(x, y+1) + p(x+1, y+1) …（１）
ここで、以下の（２）〜（４）式に基づいて、ｄ、Ｔ０、Ｔ１を計算する。
d＝Sum／16 …（２）
T0＝Sum／4−d …（３）
T1＝Sum／4＋d …（４）
パターン番号素は４ビットのビット列信号であり、以下の基準でビット値が定まる。以下では、パターン番号素をn(x, y)と表す。
p(x, y)がT0以上でT1以下なら、Bit0を０、そうでなければ１とする。
p(x+1, y)がT0以上でT1以下なら、Bit1を０、そうでなければ１とする。
p(x, y+1)がT0以上でT1 以下なら、Bit2を０、そうでなければ１とする。
p(x+1, y+1)がT0以上でT1以下なら、Bit3を０、そうでなければ１とする。
【００３３】
以下、前処理の具体的な処理手順を図３を用いて順に説明する。まず、上記（１）式に従って、注目画素を含む周囲４画素の画素値の和を計算する（ステップＳ１）。次に、（２）式に従って許容度（allowance）ｄを計算する（ステップＳ２）。次に、（３）式に従って下側閾値Ｔ０を計算する（ステップＳ３）。次に、（４）式に従って上側閾値Ｔ１を計算する（ステップＳ４）。
【００３４】
次に、注目画素値p(x, y)が下側閾値T0と上側閾値T1の範囲内にあるか否かを判定する（ステップＳ５）上記範囲外の場合は、パターン番号素の最下位ビットBit0を１に設定する（ステップＳ６）。なお、パターン番号素ｎは、初期状態では０とする。
【００３５】
次に、注目画素の右隣の画素値p(x+1, y)が上記範囲内にあるか否かを判定する（ステップＳ７）。上記範囲外の場合は、パターン番号素のBit1を１に設定する（ステップＳ８）。
【００３６】
ステップＳ７で上記範囲内と判定された場合、またはステップＳ８の処理が終わった場合は、注目画素の下隣の画素値p(x, y+1)が上記範囲内にあるか否かを判定する（ステップＳ９）。上記範囲外の場合は、パターン番号素のBit2を１に設定する（ステップＳ１０）。
【００３７】
ステップＳ９で上記範囲内と判定された場合、またはステップＳ１０の処理が終わった場合は、注目画素の斜め右下の画素値p(x+1, y+1)が上記範囲内にあるか否かを判定する（ステップＳ１１）。上記範囲外の場合は、パターン番号素のBit3を１に設定する（ステップＳ１２）。以上で、図３の処理は終了する。
【００３８】
次に、パターン検出部１１に入力される画像が２値画像の場合の前処理について説明する。この前処理では、p(x, y)が０か、それ以外（通常は１）の２つの値しか取らないため、以下のようにパターン番号素n(x, y)を設定する。
p(x, y)が０ならば、Bit0を０、そうでなければ１とする。
p(x+1, y) が０ならば、Bit1を０、そうでなければ１とする。
p(x, y+1) が０ならば、Bit2を０、そうでなければ１とする。
p(x+1, y+1)が０ならば、Bit3を０、そうでなければ１とする。
【００３９】
図５は２値画像が入力された場合の前処理の一例を示すフローチャートである。まず、p(x, y)が０か否かを判定し（ステップＳ２１）、０でなければパターン番号素のBit0を１に設定する（ステップＳ２２）。なお、パターン番号素ｎは、初期状態では０とする。
【００４０】
ステップＳ２１で０と判定された場合、またはステップＳ２２の処理が終わると、p(x+1, y)が０か否かを判定し（ステップＳ２３）、０でなければパターン番号素のBit1を１に設定する（ステップＳ２４）。
【００４１】
ステップＳ２３で０と判定された場合、またはステップＳ２４の処理が終わると、p(x, y+1)が０か否かを判定し（ステップＳ２５）、０でなければパターン番号素のBit2を１に設定する（ステップＳ２６）。
【００４２】
ステップＳ２５で０と判定された場合、またはステップＳ２６の処理が終わると、p(x+1, y+1)が０か否かを判定し（ステップＳ２７）、０でなければパターン番号素のBit3を１に設定する（ステップＳ２８）。以上で、図５の処理は終了する。
【００４３】
パターン検出部１１は、図３または図５の前処理が終わると、パターン番号生成処理を行う。パターン番号生成処理では、処理対象のパターン番号素ｎ（ｘ，ｙ）を中心とする周囲３×３個のパターン番号素（以下、画素ブロック）のビットパターンの種類を表すパターン番号を生成する。
【００４４】
図６は画素ブロックの一例を示す図である。画素ブロック内の計９個のパターン番号素は、n(x-2, y-2)、n(x, y-2)、n(x+2, y-2)、n(x-2, y)、n(x, y)、n(x+2, y)、n(x-2, y+2)、n(x, y+2)、n(x+2, y+2)である。各パターン番号素は４ビットで表され、これら４ビットのパターン番号素を９個並べた計３６ビットのビット列がパターン番号となる。パターン番号は、以下の式で表される。
パターン番号＝n(x-2, y-2) ×２３２＋n(x, y-2) ×２２８＋n(x+2, y-2) ×２２４
＋n(x-2, y)×２２０＋n(x, y)×２１６＋n(x+2, y)×２１２＋n(x-2, y+2) ×２８
＋n(x, y+2) ×２４＋n(x+2, y+2) …（５）
（５）式からわかるように、パターン番号は０から２３６−１までの値を取る。
【００４５】
パターン検出部１１は、（５）式で表されるパターン番号と、このパターン番号の画素ブロックの画像中の位置を示すパターン位置とを組にしたパターン情報を生成する。このパターン情報はパターン蓄積部１２に送られる。
【００４６】
図７は上述したパターン番号生成処理の一例を示すフローチャートである。まず、(x-2, y-2)位置のパターン番号素n(x-2, y-2)をpat_idに入力する（ステップＳ３１）。次に、pat_idを左に４ビットシフトし、(x, y-2)位置のパターン番号素を加算する（ステップＳ３２）。次に、pat_idを左に４ビットシフトし、(x+2, y-2)位置のパターン番号素を加算する（ステップＳ３３）。次に、pat_idを左に４ビットシフトし、(x-2, y)位置のパターン番号素を加算する（ステップＳ３４）。次に、pat_idを左に４ビットシフトし、(x, y)位置のパターン番号素を加算する（ステップＳ３５）。次に、pat_idを左に４ビットシフトし、(x+2, y)位置のパターン番号素を加算する（ステップＳ３６）。次に、pat_idを左に４ビットシフトし、(x-2, y+2)位置のパターン番号素を加算する（ステップＳ３７）。次に、pat_idを左に４ビットシフトし、(x, y+2)位置のパターン番号素を加算する（ステップＳ３８）。次に、pat_idを左に４ビットシフトし、(x+2, y+2)位置のパターン番号素を加算する（ステップＳ３９）。
【００４７】
以上で、パターン検出部１１の処理動作の概略説明は終りであるが、一つの画素ブロックから複数種類のパターン情報を生成してもよい。この場合、複数種類の前処理部を設けて、それぞれの前処理部が互いに異なるパターン番号素を生成するようにする必要がある。
【００４８】
例えば、上述した（２）式のｄを、ｄ＝Sum／８としてパターン番号素を生成する処理を追加で行えば、同一の画像でありながら、生成されるパターン番号素を複数種類設けることができ、結果として、パターン番号も変えることができ、複数種類のパターン情報を生成することができる。
【００４９】
上述したｄを変えるということは、画像の中にエッジ情報が含まれるかどうかの判断基準を変えることであり、例えばｄを大きくすることは、エッジとみなす輝度の差のスレッショルドが大きくなるため、よりはっきりしたエッジのみがパターン番号のビットに反映されることになり、結果ノイズの影響を受けにくくなるため、ノイズの多い画像においては、一致点検出の精度の向上につながる。
【００５０】
このように、複数の許容度（閾値）ｄのそれぞれごとに、パターン番号と、同一のパターン番号の出現回数とそれぞれのパターン番号に対応するパターン位置に関する情報とを蓄積することで、どのような画像に対しても、良好な一致点検出結果が得られる。
【００５１】
例えば、ノイズが多い高感度撮影された映像の場合は、ｄを小さくすると、ノイズに反応してしまうため、ｄは大きくするのが望ましい。ところが、単にｄを大きくしただけだと、ノイズは少ないがエッジがはっきりしない画像では、エッジを正しく検出できないおそれがある。この２つの要求を満足させるためには、同一画像に対して、ｄを小さくして得られたパターン番号とｄを大きくして得られたパターン番号をともに重複しないで二種類設ければよい。例えば、ｄを小さくした場合のパターン番号を０〜２３６−１の範囲内の数値とし、ｄを大きくした場合のパターン番号を２３６〜２３７−１の範囲内の数値とする。これにより、両者のパターン番号は重複しなくなり、同一画像について、二種類の異なる基準で二種類のパターン番号を生成できる。これにより、例えばノイズの影響を受けにくくなり、かつ不鮮明なエッジでも確実に検出できるようになる。
【００５２】
上述した例では、ｄの大きさを変えることで、二種類の重複しないパターン番号を生成したが、全く異なるアルゴリズムで複数種類のパターン番号を重複しないように生成してもよい。これらの異なるアルゴリズムで生成された複数種類のパターン番号を用いて一致点検出を行うことで、個々のアルゴリズムで生成したパターン番号を用いて一致点検出を行った場合に得られる効果を組み合わせた効果が得られる。
【００５３】
上述したように、パターン検出部１１は、３×３個のパターン番号素を含む画素ブロックを単位としてパターン検出処理を行うが、各パターン番号素は周囲の４画素のエッジ情報を考慮に入れた４ビットのビット列であり、結局、本実施形態では、縦６画素×横６画素の画素ブロックを単位としてパターン検出処理を行うことになる。
【００５４】
パターン検出部１１が一つの画素ブロックの処理が終了すると、次の画素ブロックのパターン検出処理を行うことになる。この場合、画素ブロックを画素単位でずらして新たな画素ブロックを設定するのが望ましいが、処理の簡略化と高速化の観点で、画素ブロック同士が重なり合わないように新たな画素ブロックを設定してもよい。
【００５５】
ただし、画像中のある物体が１画素だけ移動した場合を考えると、１画素単位で画素ブロックをずらしながらパターン検出処理を行わないと、その物体の移動を正しく検出できなくなる。したがって、画素ブロックの設定単位を間引く場合は、ローパスフィルタ処理等の何らかの画像処理を前段に設けるのが望ましい。
【００５６】
なお、パターン番号素は必ずしも４ビットのビット列である必要はないし、周辺の計４画素以外の画素情報を用いてパターン番号素を検出してもよい。また、パターン番号を検出する単位となる画素ブロックのサイズも、必ずしも３×３画素サイズには限定されない。
【００５７】
＜第１のパターン蓄積処理＞
次に、パターン蓄積部１２の処理動作を説明する。パターン蓄積部１２は、パターン検出部１１で検出されたパターン番号の数分の蓄積バッファ（不図示）を有する。図８は第１のパターン蓄積処理における蓄積バッファのデータ構造を示す図である。蓄積バッファは、パターン番号pat_idと、パターン位置x, yと、同じパターン番号のパターン情報を蓄積した回数を示す計数値cntとを格納する。
【００５８】
個々の蓄積バッファの計数値cntは、パターン情報の蓄積を開始する前に０に初期化される。蓄積バッファにパターン情報を格納する際には、同じパターン番号のパターン情報がすでに格納されているか否かを確認する。この確認処理は、計数値cntが０か否かで判断する。すでに格納されている場合、すなわち計数値cntが０以外の場合は、計数値cntをインクリメントする。なお、本明細書では、１だけ数を増やすことを単に「インクリメントする」と呼ぶ。
【００５９】
このとき、計数値cntが０であれば、蓄積バッファ内に新たなパターン番号pat_idと、対応するパターン位置x, yを格納し、計数値cntを１にする。
【００６０】
このような処理を繰り返して、画像内のすべての画素ブロックについて、パターン情報と計数値cntを蓄積バッファに格納し終えると、パターンの蓄積処理は終了する。
【００６１】
図９および図１０はパターン蓄積部１２が行う第１のパターン蓄積処理の一例を示すフローチャートである。まず、蓄積バッファ上の位置を表す変数ｉを０に初期化する（ステップＳ４１）。次に、ｉ番目の蓄積バッファstockの計数値cntを０に初期化する（ステップＳ４２）。次に、変数ｉをインクリメントする（ステップＳ４３）。次に、変数ｉが蓄積バッファstockの総数より小さいか否かを判定する（ステップＳ４４）。小さい場合はステップＳ４２に戻って、残りの蓄積バッファstockの係数値cntを初期化する。
【００６２】
変数ｉが蓄積バッファstockの総数以上であれば、蓄積バッファstockに格納したパターン番号pat_idの総数stock_maxを０に初期化する（ステップＳ４５）。
【００６３】
次に、パターン検出部１１で検出されたパターン番号上の位置を表す変数ｊを０に初期化する（ステップＳ４６）。次に、変数ｉを再度０に初期化する（ステップＳ４７）。
【００６４】
このように、ステップＳ４１〜Ｓ４７では、全ての蓄積バッファstockの初期化を行う。
【００６５】
次に、パターン検出部１１で検出されたパターン番号pat_idがｉ番目の蓄積バッファstockのパターン番号pat_idと一致するか否かを判定する（ステップＳ４８）。一致しない場合は、次の蓄積バッファstockを検出するために、変数ｉをインクリメントする（ステップＳ４９）。
【００６６】
次に、まだ比較していない蓄積バッファstockのパターン番号pat_idが残っているか否かを判定する（ステップＳ５０）。残っている場合は、ステップＳ４８に戻る。残っていない場合は、パターン検出部１１で検出されたパターン番号pat_idを新たな蓄積バッファに蓄積バッファに格納する（ステップＳ５１）。次に、そのパターン番号pat_idに対応するパターン位置を同じ蓄積バッファに格納する（ステップＳ５２）。そして、その蓄積バッファの計数値cntを１に設定する（ステップＳ５３）。次に、蓄積バッファの総数stock_maxをインクリメントする（ステップＳ５４）。
【００６７】
一方、ステップＳ４８で、一致すると判定された場合は、蓄積バッファstockの計数値cntをインクリメントする（ステップＳ５５）。
【００６８】
ステップＳ５４またはＳ５５の処理が終わると、変数ｊをインクリメントする（ステップＳ５６）。
【００６９】
次に、パターン検出部１１で検出されたパターン番号の総数が変数ｊより大きいか否かを判定する（ステップＳ５７）。大きい場合は、ステップＳ４７以降の処理を行う。大きくない場合は、蓄積処理を終了する。
【００７０】
＜第２のパターン蓄積処理＞
上述したパターン蓄積部１２内の各蓄積バッファは図８の情報を格納したが、格納する情報は図８に限定されない。図１１は第２のパターン蓄積処理における蓄積バッファのデータ構造を示す図である。図１１の蓄積バッファは、パターン番号pat_idと、パターン位置ｘの最大値max_xと、パターン位置ｙの最大値max_yと、パターン位置ｘの最小値min_xと、パターン位置ｙの最小値min_yと、パターン位置ｘの積算値sum_xと、パターン位置ｙの積算値sum_yと、格納した回数を示す計数値cntとを有する。
【００７１】
この場合の蓄積バッファも、パターン検出部１１で検出されたパターン番号の数分だけ設けられる。蓄積バッファへの格納を開始する前に、すべての蓄積バッファの計数値cntが０に初期化される。
【００７２】
パターン蓄積部１２は、蓄積バッファにパターン情報を格納する際には、同じパターン番号のパターン情報がすでに格納されているか否かを確認し、すでに格納されている場合には、新たに格納しようとするパターン位置x, yを、累積和sum_x, sum_yにそれぞれ加算する。また、このパターン位置xが最大値max_xより大きければmax_xをｘに置き換え、パターン位置ｙが最大値max_yより大きければmax_yをｙに置き換える。同様に、パターン位置ｘが最小値min_xより小さければmin_xをｘに置き換え、パターン位置ｙが最小値min_xより小さければmin_yをｙに置き換える。さらに、計数値cntをインクリメントする。
【００７３】
一方、上記確認を行った結果、まだ格納されていない場合は、新たな蓄積バッファのpat_idに格納対象のパターン番号pat_idを格納し、sum_x, max_x, min_xのいずれにも格納対象のパターン位置ｘを格納し、sum_y, max_y, min_yのいずれにも格納対象のパターン情報ｙを格納する。さらに、計数値cntを１に設定する。
【００７４】
このようにして、画像内のすべての画素ブロックについてのパターン情報を格納し終わったら、パターン蓄積処理は終了する。
【００７５】
図１２〜図１４はパターン蓄積部１２が行う第２のパターン蓄積処理の一例を示すフローチャートである。まず、蓄積バッファ上の位置を表す変数ｉを０に初期化する（ステップＳ６１）。次に、ｉ番目の蓄積バッファstockの計数値cntを０に初期化する（ステップＳ６２）。次に、変数ｉをインクリメントする（ステップＳ６３）。次に、変数ｉが蓄積バッファstockの総数未満か否かを判定する（ステップＳ６４）。総数未満の場合はステップＳ６２に戻る。
【００７６】
ステップＳ６４で、総数に達したと判定された場合は、パターン番号の総数stock_maxを０に初期化する（ステップＳ６５）。次に、パターン検出部１１で検出されたパターン番号上の位置を示す変数ｊを０に初期化する（ステップＳ６６）。次に、変数ｉを再度０に初期化する（ステップＳ６７）。
【００７７】
次に、パターン検出部１１で検出されたパターン情報のパターン番号pat_idが蓄積バッファstockのパターン番号pat_idと一致するか否かを判定する（ステップＳ６８）。一致する場合は、パターン検出部１１で検出されたパターン位置ｘをsum_xに加算し（ステップＳ６９）、パターン位置ｙをsum_yに加算する（ステップＳ７０）。
【００７８】
次に、パターン検出部１１で検出されたパターン位置ｘはmax_xより大きいか否かを判定し（ステップＳ７１）、大きい場合にはmax_xをｘに置き換える（ステップＳ７２）。
【００７９】
次に、パターン検出部１１で検出されたパターン位置ｘはmin_xより小さいか否かを判定し（ステップＳ７３）、小さい場合にはmin_xをｘに置き換える（ステップＳ７４）。
【００８０】
次に、パターン検出部１１で検出されたパターン位置ｙはmax_yより大きいか否かを判定し（ステップＳ７５）、大きい場合にはmax_yをｙに置き換える（ステップＳ７６）。
【００８１】
次に、パターン検出部１１で検出されたパターン位置ｙはmin_yより小さいか否かを判定し（ステップＳ７７）、小さい場合にはmin_yをｙに置き換える（ステップＳ７８）。
【００８２】
次に、蓄積バッファstockの計数値cntをインクリメントする（ステップＳ７９）。次に、変数ｊをインクリメントする（ステップＳ８０）。
【００８３】
次に、パターン検出部１１で検出されたパターン番号の総数が変数ｊより大きいか否かを判定する（ステップＳ８１）。大きくなければ処理を終了し、大きければステップＳ６７以降の処理を行う。
【００８４】
一方、上述したステップＳ６８で一致しないと判定されると、変数ｉをインクリメントする（ステップＳ８２）。次に、パターン検出部１１で検出されたパターン情報のパターン番号との比較をまだ行っていない蓄積バッファが残っているか否かを判定する（ステップＳ８３）。残っている場合にはステップＳ６８以降の処理を行う。残っていない場合は、パターン検出部１１で検出されたパターン番号pat_idを蓄積バッファに格納し（ステップＳ８４）、対応するパターン位置ｘをsum_x, max_x, min_xにそれぞれ格納する（ステップＳ８５〜Ｓ８７）。また、対応するパターン位置ｙをsum_y, max_y, min_yにそれぞれ格納する（ステップＳ８８〜Ｓ９０）。次に、計数値cntを１に設定し（ステップＳ９１）、蓄積バッファの種類を示す変数stock_maxをインクリメントし（ステップＳ９２）、その後にステップＳ８０以降の処理を行う。
【００８５】
＜第３のパターン蓄積処理＞
第２のパターン蓄積処理のように、パターン位置x, yの最大値と最小値を格納する代わりに、パターン位置ｘの２乗の積算値sum_x2とパターン位置ｙの２乗の積算値sum_y2を格納してもよい。
【００８６】
図１５は第３のパターン蓄積処理における蓄積バッファのデータ構造を示す図である。図示のように、蓄積バッファは、パターン番号pat_idと、パターン位置ｘの積算値sum_xと、パターン位置ｙの積算値sum_yと、パターン位置ｘの２乗の積算値sum_x2と、パターン位置ｙの２乗の積算値sum_y2と、蓄積バッファに格納した回数を示す計数値cntとを有する。
【００８７】
パターン蓄積部１２は、蓄積バッファにすでに格納されたデータが存在する場合は、sum_x, sum_yにそれぞれパターン位置x, yを加算し、sum_x2にｘの２乗を加算し、sum_y2にｙの２乗を加算し、計数値cntをインクリメントする。
【００８８】
蓄積バッファにまだ格納されていないパターン番号の場合は、新たな蓄積バッファのパターン番号pat_idに、格納対象のパターン情報のpat_idを格納し、sum_x, sum_yに格納対象のパターン情報のパターン位置x, yをそれぞれ格納し、sum_x2, sum_y2に格納対象のパターン情報のｘの２乗とｙの２乗をそれぞれ格納し、cntを１に設定する。このようにして、画像内のすべての検出位置のパターン情報を格納し終えたら、パターン蓄積処理は終了する。
【００８９】
図１６〜図１８はパターン蓄積部１２が行う第３のパターン蓄積処理の一例を示すフローチャートである。ステップＳ１０１〜Ｓ１１０は図１２および図１３のステップＳ６１〜Ｓ７０と共通するため、説明を省略する。
【００９０】
ステップＳ１１０の処理が終わると、パターン位置ｘの２乗をsum_x2に加算する（ステップＳ１１１）。次に、パターン位置ｙの２乗をsum_y2に加算する（ステップＳ１１２）。その後、ステップＳ１１３〜Ｓ１１９は、図１３および図１４のステップＳ７９〜Ｓ８５と共通するため、説明を省略する。
【００９１】
ステップＳ１１９の処理が終わると、次に、対応するパターン位置ｙをsum_yに格納し（ステップＳ１２０）、対応するパターン位置ｘの２乗をsum_x2に格納し（ステップＳ１２１）、対応するパターン位置ｙの２乗をsum_y2に格納する（ステップＳ１２２）。その後、計数値cntを１に初期化し（ステップＳ１２３）、蓄積バッファの種類を示す変数stock_maxをインクリメントする（ステップＳ１２４）。
【００９２】
ステップＳ１２４の後にステップＳ１１４に移行する。
【００９３】
以上で、パターン蓄積部１２の処理動作の説明は終りである。次に、特徴点抽出部１３の処理動作を説明する。特徴点抽出部１３の処理動作として、以下の第１〜第３の特徴点抽出処理が考えられる。
【００９４】
＜第１の特徴点抽出処理＞
第１の特徴点抽出処理は、図８のデータ構造の蓄積バッファに対応するものであり、第１のパターン蓄積処理の後に行われる。特徴点抽出部１３は、図８のデータ構造の蓄積バッファを走査し、計数値cntが１の情報を抽出して、特徴点バッファ（不図示）に格納する。
【００９５】
図１９は第１の特徴点抽出処理における特徴点バッファのデータ構造を示す図である。図１９の特徴点バッファには、パターン番号pat_idと、パターン位置ｘと、パターン位置ｙとが格納される。
【００９６】
図２０は第１の特徴点抽出処理の一例を示すフローチャートである。まず、蓄積バッファstock上の位置を示す変数ｉと、特徴点バッファpatinfo上の位置を示す変数ｊをともに０に初期化する（ステップＳ１３１）。
【００９７】
次に、ｉ番目の蓄積バッファ内の計数値cntが１か否かを判定する（ステップＳ１３２）。１であれば、その蓄積バッファ内のパターン番号pat_idとパターン位置x, yを、特徴点バッファpatinfoに格納する（ステップＳ１３３、Ｓ１３４）。続いて、変数ｊとｉをインクリメントする（ステップＳ１３５、Ｓ１３６）。
【００９８】
次に、変数ｉが蓄積バッファの総数未満か否かを判定し（ステップＳ１３７）、総数未満であれば、ステップＳ１３２に移行し、総数に達すると処理を終わる。
【００９９】
＜第２の特徴点抽出処理＞
第２の特徴点抽出処理は、図１１のデータ構造の蓄積バッファに対応するものであり、第２のパターン蓄積処理の後に行われる。特徴点抽出部１３は、図１１のデータ構造の蓄積バッファを走査し、計数値cntが１の蓄積バッファか、あるいは以下の３つの条件を満たす蓄積バッファを抽出する。そして、抽出した蓄積バッファ内の情報を特徴点バッファに格納する。
１）計数値cntが２以上
２）最大値max_x−最小値min_x＜ｄｘ
３）最大値max_y−最小値min_y＜ｄｙの情報
【０１００】
第２の特徴点抽出処理における特徴点バッファのデータ構造は図１９と同じであるが、パターン位置ｘには、パターン位置ｘの総和sum_xを計数値cntで割った値sum_x／cntが格納され、パターン位置ｙには、パターン位置ｙの総和sum_yを計数値cntで割った値sum_y／cntが格納される。
【０１０１】
ここで、上述したｄｘ、ｄｙは、特徴点か否かを判断するための閾値である。画像中の離れた場所に同一パターンが存在する場合は、そのパターンは特徴点として機能しない可能性が高いので、排除する。一方、同一パターンが画像中の狭い範囲内しか存在しない場合は、そのパターンを特徴点とみなして、同一パターンの検出位置を平均化した位置を、そのパターン位置とする。
【０１０２】
このような処理は、焦点が合っていないぼやけた部分では、近接した位置に同一パターンが発見されることが多いことへの対応策である。
【０１０３】
複数の画像を合成する場合など、画像の一致をより厳密に行うために画像全域で一致点をなるべく多く見つけ出したい場合には、ｄｘとｄｙに例えば１〜５程度の数値を与えて実行するのが望ましい。
【０１０４】
また、手ぶれ補正など、それほど多くの一致点を検出しなくて済む場合は、ｄｘとｄｙを０に設定すれば、画像中の一箇所のみに存在した画素配置を抽出することになる。この場合は、第１の特徴点抽出処理と等価な処理となるため、処理コストの少ない第１の特徴点抽出処理を実行するのが望ましい。
【０１０５】
図２１は第２の特徴点抽出処理の一例を示すフローチャートである。まず、蓄積バッファstock上の位置を示す変数ｉと、特徴点バッファpatinfo上の位置を示す変数ｊをともに０に初期化する（ステップＳ１４１）。
【０１０６】
次に、ｉ番目の蓄積バッファstock内の計数値cntが１か、あるいは、max_x−min_x＜ｄｘかつmax_y−min_y＜ｄｙかを判定する（ステップＳ１４２）。ステップＳ１４２の判定がＹｅｓの場合は、ｊ番目の特徴点バッファpatinfoに、ｉ番目の蓄積バッファstock内のパターン番号pat_idを格納する（ステップＳ１４３）。次に、同じ特徴点バッファpatinfoに、同じ蓄積バッファstock内の情報を用いて計算されたsum_x／cntとsum_y／cntを格納する（ステップＳ１４４、Ｓ１４５）。
【０１０７】
次に、変数ｊ、ｉをインクリメントする（ステップＳ１４６、Ｓ１４７）。次に、変数ｉが蓄積バッファの総数に達したか否かを判定し（ステップＳ１４８）、達していなければ、ステップＳ１４２以降の処理を行い、達した場合は処理を終了する。
【０１０８】
＜第３の特徴点抽出処理＞
第３の特徴点抽出処理は、図１５のデータ構造の蓄積バッファに対応するものであり、第３のパターン蓄積処理の後に行われる。特徴点抽出部１３は、図１５のデータ構造の蓄積バッファを走査し、計数値cntが１の蓄積バッファか、あるいは以下の３つの条件を満たす蓄積バッファを抽出する。そして、抽出した蓄積バッファ内の情報を特徴点バッファに格納する。
１）計数値cntが２以上
２）標準偏差stdev_x＝√((cnt＊sum_x2−sum_x＊sum_x)／cnt／(cnt−1)＜ｄｘ
３）標準偏差stdev_y＝√((cnt＊sum_y2−sum_y＊sum_y)／cnt／(cnt−1)＜ｄｙ
【０１０９】
第３の特徴点抽出処理における特徴点バッファのデータ構造は図１９と同じであるが、パターン位置ｘにはsum_x／cntが格納され、パターン位置ｙにはsum_y／cntが格納される。すなわち、第２の特徴点抽出処理と同様である。
【０１１０】
第３の特徴点抽出処理も、第２の特徴点抽出処理と同様に、画像中の近接した場所のみに同一パターンが存在する場合には特徴点とみなす。近接した場所かどうかを判断するためにパターン位置x, yの標準偏差stdev_x, stdev_yを閾値と比較する点が第２の特徴点抽出処理と異なる。
【０１１１】
図２２は第３の特徴点抽出処理の一例を示すフローチャートである。蓄積バッファstockの種類を示す変数ｉと、特徴点バッファpatinfoの種類を示す変数ｊをともに０に初期化する（ステップＳ１５１）。
【０１１２】
次に、ｉ番目の蓄積バッファstock内の計数値cntが１か否かを判定する（ステップＳ１５２）。１であれば、ｊ番目の特徴点バッファに、ｉ番目の蓄積バッファ内のパターン番号pat_idと、sum_x／cntと、sum_y／cntとを格納する（ステップＳ１５３〜Ｓ１５５）。
【０１１３】
次に、変数ｉ，ｊをインクリメントする（ステップＳ１５６，Ｓ１５７）。次に、変数ｉが蓄積バッファの総数に達したか否かを判定し（ステップＳ１５８）、達していなければステップＳ１５２に戻り、達した場合には処理を終了する。
【０１１４】
一方、ステップＳ１５２で１でないと判定された場合は、標準偏差stdev_x＝√((cnt＊sum_x2−sum_x＊sum_x)／cnt／(cnt−1)＜ｄｘか否かを判定する（ステップＳ１５９）。判定がＹｅｓの場合は、標準偏差stdev_y＝√((cnt＊sum_y2−sum_y＊sum_y)／cnt／(cnt−1)＜ｄｙか否かを判定する（ステップＳ１６０）。
【０１１５】
ステップＳ１６０でＹｅｓと判定された場合はステップＳ１５３に移行し、ステップＳ１５９またはＳ１６０でＮｏと判定された場合はステップＳ１５７に移行する。
【０１１６】
上述した第１、第２または第３の特徴点抽出処理によって、特徴点バッファに格納されたデータが特徴点パターン情報patInfoとなる。
【０１１７】
＜パターン観測確率算出処理＞
上述したパターン蓄積部１２は、パターン番号を検出すべきビットマップ画像の全画素数分の蓄積バッファを設けることを念頭に置いた。ところが、実際には、同じパターン番号を持つ画素ブロックのパターン情報は同じ蓄積バッファに格納されるため、必ずしも、ビットマップ画像の全画素数分の蓄積バッファを用意する必要はない。この場合、蓄積バッファの数を予め制限して、すべての蓄積バッファを使い終わった時点でパターン蓄積部１２の蓄積処理を終了するか、あるいは蓄積バッファに格納するパターン情報を予め制限して、有用なパターン情報のみを蓄積バッファに格納してもよい。
【０１１８】
画素ブロック内のパターン番号の観測確率を予め予測して、観測確率が低いパターン画像に関するパターン情報のみを蓄積することで、蓄積されるパターン情報の数を減らすことも考えられる。観測確率が低いパターン画像のみに限定する理由は、観測確率の低いパターン番号はまれにしか出現しないことを意味するから、特徴的である可能性が高いためである。
【０１１９】
このようなパターン画像の観測確率の予測は、上述したパターン蓄積部１２が処理を行う前に行う必要がある。図２３はパターン画像の観測確率の予測処理を行うパターン確率算出部１５を備えた画像一致点検出装置１０の内部構成の一例を示すブロック図である。図示のように、パターン検出部１１とパターン蓄積部１２の間にパターン確率算出部１５が設けられ、これ以外の構成は図２と同じである。
【０１２０】
画像の中に、あるパターン番号のパターン画像が含まれる確率は、各画像ごとに異なるが、パターン確率算出部１５は、蓄積バッファの数を減らして処理の高速化を図るために設けられるものであり、単に蓄積バッファへのパターン情報の格納を行うか否かを示す情報のみを出力すればよい。
【０１２１】
本実施形態では、６×６＝３６画素からなる画素ブロックを、３×３＝９個のパターン番号素の組合せで表現している。したがって、各パターン番号素が観測される確率を９個分掛け合わせて得られる乗算値を閾値と比較することにより、その画素ブロックのパターン情報を蓄積するべきか否かを判断すればよい。
【０１２２】
パターン番号素は、０〜１５の数値を取り得るため、予め代表的な画像について、各パターン番号素の観測確率を求めて、テーブル化しておく。図２４はパターン番号素と観測確率との対応関係を示すテーブルの一例を示す図である。このようなテーブルをルックアップテーブル（以下、ＬＵＴ）として参照することで、容易に観測確率を算出できる。
【０１２３】
図２５はパターン確率算出部１５が行う処理の一例を示すフローチャートである。このフローチャートは、パターン番号を検出する単位である画素ブロックごとに行われる。まず、パターン番号素の種類を表す変数ｉｄｓを初期化する（ステップＳ１６１）。ここでは、新たなパターン番号素の値pat_idを変数ｉｄｓに代入する。
【０１２４】
次に、パターン観測確率pat_probを１に初期化する（ステップＳ１６２）。次に、確率を求めたパターン番号素の総数を表す変数ｉを０に初期化する（ステップＳ１６３）。
【０１２５】
次に、変数ｉｄｓを１６で割った余りを変数ｎに代入する（ステップＳ１６４）。次に、変数ｉｄｓに対応する確率LUT(u)をＬＵＴから参照し、パターン観測確率pat_probと掛け合わせる（ステップＳ１６５）。次に、変数ｉｄｓを更新するために、（ids−ｎ）／１６を変数ｉｄｓに代入する（ステップＳ１６６）。次に、変数ｉをインクリメントする（ステップＳ１６７）。
【０１２６】
次に、変数ｉがパターン番号素の総数に達したか否かを判定する（ステップＳ１６８）。達していなければステップＳ１６４以降の処理を行う。変数ｉがパターン番号素の総数に達した場合は、パターン観測確率pat_probが求まったことを示しており、このパターン観測確率pat_probが予め定めた閾値未満か否かを判定する（ステップＳ１６９）。
【０１２７】
パターン観測確率pat_probが閾値未満であれば、上述した第１，第２または第３のパターン蓄積処理を行う（ステップＳ１７０）。一方、閾値以上であれば、その画素ブロックのパターン情報はパターン蓄積部１２には蓄積しないものと決定する（ステップＳ１７１）。
【０１２８】
図２５の処理では、パターン観測確率pat_probの大きさにより、パターン蓄積を行うか否かを判断している。ところが、画像によっては、細かな模様が数多く含まれているものや、逆にコントラストが低い画像や夜景のように暗い画像もある。したがって、図２５の処理では、細かな模様が数多く含まれている画像は数多くのパターン情報が蓄積され、コントラストが低い画像等はあまり蓄積されない結果となる。
【０１２９】
パターン蓄積部１２内の蓄積バッファをできるだけ最大限使うためには、画像の種類ごとに異なる適切な閾値を設定しなければならないが、そのためには、閾値を決定する処理を別個に行わなければならず、処理速度の高速化という観点から不利である。
【０１３０】
そこで、図２５の処理によって得られたパターン観測確率pat_probを複数の段階に分類し（段階分類部）、各段階ごとに蓄積バッファを設けて、蓄積バッファを使用するか否かを各段階ごとに判断することで、蓄積バッファの使用量を制限することが考えられる。
【０１３１】
この場合、対応する段階またはそれ以下の段階に属する特徴点パターン情報の候補の数を計測する（特徴点候補計数部）。次に、特徴点パターン情報の候補のパターン番号と、同一のパターン番号の出現回数と、各パターン番号に対応するパターン位置に関する情報とを、複数の蓄積バッファに分けて格納するようにする。その際、特徴点候補計数部で計測された数が所定の閾値未満であれば、対応する蓄積バッファへの格納を許可し、特徴点候補計測部で計測された数が閾値より大きければ、対応する段階以上（つまり、観測確率の高い段階）のすべての蓄積バッファへの格納を禁止する。図２６Ａ、図２６Ｂ、図２６Ｃおよび図２６Ｄはこの種の蓄積制御処理の一例を示すフローチャートである。
【０１３２】
図２６Ａは、図９のステップＳ４２、図１２のステップＳ６２または図１６のステップＳ１０２の処理に代わるものであり、段階ごとに設けられる複数の蓄積バッファをすべてクリアする処理を行う。
【０１３３】
まず、段階を表す変数ｋを０に設定する（ステップＳ４２−１）。次に、ｋ番目の段階の蓄積バッファstockを使用すべく、stockポインタを設定する（ステップＳ４２−２）。
【０１３４】
次に、ｋ番目の段階のｉ番目の蓄積バッファstockの計測数cntを０に設定（クリア）する（ステップＳ４２−３）。次に、変数ｋをインクリメントし（ステップＳ４２−４）、すべての段階（例えば、１６段階）の蓄積バッファstockすべてをクリアしたか否かを判定し、判定がＮｏの場合はステップＳ４２−２に戻り、Ｙｅｓの場合は図９のステップＳ４３、図１２のステップＳ６３または図１６のステップＳ１０３に移行する。
【０１３５】
図２６Ｂは、図９のステップＳ４６、図１２のステップＳ６６または図１６のステップＳ１０６の処理に代わるものであり、すべての段階の特徴点パターン情報の候補数（以下、特徴点候補数）ccntと蓄積バッファへの格納を許可するか否かを設定するための蓄積許可フラグFlagを初期化する。
【０１３６】
まず、パターン検出部１１で検出されたパターン番号上の位置を表す変数ｊを０に設定する（ステップＳ４６−１）。次に、段階を表す変数ｋを０に設定する（ステップＳ４６−２）。次に、ｋ番目の段階の特徴点候補数ccnt[k]を０に設定する（ステップＳ４６−３）。次に、ｋ番目の段階の蓄積許可フラグFlag[k]を許可状態（例えば１）に設定する（ステップＳ４６−４）。次に、変数ｋをインクリメントする（ステップＳ４６−５）。
【０１３７】
次に、１６段階全ての特徴点候補数ccnt[k]と蓄積許可フラグFlag[k]を初期化したか否かを判定し（ステップＳ４６−６）、判定がＮｏの場合はステップＳ４６−３に戻り、判定がＹｅｓの場合は、図９のステップＳ４７、図１２のステップＳ６７または図１６のステップＳ１０７の処理を行う。
【０１３８】
図２６Ｃは、図９のステップＳ４７、図１２のステップＳ６７または図１６のステップＳ１０７の処理に代わるものであり、蓄積許可フラグFlagが許可状態のときのみ、蓄積バッファへの格納を行うものである。
【０１３９】
まず、蓄積バッファstock上の位置を示す変数ｉを０に設定する（ステップＳ４７−１）。次に、パターン番号pat_id[j]からパターン観測確率pat_probを算出する（ステップＳ４７−２）。ここでは、図２５の処理を実行する。
【０１４０】
次に、算出したパターン観測確率pat_probから段階LEVを算出する（ステップＳ４７−３）。パターン観測確率pat_probの最大値は５３９であり、log１０５３９＝約１５であるため、段階LEVは、０〜１５の範囲内の１６段階を示す値となる。
【０１４１】
次に、段階LEVの蓄積バッファへの格納が許可されているか否かを判定する（ステップＳ４７−４）。ここでは、蓄積許可Flagの値で判断する。許可されていなければ、図１０のステップＳ５６、図１３のステップＳ８０または図１７のステップＳ１１４に移行し、許可されていれば、LEV番目の段階の蓄積バッファにパターン番号等を格納する設定を行う（ステップＳ４７−５）。その後、図１０のステップＳ４８、図１２のステップＳ６８または図１７のステップＳ１０８の処理を行う。
【０１４２】
図２６Ｄは、図１０のステップＳ５５、図１３のステップＳ７９または図１７のステップＳ１１３の処理に代わるものであり、パターン検出部１１で検出されたパターン番号pat_idがｉ番目の蓄積バッファstockのパターン番号pat_idと一致した場合には、特徴点パターン情報ではなくなることから、特徴点候補数ccnt[LEV]をデクリメントするものである。
【０１４３】
まず、計数値cntをインクリメントし（ステップＳ５５−１）、次に、特徴点候補数ccnt[LEV]をデクリメントする（ステップＳ５５−２）。その後、図１０のステップＳ５６、図１３のステップＳ８０または図１７のステップＳ１１４の処理を行う。
【０１４４】
図２６Ｅは、図１０のステップＳ５４、図１４のステップＳ９２または図１８のステップＳ１２４の処理に代わるものであり、特徴点候補数が閾値以上か否かを判定して、蓄積バッファ部への格納制御と蓄積許可フラグFlagの設定を行う。
【０１４５】
まず、蓄積バッファ部の総数stock_maxをインクリメントする（ステップＳ５４−１）。次に、段階LEVの特徴点候補数ccnt[LEV]をインクリメントする（ステップＳ５４−２）。次に、各段階の特徴点候補数数ccnt[LEV]の和を求める計数値sum_ccntに、ccnt[LEV]を代入する（ステップＳ５４−３）。
【０１４６】
次に、段階を表す変数ｋを０に設定する（ステップＳ５４−４）。次に、計数値sum_ccntに、ｋ段階の特徴点候補数を加算する（ステップＳ５４−５）。次に、変数ｋをインクリメントする（ステップＳ５４−６）。
【０１４７】
次に、段階LEVよりもパターン観測確率の低い段階の特徴点候補数の加算が終了したか否かを判定する（ステップＳ５４−７）。この判定がＮｏであればステップＳ５４−５に戻り、Ｙｅｓであれば、特徴点候補数の和sum_ccntが閾値以上か否かを判定する（ステップＳ５４−８）。
【０１４８】
ステップＳ５４−８の判定がＹｅｓであれば、変数ｋを次の段階の値に設定する（ステップＳ５４−９）。次に、段階ｋの蓄積許可フラグFlagを０に設定する（ステップＳ５４−１０）。次に、変数ｋをインクリメントする（ステップＳ５４−１１）。
【０１４９】
次に、パターン観測確率が最も高い段階まで処理したか否かを判定し（ステップＳ５４−１２）、判定がＮｏであればステップＳ５４−１０に戻り、判定がＹｅｓの場合、あるいはステップＳ５４−８の判定がＮｏの場合は、図１０のステップＳ５５、図１３のステップＳ８０または図１７のステップＳ１１４に移行する。
【０１５０】
＜一致点検出処理＞
次に、一致点検出処理について説明する。まずは、２つの画像から抽出された特徴点の情報を利用して一致点を検出する例を説明する。３つ以上の画像間での一致点検出は、そのうちの２つの画像について、まず一致点の検出を行い、その検出結果と、まだ一致点検出を行っていない残りの一つの画像との間で一致点を検出し、その検出結果を利用して、さらに残りの一つの画像との間で一致点検出を行うといった処理を繰り返せばよい。
【０１５１】
話を戻して、２つの画像間での一致点の検出処理について説明する。ここで、画像Ａから得られた特徴点パターン情報をpatInfoA、画像Ｂから得られた特徴点パターン情報をpatInfoBとする。
【０１５２】
特徴点パターン情報patInfoAに、複数の特徴点に関するパターン情報が格納されている場合には、その一つ一つのパターンに対応するパターン番号を、特徴点パターン情報patInfoBに格納されているすべての特徴点パターン情報のパターン番号と照合し、共通して含まれるパターン番号と、そのパターン位置とを抽出する。
【０１５３】
ここで、特徴点パターン情報patInfoAから抽出されたパターン位置をａ、特徴点パターン情報patInfoBから抽出されたパターン位置をｂとすると、画像Ａでは位置ａに写っていたものが画像Ｂでは位置ｂに写っていたことになる。
【０１５４】
このようにして、共通するパターン番号を持つ特徴点パターン情報をすべて抽出することにより、画像ＡとＢの間での対応する位置情報を複数得ることができる。もちろん、場合によっては、一つしか得られない場合や、一つも得られない場合もあり得る。
【０１５５】
一致点検出部１４は、上記の処理手順で図２７のような一致点情報を検出する。図２７の一致点情報は、パターン番号pat_idと、画像Ａの位置ｘの値ｘ０と、同画像Ａの位置ｙの値ｙ０と、画像Ｂの位置ｘの値ｘ１と、同画像Ｂの位置ｙの値ｙ１とを有する。
【０１５６】
ここで、パターン番号pat_idは、さらに別の画像との間で一致点検出を行う場合には必要となるが、２つの画像間での一致点検出だけを行うのであれば、必ずしも必要ない。
【０１５７】
図２８は一致点検出部１４が行う一致点検出処理の一例を示すフローチャートである。まず、画像Ａに対して、上述した第１、第２または第３の特徴点抽出処理を行って得た特徴点パターン情報patInfoAを取得する（ステップＳ１９１）。同様に、画像Ｂに対しても特徴点パターン情報patInfoBを取得する（ステップＳ１９２）。
【０１５８】
次に、特徴点パターン情報patInfoA上の位置を表す変数ｉと、一致点の数を表す変数ｋをともに０に初期化する（ステップＳ１９３）。同様に、特徴点パターン情報patInfoB上の位置を表す変数ｊを０に初期化する（ステップＳ１９４）。
【０１５９】
次に、ｉ番目の特徴点パターン情報patInfoAのパターン番号と、ｊ番目の特徴点パターン情報patInfoBのパターン番号とが一致するか否かを判定する（ステップＳ１９５）。両者が一致しない場合は、変数ｊをインクリメントする（ステップＳ１９６）。変数ｊが特徴点パターン情報patInfoBの総数に達したか否かを判定する（ステップＳ１９７）。達しなかった場合はステップＳ１９５以降の処理を行い、達した場合は変数ｉをインクリメントする（ステップＳ１９８）。
【０１６０】
変数ｉは特徴点パターン情報patInfoAの総数に達したか否かを判定する（ステップＳ１９９）。達していなければステップＳ１９４以降の処理を行い、達した場合は処理を終わる。
【０１６１】
一方、ステップＳ１９５で両者のパターン番号が一致したと判定されると、図２７のような一致点情報を追加する（ステップＳ２００）。次に、一致点情報の数を表す変数ｋをインクリメントし（ステップＳ２０１）、ステップＳ１９８以降の処理を行う。
【０１６２】
＜画像の移動、回転、拡縮＞
一致点検出部１４により検出された一致点情報は、種々の目的で利用できるが、ここでは、２つの画像Ａ，Ｂ間の一致点検出情報に基づいて、画像Ａが画像Ｂに近づくように、画像Ａの移動、回転および拡縮の少なくとも一つの処理を行う例を説明する。
【０１６３】
画像Ａ中の座標(x, y)に対して何らかの座標変換を行った後の座標を(x', y')とする。
【０１６４】
例えば、座標(x, y)を移動量dx, dyで平行移動した後の座標(x', y')は、以下の（６）式で表される。この（６）式では、変換元の二次元座標に、ｚ＝１を補って３次元のベクトルとして、３×３の行列Ｇを用いて変換を行う。
【数１】
【０１６５】
座標(x, y)を原点の回りにθ度回転させた後の座標(x', y')は、以下の（７）式で表される。
【数２】
【０１６６】
座標(x, y)を原点を不動点とする拡縮率ｆで拡縮した後の座標(x', y')は、以下の（８）式で表される。
【数３】
【０１６７】
上述した（６）〜（８）式を組み合わせた変換式は、以下の（９）式で表される。
【数４】
【０１６８】
上記（９）式の右辺の３×３行列を３つ乗算して得られる行列Ｇは、移動、回転および拡縮の処理をまとめて実施するものである。
【０１６９】
ここで、ｐ＝(x, y)からｑ＝(x', y')の変換をｇとしたときに、ｑ＝ｇ(ｐ)と表すことにする。
【０１７０】
ここで、一致点検出部１４で検出された一致点情報のｎ番目の画像Ａ上の位置をＡn、画像Ｂ上の対応位置をＢnとすると、
Ｂ0＝ｇ(Ａ0)
Ｂ1＝ｇ(Ａ1)
…
Ｂn＝ｇ(Ａn)
となる変換ｇを求めれば、変換ｇの具体的内容である移動量dx, dyや、回転角度θ、拡縮率ｆを検出できる。
【０１７１】
あるいは、ベクトルｖの長さの二乗をLen2(v)と表記する。このLen2(v)は、ベクトルｖ同士の内積により算出可能である。このLen2(v)を用いると、画像Ａの位置と対応する画像Ｂの位置の距離の二乗和は、以下の（１０）式で表される。
Len2(Ｂ0−ｇ(Ａ0))＋Len2(Ｂ1−ｇ(Ａ1))＋…＋Len2(Ｂn−ｇ(Ａn)) …（１０）
【０１７２】
（１０）式が小さくなるように、変換ｇの移動量dx, dyと、回転角度θと、拡縮率ｆとを求めれば、移動量、回転量および拡縮率を算出できる。
（１０）式の計算は、いわゆる収束計算によって行えばよい。
【０１７３】
あるいは、行列Ｇの代わりに、下記のような行列Ｈを用いて処理を行う方法もある。
【０１７４】
変換後の位置Ｂ0＝Ｈ＊変換元の位置Ａ0
変換後の位置Ｂ1＝Ｈ＊変換元の位置Ａ1
…
変換後の位置Ｂn＝Ｈ＊変換元の位置Ａn …（１１）
【０１７５】
上記（１１）式は、変換前の位置０、１、…、ｎを列ベクトルに持つ３行ｎ＋１列の行列Ａに行列Ｈを乗算して、変換後の位置０、１、…、ｎを列ベクトルに持つ３行ｎ＋１列の行列Ｂを得るものであり、Ｂ＝Ｈ＊Ａで表すことができる。
【０１７６】
通常、逆行列とは、正方行列のみに存在するが、正方でないｎ＋１行３列の行列Ａinvが、Ａ＊Ａinv＝３×３の単位行列となるとき、Ａinvは疑似逆行列と呼ばれる。
【０１７７】
このＡinvを、上述したＢ＝Ｈ＊Ａの両辺に左側から掛け合わせると、以下の（１２）式が得られる。
Ｂ＊Ａinv＝Ｈ＊Ａ＊Ａinv …（１２）
Ａ＊Ａinvは単位行列であるため、上記（１２）式は（１３）式のように変換される。
Ｂ＊Ａinv＝Ｈ＊単位行列＝Ｈ …（１３）
【０１７８】
この（１３）式により、行列Ｈが確定する。行列Ｈにより行われる変換は、移動、回転、拡縮のみならず、より複雑な変換をも含む。Ｈによる変換は、上述したように、２次元座標を３次元のｚ＝１面に置き換えて空間一次変換を行うすべての自由度を含む変換である。この行列Ｈによる画像変換を行い、その結果に基づいて行列Ｈが求まってしまえば、移動、回転、拡縮、その他のすべての自由度を含む変換を行える。
【０１７９】
移動、回転、拡縮以外の変換としては、例えば、正方形を平行四辺形にするような変換や、縦と横で異なる倍率の拡縮なども行うことができる。これにより、例えば被写体が回転している方向だけに拡縮を行う場合に対しても追従でき、処理能力が許せば、行列Ｈを用いた手法の方が望ましいかもしれない。この場合は、Ｇを計算する必要はなくなる。
【０１８０】
一方、移動、回転、拡縮等の既存の画像処理系を利用する場合は、上述したように、行列Ｇの移動量dx, dy、回転角度θおよび拡縮率ｆを求めればよい。また、移動量dx, dy、回転角度θおよび拡縮率ｆのうち、少なくとも一つを処理するように設計してもよい。
【０１８１】
３つ以上の画像について、移動、回転または拡縮を行う場合も同様の手順で行列ＧまたはＨを求めればよい。例えば、画像Ａ，Ｂの他に画像Ｃがあり、画像Ｃ上の位置をＣ0〜Ｃnで表記する場合、上述した（１０）式の代わりに、以下の（１４）式を求める。
【０１８２】
Len2(Ｂ0−ｇ(Ａ0))＋Len2(Ｃ0−ｇ(Ａ0))＋Len2(Ｂ1−ｇ(Ａ1))＋Len2(Ｃ1−ｇ(Ａ1))＋…＋Len2(Ｂn−ｇ(Ａn))＋Len2(Ｃn−ｇ(Ａn)) …（１４）
上記（１４）式により、変換後の画像Ａと、画像ＢおよびＣとの一致点の距離の二乗の和を小さくするようにすれば、画像ＢとＣの平均的な位置に画像Ａを合わせることになる。さらに、画像Ｄとの一致点も処理すると、画像Ａを画像Ｂ，Ｃ，Ｄの平均的な位置に合わせることになる。この性質を利用すると、デジタルビデオカメラの手ぶれ補正処理に応用することができる。
【０１８３】
図２９は上述した一致点検出情報に基づく画像変換の手法を模式的に示す図である。図２９では、３つのコマ画像Ａ，Ｂ，Ｃの一致点を合わせて、一致点の位置が重なり合うように画像変換を行う例を示している。例えば、コマ画像Ａ，Ｂ，Ｃ中のりんごの部分が一致点として検出されたとする。この場合、上述した行列ＧまたはＨを用いて、画像変換が行われる。その後、画像変換後の３つのコマ画像中の一致点同士が重なり合うように画像合成が行われる。
【０１８４】
本実施形態をビデオカメラに適用する場合、各コマ（フレームまたはフィールド）画像に対して上述した第１、第２または第３の特徴点抽出処理を行い、最近の数コマ（例えば２〜６０コマ程度）を参照コマとして、直前のコマを処理対象とする。
【０１８５】
上述した（１４）式が小さくなるように処理を行うと、参照コマに対する平均的な位置に、処理対象コマが合致または近づくように変換が行われ、手ぶれによる画像の移動回転拡縮が平滑化されることになる。このことは、例えばフレームレートが３０コマ／秒のカメラで最近の３０コマを参照コマとして実行した場合、１秒分の動きが平滑化された映像に対して合わせられることを意味する。すなわち、細かな振動を画像から取り除くことになり、手ぶれまたは被写体ブレを緩和することができる。
【０１８６】
なお、参照コマから一致点検出を行う場合、特徴点パターン情報だけを保持しておけばよく、画像データ自体を保持する必要はない点でも本実施形態は優れている。例えば、参照コマ数が多いほど瞬間的な移動によるブレは平滑化されることになり、６０コマ程度に増やした場合でも、画像そのものを保持しておく必要はなく、メモリ消費も少なくて実装が容易である。
【０１８７】
従来のコマ間での移動情報（フレーム間差分による移動情報）を積算しながら処理する方式では、画像同士を比較するために、最近の画像と直前の画像とを比較するのが精一杯であり、フレーム間差分を最小化するように移動量などを計算していた。本実施形態によれば、誤差の蓄積を防止できるだけでなく、時間的に離れた複数のコマとの比較も行うため、検出精度が極めて高くなる。
【０１８８】
この結果、本実施形態によれば、手ぶれ補正効果が大きくなり、誤動作も少なくなる。また、移動だけでなく、カメラの傾き（回転）や前後またはズーム（拡縮）ブレも緩和できる。
【０１８９】
上述した手法により複数の画像の一致点検出と画像変換を行うことで、同一画素位置に同一の物体が写されるように変換することができる。このような画像変換処理を行うことで、種々の利点が得られる。
【０１９０】
一つには、ノイズの低減効果である。ランダムノイズは、不規則に発生するために低減が難しいノイズであるが、不規則に発生する性質を利用すると、複数の画像を重ね合わせることで、低減が可能である。このとき、画像を重ね合わせる手法には種々のものがあるが、以下では、平均化と中間値を算出する手法を説明する。
【０１９１】
画像変換された複数画像の同一画素位置を平均化して得られる画像は、同一の物体が同一の画像位置に写っているため、平均化によりその物体から得られる信号Ｓは変化しない。一方、ノイズは不規則であるため、平均化する画素数に応じて低減される。したがって、画像変換された複数画像を合成する場合は、平均化した画素数に応じてＳ／Ｎが向上し、ノイズを低減することができる。
【０１９２】
一方、ランダムノイズは不規則であり、正規分布することが予めわかっている。このため、画像変換された複数画像を合成する際に、中間値を用いることによってもノイズを低減できる。この場合、周辺の画素ではなく、複数画素の合成に応用しているため、中間値フィルタをかけた場合によく見られるように、画像のヌメヌメ感は発生するおそれはない。
【０１９３】
なお、上述した平均化の際に、必要に応じて重み付けを行ってもよい。以下では、重み付けの一例を説明する。
【０１９４】
露出を変えながら撮影された一連の画像を合成すると、ノイズを低減できる他に、ダイナミックレンジを拡大できるという効果がある。
【０１９５】
明るく撮影された画像の方がノイズが少ないため、平均時の重みを大きくし、暗く撮影されている画像では重みを小さくする。ただし、明るい画像中で色または輝度が飽和している部分は白とびが発生しているため、重みを０にする。
【０１９６】
輝度が次第に明るくなって、飽和に至るまでのグラデーション領域で、急激な重みの変化が発生することで違和感が出ないように、飽和点手前から徐々に重みを下げていく。
【０１９７】
このような重み付けを行うには、ピクセル値の大きさに応じて重みが増し、飽和点の手前から重みが減少し、飽和点で０になるような関数によって重みを算出するのが望ましい。この種の関数の具体的な実装例として、最も処理量が小さく、かつ自由度の高いものは、ルックアップテーブルである。
【０１９８】
図３０はルックアップテーブル（以下、ＬＵＴ）をグラフ化した一例を示す図である。図３０では、画素値を０〜２５５とし、重みの範囲も０〜２５５としている。Ｒ，Ｇ，Ｂの各色ごとに、個別あるいは共通のＬＵＴを引いて、画素値に対応する重みを設定すればよい。
【０１９９】
図３１は重み付けの一例を模式的に説明する図である。図３１は図２９で画像変換した後の３つのコマ画像のそれぞれに重み付けを行う例を示している。コマ画像中の特定画素位置について、コマ画像ごとに別個の重み付けを行う。例えば、コマ画像Ａの特定画素位置の画素値が１３０の場合、ＬＵＴを引くことにより、重み２００を取得する。同様に、コマ画像Ｂの特定画素位置の画素値が１２０であれば重み１９０を取得し、コマ画像Ｃの特定画素位置の画素値が１２５であれば重み１９５を取得する。そして、以下の（１５）式により、合成画素値を算出する。
【数５】
【０２００】
本実施形態をデジタルスチルカメラに適用すれば、露出違いで撮影された一連の画像からダイナミックレンジが広くて、かつ階調性が豊かで、ノイズも少ない画像を記録することができる。
【０２０１】
図３２は露出を変えながら撮影した３枚のコマ画像Ａ，Ｂ，Ｃの重み付けの一例を模式的に説明する図である。コマ画像Ａ，Ｂ，Ｃの順に露出が低くなっているものとする。コマ画像Ａ，Ｂは露出が高いため、一部が白飛びしている。白飛びしている画素領域（画素値＝２５５）は重みが０に設定され、この画素領域については、白飛びしていないコマ画像Ｃは０でないので、合成結果はＣの画像データが使われる。
【０２０２】
コマ画像Ｃは一部が黒つぶれしている。黒つぶれした画素領域は、黒つぶれしていないコマ画像ＡまたはＢの重みよりも小さく設定されるため、結果Ａが優先され、Ｂ，Ｃの順に低い重みで合成される。
【０２０３】
なお、上述した重みづけは他の画像には依存しないため、一連の映像を同時に参照せずに重みを決定でき、必要に応じて逐次重み付けを行いながら合成画像を蓄積することができる。これにより同時に必要な作業用メモリ量を削減できる。
【０２０４】
例えば、作業用メモリには、画素数分の画素の合計値SumR, SumG, SumB と重みの合計値 SumFact を格納し、０に初期化しておく。先の変換処理によって変換済みの映像が入力されたら各画素値から重み(Fact)を算出して、Ｒ画素値と重みFactの乗算値をSumRに足しこむ、同様に、Ｇ画素値と重みFactの乗算値をSumGに足しこむ。同様に、Ｂ画素値と重みFactをSumBに足しこむ。SumFact には Fact を足しこむ。
【０２０５】
このようにして、一連の画像のすべてのピクセルの足しこみ処理が完了したら、各画素の SumR, SumG, SumB を SumFact で除算して、平均化された画素値が得られる。
【０２０６】
なお、ここで SumFact で除算する代わりに、例えば SumFact/4 で除算すると、画像合成前の画像よりも４倍大きな画素値が得られる。例えば、４枚の画像を合成している場合には、４倍程度階調性が増しているので、４倍大きな画素値を取り出すことで、豊かな階調を得ることもできる。
【０２０７】
本実施形態の他の応用は、ピント位置を変化させながら撮影された一連の画像から、できるだけ広い範囲にピントがあった画像を生成することである。これもまた、画素毎に設定された重みによる加重平均を利用する。
【０２０８】
このとき、ピントが合っている箇所ほど大きな重みとなり、ピントが合っていない箇所ほど重みが小さくなるように重みづけされて平均化すれば良い。これにもさまざまな手法が考えられるが、以下では、高い周波数が含まれている部分ほどピントが合っていると判断し、大きな重みを設定する例を説明する。
【０２０９】
処理対象画像に対して、（１５）式の行列で表される高周波検出フィルタを通すと、高周波が多く含まれている部分ほど大きな値が算出される。
【数６】
【０２１０】
算出された値の絶対値または、２乗値を重みとすれば良い。この際、カラー画像であっても、Ｒ，Ｇ，Ｂごとに別個に処理を行う必要はなく、予めＲ，Ｇ，Ｂから輝度（例えば、輝度Y=(3R+6G+B)/10）を求めてからフィルタリングすると、全体の処理量が小さくなり有利である。
【０２１１】
なお、このフィルタリングは、あくまでも重みの算出のためのものであるから、ここでの輝度の計算は厳密である必要はない。処理量を少なくしたい場合には、さらに計算を簡略化しても構わない。(例:Y＝(R＋2G＋B)／4)
図３３はピント位置に合わせて重みを調整する手法を模式的に示す図である。コマ画像Ａは人間にピントが合っており、コマ画像Ｂは木にピントが合っており、コマ画像Ｃは山にピントが合っているものとする。したがって、人間の写っている画素領域では、コマ画像Ａの重みが大きくなり、木が写っている画素領域では、コマ画像Ｂの重みが大きくなり、山が写っている画素領域では、コマ画像Ｃの重みが大きくなる。
【０２１２】
これにより、近くから遠くまで全体的にピントが合った画像が得られる。
【０２１３】
上述したように、本実施形態によれば、少ない演算量かつ高速に精度の高い一致点を大量に検出することが可能であり、従来の方法の欠点である演算量という問題点を克服できる。局部的な画素値の相対的な大小関係を許容値（閾値）を考慮するため、画像のさまざまなノイズ（ランダムノイズ、圧縮時のブロックノイズやモスキートノイズ）だけでなく、画像の傾きや拡縮（像倍率の変化）に対しても寛容であり、画像１の位置ａは、画像２の位置ｂに対応するというようなベクトル情報を複数提供でき、平行移動だけでなく、回転や拡縮も検出でき、さらには、上述した特許文献３による３次元カメラベクトルを特定してさらに高度なブレ補正を行う用途にも応用可能である。また、高速であるが故に、１対複数画像での一致点検出や、複数対複数の一致点検出も短時間に終わらせることが可能であり、結果より多くの一致検出結果を得ることができ、さらには一致点検出の精度向上が見込める。
【０２１４】
本実施形態を応用することで、上述した一致点検出機能を持つ画像処理装置、デジタルスチルカメラおよびデジタルビデオカメラ等を提供することができるが、本実施形態の適用範囲はこれだけに留まらない。本実施形態では、処理量を増大させることなく、数多くの一致点を検出できるため、動画映像から動くものだけを発見する場合においても、より小さな移動体を検出できたり、精度が高いことから、それを追跡する場合においても有利である。対象物の動きに追従してズーミングしたり、車に搭載されたビデオカメラからの画像を処理して、近づく人間や物体を警告したり、入って来た人を追いかける監視カメラなど、応用範囲は広範囲に及ぶ。
【０２１５】
すなわち、本実施形態は、複数の画像から、精度の高い一致点を高速かつ少ない演算量で検出できるため、本実施形態を利用すれば、種々の特徴を持つ応用製品を生み出せる。
【０２１６】
本発明の態様は、上述した個々の実施形態に限定されるものではなく、当業者が想到しうる種々の変形も含むものであり、本発明の効果も上述した内容に限定されない。すなわち、特許請求の範囲に規定された内容およびその均等物から導き出される本発明の概念的な思想と趣旨を逸脱しない範囲で種々の追加、変更および部分的削除が可能である。
【０２１７】
上述した実施形態で説明した画像一致点検出装置の少なくとも一部は、ハードウェアで構成してもよいし、ソフトウェアで構成してもよい。ソフトウェアで構成する場合には、画像一致点検出装置の少なくとも一部の機能を実現するプログラムをフレキシブルディスクやＣＤ−ＲＯＭ等の記録媒体に収納し、コンピュータに読み込ませて実行させてもよい。記録媒体は、磁気ディスクや光ディスク等の着脱可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記録媒体でもよい。
【０２１８】
また、画像一致点検出装置の少なくとも一部の機能を実現するプログラムを、インターネット等の通信回線（無線通信も含む）を介して頒布してもよい。さらに、同プログラムを暗号化したり、変調をかけたり、圧縮した状態で、インターネット等の有線回線や無線回線を介して、あるいは記録媒体に収納して頒布してもよい。
【符号の説明】
【０２１９】
１ 撮像素子
２ Ａ／Ｄ変換器
３ 画像処理回路
４ 符号化装置
１０ 画像一致点検出装置
１１ パターン検出部
１２ パターン蓄積部
１３ 特徴点抽出部
１４ 一致点検出部
１５ パターン確率算出部
【特許請求の範囲】
【請求項１】
複数のビットマップ画像のそれぞれにおける複数画素からなる画素ブロックのパターン画像を、前記画素ブロック内の全画素のビット数の総和である本来の画素ビット数以下のビット数で画素ブロックの特徴を表す数値であるパターン番号で表現し、前記画素ブロックの前記パターン番号と前記画素ブロックの位置を表すパターン位置とを組にしたパターン情報を前記画素ブロックごとに検出するパターン検出部と、
前記複数のビットマップ画像のそれぞれに含まれる前記パターン情報を前記パターン番号により分類し、前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを格納するパターン蓄積部と、
前記複数のビットマップ画像のそれぞれについて、前記パターン蓄積部に格納された情報を用いて、前記パターン番号の出現回数が１回だけの前記パターン情報を特徴点パターン情報として抽出する特徴点抽出部と、
前記複数のビットマップ画像のそれぞれについて前記特徴点パターン情報として抽出された前記パターン情報の前記パターン番号が一致しているか否かを判断し、一致している前記パターン番号を含む複数の前記パターン情報を一致点情報として検出する一致点検出部と、を備えることを特徴とする画像一致点検出装置。
【請求項２】
前記パターン蓄積部は、前記パターン番号ごとに、同一の前記パターン番号を持つ前記パターン位置の和と、前記パターン位置の最大値と、前記パターン位置の最小値とを、前記パターン位置に関する情報として蓄積し、
前記特徴点抽出部は、対応する前記ビットマップ画像における前記パターン番号の出現回数が２回以上の場合には、前記パターン蓄積部に蓄積された前記最大値と前記最小値との差が所定の閾値未満か否かを前記パターン番号ごとに判断して、前記閾値未満と判断された前記パターン番号に対応する前記パターン情報を前記特徴点パターン情報として抽出し、該パターン番号に対応する前記パターン位置の和を該パターン番号の出現回数で除算して得られる位置の平均値を、前記特徴点パターン情報の前記パターン位置として抽出することを特徴とする請求項１に記載の画像一致点検出装置。
【請求項３】
前記パターン蓄積部は、前記パターン番号ごとに、同一の前記パターン番号を持つ前記パターン位置の和および前記パターン位置を各座標軸上の位置ごとに２乗して足し合わせた２乗和と、を前記パターン位置に関する情報として蓄積し、
前記特徴点抽出部は、対応する前記ビットマップ画像における前記パターン番号の出現回数が２回以上の場合には、前記パターン蓄積部に蓄積された同一の前記パターン番号を持つ前記パターン位置の和および２乗和と、該パターン番号の前記出現回数とを用いて標準偏差を算出し、該標準偏差が所定の閾値未満か否かを前記パターン番号ごとに判断して、前記閾値未満と判断された前記パターン番号に対応する前記パターン情報を前記特徴点パターン情報として抽出し、該パターン番号に対応する前記和を該パターン番号の出現回数で除算して得られる位置の平均値を、前記特徴点パターン情報の前記パターン位置として抽出することを特徴とする請求項１に記載の画像一致点検出装置。
【請求項４】
前記パターン検出部は、前記パターン画像を前記パターン番号に変換する際、前記パターン番号同士が重複しないように同一の前記パターン画像に対してそれぞれ異なる前記パターン番号を生成する複数のパターン番号変換部を有し、
前記パターン蓄積部は、前記複数のパターン番号変換部で生成された複数種類のパターン番号のそれぞれごとに、前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを蓄積することを特徴とする請求項１乃至３のいずれかに記載の画像一致点検出装置。
【請求項５】
前記パターン検出部で検出されるパターン番号が、基準となるビットマップ画像に含まれる確率を算出する確率算出部を備え、
前記パターン蓄積部は、前記確率が所定の閾値未満である前記パターン番号に対応する前記パターン情報のみを蓄積することを特徴とする請求項１乃至４のいずれかに記載の画像一致点検出装置。
【請求項６】
前記パターン蓄積部は、
前記確率をその大きさに応じて複数の段階に分類する段階分類部と、
前記複数の段階のそれぞれごとに設けられ、対応する段階またはそれ以下の前記確率の段階に属する前記特徴点パターン情報の候補の数を計測する特徴点候補計数部と、
前記複数の段階のそれぞれに対応して設けられ、前記特徴点パターン情報の候補の前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを格納する複数の蓄積バッファと、
前記特徴点候補計測部で計測された数が所定の閾値未満であれば、対応する前記蓄積バッファへの格納を許可し、前記特徴点候補計測部で計測された数が前記閾値以上であれば、対応する段階以上のすべての前記蓄積バッファへの格納を禁止するパターン蓄積制御部と、を有することを特徴とする請求項５に記載の画像一致点検出装置。
【請求項７】
前記特徴点パターン情報をそれぞれ含む２以上の画像の中の一つの画像を処理対象画像として選択し、前記特徴点パターン情報を含む他の画像を参照して、前記処理対象画像の前記特徴点パターン情報と前記他の画像の前記特徴点パターン情報との間で前記一致点検出を行い、検出された一致点情報に基づいて前記処理対象画像の移動、回転および拡縮処理の少なくとも一つを行って、前記処理対象画像のブレを補正するブレ補正部を備えることを特徴とする請求項１乃至６のいずれかに記載の画像一致点検出装置。
【請求項８】
複数のビットマップ画像のそれぞれにおける複数画素からなる画素ブロックのパターン画像を、前記画素ブロック内の全画素のビット数の総和である本来の画素ビット数以下のビット数で画素ブロックの特徴を表す数値であるパターン番号で表現し、前記画素ブロックの前記パターン番号と前記画素ブロックの位置を表すパターン位置とを組にしたパターン情報を前記画素ブロックごとに検出し、
前記複数のビットマップ画像のそれぞれに含まれる前記パターン情報を前記パターン番号により分類し、前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを格納し、
前記複数のビットマップ画像のそれぞれについて、前記パターン蓄積部に格納された情報を用いて、前記パターン番号の出現回数が１回だけの前記パターン情報を特徴点パターン情報として抽出し、
前記複数のビットマップ画像のそれぞれについて前記特徴点パターン情報として抽出された前記パターン情報の前記パターン番号が一致しているか否かを判断し、一致している前記パターン番号を一致点情報として検出することを特徴とする画像一致点検出方法。
【請求項９】
複数のビットマップ画像のそれぞれにおける隣接する複数画素からなる画素ブロックのパターン画像を、前記画素ブロック内の全画素のビット数の総和である本来の画素ビット数以下のビット数で画素ブロックの特徴を表す数値であるパターン番号で表現し、前記画素ブロックの前記パターン番号と前記画素ブロックの位置を表すパターン位置とを組にしたパターン情報を前記画素ブロックごとに検出し、
前記複数のビットマップ画像のそれぞれに含まれる前記パターン情報を前記パターン番号により分類し、前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを格納し、
前記複数のビットマップ画像のそれぞれについて、前記パターン蓄積部に格納された情報を用いて、前記パターン番号の出現回数が１回だけの前記パターン情報を特徴点パターン情報として抽出し、
前記複数のビットマップ画像のそれぞれについて前記特徴点パターン情報として抽出された前記パターン情報の前記パターン番号が一致しているか否かを判断し、一致している前記パターン番号を一致点情報として検出するプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
複数のビットマップ画像のそれぞれにおける複数画素からなる画素ブロックのパターン画像を、前記画素ブロック内の全画素のビット数の総和である本来の画素ビット数以下のビット数で画素ブロックの特徴を表す数値であるパターン番号で表現し、前記画素ブロックの前記パターン番号と前記画素ブロックの位置を表すパターン位置とを組にしたパターン情報を前記画素ブロックごとに検出するパターン検出部と、
前記複数のビットマップ画像のそれぞれに含まれる前記パターン情報を前記パターン番号により分類し、前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを格納するパターン蓄積部と、
前記複数のビットマップ画像のそれぞれについて、前記パターン蓄積部に格納された情報を用いて、前記パターン番号の出現回数が１回だけの前記パターン情報を特徴点パターン情報として抽出する特徴点抽出部と、
前記複数のビットマップ画像のそれぞれについて前記特徴点パターン情報として抽出された前記パターン情報の前記パターン番号が一致しているか否かを判断し、一致している前記パターン番号を含む複数の前記パターン情報を一致点情報として検出する一致点検出部と、を備えることを特徴とする画像一致点検出装置。
【請求項２】
前記パターン蓄積部は、前記パターン番号ごとに、同一の前記パターン番号を持つ前記パターン位置の和と、前記パターン位置の最大値と、前記パターン位置の最小値とを、前記パターン位置に関する情報として蓄積し、
前記特徴点抽出部は、対応する前記ビットマップ画像における前記パターン番号の出現回数が２回以上の場合には、前記パターン蓄積部に蓄積された前記最大値と前記最小値との差が所定の閾値未満か否かを前記パターン番号ごとに判断して、前記閾値未満と判断された前記パターン番号に対応する前記パターン情報を前記特徴点パターン情報として抽出し、該パターン番号に対応する前記パターン位置の和を該パターン番号の出現回数で除算して得られる位置の平均値を、前記特徴点パターン情報の前記パターン位置として抽出することを特徴とする請求項１に記載の画像一致点検出装置。
【請求項３】
前記パターン蓄積部は、前記パターン番号ごとに、同一の前記パターン番号を持つ前記パターン位置の和および前記パターン位置を各座標軸上の位置ごとに２乗して足し合わせた２乗和と、を前記パターン位置に関する情報として蓄積し、
前記特徴点抽出部は、対応する前記ビットマップ画像における前記パターン番号の出現回数が２回以上の場合には、前記パターン蓄積部に蓄積された同一の前記パターン番号を持つ前記パターン位置の和および２乗和と、該パターン番号の前記出現回数とを用いて標準偏差を算出し、該標準偏差が所定の閾値未満か否かを前記パターン番号ごとに判断して、前記閾値未満と判断された前記パターン番号に対応する前記パターン情報を前記特徴点パターン情報として抽出し、該パターン番号に対応する前記和を該パターン番号の出現回数で除算して得られる位置の平均値を、前記特徴点パターン情報の前記パターン位置として抽出することを特徴とする請求項１に記載の画像一致点検出装置。
【請求項４】
前記パターン検出部は、前記パターン画像を前記パターン番号に変換する際、前記パターン番号同士が重複しないように同一の前記パターン画像に対してそれぞれ異なる前記パターン番号を生成する複数のパターン番号変換部を有し、
前記パターン蓄積部は、前記複数のパターン番号変換部で生成された複数種類のパターン番号のそれぞれごとに、前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを蓄積することを特徴とする請求項１乃至３のいずれかに記載の画像一致点検出装置。
【請求項５】
前記パターン検出部で検出されるパターン番号が、基準となるビットマップ画像に含まれる確率を算出する確率算出部を備え、
前記パターン蓄積部は、前記確率が所定の閾値未満である前記パターン番号に対応する前記パターン情報のみを蓄積することを特徴とする請求項１乃至４のいずれかに記載の画像一致点検出装置。
【請求項６】
前記パターン蓄積部は、
前記確率をその大きさに応じて複数の段階に分類する段階分類部と、
前記複数の段階のそれぞれごとに設けられ、対応する段階またはそれ以下の前記確率の段階に属する前記特徴点パターン情報の候補の数を計測する特徴点候補計数部と、
前記複数の段階のそれぞれに対応して設けられ、前記特徴点パターン情報の候補の前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを格納する複数の蓄積バッファと、
前記特徴点候補計測部で計測された数が所定の閾値未満であれば、対応する前記蓄積バッファへの格納を許可し、前記特徴点候補計測部で計測された数が前記閾値以上であれば、対応する段階以上のすべての前記蓄積バッファへの格納を禁止するパターン蓄積制御部と、を有することを特徴とする請求項５に記載の画像一致点検出装置。
【請求項７】
前記特徴点パターン情報をそれぞれ含む２以上の画像の中の一つの画像を処理対象画像として選択し、前記特徴点パターン情報を含む他の画像を参照して、前記処理対象画像の前記特徴点パターン情報と前記他の画像の前記特徴点パターン情報との間で前記一致点検出を行い、検出された一致点情報に基づいて前記処理対象画像の移動、回転および拡縮処理の少なくとも一つを行って、前記処理対象画像のブレを補正するブレ補正部を備えることを特徴とする請求項１乃至６のいずれかに記載の画像一致点検出装置。
【請求項８】
複数のビットマップ画像のそれぞれにおける複数画素からなる画素ブロックのパターン画像を、前記画素ブロック内の全画素のビット数の総和である本来の画素ビット数以下のビット数で画素ブロックの特徴を表す数値であるパターン番号で表現し、前記画素ブロックの前記パターン番号と前記画素ブロックの位置を表すパターン位置とを組にしたパターン情報を前記画素ブロックごとに検出し、
前記複数のビットマップ画像のそれぞれに含まれる前記パターン情報を前記パターン番号により分類し、前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを格納し、
前記複数のビットマップ画像のそれぞれについて、前記パターン蓄積部に格納された情報を用いて、前記パターン番号の出現回数が１回だけの前記パターン情報を特徴点パターン情報として抽出し、
前記複数のビットマップ画像のそれぞれについて前記特徴点パターン情報として抽出された前記パターン情報の前記パターン番号が一致しているか否かを判断し、一致している前記パターン番号を一致点情報として検出することを特徴とする画像一致点検出方法。
【請求項９】
複数のビットマップ画像のそれぞれにおける隣接する複数画素からなる画素ブロックのパターン画像を、前記画素ブロック内の全画素のビット数の総和である本来の画素ビット数以下のビット数で画素ブロックの特徴を表す数値であるパターン番号で表現し、前記画素ブロックの前記パターン番号と前記画素ブロックの位置を表すパターン位置とを組にしたパターン情報を前記画素ブロックごとに検出し、
前記複数のビットマップ画像のそれぞれに含まれる前記パターン情報を前記パターン番号により分類し、前記パターン番号と、同一の前記パターン番号の出現回数と、それぞれの前記パターン番号に対応する前記パターン位置に関する情報とを格納し、
前記複数のビットマップ画像のそれぞれについて、前記パターン蓄積部に格納された情報を用いて、前記パターン番号の出現回数が１回だけの前記パターン情報を特徴点パターン情報として抽出し、
前記複数のビットマップ画像のそれぞれについて前記特徴点パターン情報として抽出された前記パターン情報の前記パターン番号が一致しているか否かを判断し、一致している前記パターン番号を一致点情報として検出するプログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６Ａ】
【図２６Ｂ】
【図２６Ｃ】
【図２６Ｄ】
【図２６Ｅ】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６Ａ】
【図２６Ｂ】
【図２６Ｃ】
【図２６Ｄ】
【図２６Ｅ】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【公開番号】特開２０１１−２２９０８０（Ｐ２０１１−２２９０８０Ａ）
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願番号】特願２０１０−９９０２９（Ｐ２０１０−９９０２９）
【出願日】平成２２年４月２２日（２０１０．４．２２）
【特許番号】特許第４６８９７５８号（Ｐ４６８９７５８）
【特許公報発行日】平成２３年５月２５日（２０１１．５．２５）
【出願人】（５９６０４６１１８）株式会社市川ソフトラボラトリー (19)
【Ｆターム（参考）】
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願日】平成２２年４月２２日（２０１０．４．２２）
【特許番号】特許第４６８９７５８号（Ｐ４６８９７５８）
【特許公報発行日】平成２３年５月２５日（２０１１．５．２５）
【出願人】（５９６０４６１１８）株式会社市川ソフトラボラトリー (19)
【Ｆターム（参考）】
[ Back to top ]