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

2

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

LỜI MỞ ĐẦU
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 để

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

vào một ảnh mẫu và tìm kiếm những ảnh tƣơng tự với ảnh mẫu trong một tập hợp các
ảnh cho trƣớc.
Nội dung khoá luận gồm có 3 chƣơng:
CHƢƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG, giới
thiệuphƣơng pháp tra cứu ảnh dựa vào nội dung và một số hệ thống tra cứu ảnh tiêu
biểu.
CHƢƠNG 2: TRA CỨU ẢNH DỰA VÀO NỘI DUNG SỬ DỤNG PHÂN CỤM
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.

Chƣơng 2 : TRA CỨU ẢNH DỰA VÀO NỘI DUNG SỬ DỤNG PHÂN CỤM THEO
MÀU 15
2.1 Giới thiệu về phân cụm 15
2.1.1 Khái niệm 15
2.1.2 Một số vấn đề trong phân cụm 17
2.1.3 Phân cụm phân cấp 18
2.2 Một số kỹ thuật tra cứu dựa vào đặc trƣng màu 21
2.2.1 Kỹ thuật tra cứu dựa vào lƣợc đồ màu toàn bộ - GCH 21
2.2.2 Kỹ thuật tra cứu dựa vào lƣợc đồ màu cục bộ - LCH 22
2.2.3 Vector gắn kết màu 22
2.3 Kỹ thuật phân đoạn ảnhsử dụng phân cụm theo màu 23
2.3.1 Khoảng cách Euclid 23
2.3.2 Kỹ thuật phân cụm ảnh 23
2.3.3 Biểu diễn và trích rút đặc trƣng 26
2.4 Độ đo tƣơng tự 27
2

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

2.5 Kết luận chƣơng 2 29
Chƣơng 3: XÂY DỰNG HỆ THỐNG VÀ KẾT QUẢ ĐẠT ĐƢỢC 30
3.1 Giới thiệu bài toán tra cứu ảnh dựa vào nội dung 30
3.2 Phân tích bài toán 30
3.3 Thiết kế hệ thống 30
3.3.1 Thiết kế hệ thống 30
3.3.2 Thiết kế cơ sở dữ liệu 36
3.4 Mô tả chƣơng trình 37
3.5 Kết quả đạt đƣợc 38
3.6 Kết quả đạt đƣợc 46
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 48

Hình 3.15: Kết quả truy vấn lần thứ nhất. 42
Hình 3.16: Ảnh mẫu truy vấn thứ hai. 43
Hình 3.17: Kết quả truy vấn lần thứ hai. 43
Hình 3.18: Ảnh mẫu truy vấn thứ ba. 44
Hình 3.19: Kết quả truy vấn lần thứ ba. 44
Hình 3.20: Ảnh mẫu truy vấn thứ ba. 45
Hình 3.21: Kết quả truy vấn lần thứ 4. 45
KÍ HIỆU CÁC CỤM TỪ VIẾT TẮT
CBIR
Content Base Image Retrieval
Tra cứu ảnh dựa vào nội dung
QBIC
Query By Image Content
Truy vấn theo nội dung ảnh
CIE
Commission internationale de
l'éclairage
Uỷ ban quốc tế về màu sắc
HAC
Hierarchical Agglomerative Clustering
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

dung trực quan. Các hệ thống truy vấn ảnh dựa vào nội dung hiện nay rất đa dạng
nhƣng nhìn chung đƣợc phân biệt bởi: các đặc trƣng mà hệ thống rút trích từ ảnh để
làm cơ sở truy vấn, phƣơng pháp trích rút đặc trƣng ảnh đƣợc sử dụng trong hệ thống
truy vấn, độ đo sự tƣơng tự giữa hai ảnh, phƣơng pháp đánh chỉ số nhiều chiều để tối
ƣu việc tìm kiếm.
Một hệ thống tra cứu ảnh dựa trên nội dung tiêu biểu không chỉ liên quan tới các
nguồn thông tin trong những dạng khác nhau (ví dụ nhƣ văn bản, ảnh và video) mà
còn liên quan đến nhu cầu của ngƣời sử dụng. Về cơ bản nó phân tích cả nội dung của
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.
2

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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.

Chúng ta nhận thấy rằng trên một mặt của một hệ thống tra cứu ảnh dựa vào nội
dung, có các nguồn thông tin trực quan ở các khuôn dạng khác nhau và trên mặt kia có
các truy vấn ngƣời sử dụng. Hai mặt này đƣợc liên kết thông qua một chuỗi các tác vụ
nhƣ đƣợc minh họa trong Hình 1.1. Hai tác vụ phân tích truy vấn ngƣời sử dụng và
đánh chỉ số nhiều chiều đƣợc tóm lƣợc ở đây trong khi hai tác vụ quan trọng nhất:
“Phân tích các nội dung của thông tin nguồn” (trích rút đặc trƣng) và “Định nghĩa một
chiến lƣợc để đối sánh các truy vấn tìm kiếm với thông tin trong cơ sở dữ liệu đƣợc
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.
Hình 1.3: Mô tả không gian màu HSV.
Sắc độ là thành phần của không gian màu HSx. Sắc độ là góc giữa 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ừ 0
0
đến
360
0
. Theo uỷ ban quốc tế về màu sắc CIE (Commission International d'E clairage) thì
sắc độ là thuộc tính của cảm giác có liên quan đến thị giác, qua đó một vùng xuất hiện
tƣơng tự với một màu đƣợc cảm nhận nhƣ red, green, blue hoặc là sự kết hợp của hai
trong số những màu đƣợc cảm nhận. Cũng theo CIE độ bão hoà là màu đƣợc đánh giá
theo tỷ lệ độ sáng của nó. 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 phẳng I-Q là một
mặt phẳng quay
0
33
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.
6


bởi véc tơ:
H={H[0], H[1], H[2], , H[i], H[N]},
Ở đây i biểu diễn một màu trong lƣợc đồ màu và tƣơng ứng với một khối con
trong không gian màu RGB, H[i] là số các pixel có màu i trong ảnh và N là số các bin
trong lƣợc đồ màu.
Mỗi pixel trong ảnh sẽ thuộc về một bin của lƣợc đồ màu của ảnh, vì thế với lƣợc
đồ màu của một ảnh, giá trị của mỗi bin là số các pixel cùng màu. Để so sánh các ảnh
7

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

có các kích cỡ khác nhau, các lƣợc đồ màu đƣợc chuẩn hóa. Lƣợc đồ màu chuẩn hóa
H’ đƣợc xác định bằng:
H’={H’[0], H’[1], H’[2], , H’[i], H’[N]},
Ở đây
p
iH
iH
][
][' 
, P là tổng số các pixel trong ảnh.
Trong lƣợc đồ lƣợng hóa không gian màu lý tƣởng, các màu riêng biệt không
đƣợ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

Fourier[9]. Các hệ số Fourier trội đƣợc sử dụng nhƣ các mô tả hình. Các mô tả khác
trong loại này là các mô men hình [5].
Nếu một vùng có một hình phức hợp, nó có thể đƣợc phân tách tiếp thành các hình
đơn giản hơn nhƣ các hình chữ nhật hoặc các hình tròn và một số thuộc tính của các
hình đơn giản này và các quan hệ của chúng có thể đƣợc 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.
1.3 Độ tƣơng tự giữa các ảnh
1.3.1 Độ đo về màu sắc
Mộtsốđộđotƣơngđồngđƣợcsửdụngnhƣ:ĐộđokhoảngcáchƠclit,độđo Jensen-
Shannondivergence(JSD).
Gọih(I)vàh(M)tƣơngứnglà2lƣợc đồmàucủahaiảnhIvàảnhM.Khiđó
cácloạiđộđomàuđƣợcđịnhnghĩalàmộtsốnguyên(hoặcsốthực)theocácloạiđộ đotƣơng
ứng nhƣsau:
Khoảngcách Ơclit:
ĐâylàkhoảngcáchƠclitthôngthƣờnggiữacácKbin:

Intersection (h(I),h(M)) =
2
1
( ( ) ( ))
k
j
h I h M



2
1
( ( ) ( ))

'
''
1
22
log log
M
mm
mm
m
m m m m
HH
HH
H H H H




(1-20)
Trongđó:HvàH’là2biểuđồmàuđƣợcsosánh, H
m
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


(1-22)
 Độ đo Euclide:
d(x,y) =
2
1
m
ii
i
xy



2
1
m
ii
i
xy



(1-23)
1.4 Các hệ thống tra cứu ảnh dựa vào nội dung
1.4.1 Hệ thống QBIC (Query By Image Content)
Hệ thống QBIC[5] là hệ thống tra cứu ảnh dựa trên sự phác thảo cho phép ngƣời
sử dụng xây dựng một phác thảo, vẽ ra và lựa chọn màu sắc cùng các mẫu kết cấu. Các
đặc trƣng màu sử dụng trong QBIC là giá trị màu trung bình của không gian RGB.
QBIC là một trong các hệ thống dùng cấu trúcđánh chỉ số nhiều chiều dựa trên cấu
trúc R*-Tree[3] và là hệ thống đầu tiên có cách tiếp cận tra cứu ảnh dựa trên nội dung

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).
Nhƣng Virage tiến một bƣớc xa hơn QBIC. Nó cũng hỗ trợ các kết hợp tuỳ ý của bốn
truy vấn trên. Ngƣời sử dụng có thể điều chỉnh các trọng số đƣợc kết hợp với các đặc
trƣng theo sự nhấn mạnh riêng của họ. Jeffrey và cộng sự đã đề xuất tiếp một khuôn
khổ mở cho quản lý ảnh. Họ đã phân loại các đặc trƣng trực quan thành tổng quát (nhƣ
màu, hình, hoặc kết cấu) và lĩnh vực cụ thể (nhận dạng mặt ngƣời, phát hiện khối u,
v.v ). Nhiều đặc trƣng gốc hữu ích có thể đƣợc thêm vào cấu trúc mở, phụ thuộc vào
các yêu cầu lĩnh vực. Để đi ra ngoài giới hạn chế độ truy vấn bởi ví dụ, Gupta và Jain
đã đề xuất một khung công việc ngôn ngữ truy vấn chín thành phần. Hệ thống sẵn có
nhƣ một thành phần có thể thêm vào các hệ quản trị cơ sở dữ liệu nhƣ Oracle hoặc
Informix.
1.4.4 RetrievalWare
RetrievalWare là một máy tra cứu ảnh dựa vào nội dung đƣợc phát triển bởi tập
đoàn công nghệ Excalibur. Từ một trong các công bố đầu tiên của họ, chúng ta có thể
thấy rằng tầm quan trọng của nó là ứng dụng của các mạng neural để tra cứu ảnh. Máy
tìm kiếm gần đây của họ sử dụng màu, hình, kết cấu, độ sáng, bố cục màu, và hƣớng tỷ
lệ của ảnh, nhƣ các đặc trƣng truy vấn. Nó cũng hỗ trợ các kết hợp của các đặc trƣng
này và cho phép ngƣời sử dụng điều chỉnh các trọng số kết hợp với mỗi đặc trƣng.
Trang demo của nó tại
1.4.5 VisualSeek và WebSeek
VisualSEEk là một máy tìm kiếm đặc trƣng trực quan và WebSEEk là một máy
tìm kiếm văn bản/ảnh trên web, cả hai sản phẩm đã đƣợc phát triển tại đại học
12

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

Columbia. Các đặc trƣng nghiên cứu chính là truy vấn quan hệ không gian của các
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

thực sự thích hợp với truy vấn.
)q(Q
)q(R)q(Q
precision


(1-25)
Độ triệu hồi là tỉ lệ những kết quả thích hợp do truy vấn trả lại:
)q(R
)q(R)q(Q
recall


(1-26)
Thông thƣờng phải có sự thoả hiệp giữa hai số đo này bởi vì nếu muốn tăng
cƣờng số đo này thì lại phải chịu giảm số đo kia và ngƣợc lại. Trong các hệ thống tra
cứu điển hình thì độ triệu hồi có xu hƣớng tăng lên khi số lƣợng các kết quả thu đƣợc
tăng lên trong khi đó thì độ chính xác dƣờng nhƣ lại bị giảm đi.
Ngoài ra, việc lựa chọn R(q) lại rất không ổn định do sự đa đạng của cách hiểu về
một bức ảnh. Hơn nữa, khi số lƣợng ảnh thích hợp lại lớn hơn số lƣợng ảnh hệ thống
tìm đƣợc thì lúc đó khái niệm độ triệu hồi trở thành vô nghĩa.
Do đó, độ chính xác và độ triệu hồi chỉ là các mô tả ở dạng thô về hiệu năng của
một hệ thống truy vấn mà thôi.
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(q
1
), N(q

)q(NMRR


(1-29)
Thứ hạng tra cứu sửa đổi và chuẩn hoá trung bình ANMRR xét trên tất cả các
truy vấn Q là:



Q
1q
)q(NMRR
Q
1
ANMRR

1.6 Kết luận chƣơng 1
Trong chƣơng này, tôi đã giới thiệu một số khái niệm cơ bản về tra cứu ảnh dựa
vào nội dung, bao gồm: tra cứu ảnh, trình bày một số ứng dụng củahệ thống CBIR, các
chức năng tiêu biểu của hệ thống tra cứu ảnh dựa vào nội dung, một số nghiên cứu liên
quan về màu và thông tin không gian, đặc trƣng hình và kết cấu. Đặc biệt tôi nhấn
mạnh vào các đặc trƣng màu vàthông tin không gian. 15

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

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

 Dễ hiểu, dễ cài đặt và khả thi: một thuật toán càng dễ hiểu và dễ cài đặt và
mang tính khả thi cao sẽ đƣợc ngƣời dùng tin cậy và sử dụng rộng rãi.
16

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

Các kiểu biến dữ liệu
 Biểu diễn dƣới dạng ma trận của các biến cấu trúc hay các thuộc tính của đối
tƣợng. Ví dụ đối tƣợng ngƣời sẽ có các thuộc tính là tên, tuổi, chiều cao, cân nặng,
màu mắt, … Nếu ta có n đối tƣợng, mỗi đối tƣợng có p thuộc tính thì sẽ có một ma
trận với n dòng, p cột.
 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: Trong đó d(i, j) là khoảng cách giữa đối tƣợng i và j; thể hiện sự khác biệt giữa
đối tƣợng i và j; đƣợc tính tuỳ thuộc vào kiểu của các biến/thuộc tính và thỏa mãn các
tính chất:
d(i,j) 0
d(i,i) = 0
d(i,j) = d(j,i)

x
n1
x

ip
x
if
x
i1
x

1p
x
1f
x
11
x














Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  Độ đo khoảng cách Manhattan (q = 1)  Độ đo khoảng cách Euclid(q = 2)
Phép đo khoảng cách cho dữ liệu thuộc tính nhị phân
Xác định một bảng tham số

Đối tƣợng i 1
0
Đối tƣợng j
1
a
b
0
c
d

Trong đó:
a: Tổng số thuộc tính có giá trị là 1 trong cả i và j
b: Tổng số các thuộc tính có giá trị là 1 trong i và có giá trị là 0 trong j.
c: Tổng số các thuộc tính có giá trị là 0 trong i và có giá trị là 1 trong j.

11 pp j
x
i
x
j
x
i
x
j
x
i
xjid 
dcba
cb
jid


),(
cba
cb
jid


),(

Trích đoạn Biểu diễn và trích rút đặc trƣng Kết luận chƣơng 2 Thiết kế hệ thống

---