JP2002515144A - 手書き入力ストローク分割方法 - Google Patents

Abstract

(57)【要約】 本発明の方法は、手書き入力（１１０）において点における曲率の導関数（１４０）または瞬間変化率を計算する段階を含む。次に、この方法は、高い曲率導関数の点と、低い曲率導関数（１５０）の後続の点との間の中間点にある、入力のある点（またはピクセル）をストローク境界点として選択する。かかる境界点は、絶対曲率値によって影響を受けず、むしろ曲率における相対的変化によってのみ影響を受ける。ストローク分割境界点は、手書き入力の解析のためにストローク方式の認識装置に与えられる（１７０）。

Description

【発明の詳細な説明】 手書き入力ストローク分割方法 発明の分野 本発明は、一般に、手書き認識に関し、さらに詳しくは、手書き入力のストロ ーク分割(stroke segmentation)方法に関する。 従来技術の説明 人間の手書きを機械認識することは、極めて困難な問題であり、近年のペン方 式のコンピューティング装置の普及により、対処すべき重要な課題となっている 。この問題に対して多くの極めて多様な手法が存在するが、１つの有用な手法と して、筆跡を一連の基本的な動き、すなわち「ストローク(stroke)」に分解して 、このストローク（ある方法でパラメータ化される）を文字認識装置に対する入 力として利用する方法がある。 ストローク方式の認識装置における主要条件は、同一文字クラスの複数の事例 (instance)（例えば、異なる時間に異なる筆者によってかかれた文字「Ａ」）を 毎回同様なストロークのセットに分割することである。これにより、文 字事例の記述が文字認識装置自体にとって同様に「見える」ため、認識がそれほ ど困難にならないことに役立つ。理想的な場合には、ある文字のすべての事例は 常に同じ数のストロークを含み、ストロークはすべて同じ相対的位置にあり、ス トロークの形状記述(featural description)は事例全体を通じてすべて非常に類 似する。この理想は実際には達成できないが、ある程度近づくことができ、認識 制度を改善できる。 従来の１つの方法において、ストローク境界は、垂直（または「ｙ」）方向の ペン速度(pen velocity)がゼロとなる点で設定される、すなわち、筆跡が上に向 かって動き始めるあるいは下に向かって動き始める点で設定される。それによっ て得られるストロークのセットは、「アップストローク(upstroke)」および「ダ ウンストローク(downstroke)」と呼ばれる。この方法については、Mermelstein & Edenによる"Experiments on Computer Recognition of Connected Handwritte n Words"，in Information And Control vol．7，p．255-270，1964において説 明される。この方法の１つの問題点は、垂直方向の変化に対して過剰に敏感で、 水平方向の変化に対して全く敏感でないことである。しかも、多くの文字は水平 部分、例えば、「ｔ」の横棒、からなり、「Ｅ」の３つの先は、いくら下手な筆 跡でも、一般に垂直よりも水平である。ｙ速度方式のスト ローク・セグメンタ(y-velocity based strokesegmenter)は、水平部分を１つの ストロークに分解することがあるが、垂直方向におけるペンの小さなぶれという 単純な理由により、２つ，３つまたはそれ以上に分解される。このため、同一文 字の複数の事例が異なって見えるストロークのセットに分割される場合が多いの で、認識精度が低下する。新たなストロークを作成する前に最小垂直方向変化を 必要とするなど、この方法の不正確さを補正する試みの成功は限られており、同 じ基本的な問題の多くは未解決のままである。 別の既存の方法では、この問題は、曲率(curvature)が局所的な最大値であり 、筆跡における急峻な曲げに対応するある閾値を越える点でストローク境界を設 定することによって解決される。急峻な曲げはペンの動く方向に関係なく生じる ので、この方法は単語または文字など手書き入力の各部の方向に対して敏感でな い。しかし、曲率方式の方法にはそれ自体の問題もある。例えば、ある人が「Ｌ 」を急峻な曲げではなく、非常になだらかな曲げで書くと、「Ｃ」のように見え ることがある。この方法は、ストローク境界に必要な閾値曲率を満たさないと、 この場合「Ｌ」を分割できない。閾値を単純に低くしても、問題の解決にならな い。なぜならば、これは単純に過剰な数のストローク数になるためである。多す ぎる数のストロークを有することは、少なすぎることと同様に悪いが、これは同 じ文字 の複数の事例が異なる種類のストロークに分割される場合が多いためである。 従って、より正確で、ｙ速度方法や既存の曲率方法など上記の方法の問題がな いストローク分割方法が必要とされる。 発明の概要 従って、本発明は、各特定の文字クラスの複数の事例にわたって数が一貫した ストロークに手書き入力を分割する方法を提供する。 本発明は、各特定の文字クラスの複数の事例にわたって形状および位置が類似 したストロークに手書き入力を分割する方法を提供する。 一般に、本発明の方法は、手書き入力の点における曲率の導関数(derivative) または瞬間変化率(instantaneousrate of change)を算出する段階を含む。次に 、この方法は、高い曲率導関数の点と、低い曲率導関数の後続の点との間に存在 する入力における特定の点（またはピクセル）をストローク境界点として選択す る。このような境界点は、絶対曲率値によって影響を受けないが、曲率における 相対的変化によってのみ影響を受ける。 図面の簡単な説明 第１図は、本発明の好適な実施例によりストローク境界を識別する動作のフロ ー図である。 第２図は、従来のｙ速度方法によって生成される手書き入力のストロークへの 分解である。 第３図は、従来の曲率方法によって生成される手書き入力のストロークへの分 解である。 第４図は、本発明の好適な実施例によって生成される手書き入力のストローク への分解である。 第５図は、デジタイジング装置から受信される文字「Ｌ」を構成する点である 。 第６図は、本発明の好適な実施例により定距離に再サンプリングした後の文字 「Ｌ」を構成する点である。 第７図は、本発明の好適な実施例の曲率計算を示す分解図である。 第８図は、第７図における各点について計算された曲率値を図式的に示す。 第９図は、第７図における各点について計算された曲率値の導関数を図式的に 示す。 好適な実施例の詳細な説明 一般に、手書き文字入力は、離散的な連続セグメントの形式でユーザから収集 される。離散的な連続セグメントは、 １つまたはそれ以上のペン・ストロークからなり、ここでペン・ストローク(pen stroke)とは、デジタイジング・タブレットまたは用紙などの入力装置との接触 期間中にペンによって残されるマークのことである。 本発明では、１つまたはそれ以上の離散的な連続セグメントは、認識される手 書き入力の単位である。手書き入力(handwritten input)とは、電子的に捕捉さ れる入力のことであり、手書き入力；電子入力；スタンプ式入力など圧力によっ て捕捉される入力；ファクシミリ，ページャまたは他の装置を介して電子的に受 信される入力などが含まれるが、これらに限定されない。 ストロークは、入力装置によってほぼ定期的にサンプリングされる一連の点と して表される。各点は、少なくともＸおよびＹ座標によって記述される。ストロ ークは、デジタイジング・タブレットを利用して電子的に捕捉でき、あるいは画 像におけるライン検出のプロセスを介してスキャンまたはファックスされた画像 から導出できる。このように電子的に捕捉する方法は当技術分野で周知である。 好適な方法では、手書き入力は、パーソナル・デジタル・アシスタント（ＰＤＡ ）などの装置によって入力される。手書き入力を受信すべく機能する他の装置に は、コンピュータ，モデム，ページャ，電話，デジタル・テレビ，インタラクテ ィブ・テレビ，デジタイジング・タブレットを有する装置，ファクシミリ装置， スキャニング装置および手書き入 力を捕捉する機能を有する他の装置が含まれるが、これらに限定されない。一般 に、ストロークが電子的に捕捉されると、各点はピクセルによって表され、その ためストロークは装置上で一連のピクセルによって表される。 本発明に従って、手書き入力は、英数字，表意文字の形式や、書面の文字また はシンボルの他の形式でもよい。 図面を参照して、第２図および第３図は、ストローク分割がストローク方式の 認識装置に渡された場合の入力の解析が不正確な可能性が高い、英数字手書き入 力のストローク分割を示す。第４図は、第２図および第３図の同じ英数字入力の ストローク分割を示し、ここでストローク分割は本発明の教示によって行われ、 かかるストローク分割は、ストローク方式の認識装置に渡されても正確な解析の 可能性が高い。 ここで、本発明の教示による好適な方法のフローチャートを示す第１図を参照 する。デジタイザまたは他の装置からの手書き入力は、（関連するペンアップ(p enup)またはペンダウン(pendown)状態とともに）ｘｙ座標の形式で受信される（ １１０）。一般に、これらの点はピクセルによって表される。一般に、本方法は 、手書き入力を再サンプリングして、手書き入力の長さに沿って均等に配置され た点を得る（１２０）。第５図は、再サンプリング前の一連の点またはピクセル としての文字「Ｌ」（５００）の例を示す。第６図は、再サンプリング後の一連 の点またはピク セルとしての文字「Ｌ」（６００）の例を示す。再サンプリングは、手書き入力 全体で一定の点間距離(interpoint distance)ｄ（６１０）を利用して行われる 。好ましくは、選択されるｄの値は、手書き入力における中央入力高さ(median input height)がｄのほぼ１５〜３０倍の範囲となるような値である。例えば、 第６図において、選択されるｄの値は、単語における中央文字高さがｄの１５〜 ３０倍の範囲となるような値である。 第１図の好適な実施例は、各再サンプリング点において曲率(curvature)を計 算する（１３０）。第７図は、点Ｒ（７１０）における曲率の計算のためのデー タの図を図式的に示す。再サンプリング点Ｒ（７１０）における曲率は、点Ｐ（ ７２０）からＲの後者（点Ｒ＋１（７３０））までの距離として定義され、Ｒ自 身を介してＲの前者（Ｒ−１，７５０）から直線的に投影することによって得ら れる。この距離は、第７図において要素７４０として示される。手書き入力の終 点における曲率は、対応する最も近い近傍点に等しいと定義される。手書き入力 の内点における曲率も、１つの点ではなく、Ｒから２つの点を投影することによ って（およびＲ−１ではなく、Ｒより２点前の点を利用することにより）算出で き、より確実な推定値を得ることができる。第８図は、第７図に示す点について 得られる曲率値を図式的に示す。 例えば、なだらかな曲げを有する「Ｌ」の前述の例は、 「Ｌ」の２つの「直線」部分がその間の曲げよりもかなり直線的である限り、垂 直および水平ストロークに分割される。次に、曲率は曲げに向かって大きくなり （すなわち、曲率導関数は高くなり）、曲げから離れて小さくなり（すなわち、 曲率導関数は低くなり）、そのため必要に応じて曲げまたは曲げ付近でストロー ク境界が可能になる。 本発明の好適な実施例では、各再サンプリング点について曲率が得られると、 再サンプリング点の曲率のアレイを平滑化して、デジタル化処理によって生じる 既知のアーチファクトを最小限に抑えることができる。実行すべき平滑化の種類 は、特定のデジタル化特性に基づいて選択される標準的な方法である。これには 、ある点の値をその近傍の点で平均化する（その点自体と、それより高い最も近 傍の点を重み付けする）ことや、該当する点の曲率値を算出された平均値と置換 することが含まれる。ここで用いられる平滑化窓(smoothing window)の大きさは 、平滑化処理において重要な情報の損失を最小限に抑えるため、筆跡の低曲率部 分においては広く、また高曲率部分においては狭いことが理想的である。平滑化 されるのは曲率自体であるので、平滑化する１つの好適な方法では、初期曲率を 算出し、これらの曲率に基づいて平滑化し、算出された新たな曲率に基づいて再 平滑化する。 本発明の好適な実施例では、各再サンプリング点について、負の曲率値を−１ で乗じることにより曲率の絶対値が 算出される。好ましくは、絶対値は、実際の曲率値ではなく、曲率導関数を算出 する際に用いられる。なぜならば、本発明の好適な実施例の処理は、曲げが曲が る方向ではなくて、筆跡における曲げの急峻さにのみ関連するためである。 第１図に示すように、プロセスは次に各再サンプリング点における曲率の導関 数を計算する（１４０）。第７図を参照して、点Ｒにおける曲率の導関数は、点 Ｒ＋１における曲率の絶対値から、点Ｒ−１における曲率の絶対値を差し引いて 、２で割った値（すなわち、曲率値の曲線の勾配）として定められる。第９図は 、第７図に示す各点において得られる曲率の導関数を図式的に示す。前述のよう により正確な曲率値を得るため２つ以上の点を利用するのと同様に、曲率の導関 数は、関連する点が存在するより広い窓（５点対３点）と、必要に応じてより狭 い窓（２点対３点）を利用して算出しなければならない。曲率の導関数はインク 部分の終点では算出できないので、終点における曲率の導関数は、対応する近傍 点における導関数に等しいと単純に定義される。 ここで第１図および第９図を参照して、このプロセスの好適な実施例は、次に 曲率導関数値の新たに算出されたアレイを調べて、導関数が局所的最大値にある 点（９１０）（屈曲(inflection)の終端における点および低下しようとする点を 含むように定められる）または導関数が局所的最 小値にある点（９２０）（屈曲の終端における点および増加しようとする点を含 むように定められる）を見つける。（時間的に）局所的最大値の後および局所的 最小値の前の入力の各部分について、この部分の中間点（この部分の弧長につい て）を見つける（９３０）。この中間点は、Ｍ（９３０）として定義される。あ る部分について局所的最大値と局所的最小値との間の差が閾値Ｔ’（９４０）を 越え、かつＭにおける絶対曲率値がある閾値Ｔ”（８２０）を越える場合、点Ｍ はストローク境界として定義される（１５０）。 パラメータＴ’およびＴ”は推定しなければならず、曲率および曲率導関数を 測定する単位に依存する。これらの厳密な値は、誤差許容文字認識装置(error-t olerant character recognizer)を用いる限り問題にならない。本発明の特定の 実施例を作成するためこれらおよび他のパラメータの実験的調整を行う際に、所 望の目標は、特定の文字クラスの複数の事例に対してできるだけ一貫性のある分 割を達成することである。これは、この手順が認識対象の筆跡のさまざまな実サ ンプルをどのように分割するかを調べることにより、経験的に行うべきである。 説明の選択されたストローク境界の他に、ペンが離れる点またはペンが置かれ る点もストローク境界点として選択される。本発明の好適な実施例では、曲率導 関数方式の境界点は、最大２ポイントだけずれることがあり、絶対曲率 値が最大となる点になる場合がある（１６０）。曲率導関数方式の境界点をずら すことにより、曲率の尺度および曲率の導関数の両方が同じストローク境界を生 成するようにすることによって、ストローク境界の位置を改善できる。ただし、 本発明のこの好適な適用例は、３ポイント以下のストロークが生成されない場合 にのみ、与えられた点について行われる。 本発明によるストローク境界点のセットは、対応するストロークのセットを定 める。これらのストロークは、手書き入力の認識のためにストローク方式の文字 認識装置に送ることができる。 本発明およびその好適な実施例は、ストローク分割の新規でより正確な方法に 関する。本発明により、手書き入力の複数の事例において、入力は毎回同様なス トロークのセットに反復的に分割される。例えば、手書き入力が異なる筆者によ って異なる時間にかかれた文字「Ｌ」である場合、本発明およびその好適な実施 例は、異なる筆者の違いにかかわらず、文字「Ｌ」の入力を毎回同様なストロー ク分割境界点に、より正確に分割する。このようなストローク分割は、ストロー ク方式の認識装置によるより正確な解析を行うのに役立つ。 当業者であれば、本発明の多くの実施例が有用であることが理解できよう。１ つの明白な拡張例として、ここで説明した印刷済み手書きの場合から、筆写体(c ursive writing)の場合に拡張することがある。ストロークを分割する実際の方法は、文 字を分割する方法から独立し、そのため筆写体の処理を可能にする方法は、ここ で説明したストローク分割プロセスを容易に利用できる。別の実施例として、走 査された、あるいは「オフライン」筆跡をストロークに分割することがある。本 発明をかかるタスクに適用する簡単な方法では、筆跡を細くして、一定幅のイン ク曲線を得る。時間的情報の欠落のため、交差点と接する曲げとは同じように見 えるため、曲率導関数に基づく点および交差点の両方においてストローク境界を 設定できる。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，Ｍ Ｃ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ，ＳＮ， ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＭＷ，ＳＤ，ＳＺ，ＵＧ)， ＡＭ，ＡＴ，ＡＵ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，Ｃ Ｈ，ＣＮ，ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ ，ＧＥ，ＨＵ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ， ＫＺ，ＬＫ，ＬＲ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，Ｍ Ｎ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＴＪ，ＴＭ，ＴＴ， ＵＡ，ＵＧ，ＵＺ，ＶＮ

Claims (1)

1. 【特許請求の範囲】 １．複数のインク・ピクセルからなる手書き文字を認識する方法であって： 前記各複数のインク・ピクセルについて曲率導関数値を計算して、それにより 各曲率導関数値が対応する前記ピクセルにおける前記絶対曲率の変化率を表す段 階； 各ストローク境界が高い曲率導関数値を有するインク・ピクセルと、低い曲率 導関数値を有する後続インク・ピクセルとの間にあるように、ストローク境界の セットを選択する段階； 各ストローク境界がストロークの終端にあるように、ストロークのセットを見 つける段階； 各ストロークについて少なくとも１つのストローク形状値を計算して、文字形 状セットを生成する段階； 前記文字形状セットを利用して、前記手書き文字の識別を判定する段階； によって構成されることを特徴とする方法。 ２．高い曲率導関数値を有する前記インク・ピクセルは、局所的な最大曲率導関 数値を有し、低い曲率導関数値を有する前記後続インク・ピクセルは、局所的な 最小曲率導関数値を有することを特徴とする請求項１記載の方法。 ３．各ストローク境界は、局所的な最大曲率導関数値を有する前記インク・ピク セルと、局所的な最小曲率導関数値 を有する前記インク・ピクセルとの間の中間点にあることを特徴とする請求項２ 記載の方法。 ４．各ストローク境界は、局所的な最大絶対曲率値の点にあることを特徴とする 請求項１記載の方法。 ５．各点が３つの空間座標値によって構成される、一連の点からなる手書き文字 を認識する方法であって： 前記各複数の点について曲率導関数値を計算して、それにより各曲率導関数値 が前記対応する点における前記絶対曲率の変化率を表す段階； 各ストローク境界が高い曲率導関数値を有する点と、低い曲率導関数値を有す る後続の点との間にあるように、ストローク境界のセットを選択する段階； 各ストローク境界がストロークの終端にあるように、ストロークのセットを見 つける段階； 各ストロークについて少なくとも１つのストローク形状値を計算して、文字形 状セットを生成する段階； 前記文字形状セットを利用して、前記手書き文字の識別を判定する段階； によって構成されることを特徴とする方法。 ６．高い曲率導関数値を有する前記点は、局所的な最大曲率導関数値を有し、低 い曲率導関数値を有する前記後続の点は、局所的な最小曲率導関数値を有するこ とを特徴とする請求項５記載の方法。 ７．各ストローク境界は、局所的な最大曲率導関数値を有 する前記点と、局所的な最小曲率導関数値を有する前記点との間の中間点にある ことを特徴とする請求項６記載の方法。 ８．各ストローク境界は、局所的な最大絶対曲率値の点にあることを特徴とする 請求項５記載の方法。