読者です 読者をやめる 読者になる 読者になる

おぺんcv

画像処理エンジニアのブログ

Free Space Computationを実装してみた

以前の記事で紹介したFree Space Computationですが
実装がひと段落したので公開することにしました

デモ

free space(走行可能領域)の推定結果を赤で塗ってます
まあなんとなく計算できてるような…?
なお、実際の処理時間は動画ほど速くありません

youtu.be

youtu.be

使い方

README.mdに記載しましたので
興味があれば使ってやって下さい

その他メモ

アルゴリズム

以前の記事で解説していますのでそちらをご参照ください
主に[1]の「B. Image Based Free Space Computation」を参考に実装しています

Road Disparity

[1]では路面上の視差をB-Splineでフィッティングして求めていますが
カメラパラメータから路面上の視差を計算する方法もあります([2]で知りました)
今回は計算が簡単なカメラパラメータを使う方法を採用しました

DPによる境界の計算

ここは割と推測で実装してる部分がありまして、あまり自身はありません
あと計算時間の都合上、かなり処理を端折ってる部分があります…

ARM NEONの使い方 加算編

四則演算編の予定でしたが、量が多いので分割することにしました
今回は加算編です

加算

vadd[q]_<type>(va, vb)

64bit(qが付く場合は128bit)のベクタvaとvbを足します
戻り値のサイズは入力のサイズと同じです

サンプル

符号付き16bit整数のベクタvaとvbをvadd_s16()で足してみます

#include <stdio.h>
#include <stdint.h>
#include <arm_neon.h>

int main()
{
	int16_t a[4] = { 1, -1, 1, -1 };
	int16_t b[4] = { 1, -1, 32767, -32768 };

	int16x4_t va = vld1_s16(a);
	int16x4_t vb = vld1_s16(b);
	int16x4_t vc = vadd_s16(va, vb);

	int16_t c[4];
	vst1_s16(c, vc);

	for (int i = 0; i < 4; i++)
		printf("c[%d]: %d\n", i, c[i]);

	return 0;
}
実行結果
c[0]: 2
c[1]: -2
c[2]: -32768
c[3]: 32767

3,4番目のレーンはオーバーフローしました

符号拡張+加算(long add)

vaddl_<type>(va, vb)

64bitのベクタvaとvbの各レーンのbit幅を倍に拡張して足します
戻り値のサイズは128bitになります

サンプル

符号付き16bit整数のベクタvaとvbをvaddl_s16()で足してみます

#include <stdio.h>
#include <stdint.h>
#include <arm_neon.h>

int main()
{
	int16_t a[4] = { 1, -1, 1, -1 };
	int16_t b[4] = { 1, -1, 32767, -32768 };

	int16x4_t va = vld1_s16(a);
	int16x4_t vb = vld1_s16(b);
	int32x4_t vc = vaddl_s16(va, vb);

	int32_t c[4];
	vst1q_s32(c, vc);

	for (int i = 0; i < 4; i++)
		printf("c[%d]: %d\n", i, c[i]);

	return 0;
}
実行結果
c[0]: 2
c[1]: -2
c[2]: 32768
c[3]: -32769

各レーンが32bitに拡張され、オーバーフローしなくなりました

飽和加算(saturating add)

vqadd[q]_<type>(va, vb)

64bit(qが付く場合は128bit)のベクタvaとvbを足します
演算結果がオーバーフローする場合は最大値/最小値で飽和させます
戻り値のサイズは入力のサイズと同じです

サンプル

符号付き16bit整数のベクタvaとvbをvqadd_s16()で足してみます

#include <stdio.h>
#include <stdint.h>
#include <arm_neon.h>

int main()
{
	int16_t a[4] = { 1, -1, 1, -1 };
	int16_t b[4] = { 1, -1, 32767, -32768 };

	int16x4_t va = vld1_s16(a);
	int16x4_t vb = vld1_s16(b);
	int16x4_t vc = vqadd_s16(va, vb);

	int16_t c[4];
	vst1_s16(c, vc);

	for (int i = 0; i < 4; i++)
		printf("c[%d]: %d\n", i, c[i]);

	return 0;
}
実行結果
c[0]: 2
c[1]: -2
c[2]: 32767
c[3]: -32768

3,4番目のレーンは最大値/最小値で飽和しました

その他の加算

個人的にあまり使わなそうだと思ったものですが
簡単に触れておきます

wide add: vaddw_<type>(va, vb)

サイズが違うもの同士を足す場合に使うようです
例えばvaddw_s16(va, vb)はvaがint32x4_tでvbがint16x4_tです

halving add: vaddh[q]<type>(va, vb)

各レーンを足して2で割ります

(va[i] + vb[i]) >> 1
rounding halving add: vaddhn_<type>(va, vb)

各レーンを足したものにさらに1を足して2で割ります

(va[i] + vb[i] + 1) >> 1
add high half: vaddhn_<type>(va, vb)

各レーンの上位ビット同士を足すようです
例えば、各レーンが32bitなら上位16bit同士を足します
どこで使うんだろう…

#include <stdio.h>
#include <stdint.h>
#include <arm_neon.h>

int main()
{
	int a[4] = { 0, 1, 2, 3 };
	int b[4] = { 0, 1, 2, 3 };

	for (int i = 0; i < 4; i++)
	{
		a[i] = a[i] << 16;
		b[i] = b[i] << 16;
	}

	int32x4_t va = vld1q_s32(a);
	int32x4_t vb = vld1q_s32(b);
	int16x4_t vc = vaddhn_s32(va, vb); // { 0, 2, 4, 6 }

	return 0;
}
rounding add high half: vraddhn_<type>(va, vb)

これ、よく分かりませんw
(知ってたら教えて下さい)

次回

次回は減算編の予定です
ARM NEONの使い方 減算編

ARM NEONの使い方 ロード・ストア編

ロード

vld1[q]_<type>(ptr)はptrから64bit(qが付く場合は128bit)のベクタをロードします

サンプル

符号付き16bit整数のベクタをロードしてみます
ロードしたベクタの各レーンをvget_lane_s16()で取得し、表示してみます

#include <stdio.h>
#include <stdint.h>
#include <arm_neon.h>

int main()
{
	int16_t a[4] = { 0, 1, 2, 3 };

	int16x4_t va = vld1_s16(a);

	printf("lane[0]: %d\n", vget_lane_s16(va, 0));
	printf("lane[1]: %d\n", vget_lane_s16(va, 1));
	printf("lane[2]: %d\n", vget_lane_s16(va, 2));
	printf("lane[3]: %d\n", vget_lane_s16(va, 3));

	return 0;
}
実行結果
lane[0]: 0
lane[1]: 1
lane[2]: 2
lane[3]: 3

ストア

vst1[q]_<type>(ptr, val)は64bit(qが付く場合は128bit)のベクタvalをptrにストアします

サンプル

vld1_s16()でロードしたベクタをもう一度ストアして表示してみます

#include <stdio.h>
#include <stdint.h>
#include <arm_neon.h>

int main()
{
	int16_t a[4] = { 0, 1, 2, 3 };

	int16x4_t va = vld1_s16(a);

	int16_t b[4];
	vst1_s16(b, va);

	for (int i = 0; i < 4; i++)
		printf("b[%d]: %d\n", i, b[i]);

	return 0;
}
実行結果
b[0]: 0
b[1]: 1
b[2]: 2
b[3]: 3

逆インターリーブロード

先ほどはvld1を紹介しました
実はこの他にvld2、vld3、vld4というものもあります

どんな処理になるのか、サンプルを見てみましょう

サンプル

vld2_s16()を使って、符号付き16bit整数のベクタをロードしてみます
vld2_s16()の戻り値はint16x4x2_tになります
これはデータ型編でも紹介した通り、int16x4_t を2つ要素に持つ型です
各要素はvalというメンバに格納されています
val[0]とval[1]それぞれのレーンを表示してみます

#include <stdio.h>
#include <stdint.h>
#include <arm_neon.h>

int main()
{
	int16_t a[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };

	int16x4x2_t va = vld2_s16(a);

	printf("val[0]:\n");
	printf("%d\n", vget_lane_s16(va.val[0], 0));
	printf("%d\n", vget_lane_s16(va.val[0], 1));
	printf("%d\n", vget_lane_s16(va.val[0], 2));
	printf("%d\n", vget_lane_s16(va.val[0], 3));

	printf("val[1]:\n");
	printf("%d\n", vget_lane_s16(va.val[1], 0));
	printf("%d\n", vget_lane_s16(va.val[1], 1));
	printf("%d\n", vget_lane_s16(va.val[1], 2));
	printf("%d\n", vget_lane_s16(va.val[1], 3));

	return 0;
}
実行結果
val[0]:
0
2
4
6
val[1]:
1
3
5
7

val[0]にはa[8]の偶数番目の要素が、val[1]にはa[8]の奇数番目の要素がロードされました
このサンプルの偶数と奇数のように、交互に配置されたものを分離することから
vld2(およびvld3、vld4)を逆インターリーブ(deinterleave)とも呼びます
(インターリーブには「交互配置する」という意味合いがあります)

逆インターリーブの実用例としては、以下のものがあります

  • XYの2次元座標の配列から、それぞれのチャンネル(X,Y)を分離する
  • RGBの画素値の配列から、それぞれのチャンネル(R,G,B)を分離する

インターリーブストア

こちらはデータをインターリーブ(交互配置)してストアする処理になります

サンプル

偶数の配列と奇数の配列をそれぞれint16x4x2_tのval[0]とval[1]にロードして
vst2_s16()でインターリーブしてみます

#include <stdio.h>
#include <stdint.h>
#include <arm_neon.h>

int main()
{
	int16_t a[4] = { 0, 2, 4, 6 }; //even
	int16_t b[4] = { 1, 3, 5, 7 }; //odd

	int16x4x2_t vc;
	vc.val[0] = vld1_s16(a);
	vc.val[1] = vld1_s16(b);

	int16_t c[8];
	vst2_s16(c, vc);

	for (int i = 0; i < 8; i++)
		printf("c[%d]: %d\n", i, c[i]);

	return 0;
}
実行結果
c[0]: 0
c[1]: 1
c[2]: 2
c[3]: 3
c[4]: 4
c[5]: 5
c[6]: 6
c[7]: 7

偶数と奇数を交互に配置することができました

参考

その他、インターリーブの解説がある記事・資料を載せておきます

次回

次回は加算編です
ARM NEONの使い方 加算編

CUDA 8がVisual Studio 2015 Update 3に対応した

今年の6月頃からCUDA 8.0 RC(Release Candidate)は出てたのですが
このたび正式なCUDA 8.0がリリースされたようです
CUDA Toolkit | NVIDIA Developer

Parallel Forall Blog - Nvidiaでも紹介されていて
個人的に嬉しかったのがVisual Studio 2015 Update 2以降に対応したこと(RCの時は未対応だった)

Expanded developer platform support including Microsoft Visual Studio 2015 (updates 2 and 3) and GCC 5.4 (Ubuntu 16.04).


これで最新のVisual StudioでCUDA8を試すことができますね!
Pascal GPUが欲しくなるなあ

ARM NEONの使い方 組み込み関数一覧編

組み込み関数一覧

こちらのページにNEONの組み込み関数一覧が載ってます
慣れてきたらここから必要な演算を探すと良いでしょう
infocenter.arm.com

命名規則

NEONの組み込み関数は大抵のものが以下の規則で名前が付けられています

<opname>[q]_<type>

<opname>はvaddやvmul等、演算の内容を表します(必ず頭に'v'が付きます)
[q]はオプションフラグで、qが付く場合は128bit型に対する演算を表します
<type>はオペランドの型を表します

例えば、 vadd_s16 は int16x4_t(64bit型)同士の加算を、
vaddq_s16 は int16x8_t(128bit型)同士の加算を表します

次回

次回からは個別の演算に対して解説していきます
ARM NEONの使い方 ロード・ストア編

ARM NEONの使い方 データ型編

NEONデータ型の概要

NEONのデータ型は以下の規則で名前が付けられています

<type><size>x<number of lanes>_t

例えば、 int16x4_t は符号付き16bit整数を4個保持する型となります
それぞれの要素を「レーン」と呼びます

NEONのデータ型は64bitのものと128bitのものがあります

NEONデータ型一覧

NEONのデータ型一覧を示します

64bit型 128bit型
int8x8_t int8x16_t
int16x4_t int16x8_t
int32x2_t int32x4_t
int64x1_t int64x2_t
uint8x8_t uint8x16_t
uint16x4_t uint16x8_t
uint32x2_t uint32x4_t
uint64x1_t uint64x2_t
float16x4_t float16x8_t
float32x2_t float32x4_t
poly8x8_t poly8x16_t
poly16x4_t poly16x8_t

以上をさらに配列にした型もあり、以下の規則で名前が付けられています

<type><size>x<number of lanes>x<length of array>_t

例えば、 int16x4x2_t は int16x4_t を2つ要素に持つ型です
各要素はvalというメンバに格納されています

struct int16x4x2_t
{
    int16x4_t val[2];
};

これらの配列型は一部のNEON命令で使用されます
使いどころについては今後の記事で解説したいと思います

polyって何?

データ型一覧の中に、見慣れないpolyという型がありました
気になってググったところ、以下の投稿を発見しました

stackoverflow.com

どうやら多項式(polynomial)算術演算というものをするための型らしく
誤り検出符号や暗号化に利用されているようです

次回

個別の組み込み関数について説明する前に、全体像に触れておきたいと思います
ARM NEONの使い方 組み込み関数一覧編

ARM NEONの使い方 予告編

はじめに

ここ最近、NEON(ARMのSIMD命令)を使ったプログラムを初めて書きました
NEONについて調べていて思ったのが、NEONの使い方を初心者向けに
日本語で説明したページがあまり見当たらないということ
そんなわけで、自分なりにNEONの使い方をまとめておこうと思いました

書く予定のもの

とりあえず自分がある処理をNEON化する上で必要だった知識を取り上げます
すべてのNEON命令をカバーしているわけではありませんので悪しからず

次回

まずはNEONのデータ型について解説します
ARM NEONの使い方 データ型編