Tài liệu Nghiên cứu ứng dụng kỹ thuật fractal vào nén trong ảnh video

MỤC LỤC LỜI MỞ ĐẦU ............................................................................................... 3 DANH MỤC CÁC TỪ VIẾT TẮT ............................................................................ 7 DANH MỤC CÁC BẢNG ......................................................................................... 8 DANH MỤC CÁC HÌNH VẼ .................................................................................. 10 CHƯƠNG 1 - TỔNG QUAN ................................................................................... 12 1.1 Một số phương pháp nén video phổ biến .......................................................... 12 1.1.1 Nén dư thừa về không gian.................................................................................. 12 1.1.2 Nén dư thừa thời gian........................................................................................... 13 1.2 Một số chuẩn lấy mẫu tín hiệu video................................................................. 13 1.3 Các tiêu chuẩn nén video với bitrate thấp ......................................................... 14 1.3.1 Chuẩn H.263......................................................................................................... 14 1.3.2 Chuẩn H.265/HEVC ............................................................................................ 15 1.3.3 Chuẩn H.264/AVC............................................................................................... 15 1.4 Hình học Fractal ................................................................................................ 19 1.4.1 Giới thiệu hình học Fractal .................................................................................. 19 1.4.2 Các ứng dụng của hình học Fractal..................................................................... 21 1.5 Các công trình nghiên cứu liên quan đến Fractal .............................................. 23 1.5.1 Các công trình nghiên cứu ứng dụng Fractal cho nén hình ảnh........................ 23 1.5.2 Các công trình nghiên cứu ứng dụng Fractal cho nén video ............................. 24 1.6 Kết luận chương ................................................................................................ 25 CHƯƠNG 2 - NÉN HÌNH ẢNH SỬ DỤNG FRACTAL ....................................... 26 2.1 Nén hình ảnh sử dụng Fractal Coding ............................................................... 26 2.1.1 Cơ sở lý thuyết nén ảnh sử dụng Fractal Coding ............................................... 26 2.1.2 Nén ảnh xám sử dụng Fractal Coding ................................................................ 39 2.1.3 Nén ảnh màu sử dụng Fractal .............................................................................. 44 2.1.4 Kết quả nén ảnh xám và ảnh màu sử dụng Fractal Coding............................... 47 2.1.5 Nhận xét ................................................................................................................ 60 2.2 Cải tiến chất lượng nén cho Fractal Coding ...................................................... 62 2.2.1 Cải tiến tỷ số nén cho Fractal Coding đề xuất .................................................... 63 1 2.2.2 Kết quả cải tiến tỷ số nén cho Fractal Coding .................................................... 67 2.2.3 Cải tiến thời gian mã hóa cho Fractal Coding đề xuất ....................................... 76 2.2.4 Kết quả cải tiến thời gian mã hóa của Fractal Coding ....................................... 85 2.3 Kết luận chương ................................................................................................ 89 CHƯƠNG 3 - TÍCH HỢP FRACTAL CODING TRONG QUÁ TRÌNH NÉN INTRA-FRAME CỦA CHUẨN H.264 ................................................................... 92 3.1 Tích hợp Fractal Coding trong intra-frame của tiêu chuẩn H.264 .................... 92 3.1.1 Phương pháp tích hợp Fractal Coding vào intra-frame của H.264 đề xuất...... 93 3.1.2 Phương pháp cải thiện tỉ lệ nén được đề xuất..................................................... 96 3.1.3 Đề xuất tăng cường mã hóa Fractal với biến đổi wavelet ................................. 97 3.1.4 Kết quả thực nghiệm ............................................................................................ 99 3.2 Xây dựng mô hình truyền dữ liệu thời gian thực sử dụng tiêu chuẩn H.264 đã tích hợp Fractal Coding ................................................................................................. 105 3.2.1 Phương pháp thực hiện nhúng H.264F vào VLC Player được đề xuất.......... 105 3.2.2 Kết quả nhúng H.264F vào VLC Player .......................................................... 110 3.3 Kết luận chương .............................................................................................. 112 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.......................................................................... 114 TÀI LIỆU THAM KHẢO ...................................................................................... 116 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN ................. 122 2 LỜI MỞ ĐẦU Nén dữ liệu (data compression) là phương pháp mã hóa kỹ thuật số nhằm giảm dung lượng của dữ liệu. Tùy theo lượng dữ liệu trước và sau giải nén, người ta chia nén thành hai dạng: nén không mất dữ liệu (lossless) và nén bị mất dữ liệu (lossy) [23]. Các thuật toán nén không mất dữ liệu thường dựa trên giả thuyết dư thừa trong dữ liệu, từ đó thể hiện dữ liệu một cách chính xác mà không mất thông tin. Điển hình cho nén không mất dữ liệu có thể kể đến mã hóa RLE (Run-length Encoding), thay thế một loạt dữ liệu liền nhau lặp lại thành một dữ liệu đại diện khác. Nén mất dữ liệu làm giảm số lượng bit bằng cách xác định các thông tin không cần thiết và loại bỏ chúng. Một trong những dạng nén mất dữ liệu phổ biến nhất là nén video. Một tín hiệu video số thường chứa một lượng lớn dữ liệu âm thanh và hình ảnh, do đó sẽ gặp rất nhiều khó khăn trong việc lưu trữ và truyền đi trong một băng thông kênh truyền thực tế. Với sự phát triển của khoa học công nghệ hiện nay, bộ cảm biến màu có 16 triệu màu với độ phân giải rất cao lên đến 4096 x 4096 pixels đã được sản xuất. Tuy nhiên, ứng dụng thực tế cần độ phân giải cao hiện nay cũng chỉ dừng lại ở mức 1920 x 1080 pixels. Nguyên nhân của vấn đề này là những video có độ phân giải rất cao như 2K và 4K sẽ tiêu tốn nhiều không gian lưu trữ và chiếm dụng nhiều băng thông trên kênh truyền dẫn. Trước nhu cầu sử dụng thông tin và hình ảnh đòi hỏi ngày càng cao về mặt chất lượng trong khi vẫn bị giới hạn bởi không gian lưu trữ và băng thông kênh truyền đòi hỏi cần có một giải pháp có thể giải quyết được vấn đề này. Do đó, để có thể tiết kiệm không gian lưu trữ và băng thông kênh truyền thì cần thiết phải nén tín hiệu video. Quá trình nén video thực hiện được là do thông tin trong các video thường có trật tự, có tổ chức, vì thế nếu xem kỹ cấu trúc video có thể phát hiện được nhiều loại thông tin dư thừa khác nhau. Các thông tin dư thừa nằm trong video có thể chia thành năm loại. 3 Thứ nhất là dư thừa về không gian. Sự dư thừa về không gian giữa các điểm ảnh ngay trong một khung hình gọi là thừa tĩnh. Dư thừa về mặt không gian là do các chi tiết điểm ảnh giống nhau trên cùng một khung hình, ví dụ như nhiều điểm ảnh giống nhau tạo thành bầu trời xanh. Thứ hai là dư thừa về thời gian. Sự dư thừa về thời gian giữa các điểm ảnh của các khung video gọi là thừa động. Dư thừa về thời gian là do những hình ảnh giống nhau lặp lại liên tục từ khung hình này sang khung hình khác. Thứ ba là sự dư thừa thông tin về phổ. Đó là sự dư thừa về phổ giữa các mẫu tín hiệu thu được từ các bộ cảm biến trong camera. Thứ tư là sự dư thừa do thống kê. Bản thân các ký hiệu xuất hiện trong dòng bit với các xác suất xuất hiện không đồng đều. Thứ năm là sự dư thừa tâm thị giác. Sự dư thừa do các thông tin không phù hợp với hệ thống thị giác của con người. Các thuật toán nén video cần giảm được lượng thông tin thừa này bằng các phương pháp khác nhau để giảm dung lượng của video, nhằm tiết kiệm băng thông truyền, giảm chi phí lưu trữ sao cho vẫn duy trì được chất lượng ở mức chấp nhận được. Từ yêu cầu đặt ra để giảm lượng thông tin dư thừa, nhiều phương pháp nén video đã được đề xuất nhằm giảm lượng thông tin dư thừa trong dữ liệu video tương ướng với năm loại thông tin dư thừa đã nêu. Đó là dư thừa về không gian, dư thừa về thời gian, dư thừa thông tin về phổ, dư thừa thông tin do thống kê và dư thừa tâm thị giác. Trong các phương pháp nén video đã được đề xuất, hai phương pháp chính hiện tại đang được áp dụng phổ biến là giảm thông tin dư thừa về không gian và giảm thông tin dư thừa về thời gian. Phương pháp nén dư thừa về không gian tập trung vào các thuật toán nhằm giảm tối đa các dư thừa về mặt không gian giữa các điểm ảnh, từ đó nâng cao tỷ lệ nén. Các tiêu chuẩn nén video theo phương pháp này đã được công bố. Trong đó, MJPEG là đại diện tiêu biểu. Phương pháp nén dư thừa về thời gian tập trung vào các thuật toán nhằm giảm tối đa các dư thừa về mặt thời gian giữa bằng cách cố gắng xác định được tối đa các điểm ảnh giống nhau giữa các khung hình của một video. Việc giảm trừ tối đa các điểm ảnh giống nhau này cho phép tăng tỷ lệ nén video. Có nhiều tiêu chuẩn nén 4 video theo phương pháp nén dư thừa về thời gian, trong đó, MPEG là tiêu chuẩn tiêu biểu. Từ năm 2003, một tiêu chuẩn nén mới đã được đề xuất, đó là tiêu chuẩn H.264. H.264 là một tiêu chuẩn nén sử dụng phương pháp nén dư thừa về thời gian. Bản chất của tiêu chuẩn H.264 là sự phát triển của tiêu chuẩn MPEG, trong đó áp dụng thêm các kỹ thuật nhằm nâng cao hơn nữa tỷ lệ nén và cố gắng cải thiện chất lượng hình ảnh của video tương ứng với tỷ lệ nén đạt được. Năm 2013, một tiêu chuẩn phát triển dựa trên tiêu chuẩn H.264 được đề xuất. H.265 có tỷ lệ nén gấp đôi so với tiêu chuẩn H.264 ở cùng một mức độ chất lượng hình ảnh video. Mục tiêu của tiêu chuẩn H.265 là chuẩn nén hỗ trợ cho các video độ phân giải cực cao 8K UHD và kỳ vọng hỗ trợ lên đến độ phân giải 4320P ( 8192 x 4320). Như vậy, hướng phát triển của các tiêu chuẩn nén video là sự kế thừa và phát triển của các tiêu chuẩn trước đó để hướng tới hai mục đích chính. Đó là nâng cao tỷ lệ nén và cải thiện chất lượng hình ảnh sau giải nén tương đương với tỷ lệ nén đã đạt được. Hình học Fractal là nguồn cảm hứng cho thuật toán nén mà điển hình hơn là thuật toán nén hình ảnh. Lĩnh vực này hiện đang chiếm được sự quan tâm của rất nhiều nhà khoa học trên thế giới cũng như ở Việt Nam. Nén hình ảnh sử dụng Fractal mang đến tỉ lệ nén vượt trội so với bất kỳ phương pháp mã hóa nén nào trước đây mà vẫn đảm bảo được chất lượng tốt nhất có thể cho hình ảnh. Ưu điểm của nén hình ảnh sử dụng Fractal là tỷ lệ nén cao vượt trội và quá trình giải nén rất nhanh. Tuy nhiên, khối lượng tính toán rất lớn trong quá trình nén ảnh làm cho thời gian nén ảnh cũng rất lớn. Từ đó, ý tưởng kết hợp Fractal và tiêu chuẩn H.264 được hình thành nhằm áp dụng ưu điểm về tỷ số nén của Fractal vào tiêu chuẩn nén video H.264 đang được áp dụng rộng rãi là một nỗ lực nhằm tạo ra một tiêu chuẩn nén hình ảnh có tỷ số nén cao, thời gian nén ảnh đảm bảo tương đương với các tiêu chuẩn hiện thời và có thời gian giải nén ảnh vượt trội. Bên cạnh đó, việc nâng cao tỷ số nén ảnh và giảm thời gian nén ảnh đối với phương pháp nén ảnh sử dụng Fractal cũng là một vấn đề cần được giải quyết. 5 Trong Luận án này sẽ trình bày về việc sử dụng Fractal trong việc nén hình ảnh và video để đưa ra một phương pháp giải quyết các vấn đề đã nêu ở trên. Ngoài phần mở đầu và kết luận, nội dung Luận án bao gồm có 3 chương: Chương 1: Tổng quan: Chương này giới thiệu tổng quan về lý thuyết liên quan đến hình học Fractal và phương pháp nén hình ảnh sử dụng hình học Fractal. Nội dung của chương cũng giới thiệu về các lý thuyết liên quan hoặc được sử dụng trong nghiên cứu của tác giả. Chương 2: Phương pháp nén hình ảnh sử dụng Fractal: Nội dung của chương này giới thiệu về phương pháp sử dụng thuật toán Fractal để nén hình ảnh. Giới thiệu phương pháp cải tiến các chỉ tiêu nén hình ảnh sử dụng hình học là tỷ số nén và thời gian nén và trình bày các kết quả thực nghiệm đã đạt được. Chương 3: Tích hợp Fractal coding trong quá trình nén Intra-frame của tiêu chuẩn H.264: Nội dung chương 3 trình bày phương pháp tích hợp Fractal Coding trong quá trình nén intra-frame của tiêu chuẩn H.264 và những kết quả thực nghiệm mà tác giả đã đạt được trong quá trình nghiên cứu. 6 DANH MỤC CÁC TỪ VIẾT TẮT VIẾT TẮT TIẾNG ANH TIẾNG VIỆT AVC Advanced Video Coding Tiêu chuẩn nén video tiên tiến CNN Celular Neural Network Mạng nơ-ron tế bào CPU Central Processing Unit Bộ xử lý trung tâm CR Compression Ratio Tỷ số nén DCT Discrete Cosine Transform Phép biến đổi Cosin rời rạc DSP Digital signal processing Mạch xử lý tín hiệu số FCIC Fractal Color Image Coding Phương pháp nén ảnh màu sử dụng Fractal FIC Fractal Image Compression Nén hình ảnh sử dụng Fractal FPGA Field programmable Gate Array Mảng cổng lập trình được dạng trường GOP Group of Picture Nhóm các ảnh H.264 H.264/MPEG-4 Part 10 or AVC Một tiêu chuẩn nén video HEVC High Efficiency Video Coding Tiêu chuẩn nén video hiệu năng cao HV Horizontal vertical Partition Phân hoạch theo không gian IFS Iterated Function System Hệ thống chức năng lặp JPEG Joint Photographic Experts Group Phương pháp nén ảnh NAL Network abstraction layer PIFS Partition Iterated Function System Hệ thống chức năng lặp phân mảnh PSNR Peak signal-to-noise ratio Tỷ số tín hiệu cực đại trên nhiễu RIFS Recurrent Iterated Function System Hệ thống chức năng lặp đệ quy RLE Run-length Encoding Thuật toán nén dữ liệu lossless RMS Root mean square Giá trị trung bình bình phương SDK Services Development Kit Bộ phát triển dịch vụ SFC Seperated Fractal Coding Mã hóa Fractal thành phần SoC System on Chip Hệ thống tích hợp trên một chip UHD Ultra high definition television Truyền hình độ phân giải siêu cao VCL Video Coding Layer Lớp mã hóa video 7 DANH MỤC CÁC BẢNG 2.1 Phần mềm sử dụng cho bo mạch FPGA …………………………………….. 41 2.2 Tài nguyên hệ thống được sử dụng trong thực thi …………………………… 42 2.3 Tập các miền với kích thước dải khác nhau và số lượng miền ……………… 46 2.4 So sánh hiệu suất hoạt động trên nền tảng FPGA và DSP theo phương pháp Fisher ……………………………………………………………………….. 47 2.5 Hiệu suất PSNR và thời gian mã hóa ……………………………………….. 48 2.6 Các thông số nén Fractal của hình Lena ……………………………………... 50 2.7 Kết quả FCIC hình ảnh của Lena …………………………………………… 50 2.8 Các ảnh gốc được lựa chọn và tính chất ảnh ………………………………… 51 2.9 Kết quả FCIC hình ảnh của ảnh Fruit ……………………………………….. 51 2.10 Kết quả FCIC hình ảnh của ảnh Leaves ……………………………………... 52 2.11 Kết quả FCIC hình ảnh của ảnh Natural ……………………………………. 53 2.12 So sánh tỷ số nén giữa 3 ảnh Fruit, Leaves, Natural ………………………… 53 2.13 So sánh tỷ số PSNR giữa 3 ảnh Fruit, Leaves, Natural ……………………… 54 2.14 So sánh tỷ số nén và PSNR giữa Fractal và JPEG đối với ảnh Lena ……….. 55 2.15 So sánh tỷ số nén và PSNR giữa Fractal và JPEG đối với ảnh Fruit ………… 55 2.16 So sánh tỷ số nén và PSNR giữa Fractal và JPEG đối với ảnh Leaves ……… 56 2.17 So sánh tỷ số nén và PSNR giữa Fractal và JPEG đối với ảnh Natural ……… 57 2.18 Bảng kết quả so sánh giữa thực hiện nén ảnh bằng Fractal và JPEG ………. 57 2.19 So sánh hình ảnh nén thực hiện bằng Fractal và JPEG ở tỉ lệ 4 :4 : 4 ……… 59 2.20 So sánh hình ảnh nén thực hiện bằng Fractal và GPEG ở tỉ lệ 4:2:2 ……….. 59 2.21 So sánh hình ảnh nén thực hiện bằng Fractal và JPEG ở tỉ lệ 4:2:0 ………… 60 2.22 So sánh hình ảnh nén thực hiện bằng Fractal và GPEG tại tỉ lệ 4:2:0 ……… 60 2.23 Nén ảnh màu Fractal ảnh Lena ……………………………………………… 67 2.24 Nén ảnh màu Fractal ảnh Parrot ……………………………………………. 68 2.25 Nén ảnh màu Fractal ảnh One Tiger ………………………………………... 69 2.26 Nén ảnh màu Fractal ảnh Two Tiger ………………………………………... 69 2.27 Nén ảnh màu Fractal ảnh Flower …………………………………………… 70 2.28 Nén ảnh màu Fractal ảnh Fruit ……………………………………………… 70 2.29 Nén ảnh màu Fractal ảnh Balloon ………………………………………….. 71 8 2.30 Bảng 2.30: Nén ảnh màu Fractal ảnh Natural ……………………………… 71 2.31 Kết quả giải nén bởi việc điều chỉnh RMS …………………………………. 73 2.32 Kết quả FCIC với một luồng xử lý …………………………………………. 83 2.33 Kết quả FCIC với hai luồng xử lý ………………………………………….. 84 2.34 Kết quả FCIC với bốn luồng xử lý …………………………………………. 85 2.35 So sánh theo tỷ lệ phần trăm giữa 4 luồng, 2 luồng và 1 luồng ……………. 85 2.36 Kết quả FCIC với 1 luồng, 2 luồng, 4 luồng xử lý của các ảnh Parrot, Flower, Natural, One-tiger, Two-tiger, Red-tree và Roses ………………………….. 86 3.1 So sánh về chất lượng giữa video H.264 và H.264F ……………………….. 94 3.2 Thông số của các video kiểm tra ……………………………………………. 96 3.3 Tỷ số nén của H.264 và H.264F đối với video Foreman …………………… 97 3.4 Tỷ số nén của H.264 và H.264F đối với video Bridge ……………………… 97 3.5 Tỷ số nén của H.264 và H.264F đối với video Bridge-Far ………………….. 97 3.6 Tỷ số nén của H.264 và H.264F đối với video Grandma …………………… 97 3.7 Tỷ số nén của H.264 và H.264F đối với video Highway …………………… 98 3.8 So sánh PSNR giữa ảnh chuẩn và ảnh fractal trong video Foreman ……….. 98 3.9 So sánh PSNR giữa ảnh chuẩn và ảnh fractal trong video Bridge ………….. 99 3.10 So sánh PSNR giữa ảnh chuẩn và ảnh fractal trong video Bridge Far ……… 99 3.11 So sánh PSNR giữa ảnh chuẩn và ảnh fractal trong video Grandma ………… 100 3.12 So sánh PSNR giữa ảnh chuẩn và ảnh fractal trong video highway ………... 100 3.13 Bitrate so sánh giữa nén Fractal và H.264 ………………………………….. 101 3.14 Thông số của video thử nghiệm …………………………………………….. 107 3.15 So sánh khi chạy video Fractal và video H.264 …………………………….. 107 9 DANH MỤC CÁC HÌNH VẼ 1.1 Quy trình nén dư thừa không gian ………………………………………….. 12 1.2 Nén dư thừa thời gian ………………………………………………………. 13 1.3 Quy trình mã hóa và giải mã video chuẩn H.264 …………………………… 16 1.4 Phân chia Macroblock trong video …………………………………………. 16 1.5 Cấu trúc dòng bit trong H.264 ……………………………………………… 17 1.6 Sơ đồ bộ mã hóa của chuẩn H.264 …………………………………………. 18 1.7 Một số hình dạng Fractal cơ bản ……………………………………………. 19 1.8 Đồ thị Mandelbrot …………………………………………………………... 20 2.1 Tam giác Sierpinski ………………………………………………………… 26 2.2 Ảnh Sunset với các miền và vùng được tìm thấy …………………………… 34 2.3 Sơ đồ khối quá trình mã hóa của FIC ……………………………………… 36 2.4 Sơ đồ khối quá trình giải mã của FIC ……………………………………… 37 2.5 Hình ảnh Lena theo phân hoạch Quadtree ………………………………… 38 2.6 Hình ảnh lena với phân hoạch HV ………………………………………… 39 2.7 Xử lý hoạt động nén ảnh Fractal …………………………………………… 43 2.8 Module nén ảnh màu Fractal ……………………………………………… 44 2.9 Các thành phần của ảnh màu ………………………………………………… 45 2.10 Các chế độ lấy mẫu tín hiệu …………………………………………………. 45 2.11 Mô hình mã hóa Fractal triển khai trên FPGA ………………………………. 46 2.12 Ảnh chuẩn và ảnh giải nén Lena với ET = 6, RET = 16 ……………………… 49 2.13 Ảnh chuẩn và ảnh giải nén Lena với ET = 6, RET = 20 ……………………… 49 2.14 Định dạng ảnh PPM …………………………………………………………. 76 2.15 Phân phối trật tự hình ảnh vào vùng 16x16 ………………………………….. 76 2.16 Thuật toán FCIC được đề xuất ………………………………………………. 77 2.17 Trình tự các bộ nhớ stack được đề xuất ……………………………………… 78 2.18 Vi trí domain có thể có xung quanh range …………………………………… ̣ 79 2.19 Giảm dữ liệu bằng cách tạo trung bình cộng của bốn giá trị điểm ảnh ………. 79 2.20 Ví dụ về ánh xạ của miền vào vùng ………………………………………….. 80 2.21 Định dạng của bộ nhớ vùng …………………………………………………. 81 10 2.22 Xác định offset của miền ……………………………………………………. 81 2.23 Phân chia section ……………………………………………………………. 82 2.24 Phân chia section của OPENMP …………………………………………….. 83 3.1 Các bước chính để mã hóa một frame trong X264 ………………………….. 93 3.2 Sơ đồ nhúng mã hóa fractal vào intra-block trong H.264 …………………… 94 3.3 Cải thiện tỉ lệ nén ……………………………………………………………. 95 3.4 Nhúng wavelet và fractal vào x264 …………………………………………. 96 3.5a Sơ đồ khối nén ảnh sử dụng wavelet 3.5b Nhúng wavelet và fractal vào x264 ………………………………………… 97 3.6 Ảnh chuẩn và ảnh giải nén Fractal của video Foreman ……………………… 99 3.7 Ảnh chuẩn và ảnh giải nén Fractal của video Bridge ……………………… 100 3.8 Ảnh chuẩn và ảnh giải mã Fracal của video Brigde Far ……………………. 100 3.9 Ảnh chuẩn và ảnh giải mã Fracal của video Grandma ………………………. 101 3.10 Ảnh chuẩn và ảnh giải mã Fractal của video Highway …………………….. 101 3.11 Quá trình giải mã H.264 trên FFMPEG …………………………………… 103 3.12 Quá trình giải mã đơn vị NAL trên FFMPEG ………………………………. 104 3.13 Giải mã các thành phần trong FFMPEG ……………………………………. 104 3.14 Nhúng giải mã Fractal cho FFMPEG ……………………………………….. 105 3.15 Cơ chế hoạt động của VLC …………………………………………………. 106 3.16 Luồng của VLC ……………………………………………………………... 107 3.17 Hình chụp khi chạy video bridge_qcif.frt …………………………………... 109 3.18 Hình chụp khi chạy video bridge-far_qcif.frt ………………………………. 109 3.19 Hình chụp khi chạy video highway_qcif.frt ………………………………… 109 11 CHƯƠNG 1 - TỔNG QUAN 1.1 Một số phương pháp nén video phổ biến Như đã trình bày trong phần mở đầu, hai phương pháp nén video phổ biến đang được áp dụng hiện nay là phương pháp nén dư thừa về không gian và phương pháp nén dư thừa về thời gian. 1.1.1 Nén dư thừa về không gian Quy trình nén dư thừa về không gian được thể hiện qua hình Hình 1.1: Quy trình nén dư thừa không gian, trong đó khối nén dư thừa không gian tính đến sự tương tự của các pixel lân cận ngay trong một khung hình. Hình 1.1: Quy trình nén dư thừa không gian Nén dư thừa không gian bao gồm các bước sau: Chuyển qua không gian màu YUV: Quy trình này sẽ được đề cập đến trong Luận án. Chia khung hình thành các vùng nhỏ có kích thước 8x8 pixels. Biến đổi DCT đối với từng vùng nhằm giữ lại thông tin chính. 12 Loại bỏ các hệ số không quan trọng. Quét ziczag các bit trong khối 8x8 đồng thời mã hóa chúng theo độ dài. 1.1.2 Nén dư thừa thời gian Hình 1.2: Nén dư thừa thời gian Mã hóa dư thừa thời gian xem xét sự tương tự giữa các khung hình liên tiếp. Một video được mã hóa bởi một nhóm các ảnh (Group of Picture-GOP). Một GOP gồm có 3 dạng khung hình (frame) khác nhau: Intra-frame (I frame) : frame bắt đầu của GOP, lưu trữ toàn bộ hình ảnh “chính” của GOP, khi nén, frame I chỉ loại bỏ các thông tin dư thừa về không gian, dùng các điểm trong cùng một frame để dự báo cho các khung hình tiếp theo, không có bù chuyển động, đồng thời yêu cầu nhiều bit nhất. Predicted-frame (P frame) : chỉ lưu trữ những gì khác biệt so với I frame để tham chiếu, sử dụng bù chuyển động. Khi mã hóa, không cần lưu trữ những điểm ảnh không thay đổi trong các frame P. Frame P còn được biết đến với cái tên delta-frames. Bi-predictive-frame (B frame) tiết kiệm dung lượng bằng cách tham chiếu đến frame cả trước và sau nó. Có thực hiện bù chuyển động. 1.2 Một số chuẩn lấy mẫu tín hiệu video Kiểu lấy mẫu cho ảnh video cũng là một vấn đề quan trọng của kỹ thuật nén ảnh. Dưới đây là một số kiểu lấy mẫu video phổ biến sẽ được áp dụng trong phạm vi nghiên cứu của Luận án này[12]. Chuẩn lấy mẫu 4:1:1 – tần số lấy mẫu tín hiệu chói là 13,5MHz, và mỗi tín hiệu màu là 3,375MHz. 13 Chuẩn lấy mẫu 4:2:2 – tần số lấy mẫu tín hiệu chói là 13,5MHz, và mỗi tín hiệu màu là 6,75MHz. Chuẩn lấy mẫu 4:4:4 - cả 3 thành phần đều có cùng độ phân giải 13,5Mhz. Chuẩn lấy mẫu 4:2:0 – là kiểu phổ biến, tần số lấy mẫu tín hiệu chói là 13,5MHz, mỗi tín hiệu màu là 6,75MHz theo cả 2 chiều. Trong kỹ thuật nén video, tiêu chuẩn lấy mẫu là một lựa chọn quan trọng ảnh hưởng tới kết quả thực nghiệm. Sự thay đổi tần số lấy mẫu và cách lựa chọn tiêu chuẩn lấy mẫu sẽ quyết định dữ liệu đầu vào cho quá trình nén video, từ đó ảnh hưởng đến các thông số quan trọng của quá trình nén video như tỷ số nén, thời gian nén và chất lượng video sau giải nén so với video gốc. 1.3 Các tiêu chuẩn nén video với bitrate thấp Bit-rate là lượng dữ liệu được chuyển từ file video lên CPU trong 1s để xử lý giải mã thành hình ảnh và âm thanh. Bitrate càng cao chất lượng càng cao, tuy nhiên, CPU sẽ càng phải xử lý nhiều công việc, đồng thời đòi hỏi đường truyền có băng thông cao để đáp ứng. Một cách khái quát nhất, bitrate thấp đồng nghĩa với tỷ số nén cao. Do đó, trong phạm vi nghiên cứu của luận án này tập trung phân tích và lựa chọn một trong các tiêu chuẩn nén video với bitrate thấp làm đối tượng nghiên cứu để can thiệp Fractal coding vào tiêu chuẩn này. Sau đây là một số tiêu chuẩn nén video với bit-rate thấp sẽ có thể được lựa chọn. 1.3.1 Chuẩn H.263 H.263 là một chuẩn nén video bit-rate thấp, được thiết kế ban đầu dành cho các hội nghị truyền hình. Chuẩn H.263 được phát triển bởi Video Coding Experts Group và đã được công nhận vào khoảng năm 1995/1996. Một phiên bản thống nhất của H.263 đã được sản xuất năm 2005. H.263 là một trong những thành viên trong họ H.26x – một họ mã hóa tiêu chuẩn được sử dụng phổ biến. H.263 được sử dụng trong rất nhiều ứng dụng Internet, trong đó nổi bất nhất là Flash video, đã từng được sử dụng trên nhiều trang web như Youtube, Google Video, MySpace … 14 H.263 đã được cải tiến từ H261, MPEG-1 và MPEG-2. Đồng thời được phát triển thành các phiên bản mới như H.263v2 (có thể gọi tên là H.263+ hoặc H.263 1998), MPEG-4 Part 2 và H.263v3. MPEG-4 Part 2 là chuẩn H.263 được tương thích và có thể giải mã bởi các ứng dụng giải mã MPEG-4 [13]. Mặc dù H.263 là một chuẩn nén video với nhiều kỹ thuật tiên tiến, nhưng các định dạng video tiếp theo, như H.264 và H.265, với các ưu điểm vượt trội, đang dần dần thay thế chúng. 1.3.2 Chuẩn H.265/HEVC H.265/HEVC [12] (High Efficiency Video Coding) là một định dạng nén video kế thừa H.264/MPEG-4 AVC (Advanced Video Coding) được phát triển bởi ISO/IEC Moving Picture Experts Group (MPEG) và ITU-T Video Coding Experts Group (VCEG). MPEG và VCEG đã thành lập một nhóm cộng tác viên về mã hóa video để phát triển chuẩn HEVC. HEVC có tỷ lệ nén dữ liệu gấp đôi so với H.264/MPEG-4 AVC ở cùng một mức độ chất lượng video. Nó có thể được sử dụng để cung cấp chất lượng hình ảnh được cải thiện đáng kể tại cùng một bit-rate. Chuẩn nén hỗ trợ 8K UHD (Ultra high definition television) và độ phân giải lên đến 8192x4320 (4320P). Mặc dù có rất nhiều ưu điểm, tuy nhiên vẫn tồn tại nhiều hạn chế khiến chuẩn H.265 chưa thể được áp dụng rộng rãi, trong đó hạn chế cơ bản nhất là giá thành vẫn còn cao, yêu cầu các thiết bị đầu cuối phải trả tiền bản quyền thiết bị rất cao. 1.3.3 Chuẩn H.264/AVC Chuẩn nén H.264 [24] được công bố chính thức vào năm 2003, hiện là chuẩn hỗ trợ công nghệ nén tiên tiến và hiệu quả bậc nhất hiện nay, do kế thừa những ưu điểm nổi trội của các chuẩn nén trước đây. Sử dụng các thuật toán nén và phương thức truyền hình ảnh mới phức tạp, phương pháp nén và truyền hình ảnh chuẩn H.264 sử dụng đã làm giảm đáng kể dữ liệu và băng thông truyền tín hiệu video. Với cách nén và truyền thông tin theo chuẩn H.264 làm giảm đến 50% băng thông và kích thước file dữ liệu lưu trữ so với cách nén thông thường hiện nay (chuẩn 15 nén thông thường hiện nay đang được sử dụng rộng rãi là MPEG-4 Part 2) và giảm tới hơn 80% băng thông và kích thước file dữ liệu lưu trữ so với nén bằng chuẩn Motion JPEG. Điều đó cho thấy, với cùng một hệ thống nếu sử dụng chuẩn nén mới có thời gian lưu trữ gấp đôi và băng thông mạng giảm đi một nửa, lợi ích có thể thấy ngay đó là chi phí cho lưu trữ dữ liệu video giảm một nửa so với dùng hệ thống có chuẩn nén thông thường. Ngoài ra việc truyền hình ảnh chiếm băng thông giảm một nửa, vì vậy chi phí dành cho thuê băng thông mạng cũng giảm đáng kể. Do đó, tiêu chuẩn H.264 là lựa chọn phù hợp với yêu cầu nghiên cứu của Luận án bởi sự tối ưu giữa tỷ số nén, giá thành và mức độ phổ biến hiện nay. Các nội dung chi tiết hơn về tiêu chuẩn nén H.264 sẽ được trình bày dưới đây. 1.3.3.1 Cấu trúc Cấu trúc của H.264 gồm 2 phần chính: Network abstraction layer (NAL) và Video Coding Layer (VCL). Quy trình mã hóa và giải mã H.264 được trình bày trong Hình 1.3. Hình 1.3: Quy trình mã hóa và giải mã video chuẩn H.264 1.3.3.2 Macroblock Mỗi khung hình trong video đều được chia thành các Macroblock (MB) có kích thước cố định như Hình 1.4, bao trùm một diện tích ảnh hình chữ nhật gồm 16x16 mẫu thành phần luma và 8x8 mẫu cho thành phần chroma . Tất cả các mẫu luma và chroma được dự đoán theo không gian hoặc thời gian, và được dự đoán tại chỗ. 16 Hình 1.4 : Phân chia Macroblock trong video Các macroblock được tổ chức thành các slice, biểu diễn tập con của các ảnh đã cho và có thể được giải mã độc lập. Thứ tự truyền các Macroblock trong dòng bit phụ thuộc vào biểu đồ phân chia macroblock và không nhất thiết phải theo thứ tự quét. 1.3.3.3 Cấu trúc các chuỗi bit Cấu trúc các chuỗi bit trong chuẩn H.264 được thể hiện như trong Hình 1.5. Hình 1.5: Cấu trúc dòng bit trong H.264 Trong đó: mb_type: loại macroblock mb_pred: phương thức dự báo trong ảnh và xác định các list 0 hoặc list 1 để mã hóa phần khác biệt của ảnh chuyển động so với ảnh tham chiếu. 17 sub_mb_pred: xác định kích thước các sub-macroblock cho mỗi phân vùng và các list 0 hoặc list 1 để mã hóa phần khác biệt của ảnh chuyển động so với ảnh tham chiếu. coded_block_pattern: xác định khối chứa vector chuyển động được mã hóa. mb_qp_delta: thay đổi các tham số. residual: mã hóa chuyển đổi hệ số tương ứng với các mẫu ảnh còn sót lại sau khi dự đoán. 1.3.3.4 Mã hóa Sơ đồ mã hóa của chuẩn H.264 được biểu diễn như trong Hình 1.6. Dn + Fn (hiện tại) F’n (tái tạo) Q X Reorder Mã hóa entropy - ME NAL inter F’n-1 (tham chiếu) 1 hoặc 2 frame trước frame được mã hóa T MC P Lựa chọn intra prediction Intra prediction intra uF’n Bộ lọc + D’n + T-1 Q-1 Hình 1.6: Sơ đồ bộ mã hóa của chuẩn H.264 Trong đó: Fn (hiện tại): Ảnh hiện tại. F’n-1 (tham chiếu): Ảnh tham chiếu của một hoặc hai khung hình đã được mã hóa trước đó. F’n (tái tạo): Ảnh khôi phục. Intra prediction: Dự đoán trong ảnh. Lựa chọn Intra Prediction: Chọn dự đoán trong ảnh. Filter: Bộ lọc tách khối. 18 T, Q và T-1, Q-1: Mã hóa biến đổi nguyên tách biệt, lượng tử hóa và giải mã T, giải lượng tử hóa tương ứng. Dn và D’n: Phần ảnh sai khác. Reorder: Sắp xếp lại. Mã hóa Entropy: Mã hóa entropy. MC: Bù chuyển động. ME: Đánh giá chuyển động. 1.4 Hình học Fractal 1.4.1 Giới thiệu hình học Fractal Fractal [58] là một vật thể hình học thường có hình dạng gấp khúc trên mọi tỷ lệ phóng đại, và có thể được tách ra thành từng phần: mỗi phần trông giống như hình tổng thể, nhưng ở tỷ lệ phóng đại nhỏ hơn. Như vậy fractal có vô tận các chi tiết, các chi tiết này có thể có cấu trúc tự đồng dạng ở các tỷ lệ phóng đại khác nhau. Nhiều trường hợp, có thể tạo ra fractal bằng việc lặp lại một mẫu toán học, theo phép hồi quy. Hình 1.7 mô tả một số dạng Fractal phổ biến, được hình thành bằng cách đệ quy một thao tác nào đó với hình. Hình 1.7 : Một số hình dạng Fractal cơ bản 19 Fractal ban đầu được nghiên cứu như một vật thể toán học. Hình học Fractal là ngành toán học chuyên nghiên cứu các tính chất của fractal; những tính chất không dễ gì giải thích được bằng hình học thông thường. Ngành này có ứng dụng trong khoa học, công nghệ, và nghệ thuật tạo từ máy tính. Ý niệm cơ bản của môn này là xây dựng phép đo đạc mới về kích thước của vật thể, do các phép đo thông thường của hình học Euclid và giải tích thất bại khi mô tả các Fractal. Việc định nghĩa các đặc tính của fractal, có vẻ dễ dàng với trực quan, lại cực kỳ khó với đòi hỏi chính xác và cô đọng của toán học. Mandelbrot đã định nghĩa Fractal là "một tập hợp mà trong đó số chiều Hausdorff (hay chiều Hausdorff-Besicovitch) lớn hơn chiều tô pô học". Số chiều Hausdorff là khái niệm sinh ra để đo kích thước của fractal, thường không phải là một số tự nhiên. Một hình vẽ fractal trên tờ giấy 2 chiều có thể bắt đầu có những tính chất của vật thể trong không gian 3 chiều, và có thể có chiều Hausdorff nằm giữa 2 và 3. Đối với một fractal hoàn toàn tự đồng dạng, chiều Hausdorff sẽ đúng bằng chiều Minkowski-Bouligand. Hình 1.8: Đồ thị Mandelbrot Hình 1.8 mô tả đồ thị Mandelbrot, được đặt tên theo nhà toán học tìm ra và phát triển Fractal. Một Fractal thông thường sẽ có cách tính chất sau đây: Không có ý nghĩa chính xác của "gấp khúc". Không có định nghĩa duy nhất của "chiều". Có nhiều cách mà một vật thể có thể tự đồng dạng. 20