(57)【特許請求の範囲】
【請求項１】
プロセッサと、データ及びプログラムが格納される記憶装置とを備え、該データは濃淡画像を含み、該プログラムは該プロセッサに対し該データに含まれる複数の局所特徴量を生成させる特徴ベクトル生成プログラムを含む画像処理装置において、
該特徴ベクトル生成プログラムは該プロセッサに対し、
（ａ）該濃淡画像に対しコーナポイントである特徴点の座標を検出させ、
（ｂ）検出された各特徴点である第１特徴点から近い順の所定数の第２特徴点のそれぞれと該第１特徴点とのペア特徴点を選択させ、
（ｃ）各ペア特徴点について、該第１特徴点と該第２特徴点との間の距離Ｌを求めさせ、
（ｄ）該第１特徴点を中心とし該距離Ｌに比例した第１半径の円周上の画素のうち等画素間隔のｎ個（ｎ≧４）の画素のそれぞれを含む画素領域Ｐｉ、ｉ＝０〜ｎ−１の平均第１輝度Ｉ（Ｐｉ）を、該距離Ｌの線方向を基準として所定順にサンプリングさせ、それぞれと該第１特徴点を含む画素領域の輝度との差と、
該第２特徴点を中心とし該距離Ｌに比例した第２半径の円周上の画素のうち等画素間隔のｍ個（ｍ≧４）の画素のそれぞれを含む画素領域Ｑｉ、ｉ＝０〜ｍ−１の平均第２輝度Ｉ（Ｑｊ）を、該距離Ｌの線方向を基準として所定順にサンプリングさせ、それぞれと該第２特徴点を含む画素領域の輝度との差と、
を成分とする、正規化された局所特徴ベクトルを求めさせ、
該画素領域の画素数の平方根は該距離Ｌに略比例していることを特徴とする画像処理装置。
【請求項２】
ｍ及びｎはいずれも８、１６又は３２であることを特徴とする請求項１に記載の画像処理装置。
【請求項３】
カメラをさらに備え、
該濃淡画像は、該カメラで撮像されたフレーム画像をグレースケール化した画像であることを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
該データはさらに、各参照濃淡画像について、該特徴ベクトル生成プログラムで生成した局所特徴ベクトルを参照局所特徴ベクトルとしてクラスＩＤと対応付けたものと該参照濃淡画像に関する情報とを含み、該プログラムはさらに画像検索プログラムを含み、
該画像検索プログラムは、該プロセッサに対し、
（ｅ）検索濃淡画像に対しステップ（ｄ）で求めた各局所特徴ベクトルについて、該局所特徴ベクトルに対応する、該参照データ内のクラスＩＤを、該局所特徴ベクトルと該参照データ内の参照局所特徴ベクトルとのマッチングにより決定させ、該クラスＩＤが属する参照濃淡画像のカウンタをインクリメントさせ、
（ｆ）カウンタ値が最大の参照濃淡画像に関する、該参照データ内の情報を、該検索濃淡画像の情報として出力させる、
ことを特徴とする請求項１乃至３のいずれか１つに記載の画像処理装置。
【請求項５】
該画像検索プログラムは、該プロセッサに対し、ステップ（ｅ）において、局所特徴ベクトルを入力としクラスＩＤを出力とする識別器により、該クラスＩＤを決定させる、
ことを特徴とする請求項４に記載の画像処理装置。
【請求項６】
拡張現実表示装置であることを特徴とする請求項１又は２に記載の画像処理装置。
【請求項７】
請求項１乃至６のいずれか１つに記載の画像処理装置を構成するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、輝度画像上の自然特徴点を中心とする局所領域のスケール不変性かつ回転不変性特徴ベクトルを求める機能を備えた画像処理装置及びそのプログラムに関する。
【背景技術】
【０００２】
カメラを備えたスマートフォンの性能向上とＦＡＳＴ（Ｆｅａｔｕｒｅｓ  ｆｒｏｍ  Ａｃｃｅｌｅｒａｔｅｄ  Ｓｅｇｍｅｎｔ  Ｔｅｓｔ）コーナ検出法などの画像処理技術の向上に伴い、マーカレスＡＲ（Ａｕｇｍｅｎｔｅｄ  Ｒｅａｌｉｔｙ：拡張現実）をスマートフォンで実現可能になった。
【０００３】
ＦＡＳＴコーナ検出法によれば、１画像内の自然特徴点を多数、高速に検出することができる。これら特徴点を、予め求めた参照データ内の特徴点とマッチングすることにより、３次元座標をカメラ画像の２次元座標に投影するカメラパラメータを推定することができ、このパラメータに基づき、３Ｄモデルをカメラ画像に投影した（カメラ画像にＣＧ画像を重畳した）ＡＲ画像を生成することができる。このマッチングを行うために、各特徴点を中心とする局所特徴ベクトルを記述する必要がある。
【０００４】
下記特許文献１には、スケール不変性及び回転不変性を有する局所特徴ベクトルを、コントラストによらずに算出することができる局所特徴ベクトル算出方法が開示されている。
【０００５】
また、下記非特許文献１には、そこでのテストの結果、下記非特許文献２のＢＲＩＥＦ（Ｂｉｎａｒｙ  Ｒｏｂｕｓｔ    Ｉｎｄｅｐｅｎｄｅｎｔ  Ｅｌｅｍｅｎｔａｒｙ  Ｆｅａｔｕｒｅｓ）という手法が最速であると記載されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１２−３８２９０号公報
【非特許文献】
【０００７】
【非特許文献１】特徴記述子比較レポート：http://computer-vision-talks.com/2011/08/feature-descriptor-comparison-report/
【非特許文献２】BRIEF:http://cvlab.epfl.ch/~lepetit/papers/calonder_pami11.pdf
【非特許文献３】ランダムフォレスト:http://link.springer.com/article/10.1023%2FA%3A1010933404324?LI=true
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、スケール不変性及び回転不変性を有する局所特徴ベクトルを求める処理は、計算コストが比較的大きく、特に、スケール不変性を持たせるためには複数の画像スケールのそれぞれで画像処理を行う必要があるので、計算コストが増大する原因となる。
【０００９】
より具体的には、特許文献１では、特徴点を中心とするｐ個の円の円周上の画素データを検出する同心円検出部と、各画素データにおける画素値の勾配の角度と支配的勾配との差分値に円の半径の平方根を乗じた重み付き差分値をそれぞれ算出する重み付き差分値算出部と、重み付き差分値についてのｑ個の階級を有する度数分布を作成する度数分布作成
部と、各円についての各度数を成分とするｑ次元のベクトルから、ｐ×ｑ次元の記述子ベクトルを算出する記述子ベクトル算出部とを設ける必要があるので、ＳＩＦＴ（Ｓｃａｌｅ  Ｉｎｖａｒｉａｎｔ  Ｆｅａｔｕｒｅ  Ｔｒａｎｓｆｏｒｍ）や、これよりも高速なＳＵＲＦよりも計算コストを低減できるものの、計算コストが比較的大きくなる。
【００１０】
また、非特許文献２のＢＲＩＥＦでは、特徴点を中心とする円内の２画素の輝度差を２値化したものを局所特徴ベクトルの成分とするので、局所特徴ベクトルの次元数とビット長とが等しくなって省メモリにはなるものの、高速化の点では、次の理由により、充分とは言えない。すなわち、例えば１２８次元の局所特徴ベクトルを生成する場合、ＢＲＩＥＦでは局所特徴ベクトルを１２８ビットで表現できるものの、例えば６４０ｘ４８０画素の画像中の該円内のランダムな１２８回の画素サンプリングが必要になり、キャッシング回数が増え、重い処理となるからである。また、ＢＲＩＥＦは回転不変性を有しない。さらに、上記２値化により、接近した局所特徴ベクトル間の区別が困難になるので、カメラ画像から取得した局所特徴ベクトルと参照局所特徴ベクトルとのマッチングの精度及び安定性、すなわち特徴点識別性が低下する。
【００１１】
さらに、例えば文字や記号などの画像に関する情報をデータベースで検索する場合、従来法では特徴点間の局所特徴ベクトルによる識別性が比較的低いので、画像認識率が低くなる。
【００１２】
本発明の目的は、このような問題点に鑑み、スケール不変性及び回転不変性を持つ局所特徴ベクトルを、より低い計算コストで求める構成を備えた画像処理装置及びそのプログラムを提供することにある。
【００１３】
本発明の他の目的は、画像から生成した局所特徴ベクトルの識別性をより向上させる構成を備えた画像処理装置及びそのプログラムを提供することにある。
【課題を解決するための手段】
【００１４】
本発明の第１態様では、プロセッサと、データ及びプログラムが格納される記憶装置とを備え、該データは濃淡画像を含み、該プログラムは該プロセッサに対し該データに含まれる複数の局所特徴量を生成させる特徴ベクトル生成プログラムを含む画像処理装置において、
該特徴ベクトル生成プログラムは該プロセッサに対し、
（ａ）該濃淡画像に対しコーナポイントである特徴点の座標を検出させ、
（ｂ）検出された各特徴点である第１特徴点から近い順の所定数の第２特徴点のそれぞれと該第１特徴点とのペア特徴点を選択させ、
（ｃ）各ペア特徴点について、該第１特徴点と該第２特徴点との間の距離Ｌを求めさせ、
（ｄ）該第１特徴点を中心とし該距離Ｌに比例した第１半径の円周上の画素のうち等画素間隔のｎ個（ｎ≧４）の画素のそれぞれを含む画素領域Ｐｉ、ｉ＝０〜ｎ−１の平均第１輝度Ｉ（Ｐｉ）を、該距離Ｌの線方向を基準として所定順にサンプリングさせ、それぞれと該第１特徴点を含む画素領域の輝度との差と、
該第２特徴点を中心とし該距離Ｌに比例した第２半径の円周上の画素のうち等画素間隔のｍ個（ｍ≧４）の画素のそれぞれを含む画素領域Ｑｉ、ｉ＝０〜ｍ−１の平均第２輝度Ｉ（Ｑｊ）を、該距離Ｌの線方向を基準として所定順にサンプリングさせ、それぞれと該第２特徴点を含む画素領域の輝度との差と、
を成分とする、正規化された局所特徴ベクトルを求めさせ、
該画素領域の画素数の平方根は該距離Ｌに略比例している。
【００１５】
ここに、濃淡画像は、例えばグレースケール画像又はカラー画像の単色成分画像であり
、ＲＧＢ画像のＲ，Ｇ，Ｂチャネルの１つ以上のチャンネルのそれぞれの濃淡画像であってもよい。コーナポイントは、例えばＦＡＳＴコーナ検出法又はＨａｒｒｉｓオペレータを用いたコーナ検出法により検出される。平均輝度は累積加算輝度を含む概念である。また、局所特徴ベクトルの表現は、上記距離Ｌの線方向に関し成分が所定順に配置されておればよく、前者の輝度差成分と後者の輝度差成分を交互に配置したものなどであってもよい。
【００１６】
本発明による画像処理装置の第２態様では、第１態様において、ｍ及びｎはいずれも８、１６又は３２である。
【発明の効果】
【００１７】
上記第１態様の構成によれば、上記のようにペア特徴点を選択し局所特徴ベクトルを求めるので、スケール不変性及び回転不変性を持つ局所特徴ベクトルを、従来より低い計算コストで求めることができるという効果を奏する。
【００１８】
また、画像の特徴点間に基づく局所特徴ベクトルを生成するので、文字や記号などのフレーム画像であっても、局所特徴ベクトルの識別性が向上し、結果としてフレーム画像の識別性等を向上させることが可能となるという効果を奏する。
【００１９】
上記第２態様の構成によれば、ｍ及びｎはいずれも２の冪乗であるので、実施例２で述べるように、局所特徴ベクトルをより高速に求めることができるという効果を奏する。
【００２０】
本発明の他の目的、特徴的な構成及び効果は、以下の説明を特許請求の範囲及び図面の記載と関係づけて読むことにより明らかになる。  
【図面の簡単な説明】
【００２１】
【図１】本発明の実施例１に係る画像処理装置１０のハードウェア構成を示す概略ブロック図である。
【図２】１フレーム画像内の局所特徴ベクトルを生成する処理手順を示すフローチャートである。
【図３】（Ａ）は、文字画像と、その上に各特徴点に関するペア特徴点の特徴点間を直線で連結したものとを示す図であり、（Ｂ）は（Ａ）の一部を拡大したペア特徴点説明図である。
【図４】図２のステップＳ３の処理説明図であって、図３（Ａ）中の一部を拡大した局所特徴ベクトル生成処理説明図である。
【図５】図２のステップＳ４の処理説明図である。
【図６】（Ａ）〜（Ｄ）は何れも、第１特徴点を共通にする特徴点ペアを点で示す局所領域画像であり、（Ｅ）〜（Ｈ）はそれぞれ（Ａ）〜（Ｄ）の特徴点ペアに関する局所特徴ベクトルの棒グラフによる成分表示図である。
【図７】実施例２に係る画像処理装置の概略機能ブロック図である。
【図８】図７中の主処理部４０で実行されるメインルーチンの概略フローチャートである。
【図９】図７中のマッチング処理部４６での、局所特徴ベクトル記憶部Ｍ３内の１つの局所特徴ベクトルＶに対するクラスＩＤ推定処理を示す概略フローチャートである。
【図１０】（Ａ）は、クラスＩＤ及びフレーム画像ＩＤでラベルされた同一ペア特徴点に関する局所特徴ベクトルの説明図であり、（Ｂ）は、参照データ内の局所特徴ベクトルの全集合からランダムに抽出した部分集合毎のツリーからなるランダムフォレストの識別器をその入出力と対応付けて示す説明図である。
【図１１】白鳥の写真と「Ｓｗａｎ」の文字列とを含む印刷物の撮影画像に対し図７の処理を行いその途中結果を可視化したものを含む図であって、該画像と該画像から抽出された特徴点ペアと、各ペアの特徴点間を接続した直線とを示す図である。
【図１２】白鳥の写真と「Ｓｗａｎ」の文字列とを含む印刷物の撮影画像に対し図７の処理を行いその途中結果を可視化したものを含む図であって、該画像を縮小し回転した参照画上の特徴点と認識対象である図１１中の画像上の特徴点とをマッチング部でマッチングさせ、マッチングした特徴点間を直線で接続した図である。
【図１３】白鳥の写真と「Ｓｗａｎ」の文字列とを含む印刷物の撮影画像に対し図７の処理を行いその途中結果を可視化したものを含む図であって、該画像を縮小し回転し射影変換した参照画上の特徴点と認識対象である図１１中の画像上の特徴点とをマッチング部でマッチングさせ、マッチングした特徴点間を直線で接続した図である。
【図１４】白鳥の写真と「Ｓｗａｎ」の文字列とを含む印刷物の撮影画像に対し図７の処理を行いその途中結果を可視化したものを含む図であって、該画像を回転し図１２の場合よりも縮小した参照画上の特徴点と認識対象である図１１中の画像上の特徴点とをマッチング部でマッチングさせ、マッチングした特徴点間を直線で接続した図である。
【実施例１】
【００２２】
図１は、本発明の実施例１に係る画像処理装置１０のハードウェア構成を示す概略ブロック図であって、この実施例１で必要な構成要素のみを示す。画像処理装置１０は例えば、カメラを備えたスマートフォンやＰＤＡ等の携帯端末装置、ノートパソコン又はデスクトップパソコンなどである。
【００２３】
画像処理装置１０は、その本体部２０において、プロセッサ２１がバス２２を介して記憶装置２３、入力インターフェイス２４、カメラインターフェイス２５及びディスプレインターフェイス２６に結合されている。プロセッサ２１は、内部キャッシュメモリを備えている。入力インターフェイス２４には入力装置３０が結合され、カメラインターフェイス２５にはカメラ３１が結合され、ディスプレインターフェイス２６には出力装置としての表示装置３２が結合され、他の出力装置としての通信部２７にはアンテナ３３が結合されている。
【００２４】
入力装置３０は、対話型入力装置であって、タッチパネル、ポインティングデバイス若しくはキーボード又はこれらの組み合わせで構成されている。通信部２７は、電波を介して外部モニタ又はインターネットと結合するためのインターフェイスを備えている。
【００２５】
記憶装置２３にはプログラム及びデータが格納され、このプログラムは、プロセッサ２１に対し、入力装置３０から入力インターフェイス２４を介したユーザの指示又は設定値の選択若しくは入力を受け付け、この入力に応じて、アプリケーションを起動させ、カメラ３１で被写体、例えば、図書館の本の表紙又は看板を撮像させてそのフレーム画像（静止画）を記憶装置２３内に格納させ、このフレーム画像から複数の局所特徴ベクトルを生成し、これらと記憶装置２３内の参照データとに基づいて、このフレーム画像を識別し、このフレーム画像に関する情報、例えば、該図書館に蔵書されている関連する本の情報又は看板に関する詳細情報を記憶装置２３から読み出してディスプレインターフェイス２６を介し表示装置３２に表示させる。或いは、カメラ３１で店内又は通販カタログの商品を撮像させ、同様にして、この商品に関する情報を表示装置３２に表示させる。
【００２６】
本実施例１の特徴は、図２に示す、１フレーム画像内の局所特徴ベクトルを生成する処理である。以下、括弧内は図中のステップ識別符号を示す。
【００２７】
（Ｓ０）１フレーム画像内で注目画素をラスタースキャンしながら特徴点をＦＡＳＴコーナ検出法により検出する。
【００２８】
このＦＡＳＴコーナ検出法は、注目画素を中心とし、正の閾値をｔｈとし、例えば半径
３画素の円周上における１６個の画素の輝度値を、（注目画素の輝度値）−ｔｈより小さければ暗い、（注目画素の輝度値）＋ｔｈより大きければ明るい、これらの間の値であれば類似と３値化し、連続して例えば９画素以上が明るい又は暗いと判定された場合に、注目画素がコーナの特徴点であると判定するものである。
【００２９】
（Ｓ１）以下、ステップＳ０で検出した各特徴点（注目特徴点）について、Ｓ５迄の処理を行う。
【００３０】
（Ｓ２）注目特徴点（第１特徴点）について、この特徴点から距離が小さい順の所定数ｎの特徴点を第２特徴点とし、第１特徴点と、第２特徴点のそれぞれとのｎ組のペア特徴点を選択する。ｎは、ｎ≧１であって、各第１特徴点について共通の値である。
【００３１】
図３（Ａ）は、各特徴点について、ｎ＝４とし、第１特徴点とそれぞれの第２特徴点との間を直線で連結（ペアを連結）したものである。図４は、図３中の一部拡大説明図である。
【００３２】
このステップＳ２で求めた各ペア特徴点についてステップＳ３及びステップＳ４の処理を行う。
【００３３】
（Ｓ３）ペア特徴点の特徴点間距離Ｌを算出し、例えば図４に示すように第１特徴点３５０と第２特徴点３５１との間の距離Ｌを算出し、第１特徴点３５０を中心とする距離Ｌに比例した半径の第１サンプリング円３５２、及び、第２特徴点３５１を中心とする距離Ｌに比例した半径の第２サンプリング円３５３を決定する。
【００３４】
図４での比例定数は、１であり、各特徴点について共通である。第１サンプリング円３５２と第２サンプリング円３５３の半径に関する該比例定数は、互いに異なるものを用いてもよい。
【００３５】
図５は、図４と異なる第１特徴点３６、第２特徴点３７及び該比例定数が上記と異なる第１サンプリング円Ｃ１及び第２サンプリング円Ｃ２を示している。
【００３６】
（Ｓ４）第１サンプリング円Ｃ１上の画素のうち、等画素間隔のＮ個（Ｎ≧４）、例えば１６個の画素のそれぞれを中心とする矩形画素領域Ｐ０〜Ｐ９、Ｐａ〜Ｐｆのそれぞれの平均輝度Ｉ（Ｐｉ）、ｉ＝０〜ｆを、第１特徴点３６から第２特徴点３７へ向かう方向ベクトル（又は直線Ｌの方向）を基準として所定順、例えばこの方向ベクトルを基準として反時計回りの方向にサンプリング、図５では平均輝度Ｉ（Ｐ１），Ｉ（Ｐ２）、・・・、Ｉ（Ｐｆ）、Ｉ（Ｐ０）をこの順にサンプリングし、これらのそれぞれと、第１特徴点３６を中心とする矩形画素領域（ハッチングで示す領域）の平均輝度Ｉ１との差を、この順に並べ、同様に、第２特徴点３７から第１特徴点３６へ向かう方向ベクトル（又は直線Ｌの方向）を基準として所定順、例えばこの方向ベクトルを基準として反時計回りの方向にサンプリング、図５では平均輝度Ｉ（Ｑ９），Ｉ（Ｑａ）、・・・、Ｉ（Ｑｆ）、Ｉ（Ｑ０）、・・・、Ｉ（Ｑ８）をこの順にサンプリングし、これらのそれぞれと、第２特徴点３７を中心とする矩形画素領域（ハッチングで示す領域）の平均輝度Ｉ２との差を、この順に並べ、かつ、正規化したものを、ペア特徴点の３６に関する局所特徴ベクトルとして求める。すなわち、この局所特徴ベクトルＶを、
Ｖ＝α（Ｉ（Ｐ１）−Ｉ１，Ｉ（Ｐ２）−Ｉ１，・・・，Ｉ（Ｐｆ）−Ｉ１、Ｉ（Ｐ０）−Ｉ１，Ｉ（Ｑ９），Ｉ（Ｑａ）−Ｉ２，・・・，Ｉ（Ｑｆ），Ｉ（Ｑ０），・・・，Ｉ（Ｑ８））
として求める。αは、特徴ベクトルＶのノルムの値を、例えば符号付８ビット整数の最大値である１２７（ノルムの平方が１６１２９）に正規化するための係数である。また、各
成分の符号は、上記と逆であっても、また、第２サンプリング円Ｃ２に関してのみ上記と逆であってもよい。
【００３７】
上記各矩形画素領域は、正方形領域であって、その一辺の長さが距離Ｌに略比例している。ここに略比例とは、量子化誤差が含まれることを意味している。
【００３８】
１フレーム内の全特徴点のそれぞれについて、ステップＳ１〜Ｓ５の処理を行うので、上記第２特徴点３７と第１特徴点とを互いに入れ替えたものの局所特徴ベクトルも算出することになる。
【００３９】
このようにして求めた局所特徴ベクトルは、カメラ３１の光軸及び位置を一定にし、光軸の回りにカメラ３１を回転させても不変であり、かつ、この光軸方向へカメラ３１をスライドさせても不変である。すなわち、この局所特徴ベクトルは、スケール不変性及び回転不変性を持っている。
【００４０】
図６（Ａ）〜（Ｄ）は何れも、第１特徴点を共通にする互いに異なる特徴点ペアを点で示す局所領域画像であり、（Ｅ）〜（Ｈ）はそれぞれ（Ａ）〜（Ｄ）の特徴点ペアに関する局所特徴ベクトルの棒グラフによる成分表示図である。
【００４１】
上記の正規化前の局所特徴ベクトルＶの第ｋ成分をＶ［ｋ］、輝度Ｉ（Ｐｉ）をＲ［ｉ］、第１特徴点３６の輝度をＩ１、計算開始位置の輝度配列要素をＲ［ｏ］（図５の場合、ｏ＝１）とし、１６進数の前に０ｘを付加して表記すると、Ｃ言語の場合、ベクトルＶの第１サンプリング円Ｃ１に関する成分を次のような簡単なループ処理で計算することができる。
【００４２】
ｆｏｒ  （ｉ＝０；    ｉ＜１６；    ｉ＋＋）  ｛    Ｖ［ｉ］  ＝  Ｓ［（ｉ＋ｏ）＆０ｘ１ｆ］  −  Ｉ１  ｝；
ここに、＆は論理積演算子である。一般に、剰余（ｍｏｄｅ）演算子を％、とすると、ｎが２の冪乗である場合、ｉ＝（ｊ＋ｏ）％ｎはｉ＝（ｊ＋ｏ）＆（ｎ−１）で計算できるので、上記ループ処理のように、ｉの値を決定するためｉ＝ｎであるか否かでジャンプする余分な条件ジャンプ命令を用いずに論理積演算子＆を用いてインデックスｉを高速計算できる。
【００４３】
ベクトルＶの第２サンプリング円Ｃ２に関する成分についても上記と同様である。  
局所特徴ベクトルＶは、各成分が輝度値の差であるので、照明の変化に影響されにくい。また、局所特徴ベクトルＶのノルムが正規化されているので、さらに照明の変化に影響されにくい。さらに、局所特徴ベクトルＶの各成分が画素領域の平均輝度値（後でベクトルＶが正規化されるので、これは累積加算値でよい）を用いたものであるので、局所特徴ベクトルＶのＳＮ比を比較的大きくすることができる。
【００４４】
上記のような正規化された局所特徴ベクトルＶは、以下のような実施例２で用いられる。
【実施例２】
【００４５】
図７は、実施例１の方法を用いた実施例２に係る画像処理装置の概略機能ブロック図である。この画像処理装置のハードウェア構成は、実施例１の図１に示すものと同一である。
【００４６】
図７中、角丸矩形のブロックＭｉ及びバッファ領域Ｍ０〜Ｍ５は、図１の記憶装置２３内のデータ領域の一部である。
【００４７】
主処理部４０は、フレーム画像及びその輝度画像を画像処理するメインルーチンである。図８は、この主処理部４０による処理を示す概略フローチャートであり、ステップＳ４ｉ、Ｓ４１、Ｓ４３、Ｓ４５〜Ｓ４８でそれぞれ図７中のブロック４ｉ、４１、４３、４５〜４８をサブルーチンとして呼び出して処理する。
【００４８】
図７において、画像入力部４ｉ、バッファ領域Ｍｉ、グレースケール化部４１、バッファ領域Ｍ０、特徴点検出部４３、２次元座標記憶部Ｍ１及び局所特徴ベクトル生成部４５は、実施例１においても用いられる。すなわち、画像入力部４ｉは、オペレーティングシステムを介しカメラ３１から、シャッターオン時のカラーフレーム画像Ｇ０（例えば６４０ｘ４８０画素）を取得してバッファ領域Ｍｉに格納する。また、グレースケール化部４１は、バッファ領域Ｍｉ内のフレーム画像Ｇ０を、グレースケール化して８ビット１チャンネルの輝度画像（フレーム画像）Ｇ１に変換しながら、これをバッファ領域Ｍ０に格納する。特徴点検出部４３は、図２のステップＳ０と同じ処理を行って、各特徴点の２次元座標を取得し、２次元座標記憶部Ｍ１に格納する。局所特徴ベクトル生成部４５は、２次元座標記憶部Ｍ１内の各特徴点に対し図２のステップＳ１〜Ｓ５の処理を行って局所特徴ベクトルを生成し、局所特徴ベクトル記憶部Ｍ３に追加する。
【００４９】
次に、参照データ記憶部Ｍ４には、予め、検索で用いられる参照データが格納されている。この参照データ記憶部Ｍ４は、参照データ作成部４２、アフィン変換部４４、局所領域画像記憶部Ｍ２及び局所特徴ベクトルを生成する上記の構成を用いて、以下のようにして生成される。
【００５０】
すなわち、参照データ作成部４２は、フレーム画像Ｇ１から、各ペア特徴点の図５に示すような第１サンプリング円Ｃ１及び第２サンプリング円Ｃ２を含む局所領域画像を切り出し、局所領域画像群Ｇ２として局所領域画像記憶部Ｍ２に追加し、局所特徴ベクトル生成部４５での図２のステップＳ１〜Ｓ５の処理により、局所領域画像群Ｇ２の各ペア特徴点の局所特徴ベクトル（参照局所特徴ベクトル）を求め、参照データ記憶部Ｍ４に追加する。
【００５１】
参照データ作成部４２はまた、局所領域画像群Ｇ２のそれぞれの画像から、カメラの奥行き及び姿勢を変えたものに相当する複数の局所領域画像をアフィン変換で自動生成し、局所領域画像群Ｇ２に加えるとともに各局所領域画像について上記同様にして局所特徴ベクトルを求め、参照データ記憶部Ｍ４に追加する。
【００５２】
すなわち、アフィン変換部４４を介し、局所領域画像群Ｇ２の各局所領域画像を、奥行きを変えずに光軸方向を変えることに相当する複数のマトリックスのそれぞれでアフィン変換して新たな局所領域画像群を生成し、これらを局所領域画像群Ｇ２に追加し、変換された各画像について局所特徴ベクトル生成部４５を介し同様にして局所特長ベクトルを求め、参照データ記憶部Ｍ４に追加する。参照データ作成部４２はさらに、局所領域画像群Ｇ２のそれぞれを、奥行きのみ長くすることに相当する複数のマトリックスのそれぞれでアフィン変換した画像群、すなわち、縮小した局所領域画像、例えば、幅及び高さをそれぞれ１／√２倍し、さらに１／√２倍し、さらに１／√２倍したそれぞれの局所領域画像群Ｇ３、Ｇ４及びＧ５を生成し、それぞれの局所領域画像について、局所特徴ベクトル生成部４５を介し同様にして局所特長ベクトルを求め、参照データ記憶部Ｍ４に追加する。
【００５３】
参照データ作成部４２は、参照データ記憶部Ｍ４において、アフィン変換の有無に拘わらず同一のペア特徴点に関する局所特長ベクトルのそれぞれに同一のクラスＩＤ（ＣＩＤ）を対応付ける。すなわち、参照データ記憶部Ｍ４には、例えば図１０（Ａ）に示すように、１つのペア特徴点に対し異なる複数のカメラ視点のそれぞれの局所特徴ベクトル、例
えばＶ０１０１、Ｖ０１０２、Ｖ０１０３、・・・が同一クラスＩＤ、例えばＣＩＤ０１でクラス分けされている。
【００５４】
参照データ記憶部Ｍ４にはさらに、各ＣＩＤが属するフレーム画像ＩＤ（ＦＩＤ）が対応付けられている。例えば、ＣＩＤ０１はＦＩＤ０１、ＦＩＤ１２が対応付けられている。これは、ＦＩＤ０１、ＦＩＤ１２のそれぞれのフレーム画像にＣＩＤ０１が含まれていることを意味する。
【００５５】
参照データ記憶部Ｍ４にはまた、各ＦＩＤに対応付けられた上記情報、例えば関連する本の情報、看板の詳細情報又は商品情報などが含まれている。
【００５６】
マッチング部４６は、決定木を局所特徴ベクトルの識別器（分類器）として備えている。識別器は、局所特徴ベクトルＶを入力としクラスＩＤを出力とする。決定木として、本実施例では、複数のツリーを用いたランダムフォレスト（Ｒａｎｄｏｍ  Ｆｏｒｅｓｔ）を用いる。その理由は、使用時に高速動作すること、マルチクラス識別器であること、識別精度が比較的高いこと、識別精度とメモリ使用量がトレードオフになるがそのパラメータがほぼツリーの数で調整できること（ツリーが少数（多数）だと識別精度が低い（高い）がメモリ使用量が小（大））である。
【００５７】
局所特徴ベクトルの各成分を２値化しないのは、決定木を用いることにより、２値化とは無関係にマッチングを高速に行うことができることと、２値化による局所特徴ベクトルの識別力低下を避けるためである。
【００５８】
マッチング部４６は、ランダムフォレスト識別器を学習しておく。すなわち、参照データ記憶部Ｍ４内の局所特徴ベクトルの全集合から、クラスＩＤが同一であるか否かを考慮せずにランダムに複数の部分集合（各部分集合の要素数は互いに同一）を決め、図１０（Ｂ）に示すように部分集合をツリーの分岐ノードで分割する分割関数ｆ（Ｖ）と分割の境界を定める閾値ｔとをランダムに決定し、情報利得が最大になるように学習して分割関数ｆ（Ｖ）のパラメータと閾値ｔとを更新し、また、各ツリーの各リーフノードに、クラスＩＤ毎の確率Ｐｒを対応付けておく（リーフノードに対応付けられていないＩＤはその確率が０）。
【００５９】
マッチング部４６は、各局所特徴ベクトルＶについて、ランダムフォレストの各ツリーを辿って、リーフノードでクラスＩＤ毎の確率を取得し、全ツリーでのクラスＩＤ毎の確率の総和が最大になるＩＤを、ランダムフォレスト識別器の出力とする。
【００６０】
すなわち、マッチング部４６は、局所特徴ベクトル記憶部Ｍ３内の各局所特徴ベクトルＶに対し、図９に示すようなステップＳ１０〜Ｓ１５の処理を行って局所特徴ベクトルＶのクラスＩＤを推定する。
【００６１】
（Ｓ１０）横軸をクラスＩＤとし、縦軸を頻度（正確には確率値の累積加算値）とする空のヒストグラムをフレーム画像ＩＤヒストグラム記憶部Ｍ５に生成する。以下、ランダムフォレストの各ツリーについて、ステップＳ１１〜Ｓ１４の処理を行う。
【００６２】
（Ｓ１２）局所特徴ベクトルＶに対し、ツリーを上から下へ辿り、その際、ツリーの各ノードにおいて、局所特徴ベクトルＶの対応する成分と、その閾値ｔと、分割関数ｆ（Ｖ）とに基づいて、どちらの子ノードへ分岐するかを決定し、リーフノードで得られるクラスＩＤの確率分布から、確率値が大きい順の、例えば３つのクラスＩＤを決定する。
【００６３】
（Ｓ１３）これらの３つのクラスＩＤの確率値を、ステップＳ１０のヒストグラムに追
加する。
【００６４】
（Ｓ１５）ヒストグラム上の最頻値を、この局所特徴ベクトルＶの特徴点のクラスＩＤと推定する（図１０（Ｂ）参照）。
【００６５】
（Ｓ１６）マッチング部４６は、推定したクラスＩＤ（ＣＩＤ）に対応するフレーム画像ＩＤ（ＦＩＤ）、例えば図１０（Ａ）の左側のクラスＩＤであるＩＤ０１に対応したＦＩＤ０１及びＦＩＤ１２を、参照データ記憶部Ｍ４から取得し、フレーム画像ＩＤヒストグラム記憶部Ｍ５内のフレーム画像ＩＤで識別されるカウンタを１だけインクリメントする。
【００６６】
マッチング部４６が局所特徴ベクトル記憶部Ｍ３内の各局所特徴ベクトルＶに対し図９の処理を行った後、フレーム画像ＩＤ推定部４７は、フレーム画像ＩＤヒストグラム記憶部Ｍ５内のカウンタ値が最大のフレーム画像ＩＤを、バッファ領域Ｍｉ内のフレーム画像のＩＤと推定する。
【００６７】
フレーム画像ＩＤの情報出力部４８は、このフレーム画像ＩＤに対応した情報を参照データ記憶部Ｍ４から取り出して、表示装置３２に出力する。
【００６８】
次に、マッチング部４６による処理の試験結果を説明する。
【００６９】
図１１〜図１４はいずれも、白鳥の写真と「Ｓｗａｎ」の文字列とを含む印刷物の入力画像に対し図７の処理を行いその途中結果を可視化したものを含む図であって、図１１は、該入力画像と該画像から抽出された特徴点ペアと、各ペアの特徴点間を接続した直線とを示す可視化画像の図であり、図１２〜図１４はいずれも、参照画像上の特徴点と図１１中の入力画像上の特徴点とをマッチング部４６でマッチングさせ、マッチングした特徴点間を直線で接続した図であり、図１２は該参照画像が該入力画像を縮小し回転したものに相当し、図１３は該参照画像が該入力画像を縮小し回転し射影変換したものに相当し、図１４は該参照画像が該入力画像を回転し図１２の場合よりも縮小したものに相当する図である。ここに参照画像は、この画像から上記参照データが得られる画像である。
【００７０】
図１２及び図１３の参照画像上の特徴点ペアはいずれも１３７対であり、このうち、図１２では１１１対（８１％）がマッチングに成功し、図１３では９３対（６８％）がマッチングに成功した。図１４の参照画像上の特徴点ペアは３６対であり、このうち２９対（８０％）がマッチングに成功した。
【００７１】
以上において、本発明の好適な実施例を説明したが、本発明には他にも種々の変形例が含まれ、上記各構成要素の機能を実現する他の構成を用いたもの、当業者であればこれらの構成又は機能から想到するであろう他の構成も、本発明に含まれる。
【００７２】
例えば、マッチング部４６で用いる識別器は、高速かつある程度以上マッチング精度が得られるものであればよく、ランダムフォレスト識別器に限定されず、バギングやブースティングなどのアンサンブル学習アルゴリズムを用いたものや単一の決定木を用いた識別器であってもよい。
【００７３】
また、参照データ記憶部Ｍ４は、アプリケーション起動後に上記のような参照データを参照データ作成部４２で自動生成する構成であってもよい。
【００７４】
さらに、本発明は、拡張現実（ＡＲ）表示装置などにも適用することができる。
【符号の説明】
【００７５】
１０  画像処理装置
２０  本体部
２１  プロセッサ
２２  バス
２３  記憶装置
２４  入力インターフェイス
２５  カメラインターフェイス
２６  ディスプレインターフェイス
２７  通信部
３０  入力装置
３１  カメラ
３２  表示装置
３３  アンテナ
４ｉ  画像入力部
４０  主処理部
４１  グレースケール化部
４２  参照データ作成部
４３  特徴点検出部
４４  アフィン変換部
４５  局所特徴ベクトル生成部
４６  マッチング部
４７  フレーム画像ＩＤ推定部
４８  フレーム画像ＩＤの情報出力部
３４０、３５０，３６  第１特徴点
３４１〜３４４、３５１、３７  第２特徴点
３５２、Ｃ１  第１サンプリング円
３５３、Ｃ２  第２サンプリング円
Ｐ０〜Ｐｆ、Ｑ０〜Ｑｆ  領域
Ｍｉ、Ｍ０  バッファ領域
Ｍ１  ２次元座標記憶部
Ｍ２  局所領域画像記憶部
Ｍ３  局所特徴ベクトル記憶部
Ｍ４  参照データ記憶部
Ｍ５  フレーム画像ＩＤヒストグラム記憶部
【要約】
【課題】スケール不変性及び回転不変性を持つ局所特徴ベクトルを、より低い計算コストで求められるようにする。
【解決手段】第１特徴点から距離が小さい順の４個の特徴点を第２特徴点とし、第１特徴点と、第２特徴点のそれぞれとのペア特徴点を選択し（Ｓ１）、特徴点間距離Ｌを算出し、第１、第２特徴点を中心とする距離Ｌに比例した半径の第１、第２サンプリング円を決定し（Ｓ３）、各円周上の１６個の画素のそれぞれを中心とする矩形画素領域のそれぞれの平均輝度Ｉ（Ｐｉ）、Ｉ（Ｑｉ）、ｉ＝０〜ｆを、直線Ｌの方向を基準として順にサンプリングし、これらのそれぞれと、第１、第２特徴点を中心とする矩形画素領域の平均輝度との差を、局所特徴ベクトルの成分としてこの順に並べる（Ｓ４）。
【選択図】図２【図１】
0005500404.tif 000002
【図２】
0005500404.tif 000003
【図５】
0005500404.tif 000004
【図７】
0005500404.tif 000005
【図８】
0005500404.tif 000006
【図９】
0005500404.tif 000007
【図１０】
0005500404.tif 000008
【図３】
0005500404.tif 000009
【図４】
0005500404.tif 000010
【図６】
0005500404.tif 000011
【図１１】
0005500404.tif 000012
【図１２】
0005500404.tif 000013
【図１３】
0005500404.tif 000014
【図１４】
0005500404.tif 000015