ジェスチャーが描くかたちを判定する方法
大垣憲俊
ジェスチャーが描くかたちを判定する方法について質問させて頂きます。
android-sdkの「GestureBuilder」のサンプルでお分かりのように、
GestureOverleyView上で、指で記号を描く「ジェスチャー」によって
アプリを操作することができます。
そこで、
# そのジェスチャーが、円または楕円を描いていると判定するには、
# どうすればよいでしょうか。
ジェスチャーデータは１つのストローク（一筆書き）が各々、
次のような形式です。
x1,y1,t1, x2,y2,t2, x3,y3,t3, ... xN,yN,tN
ここで、xはx座標の値、yはy座標の値、tはx,yを通った時間です。
お教え頂ければ幸せに思います。
よろしくお願いいたします。
（参考までに...）
直線か斜め線かどうかの判定は、以下のようにしています。
直線かどうかは、
xごと、yごとに、となり同士の値の差（x1とx2の差, x2とx3の差, ...）が
-5から+5の範囲内のものを直線の一部分としてカウントし、
その合計を、そのストロークに含まれるxまたはyの個数で割った値が
0.6以上（６割が直線部分という意味）の場合に直線と見なしています。
斜め線かどうかは、以下の計算式を使って、
角度 = (float) (Math.atan2(dy, dx) * 180.0f / Math.PI);
（dx, dy は座標xまたはyの差）
まず、そのストロークの始点と終点によって、全体の角度を求め、
次に、となり同士の差（x1とx2の差=dx、y1とy2の差=dy）から角度を求めて、
それを全体の角度で割った値が (0.8f <= r && r < 1.3f) の場合に、
斜め線と見なしています。
（斜め線をさらに右上がりか右下がりかまで判定していますが、ここでは割愛します）
pie
最新の位置から2点遡って2本の直線を作り、その間の角度を求めれば
進行方向に対してどっちに曲がってるかが分かると思います。
何点か連続して同じ方向に曲がって元の近くに帰ってくれば
円ないし楕円軌道を描いてると判定するのはどうでしょうか
大垣憲俊
>進行方向に対してどっちに曲がってるかが分かると思います。
ohisamallc
山形は、天気良いです。
がんばろう東北。
内角が求められるなら、
内角の和が180度なら三角形、360度なら四角形で
円なら1000を越えるはず。
> --
> このメールは Google グループのグループ「日本Androidの会」の登録者に送られ
て
> います。
> このグループに投稿するには、android-g...@googlegroups.com にメール
を
> 送信してください。
> このグループから退会するには、
> android-group-j...@googlegroups.com にメールを送信してくださ
い
> 。
> 詳細については、http://groups.google.com/group/android-group-japan?hl=ja
か
> らこのグループにアクセスしてください。
>
>
>
大垣憲俊
五嶋克典 Gotoh,Katsunori
私も現在、同様の実装を考えております。
移動した２地点間と、回転の中点の内角、半径は中点からの距離で
考えています。
この、サイトが参考になりました！
３点の座標から簡単に角度と回転方向を求める
http://www5d.biglobe.ne.jp/~noocyte/Programming/Geometry/RotationDirection.html
大垣憲俊
>この回転が右回りか左回りかを判別せよ．
>S ≡ (Px - Cx) * (Qy - Cy) - (Py - Cy) * (Qx - Cx)
>とする．S＞0 なら左回り，S＜0 なら右回り，S＝0 ならば C，P，Q は一直線上にある．
>なので，両者を併用すると簡単に角度および回転方向 (-180°＜ θ ≦ +180°) が求まる．
ryota
下記に関して、自分の場合は以下のようなアルゴリズムで実装するかと思います。
1. x(i), y(i)それぞれの平均値(Mx, My)を計算する → この平均値が円であった場合の中心点になる
2. 座標(x(i), y(i))と予想中心点(Mx, My)の距離の平均値rを計算する → この距離の平均値が円であった場合の半径になる
3. 全ての入力された各座標(x(i), y(i))と予想中心点(Mx, My)に対してその距離R(i) がｒ－ｆ＜Ｒ（ｉ）＜ｒ＋ｆを
満たせば入力x(i), y(i)は円であると判断できる. ｒ－ｆ＜Ｒ（ｉ）＜ｒ＋ｆを満たさない点が存在すれば円ではない。
ちなみに, fは閾値であり, これを大きくすれば, 円と判定する割合が大きくなるが精度は下がり、小さくすれば円と判定する
割合が小さくなり精度は上がるかと思います.
いかがでしょうか？
2011年6月3日18:47 大垣憲俊 <noritos...@gmail.com>:
> --
> このメールは Google グループのグループ「日本Androidの会」の登録者に送られています。
> To view this discussion on the web visit
> https://groups.google.com/d/msg/android-group-japan/-/ZWtvYmZrNG1sOWtK.
> このグループに投稿するには、android-g...@googlegroups.com にメールを送信してください。
> このグループから退会するには、android-group-j...@googlegroups.com
> にメールを送信してください。
> 詳細については、http://groups.google.com/group/android-group-japan?hl=ja
> からこのグループにアクセスしてください。
>
--
+----------------------------+
| 山田良太
| 1987...@gmail.com
| 080-5165-1281
| twitter: @1987yama3
+----------------------------+
大垣憲俊
ryota
以前の書き込みで、書いた円判定アルゴリズムですが、正しく判定できなさそうなので、投稿しておきます。
数列(x(i), y(i), t(i))（0<=i<=n）が円を描くかどうかの判定に対して, 先の投稿ではt(i)（0<=i<=n）の存在を放置して
進めていました. 先のアルゴリズムでは, 座標(x(i), y(i))は等間隔に取得しており, さらに, 座標の移動速度も一定である
という前提で進めていました. t(i)が一定間隔というのは, 前提として正しいかもしれませんが, 座標の移動速度が
一定である, という前提は正しくないかと思います. 例えば, 正円の右上をゆっくり描いた場合, x, y座標それぞれの
平均値(=円の中心)は右上のほうに寄ってしまい, 正しく判定できないこともあるかと思います.
これを考慮するのであれば, 隣接する点A, Bの距離が他の隣接点間の距離に比べて小さい場合, AまたはBの点を消去
して計算するのでも問題ないかもしれません.
2011年6月4日9:53 大垣憲俊 <noritos...@gmail.com>:
> --
> このメールは Google グループのグループ「日本Androidの会」の登録者に送られています。
> To view this discussion on the web visit
> https://groups.google.com/d/msg/android-group-japan/-/enk0c3d6UDN3allK.
大垣憲俊
> 座標の移動速度が一定である, という前提は正しくないかと思います.
> 平均値(=円の中心)は右上のほうに寄ってしまい, 正しく判定できないこともあるかと思います.
> これを考慮するのであれば, 隣接する点A, Bの距離が他の隣接点間の距離に比べて小さい場合, AまたはBの点を消去
> して計算するのでも問題ないかもしれません.
ということは、すべての座標をつないだ線分から、同一の長さで座標を再サンプリングすれば良いですね。
ご丁寧にフォローをありがとうございます。
たいへん参考になりました。
S.Takahashi
最近、入会したばかりですが、よろしくお願いします。
画像処理の分野で用いられる「円形度」は利用できませんでしょうか？
円形度は、ある閉領域に対して、４π×（面積）／（周囲長の２乗）で得られる値ですが、
１に近いほど真円に近い値となります。
領域が閉じていない場合は補間するなど若干の工夫が必要ですが、適当な範囲の閾値を
設定すれば、丸っぽいナニカであることは判定できるように思います。
面積は適当にポイント間を補間してラべリング処理を行うとよいでしょう（ちょっとめんどくさいですが^^;）。
あと、計算量を減らす意味でも、最初にスケーリングしたほうがよいと思われます。
また図形が凸かどうかの判定が先かもしれません。
どのようなアプリを想定されているのかで違ってくると思いますが、できるだけ丸いものだけを
判定したいというときには利用できると思います。
＃円ではなく、輪っか的なナニカ（たとえば採点時の赤丸のような）ものには使えないかも・・・
ということで、はずしていたらゴメンナサイ（＾＾；
大垣憲俊
>円形度は、ある閉領域に対して、４π×（面積）／（周囲長の２乗）で得られる値ですが、
>１に近いほど真円に近い値となります。
>あと、計算量を減らす意味でも、最初にスケーリングしたほうがよいと思われます。
>また図形が凸かどうかの判定が先かもしれません。
S.Takahashi
> 私の目的としては、なんとなく囲んだかどうかを検出することなので、
> 円と正方形との差はあまり問題にはならないものと思っています。
なるほど。
てことはやっぱり少し外してましたね＾＾；すいません
円というよりも、特定の対象を囲むような閉領域なのでしょうか？
もしくは位置情報に意味があるようなもの？
登録済みの円的な図形が入力されたかどうかの判断だけならば、
GestureLibraryのrecognize()でもいけそうな気もしますが、精度が今一つ
なのが残念です。
アルゴリズムが分からないので推測ですが、相対的な位置情報のみで認識してる
風なのと、開始・終了位置が重要そうなので、自由な円には向いてなさそうな
感じです(多分）。
＃複数パターン登録することである程度は対応可能かも・・・
実は、recognize()を使って、簡単な漢字を認識するようなアプリを作って
みたんですが、認識結果はボロボロでした＾＾；
画数による制約をつけて、そこそこ認識するようにはなったんですが・・・
ともあれ、最終的にどのような方式で実現されたか後日教えていただければ
今後の参考にさせていただきたいと思います。
＃ここまでの議論も非常に勉強になりました。どうもありがとうございました
大垣憲俊
> 円というよりも、特定の対象を囲むような閉領域なのでしょうか？
> もしくは位置情報に意味があるようなもの？
私は、GestureIME という手書き文字認識IMEの開発をしていまして、
ジェスチャーを文字として認識させようとしています。
svm で判定する前に、候補データをフルイにかける目的で
特徴量を計算しようと思い、直線／斜線／円の区別をしようとしています。
> 登録済みの円的な図形が入力されたかどうかの判断だけならば、
> GestureLibraryのrecognize()でもいけそうな気もしますが、精度が今一つ
> なのが残念です。
/android/gesture/GestureUtils で、描いた順序を考慮する場合は
最短のコサイン距離、それ以外はユークリッド距離の２乗で、単純に比較しています。
> 実は、recognize()を使って、簡単な漢字を認識するようなアプリを作って
> みたんですが、認識結果はボロボロでした＾＾；
> 画数による制約をつけて、そこそこ認識するようにはなったんですが・・・
私は、libsvmを組み込んで、自分で描いたジェスチャーでは高い精度が出せたのですが、
アンドロイドマーケットで公開したところ、とても不評だったため現在は非公開にして
再起を図っています。
> ともあれ、最終的にどのような方式で実現されたか後日教えていただければ
> 今後の参考にさせていただきたいと思います。
GestureIMEの開発はオープンソースにしていますので、
現在のところ、あまり進捗がよろしくありませんが、いつでもご覧ください。
http://git.sourceforge.jp/view?p=gestureime/GestureIME.git
ありがとうございました。
励みになりました。
S.Takahashi
GestureIMEというのを開発されていたんですね。
ウェブサイト拝見しました。
> > 実は、recognize()を使って、簡単な漢字を認識するようなアプリを作って
> > みたんですが、認識結果はボロボロでした＾＾；
> > 画数による制約をつけて、そこそこ認識するようにはなったんですが・・・
>
> 同じようなことをされていたわけですね。
＃小学生向け漢字の書き順練習アプリみたいなのを作ってみようかなとか
＃思っていたところでした
普段、Android携帯での日本語入力に難儀しているので、GestureIME完全版（？）
完成したら利用させてください
Android開発の方はまだまだ初心者なんですが、パターン認識は昔取ったナントカ
なので、何かお役にたてることもあるかもしれません。
＃Android関係で教えていただくことのほうが多いと思いますが＾＾；
では、また何かの折によろしくお願いします。
大垣憲俊
普段、Android携帯での日本語入力に難儀しているので、GestureIME完全版（？）
完成したら利用させてください