文書および／または画像のデータベースへの登録方法およびその検索方法
【課題】性能がより向上したLLAHによる文書画像検索手法を提供する。
【解決手段】性能向上の第１の側面はメモリ消費量の削減であり、第２の側面は処理の高速化である。メモリ消費量の削減のために信頼性の低い特徴量を取り除き、データベースの構造を単純化する。また処理高速化のために特徴量を画像の回転に対して不変なものにし、検索時に総当りで探索する処理を省略する。
【解決手段】性能向上の第１の側面はメモリ消費量の削減であり、第２の側面は処理の高速化である。メモリ消費量の削減のために信頼性の低い特徴量を取り除き、データベースの構造を単純化する。また処理高速化のために特徴量を画像の回転に対して不変なものにし、検索時に総当りで探索する処理を省略する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、Locally Likely Arrangement Hashing (LLAH)の手法を用いた文書および／または画像検索（文書画像検索）に関する。
【背景技術】
【０００２】
文書画像検索とは、与えられた検索質問に対応する文書および／または画像（文書画像）を、データベースから見つける処理である。文書画像検索の研究では、さまざまな種類の検索質問が提案されている（例えば、非特許文献1参照）。デジタルカメラを用いた文書画像検索は、デジタルカメラで撮影された文書画像を検索質問とするものである。このような形式の文書画像検索が実現されれば、印刷文書を撮影することでさまざまなサービスにつなげるという応用が可能になる。つまり、サービスを提供するためのメディアとして印刷文書を活用することが可能になる。例えば、データベースで文書画像にURLを関連付けておき、利用者が印刷文書を撮影すると、検索を通じて関連したWebページにアクセスするというサービスが考えられる。
【０００３】
我々はすでに、Locally Likely Arrangement Hashing (LLAH)というハッシュに基づく文書画像検索法を提案している（例えば、特許文献１参照）。LLAHは高速かつ高精度で、高いロバスト性をもつという特長がある。実験では、10,000ページのデータベースにおいて精度95%以上、検索の処理時間約100msという結果が得られている（非特許文献2参照）。このような高い精度と高速性は、LLAHで用いられる特徴量が安定性と識別性を兼ね備えているためである。また、LLAHは射影歪みや隠れ、紙面の非線形な湾曲という、デジタルカメラで文書を撮影するときに生じる問題（例えば、非特許文献3,4参照）に対してもロバストであることが確認されている。このロバスト性は、局所領域で定義される幾何学的不変量に基づく特徴量によって実現されている。
【０００４】
前述のLLAHは特徴点の局所的配置に基づいて文書画像の検索を行うため、局所特徴量を用いた画像検索の手法に分類される。LLAHの他にもこれまでに、さまざまな局所特徴量を用いた画像検索法が提案されている。それらは、SIFTなどの複雑な特徴量を用いるものと、特徴点などの単純な特徴量を用いるものに分類される。
【０００５】
前者としては、VideoGoogle（例えば、非特許文献5参照）が提案されている。これは、SIFT特徴量をクラスタリングしてコードブックを作成しておき、検索質問として与えられた画像から得られたSIFT特徴量をコードブックを用いてベクトル量子化し、検索を行う手法である。VideoGoogleでは高い精度を実現するためにはコードブックのサイズを大きくする必要があるが、コードブックのサイズが大きいとベクトル量子化の際の最近傍探索に時間がかかるため、処理時間が長くなる。また、SIFT特徴量の計算自体にも大きな計算量が必要である。
【０００６】
後者としては、画像から特徴点を抽出し、特徴点の座標のみから検索を行うGeometricHashing(GH)（例えば、非特許文献6参照）が提案されている。GHでは、特徴量の安定性の実現のために特徴点を組み合わせて特徴量を計算する。アフィン変換に対して不変なものにする場合、GHでは特徴点の数Nに対してO(N4)の計算量が検索処理で必要になる。従って、多くの特徴点をもつ複雑な画像では組み合わせの数が膨大となり、処理時間が増大する。文書画像は多数の特徴点をもつ複雑な画像であるため、GHを適用することは困難である（より詳細な議論は、例えば、非特許文献7参照）。
【特許文献１】国際公開第2006／092957号パンフレット
【非特許文献１】D.Doermann,"The indexing and retrieval of document images: a survey", Computer Vision and Image Understanding, vol.70, no.3, pp.287-298, 1998.
【非特許文献２】T.Nakai, K.Kise, and M.Iwamura, "Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval", Lecture Notes in Computer Science (7th International Workshop DAS2006), vol.3872, pp.541-552, 2006.
【非特許文献３】J.Liang, D.Doermann, and H.Li, "Camera-based analysis of text and documents: a survey", IJDAR, vol.7, pp.84-104, 2005.
【非特許文献４】P.Clark, and M.Mirmehdi, "Recognising text in real scenes", IJDAR, vol.4, pp.243-257, 2002.
【非特許文献５】J.Sivic, and A.Zisserman, "Video google: a text retrieval approach to object matching in videos", Proc. ICCV2003, vol.2, pp.1470-1477, 2003.
【非特許文献６】H.J.Wolfson, and I.Rigoutsos, "Geometric hashing: an overview", IEEE Computational Science & Engineering, vol.4, no.4, pp.10-21, 1997.
【非特許文献７】M.Iwamura, T.Nakai, and K.Kise, "Improvement of retrieval speed and required amount of memory for geometric hashing by combining local invariants", Proc. BMVC2007, 2007[toappear].
【発明の開示】
【発明が解決しようとする課題】
【０００７】
以上のように、LLAHは速度と精度を両立させ得る高性能な文書画像検索手法であるが、より広い用途に適用するためにさらなる高性能化が望まれている。この発明による性能向上へのアプローチは、主としてメモリ量の削減と処理時間の削減に向けられている。これらの性能指標は互いに関連するものであるが、理解を容易にするため個別に説明する。まず、LLAHは高い精度とロバスト性を実現するために、大量のメモリを必要とするという課題がある。具体的には、10,000ページの文書画像がデータベースに登録されている場合、高精度な検索を実現するためには約2.6GBのメモリが必要となる。このようなメモリ効率の悪さは、LLAHのスケーラビリティを制限するものである。さらに、カメラを用いたリアルタイム文書画像処理は高い利便性をもつ（例えば、C.H.Lampert, T.Braun, A.Ulges, D.Keysers, and T.M.Breuel, "Oblivious document capture and real-time retrieval", Proc. CBDAR2005, pp.79-86, 2005.参照）ため、LLAHのリアルタイム文書画像検索への応用が望まれている。しかし、LLAHをリアルタイム処理において用いるためには、検索処理のさらなる高速化が課題である。
【０００８】
この発明は、以上のような事情を考慮してなされたものであって、性能がより向上したLLAHによる文書画像検索手法を提供するものである。
【課題を解決するための手段】
【０００９】
この発明において、LLAHの性能を向上させる第1の側面は、主としてメモリ消費量の削減である。メモリ消費量の削減についての基本的なアイデアは、信頼性の低い特徴量を取り除き、データベースの構造を単純化するというものである。第2の側面は、主として処理の高速化である。処理の高速化については、特徴量を画像の回転に対して不変なものにし、検索時に総当たりで探索する処理を省略することで実現する。
【００１０】
この発明は、
（１）取得された画像の特徴点に基づいて計算される特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、取得された画像に対応する文書および／または画像をデータベースから検索する方法であって、取得された画像から抽出された各特徴点に対して局所的な特徴点の集合を決定する工程と、決定された各集合から特徴点の部分集合を選択する工程と、選択された各部分集合を特徴付ける量として、部分集合中の特徴点の複数の組合せについて幾何学的変換に対する不変量をそれぞれ求めると共に各特徴点の配置に基づくスコアを求める不変量算出工程と、求めた各不変量を組み合わせて特徴量を計算する特徴量算出工程と、前記特徴量と予めその特徴量が得られた前記データベース中の文書および／または画像に係る特徴量との一致度を調べ、取得された画像の各特徴点に係る前記一致度を統計的に処理することにより、取得された画像に対応するデータベース中の文書および／または画像を検索する工程の各工程をコンピュータが実行し、前記不変量算出工程は、部分集合中の各特徴点について近傍の特徴点との配置関係に基づいてそれぞれのスコアを算出し、前記特徴量算出工程は、前記スコアに基づいて特徴量を計算するための各不変量の組合せ順を決定することを特徴とする文書および／または画像の検索方法を提供する。また、
【００１１】
（２）入力された文書および／または画像の特徴を示す特徴点を抽出し、各特徴点から得られる特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、入力された文書および／または画像に対応するデータベース中の文書および／画像を検索する処理に係る前記データベースへ文書および／または画像を登録する方法であって、コンピュータが、登録すべき文書および／または画像から複数の特徴点を抽出し、抽出された各特徴点pについてその近傍n個の特徴点を選択し、それらn個の特徴点からm個（m≦n）をさらに選択する各組合せについて実行する次の工程(s1)〜(s4)、(s1) 対象とするm個の各特徴点p(i)(ここでiは各点に対応する0〜(m-1)の整数)について、所定方向の巡回順に並ぶc個(c＜m)の配置関係に基づくスコアS(i)をそれぞれ求める工程、(s2) スコアS(i)が最大の特徴点p(i)を開始点として前記巡回順のd個（d≦m）の点から特徴量の要素となる値を求め、開始点を巡回順にずらしていって各開始点からd個の点に基づいてそれぞれ要素を求め、開始点の巡回順に所定個数の要素を組み合わせた多次元ベクトルを特徴点pに係る特徴量として求める工程、(s3) 求めた特徴量から所定の計算手順でハッシュのインデックスを求める工程、(s4) 求めたインデックスでハッシュ表にアクセスし、(b)工程で求めた特徴量と特徴点pが抽出された文書および／または画像を識別する文書IDとをハッシュに登録する工程を実行することを特徴とし、前記検索は、入力された文書および／または画像から抽出された各特徴点pqについて、近傍n個の特徴点からm個を選択する各組み合わせについて実行する次の工程(r1)〜(r4)、(r1) 対象とするm個の各特徴点p(k)について、所定方向の巡回順に並ぶc個の配置関係に基づくスコアS(k)(ただしkは各点に対応する0〜(m-1)の整数)を求める工程、(r2) m個の特徴点のうちスコアS(k)が最大の点を開始点として前記巡回順のd個の点から特徴量の要素を求め、開始点を巡回順にずらしたd個からさらに異なる要素を求め、それらを開始点の巡回順に組み合わせた多次元ベクトルを点pqに係る特徴量として求める工程、(r3) 求めた特徴量から予め定められた計算手順でハッシュのインデックスを求め、そのインデックスでハッシュを参照する工程、(r4) 登録されたリストから得られる文書IDに対して投票する工程が実行されることにより、投票結果に基づいて検索結果が決定されるものである文書および／または画像のデータベースへの登録方法を提供する。さらにまた、この発明のより具体的な一態様として、
【００１２】
（３）入力された文書および／または画像の特徴を示す特徴点を抽出し、各特徴点から得られる特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、入力された文書および／または画像に対応するデータベース中の文書および／画像を検索する方法であって、前記データベースは、登録すべき文書および／または画像から抽出された各特徴点pについてその近傍n個の特徴点を選択し、それらn個の特徴点からm個（m≦n）をさらに選択する各組合せについて実行する次の工程(s1)〜(s4)、(s1) 対象とするm個の各特徴点p(i)(ここでiは各点に対応する0〜(m-1)の整数)について、所定方向の巡回順に並ぶc個(c＜m)の配置関係に基づくスコアS(i)をそれぞれ求める工程、(s2) スコアS(i)が最大の特徴点p(i)を開始点として前記巡回順のd個（d≦m）の点から特徴量の要素となる値を求め、開始点を巡回順にずらしていって各開始点からd個の点に基づいてそれぞれ要素を求め、開始点の巡回順に所定個数の要素を組み合わせた多次元ベクトルを特徴点pに係る特徴量として求める工程、(s3) 求めた特徴量から所定の計算手順でハッシュのインデックスを求める工程、(s4) 求めたインデックスでハッシュ表にアクセスし、(b)工程で求めた特徴量と特徴点pが抽出された文書および／または画像を識別する文書IDとをハッシュに登録する工程が実行されて文書および／または画像が登録されたものであり、コンピュータが、入力された文書および／または画像から抽出された各特徴点pqについて、近傍n個の特徴点からm個を選択する各組み合わせについて実行する次の工程(r1)〜(r4)、(r1) 対象とするm個の各特徴点p(k)について、所定方向の巡回順に並ぶc個の配置関係に基づくスコアS(k)(ただしkは各点に対応する0〜(m-1)の整数)を求める工程、(r2) m個の特徴点のうちスコアS(k)が最大の点を開始点として前記巡回順のd個の点から特徴量の要素を求め、開始点を巡回順にずらしたd個からさらに異なる要素を求め、それらを開始点の巡回順に組み合わせた多次元ベクトルを点pqに係る特徴量として求める工程、(r3) 求めた特徴量から予め定められた計算手順でハッシュのインデックスを求め、そのインデックスでハッシュを参照する工程、(r4) 登録されたリストから得られる文書IDに対して投票する工程を実行し、投票結果に基づいて検索結果を決定することを特徴とする文書および／または画像の検索方法を提供する。
【発明の効果】
【００１３】
この発明の（１）前記の検索方法は、近傍の特徴点との配置関係に基づいて算出されるスコアに基づいて特徴量を計算するための各不変量の組合せ順を決定するので、各不変量の組合せをすべて計算する場合に比べて組合せの数を減らすことができ、従って検索に要する処理時間を短縮することができる。
【００１４】
また、この発明の前記（２）の登録方法および前記（３）の検索方法は、工程(s2)が、スコアS(i)が最大の開始点に係る要素を先頭に開始点の巡回順に各要素を組み合わせた多次元ベクトルを用いて特徴量を計算し、それに対応して工程(r2)が、スコアS(k)が最大の開始点に係る要素を先頭に開始点の巡回順に各要素を組み合わせた多次元ベクトルを用いて特徴量を計算するので、登録時と検索時に同じ開始点を選ぶことができる。従って、すべての点を開始点とする組合せ（巡回置換）を試す場合に比べて、検索に要する処理時間を短縮することができる。
【００１５】
以下、この発明の好ましい態様について説明する。
前記（１）におて、各スコアは幾何学的変換に対する不変量であり、その算出手順は各特徴量の算出手順の一部と共通であってもよい。このようにすれば、幾何学的変換に対して安定したスコアを得ることができ、かつ、特徴量の算出と共にスコアを算出することができるので、特徴量とスコアを別に算出する場合に比べて処理時間を減らすことができる。
前記（２）および／または（３）において、前記スコアS(i)は、点p(i)を含む所定個数の特徴点から求められるアフィン不変量であり、前記スコアS(k)は、点p(k)を含む所定個数の特徴点から求められるアフィン不変量であってもよい。このようにすれば、幾何学的変換に対して安定したスコアを得ることができる。
【００１６】
また、前記（２）および／または（３）において、前記スコアS(i)の算出手順は、点pに係る特徴量の算出手順の一部と共通し、前記スコアS(k)の算出手順は、点pqに係る特徴量の算出手順の一部と共通してもよい。このようにすれば、各点について特徴量の算出と共にスコアを算出することができるので、特徴量と別にスコアを算出する場合に比べてスコアの算出に要する処理時間を減らすことができる。
【００１７】
さらにまた、前記（２）において、前記工程(d)は、ハッシュへの登録対象のうちインデックスの等しい登録対象が複数個ある場合それらをいずれもハッシュに登録せず、インデックスの異なる登録対象だけをハッシュに登録する工程でであってもよい。このようにすれば、同一インデックスについて複数の対象を登録する（ハッシュの衝突を許す）場合に比べてハッシュ表が単純になり、ハッシュ表の格納に必要なメモリ量を削減することができる。
ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
【００１９】
≪LLAHと、それを用いた検索処理≫
この発明の実施形態を説明する前に、オリジナルのLLAHと、それを用いた検索処理についてまず説明する。この発明の本質を理解するためには、その改良の基礎となる技術の理解が不可欠だからである。
【００２０】
1.処理の概要
図1に従来のLLAHを用いた検索処理の概要を示す。まず、特徴点抽出処理部15（Feature Point Extraction）で文書画像11および13は特徴点の集合に変換される。次に、各特徴点は登録処理部17（Storage）および検索処理部19（Retrieval）に入力される。これらの処理は特徴量計算処理部21（Calculation of Features）を共有している。登録処理部17は、各特徴点を独立に、その特徴量に基づいて文書画像データベース（Document Image Database）15に登録する。つまり、文書画像11は特徴点を用いてインデキシングされる。検索処理部19は、検索質問13の各特徴量を用いて文書画像データベース23にアクセスし、投票処理によって対応する文書画像を決定する。以下では各処理部が実行する処理について説明する。
【００２１】
2.特徴点抽出処理
特徴点抽出処理部15が実行する処理である。LLAHでは特徴点の配置に基づいて文書画像のマッチングを行う。従って、特徴点抽出処理では、射影歪みやノイズが生じていた場合や低解像度の場合でも同一の点を抽出する必要がある。そのため、単語領域の重心を特徴点として用いる。
【００２２】
図2は、従来の特徴点抽出の手順を示す説明図である。図2に示すように、特徴点抽出処理部は、まず、入力画像（図2(a)）を適応2値化し、2値画像（図2(b)）を得る。次に、2値画像をガウシアンフィルタでぼかし、再度適応2値化を行うと、単語ごとに連結された画像（図2(c)）が得られる。最後に連結成分の重心を計算して特徴点（図2(d)）とする。
【００２３】
3.特徴量計算
特徴量計算処理部21が実行する処理である。特徴量とは、文書画像の特徴点を表現する値である。特徴点のマッチングは特徴量に基づいて行われる。そのため、特徴量は以下の2つの条件を満たす必要がある。1つは、同一の特徴点は、さまざまな外乱が生じて画像の見え方が変わったとしても、同一の特徴量を与えなければならないというものである。同一の特徴点であるにもかかわらず、登録処理と検索処理で異なる特徴量が得られた場合、それらの対応付けを行うことはできない。そのため、正しい検索結果を得ることができなくなる。この明細書において、この条件を"特徴量の安定性"と呼ぶ。もう1つの条件は、異なる特徴点は異なる特徴量を与えなければならないというものである。異なる特徴点から同一の特徴量が得られた場合、誤った特徴点と対応付けられてしまう。そのため、正しいものだけでなく誤ったものも検索結果として得られることになる。この明細書において、この条件を"特徴量の識別性"と呼ぶ。正確な検索のためには、安定性と識別性を両立した特徴量が必要である。
【００２４】
3-1.安定性
カメラで文書を撮影する場合、隠れが生じていたり、紙面の一部だけが撮影される場合がある。従って安定性の実現のためには、特徴量は文書画像の部分から計算されるものが望ましい。LLAHでは、各特徴点についてその近傍の特徴点の配置から特徴量を計算する。特徴量が文書画像の局所領域から得られるため、同じ領域が撮影されていれば同じ特徴量を計算することができる。
【００２５】
カメラを用いる場合、画像が射影歪みを受けることがある。そこで、射影歪みが生じても安定な特徴量を計算するために、幾何学的不変量を用いる。カメラで斜め方向から撮影するときに生じる歪みは射影変換であるため、射影変換の不変量である複比を用いることが考えられる。しかし、非特許文献2の結果より、射影変換より自由度の低い変換であるアフィン変換の不変量を用いる方が検索において高い精度をもたらすことが確認されている。これは、局所領域においては射影変換はアフィン変換に近似可能であることと、アフィン不変量の方が特徴点の位置の変動に強く安定であることが原因である。
この実施形態では、同一平面上の4点ABCDから以下の式で計算されるアフィン不変量を用いる。
【００２６】
【数１】
【００２７】
ここで、P(A,B,C)は頂点A，B，Cをもつ三角形の面積である。
近傍点の配置から特徴点pの特徴量を計算する場合、最も単純なものはpの近傍4点から計算されるアフィン不変量を特徴量とするものである。しかし、射影歪みが生じた場合は近傍点に異なるものが得られることがある。図3は、従来のLLAHにおいて、同じ文書を異なる視点から見たときの特徴点と近傍8点の配置を示す説明図である。図3(a)および(b)の2枚の画像は、特徴点pとその近傍の8つの特徴点を異なる視点から見たときの例を示している。図中、丸で囲まれた数字は点pからの距離の順位である。黒抜きの数字（図3(a)の「3」と図3(b)の「8」）は異なる点が得られている例を示す。
【００２８】
従って、近傍4点から計算されるアフィン不変量は安定ではない。この問題を解決するため、より広い範囲の局所領域を用いる。図3では、近傍7点のうち6点までは共通のものが得られている。このことから、近傍n点のうちm(≦n)点まではある程度の射影歪みが生じていても共通のものを得ることができると考えられる。以上のことから、m点を用いて安定な特徴量を計算する。
【００２９】
図4は、従来のLLAHにおいて、近傍n(=7)点からすべてのm(=6)点の組み合わせを選択する組合せを示す説明図である。図4に示されるように、LLAHにおいてはn点からのすべてのm点の組み合わせ
【００３０】
【数２】
を調べる。n点のうちm点が共通であれば、同じm点を得ることができる。LLAHではこのようにして特徴量の安定性を実現している。
【００３１】
3-2.識別性
m点から特徴量を計算する場合、最も単純な方法はm=4として4点から計算されるアフィン不変量を特徴量とするというものである。しかし、異なる文書から得た特徴点でも、類似した4点の配置をもつ場合があるため、このような単純な方法は識別性に問題がある。そこで、識別性を向上させるため、m(＞4)の値を大きくしてより多くの点から特徴量を計算する。mが大きくなると、異なる文書画像から類似したm点の配置をもつ確率が低くなる。図5は、従来のLLAHにおいて、m(=6)点からのすべての4点の組み合わせと、それら4点から計算されるアフィン不変量の列を示す説明図である。図5に示されるように、m点の配置は、m点から4点をそれぞれ選び、そこから計算されるアフィン不変量を離散化した値の列
【００３２】
【数３】
で表現される。m点から4点を選ぶ手法の詳細は次のとおりである。まず、m点から適当に1つの点p0を選ぶ。そして、m点を特徴点pを中心としかつp0を先頭にして時計回りに並べた特徴点の列Lm=(p0,…pm-1)を作る。このとき、Lm中の連続する4点（循環を含む）を選んでできる各部分列がm点から4点を選ぶ各組合せである。
【００３３】
4.登録
登録処理のアルゴリズムの一例を図6に示す。ここで、文書IDとは文書の識別番号、点IDとは特徴点の識別番号である。
ハッシュ表（ハッシュテーブル）のインデックスは以下に示すハッシュ関数で計算される。
【００３４】
【数４】
ここで、r(i)はアフィン不変量の離散値、kは離散化レベル数、Hsizeはハッシュ表のサイズである。
【００３５】
図７は、従来のLLAHにおいて、ハッシュ表の構造の一例を示す説明図である。図7に示されるように、文書ID、点ID、
【００３６】
【数５】
の組が多次元の特徴量（特徴ベクトル）としてハッシュ表に登録される。衝突が生じた場合は、リスト形式で追加される。
【００３７】
5.検索
検索処理のアルゴリズムの一例を図8に示す。LLAHでは、投票テーブルを用いた登録文書への投票を通じて検索を行う。
まず、7-10行目で登録処理と同様にハッシュ表のインデックスを求める。得られたインデックスを用いて、11行目で図7に示されるリストを得る。リストの各項目について
【００３８】
【数６】
【００３９】
が一致するか調べ、一致していたら投票テーブルの文書IDの項目をインクリメントする。最後に、最大の得票数を得た文書を検索結果として出力する。
以上が、オリジナルのLLAHとそれを用いた検索処理についての説明である。次に、性能向上の第1の側面であるメモリ量の削減について説明する。
【００４０】
≪必要メモリ量の削減≫
LLAHでは、安定性の実現のために多くの特徴量を計算し、それらすべてをリスト形式でハッシュ表へ保存する。そのため、必要メモリ量が多くなる。そこで、重要性の低い特徴量をデータベースから削除し、データ構造を改めることで記憶容量の削減を図る。
【００４１】
必要メモリ量の削減手法は、基本的に次のようなアイデアに基づく。ハッシュテーブルに登録する特徴ベクトルのうち、多数の衝突を起こしているものについては、識別にそれほど有効ではないため、削除してもよい。記録する特徴ベクトルが少なくなれば、それだけメモリ量を削減できる。
【００４２】
ただし、これだけでは、既存のもの（たとえば非特許文献5に記載の方法）との差異がない。この発明の特徴は、衝突を起こしている特徴ベクトルを「すべて」削除する点にある。すべて削除することによって、識別性や安定性が損なわれることが考えられたが、後述する実験の結果、以外にもこれは問題とはならなかった。図９は、この発明において、衝突を起こしている特徴ベクトルをすべて削除した状態のハッシュ表の一例を示す説明図である。図９に示すようにデータ構造をきわめて単純な形にすることが可能となり、必要メモリの量を大幅に削減できる。
【００４３】
以下に具体例におけるメモリ消費量を示す。
n=7, m=6, Hsize=1.28×108
登録ページ数10,000
文書画像1枚あたりの平均特徴点数630
文書ID、点ID、r(i)はそれぞれ2バイト、2バイト、1バイトの変数に保存される
ポインタ変数のサイズは8バイト
このような条件では、図7左側のハッシュ表は1.28×108×8=1.0GB、図7右側のリストは10,000×630×7×(2＋2＋1×15＋8)=1.2GBを消費する。従って、必要メモリ量の合計は2.2GBとなる。
【００４４】
メモリの削減のためには、重要性の低いデータを削除することが望ましい。重要性の低いデータとして、リストにおいて衝突を起こしているものが挙げられる。これは、衝突を起こしているものは識別性に欠ける可能性があり、また頻繁に生じる特徴量であるため、検索処理において速度の低下を引き起こすからである。また、実験では衝突を起こしているものはハッシュ表でデータの登録されているもののうち28%程度であり、削除しても影響は限られると考えられる。以上の理由から、ハッシュ表において衝突の生じているリストを削除する。これにより、メモリ容量の削減が期待できる。同時に、処理時間の短縮（高速化）も期待できる。
【００４５】
衝突のあったリストを削除すると、データ構造の変更によるさらなる容量の削減が可能になる。リストにおける特徴ベクトルは、衝突している場合に適切なものを見つけるためにあった。そのため、衝突がないのならば特徴ベクトルを保存する必要がなくなる。また、衝突がないのならそもそもリスト形式にする必要もない。そこで、図9に示すような単純なハッシュ表にすることで、記憶容量を削減する。単純なハッシュ表では、前に挙げた例の条件（Hsize=1.28×108）、文書IDと点IDの変数サイズ2バイト）の場合は必要メモリ量は512MBとなり、77%のメモリ消費量が削減される。
【００４６】
図16は、前述のメモリ消費量削減の工夫がなされた登録処理（メモリ削減版）のアルゴリズムの一例を示す図である。図6（従来の登録処理）と図16のアルゴリズムとを比較するとstep10以降が異なる。特に、step10〜14が、従来のアルゴリズムに追加された部分である。前記部分の追加によって、図16のアルゴリズムは、図9に示すように衝突を起こしたものが除外されたハッシュ表を用いることになる。即ち、あるインデックス(Hindex)に対してハッシュ表にデータを登録する際、既にデータが登録されているか否かを調べる（step11）。未だデータが登録されていなければ、従来と同様にそのデータを登録するが(step12)、既にデータが登録されていた場合は(step13)、衝突を意味する。そこで、そのデータには衝突の印を付けて登録する（step14）。検索時には、衝突の印が付いたものを使用しない。
【００４７】
図18は、図16の登録処理に対応する検索処理のアルゴリズムの一例を示す図である。図6（従来の登録処理）と図16のアルゴリズムとを比較するとstep11以降が異なる。図6の従来手法のstep11〜13は、衝突が生じた場合に対処するためのステップである。図16（メモリ削減版）のアルゴリズムには、その部分が存在しない。それに代えて、登録時に衝突の印が付されたデータか否かをチェックするためのステップ(step11)が設けられている。
【００４８】
メモリを圧縮するもう一つの方法は、ハッシュのサイズHsizeを小さくすることである。しかし、ハッシュサイズは検索性能に大きく影響する。特に、衝突した項目を削除する場合は、ハッシュサイズを小さくすると衝突が多発し、多くの登録データが失われて検索精度が大きく低下する可能性がある。従って、ハッシュ表の占有率は低く保ち、必要に応じてハッシュサイズを大きくする必要がある。
【００４９】
≪検索処理の高速化≫
次に、検索処理の高速化のための登録および検索アルゴリズムの改良について述べる。
検索処理の高速化は、次のようなアイデアである。従来法ではどの点から不変量を計算するのかという、「開始点」が一意に定まらなかったため、開始点を一つずつずらしながら、すべての可能性を試していた。一方、提案の手法では、点の配置から、どの点が開始点となるべきかを求めることで、計算量を削減している。
【００５０】
基本的な方法は次のとおりである。点の配置から各点のスコアを求め、そのスコアが最大のものを開始点とする。ただし、いくつか注意すべきポイントがある。
【００５１】
1.開始点を求めるための計算量が十分小さいこと。
これが大きいと、開始点をずらしながらすべての可能性を試すほうが、高速である、ということになりかねない。
2.開始点を求めるためのメモリ量が十分小さいこと。
これが大きいと、やはり問題を招く。
3.開始点は、幾何学的変換に不変に求められること。
撮影角度によって、求められる開始点は変化しないことが必要である。
4.同一の特徴ベクトルが得られる点の配置からは、同一の開始点が得られること。
【００５２】
この条件は、少々わかりにくい。まず、この発明では、特徴ベクトルが安定して得られるように種々の工夫をこらしている。たとえば、アフィン不変量を用いて特徴ベクトルを計算することも、その工夫のひとつである。しかしながら、画像によっては、ノイズや撮影角度、照明など、種々の条件が悪化することによって、同じ特徴ベクトルが得られず、異なる特徴ベクトルとなってしまうことがある。異なる特徴ベクトルが得られた場合、もはや元の特徴ベクトルとの対応を取ることができないため、検索には役に立たない。逆にいえば、同じ特徴ベクトルが得られるものについては、検索に役立てることができる。さらにいえば、これらを漏れなく検索に役立てる必要がでてくる。
【００５３】
ここで、開始点を求めるための不変量の計算と、特徴ベクトルを求めるための不変量の計算が、全く異なる場合を考えてみよう。異なる方法で求められた不変量は、変動の傾向も異なるため、同じ特徴ベクトルが得られる場合であっても、開始点が異なってしまうことが考えられる。そのようなケースが生じると、折角、同じ特徴ベクトルが得られているにもかかわらず、開始点が異なるために、検索に役立てることができない。
【００５４】
逆に、開始点を求めるための不変量の計算と、特徴ベクトルを求めるための不変量の計算が同じ傾向をもっており、同じ特徴ベクトルが得られる場合には、必ず同じ開始点を得ることができれば、好都合である。
【００５５】
このような条件を満たすことは困難であると思われるかもしれないが、実は、特徴ベクトルの計算に用いる不変量の一部を、開始点の計算に用いることによって、実現できる。特徴ベクトルが同じであるためには、特徴ベクトルを構成する不変量がすべて同じ値に量子化される必要がある。したがって、その一部を用いて開始点を計算すれば、特徴ベクトルが同じである場合には、必ず開始点も同じであるといえる。
【００５６】
この発明で提案している方式は、上記の４点を満たすものといえる。
なお、特徴ベクトルに用いる不変量が、現在のアフィン不変量ではなく、相似不変量や射影不変量になっても、同じアイデアを用いることが可能である。
【００５７】
図8に示されるオリジナルのLLAHに係る検索アルゴリズムでは、4-5行目でLmのすべての巡回置換を試すために、Pmのすべての点が開始点p0となるように繰り返し処理を行う。これは、カメラで画像を撮影する際に回転が生じるため、検索時のLmと登録時のLmが必ずしも一致しないためである。
しかし、登録時と検索時に同じ開始点p0を選ぶことができれば、巡回置換を試す必要はない。以下の実施形態では、開始点の選択規則を導入し、検索処理の効率化を図る。
【００５８】
図10は、この発明に係る開始点の選択規則を示す説明図である。特徴点pに属するm点の各点iについて、後続の3点と合わせてアフィン不変量s(i)を計算する。
【００５９】
【数７】
の中で最大のものがs(j)であれば、点jを開始点として選択する。図10の例では、s(1)が最大であるため点1が開始点となる。最大値を取るものが複数あった場合、次の
【００６０】
【数８】
の最大値を調べて開始点を定める。例えば、s(i)=s(j)がともに最大値であれば、
【００６１】
【数９】
を比較する。
【００６２】
【数１０】
の方が大きければ、点i が開始点として選ばれる。ここで
【００６３】
【数１１】
であれば、さらに次の値
【００６４】
【数１２】
を比較し、開始点を選択する。
【００６５】
図17は、メモリ削減版に加えて、前述の高速化の工夫がなされた登録処理（メモリ削減+高速化版）のアルゴリズムの一例を示す図である。図6（従来の登録処理）あるいは図16と図17のアルゴリズムとを比較すると、step4において、開始点を決めている点が異なる。従来手法およびメモリ削減版では，たまたま最初になった点が開始点となるが、高速化版ではどの開始点にするかを図10の選択規則により計算して決めている。
【００６６】
図19は、図17の登録処理に対応する検索処理のアルゴリズムの一例を示す図である。図6（従来の登録処理）あるは図16と図19のアルゴリズムでは、開始点が一意に定まらないため、開始点を巡回させながらすべてを試す処理を行っている。これが、図6および図16のstep4の処理である。これに対して、図20（メモリ削減+高速化版）のアルゴリズムでは、step4で開始点を選択規則に基づいて計算することによって、m個の各点p0について試すforループを削除している。
【００６７】
なお、この実施形態ではメモリ削減版と、メモリ削減版+高速化版を説明し、高速化版のみの例を省略しているが、高速化版単独の実施形態は両者の差異点を抽出することで当業者に容易に理解されるものである。この明細書の開示の範囲には、高速化版単独の態様も含まれていると解されるべきである。
【００６８】
≪実験例≫
この発明に係る手法の効果を調べるため、元のLLAHと改善されたLLAHで検索実験を行い、性能を比較した。前述の「必要メモリ量の削減」と前述の「検索処理の高速化」の効果を明確にするため、以下の3つのバージョンのLLAHでメモリ消費量、処理時間、精度を調べた。
(1) オリジナル
(2) メモリ削減版
(3) メモリ削減＋高速化版
(2)および(3)がこの発明に係る手法である。
【００６９】
データベースに登録された文書画像は、主に予稿集のCD-ROMから集められた、1段組および2段組の英語論文のPDFファイルを200dpiで画像に変換したものである。図11は、この発明に係る実験例に用いられたデータベースに登録された文書画像の一例を示す図である。検索質問の文書画像は630万画素のデジタルカメラで撮影されたものである。図12は、この発明に係る実験例に用いられた検索質問画像の一例を示す図である。図12に示されるように、検索質問は紙面に対して斜め方向（約45度）から撮影されたものである。検索質問の撮影角度（45度）と登録画像の撮影角度（90度）は異なるため、これらを用いた実験によって、手法の射影歪みに対するロバスト性が示すことができる。なお、検索質問画像の受ける射影歪みは非特許文献2のものより強いものである。実験に用いた計算機は、AMDOpteron2.8GHzのCPUと16GBのメモリをもつものである。パラメータはn=7、m=6、k=15、Hsize=1.28×108とした(異なるnとmの場合の実験結果については非特許文献2を参照のこと)。
【００７０】
1.必要メモリ量
図13は、この発明に係る実験例において登録ページ数を100，1,000，10,000と増加させたときの3つのバージョンのLLAHにおけるメモリ消費量の比較実験結果を示すグラフである。オリジナルのLLAHは、登録ページ数10,000では本発明に係るメモリの削減版に比べて5倍のメモリを消費した。さらに、登録ページ数の増加に伴ってメモリの消費量も増加した。これは、オリジナルのLLAHではデータベースでリストを用いており、登録ページ数が増加するとメモリ消費量も増加するためである。一方、本発明に係るメモリ削減の改善がなされたLLAHでは、登録ページ数が増加してもメモリ消費量は一定であった。これは、データベースが単純なハッシュ表であり、ハッシュ表のサイズが固定されているためである。
【００７１】
2.処理時間
図14は、処理時間について各バージョンの比較実験結果を示すグラフである。このように、本発明に係る高速化バージョンはそれ以外に比べておよそ60%の処理時間の削減を実現した。これは、巡回置換を試すための繰り返し処理を避けることで不変量の計算回数やハッシュへのアクセス回数を減らすことができたためと考えられる。
【００７２】
また、本発明に係るメモリ削減版はオリジナルに比べて登録ページ数の増加に対する速度の低下が見られなかった。これは、オリジナルではリスト構造のためデータ量が増えるとリストをたどる処理時間が増加する一方、単純なハッシュ表であるメモリ削減版は常に一定の処理時間しか要しないためと考えられる。
【００７３】
3.精度
図15は、それぞれのバージョンの各データベースサイズにおける精度についての比較実験結果を示すグラフである。処理時間とメモリ効率に加えて、精度に関しても本発明に係るメモリ削減版および高速化版はオリジナルより高い性能を示した。オリジナルが登録ページ数の増加に伴って精度を低下させた一方で、メモリ削減版および高速化版は登録ページ数10,000では精度がやや低下したものの、オリジナルよりも高い精度を維持した。
【００７４】
この実施形態に係る改善手法が精度の向上を意図したものではないにも関わらず、精度の向上をもたらした理由は、メモリの削減のために識別性の低い特徴量を削除した結果、誤投票を減らすことができたことと考えられる。メモリ削減版および高速化版では衝突を生じた項目は削除される。そのような項目は誤った投票を生じやすいため、それらを削除することで精度の向上が実現されたと考えられる。
【００７５】
以上の実験例で示されるように、10,000ページのデータベースを用いた実験では、元のLLAHに対して必要メモリ量は1/5、処理時間は2/5となることが確認された。また実験では、改善されたLLAHは高いスケーラビリティをもつことも示された。データベースの登録画像数が10,000までは、メモリ消費量と処理時間がほぼ一定であった。
【００７６】
この発明では、LLAHの改良手法を提案した。不必要な特徴量の削除とデータ構造の単純化により、必要メモリ量の削減を実現した。また、検索アルゴリズムを改良することで処理時間を削減することができた。実験により、必要メモリ量の80%、処理時間の60%が削減されたことを確認した。実験ではさらに、改良手法では精度についても向上することが確認された。以上のことから、LLAHのスケーラビリティや、リアルタイム処理などの高速性を要求するアプリケーションへの拡張性が向上したといえる。
【００７７】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【図面の簡単な説明】
【００７８】
【図１】従来のLLAHを用いた検索処理の概要を示すブロック図である。
【図２】従来の特徴点抽出の手順を示す説明図である。
【図３】従来のLLAHにおいて、同じ文書を異なる視点から見たときの特徴点と近傍8点の配置を示す説明図である。
【図４】従来のLLAHにおいて、近傍n(=7)点からすべてのm(=6)点の組み合わせを選択する組合せを示す説明図である。
【図５】従来のLLAHにおいて、m(=6)点からのすべての4点の組み合わせと、それら4点から計算されるアフィン不変量の列を示す説明図である。
【図６】従来のLLAHの登録処理のアルゴリズムの一例を示す説明図である。
【図７】従来のLLAHにおいて、ハッシュ表の構造の一例を示す説明図である。
【図８】従来のLLAHの検索処理のアルゴリズムの一例を示す説明図である。
【図９】この発明において、衝突を起こしている特徴ベクトルをすべて削除した状態のハッシュ表の一例を示す説明図である。
【図１０】この発明に係る開始点の選択規則を示す説明図である。
【図１１】この発明に係る実験例に用いられたデータベースに登録された文書画像の一例を示す図である。
【図１２】この発明に係る実験例に用いられた検索質問画像の一例を示す図である。
【図１３】この発明に係る実験例において、登録ページ数を100，1,000，10,000と増加させたときの3つのバージョンのLLAHにおけるメモリ消費量の比較実験結果を示すグラフである。
【図１４】この発明に係る実験例において、処理時間について各バージョンの比較実験結果を示すグラフである。
【図１５】この発明に係る実験例において、それぞれのバージョンの各データベースサイズにおける精度についての比較実験結果を示すグラフである。
【図１６】この実施形態において、メモリ消費量削減の工夫がなされた登録処理（メモリ削減版）のアルゴリズムの一例を示す図である。
【図１７】この実施形態において、メモリ削減版に加えて、前述の高速化の工夫がなされた登録処理（メモリ削減+高速化版）のアルゴリズムの一例を示す図である。
【図１８】この実施形態において、図16の登録処理に対応する検索処理のアルゴリズムの一例を示す図である。
【図１９】この実施形態において、図17の登録処理に対応する検索処理のアルゴリズムの一例を示す図である。
【符号の説明】
【００７９】
１１：登録画像（文書画像）
１３：検索質問（文書画像）
１５：特徴点抽出処理部
１７：登録処理部
１９：検索処理部
２１：特徴量計算処理部
２３：文書画像データベース
【技術分野】
【０００１】
この発明は、Locally Likely Arrangement Hashing (LLAH)の手法を用いた文書および／または画像検索（文書画像検索）に関する。
【背景技術】
【０００２】
文書画像検索とは、与えられた検索質問に対応する文書および／または画像（文書画像）を、データベースから見つける処理である。文書画像検索の研究では、さまざまな種類の検索質問が提案されている（例えば、非特許文献1参照）。デジタルカメラを用いた文書画像検索は、デジタルカメラで撮影された文書画像を検索質問とするものである。このような形式の文書画像検索が実現されれば、印刷文書を撮影することでさまざまなサービスにつなげるという応用が可能になる。つまり、サービスを提供するためのメディアとして印刷文書を活用することが可能になる。例えば、データベースで文書画像にURLを関連付けておき、利用者が印刷文書を撮影すると、検索を通じて関連したWebページにアクセスするというサービスが考えられる。
【０００３】
我々はすでに、Locally Likely Arrangement Hashing (LLAH)というハッシュに基づく文書画像検索法を提案している（例えば、特許文献１参照）。LLAHは高速かつ高精度で、高いロバスト性をもつという特長がある。実験では、10,000ページのデータベースにおいて精度95%以上、検索の処理時間約100msという結果が得られている（非特許文献2参照）。このような高い精度と高速性は、LLAHで用いられる特徴量が安定性と識別性を兼ね備えているためである。また、LLAHは射影歪みや隠れ、紙面の非線形な湾曲という、デジタルカメラで文書を撮影するときに生じる問題（例えば、非特許文献3,4参照）に対してもロバストであることが確認されている。このロバスト性は、局所領域で定義される幾何学的不変量に基づく特徴量によって実現されている。
【０００４】
前述のLLAHは特徴点の局所的配置に基づいて文書画像の検索を行うため、局所特徴量を用いた画像検索の手法に分類される。LLAHの他にもこれまでに、さまざまな局所特徴量を用いた画像検索法が提案されている。それらは、SIFTなどの複雑な特徴量を用いるものと、特徴点などの単純な特徴量を用いるものに分類される。
【０００５】
前者としては、VideoGoogle（例えば、非特許文献5参照）が提案されている。これは、SIFT特徴量をクラスタリングしてコードブックを作成しておき、検索質問として与えられた画像から得られたSIFT特徴量をコードブックを用いてベクトル量子化し、検索を行う手法である。VideoGoogleでは高い精度を実現するためにはコードブックのサイズを大きくする必要があるが、コードブックのサイズが大きいとベクトル量子化の際の最近傍探索に時間がかかるため、処理時間が長くなる。また、SIFT特徴量の計算自体にも大きな計算量が必要である。
【０００６】
後者としては、画像から特徴点を抽出し、特徴点の座標のみから検索を行うGeometricHashing(GH)（例えば、非特許文献6参照）が提案されている。GHでは、特徴量の安定性の実現のために特徴点を組み合わせて特徴量を計算する。アフィン変換に対して不変なものにする場合、GHでは特徴点の数Nに対してO(N4)の計算量が検索処理で必要になる。従って、多くの特徴点をもつ複雑な画像では組み合わせの数が膨大となり、処理時間が増大する。文書画像は多数の特徴点をもつ複雑な画像であるため、GHを適用することは困難である（より詳細な議論は、例えば、非特許文献7参照）。
【特許文献１】国際公開第2006／092957号パンフレット
【非特許文献１】D.Doermann,"The indexing and retrieval of document images: a survey", Computer Vision and Image Understanding, vol.70, no.3, pp.287-298, 1998.
【非特許文献２】T.Nakai, K.Kise, and M.Iwamura, "Use of affine invariants in locally likely arrangement hashing for camera-based document image retrieval", Lecture Notes in Computer Science (7th International Workshop DAS2006), vol.3872, pp.541-552, 2006.
【非特許文献３】J.Liang, D.Doermann, and H.Li, "Camera-based analysis of text and documents: a survey", IJDAR, vol.7, pp.84-104, 2005.
【非特許文献４】P.Clark, and M.Mirmehdi, "Recognising text in real scenes", IJDAR, vol.4, pp.243-257, 2002.
【非特許文献５】J.Sivic, and A.Zisserman, "Video google: a text retrieval approach to object matching in videos", Proc. ICCV2003, vol.2, pp.1470-1477, 2003.
【非特許文献６】H.J.Wolfson, and I.Rigoutsos, "Geometric hashing: an overview", IEEE Computational Science & Engineering, vol.4, no.4, pp.10-21, 1997.
【非特許文献７】M.Iwamura, T.Nakai, and K.Kise, "Improvement of retrieval speed and required amount of memory for geometric hashing by combining local invariants", Proc. BMVC2007, 2007[toappear].
【発明の開示】
【発明が解決しようとする課題】
【０００７】
以上のように、LLAHは速度と精度を両立させ得る高性能な文書画像検索手法であるが、より広い用途に適用するためにさらなる高性能化が望まれている。この発明による性能向上へのアプローチは、主としてメモリ量の削減と処理時間の削減に向けられている。これらの性能指標は互いに関連するものであるが、理解を容易にするため個別に説明する。まず、LLAHは高い精度とロバスト性を実現するために、大量のメモリを必要とするという課題がある。具体的には、10,000ページの文書画像がデータベースに登録されている場合、高精度な検索を実現するためには約2.6GBのメモリが必要となる。このようなメモリ効率の悪さは、LLAHのスケーラビリティを制限するものである。さらに、カメラを用いたリアルタイム文書画像処理は高い利便性をもつ（例えば、C.H.Lampert, T.Braun, A.Ulges, D.Keysers, and T.M.Breuel, "Oblivious document capture and real-time retrieval", Proc. CBDAR2005, pp.79-86, 2005.参照）ため、LLAHのリアルタイム文書画像検索への応用が望まれている。しかし、LLAHをリアルタイム処理において用いるためには、検索処理のさらなる高速化が課題である。
【０００８】
この発明は、以上のような事情を考慮してなされたものであって、性能がより向上したLLAHによる文書画像検索手法を提供するものである。
【課題を解決するための手段】
【０００９】
この発明において、LLAHの性能を向上させる第1の側面は、主としてメモリ消費量の削減である。メモリ消費量の削減についての基本的なアイデアは、信頼性の低い特徴量を取り除き、データベースの構造を単純化するというものである。第2の側面は、主として処理の高速化である。処理の高速化については、特徴量を画像の回転に対して不変なものにし、検索時に総当たりで探索する処理を省略することで実現する。
【００１０】
この発明は、
（１）取得された画像の特徴点に基づいて計算される特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、取得された画像に対応する文書および／または画像をデータベースから検索する方法であって、取得された画像から抽出された各特徴点に対して局所的な特徴点の集合を決定する工程と、決定された各集合から特徴点の部分集合を選択する工程と、選択された各部分集合を特徴付ける量として、部分集合中の特徴点の複数の組合せについて幾何学的変換に対する不変量をそれぞれ求めると共に各特徴点の配置に基づくスコアを求める不変量算出工程と、求めた各不変量を組み合わせて特徴量を計算する特徴量算出工程と、前記特徴量と予めその特徴量が得られた前記データベース中の文書および／または画像に係る特徴量との一致度を調べ、取得された画像の各特徴点に係る前記一致度を統計的に処理することにより、取得された画像に対応するデータベース中の文書および／または画像を検索する工程の各工程をコンピュータが実行し、前記不変量算出工程は、部分集合中の各特徴点について近傍の特徴点との配置関係に基づいてそれぞれのスコアを算出し、前記特徴量算出工程は、前記スコアに基づいて特徴量を計算するための各不変量の組合せ順を決定することを特徴とする文書および／または画像の検索方法を提供する。また、
【００１１】
（２）入力された文書および／または画像の特徴を示す特徴点を抽出し、各特徴点から得られる特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、入力された文書および／または画像に対応するデータベース中の文書および／画像を検索する処理に係る前記データベースへ文書および／または画像を登録する方法であって、コンピュータが、登録すべき文書および／または画像から複数の特徴点を抽出し、抽出された各特徴点pについてその近傍n個の特徴点を選択し、それらn個の特徴点からm個（m≦n）をさらに選択する各組合せについて実行する次の工程(s1)〜(s4)、(s1) 対象とするm個の各特徴点p(i)(ここでiは各点に対応する0〜(m-1)の整数)について、所定方向の巡回順に並ぶc個(c＜m)の配置関係に基づくスコアS(i)をそれぞれ求める工程、(s2) スコアS(i)が最大の特徴点p(i)を開始点として前記巡回順のd個（d≦m）の点から特徴量の要素となる値を求め、開始点を巡回順にずらしていって各開始点からd個の点に基づいてそれぞれ要素を求め、開始点の巡回順に所定個数の要素を組み合わせた多次元ベクトルを特徴点pに係る特徴量として求める工程、(s3) 求めた特徴量から所定の計算手順でハッシュのインデックスを求める工程、(s4) 求めたインデックスでハッシュ表にアクセスし、(b)工程で求めた特徴量と特徴点pが抽出された文書および／または画像を識別する文書IDとをハッシュに登録する工程を実行することを特徴とし、前記検索は、入力された文書および／または画像から抽出された各特徴点pqについて、近傍n個の特徴点からm個を選択する各組み合わせについて実行する次の工程(r1)〜(r4)、(r1) 対象とするm個の各特徴点p(k)について、所定方向の巡回順に並ぶc個の配置関係に基づくスコアS(k)(ただしkは各点に対応する0〜(m-1)の整数)を求める工程、(r2) m個の特徴点のうちスコアS(k)が最大の点を開始点として前記巡回順のd個の点から特徴量の要素を求め、開始点を巡回順にずらしたd個からさらに異なる要素を求め、それらを開始点の巡回順に組み合わせた多次元ベクトルを点pqに係る特徴量として求める工程、(r3) 求めた特徴量から予め定められた計算手順でハッシュのインデックスを求め、そのインデックスでハッシュを参照する工程、(r4) 登録されたリストから得られる文書IDに対して投票する工程が実行されることにより、投票結果に基づいて検索結果が決定されるものである文書および／または画像のデータベースへの登録方法を提供する。さらにまた、この発明のより具体的な一態様として、
【００１２】
（３）入力された文書および／または画像の特徴を示す特徴点を抽出し、各特徴点から得られる特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、入力された文書および／または画像に対応するデータベース中の文書および／画像を検索する方法であって、前記データベースは、登録すべき文書および／または画像から抽出された各特徴点pについてその近傍n個の特徴点を選択し、それらn個の特徴点からm個（m≦n）をさらに選択する各組合せについて実行する次の工程(s1)〜(s4)、(s1) 対象とするm個の各特徴点p(i)(ここでiは各点に対応する0〜(m-1)の整数)について、所定方向の巡回順に並ぶc個(c＜m)の配置関係に基づくスコアS(i)をそれぞれ求める工程、(s2) スコアS(i)が最大の特徴点p(i)を開始点として前記巡回順のd個（d≦m）の点から特徴量の要素となる値を求め、開始点を巡回順にずらしていって各開始点からd個の点に基づいてそれぞれ要素を求め、開始点の巡回順に所定個数の要素を組み合わせた多次元ベクトルを特徴点pに係る特徴量として求める工程、(s3) 求めた特徴量から所定の計算手順でハッシュのインデックスを求める工程、(s4) 求めたインデックスでハッシュ表にアクセスし、(b)工程で求めた特徴量と特徴点pが抽出された文書および／または画像を識別する文書IDとをハッシュに登録する工程が実行されて文書および／または画像が登録されたものであり、コンピュータが、入力された文書および／または画像から抽出された各特徴点pqについて、近傍n個の特徴点からm個を選択する各組み合わせについて実行する次の工程(r1)〜(r4)、(r1) 対象とするm個の各特徴点p(k)について、所定方向の巡回順に並ぶc個の配置関係に基づくスコアS(k)(ただしkは各点に対応する0〜(m-1)の整数)を求める工程、(r2) m個の特徴点のうちスコアS(k)が最大の点を開始点として前記巡回順のd個の点から特徴量の要素を求め、開始点を巡回順にずらしたd個からさらに異なる要素を求め、それらを開始点の巡回順に組み合わせた多次元ベクトルを点pqに係る特徴量として求める工程、(r3) 求めた特徴量から予め定められた計算手順でハッシュのインデックスを求め、そのインデックスでハッシュを参照する工程、(r4) 登録されたリストから得られる文書IDに対して投票する工程を実行し、投票結果に基づいて検索結果を決定することを特徴とする文書および／または画像の検索方法を提供する。
【発明の効果】
【００１３】
この発明の（１）前記の検索方法は、近傍の特徴点との配置関係に基づいて算出されるスコアに基づいて特徴量を計算するための各不変量の組合せ順を決定するので、各不変量の組合せをすべて計算する場合に比べて組合せの数を減らすことができ、従って検索に要する処理時間を短縮することができる。
【００１４】
また、この発明の前記（２）の登録方法および前記（３）の検索方法は、工程(s2)が、スコアS(i)が最大の開始点に係る要素を先頭に開始点の巡回順に各要素を組み合わせた多次元ベクトルを用いて特徴量を計算し、それに対応して工程(r2)が、スコアS(k)が最大の開始点に係る要素を先頭に開始点の巡回順に各要素を組み合わせた多次元ベクトルを用いて特徴量を計算するので、登録時と検索時に同じ開始点を選ぶことができる。従って、すべての点を開始点とする組合せ（巡回置換）を試す場合に比べて、検索に要する処理時間を短縮することができる。
【００１５】
以下、この発明の好ましい態様について説明する。
前記（１）におて、各スコアは幾何学的変換に対する不変量であり、その算出手順は各特徴量の算出手順の一部と共通であってもよい。このようにすれば、幾何学的変換に対して安定したスコアを得ることができ、かつ、特徴量の算出と共にスコアを算出することができるので、特徴量とスコアを別に算出する場合に比べて処理時間を減らすことができる。
前記（２）および／または（３）において、前記スコアS(i)は、点p(i)を含む所定個数の特徴点から求められるアフィン不変量であり、前記スコアS(k)は、点p(k)を含む所定個数の特徴点から求められるアフィン不変量であってもよい。このようにすれば、幾何学的変換に対して安定したスコアを得ることができる。
【００１６】
また、前記（２）および／または（３）において、前記スコアS(i)の算出手順は、点pに係る特徴量の算出手順の一部と共通し、前記スコアS(k)の算出手順は、点pqに係る特徴量の算出手順の一部と共通してもよい。このようにすれば、各点について特徴量の算出と共にスコアを算出することができるので、特徴量と別にスコアを算出する場合に比べてスコアの算出に要する処理時間を減らすことができる。
【００１７】
さらにまた、前記（２）において、前記工程(d)は、ハッシュへの登録対象のうちインデックスの等しい登録対象が複数個ある場合それらをいずれもハッシュに登録せず、インデックスの異なる登録対象だけをハッシュに登録する工程でであってもよい。このようにすれば、同一インデックスについて複数の対象を登録する（ハッシュの衝突を許す）場合に比べてハッシュ表が単純になり、ハッシュ表の格納に必要なメモリ量を削減することができる。
ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
【００１９】
≪LLAHと、それを用いた検索処理≫
この発明の実施形態を説明する前に、オリジナルのLLAHと、それを用いた検索処理についてまず説明する。この発明の本質を理解するためには、その改良の基礎となる技術の理解が不可欠だからである。
【００２０】
1.処理の概要
図1に従来のLLAHを用いた検索処理の概要を示す。まず、特徴点抽出処理部15（Feature Point Extraction）で文書画像11および13は特徴点の集合に変換される。次に、各特徴点は登録処理部17（Storage）および検索処理部19（Retrieval）に入力される。これらの処理は特徴量計算処理部21（Calculation of Features）を共有している。登録処理部17は、各特徴点を独立に、その特徴量に基づいて文書画像データベース（Document Image Database）15に登録する。つまり、文書画像11は特徴点を用いてインデキシングされる。検索処理部19は、検索質問13の各特徴量を用いて文書画像データベース23にアクセスし、投票処理によって対応する文書画像を決定する。以下では各処理部が実行する処理について説明する。
【００２１】
2.特徴点抽出処理
特徴点抽出処理部15が実行する処理である。LLAHでは特徴点の配置に基づいて文書画像のマッチングを行う。従って、特徴点抽出処理では、射影歪みやノイズが生じていた場合や低解像度の場合でも同一の点を抽出する必要がある。そのため、単語領域の重心を特徴点として用いる。
【００２２】
図2は、従来の特徴点抽出の手順を示す説明図である。図2に示すように、特徴点抽出処理部は、まず、入力画像（図2(a)）を適応2値化し、2値画像（図2(b)）を得る。次に、2値画像をガウシアンフィルタでぼかし、再度適応2値化を行うと、単語ごとに連結された画像（図2(c)）が得られる。最後に連結成分の重心を計算して特徴点（図2(d)）とする。
【００２３】
3.特徴量計算
特徴量計算処理部21が実行する処理である。特徴量とは、文書画像の特徴点を表現する値である。特徴点のマッチングは特徴量に基づいて行われる。そのため、特徴量は以下の2つの条件を満たす必要がある。1つは、同一の特徴点は、さまざまな外乱が生じて画像の見え方が変わったとしても、同一の特徴量を与えなければならないというものである。同一の特徴点であるにもかかわらず、登録処理と検索処理で異なる特徴量が得られた場合、それらの対応付けを行うことはできない。そのため、正しい検索結果を得ることができなくなる。この明細書において、この条件を"特徴量の安定性"と呼ぶ。もう1つの条件は、異なる特徴点は異なる特徴量を与えなければならないというものである。異なる特徴点から同一の特徴量が得られた場合、誤った特徴点と対応付けられてしまう。そのため、正しいものだけでなく誤ったものも検索結果として得られることになる。この明細書において、この条件を"特徴量の識別性"と呼ぶ。正確な検索のためには、安定性と識別性を両立した特徴量が必要である。
【００２４】
3-1.安定性
カメラで文書を撮影する場合、隠れが生じていたり、紙面の一部だけが撮影される場合がある。従って安定性の実現のためには、特徴量は文書画像の部分から計算されるものが望ましい。LLAHでは、各特徴点についてその近傍の特徴点の配置から特徴量を計算する。特徴量が文書画像の局所領域から得られるため、同じ領域が撮影されていれば同じ特徴量を計算することができる。
【００２５】
カメラを用いる場合、画像が射影歪みを受けることがある。そこで、射影歪みが生じても安定な特徴量を計算するために、幾何学的不変量を用いる。カメラで斜め方向から撮影するときに生じる歪みは射影変換であるため、射影変換の不変量である複比を用いることが考えられる。しかし、非特許文献2の結果より、射影変換より自由度の低い変換であるアフィン変換の不変量を用いる方が検索において高い精度をもたらすことが確認されている。これは、局所領域においては射影変換はアフィン変換に近似可能であることと、アフィン不変量の方が特徴点の位置の変動に強く安定であることが原因である。
この実施形態では、同一平面上の4点ABCDから以下の式で計算されるアフィン不変量を用いる。
【００２６】
【数１】
【００２７】
ここで、P(A,B,C)は頂点A，B，Cをもつ三角形の面積である。
近傍点の配置から特徴点pの特徴量を計算する場合、最も単純なものはpの近傍4点から計算されるアフィン不変量を特徴量とするものである。しかし、射影歪みが生じた場合は近傍点に異なるものが得られることがある。図3は、従来のLLAHにおいて、同じ文書を異なる視点から見たときの特徴点と近傍8点の配置を示す説明図である。図3(a)および(b)の2枚の画像は、特徴点pとその近傍の8つの特徴点を異なる視点から見たときの例を示している。図中、丸で囲まれた数字は点pからの距離の順位である。黒抜きの数字（図3(a)の「3」と図3(b)の「8」）は異なる点が得られている例を示す。
【００２８】
従って、近傍4点から計算されるアフィン不変量は安定ではない。この問題を解決するため、より広い範囲の局所領域を用いる。図3では、近傍7点のうち6点までは共通のものが得られている。このことから、近傍n点のうちm(≦n)点まではある程度の射影歪みが生じていても共通のものを得ることができると考えられる。以上のことから、m点を用いて安定な特徴量を計算する。
【００２９】
図4は、従来のLLAHにおいて、近傍n(=7)点からすべてのm(=6)点の組み合わせを選択する組合せを示す説明図である。図4に示されるように、LLAHにおいてはn点からのすべてのm点の組み合わせ
【００３０】
【数２】
を調べる。n点のうちm点が共通であれば、同じm点を得ることができる。LLAHではこのようにして特徴量の安定性を実現している。
【００３１】
3-2.識別性
m点から特徴量を計算する場合、最も単純な方法はm=4として4点から計算されるアフィン不変量を特徴量とするというものである。しかし、異なる文書から得た特徴点でも、類似した4点の配置をもつ場合があるため、このような単純な方法は識別性に問題がある。そこで、識別性を向上させるため、m(＞4)の値を大きくしてより多くの点から特徴量を計算する。mが大きくなると、異なる文書画像から類似したm点の配置をもつ確率が低くなる。図5は、従来のLLAHにおいて、m(=6)点からのすべての4点の組み合わせと、それら4点から計算されるアフィン不変量の列を示す説明図である。図5に示されるように、m点の配置は、m点から4点をそれぞれ選び、そこから計算されるアフィン不変量を離散化した値の列
【００３２】
【数３】
で表現される。m点から4点を選ぶ手法の詳細は次のとおりである。まず、m点から適当に1つの点p0を選ぶ。そして、m点を特徴点pを中心としかつp0を先頭にして時計回りに並べた特徴点の列Lm=(p0,…pm-1)を作る。このとき、Lm中の連続する4点（循環を含む）を選んでできる各部分列がm点から4点を選ぶ各組合せである。
【００３３】
4.登録
登録処理のアルゴリズムの一例を図6に示す。ここで、文書IDとは文書の識別番号、点IDとは特徴点の識別番号である。
ハッシュ表（ハッシュテーブル）のインデックスは以下に示すハッシュ関数で計算される。
【００３４】
【数４】
ここで、r(i)はアフィン不変量の離散値、kは離散化レベル数、Hsizeはハッシュ表のサイズである。
【００３５】
図７は、従来のLLAHにおいて、ハッシュ表の構造の一例を示す説明図である。図7に示されるように、文書ID、点ID、
【００３６】
【数５】
の組が多次元の特徴量（特徴ベクトル）としてハッシュ表に登録される。衝突が生じた場合は、リスト形式で追加される。
【００３７】
5.検索
検索処理のアルゴリズムの一例を図8に示す。LLAHでは、投票テーブルを用いた登録文書への投票を通じて検索を行う。
まず、7-10行目で登録処理と同様にハッシュ表のインデックスを求める。得られたインデックスを用いて、11行目で図7に示されるリストを得る。リストの各項目について
【００３８】
【数６】
【００３９】
が一致するか調べ、一致していたら投票テーブルの文書IDの項目をインクリメントする。最後に、最大の得票数を得た文書を検索結果として出力する。
以上が、オリジナルのLLAHとそれを用いた検索処理についての説明である。次に、性能向上の第1の側面であるメモリ量の削減について説明する。
【００４０】
≪必要メモリ量の削減≫
LLAHでは、安定性の実現のために多くの特徴量を計算し、それらすべてをリスト形式でハッシュ表へ保存する。そのため、必要メモリ量が多くなる。そこで、重要性の低い特徴量をデータベースから削除し、データ構造を改めることで記憶容量の削減を図る。
【００４１】
必要メモリ量の削減手法は、基本的に次のようなアイデアに基づく。ハッシュテーブルに登録する特徴ベクトルのうち、多数の衝突を起こしているものについては、識別にそれほど有効ではないため、削除してもよい。記録する特徴ベクトルが少なくなれば、それだけメモリ量を削減できる。
【００４２】
ただし、これだけでは、既存のもの（たとえば非特許文献5に記載の方法）との差異がない。この発明の特徴は、衝突を起こしている特徴ベクトルを「すべて」削除する点にある。すべて削除することによって、識別性や安定性が損なわれることが考えられたが、後述する実験の結果、以外にもこれは問題とはならなかった。図９は、この発明において、衝突を起こしている特徴ベクトルをすべて削除した状態のハッシュ表の一例を示す説明図である。図９に示すようにデータ構造をきわめて単純な形にすることが可能となり、必要メモリの量を大幅に削減できる。
【００４３】
以下に具体例におけるメモリ消費量を示す。
n=7, m=6, Hsize=1.28×108
登録ページ数10,000
文書画像1枚あたりの平均特徴点数630
文書ID、点ID、r(i)はそれぞれ2バイト、2バイト、1バイトの変数に保存される
ポインタ変数のサイズは8バイト
このような条件では、図7左側のハッシュ表は1.28×108×8=1.0GB、図7右側のリストは10,000×630×7×(2＋2＋1×15＋8)=1.2GBを消費する。従って、必要メモリ量の合計は2.2GBとなる。
【００４４】
メモリの削減のためには、重要性の低いデータを削除することが望ましい。重要性の低いデータとして、リストにおいて衝突を起こしているものが挙げられる。これは、衝突を起こしているものは識別性に欠ける可能性があり、また頻繁に生じる特徴量であるため、検索処理において速度の低下を引き起こすからである。また、実験では衝突を起こしているものはハッシュ表でデータの登録されているもののうち28%程度であり、削除しても影響は限られると考えられる。以上の理由から、ハッシュ表において衝突の生じているリストを削除する。これにより、メモリ容量の削減が期待できる。同時に、処理時間の短縮（高速化）も期待できる。
【００４５】
衝突のあったリストを削除すると、データ構造の変更によるさらなる容量の削減が可能になる。リストにおける特徴ベクトルは、衝突している場合に適切なものを見つけるためにあった。そのため、衝突がないのならば特徴ベクトルを保存する必要がなくなる。また、衝突がないのならそもそもリスト形式にする必要もない。そこで、図9に示すような単純なハッシュ表にすることで、記憶容量を削減する。単純なハッシュ表では、前に挙げた例の条件（Hsize=1.28×108）、文書IDと点IDの変数サイズ2バイト）の場合は必要メモリ量は512MBとなり、77%のメモリ消費量が削減される。
【００４６】
図16は、前述のメモリ消費量削減の工夫がなされた登録処理（メモリ削減版）のアルゴリズムの一例を示す図である。図6（従来の登録処理）と図16のアルゴリズムとを比較するとstep10以降が異なる。特に、step10〜14が、従来のアルゴリズムに追加された部分である。前記部分の追加によって、図16のアルゴリズムは、図9に示すように衝突を起こしたものが除外されたハッシュ表を用いることになる。即ち、あるインデックス(Hindex)に対してハッシュ表にデータを登録する際、既にデータが登録されているか否かを調べる（step11）。未だデータが登録されていなければ、従来と同様にそのデータを登録するが(step12)、既にデータが登録されていた場合は(step13)、衝突を意味する。そこで、そのデータには衝突の印を付けて登録する（step14）。検索時には、衝突の印が付いたものを使用しない。
【００４７】
図18は、図16の登録処理に対応する検索処理のアルゴリズムの一例を示す図である。図6（従来の登録処理）と図16のアルゴリズムとを比較するとstep11以降が異なる。図6の従来手法のstep11〜13は、衝突が生じた場合に対処するためのステップである。図16（メモリ削減版）のアルゴリズムには、その部分が存在しない。それに代えて、登録時に衝突の印が付されたデータか否かをチェックするためのステップ(step11)が設けられている。
【００４８】
メモリを圧縮するもう一つの方法は、ハッシュのサイズHsizeを小さくすることである。しかし、ハッシュサイズは検索性能に大きく影響する。特に、衝突した項目を削除する場合は、ハッシュサイズを小さくすると衝突が多発し、多くの登録データが失われて検索精度が大きく低下する可能性がある。従って、ハッシュ表の占有率は低く保ち、必要に応じてハッシュサイズを大きくする必要がある。
【００４９】
≪検索処理の高速化≫
次に、検索処理の高速化のための登録および検索アルゴリズムの改良について述べる。
検索処理の高速化は、次のようなアイデアである。従来法ではどの点から不変量を計算するのかという、「開始点」が一意に定まらなかったため、開始点を一つずつずらしながら、すべての可能性を試していた。一方、提案の手法では、点の配置から、どの点が開始点となるべきかを求めることで、計算量を削減している。
【００５０】
基本的な方法は次のとおりである。点の配置から各点のスコアを求め、そのスコアが最大のものを開始点とする。ただし、いくつか注意すべきポイントがある。
【００５１】
1.開始点を求めるための計算量が十分小さいこと。
これが大きいと、開始点をずらしながらすべての可能性を試すほうが、高速である、ということになりかねない。
2.開始点を求めるためのメモリ量が十分小さいこと。
これが大きいと、やはり問題を招く。
3.開始点は、幾何学的変換に不変に求められること。
撮影角度によって、求められる開始点は変化しないことが必要である。
4.同一の特徴ベクトルが得られる点の配置からは、同一の開始点が得られること。
【００５２】
この条件は、少々わかりにくい。まず、この発明では、特徴ベクトルが安定して得られるように種々の工夫をこらしている。たとえば、アフィン不変量を用いて特徴ベクトルを計算することも、その工夫のひとつである。しかしながら、画像によっては、ノイズや撮影角度、照明など、種々の条件が悪化することによって、同じ特徴ベクトルが得られず、異なる特徴ベクトルとなってしまうことがある。異なる特徴ベクトルが得られた場合、もはや元の特徴ベクトルとの対応を取ることができないため、検索には役に立たない。逆にいえば、同じ特徴ベクトルが得られるものについては、検索に役立てることができる。さらにいえば、これらを漏れなく検索に役立てる必要がでてくる。
【００５３】
ここで、開始点を求めるための不変量の計算と、特徴ベクトルを求めるための不変量の計算が、全く異なる場合を考えてみよう。異なる方法で求められた不変量は、変動の傾向も異なるため、同じ特徴ベクトルが得られる場合であっても、開始点が異なってしまうことが考えられる。そのようなケースが生じると、折角、同じ特徴ベクトルが得られているにもかかわらず、開始点が異なるために、検索に役立てることができない。
【００５４】
逆に、開始点を求めるための不変量の計算と、特徴ベクトルを求めるための不変量の計算が同じ傾向をもっており、同じ特徴ベクトルが得られる場合には、必ず同じ開始点を得ることができれば、好都合である。
【００５５】
このような条件を満たすことは困難であると思われるかもしれないが、実は、特徴ベクトルの計算に用いる不変量の一部を、開始点の計算に用いることによって、実現できる。特徴ベクトルが同じであるためには、特徴ベクトルを構成する不変量がすべて同じ値に量子化される必要がある。したがって、その一部を用いて開始点を計算すれば、特徴ベクトルが同じである場合には、必ず開始点も同じであるといえる。
【００５６】
この発明で提案している方式は、上記の４点を満たすものといえる。
なお、特徴ベクトルに用いる不変量が、現在のアフィン不変量ではなく、相似不変量や射影不変量になっても、同じアイデアを用いることが可能である。
【００５７】
図8に示されるオリジナルのLLAHに係る検索アルゴリズムでは、4-5行目でLmのすべての巡回置換を試すために、Pmのすべての点が開始点p0となるように繰り返し処理を行う。これは、カメラで画像を撮影する際に回転が生じるため、検索時のLmと登録時のLmが必ずしも一致しないためである。
しかし、登録時と検索時に同じ開始点p0を選ぶことができれば、巡回置換を試す必要はない。以下の実施形態では、開始点の選択規則を導入し、検索処理の効率化を図る。
【００５８】
図10は、この発明に係る開始点の選択規則を示す説明図である。特徴点pに属するm点の各点iについて、後続の3点と合わせてアフィン不変量s(i)を計算する。
【００５９】
【数７】
の中で最大のものがs(j)であれば、点jを開始点として選択する。図10の例では、s(1)が最大であるため点1が開始点となる。最大値を取るものが複数あった場合、次の
【００６０】
【数８】
の最大値を調べて開始点を定める。例えば、s(i)=s(j)がともに最大値であれば、
【００６１】
【数９】
を比較する。
【００６２】
【数１０】
の方が大きければ、点i が開始点として選ばれる。ここで
【００６３】
【数１１】
であれば、さらに次の値
【００６４】
【数１２】
を比較し、開始点を選択する。
【００６５】
図17は、メモリ削減版に加えて、前述の高速化の工夫がなされた登録処理（メモリ削減+高速化版）のアルゴリズムの一例を示す図である。図6（従来の登録処理）あるいは図16と図17のアルゴリズムとを比較すると、step4において、開始点を決めている点が異なる。従来手法およびメモリ削減版では，たまたま最初になった点が開始点となるが、高速化版ではどの開始点にするかを図10の選択規則により計算して決めている。
【００６６】
図19は、図17の登録処理に対応する検索処理のアルゴリズムの一例を示す図である。図6（従来の登録処理）あるは図16と図19のアルゴリズムでは、開始点が一意に定まらないため、開始点を巡回させながらすべてを試す処理を行っている。これが、図6および図16のstep4の処理である。これに対して、図20（メモリ削減+高速化版）のアルゴリズムでは、step4で開始点を選択規則に基づいて計算することによって、m個の各点p0について試すforループを削除している。
【００６７】
なお、この実施形態ではメモリ削減版と、メモリ削減版+高速化版を説明し、高速化版のみの例を省略しているが、高速化版単独の実施形態は両者の差異点を抽出することで当業者に容易に理解されるものである。この明細書の開示の範囲には、高速化版単独の態様も含まれていると解されるべきである。
【００６８】
≪実験例≫
この発明に係る手法の効果を調べるため、元のLLAHと改善されたLLAHで検索実験を行い、性能を比較した。前述の「必要メモリ量の削減」と前述の「検索処理の高速化」の効果を明確にするため、以下の3つのバージョンのLLAHでメモリ消費量、処理時間、精度を調べた。
(1) オリジナル
(2) メモリ削減版
(3) メモリ削減＋高速化版
(2)および(3)がこの発明に係る手法である。
【００６９】
データベースに登録された文書画像は、主に予稿集のCD-ROMから集められた、1段組および2段組の英語論文のPDFファイルを200dpiで画像に変換したものである。図11は、この発明に係る実験例に用いられたデータベースに登録された文書画像の一例を示す図である。検索質問の文書画像は630万画素のデジタルカメラで撮影されたものである。図12は、この発明に係る実験例に用いられた検索質問画像の一例を示す図である。図12に示されるように、検索質問は紙面に対して斜め方向（約45度）から撮影されたものである。検索質問の撮影角度（45度）と登録画像の撮影角度（90度）は異なるため、これらを用いた実験によって、手法の射影歪みに対するロバスト性が示すことができる。なお、検索質問画像の受ける射影歪みは非特許文献2のものより強いものである。実験に用いた計算機は、AMDOpteron2.8GHzのCPUと16GBのメモリをもつものである。パラメータはn=7、m=6、k=15、Hsize=1.28×108とした(異なるnとmの場合の実験結果については非特許文献2を参照のこと)。
【００７０】
1.必要メモリ量
図13は、この発明に係る実験例において登録ページ数を100，1,000，10,000と増加させたときの3つのバージョンのLLAHにおけるメモリ消費量の比較実験結果を示すグラフである。オリジナルのLLAHは、登録ページ数10,000では本発明に係るメモリの削減版に比べて5倍のメモリを消費した。さらに、登録ページ数の増加に伴ってメモリの消費量も増加した。これは、オリジナルのLLAHではデータベースでリストを用いており、登録ページ数が増加するとメモリ消費量も増加するためである。一方、本発明に係るメモリ削減の改善がなされたLLAHでは、登録ページ数が増加してもメモリ消費量は一定であった。これは、データベースが単純なハッシュ表であり、ハッシュ表のサイズが固定されているためである。
【００７１】
2.処理時間
図14は、処理時間について各バージョンの比較実験結果を示すグラフである。このように、本発明に係る高速化バージョンはそれ以外に比べておよそ60%の処理時間の削減を実現した。これは、巡回置換を試すための繰り返し処理を避けることで不変量の計算回数やハッシュへのアクセス回数を減らすことができたためと考えられる。
【００７２】
また、本発明に係るメモリ削減版はオリジナルに比べて登録ページ数の増加に対する速度の低下が見られなかった。これは、オリジナルではリスト構造のためデータ量が増えるとリストをたどる処理時間が増加する一方、単純なハッシュ表であるメモリ削減版は常に一定の処理時間しか要しないためと考えられる。
【００７３】
3.精度
図15は、それぞれのバージョンの各データベースサイズにおける精度についての比較実験結果を示すグラフである。処理時間とメモリ効率に加えて、精度に関しても本発明に係るメモリ削減版および高速化版はオリジナルより高い性能を示した。オリジナルが登録ページ数の増加に伴って精度を低下させた一方で、メモリ削減版および高速化版は登録ページ数10,000では精度がやや低下したものの、オリジナルよりも高い精度を維持した。
【００７４】
この実施形態に係る改善手法が精度の向上を意図したものではないにも関わらず、精度の向上をもたらした理由は、メモリの削減のために識別性の低い特徴量を削除した結果、誤投票を減らすことができたことと考えられる。メモリ削減版および高速化版では衝突を生じた項目は削除される。そのような項目は誤った投票を生じやすいため、それらを削除することで精度の向上が実現されたと考えられる。
【００７５】
以上の実験例で示されるように、10,000ページのデータベースを用いた実験では、元のLLAHに対して必要メモリ量は1/5、処理時間は2/5となることが確認された。また実験では、改善されたLLAHは高いスケーラビリティをもつことも示された。データベースの登録画像数が10,000までは、メモリ消費量と処理時間がほぼ一定であった。
【００７６】
この発明では、LLAHの改良手法を提案した。不必要な特徴量の削除とデータ構造の単純化により、必要メモリ量の削減を実現した。また、検索アルゴリズムを改良することで処理時間を削減することができた。実験により、必要メモリ量の80%、処理時間の60%が削減されたことを確認した。実験ではさらに、改良手法では精度についても向上することが確認された。以上のことから、LLAHのスケーラビリティや、リアルタイム処理などの高速性を要求するアプリケーションへの拡張性が向上したといえる。
【００７７】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【図面の簡単な説明】
【００７８】
【図１】従来のLLAHを用いた検索処理の概要を示すブロック図である。
【図２】従来の特徴点抽出の手順を示す説明図である。
【図３】従来のLLAHにおいて、同じ文書を異なる視点から見たときの特徴点と近傍8点の配置を示す説明図である。
【図４】従来のLLAHにおいて、近傍n(=7)点からすべてのm(=6)点の組み合わせを選択する組合せを示す説明図である。
【図５】従来のLLAHにおいて、m(=6)点からのすべての4点の組み合わせと、それら4点から計算されるアフィン不変量の列を示す説明図である。
【図６】従来のLLAHの登録処理のアルゴリズムの一例を示す説明図である。
【図７】従来のLLAHにおいて、ハッシュ表の構造の一例を示す説明図である。
【図８】従来のLLAHの検索処理のアルゴリズムの一例を示す説明図である。
【図９】この発明において、衝突を起こしている特徴ベクトルをすべて削除した状態のハッシュ表の一例を示す説明図である。
【図１０】この発明に係る開始点の選択規則を示す説明図である。
【図１１】この発明に係る実験例に用いられたデータベースに登録された文書画像の一例を示す図である。
【図１２】この発明に係る実験例に用いられた検索質問画像の一例を示す図である。
【図１３】この発明に係る実験例において、登録ページ数を100，1,000，10,000と増加させたときの3つのバージョンのLLAHにおけるメモリ消費量の比較実験結果を示すグラフである。
【図１４】この発明に係る実験例において、処理時間について各バージョンの比較実験結果を示すグラフである。
【図１５】この発明に係る実験例において、それぞれのバージョンの各データベースサイズにおける精度についての比較実験結果を示すグラフである。
【図１６】この実施形態において、メモリ消費量削減の工夫がなされた登録処理（メモリ削減版）のアルゴリズムの一例を示す図である。
【図１７】この実施形態において、メモリ削減版に加えて、前述の高速化の工夫がなされた登録処理（メモリ削減+高速化版）のアルゴリズムの一例を示す図である。
【図１８】この実施形態において、図16の登録処理に対応する検索処理のアルゴリズムの一例を示す図である。
【図１９】この実施形態において、図17の登録処理に対応する検索処理のアルゴリズムの一例を示す図である。
【符号の説明】
【００７９】
１１：登録画像（文書画像）
１３：検索質問（文書画像）
１５：特徴点抽出処理部
１７：登録処理部
１９：検索処理部
２１：特徴量計算処理部
２３：文書画像データベース
【特許請求の範囲】
【請求項１】
取得された画像の特徴点に基づいて計算される特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、取得された画像に対応する文書および／または画像をデータベースから検索する方法であって、
取得された画像から抽出された各特徴点に対して局所的な特徴点の集合を決定する工程と、
決定された各集合から特徴点の部分集合を選択する工程と、
選択された各部分集合を特徴付ける量として、部分集合中の特徴点の複数の組合せについて幾何学的変換に対する不変量をそれぞれ求めると共に各特徴点の配置に基づくスコアを求める不変量算出工程と、
求めた各不変量を組み合わせて特徴量を計算する特徴量算出工程と、
前記特徴量と予めその特徴量が得られた前記データベース中の文書および／または画像に係る特徴量との一致度を調べ、取得された画像の各特徴点に係る前記一致度を統計的に処理することにより、取得された画像に対応するデータベース中の文書および／または画像を検索する工程
の各工程をコンピュータが実行し、
前記不変量算出工程は、部分集合中の各特徴点について近傍の特徴点との配置関係に基づいてそれぞれのスコアを算出し、
前記特徴量算出工程は、前記スコアに基づいて特徴量を計算するための各不変量の組合せ順を決定することを特徴とする文書および／または画像の検索方法。
【請求項２】
各スコアは幾何学的変換に対する不変量であり、その算出手順は各特徴量の算出手順の一部と共通である請求項１に記載の方法。
【請求項３】
入力された文書および／または画像の特徴を示す特徴点を抽出し、各特徴点から得られる特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、入力された文書および／または画像に対応するデータベース中の文書および／画像を検索する処理に係る前記データベースへ文書および／または画像を登録する方法であって、
コンピュータが、
登録すべき文書および／または画像から複数の特徴点を抽出し、
抽出された各特徴点pについてその近傍n個の特徴点を選択し、それらn個の特徴点からm個（m≦n）をさらに選択する各組合せについて実行する次の工程(s1)〜(s4)、
(s1) 対象とするm個の各特徴点p(i)(ここでiは各点に対応する0〜(m-1)の整数)について、所定方向の巡回順に並ぶc個(c＜m)の配置関係に基づくスコアS(i)をそれぞれ求める工程、
(s2) スコアS(i)が最大の特徴点p(i)を開始点として前記巡回順のd個（d≦m）の点から特徴量の要素となる値を求め、開始点を巡回順にずらしていって各開始点からd個の点に基づいてそれぞれ要素を求め、開始点の巡回順に所定個数の要素を組み合わせた多次元ベクトルを特徴点pに係る特徴量として求める工程、
(s3) 求めた特徴量から所定の計算手順でハッシュのインデックスを求める工程、
(s4) 求めたインデックスでハッシュ表にアクセスし、(b)工程で求めた特徴量と特徴点pが抽出された文書および／または画像を識別する文書IDとをハッシュに登録する工程
を実行することを特徴とし、
前記検索は、入力された文書および／または画像から抽出された各特徴点pqについて、近傍n個の特徴点からm個を選択する各組み合わせについて実行する次の工程(r1)〜(r4)、
(r1) 対象とするm個の各特徴点p(k)について、所定方向の巡回順に並ぶc個の配置関係に基づくスコアS(k)(ただしkは各点に対応する0〜(m-1)の整数)を求める工程、
(r2) m個の特徴点のうちスコアS(k)が最大の点を開始点として前記巡回順のd個の点から特徴量の要素を求め、開始点を巡回順にずらしたd個からさらに異なる要素を求め、それらを開始点の巡回順に組み合わせた多次元ベクトルを点pqに係る特徴量として求める工程、
(r3) 求めた特徴量から予め定められた計算手順でハッシュのインデックスを求め、そのインデックスでハッシュを参照する工程、
(r4) 登録されたリストから得られる文書IDに対して投票する工程
が実行されることにより、投票結果に基づいて検索結果が決定されるものである文書および／または画像のデータベースへの登録方法。
【請求項４】
前記スコアS(i)は、点p(i)を含む所定個数の特徴点から求められるアフィン不変量であり、
前記スコアS(k)は、点p(k)を含む所定個数の特徴点から求められるアフィン不変量である請求項３に記載の方法。
【請求項５】
前記スコアS(i)の算出手順は、点pに係る特徴量の算出手順の一部と共通し、
前記スコアS(k)の算出手順は、点pqに係る特徴量の算出手順の一部と共通する請求項３または４に記載の方法。
【請求項６】
前記工程(d)は、ハッシュへの登録対象のうちインデックスの等しい登録対象が複数個ある場合それらをいずれもハッシュに登録せず、インデックスの異なる登録対象だけをハッシュに登録する工程である請求項３〜５の何れか一つに記載の方法。
【請求項７】
入力された文書および／または画像の特徴を示す特徴点を抽出し、各特徴点から得られる特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、入力された文書および／または画像に対応するデータベース中の文書および／画像を検索する方法であって、
前記データベースは、登録すべき文書および／または画像から抽出された各特徴点pについてその近傍n個の特徴点を選択し、それらn個の特徴点からm個（m≦n）をさらに選択する各組合せについて実行する次の工程(s1)〜(s4)、
(s1) 対象とするm個の各特徴点p(i)(ここでiは各点に対応する0〜(m-1)の整数)について、所定方向の巡回順に並ぶc個(c＜m)の配置関係に基づくスコアS(i)をそれぞれ求める工程、
(s2) スコアS(i)が最大の特徴点p(i)を開始点として前記巡回順のd個（d≦m）の点から特徴量の要素となる値を求め、開始点を巡回順にずらしていって各開始点からd個の点に基づいてそれぞれ要素を求め、開始点の巡回順に所定個数の要素を組み合わせた多次元ベクトルを特徴点pに係る特徴量として求める工程、
(s3) 求めた特徴量から所定の計算手順でハッシュのインデックスを求める工程、
(s4) 求めたインデックスでハッシュ表にアクセスし、(b)工程で求めた特徴量と特徴点pが抽出された文書および／または画像を識別する文書IDとをハッシュに登録する工程
が実行されて文書および／または画像が登録されたものであり、
コンピュータが、
入力された文書および／または画像から抽出された各特徴点pqについて、近傍n個の特徴点からm個を選択する各組み合わせについて実行する次の工程(r1)〜(r4)、
(r1) 対象とするm個の各特徴点p(k)について、所定方向の巡回順に並ぶc個の配置関係に基づくスコアS(k)(ただしkは各点に対応する0〜(m-1)の整数)を求める工程、
(r2) m個の特徴点のうちスコアS(k)が最大の点を開始点として前記巡回順のd個の点から特徴量の要素を求め、開始点を巡回順にずらしたd個からさらに異なる要素を求め、それらを開始点の巡回順に組み合わせた多次元ベクトルを点pqに係る特徴量として求める工程、
(r3) 求めた特徴量から予め定められた計算手順でハッシュのインデックスを求め、そのインデックスでハッシュを参照する工程、
(r4) 登録されたリストから得られる文書IDに対して投票する工程
を実行し、
投票結果に基づいて検索結果を決定することを特徴とする文書および／または画像の検索方法。
【請求項８】
前記スコアS(i)は、点p(i)を含む所定個数の特徴点から求められるアフィン不変量であり、
前記スコアS(k)は、点p(k)を含む所定個数の特徴点から求められるアフィン不変量である請求項７に記載の方法。
【請求項９】
前記スコアS(i)の算出手順は、点pに係る特徴量の算出手順の一部と共通し、
前記スコアS(k)の算出手順は、点pqに係る特徴量の算出手順の一部と共通する請求項７または８に記載の方法。
【請求項１】
取得された画像の特徴点に基づいて計算される特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、取得された画像に対応する文書および／または画像をデータベースから検索する方法であって、
取得された画像から抽出された各特徴点に対して局所的な特徴点の集合を決定する工程と、
決定された各集合から特徴点の部分集合を選択する工程と、
選択された各部分集合を特徴付ける量として、部分集合中の特徴点の複数の組合せについて幾何学的変換に対する不変量をそれぞれ求めると共に各特徴点の配置に基づくスコアを求める不変量算出工程と、
求めた各不変量を組み合わせて特徴量を計算する特徴量算出工程と、
前記特徴量と予めその特徴量が得られた前記データベース中の文書および／または画像に係る特徴量との一致度を調べ、取得された画像の各特徴点に係る前記一致度を統計的に処理することにより、取得された画像に対応するデータベース中の文書および／または画像を検索する工程
の各工程をコンピュータが実行し、
前記不変量算出工程は、部分集合中の各特徴点について近傍の特徴点との配置関係に基づいてそれぞれのスコアを算出し、
前記特徴量算出工程は、前記スコアに基づいて特徴量を計算するための各不変量の組合せ順を決定することを特徴とする文書および／または画像の検索方法。
【請求項２】
各スコアは幾何学的変換に対する不変量であり、その算出手順は各特徴量の算出手順の一部と共通である請求項１に記載の方法。
【請求項３】
入力された文書および／または画像の特徴を示す特徴点を抽出し、各特徴点から得られる特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、入力された文書および／または画像に対応するデータベース中の文書および／画像を検索する処理に係る前記データベースへ文書および／または画像を登録する方法であって、
コンピュータが、
登録すべき文書および／または画像から複数の特徴点を抽出し、
抽出された各特徴点pについてその近傍n個の特徴点を選択し、それらn個の特徴点からm個（m≦n）をさらに選択する各組合せについて実行する次の工程(s1)〜(s4)、
(s1) 対象とするm個の各特徴点p(i)(ここでiは各点に対応する0〜(m-1)の整数)について、所定方向の巡回順に並ぶc個(c＜m)の配置関係に基づくスコアS(i)をそれぞれ求める工程、
(s2) スコアS(i)が最大の特徴点p(i)を開始点として前記巡回順のd個（d≦m）の点から特徴量の要素となる値を求め、開始点を巡回順にずらしていって各開始点からd個の点に基づいてそれぞれ要素を求め、開始点の巡回順に所定個数の要素を組み合わせた多次元ベクトルを特徴点pに係る特徴量として求める工程、
(s3) 求めた特徴量から所定の計算手順でハッシュのインデックスを求める工程、
(s4) 求めたインデックスでハッシュ表にアクセスし、(b)工程で求めた特徴量と特徴点pが抽出された文書および／または画像を識別する文書IDとをハッシュに登録する工程
を実行することを特徴とし、
前記検索は、入力された文書および／または画像から抽出された各特徴点pqについて、近傍n個の特徴点からm個を選択する各組み合わせについて実行する次の工程(r1)〜(r4)、
(r1) 対象とするm個の各特徴点p(k)について、所定方向の巡回順に並ぶc個の配置関係に基づくスコアS(k)(ただしkは各点に対応する0〜(m-1)の整数)を求める工程、
(r2) m個の特徴点のうちスコアS(k)が最大の点を開始点として前記巡回順のd個の点から特徴量の要素を求め、開始点を巡回順にずらしたd個からさらに異なる要素を求め、それらを開始点の巡回順に組み合わせた多次元ベクトルを点pqに係る特徴量として求める工程、
(r3) 求めた特徴量から予め定められた計算手順でハッシュのインデックスを求め、そのインデックスでハッシュを参照する工程、
(r4) 登録されたリストから得られる文書IDに対して投票する工程
が実行されることにより、投票結果に基づいて検索結果が決定されるものである文書および／または画像のデータベースへの登録方法。
【請求項４】
前記スコアS(i)は、点p(i)を含む所定個数の特徴点から求められるアフィン不変量であり、
前記スコアS(k)は、点p(k)を含む所定個数の特徴点から求められるアフィン不変量である請求項３に記載の方法。
【請求項５】
前記スコアS(i)の算出手順は、点pに係る特徴量の算出手順の一部と共通し、
前記スコアS(k)の算出手順は、点pqに係る特徴量の算出手順の一部と共通する請求項３または４に記載の方法。
【請求項６】
前記工程(d)は、ハッシュへの登録対象のうちインデックスの等しい登録対象が複数個ある場合それらをいずれもハッシュに登録せず、インデックスの異なる登録対象だけをハッシュに登録する工程である請求項３〜５の何れか一つに記載の方法。
【請求項７】
入力された文書および／または画像の特徴を示す特徴点を抽出し、各特徴点から得られる特徴量と、データベース中に登録された文書および／または画像の特徴点から得られる特徴量とを比較し、入力された文書および／または画像に対応するデータベース中の文書および／画像を検索する方法であって、
前記データベースは、登録すべき文書および／または画像から抽出された各特徴点pについてその近傍n個の特徴点を選択し、それらn個の特徴点からm個（m≦n）をさらに選択する各組合せについて実行する次の工程(s1)〜(s4)、
(s1) 対象とするm個の各特徴点p(i)(ここでiは各点に対応する0〜(m-1)の整数)について、所定方向の巡回順に並ぶc個(c＜m)の配置関係に基づくスコアS(i)をそれぞれ求める工程、
(s2) スコアS(i)が最大の特徴点p(i)を開始点として前記巡回順のd個（d≦m）の点から特徴量の要素となる値を求め、開始点を巡回順にずらしていって各開始点からd個の点に基づいてそれぞれ要素を求め、開始点の巡回順に所定個数の要素を組み合わせた多次元ベクトルを特徴点pに係る特徴量として求める工程、
(s3) 求めた特徴量から所定の計算手順でハッシュのインデックスを求める工程、
(s4) 求めたインデックスでハッシュ表にアクセスし、(b)工程で求めた特徴量と特徴点pが抽出された文書および／または画像を識別する文書IDとをハッシュに登録する工程
が実行されて文書および／または画像が登録されたものであり、
コンピュータが、
入力された文書および／または画像から抽出された各特徴点pqについて、近傍n個の特徴点からm個を選択する各組み合わせについて実行する次の工程(r1)〜(r4)、
(r1) 対象とするm個の各特徴点p(k)について、所定方向の巡回順に並ぶc個の配置関係に基づくスコアS(k)(ただしkは各点に対応する0〜(m-1)の整数)を求める工程、
(r2) m個の特徴点のうちスコアS(k)が最大の点を開始点として前記巡回順のd個の点から特徴量の要素を求め、開始点を巡回順にずらしたd個からさらに異なる要素を求め、それらを開始点の巡回順に組み合わせた多次元ベクトルを点pqに係る特徴量として求める工程、
(r3) 求めた特徴量から予め定められた計算手順でハッシュのインデックスを求め、そのインデックスでハッシュを参照する工程、
(r4) 登録されたリストから得られる文書IDに対して投票する工程
を実行し、
投票結果に基づいて検索結果を決定することを特徴とする文書および／または画像の検索方法。
【請求項８】
前記スコアS(i)は、点p(i)を含む所定個数の特徴点から求められるアフィン不変量であり、
前記スコアS(k)は、点p(k)を含む所定個数の特徴点から求められるアフィン不変量である請求項７に記載の方法。
【請求項９】
前記スコアS(i)の算出手順は、点pに係る特徴量の算出手順の一部と共通し、
前記スコアS(k)の算出手順は、点pqに係る特徴量の算出手順の一部と共通する請求項７または８に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【公開番号】特開２００９−７００６６（Ｐ２００９−７００６６Ａ）
【公開日】平成２１年４月２日（２００９．４．２）
【国際特許分類】
【出願番号】特願２００７−２３６７３８（Ｐ２００７−２３６７３８）
【出願日】平成１９年９月１２日（２００７．９．１２）
【出願人】（５０５１２７７２１）公立大学法人大阪府立大学 (688)
【Ｆターム（参考）】
【公開日】平成２１年４月２日（２００９．４．２）
【国際特許分類】
【出願日】平成１９年９月１２日（２００７．９．１２）
【出願人】（５０５１２７７２１）公立大学法人大阪府立大学 (688)
【Ｆターム（参考）】
[ Back to top ]