TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

BÁO CÁO MÔN HỌC
XỬ LÝ DỮ LIỆU ĐA PHƯƠNG TIỆN

Đề 2: Dữ liệu ảnh số (cấu trúc, định dạng dữ
liệu), mã hóa dự đoán không tổn hao, thuật toán
mã hóa ảnh theo chuẩn jpeg-ls.
Giảng viên hướng dẫn
Học viên thực hiện
Mã HV
Lớp

Hà Nội 10-2017
1

: PGS.TS. Nguyễn Thị Hoàng Lan
:
:
: 16BTTM


MỤC LỤC

I. Dữ liệu ảnh số
Hệ thống xử lý ảnh:

Ảnh sau khi thu nhận qua bộ cảm biến là ảnh tương tự. Tín hiệu ảnh này được số
hóa để tạo ra dữ liệu ảnh số. Số hóa ảnh nhằm tạo thuận tiện cho việc lưu trữ cũng như xử
lý ảnh.

Có 2 khuôn dạng ảnh số thường gặp đó là ảnh Vector và ảnh Raster (hay ảnh
Bitmap)
1.1 Cấu trúc ảnh Vector
1.1.1 Khái niệm
Ảnh Vector được tạo nên từ những phần tử là những yếu tố cốt lõi của hình học như
đường thẳng, đường cong, những hình dạng, đa giác. Dữ liệu ảnh Vector tạo thành dựa
trên các vector, các vector lại được tạo thành từ các biểu thức toán học. Vector chạy qua
các điểm mút, mỗi điểm có một tọa độ (x,y) nhất định trên hệ trục tọa độ. Mỗi một vector
này có thể được gán cho các thuộc tính riêng như màu sắc, độ dày mỏng , v..v.
1.1.2 Các ưu và nhược điểm của ảnh Vector
Ảnh Vector có các ưu điểm nổi bật sau:
2


-

Mã hóa ảnh bằng các hình đơn giản
Gọn, kích thước nhỏ
Thay đổi kích thước đơn giản, không bị mất thông tin.
Sửa dễ dàng do các phần tử của ảnh độc lập.

Nhược điểm của ảnh Vector:
-

Không biểu diễn được các ảnh chụp
Xử lý các ảnh phức tạp (nhiều đối tượng) gặp nhiều khó khăn
Khuôn dạng không chuẩn nên các trình duyệt web không nhận dạng được

1.1.3 Khuôn dạng WMF (Windows Metafile)
Chứa các thông tin về các đối tượng, một file WMF có thể chứa 65535 đối tượng.

Là ảnh đồ họa chứa cả dữ liệu ảnh bitmap và ảnh vectơ. Ví dụ một ảnh vectơ có
thể chứa đối tượng mẫu được tạo thành từ các điểm pixel như là tô màu vùng. Lúc đó file
này chứa ảnh vectơ nhưng thuộc tính tô màu được ghi dưới dữ liệu ảnh bitmap.
1.1.4 Ứng dụng ảnh Vector
Ảnh Vector thường được sử dụng trong các trường hợp như :
-

Thiết kế logo : Vì logo cần sự nhất quán trong mọi trường hợp sử dụng, người

-

ta có thể phóng to, thu nhỏ mà không ảnh hưởng quá nhiều đến tổng thể logo.
Thiết kế icon : icon cũng cần thay đổi nhiều về kích thước, đặc biệt là phải nhẹ,

-

sắc nét.
Nghệ thuật Vector (Vector art): Người ta dùng các vector, các mảng (shapes),
lưới chuyển màu (gradient meshes)... để tạo nên những hình ảnh độc đáo, gọi
là nghệ thuật Vector.

1.1.5 Một số định dạng file dữ liệu ảnh Vector :
- PDF: là định dạng file sách phổ biến bật nhất do ưu thế hỗ trợ bit map lẫn
vector và text (Dùng illustrator mở file PDF có thể chỉnh sửa các hình vector
hoặc nội dung chữ trên định dạng này). Đây cũng là địng dạng mà nhà thiết kế
-

chuyển xuống nhà in.
EPS : là định dạng xuất phim trong in ấn. khi chuyển từ ai sang định dạng này


-

các file link sẽ được nhúng vào 1 file ép luôn, không thay đổi cấu trúc lớp.
AI : là file lưu của Adobe Illustrator.
3


-

CDR : là file lưu của Corel.
SVG : là định dạng vector mà có thể hiển thị trên web.
DWG : là định dạng file lưu của Autocad.

1.2 Cấu trúc dữ liệu ảnh Raster (Bitmap)
1.2.1 Khái niệm:
Ảnh Raster hay còn gọi là ảnh bitmap là ảnh được tạo nên từ một lưới các điểm
ảnh (hay Pixel). Điểm ảnh là một phần tử của ảnh số tại toạ độ (x, y) với độ xám hoặc
màu nhất định. Có nhiều mô hình màu khác nhau cho mỗi điểm ảnh: RGB, YUV,YcbCr,
… Kích thước và khoảng cách giữa các điểm ảnh đó được chọn thích hợp sao cho mắt
người cảm nhận sự liên tục về không gian và màu của ảnh số gần như ảnh thật. Mỗi phần
tử trong ma trận được gọi là một phần tử ảnh. Đây là cách biểu diễn ảnh thông dụng hiện
nay.
1.2.2 Đặc điểm ảnh Raster
- Khuôn dạng ảnh Raster thuận lợi cho hiển thị và in ấn.
- Thiết bị thu nhận ảnh Raster phù hợp với tốc độ nhanh và chất lượng cao cho
-

cả đầu vào và đầu ra.
Thuận lợi hiển thị trên môi trường Windows.


1.2.3 Mã hóa màu
Ảnh là tập hợp các điểm ảnh, thông tin của từng điểm ảnh sẽ quyết định loại ảnh.
thông tin của từng điểm ảnh sẽ quyết định loại ảnh là: ảnh đen trắng (ảnh nhị phân), ảnh
đa mức xám (dùng N bit để mã hóa mức xám) hay ảnh màu.
Với ảnh đa mức xám : Nếu dùng 8bit (1 byte) để biểu diễn mức xám cho một điểm
ảnh thì số các mức xám có thể biểu diễn được là 2 8 hay 256. Mỗi mức xám được biểu
diễn dưới dạng là một số nguyên nằm trong khoảng tử 0 đến 255, với mức 0 biểu diễn
cho mức cường độ đen nhất và 255 biểu diễn cho mức cường độ sáng nhất.
Với ảnh màu : Cách biểu diễn cũng tương tự như ảnh đen trắng, chỉ khác là các số
tại mỗi phần tử của ma trận biểu diễn cho 3 màu riêng rẽ gồm: đỏ, lục và lam (Red,
Green, Blue). Để biểu diễn cho một điểm ảnh màu cần 24 bit, 24 bit này được chia thành
3 khoảng 8 bit. Mỗi khoảng này biểu diễn cho cường độ sáng của một trong các màu
4


chính. Vậy với ảnh màu như trên sử dụng 3 bytes mô tả mức màu, chúng ta sẽ có
28*3=224≈ 16,7 triệu màu.
1.2.4 Độ phân giải ảnh
Độ phân giải (Resolution) của ảnh là mật độ điểm ảnh được ấn định trên một ảnh
số được hiển thị.
Theo định nghĩa, khoảng cách giữa các điểm ảnh phải được chọn sao cho mắt
người vẫn thấy được sự liên tục của ảnh. Việc lựa chọn khoảng cách thích hợp tạo nên
một mật độ phân bổ, đó chính là độ phân giải và được phân bố theo trục x và y trong
không gian hai chiều.
Ví dụ: Độ phân giải của ảnh trên màn hình CGA (Color Graphic Adaptor) là một
lưới điểm theo chiều ngang màn hình: 320 điểm chiều dọc * 200 điểm ảnh (320*200). Rõ
ràng, cùng màn hình CGA 12” ta nhận thấy mịn hơn màn hình CGA 17” độ phân giải
320*200. Lý do: cùng một mật độ (độ phân giải) nhưng diện tích màn hình rộng hơn thì
độ mịn (liên tục của các điểm) kém hơn.
1.2.5 Một số định dạng file dữ liệu ảnh Bitmap:

- BMP (Bitmap): Chuẩn raster dùng trong MS-Windows
- JPG : là định dạng nén phổ biến nhất của máy ảnh số và trên website. Có tỷ lệ
nén cao nên tối ưu hóa đối với lưu trữ và truyền dữ liệu trên mạng. Tuy nhiên,
do sử dụng phương pháp nén có tổn hao nên chất lượng ảnh bị ảnh hưởng khi
-

tỷ lệ nén cao.
GIF : là định dạng nén hỗ trợ nền trong suốt, và hình ảnh động đơn giản.
PNG : Là phiên bản mã nguồn mở thay thế cho GIF. Sử dụng phương pháp
nén không tổn hao nên phù hợp với ảnh có nhiều mảng đồng màu lớn. Ảnh
PNG Phù hợp với web vì có khả năng hiển thị từng bước. Có thêm kênh alpha

-

để thể hiện độ trong.
TIFF : Là định dạng không nén nên kích thước rất lớn, thường được sử dụng
để lưu trữ hình ảnh. Hỗ trợ 6 kiểu mã hóa (không nén, Huffman, Pack Bits,
LZW, Fax Group 3, Fax Group 4); 3 kiểu màu (Đen trắng, đa cấp xám, màu)

5


-

PSP : là định dạng không nén của photoshop, giữ nguyên cấu trúc lớp và dạng

-

chỉnh sửa không dùng được trên web, power point.
RAW: Xuất hiện trên một số máy ảnh tuy nhiên có thể không cùng chuẩn. Có

thể sử dụng nén không tổn hao.

II. Mã hóa dự đoán không tổn hao
2.1 Khái niệm
Nén dữ liệu (Data Compression): Nén dữ liệu nhằm làm giảm giảm lượng thông
tin “dư thừa” trong dữ liệu gốc (dư thừa thông tin về không gian, thời gian, dư thừa về
phổ và dư thừa do độ cảm nhận), nhằm mục đích 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ố bít mã hoá ít hơn so với bức
ảnh gốc. . Ngoài thuật ngữ “nén dữ liệu”, do bản chất của kỹ thuật này nó còn có một số
tên gọi khác như : giảm độ dư thừa, mã hóa ảnh gốc.
Sơ đồ chung của hệ thống nén dữ liệu:

Trong đó Bộ mã hóa tín hiệu (Encoder) thường có cấu trúc như hình dưới, bao
gồm: Bộ chuyển đổi (T), bộ lượng tử hóa (Q) và bộ mã hóa (E).
-

Bộ chuyển đổi: thường dùng các phép biến đổi không gian để chuyển ảnh
trong không gian thực sang một không gian khác, nơi các hệ số chuyển đổi có

-

mức độ tương quan thấp hơn. Kết quả nhận được là ma trận các hệ số biến đổi.
Bộ lượng tử hoá: sử dụng phương pháp lượng tử không đồng đều nhằm triệt
tiêu các hệ số biến đổi có năng lượng thấp hoặc đóng vai trò không quan trọng
khi khôi phục ảnh. Quá trình lượng tử không có tính thuận nghịch: ảnh khôi

-

phục sẽ bị biến dạng so với ảnh gốc.
Bộ mã hoá: gán một từ mã (một dòng bit nhị phân) cho một mức lượng tử.


6


Hình 1. Sơ đồ hệ thống nén ảnh

Nén dữ liệu ảnh số giúp giảm kích thước ảnh, làm cho ảnh có thể dễ dàng lưu trữ
hoặc truyền đi trên mạng.
Về cơ bản có 2 dạng nén: (i) Nén có tổn hao (Lossy Compression) và (ii) Nén
không tổn hao (Lossless Compression).
(i) Nén có tổn hao: dữ liệu ảnh sau khôi phục (giải mã) sai khác với ảnh gốc do
quá trình nén có làm mất một số thông tin tuy nhiên chất lượng ảnh vẫn đảm bảo (về mặt
cảm nhận) và thường đạt được hiệu quả nén rất cao. Các phương pháp nén có tổn hao đa
phần dựa trên các biến đổi ảnh.
(ii) Nén không tổn hao (Lossless Compression): Ảnh khôi phục hoàn toàn giống
ảnh gốc. Các phương pháp nén này thường dựa trên các phương pháp mã hóa dữ liệu.
2.2 Phương pháp mã hóa dự đoán không tổn hao
Nguyên tắc của các phương pháp mã hóa này dựa trên tính tương quan giữa những
điểm ảnh nằm kề nhau và kỹ thuật tách và truyền thông tin "mới" chứa trong mỗi điểm
ảnh. Theo những nghiên cứu thống kê về phân bố biên độ tín hiệu video, mức độ tương
quan giữa các điểm ảnh nằm gần nhau trong miền không gian là khá cao, điều này có
nghĩa là sự khác biệt giữa hai điểm ảnh kế bên rất nhỏ hoặc bằng 0, vì thế khi mã hóa độ
chênh lệch này (sự sai khác giữa các mẫu) cần số lượng bit ít hơn so với khi mã hóa toàn
bộ biên độ các mẫu. Giá trị mẫu được giải mã dựa trên giải mã sự sai khác và giá trị
dự đoán ở thời điểm trước.
Quá trình mã hóa không tổn hao thường cài đặt một mô hình mã hóa dự đoán đơn
giản gọi là điều xung mã sai phân (DPCM – Differential Pulse Code Modulation). Trong
7



mô hình này, các giá trị dự đoán của mẫu được ước lượng từ các mẫu lân cận đã được mã
hóa trong hình ảnh. Hầu hết các bộ dự đoán (predictors) đều lấy trung bình các mẫu
ngay phía trên và bên trái mẫu đích. DPCM mã hóa sự sai khác giữa các mẫu được dự
đoán thay vì mã hóa từng mẫu một cách độc lập. Sự khác biệt từ mẫu này đến mẫu kế
tiếp thường gần bằng không. Một bộ mã hoá DPCM (DPCM encoder) điển hình được mô
tả ở hình dưới

Hình 2. Mô hình DPCM encoder

Trong đó:
-

-

Bộ dự đoán (Predictor): tính toán dự đoán ra các mẫu tín hiệu theo mẫu tại thời
điểm trước (tín hiệu tham chiếu).
Sai số dự đoán (Prediction error): Sai khác giữa tín hiệu dự đoán với tín hiệu
được truyền đến. Sai số dự đoán được dùng để giải mã đảm bảo không mất mát
thông tin.
Bộ mã hóa (Encoder): Mã hóa các sai số dự đoán, ví dụ Huffman.

Các bước chính của quá nén không tổn hao được mô tả trong hình dưới. Trong quá
trình này, bộ dự đoán kết hợp ba mẫu lân cận A, B và C (thể hiện trong bảng dưới) để tạo
ra dự đoán giá trị mẫu tại vị trí X. Ba mẫu lân cận phải là các mẫu đã được mã hóa. Bất
kỳ một bộ dự đoán được chỉ ra trong bảng dưới đây cũng có thể được sử dụng để ước
lượng mẫu đặt tại X. Ta có thể sử dụng bất kỳ một trong tám bộ dự đoán được liệt kê
trong bảng. Lưu ý rằng các lựa chọn 1, 2, và 3 là các bộ dự đoán một chiều và các lựa
chọn 4, 5, 6, và 7 là các bộ dự đoán hai chiều. Giá trị lựa chọn đầu tiên trong bảng, 0, chỉ
được sử dụng cho mã sai phân trong chế độ phân cấp của quán trình nén. Sau khi tất cả
các mẫu đã được dự đoán, sai số giữa các mẫu được mã hoá entropy bằng cách sử dụng

mã hóa Huffman hoặc mã số học số học.
8


Hình 3. Sơ đồ khối đơn giản của quá trình nén không tổn hao

Hình 4. 3 mẫu lân cận xung quanh mẫu được dự đoán
Prediction
No prediction
A
B
C
A+ B–C
A + (B – C)/2
B + (A – C)/2
(A + B)/2
Lựa chọn giá trị dự đoán
Thông thường, các phương pháp nén không tổn hao có thể đạt được tỷ lện nén 2:1
cho các ảnh màu và thường được sử dụng phổ biến trong lĩnh vực y tế. Một số thuật toán
nén không tổn hao phổ biến như lossless JPEG, JPEG-LS, JPEG 2000, PNG và CALIC.
-

Lossless JPEG: thuật toán nén ảnh dự đoán với một mã hóa entropy số học
hoặc Huffman.
JPEG-LS: thuật toán nén ảnh có độ phức tạp thấp với bộ mã hóa entropy và
thuật toán LOCO-I
9


-


-

JPEG-2000: phương pháp nén ảnh dựa trên phép biến đổi sóng con và mã hóa
số học. Tiêu chuẩn này hỗ trợ các hai phương pháp nén ảnh có và không có tổn
hao, giúp tạo ra các bức ảnh có chất lượng cao.
PNG: thuật toán nén ảnh dự đoán dùng LZ77 và bộ mã hóa Huffman.
CALIC: bộ mã hóa entropy số học với tỷ lệ nén cao.

Trong các thuật toán này, thì JPEG-LS đạt được hiệu năng tốt nhất với tỷ lệ nén
(Compression Ratio - CR) và tốc độ nén (Compression Speed - CS) so với các thuật toán
còn lại [2]

III. Thuật toán mã hóa ảnh theo chuẩn JPEG-LS
3.1 Giới thiệu
JPEG-LS là một thuật toán đơn giản bao gồm hai pha độc lập và riêng biệt: mô
hình hóa (modeling) và mã hóa (encoding). JPEG-LS cung cấp một tiêu chuẩn nén hình
ảnh không tổn hao và ít tổn hao có độ phức tạp thấp mang lại hiệu quả nén tốt hơn JPEG
lossless.
Tiêu chuẩn JPEG lossless dựa trên mã hóa Huffman và các tiêu chuẩn khác bị giới
hạn trong hiệu suất nén do cách thiết kế của chúng. Phần lõi của tiêu chuẩn JPEG-LS dựa
trên thuật toán LOCO-I, là thuật toán dựa vào dự đoán, mô hình hóa dư (residual
modeling) và mã hoá dựa trên ngữ cảnh của các phần dư.
Thuật toán nén JPEG-LS nhìn chung là nhanh hơn nhiều so với JPEG 2000 và tốt
hơn nhiều so với tiêu chuẩn JPEG lossless ban đầu.
3.2 Thuật toán LoCo-I
JPEG-LS áp dụng lý thuyết nén ảnh không tổn hao theo DPCM, trong đó mẫu dự
đoán Px được tính toán dựa trên 3 lân cận như hình sau:

10



Trong hình vẽ, mẫu tại vị trí X là mẫu cần dự đoán. Các vị trí A, B, C là các điểm ảnh lân
cận là cơ sở cho bộ dự đoán dự đoán ra mẫu ở vị trí X. Giả sử giá trị điểm ảnh tại A, B, C
lần lượt là Ra, Rb, Rc là các số nguyên đã biết. Giá trị mẫu dự đoán tại X, Px, theo thuật
toán LOCO-I là:
Mẫu dự đoán Px sau đó được so sánh sai khác với giá trị mẫu thực tế Ix. Giá trị sai khác
(hay sai số dự đoán – Prediction error) sẽ là thông tin được mã hóa.
3.3. Sơ đồ nén ảnh JPEG-LS

Hình 5. Sơ đồ khối thuật toán JPEG-LS
Sơ đồ nén ảnh JPEG-LS về cơ bản giống với sơ đồ nguyên lý nén ảnh không tổn
hao áp dụng DPCM.
Trong hình vẽ, tín hiệu đầu vào là các mẫu (các giá trị điểm ảnh) được so sánh sai
khác với mẫu dự đoán chính nó ở đầu ra của khối dự đoán (khối Predictor ). Khối dự
đoán này thực hiện tính toán mẫu dự đoán theo thuật toán LOCO-I đã nói ở trên.
Sai số dự đoán (Prediction error) là thông tin dùng để mã hóa. Thông tin sai số là
đầu ra của khối Modeler, sau đó nó được đưa đến khối Coder, là khối mã hóa. Tại đây,
thông tin sai khác sẽ được mã hóa thành các từ mã. Khối mã hóa sử dụng thuật toán mã

11


hóa Golomb để mã hóa thông tin sai khác. Sản phẩm cuối cùng của quá trình nén là các
từ mã sắp xếp liên tiếp tạo thành dòng bit.
Tính chất không mất mát thông tin và nén ảnh trong sơ đồ thuật toán JPEG-LS:
•

Không mất mát thông tin: từ thuật toán LOCO-I ở trên, ta nhận thấy giá
trị của mẫu dự đoán là giá trị của một trong các điểm ảnh lân cận (Ra, Rb)

hoặc sự sai khác tính toán giữa giá trị các điểm ảnh (Ra+Rb-Rc). Trong bất
kỳ trường hợp nào thì giá trị nhận được của mẫu dự đoán luôn là số nguyên
(bởi Ra, Rb là số nguyên, hiệu giữa Ra, Rb, Rc cũng là số nguyên). Khi giải
nén khôi phục ảnh thì giá trị điểm ảnh được tính dựa trên sự sai khác cộng
với giá trị nguyên, kết quả cho ra đúng giá trị điểm ảnh mà không sai lệch
so với ban đầu (vì chỉ là sự cộng trừ giữa các số nguyên). Vì vậy sơ đồ này
không có sự mất mát thông tin.

•

Nén ảnh: thông thường giá trị của điểm ảnh sẽ được biểu diễn bằng số
nguyên 8 bit. Nếu mã hóa các điểm ảnh thì sẽ phải dùng tất cả từ mã 8 bit.
Tuy nhiên, sự sai khác của các điểm ảnh là rất nhỏ so với giá trị (thường là
giá trị 1 chữ số trong hệ 10), vì vậy lượng bit dùng để mã hóa chỉ cần dùng
3, 4 bit. Mã hóa sự sai khác cho phép tính toán giá trị điểm ảnh từ sự sai
khác và giá trị điểm ảnh lân cận nên vẫn có thể bảo toàn giá trị điểm ảnh,
hay bảo toàn thông tin. Vậy thay vì mã hóa các điểm ảnh ta chỉ cần mã hóa
sự sai khác, dùng số bit cho từ mã ít hơn. Điều này tạo ra tính chất nén của
sơ đồ.

3.4 Chi tiết thuật toán JPEG-LS
Cho ảnh minh họa 4x4 như hình

3.4.1 Các bước tính toán ở khối Modeler
Tại khối Modeler, thuật toán sẽ thực hiện: tính các giá trị gradients cục bộ; lượng
hóa gradient cục bộ; trộn các gradient đã lượng hóa và lựa chọn mode sẽ thực hiện mã
hóa
a. Tính các gradients cục bộ

12



Giả sử Ix là giá trị của mẫu hiện thời trong ảnh. Tính 3 gradients cục bộ g i như sau: g1 =
Rd – Rb, g2 = Rb – Rc, g3 = Rc – Ra.

Ví dụ :

(g1,g2,g3)=( 0,81,-36)

(g1,g2,g3)=( 0, 0, 0)

b. Lượng hóa gradient cục bộ
Q1, Q2, Q3 là các số miền của các gradients cục bộ đã được lượng hóa, từ (g1,g2,g3) ⇒
(Q1,Q2,Q3)
gi ( i = 1 to 3 )
{0}
±{1,2}
±{3,4,5,6}
±{7,8,...,20}
±{≧21}
Ví dụ:
(g1, g2, g3)=( 0,81,-36) ⇒ (Q1,Q2,Q3)=( 0, 4, -4)
(g1, g2, g3)=( 0, 0, 0) ⇒ (Q1,Q2,Q3)=( 0, 0, 0)
c. Trộn các gradient đã lượng hóa
Nếu giá trị đầu tiên khác không của vector (Q1,Q2,Q3) là số âm, thì (Q1,Q2,Q3)
⇒ (-Q1,-Q2,-Q3) và SIGN gán bằng –1, ngược là là +1.

13



Ví dụ:
(Q1, Q2, Q3)=( 0, 4, -4) ⇒ SIGN = +1
(Q1, Q2, Q3)=( 0, 0, 0) ⇒ SIGN = +1
d. Lựa chọn mode
Từ các gradients cục bộ ta có thể mode sẽ được chọn tiếp theo là Regular mode
hay run mode.
Nếu Q1=Q2=Q3=0, chọn run mode, ngược lại , chọn regular mode.
Ví dụ:
(Q1, Q2, Q3)=( 0, 4, -4) ⇒ Reqular mode
(Q1, Q2, Q3)=( 0, 0, 0) ⇒ Run mode
3.4.2 Chế độ Regular mode
Các công việc được thực hiện ở chế độ Regular mode: Tính giá trị dự đoán cố định
(fixed prediction; Điều chỉnh thích nghi; Tính sai số dự đoán (prediction error); Giảm
modulo của sai số dự đoán; Ánh xạ sai số (Error mapping); Tính tham số k của mã hóa
Golomb; Mã hóa Golomb; Mã hóa sai số đã ánh xạ và Cập nhập các biến
a. Tính giá trị dự đoán cố định (fixed prediction)
Sử dụng thuật toán LOCO-I để tính giá trị sai số cố định. Giả sử Ra, Rb, Rc được
dùng để dự đoán Ix, Px là giá trị dự đoán cho mẫu Ix, ta có:

Ví dụ:

Rc = 64≦min(100,145)≦100 ⇒ Px = max(100,145) = 145
b. Điều chỉnh thích nghi
Để điều chỉnh giá trị dự đoán Px, ta dùng tham số điều chỉnh C, với C = [B/N] (Cách tính
các biến B, N được giới thiệu trong mục i)
Khi đó,

14



Ví dụ:
Với B = -1, N = 2 ⇒ C=[-1/2] = -1
Px = 145, SIGN = +1 ⇒ Px = Px + C = 145 + (-1) = 144
c. Tính sai số dự đoán
Gọi Errval là sai số dự đoán, khi đó: Errval = Ix -Px nếu SIGN = +1 và Errval = Errval, nếu SIGN = -1
Ví dụ:
Ix = 145, Px = 144, SIGN = +1 ⇒ Errval = Ix - Px = 145 ─ 144 = 1
d. Giảm modulo sai số dự đoán
Sai số dự đoán sẽ được làm giảm xuống trong khoảng mã hóa,-127~+128. Từ đó,
để chuyển đổi sai số, ta dùng công thức sau:
1. Errval = Errval + 256, nếu Errval < 0.
2. Errval = Errval ─ 256, nếu Errval ≧ 128.
Ví dụ:
Errval = 1 (1 > 0 và 1 ≦ 128) ⇒ Errval = 1
e. Ánh xạ sai số dự đoán
Sai số dự đoán, Errval, sẽ được ánh xạ tới một giá trị không âm MErrval, với
công thức:

Ví dụ:
Với Errval = 1 (1 ≧ 0) ⇒ MErrval = 2 * 1 = 2
Hay giá trị chuyển đổi chung được thể hiện như bảng dưới:
Sai số dự đoán
0 -1 1 -2 2 -3 3 … 127 -128
↓ ↓ ↓ ↓ ↓↓ ↓ ↓ ↓
0 1 2 3 4 5 6 … 254 255
Giá trị được ánh xạ
f. Tính tham số k của thuật toán mã hóa Golomb
15



k là tham số mã hóa Golomb trong chế độ regular mode, k được tính theo công
thức:
k = min {k’|2k’ * N ≧ A}
với N, A là các biến được giới thiệu trong mục i.
Ví dụ:
Với N = 2, A = 64 ⇒ 2k’ * 2 ≧ 64 ⇒ 2k’ ≧ 32 ⇒ k = 5
g. Mã hóa Golomb
Sai số dự đoán được tách theo công thức: MErrval = q * m + r, với m (m = 2k) (k là
tham số được tính ở mục f) thành hai thành phần unary code (q) và modified binary
code (r).
Ví dụ:
Với MErrval = 13, k = 2 ⇒ m = 22 = 4
⇒ 13 = 3 x 4 + 1 ⇒ q = 3, r = 1
⇒ unary code=3,

modified binary code=1

⇒ unary code=000, modified binary code=01
Từ mã đã mã hóa ⇒ 000101
Bảng mã Golomb với m = 4 (k=2).
n

q

0

0

1


0

2

0

3

0

4

1

5

1

6

1

7

1

Tính chất của mã Golomb:
16



n↓⇒ độ dài từ mã ↓
Mã một chiều
không cần lưu vào bảng mã
Golomb code là tối ưu hóa cho phân bố hình học một mặt của các số nguyên
không âm

-

h. Mã hóa mapped-error (MErrval)
Ví dụ: k = 5 ⇒ m = 2k = 25 = 32
Với MErrval = 2, ⇒ 2 = q * m + r = 0 * 32 + 2 ⇒ q = 0, r = 2
⇒ unary code= 0,

modified binary code=2

⇒ unary code= null, modified binary code=00010
⇒ 100010
i. Cập nhập các biến
Các biến A, B và N được cập nhập tùy vào sai số dự đoán hiện thời, với A, B là
các bộ đếm cho các sai số dự đoán tích lũy và N là bộ đếm cho tần suất xuất hiện của ngữ
cảnh (context)
Ví dụ: Các biến trước khi mã hóa A = 64, B = -1, N = 2. Khi có giá trị sai số dự đoán
Errval = 1, các biến sau khi được cập nhập như sau:
⇒A = A + |Errval| = 64 + 1 = 65
B = B + Errval = -1 + 1 = 0
N=N+1=2+1=3
3.4.3 Chế độ Run (Run mode)
Khi các gradients cục bộ đều bằng không, thuật toán chuyển sang chế độ Run.
Trong chế độ này, đầu tiên thuật toán tính độ dài run và tiếp theo là thực hiện mã hóa loạt
dài này (Run-length coding).

a. Quét loạt dài (Run scanning)
Gọi RUNval là giá trị của mẫu lặp (giống nhau), RUNcnt là biến đếm số mẫu lặp lại
trong run mode.
Tính độ dài Run theo thuật toán:
RUNval = Ra;
while (Ix == RUNval) {
17


RUNcnt = RUNcnt + 1;
}
Ví dụ:

RUNval = Ra = 145.
Ix = 145 = RUNval ⇒ RUNcnt = 2
b. Mã hóa loạt dài (Run-length coding)
RUNcnt là giá trị mô tả cho độ dài Run đã được tính như trên, thuật toán mã hóa
loạt dài đơn giản như sau:
while (RUNcnt >0) {
Thêm 1 vào bit stream;
RUNcnt = RUNcnt ─ 1;
}
Ví dụ:
RUNcnt = 2
⇒ 11
3.5 Kết luận
LOCO-I/JPEG-LS thể hiện hiệu năng vượt trội so với các phương pháp nén khác
có độ phức tạp tương đương(như JPEG-Huffman), và đạt được tỷ lệ nên tương tự hoặc
cao hơn so với các phương pháp nén phức tạp dựa trên mã hóa số học (arithmetic coding,
ví dụ: JPEG-Arithm, CALIC Arithm).


18


TÀI LIỆU THAM KHẢO
[1] Bài giảng Xử lý dữ liệu đa phương tiện. Nguyễn Thị Hoàng Lan. Viện CNTT&TT ĐHBK Hà nội.
[2] “A Survey on Lossless Compression for Medical Images”. M.Ferni Ukrit,
A.Umamageswari, Dr.G.R.Suresh. International Journal of Computer Applications (0975
– 8887)
[3] “The LOCO-I Lossless image Compression Algorithm: Principles and
Standardization into JPEG-LS”. M. J. Weinberger, G. Seroussi, G. Sapiro
[4] From LOCO-I to the JPEG-LS Standard. Marcelo J. Weinberger, Gadiel Seroussi.
HP Laboratories Palo Alto
[5] />
19


20