Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2011-02-28

[]NASA NTL Marathon Match 1 00:19 はてなブックマーク - NASA NTL Marathon Match 1 - TopCoderの学習のお時間


割に合わない賞金につられた人たちが集った(?)回。


問題


http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14481&pm=11313

150*150くらいのボケた航空写真が与えられる。画像の中に乗り物が写っているかどうかを判定してその可能性を0〜1の間の実数で返せ。

訓練集合として、乗り物が写っているパターンの画像1000枚くらいと背景だけの画像3000枚くらいが用意される。


方針


学習フェーズ(機械学習じゃなくて自分の脳に対しての学習)

画像処理とか機械学習とかやったこと無いので、図書館から本借りてきて期間の前半はひたすらお勉強していた。在学してなくても利用できるとは大学図書館は素晴らしいものだ

あやうくそれだけで満足しかけた。危ない危ない


単純解

とりあえず、扱いやすくなるよう次の処理をする

  • ノイズ除去のためにメディアンフィルタかける
  • 画素値ヒストグラムの1%〜99%の位置が0〜255に合うよう線形変換してコントラスト強調

乗り物(というか人工物)は基本のっぺりしていて、背景(というか自然物)はわしゃわしゃしているので、

近隣の画素との差分をとって、その平均値が小さいかどうかで判別できるのではないかと考えた。

エッジがあるのでそれを除外するために適当に閾値を設けて、大きすぎる差分値は計算から除外する。


訓練集合の画像それぞれについて画素値の差分の平均値を計算して、乗り物あり・なし両方の集合内で正規分布を仮定して最尤推定からパラメータを決める。

テスト画像について同じく差分平均値を計算して、正規分布からP(乗り物あり)とP(乗り物なし)を求める。

返すのは P(乗り物あり) / (P(乗り物あり) + P(乗り物なし)) 。


これだけでスコア0.7くらい出た


エッジ検出

乗り物、というか人工物の特徴として、平行だったり直交したりしている直線が多いことに着目した。

このへん http://www.pages.drexel.edu/~weg22/can_tut.html を参考に、canny edge detectionを実装。

そしてHough変換で直線を検出してみる。

しかし直線の数や垂直な線がどれだけあるかの情報だけでは大して役立たなかった。↑の方がまだ良い結果になる。


領域分割

画素値をk-means++でクラスタリングして塗り分けてみる。Kは適当に9とか決めうちで。

この領域の境界を使って直線・角の検出をしたり乗り物の領域を検出したりできないかと思ったけどうまくいきそうになかった。


あとk-meansやってるとTLEの危険があることに気づいて画像をグレースケール化することにした。

(けど結局グレースケールにするんだったらそもそもk-meansなんてやらずヒストグラムのp-tileだけで十分だったかも…)


パーセプトロン

機械学習的な手法も使ってみたいと思い、本に載ってた隠れ層ありパーセプトロンを実装してみた。

入力に使った画像の特徴量はこんな感じ。

  • ↑の「単純解」で使った画素値の差分平均値
  • 直線の数(平行や垂直なものがあったらプラス)
  • k-meansの結果の一番明るい領域についての面積/周長比
  • 明るい領域に囲まれた暗い領域があるか(窓の検出)

過学習については特に考えず単純に全部のデータを使って訓練。

あれだけ少々のコードで学習できるとはパーセプトロンって面白い仕組みですね。


やらなかったこと
  • 画像の特徴量としてはSIFTとかSURFとかがトレンドぽかったけど、特許に保護されてて商用には使えない云々とあったので避けといた
  • 乗り物に特徴的な色の情報を見る方針もありかとはちょっと思ったが、訓練集合に出てくる乗り物のインスタンスに依存してしまって激しく過学習になりそうだったのでやめた(けどそんなこともなくてその方針で良かったみたい)
  • SVMは名前しか知りません。…勉強しよう
  • 画素値はRGBじゃなくて他の表現に直した方が良いかも、と思ったが手が回らなかった。彩度が重要そう←彩度じゃなくて色相の間違い

結果と感想

  • 暫定スコア:0.77(1.00が最高)
  • 最終スコア:713.41(1000.00が最高)
  • 順位:24位/139人
  • レート:2078->2010

もっと過学習でスコア下がるかと思ってたがそこまででもなかった。

与えられる画像の画質が悪かったので、エッジ検出や領域分割をやろうとしたのはあまり賢くなかったかもしれない


最初から予想できていた通りレーティングは落ちたけれども、コンテストを通していろいろ勉強できたという点では過去最高の回でした。

 |