Tài liệu Tìm hiểu, nghiên cứu và ứng dụng vài thuật toán nén tiếng nói

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN NHƢ HIỀN TÌM HIỂU, NGHIÊN CỨU VÀ ỨNG DỤNG MỘT SỐ THUẬT TOÁN NÉN TIẾNG NÓI LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2013 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN NHƢ HIỀN TÌM HIỂU, NGHIÊN CỨU VÀ ỨNG DỤNG MỘT SỐ THUẬT TOÁN NÉN TIẾNG NÓI Ngành : Công nghệ Thông tin Chuyên ngành : Hệ thống Thông tin Mã số : 60 48 05 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS. TS Nguyễn Văn Xuất Hà Nội – 2013 LỜI CAM ĐOAN Với mục đích học tập, nghiên cứu để nâng cao kiến thức và trình độ chuyên môn nên tôi đã làm luận văn này một cách nghiêm túc và hoàn toàn trung thực. Trong luận văn, tôi có sử dụng một số tài liệu tham khảo của một số tác giả. Tôi đã nêu ra trong phần tài liệu tham khảo ở cuối luận văn. Tôi xin cam đoan và chịu trách nhiệm về nội dung và sự trung thực trong luận văn tốt nghiệp Thạc sĩ của mình! Học viên: Nguyễn Như Hiền 1 MỤC LỤC LỜI CAM ĐOAN ..........................................................................................................1 MỤC LỤC ...................................................................................................................... 2 DANH MỤC CÁC BẢNG............................................................................................. 4 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ......................................................................5 MỞ ĐẦU ......................................................................................................................... 6 CHƢƠNG 1. CƠ SỞ TOÁN HỌC CỦA LUẬN VĂN ...............................................7 1.1. Nén dữ liệu ...........................................................................................................7 1.1.1. Khái niệm, định nghĩa.....................................................................................7 1.1.2. Phân loại nén dữ liệu ...................................................................................... 7 1.2. Điểm cắt Zero (Zero Crossing) ..........................................................................8 1.2.1. Khái niệm và định nghĩa .................................................................................8 1.2.2. Trích chọn đặc trưng dựa vào điểm cắt Zero .................................................8 1.2.3. Thuật toán lấy điểm cắt Zero ..........................................................................9 1.3. Phép biến đổi Cosin ........................................................................................... 11 1.3.1. Khái niệm và định nghĩa ...............................................................................11 1.3.2. Thuật toán Cosin và nén dữ liệu ...................................................................15 1.4. Phép biến đổi Wavelet Haar ............................................................................17 1.4.1. Phép biến đổi Wavelet liên tục (Continuous Wavelet Transform - CWT) ....19 1.4.2. Phép biến đổi Wavelet rời rạc (Discrete Wavelet Transform - DWT) .........21 1.4.3. Thuật toán Wavelet Haar và nén dữ liệu ...................................................... 22 1.5. Hệ số tƣơng quan của các đại lƣợng ngẫu nhiên ...........................................26 1.5.1. Khái niệm và định nghĩa ...............................................................................26 1.5.2. Ý nghĩa của hệ số tương quan ......................................................................27 CHƢƠNG 2. ÂM THANH, TIẾNG NÓI VÀ NHẬN DẠNG TIẾNG NÓI ...........30 2.1. Âm thanh và tiếng nói ....................................................................................... 30 2.1.1. Khái niệm về âm thanh .................................................................................30 2.1.2. Tiếng nói, các đặc tính cơ bản của tiếng nói ................................................30 2.2. Tổng quan về nhận dạng tiếng nói ..................................................................30 2.2.1. Nhận dạng tiếng nói...................................................................................... 30 2.2.2. Phân loại các bài toán nhận dạng tiếng nói .................................................31 2 2.2.3. Quá trình nhận dạng tiếng nói......................................................................31 2.2.4. Một số hệ thống nhận dạng tiếng nói trên thị trường...................................33 CHƢƠNG 3. SỐ HÓA ÂM THANH .........................................................................35 3.1. Âm thanh số .......................................................................................................35 3.1.1. Một số khái niệm và định nghĩa ....................................................................35 3.1.2. Số hóa âm thanh ........................................................................................... 36 3.2. File WAVE .........................................................................................................37 3.2.1. Cấu trúc file Wave ........................................................................................ 37 3.2.2. Đọc, ghi file Wave......................................................................................... 41 3.3. Nhiễu và khử nhiễu ........................................................................................... 43 3.3.1. Nhiễu .............................................................................................................43 3.3.2. Khử nhiễu ......................................................................................................43 CHƢƠNG 4. XÂY DỰNG ỨNG DỤNG NHẬN DẠNG TIẾNG NÓI ...................47 4.1. Xây dựng ứng dụng thử nghiệm ......................................................................47 4.1.1. Bài toán nhận dạng tiếng nói........................................................................47 4.1.2. Mô tả bài toán nhận dạng từ đơn “Có” và “Không” ..................................47 4.2. Tổ chức, chuẩn hóa dữ liệu ..............................................................................49 4.3. Học mẫu .............................................................................................................49 4.4. Đối sánh đặc trƣng và đánh giá kết quả ......................................................... 49 4.4.1. Thuật toán đối sánh theo hệ số tương quan .................................................49 4.4.2. Thuật toán đối sánh qua phép biến đổi Cosin DCT .....................................53 4.4.3. Thuật toán đối sánh qua phép biến đổi Wavelet Haar .................................55 4.5. Mô tả chƣơng trình ứng dụng ..........................................................................55 4.6 Kết quả thử nghiệm ........................................................................................... 57 KẾT LUẬN ..................................................................................................................60 TÀI LIỆU THAM KHẢO........................................................................................... 61 3 DANH MỤC CÁC BẢNG Bảng 1.1: Trọng lượng và vòng eo của 15 đối tượng .................................................... 27 Bảng 1.2: Các cặp giá trị (Xi, Yi) với n học sinh trong một trường............................... 28 Bảng 1.3: Số phần tử của mẫu n = 15............................................................................28 Bảng 3.1: Dạng tệp tin cơ bản ....................................................................................... 38 Bảng 3.2: Một dạng chuẩn của file Wave .....................................................................39 Bảng 3.3: Khuôn dạng khúc fmt sử dụng cho dữ liệu PCM: ........................................42 Bảng 4.1: Bảng số lượng mẫu thu thập hai từ “Có” và “Không” .................................57 Bảng 4.2: Bảng số lượng mẫu hai từ “Có” và “Không” lưu đặc trưng vào cơ sở dữ liệu .......................................................................................................................................58 Bảng 4.3: Kết quả thử nghiệm chương trình với từ “Có” .............................................58 Bảng 4.4: Kết quả thử nghiệm chương trình với từ “Không” .......................................58 4 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1: Điểm cắt Zero biểu thị tương quan giữa điện áp và thời gian ......................... 8 Hình 1.2: Mô tả cách biểu diễn đoạn tín hiệu giữa hai điểm cắt zero qua tam giác ABC .........................................................................................................................................9 Hình 1.3: Sơ đồ mô tả thuật toán xác định tệp f1.txt chứa các bộ ba {x,y,z} ...............10 Hình 1.4: Ví dụ phép biến đổi DCT một chiều ............................................................. 17 Hình 1.5: Biến đổi Wavelet ........................................................................................... 18 Hình 1.6: Mô tả các miền biến đổi của tín hiệu ............................................................ 18 Hình 1.7: Sóng sin và wavelet ....................................................................................... 18 Hình 1.8: Các thành phần wavelet tương ứng với các tỉ lệ và vị trí khác nhau ............20 Hình 1.9: Biến đổi wavelet rời rạc của tín hiệu ............................................................. 21 Hình 1.10: Hàm Wavelet ψ(t) và hàm tỉ lệ Haar φ(t) cơ bản ........................................23 Hình 1.11: Tính toán chuẩn hóa biến đổi wavelet ......................................................... 25 Hình 1.12: Khôi phục lại từ một biến đổi wavelet đã được chuẩn hóa ......................... 26 Hình 1.13: Đồ thị tương quan giữa vòng eo và cân nặng của 15 đối tượng..................29 Hình 2.1: Cấu trúc tổng quát của một hệ thống nhận dạng tiếng nói ............................ 32 Hình 3.1: Quá trình số hóa âm thanh .............................................................................35 Hình 3.2: Nguyên lý số hóa âm thanh ...........................................................................36 Hình 3.3: Khuôn dạng tệp Wave ...................................................................................37 Hình 3.4: Cấu trúc file wave.......................................................................................... 39 Hình 3.5: Phần diễn dịch ............................................................................................... 41 Hình 3.6: Sơ đồ khối thuật toán lọc nhiễu sử dụng hàm năng lượng thấp .................... 44 Hình 3.7: Dạng sóng của từ “Không” khi đọc qua mic (đã lọc năng lượng thấp) ........45 Hình 3.8: Dạng sóng của từ “Không” ở trên sau khi lọc nhiễu dựa vào năng lượng tập trung. .............................................................................................................................. 45 Hình 3.9: Sơ đồ khối thuật toán lọc nhiễu sử dụng năng lượng tập trung .................... 46 Hình 4.1: Sơ đồ khối hệ thống nhận dạng từ đơn “Có” và “Không” ............................ 48 Hình 4.2: Xét sự tương quan giữa 2 dãy .......................................................................51 Hình 4.3: Sơ đồ khối thuật toán đối sánh theo hệ số tương quan ..................................52 Hình 4.4: Sơ đồ khối thuật toán đối sánh theo phép biến đổi Cosin DCT .................... 54 Hình 4.5: Giao diện chính của chương trình .................................................................55 5 MỞ ĐẦU Tiếng nói là một phương tiện trao đổi thông tin tiện ích vốn có của còn người. Ước mơ về những “máy nói”, “máy hiểu tiếng nói” đã không chỉ xuất hiện từ những câu truyện khoa học viễn tưởng xa xưa mà còn là động lực thôi thúc của nhiều chuyên gia nghiên cứu trên thế giới. Hiện nay, nhiều thành tựu tiên tiến đã được đưa vào ứng dụng trong cuộc sống. Tuy vậy, việc có được một “máy nói” mang tính tự nhiên (về giọng điệu, phát âm, …) cũng như một “máy hiểu tiếng nói” thực sự cho đến nay vẫn còn xa với mong muốn và yêu cầu thực tế của con người. Cùng với xu thế phát triển của khoa học công nghệ ngày càng thúc đẩy việc hoàn thiện hơn nữa công nghệ để có thể đạt được mục tiêu của con người về lĩnh vực xử lý tiếng nói. Chính vì thế, việc nắm bắt được các kỹ thuật cơ bản cũng như các công nghệ tiên tiến cho việc xử lý tiếng nói là thực sự cần thiết cho việc xây dựng các ứng dụng xử lý tiếng nói. Với mục đích đó, luận văn đã tập trung vào việc tìm hiểu, nghiên cứu và tìm kiếm các đặc trưng của tiếng nói phục vụ cho việc nhận dạng.Trên cơ sở các kết quả nghiên cứu luận văn xây dựng ứng dụng để kiểm tra, đánh giá các đặc trưng.Với mục đích trên, không làm giảm ý nghĩa của nội dung nghiên cứu, luận văn đã chọn tiếng Việt để thử nghiệm. Luận văn gồm các chương sau: Chương 1: Cơ sở toán học của luận văn Chương này trình bày những vấn đề lý thuyết làm cơ sở cho các chương saunhư nén dữ liệu, Zero Crossing, phép biến đổi Cosine, phép biến đổi Wavelet Haar, hệ số tương quan Peason Chương 2: Âm thanh, tiếng nói và nhận dạng tiếng nói Chương này trình bày cơ sở lý thuyết về âm thanh, tiếng nói và nhận dạng tiếng nói. Chương 3: Số hóa âm thanh Chương này trình bày các phương pháp số hóa âm thanh, tiếng nói. Chương 4: Xây dựng ứng dụng để nhận dạng tiếng Việt Chương này trình bày cách lấy đặc trưng tiếng nói, kỹ thuật nén các đặc trưng và thử áp dụng cho bài toán nhận dạng tiếng nói các từ đơn tiếng Việt. 6 CHƢƠNG 1.CƠ SỞ TOÁN HỌC CỦA LUẬN VĂN 1.1.Nén dữ liệu 1.1.1.Khái niệm, định nghĩa Trong công nghệ thông tin, Nén dữ liệu (tiếng Anh: Data compression) là việc biến đổi dữ liệu có dung tích lớn về dữ liệu có dung tích nhỏ hơn song vẫn có thể khôi phục lại dữ liệu ban đầu với độ chính xác nào đó. Tùy thuộc vào khả năng khôi phục lại dữ liệu ban đầu, người ta chia nén dữ liệu thành hai loại: Nén bảo toàn thông tin (lostless) và nén không bảo toàn thông tin (lossy). Nén dữ liệu là một lĩnh vực quan trọng trong Công nghệ Thông tin vì ngày càng có nhiều bài toán dữ liệu quá lớn, thiết bị lưu trữ không đáp ứng được, tốn thời gian, tìm kiếm, tốn dung tích bộ nhớ. Nén dữ liệu làm giảm dung tích lưu trữ, giảm thời gian truyền dữ liệu và giảm thời gian tìm kiếm, xử lý mà nhiều bài toán thực tế đòi hỏi. Nhìn chung không có phương pháp nén tổng quát cho kết quả tốt đối với tất cả các loại tập tin. Kỹ thuật nén tập tin thường được áp dụng cho các tập tin văn bản, các tập tin là hình ảnh, âm thanh, video, … Mỗi loại tập tin đòi hỏi các phương pháp nén khác nhau. 1.1.2.Phân loại nén dữ liệu Về nguyên tắc có 2 loại nén dữ liệu, nén bảo toàn thông tin và nén không bảo toàn thông tin. Nén bảo toàn thông tin là loại dữ liệu được nén sau khi giải nén sẽ nhận được bản gốc ban đầu. Một số kỹ thuật nén bảo tồn thông tin thông dụng là thuật toán Lempel-Ziv (LZ), DEFLATE, là một biến thể của thuật toán LZ, được tối ưu hóa nhằm tăng tốc độ giải nén và tỉ lệ nén, bù lại thuật toán này có tốc độ của quá trình nén chậm. Các thuật toán nén bảo toàn thông tin được dùng để nén các file văn bản như file dạng word, excel, … Các loại dữ liệu này không được phép sai lệch so với bản gốc sau khi giải nén. Ngoài ra còn một số thuật toán nén bảo toàn thông tin cơ bản khác như: o LZ-77 & LZ-78 o LZW o Run-length encoding (RLE),Dictionary coder o Nén Số học o Huffman coding. 7 Nén không bảo toàn thông tinlà kiểu nén dữ liệu mà sau khi giải nén người ta không nhận lại được dữ liệu gốc.Đối với hình ảnh, âm thanh, video, nói chung các dữ liệu multimedia được nén theo kiểu này, ví dụ như nén MPEG, JPEG là kiểu nén mất dữ liệu dùng cho các dữ liệu Multimedia. Về nguyên tắc của loại nén này là dựa vào đặc tính sinh lý của các giác quan của con người, người ta có thể lược bỏ một số thành phần của dữ liệu mà con người không nhận ra. Ưu điểm của nénkhông bảo toàn thông tin so với nén bảo toàn thông tin đó là nén không bảo toàn thông tin cho tỉ lệ nén cao hơn rất nhiều so với bất cứ thuật toán nén bảo toàn thông tin. 1.2.Điểm cắt Zero (Zero Crossing) 1.2.1.Khái niệm và định nghĩa Điểm cắt zero là một khái niệm được sử dụng phổ biến trong kỹ thuật điện, toán học và xử lý ảnh. Trong toán học, điểm cắt zero là điểm mà ở đó hàm số đổi dấu, ví dụ từ dương sang âm và được biểu diễn bằng điểm cắt trên trục hoành. Hình 1.1: Điểm cắt Zero biểu thị tương quan giữa điện áp và thời gian 1.2.2.Trích chọn đặc trưng dựa vào điểm cắt Zero Chúng ta xem đường cong tạo bởi tín hiệu của âm thanh là đường hình sin liên tụctheo thời gian t, khi đó điểm cắt zero là điểm đường cong cắt trục thời gian (t).Thay cho việc lưu giữ các giá trị mẫu tín hiệu trên cung ABC chúng ta chỉ lưu thông tin về tam giác ABC như mô tả ở hình 1.2. 8 Hình 1.2: Mô tả cách biểu diễn đoạn tín hiệu giữa hai điểm cắt zero qua tam giác ABC Thông tin về tam giác ABC gồm:  Độ dài cạnh AC được đo bằng x= t2-t0  Độ dài từ t0 đến thời điểm giá trị tín hiệu đạt cực đạit1ta ký hiệulày=t1t0;Về lý thuyết hàm tín hiệu liên tục φ(t)thì vị trí này luôn tồn tại  Giá trị cực đại max của tín hiệu trên cung ABC kí hiệu là z Khi đó kết quả thu được từ hàm tín hiệu φ(t) là tệp dữ liệu text mà mỗi đoạn nằm giữa của 2 điểm cắt zero liên tiếp ứng với bộ ba tham số {x,y,z}. Trong đó: x: là độ dài giữa hai điểm cắt Zero liên tiếp; y: là độ dài đoạn từ điểm cắt Zero thứ nhất đến thời điểm tín hiệu đạt giá trị max; z: là giá trị max của tín hiệu. 1.2.3.Thuật toán lấy điểm cắt Zero Input: Tín hiệu tiếng nói, là chuỗi các biên độ ứng với giá trị tín hiệu tiếng nói. Output: Dữ liệu là một chuỗi của các bộ 3 tham số {x,y,z}. Kí hiệu n là độ dài tệp dữ liệu được gọi tên là f.wave, dùng mảng A để đọc dữ liệu tiếng nói từ tệp dữ liệu f. Duyệt từ byte thứ 44 cho đến cuối mảng A (do cấu trúc tệp dữ liệu dạng wave, 44 byte đầu tiên lưu thông tin Header của tệp dữ liệu), xét dấu từng giá trị tín hiệu, nếu có sự đổi dấu của giá trị tín hiệu khi đó có tồn tại một điểm cắt zero. Trong đoạn giữa hai điểm cắt zero liên tiếp này, tìm z là giá trị lớn nhất của tín hiệu, y là vị trí đạt z và x là độ dài đoạn tín hiệu đang khảo sát, nếu chọn bước lấy mẫu là đơn vị thì x cũng là số mẫu được lấy trên đoạn tín hiệu trên. Lưu bộ 3 giá trị này vào tệp dữ liệu f1. Tiếp tục thực hiện như trên cho đến khi hết tệp dữ liệu f, tệp dữ liệu có tên f1.txt nhận được, chỉ chứa các bộ ba {x,y,z} của tệp dữ liệu ban đầu f.wave. 9 Begin Open(f) n = f.length read(f,A) i = 44; dem = 0; z = A(i); y = i; dau = lay dau(A(i)) i = i+1 i <= n Sai Đúng dau = lay_dau(A(i)) Sai x = dem; write (f1, x, y, z) z = A(i); y = i; dem = 0 dau = lay_dau (A(i)) Đúng dem = dem +1 Sai z < A(i) Đúng A(i) → f1 f1. close Stop z = A(i); y = i Hình 1.3: Sơ đồ mô tả thuật toán xác định tệpf1.txtchứa các bộ ba {x,y,z} Các biến được sử dụng trong thuật toán lấy điểm cắt Zero được mô tả như trên Hình 1.3: dau: nhận giá trị -1 hoặc +1 để nhận biết dãy giá trị tín hiệu đổi dấu, có nghĩa là có điểm cắt Zero. A: lưu giá trị tín hiệu. x: lưu số mẫu hay số tín hiệu giữa 2 điểm cắt Zero. 10 y: vị trí giá trị tín hiệu đạt cực đại giữa 2 điểm cắt Zero. z: giá trị biên độ cực đại hay giá trị cực đại của tín hiệu. n: số mẫu ứng với đoạn dữ liệu tiếng nói. dem: biến trung gian đếm số mẫu giữa 2 điểm cắt Zero File f: chứa dữ liệu tiếngnói ngõ vào. File f1: chứa dữ liệu nén ngõ ra. 1.3.Phép biến đổi Cosin Phép biến đổi Cosin rời rạc (Discrete Cosine Transform - DCT) được Ahmed đưa ra vào năm 1974. Kể từ đó đến nay nó được ứng dụng rất rộng rãi trong kỹ thuật xử lý ảnh, âm thanh và các kỹ thuật xử lý tín hiệu số nói chung. Mục đích của biến đổi Cosine rời rạc là nhằm giảm khối lượng dữ liệu của các tín hiệu mà vẫn bảo toàn chất lượng của tín hiệu. 1.3.1.Khái niệm và định nghĩa 1.3.1.1.Phép biến đổi Cosinthuận rời rạc một chiều Phép biến đổi Cosin thuận rời rạc một chiều được định nghĩa bởi công thức (1.1): 2𝜀𝑘 𝑋 𝑘 = 𝑁 𝑁−1 𝑥(𝑛) cos 𝑛=0 𝜋 2𝑛 + 1 𝑘 2𝑁 1.1 Trong đó:  N là hằng số tùy chọn, thường được lấy với N=8 1 2  𝜀𝑘 = 0 𝑘𝑕𝑖𝑘 = 0 𝑘𝑕𝑖𝑘 = 1, 𝑁 − 1 Khi dãy đầu vào x(n) là thực thì dãy các hệ số X(k) cũng là số thực. Tính toán trên trường số thực giảm đi một nửa thời gian so với biến đổi Fourier. Để đạt được tốc độ biến đổi thỏa mãn yêu cầu của các ứng dụng thực tế, người ta đã cải tiến kĩ thuật tính toán và đưa ra nhiều thuật toán biến đổi nhanh Cosine như: Phép biến đổi Cosine nhanh FCT (Fast Cosine Transform). 1.3.1.2. Phép biến đổi Cosin ngược một chiều Phép biến đổi Cosin ngược một chiều được định nghĩa bằng công thức (1.2): 11 𝑁−1 𝑥 𝑛 = 𝑋 𝑘 𝜀𝑘 𝐶𝑜𝑠 𝑘=0 1 2 𝑉ớ𝑖𝜀𝑘 = 0 𝜋𝑘 2𝑛 + 1 2𝑁 (1.2) 𝑘𝑕𝑖𝑘 = 0 𝑘𝑕𝑖𝑘 ≠ 0 Phép biến đổi Cosin ngược sẽ được thực hiện theo chiều ngược lại với quy trình đã tiến hành trong phép biến đổi nhanh. Tuy nhiên, công việc này không được thuận lợi như phép biến đổi FFT ngược. Từ X(k) chúng ta phải khôi phục lại XM(k) bằng cách thực hiện các phép cộng truy hồi và phép hoán vị theo thứ tự đảo bit. Công thức tổng quát cho mỗi khối biến đổi ngược được xây dựng dựa trên công thức tổng quát trong biến đổi xuôi: 𝑉ớ𝑖 𝑖 = 𝑘 𝑁 2𝑚 −1 𝑋𝑚 −1 𝑖 + ,…,𝑘 𝑁 2𝑚 −1 + 𝑁 , 𝑡𝑟𝑜𝑛𝑔 đó 𝑘 = 0,1, … , 2𝑚 − 1 2𝑚 𝑁 1 𝑁 1 = 𝑋 𝑖 − 𝑋 𝑖 + 𝑚 𝑚 𝑖 2𝑚 2 2𝑚 2𝐶𝑁/2 𝑚 −1 (1.3) 1 𝑁 1 𝑋𝑚 𝑖 + 𝑋𝑚 𝑖 + 𝑚 𝑖 2 2 2𝐶𝑁/2 𝑚 −1 (1.4) 𝑋𝑚 −1 𝑖 = Phép biến đổi ngược phải cài đặt riêng. Tuy vậy, tư tưởng chính của hai bài toán xuôi và ngược về cơ bản giống nhau. Đầu ra của phép biến đổi ngược sẽ là x’(n). Muốn thu được x(n) ta phải đảo vị trí. 1.3.1.3. Phép biến đổi Cosin nhanh Phép biến đổi Cosin nhanh viết tắt là FCT (Fast Cosine Transform), dựa vào ý tưởng đưa bài toán ban đầu về tổ hợp các bài toán biến đổi FCT trên các dãy con. Việc tiến hành biến đổi trên các dãy con sẽ đơn giản hơn rất nhiều so với dãy gốc. Vì thế, người ta tiếp tục phân nhỏ dãy tín hiệu cho đến khi chỉ còn một phần tử. Giải thuật biến đổi Cosin nhanh không thực hiện trực tiếp trên dãy tín hiệu đầu vào x(n) mà thực hiện trên dãy x’(n) là một hoán vị của x(n). Giả thiết số điểm cần tính FCT là lũy thừa của 2: N=2M Dữ liệu đầu vào sẽ được sắp xếp lại như sau: 𝑥 ′ 𝑖 = 𝑥 2𝑖 𝑣ớ𝑖 𝑖 = 0, 1, … , 𝑁 −1 2 𝑥 ′ 𝑁 − 𝑖 − 1 = 𝑥 2𝑖 + 1 𝑣ớ𝑖 𝑖 = 0, 1, … , 𝑁 −1 2 12 Như vậy, nửa đầu dãy x’(n) là các phần tử chỉ số chẵn của x(n) xếp theo chiều tăng dần của chỉ số. Nửa sau của x’(n) là các phần tử chỉ số lẻ của x(n) xếp theo chiều giảm dần của chỉ số. Thay vào công thức (1.1) ta được: 𝑁 −1 2 𝑋 𝑘 = 𝑥 2𝑛 𝐶𝑜𝑠 𝑛 =0 𝜋 4𝑛 + 1 𝑘 + 2𝑁 𝑁 −1 2 𝑥 2𝑛 + 1 𝐶𝑜𝑠 𝑛 =0 𝜋 4𝑛 + 3 𝑘 2𝑁 Rút gọn biểu thức: 𝑁−1 𝑋 𝑘 = 𝑥′ 2𝑛 𝐶𝑜𝑠 𝑛=0 𝜋 4𝑛 + 1 𝑘 2𝑁 Chia X(k) ra làm hai dãy, một dãy bao hàm các chỉ số chẵn, còn dãy kia gồm các chỉ số lẻ. Phần chỉ số chẵn 𝑁 −1 2 𝑥 ′ 𝑛 + 𝑥′ 𝑛 + 𝑋 2𝑘 = 𝑛=0 𝑁 2 𝐶𝑜𝑠 𝜋 4𝑛 + 1 2𝑘 2 𝑁 2 Có thể chuyển về dạng: 𝑁−1 𝑥 ′ 𝑛 𝐶𝑜𝑠 𝑋 2𝑘 = 𝑛 =0 𝜋 4𝑛 + 1 𝑘 2𝑁 (1.5) Các công thức: Có thể nhận ra ngay các công thức trên là các phép biến đổi Cosin N/2 điểm của g(n) và h(n).Hai dãy g(n) và h(n)được tính toán một cách dễ dàng, g(n) là tổng của nửa đầu dãy x’(n) với nửa sau của nó, h(n) là hiệu của nửa đầu dãy x’(n) với nửa sau của nó. Như vậy, bài toán biến đổi Cosin của dãy x’(n) đã được đưa về biến đổi Cosin của hai dãy là g(n) và h(n) có kích thước bằng một nửa x’(n), sau đó đem nhân với 2𝐶𝑁𝑛 . Ta lặp lại quá trń h chia đôi đ ối với các dãy con, dãy con của dãy con và cứ tiếp tục như thế. Mỗi bước lặp được coi là một tầng phân chia. Với N = 2M thì số tầng phân chia là M. Để dễ hình dung, đầu ra của mỗi tầng được kí hiệu là Xm(n) với m là tầng hiện thời. Ta xem x’(n) là biến đổi Cosin(0) tầng của x’(n): X0(n) = x’(n) (1.6) 13 XM(n) là biến đổi Cosin tầng M của x(n), nó không phải là X(k). Bởi vì cứ sau mỗi tầng, không chỉ thứ tự các phần tử trong X(k) bị xáo trộn mà các X(2k+1) còn được cộng với X(2k-1). Đầu ra của một tầng là đầu vào của tầng tiếp theo. X1(n) = g(n) với n=0, 1, …, 𝑁 2 −1 (1.7) 𝑁 X1(n+ ) = h(n) với n=0, 1, …, 2 𝑁 2 −1 Từ công thức tính g(n) và h(n) ta có: 𝑋1 𝑖 = 𝑋0 𝑖 + 𝑋0 𝑖 + 𝑋1 𝑖 + 𝑁 𝑁 = 𝑋0 𝑖 − 𝑋0 𝑖 + 2 2 𝑁 2 2𝐶𝑁𝑖 𝑣ớ𝑖 𝑛 = 0, 1, … , 𝑁 − 1 (1.8) Cứ sau mỗi tầng, số dãy con lại được nhân đôi. Xét phép biến đổi của tầng thứ m, chúng ta phải lặp lại công việc biến đổi cho 2m-1 dãy con. Mỗi dãy con đóng vai trò như dãy x’(n) trong tầng thứ nhất. Số phần tử trong một dãy là 𝑁 2𝑚 −1 . Công đoạn biến đổi trên một dãy con gọi là một khối biến đổi. Mỗi dãy con sẽ tiếp tục được phân làm hai dãy nhỏ hơn. Công thức tổng quát của mỗi khối là: 𝑋𝑚 𝑖 + 𝑣ớ𝑖 𝑖=𝑘 𝑋𝑚 𝑖 = 𝑋𝑚 −1 𝑖 + 𝑋𝑚 −1 𝑖 + 𝑁 2𝑚 𝑁 2𝑚 𝑁 𝜋2𝐶 ′ 𝑁/𝑚 −1 2𝑚 𝑋𝑚 − 𝑖 𝑖 − 𝑋𝑚 − 1 𝑖 + 𝑁 2 ,…,𝑘 𝑚 −1 𝑁 2 + 𝑚 −1 𝑁 , 2𝑚 (1.9) (1.10) 𝑡𝑟𝑜𝑛𝑔 đó 𝑘 = 0, 1, … , 2𝑚 − 1  Thuật toán biến đổi nhanh Cosin Thuật toán biến đổi nhanh Cosin có thể mô tả bằng các bước sau: Bước 1: Tính dãy hệ số Cij Xác định số tầng M=log2N Tầng hiện thời m=1 Bước 2: Nếu m ≤ M thực hiện bước 5. Nếu không kết thúc. (Chưa hết các khối trong một tầng) Bước 3: Khối hiện thời k = 0. Bước 4: Nếu k<2m-1 . Thực hiện bước 5. Nếu không thực hiện bước 6. (Chưa hết các khối trong một tầng) 14 Bước 5: Tính toán Xm(i) trong khối theo công thức tổng quát (1.6),( 1.7). Tăng k lên 1. Quay về bước 4. Bước 6: Tăng m lên 1. Quay về bước 2 (Chuyển đến tầng tiếp theo) Khác với biến đổi Fourier nhanh, trong biến đổi Cosin, x(n) không phải đầu vào trực tiếp và X(k) không phải là đầu ra trực tiếp. Ở đầu vào, x’(n) chỉ là cách sắp xếp lại x(n). Chúng ta biết rằng tại mỗi tầng, đối với mỗi khối: X(2i + 1) = X(2i +1) + X(2i -1) Nên ở đầu ra, sau khi tính được XM(n) chúng ta phải thực hiện việc trừ truy hồi từ tầng M về tầng 1 sau đó hoán vị lại theo thứ tự đảo bit mới thu được hệ số biến đổi X(k) cần tính. Dãy hệ số Cij được tính trước một lần. trong các ứng dụng mà số điểm tính FCT không đổi hoặc chỉ nhận một số giá trị cụ thể, người ta thường tính trước Cij và ghi ra file. Khi thực hiện biến đổi thì đọc từ file để lấy thông tin này. 1.3.1.4. Phép biến đổi Cosinerời rạc hai chiều  Phép biến đổi Cosine thuận rời rạc hai chiều được định nghĩa bởi công thức (1.11): 𝑋 𝑘1 , 𝑘2 4𝜀𝑘1 𝜀𝑘2 = 𝑁1 𝑁2 𝑁1 −1 𝑁2 −1 𝑥 𝑛1 , 𝑛2 𝐶𝑜𝑠 𝑛1=0 𝑛2=0 𝜋 2𝑛1 + 1 𝑘1 𝜋 2𝑛2 + 1 𝑘2 𝐶𝑜𝑠 2𝑁1 2𝑁2 (1.11) Trong đó, εk1=0 khi k1 =0 và 𝜀𝑘1 = εk2=0 khi k2=0 và 𝜀𝑘2 = 1 2 1 2 khi k1 = 1, 2,… , N1-1 khi k2 = 1, 2,… , N2 -1  Phép biến đổi ngược được định nghĩa bởi công thức (1.12): 𝑁1 −1 𝑁2 −1 𝑥 𝑛1 , 𝑛2 = 𝑋 𝑘1 , 𝑘2 𝜀𝑘1 𝜀𝑘2 𝐶𝑜𝑠 𝑘1=0 𝑘2=0 𝜋 2𝑛1 + 1 𝑘1 𝜋 2𝑛2 + 1 𝑘2 𝐶𝑜𝑠 2𝑁1 2𝑁2 (1.12) Trong đó, εk1, εk2 nhận các giá trị như trong công thức biến đổi xuôi. 1.3.2.Thuật toán Cosin và nén dữ liệu Theo phép biến đổi Cosin một chiều được cho bởi công thức (1.1) chúng ta thấy: 15 Dữ liệu đầu vào là một tập hợp gồm n giá trị dữ liệu pt (các pixel, các mẫu âm thanh, hoặc dữ liệu loại khác), và dữ liệu đầu ra là một tập hợp gồm n các hệ số biến đổi DCT X(k). Hệ số đầu tiên X(0) được gọi là hệ số DC, các phần còn lại được xem như là hệ số AC (những thuật ngữ này được thừa kế từ ngành kĩ thuật điện, chúng được hiểu như là “direct current” (dòng điện một chiều) và “alternating current” (dòng điện xoay chiều)),các hệ số này có thể âm hoặc có thể dương. Để khôi phục lại dữ liệu gốc ban đầu ta sử dụng phép biến đổi Cosin ngược IDCT. Phép biến đổi Cosin ngược IDCT được cho bởi công thức (1.8). Đặc trưng quan trọng của phép biến đổi Cosin DCT, điều khiến nó trở nên rất hữu dụng trong nén dữ liệu đó là nó lấy các dữ liệu đầu vào có tương quan với nhau. Hệ số AC được coi là đại diện, các hệ số DC nhỏ không đáng kể. Về mặt kỹ thuật người ta coi AC là năng lượng tập trung của nhóm. Nếu dữ liệu đầu vào bao gồm các khối dữ liệu có tương quan với nhau thì phần lớn n hệ số biến đổi được tạo ra sau phép biến đổi cosin rời rạc DCT là 0 hoặc các số rất nhỏ, và chỉ hệ số AC và một vài hệ số DC là đáng kể. Chúng ta nhận thấy rằng, các hệ số ở đầu khối chứa thông tin quan trọng và các hệ số còn lại chứa thông tin ít quan trọng hơn. Bởi vậy nén dữ liệu với phép biến đổi Cosin rời rạc được hoàn thành bằng cách làm tròn các hệ số. Các hệ số nhỏ được làm tròn về 0 và các số lớn có thể được làm tròn về số nguyên gần nhất. Giải nén được thực hiện bằng cách áp dụng phép biến đổi Cosin ngược IDCT trên những hệ số đã được làm tròn. Kết quả trong các giá trị dữ liệu ta được dãy sai khác với giá trị dữ liệu gốc ban đầu. Trong các ứng dụng thực tế, dữ liệu nén được phân chia thành các khối bao gồm n giá trị (người ta thường chọn n=8) và mỗi khối được áp dụng phép biến đổi DCT và được làm tròn từng giá trị một. Ví dụ sau đây minh họa sức mạnh của biến đổi Cosin rời rạc một chiều. Xét dãy pgồm 8hệ sốlàp={12;10;8;10;12;10;8;11}, áp dụng phép biến đổi DCT một chiềuta nhận dược kết quả là: q = {28.6375;0.571202;0.46194;1.757;3.18198; -1.72956; 0.191342; -0.308709} Áp dụng phép biến đổi Cosin ngược IDCT với q ta có thể khôi phục lại dãy pban đầu (loại trừ các lỗi nhỏ nguyên nhân bởi giới hạn độ chính xác của máy tính).Tuy nhiên mục đích của chúng ta ở đây là nén dữ liệu bằng cách làm tròn các hệ số. Đầu tiên chúng ta làm tròn các hệ số củadãy qthành dãy q1= {28.6; 0.6; 0.5; 1.8; 3.2; -1.8; 0.2; -0.3}rồi áp dụng phép biến đổi Cosin ngược IDCT để khôi phục lại ta thu được dãy p1 = {12.0254; 10.0233; 7.96054; 9.93097; 12.0164; 9.99321; 7.94354; 10.9989} 16 Sau đó chúng ta tiếp tục làm tròn các hệ số củadãy q1 với mức độ cao hơn thành dãy q2= {28; 1; 1; 2; 3; -2; 0; 0} và áp dụng phép biến đổi IDCT để khôi phục lại ta tiếp tục thu được dãy p2 = {2.1883; 10.2315; 7.74931; 9.20863; 11.7876; 9.54549; 7.82865; 10.6557} Cuối cùng, chúng ta làm tròn cáchệ số của dãyq2 thành dãyq3 = {28; 0; 0; 2; 3; -2; 0; 0} và tiếp tục khôi phục lại dữ liệu từ phép biến đổi Cosin ngược IDCT ta thu được dãy p3 = {11.236; 9.62443; 7.66286; 9.57302; 12.3471; 10.0146; 8.05304; 10.6842} từ dãy p3 được khôi phục lại và dãy p ban đầu ta thấy rằng sự khác biệt lớn nhất giữa hệ số gốc ban đầu (12) và hệ số được khôi phục lại (11.236) là 0.764 (hay là 6.4% của 12). Các bước thực hiện ví dụ cho kết quả trên thực hiện trong Matlab được liệt kê trong hình 1.4. Hình 1.4: Ví dụ phép biến đổi DCT một chiều Ta nhận thấy rằng 8 hệ số dữ liệu gốc có thể được khôi phục lại với độ chính xác caochỉ với 4 bước biến đổi DCT một chiều. 1.4.Phép biến đổi Wavelet Haar Để đáp ứng được yêu cầu độ phân giải ổn định với các tín hiệu có thành phần thời gian và tần số, ta cần dùng một phương pháp biến đổi sao cho độ phân giải thời gian và tần số có thể thay đổi phù hợp với đặc tính của tín hiệu trên mặt phẳng thời gian và tần số. Vấn đề này được giải quyết bằng cách thay thế phép di dời đơn giản trong STFT (Phép biến đổi Fourier thời gian ngắn) bằng phép tịnh tiến và thay đổi tỉ lệ (shifts and scales). Điều này dẫn đến sự ra đời của một phép biến đổi mới đó là phép biến đổi wavelets. Phép biến đổi Wavelet cho phép sử dụng các khoảng thời gian dài khi ta cần thông tin tần số thấp chính xác hơn, và miền thời gian ngắn hơn đối với thông tin tần số cao. Ở đây cho thấy sự tương phản với cách nhìn tín hiệu dựa theo thời gian, tần số, STFT : 17 Hình 1.5: Biến đổi Wavelet Vậy biến đổi wavelet không dùng một miền thời gian – tần số, mà là miền thời gian – tỷ lệ. Hình 1.6: Mô tả các miền biến đổi của tín hiệu Wavelets là các dạng sóng nhỏ có thời gian duy trì tới hạn với giá trị trung bình bằng 0. So sánh với sóng sin thì sóng sin không có khoảng thời gian giới hạn – nó kéo dài từ âm vô cùng đến vô cùng. Và trong khi sóng sin là trơn tru và có thể dự đoán, wavelet lại bất thường và bất đối xứng. Hình 1.7 mô tả sóng sin và wavelet . Hình 1.7: Sóng sin và wavelet Biến đổi Wavelet chia tách tín hiệu thành các phiên bản dịch vị và tỷ lệ (co dãn) của một hàm đơn hay gọi là hàm mẹ wavelet. Vì vậy tín hiệu với thay đổi nhanh có thể phân tích tốt với một wavelet bất ổn định hơn là với một sóng sin trơn. Các đặc tính cục bộ sẽ được miêu tả tốt hơn với các wavelet. 18