Lấy mẫu nén (Compressed Sampling)

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 4 1.1 Các Phương pháp nén cổ điển và nhược điểm của chúng . . . . . . . . . . . . . 4 1.1.1 Tín hiệu thưa và có thể nén . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Các phương pháp nén cổ điển và nhược điểm . . . . . . . . . . . . . . . . 5 1.2 Phương pháp lấy mẫu nén . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Hai vấn đề chính trong lấy mẫu nén . . . . . . . . . . . . . . . . . . . . . . . . . 6 I Kỹ Thuật Lấy Mẫu Nén 7 2 Lý thuyết về lấy mẫu nén 7 2.1 Phương pháp lấy mẫu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Điều kiện để khôi phục được tín hiệu . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Phương pháp khôi phục tín hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3.1 Thuật toán khôi phục L1-minimization . . . . . . . . . . . . . . . . . . . 10 2.3.2 Thuật toán khôi phục OMP . . . . . . . . . . . . . . . . . . . . . . . . . 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ô phỏng lấy mẫu nén 19 4.1 Nén tín hiệu thưa trong miền thời gian . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Nén ảnh sử dụng CS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 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 23 5.1 Giới thiệu ngắn gọn về lý thuyết hỗn độn . . . . . . . . . . . . . . . . . . . . . . 23 5.1.1 Hỗn độn là gì? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.1.2 Một số hàm hỗn độn thông thường . . . . . . . . . . . . . . . . . . . . . 24 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) . . . . . . . . . . . . . . . . . . . 25 6 Thiết kế bộ lọc hỗn độn 28 6.1 Thiết kế bộ lọc hỗn độn và khôi phục tín hiệu dùng L1 minimization . . . . . . 28 6.1.1 Phương pháp lấy mẫu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.1.2 Phương pháp khôi phục tín hiệu . . . . . . . . . . . . . . . . . . . . . . . 30 6.2 Thiết kế bộ lọc hỗn độn và khôi phục tín hiệu dùng OMP . . . . . . . . . . . . 31 2 7 Mô phỏng 34 7.1 Mô phỏng kỹ thuật lấy mẫu nén sử dụng bộ lọc ngẫu nhiên . . . . . . . . . . . 35 7.2 Mô phỏng sử dụng bộ lọc hỗn độn với phương pháp khôi phục L1 minimization 35 7.3 Mô phỏng sử dụng bộ lọc hôn độn với phương pháp khôi phục OMP . . . . . . . 36 8 Kết Luận 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 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 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}Ni=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: x = N∑ i=1 siψi hoặc x = Ψ.s Ở đây s là vectơ cột N × 1 của các trọng số si == ψTi 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 = ΨTx Ψ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}Mj=1: yj = 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∑ i=1 siψi 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 ≈ ∑ K siψi 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<N) - tức là khôi phục x từ vectơ y. Do M<N cho nên bài toán sẽ không thể có duy nhất nghiệm. Tuy nhiên nếu x là tín hiệu thưa K và vị trí của K hệ số khác 0 này được biết trước thì bài toán trở thành giải hệ phương trình K ẩn với M phương trình (M ≥ K) và bài toán sẽ có duy nhất nghiệm. Một điều kiện cần và đủ cho vấn đề này là, cho vectơ v bất kỳ có K hệ số khác 0, với  > 0 thì Θ cần thỏa mãn điều kiện sau đây: 1−  ≤ ‖Θv‖2‖v‖2 ≤ 1 +  Đ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̂ = min x∈RN ‖x‖l0 Với điều kiện: Y = ΦX Ở đây ‖x‖l0 = |{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̂ = min x∈RN ‖x‖l2 = min x∈RN N∑ i=1 |xi|2 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̂ = min x∈RN ‖x‖l1 = min x∈RN N∑ i=1 |xi| 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̂ = min x∈RN ‖Wx‖l1 = min x∈RN N∑ i=1 wi|xi| 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: • 1. Thiết đặt l=0 và w(0)i , i = 1, ...., N • 2. Tính: x(l) = min‖W (l)x‖l1 với Y = Φx • 3. Cập nhật các giá trị trọng số: với i=1,......,n : w (l+1) i = 1 |x(l)i |+  • 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, cho x = 0 1 0 T (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 với đường biểu diễn Y = Φx tại vị trí x̂ = 1 3 0 1 3 T 6= x giá trị này cho chúng ta kết quả không chính xác. Sơ đồ 1(b) Bây giờ nếu chúng ta đưa vào ma trận trọng số W = diag( 3 1 3 T ) 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∑ n=0 angn 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 = 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∑ n=1 angn Đ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:  = ‖x− N∑ n=0 angn‖ = min 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). R0x = x Rnx = gγn +R n+1x gγn = argmaxgγn∈D| | 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 R nx. 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| | 13 3. Tính: rt = y − Pty Trong đó : Pty = N∑ k=1 θ̂ikΦik θ̂ik là các trọng số được ước lượng của tín hiệu X. 4. Nếu t<N tăng t lên 1 đơn vị và lặp lại bước 2, ngược lại kết thúc thuật toán. ĐẦU RA: • Tín hiệu khôi phục X̂ 14 3 Ứng dụng của lý thuyết lấy mẫu nén 3.1 Trong nén dữ liệu Thành tựu điển hình của lấy mẫu nén là việc thu các bức ảnh số với tốc độ lấy mẫu nhỏ trong một camera có duy nhất 1 sensor thu được gọi là CAMERA 1 ĐIỂM ẢNH (single pixel camera). Sơ đồ khối của Camera được cho như trong hình bên: Ở đây việc tạo ra một ma trận DMD bao gồm N mảnh gương rất nhỏ với hệ số phản xạ trên Hình 6: Camera số 1 điểm ảnh mỗi gương là ngẫu nhiên được điều khiển bởi bộ phát số ngẫu nhiên RNG (Random number generator) thay thế cho việc tạo ra ma trận Φ trong lý thuyết lấy mẫu nén mà Candès, Romberg và Tao đã đề cập. Toàn bộ bức ảnh đi qua một thấu kính thứ nhất và rơi vào ma trận gương DMD với hệ số phản xạ ngẫu nhiên, sau đó được hội tụ tại một điểm khi đi qua thấu kính thứ hai, tại điểm đó một photodiode được đặt thu nhận và lấy mẫu, do đó chỉ cần một photodiode và thực hiện M phép đo cần thiết chúng ta có thể khôi phục lại bức ảnh. Hình 7: Thực hiện M phép đo 15 Sơ đồ bố trí của Camera như trong hình: Hình 8: Sơ đồ bố trí Camera Và kết quả của nó: Hình 9: So sánh kết quả giữa ảnh nguồn và ảnh gốc 16 3.2 Trong truyền Thông Trong các ứng dụng truyền thông không dây ngày nay, việc tiết kiệm băng tần là một vấn đề rất quan trọng, đem lại hiệu quả về mặt kinh tế. Các hệ thống cảm nhận thông minh hiện nay cho phép cảm nhận môi trường phổ tần vô tuyến để phát hiện các khoảng phổ trống (Việc làm này dựa trên các mô hình ước lượng và nhận biết phổ), từ đó có thể nhanh chóng điều chỉnh các thông số truyền và nhận để có thể gửi tín hiệu vào trong các khoảng phổ trống đó. Cách làm này cho phép các nhà cung cấp dịch vụ tận dụng tối đa băng thông cho phép, phục vụ hiệu quả người sử dụng mà vẫn đảm bảo tránh gây nhiễu cho những người sử dụng ưu tiên. Đối với truyền thông băng thông rộng, thách thức lớn nhất đối với các mô hình ước lượng và nhận biết phổ là tần số lấy mẫu là quá lớn, nếu lấy mẫu không đủ sẽ không cung cấp đầy đủ thông tin về mặt thống kê cho các thuật toán khôi phục tín hiệu tuyến tính truyền thống. Tuy nhiên, do tính chất điển hình của các tín hiệu trong truyền thông không dây là thưa về mặt tần số. Nguyên nhân của tính chất này là do trong thực tế các kênh radio được sử dụng chiếm dụng phổ rất ít. Đây chính là tiền đề để có thể áp dụng kỹ thuật lấy mẫu nén (Compressed Sensing) trong mô hình nhận biết vô tuyến để có thể giảm tốc độ lấy mẫu xuống trong khi vẫn đảm bảo tính chính xác trong việc ước lượng các khoảng phổ trống. Một nghiên cứu của các tác giả Z.Tian, G.B.Giannakis cho thấy kết quả tốt khi áp dụng phương pháp lấy mẫu nén cho việc nhận biết phổ vô tuyến. Trong bài báo này, kỹ thuật lấy mẫu nén được sử dụng để khôi phục dải phổ từ mô hình lấy mẫu ngẫu nhiên - với số mẫu ít hơn so với tiêu chuẩn Nyquist - từ đó xác định vị trí của các dải tần bằng phương pháp xác định biên dựa trên kỹ thuật wavelet (wavelet based edge detector). Chúng ta có thể tóm lược phương pháp sử dụng lấy mẫu nén mà các tác giả đã trình bày trong việc ứng dụng cho nhận biết phổ vô tuyến như sau: Giả sử một mạng không dây băng rộng có dải tần tổng cộng là B Hz (từ f0 đến fN). Hàm mật độ phổ công suất (PSD) trên dải tần này được thể hiện trong hình: Hình 10: Mật độ phổ công suất trên dải tần tín hiệu Dải phổ này được thể hiện bằng tín hiệu liên tục r(t) (đây cũng chính là tín hiệu mà bộ 17 cảm nhận phổ vô tuyến (CR) phải cảm nhận). Giả sử khoảng thời gian cần thiết để CR cảm nhận là t ∈ [0,MT0]. Trong đó T0 là chu kỳ lấy mẫu theo Nyquist ⇒ cần tối thiểu M mẫu để khôi phục r(t) tức là chúng ta phải có một vectơ Γt kích thước M × 1 với các thành phần rt(n) = r(t)|t=nT0 . Đặt biến đổi Fourier M điểm của Γt là Γf : Γf = FMΓt, trong đó FM là ma trận biểu diễn biến đổi Fourier rời rạc M điểm. Nhiệm vụ của bài toán CR là xác định được Γf để từ đó xác định được các khoảng phổ trống, rồi điều chỉnh thông số và gửi tín hiệu vào trong khoảng phổ đó. Gọi F là tập hợp các khoảng phổ làm cho r(t) khác 0 trong miền tần số (trong trường hợp không có nhiễu). Do r(t) là thưa trong miền tần số nên |F |  B hay một cách tương đương khi rời rạc hóa, vectơ Γt có trung bình khoảng Kb = d|F |M/Be hệ số khác 0 và Kb  M . Kỹ thuật lấy mẫu nén cho phép khôi phục chính xác vectơ Γt từ một vectơ Υt có kích thước K × 1(Kb ≤ K ≤ M) : Υt = STc Γt, trong đó Sc là một ma trận đo có kích thước M × K (trường hợp đơn giản có thể lấy Sc là một ma trận lấy ngẫu nhiên K cột từ ma trận đơn vị). Như vậy, chúng ta có thể biểu diễn: Υt = (S T c FM)rf , và chúng ta có thể ước lượng rf dựa trên các phương pháp l1 minimization hoặc OMP: r̂t = argmin rf ‖rf‖1 , STc Γt = Υt 18 4 Mô phỏng lấy mẫu nén 4.1 Nén tín hiệu thưa trong miền thời gian Xét tín hiệu thưa x trong miền thời gian, chiều dài N = 512 thưa K = 20. Số các phép đo sử dụng M = 100. Sử dụng phương pháp L1 minimization cho việc khôi phục tín hiệu. Sơ đồ bên dưới trình bày kết quả mô phỏng: Hình 11: Kết quả mô phỏng 4.2 Nén ảnh sử dụng CS Như chúng ta đã biết, JPEG là một trong những chuẩn nén tốt sử dụng trong nén ảnh, tuy nhiên nếu bức ảnh JPEG là thưa, việc sử dụng phương pháp lấy mẫu nén vẫn có thể cho phép nén bức ảnh xuống nhiều lần. Xét bức ảnh: Hình 12: Ví dụ về bức ảnh JPEG thưa gồm 189280 điểm ảnh 19 Bức ảnh này phần lớn các điểm ảnh là màu đen, chỉ có số ít các điểm ảnh màu trắng biểu thị vòng tròn màu trắng. Nếu coi các điểm màu đen có giá trị là 0 và các điểm màu trắng có giá trị là 1, thì mỗi dòng trong bức ảnh gốc sẽ được coi như một tín hiệu thưa x(n), sử dụng phương pháp lấy mẫu nén áp dụng cho tất cả các dòng thưa này, chúng ta sẽ nén được toàn bộ bức ảnh xuống chỉ còn 33280 điểm ảnh. Tức là bức ảnh JPG giảm xuống chỉ còn 17.5% so với bức ảnh ban đầu. Việc khôi phục lại bức ảnh sử dụng thuật toán L1 minimization. Kết quả được thể hiện trong hình dưới: Hình 13: Kết quả mô phỏng việc nén ảnh JPEG bằng lấy mẫu nén 20 4.3 Nén tín hiệu thưa trong miền tần số Như trong lý thuyết xử lý tín hiệu mà chúng ta đã biết, một tín hiệu dạng sin/cos vô hạn về mặt thời gian thì nó được biểu diễn bởi 1 vạch phổ trong miền tần số. Vì vậy, để tạo ra một tín hiệu thưa trong miền tần số, chúng ta sử dụng kỹ thuật cộng gộp 5 tín hiệu dạng sin tại 5 tần số khác nhau trong miền thời gian, khi đó trong miền tần số tín hiệu được biểu diễn chỉ với 5 vạch phổ, khi đó tín hiệu gọi là thưa trong miền tần số. Dạng của tín hiệu trong miền thời gian và tần số được thể hiện trong sơ đồ bên dưới(trong mô phỏng sử dụng chiều dài là 512): (a) Dạng tín hiệu trong miền thời gian (b) Dạng tín hiệu trong miền tần số Hình 14: Tạo tín hiệu thưa trong miền tần số Sử dụng phương pháp lấy mẫu nén, chúng ta nhận được kết quả: 21 Hình 15: Nén tín hiệu thưa trong miền tần số Do trong mô phỏng sử dụng chiều dài tín hiệu là 512 chứ không phải ∞ nên tín hiệu trong miền tần số có dạng không hoàn hảo là các vạch như mong muốn, do đó kết quả tín hiệu khôi phục trong miền thời gian chỉ gần giống với tín hiệu gốc. Để hạn chế điều này chúng ta có thể tăng chiều dài của tín hiệu trong miền thời gian, nhưng việc làm này không thực sự quan trọng nên chúng ta vẫn sử dụng chiều dài 512 trong mô phỏng của mình. 22 Phần 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) 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ì? Ngay từ thời cổ xưa, các nhà thiên văn cổ đại đã cố gắng dự đoán sự di chuyển của mặt trăng xung quanh trái đất, và sự di chuyển của các hành tinh trong hệ mặt trời, chúng là các hệ thống động. Việc hiểu biết về điều này là rất quan trọng trong việc xác định tọa độ cho các con thuyền khi chúng di chuyển trên biển. Bảng Kepler và 3 định luật kepler ra đời là một phát kiến lớn cho vấn đề này. Các hệ thống động tồn tại rất phổ biến trong tự nhiên, và khác với một hệ thống ngẫu nhiên, hệ thống động có trạng thái hoàn toàn xác định được với các điều kiện khởi tạo ban đầu thích hợp, bởi vì một hệ thống động sẽ được đặc trưng bởi một hàm số biết trước nào đó. Một hệ thống động với các điều kiện khởi tạo ban đầu thích hợp sẽ dễ dàng đánh lừa chúng ta rằng nó là hệ thống ngẫu nhiên khi kết quả của nó rất giống ngẫu nhiên. Đó chính là Chaos (hỗn độn). Vậy một hệ thống gọi là hệ thống hỗn độn(hay hệ thống động) nếu thỏa mãn cả 2 điều kiện sau: • Hàm số đặc trưng cho hệ thống là hoàn toàn xác định. • Gía trị theo thời gian (hoặc không gian) của hệ thống phải rất gần với ngẫu nhiên. Chúng ta xét một ví dụ đơn giản sau để có thể so sánh, cho chuỗi x được tạo bởi lệnh tạo số ngẫu nhiên: x = rand(1, 30). Và một chuỗi y được tạo bởi hàm số sau: y(n+ 1) = cy(n)(1− y(n)) + y(n) Với các giá trị khởi tạo : c=3, y(0)=0.5. Hình 6 biểu diễn kết quả của hai chuỗi số, chúng ta thấy được với các điều kiện khởi đầu như trên chuỗi tạo bởi phương trình trên cho kết quả giống như ngẫu nhiên. 23 Hình 16: Sự giống nhau giữa giá trị tạo bởi hàm chaos và giá trị ngẫu nhiên Thực tế, trong truyền thông chúng ta cũng gặp một ứng dụng của chaos dưới một cái tên khác là chuỗi giả ngẫu nhiên (Preudorandom). Để gửi một bản tin qua một đường truyền viễn thông, bản tin được chuyển đổi thành tín hiệu số (được biểu diễn bởi hai bit 0 và 1). Để bảo mật cho bản tin, người ta cộng nhị phân bản tin ở dạng số với một chuỗi giả ngẫu nhiên được tạo bởi một hàm hỗn độn thông qua phép XOR: 0⊕ 0 = 0 0⊕ 1 = 1 1⊕ 0 = 1 1⊕ 1 = 0 Ở nơi thu đã biết chuỗi giả ngẫu nhiên thông qua hàm hỗn độn, do đó chỉ cần đồng bộ lại và thực hiện phép XOR lại với chuỗi giả ngẫu nhiên tạo bởi hàm hỗn độn, toàn bộ bản tin sẽ được khôi phục. 5.1.2 Một số hàm hỗn độn thông thường Hiện nay số lượng các hàm hỗn độn ứng dụng trong các lĩnh vực khoa học là rất nhiều, ở đây tôi chỉ nêu ra một số hàm hỗn độn tôi sử dụng trong nghiên cứu này: 1) xn+1 = axn(1− xn) a = 4, x0 = 0.5 2) { xn+1 = 1− ax2n + byn yn+1 = xn 24 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) Trong kết quả bài báo của Candès, Romberg, Tao and Donoho phép đo tuyến tính ngẫu nhiên không thích nghi (Random linear projection) được sử dụng cho việc thu trực tiếp tín hiệu thưa x, tuy nhiên nếu như vậy thì phương pháp lấy mẫu nén khó có thể triển khai các ứng dụng thực tế bởi các phép đo như vậy yêu cầu thu toàn bộ tín hiệu tại một thời điểm, nếu tín hiệu là dài thì điều này gây ra nhiều khó khăn. Hơn nữa, chỉ dừng lại ở phép nhân ma trận thì rất khó có thể triển khai cụ thể ứng dụng lấy mẫu tín hiệu thời gian thực. Sử dụng bộ lọc ngẫu nhiên là một kỹ thuật lấy mẫu tín hiệu trong phương pháp lấy mẫu nén được công bố bởi Joel A.Tropp, Michael B.Wakin, Marco F.Duarte, Dror Baron và Richard G.Baraniuk. Trong phương pháp này các tác giả đã thay thế việc sử dụng phép đo tuyến tính ngẫu nhiên (dưới dạng một ma trận) bằng một bộ lọc FIR với hệ số ngẫu nhiên cho việc thu tín hiệu. Sơ đồ bên dưới trình bày kỹ thuật này: Hình 17: Sử dụng bộ lọc ngẫu nhiên trong lấy mẫu nén Trong kỹ thuật này tín hiệu s được nhân chập với một bộ lọc FIR hệ số ngẫu nhiên h và sau đó hạ tốc tín hiệu sau bộ lọc để thu được tín hiệu y dưới dạng nén. s là tín hiệu có chiều dài d, h là bộ lọc FIR hệ số ngẫu nhiên chiều dài B. Tín hiệu y được tính toán: y = Dowsample↓ d N (h ∗ s) Phép nhân chập này có thể tiến hành trong miền thời gian: y(n) = B−1∑ j=0 s(n[ d N ] + j)h(B − j) với n = 0, 1......N − 1 25 Hoặc tiến hành trong miền tần số: y = Downsample↓ d N z−1{H(w)S(w)} Do quá trình là tuyến tính nên việc chuyển từ tín hiệu thưa s sang thành tín hiệu nén y có thể được mô tả bằng: y = Φs Ở đây Φ là ma trận N × d: mỗi hàng có B phần tử khác 0 và mỗi hàng của φ là một bản sao của hàng phía trên nó được dịch sang bên phải d N vị trí. Việc tái tạo ma trận Φ là cần thiết cho việc khôi phục tín hiệu, do kỹ thuật này sử dụng phương pháp khôi phục OMP(orthogonal matching pursuit) để khôi phục tín hiệu. OMP yêu cầu hai tham số đầu vào cho thuật toán: Ma trận đo Φ được tái dựng lại và dữ liệu nén y (trong Chaos filter chúng ta cũng sẽ dùng kỹ thuật này do đó kỹ thuật này sẽ được mô tả kỹ hơn trong phần Chaos filter). Tuy nhiên chúng ta phân tích sơ đồ sau đây: Hình 18: Nén và giải nén Compressive Sensing giữa nơi phát và nơi thu Gỉa thiết khối project ở nơi phát được thay bằng bộ lọc ngẫu nhiên, khối reconstruct ở nơi thu sử dụng thuật toán OMP cho việc khôi phục tín hiệu và như vậy nó yêu cầu việc tái tạo lại ma trận đo Φ. Không may thay, bộ lọc ngẫu nhiên được tạo ra ở khối project với các hệ số là ngẫu nhiên, do đó nơi thu không thể xác định được các hệ số đó cho việc tái tạo lại ma trận đo Φ. Vì vậy vấn đề đặt ra ở đây là thiết kế khối project bằng một bộ lọc sao cho thỏa mãn yêu cầu: hệ số của bộ lọc hoàn toàn xác định được, thống nhất giữa nơi phát và nơi thu và các hệ số phải là ngẫu nhiên (tuân theo lý thuyết của Candès, Romberg và Baraniuk) Và do đó, chúng ta lựa chọn bộ lọc hỗn độn(Chaos filter) cho việc giải quyết các vấn đề trên. Với đặc điểm của Chaos fitler: Hệ số của bộ lọc hoàn toàn xác định được và những hệ số đó gần giống ngẫu nhiên là một giải pháp hiệu quả trong lấy mẫu nén. 26 Trong nghiên cứu của mình, tôi thực hiện việc triển khai bộ lọc hỗn độn theo hai hướng khác nhau sử dụng hai phương pháp khôi phục dữ liệu khác nhau là L1 minimization và OMP(Orthogonal Maching Pursuit). 27 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 hiệu dùng L1 mini- mization 6.1.1 Phương pháp lấy mẫu Giả Thiết • Cho tín hiệu x(n) thưa K, chiều dài N • Số các phép đo ngẫu nhiên cần thiết là M ≥ K log(N K ) • Ma trận đo ΦMN kích thước M ×N • Tín hiệu đầu ra y(n) có chiều dài M Sơ đồ của các phép đo tuyến tính ngẫu nhiên không thích nghi trong lấy mẫu nén: Dạng của Hình 19: Các phép đo tuyến tính ngẫu nhiên ma trận Φ được cho như sau: Φ = a11 a12 . . . a1N a21 a22 . . . a2N ... ... ... ... aM1 aM2 . . . aMN Chúng ta sắp xếp M hàng của ma trận ΦMN thành một chuỗi có chiều dài M ×N : 28 Hình 20: Chuyển ma trận ΦMN thành 1 chuỗi Khi đó phép nhân ma trận trong Hình 9 có thể được biểu diễn lại như sau: Để tính y(1) chúng ta nhân các cột tương ứng rồi cộng các kết quả lại. Để tính y(2), y(3), ....y(M) chúng ta làm tương tự như hình dưới: (a) Tính y(1) (b) Tính y(2) (c) Tính y(3) (d) Tính y(M) Hình 21: Các phép tính toán trên chuỗi thay cho phép nhân ma trận Nếu chúng ta coi chuỗi được tạo thành là chuỗi các hệ số của bộ lọc hàm truyền h(n), thì toàn bộ quá trình trên hoàn toàn được thay thế bằng sơ đồ: Hình 22: Các phép tính trên chuỗi được đưa về phép nhân chập với bộ lọc Với tín hiệu x(n) chiều dài N, hàm truyền h(n) có chiều dài M ×N , đầu ra p(n) của bộ lọc có chiều dài M × N + N − 1, để thu được chuỗi dữ liệu nén y(n) chiều dài M, chúng ta phải hạ tốc tín hiệu p(n) ra khỏi bộ lọc với hệ số hạ tốc là (M ×N +N − 1)/M . 29 Như vậy các phép đo ngẫu nhiên tuyến tính mà các tác giả Candès, Romberg, Tao mô tả dưới dạng một phép nhân ma trận ngẫu nhiên đã được chuyển đổi hoàn toàn thành phép nhân chập với một bộ lọc và thực hiện Downsample (hạ tốc). Do các hệ số của bộ lọc được tạo thành bởi sự "ghép nối" các hàng của ma trận ngẫu nhiên, nên các hệ số của bộ lọc là ngẫu nhiên. Tuy nhiên, như đã trình bày trước, chúng ta sử dụng các hàm hỗn độn cho việc tạo ra các hệ số này thay vì dùng phép tạo ngẫu nhiên. Trong nghiên cứu của mình tôi sử dụng hàm: h(n+ 1) = C.h(n)(1− h(n)) + h(n) với : C = 3, h(0) = 0.5 6.1.2 Phương pháp khôi phục tín hiệu Chúng ta khôi phục tín hiệu bằng thuật toán L1-minimization. Thuật toán này yêu cầu: Đầu vào: • Ma trận đo Φ: ma trận này sẽ được tái tạo lại từ hàm truyền h(n) của bộ lọc. • Tín hiệu nén y(n) chiều dài M. Đầu ra: Tín hiệu ước lượng x̂(n) Việc tái tạo ma trận đo Φ từ hàm truyền h(n) có độ dài M ×N bằng cách cắt h(n) thành M đoạn có chiều dài N và sắp xếp lại thành ma trận kích thước M ×N . Minh họa như trong hình: Hình 23: Hàm truyền h(n) của bộ lọc Hình 24: Ma trận đo Φ 30 Từ ma trận Φ tái tạo được, chúng ta dễ dàng khôi phục tín hiệu x̂(n) sử dụng thuật toán L1 minimization như đã trình bày trong phần 2.3.1 Tuy nhiên phương pháp này có nhược điểm là chiều dài bộ lọc là lớn, lớn hơn rất nhiều lần chiều dài của tín hiệu(Chiều dài của tín hiệu là N thì chiều dài của bộ lọc là M ×N tức là gấp M lần). 6.2 Thiết kế bộ lọc hỗn độn và khôi phục tín hiệu dùng OMP Chúng ta vẫn sử dụng bộ lọc hỗn độn như một phương pháp mới cho vấn đề lấy mẫu nén, với sơ đồ như hình vẽ: Hình 25: Sử dụng Chaos filter cho Compressive Sensing Gỉa thiết: • Cho tín hiệu vào x(n) chiều dài N , thưa K • Bộ lọc hỗn độn với hàm truyền h(n) có chiều dài B < N . • Tín hiệu lấy mẫu nén y(n) có chiều dài M. Tín hiệu p(n) ra khỏi bộ lọc có chiều dài B+N − 1 được tạo bởi phép nhân chập giữa x(n) và h(n): p(n) = ∞∑ k=0 x(k)h(n− k) Để tạo ra tín hiệu lấy mẫu nén y(n) chiều dài M, chúng ta thực hiện giảm tốc tín hiệu p(n) với hệ số giảm tốc là B+N−1 M : y(n) = Downsample↓B+N−1 M {p(n)} Việc thực hiện toàn bộ quá trình trên có thể phân tích chi tiết bằng sơ đồ: Phép nhân chập: 31 (a) Tính p(0) (b) Tính p(1) (c) Tính p(2) (d) Tính p(3) (e) Tính p(4) (f) Tính p(5) (g) Tính p(M + N − 1) Hình 26: Quá trình thực hiện nhân chập với bộ lọc hỗn độn Quá trình này lại có thể được thay thế bằng phép nhân giữa tín hiệu x(n) với một ma trận A kích thước (B +N − 1)×N . Ma trận A được tạo bởi hàm truyền h(n) của bộ lọc hỗn độn. Hàng đầu tiên của ma trận A có phần tử đầu tiên là h(B), các phần tử còn lại bằng 0. Hàng thứ hai được tạo bằng cách dịch hàm truyền h(n) của bộ lọc sang phải một vị trí so với hàng thứ nhất. Cứ như vậy các hàng phía dưới được tạo bằng cách dịch h(n) sang phải một vị trí so với hàng liền kề phía trên nó. Khi đó phép nhân chập sẽ hoàn toàn tương đương với việc thay thế bởi phép nhân ma trận A với tín hiệu x(n). 32 Hình 27: Phép nhân chập được chuyển đổi thành phép nhân ma trận Tiếp tục thực hiện giảm tốc tín hiệu p(n) thu được với hệ số giảm tốc λ = B+N−1 M để thu được tín hiệu nén y(n) có chiều dài M: y(n) = Downsample↓λ{p(n)} = p(nλ) với n = 0, 1....M Hình 28: Kết quả tạo thành từ việc giảm tốc tín hiệu p(n) Tương đương với việc tạo thành tín hiệu y(n) từ việc giảm tốc, M hàng tương ứng của ma trận A cũng được tách ra tạo thành ma trận Φ. Do đó có thể viết được: Y = ΦX 33 Kết quả chúng ta lại thu được vectơ đo Y và tái tạo được ma trận đo Φ từ hàm truyền h(n) của bộ lọc hỗn độn. Do đó sử dụng 2 tham số đầu vào này ( vectơ Y và ma trận Φ ) cho thuật toán khôi phục tín hiệu OMP chúng ta sẽ khôi phục được tín hiệu x̂(n). Xét trong một hệ thống truyền tin giữa nơi gửi và nơi nhân, do hàm truyền của bộ lọc hỗn độn là hoàn toàn biết trước nên nơi dễ dàng khôi phục lại Φ, do đó việc truyền tín hiệu giữa nơi phát và nơi thu chỉ cần gửi duy nhất vectơ Y . 7 Mô phỏng Trong tất cả các phương pháp mô phỏng, chúng ta sử dụng một tín hiệu x(n) chiều dài 512 độ thưa 20 được tạo ra một cách ngẫu nhiên. N = 512; T = 20; K = 90; x = zeros(N,1); q = randperm(N); x(q(1:T)) = sign(randn(T,1)); Hình 29: Tín hiệu thưa x(n) 34 7.1 Mô phỏng kỹ thuật lấy mẫu nén sử dụng bộ lọc ngẫu nhiên Với phương pháp sử dụng bộ lọc ngẫu nhiên của Joel A.Tropp, Michael B.Wakin. Hàm truyền của bộ lọc được tạo ra ngẫu nhiên. H=rand(1,M); với M là chiều dài của bộ lọc. Sau khi thực hiện nhân chập tín hiệu x(n) với hàm truyền h(n) chúng ta thực hiện việc giảm tốc và khôi phục tín hiệu sử dụng phương pháp OMP. Sơ đồ bên dưới cho thấy kết quả mô phỏng với hàm truyền h(n) chiều dài M = 100 Hình 30: Kết quả mô phỏng với random filter 7.2 Mô phỏng sử dụng bộ lọc hỗn độn với phương pháp khôi phục L1 minimization Phương pháp này chúng ta sử dụng hàm Chaos: h(n+ 1) = C.h(n)(1− h(n) + h(n) với C = 3, h(0) = 0.5 Để tạo ra hàm truyền h(n) có chiều dài M ∗N , do đó 2 tham số đầu vào cho hàm Chaos là M và N . h=chaos(M,N); Nhân chập tín hiệu x(n) với hàm truyền h(n),sau đó giảm tốc. Việc khôi phục tín hiệu được thực hiện bởi L1-minimization, bước đầu tiên của quá trình này là tái tạo lại ma trận đo Φ bằng cách cắt hàm truyền h(n) thành M đoạn chiều dài N sau đó ghép lại tạo thành ma trận đo Φ, bước thứ 2 đưa các tham số đầu vào vào thuật toán L1-minimization để khôi phục lại tín hiệu. Kết quả mô phỏng trong sơ đồ bên dưới. 35 Hình 31: Kết quả mô phỏng sử dụng bộ lọc hỗn độn và khôi phục bằng L1-minimization 7.3 Mô phỏng sử dụng bộ lọc hôn độn với phương pháp khôi phục OMP Với phương pháp khôi phục sử dụng OMP, hàm hỗn độn chúng ta cần duy nhất một tham số đầu vào là chiều dài của bộ lọc. h=chaos(M); Và tiếp tục sử dụng hàm chaos: h(n+ 1) = C.h(n)(1− h(n)) + h(n) với C = 3, h(0) = 0.5 Sau khi tiến hành nhân chập, giảm tốc đồng thời với việc tái tạo ma trận đo Φ làm đầu vào cho thuật toán OMP. Chúng ta thu được kết quả mô phỏng. Hình 32: Kết quả mô phỏng sử dụng bộ lọc hỗn độn và khôi phục bằng L1-minimization 36 8 Kết Luận Lấy mẫu nén(Compressed Sensing), một lĩnh vực mới được phát triển trong 2 năm trở lại đây nhưng đã thể hiện được những ưu điểm vượt trội của nó. Vượt qua tiêu chuẩn lấy mẫu Nyquist/Shanon nó cho phép lấy mẫu ở tốc độ thấp hơn nhiều(tùy từng loại tín hiệu). Lấy mẫu nénthực sự là một giải pháp hiệu quả trong thời đại ngày nay khi mà các tài nguyên như băng tần (bandwidth) ngày càng hạn hẹp do được sử dụng cho nhiều mục đích khác nhau trong dân sự, quốc phòng, an ninh. Với tốc độ lấy mẫu thấp nó còn cho phép giảm giá thành chế tạo đối với các thiết bị như ADC/DAC, đơn giản hóa trong việc chế tạo các thiết bị thu tín hiệu. Phần đầu của khóa luận đã trình bày tổng quan về phương pháp lấy mẫu nén và giới thiệu một số ứng dụng của nó. Phần thứ hai triển khai nghiên cứu thiết kế bộ lọc hỗn độn (chaos filters) nhằm thay thế bộ lọc ngẫu nhiên (random filters) trong phương pháp lấy mẫu nén. Kết quả nghiên cứu này đã được gửi đăng trong tạp chí quốc tế sau đây: Nguyen Linh-Trung, Dinh Van Phong, Zahir M. Hussain, and Huynh Huu Tue, “Compressed sensing using chaos filters”, IET Electronics Letters, submitted May 26, 2008. Lý thuyết lấy mẫu nén đang được tiếp tục phát triển và hoàn thiện trong các kỹ thuật lấy mẫu mới. Việc áp dụng lấy mẫu nén trong các ứng dụng thực tế, nơi mà các tín hiệu thưa là nhiều(do đó việc lấy mẫu với tốc độ Nyquist là dư thừa và không cân thiết) như MRI, xử lý ảnh...cũng đang được tiếp tục phát triển hứa hẹn những kết quả khả quan trong tương lai. 37 Tài liệu [1] J. A.TROPP and A. C.GILBERT, “signal recovery from random measurements via orthog- onal matching pursuit,” 2006. [2] S. P. Emmanuel J. Candès, Michael B.Wakin, “Enhancing sparsity by reweighted l1 mini- mization,” Nov 2007. [3] R. G.Baraniuk, “Compressive sensing,” IEEE signal processing magazine, pp. 118–124, July 2007. [4] M. F. D. B. Joel A.Tropp, Michael B.Wakin and R. G.Braniuk, “Random filters for com- pressive sampling and recontruction,” Proc.Int.Conf.Acoustics, Speech, Signal Processing, May 2006. [5] D. D. Michael Lustig and J. M.Pauly, “Sparse mri: The application of compressed sensing for rapid mr imaging,” Magnetic Resonance in Medicine, vol. 58, pp. 1182–1195, 2007. [6] D. NEEDELL and R. VERSHYNIN, “Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit,” July 23 2007. [7] L. O.CHUA and T. LIN, “Chaos in digital filters,” IEEE transactions on circuit and systems, vol. 35, pp. 648–658, June 1988. [8] P. T.Boufounos and R. G.Baraniuk, “Recontructing sparse signals from their zero crossings,” 2007. [9] Z. Tian and G. B. Giannakis, “Compressed sensing for wideband cognitive radios,” IEEE, 2007. 38