Loading [MathJax]/jax/element/mml/optable/MathOperators.js

2016年9月18日日曜日

パラレルリンクロボットの逆運動学のお話

期末試験や大会などでゴタゴタしていたためか,4ヶ月ぶりの更新です.

現在自分はパラレルリンクロボットというロボットを勉強がてら作っています.以下のような機体です.


よく見かけるロボットアーム(多関節ロボット)とはだいぶ様相が異なっています.

最下部の移動する部分が常に地面に対して水平になるような構造となっています.

ちまちま開発していたのですが,疲れてしまったので気分転換がてらブログを更新することにしました.

実機製作の話やプログラムの話は今後に回すとして,今回はモーターの角度と移動する部分の位置の関係式を導出する逆運動学の話を書くことにします.

1.イントロダクション

実際に機体を作ったとしても,プログラムが書けなければ動かすことが出来ません.
その際にはこのロボットの動きを数式で表す必要があります,

ただ,機構学をまだ履修しておらず,運動学についてはさっぱりわからないので,こちらのPDFをトレースする形になりました.
The Delta Parallel Robot: Kinematics Solutions
Robert L. Williams II, Ph.D
http://www.ohio.edu/people/williar4/html/pdf/DeltaKin.pdf
パラレルリンクロボットの運動学について,数式や図を用いて解説しているPDFです.
多分僕の記事はどこか必ず間違いがあるのでこのPDFを見れば間違いないかと思います.


加えて,今回GitHubの方にリポジトリを作成しました.計算の殆どはsympyに計算は投げてまして,その過程も載せてありますので参考になるかと思います.
パラレルリンクロボットの逆運動学問題の導出過程
PLR_Controller/InversePositionKinematics.ipynb at master · TonyMooori/PLR_Controller

どういう機体であるのかという詳細な説明を書くべきですが,面倒なので省略します.上記PDFの最初で扱われているデルタロボットがそれに当たると思うのですがちゃんとした本を見つけられなかったのでなんとも…….

2.各座標の定義

実際に計算を始める前に座標系や各部の名称を決めていきます.まず各部の名称です.
上のモーターや電装部品がある部分を「胴体」,モーターの取り付け部分を「肩」,その先の関節を「肘」,更にその先を「手首」,一番下の部分を「移動体」と名前をつけます.
また,肩から肘の部分を上腕,肘から手首の部分を下腕と名付けます.
※一般的な名前ではなく僕が勝手につけた名前です

また各腕は,反時計回りに0,1,2と番号を振ります.

座標系は次のように取ります.胴体の中央を原点としていますが,胴体は移動しないためこれがワールド座標系となります.
胴体中央部を原点(0,0,0)としてとり,z方向が上方向が正である点に注意してください.

次に,各部分の原点からの位置ベクトルの名称を定義します.iは添字(0,1,2)です.
\vec{A_i}  …… 肩の位置ベクトル
\vec{B_i}  …… 肘の位置ベクトル
\vec{C_i}  …… 手首の位置ベクトル
\vec{D}  …… 移動体の中央部分の位置ベクトル
\vec{e_i}  ……  \vec{A_i} 方向の単位ベクトル.互いに120度向きが異なります.
\phi_i  ……  \vec{e_i} の角度. \frac{2 \pi}{3}i
\vec{e_z} …… z方向の単位ベクトル

各部の長さは次のように定義します.
A  …… 原点から肩への距離( \|\vec{A_i}\| ) 
B  …… 肩から肘への距離(上腕の長さ, \| \vec{A_i} - \vec{B_i} \| ) 
C  …… 肘から手首への距離(下腕の長さ, \| \vec{B_i} - \vec{C_i} \| ) 
D  …… 手首から移動体の中央部分への距離( \| \vec{C_i} - \vec{D_i} \| ) 
サーボモータの角度は次のように定義します.
\theta_i  …… i番目の腕につけられたサーボモーターの角度.±90°とする.正なら上腕が胴体よりも下に行く.


3.逆運動学

ではまず逆運動学から考えていきます.補足ですが,
・サーボモーターを動かしたら移動体の位置がどうなるかを求めるのが順運動学
・移動体の位置を決めたときのサーボモーターの角度を求めるのが逆運動学
と考えて問題ないと思います.

ネットの記事や1で挙げたPDFなどにも書かれているように,パラレルリンクロボットでは逆運動学の方が順運動学よりも求めやすいそうです.
逆に,シリアルリンクロボット(多関節ロボット)では逆運動学のほうが順運動学よりも求めやすいとのこと.

なのでとりあえず逆運動学問題について考えていきます.
ただ,繰り返すようですが運動学を学んでいないので高校レベルのベクトルで考えていきますのでこの道のプロがやる方法とは異なるかもしれないです.

まず \vec{e_i} について考えると,肩は3つ均等に並べられていることから,
e_i = \left[\begin{matrix}\cos{\left (\phi_{i} \right )}\\\sin{\left (\phi_{i} \right )}\\0\end{matrix}\right]
となります.ただし \phi_{i} = \frac{2 \pi}{3}i  , i は0,1,2のいずれかです.さらに, \vec{A_i} \vec{e_i} と同じ方向で長さが異なるだけなので,
\vec{A_i} = A \vec{e_i}
です.スカラーのAとベクトルのAが紛らわしいので注意してください.

次に \vec{B_i} について考えます. \vec{B_i} \vec{A_i} から伸びており, \vec{e_i} \vec{e_z} 成分しかありません.
したがって, \vec{B_i} は次のように表されます. \vec{B_i} = \vec{A_i} + B( \vec{e_i}cos(\theta) - \vec{e_z}sin(\theta) )
次に, \vec{C_i} を考える前 \vec{D} を定義します.逆運動学問題では移動体の位置を決めた上で角度 \theta_i を求めるので,移動体の位置は, \vec{D} = \left[\begin{matrix}x\\y\\z\end{matrix}\right] という値が予めわかった上で考えていきます.

これを使うと \vec{C_i} は移動体がねじれずに(z軸に対して回転することなく)移動するため, \vec{C_i} = \vec{D} + D\vec{e_i} となります.

ここで,2で書いた定義, C = \| \vec{B_i} - \vec{C_i} \|  を用いることで \theta_i が求まります.この式は求めたい変数 \theta_i ひとつだけなので非常に簡単というか,個人的には驚きです.
この式を両辺を二乗すると次のようになります.
C^{2} = \left(B \sin{\left (\theta_{0} \right )} + z\right)^{2} + \left(- A \sin{\left (\phi_{0} \right )} - B \sin{\left (\phi_{0} \right )} \cos{\left (\theta_{0} \right )} + D \sin{\left (\phi_{0} \right )} + y\right)^{2} + \left(- A \cos{\left (\phi_{0} \right )} - B \cos{\left (\phi_{0} \right )} \cos{\left (\theta_{0} \right )} + D \cos{\left (\phi_{0} \right )} + x\right)^{2} 更に展開して, C^{2} = A^{2} + 2 A B \cos{\left (\theta_{0} \right )} - 2 A D - 2 A x \cos{\left (\phi_{0} \right )} - 2 A y \sin{\left (\phi_{0} \right )} + B^{2} - 2 B D \cos{\left (\theta_{0} \right )} - 2 B x \cos{\left (\phi_{0} \right )} \cos{\left (\theta_{0} \right )} - 2 B y \sin{\left (\phi_{0} \right )} \cos{\left (\theta_{0} \right )} + 2 B z \sin{\left (\theta_{0} \right )} + D^{2} + 2 D x \cos{\left (\phi_{0} \right )} + 2 D y \sin{\left (\phi_{0} \right )} + x^{2} + y^{2} + z^{2} となります.この辺はsympyという数式処理ソフトに投げてるので手計算ではないです.
この式と2,3分ほどにらめっこすると,こういう式であることに気づきます.
P + Q \sin{\left (\theta_{i} \right )} + R \cos{\left (\theta_{i} \right )} = 0 ただし,P,Q,Rは次のような値です. \begin{eqnarray*} P &=& - A^{2} + 2 A D + 2 A x \cos{\left (\phi_{i} \right )} + 2 A y \sin{\left (\phi_{i} \right )} - B^{2} + C^{2} - D^{2} \\ &-& 2 D x \cos{\left (\phi_{i} \right )} - 2 D y \sin{\left (\phi_{i} \right )} - x^{2} - y^{2} - z^{2}\\ Q &=& - 2 B z \\ R &=& - 2 A B + 2 B D + 2 B x \cos{\left (\phi_{i} \right )} + 2 B y \sin{\left (\phi_{i} \right )} \end{eqnarray*}

この式から, \theta_i を求めます. t = tan(\frac{\theta_i}{2}) を置くことで,この式を2次方程式にすることができ,そこから \theta_i を求めることが出来ます.

こちらはsympyに投げてるので途中式を省略します.結果は次のようになります. \begin{eqnarray*} \theta_i &=& - 2 \operatorname{atan}{\left (\frac{1}{P - R} \left(Q - \sqrt{- P^{2} + Q^{2} + R^{2}}\right) \right )} \\ \theta_i ' &=& - 2 \operatorname{atan}{\left (\frac{1}{P - R} \left(Q + \sqrt{- P^{2} + Q^{2} + R^{2}}\right) \right )} \end{eqnarray*}
2次方程式,と言った時点で気づいた方もいるかもしれませんが,解が2つ出てきます.これは肘が内側に来てる状態も含まれているためです.

因みに,適切な方を選ばなければこのような状態になります.
それぞれの腕に対して2パターンあるので,この条件が成立する状態がこのロボットでは合計8パターン存在します.

加えて,どちらが適切であるかどうかは角度の絶対値が小さい方,すなわち0付近である方を選択することでたいていうまくいきます(理論的な根拠があるわけではないです).
そもそも不適切な方の角度はサーボモーターの移動範囲外である事が多いため,このような状態にはならないはずですが,間違えるとサーボモーターを傷めるので注意してください.

また根号の中が負となる場合がありますが,その場合はこのロボットの移動範囲外であるということを表していると思って問題ないと思います.

4.シミュレーション

シミュレーションというか,可視化というか,ちゃんと数式があっているかの確認を行います.
プログラムは個々に貼り付けると長くなるのでGitHubのリポジトリの方においておきます.

PLR_Controller/IPK_Visualize.ipynb at masterTonyMooori/PLR_Controller

結果はこのようになります.

必要ならば各ベクトルの距離を計算して調べてみるとよいかと思います.


5.実機による実験

Arduino Microを用いて3つのサーボモータを制御します.
Amazonで購入した大きめのトルクの物を動かしています.

回路図はこんな感じです.サーボとマイコンを繋げただけです.
プログラムはこれもGitHubにあげてあります.
PLR_Controller/Arduino/trace_circle at masterTonyMooori/PLR_Controller
実際の動画です.とりあえずサンプルとして円を描くような軌跡で動かしています.
今回は以上ですが,もうしばらく続くかと思います.



2016年5月15日日曜日

GUI自動化ライブラリの使い方のまとめと利用例[Python]

この所スランプ気味でして,気分転換に久しぶりの更新です.

1.GUI自動化について

普段PCを使っていて,単純作業やゲームなどを自動化したいと思うことは結構あるかと思います(チートはダメだよ).

ExcelなどではVBAでマクロを書くことが出来るのですが,それ以外の場合については大抵GUI自動化ライブラリを使って自分でプログラムを書くのが一般的かと思います.

有用に使う例は多々あるのですが,ただ遊ぶだけでもそこそこ楽しいです.頑張ればこんなこともできちゃいます.


自分は普段PyAutoGUIというPythonのライブラリを使っているのですが,日本語で使い方を書いたサイトが少なく,毎回英語の公式ドキュメントをGoogle翻訳片手に読むのはつらいのでブログにまとめることにしました.

2.PyAutoGUIの関数使い方のまとめ

自分が普段使うときに使う関数のまとめです.これである程度使いこなすことは出来るかと思います.

このプログラム自体に意味は無いので実行しないようにしたほうが良いかと思います.

ちなみに間違えて作ったプログラムで暴走した時は左上にカーソルを移動すると例外が発生して止まるようになっています.

import pyautogui as pa

"""
参考:PyAutoGUI公式ドキュメント
[1] Welcome to PyAutoGUI’s documentation! — PyAutoGUI 1.0.0 documentation
    https://pyautogui.readthedocs.io/en/latest/
[2] PyAutoGUI Documentation
    https://media.readthedocs.org/pdf/pyautogui/latest/pyautogui.pdf
"""

if __name__=="__main__":
    # 画面の幅と高さを取得する関数
    w,h = pa.size()
    
    # マウスカーソルの位置を取得する関数
    mouseX,mouseY = pa.position()
    
    # クリック
    pa.click()
    
    # click関数詳細
    pa.click(
        x = 200,y = 200,    # 座標
        clicks = 2,            # クリックの回数
        interval = 0.25,    # クリック間のインターバル
        button = "left",    # マウスのボタン(left,middle,rightの3つ)
        duration = 0.05        # 長押しするかどうか    
    )
    # マウスカーソルの移動(左上を(0,0)とする)
    pa.moveTo(x=100,y=200,duration=0.0)
    
    # マウスカーソルの移動(現在の位置を(0,0)とする)
    pa.moveRel(xOffset=20,yOffset=20,duration=0.0)
    
    # ドラッグ(左上を(0,0)とする)
    pa.dragTo(x=100,y=300,duration=0.0,button="left")
    
    # ドラッグ(現在の位置を(0,0)とする)
    pa.dragRel(xOffset=10,yOffset=30,duration=0.0,button="left")
    
    # マウスの押下(押したまんまになる)
    pa.mouseDown(x=200,y=300,button="left")
    
    # マウスの押下の取り消し
    pa.mouseUp()
    
    # スクロール(上に移動するのが正)
    pa.scroll(clicks=100,x=100,y=100)
    
    # 文字の打ち込み
    pa.typewrite("Hello, World!",interval=0.0)
    
    # 指定したキーを押す
    pa.press(keys="enter",presses=2,interval=0.0)
    
    # 指定したキーを押したまんまにする
    pa.keyDown("shift")
    
    # 指定したキーを離す
    pa.keyUp("shift")
    
    # 複数のキーを同時に押す
    pa.hotkey("ctrl","f")
    
    # スクリーンショット(ファイルに保存,範囲指定)
    # imageFilename,regionは指定しなくても良い
    img = pa.screenshot(
        imageFilename="screenshot.png",    # 保存先ファイル名
        region=(20,20,100,100)    # 撮影範囲(x,y,width,height)
    )
    
    # 指定した画像がスクリーン上のどこにあるかを探す関数
    # 一致箇所をすべて探してタプル(x,y,width,height)の配列で返す
    pos_list = pa.locateAllOnScreen(img)
    
    # ファイル名で与えることも出来る
    pos_list = pa.locateAllOnScreen("screenshot.png")
    
    # 一箇所見つかればよいのならばlocateOnScreen
    pos = pa.locateOnScreen("screenshot.png")


"""
keyDownで指定できるキー一覧
['\t', '\n', '\r', ' ', '!', '"', '#', '$', '%', '&', "'", '(',
')', '*', '+', ',', '-', '.', '/', '0', '1', '2', '3', '4', '5', '6', '7',
'8', '9', ':', ';', '<', '=', '>', '?', '@', '[', '\\', ']', '^', '_', '`',
'a', 'b', 'c', 'd', 'e','f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '{', '|', '}', '~',
'accept', 'add', 'alt', 'altleft', 'altright', 'apps', 'backspace',
'browserback', 'browserfavorites', 'browserforward', 'browserhome',
'browserrefresh', 'browsersearch', 'browserstop', 'capslock', 'clear',
'convert', 'ctrl', 'ctrlleft', 'ctrlright', 'decimal', 'del', 'delete',
'divide', 'down', 'end', 'enter', 'esc', 'escape', 'execute', 'f1', 'f10',
'f11', 'f12', 'f13', 'f14', 'f15', 'f16', 'f17', 'f18', 'f19', 'f2', 'f20',
'f21', 'f22', 'f23', 'f24', 'f3', 'f4', 'f5', 'f6', 'f7', 'f8', 'f9',
'final', 'fn', 'hanguel', 'hangul', 'hanja', 'help', 'home', 'insert', 'junja',
'kana', 'kanji', 'launchapp1', 'launchapp2', 'launchmail',
'launchmediaselect', 'left', 'modechange', 'multiply', 'nexttrack',
'nonconvert', 'num0', 'num1', 'num2', 'num3', 'num4', 'num5', 'num6',
'num7', 'num8', 'num9', 'numlock', 'pagedown', 'pageup', 'pause', 'pgdn',
'pgup', 'playpause', 'prevtrack', 'print', 'printscreen', 'prntscrn',
'prtsc', 'prtscr', 'return', 'right', 'scrolllock', 'select', 'separator',
'shift', 'shiftleft', 'shiftright', 'sleep', 'stop', 'subtract', 'tab',
'up', 'volumedown', 'volumemute', 'volumeup', 'win','winleft', 'winright', 'yen',
'command', 'option', 'optionleft', 'optionright']
"""

幾つかマニアックな機能などは書きませんでしたが,この程度あれば十分いろんなことが出来るかと思います.


3.実際に使ってみる

関数の使い方だけではつまらないのでちょっと上の関数を使って遊んでみた例を書いてみます.

(あ,一応上で述べたミクのやつはここにコードが貼ってありますがPyAutoGUI以外の知識がいるのであまりオススメではないです)


とりあえずペイントで四角を書くプログラムです.本当はpa.locateOnScreen("画像ファイル")で座標を取り出してボタンをクリックするみたいな処理を入れたいのですが,画像がないと実行できないのでこれで妥協です.
import pyautogui as pa
import time

if __name__=="__main__":
    # 起動してすぐに実行されると困るので5秒待つ
    time.sleep(5)
    
    # 現在の位置を取得する
    x0,y0 = pa.position()
    
    # PyAutoGUIの各動作の間隔を0.1秒に指定
    pa.PAUSE = 0.1
    
    n = 256
    # マウスを押して
    pa.mouseDown(button="left")
    for i in range(n)[::16]:
        # 左上,右上,右下,左下,左上と移動してみる
        pa.moveTo(x0 , y0)
        pa.moveTo(x0 + i , y0)
        pa.moveTo(x0 + i , y0 + i)
        pa.moveTo(x0 , y0 + i )
        pa.moveTo(x0 , y0)
    # マウスを戻す
    pa.mouseUp()
またなんか作ったら記事書きます.


4.参考

公式ドキュメント.割とわかりやすくまとまっています.
Welcome to PyAutoGUI’s documentation! — PyAutoGUI 1.0.0 documentation
https://pyautogui.readthedocs.io/en/latest/

公式ドキュメントのPDF.一度に見れるので良いです.
PyAutoGUI Documentation
https://media.readthedocs.org/pdf/pyautogui/latest/pyautogui.pdf

2016年3月10日木曜日

ルンゲクッタ法の説明と実装例[C言語]

3日かけてルンゲクッタ法を理解する所までにきました.

とは言うものの,この記事では1階常微分方程式についての4次ルンゲクッタについて説明しています.

前回,前々回の記事である

オイラー法と修正オイラー法の説明と実装例
ニュートン・コーツの公式とシンプソンの公式の導出と実装

を読むと今回の記事で説明するルンゲクッタ法の導出部分が理解しやすいかと思います.


1.(4次)ルンゲクッタ法の簡単な説明


詳しい説明はしたところであまり興味がない人が多い気がするので,詳しい説明は最後にすっ飛ばして,実装するにおいて最低限の部分だけ示しておきます.

次の初期値がわかっている1階常微分方程式を解く事を考えます.
\begin{eqnarray*} f(x_0) &=& y_0 \\ \frac{df(x)}{dx} &=& g(x,f(x)) \end{eqnarray*} この時,4次ルンゲクッタ法では次のようにして計算します. \int_{x_k}^{x_{k+1}} g(x,f(x)) dx \approx \frac{1}{6}(k_1+2k_2+2k_3+k_4 )\Delta x ただしk1,...,k4は \begin{eqnarray*} k_1 &=& g(x_k,f(x_k)) \\ k_2 &=& g(x_{k+\frac{1}{2}},f(x_k) + k_1 \frac{\Delta x}{2}) \\ k_3 &=& g(x_{k+\frac{1}{2}},f(x_k) + k_2 \frac{\Delta x}{2}) \\ k_4 &=& g(x_{k+1},f(x_k)+k_3 \Delta x) \end{eqnarray*} として計算しています.
この辺の導出は一番最後でしているので気になる人は見てってくださいな.


2.実装例


何を実装しようか悩んで適当にWikipediaを漁っていたらロジスティック方程式というモデルがあったので,これのシミュレーションをしてみたいと思います.

Wikipediaによれば,生物の個体数がどのように変化していくかを説明するモデルの一つであるとのこと.

求める常微分方程式はこれ. \frac{dN(t)}{dt} = r \frac{K-N(t)}{K} N(t) rは一匹の個体の増加率,N(t)は時間tにおける生物の個体数,Kは個体数のしきい値で,最終的に安定するNの値.

例えば水槽なら最大でも20匹ぐらいしか入らない大きさならK=20みたいな値になると思う.

ちなみに厳密解は普通の変数分離法で多少計算が面倒だけど求まる.初期値をN_0とすると次のようになる. N(t) = \frac{N_0 K e^{rt}}{K - N_0 + N_0 e^{rt}} 厳密解はさておき,この常微分方程式にルンゲクッタ法を適用する.

まず見通しを良くするために,1で示した式のg(x,f(x))に当たる部分g(t,N(t))を定義しておく. \begin{eqnarray*} \frac{dN(t)}{dt} &=& r \frac{K-N(t)}{K} N(t) \\ &=& g(t,N(t)) \end{eqnarray*} そうすると \Delta t を微小な値として, t_k = k \Delta t とすると,漸化式はこのようになる. \int_{t_k}^{t_{k+1}} g(t,N(t)) dt \approx \frac{1}{6}(k_1+2k_2+2k_3+k_4 )\Delta t ただしk1,...,k4は次の式で計算する. \begin{eqnarray*} k_1 &=& g(t_k,N(t_k)) \\ k_2 &=& g(t_{k+\frac{1}{2}},N(t_k) + k_1 \frac{\Delta t}{2}) \\ k_3 &=& g(t_{k+\frac{1}{2}},N(t_k) + k_2 \frac{\Delta t}{2}) \\ k_4 &=& g(t_{k+1},N(t_k)+k_3 \Delta t) \end{eqnarray*} それではC言語による実装.関数g,を定義することで,数式とほぼ変わらないプログラムが書けます.実装の係数は適当なのでアレですが.
/* 4次ルンゲクッタ法によるロジスティック方程式の解の計算 */
#include <stdio.h>
#define K 1000.0 // 個体数のしきい値
#define r 0.9 // 1個体の増加率
#define N_LOOP 10000 // ループ回数
// 積分する関数g(t,N)
double g(double t,double N_t){
return r*(K-N_t)*N_t/K;
}
int main(void){
int k; // ループカウンタ
double dt = 1e-3; // 刻み幅Δt
double N = 1.0; // 個体数t(初期値を代入しておく)
double k1,k2,k3,k4; // 計算に使う諸変数
double a,m,b; // t_k,t_k+0.5,t_k+1を格納する
for( k = 0 ; k < N_LOOP ; k++ ){
// t_k,t_k+0.5,t_k+1を計算
a = k*dt;
m = (k+0.5)*dt;
b = (k+1.0)*dt;
// k1,...,k4の値を計算
k1 = g(a,N);
k2 = g(m,N+k1*dt*0.5);
k3 = g(m,N+k2*dt*0.5);
k4 = g(b,N+k3*dt);
// 積分して代入
N = N + (dt/6.0)*(k1+2.0*k2+2.0*k3+k4);
// 値を表示
printf("%lf,%e\n",b,N);
}
return 0;
}
シミュレーション結果.
このシミュレーションだとほとんど違いがわかりませんね.誤差をプロットするとこうなります.
オーダーが1e-5といったところでしょうか.誤差が振動しているのがわかります.シミュレーションの精度としては十分なのでしょう.

4次のルンゲクッタ法では4次の項まで級数展開が一致しているとかで,誤差は O(\Delta t^5) に比例して小さくなるとのことです.

流石にルンゲクッタ法でシミュレーションすれば精度どうなの?とか言われても大丈夫そう……?まだその辺はよく知らないけれど.

3.ルンゲクッタ法の説明


手元の本には書かれていないのではっきりしたことはわからないのですが軽く調べたところによると,修正オイラー法は2次ルンゲクッタ法とも呼ぶらしいです.

なので2次ルンゲクッタについては前回の記事を参照してください.ここでは4次ルンゲクッタについて説明します.

今回はとりあえず1階微分方程式についての4次ルンゲクッタについて説明するので,次の常微分方程式について考えます.
f(x_0) = y_0 \\ \frac{df(x)}{dx} = g(x,f(x)) ここで  x_k = x_0 + k \Delta x  と置くと  f(x_{k+1})  と  f(x_{k})  の漸化式を得ます. \begin{eqnarray*} \int_{x_k}^{x_{k+1}} \frac{df(x)}{dx} dx &=& f(x_{k+1})-f(x_k) \\ &=& \int_{x_k}^{x_{k+1}} g(x,f(x)) dx \\ \\ ∴f(x_{k+1}) &=& f(x_k) + \int_{x_k}^{x_{k+1}} g(x,f(x)) dx \end{eqnarray*}

この \int_{x_k}^{x_{k+1}} g(x,f(x)) dx の部分をどう計算するかによってオイラー法,修正オイラー法,ルンゲクッタ法が分類できます.

オイラー法では矩形積分,修正オイラー法では台形積分,ルンゲクッタ法ではシンプソンの公式を使います.

シンプソンの公式は次のようになります. \int_{x_k}^{x_{k+1}}h(x) dx \approx \frac{1}{6}(h(x_k)+4h(x_k+\frac{\Delta x}{2}) + h(x_{k+1}) )\Delta x これを使って積分値を計算すれば良いわけです. x_{k+\frac{1}{2}} = x_k+\frac{1}{2}\Delta x \\ として \begin{eqnarray*} g_k &=& g(x_k,f(x_k)) \\ g_{k+\frac{1}{2}} &=& g(x_{k+\frac{1}{2}},f(x_{k+\frac{1}{2}})) \\ g_{k+1} &=& g(x_{k+1},f(x_{k+1})) \\ \end{eqnarray*} という値を考えると, \int_{x_k}^{x_{k+1}} g(x,f(x)) dx は次のように近似できます. \int_{x_k}^{x_{k+1}} g(x,f(x)) dx \approx \frac{1}{6}(g_k + 4g_{k+\frac{1}{2}} + g_{k+1} )\Delta x
しかしこの式には未知の値f(x_{k+\frac{1}{2}})f(x_{k+1})を使っています.これらの値を矩形積分で求めて計算することもできますが,良い精度が得られません.

ルンゲクッタ法ではこれらの値を二段階の計算で計算します.
\begin{eqnarray*} k_1 &=& g(x_k,f(x_k)) \\ k_2 &=& g(x_{k+\frac{1}{2}},f(x_k) + k_1 \frac{\Delta x}{2}) \\ k_3 &=& g(x_{k+\frac{1}{2}},f(x_k) + k_2 \frac{\Delta x}{2}) \\ k_4 &=& g(x_{k+1},f(x_k)+k_3 \Delta x) \end{eqnarray*} g_{k+\frac{1}{2}} に当たる部分をk2,k3という形で計算しています.これらを先ほどのシンプソンの公式に代入することで以下のような近似を行うものを4次のルンゲクッタ法と呼ぶそうです. \int_{x_k}^{x_{k+1}} g(x,f(x)) dx \approx \frac{1}{6}(k_1+2k_2+2k_3+k_4 )\Delta x

今日はここまで.

ニュートン・コーツの公式とシンプソンの公式の導出と実装[C言語]

ルンゲクッタ法はどうやって導かれたのか謎だったのですが,『情報処理入門コース 数値計算』によれば,シンプソンの公式から来ているとのこと.
なのでシンプソンの公式がどういう経緯でできたのかメモしていきます.

※数式がうまく表示されない時はPCのブラウザから見ることを推奨します


1.ニュートン・コーツの積分公式


まずラグランジュ補間の公式が与えられているものとして使います.f(x)が近似したい式,p(x)が近似式.x_0,...,x_nが関数f(x)上のわかっている点. p(x)=\sum_{i=0}^{n}f(x_i)N(i,x) \\ N(i,x) = \prod_{j=0,j \neq i}^{n} \frac{x-x_j}{x_i-x_j} ラグランジュ補間の出処はよくわかんないけど関数N(x)がクロネッカーのデルタ関数のようになっていることから意味をお察しください.とりあえずラグランジュ補間については前書いたのでそっちも見てくださいな.

次に,このラグランジュ補間で求めた近似式を用いて関数f(x)を区間[a,b]で積分する事を考えます. a = x_0,x_1,x_2,...,x_n = b という様に区間をn分割し,上記のラグランジュ補間を適用すると次のようになります. \begin{eqnarray*} S &=& \int_{a}^{b}f(x)dx \\ & \approx & \int_{a}^{b}p(x)dx \\ &=& \int_{a}^{b} \sum_{i=0}^{n}f(x_i)N(i,x) dx \\ \end{eqnarray*} ここで少しわかりづらいのですが,x_iは定数なのでf(x_i)はxの関数では無いことから, \begin{eqnarray*} S & \approx & \int_{a}^{b} \sum_{i=0}^{n}f(x_i)N(i,x) dx \\ &=& \sum_{i=0}^{n}f(x_i) \int_{a}^{b}N(i,x) dx \end{eqnarray*} という式が得られます.ここで関数N(i,x)はx_0,...,x_nが[a,b]をn等分した値,すなわち x_k = a + k\Delta x \\ \Delta x = \frac{b-a}{n} と表せることを用いて,次の変数変換をすることを考えます. t = \frac{x-a}{\Delta x}\\ dt = \Delta x \, dx ここで,N(i,x)は上記のtを代入して次のように変形したものをM(i,t)とする. \begin{eqnarray*} N(i,x) &=& \prod_{j=0,j \neq i}^{n} \frac{x-x_j}{x_i-x_j} \\ &=& \prod_{j=0,j \neq i}^{n} \frac{(a+ t \Delta x) - (a + j \Delta x)}{(a+i \Delta x) - (a + j \Delta x ) } \\ &=& \prod_{j=0,j \neq i}^{n} \frac{t-j}{i-j} \\ &=& M(i,t) \end{eqnarray*} このN(i,x)を変形した関数M(i,t)を用いると先ほどの積分はこうなる. \begin{eqnarray*} S & \approx & \sum_{i=0}^{n}f(x_i) \int_{a}^{b}N(i,x) dx \\ &=& \sum_{i=0}^{n}f(x_i) \Delta x \int_{0}^{n}M(i,t) dt \end{eqnarray*} M(i,t)は変数xや,区間[a,b]などに依存しないから, C_i = \int_{0}^{n}M(i,t) dt と置いて,先に手計算で計算しておけば使い回しが効いて,最終的に次のようになります. S \approx \sum_{i=0}^{n}f(x_i) C_i \Delta x この公式をニュートン・コーツの積分公式と呼ぶとのこと.


2.シンプソンの公式


うえで求めたニュートン・コーツの積分公式にn=2を代入したものが世間一般にシンプソンの公式と呼ばれているものとのこと.C_iの値は上式に突っ込んで \begin{eqnarray*} C_0 &=& \int_0^2 \frac{t-1}{-1} \frac{t-2}{-2} dt &=& \frac{1}{3} \\ C_1 &=& \int_0^2 \frac{t}{1} \frac{t-2}{-1} dt &=& \frac{4}{3} \\ C_2 &=& \int_0^2 \frac{t}{2} \frac{t-1}{1} dt &=& \frac{1}{3} \\ \end{eqnarray*} となる.この公式のすごいところはこの係数をあらかじめ求めておけば面倒な計算を端折ることができるところだと思います.
この値をニュートン・コーツの積分公式に代入すると, \begin{eqnarray*} \int_{a}^{b} f(x) dx &=& \sum_{i=0}^{2}f(x_i) C_i \Delta x\\ &=& (\frac{f(x_0)}{3} +\frac{4f(x_1)}{3} +\frac{f(x_2)}{3}) \Delta x\\ &=& (\frac{f(x_0)}{3} +\frac{4f(x_1)}{3} +\frac{f(x_2)}{3}) {\frac{b-a}{2}}\\ &=& \frac{1}{6}(b-a)(f(x_0)+4f(x_1) +f(x_2)) \end{eqnarray*} となります.

シンプソンの公式を図で表すとこんな感じ.青色の線が二次式で近似した曲線.その曲線の積分を求めてる.

ちなみにn=3の場合などはニュートン・コーツの公式のWikipediaに載ってたりするのでそちらを参照すると良いかと思います.


3.プログラム


抽象的な話はこの辺にして,実際にプログラムを書いてみます.試しに f(x) = \frac{4}{x^2+1} を[0,1]区間で積分してみます.

ちなみに \int_{0}^{1}f(x)dx の厳密解はπです.

まず \Delta x = \frac{1}{n} とし, x_k = k \Delta x と置くと, \begin{eqnarray*} \int_{0}^{1}f(x)dx = \sum_{k=0}^{n-1} \int_{x_k}^{x_{k+1}}f(x) dx \end{eqnarray*} という微小区間 [x_k,x_{k+1}] の積分となります.この微小な区間に対してシンプソンの公式を適用すると次のようになります. \int_{x_k}^{x_{k+1}}f(x) dx \approx \frac{1}{6}(f(x_k)+4f(x_k+\frac{\Delta x}{2}) + f(x_{k+1}) )\Delta x 実際はf(x_k)の足し算がかぶっているのでもう少しスマートにできるのですが,今回は愚直にそのままこれを実装します.
/* シンプソンの公式による1/(x^2+1)の計算 */
#include <stdio.h>
// 被積分関数
double f(double x){
return 4.0/(x*x+1.0);
}
int main(void){
int k; // ループカウンタ
int N = 1000; // 分割数
double dx = 1.0/N; // 刻み幅Δx
double S = 0.0; // 和を格納する変数
double a; // x_kの値を格納する
double b; // x_{k+1}の値を格納する
double m; // a,bの中間の値を格納する
for( k = 0 ; k < N ; k++ ){
// 近似を行う3点を計算
a = k * dx;
m = a + dx / 2.0;
b = (k+1) * dx;
// f_k + g(x_k,f(x_k))をfに代入
S += (1.0/6.0)*(f(a)+4.0*f(m)+f(b))*dx;
// 値の表示
printf("%lf,%e\n",b,S);
}
return 0;
}
view raw SimpsonsRule.c hosted with ❤ by GitHub
実行結果
結果が3.141593なので円周率が概ねちゃんと求まっているので大丈夫そうです.

オイラー法と修正オイラー法の説明と実装例[C言語]

学科的に流体シミュレーションとか多分そのうちやると思うのですが,ルンゲクッタ法を理解していなかったのでとりあえず常微分方程式の数値計算の基本であるオイラー法と修正オイラー法について記事を書いてみます.


1.オイラー法


オイラー法は精度は悪いですが,非常に簡単で計算が高速です.研究などでは恐らく使われることはありませんが,ゲームプログラミング等をしているとシューティングの弾の運動などは大抵オイラー法が使われています.
今回は説明のための例として,次のような常微分方程式があったとします.今回は初期値f(x_0)がわかっているものとします. f(x_0) = y_0 \\ \frac{df(x)}{dx} = g(x,f(x)) ここで  x_k = x_0 + k \Delta x  と置くと  f(x_{k})  の値は次のようにして求められることがわかります. \begin{eqnarray*} f(x_{k}) &=& f(x_0) + \int_{x_0}^{x_k} g(x,f(x)) dx \\ &=& f(x_0) + \sum_{i=0}^{k-1} \int_{x_{i}}^{x_{i+1}} g(x,f(x)) dx \end{eqnarray*} ここで  f(x_{k+1})  と  f(x_{k})  の漸化式を考えます. \begin{eqnarray*} \int_{x_k}^{x_{k+1}} \frac{df(x)}{dx} dx &=& f(x_{k+1})-f(x_k) \\ &=& \int_{x_k}^{x_{k+1}} g(x,f(x)) dx \\ \\ ∴f(x_{k+1}) &=& f(x_k) + \int_{x_k}^{x_{k+1}} g(x,f(x)) dx \end{eqnarray*} この \int_{x_k}^{x_{k+1}} g(x,f(x)) dx の部分がキモです.この部分をどうするかで精度が大きく変わってきます.

オイラー法ではg(x,f(x))が区間[x_k,x_{k+1}]でほとんど変化しないものとして,次のように近似しています. \int_{x_k}^{x_{k+1}} g(x,f(x)) dx \approx g(x_k,f(x_k)) \Delta x これを漸化式に代入したものがオイラー法です. f(x_{k+1}) \approx f(x_k) + g(x_k,f(x_k)) \Delta x

2.修正オイラー法


オイラー法は非常に簡単なのですが精度がよろしくないです.なのでもう少し精度を上げる必要があります.

修正オイラー法はその改良版の一つです.もっとも,これもあまり制度が良いというわけではないですが.

先ほど,  \int_{x_k}^{x_{k+1}} g(x,f(x)) dx の部分がキモと言いました.オイラー法では関数g(x,f(x))があまり変化しないものとして計算していました.イメージとしてはこんな感じです.
矩形近似とか長方形近似とか呼ばれているタイプの積分方法です.見るからに精度がよろしくなさそうなのがわかります.

そこで台形公式というものを使って修正オイラー法というものが提案されました.イメージとしてはこんな感じです.
名前の通り台形で近似するというものです.数式で表すと次のようになります.台形の面積は((高さ)×(上辺)+(下辺))÷2という小学生の時に習った公式を用いて,
\int_{x_k}^{x_{k+1}} g(x,f(x)) dx \approx (g(x_k,f(x_k)) + g(x_{k+1},f(x_{k+1}))) \frac{\Delta x}{2} という近似式で計算します.しかしこれを漸化式に代入すると f(x_{k+1}) \approx f(x_k) + (g(x_k,f(x_k)) + g(x_{k+1},f(x_{k+1}))) \frac{\Delta x}{2} となり, f(x_{k+1}) を求めるために f(x_{k+1}) を使っているのでこれでは使えません.なので右辺の f(x_{k+1}) だけは,オイラー法で使った矩形近似を用いて次のように求めておきます. \widehat{f(x_{k+1})} = f(x_k) + g(x_k,f(x_k)) \Delta x この  \widehat{f(x_{k+1})}  を用いて漸化式に代入したものが修正オイラー法です. f(x_{k+1}) \approx f(x_k) + (g(x_k,f(x_k)) + g(x_{k+1},\widehat{f(x_{k+1})})) \frac{\Delta x}{2}

3.利用例

ここまで抽象的すぎたのでここで一度,次の1階微分方程式を数値的に解いてみたいと思います. \frac{df(x)}{dx} - 2f(x) = x まぁ適当に作った式なので意味は無いです.ちなみに厳密解はCを定数として f(x) = -\frac{1}{4}(2x+1) + Ce^{2x} と表されます.ちなみに定数Cは関数f(x)の初期値f(0) = aとした時, C = a + \frac{1}{4} になります.
今回は初期値 f(0) = a = 1 として数値的に求めてみます.

上記の微分方程式を変形してみます. \begin{eqnarray*} \frac{df(x)}{dx} &=& x + 2f(x) \\ &=& g(x,f(x)) \end{eqnarray*} これでg(x,f(x))が求まりましたので,先ほど示した漸化式に代入してみれば,オイラー法では f(x_{k+1}) \approx f(x_k) + (x_k + 2f(x_k)) \Delta x となります.

修正オイラー法では,まず  \widehat{f(x_{k+1})}  が \begin{eqnarray*} \widehat{f(x_{k+1})} &=& f(x_k) + g(x_k,f(x_k)) \Delta x \\ &=& f(x_k) + (x_k + 2f(x_k)) \Delta x \\ \end{eqnarray*} となることから,次の漸化式に代入してやれば良いです. f(x_{k+1}) \approx f(x_k) + (g(x_k,f(x_k)) + g(x_{k+1},\widehat{f(x_{k+1})})) \frac{\Delta x}{2} \\ 全部数式を代入すれば,x_kとf(x_k)とΔxだけの式にできますが,数式が長くなるので省略.

もっとも,関数をプログラム内で定義してやればそんなに気にならないと思います.


4.精度の評価


ソースコードは長くなりますので先にオイラー法,修正オイラー法の精度を示しときます.

もっとも,評価と言ってもこの例での真値との差を見るだけですが.以下数値的に求めたものと,真値との差です.
刻み幅Δx=0.001,反復回数1000回です.euler's method 2の方が修正オイラー法です.適切な英語が見つからなかったので…….
1000回繰り返して差が10^-7オーダーですね.とりあえずそれらしい値は取れているのがわかります.
これを見る限り修正オイラー法はオイラー法と比べたら優秀そうではあります.
ただ傾きが指数関数的に増えていきそうなので後日ルンゲクッタ法を実装してそれと比較したいです.


5.ソースコード


C言語による実装.オイラー法はこんな感じです.
/* Euler法による微分方程式 f' - 2f = x の計算 */
#include <stdio.h>
#include <math.h>
double g(double x,double fx){
return x + 2.0 * fx;
}
int main(void){
int k; // ループカウンタ
int N = 10000; // 繰り返し数
double dx = 1e-3; // 刻み幅Δx
double f = 1.0; // 関数f(x)の値(初期値)
double x_0 = 0.0; // 初期値の時のxの値
double x_k; // x_kの値
for( k = 1 ; k <= N ; k++ ){
x_k = x_0 + k * dx; // x_kの値を求める
f = f + g(x_k,f) * dx; // f_k + g(x_k,f(x_k))をfに代入
// 値の表示
printf("%lf,%e\n",x_k,f);
}
return 0;
}
view raw EulersMethod.c hosted with ❤ by GitHub

修正オイラー法はこんな感じです.
/* 修正Euler法による微分方程式 f' - 2f = x の計算 */
#include <stdio.h>
#include <math.h>
double g(double x,double fx){
return x + 2.0 * fx;
}
int main(void){
int k; // ループカウンタ
int N = 10000; // 繰り返し数
double dx = 1e-3; // 刻み幅Δx
double f = 1.0; // 関数f(x)の値(初期値)
double f_bar; // f(x_k+1)を矩形積分でとりあえず求めた値
double x_0 = 0.0; // 初期値の時のxの値
double x_k; // x_kの値
for( k = 1 ; k <= N ; k++ ){
x_k = x_0 + k * dx; // x_kの値を求める
// まず矩形積分でf_k+1を見積もって
f_bar = f + g(x_k,f) * dx;
// 台形公式で積分する
f = f + (g(x_k,f) + g(x_k + dx, f_bar)) * dx /2.0;
// 値の表示
printf("%lf,%e\n",x_k,f);
}
return 0;
}
view raw EulersMethod2.c hosted with ❤ by GitHub
今日はここまで.

2016年3月7日月曜日

自己相関関数で音声の繰り返し部分を抽出する[Python]

フーリエ変換でミクを描いたものの,フーリエ変換をちゃんと勉強したことがなかったので『メカトロニクス入門シリーズ 信号処理入門』を読んでます.

その中で「自己相関関数」というものが紹介されており,非常に面白そうだったので実装してみることにします.


1.自己相関関数とは

「あー」というような定常な音の場合,同じような音の波形が繰り返されています.
すなわち,f(t)を時間tの時の音の大きさだとすると,f(t)には次のような性質を持つことがわかります. f(t) = f(t + nT) もっとも,実際の音声では完全にイコールにはならないと思いますが,概ねこのような性質を持っています.こういった関数を周期Tの周期関数と呼びます.例えばサイン関数は周期2πの周期関数です.

この周期Tを求める手法として上記の本では「自己相関関数」を用いています.関数fに対する自己相関関数R_ffを,今回次のように定義します.
R_{ff}(\tau) = \frac{(f(t),f(t+\tau))}{||f(t)||\,\,||f(t+\tau)||}\\ ただし,実装するときにどうするかをはっきりしたいので,関数の内積とノルムは次のように定義します. (f(t),f(t+\tau)) = \int_{t_0}^{t_1} f(t)f(t+\tau)dt \\ ||f(t)|| = \sqrt{\int_{t_0}^{t_1}f(t)^2 dt }\\ ||f(t+\tau)|| =\sqrt{ \int_{t_0}^{t_1}f(t+\tau)^2 dt} \\
関数f(t)とf(t+τ)の相関係数みたいなものなので,関数のノルムで割るかどうかや,関数の平均値を減じるかどうかは人それぞれだと思います.

さてこの自己相関関数R_ffを実際に計算していくとこのようになります.
τを変化していき,τ=nT ( n = 0,1,2,... )となる点で似たパターンとなるため,R_ffが極大値を取ることがわかります.

2.抽出アルゴリズム

ソースコードを貼る前に,実際にプログラムを組んで「あー」という音を読み込ませて,その音声に対する自己相関関数を求めるとこんな感じになります.
とまぁ現実の音をやってみるとそんなうまくいかないようです.結構ギザギザしてて嫌な感じです.

恐らくフラクタル図形のように「あー」という音の中にも似た部分があるようです.それはそれで面白いのですが…….

まぁ自分の目で見ればどれが目的の周期なのか一目瞭然なのですが,できれば自動的に判定したいところです.

とりあえずFFTで高周波成分を除去するハイパスフィルタを実装するとこんな感じになります.緑色の部分がハイパスフィルタで高周波成分を除去したもの.移動平均でも良いと思います.
そんでもってscipy.signalの極大値の要素番号をsignal.argrelmaxで求めて,しきい値0.2よりも大きい相関以上かつ極大となっている要素番号を取得すると,{5,  646, 1291, 1938, 2582, 3228, 3872, 4520} みたいな等差数列になっているので差を求めてやればそれっぽい周期が求められる.

その周期で音声の波形を10個ほど取り出すとこんな感じになった.
繰り返されている部分がいい感じに取り出せました.とは言うものの周期Tをint型に型キャストしているのでズレていってしまいますがまぁこんなもんでしょう.

この繰り返されている波形データだけで音声認識とかできないか考え中なところです.

3.プログラム

コメントは多めにしたつもりではありますがうまくいかない場合はコメントを参考にしつつ頑張って下さい.

#coding:utf-8
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import wave
from scipy import signal
"""
参考
[1] 波形を見る - 人工知能に関する断創録 http://aidiary.hatenablog.com/entry/20110519/1305808715
[2] 雨宮好文 監修, 佐藤幸男 著『信号処理入門』 オーム社
"""
def read_wave(path):
""" waveファイルを読み込む関数 """
wf = wave.open(path , "r" )
fs = wf.getframerate() # サンプリング周波数
x = wf.readframes(wf.getnframes())
x = np.frombuffer(x, dtype= "int16") / 32768.0 # -1 - +1に正規化
wf.close()
# fsはサンプリング周波数
return (x,fs)
def HPF(x,n_dim):
""" ハイパスフィルタ,n_dimは打ち切る周波数 """
c = np.fft.rfft(x) # 高速フーリエ変換
c[n_dim:] = 0.0 # 高周波成分除去
return np.fft.irfft(c)
def cross_correlation(v1,v2,low,high,tau):
""" ベクトルv1,v2の相互相関関数 """
# v1の要素番号lowからhightまで
# v2の要素番号low+tauからhigh+tauまでを取り出す
x1 = v1[low:high]
x2 = v1[(low+tau):(high+tau)]
# ノルムを1にする
x1 = x1 / np.linalg.norm(x1)
x2 = x2 / np.linalg.norm(x2)
# x1,x2の内積が相関係数となる
return x1.T.dot(x2)
if __name__=="__main__":
# データ読み取り
print("reading voice.wav")
x,fs = read_wave("./voice.wav")
# 自己相関関数を計算
print("calculating R_ff")
R = np.array([ cross_correlation(x,x,0,fs,tau) for tau in range(fs) ])
# 周期を計算してく
print("calculating T")
# まずハイパスフィルタで高周波成分を除去
R_HPF = HPF(R,len(R) / 20)
# 自己相関関数はτが小さいほうが相関が高いため,τが小さい部分を取り出す
R_HPF[:fs/5]
# 極大値の要素番号を取得
local_max, = signal.argrelmax(R_HPF)
# 極大値の中で0.2よりも大きい部分の要素番号を取得
threshold = 0.2 # しきい値
local_max = local_max[ R_HPF[ local_max ] > threshold ]
# この時 local_max は(うまく行けば)
# array([ 5, 646, 1291, 1938, 2582, 3228, 3872, 4520])
# のような等差数列になっているので各項の差を取る
diff = np.diff(local_max)
# diffは(うまく行けば)こうなっている
# array([641, 645, 647, 644, 646, 644, 648])
# 外れ値があるかもしれないので,平均値ではなく中央値を使うと良い
T = (int)(np.median(diff))
# 周期Tで取り出して表示
for i in range(10):
plt.plot(x[(i*T):(i*T+T)])
plt.title("T = %d" % T )
plt.show()
view raw extract_wave.py hosted with ❤ by GitHub

2016年2月24日水曜日

水玉コラ作成ソフトを公開した話

Bloggerで過去の記事に追記をすると最新の記事の扱いになる現象が勃発している今日この頃です.先日「水玉コラ作成ソフト」をVectorさんで公開しました


一応こんな感じに動作する.
これを使うことで慣れれば2,3分で水玉コラを作ることができるようになる.やったぜ.

一度フリーソフトを公開してみたかったので夢というか目標が達成できてよかった.Vectorさんもフリーソフトの審査を人の目が見てくれているようでとても良い対応だったのでよかった.

ただ現状ダウンロードして実行すると次のような画面が出る……(´・ω・`)
しばらくの辛抱らしい.

Windows SmartScreenは認識されないアプリの起動を停止しました……と.一応弁明させていただきますと僕がこの画面を作ってパスワードを盗み取ろうとしているわけではないです.

この画面,沢山ダウンロードされると消えるらしいのだけど俺だったらこんなソフト使わないな(笑).こういう詐欺もあるだろうし,気をつけねば.

フーリエ級数の可視化プログラムの実装[Processing]

もはや2週間前のネタを真似ただけで新規性に乏しいのですが……(´・ω・`)
一応実装にあたって元ネタを書いておかないと申し訳ないのでツイートを貼らせていただきます……



という経緯です.

今回の実装はProcessingによるものなので上記ツイートのような数式で描くことができませんが,プログラミング言語というだけあって自由度は高いものとなっています.

円の数とか任意に決められますし.関数も自由に決められますし.

追記:鰺坂もっちょ先生がトゥギャってくれました→世はまさに大フーリエ時代 - Togetterまとめ

・ソースコード


例として矩形波を近似しています.関数funcの中身を[0,1)区間で変えてやればその形になりますが,無限大に発散させたりするとダメです.
あと数字が小さすぎる(1.0とか)だと小さすぎて見えませんので気をつけてください.


// フーリエ級数可視化クラス
class FourierPlotter {
int n_data; // データの個数
int n_approx; // 近似次数
float[][] radius; // 半径.radius[0][k]にsin成分のk次の成分が入る
float[] data; // データ
float centerX; // 中心X座標
float centerY; // 中心Y座標
float phase; // 位相のズレ
public float x; // 先端部分のX座標
public float y; // 先端部分のY座標
// コンストラクタ
FourierPlotter(float[] data, int n_approx,
float centerX, float centerY, float phase) {
// 引数をメンバ変数に代入した後,フーリへ級数展開
this.data = data;
this.n_data = data.length;
this.n_approx = n_approx;
this.phase = phase;
this.centerX = this.x = centerX;
this.centerY = this.y = centerY;
this.calcRadius();
}
// フーリエ級数展開を計算する関数
void calcRadius() {
// フーリエ級数の係数は半径に当たる
this.radius = new float[2][this.n_approx];
float dt = 2.0*PI / this.n_data; // 微小長さdt
// バイアス項(0次の項)は無視している
for ( int i = 1; i < this.n_approx; i++ ) {
for (int j = 0; j < this.n_data; j++ ) {
float t = 2.0*PI*j/this.n_data;
// 普通に矩形積分する
this.radius[0][i] += sin(i*t)*this.data[j]*dt/PI; // sin成分の計算
this.radius[1][i] += cos(i*t)*this.data[j]*dt/PI; // cos成分の計算
}
}
}
// 描画を行う関数
void visualize(float theta) {
// x,y座標をとりあえず中心に持ってくる
this.x = this.centerX;
this.y = this.centerY;
float tempX, tempY;
for (int i = 0; i < this.n_approx; i++ ) {
for (int j= 0; j<2; j++) {
// 円を描く
ellipse(x, y, 2.0*this.radius[j][i], 2.0*this.radius[j][i]);
tempX = x;
tempY = y;
// 先端部分の位置座標を計算(j=1の時,余弦なので位相がPI/2ずれる)
x += this.radius[j][i]*cos(i*theta+PI*j/2 + this.phase);
y += this.radius[j][i]*sin(i*theta+PI*j/2 + this.phase);
line(x, y, tempX, tempY); // 各円の中心をを直線で結ぶ
}
}
}
}
float scale = 1.0; // 拡大率
float dx=0.0; // x方向の移動
float dy=-0.0; // y方向の移動
int n_data = 100; // データの個数
FourierPlotter fp; // 描画クラス
float[] points; // 過去に通った座標
int count; // ループカウンタ
int n_approx = 20; // 近似次数
void setup() {
size(640, 480);
// 関数funcを離散的なデータにしてFourierPlotterに渡す
float[] data = new float[n_data];
for (int i = 0; i < n_data; i++ )
data[i] = func( (float)(i)/n_data );
fp = new FourierPlotter(data, n_approx, -100, 0, 0);
// 諸々を初期化
count = 0;
points = new float[1000];
}
void draw() {
background(0);
translate(width/2-dx, height/2-dy); // 原点を中心に移動
scale(scale, scale);
fill(0, 0, 0, 0);
strokeWeight(3);
stroke( 0, 255, 0);
float theta = count * 2*PI / n_data;
fp.visualize(theta); // 描画
points[count%points.length] = fp.y; // y座標を保存
// 過去のデータの描画
stroke(255,0,0);
line(fp.x,fp.y,100.0,fp.y);
plot(points,100,0,count%points.length);
count +=1; // ループカウンタを増やす
// フレームを保存する場合はコメントインする
//saveFrame("./frames/#####.png");
}
// [0,1)区間で定義される区分的に滑らかな関数
// 近似する関数の対象なのでここを変えればいい
float func(float x) {
// 矩形波
return x < 0.5 ? -50:50;
// サイン波
//return 100*sin(2*x*PI);
}
// 配列arrをプロットする関数
void plot(float[] arr,float x,float y,int startIndex){
int N = arr.length;
float y2 = arr[startIndex%N];
for(int i = 1 ; i < N ; i++ ){
line(x+N-i+1,y2,x+N-i,y+arr[(startIndex+i)%N]);
y2 = arr[(startIndex+i)%N] + y;
}
}
void keyPressed() {
// キー操作による拡大・移動
if (key == CODED) {
if (keyCode == UP) {
dy -= 10;
} else if (keyCode == DOWN) {
dy += 10;
} else if (keyCode == LEFT) {
dx -= 10;
} else if (keyCode == RIGHT) {
dx += 10;
}
} else if (key == '+') {
scale *= 1.05;
} else if (key=='-') {
scale /= 1.05;
}
}

2016年2月17日水曜日

画像を一筆書きで描くプログラムを実装した[Python,Processing]

1.概要

この動画の最後のやつの,ほぼ完璧なトレースができます.
 

とりあえず順序としては
1.画像を読み込む
2.エッジ部分の座標を取り出す
3.巡回セールスマン問題として一筆書き経路を探索
4.フーリエ級数展開
5.画像を描画
という手順です.

今回サンプルとして画像はこいつを使います.勝手に使ってください.
Processingしかできない人や,Pythonの実行環境ないひとは一筆書きの経路を探索した結果の座標ファイルを置いておきます.こいつをProcessingのソースコードと同一フォルダに入れておけば一応はできます.ちなみにこんな感じ.


プログラムが長過ぎるので注意してください.もっとスマートにかければ良いのだけれど,無駄にクラスを作成して再利用しやすい形にした……(´・3・`)ドウセツカワナイノニ

2.プログラム

まず上記の手順の1-3を行うソースコードです.
蟻コロニー最適化のプログラムなのでこの前書いたやつの書き直しみたいな感じです.
実際はopt2を使って更に最適化してますが,それのコードはネットのやつを丸パクリしたやつなので流石に上げられません(参考URL先に借りたソースコードがあります).

#coding:utf-8
import cv2
import numpy as np
import time
import matplotlib.pyplot as plt
import pandas as pd
from scipy.spatial import distance as dis
"""
参考URL
[1] 蟻コロニー最適化 - Wikipedia https://ja.wikipedia.org/wiki/蟻コロニー最適化
[2] 任意の確率密度分布に従う乱数の生成(von Neumannの棄却法) | Pacocat's Life http://pacocat.com/?p=596
[3] Algorithms with Python / 巡回セールスマン問題 http://www.geocities.jp/m_hiroi/light/pyalgo64.html
"""
class TSP:
def __init__(self,path=None,alpha = 1.0,beta = 1.0,Q = 1.0,vanish_ratio = 0.95):
""" 初期化を行う関数 """
self.alpha = alpha # フェロモンの優先度
self.beta = beta # ヒューリスティック情報(距離)の優先度
self.Q = Q # フェロモン変化量の係数
self.vanish_ratio = vanish_ratio # 蒸発率
if path is not None:
self.set_loc(np.array(pd.read_csv(path)))
def set_loc(self,locations):
""" 位置座標を設定する関数 """
self.loc = locations # x,y座標
self.n_data = len(self.loc) # データ数
self.dist = dis.squareform(dis.pdist(self.loc)) # 距離の表を作成
self.weight = np.random.random_sample((self.n_data,self.n_data))+1.0 # フェロモンの量
self.result = np.arange(self.n_data) # もっともよかった順序を保存する
def cost(self,order):
""" 指定された順序のコスト計算関数 """
order2 = np.r_[order[1:],order[0]]
return np.sum(tsp.dist[order,order2])
def plot(self,order=None):
""" 指定された順序でプロットする関数 """
if order is None:
plt.plot(self.loc[:,0],self.loc[:,1])
else:
plt.plot(self.loc[order,0],self.loc[order,1])
plt.show()
def solve(self,n_agent=1000):
""" 巡回セールスマン問題を蟻コロニー最適化で解く """
order = np.zeros(self.n_data,np.int) # 巡回経路
delta = np.zeros((self.n_data,self.n_data)) #フェロモン変化量
for k in range(n_agent):
city = np.arange(self.n_data)
now_city = np.random.randint(self.n_data) # 現在居る都市番号
city = city[ city != now_city ]
order[0] = now_city
for j in range(1,self.n_data):
upper = np.power(self.weight[now_city,city],self.alpha)*np.power(self.dist[now_city,city],-self.beta)
evaluation = upper / np.sum(upper) # 評価関数
percentage = evaluation / np.sum(evaluation) # 移動確率
index = self.random_index2(percentage) # 移動先の要素番号取得
# 状態の更新
now_city = city[ index ]
city = city[ city != now_city ]
order[j] = now_city
L = self.cost(order) # 経路のコストを計算
# フェロモンの変化量を計算
delta[:,:] = 0.0
c = self.Q / L
for j in range(self.n_data-1):
delta[order[j],order[j+1]] = c
delta[order[j+1],order[j]] = c
# フェロモン更新
self.weight *= self.vanish_ratio
self.weight += delta
# 今までで最も良ければ結果を更新
if self.cost(self.result) > L:
self.result = order.copy()
# デバッグ用
print("Agent ... %d,\t Now Cost %lf,\t Best Cost ... %lf" % (k,L,self.cost(self.result)))
return self.result
def save(self,out_path):
""" 最もコストが低かった順序で保存する関数 """
points = self.loc[ self.result ]
f = open(out_path,"w")
f.write("x,y\n")
for i in range(len(points)):
f.write(str(points[i,0]) + "," + str(points[i,1])+"\n")
f.close()
def random_index(self,percentage):
""" 任意の確率分布に従って乱数を生成する関数 """
n_percentage = len(percentage)
arg = np.argsort(percentage)
while True:
index = np.random.randint(n_percentage)
y = np.random.random()
if y < percentage[index]:
return index
def random_index2(self,percentage):
""" 精度低めで任意の確率分布に従って乱数を生成する関数 """
n_percentage = len(percentage)
arg = np.argsort(percentage)[::-1]
n_arg = min(n_percentage,10)
percentage = percentage / np.sum( percentage[arg] )
while True:
index = np.random.randint(n_arg)
y = np.random.random()
if y < percentage[arg[index]]:
return arg[index]
def save_edge_points(img_path,out_path):
# 画像を読み込んでエッジ処理
img = cv2.imread(img_path)
edge = cv2.Canny(img,100,200)
# エッジになっているx,y座標を取り出す
h,w = edge.shape
x = np.arange(w)
y = np.arange(h)
X,Y = np.meshgrid(x,y)
# 255になっている部分がエッジ部分
X_true = X[ edge > 128 ]
Y_true = Y[ edge > 128 ]
# エッジの点になっている座標が入っている
index = np.array([X_true,Y_true]).T
# 保存
f = open(out_path,"w")
f.write("x,y\n")
for i in range(len(index)):
f.write(str(index[i,0]) + "," + str(index[i,1])+"\n")
f.close()
if __name__=="__main__":
# エッジを検出し保存.img.pngが対象の画像
save_edge_points("img.png","edge_points.csv")
# TSPで巡回セールスマン問題として一筆書きの手順を計算・保存
tsp = TSP(path="edge_points.csv",alpha=1.0,beta=16.0,Q=1.0e3,vanish_ratio = 0.8)
tsp.solve(100)
tsp.save("best_order.csv")
tsp.plot(tsp.result)
view raw ImageEdgeTSP.py hosted with ❤ by GitHub

次にProcessingで上記の手順の4,5の描画を行うコード

class FourierPlotter {
int n_data; // データの個数
int n_approx; // 近似次数
float[][] radius; // 半径
float[] data; // データ
float centerX; // 中心X座標
float centerY; // 中心Y座標
float phase; // 位相のズレ
public float x; // 先端部分のX座標
public float y; // 先端部分のY座標
// コンストラクタ
FourierPlotter(float[] data, int n_approx,
float centerX, float centerY, float phase) {
// 引数をメンバ変数に代入した後,フーリへ級数展開
this.data = data;
this.n_data = data.length;
this.n_approx = n_approx;
this.phase = phase;
this.centerX = this.x = centerX;
this.centerY = this.y = centerY;
this.calcRadius();
}
// フーリエ級数展開を計算する関数
void calcRadius() {
// フーリエ級数の係数は半径に当たる
this.radius = new float[2][this.n_approx];
float dt = 2.0*PI / this.n_data; // 微小長さdt
// バイアス項(0次の項)は無視している
for ( int i = 1; i < this.n_approx; i++ ) {
for (int j = 0; j < this.n_data; j++ ) {
float t = 2.0*PI*j/this.n_data;
// 普通に矩形積分する
this.radius[0][i] += sin(i*t)*this.data[j]*dt/PI;
this.radius[1][i] += cos(i*t)*this.data[j]*dt/PI;
}
}
}
// 描画を行う関数
void visualize(float theta) {
// x,y座標をとりあえず中心に持ってくる
this.x = this.centerX;
this.y = this.centerY;
float tempX, tempY;
for (int i = 0; i < this.n_approx; i++ ) {
for (int j= 0; j<2; j++) {
// 円を描く
ellipse(x, y, 2.0*this.radius[j][i], 2.0*this.radius[j][i]);
tempX = x;
tempY = y;
// 先端部分の位置座標を計算(j=1の時,余弦なので位相がPI/2ずれる)
x += this.radius[j][i]*cos(i*theta+PI*j/2 + this.phase);
y += this.radius[j][i]*sin(i*theta+PI*j/2 + this.phase);
line(x, y, tempX, tempY); // 各円の中心をを直線で結ぶ
}
}
}
}
class Fourier2d {
float[][] points; // 過去に通った座標
int n_data; // データ数
FourierPlotter fpX; // FourierPlotterクラスX方向
FourierPlotter fpY; // FourierPlotterクラスY方向
int count; // ループカウンタ
int centerX;
int centerY;
// コンストラクタ
Fourier2d(String filename,int centerX,int centerY) {
float[][] data = load_data(filename);
this.n_data = data[0].length;
this.points = new float[2][n_data];
this.count = 0;
this.centerX = centerX;
this.centerY = centerY;
this.fpX = new FourierPlotter(data[0], n_data, centerX+150, centerY+150, -PI/2);
this.fpY = new FourierPlotter(data[1], n_data, centerX-150, centerY-150, 0);
}
// x,yのデータを読み込む関数
float[][] load_data(String path) {
// 文字列を読み込む
String lines[] = loadStrings(path);
FloatList x = new FloatList();
FloatList y = new FloatList();
// 先頭行(ヘッダー)は読み飛ばすので1始まり
for (int i=1; i < lines.length; i++) {
// コンマで区切って2つ以上の要素があったらリストに加える
String [] element =split(lines[i], ',');
if (element.length >= 2 ) {
x.append(parseFloat(element[0]));
y.append(parseFloat(element[1]));
}
}
float[][] data = new float[2][x.size()];
data[0] = x.array();
data[1] = y.array();
return data;
}
void visualize( ) {
float theta = this.count * 2*PI / this.n_data;
fill(0, 0, 0, 0);
strokeWeight(3);
// 円を描画
stroke( 0, 255, 0);
this.fpX.visualize(theta);
stroke( 255, 0, 0);
this.fpY.visualize(theta);
// 色を変える
stroke(0, 255, 255);
fill(0, 255, 255);
strokeWeight(1);
// 円の先端からの直線を描画
line(fpX.x, fpX.y, fpX.x, fpY.y);
line(fpY.x, fpY.y, fpX.x, fpY.y);
rect(fpX.x, fpY.y, 1, 1);
// 軌跡を描画
stroke(255, 255, 255);
fill(255, 255, 255);
strokeWeight(3);
this.points[0][this.count%n_data] = fpX.x;
this.points[1][this.count%n_data] = fpY.y;
for (int i = 0; i < min(this.n_data, this.count) - 1; i++ )
line(points[0][i], points[1][i], points[0][i+1], points[1][i+1]);
this.count+=1; // stepをすすめる
}
}
float scale = 0.75; // 拡大率
float dx=0.0; // x方向の移動
float dy=-0.0; // y方向の移動
Fourier2d f1; // 描画クラス
void setup() {
size(640, 480);
// ここでデータを読み込むので同一フォルダにcsvファイルが必要
f1 = new Fourier2d("best_order.csv", -100, 100);
}
void draw() {
background(0);
translate(width/2-dx, height/2-dy); // 原点を中心に移動
scale(scale, scale);
// 描画
f1.visualize();
//saveFrame("./frames/#####.png");
}
void keyPressed() {
// キー操作による拡大・移動
if (key == CODED) {
if (keyCode == UP) {
dy -= 10;
} else if (keyCode == DOWN) {
dy += 10;
} else if (keyCode == LEFT) {
dx -= 10;
} else if (keyCode == RIGHT) {
dx += 10;
}
} else if (key == '+') {
scale *= 1.05;
} else if (key=='-') {
scale /= 1.05;
}
}
view raw DrawEdge.pde hosted with ❤ by GitHub

初音ミクを三角関数で描いてみた

1.動画紹介

フーリエ級数の視覚化を見て動画を作った.



まぁ二番煎じなんですけど.その辺の詳細はこちらで.

2.手法とか

まず序盤のやつはこいつ.Processingで作ったフーリエ級数の視覚化プログラム.こいつでいろんな関数を近似している.ここの先で先駆者たちのツイートが見られます.
フーリエ級数の可視化プログラムの実装[Processing]


次に出てくる二次元平面での三角関数的な奴ってのはこれ.実はフーリエ変換ではなく離散コサイン変換の二次元の基底関数なので嘘といえば嘘だけど,まぁそんなに違いはないし説明が面倒なので省略した.
離散コサイン変換(DCT)をPythonで実装した[Python]


その次の巡回セールスマン問題についてはこいつで解いた.基本的に蟻コロニー最適化を用いているけど,2000個の点で蟻コロニー最適化をすると遅すぎるので,パラメータを変えて貪欲法みたいな方法で経路探索して,その下のサイトで紹介されているopt2法のプログラムを用いてる,

・巡回セールスマン問題を蟻コロニー最適化と遺伝的アルゴリズムで解いてみる[Python]
Algorithms with Python / 巡回セールスマン問題


そんで最後のやつはフーリエ級数の可視化プログラムを使って,巡回セールスマン問題でもとめた一筆書きのルートを描いてる.
・画像を一筆書きで描くプログラムを実装した[Python,Processing]

結構大掛かりなプログラムだった割に動画を見てみると正直あまり面白くない……(´・ω・`)
アイデアおもついて実装したら面白くないのよくあるから仕方ないか…….

2016年2月14日日曜日

巡回セールスマン問題を蟻コロニー最適化と遺伝的アルゴリズムで解いてみる[Python]

巡回セールスマン問題(Traveling Salesman Problem,TSP)は有名だけれどなにげに解いたことがなかったのでちょいと実装してみました.
手法としてはいろいろあると思うのですが,今回は遺伝的アルゴリズム(GA)と蟻コロニー最適化(ACO)の2つを実装・比較しました.

1.巡回セールスマン問題

よく出される例としてはゴミ収集車の経路でしょうか.ゴミ収集所から出発して,100軒の家を最短で全て回ってゴミ収集所にまた戻ってくるまでの経路を求める話です.

まぁ僕がここで云々説明せずともネット上には沢山関連するサイトが有りますからそちらを参照してください.とりあえずWikipediaと検索したらトップに出てきたサイトのURLを貼っときます.

真ん中のサイトは手法について非常に詳しく解説されている上,Pythonで実装されたソースコードがありますのでそちらもごらんになると良いかと思います.

一番下のサイトは巡回セールスマンについての説明が詳しく,フリーソフトの紹介もされています.


この問題はまだ多項式時間で最適解を解くことができるアルゴリズムが無く,うちの大学でも研究してる研究室がたしかあった気がします.

2.蟻コロニー最適化による実装

蟻コロニー最適化に関する数式は今回全てWikipediaに載っていたものを利用しました(蟻コロニー最適化 - Wikipedia).
一応『心はプログラムできるか』という本を読んだ時に出てきてまして非常にわかりやすい解説がなされていましたので読んでみると良いかと思います.

以下ソースコード
#coding:utf-8
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from scipy.spatial import distance as dis
"""
参考URL
[1] 蟻コロニー最適化 - Wikipedia https://ja.wikipedia.org/wiki/蟻コロニー最適化
[2] 任意の確率密度分布に従う乱数の生成(von Neumannの棄却法) | Pacocat's Life http://pacocat.com/?p=596
"""
class TSP:
def __init__(self,path=None,alpha = 1.0,beta = 1.0,Q = 1.0,vanish_ratio = 0.95):
""" 初期化を行う関数 """
self.alpha = alpha # フェロモンの優先度
self.beta = beta # ヒューリスティック情報(距離)の優先度
self.Q = Q # フェロモン変化量の係数
self.vanish_ratio = vanish_ratio # 蒸発率
if path is not None:
self.set_loc(np.array(pd.read_csv(path)))
def set_loc(self,locations):
""" 位置座標を設定する関数 """
self.loc = locations # x,y座標
self.n_data = len(self.loc) # データ数
self.dist = dis.squareform(dis.pdist(self.loc)) # 距離の表を作成
self.weight = np.random.random_sample((self.n_data,self.n_data)) # フェロモンの量
self.result = np.arange(self.n_data) # もっともよかった順序を保存する
def cost(self,order):
""" 指定された順序のコスト計算関数 """
n_order = len(order)
return np.sum( [ self.dist[order[i],order[(i+1)%n_order]] for i in np.arange(n_order) ] )
def plot(self,order=None):
""" 指定された順序でプロットする関数 """
if order is None:
plt.plot(self.loc[:,0],self.loc[:,1])
else:
plt.plot(self.loc[order,0],self.loc[order,1])
plt.show()
def solve(self,n_agent=1000):
""" 巡回セールスマン問題を蟻コロニー最適化で解く """
order = np.zeros(self.n_data,np.int) # 巡回経路
delta = np.zeros((self.n_data,self.n_data)) #フェロモン変化量
for k in range(n_agent):
city = np.arange(self.n_data)
now_city = np.random.randint(self.n_data) # 現在居る都市番号
city = city[ city != now_city ]
order[0] = now_city
for j in range(1,self.n_data):
upper = np.power(self.weight[now_city,city],self.alpha)*np.power(self.dist[now_city,city],-self.beta)
evaluation = upper / np.sum(upper) # 評価関数
percentage = evaluation / np.sum(evaluation) # 移動確率
index = self.random_index(percentage) # 移動先の要素番号取得
# 状態の更新
now_city = city[ index ]
city = city[ city != now_city ]
order[j] = now_city
L = self.cost(order) # 経路のコストを計算
# フェロモンの変化量を計算
delta[:,:] = 0.0
c = self.Q / L
for j in range(self.n_data-1):
delta[order[j],order[j+1]] = c
delta[order[j+1],order[j]] = c
# フェロモン更新
self.weight *= self.vanish_ratio
self.weight += delta
# 今までで最も良ければ結果を更新
if self.cost(self.result) > L:
self.result = order.copy()
# デバッグ用
print("Agent ... %d , Cost ... %lf" % (k,self.cost(self.result)))
return self.result
def random_index(self,percentage):
""" 任意の確率分布に従って乱数を生成する関数 """
n_percentage = len(percentage)
while True:
index = np.random.randint(n_percentage)
y = np.random.random()
if y < percentage[index]:
return index
if __name__=="__main__":
#tsp = TSP(path="input.csv")
tsp = TSP()
tsp.set_loc(np.random.random_sample((30,2)))
tsp.plot() # 計算前
tsp.solve(n_agent=1000) # 1000匹の蟻を歩かせる
tsp.plot(tsp.result) # 計算後
view raw TSP_ACO.py hosted with ❤ by GitHub
とりあえず評価のちゃんとした結果は遺伝的アルゴリズムの実装の後に書きます.

3.遺伝的アルゴリズムによる実装

ぶっちゃけ蟻コロニー最適化よりも精度低いです.30個点でさえも蟻コロニー最適化に負けています.1000個ぐらいの点になるともう最適解求めるなんて夢のまた夢でした.
原因としては恐らく突然変異がランダムすぎて,ほとんど改悪になるばかりという結果でしょうか.遺伝子は巡回経路の順番を表した変数(5つの点なら[2,4,3,1,0]という配列)です.突然変異で中身を入れ替えてます.
※追記:先日図書館にてほかの人の実装例を見ましたがこれとは異なる手法を用いていました.それを踏まえるとこのプログラムは一般的な実装例とは異なると思われますので注意してください.

ソースコード
#coding:utf-8
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from scipy.spatial import distance as dis
class TSP:
def __init__(self,path=None,n_gene = 256,n_parent = 10,change_ratio = 0.1):
""" 初期化を行う関数 """
self.n_gene = n_gene # 一世代の遺伝子の個数
self.n_parent = 10 # 親として残す個体数
self.change_ratio = change_ratio # 突然変異で変化させる場所の数
if path is not None:
self.set_loc(np.array(pd.read_csv(path)))
def init_genes(self,):
""" 遺伝子をランダムに初期化 """
self.genes = np.zeros((self.n_gene,self.n_data),np.int)
order = np.arange(self.n_data)
for i in range(self.n_gene):
np.random.shuffle(order)
self.genes[i] = order.copy()
self.sort()
def set_loc(self,locations):
""" 位置座標を設定する関数 """
self.loc = locations # x,y座標
self.n_data = len(self.loc) # データ数
self.dist = dis.squareform(dis.pdist(self.loc)) # 距離の表を作成
self.init_genes() # 遺伝子を初期化
def cost(self,order):
""" 指定された順序のコスト計算関数 """
return np.sum( [ self.dist[order[i],order[(i+1)%self.n_data]] for i in np.arange(self.n_data) ] )
def plot(self,order=None):
""" 指定された順序でプロットする関数 """
if order is None:
plt.plot(self.loc[:,0],self.loc[:,1])
else:
plt.plot(self.loc[order,0],self.loc[order,1])
plt.show()
def solve(self,n_step=1000):
""" 遺伝的アルゴリズムで解く関数 """
for i in range(n_step):
print("Generation ... %d, Cost ... %lf" % (i,self.cost(self.genes[0])))
self.step()
self.result = self.genes[0]
return self.result
def step(self):
""" 遺伝子を一世代分進化させる関数 """
# 突然変異
for i in range(self.n_parent,self.n_gene):
self.genes[i] = self.mutation( np.random.randint(self.n_parent) )
self.sort() # ソートする
def sort(self):
""" 遺伝子を昇順にする関数 """
# コストを計算し,ソート
gene_cost = np.array([self.cost(i) for i in self.genes])
self.genes = self.genes[ np.argsort(gene_cost) ]
def mutation(self,index):
""" 突然変異を起こした遺伝子を返す関数 """
n_change = int(self.change_ratio * self.n_data)
gene = self.genes[index].copy()
for i in range(n_change):
# n_changeの個数だけ値を入れ替える
left = np.random.randint(self.n_data)
right = np.random.randint(self.n_data)
temp = gene[left]
gene[left] = gene[right]
gene[right] = temp
return gene
if __name__=="__main__":
#tsp = TSP(path="input.csv")
tsp = TSP()
tsp.set_loc(np.random.random_sample((30,2)))
tsp.plot()
tsp.solve()
tsp.plot(tsp.result)
view raw TSP_GA.py hosted with ❤ by GitHub

4.評価

一応同じデータを用いてやった結果です.30個の[0,1)のランダムな二次元の点について行いました.
パラメータはデフォルトです.まずは遺伝的アルゴリズム.
直線が交差してますね.コストは6.056765でした.続いて蟻コロニー最適化.
直線が交差すること無く,コストも5.701502です.しかも計算時間が遺伝的アルゴリズムよりも遥かに実行時間が早いです.

とりあえず今回の実装では蟻コロニー最適化のほうが早かったですが,遺伝的アルゴリズムも突然変異をもう少し工夫してやればもっと良い結果が出るような気がします.いつか焼きなまし法とかやってみたいです.

2016年2月10日水曜日

離散コサイン変換(DCT)をPythonで実装した[Python]

ダブルミーニングでテストが終わりました.春休みに入ったので今年の目標の「数学を勉強する」を早速実行してみます.将来勉強するはめになりそうなものから学ぼうと思うので,まずは主軸変換から勉強します.

フーリエ変換はnumpyやscipyで実装されているので,されていないであろう離散コサイン変換(DCT)を今日は実装してみました……と思っていたらscipy.fftpackにdctの実装ありました(公式サイト).こちらはWikipediaで紹介されている基底関数DCT-I,DCT-II,DCT-IIIが実装されているようです.

1.離散コサイン変換(DCT)の概要

離散コサイン変換(Discrete Cosine Transform)はWikipediaさんを見る限りではいろんな基底関数があるようですが,今手元にある本『画像処理とパターン認識入門』では離散コサイン変換の基底関数を次のように定義しています.Wikipediaで言うところのDCT-IIですね.
\phi_k[i] = \begin{cases} \frac{1}{\sqrt{N}} \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(k=0) \\ \sqrt{\frac{2}{N}} \cos {\frac{(2i+1)k\pi}{2N}} (k=1,2,...,N-1) \end{cases}

この基底関数ですがこんな感じのグラフになります.N=64,横軸がiに相当し上からk=0,1,2,...,9の時の基底関数のグラフです.この定義だとほぼ普通の三角関数ですね.
離散化された信号をf_iとすると,離散コサイン変換,離散コサイン逆変換の式は以下のとおりです.
C[k] = \sum_{i=0}^{N-1}f_{i}\phi_k[i] \,\,(k=0,1,...,N-1)\\ f_{i}=\sum_{k=0}^{N-1}C[k]\phi_{k}[i] \,\,(i=0,1,...,N-1)
とりあえずこいつを実装します.

2.離散コサイン変換(1次元)の実装例

まぁこんな感じです.関数phiは基底関数です.本で紹介されていた数式以外にWikipediaにあったDCT-IVもコメントアウトしてありますが一応実装してあります.
ベンチマークとして乱数で作った配列データを試しに変換・逆変換してみます.

#coding: utf-8
import numpy as np
import matplotlib.pyplot as plt
"""
参考:
[1]『画像処理とパターン認識入門』酒井幸市 著
[2] scipy.fftpack.dct http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.fftpack.dct.html
"""
class DCT:
def __init__(self,N):
self.N = N # データ数.
# 1次元離散コサイン変換の変換行列を予め作っておく
self.phi_1d = np.array([ self.phi(i) for i in range(self.N) ])
def dct(self,data):
""" 1次元離散コサイン変換を行う """
return self.phi_1d.dot(data)
def idct(self,c):
""" 1次元離散コサイン逆変換を行う """
return np.sum( self.phi_1d.T * c ,axis=1)
def phi(self,k):
""" 離散コサイン変換(DCT)の基底関数 """
# DCT-II
if k == 0:
return np.ones(self.N)/np.sqrt(self.N)
else:
return np.sqrt(2.0/self.N)*np.cos((k*np.pi/(2*self.N))*(np.arange(self.N)*2+1))
# DCT-IV(試しに実装してみた)
#return np.sqrt(2.0/N)*np.cos((np.pi*(k+0.5)/self.N)*(np.arange(self.N)+0.5))
if __name__=="__main__":
N = 100 # データ数を100とします
dct = DCT(N) # 離散コサイン変換を行うクラスを作成
x = np.random.random_sample(N) # N個の乱数データを作成
c = dct.dct(x) # 離散コサイン変換を実行
y = dct.idct(c) # 離散コサイン逆変換を実行
# 元のデータ(x)と復元したデータ(y)をグラフにしてみる
plt.plot(x,label="original")
plt.plot(y,label="restored")
plt.legend()
plt.title("original data and restored data")
plt.show()
view raw dct_1dim.py hosted with ❤ by GitHub
実行結果

まぁ問題なくデータが復元されてますね.乱数なので高周波数成分があるので圧縮は無理ですが.

3.離散コサイン変換(2次元)の概要

さて手元の本のタイトルには「画像処理」の文字が書かれています.すなわち二次元データに対する解説も書かれています(というかむしろそれが本題).なのでpythonで二次元データに対しても実装してみます.

本によれば二次元のDCT係数F_k,lは次のように表されるとのこと.また画像の濃度値f_i,jはDCT係数を用いてこのように逆変換できるとのこと.
F_{k,l}=\sum_{j=0}^{N-1}\sum_{i=0}^{N-1}f_{i,j}\phi_k[i]\phi_l[j] \\ f_{i,j}=\sum_{l=0}^{N-1}\sum_{k=0}^{N-1}F_{k,l}\phi_k[i]\phi_{l}[j]
ここでこの基底ベクトル(基底画像)がどんな形をしているか見てみます.
この画像,離散コサイン変換(DCT)で検索すると出てくるやつですね.これらの画像は10x10ピクセルの画像を100個並べたものですが,二次元離散コサイン変換ではこの100個の画像をうまいこと足し合わせることで様々な画像を表現するというのがテンションが上ります.(つまりこの画像の中にあんな画像,こんな画像まで,ありとあらゆる画像が含まれていると言っても過言ではない……?)

4.離散コサイン変換(2次元)の実装例

では実装です.scipyにも2次元の離散コサイン変換は実装されてないのでちょっとテンションが上ります.まぁ2次元のフーリエ変換は実装されてますが.
サンプルとして適当な画像を変換・逆変換してみます.
#coding: utf-8
import numpy as np
import matplotlib.pyplot as plt
"""
参考:
[1]『画像処理とパターン認識入門』酒井幸市 著
[2] scipy.fftpack.dct http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.fftpack.dct.html
"""
class DCT:
def __init__(self,N):
self.N = N # データ数.
# 1次元,2次元離散コサイン変換の基底ベクトルをあらかじめ作っておく
self.phi_1d = np.array([ self.phi(i) for i in range(self.N) ])
# Nが大きいとメモリリークを起こすので注意
# MNISTの28x28程度なら問題ない
self.phi_2d = np.zeros((N,N,N,N))
for i in range(N):
for j in range(N):
phi_i,phi_j = np.meshgrid(self.phi_1d[i],self.phi_1d[j])
self.phi_2d[i,j] = phi_i*phi_j
def dct(self,data):
""" 1次元離散コサイン変換を行う """
return self.phi_1d.dot(data)
def idct(self,c):
""" 1次元離散コサイン逆変換を行う """
return np.sum( self.phi_1d.T * c ,axis=1)
def dct2(self,data):
""" 2次元離散コサイン変換を行う """
return np.sum(self.phi_2d.reshape(N*N,N*N)*data.reshape(N*N),axis=1).reshape(N,N)
def idct2(self,c):
""" 2次元離散コサイン逆変換を行う """
return np.sum((c.reshape(N,N,1)*self.phi_2d.reshape(N,N,N*N)).reshape(N*N,N*N),axis=0).reshape(N,N)
def phi(self,k):
""" 離散コサイン変換(DCT)の基底関数 """
# DCT-II
if k == 0:
return np.ones(self.N)/np.sqrt(self.N)
else:
return np.sqrt(2.0/self.N)*np.cos((k*np.pi/(2*self.N))*(np.arange(self.N)*2+1))
# DCT-IV(試しに実装してみた)
#return np.sqrt(2.0/N)*np.cos((np.pi*(k+0.5)/self.N)*(np.arange(self.N)+0.5))
if __name__=="__main__":
N = 10 # データの次元は10x10とする
dct = DCT(10) # 離散コサイン変換を行うクラスを作成
# サンプル画像を作る
img = np.array([
[0,0,0,0,0,0,0,0,0,0],
[0,0,1,1,1,1,1,1,0,0],
[0,1,0,0,0,0,0,0,1,0],
[0,1,0,0,0,0,0,0,1,0],
[0,0,0,0,0,0,1,1,0,0],
[0,0,0,0,1,1,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0],
[0,0,1,0,0,0,0,0,0,0],
[0,1,1,1,1,1,1,1,1,0],
[0,0,0,0,0,0,0,0,0,0]
])
c = dct.dct2(img) # 2次元離散コサイン変換
y = dct.idct2(c) # 2次元離散コサイン逆変換
# 元の画像と復元したものを表示
plt.subplot(1,2,1)
plt.imshow(img,cmap="Greys")
plt.title("original")
plt.xticks([])
plt.subplot(1,2,2)
plt.imshow(y,cmap="Greys")
plt.title("restored")
plt.xticks([])
plt.show()
view raw dct_2dim.py hosted with ❤ by GitHub
実行結果です.
画像がちゃんと元の状態に戻っているのがわかります.ちなみにDCT係数(周波数成分)はこんな感じでした.
概ね右下に行くほど色が薄くなっています.ここから低周波成分(左上)が多くを占めていることがわかります.
高周波成分を消していったものがこちらです.
DCT係数cについてc[i:,i:] = 0とした時に復元された画像です.i=3でだいたい認識できそうですね.結構データを圧縮できてるのではないでしょうか.まぁまぁうまく行って良かったです.

2016年2月5日金曜日

相関係数を用いてmnistのラベルを認識してみる[Python]

線形代数はわかるけど,ディープラーニングとかわかる気がしねぇ(゜∀。)ワヒャヒャヒャヒャヒャヒャ
という人向けです.
各ラベルごとの平均画像との相関関係からmnistのラベルを予想します.

1.使用する画像

MNIST は 0 から 9 の手書き数字が書かれた,70,000 点の白黒画像です.こんな感じ.
画像は28×28の784ピクセル.今回は学習データを評価用のデータに含めちゃダメなので,この画像データ70,000点のうち,60,000点を学習用のデータとし,10,000点を評価用のデータとします。
とは言うものの学習という学習はしないのであまり関係がないけれど.

2.相関係数の求め方

まぁ今回は一応相関係数を求める部分も実装したのでTeXの練習がてら書いときます.普通はnumpy.corrcoef関数とか使えばいいと思います.
次のようなベクトルx,yがあったとします.
このとき,x,yの相関係数は次のようになります.

ただし,xバー,yバーは各要素の平均です.
同じことですが,これはx,yの平均ベクトルを次のように定義してやるともう少し見通しが良くなります.
とすると,相関係数rは
と表すことができ,x,yベクトルから要素の平均値を引いたベクトルの方向余弦(cosθ)になるわけです.(割とこれが言いたいだけの記事だったりする.線形代数の先生がドヤ顔して話してた)

今回作ったプログラムではxは調べたい画像のベクトル,yは0,1,2,3...9の平均画像に当たります.最も似ている(相関がある)ものを探していきます.

3.ソースコード


#coding: utf-8
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import fetch_mldata
from sklearn.cross_validation import train_test_split
from sklearn.metrics import confusion_matrix, classification_report
def corrcoef(x,y):
""" ベクトルx,yの相関係数を求める関数 """
# ノルムが0になる場合はないものとします
# 要素の平均を引く
x = x - np.average(x)
y = y - np.average(y)
# ベクトルの内積はベクトルを転置して行列の積となる
return x.T.dot(y)/(np.linalg.norm(x)*np.linalg.norm(y))
# mnistの手書き数字データをロード
# カレントディレクトリ(.)にない場合は、
# Webから自動的にダウンロードされる(時間がかかるので注意!)
# 70000サンプル,28x28ピクセル
mnist = fetch_mldata('MNIST original', data_home=".")
"""
# 100個適当に表示してみる
for i in range(10):
for j in range(10):
img = mnist.data[ mnist.target == i ][j]
plt.subplot(10, 10, 10 * i + j + 1)
plt.axis('off')
plt.imshow( img.reshape(28, 28), cmap=plt.cm.gray_r, interpolation='nearest')
plt.show()
"""
# 訓練データを作成
X = mnist.data
y = mnist.target
# 訓練データとテストデータに分解
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=1./7.)
# 代表値を作成する
avg_img = np.zeros((10,X_train.shape[1]))
for i in range(10):
# ラベルがiの画像を取り出して,平均をとる
i_imgs = X_train[ y_train == i ]
avg_img[i] = np.average(i_imgs,axis=0)
"""
# 代表値(平均画像)を表示してみる
for i in range(10):
img = avg_img[i]
plt.subplot(1, 10, i + 1)
plt.axis('off')
plt.imshow( img.reshape(28, 28), cmap=plt.cm.gray_r, interpolation='nearest')
plt.show()
"""
# 予測
predictions = np.zeros(y_test.shape)
for i in range(len(y_test)):
test = X_test[i].astype(np.float)
# 内積が最も大きいものを予想ラベルとする
predictions[i] = np.argmax( [ corrcoef(test,img) for img in avg_img ] )
# 評価
print (confusion_matrix(y_test, predictions))
print (classification_report(y_test, predictions))

4.結果

こんな感じ.
[[ 878    0    3    6    4   40   36    0   14    2]
 [   0 1095   16    4    1    6    2    3   33    1]
 [  26   37  732   44   23    1   43   24   45    4]
 [   8   14   35  809    2   45    6   17   73   25]
 [   4   14    5    0  818    1   24    4   17  117]
 [  29   41   13  127   21  554   24    9   36   23]
 [  21   23   22    1    9   25  862    0    4    0]
 [  17   27   15    0   17    1    0  823   18   68]
 [   7   44   14   85    8   31   10    8  728   38]
 [  19   19    9   12   66    4    1   53   33  820]]
             precision    recall  f1-score   support

        0.0       0.87      0.89      0.88       983
        1.0       0.83      0.94      0.88      1161
        2.0       0.85      0.75      0.79       979
        3.0       0.74      0.78      0.76      1034
        4.0       0.84      0.81      0.83      1004
        5.0       0.78      0.63      0.70       877
        6.0       0.86      0.89      0.87       967
        7.0       0.87      0.83      0.85       986
        8.0       0.73      0.75      0.74       973
        9.0       0.75      0.79      0.77      1036

avg / total       0.81      0.81      0.81     10000
統計はよく知らない民なのでprecision,recallでググるとwikipediaの画像が非常にわかりやすいので見ると良いかと思います.まぁ普段生活する中で言う「的中率」というのはrecallだと思う….

幸いprecision,recall,f1-scoreも81%なので,とりあえず結果は81%ってことですね.mnistの公式サイトを見ると圧倒的最下位ですね.現状1位はConvolutional neural networkの99.77%ッスか.もうこの域まで来ると人よりも精度がいいらしいのでもう関係ないような気がしますがね.

5.感想とか

こうしてみるとやっぱりニューラルネットすげーってなるわけですが,もう少しニューラルネットを使わずに精度を上げられないかと思われるわけですが,ミスした画像を見ればどうすればいいかはある程度わかります.
一番左は平均画像.周りが判定ミスをした画像たちです.数字が書かれている位置が違っていたり,ある程度傾いていたりすると平均画像との相関係数だけだと限界があるわけですね.
もし更に精度を上げるには傾きや位置によらない特徴量を抽出してやる必要がありそうです.その特徴量ベクトルに対して相関係数を用いるのもよし,ユークリッド距離を用いるのもよし,別の手法でやってみるのも良しです.

ちなみにKaggleにはDigit Recognizerというのがあって,Forumとかを見れば結構わかりやすいコードだとかがありますし,自分で実装してmake a submissionで結果を送信するのも楽しいです.
でも大体みんなForumにある頭のいい人が書いたソースコードを実行して送信してるだけみたいな人が多いのでオリジナルのコードで上位に食い込むにはやっぱりディープラーニングとかを実装するしかない気がします.

6.参考

[1] MNIST handwritten digit database, Yann LeCun, CorinnaCortes and Chris Burges
[2] 酒井幸市 著,『画像処理とパターン認識入門』,森北出版株式会社
[3] 多層パーセプトロンで手書き数字認識 - 人工知能に関する断創録

2016年2月2日火曜日

振り子の動きを画像認識で検出してみる[Python]

前やった特定の色の物体の座標を検出の続きみたいなもんです.
振り子を作ってWebカメラを使って振り子の位置を検出して,グラフにしてみます.

まぁ今日のテストがイミフで,水曜日の第二外国語の勉強したくないだけですけど.

1.振り子

こんなの

文句はなしで行きましょう(笑).
暇つぶしクオリティなので重りはキャップを2つくっつけただけです.
糸も細くて変形しにくい針金などではなく,裁縫道具に入ってたやつです.

2.検出プログラム

こんな感じ.output.csvに時間,x座標,y座標が保存されます.

検出アルゴリズムとしては,HSV色空間にWebカメラの画像を変換し,緑色の成分のみをOpenCVのinRange関数を使って取り出しています.
なので以下のプログラムは「緑色の物体」の座標を認識しているので緑色のものがないところでやるようにしてください.

座標は緑色が一番たくさんあった行と列の要素番号をx,yの座標としてます.
まぁそのへんはプログラムを参照してください.
# -*- coding: utf-8 -*-
import numpy as np
import cv2
import time
cap = cv2.VideoCapture(0)
f = open("output.csv","w")
f.write("t,x,y\n")
start = time.time()
while(True):
# フレームをキャプチャする
ret, frame = cap.read()
# hsv色空間に変換
hsv = cv2.cvtColor(frame,cv2.COLOR_BGR2HSV)
# 0 <= h <= 179 (色相) OpenCVではmax=179なのでR:0(180),G:60,B:120となる
# 0 <= s <= 255 (彩度) 黒や白の値が抽出されるときはこの閾値を大きくする
# 0 <= v <= 255 (明度) これが大きいと明るく,小さいと暗い
# ここでは緑色を抽出するので60±20を閾値とした
low_color = np.array([40, 75, 75])
upper_color = np.array([80, 255, 255])
# 色を抽出する
ex_img = cv2.inRange(hsv,low_color,upper_color)
# 縦,横方向の和の中で最も大きいインデックスを抽出
x = np.argmax(np.sum(ex_img,axis=0))
y = np.argmax(np.sum(ex_img,axis=1))
# 時間と座標の保存
t = time.time() - start
f.write(str(t)+","+str(x)+","+str(y)+"\n")
print(str(t)+","+str(x)+","+str(y)+"\n")
# 抽出した座標に丸を描く
cv2.circle(frame,(x,y),10,(0,255,0))
# 画面に表示する
cv2.imshow('frame',frame)
if t > 120:
break
key = cv2.waitKey(1) & 0xFF
# qが押された場合は終了する
if key == ord('q'):
break
# 後始末
cap.release()
cv2.destroyAllWindows()
f.close()
view raw DetectGreen.py hosted with ❤ by GitHub

3.プロット

データがoutput.csvに入ったら次はmatplotlibで可視化してみます.可視化プログラムはこんな感じです.
#coding:utf-8
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
# 最初のデータはWebカメラの調子が悪いため無視
data = pd.read_csv("output.csv")
data = data[50:]
# 計算しやすいように取り出す
t = data['t']
x = data['x']
y = data['y']
# x,yは平均(振動の中心)を0に持ってこさせる
x = x - np.average(x)
y = y - np.average(y)
# 時間はt[0]が0になるようにしとく
# (pandasを使うとt[0]という表現ができないのでこうしました)
t = t - np.min(t)
# 凡例とともに表示
plt.plot(t,x,label="x")
plt.plot(t,y,label="y")
plt.legend()
plt.show()
view raw PendulumPlot.py hosted with ❤ by GitHub
グラフはこんなんが出てくる.これ横からではなく,下から撮影したのでこうなってます.

x,y座標の振り幅の極大極小はそれなりに取れてますね.振り幅が小さくなるとノイズが目立ちますが.(まぁあとカメラの傾きとか重力の方向とかどうなってんのみたいな話は置いといて……)


今日は以上です.
振り子の長さは大体37cmだったので,T=2*pi*sqrt(l/g)で,周波数はおおよそ0.8[Hz]になっているはずで,本当はここでフーリエ変換で周波数を求めようと思ったのですが……これ一定間隔でサンプリングしてないのです.

numpyやscipyのフーリエ変換の関数はたぶんサンプリング間隔が一定という条件でやってる気がする……時間のデータを与えられないし.
複素数をPythonで扱ったりとかはできず,現状実装できる能力がないので近いうちにフーリエ変換を実装しなければ…….

2016年1月30日土曜日

ラグランジュ補間でルンゲ現象を再現してみた[Python]

テスト期間中だけどラグランジュ補間のプログラムを作成した.で,試しにルンゲ現象を再現してみた.

ベッ……別に単位落とした時の言い訳なんかじゃないんだからねっ(。>﹏<。)

1.前知識

ラグランジュ補間は関数の近似を行うアルゴリズム手法の一つ.例えば値がわかっているデータが10個あったとする(例えばこんな感じ.x_data = { x0,x1,x2,...,x9}の時のy_data={y0,y1,y2,…,y9})

この時,f(x)を近似したい式として,近似式p(x)は次のように計算される.

この時,f(x)を近似したい式として,近似式p(x)は次のように計算される.
N(i,x)はxがi番目のデータに近い数字なら1を返す.もしxがi番目のサンプルデータに近ければ,i番目の時だけN(i,x)が1になるように出来てる.

こいつの利点としては雨の雨量みたいな離散的なデータを積分したいときに,そのサンプリングした奴の間のデータを出せたりする.

2.プログラム

とりあえずプログラムはこんな感じ.例としてsin関数の近似をやってみた.
#coding:utf-8
import numpy as np
import matplotlib.pyplot as plt
def approx(x,x_data,y_data):
""" x_data,y_dataを利用してy(x)の値をラグランジュ補間で予測する """
y = 0 # 予想されるf(x)の近似値
n_data = len(x_data) # サンプルデータの数
for i in range(n_data):
# indxにはi以外の0からn_data-1が代入される
indx = np.arange(n_data)[ np.arange(n_data) != i ]
# N(i,x)に当たる.np.productは全配列データの積を返す
N = np.product(x-x_data[indx])/np.product(x_data[i]-x_data[indx])
# f(x_data[i])*N(i,x)を足していく
y += y_data[i]*N
return y
# プロットデータを作成(0から2*piから6個)
x_data = np.linspace(0,2*np.pi,num=6)
y_data = np.sin(x_data)
# 試しに0から2*piまでのサイン関数を補間させてみる
x = np.linspace(0,2*np.pi,num=100)
y = np.array( [ approx(xi,x_data,y_data) for xi in x ] )
# 表示
plt.plot(x,y,label="approximation")
plt.plot(x,np.sin(x),label="sin(x)")
plt.title("Lagrange interpolation of sin(x)")
plt.legend()
plt.show()
で,結果はこんな感じ.

6個のデータしか与えてないのにだいぶいい感じに近似出来てる.すごい.まぁサンプルデータが偏ったりしているとうまくいかない.あとルンゲ現象なんてものもある.ちょっとやってみますか.

3.ルンゲ現象

Wikipediaに載ってる式を試しにやってみます.この式です.

プログラムはこいつ.
#coding:utf-8
import numpy as np
import matplotlib.pyplot as plt
def approx(x,x_data,y_data):
""" x_data,y_dataを利用してy(x)の値をラグランジュ補間で予測する """
y = 0 # 予想されるf(x)の近似値
n_data = len(x_data) # サンプルデータの数
for i in range(n_data):
# indxにはi以外の0からn_data-1が代入される
indx = np.arange(n_data)[ np.arange(n_data) != i ]
# N(i,x)に当たる.np.productは全配列データの積を返す
N = np.product(x-x_data[indx])/np.product(x_data[i]-x_data[indx])
# f(x_data[i])*N(i,x)を足していく
y += y_data[i]*N
return y
for n in [10,15,20,25]:
# プロットデータを作成(0から2*piからn個)
x_data = np.linspace(-1.0,1.0,num=n)
y_data = 1/(1+25*x_data**2)
# 補間
x = np.linspace(-1.0,1.0,num=100)
y = np.array( [ approx(xi,x_data,y_data) for xi in x ] )
# プロット
plt.plot(x,y,label="approx,n="+str(n))
plt.plot(x,1/(1+25.0*x**2),label="1/(1+25*x**2)")
plt.title("Lagrange interpolation of 1/(1+25*x**2)")
plt.ylim(-0.5,1.5)
plt.legend()
plt.show()
結果はこんな感じ.

荒ぶってますねぇ~.補間する点を多くすると過学習みたいになってまぁ変な風になってしまうというやつですね.まぁ気をつけましょうってことっすかね.

多変数関数の補間とかできるのか気になる.

2016年1月20日水曜日

MNISTの自己組織化マップ(SOM)を作った[Python]

さっき昔の記事の修正してたら操作を誤ってしまい,古い投稿がさっき投稿されたようになっててちょっとつらいです…….なのでもう少し温めてから出そうと思ってた内容をさっさと書いちゃいます.

自己組織化マップというのは,教師なしクラスタリングの一種で,似た者同士がまとまっていくものです.詳細はプログラムのコメントに書いたリンク先を参照してください.

とりあえずこういった感じの画像が得られます.(実際に使うときはこういった画像を探してくるのではなくて写像した2次元座標を使います.scikit-learnにもクラスが無く,ひょっとしたら可視化以外に使う人はもういないのかもしれません)

MNISTの手書き数字を似た者同士でまとめてる感じです.上のような画像を作るには結構演算が必要なので以下のプログラムのパラメータを幾つか変更してやる必要がありますが,基本的にはこのプログラムで出来ます(n_side=50,n_learn=5000ぐらい).これを見て,画像認識のプログラムを作る際に,どういった特徴量を作るかを考えるのに役立てることができます.

まぁ画像以外にも元素のデータ突っ込んで似た元素でまとめたりとか,動物の特徴から似た者同士をまとめたりとかという使い方もあります.よくネットに上がっている例だと色の自己組織化マップがあります.そんなに時間がかからないので出来る様子を動画にしてみました.

最初は結構変化しますが,時間が立つに連れて落ち着いてくるようすがわかります.

以下ソースコード

#coding:utf-8
import matplotlib.pyplot as plt
import numpy as np
import cv2
import random
from sklearn.datasets import fetch_mldata
from sklearn.decomposition import RandomizedPCA
"""
参考:
[1]自己組織化特徴マップ(SOM)
http://www.sist.ac.jp/~kanakubo/research/neuro/selforganizingmap.html
[2]Pythonで逐次型自己組織化マップ - 理系大学生がPythonとJavaで色々頑張るブログ
http://emoson.hateblo.jp/entry/2015/02/16/034632
[3]マインドウエア総研 | 技術情報 | SOMデータマイニング解説
http://mindware-jp.com/basic/SOM_for_datamining.html
"""
class SOM:
def __init__(self, n_side , n_learn = 1000,learning_rate = 0.5 ):
"""
n_side: output_vectorの一辺の長さ
n_learn: 学習回数
learing_rate: 学習に使う定数で,参考[1]の定数cに当たる
"""
self.n_side = n_side
self.n_learn = n_learn
self.learning_rate = learning_rate
self.n_weight = self.n_side * self.n_side
def fit(self, input_vector):
"""
学習を行うメソッド
input_vector: 変化させるベクトル
"""
input_vector = np.array(input_vector) # numpy.ndarrayにする
n_input = len(input_vector) # input_vectorの数を計算
n_vector = input_vector.shape[1] # ベクトルの次元
# points[i]にはoutput_vector[i]の要素のx座標とy座標が入っている(範囲は[0,1))
points = np.array([[i//self.n_side,i%self.n_side] for i in range(self.n_weight)])
points = points / (1.0 * self.n_side)
# 重みベクトルの初期化
self.weight = np.zeros((self.n_weight,n_vector))
# ランダムなインデックス
random_index = np.arange(n_input)
np.random.shuffle(random_index)
for t in range(self.n_learn):
print(t)
# 徐々に小さくなる数字(収束に使う)
alpha = 1.0 - float(t) / self.n_learn
# ランダムに一つ抽出
vec = input_vector[ random_index[ t % n_input ] ]
# vecとweightの差
diff = vec - self.weight
# 勝ちニューロンの要素番号を取得
winner_index = np.argmin( np.linalg.norm(diff, axis=1) )
# 勝ちニューロンのx,y座標を取得
winner_point = points[winner_index]
# 勝ちニューロンとのx,y方向の差
delta_point = points - winner_point
# 勝ちニューロンとの距離を計算
dist = np.linalg.norm(delta_point,axis = 1)
# 近傍関数。距離が近いほど大きくなる
h = self.learning_rate * alpha * np.exp( - ( dist/alpha )**2 )
# output_vectorの誤差を修正する
self.weight += np.atleast_2d(h).T * diff
if __name__ == "__main__":
# MNISTの画像の読み込み
mnist = fetch_mldata('MNIST original', data_home="..\\")
imgs = mnist.data
label = mnist.target
# 入力画像から20000件を抽出
index = np.arange(len(imgs))
np.random.shuffle(index)
input_vector = imgs[ index[:20000] ]
# SOMクラスの作成・学習
n_side = 10 # 一辺の長さ
som = SOM(n_side,n_learn=5000,learning_rate = 0.75)
som.fit(input_vector)
# 重みベクトルの取得
output_imgs = som.weight
# 順番通りに並べる
output_imgs = output_imgs.reshape(n_side,n_side,28,28)
tile = np.zeros((n_side*28, n_side*28))
for x in range(n_side):
for y in range(n_side):
tile[(x*28):(x*28+28),(y*28):(y*28+28)] = output_imgs[x,y]
# 白黒反転
tile = np.abs(255 - tile).astype(np.uint8)
# 画像の保存
cv2.imwrite("tile.png",tile)
view raw SOM_MNIST.py hosted with ❤ by GitHub

PythonでWebカメラの画像を保存する[Python]

 Pythonで画像処理の勉強をちょっとやってみたいと思い,とりあえずWebカメラから画像を取得してみた。

1.OpenCVのインストール


 OpenCVの公式サイトのダウンロードページからOSに合ったバージョンをダウンロードしてインストールする。opencvフォルダ内のbuild\python\2.7\x86\cv2.pydをPython27フォルダ内のLib\site-packagesにコピーすれば大丈夫なはず。

2.プログラム

 俺が書いたみたいに見せてるけれどOpenCVの公式ドキュメントをちょこっと変えただけでなんか申し訳ない。sを押すとphoto.jpgという名前で保存される。qを押すと終了する。

# -*- coding: utf-8 -*-
import numpy as np
import cv2

cap = cv2.VideoCapture(0)

while(True):
    # フレームをキャプチャする
    ret, frame = cap.read()

    # 画面に表示する
    cv2.imshow('frame',frame)

    # キーボード入力待ち
    key = cv2.waitKey(1) & 0xFF

    # qが押された場合は終了する
    if key == ord('q'):
        break
    # sが押された場合は保存する
    if key == ord('s'):
        path = "photo.jpg"
        cv2.imwrite(path,frame)

# キャプチャの後始末と,ウィンドウをすべて消す
cap.release()
cv2.destroyAllWindows()


 左はArduinoの箱。特に意味は無いです。右は画面を撮影したらこうなった。写し鏡みたいな。こちらも特に意味は無いです。

 ちなみにcv2.Cannyという関数を使うとエッジ検出ができます。ラズパイでは難しいかもしれないですが,普通のパソコンならリアルタイムで処理できるはずです。

# -*- coding: utf-8 -*-
import numpy as np
import cv2

cap = cv2.VideoCapture(0)

while(True):
 # フレームをキャプチャする
 ret, frame = cap.read()

 # エッジ検出
 frame = cv2.Canny(frame,100,200)

 # 画面に表示する
 cv2.imshow('frame',frame)

 # キーボード入力待ち
 key = cv2.waitKey(1) & 0xFF

 # qが押された場合は終了する
 if key == ord('q'):
  break
 # sが押された場合は保存する
 if key == ord('s'):
  path = "photo.jpg"
  cv2.imwrite(path,frame)

# When everything done, release the capture
cap.release()
cv2.destroyAllWindows()


 こちらエッジがされた画像。緑茶の二文字が見て取れる。画像処理と言っても既存の関数を使うだけで中身を知らなくてもできるという現実が嬉しいような悲しいような……。