Lê Thanh Hà, TS. Lê Thanh Hà, TS. Phòng thí nghiệm Tương tác người máy 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ở Số lượng dữ liệu âm thành, phim ảnh trở nên khổng lồ. nên khổng lồ. Nhưng hệ thống lưu trữ và truyền tải hạn Nhưng hệ thống lưu trữ và truyền tải hạn chế. chế.

Cần những phương pháp giảm kích thước 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 âm thanh và hình ảnh để lưu trữ và truyền tải hiệu quả. tải hiệu quả.

2

Lê Thanh Hà 11/4/2013

Sự dư thừa về mặt không Sự dư thừa về mặt không

gian chính là ở giữa các gian chính là ở giữa các điểm của một ảnh. Nói rõ điểm của một ảnh. Nói rõ hơn, các điểm ảnh hơn, các điểm ảnh thường có quan hệ mật thường có quan hệ mật thiết với nhau. thiết với nhau.

3

Lê Thanh Hà 11/4/2013

Mã hóa Entropy (Lossless coding) 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. 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 Thông tin sau khi giải mã bằng chính xác thông tin trước khi mã. khi mã.

Mã hóa dự đoán (Lossy coding) 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. 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 Thông tin sau khi giải có thể (ít nhiều) khác thông tin trước khi mã. khi mã.

4

Lê Thanh Hà 11/4/2013

Đo thông tin Đo thông tin

với xác suất xuất hiện pp, , Giả thiết một biểu tượng x x với xác suất xuất hiện Giả thiết một biểu tượng thì nội dung thông tin của nó (thông tin chứa trong thì nội dung thông tin của nó (thông tin chứa trong biểu tượng) là: 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 Độ đo thông tin không phụ thuộc vào giá trị biểu tượng tượng Độ đo thông tin chỉ phụ thuộc vào xác suất của biểu Độ đo thông tin chỉ phụ thuộc vào xác suất của biểu tượng tượng Khi cơ sở của hàm log là 2 thì đơn vị tính của độ đo 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. thông tin gọi là bit.

5

Lê Thanh Hà 11/4/2013

Entropy thông tin Entropy thông tin

Entropy được định nghĩa là trung bình thông tin đối với mỗi Entropy được định nghĩa là trung bình thông tin đối với mỗi H, được thể hiện như biểu tượng trong một nguồn. Entropy, H, được thể hiện như biểu tượng trong một nguồn. Entropy, sau: 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 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 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 biểu tượng đều xảy ra với xác suất như nhau

6

Lê Thanh Hà 11/4/2013

={0,1}, Ví dụ nguồn thông tin digital ={0,1}, Ví dụ nguồn thông tin digital p(0)=2/3 p(0)=1/3, p(1)=1--p(0)=2/3 p(0)=1/3, p(1)=1

H X (

)

 

p

(0) log(

p

(0)

p

(1) log(

p

(1))

 

log(

)

1 log( ) 3

2 3

2 3

1 3 0.646

7

Lê Thanh Hà 11/4/2013

Đồ thị Entropy Đồ thị Entropy

là 1 hàm lồi với p là 1 hàm lồi với p Khi p tiến gần tới 0 hoặc Khi p tiến gần tới 0 hoặc mang càng 1 thì nguồn  mang càng 1 thì nguồn ít thông tin. ít thông tin. Cực đại tại p=0.5 Cực đại tại p=0.5

8

Lê Thanh Hà 11/4/2013

Tính Entropy H(X) của: Tính Entropy H(X) của:

a p a

 ( ) 1/ 2

b p b

 ( ) 1/ 4

X

c p c d p d

 ( ) 1/ 8  ( ) 1/ 8

       

9

Lê Thanh Hà 11/4/2013

10

Lê Thanh Hà 11/4/2013

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

         

        

Lê Thanh Hà 11/4/2013 11

Tổng số lượng bit dùng để thể hiện dữ liệu có thể 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. 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 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 đó 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 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 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 Kết quả là giảm được số lượng bit trung bình cần cho một biểu tượng cho một biểu tượng

12

Lê Thanh Hà 11/4/2013

Mã C cho một nguồn X là 1 ánh xạ từ tập  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ý (miền của X), tới D*. D* là tập các chuỗi ký tự mã. Ví dụ: tự mã. Ví dụ:

Nguồn X là màu sắc, = {Red, Blue} Nguồn X là màu sắc,  = {Red, Blue} C(Red)=00, C(Blue)=11 là mã cho tập C(Red)=00, C(Blue)=11 là mã cho tập ={Red,Blue) với D={0,1} ={Red,Blue) với D={0,1}

L C (

)

p x l x ( ) ( )

Độ dài trung bình của mã C: Độ dài trung bình của mã C:

 

 x

13

Lê Thanh Hà 11/4/2013

Mã C được gọi là mà tiền tố (prefix code) 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. 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 00 là tiền tố của 001 Mã C(1)=0, C(2)=10, C(3)=110, C(4)=111 là mà Mã C(1)=0, C(2)=10, C(3)=110, C(4)=111 là mà tiền tố tiền tố Mã tiền tố cho phép giải mã mà không phải duyệt Mã tiền tố cho phép giải mã mà không phải duyệt đến cuối chuỗi mã. đến cuối chuỗi mã.

14

Lê Thanh Hà 11/4/2013

mã hóa độ dài cố định Ví dụ -- mã hóa độ dài cố định Ví dụ

Biểu tượng x

Xác suất

Đoạn mã C(x)

0.75

0.125

0.0625

A B C

00 01 10

Độ dài đoạn mã L(c) 2 2 2

0.0625

D

11

2

= 0.75*2 + 0.125*2 + 0.0625*2 + 0.0625*2 =

Số bit trung bình/ biểu tượng 2.0 bits/biểu tượng

15

Lê Thanh Hà 11/4/2013

mã hóa có độ dài không cố định Ví dụ -- mã hóa có độ dài không cố định Ví dụ Xác suất

Biểu tượng

Đoạn mã

Độ dài đoạn mã

0.75

0.125

A B

0 10

1 2

0.0625

C

110

3

0.0625

D

111

3

= 0.75*1 + 0.125*2 + 0.0625*3 + 0.0625*3 =

Số bit trung bình/ biểu tượng 1.375 bits/biểu tượng (tiết kiệm 30% mà không mất dữ liệu)

16

Lê Thanh Hà 11/4/2013

Golomb codes ExpExp--Golomb codes

Thường được sử dụng trong nén video (nén các motion Thường được sử dụng trong nén video (nén các motion vectors) vectors)

Mã Huffman (Huffman codes) Mã Huffman (Huffman codes)

Thường dùng trong nén dữ liệu, và nén ảnh tĩnh. Thường dùng trong nén dữ liệu, và nén ảnh tĩnh.

Mã số học (Arthimetic codes) Mã số học (Arthimetic codes)

Nén video trong chuẩn H.264/AVC Nén video trong chuẩn H.264/AVC

Mã hóa chuỗi liên tiếp Mã hóa chuỗi liên tiếp

17

Lê Thanh Hà 11/4/2013

Đơn giản dễ cài đặt cho các thiết bị phần Đơn giản dễ cài đặt cho các thiết bị phần cứng. cứng. Thích hợp với các nguồn có hàm phân bố 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) xác xuất dạng mũ (laplace, exponential) Thường được sử dụng để mã hóa độ dài của Thường được sử dụng để mã hóa độ dài của các motion vectors. các motion vectors.

18

Lê Thanh Hà 11/4/2013

Golomb có cấu trúc như sau: Mã Exp--Golomb có cấu trúc như sau: Mã Exp [M zeros][1][INFO] [M zeros][1][INFO]

Trong đó INFO là một trường có M bit thông tin Trong đó INFO là một trường có M bit thông tin [code_num+1]) M = floor(log22[code_num+1]) M = floor(log INFO = code_num+1 –– 22MM INFO = code_num+1

Giải mã: Giải mã:

Đọc M ký tự ‘0’, đọc tiếp ký tự ‘1’ Đọc M ký tự ‘0’, đọc tiếp ký tự ‘1’ Đọc M bít của trường INFO Đọc M bít của trường INFO Code_num = 2MM + INFO + INFO -- 11 Code_num = 2

Lê Thanh Hà 11/4/2013 19

Mã 1 010 011 00100 00101 00110 00111 0001000 0001001 0001010 0001011 0001100 ...

Cho số không dấu 0 1 2 3 4 5 6 7 8 9 10 11 ...

Cho số có dấu 0 1 -1 2 -2 3 -3 4 -4 5 -5 6 ...

20

Lê Thanh Hà 11/4/2013

Được Huffman phát minh vào năm 1952 tại Được Huffman phát minh vào năm 1952 tại MIT.MIT. Đây là một dạng mã tiền tố gán mỗi ký hiệu Đây là một dạng mã tiền tố gán mỗi ký hiệu với một mã dựa theo tần xuất xuất hiện của với một mã dựa theo tần xuất xuất hiện của mã đó. mã đó.

Lê Thanh Hà 11/4/2013 21

Sinh ra mã Huffman Sinh ra mã Huffman

22

Lê Thanh Hà 11/4/2013

Từ phải sang trái; Hai nhánh thấp nhất tạo thành một nút; Sắp xếp Từ phải sang trái; Hai nhánh thấp nhất tạo thành một nút; Sắp xếp

lại giá trị các nút lại giá trị các nút

23

Lê Thanh Hà 11/4/2013

Xắp xếp lại cây cho dễ nhìn; Quá trình mã hóa đi từ trái qua phải; 0-- Xắp xếp lại cây cho dễ nhìn; Quá trình mã hóa đi từ trái qua phải; 0

nhánh dưới nhánh trên, 1-- nhánh dưới nhánh trên, 1

24

Lê Thanh Hà 11/4/2013

Những hạn chế của mã Huffman: Những hạn chế của mã Huffman:

Các đoạn mã Huffman phải có số lượng bit nguyên. Các đoạn mã Huffman phải có số lượng bit nguyên.

Ví dụ: mã nguồn có 2 biểu tượng, mã Huffman sẽ gán 0 cho Ví dụ: mã nguồn có 2 biểu tượng, mã Huffman sẽ gán 0 cho một biểu tượng, và gán 1 cho biểu tượng kia. Độ dài mã một biểu tượng, và gán 1 cho biểu tượng kia. Độ dài mã trung bình luôn là 1. Nếu p(0)=0.9999, p(1)=0.0001. trung bình luôn là 1. Nếu p(0)=0.9999, p(1)=0.0001. Entropy=0.00147 bits/biểu tượng. Entropy=0.00147 bits/biểu tượng. Xác suất của các biểu tượng phải biết trước khi giải mã. Xác suất của các biểu tượng phải biết trước khi giải mã. Nếu không, chúng phải được truyền tới bộ giải mã cùng với Nếu không, chúng phải được truyền tới bộ giải mã cùng với dữ liệu đã được mã hóa dữ liệu đã được mã hóa Khi số lượng biểu tượng nhiều, bảng mã sẽ trở nên rất lớn Khi số lượng biểu tượng nhiều, bảng mã sẽ trở nên rất lớn

25

Lê Thanh Hà 11/4/2013

Mã hóa số học (Arithmetic Coding) Mã hóa số học (Arithmetic Coding)

Khắc phục những hạn chế của mã hóa Huffman: Khắc phục những hạn chế của mã hóa Huffman: cho phép mã hóa với chiều dài không nguyên, và cho phép mã hóa với chiều dài không nguyên, và phân bố xác suất có thể tính trong thời gian thực phân bố xác suất có thể tính trong thời gian thực Hoạt động bằng cách thay một chuỗi các biểu Hoạt động bằng cách thay một chuỗi các biểu tượng bằng một số thực duy nhất. tượng bằng một số thực duy nhất.

26

Lê Thanh Hà 11/4/2013

 Mã nguồn {A, B, C}, chuỗi cần nén BCA  p(A) = 0.6, p(B) = 0.3, p(C) = 0.1

 Chuỗi cần nén bắt đầu bởi A, B, và C được ánh xạ tương ứng tới đoạn nửa mở (haft-open) [0, 0.6), [0.6, 0.9), và [0.9, 1), theo xác xuất của chúng.

C

BC

BCC

1 0.9

0.9 0.87

0.9 0.897

B

BB

BCB

0.6

0.78

0.888

BCA

A

BA

0

0.87

0.6 Lê Thanh Hà

27

11/4/2013

Mã nguồn{A, B, C}, chuỗi cần nén BCA Mã nguồn{A, B, C}, chuỗi cần nén BCA p(A) = 0.6, p(B) = 0.3, p(C) = 0.1 p(A) = 0.6, p(B) = 0.3, p(C) = 0.1

Đoạn đoạn đó lại tiếp tục được chia nhỏ hơn thành các đoạn con Đoạn đoạn đó lại tiếp tục được chia nhỏ hơn thành các đoạn con [0.6, 0.78), [0.78, 0.87), [0.87, 0.9), cho các chuỗi được bắt đầu với [0.6, 0.78), [0.78, 0.87), [0.87, 0.9), cho các chuỗi được bắt đầu với BA, BB, BC. Chú ý rằng tỉ lệ độ dài các đoạn tuân theo tỉ lệ của BA, BB, BC. Chú ý rằng tỉ lệ độ dài các đoạn tuân theo tỉ lệ của xác suất các biểu tượng: xác suất các biểu tượng:

0.18 : 0.09 : 0.03 = 6 : 3 : 1 = p(A) : p(B) : p(C) 0.18 : 0.09 : 0.03 = 6 : 3 : 1 = p(A) : p(B) : p(C)

C

BC

BCC

1 0.9

0.9 0.87

0.9 0.897

B

BB

BCB

0.6

0.78

0.888

A

BA

BCA

0

0.6

0.87

Lê Thanh Hà 11/4/2013 28

Mã nguồn{A, B, C} , chuỗi cần nén BCA Mã nguồn{A, B, C} , chuỗi cần nén BCA p(A) = 0.6, p(B) = 0.3, p(C) = 0.1 p(A) = 0.6, p(B) = 0.3, p(C) = 0.1

Tương tự như vậy, đoạn [0.87, 0.9) tiếp tục được chia nhỏ thành 3 Tương tự như vậy, đoạn [0.87, 0.9) tiếp tục được chia nhỏ thành 3 đoạn con, và những chuỗi bắt đầu bởi BCA được ánh xạ tới đoạn con, và những chuỗi bắt đầu bởi BCA được ánh xạ tới [0.87, 0.888). [0.87, 0.888).

C

BC

BCC

1 0.9

0.9 0.87

0.9 0.897

B

BB

BCB

0.6

0.78

0.888

A

BA

BCA

0

0.87

0.6 Lê Thanh Hà

11/4/2013 29

Mã nguồn {A, B, C} , chuỗi cần nén BCA Mã nguồn {A, B, C} , chuỗi cần nén BCA p(A) = 0.6, p(B) = 0.3, p(C) = 0.1 p(A) = 0.6, p(B) = 0.3, p(C) = 0.1

 0.11011 ,

0.87

0.11100

0.888

 .

2 điểm đầu của đoạn [0.87, 0.888) được biểu diễn bằng số nhị phân: 2 điểm đầu của đoạn [0.87, 0.888) được biểu diễn bằng số nhị phân: 1 5 2 1 7 2

1   2 1   2

1 4 2 1 3 2

1 2 2 1 2 2

C

BC

BCC

1 0.9

0.9 0.87

0.9 0.897

B

BB

BCB

0.6

0.78

0.888

A

BA

BCA

0

0.87

Lê Thanh Hà 0.6 11/4/2013 30

Mã nguồn {A, B, C} , chuỗi cần nén BCA Mã nguồn {A, B, C} , chuỗi cần nén BCA p(A) = 0.6, p(B) = 0.3, p(C) = 0.1 p(A) = 0.6, p(B) = 0.3, p(C) = 0.1

Bộ mã hóa có thể gửi một số bất kỳ trong đoạn [0.87, 0.9) để cho Bộ mã hóa có thể gửi một số bất kỳ trong đoạn [0.87, 0.9) để cho biết rằng chuỗi cần nén được bắt đầu với BCA. Ví dụ, nó có thể biết rằng chuỗi cần nén được bắt đầu với BCA. Ví dụ, nó có thể gửi chuỗi 3 bits, 111, tương ứng với số 0.875 trong hệ thập phân. gửi chuỗi 3 bits, 111, tương ứng với số 0.875 trong hệ thập phân.

C

BC

BCC

1 0.9

0.9 0.87

0.9 0.897

B

BB

BCB

0.6

0.78

0.888

BCA

A

BA

0

0.87

0.6 Lê Thanh Hà

11/4/2013 31

Mã nguồn {A, B, C} , chuỗi cần nén BCA Mã nguồn {A, B, C} , chuỗi cần nén BCA p(A) = 0.6, p(B) = 0.3, p(C) = 0.1 p(A) = 0.6, p(B) = 0.3, p(C) = 0.1

Nhận được 111, bộ giải mã sẽ thực hiện lại thủ tục chia đoạn như Nhận được 111, bộ giải mã sẽ thực hiện lại thủ tục chia đoạn như giải mã, và thu được chuỗi bắt đầu với BCA, do nó biết 0.875 nằm giải mã, và thu được chuỗi bắt đầu với BCA, do nó biết 0.875 nằm trong đoạn [0.87, 0.888). trong đoạn [0.87, 0.888).

C

BC

BCC

1 0.9

0.9 0.87

0.9 0.897

B

BB

BCB

0.6

0.78

0.888

BCA

A

BA

0

0.87

0.6 Lê Thanh Hà

11/4/2013 32

Mã nguồn {A, B, C} , chuỗi cần nén BCA Mã nguồn {A, B, C} , chuỗi cần nén BCA p(A) = 0.6, p(B) = 0.3, p(C) = 0.1 p(A) = 0.6, p(B) = 0.3, p(C) = 0.1

Tuy nhiên, 0.875 có thể là biểu diễn của B, BA, hoặc BAC. Dùng Tuy nhiên, 0.875 có thể là biểu diễn của B, BA, hoặc BAC. Dùng biểu tượng bổ sung EOS (end of sequence) để báo hiệu chuỗi cần biểu tượng bổ sung EOS (end of sequence) để báo hiệu chuỗi cần nén đã kết thúc. nén đã kết thúc.

C

BC

BCC

1 0.9

0.9 0.87

0.9 0.897

B

BB

BCB

0.6

0.78

0.888

BCA

A

BA

0

0.6

0.87

Lê Thanh Hà 11/4/2013 33

Lê Thanh Hà 11/4/2013 34

Biểu diễn nhị phân: Biểu diễn nhị phân:

i

2^-i

X

Bit

1

0.3203125

0

0.5

2

0.3203125

1

0.25

3

0.0703125

0

0.125

4

0.0703125

1

0.0625

5

0.0078125

0

0.03125

6

0.0078125

0

0.015625

7

0.0078125

1

0.0078125

8

0

0

0.00390625

Lê Thanh Hà 11/4/2013 35

Những vấn đề cần quan tâm của mã số học Những vấn đề cần quan tâm của mã số học khi sử dụng công nghiệp: khi sử dụng công nghiệp:

Thực hiện trên miền nguyên thay bằng miền thập Thực hiện trên miền nguyên thay bằng miền thập phân. phân. Phân đoạn sẽ giảm rất nhanh trong quá trình mã Phân đoạn sẽ giảm rất nhanh trong quá trình mã hóa, cần có cơ chế thay đổi tỷ lệ (rescale) hóa, cần có cơ chế thay đổi tỷ lệ (rescale) Tham khảo kỹ thuật nén CABAC của chuẩn nén Tham khảo kỹ thuật nén CABAC của chuẩn nén video H.264. video H.264.

Lê Thanh Hà 11/4/2013 36

Hãy sử dụng mã số học để nén chuỗi: Hãy sử dụng mã số học để nén chuỗi: badcd badcd Các biểu tượng có xác suất như sau: Các biểu tượng có xác suất như sau:

X

a p a b p b c p c d p d

 ( ) 1/ 2  ( ) 1/ 4 ( ) 1/ 8   ( ) 1/ 8

       

Lê Thanh Hà 11/4/2013 37

length coding): Mã hóa chuỗi liên tiếp (Run--length coding): Mã hóa chuỗi liên tiếp (Run Chuỗi các biểu tượng giống nhau được gộp lại và Chuỗi các biểu tượng giống nhau được gộp lại và biểu diễn bằng một đoạn mã biểu diễn bằng một đoạn mã Bắt đầu bằng một ký tự đặc biệt, tiếp theo đó là Bắt đầu bằng một ký tự đặc biệt, tiếp theo đó là biểu tượng và số lần lặp lại biểu tượng và số lần lặp lại Là một kỹ thuật nén được sử dụng trong chuẩn Là một kỹ thuật nén được sử dụng trong chuẩn H.264, CAVLC H.264, CAVLC

38

Lê Thanh Hà 11/4/2013

Trường hợp đơn giản nhất của phương nén Trường hợp đơn giản nhất của phương nén này là gộp các biểu tưởng liên tiếp lại với này là gộp các biểu tưởng liên tiếp lại với nhau, và thay bằng cặp [N][S] nhau, và thay bằng cặp [N][S]

N là số lượng biểu tượng N là số lượng biểu tượng S symbol S symbol

Ví dụ chuỗi: aaaabbbddaaddccccccca Ví dụ chuỗi: aaaabbbddaaddccccccca Được nén lại thành: 4a3b2d2a2d7c1a Được nén lại thành: 4a3b2d2a2d7c1a

Lê Thanh Hà 11/4/2013 39

Chỉ áp dụng với chuỗi có số lượng biểu tượng Chỉ áp dụng với chuỗi có số lượng biểu tượng liên tiếp >3 liên tiếp >3 Thay thế chuỗi đó bằng [E][S][N--1]1] Thay thế chuỗi đó bằng [E][S][N

E: Ký hiệu đặc biệt E: Ký hiệu đặc biệt S: Biểu tượng S: Biểu tượng N: Số lượng biểu tượng liên tiếp N: Số lượng biểu tượng liên tiếp

Lê Thanh Hà 11/4/2013 40