NEON優化——OpenCV Resize雙線性插值

算法要點

一、基本原理

具體原理可以自行搜尋，這裡隻大緻描述一下，目标圖像上某一個點按比例映射到原始圖像上某一點，不過通常計算得到的原始點坐标不是整數，最近鄰的做法是向下取整，而雙線性內插補點的做法是取與該坐标最接近的上下左右四個點來線性權重，在放大的時候不會像最近鄰那樣鋸齒嚴重，但是計算量會大不少。這裡要注意的是權重分為兩個次元，橫向和縱向。此外，邊界的處理也要注意。

二、優化思路

這裡核心的優化思路有兩點：

1. 避免重複計算
2. 浮點轉定點

避免重複計算

首先要分析哪裡存在可能的重複計算。resize是原始圖像和目标圖像之間的映射，這個映射不一定是一對一的。比如對于目标圖像的高大于原始圖像的高的情況，目标圖像的多個行可能會映射到原始圖像的同一行，這樣我們就可以利用之前的計算結果，而不用重複計算。

對于目标圖像上的某個點，映射到原始圖像的坐标為O，相鄰的四個點為ABCD，則目标圖像的像素值為val = A(1-fx)(1-fy) + Bfx(1-fy) + C(1-fx)fy + Dfxfy

這個公式可以分解為兩個過程：HResize和VResize

HResize

val0 = A(1-fx) + Bfx 
val1 = C(1-fx) + Dfx
           

VResize

val = val0*(1-fy) + val1*fy
           

之是以分解為兩步，是因為上面提到的當目标圖像的多行映射到原始圖像的同一行時，HResize計算的結果是可以複用的，直接拷貝即可。而VResize是無法複用的，因為即便都映射到同一行，但是fy是不會相同的。

浮點轉定點

浮點轉定點需要乘一個轉換系數。這裡fx和fy都是浮點，OpenCV預設的做法是将fx和fy都乘以固定系數1<<11轉成定點，最後結果再右移22。為什麼取11，因為這是保證不溢出的最高的精度。分析上面的val0，假設A和B都取最大255，則val0最大為

2^19

。假設val0和val1都取最大值

2^19

，則val最大為

2^30

。如果這個固定系數取12，則val的最大值為2^32，即便是unsigned也裝不下了。

雖然取11能保證精度最大，但是由于val0最大是

2^19

，int16是裝不下了，隻能進行int32計算，neon一次隻能算4個數。是以如果想提升neon向量化計算的并行度，可以給系數降低一點，參考OpenCV的三方庫carotene，系數取的是7，同樣這是為了保證能進行int16計算的最高精度，因為這樣val0的最大值為2^15。此外為了保證VResize也能進行int16計算，val0和val1要轉回到int8，這一點和OpenCV不一樣。轉換系數的降低可以提升向量化計算的并行度，進而提升性能，不過會對像素值造成一定的精度損失，經過測試，像素值的誤差不會超過3，而轉換系數為11時這個誤差不會超過1。

整個過程中計算量最重的部分是HResize，我們分析HResize的向量化過程，由于是int16的計算，是以一次最多算8個點，以8UC3為例，假設映射到原始圖像的8個點分别為ABCDEFGH，

A = A0 A1 A2 A3 A4 A5 A6 A7
B = B0 B1 B2 B3 B4 B5 B6 B7
C = C0 C1 C2 C3 C4 C5 C6 C7
D = D0 D1 D2 D3 D4 D5 D6 D7
E = E0 E1 E2 E3 E4 E5 E6 E7
F = F0 F1 F2 F3 F4 F5 F6 F7
G = G0 G1 G2 G3 G4 G5 G6 G7
H = H0 H1 H2 H3 H4 H5 H6 H7
           

對于A點，我們需要

[A0 A1 A2]*K0 + [A3 A4 A5]*K0’，K0=1-fx，K0’=fx，

後面的B~H點同理。

是以向量化計算為

[A0 B0 C0 D0 E0 F0 G0 H0]*[K0 K1 K2 K3 K4 K5 K6 K7] + [A3 B3 C3 D3 E3 F3 G3 H3]*[K0' K1' K2' K3' K4' K5' K6' K7']
[A1 B1 C1 D1 E1 F1 G1 H1]*[K0 K1 K2 K3 K4 K5 K6 K6] + [A4 B4 C4 D4 E4 F4 G4 H4]*[K0' K1' K2' K3' K4' K5' K6' K7']
[A2 B2 C2 D2 E2 F2 G2 H2]*[K0 K1 K2 K3 K4 K5 K6 K7] + [A5 B5 C5 D5 E5 F5 G5 H5]*[K0' K1' K2' K3' K4' K5' K6' K7']
           

可見關鍵是要從ABCDEFGH向量中抽取出類似Ai Bi Ci Di Ei Fi Gi Hi(0<=i<6)這樣的向量。

這裡已知兩種做法，一種是轉置，一種是查表。

三、優化結果

輸出336x192，測試以下三種輸入：

phone	224x128	640x360	1280x720
MI6	0.61ms->0.16ms	1.46ms->0.3ms	1.78ms->0.35ms
魅藍5S	1.97ms->0.57ms	4.9ms->1.38ms	5.64ms->1.97ms
IPHONE7	0.31ms->0.06ms	0.7ms->0.12ms	0.8ms->0.17ms

輸出224x128，測試以下三種輸入：

phone	336x192	640x360	1280x720
MI6	0.52ms->0.12ms	0.72ms->0.15ms	0.73ms->0.17ms
魅藍5S	1.67ms->0.45ms	2.33ms->0.64ms	2.59ms->1.25ms
IPHONE7	0.27ms->0.05ms	0.35ms->0.07ms	0.36ms->0.07ms

輸出640x360，測試以下三種輸入：

phone	224x128	336x192	1280x720
MI6	1.51ms->0.36ms	1.84ms->0.45ms	1.91ms->1.21ms
魅藍5S	4.87ms->1.44ms	6.15ms->1.77ms	6.32ms->4.88ms
IPHONE7	0.44ms->0.15ms	0.65ms->0.15ms	0.38ms->0.37ms