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

Ninh Thị Kim Yến

MỘT SỐ KỸ THUẬT ĐÁNH GIÁ ĐỘ TƯƠNG TỰ
TRONG TRA CỨU TÀU CÁ TRÊN BIỂN

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

Thái Nguyên - 2016
Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn


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

Ninh Thị Kim Yến

MỘT SỐ KỸ THUẬT ĐÁNH GIÁ ĐỘ TƯƠNG TỰ
TRONG TRA CỨU TÀU CÁ TRÊN BIỂN
Chuyên ngành: Khoa học máy tính
Mã số: 60480101

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

NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS ĐỖ NĂNG TOÀN


luận văn này.
Học viên cũng xin gửi lời cảm ơn sâu sắc tới Thủ trưởng các cấp - nơi
học viên đang công tác, đã luôn tạo điều kiện, giúp đỡ để học viên hoàn thành
chương trình học trong thời gian qua. Đồng thời, học viên xin được chân
thành cảm ơn gia đình, các bạn cùng lớp và những người thân thiết đã động
viên, giúp đỡ trong suốt quá trình học tập và thực hiện luận văn./.
Thái Nguyên, ngày 20 tháng 6 năm 2016
Học viên thực hiện

Ninh Thị Kim Yến

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn


i

MỤC LỤC
TRANG BÌA PHỤ
LỜI CAM ĐOAN
LỜI CẢM ƠN
MỤC LỤC...................................................................................................................i
CÁC THUẬT NGỮ, TỪ VIẾT TẮT........................................................................iii
DANH MỤC HÌNH MINH HỌA...............................................................................iv
MỞ ĐẦU ....................................................................................................................... 1
Chương 1. KHÁI QUÁT VỀ TRA CỨU ẢNH VÀ BÀI TOÁN TRA CỨU TÀU CÁ
TRÊN BIỂN .................................................................................................................. 3
1.1. Khái quát về tra cứu ảnh .................................................................................. 3
1.1.1. Giới thiệu ................................................................................................ 3

CÁC THUẬT NGỮ, TỪ VIẾT TẮT

STT Từ, thuật ngữ

Ý nghĩa
Content Base Image Retrieval Tra cứu ảnh dựa vào

1

CBIR

nội dung

2

QBIC

Query By Image Content Truy vấn theo nội dung ảnh

3

4

Commission internationale de l'éclairage - Uỷ ban quốc
CIE

tế về màu sắc
Geographic Information System - Hệ thống thông tin

GIS

Hình 2.10. Hàm xấp xỉ Gaussian rời rạc với   1.4 (cửa sổ W kích cỡ 5x5) ........... 51
Hình 2.11. Cặp mặt lạ tính toán gradient .................................................................... 51
Hình 3.1. Giao diện chương trình thử nghiệm ............................................................ 58
Hình 3.2. Chọn ảnh cần truy vấn................................................................................. 58
Hình 3.3. Biểu đồ Histograms của ảnh ....................................................................... 59
Hình 3.4. Xác định giá trị ngưỡng và ảnh xử lý.......................................................... 59
Hình 3.5. Giao diện hiển thị kết quả cuối cùng........................................................... 60


1

MỞ ĐẦU
1. Lý do chọn đề tài
Nhận dạng và xử lý ảnh là một trong những lĩnh vực có nhiều ứng dụng
trong thực tiễn như: Hệ thống thông tin địa lý, quân sự, y học, vv..... Đối với
lĩnh vực khoa học quân sự, trong những thập kỷ vừa qua, công nghệ xử lý ảnh
đã thực sự trở thành một lĩnh vực mũi nhọn không thể thiếu.
Thời gian gần đây, tình trạng tàu cá nước ngoài có những hành động
xâm phạm chủ quyền vùng biển Việt Nam ngày càng nhiều và phức tạp.
Tàu cá nước ngoài không chỉ khai thác trái phép hải sản, đưa phương
tiện vào thăm dò tài nguyên biển nước ta, mà còn xuất hiện những hành động
mang tính chất đặc biệt nguy hiểm, dễ gây xung đột vũ trang trên biển như uy
hiếp, vô cớ trấn cướp tài sản của ngư dân Việt Nam.

Một số hình ảnh tàu cá Việt Nam bị tàu cá nước ngoài uy hiếp trên biển


2

Trong các lực lượng thực thi pháp luật trên biển của Việt Nam nói riêng

1.1.1. Giới thiệu
Những năm gần đây, vấn đề tra cứu ảnh số nhận được sự quan tâm
ngày càng lớn. Nguyên nhân một phần là do sự phát triển của công nghệ chế
tạo thiết bị thu nhận và lưu trữ ảnh số cũng như sự phát triển mạnh mẽ
của mạng Internet. Người sử dụng trong nhiều lĩnh vực khác nhau có cơ hội
để truy cập và sử dụng các kho lưu trữ ảnh thuộc đủ loại chủ đề và với
nhiều kiểu định dạng ảnh khác nhau. Tuy nhiên người ta cùng nhận thấy
rằng việc tìm được một bức ảnh mong muốn trong bộ sưu tập ảnh đa dạng
có kích thước lớn là rất khó khăn.
Tra cứu ảnh là một quá trình tìm kiếm trong một cơ sở dữ liệu ảnh
những ảnh thoả mãn một yêu cầu nào đó. Ví dụ, người sử dụng có thể tìm
kiếm tất cả các ảnh về chủ đề về “tàu cá” trong một cơ sở dữ liệu ảnh hoặc
một người sử dụng khác lại muốn phân loại cơ sở ảnh của mình thành các bộ
sưu tập có chủ đề khác nhau. Một ví dụ khác về tra cứu ảnh là một người
muốn tìm tất cả các ảnh tương tự với một bức ảnh mẫu nào đó trong một cơ
sở dữ liệu ảnh.
Trước năm 1990, người ta thường sử dụng phương pháp tra cứu ảnh theo
văn bản (Text Based Image Retrieval). Theo cách này người ta sẽ gán cho
mỗi bức ảnh một lời chú thích phù hợp với nội dung hoặc một đặc điểm nào
đó của ảnh, sau đó việc tra cứu ảnh được thực hiện dựa trên những lời chú
thích này. Phương pháp này khá đơn giản. Phương pháp tra cứu ảnh như trên
còn được gọi là tra cứu ảnh theo từ khóa. Tuy nhiên, việc tra cứu chỉ dựa vào
văn bản đi kèm còn có nhiều nhập nhằng giữa nội dung hiển thị ảnh và nội


4

dung văn bản đi kèm ảnh trong quá trình tra cứu. Bên cạnh đó phương pháp
tra cứu ảnh dựa theo văn bản không thể áp dụng để tra cứu các cơ sở dữ liệu
ảnh có số lượng ảnh lớn và kết quả tra cứu thì mang tính chủ quan và cảm


trưng

Hình 1.1. Mô hình hệ thống Tra cứu ảnh theo nội dung

Trong mô hình này, người sử dụng sẽ tạo truy vấn bằng cách chọn một ảnh
mẫu trong một cơ sở dữ liệu ảnh cho trước hoặc phác thảo một hình vẽ mô tả
đối tượng ảnh cần tìm bằng cách sử dụng một giao diện đồ hoạ của hệ thống.
Ảnh mẫu đó được đưa qua khối mô tả nội dung trực quan, trong đó
người ta sử dụng một phương pháp mô tả nội dung trực quan nào đó để
trích chọn một đặc điểm nội dung trực quan để xây dựng thành một véc tơ
đặc trưng.
Véc tơ đặc trưng của ảnh mẫu sẽ được so sánh với véc tơ đặc trưng
tương ứng của các ảnh trong cơ sở dữ liệu ảnh. Kết quả của phép so sánh
là một chỉ số đánh giá độ tương tự giữa ảnh mẫu và ảnh lấy ra để so sánh.
Dựa vào chỉ số độ tương tự tính toán được ở trên, hệ thống sẽ sắp xếp các
ảnh tìm được trong cơ sở dữ liệu ảnh theo một sơ đồ đánh chỉ số nào đó. Danh
sách các ảnh tìm được (đã được sắp xếp) được đưa ra đầu ra của hệ thống.


6

Các chức năng chính của một hệ thống tra cứu ảnh dựa vào nội
dung bao gồm:
 Phân tích nội dung của nguồn thông tin và biểu diễn nội dung của các
nguồn thông tin được phân tích phù hợp với sự đối sánh truy vấn của người
sử dụng (không gian của thông tin nguồn được chuyển đổi thành không gian
đặc điểm với mục đích đối sánh nhanh trong bước tiếp theo). Bước này
thường mất nhiều thời gian cho việc xử lý tuần tự các thông tin nguồn (ảnh)
trong cơ sở dữ liệu. Nó chỉ phải làm một lần và có thể làm độc lập.

năng của các máy tính để thực hiện nhận dạng đối tượng tự động trên các ảnh
chung vẫn là một vấn đề nghiên cứu mở. Do đó hầu hết các nỗ lực nghiên cứu
và thương mại tập trung vào xây dựng các hệ thống thực hiện tốt với các
phương pháp QBE.
1.1.2. Một số phương pháp tra cứu ảnh
1.1.2.1. Tra cứu ảnh theo nội dung
Trích rút đặc trưng là cơ sở của tra cứu ảnh dựa vào nội dung. Theo
nghĩa rộng, các đặc trưng có thể bao gồm cả các đặc trưng dựa vào văn bản và
các đặc trưng trực quan như màu, kết cấu, hình dạng. Trong phạm vi đặc
trưng trực quan, các đặc trưng có thể được phân loại tiếp thành các đặc trưng
chung và các đặc trưng lĩnh vực cụ thể. Các đặc trưng trực quan chung gồm
màu, kết cấu và hình dạng trong khi các đặc trưng lĩnh vực cụ thể là phụ thuộc
ứng dụng, có thể gồm mặt người và vân tay. Các đặc trưng lĩnh vực cụ thể
bao gồm nhiều tri thức lĩnh vực.
Nói chung, không tồn tại một biểu diễn đơn tốt nhất cho một đặc trưng
đã cho. Với mọi đặc trưng được cho tồn tại nhiều biểu diễn mô tả đặc trưng từ
các viễn cảnh khác nhau.
a) Màu sắc
Mắt người rất nhạy cảm với màu sắc và đặc điểm màu là một trong
những thành phần quan trọng giúp con người có thể nhận biết được hình ảnh.


8

Vì vậy, đặc điểm màu sắc là đặc điểm cơ bản của nội dung ảnh. Đặc điểm
màu sắc có thể cung cấp những thông tin rất hữu hiệu cho việc phân loại ảnh
và chúng cũng rất hữu ích cho việc tra cứu ảnh. Cũng vì thế mà tra cứu ảnh
dựa trên màu sắc được sử dụng rộng rãi trong các hệ thống tra cứu ảnh dựa
trên nội dung. Biểu đồ màu thường được sử dụng để thể hiện những đặc điểm
màu của các ảnh. Mặc dù vậy trước khi sử dụng biểu đồ màu chúng ta cần

những đường tham chiếu và điểm gốc màu trong không gian màu RGB. Vùng
giá trị này từ 00 đến 3600. Trong hình nón độ bão hoà là khoảng cách từ tâm
đến cạnh hình nón. Chiều cao của đường cắt chính là giá trị (value) đây chính
là độ sáng hoặc độ chói của màu. Khi độ bão hoà S bằng 0 thì H không xác
định, giá trị nằm trên trục V biểu diễn ảnh xám. Không gian màu HSV dễ
dàng lượng tử hoá. Mức lượng tử hoá thông dụng trong không gian màu này
là 162 mức với H nhận 18 mức, S và V nhận 3 mức.
Không gian màu YUV và YIQ
Các không gian màu YUV và YIQ được phát triển cho truyền hình vô
tuyến. Không gian màu YIQ là giống như không gian màu YUV, ở đây mặt


10

phẳng I-Q là một mặt phẳng quay 330 của mặt phẳng U-V. Tín hiệu Y biểu
diễn độ chói của một pixel và là kênh duy nhất được sử dụng trong ti vi đen
trắng. U và V cho YUV và I và Q cho YIQ là các thành phần màu.
Kênh Y được định nghĩa bởi các giá trị năng lượng có trọng số của
R(0.299), G(0.587) và B(0.144). Các không gian màu YUV và YIQ không
là đồng nhất nhận thức. Khi các không gian màu YUV và UIQ được lượng
hoá, mỗi trục được lượng hoá với cùng độ chính xác.
Không gian màu CIE XYZ và CIE LUV
Không gian màu đầu tiên được phát triển bởi CIE là không gian màu
XYZ. Thành phần Y là thành phần độ chói được xác định bởi các tổng có
trọng số của R(0:212671), G(0:715160) và B(0:072169). X và Y là các thành
phần màu. Không gian màu XYZ là không đồng nhất nhận thức. Trong lượng
hoá không gian màu XYZ, mỗi trục được lượng hoá với cùng độ chính xác.
Không gian màu CIE LUV là một biến đổi xạ ảnh của không gian màu
XYZ là đồng nhất nhận thức. Kênh L của không gian màu LUV là độ chói
của màu. Các kênh U và V là các thành phần màu. Vậy, khi U và V được đặt

biệt được gán vào cùng các bin, nội dung thông tin của các ảnh sẽ giảm. Mặt
khác, các lược đồ màu với một số lượng lớn các bin sẽ chứa nhiều thông tin về
nội dung của ảnh, theo đó giảm khả năng các màu riêng biệt sẽ được gán vào
cùng các bin. Tuy nhiên, chúng tăng khả năng các màu tương tự sẽ được gán
vào các bin khác nhau và tăng không gian lưu trữ biểu diễn ảnh và thời gian
tính toán khoảng cách giữa các lược đồ màu. Do đó, cần có sự thỏa hiệp trong
việc xác định số lượng các bin sẽ được sử dụng trong các lược đồ màu.
b) Kết cấu
Kết cấu là một đặc tính quan trọng khác của ảnh. Các biểu diễn kết cấu
đa dạng đã được nghiên cứu trong nhận dạng mẫu và thị giác máy tính. Về cơ
bản, các phương pháp biểu diễn kết cấu có thể được phân ra thành hai loại:
cấu trúc và thống kê.
Các phương pháp cấu trúc, gồm toán tử hình thái và đồ thị kề, mô tả kết
cấu bởi nhận dạng cấu trúc gốc và các luật sắp đặt của chúng. Chúng có chiều
hướng hiệu quả nhất khi được áp dụng với các kết cấu đều.
Các phương pháp thống kê, gồm các kỹ thuật phổ năng lượng Fourier,


12

các ma trận đồng khả năng, phân tích thành phần chính bất biến - trượt, đặc
trưng Tamura, phân rã Wold, trường ngẫu nhiên Markov (Markov random
field), mô hình fractal và lọc đa phân giải như biến đổi Gabor và sóng, mô tả
kết cấu bằng phân bố thống kê của cường độ ảnh.
Trích xuất nội dung ảnh theo kết cấu nhằm tìm ra mô hình trực quan của
ảnh và cách thức chúng được xác định trong không gian. Kết cấu được biểu
diễn bởi các texel mà sau đó được đặt vào một số các tập phụ thuộc vào số kết
cấu được phát hiện trong ảnh. Các tập này không chỉ xác định các kết cấu mà
còn chỉ rõ vị trí các kết cấu trong ảnh. Việc xác định các kết cấu đặc biệt trong
ảnh đạt được chủ yếu bằng cách mô hình các kết cấu như những biến thể cấp

sử dụng cho các mô tả hình. Các mô tả vùng khác gồm màu và kết cấu. Một
số đặc tính của vùng như trọng tâm, không cụ thể đối với đường biên hoặc nội
dung của vùng.
d) Thông tin không gian
Các vùng hoặc đối tượng với các đặc tính màu và kết cấu tương tự có thể
được phân biệt dễ dàng bằng việc tận dụng các ràng buộc không gian. Thí dụ,
các vùng bầu trời màu xanh và biển xanh có thể có các lược đồ màu tương tự,
nhưng các vị trí không gian của chúng trong các ảnh là khác nhau. Do đó, vị
trí không gian của các vùng (hoặc các đối tượng) hoặc quan hệ không gian
giữa nhiều vùng (hoặc đối tượng) trong một ảnh thì rất hữu ích cho tìm kiếm
các ảnh.
Thu thông tin không gian của các đối tượng trong một ảnh là một quá
trình quan trọng đối với các hệ thống GIS. Quá trình này bao gồm việc biểu
diễn vị trí không gian tuyệt đối và cũng bao gồm vị trí không gian tương đối


14

của các đối tượng. Các thao tác như giao và chồng được sử dụng. Bố cục màu
kết hợp thông tin không gian với thông tin màu xuất hiện trong ảnh và tạo ra
một đặc trưng rất quan trọng trong quá trình tra cứu, gọi là đặc trưng màu –
không gian.
Biểu diễn quan hệ không gian được sử dụng rộng rãi nhất là các xâu 2D
được đề xuất bởi Chang và cộng sự. Nó được xây dựng bởi việc chiếu các ảnh
dọc theo các hướng x và y. Hai tập ký hiệu V và A được định nghĩa trên hình
chiếu. Mỗi ký hiệu trong V biểu diễn một đối tượng trong ảnh. Mỗi ký hiệu A
biểu diễn một loại quan hệ không gian giữa các đối tượng. Do sự biến đổi của
nó, xâu 2DG cắt tất cả các đối tượng dọc theo hình hộp tối thiểu của nó và mở
rộng các quan hệ không gian thành lập hai toán tử không gian. Một tập định
nghĩa các quan hệ không gian cục bộ. Tập còn lại định nghĩa quan hệ không

tiếp cận của họ với các loại ảnh khác nhau, gồm các ảnh thiên văn và các ảnh
hồng ngoại. Trong khi cách tiếp cận này là hiệu quả trong xử lý các loại ảnh
khoa học ở trên, hiệu năng của nó cần được tiếp tục đánh giá cho các ảnh tự
nhiên phức tạp hơn. Li và cộng sự đã đề xuất một cách tiếp cận phân đoạn dựa
vào entropy mờ. Cách tiếp cận này dựa trên thực tế rằng entropy cực đại địa
phương tương ứng với sự không rõ ràng giữa các vùng khác nhau trong ảnh.
Cách tiếp cận này rất hiệu quả cho các ảnh có lược đồ không có các đỉnh và
các rãnh rõ ràng. Các kỹ thuật phân đoạn khác dựa trên phép đạc tam giác
Delaunay (Delaunay triangulation), fractals và luồng biên (edge flow).
Tất cả các thuật toán được đề cập ở trên là tự động. Một ưu điểm chính
của các thuật toán phân đoạn loại này là nó trích rút các đường bao từ một số
lượng lớn các ảnh mà không chiếm thời gian và nỗ lực của con người. Tuy
nhiên, trong một lĩnh vực tự nhiên, với các ảnh không có điều kiện tiên quyết,
phân đoạn tự động không luôn luôn tin cậy. Một thuật toán có thể phân đoạn
trong trường hợp này chỉ là các vùng, mà không là các đối tượng. Để thu được
các đối tượng mức cao, nó cần có sự trợ giúp của con người.


16

Samadani và Han đã đề xuất một cách tiếp cận trích rút đường bao được
trợ giúp bởi máy tính, nó kết hợp các đầu vào thủ công từ người sử dụng với
các biên ảnh được sinh ra bởi máy tính. Trong, Daneel và cộng sự đã phát
triển một phương pháp cải tiến của các chu tuyến thiết thực. Dựa trên đầu vào
của người sử dụng, đầu tiên thuật toán sử dụng một thủ tục tham lam để cung
cấp sự hội tụ ban đầu nhanh. Thứ hai, nét ngoài được lọc bằng việc sử dụng
quy hoạch động. Trong, Rui và cộng sự đã đề xuất một thuật toán dựa vào
phân cụm và nhóm trong không gian - màu - kết cấu. Người sử dụng định
nghĩa đối tượng quan tâm là ở đâu, và thuật toán nhóm các vùng thành các đối
tượng có ý nghĩa.

phụ có cùng chiều dài thì 4 khả năng xoay phải được xem xét. So khớp hình
chiếu được sử dụng thành công trong tìm kiếm ảnh logo. Những khả năng
khác để xây dựng lược đồ thông qua góc tiếp tuyến tại mỗi điểm ảnh trên
đường bao của hình dạng. Độ đo này thì hoàn toàn tự động về mặt kích thước
và bất biến đối với sự dịch chuyển, nhưng nó cũng không bất biến đối với
xoay đối tượng, bởi vì góc tiếp tuyến được tính từ hình dạng đối với một
hướng xác định. Có một số cách khác nhau để giải quyết vấn đề này. Cách thứ
nhất là xoay hình dạng về trục chính như đã mô tả ở trên. Một cách khác đơn
giản hơn là xoay lược đồ hình dạng. Nếu lược đồ có K bin, thì sẽ có K khả
năng xoay. Những vị trí xoay không đúng có thể làm ảnh hưởng tốc độ của
việc tính toán, đặc biệt là trong trường hợp lược đồ và ảnh có kích thước lớn.
Hoặc là lược đồ có thể được tiêu chuẩn hoá bởi cách chọn bin với số đếm lớn
nhất là bin đầu tiên. Một vài bin lớn nhất nên được thử vì có thể có sự tồn tại
của nhiễu.
b) Độ so khớp đường biên của hình dạng
Thuật toán so khớp đường biên đòi hỏi sự trích rút và trình bày đường
biên của cả ảnh cần truy vấn và ảnh mang ra so khớp. Đường biên có thể
được trình bày bởi một dãy những điểm ảnh hay có thể được xấp xỉ bởi một