全国高等専門学校プログラミングコンテスト有明大会

第23回全国高専プログラミングコンテスト・有明大会に、競技部門のメンバーとして@、@と参加してきました!

結果は…
一回戦4位/6チーム→敗者復活戦4位/6チームでしたorz(通過出来るのはいずれも上位2チーム)

問題内容

大・中・小3種類の大きさのサイコロが、テーブル上に沢山あります。サイコロ以外の物もあります。全体のサイコロの重さも教えます。それぞれの大きさのサイコロがいくつあるのか頑張って数えてね!
というルールです。
超端折りましたが、詳細なルールはこちら(PDF)の7ページ以降に書いてあります。興味が有る方は御覧ください。

あと割と大事なQ&Aで、こういうのもあります。サイコロは自然に散らべ、手で並べたりはしないらしい。

例えばこんな感じです。(クリックすると拡大します)

取り組んだこと

4月

問題が公開される。絶望する。


というのは置いておいて、測定方法をどうするかまず考えました。

機器 分かるもの メリット デメリット
カメラ 画像 機器の用意が容易、既存の画像処理アルゴリズムが使える 表面の情報しか読み取れない
ソナー 奥行き 超音波を用いることで表面の凸凹が分かる 機器が高そう
Kinect 奥行き レーザーを用いることで表面の凹凸が分かる 精度が全然出なさそう
X線CT サイコロの中の構造 全部のサイコロが見える X線作業主任者免許保持者がいない
扇風機&風速計 風の流れ 頑張れば山の中の構造が分かる? 流体力学こわい
ヒーター&サーモグラフィ 温度分布と熱伝導率 最悪発火する
手動 サイコロの個数 環境変化に頑健 精神状態に左右される、時間内に数えられる量に限度がある

この中で現実的なのはカメラで画像撮ってがんばるくらいですよね。
ということで画像処理に決定。
複数枚の画像撮ってサイコロのマッチングしよう、特徴量抽出がどうの、エピポーラ幾何がどうの、オプティカルフローがどうのって話が賑わっていた記憶があります。

5月、6月

自分は編入試験の勉強で全く動けませんでした。
他の2人にはサイコロを各大きさ500個ずつ購入したり、サイコロを撒くテーブルを作ったりしてもらいました。
テーブルに敷くピンク色のカーペット、4枚で足りるのに沖縄高専200枚も買ったりしたらしいです!。びっくりですね。

7月

ようやく本格的に動き出しました。SIFTとかSURFとか使えるのかなーとか色々やってみたり…

調査が一段落した後、取り敢えず1枚の画像から見えるサイコロの個数を計算するプログラムを作成しようとしました。
まずはその前段階としてサイコロの目を検出しようと思い

  1. 画像にCannyのアルゴリズムを用いてエッジ抽出する
  2. エッジ情報を、同じ楕円を構成しているもの別に頑張って分ける(実際はただの8方向隣接ピクセルを見て繋がってるピクセルにBFSするだけ)
  3. 最小二乗法を用いて楕円の方程式のパラメータを算出する

という感じでしました。実装にはOpenCVを用いました。
上記の実装は主にhetare09君にやってもらい、自分は主に幾何ライブラリを作りました。ベクトルや直線や円や楕円を扱えます。結構多機能!
作った幾何ライブラリはhttp://ideone.com/ZI2Lgから見られます!。

8月

nikollsonが1ヶ月東京に行ってしまい居ませんでした。
hetare09君が後半半月SuperConやJOI夏合宿に行ってしまい居ませんでした。夏合宿うらやま!!!!

その間自分は、Canny法によるエッジ抽出がサイコロの目の反射光に弱いとか色々あったので、エッジ抽出の方法を独自に考えたりしました。説明はけっこう面倒なので省きます。隣接ピクセルとの差を見てます。
論文を漁ると最小二乗法はあまり精度が良くないらしく、「最尤推定」とか「超精度最小二乗法」とかあるらしかったんですが、なんかそういうのを新しく勉強する・実装するのに工数を割きたくなかった(本質ではないと思った)ので諦めました*1

9月

前半は定期試験があったので取り組みませんでした。
後半はnikosllonが工場見学旅行でいませんでした。

hetare09君には、「僕の考えた最強のエッジ抽出法」を使って楕円抽出の精度向上をやってもらっていました。全然最強じゃないし、全然エッジ抽出法じゃないけどね!。

一方自分は、抽出した目情報から、「同じサイコロの同じ面に属している目であるだろう」とおもわれる目同士を線で結んでみるプログラムを作ったりしました。「同じサイコロの同じ面に属している目であるだろう」の判定は、二つの楕円の中心座標を合わせて重ねた時にその共通部分の面積が全体に占める比率を頑張って積分して求めてどうのこうのしてました。
楕円同士の交点計算とか、死ぬかと思ったよ。まじで。


最終的にこんな感じになったりしました!

10月

自動でカウントするのを諦めました☆



カメラで画像を撮った後コンピュータに取り込み、マウスとキーボードを用いてひたすら人力で数えるとってもアナログな手法に切り替えました。例年久留米は基本全自動でやってきていたので、本当は最後まで人力に頼りたくはなかったのですが、何らかの方法で見えるサイコロの個数を正確に数え上げることができても、結局真のサイコロの個数は結局分からず推測せざるを得ないため、あまり意味が無いと思ったためです。画像処理をこのまま続けても実りそうになかったし、そこに工数を割くぐらいなら推測の方に力を入れたかったので。
しかし手動で行くと決まったからには、インタフェースは徹底的に。まずはカウント支援ソフトを作りました。なんと1台のPCにマウスを2台接続して2人が同時にカウントできます!すごい!
あとは指定領域に指定した割合でサイコロのカウントをコピペする機能とかいろいろつけました!。C#さまさま。
クロスケーブルも買ったんだけど結局コンピュータ間の通信機能は間に合いませんでした。。


久留米高専では、恐らく本戦では推測の精度で順位が決まると考え、サイコロの数や比率をいろいろ変えたサイコロ画像180枚に対して、「サイコロ数え上げパーティー*2」を行い、部員達の力を借りて見えるサイコロの数を大中小それぞれ数え上げ、それを基に「見える大・中・小サイコロの数・重さ・比率」を基底(入力変数)として重回帰分析を行い係数を決定し、本番に臨むことにしました。重回帰分析はExcelで出来るんですけど不便だったので最初はmatlabでプログラムを作成し、それを後にC++に移植しました。matlab便利すぎ・・・

こんな風にデータまとめて

こんな風に分析しました。

10月に入ってからは自分とhetare09君でほとんど毎日Excelとにらめっこしてました。「エクセルコンテスト」「確率統計コンテスト」「データマイニングコンテスト」とかそんな名前のコンテストに参加してる気分でした。それでも精度は少しずつ上がってきて、本番直前に行った予行演習では誤差が大0、中2、小20くらいまでは縮めることができました。(小サイコロは本当にずれるので、最大で誤差率±30%は普通にあったかと思います)。
ところで、この時点で行なっていることをよく考えると

  1. 手動で見えるサイコロの数を数える
  2. 事前に重回帰分析により算出したパラメータを用いて、真のサイコロの個数を推測する

ですよね。つまり、「見えるサイコロの数」をインプットとして与えると、「真のサイコロの数」がアウトプットで返ってくる。これ、よく考えると、別にインプットを「見えるサイコロの数」にする必要はないように思えませんか?例えばコンピュータで抽出可能な量・・・何らかの特徴量だとか、サイコロの目の大きさの分布だとか・・・
その事実に本番1週間くらい前に気がついた久留米高専は一部自動に翻り、SIFTの検出ウィンドウの大きさの分布を使ってみたりーだとかサイコロの目の大きさの分布を使ってみたりーだとかを主にnikollsonがしました。サイコロの目の大きさは、ヒストグラムを作ると中サイコロと大サイコロの所で結構くっきりとピークが現れる二峰性のグラフになっていました。こんなにくっきり現れるのか・・・と割と感心してました。後はピークの間の谷のところで2つに切って大と中それぞれの大きさの目の数だと思われる数値を得てそれを入力にしてまた重回帰分析すればいいよね(・∀・)(小サイコロは重さから求めます)
それで前述した180枚の画像データに対して、目の大きさのヒストグラムを作ってみたりしたんですが……同じ個数の山でも、撮った角度等の要因で容易に割合が変わってしまうことが発覚してしまいました。これでは分析できないよ・・・えーん・・・というわけで一度翻った自動解法は再び下火になってしまいました(フラグ)。


そして、そのまま、本戦に挑むことに。

大会本番

予行演習

なんと、サイコロを撒いた後、手でサイコロの山をならしていました!。「サイコロは自然に散らべ、手で並べたりはしない」と言ってたのに…と思って2度くらい運営に質問と抗議に行きました。結果、サイコロには極力手を触れないことになりました。
久留米の予行演習は上手く行きました!。堂々の1位。

1回戦

一眼レフカメラのバッテリーが切れました!。
目視で頑張りましたが限界があった。敗者復活戦へ。

1日目夜

1日目で運営のサイコロの撒き方が分かったので、その撒き方で30枚の写真を撮り重回帰分析を行いデータを作り直しました。それと色々な高専から1回戦の画像データを譲って頂き、それらについても分析をかけました。快く譲って下さった東京産高専、沖縄高専、一関高専(それと協力して下さった福島高専)の方々ありがとうございました。この場を借りてお礼申し上げます*3

敗者復活戦

負けましたorz。
敗因は割とはっきりしていて、「実験データとの明らかな不整合」です。1日目夜の実験では、小サイコロは多くても全体の35%程度しか見えないし、実際にみんなから集めた1回戦のデータはどれもそうでした(一番ひどいものでは156個中20個、割合にして13%程度しか見えていないものもありました)。それが敗者復活戦では何故か、小サイコロが全体の60%は見えていたので、かなり大きめに答えが出てしまっていました。何故でしょう…午前中に行った競技なので、大中小のサイコロが混ざらずにバケツの中に入っていて(小サイコロが最下層)、大中のサイコロが転がった上に少サイコロがぱらぱらと降り注ぐことで飛び散る数が増えてしまったのかなとかも思いましたが、実際のところどうなのかは分かりません。あとやっぱ運要素はありますね。しょうがないね。

自動か?人力か?

twitter#procon2012タグ等でだいぶ荒れていましたね。
自分は、途中で手動に切り替えたことを後悔していませんし、実際に決勝に進んだチームは6つ全て手動でしたから、妥当な判断だったと思っています。大会に参加している以上は勝ちを取りにいきたいので。もちろん出来れば全部自動でやりたいですが、やっぱりどうしても人間の大局観*4やパターン認識力*5には、少なくとも今の自分では勝てるプログラムを作るのは厳しいです。問題解決の一手段として、時には潔く一部の仕事を人が請け負ってもいいんじゃないかとは思います。

今回の久留米高専の方針は、その変化まで含めて大阪府立高専と近いものだったようです。もっとも府立が手動に切り替えたのは大会前日らしいので、そのタイミングはだいぶ違いますが…。画像処理だけで答えを出そうとした高専も幾つかあると思うんですが、例えば沖縄高専は目の大きさのヒストグラムと重さから大中小のサイコロの分布を自動で算出し、かなりの精度を出していたようです(あれ?どこかで聞いたような…)。

高専プロコン競技部門として

今年の問題は確かにルールとして少し耐え難いものがありました。曲がりなりにも「プログラミングコンテスト」な訳ですから、ちゃんと優秀なプログラムを作成したチームが勝てるようなルールにして頂きたいですね。こんな状況を続けていたら、多分見放されちゃうよ?。決勝進出チーム全てがが手動解法に頼っていたというのは、問題作成時点で想定されてなかったのでしょうか?閉会式の審査委員長の言葉でも競技はノータッチだったし…。

どんなルールになっても、勝ちは狙いに行きますけど。でも今年もアルゴリズム考えてSSE書いてOpenMP使ってIntelコンパイラ使ってガチガチに高速化して、俺つえーしたかったなあ。最後だったし。

所感

優勝は宇部高専の方々でした。おめでとうございます。宇部は去年、1日目の夜にうちの解法をコピーして翌日準優勝したという猛者です。宇部さんやばすぎでしょ。
今回の大会は会場が大牟田だったので久留米から近く、部活のOBや後輩が沢山来てくれました。先生や友達からもfacebook等で応援メッセージをたくさんもらいました。だからせめて1回は勝ちたかった、かっこいいとこ見せてやりたかった…。運要素の強い競技内容とはいえ流石に情けなくなります。先生なんて「最強の布陣*6」とまで仰って下さったのに。うぐぅ。
nikollsonとhetare09君はまだ来年もあるので、優勝旗を(ないけど)是非宇部から奪還していただきたいです。もちろん府立や沖縄にも負けない。あと自由・課題も、久留米今は弱いけど、頑張って欲しい。
来年の開催地は北の大地旭川、絶対見に行きます。

久留米黄金時代、また作ろーぜっ

*1:最尤推定は研究室のゼミでやっていたんだけどね!。

*2:副題は「みんなも数え上げお姉さんになろう!」。

*3:大阪府立高専からも貰いたかったけど彼ら競技終了後懇親会も出ずにすぐに帰って寝てたんだよねえ…。

*4:平成22年度競技部門、水瓶の恵み。

*5:今年の競技。

*6:今まで3人全員がJOI春合宿参加者だったことはないんだけど、今年は自分とnikollsonはJOI春合宿参加したし、hetare09君は春合宿参加相当の実力があった(人為的ミスで失敗)ためだと思う。