OpenMV-AGAST算法代碼解析

我以前研究過一段時(shí)間的OpenMV的源碼，當(dāng)時(shí)的功力太淺，看不大懂，現(xiàn)在又重新的翻出來看。

先確定代碼在哪里，OpenMV是在資源受限的情況下執(zhí)行視覺算法，所以里面的很多寫法都是高效的，被優(yōu)化過的，這也是我讀的一個(gè)原因。

第一先讀第一個(gè)文件，是一個(gè)角點(diǎn)的快速查找算法。圖像基礎(chǔ)的操作都被封裝在了我現(xiàn)在展示的這個(gè)文件里面。

什么是角點(diǎn)？

角點(diǎn)通常被定義為兩條邊的交點(diǎn)，或者說，角點(diǎn)的局部鄰域應(yīng)該具有兩個(gè)不同區(qū)域的不同方向的邊界。角點(diǎn)檢測(Corner Detection)是計(jì)算機(jī)視覺系統(tǒng)中獲取圖像特征的一種方法，廣泛應(yīng)用于運(yùn)動(dòng)檢測、圖像匹配、視頻跟蹤、三維重建和目標(biāo)識別等，也可稱為特征點(diǎn)檢測。

這張圖可以說是非常的簡單明了。

角點(diǎn)的基本算法：選取一個(gè)局部窗口，將這個(gè)窗口沿著各個(gè)方向移動(dòng)，計(jì)算移動(dòng)前后窗口內(nèi)像素的差異的多少進(jìn)而判斷窗口對應(yīng)的區(qū)域是否是角點(diǎn)。

這個(gè)就是數(shù)學(xué)上的描述

我們尋找的角點(diǎn)就是去滑動(dòng)判斷。

這個(gè)就是我說的常見操作被打包的地方

它提供了低級圖像處理操作的定義和函數(shù)。像素格式,基本圖像統(tǒng)計(jì),濾波,邊緣檢測,形狀檢測,條碼識讀等。

它針對嵌入式設(shè)備和微控制器設(shè)計(jì),側(cè)重效率和代碼體積小。

使用定點(diǎn)數(shù)代替浮點(diǎn)數(shù)。直接對原始像素緩沖區(qū)進(jìn)行操作。

支持常見的圖像格式,像BMP,PPM,JPEG等。以及基本的機(jī)器視覺功能,比如模板匹配,QR碼識讀。

有在圖像上繪制基本形狀,線條,文字等的函數(shù)。

在可用時(shí)使用DMA和SIMD指令做硬件加速。不可用時(shí)回退到C實(shí)現(xiàn)。

使用C語言編寫,但可以通過FFI在更高級語言如MicroPython或Arduino中使用。

OpenMV開源開發(fā),作為他們的機(jī)器視覺相機(jī)模塊的一部分。但可以獨(dú)立使用。

這個(gè)是要看的算法的函數(shù)

這個(gè)算法現(xiàn)在討論的很少，我就簡單的說下：自適應(yīng)通用角點(diǎn)檢測(Adaptive and Generic Accelerated Segment Test，AGAST)算法，該算法是對FAST算法的一種改進(jìn)主要提升了速度與亮度變化下的魯棒性，但沒有解決尺度不變性。

現(xiàn)在接著看代碼。上面的代碼里面大體是實(shí)現(xiàn)了：

init5_8_pattern() 函數(shù):

初始化像素橫豎方向偏移量,用于后續(xù)快速訪問周圍像素。

agast58_detect() 函數(shù):

使用5x5個(gè)像素組成的模板匹配算法掃描圖像,找到角點(diǎn)。

像素值大于或小于中心點(diǎn)像素值的偏移量編碼成一個(gè)64位的特征碼。

如果匹配了角點(diǎn)模板,記錄下角點(diǎn)坐標(biāo)。

agast58_score() 函數(shù):

使用二分法找到最佳的閾值,進(jìn)一步提高角點(diǎn)質(zhì)量。

周圍5x5像素值和該閾值進(jìn)行比較,如果匹配角點(diǎn)模板,說明是角點(diǎn)。

不斷調(diào)整閾值,找到使得匹配模板的像素?cái)?shù)最多的閾值。

nonmax_suppression() 函數(shù):

應(yīng)用非極大值抑制進(jìn)一步提煉角點(diǎn)。

抑制掉像素梯度較小的不明顯角點(diǎn)。

alloc_keypoint() 函數(shù):

將檢測到的角點(diǎn)包裝成 keypoints 數(shù)據(jù)結(jié)構(gòu)。

第一次見這種寫法

該變量是用于儲(chǔ)存圖像像素的偏移量,用于快速訪問像素周圍的像素灰度值。

s_offset0 表示相對于當(dāng)前像素的左上方像素的偏移量。

具體來說:

s_offset0 表示相對于(x,y)的(x-1, y-1)像素

s_offset1 表示相對于(x,y)的(x-1, y)像素

s_offset2 表示相對于(x,y)的(x, y-1)像素

以此類推

通過預(yù)先計(jì)算好這些固定的偏移量,就可以通過 指針偏移 的方式,快速獲取周圍像素的值,而不需要每次都計(jì)算坐標(biāo)關(guān)系,從而提高效率。所以,這個(gè) s_offset0 變量就是一個(gè)優(yōu)化手段,用來加速周圍像素訪問。

我們看第一個(gè)函數(shù)的簽名，有個(gè)*，這里就要寫一下C語言的知識了。

先說這個(gè)函數(shù)的作用-agast58_detect() 是AGAST算法中用于檢測角點(diǎn)的主要函數(shù)。

它的主要功能是:

在輸入圖像img上,使用一個(gè)5x5像素模板滑動(dòng)掃描。

將中心像素與周圍像素進(jìn)行比較,大于或小于閾值b的編碼成一個(gè)特征碼。

如果特征碼與角點(diǎn)的模板匹配,則記錄該像素為角點(diǎn)候選。

所有檢測到的角點(diǎn)候選保存在 corner_t 結(jié)構(gòu)體數(shù)組 corners 中。

num_corners 為輸出參數(shù),用于返回檢測到的角點(diǎn)總數(shù)。

roi 參數(shù)用于指定只檢測圖像的某個(gè)區(qū)域。

其中corner_t結(jié)構(gòu)體包含了每個(gè)檢測到角點(diǎn)的x,y坐標(biāo)和score明顯性分?jǐn)?shù)。

agast檢測依賴于一個(gè)經(jīng)過優(yōu)化的像素訪問順序以及二值比較來實(shí)現(xiàn)高效運(yùn)算。

在C語言中,函數(shù)名前面的*代表該函數(shù)返回一個(gè)指針類型。

對于agast58_detect這個(gè)函數(shù):

返回值的類型是corner_t*,是一個(gè)指向corner_t結(jié)構(gòu)體的指針。

這個(gè)指針指向一個(gè)動(dòng)態(tài)分配的數(shù)組,用于存儲(chǔ)檢測到的所有角點(diǎn)。

加上*的原因:

返回一個(gè)指針,函數(shù)可以返回一個(gè)數(shù)組或?qū)ο?不僅僅是一個(gè)scalar值。

指針訪問內(nèi)存速度快,不需要拷貝整個(gè)數(shù)組。

函數(shù)執(zhí)行結(jié)束后,指針變量還可以被外部代碼訪問,相當(dāng)于函數(shù)可以修改外部變量。

把返回?cái)?shù)組的內(nèi)存管理交給調(diào)用者,函數(shù)執(zhí)行完就可以釋放內(nèi)部內(nèi)存,不用維護(hù)資源。

總結(jié)一下:

*表示返回一個(gè)指針

可以返回動(dòng)態(tài)數(shù)組/對象

提高效率,不拷貝大數(shù)組

指針可修改外部變量

內(nèi)存管理交給調(diào)用者

程序的實(shí)現(xiàn)里面大量的使用了指針的偏移，基本思想是：

直接通過指針運(yùn)算獲取相鄰像素,而不用每次計(jì)算坐標(biāo)。

預(yù)先計(jì)算好偏移量,例如左上角像素的偏移量是 -1行 -1列。

將這些固定偏移量存儲(chǔ)在變量中,比如s_offset0。

在訪問像素時(shí),直接基于指針偏移這個(gè)固定的值,這樣就跳過了坐標(biāo)計(jì)算。

例如,當(dāng)前指針指向像素 (x, y):

uint8_t *imgPtr = &img[y * width + x];

獲取左上角像素,不用偏移:

uint8_t leftUp = img[ (y-1) * width + (x-1) ]; // 需要計(jì)算坐標(biāo)

使用偏移:

int offset0 = -width - 1; // 預(yù)先計(jì)算偏移量 
uint8_t leftUp = imgPtr[offset0]; // 基于指針偏移

通過指針偏移,避免每次獲取相鄰像素時(shí)重復(fù)計(jì)算偏移量,這樣可以明顯減少計(jì)算量,從而加速像素訪問。

再看這個(gè)函數(shù),這個(gè)alloc_keypoint()函數(shù)是用于分配和初始化一個(gè)關(guān)鍵點(diǎn)結(jié)構(gòu)kp_t的。

它做了以下幾件事:

使用xalloc0()在堆上分配一個(gè)kp_t結(jié)構(gòu)的內(nèi)存,并初始化為0。

將傳入的x,y坐標(biāo)及score分?jǐn)?shù)存入kp_t中。

注釋里提到必須將描述子descriptor數(shù)組初始化為0。這里通過xalloc0()預(yù)先設(shè)置為0實(shí)現(xiàn)。

返回這個(gè)kp_t指針。

這樣調(diào)用者就可以拿到一個(gè)堆上分配的、坐標(biāo)與分?jǐn)?shù)填充了、描述子初始化為0的關(guān)鍵點(diǎn)結(jié)構(gòu)kp_t。

需要注意的是:

必須初始化描述子數(shù)組,后續(xù)的特征描述算子會(huì)填充描述子。

使用xalloc0()而不是malloc,可以自動(dòng)初始化內(nèi)存為0。

返回 kp_t 指針,調(diào)用者可以進(jìn)一步訪問關(guān)鍵點(diǎn)數(shù)據(jù)。

綜上,這是一個(gè)輔助函數(shù),用于根據(jù)坐標(biāo)分?jǐn)?shù)快速創(chuàng)建一個(gè)關(guān)鍵點(diǎn)結(jié)構(gòu).

它自己又重寫了一次這個(gè)malloc的函數(shù)，xalloc0()是一種自定義的內(nèi)存分配函數(shù),與malloc()類似,但是有一些額外的功能:

當(dāng)size為0時(shí),直接返回NULL,而不報(bào)錯(cuò)。這與malloc的行為不同。

使用gc_alloc在堆上分配內(nèi)存,這是MaixPy特有的 gc 堆內(nèi)存分配函數(shù)。

分配成功后用memset清零內(nèi)存。這是xalloc0的關(guān)鍵功能之一。

如果分配失敗,調(diào)用xalloc_fail導(dǎo)致程序異常。

返回清零后的內(nèi)存指針。

這樣使用xalloc0比malloc好在:

SIZE為0時(shí)不會(huì)錯(cuò)誤。

自動(dòng)清零內(nèi)存,不需再memset。

與MaixPy的GC堆內(nèi)存管理兼容。

出錯(cuò)時(shí)終止程序,不需要額外判斷返回NULL情況。

這個(gè)init5_8_pattern()函數(shù)是用于初始化圖像像素的8方向偏移量,這是AGAST算法的一個(gè)優(yōu)化。

它的作用是:

接收圖像的寬度width作為參數(shù)。

如果當(dāng)前寬度與已保存的s_width相同,直接返回,不再初始化,避免重復(fù)計(jì)算。

如果寬度變了,更新s_width為新寬度。

計(jì)算8個(gè)方向相對當(dāng)前像素點(diǎn)的偏移量:

s_offset0 (-1, -1) 左上角

s_offset1 (-1, 0) 正上方

...

s_offset7 (-1, 1) 左下角

偏移量根據(jù)圖像寬度width調(diào)整,即乘以width。

這樣,在后續(xù)檢測角點(diǎn)時(shí),可以直接用這些預(yù)計(jì)算偏移訪問周圍像素,不需要每次都計(jì)算坐標(biāo)偏移,加速了像素訪問。通過一次初始化,減少重復(fù)計(jì)算,從而提升檢測效率。充分利用了圖像具有固定尺寸的特點(diǎn)。

這個(gè)agast_detect()函數(shù)實(shí)現(xiàn)了AGAST角點(diǎn)檢測的完整流程:

初始化5x5窗口的偏移量init5_8_pattern()

調(diào)用agast58_detect()函數(shù)進(jìn)行角點(diǎn)檢測,返回檢測到的角點(diǎn)數(shù)組

對每一個(gè)角點(diǎn)調(diào)用agast58_score()計(jì)算明顯性分?jǐn)?shù)

進(jìn)行非極大值抑制nonmax_suppression(),過濾掉弱角點(diǎn)

將剩下的角點(diǎn)保存在輸出的keypoints數(shù)組中

釋放臨時(shí)的角點(diǎn)內(nèi)存fb_free()

所以這個(gè)函數(shù)將角點(diǎn)檢測、評分和濾波三個(gè)階段包裝起來,實(shí)現(xiàn)了一個(gè)完整的AGAST角點(diǎn)檢測器。

它接受輸入圖像,檢測參數(shù)(threshold),區(qū)域等,最終輸出經(jīng)過優(yōu)化的高質(zhì)量角點(diǎn)集。

其實(shí)還沒有完全說完，這個(gè)函數(shù)很長：

大概是這樣的

初始化循環(huán)邊界 - xsizeB, ysizeB 定義了只在圖像有效區(qū)域內(nèi)循環(huán)

分配內(nèi)存 - 使用 fb_alloc 在內(nèi)存池中分配 corner_t 數(shù)組

雙重循環(huán) - 外層循環(huán) y 方向,內(nèi)層循環(huán) x 方向掃描每個(gè)像素

像素比較 - 在 homogeneous 和 structured 兩個(gè)標(biāo)簽下,使用偏移像素比較中心像素,判斷是否匹配角點(diǎn)模式

記錄角點(diǎn) - 如果匹配就記錄下角點(diǎn)坐標(biāo)到 corners 數(shù)組

返回結(jié)果 - 將檢測到的角點(diǎn)數(shù)量賦值給 num_corners,并返回角點(diǎn)數(shù)組

里面的循環(huán)做的這個(gè)事情比較多。

同樣下頭的還有一個(gè)函數(shù)， agast58_score() 函數(shù)主要實(shí)現(xiàn)了A-GAST算法中使用二分法搜索最佳閾值的步驟。

主要流程是:

初始化閾值的上下限 bmin、bmax。

不斷循環(huán),將當(dāng)前閾值 b 代入角點(diǎn)模式比較。

如果匹配了角點(diǎn)模式,則把 b 作為新的下限 bmin。

如果不匹配角點(diǎn)模式,則把 b 作為新的上限 bmax。

通過二分不斷逼近使得角點(diǎn)模式匹配的像素?cái)?shù)最多的閾值。

當(dāng)上下限只差1時(shí),返回最佳閾值 bmin。

關(guān)鍵點(diǎn):

使用二分搜索提升角點(diǎn)明顯性。

像素比較使用偏移訪問提速。

通過不斷調(diào)整閾值 b 尋找最佳角點(diǎn)模式匹配。

返回最佳閾值,作為該像素角點(diǎn)的分?jǐn)?shù)。

看下這個(gè)檢測算法里面的這個(gè)句子，

循環(huán)遍歷所有檢測到的角點(diǎn) corners

計(jì)算每個(gè)角點(diǎn)的像素指針 - 通過角點(diǎn)的 x,y 坐標(biāo),計(jì)算在圖像像素?cái)?shù)組中的偏移量

調(diào)用 agast58_score() 并傳入像素指針和閾值threshold

agast58_score() 將返回0-255范圍的分?jǐn)?shù),記錄在 corner[i].score 中

最后每個(gè)角點(diǎn)除了有坐標(biāo)x,y之外,還有一個(gè)分?jǐn)?shù)score表示角點(diǎn)的明顯程度。

所以這個(gè)過程對每一個(gè)角點(diǎn)候選運(yùn)行了二分搜索,找到了最佳的閾值,作為該點(diǎn)的分?jǐn)?shù)。分?jǐn)?shù)高的角點(diǎn)匹配度更好,更明顯,更穩(wěn)定,這樣后續(xù)就可以基于分?jǐn)?shù)進(jìn)行非極大值抑制來過濾掉弱角點(diǎn)。這種為每個(gè)角點(diǎn)單獨(dú)密集計(jì)算的方式也是AGAST算法區(qū)別于FAST算法的主要特點(diǎn)之一。

這個(gè)非極大值抑制(non-maximum suppression)函數(shù)的作用是去除重復(fù)或邊緣響應(yīng)較弱的非極大值角點(diǎn),只保留每個(gè)局部區(qū)域響應(yīng)最強(qiáng)的角點(diǎn)。

主要步驟是:

計(jì)算每一行的起始角點(diǎn)索引,用于快速查找上下行角點(diǎn)。

對每個(gè)角點(diǎn),檢查其上下左右4鄰域是否存在更高分?jǐn)?shù)的角點(diǎn)。

如果存在,則抑制該角點(diǎn),不將其錄入最終角點(diǎn)集。

只保留每個(gè)局部區(qū)域分?jǐn)?shù)最高的角點(diǎn)。

檢查內(nèi)存是否足夠,不足則試圖釋放內(nèi)存使能繼續(xù)錄入角點(diǎn)。

將抑制后的角點(diǎn)保存到輸出數(shù)組中。

這通過只保留局部最大值點(diǎn),去除了邊緣響應(yīng)較弱的重復(fù)角點(diǎn),提升了角點(diǎn)質(zhì)量。

AGAST算法相比FAST算法加入了這個(gè)非極大值抑制步驟,可以有效提升角點(diǎn)的重復(fù)性和分布均勻性。

里面有一個(gè)這樣的句子，是初始化 row_start 數(shù)組,row_start 數(shù)組用來記錄每一行的第一個(gè)角點(diǎn)在 corners 數(shù)組中的索引。

具體地:

row_start 的大小是圖像總行數(shù)+1,即 last_row + 1

使用 -1 來表示該行沒有檢測到角點(diǎn)

初始化所有值為 -1,表示剛開始還沒有任何角點(diǎn)

后面在檢測到角點(diǎn)時(shí)會(huì)記錄:

row_start[角點(diǎn)所在行] = 角點(diǎn)在corners數(shù)組中的索引

所以row_start[y] = x 表示:

第y行的第一個(gè)角點(diǎn)在corners數(shù)組中的索引為x

這樣初始化row_start為-1VeryAmerican,在后續(xù)的非極大值抑制中,就可以通過row_start數(shù)組快速獲取上下行的角點(diǎn)信息,從而高效實(shí)現(xiàn)非極大值抑制。

審核編輯：劉清