Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Omega Detector

久々のMarathon Matchの参加。前回submitまで漕ぎ付けたのは2011 TCO予選らしいので、実に3年ぶりとなる。ここ数年、仕事での消耗が激しく、Marathon Matchの開催期間中のモチベーションが維持できない状態が続いている…

今回のお題は「バーコード検出」で、コンピュータビジョン勉強中の自分にとって興味ある題材であり、何とかsubmitまで辿りつけた。

丁度下記の本を読んでいたところで、この本の内容を基本として進めていくという方針で着手した。(Kindle版が¥1,854とお得)
    Mastering OpenCV With Practical Computer Vision Projects

当初検討では、次の方法を想定した。
1Dバーコードの検出

  • ガウスフィルタでノイズ除去
  • Sobelフィルタでエッジ検出
  • 2値化
  • Morphology処理(太線化&細線化)
  • 直線の検出
  • 直線が集まる(並ぶ)部位の検出

2Dバーコードの検出

  • ガウスフィルタでノイズ除去  => ぼやけてしまって、次処理のコーナー点検出に不利かも?
  • コーナー点検出
  • コーナーが集まる部位の抽出

2Dバーコードの方は相当に手薄感があったが、作りながら考えることとした。また、今回のスコアルールでは画像1枚あたり数ms~数十ms程度での処理が期待されているようで、上記はかなりリッチな内容である(処理時間がかかる)気もしていた。

1Dバーコード検出の試作ができたところでExample Testを実行。bad_allocが出る…。問題文に「the memory limit is 2MB」の記述発見-どうやら問題文をちゃんと読めていなかったようだ…

省メモリ化を踏まえ、最終的には次の方法で実装した。
■ 共通処理

  • ガウスフィルタでノイズ除去
  • Sobelフィルタでエッジ検出
  • 直線の検出

■ 1Dバーコードの検出

  • 直線が集まる(並ぶ)部位の検出

■ 2Dバーコードの検出

  • L字(直線が直角に接続する)の検出 => L字を含む正方形の抽出
  • 正方形の重なりを併合
  • L字の対向に白黒のパターンがある。

    以下、それぞれの項目についてメモを残しておく。

    直線の検出

    直線の検出といえば、Canny法等でのエッジ検出+ハフ変換が定番。今回は省メモリと実行時間の短縮を考慮して、次のような方法を考案した。

    1. Sobelフィルタでエッジ勾配を検出

    Sobelフィルタでエッジ強度を求め閾値でエッジ判定するとともに、x,y方向の勾配値からエッジの勾配方向を8方向で抽出した。方向の分割数については、もっと良い解があると思うが検討時間がないため8方向で決め打った。

    od_original
    元画像

    od_sobel
    Sobelフィルタ

    Sobelフィルタの画像は8方向に対応させてGreen、Blueの色付けを行った。

    2.直線の抽出

    Sobelフィルタの結果に対して、Flood Fillでエッジ領域の抽出を行った。Flood Fillは隣接する2方向に限定して行い8連結で走査する。同じ勾配を持つ領域が抽出できる。

    抽出した領域に対して、最遠点を結ぶ直線を定義する。この直線と領域内の各点の距離が全て閾値内であれば、これを直線として抽出する。

    od_line
    検出した直線(赤色)

    直線と各点の距離は、外積で求めることができる。

    distance
    点と直線の距離

    1Dバーコードの検出
    1.隣接する直線の検出

    隣接する直線をグルーピングし、閾値以上の本数の直線を含むグループを1Dバーコードとする。グルーピングの管理はUnion-Findを使った。

    隣接する直線の判定条件は「① 2つの直線がほぼ平行であること」。実装では、2つの直線がなす角が14度以内であることとした。角度は内積でcos値を求めて判定する。「② 2つの直線の重複率が70%であること」。重複率は、(直線の傾きにより)x軸もしくはy軸への射影で重複部分の割合で求める。

    2Dバーコードの検出
    1.L字の検出

    2Dバーコード検出のために、L字をなす直線を検出する。条件は「① 2つの直線がほぼ直角である」、「② 直線の端点の最短距離が閾値以下であること」、「③ 2つの直線の交差点を起点とし、2つの直線の終点(交差点から遠い方の端点)で作られる四角形が正方形に近いこと」。

    直角の判定は内積を用いる。2つの直線の交差点の求め方は「平面上の2直線の交点を外積により求める」を参考にした。

    2.正方形の重なり/L字の対向に白黒のパターンチェック

    この辺りで時間切れが迫り、やっつけ感が漂い始める…
    上記で四角形が得られるが、元画によってはL字の対向の辺も直線として検出されることで、1つの2Dバーコードに対して重複した複数の四角形が得られることがある。このため、重複した四角形は1つの四角形に併合する処理を入れた。
    四角形の重複判定の基礎となる矩形と点の位置関係の判定は「回転する矩形と点の当たり判定」に書かれる手法がすばらしい。一般的には外積を用いる手法があるが、矩形が直方体であることを前提に計算量の少ない方法が提案されている。

    四角形が得られたのち、Data Matrixの特徴である黒ブロックと白ブロックが交互に現れるパターンをチェックして、このパターンに当てはまる場合は2Dバーコードとした。

     

    最後は時間が足りず、最終結果はあまり芳しくなく。しかしながら直線の検出までの知見はかなり得られたので良しとしよう。

    スポンサーサイト

    Robonaut Challenge

    だいぶ古い話となってしまいましたが、4月にTopCoderで「Robonaut Challenge」が開催されていて、時間の許す限り検討を進めていました。ヒューマノイドロボットの両眼カメラで見た画像からの物体認識の問題でした。

    結果的には時間切れで終了という残念な状態でしたが、ここで検討したこと・調べたことなどをメモと記憶を頼りに纏めておきます。

    問題の概要は、平面パネルに付いている光るプッシュボタン、トグルスイッチ等のパーツの位置と状態を識別するものでした。特徴はステレオ画像であること、視線がパネルの正面でないこと(見下ろしが多い)、照明状態が種々あることなど。

    解法の方針としては、平面パネルを認識してからパネル上の各パーツを認識させるか、直接各パーツを認識させるかとなる。いづれにしても局所特徴量が必須であると思い、まずはこの辺りから調べてみました。

    問題類型としては特定物体の認識となり、トレンド(既に古典?)的には局所特徴量のマッチングが思い浮かぶ。局所特徴量といえばSIFT、SURF(2年前のエントリ参照)となるが、今回は視線の向き(パネルの向き)がいろいろあるため不向きとなりそう。視線の向きが変わると画面上はアフィン変換(拡縮、回転など)となり、SIFT・SURFはアフィン変換に弱い。

    局所特徴量の技術は、キーポイント検出と特徴量記述の2つの要素で構成される。それぞれ独立に考えてよいものだ。キーポイント検出は、SIFT・SURFの手法以外にもいろいろある。コーナー検出もキーポイントとなりえる。コーナー検出であればアフィン変換に対して堅牢であると考えた。手元のメモには、「FAST Corner Detector(OpenCV)」、「MSER (WikipediaOpenCV)」と残っている。

    また、次のサイトが参考になった:「複数画像から3次元構造・カメラ挙動の復元手法の調査

    特徴量記述については、SIFT・SURF以降の動向(BRIEF、ORB、BRISK)が次の資料に纏まっていて参考になります。

    OpenCVにはFREAKが実装されている。性能は微妙?(Ref.CVPR2012 報告

    局所特徴量のキャッチアップはここまでとして、以下考えたこと・試したことを記していきます。

    • アフィン変換が含まれるため、局所特徴量の適用は難しそう。ステレオ画像であることを活用することはできないか? → 対象のパネルは背景物よりカメラに近い。近いものから探索すれば良いのでは?
    • OpenCVのステレオマッチング(cvFindStereoCorrespondenceGC)を試す → 良い結果が得られず。パネル面の特徴が少ないからか?
    • ステレオ画像の距離計算は次の資料が参考になりました。
       ステレオビジョン画像処理技術の実用化研究
    • 別方針を考える : まずパネルを検出する。カメラ視点の影響からナナメに写ったパネルを正面視点に補正させる。スマホアプリでホワイトボードとか名刺の写真を補正するものをよく見かける。→ 「幾何補正」というらしい。
    • 幾何補正後のパネル画像で、局所特徴量のマッチングを行えば良いのではないか。そもそも、各部品の相対位置が固定なので、パネルをきっちり検出できたら部品の位置も導出できてしまう。
    • 四角いパネルを見つける → エッジ検出(Cannyなど)し、ハフ変換で直線を検出する方法を試す。
    • Cannyでは、光の反射具合で線分が途切れたり、パネル境界が立体的なため線が多重に検出されるなど、上手くいかない。
    • 画像の「領域分割」という手法がある。いま行いたいことはパネル部分を領域分割することだ。
    • 領域分割は次の資料が参考になりました: 画像の領域分割に関する従来研究
    • ミーンシフト法が良いようだ。「コンピュータビジョン最先端ガイド2」の2章にも記述がある。
    • OpenCV(cvPyrMeanShiftFiltering)で試作。良い結果が得られる。ただし遅い。 → 画像を縮小すればよいかも。
    • ミーンシフトに関する参考資料を挙げておきます。
        画像追跡(2) -領域の追跡-
        第8回 CV勉強会

    ここまでで時間切れ、終了となりました。後で上位者のコードを見て、勉強しておかねば!

    NTL Robot Challenge

    Topcoder方面でWeekend Algorithm Contestなるものが開催され,少し時間を作って参加してみました。コンテスト形態はマラソンマッチですが,期間が2週間ではなく金~日の3日間という短いもの。

    NASAスポンサーでRoom内上位5位に入れば賞金Getという形式でした。幸いなことに私の割り当てられたRoomはエライ過疎りようで,最終的には参加者4名でした。0点でもSubmitすれば5位に入れるという状況なのに誰も参加してこない。

    私自身は(金)は仕事,(土)は家の雑用,(日)はHaskell勉強会に参加してたので,トータル5,6時間程度しか時間をかけられず,あまり練ることができませんでした。しかしながら,上述の状況なので暫定順位は2位。少しばかり賞金を頂けそうです。

    問題は「複数のロボットと複数の出口があって,ロボットは全体同時にしか制御(右ターン,左ターン,前進)できないけど,なくべく短い手数で全ロボットを脱出させてね」というもの。

    初めの考えは,DevQuizのスライドパズルのようなグラフ探索だったのだけど,TLEまで2秒なので早々に断念。次の考えは,それぞれのロボットが最適手を考えて投票するのってカッコイイねとか思いながら,それってタダの評価関数の線形結合だよねとか・・・結局ローカルミニマムに嵌まってグルグルと回る。

    とりあえずゴールできる版として「一機ずつ脱出させる」版を作ったところで,モチベーションが切れる。前述の評価関数をチューニングするところまでは気持ちが届きませんでした。後はどれから脱出させるかを探索するようにして少しスコアを上げたところで終了でした。

    NTL MM1メモ

    すっかり旬も過ぎてしまいましたが「NASA Tournament Lab Marathon Match1」について,考えたこと・調べたことのメモを記しておきます。

    問題はこちら(要TopCoderID)。航空写真に車が写っているかの有無を判定する機械学習モノ。トレーニングデータは4000個用意されている。

    以下に考えたこと等を記していきます。

    • 「物体認識」といえば最近のトレンドは局所特徴量のはず(もう古い?)。 Open CVにあるSIFT,SURFが有名。
    • SIFT,SURFは特定物体のマッチングで良く使われる。ARのマーカー検出の事例が有名。
    • SIFT,SURFには汎化能力はなさそう。
    • 車を見つけるには,エッジ抽出して長方形を検出すれば良いかも。=> 教師データを眺めると建物とかも長方形なので,エッジだけでなくテクスチャの情報も合わせる必要がありそうだ。
    • 物体認識系の論文・資料等の調査。 最新動向にキャッチアップ。
    • この資料によれば,局所領域のつながりを見る手法が優位のようだ。学習手法はBoostingが良いようだ。
    • Joint HOGとAdaBoostについて少し深く調査してみる。次の論文が参考になります。
           http://www.vision.cs.chubu.ac.jp/04/pdf/ITS07.pdf
    • 物体認識について,中部大学 藤吉教授/藤吉研究室の情報発信量がすごい。上記の他に下記の資料も大変参考になりました。
           http://www.vision.cs.chubu.ac.jp/joint_hog/pdf/HOG+Boosting_LN.pdf
           http://www.vision.cs.chubu.ac.jp/joint_hog/pdf/Joint+RAB.pdf
           http://www.vision.cs.chubu.ac.jp/vu/pdf/VU7-ObjectClassification.pdf
    • AdaBoostについては,下記サイトで各種情報を纏めてくださっています。
           http://d.hatena.ne.jp/ymuto109/20070823
    • HOG,Joint HOGを調べると,向きの変更(回転),スケールの変更に対して弱そうである。今回の問題は航空写真なので回転とスケーリングの要素が加わっており,これらを上手く扱うことが肝になる。
    • Joint HOGは局所特徴量の相対的な位置を学習しているが,これを拡張して相対的な角度も学習してあげれば回転に対してロバストにできそう。==> 上手く行ったら論文かけるかも。
    • しかしながら,スケールの変化に対しては良い解決案が浮かばない・・・
    • さらに調べを進めると,今回やろうとしていることは「一般物体認識」というものらしい。再度検索・・・
    • Bag of Featuresというものがピッタリと当てはまりそうだ。
           http://www.vision.cs.chubu.ac.jp/04/pdf/TS02.pdf
    • 発注していた参考書が届く。前々から読みたかった本でもあり,良い機会なので買いました。
           コンピュータビジョン最先端ガイド1
           コンピュータビジョン最先端ガイド2
           コンピュータビジョン最先端ガイド3
    • この本でもBag of Featuresが大きく取り上げられている。
    • Bag of Featuresについては,次の資料が参考になります。
           http://www.vision.cs.chubu.ac.jp/ssii08/ssii08-yanai.pdf
    • Bag of Featuresは,前述で汎化能力がないとしたSIFT,SURFを使って汎化能力を持たせることができる。SIFT,SURFは回転,スケールの変化に対してロバストであることから,今回の問題にピッタリの手法と思える。

    • Bag of Featuresの考えを使って実装してみる。局所特徴量にはSURF-128を使う。
    • 局所特徴量のクラスタリングにk-means法を使う。とても時間がかかる。終わりそうにない。
    • 最近傍計算の多さがネック。kd-treeを使うと早いらしいが,次元が多いときは効果が薄いらしい。次元が多いとは何次元ぐらいを指しているのだろうか?128次元はダメ?
    • 下記サイトで三角不等式を使って高速化する文献へのリンクを見つける
           http://ibisforest.org/index.php?k-means%E6%B3%95
    • 論文はこれ
           http://www.aaai.org/Papers/ICML/2003/ICML03-022.pdf
    • かなり早くなり,計算を終えられるようになった。

    • 機械学習にはSVMを使う。SVMは作りおきがある。以前のMarathon Matchで作ったモノだが,一度もSubmitされることなくお蔵入りになったモノだ。 ついに日の目をみるときが来た。
    • うぅむ・・・動かない・・・・・・引数のコメントが間違っているようだ。教師データの正解出力は0 or 1と記載しているが,正しくは-1 or 1のはず・・・・・・動いた!

    • コード完成。しかし,submitしても結果が返らない。キューにも入らない。エラーも表示されない。
    • ・・・悩むこと3,4日・・・
    • どうやらコンパイル後のバイナリサイズに制約があるらしい。1Mバイト以内だそうだ。
    • ローカル環境でのバイナリサイズは4MB越え。どうしよう・・・
    • SVMのサポートベクトル数は,学習ケース数と相関がある。学習ケース数を減らせばサイズが減るはずだ。
    • 試行錯誤。4000個を500個に減らせば1MBに収まる!
    • ランダムに500個を抽出。残り3500はテストケース。 結果的には,このことによってオーバートレーニングを抑止でき,好成績を残せたと見ています。
    • 残り2日間は,ひたすらランダムに組合せを変えて学習。
    • 最終日。チャンピオンデータを提出。

    • 入賞したこともあって,SURFって権利的に問題ないのかが急に気になり始める。SIFTがNGであることは色々なところで見かける。
    • とりあえず,TopCoderの方に相談。参加資格に問題がないか調べてくれるとのこと。
    • 待つこと1ヶ月。賞金の通知が来ました!明示的な回答はないのだけれど,問題はなかったと考えてよいようです。

    The NASA Tournament Lab Marathon Match

    Marathon Match 参戦中 ・・・(1/28-2/18)
    航空写真での車の有無の判別問題。なかなか興味深い。


    2/21 : System Test が終わって,現在 Top!
    今回はSystem Testデータに対する物言い期間があるようで,順位が確定するのは48時間後以降のようです。


    2/28 : Testデータ修正後の再テストの結果が出ました。見事に1位をキープしました!

    訓練データで評価されるProvisionalスコアの高い人が軒並み落ちているので,オーバートレーニングとの折り合いをつける戦いだったのではないかなと思います。

    私の方は,コンパイル後のバイナリサイズが1Mバイト以内でないといけないという謎の(記載のない)仕様にひっかかり,訓練データを10%程度までに減らす破目に合いましたが,結果としてはこれが功を奏したようです。

    まとまった時間がとれたところで,今回の大会の内容を書いておきたいと思います。

    次のページ

    FC2Ad

    上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。