Tài liệu Luận văn cntt nghiên cứu mô hình học từ điển thưa ứng dụng trong nhận dạng ảnh thóc giống

. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ LAN ANH NGHIÊN CỨU MÔ HÌNH HỌC TỪ ĐIỂN THƯA ỨNG DỤNG TRONG NHẬN DẠNG THÓC GIỐNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2018 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ LAN ANH NGHIÊN CỨU MÔ HÌNH HỌC TỪ ĐIỂN THƯA ỨNG DỤNG TRONG NHẬN DẠNG THÓC GIỐNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Cán bộ hướng dẫn: PGS. TS. Nguyễn Thị Thủy Cán bộ đồng hướng dẫn: PGS. TS. Lê Thanh Hà HÀ NỘI, 2018 LỜI CAM ĐOAN Tôi xin cam đoan các kết quả nghiên cứu, thực nghiệm được trình bày trong luận văn này do tôi thực hiện dưới sự hướng dẫn của Phó giáo sư - Tiến sĩ Nguyễn Thị Thuỷ và Phó giáo sư - Tiến sĩ Lê Thanh Hà. Tất cả những tham khảo từ các nghiên cứu liên quan đều được nêu nguồn gốc một cách rõ ràng từ danh mục tài liệu tham khảo của luận văn. Trong luận văn, không có việc sao chép tài liệu, công trình nghiên cứu của người khác mà không chỉ rõ về tài liệu tham khảo. TÁC GIẢ LUẬN VĂN Phạm Thị Lan Anh LỜI CẢM ƠN Trước tiên, tôi xin gửi lời cảm ơn sâu sắc nhất đến cô giáo: Phó giáo sư - Tiến sĩ Nguyễn Thị Thuỷ và thầy giáo: Phó giáo sư - Tiến sĩ Lê Thanh Hà, đã tận tình hướng dẫn tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Cảm ơn thầy giáo - Tiến sĩ Trần Quốc Long đã có những góp ý, nhận xét quý giá giúp hoàn thiện nội dung nghiên cứu của tôi trong luận văn này. Tôi xin bày tỏ lời cảm ơn chân thành tới trường Đại học Công Nghệ - ĐHQG Hà Nội và những thầy cô giáo đã giảng dạy, truyền thụ kiến thức cho tôi trong thời gian qua cùng với sự quan tâm và động viên khích lệ tinh thần của các thành viên của phòng thí nghiệm Tương tác người máy HMI – Đại học Công nghệ, Đại học Quốc Gia Hà Nội. Tôi cũng cảm ơn các đồng nghiệp của Khoa Công nghệ thông tin, đặc biệt là Bộ môn Khoa học máy tính – Học viện Nông nghiệp Việt Nam đã luôn tạo điều kiện và hỗ trợ tốt nhất để tôi tập trung hoàn thành việc học cao học và bảo vệ luận văn thạc sĩ. Cuối cùng, tôi xin cảm ơn tất cả gia đình, bạn bè đã luôn động viên giúp đỡ tôi trong thời gian nghiên cứu đề tài. Tuy đã có những cố gắng nhất định nhưng do thời gian và trình độ có hạn nên luận văn còn nhiều thiếu sót và hạn chế. Kính mong nhận được sự góp ý của quý thầy cô và các bạn. TÁC GIẢ LUẬN VĂN Phạm Thị Lan Anh MỤC LỤC Lời cam đoan ................................................................................................................. iii Lời cảm ơn ......................................................................................................................iv Mục lục ............................................................................................................................v Danh mục ký hiệu và chữ viết tắt ....................................................................................1 Danh mục hình vẽ ............................................................................................................2 Danh mục bảng biểu ........................................................................................................3 Giới thiệu .........................................................................................................................4 Chương 1. Mô hình học từ điển và mã thưa ..............................................................6 1.1. Biểu diễn thưa và học từ điển ............................................................................6 1.1.1. Biểu diễn thưa ..........................................................................................6 1.1.2. Học từ điển...............................................................................................8 1.1.3. Mô hình học từ điển và mã thưa ..............................................................9 1.2. Xây dựng mô hình học từ điển và mã thưa ......................................................10 1.2.1. Giới thiệu họ các chuẩn .........................................................................10 1.2.2. Xác định mã thưa và xây dựng từ điển học ...........................................15 1.3. Một số mô hình học từ điển ứng dụng cho phân lớp .......................................18 1.3.1. Mô hình học từ điển có đảm bảo tính thưa ............................................19 1.3.2. Mô hình học từ điển không cần đảm bảo tính thưa ...............................21 Chương 2. Bài toán nhận dạng ảnh và ứng dụng.....................................................24 2.1. Tổng quan về bài toán nhận dạng ....................................................................24 2.1.1. Giới thiệu thị giác máy tính ...................................................................24 2.1.2. động Bài toán nhận dạng ảnh và quy trình thực hiện của hệ nhận dạng ảnh tự ...............................................................................................................26 2.2. Ứng dụng của nhận dạng ảnh...........................................................................29 Chương 3. Cài đặt và kết quả thực nghiệm .............................................................32 3.1. Mô tả bài toán ..................................................................................................33 3.1.1. Dữ liệu ...................................................................................................34 3.1.2. Cài đặt ....................................................................................................36 3.2. Kết quả đạt được ..............................................................................................37 3.3. Thảo luận về ảnh hưởng của ràng buộc thưa vào kết quả nhận dạng ..............43 Chương 4. Kết luận và hướng phát triển ......................................................................45 Tài liệu tham khảo .........................................................................................................46 Phụ lục ...........................................................................................................................49 1 DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT CS Compressed Sensing DPL Dictionary Pair Learning K-SVD K-means Singular Value Decomposition LC-KSVD Label Consistent K-means Singular Value Decomposition MP Matching Pursuit NSL Nyquist Sampling Law OMP Orthogonal Matching Pursuit RF Random Forest SAD Sum of Absolute Difference SSD Sum of Squared Difference SST Shannon’ Sampling Theorem SVM Support Véc-tơ Machine 2 DANH MỤC HÌNH VẼ Hình 1.1. Mẫu ảnh đa mức xám và biểu diễn dày ........................................................... 7 Hình 1.2. Ảnh đa mức xám với biểu diễn thưa ............................................................... 8 Hình 1.3. Mô tả giải pháp tối thiểu hóa của một số chuẩn trong không gian 2-D ........ 14 Hình 2.1. Một số ví dụ về các thuật toán thị giác máy .................................................. 26 Hình 2.2. Một số ví dụ về ứng dụng của nhận dạng mẫu ảnh ....................................... 27 Hình 2.3.Quy trình thực hiện của hệ nhận dạng ảnh tự động ........................................ 28 Hình 3.1.Ảnh từng hạt thóc của các giống thóc khác nhau sẽ trở thành dữ liệu mẫu cho việc học các mô hình ..................................................................................................... 34 Hình 3.2.Biểu đồ thể hiện hiệu suất của mô hình LC-KSVD và DPL .......................... 39 Hình 3.3.Biểu đồ so sánh tổng thời gian học và kiểm tra mô hình của LC-KSVD1, LCKSVD2, DPL ................................................................................................................. 41 Hình 3.4.Biểu đồ tổng hợp kết quả phân loại của mô hình học từ điển, SVM và RF... 43 Hình phụ lục 1.Sơ đồ quá trình nhận dạng biển số xe ................................................... 49 Hình phụ lục 2.Ảnh biển số xe sau khi được thu nhận và phân tách. ........................... 50 Hình phụ lục 3.Hiệu suất phân lớp của mô hình LC-KSVD và DPL ........................... 54 Hình phụ lục 4.Thời gian học và kiểm tra mô hình của LC-KSVD 1, LC-KSVD 2, DPL ................................................................................................................................ 55 3 DANH MỤC BẢNG BIỂU Bảng 3.1.Thống kê số lượng dữ liệu ảnh của từng giống thóc...................................... 35 Bảng 3.2.Kết quả khi thay đổi tham số sparsitythres của giống Bắc thơm 7 ................ 36 Bảng 3.3.Kết quả khi thay đổi tham số DictSize của giống thóc Bắc thơm 7 .............. 37 Bảng 3.4.Kết quả phân lớp của LC-KSVD1, LC-KSVD2 và DPL .............................. 38 Bảng 3.5.Thời gian học mô hình và kiểm tra của LC-KSVD và DPL .......................... 40 Bảng phụ lục 1.Số lượng biển số xe thu nhận được ...................................................... 50 Bảng phụ lục 2.Số lượng từng ký tự được tách ra từ biển số xe ................................... 51 Bảng phụ lục 3.Số lượng mẫu của bài toán nhận dạng 10 ký tự ................................... 52 Bảng phụ lục 4.Số lượng mẫu của bài toán nhận dạng 14 ký tự ................................... 52 Bảng phụ lục 5.Số lượng mẫu của bài toán nhận dạng mẫu ......................................... 53 Bảng phụ lục 6.Hiệu suất phân lớp của LC-KSVD 1, LC-KSVD 2 và DPL ................ 54 Bảng phụ lục 7.Thời gian học và kiểm tra mô hình của LC-KSVD 1, LC-KSVD 2, DPL ................................................................................................................................ 54 4 GIỚI THIỆU Phương pháp biểu diễn thưa (Sparse represetation) là một phương pháp đại diện tiêu biểu cho phương pháp biểu diễn tuyến tính [5] và đã được chứng minh là giải pháp mạnh mẽ cho nhiều lĩnh vực ứng dụng, đặc biệt là xử lý tín hiệu, xử lý hình ảnh, học máy, thị giác máy tính. Biểu diễn thưa cho thấy tiềm năng phát triển cho nhiều bài toán về ảnh như khử nhiễu ảnh, nén ảnh, khôi phục ảnh, phân loại hình ảnh, phân vùng hình ảnh. Sự kết hợp giữa phương pháp biểu diễn thưa dựa trên một bộ từ điển (Dictionary learning) được học từ chính tín hiệu mẫu ban đầu đã giúp cho mô hình học từ điển thưa (Dictionary learning and sparse coding) trở thành một trong những mô hình mạnh để biểu diễn tín hiệu được ưa chuộng từ khi bắt đầu hình thành cho đến ngày nay. Ban đầu, mô hình chỉ quan tâm đến lớp bài toán biểu diễn lại tín hiệu một cách thưa thớt nhất nhưng cũng phải đảm bảo khả năng khôi phục là tốt nhất. Trong những năm gần đây, với sự phát triển của khoa học kỹ thuật cũng như những đòi hỏi từ ứng dụng thực tế, các nhà nghiên cứu về mô hình học từ điển thưa đã cải tiến mô hình cổ điển thành những mô hình có tính cạnh tranh trong việc giải quyết những bài toán phân loại/nhận dạng, đặc biệt là phân loại/nhận dạng ảnh số. Trong luận văn này, tôi tìm hiểu về lý thuyết biểu diễn thưa và những phương pháp cơ bản để xây dựng một mô hình học từ điển thưa đồng thời cũng trình bày hai hướng phát triển chính của mô hình học từ điển: mô hình học từ điển đảm bảo tính thưa và mô hình học từ điển không cần đảm bảo tính thưa. Sau đó, tôi triển khai cài đặt hai mô hình đại diện cho hai hướng là mô hình học từ điển với nhãn phù hợp (LC-KSVD) – tiêu biểu cho mô hình học từ điển đảm bảo thưa và mô hình cặp từ điển (DPL) – tiêu biểu cho mô hình học từ điển không đảm bảo thưa trên bộ dữ liệu ảnh thóc giống được thu nhận từ thực tế Việt Nam. Việc áp dụng các mô hình học từ điển trên bộ dữ liệu ký tự biển số xe (được trình bày trong phần Phụ lục của luận văn này) nhằm mục đích đánh giá sơ bộ khả năng ứng dụng của các mô hình với bài toán nhận dạng ảnh để làm tiền đề cho bài toán nhận dạng thóc giống. Ngoài ra, việc áp dụng các mô hình trên hai bộ dữ liệu khác nhau với những đặc điểm, khó khăn khác nhau sẽ giúp tôi có sự đánh giá khách quan hơn đối với mô hình học từ điển đảm bảo thưa và không đảm bảo thưa. Từ đó đưa ra những nhận xét về hai dạng mô hình học từ điển cũng như đề xuất hướng ứng dụng của mô hình học từ điển thưa. Ngoài phần giới thiệu và tài liệu tham khảo, luận văn này gồm 4 chương với các nội dung chính sau đây: 5  Chương 1 trình bày về mô hình học từ điển và mã thưa với mô tả chi tiết về cách xây dựng mô hình học từ điển và tìm biểu diễn thưa tương ứng. Đồng thời, tôi cũng đề cập tới một xu hướng phát triển mới của mô hình học từ điển áp dụng cho bài toán phân lớp/nhận dạng đó là xây dựng mô hình học từ điển không cần đảm bảo tính thưa.  Chương 2 là tổng quan về bài toán nhận dạng mẫu ảnh. Trong chương này, tôi sẽ trình bày một số nghiên cứu có liên quan đến lĩnh vực của luận án bao gồm lý thuyết về thị giác máy tính, bài toán nhận dạng đối tượng nói chung và nhận dạng ảnh nói riêng cũng như nêu lên một số ứng dụng của nhận dạng mẫu ảnh.  Chương 3 mô tả chi tiết quá trình thực nghiệm cài đặt các mô hình học từ điển với bộ dữ liệu ảnh thóc giống và đưa ra kết quả tính toán cho thời gian chạy cũng như hiệu suất phân loại của từng mô hình. Qua đó đưa ra một số nhận xét đối với các mô hình.  Chương 4 trình bày kết luận và hướng phát triển trong tương lai.  Ngoài các chương chính, luận văn còn trình bày thêm phần Phụ lục: mô tả chi tiết quá trình thực nghiệm cài đặt các mô hình học từ điển trên bộ dữ liệu ảnh ký tự biển số xe để làm cơ sở lý luận cho việc so sánh tính hiệu quả của hai mô hình tiêu biểu cho hai hướng xây dựng mô hình học từ điển. 6 CHƯƠNG 1. MÔ HÌNH HỌC TỪ ĐIỂN VÀ MÃ THƯA Con người chúng ta ghi nhớ về một hiện tượng, sự vật; cách chúng ta phân biệt các hiện tượng, sự vật khác nhau không hề đầy đủ các tín hiệu về hiện tượng, sự vật đó mà chỉ qua một vài tín hiệu nhất định. Chúng ta phát hiện ra một bản nhạc có thể chỉ bằng vài nốt nhạc đầu tiên hay nhận ra khuôn mặt của ai đó sau nhiều năm không gặp chỉ thông qua vị trí nốt ruồi gần mắt. Đây chính là tiền đề cho một phương pháp biểu diễn tín hiệu được gọi là biểu diễn thưa. Ban đầu mục đích cho việc biểu diễn thưa chỉ dừng lại ở việc biểu diễn tín hiệu một cách cô đọng, giảm không gian lưu trữ tín hiệu mà không làm mất mát thông tin có giá trị. Trong những năm gần đây, biểu diễn thưa cho một tín hiệu đầu vào đã được đông đảo các nhà nghiên cứu tham gia tìm hiểu và phát triển thêm những tính chất phù hợp hơn với các bài toán thực tế đa dạng. Với ý tưởng thực hiện biểu diễn thưa cho tín hiệu ban đầu dựa trên bộ các thành phần (atoms) được tạo nên từ chính tập tín hiệu đã có sẵn, mô hình học từ điển thưa trở thành một mô hình mạnh trong việc biểu diễn tín hiệu và mở rộng ra cho việc loại bỏ nhiễu, nén, phân loại tín hiệu [4,43]. Bởi thế, mô hình học từ điển thưa đáng được quan tâm và phát triển cũng như ứng dụng vào nhiều hơn nữa các bài toán thực tế đầy thách thức. Chương này của luận văn sẽ trình bày cụ thể về mô hình học từ điển cổ điển cũng như cách để xác định từ điển và hệ số biểu diễn thưa (mã thưa). Ngoài ra, luận văn cũng trình bày một hướng phát triển khác của mô hình học từ điển ứng dụng cho phân lớp là mô hình học từ điển không cần đảm bảo tính thưa (tức yếu tố ràng buộc đối với hệ số biểu diễn thưa đã không còn được chú trọng). 1.1. Biểu diễn thưa và học từ điển 1.1.1. Biểu diễn thưa Trong thế giới số, mọi tín hiệu đều được biểu diễn dưới dạng số và việc biểu diễn này có hiệu quả hay không sẽ ảnh hưởng đến các phép xử lý tiếp theo trong đó có truyền gửi và lưu trữ. Vì vậy, các nhà nghiên cứu luôn mong muốn việc biểu diễn tín hiệu trong thế giới số gần nhất có thể với tín hiệu thế giới thực nhưng có thể truyền đưa và lưu trữ ngắn gọn dẫn tới tín hiệu thường không được biễu diễn trùng khớp hoàn toàn mà sẽ được biểu diễn thông qua các đặc trưng đủ để phân biệt tín hiệu này với tín hiệu khác giúp quá 7 trình truyền đưa và lưu trữ bớt tốn kém cũng như tăng tốc độ của việc xử lý tín hiệu sau đó. Ý tưởng này hình thành nên một phương pháp biểu diễn tuyến tính gọi là biểu diễn thưa. Về mặt nguồn gốc lý thuyết, biểu diễn thưa có liên quan đến lý thuyết cảm biến nén (Compressed Sensing – CS) [43]. Theo lý thuyết CS thì những tín hiệu thưa hoặc được nén thì tín hiệu ban đầu có thể được khôi phục bằng cách triển khai một vài giá trị đo được trong khi số lượng những giá trị này ít hơn nhiều so với cách lấy mẫu của Shannon (Shannon’sampling theorem - SST) và luật lấy mẫu Nyquist (Nyquist sampling law - NSL). Các thành tố cơ bản trong lý thuyết CS bao gồm biểu diễn thưa, mã hóa và thuật toán khôi phục. Mục đích của biểu diễn thưa là đưa không gian biểu diễn tín hiệu ban đầu sang không gian nhiều chiều hơn giúp những thành phần đặc trưng của tín hiệu “nổi lên” rõ ràng hơn so với “bề mặt”, sau đó tín hiệu sẽ được “ghi nhớ” thông qua những thành phần đặc trưng này thay vì toàn bộ các thành phần như lúc ban đầu để đưa vào các quá trình xử lý tiếp theo. Mỗi ảnh số là một ảnh tự nhiên được số hóa dưới dạng ma trận số. Với ảnh màu ta sẽ có 3 ma trận số tương ứng với các kênh màu tùy thuộc vào hệ màu biểu diễn khác nhau và thông thường các ma trận biểu diễn này là ma trận “dày” với hầu hết các giá trị trong đó khác không [1]. Hình 1.1 biểu diễn một mẫu ảnh đa mức xám kích thước 14x14. Hình 1.1. Mẫu ảnh đa mức xám và biểu diễn dày Ta hoàn toàn có thể biểu diễn mẫu ảnh này bằng một vec-tơ có 14x14 = 156 chiều, tuy nhiên cách biểu diễn này sẽ dễ bị tác động bởi nhiễu và “cồng kềnh” khi phải truyền gửi và lưu trữ. Khi áp dụng biểu diễn thưa vào, mặc dù sẽ đẩy số chiều vecto biểu diễn cho ảnh lên cao hơn nhưng số lượng giá trị thực tế cần “ghi nhớ” lại rất ít do hầu hết thành phần của vec-tơ mang giá trị không. Vì vậy, việc biểu diễn hầu như chỉ liên quan đến một vài thành phần có giá trị khác không. Ví dụ mẫu ảnh có thể được biểu diễn bằng mô hình thưa như trong hình 1.2. 8 Hình 1.2. Ảnh đa mức xám với biểu diễn thưa Khi đó, để lưu trữ và xử lý mẫu ảnh đã cho ta có thể sử dụng vec-tơ hệ số biểu diễn X sau: [a1,...,a64] = [0,0,...,0.8,0,...,0,0.3,0,...,0.5,...,0]. Trong ví dụ này, vec-tơ hệ số được dùng để đại diện cho mẫu ảnh chỉ có ba thành phần có giá trị khác không, số lượng thành phần có giá trị khác không này sẽ đóng vai trò là ngưỡng đảm bảo thưa cho mô hình biểu diễn. Ngưỡng đảm bảo thưa này không có quy định rõ ràng về giá trị mà chỉ được lựa chọn tùy thuộc vào bài toán và dữ liệu cụ thể của bài toán đó. 1.1.2. Học từ điển Trong ngôn ngữ học, bộ từ điển được hình thành bao gồm tất cả các từ đơn, từ ghép, từ láy,... đủ để giúp diễn đạt mọi câu nói, viết trong ngữ pháp của ngôn ngữ đó. Trong học máy cũng có một mô hình có tên gọi tương tự đó là học từ điển. Với góc nhìn của toán học, nếu coi từ điển là một ma trận vecto trong đó mỗi thành tố hay từ là một vecto thì từ điển trong mô hình học từ điển giống như một hệ sinh vecto mà tại đó các thành tố hay các từ không đảm bảo độc lập tuyến tính với nhau. Việc xác định từ điển sẽ được học từ chính những tín hiệu đầu vào và quá trình sinh là quá trình biểu diễn lại đối tượng bằng tập hợp các từ trong từ điển sao cho việc biểu diễn chính xác tín hiệu đầu vào hoặc gần “giống” tín hiệu đó. Mô hình học từ điển có thể có lịch sử hình thành từ những năm 1960 với sự ra đời của biến đổi nhanh Fourier (FFT). Ban đầu từ điển được tạo ra bằng các biến đổi miền của tín hiệu như biến đổi bước sóng, biến đổi wavelet [39],… Tuy nhiên những biến đổi đó không thực sự đem lại hiệu quả, thay vào đó, phương pháp học từ điển biểu diễn thưa lại đem lại những kết quả thuyết phục hơn. Khi từ điển có số từ nhiều hơn số chiều (tính 9 over-complete) thì có thể dẫn tới một biểu diễn thưa và khi đó ta có mô hình học từ điển thưa. Mô hình học từ điển, với ý nghĩa ban đầu dùng để biểu diễn tín hiệu (representation) [25], được ứng dụng cho các bài toán khôi phục dữ liệu (reconstruction) [18] , khử nhiễu [8,20] và mã hóa thưa (sparse coding), gần đây được mở rộng cho bài toán phân lớp (classification) [9,21,29,30,34]. 1.1.3. Mô hình học từ điển và mã thưa Cho 𝑦1 , 𝑦2 , ..., 𝑦𝑛 ∈ 𝑅𝑝 là tất cả n mẫu tín hiệu và Y ∈ 𝑅𝑝∗𝑁 là ma trận tín hiệu đầu vào với N tín hiệu đầu vào mà mỗi tín hiệu 𝑦𝑖 ∈ 𝑅𝑝 tương ứng với một cột của ma trận Y. Từ n mẫu tín hiệu xác định một ma trận D ∈ 𝑅𝑝∗𝐾 (p ≪ K) được gọi là từ điển cơ bản quá hoàn chỉnh (tính overcomplete) mà mỗi từ 𝑑𝑗 ∈ 𝑅𝑝 . Một mẫu mới cần biểu diễn 𝑦𝑛𝑒𝑤 ∈ 𝑅𝑝 . Nếu tất cả các mẫu đã biết được sử dụng để biểu diễn tuyến tính cho mẫu mới thì mẫu mới phải được biểu diễn bằng: 𝑦𝑛𝑒𝑤 = 𝑥𝑛𝑒𝑤_1 𝑑1 + 𝑥𝑛𝑒𝑤_2 𝑑2 + ⋯ + 𝑥𝑛𝑒𝑤𝑛 𝑑𝑛 (1) X ∈ 𝑅𝐾∗𝑁 là ma trận hệ số với 𝑥𝑖 là hệ số tương ứng biểu diễn tín hiệu 𝑦𝑖 và phương trình (1) có thể được viết lại bởi phương trình sau: 𝑦𝑛𝑒𝑤 = 𝐷 ∗ 𝑥𝑛𝑒𝑤 (2) Khi đó, mô hình bài toán học từ điển thưa được thể hiện qua biểu thức (3) sau: 2 argmin‖𝑌 − 𝐷𝑋 ‖22 𝑠𝑎𝑜 𝑐ℎ𝑜 ‖𝑥𝑖 ‖0 ≤ T và ‖𝑑𝑗 ‖2 = 1 (3) 𝐷 Trong đó, ‖. ‖0 là chuẩn 𝑙0 nhận giá trị số lượng phần tử khác không của vec-tơ. T là giá trị ngưỡng thưa được lựa chọn trước. Việc giải bài toán tối ưu (3) sẽ dẫn tới xác định được một phương pháp biểu diễn mới cho bộ tín hiệu đầu vào Y với không gian biểu diễn lớn hơn và có khả năng khôi phục lại tín hiệu Y thông qua từ điển D và hệ số biểu diễn X. Quá trình học ra từ điển D và X từ chính dữ liệu ban đầu giúp cho việc biểu diễn lại dữ liệu ban đầu là hiệu quả. Quá trình này bao gồm hai nhiệm vụ: tìm D và xác định X. Việc tìm từ điển D sẽ được gọi là cập nhật từ điển và việc xác định X được gọi là xác 10 định mã thưa. Thông thường ta sẽ cố định X trong khi cập nhật từ điển và khi xác định mã thưa thì từ điển D sẽ được cố định. Vấn đề tìm lời giải cho phương trình tuyến tính (2) với quan điểm đại số tuyến tính, nếu không có bất kỳ ràng buộc nào được áp đặt đối với hệ số biểu diễn x thì phương trình (2) sẽ không có lời giải duy nhất. Với việc coi từ điển như một hệ sinh vec-tơ, với tính chất số chiều nhỏ hơn nhiều so với số từ (p ≪ K), theo lý thuyết hình học không gian, ta có vô số lời giải cho biểu diễn vec-tơ. Để giảm bớt khó khăn, các ràng buộc chuẩn hóa thích hợp được áp dụng cho hệ số biểu diễn [19]. Với phương pháp biểu diễn thưa thì yêu cầu đặt ra là giải pháp biểu diễn thu được phải thưa thớt. Ràng buộc theo chuẩn 𝑙0 giúp cho bài toán có nghiệm đảm bảo tính chất thưa cho véc-tơ hệ số tìm được. Ta cũng có thể thay thế chuẩn 𝑙0 bằng chuẩn 𝑙1 để đảm bảo tính thưa cho mô hình học từ điển, tuy nhiên nếu sử dụng chuẩn 𝑙2 thì tính thưa sẽ không được bảo đảm. Ngoài ra mối tương quan giữa bộ hệ số 𝑥𝑖 với việc biểu diễn các tín hiệu đầu vào của cùng một đối tượng nào đó đã gợi ý về việc sử dụng mô hình này vào trong bài toán phân lớp, đặc biệt là nhận dạng đối tượng. 1.2. Xây dựng mô hình học từ điển và mã thưa Việc xây dựng mô hình học từ điển thưa cần đảm bảo hai yếu tố cơ bản: từ điển học được tạo ra từ chính dữ liệu mẫu ban đầu và hệ số biểu diễn đảm bảo ràng buộc thưa. Có nhiều phương pháp để giải quyết các yêu cầu đặt ra đối với việc xây dựng mô hình [7]. Luận văn này sẽ giới thiệu một số phương pháp cổ điển và đặc biệt trình bày về giải thuật K-SVD trong quá trình xác định mã thưa và cập nhật từ điển. 1.2.1. Giới thiệu họ các chuẩn Trước hết, để làm rõ hơn việc sử dụng điều kiện ràng buộc thưa dựa trên các chuẩn 𝑙0 hay 𝑙1 của mô hình học từ điển cũng như vì sao khi áp dụng chuẩn 𝑙2 vào việc tìm hệ số biểu diễn thì hệ số sẽ không được đảm bảo tính thưa thì phần này sẽ trình bày về họ các chuẩn [1,43] thông thường. Về mặt toán học, một chuẩn là tổng kích thước hoặc chiều dài của tất cả các véc-tơ trong một không gian véc-tơ hoặc ma trận nào đó, khi đó, chuẩn càng cao thì (độ lớn) ma trận hay véc-tơ càng lớn. Chuẩn có thể có nhiều hình thức và nhiều tên gọi khác nhau như khoảng cách Euclide, sai số bình phương trung bình – phương sai của ước lượng (Mean Squared Error)... Ký hiệu ‖𝑥 ‖với x có thể là véc-tơ hoặc ma trận. 11 Ví dụ, một chuẩn Euclide của một véc-tơ x: 3 x= [−2] là ‖𝑥‖2 = √32 + (−2)2 + 12 = 3.742 là kích thước của x 1 Ví dụ trên cho thấy làm thế nào để tính ra một chuẩn Euclide, hay chính thức gọi là một chuẩn 𝑙2 . Công thức (4) xác định một chuẩn 𝑙𝑝 của x: 𝑝 ‖𝑥‖𝑝 = √∑𝑖|𝑥𝑖 |𝑝 với p ∈ 𝑅 (4) Mặc dù mọi chuẩn đều trông rất giống nhau về mặt công thức tổng quát nhưng tính toán của chúng rất khác nhau và do đó ứng dụng của chúng cũng khác nhau rất nhiều.  Chuẩn 𝑙0 Chuẩn 𝑙0 của x được xác định bởi (5): ‖𝑥‖0 = 0√∑𝑖|𝑥𝑖 |0 (5) Nói đúng ra, chuẩn 𝑙0 không chính xác là một chuẩn. Đó là một trường hợp đặc biệt trong định nghĩa hình thức chuẩn 𝑙p . Xác định chuẩn 𝑙0 có chút khó khăn vì việc tính toán 0 giai thừa và căn bậc 0 của một số x bởi định nghĩa về giai thừa 0 và đặc biệt là căn bậc 0 của một số là không rõ ràng và thường phải có quy ước trước để tuân thủ. Vì vậy, trong thực tế, hầu hết các nhà toán học và kỹ sư xác định chuẩn 𝑙0 bằng công thức: ‖𝑥‖0 = (𝑖|𝑥𝑖 ≠ 0). Đó là số các phần tử khác 0 trong một véc-tơ và là một số nguyên khác không. Chuẩn 𝑙0 có rất nhiều ứng dụng và gần đây nó được quan tâm nhiều hơn do sự phát triển của các bài toán liên quan đến khôi phục dữ liệu sau nén thông qua việc cố gắng tìm ra giải pháp thưa thớt của hệ thống biểu diễn tuyến tính. Giải pháp thưa thớt nhất là giải pháp có chuẩn 𝑙0 nhỏ nhất. Vấn đề này thường liên quan đến vấn đề tối ưu hoá chuẩn theo 𝑙0 . 12  Chuẩn 𝑙1 Theo định nghĩa về chuẩn, chuẩn 𝑙1 của x được xác định bởi (6): ‖𝑥‖1 = 1√∑𝑖|𝑥𝑖 |1 (6) Tiêu chuẩn này khá phổ biến trong họ các chuẩn. Nó có nhiều tên và nhiều hình thức trong các lĩnh vực khác nhau. Nếu chuẩn 𝑙1 được tính cho sự khác biệt giữa hai vectơ hoặc ma trận, thì chuẩn 𝑙1 được gọi là Sum of Absolute Difference (SAD) và được xác định bởi công thức (7): SAD (𝑥1 , 𝑥2 ) = ‖𝑥1 − 𝑥2 ‖1 = ∑𝑖|𝑥1𝑖 − 𝑥2𝑖 |1 (7) Trong trường hợp tổng quát về phép đo sai lệch tín hiệu, chuẩn 𝑙1 có thể đóng vai trò như lỗi trung bình tuyệt đối (MAE) trong công thức (8): 1 1 𝑛 𝑛 MAE(𝑥1 , 𝑥2 ) = ‖𝑥1 − 𝑥2 ‖1 = ∑|𝑥1𝑖 − 𝑥2𝑖 | với n là kích thước của x. (8)  Chuẩn 𝑙2 Phổ biến nhất của tất cả các tiêu chuẩn là chuẩn 𝑙2 . Chuẩn 𝑙2 được sử dụng trong hầu hết các lĩnh vực kỹ thuật và khoa học. Theo định nghĩa cơ bản, chuẩn 𝑙2 được xác định bởi công thức (9): ‖𝑥‖2 = √∑𝑖|𝑥𝑖 |2 (9) Chuẩn 𝑙2 được biết đến như là một chuẩn Euclide, được sử dụng như một đại lượng chuẩn để đo sự chênh lệch véc-tơ. 13 Như trong chuẩn 𝑙1 , nếu chỉ số Euclide được tính cho một sự khác biệt về véc-tơ, nó được gọi là khoảng cách Euclide và được xác định trong công thức (10): ‖𝑥1 − 𝑥2 ‖2 = √∑ |𝑥1 − 𝑥2 |2 (10) hoặc được gọi là một Sum of Squared Difference (SSD): SSD (𝑥1 , 𝑥2 ) = ‖𝑥1 − 𝑥2 ‖22 = ∑𝑖(𝑥1i − 𝑥2i )2 (11) Ứng dụng được biết đến nhiều nhất trong lĩnh vực xử lý tín hiệu là đo lường sai số trung bình (MSE), được sử dụng để tính toán độ tương đồng hoặc tương quan giữa hai tín hiệu: 1 1 𝑛 𝑛 MSE (𝑥1 , 𝑥2 ) = ‖𝑥1 − 𝑥2 ‖22 = ∑𝑖(𝑥1i − 𝑥2i )2 (12) Để làm rõ hơn ý nghĩa và giải pháp của các phương pháp tối thiểu hóa dựa trên các chuẩn 𝑙0 , 𝑙1 , 𝑙2 , hình học trong không gian 2-D được sử dụng để minh họa như trong hình 1.3. Tối thiểu hóa với chuẩn 𝑙0 trong hình 1.3a, tối thiểu hóa với chuẩn 𝑙1 trong hình 1.3b và tối thiểu hóa với chuẩn 𝑙2 trong hình 1.3c [1,43]. Gọi S (norm ball) là đường màu đỏ biểu diễn các điểm mà tại đó giá trị chuẩn của chúng bằng nhau. Bài toán mục tiêu có thể xem như việc xấp xỉ hàm mục tiêu bởi các điểm trên norm ball. Để xấp xỉ hàm, ta thay đổi tỉ lệ của norm ball đến khi norm ball tiếp xúc với giá trị hàm mục tiêu (đường thẳng y = Ax trong hình). Tọa độ điểm tiếp xúc chính là hệ số biểu diễn x cần tìm. Từ hình 1.3a và 1.3b, giao điểm có xu hướng cắt các điểm trên trục tọa độ hay nói cách khác, sử dụng ràng buộc 𝑙0 và 𝑙1 sẽ thúc đẩy yếu tố thưa trong biểu diễn véc-tơ. Cũng qua đó, trong hình 1.3c, giao điểm rất khó cắt các trục tọa độ, vì vậy, việc sử dụng ràng buộc 𝑙2 khó đảm bảo tính thưa cho biểu diễn véc-tơ. 14 Hình 1.3. Mô tả giải pháp tối thiểu hóa của một số chuẩn trong không gian 2-D Ngoài các chuẩn cơ bản kể trên, trong một số mô hình học từ điển thưa còn sử dụng đến chuẩn Frobenius.  Chuẩn Frobenius Chuẩn Frobenius được biết đến như là chuẩn 𝑙2,1 (chuẩn F) [4,43]. Việc xác định chuẩn F của một ma trận X ∈ 𝑅𝑚∗𝑛 thông qua 2 bước: Tìm chuẩn 𝑙1 của X theo công thức (13): ‖𝑋 ‖1 = 𝑚𝑎𝑥𝑗=1,…,𝑛 ∑𝑚 𝑛 |𝑥𝑖,𝑗 | (13) Tìm chuẩn 𝑙2 của X theo công thức (14): ‖𝑋 ‖2 = 𝛿𝑚𝑎𝑥 (X) = (𝜆𝑚𝑎𝑥 (𝑋 𝑇 𝑋))1/2 (14) Khi đó, chuẩn F được xác định bởi công thức tổng quát (15): 2 1/2 ‖𝑋 ‖1,2 = ∑𝑛𝑖=1(∑𝑚 𝑗=1 𝑋𝑗,𝑖 )) (15) Các giải thuật xác định hệ số biểu diễn trong mô hình học điển sử dụng phương pháp tối ưu hóa dựa trên các chuẩn sẽ được trình bày trong phần 1.2.2 của luận văn. Cũng có một số thuật toán được áp dụng vào cho việc biểu diễn thưa với tối thiểu hóa chuẩn F, tuy nhiên luận văn không đi sâu vào tìm hiểu mà chỉ mang tính chất giới thiệu.