openCV と python で SLAMする

さて、夏休みも終わりですね。
世間の皆様方は旅行行ったり海に行ったりとリア充ライフを満喫されたでしょうか?

私はこれといって特別なことはせずに、ネットみたり本読んだりとフツーの日々を過ごしていました。
夏は冷房の効いた部屋で過ごすに限りますからね。

といってもただ怠惰に過ごしていたわけでもなくブログのネタを仕込んだり、資格試験の勉強したりと それなりに有意義に過ごせたと思います。

で、本題ですが、タイトルにもある通りSLAMをやりたいと思います。

SLAMとはもちろん不良たちがバスケをやって成長していく有名マンガではなく、Simultenious Localizetion And Mapping の略称です。

SLAMについてもう少し付け加えると、これは自動運転車やお掃除ロボットが自分の位置を把握するために用いる技術で、
センサ値から自己位置推定と周囲の地図作成を平行して行うというものです。
大抵はセンサとしてレーザーレンジファインダを用いるのですが、カメラを使ったものもあり、Visual-SLAMと呼ばれます。 (Visual Odometryとも)

今回はこのVisual-SLAM(以下VSLAM)を実装していこうと思います。

今回実装するVSLAMについて

今回はwebカメラを用いた単眼VSLAMを実装しようと思います。
フローとしてはだいたい以下のような形になると思われます。

  1. カメラのキャリブレーションを行い、キャリブレーション行列を求めておく
  2. 画像を撮る(このときの視点を視点1とする)
  3. 移動して視点を変える
  4. 画像を撮る(このときの視点を視点2とする)
  5. 2,4で撮影した画像間で共通する特徴点を抽出する
  6. (a) 特徴点の対応から視点1から視点2への移動を計算する(回転行列、平行移動ベクトルを求める)
    (b) 特徴点の三次元座標を計算する
  7. 特徴点の三次元座標、視点1,2の画像,画像上での特徴点座標,各視点でのカメラ姿勢、位置を記録する
  8. バンドル調整を行う
  9. 2へ戻る

各処理について簡単に説明すると

1のキャリブレーションはレンズの歪みを補正するための処理です。単眼でなく複眼のVSLAMを行う場合はカメラごとに行う必要があると考えられます。

2~4では撮影と移動を行っています。

5では特徴点を検出しています。ロバスト性を強めたいので今回はSURF特徴量を用います。検出にはopenCVのモジュールを用います。

6で視点間の相対位置と三次元座標の計算を行っています。視点の移動をもとに三次元構造を把握するこの手法はSfM(Structure from Motion)と呼ばれます。

7ではマップの構築と記録を行っています。本当ならステップ5のあとで検出した特徴点をDBに問い合わせ、既出のものか判断する必要があります。

8ではバンドル調整なる処理を行います。位置推定と地図作製をそのまま繰り返すと誤差が蓄積するため、それを除去する処理です

さて、大枠としては上記のようになります(なると思います)。 次回以降キャリブレーションについてサンプルプログラムと一緒に見ていきたいと思います。

参考図書

  • 実践コンピュータビジョン

実践 コンピュータビジョン

実践 コンピュータビジョン

この書籍はコンピュータビジョンの入門として買ったのですが、ソースコードpythonで書かれておりとても読みやすかったです。 今回実装するVSLAMでは主にこのpythonコードとopenCVを使って実装しようと考えています。

Kindle Unlimited

8月に入りますます暑くなってきましたね。 夏といえば海行ったり、山行ったり、祭りに行ったりと楽しいイベントがありますが、この暑さではちょっと外にでるのは苦痛ですよね。
ここはひとつ冷房の効いた部屋で本を読んだり、プログラミングしたり、アニメやニコ動見るのが一番な気がしてきます。
  

読書といえばアマゾンの電子書籍読み放題のサービス「Kindle Unlimited」がはじまりましたね。
早速無料お試ししているんですけど、マイナビ出版の技術書が対象書籍になっているおかげでお勉強がはかどりそうです。
中でも"買い"だなと思ったのがセバスチャン・スラン氏の 確率ロボティクス が読めちゃうところです。

確率ロボティクス (Mynavi Advanced Library)

確率ロボティクス (Mynavi Advanced Library)

スラン氏はスタンフォード大の教授でgoogleの副総裁にして自動運転技術の第一人者です。また同氏が設立したUdacityというオンライン学習サービスで自動運転技術の講義が見れちゃいます。   

ところで自動運転や、最近ではお掃除ロボットなどの位置推定に用いられている手法にSLAM(Simultaneous Localizetion And Mapping)というものがあります。

これはセンサを使って周囲の情報を収集し、自分の周囲の環境の地図を作りながら自分の位置推定を行う手法で、確率ロボティクスではSLAMやそれに関連する技術についてわかりやすく説明されています。
翻訳書ですが日本語でここまでまとまっていて整理されたSLAMの解説はないんじゃないかと思います。   

ちなみに定価だと7000円くらいした記憶があるんですが、Kindle Unlimitedを利用すれば月額980円で読めてしまいます!
いやぁ太っ腹だなぁ!その調子でどんどんやってくれ!
  

僕は去年Kindle版を買ったのでちょっと損した気分ですが...

  

いずれにせよこういった優れた書籍(そして学生には高価な書籍)がたかだか1000円で読み放題っていうのは夢みたいな話ですね。 個人的にはオライリーの本も対象書籍にならないかなぁなんて思っていますがどうでしょうかね。
  

技術書以外でもマンガや小説で読みたかった本が色々と読めるので今年の夏は引きこもり読書ライフがはかどりそうです。
では、まだ読みかけの本があるのでこれくらいで終わります。

Pythonメモ

僕はC言語からプログラミングを学び,JavaAndroidアプリ作ったり,RubyScheme,Common Lispなんかを触ったりして,最近PythonをはじめたPython初級者です。

この記事は勉強していく中で「へーそんな書き方あるんかー」と思ったPythonのコードの作法をメモしたものです。(備忘録というやつです)
勉強しながら適宜更新していく予定です。

リスト内包表記

リスト内でfor文を使ってリストを初期化する 。

たとえば数値列の累積和のリストをつくるには以下のように書ける。

num_l = [1 , 2 , 3 , 4]
sum = 0
cumsum_l = [num+sum for num in num_l]

また奇数だけの累積和リストを取りたい場合(そんな場合があるかは知らんが)以下のように条件付けできる。

num_l = [1 , 2 , 3 , 4]
sum = 0
cumsum_l = [num+sum for num in num_l if num % 2 !=0]

ジェネレータ

リスト内包表記ではfor句,if句を使って条件に合う項すべてを含んだリストを生成する。 これではリストサイズが大きい場合にメモリ,処理時間が多くなってしまう。 そこで一度にリストを作るのではなく,要素を一つずつ逐次生成するのがジェネレータである。
ジェネレータではreturn文は用いずにyield文によって指定した値を生成して返す。
なのでメソッドの中にyield文があったならそいつはジェネレータだ。
例としてジェネレータを用いてFizzBuzzを実装してみよう。

  • FizzBuzz:1から数を数え挙げていき、3の倍数のときに"Fizz",5の倍数のときに"Buzz",15の倍数のとき"FizzBuzz"と出力するナベアツ的なやつのこと。
def fizzBuzzGen():
    i = 0
    while(True):
        i += 1
        if i % 15 == 0:
            yield "Fizz Buzz" 
        elif i % 3 == 0:
            yield "Fizz"
        elif i % 5 == 0:
            yield "Buzz" 
        else:
            yield i

g = fizzBuzzGen()
for i in range (20):
    print g.next()
->1
  2
  Fizz
  4
  Buzz
  Fizz
  7
  8
  Fizz
  Buzz
  11
  Fizz
  13
  14
  Fizz Buzz
  16
  17
  Fizz
  19
  Buzz

文字列操作

文字列中に特定の部分列を含むか判定する。

str = 'This is a string'
str.find('string')

組み合わせ

組み込みモジュールの中に itertools というものがあり,これを使うと組み合わせや順列などを扱える。
組み合わせには itertools.combinations( iteratable , r) を用いる
これによりリストなどからn個の要素を取り出すときの組み合わせを生成するジェネレータを返す

string = "ABC"
#string(ABC)から任意の2文字を選ぶ
[c for c in itertools.combinations(string , 2) ]
-> [('A','B') , ('A','C') ,('B','C')]

順列

順列には itertools.permutations( iteratable , r) を用いる。 これによりリストなどからn個の要素を取りだし並べるときの順列を生成するジェネレータを返す。

string = "ABC"
#string(ABC)から任意の2文字を選びならべる。
[p for p in itertools.permutations(string , 2) ]
-> [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

文字列リストの連結

L = ['The ','length ','of ','this ','list ','is ','seven.']
print ''.join(L)
-> 'The length of this list is seven.'

Cracking The Coding Interview (つづき)

前回記事にした

をちまちまと読み進めています。 こういう頭を使う知的ゲームは、なんというか大学受験の時の数学を思い出しますねー。
問題文を一読して解法の当たりがつくこともあれば,頭のなかで試行錯誤しながら正解に近づいて行く場合もあります。
一方で「全然解答がわからない。発想が根本的にちがうのでは?」という状況もあったり。
勉強していて一番面白いのはそういう問題を考えているときで、たとえ正解にたどり着かなくても解答を読んだ時のインパクトが違う。
今日は「そんな解き方、考え方があったのか!」と思わず膝を打った問題についてです。


1.8 片方の文字列がもう片方の文字列の一部分になっているかどうか調べるメソッドisSubstring()が使えると仮定する。
二つの文字列 str1 , str2 が与えられたとき、isSubstring()を一度だけ使ってstr2がstr1を回転させたものかどうか判定する
プログラムを書け


この問題を見たとき、全く解法が頭に浮かびませんでした。
「ふーむ、困った。どうしよう。とりあえず二つの文字列の長さが異なる場合は明らかにFalseでいいだろう」
「長さが同じ場合、str1とstr2の関係としては
①str1を回転させたものがstr2 ②str1とstr2は長さが同じだけで全然違う文字列 ③str1とstr2は互いにアナグラム
という場合が考えられそうだ」
「①は③に包含される。とりあえず②の可能性をつぶすためにアナグラムかどうか判定しよう」
アナグラムの判定はstr1とstr2をソートして比較すれば実装できるからとりあえずおいておこう」
「じゃあstr1とstr2が互いにアナグラムだとして、str1を回転させたらstr2になるかどうかどうやって判定しよう」
「str1をn回右に回転させたものがstr2だとしよう。いま文字列を右にn回回転させる関数をRotate(str,n)とすると  isSubstring(Rotate(str,n),str2) == True となるはずだ。」
「じゃあstr1を何回右回転させたらstr2になるのかどうやって求めたらいいだろう???」
「たとえば文字列中に一回しか出現しない文字cが存在するならstr1.indexOf(c)とstr2.indexOf(c)を比べれば回転数nが求められるだろう」
「そんな都合のいい文字cが存在しない場合は??」
「どうしよう....」
  ・
  ・
  ・

模範解答

模範解答をみてまず思ったのが「あれ?解説とソースコード短くね?」ということ。
実際数えるとソースコードのステップ数はたった10ステップ。一体どういうことだってばよ...
うすうす気づいていましたが考え方が根本的に違っていました。
この問題を解くために重要な考えは回転すなわち円運動には周期が存在するということです。 もっとかみ砕くと、繰り返しの中にパターンがあるということです。 例えば以下のような文字列str1,str2があったとします。

str1 = "waterbottle"
str2 = "erbottlewat"

str1を三回左に回転させたものがstr2になります。
では、実際にstr1を繰り返します

str1 + str1  == "waterbottlewaterbottle"

ここにstr2が含まれているのに気が付くでしょうか?

"waterbottlewaterbottle"

このように回転の周期性のために、元の文字を繰り返した中に回転後の文字列を見出すことができます。 というわけで答えは

isRotate(String str1,String str2){
   int len = str1.length();
   if(len == str2.length() && len > 0){
     String str11 = str1+str1;
     return isSubstring(str11,str2);
   }
   return false;
}

いやーこんな冴えたやり方があったとは。こういうのを自分で思いつけるようになりたいですな。

世界で闘うプログラミング力を鍛える150問 Cracking The Coding Interview

という本を買いました。 IT企業の採用でしばしば実施されるコーディング面接をどのように攻略するか、 また実際のコーディング問題にどのようにアプローチすべきかを解説した書籍です。

導入部分(書籍の1/4くらい)は主にIT企業に就職するための対策について書かれています。
その後、各章で特定のデータ構造やアルゴリズムについて取り上げて、注意すべき点をまとめ、 コーディングの問題を解くという形式。

問題の解法にかなりページを割いており、書籍(450ページくらい)の半分が解法になっている。

プログラミングの勉強もかねて読んでいこうかなぁと思います。

第一章は配列と文字列  

記念すべき最初の問題は以下


1.1 ある文字列が、すべてユニークであるかチェックするアルゴリズムを実装せよ。またそれを実装する際に新たなデータ構造が使えない場合どうすればよいか


はじめに思いついたのが出現した文字をカウントするという方法。
たとえば文字をkey,文字の出現回数をvalueとするディクショナリをつくり、 valueが2以上になるkeyがあった場合にfalseを返すというもの
簡単に書いてみると以下のような感じ

import java.Util.*

boolean checkStringDuplication(String str){
    Map<Charactor,Integer> CharCountMap = new Map<Charactor,Integer>();
    for (int index=0;index<str.length();index++){
        char c = str.charAt(index);
        if(CharCountMap.containsKey(c)){
            return false;
        else
            CharCountMap.put(c,1);
    }
    return true;
}

と、書いてみたけれど、途中で文字の出現回数をカウントする必要ないと気づいた(CharCountMapなんてひどい名前をつけてしまった...)

結局のところ、既出の文字を記憶しておいて二回目に同じ文字が出たらFalseを返すだけだから、 MapじゃなくてListとかのほうが適切かな。

import java.util.*

boolean checkStringDuplication(String str){
    ArrayList<Character> CharEncountList = ArrayList<Character>();
    for (int index=0;index<str.length();index++){
        char c = str.charAt(index);
        if(CharEncountList.contains(c))
            return false;
        else
            CharEncountList.add(c);
    }
    return true;
}

あらたなデータ構造使うまでもなく実装してしまったけど、ほかにどんな実装が考えられるだろう?

文字列を先頭から順番に見ていくとして、現在注目している文字が文字列中の別の場所で出現しないか をチェックすると考えると、lastIndexOfとかで後ろから出現個所をチェックする方法も考えられそう。

import java.util.*

boolean checkStringDuplication(String str){
    for (int index=0;index<str.length();index++){
        char c = str.charAt(index);
        if(str.lastIndexOf(c) != index)
            return false;
    }
    return true;
}

うーん、これも別に新たなデータ構造つかわないんだよなぁ
まあ、新しく独自の構造を定義するより既存の物を使った方がわかりやすいしいいか

で、解法をみてみると

模範解答では最初に文字列がASCIIと仮定していて、初めに文字列が256を超えるかチェックをしている。
もし文字列が256より大きいなら(ASCIIの文字種より大きいなら)鳩の巣原理的に文字に重複がある。
256より小さい場合は256サイズのboolean配列(各要素がASCII文字に対応)で既出かどうかをフラグだててチェックする
といった形になっている

確かに文字コードについては初めに気にしておくべきかもしれない。
文字コードがわかっていれば必要となる配列サイズがわかり、プログラムがどれくらいのメモリを必要とするのかわかる。
その点を意識しないと実行時にメモリ食ってあぼーんするかもしれないもんなぁ

別解として文字列をソートして頭から比較していく方法とすべての文字を互いに比較する方法について言及してあったが、 いずれにしても「新たなデータ構造を使えない場合」に関しては解法でも触れてないのか。 なんなんだろう

とりあえず今後の課題図書としてチマチマ読み進めようと思います。
面白い問題や解法が思いついたら記事にするかも

blogはじめました

タイトルは冷やし中華のごとく読んでいただけるとありがたいです(もう夏ですね...)。

はじめに自己紹介とこのブログについてです。
このブログの主な目的は研究や日々勉強したことの備忘録です。
特にネタがないときはアニメのこととか最近読んだ本とかを書き散らします。

筆者は大学院生で,情報工学を専攻しています。
好きな言語は python Java C# など 最近は画像処理やコンピュータビジョンに興味があり,その方面の記事を書いていく予定です。

はてなでブログを始めた理由はMarkdown記法が使えるということで,Markdownの練習にもちょうどいいかと思ったからです。
とりあえず週1更新を目指してちまちまとやっていこうと思います。

もしよろしければ見ていただけると幸いです。

今回は最初の記事なので私の好きな言語 Python についてお話ししようと思います。

Pythonってなに?

Pythonインタプリタ型のプログラミング言語です。 インタプリタ型なのでちょっとした作業を効率化するときにささっと立ち上げて,チョロチョロっとスクリプトを書けば動作させられます。(といってもWindowsにはPythonは標準搭載されてないけど)

Pythonはコードブロックを区切るのにインデントを用います.なのでCなどである
if(条件){
}

if(条件)
{
}
のどちらを使うべきかという不毛な戦争はありません。
参考
社畜ちゃん漫画まとめ | 社畜ちゃんBlog

また,インデントでコードを区切るため必然的に,プログラムの構造がわかりやすくなる言語です。

Pythonの特徴

Pythonは一行当たりのコスパが非常に高く,同じ処理をCで記述した場合に比べPythonでは1/6のコード量で済むといわれています。
プログラミング言語の比較 - Wikipedia

これは言語自体に色々便利な機能が搭載されていることに加えライブラリ(モジュール)が非常に豊富であるためといわれています。
特に科学技術向けのモジュールが豊富で,線形代数フーリエ変換機械学習数値計算などなどいろいろな処理がPythonのモジュールを使えば数行でかけてしまいます。

私がPythonを始めたのはこのモジュール群に惹かれてのことです。 大学での研究用にJavaやCなんかのプログラムを書くことがしばしばありましたが,コーディング自体は研究の本質でないため, 「車輪の最発明」のためにバグと戦うくらいなら,この豊富なモジュール群を使いこなすために勉強するほうがよっぽど有意義では?? と思ったことがきっかけでした。

実際に触ってみると使いやすいしやりたかったことが色々できるし(画像処理やら補間やら),Matplotlibという描画モジュールできれいにグラフを掛けたり といいこと尽くしでした。

Pythonを勉強するときに参考にしたサイト

最後に私がPythonを勉強するために参考にしたサイトをいくつか 挙げておきます。

  • 本家のサイト
    www.python.org
    Pythonの実行環境を作るときにどうぞ
    Python2.xとPython3.xで文法が微妙に違ったり,モジュールが未対応だったりするので とりあえずはPython2.xを入れるのが無難かと

  • 科学技術計算のためのチュートリアルサイト

1. 科学技術計算のために Python を始めよう。 — Scipy lecture notes
基本はこのサイトで勉強しました(配列のスライスとか描画の仕方とか)

  • インストールの参考
    http://www.aoki.ecei.tohoku.ac.jp/~ito/python_windows.html/
    色々なモジュールを入れるときの参考に
    基本はpipやeasy_installというモジュール管理ツールを初めにインストールし,あとはツールからお好きなモジュールをインストールする
    モジュール間で依存関係があったりするので注意

  • プログラミング
    www.udacity.com Pythonに限ったことではないけれどプログラミングやコンピュータサイエンスを勉強するときに便利なオンライン学習サイト
    英語メインだけどコースによっては動画に日本語字幕がついている

とりあえず最初の一回目は以上です。
気になった方はぜひPythonはじめてみませんか?
Pythonはいいぞ!!