ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lưu Xuân Thế

NGHIÊN CỨU CÁC KỸ THUẬT DÒ BIÊN ÁP DỤNG
TRONG TRÍCH CHỌN CÁC BỘ PHẬN KHUÔN MẶT
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công nghệ thông tin

HÀ NỘI – 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lưu Xuân Thế

NGHIÊN CỨU CÁC KỸ THUẬT DÒ BIÊN ÁP DỤNG
TRONG TRÍCH CHỌN CÁC BỘ PHẬN KHUÔN MẶT


Lưu Xuân Thế

ii
TÓM TẮT
Kỹ thuật dò biên là bài toán mới chỉ xuất hiện cách đây không lâu, chỉ khoảng vài thập
niên, nhưng đã có rất nhiều nghiên cứu về nó. Các nghiên cứu ban đầu rất đơn giản, ảnh là
đen trắng và chỉ có một khuôn mặt chụp thẳng, sau này mở rộng ra cho ảnh màu, ảnh có
nhiều khuôn mặt với nhiều góc, môi trường xung quanh cũng đi từ đơn giản đến rất phức
tạp.
Từ khóa
: edge detection, edge filter.


Chương 2. CÁC KỸ THUẬT DÒ BIÊN 4
2.1 Quy trình phát hiện biên 4
2.2 Kỹ thuật phát hiện biên trực tiếp 4
2.2.1 Kỹ thuật Gradient 5
2.2.2 Toán tử la bàn 8
2.2.3 Kỹ thuật Laplace 10
2.2.4 Tách sườn theo ảnh Canny 11
2.2.5 Dò biên theo quy hoạch động 12
2.3 Kỹ thuật phát hiện biên gián tiếp 15
2.4 Một số phương pháp khác 15
16
2.5 Tổng kết 16
Chương 3. CÁC KỸ THUẬT DÒ BIÊN ĐƯỢC ÁP DỤNG 18
3.1 Các kỹ thuật được dùng 18
3.1.1 Lấy biên theo trục X 19
3.1.2 Lấy biên theo trục Y 21
3.1.3 Lấy biên theo Gradient 21
3.1.4 Lấy biên theo Thresholding 21
iv
3.1.5
Lấy biên theo Thinning 21
3.2 Chương trình và kết quả 23
3.3 Biến thành ảnh đa cấp xám 24
3.2.1 Lấy biên theo trục X 24
3.2.2 Lấy biên theo trục Y 25
3.2.3 Lấy biên theo Gradient 26
3.2.4 Lấy biên theo Thresholding 26

nhiều khuôn mặt với nhiều góc, môi trường xung quanh cũng đi từ đơn giản đến rất phức
tạp. Bài toán phát hiện biên nói chung và phát hiệ
n biên khuôn mặt nói riêng có rất nhiều
hướng để phát triển, nhưng có thể kể ra hai hướng chính sau:
- Thứ nhất là nhận diện (face recognition) một khuôn mặt, tức là giả sử ta có bức ảnh
một khuôn mặt, ta sẽ tìm một bức ảnh có khuôn mặt giống với khuôn mặt trong ảnh. Ứng
dụng của nó là truy tìm tội phạm, các hệ thống an ninh xác đinh dựa vào khuôn mặt.
- Thứ hai là xác định vị trí những khuôn mặt trong mộ
t bức ảnh (face detection), các
bức ảnh có thể có nhiều khuôn mặt, có kích thước và góc khác nhau. Ứng dụng của nó như
trong các máy chụp hình có khả năng nhận dạng mặt người để chỉnh độ sáng nơi đó.
Biên là vấn đề chủ yếu trong phân tích ảnh, vì các đặc điểm trích chọn trong quá trình
phân tích ảnh chủ yếu dựa vào biên. Một điểm được gọi 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 của ảnh.
Về mặt toán học người ta xem biên là nơi có sự thay đổi đột ngột về mức xám, trên cơ
sở đó người ta thường sử dụng hai phương pháp phát hiện biên sau:
- Phương pháp phát hiện biên trực tiếp
- Phương pháp phát hiện biên gián tiếp
Xuất phát từ thực tế đó, mục tiêu của luận v
ăn là nghiên cứu các phương pháp biểu
diễn biên, hệ thống hóa kiến thức về các phương pháp phát hiện biên, tìm hiểu các kỹ thuật
phân vùng ảnh, một bước trước trong quá trình dò biên và ứng dụng của nó trong xử lý ảnh
và xử lý ảnh văn bản là một trong những nhiệm vụ quan trọng trong việc tự động hóa công
việc văn phòng.
2
1.2 Bài toán nghiên cứu kỹ thuật dò biên áp dụng trong trích chọn
khuôn mặt

Chươ
ng này giới thiệu vào các kỹ thuật dò biên được áp dụng trong chương trình.
Bằng cách sử dụng hàm Gauss để làm trơn ảnh sau đó dùng các kỹ thuật tìm kiếm trực tiếp
3
để đưa ra 5 kiểu biên khác nhau với một bức ảnh nói chung và khuôn mặt trong chương
trình này.
Chương 4: Kết luận và hướng phát triển
Chương này tổng kết lại những gì đã đạt được và chưa đạt được. Từ đó nêu lên những
kết quả hướng tới, hướng nghiên cứu và phát triển tiếp theo.

Lọc nhiễu Làm nổi Định vị biên
trích chọn biên
5
Gradient trong gốc tọa độ góc (r, θ), với r là vector, θ là góc
2.2.1 Kỹ thuật Gradient
Theo định nghĩa về Gradient, nếu áp dụng nó vào xử lý ảnh, việc tính toán sẽ rất phức
tạp. Để đơn giản mà không mất tính chất của phương pháp Gradient, người ta sử dụng kỹ
thuật Gradient dùng cặp mặt nạ H1, H2 trực giao (theo 2 hướng vuông góc). Nếu định nghĩa
g1, g2 là Gradient theo hai hướng x, y tương ứng thì biên độ g(m, n) tại điểm (m, n) được
tính:

Đặt A
0
= g(m,n);

Để giảm độ phức tạp tính toán, A
0
được tính gần đúng như sau:

Mặt nạ Robert Toán tử (mặt nạ) Sobel
Toán tử Sobel được Duda và Hart [5] đặt ra năm 1973 với các mặt nạ tương tự như của
Robert nhưng cấu hình khác như sau:
H
2.3. Toán
t
ử 4 lân c
ậ
n
7

Hướng ngang (x) Hướng dọc (y)
Mặt nạ Prewitt
Toán tử Prewitt đưa ra năm 1970 có dạng:

Hướng ngang (x) Hướng dọc (y)
Mặt nạ đẳng hướng:
Một mặt nạ khác cũng được nêu như dưới đây gọi là mặt nạ đẳng hướng (Isometric).

Hướng ngang (x) Hướng dọc (y)
Toán tử 4-lân cận (4-Neighbour Operator).
Toán tử 4-lân cận được Chaudhuri và Chandor (1984) nêu ra trong đó mặt nạ có kích
thước 3x3 được thay cho mặt nạ 2x2 của toán tử Robert. Các mặt nạ này được cho:


đồng hồ: Đông, Đông – Nam, Nam, Nam – Tây, Tây, Tây – Nam, Tây – Bắc,
Bắc, Đông – Bắc; mỗi hướng lệch nhau 45 độ.

Toán tử la bàn Kirsh:
Có nhiều toán tử la bàn khác nhau. Ta xem xét toán tử la bàn Kirsh đặc trưng bởi tám
mặt nạ với kích thước 3x3 như sau: Ký hiệu 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 - Nếu lấy theo đạo hàm bậc hai của ảnh: ta có phương pháp Laplace
Hai phương pháp này gọi chung là phương pháp dò biên cục bộ.
Toán tử la bàn khác:
Ngoài toán tử la bàn Kirsh, một số toán tử la bàn khác sử dụng bộ mặt nạ 8 hướng khác
như:


thể tính gần đúng như sau:

Do đó:

Tóm lại: Kỹ thuật theo toán tử Laplace tạo đường biên mảnh (có độ rộng 1 pixel). Nhược
điểm của kỹ thuật này rất nhạy với nhiễu, do vậy đường biên thu được thường kém ổn định.
2.2.4 Tách sườn theo ảnh Canny
Bộ tách sườn ảnh theo Canny (1986) dựa trên cặp đạo hàm riêng bậc nhấtvới việc làm
sạch nhiễu. Mục này được để riêng vì đây là phương pháp tách đường biên khá phổ biến
được dùng theo toán tử đạo hàm. Như đã nói, phương pháp đạo hàm chịu ảnh hưởng lớn
của nhiễu. Phương pháp đạt hiệu quả cao khi xấp xỉ đạo hàm bậc nhất của Gauss.

Với f
x
, f
y
là đạo hàm riêng theo x,y của f.
12
Do vậy:

Lấy đạo hàm riêng theo x và y của G ta được: H2.5. Mô hình tính của phương pháp Canny.
Do bộ lọc Gauss là tách được, ta có thể thực hiện riêng biệt các tích chập theo x và y:

Từ đó ta có:

)| và θ(x
k
) Gradient biên độ và Gradient hướng ở đỉnh x
k
.
• α và β các hằng số không âm.
Đường bao tối ưu sẽ nhận được bằng cách nối các đỉnh x
k
, k=1, , N nào đó sao cho S(x
1
, ,
x
N
, N) đạt cực đại.
Định nghĩa hàm ф như sau:

Bây giờ ta có:

14
Lấy N = k.
Như vậy:

Với cách này, thay vì tìm tối ưu toàn cục phức tạp của S(x1, …,xN, N), ta tìm tối ưu
của N chặng theo tối ưu 2 biến. Trong mỗi chặng, với mỗi xk tìm tối ưu, ( k x k φ. Để dễ

2 hoặc giảm một số điểm cực trị cục bộ. Dưới đây sẽ trình bày một
cách tóm tắt các phương pháp đó.
¾ Tiếp cận theo mô hình mặt

Tư tưởng của phương pháp này là tại lân cận điểm cắt không (điểm biên), ảnh sau khi
lọc Laplace có thể được xấp xỉ bởi một đa thức bậc 3 theo hàng và cột. Đa thức thường
được dùng là đa thức Trebưchép với kích thước 3x3. Các đa thức này được định nghĩa như
sau:

Với mỗi điểm cắt không phát hiện tại P(x, y) trong ảnh đã được lọc bởi toán tử Laplace –
Gauss, Huertas và Medioni đã cho được tính theo công thức tính xấp xỉ:

Vấn đề là xác định các hệ số ai, i=1, 2, …, N-1. Nếu W là cửa số lọc tại điểm cắt không và
x, y, i, j trong cửa số; các hệ số a có thể được tính toán như một tổ hợp tuyến tính:

16
ở đây, IL-G(x, y) là ký hiệu ảnh đã được lọc bởi toán tử Laplace–Gauss. Các hệ số này có
thể nhận được bởi chập ảnh IL-G(x, y) với các nhân chập như trung bình có trọng số hay
một số nhân chập khác.
Các bước cài đặt phương pháp nhày có thể mô tả như sau:
9 Chập ảnh gốc kích thước NxM với toán tử Laplac –Gauss kích thước M2, ảnh thu
được gọi là IL-G.
9 Trích chọn các điẻm cắt không của
ảnh IL-G, ảnh kết quả ký hiệu là IZCR.
9 Với mỗi điểm cắt không trong IZCR, thực hiện một xấp xỉ với kích thước 3x3 để suy ra
các điểm cắt không theo cách gải tích.
9 Tạo một ảnh mới của các điểm cắt không kích thước nXxnY mà các đường bao được

Phương pháp dò biên trực tiếp có hiệu quả và ít bị tác động bởi nhiễu.
18
Chương 3. CÁC KỸ THUẬT DÒ BIÊN ĐƯỢC ÁP DỤNG
3.1 Các kỹ thuật được dùng
Biên là tập hợp các điểm tại đó hàm độ sáng của ảnh thay đổi cục bộ đột ngột, do đó để
phát hiện biên và tách biên ta dùng phép toán đạo hàm. Các phép toán đạo hàm thường
19
H3.1Đường cong Gauss chuẩn hóa với giá trị kỳ vọng μ và phương sai σ
2
. Những tham số
tương ứng là a = 1/(σ
2
π
), b = μ, c = σ
Tiếp đến ta sử dụng hàm dgauss với công thức như sau:
y = -x ae
-((x-b)^2)/2c^2
/ c
2
;
Với hàm Gauss có công thức được định nghĩa như sau:

y = e
-x^2/(2c^2)
/ (c 2
π
);
Hàm này chính là đạo hàm của hàm gauss với các tham số của hàm tương ứng là a =
1/(c 2
π
), b = 0, c = c. Và hàm d2dgauss:

h = d2dgauss(n1,sigma1,n2,sigma2,theta)
Hàm này tìm kiếm và trả lại biên 2D với ảnh có cỡ n1 * n2. Theta là góc xoay theo chiều