Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Go/Cgoで映像・音声のリアルタイム処理をやるまでの道のり - Go Conference ...

Go/Cgoで映像・音声のリアルタイム処理をやるまでの道のり - Go Conference 2023

Go Conference 2023 Room A : A7-L https://gocon.jp/2023/sessions/A7-L/

Yusuke Hata

June 02, 2023
Tweet

Other Decks in Programming

Transcript

  1. 自己紹介 Yusuke Hata (漢 祐介) / @octu0 / @octu0 インフラ・ストリーミング

    MGR @ Mirrativ フロントエンド → バックエンド → ゲーム → インフラ(今ここ) インフラ基盤・ライブ配信基盤の設計開発 映像/音声配信サーバの開発運用...etc 過去に 猫と暮らしてます( ) Go Conference 2023 3
  2. 画像についておさらい 僕らが普段使う画像の形式は RGBA R(red)/G(green)/B(blue)/A(alpha) Alphaを除いて 3つの色の種類から構成されてる CSSなんかでよくみる #C0FFEE という書式 R

    = C0 = 192 G = FF = 255 B = EE = 238 色にすると赤が少なく、緑と青っぽいのがわかる 実際は のような色 1px には3つ(+1)の色を組み合わせられてる Go Conference 2023 9
  3. 二次元画像とStride これを image パッケージの RGBA では 1次元配列で表現してる type RGBA struct

    { Pix []uint8 Stride int Rect Rectangle } 1次元配列から横を決めるのは Stride 400x300の画像だと 400x300x4 = 480000 個の要素 make([]byte, 480000) Go Conference 2023 11
  4. 実際の映像処理では YCbCr 実際の映像処理に RGBA を直接使 うことはほぼなく、 YCbCr という形式使われる (YUV420/I420など) YCbCr

    は 輝度(Y)と色差信号 (CbCr)で表現 type YCbCr struct { Y, Cb, Cr []uint8 YStride int CStride int SubsampleRatio YCbCrSubsampleRatio Rect Rectangle } Go Conference 2023 12
  5. func YCbCrToRGBA(src *image.YCbCr) *image.RGBA { b := src.Bounds() dst :=

    image.NewRGBA(b) for y := b.Min.Y; y < b.Max.Y; y += 1 { for x := b.Min.X; x < b.Max.X; x += 1 { c := color.RGBAModel.Convert(src.At(x, y)) dst.Set(x, y, c) } } } func RGBAToYCbCr(src *image.RGBA) *image.YCbCr { b := src.Bounds() dst := image.NewYCbCr(b, image.YCbCrSubsampleRatio420) for y := b.Min.Y; y < b.Max.Y; y += 1 { for x := b.Min.X; x < b.Max.X; x += 1 { c := src.RGBAAt(x, y) cy, cu, cv := color.RGBToYCbCr(c.R, c.G, c.B) dst.Y[dst.YOffset(x, y)] = cy dst.Cb[dst.COffset(x, y)] = cu dst.Cr[dst.COffset(x, y)] = cv } } } 14
  6. Template Matching するために 1. 注目画像に対して、テンプレートとなる画像を比較して類似度合いを使う SAD / SSD / NCC

    などを使って類似度の計算 2. 輝度の影響を受けにくくするためグレースケール化 3. Edge処理 Go Conference 2023 16
  7. Grayscale (不要な色は捨てる) func Grayscale(src *image.RGBA) *image.RGBA { b := src.Bounds()

    w, h := b.Dx(), b.Dy() dst := image.NewRGBA(b) for y := 0; y < h; y += 1 { for x := 0; x < w; x += 1 { c := src.RGBAAt(x, y) gray := byte(( (76 * int(c.R)) + (152 * int(c.G)) + (28 * int(c.B)) ) >> 8) // RGB を同じ色にする dst.SetRGBA(x, y, color.RGBA{ R: gray, G: gray, B: gray, A: 0xff, }) } } return dst } Go Conference 2023 18
  8. オブジェクトの検出(類似度) 画像の類似度は ここでは SAD (Sum of Absolute Difference) で計算するようにした 疑似コードにするとこんな感じ(

    Σ は for | は abs() に置き換えるイメージ) func SAD(dx, dy int) float64 { sum := 0.0 for x := 0; x < w; x += 1 { for y := 0; y < h; y += 1 { // 1px ずつ比較していって差分を蓄積 sum += Abs( Image(dx + x, dy + y) - Template(x, y) ) } } return sum } Go Conference 2023 19
  9. オブジェクトの検出(類似度) func SAD(s, t *image.RGBA, dx, dy int) float64 {

    w, h := t.Rect.Dx(), t.Rect.Dy() sum := 0.0 for x := 0; x < w; x += 1 { for y := 0; y < h; y += 1 { // grayscale 済みなので R を使う a := float64(s.RGBAAt(dx + x, dy + y).R) b := float64(t.RGBAAt(x, y).R) sum += math.Abs(a - b) } } return sum } func Detect(src *image.RGBA, tpl *image.RGBA) { var pt []image.Point for x := 0; x < w; x += 1 { for y := 0; y < h; y += 1 { if SAD(src, tpl, x, y) < 10 { pt = append(pt, image.Pt(x, y)) } } } } Go Conference 2023 20
  10. Edge処理 + 二値化 グレースケールによって色が減らせた が、まだまだ情報が多い、もっと減らしてもいいはず 濃いところだけで良い 境界をもっとハッキリさせたい Threshold(閾値)を使ってさらに色を減らして 0 と

    1 にしよう 0 と 1 の二値化にすると画像比較にビット演算で処理しやすくなる SADを使っていたのは uint64 に詰めて ハミング距離を計算ができる 64要素まとめて処理できるようになる Go Conference 2023 21
  11. Edge処理(ここでは閾値で判定) const threshold = 50 func IsEdge(graycolor color.RGBA) bool {

    return threshold < graycolor.R } func Binary(gray *image.RGBA) [][]uint64 { b := gray.Bounds() w, h := b.Dx(), b.Dy() dst := make([][]uint64, h) for y := 0; y < h; y += 1 { wc := (width - c) / 64 dst[y] = make([]uint64, w) for x := 0; x < wc; x += 1 { b := uint64(0) for i := 0; i < 64; i += 1 { if IsEdge(gray.RGBAAt(x, y)) { b |= 1 << (64 - i) } } dst[y][x] = b } } return dst } Go Conference 2023 22
  12. ハミング距離 ハミング距離はビット列同士の異なって いる数のこと 一致していないビットは XOR を使 うことで出せる XOR 後に popcount

    を使うこと でビットが立っている数を出すこ とができる import "math/bits" func HammingDistance(a, b []uint64) int { sum := 0 for i := 0; i < cap(a); i += 1 { sum += bits.OnesCount64(a[i] ^ b[i]) } return sum } Go Conference 2023 23
  13. ぼかし処理(ブラー処理) func BlurX(src *image.RGBA, size int) *image.RGBA { for y

    := 0; y < h; y += 1 { for x := 0; x < w; x += 1 { r, g, b := 0, 0, 0 for bx := 0; bx < size; bx += 1 { c := src.RGBAAt(x + bx, y) // X 方向にsize だけ集める r += int(c.R) g += int(c.G) b += int(c.B) } blur.SetRGBA(x, y, color.RGBA{ R: byte(r/size), G: byte(g/size), B: byte(b/size), A: 0xff, }) } } return blur } func BlurY(...) { ... } func BoxBlur(src *image.RGBA) *image.RGBA { return BlurY(BlurX(src, 50), 50) } Go Conference 2023 26
  14. よしよしできた。 いろいろ実装できたので1枚の画像で実行 $ go run main.go elapsed = 580.107ms 1画像の処理に

    580ms もかかった 遅すぎる…。リアルタイムに処理できてない。 30ms以内に処理しないといけないのに。 Go Conference 2023 27
  15. どこが遅かったか 1. 画像の読み込み 13.68 ms 2. 検出のための前処理(グレースケール) 2.11 ms 3.

    検出のための前処理(エッジ処理) 1.28 ms 4. 検出するロジック 38 ms 5. ぼかし処理 520 ms 無駄な処理が多いのはあるが、これではリアルタイムに処理はできない。 このスライドだけでも for が何回出てきたか分からないくらいループしている 不要な処理を可能な限り削る必要がある Go Conference 2023 28
  16. 並列処理と SIMD CPUにはまとめて処理できる機能がある (SIMD) 128bit レジスタであれば32bitずつ4個まとめて処理できる #include <immintrin.h> int main(int

    argc, char **argv) { __m128i a = _mm_set_epi32(1, 2, 3, 4); __m128i b = _mm_set_epi32(10, 20, 30, 40); __m128i sum = _mm_add_epi32(a, b); int r[4]; memcpy(r, &sum, sizeof(int)*4); printf("%d %d %d %d\n", r[3], r[2], r[1], r[0]); // => 11 22 33 44 return 0; } Go Conference 2023 30
  17. 残念ながら標準のGoではSIMDで書けない、が、 cgo 経由であれば実行できる /* #include <string.h> #include <immintrin.h> int add4(int32_t

    *a, int32_t *b, int32_t *out) { __m128i aa = _mm_set_epi32(a[0], a[1], a[2], a[3]); __m128i bb = _mm_set_epi32(b[0], b[1], b[2], b[3]); __m128i sum = _mm_add_epi32(aa, bb); memcpy(out, &sum, sizeof(int) * 4); return 0; } */ import "C" func Add4(a [4]int32, b [4]int32) []int32 { out := make([]int32, 4) C.add4( (*C.int32_t)(unsafe.Pointer(&a[0])), (*C.int32_t)(unsafe.Pointer(&b[0])), (*C.int32_t)(&out[0]), ) return out } Go Conference 2023 31
  18. これまでの for の中身をよく見るとデータ列に対して同じ処理をしている。 先程のグレースケールを例にすると c := src.RGBAAt(x, y) gray :=

    byte(( (76 * int(c.R)) + (152 * int(c.G)) + (28 * int(c.B)) ) >> 8) dst.SetRGBA(x, y, color.RGBA{R: gray, G: gray, B: gray}) は、もう少し崩すと r[i] = 76 * c.R g[i] = 152 * c.G b[i] = 28 * c.B dst.Pix[i] = (r[i] + g[i] + b[i]) >>8 いい感じに取り出して、4つずつ処理させていけばSIMDでいけるのでは...? Go Conference 2023 32
  19. SIMD で書き換えてみた BenchmarkGray BenchmarkGray/Go BenchmarkGray/Go-8 788 1319082 ns/op BenchmarkGray/SIMD BenchmarkGray/SIMD-8

    9007 135928 ns/op PASS Goで書いたグレースケール 1.329 ms SIMDで書いたグレースケール 0.127 ms SIMD で書き換えて 10倍 くらい高速になった が、単純な四則演算もpackしなおして流し直すの は、シンプルなGrayscaleでもとても大変...。 Go Conference 2023 33
  20. libyuvにやりたいことが実装されてる https://chromium.googlesource.com/libyuv/libyuv/ Grayscale であれば ARGBGrayTo で最適化されたもので呼べる /* #cgo CFLAGS: -I/path/to/include

    #cgo LDFLAGS: -L/path/to/lib -lyuv #include "planar_functions.h" */ import "C" func Grayscale(src, dst *image.RGBA) bool { width, height := src.Rect.Dx(), src.Rect.Dy() stride := width * 4 C.ARGBGrayTo( (*C.uchar)(&src.Pix[0]), C.int(stride), (*C.uchar)(&dst.Pix[0]), C.int(stride), C.int(width), C.int(height), ) } 35
  21. libyuvにやりたいことが実装されてる 今までのコードはほとんど置き換えできた 1. 画像の読み込み → I420ToARGB (13.68 ms → 0.14ms)

    2. グレースケール → ARGBGrayTo (2.11 ms → 0.18 ms) 3. エッジ処理 → ARGBSobel (1.28 ms → 0.29ms) 4. 検出ロジック → 自前 38 ms 5. ぼかし処理 → ARGBBlur (520 ms → 8.49ms) この置き換えで 580ms → 47 ms で12倍くらい改善 無駄な処理が多く残っている状態でこれはすごい Go Conference 2023 36
  22. Halide言語 色々探したところ Halide 言語に出会った C++ の DSL 画像処理に特化コード 最適化されたコードを静的ライブラリとして出力できる →

    *.a で出力される → Goに組み込める!! アルゴリズムとスケジューラを分離することができる → アルゴリズム側は変えずにチューニングできる → コードが難しくならず保守しやすくなる 軽く紹介します! Go Conference 2023 39
  23. Halide のコード 公式ページより Blur3x3 処理をするコード Func blur_3x3(Func input) { Func

    blur_x, blur_y; Var x, y, xi, yi; // The algorithm - no storage or order blur_x(x, y) = (input(x-1, y) + input(x, y) + input(x+1, y))/3; blur_y(x, y) = (blur_x(x, y-1) + blur_x(x, y) + blur_x(x, y+1))/3; // The schedule - defines order, locality; implies storage blur_y.tile(x, y, xi, yi, 256, 32) .vectorize(xi, 8).parallel(y); blur_x.compute_at(blur_y, x).vectorize(x, 8); return blur_y; } 非常にシンプルなコードですがHalideの魅力が詰まったコード 40
  24. Goで書いた Grayscale (再掲) グレースケールを題材にHalideに置き換えてみます func Grayscale(src *image.RGBA) *image.RGBA { b

    := src.Bounds() w, h := b.Dx(), b.Dy() dst := image.NewRGBA(b) for y := 0; y < h; y += 1 { for x := 0; x < w; x += 1 { c := src.RGBAAt(x, y) gray := byte(( (76 * int(c.R)) + (152 * int(c.G)) + (28 * int(c.B)) ) >> 8) // RGB を同じ色にする dst.SetRGBA(x, y, color.RGBA{ R: gray, G: gray, B: gray, A: 0xff, }) } } return dst } 41
  25. Halide で書き直した Grayscale for 文の中身を書いていくような感じで書き直します Func Grayscale(Func in) { Var

    x("x"), y("y"), ch("ch"); Func out = Func("grayscale"); Expr r = cast<int16_t>(in(x, y, 0)); Expr g = cast<int16_t>(in(x, y, 1)); Expr b = cast<int16_t>(in(x, y, 2)); Expr gray = ((76 * r) + (152 * g) + (28 * b)) >> 8; Expr value = select( ch == 0, gray, // R ch == 1, gray, // G ch == 2, gray, // B 255 // A ); out(x, y, ch) = cast<uint8_t>(value); return out; } 42
  26. Go(cgo)から呼べるように 静的ライブラリにコンパイル void main() { Target target; target.os = Target::OSX;

    target.arch = Target::X86; target.bits = 64; target.set_features({ Target::AVX, Target::AVX2, Target::SSE41 }); ImageParam src(UInt(8), 3, "src"); Func fn = Grayscale(src.in()); OutputImageParam out = fn.output_buffer(); // rgba out out.dim(0).set_stride(4); out.dim(2).set_stride(1); out.dim(2).set_bounds(0, 4); fn.compile_to_static_library("lib/libgrayscale", {src}, "grayscale", target); } コンパイルして実行すると libgrayscale.a と libgrayscale.h が生成される 43
  27. runtime込みで生成しているので libgrayscale.h に最低限必要なものは全て入ってる cgoで呼び出すエントリポイントを my_grayscale.h に、 my_grayscale.c で実装 #include "libgrayscale.h"

    #include "my_grayscale.h" int my_grayscale( unsigned char *in, int32_t width, int32_t height, unsigned char *out ) { halide_buffer_t *in_buf = create_rgba_buffer(in, width, height); halide_buffer_t *out_buf = create_rgba_buffer(out, width, height); int ret = grayscale(in_buf, out_buf); free(in_buf); free(out_buf); return ret; } ※ create_rgba_buffer() は github.com/octu0/blurry/buffer.h にサンプル実装があります 44
  28. CFLAGS/LDFLAGS で libgrayscale.a を読み込み /* #cgo CFLAGS: -I${SRCDIR}/lib #cgo LDFLAGS:

    -L${SRCDIR}/lib -ldl -lm #cgo LDFLAGS: -lgrayscale #include "my_grayscale.h" */ import "C" func Grayscale(in *image.RGBA) *image.RGBA { b := in.Bounds() w, h := b.Dx(), b.Dy() out := image.NewRGBA(image.Rect(0, 0, w, h)) ret := C.my_grayscale( (*C.uchar)(unsafe.Pointer(&in.Pix[0])), C.int(w), C.int(h), (*C.uchar)(unsafe.Pointer(&out.Pix[0])), ) if ret != C.int(0) { panic("failed to call my_grayscale") } return out } Go Conference 2023 45
  29. Halide版 Grayscale を実行 BenchmarkGrayscale BenchmarkGrayscale/go BenchmarkGrayscale/go-8 560 2109204 ns/op BenchmarkGrayscale/halide

    BenchmarkGrayscale/halide-8 868 1364983 ns/op 同じ条件になるように Go と Halide を書き直した状態 この時点でもGoで書いたものよりも速い ( 1.364ms ) が、これくらいならGoだけでも頑張ればいける Go Conference 2023 46
  30. Halide のスケジューラ 作成済みのロジックには手を加えず次のように schedule を追加 やっていることは、ch 単位に parallel、 x方向にベクトル処理をするようにした Func

    grayscale(Func in) { Func out = Func("grayscale"); ... // schedule を定義 out.compute_root() .parallel(ch) .vectorize(x, 16); return out; } Go Conference 2023 47
  31. BenchmarkGrayscale BenchmarkGrayscale/go BenchmarkGrayscale/go-8 554 2114768 ns/op BenchmarkGrayscale/halide BenchmarkGrayscale/halide-8 2391 491738

    ns/op スケジューラを変えることでチューニングできる たった3行の修正で 0.491ms まで下げることができた SIMD で書き直したものまでは行かないが このコーディング量でこの速度は大きい Go Conference 2023 48
  32. Halideで色々チューニングしやすくなった libyuv でやっていたものは、全て halide に書き直しました 1. 画像の読み込み → YCbCr のまま処理するようにした

    (13.68 ms → 0) 2. グレースケール → halide化(libyuv よりちょっと遅い) (2.11 ms → 0.36 ms) 3. エッジ処理 → グレースケール時にまとめた (1.28 ms → 0) 4. 検出ロジック → halide化 (38 ms → 0.28 ms) 5. ぼかし処理 → halide化(libyuvよりよっと速い) (520 ms → 0.11ms) 必要な処理に応じて、必要なロジックだけを書けるので最適化が捗ります Go Conference 2023 50
  33. もろもろチューニングした結果 $ go run main.go elapsed = 0.75ms 1画像 1ms

    未満 で出来るようになった 30ms 以内に処理できる → リアルタイムに処理できる Go Conference 2023 51
  34. CとGoでのデータ変換 Go で使っているデータを C (cgo) 側に渡したい時がちょくちょくある Go では []int16 として定義している値が

    C側では uchar* C では uchar* で返すが、値は float32 例えば Cでは、こんな感じの定義 int PCM16Decibel(unsigned char* in, int size, unsigned char* out); in と out が []byte で受け取るような実装があった際に 都度変換するの大変 Go Conference 2023 55
  35. 通常であれば encoding/binary パッケージを使って変換して利用する(つらい) func calcDecibel(src []int16) (float32, error) { buf

    := bytes.NewBuffer(make([]byte, 0, len(src) * 2)) // []byte -> int16 for _, s := range src { if err := binary.Write(buf, binary.LittleEndian, s); err != nil { return 0.0, err } } in := buf.Bytes() out := make([]byte, 4) // byte -> float ret := C.PCM16Decibel( (*C.uchar)(&in[0]), C.int(len(src)), (*C.uchar)(&out[0]), ) var res float32 if err := binary.Read(bytes.NewReader(out), binary.LittleEndian, &res); err != nil { return 0.0, err } return res, nil } Go Conference 2023 56
  36. データ型に注意しながら unsafe.Pointer / unsafe.Slice を使うことで直接渡せる func calcDecibel2(src []int16) (float32, error)

    { in := unsafe.Slice((*byte)(unsafe.Pointer(&src[0])), len(src)) // go1.17 out := make([]byte, 4) // byte -> float ret := C.PCM16Decibel( (*C.uchar)(&in[0]), C.int(len(src)), (*C.uchar)(&out[0]), ) if ret != C.int(0) { return 0.0, errors.New("...") } return *(*float32)(unsafe.Pointer(&out[0])), nil } Go Conference 2023 57
  37. データ変換のパフォーマンスも結構ばかにならない BenchmarkFloat BenchmarkFloat/old BenchmarkFloat/old-8 40492 28886 ns/op 5644 B/op 1750

    allocs/op BenchmarkFloat/new BenchmarkFloat/new-8 1000000 1033 ns/op 4 B/op 1 allocs/op よく見かける []byte <-> string と同じような要領で C.GoBytes や C.GoString などはこういった組み合わせで置き換え Go Conference 2023 58
  38. var ( pool = make(chan []byte, 1000) // buffer 1000

    ) func NewMakeSlice(size int) []byte { select { case buf := <-pool: return buf default: return make([]byte, size) } } func PutSlice(buf []byte) { select { case pool <- buf: // ok default: // discard } } Go Conference 2023 60
  39. 再利用可能なものは使い回す func foo() { buf := NewMakeSlice(1920*1080) defer PutSlice(buf) grayscale(buf)

    } BenchmarkFloat BenchmarkFloat/old_make_slice BenchmarkFloat/old_make_slice-8 9337 129397 ns/op 2080774 B/op 1 allocs/op BenchmarkFloat/new_make_slice BenchmarkFloat/new_make_slice-8 26715202 44.29 ns/op 0 B/op 0 allocs/op 例えば image.RGBA{Pix:[]byte} はこのスライスを使い回すようにする Go Conference 2023 61
  40. ライブラリの宣伝 Halideで作った画像処理ライブラリ ( よく使う変換系を実装 ) https://github.com/octu0/blurry Leaky buffer ライブラリ (

    []byte 以外の色々なパターンをまとめた ) https://github.com/octu0/bp cgo <-> go の変換とか cgo.Handle 使ったりとか https://github.com/octu0/cgobytepool go generate を使ったHalide連携 https://github.com/octu0/example-halide-go Go Conference 2023 63