沖縄高専とプロコンとサイコロとわたし。

最初に

こんにちは。沖縄高専ICT委員会委員長、高専プロコン競技部門に参加したなっちゃん(@marin72_com)です。とにかく長いです。思っていることをひたすらに全部書きます。高専プロコンの今年の競技部門の内容を知っている体で書きます。先にかがみずのブログとかなとりうむさんのブログを読んでもらえると助かります。

私達沖縄高専競技部門は、完全に画像処理で今回の競技部門に挑みました。画像処理のアルゴリズムについて知りたいのならば、真ん中の下あたりの「沖縄高専の画像処理内容」から見てください。

沖縄高専の結果

競技部門＞1回戦進出、2回戦敗退

自由部門＞特別賞、エグジットチューンズ特別賞

課題部門＞優秀賞、NICT賞(起業家甲子園の参加資格)

結果から言うと、本当に凄いことだと思います。沖縄高専のプロコンの歴史史上最も良い結果を収められました。今年はICT委員会総出でがんばったからなのかなあとかも思いました。

では、まず私が委員長を務めるICT委員会からの説明をします。

沖縄高専のICT委員会

Imformation Communication Technologyの略であるICT委員会は、主にプログラミングのコンテストに出るために日々切磋琢磨をしてプログラミングに励んでいます。委員会という名前ですが、やってることは他高専のプロコン部と一緒の部活です。部員集め用に作成したICT委員会の説明がこちら(pdf)です。

昨年からぴんく(@pinkroot)先輩が部活に参加して大きくICT委員会は変化しました。今まで競技部門しか出ていなかったけど、ぴんく先輩をリーダーにして自由部門を出すことに挑戦したことが第一の始まりです。自由部門ではマイクロソフト賞(企業特別賞)を受賞しました。その後、ぴんく先輩の影響で部員の意識はとても変わりました。今まで沖縄高専は競技プログラミング中心のプログラミングコンテストに出場していましたが、androidアプリやwebサービスなどの開発面、ビジネスアイデアコンテストに参加して優秀賞や特別賞を受賞したりいろんな方面にICT委員会の活動が広がっていきました。今年は新入部員もたくさん入って、とても賑やかな部活になっています。昨年度までの沖縄高専の活動はこちら(沖縄高専ウィキ)から。

わたしは顧問の指名によりこのICT委員会の委員長を昨年からしています。

沖縄高専と高専プロコン

先述した通り沖縄高専は競技プログラミング中心だったため、沖縄高専のプロコンのICT委員会としての自由部門・課題部門の歴史は浅いです。沖縄高専は一昨年まで、「ICT委員会が競技部門、自由部門・課題部門は出場したい学生が出る(ICT委員会関係ない)」という状態でした。先ほどのこちら(沖縄高専ウィキ)ではICT委員会の活動にプロコンの活動をすべて書いているため、自由部門・課題部門も記述しておりますがあれはICT委員会に所属していない方が頑張って受賞した結果です。昨年の課題部門もICT委員会には所属していない方で結成されたチームなので、ICT委員会として高専プロコンに3部門出たのは初めてです。出場が決まったときは本当に嬉しかったです。

過去の高専プロコンとわたし

1年生の時から競技部門に参加しており、今年で3度目の競技部門です。競技部門は3人しかメンバー登録ができないため3人で開発しているところも多いですが、沖縄高専は3人+2人が大会に参加します(現地に来るという意味)。

1年生の時に参加した理由はただの運です。行けない人がいたので、行く人居ないから行く？みたいなノリです。メンバーは4年(1)、3年(2)、2年(1)、1年(1)です。2010年のルールの説明は省きますが、通称水瓶です。行くまでは特に何もしていませんでした。ただ水瓶の全座標を覚えた程度。これ何？って聞かれたらすぐに答えられるようにはした、というだけです。現地ではマップを作って実験したり、先輩にプログラムを書かせたり起こしたり励ましたり。プログラミングとは関係ないことをしていました。しかし、この行動・雰囲気を見て顧問はわたしを委員長にしたらしいです。結果は1回戦敗退、敗者復活戦敗退で残念でしたが、初めてプロコンに参加して興奮していたのを覚えています。

2年生では委員長だし昨年参加したし、という理由から競技部門の登録メンバーに。メンバーは3年(1)、2年(4)です。私はこの時昨年の感動を忘れてプログラミングをしていませんでした。この年も一行もソースを書いていません。マネジメントが仕事だったはずなのにそれすら全然できていませんでした。夏休みに動いていたはずのシステムもいざ直前に動かそうとすると動きませんでした。プロコンが始まってもシステムは動きませんでしたが、なんとか1回戦を勝ち進むことができ、準決勝敗退でした。ホテルで一緒にデバッグを手伝いましたがわたしがやったことはそれだけで、この結果は先輩や同級生のおかげでわたし自身なにもしていないです。緊張もしなかったし、今考えると悔しいなんて気持ちはなかったのかもしれません。

今年の高専プロコンとチーム

今年はルールを見てみんなが嫌がりました。それでも競技部門が出ないわけにはいかず、なんとかチームをつくりました。(少し意味のわからない単語もありますが、後々説明します)

●わたし(@marin72_com)

担当：リーダー(元はマネジメントだけの予定だった)、黒の2値化(black)、黒と赤とアルゴリズムの全体の管理(takt)

●にゃおちゃん(@Orisano)

担当：赤の2値化(red)、UI・全体の管理(harmony)

●かがみず(@kagamiz)

担当：黒と赤の2値化からどうやってサイコロの個数を求めるか(piano, forte)

とりあえずこの3人が登録メンバーになり、ほとんど3人で開発をしていきます。その後、1年生を何人かサポートメンバーにつけ(この段階ではまだ誰を連れて行くか決めていない)、サイコロとの戦いが始まります。

 

 

競技部門の開発の流れと感想

4月

メンバー決めをする。みんなやりたがらなくて結構たいへんだった。

5月

いつの間にか5月じゃんってなる。サイコロの目からサイコロを求めようとする。サイコロの2〜5の目を取る

ため黒の2値化を私、1の目を取るため赤の2値化をにゃおちゃんが主にやることになる。かがみずは何か他のアプローチを考える。

6月

赤の2値化はほとんど完成する。

7月

同様。エッジ検出とかやる(結局使わなかった)。テストにより開発がストップする前に、「黒の2値化でサイコロの目以外の影を排除する」という目標を決める。テストが来て開発がストップしてしまう。目標が達成できなかった。

8月

会場に来てもらう1年生を決める。プロコンに間に合うか不安になる。沖縄高専は本当に田舎にあるため寮生は学校に来ることが困難でかがみずが学校に来れなくなり、にゃおちゃんがITFrogsで忙しくなり、私しか学校に来れなくなる。8/25〜わたし・かがみずはJOIssに参加し、にゃおちゃんはITFrogsでシリコンバレーに行く。1週間以上開発止まるし、だいぶやばい状況になる。APIとかをやっと決めた。

9月

もう1ヶ月しか無いし、本当に危機を感じる。にゃおちゃんもITFrogsが落ち着いて("なんとか落ち着かせて"の方が正しい)、合宿が始まったおかげでかがみずが学校に来れるようになり、直接コミュニケーションを取りながら開発をするようになる。ここからどんどんみんなで作れていけた感じがする。SURFとかSIFTとかやばいねーってなる(結局使わなかった)。にゃおちゃんにUIを頼む。9/14に"画像を投げて答えを返す流れ"をとりあえず9/31(金)に作る目標を立てる。無事にできる。けど、黒の2値化もまだまだ影を排除できるし、そのせいでアルゴリズムがうまく動かず解がおかしい。次の目標として10/9までは"バリバリコードを書いて、そこからは調整をしよう"を立てる。部員全員を競技・課題・自由部門に振り分けて、お手伝いをしてもらう(これはICT委員会史上初めてのことである)。ICT委員会全員で開発！という雰囲気になる。

10月

10月の頭からはサイコロを1年生に並べてもらい、それをにゃおちゃんが数えることを訓練する。要するに人力。もし画像処理ができなかったら沖縄高専も人力の予定だった。精度にむらがあるためやっぱり画像処理がんばろうって思う(一度だけ大中小全部当てたこともある)。部活の時間ではサイコロを人力でやって、家では画像処理を書くというスタンスになる。にゃおちゃんにアドバイスもらったりして黒の影の処理がどんどん良くなっていく。精度が良くなっているのか悪くなっているのか黒の点を見すぎてわからなくなっていく(にゃおちゃんに確認しながら開発していた)。かがみずのアルゴリズムが安定していく。10/9までにある程度の黒ができて、ある程度のアルゴリズムができ、ある程度の解を返すシステムが出来上がる。

プロコン前日(金曜日)

ある程度の解だしやばい。黒の2値化もっと追求する。かがみず寝る。にゃおちゃんにぶつかってしまう。にゃおちゃんと一緒にがんばる。かがみず起こす。にゃおちゃん寝る。夜中4:30にかがみずのアルゴリズムで良い感じの解を出すver2.56ができる。ある程度の解から脱出！ver2.61とかまで作り、いつのまにか朝になる。

プロコン1日目(土曜日)

いろんな人に会う。予行練習ギリギリまで書いて実験を繰り返す。ver2.56がいいことに気づく。ver2.56じゃなくてver2.55を組み込むというやってはいけない間違いやnot foundバグのせいで予行練習では4位になる。昼食後30分ほど寝ている間にver2.56の間違いに気付いてくれた2人が組み込み直し、1回戦に挑む。小のサイコロだけは誤差が酷いので人間補正をかける。パンフレットでは「最後に人間補正が〜」など書いているので、パンフレットまんまである。結果は2位通過。単純に嬉しい。この日は仲間の優しさで5時間ぐらい寝かせてもらう。

プロコン2日目(日曜日)

競技の連絡者会議はにゃおちゃんにお願いし、黒の最終調整を行う。府立も久留米も敗者復活戦で負けてしまって悲しかった。本番は画像処理のみで解を出す。小のサイコロをにゃおちゃんに数えてもらっていたけど、画像処理の解のまま提出(まったく人間の補正をしなかった)。一瞬で解が出て暇だからピースをしたり片付けをしたりする。4位になってしまい、敗退決定するけど終わった後は本当にすっきりしていた。自分のできることは全部やった気分。

 

 

沖縄高専の画像処理内容

ここがたぶん気になる方多いと思います。沖縄高専はパンフレットを90%実装しただけという感じもしますが、できる限り説明します。

画像の入力 

調査エリアに入る人はわたし：カメラで撮影担当、にゃおちゃん：もしも用で小のサイコロを数えてもらう。ブースはかがみずが画像処理をPCにさせる担当でやりました。わたしが撮影した画像をSDカードを使ってPCに入力させるのですが、にゃおちゃんのおかげでSDカードの画像を自動で入力してくれる。超楽。これが第一の時間短縮。画像は毎回同じ倍率で同じ範囲分を取る(ここ重要)ため、画像の要らない部分をカットする。これを2値化していく。

図1:UI全体図。左下の上界下界は人力用。分析を押すと図2が出てくる。(今回は参照しました)

図2:読み込みたい画像が左に出てくる。カットしたら右上にそれが出てくる(選ぶ前は一面灰色)

図3:切り取った画像
 

２値化

赤の2値化はにゃおちゃん担当でよくわからないけど、初めからだいぶ精度良い感じだったけど、練習の時にたまに悪くなったりするので注意が必要な感じです。今回の黒の2値化は私担当で、大津の2値化とか既存の2値化を使わずにイチから全部作ったので本当に本当に辛かったです。とにかく問題点が影でした。影が出てくる出てくる。

 

黒の２値化(詳しく)

黒の2値化は、画面全体から平均的な輝度をRGBの式(※1)により求めます。その後、100x100ずつに区切りRGBを利用し輝度のヒストグラムを描きヒストグラムの値が小さいところを探します。9300pixel以上固まってるところ・輝度が全体的に高すぎる・低すぎるところはキツめに2値化しますが、あとはかる〜く2値化します(今後はこの画像をただの2値化とよびます)。だいたいこのような感じで黒の目と認識したところを黒、その他は灰色にします。(※1 RGBで輝度を求める式 = 0.298912 * r + 0.586611 * g + 0.114478 * b)

図4:ただの2値化

このままでは影やゴミが多すぎて目の検出ができません。ただの2値化を2つの方法で更にキツく2値化します。1つめは、ただの2値化をHSVに分解したV(明度)の値で2値化します。この2値化は単純で、画面全体の平均的な輝度 * 0.8を閾値にします。もともと閾値は75で完全に定数だったのですが、本番環境では照明の関係でたまに酷い状態になるので平均的な輝度を利用して閾値を設定しました。

図5:ただの2値化+Hによる2値化

2つめは、ただの2値化の影をいろんな式に入れてキツめに2値化しました(と言ったら久留米と府立にもっと情報をくれみたいな感じだった)。ラベリングを用いて繋がっている黒の集合体を作り、この黒の集合体がひとつひとつ影か目かどうかを判定していきます(黒の集合体をareaとよびます)。

【条件1】areaのxmax(xの座標の最大値),xmin(xの座標の最小値),ymax(yの座標の最大値),ymin(yの座標の最小値)をもち、縦横比があまりにも大きいかどうか。

【条件2】areaと(xmax - xmin) * (ymax - ymin)の面積(長方形とよびます)の差が大きいかどうか。

【条件3】長方形を4分割し、黒がなさすぎる部分がないかどうか。

【条件4】areaが小さすぎ、大きすぎないか。 
この条件にいずれかにでも引っかかるとこのareaは影・ゴミと判定し、白(黒の目じゃない/画像的には灰色だけど)ということにします。

図6:ただの2値化+4つの条件を使った2値化
 

Vの2値化、4つの条件を使った2値化をORします。その後、また上記の条件を使い2値化をし、黒の2値化終了です。ちなみに、ただの2値化とOR後の画像の条件はやっていることは一緒ですが、条件の厳しさがところどころ違ったりします。結局うまくはじけずに大きめな影が残っていますが、今回かがみずのアルゴリズムではそういうのは大丈夫です(さすがにただの2値化状態のまま渡したら大変なことになりますが)。ただの2値化ではあった黒の目が消えていたりすることもありますが、小だけ消えることはなく、大も中も消えてしまうので大丈夫です。とりあえずわたしの範囲はこんな感じでした。

図7:最終的な黒の2値化終了
 

サイコロの個数を求める

それはかがみずのブログで説明してくれているので丸投げします。にゃおちゃんと夜中ひたすら実験を重ねてこれがいいんじゃないかこれはだめだとひたすら値を変え続けてなんとなく値がわかったので、今度はそれをかがみずに組み込んでもらって実際に良い解が出た時の感動は今でも忘れません。

ちなみにあの写真を切り取ったあとにある分析ボタンを押すと図8のようになります(時間は1秒かからない)。分析ボタンの上にある大中小のチェックボックスは、大のサイコロがないときにチェックをつけると中・小のみで値を出してくれます。

図8: 分析を押して解を出す

 

このアルゴリズムの大事なところ

先述した「同じ倍率で同じ範囲分を取る」というのは、 大中小のサイコロの目の大きさが毎回変わったら大変だからです。同じ距離から撮ることで大中小のサイコロを見分けていました。あとは、画像全体から平均的な輝度を求めることにより、学校のサイコロ環境(実験)に依存することはなかったです。実際撮影したところ、場所によってとても明るさが変わったので画像ごとに閾値が変えることにより2値化に成功することができたんじゃないかなあと思います。

 

 

実際の沖縄高専の競技部門

予行練習＞4位
1回戦＞2位(動画はこちら)

2回戦＞4位(動画はこちら)

という感じでした。教授が撮ってくれた動画があるのでアップしました(ustは結構見にくかったので)。とりあえず1回戦の終わりあたりで私が超喜んでいるのがわかると思うのですが、あのときは本当に嬉しかったです。あと2回戦のときに沖縄高専は解析時間に片付けていたのは余裕だったからではなく、ただ単に画像処理が一瞬で終わるため暇だったからです。舞台の上まで久留米や府立の方の「沖縄ぇ」みたいなのが聞こえました。2回戦が終わった後にわかったことは、redとtaktがあまりうまく結合できてなかったことです。もっと早く気づいていればよかったです。決勝行きたかったです。

 

沖縄高専競技部門の問題点

私達の問題点を箇条書きで書きます。(反省点)
●バージョン管理が酷い
●お互いが何をしているのかわかっていない
●もっと話し合うべき
●リーダーがリーダーらしくなさすぎる
●プログラムをくっつけるときはちゃんとみんなで確認するべき
●ひとつのアルゴリズムしか動いてない(例年)
●当日デスマしすぎ(例年)
当たり前のことかもしれませんが、これができていなかったなあとひしひしと感じました。来年に活かしたいです。 

 

 

今回のプロコン競技部門の問題点

今度は、私が感じたプロコン競技部門の問題点を箇条書きで書きます。あくまでも個人的見解です。
●人力で数えられるような個数を問題にした
●見えていないサイコロがあるのに、サイコロの総重量の誤差が大きすぎた

●1回戦・敗者復活戦・・・決勝になるにつれて毎年だと問題が難しくなるのに、今年はそんなに難しくなっていなかった
●サイコロが2種類しかないとき、テーブルと調査エリアの距離が変わるなどそういうのがなく、全部同じような試合だった。
●観戦者的には途中経過もないので、あまり楽しくなかったと思う
●サイコロの個数を入力するUIがテンキーを受け付けないめんどくさい仕様だった
他にも色々とあるかもしれませんが、わたしはこの6つを特に感じました。

 

 

プロコンが終わって

行く前はもう早く月曜日になってくれって気分だったのに、終わるときはあっさり終わってしまうし半年間の結果はこれかーとか思っていました。久留米と府立のアプローチがほとんど一緒でびっくりしたし、決勝のチーム全部人力ってことには本当に本当にびっくりしました。「人力とかずるい」「それってどうなの？」等は思ってはいません。それはその高専のアプローチで、結局決勝みんな同じことしてたみたいだし(インタビューではそう言ってたけど実際は画像処理をしかけてたところもあると思う)、まあ人力のほうが強かったってことだと思います。敗退が決まった時、いろんな人に応援してもらったし、にゃおちゃんとかがみずとまた舞台にのぼりたかった気持ちも強くあったけど、私ができることは全部やったし悔いはないなあとか思っていました。課題部門・自由部門賞がたくさん受賞してくれたので凄く嬉しくて、私達のぶんまで取ってくれた！とか思っていました。

翌日の福岡観光を終えて帰宅し、どこかでずっと考えていたモヤモヤがどんどん大きくなってきました。そのモヤモヤは、私がもっとしっかりマネジメントしていれば、余裕を持ってやっていれば、もっと解に近づいたんじゃないか、寧ろプログラムなんて書かずに沖縄高専も人力でやれば勝てたんじゃないか、委員長の私がいる部門だけ賞をもらえなくてそれってどうなんだろうなど考え、本当に悲しくて悔しくて思いっきり泣きました。だけど全くわたしのことを知らない人に「沖縄元気」「沖縄頑張れ！」とか言ってもらって、一緒に戦った久留米や府立の方には「沖縄凄く頑張ってたと思う」「沖縄の画像処理すごかった」「画像処理一本で頑張っていて輝いて見えた」とか言ってもらえて、今度は嬉し泣きをしてしまいました。今年のプロコンの競技部門は叩かれまくっているし私自身もこれはどうなのって思っているところは多々あります。人力でやればよかったのかーとか思っている人も多いと思いますが、私は「もっと画像処理を追求して優勝したかった」と思いました。競技中はSDカードを渡しにブースと調査エリアを走り回ったり、時間が余ったからピースとかしちゃって(実際は寝てない身体にムチを打って走り回っていた)、仲間を信じて画像処理のみで解を出したし、私は競技部門楽しかったです。私達は例年通り、仲間で開発をし、プロコンに挑戦しました。来年、また部員が変わるので私が競技部門に出るかわかりませんが、どの部門に出ても全力で頑張りたいです！

 

 

今後

沖縄高専、ICT委員会としてのプロコンはまだまだ始まったばかりです。「大きな柱であるぴんく先輩が居ないのだから来年の出場は2部門の方がいいんじゃないのか」等問題も多いですが、私はもっと修行を積み、更に後輩を育成していつか夢の3部門優勝できるように頑張ります。
長文でしたが、これでわたしのプロコンは終わりです。参加者・関係者・スタッフ・このブログを読んで下さった方ありがとうございました。