JPH04336691A - オンライン文字認識装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は文字認識装置において
文字を認識する方法に関し、特に、オンライン文字認識
装置の様に手書き入力文字を高速で認識するための装置
において、二本の線分の端点のみが与えられた場合に、
この線分が交差している否かを判定するための方法に関
する。

【０００２】

【従来の技術】従来から、タブレットやデジタイザなど
を用いて人が手書きで入力する文字をリアルタイムで判
読するオンライン手書き文字認識装置が用いられている
。このような手書き文字認識装置において、入力文字を
判読するために、使用者が入力した２つのストローク（
一回の筆の運びの軌跡）が交差しているか否かを、文字
認識のための特徴として検出する必要が起こる場合があ
る。また、そのようなストロークがともに直線（線分）
であって、その始点および終点のみが座標として得られ
ている場合がある。このような場合、従来の文字認識装
置などにおいては、以下のようにして二元一次連立方程
式の問題として、ストロークが交差するか否かを判別し
ていた。

【０００３】ｘｙ座標平面において線分Ａの始点終点の
座標をそれぞれ（Ａｘ　ｓ　，Ａｙ　ｓ　）、（Ａｘ　
ｅ　，Ａｙ　ｅ　）とする。直線Ｂの始点終点の座標を
それぞれ（Ｂｘ　ｓ　，Ｂｙ　ｓ　）、（Ｂｘ　ｅ　，
Ｂｙ　ｅ　）とする。線分Ａは、以下の式（１）によっ
て表わされる直線の一部分であるものとする： Ｙ＝αＡ　Ｘ＋βＡ　…（１） 線分Ｂは、以下の式（２）で表わされる他の直線の一部
分で表わされるとする：Ｙ＝αＢ　Ｘ＋βＢ　…（２）
式（１）、（２）の２つの式を二元一次連立方程式とし
て解くことにより、式（１）、（２）で表わされる直線
が交わるか否か、交わる場合にその交点がどこに存在す
るかを知ることができる。二元一次連立方程式に解が存
在し、かつ４点（Ａｘ　ｓ　，Ａｙ　ｓ　）、（Ａｘ　
ｅ　，Ａｙ　ｅ　）、（Ｂｘ　ｓ　，Ｂｙ　ｓ　）、（
Ｂｘ　ｅ，Ｂｙ　ｅ　）で表わされる領域内に解が存在
する場合のみ、線分Ａと線分Ｂとが交差していると判断
される。

【０００４】

【発明が解決しようとする課題】しかし、上述の従来の
方法においては、二元一次連立方程式を解く必要が有る
ため計算量が多く、特にオンライン手書き文字認識装置
の様に応答性が要求される装置においては処理速度がお
そくなり不適当であった。

【０００５】それ故にこの発明の目的は、二つの線分の
端点のみのデータが得られたときに、これら二つの線分
が交差しているか否かを高速で判定するための方法を提
供することである。そしてより好ましくは、従来よりも
簡単な方法で上述の判定を行える様にすることである。

【０００６】

【課題を解決するための手段】請求項１に記載の二本の
線分が交差するか否かを判定するための方法は、第一お
よび第二の二本の線分のそれぞれの端点を特定する為の
座標値を取得するステップと、第一の線分の端点の各々
と第二の線分の端点の各々とを直線で連結することによ
って得られる四角形が凸四角形であるか否かを判定する
ステップと、得られた四角形が凸四角形であるか否かの
判定結果に基づいて第一及び第二の線分が相互に交差す
るか否かを判定するステップとを含む。

【０００７】請求項２に記載の二本の線分が交差するか
否かを判定するための方法は、請求項１に記載の方法で
あって、得られた四角形が凸四角形であるか否かを判定
するステップは、四角形の任意の隣接する二辺の交わる
角度が全て所定の関係を満足しているか否かを判定する
ステップと、四角形の隣接する二辺の交わる角度が全て
所定の関係を満足していると判定された場合には四角形
が凸四角形であると判断し、それ以外の場合には四角形
が凸四角形でないと判断するステップとを含み、第一及
び第二の線分が相互に交差するか否かを判定するステッ
プは、四角形が凸四角形であると判断された場合には二
本の線分が相互に交差すると判断し、それ以外の場合に
は二本の線分が相互に交差しないと判断するステップを
含む。

【０００８】

【作用】請求項１に記載の二本の線分が交差するか否か
を判定する為の方法においては、第一及び第二の二本の
線分のそれぞれの端点を特定する為の座標値に基づき、
第一の線分の端点の各々と第二の線分の端点の各々とが
直線で連結され、四角形が得られる。得られた四角形が
凸四角形であるか否かが判定され、その判定結果に基づ
いて第一及び第二の線分が交差するか否かの判定が行わ
れる。

【０００９】請求項２に記載の二本の線分が交差するか
否かを判定するための方法においては、四角形の任意の
隣接する二辺の交わる角度が全て所定の関係を満たして
いるか否かが判定され、全て所定の関係を満たしている
と判定された場合には四角形は凸四角形であると判断さ
れる。全てが所定の関係を満たしているわけではない場
合には、四角形は凸四角形ではないと判断される。そし
て、四角形が凸四角形であると判断された場合には二本
の線分は相互に交差すると判断され、それ以外の場合に
は二本の線分は相互に交差しないと判断される。

【００１０】

【実施例】図１は、本発明にかかる方法を実施するため
の文字認識装置のブロック図である。図１を参照して、
この文字認識装置は、タブレットやデジタイザなどから
なり、使用者が入力する手書き文字のストロークを一連
の点列の座標値として取得するための座標取得部１と、
座標取得部１から与えられる座標に基づき、交差してい
るか否かを判定すべき２つの線分について、後述するよ
うな角度演算を行なうための角度演算部２と、角度演算
部２にそれぞれ接続され、角度演算部２によって演算さ
れた角度の値に基づいて所定の加算処理を行なうための
第１カウンタ３および第２カウンタ４と、第１カウンタ
３および第２カウンタ４に接続され、第１カウンタ３お
よび第２カウンタ４の内容に基づき、２つの線分が交差
しているか否かを後述する判定方法により判定するため
の交差判定部５と、交差判定部５の判定結果に基づいて
、入力された文字を認識するための文字認識部６と、文
字認識部６によって認識された文字を表示するための表
示部７とを含む。

【００１１】角度演算部２において行なわれる角度演算
の詳細を説明する前に、角度計算の際の規約を説明して
おく。図２に示されるように、２つの線分Ａ、Ｂが、と
もに有向なものであるとする。線分Ａの終点と線分Ｂと
の始点とが一致している。この場合、図２（ａ）、（ｂ
）に示されるように、線分Ａ、Ｂがなす角度αは、線分
Ａをその終点より先に延長した直線と、線分Ｂとが、時
計方向になす角度であるものとする。

【００１２】以下、角度演算部２および第１カウンタ３
、第２カウンタ４において行なわれる処理を詳細に説明
する。図３を参照して、座標取得部１（図１）から入力
された線分（ストローク）が、始点ａｓと終点ａｅとで
定義されるものとする。入力された他の線分Ｂが、始点
ｂｓと終点ｂｅとで定義されているものとする。各点ａ
ｓ、ａｅ、ｂｓ、ｂｅの座標値は、座標取得部１（図１
）によって角度演算部２に与えられる。

【００１３】角度演算部２は、まず、ａｓ、ｂｓ、ａｅ
の座標値から、点ａｓを始点とし点ｂｓを終点とする有
向線分と、点ｂｓを始点とし点ａｅを終点とする有向線
分とのなす角度を図２に示されるような規約に従って計
算する。

【００１４】角度演算部２は、計算の結果得られた角度
が０度以上１８０度未満であれば図１の第１カウンタ３
に１を加え、１８０度を越えて３６０度未満であれば第
２カウンタ４（図１）に１を加える。角度が１８０度で
ある場合にはいずれのカウンタ３、４にも何ら処理はさ
れず、次の角度計算の処理に移る。

【００１５】上述のように与えられた３点で定められる
２つの有向線分についての角度計算は、点ｂｓ、ａｅ、
ｂｅについて、点ａｅ、ｂｅ、ａｓについて、点ｂｅ、
ａｓ、ｂｓについて、それぞれ行なう。したがって、合
計４回の角度計算処理を行なうことになる。この処理の
結果第１カウンタ３には計算された角度が０度以上１８
０度未満であるような点の組合せの数が、第２カウンタ
４には角度が１８０度を越えて３６０度未満であるよう
な点の組合せの数が格納されていることになる。

【００１６】交差判定部５は、第１カウンタ３あるいは
第２カウンタ４のいずれかの内容が４である場合に、処
理対象となっている線分Ａ、Ｂが交差していると判断す
る。これは、以下のような理由による。図３を参照して
、２つの線分Ａ、Ｂが交差している場合、点ａｓ、ｂｓ
、ａｅ、ｂｅ、ａｓの順序で各点を結んで得られた四角
形は凸四角形となる。そしてそのときは、点ａｓと点ｂ
ｓとを結ぶ線分を延長して得られる直線と、点ｂｓと点
ａｅとを結んで得られる線分とのなす角が１８０度より
も大きくなる。同様にこの四角形の他の頂点のすべてに
おいても、計算によって得られる角度はいずれも１８０
度より大きくなる。

【００１７】一方、線分Ａ、Ｂの始点および終点を、図
３に示されるような順番と異なる順番で接続すると、計
算される角度は以下のようになる。図４を参照して、点
ａｓ、ｂｅ、ａｅ、ｂｓ、ａｓの順序で各点を連結した
場合、図２に示されるような規約に従って各頂点でこの
凸四角形の隣接する２つの辺がなす角度を計算すると、
いずれも１８０度よりも小さくなる。すなわち、図３あ
るいは図４に示されるように２つの線分Ａ、Ｂが交差す
る場合には、線分Ａの始点および終点と、線分Ｂの始点
および終点とを、同一の線分の始点、終点が互いに隣接
しないような順序で結んで得られた四角形は凸四角形と
なり、図２に示されるような規約に従って各頂点での角
度を計算すると、いずれも１８０度を越えて３６０度未
満であるか、いずれも０度以上１８０度未満であるかの
２つの場合になる。

【００１８】これに対し、図５に示されるように線分Ａ
と線分Ｂとが交差しない場合には、線分Ａと線分Ｂとの
終点および始点を、それぞれの線分の始点および終点が
隣接しないような順序で順に連結して得られた四角形は
、図３、図４に示される場合と異なって凸四角形とはな
らない。そのため、図２に示されるような規約で各頂点
において２辺のなす角度を計算すると、すべての角度が
０度以上１８０度未満となったり、すべての角度が１８
０度を越えて３６０度未満となったりすることはない。 たとえば図５に示されるように、角度の１つが１８０度
を越え、他の３つの角度がいずれも０度以上１８０度未
満となる。

【００１９】したがって、図２に示されるような条件に
従って４つの角度を計算し、その４つの角度がいずれも
０度以上１８０未満であるか、４つの角度がいずれも１
８０度を越え３６０度未満であれば２つの線分Ａ、Ｂが
交差していると判断することができる。

【００２０】角度計算は以下のようにして行なわれる。 図６を参照して、線分Ａ、線分Ｂが原点Ｏで交わってお
り、ｘ軸と線分Ａとのなす角度がα、ｘ軸と線分Ｂとの
なす角度がβであるものとする。線分ａと線分ｂのなす
角度はγであるものとする。線分Ａの終点と線分Ｂの終
点とからｘ軸に下ろした垂線の足をそれぞれＳ、Ｔとす
る。この場合、図６に示される各量の間には、以下のよ
うな関係が成り立つ：

【００２１】

【数１】

【００２２】「０＜γ＜１８０度」と「ｓｉｎγ＞０」
とは同値であり、「１８０度＜γ＜３６０度」と「ｓｉ
ｎγ＜０」とは同値である。したがって、式（３）の右
辺の値を計算し、その符号を求めることにより、角度γ
の値の範囲を知ることができる。

【００２３】図１に示されるような文字認識装置は、実
際にはコンピュータ上で動作するプログラムによって実
施されることが多い。図７は、そのようなコンピュータ
プログラムのフローチャートの一例である。図７を参照
して、ステップＳ０１において、２つの線分Ａ、Ｂの始
点および終点の座標が角度演算部２にセットされる。制
御はステップＳ０２に進む。

【００２４】ステップＳ０２においては、以下で説明さ
れる処理がすでに４回繰返されたか否かが判断される。 判断の答がＹＥＳであれば制御はステップＳ０８に進み
、さもなければ制御はステップＳ０３に進む。

【００２５】ステップＳ０３においては、角度演算部２
にセットされた３点の座標値に基づいて、その３点によ
って定義される２つの線分のなす角度が計算される。制
御はステップＳ０４に進む。

【００２６】ステップＳ０４においては、次の角度計算
に備えて、角度演算部２に与えられる座標が次に処理す
るべき３点の座標に変化される。制御はステップＳ０５
に進む。

【００２７】ステップＳ０５においては、ステップＳ０
３において得られた角度と１８０度との大小が比較され
る。計算により得られた角度が１８０度未満であれば制
御はステップＳ０６に進み、得られた角度が１８０度を
越えていれば制御はステップＳ０７に進み、それ以外の
場合には制御はステップＳ０２に戻る。

【００２８】ステップＳ０６においては、第１のカウン
タ３（図１）に１加算され、制御はステップＳ０２に戻
る。

【００２９】ステップＳ０７においては、第２のカウン
タ４（図１）に１加算され、制御はステップＳ０２に戻
る。

【００３０】ステップＳ０２における判断の結果制御が
ステップＳ０８に進んだ場合、線分Ａ、Ｂの始点および
終点を結んでできる四角形の４つの頂点のすべてについ
て角度計算が終了したということであるから、以下の処
理において交差の判定が行なわれる。ステップＳ０８に
おいては、第１のカウンタ３または第２のカウンタ４の
いずれかの値が４であるか否かが判断される。判断の結
果答がＹＥＳであれば制御はステップＳ１０に進み、さ
もなければ制御はステップＳ０９に進む。

【００３１】ステップＳ１０においては、前述の説明で
明らかなように２つの線分Ａ、Ｂが交差しているという
判断がされる。

【００３２】一方、ステップＳ０９においては、２つの
線分Ａ、Ｂは交差しないという判断がなされる。

【００３３】以上のような制御の構造を有するプログラ
ムをコンピュータ上で動作させることにより、本発明に
かかる方法を実施することができる。

【００３４】以上、この発明が図面を参照して実施例に
基づき説明された。しかし、この発明は上述の実施例に
は限定されず、この他にも様々な変形を加えて実施する
ことができる。たとえば、上述の実施例中においては、
線分Ａ、Ｂの始点および終点を結んでできる四角形のす
べての頂点において角度計算がされた。しかし、場合に
よっては４つの頂点のすべてで角度計算をする必要がな
い場合もある。たとえば、上述の説明からも明らかなよ
うに、４つの頂点で計算された角度がすべて同じ条件を
満たす場合に限り２つの線分Ａ、Ｂが交差すると判断さ
れる。したがって、処理途中においていずれかの２つの
頂点で得られた角度が、一方は１８０度より大きく、他
方は１８０度よりも小さいということが判明したならば
、その時点で線分Ａ、Ｂは交差しないと判断することが
できる。４つの頂点において得られた角度がすべて同一
の条件を満たすことはあり得ないからである。このよう
にすれば、角度計算をしないですむことがあるために処
理が高速化される。

【００３５】

【発明の効果】以上の様に請求項１に記載の二本の線分
が交差するか否かを判定するための方法においては、第
一及び第二の二本の線分のそれぞれの端点を特定する為
の座標値に基づき、第一の線分の端点の各々と第二の線
分の端点の各々とが直線で連結されて得られた四角形が
凸四角形であるか否かが判定され、その判定結果に基づ
いて第一及び第二の線分が交差するか否かの判定が行わ
れる。二本の線分を表わす二つの一次方程式を連立させ
て解くことによりその交点を求め、交点が所定の領域内
に或るか否かを判定する従来の方法と比較して、四角形
が凸四角形であるか否かを判断するだけで線分の交差の
有無の判定が行えるため計算量が少なくて済む。そのた
め、本発明に係る方法により高速で判定処理を行うこと
が出来る。

【００３６】請求項２に記載の二本の線分が交差するか
否かを判定するための方法においては、四角形の任意の
隣接する二辺の交わる角度が全て所定の関係を満たして
いる場合のみ四角形は凸四角形であると判断される。そ
して、その場合のみ二本の線分は相互に交差すると判断
される。判定の為には４回の角度計算ですむため、従来
の方法に比べ遙かに計算量が減少し、判定処理を高速、
かつ簡単に行うことが出来る。

【図面の簡単な説明】

【図１】本発明にかかる方法を実施するための文字認識
装置のブロック図である。

【図２】本発明の実施例中において行なわれる角度計算
のための規約を説明するための図である。

【図３】線分Ａ、Ｂの始点および終点を連結することに
より得られる四角形と、その各頂点での角度計算の様子
を示す図である。

【図４】図３に示される順序と異なる順序で線分Ａ、Ｂ
の始点および終点を連結した場合の図である。

【図５】２つの線分Ａ、Ｂが交差しない場合の、線分Ａ
、Ｂの始点および終点を連結して得られる四角形と各頂
点での角度計算を示す図である。

【図６】角度計算を行なう方法を説明するための図であ
る。

【図７】本発明にかかる方法をコンピュータによって実
現する際のプログラムのフローチャートである。

【符号の説明】

１　　座標取得部 ２　　角度演算部 ３　　第１カウンタ ４　　第２カウンタ ５　　交差判定部 ６　　文字認識部 ７　　表示部

Claims (2)

【特許請求の範囲】
1. 【請求項１】　　第一および第二の二本の線分のそれぞ
   れの端点を特定する為の座標値を取得するステップと、
   前記第一の線分の端点の各々と前記第二の線分の端点の
   各々とを直線で連結することによって得られる四角形が
   凸四角形であるか否かを判定するステップと、前記得ら
   れた四角形が凸四角形であるか否かの判定結果に基づい
   て前記第一及び第二の線分が相互に交差するか否かを判
   定するステップとを含む、二つの線分の交差を判定する
   ための方法。
2. 【請求項２】　　前記得られた四角形が凸四角形である
   か否かを判定するステップは、前記四角形の任意の隣接
   する二辺の交わる角度が全て所定の関係を満足している
   か否かを判定するステップと、前記四角形の隣接する二
   辺の交わる角度が全て前記所定の関係を満足していると
   判定された場合には前記四角形が凸四角形であると判断
   し、それ以外の場合には前記四角形が凸四角形でないと
   判断するステップとを含み、前記第一及び第二の線分が
   相互に交差するか否かを判定するステップは、前記四角
   形が凸四角形である場合には前記二本の線分が相互に交
   差すると判断し、それ以外の場合には前記二本の線分が
   相互に交差しないと判断するステップを含む、請求項１
   に記載の二つの線分の交差を判定するための方法。