Tương tác người máy

Chia sẻ: Vang Thi | Ngày: | Loại File: PDF | Số trang:40

Thêm vào BST

Báo xấu

63
lượt xem 3
download

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

Mã hóa Entropy (Lossless coding) Là các dạng mã hóa nhằm loại bỏ các dư thừa thông tin. Thông tin sau khi giải mã bằng chính xác thông tin trước khi mã. Mã hóa dự đoán (Lossy coding) Là các dạng mã hóa nhằm loại bỏ các dư thừa thông tin. Thông tin sau khi giải có thể (ít nhiều) khác thông tin trước khi mã.

Chủ đề:

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

Lưu

Nội dung Text: Tương tác người máy

Lê Thanh Hà, TS. Phòng thí nghiệm Tương tác người máy
Số lượng dữ liệu âm thành, phim ảnh trở nên khổng lồ. Nhưng hệ thống lưu trữ và truyền tải hạn chế.  Cần những phương pháp giảm kích thước âm thanh và hình ảnh để lưu trữ và truyền tải hiệu quả. 11/4/2013 Lê Thanh Hà 2
Sự dư thừa về mặt không gian chính là ở giữa các điểm của một ảnh. Nói rõ hơn, các điểm ảnh thường có quan hệ mật thiết với nhau. 11/4/2013 Lê Thanh Hà 3
Mã hóa Entropy (Lossless coding) Là các dạng mã hóa nhằm loại bỏ các dư thừa thông tin. Thông tin sau khi giải mã bằng chính xác thông tin trước khi mã. Mã hóa dự đoán (Lossy coding) Là các dạng mã hóa nhằm loại bỏ các dư thừa thông tin. Thông tin sau khi giải có thể (ít nhiều) khác thông tin trước khi mã. 11/4/2013 Lê Thanh Hà 4
Đo thông tin Giả thiết một biểu tượng x với xác suất xuất hiện p, thì nội dung thông tin của nó (thông tin chứa trong biểu tượng) là: I ( x)   log( p ( x)) Độ đo thông tin không phụ thuộc vào giá trị biểu tượng Độ đo thông tin chỉ phụ thuộc vào xác suất của biểu tượng Khi cơ sở của hàm log là 2 thì đơn vị tính của độ đo thông tin gọi là bit. 11/4/2013 Lê Thanh Hà 5
Entropy thông tin Entropy được định nghĩa là trung bình thông tin đối với mỗi biểu tượng trong một nguồn. Entropy, H, được thể hiện như sau: H ( X )   p ( x) I ( x)    p ( x) log( p ( x)) x x Từ định nghĩa này, entropy của một nguồn thông tin là một hàm của xác suất xảy ra. Entropy đạt giá trị cực đại khi mọi biểu tượng đều xảy ra với xác suất như nhau 11/4/2013 Lê Thanh Hà 6
Ví dụ nguồn thông tin digital ={0,1}, p(0)=1/3, p(1)=1-p(0)=2/3 p(1)=1- H ( X )   p (0) log( p (0)  p (1) log( p (1)) 1 1 2 2   log( )  log( ) 3 3 3 3  0.646 11/4/2013 Lê Thanh Hà 7
Đồ thị Entropy là 1 hàm lồi với p Khi p tiến gần tới 0 hoặc 1 thì nguồn  mang càng ít thông tin. Cực đại tại p=0.5 11/4/2013 Lê Thanh Hà 8
Tính Entropy H(X) của: a p (a)  1/ 2 b p (b)  1/ 4  X  c p (c)  1/ 8 d  p (d )  1/ 8 11/4/2013 Lê Thanh Hà 9
11/4/2013 Lê Thanh Hà 10
1 2 1 2 1 1 1 3 3 2 3 1   1 5 6 5 5 1 I   2 5 7 7 4 2 1 3 3 2 3 1   1 2 1 1 1 2 11/4/2013 Lê Thanh Hà 11
Tổng số lượng bit dùng để thể hiện dữ liệu có thể tính được trên nội dung thông tin. Những biểu tượng với khả năng xảy ra cao được thể hiện bằng các đoạn mã ngắn trong khi đó những biểu tượng với khả năng xảy ra thấp được thể hiện bằng những đoạn mã dài hơn Kết quả là giảm được số lượng bit trung bình cần cho một biểu tượng 11/4/2013 Lê Thanh Hà 12
Mã C cho một nguồn X là 1 ánh xạ từ tập  (miền của X), tới D*. D* là tập các chuỗi ký tự mã. Ví dụ: Nguồn X là màu sắc,  = {Red, Blue} C(Red)=00, C(Blue)=11 là mã cho tập ={Red,Blue) với D={0,1} Độ dài trung bình của mã C: L(C )   p ( x)l ( x) x 11/4/2013 Lê Thanh Hà 13
Mã C được gọi là mà tiền tố (prefix code) nếu không có mã nào là tiền tố của mã nào. 00 là tiền tố của 001 Mã C(1)=0, C(2)=10, C(3)=110, C(4)=111 là mà tiền tố Mã tiền tố cho phép giải mã mà không phải duyệt đến cuối chuỗi mã. 11/4/2013 Lê Thanh Hà 14
Ví dụ - mã hóa độ dài cố định Biểu tượng x Xác suất Đoạn mã C(x) Độ dài đoạn mã L(c) A 0.75 00 2 B 0.125 01 2 C 0.0625 10 2 D 0.0625 11 2 Số bit trung bình/ biểu tượng = 0.75*2 + 0.125*2 + 0.0625*2 + 0.0625*2 = 2.0 bits/biểu tượng 11/4/2013 Lê Thanh Hà 15
Ví dụ - mã hóa có độ dài không cố định Biểu tượng Xác suất Đoạn mã Độ dài đoạn mã A 0.75 0 1 B 0.125 10 2 C 0.0625 110 3 D 0.0625 111 3 Số bit trung bình/ biểu tượng = 0.75*1 + 0.125*2 + 0.0625*3 + 0.0625*3 = 1.375 bits/biểu tượng (tiết kiệm 30% mà không mất dữ liệu) 11/4/2013 Lê Thanh Hà 16
Exp- Exp-Golomb codes Thường được sử dụng trong nén video (nén các motion vectors) Mã Huffman (Huffman codes) Thường dùng trong nén dữ liệu, và nén ảnh tĩnh. Mã số học (Arthimetic codes) Nén video trong chuẩn H.264/AVC Mã hóa chuỗi liên tiếp 11/4/2013 Lê Thanh Hà 17
Đơn giản dễ cài đặt cho các thiết bị phần cứng. Thích hợp với các nguồn có hàm phân bố xác xuất dạng mũ (laplace, exponential) Thường được sử dụng để mã hóa độ dài của các motion vectors. 11/4/2013 Lê Thanh Hà 18
Mã Exp-Golomb có cấu trúc như sau: Exp- [M zeros][1][INFO] Trong đó INFO là một trường có M bit thông tin M = floor(log2[code_num+1]) INFO = code_num+1 – 2M Giải mã: Đọc M ký tự ‘0’, đọc tiếp ký tự ‘1’ Đọc M bít của trường INFO Code_num = 2M + INFO - 1 11/4/2013 Lê Thanh Hà 19
Mã Cho số không dấu Cho số có dấu 1 0 0 010 1 1 011 2 -1 00100 3 2 00101 4 -2 00110 5 3 00111 6 -3 0001000 7 4 0001001 8 -4 0001010 9 5 0001011 10 -5 0001100 11 6 ... ... ... 11/4/2013 Lê Thanh Hà 20