プロコン行ってきた
全国高等専門学校 第23回プログラミングコンテストに参加してきました。競技部門に出場し、敗者復活戦で勝利することができたものの、その次の準々決勝で負けてしまいました。
この記事では、うちのチームのシステム構成と各試合でのようすについて振り返ります。
システム構成
うちのチームのシステムを紹介します。いつもはソースも上げているのですが、今回は自分ひとりで書いたわけではなく、後輩の書いたコードも組み込まれているので公開しません。
基本的な戦略
うちのチームは大会直前まで画像処理によるサイコロ検出を作っておらず、高い検出精度を実現できる自信もなかったため、画像処理では確実に検出できそうなサイコロのみを検出し、足りない部分を人力で補う手法をとることにしました。外側から見えない内部のサイコロをカウントするためのアイデアもなかったため、事前に似たような問題を解いておき、見えているサイコロの数と見えないサイコロの数の比を求めておいて利用することにしました。
サイコロの検出
サイコロの検出アルゴリズムは後輩に丸投げしていたのであまりよくわかっていません。一応本人に確認した概要を書いておきます。
- 撮影した画像を二値化し、白い部分を取り出す
- 白い部分をラベリングする
- 面積が極端に大きい・小さい領域を除く
- 形状が長方形でない領域を除く
- 正方形から遠い領域を除く
- 残った領域をサイコロとして認識する (大きさは長い辺の長さ)
こんなかんじで大きなサイコロは割と取れていたんじゃないかと思います。中くらいのサイコロも一部取れる場合がありましたが、さすがに小さいサイコロは無理でした。
アルゴリズムと人力の連携
見えるサイコロを検出してから見えないサイコロを予測するまでの間に人力で検出結果を修正しておく必要があったため、編集用のデータフォーマットを定義しました。といっても大したものではなく、ただの32bit PNG画像で、サイコロを検出した位置に●を印としてプロットしただけのものです。サイコロの大きさは●の色で定義し、赤を大、緑を中、青を小としました。
こんな感じの画像を撮影してきたとすると
検出結果 (を人力で調整したもの) は以下のような感じです。デカい点は手で打ったものです。
重ねるとこんな感じ。
PNG画像にしたことで、一般的なグラフィック編集ソフトで結果を編集できるようになりました。先ほど述べたように、画像処理でのサイコロ検出だけでは多くのサイコロを検出できずに漏らしてしまうため、試合時間の大部分はPaint.NETを起動して画像ファイルの編集を行なっていました。
見えないサイコロの予測
画像処理し、人力で修正したサイコロの検出結果をもとに、見えない部分のサイコロの数を予測し、最終的な回答を計算しました。求め方ははじめに書いたように類題から求めていて特に書くことはないです。何を持って類題とするかというのは問題ですが、今回はサイコロの積み重なり具合 (平坦に並べられているか・複数段に積み重なっているか) を目視で判断して判断しました。
各試合のようす
練習
回答を提出できず。練習不足、打ち合わせ不足、カメラがSDカードをなぜか認識しないなどが原因。
1回戦
当初は前と後ろの2方向から写真を撮影する方針だったが、練習で間に合わないことが確認されたので1方向だけ撮影することに。順調に答えを提出できたかと思われたものの、終了数秒前に答えがおかしいことに気付く。すぐに前日に思いつきで実装した機能の使い方を実装した本人 (私) が理解していなかったのが原因だと気付くものの、修正できず。
敗者復活戦
徹夜で改良、といったことはまったくなく、プログラム的には1回戦の戦犯機能を取り外したのみ。あとは試合での結果をもとに見えないサイコロを推測するためのパラメータを計算。これが大当たりし、メンバーの誰もが予想しなかった1位通過となった。
準々決勝
敗者復活戦から何も変更せずに突っ込む。真ん中のオブジェクトはどうでもよかったが、サイコロの積み上がり具合があまり都合がよろしくない。極度の準備不足であるうちのチームは適切なパラメータを持ちあわせておらず、大きな誤差を出して敗退。
アレな件ついて
いろいろ言われてますが、過去の問題もアレだと思うのが結構あったので今更かなという感じです。2008年に出ている私としては、相変わらず特定の個人に負担がかかりまくっている運営の構造のほうが深刻な問題だと思います。