Computer Vision

Connected-component Labeling

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về Connected-component Labeling (còn gọi là Blob Extraction). Đây là một ứng dụng của Lý thuyết đồ thị (Graph Theory) dùng để xác định các “blob”-like regions có trong bức ảnh nhị phân.

Chúng ta thường sử dụng Connected-component Labeling trong các tình huống mà Contour Detection được áp dụng. Tuy nhiên, Connected-component Labeling sẽ cung cấp cho chúng ta một bộ lọc chi tiết hơn.

Khi sử dụng Contour Detection chúng ta thường bị giới hạn bởi “hierarchy of the outlines” (một contour nằm bên trong một contour khác là một ví dụ), nhưng đối với Connected-component Labeling chúng ta có thể dễ dàng phân tích các cấu trúc này.

Một khi đã tách được các “blob” từ ảnh nhị phân, chúng ta có thể áp dụng Contour Detection để định lượng chúng. Trong bài viết này chúng ta sẽ áp dụng Connected-component Labeling để trích xuất các ký tự có trong biển số xe.


GIẢI THUẬT CONNECTED-COMPONENT LABELING

Cần chú ý rằng, chúng ta chỉ áp dụng Connected-component Labeling cho binary hoặc thresholded images.

Giải thuật gồm 2 phần (2 passes), phần 1 (first pass) – gán nhãn, phần 2 (second pass) – tổng hợp.

FIRST PASS

Ở phần này chúng ta sẽ lần lượt kiểm tra từng pixel của Binary Image và Neighbors của nó (Figure 1).

connected_components_connectivity

Figure 1 – Central pixel (red) and its neighbors (gray)

Các bạn sẽ thắc mắc rằng tại sao chỉ có 2 neighbors đối với 4-connectivity cũng như chỉ có 4 neighbors đối với 8-connectivity. Bởi vì chúng ta kiểm tra từng pixel riêng biệt của từng hàng một, do đó sau khi hoàn thành quá trình này thì tất cả các pixel của Binary Image đã được kiểm tra với đủ số lượng neighbors (4 neighbors đối với 4-connectivity, 8 đối với 8-connectivity).

Giải thuật đối với 4-connectivity (tương tự đối với 8-connectivity) như sau:

  1. Khởi tạo biến labelCounter = 0;
  2. Nếu Central Pixel có giá trị 0 (background) thì gán cho label của nó giá trị 0 và chuyển đến bước 4; nếu Central Pixel có giá trị 255 (foreground) thì sang bước 3;
  3. Nếu các Neighbors của Central Pixel đều có giá trị 0 (background) thì tăng giá trị của labelCounter lên 1 và gán cho label của Central Pixel; nếu một trong các Neighbors của Central Pixel đã được gắn label thì gán giá trị nhỏ nhất trong các labels này (tất nhiên các labels này phải lớn hơn 0) cho label của Central Pixel. Chuyển đến bước 4;
  4. Di chuyển đến pixel tiếp theo và quay lại bước 2.

Example:

binaryImage

Figure 2 – Input Binary Image

pass1

Figure 3 – Result of assigning labels

Ở example này, Binary Image được thể hiện ở Figure 2.

Sau khi áp dụng giải thuật đã trình bày ở trên, chúng ta sẽ nhận được một ma trận chứa labels của từng pixel trong Binary Image như ở Figure 3.

SECOND PASS

Ở phần này chúng ta sẽ lọc ma trận label nhận được từ phần 1 để nhận được một array chứa các “unique labels”. Với các “unique labels” này, các pixel tương ứng trên Binary Image sẽ được chuyển thành màu trắng (255).


ÁP DỤNG CONNECTED-COMPONENT LABELING

Để thực hiện thuật toán Connected-component Labeling, OpenCV 3 cung cấp function cv2.connectedComponents().

Function:

retval, labeledImage = cv2.connectedComponents(image, connectivity, ltype)

Trong đó:

  • image – bức ảnh input ở grayscale;
  • connectivity – số lượng neighbor xung quanh mỗi pixel, có thể là 4 hoặc 8;
  • ltype – kiểu dữ liệu của bức ảnh đã được gắn nhãn, gồm cv2.CV_16U (unsigned 16-bit integer) và cv2.CV_32S (signed 32-bit integer);
  • retval – số lượng label được gắn, tương ứng với số lượng “blob” được phát hiện;
  • labeledImage – bức ảnh đã được gắn nhãn, với mỗi pixel được gắn một nhãn có giá trị trong đoạn [0, retval – 1].

Mục tiêu của chúng ta là trích xuất các ký tự có trên biển số xe và loại bỏ các phần không cần thiết.
Input:
carplate2
Code:

import numpy as np
import cv2
import argparse

ap = argparse.ArgumentParser()
ap.add_argument("-i", "--image")
args = vars(ap.parse_args())

plate = cv2.imread(args["image"])

V = cv2.split(cv2.cvtColor(plate, cv2.COLOR_BGR2HSV))[2]

thresh = cv2.adaptiveThreshold(V, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY_INV, 29, 15)

cv2.imshow("Gray", V)
cv2.imshow("Thresh", thresh)

retval, labels = cv2.connectedComponents(thresh, connectivity=8, ltype=cv2.CV_16U)
mask = np.zeros(thresh.shape, dtype="uint8")

print("[INFO] No. labels: {}\tFound {} blobs".format(retval, len(np.unique(labels))))

for (i, label) in enumerate(np.unique(labels)):
    if label == 0:
        continue

    labelMask = np.zeros(thresh.shape, dtype="uint8")
    labelMask[labels == label] = 255
    numPixels = cv2.countNonZero(labelMask)

    if numPixels > 1000 and numPixels < 5000:
        mask = cv2.add(mask, labelMask)

# show the large components in the image
cv2.imshow("Large Blobs", mask)
cv2.waitKey(0)

Giải thích
– Ở dòng 13, chúng ta tách lấy phần ảnh nhị phân từ bức ảnh gốc;
– Ở dong 14-16, chúng ta áp dụng Adaptive Threshold để nhị phân hóa bức ảnh. Các bạn có thể sử dụng hoặc threshold_local() function hoặc cv2.adaptiveThreshold() function, kết quả là tương đương;
– Ở dòng 21, chúng ta áp dụng giải thuật Connected-component Labeling để tính toán label cho từng pixel của bức ảnh nhị phân với function measure.label();
– Ở dòng 25-34, chúng ta xem xét từng giá trị label và set các pixel tương ứng thành 255. Sử dụng function cv2.countNonZero() để đếm số lượng các pixel này. Vùng label nào có số lượng pixel thỏa mãn điều kiện ở dòng 33 thì sẽ được tính là một “blob”.

Output:
output

[INFO] No. labels:119    Found 119 blobs

Như kết quả nhận được chúng ta thấy rằng các ký tự có trên biển số xe đã được trích xuất, các phần không liên quan đến nội dung biển số xe đã được loại bỏ.


SUMMARY

Qua bài viết này chúng ta đã tìm hiểu về thuật toán Connected-component Labeling (Blob Extraction) và cách áp dụng nó vào việc trích xuất các ký tự của biển số xe. Cảm ơn các bạn đã theo dõi bài viết.

Thân ái và quyết thắng.

Reference:
[1] Wikipedia: Graph Theory.
[2] Wikipedia: Connected-component labeling.
[3] Connected Component Labeling Algorithm.
[4] Wikipedia: Union–find data structure.

One thought on “Connected-component Labeling

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s