Nén ảnh trong thông tin số thế hệ sau

Học viện Công nghệ Bưu chính Viễn thông

Trần Mạnh Tuấn

Nén ảnh trong thông tin số thế hệ sau

Chuyên ngành: Kỹ thuật Viễn thông

- Mã số: 62.52.70.05

- Họ và tên NCS: Trần Mạnh Tuấn

- Người hướng dẫn khoa học:

1- TS. Phùng Kim Anh

2- TS. Nguyễn Hữu Hậu

2014

i

LỜI CAM ĐOAN

Tôi cam đoan các kết quả nghiên cứu đƣa ra trong luận án này dựa trên các

kết quả thu đƣợc trong quá trình nghiên cứu của riêng tôi, không sao chép bất kỳ kết

quả nghiên cứu nào của các tác giả khác. Nội dung của luận án có tham khảo và sử

dụng một số thông tin, tài liệu từ các nguồn sách, tạp chí đƣợc liệt kê trong danh

mục các tài liệu tham khảo.

Trần Mạnh Tuấn

ii

LỜI CẢM ƠN

Luận án Tiến sĩ kỹ thuật này đƣợc thực hiện tại Học viện Công nghệ Bƣu

chính Viễn thông. Tôi xin chân thành cảm ơn TS. Phùng Kim Anh và TS. Nguyễn

Hữu Hậu đã trực tiếp tận tình hƣớng dẫn, giúp đỡ, tạo mọi điều kiện thuận lợi cho

tôi trong suốt quá trình nghiên cứu.

Tôi xin cảm ơn Ban lãnh đạo Học viện Công nghệ Bƣu chính Viễn thông,

khoa Quốc tế và Sau đại học đã giúp đỡ tôi rất nhiều trong quá trình nghiên cứu, tạo

mọi điều kiện thuận lợi về mặt thủ tục cho hoạt động nghiên cứu của tôi.

Tôi xin cảm ơn tập thể lãnh đạo Cục Viễn thông - Bộ Thông tin và Truyền

thông cùng các đồng nghiệp đã luôn động viên, tạo điều kiện thuận lợi để tôi hoàn

thành luận án.

Cuối cùng, tôi xin đƣợc bày tỏ lòng biết ơn sâu sắc tới toàn thể gia đình, bạn

bè đã luôn động viên, khích lệ tinh thần để tôi có đủ nghị lực hoàn thành luận án.

Trần Mạnh Tuấn

iii

MỤC LỤC

LỜI CAM ĐOAN ....................................................................................................... i

LỜI CẢM ƠN ............................................................................................................ ii

MỤC LỤC................................................................................................................. iii

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT..............................................v

DANH MỤC CÁC BẢNG....................................................................................... vii

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ................................................................. viii

MỞ ĐẦU.....................................................................................................................1

CHƢƠNG 1: TỔNG QUAN VỀ NÉN VIDEO..........................................................7

1.1.Giới thiệu........................................................................................................7

1.2.Độ dƣ trong tín hiệu video, nhu cầu cần thiết nén video ...............................8

1.2.1. Độ dƣ trong tín hiệu video ...................................................................8

1.2.2. Nhu cầu cần thiết nén video ...............................................................13

1.3.Khái niệm về nén video ...............................................................................13

1.4.Yêu cầu về ứng dụng nén video, một số kỹ thuật nén video .......................18

1.4.1. Yêu cầu về ứng dụng nén video .........................................................18

1.4.2. Một số kỹ thuật nén video ..................................................................21

1.5.Kết luận ........................................................................................................33

CHƢƠNG 2: TỔNG QUAN VỀ ƢỚC LƢỢNG CHUYỂN ĐỘNG CỦA ẢNH....34

2.1.Giới thiệu......................................................................................................34

2.2.Ƣớc lƣợng chuyển động và các phƣơng pháp ƣớc lƣợng chuyển động ......34

2.2.1. Ƣớc lƣợng chuyển động .....................................................................34

2.2.2.Các phƣơng pháp ƣớc lƣợng chuyển động.........................................39

2.3.Kết luận ........................................................................................................62

CHƢƠNG 3: ƢỚC LƢỢNG CHUYỂN ĐỘNG BẰNG CÁC GIẢI PHÁP MỚI...64

3.1.Giới thiệu......................................................................................................64

3.2.Ƣớc lƣợng chuyển động bằng Kalman ........................................................65

3.2.1. Đặt bài toán.........................................................................................65

3.2.2. Ƣớc lƣợng chuyển động của ảnh bằng thuật toán Kalman ................66

3.3.Ƣớc lƣợng chuyển động tối ƣu của ảnh trong video....................................72

3.3.1. Đặt bài toán.........................................................................................72

3.3.2. Ƣớc lƣợng chuyển động tối ƣu của ảnh trong video..........................73

iv

3.4.Ƣớc lƣợng chuyển động của ảnh bằng phƣơng pháp mù ............................76

3.4.1. Đặt bài toán.........................................................................................76

3.4.2. Ƣớc lƣợng chuyển động của ảnh bằng phƣơng pháp mù...................77

3.5.Kết luận ........................................................................................................92

CHƢƠNG 4: MỘT SỐ KẾT QUẢ TÍNH TOÁN SỐ..............................................94

4.1.Giới thiệu......................................................................................................94

4.2.Thiết lập mô phỏng ......................................................................................94

4.2.1. Phƣơng pháp Bayes............................................................................94

4.2.2. Phƣơng pháp Kalman .........................................................................97

4.3.Kết quả và bàn luận....................................................................................100

4.4.Kết luận ......................................................................................................109

KẾT LUẬN VÀ KIẾN NGHỊ.................................................................................110

DANH MỤC CÔNG TRÌNH CÔNG BỐ CỦA TÁC GIẢ....................................113

DANH MỤC TÀI LIỆU THAM KHẢO................................................................114

v

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

BDM Block Distortion Measure Độ đo biến dạng khối

BMA Block-Matching Algorithm Thuật toán phối hợp khối

BMME Block-Matching Motion Estimation Ƣớc lƣợng chuyển động

phối hợp khối

DC Direct Current Dòng một chiều

DCT Discrete Cosine Transform Biến đổi Cosine rời rạc

DFD Displaced Frame Difference Hiệu dịch chuyển khung

DFT Discrete Fourier Transform Biến đổi Fourier rời rạc

DMS Discrete Memoryless Source Nguồn không nhớ rời rạc

DPCM Differential Pulse Code Modulation Điều chế xung mã vi sai

DVB-H Digital Video Broadcasting - Handheld Phát quảng bá video kỹ thuật số -

Thiết bị cầm tay

ECC Error Correction Code Mã sửa sai

FD Frame Difference Độ lệch khung

FFT Fast Fourier Transform Biến đổi Fourier nhanh

FT Fourier Transform Biến đổi Fourier

HD Horizontal Difference Độ lệch trục ngang

HDTV High Definition Television Truyền hình độ phân giải cao

HVS Human Visual System Hệ thống nhìn của con ngƣời

IBM Ideal Binary Mask Mặt nạ nhị phân lý tƣởng

IDCT Inverse DCT Biến đổi ngƣợc DCT

IDFT Inverse DFT Biến đổi ngƣợc DFT

KLT Karhunen-Loève Transform Biến đổi Karhunen-Loève

LMS Least Mean Square Bình phƣơng trung bình tối thiểu

MAE Mean Absolute Error Sai số tuyệt đối trung bình

MAP Maximum A posteriori Probability Cực đại xác suất hậu nghiệm

MC Motion Compensation Bù chuyển động

vi

ML Maximum Likelihood Hợp lý cực đại

MPEG Moving Picture Experts Group Nhóm chuyên gia về hình ảnh động

MRF Markov Random Field Trƣờng ngẫu nhiên Markov

MSE Mean Squared Error Sai số trung bình bình phƣơng

NCCF Normalized Cross Correlation Function Hàm tƣơng quan chéo chuẩn hóa

NGN Next Generation Network Mạng thế hệ kế tiếp

NTSC National Television System Committee Ủy ban truyền hình quốc gia

PSNR Peak Signal to Noise Ratio Tỷ số tín hiệu đỉnh trên nhiễu

SAD Sum of Absolute Differences Tổng các sai phân tuyệt đối

SSD Sum Squared Difference Tổng các sai phân bình phƣơng

TSVQ Tree-Structured Vector Quantizers Lƣợng tử véctơ có cấu trúc cây

TV Television Máy thu hình

VD Vertical Difference Độ lệch trục đứng

VLC Variable Length Coding Mã hóa với độ dài từ mã thay đổi

VQ Vector Quantization Lƣợng tử véctơ

2D Two-Dimensional 2 chiều

3D Three-Dimensional 3 chiều

3G Third-Generation Thế hệ thứ ba

vii

DANH MỤC CÁC BẢNG

Bảng 2.1 Độ phức tạp tính toán của SSD, SAD và NCCF với khối

N N .............51

Bảng 4.1 Bảng thống kê thời gian tính toán theo phƣơng pháp Bayes...................107

Bảng 4.2 Bảng thống kê thời gian tính toán theo phƣơng pháp Kalman................108

viii

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

Hình 1.1 Nén video trong truyền video.......................................................................8

Hình 1.2 Hàm tự tƣơng quan theo chiều ngang của một số bức ảnh ..........................9

Hình 1.3 Phổ công suất đặc trƣng của tín hiệu TV quảng bá ...................................10

Hình 1.4 (a) khung thứ 21 và (b) khung thứ 22 của dãy ảnh “Hoa hậu Mỹ” ...........11

Hình 1.5 Hệ thống nén video tổng quát ....................................................................15

Hình 1.6 Tính chu kỳ tái cấu trúc của DFT và DCT.................................................25

Hình 1.7 Biến đổi DCT ảnh của Lena: (a) ảnh gốc, (b) ảnh tái cấu trúc ..................26

Hình 1.8 (a) Khối con 8×8 ảnh gốc của Lena; (b) Các hệ số DCT..........................26

Hình 1.9 Ƣớc lƣợng chuyển động phối hợp tốt nhất ................................................31

Hình 1.10 Biểu diễn thuật toán tìm kiếm ba bƣớc ....................................................32

Hình 2.1 Hình chiếu chuyển động.............................................................................35

Hình 2.2 Ƣớc lƣợng chuyển động phối hợp khối .....................................................48

Hình 2.3 Tái xác lập chất lƣợng của SSD, SAD, NCCF ..........................................50

Hình 2.4 Ba loại hồi quy khác nhau..........................................................................52

Hình 2.5 Phƣơng pháp dốc nhất................................................................................54

Hình 2.6 Mô tả phƣơng pháp Newton-Raphson .......................................................57

Hình 4.1 a) Khung 1512 và b) Khung 1513 của videoclip-1..................................100

Hình 4.2 a) Khung 434 và b) Khung 435 của videoclip-2......................................101

Hình 4.3 Trƣờng chuyển động của videoclip-1, phƣơng pháp Bayes (λ=100) ......102

Hình 4.4 Trƣờng chuyển động của videoclip-1, phƣơng pháp Bayes (λ=1500) ....102

Hình 4.5 Trƣờng chuyển động của videoclip-1, phƣơng pháp Kalman (L=10).....104

Hình 4.6 Trƣờng chuyển động của videoclip-1, phƣơng pháp Kalman (L=100)...104

Hình 4.7 Trƣờng chuyển động của videoclip-2, phƣơng pháp Bayes (λ=100) ......106

Hình 4.8 Trƣờng chuyển động của videoclip-2, phƣơng pháp Kalman (L=100)...106

Hình 4.9 Đồ thị biểu diễn thời gian tính toán theo phƣơng pháp Bayes.................107

Hình 4.10 Đồ thị biểu diễn thời gian tính toán theo phƣơng pháp Kalman............108

1

MỞ ĐẦU

Giới thiệu

Nén video là chủ đề đã và đang thu hút sự quan tâm của các nhà nghiên cứu

trên thế giới. Việc tìm giải pháp nén video luôn hƣớng tới mục tiêu làm sao tăng

hiệu quả nén trong khi giảm thiểu sự biến dạng hình ảnh mà quá trình nén gây ra.

Hai yêu cầu này thƣờng mâu thuẫn với nhau. Vì vậy, tùy ứng dụng cụ thể mà ngƣời

ta chọn giải pháp nén phù hợp để dung hòa giữa hai yếu tố.

Hiện nay trên thế giới cũng nhƣ ở Việt Nam đã triển khai mạng thông tin thế

hệ sau. Một trong các đặc điểm của mạng thông tin thế hệ sau là truyền tải tất cả các

thông tin và các dịch vụ trên cơ sở sử dụng công nghệ chuyển mạch mềm, cho phép

cung cấp các dịch vụ đa phƣơng tiện đến ngƣời sử dụng. Trong đó, các dịch vụ đa

phƣơng tiện sử dụng video bao gồm: điện thoại video, hội nghị truyền hình, y tế từ

xa, đào tạo từ xa, xem các chƣơng trình video phát quảng bá hoặc theo yêu cầu…

Các dịch vụ của mạng thông tin thế hệ sau không chỉ trong suốt trên mạng cố định

mà với xu thế hội tụ cố định - di động thì chúng cũng phải trong suốt đến tận máy

đầu cuối di động. Để đáp ứng yêu cầu đó, cần tìm ra các phƣơng pháp nén video

hiệu quả để giải quyết một số bài toán đặt ra ở đây là:

- Nguồn tài nguyên tần số của môi trƣờng vô tuyến là hữu hạn, vì vậy có giải

pháp gì để tăng hiệu suất sử dụng tài nguyên đó.

- Kênh truyền dẫn vô tuyến có tác động tiềm tàng của nhiễu, vì vậy có thuật

toán xử lý tín hiệu mà chống đƣợc ảnh hƣởng đó không.

- Thiết bị đầu cuối di động có kích thƣớc bé, nguồn năng lƣợng pin cung cấp

cho nó hạn chế, vì vậy có giải pháp nào để tăng tốc độ xử lý nhằm tiết kiệm

nguồn điện.

Nhiều công trình nghiên cứu đã đƣợc công bố tập trung vào giải pháp nén tín

hiệu video với mục tiêu là giảm băng tần cần thiết giành cho phổ tần tín hiệu video.

2

Trong đó đặc trƣng là các công trình mã tốc độ thấp [4], [15], [24], [35], [64], [68]

hoặc là giải pháp ƣớc lƣợng chuyển động của ảnh trong video.

Trong hệ thống nén video thì bù chuyển động là một bộ phận rất quan trọng,

đóng vai trò then chốt, đƣợc Netravali và Robbins đƣa ra năm 1997. Bù chuyển

động là một kỹ thuật dự đoán hƣớng theo thời gian, nó ƣớc lƣợng độ dịch chuyển

của mục tiêu chuyển động từ khung tham chiếu đến khung hiện tại. Ƣớc lƣợng

chuyển động thu đƣợc dự đoán bù chuyển động bằng cách tìm véctơ chuyển động

giữa khung tham chiếu và khung hiện tại.

Giai đoạn đầu ngƣời ta sử dụng phƣơng pháp Bayes để ƣớc lƣợng chuyển

động của ảnh. Phƣơng pháp Bayes xét đặc điểm tự nhiên của nội dung ảnh và hiệu

giữa các khung liên tiếp, mô tả đƣợc bản chất xuất hiện của ảnh nhƣng việc tính

toán phức tạp, đặc biệt khi phân bố nhiều chiều. Đồng thời, chúng ta cũng biết rằng

để sử dụng đƣợc công thức Bayes thì điều kiện tiên quyết là dãy ảnh phải là dãy xác

suất đầy đủ. Đó là điều kiện tính toán khó vì phải nhận biết đƣợc dãy ảnh có thỏa

mãn điều kiện “đầy đủ” hay không, nếu không thì quá trình ƣớc lƣợng sẽ phạm phải

sai số đáng kể.

Trong những năm gần đây, một số tác giả đã mở rộng phƣơng pháp Bayes

cho ƣớc lƣợng ảnh [57]. Rất nhiều nỗ lực đã đƣợc thực hiện trong ƣớc lƣợng IBM

thông qua phƣơng pháp học thống kê bằng Bayes. Tuy nhiên, nhƣợc điểm của nó là

mặt nạ đƣợc ƣớc lƣợng cho từng đơn vị thời gian - tần số một cách độc lập mà

không tính đến mối tƣơng quan giữa chúng. Trong [57], Shan Liang, Wenju Liu và

Wei Jiang đã đề cập đến mối tƣơng quan đó bằng thông tin tƣơng quan địa phƣơng.

Họ đã sử dụng những biến phụ để chỉ ra mối tƣơng quan. Phƣơng pháp này đã

chứng tỏ có độ chính xác cao hơn phƣơng pháp Bayes thông thƣờng. Tuy vậy,

phƣơng pháp này đã bỏ qua một số tham số thống kê bậc hai vì vậy làm hạn chế độ

chính xác trong ƣớc lƣợng chuyển động.

Bên cạnh những ƣu điểm của phƣơng pháp Bayes thì bản thân nó bộc lộ

những điều kiện ứng dụng mà không phải dãy ảnh chuyển động nào cũng thỏa mãn,

3

đó là tính độc lập, tính đầy đủ. Vì vậy, những năm gần đây đã xuất hiện ƣớc lƣợng

chuyển động của ảnh bằng lọc Kalman làm tăng tốc độ xử lý. Điển hình năm 2009,

Nai-Chung Yang, Chaur Heh Hsieh và Chung Ming Kuo [50] đã công bố công trình

ƣớc lƣợng chuyển động trong mã hóa video bằng lọc Kalman. Trong [50], các tác

giả đã sử dụng mô hình ƣớc lƣợng ba chiều. Tuy nhiên, các tác giả đã không tính

trực tiếp ba chiều trong các thuật toán Kalman mà đã giả thiết về tính độc lập để đƣa

về tính trong không gian một chiều bằng phƣơng pháp hồi qui và lọc Kalman địa

phƣơng. Vì vậy, [50] còn có những hạn chế sau:

- Mô hình địa phƣơng chỉ trợ giúp cho biến đổi không gian và thời gian sau đó

phải cải tiến biểu diễn không gian trạng thái. Biểu diễn không gian trạng thái

của mô hình địa phƣơng không gian và thời gian một cách riêng biệt.

- Ƣớc lƣợng chuyển động có ràng buộc tốc độ bằng lọc Kalman, mới đƣa ra

hàm mục tiêu bằng cách cực tiểu hàm Lagrange, chƣa chỉ ra thuật toán.

- Mới đƣa ra sơ đồ khối thuật toán ƣớc lƣợng chuyển động nâng cao kết hợp

lọc Kalman với thuật toán BMA để nâng cao độ chính xác ƣớc lƣợng, chƣa

chỉ ra thuật toán cụ thể.

Để tăng tốc độ xử lý, cải tiến độ bám chuyển động, ngƣời ta đã đƣa ra các

phƣơng pháp ƣớc lƣợng chuyển động có tốc độ nhanh hơn, có độ phối hợp tốt giữa

các khung ảnh [28], [36], [37], [43], [47], [58], [70]. Tuy vậy, việc ƣớc lƣợng

chuyển động vẫn chủ yếu dựa trên không gian hai chiều còn trong không gian ba

chiều thì họ vẫn phải chuyển từ không gian ba chiều sang hai chiều [26].

Trong luận án này, nghiên cứu sinh sẽ tiếp tục nghiên cứu áp dụng lọc

Kalman để ƣớc lƣợng chuyển động của ảnh với các giải pháp mở rộng hơn:

- Ƣớc lƣợng chuyển động của ảnh bằng Kalman một bƣớc.

- Ƣớc lƣợng chuyển động của ảnh bằng Kalman nhiều bƣớc, nhiều chiều.

- Ƣớc lƣợng chuyển động tối ƣu của ảnh trong video bằng lọc Kalman.

4

Để giải quyết bài toán nâng cao hiệu quả sử dụng băng tần hơn nữa, đồng

thời tăng độ chính xác ƣớc lƣợng trong môi trƣờng kênh có nhiễu lớn và fading,

luận án đã nghiên cứu, đề xuất ứng dụng thuật toán mù.

Tính cấp thiết của đề tài

Hiện nay, với việc triển khai mạng thông tin thế hệ sau đã mở đƣờng cho

nhiều ứng dụng mới ra đời nhƣ truyền tín hiệu video trên các phƣơng tiện thông tin

di động, đa môi trƣờng. Nhƣng làm sao để nâng cao hiệu quả sử dụng tài nguyên

băng tần, hạn chế tối đa tác động tiềm tàng của nhiễu trong môi trƣờng truyền dẫn

vô tuyến thì bài toán đặt ra là phải nén tín hiệu video sao cho hiệu quả nhất mà vẫn

đảm bảo chất lƣợng hình ảnh với sự trợ giúp đắc lực của công nghệ thông tin. Vì

vậy, đề tài này là một chủ đề cấp thiết cho ứng dụng truyền video trên các mạng

viễn thông đa môi trƣờng thế hệ mới.

Mục tiêu nghiên cứu

Luận án tìm các thuật toán hợp lý để ƣớc lƣợng chuyển động của ảnh trong

video sao cho dễ tính toán, đảm bảo độ bám chuyển động của ảnh một cách tốt nhất.

- Nghiên cứu đề xuất ứng dụng thuật toán ƣớc lƣợng chuyển động trong không

gian nhiều chiều với nghiệm ƣớc lƣợng chuyển động tối ƣu, độ bám tốt.

- Tăng hiệu quả sử dụng băng tần truyền dẫn bằng các thuật toán không cần sử

dụng tín hiệu đào tạo.

- Thuật toán ƣớc lƣợng làm việc ổn định trong điều kiện kênh có nhiễu.

Đối tƣợng, phạm vi và phƣơng pháp nghiên cứu

Luận án nghiên cứu các phƣơng pháp nén video số, ứng dụng truyền video

trong mạng thông tin di động thế hệ mới. Đây là một phạm vi rộng, bao gồm: lƣợng

tử hóa, ƣớc lƣợng chuyển động của ảnh, mã hóa - giải mã.

Luận án tập trung vào việc nghiên cứu các thuật toán ƣớc lƣợng chuyển động

của ảnh, phân tích các kết quả nghiên cứu chuyển động ảnh đã có trƣớc đây; nghiên

cứu các thuật toán ƣớc lƣợng về mặt toán học từ đó tìm ra thuật toán ƣớc lƣợng hợp