(57)【要約】【課題】  画像の中から画素値が急激に変化する点を特徴点として抽出し、この特徴点及び／又は特徴点に関する情報を用いて画像処理をするシステムにおいて、コーナから抽出した特徴点と、コーナと比べて抽出される再現性の低いコーナ以外のエッジから抽出した特徴点との区別をしていなかった。【解決手段】  入力画像からエッジを抽出し、エッジからセグメントを抽出し、セグメントごとに勾配方向を計算して勾配方向グラフを生成し、この勾配方向グラフを調べて勾配方向の変動点を特徴点として抽出するようにした。【選択図】  図１
2010092426.tif 000002
【特許請求の範囲】
【請求項１】
画像からエッジを抽出するエッジ抽出手段と、
前記エッジ抽出手段が抽出したエッジに属する各画素の勾配方向を算出する勾配方向算出手段と、
前記エッジに沿う方向について前記勾配方向が変動する点を特徴点として抽出する特徴点抽出手段と
を有する画像処理装置。
【請求項２】
前記勾配方向算出手段が、勾配方向の値をエッジに沿う方向の順に並べることで勾配方向グラフを生成し、前記勾配方向の変化量があらかじめ定めたしきい値以上の点を勾配方向の変動点として特定し、前記特徴点抽出手段は前記変動点から得られる画素の座標とスケールとを特徴点に関する情報として抽出することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記勾配方向算出手段が、前記勾配方向グラフに平滑化処理を施すことを特徴とする請求項２に記載の画像処理装置。
【請求項４】
前記エッジ抽出手段が、前記勾配方向グラフから抽出するエッジを勾配方向の変動点として特定することを特徴とする請求項２又は３に記載の画像処理装置。
【請求項５】
前記特徴点に関する局所特徴量を算出する局所特徴量手段と、前記局所特徴量に基づいて複数の画像を比較する比較手段とを更に有することを特徴とする請求項１乃至４に記載の画像処理装置。
【請求項６】
前記エッジ抽出手段が、勾配振幅がしきい値より小さい画素を除去することを特徴とする請求項１乃至５のいずれか１項に記載の画像処理装置。
【請求項７】
前記エッジ抽出手段が、エッジがあらかじめ定めたしきい値より短いエッジを除去する
ことを特徴とする請求項１乃至６のいずれか１項に記載の画像処理装置。
【請求項８】
前記エッジ抽出手段がエッジを複数のセグメントに分類して抽出し、前記勾配方向算出手段が、前記セグメントに応じた処理によって、前記セグメントごとに勾配方向を算出することを有する請求項１乃至７のいずれか１項に記載の画像処理装置。
【請求項９】
前記画像をあらかじめ定められた縮小率で段階的に縮小して縮小画像を生成する縮小変換手段を更に有し、前記エッジ抽出手段が前記縮小画像からもエッジを抽出し、前記特徴点抽出手段は前記縮小画像から抽出したエッジに関して特徴点を抽出することを特徴とする請求項１乃至８のいずれか１項に記載の画像処理装置。
【請求項１０】
前記画像をあらかじめ定められた平滑度で段階的に平滑化してスケール画像を生成する平滑化手段を更に有し、前記エッジ抽出手段がスケール画像からもエッジを抽出し、前記特徴点抽出手段は前記スケール画像から抽出したエッジに関して特徴点を抽出することを特徴とする請求項１乃至に記載の画像処理装置。
【請求項１１】
前記エッジ抽出手段は前記画像にＬＯＧフィルタを作用させた画像の画素値の符号が変化する点をエッジとして抽出することを特徴とする請求項１乃至１０のいずれか１項に記載の画像処理装置。
【請求項１２】
前記エッジ抽出手段は前記画像にＤＯＧフィルタを作用させた画像の画素値の符号が変化する点をエッジとして抽出する、
ことを特徴とする請求項１乃至１０のいずれか１項に記載の画像処理装置。
【請求項１３】
画像処理装置が処理する画像処理方法であって、
画像からエッジを抽出するエッジ抽出工程と、
前記エッジ抽出工程で抽出したエッジに属する各画素の勾配方向を算出する勾配方向算出工程と、
前記エッジに沿う方向について前記勾配方向が変動する点を特徴点として抽出する特徴点抽出工程と
を有することを特徴とする画像処理方法。
【請求項１４】
コンピュータに、
画像からエッジを抽出するエッジ抽出工程と、
前記エッジ抽出工程で抽出したエッジに属する画素の勾配方向を算出する勾配方向算出工程と、
前記エッジに沿う方向について前記勾配方向が変動する点を特徴点として抽出する特徴点抽出工程と
を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、局所的な特徴を抽出する画像処理装置に関するものである。
【背景技術】
【０００２】
類似画像を検索するための技術が多く提案されている。例えば、画像を複数のブロックに分け、それぞれの画像特徴量（代表色）を用いてパターンマッチングを行うことで色の位置情報を利用して類似画像を検索する方法がある（特許文献１）。しかし、特許文献１に開示された方法の場合、検索時に画像全体から特徴量を計算する必要があるため、例えば画像内のオブジェクトが切り取られたり、背景色が変わったりした場合には検索が困難になってしまう。
【０００３】
そこで、画像全体の特徴量を使うのではなく、画像の局所的な特徴を使って類似画像を検索する方法が提案されている（非特許文献１）。この方法では、まず画像の中から画素値が急激に変化する点を特徴点として抽出する。次に、特徴点とその近傍の画像情報とから、その特徴点に対する特徴量（局所特徴量）を計算する。画像の検索は、局所特徴量同士のマッチングによって行う。
【０００４】
上述のような局所的な特徴を利用する手法においては、特徴点の抽出方法が重要である。抽出した特徴点が、画像に回転や拡大・縮小などの処理をするだけで抽出されなくなってしまうような再現性が低い特徴点であるならば、このような不安定な特徴点は、画像検索や位置合わせに利用することができない。また、抽出される再現性の低い特徴点は検索や位置合わせ精度の低下原因にもなる。そのため特徴点を抽出する際に、利用する関数値の出力にしきい値を設け、しきい値以下となるような特徴点は廃棄することで、より安定した特徴点を取捨選択するようにしている。
【０００５】
非特許文献２では、特徴点を抽出する対象の画像を連続して縮小変換し取得した多重解像度の各解像度の画像に対してＤｏＧフィルタを適用し、ＤｏＧフィルタ出力画像の極点のうち、所定の範囲内の解像度変化によって位置の変化がない点を特徴点として検出する。その後、抽出した特徴点に対し、位置、スケール、主曲率について近くの輝度値と比較し、コントラストの小さい点やエッジ沿いの点などを除外するようにしている。
【特許文献１】ＵＳＰ６，７１１，２９３
【非特許文献１】Ｃ．Ｓｃｈｍｉｄ  ａｎｄ  Ｒ．Ｍｏｈｒ，“Ｌｏｃａｌ  ｇｒａｙ  ｖａｌｕｅ  ｉｎｖａｒｉａｎｔｓ  ｆｏｒ  ｉｍａｇｅ  ｒｅｔｒｉｅｖａｌ，”ＩＥＥＥ  Ｔｒａｎｓ．ＰＡＭＩ，Ｖｏｌ．１９，Ｎｏ．５，ｐｐ５３０−５３５，１９９７．
【非特許文献２】Ｄａｖｉｄ  Ｇ．Ｌｏｗｅ，“Ｄｉｓｔｉｎｃｔｉｖｅ  Ｉｍａｇｅ  Ｆｅａｔｕｒｅｓ  ｆｒｏｍ  Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｋｅｙｐｏｉｎｔｓ，”Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，６０，２（２００４），ｐｐ．９１−１１０．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、非特許文献１、２の方法で抽出した特徴点は、特徴点を抽出する対象の画像のエッジから抽出した点とコーナから抽出した点とを区別することなく含んでいる。ここで、エッジは画像内の物体の外縁を示す情報であり、画像を特徴づける線要素である。また、コーナは画像内の物体の外縁の角を示す情報であるので、正確にはコーナはエッジの一部である。コーナはエッジの尖ったところ、又はエッジの交点と表現することもできる。
【０００７】
コーナから抽出した特徴点とコーナ以外のエッジから抽出した特徴点とを比較すると、コーナから抽出した特徴点の方が人も画像の特徴として認識し易く、また、同じコーナから特徴点を抽出する再現性も高く安定している。一方で、コーナ以外から抽出する特徴点は、画像に変化が生じた場合に再び同じ箇所から抽出される再現性が低い。このような再現性の低い点は画像の特徴としてはあまり相応しくなく、画像を比較する際の精度を下げたり処理負荷を増やしたりしてしまう。
【０００８】
本発明は、このような課題を解決するためになされたもので、特徴点を使ったシステムにおいて、コーナから特徴点を抽出することで安定した特徴点の抽出機能を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記課題を解決するために本発明に係る画像処理装置は、画像からエッジを抽出するエッジ抽出手段と、前記エッジ抽出手段が抽出したエッジに属する各画素の勾配方向を算出する勾配方向算出手段と、前記エッジに沿う方向について前記勾配方向が変動する点を特徴点として抽出する特徴点抽出手段とを備えることを特徴とする。
【発明の効果】
【００１０】
エッジに沿う方向に勾配方向の変動点を特定することで、コーナから安定した特徴点の抽出が可能になる。
【発明を実施するための最良の形態】
【００１１】
＜第１の実施形態＞
図１、図２を用いて本発明の一実施形態である画像処理装置（以下、特徴点抽出装置１００）についての概略を説明する。図１は本実施形態の構成例を示すブロック図である。
【００１２】
図１に示すように、特徴点抽出装置１００は、画像入力部１０２、エッジ抽出部１０３、勾配方向算出部１０４、勾配方向グラフ生成部１０５、勾配変動点特定部１０６、特徴点抽出部１０７を有し、それぞれが通信可能に接続されている。図２は本実施形態の処理手順を示すフローチャーである。
【００１３】
ステップＳ２０１において、画像入力部１０２が画像１０１を読み込む。ステップＳ２０２において、画像入力部１０２がこの画像１０１から輝度成分画像を抽出し輝度成分画像を生成する。
【００１４】
ステップＳ２０３において、エッジ抽出部１０３が画像入力部１０２が生成した輝度成分画像からエッジを抽出する。本実施形態では、輝度成分画像にＬＯＧ（Ｌａｐｌａｃｉａｎ  ｏｆ  Ｇａｕｓｓｉａｎ）を利用したＬＯＧフィルタを施した画像の各画素の画素値を調べ、画素値の符号が変化する点（零交差点）をエッジとして抽出する。なお、ＬＯＧは以下の式（１）で表される。
【００１５】
【数１】
2010092426.tif 000003
【００１６】
式中、ｒは着目画素からの距離、σはフィルタの平滑化度合いを示し、スケールを決めるパラメータである。本実施形態では、σをあらかじめ定めておく。
【００１７】
次に、エッジ抽出部１０３が抽出したエッジからセグメントを抽出する。予めセグメントとしての類型を設定し、エッジの中で類型に当てはまる部分をセグメントとして抽出する、この詳細は後述する。そして、セグメント毎に始点と終点とを設定し、セグメントに沿う方向（エッジに沿う方向）で始点から終点に向けて各画素に昇順の番号を付与する。
【００１８】
ステップＳ２０４において、勾配方向算出部１０４がステップＳ２０３で生成したセグメントごとに、輝度成分画像の画素でこのセグメントに属する画素の輝度勾配の方向（勾配方向）を算出する。
本実施形態において輝度勾配の方向は、輝度画像上の着目している画素の画素値をＩ（ｘ，ｙ）と表すとき、以下の式（２）で算出する。ただし、θ（ｘ，ｙ）を着目している画素上の勾配方向とする。式（２）で算出される勾配方向は、着目している画素を通る輝度成分画像から抽出したエッジの法線方向とほぼ一致する。
【００１９】
【数２】
2010092426.tif 000004
【００２０】
ステップＳ２０５において、勾配方向グラフ生成部１０５がステップＳ２０４で算出した勾配方向を使い、ステップＳ２０３で抽出したセグメントごとに、勾配方向グラフを生成する。ここで、勾配方向グラフとは、Ｘ軸を着目しているセグメントの画素番号とし、Ｙ軸を勾配方向算出部１０４のステップＳ２０４で計算された勾配方向とするグラフである。セグメントがエッジ形態３０１の場合は、始点から終点の方向の画素順に勾配方向を抽出する。しかし、セグメントが閉曲線であるエッジ形態３０２の場合、勾配方向のグラフの処理終了点をセグメントの終点とせず、終点からあらかじめ定められた画素数Ｒだけ余分に処理して（つまり終点に達したあと、さらに始点からＲ画素だけ実施する）処理を完了する。ここで、余分に処理した画素について、勾配方向のグラフ上での画素番号は終点の画素番号からの連番を付与する。セグメントが閉曲線である場合は、始点や終点が変動点である可能性もあるのでＲ画素だけ余分に処理を必要とする。
【００２１】
ステップＳ２０６は勾配方向変動点の特定ステップであり、勾配変動点特定部１０６で実行される。本ステップでは、ステップＳ２０５で生成された勾配方向のグラフを調べ、勾配方向があらかじめ定めたしきい値以上に変化している画素番号を特定し、当該画素番号に関連付けられている画素を勾配方向の変動点とする。
【００２２】
ステップＳ２０７において、特徴点抽出部１０７がステップＳ２０６で特定された勾配方向の変動点の座標を特徴点情報１０８として出力する。
【００２３】
〔エッジからセグメントを抽出する方法〕
ステップＳ２０３で生成されるセグメントの形態には大きく３種類ある。図３は抽出エッジ形態を表す図であり、図中、エッジ形態３０１は１本の開曲線として抽出されるエッジ形態の一例である。エッジ形態３０２は１本の閉曲線として抽出されるエッジ形態の一例である。エッジ形態３０３はエッジ形態３０１あるいはエッジ形態３０２が他のエッジと連結された状態で抽出されている一例である。エッジ形態３０３において、３１０および３１１は連結点であり図では強調して記している。
【００２４】
本実施形態では、着目エッジが図３に示したエッジ形態のどれに属するかを決定する。本実施の形態では、まず、画像を左上から右下に走査して行き、ステップＳ２０３で抽出したエッジに属する画素を構成画素として見つける。構成画素はエッジと重なる画素である。最初に見つけた構成画素を追跡開始点としてエッジの方向に沿ってエッジの追跡を開始する。
【００２５】
ここで、追跡済みのエッジ構成画素には追跡済みであることを示す情報としてラベル（フラグ）を付ける。追跡は隣接する構成画素の全てにラベルを付け終わるまで実施する。追跡の結果、他のエッジとの連結点が見つかればエッジ形態３０３と見なす。このとき、連結点には連結点を示すラベルを付けておく。連結点が見つからず、かつ、追跡の結果当該追跡開始点に戻ってしまった場合は、エッジ形態３０２と見なす。追跡の結果、エッジ形態３０２でもなく、エッジ形態３０３でもない場合はエッジ形態３０１となる。
【００２６】
エッジ形態３０１の場合、まず、エッジが持つ２つの端点の一方を始点とし他方を終点としてセグメントを生成する。本実施形態では処理した順番が早かった点を始点として採用するが、実際はどちらを始点、終点としても良い。次に、始点から終点へセグメントに沿う方向へ、セグメントに属する各画素に昇順の番号を付与する。最後に、抽出したセグメントに対して重複しないセグメントＩＤを付与し、セグメントＩＤと始点情報および終点情報と画素番号とを関連付けてセグメント情報とする。
エッジ形態３０２の場合、まず、追跡開始点を始点及び終点に設定してセグメントを生成する。次に、始点からセグメントに沿う方向へ、セグメントに属する各画素に昇順の番号を付与する。最後に、重複しないセグメントＩＤを付与し、セグメントＩＤと始点情報および終点情報と画素番号とを関連付けてセグメント情報とする。
【００２７】
エッジ形態３０３の場合、連結点の１つ（連結点１）から再度追跡を開始する。追跡の結果、他の連結点（連結点２）あるいは端点に達した場合は連結点１を始点とし連結点２あるいは当該端点を終点としてセグメントを生成する。次に、始点から終点に向かってセグメントに沿う方向へ、セグメントに属する各画素に昇順の番号を付与する。最後に、重複しないセグメントＩＤを付与し、セグメントＩＤと始点情報および終点情報と画素番号とを関連付けてセグメント情報とする。しかし、セグメントの追跡の結果、連結点１（始点）に戻ってきた場合は、連結点１を始点と終点とに設定して追跡経路上のエッジ部分から成るセグメントについてセグメント情報を生成する。次に、始点から終点に向けてセグメントに沿う方向へ、セグメントに属する各画素に昇順の番号を付与する。最後、重複しないセグメントＩＤを付与し、当該ＩＤと当該始点情報および当該終点情報と当該画素番号とを当該セグメントと関連付ける。着目エッジがエッジ形態３０１あるいは３０２にすべて分類されてセグメントへの分割が完了するまで繰り返す。
【００２８】
〔勾配方向の変動点の抽出〕
ここで、図２のステップＳ２０３〜Ｓ２０６の勾配方向の変動点の抽出処理について詳細を説明する。
【００２９】
図４（ａ）、（ｂ）は正三角形を使った勾配方向の変動点の抽出処理の概略図である。画像４１０と画像４１１の外枠は画像の外枠を図示しているだけであって、画素値を有しているわけではない。
【００３０】
図４（ａ）に示すように画像４１０は白い画素で囲まれた中に黒い正三角形を有する画像とする。ここで、黒の輝度値を０、白の輝度値を２５５、輝度の勾配方向は輝度の高い方向を示すとする。
【００３１】
図４（ｂ）において、エッジ４００は図２のステップＳ２０３においてエッジ抽出部１０３が画像４１０から抽出したエッジである。この例では、エッジ４００はステップＳ２０３において生成されたセグメントと１対１の関係にあるので以降セグメント４００と称す。セグメント４００は正三角形を構成する閉曲線であるから、エッジ形態は図３のエッジ形態３０２に分類される。点４０１はセグメントの始点および終点である。矢印４０２はステップＳ２０４で算出した勾配方向を矢印の向きで表したものである。点４０３はステップＳ２０５の処理においてエッジ形態３０２の場合に処理を完了する処理終了点である。また、点４０１、点４０４、点４０５はステップＳ２０６で特定した勾配方向変動点である。
【００３２】
図５は図４に示すセグメント４００に属する画素から作成した画素番号と勾配方向のグラフを示す図である。図５は図４の勾配方向４０２を画素番号順にプロットしたものであり、Ｘ軸はセグメント４００に沿う方向についてのセグメント４００に属する画素の画素番号を示し、Ｙ軸は各画素における勾配方向を示す。ここで、勾配方向は通常の２次元座標系においてＸ軸正の向きを０°とし、反時計回りに角度が増加していくものとして数値化されたものとする。すなわち、Ｙ軸の正の向きは９０°、Ｘ軸負の向きは１８０°、Ｙ軸負の向きは２７０°となる。また勾配方向θの範囲を０°≦θ＜３６０°としている。
【００３３】
図５の勾配方向のグラフを見ると、点４０１（始点）から点４０４の勾配方向は１２０°であり、点４０４から点４０５の勾配方向は１８０°、点４０５から点４０１までの勾配方向は３０°、点４０１から点４０３（処理終了点）までは１２０°になっている。また、点４０４、点４０５、点４０１において勾配方向が大きく変化している。ステップＳ２０６において、たとえばしきい値を４５°と定め、勾配方向の変化量と比較することにより、点４０４、点４０５、点４０１が勾配方向変動点として特定される。
【００３４】
また、この勾配方向変動点の特定前に、勾配方向グラフ生成部１０５が画素番号順に取得した勾配方向のグラフに図７に示すようなノイズが有る場合に、平滑化処理を実施し、平滑化して図５のようにしてから勾配方向グラフを出力するようにしてもよい。例えば、画像がスキャンされたものであったり、画像に圧縮処理が施されたものであったりする場合、勾配方向グラフ生成部１０５が最初に取得する画素番号―勾配方向のデータには不特定の原因によって細かい変動が重畳されていることがある。図７のように重畳されている場合、勾配変動点特定部１０６で実行される勾配方向の変動点を特定する際に、細かい振動による勾配方向の変動が大きい場合、勾配方向の変動点の抽出精度が下がる。
【００３５】
ここで、平滑化の方法としては勾配方向グラフとガウス関数との畳み込み演算を実施すればよいが、勾配方向グラフを平滑化する処理であればガウス関数の畳み込み演算に限定されない。
【００３６】
以上のように、本実施形態における特徴点抽出装置では、入力画像からエッジを抽出し、エッジからセグメントを抽出し、セグメントごとにセグメントに沿う方向（エッジ方向）勾配方向を計算して勾配方向グラフを生成する。そして、この勾配方向グラフを調べて勾配方向の変動点を特徴点として出力するようにした。従って、画像の中からエッジの角に相当するコーナを精度良く抽出できるので、ノイズ特徴点になりにくい安定した特徴点の抽出が可能になる。
【００３７】
また、本実施形態では特徴点の抽出方法を説明したが、この特徴点に関する局所特徴量を算出し、類似画像検索や画像同士のマッチングなどに適用して処理精度を高めることができる。局所特徴量は非特許文献１や非特許文献２に記載の方法で計算可能である。他にも例えば、Ｌｏｃａｌ  ＪｅｔやＰＣＡ−ＳＩＦＴなどで定義される局所特徴量を抽出すれば、類似画像検索やマッチングに用いる画像の比較処理に適用できる。
【００３８】
エッジからセグメントを抽出する際、図３に示したエッジ形態に分類した上でそれぞれの形態に応じた処理を実施する方法を説明したが、エッジを抽出可能であればよいので前述した方法に限定されるものではない。また、エッジ形態３０１〜３０３の全てに着目しなくても、エッジ形態３０１、３０２だけや、エッジ形態３０１だけに着目してセグメントを抽出するようにしてもよい。
【００３９】
ここで、本実施形態は輝度成分画像に対する処理だけに限定されるものではなく、たとえばＲＧＢやＹＵＶで表現される色空間の各色成分に分解した画像においても適用できる。
【００４０】
また、本実施形態ではエッジ抽出処理にＬＯＧを利用したが、本発明はエッジを抽出可能であればＬＯＧだけに限定されるものではなく、たとえばＬＯＧの近似となるＤＯＧ（Ｄｉｆｆｅｒｅｎｃｅ  ｏｆ  Ｇａｕｓｓｉａｎ）によるＤＯＧフィルタを使ってもよい。なお、各画素について横方向に隣接する画素や縦方向に隣接する画素との差分を算出するだけでも本発明を適用可能な簡易なエッジ抽出は可能である。しかし、エッジの抽出処理としてＬＯＧフィルタやＤＯＧフィルタを用いた場合に抽出されるエッジは太さが１画素で表現されるため細線化処理を必要としないが、２画素以上の太さのエッジは細線化処理を必要とする。
【００４１】
また、変動点特定部１０６の処理の処理は、図５に示す画素番号―勾配方向の線図において、隣合う画素番号の差に着目している事になるが、画素番号―勾配方向の線図にＬＯＧやＤＯＧなどのを作用させることによって変動点を検出してもよい。エッジ抽出をハードとして構成する場合には、この処理も同じハードによって処理ができるため効率良く処理ができる。
【００４２】
＜第２の実施形態＞
本実施形態では、図２のステップＳ２０２で輝度成分画像を生成した後にこの輝度成分画像をあらかじめ定められた縮小率で段階的に縮小変換をすることでスケール画像を生成し、各スケール画像を用いて図２のステップＳ２０３〜Ｓ２０７の処理をする。
【００４３】
図６は縮小画像生成の例を示す図である。図６に示す例は、スケール率ｐが２の−（１／４）乗、縮小画像の枚数ｎが９の場合である。図４において、画像８０１は画像入力部１０２から渡された輝度成分画像である。画像８０２は当該輝度成分画像から倍率ｐに従って４回縮小された縮小画像である。画像８０３は当該輝度成分画像から倍率ｐに従って８回縮小された縮小画像である。
【００４４】
この例では、縮小画像８０２は画像入力部１０２から渡された輝度成分画像が１／２に縮小された画像となり、縮小画像８０３は画像入力部１０２から渡された輝度成分画像が１／４に縮小された画像となる。
【００４５】
なお、本実施形態では線形保管による縮小方法を用いるが、画像を縮小する方法として単純に画素を間引く方法、線形補間を用いる方法、低域フィルタ適用後にサンプリングする方法などを用いてもよい。
【００４６】
縮小画像生成部６０１で生成された当該縮小画像は、エッジ抽出部１０３に渡される。
尚、上記実施の形態２では、スケール画像として縮小画像を用いたが、代わり所定の平滑度合で平滑化した画像を用いるスケールスペース（非特許文献１に記載）を用いてもよい。
また、縮小画像とスケールスペース画像の両方を組み合わせて用いてもよい。たとえば非特許文献２に記載の方法を使うことができる。
【００４７】
以上、本実施形態によると画像を拡大・縮小しても、再び同じコーナから抽出する再現性の高い特徴点に絞ることが容易にできる。
【００４８】
＜第３の実施形態＞
本実施形態ではエッジ抽出部１０３がエッジの抽出後にノイズとなるエッジ（以下、ノイズエッジと称す）と判断したものについては廃棄するように構成する。
【００４９】
本実施形態では、エッジに属する各画素について画素値の勾配振幅を求め、勾配振幅の値Ｔがあらかじめ定めたしきい値よりも小さい画素についてはノイズと見なしてエッジを構成する画素から除去することで、ノイズエッジ成分を除去したエッジを抽出する。ここで、勾配振幅Ｔ（ｘ，ｙ）は式（３）で表現されるエッジの強度のことである。
【００５０】
【数３】
2010092426.tif 000005
【００５１】
式（３）においてｄＶｘは２次元配列の画素値をｘ方向に微分したもので、ｄＶｙは２次元配列の画素値をｘ方向に微分したものである。
【００５２】
以下、第１、第２の実施形態と同一の機能や構成については説明を省略する。
【００５３】
図２のステップＳ２０３においてエッジ抽出部１０３は、ノイズエッジを除去したエッジからセグメントを抽出し、後は第１、第２の実施形態と同様の処理によってコーナから特徴点を抽出する。
【００５４】
また、エッジ抽出前に輝度成分画像の各画素について画素値の勾配振幅を求め、勾配振幅の値があらかじめ定めたしきい値よりも小さい画素をして情報を付加し、エッジ抽出時に着目画素にこの情報がある場合に除去するようにしてもよい。この処理によって、強度が弱くエッジとして抽出するに相応しくない画素を除くことができる。
【００５５】
また、各抽出エッジのエッジ長を求め、エッジ長があらかじめ定めたしきい値よりも短い場合にノイズエッジとして除去するようにしてもよい。この処理によって、例えば画像中の孤立点など人がオブジェクトとして認識しない様な小さいエッジを除くことができる。勾配振幅によってノイズ画素を除去した後にエッジ長の短いエッジを除去してもよい。
【００５６】
以上、本実施形態ではエッジ抽出部１０３がノイズエッジを判定し、判定したノイズエッジを除去するので、画像の特徴をよく示すコーナを特徴点として抽出する際に、ノイズエッジの影響を抑える事ができる。
【００５７】
図８に示すコンピュータ１４００は、ＲＯＭ１４３０の中に前記実施形態で挙げたフローチャートの処理をＣＰＵ１４１０に実現させるプログラムを格納している。そして、プログラムを実行させる際にＲＯＭ１４３０のプログラムをＲＡＭ１４２０に読出しＣＰＵ１４１０が処理できるようにする。ここで、１４５０はバスであり、ＲＯＭ１４３０、ＲＡＭ１４２０、ＣＰＵ１４１０およびＨＤＤのデータをやりとりする。また、コンピュータ１４００はユーザインターフェースに接続されるキーボードやマウスなどの入出力機器からの入力を受ける。また、コンピュータ１４００は、ネットワークインターフェース１４７０に対して入出力を行ったりする。コンピュータ１４００のネットワークインターフェース１４７０はネットワーク１５００を介して、データベース（ＤＢ）１５１０、クライアント（ＣＬＩＥＮＴ）１５２０、プリンタ（ＰＲＩＮＴＥＲ）１５３０と通信可能である。
【００５８】
また、複数のハードウェアとソフトウェアの協同によって前述の実施形態の処理を実現してもよい。例えば、図１に示す構成は、その構成の一部をソフトウェアで実現可能であり、また特定の処理に特化したチップでも実現可能である。他にも、ネットワークで接続している複数の機器の協同によって実現してもよい。図８を用いて例を挙げると、コンピュータ１４００がプリンタ１５３０やクライアント１５２０から画像を受付けて、コンピュータ１４００が図２のフローチャートの処理を行い、データベース１５１０に登録する形態が挙げられる。また、コンピュータ１４００がクライアント１５２０やプリンタ１５３０から検索依頼とクエリ画像を受付けて、データベース１５１０からクエリ画像に類似する画像を検索する形態も挙げられる。
【００５９】
また、記憶媒体から読み出されたプログラムがコンピュータに挿入された機能拡張ユニットに備わるメモリに書込まれ、その機能拡張ユニットに備わるＣＰＵがそのプログラムコードの指示に基づき、処理を行ってもよい。
【００６０】
また、プログラムコードを供給する記憶媒体として、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。
【００６１】
また、プログラムコードをＣＰＵ（中央処理装置）が読み出し、ＣＰＵが、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）の機能を使って前述の処理を行ってもよい。
【図面の簡単な説明】
【００６２】
【図１】特徴点抽出装置を示すブロック図である。
【図２】特徴点の抽出処理の手順を表すフローチャートである。
【図３】抽出エッジの形態を表す図である。
【図４】正三角形を使った勾配方向変動点を抽出する処理の概略図である。
【図５】画素番号と勾配方向のグラフである。
【図６】縮小画像生成の例を示す図である。
【図７】画像劣化が生じている場合の画素番号と勾配方向のグラフである。
【図８】本発明の一実施形態の構成の概略図である。
【符号の説明】
【００６３】
１００  特徴点抽出装置
１０２  画像入力部
１０３  エッジ抽出部
１０４  勾配方向算出部
１０５  勾配方向グラフ生成部
１０６  勾配変動点特定部
１０７  特徴点出力部
１０８  特徴点情報
【図１】
2010092426.tif 000006
【図２】
2010092426.tif 000007
【図３】
2010092426.tif 000008
【図４】
2010092426.tif 000009
【図５】
2010092426.tif 000010
【図６】
2010092426.tif 000011
【図７】
2010092426.tif 000012
【図８】
2010092426.tif 000013