#contents

*この記事について [#d0b5f26e]
-この記事は[[Computer Vision Advent Calendar 2012>http://partake.in/events/13622c9b-3ada-4dd8-a967-56fe8927541b]]の5日目&note{cv-advent-calendar:[[Computer Vision Advent Calendar 2012>http://partake.in/events/13622c9b-3ada-4dd8-a967-56fe8927541b]], 2012-12-01閲覧};の12/9担当記事です。タイトルが5日目になってるのは、手島が担当したのが5日目、という意味。
-もし誰かの記事がかぶったら、12月12日の担当記事にしてしまっても構いません。
-できるだけ、毎日更新を達成したいので、穴埋めを頑張りまする。
-詳しくは[[Computer Vision Advent Calendar 2012>http://partake.in/events/13622c9b-3ada-4dd8-a967-56fe8927541b]]&note{cv-advent-calendar};をご参照ください。

*高専プログラミングコンテスト [#uca2a359]
-今日書くのは個人的な感想
-先日、高専プログラミングコンテスト&note{procon-official:[[全国高等専門学校プログラミングコンテスト - Official Site>http://www.procon.gr.jp/]], 2012-12-09閲覧};が開催され、コンテストでの人力での優勝が話題になりました。
-プログラミングコンテストとは、毎年課題が提示され、それを処理するプログラムを高専生がくみ、当日そのプログラムを用いて課題に挑戦する大会です。
-今年の大会に関する情報は大会のサイト&note{procon-official};やまとめサイトなんかが多数あります。今日はその紹介がメインではないので、そのあたりはググって調べてみてください。
-簡単にまとめると、
--サイコロの数を数える問題
--プログラミングのコンテストなのに人力で数えたチームが優勝した
-というのが主な話題になっています。

*問題を見た率直な感想 [#s79ef16b]
-いろいろ言われてますが、私個人としては結構難しい問題だったとおもいます。
-既に終わった大会ですから、結果に関して、とやかく言うつもりはありません。
-優勝した宇部高専のチームはおめでとうございます。
-ただ、運営側としては、画像処理によるカウントを期待していたと思います。
-なので、今日は、「もしこういうことが可能ならば、こういうアプローチが在り得たかも知れない」という個人的な感想を述べていきます。

*いろんな「もし」 [#c599d54c]
-サイコロの設置場所に関しては、随分細かくルールが決まっています。
-円形の台
-チームのメンバーが近寄れる「撮影場所」
-サイコロの重さ、大きさ
-などなど
-詳しくは要項7pからを参照&note{procon-rule:[[全国高等専門学校 第23回プログラミンコテスト 競技部門のご案内>http://www.procon.gr.jp/uploads/procon23/Apply23.pdf]], 2012-12-09閲覧};

**もしマーカが置けたならば [#q4540a63]
-マーカをおいた場合、カメラの撮影位置が正確に測定できます。
-ARマーカと同じ原理です。
-なので、台の上にマーカを置けた場合、多視点から撮影して、その情報から3次元形状の復元を行えます。
-視線交差法なんかだけでも、ざっくりとした体積が復元できたのではないかと思います。
-この体積を、サイコロ1個の体積で割り算することで、数をかぞえるアプローチが可能だったかな、と思います。
**マーカを置いた場合の技術的課題 [#yeae0c43]
-マーカの特性
--サイコロ(マーカ)とカメラが離れてますので、推定される精度がかなり低下することが予想されます。
--このために、マーカのサイズやテクスチャなどに工夫をして、精度よく位置を測定するところに技術的挑戦があります。
--このあたり、精度良くカメラの位置姿勢を推定できるマーカを工夫してつくるというコンテストでも面白かったかもしれません。
-3次元形状復元
--理論的に3次元形状復元が可能と言えど、魔法のように関数1つで復元されるわけではありません。
--3次元形状復元のためには、それなりの技術的挑戦があったのではないかと思います。


**もしサイコロの出目でなく、既知のテクスチャが使えたならば [#m3a633c9]
-サイコロというのは、画像において、容易なようで難しい側面を持っています。
--簡単な面
---色が2色、ないしは3色のみ(白、黒、赤)
--形が直方体と単純
--テクスチャが単純
-一方で、簡単な面は場合に応じて難しくなります
--白一色なのでエッジが検出しにくい
--サイコロを検出する場合、どうしてもエッジの位置が重要になってきますが、白一色のサイコロだと、エッジの位置を検出するのがかなり難しくなります。
--色が2色しかない
---赤い点の場合は用意に1の目と分かりますが、黒い丸を見つけた場合、この丸が一体どの目のうちの1つの点なのか、というのを推定する必要があります。
-まとめると、サイコロの目を「検出」するのは容易ですが、「特定」するのはかなり困難を極めます。
-そこで、これを自然写真にする、という方法があります。
-自然写真にすることで、面1枚1枚を特定することが容易になります。
-最近はGoogle画像検索なんかでも行われてるように、画像のマッチング(Image Retrieving)という分野で広く研究が行われています。
-これで面の数を数えたり、サイコロの形状復元なんかが可能になるので、体積や面の数をカウントすることで、正解にアプローチすることもできたかもしれません。


**サイコロの出目のかわりに既知のテクスチャが使えた場合の技術的課題 [#k7449913]
-見えの変化に対する頑強性
--マッチングをとってくれる特徴量抽出手法は最近けっこう増えてます
--ただし、SIFTやSURFなんかの特徴量は射影的な変換、つまり水平方向に回りこむことで発生するような見えの変化に対しては追跡が難しいと言われています。
-対応点から平面を抽出する
--特徴量抽出して対応点をみつけたとしても、その対応関係から無数の平面を抽出する作業があります。しかもサイコロは数十個のオーダで存在するので、かなり大変そうです。
-オクルージョンの対応関係
--オクルージョンとは、物体による遮蔽のことを指します。
--募集要項&note{procon-rule};を見てもらえばわかりますが、サイコロ同士がお互いの面を隠しあっています。
--人間の頭は自動的に前後関係や位置関係を推察してサイコロの数をかぞえることができますが、Computer Visionは残念ながらそこまで賢くありません
--なので、その遮蔽関係を推定する、何らかの仕組みが必要になります。

**もし出目の数を全部数えられたら [#j330f8e5]
-サイコロの良いところは、目の合計が必ず21になることです。なので、出目の合計を21で割れば、必ずサイコロの数になります。
-このアプローチは、現行のルールでも認められるものです。
-なので、このアプローチを試して、うまく行かなかったチームも居るのではないかな?
**出目の数を全部数える場合の技術的課題 [#m797eb9d]
-前述しましたが、オクルージョンの問題が残ります。
-当然接地してる面の出目は見えませんし、サイコロが別のサイコロを隠していることもありえます。
-そのオクルージョンで見えない目のことをどう対処するか、という事を考える必要があります。
-サイコロの数が十分に多ければ、1枚あたりの出目の数を3.5(21÷6)と計算してざっくり出目の数をかぞえるというアプローチも可能だったのかもしれません。


**もし円形の台をふんだんに使えたら [#r0bb4c44]
-ルール&note{procon-rule};を参照してもらえれば分かりますが、円形の台のサイズ、それから競技者たちが立ち入ることのできる領域が厳密に定義されています。
-円形の台ということは、水平にカメラを動かすことで、かなり特徴的な画像が得られます。
-これを水平ラインごとに分解することで、こんな特徴量が得られます。
-(tomoaki_teshimaの頑張りに期待ください)
-この特徴的な画像は時空間画像と呼ばれています。
-通常、ビデオとはx、y、tで表される3次元の画素の集合とみなすことができます。
-通常のカメラだとxーy平面で区切った2次元画像を我々は観測しますが、一度録画することが出来ればx-t&note{timeSpaceImage-note:今は一定の角速度(つまりはtと&mimetex(\theta);)で撮影していることを想定して感想文を書いているので、x−&mimetex(\theta);平面の話としても同様};平面で切り出した2次元画像を見ることができます。
-このような画像を作ることで、水平に動くサイコロの情報を集めやすいかと思います。

**円形の台を使うアプローチでの技術的課題 [#e43f819b]
-位置合わせ(registration)の問題
--これには水平に移動できるカメラ&note{level-strictly:厳密に言えば、撮影時の上下移動が、物理的に1ピクセル以下};という、制約が必要なので、かなり特殊な撮影装置が必要になります。
--また、撮影後に補正する場合も高度な位置合わせ手法が必要になります。
--このあたりは手島の博士課程中に散々悩まされた問題なので、かなり難しい問題だとだけ述べておきます

*最後に [#s05711d9]
-最後に、念の為に申し上げておきますが、この記事は単に手島の「もしルールがこうだったらこんなアプローチができて面白そうだなぁ」という感想文です。
-それ以上のそれ以下の他意はありません
-しかし、見事に文章だらけの記事になってしまった。
-コンピュータビジョンの記事なので、時空間画像ぐらいは作ってみてアップロードしたかった。。。
-手島の担当は本来は(ry
-[[12月1日に投稿した記事>Computer Vision Advent Calendar 2012]]と[[12月2日に投稿した記事>Computer Vision Advent Calendar 2012 2日目]]と[[12月3日に投稿した記事>Computer Vision Advent Calendar 2012 3日目]]と[[12月5日に投稿した記事>Computer Vision Advent Calendar 2012 4日目]]もご参照ください。
-もうネタがないので、あとは他の方々(ry
-今回の記事はComputer Vision Advent Calendarの[[12月6日分の記事>http://d.hatena.ne.jp/blue_jam/20121206/1354731061]]&note{blue_jam-blog:[[高専プロコンとComputer Vision - 負け犬blue_jamの日記>http://d.hatena.ne.jp/blue_jam/20121206/1354731061]], 2012-12-09閲覧};を書かれたblue_jamさんの記事を読んで、思いつきました。感謝!
-企画者の [[@sakanazensen>https://twitter.com/sakanazensen/]]&note{twitter-sakanazensen:[[@sakanazensen>https://twitter.com/sakanazensen/]], 2012-12-01閲覧}; くんにも度々感謝!


トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS