Tra cứu ảnh dựa trên lưới và ứng dụng
Lê Thị Lan Anh
Trường Đại học Công nghệ
Luận văn Thạc sĩ ngành: Hệ thống thông tin; Mã số: 60 48 05
Người hướng dẫn: PGS.TS. Ngô Quốc Tạo
Năm bảo vệ: 2012
Abstract. Giới thiệu về tra cứu ảnh, các đặc trưng của ảnh, cấu trúc hệ thống tra cứu
ảnh theo nội dung và một số lĩnh vực ứng dụng của tra cứu ảnh. Trình bày một số
phương pháp trích chọn đặc trưng hình ảnh như màu sắc, kết cấu, hình dạng … Tập
trung tìm hiểu kỹ thuật tra cứu ảnh dựa trên lưới. Giới thiệu phương pháp tra cứu
ảnh kết hợp giữa đặc trưng màu sắc và hình dạng có sử dụng kỹ thuật lưới vùng. Từ
cơ sở lý thuyết đã xây dựng ở chương 3 đưa ra ý tưởng, thuật toán xây dựng chương
trình mô phỏng tra cứu ảnh dựa trên lưới.
Keywords. Hệ thống thông tin; Kỹ thuật xử lý ảnh; Hình ảnh; Công nghệ thông tin
Content
MỞ ĐẦU
Ngày nay, bên cạnh sự phong phú của kho dữ liệu văn bản thì kho dữ liệu ảnh cũng
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 tra cứu một
vài bức ảnh nào đó trong một cơ sở dữ liệu có 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.
Do đó, việc xây dựng các hệ thống tra cứu là rất cần thiết. Các công cụ tra cứu ả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. Tra cứu ảnh
theo nội dung đã nhận được nhiều sự quan tâm của các nhà khoa học.
Tra cứu ảnh dựa trên lưới là một hướng nghiên cứu mới. Một số phương pháp tra cứu
ảnh dựa trên lưới có thể sử dụng lưới kết hợp với đặc trưng hình dạng hoặc đặc trưng màu sắc
trong quá trình tra cứu.
Nội dung luận văn giới thiệu một số vấn đề liên quan đến tra cứu ảnh, tra cứu ảnh
theo nội dung và một số phương pháp trích chọn đặc trưng hình ảnh. Nghiên cứu phương
pháp tra cứu ảnh dựa trên lưới và tìm hiểu phương pháp kết hợp đặc trưng màu sắc với đặc
trưng hình dạng. Cuối cùng đi xây dựng chương trình ứng dụng mô phỏng phương pháp tra
cứu ảnh dựa trên lưới.
Nội dung luận văn gồm có bốn chương:
Chƣơng 1: Tổng quan về tra cứu ảnh.
Chƣơng 2: Một số phương pháp trích chọn đặc trưng hình ảnh.
Chƣơng 3: Tra cứu ảnh dựa trên lưới.
Chƣơng 4: Thiết kế và cài đặt chương trình tra cứu ảnh dựa trên lưới.
Chƣơng 1: TỔNG QUAN VỀ TRA CỨU ẢNH
1.1 Giới thiệu chung
Quá trình thực thi của hệ thống xử lý ảnh bao gồm:
- Thu nhận ảnh.
- Số hóa ảnh.
- Phân tích ảnh.
- Nhận dạng ảnh.
Tra cứu ảnh là một quá trình tìm kiếm ảnh trong một cơ sở dữ liệu ảnh những ảnh
thoả mãn một yêu cầu nào đó.
Khi tra cứu ảnh người ta có thể sử dụng phương pháp tra cứu ảnh theo văn bản đi kèm
hay theo nội dung ảnh.
Tra cứu ảnh theo nội dung được thực hiện theo nguyên tắc sử dụng các đặc trưng mức
thấp của ảnh như màu sắc, kết cấu, … để biểu diễn ảnh. Sau đó tính độ tương tự giữa ảnh cần
tìm và ảnh trong cơ sở dữ liệu để đưa ra kết quả là bức ảnh có độ tương tự cao nhất.
1.2 Các đặc trƣng mức thấp của ảnh
Đặc trưng mức thấp của ảnh là một vài đặc điểm thu nhận được từ một bức ảnh như:
Hình dạng, màu sắc, kết cấu, và mối liên hệ không gian giữa các đối tượng.
Đặc trưng màu sắc là đặc trưng được sử dụng phổ biến hơn cả do đặc trưng này cho
phép con người nhận ra sự khác biệt rõ ràng nhất giữa các hình ảnh.
Hình dạng của đối tượng có thể thu được bởi đường viền bao xung quanh. Có hai
cách tiếp cận được sử dung để phân tích hình dạng, đó là dựa trên vùng hình dạng và biên.
Hình 1.1: Đặc trưng hình dạng
Kết cấu cũng là một đặc trưng quan trọng trong nhận dạng bản mẫu và tra cứu ảnh.
Nó cung cấp bản mẫu trực quan về vùng của ảnh. Các thuộc tính quan trọng của đặc trưng kết
cấu như: Độ tương phản, thuộc tính thô, hướng, tính quy luật, chu kỳ và tính ngẫu nhiên.
Hình 1.2: Đặc trưng kết cấu
Mối quan hệ không gian dùng để phân biệt các đối tượng khác nhau trong một ảnh.
Hình 1.3: Biểu diễn hình dạng qua mối quan hệ không gian
1.3 Cấu trúc của hệ thống tra cứu ảnh theo nội dung
Một hệ thống tra cứu ảnh có thể thực hiện qua nhiều công đoạn: Nhập ảnh truy vấn,
nhập dữ liệu ảnh cho cơ sở dữ liệu, chuẩn hóa ảnh, trích chọn đặc trưng của ảnh truy vấn và
ảnh trong cơ sở dữ liệu, tính toán độ tương tự và cách hiển thị kết quả lên màn hình, …
Hình 1.4: Cấu trúc hệ thống tra cứu ảnh theo nội dung
1.4 Một số hệ thống tra cứu ảnh theo nội dung
1.4.1 Hệ thống QBIC
Hệ thống QBIC của hãng IBM là một hệ thống tra cứu ảnh dựa trên nội dung cho
phép người sử dụng tra cứu ảnh dựa vào màu sắc, hình dạng và kết cấu.
1.4.2 Hệ thống Photobook
Hệ thống này được phát triển ở viện kỹ thuật Massachusetts cho phép người sử dụng
tra cứu ảnh dựa trên màu sắc, hình dạng và kết cấu.
1.4.3 Hệ thống VisualSEEK và WebSEEK
Cả hai hệ thống này đều được phát triển tại Trường Đại học Colombia. VisualSEEK
là hệ thống cơ sở dữ liệu ảnh. WebSEEK là công cụ tìm kiếm trên website.
1.4.4 Hệ thống RetrievalWare
Hệ thống này được phát triển bởi tập đoàn công nghệ Excalibur cho phép người sử
dụng tra cứu ảnh bởi nội dung màu, hình dạng, kết cấu, độ sáng, kết cấu màu và hệ số co.
1.4.5 Hệ thống Imatch
Hệ thống này cho phép người sử dụng tra cứu ảnh bởi nội dung màu, hình dạng, và
kết cấu.
1.5 Một số ứng dụng cơ bản của tra cứu ảnh
Tra cứu ảnh cùng với sự phát triển lớn mạnh của mình ngày càng được ứng dụng rộng
rãi trong các lĩnh vực: Ngân hàng, sở hữu trí tuệ, ngăn chặn tội phạm, quân sự, giải trí …
1.6 Kết luận chƣơng
Tra cứu ảnh theo nội dung (CBIR) là một lĩnh vực khoa học được phát triển dựa trên
cơ sở lý thuyết và ứng dụng của xử lý ảnh. Hệ thống cho phép người dùng tra cứu các ảnh
tương tự trong một cơ sở dữ liệu hình ảnh.
Tra cứu ảnh theo nội dung được thực hiện thông qua việc tính độ tương tự giữa hai
bức ảnh được biểu diễn bởi một trong số các đặc trưng mức thấp của ảnh như: Màu sắc, hình
dạng, kết cấu… Kết quả đưa ra là tập các bức ảnh tương tự với ảnh truy vấn được xắp xếp
theo thứ tự giảm dần độ tương tự.
Chƣơng 2: MỘT SỐ PHƢƠNG PHÁP TRÍCH CHỌN ĐẶC TRƢNG HÌNH ẢNH
2.1 Phƣơng pháp trích chọn đặc trƣng theo màu sắc
2.1.1 Không gian màu
Không gian màu phổ biến: RGB, CMY, HSx, …
Không gian màu RGB
RGB là không gian màu được sử dụng phổ biến nhất để hiển thị ảnh. Không gian
RGB bao gồm 3 thành phần màu là Đỏ (Red), Xanh lá cây (Green) và Xanh lam (Blue). Các
thành phần này gọi là màu cộng bởi vì các màu sắc trong không gian RGB đều có thể thu
được bằng cách cộng 3 thành phần màu này lại với nhau.
Hình 2.1 Không gian màu RGB.
Không gian màu CMY
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.
Không gian màu HSx
Hình 2.2 Mô tả không gian màu HSV.
2.1.2 Lượng tử hoá màu
Lượng tử hóa màu là quá trình làm giảm số màu sắc được sử dụng để mô tả ảnh. Việc
lượng tử hóa màu trong không gian màu RGB được thực hiện bằng cách chia khối hình lập
phương lớn thành những khối nhỏ và mỗi khối nhỏ có thể đại diện cho một màu đơn.
Khi giảm một màu {R, G ,B} 24 bit màu thành màu mới {R’, G’ ,B’} với n 3 màu ta
đặt:
R'
n*R
28
G'
n*G
28
B'
n*B
28
(2.1)
Vì vậy, sau khi giảm số màu sẽ có n*n*n=n màu.
2.1.3 Các moment màu
Công thức toán học để biểu diễn 3 moment :
3
i
i
si 3
1
N
1
N
N
f
j 1
(2.2)
N
( f
1
N
ij
j 1
ij
i ) 2
(2.3)
N
( f
j 1
ij
i )3
(2.4)
Trong đó fij là giá trị của thành phần màu thứ i của điểm ảnh thứ j và N là số lượng
điểm ảnh của ảnh đó.
2.1.4 Biểu đồ màu
Biểu đồ màu (Color Histogram) để biểu diễn nội dung màu của một bức ảnh. Trong
biểu đồ màu của ảnh, giá trị của mỗi mức sẽ là tổng số điểm ảnh có cùng màu tương ứng. Để
so sánh những ảnh có kích cỡ khác nhau biểu đồ màu nên được chuẩn hóa và biểu đồ màu
chuẩn hóa được định nghĩa:
H’={H’[0], H’[1], H’[2], ..., H’[i], ...H’[N]}
(2.5)
H [i]
H ' [i]
P
Với
(2.6) và P là tổng số các điểm trong ảnh.
2.2 Phƣơng pháp trích chọn đặc trƣng theo kết cấu
2.2.1 Các đặc trưng Tamura
Độ thô
Độ thô được dùng để đo tính chất hạt của kết cấu. Để tính toán độ thô, tại mỗi điểm
ảnh (x,y) ta tính toán một trung bình động (average moving) Ak(x,y) sử dụng một cửa sổ kích
thước 2k×2k (k = 0, 1, ..., 5):
Ak ( x, y )
x 2 k 1 1 y 2
k 1
1
g (i, j ) / 2
i x 2
k 1
j y 2
2k
k 1
(2.7)
Trong đó g(i,j) là độ sáng của điểm ảnh ở vị trí (i,j).
Độ thô được tính toán bằng cách lấy giá trị trung bình của Sbest trên phạm vi toàn bức
ảnh, nghĩa là:
Fcrs
1 m
m.n i 1
n
S
j 1
best
(i, j )
(2.11)
Độ tương phản
Công thức tính độ tương phản như sau:
Fcon
4
4
(2.12)
Độ định hướng
Độ lớn và góc pha của véc tơ này được định nghĩa:
| G |
| H | | V |
2
(2.13)
tan 1 ( V )
H
2
(2.14)
Tính toán histogram tổng hợp của cả ảnh để xác định độ định hướng tổng thể dựa trên
độ sắc của các đỉnh:
np
Fdir
p
(
w p
p
) 2 H D ( )
(2.15)
2.2.2 Các đặc trưng Wold
Một cách tiếp cận khác để biểu diễn kết cấu là sử dụng phân tích Wold. Phân tích
Wold có 3 thành phần độ hài hoà, độ phai mờ và độ bất định tương ứng với các đặc điểm tính
chu kỳ, tính định hướng và tính ngẫu nhiên của kết cấu.
Trong miền tần số ta xây dựng được các công thức:
Fy ( , ) Fu ( , ) Fd ( , ) Fu ( , ) Fh ( , ) Fe ( , )
(2.16)
2.2.3 Mô hình SAR
Trong mô hình SAR, độ chói của các điểm ảnh được coi như các biến ngẫu nhiên. Độ
chói g(x,y) của điểm ảnh (x,y) được coi như là một tổ hợp tuyến tính độ chói của điểm ảnh
liền kề g(x’,y’) và mẫu nhiễu dương (x,y) tức là:
g ( x, y) ( x' , y' ) g ( x' , y' ) ( x, y)
( x ', y ')D
(2.17)
2.2.4 Ma trận đồng khả năng
Một số đặc trưng của kết cấu có thể tính được dựa vào phương pháp ma trận đồng khả
năng là:
Năng lượng:
Entropy:
C
i
2
(i, j )
j
C (i, j) log C (i, j)
i
j
Độ tương phản:
(i j)
i
2
C (i, j )
j
C (i, j )
1 | i j |
Tính đồng nhất:
2.2.5 Lọc Gabor
Hàm lọc Gabor hai chiều g(x,y) được định nghĩa:
i
g ( x, y)
j
1 x2 y2
exp[ ( 2 2 ) 2jWx
2 x y
2 x y
1
(2.18)
2.2.6 Biến đổi dạng sóng
Biến đổi dạng sóng phân tích một tín hiệu thành một họ các hàm cơ sở mn(x) bằng
cách dịch chuyển và co giãn một hàm gốc (x), tức là:
mn(x) = 2-m/2(2-mx - n)
(2.24)
Trong đó m và n là tham số co giãn và tham số dịch chuyển. Một tín hiệu f(x) có thể
được biểu diễn dưới dạng:
f ( x) cmn mn ( x)
m,n
(2.25)
2.3 Phƣơng pháp trích chọn đặc trƣng hình dạng
Biểu diễn hình dạng của đối tượng ảnh có thể chia thành hai kiểu: Theo đường bao
quanh (biên) và theo vùng.
Hình 2.3 Biểu diễn hình dạng theo đường biên và theo vùng
2.3.1 Biên và các phương pháp phát hiện biên
Phƣơng pháp phát hiện biên trực tiếp
Phương pháp này làm nổi biên dựa vào sự biến thiên độ xám của ảnh. Kỹ thuật chủ
yếu dùng để phát hiện biên là kỹ thuật đạo hàm.
Phƣơng pháp phát hiện biên gián tiếp
- Thuật toán dò biên tổng quát như sau:
Bước 1: Xác định cặp nền-vùng xuất phát: cặp nền-vùng xuất phát được xác định
bằng cách duyệt ảnh lần lượt từ trên xuống dưới, từ trái sang phải và kiểm tra theo định nghĩa
cặp nền-vùng.
Bước 2: Xác định cặp nền-vùng tiếp theo.
Bước 3: Lựa chọn điểm biên
Bước 4: Nếu gặp lại cặp xuất phát thì dừng, nếu không quay lại bước 2.
2.3.2 Xử lý ảnh trong miền tần số và biến đổi Fourier
Để biểu diễn dữ liệu trong miền tần số cần phải thực hiện một số biến đổi thông qua
các phép biến đổi: Fourier, ...
Xét một ví dụ đơn giản: tín hiệu đầu vào có dạng hình cosin được biểu diễn trong
miền thời gian và miền tần số:
Hình 2.4 Biểu diễn hình dạng theo miền thời gian và miền tần số.
Hình 2.5: Ảnh thực (a) và ảnh thu được sau biến đổi Fourier (b)
2.4 Thông tin không gian
Thu thông tin không gian của các đối tượng trong một ảnh là một quá trình quan trọng
đối với các hệ thống GIS. Quá trình này bao gồm việc biểu diễn vị trí không gian tuyệt đối và
cũng bao gồm vị trí không gian tương đối của các đối tượng. Các thao tác như giao và chồng
được sử dụng. Bố cục màu kết hợp thông tin không gian với thông tin màu xuất hiện trong
ảnh và tạo ra một đặc trưng quan trọng trong quá trình tra cứu.
2.5 Phân đoạn
Phân đoạn là quá trình phân ảnh ra thành các vùng mà về lý tưởng nó sẽ tương ứng
với các đối tượng xuất hiện trong ảnh. Trong phân đoạn các yêu cầu chính xác phân đoạn là rất
khác nhau cho các đặc trưng hình và các đặc trưng bố cục.
2.6 Kết luận
Như vậy chương 2 đã tập trung giới thiệu một số phương pháp trích chọn đặc trưng hình
ảnh trong tra cứu ảnh theo nội dung. Với mỗi phương pháp lại có các kỹ thuật tương ứng khác
nhau. Tùy vào từng trường hợp cụ thể chúng ta có thể sử dụng phương pháp trích chọn nào đó
cho phù hợp để trả về kết quả tra cứu là tốt nhất.
Chƣơng 3: TRA CỨU ẢNH DỰA TRÊN LƢỚI
3.1 Định nghĩa lƣới
Hình 3.1: Biểu diễn lưới.
3.2 Phƣơng pháp tra cứu ảnh dựa trên lƣới
Tra cứu ảnh dựa trên lưới là phương pháp tra cứu dựa trên hình đại diện và độ đo
tương tự.
3.2.1 Một số khái niệm cơ bản
3.2.1.1 Khái niệm về hình dạng
Hình dạng không phải là một thuộc tính của ảnh, hình dạng chỉ là biên của đối tượng
bất kỳ có trong ảnh.
3.2.1.2 Trục chính của hình dạng
Trục chính của hình dạng là đoạn thẳng nối hai điểm thuộc đường bao của vùng hình
dạng và có độ dài lớn nhất.
3.2.1.3 Trục phụ của hình dạng
Trục phụ của hình dạng là đoạn thẳng vuông góc với tru ̣c chiń h, có đô ̣ dài đảm bảo để
có thể vẽ một hình chữ nhật bao khít hình dạng có các cạnh song song và có độ dài b ằng với
trục chính và trục phu ̣.
3.2.1.4 Độ lệch tâm
Độ lệch tâm là tỉ lệ đô ̣ dài của tru ̣c chính trên tru ̣c phu .̣
3.2.1.5 Độ đo tương tự
Sự tương tự giữa hai hình ảnh p , q đươ ̣c xác đinh
̣ bằ ng đô ̣ đo tương tự s (p,q). Nế u
s(p,q) = 1 có nghĩa là hai hình ảnh đượ c coi là giố ng nhau , ngươ ̣c l ại thì hai hình ảnh khác
nhau.
3.2.2 Tra cứu ảnh dựa trên lưới
3.2.2.1 Tách vùng hình dạng của đối tượng
Từ một ảnh ban đầu, chúng ta có thể thực hiện tách vùng hình dạng bằng cách sử
dụng các phương pháp tách biên (nổi biên) hoặc biến đổi từ miền quan sát sang miền tần số.
3.2.2.2 Biể u diễn vùng hình dạng dựa trên lưới
Đầu tiên ta vẽ đè mô ̣t lưới g ồm các ô có cùng kích thước lên vùng hình dạng. Quy
ước rằng:
- Số 1 tương ứng với ô có it́ nhấ t 15% số điể m ảnh của vùng hình dạng phủ lên ô lưới.
- Số 0 ứng với mỗi ô còn la ̣i.
Đọc l ần lượt các số trong lưới theo thứ tự từ trái sang phải , từ trên xuố ng dưới để
được daỹ bit́ đa ̣i diê ̣n cho vùng hiǹ h da ̣ng.
Ví dụ, 11100000 11111000 01111110 01111111.
Hình 3.2: Tạo chuỗi bít biểu diễn vùng hình dạng
3.2.2.3 Chuầ n hóa xoay
Mục đích của chuẩn hóa độ xoay là đặt vùng hình d ạng theo mô ̣t hướng cố đinh
̣ duy
nhấ t, bằ ng cách xoay vùng hình d ạng sao cho tru ̣c chiń h của nó song song với tru ̣c hoành Ox
(hoă ̣c trục tung Oy tùy theo từng chương triǹ h ). Khi đó vẫn có hai khả năng xảy ra đố i với vi ̣
trí của vùng hình dạng.
Hình 3.3: Hai hướng của cùng một vùng hình dạng
3.2.2.4 Chuẩn hóa co dãn
Thố ng nhấ t đưa vùng hiǹ h da ̣ng về kić h thướ c đồ ng da ̣ng mà ở đó tru ̣c chiń h của nó
có cùng độ dài không đổi là 192 điể m ảnh (pixel).
3.2.2.5 Chỉ mục vùng hình dạng
Sau khi chuẩ n hóa xoay , chuẩn hóa co dañ và cho ̣n kić h thước ô lưới phủ , chúng ta
chỉ cần lưu trữ một chuỗi bit́ biể u diễn duy nhấ t cho mỗi vùng hiǹ h da ̣ng trong cơ sở dữ liê ̣u ,
với giả đinh
̣ rằ ng mỗi vùng chỉ có một tru ̣c chiń h.
3.2.2.6 Độ đo tương tự
Giả sử: R và R’ là các véctơ hàng của hai ảnh, C và C’ là các véctơ cột của hai ảnh.
Ta thực hiện:
- Tính toán độ đo tương tự.
- Tính toán các véctơ hàng và cột của mọi vùng hình dạng trong ảnh truy vấn.
- Tìm khác biệt hàng và cột giữa các vùng hình dạng trong hai ảnh.
- Ri và Ci là bit thứ i của các véctơ ảnh thứ nhất
- Ri’ và Ci’ là bit thứ i của các véctơ ảnh thứ hai
- Nếu (Rd+Cd) < T (ngưỡng) thì hai ảnh tương tự.
3.2.2.6 Các phép toán khác
Ngoài ra chúng ta cần quan tâm tới phép đối xứng theo trục ngang và đối xứng theo
trục thẳng đứng.
Hình 3.4: Phép đối xứng
3.2.2.7 Xử lý trường hợp vùng hình dạng có hơn một trục chính
Với những vùng hiǹ h da ̣ng có nhiề u hơn m ột tru ̣c, ta cầ n phải tim
̀ chuỗi bit́ chỉ mu ̣c
của vùng hình d ạng đó theo từng tru ̣c chiń h của nó . Khi đó viê ̣c so sánh để tìm kiếm ảnh sẽ
đươ ̣c thực hiê ̣n tố n kém hơn bằ ng cách so sánh từng că ̣p chuỗi bit́ trong tấ t cả các chuỗi bit́
biể u diễn vùng hình da ̣ng trong CSDL với 4 chuỗi bít phát sinh cho vùng hình da ̣ng truy vấ n .
3.2.2.8 Quy trình tạochỉ mục và tra cứu ảnh dựa trên lưới
Xử lý các trích chọn đặc trưng để t ạo chỉ mu ̣c cho các hình da ̣ng trong cơ sở dữ liê ̣u ,
bao gồ m các bước:
- Xác định trục chính, trục phụ, đô ̣ lê ̣ch tâm.
- Chuẩ n hóa co dañ và chuẩ n hóa xoay.
- Xác định kích thước lưới phủ, kích thước ô lưới và cố định kích thước đó để phủ lên
vùng hình dạng.
- Xác định chuỗi bít chỉ mục.
- Chuỗi bit́ duy nhấ t, đô ̣ dài tru ̣c phu ̣ ta ̣o thành chỉ mu ̣c cho vùng hiǹ h da ̣ng và đươ ̣c
lưu trữ trong cơ sở dữ liê ̣u.
Như vậy trong quá trình tra cứu gồm các bước:
1. Vùng hình dạng trong ảnh truy vấn được mô tả bởi chiều dài trục phụ và chuỗi bít
nhị phân.
2. Thực hiện so sánh bốn chuỗi bít nhị phân với các chuỗi trong cơ sở dữ liệu để tìm
kiếm.
3. Khoảng cách giữa vùng hình dạng truy vấn với một vùng hình dạng trong cơ sở dữ
liệu được tính toán bởi số lượng các vị trí bít bị sai khác.
4. Các vùng hình dạng tương tự được hiển thị hoặc lấy thứ tự tăng dần các khoảng
cách.
3.3 Tra cứu ảnh dựa vào chỉ mục kết hợp màu sắc và hình dạng
3.3.1 Các đặc trưng màu sắc và hình dạng
3.3.1.1 Phương pháp lập chỉ mục màu sắc
Không gian phân loại màu
Toàn bộ không gian màu RGB được mô tả bằng cách sử dụng một tập con các màu
như trong hình 3.5.
Hình 3.5: Bảng tra cứu màu
Kết hợp màu sắc và vùng lựa chọn
Sử dụng giá trị màu tại điểm ảnh p và giá trị trong bảng màu tương ứng C, khoảng
cách màu Cd được tính toán bằng cách sử dụng công thức tính khoảng cách Euclidean:
2
2
2
(3.1)
Cd MINi25
1 ( pr Ci ) ( p g Ci ) ( pb Ci )
R
G
B
Các bước thực hiện phân đoạn và dò biên:
1. Đọc ảnh và tạo một ma trận ảnh.
2. For mỗi điểm ảnh trong ảnh do
D (( I r Cr ) 2 ( I g Cg ) 2 ( I b Cb ) 2
(3.2)
- Gán các thành phần RGB trong bảng tra cứu màu cho một điểm ảnh có khoảng cách
D nhỏ nhất.
3. Xác định sự xuất hiện đầu tiên của một điểm ảnh có giá trị RGB tương tự như bảng
tần suất.
4. Gán vị trí điểm ảnh theo chiều ngang và chiều dọc.
5. Dựa vào iseed, jseed để đánh dấu toàn bộ vùng sử dụng thuật toán phát hiện biên gián
tiếp (8 lân cận).
6. Kết hợp các (x,y) tạo thành biên của vùng.
7. Xác định kích thước r(R) của hình chữ nhật bao quanh:
r ( R)
x1 x2 * y1 y 2
(3.3)
Im age _ size
8. Lặp lại từ bước 3 đến bước 7 cho đến khi tìm được 3 vùng màu trội.
Hình 3.6: Minh họa phân vùng màu.
Hình 3.7: Ảnh đã tìm được biên.
Tìm vị trí vùng màu trội
Không gian ảnh được chia thành 9 khu vực nhỏ. Vị trí tương đối của vùng được xác
định.
Hình 3.8: Bản đồ khu vực
Hình 3.9: Minh họa tìm khu vực.
3.3.1.2 Biểu diễn hình dạng
Sau khi có được các vùng màu trội, ta có thể coi đó như là các vùng hình dạng cần tìm
kiếm.
3.3.2 Quá trình lập chỉ mục và truy vấn
3.3.2.1 Chỉ mục màu sắc
Cấu trúc chỉ mục chỉ mục đa chiều đa mức dựa trên việc phân đoạn và cấu trúc cây Rtree được sử dụng để lưu trữ hình ảnh. Cấu trúc này sử dụng kĩ thuật cắt tỉa để tăng tốc độ tìm
kiếm. hình 3.10 mô tả cấu trúc hai mức đầy đủ như sau:
Hình 3.10: Cấu trúc chỉ mục.
Một chỉ số duy nhất được hình thành dựa trên 25 màu và được tính toán như sau:
n
(3.6)
Index i 1 Ci * 25 n1
Khi đó, chỉ số được đưa ra bởi công thức:
Index C1 * 25 2 C2 * 251 C3 * 250
(3.7)
Hình 3.11: Ví dụ về bảng băm.
3.3.2.2 Chỉ mục hình dạng
Với mỗi vùng màu được tìm thấy ở trên, ta thực hiện tính toán để có được chỉ mục
cho vùng hình dạng gồm: Chuỗi bít và độ dài trục phụ.
3.3.2.3 Truy vấn
Quy trình truy vấn được thực hiện qua các bước:
1. Ảnh truy vấn được xử lý để có được danh sách các ảnh phù hợp với đặc trưng màu
sắc.
2. Với mỗi vùng màu trong ảnh truy vấn ta biểu diễn vùng hình dạng. Cần lưu lại chỉ
mục của 4 ảnh tương ứng với vùng hình dạng khi thực hiện quay 180 độ và lật theo chiều
ngang, lật theo chiều dọc.
3. So sánh chỉ mục vùng của ảnh truy vấn với danh sách các ảnh nhận được dựa vào
màu sắc.
4. Chỉ các vùng có độ lệch tâm thỏa mãn ngưỡng T nào đó mới được so sánh độ
tương tự hình dạng.
5. Các ảnh phù hợp được xếp thứ tự phụ thuộc vào độ khác biệt của tổng độ khác biệt
trong các véc tơ hàng và cột giữa hình ảnh truy vấn và hình ảnh tương thích tìm được.
3.3.2.4 Độ đo tương tự
Độ đo tương tự được tính toán như mục 3.2.2.6 của luận văn này.
3.4 Kết luận
Tra cứu ảnh dựa trên lưới là một cách tiếp cận mới dựa trên hình dạng. Với ảnh đưa
vào, chúng ta thực hiện trích chọn đặc trưng cho ảnh để được xâu bít nhị phân làm chỉ mục
cho việc tra cứu.
Tra cứu ảnh dựa trên lưới có thể kết hợp với đặc trưng màu sắc nhằm tăng hiệu quả
tra cứu. Thực chất là tra cứu dựa trên chỉ mục kết hợp giữa màu sắc và hình dạng.
Chƣơng 4: THIẾT KẾ VÀ CÀI ĐẶT CHƢƠNG TRÌNH MÔ PHỎNG TRA CỨU ẢNH
DỰA TRÊN LƢỚI
4.1 Phát biểu bài toán
Bài toán: Cho cơ sở dữ liệu ảnh, tìm kiếm ảnh tương tự với ảnh truy vấn về màu sắc
và hình dạng.
Giải quyết:
- Trích chọn đặc trưng ảnh trong cơ sở dữ liệu lưu vào tệp đặc trưng. Tệp đặc trưng
gồm các đặc trưng: chỉ số màu sắc, chuỗi bít nhị phân, chiều cao trục phụ (độ cao của ảnh),
đường dẫn.
- Trích chọn ảnh truy vấn bao gồm chỉ số màu sắc, chuỗi bít nhị phân và thực hiện so
sánh với các đặc trưng được lưu trong tệp đặc trưng tìm ra ảnh có độ tương tự gần với ảnh
truy vấn thỏa mãn một ngưỡng (T) cho trước nào đó.
4.2 Cài đặt sử dụng phƣơng pháp tra cứu ảnh dựa trên lƣới
4.2.1 Chuyển đổi ảnh về ảnh đen trắng
Kiểm tra giá trị màu tại mỗi điểm ảnh nếu nhỏ hơn 128 thì đặt lại giá trị màu là 0,
ngược lại đặt giá trị màu là 255.
4.2.2 Tìm hình chữ nhật cơ sở
Lần lượt chiếu vùng hình dạng lên trục chính X và trục phụ Y để tìm giá trị Xmin,
Xmax, Ymin, Ymax.
4.2.3 Chuẩn hóa vùng hình dạng
Việc chuẩn hóa vùng hình dạng được thực hiện ở việc co dãn và xoay đối tượng.
4.2.3.1 Co dãn đối tượng
Xét từng điểm ảnh rồi thực hiện làm tròn sau khi nhân tọa độ điểm ảnh với một hệ số
nào đó sao cho kích thước của ảnh mới đúng bằng hình chữ nhật bao quanh đối tượng.
4.2.3.2 Tìm trục chính cho vùng hình dạng
Trục chính của ảnh được xác định: đường nối giữa 2 điểm ảnh xa nhất (có độ dài lớn
nhất).
Với từng cặp điểm bất kỳ trong ảnh ta tính độ dài giữa chúng để tìm ra độ dài lớn
nhất. Đường nối giữa hai cặp điểm có độ dài lớn nhất đó chính là trục chính cần tìm.
4.2.3.3 Xoay vùng hình dạng
Thực hiện xoay vùng hình dạng theo góc quay nhất định. Góc quay được xác định
thông qua công thức hệ thức lượng trong tam giác vuông. Để đảm bảo xoay hình theo hướng
chính xác ta cần chú ý đến các trường hợp cụ thể.
4.2.4 Phủ lưới vùng hình dạng
Ta thực hiện phủ lưới bằng cách chia tọa độ các ô trong ảnh, mặc định các ô lưới có
kích thước 12 × 12. Dựa trên các ô lưới này, ta tính toán và tìm các ô có chứa ảnh theo tỷ lệ:
thì ô lưới đó sẽ nhận giá trị 1, ngược lại là 0 (coi như không có ảnh trong ô lưới đó).
Hình 4.1: Phủ lưới ảnh và tô màu đối tượng
4.2.5 Tính độ tương tự
Với hai chuỗi bít nhị phân bất kỳ, ta kiểm tra nếu độ dài khác nhau không quá ngưỡng
T cho phép thì ta sử dụng công thức tính khoảng cách Hamminh để tìm sự sai khác giữa các
bít có trong dãy bít.
4.3 Giao diện chƣơng trình
Chương trình được thiết kế có hai chức năng: Tra cứu dựa trên hình dạng, tra cứu kết
hợp màu sắc và hình dạng.
Hình 4.2: Tra cứu dựa trên hình dạng.
Hình 4.3: Tra cứu kết hợp màu sắc và hình dạng.
KẾT LUẬN
Luận văn đã trình bày một cách tổng quan về tra cứu ảnh và một số phương pháp trích
chọn đặc trưng hình ảnh, đồng thời tìm hiểu và nghiên cứu phương pháp tra cứu ảnh dựa trên
lưới. Giới thiệu một số phương pháp trích chọn đặc trưng của ảnh trong tra cứu ảnh theo nội
dung như: Trích chọn theo màu sắc, hình dạng, ... Sau đó đi vào nghiên cứu kỹ thuật tra cứu
ảnh dựa trên lưới có sử dụng đặc trưng hình dạng, đồn thời kết hợp đặc trưng màu sắc với đặc
trưng hình dạng. Việc nghiên cứu cài đặt phương pháp tra cứu ảnh dựa trên lưới là một bước
đệm cho phép tra cứu ảnh kết hợp với các đặc trưng màu sắc để cho kết quả tra cứu tốt hơn
nữa.
Luận văn “Tra cứu ảnh dựa trên lưới và ứng dụng” đã đạt được những kết quả:
1. Nghiên cứu tổng quan về tra cứu ảnh, một số phương pháp trích chọn đặc trưng
hình ảnh.
2. Nghiên cứu phương pháp tra cứu ảnh dựa trên lưới và tìm hiểu phương pháp tra
cứu kết hợp đặc trưng màu sắc và hình dạng.
3. Xây dựng ứng dụng mô phỏng phương pháp tra cứu ảnh dựa vào đặc trưng mức
thấp của ảnh.
Tuy nhiên chương trình mới chỉ áp dụng cho tra cứu các ảnh đơn giản chứ chưa tra
cứu được các ảnh phức tạp trong thực tế.
References
Tiếng Việt
[1]. PGS.TS Đă ̣ng Văn Đức (2005), Bài giảng điện tử Cơ sở dữ liệu đa phương tiện , trường
Đa ̣i ho ̣c Công Nghê ̣, Đa ̣i ho ̣c Quố c Gia Hà Nô ̣i.
[2]. TS. Đỗ Năng Toàn - TS. Phạm Việt Bình (2008), Giáo trình xử lý ảnh, Nhà xuất bản
Khoa học và Kỹ thuật.
Tiếng Anh
[3]. Guojun Lu (1999) Multimedia Database Management Systems, Artech House, Inc.
[4]. Prof. Dr. H.-J. Schek, Supervisors: M. Mlivoncic, Dr. R. Weber (2002), Region Based
Image Similarity Search, Silvan Andreas Saxer.
[5]. Cheng Chang, Liu Wenyin, Hongjiang Zhang (2001), Image retrieval base on region
shape similarity, Microsoft Research China.
[6]. Atul Sajjanhar and Guojun Lu, A Grid Based Shape Indexing and Retrieval Method,
Gippsland Shool of Computing and Information Technology, Monash University, Churchill,
Victoria – 3842, Australia.
[7]. B.G. Prasad, S.K. Gupta, K.K Biswas, Color and Shape Index for Region – Based Image
Retrieval, Department of Computer Science and Engineering, P.E.S College of Engineering,
Mandya, 571402, INDIA.
[8]. Fuhui Long, Hongjiang Zhang, David Dagan Feng (2002), Fundamentals of Contentbased Image Retrieval, in Multimedia Information Retrieval and Management Technological Fundamentals and Applications.
[9]. Colin C. Venteres and Dr. Matthew Cooper, A Review of Content-Based Image Retrieval
Systems.
[10]. Dengsheng Zhang, Aylwin Wong, Maria Indrawan, Guojun Lu, Content-based Image
Retrieval Using Gabor Texture Features.
[11]. Eva M.van Rikxoort (2005), “Content-based Image Retrieval Utilizing Color, Texture,
and Shape”, Master’s thesis in AI Radbound University Nijmegen The Netherlands.
[12]. Low (1991), A introductory Computer Vision and Image Processin, McGraw-hill, 244p.
ISBN 0077074033
[13]. Sebe N, Lew (2001), “Texture Features for Content-based Retrieval”: Principles of
visual Information Retrieval.
- Xem thêm -