(57)【特許請求の範囲】
【請求項１】
画像に対する注目位置および注目サイズを変更しながら、注目する領域と複数カテゴリの文字認識辞書との距離を算出する文字走査処理を行い、この文字走査処理により得られた候補文字集合に対して、探索を指定された文字列を構成する文字が一定のピッチで直線状に並んでいる個所を探索処理する文字列探索装置の文字列探索方法において、
すべての候補文字について、元の画像内の該当領域のパターンの変形角度を推定する変形角度推定ステップと、
前記探索を指定された文字列の任意の２個の文字に対応する候補文字のペアについて、２個の文字の文字位置から前記候補文字のペアで想定される文字列における先頭文字の座標位置と文字間ピッチを求め、２つの候補文字の大きさの関係が所定の範囲内で、かつ、前記文字間ピッチで定まる文字の並びの方向が決められた方向の範囲内で、かつ、候補文字の大きさと前記文字間ピッチの関係が所定の範囲内という条件を満足し、かつ、２個の文字の文字位置から定まる両者の相対的な角度および両者の変形角度が定められた角度の条件を満足するものだけを選ぶ投票ステップと、
前記候補文字のペアについて、その先頭文字の座標位置を定数で調整した始点の概値が一致し、かつ、文字間ピッチを定数で調整したピッチの概値が一致するものをまとめる投票空間格納ステップと、
前記投票空間格納ステップによりまとまったもののうち、探索文字列の文字数から定まる所定数以上の候補文字があるものを抽出する候補点群作成ステップと、
前記候補点群作成ステップで抽出された候補文字の中から、なるべく直線的に並ぶ候補文字に絞る候補点選択ステップと、
を備えたことを特徴とする文字列探索方法。
【請求項２】
画像に対する注目位置および注目サイズを変更しながら、注目する領域と複数カテゴリの文字認識辞書との距離を算出する文字走査処理を行い、この文字走査処理により得られた候補文字集合に対して、探索を指定された文字列を構成する文字が一定のピッチで直線状に並んでいる個所を探索処理する文字列探索装置において、
すべての候補文字について、元の画像内の該当領域のパターンの変形角度を推定する変形角度推定手段と、
前記探索を指定された文字列の任意の２個の文字に対応する候補文字のペアについて、２個の文字の文字位置から前記候補文字のペアで想定される文字列における先頭文字の座標位置と文字間ピッチを求め、２つの候補文字の大きさの関係が所定の範囲内で、かつ、前記文字間ピッチで定まる文字の並びの方向が決められた方向の範囲内で、かつ、候補文字の大きさと前記文字間ピッチの関係が所定の範囲内という条件を満足し、かつ、２個の文字の文字位置から定まる両者の相対的な角度および両者の変形角度が定められた角度の条件を満足するものだけを選ぶ投票手段と、
前記候補文字のペアについて、その先頭文字の座標位置を定数で調整した始点の概値が一致し、かつ、文字間ピッチを定数で調整したピッチの概値が一致するものをまとめる投票空間格納手段と、
前記投票空間格納手段によりまとまったもののうち、探索文字列の文字数から定まる所定数以上の候補文字があるものを抽出する候補点群作成手段と、
前記候補点群作成手段で抽出された候補文字の中から、なるべく直線的に並ぶ候補文字に絞る候補点選択手段と、
を備えたことを特徴とする文字列探索装置。
【請求項３】
請求項１に記載の文字列探索方法における処理手順をコンピュータに実行させるプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、本発明は、濃淡画像から指定された文字列が存在する位置を探索する技術に関する。
【背景技術】
【０００２】
景観の濃淡画像に写った文字列の認識技術の一つに、画像を２値化せずに濃淡のままで用い、ずらしマッチングにより各文字カテゴリの基準となる形状を表す認識辞書と画像の各領域の近さを算出し、算出された近さの値のマップから局所的なピークを全て取り出し、それらピークの中であらかじめ決められた文字列の図形的な配置規則に従うピークの列を抽出する技術がある（例えば、特許文献１参照）。
【０００３】
この探索技術では濃淡画像を２値化しないため、撮影条件が悪く画像のコントラストが低い場合、部分的な隠蔽がある場合、文字間の接触、複雑な背景、文字の陰影等に対して強いという特徴がある。
ここで、特許文献１の詳細な説明には、図４２に「電話会社」という文字列が写った濃淡画像の例を示すように、認識対象とする文字が変形しうる場合についての対策は記載されていないが、その［請求項７］には抽出の対象である画像もしくは認識辞書を変形させることで認識対象とする文字の変形に対処する方法が記載されている。また、特許文献１の詳細な説明では、認識対象を数字の集合に限定しているが、これは他の場合、例えば漢字の集合に容易に拡張できる。
【０００４】
また、特許文献１の詳細な説明では、認識辞書と画像の各領域との近さの距離値としては相関を用いているが、これは他の距離値、例えばユークリッド距離、該特徴空間における少数の特徴ベクトルで近似された部分空間への投影距離（田村秀行：「コンピュータ画像処理」pp282-286、オーム社出版局、2002）、カーネル関数により定義された非線形変換を利用して作成した該部分空間への投影距離（前田英作、村瀬洋：「カーネル非線形部分空間法によるパターン認識」、電子情報通信学会論文誌D-II、VOL.J82-D-II、NO.4、pp600-612、1999年4月）、ベイズ推定や最尤推定等の特徴ベクトル空間における生起確率（Richard O.Duda、Peter E.Hart、David G.Stork：「パターン識別」84-101、新技術コミュニケーションズ、2001）などが使用できることは類推できる。また、認識辞書と画像の各領域との近さの算出の際に、両者の画像をそのまま用いているが、これを他の特徴量、例えば画素値の２乗の合計が一定値になるように正規化したものや、濃淡の加重方向ヒストグラム特徴の各特徴量の２乗の合計値が一定値になるように正規化したものを用いることもできる。
【０００５】
ここで、説明のために、従来技術において、対象とする画像の解像度を複数段階に変化させることとし、またアフィン変換によって様々な歪を加えたテンプレートをあらかじめ用意しておき、それらのテンプレートを用いて解像度を複数段階に変化させた各画像に対してずらしマッチングを行なうこととする。また認識辞書と画像の各領域との近さの距離値としてはユークリッド距離を用いることとする。複数段階の解像度の例として、図４３の（ａ）〜（ｄ）は、各々図４２の原画像を、０.７倍、０.８倍、１.０倍、１.２倍したものであり、各々の左上の矩形は、例とする観測窓の大きさ（４０画素×４０画素）を表している。走査の結果、解像度毎に候補文字の検出結果が生成されるが、図４４は原画像を０.７倍に縮小した図４３（ａ）に対する走査結果の模式図である。図において、［］と■で表される点が正しい候補文字、（）と×で表される点が偽の候補文字である。［］、（）内の情報は、第１が候補文字、第２が認識結果の距離値である。このような結果が複数の解像度分だけ生成される。
【０００６】
特許文献１においては、この後に、それらピークの中であらかじめ決められた文字列の図形的な配置規則に従うピークの列を抽出する処理を行なうが、認識対象がナンバープレート以外の場合（例えば日本語の看板等）には、この処理ではうまく働かないことがある。理由は、認識対象カテゴリを漢字のように大きなセット（ＪＩＳ第１水準のセットで２９６５個）にすると非常に多くの偽のピークが発生することと、文字の背景が無地であるナンバープレートとは異なり看板の文字の背景には模様がある場合がありその場合には模様の部分からやはり非常に多くの偽のピークが発生するため、文字列の図形的な配置規則に従う偽のピークの列が数多く抽出されることによる。
【０００７】
ここで、画像を検索するためであれば、必ずしも正しい文字列だけが抽出できなくとも、ピーク（以降、これを候補文字と呼ぶ）の集合をまとめたものをインデクスとし、このようなインデクスを用いて文字列をキーとして（例えば「電話会社」をキーとして入力して）画像を検索できれば良いことに注目する。そのためには、背景からの偽の候補文字も大量に出現することを前提として「電話会社」のような文字列が空間的な規則性を持ってインデクスの中に存在する個所を探索する手段が必要である。これを行なうためには、検索キーとされた文字列の文字数をＬとした場合、候補文字の総数をＭとすると、Ｍ個の中からＬ個を選ぶＭＣＬ個全ての組み合わせに対して、検索文字列と一致するか否か、さらに空間的に直線的に低ピッチで並んでいるか否か、を調べる必要があり、膨大な処理時間が必要である。
【０００８】
この問題を解決し、濃淡画像を２値化することなく濃淡画像から指定される文字列を探索する方式において、探索処理時間を大幅に短縮できる文字列探索技術の従来技術が特許文献２に示されている。ここでは、濃淡画像の小ブロックにある候補文字数を距離によって絞込み、近くにある同じカテゴリ文字となる候補を削除し、探索文字列の２つの文字を取り出して、これとカテゴリが一致する文字候補の組み合わせを求める。また、２つの候補の組み合わせを、さらに組み合わせて整合するものを選択する。次に、探索文字列の文字数により、所定文字数以上の固まりになったものを選択する。そして、候補点で重複するものは除いて、最後は候補の座標位置から１つに絞り込んでいる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００１−３０７０２１号公報
【特許文献２】特許第４４１８７２６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、特許文献２に示す方法では、画像に文字が含まれていない場合でも、画像内のテクスチャを文字として認識する場合があると考えられる。例えば、図２０（ａ）は格子状のテクスチャの領域を撮影した景観画像の模式図である。この画像には文字列は含まれていないので、どのような検索文字列に対しても検索されれば誤りである。これに対して、濃淡画像からの候補文字の抽出処理によって出力された結果を原画像に重畳した模式図を図２０（ｂ）に示す。説明の簡単のために、２個の候補文字だけが抽出され候補文字集合を構成したとし、この候補文字集合を図２０（ｃ）に示す。
【００１１】
これに対して、探索キーとして２文字の文字列「土田」が投入されたとする。この時の特許文献２の技術の動作を確認する。まず、 図２２（ｃ）の候補文字集合が候補文字絞込み手段により処理される。まず単一解像度候補文字絞込み手段においてブロック内で候補文字から２個までに絞り込むが、この例では全部で２個の候補文字しかないので影響を受けない。次に、この結果が複数解像度候補文字絞込み手段に入力されるが、２個の候補文字は互いに文字カテゴリが一致しないので影響しない。
【００１２】
次に投票手段の処理に移る。ここでは投票手段は探索キーの２つの文字要素を取り出して、文字要素と候補のカテゴリが一致する組み合わせを求める。この場合、探索キーは「土田」で、２つの文字要素は「土」と「田」の組合せだけである。したがって、図２０（ｃ）のＰＩＤ＝０、ＰＩＤ＝１の候補文字の組合せだけが選ばれる。次に、投票手段が以下（Ａ１）〜（Ｄ１）の順に処理を行う。
まず、（Ａ１）文字列の中心位置座標の配列を規定する４つのパラメータ値（ａ、ｂ、ｃ、ｄ）を算出する。ここでは仮想ピッチベクトルを算出するが、ＰＩＤ＝０、ＰＩＤ＝１の候補文字とこれらを結ぶ仮想ピッチベクトルの関係を図示したのが図４５である。この例では単語長さは２文字で候補文字も２個だけなので、ａはＰＩＤ＝０のＸ座標１１０、ｂはＰＩＤ＝０のＹ座標１００、ｃはＰＩＤ＝０を始点としＰＩＤ＝１を終点とするベクトルのＸ成分２３０−１１０＝１２０、ｄはＰＩＤ＝０を始点としＰＩＤ＝１を終点とするベクトルのＹ成分１２０−１３０＝−１０、となる。
【００１３】
そして、（Ｂ１）パラメータ値（ａ、ｂ、ｃ、ｄ）から、投票空間格納手段に登録するための座標ベクトル（Ｒａ、Ｒｂ、Ｒｃ、Ｒｄ）を算出する。この処理結果は動作に影響しないので記述を省略する。
【００１４】
次に、（Ｃ１）各々の候補点Ｒ１とＲ２の組み合わせの可否を判定する関数（組み合わせ判定関数）を適用する。ここでは、
・ｓ＝（Ｒ２の「大きさ」）÷（Ｒ１の「大きさ」）＝１
・α＝仮想ピッチベクトルの角度＝ａｒｃｔａｎ（−１０／１２０）＝４．７６度
・Ｐｓ＝（ｃ×ｃ＋ｄ×ｄ）０．５／０.５×（Ｒ２の「大きさ」＋Ｒ１の「大きさ」）
＝（１２０×１２０＋（−１０）×（−１０））０．５／０．５×（５０＋５０）
＝１２０．４／５０
＝２．４
となる。これらの数値は、
「ｓ１＜ｓ＜ｓ２ かつα∈α１かつＰｓ１＜ｐｓ＜Ｐｓ２」
を満足する。したがって、次の処理である（Ｄ１）組み合わせ判定関数が合格と判定した組み合わせを投票空間格納手段に追加する処理を実施する。
【００１５】
これを受けて、投票空間格納手段は、２つの候補の組み合わせを、さらに組み合わせて整合するものを選択する。しかしこの場合は２つの候補の組み合わせは一つしかないので、それがそのまま選択され、投票空間に格納される。
次に候補点群作成手段は、探索キーの文字数により、投票空間格納手段の処理で所定文字数以上の固まりになったものを選択し、ＰＩＤ＝０、ＰＩＤ＝１の候補文字の組合せがそのまま選ばれる。次に候補点選択手段は、候補点で重複するものは除いて、最後は候補の座標位置から１つに絞り込むがこの場合はＰＩＤ＝０、ＰＩＤ＝１の候補文字の組合せには重複は無いのでそのまま出力される。すなわち、検索文字列「土田」に対して、ＰＩＤ＝０、ＰＩＤ＝１の候補文字の組合せが検索結果として返されることとなる。すなわち、図２０（ａ）の画像には文字が含まれていないのに、誤って検索結果として出力されるという処理の失敗が発生すると考えられる。
【００１６】
本発明は、このような状況に鑑みてなされたもので、画像に文字が含まれていない場合に文字列による検索を行う際、文字列が誤って検索されてしまうことを防ぎ、より精度良く文字列探索を行う文字列探索方法、文字列探索装置、記録媒体を提供する。
【課題を解決するための手段】
【００１７】
上述した課題を解決するために、本発明は、画像に対する注目位置および注目サイズを変更しながら、注目する領域と複数カテゴリの文字認識辞書との距離を算出する文字走査処理を行い、この文字走査処理により得られた候補文字集合に対して、探索を指定された文字列を構成する文字が一定のピッチで直線状に並んでいる個所を探索処理する文字列探索装置の文字列探索方法において、すべての候補文字について、元の画像内の該当領域のパターンの変形角度を推定する変形角度推定ステップと、探索を指定された文字列の任意の２個の文字に対応する候補文字のペアについて、２個の文字の文字位置から候補文字のペアで想定される文字列における先頭文字の座標位置と文字間ピッチを求め、２つの候補文字の大きさの関係が所定の範囲内で、かつ、文字間ピッチで定まる文字の並びの方向が決められた方向の範囲内で、かつ、候補文字の大きさと文字間ピッチの関係が所定の範囲内という条件を満足し、かつ、２個の文字の文字位置から定まる両者の相対的な角度および両者の変形角度が定められた角度の条件を満足するものだけを選ぶ投票ステップと、候補文字のペアについて、その先頭文字の座標位置を定数で調整した始点の概値が一致し、かつ、文字間ピッチを定数で調整したピッチの概値が一致するものをまとめる投票空間格納ステップと、投票空間格納ステップによりまとまったもののうち、探索文字列の文字数から定まる所定数以上の候補文字があるものを抽出する候補点群作成ステップと、候補点群作成ステップで抽出された候補文字の中から、なるべく直線的に並ぶ候補文字に絞る候補点選択ステップと、を備えたことを特徴とする。
【００１８】
また、本発明は、画像に対する注目位置および注目サイズを変更しながら、注目する領域と複数カテゴリの文字認識辞書との距離を算出する文字走査処理を行い、この文字走査処理により得られた候補文字集合に対して、探索を指定された文字列を構成する文字が一定のピッチで直線状に並んでいる個所を探索処理する文字列探索装置において、すべての候補文字について、元の画像内の該当領域のパターンの変形角度を推定する変形角度推定手段と、探索を指定された文字列の任意の２個の文字に対応する候補文字のペアについて、２個の文字の文字位置から候補文字のペアで想定される文字列における先頭文字の座標位置と文字間ピッチを求め、２つの候補文字の大きさの関係が所定の範囲内で、かつ、文字間ピッチで定まる文字の並びの方向が決められた方向の範囲内で、かつ、候補文字の大きさと文字間ピッチの関係が所定の範囲内という条件を満足し、かつ、２個の文字の文字位置から定まる両者の相対的な角度および両者の変形角度が定められた角度の条件を満足するものだけを選ぶ投票手段と、候補文字のペアについて、その先頭文字の座標位置を定数で調整した始点の概値が一致し、かつ、文字間ピッチを定数で調整したピッチの概値が一致するものをまとめる投票空間格納手段と、投票空間格納手段によりまとまったもののうち、探索文字列の文字数から定まる所定数以上の候補文字があるものを抽出する候補点群作成手段と、候補点群作成手段で抽出された候補文字の中から、なるべく直線的に並ぶ候補文字に絞る候補点選択手段と、を備えたことを特徴とする。
【００１９】
また、本発明は、上述の文字列探索方法における処理手順をコンピュータに実行させるプログラムを記録した記録媒体である。
【発明の効果】
【００２０】
以上説明したように、本発明によれば、文字列探索の際に、探索キーとされた長さＬの文字列から、該文字列の前から後の方向に存在する全ての２個の文字の組である文字ペアを選び、各々の文字ペアに対して、候補文字集合中から文字カテゴリが一致する全ての２個の候補文字の組を探索する処理を行い、該処理の結果探索された全ての２個の候補文字の組に対して、ピッチが一定でかつ直線的に並ぶ文字列を特定するパラメータの組を算出する際に、候補文字パターンの変形角度を推定しその結果に基づく判定処理を行って合格した場合にだけ該２個の候補文字の組と該パラメータの組の情報を投票空間に投票するようにしたので、画像に文字が含まれていない場合に文字列による検索を行う際、文字列が誤って検索されてしまうことを防ぎ、より精度良く文字列探索を行うことが可能となる。
【図面の簡単な説明】
【００２１】
【図１】本発明の一実施形態による文字列探索装置の構成例を示すブロック図である。
【図２】本発明の一実施形態による候補文字絞込み手段の構成例を示すブロック図である。
【図３】本発明の一実施形態による単一解像度候補文字絞込み手段の処理過程を示す模式図である。
【図４】本発明の一実施形態による単一解像度候補文字絞込み手段の処理過程を示す模式図である。
【図５】本発明の一実施形態において元画像の中を０.７倍した解像度の画像から出力された候補文字を重畳表示した模式図である。
【図６】本発明の一実施形態による単一解像度候補文字絞込み手段の処理過程を示す模式図である。
【図７】本発明の一実施形態による単一解像度候補文字絞込み手段の処理過程を示す模式図である。
【図８】本発明の一実施形態による単一解像度候補文字絞込み手段の処理過程を示す模式図である。
【図９】本発明の一実施形態による単一解像度候補文字絞込み手段の処理過程を示す模式図である。
【図１０】本発明の一実施形態による単一解像度候補文字絞込み手段の処理過程を示す模式図である。
【図１１】本発明の一実施形態による単一解像度候補文字絞込み手段の処理過程を示す模式図である。
【図１２】本発明の一実施形態による絞込み処理の入力データ配列の例を示す図である。
【図１３】本発明の一実施形態による絞込み処理を示すフローチャートである。
【図１４】本発明の一実施形態による複数解像度候補文字絞込み手段におけるデータの処理過程を示す模式図である。
【図１５】本発明の一実施形態による複数解像度候補文字絞込み手段におけるデータの処理過程を示す模式図である。
【図１６】本発明の一実施形態による複数解像度候補文字絞込み手段におけるデータの処理過程を示す模式図である。
【図１７】本発明の一実施形態による変形角度推定手段の動作を説明するための、前提とする斜めからの撮影による文字パターン列の変形、および水平軸と垂直軸の角度変化についての模式図である。
【図１８】本発明の一実施形態による変形角度推定手段２０の構成例を示す図である。
【図１９】本発明の一実施形態により元画像から抽出された２つの候補文字の領域の画像を示す図である。
【図２０】本発明の一実施形態による処理対象となる文字が存在しない画像と、その画像から抽出された候補文字集合の模式図である。
【図２１】本発明の一実施形態による文字パターンと勾配ベクトルの角度分布のグラフの例を示す図である。
【図２２】本発明の一実施形態による文字パターンと勾配ベクトルの角度分布のグラフの例を示す図である。
【図２３】本発明の一実施形態によるマスクと勾配ベクトルの角度分布のグラフの例を示す図である。
【図２４】本発明の一実施形態によるマスク生成手段の処理過程を表す図である。
【図２５】本発明の一実施形態による変形角度の推定結果の例を示す図である。
【図２６】本発明の一実施形態による投票処理の処理を示すフローチャートである。
【図２７】本発明の一実施形態による投票処理途中のデータ例を示す図である。
【図２８】本発明の一実施形態により２個の候補点から算出される、仮想的な開始点のＸ座標、仮想的な開始点のＹ座標、仮想的なＸ方向のピッチ、仮想的なＹ方向のピッチ、仮想的ピッチベクトルのＸ成分、仮想的ピッチベクトル、等の概念を説明する模式図である。
【図２９】本発明の一実施形態による投票処理のデータ処理過程を示す図である。
【図３０】本発明の一実施形態による投票処理のデータ処理過程を示す図である。
【図３１】本発明の一実施形態による投票処理のデータ処理過程を示す図である。
【図３２】本発明の一実施形態による投票処理のデータ処理過程を示す図である。
【図３３】本発明の一実施形態による２個の候補文字および各値の関係の示す模式図である。
【図３４】本発明の一実施形態による投票処理のデータ処理過程を示す図である。
【図３５】本発明の一実施形態による投票空間格納手段の初期状態を示す図である。
【図３６】本発明の一実施形態による処理後の投票空間格納手段の状態を示す図である。
【図３７】本発明の一実施形態による候補文字・文字位置リストの例を示す模式図である。
【図３８】本発明の一実施形態による候補文字・文字位置リストの例を示す模式図である。
【図３９】本発明の一実施形態による候補点群リストの処理過程を示す図である。
【図４０】本発明の一実施形態による候補選択処理の処理過程を示す図である。
【図４１】本発明の一実施形態による候補選択処理の処理結果を示す図である。
【図４２】文字探索の処理対象である元画像の例を示す図である。
【図４３】文字探索の処理対象である元画像を複数の解像度に変換した例を示す図である。
【図４４】文字探索の処理対象である元画像を０.７倍した解像度の画像から出力された候補文字を重畳表示した模式図である。
【図４５】文字探索の処理対象である元画像から抽出された２つの候補文字とそれらを組み合わせた仮想ピッチベクトルを表す図である。
【発明を実施するための形態】
【００２２】
以下、本発明の一実施形態について、図面を参照して説明する。
図１は、本実施形態による文字列探索装置１の構成を示すブロック図である。文字列探索装置１は、候補文字絞込み手段１０と、変形角度推定手段２０と、選択的投票手段３０と、投票空間格納手段４０と、候補点群作成手段５０と、候補点選択手段６０とを備えている。
【００２３】
候補文字絞込み手段１０は、文字列探索における最初の処理を行う。候補文字絞込み手段１０は様々な構成が考えられるが、本実施形態では説明のために、図２に示す構成をとる。候補文字絞込み手段１０は、単一解像度候補文字絞込み手段１１と、複数解像度候補文字絞込み手段１２とを備えている。単一解像度候補文字絞込み手段１１は、候補文字集合を画像の解像度別に分け、各々の候補文字集合の中での絞込み処理を行なう。これに対し、複数解像度候補文字絞込み手段１２は、全ての解像度の候補文字集合に対する絞込み処理を行なう。本実施形態ではこの２つの手段を直列に接続して候補文字を絞込む。
【００２４】
単一解像度候補文字絞込み手段１１は、例えば、ある解像度の画像に対して、１つの小ブロックにある候補文字数を距離によって絞込む。この絞込みは、升目の仕切位置を変更しても行う。この処理の詳細を説明する。ここでは、ある解像度における候補文字集合を、その中心座標によりブロック分割する。本実施形態では解像度が原画像の０.７倍の場合のみを図面を参照して説明する。他の解像度については単一解像度候補文字絞込み手段１１の処理内容の説明は省略するが、同様の処理である。
【００２５】
図３は、０.７倍の画像の場合の基本的なブロック分割の様子を示しており、各升目が４０画素×４０画素のブロックを表している。実際のブロック分割は、この基本的なブロック分割を基に、ブロック配列の位置を縦および横方向にずらした分割方法を複数用意する。図４（ａ）〜（ｄ）はその例で、これらのうち、太線で囲まれた正方形の閉領域が１つのブロックである。図４（ａ）は、図３の基本的なブロック分割をずらさずに用いたブロック分割結果であり、（ｂ）、（ｃ）はそれぞれ縦方向、横方向に２０画素ずらしたもの、（ｄ）は縦横に両方とも２０画素ずらしたものである。
【００２６】
ここで、単一解像度候補文字絞込み手段１１は、これらのブロック分割結果を順番に適用して絞込みを行なう。まず、図４（ａ）を用いた例を説明する。図５に示す候補文字集合を、図４（ａ）のブロック分割方法に従って分割したのが図６である。ここで、１ブロックの中での絞込みの方法を、候補文字を距離値の小さい順に並び替え、上位の候補文字から一定個数（この実施形態では２個）だけ採用して他を削除するものとする。他にも、候補文字を距離値の小さい順に並び替え、最小の距離値を持つ候補文字からの距離値の差分が一定閾値を越える候補文字を削除する方法もありうる。
【００２７】
図６の場合、複数の候補文字が存在するブロックは左上端から１ブロック分右下のブロックだけであり、このブロックにおける処理内容を説明する。このブロックには、（電、６００）と［電、４２０］と（黄、７８０）の３個が存在する。これを距離の小さい順に並び替えると、［電、４２０］、（電、６００）、（黄、７８０）となり、これを上位から２個だけ採用し他を削除すると、［電、４２０］、（電、６００）が残る。これを図示したのが図７である。
【００２８】
１ブロックの中での絞込みの方法としては、以上の他に、候補文字を距離値の小さい順に並び替えた後、上位の候補文字と同一の文字カテゴリを有する下位の候補文字を削除した後に、上位の候補文字から一定個数個（この実施形態では２個）だけ採用して他を削除する方法もある。図８は図６に対してこの方法を適用した結果である。
【００２９】
さて、単一解像度候補文字絞込み手段１１は、図７の結果に対して、次に、他のブロック分割方法を適用して絞込みを行なう。図９は、図７の結果に対して図４（ｂ）のブロック分割方法を当てはめた時のブロック分割の様子であり、図１０はその絞込み結果である。これに対してさらに、図４（ｃ）、図４（ｄ）を当てはめるが、候補文字はこれ以上削減されない。従って、図１０が解像度０.７倍の場合の単一解像度候補文字絞込み手段１１の処理結果である。同様に、他の解像度に対しても同様の処理結果が単一解像度候補文字絞込み手段１１から出力される。
【００３０】
複数解像度候補文字絞込み手段１２は、単一解像度候補文字絞込み手段１１による単一解像度候補文字絞込みが行われた後の処理を行う。複数解像度候補文字絞込み手段１２は、距離が小さい候補文字は残す方針による判定関数（Ｆ１）を用いて、近くにある同じカテゴリ文字となる候補を削除する文字絞込みを行うもので、以下詳細に説明する。複数解像度候補文字絞込み手段１２は、まず、単一解像度候補文字絞込み手段１１から出力された各解像度の絞込み結果を一つにまとめる。まとめた結果の例を図１１と図１２に示す。図１１において、［］と■は正しい候補文字（■は中心座標）、（）と×は誤った候補文字（×は中心座標）である。また、実線の正方形は正しい候補文字の窓の大きさを、破線の正方形は誤った候補文字の窓の大きさを表す。さらに［］、（）内の情報は、ＰＩＤ（単一解像度候補文字絞込み手段１１の処理の結果残った候補文字の０から始まる通し番号）、候補文字カテゴリ、中心点のＸ座標、中心点のＹ座標、観測窓の大きさを表す。ここで、観測窓の大きさは、基本的な観測窓の大きさ（縦４０画素、横４０画素）を画像の解像度の倍率で割った値である。例えば、原画像を０.７倍した画像から検出された候補文字の観測窓の大きさは、縦４０画素、横４０画素を０.７で割った値であり、縦横共通に５７.１≒５７である。すなわち、図１１において観測窓の大きさ＝５７である候補文字が図１０のデータ（解像度が０.７倍）に由来する。
【００３１】
図１２は、図１１の各候補文字をリストにまとめたものであり、図１１の情報に加えて候補文字の認識結果の距離値が情報として加わっている。また、図１２には「正誤」の情報が示されているが、これは本実施形態の説明のために、正しい候補文字（正誤＝１）と誤った候補文字（正誤＝０）を区別するために便宜上示したものであり、実際の処理とは無関係である。この図１２に例を示すリストを「入力データ配列」と呼ぶ。
【００３２】
次に、複数解像度候補文字絞込み手段１２では、入力データ配列のデータに対して図１３のフローチャートで示した処理を行なう。図１３の処理において、関数Ｆ１とは、２つの候補文字が「近い」か「遠い」かを判定する判定関数である。具体的には、
（１）２つの候補文字の文字カテゴリが一致するか否か
（２）２つの候補文字の中心座標のユークリッド距離の近さ
（３）２つの候補文字の大きさの近さ
の３つの「近さ」を総合判断して決定する。総合判断の方法は様々に考えられるが、ここでは例として、（３）は無視して、（１）の文字カテゴリが一致し、かつ（２）のユークリッド距離が一定の閾値（この例では４０）以下である場合に、Ｆ１は「近い」と判断し、それ以外の場合は「遠い」と判断するものとする。その結果が図１４と図１５であり、途中経過を示すのが図１６である。
【００３３】
図１３のフローチャートでは、まず図１２で示す入力データ配列に対して、距離値の小さい順にソートする（Ｓ０）が、この場合の結果が図１６（ａ）である。またこの後に、入力データ配列の上位レコードから順次「大きさ」が−１でないものを取り出して行く。この実施形態では、入力データ配列のレコードの「大きさ」に「−１」を記入することは「削除」を意味しており、これはレコードの他の欄を用いてもよい。また、図１３におけるレコードバッファとは、入力データ配列におけるレコードの情報を複数個分コピーして一時格納しておくメモリである。
【００３４】
図１６（ａ）の例では、ｉ＝１から初めてｉ＝６までは、レコードバッファに格納されるのは入力データ配列のｉ番目のレコード１個だけであり、入力データ配列のデータは削除されない（すなわちいずれのレコードの「大きさ」も−１が書き込まれない）。これに対して、ｉ＝７の時には、レコードバッファに計３個のレコードが書き込まれる（Ｓ５）。これは図１６（ｂ）の３つのレコード（ｉ＝７、９、１０）であり、書き込まれたレコードバッファが図１６（ｃ）である。このレコードバッファから上位一定個数（ここでは例として２個）のレコードを削除すると（Ｓ６）、この例ではＰＩＤ＝０のレコードだけが残り、このレコードのＰＩＤ＝０に該当する入力データ配列のレコードの「大きさ」の欄に−１を書き込んだ（Ｓ８）のが図１６（ｄ）である。
さて、入力データ配列のｉ＝７に対する上記の処理の後、ｉ＝８から１１まで処理を行なった後でも入力データ配列の内容は図１６（ｄ）と変わらない。最後に入力データ配列をＰＩＤの小さい順にソート（Ｓ２）した結果が図１４であり、それを画像上に重畳して表示したのが図１５である。
【００３５】
なお、Ｆ１における総合判断の方法としては上記以外にも、（１）を無視することが考えられる。また（３）を無視せずに、２つの候補文字の大きさの近さが一定閾値以下である、という条件をＦ１の判断に論理積の形で加えることも考えられる。すなわち、（１）の文字カテゴリが一致し、かつ（２）のユークリッド距離が一定の閾値以下であり、かつ（３）の２つの候補文字の大きさの近さが一定閾値以下である場合にＦ１は「近い」と判断する。その場合の「大きさの近さ」とは例えば、具体的には大きい方の「大きさ」を小さい方の「大きさ」で割った値を尺度とすることが考えられる。この尺度を用いる場合には、この尺度は両者の大きさが最も近い場合には１となり、大きさが離れていくにつれて１よりも大きな値になっていくので、２つの候補文字の大きさの近さの閾値は１よりも大きい値に設定する必要がある（例えば、１.５など）。あるいは、１つの閾値を用いる代わりに、２つの候補文字の大きさの順序は考慮せずに機械的に片方の「大きさ」をもう片方の「大きさ」で割った値を尺度として、その値に２つの値で決定される範囲を設定する方法もある。この場合、この尺度は両者の大きさが最も近い場合には１となり、大きさが離れていくにつれて１よりも小さくなるか大きくなっていくので、１より小さい値（例えば、０.７）と大きい値（例えば、１.５）の２つの値によって設定された範囲に入っていれば（例えば、０.７以上かつ１.５以下の範囲）Ｆ１は「近い」と判定し、そうでなければ「近い」と判定しない。
【００３６】
また、（２）と（３）の２つの「近さ」を個別に扱う代わりに、この２つの尺度を一つにまとめることも考えられる。具体的には、２つの候補文字の（中心点のＸ座標、中心点のＹ座標、大きさ）の３次元ベクトル間のユークリッド距離、もしくは各次元に重みをつけたユークリッド距離が一定閾値以下であることを「近い」と判定する尺度とする。
また、上述した関数Ｆ１の説明では、比較する２つの候補文字の「大きさ」が等しい場合も「近い」と判定する可能性があるが、これを比較する２つの候補文字の「大きさ」が等しい場合は「近い」と判定しない、とすることも可能である。これは、単一解像度候補文字絞込み手段１１において既に「大きさ」が等しい候補文字の絞込みは既に済んでいるので不要、という考え方による。
【００３７】
ここで、候補文字絞込み手段１０を単一解像度候補文字絞込み手段１１だけで構成することも可能である。その具体的な処理内容は、上記の候補文字絞込み手段１０の説明において、単一解像度候補文字絞込み手段１１による処理を行い、複数解像度候補文字絞込み手段１２では何もせずに単一解像度候補文字絞込み手段１１から受け取った処理結果をそのまま出力することができる。
また、上述の候補文字絞込み手段１０の構成を、まず複数解像度候補文字絞込み手段１２による処理を行って、その次に単一解像度候補文字絞込み手段１１による処理を行うという順番に構成することも可能である。例えば、複数解像度候補文字絞込み手段１２のＦ１の総合判定において、上記の（１）、（２）、（３）の３つの「近さ」の判定結果の論理積を用いることにすると、この複数解像度候補文字絞込み手段１２の処理によって、解像度と空間的な距離が近い同一カテゴリの候補文字を統合する効果となる。
【００３８】
次に、変形角度推定手段２０を説明する。まず、変形角度推定手段２０の動作を説明するために、前提とする斜めからの撮影による文字パターン列の変形、および水平軸と垂直軸の角度変化について模式図を用いて説明する。この説明では水平方向に文字が並んでいる模式図が例となっているが、縦方向に並ぶ場合も同様である。図１７（ａ）は、検出対象である文字パターン列を正面から見た時の例で、個々の文字パターンの変形の様子を示すために外接矩形で囲んだ。個々の文字パターンは同じ大きさで一本の直線上に等間隔に並んでいるとする。このとき、個別の文字パターンと、文字列パターン全体は、水平軸と垂直軸の方向を表すベクトルｕとｖを共有している。
【００３９】
この文字パターン列を斜めから見た画像を想定すると、原画像に対して見かけの変形が加わるが、この変形をアフィン変換で近似することとして、このアフィン変換が加わった模式図を図１７（ｂ）である（この図では外接矩形だけを描いた）。アフィン変換は、文字パターン列の画像全体に対して、１）大きさの変化、２）縦横比率の変化、３）スキュー、４）回転、５）並行移動が加わるものであり、その度合いはすべての座標で一定である。したがって上記のベクトルｕとｖは画像全体で同一の変換がなされ、変換後のベクトルをＵとＶで表すと、この２つはアフィン変換後の文字列パターン全体と個々の文字パターンとの間で共通する。ここでは、このベクトルＵとＶをパターンの空間的配置の検定の新たな手がかりとして採用する。ただしベクトルの形態では扱わず、代わりに各々の変換後の画像の見かけ上の水平軸と垂直軸との間の角度（図１７（ｃ）のα＾（α＾（αハット）は、図中ではαの上部に＾記号が付されたものである）とβ）を、方向を表す値として採用する。これら２角度は文字パターンの変形度合いを部分的に表しており、変形角度と呼ぶこととする。
【００４０】
これを前提として、変形角度推定手段２０の具体的な動作を説明する。変形角度推定手段１１は、候補文字絞込み手段１０から出力された入力データ配列に格納されたすべての候補文字の情報に対して、変形角度α＾、変形角度βを推定する。候補文字絞込み手段１０から出力された入力データ配列における１個の候補文字のフォーマットは、（カテゴリ名、Ｘ座標、Ｙ座標、大きさ、距離値）であるが、これに対して、変形角度α＾とβの値が加わるので、新たなフォーマットは（カテゴリ名、Ｘ座標、Ｙ座標、大きさ、距離値、変形角度α＾、変形角度β）となる。ただし後述するように、文字カテゴリによっては変形角度α＾とβとのいずれか、もしくは両方が推定できない場合もあり、その場合はこれらの値には無効を表す特別な値を入れる。
【００４１】
以下、変形角度推定手段２０が個別の候補文字に対して、該当する画像中の領域のパターンの角度α＾とβの推定を行う処理手順を説明する。変形角度推定手段２０の構成例を図１８に示す。変形角度推定手段２０は、制御手段２１と、マスクテーブル２２と、角度算出手段２３と、マスク生成手段２４とを備えている。
【００４２】
マスクテーブル２２は、各文字カテゴリについて、α＾算出用のマスクと、β算出用のマスクと、この２種類のマスクの有無を示すフラグとを格納したテーブルである。マスクの内容については後述する。このマスクテーブル２２に格納される個別のマスクの作成は、事前にマスク生成手段２４によって実施される。このマスク生成手段２４については後述する。
【００４３】
制御手段２１は、変形角度推定手段２０の全体的な制御を行う。制御手段２１は、例えば、候補文字絞込み手段１０から入力される入力データ配列から候補文字の情報を１つずつ取り出し、各々について以下の処理を行う。
まず、制御手段１０１０は、１個分の候補文字のレコードから候補文字の画像中のＸ座標とＹ座標とを取り出し、画像中から該当領域のパターンを切出して、文字カテゴリの情報と共に角度算出手段２３に送る。図１９の（ａ）と（ｂ）に、図２０（ｃ）のＰＩＤ＝０、１の候補文字の領域の切出し画像を入力する。以降、制御手段２１は、これをすべての候補文字について行う。
【００４４】
角度算出手段２３は、制御手段２１から候補文字の領域の切出画像が入力されると、マスクテーブル２２を参照し、入力された候補文字に該当するマスクの有無を調べる。このマスクが有る場合と無い場合とで以後の処理が異なる。α＾算出用のマスクとβ算出用のマスクとが両方とも無い場合のα＾の算出とβの算出との例として、図２１の左上に置かれた画像を対象とする例を述べる。このパターンは画像から切出した漢字の「土」のパターンの例であり、このパターンの領域が候補文字として検出され、候補文字カテゴリが正しく「土」であったとする。
【００４５】
角度算出手段２３は、まず、以下の処理を行う。切出された文字パターンの座標（ｘ、ｙ）における輝度値をｆ（ｘ、ｙ）、座標（ｘ、ｙ）における勾配ベクトルを（ｆｘ、ｆｙ）とすると、勾配ベクトルの角度ψ（ｘ、ｙ）は、ａｒｃｔａｎ（ｆｙ／ｆｘ）となる。このψ（ｘ、ｙ）の範囲を０≦ψ（ｘ、ｙ）＜２πとし、これから下式によりひとつの角度ψ＾（ｘ、ｙ）を得る。
【００４６】
ｉｆ  （ψ（ｘ、ｙ）＜π）  ψ＾（ｘ、ｙ）＝ψ（ｘ、ｙ）
ｅｌｓｅ  ψ＾（ｘ、ｙ）＝ψ（ｘ、ｙ）−π
（（ψ（ｘ、ｙ）＜π）が真の場合は、ψ＾（ｘ、ｙ）の値をψ（ｘ、ｙ）、偽の場合はψ＾（ｘ、ｙ）の値をψ（ｘ、ｙ）−πとする）
【００４７】
ψ（ｘ、ｙ）の範囲は０≦ψ（ｘ、ｙ）＜πであり、この範囲を離散的に量子化し投票空間として使用する。角度算出手段２３は、全座標（ｘ、ｙ）において、勾配ベクトル（ｆｘ、ｆｙ）を算出し、それから絶対値｜（ｆｘ、ｆｙ）｜と角度ψ＾（ｘ、ｙ）とを算出し、その角度ψ＾（ｘ、ｙ）を量子化した投票空間のブロックに｜（ｆｘ、ｆｙ）｜を加算する。投票では分布を平滑化するために前後のブロックにも｜（ｆｘ、ｆｙ）｜×０．３を加算することもありうる。またψ＾（ｘ、ｙ）の量子化処理では、単位を「度」に変換し、０度から１７９度まで一度単位の投票空間として用いる。図２１に示した「土」のパターンから以上の処理手順により得られた、ψ＾（ｘ、ｙ）の各値における｜（ｆｘ、ｆｙ）｜の合計値の分布を図２１に示す。「土」では水平方向のエッジと水平方向のエッジが共に多いのでピークが２箇所に出現している。
【００４８】
４５≦ψ＾＜１３５度のピークからα＾、それ以外の範囲のピークからβが算出される。エッジの勾配方向はエッジ方向と直交するため、ここでは９４度から９０度を減算した４度がα＾として求められる。０度の別のピークがβで、この場合のβは０度と求められる。
【００４９】
次に、α＾算出用マスクが存在するときのα＾の値の算出処理過程の例を説明する。βについても、このα＾と同様の処理が実施される。ここでは、図２２の左上に示した文字パターンの画像を対象とする例の処理過程を説明する。この文字パターンは、ある景観画像の中から切出された片仮名「ビ」の文字パターンのサンプルであり、この文字パターンの領域が候補文字として検出されたと仮定し、さらに候補文字カテゴリが正しく「ビ」であったと仮定する。この場合は、マスクテーブルの「ビ」のα＾算出用マスクの有無のフラグが１であるとして、そのマスクのデータをマスクテーブルから引き出して処理を行う。ここでは、図２３の左上に示した画像がマスクの具体例とする。この例では、原パターンに重ねたマスクの黒い領域だけにおける勾配ベクトルの角度分布を集計することとする。マスクの有効性を示すため、マスクを用いたときの勾配ベクトルの角度分布と、マスクを使わないときの勾配ベクトルの角度分布を、おのおの図２２と図２３に示して比較する。
【００５０】
さて、「ビ」の文字パターンは、パターンの下部に水平方向のエッジがあるが、その一方でその上部に右肩上りのエッジが存在することから、勾配ベクトルの角度分布をグラフ化すると、４５≦ψ＾＜１３５度の範囲に図２２に示すように、２箇所のピークが出現する。この２つのピークの中で、変形角度α＾に対応するのは正しくは左側であるが、いずれが正しいピークであるかをこの分布だけから識別することは困難である。これに対して図２３ではマスクの効果によって「ビ」の下部の水平方向のエッジを中心とする領域のみで勾配ベクトルの角度分布が集計されるため、９０度付近に正しく単一のピークが出現し、変形角度α＾を容易に推定できる効果は図から明らかである。この説明は変形角度α＾の推定の場合であるが、変形角度βの推定においても同様に文字カテゴリ毎にマスクを作成し、同様の処理を行うことで正しくβを推定することが可能である。
【００５１】
マスク生成手段２４は、マスクテーブル２２に記憶されるマスクを生成する。図２４に、文字「全」を例とし、変形角度α＾の推定のために用いるマスクを作成する処理の過程を示した。この図の例は、マスクを作成するための源となる情報として、ゴシック体の文字フォント１種類を２値画像にしたものを用いる。図において、（ａ）が１個のゴシック体の文字フォントの２値画像であり、それに対して（ｅ）が得られたマスクの画像を示す。なお（ｅ）では、黒い部分がエッジを集計する領域である。
【００５２】
まず、マスク生成手段２４は、（ａ）の源の画像を加工して（ｂ）に示すエッジの画像を作る。ここでは例として４近傍で黒画素を膨張させた後、元の画像との差分画像を用いることとする。次に（ｂ）のエッジの画像を水平方向に１画素収縮させ、縦や斜めや短い水平方向のエッジを消すことで（ｃ）の画像を作成する。そして（ｃ）の画像に対して、水平方向の膨張を複数回行って途切れたエッジをつなぎ、さらに収縮を複数回行うことにより、（ｄ）の画像を作成する。次に（ｄ）の画像に対して、垂直方向に膨張を複数回行うことで、（ｅ）に示すマスク画像を最終的に生成する。また、（ｆ）は（ｅ）のマスク画像をエッジ画像に重畳させて表したものである。なお、変形角度βを推定するためのマスクについては、以上の説明における垂直方向の処理と水平方向の処理を入れ替えて同様の処理を行うことにより作成することができる。
【００５３】
ところで、水平方向の長いエッジが少ない文字が少数ではあるが存在する。例としては、大部分が曲線により構成される文字（例：「の」）、大部分が斜め線により構成される文字（例：「へ」）、大部分が縦線で構成される文字（例：「川」）、などが挙げられる。これらの文字から変形角度α＾を推定することは難しいため推定対象から除外することとする。選択の基準は、マスクとして採用する領域の、文字パターン全体の領域に対する面積の比率が一定値以下の文字については不採用とする、という基準を採用する。この基準による「採用」と「不採用」の情報が、マスクテーブル２２に記憶された対応する文字カテゴリのマスクの有無のフラグに書き込まれる。変形角度βを推定するためのマスクについても。上記と同様の考え方で選択することとする。以上の処理を図１７の（ａ）と（ｂ）に適用した結果、両方ともα＾＝２５度、β＝０度と推定されたものとし、これを図２５の表にまとめて示す。
【００５４】
選択的投票手段３０は、候補文字の組合せに対して組み合わせ判定関数を適用し、合格したものだけを投票空間格納手段４０におくる。例として、図２５の表におけるＰＩＤ＝０の候補文字とＰＩＤ＝１の候補文字の組合せに対して適用した場合を説明する。組み合わせ判定関数は、従来技術と同様の組み合わせ判定関数（これを第１の判定関数と呼ぶ）に加えて、以下に説明する別種の組み合わせ判定関数（これを第２の判定関数と呼ぶ）を使用し、２つの判定関数の結果が両方とも「組み合わせ可」となった場合にだけ「組み合わせ可」とし、片方もしくは両方が「組み合わせ不可」となれば「組み合わせ不可」とする。
【００５５】
ここで、選択的投票手段３０は、候補文字絞込み手段１０によって絞り込まれた候補文字に対し、探索キー（探索文字列）の２つの文字要素を取り出して、文字要素と候補のカテゴリが一致する組み合わせを求める。そして、文字の方向（縦書き、横書き）や文字間隔から適切な候補の組み合わせだけを残す。この処理はあらゆる２つの文字要素について行う。この選択的投票手段３０の処理手順を示したのが図２６のフローチャートである。以下、図１４の入力データ配列を対象として動作を説明する。入力データ配列のレコード数をＫ個と置く。このフローチャートは、以下の表記を用いている。まず、入力データ配列のＫ個の点をＰ１、Ｐ２、・・・、ＰＫで表し、この集合をＰＧで表す。また、探索キーとされた文字列をＷ（長さＬ）とし、Ｗを構成する文字をＣ１、Ｃ２、・・・、ＣＬで表す。さらに、ｍ、ｎを自然数（１≦ｍ＜ｎ≦Ｌ）とする。
【００５６】
ここで、Ｗを「電話会社」としたとき（すなわちＣ１＝電、Ｃ２＝話、Ｃ３＝会、Ｃ４＝社、とする）、このフローチャートの中で、全てのｎとｍの可能な組み合わせにおいてＫ０とＫ１の処理（カテゴリ番号が一致する集合ＰＧＭ、ＰＧＮの作成処理）を図１４の入力データ配列に対して行い、各々を全ての組み合わせた結果を図２７に示す。図２７において、左側は集合ＰＧＭから抽出した要素、右側は集合ＰＧＮから抽出した要素である。ただし、各々の要素には、文字位置を表すｍ、ｎの数値を追加してある。このように、候補文字の情報に単語内の文字位置の情報を追加したデータを、以後「候補点」と呼ぶ。また、集合ＰＧＭから抽出した１個の「候補点」をＲ１、集合ＰＧＮから抽出した１個の「候補点」をＲ２と呼ぶ。また、図２７の各レコードには、説明のための通し番号が先頭に振ってある。
【００５７】
図２６のフローチャートのＫ２の処理では、これらの組み合わせに対して、（Ａ１）文字列の中心位置座標の配列を規定する４つのパラメータ値（ａ、ｂ、ｃ、ｄ）を算出する。そして、（Ｂ１）パラメータ値（ａ、ｂ、ｃ、ｄ）から、投票空間格納手段４０に登録するための座標ベクトル（Ｒａ、Ｒｂ、Ｒｃ、Ｒｄ）を算出する。次に、（Ｃ１）各々の候補点Ｒ１とＲ２の組み合わせの可否を判定する関数（第１の判定関数および第２の関数）を適用する。次に、（Ｄ１）第１の判定関数および第２の関数により合格と判定した組み合わせを投票空間格納手段４０に追加する。このような、（Ａ１）、（Ｂ１）、（Ｃ１）、（Ｄ１）の４つの処理を行なう。なお（Ｂ１）におけるＲａ、Ｒｂ、Ｒｃ、Ｒｄは、それぞれａ、ｂ、ｃ、ｄの概値として算出される値である。また、（Ｃ１）における「Ｒ１とＲ２」は、集合ＰＧＭから抽出した１個の「候補点」と、集合ＰＧＮから抽出した１個の「候補点」を意味する。以下、各々の処理を、例を用いて説明する。
【００５８】
（Ａ１）における４つのパラメータ値（ａ、ｂ、ｃ、ｄ）は、それぞれ以下の意味である。
ａ：仮想的な開始点のＸ座標
ｂ：仮想的な開始点のＹ座標
ｃ：仮想的なＸ方向のピッチ（仮想的ピッチベクトルのＸ成分）
ｄ：仮想的なＹ方向のピッチ（仮想的ピッチベクトルのＹ成分）
これらを説明する模式図を図２８に示す。これは図２７における番号＝１１、（ｍ、ｎ）＝（２、３）のレコードを用いた時の模式図である。このレコードには、集合ＰＧＭから取り出した候補点Ｒ１＝（カテゴリ＝話、Ｘ１＝１６０、Ｙ１＝１９０、窓の大きさ＝
５０、距離３７４、単語内文字位置＝２、ＰＩＤ＝９）と、集合ＰＧＮから取り出した候補点Ｒ２＝（カテゴリ＝会、Ｘ２＝２３０、Ｙ２＝１７０、窓の大きさ＝５０、距離＝４５０、単語内文字位置＝３、ＰＩＤ＝５）が存在する。ここで、Ｒ１の中心のＸ座標＝Ｘ１、中心のＹ座標＝Ｙ１、単語内文字位置＝ｉとし、Ｒ２の中心のＸ座標＝Ｘ２、中心のＹ座標＝Ｙ２、単語内文字位置＝ｊとすると、ａ、ｂ、ｃ、ｄは下式で計算される。
ｃ＝（Ｘ２−Ｘ１）／（ｊ−ｉ）
ｄ＝（Ｙ２−Ｙ１）／（ｊ−ｉ）
ａ＝Ｘ１−ｃ×（ｉ−１）
ｂ＝Ｙ１−ｄ×（ｉ−１）
図２７の各レコードに対して上記の式により（ａ、ｂ、ｃ、ｄ）を計算した結果を図２９に示す。
【００５９】
次に（Ｂ１）の処理であるが、ここでは（Ｒａ、Ｒｂ、Ｒｃ、Ｒｄ）を（ａ、ｂ、ｃ、ｄ）の値から算出する。本実施形態では、
Ｒａ＝ａ／Ｃａ  （Ｃａは定数）  小数点１位を四捨五入
Ｒｂ＝ｂ／Ｃｂ  （Ｃｂは定数）  小数点１位を四捨五入
Ｒｃ＝ｃ／Ｃｃ  （Ｃｃは定数）  小数点１位を四捨五入
Ｒｄ＝ｄ／Ｃｄ  （Ｃｄは定数）  小数点１位を四捨五入
の演算で算出する。Ｃａ、Ｃｂ、Ｃｃ、Ｃｄは例として、６０、６０、９０、９０を用いる。ここで、Ｃａ、Ｃｂ、Ｃｃ、Ｃｄはそれぞれ、ａ、ｂ、ｃ、ｄを概値にするための値であり、同一文字列上に存在する候補文字のペアができるだけ同一の（Ｒａ、Ｒｂ、Ｒｃ、Ｒｄ）ベクトルの値をとるように、かつ同一文字列上に存在しない候補文字のペアができるだけ同一の（Ｒａ、Ｒｂ、Ｒｃ、Ｒｄ）ベクトルの値をとらないような大きさに調整する。図２９に対してこの処理を行なった結果を図３０に示す。
【００６０】
次に（Ｃ１）の処理における第１の判定関数であるが、これは本実施形態ではまず、下記の３つの評価尺度を計算する。
・ｓ＝（Ｒ２の「大きさ」）÷（Ｒ１の「大きさ」）
・α＝仮想ピッチベクトルの角度（角度の取り方については図２２（ａ）を参照） 
・Ｐｓ＝(ｃ×ｃ＋ｄ×ｄ)0.5／{０.５×（Ｒ２の「大きさ」＋Ｒ１の「大きさ」）}
ここで、第１の判定関数は、
ｓ１＜ｓ＜ｓ２  かつ  α∈α１  かつ  Ｐｓ１＜ｐｓ＜Ｐｓ２
の条件を満足した時に「組み合わせ可」と判定し、満足しない時に「組み合わせ不可」と判定する。上式において、ｓ１とｓ２はｓの範囲を表す数値で、本実施形態ではｓ１＝０.８、ｓ２＝１.２を用いる。また、Ｐｓ１とＰｓ２はＰｓの範囲を表す数値で、本実施形態ではＰｓ１＝０.９、Ｐｓ２＝３.０を用いる。
【００６１】
また、α１は許容されるαの範囲である。本実施形態では、左から右に書かれた、多少傾きがあり得る文字列を読み取り対象としており、そのためにα１は図３１（ｂ）のように（この図における、太い円弧で示した角度の範囲が該当）、Ｘ軸のプラス方向に対して±２０度の範囲内とした。ただし、この範囲は読み取りを想定する文字列の角度によって設定すればよい。例えば、左から右方向だけでなく、上から下に並んだ文字列も許容しようとすれば、図３１（ｃ）のように、Ｙ軸のマイナス方向の周囲にも許容する角度の範囲を設ければよい。
【００６２】
上述の「ｓ」は、２つの候補文字の大きさの比を意味する。同一文字列上に存在する候補文字は、通常は大きさが近いはずであり、この「ｓ」の範囲を限定することで候補文字の組み合わせを絞込むことができる。
Ｐｓは、Ｒ１の「大きさ」とＲ２の「大きさ」の平均値に対する、Ｒ１とＲ２から算出されるピッチの大きさの相対値であり、一般的な文字列はこの大きさに範囲があるので、この範囲を限定することで候補文字の組み合わせを絞込むことができる。
【００６３】
図３０の結果に対して、上述の（Ｃ１）の処理を施し、第１の判定関数による判定を行った結果が図３２である。ここで、各レコードにおけるｓ、α、Ｐｓの欄に書かれた数値が算出された値であり、「判定結果」が「×」となっているのが第１の判定関数により「組み合わせ不可」となったレコードである。３つの評価尺の中で１個でも「組み合わせ不可」となった場合には、「判定結果」が「×」となっており、これが組み合わせ判定関数の判定結果（この場合には「組み合わせ不可」）である。また「○」は３つの評価尺が全て「組み合わせ可」となり、組み合わせ判定関数が「組み合わせ可」と判定した結果である。
【００６４】
ここで、第１の判定関数においては、上記の３つの条件に加えて、「Ｒ１とＲ２の距離値の合計が一定閾値以内」という判定を用いることも可能である。例えば、図３２の中のｍ＝１、ｎ＝２の表において、番号＝３の行におけるＲ１とＲ２の組み合わせは、集合ＰＧＭから取り出した要素の「正誤」の欄が「０」となっている（すなわち、誤った候補文字）にもかかわらず、判定結果は「○」となってしまい、誤った投票が行われてしまっている。これに対して、判定条件にさらに「Ｒ１とＲ２の距離値の合計が一定閾値（ここでは例として「９００」を用いる）以内であること」という判定条件を論理的な積として追加すると、番号＝３の行のＲ１とＲ２の組み合わせにおける両者の距離値の合計は「９２４」であるため、この判定条件を満足せず、判定結果は「×」となり、誤った投票を防ぐことができる。これに対して、それ以外の正しい組み合わせ、すなわち、図３２の全ての表における、集合ＰＧＭから取り出した要素と集合ＰＧＮから取り出した要素の「正誤」の欄が両方とも「１」となっている組み合わせでは、両者の距離値の合計はいずれも「９００」を下回るので、上記の新たな判定条件を満足するため、これらの正しい投票は妨げられない。
【００６５】
このような第１の判定関数に加えて、第２の判定関数は、以下に説明する条件（１）〜（４）を満足した時に「組み合わせ可」と判定し、満足しない時に「組み合わせ不可」と判定する。本実施例では文字列が横書きの場合を述べるが、縦書きの文字列の場合も同様に実施できる。４つの条件の説明のため、２個の候補文字をそれぞれ「第１の候補文字」、「第２の候補文字」と呼ぶ。原画像におけるこれら２個の候補文字と各値の関係の模式図を図３３に示した。図３３では、α１、β１、α２、β２の各値はすべて変形角度の推定結果である。これに対して、Ｕ１、Ｕ２、Ｖ１、Ｖ２は、上記の変形角度と対をなす水平軸と垂直軸を表すベクトルを意味する。また、原画像における第１の候補文字と第２の候補文字の中心を通る直線を算出し、これをＬで表す。さらに、ＬとベクトルＵ１、Ｕ２がなす角度を算出して、これをθ１、θ２で表すこととする。以上の各値が用意できたことを前提としたとき、第１の候補文字と第２の候補文字との組合せを「可」とする判定条件を、以下の４個の条件の論理積で表す。
【００６６】
条件（１）：｜α＾１−α＾２}|＜Ｔｈａ１
条件（２）：｜β１−β２|＜Ｔｈａ１
条件（３）：｜θ１|＜Ｔｈａ２
条件（４）：｜θ２|＜Ｔｈａ２
【００６７】
さて、既に説明したように第１の候補文字と第２の候補文字の文字カテゴリによっては、α＾１、β１、α＾２、β２の一部もしくは全部が算出できていない可能性があるが、その場合は上記の４つの条件の論理積の中から、該当する条件を削除して用いる。例としてβ１が算出されていないときは、条件（２）を論理積の中から削除する。また、α＾２が算出できない場合には条件（１）を削除する。またα＾２が算出できていなければθ２も算出できないので、条件（４）も削除することとなる。
【００６８】
以上の条件（１）〜（４）を、図２５の表におけるＰＩＤ＝０の候補文字とＰＩＤ＝１の候補文字の組合せに対して適用する。まず、Ｔｈａ１＝１０度、Ｔｈａ２＝１０度とする。ここで、仮想ピッチベクトルの角度αは既に−４．７６度と算出されている。α＾１＝α＾２＝２５度、β１＝β２＝０度と既に推定されている。従って、θ１＝α＾１−α＝２５度−（−４．７６度）＝２９．７６度、同様にθ２＝α＾２−α＝２５度−（−４．７６度）＝２９．７６度である。これにより条件１〜４を判定すると、
条件（１）：｜２５度−２５度｜＜１０度  であり、合格
条件（２）：｜０度−０度｜＜１０度  であり、合格
条件（３）：｜２９．７６度｜＞１０度  であり、不合格
条件（４）：｜２９．７６度｜＞１０度  であり、不合格
となり、条件（３）と条件（４）が「不合格」のため、第２の判定関数は「組み合わせ不可」となる。このため、選択的投票手段３０において、図２５の表におけるＰＩＤ＝０の候補文字とＰＩＤ＝１の候補文字の組合せに対する組み合わせ判定関数の結果は「組み合わせ不可」となり、この組合せは後述する投票空間格納手段４０には送られない。結果として以後の処理も行われず、探索キー「土田」に対する謝った検索は行われないこととなる。
【００６９】
次に（Ｄ１）の処理であるが、ここでは第１の判定関数および第２の判定関数により合格と判定した組み合わせを投票空間格納手段４０に追加する。図３２の結果において、組み合わせ判定関数の判定結果が「組み合わせ可」（図３２では「○」）となったレコードだけを集めたものが図３４である。
【００７０】
投票空間格納手段４０は、２つの候補の組み合わせを、さらに組み合わせて整合するものを選択する。つまり、始点位置の概数（Ｒａ、Ｒｂ）とピッチの概数（Ｒｃ、Ｒｄ）が一致すれば整合すると判定する。投票空間格納手段４０は、２個の候補点Ｒ１とＲ２の情報と、該２個の候補点の、探索を指定された文字列内の文字位置の情報と、ピッチが一定でかつ直線的に並ぶ文字列を特定するパラメータの組の情報とから構成されるレコードである投票レコードを複数格納する投票レコード格納手段と、該手段の中で該パラメータの組を持つ投票レコードが格納されているアドレスを示すインデクスを全て格納するインデクス格納手段とを有している。何も情報が登録されていない状態の投票空間格納手段４０の実現例を図３５に示す。（Ｄ１）の処理では、次の（Ｄ１−１）から（Ｄ１−５）の処理を行なう。
【００７１】
（Ｄ１−１）図３４に示す組み合わせ判定関数の判定結果が「組み合わせ可」（図３２では「○」)となったレコードを１個ずつ取り出す。
（Ｄ１−２）そのレコードの情報を投票レコード格納手段のまだ書き込まれていない最末端のレコードのエリアに書き込む。
（Ｄ１−３）この書き込んだ投票レコード格納手段のレコードのアドレスを一時保存する。
（Ｄ１−４）（Ｄ１−３）で書き込んだレコードの（Ｒｃ、Ｒｄ、Ｒａ、Ｒｂ）を調べ、これを（Ｒｃ０、Ｒｄ０、Ｒａ０、Ｒｂ０）とする。
（Ｄ１−５）投票空間格納手段４０のインデクス格納手段における（Ｄ１−４）で調べた（Ｒｃ０、Ｒｄ０、Ｒａ０、Ｒｂ０）を持つレコードにアクセスし、該レコードの「投票数」を＋１し、該レコードの「アドレス格納部」に、（Ｄ１−３）で一時保存した投票レコード格納手段のレコードのアドレスを追加する。
以上の処理（Ｄ１）を図３４のデータ全てに対して行なった結果の投票空間格納手段４０のデータを図３６に示す。
【００７２】
上記の（Ｄ１−５）の代わりに、次の（Ｄ１−５０）を行なう方法もある。すなわち、（Ｄ１−５０）投票空間格納手段４０のインデクス格納手段における（Ｄ１−４）で調べた（Ｒｃ０、Ｒｄ０、Ｒａ０、Ｒｂ０）を持つレコード、および（Ｒｃ０、Ｒｄ０、Ｒａ０、Ｒｂ０）の近傍の（Ｒｃ、Ｒｄ、Ｒａ、Ｒｂ）を持つレコードにアクセスし、それらのレコードの「投票数」を＋１し、かつ「アドレス格納部」に、（Ｄ１−３）で一時保存した投票レコード格納手段のレコードのアドレスを追加する。ここで、（Ｒｃ０、Ｒｄ０、Ｒａ０、Ｒｂ０）の近傍の（Ｒｃ、Ｒｄ、Ｒａ、Ｒｂ）とは、Ｒｃ０、Ｒｄ０、Ｒａ０、Ｒｂ０の一部ないし全てに一定範囲に含まれる整数（例えば−１から１までの整数）を加えたものである。例えば、Ｒｃ０とＲｄ０の一方だけに−１から＋１の整数を加えることとした場合、（Ｒｃ０、Ｒｄ０、Ｒａ０、Ｒｂ０）＝（１、０、１、２）の近傍の（Ｒｃ、Ｒｄ、Ｒａ、Ｒｂ）は、（０、０、１、２）、（２、０、１、２）、（１、−１、１、２）、（１、１、１、２）の４個となる。
【００７３】
図３６は（Ｄ１−５）を用いた処理の結果であり、（Ｒｃ０、Ｒｄ０、Ｒａ０、Ｒｂ０）＝（１、０、１、２）のレコードに正しい組み合わせの多くが集まっているが、（Ｂ１）の処理で用いるＣａ、Ｃｂ、Ｃｃ、Ｃｄの値がさらに小さく設定されている場合には、接近した複数の（Ｒｃ、Ｒｄ、Ｒａ、Ｒｂ）に分かれてしまう可能性があり、それが原因で「投票数」が小さくなり、候補点群作成手段４の処理で正しくレコードが抽出されない危険がある。これに対して、例えば正しい組み合わせが（１、０、１、２）と（０、０、１、２）の２つ分かれたとしても、例えば、Ｒｃ０とＲｄ０の一方だけに−１から＋１の整数を加えるとしておけば、それぞれ
・（１、０、１、２）、（０、０、１、２）、（２、０、１、２）、（１、−１、１、２）、（１、１、１、２）
・（０、０、１、２）、（−１、０、１、２）、（１、０、１、２）（０、−１、１、２）、（０、１、１、２）
に投票し、（０、０、１、２）と（１、０、１、２）の（Ｒｃ、Ｒｄ、Ｒａ、Ｒｂ）を持つインデクスには、正しい組み合わせのレコードの「アドレス格納部」のアドレスが全て書き込まれることとなる。
【００７４】
候補点群作成手段５０は、投票空間格納手段４０による投票処理が行われた後の処理を行う。候補点群作成手段５０は、探索キー（探索文字列）の文字数により、投票空間格納手段４０の処理によって所定文字数以上の固まりになったものを選択する。ここで、候補点群作成手段５０は、まず、投票空間格納手段４０におけるインデクス格納手段の中から、投票数が探索キーとして指定された文字列の長さ別に設定された閾値を越えるインデクスを全て抽出する。この「投票数が探索キーとして指定された文字列の長さ別の閾値の設定方法」には様々な方法が考えられるが、本実施形態では、下記のように設定する。まず、探索キーとして指定された文字列の中で、何文字の欠落まで許容するかを文字列の長さ毎に人手で設定する。本実施形態では、
【００７５】
単語長＝１は扱わない。
単語長＝２の場合：許容する最大欠落文字数＝０
単語長＝３の場合：許容する最大欠落文字数＝０
単語長＝４の場合：許容する最大欠落文字数＝１
単語長＝５の場合：許容する最大欠落文字数＝１
単語長＝６の場合：許容する最大欠落文字数＝２
単語長＝７の場合：許容する最大欠落文字数＝２
単語長≧８の場合：許容する最大欠落文字数＝単語長×一定数（例：０.２）を小数点１位切り上げ（例えば単語長＝８では、８×０.２＝１.６→２）
とする。
【００７６】
これに対して、「投票数が探索キーとして指定された文字列の長さ別の閾値」は、
（単語長−許容する最大欠落文字数）×（単語長−許容する最大欠落文字数−１）÷２
で計算する。すると、本実施形態における「電話会社」の単語長は４なので、閾値は「３」となる。すなわち、インデクス格納手段の中から「投票数」が３以上のインデクスを残らず抽出する。この場合、図３６のインデクス格納手段において「投票数」が３以上のインデクスは、（Ｒｃ、Ｒｄ、Ｒａ、Ｒｂ）＝（１、０、１、２）のレコードだけでありこれが抽出される。
【００７７】
次に、抽出されたインデクスに対して、該インデクスから手繰られる全てのレコード格納手段中の投票レコードを抽出し、それらに含まれる全ての候補点の情報および該候補文字の、探索を指定された文字列内の文字位置の情報を探索してそれらのリストである候補文字・文字位置リストを作成する。
図３４の（Ｒｃ、Ｒｄ、Ｒａ、Ｒｂ）＝（１、０、１、２）のインデクスのアドレス格納部の格納されたアドレスは、（１、３、４、５、７、９、１０、１１）であり、これらに該当する投票レコード格納手段のレコードを全て抽出した結果（候補文字・文字位置リスト）を図３７に示す。図３７にあるように、候補文字・文字位置リストには、全レコードのａ、ｂ、ｃ、ｄの平均値を格納するエリアも末端部に付属している。ただし、図３７ではまだ書き込まれていない。
【００７８】
次に、候補点群作成手段５０は、全レコードのａの平均値を求め、次いで全レコードのｂの平均値を求め、次いで全レコードのｃの平均値を求め、次いで全レコードのｄの平均値を求め、各々の平均値を候補文字・文字位置リストの末端部の全レコードのａ、ｂ、ｃ、ｄの平均値を格納するエリアに書き込む。その結果が図３８である。
この例では、ｃ、ｄ、ａ、ｂの平均値は各々７４.４、−１０、８１.３、１９５となっている。次に、候補文字・文字位置リストに含まれる全てのＲ１とＲ２を抜き出し、リス
ト化する。これを候補点群リストと呼ぶ。図３８から作成した候補点群リストを図３９（ａ）に示す。
【００７９】
候補点選択手段６０は、候補点群作成手段５０による処理が行われた後の処理を行う。候補点選択手段６０は、候補点で重複するものは除いて、最後は候補の座標位置から１つに絞り込む。
図３９（ａ）から分かるように、候補点群作成手段５０の処理結果には多くの候補点が重複して含まれているので、候補点選択手段６０はまずこの重複を排除する処理を行なう。そのためにまず、候補点群リストを、ＰＩＤの小さい順に（ＰＩＤが等しい場合には「文字位置」の小さい順に）ソートする。この結果を図３９（ｂ）に示す。次に、候補点群リストのレコードを上位側から１個ずつ選び、自分自身のＰＩＤと文字位置の値が１つ下位のレコードのＰＩＤと文字位置の値と両方とも一致するか否かを調べ、一致していれば自分の「大きさ」の値に−１を記入する。この処理を逐次的に、下から２番目のレコードまで行なう。これを図３９（ｂ）に対して行なった結果が図３９（ｃ）である。次に、図３９（ｃ）に示す結果から、「大きさ」が−１のレコードを削除すると、図３９（ｄ）の結果となる。この結果を画像に重畳した表示したのが図４０である。この時点でまだ、文字位置＝１の候補点が２個残っていることが分かる。この中から正しい候補点を選択するために、候補点選択手段６０は以下の処理を行なう。
【００８０】
まず、候補文字・文字位置リストに付属している全レコードのａ、ｂ、ｃ、ｄの平均値を格納するエリアから、ｃ、ｄ、ａ、ｂの平均値を取り出す。これを各々、ｃ０、ｄ０、ａ０、ｂ０と表記する。本実施形態での値は図３８から分かるように各々、７４.４、−１０、８１.３、１９５となる。
次に、このｃ０、ｄ０、ａ０、ｂ０の値から算出される仮想的な文字位置の中心座標を、複数の候補点が存在している文字位置について算出する（この場合には文字位置＝１）。文字位置ｉの仮想的な中心座標を（Ｘｅｉ、Ｙｅｉ）と表記すると、
Ｘｅｉ＝ａ０＋ｃ０（ｉ−１）、Ｙｅｉ＝ｂ０＋ｄ０（ｉ−１）
で計算する。従って、ｉ＝１の場合には、Ｘｅｉ＝８１.３、Ｙｅｉ＝１９５となる。
【００８１】
次に、複数の候補点が存在している文字位置について、各々の候補点の実際の中心座標と上記で計算された仮想的な中心座標のユークリッド距離を計算する。この実施形態での計算結果を図３９（ｅ）に示す。そして、この距離が最も小さい候補点を選択する。図３９（ｅ）では、ＰＩＤ＝１のレコードがこの（Ｘｅｉ、Ｙｅｉ）との距離が最も小さいので、このレコードが正しく選ばれる。そして、ここで選択されなかったレコードは、すべて候補点群リストから削除する（図３９（ｅ）ではＰＩＤ＝２のレコード）。図３９（ｄ）に対して、このＰＩＤ＝２のレコードを削除した結果が図４１（ａ）であり、これを原画像上に重畳表示したのが図４１（ｂ）である。
【００８２】
なお、特許文献２には実施形態を用いた応用例として、多くの画像を蓄積し、検索する画像データベースシステムにおいて、画像中に写った文字列をキーワードとして画像の検索が可能な検索技術の記述があるが、本発明の実施例でも、同様の応用が可能である。また、画像に付与されるキーワードは単語辞書に含まれる単語に限定されるため、単語辞書に含まれない単語が画像中に存在している場合に従来技術で想定されているように画像検索における文字列間照合として完全一致を用いたのでは画像の検索に失敗する確率が高くなってしまう。そこで、以下のように部分一致を基本とする処理とすることで未登録語による影響をできる限り低減することが可能となる。
【００８３】
ユーザーが投入する検索文字列をＱ、データベースに格納されている画像の枚数をＭ、各画像をＩｉ（１≦ｉ≦Ｍ）、Ｉｉのキーワードの集合をＤｉと表記する。ここで、Ｑに対する画像Ｉｉのスコアを以下の方法で計算を行う。最初に、Ｑの文字数分だけビットを並べたビット列を作成しＳで表す。初期の状態では、Ｓを構成するビットには全部０を代入する。たとえばＱを「駅周辺商店街」とすると、６文字なので初期ではＳ＝［００００００］となる。そして、Ｄｉに含まれる任意の単語をＷで表すと、Ｑに含まれる文字とＷの２文字以上とが連続して部分一致する文字列の箇所を探索し、検出できた場合には、Ｓの該当するビットに１を代入する。
【００８４】
この処理では文字位置を変えつつ探すので、文字位置は異なっていても良い。たとえばＷを「商店主」とすると、ＱがＷと２文字以上部分一致する箇所は「商店」の２文字であり、これによりＳは［０００１１０］にセットされる。また、他の単語として「周辺」があったとすると、Ｑの２文字目と３文字目に連続して部分一致するので、Ｓは［０１１１１０］にセットされる。この処理をＤｉに含まれる全単語に対して行い、その後でＳに含まれる１のビットの個数をカウントしてＱへのＩｉのスコアとして設定する。上記の例ではＳ＝［０１１１１０］から４がスコアとなる。上記の方法は文字列の部分一致を基本とするので、Ｑと同じ文字列が単語として単語辞書に登録されていなくても、Ｑと部分的に文字列が一致する単語が登録されていれば検索できる可能性が生じる。以上のＱによる画像へのスコア付けの処理をＩｉ（１≦ｉ≦Ｍ）のすべてに対して行った後、スコアの大きさにより画像を並べ替え、最大値のスコアを有する画像を最終的な検索結果として出力する。最大値のスコアを持つ画像が複数ある場合には、それらを全部出力する。
【００８５】
以上、詳細に説明したように、本実施形態によれば、文字列探索の際に、探索キーとされた長さＬの文字列から、該文字列の前から後の方向に存在する全ての２個の文字の組である文字ペアを選び、各々の文字ペアに対して、候補文字集合中から文字カテゴリが一致する全ての２個の候補文字の組を探索する処理を行い、該処理の結果探索された全ての２個の候補文字の組に対して、ピッチが一定でかつ直線的に並ぶ文字列を特定するパラメータの組を算出する際に、候補文字パターンの変形角度を推定しその結果に基づく判定処理を行って合格した場合にだけ該２個の候補文字の組と該パラメータの組の情報を投票空間に投票するようにしたので、従来技術に比べて文字が存在しない領域に対して文字列探索が誤って成功することを抑制できる。
【００８６】
なお、本発明における処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより文字列探索を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００８７】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【符号の説明】
【００８８】
１０  候補文字絞込み手段
１１  単一解像度候補文字絞込み手段
１２  複数解像度候補文字絞込み手段
２０  変形角度推定手段
２１  制御手段
２２  マスクテーブル
２３  角度算出手段
２４  マスク生成手段
３０  選択的投票手段
４０  投票空間格納手段
５０  候補点群作成手段
６０  候補点選択手段
【図１】
0005414631.tif 000002
【図２】
0005414631.tif 000003
【図３】
0005414631.tif 000004
【図４】
0005414631.tif 000005
【図５】
0005414631.tif 000006
【図６】
0005414631.tif 000007
【図７】
0005414631.tif 000008
【図８】
0005414631.tif 000009
【図９】
0005414631.tif 000010
【図１０】
0005414631.tif 000011
【図１１】
0005414631.tif 000012
【図１２】
0005414631.tif 000013
【図１３】
0005414631.tif 000014
【図１４】
0005414631.tif 000015
【図１５】
0005414631.tif 000016
【図１６】
0005414631.tif 000017
【図１７】
0005414631.tif 000018
【図１８】
0005414631.tif 000019
【図１９】
0005414631.tif 000020
【図２０】
0005414631.tif 000021
【図２１】
0005414631.tif 000022
【図２２】
0005414631.tif 000023
【図２３】
0005414631.tif 000024
【図２４】
0005414631.tif 000025
【図２５】
0005414631.tif 000026
【図２６】
0005414631.tif 000027
【図２７】
0005414631.tif 000028
【図２８】
0005414631.tif 000029
【図２９】
0005414631.tif 000030
【図３０】
0005414631.tif 000031
【図３１】
0005414631.tif 000032
【図３２】
0005414631.tif 000033
【図３３】
0005414631.tif 000034
【図３４】
0005414631.tif 000035
【図３５】
0005414631.tif 000036
【図３６】
0005414631.tif 000037
【図３７】
0005414631.tif 000038
【図３８】
0005414631.tif 000039
【図３９】
0005414631.tif 000040
【図４０】
0005414631.tif 000041
【図４１】
0005414631.tif 000042
【図４２】
0005414631.tif 000043
【図４３】
0005414631.tif 000044
【図４４】
0005414631.tif 000045
【図４５】
0005414631.tif 000046