(57)【特許請求の範囲】
【請求項１】
筆跡入力可能なポインティングデバイスによる入力パターンと、辞書記憶部に登録されている文字または記号のパターンとを対比し、前記入力パターンと全体または部分が一致または類似する文字または記号を提示する文字検索装置であって、
前記辞書記憶部には、文字または記号のパターンを表すデータとして、当該文字または記号を構成するストロークである辞書ストロークを表すデータと、各辞書ストロークの筆順を表す筆順データとが少なくとも登録され、
前記辞書記憶部を参照し、入力パターンに含まれる入力ストロークと、一つの辞書ストロークまたは連続して筆記される複数の辞書ストロークである辞書ストローク列との類似度を求めるストローク類似度算出部と、
前記ストローク類似度算出部によって求められた類似度に基づき、一つの入力パターンに含まれる入力ストロークと、前記辞書記憶部に登録されている一つの文字または記号の辞書ストローク列との組合せについて類似度表を作成する類似度表作成部と、
前記類似度表から、各入力ストロークに対して最大類似度を与える辞書ストローク列を決定し、全ての入力ストロークに対する最大類似度の総和を最大類似度和として求める類似度和算出部と、
前記類似度表を参照し、入力パターンと、前記辞書記憶部に登録されている文字または記号のパターンとの間に、類似度を下げるべき所定のペナルティ条件が成立していれば、前記条件に応じた所定のペナルティ値を前記最大類似度和から減算してパターン一致度とし、所定のペナルティ条件が成立していない時には前記最大類似度和をパターン一致度とする、ペナルティ値減算部と、
前記ペナルティ値減算部で求められたパターン一致度が高い順に、文字または記号を検索結果とし提示する検索結果提示部とを備えたことを特徴とする文字検索装置。
【請求項２】
前記類似度表作成部は、一つの入力パターンを構成するストロークのそれぞれと、一つの文字または記号のパターンの辞書ストロークのそれぞれを先頭とする辞書ストローク列との組合せについての類似度表を作成し、
前記類似度和算出部は、作成された前記類似度表に基づいて、前記辞書ストローク列を決定し、前記最大類似度和を求める、請求項１に記載の文字検索装置。
【請求項３】
前記ペナルティ条件が、ある入力パターンに含まれる一つの入力ストロークに対して最大の類似度を与える辞書ストローク列が、同じ入力パターンに含まれる別の入力ストロークに対しても最大の類似度を与えることである、請求項１または２に記載の文字検索装置。
【請求項４】
前記ペナルティ条件が、ある入力ストロークに対して一定値以上の類似度で対応する辞書ストロークがあり、かつ、当該辞書ストロークの後に、前記入力ストロークの次の入力ストロークに対して前記一定値以上の類似度で対応する辞書ストロークがないことである、請求項１または２に記載の文字検索装置。
【請求項５】
前記ペナルティ条件が、入力ストロークに対して一定値以上の類似度で対応する辞書ストロークがないことである、請求項１または２に記載の文字検索装置。
【請求項６】
前記ストローク類似度算出部が、伸縮マッチング法に従って、入力ストロークと辞書ストローク列との類似度を求める、請求項１〜５のいずれか一項に記載の文字検索装置。
【請求項７】
筆跡入力可能なポインティングデバイスによる入力パターンと、辞書記憶部に登録されている文字または記号のパターンとを対比し、前記入力パターンと全体または部分が一致または類似する文字または記号を提示する文字検索処理をコンピュータに実行させるプログラムであって、
前記辞書記憶部には、文字または記号のパターンを表すデータとして、当該文字または記号を構成するストロークである辞書ストロークを表すデータと、各辞書ストロークの筆順を表す筆順データとが少なくとも登録され、
前記辞書記憶部を参照し、入力パターンに含まれる入力ストロークと、一つの辞書ストロークまたは連続して筆記される複数の辞書ストロークである辞書ストローク列との類似度を求めるストローク類似度算出処理と、
前記ストローク類似度算出処理によって求められた類似度に基づき、一つの入力パターンに含まれる入力ストロークと、前記辞書記憶部に登録されている一つの文字または記号の辞書ストローク列との組合せについて類似度表を作成する類似度表作成処理と、
前記類似度表から、各入力ストロークに対して最大類似度を与える辞書ストローク列を決定し、全ての入力ストロークに対する最大類似度の総和を最大類似度和として求める類似度和算出処理と、
前記類似度表を参照し、入力パターンと、前記辞書記憶部に登録されている文字または記号のパターンとの間に、類似度を下げるべき所定のペナルティ条件が成立していれば、前記条件に応じた所定のペナルティ値を前記最大類似度和から減算してパターン一致度とし、所定のペナルティ条件が成立していない時には前記最大類似度和をパターン一致度とする、ペナルティ値減算処理と、
前記ペナルティ値減算処理で求められたパターン一致度が高い順に、文字または記号を検索結果として提示する検索結果提示処理とをコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、筆跡入力可能なポインティングデバイスにより手書きで入力されたパターンに基づいて文字または記号の検索を行う文字検索装置に関し、特に、入力されたパターンの少なくとも一部が一致する文字または記号の検索を効率的に行うことができる文字検索装置に関する。
【背景技術】
【０００２】
従来、ペンタブレットまたはマウスなどの筆跡入力可能なポインティングデバイスにより、手書きで文字や記号を入力することができる情報処理装置が広く知られている。このような情報処理装置において、入力されたパターンと、辞書に登録されている文字や記号のパターンとを比較することにより、手書き入力されたパターンが、文字辞書に登録されている文字または記号のどれに一致または類似するかを判断する手書き文字認識（手書き文字検索ともいう）について、様々な手法が従来提案されている。
【０００３】
また、ユーザが漢字を入力しようとする場合、漢字は仮名に比べて画数が多いので、文字全体の入力が完了しなくても、部分パターンに基づいて文字を検索して類似度の高い文字候補をユーザに提示できれば、ユーザの入力の手間が省け、ユーザが漢字全体の構成を覚えていなくても漢字入力が可能となる点で好都合である。図７に、部分パターンによる文字検索の一例を示す。図７に示すように、ユーザが漢字の少なくとも一部を入力すると、入力された部分パターンに類似するパターンを含む文字候補が表示されるので、ユーザは、表示された文字候補から、自分が入力しようとした漢字を選択すれば良い。
【０００４】
従来の手書き文字認識または手書き文字検索手法としては、例えば以下のような技術が知られている。
【０００５】
例えば、手書き文字を、ストローク、部分パターン、および文字と順に認識していくことで、高速で高精度な文字認識を可能とするオンライン文字認識装置が、特許文献１（特開平７−５７０５６号公報）に開示されている。
【０００６】
また、入力と辞書の各ストロークとの間で類似度を求めて類似度行列を生成し、各列で最大の類似度を持つ要素を各行ごとに一意に決定し、その最大類似度の和を取ることで文字間の類似度を求め、文字を認識する文字認識方法が、特許文献２（特許第３１５５５７７号公報）に開示されている。この文字認識方法によれば、筆順に依存しない文字検索を行うことが可能である。
【０００７】
さらに、ストローク−ストローク列間で荒く対応を取り、その後でストローク対応に重複がないように整合を取ることで、筆順違いや筆画の続け書きを許容した文字認識を実現させる技術が、下記の非特許文献１に開示されている。
【０００８】
また、部分パターンを対象としてパターン認識を行い、部分パターンと漢字の対応表から漢字を探すことにより、部分パターン文字検索を実現する技術が、特許文献３（特開平８−１２３９０３号公報）に開示されている。
【０００９】
また、ストローク形状とストローク間位置関係の辞書を用いて入力パターンと辞書パターンのストロークを一画ずつ順番に照合し、部分パターン文字検索を行う方法が、特許文献４（特開平９−１９０４９９号公報）に開示されている。この方法は、検索できる部分パターンの種類に制約を受けないので、柔軟な検索が可能である。
【特許文献１】特開平７−５７０５６号公報
【特許文献２】特許第３１５５５７７号公報
【特許文献３】特開平８−１２３９０３号公報
【特許文献４】特開平９−１９０４９９号公報
【非特許文献１】小高和巳、若原徹、梅田三千雄、「選択的ストローク結合による画数・筆順に依存しないオンライン文字認識」、電子通信学会論文誌、昭和５８年５月、J66-D, No.5, p.593-600
【発明の開示】
【発明が解決しようとする課題】
【００１０】
手書きによる文字入力の場合、特に、画数が多く複雑な漢字の場合、文字全体を正しく書くことが困難であることがある。また、しばしば、本来は複数画からなる部分パターンが、続け書きによって１ストロークで入力される。従って、文字全体が正しく筆記されていない場合、または複数画が１ストロークで入力された場合でも、部分パターンによる文字検索が可能であることが好ましい。
【００１１】
例えば、上記特許文献３に記載された検索方法では、部分パターンと文字との対応表にない文字は検索できず、部分パターン辞書にないパターンを書いても検索することができない。また、完全な対応表や部分パターン辞書を作成するのは困難である。
【００１２】
また、特許文献４に記載された方法では、入力パターンのストロークを辞書パターンのストロークと一画ずつ照合するため、複数画が１ストロークで入力された場合は、正しい検索ができない。
【００１３】
複数画の続け書きに対処した文字認識方式としては、上記非特許文献１の手法が提案されているが、この方法は、文字全体の筆記が完了していることを前提とした方式であり、ユーザの入力の手間を軽減できない。また、この手法は、筆順の異なる筆画を対応付けて精度良く認識を行うために、対応の重複を取り除く処理を含んでおり、これが処理量の多大な増加を招いている。
【００１４】
上記の課題を鑑み、本発明は、複数画が１ストロークで入力された場合でも、部分パターンによる文字または記号の検索が可能な文字検索装置を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記の目的を達成するために、本発明にかかる文字検索装置は、筆跡入力可能なポインティングデバイスによる入力パターンと、辞書記憶部に登録されている文字または記号のパターンとを対比し、前記入力パターンと全体または部分が一致または類似する文字または記号を提示する文字検索装置であって、前記辞書記憶部には、文字または記号のパターンを表すデータとして、当該文字または記号を構成するストロークである辞書ストロークを表すデータと、各辞書ストロークの筆順を表す筆順データとが少なくとも登録され、前記辞書記憶部を参照し、入力パターンに含まれる入力ストロークと、一つの辞書ストロークまたは連続して筆記される複数の辞書ストロークである辞書ストローク列との類似度を求めるストローク類似度算出部と、前記ストローク類似度算出部によって求められた類似度に基づき、一つの入力パターンに含まれる入力ストロークと、前記辞書記憶部に登録されている一つの文字または記号の辞書ストローク列との組合せについて類似度表を作成する類似度表作成部と、前記類似度表から、各入力ストロークに対して最大類似度を与える辞書ストローク列を決定し、全ての入力ストロークに対する最大類似度の総和を最大類似度和として求める類似度和算出部と、前記類似度表を参照し、入力パターンと、前記辞書記憶部に登録されている文字または記号のパターンとの間に、類似度を下げるべき所定のペナルティ条件が成立していれば、前記条件に応じた所定のペナルティ値を前記最大類似度和から減算してパターン一致度とし、所定のペナルティ条件が成立していない時には前記最大類似度和をパターン一致度とするペナルティ値減算部と、前記ペナルティ値減算部で求められたパターン一致度が高い順に、文字または記号を検索結果として提示する検索結果提示部とを備えたことを特徴とする。
【００１６】
本発明に関して、「ストローク」は、１回のペンダウンからペンアップまでに書かれる筆跡を意味する。また、「パターン」は、１つまたは複数の「ストローク」から形成される、文字または記号の全体または部分パターンを意味する。
【００１７】
上記の構成によれば、類似度表作成部が、ストローク類似度算出部によって求められた類似度に基づき、一つの入力パターンに含まれる入力ストロークと、前記辞書記憶部に登録されている一つの文字または記号の辞書ストローク列との組合せについて類似度表を作成し、類似度和算出部が、前記類似度表から、各入力ストロークに対して最大類似度を与える辞書ストローク列を決定し、全ての入力ストロークに対する最大類似度の総和を最大類似度和として求めることにより、本来は複数ストロークで書かれるべきパターンが１ストロークで入力された場合でも、部分パターンによる文字または記号の検索が可能となる。また、ペナルティ値減算部が、前記類似度表を参照し、入力パターンと、前記辞書記憶部に登録されている文字または記号のパターンとの間に、類似度を下げるべき所定のペナルティ条件が成立していれば、前記条件に応じた所定のペナルティ値を前記最大類似度和から減算し、パターン一致度を求めることにより、部分パターンによる文字または記号の検索精度を向上させることが可能となる。
【００１８】
上記の文字検索装置において、前記ペナルティ条件は、例えば、ある入力パターンに含まれる一つの入力ストロークに対して最大の類似度を与える辞書ストローク列が、同じ入力パターンに含まれる別の入力ストロークに対しても最大の類似度を与えることである。
【００１９】
上記の文字検索装置において、前記ペナルティ条件は、例えば、ある入力ストロークに対して一定値以上の類似度で対応する辞書ストロークがあり、かつ、当該辞書ストロークの後に、前記入力ストロークの次の入力ストロークに対して前記一定値以上の類似度で対応する辞書ストロークがないことである。
【００２０】
上記の文字検索装置において、前記ペナルティ条件は、例えば、入力ストロークに対して一定値以上の類似度で対応する辞書ストロークがないことである。
【００２１】
上記の文字検索装置において、前記ストローク類似度算出部が、伸縮マッチング法に従って、入力ストロークと辞書ストローク列との類似度を求めることが好ましい。
【００２２】
また、上記の目的を達成するために、本発明にかかるプログラムは、筆跡入力可能なポインティングデバイスによる入力パターンと、辞書記憶部に登録されている文字または記号のパターンとを対比し、前記入力パターンと全体または部分が一致または類似する文字または記号を提示する文字検索処理をコンピュータに実行させるプログラムであって、前記辞書記憶部には、文字または記号のパターンを表すデータとして、当該文字または記号を構成するストロークである辞書ストロークを表すデータと、各辞書ストロークの筆順を表す筆順データとが少なくとも登録され、前記辞書記憶部を参照し、入力パターンに含まれる入力ストロークと、一つの辞書ストロークまたは連続して筆記される複数の辞書ストロークである辞書ストローク列との類似度を求めるストローク類似度算出処理と、前記ストローク類似度算出処理によって求められた類似度に基づき、一つの入力パターンに含まれる入力ストロークと、前記辞書記憶部に登録されている一つの文字または記号の辞書ストローク列との組合せについて類似度表を作成する類似度表作成処理と、前記類似度表から、各入力ストロークに対して最大類似度を与える辞書ストローク列を決定し、全ての入力ストロークに対する最大類似度の総和を最大類似度和として求める類似度和算出処理と、前記類似度表を参照し、入力パターンと、前記辞書記憶部に登録されている文字または記号のパターンとの間に、類似度を下げるべき所定のペナルティ条件が成立していれば、前記条件に応じた所定のペナルティ値を前記最大類似度和から減算してパターン一致度とし、所定のペナルティ条件が成立していない時には前記最大類似度和をパターン一致度とするペナルティ値減算処理と、前記ペナルティ値減算処理で求められたパターン一致度が高い順に、文字または記号を検索結果として提示する検索結果提示処理とをコンピュータに実行させることを特徴とする。
【発明の効果】
【００２３】
本発明によれば、複数画が１ストロークで入力された場合でも、部分パターンによる文字または記号の検索が可能な文字検索装置を提供することができる。
【発明を実施するための最良の形態】
【００２４】
以下、図面を参照し、本発明の一実施形態について説明する。
【００２５】
なお、本発明は、部分パターンによる文字または記号の検索を行うための装置、方法、プログラム等に関するが、検索対象となる文字または記号には、仮名、漢字、および数字の他、任意の記号が含まれる。また、本明細書および特許請求の範囲では、これらの文字または記号の検索を「文字検索」と略称する。
【００２６】
本発明は、ペンタブレットまたはマウスなどの筆跡入力可能なポインティングデバイスの接続されたコンピュータ環境上で実行される文字検索プログラムとして実施することが可能である。また、この文字検索プログラムを記録した記録媒体も、本発明の一実施形態である。なお、本発明は、適当なポインティングデバイスを備えたコンピュータまたは携帯情報端末として実施されても良い。このようにコンピュータまたは携帯情報端末として本発明の文字検索装置を実施する場合、コンピュータまたは携帯情報端末は、文字検索機能以外の任意の機能を有し得る。
【００２７】
以下では、本発明にかかる文字検索プログラムがインストールされたコンピュータを、本発明にかかる文字検索装置の一実施形態として説明する。
【００２８】
図１は、本実施形態にかかるコンピュータにおいて、本発明の文字検索プログラムが実行されることによって実現される機能的構成を示したブロック図である。
【００２９】
図１に示すように、本実施形態にかかるコンピュータ１は、ユーザに手書き文字を入力させるために、ポインティングデバイス１１とディスプレイ１２とを備えている。また、コンピュータ１は、文字検索機能を実現するために、ストローク類似度算出部１３と、類似度表作成部１４と、類似度和算出部１５と、ペナルティ値減算部１６と、ストローク辞書記憶部１７と、入力ストローク記憶部１８と、検索結果提示部１９とを備えている。なお、ストローク類似度算出部１３、類似度表作成部１４、類似度和算出部１５、ペナルティ値減算部１６、および検索結果提示部１９は、コンピュータ１のプロセッサ（図示せず）がメモリ（図示せず）にインストールされた文字検索プログラムを実行することによって機能的に実現されるものであって、これらの各部に個々に対応するハードウェアは必ずしも存在しない。
【００３０】
ポインティングデバイス１１としては、マウスやペンタブレット等の、手書き入力が可能な入力装置が用いられる。なお、ポインティングデバイス１１としてディスプレイ一体型のペンタブレットを用いる場合は、ディスプレイ１２を省略可能である。
【００３１】
ユーザにより手書き入力がなされると、ポインティングデバイス１１が、入力パターンの１ストローク毎に、入力ストロークデータを取得する。取得された入力ストロークデータは、入力ストローク記憶部１８に記憶される。なお、「１ストローク」とは、ペンダウンからペンアップまで（マウスの場合はドラッグ開始からドラッグ終了まで）に描かれる連続した軌跡を意味する。
【００３２】
ここで、入力ストロークデータは、
（ｘi，ｙi，ｔi）：０≦ｉ＜ｎ
と表される時系列の特徴点データである。ｘi，ｙiは特徴点座標であり、ｔiはペンアップダウン情報、ｉは特徴点番号、ｎは整数である。特徴点は、ストロークのサンプリングデータから特徴的な点を抽出したものである。特徴点抽出には、再帰的最遠点分離法や、一定の時間間隔でサンプリングしなおす方法、方向成分を量子化する方法など、様々な方法が提案されている。本発明は、特徴点抽出の方法には特に依存しない。また、複数のストロークが入力された場合、それらの入力ストロークのストロークデータには、筆記された順にストローク番号が付けられ、入力ストローク記憶部１８に記憶される。本実施形態では、ストローク番号を付加したが、ストロークデータを順番に保存するなり、ストロークデータ列を保存するなりして、ストロークの順序がわかるように保存すれば、必ずしもストローク番号を付加する必要はない。
【００３３】
ストローク辞書記憶部１７には、様々な文字または記号のパターンを、そのパターンを構成するストロークで表した辞書ストロークデータが記憶されている。時系列の特徴点データで定義した辞書ストロークデータが記憶されている。辞書ストロークデータは、
（ｖｘij，ｖｙij，ｖｔij）：０≦ｉ＜ｍ，  ０≦ｊ＜ｋ
と表される。ｖｘij，ｖｙijは特徴点座標であり、ｖｔijはペンアップダウン情報である。ｊは特徴点番号である。ｉは、その文字パターン中のストローク番号である。ストローク番号は、各ストロークの筆順に従って付与されている。ｍ、ｋは整数である。
【００３４】
ストローク類似度算出部１３は、ストローク辞書記憶部１７を参照し、入力ストロークと、一つの文字前記辞書ストローク群のうち、一つの辞書ストロークまたは連続して筆記される辞書ストローク列との類似度を求める。求めた類似度は、類似度表作成部１４へ渡される。なお、「辞書ストローク列」とは、１つの文字パターンを構成する複数の辞書ストロークのうち、時系列的に連続する複数のストロークを意味する。つまり、ユーザが手書き入力を行う際、本来は複数ストロークで筆記すべき箇所を、続け書きにより１ストロークで筆記することがしばしばある。このため、ストローク類似度算出部１３は、１つの入力ストロークを、複数の辞書ストローク（すなわち辞書ストローク列）と順次対比することにより、類似度を求める。
【００３５】
ストローク類似度算出部１３は、入力ストロークと辞書ストローク列との類似度を求める際に、伸縮マッチングの手法を用いる。伸縮マッチングで最もよく知られている方法の一つには、動的計画法によるマッチング（いわゆるＤＰマッチング）があるが、本発明に適用可能な伸縮マッチングはＤＰマッチングのみに限定されない。なお、入力ストローク一つに対して辞書ストローク列の何画目までが対応するかを決定するためには、次のような方法が考えられる。例えば、一つの入力ストロークと、辞書ストローク列の１画目のストロークからt画目のストロークまでで形成されるパターンとの類似度ｓ（ｔ）が、同じ入力ストロークと、同じ辞書ストローク列の１画目のストロークから（ｔ＋１）画目のストロークまでの類似度ｓ（ｔ＋１）よりも大きい場合に、前記一つの入力ストロークに対して、辞書ストローク列の１画目からｔ画目までのストロークが対応していると決定する方法である。
【００３６】
これにより、例えば、図２（ａ）に示すような入力ストロークＳin1と、図２（ｂ）に示すような辞書パターンとがあった場合、ストローク類似度算出部１３は、図２（ａ）の入力ストロークＳin1に対応付く辞書ストロークが、図２（ｂ）のＳdic1およびＳdic2であると決定することができる。
【００３７】
ストローク類似度算出部１３が入力ストロークと辞書ストローク列との類似度を求めるための他の方法としては、次のような方法もある。例えば、入力ストロークの特徴点（ｘp，ｙp）と辞書ストロークの特徴点（ｖｘiq、ｖｙiq）との対応を［ｐ，ｑ］と表し、そのローカルな評価値がｆ（ｐ，ｑ）で与えられるとき、対応［ｐ，ｑ］の次の対応［ｐ’、ｑ’］を、［ｐ＋１，ｑ］、［ｐ，ｑ＋１］、［ｐ＋１，ｑ＋１］の中からｆ（ｐ’、ｑ’）を最大化するように選択し、これを繰り返す。そして、この繰り返し処理の過程で、入力ストロークおよび辞書ストローク共に最終ストロークまで辿り着いた時点で、マッチングを終了する。
【００３８】
類似度表作成部１４は、ストローク類似度算出部１３の処理結果に基づき、入力パターンと辞書に登録されている全ての文字パターンとの組合せについて、入力ストロークに対する辞書ストローク列の類似度の表（以降、この表を「類似度表」と称する。）を作成し、少なくとも一時的に記憶する。なお、「類似度表を作成する」とは、入力ストロークと辞書ストローク列との全ての組合せについて総当たり的に類似度を求めることを意味し、必ずしも表形式の出力を求めるわけではない。
【００３９】
ここで、類似度表作成部１４は、一つの入力パターンと一つの文字パターンとの類似度表を作成する場合、当該一つの入力パターンを構成するストロークのそれぞれと、当該一つの文字パターンの辞書ストロークのそれぞれを先頭とする辞書ストローク列との組合せについて、ストローク類似度算出部１３を用いて類似度を求める。つまり、入力パターンのストローク数をｎin、辞書に登録されているある文字パターンのストローク数をｎdicとすれば、その入力パターンと文字パターンとの組合せについて、ｎin×ｎdicの大きさの類似度表が作られることになる。
【００４０】
例えば、入力パターンのストローク数が３であり、辞書に登録されているある文字パターンのストローク数が５であるとする。この場合、この入力パターンと文字パターンとの組合せについて、入力パターンの３ストロークのそれぞれに対して、次の（１）〜（５）までの５種類の辞書ストローク列との類似度が、ストローク類似度算出部１３によって求められ、３×５の類似度表が作成される。この類似度表の各要素を、ｓｓ（ｉ，ｊ）と表すことにする。ここで、ｉは入力パターン中のストローク番号、ｊは辞書ストローク列の先頭となる辞書ストローク番号である。
【００４１】
（１）文字パターンの辞書ストロークの第１画〜第５画からなる辞書ストローク列、
（２）第２画〜第５画からなる辞書ストローク列、
（３）第３画〜第５画からなる辞書ストローク列、
（４）第４および第５画からなる辞書ストローク列、
（５）第５画からなる辞書ストローク列。
【００４２】
類似度和算出部１５は、類似度表作成部１４によって作成された類似度表から、各入力ストロークに対して最も大きな類似度を与える辞書ストローク列を選び出し、入力ストロークの全てについて、選び出した最大類似度の和ｓｔを求める。すなわち、和ｓｔは以下の式によって求められる。
【００４３】
ｓｔ＝Σ［ｉ=０〜（ｎin−１）］ｍａｘ[ｓｓ（ｉ，ｊ）|０≦ｊ＜ｎdic]
【００４４】
ペナルティ値減算部１６は、類似度表作成部１４によって作成された類似度表を参照し、入力パターンと、前記辞書記憶部に登録されている文字または記号のパターンとの間に、類似度を下げるべき所定のペナルティ条件が成立する場合に、前記ペナルティ条件に応じた所定のペナルティ値を、類似度和算出部１５によって算出された最大類似度和ｓｔから減算する。この結果得られた値が、入力パターンと文字パターンとのパターン一致度となる。ペナルティ値の算出については、後に詳しく説明する。
【００４５】
検索結果提示部１９は、検索結果として、入力パターンと辞書に登録されている全ての文字パターンとの組合せのそれぞれについて求められたパターン一致度が大きい順に、文字パターンをディスプレイ１２に表示する。
【００４６】
ここで、ペナルティ値減算部１６の処理の詳細について説明する。ペナルティ値減算部１６においてペナルティ値の減算を行うべきペナルティ条件としては、例えば、以下の第１〜第３の条件が考えられる。
【００４７】
第１の条件は、ペナルティ値減算部１６が、類似度表作成部１４によって作成された類似度表を参照し、ある入力パターンに含まれる一つの入力ストロークに対して最大類似度を与える辞書ストローク列が、同じ入力パターンに含まれる別の入力ストロークに対しても最大類似度を与えることである。この場合、ペナルティ値減算部１６は、入力ストロークと辞書ストロークとの対応に重複ありと見なして、所定のペナルティ値ｐ1を最大類似度和ｓｔから減算する。
【００４８】
上述のように、本実施形態では、ストローク類似度算出部１３、類似度表作成部１４、および類似度和算出部１５は、入力パターンと辞書の文字パターンとにおけるストローク対応の重複を許して類似度を算出する処理を行っている。しかし、このように、入力パターンの各ストロークが本来対応すべき辞書ストローク以外とのストロークとも重複して対応することを許可すれば、例えば同様のストロークがいくつか並んだパターンを持つ文字間の識別が困難になってしまう。上記第１の条件によるペナルティ値減算は、ストロークの重複による識別の困難さをある程度軽減し、高精度化する役割を果たす。
【００４９】
例えば、図３（ａ）に示す入力パターンを構成する３つの入力ストロークＳin1〜Ｓin3を、図３（ｂ）に示す文字パターンの辞書ストロークＳdic1〜Ｓdic3と比較して類似度を求めた場合、入力ストロークＳin1およびＳin2のそれぞれは、辞書ストロークＳdic1に対して最大類似度を有し、入力ストロークＳin3は、辞書ストロークＳdic3に対して最大類似度を有する。ペナルティ値減算部１６によるペナルティ値減算がなければ、入力ストロークＳin1〜Ｓin3の全てについて、位置、形状共に良く似た辞書ストロークが存在するので、図３（ａ）の入力パターンと、図３（ｂ）の文字パターンとのパターン一致度は、非常に高くなる。しかし、図３（ａ）の入力パターンは、図３（ｂ）の文字パターンの部分パターンではないので、パターン一致度があまり高くなることは好ましくない。そこで、ペナルティ値減算部１６が、上記第１の条件が満たされた場合に、最大類似度を与えるストロークの重複にペナルティを課すことで、文字全体としての検索の正確性を向上させることができる。
【００５０】
第２の条件は、ある入力ストロークａに対して一定値以上の類似度で対応する辞書ストロークＡがあるとき、この辞書ストロークＡの後に、入力ストロークａの次の入力ストロークｂに対して一定値以上の類似度で対応する辞書ストロークがないことである。この場合、ペナルティ値減算部１６は、所定のペナルティ値ｐ2を最大類似度和ｓｔから減算する。これにより、筆順違いにもある程度のペナルティを与えることができる。
【００５１】
例えば、図４（ａ）の入力パターン「白」は、図４（ｂ）の辞書パターン「鮮」と図４（ｃ）の辞書パターン「的」との両方の部分パターンである。なお、図４（ａ）の入力パターンは、文字「白」の正しい筆順で手書き入力されたものとする。ここで、図４（ａ）の入力パターンの各ストロークに対し、図４（ｂ）の辞書パターン「鮮」も、図４（ｃ）の辞書パターン「的」と同様に、非常に類似した位置と形状を持った辞書ストロークを有している。したがって、入力ストロークと辞書ストローク列との類似度だけを考慮すれば、図４（ａ）の入力パターン「白」に対して、図４（ｂ）の辞書パターン「鮮」は、図４（ｃ）の辞書パターン「的」と同列に並ぶほど、高い類似度を取り得る。しかし、図４（ａ）の入力パターンに対しては、左側に「魚」を持つ文字より、左側に「白」を持った文字が、検索結果の上位に来ることが望ましい。
【００５２】
図４（ａ）の入力パターンに対して、図４（ｃ）の辞書パターン「的」の各ストロークは、順番に、高い類似度で対応付く。しかし、図４（ａ）の入力パターンに対して、図４（ｂ）の辞書パターン「鮮」の各ストロークは、必ずしも高い類似度で対応付かない。例えば、図４（ａ）の入力パターン「白」の１番目のストロークＳin1と、図４（ｂ）の辞書パターン「鮮」の１番目のストロークＳdic1とは、位置、形状ともに類似しており、高類似度を取り得る。しかし、図４（ａ）の入力パターン「白」の２番目のストロークＳin2と、図４（ｂ）の辞書パターン「鮮」の２番目のストロークＳdic2とは、形状差が大きく、類似度は低い。
【００５３】
そこで、上記第２の条件に従い、入力ストロークの筆記順に従って、高い類似度で辞書ストロークが対応付いているかどうかを判定し、対応付いていない場合は、所定のペナルティ値ｐ2を最大類似度和ｓｔから減算する。これにより、図４（ａ）の入力パターン「白」に対して、図４（ｃ）の辞書パターン「的」の方が、図４（ｂ）の辞書パターン「鮮」よりも、検索結果中の順位が高くなるという効果が得られる。
【００５４】
第３の条件は、辞書ストロークと一定値以上の類似度での対応がない入力ストロークがあること、言い換えれば、ある入力ストロークに対して対応すると見なせる辞書ストロークがないことである。このとき、ペナルティ値減算部１６は、所定のペナルティ値ｐ3を最大類似度和ｓｔから減算する。
【００５５】
例えば、図５（ａ）の入力パターンのストロークＳin1〜Ｓin5は、図５（ｂ）の辞書パターン「龍」のストロークＳdic1〜Ｓdic5と、非常に高い類似度で対応付く。しかし、図５（ａ）の入力パターンのストロークＳin6は、図５（ｂ）の辞書パターン「龍」のどの部分とも類似しない。入力ストロークと辞書ストローク列との類似度だけを考慮すれば、図５（ａ）の入力パターンに対して、図５（ｂ）の辞書パターン「龍」は、入力ストロークＳin6と類似するストロークを含まないにも関わらず、入力ストロークＳin6と類似するストロークを含む図５（ｃ）の辞書パターン「部」と同様に、高いパターン一致度を有することとなってしまう。
【００５６】
そこで、上記第３の条件に従い、入力パターンの一部が辞書パターンのどの部分とも類似しない場合は、その辞書パターンの文字が検索結果の上位にならないよう、所定のペナルティ値ｐ3を最大類似度和ｓｔから減算する。
【００５７】
なお、上記第１〜第３の条件のそれぞれに従って適用されるペナルティ値ｐ1〜ｐ3は、実験的に適切な値を求めれば良い。例えば、ペナルティ値減算部１６の演算結果として得られるパターン一致度が０〜１０００の値を取り得る場合、様々な手書き文字パターンを用いてシミュレーションを行いながら、ペナルティ値を所定値きざみ（例えば５０ずつ）で変更させ、最も適切な検索結果が得られるペナルティ値を採用すれば良い。
【００５８】
以上のとおり、ペナルティ値減算部１６によるペナルティ値の適用条件について、第１〜第３の３つの具体的条件を例示したが、ペナルティ値減算部１６によるペナルティ値の算出に際して、上記第１〜第３の条件を複数組み合わせて適用することも有効である。
【００５９】
次に、図６を参照し、本発明にかかる文字検索方法の手順を説明する。
【００６０】
ユーザがポインティングデバイス１１を用いて手書きパターンを入力すると、ポインティングデバイス１１が、入力パターンの１ストローク毎に、入力ストロークデータを取得し、入力ストローク記憶部１８に記憶する（ステップＯｐ１）。
【００６１】
次に、類似度表作成部１４が、入力パターンの最初のストロークと、ストローク辞書記憶部１７に登録されている最初の文字パターンとを選択し、入力ストロークと当該文字パターンの辞書ストローク列との類似度表を作成する（ステップＯｐ２）。このステップＯｐ２において、入力ストロークと辞書ストローク列との類似度を求める際に、ストローク類似度算出部１３が、例えば伸縮マッチングの手法を用いる。
【００６２】
類似度表作成部１４は、類似度表が完成するまで、すなわち、入力ストローク数をｎin、前記文字パターンの辞書ストローク数をｎdicとすれば、入力ストロークと辞書ストローク列との全ての組合せについて、ｎin×ｎdicの大きさの類似度表が完成するまで（ステップＯｐ３にてＹｅｓ）、ステップＯｐ２を繰り返し実行する。
【００６３】
次に、類似度和算出部１５が、ステップＯｐ２で作成された類似度表から、各入力ストロークに対して最も大きな類似度を与える辞書ストローク列を選び出し、入力ストロークの全てについて、選び出した最大類似度の和ｓｔを求める（ステップＯｐ４）。
【００６４】
次に、ペナルティ値減算部１６が、ステップＯｐ２で作成された類似度表に基づいてペナルティ値を算出し、算出されたペナルティ値をステップＯｐ４で算出された最大類似度和ｓｔから減算することにより、入力パターンと文字パターンとのパターン一致度を求める（ステップＯｐ５）。
【００６５】
上記のステップＯｐ２〜Ｏｐ５を、入力パターンと、ストローク辞書記憶部１７に登録されている全ての文字パターンとの組合せについてパターン一致度が求められるまで（ステップＯｐ６にてＹｅｓ）、繰り返す。
【００６６】
そして、最後に、検索結果提示部１９が、入力パターンに対してパターン一致度が高い順に、検索結果としての文字パターンをディスプレイ１２に表示する（Ｏｐ７）。
【００６７】
以上の手順により、複数画が１ストロークで入力された場合でも、入力パターンと部分的に一致するパターンを含む文字を、効率的にかつ高精度に検索することができる。
【産業上の利用可能性】
【００６８】
本発明は、複数画が１ストロークで入力された場合でも、部分パターンによる文字検索が可能な文字検索装置およびこれを具現化するコンピュータプログラムとして利用可能である。
【図面の簡単な説明】
【００６９】
【図１】本発明の一実施形態にかかる文字検索装置のブロック図である。
【図２】本発明の一実施形態にかかる文字検索装置における入力パターン（ａ）と辞書パターン（ｂ）との対応付けを説明するための図である。
【図３】本発明の一実施形態にかかる文字検索装置におけるペナルティ条件が課される場合の入力パターン（ａ）と辞書パターン（ｂ）との組合せの一例を示した図である。
【図４】本発明の一実施形態にかかる文字検索装置におけるペナルティ条件が課される場合の入力パターン（ａ）と辞書パターン（ｂ）との組合せの一例と、前記入力パターンとの組合せでペナルティ条件が課されない辞書パターン（ｃ）の例を示した図である。
【図５】本発明の一実施形態にかかる文字検索装置におけるペナルティ条件が課される場合の入力パターン（ａ）と辞書パターン（ｂ）との組合せの一例と、前記入力パターンとの組合せでペナルティ条件が課されない辞書パターン（ｃ）の例を示した図である。
【図６】本発明にかかる文字検索方法の手順の一例を示すフローチャートである。
【図７】従来の部分パターン文字検索装置の画面例である。
【符号の説明】
【００７０】
１    コンピュータ（文字検索装置）
１１  ポインティングデバイス
１２  ディスプレイ
１３  ストローク類似度算出部
１４  類似度表作成部
１５  類似度和算出部
１６  ペナルティ値減算部
１７  ストローク辞書記憶部
１８  入力ストローク記憶部
１９  検索結果提示部
【図１】
0004817297.tif 000002
【図２】
0004817297.tif 000003
【図３】
0004817297.tif 000004
【図４】
0004817297.tif 000005
【図５】
0004817297.tif 000006
【図６】
0004817297.tif 000007
【図７】
0004817297.tif 000008