AndroidアプリでSMS受信を偽装する方法
今日のGoogle Developer Day 2010のセッションで、IMoNiの作者@t_eggさんが、「IMoNiはSMSのContentProviderにデータを突っ込むことで、iモード.netメールの受信通知をSMSとして(実際に受信している訳ではなく、仮想的に)受信させている」ということを説明されていました。
これについて、興味があったので自分でも実装してみました。
また、ContentProviderに突っ込む以外でも、SMSの受信サービスを直接呼び出すことでSMSを仮想的に受信させる方法を見つけたので、それについても記しておきます。
SMSのContentProviderに突っ込む方法
「SMSのContentProviderに突っ込む」と一言でいっても、SMSのContentProviderはSDKのandroid.jarには存在しないので、詳細はOSのソースを追っていく必要があります。
URIとかカラム名の詳細は、
android.provider.Telephony
クラスを参照します。
これによると、insertすべきSMS受信BOXのContent URIは "content://sms/inbox" で、"address","date","read","subject","body"あたりのカラムにデータを突っ込めば良さそうということが分かります。
ContentValues values = new ContentValues(); values.put("address", "090xxxxxxxx"); values.put("date", System.currentTimeMillis()); values.put("read", false); values.put("subject", "test subject"); values.put("body", "test body"); getContentResolver().insert(Uri.parse("content://sms/inbox"), values);
この書き込みをするためにはAndroidManifest.xmlに以下のパーミッション設定が必要です。
<uses-permission android:name="android.permission.WRITE_SMS" /> <uses-permission android:name="android.permission.READ_SMS" />
このソースを実機で実行してみると、以下のような感じでちゃんと受信できていることが分かります。
受信元は数字じゃなくてもちゃんと表示されてますね。
もう一つの方法 - 直接SMS受信用のServiceを呼ぶ
さて上記のContentProviderに突っ込む方法でSMSの一覧に表示させることはできるのですが、一つ問題があって、ステータスバーへの通知が表示されません。
もちろん、自力で別途Notificationを発行すれば出ますが、出来ればこの辺の処理も本来行うべきクラスに行わせたいところです。
そこでもう一つの方法ですが、SMSの受信サービスに直接Intentを発行する、ということが出来ます。
呼び出す対象は「メッセージ」アプリのサービスクラスである、
com.android.mms.transaction.SmsReceiverService
クラスです。
このSmsReceiverServiceに発行するIntentには、SMS受信を表すActionである「android.provider.Telephony.SMS_RECEIVED」を指定します。
さらに、ここで肝となるのは、受信したSMSを表すバイト列を、"pdus"というキー名のextraにセットしてあげる必要がある点です。僕が調べた限り、このデータを一発で組み立ててくれるような便利なメソッドとかは存在しないので、SMSのフォーマットを調べた上で、自力でバイト列を作成してあげる必要があります。
以下のコードは、SMS and the PDU formatなどを参考にして、SMSのPDUバイト列を組み立てて受信サービスに渡してあげるサンプルソースです。
処理中で、GsmAlphabetというクラスを使ってますが、これはAndroid OSのcom.android.internal.telephonyパッケージに存在する内部ユーテリティクラスです。同パッケージ中のEncodeExceptionクラスと一緒に自分のプロジェクトにコピーしてやればそのまま使えるはずです。
public void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); sendSms(this, "09000000000", "これはてすとだよ!"); } private static void sendSms(Context context, String sender, String body) { byte[] pdu = null; byte[] scBytes = PhoneNumberUtils .networkPortionToCalledPartyBCD("0000000000"); byte[] senderBytes = PhoneNumberUtils .networkPortionToCalledPartyBCD(sender); int lsmcs = scBytes.length; byte[] dateBytes = new byte[7]; Calendar calendar = new GregorianCalendar(); dateBytes[0] = reverseByte((byte) (calendar.get(Calendar.YEAR))); dateBytes[1] = reverseByte((byte) (calendar.get(Calendar.MONTH) + 1)); dateBytes[2] = reverseByte((byte) (calendar.get(Calendar.DAY_OF_MONTH))); dateBytes[3] = reverseByte((byte) (calendar.get(Calendar.HOUR_OF_DAY))); dateBytes[4] = reverseByte((byte) (calendar.get(Calendar.MINUTE))); dateBytes[5] = reverseByte((byte) (calendar.get(Calendar.SECOND))); dateBytes[6] = reverseByte((byte) ((calendar.get(Calendar.ZONE_OFFSET) + calendar .get(Calendar.DST_OFFSET)) / (60 * 1000 * 15))); try { ByteArrayOutputStream bo = new ByteArrayOutputStream(); bo.write(lsmcs); bo.write(scBytes); bo.write(0x04); bo.write((byte) sender.length()); bo.write(senderBytes); bo.write(0x00); try { // ascii文字のみの場合こっち byte[] bodyBytes = GsmAlphabet.stringToGsm7BitPacked(body); bo.write(0x00); bo.write(dateBytes); bo.write(bodyBytes); } catch (EncodeException e) { // 2バイト文字を含む場合こっち System.out.println("try UCS2"); try { byte[] textPart = body.getBytes("utf-16be"); bo.write(0x0b); bo.write(dateBytes); bo.write(textPart.length); bo.write(textPart); } catch (UnsupportedEncodingException e1) { } } pdu = bo.toByteArray(); } catch (IOException e) { } Intent intent = new Intent(); intent.setClassName("com.android.mms", "com.android.mms.transaction.SmsReceiverService"); intent.setAction("android.provider.Telephony.SMS_RECEIVED"); intent.putExtra("pdus", new Object[] { pdu }); context.startService(intent); } private static byte reverseByte(byte b) { return (byte) ((b & 0xF0) >> 4 | (b & 0x0F) << 4); }
このソースは単にサービスを呼び出しているだけなので、Permissionの設定は特に必要ありません。
こいつを実機で実行してみると、以下のようにちゃんと受信通知まで表示してくれます。
まるで本当にSMSを受信してるようです。
ただ、当然ながらメッセージアプリがアンインストールされちゃったりしている場合は、Serviceが反応しないのでこの方法は使えません。(レアケースだとは思いますが)
まとめ
- SMSのContentProviderにデータを直接突っ込んでSMS受信を偽装する方法
- SMSの受信サービスを直接呼び出してSMS受信を偽装する方法
を紹介しました。
これを使えば、アプリからの様々な通知をSMSで置き換えることができるので、うまく使えばユーザービリティを高められると思います!
Live Wallpaperで動画ファイルをそのまま表示する(とりあえずできたよ編)
Android OS 2.1からLive Wallpaper(ライブ壁紙)の機能が追加されていますが、いざLive Wallpaperを自分で作る、となると結構面倒です。
実装方法の詳細は、「Android 2.1の新機能「Live Wallpaper」で作る、美しく燃える“待ち受け”」に詳しいですが、WallpaperService.Engineの各種メソッドをオーバーライドして、SurfaceHolderを経由してCanvasに描画処理を行うことで、アニメーションを実現するのが常套手段のようです。
ですがこの方法はかなり面倒です。単にアニメーションを再生したいだけなのに、Javaでゴリゴリプログラムを書きたくない。
そもそも、mp4とかの動画ファイルが素材としてあるんだったらそれをそのまま表示できないのでしょうか?
というわけで色々試してみます。
MediaPlayerクラスで再生している動画はSurfaceHolderに対して表示できるので、まずはその方法で試してみます。
MediaPlayerにSurfaceHolderをそのままsetDiaplayしてやる
public class LiveWallpaperTest extends WallpaperService { ~~ class LiveEngineTest extends Engine { private MediaPlayer mp; @Override public void onCreate(SurfaceHolder holder) { super.onCreate(holder); holder.setType(SurfaceHolder.SURFACE_TYPE_PUSH_BUFFERS); mp = new MediaPlayer(); mp.setDisplay(holder); mp.setOnPreparedListener(new OnPreparedListener() { @Override public void onPrepared(MediaPlayer mp) { mp.start(); } }); try { mp.setDataSource(LiveWallpaperTest.this, Uri.parse("content://media/external/video/media/1")); } catch (Exception e) { Log.e(TAG, "error"); } mp.setOnCompletionListener(new OnCompletionListener() { @Override public void onCompletion(MediaPlayer mp) { mp.stop(); } }); } // MediaPlayerをpreparaeする部分は省略 } ~~ }
ダメでした。logcatには以下のようなエラーが出力されます。
E/AndroidRuntime( 754): java.lang.UnsupportedOperationException: Wallpapers do not support keep screen on E/AndroidRuntime( 754): at android.service.wallpaper.WallpaperService$Engine$2.setKeepScreenOn(WallpaperService.java:202) E/AndroidRuntime( 754): at android.media.MediaPlayer.updateSurfaceScreenOn(MediaPlayer.java:895) E/AndroidRuntime( 754): at android.media.MediaPlayer.setDisplay(MediaPlayer.java:573)
ということで、MediaPlayer.setDisplayの中で自動的に、SurfaceHolder.setKeepScreenOnが呼ばれますが、WallpaperのSurfaceHolderはこのメソッドをサポートしていないのです。
ここで一工夫します。Wallpaper用のSurfaceHolderをそのまま使っていると上記の例外が避けられないので、独自のSurfaceHolderのWrapperを自分でこしらえます。
独自のSurfaceHolder WapperをMediaPlayerにsetDiaplayしてやる
class MySurfaceHolder implements SurfaceHolder { private SurfaceHolder surfaceHolder; public MySurfaceHolder(SurfaceHolder surfaceHolder) { this.surfaceHolder = surfaceHolder; } @Override public void addCallback(Callback callback) { surfaceHolder.addCallback(callback); } @Override public Surface getSurface() { return surfaceHolder.getSurface(); } @Override public Rect getSurfaceFrame() { return surfaceHolder.getSurfaceFrame(); } @Override public boolean isCreating() { return surfaceHolder.isCreating(); } @Override public Canvas lockCanvas() { return surfaceHolder.lockCanvas(); } @Override public Canvas lockCanvas(Rect dirty) { return surfaceHolder.lockCanvas(dirty); } @Override public void removeCallback(Callback callback) { surfaceHolder.removeCallback(callback); } @Override public void setFixedSize(int width, int height) { surfaceHolder.setFixedSize(width, height); } @Override public void setFormat(int format) { surfaceHolder.setFormat(format); } @Override public void setKeepScreenOn(boolean screenOn) { return; } @Override public void setSizeFromLayout() { surfaceHolder.setSizeFromLayout(); } @Override public void setType(int type) { surfaceHolder.setType(type); } @Override public void unlockCanvasAndPost(Canvas canvas) { surfaceHolder.unlockCanvasAndPost(canvas); } }
見ての通り、setKeepScreenOnメソッドの実装を空にしている以外は、全てもとのSurfaceHolderに丸投げするだけです。
こいつを使ってもう一度動画を再生してみましょう。
public class LiveWallpaperTest extends WallpaperService { ~~ class LiveEngineTest extends Engine { private MediaPlayer mp; @Override public void onCreate(SurfaceHolder holder) { super.onCreate(holder); holder.setType(SurfaceHolder.SURFACE_TYPE_PUSH_BUFFERS); mp = new MediaPlayer(); mp.setDisplay(new MySurfaceHolder(holder)); mp.setOnPreparedListener(new OnPreparedListener() { @Override public void onPrepared(MediaPlayer mp) { mp.start(); } }); try { mp.setDataSource(LiveWallpaperTest.this, Uri.parse("content://media/external/video/media/1")); } catch (Exception e) { Log.e(TAG, "error"); } mp.setOnCompletionListener(new OnCompletionListener() { @Override public void onCompletion(MediaPlayer mp) { mp.stop(); } }); } @Override public void onDestroy() { super.onDestroy(); if (mp != null) { mp.stop(); mp.release(); } } @Override public void onVisibilityChanged(boolean visible) { super.onVisibilityChanged(visible); if (visible) { play(); } } private void play() { if (mp.isPlaying()) { mp.stop(); } try { mp.prepareAsync(); } catch (IllegalArgumentException e) { Log.e(TAG, "error"); } catch (SecurityException e) { Log.e(TAG, "error"); } catch (IllegalStateException e) { Log.e(TAG, "error"); } } } ~~ }
さてどうでしょうか?
見事、Live Wallpaperとして動画が表示されています!
まとめ
- Live wallpaperのSurfaceHolderにMediaPlayerで再生した動画を表示しようとするとエラーでこける。
- SurfaceHolderをそのまま使うんじゃなくて、独自のWrapperを用意すればMediaPlayerで再生した動画をそのままライブ壁紙に使える。
という話でした。
単に動画を表示するだけのライブ壁紙はつまらないですが、面白いアプリを作る一手段としてなら使えるんじゃないでしょうか。(電池をどれくらい食うか心配ですが。。)
Androidの開発効率化Tips
2010/09/06追記:id:gaeさんよりXMLのファイル名はキャメルケースにできない、という指摘を頂きました。XMLのファイル名は未検証のまま書いてしまっていたのでそれに関する記述を削除させて頂きました。
Androidの開発にもだいぶ慣れてきて、スムーズに開発できるようになってはいるのですが、冷静に自分の実装プロセスを分析するとまだまだ非効率だなあと感じる点が多々あったりします。効率化のためにADTを改造するかな、とも思ったのですが、それ以前に既存のEclipse+ADTの機能を活用して効率化できる部分がまだあるのではないかと考えて調査してみました。
その中で、これは使えそうかな、というEclipse+ADTでのAndroid開発効率化の小技をいくつか紹介します。
GotoFileプラグイン
Androidで開発をしているとファイルを行ったり来たりすることが非常に多くなります。LayoutファイルとJavaソースの行ききだったり、似たような処理をしているところをコピって持ってきたり、、、。そこで使えるのが、Eclipse上で素早くファイル検索できるGotoFileプラグインです。オリジナルの配布サイトからはダウンロード出来なくなっているようですが、id:kusakariさんが表示数制限版を公開されています。
このプラグインをインストールすると、Ctrl-Alt-Nで検索窓が出てきます。Eclipse標準機能のCtrl-Shift-Tでも似たようなことができますが、GotoFileプラグインが特徴的なのは曖昧検索ができることです。
たとえば、hello_world.xmlのファイルに移動したければ「hxml」でヒットします。仮にファイルの一部分しか覚えていなくてもかなりスムーズにファイル間を移動することができます。
Extract Android String
Androidの開発で、もう一つ面倒なのがstrings.xmlファイルの存在です。
他言語化するために、基本的に文言は全てstring.xmlに抽出しますが、文言が出てくるたびにstrings.xmlを開いて編集、とやっていると非常に効率が悪いです。
あまり知られていないですが、ADTにはこれを解消するための便利な機能が用意されています。
Javaファイル、もしくはリソースXMLファイルで文言部分を選択した状態で、「Refactor->Android->Extract Android String」のメニューを選ぶと、指定された文字列をstrings.xmlに抜き出すことが出来ます。Alt-Shift-A, Sのショートカットで呼び出すとさらに便利です。
僕はこの機能で1日で1度もstrings.xmlを開かなくても開発できるようになりました。
キャメルケースを活用する
これはAndroid開発に限らないですが、Eclipseの補完機能をフル活用するために、キャメルケースで補完するのが良いです。
たとえばOnItemLongClickListenerだったらOILCと打ってCtrl-Shiftすれば、候補表示を飛ばして一発で補完できます。OnItemと打って、次に候補から選んで・・・とするよりもキーストロークを大幅に減らすことができます。
これはR.javaの各フィールドについても言えることで、R.strings.XXXXなどのXXXX部分を補完する際にも使えるので、stringsのキー名やandroid:id、layoutやdrawableのファイル名は、全てキャメルケースにしておくことをお勧めします。特にstringsのキー名とかは数が多くなってくると、必然的に長くなってくると思うので・・・
僕はいままでアンダースコアで区切っていたのですが、補完時に不便なのでキャメルケースに切り替えました。
まとめ
Eclpse+ADTにもまだまだ知らない便利機能が多いので、みんなでTipsを共有するといいと思うな!(おい
iPhone・iPad用に手書き文字認識ライブラリZinniaをビルドする
iPhone・iPad向けに手書き文字認識ライブラリ-Zinniaをビルドしてみて、結構苦労したので、そのときのメモです。Zinniaと書いてますが、Fat binary全般についての僕の理解も込みで説明してます。以下iPhoneと書いてますが、iPad用でも同様の内容があてはまります。
Fat binaryについて
まず基本的な話で、iPhone実機、Mac OSが稼働するPC、そしてiPhoneシミュレータの三者は、動作するプログラムのアーキテクチャが違う、ということを頭に置いておく必要があります。iPhoneのCPUはarm、Mac OSが稼働するCPUは(OS10.6では)x86_64、そしてiPhoneシミュレータはi386のCPUをシミュレートするようになっています。Mac OS上で普通にコンパイルするとx86_64向けのバイナリが出来てしまうので、これはiPhone実機やシミュレータでは動かないわけです。
作成されたバイナリがどのアーキテクチャ向けにビルドされているかは、otoolコマンドなどで参照することが出来て、たとえば普通にconfigureしてmakeしたZinniaのバイナリは以下のようになっています。
$ otool -vh .libs/libzinnia.a Archive : .libs/libzinnia.a .libs/libzinnia.a(param.o): Mach header magic cputype cpusubtype caps filetype ncmds sizeofcmds flags MH_MAGIC_64 X86_64 ALL 0x00 OBJECT 3 1136 SUBSECTIONS_VIA_SYMBOLS ...
こんな感じでこのライブラリにリンクされているバイナリがx86_64をターゲットにコンパイルされていることが分かります。
で、こいつをiPhoneで動かしたい、となるとシミュレータのことも考慮してarmとi386の両方で動くようにビルドしてあげる必要があるわけです。こんな風に複数CPUで動くように作られたバイナリをFat binaryとかUniversal binaryとか呼んだりします。
さて、Mac OS上でFat binaryを作るにはここに書いてあるようにいくつか方法がありますが、一番シンプルなのが、それぞれのアーキテクチャ向けに個々にコンパイルしたものを、lipoコマンドで結合してあげるやり方です。
基本的にはg++に-arch [アーキテクチャ名]のオプションが渡るようにしてあげれば、そのアーキテクチャ向けにコンパイルしてくれるはずなのですが、これがなかなか一筋縄ではいきません
armバイナリのビルド
armでビルドするときは、arm向けのライブラリやヘッダファイルなどが、Mac OSのデフォルトパス上のものとは異なるので、それらのライブラリパスやインクルードパスも全部指定し直す必要があります。arm用のファイルは、iOS SDKをインストールしたフォルダ /Developer/Platforms/iPhoneOS.platform/Developer に格納されているので、configure時にこれらを参照するように〜FLAGSなどの環境変数を設定してあげます。
export CPPFLAGS="-I$SDKROOT/usr/lib/gcc/arm-apple-darwin10/4.2.1/include/ -I$SDKROOT/usr/include/ -I$SDKROOT/usr/include/c++/4.2.1 -I$SDKROOT/usr/include/c++/4. 2.1/armv6-apple-darwin10/ -miphoneos-version-min=3.0" export CFLAGS="$CPPFLAGS -pipe -no-cpp-precomp -isysroot $SDKROOT" export CPP="$DEVROOT/usr/bin/cpp $CPPFLAGS" export CXXFLAGS="$CFLAGS" # Dynamic library location generated by the Unix package LIBPATH=$LIBFILE.dylib LIBNAME=`basename $LIBPATH` export LDFLAGS="-L$SDKROOT/usr/lib -L$SDKROOT/usr/lib/gcc/arm-apple-darwin10/4.2.1/ -Wl,-dylib_install_name,@executable_path/$LIBNAME" ./configure CXX=$DEVROOT/usr/bin/arm-apple-darwin10-g++-4.2.1 CC=$DEVROOT/usr/bin/arm-apple-darwin10-gcc-4.2.1 LD=$DEVROOT/usr/bin/ld --host=arm-apple-darwin make
これでarm用のバイナリが作られるはずです。
i386バイナリのビルド
Mac OSのライブラリ類はi386互換で作られているはずなので、armのようにインクルードパスやライブラリパスをいちいち指定し直さなくても、g++に-arch i386オプションを指定してあげれば、i386用のバイナリが作られます。
ただ一つ問題なのがZinniaのMakefileです。./configure時にCFLAGS="-arch i386"と指定してもMakefileが作られるときには、なぜかこの指定が消えてしまっているのです。恐らくはZinniaがビルドに使用しているlibtoolの問題ではないかと思うのですが(推測です)、仕方がないので無理矢理Makefileを書き換えてあげます。
./configure perl -pi -e 's@^CXXFLAGS = @CXXFLAGS = -arch i386 @g' Makefile perl -pi -e 's@^CFLAGS = @CFLAGS = -arch i386 @g' Makefile make
これでi386のバイナリもビルドできました。
まとめ
以上をまとめたZinniaのFat binaryビルドファイルです。
Mac OS 10.6.4、iOS SDK 4.0.2、Zinnia 0.0.6で動作確認しています。
build_fat.sh
#!/bin/sh LIBFILE=.libs/libzinnia export DEVROOT=/Developer/Platforms/iPhoneOS.platform/Developer export SDKROOT=$DEVROOT/SDKs/iPhoneOS4.0.sdk # build arm binary export CPPFLAGS="-I$SDKROOT/usr/lib/gcc/arm-apple-darwin10/4.2.1/include/ -I$SDKROOT/usr/include/ -I$SDKROOT/usr/include/c++/4.2.1 -I$SDKROOT/usr/include/c++/4.2.1/armv6-apple-darwin10/ -miphoneos-version-min=3.0" export CFLAGS="$CPPFLAGS -pipe -no-cpp-precomp -isysroot $SDKROOT" export CPP="$DEVROOT/usr/bin/cpp $CPPFLAGS" export CXXFLAGS="$CFLAGS" LIBPATH=$LIBFILE.dylib LIBNAME=`basename $LIBPATH` export LDFLAGS="-L$SDKROOT/usr/lib -L$SDKROOT/usr/lib/gcc/arm-apple-darwin10/4.2.1/ -Wl,-dylib_install_name,@executable_path/$LIBNAME" LIBPATH_static=$LIBFILE.a LIBNAME_static=`basename $LIBPATH_static` ./configure CXX=$DEVROOT/usr/bin/arm-apple-darwin10-g++-4.2.1 CC=$DEVROOT/usr/bin/arm-apple-darwin10-gcc-4.2.1 LD=$DEVROOT/usr/bin/ld --host=arm-apple-darwin make mkdir -p lnsout cp $LIBPATH_static lnsout/$LIBNAME_static.arm make distclean unset CPPFLAGS CFLAGS CPP LDFLAGS CXXFLAGS DEVROOT SDKROOT # build i386 binary ./configure perl -pi -e 's@^CXXFLAGS = @CXXFLAGS = -arch i386 @g' Makefile perl -pi -e 's@^CFLAGS = @CFLAGS = -arch i386 @g' Makefile make cp $LIBPATH_static lnsout/$LIBNAME_static.i386 /usr/bin/lipo -arch arm lnsout/$LIBNAME_static.arm -arch i386 lnsout/$LIBNAME_static.i386 -create -output lnsout/$LIBNAME_static unset CPPFLAGS CFLAGS CPP LDFLAGS CPP CXXFLAGS DEVROOT SDKROOT
結果
fileコマンドで本当にfat binaryができているか確認してみます。
$ file lnsout/libzinnia.a lnsout/libzinnia.a: Mach-O universal binary with 2 architectures lnsout/libzinnia.a (for architecture arm): current ar archive random library lnsout/libzinnia.a (for architecture i386): current ar archive random library
IS01専用Androidアプリ「LEDモールス」を公開しました
ものすごく久しぶりのブログになってしまいましたが生きてます。
最近は社内でスマートフォン関連の開発をやってまして、どっぷりとAndroidに浸かっています。
機種依存やら何やらに悩まされたり、Android開発の奥深さに毎度唸らされる毎日です。
で、今日はシャープとアンドロイダーが開催した「SHARP Androidアプリ開発 テクニカルセッション」というセミナーにいってきました。これはメーカーの開発者の方がいる中で、皆PC持参でひたすら実機を触るという素晴らしいイベント(※講演もありました)だったのですが、このセミナー中に1個お遊びのアプリを作ってみたので公開します。
LEDフラッシュでモールス信号を発信できるアプリです。
LEDの制御はIS01専用(というかシャープ専用)の拡張APIなので、いまのところIS01しか動きませんが、船舶間での通信、難破・遭難時の救難信号、符号理論の勉強などに是非ご活用ください!
というわけで僕はAndroid端末を持っていないので本当に公開できているか分からないのですが、「LEDモールス」という名前でマーケット公開中です。ダウンロードは(多分)↓こちらから。
【LEDモールス】(IS01専用アプリ)
http://market.android.com/search?q=org.firemobilesimulator.morse
適当なソースコードなのでさらしておきます。
package org.firemobilesimulator.morse; import java.util.Hashtable; import jp.co.sharp.android.hardware.FlashLight; import android.app.Activity; import android.os.Bundle; import android.text.Editable; import android.util.Log; import android.view.View; import android.widget.EditText; import android.widget.Toast; public class TopActivity extends Activity { private static final String TAG = "Morse"; private static final int INTERVAL = 1000; private static final int LONG = 1000; private static final int SHORT = 200; private EditText mEditText; private static Hashtable<String, String> mTable; static { mTable = new Hashtable<String, String>(); mTable.put("A", "・−"); mTable.put("B", "−・・・"); mTable.put("C", "−・−・"); mTable.put("D", "−・・"); mTable.put("E", "・"); mTable.put("F", "・・−・"); mTable.put("G", "−−・"); mTable.put("H", "・・・・"); mTable.put("I", "・・"); mTable.put("J", "・−−−"); mTable.put("K", "−・−"); mTable.put("L", "・−・・"); mTable.put("M", "−−"); mTable.put("N", "−・"); mTable.put("O", "−−−"); mTable.put("P", "・−−・"); mTable.put("Q", "−−・−"); mTable.put("R", "・−・"); mTable.put("S", "・・・"); mTable.put("T", "−"); mTable.put("U", "・・−"); mTable.put("V", "・・・−"); mTable.put("W", "・−−"); mTable.put("X", "−・・−"); mTable.put("Y", "−・−−"); mTable.put("Z", "−−・・"); mTable.put("1", "・−−−−"); mTable.put("2", "・・−−−"); mTable.put("3", "・・・−−"); mTable.put("4", "・・・・−"); mTable.put("5", "・・・・・"); mTable.put("6", "−・・・・"); mTable.put("7", "−−・・・"); mTable.put("8", "−−−・・"); mTable.put("9", "−−−−・"); mTable.put("0", "−−−−−"); } @Override public void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.main); mEditText = (EditText) findViewById(R.id.input); } public void morse(View view) { Editable edit = mEditText.getText(); String s = edit.toString(); FlashLight mFlashLight = new FlashLight(); // 通常の点灯時は、ライトの色のみ指定します int len = s.length(); for (int i = 0; i < len; i++) { String oneChar = s.substring(i, i + 1).toUpperCase(); Log.d(TAG, "morse:" + oneChar); String code = mTable.get(oneChar); if (code != null) { int codeLen = code.length(); for (int j = 0; j < codeLen; j++) { char c = code.charAt(j); int time = 0; switch (c) { case '−': time = LONG; break; case '・': time = SHORT; break; } mFlashLight.setFlashLightOn(FlashLight.LIGHT_COLOR_WHITE); try { Thread.sleep(time); mFlashLight.setFlashLightOff(); Thread.sleep(INTERVAL); } catch (InterruptedException e) { Log.e(TAG, "sleep error", e); } } } else { Log.w(TAG, "Unknown Character"); } } Toast.makeText(this, "モールス信号を発信しました", Toast.LENGTH_LONG); } }
Blenderでドミノ崩し
前回に引き続き、今度はblenderでモデルを組み立ててみます。blender上ではpythonのマクロが使えるので、手作業が大変でも、自動化で簡単に複雑なモデルを組み立てることができます。
ってなわけでblender上でドミノを配列させるスクリプトを組んでみました。
from Blender import * import math scene = Scene.GetCurrent() defRBFlags = Object.RBFlags.COLLISION | Object.RBFlags.PROP | \ Object.RBFlags.BOUNDS | Object.RBFlags.RIGIDBODY | \ Object.RBFlags.ACTOR | Object.RBFlags.DYNAMIC for n in range(18): # n周目の作成 r = 10 + 1.8 * n j = int(math.pi * r * 0.7) d = 2 * math.pi / j for i in range(j): # i個目の作成 x = r * math.cos(d*i) y = r * math.sin(d*i) objname = 'dominoobj_' + str(n) + '_' + str(i) mdat = Mesh.Primitives.Cube(1.0) mdat.name = objname m = scene.objects.new(mdat,objname) m.SizeX = 0.5 m.SizeY = 2 m.SizeZ = 3 m.LocX = x m.LocY = y m.LocZ = 1.5 s = 360*d*i/(2*math.pi) m.RotZ = d*i # 物理エンジンの計算対象にするための設定 m.rbFlags = defRBFlags m.rbMass = 0.5 m.rbShapeBoundType = Object.RBShapes.BOX Redraw()
やっていることはいたってシンプルで、半径の異なる同心円上にブロックオブジェクトを配置していっているだけです。また、rbXXXのプロパティを設定しているのは、物理エンジンの計算対象とするための設定です。
このスクリプトを実行した後は、床となるプレートオブジェクトと、ブロックを倒すためのボールオブジェクトをblender上で作ってあげます。そうすると以下のようなアニメーションが出来あがります。
うーん、面白い!
フォード・ファルカーソンのアルゴリムで最大流-最小切断問題を解く
PRMLの8.3節では、マルコフ確率場を応用した事例として画像のノイズ除去がでてきますが、PRMLで紹介されている「グラフカットアルゴリズム」を試すには最大流問題を解く必要があるのでアルゴリズムの勉強もかねて実装してみました。
最大フロー問題または最大流問題とは、各枝に容量(capacity)と流量(flow)が設定された有効グラフにおいて、ある始点(ソース)から終点(シンク)へのフローで最大となるフローを求める問題です。
この問題を解くアルゴリズムとしてフォード・ファルカーソンのアルゴリズムが一般的に良く知られていて、僕の持っているアルゴリズムC・新版—基礎・データ構造・整列・探索にも載っています。
アルゴリズムCから引用すると、フォード・ファルカーソンのアルゴリズムは「辺の流量がすべてゼロである状態から開始し、ソースからシンクに向かう道で、飽和した前向きの辺や流量ゼロの後ろ向きの辺を含まないものに沿って流量を増やし、ネットワークにそのような道がなくなるまで繰り返す」というように要約できます。「後ろ向きの辺」が何かというと、元の向きと逆向きの辺を考えて、その辺を流れるときは逆に流量を減らすというものです。この逆向きの辺を考えないと、最初に変な道の選び方をしてしまうと、もう最大フローにはたどり着かなくなってしまいます。
また、フォード・ファルカーソンのアルゴリズム自体は「ソースからシンクに向かう道で、飽和した前向きの辺や流量ゼロの後ろ向きの辺を含まないもの」を探すアルゴリズム自体を規定しているわけではないので、このアルゴリズムは自分で探索アルゴリズムを組む必要があります。アルゴリズムCでは最良優先探索を使用しています。
以下では、アルゴリズムCにならって最良優先検索で最大流および最小切断を求めてみます。
対象となる最大流問題は、アルゴリズムCの図33.2のネットワークを対象としています。
(図がダウンロードできなかったので、貼付けられず。。ご容赦。。)
#include <iostream> #include <vector> #include <math.h> using namespace std; namespace GraphCut { //NodeとEdgeで相互参照するため、あらかじめ宣言しておく。 class Node; class Edge { public: Node* s_Node_; Node* e_Node_; Edge (Node* s_Node, Node* e_Node, double size); double AddFlow (double flow); void set_reverse_edge (Edge* re); double get_flow (); void set_flow (double flow); double get_size (); private: Edge* reverse_edge_; double flow_; double size_; }; class Node { public: vector<Edge*> vecFlowPath; Node* dad_; string name_; Node (string name); void AddFlowPath (Node* e_node, double size); double get_val (); void set_val (double val); void visit (); bool get_is_visited (); Edge* dad_path_; void reset (); private: double val_; bool is_visited_; }; Edge::Edge (Node* s_Node, Node* e_Node, double size) : s_Node_(s_Node), e_Node_(e_Node), size_(size), flow_(0) {} double Edge::AddFlow (double flow) { flow_ += flow; reverse_edge_->set_flow(-flow); return flow; } double Edge::get_flow () { return flow_; } void Edge::set_flow (double flow) { flow_ = flow; } void Edge::set_reverse_edge (Edge* re) { reverse_edge_ = re; } double Edge::get_size () { return size_; } Node::Node (string name) : name_(name), val_(0), is_visited_(false) {} void Node::AddFlowPath (Node* e_node, double size) { Edge* e = new Edge(this, e_node, size); vecFlowPath.push_back(e); Edge* re = new Edge (e_node, this, -size); re->set_reverse_edge(e); e->set_reverse_edge(re); e_node->vecFlowPath.push_back(re); } double Node::get_val () { return val_; } void Node::set_val (double val) { val_ = val; } void Node::visit () { is_visited_ = true; } bool Node::get_is_visited () { return is_visited_; } void Node::reset () { is_visited_ = false; val_ = 0; } } using namespace GraphCut; //ノードnを含む最小切断を再帰的に求めてmincutに追加する void SearchMinCut (Node* n, vector<Node*>& mincut) { mincut.push_back(n); n->visit(); vector<Edge*> vecAdjEdges = n->vecFlowPath; for (int j=0; j<vecAdjEdges.size(); j++) { Edge* adjEdge = vecAdjEdges[j]; Node* adjNode = adjEdge->e_Node_; if (adjNode->get_is_visited()) continue; //飽和した前向きの辺や、流量ゼロの後ろ向きの辺ではない場合 if ((adjEdge->get_size() > 0 && adjEdge->get_flow() != adjEdge->get_size()) || (adjEdge->get_size() < 0 && adjEdge->get_flow() != 0)) { SearchMinCut(adjNode, mincut); } } } //全ノードvecNodesを順位優先で検索して、流量の増加の最も多い経路を見つける。 bool PFS (vector<Node*> vecNodes, Node* source, Node* sink) { printf("start priority-first search\n"); //初期化 for (int j=0; j<vecNodes.size(); j++) { Node* n = vecNodes[j]; n->reset(); } source->set_val(INT_MAX); Node* v = source; bool findSource2Sink = false; bool findMax = true; while (findMax) { findMax = false; v->visit(); double val = v->get_val(); //新たに訪問済になったノードvの隣接ノードのpriority(流量)の更新 vector<Edge*> vecAdjEdges = v->vecFlowPath; for (int j=0; j<vecAdjEdges.size(); j++) { Edge* adjEdge = vecAdjEdges[j]; Node* adjNode = adjEdge->e_Node_; if (adjNode->get_is_visited()) continue; //priorityの更新 //vを経由した場合の、adjNodeへの流量を求める double priority = -(adjEdge->get_flow()); double size = adjEdge->get_size(); if (size > 0) priority += size; if (priority > val) priority = val; //新たに求めたadjNodeへの流量が、既に設定された流量を上回る場合、adjNodeへの経路と流量を更新する if (adjNode->get_val() < priority) { adjNode->set_val(priority); adjNode->dad_ = v; adjNode->dad_path_ = adjEdge; } } //流量最大のノードを求める double maxval = 0; int max = -1; int nodeNum = vecNodes.size(); for (int j=0; j<nodeNum; j++) { Node* n = vecNodes[j]; if (n->get_is_visited()) continue; if (n->get_val() > maxval) { maxval = n->get_val(); max = j; } } //流量最大のノードが見つかった場合 if (max >= 0) { findMax = true; v = vecNodes[max]; if (v == sink) { //ソースからシンクまでの経路が見つかった場合 findSource2Sink = true; break; } } } return findSource2Sink; } int main (int argc, char * const argv[]) { //ノードと辺の初期化 vector<Node*> vecNodes; Node* a = new Node("a"); Node* b = new Node("b"); Node* c = new Node("c"); Node* d = new Node("d"); Node* e = new Node("e"); Node* f = new Node("f"); vecNodes.push_back(a); vecNodes.push_back(b); vecNodes.push_back(c); vecNodes.push_back(d); vecNodes.push_back(e); vecNodes.push_back(f); a->AddFlowPath(b,6); a->AddFlowPath(c,8); b->AddFlowPath(d,6); b->AddFlowPath(e,3); c->AddFlowPath(d,3); c->AddFlowPath(e,3); d->AddFlowPath(f,8); e->AddFlowPath(f,6); Node* source = a; Node* sink = f; //ソースからシンクまでの経路が尽きるまで、流量最大経路の探索を繰り返す while (PFS(vecNodes, source, sink)) { //ソースからシンクまでの流量が増加する経路が発見された場合、シンクから逆に発見された経路をたどり、流量を増加させる。 Node* n = sink; while (n != source) { Edge* e = n->dad_path_; e->AddFlow(sink->get_val()); printf("add flow to %s-%s by %f\n", e->s_Node_->name_.c_str(), e->e_Node_->name_.c_str(), sink->get_val()); n = n->dad_; } } //最小切断を求めるために全ノードを初期化 for (int j=0; j<vecNodes.size(); j++) { Node* n = vecNodes[j]; n->reset(); } //再帰的に最小切断を求める vector<Node*> mincut; SearchMinCut(source, mincut); cout << "display mincut" << endl; for (int j=0; j<mincut.size(); j++) { Node* n = mincut[j]; printf("%s\n", n->name_.c_str()); } return 0; }
実行結果
start priority-first search add flow to d-f by 6.000000 add flow to b-d by 6.000000 add flow to a-b by 6.000000 start priority-first search add flow to e-f by 3.000000 add flow to c-e by 3.000000 add flow to a-c by 3.000000 start priority-first search add flow to e-f by 3.000000 add flow to b-e by 3.000000 add flow to d-b by 3.000000 add flow to c-d by 3.000000 add flow to a-c by 3.000000 start priority-first search display mincut a c
というわけで、最小切断がa,cだということが分かりました。
PFS内で、流量最大のノードを探索している箇所をヒープソートにしたりすれば多分もっと早くなります。
ちなみにですが、石川先生のグラフカットのサーベイ論文によれば、最大流問題を解くアルゴリズムとして、フォード・ファルカーソンのアルゴリズム以外にpush-relabelアルゴリズム(PDF)が知られていて、フォード・ファルカーソンが計算量O(n^3)に対し、push-relabelはO(nmlog(n^2/m))(nは頂点の数、mは辺の数)で、push-relabelの方が速いそうです。
ですが、次回はとりあえずこのままフォード・ファルカーソンのアルゴリズムで、グラフカットによるエネルギー最小化問題を解いてみることにします。