---
title: コンピュータビジョンセミナーvol.3 ～視差計算を利用した障害物検出～（2023/10/27）
tags:  #cuda #機械学習 #deeplearning #深層学習 #stixel #semanticsegmentation #障害物検知 #障害物検出 #自動運転 #画像解析 #画像処理 #コンピュータビジョン #コンピュータビジョンシリーズ #cuda高速化 #障害物検出  
author: [株式会社フィックスターズ](https://www.docswell.com/user/fixstars)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/YJ65RX8G7V.jpg?width=480
description: 自動運転を実現するために、障害物の検出は欠かせません。 障害物検出を行う処理手順の1つに、前回の弊社ウェビナーで紹介した「視差計算」の後、短冊状のセグメント Stixel を計算する方法があります。 さらに深層学習と組み合わせて、高度な Stixel の検出を行い、障害物検出の精度を上げる手法も提案されています。  本ウェビナーでは、Stixelの考え方および計算手法の解説、CUDAによる高速化の事例を紹介します。 障害物検出機能の基礎となる考え方をおさえておきたい方に最適です。   ＜過去資料＞ ・vol.1　OpenCV活用（OpenCVでCUDAを活用するためのGpuMat解説）：　https://www.docswell.com/s/fixstars/ZRXQ72-20220805 ・vol.2　視差計算ライブラリ libSGM のアルゴリズム解説と CUDA高速化：　https://www.docswell.com/s/fixstars/5ENE7J-20221220 ・vol.3　視差計算を利用した障害物検出：　https://www.docswell.com/s/fixstars/ZQ8447-20231027  ・フィックスターズの画像処理アルゴリズム開発支援：　https://www.fixstars.com/ja/services/image-processing
published: November 01, 23
canonical: https://www.docswell.com/s/fixstars/ZQ8447-20231027
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/YJ65RX8G7V.jpg)

コンピュータビジョンセミナーvol.3
視差計算を利用した障害物検出
Copyright © Fixstars Group


# Page. 2

![Page Image](https://bcdn.docswell.com/page/GJ5Y8X9XJ4.jpg)

本日のAgenda
⚫ はじめに
⚫ フィックスターズのご紹介
⚫ Stixel検出のアルゴリズム
⚫ Stixel検出のCUDA実装
Copyright © Fixstars Group
1


# Page. 3

![Page Image](https://bcdn.docswell.com/page/LE358XY4J5.jpg)

はじめに
Copyright © Fixstars Group


# Page. 4

![Page Image](https://bcdn.docswell.com/page/8EDDM255EG.jpg)

本講演の位置づけ
⚫ 弊社でサービス展開しているコンピュータビジョン領域での様々な技術情報を、
コンピュータビジョンセミナーとして発信しています
⚫ Vol.1 OpenCVでCUDAを活用するためのGpuMat解説
⚫ Vol.2 視差計算ライブラリ libSGM のアルゴリズム解説
⚫ Vol.3 視差計算を利用した障害物検出
⚫
⚫
障害物検出に向けた短冊状セグメント Stixel の計算方法
CUDAによる高速化事例
⚫ こんな方に向いています
⚫
⚫
障害物検出の基礎となる考え方を理解したい
実用的なアルゴリズムの GPU 高速化事例を知りたい
Copyright © Fixstars Group
3


# Page. 5

![Page Image](https://bcdn.docswell.com/page/V7PXR1GDE8.jpg)

発表者紹介
冨田 明彦
高木 章洋
ソリューションカンパニー 営業企画
ソリューション第二事業部
リードエンジニア
2008年に入社。金融、医療業界において、ソ
フトウェア高速化業務に携わる。その後、新規
事業企画、半導体業界の事業を担当し、現職。
2014年に新卒入社。自動運転向けの画像認識
アルゴリズムの開発、高速化などに携わる。
OSS活動として、libSGMの開発にも携わる。
Copyright © Fixstars Group
4


# Page. 6

![Page Image](https://bcdn.docswell.com/page/2JVLRY6G7Q.jpg)

フィックスターズの
ご紹介
Copyright © Fixstars Group


# Page. 7

![Page Image](https://bcdn.docswell.com/page/5EGXM92DJL.jpg)

フィックスターズの強み
コンピュータの性能を最大限に引き出す、ソフトウェア高速化のエキスパート集団
ハードウェアの知見
アルゴリズム実装力
各産業・研究分野の知見
目的の製品に最適なハードウェアを見抜き、
その性能をフル活用するソフトウェアを開
発します。
ハードウェアの特徴と製品要求仕様に合わ
せて、アルゴリズムを改良して高速化を実
現します。
開発したい製品に使える技術を見抜き、実
際に動作する実装までトータルにサポート
します。
Copyright © Fixstars Group
6


# Page. 8

![Page Image](https://bcdn.docswell.com/page/4JQ8RWPX7P.jpg)

サービス概要
お客様専任のエンジニアが直接ヒアリングを行い、高速化を実現するために乗り越えるべき
課題や問題を明確にしていきます。
高速化のワークフロー
お客様
オリジナルソースコードのご提供
高速化したコード
コンサルティング
高速化
サポート
先行技術調査
アルゴリズムの改良・開発
レポートやコードへのQ&amp;A
性能評価・ボトルネックの特定
ハードウェアへの最適化
実製品への組込み支援
レポート作成
Copyright © Fixstars Group
7


# Page. 9

![Page Image](https://bcdn.docswell.com/page/K7428KY2J1.jpg)

サービス提供分野
半導体
産業機器
金融
自動車
● NAND型フラッシュメモリ向け
ファームウェア開発
● 次世代AIチップの開発環境基盤
生命科学
● Smart Factory実現への支援
● マシンビジョンシステムの高速化
● 自動運転の高性能化、実用化
● ゲノム解析の高速化
● 次世代パーソナルモビリティの
研究開発
● 医用画像処理の高速化
Copyright © Fixstars Group
● デリバティブシステムの高速化
● HFT(アルゴリズムトレード)の高速化
● AI画像診断システムの研究開発
8


# Page. 10

![Page Image](https://bcdn.docswell.com/page/LJ1M2X6KEG.jpg)

サービス領域
様々な領域でソフトウェア高速化サービスを提供しています。大量データの高速処理は、
お客様の製品競争力の源泉となっています。
組込み高速化
GPU向け高速化
AI・深層学習
画像処理・
アルゴリズム開発
FPGAを活用した
システム開発
分散並列システム開発
量子コンピューティング
自動車向け
フラッシュメモリ向け
ソフトウェア開発
ファームウェア開発
Copyright © Fixstars Group
9


# Page. 11

![Page Image](https://bcdn.docswell.com/page/GJW3RNWPJ2.jpg)

画像処理アルゴリズム開発
高速な画像処理需要に対して、経験豊富なエンジニアが
責任を持って製品開発をご支援します。
お客様の課題
ご支援内容
高度な画像処理や深層学習等のアルゴリズム
を開発できる人材が社内に限られている
アルゴリズム調査・改変
課題に合ったアルゴリズム・実装手法を調査
製品実装に向けて適切な改変を実施
機能要件は満たせそうだが、ターゲット機器
上で性能要件までクリアできるか不安
深層学習ネットワーク精度の改善
様々な手法を駆使して深層学習ネットワークの精度を改善
製品化に結びつくような研究ができていない
論文調査・改善活動
論文調査から最先端の手法の探索
性能向上に向けた改善活動を継続
Copyright © Fixstars Group
10


# Page. 12

![Page Image](https://bcdn.docswell.com/page/4EZVR356J3.jpg)

GPU向け高速化
高性能なGPUの本来の性能を十分に引き出し、
ソフトウェアの高速化を実現します。
お客様の課題
ご支援内容
GPUで計算してみたが期待した性能が出ない
GPU高速化に関するコンサルティング
GPU/CPUを組み合わせた全体として最適な設
CPU・GPU混在環境でのシステム設計
計がしたい
アルゴリズムのGPU向け移植
原価を維持したまま機能を追加するため、も
う少し処理を速くしたい
GPUプログラム高速化
品質確保のため、精度を上げたく演算量は増
えるが性能は維持したい
Copyright © Fixstars Group
継続的な精度向上
11


# Page. 13

![Page Image](https://bcdn.docswell.com/page/Y765RX9LEV.jpg)

Stixel World：
視差計算を利用した障害物検出
Copyright © Fixstars Group


# Page. 14

![Page Image](https://bcdn.docswell.com/page/G75Y8XNM74.jpg)

Stixel Worldとは
⚫ 自動車メーカーDaimler※のステレオビジョン研究で提唱されている、
シーンの中間表現方法
⚫ 短冊状のセグメントStixel(Stick+Pixel)によって障害物を構成
各画素のRGB値、視差値など
Low
Stixels
Mid
物体の位置・速度など
High
情報の階層 (図は[1]から抜粋)
※Daimler AG
現在はメルセデス・ベンツ・グループに社名変更
Copyright © Fixstars Group
13


# Page. 15

![Page Image](https://bcdn.docswell.com/page/9J2GKX5RJR.jpg)

Stixel Worldの研究史
2009 Stixel World
の登場[1]
2011 Multi-Layer Stixel[3]
一列に複数のStixelを検出できる新モデル
2016 Semantic Stixels[4]
視差とSemantic Segmentationを利用した、
Joint Optimization (同時最適化)
2010 Dynamic Stixel[2]
Stixelを追跡し、3次元位置・速度を推定
2021 Slanted Stixels on GPU[6]
Jetson Xavierで300FPS以上
2017 Slanted Stixels[5]
複雑な視差モデルに対応
[1] Badino, Hernán, Uwe Franke, and David Pfeiffer. &quot;The stixel world-a compact medium level representation of the 3d-world.&quot;
Pattern Recognition: 31st DAGM Symposium, Jena, Germany, September 9-11, 2009. Proceedings 31. Springer Berlin Heidelberg, 2009.
[2] Pfeiffer, David, and Uwe Franke. &quot;Modeling dynamic 3D environments by means of the stixel world.&quot; IEEE Intelligent Transportation Systems Magazine 3.3 (2011): 24-36.
[3] Pfeiffer, David, and Uwe Franke. &quot;Towards a Global Optimal Multi-Layer Stixel Representation of Dense 3D Data.&quot; BMVC. Vol. 11. 2011.
[4] Schneider, Lukas, et al. &quot;Semantic stixels: Depth is not enough.&quot; 2016 IEEE Intelligent Vehicles Symposium (IV). IEEE, 2016.
[5] Hernandez-Juarez, Daniel, et al. &quot;Slanted stixels: Representing San Francisco&#039;s steepest streets.&quot; arXiv preprint arXiv:1707.05397 (2017).
[6] Hernandez-Juarez, Daniel, et al. &quot;3D Perception With Slanted Stixels on GPU.&quot; IEEE Transactions on Parallel and Distributed Systems 32.10 (2021): 2434-2447.
Copyright © Fixstars Group
14


# Page. 16

![Page Image](https://bcdn.docswell.com/page/DEYVN8K5EM.jpg)

Stixel Worldを題材にした理由
⚫ 自動運転に関連する技術
⚫ 応用レベルのComputer Vision
○
前回のCVセミナーで扱った視差計算※を土台とした、より高度な処理を実現する事例
⚫ 高速化へのこだわり
○
自動運転のため、リアルタイム性が必須
○
データ構造の工夫、CUDA実装等、論文を通して様々なアプローチを知ることができる
※前回のCVセミナーはこちらをご参照下さい
コンピュータビジョンセミナーvol.2 視差計算ライブラリ libSGM のアルゴリズム解説とCUDA高速化
https://www.docswell.com/s/fixstars/5ENE7J-20221220
Copyright © Fixstars Group
15


# Page. 17

![Page Image](https://bcdn.docswell.com/page/VJNMXQR478.jpg)

本セミナーの構成
1. Stixel検出のアルゴリズム
2. Stixel検出のCUDA実装
Copyright © Fixstars Group
16


# Page. 18

![Page Image](https://bcdn.docswell.com/page/YE9N8DM4E3.jpg)

1. Stixel検出のアルゴリズム
Copyright © Fixstars Group


# Page. 19

![Page Image](https://bcdn.docswell.com/page/GE8K83LV7D.jpg)

Stixel検出のアルゴリズム
⚫ Stixelとは
⚫ 座標系と表記
⚫ Stixel検出の原理
⚫ アルゴリズムの概要と発展
⚫ 目的関数の設計と解法
⚫ 計算量と高速化
Copyright © Fixstars Group
18


# Page. 20

![Page Image](https://bcdn.docswell.com/page/LELZRVLRJR.jpg)

Stixelとは
⚫ 物体を構成する短冊状のセグメントで、以下の属性を持つ
説明
Stixelの属性
Stixel座標
上下左右．ただしStixelの幅はパラメータで事前に決定
geometricクラス
シーンの構成要素を空間構造によって分類したもの
路面(ground)、物体(object)、空(sky)の3種類あり、それぞれ付随した視差モデルを持つ
視差モデル
Stixel内の視差分布を平面によって近似したモデル
semanticクラス
シーンの構成要素を意味によって分類したもの (車/人/標識/樹木/etc.)
Semantic Stixels[4]以降で導入されている
Stixelによるシーンの表現 (図は[6]より抜粋)
a. geometricクラス”物体”のStixelの表示．色は奥行きに対応 (近:赤 ～ 遠:緑)
b. semanticクラスによって色分けしたStixelの表示
c. 各Stixelを視差モデルによって3次元復元したもの
Copyright © Fixstars Group
19


# Page. 21

![Page Image](https://bcdn.docswell.com/page/4JMVRGMPJW.jpg)

Stixelとは
⚫ Stixelの設計思想 ([1]からの引用)
○
compact：画素数と比較して、大幅にデータ量を削減
○
complete：対象物の情報を保存
○
stable：入力データの微小な変動に影響を受けない
○
robust：ノイズにも頑健
⚫ Stixelの応用
○
シーンの3次元復元
○
走行可能領域や障害物の検出
○
移動物体のトラッキング、位置・速度の推定
○
etc.
Copyright © Fixstars Group
20


# Page. 22

![Page Image](https://bcdn.docswell.com/page/PJR2RZVYE9.jpg)

座標系と表記
⚫ 元論文を踏襲し、画像座標を(𝑢,𝑣) で表記
⚫ 𝑣は上向きを正とする
⚫ 座標は1オリジンで数える (1,2,3, … , 𝑤)
𝑣
ℎ
画像
1,1
𝑢
𝑤
Copyright © Fixstars Group
21


# Page. 23

![Page Image](https://bcdn.docswell.com/page/PEXDR9Z47X.jpg)

Stixel検出の原理
⚫ v-disparity空間
○
画像のある水平座標𝑢上で、垂直座標𝑣と視差𝑑を軸にとる空間
○
観測視差をプロットすると、シーンの構造に応じて特有のパターンが現れる
⚫ 観測視差に視差モデルを当てはめることで、セグメンテーションを実現
geometricクラスと付随する視差モデル
geometric
クラス
視差モデル
補足
路面(𝑔)
𝑓𝑔 𝑣 = 𝛼𝑣 + 𝛽
𝑣の一次関数
物体(𝑜)
𝑓𝑜 𝑣 = constant
𝑣によらず一定
空(𝑠)
𝑓𝑠 𝑣 = 0
無限遠点の視差は0
v-disparity空間上の観測視差(real)と視差モデル(ideal) (図は[3]より抜粋)
Copyright © Fixstars Group
22


# Page. 24

![Page Image](https://bcdn.docswell.com/page/3EKXRP8P7D.jpg)

Stixel検出の原理
⚫ 事前知識(prior knowledge)の活用
○
𝑣方向に隣り合うStixelの組について、現実に起こりやすい/起こりにくいパターンを列挙
⚫ 当てはめ誤差と事前知識、2つの観点から最適なセグメンテーションを推定
geometricクラスの組と事前知識
geometricクラスの組
事前知識の例
上側
下側
𝑜
𝑜
上側の視差が大きい(=手前側にある)確率は低い
そうでないと上側の物体が浮いていることになるため
𝑜
𝑔
物体下端と路面が接する点で、視差分布は連続 (同一視差値をとる)
𝑔
𝑜
上側の視差が大きい(=手前側にある)確率は低い
そうでないと物体が地面に埋まっていることになるため
Copyright © Fixstars Group
23


# Page. 25

![Page Image](https://bcdn.docswell.com/page/L7358X24E5.jpg)

アルゴリズムの概要と発展
視差画像
⚫ 入力データの縮約
○
○
入力視差画像を水平方向に、Stixel幅𝑤𝑆 で分割
各列について、水平方向に縮約 (平均値や中央値をとる)
⚫ 垂直方向のセグメンテーション
○
○
縮約後の各列について、垂直方向にセグメンテーション
最後に元画像の座標に復元
水平方向の縮約
縮約画像
⚫ セグメンテーション手法は何度か発展あり
○
○
○
○
Single Layer Stixels
Multi Layer Stixels
Semantic Stixels
Slanted Stixels
垂直方向のセグメンテーション
+座標の復元
Stixel
※以降は縮約後の1つの列に対する処理に注目して解説
Copyright © Fixstars Group
24


# Page. 26

![Page Image](https://bcdn.docswell.com/page/87DDM2Z57G.jpg)

Single Layer Stixels
⚫ Free Space検出とHeight Segmentationで構成
⚫ 1列につき、最大1つのStixelを検出可能
𝒗𝑻
Height Segmentation
•
𝑣𝐵 を下端として、視差一定と
見なせる区間の上端𝑣𝑇 を推定
𝒗𝑩 ～𝒗𝑻 の区間を
Stixelとして出力
𝒗𝑩
Free Space検出
•
画像下端側から最初に見つかる
路面と物体の境界𝑣𝐵 を推定
Single Layer Stixels (図は[2]から引用)
Copyright © Fixstars Group
25


# Page. 27

![Page Image](https://bcdn.docswell.com/page/VJPXR1DD78.jpg)

Multi Layer Stixels
⚫ Stixel検出を区間分割問題として再定義
○
分割の妥当性を測る目的関数を導入
○
動的計画法による目的関数の最小化
⚫ 1列から複数のStixelを検出可能
区間分割問題
• 0～ℎの範囲に任意個数の
仕切りを置くことができる
• 視差モデル+事前知識
に最も合致する分割を推定
Multi Layer Stixels (図は[3]から引用)
Copyright © Fixstars Group
26


# Page. 28

![Page Image](https://bcdn.docswell.com/page/2EVLRY1GJQ.jpg)

Semantic Stixels
⚫ 視差とSemantic Segmentation(SS)を相補的に活用 (Joint Optimization)
○
SSの分類確率によってgeometricクラスの分類を補強
○
視差によってsemanticクラスの分類を補強
Semantic Segmentationの推論結果を入力
ピクセルごとに各semanticクラスの
分類確率を保持した状態
Joint Optimizationの効果 (図は[4]より抜粋)
• semantic 1st：SSの結果からStixel検出し、Stixel毎の視差モデルを推定．SSの分類ミスが残っている(赤点線)
• depth 1st：視差のみでStixel検出し、Stixel毎のsemanticクラスを推定．SS単体にあった細かいセグメントが消失
• ours(Semantic Stixels)：Joint Optimizationにより、細かいセグメントを保存しつつ、SSの分類ミスを補正
Copyright © Fixstars Group
27


# Page. 29

![Page Image](https://bcdn.docswell.com/page/57GXM98DEL.jpg)

Slanted Stixels
⚫ Semantic Stixelsをベースとし、視差モデルを拡張
新旧モデルの比較 (図は[5]より抜粋)
• 従来モデル (上)：物体の視差は𝑣に寄らず一定．路面は大域的な1種類の視差モデルしかもたない
• 新規モデル (下)：区間ごとに、それにフィットする直線 𝑓 𝑣 = 𝛼𝑣 + 𝛽 を推定．シーンの表現能力が向上
Copyright © Fixstars Group
28


# Page. 30

![Page Image](https://bcdn.docswell.com/page/4EQ8RW9XJP.jpg)

目的関数の設計
⚫ v-disparity空間を、𝑣方向に𝑛個のStixelに分割
⚫ ある組み合わせ𝑆 = 𝒔1 , 𝒔2 , … , 𝒔𝑛 に対する、目的関数を定義
𝒔5
𝒔4
𝒔3
Stixel 𝒔 の属性
𝒔 = 𝑣𝐵 , 𝑣𝑇 , 𝑐, 𝑓𝑐 𝑣 ,𝑙
𝑣𝐵 , 𝑣𝑇
𝒔2
𝒔1
𝑐 ∈ 𝑔, 𝑜
Stixelの下端/上端座標
geometricクラス(路面 or 物体)※
𝑓𝑐 𝑣
視差モデル
𝑙∈𝐿
semanticクラス
※説明の簡略化のため、 geometricクラスの内、空を除外します (理論の一般性は失いません)
Copyright © Fixstars Group
29


# Page. 31

![Page Image](https://bcdn.docswell.com/page/KJ428KX2E1.jpg)

目的関数の設計
⚫ 目的関数はデータ項(Data Term)と事前項(Prior Term)から構成
データ項： 𝐸𝐷 𝒔𝑘 , 𝒎
𝒔𝑘 の観測データ𝒎への当てはまり度合
事前項：𝐸𝑃 𝒔𝑘 , 𝒔𝑘−1
連続する2つのStixelの遷移の妥当性
目的関数： 𝐸 𝑆
全てのデータ項と事前項を足し合わせたもの
𝒔5 → 𝐸𝐷 𝒔5 , 𝒎
𝐸𝑃 𝒔5 , 𝒔4
𝒔4 → 𝐸𝐷 𝒔4 , 𝒎
𝒔3 → 𝐸𝐷 𝒔3 , 𝒎
𝐸𝑃 𝒔4 , 𝒔3
𝐸𝑃 𝒔3 , 𝒔2
𝑛
𝐸 𝑆 = 𝐸𝐷 𝒔1 + ෍ 𝐸𝐷 𝒔𝑘 + 𝐸𝑃 𝒔𝑘 , 𝒔𝑘−1
𝑘=2
𝒔2 → 𝐸𝐷 𝒔2 , 𝒎
𝐸𝑃 𝒔2 , 𝒔1
𝒔1 → 𝐸𝐷 𝒔1 , 𝒎
Copyright © Fixstars Group
30


# Page. 32

![Page Image](https://bcdn.docswell.com/page/LE1M2XNK7G.jpg)

データ項の詳細
⚫ データ項𝐸𝐷 𝒔, 𝒎 は、さらに𝐸disp 𝒔, 𝑫 と𝐸sem 𝒔, 𝑷 から構成
𝐸𝐷 𝒔, 𝒎 = 𝐸disp 𝒔, 𝑫 + 𝑤sem 𝐸sem 𝒔, 𝑷
視差データ項：𝐸disp 𝒔, 𝑫
𝒔の視差モデル𝑓𝑐 𝑣 に対する、観測視差
𝑫の当てはまり度合
Copyright © Fixstars Group
Semanticデータ項：𝐸sem 𝒔, 𝑷
Semantic Segmentationの推論𝑷の元で、
𝒔がクラス𝑙に所属している度合
31


# Page. 33

![Page Image](https://bcdn.docswell.com/page/GEW3RN4PE2.jpg)

𝐸disp 𝒔, 𝑫 の計算
⚫ 𝒔に対してある𝑣𝐵 , 𝑣𝑇 , 𝑐が与えられているとする
⚫ この時、𝑓𝑐 𝑣 のパラメータ𝑎, 𝑏に関する誤差関数を次のように定義する
○
𝑣𝑇
𝐸plane 𝑎, 𝑏 = σ𝑣=𝑣
𝑤 𝑑𝑣 − 𝑎𝑣 + 𝑏
𝐵 𝑣
2
+ 𝑤𝑎2 𝑎 − 𝜇𝑐𝑎
重み付き最小二乗の項
• 観測視差𝑑𝑣 とモデル𝑎𝑣 + 𝑏との2乗誤差に重み𝑤𝑣 をかけたもの
• 重み𝑤𝑣 はステレオマッチングの信頼度等を反映
2
+ 𝑤𝑏2 𝑏 − 𝜇𝑐𝑏
2
解に対する事前情報
• 𝜇𝑐𝑎 , 𝜇𝑐𝑏 に近い解が推定されるようにする拘束．𝑐毎に設定(下表)
• 𝑤𝑎2 , 𝑤𝑏2 は拘束の強さ
⚫ 𝐸plane 𝑎, 𝑏 を最小化する𝑎∗ , 𝑏 ∗ を視差モデル𝑓𝑐 𝑣 、誤差関数値𝐸plane 𝑎∗ , 𝑏 ∗ を
視差のデータ項𝐸disp 𝒔, 𝑫 とする
直線パラメータに対する事前情報
路面
カメラの設置高さ・傾きから𝜇𝑔𝑎 , 𝜇𝑔𝑏 を設定
物体
𝜇𝑜𝑎 = 0(傾き0)、𝜇𝑜𝑏 は拘束なし(𝑤𝑏2 = 0)
空
Copyright © Fixstars Group
𝜇𝑠𝑎 = 0, 𝜇𝑠𝑏 = 0
32


# Page. 34

![Page Image](https://bcdn.docswell.com/page/47ZVR326E3.jpg)

𝐸sem 𝒔, 𝑷 の計算
⚫ 𝒔に対してある𝑣𝐵 , 𝑣𝑇 , 𝑐が与えられているとする
⚫ Semantic Segmentation最終層、分類直前の特徴マップを用意
○
特徴マップの次元 = クラス数×画像高さ×画像幅
○
チャネル𝑙の各ピクセル𝑃𝑙 𝑣 は、そのクラスに属する分類確率を表すよう規格化
○
視差画像と同様の縮約処理を適用
⚫ 𝑃𝑙 𝑣 の負の対数※の区間和を𝐸CE 𝒔, 𝑷, 𝑙 とする
○
𝑣
𝑇
𝐸CE 𝒔, 𝑷, 𝑙 = σ𝑣=𝑣
− log 𝑃𝑙 𝑣
𝐵
※規格化(Softmax)と負の対数を合わせて、Cross Entropy Loss(CE loss)というloss関数になる
Copyright © Fixstars Group
33


# Page. 35

![Page Image](https://bcdn.docswell.com/page/YJ65RXVL7V.jpg)

𝐸sem 𝒔, 𝑷 の計算
⚫ 𝑐に対応するsemanticクラス集合𝐿𝑐 を作成 (下表)
⚫ 𝐿𝑐 に属する𝑙について𝐸CE 𝒔, 𝑷, 𝑙 を計算、最小のものを𝐸sem 𝒔, 𝑷 とする
𝑣
○
𝑇
𝐸sem 𝒔, 𝑷 = min𝑐 𝐸CE 𝒔, 𝑷, 𝑙 = min𝑐 σ𝑣=𝑣
− log 𝑃𝑙 𝑣
𝐵
○
geomtricクラスが路面であれば、路面に属するsemanticクラス(Road,Sidewalk,Terrain)の
𝑙∈𝐿
𝑙∈𝐿
各区間和の内、最小のものを選択
⚫ 同時に、最小値をとった𝑙 ∗ を、そのStixelのsemanticクラスとする
クラス集合
説明
クラス要素(Cityscapes dataset)
𝐿𝑔
路面に属するsemanticクラスの集合
Road,Sidewalk,Terrain
𝐿o
物体に属するsemanticクラスの集合
Building,Wall,Fence,Pole,TrafficLight,
TrafficSign,Vegetation,Person,Rider,C
ar,Truck,Bus,Train,Motorcycle,Bicycle
𝐿s
空に属するsemanticクラスの集合
Sky
Copyright © Fixstars Group
34


# Page. 36

![Page Image](https://bcdn.docswell.com/page/GJ5Y8XDMJ4.jpg)

データ項のまとめ
⚫ データ項𝐸𝐷 𝒔, 𝒎 は、𝐸disp 𝒔, 𝑫 と𝐸sem 𝒔, 𝑷 から構成される
⚫ 𝑣𝐵 , 𝑣𝑇 , 𝑐が与えらるとデータ項が決まる
⚫ 𝐸disp 𝒔, 𝑫 は𝑓𝑐 𝑣 の推定とセットになっている
⚫ 𝐸sem 𝒔, 𝑷 は𝑙の推定とセットになっていて、𝑐の分類を補強する
○
Semantic Segmentationの分類確率が、路面 or 物体の判断に寄与
○
𝑤sem は寄与度を調節する重み
Stixel 𝒔 の属性
𝒔 = 𝑣𝐵 , 𝑣𝑇 , 𝑐, 𝑓𝑐 𝑣 ,𝑙
𝐸𝐷 𝒔, 𝒎 = 𝐸disp 𝒔, 𝑫 + 𝑤sem 𝐸sem 𝒔, 𝑷
𝑣𝐵 , 𝑣𝑇
𝑐 ∈ 𝑔, 𝑜
Copyright © Fixstars Group
Stixelの下端/上端座標
geometricクラス(路面 or 物体)
𝑓𝑐 𝑣
視差モデル
𝑙∈𝐿
semanticクラス
35


# Page. 37

![Page Image](https://bcdn.docswell.com/page/9E2GKX8RER.jpg)

事前項𝐸𝑃 𝒔𝑘 , 𝒔𝑘−1 の計算
⚫ 2つのStixelの視差モデルの組み合わせに応じて𝐸𝑃 𝒔𝑘 , 𝒔𝑘−1 を定義
geometricクラスの組
𝑐𝑘
𝑐𝑘−𝟏
境界部分の視差の関係
意味
o
o
𝑑𝑘 &gt; 𝑑𝑘−1 + ∆
大
上側のStixelが手前側
物体が浮いていることになり起こりにくい
o
o
𝑑𝑘 &lt; 𝑑𝑘−1 − ∆
小
上側のStixelが奥側
o
o
𝑑𝑘 − 𝑑𝑘−1 ≤ 2∆
小
境界で視差値が連続している
o
g
𝑑𝑘 &gt; 𝑑𝑘−1 + 𝜀
大
上側のStixelが手前側
物体が地面から浮いていることになり起こりにくい
o
g
𝑑𝑘 &lt; 𝑑𝑘−1 − 𝜀
大
上側のStixelが奥側
物体が地面に沈んでいることになり起こりにくい
o
g
𝑑𝑘 − 𝑑𝑘−1 ≤ 2𝜀
小
境界で視差値が連続している
𝐸𝑃 𝒔𝑘 , 𝒔𝑘−1
具体的な𝐸𝑃 𝒔𝑘 , 𝒔𝑘−1 の定義は[3,7]等を参照のこと (論文によって定義はまちまち)
Copyright © Fixstars Group
36


# Page. 38

![Page Image](https://bcdn.docswell.com/page/D7YVN8657M.jpg)

モデルの複雑度 (model complexity)
⚫ 遷移(=分割)そのものに一定のペナルティ𝛽mc を足す
⚫ モデルの複雑度をコントロール
𝐸𝑃 𝒔𝑘 , 𝒔𝑘−1 + 𝛽mc
オーバーフィッティング
Copyright © Fixstars Group
モデルを単純化
37


# Page. 39

![Page Image](https://bcdn.docswell.com/page/VENMXQZ4J8.jpg)

解法
⚫ 𝐸 𝑆 を最小化する𝑆 = 𝒔1 , 𝒔2 , … , 𝒔𝑛 を求めたい
○
分割の組み合わせは膨大だが、どうやって解けばよいだろうか?
⚫ 問題の構造に着目
○
問題Aの最適解は、問題Bの最適解を含んでいる
○
動的計画法が使えそう！
問題Aの最適解
問題Bの最適解
Copyright © Fixstars Group
38


# Page. 40

![Page Image](https://bcdn.docswell.com/page/Y79N8DZ473.jpg)

動的計画法 (単純版)
⚫ まずは以下の単純化を行って説明
○
Stixelのgeometricクラスは1種類
○
データ項𝐸D 𝒔 は下端/上端座標のみによって決まる
■ 𝐸D 𝒔 = 𝐸D 𝑣𝐵 , 𝑣𝑇
事前項𝐸P 𝒔𝑘 , 𝒔𝑘−1 は考えない
○
𝑣∗
∗
𝑇E 𝑣 ∗ = 𝐸 𝑆opt
⚫ 用意するデータ構造
○
○
コストテーブル𝑇E 𝑣
■ 𝑣を画像上端としたときの、目的関数の最小値を保存
インデックステーブル𝑇I 𝑣
■ 上端𝑣𝑇 = 𝑣であるStixelの下端座標𝑣𝐵 について、𝑣𝐵 − 1を保存
■ 遷移元 𝒔𝑘−1 の上端座標に等しい
Copyright © Fixstars Group
𝑇I 𝑣 ∗
39


# Page. 41

![Page Image](https://bcdn.docswell.com/page/G78K831VJD.jpg)

動的計画法 (単純版)：Forward Step
(1) 画像上端𝒉∗ を𝒉∗ = 𝟏とした問題を解く
• 上端𝑣𝑇 = ℎ∗ = 1のStixelに対し、
下端𝑣𝐵 の取り方は1通り
• コストを計算
(2) 画像上端𝒉∗ を𝒉∗ = 𝟐とした問題を解く
• 上端𝑣𝑇 = ℎ∗ = 2のStixelに対し、
下端𝑣𝐵 の取り方は2通り
• それぞれコストを計算
𝑣𝑇 = 2
𝑣𝐵 = 1
𝑣𝑇 = 2
𝑣𝐵 = 2
𝐸D 1,2
𝐸D 2,2 + 𝑇E 1
(3) 画像上端𝒉∗ を𝒉∗ = 𝟑とした問題を解く
• 上端𝑣𝑇 = ℎ∗ = 3のStixelに対し、
下端𝑣𝐵 の取り方は3通り
• それぞれコストを計算
𝑣𝑇 = 3
𝑣𝐵 = 1
𝑣𝑇 = 3
𝑣𝐵 = 2
𝑣𝑇 = 3
𝑣𝐵 = 3
𝐸D 1,3
𝐸D 2,3 + 𝑇E 1
𝐸D 3,3 + 𝑇E 2
𝑣𝑇 = 1
𝑣𝐵 = 1
𝐸D 1,1
最小コスト𝐸 ∗ = 𝐸D 1,1 、その時の下端
𝑣𝐵∗ = 1
•
•
𝑇E 1 に𝐸D 1,1 を記録
𝑇I 1 に𝑣𝐵∗ − 1 = 0を記録
最小コスト𝐸 ∗ 、その時の下端𝑣𝐵∗ を選択
•
•
𝑇E 2 に𝐸 ∗ を記録
𝑇I 2 に𝑣𝐵∗ − 1を記録
最小コスト𝐸 ∗ 、その時の下端𝑣𝐵∗ を選択
•
•
𝑇E 3 に𝐸 ∗ を記録
𝑇I 3 に𝑣𝐵∗ − 1を記録
以下同様に、𝒉∗ = 𝒉まで繰り返す
Copyright © Fixstars Group
40


# Page. 42

![Page Image](https://bcdn.docswell.com/page/L7LZRVQRER.jpg)

動的計画法 (単純版)：Backtracking Step
⚫ 一番上のStixelを復元
○
上端は𝑣𝑇1 = ℎ、下端は𝑣𝐵1 = 𝑇I 𝑣𝑇1 + 1
⚫ その下のStixelを復元
○
上端は𝑣𝑇2 = 𝑇I 𝑣𝑇1 、下端は𝑣𝐵2 = 𝑇I 𝑣𝑇2 + 1
𝑣𝑇1 = ℎ
⚫ 以下同様に𝑇I 𝑣𝑇𝑛 = 0となるまで繰り返す
𝑣𝑇2 = 𝑇I 𝑣𝑇1
𝑣𝑇3 = 𝑇I 𝑣𝑇2
𝑣𝑇4 = 𝑇I 𝑣𝑇3 = 0 → 終了
Copyright © Fixstars Group
41


# Page. 43

![Page Image](https://bcdn.docswell.com/page/4EMVRG1PEW.jpg)

動的計画法 (詳細版)
𝑇E 𝑣 ∗ , 𝑔
g
⚫ 本来の問題設定に近づける
o
𝑣∗
○
Stixelのgeometricクラスは2種類 (𝑐 ∈ 𝑔, 𝑜 )
○
データ項𝐸D 𝑠 は𝑣𝐵 , 𝑣𝑇 , 𝑐によって決まる
■ 𝐸D 𝑠 = 𝐸D 𝑣𝐵 , 𝑣𝑇 , 𝑐
事前項𝐸P 𝑠𝑘 , 𝑠𝑘−1 を考慮
○
𝑇E 𝑣 ∗ , 𝑜
⚫ 用意するデータ構造
○
○
コストテーブル𝑇E 𝑣, 𝑐
■ 𝑣を画像上端としたときの、目的関数の最小値を保存
■ ただし、画像上端に位置するStixelのgeometricクラスに応じて、2通りの状態を保持する
インデックステーブル𝑇I 𝑣, 𝑐
■ 遷移元 𝒔𝑘−1 の上端座標およびgeometricクラスのペアを保存
Copyright © Fixstars Group
42


# Page. 44

![Page Image](https://bcdn.docswell.com/page/PER2RZLY79.jpg)

動的計画法 (詳細版)：Forward Step
⚫ (1.1)：画像上端𝑣𝑇 を𝑣𝑇 = 1、上端Stixelのクラスを𝑜とした問題を解く
○
分割の仕方は1通りで、コスト𝐸D 1,1, 𝑜 が最小コスト
○
𝑇E 1, 𝑜 に最小コストを記録
○
𝑇I 1, 𝑜 に 0, None を記録
⚫ (1.2)：画像上端𝑣𝑇 を𝑣𝑇 = 1、上端Stixelのクラスを𝑔とした問題を解く
○
同様に𝑇E 1, 𝑔 , 𝑇I 1, 𝑔 をそれぞれ更新
o
g
step1
分割の仕方は1通り、2つのgeometricクラス
Copyright © Fixstars Group
43


# Page. 45

![Page Image](https://bcdn.docswell.com/page/P7XDR9W4JX.jpg)

動的計画法 (詳細版)：Forward Step
⚫ (2.1)：画像上端𝑣𝑇 を𝑣𝑇 = 2、上端Stixelのクラスを𝑜とした問題を解く
○
𝑣𝑇 = 2のStixelに対し、自身への遷移のパターンは3通り、そのうちの最小コストを計算
a. 𝑣𝐵 = 1：分割しないパターン、コスト𝐸D 1,2, 𝑜 を計算
b. 𝑣𝐵 = 2, 𝑜 → 𝑜：コストは𝐸D 2,2, 𝑜 + 𝑇E 1, 𝑜 + 𝐸P 𝒔𝑘 , 𝒔𝑘−1
c. 𝑣𝐵 = 2, 𝑔 → 𝑜：コストは𝐸D 2,2, 𝑜 + 𝑇E 1, 𝑔 + 𝐸P 𝒔𝑘 , 𝒔𝑘−1
○
𝑇E 2, 𝑜 に最小コストを記録
○
𝑇I 2, 𝑜 に最小コストをとった(下端𝑣𝐵 − 1、遷移元クラス)のペアを𝑇B 2, 𝑜 に記録
⚫ (2.2)：画像上端𝑣𝑇 を𝑣𝑇 = 2、上端Stixelのクラスを𝑔とした問題を解く
○
同様に𝑇E 2, 𝑔 , 𝑇I 2, 𝑔 をそれぞれ更新
⚫ 以下同様に𝑣𝑇 = ℎまで繰り返す
o
a.
o
o
o
g
b.
c.
g
d.
g
g
o
g
e.
f.
step2
遷移パターンは6通り
Copyright © Fixstars Group
44


# Page. 46

![Page Image](https://bcdn.docswell.com/page/37KXRPVPJD.jpg)

動的計画法 (詳細版)：Backtracking Step
⚫ 一番上のStixelを復元
○
クラス𝑐 1 は𝑐 1 = argmin 𝑇E ℎ, 𝑐
○
上端は𝑣𝑇1
𝑐∈ 𝑜,𝑔
= ℎ、遷移元が 𝑣𝑇2 , 𝑐 2 = 𝑇I 𝑣𝑇1 , 𝑐 1 より、下端𝑣𝐵1 は𝑣𝑇2 + 1
⚫ その下のStixelを復元
o
○
上端およびクラスは 𝑣 𝑇2 , 𝑐 2 = 𝑇I 𝑣𝑇1 , 𝑐 1
○
遷移元が
𝑣𝑇3 , 𝑐 3
=
𝑇I 𝑣 𝑇2 , 𝑐 2
より、下端𝑣𝐵2 は𝑣𝑇3
g
𝑣𝑇1 , 𝑐1 = ℎ, argmin 𝑇E ℎ, 𝑐
𝑐∈ 𝑜,𝑔
+1
⚫ 以下同様に𝑇I 𝑣𝑇𝑛 , 𝑐 𝑛 = 0, None まで繰り返す
𝑣𝑇2 , 𝑐 2 = 𝑇I 𝑣𝑇1 , 𝑐1
𝑣𝑇3 , 𝑐 3 = 𝑇I 𝑣𝑇2 , 𝑐 2
𝑣𝑇4 , 𝑐 4 = 𝑇I 𝑣𝑇3 , 𝑐 3 = 0, None
Copyright © Fixstars Group
45


# Page. 47

![Page Image](https://bcdn.docswell.com/page/LJ358XM475.jpg)

DP部の疑似コード
def DP(...):
DP_table = [Segment()] * h
for vT = 1 to h:
for vB = 1 to vT:
# fit line and get it&#039;s error
f[G], E_disp[G] = fit_line_grd(disp, vB, vT)
f[O], E_disp[O] = fit_line_obj(disp, vB, vT)
データ項計算
# find minimum interval sum of semantic loss and it&#039;s label
l[G], E_sem[G] = find_min_semantic_loss(sem_probs, vB, vT, L_grd)
l[O], E_sem[O] = find_min_semantic_loss(sem_probs, vB, vT, L_obj)
# calculate data term
E_data[G] = E_disp[G] + w_sem*E_sem[G]
E_data[O] = E_disp[O] + w_sem*E_sem[O]
# candidate of &quot;no segmentation&quot;
if vB == 1:
best_segment = Segment(E=E_data, f=f, l=l, p=None)
continue
分割しないパターン
# update best segment
for CT, CB in [ (G,G), (G,O), (O,G), (O,O) ]:
prev_segment = DP_table[vB-1]
prior_term = calc_prior_term(CT, CB, f[CT], prev_segment.f[CB])
E_total = E_data[CT] + prior_term + prev_segment.E[CB]
if E_total &lt; best_segment.E[CT]:
best_segment.E[CT] = E_total
best_segment.f[CT] = f[CT]
best_segment.l[CT] = l[CT]
best_segment.p = (vB,CB) # 遷移元
CB(下)→CT(上)への
遷移パターンの評価
DP_table[vT] = best_segment
Copyright © Fixstars Group
46


# Page. 48

![Page Image](https://bcdn.docswell.com/page/8JDDM265JG.jpg)

計算量と高速化
⚫ 計算量
○
○
計算量はナイーブ実装でΟ 𝑤ℎ3
このままだとリアルタイム動作には厳しい
⚫ 高速化のアプローチ
○
○
○
𝑤
列のループ
𝑢 = 1~𝑤
ℎ1
上端のループ
𝑣𝑇 = 1~ℎ
ℎ2
下端のループ
𝑣𝐵 = 1~𝑣𝑇
ℎ3
データ項𝐸D 𝑣𝐵 , 𝑣𝑇 の計算
𝑣 = 𝑣𝐵 ~𝑣𝑇
列のループを並列化
■ 列ごとにデータの依存なし
データ項の計算におけるSummed Area Table(SAT)※の利用
■ データ項𝐸D 𝑣𝐵 , 𝑣𝑇 の計算がΟ 1 に
■ 詳細は次頁
※ Summed Area Table
• 累積和のテーブル、区間和をO(1)で計算可能
𝑣方向の縮約
• Prefix Sumとも呼ばれる
■ 前処理の縮約時に𝑣方向にも縮約
y0 = x0
■ 解像度を犠牲に負荷を大きく下げることができる
y1 = x0 + x1
y2 = x0 + x1 + x2
...
Copyright © Fixstars Group
47


# Page. 49

![Page Image](https://bcdn.docswell.com/page/VEPXR1YDJ8.jpg)

データ項の計算におけるSATの利用
⚫ 視差モデルの誤差関数を再掲
○
𝑣𝑇
𝐸plane 𝑎, 𝑏 = σ𝑣=𝑣
𝑤 𝑑𝑣 − 𝑎𝑣 + 𝑏
𝐵 𝑣
2
+ 𝑤𝑎2 𝑎 − 𝜇𝑐𝑎
2
+ 𝑤𝑏2 𝑏 − 𝜇𝑐𝑏
2
⚫ 整理すると、2×2の線形方程式に帰着
○
○
𝑠𝑥𝑦 + 𝑤𝑎2 𝜇𝑎
𝑠𝑥𝑥 + 𝑤𝑎2
𝑠𝑥
𝑎
=
𝑠𝑥
𝑠𝑤 + 𝑤𝑏2 𝑏
𝑠𝑦 + 𝑤𝑏2 𝜇𝑏
𝑣𝑇
𝑣𝑇
𝑣𝑇
𝑣𝑇
𝑣𝑇
𝑇
■ 𝑠𝑥 = σ𝑣𝑣=𝑣
𝑤 𝑣 , 𝑠𝑥𝑥 = σ𝑣=𝑣
𝑤 𝑣 2 , 𝑠𝑦 = σ𝑣=𝑣
𝑤 𝑑 , 𝑠𝑦𝑦 = σ𝑣=𝑣
𝑤 𝑑 2 , 𝑠𝑥𝑦 = σ𝑣=𝑣
𝑤 𝑣𝑑𝑣 , 𝑠𝑤 = σ𝑣=𝑣
𝑤
𝐵 𝑣
𝐵 𝑣
𝐵 𝑣 𝑣
𝐵 𝑣 𝑣
𝐵 𝑣
𝐵 𝑣
行列の要素は区間和となっており、それぞれのSATを作成することでΟ 1 で計算可能
⚫ 同様に、Semantic SegmentationのCE Lossについても、各チャネルのSAT
を作成することでΟ 1 で区間和を計算可能
Copyright © Fixstars Group
48


# Page. 50

![Page Image](https://bcdn.docswell.com/page/27VLRYGGEQ.jpg)

実装してみた
⚫ ステレオマッチング
○
libSGMを使用
⚫ Semantic Segmentation
○
○
ERFNetを使用
■ 2017年に提案されたリアルタイム向けの軽量モデル
Cityscapes(20クラス)の学習済みモデルを用いて推論
⚫ Slanted Stixels
○
[5,6,7]を参考にCUDAで実装
○
CUDA実装内容や処理時間は次章で解説
libSGM：github.com/fixstars/libSGM
ERFNet： github.com/Eromera/erfnet_pytorch
Copyright © Fixstars Group
49


# Page. 51

![Page Image](https://bcdn.docswell.com/page/5JGXMWDD7L.jpg)

実装結果
視差画像
Slanted Stixels (depth 表示)
Semantic Segmentation
Copyright © Fixstars Group
Slanted Stixels (semantic 表示)
50


# Page. 52

![Page Image](https://bcdn.docswell.com/page/47Q8R31XEP.jpg)

所感
⚫ 視差の欠損についてはSemantic Segmentationの補助もあり、
うまく補間できていそう
⚫ Semantic Segmentationの分類ミスはあまり補正できていない
○
𝑤sem (Semantic Segmentationの寄与)の調整が難しい
○
分類ミスの領域が広すぎると、周囲から修正できない
Semantic Segmentation
Slanted Stixels
Copyright © Fixstars Group
51


# Page. 53

![Page Image](https://bcdn.docswell.com/page/KE4281R271.jpg)

2. Stixel検出のCUDA実装
Copyright © Fixstars Group


# Page. 54

![Page Image](https://bcdn.docswell.com/page/L71M2GQKJG.jpg)

CUDAの簡単なおさらい
⚫ スレッドおよびメモリの階層
スレッドの階層構造
• スレッド間に階層構造がある
• 近いスレッド同士はより密に通信・同期を行うことができる
メモリの階層構造
• おおむねスレッドの階層構造と対応
Fixstars CUDA高速化セミナーvol.1 ～画像処理アルゴリズムの高速化～ より抜粋
https://www.docswell.com/s/fixstars/K24MYM-20220527
Copyright © Fixstars Group
53


# Page. 55

![Page Image](https://bcdn.docswell.com/page/G7W3RKMP72.jpg)

CUDA化の対象の処理と実装方針
⚫ CUDA化の対象の処理
○
入力データの縮約+転置
○
SAT(Summed Area Table)の計算
○
Dynamic Programming (DP)
⚫ GPU実装の論文[6]を参考に実装
○
ソースコードそのものは公開されておらず、所々推測で実装
Copyright © Fixstars Group
54


# Page. 56

![Page Image](https://bcdn.docswell.com/page/4JZVRZQ673.jpg)

入力データの縮約+転置
⚫ 処理概要
○
Stixelの解像度を𝑘 × 𝑘とする (論文では 𝑘 = 4 or 𝑘 = 8)
○
入力データ※を𝑘 × 𝑘領域で分割、領域内の平均値をとって幅・高さをそれぞれ1Τ𝑘に縮小
○
出力に転置して格納
■ DPで𝑣方向に頻繁にアクセスするため、 𝑣方向にメモリが連続するように
⚫ 1スレッドで𝑘 × 𝑘領域の平均を計算
𝑘
𝑘
1
1
0
1
2
3
平均
1
※入力データ
視差画像および、Semantic
Segmentationの特徴マップ
0
2
3
入力データ
出力データ
Copyright © Fixstars Group
55


# Page. 57

![Page Image](https://bcdn.docswell.com/page/YE65RZ6LJV.jpg)

SAT(Summed Area Table)の計算
⚫ 処理概要
○
縮約+転置後のデータの各列について、Prefix Sumを計算
⚫ 1列に1warp(32スレッド)を割り当て
○
Warp Shuffleを用いて並列にPrefix Sumを計算 (次頁)
1warp
𝑥0 , 𝑥1 , 𝑥2 , …
𝑥0 , 𝑥0 + 𝑥1 , 𝑥0 + 𝑥1 + 𝑥2 , …
…
…
…
…
…
…
入力データ
出力データ
Copyright © Fixstars Group
56


# Page. 58

![Page Image](https://bcdn.docswell.com/page/GE5Y8W6ME4.jpg)

Warp Shuffleによる並列Prefix Sum
⚫ __shfl_up_syncを用いて、左lane※の値を自身に足していく
※lane
• warp内の各スレッドのこと
• lane id(0～31)によって識別
step1：lane id≧1のスレッドは、1つ左のレーンの値を自分自身に足す
x0
x1
x2
x3
x4
x5
x6
x7
…
x0
x1
x2
x3
x4
x5
x6
…
step2：lane id≧2のスレッドは、2つ左のレーンの値を自分自身に足す
Warp Shuffleによる並列Prefix Sumの実装例
x0
x1
x2
x3
x4
x5
x6
x7
…
x0
x1
x2
x3
x4
x5
x6
…
x0
x1
x2
x3
x4
x5
…
x0
x1
x2
x3
x4
…
step3：lane id≧4のスレッドは、4つ左のレーンの値を自分自身に足す
…
step5：lane id≧16のスレッドは、16個左のレーンの値を自分自身に足す
→完了
template &lt;typename T&gt;
__device__ inline T warpPrefixSum(T value, int lane)
{
#pragma unroll
for (int i = 1; i &lt; WARP_SIZE; i &lt;&lt;= 1)
{
const T n = __shfl_up_sync(0xffffffff, value, i);
if (lane &gt;= i) value += n;
}
return value;
}
Copyright © Fixstars Group
57


# Page. 59

![Page Image](https://bcdn.docswell.com/page/972GKQMR7R.jpg)

Warp Shuffleによる並列Prefix Sum
⚫ 長さ32以上の配列に対しては、 Warp Prefix Sumを順次適用
○
現在注目している32要素を処理したら、末尾要素の値を各レーンにBroadcast※し、
次の32要素の初期値に使用
入力データ
𝑥0 , 𝑥1 , 𝑥2 , … 𝑥31
𝑥32 , 𝑥33 , 𝑥34 , … 𝑥63
𝑦31 + Prefix Sum
Prefix Sum
𝑦0 , 𝑦1 , 𝑦2 , … 𝑦31
𝑦63 + Prefix Sum
Broadcast
Broadcast
出力データ
𝑥64 , 𝑥65 , 𝑥66 , … 𝑥95
𝑦32 , 𝑦33 , 𝑦34 , … 𝑦63
𝑦64 , 𝑦65 , 𝑦66 , … 𝑦95
※Broadcast
• 同じ値を各スレッドにコピーする処理のこと
• Warp内でのBroadcastは__shfl_syncにより実現できる
Copyright © Fixstars Group
58


# Page. 60

![Page Image](https://bcdn.docswell.com/page/DJYVNWX5JM.jpg)

Dynamic Programming (DP)
⚫ 1つの列の処理に1ブロックを割り当て
○
1ブロック内ではhスレッドでDPを実行
h
col0
Segmantation by
DP
col1
hスレッドで実行
col2
...
...
...
...
colw-1
入力データ (縮約+転置後)
Copyright © Fixstars Group
59


# Page. 61

![Page Image](https://bcdn.docswell.com/page/V7NMX914E8.jpg)

DP部の疑似コード (再掲)
def DP(...):
DP_table = [Segment()] * h
for vT = 1 to h:
for vB = 1 to vT:
# fit line and get it&#039;s error
f[G], E_disp[G] = fit_line_grd(disp, vB, vT)
f[O], E_disp[O] = fit_line_obj(disp, vB, vT)
# find minimum interval sum of semantic loss and it&#039;s label
l[G], E_sem[G] = find_min_semantic_loss(sem_probs, vB, vT, L_grd)
l[O], E_sem[O] = find_min_semantic_loss(sem_probs, vB, vT, L_obj)
# calculate data term
E_data[G] = E_disp[G] + w_sem*E_sem[G]
E_data[O] = E_disp[O] + w_sem*E_sem[O]
# candidate of &quot;no segmentation&quot;
if vB == 1:
best_segment = Segment(E=E_data, f=f, l=l, p=None)
continue
# update best segment
for CT, CB in [ (G,G), (G,O), (O,G), (O,O) ]:
prev_segment = DP_table[vB-1]
prior_term = calc_prior_term(CT, CB, f[CT], prev_segment.f[CB])
E_total = E_data[CT] + prior_term + prev_segment.E[CB]
if E_total &lt; best_segment.E[CT]:
best_segment.E[CT] = E_total
best_segment.f[CT] = f[CT]
best_segment.l[CT] = l[CT]
best_segment.p = (vB,CB)
DP_table[vT] = best_segment
Copyright © Fixstars Group
60


# Page. 62

![Page Image](https://bcdn.docswell.com/page/YJ9N8254J3.jpg)

DP部のタスク
⚫ vT,vBの2重ループ
⚫ vBのループ回数がvTに従って増加
for vT = 1 to h:
for vB = 1 to vT:
DP_body()
vT
水色マスで有効なタスク
(DP_body)が発生
vB
Copyright © Fixstars Group
61


# Page. 63

![Page Image](https://bcdn.docswell.com/page/GJ8K85YVED.jpg)

DP部のスレッド割り当て
⚫ どちらかのループにh個のスレッドを割り当てる
○
白マスに対応するスレッドは何もしない
○
どちらのプランにしろスレッドの負荷はアンバランス…
⚫ メモリ効率の面で比較
○
DPテーブルの扱いに違いあり
vT
vT
vB
vB
プラン(A)：vBについて並列化
有効なタスクは1~hに増加
Copyright © Fixstars Group
プラン(B)：vTについて並列化
有効なタスクはh~1に減少
62


# Page. 64

![Page Image](https://bcdn.docswell.com/page/LJLZRY4R7R.jpg)

プラン(A)の場合
⚫ 各スレッドが、異なるDPテーブル要素を参照
⚫ DPテーブルをGlobal MemoryやShared Memoryに保持する必要あり
○
Global Memoryに置く：アクセスのレイテンシ大
○
Shared Memoryに置く：確保量が大きく、activeブロック数に制限、Occupancy低下※
vT
def DP(...):
DP_table = [Segment()] * h
for vT = 1 to h:
for vB = 1 to vT:
...中略...
# update best segment
for CT, CB in geom_combination:
prev_segment = DP_table[vB-1]
...中略...
vB
※Shared MemoryとOccupancy
Occupancy=GPU利用率の指標．
ブロック当たりのShared Memory使用量をM、
同時に実行できるブロック(activeブロック)
の数をNとすると、M×N ≦ Streaming
MultiprocessorのShared Memory容量
となるようNが決まる．従ってShared
Memory使用量が大きすぎるとactiveブロック
数が減少し、Occupancyが低下する．
DP_table[vT] = best_segment
DPテーブル
Copyright © Fixstars Group
63


# Page. 65

![Page Image](https://bcdn.docswell.com/page/47MVRNKP7W.jpg)

プラン(B)の場合
⚫ 各スレッドが、同じDPテーブル要素を参照
○
その要素は、直前のvBで計算したbest_segment
⚫ DPテーブルをメモリに保持する必要がない
○
直前の要素のみブロードキャストすればよい
vB=2
• 2番目のスレッドはDPを完了、
best_segmentをDPテーブルに書き込み
vB=3
• 各スレッドは直前のvBで計算した
best_segmentを参照
vT
vT
2
vB
vB
Broadcast
Copyright © Fixstars Group
64


# Page. 66

![Page Image](https://bcdn.docswell.com/page/P7R2RDXYJ9.jpg)

その他の高速化
⚫ SAT計算とDPの結合
○
SAT～DPまでの処理を一つの関数で実行
○
SATの結果をShared Memoryに配置することでメモリアクセス効率を向上
SAT計算
Shared Memory
Segmantation by
DP
hスレッドで実行
入力データ (縮約+転置後)
Copyright © Fixstars Group
65


# Page. 67

![Page Image](https://bcdn.docswell.com/page/PJXDR164EX.jpg)

Stixel検出の処理時間
⚫ 計測環境
GPU
Jetson AGX Xavier (clock：1377MHz 512 core)
入力画像サイズ
2048×1024
Stixel解像度
4×4と8×8について計測
⚫ 計測結果
○
Fixstars実装は論文報告値より0.5[msec]程度遅いが、概ね実装内容は合ってそうか
論文報告値[msec]
Fixstars実装[msec]
4×4
10.8
11.2
8×8
2.9
3.4
Copyright © Fixstars Group
66


# Page. 68

![Page Image](https://bcdn.docswell.com/page/3JKXR21PED.jpg)

前処理も含めた処理時間
⚫ 計測環境
GPU
Jetson AGX Xavier および GeForce RTX 3060 Ti
入力画像サイズ
1024×512
Stixel解像度
4×4
ステレオマッチング
libSGM を使用
Semantic Segmentation
ERFNetのONNXモデルをTensorRTでFP16でコンパイル
⚫ 計測結果
処理
Jetson AGX Xavier
処理時間[msec]
ステレオマッチング
Semantic Segmentation
Stixel検出
合計
Copyright © Fixstars Group
GeForce RTX 3060 Ti
処理時間[msec]
6.6
1.6
15.0
3.0
2.1
0.5
23.7
5.1
67


# Page. 69

![Page Image](https://bcdn.docswell.com/page/LE3584Q4J5.jpg)

今後の予定
⚫ さらなる高速化検討
⚫ Stixelの応用アプリケーションの開発
○
Stixelのクラスタリングによる3次元の物体検出
○
3次元上の物体追跡、位置速度の推定
○
etc.
⚫ ソースコードの公開
Copyright © Fixstars Group
68


# Page. 70

![Page Image](https://bcdn.docswell.com/page/8EDDMQ95EG.jpg)

参考文献
[1] Badino, Hernán, Uwe Franke, and David Pfeiffer. &quot;The stixel world-a compact medium level representation of the 3d-world.&quot;
Pattern Recognition: 31st DAGM Symposium, Jena, Germany, September 9-11, 2009. Proceedings 31. Springer Berlin Heidelberg, 2009.
[2] Pfeiffer, David, and Uwe Franke. &quot;Modeling dynamic 3D environments by means of the stixel world.&quot;
IEEE Intelligent Transportation Systems Magazine 3.3 (2011): 24-36.
[3] Pfeiffer, David, and Uwe Franke. &quot;Towards a Global Optimal Multi-Layer Stixel Representation of Dense 3D Data.&quot;
BMVC. Vol. 11. 2011.
[4] Schneider, Lukas, et al. &quot;Semantic stixels: Depth is not enough.&quot;
2016 IEEE Intelligent Vehicles Symposium (IV). IEEE, 2016.
[5] Hernandez-Juarez, Daniel, et al. &quot;Slanted stixels: Representing San Francisco&#039;s steepest streets.&quot;
arXiv preprint arXiv:1707.05397 (2017).
[6] Hernandez-Juarez, Daniel, et al. &quot;3D Perception With Slanted Stixels on GPU.&quot;
IEEE Transactions on Parallel and Distributed Systems 32.10 (2021): 2434-2447.
[7] Cordts, Marius, et al. &quot;The stixel world: A medium-level representation of traffic scenes.&quot;
Image and Vision Computing 68 (2017): 40-52.
Copyright © Fixstars Group
69


# Page. 71

![Page Image](https://bcdn.docswell.com/page/V7PXRLZDE8.jpg)

7
0
Thank you!
お問い合わせ窓口 : hr-seminar@fixstars.com
Copyright © Fixstars Group


