ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CÔNG NGHỆ
ĐINH ĐỨC HÙNG
NGHIÊN CỨU MỘT SỐ KĨ THUẬT Hỗ TRỢ
• m m
TÌM KIẾM ẢNH THEO NỘI DUNG
Chuyên ngành: Công nghệ Thông tin
Mã số: 1.01.10
LUẬN VĂN THẠC sĩ
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS TS NGÔ QUỐC TẠO
Hà n ộ i-2003
ị i)ĨW
HOC C.UÓCGiA MA
2
MỤC LỤC
LỜI CẢM ƠN

.

.

1
Chương 1 TỔNG QUAN VỀ TRA ctnu ẢNH
.

5
1.1. Giới thiệu về xử lí ảnh

.


2.2. Phạm vi của tìm kiếm ảnh theo nội 12
2.2.7. P hân lo ạ i th eo ứng dụ ng 12
2.2.2. V ùng ảnh và lỗ hổng cảm g iác 13
2 .2 .3. T r i thứ c vù n g

.
14
2.3. Biểu diễn nội dung ảnh, xử lí ảnh 16
2 .3 .L Xử lí m àu s ắ c 17
2 .3.2 . Xử lí hình d ạng cục bộ
17
2 .3 .3. X ử lí cấu trú c ả n h 18
2 3 .4 . K ết lu ậ n 18
2A.
Thể hiện nội dungỉ Các đặc trư n g .""""
.

18
2 .4.1 . G ộp d ữ liệ u 19
2 .4.2 . C á c đ ặ c trư n g 19
2 .4 .3 . M ô tả cấ u tr ú c 21
2.5. Sự thể hiện và độ tương tự ••••••••••••••••••••

.
22
2 .5 .1 . T h ể h iệ n n g ữ n g h ĩa 22
2.5.2. Đ ộ tương tự 22


.

.

.

3.2. Kĩ thuật phân đoạn ảnh sử dụng kì vọng lớn nhất

3 .2.1. T rích chọn cá c đ ặc trư n g
3 .2 .2 . N h óm các điểm ản h thành các vù n g
3 2 3 . B iểu d iễn các v ù n g
.

3.3. Kĩ thuật so khớp theo qui hoạch động
.

.

3 .3.1 . B iểu diễn h ình d ạng trong D P

3 3 2 , C ác trường hợp cần so kh ớ p
3 .3.3 . B ảng qui ho ạch động (DP ta b le )

3 .3 .4 . Đ ánh giá so khớp bằ ng hàm kh oả ng c á c h

.

3 3 .5 . C ác yếu tố ảnh hưởng đến giá so k h ớ p


41
41
42
43
4 5
46
50
50
50
52
52
57
58
60
4
DANH MỤC BẢNG BIỂU VÀ HÌNH VẼ
Bảng 1 : Ba sự phân loại theo mục đích của các hệ thống tìm kiếm ảnh
theo nội dung 13
Bảng 2: So sánh vùng rộng và vùng h ẹ p
14
Hình 1 : Các giai đoạn chính trong xử lí ảnh
.

5
Hình 2: Các thành phần của một hệ thống xử lí ảnh 6
Hình 3: Các nguồn tri thức chung theo thứ tự bằng nhau
15
Hình 4: Các module xử lí ảnh 16
Hình 5: Các cách khác nhau để nhóm dữ liệu ảnh 18
Hình

Hình 1: Các giai đoạn chính trong xử lí ảnh
• Thu nhận ảnh: ảnh có thể được thu nhận qua camera nó có thể là tín
hiệu tương tự cũng có thể là tín hiệu số. Ngoài ra ảnh cũng có thể được
thu nhận từ vệ tinh thông qua các bộ cảm ứng (sensor), hoặc tranh ảnh
được quét bằng scanner,
• Ảnh sau khi được thu nhận có thể được số hoá để lưu trữ hoặc sẽ được
♦ 攀 • • •
phân tích trong giai đoạn tiếp theo (phân tích ảnh. Phân tích ảnh gồm
6
nhiẻu giai đoạn nhỏ hơn: tăng cường, nâng cao chất lượng ảnh (khắc
phục những thiếu xót của quá trình thu nhận ảnh như： nhiểu, méo.v.v)，
làm nổi bật những đặc trưng chính của ảnh hoặc làm cho ảnh trở về tình
trạng ban đầu.v.v.x tiếp theo là việc phát hiện các đặc trưng của ảnh
như： biên, vùng ảnh，trích chọn các đặc trưng của ảnh.
• Cuối cùng ảnh sẽ được nhận dạng, phân lớp hoặc phục vụ cho các mục
đích khác nhau.
Đé xử lí các quá trình trên đây thì m ột hệ thống xử lí ảnh bao gồm m ột
số thành phần sau đây (phần cứng) [
1
]:
Hình 2: Các thành phần của m ột hệ thống xử lí ảnh
• Camera: cũng giống như con mắt của hệ thống. Camera có hai loại: loại
CCIR ứng với chuẩn CCIR quét ảnh vớ i tần số 1/25，m ỗi ảnh gồm 625
dòng; loại CCD gồm các photo điố t tương ứng m ột cường độ sáng tại
m ột điểm ảnh ứng với m ột phần tử ảnh (pixel).
• Bộ xử lí tương tự (analog processor) thực hiện các chức năng:
- Chọn camera thích hợp nếu hệ thống có nhiều camera.
一 Chọn màn hình hiển th ị tữi hiệu*
« • • •
7

• Biến đổi ảnh (Image Transform ) nói tới một lớp các ma trận đơn vị và
các k ĩ thuật dùng để biến đổi ảnh: Biến đổi Fourier, Sin, Cosin, tích
Kronecker, biến đổi Karhumen Loeve.v.v.
• Phân tích ảnh: liên quan đến việc xác đinh các độ đo đinh lượng của
m ột ảnh để đưa ra một mô tả đầy đủ về ảnh. Có nhiều k ĩ thuật hổ trợ
phân tích ảnh: xác định biên của ảnh, các k ĩ thuật lọc vi phân, dò theo
quy hoạch động, các k ĩ thuật phân vùng ảnh dựa trên các tiêu chuẩn
đánh giá về màu sắc，cường độ.v.v.
• Nhận dạng ảnh: quá trình này liên quan đến các mô tả đối tượng mà
người ta muốn đặc tả nó. Nhận dạng ảnh thường đi sau quá trình trích
chọn các đặc trưng chủ yếu của đối tượng.
• Tra cứu ảnh (hay tìm kiếm ảnh): để có thể tra cứu được ảnh cũng cần
mô tả được ảnh như trong quá trình nhận dạng ảnh. Tra cứu ảnh có
nhiệm vụ tìm được ảnh theo yêu cầu của người sử dụng. Nhiều hệ thống
nhận dạng và tra cứu ảnh đã được nghiên cứu rất thành công trong
những năm gần đây [13].
• Nén ảnh: nhằm giảm kích cỡ ảnh để có thể truyền tải ảnh qua mạng hay
để giảm bộ nhớ lưu trữ giữ liệu ảnh [
1
].
1.2.
Giới thiệu về tìm kiếm ảnh.
Gần đây có một sự bùng nổ mạnh mẽ về thông tin, nhiều cơ sở dữ liệu
đã được xây dựng [13]. Nó là nguồn tài sản vô cùng quý giá đối với nhiều
9
ngành kinh tế cũng như nhiều ngành khoa học k ĩ thuật. Tuy nhiên, để có thể
sứ đụng m ột cách hiệu quả những cơ sở dữ liệu ảnh này thì cần phải có những
phương pháp đồng bộ bao gồm tất cả các khâu trong quá trình xử lí ảnh.
• X ử lí các nhiẻu méo trong quá trình thu nhận ảnh để ảnh lưu trữ trung
thực nhất với hình ảnh ban đầu. Đồng thời đưa ra các thuật toán tố i ưu

theo nội dung là việc tìm kiếm ảnh theo những đặc trưng thuộc về ảnh mà ta
g?i là nội dung: theo vùng, theo đối tượng trong ảnh, theo sơ đồ mức xám.v.v.
1.3. Mục tiêu của luận văn
Trong khuôn khổ m ột luận văn cao học và m ột khoảng thời gian hạn
chế chúng tôi không đặt ra mục tiêu quá cao đối với m ột vấn đề quá lớn. Luận
vin chỉ đề cập đến m ột số vấn đế dưóiđây:
• Nghiên cứu, phân tích và đưa ra cái nhìn chung nhất vể tìm kiếm ảnh
theo nội dung và các phương pháp tìm kiếm ảnh theo nội dung trong
những năm gần đây [13] trên m ột số khía cạnh sau: các đặc trưng, kiểu
loại ảnh, chỗ hổng cảm ứng và chỗ hổng ngữ nghĩav
• Tìm hiểu các hệ thống tra cứu ảnh theo: các đặc trưng toàn cục, các
điểm nổi bật, đặc trưng hình dạng, kết hợp các đấu hiệu và cấu trúc, độ
tương tự của các ảnh và các đối tượng trong ảnh. Tương tác của người
sử dụng và hệ thống.
• Nghiên cứu đánh giá phương pháp phân đoạn ảnh Blobw orld và sử dụng
k ì vọng cực đại để truy vấh ảnh; phương pháp tìm kiếm ảnh bằng qui
hoạch động [1 3]
，[8 ]，[5].
• M ột số thử nghiệm của các thuật toán đưa ra.
• Việc cải tiến, đưa ra thuật toán và ứng dụng vào thực tế trong các bài
toán Nhận dạng và tìm kiếím ảnh dành cho những nghiên cứu lớn hơn.
11
1A Kết luận
Trong chương 1 chúng tôi giới thiệu một số khái niệm về xử lí ảnh, khái
quát về một hệ xử lí ảnh. Trong chương này chúng tôi cũng giới thiệu tổng
quát vế một số vấn đề trong tra cứu ảnh và mục tiêu luận văn cần đạt được.
12
MỘT SỔ K ĩ THUẬT CHUNG VỂ TÌM KIẾM ẢNH
THEO NỘI DUNG
2

đăc tả
Một đối tượng phức tạp
từ một lớp được đặc tả
Không định nghĩa tại vị
tríbắỉđẩu
Truy vấn bằng ví dụ
1 …N đối tượng
1 N đối tượng với các
nhăn lớp
N đối tượng cộng với
sự kết hợp
Độ tương tự
Dựa trên đặc
trưng
Theo lớp
Đặc tả phiên
Các
sự kiện trong
F-
không gian.
Xáp xỉ truy vấn
Thành phẩn phân lớp
Các cụm
Phản hổi
Theo vị trí thứ tự
trên độ tương tự
Khả năng trên các lớp
thành phần
Phản hỗi thích đáng
trên các giá tri kết hợp

đề đó ỉà sự không chắc chắn trong trạng thái của đối tượng. Chỗ hổng cảm
giác là m ột thiếu xót khi một tri thức chính xác của điều kiện thu nhận ảnh bị
mất. Hầu hết các thiếu xót của các hệ thống tìm kiếm ảnh gần đây xuất phát từ
việc không tìm ra chỗ hổng ngữ nghĩa và khắc phục những hậu quả của nó cho
hộ thống. X é t trên khía cạnh người sử dụng ta có thể coi c h ỗ hổn g cả m giá c là
sự th iếu s ự trù n g kh ớp g iữa thô ng tin m à ng ười ta có th ể trích ra từ c ơ s ỏ d ữ
liệu nhìn th ấ y và s ự b iễu diễn cá c d ữ liệu đó d o người s ử dụng đưa ra.
So sánh các vùng rộng và hẹp trong tìm kiếm ảnh
Hẹp——
Rộng
Sự biến thiên nội dung
thấp Cao
Các nguồn tri thức
đươc đăc tả Chung
Các
ngữ nghĩa
đổng nhất
không đổng nhất
Sư chính xác
có thể không thể
Thể hiên nôidung^
khách quan chù quan
Ngoại cảnh và cảm ứng
có thể đươc điốu khiển
không biết
Hướng ứng dụng
đươcđăctả Chung
Kiều ứng dụng
chuyên biệt
Phổ dụng

• Các quy tắc vật lí diễn tả sự bằng nhau và khác nhau của các ảnh dưới
sự khác nhau về tri giác và đặc tính bể mặt của đối tượng.
• Các quy tắc về cấu trúc và tính chất hình học diễn tả sự bằng nhau và
sự khác nhau của các đặc trưng trong không gian.
• Các quy tắc dựa trên các phạm trù để mã hoá các đặc điểm thông
thường vào lớp z của không gian tất cả các k í hiệu z .
• Các quy tắc bằng nhau và khác nhau dựa trên văn hoá.
N hư vậy: Điểm chủ chốt trong tìm kiếm ảnh theo nội dung là tìm ra sự
tương tự về nội dung của ảnh cần tìm trong cơ sở dữ liệu. Các ứng đụng của
tìm kiếm ảnh theo nộ i dung theo được phân chia thành: tìm kiếm đích, tìm
kiếm theo phạm trù và tìm kiếm kết hợp.
Hình 3: Các nguồn tri thức chung theo thứ tự bằng nhau
16
Chỗ hổng cảm giác giữa các tính chất trong m ột ảnh và các đặc điểm
của đối tượng ảnh hưởng lớn đến tìm kiếm ảnh theo nội dung. Các hệ thống
tìm kiếm ảnh theo nội dung phải có khả năng khắc phục chỗ hổng ngữ nghĩa
giữa các đặc trưng và làm giàu ngữ nghĩa của người sử dụng.
Việc phân tích các đặc điểm của vùng ảnh, vùng tri thức và các kiểu sử
dụng các yếu tố sẵn có để xác định chức năng của m ột hệ thống tìm kiếm ảnh
theo nội dung.
2.3. Biểu diễn nội dung ả n h，xử lí ảnh*
Đầu tiên, hãy thảo luận vể các toán tử xử lí ảnh, biến đổi dữ liệu ảnh
thành m ột mảng dữ liệu không gian khác, xem hình 4.
Hình 4: Các module xử lí ảnh
Các phương pháp được phân chia theo màu cục bộ, cấu trúc cục bộ，tính
chất hình học cục bộ. Công thức biến đổi tổng quát như sau:
f ( x ) = g o i(x ) (2.1)
Trong đó /(X) là ảnh, g là một toán tử trên các ảnh, f (jc) là ảnh kết
quả. Ở đây, có thể sử dụng bất biến như m ột công cụ để xử lí những hiện
tượng bị méo trong thông tin ảnh [3]. Hai đối tượng tị nào đó là tương đương

hàm màu theo hướng cũng được sử dụng, ứng dụng trong các máy dò ảnh.
L í thuyết vể không gian tỉ lệ cung cấp cơ sở phát hiện các chi tiế t chuứì
xác trên bất kì tỉ lệ nào. Hình dạng cục bộ và thông tin cường độ cho điểm
nhìn và tìm kiếm đối tượng bất biến.
K ết hợp giữa hình dạng cục bộ và màu sắc trong thể hiện bất biến là
m ột sự kết hợp hữu ích; trong đó màu sắc ở trong và ngoài của độ cong lớn
nhất trong cạnh màu được lưu trong đối tượng nhận dạng.
m ：r t s v i U ' r î H
18
2.3.3. Xử lí cấu trúc ảnh
Các cấu trúc ảnh được tạo bởi nhiều thành phần, số các thành phần này
thường lớn hơn rất nhiểu con số nhận được khi các đối tượng bị tách ra. Các
thành phần có thể được thay thế bởi nhiều hoặc ít hơn một cách ngẫu nhiên.
Trong khuôn khổ tìm kiếm ảnh, các nghiên cứu tập trung vào các phương pháp
sinh ra hay phân tích sự biểu th ị đặc điểm từng phần.
2.3.4. Kết luận
X ử lí ảnh nhằm mục đích nâng cao chất lượng thông tin ảnh để tìm
kiếm ảnh theo nội dung. Trong đó, xử lí màu sắc ảnh để giảm các lỗi do điéu
kiện ngẫu nhiên gây ra (ví dụ chỗ hổng cảm giác), ứ ig dụng thể hiện hình học
thu được từ lí thuyết không gian tỉ lệ cho thấy m ột góc độ và cảnh độc lập với
tập điểm nổi bật vì vậy sẽ có cách tìm tính tương tự của ảnh trén các vùng
hoặc m ột vài điểm chứa thông tin*
Thảo luân ờ trên đã phân biệt màu sắc, hình học cục bộ và cấu trúc. Các
vùng đồng nhất được biểu diễn như các tập hợp của các elipsolid của các màu
và cấu trúc đồng nhất. Trong tìm kiếm ảnh theo nội dung bước đầu tiên là tạo
nên khả năng phân biệt các tính chất bất biến.
2.4. Thể hiện nội dung: Các đặc trưng
Gộp ảnh
■ phân <ỉoạiì 0iạob
- — ■夢 Phao doạ» yếu

được gán m ột nhãn.
2.4.2* Các đặc trưng
• Các đặc trưng toàn cục: là các đặc trưng được tính toán từ toàn bộ
ảnh. Đặc trưng tích luỹ tính theo công thức sau:
2.4.1. Gộp dữ liệu
20
F j - ỵ h o f( x ) (2.4)
h
Trong đó z là toán tử kết hợp; Fj là tập các đặc trưng tích luỹ hoặc là
tập các đặc trưng tích luỹ đánh số trong m ột biểu đồ mức xám; Tj là phần phân
chia qua giá trị Fj được tính. Toán tử/ỉ là trọng số liê n quan.
Để tính các đặc trưng tích luỹ có thể sử dụng biểu đồ mức xám. Nó
cũng tỏ rõ m ột số ưu điểm : không cần thông tin vế v ị trí đối tượng trong ảnh,
thay đổi rất chậm so vớ i các tiêu chuẩn khác. Tuy nhiên, đối với cơ sở dữ liệu
lớn dùng biểu đồ mức xám đơn giản không thể phân biệt được. Để giải quyết
vấn để này người ta đã thêm vào cấu trúc cục bộ, đặc trưng cục bộ, cạnh định
hướng, khoảng cách cục bộ, biểu đồ mức xám, các đặc trưng hình học.
• Các đặc trưng Dổi b ật: Để tránh sự các nhược điểm của phân đoạn
mạnh là sử dụng phân đoạn yếu. Đ iều này đã dẫn đến việc gộp dữ liệu thành
các vùng và việc lựa chọn phải dựa trên các đặc trưng nổi bật của vùng. Các
dặc trưng nổi bật có thể được đưa ra trong phương trình tổng quát sau:
FẢ x ) = A hof( x) (2-5)
Tj
Trong đó
, 八
là một toán tử lựa chọn cục bộ, h cho ta max của trường
ảnh được xử lí f(x). Vùng Tj được xét trên giá trị củâ Fj được tìm trên toàn ảnh.
Thông tin của ảnh chỉ được thể hiện trong m ột số giá trị đặc trưng nổi
bật. Những giá trị này được lưu trữ để tìm kiếm ảnh. N goài ra những giá trị bất
biến cũng cần được ghi lại và được coi như các điểm nổi bật.

thứ tự của các giá trị đặc trưng, hoặc mối liên hệ giữa tập các điểm hoặc tập
các đối tượng.
Quá trình trên được biểu diẻn bằng phương trình sau:
2 2
Trong đó
Tjtk
là thành phần thứ
k
của đối tượng thứ ý, và
H jtk
là một mối
liên hệ không gian diễn tả đối tượng ý trong k thành phần.
2.5, Sự thể hiện và độ tương tự
2.5.1. Thể hiện ngữ nghĩa
Trong tìm kiếm ảnh theo nội dung sẽ rất hữu ích nếu đưa vào sự thể
hiện ngữ nghĩa của các đặc trưng thu được từ ảnh. Đ ặ c trư ng ng ữ nghĩa nhằm
vào mục đích mã hoá sự thể hiện của ảnh mà thích đáng với các ứng dụng.

Giả sử m ột véc tơ đặc trưng F thu được từ ảnh /• Đ ố i vớ i những sự thể hiện
ngữ nghĩa z thu được từ tập tất cả các sự thể hiện hiện z ，ta có xác suất điều
kiện:
P^P(z\ F) (2.10)
M ột đặc trưng ngữ nghĩa mạnh với sự thể hiện Zj sẽ có xác suất được
tữih bằng P (z I F) = - Zj). Nếu m ột đặc trưng không mang ngữ nghĩa thì ta
có P (z I F) = P (z) độc lập với giá trị đặc trưng.
2.5.2. Độ tương tự
• Độ tương tự giữa các đặc trưng: Để gán ý nghĩa cho một tập đặc
trưng có thể sử dụng hàm tương tự. Khi tìm ảnh /*^(x) trong số các thành phần
của cơ sở dữ liệu ảnh,
id(x),

trưng cấu tróc cho bởi:
Sqd: s (H q
，
H dl (2.14)
Cây thứ tự được so sánh với mục đích tìm kiếm bằng việc chuyển chúng
thành các xâu. M ột độ đo tương tự dựa trên khoảng cách cho ta độ đo tương tự
giữa các lá tương ứng trong cây.
K h i các ảnh được biến đổi thành các vùng đồng nhất nhằm tìm kiếm
dựa trên cấu trúc, màu sắc. Các vùng được chuyển thành m ột xâu trong từ điển
thị giác. Các xâu được biểu diễn bằng các biểu đồ mức xám liên vùng F (/j/).
Trong quá trình truy vấn
，
độ tương tự giữa q d được cho bởi
F9Frf，đó là từng thành phần tương ứng của các biểu đồ mức xám
theo thứ tự vùng.
• Đ ộ tương tự giữa các đặc trưng nổi bật: các đặc trưng nổi bật được
sử dụng thu được thông tin trong ảnh. Sau đó độ tương tự có thể được tữih theo
các véc tơ đặc trưng nổi bật:
24
Trong đó và ¥d là các véc tơ đặc trưng nổi bật và g ỉà một hàm đơn
điệu tối ưu. M ộ t độ đo tương tự giữa các giá trị đặc trưng để đo kết quả từ các
điểm màu từ sự phân đoạn yếu bao gồm m ột khoảng cách Mahalanobis giữa
các véc tơ đặc trưng của màu sắc, cấu trúc, v ị trí, diện tích, độ lệch tâm và
hướng của 2 elip. Nếu các đặc trưng của elip được thể bằng véc tơ F ，khoảng
cách giữa p q được cho bởi dq d = [(F q - F^)r (¥q - F^)]^ trong đó z là ma
trận trọng số đường chéo được đặt bởi người sử dụng. Độ tương tự giữa hai
điểm màu được định nghĩa là Sqd: exp(- tí^ /2 ).
V ới các điểm nổi bật được tính theo biểu đồ mức xám, độ tương tự giữa
các biểu đồ mức xám F^và xác đinh sự có mặt của các điểm nổi bật được
tính như sau:

5)) + W 2exp(-(i(5^)). Mục đích cùa độ đo này là tìm ra tất cả các
vùng mà tương tự với hai truy vấn điểm được đặc tả.
2.5.3. Thảo luận về sự thể hiện và độ tương tự
Chỉ kh i ảnh tự nó đã cho ta m ột sự thể hiện rõ, các hệ thống dựa trên
nội dung sẽ có được thông tin trong trường hợp lí tưởng. M ộ t sự thể hiện ngữ
nghĩa mạnh xuất hiện khi một dấu hiệu có thể được đồng nhất trong ảnh. Các
ngữ nghĩa yếu phụ thuộc vào sự phân loại không chính xác đã được kết luận
bởi độ đo tương tự thích hợp tương tác trực tuyến.
Đ ộ tương tự là m ột trong những sự thể hiện của ảnh dựa trên sự khác
nhau với các ảnh khác. Đ ối với m ỗi m ột kiểu đặc trưng khác nhau độ đo tương
tự là cần thiết vì ảnh hưởng độ đo này đến tìm kiếm .
2.6.
Tương tác
Trong tìm kiếm ảnh theo nội dung, tương tác là m ột sự ảnh hưởng qua
lại giữa người sử dụng, các ảnh, và sự thể hiện ngữ nghĩa của chúng.
2.6A.
Không gian truy vấn
K hông g ia n ư u y vấn Q là m ộ t m ụ c tiêu p h ụ th uộc 4 thành phầ n
{IqJq^q^Zq}. Trong đó: Iq^là sự lựa chọn ảnh từ tập I; Fq^c F là sự lựa chọn đăc
trưng từ Iq
；
ôq^là hàm tương tự; ZqJZ z là tập các nhãn,
M ột truy vấn Q = ự QyFQìSQìZQ} là m ột phần tử của không gian truy vấn.
Các truy vấn được phân thành các loại sau: