ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN

MỤC LỤC
Trang
MỤC LỤC ...................................................................................................................................................... 2
LỜI CẢM ƠN ............................................................................................................................................... 4
DANH SÁCH CÁC HÌNH ẢNH ........................................................................................................ 5

NGUYỄN QUANG SƠN

MỞ ĐẦU ......................................................................................................................................................... 7
CHƯƠNG I: TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN ................................................ 9
1.1. Tổng quan về xử lý ảnh ............................................................................................................. 9
1.1.1. Xử lý ảnh................................................................................................................................. 9

NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP
PHÁT HIỆN BIÊN
Chuyên ngành:
Mã số:

Khoa học máy tính
60.48.01

1.1.2. Các bước cơ bản trong xử lý ảnh ..............................................................................10
1.1.3. Một số vấn đề cơ bản trong xử lý ảnh ....................................................................14
1.2. Toán tử không gian với xử lý ảnh ......................................................................................18
1.2.1. Làm trơn nhiễu bằng lọc tuyến tính .........................................................................18
1.2.2. Làm trơn nhiễu bằng lọc phi tuyến ..........................................................................21
1.2.3. Lọc thông thấp, thông cao và lọc dải thông .........................................................22


LỜI CẢM ƠN

2.3.1. Toán tử la bàn Kirsh ........................................................................................................37
2.3.2. Toán tử la bàn Prewitt ....................................................................................................38

Trước hết tôi muốn gửi lời cảm ơn đến các thầy cô giáo ở Viện công nghệ

2.3.3. Robinson 3 - Level ...........................................................................................................39

thông tin và Khoa công nghệ thông tin - Đại học Thái Nguyên đã quan tâm tổ chức

2.3.4. Robinson 5 - Level ...........................................................................................................40

chỉ đạo và trực tiếp giảng dạy khóa cao học của chúng tôi. Đặc biệt tôi xin gửi lời

2.4. Kỹ thuật phát hiện biên Laplace..........................................................................................41

cảm ơn sâu sắc đến thầy giáo hướng dẫn PGS.TS Ngô Quốc Tạo về những chỉ dẫn

CHƯƠNG III: CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN NÂNG CAO ..........45

khoa học và tận tình hướng dẫn cho tôi trong suốt quá trình làm luận văn. Nếu

3.1. Phương pháp Canny ..................................................................................................................45

không có sự giúp đỡ của thầy thì tôi khó có thể hoàn thành bản luận văn này.

3.1.1. Cơ sở lý thuyết thuật toán .............................................................................................45

Cũng qua đây, tôi xin chân thành cảm ơn lãnh đạo Trung tâm ứng dụng tiến

4


Hình 3.3: Biên ảnh theo phương pháp Canny ...........................................................................52
Hình 3.4: Biên ảnh theo phương pháp Shen-Castan ..............................................................55

DANH SÁCH CÁC HÌNH ẢNH

Hình 3.5: Dùng DWT cho biến đổi Neurite ...............................................................................56
Hình 3.6 Biên ảnh của một cái hộp đơn .......................................................................................57

Hình 1.1: Quá trình xử lý ảnh.............................................................................................................. 9
Hình 1.2: Các bước trong quá trình xử lý ảnh ...........................................................................10
Hình 1.3: Lân cận các điểm ảnh của tọa độ (x,y) ....................................................................16
Hình 1.4: Đường biên lý tưởng.........................................................................................................24
Hình 1.5: Đường biên dốc ...................................................................................................................25
Hình 1.6: Đường biên không trơn ...................................................................................................26
Hình 2.1: Biên ảnh với Pixel Difference......................................................................................31
Hình 2.2: Biên ảnh với Separated Pixel Difference ...............................................................32
Hình 2.3: Biên ảnh với toán tử Robert ..........................................................................................33
Hình 2.4: Biên ảnh với toán tử Prewitt .........................................................................................33
Hình 2.5: Biên ảnh với toán tử Sobel ............................................................................................34
Hình 2.6: Biên ảnh với toán tử Frie-Chen ...................................................................................34

Hình 3.7: Biên ảnh con chó nằm ở bậc thang ............................................................................57
Hình 3.8: Sử dụng 3 tiêu chuẩn cho ảnh con cho nằm bậc thang ....................................58
Hình 3.9: Sử dụng 3 tiêu chuẩn cho ảnh của Filopodia ........................................................59
Hình 3.10: Sử dụng liên kết tự động trong ảnh hộp đơn ......................................................59
Hình 3.11: Sử dụng liên kết tự động trong ảnh con cho nằm bậc thang.......................60
Hình 3.12: Sử dụng liên kết tự động trong ảnh của Filopodia ..........................................60


trong một hệ thống xử lý ảnh. Một số thành phần cốt tử trong xử lý ảnh, như điểm
ảnh, mức xám, biên,…được trình bày như là các khái niệm.

Thời đại công nghệ thông tin phát triển như vũ bão đã đi vào từng ngõ ngách
của cuộc sống. Hiện nay, bất cứ sự phát triển của ngành công nghiệp nào đều có sự
hiện diện và đóng góp rất to lớn của công nghệ thông tin. Xử lý ảnh là một trong
những chuyên ngành quan trọng và lâu đời của Công nghệ thông tin. Xử lý ảnh
được áp dụng trong nhiều lĩnh khác nhau như y học, vật lý, hoá học, tìm kiếm tội
phạm, trong quân sự và trong một số lĩnh vực khác....
Phần lớn con người thu nhận thông tin bằng thị giác, cụ thể đó là các hình ảnh.
Vì vậy xử lý ảnh là vấn đề không thể thiếu và hết sức quan trọng để thu được hình
ảnh tốt hơn, đẹp hơn, nhằm đáp ứng yêu cầu thông tin khác nhau của người nhận.
Trong xử lý ảnh, việc nhận dạng và phân lớp đối tượng cần trải qua các quá
trình và các thao tác khác nhau. Phát hiện biên là một giai đoạn rất quan trọng vì các

Chương II: Các phương pháp phát hiện biên cổ điển
Nội dung của chương này sẽ đề cập đến một số phương pháp phát hiện biên
trong phương pháp đạo hàm bậc nhất và phương pháp đạo hàm bậc hai.
Chương III: Các phương pháp phát hiện biên nâng cao
Trong chương này đề cập đến phương pháp phát hiện biên Canny, phương
pháp Shen-Castan và phương pháp Wavelet.
Chương IV: Một số nhận xét đánh giá các phương pháp phát hiện biên
Qua việc cài đặt thử nghiệm các phương pháp phát hiện biên đã trình bày trong
các chương trước, từ các kết quả mô phỏng thực nghiệm khi chạy chương trình,
trong chương này đưa ra các nhận xét đánh giá, so sánh các phương pháp phát hiện
biên. Chỉ ra phương pháp phát hiện biên phù hợp với loại ảnh cần xử lý.

kỹ thuật phân đoạn ảnh chủ yếu dựa vào giai đoạn này. Mục đích của việc dò biên
sẽ đánh dấu những điểm trong một ảnh số mà có sự thay đổi đột ngột về độ xám,

1.1.2. Các bước cơ bản trong xử lý ảnh
Quá trình xử lý một ảnh đầu vào nhằm thu được một ảnh đầu ra mong muốn
thường phải trải qua rất nhiều bước khác nhau. Các bước cơ bản của một quá trình
xử lý ảnh được thể hiện thông qua hình sau:

CHƯƠNG I
TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN

Biểu diễn và
mô tả

Phân đoạn
ảnh

1.1. Tổng quan về xử lý ảnh
1.1.1. Xử lý ảnh
Con người thu nhận thông tin qua các giác quan trong đó thị giác đóng vai trò
quan trọng nhất. Sự phát triển nhanh của phần cứng máy tính, xử lý ảnh và đồ hoạ

Tiền xử
lý ảnh

đã phát triển mạnh mẽ và ngày càng có nhiều ứng dụng trong cuộc sống. Xử lý ảnh

CƠ SỞ
TRI THỨC

đóng một vai trò quan trọng trong tương tác người máy.
Quá trình xử lý nhận dạng ảnh là một quá trình thao tác nhằm biến đổi một
ảnh đầu vào để cho ra một kết quả mong muốn. Kết quả đầu ra của một quá trình xử

Converter) để thu nhận dạng số hoá của ảnh. Mặc dù đây chỉ là công đoạn đầu tiên
song kết quả của nó có ảnh hưởng rất nhiều đến công đoạn kế tiếp.

- Từ ảnh đầu vào mà có những nhận xét, kết luận ở mức cao hơn, sâu hơn (ví
dụ: ảnh một tai nạn giao thông phác hoạ hiện trường tai nạn).
9

10


thuộc rất nhiều vào công đoạn này.

1.1.2.2 Tiền xử lý
Ở bước này, ảnh sẽ được cải thiện về độ tương phản, khử nhiễu, khôi phục

Kết quả của bước phân đoạn ảnh thường được cho dưới dạng dữ liệu điểm ảnh

ảnh, nắn chỉnh hỉnh học... Với mục đích làm cho chất lượng ảnh trở lên tốt hơn nữa,

thô, trong đó hàm chứa biên của một vùng ảnh hoặc tập hợp tất cả các điểm ảnh

chuẩn bị cho các bước xử lý phức tạp kế tiếp sau đó.

thuộc về chính vùng ảnh đó. Trong cả hai trường hợp, sự chuyển đổi dữ liệu thô này

* Khử nhiễu: Nhiễu được chia thành hai loại: nhiễu hệ thống và nhiễu ngẫu

thành một dạng thích hợp hơn cho việc xử lý trong máy tính là hết sức cần thiết,

nhiên. Đặc trưng của nhiễu hệ thống là tính tuần hoàn. Do vậy, có thể khử nhiễu này


f(x',y') như sau:

 x' = hx ( x, y )

 y ' = hy ( x , y )

chất để thể hiện ảnh gọi là trích chọn đặc trưng (Feature Selection) gắn với việc

Trong đó hx, hy là các phương trình tuyến tính (biến dạng do phối cảnh) hay

tách các đặc tính của ảnh dưới dạng các thông tin định lượng hoặc làm cơ sở để

dạng thích hợp là cần thiết cho xử lý tiếp theo bằng máy tính. Việc chọn các tính

bậc hai (biến dạng do ống kính camara).

phân biệt lớp đối tượng này với đối tượng khác trong phạm vi ảnh nhận được. Ví

1.1.2.3 Phân đoạn ảnh

từng ký tự giúp phân biệt ký tự này với ký tự khác.

dụ: trong nhận dạng ký tự trên phong bì thư, chúng ta miêu tả các đặc trưng của

Phân đoạn ảnh có nghĩa là chia một ảnh đầu vào thành nhiều phần khác nhau
hay còn gọi là các đối tượng để biểu diễn phân tích, nhận dạng ảnh. Ví dụ: để nhận

b) Mô tả


cuộc sống không chỉ tạo ra những thách thức về giải thuật, mà còn đặt ra những yêu
cầu về tốc độ tính toán. Đặc điểm chung của tất cả những ứng dụng đó là những đặc

• Biểu diễn bằng mã xích: Phương pháp này thường dùng để biểu diễn đường
biên ảnh.

điểm đặc trưng cần thiết thường là nhiều, không thể do chuyên gia đề xuất, mà phải
được trích chọn dựa trên các thủ tục phân tích dữ liệu.

• Biểu diễn bằng mã tứ phân: Phương pháp này được dùng để mã hoá cho
vùng ảnh.

Việc trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các đối tượng
ảnh chính xác, với tốc độ tính toán cao và dung lượng nhớ lưu trữ giảm xuống.
Các đặc điểm của đối tượng được trích chọn tuỳ theo mục đích nhận dạng
trong quá trình xử lý ảnh. Có thể nêu ra một số đặc điểm của ảnh sau đây:

1.1.2.5 Nhận dạng và nội suy ảnh
Nhận dạng ảnh là quá trình xác định ảnh. Quá trình này thường thu được bằng
cách so sánh với mẫu chuẩn đã được lọc (hoặc lưu) từ trước.

- Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ, điểm
uốn v.v..

Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Ví dụ: một loạt chữ

- Đặc điểm biến đổi: Các đặc điểm loại này được trích chọn bằng việc thực

số và nét gạch ngang trên phong bì thư có thể được nội suy thành mã điện thoại. Có


1.1.3.1 Điểm ảnh (Picture Element)
Gốc của ảnh là ảnh liên tục về không gian và độ sáng. Để xử lý bằng máy tính,

1.1.2.6 Cơ sở tri thức
Ảnh là một đối tượng khá phức tạp về đường nét, độ sáng tối, dung lượng

ảnh cần phải được số hoá. Số hoá ảnh là sự biến đổi gần đúng một ảnh liên tục

điểm ảnh, môi trường để thu ảnh phong phú kéo theo nhiễu. Trong nhiều khâu xử lý

thành một tập điểm phù hợp với ảnh thật về vị trí (không gian) và độ sáng (mức

và phân tích ảnh ngoài việc đơn giản hóa các phương pháp toán học đảm bảo tiện

xám). Khoảng cách giữa các điểm ảnh đó được thiết lập sao cho mắt người không

lợi cho xử lý, người ta mong muốn bắt chước quy trình tiếp nhận và xử lý ảnh theo

phân biệt được ranh giới giữa chúng. Mỗi một điểm như vậy gọi là điểm ảnh (PEL:

cách của con người. Trong các bước xử lý đó, nhiều khâu hiện nay đã xử lý theo

Picture Element) hay gọi tắt là Pixel. Trong khuôn khổ ảnh hai chiều, mỗi pixel ứng

các phương pháp trí tuệ con người. Vì vậy, ở đây các cơ sở tri thức được phát huy.

với cặp tọa độ (x, y).

13


trong đó: số 1 là giá trị logic; N4(p) tập 4 điểm lân cận của p.

được sự liên tục của ảnh. Việc lựa chọn khoảng cách thích hợp tạo nên một mật độ
Đông

x

Tây

Nam

(x-1,y-1)

(x,y-1)

(x+1,y-1)

y

(x-1,y)

(x,y)

(x+1,y)

Bắc

(x-1,y+1)

(x,y+1)

Các mối liên kết được sử dụng để xác định giới hạn (Boundaries) của đối
tượng vật thể hoặc xác định vùng trong một ảnh. Một liên kết được đặc trưng bởi
tính liền kề giữa các điểm và mức xám của chúng.
Giả sử V là tập các giá trị mức xám. Một ảnh có các giá trị cường độ sáng từ
thang mức xám từ 32 đến 64 được mô tả như sau :

16


V={32, 33, … , 63, 64}.
Có 3 loại liên kết:

1.2. Toán tử không gian với xử lý ảnh
Thông thường ảnh thu nhận được có nhiễu cần phải loại bỏ hay không sắc nét

* Liên kết 4: Hai điểm ảnh p và q được nói là liên kết 4 với các giá trị cường
độ sáng V nếu q nằm trong một các lân cận của p, tức q thuộc N4(p)
* Liên kết 8: Hai điểm ảnh p và q nằm trong một các lân cận 8 của p, tức q

bị mờ hoặc cần làm tõ các chi tiết như đường biên ảnh. Các toán tử không gian
dùng trong kỹ thuật tăng cường ảnh được phân nhóm theo công dụng: làm trơn
nhiễu, nổi biên. Để làm trơn nhiễu hay tách nhiễu, người ta sử dụng các bộ lọc
tuyến tính (lọc trung bình, thông thấp) hay lọc phi tuyến (trung vị, giả trung vị, lọc

thuộc N8(p)
* Liên kết m (liên kết hỗn hợp): Hai điểm ảnh p và q với các giá trị cường độ

đồng hình). Từ bản chất của nhiễu (thường tương ứng với tần số cao) và từ cơ sở lý
thuyết lọc là: bộ lọc chỉ cho tín hiệu có tần số nào đó thông qua do đó, để lọc nhiễu


Xqs, ảnh gốc là Xgốc, nhiễu là η, ảnh thu được có thể biểu diễn bởi:

Khoảng cách Euclide: Khoảng cách Euclide giữa hai điểm ảnh p(x, y) và

Xqs = Xgốc + η
- Nhiễu nhân

q(s,t) được định nghĩa như sau:
De(p, q) = [(x - s)2 + (y - t)2]1/2
Khoảng cách khối: Khoảng cách D4(p, q) được gọi là khoảng cách khối đồ thị

Nhiễu nhân thường phân bố khắp ảnh và ảnh thu được sẽ biểu diễn với công
thức:

và được xác định như sau:

Xqs = Xgốc * η
D4(p,q) = | x - s | + | y - t |

Giá trị khoảng cách giữa các điểm ảnh r: giá trị bán kính r giữa điểm ảnh từ

- Nhiễu xung
Nhiễu xung thường gây đột biến tại một số điểm ảnh.

tâm điểm ảnh đến tâm điểm ảnh q khác.
Khoảng cách D8(p, q) còn gọi là khoảng cách bàn cờ giữa điểm ảnh p, q được
xác định như sau:

1.2.1. Làm trơn nhiễu bằng lọc tuyến tính
Do có nhiều loại nhiễu can thiệp vào quá trình xử lý ảnh nên cần có nhiều bộ


Nếu trong kỹ thuật lọc trên, ta chọn các trọng số bằng nhau, phương trình trên

26 31 19 16 
39 46 31 27 

43 49 34 27 

48 48 34 22
35 33 22 11 

Lọc trung bình trọng số là một trường hợp riêng của lọc thông thấp.

sẽ có dạng:
v ( m, n ) =

Với :

1
∑
N

∑ y ( m − k , n − l)

( k ,l )∈W

y(m,m): ảnh đầu vào

b) Lọc thông thấp


1

Trong lọc trung bình, thường người ta ưu tiên cho các hướng để bảo vệ biên
của ảnh khỏi bị mờ khi làm trơn ảnh. Các kiểu mặt nạ được sử dụng tùy theo các
trường hợp khác nhau. Các bộ lọc trên là bộ lọc tuyến tính theo nghĩa là điểm ảnh ở
tâm cửa số sẽ được thay bởi tổ hợp các điểm lân cận chập với mặt nạ.
Giả sử ảnh đầu vào biểu diễn bởi ma trận:
4
5

I = 6

5
5

7 3 7 1
1 7 1 
6 1 8 3

7 5 7 1
7 6 1 2
7

Ảnh số thu được bởi lọc trung bình Y = H⊗I có dạng:

19

0 1 0 
1
1 2 1 


1
Nw

∑ ∑X

qs

( m − k , n − l) +

k ,l∈W

k ,l∈W

σ 2n
Nw

Như vậy, nhiễu cộng trong ảnh đã giảm đi Nw lần.
c) Lọc đồng hình (Homomorphie Filter)

Kỹ thuật lọc này hiệu quả với ảnh có nhiễu nhân. Thực tế, ảnh quan sát được

20


gồm ảnh gốc nhân với hệ số nhiễu. Gọi X( m, n ) là ảnh thu được, X(m,n) là ảnh gốc

* Tính chất của lọc trung vị:

và η(m,n) là nhiễu như vậy:

trường hợp đó, thay thế giá trị của điểm ảnh bằng giá trị trung bình 8 lân cận vừa
tính được. Bộ lọc ngoài có thể diễn tả bằng công thức sau:
α( w )
Y(m,n) = 
 u ( m, n )

a) Lọc trung vị

Trung vị được viết với công thức:
v(m,n) = Trungvi(y(m-k,n-l))

với {k,l} ∈ W

Kỹ thuật này đòi hỏi giá trị các điểm ảnh trong cửa sổ phải xếp theo thứ tự
tăng hay giảm dần so với giá trị trung vị. Kích thước cửa số thường được chọn sao
cho số điểm ảnh trong cửa số là lẻ. Các cửa sổ hay dùng là cửa sổ có kích thước
3x3, hay 5x5 hay 7x7. Thí dụ:
Nếu y(m) = {2, 3, 8, 4, 2} và cửa sổ W=(-1, 0, 1), ảnh thu được sau lọc trung
vị sẽ là:

≠

với α(w) là trung bình cộng các điểm trong lân cận w; δ là ngưỡng ngoài
Các cửa sổ tính toán thường chọn là 3x3. Tuy nhiên, cửa sổ có thể mở rộng
đến 5x5 hay 7x7 để đảm bảo tính tương quan giữa các điểm ảnh. Vấn đề quan trọng
là xác định ngưỡng để loại nhiễu mà vẫn không làm mất thông tin của ảnh.
1.2.3. Lọc thông thấp, thông cao và lọc dải thông

Toán tử trung bình không gian là lọc thông thấp. Nếu hLP(m, n) biểu diễn bộ
lọc thông thấp.

Tập hợp các điểm biên tạo thành biên, hay còn gọi là đường bao của ảnh

Bộ lọc thông thấp thường dùng làm trơn nhiễu và nội suy ảnh. Bộ lọc thông
cao dùng nhiều trong trích chọn biên và làm trơn ảnh, còn bộ lọc dải thông có hiệu
quả làm nổi cạnh. Về biên sẽ được trình bày kỹ trong các phần sau. Tuy nhiên, dễ
nhận thấy, biên là điểm có độ biến thiên nhanh về giá trị mức xám theo quan điểm

(boundary). Chẳng hạn, trong một ảnh nhị phân, một điểm có thể được gọi là biên
nếu đây là một điểm đen và có ít nhất một điểm trắng nằm trong lân cận điểm đó.
Mỗi một biên là một thuộc tính gắn liền với một điểm riêng biệt và được tính
toán từ những điểm lân cận nó. Đó là một biến Vector bao gồm hai thành phần:

về tần số tín hiệu. Như vậy, các điểm biên ứng với các thành phần tần số cao. Từ đó,

- Độ lớn của Gadient.

có thể dùng bộ lọc thông cao để cải thiện nhiễu nghĩa là có thể lọc các thành phần

- Hướng φ được quay đối với hướng Gradient ψ.

tần số thấp và giữ lại các thành phần tần số cao. Vì thế, lọc thông cao thường được
dùng làm trơn biên trước khi tiến thành các thao tác với biên ảnh. Dưới đây là một

1.3.1.1 Biên lý tưởng

Việc phát hiện biên một cách lý tưởng là việc xác định được tất cả các đường

số mặt nạ dùng trong lọc thông cao:

bao trong đối tượng. Biên là sự thay đổi đột ngột về mức xám nên sự thay đổi cấp

- 2

1 

xám giữa các vùng trong ảnh càng lớn thì càng dễ dàng nhận ra biên.
Hình minh hoạ điểm ảnh có sự biến đổi mức xám u(x) một cách đột ngột:
u

Các nhân chập thông cao có đặc tính chung là tổng các hệ số của bộ lọc bằng
1. Nguyên nhân chính là ngăn cản sự tăng quá giới hạn của các giá trị mức xám (các
giá trị điểm ảnh vẫn giữ được giá trị của nó một cách gần đúng không thay đổi quá
nhiều với giá trị thực).

x

1.3. Tổng quan về biên
1.3.1. Biên và các kiểu biên cơ bản

Hình1.4: Đường biên lý tưởng

Các đặc trưng của ảnh thường bao gồm các thành phần như: mật độ xám, phân
bố xác suất, phân bố không gian, biên ảnh. Biên là một vấn đề chủ yếu và đặc biệt
quan trọng trong phân tích ảnh vì các kĩ thuật phân đoạn ảnh chủ yếu dựa vào biên.
Hiện nay có nhiều định nghĩa về biên ảnh và mỗi định nghĩa được sử dụng

Một biên được coi đó là biên lý tưởng khi mà có sự thay đổi cấp xám lớn giữa
các vùng trong ảnh. Biên này thường chỉ xuất hiện khi có sự thay đổi cấp xám qua
một điểm ảnh.

trong một số trường hợp nhất định. Song nhìn chung, ta có thể hiểu là:


Trên thực tế, ảnh thường có biên không lý tưởng, các điểm ảnh trên ảnh
thường có sự thay đổi mức xám đột ngột và không đồng nhất, đặc biệt là ảnh nhiễu.
Trong trường hợp không nhiễu (biên lý tưởng), bất cứ một sự thay đổi cấp xám nào
cũng thông báo sự tồn tại của một biên. Trường hợp đó khó có khả năng xảy ra, ảnh
thường là không lý tưởng, có thể là do các nguyên nhân sau:

ảnh. Người ta sử dụng đường biên làm phân cách các vùng xám (màu) cách biệt.
Ngược lại, người ta cũng dùng các vùng ảnh để tìm đường phân cách.
Như đã đề cập tới ở phần tổng quan về một hệ thống nhận dạng và xử lý ảnh,
quá trình nhận dạng có hai giai đoạn cần thực hiện:
- Giai đoạn học: Các đặc điểm của đối tượng mẫu được lưu trữ (gọi là học
mẫu) và tập các phần tử mẫu được chia thành các lớp.

- Hình dạng không sắc nét.
- Nhiễu: do một loạt các yếu tố như: kiểu thiết bị nhập ảnh, cường độ ánh

- Giai đoạn nhận dạng: Khi có đối tượng cần nhận dạng, các đặc điểm của đối

sáng, nhiệt độ, hiệu ứng áp suất, chuyển động, bụi…, chưa chắc rằng hai điểm ảnh

tượng sẽ được trích chọn và sử dụng hàm quyết định để xác định đối tượng cần

có cùng giá trị cấp xám khi được nhập lại có cùng cấp xám đó trong ảnh. Kết quả

nhận dạng thuộc lớp nào.

của nhiễu trên ảnh gây ra một sự biến thiên ngẫu nhiên giữa các điểm ảnh. Sự xuất

Như vậy, việc nhận dạng sẽ chính xác nếu các đặc điểm được trích chọn chính

- Bất biến tô-pô: Biểu diễn các cấu trúc tô-pô của các ảnh như số điểm đỉnh, số
lỗ hổng v.v..
- Bất biến đại số: Chu tuyến, phân bố của các điểm ảnh, v.v.. dựa vào các việc
tổ hợp các hệ số của đa thức mô tả đối tượng ảnh.
Các bất biến dùng trong nhận dạng thường được trích chọn từ biên, xương của

CHƯƠNG II

đối tượng [3,5,8,18,33,38,39,45,46,48]. Do vậy, việc nhận dạng có hiệu quả hay

CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN CỔ ĐIỂN

không phụ thuộc nhiều vào cách biểu diễn hình dạng và mô tả của vật thể.
Biên là một phần đặc biệt quan trọng trong xử lý ảnh, hầu như trước khi sử
dụng các thuật toán phát hiện biên phải trải qua một bước tiền xử lý, đó là quá trình
loại bỏ nhiễu. Cơ sở của các phép toán phát hiện biên đó là quá trình biến đổi về giá
trị độ sáng của các điểm ảnh. Tại điểm biên sẽ có sự biến đổi đột ngột về mức xám.
Đây chính là cơ sở của kỹ thuật phát hiện biên. Xuất phát từ cơ sở này, có hai
phương pháp phát hiện biên tổng quát, đó là phương pháp phát hiện biên trực tiếp
và phương pháp phát hiện biên gián tiếp.
2.1. Phân loại các kỹ thuật phát hiện biên
2.1.1. Phương pháp phát hiện biên trực tiếp

Phương pháp phát hiện biên này nhằm làm nổi biên dựa vào sự biến thiên về
giá trị độ sáng của điểm ảnh. Kỹ thuật chủ yếu dùng phát hiện biên ở đây là kỹ thuật
đạo hàm.
- Nếu lấy đạo hàm bậc nhất của ảnh ta có phương pháp Gradient.
Phương pháp này bao gồm kỹ thuật Gradient và kỹ thuật la bàn.
- Nếu lấy đạo hàm bậc hai của ảnh ta có phương pháp Laplace.
2.1.2. Phương pháp phát hiện biên gián tiếp


pháp trực tiếp tỏ ra không đạt được hiệu quả tốt. Phương pháp tìm biên gián tiếp
dựa trên các vùng, đòi hỏi áp dụng lý thuyết về xử lý kết cấu đối tượng phức tạp, vì

Việc xấp xỉ đạo hàm bậc nhất theo các hướng x và y được thực hiện thông
qua 2 mặt nạ nhân chập tương ứng sẽ cho ta các kỹ thuật phát hiện biên khác nhau.

thế khó cài đặt, song đạt hiệu quả cao khi sự biến thiên về cường độ sáng là nhỏ.
Trong khuôn khổ bản luận văn này ta đề cập nghiên cứu chủ yếu phương pháp
phát hiện biên trực tiếp.

2.2.1. Pixel difference

Đây là bộ lọc cơ bản dựa theo kỹ thuật Gradient, bộ lọc này áp dụng phương
thức so sánh giữa điểm ảnh đang xét với một điểm lân cận nó (sự khác nhau giữa
các điểm ảnh). Vì thế mặt nạ được sử dụng ở đây là hai mặt nạ Hx và Hy biểu thị

2.1.3. Quy trình phát hiện biên

Bước 1: Do ảnh ghi được thường có nhiễu, bước một là phải lọc nhiễu theo các

theo hai hướng dọc (mặt nạ theo hướng x) và ngang (mặt nạ theo hướng y) như sau:

phương pháp đã tìm hiểu ở các phần trước.
Bước 2: Làm nổi biên sử dụng các toán tử phát hiện biên.
Bước 3: Định vị biên. Chú ý rằng kỹ thuật nổi biên gây tác dụng phụ là gây
nhiễu làm một số biên giả xuất hiện do vậy cần loại bỏ biên giả.
Bước 4: Liên kết và trích chọn biên.

0

Đây là phép toán lấy đạo hàm bậc nhất trong không gian hai chiều.
Theo định nghĩa Gradient là một véctơ có các thành phần biểu thị tốc độ thay
đổi giá trị của điểm ảnh, ta có:
∂f ( x, y)
f ( x + dx , y) − f ( x , y)
= f (x) ≈
∂x
dx
∂f ( x, y)
f ( x , y + dx ) − f ( x , y)
= f ( y) ≈
∂y
dy

Để giảm thời gian tính toán và độ phức tạp ta có xấp xỉ:
G[f(i,j)] ≈ Gx + Gy

⇔ G[f(i,j)] = f(i,j) - f(i+1,j) + f(i,j) - f(i,j-1)
Ta có kết quả tìm biên theo kỹ thuật này như sau:

Trong đó dx, dy là khoảng cách giữa 2 điểm kế cận theo hướng x, y tương ứng
(thực tế chọn dx= dy=1). Đây là phương pháp dựa theo đạo hàm riêng bậc nhất theo

29

30


a) Ảnh gốc


Hx = 1
0

0
0
0

0
−1
0 

0
Hy = 0
0

-1
0
1

0
0
0 

Sử dụng phép nhân cuộn di chuyển 2 mặt nạ trên ảnh cần tìm biên sao cho tâm
chính giữa của mặt nạ trùng với điểm ảnh đang xét.
Giá trị điểm ảnh mới sau khi thực hiện Gradient tại điểm (i,j) được tính theo
công thức:

0
Hx = 

trên ảnh. Từ đó cho ra kết quả của ảnh mới theo phương pháp này.
Như vậy, ta có kết quả Gradient tại một điểm ảnh (i,j):
y(i,j)= |y(i,j+1)- y(i+1,j)| + |y(i,j)+y(i+1,j+1)|
Kết quả của toán tử Robert sau khi tiến hành tách biên:

31

32


- 1 0
H x = - 1 0
- 1 0

a) Ảnh gốc

1
1
1

- 1
H y =  0
 1

- 1
0
1

-1
0

0
1

2.2.6. Toán tử Frie-Chen

Phương pháp Frie-Chen được thiết kế xấp xỉ đạo hàm Gradient rời rạc. Mặt nạ
Frie-Chen xử lý có hình dạng như sau:
1

Hx =  2
1


0
0
0

-1 

- 2
-1 


- 1

Hy =  0

1

- 2


Một hạn chế chung đối với toán tử Gradient là không có khả năng phát hiện

1
1

1

H x = 1
1

1
1


biên trong môi trường nhiều nhiễu. Điều này đặt ra vấn đề làm giảm bớt bằng việc
mở rộng thêm kích thước của toán tử ra các khu lân cận thông qua vi phân đường
dốc.
1
1

1

H x = 1
1

1
1



1

1

0

1

1

0

- 1 - 1 - 1 - 1
- 1 - 1 - 1 - 1

- 1 - 1 - 1 - 1

Hy =  0 0 0 0
1 1 1 1

1 1 1 1
1 1 1 1


-1 -1 -1 
- 1 - 1 - 1 
-1 -1 -1 

-1 -1 -1 
-1 -1 -1 

2

3

0

-3

2

3

0

-3

2

2

0

-2

1

1

0


-2
-3
0
3
2
1

a) Ảnh gốc

- 1
- 1
- 2 - 1

0 0
2
1

2 1
1
1 

-1
-2

b) Ảnh biên

Hình 2.8: Biên ảnh với toán tử Truncated Pyramid
2.3. Các toán tử la bàn
a) Ảnh gốc


b) Ảnh biên

Hình 2.9: Biên ảnh với toán tử Kirsh

2.3.1 Toán tử la bàn Kirsh

Phép toán này được xem như là các toán tử thuần nhất. Nó tạo ra một sự thay
đổi nhỏ trong Gradient và tạo ra các sự so sánh lần lượt như các phương pháp trên.

2.3.2 Toán tử la bàn Prewitt

Cũng giống như toán tử la bàn Kirsh, toán tử la bàn Prewitt đưa ra các mặt nạ

Các mặt nạ được sử dụng như sau:
- 3 5 5 
HĐông-Bắc = - 3 0 5
- 3 - 3 - 3 

HBắc =

 5 5 5
- 3 0 - 3 


- 3 - 3 - 3 

nhân cuộn theo 8 hướng khác nhau. Giá trị độ lớn của điểm ảnh mới được thực hiện
như Kirsh. Các mặt nạ có dạng như sau:
 1
HĐông-Bắc =  1

 1

- 1

1
1
- 2 1
- 1 - 1

HĐông=

- 3 - 3
- 3 0

- 3 - 3

5
5
5 

- 3 - 3 - 3 
HĐông-Nam = - 3 0 5
- 3 5 5 
 5 - 3 - 3
 5 0 - 3


 5 - 3 - 3 

HĐông =

1

1
-2
1

HTây =

1
1

1

Ký hiệu Ai; i = 1,2,....,8 là Gradient theo 8 hướng như 8 mặt nạ kể trên, khi đó
biên độ Gradient tại điểm ảnh (x,y) được tính theo:
i = 1,2,...,8
37

- 1
- 1

- 1

- 1
HTây-Bắc = - 1
 1

lớn nhất trong tám kết quả của việc nhân xoắn.

A(x,y) = Max(gi(x,y))

1

1 


a) Ảnh gốc

b) Ảnh biên

a) Ảnh gốc

Hình 2.10: Biên ảnh với toán tử la bàn Prewitt

Hình 2.11: Biên ảnh với toán tử Robinson 3 - level

2.3.3. Robinson 3 - Level

Cũng giống như các toán tử la bàn ở trên. Robinson 3 - Level được phát triển
từ toán tử Prewitt. Các mặt nạ có dạng như sau:
 1
HĐông-Bắc =  1
 0

1
0
-1

 1
HĐông =  1
 1

- 1

 -1
 0

 1

-1

HBắc =

- 1
- 1

- 1

 0
HĐông-Nam =  1
 1

-1
0

1
0
- 1

1

- 1


0
1

HTây =

1
1

1

0
1

0
1
1

 -1
 -1

 0

b) Ảnh biên

HĐông =

HNam =

 1

 0

 1

-2

HBắc =

- 1
-2

- 1

 0
HĐông-Nam =  1
 2

-1
0

1
0
- 1 

HTây =

0
1

0

-1
0
1
- 2
-1 

0

Do tính đối xứng nên trong bộ mặt nạ này ta cũng chỉ cần sử dụng 4 mặt nạ là
đủ.

40


Toán tử Laplace dùng nhiều kiểu mặt nạ khác nhau để xấp xỉ rời rạc đạo hàm
bậc hai. Dưới đây là ba kiểu mặt nạ hay dùng:
 0
H1 = - 1
 0

-1
4
-1

0
- 1 
0 

- 1
H2 = - 1


Ikq = I ⊗ H
Kết quả mô phỏng được thể hiện như hình sau:

2.4. Kỹ thuật phát hiện biên Laplace

Để khắc phục hạn chế và nhược điểm của phương pháp Gradient, trong đó sử
dụng đạo hàm riêng bậc nhất người ta nghĩ đến việc sử dụng đạo hàm riêng bậc hai
hay toán tử Laplace. Phương pháp dò biên theo toán tử Laplace hiệu quả hơn
phương pháp toán tử Gradient trong trường hợp mức xám biến đổi chậm, miền
chuyển đổi mức xám có độ trải rộng.
Toán tử Laplace được xác định như sau:
∇ 2f =

a) Ảnh gốc

∂ 2f ∂ 2f
+
∂x 2 ∂y 2

b) Ảnh biên

Hình 2.13: Biên ảnh với kỹ thuật Laplace

Toán tử Laplace dùng một số kiểu mặt nạ khác nhau nhằm tính gần đúng đạo
hàm riêng bậc hai. Các dạng mặt nạ theo toán tử Laplace bậc 3x3 có thể:
∂ 2f
= 2f ( x, y) − f ( x − 1, y) − f ( x + 1, y)
∂x 2
∂ 2f


42

O(x,y)


Phương pháp này thực hiện như sau:

với ảnh nhiễu, bước này làm mờ đi ảnh cần xử lý, nghĩa là các điểm nhiễu cũng bị

- Làm trơn ảnh với bộ lọc Gauss

làm mờ đi trong khi những cạnh chính thì vẫn tồn tại.

- Tìm điểm cắt không (áp dụng bộ lọc Laplace)

Bước 2: Tiến hành đạo hàm bậc hai

Ảnh kết quả:

Kết quả nhận được ở bước 1 là ảnh sau khi làm trơn đã loại bỏ bớt được
nhiễu. Để thực hiện phương pháp Laplace of Gauss, ta tiến hành đạo hàm bậc hai

O( x , y) = ∇ (I( x, y) * G ( x, y))
2

- Hàm Gauss:

kết quả ở bước 1. Việc đạo hàm kết quả này tương tự như việc ta tiến hành nhân


2

Đạo hàm bậc nhất của Gauss:

∆2 S

∂2
S
∂x 2

=

x2

g"(x) = (

x 2 1 − 2σ
− )e
σ3 σ

∆2g =

logσ=

−
1
e
2πσ

x 2 + y2




x 2 + y2
2σ2

Song ở bước thứ nhất ta tiến hành nhân ảnh với bộ lọc Gauss, nên ở đây ta chỉ
x 2 + y2
2σ2

phải đạo hàm ảnh S (không sử dụng công thức đạo hàm Gauss). Vì vậy, ta tiến hành
nhân ảnh sau khi làm trơn với một trong ba mặt nạ nhân xoắn của Laplace.

Quá trình thực hiện:

Bước 1: Làm trơn ảnh
Để giảm bớt nhiễu cho ảnh, ta tiến hành làm trơn ảnh bằng bộ lọc Gauss. Việc
làm trơn ảnh được thực hiện bằng cách tiến hành nhân xoắn ảnh với bộ lọc Gauss.
S = I * g(x,y) = g(x,y) * I
Bộ lọc Gauss có thể được xấp xỉ là các bộ lọc với kích thước ma trận khác
nhau với các σ khác nhau.

Như vậy để thực hiện bước 1: Ta tiến hành nhân xoắn ảnh cần xử lý với bộ
lọc Gauss giống như cách thức nhân xoắn của các toán tử ta đã thực hiện ở trên. Kết

a) Ảnh gốc

b) Ảnh biên

Hình 2.15: Biên ảnh với kỹ thuật Laplace of Gauss


( x )dx

−w

3.1. Phương pháp Canny
Phương pháp này do John Canny ở phòng thí nghiệm MIT khởi xướng vào

Localization =

năm 1986. Canny đã đưa một tập hợp các ràng buộc mà một phương pháp phát hiện

Các ràng buộc mà phương pháp phát hiện biên Canny đã thực hiện được đó là:
mức lỗi, định vị và hiệu suất. Trong đó:
- Mức lỗi: có ý nghĩa là một phương pháp phát hiện biên chỉ và phải tìm tất cả
các biên, không biên nào được tìm bị lỗi.
- Định vị: Điều này nói đến độ chênh lệch cấp xám giữa các điểm trên cùng
một biên phải càng nhỏ càng tốt.
- Hiệu suất: là làm sao cho khi tách biên không được nhận ra nhiều biên trong
khi chỉ có một biên tồn tại.
Ràng buộc mức lỗi và định vị được dùng để đánh giá các phương pháp phát
hiện biên. Còn ràng buộc về hiệu suất thì tương đương với mức lỗi dương.
Canny đã giả thiết rằng nhiễu trong ảnh tuân theo phân bố Gauss và đồng thời
ông cũng cho rằng một phương pháp phát hiện biên thực chất là một bộ lọc nhân
xoắn có khả năng làm mịn nhiễu và định vị được cạnh. Vấn đề là tìm một bộ lọc sao
45

2

dx

n0

biên phải đạt được. Ông đã trình bày một phương pháp tối ưu nhất để thực hiện

Ý tưởng thuật toán: Ý tưởng của phương pháp này là định vị đúng vị trí bằng

A f (0)

−∞

Trong đó:
SNR: (mức lỗi) nhằm tìm một hàm f(x) phản đối xứng sao cho tỷ số giữa tín
hiệu và nhiễu là cực đại.
Các giá trị Localization đại diện cho nghịch đảo chênh lệch mức xám giữa các
điểm trong cùng một biên và càng lớn càng tốt.
XZC: ràng buộc này nhằm hạn chế điểm cực trị cục bộ với mục đích cung cấp
chỉ một đường bao.
Canny cố gắng tìm ra bộ lọc f làm cực đại tích: SNR * Localization. Nhưng
cuối cùng thì một sự sấp xỉ có hiệu quả của f lại chính là đạo hàm bậc nhất của hàm
Gauss.
Khi đó G có đạo hàm theo cả hai hướng x và y. Sự xấp xỉ với bộ lọc tối ưu
của thuật toán phát hiện biên Canny chính là G’ và do vậy, bằng phép nhân xoắn
ảnh vào với G’ ta thu được ảnh E đã được tách biên ngay cả trong trường hợp ảnh
có nhiều nhiễu.
Phép nhân xoắn thực hiện một cách dễ dàng trong khi việc tính toán khá phức

46


tạp, đặc biệt là nhân xoắn với mảng hai chiều. Tuy nhiên một phép nhân xoắn với






Như vậy, kết quả ảnh bước hai chính là sự tổng hợp của đạo hàm của Gauss
theo hướng x nhân với ảnh I và đạo hàm của Gauss theo hướng y nhân với ảnh I.

3.1.2. Hoạt động của thuật toán

Nghĩa là ta có thể đạo hàm hàm Gauss theo hai hướng rồi mới tiến hành nhân

a)Thuật toán
Thuật toán được tiến hành qua bốn bước cơ bản sau:
- Đọc ảnh I cần xử lý: tiến hành làm trơn ảnh bằng cách nhân xoắn ảnh với bộ

xoắn với ảnh thay vì nhân xoắn ảnh với hàm Gauss rồi mới đạo hàm.
Có thể minh hoạ như sau đạo hàm hàm Gauss theo hai hướng x và y như sau:

lọc Gauss.
- Đạo hàm bậc nhất kết quả trên theo hai hướng x và y:
Điều này tương ứng với việc nhân xoắn ảnh kết quả ở bước 1 theo hai hướng

gx(x,y)

(x và y) với một bộ lọc dựa trên đạo hàm bậc nhất (các bộ lọc của kỹ thuật
Gradient).
Từ đó đưa ra kết quả đạo hàm ảnh sau khi tiến hành nhân xoắn với Gauss.
- Cho ảnh kết quả ở bước trên tiến hành “Non-maximum Suppression” Nghĩa
là loại bỏ bớt các điểm cạnh (loại bỏ bớt nhiễu), chỉ giữ lại điểm có mức xám cao.



Như đã biết, phương pháp Gradient là phương pháp dò biên cục bộ dựa vào

112,50

cực đại của đạo hàm, đó chính là phương pháp đạo hàm bậc nhất. Chính vì vậy ta có

y

67,50

thể thực hiện việc đạo hàm ở bước 2 bằng cách nhân ảnh kết quả S ở bước 1 với các
157,50

mặt nạ trong phương pháp Gradient dựa theo các toán tử như Sobel, Pixel

(x,y-1)

Difference.

(x-1,y-1)

(x+1,y-1)

22,50

Ở đây ta tiến hành nhân xoắn ảnh S với hai mặt nạ của phương pháp Sobel
(x-1,y)


(x+1,y+1)

1,y+1)

hai hướng là Sx và Sy, ta tiến hành tổng hợp hai kết quả đó để cho ra kết quả cuối

(S

(x+1,y)
x

1
0 
- 1

Sau khi tiến hành nhân xoắn ảnh theo hai hướng x và y ta được hai ảnh theo

S' =

(x,y)

-112,50

+ S 2y )

Hướng của biên θ như sau:

-22,50

-67,50


Điểm ảnh

Công thức tính hướng của đường biên θ nằm ở bước 2.

θ ≤ 22,50 hoặc θ > 157,50

θ = 00

(x-1,y) (x+1,y)

Giả sử ta có điểm biên đang xét là tại vị trí (x,y), ta có 8 điểm biên lân cận

22,50 < θ ≤ 67,50

θ = 450

(x-1,y-1) (x+1,y+1)

67,50 < θ ≤ 112,50

θ = 900

điểm biên này như hình dưới:

0

0

112,5 < θ ≤ 157,5