Tài liệu áp dụng học máy trong nhận dạng biển báo giao thông

MỤC LỤC LỜI CAM ĐOAN MỤC LỤC DANH MỤC CÁC CHỮ VIẾT TẮT DANH MỤC CÁC BẢNG DANH MỤC CÁC HÌNH TÓM TẮT LUẬN VĂN MỞ ĐẦU .........................................................................................................................1 1. Lý do chọn đề tài .............................................................................................. 1 2. Mục tiêu nghiên cứu .........................................................................................2 3. Đối tượng và phạm vi nghiên cứu ....................................................................2 4. Phương pháp nghiên cứu ..................................................................................2 5. Ý nghĩa khoa học và thực tiễn ..........................................................................2 6. Bố cục của Luận văn ......................................................................................3 CHƯƠNG 1. TỔNG QUAN NGHIÊN CỨU .............................................................. 4 1.1. Tổng quan về xử lý ảnh ............................................................................................ 4 1.1.1. Tổng quan về xử lý ảnh...............................................................................4 1.1.2. Các quá trình xử lý ảnh ..............................................................................5 1.1.3. Ảnh và biểu diễn ảnh ..................................................................................6 1.1.4. Phạm vi ứng dụng của xử lý ảnh ................................................................ 8 1.2. Học máy ....................................................................................................................9 1.2.1. Tổng quan học máy ...................................................................................9 1.2.2. Các phương pháp học máy ........................................................................9 1.2.2.1. Học không giám sát .................................................................................9 1.2.2.2. Học có giám sát .......................................................................................9 1.2.2.3. Học bán giám sát ...................................................................................10 1.2.2.4. Học tăng cường .....................................................................................10 1.2.2.5. Các ứng dụng của học máy ...................................................................11 1.3. Các phương pháp nhận dạng đối tượng ..................................................................11 1.3.1. Phương pháp Neural Networks (NN) ......................................................11 1.3.2. Phương pháp Support Vector Machine (SVM) .......................................12 1.3.3. Phương pháp Linear Discriminant Analysis ...........................................12 1.3.4. Phương pháp Naive Bayes (NB) ............................................................. 12 1.3.5. Phương pháp Principal Component Analysis (PCA) ............................. 12 1.4. Kết chương .............................................................................................................13 CHƯƠNG 2. MÔ HÌNH ĐỀ XUẤT TRONG PHÁT HIỆN VÀ NHẬN DẠNG BIỂN BÁO GIAO THÔNG ........................................................................................14 2.1. Mô tả bài toán .........................................................................................................14 2.2. Mô hình tổng quát...................................................................................................14 2.3. Phương pháp đề xuất .............................................................................................. 15 2.3.1. Mô hình phát hiện Biển Báo Giao Thông ...............................................15 2.3.1.1. Mô hình phát hiện ..................................................................................15 2.3.1.2. Đặc trưng Haar-like ..............................................................................16 2.3.1.3. Integral Image .......................................................................................17 2.3.1.4. Thuật toán Adaboost ..............................................................................18 2.3.1.5. Cascade ..................................................................................................23 2.3.2. 2.3.3. 2.3.4. 2.3.5. Mô tả thuật toán nhận diện biển báo ......................................................28 Principal component analysis (PCA) ......................................................29 Khoảng cách mahalanobis ......................................................................31 Chuyển đổi không gian vector .................................................................31 2.3.6. Các bước giảm chiều dữ liệu: .................................................................32 2.3.7. Tiến trình nhận dạng biển báo ................................................................ 35 2.4 Kết chương .............................................................................................................35 CHƯƠNG 3. THỰC NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ ..................................36 3.1. Tổ chức dữ liệu .......................................................................................................36 3.2. Thu thập dữ liệu ......................................................................................................36 3.3. Cài đặt và thực nghiệm chương trình .....................................................................36 3.3.1. Dữ liệu đầu vào .......................................................................................36 3.3.2. Xử lý dữ liệu ............................................................................................ 36 3.3.2.1. Cấu trúc chương trình .........................................................................37 3.3.2.2. Huấn luyện ........................................................................................... 37 3.3.2.3. Phát hiện biển báo ...............................................................................37 3.3.2.4. Nhận dạng biển báo .............................................................................38 3.3.3. Giao diện chương trình ...........................................................................40 3.4. Một số hình ảnh thực hiện trên chương trình Demo ..............................................43 3.4.1. Phát hiện biển báo ...................................................................................43 3.4.2. Huấn luyện và kiểm tra ...........................................................................46 3.5. Đánh giá kết quả .....................................................................................................50 3.5.1. Về lý thuyết .............................................................................................. 50 3.5.2. Về Cài đặt ................................................................................................ 51 3.5.3. Về thực nghiệm ........................................................................................51 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .................................................................52 TÀI LIỆU THAM KHẢO........................................................................................... 53 QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN (bản sao) TÓM TẮT LUẬN VĂN ÁP DỤNG HỌC MÁY TRONG NHẬN DẠNG BIỂN BÁO GIAO THÔNG Bùi Thanh Phong, học viên cao học khóa 33 Quảng Ngãi, chuyên ngành Khoa học máy tính. Tóm tắt: Biển báo giao thông là một phần của công trình tín hiệu đường bộ, tuy nhiên việc phát hiện và nhận biết biển báo giao thông gặp rất nhiều khó khăn do trong quá trình lái xe còn nhiều vấn đề an toàn khác chi phối. Mục đích của đề tài này là nghiên cứu và tìm ra phương pháp tối ưu nhất để xây dựng thuật toán phát hiện và nhận dạng biển báo giao thông. Chương trình có đầu vào là một file ảnh hoặc video và đầu ra là biển báo có trong dữ liệu đầu vào. Chương trình áp dụng thuật toán Viola-Jones để phát hiện biển báo trong ảnh. Sau đó sử dụng kỹ thuật phân tích thành phần chính (PCA) để xác định biển báo trong ảnh. Báo cáo sẽ tập trung vào việc trình bày các thuật toán ViolaJones và kỹ thuật PCA. Từ khóa: biển báo giao thông, Viola-Jones, PCA Abstract: Traffic signs are a part of road signaling works, however, the detection and identification of traffic signs are difficult due to many other safety issues in driving. The purpose of this research is to research and find the best method to build traffic detection and identification algorithm. The program has an input image or video file and the output is the signage contained in the input data. The program uses the ViolaJones algorithm to detect signage in photos. Then use the component analysis technique to identify the sign in the image. The report will focus on presenting ViolaJones algorithms and PCA techniques. Keyword: traffic signs, Viola-Jones, PCA. DANH MỤC CÁC TỪ VIẾT TẮT Từ đầy đủ Từ viết tắt DP Dynamic Programming DT Decision Tree EM Expectation Maximization HAC Hierarchial Agglomerative Clustering KNN K Nearest Neighbours LDA Linear Discriminant Analysis LLSF Linear Least Square Fit NB Naive Bayes NN Neural Networks Nnet Neural Network PCA Principal Components Analysis SVM Support Vector Machine SVM pháp Support Vector Machine TD TSVM XLA Temporal Difference Transductive Support Vector Machine Xử lý ảnh DANH MỤC CÁC HÌNH VẼ Số hiệu Tên hình Trang hình 1.1: Các bước cơ bản trong quá trình xử lí ảnh 4 1.2: Các giai đoạn chính trong xử lý ảnh 5 1.3: Quan hệ trong vùng lân cận giữa các điểm ảnh 8 2.1: Mô hình tổng quát 14 2.2: Mô hình phát hiện 15 2.3: 4 đặt trưng Haar-like cơ bản 16 2.4: Các đặc trưng mở rộng của các đặc trưng Haar-like cơ sở 16 2.7: Vòng 1 19 2.9: Vòng 3 20 2.10: Vòng 4 21 2.11: Hoàn thành boosting 21 2.12: Chọn p = 1 và tăng trọng số của mẫu phân loại sai. 23 2.13: Trong bước này chúng ta chọn p = -1. 23 2.14: Mô hình hoạt động Cascade 24 2.15: Mô hình phân tầng 24 2.16: Biểu đồ thống kê số phân loại yếu trong mỗi phân loại mạnh của 25 biển báo nguy hiểm 2.17: Biểu đồ thống kê số phân loại yếu trong mỗi phân loại mạnh của biển báo Cấm 25 2.18: Tỷ lệ false positive của mỗi strong classifier trên tập test ( biển nguy hiểm) 26 2.19: Tỷ lệ false positive của mỗi strong classifier trên tập test ( biển báo 26 cấm) 2.20: Tỷ lệ false positive của mỗi strong classifier trên tập train (biển nguy hiểm) 27 2.21: Tỷ lệ false positive của mỗi strong classifier trên tập train ( biển báo cấm) 27 2.22: Xem biển báo là một điểm trong không gian 28 2.23: Khoảng cách giữa các điểm 28 2.24: Chuyển vector x ban đầu có N chiều thành vector y còn K chiều 29 2.25: Tập huấn luyện biển báo 30 2.26: Vector riêng có giá trị riêng lớn nhất 32 2.27: Ma trận hiệp phương sai 33 2.28: Biểu đồ eigenvalues 34 3.1: Cấu trúc chương trình 37 3.2: Phát hiện biển báo 37 3.3: Nhận dạng biển báo 38 3.4: Dữ liệu của từng loại biển báo khác nhau đã được huấn luyện. 39 3.5: Dữ liệu biển báo đường hẹp bên trái được lưu vào thư mục 39 3.6: Khởi chạy chương trình 40 3.7: Giao diện chính của chương trình 40 3.8: Dữ liệu biển báo đã huấn luyện 41 3.9: Giao diện chương trình trong chức năng Recognize. 42 3.10: Giao diện chương trình trong chức năng Camera. 42 3.11: Phát hiện biển báo cấm trong hình ảnh chuẩn 43 3.12: Phát hiện biển báo nguy hiểm trong hình ảnh chuẩn 43 3.13: Phát hiện biển báo giao nhau và có vùng bị phát hiện sai. 44 3.14: Phát hiện biển báo giới hạn tốc độ 40 Km/h. 45 3.15: Phát hiện đúng 2 biển báo giới hạn tốc độc và biển báo đường hẹp bên 45 3.16: Phát hiện sai và nhiều vùng bị nhận là biển báo. 46 3.17: Huấn luyện biển báo Cấm ô tô và xe máy. 46 3.18: Kiểm tra và nhận dạng biển báo Cấm ô tô và xe máy 47 3.19: Huấn luyện biển báo Cấm mô tô. 47 3.20: Kiểm tra và nhận dạng biển báo Cấm mô tô. 48 3.21: Huấn luyện biển báo tín hiệu đèn giao thông 48 3.22: Kiểm tra và nhận dạng biển báo tín hiệu đèn giao thông 49 3.23: Huấn luyện biển báo vòng xoay phía trước 49 3.24: Kiểm tra biển báo vòng xoay phía trước nhưng bị cho kết quả sai. 50 1 MỞ ĐẦU 1. Lý do chọn đề tài Việt nam là một đất nước có hệ thống chính trị ổn định bậc nhất trong khu vực và trên thế giới, tình trạng khủng bố hầu như không có. Thế nhưng tình trạng thiệt mạng do tai nạn giao thông thì lại rất cao, trong năm 2017, toàn quốc xảy ra 20.280 vụ tai nạn giao thông, làm chết 8.279 người, bị thương 17.040 người, thiệt hại kinh tế ước tính đến cả tỷ USD. So với năm trước, số vụ tai nạn giao thông năm nay giảm 7% (Số vụ tai nạn giao thông từ ít nghiêm trọng trở lên giảm 5,6%; số vụ va chạm giao thông giảm 8,3%); số người chết giảm 4,7%; số người bị thương giảm 9,6% và số người bị thương nhẹ giảm 12,6%. Nhìn vào con số thống kê, bình quân 1 ngày trong năm 2017, trên địa bàn cả nước xảy ra 55 vụ tai nạn giao thông, gồm 27 vụ tai nạn giao thông từ ít nghiêm trọng trở lên và 28 vụ va chạm giao thông, làm 23 người chết, 47 người bị thương. Qua thống kê về lượng người chết và thiệt hại về kinh tế, ta thấy sự mất mát rất lớn và rất nhiều người đã là nạn nhân trực tiếp hoặc là hệ lụy, ảnh hưởng của tai nạn giao thông. Từ tình hình thực tế giao thông tại Việt Nam, có nhiều nguyên nhân gây ra các vụ tai nạn giao thông đường bộ, nhưng phần lớn là do tài xế không làm chủ tốc độ, thiếu quan sát hoặc không kịp nhận ra các loại biển báo và tín hiệu giao thông. Những mối nguy hiểm này đã được cảnh báo trước bởi hệ thống biển báo giao thông nhưng tai nạn vẫn thường xuyên xảy ra, gây không ít thiệt hại về tính mạng, tài sản của người tham gia giao thông và đặc biệt để lại hậu quả nặng nề cho gia đình, xã hội. Công nghệ thông tin ngày nay đã phát triển rất sôi động trong rất nhiều lĩnh vực trên toàn thế giới trong đó có Việt Nam, hầu hết các hoạt động hàng ngày của chúng ta đều liên quan đến công nghệ thông tin. Trong thực tế ngày nay, ứng dụng công nghệ thông tin đã được đưa vào các lĩnh vực kinh tế, chính trị, xã hội, quân sự…, đây là cơ hội phát triển và đồng thời cũng là thách thức to lớn đối với việc phát triển xã hội nói chung. Cho đến nay, vấn đề này đã được nhiều nghiên cứu trên thế giới quan tâm. Nhưng những nghiên cứu này chưa thực sự hiệu quả đối với giao thông đường bộ tại Việt Nam. Trong khi đó, tình hình nghiên cứu biển báo giao thông tại Việt Nam vẫn còn nhiều hạn chế và chưa đầy đủ. Vì vậy, Trong luận văn tốt nghiệp, tôi chọn đề tài “Áp dụng học máy trong nhận dạng biển báo giao thông” để nghiên cứu với mục đích tìm hiểu được nền tảng công nghệ, các lý thuyết cơ bản trong bài toán xử lý ảnh, học máy và áp dụng vào việc nhận dạng biển báo giao thông nhằm xây dựng chương trình nhắc nhở tài xế. 2 2. Mục tiêu nghiên cứu Nghiên cứu, tìm hiểu các phương pháp nhận dạng, áp dụng vào nhận diện biển báo giao thông, xây dựng chương trình, cài đặt thực nghiệm chương trình phát hiện và nhận dạng biển báo giao thông đường bộ từ hình ảnh tĩnh và video thu về, sau đó hiển thị thông tin cảnh báo dưới dạng hình ảnh hoặc âm thanh. 3. Đối tượng và phạm vi nghiên cứu Hệ thống các biển báo giao thông đường bộ ở Việt Nam gồm: - Hệ thống biển báo nguy hiểm - Hệ thống biển báo chỉ dẫn - Hệ thống biển cấm - Hệ thống biển hiệu lệnh 4. Phương pháp nghiên cứu 4.1. Phương pháp lý thuyết 4.1.1. Nghiên cứu lý thuyết học máy - Học có giám sát - Bán giám sát - Học không giám sát 4.1.2. Nghiên cứu xử lý ảnh - Tiền xử lý - Thuật toán Viola – Jone 4.2. Phương pháp thực nghiệm - Xây dựng bộ dữ liệu: ở bước này, tôi tiến hành thu thập dữ liệu bằng cách quay phim, chụp ảnh hệ thống biển báo giao thông trong thực tế - Tìm hiểu phương pháp phát hiện biển báo giao thông dựa trên trích chọn đặc trưng Haar-like kết hợp với bộ tăng tốc Adaboost. - Tìm hiểu phương pháp nhận dạng biển báo giao thông đường bộ: Luận văn có sử dụng phương pháp phân tích thành phần chính Principal Components Analysis (PCA) để nhận dạng biển báo giao thông. - Xây dựng mô hình nhận dạng sử dụng thuật toán - Cài đặt chương trình thử nghiệm - Đánh giá tỉ lệ nhận dạng 5. Ý nghĩa khoa học và thực tiễn Với đề tài “Áp dụng học máy trong nhận dạng biển báo giao thông”, mục tiêu là xây dựng một chương trình hỗ trợ lái xe hiệu quả và áp dụng trong thực tế, đầu vào là 3 hình ảnh giao thông phía trước, đầu ra của hệ thống là thông tin cảnh báo cho tài xế về hệ thống biển báo ở phía trước giúp tài xế tập trung và lái xe an toàn hơn. Khi đề tài được hoàn thành, sẽ là nền tảng để xây dựng phần mềm hỗ trợ đáp ứng được nhu cầu thực tế cho tài xế trong việc tham gia giao thông. Hơn nữa, đề tài này có thể là một giải pháp tình thế cho lĩnh vực giao thông ở Việt Nam trước khi đi lên xây dựng một hệ thống tổng thể thống nhất, toàn diện. 6. Bố cục của Luận văn Phần mở đầu: Nêu lên lý do chọn đề tài, đối tượng và phạm vi nghiên cứu và phương pháp nghiên cứu của đề tài. Phần nội dung: Chương 1: Tổng Quan Nghiên Cứu Chương này trình bày những lý thuyết cơ bản về xử lý ảnh, tổng quát các phương pháp phổ biến trong quá trình phát hiện và nhận dạng đối tượng, học máy. Chương 2: Mô Hình Đề Xuất Trong Nhận Dạng Biển Báo Giao Thông Chương này trình bày về ý tưởng đề tài, phát biểu bài toán nhận dạng biển báo giao thông và trình bày nền tảng công nghệ, chi tiết các thuật toán hỗ trợ trong việc phát hiện và nhận dạng biển báo bao gồm: Trích chọn đặc trưng Haar-like, bộ tăng tốc Adaboost, phân tích thành phần chính PCA. Chương 3: Thực Nghiệm Và Đánh Giá Kết Quả Chương này mô tả chương trình cài đặt , thực hiện thực nghiệm và đánh giá kết quả. Sử dụng ngôn ngữ Java, và bộ thư viện xử lý ảnh mã nguồn mở OpenCV để xây dựng chương trình. Sau đó phân tích và đánh giá kết quả nhận dạng. Phần kết luận và hướng phát triển của đề tài. 4 CHƯƠNG 1 TỔNG QUAN NGHIÊN CỨU Chương này trình bày những lý thuyết cơ bản về xử lý ảnh, tổng quát các phương pháp phổ biến trong quá trình phát hiện và nhận dạng đối tượng, học máy. 1.1. Tổng quan về xử lý ảnh 1.1.1. Tổng quan về xử lý ảnh Hình 1.1: Các bước cơ bản trong quá trình xử lí ảnh Xử lý ảnh (XLA) [1] là đối tượng nghiên cứu của lĩnh vực thị giác máy, là quá trình biến đổi từ một ảnh ban đầu sang một ảnh mới với các đặc tính và tuân theo ý muốn của người sử dụng. Xử lý ảnh có thể gồm nhiều quá trình: phân tích, phân lớp các đối tượng, làm tăng chất lượng, phân đoạn và tách cạnh, gán nhãn cho vùng hay quá trình biên dịch các thông tin hình ảnh của ảnh. Cũng như xử lý dữ liệu bằng đồ hoạ, xử lý ảnh số là một lĩnh vực của tin học ứng dụng. Xử lý dữ liệu bằng đồ họa đề cập đến những ảnh nhân tạo, các ảnh này được xem xét như là một cấu trúc dữ liệu và được tạo bởi các chương trình. Xử lý ảnh số bao gồm các phương pháp và kỹ thuật biến đổi, để truyền tải hoặc mã hoá các ảnh tự nhiên. Mục đích của xử lý ảnh gồm: + Biến đổi ảnh làm tăng chất lượng ảnh. + Tự động nhận dạng ảnh, đoán nhận ảnh, đánh giá các nội dung của ảnh. + Nhận biết và đánh giá các nội dung của ảnh là sự phân tích một hình ảnh thành những phần có ý nghĩa để phân biệt đối tượng này với đối tượng khác, dựa vào đó ta có thể mô tả cấu trúc của hình ảnh ban đầu. Có thể liệt kê một số phương pháp nhận dạng cơ bản như nhận dạng ảnh của các đối tượng trên ảnh, tách cạnh, 5 phân đoạn hình ảnh,…Kỹ thuật này được dùng nhiều trong y học (xử lý tế bào, nhiễm sắc thể), nhận dạng chữ trong văn bản. 1.1.2. Các quá trình xử lý ảnh Thu nhận ảnh Tiền xử lý Phân đoạn ảnh Tách các đặc tính Nhận dạng và giải thích Hình 1.2: Các giai đoạn chính trong xử lý ảnh Thu nhận ảnh: Đây là công đoạn đầu tiên mang tính quyết định đối với quá trình XLA. Ảnh đầu vào sẽ được thu nhận qua các thiết bị như camera, sensor, máy scanner,v.v… và sau đó các tín hiệu này sẽ được số hóa. Việc lựa chọn các thiết bị thu nhận ảnh sẽ phụ thuộc vào đặc tính của các đối tượng cần xử lý. Các thông số quan trọng ở bước này là độ phân giải, chất lượng màu, dung lượng bộ nhớ và tốc độ thu nhận ảnh của các thiết bị. Tiền xử lý: Ở bước này, ảnh sẽ được cải thiện về độ tương phản, khử nhiễu, khử bóng, khử độ lệch,v.v… với mục đích làm cho chất lượng ảnh trở lên tốt hơn nữa, chuẩn bị cho các bước xử lý phức tạp hơn về sau trong quá trình XLA. Quá trình này thường được thực hiện bởi các bộ lọc. Phân đoạn ảnh: phân đoạn ảnh là bước then chốt trong XLA. Giai đoạn này phân tích ảnh thành những thành phần có cùng tính chất nào đó dựa theo biên hay các vùng liên thông. Tiêu chuẩn để xác định các vùng liên thông có thể là cùng màu, cùng mức xám v.v… Mục đích của phân đoạn ảnh là để có một miêu tả tổng hợp về nhiều phần tử khác nhau cấu tạo lên ảnh thô. Vì lượng thông tin chứa trong ảnh rất lớn, trong khi đa số các ứng dụng chúng ta chỉ cần trích một vài đặc trưng nào đó, do vậy cần có một quá trình để giảm lượng thông tin khổng lồ đó. Quá trình này bao gồm phân vùng ảnh và trích chọn đặc tính chủ yếu. Tách các đặc tính: Kết quả của bước phân đoạn ảnh thường được cho dưới dạng dữ liệu điểm ảnh thô, trong đó hàm chứa biên của một vùng ảnh, hoặc tập hợp tất cả các điểm ảnh thuộc về chính vùng ảnh đó. Trong cả hai trường hợp, sự chuyển đổi dữ liệu thô này thành một dạng thích hợp hơn cho việc xử lý trong máy tính là rất cần thiết. Để chuyển đổi chúng, câu hỏi đầu tiên cần phải trả lời là nên biểu diễn một vùng ảnh dưới dạng biên hay dưới dạng một vùng hoàn chỉnh gồm tất cả những điểm ảnh thuộc về nó. Biểu diễn dạng biên cho một vùng phù hợp với những ứng dụng chỉ quan 6 tâm chủ yếu đến các đặc trưng hình dạng bên ngoài của đối tượng, ví dụ như các góc cạnh và điểm uốn trên biên chẳng hạn. Biểu diễn dạng vùng lại thích hợp cho những ứng dụng khai thác các tính chất bên trong của đối tượng, ví dụ như vân ảnh hoặc cấu trúc xương của nó. Sự chọn lựa cách biểu diễn thích hợp cho một vùng ảnh chỉ mới là một phần trong việc chuyển đổi dữ liệu ảnh thô sang một dạng thích hợp hơn cho các xử lý về sau. Chúng ta còn phải đưa ra một phương pháp mô tả dữ liệu đã được chuyển đổi đó sao cho những tính chất cần quan tâm đến sẽ được làm nổi bật lên, thuận tiện cho việc xử lý chúng. Nhận dạng và giải thích: Đây là bước cuối cùng trong quá trình XLA. Nhận dạng ảnh có thể được nhìn nhận một cách đơn giản là việc gán nhãn cho các đối tượng trong ảnh. Ví dụ đối với nhận dạng chữ viết, các đối tượng trong ảnh cần nhận dạng là các mẫu chữ, ta cần tách riêng các mẫu chữ đó ra và tìm cách gán đúng các ký tự của bảng chữ cái tương ứng cho các mẫu chữ thu được trong ảnh. Giải thích là công đoạn gán nghĩa cho một tập các đối tượng đã được nhận biết. Không phải bất kỳ một ứng dụng XLA nào cũng bắt buộc phải tuân theo tất cả các bước xử lý đã nêu ở trên, tùy theo mục đích sử dụng dữ liệu của từng ứng dụng XLA. Ví dụ như các ứng dụng chỉnh sửa ảnh nghệ thuật chỉ dừng lại ở bước tiền xử lý. Một cách tổng quát thì những chức năng xử lý bao gồm cả nhận dạng và giải thích thường chỉ có mặt trong hệ thống phân tích ảnh tự động hoặc bán tự động, được dùng để rút trích ra những thông tin quan trọng từ ảnh, ví dụ như các ứng dụng nhận dạng ký tự quang học, nhận dạng chữ viết tay v.v… 1.1.3. Ảnh và biểu diễn ảnh Ảnh trong thực tế là một ảnh liên tục cả về không gian và giá trị độ sáng. Để có thể xử lý ảnh bằng máy tính thì cần thiết phải tiến hành số hóa ảnh. Quá trình số hóa biến đổi các tín hiệu liên tục sang tín hiệu rời rạc thông qua quá trình lấy mẫu (rời rạc hóa về không gian) và lượng tử hóa các thành phần giá trị mà về nguyên tắc bằng mắt thường không thể phân biệt được hai điểm liền kề nhau. Các điểm như vậy được gọi là các pixel (Picture Element) hay các phần tử ảnh hoặc điểm ảnh. Ở đây cần phân biệt khái niệm pixel hay đề cập đến trong các hệ thống đồ họa máy tính. Để tránh nhầm lẫn ta gọi khái niệm pixel này là pixel thiết bị. Khái niệm pixel thiết bị có thể xem xét như sau: khi ta quan sát màn hình (trong chế độ đồ họa), màn hình không liên tục mà gồm các điểm nhỏ, gọi là pixel. Mỗi pixel gồm một tập tọa độ (x, y) và màu. Như vậy mỗi ảnh là tập hợp các điểm ảnh. Khi được số hóa nó thường được biểu diễn bởi mảng 2 chiều I(n,p): n là dòng và p là cột. Về mặt toán học có thể xem ảnh là một hàm hai biến f(x,y) với x, y là các biến tọa độ. Giá trị số ở điểm (x,y) tương ứng 7 với giá trị xám hoặc độ sáng của ảnh (x là các cột còn y là các hàng). Giá trị của hàm ảnh f(x,y) được hạn chế trong phạm vi của các số nguyên dương. 0 ≤ f(x,y) ≤ fmax. Với ảnh đen trắng mức xám của ảnh có thể được biểu diễn bởi một số như sau: Trong đó SBW( λ) là đặc tính phổ của cảm biến được sử dụng và k là hệ số tỷ lệ xích. Vì sự cảm nhận độ sáng có tầm quan trọng hàng đầu đối với ảnh đen trắng nên SBW( λ) được chọn giống như là hiệu suất sáng tương đối. Vì f biểu diễn công suất trên đơn vị diện tích, nên nó bao giờ cũng không âm và hữu hạn. 0≤ f ≤ fmax Trong đó fmax là giá trị lớn nhất mà f đạt được. Trong xử lý ảnh, f được chia thang sao cho nó nằm trong một phạm vi thuận lợi nào đó. Thông thường đối với ảnh xám, giá trị fmax là 255 (28=256) bởi vì mỗi phần tử ảnh được mã hóa bởi một byte. Khi quan tâm đến ảnh màu ta có thể mô tả màu qua ba hàm số: thành phần màu đỏ qua R(x,y), thành phần màu lục qua G(x,y) và thành phần màu lam qua B(x,y). Bộ ba giá trị R, G, và B nhận được từ: Ở đó SR(λ), SG(λ) và SB(λ) theo thứ tự là những đặc tính phổ của các cảm biến (bộ lọc) đỏ, lục và lam. R, G, B cũng không âm và hữu hạn. Ảnh có thể được biểu diễn theo một trong hai mô hình: mô hình Vector hoặc mô hình Raster. Mô hình Vector: Ngoài mục đích tiết kiệm không gian lưu trữ, dễ dàng hiển thị và in ấn, các ảnh biểu diễn theo mô hình vector còn có ưu điểm cho phép dễ dàng lựa chọn, sao chép, di chuyển, tìm kiếm…Theo những yêu cầu này thì kỹ thuật biểu diễn vector tỏ ra ưu việt hơn. Trong mô hình này, người ta sử dụng hướng vector của các điểm ảnh lân cận để mã hóa và tái tạo lại hình ảnh ban đầu. Các ảnh vector được thu 8 nhận trực tiếp từ các thiết bị số hóa như Digitalize hoặc được chuyển đổi từ các ảnh Raster thông qua các chương trình vector hóa. Mô hình Raster: là mô hình biểu diễn ảnh thông dụng nhất hiện nay. Ảnh được biểu diễn dưới dạng ma trận các điểm ảnh. Tùy theo nhu cầu thực tế mà mỗi điểm ảnh có thể được biểu diễn bởi một hay nhiều bit. Mô hình Raster thuận lợi cho việc thu nhận, hiển thị và in ấn. Các ảnh được sử dụng trong phạm vi của đề tài này cũng là các ảnh được biểu diễn theo mô hình Raster. Khi xử lý các ảnh Raster chúng ta có thể quan tâm đến mối quan hệ trong vùng lân cận của các điểm ảnh. Các điểm ảnh có thể xếp hàng trên một lưới (raster) hình vuông, lưới hình lục giác hoặc theo một cách hoàn toàn ngẫu nhiên với nhau. Cách sắp xếp theo hình vuông là được quan tâm đến nhiều nhất và có hai loại: điểm 4 láng giềng (4 liền kề) hoặc 8 láng giềng (8 liền kề). Với điểm 4 láng giềng, một điểm ảnh I(i, j) sẽ có điểm kế cận theo 2 hướng i và j; trong khi đó với điểm 8 láng giềng, điểm ảnh I(i, j) sẽ có 4 điểm kế cận theo 2 hướng i, j và 4 điểm kế cận theo hướng chéo 45o (Xem hình 1-3). 8 láng giềng 4 láng giềng Hình 1.3: Quan hệ trong vùng lân cận giữa các điểm ảnh 1.1.4. Phạm vi ứng dụng của xử lý ảnh Xử lý ảnh đã đem lại nhiều ứng dụng trong nhiều lĩnh vực khác nhau: y học, khoa học hình hình sự, khí tượng thuỷ văn, quản lý, ... Quản lý là là một trong những ứng dụng quan trọng của xử lý ảnh. Cùng với sự bùng nổ của kinh tế thị trường. Khối lượng quản lý càng lớn, như quản lý hồ sơ, quản lý phiếu điều tra trong công tác thống kê, các câu hỏi trắc nghiệm. Để thực hiện các công việc trên một cách chính xác, nhanh chóng và hiệu quả. Xử lý ảnh và nhận dạng đã nghiên cứu và phát triển mạnh mẽ bài toán nhập liệu tự động. 9 1.2. Học máy 1.2.1. Tổng quan học máy Học máy [6] là một lĩnh vực của trí tuệ nhân tạo liên quan đến việc phát triển các kĩ thuật cho phép các máy tính có thể “học”. Cụ thể hơn, học máy là một phương pháp để tạo ra các chương trình máy tính bằng việc phân tích các tập dữ liệu. Học máy có liên quan lớn đến thống kê, vì cả hai lĩnh vực đều nghiên cứu việc phân tích dữ liệu, nhưng khác với thống kê, học máy tập trung vào sự phức tạp của các giải thuật trong việc thực thi tính toán. Nhiều bài toán suy luận được xếp vào loại bài toán khó, vì thế một phần của học máy là nghiên cứu sự phát triển các giải thuật suy luận xấp xỉ mà có thể xử lý được. Học máy có tính ứng dụng rất cao bao gồm máy truy tìm dữ liệu, chẩn đoán y khoa, phát hiện thẻ tín dụng giả, phân tích thị trường chứng khoán, phân loại các chuỗi DNA, nhận dạng tiếng nói và chữ viết, dịch tự động, chơi trò chơi và cử động rô-bốt. 1.2.2. Các phương pháp học máy 1.2.2.1. Học không giám sát Học không giám sát (Unsupervised Learning) là một phương pháp nhằm tìm ra một mô hình mà phù hợp với các tập dữ liệu quan sát. Nó khác biệt với học có giám sát ở chỗ là đầu ra đúng tương ứng cho mỗi đầu vào là không biết trước. Trong học không có giám sát, đầu vào là một tập dữ liệu được thu thập. Học không có giám sát thường đối xử với các đối tượng đầu vào như là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ được xây dựng cho tập dữ liệu đó. Học không giám sát có thể được dùng kết hợp với suy diễn Bayes (Bayesian inference) để cho ra xác suất có điều kiện cho bất kì biến ngẫu nhiên nào khi biết trước các biến khác. Học không giám sát cũng hữu ích cho việc nén dữ liệu: về cơ bản, mọi giải thuật nén dữ liệu hoặc là dựa vào một phân bố xác suất trên một tập đầu vào một cách tường minh hay không tường minh. Có rất nhiều thuật toán học không giám sát được ra đời và phát triển nhằm giải quyết bài toán phân cụm phục vụ khai thác hiệu quả nguồn dữ liệu chưa gán nhãn nhiều và rất đa dạng. Việc lựa chọn sử dụng thuật toán nào tuỳ thuộc vào dữ liệu và mục đích của từng bài toán. 1.2.2.2. Học có giám sát Học có giám sát (Supervised Learning) là một kĩ thuật của ngành học máy để xây dựng một hàm 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, và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị 10 liên tục, hay có thể là dự đoán một nhãn phân loại cho một đối tượng đầu vào. Nhiệm vụ của chương trình học có giám sát là dự đoán giá trị của các cặp đầu vào và đầu ra tương ứng. Chương trình học 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ý. Một số thuật toán thường được lựa chọn khi xây dựng bộ phân lớp gồm có: mạng nơron (Neural Network – Nnet), Vector trọng tâm (Centroid–base vector), tuyến tính bình phương nhỏ nhất (Linear Least Square Fit – LLSF), máy vector hỗ trợ (Support Vector Machine – SVM), hạt nhân phân tích biệt thức, K láng giềng gần nhất (K Nearest Neighbours – KNN), tiếp cận xác suất thống kê (Naive Bayes – NB), cây quyết định (Decision Tree – DT). 1.2.2.3. Học bán giám sát Học bán giám sát là một lớp của kỹ thuật học máy, sử dụng cả dữ liệu đã gán nhãn và chưa gán nhãn để huấn luyện – điển hình là một lượng nhỏ dữ liệu có gán nhãn cùng với lượng lớn dữ liệu chưa gán nhãn. Có thể xem học bán giám sát là trung gian đứng giữa học không giám sát và có giám sát. Xét qua nhiều nghiên cứu, ta có thể nhận thấy dữ liệu không gán nhãn, khi được sử dụng kết hợp với một chút dữ liệu có gán nhãn, có thể cải thiện đáng kể độ chính xác. Để gán nhãn dữ liệu cho một bài toán học máy thường đòi hỏi một chuyên viên có kĩ năng để phân loại bằng tay các ví dụ huấn luyện. Chi phí cho quy trình này khiến tập dữ liệu được gán nhãn hoàn toàn trở nên không khả thi, trong khi dữ liệu không gán nhãn thường tương đối rẻ tiền. Trong tình huống đó, học bán giám sát có giá trị thực tiễn lớn lao. Một số thuật toán thường được sử dụng gồm có: thuật toán Cực đại kỳ vọng (EM – Expectation Maximization), SVM truyền dẫn (TSVM – Transductive Support Vector Machine), Self-training, Co-training và các phương pháp dựa trên đồ thị (graphbased). Việc lựa chọn thuật toán nào dựa trên một số định hướng: nếu các lớp dữ liệu có tính phân cụm cao thì nên dùng EM với mô hình hỗn hợp sinh; nếu đã sử dụng SVM thì mở rộng thành TSVM; khi khó nâng cấp mô hình học có giám sát đã có, thì nên dùng self-training; nếu các đặc trưng của dữ liệu phân chia tự nhiên thành hai phần riêng rẽ thì nên dùng Co-training; còn nếu hai mẫu dữ liệu có đặc trưng tương tự nhau hướng tới một lớp thì sử dụng phương pháp dựa trên đồ thị. 1.2.2.4. Học tăng cường Học tăng cường [9] là phương pháp máy tính đưa ra quyết định hành động (action) và nhận kết quả phản hồi (response/reward) từ môi trường (environment). Sau đó máy tính tìm cách chỉnh sửa cách ra quyết định hành động của mình. Các thuật toán học tăng cường được chia thành hai loại chính đó là: học dựa trên mô hình (model based) và học không có mô hình (model free). Đại điện cho kiểu học 11 dựa trên mô hình phải kể đến phương pháp quy hoạch động (Dynamic Programming DP), đại diện cho kiểu học không có mô hình là phương pháp Monte Carlo và phương pháp TD (Temporal Difference). 1.2.2.5. Các ứng dụng của học máy Học máy có ứng dụng trải rộng khắp trong các ngành khoa học/sản xuất, đặc biệt những ngành cần phân tích khối lượng dữ liệu khổng lồ. Một số ứng dụng phổ biến: - Xử lý ngôn ngữ tự nhiên (Natural Language Processing): xử lý văn bản, - giao tiếp người – máy, … Nhận dạng (Pattern Recognition): nhận dạng tiếng nói, chữ viết tay, vân - tay, thị giác máy (Computer Vision)… Tìm kiếm (Search Engine) Chẩn đoán trong y tế: phân tích ảnh X-quang, các hệ chuyên gia chẩn đoán - tự động. Tin sinh học: phân loại chuỗi gene, quá trình hình thành gene/protein Vật lý: phân tích ảnh thiên văn, tác động giữa các hạt … Phát hiện gian lận tài chính (financial fraud): gian lận thẻ tín dụng… - Phân tích thị trường chứng khoán (stock market analysis) Chơi trò chơi: tự động chơi cờ, hành động của các nhân vật ảo. Rôbốt: là tổng hợp của rất nhiều ngành khoa học, trong đó học máy tạo nên hệ thần kinh/bộ não của người máy. 1.3. Các phương pháp nhận dạng đối tượng 1.3.1. Phương pháp Neural Networks (NN) Mạng noron nhân tạo (Artifical Neural Networks) mô phỏng lại mạng noron sinh học là một cấu trúc khối gồm các đơn vị tính toán đơn giản được liên kết chặt chẽ với nhau trong đó các liên kết giữa các noron quyết định chức năng của mạng. Về cơ bản mạng Neural là một mạng các phần tử (gọi là neural) kết nối với nhau thông qua các liên kết (các liên kết này được gọi là trọng số liên kết) để thực hiện một công việc cụ thể nào đó. Khả năng xử lý của mạng neural được hình thành thông qua quá trình hiệu chỉnh trọng số liên kết giữa các neural, nói cách khác là học từ tập hợp các mẫu huấn luyện. Ưu điểm: Dễ cài đặt cùng với khả năng học và tổng quát hoá rất cao, tốc độ xử lý nhanh, linh hoạt và dễ bảo trì. Nhược điểm: Tính chậm và xác suất không cao không có quy tắc tổng quát để xác định cấu trúc mạng và các tham số học tối ưu cho một (lớp) bài toán nhất định, 12 tiêu chuẩn thu thập cơ sở dữ liệu huấn luyện còn khắt khe, đòi hỏi thời gian xử lý cao với mạng một mạng Neural lớn. 1.3.2. Phương pháp Support Vector Machine (SVM) Cho trước một tập huấn luyện, các ảnh được biểu diễn dưới dạng vector. Trong không gian vector, mỗi vertor được biểu diễn bởi một điểm. Phương pháp SVM sẽ tìm một siêu phẳng quyết định để phân chia không gian vector thành hai lớp. Chất lượng của siêu phẳng này phụ thuộc vào khoảng cách giữa các vector, tức là phụ thuộc vào các đặc trưng của ảnh. Ưu điểm: Cho kết quả nhận dạng với độ chính xác cao, bài toán huấn luyện SVM thực chất là bài toán trên một tập lồi, do đó SVM luôn có nghiệm toàn cục và duy nhất, đây chính là điểm khác biệt rõ nhất giữa SVM so với phương pháp mạng Neural, vì mạng Neural vốn tồn tại nhiều điểm cực trị địa phương. Nhược điểm: Hạn chế lớn nhất của SVM là tốc độ phân lớp rất chậm, tùy thuộc vào số lượng các véc tơ hỗ trợ, giai đoạn huấn luyện SVM đòi hỏi bộ nhớ rất lớn, do đó các bài toán huấn luyện với số lượng mẫu lớn sẽ gặp trở ngại trong vấn đề lưu trữ. Hiệu quả phân lớp của SVM phụ thuộc vào hai yếu tố: giải bài toán và lựa chọn hàm nhân. 1.3.3. Phương pháp Linear Discriminant Analysis Mục đích của LDA – Linear Discriminant Analysis là tìm cách phân loại các đối tượng (người, sự vật,…) vào một trong hai hay nhiều lớp đã được xác định trước dựa vào các đặt trưng (feature) dùng để mô tả đối tượng (ví dụ như các đặc trưng dùng để mô tả đối tượng khách hàng là giới tính, tuổi, nghề nghiệp, thu nhập,…) Ưu điểm: Dễ dàng hơn để đào tạo, phương sai thấp, hiệu quả hơn nếu mô hình là chính xác, LDA làm việc tốt khi số mẫu là lớn. Nhược điểm: LDA gặp phải vấn đề khi tổng số mẫu huấn luyện ít hơn so với kích thước của không gian đặc trưng. 1.3.4. Phương pháp Naive Bayes (NB) Ý tưởng cơ bản của cách tiếp cận NB là sử dụng xác suất có điều kiện. Ưu điểm: Cho độ chính xác cao khi kết hợp với các phương pháp khác. Nhược điểm: Chi phí thời gian để đếm mẫu, phải kết hợp với các phương pháp khác 1.3.5. Phương pháp Principal Component Analysis (PCA) Principal Component Analysis [5] là một thuật toán được sử dụng để tạo ra một ảnh mới từ ảnh ban đầu. Ảnh mới này có kích thước nhỏ hơn nhiều so với ảnh ban đầu nhưng vẫn mang những đặc trưng cơ bản nhất của ảnh cần nhận dạng. Nói một cách ngắn gọn, mục tiêu của PCA là tìm một không gian mới (với số chiều nhỏ hơn không gian cũ). Các trục tọa độ trong không gian mới được xây dựng 13 sao cho trên mỗi trục, độ biến thiên của dữ liệu trên đó là lớn nhất có thể. Ưu điểm: Tìm được các đặc tính tiêu biểu của đối tượng cần nhận dạng mà không cần phải xác định các thành phần và mối quan hệ giữa các thành phần đó, thuật toán có thể thức hiện tốt với các ảnh có độ phân giải cao, do PCA sẽ thu gọn ảnh thành một ảnh có kích thước nhỏ hơn, PCA có thể kết hợp với các phương pháp khác để mang lại hiệu quả nhận dạng cao hơn. Nhược điểm: PCA chỉ làm việc với dữ liệu numeric, PCA rất nhạy với nhiễu, Không phù hợp với các mô hình phi tuyến do PCA hoàn toàn dựa trên các biến đổi tuyến tính, cài đặt thuật toán phức tạp. 1.4. Kết chương Nội dung chương I được trình bày ở trên đã nêu ra những vấn đề cơ bản tương đối chi tiết về lý thuyết Xử lý ảnh, Học máy và nêu ưu điểm và nhược điểm cụ thể của từng phương pháp nhận dạng đối tượng đã được nghiên cứu trước đây và có thể áp dụng được, để thực hiện nghiên cứu trong đề tài này.