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

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

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

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

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

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

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

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

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

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