Phương pháp phân tích ảnh bằng Wavelet

PHƯƠNG PHÁP PHÂN TÍCH ẢNH BẰNG WAVELET PHỤC LỤC: PHƯƠNG PHÁP PHÂN TÍCH ẢNH BẰNG WAVELET Thành công cơ bản của công nghệ nén ảnh là giảm số lượng bit cần dùng để thể hiện ảnh với độ biến dạng cảm nhận là ít nhất.Mã hóa băng con sử dụng Wavelets là một công nghệ thể hiện tốt nhất giữa trong những công nghệ nén. Hình 1.1 dưới đây thể hiện sơ đồ khối của hệ thống nén ảnh dựa trên công nghệ wavelet. Ba khối đầu tiên của sơ đồ (DWT, quantizer and entropy coder) chịu trách nhiệm nén dữ liệu, trong khi 2 khối tiếp theo (entropy decoder, inverse discrete wavelet transform(IDWT) sẽ khôi phục hình ảnh từ dữ liệu đã bị nén. DWT Quantizer Entropy coder Channel Image X Entropy decoder IDWT Image X Fig 1.1 Sơ đồ khối của một hệ thống nén lossy dựa trên wavelet I. LỜI GIỚI THIỆU Biến đổi Wavelet được nghiên cứu từ những năm 60 của thế kỷ trước và cũng đã được ứng dụng trong một số ngành khoa học và công nghệ khác nhau. Tuy nhiên biến đổi Wavelet vẫn là một lĩnh vực đang và sẽ tiếp tục được nghiên cứu để phát triển cũng như ứng dụng rộng rãi hơn nữa. Đặc biệt biến đổi Wavelet ngày càng được áp dụng rộng rãi trong xử lý tiếng nói, xử lý ảnh số. Có nhiều thuật toán sử dụng cho nén ảnh như: dựa theo phép biến đổi, lượng tử hoá véctơ hoặc mã hoá băng con. Việc lựa chọn thuật toán trong truyền thông đa phương tiện không chỉ phụ thuộc vào tỉ số nén đạt được, chất lượng ảnh khôi phục mà còn liên quan đến năng lượng tiêu hao cũng như khả năng chống lại lỗi bit cao hơn. Mục đích của tiểu luận là trình bày một kỹ thuật nén ảnh sử dụng biến đổi Wavelet cho ảnh tĩnh và đặc biệt là ảnh tĩnh trong các dịch vụ dữ liệu đa phương tiện. So với các kỹ thuật nén sử dụng phép biến đổi trước đây như biến đổi Fourier (FT), biến đổi cosine rời rạc (DCT), biến đổi xếp chồng (LT),.., biến đổi Wavelet (DWT) có nhiều ưu điểm không chỉ trong xử lý ảnh mà còn nhiều ứng dụng khác. Đặc biệt gần đây nhóm JPEG đã phát triển chuẩn nén ảnh dựa trên biến đổi Wavelet gọi là JPEG2000 với nhiều ưu điểm. Tuy nhiên thống kê cho thấy bước biến đổi Wavelet trong quá trình nén tiêu tốn hơn 60% thời gian CPU. Như vậy nếu tối ưu các đặc điểm của thuật toán ở bước biến đổi thì năng lượng và hiệu suất nén có thể được cải thiện đáng kể. Do đó ta tập trung vào tối ưu năng lượng tiêu hao ở bước biến đổi. II. PHƯƠNG PHÁP NÉN ẢNH BẰNG WAVELET II.1 Tổng quan về kỹ thuật nén II.1.1 Giới thiệu chung về nén ảnh số Nén dữ liệu là quá trình làm giảm lượng thông tin dư thừa trong dữ liệu gốc và do vậy lượng thông tin thu được sau nén thường nhỏ hơn dữ liệu gốc rất nhiều. Nén ảnh số là một kiểu của nén dữ liệu nó là một đề tài nghiên cứu rất phổ biến trong lĩnh vực xử lý dữ liệu đa phương tiện. Mục đích là làm thế nào để lưu trữ bức ảnh dưới dạng có kích thước nhỏ hơn hay dưới dạng biểu diễn mà chỉ yêu cầu số bit mã hoá ít hơn so với bức ảnh gốc. Một trong các đặc trưng quan trọng nhất của mọi phương pháp nén là tỷ số nén. Tỷ số nén được tính =1/r % ( trong đó r= Kích thước dữ liệu gốc / Kích thước dữ liệu thu được sau nén). Với mục đích nén là làm giảm bớt dữ liệu dư thừa thì việc xác định bản chất các dữ liệu dư thừa là rất có ích cho việc xây dượng các phương pháp nén dữ liệu khác nhau. Ta có 4 loại dữ liệu dư thừa khác nhau: Trong một dãy ký tự, có một số ký tự có tần suất xuất hiện nhiều hơn một số dãy khác. Do vậy ta có thể mã hóa dữ liệu một cách cô đọng hơn, các ký tự có tần suất cao sẽ được thay đổi bởi một từ mã nhị phân với số bit nhỏ, ngược lại các dãy có tần suất thấp sẽ được mã hóa bởi từ mã có nhiều bit hơn. Người ta gọi là sự phân bố ký tự. Sự lặp lại của các ký tự: trong một số tình huống như trong ảnh, một ký hiệu (bit 0 hoặc bit 1) được lặp đi lặp lại một số lần thì ta thay dãy lặp đó bởi dãy mới gồm 2 thành phần: số lần lặp và ký hiệu dùng để mã. Những mẫu sử dụng tần suất: là một dãy ký hiệu nào đó xuất hiện một tần suất cao thì ta có thể mã hóa bởi số lượng bit ít hơn. Độ dư thừa vị trí: là sự phụ thuộc lẫn nhau của dữ liệu đôi khi biết được giá trị xuất hiện tại một vị trí, đồng thời có thể đoán được sự xuất hiện của giá trị ở một vị trí khác.+ Các phương pháp nén: Nén chính xác hay nén không mất thông tin: là các phương pháp nén mà sau khi giải nén ta thu được ảnh dữ liệu chính xác không mất mát. Nén có mất mát thông tin: là các phương pháp nén mà sau khi thu được dữ liệu nén không như bản gốc. Phương pháp không gian: là các phương pháp nén bằng cách tác động trực tiếp lên vật lấy mẫu của ảnh trong miền không gian. Phương pháp sử dụng biến đổi: là các phương pháp tác động lên sự biến đổi của ảnh gốc mà không tác động trực tiếp. Nhìn chung quá trình nén và giải nén dữ liệu có thể mô tả một cách tóm tắt như sau: QUÁ TRÌNH NÉN QUÁ TRÌNH GIẢI NÉN Dữ liệu gốc Dữ liệu nén Hình 1.2 Quá trình nén và giải nén dữ liệu Tín hiệu ảnh, video hay audio đều có thể nén lại bởi chúng có những tính chất như sau: Có sự tương quan (dư thừa) thông tin về không gian: Trong phạm vi một bức ảnh hay một khung video tồn tại sự tương quan đáng kể giữa các điểm ảnh lân cận. Có sự tương quan (dư thừa) thông tin về phổ: Các dữ liệu thu được từ các bộ cảm biến của thiết bị thu nhận ảnh tồn tại sự tương quan đáng kể giữa các mẫu thu, đây chính là sự tương quan về phổ. Có sự tương quan (dư thừa) thông tin về thời gian: Trong một chuỗi ảnh video, tồn tại sự tương quan giữa các điểm ảnh của các khung video (frame). II.1.2 Các kỹ thuật nén có tổn hao II.1.2.1 Kỹ thuật mã hoá băng con (subband coding) Tư tưởng chính của kỹ thuật mã hoá băng con là: các ảnh được lấy mẫu ở đầu vào được phân ly thành các băng tần khác nhau (gọi là các tín hiệu băng con). Yêu cầu của kỹ thuật này là làm thế nào các băng con không bị chồng chéo lên nhau. Để có thể phân ly tín hiệu ở bộ mã hoá (encoder) thành các băng con, ảnh được cho qua một bank lọc (filter bank) gọi là bank lọc phân tích và mỗi đầu ra của bank lọc băng con được lấy mẫu xuống hệ số 2. Các đầu ra băng con tần số được lẫy mẫu xuống sẽ lần lượt được: lượng tử hoá độc lập bằng các bộ lọc vô hướng khác nhau, mã hoá entropy, lưu trữ và truyền đi. Ở phía bộ giải mã (decoder), quá trình được thực hiện ngược lại: giải lượng tử băng con tần số, lấy mẫu lên với hệ số 2, cho đi qua bank lọc băng con tổng hợp rồi cộng tất cả các đầu ra của bộ lọc để khôi phục lại ảnh. Các bộ lọc băng con thường được thiết kế xấp xỉ thoả mãn tiêu chuẩn của các đáp ứng tần số không chồng chéo. Mục đích là để giải tương quan các hệ số tần số kết quả. Đây chính là tính chất quan trọng mà quá trình lọc băng con cố gắng đạt được. Các bộ lọc băng con được thiết kế để là các xấp xỉ với các bộ lọc chọn tần số lý tưởng, trong đó đáp ứng tổng hợp từ tất cả các bộ lọc bao trùm tất cả băng tần của ảnh. Tuy nhiên trong thực tế, sự tương quan tổng không bao giờ đạt được do những bộ lọc này chỉ xấp xỉ với các bộ lọc lý tưởng. Các bộ lọc sử dụng trong mã hoá băng con là các bộ lọc gương tứ phương – QMF (quardrature mirror filters), do vậy chúng ta chỉ cần thiết kế các bộ lọc thông thấp có đáp ứng H(ω) còn đáp ứng của các bộ lọc thông cao là H(ω+π) chỉ là sự dịch pha 1800 so với bộ lọc thông thấp. Sự chính xác của bộ lọc phụ thuộc vào số các hệ số của bộ lọc. Một trong các phương pháp mã hoá băng con đó là áp dụng sự phân ly cây bát phân để phân ly dữ liệu ảnh thành các băng tần khác nhau. Ý tưởng của phương pháp này là: trước tiên lọc vào lược bỏ ảnh để phân ly ảnh thành các băng con tần số cao và thấp, sau đó tiếp tục phân ly nhưng chỉ áp dụng cho băng con tần số thấp để tạo thành các băng con tần số cao và thấp để tiếp tục lược bỏ. Kỹ thuật này rất phổ biến và cũng được áp dụng trong các bộ mã sử dụng biến đổi Wavelet. Đầu ra của các băng con sau khi đã giản lược sẽ được lượng tử hoá và mã hoá độc lập. Mỗi băng con sẽ sử dụng bộ lượng tử hoá riêng và mỗi bộ lượng tử hoá này có tốc độ lấy mẫu riêng (bít/mẫu). Như vậy rõ ràng mã hoá băng con không đạt được sự nén, mà nó chỉ thực hiện việc giải tương quan dữ ảnh gốc và tập trung năng lượng của ảnh vào một số băng con. Nén chỉ đạt được là do sự lược bỏ ảnh (decimation) và do sự lượng tử hoá (quantization). Hình 1.3 Minh hoạ quá trình phân ly băng con cây bát phân Trong các hệ thống mã hoá băng con hai chiều thực tế, người ta chia miền tần số - không gian hai chiều của ảnh gốc thành các băng khác nhau ở bất kỳ mức nào. II.1.2.2.Kỹ thuật mã hoá dựa trên phép biến đổi II.1.2.2.1 Kỹ thuật mã hoá dựa trên phép biến đổi DCT Phép biến đổi cosine rời rạc – DCT (Discrete Cosine Transform) biến đổi thông tin ảnh từ miền không gian sang miền tần số để có thể biểu diễn dưới dạng gọn hơn. Tính chất của nó tương tự như biến đổi Fourier, coi ảnh đầu vào là các tín hiệu ổn định bất biến theo thời gian. + Biến đổi Fourier – FT Biến đổi Fourier – FT (Fourier Transform) là một phép biến đổi thuận nghịch, nó cho phép sự chuyển đổi thuận – nghịch giữa thông tin gốc (miền không gian hoặc thời gian) và tín hiệu được xử lý (được biến đổi). Tuy nhiên ở một thời điểm bất kỳ chỉ tồn tại một miền thông tin được thể hiện. Nghĩa là tín hiệu trong miền không gian không có sự xuất hiện thông tin về tần số và tín hiệu sau biến đổi Fourier không có sự xuất hiện thông tin về thời gian. FT cho biết thông tin tần số của tín hiệu, cho biết những tần số nào có trong tín hiệu, tuy nhiên nó không cho biết tần số đó xuất hiện khi nào trong tín hiệu. Nếu như tín hiệu là ổn định (stationary – có các thành phần tần số không thay đổi theo thời gian) thì việc xác định các thành phần tần số xuất hiện khi nào trong tín hiệu là không cần thiết. Phép biến đổi FT thuận và nghịch được định nghĩa như sau: (1.2) (1.1) Phép biến đổi FT cũng có thể được áp dụng cho tín hiệu không ổn định (non-stationary) nếu như chúng ta chỉ quan tâm đến thành phần phổ nào có trong tín hiệu mà không quan tâm đến nó xuất hiện khi nào trong tín hiệu. Tuy nhiên, nếu thông tin về thời gian xuất hiện của phổ trong tín hiệu là cần thiết, thì phép biến đổi FT không có khả năng đáp ứng được yêu cầu này, đây cũng là hạn chế của phép biến đổi. Để có biến đổi Fourier rời rạc –DFT (Discrete Fourier Transform) thì ở phép tích phân trong biểu thức toán học của biến đổi FT, ta thay bằng phép tổng và tính toán nó với các mẫu hữu hạn. Hệ số phép biến đổi DFT thứ k của một chuỗi gồm N mẫu {x(n)} được định nghĩa: (1.3) Trong đó WN =e-j2Π/N = cos (2π/N) – j sin (2π/N), còn chuỗi {x(n)} có thể khôi phục bằng DFT ngược như sau: (1.4) * Định nghĩa và các tính chất của biến đổi DCT Biến đổi DCT thuận và ngược một chiều gồm N mẫu được định nghĩa như sau: (1.6) (1.5) Cả DCT và IDCT đều là biến đổi trực giao, tách biệt và thực. Tính chất phân tách (separable) ở đây nghĩa là biến đổi nhiều chiều của nó có thể phân tách thành các biến đổi một chiều. Tính chất trực giao ở đây nghĩa là nếu các ma trận của DCT và IDCT là không bất thường (non-singular) và thực thì biến đổi ngược của chúng có thể đạt được bằng cách áp dụng toán tử hoán vị. Cũng như biến đổi FT, DCT cũng coi dữ liệu đầu vào là tín hiệu ổn định (bất biến). Trong các chuẩn nén ảnh tĩnh vào video, người ta thường sử dụng DCT và IDCT có kích thước 8 mẫu. Bức ảnh hoặc khung ảnh video kích thước NxN được chia thành các khối không chồng chéo nhau hai chiều gọi là các ảnh con kích thước 8x8 rồi áp dụng biến đổi DCT hai chiều ở bộ mã hoá và áp dụng biến đổi IDCT ở bộ giải mã. Biến đổi DCT và IDCT 8 mẫu tạo thành các ma trận 8x8 theo công thức: (1.8) (1.7) Thuật toán để tính 2-D DCT và IDCT là: thực hiện phép biến đổi 1-D lần lượt cho hàng rồi đến cột của ma trận. + Nén và giải nén ảnh dựa theo phép biến đổi DCT trong JPEG JPEG là chuẩn nén số quốc tế đầu tiên cho các ảnh tĩnh có tông màu liên tục gồm cả ảnh đơn sắc và ảnh màu. Trong kỹ thuật này các khối ảnh kích thước 8x8 được áp dụng để thực hiện DCT, sau đó lượng tử hoá các hệ số rồi mã hoá entropy sau lượng tử. Đối với những ảnh màu RGB, để áp dụng kỹ thuật nén này, trước hết phải chuyển sang chế độ màu YUV (Y là thành phần chói, U và V là 2 thành phần màu). Thành phần độ chói là ảnh đơn sắc xám. Hai thành phần màu còn lại chứa thông tin về màu. Việc mã hoá và giải mã ảnh trong JPEG ở được thực hiện cho thành phần chói rồi màu. Sơ đồ khối bộ mã hoá và giải mã của JPEG như sau: Hình 1.4 Sơ đồ bộ mã hoá theo chuẩn JPEG Hình 1.5 Sắp xếp Zigzag các hệ số DCT ở bộ mã hoá Hình 1.6 Sơ đồ khối bộ giải mã theo chuẩn JPEG Quá trình xử lý thành phần độ chói ở phía mã hoá được giải thích như sau: (a) Ảnh gốc được chia thành các khối ảnh (block) nhỏ kích thước 8x8 không chồng chéo lên nhau. Tiếp theo, giá trị của mỗi điểm ảnh ở mỗi khỗi khối ảnh sẽ được trừ đi 128. Lý do là do giá trị các điểm ảnh có giá trị từ 0 đến 255 (được mã hoá bởi 8 bít không dấu), áp dụng biến đổi DCT sẽ tạo ra các hệ số AC có dải giá trị từ -1023 đến +1023 (có thể được mã hoá bởi 11 bít có dấu). Nhưng hệ số DC lại có giải giá trị từ 0 đến 2040 (được mã hoá bởi 11 bít không dấu) và cần cách xử lý khác ở phần cứng hoặc phần mềm so với các hệ số AC. Chính vì thế việc trừ giá trị mỗi điểm ảnh đi 128 là để sau khi biến đổi DCT cả các hệ số DC và AC có cùng dải giá trị thuận lợi cho việc xử lý và biểu diễn. (b) Ở mỗi khối ảnh hai chiều kích thước 8x8, áp dụng biến đổi DCT để tạo ra mảng hai chiều các hệ số biến đổi. Hệ số có tương ứng với tần số không gian thấp nhất nhưng lại có giá trị lớn nhất được gọi là hệ số DC (một chiều), nó tỉ lệ với độ chói trung bình của cả khối ảnh 8x8. Các hệ số còn lại gọi là các hệ số AC (xoay chiều). Theo lý thuyết, biến đổi DCT không đem lại sự mất mát thông tin ảnh, mà đơn giản nó chỉ chuyển thông tin ảnh sang miền không gian mới thuật lợi hơn cho mã hoá ở bước tiếp theo. (c) Mảng hai chiều các hệ số biến đổi được lượng tử hoá sử dụng bộ lượng tử hóa tỉ lệ đồng nhất. Nghĩa là các hệ số sẽ được lượng tử hoá riêng lẻ và độc lập. Quá trình lượng tử hoá là dựa trên sinh lý của hệ thống mắt người: cảm nhận hình ảnh có độ nhậy kém hơn ở các hệ số tần số cao và có độ nhậy tốt hơn ở các hệ số có tần số thấp. Vì thế các hệ số được chọn sao cho thực hiện lượng tử hoá thô đối với các hệ số tần số cao và lượng tử hoá tinh đối với các hệ số có tần số thấp. Bảng lượng tử hoá được lấy tỉ lệ để tạo ra các mức nén thay đổi tuỳ theo tốc độ bít và chất lượng ảnh. Việc lượng tử hoá sẽ tạo ra rất nhiều giá trị 0, đặc biệt là ở tần số cao. Quá trình làm tròn trong khi lượng tử hoá chính là nguyên nhân chính gây ra sự tổn hao nhưng lại là nhân tố chính đem lại hiệu suất nén. (d) Để tận dụng ưu điểm của các hệ số đã được lượng tử có giá trị gần bằng 0, mảng hai chiều các hệ số đã được lượng tử sẽ được sắp xếp theo hình Zigzag tạo thành mảng một chiều. Cách sắp xếp này cho phép giảm thiểu năng lượng tổn hao trung bình và tạo ra dãy các giá trị bằng 0 liên tiếp. Cũng theo cách sắp xếp này, các hệ số DC được tách khỏi các hệ số AC và sử dụng kỹ thuật mã hoá điều xung mã vi sai – DPCM. (e) Bước cuối cùng của bộ mã hoá là sử dụng mã hoá entropy chẳng hạn mã hoá Huffman cho các AC và DC (sau khi đã mã hoá DPCM) để tăng thêm hiệu quả nén cũng như giảm thiểu lỗi. Ở phía giải mã, luồng bít mã hoá được giải mã entropy, sau đó mảng hai chiều các hệ số DCT đã được lượng tử hoá được giải sắp xếp Zigzag và giải lượng tử. Mảng hai chiều các hệ số DCT kết quả sẽ được biến đổi IDCT rồi cộng mỗi giá trị với 128 để xấp xỉ tạo thành các khối ảnh con kích thước 8x8. Chú ý là bảng lượng tử hoá và mã hoá entropy ở cá phía mã hoá và giải mã là đồng nhất. Hai thành phần màu cũng được mã hoá tương tự như thành phần chói ngoại trừ khác biệt là chúng được lấy mẫu xuống hệ số 2 hoặc 4 ở cả chiều ngang và dọc trước khi biến đổi DCT. Ở phía giải mã , thành phần màu sẽ được nội suy thành kích thước gốc. III.1.2.2.2 Kỹ thuật mã hoá dựa trên phép biến đổi DWT * Mối quan hệ giữa biến đổi Wavelet và Fourier Không giống như biến đổi Fourier chỉ thích hợp khi phân tích những tín hiệu ổn định (stationary),Wavelet là phép biến đổi được sử dụng để phân tích các tín hiệu không ổn định (non-stationary) – là những tín hiệu có đáp ứng tần số thay đổi theo thời gian. Để khắc phục những hạn chế của biến đổi FT, phép biến đổi Fourier thời gian ngắn – STFT được đề xuất. Chỉ có một sự khác biệt nhỏ giữa STFT và FT: Trong biến đổi STFT, tín hiệu được chia thành các khoảng nhỏ và trong khoảng đó tín hiệu được giả định là tín hiệu ổn định. Để thực hiện kỹ thuật này cần chọn một hàm cửa sổ w sao cho độ dài của cửa sổ đúng bằng các khoảng tín hiệu phân chia. Với phép biến đổi STFT, chúng ta có thể thu được đáp ứng tần số - thời gian của tín hiệu đồng thời mà với phép biến đổi FT ta không thực hiện được. Biến đổi STFT đối với tín hiệu liên tục thực được định nghĩa như sau: (1.9) Trong đó độ dài thời gian của cửa sổ là (t-τ), chúng ta có thể dịch chuyển vị trí của cửa sổ bằng cách thay đổi giá trị t và để thu được các đáp ứng tần số khác nhau của đoạn tín hiệu ta thay đổi giá trị τ . Giải thích biến đổi STFT bằng nguyên lý bất định Heissenber, nguyên lý này phát biểu là: Không thể biết được chính xác được biểu diễn thời gian - tần số của một tín hiệu (hay không thể biết các thành phần phổ của tín hiệu ở một thời điểm nhất định). Cái mà ta có thể biết là trong một khoảng thời gian nhất định tín hiệu có những băng tần nào. Đây được gọi là bài toán phân giải. Vấn đề này liên quan đến độ rộng của hàm cửa sổ mà chúng ta sử dụng. Nếu hàm cửa sổ càng hẹp thì độ phân giải càng tốt hơn và giả định tín hiệu là ổn định càng có độ chính xác nhưng độ phân giải tần số lại kém đi. Ta có các hệ quả sau: Cửa sổ hẹp -> phân giải thời gian tốt, phân giải tần số kém Cửa sổ rộng -> phân giải tần số tốt, phân giải thời gian kém Trên cơ sở cách tiếp cận biến đổi STFT, biến đổi Wavelet được phát triển để giải quyết vấn đề về độ phân giải tín hiệu (miền thời gian hoặc tần số) mà STFT vẫn còn hạn chế. Biến đổi Wavelet được thực hiện theo cách: tín hiệu được nhân với hàm Wavelet (tương tự như nhân với hàm cửa sổ trong biến đổi STFT), rồi thực hiện biến đổi riêng rẽ cho các khoảng tín hiệu khác nhau trong miền thời gian tại các tần số khác nhau. Cách tiếp cận như vậy còn được gọi là: phân tích đa phân giải – MRA (Multi Resolution Analysis): phân tích tín hiệu ở các tần số khác nhau và cho các độ phân giải khác nhau. MRA khi phân tích tín hiệu cho phép: phân giải thời gian tốt và phân giải tần số kém ở các tần số cao; phân giải tần số tốt và phân giải thời gian kém ở các tần số thấp. Như vậy kỹ thuật này rất thích hợp với những tín hiệu: có các thành phần tần số cao xuất hiện trong khoảng thời gian ngắn, các thành phần tần số thấp xuất hiện trong khoảng thời gian dài chẳng hạn như ảnh và khung ảnh video. * Biến đổi Wavelet rời rạc – DWT Bước này có thể hiểu phép biến đổi DWT như là áp dụng một tập các bộ lọc thông cao và thông thấp. Thiết kế các bộ lọc này tương đương như kỹ thuật mã hoá băng con (subband coding) nghĩa là: chỉ cần thiết kế các bộ lọc thông thấp, còn các bộ lọc thông cao chính là các bộ lọc thông thấp dịch pha đi một góc 1800. Tuy nhiên khác với mã hoá băng con, các bộ lọc trong DWT được thiết kế phải có đáp ứng phổ phẳng, trơn và trực giao. Biến đổi DWT một chiều : tín hiệu được cho đi qua các bộ lọc thông cao và thông thấp H và G rồi được lấy mẫu xuống (down sampling) hệ số 2 tạo thành biến đổi DWT mức 1. Biến đổi ngược thì thực hiện ngược lại: lấy mẫu lên (up sampling) hệ số 2 rồi sử dụng các bộ lọc khôi phục H’, G’ (lý tưởng là H’ và G’ chính là H, G). Hình 1.7 Bank lọc khôi phục lý thuyết sử dụng DWT 1D Từ biến đổi DWT một chiều có thể mở rộng định nghĩa biến đổi DWT hai chiều theo cách: Sử dụng các bộ lọc riêng biệt, thực hiện biến đổi DWT một chiều dữ liệu vào (ảnh) theo hàng rồi thực hiện theo cột. Theo cách này nếu thực hiện biến đổi DWT ở mức 1, sẽ tạo ra 4 nhóm hệ số biến đổi. Quá trình biến đổi DWT hai chiều có thể minh hoạ như hình 1.8 dưới đây, trong đó 4 nhóm hệ số là: LL, HL, LH, HH (chữ cái đầu tiên tương ứng đã thực hiện lọc theo hàng, chữ cái thứ hai tương ứng đã thực hiện lọc theo cột). Hình 1.8 Minh hoạ DWT hai chiều cho ảnh II.2 Cơ sở lý thuyết biến đổi Wavelet II.2.1 Các phép biến đổi Wavelet II.2.1.1 Biến đổi Wavelet liên tục (Continuous Wavelet Transform - CWT) Biến đổi Wavelet liên tục của một hàm f (t ) được bắt đầu từ một hàm Wavelet mẹ (mother Wavelet) ψ (t ). Hàm Wavelet mẹ ψ (t ) có thể là bất kỳ một hàm số thực hoặc phức liên tục nào thoả mãn các tính chất sau đây: - Tích phân suy rộng trên toàn bộ trục t của hàm ψ (t ) là bằng 0. Tức là: (1.10) - Tích phân năng lượng của hàm trên toàn bộ trục t là một số hữu hạn, tức là: (1.11) Điều kiện trên có nghĩa là hàm ψ (t ) phải là một hàm bình phương khả tích. Sau khi hàm Wavelet ψ (t ) được lựa chọn, biến đổi Wavelet liên tục của một hàm bình phương khả tích f (t ) được tính theo công thức: (1.12) Biến đổi này là một hàm của hai tham số thực a và b. Dấu * ký hiệu là liên hiệp phức của ψ (t ) . Nếu chúng ta định nghĩa một hàm ψa,b(t) theo biểu thức: (1.13) Chúng ta có thể viết được: (1.14) Theo toán học ta gọi đây là tích vô hướng của hai hàm f(t) và ψa,b(t) , giá trị là hệ số chuẩn hoá để đảm bảo rằng tích phân năng lượng của hàn ψa,b(t) sẽ độc lập với a và b. (1.15) Với mỗi giá trị của a thì ψa,b(t) là một bản sao của ψa,b(t) được dịch đi b đơn vị trên trục thời gian. Do đó b được gọi là tham số dịch. Đặt tham số dịch b = 0 ta thu được: (1.16) điều đó cho thấy rằng a là tham số tỷ lệ. Khi a >1 thì hàm Wavelet sẽ được trải rộng còn khi 0< a <1 thì hàm sẽ được co lại. Sau đây chúng ta sẽ định nghĩa phép biến đổi ngược của biến đổi Wavelet liên tục. Gọi Ψ(ω) là biến đổi đổi Fourier của ψ (t ) : (1.17) Nếu W(a,b) là biến đổi CWT của f (t ) bằng hàm Wavelet ψ (t ) , thì biến đổi ngược của biến đổi CWT sẽ được tính như sau: (1.18) với giá trị của C được định nghĩa là: (1.19) Biến đổi CWT chỉ tồn tại nếu C dương và hữu hạn. Do đó C được gọi là điều kiện tồn tại của biến đổi Wavelet. Cùng với hai điều kiện đã nêu ở trên, đây là điều kiện thứ 3 mà một hàm cần phải thoả mãn để có thể được lựa chọn làm hàm Wavelet. Chúng ta có thể xem biến đổi CWT như là một ma trận hai chiều các kết quả của phép tính tích vô hướng giữa hai hàm f (t) và ψa,b(t). Các hàng của ma trận tương ứng với các giá trị của a và các cột tương ứng với các giá trị của b do cách tính biến đổi Wavelet theo tích vô hướng đã trình bày ở trên: (1.20) II.2.1.2 Biến đổi Wavelet rời rạc (DWT) Việc tính toán các hệ số Wavelet tại tất cả các tỉ lệ là một công việc hết sức phức tạp, nếu tính toán như vậy sẽ tạo ra một lượng dữ liệu khổng lồ. Để giảm thiểu công việc tính toán người ta chỉ chọn ra một tập nhỏ các giá trị tỉ lệ và các vị trí để tiến hành tính toán. Hơn nữa nếu việc tính toán được tiến hành tại các tỷ lệ và các vị trí trên cơ sở luỹ thừa cơ số 2 thì kết quả thu được sẽ hiệu quả và chính xác hơn rất nhiều. Quá trình chọn các tỷ lệ và các vị trí để tính toán như trên tạo thành lưới nhị tố (dyadic). Một phân tích như trên hoàn toàn có thể thực hiện được nhờ biến đổi Wavelet rời rạc (DWT). Do đó, việc tính toán biến đổi DWT thực chất là sự rời rạc hoá biến đổi Wavelet liên tục (CWT) việc rời rạc hoá được thực hiện với sự lựa chọn các hệ số a và b như sau: Việc tính toán hệ số của biến đổi Wavelet có thể dễ dàng thực hiện bằng các băng lọc số nhiều nhịp đa kênh, một lý thuyết rất quen thuộc trong xử lý tín hiệu. Hình 2.1. Minh hoạ lưới nhị tố dyadic với các giá trị của m và n II.2.2 Tính chất của biến đổi Wavelet - Biến đổi Wavelet dù chỉ làm việc với các tín hiệu một chiều (liên tục hoặc rời rạc) nhưng sau khi biến đổi xong ta thu được một hàm số hai biến hoặc một tập các cặp giá trị W(a,b) minh họa các thành phần tần số khác nhau của tín hiệu xảy ra tại thời điểm t . - Các giá trị W (a, b) tạo thành một cột (i=1, 2,...., n) cho biết một thành phần tần số có trong những thời điểm t nào và các giá trị W (a, b) tạo thành hàng cho biết tại một thời điểm t của tín hiệu f (t ) có các thành phần tần số nào. - Tham số b trong biến đổi Wavelet cho biết khoảng dịch của hàm Wavelet mẹ và độ phân giải các tần số khác nhau của f (t ) được minh họa bởi hệ số tỷ lệ chính là a. - Ta kết hợp biến đổi Wavelet với các hàm Wavelet thích hợp với dạng tín hiệu cần khảo sát và phép phân tích đa phân giải để việc xử lý tín hiệu tiếng nói và hình ảnh đạt hiệu quả cao hơn. + Lý thuyết về đa phân giải trong phân tích tín hiệu như sau: Giả sử chúng ta cần xấp xỉ hoá một tín hiệu liên tục có dạng một hàm bình phương khả tích f (x) bằng một tập các giá trị rời rạc (ví dụ hàm f (x) là hàm cường độ sáng của ảnh). Phép xấp xỉ đơn giản thực hiện dựa trên lý thuyết phép lấy trung bình và dựa vào hàm xấp xỉ là hàm ϕ ( x) có dạng: (2.1) Với fn chính là giá trị xấp xỉ của hàm f (x) trong khoảng [n;n+1). Đây chính là giá trị trung bình của hàm f (x) trong khoảng [n;n+1) được cho bởi biểu thức: (2.2) Như vậy chúng ta có thể xấp xỉ hoá hàm f ( x) bằng một tập các hàm tương tự như hàm ϕ (x) và phép xấp xỉ hoá hàm f ( x) cho bởi: (2.3) Ở đây ϕ~ (x) được gọi là hàm trọng và ϕ ( x) là hàm nội suy, để xấp xỉ ϕ (x) thoả mãn điều kiện: (2.4) Việc phải thoả mãn điều kiện trên là để đảm bảo rằng hàm f ( x) có thể được xấp xỉ hoá bằng một tổ hợp tuyến tính của các hàm ϕ ( x − n) . Ngoài ra hai hàm ϕ~ (x) và ϕ ( x) phải được chuẩn hoá để thoả mãn: (2.5) Trong thực tế, hàm f ( x) thường được giả thiết là có chu kỳ nguyên và chúng ta chỉ cần một số hữu hạn các tổ hợp tuyến tính để xấp xỉ hoá hàm f (x). Chúng ta có thể thay đổi độ phân giải của phép xấp xỉ bằng cách thay đổi hệ số tỷ lệ của các hàm ϕ~ (x) và ϕ (x). Cho: Và Ta có xấp xỉ: (2.6) của hàm f ( x) là các phép chiếu trực giao của hàm f (x) lên không gian lấy {φf(x-2jk)} làm cơ sở. Việc thay đổi giá trị của j sẽ làm thay đổi mức độ chính xác của phép xấp xỉ hàm f (x) của chúng ta như trên hình vẽ. Hình 2.2 Phân tích đa phân giải áp dụng cho biểu diễn tín hiệu Hàm ϕ (x) được gọi là hàm tỷ lệ và chúng ta thấy hàm này có một tính chất đặc biệt là các hàm ứng với độ phân giải thứ j (tức là có chiều rộng 2j ) là trường hợp đặc biệt của các hàm có độ phân giải thứ j +1 (chiều rộng 2-j-1) bởi vì các hàm có độ phân giải j có thể dễ dàng biểu diễn từ các hàm có độ phân giải j +1. Điều đó dẫn tới: Vì vậy chúng ta có thể biểu diễn hàm f ( x) theo các mức phân giải khác nhau dựa trên các phép chiếu trực giao của hàm f (x) lên các không gian Vj. Chính vì thế người ta định nghĩa một phép phân tích đa phân giải như sau: - Một phân tích đa phân giải bao gồm một chuỗi không gian bao hàm nhau: thoả mãn: Tính bất biến tỷ lệ Tính bất biến dịch: Tính tồn tại của cơ sở: tồn tại với φє V0 với {φ(x-n)|n є Z là một cơ sở trực chuẩn của V0. Nếu chúng ta gọi A[f(x)]= ProjVm[f(x)] là hình chiếu trực giao của f(x) lên Vm thì ta có: limm->∞[f(x)]=f(x) Trên đây là cơ sở lý thuyết của phép phân tích đa phân giải với tín hiệu 1D tổng quát. Việc áp dụng trong tín hiệu ảnh (tín hiệu 2D) có thể dễ dàng mở rộng từ việc phân tích đa phân giải 1D. II.3 Nén ảnh bằng Wavelet Kỹ thuật nén ảnh bằng Wavelet hiệu năng với hai đặc tính quan trọng trong thuật toán: 1. Giảm thiểu năng lượng tính toán để thực hiện nén ảnh. 2. Giảm thiểu năng lượng khi truyền thông. II.3.1 Sơ đồ khối tổng quát Hình 3.1 Sơ đồ khối quá trình nén ảnh bằng Wavelet Hình 3.1 chỉ ra sơ đồ khái quát quá trình nén ảnh (mã hoá nguồn) như sau: Ảnh mẫu được đưa qua một phép biến đổi để tạo thành tập hệ số biến đổi. Các hệ số này tiếp tục được lượng tử hoá (chia cho các giá trị cố định cho trước) để giảm dung lượng dữ liệu. Đầu ra của bước này là một luồng các số nguyên mà mỗi một trọng số đó tương ứng với một chỉ số nhị phân được lượng tử hoá. Bước cuối cùng là mã hoá: các luồng dữ liệu được chuyển thành chuỗi các từ mã nhị phân (binary symbol). Có nhiều thuật toán sử dụng cho nén ảnh như: dựa theo phép biến đổi, lượng tự hoá véctơ hoặc mã hoá băng con. II.3.2 Biến đổi Wavelet Phép biến đổi Wavelet thuận sử dụng sự phân ly 1D (một chiều) để chuyển tập các mẫu 1D thành hai băng: băng con thông thấp (Li) và băng con thông cao (Hi). Băng Li là phiên bản có độ phân giải thấp của ảnh gốc được lấy mẫu xuống (downsampled), băng Hi biểu thị thông tin dư thừa của ảnh gốc (chỉ cần thiết khi cần khôi phục hoàn toàn ảnh gốc từ băng thông thấp). Quá trình phân ly băng con 2D chỉ là sự mở rộng quá trình phân ly băng con 1D. Toàn bộ quá trình chính là sự thực hiện quá trình phân ly 1D hai lần: đầu tiên theo hàng, rồi theo cột. Theo cách này, băng con thông thấp Li tạo thành khi phân ly theo hàng lại tiếp tục được phân ly theo cột tạo thành băng con LLi và LHi. Tương tự như vậy, băng con Hi tiếp tục được phân ly thành HLi và HHi. Sau mức biến đổi đầu tiên, ảnh có thể tiếp tục được phân ly bằng cách áp dụng quá trình phân ly 2D cho băng con LLi. Như vậy ảnh có thể được biến đổi ở nhiều mức. Hình 3.2 (a) Biến đổi Wavelet 2D mức 3 và (b) Minh hoạ bằng ảnh “CASTLE” II.3.3 Tính toán năng lượng tiêu hao Để thực hiện biến đổi Wavelet cần chọn một bộ lọc đáp những ưu điểm sau: - Kết quả sau bộ lọc Wavelet có chứa thông tin điểm ảnh lân cận và như thế loại bỏ được hiệu ứng khối mà biến đổi DCT gặp phải. - Có tính chất đối xứng và định vị cho phép dễ dàng phát hiện đường viền, tính toán nhanh, ảnh nén có chất lượng cao. - Dễ dàng thực hiện bằng phần cứng vì nó chỉ gồm các bộ cộng và bộ dịch nhị phân Ta sử dụng bộ lọc: Daubechies 5-tap/3-tap, có phương trình là: (3.1) Ví dụ: trong phép phân ly Wavelet thuận sử dụng ở bộ lọc trên, cần 8 phép toán cộng - A(Add) và dịch - S(Shift) để chuyển những điểm ảnh mẫu thành một hệ số thông thấp. Tương tự như vậy, sự phân ly thông cao cần 2 phép toán dịch và 4 phép toán cộng. Chúng ta lập mô hình tiêu hao năng lượng của sự phân ly thông thấp/cao bằng cách đếm số các phép toán và xem chúng như là tải tính toán. Như vậy có 8*S (phép dịch) + 8*A (phép cộng) là tải tính toán cần cho một điểm ảnh trong quá trình phân ly thông thấp và 2S + 4A phép toán cho thông cao. Với một ảnh đầu vào cho trước kích thước M x N và quá trình phân ly được áp dụng với L mức biến đổi, khi đó chúng ta có thể đánh giá được tổng tải tính toán như sau: Giả sử trước tiên chúng ta áp dụng quá trình phân ly theo chiều ngang. Nhưng do tất cả các điểm ảnh ở vị trí chẵn được phân ly thành các hệ số thông thấp và các điểm ảnh ở vị trí lẻ được phân ly thành các hệ số thông cao, tổng tải tính toán trong quá trình phân ly chiều ngang sẽ là 1/2MN(10S+12A). Lượng tải tính toán trong quá trình phân ly theo chiều dọc cũng dễ nhận ra. Do kích thước của ảnh giảm theo hệ số 4 sau mỗi mức biến đổi, tổng tải tính toán có thê được biểu diễn bằng công thức sau: * Tải tính toán với biến đổi Wavelet thường – CW: (3.2) Ngoài các phép toán số học, bước biến đổi cũng bao gồm một số lượng lớn các lần truy nhập bộ nhớ. Do vậy năng lượng tiêu hao trong các lần truyền dữ liệu nội và ngoại hệ thống có thể đáng kể, chúng ta ước lượng tải truy nhập dữ liệu (data-acces load) bằng cách đếm tổng số các lần truy nhập bộ nhớ trong quá trình thực hiện biến đổi Wavelet. Tại một mức biến đổi, mỗi điểm ảnh sẽ được đọc hai lần và được ghi hai lần. Do vậy, với cùng một điều kiện cũng như cùng phương pháp đánh giá như trên, tổng tải truy nhập dữ liệu rút ra bằng số các toán tử đọc và ghi. Tải truy nhập dữ liệu với biến đổi Wavelet thường: (3.3) Năng lượng tính toán tổng được tính bằng tổng trọng số của tải tính toán và tải truy nhập dữ liệu. Từ kết quả tiến hành thực nghiệm, ta thấy rằng thực hiện các phép cộng tiêu tốn năng lượng gấp đôi so với thực hiện phép dịch và năng lượng tiêu tốn cho tải truy nhập dữ liệu gấp 2.7 lần tải tính toán. Chúng ta cũng ước lượng năng lượng truyền thông bằng C*R, trong đó C là kích thước của ảnh nén (tính bằng bít) và R là tổn hao năng lượng để truyền một bít bằng bộ phát RF. II.3.4 Thuật toán nén ảnh bằng Wavelet hiệu năng - EEW Trong phần này, chúng ta trình bầy thuật toán EEW (Effective Energy Wavelet) - một thuật toán biến đổi bằng Wavelet mà mục đích là tiết kiệm năng lượng trong khi chất lượng ảnh chỉ bị ảnh hưởng ít nhất. Cách này có hai ưu điểm chính sau: + Thứ nhất, bởi vì các hệ số thông cao không cần phải tính toán, EEW làm giảm năng lượng tính toán tiêu hao trong quá trình nén ảnh bằng Wavelet bằng cách giảm số lượng các phép toán đã được thực hiện. + Thứ hai, bởi vì bộ mã hoá và giải mả là kỹ thuật làm tròn (ước lượng), vì thế không có thông tin yêu cầu được truyền qua kênh vô tuyên, do đó giảm được năng lượng tiêu hao cần có. Hình3.3 Phân bố số học các hệ số thông cao sau phép biến đổi Wavelet mức 2 Sử dụng kỹ thuật ước lượng ở trên chúng ta đã xây dựng được thuật toán gồm hai kỹ thuật hạn chế tiêu hao năng lượng: hạn chế tính toán và truyền thông cho các hệ số thông cao: Kỹ thuật đầu tiên là loại bỏ băng con ít ý nghĩa nhất. Trong số 4 băng con ta thấy băng con đường chéo (HHi) là ít ý nghĩa nhất, và là ứng cử viên sáng giá để loại bỏ ở trong bước biến đổi Wavelet. Chúng ta gọi kỹ thuật này là kỹ thuật “loại bỏ HH”. Ở kỹ thuật thứ 2, thì chỉ những băng con có ý nghĩa nhất (chứa thông tin độ phân giải thấp, LLi) được giữ lại còn các băng thông cao khác (LHi, HLi và HHi) đều được loại bỏ. Chúng ta gọi kỹ thuật này là kỹ thuật “loại bỏ H*” (tất cả các băng con thông cao đều bị loại bỏ trong bước biến đổi). * Hiệu năng của các kỹ thuật loại bỏ Để thực hiện các kỹ thuật loại bỏ HH và H* (EEW), chúng ta thay đổi phép biến đổi Wavelet như mô tả trong hình 3.4. Như đã giải thích ở trên, trong quá trình biến đổi Wavelet, mỗi ảnh đầu vào được thực hiện phép biến đổi theo hàng rồi đến cột và phân ly ảnh thành bốn băng con (LL, LH, HL, HH). Tuy nhiên, để thực hiện kỹ thuật loại bỏ HH, thì sau khi thực hiện biến đổi theo hàng, các hệ số thông cao chỉ được đưa vào bộ lọc thông thấp mà không được đưa vào bộ lọc thông cao trong bước biến đổi theo cột tiếp theo (trong hình 4 bên dưới , ký hiệu là những hình có bóng sáng). Cách làm này đã loại bỏ băng con đường chéo HH. Còn để thực hiện kỹ thuật loại bỏ H*, ảnh đầu vào được xử lý chỉ cho qua bộ lọc thông thấp trong cả quá trình thực hiện biến đổi hàng và cột. Và như vậy chúng ta cũng loại bỏ được tất cả các bước phân ly thông cao trong quá trình biến đổi. Hình 3.4 Dữ liệu sau phép biến đổi Wavelet với hai kỹ thuật loại bỏ HH và H* Để ước lượng hiệu năng của các kỹ thuật EEW ở trên, chúng ta sẽ tiến hành tính tải tính toán và tải truy nhập dữ liệu theo phương pháp đã đề cập ở trên. Chúng ta giả thiết rằng, các kỹ thuật tính toán chỉ được áp dụng ở E mức biến đổi đầu tiên trong tổng số L mức. Lý do là bởi vì ưu điểm của các hệ số thông cao thực hiện loại bỏ càng ý nghĩa ở các mức biến đổi thấp. Trong kỹ thuật loại bỏ HH, tải tính toán trong quá trình thực hiện biến đổi theo hàng bằng với thuật toán Wavelet thường. Tuy nhiên, trong quá trình thực hiện biến đổi theo cột băng con thông cao là kết quả từ phép biến đổi theo dòng trước, băng con HH không được tính. Kết quả trong mục trên chỉ ra rằng làm như vậy có thể tiết kiệm 1/4MN(4A+2S) các phép toán cho tải tính toán ( nghĩa là tiết kiệm được 7.4% so với thuật toán Wavelet thường). Và vì thế, tổng tải tính toán có thể được tính như sau: (3.4) Bởi vì băng con thông cao sau phép biến đổi theo hàng vần cần để tính băng con HL trong phép biến đổi theo cột nên chúng ta có thể tiết kiệm số lần “đọc” trong kỹ thuật loại bỏ HH. Tuy nhiên, chúng ta chỉ tiết kiệm được 1/4 các lần “ghi” (tiết kiệm 25%) trong quá trình thực hiện phép biến đổi theo cột. Do vậy kết quả băng con HH được gán trước bằng 0 trước khi quá trình biến đổi được thực hiện. Do vậy, tổng tải truy cập dữ liệu sẽ được tính: (3.5) Kỹ thuật loại bỏ H* cho kết quả đáng kể trong việc tiết kiệm năng lượng tính toán bởi đã có 3 trong tổng số 4 băng con được loại bỏ. Phần tới chúng ta sẽ tập trung mô tả và minh họa các kỹ thuật trên. II.4 Chuẩn nén ảnh tỉnh dựa trên biến đổi Wavelet-JFEG2000 Các bước thực hiện nén ảnh theo chuẩn JPEG2000 Hình 4.1 Trình tự mã hoá (a) và giải mã JPEG2000 (b) Bước 1: Xử lý trước biến đổi Bước 2: Biến đổi liên thành phần Bước 3: Biến đổi riêng thành phần (biến đổi Wavelet) Bước 4: Lượng tử hoá - Giải lượng tử hoá Bước 5: Mã hoá và kết hợp dòng dữ liệu sau mã hoá II.4.1 Xử lý trước biến đổi Do sử dụng biến đổi Wavelet, JPEG2000 cần có dữ liệu ảnh đầu vào ở dạng đối xứng qua 0. Xử lý trước biến đổi chính là giai đoạn đảm bảo dữ liệu đưa vào nén ảnh có dạng trên. Ở phía giải mã, giai đoạn xử lý sau biến đổi sẽ trả lại giá trị gốc ban đầu cho dữ liệu ảnh. II.4.2 Biến đổi liên thành phần Giai đoạn này sẽ loại bỏ tính tương quan giữa các thành phần của ảnh. JPEG2000 sử dụng hai loại biến đổi liên thành phần là biến đổi màu thuận nghịch (Reversible Color Transform - RCT) và biến đổi màu không thuận nghịch (Irreversible Color Transform - ICT) trong đó biến đổi thuận nghịch làm việc với các giá trị nguyên, còn biến đổi không thuận nghịch làm việc với các giá trị thực. ICT và RCT chuyển dữ liệu ảnh từ không gian màu RGB sang YCrCb. RCT được áp dụng trong cả hai dạng thức nén có tổn thất và không tổn thất, còn ICT chỉ áp dụng cho nén có tổn thất. Việc áp dụng các biến đổi này trước khi nén ảnh không nằm ngoài mục đích làm tăng hiệu quả nén. Các thành phần Cr, Cb có ảnh hưởng rất ít tới sự cảm nhận hình ảnh của mắt trong khi thành phần độ chói Y có ảnh hưởng rất lớn tới ảnh. Hình 4.2 Minh hoạ ảnh với RGB và YCrCb II.4.3 Biến đổi riêng thành phần (biến đổi Wavelet) Biến đổi riêng thành phần được áp dụng trong JPEG2000 chính là biến đổi Wavelet. Để đảm bảo tính toàn vẹn thông tin cũng phải áp dụng các phép biến đổi thuận nghịch hoặc không thuận nghịch. Do phép biến đổi Wavelet không phải là một phép biến đổi trực giao như biến đổi DCT mà là một phép biến đổi băng con nên các thành phần sẽ được phân chia thành các băng tần số khác nhau và mỗi băng sẽ được mã hóa riêng rẽ. JPEG2000 áp dụng biến đổi Wavelet nguyên thuận nghịch 5/3 (IWT) và biến đổi thực không thuận nghịch Daubechies 9/7. Việc tính toán biến đổi trong JPEG2000 này sẽ được thực hiện theo phương pháp Lifting. Sơ đồ của phương pháp Lifting 1D áp dụng trong JPEG2000 trên hình 4.3.Việc tính toán biến đổi Wavelet 2D suy ra từ biến đổi Wavelet 1D theo các phương pháp phân giải ảnh tuỳ chọn. Trong JPEG2000 có 3 phương pháp phân giải ảnh nhưng phương pháp được sử dụng nhiều nhất chính là phương pháp kim tự tháp. Hình 4.3 Phương pháp Lifting 1D dùng tính toán biến đổi Wavelet Do biến đổi Wavelet 5/3 là biến đổi thuận nghịch nên có thể áp dụng cho nén ảnh theo cả hai phương pháp, có tổn thất và không tổn thất trong khi biến đổi 9/7 chỉ áp dụng cho nén ảnh theo phương pháp có tổn thất thông tin. III.4.4 Lượng tử hoá - Giải lượng tử hoá Các hệ số của phép biến đổi sẽ được tiến hành lượng tử hoá. Quá trình lượng tử hoá cho phép đạt tỷ lệ nén cao hơn bằng cách thể hiện các giá trị biến đổi với độ chính xác tương ứng cần thiết với mức chi tiết của ảnh cần nén. Các hệ số biến đổi sẽ được lượng tử hoá theo phép lượng tử hoá vô hướng. Các hàm lượng tử hoá khác nhau sẽ được áp dụng cho các băng con khác nhau và được thực theo biểu thức: (4.1) với Δ là bước lượng tử, U(x,y) là giá trị băng con đầu vào; V(x,y) là giá trị sau lượng tử hoá. Trong dạng biến đổi nguyên, đặt bước lượng tử bằng 1.Với dạng biến đổi thực thì bước lượng tử sẽ được chọn tương ứng cho từng băng con riêng rẽ. Bước lượng tử của mỗi băng do đó phải có ở trong dòng bít truyền đi để phía thu có thể giải lượng tử cho ảnh. Công thức giải lượng tử hoá là: (4.2) r là một tham số xác định dấu và làm tròn, các giá trị ( U x,y);V(x,y) tương ứng là các giá trị khôi phục và giá trị lượng tử hoá nhận được. JPEG2000 không cho trước r tuy nhiên thường chọn r = 1/2 . II.4.5 Mã hoá và kết hợp dòng dữ liệu sau mã hoá JPEG2000 theo khuyến nghị của uỷ ban JPEG quốc tế có thể sử dụng nhiều phương pháp mã hoá khác nhau cũng như nhiều cách biến đổi Wavelet khác nhau để có thể thu được chất lượng ảnh tương ứng với ứng dụng cần xử lý. Điều này giúp cho JPEG2000 mềm dẻo hơn nhiều so với JPEG. Việc áp dụng các phương pháp mã hoá khác nhau cũng được mở rộng sang lĩnh vực nén ảnh động bằng biến đổi Wavelet. Trong thực tế các phương pháp mã hoá ảnh được áp dụng khi nén ảnh bằng biến đổi Wavelet cũng như JPEG2000 thì có hai phương pháp được coi là cơ sở và được áp dụng nhiều nhất: phương pháp SPIHT và phương pháp EZW. Hiện nay JPEG2000 vẫn được áp dụng mã hoá bằng hai phương pháp này và một phương pháp phát triển từ hai phương pháp này là phương pháp mã hoá mặt phẳng bít. Vì thế ở đây chúng ta sẽ xem xét hai phương pháp này. Việc kết hợp dòng dữ liệu sau mã hoá của JPEG2000 thực chất là để thực hiện các tính năng đặc biệt của JPEG2000 như tính năng ROI v.v... * Phương pháp mã hoá EZW Phương pháp mã hoá EZW (Embedded Zerotree Wavelet Encoder) dựa trên cơ sở phép mã hoá luỹ tiến (progressive coding). Phương pháp này chủ yếu dựa trên khái niệm về cây zero (zerotree). Sau đây chúng ta sẽ xem xét các khái niệm cơ bản của thuật toán: Cây tứ phân: Sau khi áp dụng biến đổi Wavelet ứng với các mức phân giải khác nhau chúng ta có thể biểu diễn các hệ số biến đổi dưới dạng một cây. Ta thấy rằng với cây biểu diễn này cứ mỗi nút cha thì có 4 nút con. Sở dĩ có được điều này là do quá trình biến đổi Wavelet ở các tỷ lệ khác nhau. Ta gọi đây là các cây tứ phân (quadtree). Sơ đồ cây tứ phân được minh hoạ ở hình 4.4 Hình 4.4 Minh họa cây tứ phân (a) và sự phân mức (b) Cây zero (zerotree): Cây zero là một cây tứ phân, trong đó tất cả các nút của nó đều nhỏ hơn nút gốc. Một cây như vậy khi mã hoá sẽ được mã hoá bằng một đối tượng duy nhất và khi giải mã thì chúng ta cho tất cả các giá trị bằng không. Ngoài ra để có thể mã hoá được các hệ số Wavelet trong trường hợp này, giá trị của nút gốc phải nhỏ hơn giá trị ngưỡng đang được xem xét ứng với hệ số Wavelet đó. Sau khi có đủ các khái niệm cần thiết về cây tứ phân và cây zero, chúng ta có thể trình bày nguyên lý hoạt động của thuật toán. Thuật toán sẽ mã hoá các hệ số theo thứ tự giảm dần. Chúng ta sẽ dùng một giá trị gọi là ngưỡng (threshold) và sử dụng ngưỡng này để tiến hành mã hoá các hệ số biến đổi. Các hệ số được mã hoá theo thứ tự từ vùng tần số thấp đến vùng tần số cao. Và chỉ những hệ số có giá trị tuyệt đối lớn hơn hoặc bằng ngưỡng thì mới được mã hoá. Tiếp theo giảm ngưỡng và tiếp tục làm như vậy cho tới khi ngưỡng đạt tới một giá trị nhỏ hơn giá trị của hệ số nhỏ nhất. Cách giảm giá trị ngưỡng ở đây thực hiện tương đối đặc biệt, giá trị của ngưỡng giảm xuống một nửa so với trước đó. Bộ giải mã phải biết các mức ngưỡng này thì mới có thể giải mã ảnh thành công. Nhưng khi ta đi từ nút cha đến nút con trong cây tứ phân thì nó vẫn có 3 nút con. Vậy ta phải đi theo nhánh có nút con nào trước. Hay nói một cách đầy đủ hơn ta di chuyển từ hệ số này đến hệ số khác theo thứ tự như thế nào. Có nhiều cách di chuyển khác nhau, tuy nhiên hai cách di chuyển trên hình 4.5 được sử dụng nhiều nhất. Hình 4.5 Hai cách sắp xếp thứ tự các hệ số biến đổi Việc sắp xếp này còn phải được quy ước thống nhất giữa quá trình mã hoá và quá trình giải mã để việc giải mã ảnh được thành công. Trên đây chỉ là nguyên lý cơ bản của phương pháp mã hoá EZW. Chi tiết về thuật toán mã hoá có thể xem ở phần chương trình. Hiện nay phương pháp mã hoá này được áp dụng ngày càng nhiều nén ảnh động. Phương pháp này cho tỉ lệ nén và độ tin cậy giải mã cao. Ngoài ra phương pháp EZW rất dễ triển khai trên máy tính bởi phương pháp này không yêu cầu việc lập trình quá phức tạp. III. KẾT LUẬN Kỹ thuật nén ảnh ngày nay đã phát triển mạnh mẽ nhờ áp dụng được các thuật toán mới, được hỗ trợ nhiều thiết bị tính toán và trở thành một công cụ không thể thiếu trong mạng truyền thông. Các ứng dụng về đồ họa, hình ảnh, video đa phương tiện... áp dụng hiệu quả công cụ này đã chứng minh cho điều đó. Bài tiểu luận này đã mô tả khái quát các mô hình nén ảnh thông dụng trên cơ sở các lý thuết về động học và toán học. - Nén ảnh là một quá trình mã hóa, giải mã các thông tin giữ liệu ảnh nhằm loại bỏ các dữ liệu dư thừa hoặc không quan trọng cho tính trực quan để giảm dung lượng dữ liệu. - Hai kỹ thuật cơ bản là sử dụng các phép biến đổi DCT và Wavelet và phép dự đoán. - Có khả năng xử lý các ảnh phức tạp, đa thành phần. - có thể đưa các tham số đầu vào các bộ biến đổi của quá trình nén ảnh từ người sử dụng hoặc các ứng dụng nhằm điều chỉnh được tỷ lệ nén và chất lượng ảnh theo yêu cầu. IV. TÀI LIỆU THAM KHẢO 1. TSKH. Nguyễn Ngọc San: Bài giảng môn học về công cụ toán học cơ sở và lý thuyết hệ thống-xử lý tín hiệu; Chuyên đề môn học XLSTH, MHH&Mô phỏng mạng thông tin CH ĐTVT khóa 5 do thầy giáo hướng dẫn, 2004-2005, Học viện CNBCVT VNPT. 2. Nhập môn xử lý ảnh số - Lương Mạnh Bá- Nguyễn Thanh Thủy. 3. Borko Furht, Stephen W.Smoliar, Hong Jiang Zhang – “Video and Image Processing in multimedia systems”. 4. Geoffrey Davis - Arina Nosratinia - “Waveled-Based Image Encoding - Overview”. 5. Geoffrey Davis - Roger Claypoole - Wim Sweldens - Richard G.Baraniuk - “Nonlinear Wavelet transform for Image Coding via lifting” 6. PIKS Inside, Third Edition. William K. Pratt: Digital Image Processing 7. Richard W. Hamming: Haar Wavelets 8. Martin Vetterli - Jelena Kovacevic - “Wavelet and Subband Coding”