いうのは置いておいて、測定方法をどうするかまず考えました。精神状態に左右される、時間内に数えられる量に限度があるこの中で現実的なのはカメラで画像撮ってがんばるくらいですよね。いうことで画像処理に決定。複数枚の画像撮ってサイコロのマッチングしよう、特徴量抽出がどうの、エピポーラ幾何がどうの、オプティカルフローがどうのって話が賑わっていた記憶があります。自分は編入試験の勉強で全く動けませんでした。他の2人にはサイコロを各大きさ500個ずつ購入したり、サイコロを撒くテーブルを作ったりしてもらいました。テーブルに敷くピンク色のカーペット、4枚で足りるのに沖縄高専は200枚も買ったりしたらしいです!。7月ようやく本格的に動き出しました。SIFTとかSURFとか使えるのかなーとか色々やってみたり...調査が一段落した後、取り敢えず1枚の画像から見えるサイコロの個数を計算するプログラムを作成しようとしました。その前段階としてサイコロの目を検出しようと思い画像にCannyのアルゴリズムを用いてエッジ抽出するエッジ情報を、同じ楕円を構成しているもの別に頑張って分ける(実際はただの8方向隣接ピクセルを見て繋がってるピクセルにBFSするだけ)最小二乗法を用いて楕円の方程式のパラメータを算出するという感じでしました。実装にはOpenCVを用いました。上記の実装は主にhetare09君にやってもらい、自分は主に幾何ライブラリを作りました。ベクトルや直線や円や楕円を扱えます。多機能!作った幾何ライブラリはhttp://ideone.com/ZI2Lgから見られます!。8月nikollsonが1ヶ月東京に行ってしまい居ませんでした。hetare09君が後半半月SuperConやJOI夏合宿に行ってしまい居ませんでした。夏合宿うらやま!!!!その間自分は、Canny法によるエッジ抽出がサイコロの目の反射光に弱いとか色々あったので、エッジ抽出の方法を独自に考えたりしました。説明はけっこう面倒なので省きます。隣接ピクセルとの差を見てます。あるらしかったんですが、なんかそういうのを新しく勉強する・実装するのに工数を割きたくなかった(本質ではないと思った)ので諦めました*1。前半は定期試験があったので取り組みませんでした。後半はnikosllonが工場見学旅行でいませんでした。hetare09君には、「僕の考えた最強のエッジ抽出法」を使って楕円抽出の精度向上をやってもらっていました。最強じゃないし、全然エッジ抽出法じゃないけどね!。自分は、抽出した目情報から、「同じサイコロの同じ面に属している目であるだろう」とおもわれる目同士を線で結んでみるプログラムを作ったりしました。「同じサイコロの同じ面に属している目であるだろう」の判定は、二つの楕円の中心座標を合わせて重ねた時にその共通部分の面積が全体に占める比率を頑張って積分して求めてどうのこうのしてました。楕円同士の交点計算とか、死ぬかと思ったよ。自動でカウントするのを諦めました☆カメラで画像を撮った後コンピュータに取り込み、マウスとキーボードを用いてひたすら人力で数えるとってもアナログな手法に切り替えました。例年久留米は基本全自動でやってきていたので、本当は最後まで人力に頼りたくはなかったのですが、何らかの方法で見えるサイコロの個数を正確に数え上げることができても、結局真のサイコロの個数は結局分からず推測せざるを得ないため、あまり意味が無いと思ったためです。画像処理をこのまま続けても実りそうになかったし、そこに工数を割くぐらいなら推測の方に力を入れたかったので。手動で行くと決まったからには、インタフェースは徹底的に。カウント支援ソフトを作りました。なんと1台のPCにマウスを2台接続して2人が同時にカウントできます!すごい!あとは指定領域に指定した割合でサイコロのカウントをコピペする機能とかいろいろつけました!。クロスケーブルも買ったんだけど結局コンピュータ間の通信機能は間に合いませんでした。久留米高専では、恐らく本戦では推測の精度で順位が決まると考え、サイコロの数や比率をいろいろ変えたサイコロ画像180枚に対して、「サイコロ数え上げパーティー*2」を行い、部員達の力を借りて見えるサイコロの数を大中小それぞれ数え上げ、それを基に「見える大・中・小サイコロの数・重さ・比率」を基底(入力変数)として重回帰分析を行い係数を決定し、本番に臨むことにしました。重回帰分析はExcelで出来るんですけど不便だったので最初はmatlabでプログラムを作成し、それを後にC++に移植しました。matlab便利すぎ・・・こんな風にデータまとめてこんな風に分析しました。10月に入ってからは自分とhetare09君でほとんど毎日Excelとにらめっこしてました。「エクセルコンテスト」「確率統計コンテスト」「データマイニングコンテスト」とかそんな名前のコンテストに参加してる気分でした。それでも精度は少しずつ上がってきて、本番直前に行った予行演習では誤差が大0、中2、小20くらいまでは縮めることができました。(小サイコロは本当にずれるので、最大で誤差率±30%は普通にあったかと思います)。ところで、この時点で行なっていることをよく考えると手動で見えるサイコロの数を数える事前に重回帰分析により算出したパラメータを用いて、真のサイコロの個数を推測するですよね。「見えるサイコロの数」をインプットとして与えると、「真のサイコロの数」がアウトプットで返ってくる。これ、よく考えると、別にインプットを「見えるサイコロの数」にする必要はないように思えませんか?例えばコンピュータで抽出可能な量・・・何らかの特徴量だとか、サイコロの目の大きさの分布だとか・・・その事実に本番1週間くらい前に気がついた久留米高専は一部自動に翻り、SIFTの検出ウィンドウの大きさの分布を使ってみたりーだとかサイコロの目の大きさの分布を使ってみたりーだとかを主にnikollsonがしました。サイコロの目の大きさは、ヒストグラムを作ると中サイコロと大サイコロの所で結構くっきりとピークが現れる二峰性のグラフになっていました。こんなにくっきり現れるのか・・・と割と感心してました。後はピークの間の谷のところで2つに切って大と中それぞれの大きさの目の数だと思われる数値を得てそれを入力にしてまた重回帰分析すればいいよね(・∀・)(小サイコロは重さから求めます)それで前述した180枚の画像データに対して、目の大きさのヒストグラムを作ってみたりしたんですが......同じ個数の山でも、撮った角度等の要因で容易に割合が変わってしまうことが発覚してしまいました。これでは分析できないよ・・・えーん・・・というわけで一度翻った自動解法は再び下火になってしまいました(フラグ)。なんと、サイコロを撒いた後、手でサイコロの山をならしていました!。「サイコロは自然に散らべ、手で並べたりはしない」と言ってたのに...と思って2度くらい運営に質問と抗議に行きました。結果、サイコロには極力手を触れないことになりました。久留米の予行演習は上手く行きました!。一眼レフカメラのバッテリーが切れました!。目視で頑張りましたが限界があった。1日目夜1日目で運営のサイコロの撒き方が分かったので、その撒き方で30枚の写真を撮り重回帰分析を行いデータを作り直しました。それと色々な高専から1回戦の画像データを譲って頂き、それらについても分析をかけました。(それと協力して下さった福島高専)の方々ありがとうございました。この場を借りてお礼申し上げます*3。敗因は割とはっきりしていて、「実験データとの明らかな不整合」です。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:大阪府立高専からも貰いたかったけど彼ら競技終了後懇親会も出ずにすぐに帰って寝てたんだよねえ...。