# 【C】Pure C 處理影像實作
## 簡介
本文是學習筆記，學習開源程式碼 OpenCV 中的實作，並且學習其中所使用的概念
## Mat Implementation
```cpp!
struct Mat {
/*! includes several bit-fields:
- depth (4~-11)
- number of channels (1~3)
*/
size_t flags;
//! the matrix dimensionality, >= 2
size_t dims;
//! number of rows, colums
int rows;
int cols;
//! pointer to the array of size and step for n-dim array
size_t* size;
size_t* step;
//! pointer to the data
uchar* data;
};
```
Mat為基本影像處理的最基本的資料結構
* `flags`: 影像的資料型態，以位元方式儲存，包含維度跟深度，在OpenCV中此項隱藏更多訊息
* `dims` : 影像的維度
* `rows` : 行的數量
* `cols` : 列的數量
* `size` : 存放影像大小的指標
* `step` : 索引的步長的指標
* `data` : 實際資料存放的位置，由一維陣列來代表多維陣列，並透過`unsigned char*`的指標來讀取資料
## Mat Function
* `struct Mat* alloc_mat(int rows, int cols, int type)`
* 分配影像記憶體空間
* `type` 參照 opencv可以是 `CV_8UC1, CV_8UC3 ...`
* `struct Mat* create_mat_from_buffer(unsigned char* buffer, size_t buffer_size)`
* 從`buffer memory`來分配影像記憶體空間
* `struct Mat* alloc_mat_from_file(char const* filename)`
* 從影像檔案來分配記憶體空間
* `void free_mat(struct Mat** mat)`
* 釋放影像記憶體空間
* 需要釋放指向記憶體空間，同時將指標設置為 `NULL`
* `void mat_info(struct Mat* mat)`
* 將影像資訊輸出到terminal中
* `void mat_write(const char *filename, struct Mat *mat)`
* 將影像寫入到影像檔案
## Color Conversions
* `void cvt_color(struct Mat* src, struct Mat* dst, int code)`
* `cvt_color`為界面，並透過code來去切換不同演算法的實作
### RGB2GRAY Naive
`mat_at` 為 `mat` 索引的巨集，能夠取得指定位置開頭的指標，經過測試後發現每次進行索引與移動指標會造成速度過慢的問題，由於每次都是從起始位置移動並執行邊界檢查
```cpp!
void rgb_to_gray(struct Mat* src, struct Mat* dst)
{
for (int i = 0; i < src->rows; i++)
{
for (int j = 0; j < src->cols; j++)
{
uchar* src_p = mat_at(src, i, j);
uchar r = src_p[0];
uchar g = src_p[1];
uchar b = src_p[2];
uchar v = (uchar) (r * 0.299 + g * 0.587 + b * 0.114);
uchar* dst_p = mat_at(dst, i, j);
*dst_p = v;
}
}
}
```
### RGB2GRAY ver2
相比於前面 naive 實作的版本，這次執行速度就快很多了，由於不需要一直移動指標與進行邊界檢查
```cpp
void rgb_to_gray(struct Mat *dst, struct Mat *src) {
uchar *s = (uchar *)src->data;
uchar *d = (uchar *)dst->data;
size_t s_ch = mat_channel_num(src);
size_t d_ch = mat_channel_num(dst);
int total = src->rows * src->cols;
for (int i = 0; i < total; i++) {
*d = (uchar)(*(s + 0) * 0.299 + *(s + 1) * 0.587 + *(s + 2) * 0.114);
d += d_ch;
s += s_ch;
}
}
```
### RGB2GRAY Multi-Thread
```c
typedef struct {
struct Mat *src;
struct Mat *dst;
int start_row;
int end_row;
} ThreadData;
```
由於RGB影像轉成灰階影像，每一個像素值都是獨立計算出來的，因此可以透過多線程方式加速迴圈運算，本次實作是以沿著 `row` 方向上進行切塊分配給不同線程進行處理
```c
void* rgb_to_gray_thread_impl(void* args){
ThreadData* thread_data = (ThreadData*)args;
uchar *s = (uchar *)thread_data->input->data;
uchar *d = (uchar *)thread_data->output->data;
size_t s_ch = mat_channel_num(thread_data->input);
size_t d_ch = mat_channel_num(thread_data->output);
fprintf(stdout,"Thread processing rows %d to %d\n", thread_data->start_row, thread_data->end_row - 1);
for (int i = thread_data->start_row; i < thread_data->end_row; ++i) {
for (int j = 0; j < thread_data->input->cols; ++j) {
*d = (uchar)(*(s + 0) * 0.299 + *(s + 1) * 0.587 + *(s + 2) * 0.114);
d += d_ch;
s += s_ch;
}
}
return NULL;
}
void rgb_to_gray_thread(struct Mat *dst, struct Mat *src){
const int NUM_THREADS = 4;
pthread_t threads[NUM_THREADS];
ThreadData thread_data[NUM_THREADS];
int rows_per_thread = src->rows / NUM_THREADS;
for (int i = 0; i < NUM_THREADS; ++i) {
thread_data[i].input = src;
thread_data[i].output = dst;
thread_data[i].start_row = i * rows_per_thread;
thread_data[i].end_row = (i == NUM_THREADS - 1) ? src->rows : (i + 1) * rows_per_thread;
pthread_create(&threads[i], NULL, rgb_to_gray_thread_impl, (void*)&thread_data[i]);
}
for (int i = 0; i < NUM_THREADS; ++i) {
pthread_join(threads[i], NULL);
}
}
```
### RGB2Gray 指令集加速
- [ ] 待實作
## Memory malloc and Free Align
將記憶體進行對齊，記憶體是否對齊，會影響存取記憶體資料的時間
```cpp
#define ALIGN 16 // 對齊 16 字節
void* fast_malloc(size_t size)
{
void* mem = malloc(size + sizeof(void*) + (ALIGN - 1));
void* ptr = (void**) ((uintptr_t) (mem + (ALIGN - 1) + sizeof(void*)) & ~(ALIGN - 1));
((void**) ptr)[-1] = mem;
return ptr;
}
```
```cpp
void fast_free(void* ptr)
{
free(((void**) ptr)[-1]);
}
```
### Reference
* [Aligned memory allocation](https://codeyarns.com/tech/2017-02-28-aligned-memory-allocation.html#gsc.tab=0)
## Index
經過實際測試，下面巨集將會造成速度慢將近50%，由於每次索引元素時都需要從初始位置開始移動指標，指標最好不要移來移去
```cpp
#define MAT_AT(mat, row, col) \
(assert((row) >= 0 && (row) < (mat).rows && (col) >= 0 && \
(col) < (mat).cols), \
((mat).data + (mat).step[0] * (row) + (mat).step[1] * (col)))
#define MAT_AT_ELEM_PTR(mat, type, row, col) ((type*) (MAT_AT(mat, row, col)))
#define MAT_AT_ELEM(mat, type, row, col) (*((type*) (MAT_AT(mat, row, col))))
```
## TODO
- [x] Index Operation
- [ ] 根據不同處理器撰寫組合語言加速
- SSE
- NEON
## Macro
`OpenCV` 透過巨集來針對不同資料型態進行編碼
* `#define CV_CN_SHIFT 3`
為通道偏移量，對應到 Flag 上的第四個位置開始
* `#define CV_CN_MAX 512`
最大支援的的通道數量
* `#define CV_DEPTH_MAX (1 << CV_CN_SHIFT)`
將1位移 `CV_CN_SHIFT`，表示乘以 8，代表著 OpenCV 所支持的最大深度為8
* `#define CV_MAT_DEPTH_MASK (CV_DEPTH_MAX - 1)`
用於篩選flag的數值，並確保其數值落在範圍內， `7 (0111)`
* `#define CV_MAT_DEPTH(flags) ((flags) & CV_MAT_DEPTH_MASK)`
將輸入 `flags` 做遮罩選出深度是多少
* `#define CV_MAT_CN_MASK ((CV_CN_MAX - 1) << CV_CN_SHIFT)`
通道數的遮罩，對應到 `flags` 的4位至第11位， `4088 (1111 1111 1000)`
* `#define CV_MAT_CN(flags) ((((flags) & CV_MAT_CN_MASK) >> CV_CN_SHIFT) + 1)`
* 將輸入的 `flags` 作一次mask，並右移回去並加一，表示通道數範圍為1~512
* `#define CV_ELEM_SIZE1(type) ((0x28442211 >> CV_MAT_DEPTH(type) * 4) & 15)`
* `0x28442211 = 0010 1000 0100 0100 0010 0010 0001 0001` 對應到深度為 `7 ~ 0`
* 操作流程
* 根據其**圖像深度**來進行位移操作，上面數字就是 **LUT(Look on Table)**
* `CV_MAT_DEPTH(type)`
取得深度的數字後並位移4的整數倍來取得對應的大小
* `#define CV_ELEM_SIZE(type) (CV_MAT_CN(type) * CV_ELEM_SIZE1(type))`
* 不得不說，這命名跟屎一樣
* 計算一個 `Pixel`所佔多少位元組
* `CV_MAT_CN(type)`: 計算通道數`(int)`
* `CV_ELEM_SIZE1(type)`: 一個通道的元素大小 `(Byte)`
* `#define CV_MAKETYPE(depth,cn) (CV_MAT_DEPTH(depth) + (((cn)-1) << CV_CN_SHIFT))`
* 影像像素資料由**深度 (8bit, 16bit)** 與 **通道數(gray, rgb, rgba...)** 組成
* 用一個整數代表兩個資訊，這兩個資訊以bit方式來區隔表示
* `CV_MAT_DEPTH`
處理 7 種不同深度的資料結構，範圍 `0 ~ 7`，在 flag 中的 `1 ~ 2`位置(base-1)
* `(((cn)-1) << CV_CN_SHIFT))`
位元操作將通道數左移 `3` 位，以避免與前面的深度搞混，`-1` 是為了要將編碼從 `0` 開始
OpenCV對於圖像的資料型態進行編碼後轉換成十進位的結果
Sign in with Wallet
Connect another wallet