ĐẠ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
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 để
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
người nghiên cứu với nhiều cách tiếp cận khác nhau; do đó rất nhiều hệ thống tra cứu
ảnh dựa trên nội dung đã ra đời như: QBIC, VisualSeek, WebSeek và BlobWorld...
Phân cụm là bài toán đã được nhiều người nghiên cứu trước đây, nhưng cho đến
nayvẫn có vai tròquan trọng và cần thiết trong nghiên cứu khai phá dữ liệu cũng như
trong nhiều lĩnh vực đời sống: thương mại, sinh học, phân tích dữ liệu không gian. Đề
tài này nghiên cứu kỹ thuật phân cụm ảnh thành từng vùng rồi trích chọn đặc trưng của
từng vùng, dựa vào đó ta có thể tra cứu các bức ảnh một cách nhanh chóng và chính
xác từ một cơ sở dữ liệu ảnh cho trước. Có nhiềuphương pháp phân cụm khác nhau
như K-Means, HAC. Mỗi phương pháp có những ưu điểm, thế mạnh riêng và có yêu
cầu riêng về cách biểu diễn dữ liệu, độ đo. So sánh các thuật toán khác nhau ở các
phạm vi khác nhau là khôngđơn giản, do vậy việc đánh giá thường dựa vào chất lượng
kết quả phân cụm.Phân cụm tích lũy phân cấp (Hierarchical Agglomerative Clustering
HAC) là thuật toán phân cụm cây phâncấp có tính gia tăng cao và tạo ra được một cây
phân cấp các pixel dựa theo yếu tố nào đó, theo hướng tiếp cận này khóa luận sẽ áp
dụng phương pháp phâncụm HAC để phân cụm dữ liệu trước khi đưa vào tra cứu ảnh.
Nội dung của luận văn giới thiệu tổng quan về tra cứu ảnh dựa vào nội dung và
đi sâu vào đề tài “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”. Trên những cơ sở phương pháp tra
cứu ảnh dựa vào phân cụm, tiến hành xây dựng chương trình thử nghiệm cho phép đọc
3
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.
Thái Nguyên, ngày 25 tháng 2 năm 2013
MỤC LỤC
Lời mở đầu
Trang
Chương 1: TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG.....................1
1.1 Giới thiệu....................................................................................................................1
1.2 Đặc trưng ảnh.............................................................................................................3
1.2.1 Màu sắc.....................................................................................................................3
1.2.2 Kết cấu......................................................................................................................7
1.2.3 Hình dạng.................................................................................................................7
1.3 Độ tương tự giữa các ảnh...........................................................................................8
1.3.1 Độ đo về màu sắc.....................................................................................................8
1.3.2 Độ đo tương đồng hình dạng...................................................................................9
1.3.3 Độ đo tương đồng cho kết cấu ảnh..........................................................................9
1.3.4 Độ đo tương đồng cho đặc trưng phân đoạn...........................................................9
1.4 Các hệ thống tra cứu ảnh dựa vào nội dung............................................................10
1.4.1 Hệ thống QBIC (Query By Image Content)..........................................................10
1.4.2 Hệ thống Blobworld...............................................................................................10
1.4.3 Virage......................................................................................................................11
1.4.4 RetrievalWare.........................................................................................................11
1.4.5 VisualSeek và WebSeek.........................................................................................11
1.4.6 Photobook...............................................................................................................12
1.5 Đánh giá hiệu năng tra cứu......................................................................................12
1.6 Kết luận chương 1....................................................................................................14
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......................................................20
2.2.1 Kỹ thuật tra cứu dựa vào lược đồ màu toàn bộ - GCH.........................................20
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..............................................22
2.3.1 Khoảng cách Euclid...............................................................................................22
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ự.........................................................................................................26
2
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......................................................................................................45
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN......................................................................47
TÀI LIỆU THAM KHẢO..............................................................................................48
DANH MỤC CÁC BẢNG, SƠ ĐỒ, HÌN
Bảng 3.1 : Bảng cơ sở dữ liệu Image.............................................................................36
Bảng 3.2 : Bảng cơ sở dữ liệu Cluster............................................................................36
Bảng 3.3:Số liệu các loại ảnh trong cơ sở dữ liệu..........................................................37
Bảng 3.4 : Bảng kết quả tra cứu với chủ đề Ngựa.........................................................45
Bảng 3.5 : Bảng kết quả tra cứu với chủ đề Hoa.........................................................45Y
Hình 1.1: Kiến trúc hệ thống tra cứu ảnh dựa vào nội dung............................................2
Hình 1.2: Không gian màu RGB được trực quan hoá như một hình khối.......................4
Hình 1.3: Mô tả không gian màu HSV.............................................................................5
Hình 2.1: Biểu diễn phận cụm phân cấp bottom-up của 5 đối tượng............................19
Hình 2.2: Ba ảnh và biểu đồ của chúng..........................................................................21
Hình 2.3: Thuật toán phân cụm......................................................................................24
Hình 2.4: Thuật toán Single-Linkage.............................................................................25
Hình 2.5: Thuật toán tính khoảng cách giữa hai ảnh.....................................................28
Hình 3.1: Kiến trúc tổng quát của hệ thống tra cứu ảnh................................................31
Hình 3.2: Mô hình chi tiết của hệ thống tra cứu ảnh......................................................31
Hình 3.3: Biểu đồ UseCase tổng quát hệ thống.............................................................33
Hình 3.4: Biểu đồ trình tự tra cứu ảnh............................................................................34
Hình 3.5: Biểu đồ trình tự lưu vào cơ sở dữ liệu...........................................................35
Hình 3.6: Biểu đồ trình tự xoá ảnh khỏi cơ sở dữ liệu...................................................35
Hình 3.7: Mối quan hệ giữa các bảng.............................................................................37
Hình 3.8: Giao diện chính hệ thống tra cứu ảnh............................................................38
Hình 3.9: Giao diện hiển thị kết quả truy vấn................................................................38
Hình 3.10: Các vùng ảnh sau khi phân cụm...................................................................39
Hình 3.11: Giao diện chính tab cơ sở dữ liệu.................................................................39
Hình 3.12: Giao diện thêm một ảnh vào cơ sở dữ liệu..................................................40
Hình 3.13: Giao diện xoá một ảnh khỏi cơ sở dữ liệu...................................................40
Hình 3.14: Ảnh mẫu truy vấn thứ nhất...........................................................................41
Hình 3.15: Kết quả truy vấn lần thứ nhất.......................................................................41
Hình 3.16: Ảnh mẫu truy vấn thứ hai.............................................................................42
Hình 3.17: Kết quả truy vấn lần thứ hai.........................................................................42
Hình 3.18: Ảnh mẫu truy vấn thứ ba..............................................................................43
Hình 3.19: Kết quả truy vấn lần thứ ba..........................................................................43
Hình 3.20: Ảnh mẫu truy vấn thứ ba..............................................................................44
Hình 3.21: Kết quả truy vấn lần thứ 4............................................................................44
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
Uỷ ban quốc tế về màu sắc
HAC
l'éclairage
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
CSDL
Cơ Sở Dữ Liệu
1
Chương 1: TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG
1.1 Giới thiệu
Thông thường để lưu trữ thông tin, dữ liệu về một nội dung, sự vật, sự việc nào
đó thì người ta thường chọn sử dụng dạng lưu trữ kiểu văn bản. Nhưng lưu trữ dữ liệu
bằng văn bản nhiều khi không thể phản ánh đầy đủ, chân thực về đối tượng được miêu
tả và nhiều khi đó chỉ là do cảm nhận chủ quan củangười viết. Vì vậy kết hợp với lưu
trữ dữ liệu dạng văn bản người ta còn sử dụng lưu trữ dữ liệu dạng ảnh. Khối lượng dữ
liệu dạng ảnh ngày càng trở nên khổng lồ nhất là khi hiện nay các thiết bị thu nhận ảnh
số ngày càng trở nên phổ biến với giá cả phù hợp. Khi ta có nhu cầu tìm kiếm một vài
bức ảnh trong một kho dữ liệu ảnh có thể lên tới vài trăm nghìn bức ảnh để minh họa
cho một đề tài nào đó thì tuyệt đối không phải là chuyện đơn giản nếu chúng ta tìm
kiếm một cách thủ công tức là xem lần lượt từng bức ảnh cho tới khi ta tìm thấy được
bức ảnh có nội dung cần tìm. Song song với sự phát triển của các phương tiện kỹ thuật
số trong tương lai, số lượng ảnh sẽ còn tăng nhiều hơn nữa. Do vậy nhu cầu thật sự đòi
hỏi phải có một công cụ hỗ trợ tìm kiếm ảnh chính xác và hiệu quả. Vì vậy tra cứu ảnh
dựa vào nội dung ra đời để góp phần đáp ứng nhu cầu này.
“Tra cứu ảnh dựa vào nội dung” - Đây là một chủ đề nghiên cứu mới trong lĩnh
vực công nghệ thông tin. Mục đích chính của nó là lấy những ảnh từ cơ sở dữ liệu phù
hợp với tiêu chí truy vấn. Các yếu tố mô tả nội dung của một bức ảnh có liên quan đến
cảm nhận như màu sắc, kết cấu, hình dạng, cấu trúc, mối liên hệ về không gian và
chuyển động. Do vậy, phân tích ảnh, nhận dạng ảnh và thị giác máy tính đóng vai trò
cơ bản trong các hệ thống tra cứu ảnh.Nó cho phép tự động trích chọn hầu hết các
thông tin cảm nhận, thông qua việc phân tích phân bố điểm ảnh và rút ra các độ đo nội
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
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.
Thực hiện ngoại tuyếến
Cơ sở dữ liệu ảnh Cơ sở dữ liệu đặc trưng
Đá
nh
ch ỉ
sốấ
Trí
ch
rút
đặ
c
tr
nư
g
Người sử dụng
Tạo truy vấấn
So sánh độ tương tự
Trích rút đặc trưng
Đầầu ra
Các kếất quả tra cứu
Phản hốồi liến quan
Các hệ thống tra cứu ảnh dựa vào nội dung thường tuân theomô hình sau:
3
Hình 1.1: Kiến trúc hệ thống tra cứu ảnh dựa vào nội dung
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.
4
Hình 1.2: Không gian màu RGB được trực quan hoá như một hình khối.
Mỗi trục màu (R, G, B) có độ quan trọng như nhau. Do đó, mỗi trục nên được
lượng hoá với cùng một độ chính xác. Khi không gian màu RGB được lượng hoá, số
các bin sẽ luôn luôn là một hình khối. Thông thường, 8 (2 3), 64 (43), 216 (63), 512 (83)
bin được sử dụng trong lượng hoá không gian màu RGB. Chuyển đổi từ một ảnh RGB
sang một ảnh cấp xám nhận được tổng của R, G và B rồi chia kết quả cho ba.
Không gian màu HSx
Không gian màu HSI, HSV, HSB và HLS thường được gọi là HSx có mối liên
quan gần gũi với sự nhận thức về màu sắc của con người hơn là không gian màu RGB.
Những trục từ không gian màu HSx mô tả những đặc tính của màu như sắc độ, độ bão
hoà và độ sáng. Sự khác nhau giữa những không gian màu HSx là sự biến đổi của
chúng từ không gian màu RGB, chúng thường được mô tả bằng những hình dạng khác
nhau (như hình nón, hình trụ). Trong hình 1.3 không gian màu HSV được mô tả như
hình nón.
5
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
3600. 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
33
0
của mặt phẳng U-V. Tín hiệu Y biểu diễn độ chói của một pixel
6
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
xác. Với cả không gian màu XYZ và LUV, các lược đồ lượng hoá thường sử dụng 8
(23), 27 (33), 64 (43), 125 (53) bin.
1.2.1.2 Lược đồ màu
Lược đồ màu được xác định bằng một tập các bin, trong đó mỗi bin biểu thị xác
suất của các pixel trong ảnh. Một lược đồ màu H của một ảnh đã cho được xác định
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
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]},
H ' i
Ở đây
H i
p
, 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
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
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.
8
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,
các đặc trưng thuộc về các vùng thu được sẽ được ghi lại. Các mã xích[9] sử dụng 4
hoặc 8 liên thông để biểu diễn cácđoạn thẳng tạo thành đường biên của vùng. Các dấu
hiệu, số các hình vàđa giác là các lượcđồ biểu diễn khác.
Bước tiếp theo là sử dụng các mô tả thích hợp cho các vùng này sao cho chúng
có thểđược sử dụng trong khi đối sánh các vùng của cácảnh khác nhau. Các mô tả
hìnhđược chia thành ba loại: Các mô tả dựa vàođường biên xácđịnh các thuộc tính
củađường biên. Các kỹ thuật dựa vào đường biên sử dụng các phác thảo vùngđể tính
toán hình. Mô tả Fourier là một trong những phương pháp phổ biến thuộc về loại này.
Trong kỹ thuật này, đường biên của một vùng đã cho được thu và được biến đổi
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độ
ứng nhưsau:
Khoảngcách Ơclit:
ĐâylàkhoảngcáchƠclitthôngthườnggiữacácKbin:
k
j 1
Intersection (h(I),h(M)) =
(h( I ) h(M )) 2
k
(h( I ) h( M )) 2
j 1
(1-18)
đotương
9
Hoặc
k
h( I ) h ( M )
j 1
Intersection (h(I),h(M)) =
(1-19)
ĐộđoJensen-Shannondivergence(JSD):
ĐộđoJensen-Shannon
divergencesửdụnglượcđộmàuRGBđểtínhtoánđộ
tươngđồngvềmàusắcgiữa2ảnh:
M
m 1
dJSD(H,H’)=
M
m 1
H m log
H m log
2H m
2H 'm
'
H
log
m
H m H 'm
H 'm H m
(1-20)
2H m
2H '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
vẽhaycungcấp.
1.3.3 Độ đo tương đồng cho kết cấu ảnh
Đểđođộtươngđồng
theokếtcấugiữacácảnh,ngườitathườngsửdụngđộđo
Ơclit.Kếtcấuđượctrích xuấttừ cácbức ảnhsẽ đượcbiểu diễnthànhcácvéc tơnhiều
10
chiềuvàkhoảngcáchƠclitđượcdùngđểđođộtươngđồnggiữacácđặctrưngcủa
ảnhtruyvấnvớiđặctrưngcủaảnhtrongcơsởdữliệu.
1.3.4 Độ đo tương đồng cho đặc trưng phân đoạn
Mộtsốđộđotươngđồngchoảnh:
Độ đo Cosin:
x. y
x. y
x. y
x. y
d(x,y) =
(1-21)
Khoảng cách góc:
cos 1 ( x. y)
d(x,y) =
cos 1 ( x. y )
1
cos ( x, y )
(1-22)
cos 1 ( x, y )
Độ đo Euclide:
m
i 1
xi yi
2
m
i 1
xi yi
2
d(x,y) =
(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
được ứng dụng trong thực tiễn. Các kỹ thuật trong hệ thống này là cơ sở nghiên cứu
cho sự xây dựng và phát triểncủa các hệ thống tra cứu ảnh sau này. QBIC cung cấp
một số phương pháp: đơn đặc trưng, đa đặc trưng [12] và Multi-pass:
Phương pháp truy vấn đơn đặc trưngchỉ sử dụng một đặc điểm cụ thể để tra cứu
ảnh.
Truy vấn đa đặc trưng bao gồm nhiều hơn một đặc trưngvà mọi đặc trưngđều có
trọng số như nhau trong suốt quá trình tìm kiếm.
11
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).
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
12
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 http://vrw.excalib.com/cgi-bin/sdk/cst/cst2.bat.
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
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
đá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
http://www.ee.columbia.edu/sfchang/demos.html.
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à
- Xem thêm -