MỤC LỤC
MỤC LỤC 1
DANH MỤC HÌNH VẼ 2
ĐẶT VẤN ĐỀ 3
CHƯƠNG I TỔNG QUAN VỀ THUẬT TOÁN HOUGH 4
1.1 Tổng quan về phương pháp Hough 4
1.2 Các phương pháp Hough 7
1.2.1 Phương pháp biến đổi Hough cơ bản (standard) 7
1.2.2 Phương pháp biến đổi Hough theo xác suất (Probability) 8
1.2.3 Phương pháp biến đổi Hough ngẫu nhiên (Randomized Hough Transform).14
1.3 Đánh giá các phương pháp Hough 16
CHƯƠNG 2 THỰC HIỆN THUẬT TOÁN HOUGH TRÊN NỀN FPGA 18
2.1 Nguyên tắc biến đổi Hough ứng dụng trên nền FPGA 18
2.2 Phương pháp tính toán biến đổi Hough 19
2.2.1 Phương pháp cổ điển 19
2.2.2 Biến đổi Hough tăng cường nhanh 2 (FIHT2) 20
2.2.3 Phương pháp dựa trên góc nghiêng 21
2.2.4 Thuật toán CORDIC 22
2.3 Triển khai FPGA theo cấu trúc CORDIC 25
2.4 Kiến trúc FPGA thời gian thực cho biến đổi Hough sử dụng thuật toán CORDIC
28
2.4.1 Tìm đường thẳng 32
2.4.2 Nguyên mẫu 37
KẾT LUẬN 38
THAM KHẢO 39
1
DANH MỤC HÌNH VẼ
Hình 1.1 Không gian Hough 5
Hình 1.2. Các mặt phẳng trong không gian Hough 6
Hình 2.1 Nguyên tắc biến đổi Hough 18
Hình 2.2 Mối quan hệ định hướng cạnh – góc nghiêng 21

trình bày nhanh nguyên tắc biến đổi Hough và có sự thảo luận có liên quan đến các
phương pháp tính toán chuyển đổi Hough khác nhau. Thuật toán CORDIC được mô tả
một cách ngắn gọn trong phần 2.2.4. Chi tiết về một sô việc thực hiện thuật toán
CORDIC được trình bày để lựa chọn cấu trúc phù hợp với kiến trúc của chúng ta. Phần
2.3 mô tả các thuật toán phát hiện đường thẳng và các kiến trúc được đề xuất trên nền
FPGA. Phần 2.4 trình bày các hệ thống nguyên mẫu. Cuối cùng là các kết quả thu được
được trình bày ở cuối báo cáo này
3
CHƯƠNG I TỔNG QUAN VỀ THUẬT TOÁN HOUGH
1.1 Tổng quan về phương pháp Hough
Transform Hough là một phương pháp nổi tiếng để phát hiện đối tượng tham số.
Đây là tiêu chuẩn thực tế cho việc phát hiện đường thẳng và vòng tròn trong bộ dữ liệu
2-chiều. Đối với 3D, cho đến nay nó được ít sự chú ý. Ngay cả đối với trường hợp 2D
do chi phí cao tính toán đã dẫn đến sự phát triển của rất nhiều biến thể cho Hough
Transform. Trong bài viết này, có sự đánh giá các biến thể khác nhau của Biến đổi
Hough có liên quan đến ứng dụng phát hiện mặt phẳng trong những đám mây điểm 3D
một cách đáng tin cậy.
Ngoài tính toán chi phí, vấn đề chính là cách biểu diễn bộ tích lũy. Các triển khai
thông thường thiên về đối tượng hình học với một số thông số do không đồng đều lấy
mẫu của không gian tham số. Nội dung trình bày một cách tiếp cận để thiết kế bộ tích
lũy tập trung vào việc đạt được cùng kích thước cho mỗi cell và so sánh nó với thiết kế
hiện tại.
Biến đổi Hough (Hough transform) là một phương pháp để phát hiện các đối
tượng tham số, thường được sử dụng cho các đường thẳng và vòng tròn. Tuy nhiên, có
thể tập trung vào việc phát hiện các mặt phẳng trong các đám mây điểm 3D. (Mặc dù
nhiều phương pháp Biến đổi Hough làm việc với đầu vào là điểm ảnh nhưng điều này
không phải luc nào cũng cần thiết).
Trong kịch bản, có một tập hợp các điểm chưa được tổ chức được sử dụng như là
đầu vào và đầu ra bao gồm các tham số mặt phẳng. Mặt phẳng thường được biểu diễn
bởi đã ký hiệu ρ là khoảng cách đến gốc của hệ tọa độ và độ dốc mx và my theo hướng

6
nằm trên mặt phẳng biểu diễn bởi hj và xác suất hj thực sự là chiết xuất từ P càng cao
hơn.
1.2 Các phương pháp Hough
1.2.1 Phương pháp biến đổi Hough cơ bản (standard)
Đối với các ứng dụng thực tế, Duda và Hart (1971) đề xuất sử dụng không gian
Hough với các tham số ρ, φ và θ dùng để biểu thị mức độ của mỗi cell theo hướng theo
trong không gian Hough. Một cấu trúc dữ liệu là cần thiết để lưu trữ tất cả các cell với
tham số tính điểm cho mỗi cell. Trong phần tiếp theo sẽ đề cập cách tăng điểm của một
cell và lượng gia tăng điểm số bằng 1. Cấu trúc dữ liệu này gọi là bộ tích lũy, được mô
tả chi tiết hơn trong phần sau. Đối với mỗi điểm biến đổi Hough sẽ xử lý tăng tất cả
các cell có liên quan đến nó. Quá trình gia tăng này thường được gọi là quá trình bỏ
phiếu, tức là, mỗi điểm bỏ phiếu cho tất cả các bộ tham số (θ, φ, ρ) xác định một mặt
phẳng mà trên đó nó có thể nằm trên, tức là, nếu khoảng cách euclidian từ điểm đang
xem xét đến mặt phẳng đại diện bởi cell nhỏ hơn một ngưỡng. Các cell với các giá trị
cao nhất đại diện cho những mặt phẳng nổi bật nhất, mặt phẳng bao gồm hầu hết các
điểm của đám mây điểm.
Một khi tất cả các điểm đã bình chọn, những mặt phẳng chiến thắng được lựa
chọn. Do sự rời rạc của không gian Hough và nhiễu trong các dữ liệu đầu vào thì nên
tìm kiếm không chỉ một cell với số điểm tối đa mà còn tìm tổng tối đa
trong một khu vực nhỏ của bộ tích lũy. Kiryati sử dụng các tiêu chuẩn thực hành để phát
hiện điểm đỉnh. Trong thủ tục cửa sổ trượt, một cửa sổ 3 chiều nhỏ xác định được thiết
kế để phủ phổ các đỉnh đầy đủ. Mặt phẳng có ưu thế nhất tương ứng với điểm trung tâm
của một khối lập phương trong không gian Hough với tổng các giá trị tích lũy là lớn
nhất. Các bước của thủ tục được nêu trong thuật toán 1.
Gồm hai giai đoạn
GĐ1: Tất cả các điểm P
i
thuộc tập điểm P được chuyển sang không gian Hough. Gồm
các dòng 1 đến 7 trong giải thuật

với số Nρ • Nφ • Nθ của các cell trong mảng accumulator, cải tiến lớn liên quan đến chi
phí tính toán được thực hiện bằng cách giảm số lượng các điểm hơn là bằng cách điều
chỉnh quá trình rời rạc trong không gian Hough. Kiryati đề xuất một phương pháp xác
suất để lựa chọn một tập hợp con từ tập điểm ban đầu. Sự thích nghi của SHT trở thành
biến đổi Hough xác suất (PHT) được trình bày trong thuật toán 2.
Algorithm: Probabilistic Hough Transform (PHT)
1: determine m and T
2: randomly select m points to create Pm ⊂ P
3: for all points in m
i p in point set Pm do
4: for all cells (θ, φ, ρ) in accumulator A do
5: if point pi lies on the plane defined by (θ,
φ, ρ) then
6: increment cell A(θ, φ, ρ)
7: end if
8: end for
9: end for
10: Search for the most prominent cells in the
accumulator, that define the detected planes in P
Các điểm m (m <| P |) được chọn ngẫu nhiên từ các đám mây điểm P. Những
điểm này được biến đổi thành Hough không gian và bỏ phiếu cho các mặt phẳng mà các
điểm có thể nằm trên. Phần chi phối thời gian chạy được tỷ lệ thuận với m • Nφ • Nθ.
Bằng cách giảm m, thời gian chạy là giảm mạnh.
Để có được kết quả tốt tương tự như với phương pháp biến đổi Hough tiêu chuẩn
thì điều quan trọng là đảm bảo tính năng vẫn phát hiện với xác suất cao ngay cả khi chỉ
có một tập hợp các các điểm m được sử dụng. Sự lựa chọn tối ưu của m và ngưỡng T
9
phụ thuộc vào các vấn đề thực tế. Nhiễu cảm biến dẫn đến mặt phẳng xuất hiện dày hơn
so với số mặt phẳng đang có trong thực tế. Sự rời rạc của không gian Hough kết hợp với
các phương pháp tiếp cận cửa sổ trượt chính là cách xử lý cho vấn đề này. Càng có

peaks
8: determine stability order
9: end while
Để đẩy nhanh quá trình, việc cập nhật danh sách chỉ được thực hiện sau khi một
lô hàng nhỏ các điểm đã được bình chọn. Danh sách các đỉnh bị hạn chế về quy mô và
sắp xếp tăng dần theo giá trị của các cell. Khi cập nhật danh sách với một đỉnh, tọa độ
của đỉnh được đưa vào tài khoản. Nếu hai đỉnh nằm trong cùng khu vực không gian của
nhau, đỉnh nào thấp hơn được bỏ qua hoặc loại bỏ khỏi danh sách. Trong giai đoạn đầu
của thuật toán sự thay đổi theo thứ tự các đỉnh núi thường xuyên xảy ra. Khi cập nhật,
cấu trúc của bộ tích lũy trở nên rõ ràng hơn. Nguyên tắc dừng cho các thuật toán được
xác định bởi sự ổn định của các đỉnh chiếm ưu thế nhất.
Một tập Sk của k đỉnh trong danh sách được gọi là ổn định nếu tập này chứa tất
cả các đỉnh lớn nhất trước và sau khi giai đoạn một lần cập nhật. Thứ tự trong tập hợp là
không quan trọng cho sự ổn định. Số lượng danh sách liên tiếp (mk) mà trong đó Sk
được ổn định được gọi là trật tự ổn định của Sk. Các tính ổn định tối đa là yếu tố k của
tập Sk với trật tự ổn định cao nhất. Trong trường hợp có hai bộ có cùng trật tự ổn định
11
thì bộ nào có yếu tố cao hơn được ưu tiên hơn. Trình tự ổn định của bộ Sk có tính ổn
định tối đa được gọi để ổn định là tối đa.
Nguyên tắc dừng khi phát hiện chính xác một mặt phẳng là nếu thứ tự ổn định
của S1 vượt quá một ngưỡng xác định trước. Đối với việc phát hiện k đối tượng, trật tự
ổn định của Sk phải vượt quá một số định trước. Phát hiện một số lượng tùy ý các mặt
phẳng sử dụng một số lần lặp với k cố định có thể dẫn đến thời gian thực hiện bài toán
dài. Vì vậy, một đề nghị cho phép các chương trình chạy cho đến khi trật tự ổn định tối
đa đạt đến một ngưỡng. Sau đó giá trị điếm ổn định tối đa là số lượng các đối tượng
được tìm thấy.
1.2.2.2 Phương pháp biến đổi Hough theo xác suất cải tiến (Progressive
Probabilistic Hough Transform)
Phương pháp biến đổi Hough lũy tiến xác suất (PPHT) tính toán số lần dừng cho
quá trình lựa chọn ngẫu nhiên các điểm phụ thuộc vào số phiếu trong một bộ tích lũy

Pplane
13: remove from P all points that are in Pregion
14: for all point pj that are in Pvoted and Pregion do
15: unvote pj from the accumulator
16: remove pj from Pvoted
17: end for
18: if the area covered by Pregion is larger than a
threshold then
19: add Pregion to the output list
20: end if
21: end if
22: end while

13
1.2.3 Phương pháp biến đổi Hough ngẫu nhiên (Randomized Hough
Transform)
Phương pháp biến đổi Hough ngẫu nhiên (RHT) làm giảm số lượng cell được tác
động bằng cách khai thác thực tế rằng một đường cong với n các thông số được xác
định bởi n điểm. Đối với việc phát hiện các mặt phẳng, ba điểm từ không gian đầu vào
được ánh xạ vào một điểm trong Không gian Hough. điểm này là một trong những điểm
tương ứng với mặt phẳng xác định bởi ba điểm. Trong mỗi bước thủ tục chọn ngẫu
nhiên ba điểm p1, p2 và p3 từ đám mây điểm. Mặt phẳng trải rộng bởi ba điểm được
tính như sau
ρ = n · p1 = ((p3 - p2) × (p1 - p2)) · p1
φ và θ được tính như được giải thích trong phần 2 và ô tương ứng A (θ, φ, ρ)
được tích lũy. Nếu điểm đám mây bao gồm một mặt phẳng với θ, φ, ρ, sau một số lượng
nhất định lần lặp sẽ có một điểm số cao tại A (θ, ρ, φ).
Khi mặt phẳng được biểu diễn bởi một số lượng lớn các điểm, có nhiều khả năng
rằng ba điểm từ mặt phẳng này đượcchọn. ngẫu nhiên. Cuối cùng, các cell tương ứng
với các mặt phẳng thực tế.

Tham số
SHT PHT PPHT APHT RHT
Độ hoàn thành/tính
xác định
+ - - - -
Điều kiện dừng - - + + +
Điều kiện dừng
thích nghi
- - + ++ -
Xóa các mặt phẳng
phát hiện được từ
bộ điểm
- - + - +
Tác động chỉ một
cell trên một lần lặp
- - - - +
Độ dễ khi thực hiện + + + - +
Nhận xét:
Trong SHT, HT hoàn được thực hiện cho tất cả các điểm (gọi là biến đổi Hough
hoàn toàn). Điều này làm cho nó có số lượng phép toán lớn.
Các PPHT, APHT và RHT thì không cần biến đổi Hough hoàn toàn do thêm vào
một hoặc vài quy tắc dừng lại.
16
Trong khi đối với RHT số dừng lại quy tắc là một ngưỡng đơn giản, ví dụ, điểm
còn lại trong đám mây điểm hoặc số lượng các mặt phẳng được phát hiện.
PPHT có một quy tắc dừng lại đó là dựa trên số lượng điểm đã được xử lý. Vì
vậy, thuật toán là ít nhạy cảm với nhiễu trong các dữ liệu.
Quy tắc dừng lại tinh vi nhất là áp dụng trong phương pháp APHT. Ở đây, sự ổn
định của một số cực đại được theo dõi theo thời gian trong quá trình lựa chọn làm cho
thuật toán mạnh mẽ hơn đối với các tác động tiêu cực lựa chọn điểm ngẫu nhiên.

(1)
cos sinx y
ρ θ θ
= +
(2)
Hình 2.1 Nguyên tắc biến đổi Hough
Trong không gian tham số, mỗi đường thẳng được đại diện bởi 1 điểm
( )
,
k k k
L
ρ θ
.
Theo phương trình (2), mỗi điểm sẽ thuộc 1 đường thẳng, nó tương ứng với đồ thị hình
sin trong không gian tham số. Tất cả các đồ thị hình sin tương ứng với mỗi đường thẳng
sẽ đi qua một điểm duy nhất trong không gian tham số
( )
0 0
,
ρ θ
. Nói cách khác, đối
tượng đầu vào cho việc tính toán không gian tham số là một đường viền hình ảnh. Với
18
mỗi điểm riêng biệt trong đường viền hình ảnh, các đồ thị hình sin tương ứng được tính
toán bằng máy tính sử dụng quan hệ (2). Nếu một tập hợp các điểm đặc trưng trong
đường viền hình ảnh thuộc cùng một đường thẳng, đồ thị hình sin tương ứng của chúng
sẽ có một điểm chung trong không gian tham số. Sử dụng nguyên tắc biến đổi Hough,
nhiệm vụ phát hiện đường thẳng trong không gian (x,y) trở thành tìm ra các điểm
giaonhau của các đường cong hình sin trong không gian tham số. Những điểm đi qua vị
trí của không gian bộ nhớ đơn giản là tham số được bầu chọn cao.

Ma trận
( )
,R
ρ θ
được khởi tạo bằng 0.
Với mỗi điểm đặc trưng (x,y) trong đường viền hình ảnh
Begin
Với mỗi giá trị
[ ]
min max
,
k
θ θ θ
∈
Begin
Tính toán
.cos .sin
k k k
x y
ρ θ θ
= +
Cho
( )
,R
ρ θ
=
( )
,R
ρ θ
+1

. Không gian tham số
( )
,R
ρ θ
có thể được xác định lại bởi quan
hệ (3) và (4):
( )
cos sin / 2 sin
n n n n
x y p K x
ρ θ θ θ
= + +
(3)
( )
'
cos sin / 2 sin
n n n n
x y p K x
ρ θ θ θ
= − + −
(4)
Các đánh giá lượng giác cũng như các sản phẩm có thể tránh được nếu
/ 1 2
m
p K
ε
= = =
với K = p.2m với m là số tự nhiên. Phương trình (3) và (4) trở thành:
'
1

chọn đủ lớn. Tuy nhiên, phương pháp này vẫn cần C.K bổ sung và truy cập không gian
bộ nhớ tham số C.K bởi vì nó sử dụng tất cả các giá trị có thể có của
θ
.
2.2.3 Phương pháp dựa trên góc nghiêng.
Như đã mô tả trước đây, phương pháp này sử dụng góc nghiêng để ước lượng
định hướng đường thẳng vào điểm riêng biệt cần xem xét. Khi một giá trị duy nhất của
θ
cần dùng đến, chỉ có một bộ nhớ truy cập duy nhất được yêu cầu cho mỗi điểm riêng
biệt. Điều này tất nhiên sẽ tăng tốc tính toán và giảm yêu cầu về kích thước bộ nhớ.
Chất lượng yếu kém của các máy dò cạnh không cho phép việc sử dụng đáng tin cậy khi
O’Gormans và M.B. Clowes giới thiệu ý tưởng này vào năm 1976. Góc nghiêng ngang
Gx và góc nghiêng dọc Gy thu được từ toán tử tiền xử lý trong khi chiết xuất đường
viền hình ảnh như Robert, Sobel, Prewitt hoặc sử dụng áy dò cạnh Deriche đứng sau
một hình ảnh mịn.
tan
tan
y
y x
x
x
y x
y
G
G G G
G
G
G G G
G
= ≤

φ φ φ φ
= − = +
(8)
' '
cos [ tan ] y cos [ tan ]x x y y x
φ φ φ φ
= − = +
(9)
Các biểu thức này vẫn còn rất phức tạp để thể hiện phần cứng. Các phép nhân
bởi tan
φ
có thể tránh được nếu các góc quay được giới hạn giá trị là tan
φ
= 2-i. Điều
này dẫn đến toán tử dịch đơn giản. Góc xoay tùy ý có thể thu được bằng cách sử dụng
một vài phép quay cơ bản với
arctan 2
i−
φ =
. Do đó, quan hệ trên có thể được viết theo
(10) và (11):
1
[ 2 ]
i
i i i i i
x K x y d
−
+
= −
(10)

≥

4. Giá trị arctan(2-i) có thể được lấy trực tiếp từ bảng tra cứu (một đầu vào cho mỗi lần
lặp).
Với cơ sở này, thuật toán CORDIC sử dụng hai chế độ xác định dấu hiệu quay cơ
bản: chế độ luân chuyển và chế độ vector. Trong chế độ luân chuyển, góc thiết bị được
khởi tạo với góc z0 mong muốn. Với mỗi lần lặp lại, các dấu hiệu quay được chọn theo
cách như vậy để giảm thiểu các góc còn sót lại trong thiết bị. Do đó, các quyết định
được dựa trên dấu hiệu góc còn sót lại. Sau n lần lặp, thu được phương trình (12) và
(13):
0 0 0 0
[ cos(z ) sin(z )]
n n
x A x y
= −
(12)
[ ]
0 0 0 0
cos( ) sin(z )
n n
y A y z x
= +
(13)
Với
( )
2
1/ 1 2
i
n n
n

 
= + =
 ÷
 
(15)
23
Hình 2.3 So sánh kích thước không gian tham số của biến đổi Hough dựa trên
góc nghiêng và cổ điển
Trong cả hai chế độ, góc quay được giới hạn giữa -
/ 2
π
và
/ 2
π
+
. Hạn chế
này do giá trị 20 đã được sử dụng cho các tiếp tuyến vòng cung tại lần lặp đầu tiên. Đối
24
với các góc lớn hơn
/ 2
π
, vòng quay đầu tiên của
/ 2
π
±
sẽ được thể hiện trong phương
trình (16):
' ' '
y z / 2x dy dx z d
π