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秒なので早々に断念。次の考えは,それぞれのロボットが最適手を考えて投票するのってカッコイイねとか思いながら,それってタダの評価関数の線形結合だよねとか・・・結局ローカルミニマムに嵌まってグルグルと回る。

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

    GCJ 2012

    GCJで初のTシャツ圏内!ちょっとうれしい。最近,ショートラウンドものから遠ざかっていたのだけど,かなりの健闘を見せました。

    まだまだ問題によって得意不得意の波が大きいので,来年以降も安定的にTシャツ圏内に入れるように実力をつけていきたいなぁと思うところです。

    出遅れ

    Samurai Codingは,そろそろ問題公開の頃ということで久々に訪問してみたら,参加は先着100チームで締切り! しかも,参加者一覧に99チームが出ている状況・・・。急いで登録しましたが間に合いませんでした。

    去年の参加状況が先入観として残っていたので,ゆっくりしすぎました。今年はプロモーションが上手くいったみたいです。

    結果的には,USPTO Innovation Challengeに全力を注げる状況になったので,こっちを頑張ります。得意のCV系なので上位に食い込みたい。

    もう一つ重なると大変だなと思っていた AMD OpenCL Performace Challenge2 は延期がさらに伸び年内に開催されないことが発表されたので一安心。しかしながら,AMDの状況が変わっていることから,このまま中止となるような気も・・・

    Performance Challenge1も,締切り直前でルールを厳格化して締切りを伸ばすなどグダグダな状態。最終スコアもTop5しか発表しないというのもどうかと。AMDさんには頑張って欲しいところです。

    次のページ

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