Xem mẫu
- BỘ CÔNG THƯƠNG
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO XỬ LÝ ẢNH
Đề Tài: Dò biên
Giáo viên hướng dẫn: Trần Hùng Cường
Nhóm sinh viên thực hiên: Nguyễn Văn Điệp
Nguyễn Huy Đông
Nguyễn Hồng Hiếu
- Phần 1 TỔNG QUAN VỀ BIÊN VÀ CÁC PHƯƠNG PHÁP PHÁT HIỆN
BIÊN
1.1. Vị trí của biên trong phân tích ảnh
Phân tích ảnh là một qua trình gồm nhiều giai đoạn. Đầu tiên là giai đoạn
tiền xử lý ảnh. Sau giai đoạn này, ảnh được tăng cường hay đ ược khôi ph ục đ ề
làm nồi các đặc tính ( feature extraction ), tiếp theo là phân đoạn ảnh
(segmentation) thành các phần tử. Thí dụ, như phân đoạn dựa theo biên, dựa theo
vùng,… Và tuỳ theo các ứng dựng, giai đoạn tiếp theo có thể là nhận d ạng ảnh (
phân thành các lớp có miêu tả) hay là giải thích và miêu t ả ảnh. Hình 1.1 mô t ả
tóm lược các bước của quá trình phân tích ảnh:
Ảnh đầu ra của
quá trình tiền XL
Hình 1.1. Các bước trong phân tích ảnh
Các đặc trưng của ảnh thường gồm: mật độ xám, phân bổ xác xuất, phân b ồ
không gian, biên ảnh. Các kỹ thuật phân đoạn ảnh chủ yếu dựa vào biên.
Do đó, biên có tầm quan trọng đặc biệt trong qua trình phân tích ảnh.
1.2. Biên và các kỹ thuật dò biên
Trong phần này chúng ta sẽ đề cập đến một số nội dung: khái niệm về
biên, phân loại các phương pháp phát hiện biên và qui trình phát hiện biên.
1.2.1. Khái niệm về biên
Biên là một vấn đề chủ yếu 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.
Một điểm ảnh có thể coi là điểm biên nếu ở đó có sự thay đổi đột ngột
về mức xám. Tập hợp các điểm biên tạo thành biên hay đường bao ảnh c ủa ảnh
(boundary).
Thí dụ, trong một ảnh nhị phân, một điểm có thể gọi là biên nếu đó là
điểm đen và có ít nhất một điểm trắng là lân cận.
Để hình dung tầm quan trọng của biên ta xét ví dụ sau: Khi người hoạ sĩ
vẽ một cái bàn gỗ, chỉ cần vài nét phác thảo về hình dáng như cái m ặt bàn, chân
- bàn mà không cần thêm các chi tiết khác, người xem đã có th ể nh ận ra nó là m ột
cái bàn. nếu ứng dụng của ta là phân lớp nhận diện đối tượng, thì coi nh ư
nhiệm vụ đã hoàn thành. Tuy nhiên nếu đòi hỏi thêm về các chi ti ết khác nh ư
vân gỗ hay màu sắc,…thì với chừng ấy thông tin là chưa đủ.
Nhìn chung về mặt toán học người ta coi điểm biên của ảnh là điểm có
sự biến đổi đột ngột về độ xám.Như vậy phát hiện biên một cách lý tưởng là
xác định được tất cả các đường bao trong các đối tượng. Định nghĩa toán học
của biên ở trên là cơ sở cho các kỹ thuật phát hiện biên. Điều quan trọng là sự
biến thiên mức xám giữa các ảnh trong một vùng thường là nh ỏ, trong khi đó
biến thiên mức xám của điểm vùng giáp ranh (khi qua biên) lại khá lớn.
1.2.2. Phân loại các kỹ thuật phát hiện biên
Xuất phát từ định nghĩa toán học của biên người ta thường sử dụng 2
phương pháp phát hiện biên sau:
1.2.2.1.Phương pháp phát hiện biên trực tiếp:
Phương pháp 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; nếu lấy đạo
hàm bậc hai ta có kỹ thuật Laplace. Hai phương pháp trên được gọi là ph ương
pháp dò biên cục bộ. ngoài ra người ta còn sử dụng phương pháp “đii theo
đường bao”: dựa vào nguyên lý qui hoạch hoạt động và đ ược g ọi là ph ương
pháp dò biên tổng thể.
1.2.2.2.Phương pháp gián tiếp:
Nếu bằng cách nào đấy , ta phân được ảnh thành các vùng thì đường phân
ranh giữa các vùng đó chính là biên. việc phân vùng ảnh thường dựa vào kết cấu
(texture) bề mặt của ảnh.
Cũng cần lưu ý rằng, kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối
ngẫu của nhau. Thực vậy, dò biên để thực hiện phân lớp đối tượng và một khi
đã phân lớp xong có nghĩa là đã phân vùng được ảnh. Và ng ược l ại, khi phân
vùng, ảnh đã phân lập được thành các đối tượng, ta có th ể phát hi ện đ ược biên.
Phương pháp dò biên trực tiếp tỏ ra khá hiệu quả vì ít chịu ảnh hưởng của
nhiễu. song nếu sự biến thiên độ sáng không đột ngột, phương pháp này lại kém
hiệu quả. Phương pháp dò biên gián tiếp tuy có khó cài đặt song l ại áp d ụng khá
tốt khi sự biến thiên độ sáng nhỏ.
1.2.3. Qui trình phát hiện biên trực tiếp
b1) Khử nhiễu ảnh
Vì ảnh thu nhận thường có nhiễu, nên bước đầu tiên là phải khử nhiễu.
việc khử nhiễu được thực hiện bằng các kỹ thuật khử nhiễu khác nhau.
- b2) Làm nổi biên
Tiếp theo là làm nổi biên bởi các toán tử đạo hàm
b3) Định vị điểm biên
Vì các kỹ thuật làm nổi biên có hiệu ứng phụ là tăng nhiễu , do vậy sẽ có
một số điểm biên giả cần loại bỏ.
b4) liên kết và trích chọn biên.
Như đã nói, phát hiện biên và phân vùng ảnh là một bài toán đ ối ngẫu. vì
thế cũng có thể phát hiện biên thông qua việc phân vùng ảnh.
1.3. Một số phương pháp phát hiện biên cục bộ
1.3.1. Phương pháp gradient
Phương pháp gradient là phương pháp dò biên cục bộ dựa vào cực đ ạii
của đạo hàm. 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 theo hai hướng x và y . các thành ph ần c ủa
gradient được tính bởi:
df(x,y) f(x+dx,y) – f(x,y)
= fx ≈
dx dx
df(x,y) f(x,y+dy) – f(x,y)
= fy ≈
dy dy
với dx là khoảng cách giữa các điểm theo hướng x ( khoảng các tính bằng s ố
điểm) và tương tự với dy. Trên thực tế, người ta hay dùng với
dx = dy = 1
Trong kỹ thuật gradient, người ta chia thành 2 kỹ thuật (do dùng 2 toán t ử
khác nhau): kỹ thuật gradient và kỹ thuật la bàn. kỹ thuật gradient dùng toán t ử
gradient lấy đạo hàm theo hai hướng; còn kỹ thuật la bàn lấy đạo hàm theo 8
hướng chính: Bắc, Nam, Đông ,Tây và Đông Bắc, Tây Bắc, Đông Nam, Tây
Nam.
1.3.1.1.Kỹ thuật gradient
Kỹ thuật này sử dụng một cặp mặt nạ H 1 và H2 trực giao ( theo 2 hướng
vuông góc). Nếu định nghĩa g1,g2 là gradient tương ứng theo 2 hướng x và y, thì
biên độ của gradient, ký hiệu là g tại điểm (m,n) được tính theo công thức:
A0 = g(m,n) = √ g² 1(m,n) + g22(m,n) (1.2)
θr(m,n) = tan-1g2(m,n)/ g1(m,n) (1.3)
- Chú ý: để giảm tính toán, công thức 1-2 được tính gần đúng bởi:
A0 = | g1(m,n) | + | g2(m,n) |
Các toán tử đạo hàm được áp dụng là khá nhiều. ở đây ta chỉ xét một số
toán tử tiêu biểu: toán tử Robert, Sobel, Prewitt…
Trước tiên chúng ta xét toán tử Robert. Toán tử này do Robert đ ề xu ất vào
năm 1965. Nó áp dụng trực tiếp của các công thức đạo hàm tại điểm (x,y). với
mỗi điểm ảnh I(x,y) của I, đạo hàm theo x, theo y được ký hi ệu t ương ứng b ởi
gx, gy được tính:
gx = I(x +1,y) – I(x,y)
gy =I(x,y+1) – I(x,y)
điều này tương đương với việc chập ảnh với 2 mặt nạ H1 và H2:
0 1 -1 0
H1 = H2 =
-1 0 0 -1
Ta gọi H1,H2 là mặt nạ Robert.
Trong trường hợp tổng quát, giá trị gradient biên độ g và gradient hướng θr
được tính bởi công thức 1.2 và 1.3. Thường để giảm thời gian tính toán, người ta
còn tính gradient theo các chuẩn sau:
A1 = | g1(m,n) + g2(m,n) |
hoặc
A2 = max( | g1(m,n) | , | g2(m,n) |)
Cần lưu ý rằng, do lạm dụng về ngôn từ, tuy ta l ấy đạo hàm c ủa ảnh
nhưng thực ra chỉ là mô phỏng và xấp xỉ đạo hàm bằng kỹ thuật nhân ch ập do
ảnh số là tín hiệu rời rạc, do vậy đạo hàm không tồn tại.
Trong kỹ thuật Sobel và prewtt người ta sử dụng 2 mặt nạ:
-1 0 1 -1 -1 -1
H1 = -1 0 1 H2 = 0 0 0
-1 0 1 1 0 1
- Ngang (hướng x) Dọc(hướng y)
a) mặt nạ Sobel
-1 0 1 -1 -2 -1
H1 = -2 0 2 H2 = 0 0 0
-1 0 1 1 2 1
Ngang (hướng x) Dọc(hướng y)
b) mặt nạ Prewitt
-1 0 1 -1 - -1
H1 = - 0 H2 = 0 0 0
-1 0 1 1 1
Ngang (hướng x) Dọc(hướng y)
c) mặt nạ đẳng hướng (Isometric)
Gradient được tính xấp xỉ công thức
Gx=Hx I và Gy=Hy I (Hx nhân chập với I, Hy nhân chập với I)
Thực tế cho thấy rằng các toán tử Sobel và Prewitt tốt hơn toán t ử Sobel b ởi
chúng ít nhậy cảm với nhiễu.
1.3.1.2.Kỹ thuật La bàn
Về phương pháp kỹ thuật này tương tự kỹ thuật Gradient. Tuy
nhiên,điểm khác, kỹ thuật Gradient chỉ lấy đạo hàm theo 2 hướng. còn kỹ thu ật
la bàn lấy đạo hàm theo 8 hướng chính: Bắc, Nam, Đông ,Tây và Đông B ắc, Tây
Bắc, Đông Nam, Tây Nam. Bằng cách sử dụng 8 mặt nạ cho 8 hướng khác
nhau.
1.3.2. Phương pháp Laplace
- Các phương pháp đánh giá Gradient ở trên làm việc khá tốt khi mà độ sáng
thay đổi rõ nét. Khi mức sáng thay đổi ch ậm, miền chuy ển ti ếp tr ải r ộng,
phương pháp cho hiệu quả hơn đó là sử dụng phương pháp đạo hàm bậc hai gọi
là phương pháp Laplace. Kết quả nghiên cứu cho thấy phương pháp Gradient rất
nhậy cảm với nhiễu và thường tạo nên biên kép. Toán tử Laplace dùng nhi ều
kiểu mặt nạ khác nhau để xấp xỉ đạo hàm bậc hai. Dưới đây là 3 kiểu mặt nạ
hay dùng.
0 -1 0 -1 -1 -1 1 -2 1
H2
H1= -1 4 -1 -1 8 -1 H2= -2 8 -2
=
0 -1 0 -1 -1 -1 1 -2 1
Kỹ thuật laplace cho đường biên mảnh, tức là đường biên có đ ộ rộng b ằng
một pixel. Tuy nhiên, kỹ thuật này rất nhạy cảm với nhiễu vì đạo hàm bậc hai
thường không ổn định.
1.4. Các phương pháp do biên gián tiếp (phân vùng ảnh)
1.4.1. Giới thiệu
Như phần trên đã trình bày, Nếu bằng cách nào đấy, ta phân được ảnh thành
các vùng thì đường phân ranh giữa các vùng đó chính là biên. việc phân vùng ảnh
thường dựa vào kết cấu (texture) bề mặt của ảnh.
Kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối ngẫu của nhau. Th ực
vậy, dò biên để thực hiện phân lớp đối tượng và một khi đã phân lớp xong có
nghĩa là đã phân vùng được ảnh. Và ngược lại, khi phân vùng, ảnh đã phân lập
được thành các đối tượng, ta có thể phát hiện được biên.
Do vậy, Phân vùng ảnh là bước then chốt trong xử lý ảnh. Giai đoạn này
nhằm phân tích ảnh thành các thành phần có cùng tính chất nào đấy dựa vào biên
hay những vung liên thông. Tiêu chuẩn để xác định các vùng liên thông có th ể là
cùng mức xám, cùng màu, v..v… Vùng ảnh là một thuộc tính quan tr ọng c ủa
ảnh. Nói đến vùng ảnh là nói đến kết cấu bề mặt. Đ ường bao quanh m ột vùng
ảnh gọi là biên ảnh.
- Phần 2 CHƯƠNG TRÌNH ỨNG DỤNG
2.1. Giới thiệu
Phần 1 đã trình bày khái quát về vai trò và tầm quan trọng của biên trong quá
trình xử lý ảnh. Đồng thời, phần 1 cũng đã trình bày khái niệm về biên ảnh cũng
như các phương pháp dò biên của ảnh nhị phân trong máy tính.
Để áp dụng lý thuyết đã trình bày ở phần 1, Phần này s ẽ gi ới thi ệu m ột
chương trình ứng dụng tìm biên của ảnh. Chương trình này áp dụng các kỹ
thuật do biên trực tiếp là kỹ thuật Gradient và Laplace. Trong k ỹ thu ật Gradient,
các toán tử Sobel và Prewitt được sử dụng.
Tiếp đó chương trình cũng giới thiệu một phương pháp dò biên gián ti ếp
thông qua việc phân vùng ảnh.
Chương trình được viết trên ngôn ngữ Visual C++ 6.0.
2.2. Các chức năng trong chương trình
Chương trình bao gồm các chức năng chính sau:
Đọc một ảnh nhị phân: ảnh có thể là đen trắng, ảnh màu (16 màu hoặc
256 màu) dạng bitmap (*.bmp).
Lưu ảnh: lưu ảnh đã biến đổi ra file
Dò biên ảnh bao gồm các chức năng sau
o Theo kỹ thuật Gradient: bằng cách sử dụng toán tử Sobel và
Prewitt.
o Theo kỹ thuật Laplace: sử dụng toán tử Laplace-H2.
o Dò biên gián tiếp theo phân vùng ảnh: dò biên theo màu của ảnh.
2.3. Chi tiết các chức năng dò biên và thuật toán
2.3.1. Dò biên theo kỹ thuật Gradient
Theo như phần lý thuyết đã trình bày, kỹ thuật Gradient dò biên theo 2 h ướng x
và y bằng cách sử dụng hai mặt nạ nhân chập theo hai hướng
Chương trình sử dụng hai toán tử là Sobel và Prewitt như sau.
-1 0 1 -1 -1 -1
H1 = -1 0 1 H2 = 0 0 0
-1 0 1 1 0 1
- Ngang (hướng x) Dọc(hướng y)
a) mặt nạ Sobel
-1 0 1 -1 -2 -1
H1 = -2 0 2 H2 = 0 0 0
-1 0 1 1 2 1
Ngang (hướng x) Dọc(hướng y)
b) mặt nạ Prewitt
Giả sử Gx và Gy là 2 ma trận điểm ảnh thu được sau khi nhân ch ập với 2 mặt
nạ theo hai hướng tương ứng. Ma trận điểm ảnh G được tính xấp xỉ theo công
thức sau:
G=|Gx| + |Gy|
Thuật toán dò biên theo phương pháp Gradient như sau:
Đầu vào: ma trận ảnh cần tìm biên:
mặt nạ I1 và I2
Đầu ra: Một ma trận ảnh (chứa các đường biên được tìm thấy).
Giải thuật
// Gradient Algorithm
For (mỗi điểm ảnh của ảnh)
if(Nếu điểm ảnh nẳm trên đường viền ảnh)
Gán giá trị các điểm ảnh trên đường viền ảnh =0 (hoặc b ằng
màu nền ảnh).
else
{
- Tính xấp xỉ Gradient theo chiều x (Gx): nhân ch ập với
mặt nạ I1
-Tính xấp xỉ Gradient theo chiều y (Gy): nhân ch ập v ới
mặt nạ I2
-Tính giá trị điểm ảnh theo công thức xấp xỉ G:
- G=|Gx|+ |Gy|
- Nếu giá trị điểm ảnh lớn hơn chỉ số màu của ảnh thì
gán giá trị ảnh là giá trị màu lớn nhất.
}
Để dễ hiểu, phần dưới đây sẽ minh hoạ thêm về giải thuật này:
Ma trận ảnh vào Mặt nạ
a11 a12 a13 .... a1n m11 m12 m13
m21 m22 m23
a21 a22 a23 .... a2n
m31 m32 m33
a31 a32 a33 .... a3n
.. ..
.. ..
Ma trận ảnh ra sau khi nhân chập
b11 b12 b13 .... b1n
b21 b22 b23 .... b2n
b31 b32 b33 .... b3n
.. ..
.. ..
- Trong đó:
b22=(a11*m11)+ (a12*m12)+ (a12*m13)+ (a21*m21) + (a22*m22) + (a23*m23)
+ (a31*m31)+ (a32*m32)+ (a33*m33).
Các giá trị nằm trên đường viền được gán =0 (hay giá trị màu nền).
(b11,b12,...b1n,b11....bn1,b1n...bnn, bn1...bnn)
Đây là công thức tính Gx và Gy
Để tính giá trị điểm ảnh đầu ra, sử dụng công thức: G=|Gx|+ |Gy|
2.3.2. Phương pháp dò biên theo kỹ thuật Laplace
Kỹ thuật Laplace dò biên theo cách tính xấp xỉ đạo hàm bậc hai dựa trên
một mặt nạ. Chương trình sử dụng mặt nạ H2 trong cách dò biên theo k ỹ thu ật
Laplace.
-1 -1 -1
H2= -1 8 -1
-1 -1 -1
Gọi G là ma trận điểm thu được sau khi nhân ch ập ma tr ận đi ểm ảnh (c ủa ảnh
cần tìm biên)với mặt nạ H2.
G chính là ma trận điểm ảnh chứa các đường biên cần tìm.
Thuật toán dò biên theo phương pháp Gradient như sau:
Đầu vào: ma trận ảnh cần tìm biên:
mặt nạ H2
Đầu ra: Một ma trận ảnh (chứa các đường biên được tìm thấy).
Giải thuật
// Laplace Algorithm
For (mỗi điểm ảnh của ảnh)
if(Nếu điểm ảnh nẳm trên đường viền ảnh)
Gán giá trị các điểm ảnh trên đường viền ảnh =0 (hoặc b ằng
màu nền ảnh).
else
{
- Tính xấp xỉ Laplace G: nhân chập với mặt nạ I1
- - Nếu giá trị điểm ảnh lớn hơn chỉ số màu của ảnh thì
gán giá trị ảnh là giá trị màu lớn nhất.
}
2.3.3. Phương pháp dò biên gián tiếp
Dựa trên kỹ thuật phân vùng ảnh, Phương pháp này dò biên theo sự thay
đổi mức xám màu của ảnh. Nếu những điểm ảnh nào có cùng màu hoặc có màu
khác nhưng khoảng cách màu nằm trong phạm vi cho phép, đồng th ời nằm kề
nhau sẽ tạo thành một vùng.
Định nghĩa khoảng cách màu:
Khoảng cách màu là một khái niệm để chỉ sự khác nhau về giá trị màu
của các điểm ảnh.
Giả sử a và b là 2 giá trị màu của 2 đi ểm ảnh. Kho ảng cách màu d c ủa
a và b được tính như sau:
d(a,b)=|Ra-Rb| + |Ga-Gb| + |Ba-Bb|
Trong đó Ra: là giá trị màu đỏ tại điểm ảnh
Ga: là giá trị màu xanh (green)tại điểm ảnh
Ba: là giá trị màu xanh da trời (blue) tại điểm ảnh.
Nếu khoảng cách màu d=0 thì 2 điểm ảnh đó có cùng màu.
Đường biên giữ các vùng chính là các đường biên cần tìm.
Thuật toán tìm đường biên dựa trên sự biến thiên giá tr ị màu c ủa
các điểm ảnh.
Đầu vào: Ma trận điểm ảnh, khoảng cách màu tối thiểu
Đầu ra: Ma trận điểm ảnh mới (chứa các đường biên tìm thấy).
Giải thuật:
For (mỗi điểm ảnh của ảnh)
{
- Tính khoảng cách màu của điểm ảnh với các điểm ảnh lân
cận: Tính theo 8 hướng của điểm ảnh
if(Nếu có một khoảng cách màu lớn hơn khoảng cách màu
cho phép)
{
- Ghi nhận điểm ảnh này là một điểm biên mới.
}
}
Tài Liệu Tham Khảo
- 1. Luận Văn Tốt nghiệp NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP
2. PHÁT HIỆN BIÊN VÀ ỨNG DỤNG
3. Giáo Trình Xử Lý Ảnh…………………………………ĐH Back Khoa
4. Giáo Trình Xử Lý Ảnh…………………………………ĐH Thái Nguyên
5. Và 1 số tài liệu trên mạng khác
6. Chương trình tham khảo
nguon tai.lieu . vn