Stixelを用いた視差画像からのフリースペース計算 〜（理論編２）
ということで，実装編に入る！と思っていたんですが，「どうやって動的計画法を実装するか？」という点を抑えておきたく下記の理論編１に引き続き理論編２のエントリも書くことにしました．
１．参考文献
こちらのエントリでは下記の論文の内容を見ていきますが，論文内容としては「Stixel をどうやって Cuda で実装するか？」です．
- GPU-accelerated real-time stixel computation
画像処理をやる人の端くれとして，一応 Cuda には触ったことはあるのですが，あまりむずかしい並列化はやったことがなく，今回の Stixel の問題は難易度も結構高くていい題材かと思ったので論文を読んでまとめてみることにしました．（が，このエントリでは動的計画法のとこまでしか書いてません．Cuda化のところは実装編で触れます．）
２．問題のおさらい
細かい問題定義は「理論編１」を見ていただくとして，簡単に問題構成のおさらいをしておきます．解こうとしている問題は，「視差画像 D が与えられたときに，尤度が最大となるような Stixel の集合 L を見つける．」ことです．
で，尤度が最大になるような Stixel L の集合をどうやって見つけるか？ですが，簡単に言うと可能な Stixel の組み合わせを総当りで試してみて，その中で尤度が最大になる組み合わせを採用します．この総当り計算を実施するときに，単純に全組み合わせを計算すると計算量が爆発してしまうので，「重複した計算を避ける」ために動的計画法が出てきます．で，動的計画法の話に入る前に，解法に重要な影響を与える２つの前提を書いておきます．
１．隣り合う列は互いに独立である．
３．動的計画法のおさらい
次に，簡単に動的計画法のおさらいをしておきます．この Stixel の問題と類似の問題を見つけたので，別のエントリとして作ってみました．
で，上記エントリの場合の問題設定は下記でした．
ロッド切り出し問題
あなたはコーナンで働いているとします！長〜い金属棒を仕入れて，これを小分けに切断して販売したいですが，金属棒は長さによって販売価格が異なります．そして，販売価格は長さに比例しているとは限りません！このときに，長さ n の金属棒をどのように切断すれば売上を最大化できるでしょうか？
動的計画法の観点では，この問題はとても良く似ています．
一点異なる点として，ロッド切り出し問題の場合は単純に切り出し方法を決めればよかったのに対し，Stixel の最適化計算では Stixel の種類（Sky, Ground, Object）が変数として増えてきます．
４．動的計画法を用いた Stixel の解法
ロッド切り出し問題との類似点がわかったので，同様の考え方で動的計画法を解いてみたいと思います．
４．１．細かな問題設定
下記，論文にある問題設定です．
・Stixel は３種類（Object, Ground, Sky）
・Stixel自体 の表記方法
1. 開始端を row = b，終了端を row = t にもつ，Object の Stixel：obtb = {vb, vt, Object}
2. 開始端を row = b，終了端を row = t にもつ，Sky の Stixel：skytb = {vb, vt, Sky}
3. 開始端を row = b，終了端を row = t にもつ，Ground の Stixel：groundtb = {vb, vt, Ground}
・集約コストの表記方法
1. 終了端を row = k にもち，最後の Stixel が Object である場合の集約コスト： OBk
2. 終了端を row = k にもち，最後の Stixel が Sky である場合の集約コスト： SKk
3. 終了端を row = k にもち，最後の Stixel が Ground である場合の集約コスト： GRk
で，やっぱりわかりにくいので描画します！
４．２．評価式
評価式自体は，理論編１のときに紹介したものがベースになっています．が，，，２つの論文で評価式がちょっと違っていたので，これは実装と突き合わせながら，実装編で確認します．
４．３．動的計画法
で，ようやく評価式ができたとして，動的計画法を用いて最適化問題をときます．
上図を見てもらうとわかると思うのですが，ある画像列に対して高さ h までの集約コストが最適になるものを求めるという問題なので，ロッドの切り出し問題とよく似ています．が，Stixel の種類が３つあるということと，評価式が実質的に２つの項（条件付き確率項，事前確率項）からなるということで，ちょっとだけ問題が複雑になります． この条件を鑑みて，動的計画法の漸化式を書いてみます．
上図に描画したとおり，Stixel の種類が３種になることから下記の点が異なってきます．
・考慮している Stixel (終了端が k) 自体に関して，３つの分岐ができる．
・考慮している Stixel (終了端が k) の一つ前の Stixel に関して，３つの分岐ができる．
ここまでで，動的計画法の漸化式が求まりました．前述したとおり，この論文のメインテーマは「Cudaでどうやって並列化するか？」なのですが，これは実装編でかければと思います．
