Luận văn Thạc sĩ Khoa học máy tính: Phương pháp phát hiện mặt người sử dụng đặc trưng HOG

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

ĐINH QUANG HUY PHƯƠNG PHÁP PHÁT HIỆN MẶT NGƯỜI SỬ DỤNG ĐẶC TRƯNG HOG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên, 2018

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

ĐINH QUANG HUY PHƯƠNG PHÁP PHÁT HIỆN MẶT NGƯỜI SỬ DỤNG ĐẶC TRƯNG HOG Chuyên ngành: Khoa học máy tính

Mã số: 8480101

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: TS. NGUYỄN TOÀN THẮNG

Thái Nguyên, 2018

1

LỜI CAM ĐOAN

Tên tôi là: Đinh Quang Huy

Sinh ngày: 06/08/1981

Học viên lớp cao học CHK15A - Trường Đại học Công nghệ Thông tin và

Truyền thông - Đại học Thái Nguyên.

Hiện đang công tác tại: Sở Giáo dục và Đào tạo tỉnh Thái Nguyên.

Xin cam đoan: Đề tài “Phương pháp phát hiện mặt người sử dụng đặc trưng

HOG” do TS. Nguyễn Toàn Thắng hướng dẫn là công trình nghiên cứu của riêng

tôi. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng.

Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng như nội

dung trong đề cương và yêu cầu của thầy giáo hướng dẫn. Nếu sai tôi hoàn toàn

chịu trách nhiệm trước hội đồng khoa học và trước pháp luật.

Thái Nguyên, ngày tháng năm 2018

Tác giả luận văn

Đinh Quang Huy

2

Sau một thời gian nghiên cứu và làm việc nghiêm túc, được sự động viên,

LỜI CẢM ƠN

giúp đỡ và hướng dẫn tận tình của Thầy giáo hướng dẫn TS. Nguyễn Toàn Thắng,

luận văn với Đề tài “Phương pháp phát hiện mặt người sử dụng đặc trưng

HOG”.

Tôi xin bày tỏ lòng biết ơn sâu sắc đến:

Thầy giáo hướng dẫn TS. Nguyễn Toàn Thắng đã tận tình chỉ dẫn, giúp đỡ

tôi hoàn thành luận văn này.

Phòng đào tạo Sau đại học Trường Đại học Công nghệ Thông tin và Truyền

thông đã giúp đỡ tôi trong quá trình học tập cũng như thực hiện luận văn.

Sở Giáo dục và Đào tạo tỉnh Thái nguyên nơi tôi công tác đã tạo điều kiện tối

đa cho tôi thực hiện khóa học này.

Tôi xin chân thành cảm ơn bạn bè, đồng nghiệp và gia đình đã động viên,

khích lệ, tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, thực hiện và hoàn

thành luận văn này.

Thái Nguyên, ngày 17 tháng 6 năm 2018

Tác giả luận văn

Đinh Quang Huy

3

MỤC LỤC

Trang

LỜI CAM ĐOAN ...................................................................................................... 1

LỜI CẢM ƠN ............................................................................................................ 2

MỤC LỤC .................................................................................................................. 3

DANH MỤC CÁC TỪ VIẾT TẮT .......................................................................... 5

DANH MỤC HÌNH ẢNH ......................................................................................... 6

DANH MỤC BẢNG BIỂU ....................................................................................... 8

MỞ ĐẦU .................................................................................................................... 9

1. Mục tiêu của đề tài ..................................................................................... 10

2. Hướng nghiên cứu của đề tài ..................................................................... 11

3. Ý nghĩa khoa học và thực tiễn của đề tài ................................................. 11

CHƯƠNG I. TỔNG QUAN VỀ PHÁT HIỆN MẶT NGƯỜI TRONG ẢNH VÀ

VIDEO .............................................................................................. 12

1.1. Phát hiện điểm ......................................................................................... 12

1.2. Phép trừ nền ............................................................................................. 14

1.3. Phân vùng ................................................................................................. 18

1.3.1. Mean-Shift Clustering .................................................................... 18

1.3.2. Phân đoạn Hình ảnh Sử dụng Đồ thị-Cuts. ................................... 19

1.3.3. Đường nét hoạt động ..................................................................... 20

1.4. Học có giám sát ........................................................................................ 21

1.5. Thuật toán Viola–Johns và các vấn đề liên quan. ................................ 23

1.5.1. Thuật toán Viola–Johns ................................................................. 23

1.5.2. Đánh Giá Thuật Toán Viola-Jones ................................................ 24

4

1.6. Adaboost ................................................................................................... 26

1.7. Đặc trưng Haar wavelet .......................................................................... 30

CHƯƠNG 2. ĐẶC TRƯNG HOG VÀ CÁCH SỬ DỤNG HOG KẾT HỢP VỚI

SVM TRONG PHÁT HIỆN MẶT NGƯỜI.................................. 33

2.1. Phương pháp phát hiện mặt người sử dụng HOG. .............................. 33

2.2. Rút trích đặc trưng HOG trong ảnh ..................................................... 38

2.3. Chuẩn hóa vector đặc trưng cho từng block ........................................ 42

2.4. Integral Image, công thức đệ quy tính Integral Image ........................ 43

2.5. Chuẩn hóa ánh sáng với bộ lọc Retinal filter ........................................ 44

2.6. Phương pháp phân lớp SVM .................................................................. 47

CHƯƠNG 3. XÂY DỰNG CHƯƠNG TRÌNH, THỬ NGHIỆM VÀ ĐÁNH

GIÁ KẾT QUẢ ................................................................................ 50

3.1. Môi trường thử nghiệm........................................................................... 50

3.2. Dữ liệu thử nghiệm .................................................................................. 50

3.2.1. Cơ sở dữ liệu UOF ........................................................................... 50

3.2.2. Cơ sở dữ liệu FEI ............................................................................. 51

3.2.3. Cơ sở dữ liệu JAFFE ....................................................................... 51

3.2.4. Cơ sở dữ liệu LFW ........................................................................... 52

3.3. Kết quả thử nghiệm ................................................................................. 52

KẾT LUẬN .............................................................................................................. 56

DANH MỤC TÀI LIỆU THAM KHẢO ............................................................... 58

5

DANH MỤC CÁC TỪ VIẾT TẮT

Từ hoặc cụm từ Từ Tiếng Anh Từ tiếng Việt

HOG Lược đồ gradient định hướng Histogram of Oriented Gradient

HMM Hidden Markov Model Mô hình Markov ẩn

SVM Support Vector Machines

6

DANH MỤC HÌNH ẢNH

Hình 1.1: Các điểm quan tâm được phát hiện bằng cách áp dụng (a) Harris, (b) các

toán tử KLT, và (c) SIFT. ......................................................................................... 12

Hình 1.2: Hỗn hợp mô hình Gaussian cho phép trừ nền. .......................................... 15

Hình 1.3: Tách hình nền dựa trên phân hủy Eigenspace (không gian được xây dựng

với các vật thể trong FOV của máy ảnh .................................................................... 17

Hình 1.4: Phân chia hình ảnh trong (a), sử dụng phân đoạn dịch chuyển trung bình

(b) và vết cắt bình thường (c). ................................................................................... 17

Hình 1.5: Đặc trưng Haar - Like ............................................................................... 23

Hình 1.6: Tính tích phân ảnh..................................................................................... 23

Hình 1.7: Cách tính P(x, y) ....................................................................................... 24

Hình 1.8: Kiểm tra kết quả chương trình so với bộ dữ liệu test ................................ 25

Hình 1.9: Kết quả phát hiện khuôn mặt bị sai lệch với khuôn mặt đeo kính ............ 26

Hình 1.10: Mô hình phân tầng kết hợp các bộ phân loại yếu để xác định khuôn mặt

................................................................................................................................... 27

Hình 1.11: Kết hợp các bộ phận loại yếu thành bộ phận loại mạnh ......................... 28

Hình 1.12: Sơ đồ khối thuật toán Adaboost .............................................................. 28

Hình 1.13. Minh họa tầng phân loại .......................................................................... 31

Hình 2.1. Mô hình phương pháp phát hiện khuôn mặt sử dụng đặc trưng HOG ..... 33

Hình 2.2: Minh họa các mẫu cửa sổ tìm kiếm kích thước 64x128 ........................... 34

Hình 2.3: Minh họa ô kích thước 8x8 trong cửa sổ tìm kiếm ................................... 35

Hình 2.4: Minh họa cho HOG ................................................................................... 35

Hình 2.5: Minh họa cho việc cộng thêm và nhân thêm vào giá trị của từng điểm ảnh

................................................................................................................................... 36

Hình 2.6: Minh họa cho sự thay đổi giá trị các vector gradient khi có sự thay đổi về

ánh sáng ..................................................................................................................... 36

7

Hình 2.7: Hình ảnh minh họa cho sự gộp các ô để tạo nên các khối có sự chồng lấp.

................................................................................................................................... 37

Hình 2.8: R-HOG và C-HOG [7] .............................................................................. 38

Hình 2.9: Mỗi khối (block) gồm nhiều ô (cell). Trong hình trên ta thấy một khối

gồm 9 ô ...................................................................................................................... 39

Hình 2.10: Các khối được xếp chồng lên nhau ......................................................... 39

Hình 2.11: Tính góc và biên độ theo X-gradient và Y-gradient ............................... 40

Hình 2.12: Các bước rút trích đặc trưng HOG [10] .................................................. 42

Hình 2.13: Integral Image [11].................................................................................. 43

Hình 2.14 Các bước trong bộ lọc Retinal filter ......................................................... 45

Hình 2.15: Kết quả của việc tiền xử lý với bộ lọc Retina filter ................................ 46

Hình 2.16. Siêu phẳng tách với khoảng cách lề cực đại ........................................... 47

Hình 3.1: Cơ sở dữ liệu mẫu UOF ............................................................................ 51

Hình 3.2: Cơ sở dữ liệu mẫu FEI .............................................................................. 51

Hình 3.3: Cơ sở dữ liệu mẫu JAFFE ......................................................................... 52

Hình 3.4: Cơ sở dữ liệu mẫu LFW ............................................................................ 52

Hình 3.5: Giao diện chương trình ............................................................................. 55

Hình 3.6: Giao diện chương trình khi thực hiện phát hiện được khuôn mặt ............ 55

8

DANH MỤC BẢNG BIỂU

Bảng 1.1: Bảng đánh giá thuật toán Viola - Jones .................................................... 25

Bảng 3.1: Đánh giá hiệu quả phát hiện khuôn mặt ................................................... 53

Bảng 3.2: Đánh giá độ chính xác phát hiện khuôn mặt ............................................ 54

9

MỞ ĐẦU

Thị giác máy là một lĩnh vực thu hút nhiều nghiên cứu và thể hiện khả năng

ứng dụng cao trong những năm gần đây. Một trong những bài toán được đặc biệt

quan tâm là phát hiện vật thể trong ảnh/video. Phát hiện vật thể thường là bước khởi

đầu cho các hệ thống theo dõi/giám sát và nhận diện.

Phát hiện mặt người là một chủ đề nghiên cứu thuộc lĩnh vực thị giác máy

tính đã được phát triển từ đầu những năm 90 của thế kỷ trước, cho tới hiện nay, đây

vẫn là một chủ đề nghiên cứu mở, nhận được sự quan tâm của nhiều nhà nghiên cứu

từ nhiều lĩnh vực nghiên cứu khác nhau. Điều này là do có rất nhiều ứng dụng thực

tế cần tới một hệ thống phát hiện mặt người, từ các hệ thống quản lý đăng nhập đơn

giản cho tới các ứng dụng giám sát tại các địa điểm công cộng, hoặc quản lý dân số

và pháp lý.

Hơn một thập kỷ qua, có rất nhiều công trình nghiên cứu về bài toán xác định

khuôn mặt người từ ảnh đen trắng, ảnh xám, đến ảnh màu như ngày nay. Các

nghiên cứu đi từ bài toán đơn giản là ảnh chỉ chứa một khuôn mặt người nhìn thẳng

vào thiết bị thu hình và đầu ở tư thế thẳng đứng, cho đến ảnh màu với nhiều khuôn

mặt người trong cùng ảnh, khuôn mặt có quay một góc nhỏ, hay bị che khuất một

phần, và với ảnh nền của ảnh phức tạp (ảnh chụp ngoài thiên nhiên) nhằm đáp ứng

nhu cầu thật sự cần thiết của con người.

Bài toán xác định khuôn mặt người (Face detection) là một kỹ thuật máy tính

để xác định các vị trí và các kích thước của khuôn mặt trong ảnh bất kỳ (ảnh kỹ

thuật số). Kỹ thuật này nhận biết các đặt trưng khuôn mặt và bỏ qua những thứ khác

như: tòa nhà, cây cối, cơ thể...

Một số ứng dụng của bài toán xác định khuôn mặt là: hệ thống tương tác giữa

người và máy (điều kiển máy tính qua các cử động của khuôn mặt), hệ thống nhận

dạng người (giúp cho các cơ quan an ninh quản lý con người), hệ thống quan sát

theo dõi, hệ thống quản lý việc ra vào cho các cơ quan và công ty, hệ thống kiểm tra

10

người lái xe có ngủ gật hay không, hệ thống phân tích cảm xúc trên khuôn mặt, và

hệ thống nhận dạng khuôn mặt cho các máy ảnh kỹ thuật số...

Hiện nay có rất nhiều phương pháp phát hiện khuôn mặt người, dựa vào các

tính chất của các phương pháp, ta có thể chia ra làm bốn hướng tiếp cận chính như

sau: Hướng tiếp cận dựa trên tri thức: mã hoá hiểu biết của con người về các loại

khuôn mặt và tạo ra các tập luật để xác định khuôn mặt. Hướng tiếp cận dựa trên

đặc tả không thay đổi: mục tiêu các thuật toán tìm ra các đặt trưng mô tả cấu trúc

khuôn mặt người (các đặt trưng không thay đổi với tư thế, vị trí đặt thiết bị thu hình,

độ sáng tối thay đổi...). Hướng tiếp cận dựa trên so khớp mẫu: dùng các mẫu chuẩn

hay các đặc trưng của khuôn mặt người. Hướng tiếp cận dựa trên diện mạo: phương

pháp học từ một tập ảnh huấn luyện mẫu để xác định khuôn mặt người.

Phương pháp nhận diện được sử dụng rất phổ biến hiện nay dựa trên thuật

toán của Viola-Johns. Tuy nhiên, phương pháp này có thời gian huấn luyện rất dài,

yêu cầu số mẫu lớn. Một số cải tiến đã được đưa ra để giải quyết vấn đề này, trong

đó có việc sử dụng đặc trưng HOG (Histogram of Oriented Gradient).

Mục tiêu của đề tài là nghiên cứu loại đặc trưng HOG, cách sử dụng nó kết

hợp với SVM (Support Vector Machines) để phát hiện khuôn mặt người trong ảnh

thu từ camera giám sát. Đây là một vấn đề cần giải quyết để xây dựng thử nghiệm

một hệ thống hỗ trợ điểm danh tự động học sinh.

1. Mục tiêu của đề tài

Mục tiêu của đề tài nghiên cứu các vấn đề sau:

- Nghiên cứu Haar wavelet và Adaboost;

- Nghiên cứu thuật toán Viola - Johns;

- Nghiên cứu đặc trưng HOG;

- Nghiên cứu cách sử dụng đặc trưng HOG với SVM trong phát hiện mặt người.

- Xây dựng bộ dữ liệu khuôn mặt để thử nghiệm;

- Thực hiện huấn luyện và test;

- Phân tích, đánh giá kết quả thu được; so sánh kết quả thu được với kết quả của

một số phương pháp phát hiện đã được công bố.

11

- Xây dựng thử nghiệm chương trình phát hiện khuôn mặt từ camera giám sát

lớp học.

2. Hướng nghiên cứu của đề tài

- Nghiên cứu Haar wavelet và Adaboost, thuật toán Viola - Johns;

- Nghiên cứu cách sử dụng đặc trưng HOG với SVM trong phát hiện mặt người.

- Xây dựng dữ liệu để huấn luyện và test; phân tích và đánh giá kết quả thu

được; so sánh kết quả test trên các kho dữ liệu cử chỉ khác nhau; so sánh kết

quả thu được bằng phương pháp sử dụng đặc trưng HOG với các phương pháp

khác đã được công bố.

3. Ý nghĩa khoa học và thực tiễn của đề tài

Đề tài có ý nghĩa thực tiễn trong việc xây dựng một hệ thống thử nghiệm hỗ

trợ điểm danh tự động cho trường phổ thông. Hệ thống này gồm một đề tài về phát

hiện khuôn mặt và một đề tài về nhận diện khuôn mặt.

12

CHƯƠNG I. TỔNG QUAN VỀ PHÁT HIỆN MẶT NGƯỜI

TRONG ẢNH VÀ VIDEO

Mọi phương pháp nhận dạng đều yêu cầu cơ chế phát hiện đối tượng trong

mỗi hình ảnh hoặc khi đối tượng xuất hiện trong video. Cách tiếp cận phổ biến để

phát hiện đối tượng là sử dụng thông tin trong một hình ảnh đơn. Tuy nhiên, một số

phương pháp phát hiện đối tượng sử dụng thông tin thời gian được tính từ một

chuỗi các hình ảnh để giảm số lần phát hiện sai. Thông tin thời gian này thường ở

sự khác biệt hình ảnh, làm nổi bật các vùng thay đổi trong các hình ảnh liên tiếp.

1.1. Phát hiện điểm

Phát hiện điểm [1] được sử dụng để tìm các điểm quan tâm trong các hình ảnh

có kết cấu biểu cảm ở các vùng tương ứng. Điểm quan tâm được sử dụng nhiều

trong các ngữ cảnh chuyển động, âm thanh stereo, và các vấn đề theo dõi. Chất

lượng mong muốn của điểm quan tâm là sự bất biến của nó đối với những thay đổi

về độ chiếu sáng và quan điểm của máy ảnh.

Trong các tài liệu, các phát hiện điểm thường được sử dụng bao gồm: phát

hiện điểm Moravec, phát hiện điểm Harris, máy dò KLT, và phát hiện SIFT. Để

đánh giá, so sánh các điểm quan tâm, chúng ta tham khảo nghiên cứu của

Mikolajczyk và Schmid. Để tìm các điểm quan tâm, thuật toán của Moravec tính

toán sự thay đổi của các điểm ảnh hình ảnh trong một bảng kích thước 4x4 theo

hướng ngang, dọc, đường chéo và chọn tối thiểu bốn biến thể như các giá trị đại

diện cho cửa sổ. Một điểm được xác nhận là quan tâm nếu sự thay đổi cường độ cục

bộ tối đa kích thước 12x12.

Hình 1.1: Các điểm quan tâm được phát hiện bằng cách áp dụng (a) Harris, (b) các toán tử KLT, và (c) SIFT.

13

Máy dò Harris tính toán các dẫn xuất hình ảnh bậc nhất, (𝐼𝑥,𝐼𝑦,) theo các hướng

x và y để làm nổi bật các biến thể cường độ hướng, sau đó một ma trận thời gian thứ

hai mã hóa biến thể này, được đánh giá cho mỗi điểm ảnh trong một khu vực lân

cận nhỏ:

2 ) (1)

2 ∑ 𝐼𝑥 ∑ 𝐼𝑥 𝐼𝑦

𝑀 = ( ∑ 𝐼𝑥 𝐼𝑦 ∑ 𝐼𝑦

Một điểm quan tâm được xác định bằng cách sử dụng phương thức và dấu vết

của M đo lường sự biến thiên trong một khu vực lân cận 𝑅 = 𝑑𝑒𝑡(𝑀) −

𝑘. 𝑡𝑟(𝑀)2, trong đó k là hằng số. Các điểm quan tâm được đánh dấu bằng ngưỡng R

sau khi áp dụng sự khử không tối đa (kết quả hình 1.1 (a)).

Ma trận thời gian tương tự M được đưa ra trong phương trình (1) được sử

dụng trong bước phát hiện điểm quan tâm của phương pháp theo dõi KLT. Xác định

điểm quan tâm R được tính bằng cách sử dụng giá trị riêng tối thiểu của 𝑀, 𝜆𝑚𝑖𝑛.

Các điểm quan tâm được lựa chọn bởi ngưỡng R. Trong số các điểm quan tâm,

KLT loại bỏ các điểm quan tâm mà không gian gần nhau (Hình 1.1 (b)).Về mặt

định lượng cả Harris và KLT đều nhấn mạnh các biến thể cường độ bằng các biện

pháp tương tự nhau. Ví dụ, R ở Harris có liên quan đến đa thức đặc trưng được sử

dụng để tìm các giá trị riêng của 𝑀: 𝜆2 + 𝑑𝑒𝑡(𝑀) − 𝜆 . 𝑡𝑟(𝑀) = 0, trong khi

KLT tính trực tiếp các giá trị riêng.

Trong thực tế, cả hai phương pháp này đều tìm thấy gần như cùng một điểm

quan tâm. Sự khác biệt duy nhất là tiêu chí KLT bổ sung thực thi một khoảng cách

không gian được xác định trước giữa các điểm quan tâm đã phát hiện.

Về lý thuyết, ma trận M là bất biến đối với phép quay và dịch. Tuy nhiên,

không phải bất biến đối với các biến đổi affine hoặc projective. Để giới thiệu sự

phát hiện mạnh mẽ các điểm quan tâm dưới các biến đổi khác nhau, Lowe đã giới

thiệu phương pháp SIFT (Quy mô biến đổi không đổi) bao gồm bốn bước.

Thứ nhất, một không gian được xây dựng bằng cách hợp nhất hình ảnh với các

bộ lọc Gaussian ở các quy mô khác nhau. Hình ảnh đã hợp nhất được sử dụng để

14

tạo ra các hình ảnh khác nhau của Gaussians (DoG). Các điểm quan tâm đề xuất sau

đó được chọn từ các cực tiểu và cực đại của các hình ảnh DoG trên tỷ lệ.

Bước tiếp theo cập nhật vị trí của mỗi đề xuất bằng cách nội suy các giá trị

màu sắc và sử dụng các điểm ảnh lân cận. Trong bước thứ ba, loại bỏ các đề xuất

tương phản thấp, dọc theo các cạnh.

Cuối cùng, các điểm quan tâm còn lại được định hướng dựa trên các đỉnh

trong biểu đồ của các đường định hướng gradient trong một khu vực nhỏ xung

quanh điểm đề xuất. Máy dò SIFT tạo ra một số điểm quan tâm lớn hơn so với các

máy dò điểm quan tâm khác. Điều này là do thực tế các điểm quan tâm ở các quy

mô khác nhau và độ phân giải khác nhau (hình chóp) được tích trữ. Theo kinh

nghiệm SIFT tốt hơn hầu hết các điểm dò và linh hoạt hơn cho các biến dạng hình

ảnh.

1.2. Phép trừ nền

Phát hiện đối tượng có thể đạt được bằng cách xây dựng một biểu diễn của

cảnh được gọi là mô hình nền, sau đó tìm ra độ lệch từ mô hình cho mỗi khung. Bất

kỳ thay đổi nhỏ nào trong vùng hình ảnh từ hình nền cho thấy một đối tượng

chuyển động. Các điểm ảnh tạo thành các vùng thay đổi được đánh dấu để xử lý

tiếp. Thông thường, thuật toán thành phần kết nối được áp dụng để có được các

vùng kết nối tương ứng với các đối tượng. Quá trình này được gọi là phép trừ nền

[1].

Sự khác biệt khung của các khung liền kề đã được nghiên cứu kỹ lưỡng từ

cuối những năm 70. Tuy nhiên, phép trừ nền đã trở nên phổ biến theo sau công trình

của Wren et al. Để tìm hiểu sự thay đổi dần dần về thời gian, Wren et al. đề xuất mô

hình hoá màu sắc của mỗi điểm ảnh, 𝐼 (𝑥, 𝑦) của một nền tĩnh cố định với một

không gian màu 3D (Y, U, và V) Gaussian, 𝐼(𝑥, 𝑦) ~ 𝑁(𝜇 (𝑥, 𝑦) , ∑( 𝑥, 𝑦)). Các

thông số mô hình, trung bình (x, y) và hiệp phương sai £(x, y), được học từ các

quan sát màu sắc trong một số khung liên tiếp. Khi mô hình nền được tạo ra, đối với

mỗi điểm ảnh (𝑥, 𝑦) trong khung đầu vào, tính khả năng màu của nó đến từ

𝑁(𝜇(𝑥, 𝑦), ∑(𝑥, 𝑦)) được tính toán, và các điểm ảnh đi chệch hướng mô hình nền

15

được dán nhãn là các điểm ảnh nổi. Tuy nhiên, một Gaussian không phải là một mô

hình tốt cho những cảnh ngoài trời vì nhiều màu sắc có thể được quan sát ở một vị

trí nhất định do chuyển động đối tượng lặp đi lặp lại, bóng hoặc phản xạ.

Một cải tiến đáng kể trong mô hình nền đã đạt được bằng cách sử dụng mô

hình thống kê đa phương thức để mô tả màu nền cho mỗi điểm ảnh. Ví dụ, Stauffer

và Grimson sử dụng một hỗn hợp của Gaussians để mô hình màu điểm ảnh. Trong

phương pháp này, một điểm ảnh trong khung hiện tại được kiểm tra đối với mô hình

nền bằng cách so sánh nó với mọi Gaussian trong mô hình cho đến khi tìm thấy một

Gaussian phù hợp. Nếu so khớp được tìm thấy, giá trị trung bình và phương sai của

Gaussian phù hợp được cập nhật, nếu không Gaussian mới có nghĩa là bằng với

màu điểm ảnh hiện tại và một số phương sai ban đầu được đưa vào hỗn hợp. Mỗi

điểm ảnh được phân loại dựa trên việc phân phối phù hợp có phải là quá trình nền

hay không. Di chuyển các khu vực, được phát hiện bằng cách sử dụng phương pháp

này, cùng với các mô hình nền được thể hiện trong hình 1.2. (a) Hình ảnh từ một

dãy trong đó một người đang đi ngang qua hiện trường. (b) Giá trị trung bình của

các Gaussian có trọng số cao nhất ở mỗi vị trí điểm ảnh. Các phương tiện này đại

diện cho màu sắc cho mỗi điểm ảnh tạm thời nhất và do đó phải đại diện cho nền

tĩnh. (c) Các phương tiện của Gauss với trọng lượng cao thứ hai; những phương tiện

này đại diện cho màu sắc được quan sát ít thường xuyên hơn. (d) Kết quả trừ nền.

Các tiền cảnh bao gồm các điểm ảnh trong khung hiện tại mà phù hợp với một trọng

số thấp Gaussian.

Hình 1.2: Hỗn hợp mô hình Gaussian cho phép trừ nền.

Cách tiếp cận khác là kết hợp thông tin cảnh dựa trên vùng (không gian) thay

vì chỉ sử dụng thông tin dựa trên màu. Elgammal và Davis sử dụng ước lượng mật

độ hạt nhân không tham số để mô hình nền cho mỗi điểm ảnh. Trong quá trình trừ,

16

điểm ảnh hiện tại không chỉ khớp với điểm ảnh tương ứng trong mô hình nền, mà

còn đến vị trí điểm ảnh gần đó. Do đó, phương pháp này có thể xử lý sự chập chờn

của ảnh hoặc các chuyển động nhỏ trong nền. Li và Leung kết hợp các tính năng kết

cấu và màu để thực hiện phép trừ nền trên khối 5 x 5 điểm ảnh. Do cấu trúc không

thay đổi nhiều với sự thay đổi độ chiếu sáng, nên phương pháp này ít bị ảnh hưởng

bởi ánh sáng. Toyama và cộng sự đề xuất một thuật toán ba cấp để giải quyết vấn đề

trừ nền. Ngoài phép trừ cấp điểm ảnh, họ sử dụng miền và thông tin mức khung. Ở

cấp điểm ảnh, họ đề xuất sử dụng bộ lọc Wiener để dự đoán có tính xác suất về màu

nền dự kiến. Ở cấp vùng, các vùng tiền cảnh bao gồm màu đồng nhất được điền

vào. Ở cấp khung, nếu hầu hết các điểm ảnh trong khung hiển thị đột ngột thay đổi,

giả sử rằng các mô hình nền màu điểm ảnh dựa trên không còn hợp lệ. Vào thời

điểm này, mô hình nền dựa trên điểm ảnh được lưu trữ trước đó được hoán đổi,

hoặc mô hình được khởi tạo lại.

Cách tiếp cận thay thế cho phép trừ nền là đại diện cho các biến thể cường độ

của một điểm ảnh trong một chuỗi ảnh như các trạng thái rời rạc tương ứng với các

sự kiện trong môi trường. Rittscher et al sử dụng mô hình Markov ẩn (HMM) để

phân loại các khối nhỏ của một hình ảnh giống như một trong ba trạng thái này.

Trong bối cảnh phát hiện ánh sáng trong và ngoài sự kiện trong một căn phòng,

Stenger et al sử dụng HMM cho phép trừ nền. Ưu điểm của việc sử dụng HMM là

các sự kiện nhất định, khó có thể mô hình chính xác bằng cách sử dụng các phương

pháp mô hình nền không giám sát, có thể được học bằng các mẫu huấn luyện.

Thay vì mô phỏng các biến thể của từng điểm ảnh, Oliver et al đề xuất một

cách tiếp cận toàn diện bằng cách sử dụng phân tích eigenspace. Đối với các khung

đầu vào 𝑘, 𝐼2: 𝑖 = 1 … 𝑘, có kích thước 𝑛 × 𝑚, ma trận nền B có kích thước 𝑘 × 𝑙

được tạo thành bởi các phân tầng m trong mỗi khung, sau đó là 𝑙 = (𝑛 × 𝑚), và sự

phân hủy giá trị riêng đến hiệp phương sai của 𝐵, 𝐶 = 𝐵𝑇𝐵. Sau đó nền được đại

diện bởi các vector riêng mô tả hầu hết n, 𝑢𝑖, trong đó 𝑖 < 𝑛 < 𝑘, bao gồm tất cả

những ánh sáng có thể có trong vùng quan sát (FOV). Do đó, phương pháp tiếp cận

này ít nhạy cảm với ánh sáng. Các đối tượng nền được phát hiện bằng cách chiếu

17

hình ảnh hiện tại lên vùng không gian và tìm ra sự khác biệt giữa hình ảnh được tái

tạo và thực tế. Hình 1.3. hiển thị các vùng đối tượng phát hiện được sử dụng

phương pháp tiếp cận eigenspace ): (a) một hình ảnh đầu vào với các đối tượng, (b)

tái tạo hình ảnh sau khi chiếu hình ảnh đầu vào lên không gian eigenspace, (c) Lưu

ý rằng các đối tượng nền được xác định rõ ràng.

Hình 1.3: Tách hình nền dựa trên phân hủy Eigenspace (không gian được xây dựng với các vật thể trong FOV của máy ảnh

Một hạn chế của các phương pháp tiếp cận nói trên là cần nền tĩnh. Hạn chế

này được giải quyết bởi Monnet et al., và Zhong và Sclaroff. Cả hai phương pháp

này đều có thể xử lý được nền thời gian khác nhau (ví dụ: sóng trên mặt nước, các

đám mây di chuyển…). Các phương pháp này mô hình các vùng hình ảnh như các

quá trình tự động hồi quy trung bình (ARMA) cung cấp cách để tìm hiểu và dự

đoán mô hình chuyển động trong một cảnh. Quy trình ARMA là một mô hình chuỗi

thời gian, được tạo thành từ các thành phần tự hồi quy và di chuyển trung bình,

trong đó quá trình tự hồi quy có thể được mô tả như là một tổng trọng số của các giá

trị trước đó và một lỗi tiếng ồn trắng.

Hình 1.4: Phân chia hình ảnh trong (a), sử dụng phân đoạn dịch chuyển trung bình (b) và vết cắt bình thường (c).

Tóm lại, hầu hết các phương pháp theo dõi cho những camera cố định, ví dụ,

Haritaoglu et al và Collins et al sử dụng phương pháp trừ nền để phát hiện các vùng

18

quan tâm. Bởi vì các phương pháp trừ gần đây có khả năng mô hình hoá độ sáng,

tiếng ồn và chuyển động định kỳ của vùng nền, do đó có thể phát hiện chính xác các

đối tượng trong nhiều trường hợp. Trong thực tế, phép trừ nền cho ta các vùng đối

tượng không đầy đủ trong nhiều trường hợp, nghĩa là các đối tượng có thể tràn vào

một số vùng, hoặc có thể có lỗ bên trong đối tượng vì không bảo đảm rằng các đối

tượng không khác biệt so với nền.

1.3. Phân vùng

Mục đích của thuật toán là phân chia hình ảnh thành các vùng tương tự nhau.

Mỗi thuật toán phân vùng giải quyết hai vấn đề, các tiêu chí cho một phân vùng tốt

và phương pháp để đạt được phân vùng hiệu quả [1].

1.3.1. Mean-Shift Clustering

Đối với vấn đề phân vùng hình ảnh [1], Comaniciu và Meer đề xuất phương

pháp chuyển dịch trung bình để tìm các cụm trong không gian hỗn hợp với không

gian màu [𝑙, 𝑢, 𝑣, 𝑥, 𝑦], trong đó [𝑙, 𝑢, 𝑣] đại diện cho màu sắc và [𝑥, 𝑦] đại diện cho

vị trí không gian. Với hình ảnh, thuật toán được khởi tạo với số lượng lớn các trung

tâm cụm giả thuyết được chọn ngẫu nhiên từ dữ liệu. Sau đó, mỗi trung tâm cụm

được di chuyển đến mức trung bình của dữ liệu nằm bên trong ellip đa chiều tập

trung vào trung tâm cụm. Vectơ được xác định bởi các trung tâm cụm cũ và mới

được gọi là vector thay đổi trung bình. Vectơ thay đổi trung bình được tính toán lặp

đi lặp lại cho đến khi các trung tâm cụm không thay đổi vị trí của chúng. Lưu ý rằng

trong quá trình dịch lặp lại có nghĩa là một số cụm có thể được hợp nhất. Hiển thị

phân đoạn sử dụng phương pháp chuyển dịch trung bình Trong hình 1.4 (b), sử

dụng mã nguồn có sẵn tại MeanShiftSegmentSrc.

Khả năng phân cụm trung bình thay đổi có thể mở rộng cho nhiều ứng dụng

khác như phát hiện cạnh, điều chỉnh hình ảnh, và theo dõi.

Sự phân đoạn dựa trên chuyển đổi trung bình đòi hỏi phải tinh chỉnh các tham

số khác nhau để có được sự phân đoạn tốt hơn, ví dụ như lựa chọn màu sắc và

19

không gian trung tâm, ngưỡng cho kích thước nhỏ nhất của vùng có ảnh hưởng

đáng kể tới kết quả phân đoạn.

1.3.2. Phân đoạn Hình ảnh Sử dụng Đồ thị-Cuts.

Phân chia hình ảnh cũng có thể được xây dựng như là một vấn đề phân vùng

𝑁 𝐴𝑖 = V, 𝐴𝑖 ∩ 𝐴𝑗 =

đồ thị, trong đó các đỉnh (các điểm ảnh), V = {𝑢, 𝑣, . . . }, của một đồ thị (hình ảnh)

G, được phân chia thành 𝑁 đồ thị phụ rời rạc (vùng) 𝐴𝑖,∪𝑖=1

∅, 𝑖 ≠ 𝑗, bằng cách tỉa các cạnh trọng số của đồ thị. Tổng trọng số của các cạnh cắt

tỉa giữa hai bản đồ con được gọi là cắt. Trọng số thường được tính bằng màu sắc, độ

sáng, hoặc độ tương đồng giữa các nút. Wu và Leahy sử dụng tiêu chuẩn cắt giảm

tối thiểu, mục tiêu là tìm các phân vùng để giảm thiểu sự cắt giảm. Trong cách tiếp

cận của họ, trọng số được xác định dựa trên màu giống nhau. Một giới hạn của cắt

tối thiểu là ảnh hưởng của nó đối với việc phân đoạn hình ảnh. Ảnh hưởng này do

chi phí cắt giảm với số lượng các cạnh đi qua hai phân đoạn được chia [1].

Shi và Malik đề xuất cắt giảm bình thường để vượt qua vấn đề phân đoạn trên.

Trong cách tiếp cận của họ, việc cắt giảm không chỉ phụ thuộc vào tổng trọng số

của trọng số cắt, mà còn dựa trên tỷ lệ tổng trọng số kết nối của các nút trong mỗi

phân vùng cho tất cả các nút của đồ thị. Đối với phân đoạn dựa trên hình ảnh, trọng

số giữa các nút được xác định bởi sản phẩm có độ tương tự màu và không gian gần

nhau. Một khi các trọng số giữa mỗi cặp nút được tính toán, ma trận trọng số 𝑊 và

𝑁 𝑗=1

, được xây dựng. Phân đoạn được ma trận đường chéo 𝐷, trong đó 𝐷𝑖,𝑖 = ∑ 𝑊𝑖,𝑗

thực hiện đầu tiên bằng cách tính toán các vector đặc trưng và các trị số riêng của hệ

thống tổng quát (𝐷 − 𝑊)𝑦 = 𝜆𝐷𝑦, sau đó là vector đặc trưng thứ hai được sử dụng

để chia trong hình ảnh thành hai phân đoạn. Đối với mỗi phân đoạn mới, quá trình

này được thực hiện đệ quy cho đến khi đạt ngưỡng. Trong hình 1.4 (c), hiển thị các

kết quả phân khúc thu được bằng cách tiếp cận cắt giảm bình thường.

Trong phân đoạn dựa trên cắt bình thường, giải pháp cho hệ thống tổng quát

cho các hình ảnh lớn có thể tốn kém về mặt xử lý và yêu cầu về bộ nhớ. Tuy nhiên,

phương pháp này yêu cầu các tham số được chọn bằng tay ít hơn, so với phân đoạn

20

trung bình. Cắt bình thường cũng được sử dụng trong bối cảnh các đường viền theo

dõi đối tượng.

1.3.3. Đường nét hoạt động

Trong một khung viền, phân đoạn đối tượng bằng cách phát triển một đường

viền khép kín bao quanh đối tượng, để đường viền bao quanh vùng đối tượng. Sự

phát triển của đường viền được điều chỉnh bởi một chức năng xác định sự vừa vặn

của đường viền quanh đối tượng [1]. Chức năng có dạng sau đây:

1 0

(2) 𝐸(Γ) = ∫ 𝐸𝑖𝑛𝑡 (v)+𝐸𝑖𝑚(v)+𝐸𝑒𝑥𝑡(v)𝑑𝑠

Trong đó s là chiều dài cung của đường viền Γ , 𝐸𝑖𝑛𝑡 gồm có các ràng buộc

quy định, 𝐸𝑖𝑚 bao gồm năng lượng dựa trên sự xuất hiện, và 𝐸𝑒𝑥𝑡 chỉ rõ các hạn chế bổ sung. 𝐸𝑖𝑛𝑡 thường có độ cong, thứ tự đầu tiên (∇v) hoặc thứ hai (∇2v) để tìm đường viền ngắn nhất. Năng lượng hình ảnh, 𝐸𝑖𝑚, có thể được tính toán cục bộ hoặc

tổng thể. Thông tin cục bộ thường ở dạng hình ảnh gradient và được đánh giá xung

quanh đường viền. Ngược lại, các tính năng tổng thể được tính toán bên trong và

bên ngoài của vùng đối tượng. Các tính năng tổng thể bao gồm màu sắc và kết cấu.

Các nhà nghiên cứu khác nhau đã sử dụng thuật ngữ năng lượng khác nhau

trong phương trình (2). Năm 1995, Caselles et al. loại trừ 𝐸𝑒𝑥𝑡 và chỉ sử dụng ảnh gradient như là năng lượng ảnh 𝐸𝑖𝑚 = g(|∇𝑰|) , trong đó g là hàm sigma.

So với gradient, một hàm của gradient xác định đường viền đối tượng như một

đường cong đo đạc trong không gian Riemannian. Tuy nhiên, hình ảnh gradient

cung cấp thông tin rất cục bộ và nhạy cảm với cục bộ nhỏ nhất. Để khắc phục vấn

đề này, các nhà nghiên cứu đã giới thiệu các thuật ngữ về năng lượng hình ảnh theo

khu vực. Năm 1996, Zhu và Yuille đã đề xuất sử dụng thông tin vùng thay vì

gradient hình ảnh. Tuy nhiên, việc sử dụng thuật ngữ khu vực trong chức năng năng

lượng không đưa đến cục bộ tốt của đường viền đối tượng.

Gần đây, các phương pháp kết hợp cả năng lượng ảnh dựa trên vùng và

gradient dựa trên đã trở nên phổ biến. Paragios và Deriche đề xuất sử dụng một sự

kết hợp lồi của gradient và các nguồn năng lượng vùng, 𝐸𝑖𝑚𝑎𝑔𝑒 = 𝜆𝐸𝑏𝑜𝑢𝑛𝑑𝑎𝑟𝑦 +

21

(1 − 𝜆)𝐸𝑟𝑒𝑔𝑖𝑜𝑛. Đặc biệt, các tác giả mô hình sự xuất hiện ở 𝐸𝑟𝑒𝑔𝑖𝑜𝑛. bằng hỗn hợp

Gaussians. Sự biến đổi đường viền được thực hiện đầu tiên trên tổng thể, sau đó

bằng cách thay đổi 𝛼 từ 0 đến 1 tại mỗi lần lặp.

Một vấn đề quan trọng trong phương pháp đường viền là khởi tạo đường viền.

Trong phương pháp tiếp cận dựa trên gradient hình ảnh, một đường viền thường

được đặt bên ngoài vùng đối tượng và bị co lại cho đến khi gặp ranh giới đối tượng.

Hạn chế này được khắc phục trong các phương pháp dựa trên vùng sao cho đường

viền có thể được khởi tạo bên trong hoặc bên ngoài đối tượng sao cho đường viền

có thể mở rộng hoặc thu nhỏ tương ứng để phù hợp với ranh giới đối tượng. Những

cách tiếp cận này đòi hỏi phải có đối tượng hoặc kiến thức nền trước. Sử dụng nhiều

khung hoặc một khung tham chiếu, khởi tạo có thể được thực hiện mà không cần

xây dựng khu vực priors. Ví dụ, trong Paragios và Deriche, các tác giả sử dụng

phép trừ nền để khởi tạo đường viền.

Bên cạnh việc lựa chọn các chức năng năng lượng và khởi tạo, một vấn đề

quan trọng khác là lựa chọn đường viền phải đại diện. Vẽ đối tượng Γ có thể được

biểu diễn một cách rõ ràng (control points, v) hoặc hoàn toàn (level sets, 𝜙). Trong

biểu diễn rõ ràng, mối quan hệ giữa các control points được xác định bởi phương

trình spline. Trong biểu thức cấp đại diện, đường viền được biểu diễn trên lưới

không gian mã hóa khoảng cách đã ký của lưới từ đường viền với các dấu hiệu

ngược đối với đối tượng và vùng nền. Đường viền được định nghĩa ngầm như là các

đường giao cắt không trong lưới thiết lập mức. Sự tiến triển của đường viền được

điều chỉnh bằng cách thay đổi giá trị lưới theo công thức tính bằng phương trình (2),

đánh giá tại mỗi vị trí lưới. Sự thay đổi trong các giá trị lưới tạo ra các đường giao

cắt mới bằng 0, do đó, các vị trí đường viền mới

1.4. Học có giám sát

Học có giám sát là một kĩ thuật của ngành học máy để xây dựng một hàm

(function) từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp gồm đối

tượng đầu vào (thường dạng vec-tơ), và đầu ra mong muốn. Đầu ra của một hàm có

22

thể là một giá trị liên tục (gọi là hồi qui), hay có thể là dự đoán một nhãn phân loại

cho một đối tượng đầu vào (gọi là phân loại). Nhiệm vụ của chương trình học có

giám sát là dự đoán giá trị của hàm cho một đối tượng bất kì là đầu vào hợp lệ, sau

khi đã xem xét một số ví dụ huấn luyện (nghĩa là, các cặp đầu vào và đầu ra tương

ứng). Để đạt được điều này, chương trình học phải tổng quát hóa từ các dữ liệu sẵn

có để dự đoán được những tình huống chưa gặp phải theo một cách “hợp lý”.

Học có giám sát có thể tạo ra hai loại mô hình. Phổ biến nhất, học có giám sát

tạo ra một mô hình toàn cục (global model) để ánh xạ đối tượng đầu vào đến đầu ra

mong muốn. Tuy nhiên, trong một số trường hợp, việc ánh xạ được thực hiện dưới

dạng một tập các mô hình cục bộ (như trong phương pháp lập luận theo tình

huống(case-based reasoning) hay giải thuật láng giềng gần nhất).

Để có thể giải quyết một bài toán nào đó của học có giám sát (ví dụ: học

để phát hiện mặt người) người ta phải xem xét nhiều bước khác nhau:

- Xác định loại của các ví dụ huấn luyện. Trước khi làm bất cứ điều gì, người

kĩ sư nên quyết định loại dữ liệu nào sẽ được sử dụng làm ví dụ. Chẳng hạn, đó có

thể là một ảnh đơn, đoạn video…

- Thu thập tập huấn luyện. Tập huấn luyện cần đặc trưng cho thực tế sử dụng

của hàm chức năng. Vì thế, một tập các đối tượng đầu vào được thu thập và đầu ra

tương ứng được thu thập, hoặc từ các chuyên gia hoặc từ việc đo đạc tính toán.

- Xác định việc biểu diễn các đặc trưng đầu vào cho hàm chức năng cần tìm.

Sự chính xác của hàm chức năng phụ thuộc lớn vào cách các đối tượng đầu vào

được biểu diễn. Thông thường, đối tượng đầu vào được chuyển đổi thành một vec-

tơ đặc trưng, chứa một số các đặc trưng nhằm mô tả cho đối tượng đó. Số lượng các

đặc trưng không nên quá lớn, do sự bùng nổ tổ hợp (curse of dimensionality); nhưng

phải đủ lớn để dự đoán chính xác đầu ra.

- Xác định cấu trúc của hàm chức năng cần tìm và giải thuật học tương ứng.

Ví dụ, chúng ta có thể lựa chọn việc sử dụng mạng nơ-ron nhân tạo hay cây quyết

định.

23

- Hoàn thiện thiết kế chúng ta sẽ chạy giải thuật học từ tập huấn luyện thu thập

được. Các tham số của giải thuật học có thể được điều chỉnh bằng cách tối ưu hóa

hiệu năng trên một tập con (gọi là tập kiểm chứng -validation set) của tập huấn

luyện, hay thông qua kiểm chứng chéo (cross-validation). Sau khi học và điều chỉnh

tham số, hiệu năng của giải thuật có thể được đo đạc trên một tập kiểm tra độc lập

với tập huấn luyện.

1.5. Thuật toán Viola–Johns và các vấn đề liên quan.

1.5.1. Thuật toán Viola–Johns

Đây là thuật toán của Paul Viola và Michael Jones đề xuất vào năm 2001.

Phương pháp sử dụng đặc trưng Haar-Like kết hợp với máy phân lớp Ada Boost

giúp tăng tốc độ của chương trình [2].

Các đặc trưng Haar-like là các hình chữ nhật đen trắng để xác định khuôn mặt

người. Gồm 4 đặc trưng cơ bản:

Hình 1.5: Đặc trưng Haar - Like

Để tăng tốc độ tính toán và xử lí, Viola-Jones đề xuất một khái niệm mới là

Intergral Image (tích phân ảnh). Intergral Image là một mảng hai chiều có kích

thước bằng kích thước của ảnh đang xét. Khi đó, tổng mức xám của 1 vùng được

tính như sau:

Hình 1.6: Tính tích phân ảnh

D = A + B + C + D – (A+B) – (A+C) + A

= P1(x1, y1) + P2(x2, y2) + P3(x3, y3) + P4(x4, y4) – (P1(x1, y1)+P2(x2,

y2)) – (P1(x1, y1)+P3(x3, y3)) + P1(x1, y1)

24

Trong đó, P(x, y) được tính như Hình 1.7:

Hình 1.7: Cách tính P(x, y)

Sau khi tính được tích phân ảnh từ vùng ảnh cần xét, thuật toán Viola-Jones sử

dụng bộ phân lớp AdaBoost để loại bỏ các đặc trưng không cần thiết.

1.5.2. Đánh Giá Thuật Toán Viola-Jones

Để đánh giá hiệu quả phương pháp phát hiện khuôn mặt, chúng tôi sử dụng

hàm Viola-Jones được cài đặt sẵn trong bộ thư viện OpenCV và kiểm tra trên các

bộ dữ liệu chuẩn sau: Bao là bộ dữ liệu gồm 100 ảnh màu. Mỗi ảnh chứa một khuôn

mặt người ở các vị trí khác nhau như nghiêng đầu, xoay mặt về trái, về phải bao

gồm cả ảnh chứa nhiễu như bị mờ, nhòe, đội mũ, đeo kính, các biểu cảm khác nhau

trên khuôn mặt, có cả ngoại cảnh và người đứng phía sau. Đối tượng trong bộ dữ

liệu chủ yếu là người Châu Á với các độ tuổi khác nhau. AT&T là bộ dữ liệu của

Đại Học Cambrigde gồm 100 ảnh xám của 10 người khác nhau. Cứ mỗi 10 ảnh là

khuôn mặt của một người ở các góc độ, biểu cảm khác nhau. Đối tượng trong bộ dữ

liệu là người châu âu độ tuổi từ thanh niên đến cao niên, có một số đối tượng đeo

kính. Các ảnh trong bộ dữ liệu này chỉ chứa khuôn mặt, không có ngoại cảnh và các

yếu tố gây nhiễu, chụp ở độ sáng cố định. JAFFE là bộ dữ liệu của Psychology

Department, Kyushu University. Gồm 100 ảnh xám khuôn mặt chính diện của 6 cô

gái người Nhật với các biểu cảm khác nhau, được chụp trong nhiều điều kiện chiếu

sáng khác nhau. Ảnh được chụp với nền tĩnh và đơn sắc. Việc so khớp được thực

hiện như sau:

25

Hình 1.8: Kiểm tra kết quả chương trình so với bộ dữ liệu test

Theo Hình 1.8, hình chữ nhật viền đậm là hình chữ nhật có chứa khuôn mặt

được vẽ bằng tay. Hình chữ nhật viền mảnh là hình chữ nhật kết quả của chương

trình vẽ ra. Ta tính vùng giao A của 2 hình chữ nhật này. Sau đó tính tổng vùng

không giao của hai hình B + C rồi lấy tỉ lệ A/(B+C). Tỉ lệ này càng lớn chứng tỏ kết

quả của chương trình càng chính xác. Các trạng thái của kết quả phát hiện khuôn

mặt dựa trên tỉ lệ này như sau:

 Nếu tỉ lệ này < 1 thì kết quả của chương trình là 1 false face.

 Nếu tỉ lệ này >= 1 thì kết quả của chương trình là 1 correct face.

 Miss face được xác định bằng độ chệnh lệch giữa số lượng khuôn mặt phát

hiện được bằng chương trình với số lượng khuôn mặt được xác định bằng tay trước

đó.

Bảng 1.1 đánh giá xác định 3 trạng thái của kết quả phát hiện khuôn mặt:

Correct face (phát hiện đúng khuôn mặt), Miss face (không phát hiện ra khuôn mặt),

False face (phát hiện ra vùng ảnh không chứa khuôn mặt)

- Database - Correct - Total face

AT&T 100 Detect Status - Miss face 14 - False face 0 Hiệu suất = correct face/total face 86% face 86

Bao 100 13 1 87% 87

JAFFE 100 0 0 100% 100

Bảng 1.1: Bảng đánh giá thuật toán Viola - Jones

Thuật toán hoạt động khá ổn định trên 2 bộ dữ liệu khác nhau. Tuy nhiên,

trong quá trình test, trạng thái miss face xuất hiện tập trung ở các khuôn mặt

26

nghiêng và đeo kính như Hình 1.9. Dễ thấy rằng, vì bộ huấn luyện sử dụng huấn

luyện chủ yếu với các ảnh khuôn mặt chính diện và không đeo kính nên ảnh hưởng

tới độ chính xác khi làm việc với các khuôn mặt loại này. Để khắc phục tình trạng

trên, có thể tăng số ảnh huấn luyện bằng việc thêm vào các bộ ảnh khuôn mặt

nghiêng và đeo kính.

Hình 1.9: Kết quả phát hiện khuôn mặt bị sai lệch với khuôn mặt đeo kính

1.6. Adaboost

Adaboost (Adaptive Boost) [3] là một bộ phân loại mạnh phi tuyến phức dựa

trên hướng tiếp cận Boosting được Freund và Schapire đưa ra vào năm 1995.

Adaboost hoạt động dựa trên nguyên tắc kết kết hợp tuyến tính các Weak Classifier

dựa trên đặc trưng Haar-Like để hình thành một Classifier.

Tư tưởng của thuật toán Adaboost đấy là kết hợp các bộ phân loại yếu thành

một bộ phân loại mạnh. Trong quá trình xây dựng, bộ phân loại yếu tiếp theo sẽ

được xây dựng dựa trên các đánh giá về các bộ phân loại yếu trước, cuối cùng các

bộ phân loại yếu sẽ được kết hợp để trở thành bộ phân loại mạnh.

Để có thể kết hợp các bộ phân loại yếu, Adaboost sử dụng một trọng số

(weight) để đánh dấu các mẫu khó nhận dạng. Trong quá trình huấn luyện, cứ mỗi

weak classifier được xây dựng, thuật toán sẽ tiến hành cập nhật lại trọng số để

chuẩn bị cho việc xây dựng weak classifier tiếp theo: tăng trọng số của các mẫu bị

nhận dạng sai và giảm trọng số của các mẫu được nhận dạng đúng bởi weak

classifier vừa xây dựng. Bằng cách này, các weak classifier sau có thể tập trung vào

các mẫu mà các weak classifier trước đó chưa thực hiện tốt. Sau cùng các weak

27

classifier sẽ được kết hợp tùy theo mức độ ‘tốt’ của chúng để tạo nên một strong

classifier.

Viola và Jones dùng AdaBoost kết hợp các bộ phân loại yếu sử dụng các đặc

trưng Haar-like theo mô hình phân tầng (cascade) như sau:

Hình 1.10: Mô hình phân tầng kết hợp các bộ phân loại yếu để xác định khuôn mặt

Các Weak Classifiers hk(x) là các bộ phận loại yếu, được biểu diễn như sau:

(3) ℎ𝑘 = { 1 𝑛ế𝑢 𝑝𝑘𝑓𝑘(𝑥) < 𝑝𝑘𝜃𝑘 0 𝑛𝑔ượ𝑐 𝑙ạ𝑖

Trong đó:

- x : mẫu hay cửa sổ con cần xét (x=(x1,x2,.....,xn) là vectơ đặc trưng

của mẫu )

- 𝜃k : ngưỡng

- 𝑓𝑘 : giá trị của đặc trưng Haar-like

- 𝑝k : hệ số quyết định chiều của phương trình

Ý nghĩa của công thức (3):

Nếu giá trị đặc trưng của mẫu cho bởi hàm đánh giá của bộ phân loại vượt qua

một ngưỡng cho trước thì mẫu đấy là khuôn mặt (gọi là object: đối tượng cần nhận

dạng), ngược lại thì mẫu là background (không phải là đối tượng).

28

Adaboost sẽ kết hợp các bộ phận loại yếu thành bộ phân loại mạnh như sau:

H(x) = sign(α1h1(x) +α2h2(x) + ... + αnhn(x))

Với: αt >= 0 là hệ số chuẩn hóa cho các bộ phận loại yếu

Hình 1.11: Kết hợp các bộ phận loại yếu thành bộ phận loại mạnh

Tập các mẫu

Tập các mẫu và trọng số

đầu Bắt huấn luyện

Khởi tạo tập đặc trưng ban đầu

Mẫu đúng

Mẫu sai

Đặc trưng haar-like

Xác định các đặc trưng từng trong mẫu, xây dựng các bộ phân loại yếu tương ứng

Cập nhật lại trọng số

Tính toán giá trị lỗi cho mỗi đặc trưng (false alarm)

Sai

Xác định ngưỡng

Đúng

False alarm ≤ max false alarm

Lưu weak classifier được chọn

Chọn weak classifier có giá trị lỗi bé nhất

Kết thúc, strong classifier đuợc xây dựng

Sơ đồ khối:

Hình 1.12: Sơ đồ khối thuật toán Adaboost

Quá trình huấn luyện bộ phân loại được thực hiện bằng một vòng lặp mà ở

mỗi bước lặp, thuật toán sẽ chọn ra weak classifier ht thực hiện việc phân loại với

29

lỗi εt nhỏ nhất (do đó sẽ là bộ phân loại tốt nhất) để bổ sung vào strong classifier.

Mỗi khi chọn được 1 bộ phân loại ht, Adaboost sẽ tính giá trị 𝛼𝑡 theo công thức ở

trên. 𝛼𝑡 cũng được chọn trên nguyên tắc làm giảm thiểu giá trị lỗi εt.

𝑇

Hệ số 𝛼𝑡 nói lên mức độ quan trọng của ℎ𝑡: o Trong công thức của bộ phân loại H(x):

𝑡=1

) 𝐻(𝑥) = 𝑠𝑖𝑔𝑛 (∑ ∝𝑡 ℎ𝑡(𝑥)

Ta thấy tất cả các bộ phân loại ht đều có đóng góp vào kết quả của bộ phân

loại H(x), và mức độ đóng góp của chúng phụ thuộc vào giá trị αt tương ứng: ht với

αt càng lớn thì nó càng có vài trò quan trọng trong H(x).

o Trong công thức tính αt:

ln ( ) ∝𝑡= 1 2 1 − 𝜀𝑗 𝜀𝑗

Dễ thấy giá trị αt tỉ lệ nghịch với εj. Bởi vì ht được chọn với tiêu chí đạt εj nhỏ

nhất, do đó nó sẽ đảm bảo giá trị αt lớn nhất.

Sau khi tính được giá trị αt, Adaboost tiến hành cập nhật lại trọng số của các

mẫu: tăng trọng số các mẫu mà ht phân loại sai, giảm trọng số các mẫu mà ht phân

loại đúng. Bằng cách này, trọng số của mẫu phản ánh được mức độ khó nhận dạng

của mẫu đó và ht+1 sẽ ưu tiên học cách phân loại những mẫu này.

Vòng lặp xây dựng strong classifier sẽ dừng lại sau T lần lặp. Trong thực tế

cài đặt (thư viện OpenCV của Intel), người ta ít sử dụng giá trị T vì không có công

thức nào đảm bảo tính được giá trị T tối ưu cho quá trình huấn luyện. Thay vào đó,

người ta sử dụng giá trị max false positive hay max false alarm (tỉ lệ nhận dạng sai

tối đa các mẫu background). Tỉ lệ này của bộ phân loại cần xây dựng không được

phép vượt quá giá trị này. Khi đó, qua các lần lặp, false alarm của strong classifier

Ht(x) xây dựng được (tại lần lặp thứ t) sẽ giảm dần, và vòng lặp kết thúc khi tỉ lệ

này thấp hơn max false alarm.

30

1.7. Đặc trưng Haar wavelet

Một trong những phương pháp phát hiện mặt người hiệu quả hiện nay là phát

hiện mặt người sử dụng đặc trưng Haar dựa trên bộ phân loại tầng được để xuất bởi

Paul Viola và Michael Jones [4]. Đây là một phương pháp học máy dựa trên cách

tiếp cận sử dụng chức năng tầng được huấn luyện bởi cách ảnh đúng (Positive) và

ảnh sai (Negative) và sau đó dùng để phát hiện các đối tượng ở các ảnh khác.

Ở giai đoạn đầu tiên, thuật toán cần một số lượng lớn các ảnh đúng (các ảnh

khuôn mặt người) và các ảnh sai (ảnh không có khuôn mặt người) để huấn luyện

cho việc phân loại. Sau đó trích chọn các đặc trưng từ tập đặc điểm rất lớn. Để làm

điều này, các đặc trưng Haar được sử dụng. Mỗi đặc trưng là một giá trị đơn được

tính toán bằng cách đem tổng các điểm ảnh trong vùng đen trừ tổng các điểm ảnh ở

vùng trắng.

Bây giờ tất cả các kích thước và vị trí có thể của từng nhân sẽ được dùng để

tính toán các đặc trưng. Với mỗi đặc trưng, chúng ta tính tổng của các điểm ảnh

vùng đen và vùng trắng. Để giải quyết điều này chúng ta tạo ra các ảnh tích phân.

Điều này làm đơn giản hóa việc tính tổng các điểm ảnh và làm gia tăng tốc độ tính

toán.

Trong số tất cả các đặc trưng được tính toán, hầu hết chúng là không thích

hợp. Dòng đầu tiên đưa ra 2 đặc trưng tốt. Đặc trưng đầu tiên được lựa chọn tập

trung vào thuộc tính của vùng mắt thường tối hơn vùng mũi và má. Đặc trưng thứ 2

được lựa chọn lại dựa trên thuộc tính vùng mắt thường tối hơn vùng sống mũi.

Nhưng các cửa sổ tương tự được áp dụng trên má hay bất cứ chỗ nào khác đều là

không thích hợp. Vậy làm sao các đặc trưng tốt nhất trong hơn 160.000 đặc trưng

được lựa chọn ra một cách hiệu quả. Để cải thiện điều này chúng ta sử dụng

AdaBoost.

Với việc này, chúng ta áp dụng từng đặc trưng và mọi đặc trưng lên tất cả các

ảnh huấn luyện. Với mỗi đặc trưng, chúng ta sẽ tìm ra ngưỡng tốt nhất để phân loại

khuôn mặt là đúng hay sai. Nhưng rõ ràng, sẽ có lỗi hoặc phân loại sai, do đó chúng

ta chọn các đặc trưng với tỷ lệ lỗi nhỏ nhất, điều đó có nghĩa đó là sự phân loại tốt

31

nhất cho ảnh có mặt hay không có mặt. (Tiến trình thực tế không đơn giản như vậy,

mỗi ảnh sẽ được đánh các trọng số như nhau ở giai đoạn đầu. Tuy nhiên sau mỗi lần

phân loại, trọng số của các ảnh bị phân loại sai sẽ được tăng lên. Tiếp theo đó một

lần nữa tiến trình lại được thực hiện, tỷ lệ lỗi mới cũng như các trọng số mới được

tính toán. Tiến trình tiếp tục cho đến khi độ chính xác cần thiết hoặc tỷ lệ lỗi đạt

được con số mong muốn hoặc số lượng đặc trưng tốt được tìm đủ)

Bộ phân loại cuối là tổng các trọng số của các bộ phân loại yếu. Nó được gọi

là yếu vì nó không thể phân loại ảnh 1 mình nhưng khi kết hợp cùng những bộ phân

loại khác nó lại trở thành bộ phân loại mạnh. Thậm chí với 200 đặc trưng có thể

cung cấp sự phát hiện với độ chính xác lên đến 95%. Thiết lập cuối cùng của họ có

khoảng 6000 đặc trưng.

Trong 1 bức ảnh, hầu hết các vùng không phải là vùng mặt người. Điều này

dẫn đến 1 ý tưởng tốt hơn để có 1 phương thức đơn giản kiểm tra xem 1 cửa sổ có

phải vùng mặt người không. Nếu không phải, loại trừ vùng đó ngay, không xử lý lại

lần nữa, thay vào đó sẽ tập trung vào vùng có thể là mặt. Theo cách này, chúng ta

có thể có nhiều thời gian hơn để kiểm tra vùng mặt.

Hình 1. 13. Minh họa tầng phân loại

Định nghĩa tầng của sự phân loại, thay vì áp dụng 6000 đặc trưng trên 1 cửa

sổ, chúng ta sẽ nhóm các đặc trưng vào các giai đoạn khác nhau của sự phân loại và

áp dụng từng cái một. Nếu 1 cửa sổ khi kiểm tra bị sai ở giai đoạn đầu tiên, loại bỏ

cửa sổ đó luôn và chúng ta không cần xem xét đến các đặc trưng còn lại của cửa sổ

32

đó. Nếu vượt qua được giai đoạn đầu tiên, chúng ta sẽ áp dụng giai đoạn 2 với các

đặc trưng kế tiếp và tiếp tục xử lý. Cửa sổ được kiểm tra vượt qua mọi giai đoạn sẽ

là vùng mặt người.

Thiết lập hơn 6000 đặc trưng vào 38 giai đoạn với số lượng đặc trừng là 1, 10,

25, 25, 50 cho 5 giai đoạn đầu tiên. Trung bình 10 đặc trưng trong hơn 6000 đặc

trưng được đánh giá cho 1 cửa sổ con.

Tổng kết chương 1

Trong chương này, chúng tôi trình bày tổng quan về phát hiện mặt người trong

ảnh và video như phát hiện điểm, phép trừ nền, phân vùng, học có giám sát. Tìm

hiểu thuật toán Viola-Johns các vấn đề liên quan, đánh giá thuật toán Viola-Johns,

tìm hiểu về Adaboost, đặc trưng Haar wavelet trong phát hiện mặt người.

Chương 2, đề tài sẽ trình bày đặc trưng HOG, phương pháp phát hiện mặt

người sử dụng đặc trưng HOG, các bước rút trích đặc trưng HOG trong ảnh, chuẩn

hóa vector đặc trưng, tích phân ảnh, chuẩn hóa ánh sáng, sử dụng SVM trong việc

kết hợp với HOG phát hiện mặt người.

33

CHƯƠNG 2. ĐẶC TRƯNG HOG VÀ CÁCH SỬ DỤNG HOG KẾT HỢP VỚI SVM TRONG PHÁT HIỆN MẶT NGƯỜI

2.1. Phương pháp phát hiện mặt người sử dụng HOG.

Phương pháp phát hiện mặt người sử dụng HOG và cách tiếp cận SVM hiện là

một trong các phương pháp phát hiện mặt người phổ biến và thành công nhất hiện

nay.

Các đặc trưng HOG [5] ban đầu được thiết kế để phát hiện người (human

detection) trong dữ liệu ảnh nhưng sau đó được mở rộng và được sử dụng rộng rãi

cho các bài toán phát hiện đối tượng nói chung (object detection). Phương pháp

HOG dựa trên việc đếm số lần xuất hiện của các hướng đạo hàm (gradient

orientation) trong các vùng cục bộ của ảnh.

HOG là một dạng của mô tả đặc trưng. Mô tả đặc trưng có ý nghĩa trong việc

tổng quát hóa đối tượng theo một cách khác diễn tả khác để đối tượng tương đồng

(trong trường hợp này là mặt người) để có thể có các mô tả đặc trưng gần nhất với

nó nhất dù ở trong các điều kiện khác nhau. Với các mô tả đặc trưng công việc phân

loại trở nên dễ dàng hơn vì khi đó việc xem xét sự tương đồng của các đối tượng

được dựa trên việc tính toán khoảng cách giữa các mô tả đặc trưng, thường được

biểu diễn dưới dạng các vector đa chiều.

Hình 2.1. Mô hình phương pháp phát hiện khuôn mặt sử dụng đặc trưng HOG

34

Bản chất của phương pháp HOG là các thông tin về hình dáng và vẻ bề ngoài

của các đối tượng cục bộ trong ảnh có thể được mô tả bằng cách sử dụng thông tin

về sự phân bố của các cường độ gradient (intensity gradients) hoặc của các hướng

biên (edge directions). Các toán tử HOG được cài đặt bằng cách chia nhỏ một bức

ảnh thành các vùng con được gọi là các tế bào (cells) và với mỗi cell đó một

histogram về các hướng của gradients sẽ được tính cho các điểm nằm trong cell.

Ghép các histogram này lại ta sẽ có một biểu diễn cho bức ảnh ban đầu. Để tăng

cường hiệu năng nhận dạng, các histogram cục bộ có thể được chuẩn hóa về độ

tương phản bằng cách tính một ngưỡng cường độ trong một vùng lớn hơn của ảnh,

gọi là các khối (blocks) và sử dụng giá trị ngưỡng đó để chuẩn hóa tất cả các hình

ảnh trong các cell trong khối. Kết quả của bước chuẩn hóa này là vector đặc trưng

sẽ có tính bất biến cao hơn đối với các thay đổi về điều kiện ánh sáng.

Phương pháp phát hiện mặt người HOG có thể coi là một phương pháp tương

đối đơn giản so với các phương pháp khác. Một trong những nguyên nhân chính của

sự đơn giản này là phương pháp đã sử dụng đặc trưng toàn cục để mô tả mặt người

chứ không thu thập các đặc trưng cục bộ. Nói một cách đơn giản hơn, mỗi một mặt

người trong ảnh sẽ được đại diện bởi một vector đặc trưng.

Phương pháp này sử dụng một cửa sổ phát hiện dạng trượt với kích thước

64x128 di chuyển qua toàn bộ bức ảnh.

Hình 2.2: Minh họa các mẫu cửa sổ tìm kiếm kích thước 64x128

Tại mỗi cửa sổ này, Một mô tả HOG sẽ được tính toán cho cửa sổ tương ứng

bằng cách tạo ra các ô kích thước 8x8 trong cửa sổ tìm kiếm. Trong mỗi ô, các

35

vector gradient cho từng điểm ảnh sẽ được tính toán, vậy nên chúng ta sẽ có 64

vector cho 1 ô kích thước 8x8.

Hình 2.3: Minh họa ô kích thước 8x8 trong cửa sổ tìm kiếm

64 vector này sẽ được đặt vào 9 bin histogram (Khoảng của histogram chạy từ

0-180 và mỗi bin sẽ ứng với 1 vùng giá trị 20 độ). Với mỗi vector gradient, sự đóng

góp vào histogram chính là độ lớn của vector. Độ lớn này sẽ được phân chia vào 2

bin gần nhất. Ví dụ 1 vector có góc là 85 độ thì ¼ độ lớn của nó sẽ được thêm vào

bin 70 và ¾ độ lớn sẽ được thêm vào bin 90.

Hình 2.4: Minh họa cho HOG

Bước tiếp theo để tính toán vector đặc trưng là chuẩn hóa biểu đồ. Chúng ta có

thể nhân 1 lượng bất biến vào các giá trị của điểm ảnh. Điều này có thể dẫn tới việc

gia tăng độ tương phản do các điểm ảnh sáng sẽ sáng hơn nhiều trong khi điểm ảnh

tối chỉ sáng lên 1 chút.

36

Hình 2.5: Minh họa cho việc cộng thêm và nhân thêm vào giá trị của từng điểm ảnh

Ngoài ra điều này còn làm gia tăng độ lớn của vector gradient một lượng

bằng với lượng chúng ta nhân vào từng điểm ảnh nhưng khi đem chia vector đó cho

độ lớn của nó thì kết quả không đổi so với trước khi nhân. Từ đó có thể thấy kết quả

của vector gradient chia cho độ lớn của nó bất biến khi thay đổi điền kiện tương

phản. Chia vector cho độ lớn của nó có thể quy về chuẩn hóa vector tới độ dài đơn

vị vì vector kết quả có độ lớn bằng 1. Chuẩn hóa vector không ảnh hưởng đến

hướng mà chỉ ảnh hưởng đến độ lớn.

Hình 2.6: Minh họa cho sự thay đổi giá trị các vector gradient khi có sự thay đổi về ánh sáng

37

Giá trị của từng bin trong histogram được dựa trên độ lớn của các vector

gradient trong ô 8x8. Nếu mỗi ô được nhân với 1,5 chúng ta sẽ có độ lớn của mỗi

vector sẽ được nhân lên 1,5. Điều này có nghĩa độ lớn các bin cũng sẽ được nhân

lên 1,5. Thông qua chuẩn hóa chúng ta có thể có được sự bất biến trong cách thay

đổi ánh sáng này.

Chúng ta thay vì chuẩn hóa từng histogram riêng biệt của từng ô, các ô này

trước tiên sẽ được nhóm vào các khối và chuẩn hóa dựa trên tât cả histogram trong

khối đó. Các khối ở đây có kích thước 2x2 ô và có 50% bị chồng lấp (Có nghĩa 2

khối có các vùng chung). Việc chuẩn hóa khối này được thực hiện bởi sự móc nối

các histogram trong 4 ô của khối vào 1 vector có 36 thành phần (4 biểu đồ x 9 bin).

Chia vector này cho độ lớn của chúng để thực hiện chuẩn hóa. Ảnh hưởng của sự

chồng lấp các khối là mỗi ô được xuất nhiện nhiều lần trong bộ miêu tả cuối cùng,

nhưng được chuẩn hóa bởi tập khác nhau các ô lân cận.

Hình 2.7: Hình ảnh minh họa cho sự gộp các ô để tạo nên các khối có sự chồng lấp.

Cửa sổ kích thước 64x128 được chia làm 7x15 khối, mỗi khối chứa 4 ô với 9

bin cho từng ô nên sẽ có 36 giá trị cho từng khối. Điều này mang tới kích thước

cuối cùng của vector là 7 x 15 x 4 x 9 = 3780 giá trị.

Vector đặc trưng này sau đó sẽ được huấn luyện SVM (để phân biệt đây là

người hay không phải người). Để phát hiện người với các tỷ lệ khác nhau, hình ảnh

sẽ được tạo các mẫu phụ với các kích thước khác nhau để sau đó từng mẫu phụ sẽ

được tìm kiếm.

38

HOG là đặc trưng được dùng nhiều trong lĩnh vực phát hiện đối tượng. Kỹ

thuật này được đề xuất bởi Bill Triggs và Navel Dalal vào năm 2005 tại viện nghiên

cứu INRIA.

Ý tưởng chính trong đặc trưng HOG là hình dạng và trạng thái của vật có thể

được đặc trưng bằng sự phân bố về gradient và hướng của cạnh. Đặc trưng này

được phát triển dựa trên SIFT, đặc trưng HOG được tính trên cả một vùng. Do sự

biến thiên màu sắc trong vùng là khác nhau, kết quả là mỗi vùng sẽ cho ta một

vector đặc trưng của nó. Vì vậy để có được đặc trưng của toàn bộ cửa sổ (window)

ta phải kết hợp nhiều vùng liên tiếp lại với nhau.

Đặc trưng HOG có một số biến thể thường gặp như: R-HOG, R2-HOG, C-

HOG [6]. Các đặc trưng này khác nhau ở cách phân bố và hình dạng của các ô như

trong hình

Hình 2.8: R-HOG và C-HOG [7]

 R-HOG: mỗi ô có hình dạng là hình chữ nhật

 C-HOG: mỗi ô có dạng hình tròn

2.2. Rút trích đặc trưng HOG trong ảnh

Từ một ảnh cho trước, qua việc rút trích đặc trưng trên ảnh đó cho ta được một

vector đại diện đối tượng đó. [8] Việc rút ra được các vector đặc trưng như vậy giúp

chúng ta chuyển không gian ảnh sang không gian vector để có thể xử lý và tính toán

đơn giản trên máy tính.

Phương pháp tổng quan để tính toán đặc trưng HOG trên một cửa số bất kỳ:

39

 Phân chia cửa sổ (window) cần tính HOG thành nhiều khối (block). Mỗi

khối gồm nhiều ô (cell). Các ô phải có kích thước bằng nhau, số lượng ô trong mỗi

khối là bằng nhau.

 Các khối này được đặt chồng lên nhau, khoảng cách giữa hai khối con liên

tiếp nhau phải là một hằng số

Hình 2.9: Mỗi khối (block) gồm nhiều ô (cell). Trong hình trên ta thấy một khối gồm 9 ô

Hình 2.10: Các khối được xếp chồng lên nhau

 Sau khi đã phân chia cửa sổ cần tính toán HOG như trên. Ta tiến hành rút

trích đặc trưng như sau:

o Tính toán đặc trưng trên từng vùng:

 Tính toán đặc trưng trên từng ô nhỏ (cell)

 Tính toán đặc trưng trên từng khối (block) bằng cách kết hợp

các ô lại với nhau

o Thu thập đặc trưng của các vùng trên ảnh

 Tính và chuẩn hóa vector đặc trưng cho từng block

 Thu thập các đặc trưng HOG cho các cửa sổ

Sau đây là chi tiết thuật toán rút trích đặc trưng HOG [8]. Để minh họa thuật

toán, ta có thể chọn một ví dụ như sau để tính vector đặc trưng HoH và số lượng

40

thành phần của vector đó: giả sử ta có một ảnh với kích thước là 64x128 pixels. Ta

chia ảnh này thành các cell với kích thước 8x8 pixels. Và ta chọn kích thước của

block là 2x2 cell.

 Bước 1: Chuyển ảnh trong không gian RGB sang ảnh dạng GRAY SCALE,

sau đó tiến hành cân bằng histogram trên ảnh GRAY SACLE để giảm đi ảnh hưởng

của sự thay đổi ánh sáng.

 Bước 2: Tính sự biến thiên màu sắc tại tất cả các pixel của ảnh GRAY

] và thu được 2 ảnh gradient-x SCALE theo chiều 𝑋[−1 0 1] và theo chiều Y [

−1 0 1

(đạo hàm theo trục x) và gradient-y (đạo hàm theo trục y) có kích thước bằng kích

thước ảnh GRAY SCALE và cho thấy được sự biến thiên màu sắc nói trên.

 Bước 3: Tiến hành tính góc và hướng biến thiên màu sắc từ 2 ảnh gradient-x

và gradient-y như hình vẽ bên dưới:

Hình 2.11: Tính góc và biên độ theo X-gradient và Y-gradient

Việc lưu trữ chính xác từng giá trị góc (orientation) của từng vị trí (𝑥, 𝑦)

không mang lại nhiều kết quả, do vậy ta sẽ chia không gian góc ra thành các bin.

Việc phân chia bin càng nhỏ sẽ càng làm tăng độ chính xác, thực nghiệm [8] cho

thấy kích thước bin khoảng 200 cho kết quả tốt nhất. Do đó từ 0° - 180° ta chia

thành 9 bin như sau:

[0° - 20°], [21° - 40°] [41° -60°], [61° - 80°], [81° - 100°], [101°- 120°], [121°

- 140°], [141°- 160°], [161° - 180°]

 Bước 4: Ứng với mỗi bin trên ta tiến hành thống kê biên độ (magnitude) tại

từng vị trí. Với mỗi bin, tại vị trí (𝑥, 𝑦) nếu như góc (orientation) thuộc về bin đó thì

41

giá trị của bin đó tại vị trí (𝑥, 𝑦) bằng giá trị biên độ (magnitude), ngược lại giá trị

bin tại vị trí (𝑥, 𝑦) bằng 0.

 Bước 5: Tính toán vector đặc trưng cho từng cell (8x8). Vector đặc trưng của

mỗi cell sẽ gồm 9 thành phần tương ứng với 9 bin, và giá trị tại thành phần 𝑖 bằng

tổng giá trị của các điểm trong bin 𝑖 mà có tọa độ nằm trong cell đó.

 Bước 6: Tính toán vector đặc trưng cho từng block (16x16). Ta chỉ cần ghép

các vector đặc trưng của từng cell trong block lại với nhau để được vector đặc trưng

của một block và chuẩn hóa lại vector đặc trưng của block này. Số thành phần của

vector đặc trưng tại mỗi khối được tính theo công thức:

𝑆𝑖𝑧𝑒𝑓𝑒𝑎𝑡𝑢𝑟𝑒/𝑏𝑙𝑜𝑐𝑘 = 𝑛𝑐𝑒𝑙𝑙 × 𝑆𝑖𝑧𝑒𝑓𝑒𝑎𝑡𝑢𝑟𝑒/𝑐𝑒𝑙𝑙

Trong đó: 𝑆𝑖𝑧𝑒𝑓𝑒𝑎𝑡𝑢𝑟𝑒/𝑏𝑙𝑜𝑐𝑘 là đặc trưng trong block, 𝑛𝑐𝑒𝑙𝑙 là số cell trong một

block, 𝑆𝑖𝑧𝑒𝑓𝑒𝑎𝑡𝑢𝑟𝑒/𝑐𝑒𝑙𝑙 là số feature trong một cell. Với giả thiết mỗi cell có kích

thước 8x8 pixels, mỗi block có kích thước 2x2 cells (16x16 pixels), không gian

hướng biến thiên xét trong miền miền từ 00 - 1800 và được chia thành 9 bin thì số

đặc trưng trong mỗi khối sẽ được tính bằng 4x9 = 36 thành phần.

 Bước 7: Tính toán vector đặc trưng cho toàn bộ ảnh (64x128). Ta chỉ cần

ghép các vector đặc trưng của từng block lại với nhau để được vector đặc trưng của

các window. Trong đó, một cửa sổ (Window) được tạo bởi các khối xếp gối nhau

overlapping. Đặc trưng của một cửa sổ sẽ được tính bằng cách ghép các vector đặc

trưng của từng block tạo lên cửa sổ đó. số thành phần đặc trưng của mỗi cửa sổ

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

+ 1) 𝑛𝑏𝑙𝑜𝑐𝑘/𝑤𝑖𝑛𝑑𝑜𝑤 = (

+ 1) × ( 𝑊𝑤𝑖𝑛𝑑𝑜𝑤 − 𝑊𝑏𝑙𝑜𝑐𝑘 × 𝑊𝑐𝑒𝑙𝑙 𝑊𝑐𝑒𝑙𝑙 𝐻𝑤𝑖𝑛𝑑𝑜𝑤 − 𝐻𝑏𝑙𝑜𝑐𝑘 × 𝐻𝑐𝑒𝑙𝑙 𝐻𝑐𝑒𝑙𝑙

𝑆𝑖𝑧𝑒𝑓𝑒𝑎𝑡𝑢𝑟𝑒/𝑤𝑖𝑛𝑑𝑜𝑤 = 𝑛𝑏𝑙𝑜𝑐𝑘/𝑤𝑖𝑛𝑑𝑜𝑤 × 𝑆𝑖𝑧𝑒𝑓𝑒𝑎𝑡𝑢𝑟𝑒/𝑏𝑙𝑜𝑐𝑘

- Trong đó: 𝑊𝑤𝑖𝑛𝑑𝑜𝑤 𝑊𝑏𝑙𝑜𝑐𝑘 𝑊𝑐𝑒𝑙𝑙 lần lượt là chiều rộng của window, block

và cell (tính theo đơn vị pixel); 𝐻𝑤𝑖𝑛𝑑𝑜𝑤 𝐻𝑏𝑙𝑜𝑐𝑘 𝐻𝑐𝑒𝑙𝑙 lần lượt là chiều cao của

window, block và cell (tính theo đơn vị pixel); 𝑛𝑏𝑙𝑜𝑐𝑘/𝑤𝑖𝑛𝑑𝑜𝑤 là số block trong một

42

cửa sổ, 𝑆𝑖𝑧𝑒𝑓𝑒𝑎𝑡𝑢𝑟𝑒/𝑤𝑖𝑛𝑑𝑜𝑤 là số đặc trưng trong một cửa sổ. Ở bước xử lý cuối

cùng, toàn bộ vector đặc trưng thu được trên mỗi cứa sổ sẽ được sử dụng làm đầu

vào của bộ phân lớp tuyến tính SVM. [9]

Lưu ý rằng các block không đặt tách biệt nhau mà gối lên nhau, cách nhau một

khoảng bằng kích thước của cell theo mỗi chiều (hoặc bằng phân nửa kích thước

của cell). Như vậy vector đặc trưng của window = số block trong window*36=((64-

16)/8+1)*((128-16)/8+1)*36 = 7*15*36=3780 thành phần.

 Bước 8: Sau cùng ta chuẩn hóa lại vector đặc trưng của cả window.

Hình 2.12: Các bước rút trích đặc trưng HOG [10]

2.3. Chuẩn hóa vector đặc trưng cho từng block

Để chuẩn hóa vector đặc trưng cho cả window, ta chuẩn hóa đặc trưng cho

từng vector của từng block. Ta sử dụng các phương pháp sau để chuẩn hóa vector

𝑣

đặc trưng của từng block. [7]

2+𝑒2

√‖𝑣‖2

 L2-norm: 𝑓 =

𝑣 (‖𝑣‖1+𝑒)

 L1-norm: 𝑓 =

43

𝑣 (‖𝑣‖1+𝑒)

 L1-sqrt: 𝑓 = √

Trong đó:

 𝑣: vector đặc trưng ban đầu của một block (chưa chuẩn hóa).

 ‖𝑣‖k là k-norm của 𝑣 với 𝑘=1,2

 𝑒: Hằng số nhỏ

Theo Dalal và Triggs, L2-norm và L1-sqrt cho kết quả tương tự. Trong khi đó

L1-norm cho kết quả kém hơn. Tuy vậy việc chuẩn hóa bằng một trong các phương

pháp trên vẫn cho kết quả tốt hơn đối với những vector không chuẩn hóa.

2.4. Integral Image, công thức đệ quy tính Integral Image

 Integral Image: Từ bước 5, 6, 7 ta nhận thấy là ta cần tính đặc trưng cho

từng cell rất nhiều lần, do vậy ở đây có thể sử dụng kỹ thuật integral image để làm

tăng tốc độ tính toán.

Hình 2.13: Integral Image [11]

Ảnh Integral là ảnh có tính chất sau: giá trị của pixel tại vị trí (𝑥, 𝑦) bất kỳ

trong ảnh Integral bằng với tổng số các pixel thuộc hình chữ nhật được tạo bởi điểm

góc trái trên cùng của ảnh (0,0) và điểm (𝑥, 𝑦) đang xét. Công thức tính integral

image:

𝑥′≤𝑥,𝑦′≤𝑦′

𝑖𝑖(𝑥, 𝑦) = ∑ 𝑖(𝑥′, 𝑦′)

Trong đó:

 𝑖: ảnh ban đầu

 𝑖𝑖: ảnh integral của 𝑖

Ảnh integral của một ảnh cho trước được tính theo công thức trên. Như áp

dụng integral image vào để tính giá trị tại mỗi bin của vector đặc trưng của từng cell

44

rất nhanh chóng. Giả sử ta cần tính giá trị vector đặc trưng của cell D (như trên

hình) tại thành phần 𝑖, khi đó ta chỉ cần lấy ảnh integral image của anh bin 𝑖 đã tính

ở trên, ta thu được ảnh 𝑖𝑖. Khi đó giá trị cần tính sẽ bằng:

𝑉𝑖 = 𝑖𝑖(𝑥1, 𝑥1) + 𝑖𝑖(𝑥4, 𝑥4) − 𝑖𝑖(𝑥2, 𝑥2) − 𝑖𝑖(𝑥3, 𝑥3)

Lưu ý rằng ta chỉ cần tính integral image duy nhất 1 lần và dùng nó để tính

cho toàn bộ các cell. Ưu điểm của cách tính này là ta chỉ cần biết giá trị ảnh Integral

của bốn góc hình chữ nhật là có thể dễ dàng tính được vector của hình chữ nhật đó.

 Công thức đệ quy tính Integral Image: Để tính nhanh Integral Image ta có

thể dùng công thức đệ quy sau [11] [5]:

𝑠(𝑥, 𝑦) = 𝑠(𝑥, 𝑦 − 1) + 𝑖(𝑥, 𝑦)

𝑖𝑖(𝑥, 𝑦) = 𝑖𝑖(𝑥 − 1, 𝑦) + 𝑠(𝑥, 𝑦)

Với giá trị khởi tạo: 𝑠(𝑥, −1) = 0

𝑖𝑖(−1, 𝑦) = 0

Trong đó:

𝑖: ảnh ban đầu

𝑖𝑖: ảnh integral của 𝑖

𝑠: giá trị trung gian

Ta có thể hiểu công thức đệ quy trên như sau, để tính 𝑖𝑖 ta sẽ tính theo từng

dòng và tính dòng tiếp theo ta sẽ dùng kết quả của dòng trước. Như vậy có thể thấy

độ phức tạp của việc tính integral image là 𝑂(𝑛)

2.5. Chuẩn hóa ánh sáng với bộ lọc Retinal filter

Bộ lọc Retinal filter ban đầu được phát triển như một bộ lọc ảnh thông thường

dựa vào việc mô phỏng các bước trong hệ thống nhận dạng hình ảnh của con người

[12]. Sau đó nó được áp dụng cho bài toán nhận dạng mặt với mục đích chuẩn hóa

ánh sáng ở bước tiền xử lý và đã chứng tỏ được tính hiệu quả của mình.

Về cơ bản bộ lọc thực hiện mô phỏng hoạt động của hai lớp chính của hệ

thống thị giác của con người là lớp Photoreceptor và Outer Plexiform bằng cách áp

dụng liên tiếp hai hàm phi tuyến, bộ lọc DoG và một hàm cắt hậu xử lý như được

minh họa trong hình 2.14.

45

Hình 2.14 Các bước trong bộ lọc Retinal filter

Hàm Naka-Rushton [13] được sử dụng để tăng cường độ tương phản cục bộ

của bức ảnh theo công thức sau:

𝑌 = 𝑋 𝑋 + 𝑋0

Trong đó X là ảnh input, X0 là tác nhân điều chỉnh và có giá trị thay đổi với

mỗi điểm ảnh còn Y là ảnh output.

Từ ảnh input I ban đầu, bộ lọc Retinal filter sử dụng hai bộ lọc thông thấp liên

tiếp với công thức (xuất phát từ công thức của hàm Naka-Rushton ở trên) như sau:

𝐼𝑙𝑎1 = (max(𝐼) + 𝐹1(𝑝))

𝐼𝑙𝑎2 = (max(𝐼𝑙𝑎1) + 𝐹2(𝑝)) 𝐼(𝑝) 𝐼(𝑝) + 𝐹1(𝑝) 𝐼𝑙𝑎1(𝑝) 𝐼𝑙𝑎1(𝑝) + 𝐹2(𝑝)

Trong đó các biểu thức (max(I)+F1(p)) và (max(Ila1)+F2(p)) đóng vai trò là các

nhân tố chuẩn hóa và hàm max là hàm trả về giá trị cường độ sáng lớn nhất của ảnh.

Hai biểu thức F1(p) và F2(p) được tính theo các công thức sau:

𝐹1(𝑝)) = 𝐼(𝑝) ∗ 𝐺1 +

𝐹2(𝑝)) = 𝐼𝑙𝑎1(𝑝) ∗ 𝐺2 + 𝐼̅ 2 𝐼𝑙𝑎1̅̅̅̅̅ 2

Ký hiệu ‘*’ là ký hiệu của phép nhân chập, ̅ là ký hiệu của hàm tính trung

bình, G1, G2 là các bộ lọc Gaussian tương ứng với hai độ lệch chuẩn 𝜎1 và 𝜎2

−

𝑥2+𝑦2 2𝜎1

𝑥2+𝑦2 2 , 2𝜎2

như sau:

2 , và 𝐺2(𝑥, 𝑦) =

2 𝑒

2 𝑒

1 2𝜋𝜎1

1 2𝜋𝜎2

𝐺1(𝑥, 𝑦) =

46

Ảnh Ila2 sau đó được xử lý bằng một bộ lọc DoG để cải thiện các thuộc tính

sắc nét như sau:

𝐼𝑑𝑜𝑔 = 𝐷𝑜𝐺 ∗ 𝐼𝑙𝑎2

−

−

𝑥2+𝑦2 2 2𝜎𝑝ℎ

𝑥2+𝑦2 2 2𝜎𝐻

trong đó DoG được tính theo công thức:

2 𝑒

2 𝑒

− 𝐷𝑜𝐺1 = 1 2𝜋𝜎𝐻 1 2𝜋𝜎𝑝ℎ

Với 𝜎𝑃ℎ = 0.5 và 𝜎𝐻 = 4. Vì bộ lọc DoG làm giảm độ tương phản toàn cục của

bức ảnh nhận được nên một bước cắt bỏ các giá trị quá lớn sẽ được thực hiện sau

khi ảnh được chuẩn hóa để có giá trị trung bình bằng 0 như sau:

= 𝐼𝑛𝑜𝑟𝑚 = 𝐼𝑑𝑜𝑔 − 𝐼𝑑𝑜𝑔̅̅̅̅̅ 𝑠𝑡𝑑(𝐼𝑑𝑜𝑔) 𝐼𝑑𝑜𝑔 𝑠𝑡𝑑(𝐼𝑑𝑜𝑔)

𝐼𝑟𝑒𝑠𝑢𝑙𝑡(𝑝) = { max (𝑇ℎ, |𝐼𝑛𝑜𝑟𝑚(𝑝)|𝑛ế𝑢 𝐼𝑛𝑜𝑟𝑚(𝑝) ≥ 0 −max (𝑇ℎ, |𝐼𝑛𝑜𝑟𝑚(𝑝)|𝑛ế𝑢 𝑛𝑔ượ𝑐 𝑙ạ𝑖

Kết quả của bộ lọc Retina filter trong việc chuẩn hóa ánh sáng của các ảnh mặt

được thu nhận trong các điều kiện sáng khác nhau có thể thấy trong hình minh họa

2.15. Có thể thấy rằng kết quả của bộ lọc này khá tốt và đạt được 2 mục đích:

+ Đưa các bức ảnh mặt có điều kiện ánh sáng khác nhau về cùng một vùng giá

trị khá gần nhau.

+ Tăng cường các đường nét quan trọng của khuôn mặt khi áp dụng cho bài

toán nhận dạng mặt người, chẳng hạn như lông mày, mắt, mũi và mồm.

Hình 2.15: Kết quả của việc tiền xử lý với bộ lọc Retina filter

47

2.6. Phương pháp phân lớp SVM

SVM (Support Vector Machine) là một khái niệm trong thống kê và khoa học

máy tính cho một tập hợp các phương pháp học có giám sát liên quan đến nhau

để phân loại và phân tích hồi quy.

SVM là một thuật toán phân loại nhị phân, SVM nhận dữ liệu vào và phân loại

chúng vào hai lớp khác nhau. Với một bộ các ví dụ luyện tập thuộc hai thể loại cho

trước, thuật toán luyện tập SVM xây dựng một mô hình SVM để phân loại các ví dụ

khác vào hai thể loại đó.

Hàm mục tiêu của một máy phân lớp SVM nhị phân có thể được phát biểu

như sau: [15]

𝑔(𝑥) = 𝑤. 𝛷(𝑥) + 𝑏 (4)

Trong đó, véc tơ đầu vào 𝑥 ∈ 𝑅𝐷 , w là véc tơ chuẩn của siêu phẳng phân cách

trong không gian đặc trưng được sinh ra từ ánh xạ Φ(x): 𝑅𝐷 – 𝑅𝐹 (F > D, Φ(x) có

thể tuyến tính hoặc phi tuyến) và b là độ lệch so với gốc tọa độ. Ban đầu, SVM

được thiết kế cho bài toán phân lớp nhị phân, do đó dấu của g(x) cho biết véc tơ x

thuộc lớp +1 hay lớp -1.

Cho tập mẫu {(𝑥1, 𝑦1,),...,( 𝑥𝑁,, 𝑦𝑁,)} trong đó xi∈𝑅𝐷 và yi∈{±1}, mục tiêu của phương pháp phân lớp SVM là tìm một siêu phẳng phân cách sao cho khoảng

cách lề (margin) giữa hai lớp đạt cực đại (Hình 2.16).

Hình 2. 17. Siêu phẳng tách với khoảng cách lề cực đại

48

2

2

𝑊.𝑊

‖𝑤‖2 Để nới lỏng điều kiện phân lớp, thêm vào một số yếu tố cân bằng và việc huấn luyện SVM chính là giải bài toán tối

Khoảng cách lề giữa hai lớp là =

1

ưu có ràng buộc:

𝑁 𝑖=1

2

(5) 𝑤. 𝑤 + 𝐶 ∑ 𝜉𝑖 min 𝑤,𝑏

Sao cho

𝑦𝑖(𝑤. 𝛷(𝑥𝑖) + 𝑏) ≥ 1 − 𝜉𝑖

𝜉𝑖 ≥ 0, ∀i, trong đó C là tham số nới lỏng điều kiện phân lớp [15]

Thay vì giải bài toán (5), ta giải bài toán đối ngẫu của nó bằng cách giải bài

1

toán qui hoạch toàn phương (QP-Quadratic programming):

2

𝛼𝑇𝐻𝛼) (6) 𝛼1 − max ( 𝛼

𝑁 𝑖=1

= 0

thỏa mãn: 0 ≤ 𝛼 ≤ 𝐶, ∀𝑖 và ∑ 𝛼𝑖𝑦𝑖 trong đó 𝛼 = [𝛼1, . . . , 𝛼𝑁] 𝑇và H là ma trận kích thước N×N được gọi là ma

trận nhân (kernel matrix) với mỗi phần tử 𝐻(𝑖, 𝑗) = 𝑦𝑖𝑦𝑗𝛷(𝑥𝑖). 𝛷(𝑥𝑗).

Giải bài toán QP (6) ta thu được:

𝑁 𝑖=1

(7) 𝑤 = ∑ 𝛼𝑖𝑦𝑖𝛷(𝑥𝑖)

Mỗi mẫu huấn luyện xi tương ứng với một hệ số Lagrange 𝛼𝑖. Sau khi huấn

luyện, các mẫu có 𝛼𝑖>0 được gọi là véc tơ hỗ trợ.

Thế (7) vào (4), ta có :

𝑁 𝑔(𝑥) = ∑ 𝛼𝑖𝑦𝑖𝛷(𝑥𝑖) 𝑖=1

. 𝛷(𝑥) + 𝑏 (8)

Giả sử 𝛷(𝑥𝑖). 𝛷(𝑥𝑗) = 𝐾(𝑥𝑖, 𝑥𝑗). Nghĩa là, tích vô hướng trong không gian

đặc trưng tương đương với một hàm nhân K của không gian đầu vào. Vì vậy, ta

không cần phải tính trực tiếp các giá trị Φ(𝑥𝑖), Φ(𝑥𝑗) mà chỉ cần tính tích vô hướng

<Φ(𝑥𝑖).Φ(𝑥𝑗)> gián tiếp thông qua hàm nhân K(𝑥𝑖, 𝑥𝑗). Nếu sử dụng hàm nhân là

hàm tuyến tính thì SVM được gọi là SVM tuyến tính, ngược lại thì gọi là SVM phi

tuyến. Như vậy, hàm mục tiêu cho bài toán phân lớp SVM nhị phân có dạng:

𝑁 𝑔(𝑥) = ∑ 𝛼𝑖𝑦𝑖𝐾( 𝑖=1

(9) 𝑥𝑖, 𝑥) + 𝑏

49

Chỉ có các véc tơ hỗ trợ tham gia vào việc xây dựng siêu phẳng phân cách, do

đó một mẫu x sẽ được phân lớp theo hàm quyết định:

𝑁𝑆𝑉 𝑖=1

(10) 𝑓(𝑥) = 𝑠𝑔𝑛(∑ 𝛼𝑖𝑦𝑖𝐾 (𝑥𝑖, 𝑥) + 𝑏)

Trong đó, NSV là số véc tơ hỗ trợ.

 Các bước để phát hiện mặt người với đăc trưng HOG

1. Chuẩn bị P mẫu là ảnh mặt người và trích xuất các vector đặc trưng HOG từ

các bức ảnh này

2. Chuẩn bị N mẫu là ảnh không phải là ảnh mặt người (N rất lớn so với P) và

trích xuất các vector HOG từ các bức ảnh này

3. Sử dụng bộ phân loại SVM tuyến tính để học với các vector của các mẫu

đúng (Positive) và mẫu sai (Negative) đã chuẩn bị

4. Đối với mỗi bức ảnh trong bộ ảnh mẫu đúng, sử dụng một cửa sổ trượt di

chuyển qua tất cả các vị trí có thể của ảnh input. Tại mỗi vị trí của cửa sổ trượt tính

vector HOG của cửa sổ và đưa vào bộ phân lớp. Nếu bộ phân lớp phân lớp sai một

cửa sổ là ảnh mặt thì ghi lại vector tương ứng cùng với xác xuất phân lớp

5. Lấy các mẫu nhận dạng sai ở bước 4 xắp sếp chúng theo mức nhận dạng sai

và cho bộ phân lớp học lại sử dụng các mẫu sai này

6. Áp dụng bộ phân lớp đã được học lại với các ảnh cần phát hiện mặt người

Tổng kết chương 2

Trong chương này, chúng tôi đã trình bày đặc trưng HOG, phương pháp phát

hiện mặt người sử dụng đặc trưng HOG, các bước rút trích đặc trưng HOG trong

ảnh, chuẩn hóa vector đặc trưng cho từng block, tích phân ảnh Integral Image,

chuẩn hóa ánh sáng với bộ lọc Retinal filter, phương pháp phân lớp SVM trong việc

kết hợp với HOG phát hiện mặt người.

Chương 3, luận văn sẽ trình bày xây dựng chương trình, môi trường thử

nghiệm, dữ liệu thử nghiệm, kết quả thử nghiệm và đánh giá kết quả. Giao diện và

hoạt động của chương trình.

50

CHƯƠNG 3. XÂY DỰNG CHƯƠNG TRÌNH, THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ

3.1. Môi trường thử nghiệm

Chương trình được cài đặt trong môi trường Visual Studio, sử dụng các thư

viện C++ cho việc biểu diễn, lưu trữ và thao tác dữ liệu, thư viện opencv để thực

hiện các thao tác xứ lý ảnh cơ bản, thư viện Scikit-Leam cho việc thử nghiệm các

mô hình học máy (mạng neural, mô hình SVM...). Chương trình được thử nghiệm

trên hệ điều hành Windows 10, máy PC tốc độ 2.4GHz, bộ nhớ 4GB.

3.2. Dữ liệu thử nghiệm

Hiệu quả của mô hình nhận dạng được đánh giá trên các bộ cơ sở dữ liệu

chuẩn (chứa các khung hình được thu nhận từ các thiết bị camera, webcam khác

nhau), được công bố dùng chung cho các nhóm nghiên cứu trên thế giới, được cung

cấp tại http://www.face-rec.org/databases, Đây là các CSDL dùng chung cho các

nhóm nghiên cứu. Thông tin của CSDL mẫu được mô tả cụ thể như sau:

3.2.1. Cơ sở dữ liệu UOF

Được cung cấp bởi trường đại học Essex của Anh (University of Essex, UK),

bao gồm 4 tập dữ liệu: faces94, faces95, faces96 và grimace. Ảnh trong cơ sở dữ

liệu là ảnh màu 24 bít định dạng dạng JPEG. Tập dữ liệu chứa một tập hợp các hình

ảnh khuôn mặt gôm 395 cá nhân (cả nam và nữ) với 20 ảnh cho mỗi cá nhân, tổng

cộng có 7900 hình ảnh. Tất cả khuôn mặt chủ yếu được thực hiện bởi các sinh viên

đại học năm đầu tiên có độ tuổi từ 18 đến 20 và một số người lớn tuổi, một số cá

nhân đeo kính và có râu, thuộc nhiều chủng tộc khác nhau (hình 3.1).

51

Hình 3.1: Cơ sở dữ liệu mẫu UOF

3.2.2. Cơ sở dữ liệu FEI

Bao gồm các tập dữ liệu: Fei_Pl, Fei_P2 và Fei_P3, với các ảnh khuôn mặt

được chụp từ tháng 6 năm 2005 đến tháng 3 năm 2006 tại Phòng thí nghiệm Trí tuệ

nhân tạo FEI ở Paulo, Brazil. Bao gồm 200 cá nhân (100 nam, 100 nữ), với 14 ảnh

cho mỗi cá nhân, tổng cộng 2800 hình ảnh. Tất cả khuôn mặt chủ yếu được thực

hiện bởi các sinh viên và nhân viên của FEI, có độ tuổi từ 19 đến 40, với ngoại

hình, kiểu tóc và đồ trang điểm khác biệt, đều được chụp trên nền ảnh mầu trắng, ở

vị trí đứng thẳng đứng và quay vòng lần lượt tới 1800. Kích thước của mỗi ảnh là

640x480 pixel (hình 3.2).

Hình 3.2: Cơ sở dữ liệu mẫu FEI

3.2.3. Cơ sở dữ liệu JAFFE

Chứa các khuôn mặt nữ Nhật Bản, được chụp tại khoa tâm lý học của Đại học

Kyushu, Nhật Bản, bao gồm 213 hình ảnh của 7 biểu hiện khuôn mặt (6 biểu hiện

52

cảm xúc cơ bản trên khuôn mặt + 1 trung tính), được chụp bởi 10 người phụ nữ

Nhật Bản (Hình 3.3).

Hình 3.3: Cơ sở dữ liệu mẫu JAFFE

3.2.4. Cơ sở dữ liệu LFW

Bao gồm những khuôn mặt được gắn nhãn trong tự nhiên. Bộ dữ liệu gồm

13233 hình ảnh khuôn mặt của 5749 người được thu thập từ web. Mỗi khuôn mặt

được gắn nhãn với tên của người đó, trong đó 1680 người có từ 2 hình ảnh khác biệt

trở lên (hình 3.28).

Hình 3.4: Cơ sở dữ liệu mẫu LFW

3.3. Kết quả thử nghiệm

Quá trình đánh giá thực nghiệm được chia thành 2 công đoạn: Đánh giá hiệu

quả của mô hình phát hiện khuôn mặt người trên khung hình webcam và đánh giá

53

độ chính xác nhận dạng. Hiệu quả của mô hình phát hiện khuôn mặt được đánh giá

dựa trên các độ đo được định nghĩa cụ thể trong phần sau đây:

■ Độ chính xác phát hiện khuôn mặt DP (Detection Precision):

DP = Số vùng khuôn mặt phát hiện đúng trên tổng số khuôn mặt cần phát hiện

■ Khả năng tìm hết DR (Detection Recall):

DR = Số vùng khuôn mặt phát hiện đúng /(Số vùng khuôn mặt phát hiện đúng

+ Số vùng không được phát hiện)

■ Độ trung bình điều hòa DM (Dectection F-Measure):

DM = (2xFDP*FDR)/(FDP+FDR)

Bên cạnh đó, để các kết quả thực nghiệm chính xác và trực quan, trong quá

trình thử nghiệm, chúng tôi đã so sánh hiệu quả của mô hình phát hiện khuôn mặt

bằng đặc trưng HOG với mô hình phát hiện khuôn mặt sử dụng đặc trưng Haar

wavelet và bộ phân lớp AdaBoost (được quy ước gọi tên là phương pháp Haar

wavelet AdaBoost) [2]. Các kết quả thực nghiệm được mô tà cụ thể trên Bảng 3.1.

Dữ liệu Sử dụng đặc trưng HOG Đặc trưng Harr wavelet

thử Số mẫu DP DR DM DP DR DM nghiệm

Faces96 3040 98,3 99,1 98,7 93,6 94,4 94,2

FEI_P1 700 98,33 98,43 98,43 80,71 80,73 80,71

FEI_P2 700 99,14 99,14 99,14 83,2 83,11 84

FEI_P3 700 97,43 97,43 97,43 79,43 79,5 79,45

JAFFE 213 100 100 100 100 100 100

93,27 93,51 93,3 LFW 13233 99,74 99,74 99,74

Bảng 3.1: Đánh giá hiệu quả phát hiện khuôn mặt

Hiệu quả của mô hình phát hiện được đánh giá dựa trên độ chính xác phát

hiện, được định nghĩa cụ thể như sau:

R_Precision = số khuôn mặt phát hiện đúng/Tổng số khuôn mặt cần phát hiện.

54

Quá trình đánh giá thực nghiệm được thực hiện lần lượt trên từng tập dữ liệu.

Mỗi tập dữ liệu được chia ngẫu nhiên thành 2 tập training và testing theo tỷ lệ 90/10

(90% số mẫu để huấn luyện mô hình và 10% số mẫu còn lại để kiểm thử).

Việc huấn luyện mô hình gồm 2 công đoạn: Huấn luyện bộ trích chọn đặc

trưng (mô hình mạng neural học sâu FaceNet) và huấn luyện bộ phân lớp SVM.

Quy trình huấn luyện được tiến hành cụ thể như sau: Từ tập mẫu huấn luyện đầu

vào, trước tiên bộ phát hiện khuôn mặt sẽ tiến hành tìm kiếm, định vị và crop vùng

ảnh khuôn mặt trên mỗi khung hình. Toàn bộ tập ảnh khuôn mặt crop sau đó sẽ

được sử dụng làm đầu vào để huấn luyện mô hình trích chọn đặc trưng. Tập đặc

trưng đầu ra của mô hình trích chọn đặc trưng sẽ được sử dụng làm đầu vào để huấn

luyện mô hình phân lớp SVM. Các kết quả thực nghiệm được mô tả cụ thể trên

Bảng 3 hiệu quả của phương pháp sử dụng đăc trưng HOG

R_Precision (%) Dữ liệu thử Số khuôn mặt sử dụng đặc nghiệm cần phát hiện trưng HOG

Faces96 3040 98,03

FEI_P1 700 98,16

FEI_P2 700 98,74

FEI_P3 700 97,55

JAFFE 213 99,04

LFW 13233 95,26

Bảng 3.2: Đánh giá độ chính xác phát hiện mặt người

Từ các kết quả thực nghiệm cho thấy phương pháp sử dụng HOG đạt được độ

chính xác cao (trên 95%) trên tất cả các tập dữ liệu thử nghiệm.

 Giao diện và hoạt động của chương trình

Chương trình thực nghiệm được cài đặt trong môi trường Visual Studio, sử

dụng các thư viện C++ cho việc biểu diễn, lưu trữ và thao tác dữ liệu, thư viện

opencv để thực hiện các thao tác xứ lý ảnh cơ bản

55

- Giao diện khi chương trình bắt đầu:

Hình 3.5: Giao diện chương trình

- Giao diện khi thực hiện chạy chương trình phát hiện khuôn mặt:

Hình 3.6: Giao diện chương trình khi thực hiện phát hiện được khuôn mặt

56

KẾT LUẬN

Luận văn đề xuất sử dụng đặc trưng HOG kết hợp với SVM trong việc phát

hiện mặt người từ ảnh và video. Trong đó tập trung chính vào công đoạn phát hiện

mặt người trên video. Hiệu quả của đặc trưng đã được đánh giá trên các tập dữ liệu

chuẩn, dùng chung cho cộng đồng nghiên cứu về phát hiện và nhận dạng khuôn mặt

người trên thế giới bao gồm cơ sở dữ liệu UOF, FEI, JAFFE và LFW.

Quá trình đánh giá thực nghiệm được chia thành 2 bước, trong đó hiệu quả là

phương pháp phát hiện khuôn mặt được đánh giá dựa trên 3 độ đo là độ chính xác

(Precision), khả năng tìm hết (recall) và độ đo F-measure, hiệu quả của mô hình

phát hiện khuôn mặt được đánh giá dựa trên độ chính xác phát hiện.

Sau một thời gian tìm hiểu nghiên cứu, luận văn đã trình bày được các vấn đề:

- Nghiên cứu Haar wavelet và Adaboost;

- Nghiên cứu thuật toán Viola - Johns;

- Nghiên cứu đặc trưng HOG;

- Nghiên cứu cách sử dụng đặc trưng HOG với SVM trong phát hiện mặt

người.

- Xây dựng bộ dữ liệu khuôn mặt để thử nghiệm;

- Thực hiện huấn luyện và test;

- Phân tích, đánh giá kết quả thu được; so sánh kết quả thu được với kết quả

của một số phương pháp nhận diện đã được công bố.

Hướng phát triển của đề tài:

Các kết quả thực nghiệm cho thấy mô hình đạt được độ chính xác cao và ổn

định trong môi trường thực tế, có thể ứng dụng mô hình để giải quyết các bài toán

ứng dụng điển hình như hệ thống camera giám sát cho phép phát hiện, nhận dạng và

cảnh báo các đối tượng lạ mặt đột nhập tại các khu vực an ninh, nhà ga, sân bay, các

cơ quan chính phủ, tòa nhà, chung cư, tra cứu thông tin tội phạm, chấm công, điểm

danh tự động tại các khu công nghiệp, nhà máy, công trường, lớp học… cải thiện

chất lượng của các thuật toán giao tiếp người-máy…

57

Một lần nữa học viên xin được cảm ơn Thầy giáo TS. Nguyễn Toàn Thắng

đã tận tình giúp đỡ, hướng dẫn trong thời gian thực hiện đề tài, cảm ơn sự giúp đỡ

của gia đình, bạn bè và các đồng nghiệp trong thời gian qua.

Thái Nguyên ngày tháng năm 2018

Người thực hiện

Đinh Quang Huy

58

DANH MỤC TÀI LIỆU THAM KHẢO

I. Tài liệu Tiếng Anh

[1] A. Yilmaz and M. Shah, "Object Tracking: A Survey," ACM Computing

Surveys , pp. 7-15, December 2006.

[2] P. Viola and M. Jones, "Rapid object detection using a boosted cascade of simple features," International Journal of Computer Vision 57, p. 137–154, 2004.

[3] Y. Freund and R. Shapire, "A decisiontheoretic generalization of online learning and an application to boosting," Proceedings of the Second European Conference on Computational Learning Theory, pp. 23-37, 1995.

[4] P. Viola and M. Jones, "Robust real-time face detection," International

Journal of Computer Vision 57, 2004.

[5] N. Dalal and B. Triggs, "Histogram of Oriented Gradients for Human Detection," in Computer Vision and Pattern Recognition CVPR 2005. IEEE Computer Society Conference on, vol. 1, pp. 886-893, 2005.

[6] C. Rasmussen and G. D. Hager, "Probabilistic data associationmethod for

tracking multiple and compound visual objects," pp. 7-9, August 2000.

[7] V. Janbandhu, "Human Detection with Non Linear Classification Using Linear SVM," International Journal of Science and Research (IJSR); Volume 3 Issue 12, pp. 1347-1354, 12 2014.

[9] V. Kazcmi and J. Sullivan., "One millisecond face alignment with an ensemble of regression trees," In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1867-1874, 2014.

[10] N. Kumar, A. C. Berg, P. N. Belhumeur and S. K. Nayar, "Attribute and simile classifiers for face verification," In Computer Vision, IEEE 12th International Conference oti, pp. 365-372, 2009.

[11] W. Jiang, "Human Feature Extraction in VS image Using HOG Algorithm".

[12] A. Blake and M. Isard, "Active Contours".

[13] N. S. Vu and A. Caplier, "Illumination-robust face recognition using retina modeling," In Image Processing (ICIP), 2009 16th IEEE International Conference on, p. 3289–3292, 2009.

[14] K. I. Naka and W. A. H. Rushton, "S-potentials from luminosity units in the

59

retina of fish (Cyprinidae)," J. Physiol, vol. 185, no. 3, p. 587–599, 1966.

[16] J. Plat, "Fast Training of Support Vector Machines Using Sequential Minimal Optimization," In Advences in Kernel Methods - Support Vector Learning, Cambridge, M.A, MIT Press, pp. 185-208, 1999.

II. Tài liệu tiếng Việt

[8] Nguyễn Thị Thanh Tân, Huỳnh Văn Huy và Ngô Quốc Tạo, "Phương pháp nhận dạng khuôn mặt người từ webcam," Hội thảo quốc gia lần thứ XX: Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, trang. 285-291, năm 2017.

[15] Phạm Anh Phương, Ngô Quốc Tạo và Lương Chi Mai, “Trích chọn đặc trưng wavelet Haar kết hợp với SVM cho việc nhận dạng chữ viết tay tiếng Việt,” năm 2008.

[17] Trương Quốc Bảo, Trương Hùng Chen và Trương Quốc Định, “Phát hiện và nhận dạng biển báo giao thông đường bộ sử dụng đặc trung HOG và mạng nơrron nhân tạo,” Tạp chí khoa học trường Đại học Cần Thơ - Số chuyên đề Công nghệ thông tin, trang. 47-54, năm 2015.