Tài liệu ứng dụng khai triển kì dị trong nén ảnh

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 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 2 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 này được hoàn thành tại Viện Toán học, Viện hàn lâm Khoa Học và Công nghệ Việt Nam. Em xin bày tỏ lòng biết ơn tới các thầy cô giáo và các cán bộ nhân viên của Viện Toán học, các thầy cô giáo ở Khoa Toán trường Đại học Sư phạm Hà Nội 2, đặc biệt là tổ Ứng dụng, đã tạo điều kiện thuận lợi cho em trong quá trình thực hiện khóa luận này. Đặc biệt, em xin bày tỏ sự kính trọng và 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, chỉ bảo tận tình giúp đỡ để em có thể hoàn thành khóa luận này. Do thời gian, năng lực và điều kiện bản thân còn hạn chế nên bản khóa luận không thể tránh khỏi những sai sót. Vì vậy, em rất mong nhận được những ý kiến góp ý quý báu của các thầy cô và các bạn. Em xin chân thành cảm ơn! Hà Nội, ngày 20 tháng 4 năm 2017. Sinh viên Nguyễn Thị Thảo i LỜI CAM ĐOAN Khóa luận này là những nghiên cứu của em dưới sự hướng dẫn tận tình nghiêm khắc của cô giáo TS. Lê Hải Yến bên cạnh đó em được sự quan tâm, tạo điều kiện của các thầy cô trong khoa toán trường ĐHSP Hà Nội 2. Vì vậy em xin cam đoan nội dung đề tài "Ứng dụng khai triển giá trị kì dị trong nén ảnh" không có sự trùng lặp với các đề tài khác. Trong khi thực hiện khóa luận này em đã sử dụng và tham khảo các thành tựu của các nhà khoa học với lòng biết ơn trân trọng. Hà Nội, ngày 20 tháng 4 năm 2017. Sinh viên Nguyễn Thị Thảo ii Mục lục Lời mở đầu 1 1 Kiến thức chuẩn bị 4 1.1. Ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1. Tập ảnh, tập không điểm, hạng của một ma trận . . . . . . . . 4 1.1.2. Tính trực giao . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3. Chuẩn ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2. Chuẩn vectơ 1.4. Tính bất biến của chuẩn Frobenius và chuẩn hai . . . . . . . . . . . . 2 Khai triển giá trị kì dị (SVD) 12 14 2.1. Định lý về 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 . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Ứng dụng trong 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 trong khoa học và công nghệ hiện đại. Trong đại số tuyến tính, khai triển ma trận là sự phân tích một ma trận thành tích các ma trận thừa số. Có rất nhiều cách khai triển ma trận, nhưng ở khóa luận này, chúng tôi quan tâm đến khai triển thành giá trị kì dị (Singular Value Decomposition) của ma trận A như sau: Cho A là ma trận thực cỡ m×n . Khi đó, tồn tại các ma trận trực giao U ∈ Rm×m và V ∈ Rn×n sao 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) được gọi là các giá trị kì dị của A. Khai triển thành giá trị kì dị đưa ma trận ban đầu về dạng đường chéo sẽ làm giảm mức độ tính toán và có nhiều ứng dụng hữu ích trong xử lí tín hiệu và thống kê. Trên cơ sở khai triển giá trị kì dị (Singular Value Decomposition), vấn đề xấp xỉ một ma trận bằng một ma trận hạng thấp hơn được hai nhà toán học Carl Eckart và Gale Young đề cập tới vào năm 1936, đó là việc giải bài toán tìm ma trận có hạng nhỏ hơn k P hoặc bằng k gần ma trận cho trước: Nếu k < r = rank(A) và Ak = σi ui viT thì i=1 min rank(B)=k kA − Bk2 = kA − Ak k2 = σk+1 . Khai triển giá trị kì dị có rất nhiều ứng dụng, một trong những ứng dụng đó là nén ảnh. Sử dụng phần mềm Matlab, bằng cách thay đổi số giá trị kì dị k thì từ một bức ảnh gốc ban đầu chúng ta sẽ thu các bức ảnh mờ nét tương ứng với giá trị k. Cấu trúc của khóa luận gồm có ba chương: Chương 1 "Kiến thức chuẩn bị" hệ thống lại một số khái niệm của đại số tuyến tính như: Chuẩn vectơ, chuẩn ma trận, ma trận trực giao và một số tính chất quan trọng phục vụ cho các chương sau. Chương 2 "Khai triển giá trị kì dị " trình bày về khai triển giá trị kì dị (Singular Value Decomposition) của ma trận và định lý Eckart Young. 1 Chương 3 "Ứng dụng trong xử lí ảnh " trình bày về ứng dụng của khai triển giá trị kì dị (Singular Value Decomposition) trong xử lí ảnh bằng phần mềm Matlab. Do thời gian thực hiện khóa luận không nhiều, kiến thức còn nhiều hạn chế nên khi làm khóa luận này em không tránh khỏi những hạn chế và sai sót. Em mong nhận được sự góp ý và những ý kiến phản biện của thầy cô và các bạn. Em xin chân thành cảm ơn! 2 Ký hiệu toán học R Tập tất cả các số thực. Rn Tập tất cả các vectơ có n chiều. Rm×n Tập tất cả các ma trận thực cỡ (m × n). k x kp Chuẩn p của vectơ x. k A k2 Chuẩn 2 của ma trận A. k A kF Chuẩn Frobenius của ma trận A. A = (aij )m×n Ma trận A cỡ m × n với các thành phần aij . null(A) Tập không điểm của ma trận A. span(v1 , v2 , ..., vn ) Không gian sinh bởi n vectơ. dim(S) Số chiều của không gian con (S). rank(A) Hạng của ma trận A. det(A) Định thức của ma trận A. tr(A) Vết của ma trận A. diag(d1 , ..., dp ) Ma trận đường chéo cỡ m × n với p = min(m, n). σi (A) P Giá trị kì dị thứ i của ma trận A. P Khai triển thành giá trị kì dị của ma trận Ak . A k Khai triển thành giá trị kì dị của ma trận A. 3 Chương 1 Kiến thức chuẩn bị Chương này trình bày lại một số khái niệm của đại số tuyến tính như chuẩn vectơ, chuẩn ma trận, ma trận trực giao, và một số tính chất quan trọng phục vụ cho các chương sau. Nội dung của chương được 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 của một ma trận Cho A là ma trận thực cỡ m × n. Giả sử m ≥ n. Định nghĩa 1.1. Tập ảnh của ma trận A được định nghĩa bởi: ran(A) = {y ∈ Rm , ∃x ∈ Rn : y = Ax}  Nếu A = a1 · · ·  an (với a1 , ..., an là các cột của A ) thì ran(A) = span{a1 , ..., an }, với span{a1 , ..., an } là không gian con của Rm sinh bởi n vectơ a1 , a2 , ..., an . 4 Định nghĩa 1.2. Tập không điểm của ma trận A được định nghĩa bởi: null(A) = {x ∈ Rn : Ax = 0}. Định nghĩa 1.3. Hạng của một ma trận A được xác định bởi số chiều của ran(A) tức là rank(A) = dim(ran(A)). Chú ý 1. Hạng của một ma trận A được có thể được định nghĩa bởi số lớn nhất các cột (hay hàng của A ) độc lập tuyến tính. 2. Nếu A ∈ Rm×n , thì dim(null(A)) + rank(A) = n. 1.1.2. Tính trực giao Định nghĩa 1.4. Tập các vectơ {x1 , x2 ..., xp } trong Rn được gọi là trực giao nếu xTi xj = 0 với mọi i 6= j và trực chuẩn nếu xTi xj = δij , ở đó δij =   1, khi i = j,  0, khi i 6= j. Định nghĩa 1.5. Ma trận Q ∈ Rm×m được gọi là ma trận trực giao nếu QT Q = I (I là ma trận đơn vị cỡ m × m). Ví dụ 1.1. Các ma trận sau là các ma trận trực giao   1 .. 0     • Im = ... ... ... ,   0 ... 1   cosα −sinα , •A= sinα cosα 5  1 0 0      • B = 0 −1 0  .   0 0 −1 Mệnh đề 1.1. Cho A là ma trận vuông cấp n với hệ số thực, khi đó (i) A là ma trận trực giao khi và chỉ khi hệ vectơ cột của A lập thành một cơ sở trực chuẩn của Rn với tích vô hướng chuẩn tắc của Rn . (ii) A là ma trận trực giao khi và chỉ khi hệ vectơ dòng của A lập thành cơ sở trực chuẩn của Rn với tích vô hướng chuẩn tắc của Rn . Định lý 1.1. Mọi hệ gồm các vectơ khác không, đôi một trực giao đều là hệ độc lập tuyến tính. Chứng minh. Ta xét hệ các vectơ trực giao (xi )i=1,2,...,m trong Rm . Giả sử m P ki xi = 0 i=1 với ki ∈ R. Nhân vô hướng hai vế với vectơ xj ( ∀j = 1, 2, ..., m) ta được hxj , m X ki xi i = 0, ∀j = 1, 2, ..., m. i=1 Theo định nghĩa tích vô hướng m X ki hxj , xi i = 0, ∀j = 1.2, ..., m. i=1 Vì hxj , xi i = 0 với mọi i 6= j nên ki hxj , xi i = 0, ∀j = 1, 2, .., m, mà hxi , xi i = 6 0, suy ra ki = 0, ∀j = 1, 2, .., m. Do đó {xi }( ∀i = 1, 2, ..., m) độc lập tuyến tính. Định lý 1.2. Giả sử S = {v1 , v2 , ..., vr } là hệ vectơ trực chuẩn của không gian Rn . Khi đó, ta có thể bổ sung n − r vectơ vào S để thu được một hệ cơ sở trực chuẩn. 6 Định lý 1.3. Nếu S = {v1 , v2 , ..., vn } là một họ vectơ trực chuẩn của không gian Rn thì với mọi vectơ u trong Rn ta có u = hu, v1 iv1 + hu, v2 iv2 + ... + hu, vn ivn . Chứng minh. Vì S là một cơ sở của Rn nên tồn tại các số thực c1 , c2 , ..., cn sao cho u có dạng u = c1 v1 + c2 v2 + ... + cn vn . Nhân vô hướng hai vế với vi (∀i = 1, 2, .., n) ta được hu, vi i = h(c1 v1 + c2 v2 + ... + cn vn ), vi i = c1 hv1 , vi i + ... + cn hvn , vi i. Vì S là cơ sở trực chuẩn nên hvj , vi i = 0, ∀j 6= i và hvi , vi i = 1. Do đó hu, vi i = ci . Ta được điều phải chứng minh. 1.2. Chuẩn vectơ Định nghĩa 1.6. Chuẩn vectơ trên Rn là một hàm f : Rn −→ R thỏa mãn các tính chất sau: (i) f (x) ≥ 0, ∀x ∈ Rn ; f (x) = 0 ⇐⇒ x = 0. (ii) f (x + y) ≤ f (x) + f (y), ∀x, y ∈ Rn ; ∀α ∈ R, ∀x ∈ Rn . (iii) f (αx) = |α|f (x), Kí hiệu : f (x) = kxk. Cho vectơ x = (x1 , x2 , ..., xn )T , các chuẩn vectơ thông dụng là : • Chuẩn p 1 kxkp = (|x1 |p + ... + |xn |p ) p , p ≥ 1. 7 • Chuẩn 1 (p = 1) kxk1 = |x1 | + ... + |xn |. • Chuẩn 2 (p = 2) 1 1 kxk2 = (|x1 |2 + ... + |xn |2 ) 2 = (xT x) 2 . • Chuẩn ∞ (p = ∞) kxk∞ = max(|x1 |, |x2 |, ..., |xn |). Bổ đề 1.1. Nếu Q ∈ Rn×n là ma trận trực giao và x ∈ Rn thì kQxk22 = kxk22 . Chứng minh. Ta có theo định nghĩa chuẩn 2 của vectơ, ta có kQxk22 = hQx, Qxi = (Qx)T (Qx) = xT QT Qx (do tính chất của ma trận chuyển vị) = xT x (do Q là ma trận trực giao nên QT Q = I) = kxk22 . 1.3. Chuẩn ma trận Định nghĩa 1.7. Chuẩn ma trận trên Rm×n là hàm số f : Rm×n −→ R thỏa mãn các tính chất sau: 8 (i) f (A) ≥ 0, ∀A ∈ Rm×n ; f (A) = 0 ⇐⇒ A = 0. (ii) f (A + B) ≤ f (A) + f (B), ∀A, B ∈ Rm×n ; ∀α ∈ R, ∀A ∈ Rm×n . (iii) f (αA) = |α|f (A), Kí hiệu : f (A) = kAk.  Cho ma trận (A) = (aij )m×n a11 ··· a12 a1n    a21 a22 · · · a2n =  .. .. .. .. .  . . .  am1 am2 · · · amn     , các chuẩn ma trận thông    dụng là: Chuẩn toán tử Nếu ma trận A thuộc không gian vectơ Rm×n thì chuẩn của A ứng với chuẩn p của vectơ là kAk = sup x6=0 kAxkp , kxkp ∀x ∈ Rn . Chuẩn 1 ( chuẩn cực đại theo cột ) kAk1 = max 1≤j≤n m X |aij |. i=1 Chuẩn 2 kAk2 = sup x6=0 kAxk2 , kxk2 ∀x ∈ Rn . Chuẩn ∝ ( chuẩn cực đại theo hàng ) kAk∝ = max 1≤i≤m 9 n X j=1 |aij |.  4 2  3    .      −1 3 −2 Ví dụ 1.2. Cho ma trận A =   0 1 5  2 4 −3 Chuẩn 1 của ma trận A là kAk1 = max 1≤j≤3 4 X |aij | = max (|a1j | + |a2j | + |a3j | + |a4j |) 1≤j≤3 i=1 = max(|a11 | + |a21 | + |a31 + |a41 |; |a12 | + |a22 | + |a32 | + |a42 |; |a13 | + |a23 | + |a33 | + |a43 |) = max(4 + 1 + 0 + 2; 2 + 3 + 1 + 4; 3 + 2 + 5 + 3) = max(7, 10, 13) = 13. Chuẩn ∝ của ma trận A là kAk∝ = max 1≤i≤4 3 X |aij | = max (|ai1 | + |ai2 | + |ai3 |) j=1 1≤i≤4 = max(|a11 | + |a12 | + |a13 |; |a21 | + |a22 | + |a23 |; |a31 | + |a32 | + |a33 |; |a41 | + |a42 | + |a43 |) = max(4 + 2 + 3; 1 + 3 + 2; 0 + 1 + 5; 2 + 4 + 3) = max(9; 6; 6; 9) = 9. Chuẩn từng phần Lấy chuẩn cho từng phần tử của ma trận, ta có kAk = m X n X ! p1 (|aij |)p . i=1 j=1 Ví dụ 1.3. Xét ma trận A ở Ví dụ 1.2 . Khi đó chuẩn từng phần của ma trận A với 10 p=3 là kAk = 4 X 3 X (|aij |)3 ! 31 i=1 j=1 = (|4|3 + |2|3 + |3|3 + | − 1|3 + |3|3 + | − 2|3 + |0|3 + |1|3 1 + |1|3 + |5|3 + |2|3 + |4|3 + | − 3|3 ) 3 = √ 3 360. Đặc biệt , khi p=2 ta được chuẩn Frobenius, kí hiệu là kAkF . Chuẩn Frobenius có nhiều định nghĩa khác nhau: v uX n u m X t kAkF = |aij |2 , i=1 j=1 hoặc kAkF = p tr(AT A). ở đó tr(AT A) là vết của ma trận (AT A). Định lý 1.4. Nếu A ∈ Rm×n , thì tồn tại một vectơ đơn vị z (theo chuẩn 2) trong Rn sao cho AT Az = µ2 z ở đây µ = kAk2 . 1 kAxk22 1 xT AT Ax Chứng minh. : Xét hàm g(x) = = . 2 kxk22 2 xT x Giả sử z ∈ Rn là một vectơ đơn vị sao cho kAzk2 = kAk2 . Vì z là điểm mà hàm g(x) đạt giá trị cực đại, suy ra ∇g(z) = 0, ở đây ∇g là gradient của g. Một phép lấy vi phân chỉ ra rằng với mọi i = 1; n ta có: n X ∂g(z) T = [(z z) (AT A)ij zj − (z T AT Az)zi ]/(z T z)2 , ∂zi j=1 với ký hiệu AT Az = (z T AT Az)z. Định lý được suy ra bởi việc đặt µ = kAzk2 . 11 Định lý suy ra rằng kAk2 = 1.4. p λmax (AT A). Tính bất biến của chuẩn Frobenius và chuẩn hai Chuẩn Frobenius và chuẩn hai của ma trận bất biến với phép nhân trái và phải với các ma trận trực giao. Tính chất này được thể hiện ở hai định lý sau đây: Định lý 1.5. Cho A ∈ Rm×n , nếu hai ma trận Q ∈ Rm×m và Z ∈ Rn×n là các ma trận trực giao thì kQAZkF = kAkF . Chứng minh. Ta có theo định nghĩa chuẩn Frobenius, ta có kQAk2F = = n X j=1 n X kQA(:, j)k22 (QA(:, j) là vectơ cột thứ j của ma trận QA) kA(:, j)k22 ( theo Bổ đề 1.1) j=1 = kAk2F ( theo định nghĩa chuẩn Frobenius). Vì vậy, kQ(AZ)k)2F = kAZk2F = k(AZ)T k2F ( do tính chất của chuẩn Frobenius kAZk2F = k(AZ)T k2F ) = kZ T AT k2F (do tính chất của ma trận chuyển vị ) = kAT k2F ( do Z là ma trận trực giao nên Z T cũng là ma trận trực giao ) = kAk2F (do định nghĩa chuẩn Frobenius kAT kF = kAkF ). 12 Định lý 1.6. Cho A ∈ Rm×n , nếu hai ma trận Q ∈ Rm×m và Z ∈ Rn×n là các ma trận trực giao thì kQAZk2 = kAk2 . Chứng minh. Theo định nghĩa của chuẩn 2 ta có: kQAk22  2 kQAxk2 = sup . kxk2 x6=0 Do Q là ma trận trực giao nên theo Bổ đề 1.1, ta có  kQAxk2 sup kxk2 x6=0 2  2 kAxk2 = sup = kAk22 . kxk x6=0 2 Do đó kQAZk22 = kAZk22 = k(AZ)T k22 = kZ T AT k22 = kAT k22 = kAk22 . (lý giải tương tự phần chứng minh của Định lý 1.5) 13 Chương 2 Khai triển giá trị kì dị (SVD) Trong chương này, chúng ta sẽ tìm hiểu về khai triển giá trị kì dị (Singular Value Decomposition) của ma trận, tức là sử dụng các ma trận trực giao để đưa ma trận ban đầu về dạng đường chéo. Khai triển thành giá trị kì dị (viết tắt là SVD ) có vai trò rất quan trọng trong việc giải bài toán tìm ma trận gần nhất và xử lí dữ liệu. Nội dung của chương được chia làm ba phần. Phần 2.1 trình bày Định lí về sự tồn tại của khai triển thành giá trị kì dị, phần 2.2 trình bày về một số tính chất và phần 2.3 trình bày về Định lí Eckart-Young. 2.1. Định lý về khai triển giá trị kì dị Định lý 2.1. Nếu A là ma trận thực cỡ m × n thì tồn tại các ma trận trực giao U = [u1 , ..., um ] ∈ Rm×m và V = [v1 , ...., vn ] ∈ Rn×n , sao cho U T AV = ΣA = diag(σ1 (A), ...., σp (A)) ∈ Rm×n , trong đó p = min(m, n) , σ1 (A) ≥ σ2 (A) ≥ .... ≥ σp (A) ≥ 0, σi (A) được gọi là các giá trị kỳ dị của A 14 Chứng minh. Xét x ∈ Rn và y ∈ Rm là các vectơ đơn vị theo chuẩn 2 thỏa mãn: Ax = σy với σ = kAk2 . Từ Định lý 1.2 tồn tại V2 ∈ Rn×(n−1) và U2 ∈ Rm×(m−1) sao cho V = [x, V2 ] ∈ Rn×n và U = [y, U2 ] ∈ Rm×m là các ma trận trực giao. Ta có  U T AV =   =  = yT U2T yT U2T T   yT   [Ax, AV2 ]  A[x, V2 ] =  T U2   [σy, AV2 ] y σy T y AV2 U2T σy U2T AV2   T σ W , = 0 B   trong đó   y T y = 1, U2T y = 0 (do U trực giao)  W ∈ Rn−1 , B ∈ R(m−1)×(n−1) .   σ WT , ta có: Đặt A1 =  0 B      2 T σ σ W σ σ +W W   =  . A1   =  W 0 B W BW T   Do đó   2

σ A1   = σ 2 + W T W 2 + kBW k2 ≥ σ 2 + W T W 2 , 2 W 2 15