ĐẠI HỌC THÁI NGUN
ĐẠI HỌC CƠNG NGHỆ THƠNG TIN VÀ TRUYỀN THƠNG
Nguyễn Đình Sinh
NGHIÊN CỨU MỘT SỐ KỸ THUẬT PHÂN CỤM
TRONG TRA CỨU LOGO
Chun ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC
1. PGS.TS: ĐỖ NĂNG TỒN
Thái Ngun - 2013
Số hóa bởi trung tâm học liệu />MỤC LỤC
LỜI CẢM ƠN i
LỜI CAM ĐOAN ii
DANH MỤC CÁC HÌNH iii
LỜI MỞ ĐẦU 1
Chƣơng 1: KHÁI QT VỀ PHÂN CỤM VÀ BÀI TỐN TRA CỨU LOGO 3
1.1 Phân cụm dữ liệu 3
1.1.1 Khái niệm và mục tiêu của phân cụm dữ liệu 3
1.1.2 Các ứng dụng của phân cụm dữ liệu 6
1.1.3 Các u cầu của phân cụm 7
3.3.2 Chƣơng trình và một số kết quả đạt đƣợc 48
KẾT LUẬN 53
TÀI LIỆU THAM KHẢO 55
PHỤ LỤC - ẢNH LƠGƠ TRONG CƠ SỞ DỮ LIỆU 57
Số hóa bởi trung tâm học liệu /> i LỜI CẢM ƠN
Em xin chân thành cảm ơn PGS. TS Đỗ Năng Tồn đã tận tình hƣớng dẫn
khoa học, giúp đỡ em hồn thành tốt luận văn tốt nghiệp này.
Em cũng xin gửi lời cảm ơn tới các thầy, cơ giáo đã dạy dỗ, và trun đạt
kiến thức cho em trong suốt q trình học tập và nghiên cứu.
Học viên
NGUYỄN ĐÌNH SINH
Số hóa bởi trung tâm học liệu /> ii LỜI CAM ĐOAN
Tơi xin cam đoan tồn bộ nội dung trong Luận văn hồn tồn theo đúng nội
dung đề cƣơng cũng nhƣ nội dung mà cán bộ hƣớng dẫn giao cho. Nội dung của
Luận văn, các phần trích lục các tài liệu là hồn tồn chính xác. Nếu có sai sót
tơi hồn tồn chịu trách nhiệm.
Hình 3.7 - Màn hình lựa chọn các tham số cho chương trình 49
Hình 3.8- Màn hình lựa chọn menu mở file ảnh lơgơ đưa vào tra cứu 49
Hình 3.9- Màn hình hiển thị ảnh lơgơ đưa vào cùng histogram màu và hình dạng 50
Hình 3.10- Lựa chọn menu Image Retrieval -> By Color (tra cứu theo màu sắc) 50
Hình 3.11- Màn hình hiển thị kết quả 10 ảnh lơgơ gần giống nhất theo màu sắc 51
Hình 3.12- Lựa chọn menu Image Retrieval -> By Shape để tra cứu theo hình dạng 51
Hình 3.13- Màn hình hiển thị kết quả 10 ảnh lơgơ gần giống nhất theo hình dạng 52
Số hóa bởi trung tâm học liệu /> iv Số hóa bởi trung tâm học liệu /> 1 LỜI MỞ ĐẦU
Những năm gần đây, ảnh số và việc xử lý ảnh số ngày càng nhận đƣợc sự quan
tâm của nhiều ngƣời, một phần do các thiết bị thu nhận ảnh số ngày càng trở nên
thơng dụng với mọi ngƣời, cùng với nó là các thiết bị lƣu trữ ngày càng đƣợc cải
cục khơng gian của ảnh, để làm cơ sở cho việc tra cứu, sắp xếp, tổ chức CSDL
ảnh. Việc biểu diễn và trích rút đặc trƣng để nhận dạng đƣợc bức ảnh mong muốn
là rất quan trọng và nhiều hƣớng nghiên cứu khác nhau đã đƣợc triển khai. Tuy
nhiên, khi CSDL ảnh lớn thì việc tìm kiếm ảnh một cách tuần tự sẽ tốn rất nhiều
thời gian. Để tăng tốc hệ thống tra cứu ảnh dựa vào nội dung, cần có một số kỹ
thuật tra cứu ảnh nhanh. Thực tế đòi hỏi thời gian tìm kiếm khơng đƣợc tăng tuyến
tính đối với số các ảnh trong CSDL.
Có rất nhiều kỹ thuật đƣợc sử dụng trong tra cứu ảnh và Logo. Một trong các kỹ
thuật đó là các kỹ thuật phân cụm. Nó có thể giúp ngƣời sử dụng tìm kiếm nhanh và
chính xác một Logo đã có. Vì vậy tơi chọn đề tài: ”Nghiên cứu một số kỹ thuật phân
cụm trong tra cứu Logo”.
Luận văn đƣợc trình bầy trong 3 chƣơng và phụ lục:
Chương 1: Khái qt về phân cụm và bài tốn tra cứu Logo.
Chương 2: Một số kỹ thuật phân cụm trong tra cứu Logo.
Chương 3: Chương trình thử nghiệm. Số hóa bởi trung tâm học liệu /> 3 Chương 1: KHÁI QT VỀ PHÂN CỤM VÀ
BÀI TỐN TRA CỨU LOGO
1.1 Phân cụm dữ liệu
đƣợc xem là vấn đề học có giám sát thì PCDL là một bƣớc trong phân lớp dữ liệu,
PCDL sẽ khởi tạo các lớp cho phân lớp bằng cách xác định các nhãn cho các nhóm
dữ liệu
Trong KPDL, ngƣời ta có thể nghiên cứu các phƣơng pháp phân tích cụm có
hiệu quả và hiệu suất cao trong CSDL lớn. Những mục tiêu trƣớc tiên của nghiên
cứu là tập trung vào khả năng mở rộng của các phƣơng pháp phân cụm, tính hiệu
quả của các phƣơng pháp phân cụm với các hình dạng phức tạp, những kĩ thuật cho
phân cụm với nhiều kiểu dữ liệu có kích cỡ lớn và những phƣơng pháp cho PCDL
tƣờng minh và những dữ liệu dạng số hỗn hợp trong CSDL lớn. PCDL đƣợc sử
dụng rộng rãi trong nhiều ứng dụng, bao gồm nhận dạng mẫu, phân tích dữ liệu, xử
lý ảnh, nghiên cứu thị trƣờng
Hình 1.1- Mơ tả tập dữ liệu vay nợ đƣợc phân thành 3 cụm.
Vấn đề thƣờng gặp trong PCDL là hầu hết các dữ liệu cần cho phân cụm đều
có chứa dữ liệu “nhiễu” do q trình thu thập thiếu chính xác hoặc thiếu đầy đủ, vì
cần phải xây dựng chiến lƣợc cho 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 bƣớc vào giai đoạn phân tích PCDL. “nhiễu” ở đây có thể là
các đối tƣợng dữ liệu khơng chính xác hoặc các đối tƣợng dữ liệu khuyết thiếu
Số hóa bởi trung tâm học liệu /> 5 thơng tin về một số thuộc tính. Một trong các kỹ thuật xử lý nhiễu phổ biến là việc
thay thế giá trị của các thuộc tính của đối tƣợng “nhiễu” bằng giá trị thuộc tính
tƣơng ứng của đối tƣợng dữ liệu gần nhất.
Ngồi ra, dò tìm phần tử ngoại lai là một trong những hƣớng nghiên cứu
quan trọng trong PCDL, chức năng của nó là xác định một nhóm nhỏ các đối tƣợng
khơng có tiêu chuẩn tuyệt đối “tốt” mà có thể khơng phụ thuộc vào kết quả phân
cụm. Vì vậy, nó đòi hỏi ngƣời sử dụng phải cung cấp tiêu chẩn này, theo các mà kết
quả phân cụm sẽ đáp ứng đƣợc u cầu. Ví dụ, có thể quan tâm đến việc tìm đại
diện cho các nhóm đồng nhất (rút gọn dữ liệu), trong tìm kiếm Mục tiêu của phân
cụm dữ liệu là xác định đƣợc bản chất nhóm trong tập dữ liệu chƣa có nhãn. Nhƣng
để có thể quyết định đƣợc cái gì tạo thành một cụm tốt. Nó có thể đƣợc chỉ ra rằng
khơng có tiêu chuẩn tuyệt đối “tốt” mà có thể khơng phụ thuộc vào kết quả phân
cụm. Vì vậy, nó đòi hỏi ngƣời sử dụng phải cung cấp tiêu chẩn này, theo các mà kết
quả phân cụm sẽ đáp ứng đƣợc u cầu. Ví dụ, có thể quan tâm đến việc tìm đại
diện cho các nhóm đồng nhất (rút gọn dữ liệu), trong tìm kiếm “các cụm tự nhiên”
và mơ tả các thuộc tính chƣa biết (kiểu dữ liệu tự nhiên) hoặc tìm kiếm các đối
tƣợng khác thƣờng (dò tìm phần tử ngoại lai).
1.1.2 Các ứng dụng của phân cụm dữ liệu
Phân cụm dữ liệu là một cơng cụ quan trọng trong một số ứng dụng. Sau đây
là một số ứng dụng của nó:
• Giảm dữ liệu: Giả sử ta có một lƣợng lớn dữ liệu (N). Phân cụm sẽ nhóm
các dữ liệu này thành m cụm dữ liệu dễ nhận thấy và m << N. Sau đó xử lý mỗi
cụm nhƣ một đối tƣợng đơn.
• Rút ra các giả thuyết: Các giả thuyết này có liên quan đến tính tự nhiên của
dữ liệu và phải đƣợc kiểm tra bởi việc dùng một số tập dữ liệu khác.
• Kiểm định giả thuyết: Ta sẽ phân cụm để xét xem có tồn tại một tập dữ liệu
nào đó trong tập dữ liệu thoả mãn các giả thuyết đã cho hay khơng. Chẳng hạn xem
xét giả thuyết sau đây: “Các cơng ty lớn đầu tư ra nước ngồi“. Để kiểm tra, ta áp
dụng kỹ thuật phân cụm với một tập đại diện lớn các cơng ty. Giả sử rằng mỗi cơng
ty đƣợc đặc trƣng bởi tầm vóc, các hoạt động ở nƣớc ngồi và khả năng hồn thành
các dự án. Nếu sau khi phân cụm, một cụm các cơng ty đƣợc hình thành gồm các
cơng ty lớn và có vốn đầu tƣ ra nƣớc ngồi (khơng quan tâm đến khả năng hồn
thành các dự án) thì giả thuyết đó đƣợc củng cố bởi kỹ thuật phân cụm đã
thực hiện.
Số hóa bởi trung tâm học liệu />
phá tri thức từ dữ liệu,
1.1.3 Các u cầu của phân cụm
Việc xây dựng, lựa chọn một thuật tốn phân cụm là bƣớc then chốt cho việc
giải quyết vấn đề phân cụm, sự lựa chọn này phụ thuộc vào đặc tính dữ liệu cần
Số hóa bởi trung tâm học liệu /> 8 phân cụm, mục đích của ứng dụng thực tế hoặc xác định độ ƣu tiên giữa chất lƣợng
của các cụm hay tốc độ thực hiện thuật tốn,
Hầu hết các nghiên cứu và phát triển thuật tốn PCDL đều nhằm thỏa
mãn các u cầu cơ bản sau:
• Có khả năng mở rộng: Nhiều thuật tốn phân cụm làm việc tốt với những
tập dữ liệu nhỏ chứa ít hơn 200 đối tƣợng, tuy nhiên một CSDL lớn có thể chứa tới
hàng triệu đối tƣợng. Việc phân cụm với một tập dữ liệu cho lớn có thể làm ảnh
hƣởng tới kết quả. Vậy làm các nào để chúng ta có thể phát triển các thuật tốn
phân cụm có khả năng mở rộng cao đối với các CSDL lớn?
• Khả năng thích nghi với các kiểu dữ liệu khác nhau: Thuật tốn có thể áp
dụng hiệu quả cho việc phân cụm các tập dữ liệu với nhiều kiểu dữ liệu khác nhau
nhƣ dữ liệu kiểu số, kiểu nhị phân, dữ liệu định danh, hạng mục, và thích nghi
với kiểu dữ liệu hỗn hợp.
• Khám phá các cụm với hình dạng bất kỳ: Do hầu hết các cơ sở dữ liệu có
chứa nhiều cụm dữ liệu với các hình thù khác nhau nhƣ: hình lõm, hình cầu, hình
que, Vì vậy, để khám phá đƣợc các cụm có tính tự nhiên thì các thuật tốn phân
cụm cần phải có khả năng khám phá ra các cụm dữ liệu có hình thù bất kì.
• Tối thiểu lƣợng tri thức cần cho xác định các tham số đầu vào: Do các giá
trị đầu vào thƣờng ảnh hƣởng rất lớn đến thuật tốn phân cụm và rất phức tạp để
xác định các giá trị vào thích hợp đối với các CSDL lớn.
1.1.4 Những kỹ thuật tiếp cận trong phân cụm dữ liệu
Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong thực
tế. Các kỹ thuật phân cụm đều hƣớng tới hai mục tiêu chung: chất lƣợng của các
cụm khám phá đƣợc và tốc độ thực hiện của thuật tốn. Tuy nhiên có thể phân loại
thành từng loại cơ bản dựa trên phân loại các phƣơng pháp. Hiện nay, các kỹ thuật
phân cụm có thể phân loại theo các cách tiếp cận chính sau:
1.1.4.1 Phương pháp phân cụm phân hoạch
Ý tƣởng chính của kỹ thuật này là phân hoạch một tập hợp dữ liệu có n phần
tử cho trƣớc thành k nhóm dữ liệu sao mỗi phần tử dữ liệu chỉ thuộc về một nhóm
dữ liệu có tối thiểu ít nhất một phần tử dữ liệu. Số các cụm đƣợc thiết lập là các đặc
trƣng đƣợc lựa chọn trƣớc. Phƣơng pháp này là tốt cho việc tìm các cụm hình cầu
trong khơng gian Euclidean. Ngồi ra, phƣơng pháp này cũng phụ thuộc vào
khoảng cách cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là
gần nhau với mỗi điểm khác và các điểm dữ liệu nào khơng có quan hệ hoặc có
Số hóa bởi trung tâm học liệu /> 10 quan hệ là xa nhau so với mỗi điểm khác. Tuy nhiên, phƣơng pháp này khơng thể
xử lý các cụm có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dầy đặc. Các
thuật tốn phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ƣu
tốn cục cho vấn đề PCDL, do nó phải tìm kiếm tất cả các cách phân hoạch có thể
đƣợc. Chính vì vậy, trên thực tế thƣờng đi tìm giải pháp tối ƣu cục bộ cho vấn đề
này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lƣợng của cụm cũng
nhƣ để hƣớng dẫn cho q trình tìm kiếm phân hoạch dữ liệu. Với chiến lƣợc này,
thơng thƣờng bắt đầu khởi tạo một phân hoạch ban đầu cho tập dữ liệu theo phép
ngẫu nhiên hoặc Heuristic và liên tục tinh chỉnh nó cho đến khi thu đƣợc một phân
hoạch mong muốn, thỏa mãn ràng buộc cho trƣớc. Các thuật tốn phân cụm phân
trên các hàm chi phisddeer đảm bảo rằng chất lƣợng phân cụm ln đƣợc cải thiện.
Cách tiếp cận này giúp K-medoid giảm nhẹ ảnh hƣởng của nhiễu và các phần tử
ngoại lai, nhƣng cũng làm tăng thời gian tính tốn so với K-means.
Một biến thể khác của K-medoids là PAM (Partitioning Around Medoids),
trong đó việc lựa chọn phần tử medoid phải thỏa mãn điều kiện sai số bình phƣơng
là nhỏ nhất. Chất lƣợng phân cụm của PAM khá tốt, nhƣng thời gian thực hiện lâu
hơn so với K-means và K-medoids. Tuy nhiên, PAM tỏ ra khơng thích hợp đối với
tập dữ liệu lớn.
1.1.4.2 Phương pháp phân cụm phân cấp
Phƣơng pháp này xây dựng một phân cấp trên cơ sở các đối tƣợng dữ liệu đang
xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng hình
cây, cây phân cấp này đƣợc xây dựng theo kỹ thuật đệ quy. Cây phân cụm có thể
đƣợc xây dựng theo hai phƣơng pháp sau: hòa nhập nhóm, thƣờng đƣợc gọi là tiếp
cận Bottom-Up và phân chia nhóm, thƣờng đƣợc gọi là tiếp cận Top-Down.
Phương pháp Bottom-Up: phƣơng pháp này bắt đầu xuất phát với mỗi đối
tƣợng dữ liệu đƣợc khởi tạo tƣơng ứng với các cụm riêng biệt và sau đó tiến hành
nhóm các đối tƣợng theo một độ đo tƣơng tự (nhƣ khoảng cách giữa hai trung tâm
của hai nhóm), q trình này đƣợc thực hiện cho đến khi tất cả các nhóm đƣợc hòa
nhập vào một nhóm (mức cao nhất của cây phân cấp) hoặc cho đến khi các điều
kiện kết thúc thỏa mãn. Nhƣ vậy, cách tiếp cận này sử dụng chiến lƣợc ăn tham
trong q trình phân cụm.
Phương pháp Top-Down: Bắt đầu với trạng thái là tất cả các đối tƣợng dữ
liệu đƣợc sắp xếp trong cùng một cụm và phƣơng pháp này tiến hành chia nhỏ các
cụm. Mỗi vòng lặp thành cơng, một cụm đƣợc tách ra thành các cụm nhỏ hơn theo
Số hóa bởi trung tâm học liệu /> 12
Hình 1.3. Một số hình dạng khám phá bởi phân cụm dựa trên mật độ
Các cụm có thể đƣợc xem nhƣ các vùng mật độ cao, đƣợc tách ra bởi các
vùng khơng có hoặc ít mật độ. Khái niệm mật độ ở đây đƣợc xem nhƣ là các số các
đối tƣợng láng giềng.
Một thuật tốn PCDL dựa trên mật độ điển hình nhƣ DBSCAN, OPTICS,
DENCLUE, SNN,
1.1.4.4 Phương pháp phân cụm dựa trên lưới
Kỹ thuật phân cụm dựa trên mật độ khơng thích hợp với dữ liệu nhiều chiều,
để giải quyết cho đòi hỏi này, ngƣời ta đã sử dụng phƣơng pháp phân cụm dựa trên
lƣới. Đây là phƣơng pháp dựa trên cấu trúc dữ liệu lƣới để PCDL, phƣơng pháp này
chủ yếu tập trung áp dụng cho lớp dữ liệu khơng gian. Thí dụ nhƣ dữ liệu đƣợc biểu
diễn dƣới dạng cấu trúc hình học của đối tƣợng trong khơng gian cùng với các quan
hệ, các thuộc tính, các hoạt động của chúng. Mục tiêu của phƣơng pháp này là
lƣợng hố tập dữ liệu thành các ơ (cell), các ơ này tạo thành cấu trúc dữ liệu lƣới;
Sau đó, các thao tác PCDL làm việc với các đối tƣợng trong từng ơ này. Cách tiếp
Số hóa bởi trung tâm học liệu /> 14 cận dựa trên lƣới này khơng di chuyển các đối tƣợng trong các ơ mà xây dựng
nhiều mức phân cấp của nhóm các đối tƣợng trong một ơ. Ƣu điểm của phƣơng
pháp PCDL dựa trên lƣới là thời gian xử lý nhanh và độc lập với số đối tƣợng dữ
liệu trong tập dữ liệu ban đầu, thay vào đó là chúng phụ thuộc vào số ơ trong mỗi
chiều của khơng gian lƣới. Một thí dụ về cấu trúc dữ liệu lƣới chứa các ơ trong
khơng gian nhƣ hình sau:
Hình 1.4. Mơ hình cấu trúc dữ liệu lưới.
nhiều trong các lĩnh vực khác nhau và đã có một số nhánh nghiên cứu đƣợc phát
triển trên cơ sở các phƣơng pháp đó nhƣ:
- Phân cụm thống kê: Dựa trên các khái niệm phân tích hệ thống, nhánh
nghiên cứu này sử dụng các độ đo tƣơng tự để phân hoạch các đối tƣợng, nhƣng chỉ
áp dụng cho các dữ liệu có thuộc tính số.
- Phân cụm khái niệm: Các kỹ thuật phân cụm đƣợc phát triển áp dụng cho
dữ liệu hạng mục, chúng phân cụm các đối tƣợng theo các khái niệm mà chúng xử lý.
- Phân cụm mờ: Thơng thƣờng mỗi phƣơng pháp PCDL phân một tập dữ
liệu ban đầu thành các cụm dữ liệu có tính tự nhiên và mỗi đối tƣợng dữ liệu chỉ
thuộc về một cụm dữ liệu, phƣơng pháp này chỉ phù hợp với việc khám ph á ra các
cụm có mật độ cao và rời nhau. Tuy nhiên, trong thực tế, các cụm dữ liệu lại có thể
chồng lên nhau (một số các đối tƣợng dữ liệu thuộc về nhiều các cụm khác nhau),
ngƣời ta đã áp dụng lý thuyết về tập mờ trong PCDL để giải quyết cho trƣờng hợp
này, cách thức kết hợp này đƣợc gọi là phân cụm mờ. Trong phƣơng pháp phân
cụm mờ, độ phụ thuộc của đối tƣợng dữ liệu x
k
tới cụm thứ i (u
k
) có giá trị thuộc
Số hóa bởi trung tâm học liệu /> 16 khoảng [0,1]. Ý tƣởng trên đã đƣợc giới thiệu bởi Ruspini (1969) và đƣợc Dunn áp
dụng năm 1973 nhằm xây dựng một phƣơng pháp phân cụm mờ dựa trên tối thiểu
hóa hàm tiêu chuẩn. Bezdek (1982) đã tổng qt hóa phƣơng pháp này và xây dựng
thành thuật tốn phân cụm mờ c-means có sử dụng trọng số mũ.
C-means là thuật tốn phân cụm mờ (của K-means). Thuật tốn C - means
*) Khái niệm đặc trưng của ảnh số
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. Các đặc trƣng trực quan có thể đƣợc phân loại tiếp thành các đặc trƣng
chung và các đặc trƣng trong các lĩnh vực cụ thể. Các đặc trƣng trực quan chung
gồm: màu, kết cấu, hình dạng, ; các đặc trƣng trong các lĩnh vực cụ thể phụ
thuộc vào các ứng dụng, ví dụ: mặt ngƣời, 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, ta khơng đề cập ở đây.
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à
tùy vào điều kiện cụ thể nên lựa chọn các đặc trƣng ảnh một cách phù hợp.
*) Đặc trưng về màu sắc
Màu là đặc trƣng trực quan quan trọng đầu tiên và đơn giản nhất trong tra cứu ảnh
dựa vào nội dung. Nó cũng là đặc trƣng đƣợc sử dụng phổ biến nhất trong lĩnh vực
này, vì nó độc lập với kích thƣớc và hƣớng của ảnh. Mỗi điểm ảnh có thể đƣợc
biểu diễn nhƣ một điểm trong khơng gian màu sắc ba chiều, với các khơng gian
màu thƣờng dùng là RGB, HSV, CIE,
*) Lược đồ màu
Lƣợc đồ màu H của một ảnh đƣợc xác định bởi véc tơ: H={H[0], H[1], H[2], ,
H[N]}, trong đó H[i] là số các pixel có màu i trong ảnh, i biểu diễn một màu trong
lƣợc đồ màu, tƣơng ứng với một khối con trong khơng gian màu RGB, N là số các
bin trong lƣợc đồ màu, mỗi bin biểu thị xác suất của các pixel trong ảnh. Để so
sánh các ảnh có các kích cỡ khác nhau, các lƣợc đồ màu sẽ đƣợc chuẩn hóa. Lƣợc
đồmàu chuẩn hóa H’ đƣợc xác định: H’={H’[0], H’[1], , H’[N]},
với H'[i] = -Mi,p và p là tổng các pixel trong ảnh.
Đối với đặc trƣng màu, lƣợc đồ màu thƣờng đƣợc sử dụng để thực hiện việc tra
cứu ảnh bằng cách tính tốn để xác định tỉ trọng của các điểm ảnh, vì lƣợc đồ màu
biểu thị xác suất chung của các cƣờng độ của ba kênh màu. Có rất nhiều kỹ thuật
Số hóa bởi trung tâm học liệu />
2
), ,(a
N
,ß
N
)). Lƣu ý
rằng (a
1
+ß
1
,a
2
+ß
2
, ,a
N
+ß
N
) là lƣợc đồ màu của ảnh. Do đã tính đến cả thơng tin
khơng gian nên CCV cho kết quả tra cứu tốt hơn lƣợc đồ màu, đặc biệt với các ảnh
có sự tƣơng đồng lớn về màu sắc và kết cấu. Khơng gian màu HSV cung cấp các
kết quả tra cứu tốt hơn khơng gian CIE L*u*v* và CIE L*a*b*.
*) Tương quan màu
Tƣơng quan màu đƣợc đề xuất khơng chỉ để mơ tả các phân bố màu của các
pixel, mà còn tƣơng quan khơng gian của các cặp màu. Chiều thứ nhất và thứ hai
của lƣợc đồ màu ba chiều là các màu của mọi cặp pixel và chiều thứ ba làkhoảng
Số hóa bởi trung tâm học liệu />
Copyright: Tài liệu đại học ©