JPH081660B2 - オンライン手書き図形認識装置 - Google Patents

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は、手書き図形の認識方式に係り、特にオンラ
イン手書き文書作成システムに好適な図形データ入力方
式に関する。

〔発明の背景〕

大型計算機の普及、情報処理端末の高機能化に帰因し
て、計算機の利用者層が急速に拡大している。これに伴
い、計算機への入力手段の１つとして、手書き入力装置
が注目されてきた。

入力される情報は、文字と図形に大別されるが、これ
ら従来例について次に説明する。

〔従来例１〕 手書き文字オンライン認識一般については、日経エレ
クトロニクス:1973,5−７号,P46〜P59に記載されてい
る。このうち、筆跡を短い線分の列として表現し、それ
と辞書の特徴を比較し認識する手法について述べる。

第11図に、手書き筆跡の平滑化処理を示す。入力した
筆跡をP₀〜P₃とすると、まずペンをおろした点P₀を第１
サンプル点S₀とし、このS₀を中心にたとえば、半径５の
円を描き、この円外にある次の点P₁を得る。そしてP₀P₁
間をn:mに分割する点を新たなサンプル点S₁とする。

上記処理をペンが上がるまで続け、サンプル点S₁ない
しS₃を得る。このとき線分S₀S₁と線分S₁S₂の角度が所定
値以下ならばサンプル点S₀からS₂までを一本の線分S₀S₂
とする。この処理を繰り返し、手書きの筆跡を折れ線
（セグメント）で近似する（第12図）。

筆跡に近似したセグメントデータは、第13図に示すよ
うな文字識別樹木を用いて特定の文字として認識する。

この例は、方向コード法と呼ばれる手法で、平滑化処
理でサンプリングした点S₀ないしS₃を次々と継いで筆跡
を複数の線分に分解している。この結果、短い筆跡（例
えば漢字等の字画）に対しては、入力の際の手ぶれが少
ないため、その筆跡の線分化に有効であるが、図形を入
力する際の長い筆跡で生じる手ぶれを吸収するには、不
十分である。つまり手ぶれを吸収する場合には線分比を
複数回繰返す必要があつた。

また、この例では、筆跡数を文字大分類の一要素とし
ているため、続け書きに対しては新たな識別手法を案出
する必要があつた。

〔従来例２〕 他の従来技術について電子通信学会論文誌′84/3 vo
l.J67−D No.3“接続ルールを導入した候補ラテイス法
によるオンライン手書き線図形認識”村瀬ら（電々公社
武蔵野通研）で述べられている図形認識方式について以
下説明する。

上記図形認識方式は「候補ラテイス法」と呼ぶ。第14
図に上記方式のアルゴリズムのフローを示す。

〔処理１ 候補図形抽出〕 入力ストロークの始終点座標Ｐを或るシンボルＧ（全
辞書図形を対象とする）の特徴点と対応付け、シンボル
Ｇの特徴点Pi（ｉ＝１…n,n:シンボルＧの特徴点数）の
全てを通過する一筆書きストローク列の組合わせを複数
発生する。この時、上記入力ストローク列と該発生した
一筆書きストローク列が矛盾しなければ、このシンボル
Ｇを候補図形G_Cとする。これを“一筆書きパターンによ
る候補図形G_Cの抽出”と言い、手書きによる図形の変形
を吸収しながら辞書図形の大分類を行う一方式である。
以下、上記一筆書きストロークを候補ストロークと言
う。

ただし、本方式では、入力図形が大きく傾いていた場
合についての上記特徴点とストロークとの一致検出に関
しては考慮していない。

〔処理２ 相違度の計算〕 本候補ラテイス法では、特徴点とストローク間のユー
クリツド距離に加え、各特徴点に対応するストローク部
分の接線方向についても評価したダイナミツクプログラ
ミング（以下DP）マツチングを採用している。この時、
相違度d²は、 ここで、（x_m,y_m）は、入力ストロークの座標系列 （ｘ′_u(m),y′_u(m)は、候補ストロークの座標系列 ｕ（ｍ）＝ｕ（１）＝1:始点 ｕ（Ｍ）＝M:終点 ｕ（ｉ）＝ｊのとき a:定数 上記（１）式の右辺｛ ｝内第１項、第２項は入力ス
トローク端点と辞書図形の特徴点とのユークリツド距離
を示し、第３項が特徴点（ｘ′_m,y′_ｍ）における、入
力ストロークと候補ストロークの接線方向の差を示す。

〔処理３ 候補ラテイスの採策〕 前記処理１で抽出した図形全てについて前記処理２の
相違度計算を行い、その結果を第15図に示すようなテー
ブルにする。そこで、最適な図形列として、上記テーブ
ルから考えられる全ての図形列の中より、相違度の和が
最も小さいものを選ぶ。

以上のような処理１−３を行うことにより、図形の画
数、筆順、セグメンテーシヨンに依存せずに手書き図形
を認識できるが、 図形の他の図形との続け書き 図形の回転 が発生した時の認識手段については考慮されていない。

〔発明の目的〕

本発明の目的は、図形と接続線が一つに組み合わされ
たストロークが入力された場合においても良好に認識し
得るオンランイン手書き図形認識装置を提供することを
目的とするものである。

〔発明の概要〕

本発明の特徴は、手書きにより入力されたストローク
を複数の線分に分割する線分分割手段と、この分割され
た線分によりなる線分群のうち最初と最後の線分から交
互に１本又は複数本削除した線分の組合せを求める線分
要素再構成手段とを設け、前記求められた線分の組合せ
と辞書図形との間で類似度の評価を行ない、前記辞書図
形に対応する線分群を切り出すことにより、仮りに接続
線が付された図形が続け書きにより入力された場合であ
つても、自動的に図形を切り出し良好に認識することが
可能となり、マンマシン性が向上されることにある。

〔発明の実施例〕

第１図に、本発明の用いたオンランイン手書き図形認
識装置を示す。

ユーザーはタブレツト100上に手書き図形を描く。こ
の時、タブレツト100は、一定時間毎に手書き筆跡の座
標をサンプリングし、図形認識装置200に座標信号を送
出する。

図形認識装置200は、一筆描き（ストローク）毎に上
記サンプリングした上記座標信号を取り込み、以後一筆
描き毎に認識処理を繰返す。認識結果は、入力図形の大
きさ、角度を示すパラメータと共に図形コードが図形表
示装置300へ送られる。

図形表示装置300は、上記認識結果の図形コード等を
ビツトマツプメモリに展開し、ビデオ信号によりCRT400
に表示する。CRT400に表示された上記認識結果は、ビツ
トマツプ信号により上記図形表示装置300に接続したプ
リンタ500により、ハードコピーを取ることが可能であ
り、また図形コード信号を同接続した外部記憶装置600
に格納することも可能である。

これら各部の処理は実時間で実行できるため、本装置
はオンライン手書き図形認識装置として機能することが
できる。

タブレツト100から図形を入力する際に、“画数”
“筆順”“回転”“区切り”等が制約を受けないことと
するため、本発明は、図形の構成単位が線分であり、図
形の形状は当該線分の接続順序、角度差で決定されるこ
とを前提として構成されている。

ここで“画数”とはペンダウンからペンアツプまでを
１ストロークとみなす際の、１つの図形を書く時に要し
たストローク数“筆順”とは図形を描く時のストローク
の順序、“回転”とは標準図形に対する入力図形の角
度、“区切り”とは入力ストローク中の図形に対応する
範囲の指示である。

本発明は大別して２つの特徴部分を有する（第２
図）。即ち、辞書図形とのマツチング処理を行う線分セ
グメント手段と、入力したストロークの中から図形を切
出す一次元線分ダイナミツクプログラム手段である。

線分セグメント手段は、さらにストロークを後述の処
理の基本単位に分割する線分要素化、図形を包むように
追跡してコードリストを生成するコードラツピング、入
力図形の回転に対して普遍的な角度変化による相違度計
算の３つから成る。

この手段により既述の“画数”ないし“回転”の制約
を緩和しており、一方、一次元線分DP手段で線分要素の
再構成を行い、“区切り”の制約を緩和している。

（１） 処理手順概要 入力された手書図形は図示されるフローに従つて処理
される（第２図）。本発明の主たる処理手順について次
に説明する。

ストロークの線分要素化 タブレツトから入力した手書図形は、各ストロークご
とにサンプル点の集合として定義されなければならな
い。

このためにサンプル点S₁からS₂への方向が第３図に示
す方向コードにより量子化され線分の要素化が行われ
る。

コードラツピング 前記で抽出した線分データの互いの端点間の接続情
報に基づいて、各々の対応する方向コードを並べたコー
ドリストL4（第７図）を生成する。このとき丁度、入力
図形を包むように順に線分データをたどることになる。

角度変化による相違度計算 前記で要素化された辞書図形（線分の数で大分類さ
れている）から、前記でコードリスト（L5とする）を
生成し、前記L4の各隣り合う方向コードの差をL5のそれ
と比較する（次式）。f_iは単位相違度を与えることとな
る。

f_i＝｜｛L4（ｉ）−L4（ｉ−１）｝−｛L5（ｉ） −L5（ｉ−１）｝｜ 但し、ｉ＝2,3,…,n n:L5の線分数 ……（１） f_iの値の平均値を、その手書き図形の相違度Ｆと定義
する。Ｆ＝０であれば、入力図形と辞書図形とが一致し
ているとみなされる。

Ｆ値は０ないし10の値をとることが多く、入力図形と
各種の辞書図形とから得たＦ値の最小値を、認識図形に
用いる。

線分要素の再構成 入力図形の中に、図形と接続線との続け書きがある
と、前記の処理ができない。そこで手書きの筆跡を線分
要素化した後、その中から図形に相当する線分要素の組
合わせを切出す必要がある。この切出し操作は、認識処
理全体のループ回数即ち処理時間に直接影響を与える。
このため、効率良く切出し操作が行われることが必要と
なる。

切出し操作は全ての線分要素の組合わせを行う“総当
たり法”が一般的であるが、１つの図形を切出すまでの
操作回数が多くなりがちであるためここでは手書き図形
入力の特徴に注目した“一次元線分ダイナミツク・プロ
グラミング（DP）法”を用いる。この結果、“総当たり
法”に較べて数分の１から10数分の１の操作回数で図形
の切出しが出来る。切出した線分要素は、前記の認識処
理をくり返す。

（２） 処理手順の説明 前記（１）で述べた基本的な図形認識アルゴリズムに
ついて、以下に例を用いて具体的に説明する。

ストロークの線分要素化（第４図） タブレツト100から入力される手書き図形のサンプル
点座標データS₁は、ペンダウンからペンアツプまで（ス
トローク）を一括して本処理に取込まれる。

同図（ａ）で示すように手書き筆跡から得たサンプル
点座標データS₁の始点SP₁ら終点SP_nまでを“未確認領域
（UA）”とし、始点SP₁を“未確認領域開始点（UA
S）”、終点SP_nを“未確認領域終了点（UAE）とする。

次に同図（ｂ）に示すように手書き筆跡Ｓとその始
点、終点を結ぶ直線Ｌにはさまれた領域の面積Ａを求め
る。この面積Ａは幾何学における台形法等を用いると容
易に得られる。

次に算出した面積Ａが予め設定したしきい値A_thより
小ならば、この手書き筆跡Ｓを直線Ｌと見なし、線分登
録処理へ移行する。

同図（ｃ）に示すように上記（３）で面積Ａがしきい
値A_thより大であれば終点を上記UAS点とUAE点の中点に
移動し、再度面積を計算して面積Ａ′を得る。

ここで再び面積Ａ′としきい値A_thの大小関係を調
べ、Ａ′＜A_thならば、同時（ｄ）に示すように現終点
を新たなUAS点として直線Ｌを決定し、Ａ′≧A_thなら
ば、同図（ｅ）に示すように現終点を新たなUAE点とし
て面積Ａ″の算出へ移行する。

前記の処理はUAが無くなる時、即ちUAE点＝UAS点とな
るまで行われる。その後始点から終点を一本の直線とみ
なし、線分登録処理へ移行する。

移行すると同時に、終点を始点及びUAS点に手書き筆
跡Ｓの最終点を終点及びUAE点に再設定する。

以上の処理で線分（Ｌ）と判定された始点、終点の座
標SP_j,SP_k、各点におけるペンのup/downの状態ST_j,S
T_k、始点から終点に向う角度θ_j,k等を同時（ｆ）に示
すような線分リストSeg−listに登録する。これらの処
理は、手書き筆跡Ｓが全て登録されるまで続けられる。

コードラツピング 本処理を行うには、各線分要素の端点間の接続関係を
知る必要がある。そのため入力図形の正規化と、上記接
続関係リストの作成について説明する。

第５図に入力図形（三角形）の正規化の様子を示す。
同図（ａ）で示すように、入力図形から得られるｘ方向
又はｙ方向の大きい方（l_i）を、正規化サイズ（l_n）に
拡大縮小する。従つて、同図（ｂ）に示すように既に作
成した線分リストL1の始点、終点の値をl_n/l_i倍し、正
規化線分リストL2を作成する。

次に線分要素端点間の接続情報の作成を第６図を用い
て説明する。同図（ａ）は正規化後の入力図形（三角
形）である。同図（ｂ）で示すように上記正規化サイズ
（l_n）の10％を線分要素端点間の“接続許容距離”とす
る。そして各線分の端点間の距離が、該接続許容距離よ
り小さければ、その２つの端点間がつながつているとみ
なす。この情報は同図（ｃ）に示す接続リストL3に書込
まれる。この例では、線分要素１は、“始点が線分要素
３の始点と接続している”、“終点は線分要素２の始点
と接続している”という２つの接続情報を持つている。

このようにして作成した線分接続リストL3と、正規化
線分リストL2を用いてコードラツピングが行われる様子
を、第７図を用いて説明する。

各線分要素を包み込む際の始点は、どの線分要素から
でもかまわないが、ここでは最も左の端点から右回りに
線分要素をたどることとする。

同図（ａ）で、入力図形を構成する線分要素の中で、
その端点が最も左にあるものを求める。

前記で求めた端点を新たな始点と考えて、この端点
を含む線分要素と、その端点に接続している他の線分要
素との中から最もｙ方向を向いた線分要素（図では線分
要素１）を選択し、上記新始点から見た方向コード（＝
4,第７図）をコードリストL4に登録する。

線分接続リスト（第６図）から線分要素１の始点は線
分要素３と接続していることが分かるので（ｂ）に示す
ようにたどる方向を向いた時の方向コード（＝28）をコ
ードリストL4に登録する。

以下と同様にコードリストL4を作成する。そして入
力した線分要素の中に未だ１回も包み込みに使用してい
ないものがあれば、からの処理を繰り返す。なければ
本処理を終了する。

本処理の結果、同時（ｄ）に示すように入力図形に関
して右回りにコードリストL4が生成される。

角度変化による相違度計算 コードラツピング処理で得たコードリストL4を用い
て、次の手順に従つて辞書図形とのマツチング処理を行
う。

まずコードリストL4から次式に示す３つの角度差デー
タを得る。

θ_ａ＝L4（２）−L4（１） θ_ｂ＝L4（３）−L4（２） θ_ｃ＝L4（４）−L4（３） 次に入力図形と辞書図形との間の相違度計算法を説明
する（第８図）。

同図（ａ）に示す入力図形の角度差データθ_ａ〜θ_ｃ
と、辞書図形の角度差データθ_１〜θ_３又はθ_１′〜θ
_３′とについて、同図（ｂ）に示す対応するデータ間の
差の絶対値の和f₁,f₂,…を求める。この中で同時（ｃ）
に示すように、入力図形に対しf_i値が最小となる辞書図
形を求め、これを認識図形（同図（ｄ））として出力す
る。

この図の例で、 θ_ａ＝24,θ_ｂ＝−12,θ_ｃ＝−12, θ_１＝23,θ_２＝−12,θ_３＝−11, θ_１′＝20,θ_２′＝−8,θ_３′＝−12 とすると f₁＝2,f₂＝８ となり、このf₁,f₂を線分要素数で平均することによ
り、 f₁/3＝0.67,f₂/3＝2.67 が得られ、この場合の認識図形は図形Ａとなる。

線分要素の再構成 ストロークの線分要素化から前記相違度の計算まで
（第２図、線分セグメント手段に対応）に説明した事項
は、複数の手書き筆跡から図形部分が独立して抽出され
ていることを前提としている。

しかし一般には、フローチヤート等を手書き入力しよ
うとする場合のように、第９図に示すごとく、接続線と
図形とが一続きの筆跡となつていることが頻発する。

そこでダイナミツク・プログラミング（DP）手法を応
用した“一次元線分DP法”による図形の切出しについて
図を用いながら説明する。

この図形切出しは、手書き図形を入力する際、その入
力順序は、接続線→図形、図形→接続線、又は接続線→
図形→接続線の３つのいずれかに場合分けされることに
着目して行われる。入力された複数の線分要素の中で、
最先に入力された線分要素と、最後に入力された線分要
素とを取去ることにより、効率良く図形部分を切出すこ
とができる。

以上の処理について第９図を用いて具体的に説明す
る。

同図（ａ）は、線分要素化後の入力図形を示してい
る。この例では線分要素１を取去る必要がある。同時
（ｂ）に、一次元線分DP法による線分要素の再構成の処
理を示す。

まず最初に線分要素１〜４が本処理に入力される。

第１回目の処理では、最後に入力された線分要素のみ
取り去つている。

第２回目では、最先に入力された線分要素を取り去
り、切出しが成功している。

第３回目以降の処理では、取り去られる線分要素数が
２であり、どのような取り去り方をしても図形の切出し
は行われないことが示されている。

このように、入力した線分要素の最初と最後から１つ
又は複数の線分要素を取り去つて、図形の切出しを効率
良く行つていく。

本実施例によれば、第10図に示されるように、手書き
図形入力の際の、画数、筆順、回転、区切りの制約が大
幅に緩和される効果を有する。

例えば同図（１）に示すように、１つの図形を任意の
回数のストロークで書いた場合、当該図形を図形の単位
である線分要素に分解するため、いわゆる画数の制限が
ない。

また同図（２）に示すように、１つの図形を任意の部
分から書いた場合、線分要素を“コードラッピング”に
より右回りに順序づけるため、筆跡の制約がなくなる。

図形を傾けて入力した場合、隣あう線分要素の角度差
で相違度を評価するため、入力図形の回転が制約されな
い（同図（３））。

〔発明の効果〕

本発明によれば、複数の線分要素から図形部分を切り
出すことができるので、接続線の付いた図形の認識が可
能となり、マンマシン性の向上が図られる。

【図面の簡単な説明】

第１図はオンライン手書き図形認識システムの構成例を
示す図、第２図は本発明の認識手順を示す流れ図、第３
図は方向コードを示す図、第４図は本発明による（面積
法）手書き筆跡の線分要素化の説明図、第５図は図形の
正規化処理の説明図、第６図は接続リストの説明図、第
７図はコードラツピングの説明図、第８図は相違度計算
の説明図、第９図は線分要素の再構成の説明図、第10図
は図形の認識例を示す図、第11図は平滑化を行う従来例
を示す図、第12図は筆跡を折れ線近似する従来例を示す
図、第13図は文字識別樹の例を示す図、第14図は従来の
手書図形認識手順の流れ図、第15図は候補ラテイス方法
を用いた従来例の説明図。 100……タブレツト、200……電算機、600……図形辞
書。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 横山 孝典 茨城県日立市幸町３丁目１番１号 株式会 社日立製作所日立研究所内 (72)発明者 福永 泰 茨城県日立市幸町３丁目１番１号 株式会 社日立製作所日立研究所内 (56)参考文献 特開 昭57−30087（ＪＰ，Ａ) 特開 昭59−57381（ＪＰ，Ａ)

Claims (1)

【特許請求の範囲】
1. 【請求項１】手書き入力される認識対象を構成するスト
   ロークを線分ごとに分割し、該分割された線分よりなる
   線分群と予め蓄えられていた辞書図形との間で類似度の
   評価を行ない、当該評価に基づいて、対応する辞書図形
   を認識結果として出力する手書き図形認識装置におい
   て、 手書きにより入力されたストロークを複数の線分に分割
   する線分分割手段と、 前記分割された線分によりなる線分群のうち最初と最後
   の線分から交互に１本又は複数本削除した線分の組合せ
   を求める線分要素再構成手段とを設け、 前記求められた線分の組合せと前記辞書図形との間での
   類似度の評価を行ない、前記辞書図形に対応する線分群
   を切り出すことを特徴とするオンライン手書き図形認識
   装置。