November 14, 2011

無料でGrowlをソースからインストールする

Growl 1.3.1の通知がうるさいのでアップデートする.App Storeで$1.99で手に入れることができますが,ソースからコンパイルしてインストールしちゃう.1.3だけど.

Growl - Growl Mercurial Accessを参考に.必要な環境は以下.
  • OS X Lion - 10.7
  • Xcode
  • Mercurial

手順
  1. Growl 1.2.2のアンインストール
    アンインストーラは http://growl.info/downloads
    ちなみに古いバージョンのインストーラもおなじところに.
  2. Mercurial SCMのインストール http://mercurial.selenic.com/
  3. Google Code repositoryからソースを取得 http://code.google.com/p/growl/source/checkout
    ターミナルから
    hg clone https://code.google.com/p/growl/
    を実行すると,growlってディレクトリができてローカルコピーされます.止まってんじゃないかくらい時間かかった.
  4. growlディレクトリからGrowl.xcodeprojを開く
  5. ビルドターゲットをGrowl.appに
  6. ビルドしようとするとエラーが起こるかも

    hgRevision.hがないとかそれっぽいこととか言われても無視.

    サインエラーに関してはGrowlのページには
    A signing error. You will need to generate a self signed certificate, and can do so at Keychain Access.app -> application's name menu -> certificate assistant -> create a certificate. Be sure to use the same prefix as the certificate that you are receiving errors about.
    ってあるけどめんどくさいので Code Signing Identity を Don't Code Sign に.2箇所ある.
  7. ビルド(⌘B)
  8. Growl.appを右クリックしてShow in FinderするとGrowl.appが見つかるのでアプリケーションフォルダに移動して実行.終わり.

November 10, 2011

Google Scholarの検索結果に+1ボタンを追加するChrome Extension


Google Scholarの検索結果にはGoogle +1ボタンがついていないのでボタンを追加するChrome拡張機能をつくった.はじめは自分用に文献をソーシャルブックマークするシステムをApp Engineでつくろうかと思ったけどめんどくさいし,gdd11jpで+1ボタンの簡単だよって聞いたので.


インストール
Chrome Web Store - +1 to Google Scholar


構成
  • manifest.json
  • content_script.js
  • jquery.js (http://jquery.com/からダウンロードしてリネーム)

- manifest.json

- content_script.js


参考にしたページ

備考
  • +1ボタンの読み込み遅いせいか知らんけど結果の表示が遅くてイライラする…たぶんこいつのせいでGoogle Readerももたついてんじゃないの…
  • だからデフォルトで検索結果に+1ボタンつけてほしいです
  • しかし拡張機能のアイコンとかタイルとかGoogleのもの勝手に使ってるの怒られるのかな

August 23, 2011

PythonでA*アルゴリズムを実装してみる

PythonでNexworkXを使ってA*アルゴリズムを実装してみます。まあNetworkXではA*アルゴリズムは実装されているのですが。

NetworkXは複雑ネットワークでいろいろやるためのPythonのパッケージ。easy_installでインストールするのが楽。

A*(A-star, エースター) アルゴリズムは、経路探索アルゴリズムの一つ。Wikipediaの解説がわかりやすい。(→Wikipedia ja, Wikipedia en)

ここではWikipediaにある疑似コードをほぼそのままの形で実装してみます。ランダムな重みつきエッジで構成される3x3のグリッドにおいて(0,0)から(2,2)への最短ルートを探索します。

以下ではヒューリスティック関数h*(n)として直線距離を使います。
が、上の設定では直線距離は
\forall n,0\leq h^*(n) \leq h(n)
を満たさないので、最短経路であることは保証されません…。

なので、一応、ヒューリスティック関数h*(n)による推定値を常に0とすることで、ダイクストラ法による最短距離を求めてみます。(A*アルゴリズムの意味なし。)

August 16, 2011

SIMロック解除とケータイ補償お届けサービスあるいは外装交換

SIMロック解除をドコモに頼んでやってもらうと、ケータイ補償お届けサービス(1回目5,250円、2回目8,400円)あるいは外装交換(5,250円?)を利用して新しい携帯電話にしてもSIMロック解除をされた状態にして受け取ることができる、と言う事をDSの店員さんに確認してGalaxy S2のSIMロック解除をしました(3,150円)。設定画面等からSIMロック解除されているかどうか確認することはできない、らしい…

docomoでは「GALAXY S II SC-02C」、SAMSUNGでは「GALAXY S2(SC-02C)」という表記。どっちでもいいのか。

(追記) 無事海外(タイ、中国、マカオ)でも使えました。

June 22, 2011

Pythonで拡張カルマンフィルタを実装してみる

拡張カルマンフィルタ(EKF; Extended Kalman Filter)は非線形カルマンフィルタのひとつ。線形カルマンフィルタは線形システムを対象としていましたが、拡張カルマンフィルタは非線形システムを対象とします。ナビゲーションやらGPSやらに利用されている、らしい。

システムが非線形のとき、すなわち
{\bf x}_{t+1}=f({\bf x}_{t},{\bf u}_{t})+{\bf w}_{t+1} (状態方程式)
{\bf y}_{t}=h({\bf x}_{t})+{\bf v}_{t} (観測方程式)
{\bf w}_{t}\sim N(0,{\bf Q}){\bf v}_{t}\sim N(0,{\bf R}) (ノイズは正規分布)
p({\bf x}_{t}|{\bf y}_{0:t})=N({\bf x}_{t};{\bf \mu}_{t},{\bf \Sigma}_{t}) (状態は正規分布)
とするとき、関数 f は前の状態から推定値を与え、関数 h は観測値を与えますが、どちらの関数も直接共分散を求めることはできません。が、拡張カルマンフィルタでは状態方程式も観測方程式も微分可能であれば線形である必要はありません。

拡張カルマンフィルタでは状態方程式と観測方程式の線形化をするために、線形カルマンフィルタにおける時間遷移モデルと観測モデルに各関数の偏微分行列(ヤコビアン)を用います。
{\bf A}_{t} = \left\ \frac{\partial f({\bf x}_{t},{\bf u}_{t})}{\partial {\bf x}_{t}} \right|_{{\bf \mu}_t, {\bf u}_t}
{\bf C}_{t} = \left\ \frac{\partial h({\bf x}_{t})}{\partial {\bf x}_{t}} \right|_{{\bf \mu}_t}
あとは、線形カルマンフィルタと同じ。 μt, Σt, ut, yt+1 を入力として、 μt+1, Σt+1を出力します。1ステップのプロセスは以下のとおり。

# prediction
{\bf \hat{\mu}}_{t+1} \leftarrow f({\bf \mu}_{t},{\bf u}) (現在の推定値)
{\bf A}_{t} \leftarrow \left\ \frac{\partial f({\bf x}_{t},{\bf u}_{t})}{\partial {\bf x}_{t}} \right|_{{\bf \mu}_t, {\bf u}_t} (状態方程式の現在のヤコビアン)
{\bf \hat{\Sigma}}_{t+1} \leftarrow {\bf Q}+{\bf A}_t{\Sigma}_t {\bf A}_t^T (現在の誤差行列)
# update
{\bf C}_{t+1} \leftarrow \left\ \frac{\partial h({\bf x}_{t})}{\partial {\bf x}_{t}} \right|_{{\bf \hat{\mu}}_{t+1}} (観測方程式のヤコビアン)
{\bf \tilde{y}}_{t+1} \leftarrow {\bf y}_{t+1}-{\bf C}_{t+1}{\hat{\mu}}_{t+1} (観測残差)
{\bf S}_{t+1} \leftarrow {\bf C}_{t+1}{\bf \hat{\Sigma}}_{t+1}{\bf C}_{t+1}^T+{\bf R} (観測残差の共分散)
{\bf K}_{t+1} \leftarrow {\bf \hat{\Sigma}}_{t+1}{\bf C}^T{\bf S}^{-1} (最適カルマンゲイン)
{\bf \mu}_{t+1} \leftarrow {\bf \hat{\mu}}_{t+1}+{\bf K}_{t+1}{\bf \tilde{y}}_{t+1} (更新された現在の推定値)
{\bf \Sigma}_{t+1} \leftarrow {\bf \hat{\Sigma}}_{t+1}-{\bf K}_{t+1}{\bf C}_{t+1}{\bf \hat{\Sigma}}_{t+1} (更新された現在の誤差行列)


例題。
2次元座標において、あるロボットがt=0に原点を出発して、速度(2,2)で動くとする。ロボットの進路は風などの影響を受け(σx=σy=1)、毎秒ごと3つの点(0,0),(10,0),(0,10)からの距離を計測できて、計測には距離によらない誤差がある(σx=σy=2)とする。このとき、観測された軌跡から実際の軌跡を推定する。
Fig.1 ロボットの位置は(x0,x1)で、3点からの観測値(y0,y1,y2)を得る。

状態方程式は線形、観測方程式は非線形となります。
f({\bf x},{\bf u})=\left[\begin{a}{cc}1&0\\0&1\end{}\right]{\bf x}+\left[\begin{a}{cc}1&0\\0&1\end{}\right]{\bf u},\ \ \ {\bf u}=\left[\begin{a}{c}2\\2\end{}\right]
h({\bf x})=\left[\begin{array}{c} \sqrt{x_0^2+x_1^2}\\ \sqrt{(x_0-10)^2+x_1^2}\\ \sqrt{x_0^2+(x_1-10)^2} \end{array}\right]

観測方程式のヤコビアンは
J=\left[\begin{array}{cc} \fr{\pa{h}_0}{\pa{x_0}}&\fr{\pa{h}_0}{\pa{x_1}} \\ \fr{\pa{h}_1}{\pa{x_0}}&\fr{\pa{h}_1}{\pa{x_1}} \\ \fr{\pa{h}_2}{\pa{x_0}}&\fr{\pa{h}_2}{\pa{x_1}} \\ \end{array}\right]
として求められます。実装では上式を解析的に解く場合、数値的に解く場合を試してみます。なおSciPyには数値的にヤコビアンを求める関数が用意されているので、ここではそれを使ってみます。(微小区間ズラして傾き求めている…)

以下、実装。61行目と62行目で解析的か数値的か切り替えます。



割とうまくいっている実行結果。

Fig. 2 赤が実際の軌跡。青が推定値。
左が解析的なヤコビアン、右が数値的なヤコビアンを使った結果。

なんかうまくいってないような(?)結果も出てしまいます。

Fig. 3 なんか微妙…

UKFも実装してみようかな。

http://docs.scipy.org/doc/scipy/reference/optimize.html
http://old.nabble.com/calculating-numerical-jacobian-td20506078.html
http://projects.scipy.org/scipy/browser/trunk/scipy/optimize/slsqp.py
http://en.wikipedia.org/wiki/Broyden's_method