Tóm tắt luận văn Thạc sĩ: Kết hợp so khớp Spatial Pyramid và vecto hỗ trợ SVM trong nhận dạng khung cảnh tự nhiên

Chia sẻ: Nguyễn Thị Thu Trang | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

85
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài nghiên cứu và phân tích xây dựng phần mềm nhận dạng khung cảnh tự nhiên Nội dung chính của luận văn được tổ chức thành 3 chương. Chương 1 Tổng quan giới thiệu bài toán nhận dạng ảnh,các hướng tiếp cận bài toán, mô hình chung của hệ thống nhận dạng và một số ứng dụng của nhận dạng,...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt luận văn Thạc sĩ: Kết hợp so khớp Spatial Pyramid và vecto hỗ trợ SVM trong nhận dạng khung cảnh tự nhiên

1 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ---------------------------------------- NGUYỄN THỊ NGỌC HÀ KẾT HỢP SO KHỚP SPATIAL PYRAMID VÀ VECTO HỖ TRỢ SVM TRONG NHẬN DẠNG KHUNG CẢNH TỰ NHIÊN Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 Người hướng dẫn khoa học: PGS. TS TỪ MINH PHƯƠNG TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – 2012
2 MỞ ĐẦU Với sự bùng nổ của dữ liệu ảnh, việc nhận dạng ảnh theo các lớp ngữ nghĩa là một trong những nhu cầu cơ bản cho việc quản lý và truy vấn ảnh dựa trên nội dung. Thêm nữa, nhận dạng ảnh là một trong những bài toán cơ bản trong lĩnh vực thị giác máy tính và ứng dụng máy học đã nhận được sự quan tâm của nhiều nhà khoa học trên thế giới. Bài toán nhận dạng ảnh có rất nhiều thách thức từ việc ảnh được chụp dưới nhiều góc độ khác nhau, điều kiện chiếu sáng khác nhau, sự đa dạng các thể hiện của cùng một lớp ngữ nghĩa cũng như sự phức tạp của thông tin nền trong ảnh. Để giải quyết bài toán nhận dạng ảnh có 4 hướng tiếp cận, đó là so khớp mẫu, nhận dạng thống kê, nhận dạng dựa vào cấu trúc và nhận dạng theo mạng nơron. Trong đó, hướng tiếp cận dựa trên so khớp mẫu được áp dụng rộng rãi và mang lại kết quả cao trong bài toán nhận dạng ảnh nói riêng và trong thị giác máy tính nói chung. Biểu diễn một ví dụ đơn lẻ bằng tập các đặc trưng cục bộ hoặc các bộ phận bao gồm nó thường rất hữu ích. Ví dụ, trong thị giác máy tính, một hình ảnh có thể được mô tả bởi các đặc trưng cục bộ được trích chọn từ các điểm hấp dẫn “nhô ra” (salient interest points) của ảnh. Tương tự như vậy trong xử lý ngôn ngữ tự nhiên, các tài liệu và chủ đề được đặc trưng bởi túi các từ (bag of words). Tuy nhiên, việc đánh giá độ giống nhau giữa các mẫu theo phương pháp này là một thách thức khi tập các đặc trưng gồm nhiều yếu tố, các yếu tố không có thứ tự. Để so sánh tập các đặc trưng này, các nhà nghiên cứu thường cố gắng sử dụng những giải pháp phù hợp tốn ít
3 chi phí nhất, tuy nhiên đây lại là những tính toán tốn kém và trở nên không khả thi khi tập này có kích thước lớn. Những phương pháp trước đây nhận đầu vào là các véctơ với mỗi chiều tương ứng là một đặc trưng toàn cục riêng biệt. Nhược điểm của những phương pháp này là không tính tới vị trí tương đối của các đặc trưng, giải quyết với những đặc trưng tương ứng rõ ràng, điều này làm cho việc tính toán tốn kém, hạn chế việc sử dụng những đầu vào có phạm vi lớn; Do đó để cải thiện những nhược điểm này Kristen Grauman và Trevor Darrell đã phát triển phương pháp so khớp phân cấp (Pyramid Matching – viết tắt là PM) – một hàm so khớp thời gian tuyến tính mới thông qua tập các đặc trưng không có thứ tự. Mặc dù vậy phương pháp này vẫn còn nhược điểm đó là bỏ qua thông tin về không gian của bức ảnh; một phương pháp mới ra đời nhằm giải quyết nhược điểm trên đó là phương pháp so khớp không gian phân cấp (Spatial Pyramid Matching – SPM). Với những lý do nêu trên tôi đã lựa chọn đề tài: “Kết hợp so khớp spatial pyramid và máy véctơ hỗ trợ SVM trong nhận dạng khung cảnh tự nhiên” - Mục đích nghiên cứu:  Nghiên cứu trích chọn đặc trưng cục bộ bất biến (Scale Invariant Feature Transform – SIFT)  Tìm hiểu phương pháp SPM  Nghiên cứu phương pháp học máy SVM  Xây dựng chương trình demo từ những nghiên cứu và tìm hiểu nói trên. - Đối tượng và phạm vi nghiên cứu:
4 25  Trích chọn đặc trưng SIFT: đây là giải thuật do David KẾT LUẬN VÀ KIẾN NGHỊ G.Lowe đưa ra từ năm 2004.  Phương pháp SPM: đây là phát triển từ phương pháp PM Kết luận do Kristen Grauman và Trevor Darrell phát triển. Luận văn định hướng nội dung nghiên cứu vào phương pháp  Phương pháp học máy SVM: SVM là một kỹ thuật mới SPM, mô hình kết hợp SPM và phương pháp học máy SVM và ứng và có nhiều triển vọng, được phát triển bởi Vapnik và các dụng vào bài toán nhận dạng khung cảnh tự nhiên. đồng sự tại AT&T Bell Labs. Từ những nghiên cứu trên đây, tôi thấy phương pháp SPM Dựa vào nghiên cứu, phân tích xây dựng phần mềm nhận mô tả ảnh tốt thông qua một chuỗi các độ phân giải khác nhau, do dạng khung cảnh tự nhiên vậy có thể mô tả thông tin tổng quát ở độ phân giải thô, cũng như Nội dung chính của luận văn được tổ chức thành 3 chương. thông tin chi tiết của ảnh ở độ phân giải mịn hơn. Ngoài ra, SPM có Chương 1. Tổng quan. Giới thiệu bài toán nhận dạng khả năng xử lý tốt trên tập hợp các đặc trưng không thứ tự như PM. ảnh,các hướng tiếp cận bài toán, mô hình chung của hệ thống nhận Sự kết hợp của SPM với trích chọn đặc trưng SIFT và SVM cho thấy dạng và một số ứng dụng của nhận dạng. đạt được hiệu quả cao. Mô hình trên cho phép đạt kết quả cao hơn so với cách tiếp cận kết hợp SIFT và SVM trên cơ sở dữ liệu phân loại Chương 2. Cơ sở lý thuyết. Trình bày những lý thuyết cơ khung cảnh MIT scene. bản về trích chọn đặc trưng SIFT, so khớp phân cấp không gian SPM và phương pháp học máy SVM được sử dụng trong luận văn. Kiến nghị Chương 3. Kết hợp SPM và SVM để nhận dạng. Giới Nghiên cứu phân loại ảnh dựa trên hướng tiếp cận kernel. thiệu sơ lược về bộ dữ liệu sử dụng, các công cụ, tham số sử dụng để xây dựng chương trình ứng dụng SPM kết hợp học máy SVM trong nhận dạng khung cảnh. Ngoài ra, trong chương 3 cũng so sánh hiệu quả phân loại của phương pháp đề xuất và phương pháp kết hợp SIFT và SVM. Phần kết luận và kiến nghị tổng kết những kết quả đã đạt được của luận văn và hướng phát triển nghiên cứu tiếp theo.
24 5 3.5 So sánh phương pháp thực nghiệm và phương pháp Chương 1 - TỔNG QUAN kết hợp SIFT và SVM Kết quả thực nghiệm kết hợp SIFT và SVM như sau 1.1 Bài toán nhận dạng ảnh Nhận dạng ảnh dựa trên lý thuyết về nhận dạng. Nhận dạng Kích thước từ M = 16 M = 100 M = 200 là quá trình phân loại các đối tượng được biểu diễn theo một mô hình điển nào đó vào một lớp dựa theo quy luật và các mẫu chuẩn. Quá trình bao gồm việc xác định các lớp của đối tượng sao cho có thể phân Độ chính xác 69.32% 83.68% 80.58% biệt. Bảng 3.3 Kết quả phân loại khung cảnh kết hợp SIFT và SVM Hệ thống nhận dạng sẽ thực hiện 2 việc: huấn luyện và nhận Từ bảng 3.2 và bảng 3.3 chúng ta có thể thấy rằng khi phân dạng. Trong quá trình huấn luyện, các đặc trưng sẽ được trích chọn loại với cùng một cơ sở dữ liệu MIT sence so thì phương pháp kết phù hợp cho việc biểu diễn và bộ phân loại sẽ được huấn luyện để hợp SPM và SVM có độ chính xác cao hơn so với phương pháp kết phân chia không gian đặc trưng. Quá trình nhận dạng, bộ phân loại đã hợp SIFT và SVM. được huấn luyện gán một mẫu đầu vào vào một trong các lớp dựa trên các đặc trưng đó. Một mô hình sẽ được xây dựng dựa trên các dữ liệu huấn luyện và mô hình này sẽ được sử dụng để phân loại một dữ liệu mới vào các lớp. Hình 1.1 Quá trình huấn luyện và nhận dạng của hệ thống nhận dạng
6 23 1.2 Các hướng tiếp cận trong bài toán nhận dạng Có 4 hướng tiếp cận chính cho bài toán nhận dạngError! Reference source not found. :  Nhận dạng dựa vào so khớp mẫu  Nhận dạng thống kê  Nhận dạng dựa vào cấu trúc  Nhận dạng dựa vào mạng nơron 1.2.1 So khớp mẫu Hình 3.8 Ảnh cần nhận dạng khung cảnh So khớp là một thuật toán chung trong nhận dạng, nó được sử dụng để xác định những điểm giống nhau giữa hai thực thể (các điểm, các góc, hình dạng…). Trong so khớp mẫu, các mẫu cần nhận dạng là biết trước và được so khớp với các mẫu đã lưu trữ, có tính tới các trường hợp mẫu bị quay, thay đổi tỉ lệ và bị tịnh tiến. 1.2.2 Nhận dạng thống kê 1.2.3 Nhận dạng dựa vào cấu trúc 1.2.4 Nhận dạng theo mạng nơron 1.3 Mô hình chung của hệ thống nhận dạng Về cơ bản, một hệ thống nhận dạng thường gồm các khối Hình 3.9 Ảnh được nhận dạng sau khi chạy chương trình chính, phù hợp với các giai đoạn xử lý sau:
22 7 Ngoài ra, từ bảng 3.2 ta có thể thấy tỉ lệ phân loại tăng dần từ mức 0 tới mức 2 nhưng từ mức 2 sang mức 3 thì tỉ lệ phân loại bị Trích chọn Ảnh giảm (trừ trường hợp kích thước từ điển M = 16). Như vậy có nghĩa đặc trưng là mức cao nhất của phân cấp L = 3 ảnh được chia nhỏ quá mịn do đó hiệu quả phân loại cơ bản giống với mức phân cấp L = 2. Với kích thước từ điển M = 16, hiệu quả phân loại không tốt bằng M = 100 và M = 200, tuy nhiên tỉ lệ phân loại cũng ở mức chấp nhận. Do kích thước từ điển M = 16 thì các đặc trưng có mật độ cao Phân loại hơn và không gian nhỏ hơn nhiều so với M = 100 và M = 200 nên hiệu suất phân loại tiếp tục cải thiện khi chuyển từ L = 2 sang L = 3. Hình 1.2 Mô hình chung của hệ thống nhận dạng 3.3.2 Nhận dạng khung cảnh cho một ảnh 1.4 Một số ứng dụng của nhận dạng 3.3.2.1 Tập huấn luyện 1.5 Kết luận chương Giống tập huấn luyện như phần xác định khung cảnh cho nhiều Trong chương này chúng ta đã tìm hiểu bài toán nhận dạng ảnh. ảnh, các hướng tiếp cận để giải quyết bài toán. Luận văn của tôi theo hướng tiếp cận so khớp mẫu với trích chọn đặc trưng SIFT kết hợp 3.3.2.2 Tập kiểm tra: kernel phân cấp không gian SPM. Đây được coi là một công cụ Gồm một ảnh cần nhận dạng khung cảnh. mạnh, mềm dẻo, do đó, khả năng ứng dụng của nó là rất lớn. 3.3.2.3 Quy trình thực nghiệm Trong chương tiếp theo, chúng ta sẽ nghiên cứu cơ sở lý Với tập huấn luyện và kiểm tra ta đều tiến hành thực nghiệm thuyết được sử dụng trong luận văn. với kích thước từ điển M =16, M =100, M =200 với lần lượt 4 mức phân cấp L =0, L =1, L =2, L =3. 3.3.1.3 Kết quả thực nghiệm Hình 3.4 và 3.5 dưới đây minh họa cho việc nhận dạng khung cảnh một ảnh:
8 21 Chúng ta cùng tìm hiểu cụ thể file pyramids_all _16_0.mat, Chương 2 - CƠ SỞ LÝ THUYẾT các file còn lại tương tự. File này lưu trữ lược đồ phân cấp đặc trưng 2.1 Trích chọn đặc trưng cục bộ bất biến SIFT của các ảnh trong tập huấn luyện (hoặc tập kiểm tra), là một ma trận kích thước (NxZ) với N là số lượng ảnh trong tập, Z được tính theo Để so sánh hoặc phân loại ảnh, cách tiếp cận thông thường là công thức: Z = , trong đó M là kích thước từ điển, L là biểu diễn ảnh dưới dạng véc tơ đặc trưng bằng cách sử dụng các kỹ mức phân cấp . thuật tạo và trích chọn đặc trưng. Véctơ đặc trưng sau đó được sử dụng làm đầu vào cho các phương pháp phân loại hoặc để tính độ Sau khi tiến hành thực nghiệm tôi thu được kết quả tỉ lệ phân tương tự giữa các ảnh với nhau. Có rất nhiều dạng đặc trưng được đề loại các ảnh đúng tên khung cảnh như sau: xuất và sử dụng trong phân loại ảnh. Trong phạm vi luận văn, tôi chọn sử dụng đặc trưng cục bộ bất biến, viết tắt là SIFT làm đặc trưng biểu diễn ảnh. 2.1.1 Tổng quan về SIFT Phương pháp trích chọn đặc trưng SIFT được tiếp cận theo phương pháp thác lọc, theo đó phương pháp được thực hiện lần lượt theo các bước sau:  Dò tìm cực trị trong không gian đo (Scale space Extrema Detection)  Lọc và trích xuất các điểm đặc biệt (Keypoint Bảng 3.2 Kết quả phân loại. Nội dung các ô là tỷ lệ ảnh được Localization) nhận dạng đúng  Gán hướng cho các điểm đặc trưng (Oriented Từ bảng kết quả 3.2, ta có thể thấy với cả 3 loại kích thước từ Assignment) điển hầu như tỉ lệ phân loại tăng dần từ mức 0 tới mức 3. Ở mức 0  Bộ mô tả điểm đặc trưng (Keypoint Descriptor) tương ứng với mô hình BoF chuẩn thì tỉ lệ phân loại đều nhỏ hơn so với các mức 1, 2, 3. Điều này chứng tỏ so với mô hình BoF chuẩn thì so khớp SPM cho kết quả phân loại tốt hơn.
20 9 Chúng ta cùng tìm hiểu cụ thể file histograms_16.mat, các 2.1.2 Giải thuật SIFT file còn lại tương tự. File này lưu trữ lược đồ đặc trưng của các ảnh 2.1.2.1 Dò tìm cực trị cục bộ trong tập huấn luyện (hoặc tập kiểm tra), là một ma trận kích thước (NxM) với N là số lượng ảnh trong tập, M là kích thước từ điển. 2.1.2.2 Lọc và trích xuất các điểm đặc biệt 2.1.2.3 Gán hướng cho các điểm đặc biệt  File lưu trữ lược đồ phân cấp đặc trưng tương ứng với kích thước từ điển và mức phân cấp, có định dạng: 2.1.2.4 Tạo bộ mô tả cục bộ pyramids_all_sizedictionary_level.mat. Bao gồm: 2.2 So khớp không gian phân cấp (SPM) o pyramids_all_16_0.mat Sau khi đã xác định được đặc trưng, chẳng hạn đặc trưng o pyramids_all_16_1.mat SIFT như mô tả ở trên, ta có thể so sánh hai ảnh với nhau bằng cách o pyramids_all_16_2.mat xác định các đặc trưng SIFT giống nhau giữa hai ảnh. Hai ảnh càng o pyramids_all_16_3.mat có chung nhiều đặc trưng SIFT giống nhau càng được coi là giống o pyramids_all_100_0.mat nhau. Tuy nhiên cách so sánh như vậy không tính tới vị trí tương đối của các vùng giống nhau giữa hai ảnh. Trong phần này, tôi sẽ giới o pyramids_all_100_1.mat thiệu một phương pháp cho phép phần nào sử dụng được các thông o pyramids_all_100_2.mat tin về vị trí tương đối giữa các vùng giống nhau giữa các ảnh. o pyramids_all_100_3.mat Phương pháp có tên Spatial Pyramid Matching, viết tắt là SPM. o pyramids_all_200_0.mat o pyramids_all_200_1.mat 2.2.1 So khớp phân cấp (Partial Matching) o pyramids_all_200_2.mat Sau khi trích chọn đặc trưng thì mỗi ảnh được đại diện bởi o pyramids_all_200_3.mat tập các véc tơ đặc trưng trong không gian d chiều. Như vậy việc so sánh hai ảnh với nhau trở thành việc đánh giá độ tương đồng của hai tập véc tơ đặc trưng. Gọi X, Y là hai tập véc tơ đặc trưng trong không gian d chiều. Grauman và Darrell đã đề xuất phương pháp so khớp phân cấp (viết tắt là PM) để ước lượng độ tương đồng giữa hai tập véc tơ này.
10 19 So khớp phân cấp thực hiện bằng cách thay thế chuỗi các lưới điểm 3.3.1.2 Quy trình thực nghiệm thô tăng dần và thu được tổng số các so khớp tại mỗi độ phân giải Với tập huấn luyện và kiểm tra ta đều tiến hành thực nghiệm (resolution). Tại mỗi độ phân giải bất kỳ, hai điểm được gọi là so với kích thước từ điển M =16, M =100, M = 200 với lần lượt 4 mức khớp nếu chúng rơi vào cùng một vùng con của lưới điểm; các so phân cấp L = 0, L =1, L =2, L = 3. khớp được tìm thấy ở độ phân giải mịn có trọng số cao hơn những so khớp ở độ phân giải thô. 3.3.1.3 Kết quả thực nghiệm Với tập huấn luyện và kiểm tra ta đều thu được các file dữ liệu:  File lưu trữ đặc trưng của các ảnh, có định dạng: dictionary_sizedictionary.mat. Bao gồm: o dictionary_16.mat o dictionary_100.mat o dictionary_200.mat Chúng ta cùng tìm hiểu cụ thể file dictionary_16.mat, các file Hình 2.5 Bên trái: So khớp cục bộ giữa tập các đặc trưng. Bên còn lại tương tự. File này lưu trữ đặc trưng của các ảnh trong tập phải: So khớp phân cấp với đầu vào là hai tập véc tơ đặc trưng. huấn luyện (hoặc tập kiểm tra), là một ma trận kích thước (Nx128) Cụ thể, chúng ta xây dựng một chuỗi lưới điểm tại các độ với N là kích thước từ điển. l phân giải 0, 1, …L; Như vậy lưới điểm ở mức l có 2 vùng con dọc  File lưu trữ lược đồ đặc trưng tương ứng với kích thước theo mỗi chiều, tổng số sẽ có D = 2dl vùng con. Gọi và là từ điển của các ảnh, có định dạng: histogram của X và Y tại lưới điểm này, do đó và (i) là số điểm của tập X và Y rơi vào vùng con thứ i của lưới điểm. Số lượng histograms_sizedictionary.mat. Bao gồm: so khớp tại mức l được cho bởi hàm histogram intersection: o histograms_16.mat o histograms_100.mat (2.8) o histograms_200.mat. Để ngắn gọn, ta sẽ thay bởi .
18 11 Lưu ý: số các so khớp ở mức l cũng bao gồm tất cả các so khớp ở mức l+1. Vì vậy, số các so khớp mới ở mức l là (l = 0, 1, …L-1). Trọng số tương ứng ở tỉ lệ l là nghịch đảo tỉ lệ chiều rộng giữa các vùng con được định nghĩa ở tỉ lệ tương ứng. Trọng số này được dùng để bù cho việc so khớp trên nhiều vùng có tỉ lệ khác nhau bởi đặc trưng cục bộ dễ tìm thấy sự so khớp ở những vùng rộng lớn hơn. Kết hợp lại chúng ta có một định nghĩa nhân so Bảng 3.1 Một số công cụ, thư viện sử dụng trong thực nghiệm khớp phân cấp như sau: Ngoài các công cụ, thư viện trên tôi còn tiến hành xây dựng (X,Y) = + 2 file xử lý dựa trên ngôn ngữ Matlab, cụ thể như sau: = + (2.9)  regMultiImg: kết hợp các module con, nhận dạng khung cảnh cho nhiều ảnh. 2.2.2 So khớp không gian phân cấp (SPM)  regSigImg: kết hợp các module con, nhận dạng khung Một trong những điểm yếu chính của PM đó là bỏ qua thông cảnh cho một ảnh. tin không gian đặc trưng cục bộ trong ảnh. Do đó để khắc phục nhược điểm này Lazebnik và các cộng sự đã đề xuất phương pháp so 3.2.3 Độ đo đánh giá độ chính xác của quá trình thực nghiệm khớp biểu diễn không gian phân cấp, viết tắt là SPM. 3.4 Kết quả thực nghiệm 3.3.1 Nhận dạng khung cảnh cho nhiều ảnh 3.3.1.1 Tập huấn luyện Gồm 8 lớp (coast, forest, highway, mountain, opencountry, insidecity, street, tallbuilding) của cơ sở dữ liệu MIT scenes, mỗi lớp chọn ngẫu nhiên 50 ảnh trong 100 ảnh để làm dữ liệu huấn luyện. 3.3.1.2 Tập kiểm tra: Gồm 50 ảnh còn lại của mỗi lớp kể trên. Hình 2.6 Lược đồ minh họa biểu diễn không gian phân cấp.
12 17 SPM sử dụng một chuỗi các lưới có kích thước khác nhau để thuật toán Kmeans được sử dụng để xây dựng từ điển từ tập các đặc chia ảnh thành các vùng con (subregion) và sau đó sử dụng mô hình trưng SIFT vừa được trích chọn. Trong luận văn tôi tiến hành thực túi đặc trưng, viết tắt là BoF để thống kê tổng hợp đặc trưng cục bộ nghiệm với 3 kích thước khác nhau của từ điển M = 16, M = 100 và trên các vùng con cố định thay vì sử dụng trên toàn ảnh như trong mô M = 200. hình BoF cổ điển, cuối cùng tập hợp các mô hình BoF trên các vùng Thực nghiệm tiến hành với các ảnh trong cơ sở dữ liệu MIT con được nối lại theo thứ tự được định nghĩa trước để mô hình cho scene 8 lớp , tại địa chỉ: ảnh. http://people.csail.mit.edu/torralba/code/spatialenvelope/spatial_enve Hình 2.7 dưới đây minh họa việc xây dựng phân cấp 3 mức lope_256x256_static_8outdoorcategories.zip. cho một ảnh. Giả sử ảnh có 3 loại đặc trưng kí hiệu là hình tròn, hình Mỗi lớp tôi chọn 100 ảnh, lấy ngẫu nhiên 50 ảnh là tập huấn thoi và hình chữ thập. Đầu tiên, ta chia ảnh thành 3 mức độ phân giải luyện, số còn lại dùng làm tập kiểm tra. khác nhau (level 0, level 1, level 2). Tiếp theo với mỗi mức độ phân giải và mỗi loại đặc trưng ta đếm số lượng đặc trưng rơi vào vùng Tất cả các thực nghiệm đều được thực hiện 10 lần với việc con. Cuối cùng, ta tính toán trọng số cho mỗi lược đồ phân cấp dựa lựa chọn ngẫu nhiên tập huấn luyện và tập kiểm tra, tỉ lệ phân loại theo công thức (2.9) được lưu sau mỗi lần chạy chương trình. Kết quả phân loại cuối cùng được tính là tỉ lệ phân loại trung bình sau 10 lần chạy riêng biệt. Việc phân loại khung cảnh trong chương trình sử dụng phương pháp học máy SVM với phân loại đa lớp, áp dụng chiến lược “một với tất cả” (one – versus – all). 3.2.2 Công cụ phần mềm sử dụng Hình 2.7 Ví dụ xây dựng phân cấp 3 mức.
16 13 2.3 Phương pháp học máy véc tơ hỗ trợ SVM Chương 3 - KẾT HỢP SPM VÀ SVM ĐỂ NHẬN DẠNG SVM là một họ các phương pháp dựa trên cơ sở các hàm nhân (kernel) để tối thiếu hóa rủi ro cấu trúc. Phương pháp SVM ra Dựa vào cơ sở lý thuyết đã trình bày, luận đời từ lý thuyết học thống kê do Vapnik và Chervonenkis xây dựng. văn tiến hành áp dụng phương pháp so khớp spatial SVM sử dụng thuật toán học nhằm xây dựng một siêu phẳng làm cực pyramid với trích chọn đặc trưng SIFT kết hợp SVM tiểu hóa độ phân lớp sai của một đối tượng dữ liệu mới. Độ phân lớp để nhận dạng khung cảnh tự nhiên. sai của một siêu phẳng được đặc trưng bởi khoảng cách bé nhất tới 3.1 Các khối xử lý chính siêu phẳng đó. Đặc trưng cơ bản quyết định khả năng phân lớp là khả năng phân lớp những dữ liệu mới dựa vào những tri thức đã tích lũy được trong quá trình huấn luyện. Sau quá trình huấn luyện nếu hiệu suất tổng quát hóa của bộ phân lớp cao thì thuật toán huấn luyện được đánh giá là tốt. Hiệu suất tổng quát hóa phụ thuộc vào hai tham số là sai số huấn luyện và năng lực của máy học. Trong đó sai số huấn luyện là tỉ lệ lỗi phân lớp trên tập dữ liệu huấn luyện. Còn năng lực của máy học được xác định bằng kích thước Vapnik – Chervonenkis (kích thước VC). Đại lượng này được xác định bằng số điểm cực đại Hình 3.1 Các khối xử lý chính trong bài toán nhận dạng khung mà họ hàm có thể phân tách hoàn toàn trong không gian đối tượng. cảnh tự nhiên Một tập phân lớp tốt là tập phân lớp có năng lực thấp nhất (có nghĩa là đơn giản nhất) và đảm bảo sai số huấn luyện nhỏ. Phương pháp 3.2 Thiết lập tham số và các công cụ sử dụng cho thực SVM được xây dựng trên ý tưởng này. nghiệm 3.2.1 Thiết lập tham số và xây dựng tập dữ liệu ảnh Trong luận văn tôi sử dụng SIFT với mật độ dày (dense SIFT) bằng cách sử dụng bộ mô tả SIFT trên vùng chữ nhật kích thước 16x16 pixel trên một lưới điểm khoảng cách 8 pixel. Sau đó,
14 15 2.3.1 Phân lớp tuyến tính 2.3.3.2 Một số hàm kernel cơ bản 2.3.2 Vấn đề lề mềm và kernel 2.3.4 SVM cho bài toán đa lớp 2.3.3 Hàm Kernel 2.3.3.1 Giới thiệu về kernel Trong trường hợp dữ liệu không thể phân chia tuyến tính, cách tiếp cận sử dụng SVM là ánh xạ các véc tơ trong không gian gốc sang một không gian mới, thường là có số chiều lớn hơn. Vấn đề là việc tính toán các ánh xạ này có thể có độ phức tạp tính toán lớn. Để tránh việc tính toán các ánh xạ, một kỹ thuật được sử dụng là dùng các hàm nhân. Hàm nhân cho phép tính tích vô hướng giữa hai véc tơ trong không gian mới mà không cần biết ánh xạ thực của các véc tơ trong không gian đó. Hình 2.11 Sử dụng Kernel để áp dụng phân loại trên không gian đặc trưng