FPGA實(shí)現(xiàn)的連通域識(shí)別算法升級(jí)

1、FPGA實(shí)現(xiàn)的連通域識(shí)別算法升級(jí)代碼在這：還做了個(gè)算法演示動(dòng)畫：之前寫過這篇文章FPGA實(shí)現(xiàn)的實(shí)時(shí)流水線連通域標(biāo)記算法。這個(gè)文章是兩年前寫的，里面介紹的算法是四五年前寫的。這個(gè)版本的算法在對(duì)二值圖像進(jìn)行連通域識(shí)別之前需要先進(jìn)行去噪、取邊緣操作，然后再對(duì)邊緣圖像進(jìn)行連通域識(shí)別。識(shí)別m,n,u,w形的連通域是沒有問題的，但遇到螺旋形的就貌似會(huì)出問題，會(huì)對(duì)它視而不見。不過在實(shí)際應(yīng)用中這樣會(huì)導(dǎo)致問題的形狀幾乎不會(huì)出現(xiàn)，所以這個(gè)算法也完全是可應(yīng)用的。當(dāng)初想著要把圖像進(jìn)行去噪取邊之后再進(jìn)行連通域識(shí)別，主要的考慮是想著如果圖像邊緣周邊噪點(diǎn)多，可能會(huì)影響連通域識(shí)別算法，把圖像變得只剩下嚴(yán)格的邊緣之后再進(jìn)行處理

2、，貌似看起來要簡(jiǎn)單一些。但后來算法實(shí)現(xiàn)起來的那個(gè)狀態(tài)機(jī)也有點(diǎn)復(fù)雜。不過當(dāng)時(shí)我還沾沾自喜，覺得自己整出來了一個(gè)還有點(diǎn)復(fù)雜的算法。真是蠢人不知自己蠢。人類就是擅長(zhǎng)把簡(jiǎn)單的事情搞復(fù)雜了還自以為很了不起。這個(gè)老版本的代碼有點(diǎn)復(fù)雜，當(dāng)時(shí)也沒寫多少注釋，所以也不便大家使用。最近又想著是不是能改進(jìn)一下這個(gè)算法。首先不需要去噪和取邊緣這些預(yù)處理，其次處理的流程不需要狀態(tài)機(jī)控制，就像算子法那樣流水線的掃過去就能完成識(shí)別。仔細(xì)想了一下之后發(fā)現(xiàn)其實(shí)這樣也是可以實(shí)現(xiàn)的，當(dāng)年沒想到這個(gè)算法可能還是因?yàn)楫?dāng)年水平低，而且先入為主的就認(rèn)為這樣對(duì)于噪點(diǎn)多的圖像會(huì)很復(fù)雜，要考慮很多情況。而現(xiàn)在重新思考一下又發(fā)現(xiàn)，噪點(diǎn)多也不會(huì)在邏

3、輯上帶來更多的麻煩，邏輯還是那個(gè)邏輯，邏輯是正確的就可以應(yīng)對(duì)所有情況。并不是有很多情況就需要很多的邏輯去應(yīng)對(duì)，而是幾個(gè)簡(jiǎn)單且嚴(yán)密的邏輯就可以應(yīng)對(duì)所有情況。算法也就是好比是一個(gè)邏輯處理公式，一個(gè)簡(jiǎn)單的分形公式可以生成千變?nèi)f化的復(fù)雜圖像，一個(gè)邏輯嚴(yán)密的算法也可以應(yīng)對(duì)任何的圖像情況。所以這個(gè)算法無(wú)需預(yù)處理，也不會(huì)出錯(cuò)，一個(gè)點(diǎn)也會(huì)被識(shí)別成一個(gè)連通域。當(dāng)然如果你不希望小噪點(diǎn)也被識(shí)別出來，可以先進(jìn)行去噪處理。也可以直接就識(shí)別，然后在輸出結(jié)果時(shí)把點(diǎn)數(shù)少的連通域忽略掉。在實(shí)驗(yàn)這個(gè)新思路時(shí)我又忽然想到了一個(gè)可以在PC上實(shí)現(xiàn)的非常簡(jiǎn)單的連通域識(shí)別算法，那就是用遞歸法來實(shí)現(xiàn)。用遞歸法來實(shí)現(xiàn)連通域識(shí)別真的非常簡(jiǎn)單。只

4、需要寫一個(gè)標(biāo)記函數(shù)，掃描圖像時(shí)找到一個(gè)未標(biāo)記黑點(diǎn)時(shí)就調(diào)用這個(gè)函數(shù)：標(biāo)記該點(diǎn)，并尋找該點(diǎn)的8鄰域中有沒有未標(biāo)黑點(diǎn)，有就遞歸調(diào)用自己。就這樣就可以了。我用Python寫了個(gè)動(dòng)畫來演示這兩種連通域識(shí)別算法，也就是遞歸法和并行流水線法。遞歸法需要隨機(jī)讀取數(shù)據(jù)，并行流水線法只需要順序掃描一遍圖像就可以了。如果你下載并運(yùn)行了這個(gè)python代碼，還可以控制它逐幀的進(jìn)行查看。Python代碼看起來有點(diǎn)長(zhǎng)，但很多都是在處理做動(dòng)畫的問題，真正算法部分沒多長(zhǎng)，尤其是遞歸法。這個(gè)并行流水線法的大致思路是這樣的：一個(gè)像素點(diǎn)有8個(gè)相鄰的點(diǎn)。上面3個(gè)，下面3個(gè)，左邊1個(gè)，右邊一個(gè)。當(dāng)從左往右逐行掃描圖像時(shí)，正在被掃描的這

5、個(gè)點(diǎn)應(yīng)該被標(biāo)上什么標(biāo)記，其實(shí)只和在它之前已經(jīng)被掃描過的點(diǎn)，也就是它鄰域中上面3個(gè)和左邊1個(gè)這4個(gè)點(diǎn)有關(guān)。所以第一個(gè)要點(diǎn)就是，某個(gè)點(diǎn)該被標(biāo)記什么標(biāo)號(hào)，只和它前鄰域的四個(gè)點(diǎn)有關(guān)，也就是左邊，左上，正上，右上這四個(gè)點(diǎn)。那么這個(gè)算法其實(shí)就相當(dāng)于用這樣一個(gè)2x3的算子掃描圖像，就能得到結(jié)果，只需緩存一行圖像。接下來就是對(duì)鄰域這4個(gè)點(diǎn)的情況進(jìn)行判斷來確定當(dāng)前這個(gè)點(diǎn)該怎么標(biāo)記?？偣惨簿?個(gè)點(diǎn)，最多也就是16種情況，但實(shí)際上概括起來只有三大種情況：一、 前鄰域這4個(gè)點(diǎn)都是白點(diǎn)，說明這是一個(gè)新連通域的起始點(diǎn)，給它標(biāo)上一個(gè)新的標(biāo)號(hào)。二、4個(gè)點(diǎn)中有兩個(gè)點(diǎn)的標(biāo)號(hào)不同，這個(gè)情況只有兩種，要么是右上點(diǎn)和左邊點(diǎn)的標(biāo)號(hào)不同，

6、要么是右上點(diǎn)和左上點(diǎn)標(biāo)號(hào)不同。不會(huì)存在有三個(gè)點(diǎn)標(biāo)號(hào)都不同和四個(gè)點(diǎn)標(biāo)號(hào)都不同的情況，至于為什么，大家可以自己想一想。之所以會(huì)存在這種有兩個(gè)點(diǎn)標(biāo)號(hào)不同的情況，是因?yàn)閁，W形連通域的存在，在一開始掃描時(shí)會(huì)被當(dāng)作兩個(gè)連通域，掃描到下面才發(fā)現(xiàn)它們兩個(gè)實(shí)際上是連通的，遇到這種情況就需要把這兩個(gè)連通域的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行合并，并把右上那個(gè)點(diǎn)的標(biāo)號(hào)改為，和當(dāng)前這個(gè)點(diǎn)的標(biāo)號(hào)標(biāo)為左邊點(diǎn)或左上點(diǎn)的標(biāo)號(hào)。這就是順序掃描法所需要面對(duì)的麻煩之處，遞歸法就不存在這個(gè)問題，這里具體是如何處理的大家可參考Python版的代碼三、4個(gè)點(diǎn)中有1、2、3或4個(gè)已標(biāo)點(diǎn)，但它們的標(biāo)號(hào)都是相同的，就把當(dāng)前點(diǎn)標(biāo)上這個(gè)標(biāo)號(hào)。實(shí)際寫代碼時(shí)，把前面兩種

7、情況判斷掉之后，剩下的就是這種情況，所以這個(gè)情況不需要寫很多if判斷，寫個(gè)else就行了。在實(shí)現(xiàn)上有一個(gè)要點(diǎn)就是，要用另外一個(gè)數(shù)組存放每個(gè)標(biāo)號(hào)連通域的信息，在Verilog實(shí)現(xiàn)時(shí)會(huì)用另外一個(gè)RAM，老版算法中也是這么做的。當(dāng)掃描到某個(gè)已標(biāo)點(diǎn)時(shí)，要用它的標(biāo)號(hào)去查這個(gè)連通域信息表里面存放的它的真實(shí)標(biāo)號(hào)。因?yàn)榇嬖跇?biāo)號(hào)合并的問題，之前標(biāo)記的標(biāo)號(hào)可能已經(jīng)被并入了別的標(biāo)號(hào)，這個(gè)改動(dòng)只會(huì)出現(xiàn)在這個(gè)連通域信息列表中，不會(huì)出現(xiàn)在標(biāo)記數(shù)組中，所以要先去查表獲得真實(shí)標(biāo)號(hào)再進(jìn)行判斷。這是關(guān)鍵一步。還有一個(gè)關(guān)鍵是如何判斷一個(gè)連通域是否已經(jīng)全部掃描完成。完成時(shí)要輸出這個(gè)連通域的信息結(jié)果。所以如果不知道一個(gè)連通域什么時(shí)候掃

8、描完成，那這個(gè)算法就沒有輸出。這個(gè)算法判斷一個(gè)連通域是否完成在它完成的那一行還判斷不了。要到掃描下一行時(shí)查看上面已標(biāo)點(diǎn)的信息時(shí)才能發(fā)現(xiàn)，具體如何判斷的請(qǐng)參考代碼。這個(gè)算法的邏輯是嚴(yán)格的，也就是它不會(huì)出錯(cuò)，如果大家不信可以拿它的結(jié)果和遞歸法的結(jié)果做對(duì)比，遞歸法很容易想明白它是嚴(yán)格不會(huì)出錯(cuò)的。Python版的代碼還是比較容易理解的。Verilog代碼里，除了上述的邏輯判斷代碼之外，還多了一些處理Ram的讀寫和流水線寄存器數(shù)據(jù)一致性的代碼。因?yàn)檫@個(gè)連通域識(shí)別算法和之前FPGA圖像處理基本技巧這篇文章中提到的算子法是不一樣的。算子法計(jì)算之后的數(shù)據(jù)不需要寫回Ram，也不能寫回。而連通域識(shí)別算法的結(jié)果是需

9、要寫回的，因?yàn)橄乱恍械呐袛噙€需要上一行的結(jié)果。這需要寫回處理起來就麻煩一些，對(duì)Ram的讀寫也和算子法中有所不同。還需要處理流水線寄存器數(shù)據(jù)一致性的問題。然后最關(guān)鍵的是，由于FPGA實(shí)現(xiàn)上的限制，這個(gè)Verilog版本的算法不能和前述的算法邏輯做到完全等價(jià)，也就是說有個(gè)地方它不能完全實(shí)現(xiàn)，這樣有些特殊結(jié)構(gòu)的連通域就會(huì)導(dǎo)致算法輸出的統(tǒng)計(jì)結(jié)果會(huì)漏掉一些點(diǎn)。具體什么樣的結(jié)構(gòu)會(huì)導(dǎo)致問題大家可參考這個(gè)圖片文件。但在實(shí)際應(yīng)用中遇到奇怪形狀的概率并不大，而且統(tǒng)計(jì)也只是會(huì)漏掉很少的一些點(diǎn)，所以基本并不影響使用。注意，不是會(huì)漏掃描標(biāo)記一些點(diǎn)，只是統(tǒng)計(jì)的時(shí)候會(huì)在特殊情況下丟失掉一些點(diǎn)的數(shù)據(jù)。這比老版本的算法也算是有進(jìn)步了，老版本的算法在遇到螺旋形時(shí)會(huì)直接視而不見，不會(huì)給出任何結(jié)果。這個(gè)算法不會(huì)出現(xiàn)視而不見的情況，只是會(huì)在特殊情況下可能漏報(bào)。這個(gè)不等價(jià)的原因就是，Verilog在實(shí)現(xiàn)時(shí)實(shí)際上并沒有實(shí)現(xiàn)用已標(biāo)點(diǎn)的標(biāo)號(hào)去查詢到它的真實(shí)標(biāo)號(hào)之后再去獲取它真實(shí)信息，這樣需要讀兩次RAM，RAM只有兩個(gè)端口，都用來讀數(shù)據(jù)了就沒法再用來寫回?cái)?shù)據(jù)了。所以在掃描合并連通域的時(shí)候會(huì)把合并的結(jié)果也寫入到被合并掉的標(biāo)號(hào)中，但之后就不好再更新這個(gè)已經(jīng)被合并掉的標(biāo)號(hào)，如果之后這個(gè)被合并掉的標(biāo)號(hào)又再出現(xiàn)了，就有可能會(huì)出現(xiàn)信息丟失，因?yàn)檫@個(gè)被合并掉的標(biāo)號(hào)中的