OpenCV Mask (Filter) performance comparison

OpenCV 的內建 filter2D 函式, 實作了影像處理上常用的 Mask, 或是稱為 Filter, Convolution, 的操作. 通常這也是影像相關的演算法的骨幹, 也是最耗費時間的環節.
Mask 的運算時間, 和 Mask 的組成有絕對的關係, 以下套用不同的 Mask, 來觀察他運算時間上的差異.

比較 filter2D()以及自行撰寫的 C 函式

Index	Implement	ms
C Function	*output++ = saturate_cast<uchar>(5*current[i]               -current[i-nChannels] - current[i+nChannels] - previous[i] - next[i]);	64.909
filter2D	Mat kernel = (Mat_<char>(3,3) <<  0, -1,  0, -1,  5, -1,   0, -1,  0); filter2D( src, dst1, src.depth(), kernel );	3.030

以 C 的實作來說, 差不多就是以上所列出來的程度. OpenCV 可以做到將近 20 倍的速度, 應該是用了一些硬體加速的方法.

不同 Mask 的時間比較

Index	Implement	ms
1x1	Mat kernel_1x1 = (Mat_<char>(1,1) <<  1);	1.134
3x3	Mat kernel_3x3 = (Mat_<char>(3,3) <<  0, -1, 0, -1, 5, -1, 0, -1, 0);	2.718
5x5	Mat kernel_5x5 = (Mat_<char>(5,5) <<  0,0,-1,0,0,0,0,-1,0,0,-1,-1,9,-1,-1,0,0,-1,0,0,0,0,-1,0,0);	4.313
7x7-1	Mat kernel_7x7 = (Mat_<char>(7,7) <<         0,0,0,-1,0,0,0,         0,0,0,-1,0,0,0,         0,0,0,-1,0,0,0,         -1,-1,-1,13,-1,-1,-1,         0,0,0,-1,0,0,0,         0,0,0,-1,0,0,0,         0,0,0,-1,0,0,0);	6.170
7x7-2	Mat kernel_7x7_2 = (Mat_<char>(7,7) <<         -4,-3,-2,-1,-2,-3,-4,         -3,-3,-2,-1,-2,-3,-3,         -2,-2,-2,-1,-2,-2,-2,         -1,-1,-1,107,-1,-1,-1,         -2,-2,-2,-1,-2,-2,-2,         -3,-3,-2,-1,-2,-3,-3,         -4,-3,-2,-1,-2,-3,-4);	22.44

隨著 Mask 的 size 變大, 所耗費時間也跟著增加, 有趣的是 Mask 的內容也有很大的影響, 可見 OpenCV 會對於 零項作刪去的最佳化. 

[OpenCV] LUT access time comparison

比較 OpenCV 做 Look Up Table 的效率.
OpenCV 提供了幾種作 Look Up Table 的動作的方法. 以下對這幾種方法做效率上的比較, 同時加上以 C 的 Pointer 的存取方式.

Index	Reference Code	ms
C Pointer	for( int i = 0; i < scan_size; i ++ ) {     * pDest = pTable[ * pSrc ];     pDest ++;     pSrc ++; }	4.98
C []	for( i = 0; i < nRows; ++i) {     p = I.ptr<uchar>(i);     for ( j = 0; j < nCols; ++j)     {         p[j] = table[p[j]];     } }	5.12
iterator	MatIterator_<Vec3b> it, end; for( it = I.begin<Vec3b>(), end = I.end<Vec3b>(); it != end; ++it) {     (*it)[0] = table[(*it)[0]];     (*it)[1] = table[(*it)[1]];     (*it)[2] = table[(*it)[2]]; }	170.45
Random Access	Mat_<Vec3b> _I = I; for( int i = 0; i < I.rows; ++i)    for( int j = 0; j < I.cols; ++j )       {           _I(i,j)[0] = table[_I(i,j)[0]];           _I(i,j)[1] = table[_I(i,j)[1]];           _I(i,j)[2] = table[_I(i,j)[2]];    } I = _I;	291.56
LUT	LUT(I, lookUpTable, J);	5.72

Note :

1. C Pointer 的作法只是做為一個參考, 以 C 程式指令來說, 應該已經是最快的, 這裡主要是用來作為對比.
2. C [] 所耗費的時間略多, 主要應該是用到索引定址的關係. 因為它要先做計數器累加.
3. OpenCV 的 LUT() 函式耗費時間較多. 通用型的函式, 一般來說, 都會比特用型的函式, 來得慢一些, 這樣的時間, 是滿不錯的了.
4. iterator 的存取方式的耗時, 非常的不好, 是 30~40 倍的慢. 顯然這種存取方式, 並不適合用來做 LookUpTable 這種對大量記憶體做簡單運算的動作. 它在存取每一個點的 overhead 太大, 需要做 iterator 前進到下一點的動作, 對每一點的存取也需要做多次的計數器及取址.
5. Random Access, 用 Random Access 的方法, 來做 Sequential Access, 就好像拿拖把掃地, 這邊也是作為參考.

1.5 ms 解出數獨的簡易程式解法

 

朋友傳了一個數獨的題目給我, 這應該算是一個相當難的題目. 原題如下 :

6						4		5
		8	2
					6		1
4		7
			1				2
		6				7	8
				5	4
			9

 

很明顯的,超多的空格, 意味著會有一些需要猜測. 所以這一題會很難. 我不想花時間去手動解, 又很好奇, 空格這麼多, 是不是會有多數解 ? 所以, 我們會需要一個程式, 可以跑出所有的解法.

數獨的解法, 曾經是一個流行的題目. 主要的關鍵字, EXACT COVER Problem, DLX, Dancing Link, Algorithm X, 都可以找到許多有用的資料. 和這些解法來比, 這邊提出來的解法, 只能說是簡單,直覺,一個普通人的解法, 有興趣的可以參考.

一個直覺的解法

數獨的解決過程, 可以分成推論和猜測以及判斷三個部分. 以下簡單的說明：

推論：

根據數獨的規則, 我們要對每一格, 所對應到的列, 行, 區塊, 計算它的可以填入數字的集合. 而這個格子的可填入數字, 就是行,列,區塊, 的交集. 譬如說, 第 7 列, 第 4 行, 這一格, 所對應到的 第 7 列, 第 4 行, 第 8 個區塊, 他們的可填入數字, 分別是 第 7 列 { 1, 2, 3, 4, 5, 9}, 第 4 行 { 3, 4, 5, 6, 7, 8 }, 第 8 區塊 {  2, 3, 6, 7, 8 }, 這幾個集合的交集是 { 3 } , 所以 S[7][4] 這一格的答案是 3.

猜測：

6						4		5
		8	2
					6		1
4		7
			1				2
		6	3			7	8
				5	4
			9

 

這一個階段, 已經沒有前述可以推論得知的答案, 考量 S[1][4], 第 1 , 第 1 列的可行解是 { 1, 2, 3, 7, 8, 9 }, 第 4 行的可行解是 { 4, 5, 6, 7, 8 }, 第 2 區塊的可行解是 { 1, 3, 4, 5, 6, 7, 8, 9}, 所以 S[1][4] 這一格的可行解是 { 7, 8 }, 我們暫時沒有線索可以判斷應該是 7 還是 8. 所以這時就需要去猜測. 猜測的方式是把題目分成兩個子題. 既然是猜測, 就有可能是錯誤, 所以會需要判斷.

判斷：

6			7			4	3	5
		8	2				7
			4
			8		6		1
4		7	5				6
			1				2
		6	3			7	8
			6	5	4		9
			9

 

考量 S[3][8] 這一格, 第 3 列的可行解是 { 1, 2, 3, 5, 6, 7, 8, 9}, 第 8 行的 可行解是 { 4, 5}, 第 3 區塊的可行解是 { 1, 2, 6, 8, 9}, S[3][8] 這一格的可行解是沒有. 原因是我們在前面的猜測錯誤, 這一個子題不存在解決方案.

一般的數獨的解決過程, 就是重複推論, 猜測, 判斷的過程. 也是最直覺的解法.

資料表示 :

從以上的這三個部份, 我們可以發現, 解題的過程, 就是在列, 行, 區塊的可行解的操作運算, 為了避免重複無意義的計算, 我們要把這些資訊記錄下來. Row/Column/Block 分別用來表示列, 行, 區塊的可行解. 由於可行解是 1-9 的數字集合, 並且只有存在及不存在兩種狀況, 因此用一個 unsigned short.  另外每一格的解決進度, 也會記錄下來.  接下來說明如何用這個資料結構來進行操作.

typedef struct tagSUDOKU_BOARD
{
    char Pattern[CELL_COUNT + 1];                       // For displaying
    unsigned short CellSet[CELL_COUNT];              // For Cell status tracking

    unsigned short RowSet[DIGIT_COUNT];             // Row possible set
    unsigned short ColumnSet[DIGIT_COUNT];        // Column possible set
    unsigned short BlockSet[DIGIT_COUNT];           // Block possible set
}    SUDOKU_BOARD, *LPSUDOKU_BOARD;

啟始動作 :

1. 預期的輸入, 是一個 81 個字元的字串, 所以要先把字串轉換成前述的資料表示. 檢查相對應字串的位置, 1~9 的數字代表這個位置已指定, 否則即未指定, 是要解決的部分.
2. 對每一列, 每一行, 每一區塊, 計算它的可行解.

推論動作 :

1. 對每一個格子, 計算它的可行解. 計算方式是對前述列, 行, 區塊, 作位元 AND 運算.
2. 運算結果計算它的位元為 1 的數量. 程式中以查表得出. 數量為 1 , 即為得出的答案.
3. 更新格子的字元表示, 可行解設定為 0. 代表已解.
4. 更新此格子所對應到的列, 行, 區塊可行解.

猜測動作 :

1. 對無法找出推論的子題, 進行猜測.
2. 找出具有最小可行解的格子.
3. 分別指定此格為可行解的其中之一
4. 更新此格子所對應到的列, 行, 區塊可行解.
5. 將此區塊加入待解問題列.

判斷動作 :

1. 對每一個格子, 計算它的可行解. 計算方式是對前述列, 行, 區塊, 作位元 AND 運算.
2. 如果任一未指定格子, 它的可行解為空, 那麼這一個子題就不存在解法.

效率 :

1. 數獨的解出速度, 會大幅度的和題目相關, 這一個題目頗為複雜, 解出的速度應該很有代表性. 一般的題目所需消耗時間不會高於這個時間.
2. 在 NoteBook 上實測, 可以達到 1.54 ms 解完的速度.

下載程式:

https://github.com/lxnick/SudokuSolver