Báo cáo Tương tác người và máy dùng cử chỉ bàn tay (Phần 1)

Nội dung text: Báo cáo Tương tác người và máy dùng cử chỉ bàn tay (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH CÔNG TRÌNH NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG TƯƠNG TÁC NGƯỜI VÀ MÁY DÙNG CỬ CHỈ BÀN TAS K C Y0 0 3 9 5 9 MÃ SỐ: T2015 - 75 S KC 0 0 5 6 2 0 Tp. Hồ Chí Minh, 2015
2. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƢỜNG TƢƠNG TÁC NGƢỜI VÀ MÁY DÙNG CỬ CHỈ BÀN TAY Mã số: T2015-75 Chủ nhiệm đề tài: ThS. Ngô Quốc Cƣờng TP. HCM, 10/2015
3. TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH KHOA ĐIỆN – ĐIỆN TỬ BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƢỜNG TƢƠNG TÁC NGƢỜI VÀ MÁY DÙNG CỬ CHỈ BÀN TAY Mã số: T2015-75 Chủ nhiệm đề tài: ThS. Ngô Quốc Cƣờng Thành viên đề tài: ThS. Nguyễn Ngô Lâm TP. HCM, 10/2015
4. DANH SÁCH CÁN BỘ THAM GIA THỰC HIỆN ĐỀ TÀI STT MSCB Họ và tên Đơn vị công tác Nội dung công việc MT-Viễn thông-Khoa ThS. Ngô 1. 0390 Điện-Điện tử- Xây dựng thuật Quốc Cƣờng ĐHSPKT Tp.HCM toán Khoa Đào tạo Chất ThS. Nguyễn Triển khai ứng dụng 2. 2204 lƣợng cao - ĐHSPKT Ngô Lâm Tp.HCM
5. MỤC LỤC MỤC LỤC i DANH SÁCH HÌNH ii DANH SÁCH TỪ VIẾT TẮT iii THÔNG TIN KẾT QUẢ NGHIÊN CỨU iv INFORMATION ON RESEARCH RESULTS v Chƣơng 1 1 MỞ ĐẦU 1 Chƣơng 2 3 CƠ SỞ LÝ THUYẾT 3 2.1 Cử chỉ bàn tay 3 2.2 Ảnh số 5 2.2.1 Điểm ảnh 5 2.2.2 Phân loại ảnh 5 2.2.3 Không gian màu L*a*b 7 2.3 Phân cụm K-means 9 2.3.1 Phân đoạn ảnh 9 2.3.2 Phƣơng pháp tìm cụm 9 2.3.3 Giải thuật K-means 9 2.4 Đặc trƣng HOG 11 2.5 Mạng Nơ-ron nhân tạo 12 Chƣơng 3 17 XÁC ĐỊNH VÙNG ẢNH CHỨA BÀN TAY 17 3.1 Thu nhận ảnh cử chỉ bàn tay 17 3.2 Xác định vị trí bàn tay 19 3.2.1 Phân cụm K-means 19 3.2.2 Tách vùng bàn tay 22 Chƣơng 4 25 TƢƠNG TÁC NGƢỜI VÀ MÁY DÙNG CỬ CHỈ BÀN TAY 25 4.1 Nhận dạng cử chỉ bàn tay 26 4.1.1 Trích đặc trƣng HOG 26 4.1.2 Huấn luyện và nhận dạng dùng mạng nơ-ron 27 4.2 Tƣơng tác ngƣời và máy dùng cử chỉ bàn tay 29 Chƣơng 5 33 KẾT LUẬN và HƢỚNG PHÁT TRIỂN 33 5.1 Kết Luận 33 5.2 Hƣớng Phát Triển 33 TÀI LIỆU THAM KHẢO 34 PHỤ LỤC 35 i
6. DANH SÁCH HÌNH Hình 2. 1. Ngôn ngữ ký hiệu tại Mỹ 3 Hình 2. 2. Ngôn ngữ ký hiệu tại Việt Nam 4 Hình 2. 3. Số trong ngôn ngữ cử chỉ 4 Hình 2. 4. Không gian màu RGB, chuẩn CIE 1931 6 Hình 2. 5. Ảnh bàn tay không gian màu RGB 7 Hình 2. 6. Ảnh bàn tay - xám 7 Hình 2. 7. Ảnh bàn tay - nhị phân 7 Hình 2. 8. Không gian màu L*a*b 8 Hình 2. 9. Ảnh bàn tay trong không gian màu RGB và L*a*b 8 Hình 2. 10. Giải thuật K-means trên phân chia các đặc trƣng - thành phần màu: 11 Hình 2. 11. Chia khối cho việc tìm đặc trƣng R-HOG và C-HOG 12 Hình 2. 12. Sự chồng lấp các khối trong cách tính đặc trƣng HOG 12 Hình 2. 13. Cấu trúc nơ-ron sinh học: cell body, axon, synaptic 13 Hình 2. 14. Cấu trúc cơ bản của tế bào thần kinh 13 Hình 2. 15. Mô hình perceptron một nơ-ron 14 Hình 2. 16. Hàm bƣớc 14 Hình 2. 17. Hàm sigmoid 14 Hình 2. 18. Hàm double sigmoid 14 Hình 2. 19. Mạng lan truyền ngƣợc với 3 lớp 15 Hình 3. 1. Sơ đồ khối xác định vùng bàn tay trong ảnh 17 Hình 3. 2. Ảnh cử chỉ bàn tay: bàn tay xòe từ một ngón tay đến năm ngón tay 18 Hình 3. 3. Ảnh chụp để tách bàn tay với cử chỉ bàn tay đang xòe năm ngón tay 18 Hình 3. 4. Thu nhận ảnh ở bƣớc 1 và chuyển sang không gian màu L*a*b trong bƣớc 2 hình 3.1. Trong đó: a. Ảnh RGB; b. Ảnh L*a*b 19 Hình 3. 5. Các kết quả ứng với các cụm đã phân đƣợc 22 Hình 3. 6. Vùng ảnh bàn tay đƣợc tách ra sau khi xác định các vị trí biên của bàn tay trong ảnh 22 Hình 3. 7. Vùng ảnh bàn tay đƣợc chuyển sang dạng ảnh nhị phân 23 Hình 3. 8. Vùng ành bàn tày cử chỉ một ngón tay 23 Hình 3. 9. Vùng ành bàn tày cử chỉ hai ngón tay 23 Hình 3. 10. Vùng ành bàn tày cử chỉ ba ngón tay 23 Hình 3. 11. Vùng ành bàn tày cử chỉ năm ngón tay 24 ii
7. DANH SÁCH TỪ VIẾT TẮT RGB Red Green Blue HOG Histogram of Oriented Gradient ANN Artifical Neural Networks iii
8. TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM THÀNH PHỐ HỒ CHÍ MINH Độc lập - Tự do - Hạnh phúc ĐƠN VỊ: ĐIỆN- ĐIỆN TỬ Tp. HCM, Ngày 22 tháng 10 năm 2015 THÔNG TIN KẾT QUẢ NGHIÊN CỨU 1. Thông tin chung: - Tên đề tài: TƢƠNG TÁC NGƢỜI VÀ MÁY DÙNG CỬ CHỈ BÀN TAY - Mã số: T2015-75 - Chủ nhiệm: Ngô Quốc Cƣờng - Cơ quan chủ trì: Đại Học Sƣ Phạm Kỹ Thuật TP. HCM - Thời gian thực hiện: 12 tháng 2. Mục tiêu: Nhận dạng cử chỉ bàn tay ngƣời 3. Tính mới và sáng tạo: Ứng dụng giải thuật K-means trong tách vùng ảnh bàn tay. Trích đặc trƣng dùng HOG. 4. Kết quả nghiên cứu: Nhận dạng 5 cử chỉ khác nhau. Thực hiện tƣơng tác thông qua truyền dữ liệu ứng với cử chỉ nhận dạng đƣợc. 5. Sản phẩm: Tài liệu cơ bản về tách vùng ảnh bàn tay, ứng dụng nhận dạng cử chỉ bàn tay trong tƣơng tác ngƣời và máy. Bài báo đăng trên website Khoa Điện- Điện tử. 6. Hiệu quả, phƣơng thức chuyển giao kết quả nghiên cứu và khả năng áp dụng: Tài liệu dùng trong giảng dạy Xử lý ảnh, Máy học. Trƣởng Đơn vị Chủ nhiệm đề tài (ký, họ và tên) (ký, họ và tên) iv
9. INFORMATION ON RESEARCH RESULTS 1. General information: Project title: Human machine interface using hand gesture recognition Code number: T2015-75 Coordinator: Cuong Ngo Implementing institution: HCMC Univerisy of Technology and Education Duration: 12 months 2. Objective(s): Human hand gesture recognition 3. Creativeness and innovativeness: Human hand localisation in an image using K-means. Feature extraction using HOG. 4. Research results: Classification of five different hand gesture. Implementation of HMI through data communication corresponding to recognised hand gestures. 5. Products: Basic material of human hand detection in an image, implementation of HMI using hand gesture recognition. Paper proposed on FEEE website 6. Effects, transfer alternatives of research results and applicability: Reference material for subjects, such as: Image processing, Machine learning. v
10. 1. Mở Đầu Chƣơng 1 MỞ ĐẦU Trong thời đại công nghệ thông tin hiện nay, các hệ thống máy tự động đã dần thay thế con ngƣời trong nhiều công đoạn của công việc. Máy móc có khả năng làm việc hiệu quả, độ chính xác cao và hữu dụng trong môi trƣờng nguy hại đối với con ngƣời cùng với tốc độ xử lý ngày càng nhanh. Hiện nay, các công nghệ nhận dạng cử chỉ đã phát triển, song song đó là các hệ thống ứng dụng nhận dạng cử chỉ đã đƣợc ứng dụng ở nhiều nơi và độ chính xác của các hệ thống ngày càng đƣợc cải thiện. Hệ thống nhận dạng cử chỉ đã và đang có những ứng dụng hữu ích trong các lĩnh vực của đời sống. Nếu đƣợc áp dụng thành công thì nó sẽ trở thành một cuộc cách mạng trong giao tiếp với máy móc, các ứng dụng của nó sẽ bao trùm lên nhiều lĩnh vực nhƣ giúp đỡ ngƣời khuyết tật, công nghiệp, an ninh, và giải trí. 1.1 Tình hình nghiên cứu Hệ thống nhận dạng cử chỉ bàn tay tự động trên luồng video đƣợc giới thiệu trong [1]. Hệ thống này gồm 2 phần: phát hiện bàn tay và nhận dạng cử chỉ. Việc phát hiện bàn tay đƣợc thực hiện bằng phƣơng pháp Viola-Jones. Trong khi đó ở phần nhận dạng, bộ phân loại SVM đƣợc sử dụng để nhận dạng cử chỉ với đặc trƣng đƣợc trích từ moment bất biến Hu. Việc nhận dạng cử chỉ bàn tay còn đƣợc thực hiện thông qua lịch sử chuyển động trong ảnh [2]. Bốn nhóm đối tƣợng có hƣớng Haar-like đƣợc huấn luyện để phân loại cử chỉ tay: lên, xuống, trái, phải. Từ đây, sáu cử chỉ bàn tay đƣợc định nghĩa bằng việc kết hợp ảnh đầu tiên và dạng sóng cử chỉ tay tiếp theo. Kết quả thí nghiệm cho độ chính xác trung bình là 94.1% và thời gian xử lý là 3.81 ms trên một khung ảnh. Đặc trƣng của màu da trong không gian màu YCbCr đƣợc sử dụng để phát hiện cử chỉ bàn tay [3]. Bộ lọc trung vị đƣợc sử dụng để loại nhiễu. Sự kết hợp của moment bất biến Hu, vùng cử chỉ bàn tay, và bộ miêu tả Fourier tạo nên một vector đặc trƣng mới đƣợc sử dụng để nhận dạng cử chỉ bàn tay. Kết quả hệ thống có thể nhận dạng thành công với độ chính xác 97.4%. Trong [4], thông số hình dạng đƣợc sử dụng để nhận dạng cử chỉ bàn tay. Ảnh sau khi thu từ web-cam đƣợc tiền xử lý để loại nhiễu nền. Sau đó, phƣơng pháp K- means đƣợc sử dụng để phân đoạn bàn tay ra khỏi nền. Tiếp theo, hệ số hình dạng đƣợc dùng để nhận dạng 45 cử chỉ khác nhau. Giải thuật đề xuất trong công trình này cho độ chính xác xấp xỉ 94%. Trƣờng hợp ảnh chụp bàn tay có cả khuôn mặt, việc loại bỏ vùng khuôn mặt đƣợc thực hiện [5]. Ảnh sau đó đƣợc chuyển sang hai không gian màu: HSV và YCbCr để trích vùng chứa màu da. Khi có sự tƣơng đồng giữa hai phƣơng pháp về khu vực bàn tay thì hệ thống xác nhận đó là vùng chứa bàn tay cần tìm. 1
11. 1. Mở Đầu 1.2 Tính cấp thiết - Hiện nay, lĩnh vực xử lý ảnh ngày càng phát triển mạnh. Đặc biệt với các ứng dụng giao tiếp ngƣời và máy. - Đề tài xây dựng và ứng dụng giải thuật để nhận dạng cử chỉ bàn tay ngƣời ứng dụng vào giao tiếp ngƣời và máy tính. - Kết quả của đề tài có thể đƣợc sử dụng vào việc nghiên cứu và giảng dạy cho sinh viên chuyên ngành điện tử viễn thông và tự động. 1.3 Mục tiêu đề tài - Nhận dạng cử chỉ bàn tay ngƣời 1.4 Cách tiếp cận, phƣơng pháp nghiên cứu, phạm vi nghiên cứu Cách tiếp cận - Lý thuyết đến thực nghiệm Phƣơng pháp nghiên cứu - Nghiên cứu lý thuyết - Mô phỏng - Thực nghiệm Phạm vi nghiên cứu - Cử chỉ bàn tay đơn giản 1.5 Nội dung nghiên cứu - Cơ sở lý thuyết về xử lý ảnh và nhận dạng. - Giải thuật phát hiện vùng chứa bàn tay trong ảnh. - Giải thuật nhận dạng cử chỉ bàn tay. - Ứng dụng nhận dạng cử chỉ bàn tay từ ảnh thu đƣợc. 2
12. 2. Cơ Sở Lý Thuyết Chƣơng 2 CƠ SỞ LÝ THUYẾT 2.1 Cử chỉ bàn tay Ngôn ngữ ký hiệu thay đổi theo từng quốc gia, và trong một quốc gia ngôn ngữ ký hiệu cũng có sự khác nhau ở các vùng miền. Hình 2.1 trình bày ngôn ngữ ký hiệu của nƣớc Mỹ, trong khi đó, hình 2.2 trình bày ngôn ngữ ký hiệu đang đƣợc sử dụng phổ biến tại Việt Nam. Hình 2. 1. Ngôn ngữ ký hiệu tại Mỹ Hai đặc điểm quan trọng của ngôn ngữ ký hiệu là tính giản lƣợc và điểm nhấn. Do hai đặc điểm này mà ngôn ngữ ký hiệu thƣờng không thống nhất, cùng một câu có thể có nhiều cách xếp khác nhau. 3
13. 2. Cơ Sở Lý Thuyết Hình 2. 2. Ngôn ngữ ký hiệu tại Việt Nam Ngoài ra, số cũng đƣợc biểu thị thông qua ngôn ngữ cử chỉ nhƣ trong hình 2.3. Mỗi số đƣợc biểu diễn riêng theo sự phối hợp các ngón tay khác nhau. Hình 2. 3. Số trong ngôn ngữ cử chỉ 4
14. 2. Cơ Sở Lý Thuyết 2.2 Ảnh số 2.2.1 Điểm ảnh Ảnh số là một tập hợp của nhiều điểm ảnh, hay còn gọi là pixel. Mỗi điểm ảnh biểu diễn một màu sắc nhất định (hay độ sáng đối với ảnh xám) tại một điểm duy nhất, có thể xem một điểm ảnh giống nhƣ một chấm nhỏ trong một tấm ảnh màu. Bằng phƣơng pháp đo lƣờng và thống kê một lƣợng lớn các điểm ảnh, chúng ta hoàn toàn có thể tái cấu trúc các điểm ảnh này thành một ảnh mới gần giống với ảnh gốc. Có thể nói pixel gần giống nhƣ các phần tử có cấu trúc hạt nhƣng đƣợc sắp xếp theo từng hàng và cột, chứa các thông tin khác nhau. Ảnh đƣợc biểu diễn dƣới dạng một ma trận hai chiều với các pixel đƣợc xác định bởi cặp tọa độ (x, y), trong đó, giá trị của pixel tại tọa độ nhất định biểu diễn độ sáng (ảnh xám) hay màu nhất định (ảnh màu). Giá trị độ sáng đƣợc số hóa trong xử lý ảnh đƣợc gọi là giá trị mức xám. Với một ảnh sau khi đƣợc lấy mẫu để cho ra một ảnh số với kích thƣớc xác định gồm có M hàng và N cột, ta nói rằng ảnh có kích thƣớc M N và đƣợc biểu diễn dƣới dạng ma trận nhƣ sau: f (1,1)  f (1, N) (2.1) f (x, y)    f (M ,1)  f (M , N) trong đó: f (x, y)– giá trị của pixel tại vị trí (x, y) M – số hàng của ảnh số đang xét N – số cột của ảnh số đang xét Đối với ảnh xám, giá trị mức xám thƣờng nằm trong khoảng 0 f (x, y) G 1, trong đó G thƣờng đƣợc biểu diễn dƣới dạng lũy thừa của 2. Mỗi điểm ảnh tƣơng ứng với một phần của một đối tƣợng vật lý trong không gian ba chiều. Đối tƣợng này đƣợc mô tả bởi các nguồn sáng mà trong đó chúng đƣợc phản chiếu một phần và hấp thụ một phần bởi vật thể. Phần phản chiếu có thể thu đƣợc bằng các cảm biến để mô tả lại khung cảnh tƣơng ứng và nó đƣợc ghi lại nhƣ là đặc trƣng của điểm ảnh. Nói cách khác, các giá trị này phụ thuộc vào từng loại cảm biến đƣợc dùng cho việc thu ảnh để phản ánh khung cảnh từ nguồn sáng phản chiếu. 2.2.2 Phân loại ảnh Có 2 dạng quan trọng trong ảnh số đƣợc dùng với nhiều mục đích khác nhau là ảnh màu và ảnh xám (hay còn gọi là ảnh trắng đen). Trong đó, ảnh màu đƣợc cấu trúc từ các pixel màu trong khi ảnh xám đƣợc xây dựng từ các pixel có giá trị mức xám khác nhau. Một ảnh màu thƣờng đƣợc tạo thành từ nhiều pixel mà trong đó mỗi pixel đƣợc biểu diễn bởi ba giá trị tƣơng ứng với các mức trong các kênh màu đỏ (Red), 5
15. 2. Cơ Sở Lý Thuyết xanh lá (Green) và xanh dƣơng (Blue) tại một vị trí cụ thể. Các kênh màu Red, Green và Blue (trong không gian màu RGB) là những màu cơ bản mà từ đó có thể tạo ra các màu khác nhau bằng phƣơng pháp pha trộn. Ngoài không gian màu RGB nhƣ trình bày trong hình 2.4, những không gian màu khác cũng đƣợc sử dụng nhƣ: HSV, YCbCr, L*a*b, tùy thuộc vào ứng dụng và lĩnh vực. Ảnh xám đƣợc xây dựng từ nhiều pixel mà tại đó biểu diễn một giá trị nhất định tƣơng ứng với một mức xám. Những mức xám này trải dài trong một khoảng từ đen sang trắng với bƣớc nhảy rất mịn, thông thƣờng là 256 mức xám khác nhau. Ảnh nhị phân chỉ sử dụng duy nhất một bit để biểu diễn một pixel. Do một bit chỉ có thể xác lập một trong hai trạng thái là đóng hoặc mở hay 1 hoặc 0 tƣơng ứng với hai màu là đen và trắng. Do đặc trƣng trên mà ảnh nhị phân ít khi đƣợc sử dụng trong thực tế. Tuy nhiên, ảnh nhị phân lại rất hữu dụng trong các bài toán nhị phân hóa ảnh nhằm phục vụ cho việc nhận dạng. Hình 2. 4. Không gian màu RGB, chuẩn CIE 1931 Hình 2.5, hình 2.6, và hình 2.7 trình bày ảnh bàn tay với các kiểu: ảnh màu, ảnh xám, ảnh nhị phân. 6
16. 2. Cơ Sở Lý Thuyết Hình 2. 5. Ảnh bàn tay không gian màu RGB Hình 2. 6. Ảnh bàn tay - xám Hình 2. 7. Ảnh bàn tay - nhị phân 2.2.3 Không gian màu L*a*b Không gian màu L*a*b là không gian màu độc lập với thiết bị. Điều này có nghĩa là màu đƣợc định nghĩa độc lập với bản chất tự nhiên của thiết bị tạo ảnh hay của thiết bị mà ảnh hiển thị trên đó. Mô hình màu L*a*b là một hệ thống 3 trục nhƣ trong hình 2.8. Trục đầu tiên là kênh L (độ sáng). Trục màu a trải từ màu xanh ngọc đến màu đỏ thẫm. Trục màu b trải dài từ màu xanh dƣơng đến màu vàng. Ảnh chụp bàn tay đƣợc chuyển sang không gian màu L*a*b đƣợc trình bày trong hình 2.9. 7
17. 2. Cơ Sở Lý Thuyết Hình 2. 8. Không gian màu L*a*b Hình 2. 9. Ảnh bàn tay trong không gian màu RGB và L*a*b 8
18. 2. Cơ Sở Lý Thuyết 2.3 Phân cụm K-means 2.3.1 Phân đoạn ảnh Phân đoạn ảnh là công việc phân chia hay tách ảnh thành các vùng có thuộc tính giống nhau. Thuộc tính cơ bản nhất để phân đoạn là độ chói đối với ảnh đơn sắc và các thành phần màu đối với ảnh màu. Biên ảnh và kết cấu ảnh cũng là các thuộc tính quan trọng để phân đoạn ảnh Có nhiều giải thuật phân đoạn ảnh khác nhau đã đƣợc phát triển: phân đoạn biên độ chói, phân đoạn nhóm, phân đoạn vùng. 2.3.2 Phƣơng pháp tìm cụm Với một tập các vector đặc trƣng cho trƣớc, ta có thể kiểm tra để tạo thành các nhóm liên quan nhau hoặc cụm. Đây là trƣờng hợp đơn giản với các vector hai chiều, ta có thể vẽ, nhìn thấy các nhóm, và gán nhãn chúng thuộc một lớp. Khi vector có số chiều lớn hơn, việc phân tích theo quan sát bằng mắt không thể thực hiện đƣợc. Nhƣ vậy, cần thiết phải đặt ra tiêu chuẩn để nhóm các vector dựa trên điều kiện về sự tƣơng đồng, sự khác biệt, hay đo khoảng cách. Một số ví dụ về thực hiện đo khoảng cách đƣợc miêu tả nhƣ sau: Khoảng Euclide đƣợc xác định nhƣ sau: ‖ ‖ ( ) ( ) ∑( ) (2.2) ở đây, x và z là hai vector đặc trƣng. Giá trị DE càng nhỏ đồng nghĩa với việc sự giống nhau giữa hai vector này càng lớn. Khoảng cách Manhattan: (2.3) ∑| | khoảng cách này là đoạn ngắn nhất giữa x và z. Khoảng cách Mahalanobis đƣợc tính nhƣ sau: ( ) ( ) (2.4) trong đó, x là vector đặc trƣng so sánh với lớp mẫu và m là vector trung bình của lớp, C là ma trận hiệp phƣơng sai. Giá trị DM nhỏ cho thấy khả năng thuộc về lớp của vector x. Nhân chấm chuẩn hóa (cos của góc giữa vector x và z) đƣợc mô tả nhƣ sau: (2.5) ‖ ‖‖ ‖ Giá trị nhân chấm càng lớn thì hai vector càng giống nhau. 2.3.3 Giải thuật K-means Giải thuật K-means dựa trên việc tối thiểu chỉ số đánh giá bằng vòng lặp. Chỉ số này đƣợc định nghĩa là tổng bình phƣơng khoảng cách từ tất cả các điểm trong một cụm đến trung tâm cụm. 9
19. 2. Cơ Sở Lý Thuyết + Bƣớc 1: khởi tạo K trung tâm cụm ( ) ( ) ( ). K là số lƣợng của cụm đƣợc tạo. Việc lựa chọn trung tâm cụm là bất kỳ và có thể là K vector đặc trƣng đầu tiên. Chỉ số trong ngoặc đại diện cho chỉ số lặp. + Bƣớc 2: ở bƣớc lặp thứ k, phân bố các mẫu giữa K cụm, dùng sự liên hệ ( ) ‖ ( )‖ ‖ ( )‖ (2.6) Trong đó, ( ) là tập các mẫu có trung tâm cụm là ( ). + Bƣớc 3: từ kết quả bƣớc 2, tính trung tâm cụm mới ( ) , nhƣ vậy bình phƣơng khoảng cách từ tất cả các điểm trong ( ) đến trung tâm cụm mới đƣợc tối thiểu hóa. Nói cách khác, trung tâm cụm mới ( ) đƣợc tính để chỉ số đánh giá ∑ ‖ ( )‖ (2.7) ( ) là tối thiểu. Trung tâm cụm ( ) đơn giản là giá trị trung bình của ( ). Vì vậy, trung tâm cụm mới đƣợc cho bởi: ( ) ∑ (2.8) ( ) ( ) trong đó ( ) là số mẫu trong ( ). Tên gọi K-means đƣợc lấy từ ý tƣởng trung tâm cụm đƣợc cập nhật một cách tuần tự. + Bƣớc 4: nếu ( ) ( ) với , giải thuật hội tụ: dừng chƣơng trình; ngƣợc lại, quay lại bƣớc 2. Giải thuật K-means bị ảnh hƣởng bởi: Số lƣợng trung tâm cụm (K) đƣợc chọn. Sự lựa chọn các trung tâm cụm lúc khởi tạo. Thứ tự xem xét các mẫu. Tính chất hình học và phân bố của dữ liệu. Hình 2.10 là một ví dụ về phân cụm K-means dựa trên sự tƣơng đồng trong cụm về màu sắc. Những cụm có màu khác nhau đƣợc tách ra sau những vòng lặp trong giải thuật này. 10
20. 2. Cơ Sở Lý Thuyết Hình 2. 10. Giải thuật K-means trên phân chia các đặc trƣng - thành phần màu: (a) Những mẫu đƣợc phân bố tự nhiên theo 3 nhóm riêng biệt (b) Khởi tạo trung tâm nhóm (c) Phân bổ mẫu theo trung tâm nhóm ở (b) (d) Tính trung tâm nhóm mới (e) Phân bổ mẫu theo trung tâm nhóm ở (d) (f) Tính trung tâm nhóm mới 2.4 Đặc trƣng HOG Histogram of Gradient (HOG) [6] là đặc trƣng đƣợc dùng nhiều trong lĩnh vực phát hiện đối tƣợng. Ý 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. Do sự biến thiên màu sắc trong các vùng là khác nhau, 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ộ ảnh 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. 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 2.11. 11
21. 2. Cơ Sở Lý Thuyết Hình 2. 11. Chia khối cho việc tìm đặc trƣng R-HOG và C-HOG Từ một ảnh cho trƣớc, qua việc trích đặc trƣng trên ảnh đó cho ta đƣợc một vector đại diện cho đối tƣợng đó. 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ỳ có thể thực hiện qua các bƣớc: Phân chia ảnh 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ố nhƣ trong hình 2.12. Sau khi đã phân chia cửa sổ cần tính toán HOG nhƣ trên. Ta tiến hành 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ổ Hình 2. 12. Sự chồng lấp các khối trong cách tính đặc trƣng HOG 2.5 Mạng Nơ-ron nhân tạo Mạng nơ-ron nhân tạo (ANN- Artifical Neural Networks) là một trong những công cụ rất mạnh trong vấn đề phân loại và nhận dạng đối tƣợng. Dựa trên cấu trúc của nơ-ron sinh học ( hình 2.13 ) trong hệ thống thần kinh ngƣời, nhiều dạng mạng nơ-ron nhân tạo đã đƣợc xây dựng và phát triển. 12
22. S K L 0 0 2 1 5 4