Image-Processing

Image-Processing === Team 2 瞿旭民 `<kevinbird61>` 林哲亘 `<CheHsuan>` 謝永勁 `<SwimGlass>` 陳柔安 `<carolc0708>` github source： https://github.com/kevinbird61/Image-Processing  --- ## 本影片流程進行 ```graphviz digraph { intro[shape="box", style=rounded]; intro[label="介紹 image-processing"]; intro->env; env[shape="box", style=rounded]; env[label="Intel & ARM NEON 實作"]; env->bmp; bmp[label="Why choose BMP ? + About DSs"]; bmp->program; program[shape="box", style=rounded]; program[label="程式架構與執行"]; program->optimize; optimize[shape="box", style=rounded]; optimize[label="優化方式"]; optimize->result; result[shape="box", style=rounded]; result[label="程式執行結果"]; optimize->check; check[shape="box", style=rounded]; check[label="說明驗證方法"]; optimize->future; future[shape="box", style=rounded]; future[label="future work"]; } ```  --- ## Intel   ```shell=bash Architecture: x86_64 CPU 作業模式： 32-bit, 64-bit Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 每核心執行緒數：2 NUMA 節點： 1 供應商識別號： GenuineIntel CPU 家族： 6 Model name: Intel(R) Core(TM) i7-4700HQ CPU @ 2.40GHz CPU MHz： 3199.968 CPU max MHz: 3400.0000 CPU min MHz: 800.0000 BogoMIPS: 4789.25 L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 6144K NUMA node0 CPU(s): 0-7 ``` ---- ## ARM（raspberry pi 3）   ```shell=bash Architecture: armv7l Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 1 Core(s) per socket: 4 Socket(s): 1 Model name: ARMv7 Processor rev 4 (v7l) CPU max MHz: 1200.0000 CPU min MHz: 600.0000 ``` ---- ### 選擇實作的 function - 高斯模糊 - 鏡像 - HSV  ---- ### Gaussian blur  <span style="font-size: 0.5em;">高斯模糊，又稱為高斯平滑，主要用於降低圖片細節與層次。</span> ![](https://i.imgur.com/3f7YVh4.png =400x250) <span style="font-size: 0.5em;">如上圖，我們以一點作為運算目標，距離該點愈遠的，所佔的影響值愈小。</span> ---- ### Gaussian blur(conti.)  ![](https://i.imgur.com/xdk19CP.png =400x250) <span style="font-size: 0.5em;">權重分佈則採常態分佈（又稱正態分佈、高斯分佈）方式，距離愈近 μ ，值愈大；而距離（ σ:標準差）愈小，則代表愈集中、愈大則代表愈分散</span> ---- ### 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^2^ = u^2^ + v^2^，而從高斯分佈公式中，可以看到當距離大於 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系列處理器中使用。 --- ## Why BMP? - 主要我認為沒有壓縮過的圖片來操作，相對於已經做過壓縮後的（或失真），效果比較明顯 - 先前有類似處理過 BMP 格式的經驗（C++） ---- ### About Data Structure  - 以影像處理為實驗方式，進而檢測效能 - 主要實作中，分為原本的資料結構和分開的結構來實作： ```C=34 // 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" ?  - 執行這兩種結構來看執行效率： <table> <tr> <td></td> <td>naive(ori)</td> <td>naive(tri)</td> </tr> <tr> <td>高斯模糊(ms)</td> <td>320.122994</td> <td>441.310818</td> </tr> </table> - 可以看到，由於以 original data structure 只執行了一次 blur function，比較 split data structure 來說，相對少了兩次的 blur function call ；而兩種實作方式就帶來`0.073597`秒的差距 - 而為何我要實作兩種，主要考慮到之後實作 SSE/AVX instruction set 時所需要的操作，可能會為了符合一個 register 大小（128/256）而做出調整，儘量使用到所有空間，減少回圈執行次數。 --- ## 程式架構與執行 ```graphviz digraph { start->Makefile; start->shell; start[shape="box", style=rounded]; start[label="執行程式（提供兩種方式）"]; shell[label="shell script"]; } ``` - 後來實作 shell script 來執行的原因： - main.c 內有許多需要決定的參數，大部份都是 define macro - 希望可以讓使用者直接再執行前決定要用哪個實作來對要影像處理的圖片上操作 ---- ### 展示 ```shell=bash $ 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 的操作或是DS做的改變 - Unroll - Expand  加上額外的函式庫作為加速手法 - SSE - pthread  變更演算法 - 1D gaussian filter  ---- ### Naive v.s. Unroll  - <span style="font-size: 0.5em;">unroll 的主要目的在於減少內部的兩層 for loop 回圈</span> <table> <tr> <td></td> <td>naive Split</td> <td>naive Original</td> <td>naive Unroll split</td> <td>naive Unroll original</td> </tr> <tr> <td>執行1次(ms)</td> <td>429.951608</td> <td>330.506621</td> <td>188.229402</td> <td>251.948595</td> </tr> </table> - <span style="font-size: 0.5em;">可以看到，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` </span> ---- ### Naive v.s. Expand  - Expand : 從原本"由四周 pixel 加總後決定其中一個點的值"，改成"由一個 pixel 把自己的值依據相對位置填入到周圍的點上" <table> <tr> <td></td> <td>naive Split</td> <td>naive Expand Split</td> </tr> <tr> <td>執行1次(ms)</td> <td>429.951608</td> <td>390.830719</td> </tr> </table> - 時間上有減少，不過由於 load 跟 store 次數還是很高，所以並沒有減少太多 - 不過由於改成從 source 擴展出去，對後來加速的方法上也多了一種原始版本作更改的選擇 ---- ### 1D gaussian filter  - 2D gaussian filter的作法，每個pixel必須要有n * n次乘法運算，複雜度O(n^2^) - Gaussian filter是一個 separable matrix，因此原本2D的 filter 可以轉換成先對 X 方向做一次1D的gaussian filter，然後再對 Y 方向做一次1D的gaussian filter - 1D gaussian filter每個pixel須經過2n次乘法運算，複雜度O(n) <table> <tr> <td></td> <td>2D filter Unroll</td> <td>1D filter Unroll</td> </tr> <tr> <td>執行1次(ms)</td> <td>174.879173</td> <td>139.384629</td> </tr> </table> ---- ### SSE  ![](https://i.imgur.com/8c4LD2A.png) - 選擇以 bytes 為一單位來操作 ---- ### SSE (conti.)  - 使用較大的 register 來一次對多個 pixel （資料）做操作與處理 <table> <tr> <td></td> <td>naive Split</td> <td>naive Original</td> <td>SSE Split</td> <td>SSE Original</td> </tr> <tr> <td>執行1次(ms)</td> <td>429.951608</td> <td>330.506621</td> <td>294.354542</td> <td>275.450552</td> </tr> </table> - 其中 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 來同時執行各區塊的操作，加速執行時間 <table> <tr> <td></td> <td>unroll Split</td> <td>Pthread Split</td> </tr> <tr> <td>執行1次(ms)</td> <td>164.484354</td> <td>103.175455</td> </tr> </table> ----  ### POSIX Thread (conti.) - 需要注意到的事情： - 彼此執行序的邊界處理問題 - 記憶體 malloc 跟 free 的時機(由於 pthread 在執行時，每個 thread 的輸入值是給予一個自訂的 structure ；而針對這個 structure 的 free 的時機，必須要等到 pthread_join() 之後，確保此執行序已經結束 ) - 不能自己去預設"電腦"的運作方式 ----  ### POSIX Thread + SSE <table> <tr> <td></td> <td>SSE Original</td> <td>Pthread SSE Original</td> </tr> <tr> <td>執行1次(ms)</td> <td>232.851845</td> <td>69.630850</td> </tr> </table> - 這邊的 pthread 是以 4 支執行緒下去執行後的結果 - 接近原本 SSE Original 版本中的 1/3 的執行時間 (0.299倍) ----  ### NEON 執行結果在 raspberry pi 3 上面的執行結果如下 <table> <tr> <td></td> <td>Naive </td> <td>NEON</td> </tr> <tr> <td>執行1次(ms)</td> <td>823.816812</td> <td>181.652232</td> </tr> </table> --- ## 程式執行結果 - 利用 gnuplot 做繪製 - 並依據 "改變操作方式或DSs" 、 "額外API" 分成兩張圖片來表示，分別存取成"runtime_naive.png" 以及 "runtime_new.png" ---- ### Runtime_naive.png ![](https://i.imgur.com/INCrYl4.png) ---- ### Runtime_new.png ![](https://i.imgur.com/a3jPTRa.png) ---- ### 產生圖檔結果 ![](https://i.imgur.com/ZxDprkO.jpg =400x300) - 隨著執行 gaussian blur 次數增加，圖像會愈來愈平滑（模糊） --- ## 鏡像Mirror - 將圖片上下顛倒或左右反轉 -- openmp -- SSE 經過上下左右反轉 ![](https://i.imgur.com/1fSuwfR.jpg =400x300) ---- ### SSE Mirror <table> <tr> <td>翻轉</td> <td>naive(ori)</td> <td>naive(tri)</td> <td>openmp(tri)</td> <td>sse(tri)</td> </tr> <tr> <td>水平翻轉(ms)</td> <td>8.165160</td> <td>16.725438</td> <td>4.859310</td> <td>4.280531</td> </tr> <tr> <td>垂直翻轉(ms)</td> <td>6.096713</td> <td>16.969292</td> <td>6.688112</td> <td>1.869409</td> </tr> </table> ---- ### ARM Mirror <table> <tr> <td>翻轉</td> <td>naive_arm(ori)</td> <td>naive_arm(tri)</td> <td>neon(tri)</td> </tr> <tr> <td>水平翻轉(ms)</td> <td>22.934580</td> <td>37.172171</td> <td>10.752292</td> </tr> <tr> <td>垂直翻轉(ms)</td> <td>19.200639</td> <td>8.979229</td> <td>7.470433</td> </tr> </table> --- ## 驗證方法 - diff 檢查兩個產生的圖檔 binary 是否相同 ```shell=bash kevin :-$ diff output_4_0_0.bmp output_8_0_0.bmp kevin :-$ ... kevin :-$ diff output_4_0_0.bmp output_128_0_0.bmp 二元碼檔 output_4_0_0.bmp 與 output_128_0_0.bmp 不同 ... ``` * 若沒有任何顯示，則代表兩個 binary 圖檔相同 * 而通常造成不同的原因： * 邊界處理方式（重複計算） * 來源是否都是一樣（如果沒有額外使用一個空間來儲存，那麼） ---- ### 驗證方法 - Expand (conti.) <span style="font-size: 0.5em;">（以 Expand 為例）使用單一點的矩陣來執行 gaussian blur 後，可以直接檢視產生的矩陣，在該點位置周圍是否為正確的值</span> <table> <tr> <td> 0,0,0,0,0 </td> <td> </td> <td> 0,3,6,3,0 </td> </tr> <tr> <td> 0,0,0,0,0 </td> <td> </td> <td> 3,14,24,14,3 </td> </tr> <tr> <td> 0,0,255,0,0 </td> <td> => </td> <td> 6,24,38,24,6 </td> </tr> <tr> <td> 0,0,0,0,0 </td> <td> </td> <td> 3,14,24,14,3 </td> </tr> <tr> <td> 0,0,0,0,0 </td> <td> </td> <td> 0,3,6,3,0 </td> </tr> </table> * 方便做 debug 的時候檢視異同、找出問題所在 ---- ### 驗證方法 - Valgrind (conti.) ![](http://www.cnitblog.com/images/cnitblog_com/qiuyangzh/snap.jpg =300x150) - 主要對記憶體部份的檢查機制，來確定程式執行時是不是有 memory leak 或是錯誤使用的部份 - 當程式編譯並執行時，沒有產生錯誤訊息、實際上卻有錯的情況發生時，會造成執行時間降低的假象（執行錯誤便結束的狀況） - 所以善用 valgrind 來檢查程式，是可以確保產生的結果是正確無誤的 --- ## Future Work - 各 Gaussian blur 程式產生的圖檔皆相同 - 處理邊界問題（thread 跟 thread 之間、圖檔的上下左右邊界） - 是否有 source 在使用前被更動的問題（沒有使用暫存空間 output 作一次儲存） - 選擇較高效率的原始版本作為基礎，再利用 SSE 、 pthread 等等方法來做優化 - 1D 、SSE Expand Original... - ARM SSE Original 版本實作 --- ## Reference - [透過 SIMD 加速高斯模糊運算 - 原始共筆討論](https://hackmd.io/s/BJOTYoHge) - [Hackmd 簡報製作](https://hackmd.io/EwNhE4A4IZgWigRgKxwCwAYRrgQ0gGbgIAmApsMjMiCZGYkA?both) --- ## End

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.