{jcomments on} 

Author: Trần Trung Thái

Published date: 11/07/2022

1. Giới thiệu

Hough Transform (HT) là một thuật toán được sử dụng nhiều trong việc xác định đường thẳng trong lĩnh vực thị giác máy tính (Computer Vision). HT sử dụng phổ biến ngày nay được phát triển bởi Richard Duda và Peter Hart vào năm 1972 và đã trở thành một trong những thuật toán phổ biến trong việc xác định đường thẳng. Bài viết sau đây sẽ giới thiệu về cơ chế hoạt động của HT.

2. Hough Transform (HT)

2.1. Không gian Hough (Hough space)

Như đã biết, một đường thẳng có thể được biểu diễn trong một trong hai hệ tọa độ:

1. Hệ tọa độ Descartes, đường thẳng được biểu diễn bởi phương trình: \(y=ax+b \text{ } (1)\), với \(a, b\) là tham số.
2. Hệ tọa độ cực, đường thẳng được biểu diễn bởi phương trình: \(r = x\cos\theta+y\sin\theta \text{ } (2)\), với \(\theta\) là góc tạo bởi trục \(Oy\) trong hệ tọa độ Decartes.

Hình 2.1. Một đường thẳng (màu đỏ) trong hệ tọa độ Descartes, khi chuyển qua hệ tọa độ cực, \(r\) là khoảng cách từ gốc tọa độ đến đường thẳng và \(\theta\) là góc tạo bởi đường thẳng và trục \(Oy\) [2].

Khi áp dụng HT, ta sẽ chuyển từ hệ hệ tọa độ hình ảnh về hệ tọa độ tham số, khi đó, mỗi đường thẳng sẽ được biểu diễn bằng một điểm tượng trưng cho tham số của nó: \((a,b)\) đối với hệ tọa độ Descartes và \((r, \theta)\) đối với hệ tọa độ cực.

Tuy nhiên, với hệ tọa độ Descartes, khi đường thẳng có xu hướng song song với trục \(Oy\), tham số \(a\) sẽ có xu hướng tiến về \(-\infty\) hoặc \(\infty\); hoặc khi đường thẳng có xu hướng song song với trục \(Ox\), tham số \(a\) sẽ có xu hướng tiến về \(0\). Do đó, ở đây ta sẽ sử dụng hai tham số trong hệ tọa độ cực để biểu diễn một đường thẳng trong không gian Hough.

Hình 2.2. Một đường thẳng khi biểu diễn trong không gian Hough sẽ trở thành một điểm duy nhất [1].

Đến đây, ta có thể đưa ra một số nhận xét về việc ánh xạ trong không gian ảnh và không gian Hough như sau:

• Một đường thẳng trong không gian ảnh sẽ được biểu diễn bằng một điểm trong không gian Hough (Hình 2.2) và ngược lại.
• Một điểm trong không gian ảnh sẽ được biểu diễn bằng một được hình \(\sin\) trong không gian Hough (Hình 2.3). Vì, ta có thể thấy rằng, một điểm trong không gian ảnh sẽ có vô số các đường thẳng đi qua nó, khoảng cách \(r\) của mỗi đường thẳng sẽ không vượt quá được khoảng cách từ gốc tọa độ đến điểm đó, hơn nữa, dựa vào công thức \((2)\), với mỗi giá trị của \(r\) sẽ tìm được vô số các \(\theta\) tương ứng với khoảng cách tuần hoàn. Do đó, tạo thành một đường hình \(\sin\).

Hình 2.3. Một điểm trong không gian ảnh khi biểu diễn trong không gian Hough sẽ trở thành một đường hình \(\sin\) [1].

• Các điểm trên một đường thẳng sẽ được biểu diễn bằng các đường hình \(\sin\) giao nhau tại một điểm duy nhất (xét trong một đoạn \(0 - \pi\)) (Hình 2.4).

Hình 2.4. Các điểm trên một đường thẳng trong không gian ảnh sẽ được biểu diễn bằng các đường hình \(\sin\) giao nhau tại một điểm duy nhất trong không gian Hough [1].

• Khi lượng hóa các điểm trên một đường thẳng, mỗi đường thẳng khác nhau trong không gian Hough sẽ tạo thành một “điểm sáng” tượng trưng cho điểm giao nhau của các đường hình \(\sin\) (Hình 2.5). Do đó, khi xác định một đường thẳng, ta chỉ cần xác định được “điểm sáng” tương ứng trong không gian Hough.

Hình 2.5. Mỗi đường thẳng trong không gian Hough sẽ tạo thành một điểm sáng tượng trưng cho điểm giao nhau của các đường hình \(\sin\) [3].

2.2. Thuật toán

2.2.1. Xác định điểm cạnh (edge points)

HT không phải là một kỹ thuật để từ một hình ảnh có thể xác định được luôn các đường thẳng đi qua nó. Thay vào đó, ta phải cung cấp một tập các điểm mà ta cho rằng đó là những điểm nằm trên một đường thẳng trong không gian ảnh. Sau đó, HT sẽ được dùng để kiểm tra các đường thẳng đi qua điểm đó và xác định được đường thẳng nào đi qua một lượng điểm đáng kể đó sẽ là một cạnh trong không gian ảnh. Vì thế, trước khi áp dụng HT, cần áp dụng thuật toán xác định cạnh (edge detector) trước để tìm ra tập các điểm cạnh. Canny edge detector là một trong những thuật toán hay được sử dụng.

2.2.2. Thuật toán chính

Khi đã xác định được tập các điểm cạnh. Ta sẽ thực hiện việc bình chọn các đường thẳng đi qua mỗi điểm trong không gian Hough. Như đã đề cập ở phần 2.1, có vô số các đường thẳng đi qua một điểm trong không gian ảnh tạo thành một đường hình \(\sin\) trong không gian Hough, do đó, ta chỉ xét một số lượng cố định các đường thẳng \((r_i,\theta_i)\) (trong không gian Hough) đi qua một điểm. Đầu tiên, ta cần thu nhỏ không gian Hough về một chiều rộng và chiều cao cố định. Nếu hình ảnh đang xét có kích thước \(H \times W\) (không xét chiều sâu: các kênh R, G, B), nếu đặt gốc tọa độ ở một góc của hình, khi đó, giá trị \(r_i\) sẽ không vượt quá \(\sqrt{H^2 + W^2}\), nếu lấy một đơn vị trên trục \(r\) là \(\Delta r\), khi đó độ rộng của trục \(r\) là \(M =\lceil\sqrt{H^2 + W^2}/\Delta r \rceil\), do đó \(0 \le r_i \le M\). Thường giá trị của \(\Delta r\) được sử dụng là \(1\). Bên cạnh đó, xét \(\theta\) có giá trị từ \(0-\pi\), nếu lấy một đơn vị trên trục \(\theta\) là \(\Delta\theta\), khi đó độ rộng trục \(\theta\) là \(N = \lceil \pi/\Delta\theta \rceil\), do đó \(0 \le \theta_i \le N\). Giá trị \(\pi/\Delta\theta\) cũng là số đường thẳng đi qua mỗi điểm mà ta cần xét.

Hình 2.6. Ma trận tích lũy (accumulator). Mỗi ô tượng trưng cho một đường thẳng trong không gian ảnh, Nhiệm vụ của HT chính là cập nhật số điểm mà đường thẳng đó đi qua, nếu số lượng đó vượt qua một ngưỡng (threshold) xác định từ trước, đó sẽ là đường thẳng cần tìm trong không gian ảnh [1].

Khi đã xác định được \(\Delta\theta\) và \(\Delta r\), từ đó xác định được \(M\) và \(N\), ta khởi tạo một ma trận \(A\) với kích thước \((M + 1) \times (N + 1)\) với các giá trị ban đầu là \(0\) để chứa lượt bình chọn của các đường thẳng được xét, ma trận này còn được gọi là ma trận tích lũy (accumulator). Giá trị của ma trận tại hàng \(i\), cột \(j\) chính là số điểm mà đường thẳng \((i \times \Delta r,j \times \Delta\theta)\) đi qua trong tập các điểm cạnh đầu vào. Nhiệm vụ của HT chính là cập nhật giá trị của ô \((i, j)\) (với \(0 \le i \le M\) và \(0 \le j \le N\)) của ma trận nếu đường thẳng \((i \times \Delta r,j \times \Delta\theta)\) đi qua một điểm cạnh. Khi đã cập nhật xong ma trận, những ô nào có giá trị lớn hơn một ngưỡng giá trị (threshold) mà ta xác định từ trước sẽ là đường thẳng trong không gian ảnh.

Cụ thể, thuật toán HT bao gồm các bước:

• Bước 1: Xác định hai giá trị \(\Delta r\) và \(\Delta \theta\), từ đó tìm được \(M =\lceil\sqrt{H^2 + W^2}/\Delta r \rceil\) và \(N = \lceil \pi/\Delta\theta \rceil\). Đồng thời, xác định giá trị ngưỡng \(T\).
• Bước 2: Khởi tạo ma trận tích lũy \(A\) với kích thước \((M + 1) \times (N + 1)\) và giá trị khởi đầu của mỗi ô là \(0.\)
• Bước 3: Lần lượt duyệt từng điểm \((x_j, y_j)\) trong tập các điểm cạnh đầu vào (chú ý rằng các giá trị \(i, j\) là số tự nhiên):
  • Bước 3.1: Xét từng giá trị \(0 \le j \le N\), tìm được \(\theta_j = \Delta\theta \times j\).
  • Bước 3.2: Có \(\theta_j\), tìm được \(r_j\) qua công thức: \(r_j=x_j\cos\theta_j+y_j\sin\theta_j\). Từ đó tìm được giá trị \(i = \lfloor r_j/\Delta r \rfloor\) (lấy cận dưới hay cận trên tùy vào cách hiện thực của mỗi người, ở đây tôi sẽ lấy cận dưới, tương tự như việc lấy phần nguyên).
  • Bước 3.3: Cập nhật giá trị \(A_{ij}\) trong ma trận tích lũy bằng cách cộng lên \(1\).
• Bước 4: Sau khi đã duyệt hết tất cả các điểm trong tập điểm cạnh đầu vào, so sánh từng giá trị với giá trị ngưỡng \(T\). Với những ô có \(A_{ij} \ge T\), điểm \((i \times \Delta r, j \times \Delta\theta)\) trong không gian Hough chính là tượng trưng cho một đường thẳng trong không gian ảnh.

Hình 2.7. Quá trình thực hiện HT [3].

Ưu điểm:

• HT là một thuật toán khá đơn giản nhưng lại khá hiệu quả trong việc xác định đường thẳng.
• Ít bị ảnh hưởng bởi nhiễu: với những đường thẳng bị ảnh hưởng bởi nhiễu như: đường thẳng bị đứt đoạn (có thể do chất lượng chụp ảnh) hay gồm nhiều điểm nhiễu khi xác định cạnh, HT vẫn xác định được các đường thẳng nếu chọn được giá trị ngưỡng phù hợp (Hình 2.8). Vì HT xét cố định một số đường thẳng đi qua một điểm, nên việc thiếu hụt điểm nằm trên một đường thẳng không ảnh hưởng nhiều đến kết quả bình chọn nếu số lượng điểm trên đường thẳng đó trong tập điểm cạnh đầu vào vẫn là đáng kể.

Hình 2.8. HT ít bị ảnh hưởng bởi nhiễu [5].

Nhược điểm:

• HT phụ thuộc nhiều vào tập các điểm cạnh đầu vào, nếu như chứa nhiều nhiễu và số lượng lớn (như hình bên phải phía trên Hình 2.8), HT có thể sẽ chạy khá chậm (vì thời gian chạy của thuật toán là \(O(N^3)\)) và nếu không chọn được ngưỡng giá trị phù hợp có thể dẫn đến xác định sai.
• HT không thể xác định được điểm đầu cuối của một đoạn thẳng, nó chỉ xác định được những đường thằng (chạy đến hết đường biên của không gian ảnh) có trong hình ảnh.

Có nhiều biến thể của HT được phát triển: Probabilistic Hough Transform (PHT) và Randomized Hough Transform (RHT) là 2 biến thể dựa trên xác xuất của HT, Fast Hough Transform (FHT) sử dụng việc ánh xạ khác với HT và tận dụng cấu trục dữ liệu cây để giảm thời gian chạy. Phần tiếp theo đây tôi sẽ giới thiệu về FHT.

3. Fast Hough Transform (FHT)

Vì HT tốn khá nhiều thời gian để thực thi (\(O(N^3)\)), do đó, Fast Hough Transform (FHT) được phát triển để khắc phục nhược điểm này. Ý tưởng của FHT cũng giống như HT là việc ánh xạ một đường thẳng từ không gian ảnh sang một không gian tham số. Tuy nhiên, việc ánh xạ trong FHT lại khác so với HT. Một điểm trong không gian ảnh \((x, y)\) của FHT sẽ được ánh xạ thành một đường thẳng trong không gian Hough:

\[ c = -m \times x+y \text{ } (3) \]

với \(x, y\) như là tham số trong phương trình. Một điểm trong không gian Hough là giao điểm của vô số các đường thẳng, do đó, khi ánh xạ lại không gian ảnh sẽ là một đường thẳng.

Bên cạnh đó FHT cũng tận dụng cấu trúc dữ liệu cây để lưu trữ các chỉ số (index) của các điểm ảnh. Ý tưởng của FHT là chia không gian Hough thành các ô vuông rồi duyệt dần các ô vuông đó để bình chọn. Nếu một ô vuông có lượt bình chọn trên một ngưỡng nhất định, chia ô vuông đó thành 4 rồi duyệt tiếp đến các ô vuông nhỏ hơn cho đến khi ô vuông giảm xuống độ lớn đơn vị.

3.1. Tiêu chí kiểm tra

FHT kiểm tra xem một đường thẳng trong không gian Hough có giao với ô vuông đã chia ra hay không để tiến hành bình chọn cho hình vuông đó. Tuy nhiên, để xác định được một đường thăng có giao với hình vuông lại tốn khá nhiều tính toán và phức tạp. Do đó, thay vì kiểm tra hình vuông, ta sẽ kiểm tra xem đường thẳng đó có đi qua hình tròn bao quanh hình vuông đó (Hình 3.1). Khi đó, chỉ cần so sánh khoảng cách của tâm hình tròn đến đường thẳng và bán kính của hình tròn. Mặc dù có thể sẽ có những đường thẳng không đúng, tuy nhiên, cách kiểm tra này đơn giản và nhanh hơn so với cách kiểm tra ban đầu. Bên cạnh đó, phần diện tích nằm ngoài hình vuông là không lớn và không ảnh nhiều đến kết quả của FHT.

Hình 3.1. Thay vì kiểm tra đường thẳng giao với hình vuông, ta sẽ kiểm tra đường thẳng có đi qua hình tròn bao quanh hình vuông đó. Như trên hình, đường thẳng A và C được xác định đúng, nhưng đường B lại có sự khác biệt khi áp dụng tiêu chí so sánh này [4].

3.2. Thuật toán FHT

Vì ta xét từng hình vuông và chia nhỏ nó, do đó, cần đảm bảo không gian Hough là một hình vuông với cạnh có độ dài \(2^n\). Tương tự với FT, FHT cũng cần các điểm cạnh là đầu vào. Cụ thể, thuật toán FHT gồm các bước:

• Bước 1: Ánh xạ các điểm ảnh sang các đường thẳng trong không gian Hough. Xác định ngưỡng giá trị \(T\).
• Bước 2: Bắt đầu từ ô vuông lớn nhất là toàn bộ không gian Hough:
  • Bước 2.1: Chia ô vuông thành 4 ô vuông kích thước bằng nhau.
  • Bước 2.2: Kiểm tra số đường thẳng đi qua từng ô vuông. Với mỗi đường thẳng đi qua, lượt bình chọn cho ô vuông đó sẽ tăng lên \(1\).
  • Bước 2.3: Kiểm tra lượt bình chọn của từng ô. Với những ô vuông có lượt bình chọn lớn hơn \(T\), tiếp tục lặp lại bước 2.1 đến khi hết tất cả các ô vuông và độ lớn của ô vuông là đơn vị.
• Bước 3: Khi đã xác định được các ô đơn vị có lượt bình chọn lớn hơn hoặc bằng \(T\), thực hiện ánh xạ ngược lại không gian ảnh.

Hình 3.2. Thực hiện FHT với 8 đường thẳng đã được ánh xạ sang không gian Hough [4].

Ví dụ về thực hiện FHT được minh họa ở Hình 3.2 với 8 đường thẳng đã được ánh xạ sang không gian Hough. Đầu tiên, xét ô vuông lớn nhất, chia nhỏ ô vuông thành 4 ô vuông nhỏ hơn, đánh dấu là \((0,0),(0,1),(1,0),(1,1)\) (như số nhị phân). Sau đó kiểm tra số đường thẳng đi qua các ô vuông đó, nếu chọn \(T=8\), khi đó chỉ có ô vuông \((1,1)\) thỏa mãn. Ta xét tiếp ô vuông đó, chia nhỏ thành 4 ô vuông nhỏ hơn, đánh dấu tiếp các ô nhỏ \((10, 10), (10, 11), (11,10), (11,11)\) (giữ hai chữ số đầu, lần lượt thêm các cặp \((0,0),(0,1),(1,0),(1,1)\) vào sau mỗi chữ số). Kiểm tra tiếp số đường thẳng đi qua từng ô nhỏ hơn đó, tiếp tục chỉ có ô \((11,11)\) thỏa mãn. Tiếp tục chia nhỏ và kiểm tra, ta xác định được ô vuông thỏa ngưỡng giá trị \((110,110)\) như trên Hình 3.2. Nếu chọn độ lớn của một đơn vị là \(\frac{1}{8}\) độ dài của ô vuông lớn nhất, độ lớn của ô vuông đã giảm xuống đơn vị, bên cạnh đó, không còn ô vuông lớn hơn nào thỏa mãn để xét tiếp, do đó, thuật toán dừng tại đây và tiếp theo là ánh xạ ô vuông ngược lại không gian ảnh.

Theo cơ chế chia nhỏ như đã đề cập, cấu trúc dữ liệu cây rất phù hợp cho việc lưu trữ thông tin của từng ô. Mỗi nút trên cây tượng trưng cho một ô và các nhánh con của nó chính là các ô được chia nhỏ từ ô vuông đó. Bên cạnh đó, việc duyệt qua các ô cũng được giải quyết bằng các thuật toán duyệt theo chiều rộng (breadth first search - BFS) hoặc duyệt theo chiều sâu (depth first search - DFS). Nếu sử dụng quá trình bình chọn thông thường như trong HT, với dữ liệu như Hình 3.2 cần duyệt hết \(8 \times 8=64\) ô, trong khi FHT chỉ cần duyệt \(4+4+4+1=13\) ô, giúp rút ngắn thời gian đáng kể. Thay vì \(O(N^3)\), FHT giảm thời gian chạy xuống còn \(O(N^2\log N)\) và còn tùy thuộc vào ngưỡng giá trị \(T\) được lựa chọn.

4. Kết luận

Hough Transform là một thuật toán đơn giản, phổ biến và khá hiệu quả trong việc phát hiện đường thẳng cổ điển. Tuy nhiên, nó lại phụ thuộc nhiều vào các điểm cạnh đầu vào, do đó không có tính ổn định nếu như các điểm cạnh đầu vào có nhiều nhiễu. Do đó HT ít được sử dụng tới ngày nay. Tuy nhiên với sự phát triển của Deep Learning và mạng tích chập, việc tích hợp HT vào các bài toán nhận diện đường thẳng bằng Deep Learning cũng có thể được xem xét và khai thác.

Tham khảo

[1] Viet-Anh Nguyen, October 24, 2019, Phát hiện đường thẳng với Hough Transform - OpenCV, ******** https://aicurious.io/posts/2019-10-24-hough-transform-phat-hien-duong-thang/

[2] OpenCV, Hough Line Transform, https://docs.opencv.org/3.4/d9/db0/tutorial_hough_lines.html

[3] OpenCV, Hough Line Transform, https://docs.opencv.org/3.4/d6/d10/tutorial_py_houghlines.html

[4] Hungwen Li, Mark A. Lavin, Ronald J. Le Master, Fast Hough Transform: A Hierarchical Approach, 1986, https://www.sciencedirect.com/science/article/pii/0734189X86900733

[5] G. Vozikisa, J.Jansa, Advantages and Disadvantages of the Hough Transformation in the Frame of Automated Building Extraction, 2008/01/01, https://www.researchgate.net/publication/228854417_Advantages_and_Disadvantages_of_the_Hough_Transformation_in_the_Frame_of_Automated_Building_Extraction

[6] N. Guil, J. Villalba and E. L. Zapata, "A fast Hough transform for segment detection," in IEEE Transactions on Image Processing, vol. 4, no. 11, pp. 1541-1548, Nov. 1995, doi: 10.1109/83.469935.