全国高等専門学校プログラミングコンテスト2014 参加記

こんにちは、部長の唐澤です。 2014年10月18日から19日に岩手県一関で開催された全国高等専門学校プログラミングコンテストにチーム「人力の神話」として情研から唐澤・中田・立川が参加してきました。
高専プロコンとは、その名の通り全国の高専生によるプログラミングで何かを行うコンテストです。 コンテストは競技・課題・自由部門に別れ、競技部門では与えられた問題に回答するプログラムを数ヶ月かけて実装し、それを用いて他の高専と対戦します。 我々はこれに参加し決勝戦まで進出することが出来ました。
本日は問題の概要と我々の解法を紹介したいと思います。

問題概要

初めにある画像がサーバより与えられます。 この画像は基本的に風景画なのですが、縦横最大16に均等分割された小画像をランダムに並び替えた画像で構成されています。 この画像をいくつかの操作によって元の画像に戻すというのが今回の課題なのですが、まずはその小画像から元の画像を推測しなければなりません。 これには画像処理の技術が応用されることになります。
名称未設定
小画像を並び替える手順は、ある小画像を選択する選択操作と選択された画像を隣の画像と入れ替える交換操作に依って表されます。 選択回数には上限があり、単純に端のピースから揃えていくということは出来ません。 一つのピースをぐるぐる回して正しい並びに戻す様子はさながらパズドラのようです。 また選択・交換ともにコストが設定されているので出来るだけ短い操作で元の画像を復元しなければなりません。 回答をするまでに掛かった時間にはかなり大きめのコストがあり、長い時間をかけてスマートな復元手順を提出するより、愚直な手順でも短い時間で提出したほうが総コストは安くなったりします。

解法解説

前述のとおりこの問題は大きく画像処理部と復元手順探索部に分かれるのでそれぞれについて解説します。 なお唐澤は復元手順探索部の実装を担当しており、画像処理部の実装には関わっていないので、画像処理部の解説のみ立川が記述します。
なおソースは全てbitbucktで管理しており、ここに公開してあります。

画像処理部

去年同様に画像処理部を担当しました。最初に言ってしまうと、画像の復元はかなり運頼みでした。最終的に上の草原の写真は復元できていません。ここでは切り分けられた各画像を画像と呼び、復元された画像を元画像と呼ぶことにします。
今回の問題では、画像に評価値を割り振って貪欲的に評価値が良いものを結合していく、という手順を取りました。
評価値は、
[latex]a_0=1.0, a_1=0.15[/latex]
[latex]E=([sum_{i=0}^{1}a_isum_{k=0}^{l}(abs(R1^{(i)}_k-R2^{(i)}_k) + abs(G1^{(i)}_k-G2^{(i)}_k) + abs(B1^{(i)}_k-B2^{(i)}_k)]/l)^3 [/latex]
で決定しています。魔法の呪文です。ちょっとだけ補足しておくと、R1,R2,G1,G2,B1,B2は比較する2つの画像の画素値で、iは各画像の各画素値をi階微分したもので、正規化のためにlで割ってます。
探索方法について説明します。予めWxHの配列を用意します。最初に配置する画像は分かるわけがないため、ランダムに置く場所を決め、そこで全ての画像を配置するようにします。そこから、四方を見て上式で求めた評価値が一番小さくなるような画像をその場所に配置します。あとは空いている場所を埋める処理を書くだけです。
グラデーション系の画像にはかなり強いというのは経験則からわかるのですが、任意の二次元画像や端の画素が似ている画像は高確率で死ぬので人力で調整してくれるクライアントをチームメイトの中田に書いてもらいました。
後で府立の取った方針を見てみるとジグソーパズルのソルバーの論文を読んでいたみたいです。冷えました。
画像解析のソースはここにあります。

復元手順探索部

名称未設定1
復元手順は結局{ 00を選択, 01を選択, …, FFを選択, 上に交換, …, 左と交換 }という操作の配列で表現されるので、この操作列の探索を行うことに依って解を導出しています。 しかし一回の操作はWxHの盤面で約WH+4個あり、N回の操作列は(WH+4)^Nもの数だけ存在することになります。 このような膨大な手順を全て検証することは出来ないのである程度操作を繰り返して十分な数の操作列を生成したら、それらの操作列を評価関数にかけ、良い値が返って来た一部の操作列だけを元に次の探索を行うことにしました。 評価関数は正しい座標と現在の座標とのマンハッタン距離に選択している小画像の正しい座標とその小画像の正しい画像のマンハッタン距離の積で表しました。 選択している小画像より遠くにある画像の方がずれている時のペナルティが大きいわけですね。 選択している小画像はどの位置にあっても評価値に影響を与えないようにしたので、それをぐるぐる回して遠くのセルを揃え、最終的に正しい位置に戻ってくるようになります。 交換操作しか行わない場合は評価値の計算は交換を行った小画像の分しか変化しないので計算を省略することも出来ます。
選択回数は交換回数よりも遥かに少なくなるという性質を利用し、選択は確立的に行うようにもしました。 選択をする確立をP1、特にとある小画像で選択する確立をP2とすると一回の操作の数はWH+4個からWHP1P2+4に減らすことが出来ます。 はじめからとある小画像を選択する確立をP1とP2の積に設定しておけば良いと思われるかもしれませんが、P1とP2を分離することに依って1−P1の確立でWH個の小画像それぞれについて選択するかどうかの判断を行わなくても良くなります。
絶対に復元できない盤面はそれ以上探索をしないようにもしました。 選択回数が上限に達していてそれ以上選択できない時は、絶対に復元できない盤面が存在することが数学的に証明されており、またその理論を応用すれば簡単に不可能性を確認できるのです。 具体的な証明は省略致しますが「15パズル 不可能性」などで検索するとわかりやすい資料を読むことが出来るかと思います。 また不可能性は選択に依って変化し、交換に依っては絶対に変化しないので、前回不可能性を判定してから交換しか行っていない操作列は計算を省略することも出来ます。
この他にも類似の盤面を除いたりもしました。
ところで、このようにして無視する操作を増やしたり、探索を続ける操作列を制限したりすると問題も生じます。 「ある程度良い解には到達するが、一度盤面を大きく崩さないと完全な復元は出来ない時に、完全な復元が出来なくなる」のです。 15パズル(スライドパズルとも言われる)を一度でもやったことがあれば、正しい位置にあるピースを崩さずに解くのはかなり難しいというのが分かるかと思います。 この問題の対策として次の4点の工夫を行ないました。

  • 特に見込みのある操作列から生成される操作列は評価を見送る。
  • なかなか評価値が改善されなかった場合は選択確率P1,P2を大きくする。
  • 操作列の中から評価値が良くないものをランダムで選び出し探索を続ける。
  • 評価値が改善されなかった場合は操作を続ける操作列の絶対数を増やす。

このような改善を行った結果、極値に陥った時のリカバリをほぼ確実に行えるようになりました。
復元手順探索部の解説は以上になりますが、このアルゴリズムの問題点は無駄な操作列を沢山検査しなければならないので時間がかかることです。 それでも導出される解はかなり交換回数を抑えた解になっており、実際1回戦は1位で勝ち抜けることが出来ましたし、予行演習では(逆の復元手順を提出してしまうというバグが有り回答としては評価されませんでしたが)高選プロコンを優勝することになった大阪府立高専よりも良いスコアを出すことが出来ました。 決勝戦で敗北した原因は、16×16の最大ケースが出題されると確信し(実際は12×10の画像が出された)それ用のチューニングを行っていたことと、予想よりも交換コストが遥かに小さかったことにあります。 逆に交換コストが最大であれば今より少しだけ良い成績が取れたのではないかと思っています。
このアルゴリズムのソースは公開してありますので、解説で曖昧だったところはソースを見て頂ければ良く分かるかと思います。

総括

結果は1回戦、準決勝を勝ち抜き決勝戦で最下位を取るというものでした。 敗因は出題されるケースを穿ち過ぎ他のケースに対応できなかったことにあります。 かと言って他のケースに対応するだけの実装力と計画力があったかと言えば疑問があり、結局は実力通りの成績だったと思います。 しかし敗因が明快であるだけに強い悔恨の念も感じています。 私達は去年も高専プロコンに参加していますがそちらは散々な結果でした。 ですので今回の目標は決勝戦進出に設定していたのですが、それを達成できたにしても決勝最下位とは……やはり悔しいです。
来年は受験や卒業研究がありますのでプロコンには参加しないつもりです。 最後のプロコンをこのような悔しい思いで終えるのは本当に悲しいものですが、来年度以降はこの経験を活かし後輩のプロコンを全力で応援したいと思います。
結果については悲しい思いでいるとは言え、連日睡眠時間を削ってプログラムを実装したことや、他の高専との岩手での交流・観光は本当に楽しい思い出です。 一緒にお話してくれた府立・神戸・松江・福島・沖縄高専の方、東京大学の大城さん、本当にありがとうございました。 一緒に麻雀をして遊んでくれた久留米高専の方々は最早ソウルメイトだと思っています。 またお話出来たら良いですね。
(毎日毎日夜遅くまでプログラミングするのは……もういいかな……w)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください