tut_procon25

第25回高専プロコン競技部門の豊橋技科大のコードです。

このプログラムは、大きく4つの部分に分割されています。

1. 入出力
2. 原画像推定
3. 人力による推定画像の修正
4. 選択・交換操作の計算

ビルド可能な環境

以下の環境でビルド可能であることが確認できています。

• ライブラリ等

  • Boost 1.56
  • OpenCV 2.4.9
  • cURL(コマンドラインでcurlが使えるような環境)

• Windows

  • Visual C++ Compiler Nov 2013 CTP

• Linux

  • gcc 4.9

• Mac

  • gcc 4.9
  • (clang)

各モジュールの説明

gochiMain

• main.cpp

  プロコンの本番で使用したmain関数

• test_main.cpp

  高専プロコン競技部門練習場2014(http://procon2014-practice.oknct-ict.org/)の問題を解くためのmain関数

• prac_main.cpp

  プログラムで復元された画像を、手動で復元する練習を行うためのmain関数

utils

全モジュールで共通して使うような関数や型などを定義している

inout

本戦サーバや、練習場から問題を取得したり、解答を堤出したりするためのモジュールです。 C言語のsystem関数を使用して、curlを叩いています。

guess_img

バラバラな画像を元の画像に復元するためのモジュール。 プロコン本番では、速度および精度に優れたblocked_guess.hppを使用していました。 当初のblocked_guess.hppは第一回戦の第一問が完全復元できなかったため、プロコン一日目の晩に強化しました。

blocked_guess.hppで使用しているアルゴリズムは、次の手順で進みます。

1. まず結合しやすい断片を数個集めて正方形のグループを作ります。

2. 次にそのグループを原画像のいろんな場所に配置してみます。

3. その配置したグループの周辺に余っている断片をすべて貪欲法で結合させていきます。

4. 最初に配置するグループの位置によって出来上がる推定画像は異なるので、これらの内から最も尤もらしい結果を選びます。

二つの画像がどの程度結合しやすいかは、画像の縁の画素のRGB値を比較した結果をそのまま使用しています(correlation.hpp)。

modify_guess_image

プログラムのみでは復元しきれなかった画像を、人力とコンピュータによる双方向的な操作によって復元を試みるモジュールです。 本戦では第一回戦の第一問目でしか使用する機会はありませんでしたし、人力修正している間に時間コストによって順位が下がる可能性が予想以上に高くて驚きました。

このモジュールでは、まずguess_imgによって推定された画像の断片達の中から、人間が「確実に結合している断片群」をマウスのドラッグにより人力で選択します。 この選択された断片群は、guess_imgで説明したグループとなり、もう一度画像推定が行われます。 この操作は人間が認定するまで行うことが出来ます。

calc_exchange

guess_imgおよびmodify_guess_imageによって推定された断片の位置から、交換操作および選択操作を計算します。 小さな問題ではA*(calc_exchange.hpp)を使用し、巨大な問題では断片を順番に目的の場所まで持っていきます(line_greedy_calc_exchange.hpp)。

巨大な問題では、断片を元の位置から目的の位置に移動させる際には、最終的に総コストが小さくなるような移動経路をダイクストラ法により探索します。 また、上下左右のうちどの辺から断片を元の位置に移動させるかは、貪欲法により決定します。

createPpm

人力修正を練習するための問題を作成するためのプログラムです。 このプログラムで1300問程度の問題を作成しましたが、結局本戦では第一回戦の一問目しか人力修正を行う機会はありませんでした。