Báo cáo tốt nghiệp lấy mẫu nén

  • Số trang: 38 |
  • Loại file: PDF |
  • Lượt xem: 21 |
  • Lượt tải: 0
nganguyen

Đã đăng 34173 tài liệu

Mô tả:

Lời Nói Đầu Trong cuộc cách mạng khoa học kỹ thuật diễn ra mạnh mẽ như ngày nay, các phát minh, các nghiên cứu mới đã và đang làm cho cuộc sống của con người trở nên tiến bộ hơn, khoa học không ngừng phát triển, các lý thuyết cũ được thay thế bằng những lý thuyết mới hơn, và những lý thuyết mới hơn nữa sẽ dần thay thế nó. Lấy mẫu nén (Compressed Sampling) là một trong những lý thuyết mới nhất trong lĩnh vực xử lý tín hiệu hiện nay, được công bố năm 2006 là một bước ngoặt quan trọng trong lĩnh vực này, dựa trên lý thuyết này, trong nhiều trường hợp, chúng ta có thể thực hiện được việc lấy mẫu tín hiệu với tốc độ thấp hơn tốc độ lấy mẫu Nyquist - một trong những tiêu chuẩn được coi là chuẩn mực trong xử lý tín hiệu - mà vẫn đảm bảo được việc khôi phục lại tín hiệu ban đầu. Qua 2 năm phát triển, lý thuyết này đã được nhiều tác giả quan tâm và hoàn thiện hơn. Hiện nay lấy mẫu nén đang được tiếp tục nghiên cứu và phát triển về cả lý thuyết cũng như ứng dụng tại nhiều trường đại học trên thế giới. Với mục đích tiếp cận nhanh chóng lĩnh vực mới mẻ này, trong khóa luận tốt nghiệp của mình tôi tập trung nghiên cứu phương pháp lấy mẫu nén trên hai mảng lớn: • Nghiên cứu lý thuyết lấy mẫu nén và những thành tựu đã đạt được cho đến thời điểm hiện tại. • Nghiên cứu phát triển lý thuyết này với một ý tưởng mới về phương pháp lấy mẫu nén dựa trên bộ lọc hỗn loạn (Chaos filter) để đóng góp vào những kết quả đã đạt được. Những nghiên cứu lý thuyết về lấy mẫu nén và những thành tựu đã đạt được cho đến thời điểm hiện tại được trích dẫn và tham khảo từ nhiều bài báo được công bố bởi nhiều tác giả trên thế giới như: Candès, Romberg, Baraniuk....... Tôi xin cam đoan việc nghiên cứu phát triển mới (Chaos filter) là kết quả nghiên cứu của tôi dưới sự hướng dẫn khoa học của TS. Nguyễn Linh Trung. Không có các nghiên cứu đã được xuất bản từ trước hay viết bởi người khác. Xin cảm ơn sự hướng dẫn khoa học của TS. Nguyễn Linh Trung, sự góp ý hướng dẫn của GS. Huỳnh Hữu Tuệ, TS. Lê Vũ Hà và sự giúp đỡ của các thành viên Bộ môn Xử Lý Thông Tin giúp tôi hoàn thành khóa luận này. Hà Nội, Ngày 22 tháng 5 năm 2008 1 Mục lục 1 Giới Thiệu 1.1 Các Phương pháp nén cổ điển và nhược điểm của chúng 1.1.1 Tín hiệu thưa và có thể nén . . . . . . . . . . . . 1.1.2 Các phương pháp nén cổ điển và nhược điểm . . . 1.2 Phương pháp lấy mẫu nén . . . . . . . . . . . . . . . . . 1.3 Hai vấn đề chính trong lấy mẫu nén . . . . . . . . . . . . I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kỹ Thuật Lấy Mẫu Nén 2 Lý 2.1 2.2 2.3 4 4 4 5 5 6 7 thuyết về lấy mẫu nén Phương pháp lấy mẫu . . . . . . . . . . . . . Điều kiện để khôi phục được tín hiệu . . . . . Phương pháp khôi phục tín hiệu . . . . . . . . 2.3.1 Thuật toán khôi phục L1-minimization 2.3.2 Thuật toán khôi phục OMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 7 9 9 10 12 3 Ứng dụng của lý thuyết lấy mẫu nén 15 3.1 Trong nén dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Trong truyền Thông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Mô 4.1 4.2 4.3 phỏng lấy mẫu nén 19 Nén tín hiệu thưa trong miền thời gian . . . . . . . . . . . . . . . . . . . . . . . 19 Nén ảnh sử dụng CS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Nén tín hiệu thưa trong miền tần số . . . . . . . . . . . . . . . . . . . . . . . . 21 II Phát triển lý thuyết lấy mẫu nén trên cơ sở bộ lọc hỗn độn (Chaos filter) 23 5 Giả ngẫu nhiên và hỗn độn 5.1 Giới thiệu ngắn gọn về lý thuyết hỗn độn . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Hỗn độn là gì? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.2 Một số hàm hỗn độn thông thường . . . . . . . . . . . . . . . . . . . . . 5.2 Kỹ thuật sử dụng bộ lọc ngẫu nhiên(random filter) trong lấy mẫu nén và sự cần thiết để phát triển bộ lọc hỗn độn(chaos filter) . . . . . . . . . . . . . . . . . . . 23 23 23 24 6 Thiết kế bộ lọc hỗn độn 6.1 Thiết kế bộ lọc hỗn độn và khôi phục tín 6.1.1 Phương pháp lấy mẫu . . . . . . 6.1.2 Phương pháp khôi phục tín hiệu . 6.2 Thiết kế bộ lọc hỗn độn và khôi phục tín 28 28 28 30 31 2 hiệu dùng L1 minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . hiệu dùng OMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 7 Mô 7.1 7.2 7.3 phỏng Mô phỏng kỹ thuật lấy mẫu nén sử dụng bộ lọc ngẫu nhiên . . . . . . . . . . . Mô phỏng sử dụng bộ lọc hỗn độn với phương pháp khôi phục L1 minimization Mô phỏng sử dụng bộ lọc hôn độn với phương pháp khôi phục OMP . . . . . . . 8 Kết Luận 34 35 35 36 37 3 1 Giới Thiệu Định lý lấy mẫu của Shannon/Nyquist nói rằng để không mất thông tin và có thể khôi phục lại hoàn toàn tín hiệu thì phải lấy mẫu tín hiệu với tần số lấy mẫu cao hơn ít nhất 2 lần băng tần của tín hiệu. Trong nhiều ứng dụng như trong ảnh số và camera số, tốc độ lấy mẫu Nyquist là cao và thu quá nhiều mẫu cần thiết, do đó việc nén tín hiệu là cần thiết cho việc lưu trữ hoặc truyền đi xa. Hay trong các ứng dụng khác như: hệ thống ảnh số với tốc độ cao, kỹ thuật siêu cao tần, thu thập dữ liệu từ rada.....Đòi hỏi lấy mẫu ở tần số rất cao nếu tuân theo định luật Nyquist, điều đó dẫn đến việc đòi hỏi các bộ chuyển đổi ADC tốc độ cao gây ra nhiều khó khăn trong chế tạo, và giá thành trở nên rất đắt. Nghiên cứu này trình bày một phương pháp mới để thu các tín hiệu với tốc độ lấy mẫu nhỏ hơn tốc độ Nyquist. Phương pháp này gọi là lấy mẫu nén (compressed sampling), sử dụng các ánh xạ (projections) tuyến tính không thích nghi lưu trữ cấu trúc của tín hiệu, tín hiệu sau đó được tái tạo lại sử dụng các phương pháp của lý thuyết tối ưu như L1-minimization hoặc OMP. 1.1 1.1.1 Các Phương pháp nén cổ điển và nhược điểm của chúng Tín hiệu thưa và có thể nén Cho một tín hiệu rời rạc x chiều dài hữu hạn, x có thể được biểu diễn như một vectơ cột N × 1 trong RN với các thành phần x[n], n = 1, 2, ....N . Bất kỳ tín hiệu trong RN nào đều có thể biểu diễn thông qua một hệ các vectơ cơ sở trực chuẩn N × 1 : {ψi }N i=1 . Sử dụng ma trận cơ sở N × N : Ψ = [ψ1 ψ2 ...ψN ] với các vectơ {ψi } là các vectơ cột, thì một tín hiệu x có thể biểu diễn như sau: N X x= si ψi i=1 hoặc x = Ψ.s Ở đây s là vectơ cột N × 1 của các trọng số si =< x, ψi >= ψiT x và .T là ký hiệu ma trận chuyển vị. Nói cách khác thì x và s là sự biểu diễn của cùng một tín hiệu, x trong miền thời gian (hoặc không gian) và s trong miền ψ. Tín hiệu x chiều dài N được gọi là thưa K (K-sparse) nếu x là một sự kết hợp tuyến tính của duy nhất K vectơ cơ sở, do đó chỉ có duy nhất K trọng số si là khác không và (N-K) trọng số là bằng không. Trong trường hợp mà K  N thì tín hiệu x gọi là thưa và có thể nén tức là nó có thể được biểu diễn chỉ với K trọng số lớn và nhiều trọng số nhỏ. 4 1.1.2 Các phương pháp nén cổ điển và nhược điểm Các kỹ thuật nén cổ điển (điển hình như DCT rời rạc, hay wavelet) sử dụng 1 phép biến đổi thuận nghịch (transform coding) để xấp xỉ tín hiệu có thể nén bằng K trọng số lớn.Cho một tín hiệu x dài N mẫu và là tín hiệu thưa K, sử dụng phép biến đổi thông qua : s = ΨT x ΨT ở đây đại diện cho một phép chuyển đổi nào đó (DCT rời rạc hoặc wavelet) chúng ta sẽ thu được một tập hợp các trọng số si trong đó K trọng số lớn nhất sẽ được lấy và mã hóa, còn lại (N-K) trọng số nhỏ sẽ được loại bỏ. Tuy nhiên chính cách làm này xuất hiện những nhược điểm của phương pháp: • Số lượng N các mẫu thu là lớn trong khi K lại là nhỏ K  N • Tất cả N mẫu đều phải được tính toán trong khi chúng ta chỉ giữ lại K giá trị còn lại (N-K) giá trị bị loại bỏ. • Việc mã hóa K giá trị sau khi giữ lại (với mục đích lưu trữ hoặc truyền đi) chúng ta lại phải thêm vào các bit tiêu đề, các bít sửa lỗi...... Tất cả các nhược điểm đó làm chậm tốc độ xử lý dữ liệu. Và điều này càng thể hiện rõ hơn trong trường hợp tín hiệu x với băng tần cao lại đòi hỏi tốc độ lấy mẫu phải rất lớn mới đảm bảo khôi phục lại dữ liệu (theo tiêu chuẩn Nyquist). 1.2 Phương pháp lấy mẫu nén Được đề xướng như một lý thuyết lẫy mẫu mới vào năm 2006 bởi Emmanuel Candès, Justin Romberg, và Terence Tao, phương pháp lấy mẫu nén cho phép thu trực tiếp tín hiệu dưới dạng nén mà không thông qua việc thu N mẫu tín hiệu rồi mới sử dụng các phương pháp nén như phương pháp thông thường. Với tín hiệu x chiều dài N, phương pháp lấy mẫu nén sử dụng M quá trình đo tuyến tính (M  N ) được biểu diễn bởi phép nhân giữa x và một tập hợp các vectơ {φj }M j=1 : yj =< x, φj > Tập hợp các phép đo yj được sắp xếp trong một vectơ Y chiều dài M × 1 và các vectơ φTj được sắp xếp như một hàng trong ma trận Φ kích thước M × N và do đó có thể được viết như sau: Y = ΦX = ΦΨs = Θs Quá trình đo ở đây là không thích nghi, tức là Φ là cố định và không phụ thuộc vào tín hiệu x. 5 1.3 Hai vấn đề chính trong lấy mẫu nén Mục tiêu của phương pháp lấy mẫu nén bây giờ là việc thiết kế và xây dựng: • Ma trận đo Φ ổn định có thể thu và lưu trữ các thông tin về tín hiệu ( tín hiệu thưa K hay tín hiệu có thể nén ) trong M phép đo (M  N ) mà vẫn đảm bảo khôi phục lại tín hiệu. • Thuật toán khôi phục tín hiệu có thể tái tạo tín hiệu x từ M phép đo y 6 Phần I Kỹ Thuật Lấy Mẫu Nén 2 Lý thuyết về lấy mẫu nén 2.1 Phương pháp lấy mẫu Phương pháp lấy mẫu truyền thống thường được biểu diễn bởi sơ đồ sau Hình 1: Phương pháp lẫy mẫu truyền thống Tín hiệu đầu vào x là một tín hiêu chiều dài N và thưa K (tín hiệu có thể nén) có thể được biểu diễn qua một tập hợp các vectơ cơ sở ψi : x= N X si ψi i=1 Do x là thưa K nên x có thể được biểu diễn bằng xấp xỉ của K trọng số lớn nhất: X x≈ si ψi K Việc thực hiện nén trong khối compress có thể thực hiện bằng một phương pháp nào đó như DCT rời rạc, Wavelet...Tín hiệu sau đó gồm K trọng số lớn nhất được mã hóa và truyền đi. Ở nơi thu từ K trọng số lớn nhất thu được người ta tái tạo lại tín hiệu sử dụng các phép biến đổi DCT ngược hoặc Wavelet ngược (do các phép biến đổi này là hoàn toàn thuận nghịch) Tuy nhiên do những nhược điểm như đã trình bày của nó, mà lý thuyết lấy mẫu nén được phát triển. 7 Hình 2: Phương pháp lẫy mẫu nén Phương pháp này sử dụng M các phép đo tuyến tính không thích nghi: Y = ΦX = ΦΨs = Θs Hình 3: Quá trình thu tín hiệu Y bằng M phép đo tuyến tính không thích nghi Trong đó Φ là ma trận kích thước M × N . Từ "không thích nghi" ở đây có nghĩa là ma trận Φ là cố định và không phụ thuộc tín hiệu đầu vào x. 8 2.2 Điều kiện để khôi phục được tín hiệu Vấn đề là chọn ma trận đo Φ thế nào để cho phép tái tạo lại tín hiệu x từ M phép đo (M 0 thì Θ cần thỏa mãn điều kiện sau đây: kΘvk2 1−≤ ≤1+ kvk2 Điều kiện này được gọi là điều kiện RIP (Restricted isometry property). Một điều kiện khác yêu cầu các hàng của ma trận Φ không được xuất hiện thưa thớt trong các cột của ma trận Ψ. Điều kiện này gọi là điều kiện tách biệt (Incoherence). Trong nghiên cứu của Emmanuel Candès, Justin Romberg, và Terence Tao đã chứng minh rằng: Với việc sử dụng ma trận Φ là ma trận ngẫu nhiên, phân bố Gaussian, thì cả điều kiện RIP và điều kiện tách biệt (incoherence) đều được thỏa mãn. Và với việc sử dụng số các phép đo tiến hành M ≥ cKlog(N/K) với c là một hằng số nhỏ thì hoàn toàn có thể tái tạo được tín hiệu x thưa K và có chiều dài N ban đầu Hình 4: Sử dụng ma trận ngẫu nhiên trong việc thu tín hiệu 2.3 Phương pháp khôi phục tín hiệu Với phương pháp lấy mẫu nén chúng ta đã thu được tín hiệu: Y = ΦX Bài toán ngược đặt ra là tìm lại tín hiệu X từ các giá trị Y. Dưới đây là 2 phương pháp phổ biến được dùng cho việc khôi phục tín hiệu cho lấy mẫu nén 9 2.3.1 Thuật toán khôi phục L1-minimization Chúng ta cần khôi phục lại X, tức là tìm lại chính xác các giá trị x[n], n = 1, 2....N , khi mà chúng ta có M phép đo Y . Tuy nhiên do M < N tức là số phương trình thiết lập được là nhỏ hơn số ẩn cần tìm, do đó sẽ có vô số các nghiệm thỏa mãn, và hiển nhiên nếu không cho thêm bất kỳ thông tin gì về nghiêm cần tìm chúng ta không thể biết nghiệm nào là đúng. Tuy nhiên trong trường hợp này, tín hiệu mà chúng ta cần khôi phục là đã biết về mặt cấu trúc tức nó là tín hiệu thưa K hay tín hiệu có thể nén. Về mặt toán học, dưới giả thiết tín hiệu X là thưa, chúng ta có thể khôi phục lại tín hiệu X bằng các phương pháp minimization. • Sử dụng L0 : x b = min kxkl0 x∈RN Với điều kiện: Y = ΦX Ở đây kxkl0 = |{i : xi 6= 0}|. Phương pháp này có thể cho phép khôi phục chính xác dữ liệu bằng cách kiểm tra từng dữ liệu để thỏa mãn 2 phương trình trên, tuy nhiên tốc độ tính toán của phương pháp là chậm. Nên thuật toán này ít được sử dụng trong thực tế và không sử dụng trong lấy mẫu nén. • Sử dụng L2 : x b = min kxkl2 = min x∈RN x∈RN N X |xi |2 i=1 Với điều kiện: Y = ΦX Phương pháp này không khôi phục đúng dữ liệu. • Sử dụng L1 : x b = min kxkl1 = min x∈RN x∈RN N X |xi | i=1 Với điều kiện: Y = ΦX Thuật toán này có thể khôi phục chính xác tín hiệu thưa K sử dụng M phép đo tuyến tính không thích nghi với M ≥ cKlog(N/K). Phương pháp này sử dụng trong lấy mẫu nén cho việc khôi phục dữ liệu. Nghiên cứu mới đây (tháng 9 năm 2007) của Emmanuel J.candès, Michael B.Walkin và Stephen P.Boyd đã cải tiến phương pháp này cho phép khôi phục tín hiệu chính xác hơn gọi là 10 phương pháp L1 minimization được trọng số hóa (Reweighted l1 minimization). Phương pháp này khôi phục tín hiệu bằng phương trình sau: x b = min kW xkl1 = min x∈RN N X x∈RN wi |xi | i=1 Với điều kiện: Y = Φx Ở đây ma trận W là ma trận chéo với w1 , w2 ...wn là các trọng số dương nằm trên đường chéo, các trọng số còn lại bằng 0. Các trọng số dương của ma trận W này được tính toán sử dụng các bước trong thuật toán sau đây: (0) • 1. Thiết đặt l=0 và wi , i = 1, ...., N • 2. Tính: x(l) = minkW (l) xkl1 với Y = Φx • 3. Cập nhật các giá trị trọng số: với i=1,......,n : (l+1) wi = 1 (l) |xi |+ • 4. Kết thúc thuật toán nếu w hội tụ hoặc khi l đạt tới một số cực đại, ngược lại tăng l lên 1 đơn vị và quay trở lại bước 2. Phương pháp này khôi phục tín hiệu chính xác hơn, để minh họa điều này ta xét ví dụ sau, T cho x = 0 1 0 (sơ đồ 1(a) thể hiện tín hiệu gốc x) và : Φ= 2 1 1 1 1 2 Ta có tín hiệu thu được: Y = Φx = 1 1 T Nhìn vào sơ đồ bên dưới, với phương pháp L1 minimization, l1 biểu thị như một quả bóng giao T với đường biểu diễn Y = Φx tại vị trí x b = 13 0 31 6= x giá trị này cho chúng ta kết quả không chính xác. Sơ đồ 1(b) T Bây giờ nếu chúng ta đưa vào ma trận trọng số W = diag( 3 1 3 ) sơ đồ 1(c)thể hiện quả bóng "weighted l1 " hội tụ tới điểm tín hiệu nguồn một cách chính xác. 11 Hình 5: So sánh phương pháp sử dụng l1 minimization và weighted l1 minimization 2.3.2 Thuật toán khôi phục OMP a) Thuật toán đuổi khớp (Matching pursuit) Nhiều phương pháp phân tích tín hiệu tìm cách biểu diễn 1 tín hiệu không biết x bằng một tổ hợp tuyến tính của các hàm số gn nào đó: x= N X an g n n=0 Chúng ta có thể nói rằng việc biểu diễn tín hiệu x tương tự như việc chọn các từ trong một quyển từ điển để tạo ra một câu văn có nghĩa nào đó. Trong trường hợp này là chúng ta chọn các hàm gn trong một tập hợp các hàm số để biểu diễn tín hiệu x. Các hệ số an được tính bởi: an =< x, gn > Chúng ta phải biểu diễn tín hiệu không biết x một cách chính xác nhất có thể bằng cách chọn các hàm gn một cách tối ưu từ một thư viện dư thừa các hàm D. Trong thực tế chúng ta chỉ có thể biểu diễn tín hiệu x một cách gần đúng: x≈ N X an g n n=1 Điều kiện để phép biểu diễn của chúng ta tối ưu là sai số giữa tín hiệu x thật và tín hiệu x biểu diễn gần đúng bằng các hàm gn là nhỏ nhất:  = kx − N X an gn k = min n=0 12 Để tìm được một sự kết hợp tuyến tính có thể của N hàm gn sao cho sai số là nhỏ nhất, chúng ta sử dụng thuật toán đuổi khớp (matching pursuit).  0  R x=x Rn x =< Rn x, gγn > gγn + Rn+1 x  gγn = argmaxgγn ∈D | < Rn x, gγx > | Bước đầu tiên thuật toán sẽ chọn gγ0 lớn nhất được cho bởi phép nhân trong (inner product) với tín hiệu x, trong mỗi bước gγn được khớp với tín hiệu Rn x. Cứ như vậy N hàm gn sẽ được tìm kiếm bằng thuật toán trên. b)Phương pháp khôi phục tín hiệu OMP trong lấy mẫu nén OMP là chữ viết tắt của phương pháp orthogonal matching pursuit, hay phương pháp "đuổi khớp trực giao". Nhắc lại rằng, chúng ta có tín hiệu X thưa K có chiều dài N , và M phép đo yi , i = 1, 2......M trong vectơ cột Y: Y = ΦX Với Φ là ma trận đo kích thước M × N . Do tín hiệu X là thưa K, tức là chỉ có K thành phần khác 0, các thành phần còn lại bằng 0. Như vậy, mỗi thành phần yi là sự kết hợp tuyến tính của K thành phần từ K cột của ma trận Φ. Do đó để khôi phục tín hiệu X dài N từ M thành phần của vectơ Y chúng ta cần tìm ra được 1 tổ hợp K cột trong ma trận Φ(có số cột là N) (N>M>K) để thỏa mãn: Y = ΦX Bài toán lại trở về giống như tìm các từ trong 1 quyển từ điển để ghép thành câu có nghĩa nào đó. Và chúng ta sử dụng thuật toán OMP (Orthogonal matching pursuit) để thực hiện điều này: ĐẦU VÀO: • Ma trận Φ • Vectơ dữ liệu nén Y • Độ thưa K của tín hiệu đầu vào x 1. Khởi tạo: r0 = y, t = 1 2. Tính toán cột it của ma trận Φ: it = argmaxi | < rt−1 , Φi > | 13 3. Tính: rt = y − Pt y Trong đó : Pt y = N X θc ik Φik k=1 θc ik là các trọng số được ước lượng của tín hiệu X. 4. Nếu t - Xem thêm -