以 halide 實作 block matching 演算法 - block matching with Halide language

由於 multi-frame 與 multi-view 的影像處理需求的提升,  image alignment 的需求日益提升, 而相關的演算也很多, 像是基於 pyramid-based, 9-steps, hexagon or diamond search. 而大小的部份也有著 match / apply 不同大小的 non-local means, 然而這些演算的基本還是源自於特定 search window 的 block matching. 本文重點在於以 Halide language 描述 matching algorithm, 至於 scheduling 的優化不在此文重點. (或是擇日分享)

Step 0 - 輸入格式 (input format - single channel as example)
首先假設要處理的是 image 的某個 channel, multi-channel 的影像則僅是套用到多個 frame 或是以 channel 輸入, 同常有一張是 base image 這裡以 in 代表, 另一張為 reference image 以 ref 代表.

Step 1 - 邊界處理, 用來避免 search block 範圍超過邊界 (boundary handling, to avoid error of part of target block is out of frame)

Func input = BoundaryConditions::repeat_edge(in);
Func refer = BoundaryConditions::repeat_edge(ref);

Step 2 - 用以代表 block 內所有 input 與 reference 的 pixel 的座標 (setup the RDom that represent all pixels of corresponding input & refer block)

// the position in motion vector output table

Var bid_x, bid_y;

// variable for motion vector

Var mv_x, mv_y;

RDom rblk(0, BLOCK_SIZE, 0, BLOCK_SIZE)
// position in input frame
Expr blk_x = (bid_x * BLOCK_SIZE) + rblk.x;

Expr blk_y = (bid_y * BLOCK_SIZE) + rblk.y;
// position in reference frame

Expr ref_x = blk_x + mv_x;
Expr ref_y = blk_y + mv_y;

Step 3 - 建立比對標準, 這裡以 SAD 為例 ( matching criteria calculation (Sum of Absolute Difference(SAD) as example))

Expr in_val = i16(input(blk_x, blk_y);

Expr ref_val = i16(refer(ref_x, ref_y));

Func sad;

sad(mv_x, mv_y, bid_x, bid_y) = sum(abs(in_val - ref_val));

Step 4 - 搜尋與輸出, 這裡是透過 RDom + argmin 搭配來做比對搜尋並取得結果 (search and output, here we use RDom + argmin for matching and finding)

// setup search window
RDom search_win(-range/2, range, -range/2, range);

// argmin will find the one in search_window which get minimal sad.

Tuple me = argmin(sad(search_win.x, search_win.y, bid_x, bid_y));

// output the motion estimation result to MV table

Var ch;

out_mv(bid_x, bid_y, ch) = me[ch];

比較不直覺的地方在於兩個 RDom 套用的層次不同, 第一個 RDom 用來計算 matching criteria, 二個 RDom 是用來作為 motion estimation 尋找 mv, 總之這是以 search window 的方式作窮舉的 block matching 定義, 然而可以延伸與改進用在一開始所說的各種 matching 演算法上