Tìm hiểu phương pháp tra cứu ảnh theo nội dung

§¹i häc Th¸i Nguyªn

Khoa c«ng nghÖ th«ng tin

Lª Hång Phong

T×m hiÓu ph-¬ng ph¸p tra cøu ¶nh

theo néi dung

LuËn v¨n th¹c sÜ c«ng nghÖ th«ng tin

Th¸i Nguyªn - 2010

§¹i häc Th¸i Nguyªn

Khoa c«ng nghÖ th«ng tin

Lª Hång Phong

T×m hiÓu ph-¬ng ph¸p tra cøu ¶nh

theo néi dung

Chuyªn ngµnh : Khoa häc m¸y tÝnh

M· sè : 60.48.01

LuËn v¨n th¹c sÜ c«ng nghÖ th«ng tin

Ng-êi h-íng dÉn khoa häc

PGS.TS Ng« Quèc T¹o

Th¸i Nguyªn - 2010

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

LỜI CAM ĐOAN

Tôi xin cam đoan toàn bộ nội dung bản luận vă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 luận văn này là

do tôi tự sưu tầm, tra cứu và sắp xếp cho phù hợp với nội dung yêu cầu của đề tài.

Nội dung luận văn này chưa từng được công bố hay xuất bản dưới bất kỳ

hình thức nào và cũng không được sao chép từ bất kỳ một công trình nghiên cứu

nào.

Tất cả phần mã nguồn của chương trình đều do tôi tự thiết kế và xây dựng,

trong đó có sử dụng một số thư viện chuẩn và các thuật toán được các tác giả xuất

bản công khai và miễn phí trên mạng Internet.

Nếu sai tôi xin tôi xin hoàn toàn chịu trách nhiệm.

Thái Nguyên, tháng 10 năm 2010

Người cam đoan

Lê Hồng Phong

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

DANH MỤC CÁC CHỮ VIẾT TẮT

Chữ

viết tắt Dạng đầy đủ Nghĩa tiếng Việt

PWT

Pyramid-structured Wavelet

Transform

Biến đổi dạng sóng kiểu hình

chóp

TWT

Tree-structure Wavelet Transform Biến đổi dạng sóng kiểu hình

cây

SAR Simultaneous Auto Regressive Tự thoái lui đồng thời

MRF Markov Random Field Trƣờng ngẫu nhiên Markov

DC Direct Current Thành phần một chiều

AVR Average Rank Thứ hạng trung bình

MRR Modified Retrieval Rank Thứ hạng tra cứu sửa đổi

ANMRR

Average Normalized Modified

Retrieval Rank

Thứ hạng tra cứu sửa đổi và

chuẩn hoá trung bình

GCH Global Color Histogram Biểu đồ màu toàn cục

LCH Local Color Histogram Biểu đồ màu cục bộ

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1

MỞ ĐẦU

Những năm gần đây, ảnh số ngày càng thu hút đƣợc sự quan tâm của nhiều

ngƣời, một phần là do các thiết bị thu nhận ảnh số ngày càng phổ biến và có giá cả

phù hợp, cho phép nhiều ngƣời có thể sở hữu và sử dụng. Mặt khác các công nghệ

chế tạo thiết bị lƣu trữ luôn đƣợc cải tiến để cho ra đời các thiết bị lƣu trữ có dung

lƣợng lớn và giá thành hạ làm cho việc lƣu trữ ảnh dƣới dạng các file trở nên phổ

biến. Thêm nữa là sự phát triển của mạng Internet làm cho số lƣợng ảnh số đƣợc

đƣa lên lƣu trữ và trao đổi qua Internet là rất lớn.

Tuy nhiên khi số lƣợng ảnh đƣợc lƣu trữ trở nên rất lớn thì vấn đề là phải có

những phƣơng pháp tổ chức cơ sở dữ liệu ảnh tốt cùng với những kỹ thuật tìm

kiếm, tra cứu ảnh hiệu quả, có độ chính xác cao và có hiệu năng tốt.

Việc tìm kiếm đƣợc một bức ảnh mong muốn trong hàng triệu bức ảnh thuộc

đủ loại chủ đề khác nhau là rất khó khăn.

Khi số lƣợng ảnh trong một bộ sƣu tập còn ít, việc nhận diện một bức ảnh

hay việc so sánh sự giống và khác nhau giữa nhiều bức ảnh có thể thực hiện đƣợc

bằng mắt thƣờng, tuy nhiên khi có số lƣợng rất lớn ảnh thì việc so sánh bằng mắt

thƣờng là rất khó khăn, đòi hỏi phải có những phƣơng pháp hiệu quả và chính xác

hơn.

Trong thực tế, bài toán tra cứu ảnh số có rất nhiều ứng dụng quan trọng. Ví

dụ nhƣ trong lĩnh vực ngân hàng việc so sánh chữ ký của khách hàng với mẫu chữ

ký đã đƣợc lƣu trữ sẵn có thể thực hiện rất nhanh và chính xác nếu có đƣợc một

phần mềm so sánh mẫu chữ ký tốt. Thực tế hiện nay tại các ngân hàng ở Việt nam

ngƣời ta vẫn phải sử dụng phƣơng pháp so sánh bằng mắt thƣờng vì việc so sánh

chữ ký bằng phần mềm vẫn chƣa thực hiện đƣợc. Một ví dụ khác là bài toán quản lý

biểu trƣng (logo) trong lĩnh vực sở hữu trí tuệ. Khi một đơn vị muốn đăng ký logo

riêng cho đơn vị của mình thì cơ quan quản lý phải tiến hành đánh giá xem mẫu

logo đó đã đƣợc sử dụng hay chƣa hoặc có tƣơng tự với mẫu logo nào đó đang đƣợc

sử dụng hay không. Trong trƣờng hợp này nếu sử dụng mắt thƣờng để duyệt thì sẽ

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

2

tốn rất nhiều thời gian, nếu có các phần mềm cho phép tìm kiếm trong cơ sở dữ liệu

ảnh có sẵn những biểu trƣng tƣơng tự với biểu trƣng mẫu thì việc đánh giá sự tƣơng

tự sẽ dễ dàng hơn nhiều.

Các ứng dụng phức tạp hơn nhƣ so sánh mẫu vân tay, tìm kiếm ảnh tội phạm

v.v... là những bài toán tra cứu ảnh đƣợc áp dụng trong ngành khoa học hình sự.

Vì vậy, việc xây dựng các hệ thống tìm kiếm và xếp hạng ảnh là rất cần

thiết và thực tế đã có nhiều công cụ tìm kiếm ảnh thƣơng mại xuất hiện. Các công

cụ tìm kiếm ảnh thƣờng dựa vào hai đặc trƣng chính là văn bản đi kèm ảnh hoặc nội

dung ảnh.

Trƣớc năm 1990, ngƣời ta thƣờng sử dụng phƣơng pháp tra cứu ảnh theo văn

bản (Text Based Image Retrieval). Theo cách này ngƣời ta sẽ gán cho mỗi bức ảnh

một lời chú thích phù hợp với nội dung hoặc một đặc điểm nào đó của ảnh, sau đó

việc tra cứu ảnh đƣợc thực hiện dựa trên những lời chú thích này. Phƣơng pháp này

khá đơn giản. Tuy nhiên, việc tìm kiếm chỉ dựa vào văn bản đi kèm còn có nhiều

nhập nhằng giữa nội dung hiển thị ảnh và nội dung văn bản đi kèm ảnh trong quá

trình tìm kiếm. Ví dụ, với truy vấn “Apple”, máy tìm kiếm khó phân biệt đƣợc

ngƣời dùng muốn tìm hình ảnh quả táo hay logo của hãng Apple. Bên cạnh đó

phƣơng pháp tra cứu ảnh dựa theo văn bản không thể áp dụng để tra cứu các cơ sở

dữ liệu ảnh có số lƣợng ảnh lớn và kết quả tra cứu thì mang tính chủ quan và cảm

ngữ cảnh. Một số công cụ tìm kiếm ảnh theo văn bản đi kèm nhƣ: google Image

Search, Yahoo!, MSN,…

Một trong những phƣơng pháp đƣợc nhiều ngƣời quan tâm nghiên cứu hiện

nay là phƣơng pháp “Tra cứu ảnh dựa theo nội dung” (Content Based Image

Retrieval). Ý tƣởng phƣơng pháp này là trích chọn các đặc điểm dựa vào nội dung

trực quan của ảnh nhƣ màu sắc, kết cấu, hình dạng và bố 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 cơ sở dữ liệu ảnh. Một số hệ thống

tra cứu ảnh nổi tiếng nhƣ QBIC (IBM), Virage (Virage Inc.), Photobook (MIT),

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

3

VisualSEEK (Columbia University)... đã áp dụng khá thành công phƣơng pháp tra

cứu này. [7],[16],[17]

Nội dung của đề tài này giới thiệu cơ sở lý thuyết và các ứng dụng chính của

một số phƣơng pháp tra cứu ảnh, trong đó đi sâu vào giới thiệu phƣơng pháp tra cứu

ảnh theo nội dung. Trên những cơ sở đó tiến hành thử nghiệm một phƣơng pháp cụ

thể để xây dựng một chƣơng trình phần mềm tra cứu ảnh cho phép đọc 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 theo hai đặc điểm là hình dạng và màu sắc của ảnh.

Nội dung luận văn ngoài phần mở đầu gồm có ba chƣơng:

Chương 1: Trình bày tổng quan vấn đề tra cứu ảnh, giới thiệu sơ lƣợc một số

phƣơng pháp tra cứu ảnh và một số hệ thống tra cứu ảnh tiêu biểu.

Chương 2: Giới thiệu chi tiết về một số phƣơng pháp trích chọn đặc trƣng

ảnh.

Chương 3: Giới thiệu một ứng dụng của phƣơng pháp tra cứu ảnh theo nội

dung; những hạn chế và khả năng mở rộng của chƣơng trình ứng dụng đó.