chigichan24に人権はあるだろうか,いやない

競技プログラミングやってます。

第27回高専プロコン久留米会場画像処理班

こんばんは.chigichan24です.

高専プロコン競技部門が軽く炎上していますが,まあ高専プロコンだし,こんなもんなのかなと思ったり思わなかったり.

次に期待ですね.

私は画像処理を担当していました.結果としてはプロコン前日くらいに方針を大幅に変更した結果その方針で完成まで持っていくことができなかったのが非常に悔しいです.進捗のロールバックは現地入りしてからするものじゃないです.

多分どの高専も私みたいな感じもしくはこれ以上にすごい手法で画像処理のプログラムを準備していたはずです.ところがやっぱり人の手が早いじゃないかとなってしまったのは,なんともつらいところです.


ド素人が画像処理やアルゴリズムについて書いている記事なので変なところが多々あるかもしれませんが,こっそり教えてもらえると記事を修正でき,私の間違った知識が公開されなくなってみんなハッピーなので教えてくれる人がいたらうれしいです.




実は高専プロコンに参加?していましたが参加していませんでした(意味不明).正確には書類上は参加していないのですが,なんとなくプログラムを組みたいみたいな気持ちがあったので,自分にできる部分があればサポートしていきたいなと思っていたら仕事が降ってきました.


数ヶ月前から優秀な後輩たちが何やら議論を進めていたような気がしますが,いかんせん自分が受験生だったので夏休みまで全く状況を把握できていませんでした.


で,気がついたら高専プロコン2週間前になっていました.この段階でうちのものとしてできている進捗は真の意味で0でした.方針などは決まっていたと思います.外部の人間だったので普通にもっと進捗があると思っていたけど実際はほとんど無だったことに驚きを隠せなかった記憶があります.

その後お話し合いの結果,なんやかんやで自分が画像処理をやってみることになりました.

私に振られたタスクは

ピースの写真を撮り,多角形の座標データを取得する

という流れでした.

環境構築phase

昨年プロコンに出場した時に,WindowsMacという微妙に環境の異なる開発形態を取ったら思いの外面倒だったので,今回はまずVisualStudio2015で環境を作ろうと考えました.ところがopenCVのNuGetがなぜかうまく動作しない(新しいバージョンに対応していないらしい)という悲しいことにぶち当たったので,いろいろ試した結果,openCVのソースをコンパイルして頑張るというWindowsではなかなかしない方法によって解決しました.これで3日近く溶かしました.やばいですね.

方針

方針として当初自分は以下の手順を踏むことを考えていました.

1. USB接続のwebカメラで写真を撮る.(openCV)
2. 微分画像なりラプラシアンなりでエッジを取得する.(openCV)
3. エッジ画像からコーナーを検出し,エッジ検出でその精度を上げる.(openCV)

しかし,実際にやってみると様々な問題が発生しました.

webカメラが案外使えない

素数が思いの外低かったり,静止画(1920×1080)を撮ることに向いていなかったりと実際に使ってみるとわかりました.しかしUSB接続されていたので,PC側から容易に制御ができたのは利点でした.
ところが本当に画像がひどかったので,この利点を捨てて,普通のカメラ(3000×3000)で撮って,データを貰うほうがいいのではないかという結果に至りました.今思えば,スキャナーで読み取っても良かった気もしますが,枠がでかすぎてそれに対応したスキャナーを探すのがまず一苦労だったかもしれません.

エッジ検出がつらい

エッジ検出にはopenCVのHoughLinesPという関数を使っていました.ところがどんなにパラメータを調整してもピースの辺だけを抽出することができませんでした.なぜか細かくエッジが検出されていました.そこで,前述の関数で得られたエッジをうまくmergeすることで目的の辺を得るという手法を目指しました.具体的にはある辺iと辺jのCCWをとって折れてなかったら,2つの辺の最も遠い2点を新たに辺としてmergeするいう簡単なものです.mergeしたあとはUnionFIndで管理していい感じに親のみが必要な辺を持っているという状況まではプログラムできました.この対応によって幾分かはましにはなりましたが,CCWをとっているだけなので,同一直線上につながってはいけない線分があると悲しいことになっていました.また,,ピースを正確に真上から捉えることができずに側面を拾ってしまったり,影を拾ってしまったりしていました.

コーナー検出&多角形認識がつらい

コーナー検出はコーナー検出器がopenCVにはあるのですが,仮に,一枚の画像に1個のピースを載せるだけならいいのですが,複数個あると,どの多角形にコーナーが属しているかといった情報が得られないので,別の方法で行いました.それは上のエッジ検出で得られたエッジの端点をいい感じに再調整することです.というか,本当は思考のプロセスが逆でコーナーを取るためにエッジを検出したという感じです.再調整と同時に多角形の認識を試みました.認識およびコーナーの調整のアルゴリズムは以下のとおりです.

1. エッジを構成する端点座標に相互にそれぞれO(1)でアクセスできるように準備する.
2.座標とエッジがそれぞれO(1)でアクセスできるように準備する.
3.座標x,yそれぞれについてsort列を準備しておく.
4. ある座標にアクセスする.
5. その座標のエッジを構成するのに対応する座標tにアクセスする.
6. sort列の中での配列のindexをtの座標について2分探索することで求め,そこからtの座標に近い座標をK個ほどx,yのそれぞれについて求める.
7. K個のうち最もtに近い座標sを同一座標して処理する.ここで,同一座標として処理する時座標tの線分を構成する辺と座標sの線分を構成する辺の交点を多角形を構成する座標として登録する.
8. 座標sの線分を構成する辺のsの対となる座標にアクセスする.
9. 4に戻る.

ようするに,近い座標を同一頂点とみなしながらエッジ情報を用いて多角形を認識しています.これでとりあえず動くものができました.

誤差許容がつらい

誤差許容は特に同一エッジと見るときのCCWのところが大変でした.なかなかうまくいかない(なぜうまくいっている or いっていない)みたいな状況に何度もぶち当たって泣きそうでした.

なんかわけのわからないバグがある & openCVに泣く.

わけがわからないバグを踏んでしまったので,まあまあの割合で謎な辺を張ることがあって泣いていました.また,openCVが勝手に?アス比を変えて画像を書き込んでいたりして悲しい気持ちになっていました.


ここまで7日間近くかかりました.

方針の変更

ここらへんから出発直前 や (正規メンバーが)現地入りしてから変わっていたことです.自分は久留米会場に現地入りしていました.

2値化の方法

パンフレットを見ると他の高専は結構いい感じの精度で2値化ができていました.実際問題自分たちは,エッジを取得するのにcannyアルゴリズムというものを用いていたのですが,結構上に書いたとおり影や側面をとっていました.また2値化はやっていたのですが,あまりうまく行っていませんでした.他の高専にできるなら自分たちにもできるということでwinjiiくんがなんかやってくれた結果,HSVではなくRGBでやったらきれいになるという結果でした.私はあえて,HSVを選んでいたのですが,光の僅かな差に過剰に反応しすぎていました.これは反省です.

なんかよくわからないバグを修正しようと試みる.

winjiiくんが頑張ってくれました.すごい.

なんかよくわからないバグを修正した結果わかったこと

winjiiくんが頑張ってバグを修正した結果なんでいままでうまく辺をmergeできていたのかが意味不明な感じになってしまいました.
そこで,いったん私がやっていた方針をやめて別の方法で調整することを試みました.

2値化された画像の探索

2値化画像が現地に入ってかなりきれいに取れるようになったので,2値化画像である点の4近傍を探索しながら多角形の外形を得ることに成功しました.しかし,外形が得られただけで,肝心のコーナーが得られませんでした.コーナをCCWしながらとるということを試みましたが,だめでした.また,一定の間隔で最小二乗法をかけながら辺を近似していく方法も試しましたが,うまく実装しきれませんでした.

探索矩形領域の変更

外形の場所がわかった今,PC上で1つのcv::Mat に1つの多角形で管理できると気が付きました.矩形領域をもとめてそれをcv::Matに入れて,もともと自分が使っていたアルゴリズムに流せばうまくいくと思いました.もともと自分が書いたやつは1つのピースに対してはかなりの精度で多角形を検出できていたので,試みました.しかし実装を始めた時間が,準決勝が始まる日の午前5時頃,終わりませんでした.そしてそのまま寝落ちしました.

結果

13時前に目が覚めると久留米の競技は終わっていました.

いろいろ

・自明にもっと早くから取り組もう
・画像処理な研究室にいるのに数学的に解析できなかった辛さが多かったです.openCVで中でやっていることをきちんと理解できていれば今回の問題に最適化できた気がします.
・強い後輩だったので勝たせてあげたかった.

これで久留米画像処理班の戯言は終わりです.ソースコードは汚すぎるので,きれいにする余裕がうまれたら公開するかもしれないです.

もし,メンバーが三重にいる間にこの記事を読んでくれていたら,赤福を買ってきてほしいなぁ.老害からは以上でした.