【C】Pure C 處理影像實作

簡介

本文是學習筆記，學習開源程式碼 OpenCV 中的實作，並且學習其中所使用的概念

Mat Implementation

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

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;
        }
    }
}

mat_at為mat索引的巨集，能夠取得指定位置開頭的指標，經過測試後發現每次進行索引與移動指標會造成速度過慢的問題，由於每次都是從起始位置移動並做邊界檢查

RGB2GRAY Move Pointer

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;
    }
}

相比於前面naive實作的版本，這次執行速度就快很多了，由於不需要一直移動指標與進行邊界檢查

RGB2GRAY Multi-Thread

typedef struct {
    struct Mat *src;
    struct Mat *dst;
    int         start_row;
    int         end_row;
} ThreadData;

由於RGB影像轉成灰階影像，每一個像素值都是獨立計算出來的，因此可以透過多線程方式加速迴圈運算，本次實作是以沿著 row 方向上進行切塊分配給不同線程進行處理

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

void* fast_malloc(size_t size)

將記憶體進行對齊，記憶體是否對齊，會影響存取記憶體資料的時間

#define ALIGN 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;
}

1. 記憶體分配：void* mem = malloc(size + sizeof(void*) + (ALIGN - 1))

• 目的：分配足夠的記憶體空間，滿足使用者需求並保證對齊。
• 組成：
  • size：使用者請求的記憶體大小。
  • sizeof(void*)：額外空間，用來儲存 malloc 返回的原始位址（供後續釋放記憶體使用）。
  • ALIGN - 1：最大可能的對齊偏移量，確保有足夠空間調整到下一個 16 位元組邊界。
• 總大小：分配的記憶體包含請求的大小加上對齊和元資料的額外開銷。

2. 對齊計算：void* ptr = (void**) ((uintptr_t) (mem + (ALIGN - 1) + sizeof(void*)) & ~(ALIGN - 1))

• 目的：計算出一個對齊到 16 位元組邊界的位址 ptr。
• 步驟：
  1. mem + sizeof(void*)：跳過儲存原始位址的空間。
  2. + (ALIGN - 1)：將位址向前移動最多可能的偏移量，確保能到達下一個對齊點。
  3. (uintptr_t)：將指標轉為整數型態，以便進行位元操作。
  4. & ~(ALIGN - 1)：使用位元遮罩將位址對齊。
     • 範例：若 ALIGN = 16（二進位 0b10000），則 ALIGN - 1 = 15（0b1111），~(ALIGN - 1) = 0b...11110000。
     • & 操作會清除低 4 位（因為 16 = 2^4），使位址成為 16 的倍數。
• 結果：ptr 現在是對齊到 16 位元組邊界的位址。

3. 儲存原始位址：((void**) ptr)[-1] = mem

• 目的：將 malloc 返回的原始位址 mem 儲存在對齊位址 ptr 之前，方便後續釋放記憶體。
• 細節：
  • (void**) ptr：將 ptr 視為指向指標的指標，以便進行指標運算。
  • [-1]：存取 ptr 前一個位置（這就是為什麼之前預留了 sizeof(void*) 的空間）。
  • 將 mem 儲存在此位置，記錄原始分配的位址。

4. 返回：return ptr

• 函數返回對齊後的位址 ptr，供使用者使用。原始位址 mem 被隱藏在它之前。

void fast_free(void* ptr)

void fast_free(void* ptr)
{
    free(((void**) ptr)[-1]);
}

Reference

• Aligned memory allocation

Index

經過實際測試，下面巨集將會造成速度慢將近50%，由於每次索引元素時都需要從初始位置開始移動指標，指標最好不要移來移去

#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

• 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對於圖像的資料型態進行編碼後轉換成十進位的結果