1. 從“數(shù)白點(diǎn)”到連通分量bwconncomp的工程價(jià)值在圖像處理尤其是二值圖像分析領(lǐng)域我們經(jīng)常遇到一個(gè)看似簡(jiǎn)單卻至關(guān)重要的任務(wù)數(shù)清楚圖像里有多少個(gè)獨(dú)立的“物體”。比如在一張細(xì)胞顯微圖像中我們需要統(tǒng)計(jì)細(xì)胞數(shù)量在一張衛(wèi)星地圖中我們需要識(shí)別并計(jì)數(shù)獨(dú)立的建筑物或車(chē)輛。這個(gè)“數(shù)物體”的過(guò)程在專(zhuān)業(yè)上被稱(chēng)為“連通分量分析”。對(duì)于MATLAB用戶而言bwconncomp函數(shù)就是執(zhí)行這項(xiàng)任務(wù)的瑞士軍刀。它遠(yuǎn)不止是一個(gè)簡(jiǎn)單的計(jì)數(shù)器其背后是一套高效、穩(wěn)健的算法實(shí)現(xiàn)直接關(guān)系到后續(xù)特征提取、目標(biāo)跟蹤等高級(jí)分析的準(zhǔn)確性。很多初學(xué)者調(diào)用它得到結(jié)果后便不再深究但當(dāng)你處理百萬(wàn)像素級(jí)的圖像或者對(duì)實(shí)時(shí)性有要求時(shí)理解bwconncomp的“內(nèi)功心法”——其采用的算法、內(nèi)存管理策略以及參數(shù)背后的邏輯——就變得至關(guān)重要。這不僅能幫你避免一些隱蔽的坑比如為什么同樣的圖像4連通和8連通數(shù)出來(lái)的物體個(gè)數(shù)不一樣更能讓你在優(yōu)化代碼、處理特殊圖像時(shí)游刃有余。2. 連通性一切分析的基礎(chǔ)與歧義之源在深入算法之前我們必須徹底厘清一個(gè)核心概念連通性。這是bwconncomp乃至所有二值圖像分析算法的基石也是最容易產(chǎn)生混淆的地方。2.1 鄰域定義4連通 vs. 8連通想象一張由黑白像素組成的網(wǎng)格圖。一個(gè)白色像素前景像素值為1如何與它的鄰居“手拉手”形成一個(gè)整體連通分量這取決于我們?nèi)绾味x“鄰居”。4連通一個(gè)像素只與其上、下、左、右四個(gè)方向的直接相鄰像素被認(rèn)為是連通的。這類(lèi)似于國(guó)際象棋中“國(guó)王”的走法只能走一步不能走斜線。在這種規(guī)則下斜對(duì)角線的兩個(gè)像素即使都是白色只要沒(méi)有通過(guò)上下左右的路徑連接它們就屬于不同的物體。8連通一個(gè)像素與其上、下、左、右、左上、右上、左下、右下共八個(gè)方向的像素都被認(rèn)為是連通的。這類(lèi)似于國(guó)際象棋中“國(guó)王”可以走到任何相鄰格子。顯然8連通規(guī)則下像素之間連接的可能性更大更容易將離散的像素塊“粘合”成一個(gè)整體。2.2 連通性選擇帶來(lái)的根本性差異這個(gè)選擇絕非隨意它直接決定了你“看到”的物體是什么。我們來(lái)看一個(gè)經(jīng)典的例子考慮一個(gè)2x2的純白色像素塊1 1 1 1在4連通規(guī)則下這四個(gè)像素是如何連接的呢左上角的“1”只能連通到右邊和下邊的“1”。右上角的“1”連通到左邊的“1”即左上角和下邊的“1”。左下角的“1”連通到上邊的“1”即左上角和右邊的“1”。你會(huì)發(fā)現(xiàn)通過(guò)這種“上下左右”的傳遞這四個(gè)像素最終都能彼此連接到。因此4連通規(guī)則下這被視為1個(gè)物體。在8連通規(guī)則下由于包含了斜對(duì)角連接這四個(gè)像素的連接更加直接和緊密顯然也是1個(gè)物體。這個(gè)例子似乎顯示兩者結(jié)果一致。但看下面這個(gè)“棋盤(pán)格”缺角的情況1 0 0 14連通左上角的“1”和右下角的“1”之間沒(méi)有一條由“上下左右”移動(dòng)構(gòu)成的、全部為“1”的路徑因?yàn)橹虚g被“0”隔開(kāi)了。因此它們被認(rèn)為是2個(gè)獨(dú)立的物體。8連通左上角的“1”可以通過(guò)“右下”這個(gè)斜對(duì)角方向直接連接到右下角的“1”因?yàn)?連通允許斜向連接。因此它們被認(rèn)為是1個(gè)物體。這個(gè)簡(jiǎn)單的例子揭示了核心8連通性會(huì)得到更少、但可能更大的連通區(qū)域4連通性則會(huì)得到更多、更細(xì)碎的連通區(qū)域。在細(xì)胞分析中如果兩個(gè)細(xì)胞邊緣恰好挨得很近8連通可能會(huì)錯(cuò)誤地將它們合并為一個(gè)而在文本識(shí)別中8連通能更好地將筆畫(huà)有斷點(diǎn)的字符連接起來(lái)。因此bwconncomp的conn參數(shù)可取值4或8或更高的多維連通性矩陣是你的第一個(gè)重要決策點(diǎn)它必須基于你對(duì)“物體”的物理定義來(lái)選擇。注意MATLAB的默認(rèn)連通性是8連通。這意味著如果你不指定conn參數(shù)函數(shù)會(huì)使用8鄰域規(guī)則。這是一個(gè)常見(jiàn)的陷阱如果你心里想的是4連通分析結(jié)果就會(huì)出乎意料。3. bwconncomp算法內(nèi)核兩遍掃描法與等價(jià)類(lèi)解析bwconncomp函數(shù)內(nèi)部實(shí)現(xiàn)的核心是經(jīng)典的兩遍掃描算法這是一種高效且節(jié)省內(nèi)存的連通分量標(biāo)記方法。理解它你就理解了函數(shù)大部分的行為邏輯。3.1 第一遍掃描 provisional labeling算法首先從左到右、從上到下遍歷圖像的每一個(gè)像素除了邊界。遇到背景像素0直接跳過(guò)。遇到前景像素1檢查它當(dāng)前已掃描過(guò)的鄰居根據(jù)conn參數(shù)可能是左、上、左上、右上。注意為了效率和避免重復(fù)通常只檢查左和上這兩個(gè)最重要的鄰居。情況A所有已檢查的鄰居都是背景0。那么這個(gè)像素是一個(gè)新物體的開(kāi)始。算法給它分配一個(gè)新的、唯一的標(biāo)簽比如標(biāo)簽123...。情況B有一個(gè)或多個(gè)鄰居已經(jīng)有標(biāo)簽。如果這些鄰居的標(biāo)簽都相同那么當(dāng)前像素繼承這個(gè)標(biāo)簽。如果這些鄰居有不同的標(biāo)簽比如左邊的像素標(biāo)為2上邊的像素標(biāo)為5這意味著之前被認(rèn)為可能是兩個(gè)不同的物體在當(dāng)前像素這里發(fā)現(xiàn)了它們是連通的這時(shí)算法會(huì)記錄下標(biāo)簽2和標(biāo)簽5是等價(jià)的它們屬于同一個(gè)物體。當(dāng)前像素會(huì)繼承其中一個(gè)標(biāo)簽比如較小的那個(gè)標(biāo)簽2但核心是建立了等價(jià)關(guān)系。第一遍掃描結(jié)束后圖像中的每個(gè)前景像素都被賦予了一個(gè)臨時(shí)標(biāo)簽但同時(shí)我們也得到了一張記錄著“哪些標(biāo)簽其實(shí)是一伙的”等價(jià)關(guān)系表。3.2 第二遍掃描 resolving equivalences第二遍掃描的任務(wù)是解決這些等價(jià)關(guān)系讓屬于同一個(gè)物體的所有像素?fù)碛凶罱K統(tǒng)一的標(biāo)簽。算法再次遍歷所有像素。對(duì)于每個(gè)有臨時(shí)標(biāo)簽的前景像素算法去查詢等價(jià)關(guān)系表找到這個(gè)臨時(shí)標(biāo)簽所屬的等價(jià)類(lèi)的根標(biāo)簽通常是最小的那個(gè)標(biāo)簽。將這個(gè)根標(biāo)簽作為該像素的最終標(biāo)簽寫(xiě)入輸出矩陣或直接用于內(nèi)部統(tǒng)計(jì)。這個(gè)過(guò)程結(jié)束后每個(gè)連通分量就有了唯一且連續(xù)的標(biāo)簽。bwconncomp并不會(huì)默認(rèn)返回這個(gè)標(biāo)簽矩陣那是bwlabel函數(shù)的工作但它內(nèi)部一定完成了這個(gè)計(jì)算以便進(jìn)行后續(xù)的統(tǒng)計(jì)。3.3 bwconncomp的輸出結(jié)構(gòu)體信息寶庫(kù)函數(shù)返回的是一個(gè)結(jié)構(gòu)體這才是它的精髓所在。我們拆解一下CC bwconncomp(BW); % 假設(shè)BW是二值圖像 disp(CC)輸出可能包含以下字段Connectivity: 你使用的連通性如8。ImageSize: 原始圖像的大小如[512, 512]。NumObjects: 最重要的結(jié)果之一連通分量的總數(shù)。PixelIdxList: 一個(gè)元胞數(shù)組這是核心中的核心。元胞數(shù)組的每個(gè)元素對(duì)應(yīng)一個(gè)連通分量。每個(gè)元素本身是一個(gè)向量里面存儲(chǔ)了該連通分量所有像素在圖像中的線性索引。PixelIdxList的存儲(chǔ)方式非常巧妙且高效。它沒(méi)有存儲(chǔ)一個(gè)和原圖一樣大的標(biāo)簽矩陣而是只記錄了每個(gè)物體像素的位置。這帶來(lái)兩個(gè)好處一是節(jié)省內(nèi)存尤其是當(dāng)物體稀疏時(shí)二是后續(xù)計(jì)算物體屬性如面積、質(zhì)心極其方便。例如計(jì)算第一個(gè)物體的面積就是length(CC.PixelIdxList{1})獲取第一個(gè)物體所有像素的坐標(biāo)可以用[row, col] ind2sub(CC.ImageSize, CC.PixelIdxList{1})。4. 實(shí)戰(zhàn)中的關(guān)鍵考量與性能陷阱理解了原理在實(shí)際使用中我們才能避開(kāi)坑用好工具。4.1 內(nèi)存與性能大圖像處理策略兩遍掃描算法的時(shí)間復(fù)雜度大致是O(N)N是像素總數(shù)效率很高。但內(nèi)存方面需要注意標(biāo)簽矩陣第一遍掃描需要?jiǎng)?chuàng)建一個(gè)與圖像同大小的矩陣來(lái)存儲(chǔ)臨時(shí)標(biāo)簽int32或類(lèi)似類(lèi)型。對(duì)于非常大的圖像如數(shù)億像素這個(gè)矩陣本身就會(huì)消耗可觀的內(nèi)存。等價(jià)表管理如果圖像非常復(fù)雜比如細(xì)碎的噪聲會(huì)產(chǎn)生大量微小區(qū)域等價(jià)關(guān)系表可能會(huì)膨脹。優(yōu)化建議預(yù)處理是關(guān)鍵在使用bwconncomp前務(wù)必進(jìn)行有效的圖像預(yù)處理。使用bwareaopen濾除面積小于某個(gè)閾值的噪聲點(diǎn)可以極大地減少連通分量的數(shù)量從而提升速度和降低內(nèi)存消耗。BW_clean bwareaopen(BW, 50); % 移除面積小于50像素的連通區(qū)域 CC bwconncomp(BW_clean);按需索取如果你只需要物體個(gè)數(shù)bwconncomp是最高效的。如果你還需要每個(gè)物體的具體屬性如面積、周長(zhǎng)、取向那么后續(xù)調(diào)用regionprops(CC, ...)是標(biāo)準(zhǔn)流程。但注意regionprops會(huì)根據(jù)PixelIdxList重新計(jì)算各種屬性如果圖像極大計(jì)算所有屬性可能很慢。應(yīng)只請(qǐng)求你需要的屬性例如regionprops(CC, Area, Centroid)。考慮分塊處理對(duì)于極端大的圖像如果內(nèi)存不足可能需要將圖像分塊分別進(jìn)行連通分量分析然后再謹(jǐn)慎地合并邊界上的結(jié)果這非常復(fù)雜通常應(yīng)優(yōu)先考慮升級(jí)硬件或優(yōu)化圖像分辨率。4.2 連通性矩陣超越4和8對(duì)于二維圖像conn參數(shù)除了標(biāo)量4和8還可以接受一個(gè)3x3的矩陣來(lái)定義自定義的連通性。矩陣中心代表當(dāng)前像素非零元素的位置定義了哪些鄰居被認(rèn)為是連通的。 例如conn_4 [0 1 0; 1 1 1; 0 1 0]; % 這等價(jià)于 conn4 conn_8 ones(3); % 這等價(jià)于 conn8 conn_custom [1 0 1; 0 1 0; 1 0 1]; % 一個(gè)“X”形連通只連接對(duì)角像素自定義連通性在分析具有特殊結(jié)構(gòu)或方向的圖案時(shí)非常有用。對(duì)于三維二值圖像如CT掃描數(shù)據(jù)conn可以是6、18或26分別對(duì)應(yīng)三維空間中的面連通、邊連通和點(diǎn)連通。4.3 與bwlabel和regionprops的協(xié)作關(guān)系MATLAB生態(tài)中與此相關(guān)的函數(shù)主要有三個(gè)明確分工有助于正確選擇bwconncomp:計(jì)算引擎。專(zhuān)注于高效地找到所有連通分量并以索引列表形式存儲(chǔ)。它是后續(xù)所有分析的基礎(chǔ)。bwlabel:bwconncomp的“表親”。它直接返回一個(gè)標(biāo)簽矩陣L其中每個(gè)像素的值是其所屬連通分量的編號(hào)0表示背景。當(dāng)你需要可視化標(biāo)簽結(jié)果或者需要進(jìn)行基于像素位置的復(fù)雜操作時(shí)bwlabel的輸出更直觀。但生成標(biāo)簽矩陣本身比生成PixelIdxList更耗內(nèi)存。內(nèi)部實(shí)現(xiàn)上bwlabel很可能調(diào)用了與bwconncomp類(lèi)似的算法只是輸出形式不同。regionprops:屬性提取器。它接受bwconncomp返回的結(jié)構(gòu)體CC或者標(biāo)簽矩陣L作為輸入計(jì)算并返回每個(gè)連通分量的幾何、灰度等屬性面積、周長(zhǎng)、質(zhì)心、邊界框等。它是建立在bwconncomp工作成果之上的高級(jí)工具。標(biāo)準(zhǔn)工作流是BW(預(yù)處理) -CC bwconncomp(BW)-stats regionprops(CC, ‘Area’, ‘Centroid’)。5. 一個(gè)完整案例從圖像到物體分析報(bào)告讓我們通過(guò)一個(gè)模擬的細(xì)胞計(jì)數(shù)場(chǎng)景串聯(lián)所有知識(shí)點(diǎn)。% 1. 模擬生成一張帶有噪聲的細(xì)胞圖像圓形亮點(diǎn) [X, Y] meshgrid(1:500, 1:500); BW false(500, 500); % 隨機(jī)生成一些圓形細(xì)胞 centers randi([50, 450], 15, 2); % 15個(gè)中心點(diǎn) radii randi([10, 25], 15, 1); % 隨機(jī)半徑 for i 1:15 BW BW | ((X - centers(i,1)).^2 (Y - centers(i,2)).^2 radii(i)^2); end % 添加一些椒鹽噪聲 noise rand(500,500) 0.01; BW_noisy xor(BW, noise); % 噪聲會(huì)翻轉(zhuǎn)一些像素 % 2. 預(yù)處理去噪 BW_clean bwareaopen(BW_noisy, 20); % 移除面積小于20像素的噪聲塊 % 3. 連通分量分析使用默認(rèn)8連通 CC bwconncomp(BW_clean); fprintf(發(fā)現(xiàn) %d 個(gè)潛在細(xì)胞/物體。\n, CC.NumObjects); % 4. 提取屬性 stats regionprops(CC, Area, Centroid, BoundingBox); % 5. 基于面積過(guò)濾非細(xì)胞物體例如面積過(guò)大或過(guò)小的 areas [stats.Area]; validIdx find(areas 150 areas 2500); % 假設(shè)細(xì)胞面積在此范圍 fprintf(經(jīng)過(guò)面積過(guò)濾剩余 %d 個(gè)有效細(xì)胞。\n, length(validIdx)); % 6. 可視化 figure; subplot(2,2,1); imshow(BW); title(原始模擬細(xì)胞); subplot(2,2,2); imshow(BW_noisy); title(添加噪聲后); subplot(2,2,3); imshow(BW_clean); title(去除小噪聲后); subplot(2,2,4); imshow(BW_clean); title(標(biāo)記連通分量); hold on; for i 1:length(validIdx) idx validIdx(i); % 繪制質(zhì)心 plot(stats(idx).Centroid(1), stats(idx).Centroid(2), r*); % 繪制外接矩形 rect stats(idx).BoundingBox; rectangle(Position, rect, EdgeColor, g, LineWidth, 1); end hold off;在這個(gè)案例中我們經(jīng)歷了完整流程生成數(shù)據(jù)、添加噪聲、使用bwareaopen預(yù)處理這是成功的關(guān)鍵一步、調(diào)用bwconncomp進(jìn)行核心分析、利用其輸出CC提取屬性、最后基于業(yè)務(wù)邏輯細(xì)胞面積范圍過(guò)濾結(jié)果。你會(huì)發(fā)現(xiàn)對(duì)bwconncomp算法的理解幫助你預(yù)判了噪聲會(huì)產(chǎn)生大量微小連通分量從而主動(dòng)引入了預(yù)處理步驟也讓你明白regionprops是如何利用PixelIdxList快速計(jì)算面積的。6. 高級(jí)話題與邊界情況探討6.1 多維度圖像處理bwconncomp天然支持多維二值數(shù)組。對(duì)于三維體數(shù)據(jù)如醫(yī)學(xué)影像conn參數(shù)可以是6面鄰接、18邊鄰接或26點(diǎn)鄰接。算法原理不變只是鄰居檢查從二維的4/8個(gè)方向擴(kuò)展到三維的6/18/26個(gè)方向。處理三維數(shù)據(jù)時(shí)內(nèi)存消耗呈立方增長(zhǎng)因此性能優(yōu)化和預(yù)處理顯得更為重要。6.2 處理“中空”物體與邊界如果一個(gè)連通分量?jī)?nèi)部有孔洞例如一個(gè)白色圓環(huán)bwconncomp會(huì)將其識(shí)別為一個(gè)對(duì)象。孔洞本身是背景區(qū)域但被前景包圍。bwconncomp只負(fù)責(zé)標(biāo)記前景像素不區(qū)分前景是實(shí)心還是環(huán)形。如果需要分析孔洞需要結(jié)合bwconncomp和imfill等函數(shù)。例如可以先找到物體然后用imfill(CC.PixelIdxList{i}, ‘holes’)來(lái)填充某個(gè)特定物體的孔洞再計(jì)算填充前后的面積差得到孔洞面積。關(guān)于圖像邊界算法在掃描時(shí)邊界像素的“鄰居”可能不存在這已被算法內(nèi)部妥善處理。但需要注意如果一個(gè)物體的一部分在圖像邊界外即被截?cái)嗔薭wconncomp只會(huì)分析和標(biāo)記圖像內(nèi)部的部分。6.3 并行化與算法變種MATLAB內(nèi)置的bwconncomp實(shí)現(xiàn)已經(jīng)過(guò)高度優(yōu)化通常比你自己編寫(xiě)的兩遍掃描算法要快得多因?yàn)樗赡苁褂昧硕嗑€程、更高效的數(shù)據(jù)結(jié)構(gòu)如并查集管理等價(jià)類(lèi)和底層C/C代碼。對(duì)于追求極致性能或處理超大規(guī)模數(shù)據(jù)的場(chǎng)景學(xué)術(shù)界和工業(yè)界有更多變種算法如并行化兩遍掃描將圖像分塊各塊獨(dú)立進(jìn)行第一遍掃描和臨時(shí)標(biāo)記然后在塊邊界進(jìn)行等價(jià)關(guān)系合并最后進(jìn)行第二遍掃描。這適合GPU或分布式計(jì)算。BFS/DFS算法從種子點(diǎn)出發(fā)廣度優(yōu)先或深度優(yōu)先搜索所有連通像素。這種方法直觀但遞歸實(shí)現(xiàn)可能棧溢出且不適合并行標(biāo)記多個(gè)物體。bwconncomp的兩遍掃描是無(wú)遞歸的更穩(wěn)健。在實(shí)際工作中除非有非常特殊的定制化需求例如需要?jiǎng)討B(tài)更新連通分量否則直接信任并使用MATLAB的bwconncomp是最佳選擇。你的精力應(yīng)該放在更上游的圖像預(yù)處理濾波、閾值分割和更下游的特征分析與解釋上。理解它的算法是為了讓你能做出正確的參數(shù)選擇連通性設(shè)計(jì)有效的預(yù)處理流程并合理解釋其結(jié)果從而讓這個(gè)強(qiáng)大的工具真正為你所用。