`
i

TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN ĐIỆN TỬ - VIỄN THÔNG

ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
Đề tài:
Nghiên cứu kỹ thuật nén ảnh theo phƣơng pháp
phân mảnh (Fractal Image Coding)
Sinh viên thực hiện: ĐẶNG THỊ XUÂN
Lớp: ĐTVT-KSTN-K52
Giảng viên hướng dẫn: PGS.TS.NGUYỄN TIẾN DŨNG
Hà Nội, 6-2012
`
ii

TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN ĐIỆN TỬ - VIỄN THÔNG

ĐỒ ÁN

2. Các số liệu và dữ liệu ban đầu:
…………………………………… …………………………………………… …… ……………………………
……………………………………………………………………………………………………………………………….
… ……………………… …………………………………………………………………………………….
3. Nội dung các phần thuyết minh và tính toán:
……………………………………………………………………………………………………………… ….……………
……………………………………………………………………………………………………………………… ….……
………………………………………………………………………………………………………………………………
… ….……………………………………………………………………………………………
4. Các bản vẽ, đồ thị ( ghi rõ các loại và kích thước bản vẽ ):
……………………………………………………………………………………………………………………… ….……
…………………………………………………………………………………………………………………… ……….…
……………………………………………………………………………………………………….
5. Họ tên giảng viên hướng dẫn: ……………………………………………………… ……………………
6. Ngày giao nhiệm vụ đồ án: ………………………………………………….……………
7. Ngày hoàn thành đồ án: ……………………………………………………………………… ………

Ngày tháng năm
Chủ nhiệm Bộ môn
Giảng viên hướng dẫn Sinh viên đã hoàn thành và nộp đồ án tốt nghiệp ngày tháng năm
Cán bộ phản biện
`
iv


Cán bộ phản biện
( Ký, ghi rõ họ và tên )
Đồ án tốt nghiệp

Đặng Thị Xuân – ĐTVT_KSTN_K52 Trang 1

LỜI NÓI ĐẦU
Cùng với sự phát triển mạnh mẽ của công nghệ thông tin, công nghệ điện tử
cũng như sự gia tăng của nhiều loại hình dịch vụ như Internet, truyền hình kỹ thuật
số… các thiết bị điện tử đều hoạt động và làm việc với tín hiệu số vì việc xử lý tín
hiệu số thực hiện dễ dàng hơn và cho chất lượng cao hơn đối với tín hiệu tương tự.
Môt yêu cầu đăt ra là làm sao việc lưu trữ đạt được hiệu quả cao, tốc độ truyền dẫn
lớn mà vẫn phù hợp với tốc độ kênh truyền? Một trong những giải pháp được đưa ra
là sử dụng kĩ thuật nén – một lượng nhỏ dữ liệu được lưu trữ, truyền thay vì số
lượng lớn ban đầu.
Trong quá trình học tâp tại trường đại học Bách khoa Hà Nội, em đã được
tiếp xúc, được đọc, được học và tham khảo những tài liệu về các kĩ thuật này. Một
công nghệ nén mới và có những ưu điểm trội hơn so với các chuẩn khác là nén ảnh
phân mảnh ( Fractal Image Compression – FIC ). Đây là một kĩ thuật nén tổn hao.
Nhược điểm lớn nhất của kĩ thuật nén này là yêu cầu số lượng lớn các phép tính
toán để thực hiện nên thời gian mã hóa lớn. Nhưng ưu điểm của nó chỉ ra rằng kĩ
thuật nén phân mảnh là tốt và có thể tốt hơn một số kĩ thuật nén khác như chuẩn
JPEG. Các ưu điểm đó là: tỉ lệ nén cao ( có bài báo đã tuyên bố rằng tỉ lệ nén có thể
lên tới 10000 lần ), giải quyết độc lập vì các ảnh có thể được khôi phục lại dễ dàng
và quá trình giải mã đơn giản. Trong vài năm gần đây, nén ảnh phân mảnh đã đạt
được những kết quả đáng kể trong nén ảnh tĩnh cũng như chuỗi ảnh, video. Sự kết
hợp giữa công nghệ nén ảnh Fractal với những phương pháp nén ảnh khác cũng thu
được những kết quả cao.
Xuất phát từ lí do nắm bắt kĩ thuật công nghệ mới, em đã thực hiện đề tài:
„Nghiên cứu kỹ thuật nén ảnh theo phương pháp phân mảnh ( Fractal Image

Sinh viên

Đồ án tốt nghiệp

Đặng Thị Xuân – ĐTVT_KSTN_K52 Trang 4

TÓM TẮT ĐỒ ÁN
Nén ảnh theo phương pháp phân mảnh ( Fractal Image Compression – FIC)
được biết như một kĩ thuật nén tổn hao, yêu cầu một số lượng lớn phép toán trong
quá trình thực hiện mã hóa. Sự phát triển của công nghệ VLSI cho phép tạo ra một
hệ thống hoàn chỉnh bên trong một chip đơn ( single chip – SoC) như FPGA, do đó
số lượng các phép toán cần thiết trong quá trình thực hiện kĩ thuật nén này có thể
được giảm xuống và việc nén dữ liệu trở nên dễ dàng và hiệu quả hơn – rất có ích
trong việc lưu trữ và truyền dữ liệu. Đồ án này đưa ra tổng quan về một số kĩ thuật
nén khác nhau và đặc biệt tập trung vào kĩ thuật nén ảnh phân mảnh FIC thực hiện
cho ảnh nhiều mức xám và ảnh màu. Kết quả thực hiện FIC trên Xilinx Virtex 5
(XUPV5-LX110T) FPGA board, nhằm giảm đáng kể thời gian mã hóa và được so
sánh với kết quả thực hiện trên DSP TMS320C5515 USB Kit với cùng tốc độ clock
100 Mhz cũng được trình bày. Những kết quả thực hiện theo phương pháp của
Fisher cho ảnh xám và mở rộng cho ảnh màu đã chứng mình khả năng có thể thiết
kế một chip đơn SoC cho bộ mã hóa/ giải mã phân mảnh nhanh với hiệu suất nén
tăng.
Cụ thể, nội dung của đồ án bao gồm những phần sau:
 Chƣơng 1: Tổng quan
Giới thiệu tổng quan về công nghệ nén ảnh theo phương pháp phân mảnh,
ứng dụng và các chuẩn nén khác.
 Chƣơng 2: Nén ảnh theo phƣơng pháp phân mảnh
Giới thiệu cơ sở toán học của công nghệ nén ảnh Fractal, quá trình mã hóa và
giải mã cho ảnh nhiều mức xám và ảnh màu.
 Chƣơng 3: Thực hiện nén ảnh phân mảnh cho ảnh xám và ảnh

encoding and decoding process of gray-scale and color image.
 Chapter 3: Implementation of fractal gray-scale and color image
compression on FPGA.
Implements fractal gray-scale and color image compression on FPGA.
 Chapter 4: Experimental results and performance evaluation
Presents and evaluates the experimental results, from which to draw
conclusions and evaluate project implementation process.
The results and future research.
Đồ án tốt nghiệp

Đặng Thị Xuân – ĐTVT_KSTN_K52 Trang 6

MỤC LỤC
LỜI NÓI ĐẦU 1
LỜI CẢM ƠN 3
TÓM TẮT ĐỒ ÁN 4
ABSTRACT 5
MỤC LỤC 6
DANH SÁCH HÌNH VẼ 9
DANH SÁCH BẢNG BIỂU 11
BẢNG CÁC THUẬT NGỮ VIẾT TẮT 12
CHƢƠNG 1. TỔNG QUAN 14
1.1 Giới thiệu chung 14
1.2 Công nghệ nén ảnh phân mảnh 14
1.3 Ứng dụng của công nghệ nén ảnh theo phương pháp phân mảnh 16
1.4 Các chuẩn nén khác 17
1.4.1 JPEG 18
1.4.2 MPEG 24
1.4.3 H261 26
1.4.4 H263 26

3.3 Thực hiện 66
3.3.1 Nén ảnh xám theo phương pháp phân mảnh triển khai trên FPGA 66
3.3.2 Nén ảnh màu theo phương pháp phân mảnh triển khai trên FPGA 69
3.3.3 Kết quả tổng hợp phần cứng trên Virtex 5 (XUPV5-LX110T) FPGA 70
CHƢƠNG 4. KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ 72
4.1 FIC thực hiện trên FPGA 72
4.1.1 Ảnh xám 72
4.1.2 Ảnh màu 73
4.2 Kết quả quá trình kiểm tra FIC trên FPGA 73
4.2.1 Ảnh xám 73
4.2.3 Ảnh màu 79
KẾT LUẬN 81
Đồ án tốt nghiệp

Đặng Thị Xuân – ĐTVT_KSTN_K52 Trang 8

TÀI LIỆU THAM KHẢO 82
Đồ án tốt nghiệp

Đặng Thị Xuân – ĐTVT_KSTN_K52 Trang 9

DANH SÁCH HÌNH VẼ
Hình 1-1 Sơ đồ thuật toán nén JPEG 19
Hình 1-2 Các công đoạn nén ảnh JPEG 19
Hình 1-3 Hàm Cosine 21
Hình 1-4 Quét Zigzag. 23
Hình 2-1 Ảnh xám Lenna 64x64 30
Hình 2-2 Một phân chia cây tứ phân là một đại diện của một ảnh 31
Hình 2-3 Thuật toán mã hóa ảnh xám theo phương pháp phân mảnh 33
Hình 2-4 Thuật toán giải mã ảnh xám theo phương pháp phân mảnh 36

Hình 3-21 Giao diện phần mềm ISE 65
Hình 3-22 Mô hình phần cứng 66
Hình 3-23 Sơ đồ khối lõi của MicroBlaze 67
Hình 3-24 Sơ đồ các bước thực hiện 68
Hình 3-25 Mô đun nén ảnh màu theo phương pháp phân mảnh 69
Hình 4-1 Lenna 64x64 72
Hình 4-2 Ảnh màu Lenna 73
Hình 4-3 Ảnh Lena ban đầu và các ảnh sau khi giải nén với ET = 6, RET = 6, MiS = 4,
MaS = 16, NI = 20 75
Hình 4-4 Ảnh Lena ban đầu và các ảnh sau khi giải nén với ET = 6, RET = 20, MiS = 4,
MaS = 16, NI =20 75
Hình 4-5 DSP TMS320C5515 USB Kit 76
Hình 4-6 Sơ đồ khối của C5515 eZdsp USB Stick [8] 77
Hình 4-7 Ảnh Lena ban đầu 79
Hình 4-8 Ảnh Lena sau khi giải nén bằng chuẩn JPEG 79
Hình 4-9 Ảnh Lena sau khi giải nén bằng phương pháp phân mảnh tương ứng với thứ tự
các ảnh ở hình 4 -8 79 Đồ án tốt nghiệp

Đặng Thị Xuân – ĐTVT_KSTN_K52 Trang 11

DANH SÁCH BẢNG BIỂU
Bảng 2-1 Thông số ảnh Lenna 64x64 30
Bảng 2-2 Các thành phần của ảnh màu Lenna trong không gian màu RGB 40
Bảng 3-1 Bảng tổng hợp phần cứng trên Virtex 5 (XUPV5-LX110T) FPGA thực hiện nén
ảnh xám 71
Bảng 3-2 Bảng tổng hợp phần cứng trên Virtex 5 (XUPV5-LX110T) FPGA thực hiện nén
ảnh màu 71

CPLDs
Complex Programmable Logic Devices
7
ASICs
Application-Specific Integrated Circuit
8
PLDs
Programmable Logic Devices
9
CLB
Configurable Logic Block
10
IOB
Input Output Block
11
LUT
Look Up Table
12
MAC
Multiplier Accumulator
13
DCM
Digital Clock Manager
14
LSB
Least Significant Bit
15
SRL16
Shift register
16

25
ET
Entropy Threshold
26
RET
rms Er ror Tolerance
27
MiS
Minimum Range Size
28
MaS
Maximum Range Size
29
NI
Number of Iteration

Đồ án tốt nghiệp

Đặng Thị Xuân – ĐTVT_KSTN_K52 Trang 14

CHƢƠNG 1. TỔNG QUAN
1.1 Giới thiệu chung
Sự ra đời của lý thuyết hình học fractal là kết quả của nhiều thập kỷ nỗ lực
giải quyết các vấn đề nan giải trong nhiều ngành khoa học chính xác, đặc biệt là vật
lý và toán học. Một cách cụ thể, lý thuyết hình học fractal được xây dựng dựa trên 2
vấn đề lớn được quan tâm ở những thập niên đầu thế kỷ 20. Các vấn đề đó bao gồm:
- Tính hỗn độn của các quá trình phát triển có quy luật trong tự nhiên.
- Sự mở rộng khái niệm số chiều và độ đo trong lý thuyết hình học Euclide cổ
điển.
Mandelbrot và các nhà toán học khác như A.Douady, J.Hubbard đã đặt nền

đầu.
Đây là trường hợp của các phương pháp nén mất thông tin ví dụ chuẩn nén
JPEG. Các nghiên cứu lý thuyết cho thấy, để đạt một tỷ lệ nén hiệu quả (kích thước
dữ liệu nén giảm so với ban đầu ít nhất hàng trăm lần), phương pháp nén mất thông
tin là bắt buộc. Tuy nhiên một vấn đề đặt ra là làm thế nào có được một phương
pháp nén kết hợp cả tính hiệu quả về tỷ lệ nén lẩn chất lượng ảnh so với ảnh ban
đầu? Phương pháp nén ảnh Fractal được phát triển gần đây bởi Iterated System đáp
ứng được yêu cầu này. Như đã biết, với một ánh xạ co trên một không gian metric
đầy đủ, luôn tồn tại 1điểm bất động x sao cho: x=P(x). Micheal F.Barnsley đã mở
rộng kết quả này cho 1 họ các ánh xạ co F.Barnsley đã chứng minh được với một họ
ánh xạ như vậy vẫn tồn tại 1 "điểm" bất động x. Để ý rằng với một ánh xạ co, ta
luôn tìm được điểm bất động của nó bằng cách lấy một giá trị khởi đầu rồi lặp lại
nhiều lần ánh xạ đó trên các kết quả thu được ở mỗi lần lặp. Số lần lặp càng nhiều
thì giá trị tìm được càng xấp xỉ chính xác giá trị của điểm bất động. Dựa vào nhận
xét này, người ta đề nghị xem ảnh cần nén là "điểm bất động" của một họ ánh xạ co.
Khi đó đối với mỗi ảnh chỉ cần lưu thông tin về họ ánh xạ thích hợp, điều này làm
giảm đi rất nhiều dung lượng cần có để lưu trữ thông tin ảnh. Việc tìm ra các ánh xạ
co thích hợp đã được thực hiện tự động hóa nhờ quá trình fractal một ảnh số hóa do
công ty Iterated System đưa ra với sự tối ưu về thời gian thực hiện. Kết quả nén cho
bởi quá trình này rất cao, có thể đạt đến tỷ lệ 10000: 1 hoặc cao hơn. Ngoài phương
pháp nén ảnh Fractal của Barnsley, còn có một phương pháp khác cũng đang được
phát triển. Phương pháp đó do F.H.Preston, A.F.Lehar, R.J.Stevens đưa ra dựa trên
Đồ án tốt nghiệp

Đặng Thị Xuân – ĐTVT_KSTN_K52 Trang 16

tính chất của đường cong Hilbert. Ý tưởng cơ sở của phương pháp là sự biến đổi
thông tin n chiều về thông tin một chiều với sai số cực tiểu. Ảnh cần nén có thể xem
là một đối tượng ba chiều, trong đó hai chiều dùng để thể hiện vị trí điểm ảnh, chiều
thứ ba thể hiện màu sắc của nó. Ảnh sẽ được quét theo thứ tự hình thành nên đường

được đưa ra vào 12-1992. Bộ bách khoa này bao gồm hơn 7 giờ âm thanh,
100 hoạt cảnh, 800 bản đồ màu cùng với 7000 ảnh chụp cây cối, hoa quả,
con người, phong cảnh, động vật,…Tất cả được mã hóa dưới dạng các dữ
liệu fractal và chỉ chiếm xấp xỉ 600 Mb trên 1 đĩa compact.
Iterated Systems Inc. cung cấp một bộ mã hóa shareware( Fractal
Imager), một bộ giải mã chuẩn riêng, một bộ giải mã Netscape plug-in và
một gói phát triển cho người sử dụng Windows.
1.4 Các chuẩn nén khác
Nén dữ liệu được chia thành hai dạng cơ bản: Nén không mất dữ liệu
(Lossless) và nén có mất dữ liệu (Lossy). Đối với dạng nén không mất dữ liệu, ảnh
được khôi phục hoàn toàn giống ảnh gốc, tuy nhiên điều này đòi hỏi phải có thiết bị
lưu trữ và đường truyền lớn hơn. Các thuật toán của nén không mất dữ liệu thường
dựa vào việc thay thế một nhóm các ký tự trùng lặp bởi một nhóm các ký tự đặc biệt
khác ngắn hơn mà không quan tâm tới ý nghĩa của dòng bit dữ liệu. Các ví dụ của
dạng nén không mất dữ liệu là Run-Length Encoding ( RLE ), Huffman Coding,
Arithmetic coding, Shannon-Fano Coding, LZ78, LZH, LZW
Đối với dạng nén có mất dữ liệu, ảnh được khôi phục không giống hoàn toàn
với ảnh gốc, dạng nén này thích hợp cho việc lưu trữ và truyền ảnh tĩnh, video qua
một mạng có băng thông hạn chế. Các dạng nén này thường cho hệ số nén cao hơn,
nó liên quan tới việc dùng các phép biến đổi tín hiệu từ miền này sang miền khác.
Các ví dụ của biến đổi có mất dữ liệu gồm: Differential Encoding, Discrete Cosine
Transform( DCT ), Vector Quantization, JPEG ( Joint Photographic Experts Group
) và MPEG ( Motion Picture Experts Group ).
Đồ án tốt nghiệp

Đặng Thị Xuân – ĐTVT_KSTN_K52 Trang 18

1.4.1 JPEG
1.4.1.1 Giới thiệu
Là viết tắt của Joint Photographic Experts Group. Nó cũng là một tiêu chuẩn

Đầu vào của DCT là một tập hợp các số và đầu ra là một tập hợp có cùng
kích cỡ. IDCT là sự biến đổi đảo ngược, có nghĩa là ta có thể dùng các hệ số đầu ra
để tái tạo các hệ số đầu vào ban đầu. Sự đảo ngược của DCT được gọi là Inverse
Discrete Consine Transform ( IDCT ). DCT thường được ám chỉ tới FORWARD
DCT ( FDCT )
DCT biến đổi tập hợp các giá trị đầu vào thành tập hợp các hệ số của các
hàm cosin với tần số ngày càng tăng. Mỗi giá trị ban đầu được biến đổi thành tổng
của các cosin. Trong quá trình này, DCT có mối liên hệ mật thiết với Fourier
transform.
DCT thường được sử dụng để xử lý các dữ liệu được thiết lập theo một chiều hoặc
hai chiều. Số lượng các giá trị đầu vào thường là 2. Trong JPEG, DCT và IDCT
thường sắp xếp dữ liệu theo hai chiều trong block 8x8.
Trong khi sử dụng DCT ta sẽ có thể nén tốt hơn nếu quan tâm đến sự tương
quan của chiều ngang và chiều dọc của ảnh điểm cùng một lúc. Trong phần trước,
chúng ta đã xem xét cách JPEG tách hình ảnh làm 8 block hình vuông gọi là đơn vị
dữ liệu. Bước đầu tiên của việc nén một đơn vị dữ liệu là sử dụng DCT hai chiều,
trong đó ma trận vuông có kích thước N được xác định như sau:

11
00
(2 1) (2 1)
[ , ] ( , ) [ , ].cos .cos
22
NN
xy
y i x j
T i j c i j V y x
NN



NN
ij
y i x j
V y x c i j T i j
NN







( 1-2 )
Cách tốt hơn để miêu tả DCT hai chiều là sử dụng các ma trận.
Forward DCT là:
T = MVM
T
Inveser DCT là:
V = M
T
TM
Ở đây V là ma trận 8 hàng, 8 cột.
Còn M là ma trận DCT.
Trong JPEG modes được sử dụng các giá trị pixel được biểu diễn bằng 8-bít
bởi vậy chúng có thể chạy từ 0 đến 255. JPEG đòi hỏi mỗi giá trị đầu vào phải trừ
đi 128 để nó có thể chạy từ -128 đến 127 trước khi tiến hành tính DCT.

Hình 1-3 Hàm Cosine
Điều này làm giảm độ lớn của hệ số DCT đầu tiên nhưng không làm thay đổi
độ lớn của các hệ số khác. Sau khi sử dụng IDCT chúng ta phải cộng thêm 128 để