Computer Vision

Contour approximation

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về Contour Approximation. Đây là một thuật toán được áp dụng nhằm giảm số lượng điểm có trong Contour (đơn giản hóa Contour), nó còn có tên gọi khác là thuật toán Ramer-Douglas-Peucker [1].


CONTOUR APPROXIMATION ALGORITHM

Input của thuật toán là một Contour và Distance Dimension ε > 0. Thuật toán sử dụng đệ quy để phân chia các điểm có trong Contour. Điểm đầu và điểm cuối (tạm gọi là A, B) của Contour sẽ được giữ lại, sau đó tìm điểm có khoảng cách lớn nhất đến đường thẳng AB (tạm gọi là điểm C).

Nếu khoảng cách từ C đến AB  d(C, AB) < ε thì điểm C sẽ bị loại bỏ khỏi Contour, ngược lại nếu d(C, AB) ≥ ε thì điểm C sẽ được giữ lại và Contour sẽ được chia thành 2 đoạn thẳng là AC và CB.

Với từng đoạn AC và CB, thuật toán sẽ được lặp lại tương tự như với AB ban đầu. Figure 1 mô tả rất trực quan về thuật toán này.

Douglas-Peucker_animated

Figure 1 – Thuật toán Ramer-Douglas-Peucker [1]

Vì OpenCV đã cung cấp function cv2.approxPolyDP() nên chúng ta không cần phải thủ công thực hiện lại thuật toán nữa.

Function:

approxContour = cv2.approxPolyDP(contour, epsilon, closed)

Trong đó:

  • contour – Contour cần được approximation;
  • epsilon – Distance Dimension, là độ chính xác của approximation;
  • closed – nếu closed=True thì approxContour sẽ ở dạng bao đóng, ngược lại thì approxContour sẽ ở dạng hở;
  • approxContour – kết quả trả về Contour mới.

Trong ví dụ đầu tiên, chúng ta sẽ tìm cách phát hiện các hình vuông có trong bức ảnh bằng cách áp dụng Contour Approximation.

Example 1 – Rectangle Detection

import cv2
import numpy as np
import argparse

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

image = cv2.imread(args["image"])
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
gray = cv2.threshold(gray, 230, 255, cv2.THRESH_BINARY_INV)[1]
cnts = cv2.findContours(gray.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)[1]

for c in cnts:
	D = cv2.arcLength(c, True)
	approx = cv2.approxPolyDP(c, 0.01*D, True)

	if len(approx) == 4:
		cv2.drawContours(image, [c], -1, (0,255,0), 2)
		(x,y,w,h) = cv2.boundingRect(approx)
		cv2.putText(image, "Rectangle", (x,y-10), cv2.FONT_HERSHEY_SIMPLEX, 0.75, (255,0,0), 2)

cv2.imshow("Image", image)
cv2.waitKey(0)

Output:
rect

Giải thích:
– Ở dòng 15 và 16, chúng ta tính chu vi D của Contour, sau đó lấy giá trị epsilon bằng 1% của D. Điều này có nghĩa là khoảng cách lớn nhất giữa Contour và xấp xỉ của nó phải nhỏ hơn 1% chu vi của chính nó;
– Ở dòng 18, vì mục đích là tìm ra hình chữ nhật nên chúng ta chỉ cần quan tâm đến các approxContour có số lượng điểm bằng 4, hình tròn và hình tam giác sẽ không thỏa mãn điều kiện này.


EPSILON PARAMETER

Bây giờ chúng ta sẽ tìm hiểu sâu hơn tham số epsilon. Trong toán học, epsilon được dùng để quy định độ chính xác của phép tính gần đúng, điều này cũng tương tự đối với Contour Approximation. Giá trị epsilon càng lớn thì ApproxContour càng lệch nhiều so với Contour ban đầu.

Câu hỏi đặt ra ở đây: giá trị tối ưu của epsilon là bao nhiêu? Làm sao để tính toán được giá trị đó?

Một điều rõ ràng là chúng ta không thể áp dụng một giá trị epsilon cố định cho tất cả các Contours. Do đó chúng ta tính toán giá trị epsilon dựa trên chu vi của từng Contour, bằng cách này chúng ta sẽ có được các giá trị epsilon phù hợp cho từng Contour. Thông thường giá trị epsilon sẽ nằm trong khoảng 1% đến 5% chu vi Contour.

Cùng đến với ví dụ tiếp theo, chúng ta sẽ tìm Contour cho các tờ biên lai siêu thị.

Example 2 – Contour drawing with Contour Approximation
Input:
chek

Code:

import cv2
import numpy as np
import argparse

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

image = cv2.imread(args["image"])
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

gray = cv2.threshold(gray, 125, 255, cv2.THRESH_BINARY)[1]
cv2.imshow("Thres", gray)
cnts = cv2.findContours(gray.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)[1]
c = sorted(cnts,key=cv2.contourArea, reverse=True)[0]

D = cv2.arcLength(c, True)
approx = cv2.approxPolyDP(c, 0.01*D, True)
cv2.drawContours(image, [approx], -1, (0,255,0), 2)

cv2.imshow("Image", image)
cv2.waitKey(0)

Output:

chek

Như các bạn thấy ở bức ảnh binary bên trái, tờ biên lai không phải là một hình chữ nhật bình thường, nó bị méo ở góc trên bên trái, phần viền phải hơi cong và phần viền bên trái cũng bị các ký tự làm biến dạng. Nếu tìm và vẽ Contour như cách bình thường chúng ta sẽ nhận được kết quả như Figure 2. Tuy nhiên, với Contour Approximation thì mọi thứ lại rất ấn tượng phải không nào, Contour được vẽ ra là một hình chữ nhật hoàn hảo.

contour

Figure 2 – Original Contour


SUMMARY

Qua 2 ví dụ đơn giản, chúng ta có thể thấy rằng, Contour Approximation là một công cụ hết sức đơn giản và mạnh mẽ. Nó giúp chúng ta đơn giản hóa Contour cũng như khắc phục khi Contour không được như ý muốn do điều kiện ngoại cảnh.

Chúng ta sẽ gặp lại Contour Approximation trong một bài viết khác về một ứng dụng của nó trong thực tế. Cảm ơn các bạn đã theo dõi bài viết.

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

Reference:
[1] Ramer–Douglas–Peucker algorithm.
[2] OpenCV approxPolyDP() function.

2 thoughts on “Contour approximation

    1. Chào bạn, ở hình 1 mình có mô tả thuật toán và tham số ε. Hiểu một cách đơn giản, Distance Dimension là thước đo để thực hiện approximation, Distance Dimension càng lớn thì approxContour nhận được sẽ càng có ít điểm, tức là càng khác biệt so với Contour ban đầu.
      Thân.

      Like

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