Coding Memorandum

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

スポンサーサイト

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

OpenCVのSURF実装

画像認識などで使われる局所特徴量SURFの特徴量記述は次の式で定義される。(ここではdx, dyの詳細は説明しない)

これを4x4領域のピクセル毎に求めて結合した64次元のベクトルがSURFとなる。

OpenCV(2.0以降)の該当コードは次のようになっている。

/* Construct the descriptor */
vec = (float*)cvGetSeqElem( descriptors, k );
for( kk = 0; kk < (int)(descriptors->elem_size/sizeof(vec[0])); kk++ )
    vec[kk] = 0;
double square_mag = 0;

/* 64-bin descriptor */
for( i = 0; i < 4; i++ )
    for( j = 0; j < 4; j++ )
    {
        for( y = i*5; y < i*5+5; y++ )
        {
            for( x = j*5; x < j*5+5; x++ )
            {
                float tx = DX[y][x], ty = DY[y][x];
                vec[0] += tx; vec[1] += ty;
                vec[2] += (float)fabs(tx); vec[3] += (float)fabs(ty);
            }
        }
        for( kk = 0; kk < 4; kk++ )
            square_mag += vec[kk]*vec[kk];
        vec+=4;
    }
}

/* unit vector is essential for contrast invariance */
vec = (float*)cvGetSeqElem( descriptors, k );
double scale = 1./(sqrt(square_mag) + DBL_EPSILON);
for( kk = 0; kk < descriptor_size; kk++ )
    vec[kk] = (float)(vec[kk]*scale);

求めた特徴量を正規化する処理が入っている(28-30行)。SURFの元論文には正規化に関する記述は見受けられなかったので、OpenCV特有の処理であるようだ。

以前にSURFを実装したNTL MM1では、Bag of FeaturesでSURF特徴量をクラスタリングして用いているが、正規化を行うか否かでクラスタリング結果が変わってくるはずである。ちゃんと検証したわけではないが、直観的に正規化を行わない方がよい結果が得られそうだと思い、このときは論文に合わせて正規化を行わなかった。

ちなみにOpenCV 1.1では次の実装となっている。

vec = (float*)cvGetSeqElem( descriptors, k );
for( kk = 0; kk < (int)(descriptors->elem_size/sizeof(vec[0])); kk++ )
    vec[kk] = 0;

/* 64-bin descriptor */
for( i = 0; i < 4; i++ )
    for( j = 0; j < 4; j++ )
    {
        for( y = i*5; y < i*5+5; y++ )
        {
            for( x = j*5; x < j*5+5; x++ )
            {
                float tx = DX[y][x], ty = DY[y][x];
                vec[0] += tx; vec[1] += ty;
                vec[2] += (float)fabs(tx); vec[3] += (float)fabs(ty);
            }
        }
        double normalize = 0;
        for( kk = 0; kk < 4; kk++ )
            normalize += vec[kk]*vec[kk];
        normalize = 1./(sqrt(normalize) + DBL_EPSILON);
        for( kk = 0; kk < 4; kk++ )
            vec[kk] = (float)(vec[kk]*normalize);
        vec+=4;
    }
}

正規化をピクセル毎に行っており、OpenCV 2.xとは異なった計算式となっている(19-23行)。ピクセル毎に正規化を行うことは、SURFの特性から考えてもあまり良い結果になりそうになく、事実OpenCV 2.0で修正されている。

本来SURFの計算では正規化の必要はなかったが、OpenCVの何らかの都合で正規化の処理が行われているのではないかと思う。OpenCV 1.1の方法は良くなかったんで、2.0から直しておきましたみたいな感じかなぁ。

xrot

みなさんは覚えておいででしょうか?Linuxの黎明期にイケてるゲームを集めたパッケージ「JG」を。この中で最もCoolなゲーム[要出典]の一つに、ここでご紹介する「xrot」がありました。

xrotは、当時のUNIXワークステーション/PC Unix環境に合わせてプログラムの最適化を行っていたことからPseudoColor(256色モード)でしか動作しませんでした。(MIT-Shared Memory Extensionを使うなど、かなり頑張っていた)

初リリースから十数年の時を経て、TrueColorに対応させた最新のxrotをここにリリースします!


xrotのプレイ動画を作成してみました。

 

ソースコードは下記に置いています。(古いスタイルのC(ANSI-Cでない)で作られています)
https://github.com/msiro/xrot

動作確認は、OSX 10.10.3+Xcode 6.3.1 と Ubuntu 15.04 で行いました。

Buildのポイントを下記にまとめておきます。

OSX
Ubuntu
  • 次のパッケージをインストールする。
      xutils-dev, libx11-dev, libxpm-dev, libxext-dev
  • FONTが見つからないエラーとなるため、FONTの定義を変える。
    xwin.c  Line.51-53
    ▼変更前
    #define FONT   "-*-new century schoolbook-medium-i-*--18-*-*-*-p-*-*-*"
    #define FONT_CS   "-*-new century schoolbook-medium-r-*--18-*-*-*-p-*-*-*"
    #define FONT2  "-*-times-bold-r-*--14-*-*-*-p-*-*-*"
    ▼変更後
    #define FONT   "fixed"
    #define FONT_CS   "fixed"
    #define FONT2  "fixed"
    適切なFONT指定方法が見つからなかったためfixedで代用

Enjoy!

Ubuntu 14.04 インストール失敗記

今日は、一日かけてUbuntuのインストールを試みたがあえなく失敗。とりあえずメモとして纏めておくこととする。

【やりたかったこと】

  • Windows8.1とUbuntu14.04のデュアルブート
  • Windows8.1はインストール済みでUEFIブートの構成である
  • HDDは1台で空き領域あり

【(自分の中の)結論】

  • HDD1台構成でUEFIのデュアルブートは無理

もう少し勘所を押さえれば簡単にできることなのかもしれませんが、現時点ではギブアップし増設HDDを調達することにしました。

下記参考にした情報源をまとめます。
今回の目的そのものずばりのサイト「デュアルブート(UEFI Win8.1 + Ubuntu14.04)その1」。 ここに書かれている通りで上手く行くと思いきや、私の環境ではブートマネージャGRUBが起動せず、Windowsが起動してしまいました。

それからUbuntuのフォーラム「UEFIでのデュアルブートについて」。他のサイトでも見かけたが、インストールCD/DVD、USBはUEFIモードでブートする必要があるとのこと。
しかしながら、私の使っているマザーボートH87-PROでは、 DVD、USBメモリのUEFIブートがどのようにやってもできなかった。この点が一番の問題であったようにも思う。

Ubuntuには「Boot-Repair」なるブートマネージャを修復してくれるツールがあるとのこと。Live DVDで起動しBoot-Repairで修復を試みた。処理途中に出るメッセージでは、UEFI環境であることを認識し、GRUBの再インストールをするとのことで、非常に期待が持てた。しかしながら残念なことに、このツールを持ってしてもGRUBが起動することなく、Windowsが起動してしまうという状況であった。

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バーコードとした。

     

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

    Haswell PC

    HaswellでPCを組みました。今回使ったパーツは次の通り(かなり無難な構成です)。

    マザーボード ASUS H87-PRO OCしないのでチップセットはH87で十分。
    メジャーなメーカーを選択。
    CPU Core i7 4770 OCしないので無印
    メモリ Kingston 8GB (4GB×2) DDR3-1600 評判の良いメーカー
    HDD WD Red 2.0TB 信頼性重視
    電源 玄人志向 KRPW-GP650W/90+ 評判の良い電源。C6/C7ステートサポート。必要なケーブルのみ挿して使えるのでケース内がすっきりする。
    ケース ANTEC NINEHUNDREDTWO-V3 冷えるケースを選択。天板に18cmファンが付く。
    グラフィックボード 玄人志向 GeForce GTX660 GTX660で一番安いもの

    DVDドライブ、キーボード、マウスは旧PCの流用です。同じようなPCを組む方の参考になれば。今のところ、問題なく稼働しています。OSはWindows8 64bitです。

    今回は全部Amazonで揃えました。ここのところの暑さで秋葉原まで行く気力が出ませんでした…。

    前のページ 次のページ

    FC2Ad

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