- 1. VIDEO, AUDIO ĐỒNG BỘ DỮ LIỆU ĐA PHƯƠNG TIỆN
- 2. nén d li u đa ph ng ti nấ ề ữ ệ ươ ệ Yêu c u dung l ng thông tin c n l u tr và truy n:ầ ượ ầ ư ữ ề + M t trang văn b n (text): 2Kbytesộ ả + M t nh màu (800 x 600 x 24bits): 1.4Mbytesộ ả + 30 phút âm thanh tho i s (8 kHz, 8 bits): 14Mbytesạ ố + 30 phút Audio CD (44.1kHz, 16bits, stereo): 432Mbytes + 30 phút audio (48kHz, 20bits, stereo): 432Mbytes + 30 phút video (800x600x24bits, 25 nh/s): 64.8 Gbytesả + T c đ dòng video (800x600x24bits, 25 nh/s): 275Mbits/số ộ ả
- 3. chất lượng nén Tỷ số nén: + Tỷ số nén tĩnh: CR= Kích thước dữ liệu ban đầu/Kích thước dữ liệu sau khi nén - Tỷ số bit/pixel đối với ảnh: Nb = Số bit sau khi nén/Tổng số điểm ảnh (bpp) - Tỷ số nén tốc độ dòng bit video Chất lượng nén: - Nén không mất mát thông tin (lossless) - Nén có mất mát thông tin (lossy)
- 4. chất lượng nén Độ phức tạp: - Độ phức tạp về thời gian: Nén thời gian thực, nén thời gian không thực - Độ phức tạp về không gian, bộ nhớ
- 5. dữ liệu ảnh: Biến đổi dòng thông tin thành từ mã nhằm giảm độ dư thừa thông tin theo không gian và thời gian - Các độ dư thừa thông tin: Dư thừa thông tin về không gian, về thời gian, độ dư thừa về phổ và dư thừa do độ cảm nhận Phân loại ảnh theo thời gian: - Ảnh tĩnh: là ảnh tự nhiên thu nhận (chụp), ảnh đồ họa (vẽ), có dư thừa không gian và dư thừa về cảm thụ - Ảnh động: ảnh video, ảnh động chuyên dụng, hoạt hình, ảnh động biến thiên theo thời gian, có cả 4 loại dư thừa
- 6. phương pháp nén ảnh tĩnh Phân loại phương pháp nén ảnh: + Nén không mất mát thông tin: các phương pháp mã hóa dữ liệu + Nén có mất mát thông tin: các phương pháp nén dựa trên phép biến đổi ảnh: Ảnh đầu vào Xử lý Mã hóa Giải mã Xử lý Ảnh đầu ra Dòng dữ liệu 00110101
- 7. mã hóa không mất mát thông tin – Lossless Compression 1.Mã loạt dài (Run length Encoding -RLE): 2.Dùng số đếm để thay thế các điểm giống nhau lặp lại. Ý tưởng của phương pháp nén này như sau: RLE thay thế các chuỗi ký tự lặp lại nhiều lần bằng một chuỗi ngắn hơn. Chuỗi ký tự được gọi là run và thường được mã hóa (encoded) thành 2 bytes: byte đầu tiên biểu diễn số lượng các ký tự trong run và được gọi là run count.
- 8. mã hóa không mất mát thông tin – Lossless Compression Run count có thể chạy từ 1 đến 128 hoặc 256, thông thường run count = số lượng ký tự - 1 + Byte thứ hai là ký tự trong run (từ 0 đến 255) và được gọi là run value + Ví dụ: Nếu không nén ta cần 15 bytes để biểu diễn chuỗi AAAAAAAAAAAAAAA (15 ký tự A), nếu sử dụng RLE ta sẽ có kết quả 15A, do đó chỉ cần 2 bytes để biểu diễn. 15A được gọi là RLE packet Một vài biến thể (variants) của RLE:
- 9. mã hóa không mất mát thông tin – Lossless Compression
- 10. mã hóa không mất mát thông tin – Lossless Compression
- 11. mã hóa không mất mát thông tin – Lossless Compression 2. Mã hóa độ dài thay đổi (Variable-Length Coding –VLC): Dùng các cụm bit có độ dài thay đổi để mã hóa, bao gồm mã Shannon-Fano và mã Huffman. a, Mã Shannon-Fano + Ý tưởng của mã Shannon-Fano: 1. Sắp xếp các ký hiệu theo tần suất xuất hiện 2. Lặp lại việc chia các ký hiệu thành 2 phần, mỗi một phần bằng số lần xuất hiện (xác suất xuất hiện) của ký hiệu đó, cho đến khi mỗi một phần chỉ còn lại một ký hiệu
- 12. mã hóa không mất mát thông tin – Lossless Compression Ví dụ: Mã hóa từ “HELLO”
- 13. mã hóa không mất mát thông tin – Lossless Compression Cây mã hóa của từ “HELLO” bằng mã Shannon-Fano
- 14. mã hóa không mất mát thông tin – Lossless Compression Kết quả của mã hóa từ “HELLO” bằng mã Shannon-Fano
- 15. mã hóa không mất mát thông tin – Lossless Compression Một cây mã hóa khác của từ “HELLO” bằng mã Shannon-Fano
- 16. mã hóa không mất mát thông tin – Lossless Compression Kết quả
- 17. mã hóa không mất mát thông tin – Lossless Compression b, Mã Huffman: + Ý tưởng của mã Huffman: 1. tạo một danh sách (list) gồm các ký tự đã được sắp xếp theo thứ tự giảm dần của tần suất xuất hiện. 2. Lặp lại cho đến khi danh sách chỉ còn lại một ký tự: (1) Từ danh sách đã sắp xếp lấy ra 2 ký tự có xác suất nhỏ nhất để tạo thành một cây Huffman con (subtree), cây này gồm 2 node là 2 ký tự vừa được lấy ra và tạo ra một node cha (parent node)
- 18. mã hóa không mất mát thông tin – Lossless Compression (2) Gán tổng xác suất của hai node con cho node cha và chèn node cha này vào danh sách sao cho không làm thay đổi thứ tự đã sắp xếp trong danh sách. (3) Xóa 2 node con khỏi danh sách 3. Gán một từ mã (codeword) cho mỗi nút lá dự trên đường đi từ gốc Ví dụ mã hóa từ “HELLO” sử dụng mã Huffman:
- 19. mã hóa không mất mát thông tin – Lossless Compression Cây mã hóa từ “HELLO” sử dụng mã Huffman
- 20. mã hóa không mất mát thông tin – Lossless Compression + Trong sơ đồ trên các ký hiệu P1, P2, P3 được tạo ra và được gọi là các node cha (parent node) và danh sách sẽ bao gồm: Sau khi sắp xếp: LHEO Sau lần lặp thứ nhất: LP1H Sau lần lặp thứ 2: LP2 Sau lần lặp thứ 3: P3
- 21. mã hóa không mất mát thông tin – Lossless Compression Các thuộc tính của mã Huffman: 1. Thuộc tính tiền tố (prefix) duy nhất: Không một mã Huffman nào lại là tiền tố của một mã Huffman khác ngăn không cho giải mã “nhập nhằng” 2. Tối ưu hóa: Mã hóa dư thừa tối thiểu, đó là: - Hai ký hiệu xuất hiện ít nhất sẽ có độ dài từ mã là như nhau chỉ khác nhau ở bit cuối cùng - Các ký hiệu xuất hiện nhiều hơn sẽ có độ dài mã Huffman ngắn hơn so với các ký hiệu xuất hiện ít hơn - Độ dài trung bình của các từ mã nhỏ hơn đó là
- 22. mã hóa không mất mát thông tin – Lossless Compression Ngoài ra ta còn có mã Huffman mở rộng (Extended Huffman) và mã Huffman thích nghi (Adaptive Huffman) 3.Mã hóa dựa trên từ điển – Dictionary-based Coding Phổ biến nhất là mã Lemple-Ziv, ý tưởng của phương pháp này là: + Sử dụng các từ mã có độ dài cố định để biểu diễn các các chuỗi có độ dài thay đổi
- 23. mã hóa không mất mát thông tin – Lossless Compression + LZW encoder và LZW decoder cùng xây dựng nên một từ điển động (dictionary) khi nhận được dữ liệu. + LZW đặt các đầu vào (entries) dài hơn, lặp lại nhiều lần vào trong từ điển và sinh ra mã cho mỗi phần tử nếu như phần tử này đã có trong từ điển
- 24. mã hóa không mất mát thông tin – Lossless Compression Giải thuật LZW để nén dữ liệu
- 25. mã hóa không mất mát thông tin – Lossless Compression Ví dụ: Sử dụng LZW để nén xâu “ABABBABCABABBA” + Bắt đầu bằng một từ điển đơn giản được gọi là “string table”, ban đầu từ điển này chỉ gồm 3 ký tự với các mã như sau: Giải thuật LZW thực hiện như sau:
- 26. mã hóa không mất mát thông tin – Lossless Compression
- 27. mã hóa không mất mát thông tin – Lossless Compression : + Bảng các mã sẽ là 1 2 4 5 2 3 4 6 1. Thay vì phải gửi đi xâu “ABABBABCABABBA” (14 ký tự) ta chỉ phải gửi đi 9 ký tự, do đó tỷ lệ nén là 14/9=1.56 Giải thuật LZW để giải nén như sau
- 28. mã hóa không mất mát thông tin – Lossless Compression Ví dụ: Giải nén mã 1 2 4 5 2 3 4 6 1
- 29. mã hóa không mất mát thông tin – Lossless Compression 4. Mã dự đoán (Prediction Coding) Các cách tiếp cận của mã hóa vi sai các ảnh (differential coding) Cho một ảnh gốc I(x,y), sử dụng một phép tính vi phân đơn giản ta có thể định nghĩa một ảnh vi sai d(x,y) như sau: d(x,y)= I(x,y) – I(x-1,y) Hoặc sử dụng một phép tính vi phân Laplician ta có thể định nghĩa một ảnh sai phân như sau
- 30. mã hóa không mất mát thông tin – Lossless Compression Do có sự dư thừa về không gian trong ảnh I nên ảnh vi sai d sẽ có một biểu đồ tần xuất hẹp hơn và do đó sẽ có một entropy nhỏ hơn Được sử dụng trong phương pháp nén ảnh Ví dụ sau sẽ minh họa việc sử dụng các phép tính vi phân để tạo ra một ảnh sai phân từ ảnh ban đầu:
- 31. mã hóa không mất mát thông tin – Lossless Compression
- 32. mã hóa không mất mát thông tin – Lossless Compression Lossless JPEG là một trường hợp đặc biệt của phương pháp nén ảnh JPEG Phương pháp dự đoán: 1. tạo ra một dự đoán vi sai: Một bộ dự đoán sẽ kết hợp giá trị từ 1 đến 3 pixels ở cạnh như là các giá trị đã được đoán trước cho pixel hiện tại (điểm X) được minh họa như sau:
- 33. mã hóa không mất mát thông tin – Lossless Compression Bộ dự đoán có thể sử dụng 1 trong 7 kiểu sau đây:
- 34. mã hóa không mất mát thông tin – Lossless Compression
- 35. mã hóa không mất mát thông tin – Lossless Compression 2. Mã hóa: Bộ mã hóa sẽ so sánh giá trị của dự đoán (prediction) với giá trị thực sự của điểm X và mã hóa sự vi sai bằng cách sử dụng một trong các kỹ thuật nén không mất mát thông tin (chẳng hạn như Huffman) Lưu ý: các giá trị A, B,C đã được giải mã trước bên phía giải mã của một chu trình mã hóa-giải mã khi được sử dụng bởi bộ dự đoán
- 36. mã hóa không mất mát thông tin – Lossless Compression Ảnh của Lena Söderberg được sử dụng trong nhiều thí nghiệm về xử lý ảnh
- 37. mã hóa không mất mát thông tin – Lossless Compression Bảng so sánh tỷ lệ nén giữa các phương pháp nén không mất mát thông tin
- 38. mã hóa mất mát thông tin – Lossy Compression Các phương pháp nén không mất mát thông tin không có được một tỷ lệ nén cao cần thiết, do đó hầu hết các giải thuật nén ĐPT là nén có mất mát thông tin (lossy) 1. Khái niệm nén có mất mát thông tin: - Dữ liệu được nén không giống với dữ liệu gốc nhưng gần giống dữ liệu gốc - Có tỷ lệ nén cao hơn nhiều so với các phương pháp nén không mất mát thông tin
- 39. sự biến dạng của dữ liệu sau khi nén: Có 3 đại lượng dùng đánh giá sự biến dạng của dữ liệu trong nén ảnh a, Bình phương trung bình sai số (Sai số quân phương) – Mean Square Error-MSE Trong đó: + xn là dãy dữ liệu vào + yn là dãy dữ liệu được xây dựng từ xn + N số lượng dữ liệu
- 40. giữa tín hiệu và tạp nhiễu – Signal to Noise Ratio – NRS (dB): Trong đó: là trung bình bình phương cửa dãy dữ liệu ban đầu và là MSE C, Đỉnh của tỷ lệ giữa tín hiệu và tạp nhiễu –Peak Signal to Noise Ratio – PNRS (dB):
- 41. – Quantization Giảm bớt các giá trị đầu ra sai khác Có 3 phương pháp để lượng hóa: + Uniform: Bao gồm midrise quantizer và midtreat quantizer + Nonuniform: companded quantizer + Vector Quantization
- 42. vô hướng giống nhau – Uniform Scalar Quantization: + Phân chia vùng dữ liệu vào (input) thành các khoảng đều nhau, ngoại trừ hai khoảng or hai biên. + Giá trị của dữ liệu ra (output) được lấy tại điểm giữa của mỗi khoảng + Độ dài của mỗi khoảng được gọi là step size và được ký hiệu là
- 43. có một số lẻ các mức ra (output levels) + Midtreat quantizer có một số chẵn các mức ra bao gồm cả số 0 như là một mức ra Trong trường hợp =1 ta có thể tính được các giá trị ra như sau:
- 44. (a) Midrise (b) Midtreat
- 45. vô hướng khác nhau – Nonuniform Quantization Phân chia vùng dữ liệu vào (input) thành các khoảng không đều nhau. Các khoảng cách có thể được lựa chọn để tối ưu hóa SNR cho một kiểu cụ thể của tín hiệu Một trong số các phương pháp lượng tử hóa của Nonuniform Quantization là Companded Quantization
- 46. là kết hợp của hai bước: Compressed (bên phía gửi) và Expanded (bên phía nhận) + Compressed sẽ làm cho tín hiệu đầu vào có phân phối đều (uniform distribution) do đó có thể sử dụng uniform quantization + Bên nhận khi nhận được tín hiệu (compressed) sẽ tiến hành giải nén dữ liệu (expanded)
- 47. vector – Vector Quantization Các hệ thống nén dữ liệu sẽ làm việc tốt hơn nếu nó hoạt động trên các vector hoặc các nhóm của các mẫu hơn là làm việc với các ký hiệu hay các mẫu riêng lẻ Các vector được thành lập bằng cách đặt các mẫu đầu vào liên tiếp vào trong một vector. Trong Vector Quantization các vector mã (code vector) với n thành phần được sử dụng, các các vector mã này sẽ tạo thành một codebook
- 48. tử hóa vector cơ bản
- 49. đổi – Transform Nếu Y là kết quả của một pháp biến đổi tuyến tính T của một vector đầu vào X sao cho các thành phần của Y ít tương quan đến nhau khi đó Y có thể được mã hóa hiệu quả hơn X. Nếu hầu hết các thông tin được mô tả một cách chính xác bởi một vài thành phần đầu tiên của một vector đã được biến đổi thì các thành phần còn lại có thể được lượng tử hóa thô hoặc được đặt bằng 0 với một chút biến dạng về tín hiệu
- 50. đổi – Transform Trong mã hóa biến đổi phép biến đổi Cosine rời rạc –Discrete Cosine Transform (DTC) và phép biến đổi Wavelet rời rạc là các phép biến đổi quan trọng được áp ựng nhiều trong nén ảnh (tĩnh và động) Tần số không gian (Spatial Frequency) và DTC Tần số không gian sẽ chỉ ra số lần giá trị của pixel thay đổi qua một block ảnh DTC chỉ ra các nội dung của bức ảnh thay đổi bao nhiêu tương ứng với số vòng của một sóng hình cosine trên một khối ảnh
- 51. đổi – Transform Vai trò của DTC là phân ly tín hiệu ban đầu thành các thành phần DC và AC của nó. Vai trò của IDTC là tái tạo lại tín hiệu (reconstruct) Định nghĩa DTC:cho một hàm vào f(i,j) i,j là các số nguyên nhận giá trị trên một phần của ảnh, phép biến đổi 2D DTC sẽ biến đổi f vào một hàm F(u,v) mới với u,v có cùng miền giá trị như i,j. Phép biến đổi được định nghĩa như sau
- 52. đổi – Transform Trong đó: Các hằng số C(u), C(v) được định nghĩa như sau: 2D Discrete Cosine Transform (2D DTC) được định nghĩa như sau: +Trong đó i, j, u, v =0,1,..,7, C(u), C(v) được định nghĩa như trên
- 53. đổi – Transform 2D Inverse Discrete Cosine Transform (2D IDTC) được định nghĩa như sau: Trong đó i, j, u, v =0,1,..,7 DTC là phép biến đổi tuyến tính (linear). Một phép biến đổi T được gọi là tuyến tính nếu và chỉ nếu T(αp+ßq)= αT(p)+ßT(q) Trong đó α, ß là các hằng số, p,q là các biến
- 54. đổi – Transform
- 55. đổi – Transform Wavelet Transform Mục tiêu của phép biến đổi Wavelet là phân rã tín hiệu vào thành các thành phần có thể xử lý được các thành phần này có thể biểu diễn cụ thể hay các thành phần có thể loại bỏ được để đạt được hiệu quả trong quá trình nén dữ liệu Với những thành phần này chúng ta có thể tái tạo lại tín hiệu ban đầu (xấp xỉ)
- 56. theo chuẩn JPEG Chuẩn JPEG: Joint Photographic Experts Group Là phương pháp nén có mất mát thông tin (lossy) Trình tự công nghệ nén ảnh JPEG: Phép biến đổi cosine rời rạc (DCT) Sắp xếp zigzag Lượng tử hóaMã hóa dữ liệu Phương thức thực hiện mã hóa: - Mã hóa tuần tự (Sequential DTC) - Mã hóa lũy tiến (Progressive DTC) - Mã hóa không mất mát thông tin (Sequential lossless - Mã hóa phân cấp (Hierarchical progressive)
- 57. theo chuẩn JPEG Các bước trong nén ảnh JPEG: 1. Biến đổi từ bộ màu RGB thành bộ màu YUV 2. Thực hiện biến đổi DCT trên các khối ảnh 3. Lượng tử hóa 4. Sắp xếp zigzag và thực hiện mã hóa RLE 5. Mã hóa entropy
- 58. theo chuẩn JPEG Sơ đồ nén ảnh tĩnh theo chuẩn JPEG
- 59. video: là chuỗi các ảnh tĩnh xuất hiện liên tiếp tạo cảm thụ chuyển động theo thời gian, gọi là chuỗi các frame ảnh (khung hình). Tốc độ xuất hiện các khung hình và độ phân giải ảnh là các yếu tố quan trọng của chất lượng video Ví dụ: 25 khung hình/s phải hiển thị 1 frame trong 40ms Không gian màu: - Hệ màu RGB - Hệ màu YUV:
- 60. 0.587G + 0.114B U=0.439(B-Y) và V=0.877(R-Y) -Hệ màu YCbCr Cb=U/2 + 0.5 Cr=V/1.6 + 0.5 2. Cấu trúc lấy mẫu và số hóa tín hiệu video: + Đối với truyền hình số NTSC và PAL, chuỗi video gồm các khung hình có độ phân giải 576 x 720, các dòng video chứa 720 điểm ảnh được lấy mẫu và số hóa theo các cấu trúc sau:
- 61. 4:2:0 YUV 4:1:1 R BG576 720 Y VU 360 Y U V 288 Y U V 180
- 62. quát về phương pháp nén video + Nén video không dùng kỹ thuật phát hiện và bù chuyển động (MJPEG) + Nén video dựa trên kỹ thuật phát hiện và bù chuyển động (MPEG, H26X), bao gồm: - Kỹ thuật nén ảnh tĩnh giảm độ dư thừa không gian (mã hóa intraframe) - Kỹ thuật đánh giá ước lượng chuyển động và mã hóa để giảm độ dư thừa giữa các frame (mã hóa interframe)
- 63. vào Biến đổi Lượng tử hóa Mã hóa Ảnh nén Đánh giá chuyển động Sơ đồ tổng quát nén video
- 64. giải pháp nén video a, Giảm tốc độ dòng bit + Dựa trên độ cảm thụ của mắt người + Cấu trúc lấy mẫu và số hóa + Dựa trên ý nghĩa các bit lượng tử hóa điểm ảnh b, Giảm độ dư thừa theo không gian: nén ảnh tĩnh + Dựa vào sự tương quan theo vị trí giữa các điểm ảnh lân cận trong một khung hình c, Giảm độ dư thừa theo thời gian: + Dựa vào sự tương quan theo thời gian giữa các điểm ảnh của các frame ảnh liên tiếp
- 65. hỗn hợp sử dụng các giải pháp trên: + Nén ảnh theo chuẩn MPEG 5. Nén ảnh theo chuẩn MPEG MPEG là chuẩn mã hóa và nén tín hiệu video- audio, gồm MPEG-1, MPEG-2, MPEG-4, MPRG-7 a, MPEG-1 (1992): Dùng để ghi CD-ROM, VCD, 352x240, 25-30 ảnh/s, tốc độ từ 1.2Mbps đến 1.5Mbps
- 66. Dùng cho DVD, TV số, HDTV, 720x 486, 30 ảnh/s, tốc độ từ 10Mbps đến 15Mbps c, MPEG-4 (1998): Dữ liệu DPT trong truyền thông và các ứng dụng tương tác ĐPT, đồng bộ dữ liệu d, MPEG-7 (2001): Chuẩn giao diện mô tả nôi dung dữ liệu ĐPT, hỗ trợ tìm kiếm, xử lý, quản lý dữ liệu ĐPT.
- 67. quy định trong chuẩn nén MPEG Phân loại các frame: - Frame I (Intraframe): là frame đầu tiên của chuỗi video, mã hóa JPEG - Frame P (Predicted frame): là frame được dự đoán tiếp theo - Frame P có kích thước nhỏ hơn frame I do được giảm độ dư thừa theo thời gian giữa các frame - Frame B (Bi-directional interpolated prediction): là frame được dự đoán nội suy 2 chiều - frame B có kích thước nhỏ hơn frame P do ưu điểm của nôi suy 2 chiều và do frame B có mức ưu tiên thấp nhất.
- 68. các frame theo chuẩn MPEG-1
|
