ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

-----------------------------

LÊ TRƯỜNG THÔNG

GIẤU TIN THUẬN NGHỊCH TRÊN ẢNH SỐ SỬ DỤNG
PHƯƠNG PHÁP DỰ ĐOÁN VÀ DỊCH CHUYỂN HISTOGRAM

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2015


i

LỜI CAM ĐOAN
Tôi xin cam đoan.
Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng
dẫn trực tiếp của thầy giáo, PGS.TS Phạm Văn Ất.
Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng tên tác
giả, tên công trình, thời gian, địa điểm công bố.
Mọi sao chép không hợp lệ, vi phạm qui chế đào tạo, hay gian trá tôi
xin chịu hoàn toàn trách nhiệm.
HỌC VIÊN

Lê Trường Thông


ii


iii

MỤC LỤC
Trang bìa phụ
Lời cam đoan
Lời cảm ơn
Mục lục
Danh mục thuật ngữ Anh – Việt
MỞ ĐẦU ..................................................................................................... - 1 CHƯƠNG 1. TỔNG QUAN ........................................................................... - 1 1.1. Giấu tin .................................................................................. - 1 1.1.1. Vài nét về lịch sử giấu tin................................................................................ - 1 1.1.2. Khái niệm giấu tin ........................................................................................... - 2 1.1.3. Phân loại các kỹ thuật giấu tin ........................................................................ - 2 1.1.4. Mô hình kỹ thuật giấu tin ............................................................................... - 3 1.1.5. Ứng dụng của kỹ thuật giấu tin ...................................................................... - 5 -

1.2. Ảnh số.................................................................................... - 6 1.2.1. Khái niệm ảnh Bitmap .................................................................................... - 7 1.2.2. Phân loại ảnh Bitmap...................................................................................... - 7 1.2.3. Định dạng tệp ảnh Bitmap .............................................................................. - 7 1.2.4. Chất lượng ảnh ............................................................................................. - 10 1.2.5. Một số đặc trưng ảnh số .............................................................................. - 11 -

1.3. Môi trường giấu tin ............................................................. - 12 1.3.1. Giấu tin trong ảnh ......................................................................................... - 12 1.3.2. Giấu tin trong audio...................................................................................... - 12 1.3.3. Giấu tin trong video ...................................................................................... - 13 1.3.4. Giấu tin trong văn bản .................................................................................. - 13 -

1.4. Các hướng tiếp cận giấu tin trên ảnh ................................... - 14 1.4.1. Tiếp cận miền không gian ảnh ...................................................................... - 14 1.4.2. Tiếp cận miền tần số ảnh.............................................................................. - 14 -

1.5. Một số lược đồ giấu tin trên ảnh nhị phân .......................... - 15 -


iv

1.5.1. Kỹ thuật giấu tin Wu-Lee .............................................................................. - 15 1.5.2. Kỹ thuật giấu tin CPT..................................................................................... - 20 -

CHƯƠNG 2. PHƯƠNG PHÁP DỊCH CHUYỂN HISTOGRAM VÀ DỰ ĐOÁN ... - 29 2.1. Sơ lược giấu tin thuận nghịch .............................................. - 29 2.1.1. Giấu tin không thuận nghịch và giấu tin thuận nghịch ................................. - 29 2.1.2. Chút lịch sử giấu tin thuận nghịch ................................................................ - 29 2.1.3. Giấu tin và thủy vân ...................................................................................... - 30 2.1.4. Một số hướng tiếp cận giấu tin thuận nghịch .............................................. - 31 -

2.2. Phương pháp histogram ...................................................... - 32 2.2.1. Một số khái niệm .......................................................................................... - 32 2.2.2 Thuật toán giấu tin ........................................................................................ - 33 2.2.3. Lược đồ giấu tin ............................................................................................ - 34 2.2.4 Thuật toán trích tin và khôi phục ảnh gốc ..................................................... - 35 2.2.5. Lược đồ trích tin và khôi phục ảnh gốc ........................................................ - 36 2.2.6. Ví dụ .............................................................................................................. - 37 -

2.3. Phương pháp dự đoán ......................................................... - 39 2.3.1. Dự đoán tuyến tính ...................................................................................... - 39 2.3.2. Thuật toán giấu tin ....................................................................................... - 39 2.3.3. Lược đồ giấu tin ............................................................................................ - 40 2.3.4. Thuật toán trích tin và khôi phục ảnh gốc ................................................... - 41 2.3.5. Lược đồ trích tin và khôi phục ảnh gốc ....................................................... - 42 2.3.6. Ví dụ .............................................................................................................. - 43 -


Miền tần số

Hide / embed

Giấu / nhúng (tin)

Hiding capacity

Khả năng giấu tin

Histogram shifting

Dịch chuyển histogram

Index domain

Miền chỉ số

Medical imange

Ảnh y tế

Neighboring pixcel

Điểm ảnh lân cận

Prediction technique

Kỹ thuật dự đoán


Giá trị dự đoán

Residual histogram

Histogram dự đoán

Extract and recovery proceduce

Thủ tục trích và khôi phục

Experimental result

Kết quả thực nghiệm

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


-1-

MỞ ĐẦU
Một trong những sự kiện trọng đại của những thập niên cuối thế kỷ 20,
đầu thế kỷ 21 là sự ra đời phát triển của mạng Internet. Thông tin đã trở thành
sẵn sàng trực tuyến, mọi người đều có thể kết nối vào Internet để tìm kiếm
thông tin một cách dễ dàng thông qua nhà cung cấp dịch vụ Internet. Người
dùng có thể đọc các thông tin mới nhất, tra cứu các thư viện số, tìm thông tin
lĩnh vực mình quan tâm. Bên cạnh đó các nhà cung cấp sản phẩm cũng sẵn
sàng cung cấp dữ liệu của mình cho người dùng thông qua mạng.
Hiện nay, các thông tin quan trọng thường được lưu trữ và truyền tải
dưới dạng tệp dữ liệu số như: ảnh, âm thanh và video. Tuy nhiên việc phân
phối một cách phổ biến các tài nguyên trên mạng hiện nay với sự trợ giúp của

Qua đây tôi xin cảm ơn thầy giáo, PGS.TS Phạm Văn Ất và các thầy, cô
giáo trong Trường Đại học Công nghệ thông tin và truyền thông – Đại học
Thái Nguyên đã tận tình hướng dẫn tôi trong quá trình học tập cũng như trong
thời gian nghiên cứu hoàn thiện luận văn này.


-1-

CHƯƠNG 1. TỔNG QUAN
1.1. Giấu tin
1.1.1. Vài nét về lịch sử giấu tin
Các kỹ thuật giấu tin đã được đề xuất và sử dụng từ thời xa xưa, và sau
này đã được phát triển ứng dụng cho nhiều lĩnh vực. Từ Steganography bắt
nguồn từ Hi Lạp với ý nghĩa tài liệu được phủ (covered writing). Các câu
chuyện kể về kỹ thuật giấu thông tin được truyền qua nhiều thế hệ. Có lẽ
những ghi chếp sớm nhất về kỹ thuật giấu thông tin thuộc về sử gia Hi Lạp
Herodotus. Khi bạo chúa Herodotus bị vua Darius bắt ở Susa vào thế kỷ thứ
V trước công nguyên, ông ta đã gửi một bài báo bí mật cho con rể của mình là
Aristagoras ở Milesus. Để thực hiện điều này, Histiaeus đã cạo trọc đầu 1 nô
lệ tin cậy và xăm một thông báo trên da đầu người nô lệ ấy. Khi tóc người nô
lệ đủ dài người nô lệ được gửi tới Milesus.
Một câu chuyện khác về thời Hi Lạp cổ đại cũng do Herodotus ghi lại.
Môi trường để ghi văn bản chính là cá viên thuốc được bọc trong sáp ong.
Demeratus, một người Hi Lạp, cần thông báo cho Sparta rằng Xarxes định
xâm chiếm Hi Lạp. Để tránh bị phát hiện, anh ta đã bóc viên thuốc này, sau
đó bọc lại cá viên thuốc này bằng một lớp sáp mới. Những viên thuốc được để
ngỏ và lọt qua mọi sự kiểm soát một cách dễ dàng.
Mực không màu là phương tiện hữu hiệu cho bảo mật thông tin trong
một thời gian dài. Người Roman cổ đã biết sử dụng những chất sẵn có như
nước quả, nước tiểu và sữa để viết các thông báo bí mật giữa những hàng văn

1.1.3. Phân loại các kỹ thuật giấu tin
Có nhiều cách phân loại khác nhau dựa trên những tiêu chí khác nhau. Có
thể chia lĩnh vực giấu tin thành hai hướng chính, đó là thủy vân số và giấu tin
mật.
Giấu tin mật với mục đích bảo toàn và bảo mật thông tin, tập trung vào
các kỹ thuật giấu tin, sao cho người khác khó phát hiện việc có tin được giấu.


-3-

Kỹ thuật giấu tin mật luôn chú trọng đến tính che giấu, với tính che giấu, các
đối thủ khó có thể phát hiện được đối tượng có chứa tin mật bên trong hay
không; hơn nữa, nếu phát hiện có giấu tin thì việc giải mã thông tin mật cũng
khó có thể thực hiện được. Ðồng thời, các kỹ thuật giấu tin mật còn quan tâm
lượng tin có thể được giấu.
Phạm vi ứng dụng của thủy vân đa dạng hơn, tuỳ theo mục đích của hệ
thủy vân mà người ta lại chia thành các hướng nhỏ như: thủy vân dễ vỡ và
thủy vân bền vững. Thủy vân bền vững quan tâm nhiều đến việc nhúng những
mẩu tin đòi hỏi độ bền vững cao của thông tin được giấu trước các biến đổi
thông thường trên dữ liệu môi trường. Thủy vân dễ vỡ yêu cầu thông tin giấu
sẽ bị sai lệch nếu có bất kỳ sự thay đổi nào trên dữ liệu chứa. Như vậy, kỹ
thuật giấu tin có thể được phân loại như trong Hình 1.1.

Hình` 1.1. Phân loại kỹ thuật giấu tin
1.1.4. Mô hình kỹ thuật giấu tin
Giống như các lược đồ mã hóa thông tin, một kỹ thuật giấu tin gồm thuật
toán nhúng tin và thuật toán trích tin. Theo [5], sơ đồ của thuật toán nhúng tin
tổng quát có mô hình như sau:



truyền tải, phân phát dữ liệu có bị xâm phạm, tấn công hay không.
Đối với các hệ thống giấu thông tin mật này rất quan tâm đến tính an
toàn và bảo mật thông tin của dữ liệu cần giấu. Hệ thống giấu tin mật có độ
bảo mật cao nếu có độ phức tạp của các thuật toán thám mã khó có thể thực
hiện được trên máy tính. Tuy nhiên, cũng có các hệ thống chỉ quan tâm đến số
lượng thông tin có thể được che giấu, hay quan tâm đến sự ảnh hưởng của
thông tin mật đến các môi trường chứa dữ liệu.
1.1.5. Ứng dụng của kỹ thuật giấu tin
Giấu tin mật: Thông tin được giấu trong những trường hợp này cần
được bảo mật trước các đối thủ. Việc giải mã để nhận được thông tin cũng


-6-

không cần dữ liệu môi trường gốc. Đối với các thuật toán giấu tin mật chúng
ta không chú trọng đến việc bảo vệ thông tin mật trước sự tấn công của các
đối thủ mà thay vào đó các thuật toán quan tâm đến tính ẩn và tính an toàn đối
với dữ liệu cần giấu. Do đó, các thuật toán giấu tin có độ bảo mật cao sẽ được
sử dụng trong các ứng dụng giấu tin mật.
Bảo vệ bản quyền tác giả: Đây là ứng dụng cơ bản nhất của kỹ thuật
thủy vân số. Một thông tin nào đó mang ý nghĩa bản quyền được sở hữu bởi
tác giả gọi là thủy vân, thông tin này sẽ được nhúng vào trong các sản phẩm
multimedia, và đó là minh chứng cho bản quyền của tác giả nhằm bảo vệ các
sản phầm chống lại các hành vi lấy cắp hoặc làm nhái. Yêu cầu kỹ thuật đối
với ứng dụng này là thủy vân phải tồn tại bền vững cùng với sản phẩm, khi
muốn bỏ thủy vân này mà không được phép của người chủ sở hữu thì chỉ còn
cách là phá huỷ sản phẩm.
Xác thực thông tin: Một tập các thông tin sẽ được giấu trong dữ liệu
nguồn và thông tin sẽ được sử dụng để nhận biết xem dữ liệu nguồn có bị
thay đổi hay không. Với kiểu ứng dụng này các thủy vân nên được ẩn để tránh

Như vậy, ảnh màu có thể xem như 3 ma trận nguyên ứng với 3 thành phần
màu của các điểm ảnh.
Trong lĩnh vực giấu tin, mỗi dạng ảnh có những thuận lợi, khó khăn và
cách tiếp cận riêng. Tuy nhiên, một lược đồ giấu tin trên ảnh nhị phân ta có
thể dễ dàng áp dụng cho ảnh đa cấp xám hoặc ảnh màu thông qua tính chẵn lẻ
của giá trị điểm ảnh. Nhưng từ lược đồ giấu tin trên ảnh màu hoặc ảnh đa cấp
xám khó có thể áp dụng đối với ảnh nhị phân.
1.2.3. Định dạng tệp ảnh Bitmap
Ảnh Bitmap được lưu trữ dưới dạng nhị phân, một tệp định dạng bitmap
được chia thành các phần cơ bản như: phần tiêu đề file (BITMAP


-8-

HEADER), thông tin về ảnh (BITMAP INFOR), bảng màu (PALLETE
Table) và vùng dữ liệu ảnh (DATA). Và thứ tự các phần của tệp ảnh được
lưu trữ tuần tự trong bộ nhớ như trong hình Hình 1.5
BITMAP HEADER
BITMAP INFOR
PALLETE Table
DATA
Hình 1.5. Minh hoạ cấu trúc tệp ảnh bitmap
 Ý nghĩa các phần trong tệp ảnh bitmap
Bitmap Header: mô tả thông tin chung về File định dạng bitmap, độ dài
của phần này được cố định với mọi file ảnh bitmap.
Bảng 1.1. Cấu trúc và nội dung của Bitmap File Header
Byte#

Data


Số TT (tính từ 0) byte
đầu của BMP data

Bitmap Infor: mô tả thông tin về ảnh được lưu trữ, độ dài của phần này
cũng cố định.
Bảng 1.2. Cấu trúc và nội dung của Bitmap Info
Byte #

Data

Giá trị

1–4

Number of bytes in Bitmap Info

40

5–8

Width of bitmap

In pixels


-9-

9 – 12

Height of bitmap


33 – 36

Number of colors In color Palette Ảnh 24 bít – 0

In bytes

Ảnh 8 bít - nếu 0 thì 256
mầu
37 – 40

Number of colors importal

Pallete Table: chính là bảng màu của ảnh bitmap, độ dài của phần này
có thể bằng không (không có bảng màu) đối với ảnh đen trắng và ảnh màu có
số lượng màu lớn hơn 256 màu.
Bảng 1.3. Cấu trúc và nội dung của Color Palette
Byte#

Data

Giá trị

Entry - chỉ số mầu

1

Blue color value

0 – 255


0 – 255

1

6

Green color value

0 – 255

1

7

Red color value

0 – 255

1

8

Reserved

0

1

9



- 11 -

1.2.5. Một số đặc trưng ảnh số
Những đặc trưng của ảnh được trích chọn để sử dụng trong nhiều ứng
dụng như xử lý ảnh, nhận dạng ảnh,… Hầu hết các phương pháp trích chọn
các đặc trưng của ảnh tập trung vào: màu sắc, kết cấu, hình dạng.
a. Đặc trưng về màu sắc
Màu sắc là đặc tính hình ảnh được thể hiện nhiều nhất vì tính đơn giản
của việc trích thông tin màu của ảnh đưa ra phân tích và đã có hiệu quả thông
qua biểu đồ màu. Các biểu đồ màu miêu tả các điểm màu trên những vùng
màu của ảnh.
Không gian màu RGB được sử dụng rộng rãi trong việc miêu tả màu sắc
của ảnh. Nó gồm ba thành phần màu cơ bản là đỏ (Reb), lục (Green), lam
(Blue). Các màu khác được tạo ra bằng cách tổng hợp ba thành phần màu cơ
bản này. Tuy nhiên không gian màu RGB biến đổi không phù hợp với cảm
nhận của mắt con người.
b. Đặc trưng về hình dạng
Hình dạng của đối tượng trong ảnh cũng là một đặc trưng có thể được
xét đến. Đối tượng của ảnh thể hiện nội dung ảnh nhiều nhất. Ảnh được chụp
hoặc tranh được vẽ luôn với mục đích mô tả lại các đối tượng đó. Việc tách
riêng các đối tượng và hình dạng của chúng trong ảnh là rất khó. Khó hơn là
so sánh các đặc trưng đó thế nào.
c. Đặc trưng về kết cấu
Kết cấu bề mặt là phản ánh sự biểu diễn một mẫu về không gian có vài
thuộc tính đồng đều không thể có được từ sự biểu diễn bằng một màu đơn
hoặc một độ sáng trong vùng mà yêu cầu sự tương tác của nhiều màu, độ sáng
khác nhau. Để sử dụng kết cấu trong tìm kiếm ảnh, ta cần có các đặc tính kết
cấu của một đối tượng hoặc một vùng quan tâm đến trong ảnh cung cấp đặc

Giấu tin trong audio mang những đặc điểm riêng khác với giấu thông tin
trong các đối tượng đa phương tiện khác. Một những yêu cầu cơ bản của giấu


- 13 -

tin là đảm bảo tính chất ẩn của thông tin được giấu đồng thời không làm ảnh
hưởng nhiều đến chất lượng của dữ liệu gốc. Để đảm bảo yêu cầu này, kỹ
thuật giấu thông tin trong audio phụ thuộc vào hệ thống thính giác của con
người. Và một vấn đề khó khăn ở đây là hệ thống thính giác của con người
nghe được các tín hiệu của các giải tần rộng và công suất lớn nên đã gây khó
dễ đối với các phương pháp giấu tin trong audio. Nhưng theo một số tài liệu,
công trình nghiên cứu đã công bố, hệ thống thính giác lại gặp những khó khăn
trong việc phát hiện sự thay đổi nhỏ về âm lượng, tần suất của tín hiệu audio.
Điều này có nghĩa là các âm thanh lớn, tần số cao có thể che giấu được các
âm thanh nhỏ, tần số thấp một cách dễ dàng. Và thông tin này sẽ giúp ích cho
việc chọn các audio thích hợp cho việc giấu tin. Vấn đề này khó khăn thứ hai
đối với giấu thông tin trong audio là kênh truyền tin. Kênh truyền hay băng
thông chậm sẽ làm ảnh hưởng đến chất lượng thông tin sau khi giấu.
1.3.3. Giấu tin trong video
Cũng giống như giấu thông tin trong ảnh hay audio, giấu tin trong video
cũng được quan tâm và được phát triển mạnh mẽ cho nhiều ứng dụng như
kiểm soát sao chép thông tin, nhận thực thông tin và bảo vệ bản quyền tác giả.
Với kỹ thuật giấu thông tin trong video, các thuật toán lợi dụng triệt để những
nhược điểm của hệ thống thị giác và thính giác của con người để thực hiện
quá trình giấu tin.
1.3.4. Giấu tin trong văn bản
Trong việc trao đổi thông tin qua hệ thống máy tính, văn bản chiếm một
tỷ lệ rất lớn so với các loại phương tiện chứa khác. Tuy vậy, giấu tin trong
văn bản lại chưa được quan tâm nghiên cứu nhiều. Các nghiên cứu về giấu tin

gián tiếp thông qua các kỹ thuật biến đổi. Các biến đổi này làm nhiệm vụ
chuyển miền biến số độc lập sang các miền khác và như vậy tín hiệu và hệ
thống rời rạc sẽ được biểu diễn trong các miền mới với các biến số mới.
Phương pháp biến đổi này cũng giống như phương pháp biến đổi trong phép


- 15 -

tính tích phân hay phương pháp đổi hệ toạ độ trong giải tích của toán phổ thông
quen thuộc.
Mỗi cách biến đổi sẽ có những thuận lợi riêng, tuỳ từng trường hợp mà
chúng ta chọn phép biến đổi nào cho phù hợp. Sau khi khảo sát, biến đổi xong
các tín hiệu và hệ thống rời rạc trong miền các biến số mới này, nếu cần thiết
có thể dùng cá biến đổi ngược để đưa chúng trở lại miền biến số độc lập.
Phương pháp khảo sát gián tiếp sẽ làm đơn giản rất nhiều các công việc
gặp phải khi dùng phương pháp khảo sát trực tiếp trong miền biến số độc lập
tự nhiên. Hệ thống rời rạc cần khảo sát chính là miền không gian các điểm
ảnh. Có một số phương pháp biến đổi được sử dụng rất phổ biến như: Furier,
Cosine rời rạc (DCT), Wavelet rời rạc (DWT)… Đây là những phép biến đổi
được sử dụng nhiều trong các kỹ thuật xử lý ảnh và âm thanh. Trong giấu tin,
đặc biệt trong kỹ thuật thủy vân tiếp cận theo miền tần số, các phép biến đổi
từ miền biến số tự nhiên của ảnh sang miền tần số như biến đổi Furier, biến
đổi cosin rời rạc, Wavelet được sử dụng phổ biến.
1.5. Một số lược đồ giấu tin trên ảnh nhị phân
1.5.1. Kỹ thuật giấu tin Wu-Lee
* Thuật toán giấu tin Wu-lee
Kỹ thuật giấu tin theo khối bit thể hiện độ an toàn không cao với việc sử
dụng duy nhất kích thước khối là khoá cho quá trình giấu tin, đồng thời ảnh
chứa thông tin giấu cũng dễ bị phát hiện do kỹ thuật có thể sẽ thay đổi giá trị
của một bit trong các khối ảnh toàn màu đen hoặc toàn màu trắng. Điều này

Fmxn là ma trận nhị phân và là ma trận môi trường để giấu tin



Kmxn là ma trận nhị phân khoá và giá trị của ma trận K phải được

giữ bí mật


b là bit nhị phân cần giấu (b = 0 hoặc b = 1)

Output:
Nếu thuật toán thực hiện thành công, kết quả thu được là ma trận G được
biến đổi tối đa một phần tử từ ma trận F và G thoả mãn hai bất biến sau:
+ 0 < SUM(G  K) < SUM(K)

(1.1)

+ SUM(G  K) mod 2 = b

(1.2)

Theo đầu ra của thuật toán, khi nhận được G để kiểm tra ma trận G có
giấu thông tin hay không chúng ta sẽ cần kiểm tra G có thoả mãn bất biến (1.1)
hay không. Với bất biến (1.2) quá trình giải mã thông tin giấu trong ma trận G
có thể dễ dàng xác định được G chứa giá trị bit đã giấu bằng 0 hay bằng 1 theo
(1.3)