BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA TOÁN NGUYỄN THỊ THẢO ỨNG DỤNG KHAI TRIỂN KÌ DỊ TRONG NÉN ẢNH KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Hà Nội – Năm 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA TOÁN NGUYỄN THỊ THẢO ỨNG DỤNG KHAI TRIỂN KÌ DỊ TRONG NÉN ẢNH Chuyên ngành: ỨNG DỤNG Mã số: KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS LÊ HẢI YẾN Hà Nội – Năm 2017 LỜI CẢM ƠN Khóa luận hoàn thành Viện Toán học, Viện hàn lâm Khoa Học Công nghệ Việt Nam Em xin bày tỏ lòng biết ơn tới thầy cô giáo cán nhân viên Viện Toán học, thầy cô giáo Khoa Toán trường Đại học Sư phạm Hà Nội 2, đặc biệt tổ Ứng dụng, tạo điều kiện thuận lợi cho em trình thực khóa luận Đặc biệt, em xin bày tỏ kính trọng lòng biết ơn sâu sắc tới TS Lê Hải Yến, người trực tiếp hướng dẫn, bảo tận tình giúp đỡ để em hoàn thành khóa luận Do thời gian, lực điều kiện thân hạn chế nên khóa luận tránh khỏi sai sót Vì vậy, em mong nhận ý kiến góp ý quý báu thầy cô bạn Em xin chân thành cảm ơn! Hà Nội, ngày 20 tháng năm 2017 Sinh viên Nguyễn Thị Thảo i LỜI CAM ĐOAN Khóa luận nghiên cứu em hướng dẫn tận tình nghiêm khắc cô giáo TS Lê Hải Yến bên cạnh em quan tâm, tạo điều kiện thầy cô khoa toán trường ĐHSP Hà Nội Vì em xin cam đoan nội dung đề tài "Ứng dụng khai triển giá trị kì dị nén ảnh" trùng lặp với đề tài khác Trong thực khóa luận em sử dụng tham khảo thành tựu nhà khoa học với lòng biết ơn trân trọng Hà Nội, ngày 20 tháng năm 2017 Sinh viên Nguyễn Thị Thảo ii Mục lục Lời mở đầu 1 Kiến thức chuẩn bị 1.1 Ma trận 1.1.1 Tập ảnh, tập không điểm, hạng ma trận 1.1.2 Tính trực giao 1.3 Chuẩn ma trận 1.2 Chuẩn vectơ 1.4 Tính bất biến chuẩn Frobenius chuẩn hai Khai triển giá trị kì dị (SVD) 12 14 2.1 Định lý khai triển giá trị kì dị 14 2.2 Một số tính chất 17 2.3 Định lý Eckart - Young 24 Ứng dụng xử lí ảnh 27 Kết luận 39 Tài liệu tham khảo 39 iii LỜI MỞ ĐẦU Khai triển ma trận có vai trò quan trọng khoa học công nghệ đại Trong đại số tuyến tính, khai triển ma trận phân tích ma trận thành tích ma trận thừa số Có nhiều cách khai triển ma trận, khóa luận này, quan tâm đến khai triển thành giá trị kì dị (Singular Value Decomposition) ma trận A sau: Cho A ma trận thực cỡ m×n Khi đó, tồn ma trận trực giao U ∈ Rm×m V ∈ Rn×n cho U T AV = ΣA = diag(σ1 (A), σ2 (A), , σp (A)) ∈ Rm×n , p = min(m, n) Trong σ1 (A) ≥ σ2 (A) ≥ ≥ σp (A) ≥ 0, σi (A) gọi giá trị kì dị A Khai triển thành giá trị kì dị đưa ma trận ban đầu dạng đường chéo làm giảm mức độ tính toán có nhiều ứng dụng hữu ích xử lí tín hiệu thống kê Trên sở khai triển giá trị kì dị (Singular Value Decomposition), vấn đề xấp xỉ ma trận ma trận hạng thấp hai nhà toán học Carl Eckart Gale Young đề cập tới vào năm 1936, việc giải toán tìm ma trận có hạng nhỏ k k gần ma trận cho trước: Nếu k < r = rank(A) Ak = σi ui viT i=1 A−B rank(B)=k = A − Ak = σk+1 Khai triển giá trị kì dị có nhiều ứng dụng, ứng dụng nén ảnh Sử dụng phần mềm Matlab, cách thay đổi số giá trị kì dị k từ ảnh gốc ban đầu thu ảnh mờ nét tương ứng với giá trị k Cấu trúc khóa luận gồm có ba chương: Chương "Kiến thức chuẩn bị" hệ thống lại số khái niệm đại số tuyến tính như: Chuẩn vectơ, chuẩn ma trận, ma trận trực giao số tính chất quan trọng phục vụ cho chương sau Chương "Khai triển giá trị kì dị " trình bày khai triển giá trị kì dị (Singular Value Decomposition) ma trận định lý Eckart Young Chương "Ứng dụng xử lí ảnh " trình bày ứng dụng khai triển giá trị kì dị (Singular Value Decomposition) xử lí ảnh phần mềm Matlab Do thời gian thực khóa luận không nhiều, kiến thức nhiều hạn chế nên làm khóa luận em không tránh khỏi hạn chế sai sót Em mong nhận góp ý ý kiến phản biện thầy cô bạn Em xin chân thành cảm ơn! Ký hiệu toán học R Tập tất số thực Rn Tập tất vectơ có n chiều Rm×n Tập tất ma trận thực cỡ (m × n) x p Chuẩn p vectơ x A Chuẩn ma trận A A F Chuẩn Frobenius ma trận A A = (aij )m×n Ma trận A cỡ m × n với thành phần aij null(A) Tập không điểm ma trận A span(v1 , v2 , , ) Không gian sinh n vectơ dim(S) Số chiều không gian (S) rank(A) Hạng ma trận A det(A) Định thức ma trận A tr(A) Vết ma trận A diag(d1 , , dp ) Ma trận đường chéo cỡ m × n với p = min(m, n) σi (A) Giá trị kì dị thứ i ma trận A A Khai triển thành giá trị kì dị ma trận A k Khai triển thành giá trị kì dị ma trận Ak Chương Kiến thức chuẩn bị Chương trình bày lại số khái niệm đại số tuyến tính chuẩn vectơ, chuẩn ma trận, ma trận trực giao, số tính chất quan trọng phục vụ cho chương sau Nội dung chương tham khảo chủ yếu từ tài liệu [3] 1.1 Ma trận 1.1.1 Tập ảnh, tập không điểm, hạng ma trận Cho A ma trận thực cỡ m × n Giả sử m ≥ n Định nghĩa 1.1 Tập ảnh ma trận A định nghĩa bởi: ran(A) = {y ∈ Rm , ∃x ∈ Rn : y = Ax} Nếu A = a1 · · · an (với a1 , , an cột A ) ran(A) = span{a1 , , an }, với span{a1 , , an } không gian Rm sinh n vectơ a1 , a2 , , an Định nghĩa 1.2 Tập không điểm ma trận A định nghĩa bởi: null(A) = {x ∈ Rn : Ax = 0} Định nghĩa 1.3 Hạng ma trận A xác định số chiều ran(A) tức rank(A) = dim(ran(A)) Chú ý Hạng ma trận A được định nghĩa số lớn cột (hay hàng A ) độc lập tuyến tính Nếu A ∈ Rm×n , dim(null(A)) + rank(A) = n 1.1.2 Tính trực giao Định nghĩa 1.4 Tập vectơ {x1 , x2 , xp } Rn gọi trực giao xTi xj = với i = j trực chuẩn xTi xj = δij , δij =   1, i = j,  0, i = j Định nghĩa 1.5 Ma trận Q ∈ Rm×m gọi ma trận trực giao QT Q = I (I ma trận đơn vị cỡ m × m) Ví dụ 1.1 Các ma trận sau ma trận trực giao       • Im =   ,     cosα −sinα , •A= sinα cosα Mà k+1 Az 2 σi (viT z)ui = i=1 k+1 σi2 (viT z)2 (do(ui ) trực chuẩn) = i=1 k+1 ≥ σk+1 (viT z)2 i=1 = σk+1 Vì A − B Do rank(B)=k 2 Hay A − B ≥ σk+1 A−B = A − Ak 2 ≥ σk+1 = σk+1 26 Chương Ứng dụng xử lí ảnh Có hàng trăm cách khác để nén ảnh, chương giới thiệu cách nén ảnh sử dụng khai triển giá trị kì dị SVD Giả sử có ảnh đen trắng cỡ 3000 × 3000 pixel (bức ảnh biểu diễn ma trận 3000 × 3000), với pixel có mức độ màu đen trắng cho số số nguyên từ đến 255 Mỗi số nguyên xấp xỉ byte để lưu trữ, kết thu ảnh xấp xỉ 8,6 Mb Một ảnh màu thường có thành phần là: màu đỏ, màu xanh màu xanh nước biển Mỗi ảnh thường lưu trữ ba ma trận, file lưu trữ ảnh màu chiếm lần không gian ( 25,8 Mb) Trong chương này, xem xét cách nén ảnh cách sử dụng khai triển thành giá trị kì dị Định lí Eckart-Young ( Chương 2) Ta xét ảnh đen trắng ma trận A cỡ m × n tương ứng Giả sử A có khai triển thành giá trị kì dị A = U ΣV T Như biết Định lí Eckart-Young Chương 2, với k, ta xấp xỉ ma trận A bới ma trận Ak = U Σk V T với k < r = rank(A) Ak = k σi ui viT i=1 rank(B)=k A−B = A − Ak = σk+1 Ứng với giá trị k, ta thu ảnh ứng với ma trận Ak Để lưu ảnh này, ta cần lưu k(m + n + 1) số thay phải lưu m × n số cho ảnh gốc Và 27 giá trị k tăng lên ta thu ảnh gần giống với ảnh gốc Ở đây, sử dụng phần mềm Matlab để thực trình nén ảnh Ví dụ 1: Chúng ta có ảnh cỡ 400 × 400 pixel Hình 3.1: ảnh gốc 28 Ta sử dụng dòng lệnh sau Matlab 29 Khi thu ảnh khác nhau, có độ nét tăng dần số giá trị kì dị k tăng lên k lớn ảnh thu giống với ảnh gốc ban đầu 30 Hình 3.2: ảnh có độ nét tăng dần tương ứng với số giá trị kì dị k tăng dần : 5, 30, 55, 280 31 Dưới đồ thị vẽ sai số thay đổi k thay đổi Ví dụ 2: Chúng ta có ảnh cỡ 250 × 600 pixel Hình 3.3: ảnh gốc 32 Sử dụng dòng lệnh Matlab tương tự dòng lệnh trang 29, 30 Thay câu lệnh số câu lệnh sau: inImage=imread(’bacu.jpg’) Khi thu ảnh khác nhau, có độ nét tăng dần số giá trị kì dị k tăng lên k lớn ảnh thu giống với ảnh gốc ban đầu Hình 3.4: ảnh có độ nét tăng dần tương ứng với số giá trị kì dị k tăng dần : 5, 30, 205, 280 33 Dưới đồ thị vẽ sai số thay đổi k thay đổi Ví dụ 3: Chúng ta có ảnh cỡ màu cỡ 250 × 300 pixel Hình 3.5: ảnh gốc 34 Ta sử dụng dòng lệnh sau Matlab 35 Hình 3.6: 36 Khi thu ảnh khác nhau, có độ nét tăng dần số giá trị kì dị k tăng lên k lớn ảnh thu giống với ảnh gốc ban đầu Hình 3.7: ảnh có độ nét tăng dần tương ứng với số giá trị kì dị k tăng dần : 5, 55, 205, 280 37 Dưới đồ thị vẽ sai số thay đổi k thay đổi 38 Kết Luận Khóa luận trình bày sô kiến thức đại số tuyến tính chuẩn vectơ, chuẩn ma trận, ma trận trực giao quan tâm đến khai triển thành giá trị kì dị ma trận làm giảm độ phức tạp tính toán tính chất cần thiết để chứng minh Định lý Eckart - Young Chương Chương khóa luận em phát biểu chứng minh chi tiết hai định lí Định lí khai triển giá trị kì dị Định lí Eckart - Young Chương khóa luận em giới thiệu ứng dụng khai triển giá trị kì dị nén ảnh phần mềm Matlab Qua khóa luận thân em lĩnh hội thêm nhiều tri thức Đại số tuyến tính, môn học có tầm quan trọng đặc biệt toán học toán học ứng dụng Tuy nhiên thời gian thực không nhiều kiến thức hạn chế nên không tránh sai sót, em mong nhận góp ý thầy cô bạn sinh viên để khóa luận hoàn thiện Em xin chân thành cảm ơn! 39 Tài liệu tham khảo [1] Lê Tuấn Hoa (2005), Đại số tuyến tính qua ví dụ tập, NXB ĐHQG Hà Nội [2] Ngô Việt Trung (2001), Đại số tuyến tính , NXB ĐHQG Hà Nội [3] Nguyễn Thị Hoàng Khuyên(2015), Định lí Eckart-young dạng rời rạc cho ma trận nguyên, Luận văn thạc sĩ, Viện Toán học, Viện Hàn lâm Khoa học Công nghệ Việt Nam [4] Carl Eckart - Gale Young (1936), The approximation of one matrix by another of lower rank Psychometrika, 1(3), 211-218 [5] Gene Howard Golub, Charles Francis Van Loan (1996), Matrix computations(third edition) Johns Hopkins University Press Baltimore, MD, USA 40 ... = A − Ak = σk+1 Khai triển giá trị kì dị có nhiều ứng dụng, ứng dụng nén ảnh Sử dụng phần mềm Matlab, cách thay đổi số giá trị kì dị k từ ảnh gốc ban đầu thu ảnh mờ nét tương ứng với giá trị... "Khai triển giá trị kì dị " trình bày khai triển giá trị kì dị (Singular Value Decomposition) ma trận định lý Eckart Young Chương "Ứng dụng xử lí ảnh " trình bày ứng dụng khai triển giá trị kì. .. VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA TOÁN NGUYỄN THỊ THẢO ỨNG DỤNG KHAI TRIỂN KÌ DỊ TRONG NÉN ẢNH Chuyên ngành: ỨNG DỤNG Mã số: KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: