高速な二次曲線当てはめの精度を改良した実用的な手書き曲線認識法の提案 信州大学大学院 工学系研究科 情報工学専攻 井澤研究室 10TA531K 竹花卓 1 はじめに 二次曲線弧の描画は，一連の入力点列があれば それを線形補間した点列から二次曲線への距離の 足を繋げばよい．最短距離よりも近似距離を用い ることで，図 1 右のようなほぼ同様の二次曲線弧 が約 1/10 の計算時間で描画できるようになった． 近年，手書きのようなノイズを含む点列データ から，コンピュータを用いて滑らかな曲線で認識 したいという需要が高まっている．特に，タッチパ ネル端末などの非力な環境において，指先の軌跡 を単純な関数で高速に計算できれば様々な応用が 期待できる．しかし，既存の最小自乗 3 次スプラ イン手法では，制御点を指定する必要から自動化 が難しく，軸ごとに異なる 3 次関数での認識とな るため，距離や精度の計算も扱いづらい．そこで， 単純な直線当てはめを用いた折れ線での認識をふ まえて，その線分を二次曲線弧に拡張する手法を 提案する．本手法は，まず，点から二次曲線への 最短距離について，高速計算できる近似距離で全 て置き換える．次に，従来の高速な二次曲線当て はめの問題点であった精度の悪さを，近似距離に 対する非線型最適化で改良する．最終的に，二次 曲線弧同士を連結させる制約式を用れば，当ては め 1 回ごとに高々4 次方程式を解く計算で，許容 精度のみを指定した自動的な曲線認識ができるこ とを，数値計算ソフト Scilab 5.4.1 で実験し示す． 2 図 1: 点から二次曲線への距離と足での描画 3 入力される点列に対して最適な二次曲線を当て はめる手法は，文献 [2] 等で最短距離の評価値を 非線型最適化するような複雑な研究がされている． 本手法は，高速性の追求のため，従来手法 [1] の 基本的な最小自乗当てはめ（式 (3)）を基にする． 入力点から二次曲線への近似距離 σs = ( √ √ Qc + 2F[x′ ,y′ ] ( ) Q Qc −4F[x′ ,y′ ] (a+c)− Qdc ( Qc = (2ax′ + by′ + d)2 + (bx′ + cy′ + e)2 0 ) 0 0 0 0 (3) 0 式 (3) の一般化固有値問題で帰着される 5 次方程 ∑ 2 σ 式解に対応して求まるのは，ある自乗平均値 n s が極値をとる二次曲線の解の候補である．特に， 極小となる第 1 候補と第 2 候補では，ノイズが大 きい点列に対して，図 2 左のようにどちらが良い 当てはめか判別が難しいような場合もあった． (1) ところで，ある点から二次曲線への最短距離は， 垂線を下ろした足の xy 座標が 4 次方程式に帰着 され解けるので，通常は 4 つの足から最短を選ぶ 計算になる．この最短距離を各点ごとに毎回評価 するのは大変なため，図 1 左のような最急降下法 に基づく近似距離を求める．それは，点 (x′ , y′ ) か ら F[x′ , y′ ] の勾配方向に F[x, y] = 0 まで到達する 小さい方の距離 σi として，2 次方程式に帰着され 式 (2) のように一意に導出できた（Qc は後述）． σi = F[x′ ,y′ ] √ , Qc ∑ ′ ∑ ′ ′ ∑ 4x′2 2x 2x y i i i i 0 0 0 n n n x′2 x′2 T ∑ ∑ ∑ ∑ ∑ i i ′ ′ 2x′ y′ (x′2 +y′2 ) 2x′ y′ y x x′ y′ x′ y′ a i i i i i i i i 0 a b n n n n n n i i i i b ( ∑ 2 ) ∑ ∑ ∑ ∑ y′2 y′2 c σ s 2y′ c 2x′ y′ 4y′2 1 i i i i 0 d i i d ∼ 0 0 n n ∑ n n n e ∑ i=1 xi′ xi′ e 2x′ y′ ′ ′ f i i 0 1 0 0 f yi yi n ∑n ′ ∑ ′ x 2y 1 1 i i 0 0 1 0 n n 二次曲線とは， xy 平面上において式 (1) の一般 的な 2 元 2 次方程式 F[x, y] = 0 を満たす点の軌跡 である．パラメータ (a, b, c, d, e, f ) の値によって， 正円・楕円・放物線・双曲線・直線を含む局所的 には任意の曲線弧を表せることが知られている． F[x, y] = ax2 + bxy + cy2 + dx + ey + f 二次曲線当てはめの精度の改良 (2) ) Qd = ae2 − bde + cd2 − (4ac − b2 )( f − F[x′ , y′ ]) 図 2: 従来手法のイメージと提案手法での合成 1 信州大学大学院 工学系研究科 情報工学専攻 2013 年度 修士論文発表要旨 最適な二次曲線とは，式 (2) の近似距離の自乗 平均値を最小化する解が望ましい．そこで，点と 二次曲線が近い F[x′ , y′ ] → 0 という近似を用いた ∑ 2 ∑ 2 ( ( )) σi σs Qd 2σ s √ ∼ n 1 + Q (a + c) − Qc を最小化する n 本手法の単純な実装では当てはめる点が増える ほど遅くなるが，図 5 のような曲線認識ができた． c 探索方向（式 (4)）において最急降下法を行う． (∑ ) ) ( ∑ 2 ) ∑ xx′′2y′ 2 ( σ2i σs Qd y′2 6σ s ∼∇ + (a + c) − =∆ x′ nQ n n Qc c y′ ∇ (4) 1 式 (3) の解の第 1 候補と第 2 候補から個別に最 急降下法を行ったところ解はそれぞれ特に変化し なかったため，式 (5) のような解の合成を行った． a1 a2 a ∑ 2 ∑ 2 b1 b2 b ∆ σ ∆ σ 1 2 c c c i1 i2 + β 2 − d = α d11 − d 2 e1 ∆T ∆1 n e e2 ∆T ∆2 n (5) 1 2 f f1 図 4: 折れ線と従来手法と提案手法の結果比較 f2 ∑ 式 (5) の α, β は F[x′ , y′ ] = 0 の制約から一意 に求まる．精度の比較として，長さ約 2 のある二 次曲線に対して，図 3 右のように最短距離の方向 に正規分布ノイズを加えた点列を作り，従来手法 と本手法で当てはめた二次曲線との近似距離同士 の足のズレ（図 3 左）を評価したところ，多くの 場合で図 3 右のように精度が良くなる傾向があっ た．最短距離同士の足のズレでも同様であった． 表 1: 折れ線と従来手法と提案手法の計算時間 折れ線 従来手法 提案手法 [秒] 0.76 ± 0.52 3.28 ± 2.20 図 5: 本提案手法による手書き曲線認識の例 5 おわりに 本稿では，手書き入力点列に対して許容精度以 内の二次曲線弧の連結として次々に認識する方法 を提案した．提案手法は，同様の問題でよく用い られる折れ線での単純な認識に比べ，数十倍の計 算時間が必要となる分，より長く適切な曲線弧の データとして描画で確認しながらリアルタイムで 認識できる可能性がある．応用としては，なぞっ て入力した点列との距離の評価や，認識された二 次曲線弧の修正など後処理も容易に考えられる． 今後の課題としては，入力される点列の許容精 度について，いくつか並行計算して選択したり， 環境ごとで事前に適切に算出する手法を考えたい． また，当てはめの精度を向上させるために，比較 的距離の離れている異常点を除外したり，さらに， 当てはめの速度を向上させるために，二次曲線解 の合成計算において探索方向を毎回総和しなけれ ばならない点を間引くような方法を試したい． 図 3: 2 つの二次曲線当てはめの精度の評価 4 0.16 ± 0.12 連結手法の実験と計算時間 前述の手法をふまえて，当てはめた二次曲線弧 の終点 ( xˆ, yˆ ) が次に当てはめる二次曲線弧の始点 となるように連結する．それは，常に制約式 f = −a xˆ2 − b xˆyˆ − cˆy2 − d xˆ − eˆy を満たすように式 (3) と 式 (5) の f を消去して当てはめを行えば可能であ る．さらに，滑らかに連結させるために始点での 傾きも制約したところ，実用的でないほど精度が 悪くなった．そこで，比較的滑らかに連結させる ために，連結させる前後の 3 点の部分だけ別の単 純な線型連立方程式での二次曲線当てはめをする 手法を提案する．図 4 は，200pixel 以内の入力領 域でノイズ 2pixel の曲線に対し許容精度 2.3pixel で折れ線認識と従来手法と提案手法を比較した結 果である．同様の条件で 200 回試したところ，計 算時間は表 1 のように約 3∼5 秒程度であった． 参考文献 [1] P.D. Sampson, ”Fitting conic sections to very scattered data: An iterative refinement of the Bookstein algorithm”, Computer Vision Graphics and Image Processing, 18:97–108, 1982. [2] 金谷健一, 菅谷保之, ”幾何学的当てはめの厳密な最尤推定の 統一的計算法”, 情報処理学会論文誌:コンピュータビジョンと イメージメディア, Vol.2, No.1(2009-3), pp.53–62. 2
© Copyright 2024 ExpyDoc
