第23回全国高等専門学校プログラミングコンテスト
第23回全国高等専門学校プログラミングコンテスト・競技部門に参加してきました。
結果は、1回戦を突破して準々決勝での敗退でした。
この記事では高専プロコン本番での方針を説明していきたいと思います。
準備した方針
私たちが問題を読んで最初に思いついた方針は、連立方程式を解くものでした。大・中・小の3種類のサイコロのそれぞれの個数を変数としたときに3つ方程式が立てば連立方程式として解くことができます。まず重量に関しての式を立てることができるので、残り2つの式を立てられればこの方針を適用できそうでした。
方程式の候補として当初思いついたのは、画像処理によってサイコロの総数とサイコロがある領域の体積を求めることでした。しかし、小のサイコロが小さすぎて隠されてしまうためサイコロの総数を求めるのは難しそうです。また、体積を画像処理によって求める手段を考えたり調べてみたりしましたが、手軽にできそうな方法が見つかりませんでした。
代替手段として挙がったのが、大のサイコロの数とサイコロのある領域の面積を求めることでした。大のサイコロならば他のサイコロに隠れている個数は比較的少なそうです。面積も、体積に比べると求めることが比較的楽に出来そうに思えました。
大のサイコロの個数を求めるためには、機械学習を使用しました。OpenCVにはすぐに使える機械学習用のプログラムが入っています。サイコロのデータを用意し機械学習を行うことで、画像中の大のサイコロの個数を数えることができます（参考：http://gihyo.jp/dev/feature/01/opencv/0004）。私たちは大・中・小のサイコロが単体で写ってる画像や全てのサイコロが混ざっている状態の画像を数百枚用意し、手作業でサイコロの学習データを作成しました（ポジティブデータ：約7000件、ネガティブデータ：約3000件を作成）。また、学習データの作成中に少ないデータで試したところ、大のサイコロをポジティブデータとして中・小のサイコロをネガティブデータとするよりは、大・中をポジティブとして小をネガティブとしたほうが認識精度があがっていました。そのため、ポジティブデータに中のサイコロも含めるように方針を変更しました。
また、機械学習によるデータだけでは誤検出や検出漏れがあることが想像できたため、人の手によってクリックや右クリックでサイコロの数を数えるプログラムも作成していました。このプログラムは機械学習による画像認識の結果を使用することもでき、機械学習の補正として用いることを想定していました。
一方で面積を求める方法ですが、画像処理によって求めることは難しいのではないかと考えていました。というのも、サイコロが大量に積まれて山になってる状態やオブジェクトが大量にフィールド上にある状態だと、正しく面積を求めるためには補正を掛ける部分が多すぎると考えたからです。そのため面積を求めることは人の手によって行うことにしました。具体的には、次のようなステップで面積を求めます。まず、次のような画像を事前に用意しておきます。
この画像にWindowsのペイントを使って、サイコロの山をならして隙間なく敷き詰めた場合どのようになるかを想像して閉曲線を書き、塗りつぶします。
プログラムを使って、緑の円を直径90cmとしたときの黒で塗りつぶされた箇所の面積を計算します。この方法は閉曲線を書く部分に人の手が加わるため誤差が当然出てしまいますが、なるべく丁寧に描くことである程度実際の値に近いものが出せるのではないかと考えました。
以上の3つのデータ、サイコロの総重量、大・中のサイコロの総数、サイコロの置かれている領域の面積を用いて連立方程式を立て、それを解くことで大・中・小それぞれのサイコロの個数が出てきます。ただ、そのままだと小数や負数の解が出てきてしまいます。そのために、総重量と大と中それぞれのサイコロの個数を入力にとって、小のサイコロの個数を求めるプログラムを作成し、調整用に使っていました。
全部で５種類（機械学習による画像認識、人の手による数え上げ、面積の計測、連立方程式の求解、解の調整）のプログラムを用意し、高専プロコン本番に挑みました。
予行練習にて
時間が足りない！ カメラをPCとつないでも認識されなかったり、ペイントのツールが鉛筆ではなくブラシになっていたり、開始直前に表示されるサイコロの総重量をメモしていなくて焦ったりといったアクシデントもあったのですが、それ以前に操作することが多すぎました。私たちは２人チームだったので、相方がカメラで写真を撮って、その間にもう私がタブレットPCで概形を撮りその概形からペイントに領域を書くという分担をしてました。しかし、私が領域を描いてる間にカメラがやってきて、写真を取り込んだり画像処理を掛けたりしている間に時間がどんどん過ぎていき、あっという間に調査時間や分析時間が終わってしまいました（予行練習で全てに９９９９を送信したのは、実はこれが理由です）。
あまりにも時間が足りなかったため、私たちは解答データを作成するまでのステップを簡略化することにしました。まず、機械学習による画像認識をした後の人の手による数え上げをしないことにしました。これは、予行演習の２つのフィールドで撮った写真１枚での画像認識の結果が、実際の大・中のサイコロの総数の約３分の１になっていたからです。とりあえず人の手による数え上げをやめて、画像認識の結果の３倍を使うことにしました（もちろん、たった２つのサンプルでそう決めるのはどうかとも思ったのですが）。
また、画像認識自体も各フィールドにつき１枚だけで行うことにしました。３アングルから撮って１枚いちまい画像処理に掛けていると時間も足りませんし、そもそも３倍するという方針ならば複数アングルでする意味もないからです。
そして、準備してきたプログラムの５つ目である、解の調整に時間を多く割くことにしました。予行演習での結果を見ると、大・中・小のサイコロの個数の傾向（どれが多い、どれとどれが同じぐらい、どれが少ない）が分かっていると、解の調整のプログラムだけでも割と誤差の小さい値が出せていたからです。
１回戦にて
大勝利！ 解の調整プログラムに多く時間を割いたことで、誤差２桁を達成しました。もちろん他のプログラムも動かしていて、重量と個数と領域の方程式を解いて得られた個数を基準にして、大のサイコロの個数をいろいろ動かすことでそれっぽい値を出しました。ちなみに、分析時間の終了ギリギリで相方が中の個数がもうちょっと少ないと思うと言ってくれたおかげで、結果的に誤差が60近く減少してました。
その夜、ホテルでは他の１回戦の結果を分析してました。その結果気付いたことは、私たちのチームで重量に関する方程式に使っていた各サイコロの重量が大きかったことです。私たちが使っていた値はFAQで公開されていた平均の値である5.902、1.35、0.274だったのですが、この値で総重量を計算すると本番で公開された総重量に比べて20〜50g程度大きい値となっていました。むしろ100個の重量を100で割った値を使った方が、公開された総重量に近いようでした。
しかし、実は１回戦では総重量に比べて大きい値となることが良い方向に働いていたようです。分析してみると重量と個数と領域の方程式を解いて得られた大のサイコロの個数が、正解の個数より若干少ないものになっていました。丁度その分が総重量の多さを相殺していたようで、中と小の値がうまく得られたようでした。
また、他の１回戦のデータで解の調整用のプログラムを動かしてみたところ、サイコロの個数の傾向が大体わかっているだけでかなり誤差の少ない値（50〜70程度）が出せました。さらに、公開された総重量を10g増やしてプログラムを動かしてみると、さらに誤差が少なくなるようでした。そのため、準々決勝でも方針を変えずにいけるのではないかと考えていました。
準々決勝にて
敗者復活戦の結果を見ていると、やはり１回戦と同じように平均値を使って総重量を計算すると、公開された総重量よりも大きい値となっていました。この傾向が変わっていなかったので、方針も変えずに準々決勝に挑みました。
……が、結果は惨敗でした。目視で中と小のサイコロが全然見えず、解の調整のときに中と小のサイコロをかなり減らしてしまったのが原因でした。中と小のサイコロを減らすために大のサイコロを増やしていたので、大のサイコロが正解の個数より少ない、ということもありませんでした。この方針はサイコロの個数の傾向を読み取ることが非常に重要です。そのため、それを人間が読み違えるだけで致命的な誤差を生んでしまいます。後で確認をしてみると、私たちが見ていなかったアングルからフィールドを見ると、中や小のサイコロもそれなりに見えていたようでした。結局、人間の力とコンピュータの力をうまく合わせることができず、残念な結果になった感じです。
使用しなかった（思いつかなかった・試してみたけど諦めた）方針について
ここまで本番で使用した方針のことを書いたので、今度は逆に使用しなかった方針について書いていこうと思います。
1．サイコロの形の検出
サイコロは立方体の形をしています（当たり前ですが……）。そのため、平面に投影すると平行六辺形となります（四角形となるときもありますが）。線分検出をして平行な線分の組み合わせを見つけ、平行六辺形を構成できるか確かめられればサイコロの検出ができそうです。
ですが、試してみるとまず線分の検出がうまく行えず、平行な線分の組み合わせどころの話ではありませんでした。テストした環境の光源が弱いものだった、というのもあると思うのですがサイコロの形を得ることが全くできず、この方針は諦めました。
2．サイコロの目の検出
次に考えたのが、サイコロの目の検出です。サイコロの形に比べると、円あるいは楕円になっているサイコロの目は検出しやすいと思われました。しかし、実際にテストしてみるとOpenCVのHoughCircles()関数を用いた円の検出では全然目が検出されず、楕円の検出のほうも全然うまく検出してくれませんでした。そのため、この方針は諦めました。
……が、準々決勝が終わって他の高専の方針を聞いてみると、どうやら目を検出してそこから処理を行っているところがあるようでした。まだ他の高専のブログ等を読んでないのですが、どうやら目の検出は行えたようです……。
3．人力のみでの数え上げ
考えたけど、サイコロの数が増えたら全く通用しなくなるだろうと考えて切り捨てた方針です。準備段階ではサイコロが大・中・小で各1000個程度は来るだろうと考えていました。そのためやめていたのですが、今思えば試合が始まったときにサイコロの個数が少ないことは分かっていたので、すぐさま人力に切り替えるというのもありだったかもしれません。
4．サイコロの存在比
これは、私たちが思いつかなかった方針です。何のことかというと単純な話で「表面上にある大・中・小のサイコロの存在比は、全体の存在比に近いと予想される」ということです。パンフレットにも結構書いている高専がありましたね。優勝した宇部高専もこれを元にして計算していたみたい？ ですし、これを思いついた高専は多かったのではないでしょうか。
私たちはこの方針を思いつかなかったばかりか、この方針をパンフレットで見たときに「いや、小のサイコロとか隠れてることが多いだろうし、全然存在比は違うだろ……」とか言って否定していました。しかし、準々決勝が終わってよくよく考えてみると、小と中のサイコロを表面上の存在比からある程度増やしてやれば結構全体の存在比に近くなりそうです。これに気付いたときに、何で今まで気付かなかったんだと絶望しました……。
そして、優勝した宇部高専は人力で数えた結果に1.4や2.1などの事前に決めていた数を掛けて存在比としていた、ということを聞いてさらに絶望しました。有効な手法だったのに、全然気付かなかった上に否定していたのだ、と。全体の一部分を見て、その傾向を全体に適用するという方針はよくあること（乱択アルゴリズムのサンプリングとか）のに、気付かなかったことが悔しくてたまりませんでした。
感想
ここまで私たちのチームで使用した方針、使用しなかった方針について書いてきました。最後に高専プロコンに参加してみての感想を書いてこの記事を終わろうと思います。
まず何と言っても非常に悔しいです。準々決勝で負けたのも悔しかったですが、とにかく悔しいのは全然頑張れなかったということに対してです。存在比のことに気付くべきでした。画像処理をもうちょっと頑張って目の検出ができるようになるべきでした。もっと練習をして中や小のサイコロを見るようにするべきでした。人力によるカウントでどこまで戦えるか実験してみるべきでした。いろいろとできることはあったはずなのに全然頑張れていなかったこと、それがとても悔しいです。
多くの高専は、画像処理とか、実験とか、練習とか本当に頑張ってるのだろうなと思います。そして、今回私たちは（サイコロとマットの準備がなかなかできなかったというのもあるのですが）始動がかなり遅かった。３週間前ぐらい前にやっとサイコロとマットを買って、それから準備を始めました。そのため、全然準備ができなかった。来年も競技部門に出る予定なので、来年はもっと早くに始動して、準備もして、そしてもっと頑張って取り組もうと思います。今年や去年みたいな悔しさを来年は味わうことがないようにしたいです。
……というのが、今年の私たちの取り組みに対しての感想。次は問題や運営に対しての感想（文句？）です。
今年の問題は取り組みにくい課題だったと思います（サイコロやマットなど実費が必要という点で取り組みにくいというわけではありません。もちろんそれもあるのですが、ある程度しょうがないことだと思うので置いておきます）。何が取り組みにくかったかというと、問題の詳細な情報が全然公開されなかったことです。
まず、サイコロの個数。これの上限は（提出クライアントの仕様で各9999個以下というのは分かりましたが）ちゃんと公開するべきだったと思います。上限が各500個なのか、1000個なのか、5000個なのか、これが変わるだけで取り組み方が大きく変わってきてしまいます。
次に、オブジェクトについて。実際に使用されるオブジェクトについて情報を公開できないのは仕方ないとして、オブジェクトをテーブルの真ん中に置くこと（オブジェクトが複数あってテーブルの上に散らばされるということではないということ）は公開しておくべきことだったと思います。複数のオブジェクトをばら撒くものであった場合、これまた取り組み方が大きく変わってきてしまうでしょうから。あまりにもオブジェクトの情報が無かったので、私たちのチームはほとんどオブジェクトを無視して取り組んでいました。
次に、サイコロの捲き方。中央のオブジェクトの周りに均一になるように捲く、ということも公開すべきことだったと思います。どこかに山積みになるようにしたり、テーブルの端に意図的に山を作ったりということがない、というのが結構重要でした。というのも、均一になるように捲かれていると（プログラムも人間も）数を数えやすくなるわけですし、中央に捲くということはカメラを結構ズームして写真を撮れるということですから。
最後に、情報公開の仕方です。確か6月30日にFAQへの回答があって、そこで寄せられた質問に対しての返答をしていたと思いますが、正直遅すぎます。そのタイミングで初めてサイコロやマット、会場の照度などが知らされたわけですから。これらの情報は問題に取り組む上で必要不可欠な情報なのですから、FAQではなくて実施要項と同時に公開すべき情報だったと思います。
