【數(shù)字圖像處理】LeetCode與圖像處理（連通域的計(jì)算）

基本概念

在數(shù)字圖像處理中，有個(gè)連通域的概念

連通區(qū)域（Connected Component）一般是指圖像中具有相同像素值且位置相鄰的前景像素點(diǎn)組成的圖像區(qū)域（Region，Blob）。

在圖像中，最小的單位是像素，每個(gè)像素周圍有 8 個(gè)鄰接像素，常見(jiàn)的鄰接關(guān)系有 2 種：4 鄰接與 8 鄰接。4 鄰接一共 4 個(gè)點(diǎn)，即上下左右、8 鄰接的點(diǎn)一共有 8 個(gè)，包括了對(duì)角線位置的點(diǎn)，如下圖所示

二值圖（圖上的值只有 0 和 1，或者 0 和 255）是非常常用的一種圖像，我們可以用它來(lái)尋找目標(biāo)的輪廓，形狀識(shí)別等操作，同時(shí)，我們也利用二值圖來(lái)尋找一個(gè)圖像的連通域。如下圖，就是一個(gè)很直觀的連通域圖，圖中總共有 6 個(gè)連通域。

尋找連通域的方法

OpenCV 庫(kù)

在 OpenCV 中，提供了一個(gè)函數(shù) cv2.connectedComponentsWithStats 可以幫助我們計(jì)算連通域的一些信息，其接口說(shuō)明如下：

connectedComponentsWithStats(image[,?labels[,?stats[,?centroids[,?connectivity[,?ltype]]]]])?->?retval,?labels,?stats,?centroids

• image：輸入的圖像，必須是單通道 8-bit 的圖像
• labels：一張和輸入圖像大小一樣的掩膜（mask），對(duì)于相同的連通域，使用同一個(gè)標(biāo)號(hào)進(jìn)行標(biāo)記，背景標(biāo)記為 0
• stats：記錄了連通域的一些信息
• centroids 連通域的質(zhì)心
• connectivity：4 或者 8， 使用 4 連通域還是 8 連通域
• ltype：輸入 labels 的數(shù)據(jù)類型，CV_32S 或者 CV_16U

下圖是一個(gè)圖像得到的連通域掩膜，即上面提到的 labels 輸出

為了方便起見(jiàn)，我們構(gòu)建一張圖來(lái)測(cè)試我們的程序

import?cv2
import?numpy?as?np

#?創(chuàng)建一個(gè)黑色的畫布
img?=?np.zeros((516,?512),?np.uint8)
#?繪制長(zhǎng)方形，起始和終點(diǎn)坐標(biāo)，顏色，厚度
img?=?cv2.rectangle(img,?(10,?10),?(49,?49),?(255),?-1)
#?繪制圓形，給定圓心，半徑，最后?-1?為圖形填充
img?=?cv2.circle(img,?(180,?88),?50,?(255),?-1)
#?繪制橢圓，橢圓心，長(zhǎng)軸，短軸，角度，起始結(jié)束角，填充
img?=?cv2.ellipse(img,?(256,?256),?(100,?50),?0,?0,?360,?255,?-1)

retval,?labels_cv,?stats,?centroids?=?cv2.connectedComponentsWithStats(img,?ltype=cv2.CV_32S)

#?cv2.imshow("labels",?labels)
cv2.imshow("img",?img)
k?=?cv2.waitKey(0)?&?0xFF
if?k?==?27:
????cv2.destroyAllWindows()

在該圖中，我們繪制了 3 個(gè)圖像，正方形、圓形、橢圓形，其中正方形的面積是 40×40=1600，圓形的質(zhì)心是 (188, 88)，請(qǐng)記住這些值，下面會(huì)對(duì)其進(jìn)行說(shuō)明。

我們重點(diǎn)對(duì)輸出的 stats 和 centroids 進(jìn)行觀察

• stats

stats 是一個(gè) (label, 5) 的矩陣，label 是連通域的個(gè)數(shù)（包括背景） [left, top, width, height, area] 分別是連通域左上角的坐標(biāo)，連通域的寬、高、以及面積

這個(gè)圖可以幫助理解

可以看到正方形的面積和我們?cè)O(shè)想的一樣

• centroids

centroids 是連通域的質(zhì)心，圓形的質(zhì)心就是圓心，很好理解

skimage 庫(kù)

skimage 庫(kù)中也有一個(gè)與 OpenCV 版本一樣的函數(shù) skimag.measure.label ，其接口如下

labels,?num?=?measure.label(input,?neighbors=None,?background=None,?return_num=False,?connectivity=None)

• input：輸入的圖像

• neighbors：1 對(duì)應(yīng)的是 4 鄰接，2 對(duì)應(yīng)的是 8 鄰接

  

• return_num：是否返回連通域的數(shù)量，否的話，該函數(shù)只有一個(gè)輸出 ?labels

• labels：同 OpenCV 的輸出，但是可能索引值的順序會(huì)不一樣

• num：連通域的數(shù)量，不包括背景，與 OpenCV 的區(qū)別

import?cv2
import?numpy?as?np
from?skimage?import?measure


#?創(chuàng)建一個(gè)黑色的畫布
img?=?np.zeros((516,?512),?np.uint8)
#?繪制長(zhǎng)方形，起始和終點(diǎn)坐標(biāo)，顏色，厚度
img?=?cv2.rectangle(img,?(10,?10),?(49,?49),?(255),?-1)
#?繪制圓形，給定圓心，半徑，最后?-1?為圖形填充
img?=?cv2.circle(img,?(180,?88),?50,?(255),?-1)
#?繪制橢圓，橢圓心，長(zhǎng)軸，短軸，角度，起始結(jié)束角，填充
img?=?cv2.ellipse(img,?(256,?256),?(100,?50),?0,?0,?360,?255,?-1)

labels,?num?=?measure.label(img,?return_num=True)?#?num?=3?不包括背景

#?cv2.imshow("labels",?labels)
cv2.imshow("img",?img)
k?=?cv2.waitKey(0)?&?0xFF
if?k?==?27:
????cv2.destroyAllWindows()

LeetCode 與圖像處理

有讀者會(huì)問(wèn)，LeetCode 怎么會(huì)和圖像處理扯上關(guān)系呢，還真有

LeetCode 上的題目是：200：島嶼數(shù)量 https://leetcode-cn.com/problems/number-of-islands/，具體描述如下，這道題跟我們今天所講的圖像連通域有非常相似之處，個(gè)人猜想，上面兩種庫(kù)的實(shí)現(xiàn)應(yīng)該與下面的實(shí)現(xiàn)思路是類似的。

給你一個(gè)由?'1'（陸地）和?'0'（水）組成的的二維網(wǎng)格，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量。
島嶼總是被水包圍，并且每座島嶼只能由水平方向或豎直方向上相鄰的陸地連接形成。
此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。
示例?1:
輸入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
輸出:?1
示例?2:
輸入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
輸出:?3
解釋:?每座島嶼只能由水平和/或豎直方向上相鄰的陸地連接而成。

這里簡(jiǎn)單說(shuō)一下解題思路，就是利用廣度優(yōu)先搜索，即遍歷所有像素，看看該像素上下左右的值是否和該像素一樣（我們假設(shè)是二值圖像，并且是 4 連通的），若是的話，將其壓入隊(duì)列中，同時(shí)將其標(biāo)記為已訪問(wèn)。

我們使用和上面一樣的測(cè)試用例，編寫程序如下

from?collections?import?deque
import?cv2
import?numpy?as?np
from?skimage?import?measure


#?創(chuàng)建一個(gè)黑色的畫布
img?=?np.zeros((516,?512),?np.uint8)
#?繪制長(zhǎng)方形，起始和終點(diǎn)坐標(biāo)，顏色，厚度
img?=?cv2.rectangle(img,?(10,?10),?(49,?49),?(255),?-1)
#?繪制圓形，給定圓心，半徑，最后?-1?為圖形填充
img?=?cv2.circle(img,?(180,?88),?50,?(255),?-1)
#?繪制橢圓，橢圓心，長(zhǎng)軸，短軸，角度，起始結(jié)束角，填充
img?=?cv2.ellipse(img,?(256,?256),?(100,?50),?0,?0,?360,?255,?-1)

class?Solution:
????def?numIslands(self,?grid:?np.array)?->?int:
????????high?=?len(grid)
????????#?特殊處理，當(dāng)矩陣為空
????????if?high?==?0:
????????????return?0
????????width?=?len(grid[0])
????????print(high,?width)
????????queue?=?deque()
????????num?=?0??
????????directions??=?[(-1,?0),?(1,?0),?(0,?1),?(0,?-1)]?#?四個(gè)方向的偏移
????????for?i?in?range(high):
????????????for?j?in?range(width):
????????????????#?島嶼，且沒(méi)有被訪問(wèn)過(guò)，BFS搜索
????????????????if?grid[i,?j]?==?255:??#?為了直觀展示，我們將陸地記為?255，海洋記為?0
????????????????????queue.append((i,?j))?#?把點(diǎn)放進(jìn)隊(duì)列中
????????????????????grid[i,?j]?=?254??#?訪問(wèn)過(guò)的點(diǎn)記為?254
????????????????????while?queue:
????????????????????????x,?y?=?queue.popleft()
????????????????????????#?判斷當(dāng)前點(diǎn)的上下左右是否是陸地且未被訪問(wèn)過(guò)的，是的話入隊(duì)
????????????????????????for?d?in?directions:
????????????????????????????cur_x?=?x?+?d[0]?
????????????????????????????cur_y?=?y?+?d[1]
????????????????????????????if?0?<=?cur_x?and?0<=?cur_y?and?grid[cur_x,?cur_y]?==?255:
????????????????????????????????queue.append((cur_x,?cur_y))
????????????????????????????????grid[cur_x,?cur_y]?=?254??#?訪問(wèn)過(guò)的
????????????????????num?+=?1
????????return?num
????
s?=?Solution()????
s.numIslands(img)??#?結(jié)果為?3