ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄN QUANG SƠN
NGHIÊN CỨU MỘT SỐ PHƯƠNG
PHÁP

PHÁT HIỆN BIÊN
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS NGÔ QUỐC TẠO
Thái Nguyên - 2008
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
M Ở ĐẦ U 7
CH ƯƠ NG

I:

T Ổ NG

QUAN

V Ề

c ơ

b ả n

trong

x ử

lý

ả nh

10
1.1.3. M ộ t

s ố

v ấ n

đề

c ơ

b ả n

trong

x ử

lý


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


c ơ

b ả n

23
1.3.2. Vai

trò

c ủ a

biên

trong

nh ậ n

d ạ ng

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

28
2.1. Phân

lo ạ i

các


phát

hi ệ n

biên

gián

ti ế p

28
2.1.3. Quy

trình

phát

hi ệ n

biên

29
2.2. K ỹ

thu ậ t

phát

hi ệ n


Prewitt

33
2
2.2.5. Toán tử (mặt nạ) Sobel 33
2.2.6. Toán tử Frie-Chen

34
2.2.7. Toán tử Boxcar

34
2.2.8. Toán tử Truncated Pyramid

35
2.3 Các toán tử la bàn

36
2.3.1. Toán tử la bàn Kirsh

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

38
2.3.3. Robinson 3 - Level

39
2.3.4. Robinson 5 - Level

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

62
4.1. Phương pháp phát hiện biên dựa vào kỹ thuật Gradient

62
4.2. Phương pháp đạo hàm bậc nhất và phương pháp đạo hàm bậc hai

66
4.3. Đánh giá nhận xét về phương pháp Canny

69
4.4. Các phương pháp phát hiện biên (phương pháp Gadient, phương pháp

Laplace,
phương pháp Canny)

71
4.5. Đánh giá nhận xét về phương pháp Wavelet

73
KẾT LUẬN

75
TÀI LIỆU THAM KHẢO

76
LỜI CẢM ƠN
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ệ
thông tin và Khoa công nghệ thông tin - Đại học Thái Nguyên đã quan tâm tổ chức
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
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

Hình 3.1: Đạo hàm hàm Gauss theo hai hướng (x,y) 48
Hình 3.2: Hình mô tả các điểm biên lân cận 50
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
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 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

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,
tập hợp nhiều điểm biên tạo nên một đường bao quanh ảnh (đường biên). Nhờ có
đường biên mà chúng ta có thể phân biệt giữa đối tượng và nền, phân biệt giữa các
vùng khác nhau và định vị được đối tượng từ đó mà nhận dạng đối tượng. Đây là cơ
sở quan trọng trong việc ứng dụng phương pháp này vào thực tiễn của cuộc sống,
đặc biệt là trong điều kiện đất nước ta đang từng bước phát triển và đi lên nên việc
nghiên cứu các ứng dụng vấn đề này cần được quan tâm và phát triển.
Xuất phát từ thực tế đó, luận văn lựa chọn đề tài " Nghiên cứu một số phương
pháp phát hiện biên". Mục đích chính của đề tài là hệ thống hóa kiến thức về các
phương pháp phát hiện biên, từ các kỹ thuật dò biên cài đặt chương trình để đưa ra
các nhận xét, so sánh, đánh giá về các phương pháp phát hiện biên. Qua đó có cái
nhìn tổng quát về các phương pháp phát hiện biên.
Ngoài phần mở đầu và kết luận luận văn được chia làm 4 chương, nội dung cụ
thể của các chương như sau:
Chương I: Tổng quan về xử lý ảnh và biên
Trong chương này trình bày sơ lược về xử lý ảnh, giới thiệu các bước xử lý
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.
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ý.

- 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).
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:
Phân đoạn
ảnh
Biểu diễn và
mô tả
Tiền xử

lý ảnh
CƠ SỞ

TRI THỨC
Nhận dạng và
nội suy
Thu nhận ảnh
(Scaner, sensor,
camera)
Hình 1.2: Các bước cơ bản trong quá trình xử lý ảnh
1.1.2.1 Thu nhận ảnh
Đây là bước đầu tiên trong quá trình xử lý ảnh. Để thực hiện điều này, ta cần
có bộ thu ảnh và khả năng số hoá những tín hiệu liên tục được sinh ra bởi bộ thu
ảnh đó. Bộ thu ảnh ở đây có thể là máy chụp ảnh đơn sắc hay màu, máy quét ảnh,
máy quay Trong trường hợp bộ thu ảnh cung cấp chưa phải là dạng số hoá ta còn
phải chuyển đổi hay số hoá ảnh. Quá trình chuyển đổi ADC (Analog to Digital

* Nắn chỉnh hình học: Những biến dạng hình học thường do các thiết bị điện

tử và
quang học gây ra. Do đó, phương pháp hiệu chỉnh ảnh dựa trên mô hình được

mô
tả dưới dạng phương trình biến đổi ảnh biến dạng f(x,y) thành ảnh lý tưởng
f(x',y') như sau:

x'
=
h
x
(x, y)


y'= h
y
(x, y)
Trong đó h
x
, h
y
là các phương trình tuyến tính (biến dạng do phối cảnh) hay
bậc hai (biến dạng do ống kính camara).
1.1.2.3 Phân đoạn ảnh
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
dạng chữ (hoặc mã vạch) trên phong bì thư cho mục đích phân loại bưu phẩm, cần
chia các câu, chữ về địa chỉ hoặc tên người thành các từ, các chữ, các số (hoặc các

từng ký tự giúp phân biệt ký tự này với ký tự khác.
b) Mô tả
Ảnh sau khi số hoá sẽ được lưu vào bộ nhớ, hoặc chuyển sang các khâu tiếp
theo để phân tích. Nếu lưu trữ ảnh trực tiếp từ các ảnh thô, đòi hỏi dung lượng bộ
nhớ cực lớn và không hiệu quả theo quan điểm ứng dụng và công nghệ. Thông
thường, các ảnh thô đó được đặc tả (biểu diễn) lại (hay đơn giản là mã hoá) theo các
đặc điểm của ảnh được gọi là các đặc trưng ảnh như: biên ảnh, vùng ảnh. Một số

phương pháp biểu diễn thường dùng:
• Biểu diễn bằng mã chạy: Phương pháp này thường biểu diễn cho vùng ảnh

và áp
dụng cho ảnh nhị phân.
• 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.
• 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.
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.
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ữ
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ó
nhiều cách phân loại khác nhau về ảnh. Theo lý thuyết về nhận dạng, các mô hình
toán học về ảnh được phân theo hai loại nhận dạng ảnh cơ bản:
- Nhận dạng theo tham số.
- Nhận dạng theo cấu trúc.

tròn v.v )
- Đặc điểm biên và đường biên: Đặc trưng cho đường biên của đối tượng và

do
vậy rất hữu ích trong việc trích trọn các thuộc tính bất biến được dùng khi nhận
dạng đối tượng. Các đặc điểm này có thể được trích chọn nhờ toán tử Gradient, toán
tử la bàn, toán tử Laplace, toán tử “chéo không” (zero crossing)
1.1.3. Một số vấn đề cơ bản trong xử lý ảnh
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,
ả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
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
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
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:
Picture Element) hay gọi tắt là Pixel. Trong khuôn khổ ảnh hai chiều, mỗi pixel ứng
với cặp tọa độ (x, y).
Điểm ảnh (Pixel) là một phần tử của ảnh số tại toạ độ (x, y) với độ xám hoặc
màu nhất định. Kích thước và khoảng cách giữa các điểm ảnh đó được chọn thích
hợp sao cho mắt người cảm nhận sự liên tục về không gian và mức xám (hoặc màu)
của ảnh số gần như ảnh thật. Mỗi phần tử trong ma trận được gọi là một phần tử
ảnh.
1.1.3.2 Độ phân giải của ảnh
Độ phân giải (Resolution) của ảnh là mật độ điểm ảnh được ấn định trên một
ảnh số được hiển thị.
Khoảng cách giữa các điểm ảnh phải được chọn sao cho mắt người vẫn thấy
đượ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 độ
phân bố, đó chính là độ phân giải và được phân bố theo trục x và y trong không gian
hai chiều.
1.1.3.3 Mức xám của ảnh
Một điểm ảnh (Pixel) có hai đặc trưng cơ bản là vị trí (x, y) của điểm ảnh và

* Giả sử có điểm ảnh p tại toạ độ (x, y). p có 4 điểm lân cận gần nhất theo
chiều đứng và ngang (có thể coi như lân cận 4 hướng chính: Đông, Tây, Nam, Bắc).
{(x-1, y); (x, y-1); (x, y+1); (x+1, y)} = N
4
(p)
trong đó: số 1 là giá trị logic; N
4
(p) tập 4 điểm lân cận của p.
Đô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) (x+1,y+1)
Hình 1.3: Lân cận các điểm ảnh của tọa độ (x,y)
* Các lân cận chéo: Các điểm lân cận chéo N
P
(p) (Có thể coi lân cận chéo là 4
hướng: Đông-Nam, Đông-Bắc, Tây-Nam, Tây-Bắc)
N
p
(p) = { (x+1, y+1); (x+1, y-1); (x-1, y+1); (x-1, y-1)}
* Tập kết hợp: N
8
(p) = N
4
(p) + N
P
(p) là tập hợp 8 lân cận của điểm ảnh p.
* Chú ý: Nếu (x, y) nằm ở biên (mép) ảnh, một số điểm sẽ nằm ngoài ảnh.
b) Các mối liên kết điểm ảnh

q(s,t) được định nghĩa như sau:
D
e
(p, q) = [(x - s)
2
+ (y - t)
2
]
1/2
Khoảng cách khối: Khoảng cách D
4
(p, q) được gọi là khoảng cách khối đồ thị
và được xác định như sau:
D
4
(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ừ
tâm điểm ảnh đến tâm điểm ảnh q khác.
Khoảng cách D
8
(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:
D
8
(p,q) = max (| x-s | , | y-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
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 nhân thường phân bố khắp ảnh và ảnh thu được sẽ biểu diễn với công
X
qs
= X
gốc
* η
- Nhiễu xung
Nhiễu xung thường gây đột biến tại một số điểm ảnh.
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ộ
lọc thích hợp. Với nhiễu cộng và nhiễu nhân ta dùng các bộ lọc thông thấp, trung
bình và lọc đồng hình (Homomorphie), với nhiễu xung ta dùng lọc trung vị, giả
trung vị, lọc ngoài (Outlier).
a) Lọc trung bình không gian
Với lọc trung bình, mỗi điểm ảnh được thay thế bằng trung bình trọng số của
các điểm lân cận và được định nghĩa như sau:
v(m, n) =
∑
∑
a(k,l)y(m − k, n − l)
( k ,l)∈W
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
sẽ có dạng:
v(m, n) =
1
∑
N
Với : y(m,m): ảnh đầu vào
v(m,n): ảnh đầu ra




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 7


I =

6 6
3 7 1

1 7

1 8 3


1

2


Ảnh số thu được bởi lọc trung bình Y = H⊗I có dạng:
11
5 7
1


0
1
0



0


H
b
=

1

1

(b + 2)
2

b


b 1

2

b


m, n
]
N
w
Y
[
m, n
]
=
1
N
w
k ,l∈W
∑
∑
X
qs k
,l∈W
σ
2
(m − k, n − l) +
n
N
w

23
26 31 19
16



b
n
Như vậy, nhiễu cộng trong ảnh đã giảm đi N
w
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
gồm ảnh gốc nhân với hệ số nhiễu. Gọi
và η(m,n) là nhiễu như vậy:
X(m, n) là ảnh thu được, X(m,n) là ảnh gốc
X(m,n) = X(m, n) * η(m,n)
Lọc đồng hình thực hiện lấy logarit của ảnh quan sát. Do vậy ta có kết quả sau:
Log(X(m, n)) = log( X ( ,m n) ) + log( η(m, n))
Rõ ràng, nhiễu nhân có trong ảnh sẽ bị giảm. Sau quá trình lọc tuyến tính, ta
chuyển về ảnh cũ bằng phép biến đổi hàm e mũ.
1.2.2. Làm trơn nhiễu bằng lọc phi tuyến
Các bộ lọc phi tuyến cũng hay được dùng trong kỹ thuật tăng cường ảnh.
Trong kỹ thuật này, người ta dùng bộ lọc trung vị, giả trung vị, lọc ngoài. Với lọc
trung vị, điểm ảnh đầu vào sẽ được thay thế bởi trung vị các điểm ảnh còn lọc giả
trung vị sẽ dùng trung bình cộng của 2 giá trị “trung vị” (trung bình cộng của max
và min).
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 h
LP
(m, n) biểu diễn bộ
lọc thông thấp.
FIR (Finite Impulse Response) thì bộ lọc thông cao h
HP
(m, n) có thể được định
nghĩa:
h
HP
(m, n) = δ(m, n) - h
LP
(m, n)
Bộ lọc dải thông có thể định nghĩa như sau:
H
HP
(m, n)= h
L1
(m, n) – h
L2
(m, n)
với h
L1
và h


(3)

-
2
5 - 2



- 1
-1 -
1




0 -1 0




1 -
2
1


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).