分水嶺演算法-偵測相連區域形狀

官方教學

Image Segmentation with Watershed Algorithm
官方的範例是一群黏在一起的硬幣

分割出黏在一起的長方形

這篇文章是在討論如何分割出一群黏在一起的長方形

給定一個二值圖像，我們可以應用距離變換 (DT) 並從中獲得分水嶺的標記。理想情況下，會有一個現成的函數來查找區域最小值/最大值，但由於它不存在，我們可以對如何設置 DT 閾值做出一個不錯的猜測。基於標記，我們可以使用 Watershed 進行分割，問題就解決了。現在您可以擔心區分矩形組件和非矩形組件了。

OpenCV的distanceTransform是一個圖像處理功能，可以計算圖像中每個像素到最近的零值像素之間的歐幾里德距離。distanceTransform功能可以在圖像分割、形狀檢測、物體識別等應用中使用。

在OpenCV中，distanceTransform有三種不同的實現方式：cv2.DIST_L1、cv2.DIST_L2和cv2.DIST_C。cv2.DIST_L1使用曼哈頓距離，cv2.DIST_L2使用歐幾里德距離，而cv2.DIST_C使用切比雪夫距離。

曼哈頓距離也稱為城市區塊距離或L1距離。它是兩點之間水平和垂直距離的總和。如果p1和p2是兩個二維坐標點，則曼哈頓距離可以通過以下公式計算：

d(p1, p2) = |p1.x – p2.x| + |p1.y – p2.y|

歐幾里德距離是兩個點之間的直線距離。如果p1和p2是兩個二維坐標點，則歐幾里德距離可以通過以下公式計算：

d(p1, p2) = sqrt((p1.x – p2.x)^2 + (p1.y – p2.y)^2)

切比雪夫距離是兩個點之間在所有方向上的最大距離。如果p1和p2是兩個二維坐標點，則切比雪夫距離可以通過以下公式計算：

d(p1, p2) = max(|p1.x – p2.x|, |p1.y – p2.y|)

import sys
import cv2
import numpy
import random
from scipy.ndimage import label

def segment_on_dt(img):
    dt = cv2.distanceTransform(img, 2, 3) # L2 norm, 3x3 mask
    dt = ((dt - dt.min()) / (dt.max() - dt.min()) * 255).astype(numpy.uint8)
    dt = cv2.threshold(dt, 100, 255, cv2.THRESH_BINARY)[1]
    lbl, ncc = label(dt)

    lbl[img == 0] = lbl.max() + 1
    lbl = lbl.astype(numpy.int32)
    cv2.watershed(cv2.cvtColor(img, cv2.COLOR_GRAY2BGR), lbl)
    lbl[lbl == -1] = 0
    return lbl


img = cv2.cvtColor(cv2.imread(sys.argv[1]), cv2.COLOR_BGR2GRAY)
img = cv2.threshold(img, 0, 255, cv2.THRESH_OTSU)[1]
img = 255 - img # White: objects; Black: background

ws_result = segment_on_dt(img)
# Colorize
height, width = ws_result.shape
ws_color = numpy.zeros((height, width, 3), dtype=numpy.uint8)
lbl, ncc = label(ws_result)
for l in xrange(1, ncc + 1):
    a, b = numpy.nonzero(lbl == l)
    if img[a[0], b[0]] == 0: # Do not color background.
        continue
    rgb = [random.randint(0, 255) for _ in xrange(3)]
    ws_color[lbl == l] = tuple(rgb)

cv2.imwrite(sys.argv[2], ws_color)

從上圖中，您可以考慮在每個組件中擬合橢圓以確定矩形。然後您可以使用一些度量來定義組件是否為矩形。這種方法更有可能適用於完全可見的矩形，但對於部分可見的矩形可能會產生不良結果。下圖顯示了這種方法的結果，如果擬合橢圓的矩形在組件面積的 10% 以內，則組件是矩形。

# Fit ellipse to determine the rectangles.
wsbin = numpy.zeros((height, width), dtype=numpy.uint8)
wsbin[cv2.cvtColor(ws_color, cv2.COLOR_BGR2GRAY) != 0] = 255

ws_bincolor = cv2.cvtColor(255 – wsbin, cv2.COLOR_GRAY2BGR)
lbl, ncc = label(wsbin)
for l in xrange(1, ncc + 1):
yx = numpy.dstack(numpy.nonzero(lbl == l)).astype(numpy.int64)
xy = numpy.roll(numpy.swapaxes(yx, 0, 1), 1, 2)
if len(xy) < 100: # Too small. continue ellipse = cv2.fitEllipse(xy) center, axes, angle = ellipse rect_area = axes[0] * axes[1] if 0.9 < rect_area / float(len(xy)) < 1.1: rect = numpy.round(numpy.float64( cv2.cv.BoxPoints(ellipse))).astype(numpy.int64) color = [random.randint(60, 255) for _ in xrange(3)] cv2.drawContours(ws_bincolor, [rect], 0, color, 2) cv2.imwrite(sys.argv[3], ws_bincolor)[/code] 更多的資訊請參考: Advanced square detection (with connected region)

Claire's Blog