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

TRẦN DOÃN HIỂN

NGHIÊN CỨU PHƯƠNG PHÁP PHÂN ĐOẠN ẢNH
SỬ DỤNG PHÂN CỤM VÀ ỨNG DỤNG TRONG TRA CỨU
ẢNH DỰA VÀO NỘI DUNG

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

Thái Nguyên, năm 2013

LỜI MỞ ĐẦU


2

Xử lý ảnh là lĩnh vực nghiên cứu đang phát triển không ngừng bởi tính trực quan
sinh động cũng như khả năng áp dụng vào thực tế lớn. Hiện xử lý ảnh đang giành được
nhiều sự quan tâm của các nhà nghiên cứu trong và ngoài nước. Trong xử lý ảnh, tra
cứu ảnh có thể nói là lĩnh vực đòi hỏi sự nghiên cứu tổng hợp: nghiên cứu xử lý ảnh để
rút trích các đặc trưng, áp dụng các tính toán toán học cao cấp để xác định mức độ
tương đồng giữa hai ảnh. Hơn nữa, cùng với sự phát triển của phần mềm và phần
cứng, khối lượng ảnh phát triển không ngừng và ngày càng lớn. Một số lượng lớn các
ảnh đang được sử dụng ở trong thư viện ảnh số và trên web. Vì vậy nhu cầu tìm kiếm
ảnh là một nhu cầu tất yếu. Hiện tại, tra cứu ảnh ứng dụng trong khá nhiều lĩnh vực
như: quản lý biểu trưng(logo), truy tìm tội phạm, ứng dụng trong y khoa, quân sự….
Hệ thống tra cứu ảnh dựa trên nội dung (CBIR-Content-Based Image Retrieval)
là hệ thống truy vấn ảnh dựa trên việc tự động rút trích một số thông tin đặc trưng
trong ảnh như: màu sắc, kết cấu, vị trí, hình dạng. Phương pháp này đã được nhiều

THEO MÀU, giới thiệu chi tiết về thuật toán cũng như phương pháp tra cứu ảnh sử
dụng phân cụm.
CHƯƠNG 3: XÂY DỰNG HỆ THỐNG VÀ KẾT QUẢ ĐẠT ĐƯỢC, xây dựng
phân tích thiết kế hệ thống và giới thiệu một số kết quả đạt được khi xây dựng chương
trình.

LỜI CẢM ƠN
Trong quá trình thực hiện luận văn này, em luôn nhận được sự hướng dẫn, chỉ
bảo tận tình của TS Nguyễn Hữu Quỳnh, Khoa Công nghệ Thông tin thuộc trường Đại
học Điện lực là cán bộ trực tiếp hướng dẫn khoa học cho em. Thầy đã giành nhiều thời
gian trong việc hướng dẫn cách nghiên cứu, đọc tài liệu, cài đặt các thuật toán và giúp
đỡ về xây dựng hệ thống thực nghiệm.
Em xin chân thành cảm ơn 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 đã luôn nhiệt tình giúp đỡ và tạo
điều kiện tốt nhất cho em trong suốt quá trình học tập tại trường.
Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học - trường
Đại học Công nghệ Thông tin và Truyền Thông thuộc Đại học Thái Nguyên đã luôn
động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh nghiệm học tập, công tác
trong suốt khoá học.
Và lời cuối cùng, tôi xin bày tỏ lòng chân thành và biết ơn tới cha mẹ, anh chị,
những người trong gia đình và bạn bè đã luôn ở bên cạnh tôi những lúc khó khăn nhất,
giúp tôi vượt qua khó khăn trong học tập cũng như trong cuộc sống.

Thái Nguyên, ngày 25 tháng 2 năm 2013


4


5


Phân cụm tích luỹ phân cấp

CBC

Color Base Clustering

Phân cụm dựa vào màu

MST

Minimum Spainning Tree

Cây mở rộng tối thiểu

IRM

Integrated Region Matching

Đối sánh vùng tích hợp

CSDL

Cơ Sở Dữ Liệu


6

Chương 1: TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG
1.1 Giới thiệu

nguồn thông tin cũng như truy vấn của người sử dụng và sau đó đối sánh chúng để tìm
ra những tiêu chí có liên quan này.


7

Những 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.
 Phân tích các truy vấn của người dùng và biểu diễn chúng thành các dạng phù

hợp với việc đối sánh với cơ sở dữ liệu nguồn. Nhiệm vụ của bước này giống với
bước trước nhưng chỉ được áp dụng với những ảnh truy vấn.
 Xác định chiến lược để đối sánh tìm kiếm truy vấn với thông tin được lưu trữ

trong cơ sở dữ liệu. Bước này có thể thực hiện trực tuyến và thực hiện rất nhanh.
Công nghệ đánh chỉ số có thể được sử dụng để nhận dạng không gian đặc điểm
để tăng tốc độ xử lý đối sánh.
 Tạo ra sự điều chỉnh cần thiết trong hệ thống (thường là bằng cách đối chiếu các

tham số trong công nghệ đối sánh) dựa trên phản hồi từ người sử dụng hoặc
những hình ảnh được tra cứu.



lưu trữ” (độ đo tương tự), sẽ được mô tả chi tiết hơn trong phần dưới (mục 2.3.3 và
mục 2.4).
1.2 Đặc trưng ảnh
1.2.1 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. 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ắccó 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 phải lựa chọn và xác định kiểu không gian màu và lựa chọn độ đo tương tự.
1.2.1.1 Không gian màu

Không gian màu là sự biểu diễn tập các màu, một số không gian màu được sử dụng
rộng rãi trong đồ họa máy tính. Màu sắc thường được xác định trong không gian màu
3 chiều.
 Không gian màu RGB

Không gian màu RGB là không gian màu được sử dụng nhiều nhất cho đồ hoạ
máy tính. Lưu ý rằng R,G và B là viết tắt của các từ đỏ (Red), xanh lục (Green) và
xanh lơ (Blue). Đây là không gian màu cộng: đỏ, xanh lục và xanh lơ được kết hợp lại
để tạo ra các màu khác. Không gian này không đồng nhất về nhận thức. Không gian
màu RGB có thể được trực quan hoá như một hình khối, như được minh hoạ trong
hình 1.2.


10


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 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


12

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à 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 bằng 0, kênh L biểu diễn
một ảnh cấp xám.
Trong lượng hoá không gian LUV, mỗi trục được lượng hoá với cùng độ chính

được định vị trong cùng hình khối con và các màu tương tự được gán vào cùng hình
khối con. Sử dụng một số màu sẽ giảm khả năng các màu tương tự được gán vào các
bin khác nhau, nhưng cũng tăng khả năng các màu riêng 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.
1.2.2 Kết cấu

Kết cấu là một mô tả vùng trợ giúptốttrong quá trình tra cứu. Kết cấu không có
khả năng tìm ra cácảnh tương tự, nhưng nó có thểđược sử dụng để phân lớp cácảnh kết
cấu từ cácảnh không kết cấu và sau đóđược kết hợp với các thuộc tínhđặc trưng khác
như màuđể làm cho tra cứu hiệu quả hơn. Một trong những biểu diễn phổ biến nhất
của đặc trưng kết cấu là ma trậnđồng khả năng đượcđề xuất bởiHaralick và cộng sự[8].
Ma trận dựa trên hướng và khoảng cách pixel. Các thống kê từ ma trận đồng khả năng
được trích rút và được biểu diễn như thông tin kết cấu. Tamura và cộng sự[6] đã đề
xuất phương pháp trích rút sáu thuộc tính kết cấu đặc trưng coarseness, contrast,
directionality, likeliness, regularity and roughness.
1.2.3 Hình dạng


14

Hình dạng được xem như là một đặc trưng quan trọng trong mô tả các đối tượng
nổi bật trong ảnh và có thể giúp phân biệt giữa hai ảnh.
Bướcđầu tiên là sử dụng một phương pháp phân đoạn thích hợpđể chia ảnh thành
các vùng. Các kỹ thuật phân đoạn có thểđược phân lớp thành ba loại: dựa vào vùng,
dựa vàođường biên và dựa vào pixel.Sau khi ảnhđược phân đoạn và thu đượccác vùng,

Khoảngcách Ơclit:
ĐâylàkhoảngcáchƠclitthôngthườnggiữacácKbin:

đotương


15
k

∑

(h( I ) − h( M )) 2

j −1

k

∑

(h( I ) − h( M )) 2

j −1

Intersection (h(I),h(M)) =

(1-18)

Hoặc
k


+
H
log
m
H m + H 'm
H 'm + H m

(1-20)

2H m
2 H 'm
'
+
H
log
m
H m + H 'm
H 'm + H m

Trongđó:HvàH’là2biểuđồmàuđượcsosánh, Hm là dải thứ m của biểu đồ H.
1.3.2 Độ đo tương đồng hình dạng

Độđovềhìnhdạng rất nhiềutrong phạmvilýthuyếtcủa bộmônxửlýảnh. Chúng trải
rộng từ những độđo toàn cục dạngthôvớisựtrợgiúpcủaviệcnhận dạng đốitượng,cho
tớinhữngđộđochitiếttựđộng tìmkiếmnhữnghìnhdạngđặc biệt.
Lượcđồhìnhdạnglàmộtvídụcủađộđođơngiản.Kỹthuậtdùngđường
biênhiệuquảhơnphươngpháptrước,chúngtìmkiếm nhữnghìnhdạngđốitượng
gầngiốngvớiđường biênnhất.Phươngphápvẽpháchọalàphươngphápcónhiều
đặctrưngrõrànghơn,khôngchỉtìmkiếmnhữngđườngbiênđốitượngđơn,mà
cònđốivớitậpnhữngđốitượngđãđượcphânđoạntrongmộtảnhmàngườidùng


Khoảng cách góc:
cos −1 ( x. y)

cos −1 ( x. y )

d(x,y) =

(1-22)

cos −1 ( x, y )

cos −1 ( x, y )
• Độ đo Euclide:
m

∑x −y
i −1

i

i

2

m

∑ x −y
i −1



•

TruyvấnMulti-pass sử dụng đầu ra của các truy vấn trước làm cơ sở cho bước
tiếp theo. Người sử dụng có thể vẽ ra và chỉ định màu, kết cấu mẫu của hình
ảnh yêu cầu.

Trong hệ thống QBIC,tương tựmàu được tính toán bằng độ đo bình phương sử
dụng biểu đồ màu k phần tử và màu trung bình được sử dụng như là bộ lọc để cải tiến
hiệu quả của truy vấn.
1.4.2

Hệ thống Blobworld

Hệ thống này không áp dụng cách tiếp cận tra cứu ảnh theo ảnh mẫu mà tạo ra
những biến đổi bằng cách trích rútcác dữ liệu điểm nguyên thuỷ có đặc tính giống
nhau về màu sắc và không gian kết cấu để hợp thành một tập hợp nhỏ gọi là vùng
riêng biệt.
Hệ thống này cũng cho người sử dụng thấy được sự trình bày kết cấu bên trong của
ảnh truy vấn và các kết quả truy vấn của nó. Ngoài ra, việc hiển thị ngẫu nhiên của hệ
thống cho người sử dụng biết nguyên nhân tại sao các ảnh không đồng dạng với ảnh
truy vấn lại được trả về như kết quả truy vấn và làm sao để cải tiến điều đó.

1.4.3

Virage
Virage là một máy tìm kiếm ảnh dựa vào nội dung được phát triển tại liên hợp

Virage. Tương tự với QBIC, Virage hỗ trợ các truy vấn trực quan dựa trên màu, thành
phần cấu tạo (bố cục màu), kết cấu và cấu trúc (thông tin đường bao đối tượng).

vùng ảnh và trích rút đặc trưng trực quan lĩnh vực được nén. Các đặc trưng trực quan
được sử dụng trong các hệ thống của họ là các tập màu và các đặc trưng kết cấu dựa
vào biến đổi sóng. Để tăng tốc quá trình tra cứu, họ cũng đã phát triển các thuật toán
đánh chỉ số dựa vào cây nhị phân. VisualSEEk hỗ trợ các truy vấn dựa vào cả các đặc
trưng trực quan và các quan hệ không gian của chúng. Điều này cho phép người sử
dụng chuyển một truy vấn hoàng hôn bằng vùng màu đỏ-cam trên đỉnh và vùng xanh
lơ hoặc xanh lá cây ở dưới bằng phác thảo của nó. WebSEEk là một máy tìm kiếm
hướng Web. Nó gồm ba module chính, tức là module tập hợp ảnh/video, module phân
loại chủ đề và đánh chỉ số, và module tìm kiếm, duyệt, và tra cứu. Nó hỗ trợ các truy
vấn dựa trên cả các từ khoá và nội dung trực quan. Bản demo trực tuyến có tại
/>1.4.6

Photobook
Photobook là một tập các công cụ tương tác để duyệt và tìm kiếm các ảnh được

phát triển tại phòng thí nghiệm MIT Media. Photobook gồm ba quyển nhỏ từ đó các
đặc trưng hình, kết cấu, và bề mặt được trích rút tương ứng. Sau đó những người sử
dụng có thể truy vấn trên cơ sở các đặc trưng tương ứng trong mỗi quyển con. Trong
phiên bản Photobook gần đây nhất của nó, bốn mắt, Picard và cộng sự đã đề xuất gồm
những người sử dụng trong lặp và chú thích tra cứu ảnh. Động cơ cho việc này là dựa
trên quan sát rằng không có đặc trưng nào có thể mô hình các ảnh tốt nhất từ mỗi và


19

mọi lĩnh vực. Hơn nữa, nhận thức của con người là chủ quan. Họ đã đề xuất một cách
tiếp cận “hội các mô hình” để liên kết nhân tố người. Các kết quả thực nghiệm chỉ ra
rằng cách tiếp cận này là hiệu quả trong chú thích ảnh tương tác.
1.5 Đánh giá hiệu năng tra cứu


một hệ thống truy vấn mà thôi.


20

Gần đây MPEG7 có khuyến nghị một cách đánh giá mới về hiệu năng của các hệ
thống tra cứu gọi là ANMRR (average normalized modified retrieval rank) . Theo
cách này độ chính xác và độ triệu hồi được kết hợp thành một số đo duy nhất.
Ký hiệu số lượng ảnh hoàn toàn đúng với truy vấn q là N(q) và số lượng lớn nhất
của các ảnh hoàn toàn đúng với tất cả Q truy vấn tức là max{N(q1), N(q2),...,N(qQ)} là
M. Sau đó đối với mỗi truy vấn q thì mỗi bức ảnh hoàn toàn đúng k được gán một giá
trị xếp hạng rank(k) giá trị này là thứ hạng của nó trong số những ảnh hoàn toàn đúng
nếu ảnh đó nằm trong K kết quả truy vấn đầu tiên (ở đây K = min{4N(q), 2M}) hoặc
có giá trị K+1 nếu ảnh đó không nằm trong K kết quả truy vấn đầu tiên.
Thứ hạng trung bìnhAVR(q) đối với truy vấn q được tính như sau:
N ( q ) rank( q )

AVR ( q ) = ∑k =1

N( q )
(1-27)

Thứ hạng tra cứu sửa đổi MRR(q) được tính là:
MRR(q)=AVR(q)-0.5-0.5*N(q)

(1-28)

MRR(q) nhận giá trị 0 khi tất cả các ảnh hoàn toàn đúng đều nằm trong K kết quả
truy vấn đầu tiên.
Thứ hạng tra cứu sửa đổi và chuẩn hoá NMRR(q) nhận giá trị từ 0 đến 1 được


22

Chương 2 : TRA CỨU ẢNH DỰA VÀO NỘI DUNG SỬ DỤNG PHÂN CỤM
2.1 Giới thiệu về phân cụm
2.1.1 Khái niệm

Phân cụm dữ liệu[2] là một kỹ thuật trong khai phá dữ liệu, nhằm đưa ra các cụm
mà các phần tử trong cụm có độ tương đồng cao và các phần tử khác cụm nhau lại có
độ tương đồng thấp.
Như vậy, phân cụm dữ liệu là kỹ thuật sử dụng quan sát đối tượng, mục đích để tổ
chức một tập các đối tượng cụ thể hoặc trừu tượng vào các nhóm, cụm phân
biệt.Những đối tượng có nội dung tương tự nhau sẽ được xếp vào cùng một cụm và
những đối tượng có nội dung khác nhau được xếp vào các cụm khác nhau.
Sau đây sẽ giới thiệu một số tính chất của dữ liệu và yêu cầu của một thuật toán
phân cụm. Hầu hết các nghiên cứu và phát triển các thuật toán phân cụm dữ liệu nói
chung đều nhằm thỏa mãn các yêu cầu cơ bản sau:
 Có khả năng mở rộng, gia tăng: Thuật toán phân cụm cần có khả năng gia tăng, mở











rộng. Rất nhiều thuật toán phân cụm có thể làm việc tốt với lượng dữ liệu nhỏ, ít


 ...
x
 i1
 ...

 xn1

... x
1f
... ...
... x
if
... ...
... x
nf

... x 
1p 
... ... 
... x 
ip 
... ... 

... x 
np 

 Biểu diễn dữ liệu dưới dạng độ đo khoảng cách giữa các cặp đối tượng. Nếu ta có n

đối tượng, chúng sẽ được biểu diễn bằng một ma trận với n hàng và n cột như sau:



24

đo khoảng cách phổ biến là: Khoảng cách Euclid, khoảng cách Manhattan được định
nghĩa bằng khoảng cách Minkowski:

d (i, j) = q (| x − x |q + | x − x |q +...+ | x − x |q )
i1 j1
i2 j 2
ip
jp
Độ đo khoảng cách



Minkowski :

 Độ đo khoảng cách Manhattan (q = 1)

d (i, j) =| x − x | + | x − x | +...+ | x − x |
i1
j1
i2
j2
ip
jp

 Độ đo khoảng cách Euclid(q = 2)



2.1.2

b+c
a +b +c

Hệ số so trùng Jaccard :

Một số vấn đề trong phân cụm

Xử lý nhiễu: Dữ liệu bị nhiễu là dữ liệu không chính xác hay là dữ liệu
khuyếtthiếu thông tin về một số thuộc tính. Hầu hết các dữ liệu sử dụng để phân cụm


25

đều bị nhiễu do quá trình thu thập thiếu chính xác hay thiếu đầy đủ. Vì vậy cần phải
thực hiện bước tiền xử lý dữ liệu nhằm khắc phục hoặc loại bỏ nhiễu trước khi chuyển
sang giai đoạn phân tích cụm dữ liệu. Một trong các kỹ thuật xử lý nhiễu hiện nay là
thay thế các giá trị các thuộc tính của đối tượng nhiễu bằng các giá trị thuộc tính tương
ứng.
Dò tìm phần tử ngoại lai: Phần tử ngoại lai là một nhóm nhỏ các đối tượng dữ
liệu khá bất thường so với các dữ liệu trong cơ sở dữ liệu. Loại bỏ những dữ liệu này
để tránh ảnh hưởng đến kết quả phân cụm.
Phân cụm hiện nay đang là vấn đề mở và khó: Vì phân cụm đang phải giải quyết
một số vấn đề cơ bản: Xây dựng hàm tính khoảng cách (hay độ tương tự), xây dựng
các tiêu chuẩn phân cụm, xây dựng mô hình cho cấu trúc dữ liệu, xây dựng các thuật
toán phân cụm và xác lập các điều kiện khởi tạo, xây dựng các thủ tục biểu diễn và
đánh giá kết quả phân cụm. Hiện nay chưa có một phương phápphân cụm tổng quát
nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc dữ liệu. Với những dữ