Luận văn Tìm kiếm ảnh dựa vào nội dung

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

KHOA CÔNG NGHỆ THÔNG TIN

BỘ MÔN CÔNG NGHỆ TRI THỨC

NGUYỄN QUỐC UY

- 9912745

TÌM KIẾM ẢNH DỰA VÀO NỘI DUNG

LUẬN VĂN CỬ NHÂN TIN HỌC

GIÁO VIÊN HƯỚNG DẪN

Th.s LÝ QUỐC NGỌC

, 07/2003

Luận văn tốt nghiệp đại học

LỜI CẢM ƠN

Trước tiên, em xin chân thành gửi lời cảm ơn đến Thầy Lý Quốc Ngọc,

người đã nhiệt tình, tận tâm, hướng dẫn về kiến thức để em có thể làm được luận

văn này. Đúng lúc tưởng chừng đã bị bế tắt trong công việc, Thầy đã động viên giúp

em mạnh dạng hoàn thành luận văn này. Một lần nữa em xin tỏ lòng biết ơn Thầy.

Sau hết, xin gửi lời cảm ơn đến gia đình bạn bè, người thân đã ủng hộ động

viên tinh thần để luận văn được hoàn thành.

Xin chân thành cảm ơn tất cả !

TPHCM, 07/2003

Người thực hiện

Nguyễn Quốc Uy

Luận văn tốt nghiệp đại học

NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN

...............................................................................................................................................

Luận văn tốt nghiệp đại học

NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN

...............................................................................................................................................

Luận văn tốt nghiệp đại học

MỤC LỤC

LỜI MỞ ĐẦU

PHẦN 1: TỔNG QUAN

1. Sự hình thành bài toán ..............................................................................3

2. Cách tiếp cận:.............................................................................................3

2.1. Đặc trưng màu sắc: .................................................................................4

2.2. Đặc trưng vân:.........................................................................................4

2.3. Đặc trưng hình dáng:..............................................................................4

2.4. Độ đo: .......................................................................................................4

2.5. Mô hình giao diện: ..................................................................................5

PHẦN 2: CÁC PHƯƠNG PHÁP TÌM KIẾM ẢNH DỰA VÀO NỘI DUNG

Chương 1: Tìm kiếm ảnh dựa vào màu sắc.................................................9

1. Màu sắc: ......................................................................................................10

1.1. Một số đặc tính vật lý đặt biệt của màu sắc..........................................10

1.2. Hệ thống màu chuẩn RGB .....................................................................10

1.3. Hệ thống màu CMY................................................................................12

1.4. Hệ thống màu L*a*b...............................................................................12

1.5. Hệ thống màu HSI...................................................................................12

2. Tìm kiếm ảnh dựa vào màu sắc ................................................................14

2.1. Lượt đồ màu ............................................................................................14

2.2. Các loại độ đo màu sắc............................................................................19

Chương 2:Tìm kiếm ảnh dựa vào vân..........................................................22

Luận văn tốt nghiệp đại học

1. Vân...............................................................................................................23

1.1. Vân là gì? ................................................................................................23

1.2. Một số loại vân tiêu biểu.........................................................................24

2. Tìm kiếm ảnh dựa vào vân........................................................................25

2.1. Mật độ của đường biên và hướng của biên...........................................25

2.2. Phân hoạch vùng nhị phân cục bộ.........................................................27

2.3. Ma trận đồng hiện và đối tượng đồng hiện ..........................................28

2.4. Độ đo năng lượng của vân dựa vào luật đo ..........................................31

2.5. Tương quan tự động và quang phổ năng lượng...................................33

2.6. Phân đoạn vân (Texture segmentation) ................................................34

Chương 3:Tìm kiếm ảnh dựa vào hình dạng...............................................35

1. Hình dạng....................................................................................................36

1.1. Khái niệm về hình dạng..........................................................................36

1.2. Đặc điểm hình dạng đối với việc tìm kiếm ảnh ....................................36

2. Tìm kiếm ảnh dựa vào hình dạng.............................................................37

2.1. Lượt đồ hình dạng...................................................................................37

2.2. Độ so khớp đường biên của hình dạng..................................................38

2.3. So khớp với ảnh phát họa.......................................................................40

PHẦN 3 CÀI ĐẶT VÀ KẾT QUẢ THỬ NGHIỆM

Chương 1:Cài đặt...........................................................................................44

1. Chương trình ..............................................................................................45

2. Phần Màu sắc..............................................................................................46

Luận văn tốt nghiệp đại học

3. Phần Vân.....................................................................................................50

4. Phần Hình dạng..........................................................................................53

Chương 2:Kết quả thử nghiệm .....................................................................54

1. Phần Màu sắc..............................................................................................55

2. Phần Vân.....................................................................................................73

3. Phần Hình dạng..........................................................................................77

PHẦN 4 KẾT LUẬN

Đánh giá kết quả đạt được ...........................................................................80

Hướng phát triển............................................................................................80

Tài liệu tham khảo .........................................................................................81

Luận văn tốt nghiệp đại học

TÓM TẮT LUẬN VĂN

Tên đề tài : Tìm kiếm ảnh dựa vào nội dung

Tìm kiếm ảnh dựa vào nội dung là một đề tài nghiên cứu về khả năng để xây dựng

một chương trình cho phép tìm kiếm ảnh trên một cơ sở dữ liệu ảnh cho trước. Việc

tìm kiếm này dựa trên nội dung của những bức ảnh trong cơ sở dữ liệu. Nội dung

của một bức ảnh có thể là màu sắc của bức ảnh, vân của bức ảnh, hay những kiểu

hình dạng.

Luận văn này tập trung vào việc nghiên cứu những lý thuyết để xây dựng nên một

ứng dụng như vậy, đồng thời ứng dụng lý thuyết đó để xây dựng nên một số demo,

cho thấy khả năng có thể phát triển được thành ứng dụng hoàn thiện được.

Đề tài gồm có ba phần: tìm kiếm ảnh dựa vào màu sắc, vân và hình dạng.

Tìm kiếm ảnh dựa vào màu sắc: cách tiếp cận chính là dựa vào lượt đồ màu (colour

histogram)

Tìm kiểm ảnh dựa vào vân: cách tiếp cận chính là dựa vào ma trận đồng hiện (co-

occurrence matrix)

Tìm kiếm ảnh dựa vào hình dạng: cách tiếp cận chính là dựa vào sự so khớp ảnh

phát họa (sketch matching)

Luận văn tốt nghiệp đại học

LỜI MỞ ĐẦU

Sự mở rộng của multimedia, cùng với khối lượng hình ảnh và phim lớn, sự

phát triển của những xa lộ thông tin hiện tại đã thu hút ngày càng nhiều những

chuyên gia đi vào nghiên cứu những công cụ cung cấp cho việc lấy thông tin từ dữ

liệu ảnh từ nội dung của chúng. Lấy thông tin từ dữ liệu ảnh có liên quan đến rất

nhiều các lĩnh vực khác, từ những phòng trưng bày tranh nghệ thuật cho tới những

nơi lưu trữ tranh nghệ thuật lớn như viện bảo tàng, kho lưu trữ ảnh chụp, kho lưu

trữ ảnh tội phạm, cơ sở dữ liệu ảnh về địa lý, y học, ... điều đó làm cho lĩnh vực

nghiên cứu này phát triển nhanh nhất trong công nghệ thông tin.

Lấy thông tin từ dữ liệu ảnh đặt ra nhiều thách thức nghiên cứu mới cho các

khoa học gia và các kỹ sư. Phân tích ảnh, xử lý ảnh, nhận dạng mẫu, giao tiếp giữa

người và máy là những lĩnh vực nghiên cứu quan trọng góp phần vào phạm vi

nghiên cứu mới này.

Khía cạnh tiêu biểu của lấy thông tin từ dữ liệu ảnh dựa trên những công bố

có sẵn như là những đối tượng nhận thức như màu sắc, vân (texture), hình dáng, cấu

trúc, quan hệ không gian, hay thuộc về ngữ nghĩa căn bản như: đối tượng, vai trò

hay sự kiện hay liên quan đến thông tin về ngữ nghĩa quan hệ như cảm giác, cảm

xúc, nghĩa của ảnh. Thật ra phân tích ảnh, nhận dạng mẫu, hay xử lý ảnh đóng một

vai trò căn bản trong hệ thống lấy thông tin từ ảnh. Chúng cho phép sự trích rút tự

động hầu hết những thông tin về nhận thức, thông qua phân tích sự phân bổ điểm

ảnh và sự phân tích độ đo.

Tìm kiếm theo cách thông thường dựa trên văn bản giờ đây được bổ sung bởi

truy vấn dựa vào nội dung, nhắm vào khía cạnh nhận thức thông tin ảnh. Thực hiện

truy vấn ở mức nhận thức đòi hỏi những phương thức mới, cho phép chỉ định đến

những thuộc tính liên quan đến thị giác cần tìm. Giao diện đồ họa phải hỗ trợ đặc tả

những ví dụ đó như là những mẫu có sẵn. Khi đó người dùng trong một vòng lặp,

mô hình giao diện sao cho người dùng có thể truy cập vào sự giống nhau giữa

những đối tượng.

1

Luận văn tốt nghiệp đại học

PHẦN 1

TỔNG QUAN

2

Luận văn tốt nghiệp đại học

1. Sự hình thành bài toán:

Bên cạnh kho dữ liệu văn bản, kho dữ liệu ảnh ngày càng trở nên khổng lồ

vượt quá sự kiểm soát của con người. Khi có nhu cầu tìm kiếm một vài tấm

ảnh nào đó trong một cơ sở dữ liệu hàng trăm ngàn ảnh, điều này khó có thể

thực hiện được khi ta tìm kiếm bằng tay theo cách thông thường, nghĩa là

xem lần lượt từng tấm ảnh một cho đến khi tìm thấy ảnh có nội dung cần tìm.

Song song với sự phát triển của những phương tiện kỹ thuật số, trong tương

lai, số lượng ảnh sẽ còn tăng nhanh hơn nữa, nhiều hơn nữa. Do đó, nhu cầu

thật sự đòi hỏi phải có một công cụ hỗ trợ cho việc tìm kiếm này càng sớm

càng tốt. Vì vậy đề tài “tìm kiếm dữ liệu ảnh dựa vào nội dung” ra đời để góp

phần đáp ứng nhu cầu này.

“Tìm kiếm dữ liệu ảnh dựa vào nội dung” là gì? Đây là một chủ đề nghiên

cứu mới trong 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.

Thế hệ đầu tiên của hệ thống tìm kiếm ảnh dựa vào nội dung cho phép truy

cập trực tiếp đến ảnh thông qua thuộc tính chuỗi. Những tìm kiếm đặc thù

cho những hệ thống dạng này là “tìm tất cả những tranh vẽ của trường

Florentine trong thế kỷ thứ XV” hay “tìm kiếm tất cả những tấm ảnh về đất

đai của Cezanne”. Metadata của hệ thống trong thế hệ đầu tiên dựa trên

chuỗi, sơ đồ trình bày, mô hình quan hệ, cấu trúc khung. Xem hình 1.1.

Thế hệ mới của hệ thống tìm kiếm ảnh hỗ trợ đầy đủ việc lấy thông tin dựa

vào nội dung thuộc về thị giác. Chúng cho phép phân tích đối tượng, tự động

trích rút đặc trưng. Xem hình 1.2.

Những phần tử thuộc về thị giác như là màu sắc, vân, hình dạng đối tượng,

quan hệ không gian có liên quan trực tiếp đến khía cạnh nhận thức của nội

dung ảnh. Ta trực tiếp đánh vào những phần tử này trong việc tìm kiếm.

Do đó, nội dung của đề tài sẽ giải quyết như sau: hệ thống tìm kiếm ảnh dựa

vào nội dung, ba đặc trưng là màu sắc,vân và hình dạng. Đề tài chỉ tập chung

vào demo một số phương pháp làm của từng phần.

3

Luận văn tốt nghiệp đại học

2. Cách tiếp cận:

Đề tài tiếp cận theo mô hình thống kê.

Có ba loại tìm kiếm ảnh đề tài tập chung giải quyết là :

- Tìm kiếm ảnh dựa vào màu sắc.

- Tìm kiếm ảnh dựa vào vân.

- Tìm kiếm ảnh dựa vào hình dạng.

2.1. Đặc trưng màu sắc:

Màu sắc là vấn đề cần tập chung giải quyết nhiều nhất, vì một ảnh màu thì

thông tin quan trọng nhất trong ảnh chính là màu sắc. Hơn nữa thông tin về

màu sắc là thông tin người dùng quan tâm nhất; qua đặc trưng màu sắc, có

thể lọc được rất nhiều lớp ảnh, thông qua vị trí, không gian, định lượng của

màu trong ảnh.

2.2. Đặc trưng vân:

Có những lớp ảnh mà màu sắc không thể giải quyết được, đòi hỏi phải dùng

đặc trưng vân. Ví dụ như những ảnh liên quan đến cấu trúc của điểm ảnh

như: cỏ, mây, đá, sợi.

Vân sẽ giải quyết tốt cho việc tìm kiếm đối với lớp ảnh này.

2.3. Đặc trưng hình dáng:

Đối với những lớp ảnh cần tìm mà liên quan đến hình dạng của đối tượng thì

đặc trưng vân và màu không thể giải quyết được. Ví dụ như tìm một vật có

hình dạng ellipse hay hình tròn trong ảnh.

Tìm kiếm theo hình dáng thật sự là một cái đích của hệ thống tìm kiếm dựa

vào nội dung muốn đạt tới.

2.4. Độ đo:

Có ý nghĩa quan trọng trong tìm kiếm ảnh dựa vào nội dung. Độ đo mang ý

nghĩa quyết định kết quả tìm kiếm sẽ như thế nào, mức độ chính xác.

4

Luận văn tốt nghiệp đại học

2.5. Mô hình giao diện:

Giao diện cũng là một vấn đề đáng quan tâm của bài toán tìm kiếm ảnh. Mô

hình giao diện dựa trên mô hình tìm kiếm cho phép lặp.

Đây mô hình người dùng có thể đặc tả yêu cầu tìm kiếm với nhiều cấp độ.

Quá trình tìm kiếm có thể là một quá trình lặp đi lặp lại nhiều lần: tìm kiếm,

lọc, chỉnh sửa ngưỡng cho đến khi đạt đến kết quả như mong muốn. Do đó

giao diện chương trình phải hỗ trợ chức năng cho phép chọn lọc kết quả, loại

bỏ những kết quả không phù hợp, lưu lại những kết quả đã vừa ý, tìm kiếm

trong kết quả vừa tìm được, thay đổi mức độ chính xác của việc tìm kiếm.

Hai vấn đề được đề tài quan tâm về giao diện tìm kiếm là: mô hình tìm kiếm

theo không gian toàn cục và cục bộ. Đối với đặc trưng màu: giao diện cho

phép giao tiếp cả toàn cục và cục bộ. Đặc trưng vân và hình dạng đề tài chỉ

dừng lại ở mức toàn cục.

5

Luận văn tốt nghiệp đại học

Người dùng

Phản hồi

Truy vấn bằng văn

Trình bày nội dung

bản

Hệ thống tìm kiếm

Chỉ mục

Chú thích

(làm bằng tay)

Hình 1.1 Mô hình của hệ thống tìm kiếm thế hệ đầu tiên

6

Luận văn tốt nghiệp đại học

Người dùng

Phản hồi

Truy vấn

bằng văn bản

Truy vấn

bằng vídụ

Tìm lướt

Trình bày nội dung

qua

Hệ thống tìm kiếm

Chỉ mục

Trích rút đặt

trưng

Chú thích

(làm bằng tay)

Hình 1.2 Mô hình của hệ thống tìm kiếm thế hệ mới

7

Luận văn tốt nghiệp đại học

PHẦN 2

CÁC PHƯƠNG PHÁP TÌM KIẾM

ẢNH DỰA VÀO NỘI DUNG

8

Luận văn tốt nghiệp đại học

Chương 1:

Tìm kiếm ảnh dựa vào màu sắc

1. Màu sắc

1.1. Một số đặc tính vật lý đặt biệt của màu sắc

1.2. Hệ thống màu chuẩn RGB

1.3. Hệ thống màu CMY

1.4. Hệ thống màu L*a*b

1.5. Hệ thống màu HSI

2. Tìm kiếm ảnh dựa vào màu sắc

2.1. Lượt đồ màu

2.2. Các loại độ đo màu sắc

9

Luận văn tốt nghiệp đại học

1. Màu sắc:

Sự nhận thức về màu sắc là quá trình quan trọng của con người. Sự nhận

thức về màu sắc phụ thuộc vào cả tính chất vật lý của ánh sáng và quá trình

xử lý của thị giác với sự góp phần rất quan trọng của kinh nghiệm. Con

người dùng thông tin màu sắc để phân biệt đối tượng, vật liệu, đồ ăn, vị trí và

ngay cả thời gian của ngày.

Với sự phát triển mạnh mẽ của các thiết bị kinh tế, máy móc xử lý màu sắc

trở nên thông dụng: Chúng ta có các thiết bị như máy quay phim màu, thiết

bị chiếu màu và những phần mềm xử lý ảnh màu. Máy móc có thể dùng màu

sắc cho những mục đích như là con người. Đặc biệt, màu sắc thuận tiện bởi

vì nó cung cấp phép đo lường đa dạng tại mỗi điểm ảnh đơn, có thể phân lớp,

phân loại mà không cần đến những sự xử lý không gian phức tạp để đưa đến

quyết định.

1.1. Một số đặc tính vật lý đặc biệt về màu sắc:

Con người chỉ có khả năng nhận thức được ánh sáng có bức xạ điện từ với

bước sóng trong khoảng 400 – 700 nanomet. Cơ quan thị giác cảm nhận

được ánh sáng là do bề mặt đối tượng phát ra ánh sáng, là kết quả của sự

tương tác giữa năng lượng chiếu sáng và những phân tử của bề mặt đối

tượng. Một đối tượng màu xanh dương sẽ có bề mặt màu xanh dương khi

chiếu ánh sáng trắng vào. Nhưng đối tượng đó sẽ có màu tím khi chiếu ánh

sáng đỏ vào.

1.2. Hệ thống màu chuẩn RGB:

Mắt người có thể phân biệt hàng ngàn màu sắc khác nhau, những con số

chính xác hơn vẫn còn đang được bàn cãi nhiều. Ba màu RGB (Red-Green-

Blue) mã hóa hệ thống đồ họa sử dụng ba byte (2⁸)³hay khoảng chừng 16

triệu màu phân biệt. Máy tính có thể phân biệt bất kỳ màu gì sau khi được

mã hóa, nhưng việc mã hóa có thể không trình bày được những sự khác biệt

10

Luận văn tốt nghiệp đại học

trong thế giới thực. Mỗi điểm ảnh RGB bao gồm một byte cho màu R, một

byte cho màu G và một byte cho màu B.

Việc mã hóa một màu tùy ý trong dãy hiển thị được làm bằng cách tổ hợp ba

màu chính. Ví dụ: Red(255,0,0), Green(0,255,0), Blue(0,0,255), Black(0,0,0)

Hệ thống màu RGB là một hệ thống màu cộng vào bởi vì mỗi màu được tạo

nên bằng cách cộng thêm các phần tử vào màu đen(0,0,0)

Khuôn dạng của không gian màu RGB là định dạng phổ biến nhất của ảnh

số, lý do chính là tính tương thích với màn hình hiển thị chính là màn hình vi

tính. Tuy nhiên không gian màu RGB có hạn chế lớn nhất là không phù hợp

với cách con người cảm nhận về màu sắc. Do đó không phù hợp cho việc

ứng dụng vào tìm kiếm ảnh.

Blue

[0,1,1]

Cyan

[0,0,1]

[1,0,1]

Magenta

[0,1,1]

White

[0,0,0]

Green

[0,1,0]

[1,0,0]

[1,1,0]

Yellow

Red

Hình 1: Khối màu

11

Luận văn tốt nghiệp đại học

1.3. Hệ thống màu CMY:

Hệ thống màu CMY theo mô hình in trên giấy trắng và theo khuôn mẫu trừ

từ màu trắng thay vì thêm vào từ màu đen như hệ thống màu RGB.

CMY là viết tắt của Cyan-Magenta-Yellow (màu lục lam, màu đỏ tươi, màu

vàng), đó là ba màu chính tương ứng với ba màu mực in. Cyan hấp thu sự

chiếu sáng của màu đỏ, Magenta hấp thu màu xanh lục, Yellow hấp thu màu

xanh dương. Do đó, tạo ra sự phản ánh tương ứng như khi in ảnh được chiếu

sáng với ánh sáng trắng. Hệ thống dưới dạng âm tính vì mã hóa theo dạng

hấp thụ màu. Có một số mã hóa như sau: trắng (0,0,0) vì không có ánh sáng

trắng được hấp thụ, đen (255,255,255) vì tất cả các thành phần của màu trắng

đều được hấp thụ.

Hệ thống màu CMY dường như là một sự đảo ngược của hệ thống màu

RGB. Đặc tính của nó là sự đơn giản, ứng dụng nhiều trong thực tế. Tuy

nhiên khuyết điểm của nó cũng tương tự như không gian màu RGB, tức là

cách mã hóa khác với cách mà con người cảm nhận về màu sắc. Không thích

hợp cho bài toán tìm kiếm ảnh dựa vào nội dung.

1.4. Hệ thống màu L*a*b:

Mô hình L*a*b được đề cử bởi CIE cho việc lượng hóa sự khác biệt của màu

sắc trong vật chiếu sáng của ánh sáng ban ngày. Tuy nhiên nó có một sự

chuyển đổi được ghi vào để mà tính toán cho việc thích nghi với những

nguồn sáng.

Đây là hệ thống màu có sự tách riêng ánh sáng và màu sắc ra riêng. Do đó,

cũng có khả năng lớn cho việc tìm kiếm dựa vào nội dung.

1.5. Hệ thống màu HSI: Hue-Saturation-Intensity

Hệ thống màu HSI mã hóa thông tin màu sắc bằng cách chia giá trị intensity

I từ hai giá trị được mã hóa thuộc về độ hội tụ của màu- hue H và saturation

S.

12

Luận văn tốt nghiệp đại học

Thành phần không gian màu HSI gồm có ba phần: Hue được định nghĩa có

giá trị 0-2Π , mang thông tin về màu sắc. Saturation có giá trị 0-1, mang giá

trị về độ thuần khiết của thành phần Hue. Intensity (Value) mang thông tin

về độ sáng của điểm ảnh.Ta có thể hình dung không gian màu HSI như là vật

hình nón. Với trục chính biểu thị cường độ sáng Intensity. Khoảng cách đến

trục biểu thị độ tập chung Saturation. Góc xung quanh trục biểu thị cho sắc

màu Hue.

Đôi khi, hệ thống màu HSI được coi như là hệ thống màu HSV dùng Value

thay vì Intensity.

Hệ thống màu HSI thì thích hợp hơn với một số thiết kế đồ họa bởi vì nó

cung cấp sự điều khiển trực tiếp đến ánh sáng và hue. Hệ thống màu HSI

cũng hỗ trợ tốt hơn cho những thuật toán xử lý ảnh vì sự tiêu chuẩn hóa về

ánh sáng và tập chung vào hai tham số về độ hội tụ màu, và cường độ màu.

H=2Π/3

Green

I

H=Π/3

Yellow

White

Yellow

H

S

Cyan

H=Π

Red

H=0

Cyan

Red

Blue

H=4Π/3

I=1

Magenta

I=0.5

Blue

[0,0,0]

Black

Hình 2: Khối nón màu minh họa hệ thống màu HSI

Hệ thống màu HSI có sự phân chia rõ rệt giữa ánh sáng và màu sắc. Do đó

có khả năng rất lớn được áp dụng cho việc tính đặc trưng và so sánh sự giống

13

Luận văn tốt nghiệp đại học

nhau về màu sắc của hai ảnh. Do đó nó rất thích hợp cho việc tìm kiếm ảnh

dựa vào màu.

Sự giống và khác nhau giữa hai ảnh về mặt màu sắc đối với mắt người chỉ

mang ý nghĩa tương đối. Do đó khi áp dụng vào bài toán này trên máy tính

thì ta cũng giả lập sự tương đối này.

Phương pháp chính của việc tìm kiếm theo màu sắc là dùng lượt đồ màu để

làm đặc trưng cho từng ảnh. Do những đặc điểm riêng của mô hình màu HSI

và đặc trưng của việc tìm kiếm nên tính lượt đồ màu cũng được dùng một mô

mình rất đặc biệt để phù hợp cho những đặc điểm riêng này.

2. Tìm kiếm ảnh dựa vào màu sắc:

Phương pháp phổ biến để tìm kiếm ảnh trong một tập những ảnh hỗn tạp cho

trước là dựa vào lượt đồ màu của chúng. Đây là cách làm khá đơn giản, tốc

độ tìm kiếm tương đối nhanh nhưng khuyết điểm là kết quả tìm kiếm lại có

độ chính xác không cao. Nhưng đây có thể được xem như là bước lọc đầu

tiên cho những tìm kiếm sau. Muốn được kết quả chính xác cao đòi hỏi sự

kết hợp đồng thời với vân (texture) và hình dáng (shape).

Cho đến nay, để giải quyết vấn đề về màu sắc, cách tiếp cận chính vẫn là dựa

vào lượt đồ màu.

2.1. Lượt đồ màu:

Lượt đồ màu: Như là một bảng tóm tắt thông tin về màu sắc cho một ảnh

màu bất kỳ.

Và việc tính lượt đồ màu này được tiến hành một cách rất nhanh chóng trong

ảnh mà chỉ qua một lần duyệt qua toàn bộ ảnh. Do đó ứng dụng vào việc tìm

kiếm ảnh sẽ có lợi rất lớn về mặt tốc độ.

Một số tính chất cần quan tâm của lượt đồ màu đối với vấn đề truy tìm ảnh:

- Việc tính lượt đồ màu của ảnh diễn ra rất nhanh chóng trong ảnh chỉ qua

một lần duyệt qua toàn bộ ảnh.

14

Luận văn tốt nghiệp đại học

- Lượt đồ màu tương đối bất biến đối với phép tịnh tiến, xoay ảnh, và nhất là

sự kéo nhỏ, kéo giãn, thay đổi kích thước của ảnh.

- Lượt đồ màu của một ảnh màu có thể là một cách miêu tả rất có ý nghĩa

cho việc truy tìm ảnh hay nhận dạng đối tượng trong ảnh

2.1.1. Lượt đồ màu thông thường RGB:

Đối với ảnh 256 màu, lượt đồ màu của ảnh tương đương với lượt đồ màu của

ảnh xám.

Đối với ảnh 24 bit màu, lượt đồ màu miêu tả khả năng kết nối về cường độ

của ba kênh màu R, G, B. Lượt đồ màu này được định nghĩa như sau:

h_R,G,B[r, g, b] = N*Prob{R=r, G=g, B=b}

trong đó N là số lượng điểm có trong ảnh.

Lượt đồ màu ở dạng này được tính bằng cách rời rạc hoá từng màu trong

ảnh, sau đó là đếm số điểm ảnh của mỗi màu.

Khi mà số lượng màu là có hạn, để thuận tiện hơn, người ta thường chuyển

đổi ba kênh màu thành một biến giá trị màu duy nhất. Cho một ảnh RGB,

một kiểu chuyển đổi thường được sử dụng là:

m= r+N_rg+N_rN_gb

trong đó N_r,N_glà số lượng bin của màu đỏ và màu xanh lục.

Điều này mang lại một lượt đồ đơn duy nhất như sau:

h[m] = N*Prob{M=m}

Một cách khác để tính lượt đồ màu của ảnh RGB là ta phân ra thành 3 lượt

đồ riêng biệt h_R[], h_G[], h_B[]. Khi đó, mỗi lượt đồ được tính bằng cách đếm

kênh màu tương ứng trong mỗi điểm ảnh.

2.1.2. Lượt đồ màu HSI:

Mô hình màu HSI có những ưu điểm lớn cho việc tìm kiếm hình ảnh dựa vào

nội dung và nhất là trong công việc tìm kiếm dựa vào màu sắc. Nhưng những

ảnh màu thông thường được lưu trữ ở dạng kỹ thuật số trong máy tính

15

Luận văn tốt nghiệp đại học

thường theo chuẩn RGB, do đó để có được ảnh màu HSI ta phải qua công

đoạn chuyển đổi. Chuyển từ hệ màu RGB sang hệ màu HSI là một thuật giải

có rất nhiều trong hầu hết những sách về xử lý ảnh cổ điển.

16

Luận văn tốt nghiệp đại học

Gọi R,G,B là giá trị nhập của RGB với giá trị trong khoảng

[0,1] hay [0,255]

I : Giá trị xuất của cường độ intensity [0,1]

S : Giá trị xuất của độ bảo hòa saturation [0,1]

H : Giá trị xuất của màu sắc hue [0,2Π]

R,G,B,H,I,S: Tất cả đều là những giá trị số thực.

Procedure RGB_to_HSI(in R,G,B; out H,S,I)

{

I:=Max(R,G,B);

Min:=Min(R,G,B);

If (I>=0) then

S:=(I-Min)/I;

Else S:=0;

If (S<=0) then

{

H:=-1;

Return;

}

Diff:= I-Min;

If (R=I) then H:=(Π/3)*(G-R) /Diff;

Else if (G=I) then H:=(2*Π/3)+Π/3*(B-R)/diff;

Else if (B=I) then H:=(4*Π/3)+Π/3*(R-G)/diff;

If (H<=0) H:=H+Π/2;

}

Thuật toán chuyển đổi từ RGB sang HSI

17

Luận văn tốt nghiệp đại học

Theo các phương pháp truyền thống, việc tạo lượt đồ màu chỉ đơn giản bằng

cách chia không gian màu thành những ngăn riêng biệt, sau đó đếm những

pixel có màu sắc phù hợp trong những ngăn này. Cách làm này rất đơn giản,

nhưng không phù hợp cho việc so sánh, tìm kiếm ảnh. Vì những thay đổi nhỏ

về điều kiện chiếu sáng, sự thay đổi về cường độ có thể gây nên những thay

đổi lớn trong lượt đồ màu. Do đó, hai ảnh rất giống nhau về màu sắc có thể

có lượt đồ màu hoàn toàn khác nhau.

Ví dụ :không gian màu HSI, thành phần Hue trong nhiều trường hợp mang

giá trị nhưng không thể hiện được màu sắc trong hiển thị: Khi giá trị

Intensity nằm trong khoảng 0-0.2, Hue mang bất kỳ giá trị nào thì màu mà

mắt người nhìn thấy vẫn là màu đen. Vì vậy đối với các cách tính lượt đồ

màu thông thường, điểm ảnh A có Hue bằng 2π , Intensity bằng 0.1 và điểm

ảnh B có Hue bằng π , Intensity bằng 0.1 sẽ nằm trong những bin khác nhau.

Nhưng thật ra, điểm ảnh A và điểm ảnh B đều có giá trị hiển thị là màu đen.

Lượt đồ HSI cải tiến:

Một phương pháp được đề suất để giải quyết cho trường hợp trên là ta

dựa vào Intensity để lọc trước những giá trị mà Hue không thể biểu thị được.

Sau đó dùng Saturation để lọc những giá trị có sắc màu xám. Phần còn lại

của không gian màu ta sẽ chia đều mỗi thành phần thành những khoảng nhất

định có sự tương đồng về màu sắc.

Để giá trị của lượt đồ màu HSI được tính một cách phù hợp nhất đối với việc

tìm kiếm, chúng ta cần chia nhỏ không gian 24 bit màu, tương ứng với 2²⁴

màu, xuống một con số có thể chấp nhận được. Một con số được đề nghị là 5

giá trị mức xám, 162 cho giá trị sắc màu, tổng cộng là ta chỉ cần lưu trữ 167

bin màu.

18

Luận văn tốt nghiệp đại học

Hue và Saturation khi Intensity < 0.33

Hue và Saturation khi Intensity > 0.33

2.2. Các loại độ đo màu:

Bước tiếp theo của quá trình tìm kiếm dữ liệu ảnh dựa vào nội dung là xác

định độ trùng khớp của hai lượt đồ màu vừa tính được ở bước trên. Do đó,

phát sinh ra một giá trị để biếu thị cho sự trùng khớp này, có nhiều cách để

tính giá trị này. Ta gọi những giá trị được tính từ những cách khác nhau này

là các loại độ đo màu.

Một cách đơn giản, độ đo màu là được coi một giá trị để biểu thị cho độ so

khớp sự trùng khớp của hai lượt đồ màu. Tùy theo từng trường hợp, từng loại

độ đo màu giá trị này có thể âm hoặc dương lớn hoặc nhỏ tương ứng với mức

độ giống nhau như thế nào của các loại lượt đồ màu.

19

Luận văn tốt nghiệp đại học

Mỗi loại độ đo màu có những ưu và khuyết điểm riêng, trong từng trường

hợp cụ thể.

Gọi h(I) và h(M) tương ứng là 2 lượt đồ màu của hai ảnh I và ảnh M. Khi đó

các loại độ đo màu được định nghĩa là một số nguyên (hoặc số thực) theo các

loại độ đo tương ứng như sau:

2.2.1. Độ đo khoảng cách min-max:

Được thực hiện dựa trên ý tưởng lấy phần giao của của hai lượt đồ cần so

sánh, ta sẽ được một lượt đồ, tính tổng các giá trị có được từ lượt đồ này cho

ta được độ đo min-max.

Đối với độ đo min: ta tính dựa vào giá trị min tại mỗi K bin.

K

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

min{h(I)[j],h(M)[j]}

∑

j=1

Đối với độ đo max: ta tính dựa vào giá trị max tại mỗi K bin.

K

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

max{h(I)[j],h(M)[j]}

∑

j=1

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

max( h(I)[i], h(M )[i])

Matching ( h(I), h(M)) =

∑

i

2.2.2. Độ đo khoảng cách euclid:

Đây là cách tính khoảng cách ơclit thông thường giữa các K bin:

K

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

(h(I) − h(M ))²

∑

j=1

Hoặc có thể là:

K

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

h(I) − h(M )

∑

j=1

20

Luận văn tốt nghiệp đại học

2.2.3. Độ đo khoảng cách toàn phương:

K

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

[h(i)-h(j)] a_ij[h(i)-h(j)]

∑∑

i=1 j=1

2.2.3. Độ đo có trọng số:

d_hist(I, Q) = (h(I) – h(Q))^TA(h(I) – h(Q))

trong đó, h(I) và h(Q) là những lượt đồ tương ứng của ảnh I và Q, và A là ma

trận đồng dạng KxK. Trong ma trận này, những màu mà rất giống nhau thì

gần với giá trị một, còn những màu rất khác nhau thì sẽ có giá trị gần với

không.

21

Luận văn tốt nghiệp đại học

Chương 2:

Tìm kiếm ảnh dựa vào vân

1. Vân

1.1. Vân là gì?

1.2. Một số loại vân tiêu biểu.

2. Tìm kiếm ảnh dựa vào vân

2.1. Mật độ của đường biên và hướng của biên

2.2. Phân hoạch vùng nhị phân cục bộ

2.3. Ma trận đồng hiện và đối tượng đồng hiện

2.4. Độ đo năng lượng của vân dựa vào luật đo

2.5. Tương quan tự động và quang phổ năng lượng

22