2014年4月 9日 (水)

USB 3.0 のUSBメモリ

SEITECという、少なくとも私は聞いたことのないメーカー(ブランド)の、C102という、なんだかやる気が感じられない名前・型番のUSBメモリをあきばおーで購入。128GBで6534円(消費税8%込み)ということで、安かったので。

この容量で最安値ではなかったが、最安値の品が「50MB/s」と主張しているのに対してこちらは「UP TO 210MB/s」と書いてあり、差が数百円だったのでこっちにしてみた。

だったら、ベンチマークしなきゃだめでしょ、ということで。

そしたら、こんな感じだった。(画像クリックで拡大。)

Usb3

うむ。これはしっかり速いんじゃないかな。シーケンシャルアクセスに限れば、秋葉原に出回りだした最初のころのSSDよりはずっと速い。512KB単位のランダムアクセスで、リードとライトの差が大きすぎるような気もするが、これはバッファ(キャッシュ)が小さいとか、そういうことなのかなぁ。

2013年11月17日 (日)

SAT Solverでナンプレを解くのにかかる時間

昨日、「ナンプレを解くのにかかる時間」についての質問をいただいた。質問者の意図を正確に把握できているかどうかわからないが、私はこの問いを「大抵の問題が2~3秒で解けるのはわかったが、とても難しい問題のときに、最大どれくらいの時間がかかるのか」という問いかけだと受け取った。

そこで昨日は、以下のようなことを答えとしてお話した。

  • 実は、よくわからない。
  • それなりにいろいろな問題を試しているつもりだが、どの問題も3秒程度で解けている。早く解ける問題はたまにあるが、特に長い時間がかかる問題は経験していない。だから、たぶん、全ての問題が3秒以内で解けるのではないかという気がしている。
  • 人間がパズルとしてナンプレで解くときの問題の難しさと、それをSATに変換してSAT Solverが解くときの難しさは、同じではないようだ。開発の初期のころに、(あまり多くない問題を)SAT4Jで解くのにかかる時間を測定しながら評価していたのだが、ナンプレ本が示す問題の難易度と、SAT Solverで消費した時間とが、逆転する(つまり、難易度が高い問題の方が短い時間で解ける)ことがあった。
  • どういうときにSAT Solverで解くのに時間がかかるのか、私にはよくわかっていないので、最悪でどれくらい時間がかかるのかも、私にはわからない。ひょっとすると、SAT Solverに向かないナンプレの問題というものがあって、それを「ナンプレ破り」で解こうとすると、いつまで待っても解き終わらずに固まってしまう(ANR)ことがあるかもしれない。そう思うと怖い。

この件について昨夜帰宅途中でいろいろと考えたのだが、まず、SAT Solverで解きにくいSAT問題について調べるべきだと思い、ぐぐってみたところ、こんな記事を発見した。

http://d.hatena.ne.jp/hzkr/20090209

この記事自体は、「ランダム生成したSATの問題が解を持つ確率」について検討し、「式(項)の個数 / 変数の個数」という値が4.27の辺りだけ、解を持つかどうかが予測できなくなる、という事実を紹介しているのだが、最後の方にこんなことも書いてある。

4.27付近は(中略)SATを解くアルゴリズムにとってとても難しいゾーンということになります。(中略)ヒューリスティックを駆使して効率的にSATを解くアルゴリズムは、式長/変数数比がこのゾーンの外ならとても効率的にSATを解けるらしいです。この4.27ゾーンだけが鬼門。

4.27ゾーンというのは、具体的には 3.5 ~ 5 くらいの範囲らしい。

ほほう、と思って、ナンプレの問題からできるSATの問題について、この比を計算してみると、11745 ÷ 729 ≒ 16.1 。めっちゃ大きい! どうも、ナンプレを変換したSATの問題というのは、大抵、SAT Solverで効率的に解くことができるものになるみたいです。

2013年11月16日 (土)

プレゼン資料掲載しました

本日無事に、日本Androidの会横浜支部の第18回定例会で、「OpenCVとSAT4Jを使ってナンプレに挑戦してみた」と題してしゃべることができました。

参加者の皆さんから、いろいろと参考になるフィードバックもいただきました。ありがとうございました。

使ったプレゼン資料をSlideShareに載せましたので、興味のあるかたはご覧ください。

http://www.slideshare.net/AlissaSabre/opencvsat4j

2013年11月15日 (金)

メモリ管理の話の続き

先日の記事の最後の部分に書いた、Java VM がネイティブヒープも管理するという話の続き。

Javaからネイティブコードを呼び出すときにはjniという仕組みを使う。

jniでは、呼ばれる側(ネイティブコード側)が、Javaからjniで呼ばれるということを全力で意識したコーディングが必要になる。ただそれは入り口だけで、内部の処理は普通のC++(または、C++から呼べる任意の言語)のライブラリとしてコーディングすればいい。メモリ管理の仕組みも普通のC++と全く同じだ。

Sun (Oracle) のJVM用にjni用ネイティブコードを開発するときには、コンパイラとかCライブラリとかは、特にJavaを意識していない、普通のCコンパイラ、普通のCライブラリを使う。だから、メモリ管理の実装(例えばmallocの内部処理)は、JVMとは無関係なものになる。

でも、Androidの場合は、Android用のC/C++開発環境というのは、AndroidのJVM (Dalvik) から呼び出されるjniネイティブコードを作る専用の環境だ(よね?)だから、そこで提供するCライブラリは、APIは普通のCライブラリと互換でも、内部の処理が普通のCライブラリと同じである必要はないと思うのだ。例えば、malloc() という関数が、内部で Dalvik のAPI を呼んだりしても一向に構わない。

そういう仕組みにすれば、ネイティブコードが使うネイティブヒープの利用状況を、Dalvik が正確に把握することができて、ネイティブコードが malloc() を呼んだときにネイティブヒープが不足していたら malloc() がすぐにNULLを返さずに Dalvik が GC する、なんてことも可能だろうと思ったのだ。

本当にそうなっているのかどうか、Dalvik も NDKのCライブラリも、たぶんソースが公開されているんだろうから、自分で調べればわかると思うのだが、調べていない。単に妄想しているだけなのだけれども。

あと、.NET の CLR はやっている、と書いたのは、上に書いたような malloc がGCを起動する、というものとは別の仕組みだが、memory pressure のことを意識していた。

JVMに比べると、.NET の GC は、非常にたくさんの(それなりにヤヤコシくて使うのが難しい)APIを公開しているのだが、その中に memory pressure という機能がある。これは、ネイティブヒープの利用状況を、GC に教える仕組みだ。

.NET ではネイティブコードの呼び出しは P/Invoke という仕掛けで行う。これは、jniと違い、呼ばれる側(ネイティブコード側)は.NET からの呼び出しであることを一切意識せず、逆に呼び出す側(マネジドコード側)がネイティブコードの呼び出しを意識することになっている。このため普通は、jniではネイティブ側に書くいわゆるグルーコードは、P/Invoke では .NET 側で書く。

このとき、P/Invoke でネイティブコードを呼び出す直前とか戻った直後とかに、ネイティブ側で割り当てたメモリの量をGCに教えるのだ。新たに割り当てたときには AddMemoryPressure、解放したときには RemoveMemoryPressure というメソッドを呼ぶことになっている。両メッソドが適切に呼ばれていれば、CLRはネイティブメモリ利用状況を把握することができて、適当な上限値を越えるとGCを動かす、ような処理を行う、らしい。(実は、この辺り、正確な記述をみつけていないのだが。断片的な情報を組み合わせると、こんなところだと思う。)

この手法は、さきほど妄想した「ネイティブコードはmallocを呼ぶだけでOK」に比べると、余計な手間がかかるし、正確性にも劣るが、それでも、Sun JVMの「ネイティブヒープの使用量には一切関知しません。以上。」みたいなスタンスよりは大分いい。

2013年11月11日 (月)

約411年前のある日

「約411年前のある日」っていう表現はおかしいと思う。「411年」と正確にわかっているのだから「約」じゃないはず。「約400年前」なら妥当だが。

2013年11月10日 (日)

LTやります

日本Androidの会 横浜支部の定例会で、LTやらせていただくことになりました。

11月16日(土)の午後、会場はJR横浜駅から徒歩7分だそうです。

http://atnd.org/events/44595

タイトルはまだ確定できていませんが、今作っているプレゼンの最初のページには「OpenCVとSAT4Jを使ってナンプレに挑戦してみた」と書いてあります。先日Google Playで配り始めた「ナンプレ破り」の中身の話です。

面白いかどうかは、… なんとも言えませんが、あ、でも他の方の話もありますから。bleah

2013年10月31日 (木)

OpenCV Java APIをWindowsやLinuxで使うときのメモリ管理の注意

OpenCVのJava APIは、もともとAndroidでOpenCVを使うために開発されたもののようだが、WindowsやLinux(たぶんMacOSも)の普通のJava実行環境でも使える。OpenCV 2.4.4(?) 以降では、Windows用にOpenCVを普通にインストールすると、Java APIもインストールされる。

拙作「ナンプレ破り」は、内部でいろいろな画像処理をするのだが、そのパラメタを決めるために、たくさんの画像を処理して結果を評価するようなことをやっている。それは開発中にWindows上でプログラムを動かしているのだが、Android用の処理を評価するのが目的なので、WindowsでもOpenCVを使うJavaプログラムとして作ってある。

これで、少々ハマったので、何にどうハマったのか、どう解決したのか、書いておく。

OpenCVをJavaから使うときには、画像データはもっぱらMatクラスということになり、他の選択肢はない。JavaオブジェクトとしてのMatオブジェクトというのは、単なるネイティブオブジェクト(C++のcv::Matクラスのインスタンス)のラッパーで、メンバー変数はnativeObjというネイティブオブジェクトのアドレスを指すlong型の変数が一個あるだけ。

まぁ、それは、そんなものだろう。

問題は、nativeObjという変数が指すネイティブオブジェクト(が占有しているメモリ)を開放するメソッドが存在しない点だ。それじゃぁ、どんどんリークしちゃうのか、というと、もちろんそうではない。JavaのMatクラスにはfinalize()メソッドが実装されていて、そこで開放するようになっている。つまり、GCが走って、使わなくなったJavaのMatオブジェクトが開放されるときに、ネイティブオブジェクトも開放されるようになっている。逆に言うと、Matのネイティブオブジェクトは、アプリが必要としなくなっても、次回のGCまでは開放されずメモリを占有し続けることになる。

と、書くと、OpenCV Java APIを使ったことがある人は「Mat.release()というメソッドがあるじゃない。あれじゃだめなの?」って思うだろう。

だめなのだ。Mat.release() というのは、「JavaのMatオブジェクトが指すネイティブオブジェクト」を解放するのではなくて、「JavaのMatオブジェクトが指すネイティブオブジェクトであるC++のMatオブジェクトの、さらにその先にあるバルクメモリ」を解放するメソッドなのだ。

図にすると、こんな感じ。(クリックすると拡大。) Mat_2 ※ ここで「バルクメモリ」と呼んでいるものは、C++の意味でのクラスのインスタンスではない、malloc()で割り当てる単なるメモリです。実際の画像データが、ここに入ります。

Mat.release()を呼び出すと、右端のバルクメモリは解放されるが、C++のMatオブジェクト、OpenCVのJavaDocがしばしば「Mat header」と呼ぶモノは解放されない。まぁ、意図はわかる。Java側のMatを、完全なC++側Matのプロキシーにしたかったんだろう。それに、このC++のMatは、バルクメモリと比べると小さい。バルクメモリが画像データを格納するために、すぐにMBオーダーになっちゃうのと比べると、Matオブジェクトは一個100バイト弱だ。ネイティブヒープに放置しても、大した影響はないと考えたのかもしれない。とは言え、JavaのMatオブジェクトがヒープ上で占有するメモリ(たぶん16バイト?)と比べると大きい。

その結果、ある程度大きな画像データを保持した(つまり、ネイティブヒープの残りがそれなりに少なくなっている)状態で、JavaのMatオブジェクトを作っては捨て作っては捨て、ということを大量に繰り返すと、Javaのオブジェクトヒープよりも先にネイティブヒープが不足して、それ以上Matオブジェクトが割り当てられない、という状態になってしまう、らしいのだ。

GCが走れば、すでに未使用になっている古いJavaのMatオブジェクトが大量に回収されて、そのときに一緒にネイティブヒープも解放されるのだが、JavaのGCというのはJavaオブジェクトヒープが不足しない限り走らないので、いつまでもネイティブメモリが解放されずに、メモリ不足を起こしてしまう。

私がハマったのは、そういう状態だったらしい。

OpenCVのJava APIでは、メモリが不足すると、CvExceptionという例外を投げるようになっている。だから、この例外をキャッチして、System.gc()を呼んだ上で再度メモリの割り当てをすればいいはずだ。ただ、この例外は、Java側でオブジェクトをnewしたときに限らず、様々なOpenCVのAPIが内部で一時的に使うメモリを確保できなかったときなどにも発生するので、OpenCVのほとんど全てのAPIで発生する可能性がある。(CvExceptionはRuntimeExceptionになっている。この仕様を考えると当然だが。)だからと言って、全てのAPIの呼び出しをtry-catchで囲むわけにもいかないし、処理途中の半端なところでキャッチしても、途中だった処理の再実行ができない。

いくつか試した結果、私の解は、こんな感じに落ち着きましたよ。

    try {
        doSomething(file);
    } catch (CvException e) {
        System.gc();
        doSomething(file);
    }

doSomething(File)というメソッドで画像をファイルから読んで処理するようにしておき、CvExceptionが発生したらGCしてもう一回(ファイルの読み込みから)やり直すわけです。それでもまた例外が発生するとそのまま抜けちゃいますが、これはGC直後に処理してもまだメモリが不足するのはバグの可能性が高い(本当にメモリリークしているとか)ので、意図的にそうしています。

実際のプログラム全体は、上のコードの外側でfileを変えながらループ(ファイル100個くらい)するのですが、さらにその外側で画像処理のパラメタを変えるループがあって20~30通りくらいのパラメタを試すようになっており、doSomethingは都合2000~3000回くらい呼ばれます。そのため、ループの中で直接上のコードを実行するのではなく、ExecutorServiceを使って並列実行するようにしてあります。

ひょっとしたら、OpenCVのJava APIを使う人には常識かとも思ったのですが、解決前後にそれなりにウェブを検索しても、この件に言及している記事をみつけられなかったので。

ところで、普通Androidでは、こんなに大量の画像をまとめて処理するなんていうことはしないのですが、もしもやったらどうなるかと思って試してみたところ、一度もCvExceptionが発生せずに処理が終わります。処理の部分で消費するネイティブヒープとJavaオブジェクトヒープの比率が変わるようにコードを書き換えていろいろ試したのですが、(自動的な)GCの頻度が変わりはするものの、ネイティブヒープが不足して例外を投げるという状況にはなりませんでした。

不思議です。

ひょっとしたら、Androidのdalvikは、jniの先でネイティブコードが割り当てるネイティブヒープの使用量も見て、Javaオブジェクトヒープだけでなく、ネイティブヒープが不足したときにも自動GCが走るようになっているのでしょうか。考えてみると、.NETのCLRは、そういう仕組み(jniじゃなくてP/Invokeですけれども)を備えているわけで、Androidであれば、やればできるだろうとは思うわけですが。

というわけで、Androidのネイティブヒープ管理の仕組みについてもウェブを探してみましたが、そうなってるとも、なってないとも、この種の話題に言及した記事をみつけることができませんでした。今後の課題です。

2013年10月26日 (土)

「ナンプレ破り」Google Playで公開中

先日の記事の最後に「次のバージョンは、いよいよベータ版ということにして、Google Play Appストアに置けるようにしたい」と書きましたが、無事、バージョン0.8がGoogle Playからダウンロードできるようになりました。

ダウンロードのページは、
https://play.google.com/store/apps/details?id=com.gmail.at.sabre.alissa.numberplace
です。

Google Playに載せるにあたって、画面のデザインを若干変更したり、日本語対応を行ったりしています。自分では、多少見映えが良くなったと思っています。

他の改良点として、0.7ではOpenCV Managerをインストールしないと全く動作しなかったのですが、今回のバージョンでは、OpenCV Managerがなくても、パズルの撮影(画像認識)以外の機能は動作するようになっています。つまり、バージョン0.6のように、問題を手入力して解かせることができます。とは言え、問題の手入力の機能は相変わらず貧弱なので、OpenCVインストールすることをお勧めしたいです。

前回の記事にも少し書きましたし、バージョン0.7を実際に試した方はお気づきと思いますが、実は問題の読み込み機能には難があり、照明の加減などが悪いと読み間違いが多発します。その辺りの改良も試みていたのですが、公開に間に合いませんでした。次回のバージョンまでには、なんとかしたいと思っています。

前回同様、ソースはGithubにあります。今回のリリースには、r.0.80というタグがつけてあります。

お楽しみください。

2013年10月17日 (木)

AndroidのOpenCVの色空間が破綻していることに気づいた

ずっと気づいていなかった。

OpenCVでは、ピクセル当たりの色要素数だけを意識して色空間は意識しない。色空間はアプリが管理することになっている。例えば、OpenCVtが画像データを扱うデータ形式の一つMatは、色要素数は管理するが、色空間は管理しない。ただ、一部、OpenCVが特定の色空間を意識する場合もある。ここまでは、一応わかっていた。

imreadとimwriteは、OpenCVが色空間を意識する特別な場合の一つだ、ということもわかっていた。

でも、imreadとimwriteが意識する色空間が具体的にはBGRまたはBGRAだ、ということは、さっきまでわかっていなかった。

と、ここまではOpenCVそのものの話。

Android用のOpenCVでは、android独自機能として、bitmapToMatとmatToBitmapという関数があり、Androidのビットマップデータオブジェクト(android.graphics.Bitmap)と、OpenCVのイメージデータ形式Matとの間で形式を変換してくれるのだが、この関数はMatの色空間がRGBAであることを前提にしている。このことも一応わかっていた。

その結果、bitmapToMat/matToBitmapと、imread/imwriteとを、一つのアプリ中で組み合わせて使うと、色空間がわけわからなくなって破綻する、ということに、さっき気づいた。

いや、まぁ、そういうものだということを意識して、どの変数はどの色空間なのかきちんと覚えておいて書き分けるとか、アプリが使う色空間を一種類に統一しておいて、違う場合はいちいち変換するとか、そうやってアプリを書けば問題ないわけだが、「カラー」「グレースケール」「二値」くらいの意識でコーディングしちゃうと、「カラー」の画像がどういう色空間なのか、わけがわからなくなる、というわけだ。

最近作っているナンプレのアプリが、そういう状況で破綻してしまっていることに、さっき気づいたのでした。ははは。なんでこういう仕様なんだか。なんて言ってもしょうがないので、今から直します。

2013年10月15日 (火)

ナンプレ破りバージョン0.7

前回の記事で紹介したナンプレ(数独)を解くAndroidアプリですが、欠けていた「ナンプレの問題を読み込む機能」が動くようになりましたので配布します。

「問題を読み込む」というのは、ナンプレの問題を記録したデータファイルを読むとか、そういうことではなくて、ナンプレ本とかナンプレ雑誌とかに掲載されている問題をケータイのカメラで撮影すると読み込む、という機能です。QRコードを読み取るようなものだと思っていただければいいと思います。

バージョン0.7と称していますが、仕上がりとしては「アルファ版」くらいです。

※ 余談ですが、アプリの日本語名は「ナンプレ破り」にしました。道場破り、のイメージで。coldsweats01

アプリ本体は、前回はSkydriveに置いたところスマホで直接ダウンロードできなくて不便でした。そこで今回は(@niftyがファイルサイズを制限した以降)、あまり使っていなかったココログのファイルダウンロードに置いてみました。これは何の工夫もないhttpダウンロードなので、問題なくスマホで直接ダンロードできます。

ダウンロードのURLは、
http://alissa-sabre.cocolog-nifty.com/files/number-place-breaker-070.apk
です。

このバージョンから、内部で画像認識の処理をするようになったため、OpenCVというライブラリを利用します。このライブラリは、ナンプレ破りのapkに組み込まれていないため、別途 Google Play Appストアから「OpenCV Manager」というアプリをダウンロードしてインストールする必要があります(無料です)。ナンプレ破りの初回起動時に、Google Playを起動してダウンロードするように求められますので、それに沿ってインストールしてください。

前回も書いたとおり、ソースはGithubで公開しています。今回配布するバイナリに相当するものに、r.0.70というタグを付けてあります。Android SDKをお持ちの方はお試しください。

※ 実は、Androidアプリのソースをgitに載せるやりかたが、よくわかってなくて、これでいいのかどうか自信がないのです。何か問題があれば、ぜひご指導くださいませ。

以下、アプリの使い方です。(例によって、画像をクリックすると拡大します。)

初めて起動すると、こんな画面になります。
Device20131015002856

このダイアログは、OpenCV Managerをインストールしますか? と聞いているので、必ず「Yes」を選んでください。すると、Google Playが起動します。
Device20131015002913
同じロゴマークがたくさん並ぶ、まるで怪しいウエブサイトのような画面ですが(crying)、アプリの説明などを良く読んだ上、ご自分でインストールするかどうか決めてください。(なお、OpenCV Managerをインストールしないと、ナンプレ破りは動作しません。)

「インストール」を選ぶと、いつもの通りに権限の確認を求められたあとで、
Device20131015002927

普通にダウンロードが始まるので、
Device20131015002943

インストールが完了するまで待ってください。
Device20131015002957
完了すると、「開く」ボタンが現れますが、開く必要はありません。開いても、何も面白いことは起きません。そこで、スマホの「戻る」ボタンを使って、ナンプレ破りに戻ります。(「ホーム」に戻って、再度ナンプレ破りを起動しても構いません。)

すると、こんな画面になります。(この画面は、前回と同じです。)
Device20131015003026

右上にある(縦長画面だと左下に移動します)Captureボタンを押すと、カメラが動作するので、解きたいナンプレの問題を写して、
Device20131015003254

画面にタッチしてナンプレの問題を撮影します。(ボタンもアイコンも何も表示されませんが、画面全体がシャッターの働きをします。)すると、画像が取り込まれ、輪が回転して画像を認識します。(数秒かかります。)
Device20131015003324

認識できました。
Device20131015003433

前回同様、「Solve」を選ぶと、しばらく考えて、(数秒かかります)
Device20131015003540

答を表示します。Device20131015003547

これだけです。

なお、問題の読み込みは、100%確実ではありません。光の具合や紙の曲がりなどによって、全く読めないこともありますし、読めても一部間違うこともあります。うまく読めなかったときには、もう一度読み込むか、間違いが少なければマス目をタッチして修正することもできます。「Solve」をタッチして答が表示された後に問題の間違いに気づいたら、問題を修正して再度「Solve」をタッチすれば解き直します。

あと、初回起動時のOpenCV Managerのインストールを求めるダイアログなのですが、機種やAndroidのバージョンによって、「Yes」と「No」のボタンが逆になることがあります。
Device20131015001317
「右」とか「左」ではなくて、画面を良く読んで、「Yes」と書いてある方を選んでください。

次のバージョンは、いよいよベータ版ということにして、Google Play Appストアに置けるようにしたいと思っています。

«ナンプレ(数独)を解くAndroidアプリ