decode

技術ブログ 本の紹介

第27回全国高等専門学校プログラミングコンテストに参加しました。

こんにちは、kawasakikouです。

今回全国高等専門学校プログラミングコンテスト - Official Siteの競技部門に参加してきました。

結果から言うと参加して良かった面が半分、悪かった面が半分ずつありました。

競技内容

一枚の板をn角形(n<32)にレーザーカットし、そのパズルを制限時間内に組み上げる。

プログラムを使っても使わなくても可。

勝利条件は

  1. 枠内に収まったピース数
  2. 回答時間が短い

という感じ

良かった点

レギュレーションからのアルゴリズム選択の重要性に気づけた

今回のレギュレーションは、完全回答が最強である。

だが全ピースをスキャンして実際に組み上げる事を考えると、完全回答を出すまでに10分以上かかると思ったので、人力の補助をしようと考えた。

人間は少し時間はかかるが完全回答できるので、人間の判断力とプログラムのサーチスピードでいけると思った。

だがこれが完全に失敗で「一番大きいピースを枠に当てはめずに適当に並べ、素早く提出する」に勝つためには「人間の評価関数+プログラムのサーチ」じゃなくて「プログラム完全回答」しかなかったのだ。

だから今回のレギュレーションを見た瞬間に考えるべき戦略は「いかに素早く誤差なくピースをデータ化し、完全回答をプログラムで完成するか」だった。

数学って大事だと実感した

私は今まで画像処理をした事が無かったので、とても勉強になった。

ピースの頂点を取るのに最小二乗法で直線を求め、直線と点間の距離を出す、データ上でピース合成する時に授業で習った様な回転移動を使う、 atanの条件がめんどくさい、二点間より三点間の角度の方が考えやすいなどなど数学の大事さが学べた。

人力に負けてたまるかという気持ちが比較的落ち込まずに芽生えた

他のチームの殆どが全自動で完答していて、私達のチームだけできていなかったらわりと辛かったというか、切腹だったと思う。

だが、他のチームも大体は人力で、自分の罪は軽いまま、「コンテストに出る場合には何があっても完全を目指すべき」という事が学べた。

問題を見たときにどういう応用があるか考えろって教えて頂いた

舞鶴高専の井上先生に、試合終了後「こういう問題をコーディングするときに何を考えるべきですか?どうやったら次この問題が解けるようになりますか?」と訪ねた所、 「このパズルは他にどういう応用がされているか考えて、それを真似するのは結構良いかもしれない」と教えて頂きました。 例えば遺跡の修復で多角形を埋めるだとか、チョコレートの割れ検出だとか。 帰り道に大阪城によったらすごい今回のパズルっぽい城壁があって興奮しました。

論文を読むべきだと教えて頂いた

うちの校長先生にも「次こういう類の問題が出た時どうすればいいですか?」と聞いた。 すると、「海外のプロコンで一度、高専プロコンに似た様な事例ががあった。その時はアメリカの論文のアルゴリズムを使ったチームだけが問題を解けて圧倒的に優勝した。日本チームも出ていたが、その論文のアルゴリズムでは無かったため惨敗だった。だから問題に則したアルゴリズムを論文でもなんでも探して実装することが大事だよ」と教えて頂いた。感動。shift-algorithmを初めて実装したらしい。(OpenCVに入ってる特徴点抽出のあれ)

一人でコード書くのは寂しいと実感できた

夏休み前に役割分担していざ夏休みに入るとチームメンバーとあんまり連絡が取れなくなって夏休みが終わると自分しか作業してないみたいな最悪の状態だった。別に作業量がじゃなくて何故かすごく寂しかった。結局ほぼ私一人で書いたが。

実は今までにこれの逆の立場を経験していて、コーディングリーダーが殆ど完成させて他のメンバーがそれに追従する案件があった。 その事自体はあり得る話だが、それを当たり前かの様に思い私より年上の方が「リーダーが書き終わったらそれを真似します」と言っていたのを真に受けて中盤までリーダー以外何もしなかった事があった。本当に自分は何をしていたんだろうと悔やまれる。実力がないなら無いなりにやれよと過去の自分に思う様になった。

色んな人に会えた

プロコンのお誘いが長友(デーリィ長友チームリーダー)から来たときに出ようと思った理由が知り合いに会えるのでは無いかというものだった。

らりょす氏に会えたし(一番うれしかった)、高専ベンチャーのうみさまと澤木さんにも会えたし、校長先生の紹介で井上先生にも会えた。 これでなんとなくスッキリした。

悪かった点

クソほど面白くなかった

コードを書くのは楽しかったが、いざ試合すると全然盛り上がらなかった。ロボコンが羨ましい。

高専ベンチャーのお偉い方曰く「なんか競技より課題自由の方が好きだわ笑」らしい。

試合時間が短かった

私達は誤差を減らすことが第一だと考えていたのでスキャナでスキャンして表面のみの二次元解析を行なった。

だが、全ピースをスキャンして、ピースと辺にナンバリングするだけで少なくとも5分はかかった。

せめて10分じゃなくて15分がよかった。

電源がないってやる気あるん?

UPS持ってったけどそれっている?

競技って企業賞なんでないん?

ねぇなんで花形とか言ってる割に閉会式で競技に触れないの?なんで企業賞ないん?東京高専にあげたいわ。

レッドブル一年分とか自由課題じゃなくて競技にあげるべきでは?初めて出場したのでびっくりした。

外野がうるさい

出て無い人達うるさすぎ。

私は出て学べた事がある(今後どうするか考えるいいきっかけになった)のに競技内容で貶さないでほしい。

クソって言うなら参加しないようにしたら?とか全員そうと決めつけないで欲しい。

企業の協賛がどうとかは競技部門に全く関係ない(協賛は課題自由にしか関わってないのが腹立たしい)ので叩かない方がいいと思う。

自分の競技に対する解法

今回の競技は大きく3つに分割できます。

  1. ピースのデータ化

  2. 隣り合うべきピースの探索

  3. ユーザインタフェース

ピースのデータ化

まずピースは物体なので何かしらデータ化をする。

今回の競技の隠しヒントとして、側面の焦げ目がある。

図1. 側面の焦げ目

図2. 側面の焦げ目を面につけて回答した例

これが結構な確率でピッタリ回答に合うため、これをプログラム的に考慮する必要がある。 この焦げ目に垂直な表面に赤い線で印をつけ、与えられたピースをA3スキャナでカラースキャンする。 その画像をラベリング法でそれぞれのピースを矩形に切り取り、ノイズや、他辺の混入を除く。 この時赤線の座標もOpenCVが出してくれるので分割した座標に変換する。

分割が終わったら、この作業で切り取った各ピース画像のピースの頂点座標を求める。 OpenCVにfindContoursという輪郭抽出ができる機能があるので、ピースの周囲点の配列を元に、 点の集合を最小二乗法して、直線の式を近似する。 この近似した直線と、次以降の点の垂直距離を図り、5mm以上点が離れていたら頂点と判断する。

f:id:kkou0801:20161013015612g:plain 図3. 最小二乗法と直線と点間の距離を用いたピースのcorner検出

取得した座標を基に、それぞれの辺の長さ、角度を求める。 辺の長さはこれ

2点間の距離の公式

角度はこれ

3点からなる角度を求める 画像処理ソリューション

で、三点間の角度を求めるのだが、三点間の角度は180°以下の方の角度が出るため、角度が多角形の内側かどうか判定する必要があった。 図3. 多角形の三点間の角度のパターン一覧

やり方としては、一点を挟む両側の二点の中点と、挟まれた点の平均をある範囲まで再帰的に取っていき、その点が図形に含まれているかどうかを判定する。 何故一点を挟む両側の二点の中点だけではダメかと言うと、図3の下の例がうまく扱えないからだ。 OpenCVに任意の点がfindContoursで出した周に内包されるか判別するpointPolygonTestという機能があるのでそれを用いた。

隣り合うべきピースの探索

辺の長さと角度の情報を基に、

  1. 辺の長さが1:1かつ合成時の角度が180になるような ピースを最優先で探索する。
  2. 二つのピースの辺の長さが 1:1
  3. 1:n かつ 180°
  4. 1:n のみ
  5. n 個の角を足すと 180°

と、次第に条件を緩くした。 この時、条件に一致するピースを基にしてネットワークグラフを作成するとともに、全ピースをたどるよ うに探索しようとした。しかし、この方法では、全ピースを枠に当てはめる際、組み合わ せ数が爆発的に増えることが考えられる。

組み合わせ数が膨大になる原因は、当てはめたピースが確実に正解しているのかどうかが分からない点である。 よって人間が正誤判定をし、その補助として長さ、角度の計算や、ピース同士の比較などをやってもらうことが最善ではないかと考えた。

ここで探索をしっかりやっとけばよかったのにとすごく反省している。 ネットワークじゃなくて木構造で枠の端からビームサーチが普通らしい。

ユーザインタフェースとピース合成

最後には現実のパズルを人間が組む必要があるので、ユーザインタフェースが必要。 現実ピースにペンでナンバリングして、私達は最悪な事にピースを合成していけるまでいって埋まらない部分は手動を考えてたのでこんな感じになった。

表示された候補の、ピースとピースを現実世界で実際にくっつけた時、それが正しい組み合わせかどうかを人間が判断する。 人間が見て正解のようであれば、ピース合成の確定処理を実行する。ここでの合成とはデータ上でのものであり、各ピースで求めた 座標を平行、回転移動させることで、新たな一つのピースとして座標、長さ、角度を導く。 この新たなピースを再び候補にいれることで新しいピースと条件が一致するピースを再び人間が正誤判断する。 これを繰り返す途中で、人間が見て明らかにおこりえないピースの組み合わせの場合、合成したピースの中の一つを分解する処理を行う。

まとめ

私は参加して良かったと思う。 校長先生(運営)が言っていたが、ただ単に富豪プログラムで優勝できるレギュレーションには高専プロコンはしないと言っていたので、頭をつかう必要があったなぁとしみじみ考えさせられた。次からはどんなコンテストに出てもプログラム完結で更に効率を良くする事に注力したいと思った。 来年は8月に受験だが、都城高専の夏季休業が9月からという情報が入ったのでワンチャン来年もありか...??と考えている。