Image-Processing

選擇實作的 function

• 高斯模糊
• 鏡像
• HSV

Gaussian blur

高斯模糊，又稱為高斯平滑，主要用於降低圖片細節與層次。

如上圖，我們以一點作為運算目標，距離該點愈遠的，所佔的影響值愈小。

Gaussian blur(conti.)

權重分佈則採常態分佈（又稱正態分佈、高斯分佈）方式，距離愈近 μ ，值愈大；而距離（ σ:標準差 ）愈小，則代表愈集中、愈大則代表愈分散

Gaussian blur - Formula

• 高斯分佈公式
  \[ f(x) = {1 \over σ \sqrt {2\pi} } e^{-(x-μ)^2 \over 2σ^2 } \]

• 而高斯模糊公式（二維空間）：
  \[ G(u,v) = {1 \over {2\piσ^2} } e^{-(u^2+v^2) \over 2σ^2 } \]

Gaussian blur - Formula(conti.)

• 若 r 為模糊半徑，則可得 r² = u² + v²，而從高斯分佈公式中，可以看到當距離大於 3*σ 後，基本上已經無影響力
• 以 u = 2 , v = 2 為例，我們可以以一個 5 x 5 的矩陣來作我們的 Gaussian 權重值
• 藉由加總所有矩陣值並調整到為 1 後，便以他為我們的權重值，作為 Gaussian Kernel 來使用

ARM NEON 簡介

NEON是一種基於SIMD的ARM技術，比較ARMv6或之前的架構，NEON结合了64-bit和128-bit的兩種SIMD指令集，提供128-bit的向量運算(vector operations)。NEON從ARMv7開始被使用，目前可以在ARM Cortex-A和Cortex-R系列處理器中使用。

About Data Structure

• 以影像處理為實驗方式，進而檢測效能
• 主要實作中，分為原本的資料結構和分開的結構來實作：

// Original structure
typedef struct tagRGBTRIPLE { // (3bytes)
    BYTE rgbBlue;             // (1bytes) blue channel
    BYTE rgbGreen;            // (1bytes) green channel
    BYTE rgbRed;              // (1bytes) red channel
} RGBTRIPLE;
// split structure
color_r = (unsigned char*)malloc(bmpInfo.biWidth*bmpInfo.biHeight*sizeof(unsigned char));
color_g = (unsigned char*)malloc(bmpInfo.biWidth*bmpInfo.biHeight*sizeof(unsigned char));
color_b = (unsigned char*)malloc(bmpInfo.biWidth*bmpInfo.biHeight*sizeof(unsigned char));

Why Using "split" & "Original" ?

• 執行這兩種結構來看執行效率：

• 可以看到，由於以 original data structure 只執行了一次 blur function，比較 split data structure 來說，相對少了兩次的 blur function call ；而兩種實作方式就帶來0.073597秒的差距

• 而為何我要實作兩種，主要考慮到之後實作 SSE/AVX instruction set 時所需要的操作，可能會為了符合一個 register 大小（128/256）而做出調整，儘量使用到所有空間，減少回圈執行次數。

展示

$ bash image_process.sh -g 1 
Your getopt version is OK!
compile with target gaussian: 1
The program will be compile with:

Git commit hooks are installed successfully.
未改變  /home/kevin/Dropbox/workspace/Image-Processing/bmp.h
未改變  /home/kevin/Dropbox/workspace/Image-Processing/gaussian.c
未改變  /home/kevin/Dropbox/workspace/Image-Processing/gaussian.h
未改變  /home/kevin/Dropbox/workspace/Image-Processing/hsv.c
未改變  /home/kevin/Dropbox/workspace/Image-Processing/hsv.h
未改變  /home/kevin/Dropbox/workspace/Image-Processing/main.c
未改變  /home/kevin/Dropbox/workspace/Image-Processing/mirror_arm.c
未改變  /home/kevin/Dropbox/workspace/Image-Processing/mirror.c
未改變  /home/kevin/Dropbox/workspace/Image-Processing/mirror.h
[Prepared to execute...]Enter the execution times your want to apply on image:[Press Enter to default=1] 5
[Prepared to execute...]Enter the thread numbers your want to apply on image:[Press Enter to default=2] 4
[Prepared to execute...]If you want to change input filename(Press Enter to get default)?[y/n] 
[Prepared to execute...]If you want to change output filename(Press Enter to get default)?[y/n] 
Picture size of picture is width: 1600 , height 1200
Read file successfully
Gaussian blur[5x5][sse pthread original structure], execution time : 484.307227 ms , with 5 times Gaussian blur

Save file successfully
...

功能

• 利用bash image_process.sh [...]做執行手段
• 後面可以加上指定的項目，例如：
  • "-g N"：利用 N (給予一個定量的範圍)來選擇我要執行哪個 gaussian function 來處理這張圖
  • "-a"：開啟並使用每一個 gaussian function
  • "-v"：使用 valgrind 來檢查記憶體使用
  • "-t"：限定程式只針對 TEST 區塊的程式執行
  • "-m"：開啟並使用每一個 mirror function
  • "-s"：加入較為嚴格的編譯選項"-Wall -pedantic"
  • "- -perf N"：表示使用 perf 並執行 N 次
  • "- -clean"：清除所有產生的檔案
  • "- -help"：察看指令

好處？

• 由於 main.c 利用 define macro 的方式來區分執行哪支程式的關係
• 所以我們可以藉由 shell script 的方式來讓使用者先決定要做哪些設定，再拿這些設定加到編譯參數做編譯，產生相對應的檔案
• 這樣就不必每次新增就要額外再新增 target
• 而且"執行次數"、"輸入/輸出檔"、"執行序數量"也可以作決定，讓所有變數能再 main.c 執行前全數決定

Naive v.s. Unroll

• unroll 的主要目的在於減少內部的兩層 for loop 回圈

• 可以看到，unroll 後的版本都比原先的實作版本快上許多（尤其以 split 的實作更為明顯）；由於原先實作中，split 版本由於必須執行三次才能完成，相對 original 版本只需要一次執行來說，相對耗費時間；而再 unroll 之後，每次執行時間減少，原先執行三次則同時代表這三次同時受到優化，可獲得3倍的執行時間減少；計算 3 次優化所減少的時間：231.528868 ms，除以 3 後大約為77.18 ms；而看到 original 前後時間差異：78.322224 ms ，差不多相同，代表著由於 unroll 對於實驗體（ 1600 x 1200 的圖片檔）來說，對一次執行實作 unroll 的效能增加差不多為 77~78 ms

Naive v.s. Expand

• Expand : 從原本"由四周 pixel 加總後決定其中一個點的值"，改成"由一個 pixel 把自己的值依據相對位置填入到周圍的點上"

• 時間上有減少，不過由於 load 跟 store 次數還是很高，所以並沒有減少太多
• 不過由於改成從 source 擴展出去，對後來加速的方法上也多了一種原始版本作更改的選擇

1D gaussian filter

• 2D gaussian filter的作法，每個pixel必須要有n * n次乘法運算，複雜度O(n²)
• Gaussian filter是一個 separable matrix，因此原本2D的 filter 可以轉換成先對 X 方向做一次1D的gaussian filter，然後再對 Y 方向做一次1D的gaussian filter
• 1D gaussian filter每個pixel須經過2n次乘法運算，複雜度O(n)

SSE

• 選擇以 bytes 為一單位來操作

SSE (conti.)

• 使用較大的 register 來一次對多個 pixel （資料）做操作與處理

• 其中 SSE split 就是用 expand 的版本來實作的； original 則是照原本來改的

SSE - 問題

• 問題所在：考慮到 SSE 對於整體動作的優勢，主要是在於對整排為單位上做移動時有較明顯的降低執行時間（ prefetcher 的範例可見 ）
• 而現階段的操作則是以塊狀為主的操作方式，對於以排為單位來說，是需要考慮使用方式的
• 原先的 split SSE 操作過於直覺且草率，每個 register 中 16 bytes 中，只用了 5 bytes，整體時間平均再 650 ms 上下
• 而一樣的方法，對 SSE original 時則由於 original 中每個 object 都是3個 bytes，所以一樣操作5個， 5x3=15 ，使用率從 5/16 成長到 15/16；相對增加使用率，進而降低執行時間

SSE - 問題 ( conti. )

• 而再 expand 的版本中，我不必考慮到處理周圍 pixel
• 變成主要以擴散的方式進行，由各點乘上一樣的 gaussian kernel 並存到周圍（ 由於 gaussian kernel 是相對位置來計算，所以跟原本一樣，只是現在方向是反過來而已 ），確保source每個 pixel 只作一次讀取
• 這麼一來就不需要以塊狀的方式來進行運算，可以利用整排（ 16 x 1 ）來操作，並存到周圍大小為（ 16+2*2 ）*( 2*2+1 )的區域，讓 SSE 再次發揮作用

POSIX Thread

• 考慮到來源皆不會改變的情況下（並且皆為 read），依據給予的 thread 數量，使用 thread 來同時執行各區塊的操作，加速執行時間

POSIX Thread (conti.)

• 需要注意到的事情：

  • 彼此執行序的邊界處理問題
  • 記憶體 malloc 跟 free 的時機(由於 pthread 在執行時，每個 thread 的輸入值是給予一個自訂的 structure ；而針對這個 structure 的 free 的時機，必須要等到 pthread_join() 之後，確保此執行序已經結束 )

• 不能自己去預設"電腦"的運作方式

POSIX Thread + SSE

• 這邊的 pthread 是以 4 支執行緒下去執行後的結果
• 接近原本 SSE Original 版本中的 1/3 的執行時間 (0.299倍)

NEON 執行結果

在 raspberry pi 3 上面的執行結果如下

Runtime_naive.png

Runtime_new.png

產生圖檔結果

• 隨著執行 gaussian blur 次數增加，圖像會愈來愈平滑（模糊）

SSE Mirror

ARM Mirror

驗證方法 - Expand (conti.)

（以 Expand 為例 ）使用單一點的矩陣來執行 gaussian blur 後，可以直接檢視產生的矩陣，在該點位置周圍是否為正確的值

• 方便做 debug 的時候檢視異同、找出問題所在

驗證方法 - Valgrind (conti.)

• 主要對記憶體部份的檢查機制，來確定程式執行時是不是有 memory leak 或是錯誤使用的部份
• 當程式編譯並執行時，沒有產生錯誤訊息、實際上卻有錯的情況發生時，會造成執行時間降低的假象（執行錯誤便結束的狀況）
• 所以善用 valgrind 來檢查程式，是可以確保產生的結果是正確無誤的