JP4649512B2 - 文字列検索方法およびその装置 - Google Patents

Description

本発明は、文字コードや手書きストロークから構成される文字列の検索の方法及びその装置に関する。

書類に記載された文章など検索対象の文字列から、ユーザ等によって指定された文字列（パターン）あるいは検索キーを見つけ出す処理が文字列検索である。文字列検索で用いられる文字列の表現形式は、ＳＪＩＳやＵｎｉｃｏｄｅなどの規格にそった文字コードの列からなる文字列が一般的である。近年、画面上でのペンの動きをスキャンできるタッチパネルの普及や、紙面上に記入したストロークを取得できるデジタルペン（例えば、国際公開第０１／７１４７３号公報参照）によって、手書きの文字列を容易に電子化できるようになってきた。従って、検索対象やパターン文字列（検索キー）が手書きのストロークの形式で表現された場合での文字列検索の方法が必要となってきた。
文字列検索の方法として、特開２００５−２５１２２２号公報には、文字列ストロークを構成するサンプリング点列同士を動的計画法で照合する方法１が開示されている。
また、特開平１０−０５５４０９号公報には、ストロークを線方向特徴等から細かなセグメントの列に変換し、セグメント列同士を照合する方法２が開示されている。
さらに、特開２００２−２５９９１２号公報には、文字列を構成するストローク集合から文字を構成する可能性があるストロークの部分集合（文字切り出し候補）を切り出し、各文字切り出し候補の形状から相応しい文字コードを識別する文字識別手段を用いて、文字切り出し候補と文字識別候補の組の列からなる候補文字ラティスを作成し、照合する方法３が開示されている。

しかし、特開２００５−２５１２２２号公報に開示された従来の方法１と特開平１０−０５５４０９号公報に開示された従来の方法２は、ストロークのサンプリング点の順序に依存するため、同じ字形でも書き順が異なると照合が困難になる問題があった。また検索対象とキーワードの手書き文字列が異なる利用者によって記入された場合、検索精度が低下する問題があった。さらにこれらの方法は、ストロークベースの検索であるため、検索対象又はパターンの文字列が手書きストロークではなく文字コードで表現されていた場合、検索できない問題があった。
また、特開２００２−２５９９１２号公報に開示された従来の方法３では、文字切り出し候補や文字識別候補がいつも正しいとは限らず、文字切り出し候補や文字識別候補に誤りが含まれる場合は正しく文字列が検索できない問題があった。
本発明は、このような問題に鑑みてなされたものである。
すなわち、本発明の目的は、検索対象とパターンとで記入者や書き順が異なる場合でも適用可能な文字列検索方法を提供することである。
また、本発明の目的は、文字切り出し候補や文字識別候補に誤りが存在してもそれらを許容する文字列検索方法を提供することである。
さらに、本発明の目的は、検索対象とパターンの文字列の表現形式として文字コードと手書きストロークの任意の組合せを許容する文字列検索方法を提供することである。
前述した課題を解決するために本願で開示する代表的な発明は以下の通りである。
利用者からの検索すべき文字列を文字コードと手書きストロークとの２種類のいずれか又は両方の表現形式で受け取るパターン文字列入力部と、文字コードと手書きストロークとの２種類のいずれか又は両方の表現形式からなる文字列を有する書類の情報を管理する書類管理部と、検索対象となる書類中の文字列と入力された検索すべき文字列を共に文字切り出しグラフに変換し、文字切り出しグラフ同士を照合することによってパターン文字列が検索対象の文字列に出現する箇所を抽出する文字列照合部と、書類又は文字列検索結果を表示する表示部と、を有する文字列検索システム。
本発明によって、利用者は書類中から探し出したい文字列を高精度に見つけることができる。また自分自身以外の書込みも見つけ出すことができる。さらに、文字コードや手書きストロークの区別なく書類中の全文字列を検索できる効果がある。

図１は、本発明の実施の形態の文字列検索システムの構成図である。
図２は、本発明の実施の形態で実現可能な文字列検索の種類を示す図である。
図３は、本発明の実施の形態で対象となる書類の１例を示す図である。
図４Ａ及び図４Ｂは、本発明の実施の形態の検索対象とパターン各々の文字切り出しグラフを示す図である。
図５は、本発明の実施の形態の文字切り出しグラフ照合の手法を説明する図である。
図６Ａ及び図６Ｂは、本発明の実施の形態の文字コード情報のデータ構造を示す図である。
図７Ａ及び図７Ｂは、本発明の実施の形態のストローク情報のデータ構造を示す図である。
図８は、本発明の実施の形態の書類情報のデータ構造を示す図である。
図９Ａから図９Ｄは、本発明の実施の形態の文字切り出しグラフのデータ構造を示す図である。
図１０は、本発明の実施の形態の文字列検索結果のデータ構造を示す図である。
図１１は、本発明の実施の形態の文字列検索候補のデータ構造を示す図である。
図１２は、本発明の実施の形態の前処理の説明図である。
図１３は、本発明の実施の形態の文字切り出し作成処理の説明図である。
図１４は、本発明の実施の形態の文字列検索処理の説明図である。
図１５は、本発明の実施の形態の文字切り出しグラフ照合処理の説明図である。

最初に本発明の文字列検索システムの構成例を示す。次に文字列検索システムで管理される書類情報中から利用者が指示したパターン文字列を見つけ出す文字列検索処理フローを説明する。
本発明の文字列検索システムは、図１に示すように、以下の部分から構成される。文字列検索装置１００が有するパターン文字列入力部１０１は、文字列検索で探すべき文字列（パターン文字列）を入力するために、キーボード又はデジタルペン１０５などと接続可能な入力インタフェースである。書類管理部１０２は、ハードディスク等の記憶部と、記憶部の読み出しや書き込みを制御する制御部によって実現され、文字コードとペンなどで記入されたストロークの情報からなる書類を管理する。
文字列照合部１０３は、記憶部に記憶される各プログラムモジュールを演算部で実行することによって、書類中にパターン文字列が出現する箇所を見つけ出し、記憶部に格納された書類やパターン文字列入力部から入力される文字列から文字切り出しグラフを生成したり、照合を行ったりする手順を実現する。書類や文字列検索結果の表示は表示部１０４によって行なわれる。
パターン文字列入力部１０１では、キーボード入力などによる文字コード形式、デジタルペンやタッチパネル入力などによるストローク形式の２種類の表現形式のいずれかでパターン文字列を受け取る。
書類管理部１０２では、各書類情報を図８の表８００に示したデータ構造で管理する。項目８０１は、書類情報を同定するためのＩＤである。項目８０２、８０３は、それぞれ書類中に含まれる文字コードの総数、ストロークの総数を示している。項目８０５及び８０６〜８０７は、書類に含まれる各文字コードのＩＤが格納されている。項目８０８及び８０９〜８１０は、書類に含まれる各ストロークのＩＤが格納されている。さらに、書類では、後に説明する図１２に示した前処理によって書類中のストロークから作成された文字切り出しグラフ（例えば、図４Ａ及び図４Ｂ）を有している。項目８０４は、書類中に含まれる文字切り出しグラフの総数を示している。項目８１１及び８１２〜８１３は、書類に含まれる各文字切り出しグラフのＩＤが格納されている。文字コード、ストローク及び文字切り出しグラフの各データ構造については後に説明する。
文字列照合部１０３では、入力されたパターン文字列と書類中の文字列とを比較する。文字列の比較は、図５と図１４を用いて後に詳細に説明する。
表示部１０４では、利用者に対して書類管理部で蓄積された書類や、文字列検索結果などをモニタ画面等に表示する。書類を紙等に印刷しても構わない。
本発明で取扱う書類の例を図３に示す。本例の書類３００は、文字コードからなる文字列３０１と、ペン３１０でそれぞれ記入されたストローク３０２及び３０３からなる。本実施形態では、ストロークの取得手段として国際公開第０１／７１４７３号公報に開示されたデジタルペンを用いることとする。デジタルペンによって、紙面上に記載されたストロークを電子化できる。
ここでストローク３０３について考える。ストロークの前半部分の解釈として、まず先頭の文字を「＃（シャープ）」とみなすか、「井（漢字の井戸の井）」とみなすかの２つの解釈がありえる。また先頭文字を「＃（シャープ）」をみなした場合は、＃後の文字列は数字とみなせる。この解釈にも「７」１桁なのか、「１７」２桁なのかの解釈がありえる。また先頭文字を「井（漢字の井戸の井）」とみなした場合は、続く文字は漢字やかな文字であろうと推測すると、二文字目は「口（くち）」と解釈できる。
このように、（１）＃７、（２）＃１７、（３）井口などの解釈が成り立ち、この部分を見ただけでは人間でも判別不能である。このように文字認識には不完全性が存在する。従って、手書き文字列を文字認識して一旦文字コード列に変換して、文字列照合する方法では、高精度に手書き文字列を検索できない問題がある。
文字コードの情報は図６Ｂの表６００に示したデータ構造で保持される。例えば、図６Ａの書類６５０上の文字コード６５１「エ」は、項目６０１〜６０７に記載された情報によって表される。
項目６０１は、その文字コードを同定するＩＤである。項目６０２は、文字コードの値を示す。項目６０３〜６０７は文字の属性情報であり、項目６０３と６０４は、それぞれ文字矩形の左上点の書類上の座標をミリメートル単位で示している。項目６０５はフォントの種類を、項目６０６はフォントサイズを、項目６０７は斜体や太字などのスタイルを示している。
ストロークの情報は図７Ｂの表７００に示されるデータ構造で保持される。例えば、図７Ａに示す書類７５０上のストローク７５１は、項目７０１〜７０４に記載された情報によって表される。項目７０１は、そのストロークを同定するＩＤである。項目７０２は、ストロークの記入開始時刻を示す。
項目７０３は、ストローク内に存在するサンプリング点数を示す。各サンプリング点の情報は表７３０に保持されている。項目７０４は、そのストロークに該当のサンプリング点集合の先頭を指すポインタを示す。各サンプリング点は書類上のＸＹ座標値７３１，７３２を有し、またサンプリング点の記入時刻と項目７０２に記載されたストローク記入開始時刻との差分を７３３に保持する。その他のそれぞれのストロークについても、表７１０、７２０のようなデータ構造で情報が保持される。また、デジタルペン以外の入力装置によって手書き文字が入力された場合でも、ストロークごとに分解してストロークＩＤ、サンプリング点数、ポインタ、座標を保持する表７３０によってストローク情報を管理することが可能である。
文字列検索システム１００は検索対象となる書類の入力時に、図１２に示す前処理を実行する。ステップ１２０２で書類を入力する。入力書類中のストローク情報を取得し（ステップ１２０３）、ステップ１２０４のストロークレイアウト解析処理によって、書類中のストローク集合を図や文字列単位に分割する。例えば、図３の書類３００上のストロークを、丸囲みと吹出し線を構成するストローク集合３０２と注釈文字列を構成するストローク集合３０３に分割する。
次に、分割されたストローク集合毎にステップ１２０５を実行し、文字切り出しグラフを得る。文字切り出しグラフとは、正しい文字の切り出しを一意に決定することが難しいことから、可能性のある文字切り出しの複数の仮説を一つの有向非循環グラフで表したものである。
例えば、図４Ａの４１１、４１２と４１３の部分は、ストローク４０１の右側部分の解釈が１文字と２文字の両方が考えられる。１文字としての解釈結果を表した４１１と、２文字としての解釈結果を表した２つのエッジ４１２、４１３の両方をグラフ４１０が有すことによって、それら多重の仮説を表現できる。得られた文字切り出しグラフを図９Ｂ〜図９Ｄに示したデータ構造で書類管理部１０２に保存し、その文字切り出しグラフＩＤを書類のデータ構造８００の項目８１１及び８１２〜８１３に格納する。
文字切り出しグラフのデータ構造を図９Ｄの表９００に示す。ここでグラフ９５０に示した文字切り出しグラフの場合を説明する。項目９０１は、文字切り出しグラフを同定するＩＤである。項目９０２は、その文字切り出しグラフが記載される書類のＩＤを示す。項目９０３及び９０４は、それぞれ文字切り出しグラフのノードとエッジの総数を示す。項目９０５〜９０８は、第１番目のエッジの情報を示しており、項目９０５はエッジの開始ノードの番号、項目９０６はエッジの終点ノードの番号を示す。各エッジは、ストローク集合からなる文字切り出し候補とその文字切り出し候補に対する文字識別候補を有し、項目９０７及び９０８は、それぞれのＩＤを示す。このようなエッジの情報が項目９０４に記載された数だけ繰返し表現される。
文字切り出し候補のデータ構造は表９２０に示すとおりである。項目９２１は、その文字切り出し候補を同定するＩＤを示す。項目９２２は、文字切り出し候補に含まれるストロークの本数を示す。項目９２３〜９２４は、文字候補に含まれる各ストロークのＩＤを示す。
文字識別候補のデータ構造は表９３０に示すとおりである。項目９３１は、その文字識別候補を同定するＩＤを示す。項目９３１は文字識別処理によって出力された文字識別結果の数を示す。項目９３３、９３４は第１位の文字識別結果を示す。項目９３３は文字識別された文字コードを示す。項目９３４はその時の類似度を示す。本例の場合、第１位は「＃（シャープ）」であり、第２位は類似度０．０２の僅差で漢字の「井」となっている。
図１２のステップ１２０５に示した文字切り出しグラフを作成する処理について、図１３を使って詳細に説明する。ステップ１３０２において、該当ストローク集合を入力後、ステップ１３０３でストローク集合を、文字を構成すると考え得る部分集合に切り出す。この作業は文字切り出しグラフのエッジの文字切り出し候補を作成することに等しい。
このとき、切り出しを一意に確定するのが困難な場合がある。例えば、図４Ａの書類４００上のストローク集合４０１の右側の部分が、「７」１文字なのか、「１」と「７」の２文字なのか判断が困難な場合がある。このような場合、エッジ４１１と、エッジ４１２と４１３の組とを作成することによって、「７」１文字と、「１」「７」２文字との両方の解釈を一つの切り出しグラフで同時に表現できる。従って文字切り出しグラフを使用することによって、文字切り出しの不完全性を許容した文字列検索が可能となる。
次のステップ１３０４で各文字切り出し候補のストローク形状から文字コードを識別する。得られた文字識別候補は、図９Ｃの表９３０に示したデータ構造で保持される。例えば、前述した図９Ａのエッジ９５１の場合、この文字切り出し候補の形状からだけでは「＃（シャープ）」か「井」かの識別が困難であるが、表９３０に示したデータ構造でその両方の仮説を同時に表現できる。従って、文字切り出しグラフを使用することによって、文字識別の不完全性を許容した文字列検索が可能となる。
最後にステップ１３０５で、文字切り出し候補と文字識別候補の情報を各エッジに対応付けて格納して、文字切り出しグラフを出力する。
なお、文字切り出しグラフは、書類中のストロークだけでなく、文字コードに対しても作成可能である。文字コードの列に対し、文字コード一つ一つを文字切り出しエッジに変換していくことによって、一本道の文字切り出しグラフが作成できる。このとき各エッジの文字識別候補は該当の文字コード１結果で類似度１．０からなるとする。
このようにして、前処理で得られた文字切り出しグラフを利用して、入力されたパターン文字列に対し、文字列を検索する（図１４）。
まずステップ１４０２で、検索すべきパターン文字列を入力する。このパターン文字列の表現形式は、文字コードと手書きストロークのどちらにも対応する。次に、ステップ１４０３で、パターン文字列から文字切り出しグラフを作成する。このパターン文字列から作成された文字切り出しグラフを、以降パターン文字切り出しグラフとよぶ。
前述した図１２のステップ１２０３から１２０５、及び図１３で説明したのと同様の文字切り出しグラフの作成手順に従って、文字コード又は手書きストロークからパターン文字切り出しグラフを作成する。
次に、書類管理部１０２に管理される書類が有す文字切り出しグラフが存在すれば、それを取得する（ステップ１４０４及び１４０５）。これを検索対象文字切り出しグラフとよぶ。先のパターン文字切り出しグラフと検索対象文字切り出しグラフとを照合し、パターン文字切り出しグラフの出現を検出する（ステップ１４０６）。本処理の詳細は後に説明する。
文字切り出しグラフを照合した結果、すなわち文字列検索結果は図１０の表１０００に示したデータ構造で保持される。
項目１００１は、その文字列検索結果を同定するＩＤを示す。項目１００２はその結果の指標値であり、大きければより確かな検索結果を意味する。項目１００３及び１００４は、それぞれ該当の検索対象文字切り出しグラフとパターン文字切り出しグラフのＩＤである。
項目１００５は、検索対象文字切り出しグラフとパターン文字切り出しグラフの各エッジの一致箇所の数を示す。項目１００６及び１００７は、第１番目の一致箇所の情報を示しており、それぞれ検索対象文字切り出しグラフでの該当エッジの番号とパターン文字切り出しグラフでの該当エッジの番号を示す。
ステップ１４０６で得られた文字列探索結果を、ステップ１４０７で文字列検索候補に登録する。文字列検索候補のデータ構造を図１１の表１１００に示す。文字列検索結果のスコアに従い、この表にその文字列検索結果のＩＤを登録していく。従って、表１１００の文字列検索結果＃１のＩＤ１１０３が、常に最高のスコアを有す文字列検索結果へのＩＤを示す。現実的には、文字列検索結果総数１１０２には１０候補までなど最大値を設定していてもよい。この場合、それ以上の候補順位の文字列検索結果ＩＤはリストから外していくことになる。
ステップ１４０５から１４０７の処理を、全ての検索対象文字切り出しグラフに対し実行し、全てが終了すると、文字列検索候補を出力する（１４０８）。
以上説明した処理によって文字列検索結果を得る。パターン文字列及び検索対象文字列の表現形式を文字切り出しグラフに変換してから照合を行なうため、各々がもともと文字コードでも手書きストロークでも区別することなく検索することが可能である（図２）。
最後に、文字切り出しグラフ照合について図５と図１５を用いて説明する。本実施形態では、グラフ照合手法として動的計画法を適用したものについて説明する。
まず、検索対象とパターンの文字切り出しグラフを入力する（１５０２）。検索対象文字切り出しグラフのノードをＴ０，Ｔ１，…，Ｔｍ、パターン文字切り出しグラフのノードをＰ０，Ｐ１，…，Ｐｎとする。次に（ｎ＋１）行（ｍ＋１）列の照合テーブルを作成し、各値に初期値０を代入する（１５０３）。照合テーブルの各値は、図５のマトリクス５００内の各ノードＰｉＴｊ（０≦ｉ≦ｎ，０≦ｊ≦ｍ）のスコアに対応する。
次に、Ｐｉ行毎にマトリクス５００内の各ノードのスコアを計算していく（ステップ１５０４）。各行において、左列から順々に一つずつ計算していく。例えば、いまマトリクスノードＰ１Ｔ２（５０１）を計算するとする。このときＰ１Ｔ２に接続される既計算のマトリクスノードのスコアからの遷移スコアを加算して計算される。
遷移元のマトリクスノードＰａＴｂの対象は、０≦ａ≦１，０≦ｂ≦２でかつ、ＰａＴｂを始点、Ｐ１Ｔ２を終点とするエッジ（ＰａＴｂ，Ｐ１Ｔ２）がマトリクス５００に存在するものである。パターン文字切り出しグラフ５６０にエッジ（Ｐａ，Ｐｂ）が存在し、かつ検索対象文字切り出しグラフ５５０にも（Ｔｂ，Ｔ２）が存在する場合、マトリクスエッジ（ＰａＴｂ，Ｐ１Ｔ２）がマトリクス５００に存在する。
本例の場合、遷移元ノードはＰ０Ｔ０，Ｐ０Ｔ１が対象となる。また余分なストロークが存在した場合（挿入）を考慮し、ギャップ遷移（縦又は横の遷移）も認めることとする。つまり本例の場合、パターン文字切り出しグラフに挿入が起きた場合のＰ０Ｔ２、検索対象文字切り出しグラフに挿入が起きた場合のＰ１Ｔ１も遷移元ノードとする。このとき、Ｐ１Ｔ２のスコアＳ（Ｐ１Ｔ２）は、ＰａＰｂのスコアＳ（ＰａＴｂ）とＰａＴｂからＰ１Ｔ２への遷移スコアＴ（ＰａＴｂ，Ｐ１Ｔ２）を用いて、
Ｓ（Ｐ１Ｔ２）＝ｍａｘ（Ｓ（ＰａＴｂ）＋Ｔ（ＰａＴｂ，Ｐ１Ｔ２））・・・・・・・・・・（数式１）
と表せる。
遷移スコアＴ（ＰａＴｂ，Ｐ１Ｔ２）の計算方法は何通りか考えられるが、本実施例では、文字識別候補の情報を利用した１方法を示す。エッジ（Ｐａ，Ｐ１）の文字識別結果が文字コードＣであったときの文字識別の類似度を、ｓ（Ｐａ，Ｐ１，Ｃ）とする。ただしＣに該当の文字識別結果が存在しない場合はｓ（Ｐａ，Ｐ１，Ｃ）＝γ＜＜１．０とする。このとき、遷移スコアは下式のとおりとする。
Ｔ（ＰａＴｂ，Ｐ１Ｔ２）＝ｍａｘ（ｓ（Ｐａ，Ｐ１，Ｃ）＋ｓ（Ｔｂ，Ｔ２，Ｃ））・・・・・・（数式２）
数式２では類似度の和としたが、積でもよい。
Ｔ（ＰａＴｂ，Ｐ１Ｔ２）＝ｍａｘ（ｓ（Ｐａ，Ｐ１，Ｃ）×ｓ（Ｔｂ，Ｔ２，Ｃ））・・・・・・（数式３）
積とした場合は、二つの類似度のどちらか一方が低ければ積算なので、和算より低い値となる。従って、積の場合は両方とも高類似度の共通の文字コードが存在すると有利になる。
またギャップ遷移の場合の遷移コストを下式のように定義する。
Ｔ（ＰｉＴｊ−１，ＰｉＴｊ）＝α＜＜１．０・・・・・・・・・・・・・・・・・・（数式４）
Ｔ（Ｐｉ−１Ｔｊ，ＰｉＴｊ）＝β＜＜１．０（ｉ≠１，ｎ），１．０（ｉ＝１ ｏｒ ｎ）・・・・・（数式５）
ここで、横方向のギャップ遷移においてｉ＝１ ｏｒ ｎのとき（イニシャルギャップ）、１．０と満点のギャップスコアとした理由は、パターン文字列が検索対象の文字列の先頭／末尾に出現するとは限らないので、イニシャルギャップペナルティを１．０とした。
このようにして、マトリクス内の各ノードのスコアを左から右、上行から下行の順に計算していき、照合テーブルを埋めていく。照合テーブルの計算の次に、文字切り出しグラフの照合結果つまり文字列探索結果を表号テーブルから求める（ステップ１５０５）。計算順序とは逆に右下端のマトリクスノードＰｎＴｍから、左上方向へ逆順にたどっていく。
現在ＰｉＴｊに着目しているとする。ＰｉＴｊの遷移元ノードのＰａＴｂのうち、一番スコアが大きいものを次の着目ノードとし、エッジ（Ｔｂ，Ｔｊ）と（Ｐａ，Ｐｉ）のエッジ番号をそれぞれ抽出し、一時的に記憶する。最終的にＰ０Ｔ０までたどりついたら、記憶した順と逆順で、図１０の項目１００６と１００７、及び１００８と１００９、・・・に、検索対象エッジ番号とパターンエッジ番号の組を登録していき、文字列検索結果１０００を完成させる。
ここでマトリクス５００の特性について補足する。マトリクス内のエッジ（ＰａＴｂ，ＰｉＴｊ）は常にａ≦ｉ，ｂ≦ｊである。従って、上行から下行へ順々にスコアを計算していけるため、動的計画法を適用できる。
また検索対象文字列が文字コードのみであった場合は、文字切り出しグラフ５５０は分岐のない一本鎖構造となるため、ｊ−１≦ｂ≦ｊとなる。つまりマトリクス内の各エッジは横方向には高々一つまでしか遷移しないエッジとなる。
同様に、パターン文字列が文字コードのみであった場合は、文字切り出しグラフ５６０は分岐のない一本鎖構造となるため、ｉ−１≦ａ≦ｉとなる。つまりマトリクス内の各エッジは縦方向には高々一つまでしか遷移しないエッジとなる。
検索対象文字列とパターン文字列の両方が手書きのときのみ、エッジ５１１や５１２に示したような、縦横共に１よりも大きい遷移のエッジが存在することになる。逆に言えば、このようなエッジをマトリクス内に作成することによって、グラフとグラフとの照合を可能とした。
最後に、文字列検索結果を出力し（ステップ１５０６）、文字切り出しグラフ照合を終了する。
以上が本発明に係る実施形態の説明である。
なお検索実行時に、検索対象の書類の範囲を限定したり、検索対象の文字列を文字コードや手書きストロークのみに限定したりして文字列検索してもよい。
また、パターン文字列を文字切り出しグラフに変換し検索するため、パターン文字列が文字コードとストロークの組合せからなる場合でも検索可能となる。これは、それぞれの表現形式毎に文字切り出しグラフに変換し、各々のグラフの終端ノードと始端ノードとを結合してパターン文字切り出しグラフを作成することができるためである。検索対象の文字列も、同様に文字コードとストロークの組合せからなる文字列を、座標情報等を利用して一つの検索対象文字切り出しグラフにまとめることによって、検索可能となる。
また、前述した実施形態では、遷移スコアの式（数式２又は数式３）で文字識別結果の類似度を利用したが、文字識別結果の順位を利用したり、文字切り出し候補のパターンから線分方向特徴などの特徴量を抽出し、特徴量同士で内積演算したりしてもよい。
ただ、文字コードから文字切り出しグラフを作成した場合、文字切り出し候補が存在しないが、例えば、事前に文字コードとそのコードの標準的な字形から抽出した文字切り出し候補の特徴量とを組で登録した文字切り出し候補特徴量辞書を用意しておき、文字コードに対応した文字切り出し候補特徴量を辞書から取得し代入することによって、文字切り出し候補特徴量を用いた遷移スコアの計算が可能となる。

書類管理システムに適用可能である。特に文字コードからなる書類に手書きで書込んだ注釈をあわせて管理する書類管理システムで有効である。

Claims (9)

1. パターン文字列入力部と書類管理部と文字列照合部とを有する文字列検索システムにおける文字列検索方法であって、
   パターン文字列入力部において、検索すべき文字列であるパターン文字列を文字コードと手書きストロークとの２種類のいずれか又は両方の形式でユーザから受け取るパターン文字列入力ステップと、
   文字コードと手書きストロークと２種類のいずれか又は両方の形式で入力された文字列を有する書類の情報を検索対象文字列の情報として管理する書類管理部から検索対象となる文字列を読み出す検索対象文字列読み出しステップと、
   前記検索対象文字列と前記パターン文字列とのそれぞれを可能性のある文字切り出しの複数の仮説を一つの有向非循環グラフで表した文字切り出しグラフに変換し、動的計画法を用いて前記切り出された文字の一致度を算出して前記文字切り出しグラフ同士を照合することによって前記パターン文字列が前記書類に出現する箇所を抽出する文字列照合ステップと、
   前記抽出されたパターン文字列の出現箇所を文字列検索結果として表示する表示ステップと、を有する文字列検索方法。
2. 請求項１に記載の文字列検索方法であって、
   前記文字列照合ステップにおいて、前記動的計画法で用いられるスコア計算に文字識別結果を利用することを特徴とする文字列検索方法。
3. 請求項１又は２に記載の文字列検索方法であって、
   前記文字列照合ステップにおいて、前記動的計画法で用いられるスコア計算に文字切り出し候補から生成される幾何特徴量を利用することを特徴とする文字列検索方法。
4. 請求項１から３のいずれか一つに記載の文字列検索方法であって、
   文字コードと該文字コードに対応する文字切り出しグラフを対応付けた文字コードグラフ対応情報を予め準備し、
   前記文字列照合ステップにおいて、文字コードで入力された前記パターン文字列又は前記検索対象文字列を、前記文字コードグラフ対応情報を用いて、文字切り出しグラフに変換することを特徴とする文字列検索方法。
5. 検索すべき文字列であるパターン文字列を文字コードと手書きストロークとの２種類のいずれか又は両方の形式で受け取るパターン文字列入力部と、
   文字コードと手書きストロークとの２種類のいずれか又は両方の形式で入力された文字列を有する書類の情報を検索対象文字列の情報として管理する書類管理部と、
   前記検索対象文字列と前記パターン文字列とのそれぞれを可能性のある文字切り出しの複数の仮説を一つの有向非循環グラフで表した文字切り出しグラフに変換し、動的計画法を用いて、前記切り出された文字の一致度を算出して前記文字切り出しグラフ同士を照合することによって前記パターン文字列が前記書類に出現する箇所を抽出する文字列照合部と、
   前記抽出されたパターン文字列の出現箇所を文字列検索結果として表示する表示部とを有する文字列検索システム。
6. 請求項５に記載の文字列検索システムにおいて、
   前記文字列照合部は、前記動的計画法で用いられるスコア計算に文字識別結果を利用することを特徴とする文字列検索システム。
7. 請求項５又は６に記載の文字列検索システムにおいて、
   前記文字列照合部は、前記動的計画法で用いられるスコア計算に文字切り出し候補から生成される幾何特徴量を利用することを特徴とする文字列検索システム。
8. 請求項５から７のいずれか一つに記載の文字列検索システムであって、
   前記文字列検索システムは、文字コードと該文字コードに対応する文字切り出しグラフを対応付けた文字コードグラフ対応情報を予め格納し、
   前記文字列照合部は、文字コードで入力された前記パターン文字列又は前記検索対象文字列を、前記文字コードグラフ対応情報を用いて、文字切り出しグラフに変換することを特徴とする文字列検索システム。
9. 文字列検索システムであって、
   手書き文字の入力を電子データのストローク情報に変換して出力するデジタルペンと、該デジタルペンからのストローク情報の入力を受け付ける入力装置と、検索対象文字列を含む書類の情報を格納する記憶装置と、演算装置とを有し、
   前記入力装置は、前記書類に追加される手書き文字のストローク情報又は検索すべき文字列であるパターン文字列のストローク情報の入力を前記デジタルペンから受けて前記演算装置に伝達し、
   前記演算装置は、
   前記書類に追加される手書き文字のストローク情報又は前記記憶装置に記憶される書類に含まれる検索対象文字列を可能性のある文字切り出しの複数の仮説を一つの有向非循環グラフで表した検索対象文字切り出しグラフに変換し、前記入力されるパターン文字列のストローク情報又は文字コードで入力されるパターン文字列を可能性のある文字切り出しの複数の仮説を一つの有向非循環グラフで表したパターン文字切り出しグラフに変換し、
   さらに、手書き文字と文字コードのいずれか又は両方の形式で入力された検索対象文字列を手書き文字と文字コードのいずれか又は両方の形式で入力されるパターン文字列によって検索するために、動的計画法を用いて前記切り出された文字の一致度を算出することによる前記検索対象文字切り出しグラフと前記パターン文字切り出しグラフの照合を利用することを特徴とする文字列検索システム。

Images