Báo cáo "Thuật toán nén dữ liệu tiếng nói trực tuyến"

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

81
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài báo đề xuất thuật toán nén dữ liệu tiếng nói trực tuyến. Nội dung của thuật toán là xấp xỉ tuyến tính dữ liệu tiếng nói. Trong bài báo này cũng đề xuất thuật toán giải nén với độ phức tạp tuyến tính. Kết quả thử nghiệm cho thấy thuật toán có thể áp dụng trong các ứng dụng nén và giải nén tiếng nói trực tuyến. Từ khóa: Nén dữ liệu, tiếng nói, dữ liệu tiếng nói, trực tuyến, dữ liệu tiếng nói trực tuyến. ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo "Thuật toán nén dữ liệu tiếng nói trực tuyến"

Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 25 (2009) 65-68 Thu t toán nén d li u ti ng nói tr c tuy n Nguy n Văn Xu t, Mai Văn Phú* Khoa Công ngh Thông tin, H c vi n K thu t Quân s , 100 Hoàng Qu c Vi t, Hà N i, Vi t Nam Nh n ngày 19 tháng 2 năm 2009 Tóm t t. Bài báo ñ xu t thu t toán nén d li u ti ng nói tr c tuy n. N i dung c a thu t toán là x p x tuy n tính d li u ti ng nói. Trong bài báo này cũng ñ xu t thu t toán gi i nén v i ñ ph c t p tuy n tính. K t qu th n ghi m cho th y thu t toán có th áp d ng trong các ng d ng nén và gi i nén ti ng nói tr c tuy n. T khóa: Nén d li u, ti ng nói, d li u ti ng nói, tr c tuy n, d li u ti ng nói tr c tuy n. 2. Thu t toán 1. M ñ u∗ 2.1. Ý tư ng Nén d li u âm thanh nói chung và d li u ti ng nói nói riêng ñ ã và ñang ñư c các nhà Chúng ta bi t r ng ñ th bi u di n năng khoa h c, công ngh trên th gi i q uan tâm lư ng c a ti ng nói là m t ñ ư ng cong liên t c nghiên c u, các k t q u ñ t ñư c ñã ñư c ng hình sin. ðư ng cong hình sin này ñư c c u d ng nhi u trong lĩ nh v c truy n thông và gi i thành t các khúc cong ñơn ñi u [5]. Chúng ta trí. Trong lĩnh v c nén âm thanh, ngư i ta ñã t ng bi t ñ n các chu n nén khá n i ti ng như dùng các ño n th ng thay cho các khúc cong dòng h nén MPEG, MP3, JPEG...[1] ð c ñi m ñơn ñi u là ý tư ng cơ b n c a thu t toán này chung c a các thu t toán nén trên là: hi u su t (hình 1). nén cao, ch t l ư ng âm thanh sau khi gi i nén t t. Tuy nhiên do tính ph c t p c a các thu t toán ñó nên quá trình nén và gi i nén luôn ph i tách thành hai quá trình riêng bi t. ð c ñi m này làm cho các thu t toán trên không th s d ng trong các trư ng h p c n nén và gi i nén tr c tuy n [2]. Vì v y, vi c tìm ki m và thi t l p các thu t toán nén và gi i nén có th th c hi n tr c tuy n ñã và ñang là v n ñ th i s . Hình 1. Bi u di n các khúc cong c a hình sin b i Dư i ñây trình bày thu t toán cho phép nén và các ñ o n th ng AB, BC, CD. gi i nén tr c tuy n trên d li u ti ng nói. ð ti n cho vi c di n ñ t, ta ký hi u thu t _______ toán nén mô t dư i ñây là thu t toán TT1. ∗ Tác gi liên h . ð T: 84-4-37580121. E-mail: phumv06@yahoo.com 65
66 N.V. Xuất, M.V. Phú / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 65-68 2.2. Mô t thu t toán TT1 thu t toán trên là Output (A,B,n) và Output (B,C,n1), v i A, B là ph n t ñ u, cu i c a dãy Gi s d li u c a ti ng nói là dãy S={s1, s2, con th nh t và B, C là ph n t ñ u, cu i c a ..., sL}, L∈N, si ∈R. Ta xét dãy con liên ti p c a dãy con th hai. Rõ ràng ta có th b t ñi ph n S: {sm, sm+1, ..., sm+n-1}, 1≤m≤L-n+1, n>0, (hình t B l n truy n th hai. 2). Khi ñó, thay vì ph i lưu tr n giá tr c a dãy 3) Thu t toán mô t trên còn có th c i ti n con này ta ch lưu tr các giá tr sm, sm+n-1 và n. ñ nâng cao t l nén b ng cách thay các khúc Sơ ñ kh i hình 3 mô t thu t toán TT1 làm ñư ng cong AB (bao g m c các khúc cong vi c theo ch ñ tr c tuy n. không gi m, không tăng) b ng ño n th ng AB n u m i ñi m trên khúc ñ ư ng cong AB th a mãn ñi u ki n |s1 -s2|0), ñây s1, s2 n m trên khúc cong AB, minh h a hình 4. Hình 2. Bi u di n dãy con n ñi m liên ti p c a m t khúc cong ñơn ñi u. ð u vào: Dãy tín hi u ti ng nói. ð u ra: Các véctơ có d ng (A,B,n) tương ng là ph n t ñ u, cu i và s p h n t c a dãy con ñơn ñi u. Các bi n s d ng trong thu t toán TT1 mô t trong hình 3: D u: nh n giá tr +1 ho c -1 bi u th dãy con không tăng hay gi m, s: lưu giá tr tín hi u, Y1, Y2: lưu hai giá tr liên ti p c a tín hi u. Hình 3. Sơ ñ kh i thu t toán TT1. A, B: lưu giá tr ñ u và cu i c a dãy con ñơn ñi u. n: lưu s ph n t c a dãy con ñơn ñi u. Nh n xét: 1) Thu t toán trên có th làm vi c tr c tuy n vì quá trình nén ch th c hi n hai thao tác ch y u là so sánh hai tín hi u liên ti p và ñ m. 2) Thu t toán mô t b i sơ ñ kh i hình 3 có th c i ti n ñ nâng cao t l nén. Chúng ta hãy xét hai l n truy n d li u nén liên ti p trong Hình 4. Minh h a ý tư ng c i ti n thu t toán TT1.
67 N.V. Xuất, M.V. Phú / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 65-68 2.3. Thu t toán gi i nén ng v i thu t toán TT1 4. ðánh giá ch t lư ng nén D li u nén d ng (A, B, n) do thu t toán Chúng ta xét m t dãy d li u trên m t ñ o n TT1 th c hi n ñư c gi i nén b ng cách n i suy ñơn ñi u: (s1, s2,..., sn). tuy n tính n ñi m cách ñ u v i giá tr ñ u, cu i Gi s d li u sau khi gi i nén b i thu t tương ng là A, B. Ký hi u (y1, y2, ..., yn) là n toán TT2 tương ng v i dãy trên là (y1, y2,..., yn). giá tr ñư c gi i nén. Khi ñó: T l sai l ch (%) gi a d li u g c (s1, s2,..., yi =A+(i-1)*(B-A)/(n-1), v i n>1, i=1..n. sn) và d li u gi i nén (y1, y2, ..., yn ) ñư c tính b ng công th c sau: Ký hi u thu t toán gi i nén ng v i thu t n toán TT1 là thu t t oán TT2. Thu t toán TT2 ∑ si − yi ñư c mô t trong sơ ñ kh i hình 5. i =1 *100 (%) σ= n ð u vào: Các véc tơ ch a d li u nén d ng ∑ si (A, B, n), tương ng là ph n t ñ u, cu i và s i =1 ph n t c a dãy con ñơn ñi u. Gi s thu t toán TT1 ñã nén ñư c K ñ o n ð u ra: n giá tr ñã ñư c gi i nén ch a trong d li u ñơn ñi u, t l sai l ch gi a d li u g c m ng y. và d li u gi i nén trên t ng ño n tương ng là σ1 , σ 2 , ..., σ K , khi ñó, t l sai l ch trung bình gi a d li u g c và d li u gi i nén c a thu t toán TT1 ñư c tính b ng công th c sau: K ∑σi i =1 (%) σ TB = K Ch t lư ng c a thu t toán TT1 có th ñánh giá qua σ TB . N u σ TB càng th p thì ch t l ư ng sau khi gi i nén càng cao và ngư c l i. 5. K t qu , th o lu n Th nghi m thu t toán TT1 và TT2 6 l n Hình 5. Sơ ñ kh i thu t toán TT2. trên 6 t p d li u ti ng nói d ng file wave. K t qu ñư c th hi n trong b ng 1. 3. ð ph c t p tính toán c a thu t toán B ng 1. K t qu th nghi m thu t toán TT1 và TT2. Thao tác ch y u trong thu t t oán TT1 là so sánh hai ph n t liên ti p. Vì v y n u dãy tín Kích thư c Kích thư c T l nén L n trư c khi nén sau khi nén 1 00 .g σ TB (%) hi u vào có n tín hi u thì s phép so sánh s là (%) th ( bytes) ( g bytes) f f n-1. Do v y, ñ ph c t p c a thu t toán TT1 là O(n). 1 467712 182024 38.92 4.53 Tương t như v y, thu t toán TT2 cũng có 2 654336 213407 32.62 6.11 3 787968 271967 34.51 5.78 ñ ph c t p tính toán tuy n tính, O(n). 4 1487616 512879 34.48 6.15 5 2609664 908306 34.81 6.08 6 5806080 1990121 34.28 6.02
68 N.V. Xuất, M.V. Phú / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 65-68 K t qu trong b ng 1 cho th y t l nén Tài li u tham kh o trung bình mà thu t toán TT1 ñ t ñ ư c x p x [1] David Salomon, Data Compression, Springer - 35%, ñi u ñó có nghĩa là thu t toán nén ñư c Verlag NewYork, Inc., 2004. ≈3 l n. T l sai l ch trung bình gi a d li u [2] Lajos Hanzo, F. Clare Somerville, Jason Woodard, g c và d li u gi i nén ≈6%. Voice compression for wireless communication. Antony Rowe Ltd, Chippenham, England., 2007 [3] C. Greg Plaxton, Yu Sun, Mitul Tiwari, Harrick 6. K t lu n Vin, “Online Compression Caching”, Proceedings of the 11th Scandinavian workshop on Algorithm Theory, Gothenburg, Sweden, ISBN: 978-3-540- Hi u su t nén c a thu t toán TT1 không 69900-2, vol. 5124, (2008) 414. th c s cao như m t s thu t toán nén thông [4] Konstantinos G. Kyriakopoulos, David J. Parish, “A d ng trên th trư ng, nhưng v i ưu ñi m ñơn system for online compression of high-speed gi n trong cài ñ t và có ñ p h c t p tuy n tính network measurements”, International Journal of nên phù h p v i các bài toán x lý tr c tuy n. Internet Protocol Technology, Springer-Verlag M t khác, có th th y d li u nén c a m t ño n Berlin, Heidelberg, vol. 3, No.2, (2008) 95. d li u ti ng nói cũng có th coi như m t ñ c [5] R. John Deller, Jr., John H.L. Hansen, G. John Poakis, Descrete - Time Processing of Speech trưng mô t ño n d li u ñó. Vì v y, ý tư ng Signals. The Institute of Electrical and Electronics này còn có th s d ng vào m t s bài toán Engineers Inc., NewYork, 2000. khác. [6] G. Richard Lyons, Understanding Digital Signal Processing. Prentice Hall, 2001. Algorithm for compressing and decompressing online voice data Nguyen Van Xuat, Mai Van Phu Faculty of Information Technology, Military Technical Academy, 100 Hoang Quoc Viet, Hanoi, Vietnam This article proposed an algorithm for compressing and decompressing online voice data. The content of this algorithm is linear approximations voice data. This article also addressed an algorithm for unpacking measures with complex linear. The test results showed that this algorithm can be used for compressing and decompressing application of online voice data. Keywords: Data compression, voice, voice data, online, online voice data.