Tài liệu Nghiên cứu xây dựng hệ thống tìm kiếm video theo nội dung: ... Ebook Nghiên cứu xây dựng hệ thống tìm kiếm video theo nội dung
111 trang |
Chia sẻ: huyen82 | Lượt xem: 2539 | Lượt tải: 4
Tóm tắt tài liệu Nghiên cứu xây dựng hệ thống tìm kiếm video theo nội dung, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Bé GI¸O DôC Vµ §µO T¹O
TR¦êNG §¹I HäC B¸CH KHOA Hµ NéI
LUËN V¡N TH¹C SÜ KHOA HäC
NGHI£N CøU, X¢Y DùNG HÖ THèNG T×M KIÕM
VIDEO THEO NéI DUNG
NGµNH: Xö Lý TH¤NG TIN Vµ TRUYÒN TH¤NG
§ç V¡N H¶I
Ng−êi h−íng dÉn khoa häc:
TS. HUúNH QUYÕT TH¾NG
HÀ NỘI - 2006
i
LỜI CẢM ƠN
Em xin bày tỏ lòng biết ơn sâu sắc tới TS. Huỳnh Quyết Thắng người
thày kính mến đã hướng dẫn, chỉ dạy tận tình để em hoàn thành luận văn này.
Em xin chân thành cảm ơn các thày, cô giáo khoa Công nghệ Thông tin,
Trung tâm Bồi dưỡng và Đào tạo Sau đại học, Trường Đại học Bách khoa Hà
nội đã đón nhận và truyền thụ kiến thức cho em trong suốt quá trình học tập
vừa qua.
Tôi cũng xin cảm ơn cơ quan, bạn bè đồng nghiệp, gia đình và những
người thân đã cùng chia sẻ, giúp đỡ, động viên, tạo mọi điều kiện thuận lợi để
tôi hoàn thành nhiệm vụ học tập và bản luận văn này.
Hà nội, ngày 22 tháng 11 năm 2006
Học viên
Đỗ Văn Hải
ii
MỞ ĐẦU
Khoảng hơn một thập kỷ gần đây, cùng với sự phát triển nhanh chóng
của công nghệ thông tin và truyền thông, các nghiên cứu về công nghệ liên
quan đến video đã đạt được những thành tựu nhất định. Hiện nay với những
phương tiện truyền thông mới cho phép kết nối Internet với tốc độ cao như:
kênh thuê riêng, xDSL,... người sử dụng có thể xem video trực tuyến trên
Internet với chất lượng cao. Cùng với đó, video số ngày càng trở nên thông
dụng trong cuộc sống như truyền thông, giáo dục đào tạo, giải trí, xuất bản,...
đã tạo nên một lượng dữ liệu khổng lồ video. Dữ liệu càng nhiều, càng phong
phú đa dạng thì con người càng khó khăn trong việc quản lý, tìm kiếm. Một
học giả nước ngoài đã từng nói “Chúng ta đang chìm ngập trong dữ liệu mà
vẫn đói tri thức”. Do vậy, một yêu cầu bức thiết được đặt ra: làm sao có thể
quản lý, tìm kiếm tự động được các đối tượng video một cách nhanh chóng và
tiện lợi? Luận văn này sẽ giải quyết được phần nào đó cho câu hỏi trên. Luận
văn sẽ tập trung vào tìm hiểu các đặc trưng cơ bản nhất của video, đưa ra một
số phương pháp trích rút các đặc trưng của video phục vụ cho việc tìm kiếm.
Việc tìm kiếm video có nhiều cấp độ, tuy nhiên trong luận văn chỉ tập trung
nghiên cứu và đưa ra một số giải pháp phục vụ cho việc tìm kiếm video ở
mức thấp.
Mục lục
iii
MỤC LỤC
LỜI CẢM ƠN.........................................................................................I
MỞ ĐẦU ...............................................................................................II
MỤC LỤC.............................................................................................III
DANH SÁCH HÌNH VẼ ..................................................................... VIII
DANH SÁCH BẢNG BIỂU ................................................................. XI
DANH MỤC CÁC TỪ VIẾT TẮT........................................................ XII
CHƯƠNG 1. TỔNG QUAN VỀ TÌM KIẾM VIDEO THEO NỘI DUNG..1
1.1 Đặt vấn đề .................................................................................................. 1
1.2 Giới thiệu sơ lược về CBVR ..................................................................... 1
1.3 Các nghiên cứu trên thế giới về CBVR................................................... 3
1.4 Hướng nghiên cứu và nội dung của luận văn......................................... 4
Kết luận chương .............................................................................................. 7
CHƯƠNG 2. PHƯƠNG PHÁP TÌM KIẾM ẢNH THEO NỘI DUNG ÁP
DỤNG TRONG BÀI TOÁN TÌM KIẾM VIDEO THEO NỘI DUNG ........8
2.1 Đặt vấn đề .................................................................................................. 8
2.2 Tổng quan về tìm kiếm ảnh theo nội dung ............................................. 8
2.2.1 Giới thiệu.............................................................................................. 8
Mục lục
iv
2.2.2 Cơ chế tính toán chung của CBIR........................................................ 9
2.2.3 Một số đặc trưng của ảnh ................................................................... 10
2.3 Đặc tính màu sắc của ảnh....................................................................... 11
2.3.1 Không gian màu ................................................................................. 12
2.3.2 Biểu đồ màu (Color Histogram)......................................................... 17
2.3.3 Biểu đồ tương quan màu (Color Correlogram).................................. 19
2.4 Đặc trưng Entropy của ảnh.................................................................... 20
2.4.1 Đặt vấn đề........................................................................................... 20
2.4.2 Lý thuyết thông tin và hàm Entropy .................................................. 21
2.4.3 Entropy ảnh là một đặc trưng............................................................. 22
2.5 Phép đo khoảng cách .............................................................................. 23
2.5.1 Đặt vấn đề........................................................................................... 23
2.5.2 Một số tính chất của độ đo ................................................................. 23
2.5.3 Một số độ đo thông dụng ................................................................... 24
2.5.4 Các độ đo được sử dụng trong tìm kiếm ảnh theo nội dung.............. 25
2.6 Xây dựng phần mềm tìm kiếm ảnh ứng dụng trong hệ thống tìm kiếm
video................................................................................................................ 27
2.6.1 Tìm kiếm ảnh sử dụng phương pháp so sánh biểu đồ màu trong không
gian màu RGB............................................................................................. 28
2.6.2 Tìm kiếm ảnh sử dụng phương pháp so sánh biểu đồ màu trong không
gian màu CIELAB....................................................................................... 30
2.6.3 Tìm kiếm ảnh sử dụng phương pháp Entropy ................................... 32
2.6.4 Tìm kiếm ảnh kết hợp hai phương pháp Entropy và so sánh biểu đồ
màu .............................................................................................................. 37
2.7 Thử nghiệm, so sánh, đánh giá các phương pháp tìm kiếm ảnh........ 39
2.7.1 Đánh giá trong hệ thống tìm kiếm ảnh............................................... 40
Mục lục
v
2.7.2 Cơ sở dữ liệu ảnh thử nghiệm............................................................ 41
2.7.3 So sánh, đánh giá về tốc độ tìm kiếm ................................................ 42
2.7.4 So sánh, đánh giá về độ chính xác ..................................................... 42
2.7.5 Nhận xét ............................................................................................. 46
Kết luận chương ............................................................................................ 46
CHƯƠNG 3. PHÂN ĐOẠN VIDEO.....................................................47
3.1 Giới thiệu sơ lược phân đoạn video....................................................... 47
3.1.1 Một số khái niệm................................................................................ 47
3.1.2 Một số hình thức chuyển cảnh ........................................................... 48
3.1.3 Các hướng tiếp cận trong phân đoạn video........................................ 50
3.2 Một số phương pháp phân đoạn video.................................................. 50
3.2.1 So sánh điểm ảnh ............................................................................... 51
3.2.2 So sánh khối ....................................................................................... 52
3.2.3 So sánh biểu đồ màu .......................................................................... 53
3.2.4 Một số phương pháp khác.................................................................. 55
3.3 Đề xuất phương pháp phân đoạn video trong chuyển cảnh đột ngột 55
3.3.1 Thuật toán phát hiện chuyển cảnh đột ngột sử dụng ngưỡng đơn giản
..................................................................................................................... 56
3.3.2 Phát hiện chuyển cảnh đột ngột sử dụng cửa sổ trượt ....................... 56
3.3.3 Thuật toán cải tiến đề xuất ................................................................. 60
3.4 Xây dựng và đánh giá hệ thống ............................................................. 61
3.4.1 Các tham số đánh giá ......................................................................... 61
3.4.2 Sơ đồ hệ thống cải tiến....................................................................... 62
3.4.3 Các tham số của thuật toán ................................................................ 62
3.4.4 Kết quả thử nghiệm............................................................................ 64
Mục lục
vi
3.4.5 Nhận xét ............................................................................................. 66
Kết luận chương ............................................................................................ 67
CHƯƠNG 4. TRÍCH CHỌN KHUNG HÌNH CHÍNH TRONG VIDEO.68
4.1 Đặt vấn đề ................................................................................................ 68
4.2 Một số kỹ thuật trích chọn khung hình chính hiện nay ...................... 69
4.3 Trích chọn khung hình chính bằng việc khảo sát đường sai khác tích
luỹ.................................................................................................................... 71
4.3.1 Đặt vấn đề........................................................................................... 71
4.3.2 Xây dựng được sai khác tích luỹ........................................................ 71
4.3.3 Thuật toán trích chọn khung hình chính ............................................ 72
4.4 Xây dựng phần mềm trích chọn khung hình chính............................. 76
Kết luận chương ............................................................................................ 79
CHƯƠNG 5. XÂY DỰNG HỆ THỐNG TÌM KIẾM VIDEO THEO NỘI
DUNG DỰA TRÊN PHƯƠNG PHÁP TÌM KIẾM ẢNH TRONG CÁC
KHUNG HÌNH CHÍNH.........................................................................80
5.1 Lựa chọn phương pháp xây dựng.......................................................... 80
5.2 Các mô-đun của hệ thống....................................................................... 80
5.2.1 Mô-đun phân đoạn video ................................................................... 81
5.2.2 Mô-đun trích chọn khung hình chính................................................. 82
5.2.3 Mô-đun tìm kiếm ảnh theo nội dung.................................................. 83
5.2.4 Mô-đun cơ sở dữ liệu ......................................................................... 83
5.3 Giao diện hệ thống .................................................................................. 85
Mục lục
vii
Kết luận chương ............................................................................................ 86
KẾT LUẬN..........................................................................................88
TÀI LIỆU THAM KHẢO ......................................................................91
PHỤ LỤC ............................................................................................96
TÓM TẮT LUẬN VĂN.........................................................................97
Danh sách hình vẽ
viii
DANH SÁCH HÌNH VẼ
Hình 1.1 Sơ đồ hệ thống tìm kiếm video nghiên cứu trong luận văn......... 6
Hình 2.1 Cơ chế hoạt động của hệ thống CBIR ......................................... 10
Hình 2.2 Không gian màu RGB................................................................... 13
Hình 2.3 Không gian màu CMY .................................................................. 14
Hình 2.4 Một số cách biểu diễn không gian màu HSV.............................. 15
Hình 2.5 Không gian màu CIELAB ............................................................ 16
Hình 2.6 Mô tả biểu đồ màu......................................................................... 18
Hình 2.7 Những ảnh khác nhau nhưng có biểu đồ màu giống nhau........ 19
Hình 2.8 Hàm Entropy trong không gian hai chiều .................................. 21
Hình 2.9 Mô tả một số hàm khoảng cách thuộc họ Ls ............................... 24
Hình 2.10 Tính và so sánh ảnh bằng biểu đồ màu cục bộ ......................... 27
Hình 2.11 Biểu đồ màu Red, Green, Blue độc lập...................................... 28
Hình 2.12 Sơ đồ khối hệ thống tìm kiếm ảnh sử dụng phương pháp so
sánh biểu đồ màu trong không gian màu RGB.................................. 29
Hình 2.13 Kết quả tìm kiếm ảnh dựa trên không gian màu RGB (ảnh
truy vấn bên phải) ................................................................................. 30
Hình 2.14 Biểu đồ màu trong không gian màu CIELAB.......................... 31
Hình 2.15 Sơ đồ khối hệ thống tìm kiếm ảnh sử dụng phương pháp so
sánh biểu đồ màu trong không gian màu CIELAB ........................... 31
Hình 2.16 Kết quả tìm kiếm ảnh dựa trên không gian màu CIELAB (ảnh
truy vấn bên phải) ................................................................................. 32
Hình 2.17 Giá trị Entropy ứng với các biểu đồ màu R, G, B.................... 33
Hình 2.18 Sơ đồ khối hệ thống tìm kiếm ảnh sử dụng phương pháp so
sánh Entropy.......................................................................................... 33
Hình 2.19 Kết quả tìm kiếm ảnh dựa trên phương pháp Entropy (ảnh
truy vấn bên phải) ................................................................................. 34
Danh sách hình vẽ
ix
Hình 2.20 Hai ảnh có biểu đồ màu khác nhau nhưng lại có Entropy giống
nhau ........................................................................................................ 34
Hình 2.21 Kết quả tìm kiếm ảnh dựa trên phương pháp Entropy kết hợp
với giá trị trung bình (ảnh truy vấn bên phải) ................................... 36
Hình 2.22 Kết hợp giải thuật tìm kiếm ảnh sử dụng đặc trưng Entropy-
giá trị trung bình và giải thuật so sánh biểu đồ màu......................... 37
Hình 2.23 Sơ đồ khối hệ thống tìm kiếm ảnh sử dụng thuật toán kết hợp
“Entropy-giá trị trung bình” và “So sánh biểu đồ màu”................. 38
Hình 2.24 Kết quả tìm kiếm ảnh dựa trên phương pháp Entropy-giá trị
trung bình kết hợp với phương pháp so sánh biểu đồ màu (ảnh truy
vấn bên phải) ......................................................................................... 39
Hình 2.25 Biểu đồ precision-recall............................................................... 41
Hình 2.26 Giá trị precision của các phương pháp khi số lượng ảnh lấy ra
khác nhau............................................................................................... 44
Hình 2.27 Giá trị precision đối với các loại ảnh khác nhau khi lấy ra 50
ảnh .......................................................................................................... 45
Hình 3.1 Khái niệm về khung hình.............................................................. 47
Hình 3.2 Khái niệm về đoạn cơ sở và chuyển cảnh.................................... 48
Hình 3.3 Chuyển cảnh dần dần fade ........................................................... 49
Hình 3.4 Chuyển cảnh dần dần dissolve ..................................................... 49
Hình 3.5 Chuyển cảnh dần dần wipe........................................................... 50
Hình 3.6 Phát hiện chuyển cảnh bằng ngưỡng đơn giản .......................... 56
Hình 3.7 Cửa sổ truy vấn trượt với HWS=5 ............................................. 57
Hình 3.8 Cửa sổ truy vấn trượt với HWS=10 ............................................ 58
Hình 3.9 Biểu đồ biến đổi của PFC trong 200 khung hình ....................... 59
Hình 3.10 Ví dụ về trường hợp thuật toán cửa sổ trượt nhận dạng nhầm
trong phân đoạn video. ......................................................................... 60
Hình 3.11 Hệ thống phát hiện chuyển cảnh đột ngột dựa vào thuật toán
cửa sổ trượt kết hợp với ngưỡng so sánh............................................ 62
Danh sách hình vẽ
x
Hình 3.12 Giao diện hệ thống phát hiện chuyển cảnh............................... 64
Hình 3.13 Thuật toán cửa sổ trượt phát hiện nhầm là chuyển cảnh ....... 66
Hình 3.14 Cả hai thuật toán đều phát hiện nhầm là chuyển cảnh ........... 67
Hình 4.1 Đường cong sai khác tích luỹ........................................................ 71
Hình 4.2 Thuật toán dò tìm các điểm có độ cong lớn ................................ 73
Hình 4.3 Ví dụ về việc trích chọn khung hình chính dựa vào giải thuật
tìm các điểm có độ cong lớn trên trong sai khác tích luỹ .................. 75
Hình 4.4 Giao diện chương trình trích chọn khung hình chính............... 77
Hình 5.1 Sơ đồ hệ thống tìm kiếm video theo nội dung trong luận văn .. 81
Hình 5.2 Mối quan hệ giữa các bảng trong cơ sở dữ liệu.......................... 85
Hình 5.3 Giao diện cửa sổ tìm kiếm video .................................................. 86
Danh sách bảng biểu
xi
DANH SÁCH BẢNG BIỂU
Bảng 2.1 So sánh giữa các không gian màu................................................ 17
Bảng 2.2 Giá trị Entropy của một số ảnh ................................................... 22
Bảng 2.3 Thời gian tìm kiếm ảnh của các phương pháp........................... 42
Bảng 2.4 Giá trị precision của các phương pháp khi số lượng ảnh lấy ra
khác nhau............................................................................................... 43
Bảng 2.5 Giá trị precision đối với các loại ảnh khác nhau khi lấy ra 50
ảnh .......................................................................................................... 45
Bảng 3.1 Kết quả thử nghiệm phân đoạn với một số loại video khác nhau
................................................................................................................. 65
Bảng 4.1 Kết quả thử nghiệm trích chọn khung hình chính với một số
video........................................................................................................ 78
Danh mục các từ viết tắt
xii
DANH MỤC CÁC TỪ VIẾT TẮT
Từ viết
tắt
Tiếng Anh Tiếng Việt
CBIR Content-Based Image Retrieval Tìm kiếm ảnh theo nội dung
CBVR Content-Based Video Retrieval Tìm kiếm video theo nội dung
CIELAB
Commission Internationale de
l’Eclairage L*-a*-b*
Không gian màu đồng nhất
L*a*b*
CIELUV
Commission Internationale de
l’Eclairage L*-u*-v*
Không gian màu đồng nhất
L*u*v*
CMY Cyan-Magenta-Yellow color space Không gian màu CMY
HSB
Hue-Saturation-Brightness color
space Không gian màu HSB
HSV Hue-Saturation-Value color space Không gian màu HSV
HWS Half-Window Size Kích thước nửa cửa sổ
LB Lower Bound Ngưỡng dưới
MPEG Motion Picture Experts Group Tiêu chuẩn mã hoá video
NVLV Người viết luận văn
PFC Pre-Frame Count
Đếm các khung hình phía
trước
RGB Red-Green-Blue color space Không gian màu RGB
SQL Structure Query Language Ngôn ngữ truy vấn có cấu trúc
UB Upper Bound Ngưỡng trên
Chương 1. Tổng quan về tìm kiếm video theo nội dung
1
CHƯƠNG 1. TỔNG QUAN VỀ TÌM KIẾM VIDEO
THEO NỘI DUNG
1.1 Đặt vấn đề
Với sự phát triển nhanh chóng của máy tính cùng với đó là các chuẩn
nén hiệu quả hơn đã làm gia tăng nhanh chóng việc lưu trữ, sử dụng các đối
tượng đa phương tiện (multimedia) như: âm thanh, hình ảnh, video,... đặc biệt
là video. Tuy nhiên, chúng thường không được sắp xếp, phân loại theo một
trình tự nào và việc truy cập thường được tiến hành bằng việc xem xét tuần
tự. Để có thể tạo được những cơ sở dữ liệu video lớn chúng ta cần tự động
hoá được quá trình đánh chỉ mục, tìm kiếm trong video. Vấn đề “tìm kiếm
video theo nội dung” (Content-Based Video Retrieval – CBVR) được tập trung
nghiên cứu trong 15 năm trở lại đây. Tuy đã có khá nhiều các nghiên cứu tập
trung vào lĩnh vực này nhưng những kết quả đạt được còn hạn chế. Việc
chuyển tự động những đặc trưng cấp thấp như: màu sắc, chuyển động,... sang
các đặc trưng cấp cao mà người sử dụng mong muốn như: đối tượng, sự kiện
là rất khó khăn. Chương này sẽ chỉ ra quá trình hình thành và phát triển của
CBVR cũng như những khó khăn trong nghiên cứu lĩnh vực này.
1.2 Giới thiệu sơ lược về CBVR
Hiện nay, phần lớn cơ sở dữ liệu video số được lưu trữ dưới dạng thô và
được gán nhãn đánh chỉ mục bằng văn bản. Đó là thế hệ thứ nhất của CBVR,
trong thế hệ này các thông tin thị giác được tách ra một cách thủ công. Xác
định các thông tin ngữ nghĩa chứa trong ảnh hay video (một đối tượng, sự
vật,...), các phần của đối tượng (đôi mắt trên khuôn mặt, chiếc thuyền trên
hồ,...) hoặc các cảnh miêu tả các khái niệm (phong cảnh, trận bão,...). Thể
hiện những thông tin đó thường dựa trên mô hình quan hệ và mô hình hướng
đối tượng. Việc tìm kiếm được thực hiện thông qua việc tìm kiếm văn bản sử
Chương 1. Tổng quan về tìm kiếm video theo nội dung
2
dụng các ngôn ngữ truy vấn truyền thống như SQL. Tuy nhiên, đánh chú
thích thủ công thường tốn rất nhiều công sức và toàn bộ quá trình đó phụ
thuộc vào chủ quan của người chú thích, mà trình độ và sự cảm nhận của mỗi
người chú thích là khác nhau.
Khác với thế hệ thứ nhất, trong thế hệ thứ hai của CBVR việc đánh chỉ
mục được thực hiện dựa trên các thuộc tính như màu sắc, kết cấu, hình dạng,
các quan hệ không gian,... Các phương pháp tập trung vào việc tự động hoá
việc đánh chỉ mục và tìm kiếm dựa vào các đặc trưng đó.
Hiện nay CBVR đang bước vào giai đoạn thứ ba, tự động hoá trong việc
đánh chỉ mục và tìm kiếm video ở mức cao (mức độ ngữ nghĩa). Tuy nhiên
các kết quả thu được còn rất khiêm tốn chỉ dừng lại ở một lĩnh vực rất hẹp
nào đó [16].
Việc mô hình hoá nội dung video là một trong những công việc quan
trọng nhất trong tìm kiếm video. M.Petkovic [1] đưa ra mô hình nội dung
video dưới dạng các mức:
• Dữ liệu thô: Bao gồm các thành phần cơ bản của video như: định
dạng, số khung hình trong một giây,...
• Các thông tin thị giác mức thấp: màu sắc, hình dạng, kết cấu,...
• Các thông tin mức ngữ nghĩa: các đối tượng và sự kiện.
Quá trình trích chọn các thông tin ngữ nghĩa là quá trình phức tạp nhất,
trong khi có thể tự động hoá trích chọn các thông tin thị giác ở mức thấp thì
việc chuyển các thông tin đó lên mức cao hơn (ngữ nghĩa) là khó khăn hơn rất
nhiều. Hiện nay trên thế giới vẫn chưa có một hệ thống nào có thể được coi là
công cụ vạn năng để thực hiện công việc đó.
Chương 1. Tổng quan về tìm kiếm video theo nội dung
3
1.3 Các nghiên cứu trên thế giới về CBVR
Trước nhu cầu ngày càng lớn trong việc quản lý dữ liệu video, nhiều
nhóm nghiên cứu đã nhảy vào cuộc. Đã có nhiều thuật toán về nén dữ liệu
video số cho kết quả rất khả quan và đang được áp dụng rộng rãi. Các định
dạng file video MPEG1, MPEG2, MPEG4, WMV, MOV, ... góp phần làm
giảm đáng kể kích thước của dữ liệu video. Nhưng chúng chỉ giúp cho việc
lưu trữ nhiều hơn trong một không gian nhỏ hơn, chứ không giải quyết được
việc lưu trữ hiệu quả để tìm kiếm. Tuy nhiên, hiện nay một số nhóm đang tiến
hành việc nghiên cứu và áp dụng vào thực tế một số phương pháp lưu trữ và
tìm kiếm video dựa vào nội dung, cho thấy đây là một hướng phát triển mới
và rất có triển vọng. Sau đây là một số nhóm tiêu biểu:
• Đại học Carnegie Mellon [2]: Đang thực hiện một dự án thư viện
thông tin cho phép người dùng truy tìm video bằng ngôn ngữ tự
nhiên. Các bước xử lý để tạo nên thư viện video: phát hiện các đoạn
cơ sở bằng cách sử dụng phương pháp độ sai khác về biểu đồ màu,
trích chọn khung hình chính, nhận dạng khuôn mặt, nhận dạng chữ
viết qua video và tìm ảnh dựa vào đặc trưng biểu đồ màu trong các
không gian màu và vân khác nhau.
• Nhóm nghiên cứu của IBM [3]: Nhóm nghiên cứu của IBM đã phát
triển một hệ thống truy tìm video theo nội dung tự động và tương tác
dựa vào những đặc điểm trực quan và mô hình thống kê. Hệ thống sử
dụng IBM Cue Video để phát hiện đoạn cơ sở và lựa chọn khung
hình chính một cách tự động.
• Đại học Johns Hopkins [4]: Nhóm nghiên cứu đã phát triển một hệ
thống truy tìm tự động video dựa vào nội dung của các khung hình
video số. Mỗi khung hình chính được đánh chỉ số bởi chính đặc trưng
lược đồ màu và vân ảnh của nó.
Chương 1. Tổng quan về tìm kiếm video theo nội dung
4
• Đại học Maryland [5]: Đại học Maryland đang làm việc với những
nhà nghiên cứu từ đại học Oulu, mở rộng các phương thức được dùng
cho việc truy tìm ảnh.
• Đại học Bắc Texas [6]: Nhóm Đại học Bắc Texas trích các khung
hình từ dữ liệu video theo chu kỳ 5 giây. Những khung hình này sẽ
qua tiến trình chọn khung hình chính để bỏ đi những khung hình thừa.
Những khung hình chính sau đó sẽ được đưa vào ứng dụng UNT’s
Brighton Image Searcher, dựa vào các độ đo toán học tương ứng với
những đặc tính quan trọng của ảnh. Độ chính xác của quá trình chọn
khung hình chính tương đối khả quan.
Có thể thấy rằng hiện nay, lĩnh vực tìm kiếm video theo nội dung khá
hấp dẫn và thu hút được sự quan tâm của ngày càng nhiều nhóm nghiên cứu
vì những nhu cầu và ứng dụng thực tế của nó. Tuy nhiên những kết quả đạt
được còn hạn chế, do vậy việc nghiên cứu, phát triển tìm kiếm video theo nội
dung là một công việc cấp thiết, cần có nhiều sự đầu tư nghiên cứu nhiều hơn
nữa.
1.4 Hướng nghiên cứu và nội dung của luận văn
Như trình bày ở phần trên, trên thế giới hiện nay có rất nhiều phương
pháp tiếp cận trong việc tìm kiếm video theo nội dung. Trong luận văn này
người viết đưa ra một phương pháp tìm kiếm video dựa trên cơ chế tìm kiếm
ảnh.
Như chúng ta đã biết, video được hình thành từ các ảnh (khung hình –
frame) liên tiếp nhau, tuỳ theo các chuẩn video khác nhau mà số khung hình
trong một giây cũng khác nhau. Các khung hình liên tiếp về mặt thời gian tạo
thành một đoạn cơ sở (shot). Một video có thể gồm nhiều đoạn cở sở ghép nối
lại, chuyển từ đoạn này sang đoạn kia có thể là chuyển cảnh đột ngột hoặc
chuyển cảnh dần dần bằng việc sử dụng một số hiệu ứng khi biên tập video
Chương 1. Tổng quan về tìm kiếm video theo nội dung
5
(dissolve, fade, wipe,...). Việc phát hiện các chuyển cảnh gọi là phân đoạn
video theo thời gian (temporal video segmentation). Đây là bước đầu tiên
trong việc tự động hoá đánh chỉ mục và tìm kiếm video.
Các khung hình trong cùng một đoạn cở sở thì thường có độ tương quan
cao với nhau. Do vậy việc tóm tắt video có thể được thực hiện bằng cách biểu
diễn mỗi đoạn cơ sở chỉ bằng một vài khung hình đại diện, gọi là các khung
hình chính (key-frame). Kỹ thuật lấy ra các khung hình chính trong đoạn
video gọi là kỹ thuật trích chọn khung hình chính (key-frame extraction).
Người sử dụng thông qua việc xem các khung hình chính có thể hiểu nhanh
được nội dung của toàn bộ video. Và thông qua việc liệt kê các khung hình
chính người sử dụng cũng có thể tìm được khung hình chính có nội dung mà
mình đang tìm kiếm. Do vậy tìm được đoạn video tương ứng chứa khung hình
chính đó. Nhưng trong một cơ sở dữ liệu lớn video thì sao? Khi đó số lượng
khung hình chính là rất lớn, người sử dụng sẽ tốn nhiều thời gian để tìm kiếm
được khung hình có nội dung mà mình mong muốn. Giải pháp mà Người viết
luận văn (NVLV) đưa ra là sử dụng cơ chế tìm kiếm ảnh theo nội dung
(Content-Based Image Retrieval) để tự động hoá công việc tìm kiếm các
khung hình chính.
Do vậy, hệ thống tìm kiếm video mà NVLV xây dựng được hình thành
từ các thành phần:
• Tìm kiếm ảnh theo nội dung
• Phân đoạn video
• Trích chọn khung hình chính
Sơ đồ khối của hệ thống được trình bày trong hình 1.1.
Chương 1. Tổng quan về tìm kiếm video theo nội dung
6
Hình 1.1 Sơ đồ hệ thống tìm kiếm video nghiên cứu trong luận văn
Với những phân tích như trên, luận văn gồm các nội dung chính như sau:
Chương 1: Tổng quan về tìm kiếm video theo nội dung
Trình bày các khái niệm và ý nghĩa của lĩnh vực CBVR, các nghiên cứu
về lĩnh vực này trên thế giới hiện nay, hướng nghiên cứu trong luận văn
Chương 2: Tìm kiếm ảnh theo nội dung áp dụng trong tìm kiếm video
theo nội dung
Chương này sẽ tìm hiểu một số phương pháp tìm kiếm ảnh hiện nay trên
thế giới, các đặc tính của ảnh, các không gian màu sắc, biểu đồ màu, Entropy
của ảnh. Phân tích các phương pháp lựa chọn và xây dựng ra một phương
pháp tìm kiếm phù hợp áp dụng trong bài toán tìm kiếm video theo nội dung.
Video Files Phân đoạn
Video
Trích chọn
key-frame
Keyframes
Browser
Đánh chỉ mục
Tìm kiếm ảnh
theo nội dung
CSDL
Keyframe
và đoạn
Kết quả:
Các đoạn
Video
Chương 1. Tổng quan về tìm kiếm video theo nội dung
7
Chương 3: Phân đoạn video
Chương này sẽ tìm hiểu, phân tích và đánh giá các phương pháp phân
đoạn video hiện nay. Đưa ra một số cải tiến nhằm nâng cao độ chính xác
trong phân đoạn
Chương 4: Trích chọn khung hình chính trong video
Trong chương này sẽ tìm hiểu một số phương pháp trích chọn khung
hình chính ứng dụng vào việc tóm tắt và đánh chỉ mục video. Việc trích chọn
khung hình chính tập trung vào giải thuật tìm các điểm có độ cong lớn trên
đường sai khác tích luỹ.
Chương 5: Xây dựng hệ thống tìm kiếm video theo nội dung dựa trên
phương pháp tìm kiếm ảnh trong các khung hình chính
Từ các lý thuyết và thử nghiệm ở các chương trước, chương này NVLV
sẽ lựa chọn và tổng hợp thành một hệ thống tìm kiếm video khá hoàn chỉnh.
Kết luận chương
Chương này đã chỉ ra mục đích ý nghĩa của hệ thống tìm kiếm video
theo nội dung cũng như những khó khăn trong nghiên cứu lĩnh vực này. Các
nghiên cứu trên thế giới hiện nay về lĩnh vực này cũng được đề cập.
Chương này cũng trình bày phạm vi nghiên cứu và cách tiếp cận của
NVLV để xây dựng hệ thống tìm kiếm video.
Chương sau sẽ tìm hiểu cơ chế tìm kiếm ảnh theo nội dung, ứng dụng
trong việc tìm kiếm video.
Chương 2. Tìm kiếm ảnh theo nội dung
8
CHƯƠNG 2. PHƯƠNG PHÁP TÌM KIẾM ẢNH
THEO NỘI DUNG ÁP DỤNG TRONG BÀI TOÁN
TÌM KIẾM VIDEO THEO NỘI DUNG
2.1 Đặt vấn đề
Như đã đề cập ở chương trước, tìm kiếm ảnh theo nội dung là một phần
của ._.hệ thống tìm kiếm video mà NVLV xây dựng. Mặt khác, các kiến thức về
CBIR là những kiến thức rất quan trọng trong việc nghiên cứu xử lý video ở
các chương tiếp, ví dụ như: cảm thụ của con người về màu sắc, tìm kiếm
trong không gian độ đo,...
2.2 Tổng quan về tìm kiếm ảnh theo nội dung
2.2.1 Giới thiệu
Trong cơ sở dữ liệu, ảnh số đóng một vai trò rất quan trọng, đặc biệt khi
khả năng lưu trữ dữ liệu của máy tính được tăng lên một cách nhanh chóng.
Khi nhu cầu về ảnh số tăng lên với khối lượng dữ liệu lớn đòi hỏi phải có một
phương pháp hiệu quả trong việc lưu trữ và tìm kiếm ảnh. Một vấn đề đặt ra
là làm sao để có thể quản lý và sử dụng chúng một cách hiệu quả khi người sử
dụng có nhu cầu tìm kiếm thông tin mà họ cần. Hiện nay phần lớn các hệ
thống mới chỉ đáp ứng tốt nhu cầu của người dùng với loại thông tin văn bản.
Từ nhu cầu thực tiễn đã có rất nhiều cố gắng nhằm giải quyết bài toán tìm
kiếm thông tin dạng hình ảnh. Bài toán này được gọi là bài toán “tìm kiếm
ảnh theo nội dung” (Content-Based Image Retrieval - CBIR). Các yêu cầu
chính đối với bài toán này là phải tìm kiếm chính xác và trả lời trong khoảng
thời gian cho phép trên một cơ sở dữ liệu ảnh lớn.
Hiện nay, có một số hệ thống tìm kiếm ảnh dựa vào từ khoá điển hình hệ
thống tìm kiếm ảnh của Google. Việc tìm kiếm này tỏ ra khá hiệu quả với
Chương 2. Tìm kiếm ảnh theo nội dung
9
người sử dụng, tuy nhiên việc xây dựng cơ sở dữ liệu ảnh đó phải thực hiện
bằng cách đánh chú thích cho từng ảnh. Công việc này thực hiện một cách thủ
công rất mất nhiều thời gian và công sức vả lại còn phụ thuộc vào chủ quan
của người nhập chú thích cho ảnh. Ở đây NVLV đi theo hướng tự động hoá
trong việc tìm kiếm và xây dựng cơ sở dữ liệu ảnh. Để làm được điều đó phải
tự động hoá trong việc trích chọn ra các đặc trưng của ảnh và bài toán tìm
kiếm ảnh trở thành bài toán tìm kiếm các đặc trưng của ảnh. Các đặc trưng
của ảnh có thể là: màu sắc, kết cấu bề mặt, hình dạng,... Đối với con người
việc nhận biết và so sánh các đặc trưng đó được thực hiện khá dễ dàng tuy
nhiên với máy tính việc nhận biết các đặc trưng đó lại không hề đơn giản.
2.2.2 Cơ chế tính toán chung của CBIR
Việc tìm kiếm ảnh được thực hiện bằng cách: người sử dụng đưa vào hệ
thống một ảnh (từ file hoặc vẽ vào) gọi là ảnh truy vấn. Sau đó hệ thống sẽ
tìm kiếm trong cơ sở dữ liệu ảnh của mình và trả lại những ảnh giống với ảnh
truy vấn nhất. Quá trình tìm kiếm và xây dựng cơ sở dữ liệu ảnh dựa vào việc
trích chọn các đặc trưng của ảnh.
Cơ chế hoạt động của hoạt hệ thống CBIR được mô tả trong hình 2.1
[17]. Toàn bộ quá trình này bắt đầu với việc phân tích và trích chọn các đặc
trưng của ảnh được xử lý bằng các thuật toán trích chọn đặc trưng, những đặc
trưng này được lưu vào cơ sở dữ liệu. Việc sử dụng thuật toán trích chọn đặc
trưng cũng được sử dụng để lấy các đặc trưng của ảnh truy vấn. Phương pháp
đo xấp xỉ sau đó sẽ so sánh những đặc trưng của truy vấn với các đặc trưng
trong cơ sở dữ liệu. Với những ảnh có đặc trưng trong cơ sở dữ liệu được cho
là “giống” với ảnh truy vấn sẽ được gửi lại cho người sử dụng như là một kết
quả cuối cùng.
Chương 2. Tìm kiếm ảnh theo nội dung
10
Trích chọn đặc trưng
Ảnh truy vấn
Trích chọn đặc trưng
Phép đo xấp xỉ
Kết quả tìm kiếm
87
23
27
19
40
54
56
10
76
23
23
34
43
12
54
86
22
26
20
40
Hình 2.1 Cơ chế hoạt động của hệ thống CBIR
2.2.3 Một số đặc trưng của ảnh
Việc trích chọn những đặc trưng từ ảnh là mục tiêu cơ bản của hệ thống
CBIR. Những đặc trưng của ảnh được trích chọn để sử dụng trong nhiều ứng
dụng như xử lý ảnh, nhận dạng ảnh,... Hầu hết các phương pháp trích chọn
các đặc trưng của ảnh tập trung vào: màu sắc, kết cấu, hình dạng [20].
a. Đặc trưng về màu sắc [17][18]
Cho đến nay màu sắc là đặc tính hình ảnh được thể hiện nhiều nhất trong
công nghệ CBIR, đầu tiên là vì tính đơn giản của việc trích thông tin màu của
ảnh đưa ra phân tích và đã có hiệu quả thông qua biểu đồ màu. Các biểu đồ
màu miêu tả các điểm màu trên những vùng màu của ảnh.
Không gian màu RGB được sử dụng rộng rãi trong việc miêu tả màu sắc
của ảnh. Nó gồm ba thành phần màu cơ bản là đỏ (Red), lục (Green), lam
(Blue). Các màu khác được tạo ra bằng cách tổng hợp ba thành phần màu cơ
Chương 2. Tìm kiếm ảnh theo nội dung
11
bản này. Tuy nhiên không gian màu RGB biến đổi không phù hợp với cảm
nhận của mắt con người. Không gian màu CIELAB và CIELUV được nghiên
cứu phát triển để phù hợp với cảm nhận của mắt người.
Việc tính toán so sánh “khoảng cách” giữa các ảnh sử dụng đặc trưng
màu sắc có thể sử dụng các phương pháp như: mô men màu, biểu đồ màu,...
Mỗi phương pháp có những đặc điểm riêng chúng ta sẽ xem xét cụ thể ở các
phần tiếp theo.
b. Đặc trưng về hình dạng [7]
Hình dạng của đối tượng trong ảnh cũng là một đặc trưng có thể được
xét đến. Đối tượng của ảnh thể hiện nội dung ảnh nhiều nhất. Ảnh được chụp
hoặc tranh được vẽ luôn với mục đích mô tả lại các đối tượng trong đó. Việc
tách riêng các đối tượng và hình dạng của chúng trong ảnh là rất khó khăn. Và
khó hơn là so sánh các đặc trưng đó thế nào. Phương pháp này chỉ nên áp
dụng cho loại ảnh đặc biệt có đặc trưng hình dạng nổi bật, dễ phân tích.
c. Đặc trưng về kết cấu (texture) [8]
Khái niệm chung về kết cấu bề mặt là phản ánh sự biểu diễn một mẫu về
không gian có vài thuộc tính đồng đều. Vào các trường hợp đặc biệt, tính
đồng đều không thể có được từ sự biểu diễn bằng một màu đơn hoặc một độ
sáng trong vùng mà yêu cầu sự tương tác của nhiều màu, độ sáng khác nhau.
Để sử dụng kết cấu trong tìm kiếm ảnh, ta cần có các đặc tính kết cấu của một
đối tượng hoặc một vùng quan tâm đến trong ảnh cung cấp đặc tính để tìm
kiếm ảnh. Ví dụ đặc trưng kết cấu tách ra từ một cảnh của đồng cỏ thì ta có
thể phân biệt được đồng cỏ và cây cối. Trong khi nếu chỉ dùng màu sắc thì có
thể tìm kiếm không chính xác.
2.3 Đặc tính màu sắc của ảnh
Con người chỉ có khả năng cảm nhận được ánh sáng có bức xạ điện từ
với bước sóng trong khoảng 350 – 780 nanomet. Cơ quan thị giác cảm nhận
Chương 2. Tìm kiếm ảnh theo nội dung
12
đượ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.
Với sự phát triển mạnh mẽ của khoa học kỹ thuậ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. Do đó, việc lựa chọn mô hình màu thích hợp và sử dụng biểu đồ lượng
hoá màu thích hợp sẽ giảm bớt độ phân giải màu. Đây là các vấn đề quan
trọng trong việc tìm kiếm ảnh dựa trên màu sắc. Màu sắc thường được biểu
diễn như là các điểm trong không gian màu ba chiều gọi là các không gian
màu.
2.3.1 Không gian màu
a. Các đặc tính của không gian màu
• Tính đồng nhất (uniform): Một không gian màu đồng nhất là một
không gian mà trong đó khoảng cách giữa các điểm trong không gian
màu là tương đương với khoảng cách nhận thức được giữa các điểm
đó của con người.
• Tính đầy đủ (complete): Một không gian màu đầy đủ là một không
gian biểu diễn được tất cả các màu mà con người có thể cảm nhận
được.
• Tính duy nhất (unique): Một không gian màu có tính duy nhất nếu hai
điểm riêng biệt trong không gian màu đại diện cho hai màu khác nhau
theo cảm nhận của con người.
Chương 2. Tìm kiếm ảnh theo nội dung
13
b. Không gian màu RGB
Phần lớn không gian màu dùng cho ảnh số và đồ hoạ máy tính là RGB
(Red-Green-Blue). Đó là không gian màu mà trong đó các màu được tạo ra
khi kết hợp tuyến tính ba thành phần màu đỏ (red), xanh lục (green), xanh lam
(blue).
Hình 2.2 Không gian màu RGB
Tuy không gian màu RGB đơn giản và được sử dụng rộng rãi nhưng nó
lại không đồng nhất về mặt nhận thức. Khoảng cách giữa hai điểm trong
không gian màu chưa chắc đã ám chỉ rằng hai màu đó là giống nhau hay
không giống nhau. Thêm vào đó, ba kênh của không gian màu RGB không
biến đổi phù hợp về mặt độ sáng.
c. Không gian màu CMY
Không gian CMY được dùng chủ yếu trong in ấn. 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. Hệ thống màu CMY theo mô hình in
trên giấy trắng và theo cách thức trừ màu từ màu trắng thay vì thêm vào từ
màu đen như hệ thống màu RGB.
Chương 2. Tìm kiếm ảnh theo nội dung
14
Hình 2.3 Không gian màu CMY
d. Không gian màu HSV
Mô hình HSV (Hue, Saturation, Value) được tạo ra từ năm 1978 bởi
Alvy Ray Smith. Nó là một phép biến đổi phi tuyến của không gian màu
RGB. Mô hình HSV giúp tách bạch màu (H, S) và độ sáng (V).
Không gian màu HSV, còn gọi là HSB (Hue, Saturation, Brightness)
định nghĩa một không gian màu gồm có ba thành phần tạo nên:
• Hue: loại màu (chẳng hạn màu đỏ, xanh, hay vàng). Có giá trị từ 0 - 360
• Saturation: độ bão hoà của màu. Có giá trị từ 0 - 100%. Độ bão hoà của
một màu càng thấp, độ xám của màu đó càng nhiều và màu đó càng mờ
(càng giống với ảnh đen trắng)
• Value, độ sáng của màu. Có giá trị từ 0 - 100%.
Chương 2. Tìm kiếm ảnh theo nội dung
15
Hình 2.4 Một số cách biểu diễn không gian màu HSV
Không gian màu HSV được sử dụng khá rộng rãi trong các ứng dụng đồ
hoạ máy tính vì nó cung cấp sự điều khiển trực tiếp đến độ chói và màu sắc.
Có một số phương pháp biểu diễn không gian màu này như bánh xe màu, hình
nón và hình trụ (hình 2.4).
Không gian màu HSV có vẻ phù hợp với cảm nhận của mắt con người
hơn không gian màu RGB, tuy nhiên người ta đã chứng minh được rằng
không gian màu này cũng không phải là không gian màu đồng nhất về nhận
thức. Do vậy, cần thiết phải xây dựng không gian màu phù hợp với cảm nhận
của con người, đó chính là không gian màu ta sẽ nghiên cứu sau đây.
e. Không gian màu có thang chia màu đồng nhất CIE
Trong một cố gắng định nghĩa một không gian màu đồng nhất về cảm
nhận, Uỷ ban Commission Internationale de l’Eclairage (CIE) đã phát triển
không gian màu L*-u*-v* (CIELUV) và L*-a*-b* (CIELAB). Không gian
màu là một hình trụ với L* hình thành nên trục đầu tiên (thẳng đứng), L* xác
định độ sáng của màu từ đen đến trắng (hình 2.5).
Không gian màu CIELUV và CIELAB được đưa ra như những sự lựa
chọn cho các không gian màu mà độ chói được thừa nhận là không đổi cho tất
cả các màu. Tầm quan trọng của màu sắc và độ chói là cân bằng nhau. Kết
quả là, trong không gian màu CIELUV và CIELAB ba đặc tính biểu diễn một
không gian màu sắc là tính đồng nhất, tính đầy đủ và tính duy nhất được đáp
ứng. Luận văn này sẽ sử dụng không gian màu CIELAB như một cơ sở cho
Chương 2. Tìm kiếm ảnh theo nội dung
16
việc miêu tả các đặc trưng màu sắc và các phép đo. Lý do cho việc lựa chọn
này bởi vì nó đáp ứng hầu hết tính thống nhất về cảm giác của không gian
màu, một đặc trưng đã không được đáp ứng ở hầu hết các không gian khác.
Để chuyển đổi từ không gian màu RGB sang không gian hai không gian
màu này phải thông qua không gian màu trung gian XYZ. Sự chuyển đổi từ
không gian màu RGB sang không gian màu CIELAB được trình bày chi tiết
trong phần phụ lục.
Hình 2.5 Không gian màu CIELAB
f. So sánh các không gian màu
Có rất nhiều không gian màu tồn tại, mỗi cái có ưu điểm và nhược điểm
riêng. Như đã đề cập, không gian màu RGB là không gian được sử dụng rộng
rãi tuy nhiên nó lại không tuyến tính về mặt cảm nhận thị giác. Thêm vào đó
không gian màu này lại phụ thuộc vào thiết bị hiển thị. Không gian màu CMY
được sử dụng hầu hết trong các máy in màu. Tuy nhiên nó cũng không thống
nhất về mặt cảm nhận. Không gian màu HSB có vài phần tương tự với không
gian màu HSV và HSI, các không gian màu này có đặc điểm và tách biệt giữa
sắc độ (màu sắc và độ bão hoà) và độ chói. Tuy nhiên các không gian màu
này cũng không đồng nhất về cảm nhận. Các không gian màu YIQ, YUV và
Chương 2. Tìm kiếm ảnh theo nội dung
17
YCrCb được sử dụng lần lượt cho các tiêu chuẩn NTSC, PAL và JPEG.
Chúng đều phụ thuộc vào thiết bị hiển thị và không đồng nhất về cảm nhận.
Thống kê so sánh giữa các không gian màu được tổng kết trong bảng 2.1.
Bảng 2.1 So sánh giữa các không gian màu
Không gian màu Đồng nhất Đầy đủ Duy nhất Độc lập thiết bị
RGB Không Có Không Không
CMY Không Có Không Không
HSL, HSV, HSI Không Có Có Không
YIQ, YUV, YCrCb Không Có Không Không
CIELAB, CIELUV Có Có Có Có
2.3.2 Biểu đồ màu (Color Histogram)
a. Định nghĩa
Biểu đồ màu của ảnh cho biết sự phân bố của các màu trong ảnh. Biểu
đồ màu H là một vector:
H={hi}
Trong đó
n
nh ii =
• i là thứ tự màu được lượng tử hoá (bin màu). Nếu Nc là số lượng màu
được lượng tử hoá thì ]1,0[ −∈ cNi
• ni: số điểm ảnh có giá trị màu là i
• n: tổng số điểm ảnh có trong ảnh
Chương 2. Tìm kiếm ảnh theo nội dung
18
Hình 2.6 Mô tả biểu đồ màu
b. Ý nghĩa của biểu đồ màu
Đối với một màu ci, hi thể hiện phần trăm số điểm ảnh có màu ci trong
ảnh I. Nói cách khác với mỗi điểm ảnh trong ảnh I thì hi thể hiện xác suất để
điểm ảnh đó có màu là ci.
Biểu đồ màu là một đặc trưng rất quan trọng của ảnh. Có thể dùng nó để
thực hiện tìm kiếm ảnh theo nội dung.
c. Ưu điểm, nhược điểm của biểu đồ màu
• Ưu điểm
o Tính toán biểu đồ màu ít tốn chi phí, đơn giản, nhanh chóng.
o Biểu đồ màu bất biến đối với một số phép biến đổi như: xoay, co,
giãn.
• Nhược điểm
Biểu đồ màu chỉ xét phân bố toàn cục về màu của ảnh mà không
xét đến yếu tố cục bộ về vị trí, làm mất thông tin về quan hệ
không gian giữa các màu. Dẫn đến việc có thể có nhiều ảnh khác
nhau nhưng lại có cùng biểu đồ màu (hình 2.7).
Chương 2. Tìm kiếm ảnh theo nội dung
19
Hình 2.7 Những ảnh khác nhau nhưng có biểu đồ màu giống nhau
2.3.3 Biểu đồ tương quan màu (Color Correlogram)
a. Giới thiệu
Biểu đồ màu đơn giản nhưng thiếu thông tin về không gian. Một đặc
trưng mới được giới thiệu gọi là biểu đồ tương quan màu.
Biểu đồ tương quan màu hứa hẹn mô tả không chỉ là phân phối màu của
các điểm ảnh mà còn là sự tương quan về không quan giữa các cặp màu.
b. Cách tính
Gọi [D] là tập gồm D khoảng cách d1, d2,..., dD. Biểu đồ tương quan màu
của ảnh I được xác định với cặp màu (ci, cj) và khoảng cách d là: xác suất cặp
điểm ảnh bất kỳ p1 có màu là ci và p2 có màu là cj và khoảng cách giữa p1, p2
là d.
Chương 2. Tìm kiếm ảnh theo nội dung
20
c. Biểu đồ tự tương quan màu
Nếu chúng ta xét đến tất cả sự kết hợp có thể có của các cặp màu, kích
thước của biểu đồ tương quan màu sẽ rất lớn, thời gian tính toán sẽ lâu. Do
đó, một phiên bản đơn giản hơn được sử dụng, gọi là biểu đồ tự tương quan
màu. Biểu đồ này chỉ quan tâm đến sự tương quan về không gian giữa những
màu giống nhau và do đó giảm được số chiều và chi phí tính toán.
d. So sánh với biểu đồ màu
So với biểu đồ màu thì biểu đồ (tự) tương quan màu không những có
được thông tin về phân bố màu của ảnh mà còn có được thông tin về không
gian của ảnh. Do vậy, việc sử dụng biểu đồ (tự) tương quan màu để tìm kiếm
ảnh theo nội dung sẽ chính xác hơn. Tuy nhiên, một nhược điểm rất lớn của
biểu đồ (tự) tương quan màu đó là chi phí tính toán lớn hơn nhiều so với việc
tính toán biểu đồ màu.
2.4 Đặc trưng Entropy của ảnh
2.4.1 Đặt vấn đề
Như đã đề cập ở phần trên, biểu đồ màu được biết đến như là một đặc
trưng quan trọng của ảnh có thể dùng để đánh chỉ số phục vụ xây dựng cơ sở
dữ liệu ảnh. Tuy nhiên, nhược điểm của biểu đồ màu đó là kích thước số
chiều lớn, do đó việc tìm kiếm so sánh ảnh mất nhiều thời gian đặc biệt với cơ
sở dữ liệu ảnh lớn.
Trong một vài thập kỷ trở lại đây đã có nhiều nghiên cứu về giảm số
chiều của biểu đồ màu xuống, các kỹ thuật này có khả năng giảm không gian
biểu đồ màu từ n xuống k>1. Trong phần này ta sẽ tìm hiểu cách thức để giảm
số chiều của không gian biểu đồ màu xuống 1 bằng việc sử dụng lý thuyết
Entropy.
Chương 2. Tìm kiếm ảnh theo nội dung
21
Ở đây, Entropy của một ảnh được hiểu là độ đo lượng thông tin của ảnh
đó. Như ta đã biết hàm Entropy Shannon ánh xạ một vector n chiều đến tập số
thực và do đó có thể hiểu như là giảm số chiều không gian xuống 1.
2.4.2 Lý thuyết thông tin và hàm Entropy
a. Định nghĩa
Cho x là một biến ngẫu nhiên với không gian mẫu X={x1,..., xN} và độ
đo xác suất P(xn)=pn. Entropy của x được định nghĩa là:
∑
=
−=
N
n
nn ppxH
1
)log()( (2.1)
Ví dụ: Cho X={0,1}, P(0)=p còn P(1)=1-p thì Entropy của x được tính
như sau:
)1log()1()log()( ppppxH −−−−=
Hình 2.8 Hàm Entropy trong không gian hai chiều
b. Một số tính chất của hàm Entropy
• H(x) ≥ 0. Entropy là một đại lượng không âm.
• H(p1,..., pn) ≤ H(1/n,...., 1/n) = log(n). Entropy của hàm mật độ xác
suất lớn nhất khi các giá trị được phân bố đều.
Chương 2. Tìm kiếm ảnh theo nội dung
22
2.4.3 Entropy ảnh là một đặc trưng
Như ta đã biết biểu đồ màu có thể coi là một hàm mật độ xác suất phân
bố màu của ảnh, do vậy có thể tính được Entropy của ảnh dựa trên biểu đồ
màu. Giả sử một ảnh có biểu đồ màu V={vi}, số bin màu là n thì Entropy của
ảnh đó được tính như sau:
∑−
=
−=
1
0
)( )log(
n
k
iiv vvH (2.2)
Bảng 2.2 đưa ra Entropy của một số ảnh được tính bởi công thức trên. Ta
thấy ảnh Clown, Lena, Mandril có phân bố màu phức tạp do đó chúng có giá
trị Entropy cao hơn còn các ảnh như Pleides có giá trị Entropy thấp hơn.
Bảng 2.2 Giá trị Entropy của một số ảnh
Đối với các ảnh số Entropy có một số ý nghĩa như sau:
• Ước lượng số bit cần thiết để mã hoá điểm ảnh
• Đo sự phân bố ngẫu nhiên của của màu trong ảnh
Chương 2. Tìm kiếm ảnh theo nội dung
23
Trong bảng 2.2 ta thấy sự khác nhau giữa các giá trị Entropy của các ảnh
dẫn đến sự khác nhau của các ảnh tương ứng. Ví dụ ảnh Mona Lisa có
Entropy = 3.63569 thì rất khác biệt so với ảnh Pleides có Entropy = 2.13897.
Tóm lại, Entropy là một đặc trưng quan trọng của ảnh có số chiều bằng
1. Có thể dùng Entropy thực hiện tìm kiếm ảnh theo nội dung với tốc độ rất
nhanh để thu gọn vùng tìm kiếm.
2.5 Phép đo khoảng cách
2.5.1 Đặt vấn đề
Để thực hiện tìm kiếm ảnh ta phải lượng hoá được sự giống nhau hay
khác nhau giữa các ảnh. Làm sao phải tìm ra một độ đo để dựa vào đó ta có
thể chỉ ra rằng ảnh này giống với ảnh truy vấn hơn là ảnh khác. Điều này
không chỉ hữu ích trong việc tìm kiếm ảnh mà nó còn rất quan trọng trong các
ngành khoa học máy tính khác đặc biệt là trong lĩnh vực nhận dạng.
2.5.2 Một số tính chất của độ đo
Giả sử có một tập các đối tượng {X}. x, y là các đối tượng thuộc X. Hàm
khoảng cách d giữa x và y là một số thực thoả mãn các tính chất sau (d càng
nhỏ thì các đối tượng càng giống nhau và ngược lại) [19]:
• 0y)(x,,, ≥∈∀ dXyx
• x)(y,y) (x,,, ddXyx =∈∀
• 0 x)(x,, =∈∀ dXx
• 0y) (x,,, >⇒≠∈∀ dyxXyx
Nếu d thực sự là một hàm của độ đo mét (metric) thì nó phải thoả mãn
bất đẳng thức tam giác sau:
• ),(),(y) (x,,,, yzdzxddXzyx +≤∈∀
Chương 2. Tìm kiếm ảnh theo nội dung
24
Và cặp (X, d) được gọi là không gian độ đo mét (metric space).
2.5.3 Một số độ đo thông dụng
Trong một không gian thuộc tính k chiều, mỗi đối tượng trong không
gian đó là một điểm và được biểu diễn bởi một vector k chiều. Việc tính toán
khoảng cách giữa các điểm trong không gian đó được thực hiện bằng một số
hàm khoảng cách. Được sử dụng rộng rãi nhất là họ các hàm khoảng cách Ls
[19]:
ssk
i
iikks yxyyxxL
/1
1
11 )),...,(),,...,(( ⎟⎟⎠
⎞
⎜⎜⎝
⎛ −= ∑
=
(2.3)
Trong hình dưới, bên trái biểu diễn kết quả tìm kiếm với điểm truy vấn
là q khoảng cách truy vấn d. Hình bên phải miêu tả tập hợp các điểm có cùng
khoảng cách với điểm trung tâm cho một số hàm khoảng cách trong họ Ls.
Với s khác nhau ta có các hàm khoảng cách khác nhau.
Hình 2.9 Mô tả một số hàm khoảng cách thuộc họ Ls
a. Khoảng cách Manhattan (L=1)
Còn được gọi là khoảng cách “city-block”
∑
=
−=
k
i
iikk yxyyxxL
1
111 )),...,(),,...,(( (2.4)
Chương 2. Tìm kiếm ảnh theo nội dung
25
b. Khoảng cách Ơcơlit (Euclidean) (L=2)
2/12
1
112 )),...,(),,...,(( ⎟⎟⎠
⎞
⎜⎜⎝
⎛ −= ∑
=
k
i
iikk yxyyxxL (2.5)
c. L=∞
Khi ∞→L thì khoảng cách giữa hai điểm trở thành sự khác nhau lớn nhất
của hai toạ độ tương ứng của hai điểm.
ii
k
ikk
yxyyxxL −=
=∞ 111
max)),...,(),,...,(( (2.6)
2.5.4 Các độ đo được sử dụng trong tìm kiếm ảnh theo nội dung
Trong quá trình tìm kiếm ảnh dựa vào nội dung điều quan trọng là xác
định mức độ giống nhau giữa hai ảnh dựa vào hai đặc trưng của hai ảnh cần
so sánh. Do đó, cần một giá trị để biểu thị cho sự giống nhau này, có nhiều
cách để tính giá trị này.
a. So sánh điểm ảnh
Trong phương pháp này việc tính toán khoảng cách dựa trên sự so sánh
từng cặp điểm ảnh (pixel) tương ứng trong hai ảnh.
YX
yxPyxP
jiD
X
x
Y
y
ji
.
),(),(
),( 1 1
∑∑
= =
−
= với ảnh đen trắng (2.7)
YX
cyxPcyxP
jiD
X
x
Y
y c
ji
.
),,(),,(
),( 1 1
∑∑∑
= =
−
= với ảnh màu
Trong đó:
• i, j là hai ảnh cần so sánh có kích thước là X × Y.
• Pi(x,y) là giá trị cường độ của điểm ảnh tại toạ độ (x,y) của ảnh i
• c là thành phần màu (ví dụ { }BGRc ,,∈ )
Chương 2. Tìm kiếm ảnh theo nội dung
26
Phương pháp này có một số nhược điểm:
• Yêu cầu các ảnh phải có kích thước giống nhau
• Khối lượng tính toán lớn
• Cơ sở dữ liệu đánh chỉ mục ảnh lớn
b. So sánh biểu đồ màu
Giả sử n là số bin màu của biểu đồ màu. Việc so sánh sự khác nhau giữa
hai ảnh được thực hiện bằng cách so sánh biểu đồ màu của chúng. Do vậy
trong cơ sở dữ liệu ta sẽ lưu trữ biểu đồ màu của các ảnh.
Ta có thể sử dụng các hàm khoảng cách như L1, L2 hay L∞ như phần
2.5.3 đã đề cập.
Dùng khoảng cách Ls:
ssn
k
jis kHkHjiD
/1
1
0
)()(),( ⎟⎟⎠
⎞
⎜⎜⎝
⎛ −= ∑−
=
(2.8)
Như chúng ta đã biết việc so sánh biểu đồ màu được thực hiện khá đơn
giản và thuận tiện, tuy nhiên nó lại có một nhược điểm là không chứa thông
tin về không gian của ảnh do vậy hai ảnh khác nhau có thể có biểu đồ màu
như nhau. Để khắc phục tình trạng đó có thể thêm thông tin về không gian
vào trong biểu đồ màu bằng cách đơn giản như sau: Ta chia ảnh thành các
vùng xác định và tính biểu đồ màu cục bộ của từng vùng và so sánh biểu đồ
màu giữa các vùng tương ứng trong hai ảnh khác nhau [18].
Ví dụ trong hình dưới ta chia ảnh thành bốn vùng như sau:
R1 R2
R3 R4
Chương 2. Tìm kiếm ảnh theo nội dung
27
Hình 2.10 Tính và so sánh ảnh bằng biểu đồ màu cục bộ
Phương pháp tính biểu đồ màu cục bộ này có ưu điểm đã có được thông
tin về không gian của ảnh. Tuy nhiên có một số nhược điểm sau:
• Khối lượng tính toán lớn
• Nhạy cảm với các phép xoay, thu phóng ảnh
2.6 Xây dựng phần mềm tìm kiếm ảnh ứng dụng trong
hệ thống tìm kiếm video
Sau khi đã nghiên cứu, tìm hiểu cơ sở lý thuyết một số phương pháp tìm
kiếm ảnh theo nội dung tập trung vào phương pháp tìm kiếm ảnh dựa trên đặc
trưng màu sắc và đặc trưng Entropy của ảnh. Trong phần này sẽ tổng hợp và
xây dựng một kiến trúc phần mềm tìm kiếm ảnh theo nội dung đưa ra mô hình
giải thuật thực hiện việc thử nghiệm và đánh giá kết quả nhận được. Phần
mềm này sẽ là một phần trong hệ thống tìm kiếm video mà người viết xây
dựng.
Một số câu hỏi sẽ phải được giải quyết trong phần này:
• Sử dụng không gian màu nào?
• Sử dụng phương pháp tiếp cận nào?
Chương 2. Tìm kiếm ảnh theo nội dung
28
• Làm sao tăng được tốc độ tìm kiếm?
Ở đây, NVLV thử nghiệm với hai không gian màu là: RGB và CIELAB.
Dùng hai phương pháp là: so sánh biểu đồ màu và so sánh Entropy.
Cơ sở dữ liệu ảnh thử nghiệm là 1000 ảnh gồm 10 nhóm khác nhau, mỗi
nhóm gồm 100 ảnh được lấy từ [35]. Phần tiếp theo sẽ trình bày các cách tiếp
cận khác nhau trong tìm kiếm ảnh theo nội dung dựa trên phần mềm mà
NVLV xây dựng.
2.6.1 Tìm kiếm ảnh sử dụng phương pháp so sánh biểu đồ màu
trong không gian màu RGB
Việc tính biểu đồ màu với không gian màu RGB được thực hiện bằng
cách tính thành 3 biểu đồ màu RGB độc lập (hình 2.11). Số bin màu cho mỗi
biểu đồ là 256 (từ 0 đến 255).
Hình 2.11 Biểu đồ màu Red, Green, Blue độc lập
Hệ thống tìm kiếm ảnh theo nội dung phải thực hiện hai giai đoạn: giai
đoạn thứ nhất là xây dựng cơ sở dữ liệu ảnh, giai đoạn thứ hai là tìm kiếm ảnh
theo yêu cầu của người dùng. Quá trình này được thể hiện trên hình 2.12.
Chương 2. Tìm kiếm ảnh theo nội dung
29
Xây dựng cơ sở dữ liệu ảnh được thực hiện bằng cách đọc lần lượt từng
ảnh → tính biểu đồ màu R, G, B → lưu vào cơ sở dữ liệu ba biểu đồ màu ứng
với mỗi ảnh, mỗi biểu đồ màu kích thước 256.
Hình 2.12 Sơ đồ khối hệ thống tìm kiếm ảnh sử dụng phương pháp so
sánh biểu đồ màu trong không gian màu RGB
Sau khi xây dựng xong cơ sở dữ liệu ảnh, ta có thể thực hiện việc tìm
kiếm ảnh bằng cách đưa vào chương trình một ảnh truy vấn, chương trình sẽ
tính ba biểu đồ màu R, G, B của ảnh truy vấn và tính khoảng cách giữa ảnh
truy vấn với các ảnh trong cơ sở dữ liệu dựa trên công thức ở mục 2.5.4
{ }∑∑ = −=
255
0,,
1 )()(),(
k
ji
BGR
kHkHjiD (2.9)
Việc tính khoảng cách dựa vào khoảng cách L1. Sau khi đã tính xong
khoảng cách của ảnh truy vấn với tất cả các ảnh trong cơ sở dữ liệu kết quả sẽ
là các ảnh được sắp xếp theo chiều tăng dần của khoảng cách với ảnh truy
vấn.
Hình 2.13 là kết quả tìm kiếm với 20 ảnh có khoảng cách gần nhất với
ảnh truy vấn (giao diện “Kết quả tìm kiếm” trong phần mềm “Tìm kiếm ảnh
theo nội dung” mà NVLV xây dựng).
Các ảnh
trong
CSDL
Tính biểu
đồ màu
R, G, B
CSDL
So sánh
Ảnh truy
vấn
Tính biểu
đồ màu
R, G, B
Các ảnh
kết quả
Chương 2. Tìm kiếm ảnh theo nội dung
30
Hình 2.13 Kết quả tìm kiếm ảnh dựa trên không gian màu RGB (ảnh
truy vấn bên phải)
2.6.2 Tìm kiếm ảnh sử dụng phương pháp so sánh biểu đồ màu
trong không gian màu CIELAB
Như trong phần 2.3.1 đã phân tích, không gian màu RGB là không đồng
nhất với cảm nhận của mắt con người do đó uỷ ban CIE đã đưa ra không gian
màu CIELAB có đặc tính đồng nhất với cảm nhận của mắt người.
Công việc đầu tiên khi xây dựng biểu đồ màu là sử dụng không gian màu
nào và lượng tử hoá không gian màu đó ra sao. Ở đây ta sử dụng không gian
màu CIELAB, khi đọc ảnh từ file ta thu được dữ liệu ảnh dưới dạng RGB do
vậy cần có sự chuyển đổi sang không gian màu CIELAB vấn đề này được đề
cập trong phần phụ lục. Việc lượng tử hoá để phục vụ việc xây dựng biểu đồ
màu NVLV lượng tử hoá như sau:
• Lượng tử hoá L* thành 4 mức đều nhau
• Lượng tử hoá a* thành 8 mức đều nhau
• Lượng tử hoá b* thành 8 mức đều nhau
Chương 2. Tìm kiếm ảnh theo nội dung
31
Kết quả có tổng cộng 4×8×8 màu tức biểu đồ màu có 256 bin màu.
Hình 2.14 Biểu đồ màu trong không gian màu CIELAB
Sơ đồ khối hệ thống được trình bày trong hình 2.15.
Hình 2.15 Sơ đồ khối hệ thống tìm kiếm ảnh sử dụng phương pháp so
sánh biểu đồ màu trong không gian màu CIELAB
Hình 2.16 là kết quả tìm kiếm ảnh với không gian màu CIELAB 256
mức
Các ảnh
trong
CSDL
Tính biểu
đồ màu
CIELAB
CSDL
So sánh
Ảnh truy
vấn
Tính biểu
đồ màu
CIELAB
Các ảnh
kết quả
Chương 2. Tìm kiếm ảnh theo nội dung
32
Hình 2.16 Kết quả tìm kiếm ảnh dựa trên không gian màu CIELAB (ảnh
truy vấn bên phải)
Nhận xét: Sau khi thử nghiệm với nhiều ảnh truy vấn khác nhau, NVLV
nhận thấy so sánh với phương pháp sử dụng không gian màu RGB, thì trong
hầu hết trường hợp phương pháp sử dụng không gian màu CIELAB cho kết
quả chính xác hơn. Tuy nhiên việc xây dựng cơ sở dữ liệu khi sử dụng không
gian màu CIELAB mất nhiều thời gian hơn RGB do quá trình chuyển đổi từ
RGB sang CIELAB khá phức tạp và phải thực hiện với từng điểm ảnh.
2.6.3 Tìm kiếm ảnh sử dụng phương pháp Entropy
Như đã phân tích Entropy là một đặc trưng của ảnh có số chiều bằng 1.
Do vậy sử dụng Entropy sẽ cho kết quả tìm kiếm rất nhanh. Tuy nhiên đôi khi
nó cũng đem lại những kết quả không chính xác.
Để tăng độ chính xác NVLV sử dụng ba giá trị Entropy ứng với ba biểu
đồ màu R, G, B để đặc trưng cho mỗi ảnh.
Chương 2. Tìm kiếm ảnh theo nội dung
33
Hình 2.17 Giá trị Entropy ứng với các biểu đồ màu R, G, B
Sơ đồ khối của hệ thống tìm kiếm ảnh dựa vào đặc trưng Entropy được
thể hiện trên hình 2.18.
Hình 2.18 Sơ đồ khối hệ thống tìm kiếm ảnh sử dụng phương pháp so
sánh Entropy
Việc tính khoảng cách giữa hai ảnh i và j dựa trên đặc trưng Entropy
được tính theo công thức sau:
)()()()()()(),( BBGGRR jEiEjEiEjEiEjiD −+−+−= (2.10)
Tính
Entropy
ER,EG,EB
Các ảnh
trong
CSDL
Tính biểu
đồ màu
R, G, B
CSDL
So sánh
Ảnh truy
vấn
Tính biểu
đồ màu
R, G, B
Các ảnh
kết quả
Tính
Entropy
ER,EG,EB
Chương 2. Tìm kiếm ảnh theo nội dung
34
Trong đó ER, EG, EB là Entropy ứng với biểu đồ màu R, G, B của ảnh.
Hình 2.19 Kết quả tìm kiếm ảnh dựa trên phương pháp Entropy (ảnh
truy vấn bên phải)
Sau khi thử nghiệm với một số ảnh truy vấn có thể thấy rằng có nhiều
trường hợp có kết quả tìm kiếm không chính xác. Ví dụ trên hình 2.19 ảnh
truy vấn là “con ngựa trên cánh đồng” tuy nhiên trong 20 kết quả đầu tiên trả
về có khá nhiều ảnh hoàn toàn khác với nội dung ở trên như ảnh về bãi biển,
món ăn,... Điều đó chứng tỏ một điều rằng có những ảnh có Entropy giống
nhau nhưng lại có nội dung hoàn toàn khác nhau. Ví dụ hai ảnh có biểu đồ
màu như hình 2.20 sẽ có Entropy giống nhau:
Hình 2.20 Hai ảnh có biểu đồ màu khác nhau nhưng lại có Entropy giống
nhau
Bin
H
Bin
H
Chương 2. Tìm kiếm ảnh theo nội dung
35
Để nâng cao hiệu qu._.h chọn khung hình chính
Khi xem xét đường sai khác tích luỹ ta có thể biết được sự thay đổi về
nội dung qua các khung hình trong toàn bộ đoạn video. Các chỗ có độ dốc lớn
chỉ ra rằng có những sự thay đổi đáng kể trong video có thể do: một vật
chuyển động, sự di chuyển của camera. Việc xác định các điểm có độ cong
lớn trên đường sai khác tích luỹ có thể được sử dụng trong việc xác định
khung hình nào là khung hình chính trong đoạn video. Khung hình chính
được chọn là khung hình nằm chính giữa hai điểm có độ cong lớn liên tiếp
[14]. Để tìm các điểm có độ cong lớn ta sử dụng thuật toán được đưa ra bởi
Chetverikov và các cộng sự [30]. Thuật toán được phát triển để phân tích các
điểm nhô lên trong đường cong trong mặt phẳng hai chiều. Các điểm có độ
cong lớn được xác định bởi hai quá trình:
Quá trình thứ nhất: thuật toán sẽ xác định các điểm có thể là (ứng cử
viên) các “điểm có độ cong lớn”. Với mỗi điểm P trên đường cong thuật toán
sẽ cố gắng nội tiếp một tam giác vào đường cong và nhận P làm đỉnh. Với
Chương 4. Trích chọn khung hình chính trong video
73
mỗi một tam giác ta sẽ xác định được một góc mở α(P) tương ứng với điểm
P. Các tam giác khác có đỉnh là P và các đỉnh khác là các điểm trong cửa sổ
kích thước w mà P làm điểm giữa sẽ xem xét; tam giác có góc nhọn nhất sẽ
được giữ lại có thể là điểm có độ cong lớn. Quá trình này được miêu tả trong
hình 4.2.
Hình 4.2 Thuật toán dò tìm các điểm có độ cong lớn
Giả sử khoảng cách giữa P và O là dPO, khoảng cách giữa P và R là dPR
và giữa O và R là dOR, góc mở α ứng với tam giác OPR là:
PROP
ORPROP
dd
ddd
..2
arccos
222 −+=α (4.2)
Một tam giác thoả mãn ràng buộc về khoảng cách giữa các điểm (chỉ
quan tâm theo phương trục hoành)
maxmin dOPd xx ≤−≤ (4.3)
maxmin dRPd xx ≤−≤
Chương 4. Trích chọn khung hình chính trong video
74
và thoả mãn về góc
maxαα ≤ (4.4)
được gọi là một tam giác có thể được chấp nhận. Ràng buộc (4.3) nói về độ
mở của cửa sổ; ràng buộc (4.4) được sử dụng để loại bỏ các góc quá tù (độ
cong nhỏ). Góc mở nhọn nhất của các tam giác có thể được chấp nhận ứng
với điểm P
⎭⎬
⎫
⎩⎨
⎧ == ^OPRmin)( αα αP (4.5)
Nếu một điểm mà không có tam giác có thể được chấp nhận, điểm đó sẽ
bị loại bỏ và gán cho nó một góc mặc định là π .
Quá trình thứ hai: các điểm có thể là (ứng cử viên) các “điểm có độ cong
lớn” mà có góc nhọn hơn các điểm lân cận nó (trong một khoảng cách xác
định) sẽ được phân loại là các điểm có độ cong lớn thực sự. Một điểm P là
điểm ứng cử cho điểm có độ cong lớn sẽ bị loại bỏ nếu nó có một điểm lân
cận N mà N có góc nhọn hơn P tức:
)()( NP αα > (4.6)
Một điểm N được gọi là lân cận P nếu thoả mãn:
maxdNP xx ≤− (4.7)
Trong thử nghiệm khoảng cách nhỏ nhất giữa các điểm dmin được lấy
luôn luôn bằng 1, do đó chỉ còn hai tham số ảnh hưởng đến kết quả của thuật
toán đó là dmax và αmax. Trong đó tham số quan trọng nhất là αmax nó quyết
định đến tập các góc có thể được chấp nhận nhiều hay ít. Nếu αmax lớn sẽ
nhiều điểm hơn trở thành điểm ứng cử có độ cong lớn, và ngược lại αmax nhỏ
hơn thì chỉ những góc rất nhọn mới được chọn.
Khi các điểm có độ cong lớn được xác định, khung hình chính có thể
được lấy ra bằng cách lấy khung hình ở điểm chính giữa hai điểm có độ cong
Chương 4. Trích chọn khung hình chính trong video
75
lớn liền nhau [14]. Hình 4.3 miêu tả quá trình làm việc của thuật toán. Hình
phía trên miêu tả một đoạn video dưới dạng các khung hình.
Hình 4.3 Ví dụ về việc trích chọn khung hình chính dựa vào giải thuật
tìm các điểm có độ cong lớn trên trong sai khác tích luỹ
Chú ý rằng khung hình đầu tiên và cuối cùng của đoạn video luôn được
gán là điểm có độ cong lớn. Các khung hình là điểm giữa của của hai điểm có
độ cong lớn liền nhau được lựa chọn là khung hình chính (ở trong hình giữa
của hình 4.3 các điểm hình tam giác là các điểm có độ cong lớn, các điểm
hình tròn là các điểm tại đó khung hình được chọn làm khung hình chính).
∇ - điểm có độ cong lớn
Ο - điểm lấy khung hình chính
Chương 4. Trích chọn khung hình chính trong video
76
Nếu đoạn video không có nhiều nội dung biến đổi thì các khung hình sẽ có độ
tương quan cao với nhau do vậy đường sai khác tích luỹ giữa các khung hình
sẽ không có các điểm có độ cong lớn, và khung hình có thể được tóm tắt chỉ
bằng một khung hình chính (đó là khung hình nằm chính giữa đoạn).
Một ưu điểm của thuật toán này là việc trích chọn khung hình chính
được thực hiện mà chưa cần xử lý toàn bộ đoạn video. Để dò tìm các điểm có
độ cong lớn ta có thể giới hạn việc xử lý tính toán khoảng cách giữa các
khung hình trong một cửa sổ định trước. Do đó điểm có độ cong lớn có thể
được xác định trong khi tính toán khoảng cách giữa các khung hình và khung
hình chính được lấy ra ngay khi điểm có độ cong lớn thứ hai được phát hiện
ra.
4.4 Xây dựng phần mềm trích chọn khung hình chính
Thuật toán trích chọn khung hình chính được sử dụng để xây dựng hệ
thống là thuật toán tìm các điểm cong lớn trên đường sai khác tích luỹ đã đề
cập chi tiết trong phần 4.3.3.
Để xây dựng đường sai khác tích luỹ giữa các khung hình trước hết ta
tính khoảng cách giữa các khung hình liền nhau dựa vào công thức (4.1). Ở
đây ta sử dụng phương pháp so sánh biểu đồ màu trong không gian màu đồng
nhất CIELAB do tính đồng nhất, tính đầy đủ và tính duy nhất được đáp ứng
[17].
Như đã nói phần 4.3.3, thuật toán trích chọn khung hình chính dựa vào
phương pháp tìm các điểm có độ cong lớn trên đường sai khác tích luỹ ảnh
hưởng bởi hai tham số: kích thước của của cửa sổ (dmax) và giá trị lớn nhất của
góc (αmax). Việc thử nghiệm được thực hiện với kích thước cửa sổ là 3 và góc
αmax=176o đó là sự cân bằng giữa độ phức tạp tính toán và số lượng các khung
hình chính được lấy ra trong mỗi đoạn video.
Chương 4. Trích chọn khung hình chính trong video
77
Hình 4.4 Giao diện chương trình trích chọn khung hình chính
Thuật toán được chạy thử nghiệm với một số loại video khác nhau, kết
quả được trình bày trong bảng 4.1
Chương 4. Trích chọn khung hình chính trong video
78
Bảng 4.1 Kết quả thử nghiệm trích chọn khung hình chính với một số
video
STT Loại
video
Số
khung
hình
Số
đoạn
Số
khung
hình
chính
Số khung
hình
chính/đoạn
Số khung
hình/Số
khung
hình
chính
Tỷ lệ
nén
1 Động
vật
1301 4 5 1.25 260.2 99.62%
2 Cánh
đồng
750 3 3 1.00 250.0 99.60%
3 Trong
nhà
2300 6 6 1.00 383.3 99.74%
4 Đồi núi 1050 3 3 1.00 350.0 99.71%
5 Quay từ
máy bay
199 2 2 1.00 99.5 98.99%
6 Nấu ăn 1250 3 23 7.67 54.3 98.16%
7 Dưới
đáy biển
300 2 2 1.00 150.0 99.33%
8 Phong
cảnh
1750 9 11 1.22 159.1 99.37%
Chương 4. Trích chọn khung hình chính trong video
79
Kết luận chương
Trong chương này chúng ta đã tìm hiểu một số phương pháp trích chọn
khung hình chính ứng dụng vào việc tóm tắt và đánh chỉ mục video. Đây là
một phần hết sức quan trọng trọng trong việc xây dựng hệ thống tìm kiếm
video.
Việc trích chọn khung hình chính tập trung vào giải thuật tìm các điểm
có độ cong lớn trên đường sai khác tích luỹ. Tại những điểm có độ cong lớn
có những sự thay đổi đáng kể trong video. Khung hình chính được chọn là
khung hình nằm chính giữa hai điểm có độ cong lớn liên tiếp.
Từ những cơ sở lý thuyết đó đã xây dựng được chương trình trích trọn
khung hình chính thử nghiệm, đánh giá trên một số loại video khác nhau.
Chương sau sẽ trình bày cách thức tổng hợp các nghiên cứu trong các
chương trước để xây dựng nên hệ thống tìm kiếm video hoàn chỉnh.
Chương 5. Xây dựng hệ thống tìm kiếm video theo nội dung
80
CHƯƠNG 5. XÂY DỰNG HỆ THỐNG TÌM KIẾM
VIDEO THEO NỘI DUNG DỰA TRÊN PHƯƠNG
PHÁP TÌM KIẾM ẢNH TRONG CÁC KHUNG HÌNH
CHÍNH
5.1 Lựa chọn phương pháp xây dựng
Như đã đề cập trong chương 1, trên thế giới hiện nay có rất nhiều
phương pháp tiếp cận trong việc tìm kiếm video theo nội dung. Trong luận
văn này người viết đưa ra một phương pháp tìm kiếm video dựa trên việc tìm
kiếm ảnh, tuy nhiên không phải tìm kiếm trên mọi khung hình mà chỉ tìm
trong các khung hình chính. Điều này làm giảm thời gian tìm kiếm đi rất
nhiều lần.
Do vậy hệ thống là sự kết hợp của các lĩnh vực:
• Tìm kiếm ảnh theo nội dung: đề cập trong chương 2
• Phân đoạn video: đề cập trong chương 3
• Trích chọn khung hình chính: đề cập trong chương 4
5.2 Các mô-đun của hệ thống
Sơ đồ khối của hệ thống được trình bày trong hình 5.1. Đầu vào của hệ
thống là các file video từ nhiều nguồn khác nhau. Các video này được phân
đoạn thành các đoạn cơ sở, sau đó trong mỗi đoạn sẽ trích chọn ra một số các
khung hình đại diện (key-frame). Các khung hình đại diện này được trích
chọn đặc trưng và lưu vào trong cơ sở dữ liệu. Việc tìm kiếm được thực hiện
theo hai cách:
• Cách thứ nhất: người sử dụng có thể liệt kê (browsing) các khung
hình chính của các đoạn video. Khi quan sát các khung hình chính
Chương 5. Xây dựng hệ thống tìm kiếm video theo nội dung
81
người sử dụng có thể hình dung được nội dung của đoạn video chứa
khung hình đó là gì và có thể lựa chọn một đoạn video nào đó.
• Cách thứ hai: người sử dụng đưa vào một ảnh và mong muốn tìm các
đoạn video có chứa các khung hình có nội dung gần giống với ảnh
đưa vào truy vấn. Hệ thống sẽ trích chọn đặc trưng của ảnh truy vấn
đó so sánh với các khung hình chính trong cơ sở dữ liệu và trả lại các
đoạn video có chứa các khung hình chính gần giống với ảnh truy vấn
nhất.
Hình 5.1 Sơ đồ hệ thống tìm kiếm video theo nội dung trong luận văn
5.2.1 Mô-đun phân đoạn video
Việc phân đoạn video đã được để cập chi tiết trong chương 3. Để xây
dựng hệ thống này, mô-đun phân đoạn video sử dụng giải thuật “cửa sổ trượt
Video Files Phân đoạn
Video
Trích chọn
keyframe
Keyframes
Browser
Đánh chỉ mục
Tìm kiếm
bằng ảnh
Trích chọn
đặc trưng
CSDL
Keyframe
và đoạn
So sánh Trích chọn
đặc trưng
Kết quả:
Các đoạn
Video
Chương 5. Xây dựng hệ thống tìm kiếm video theo nội dung
82
kết hợp với ngưỡng” nhằm tăng độ chính xác trong phân đoạn. Giải thuật
không chỉ quan tâm đến sự khác nhau tương đối giữa các khung hình mà còn
xét đến sự khác nhau tuyệt đối giữa chúng. Trong đó sử dụng tính khoảng
cách giữa các khung hình dựa vào phương pháp so sánh biểu đồ màu trong
không gian màu đồng nhất CIELAB với số màu lượng tử hoá là 256 mức. Các
tham số để xây dựng mô-đun này được lựa chọn theo mục 3.4.3 trong chương
3.
5.2.2 Mô-đun trích chọn khung hình chính
Trong chương 4 đã đề cập chi tiết về việc trích chọn khung hình chính
trong video. Để xây dựng hệ thống tìm kiếm video theo nội dung ở đây sử
dụng giải thuật tìm các điểm có độ cong lớn trên đường sai khác tích luỹ để
trích chọn khung hình chính.
Khi xem xét đường sai khác tích luỹ ta có thể biết được sự thay đổi về
nội dung qua các khung hình trong toàn bộ đoạn video. Các chỗ dốc lớn chỉ ra
rằng có những sự thay đổi đáng kể trong video có thể do: một vật chuyển
động, sự di chuyển của camera. Khung hình chính được chọn là khung hình
nằm chính giữa hai điểm có độ cong lớn liên tiếp
Việc xây dựng đường sai khác tích luỹ giữa các khung hình đòi hỏi phải
tính toán được sự khác nhau giữa các khung hình liên tiếp. Trong thử nghiệm
này việc tính khoảng cách giữa các khung hình sử dụng phương pháp so sánh
biểu đồ màu trong không gian màu đồng nhất CIELAB với số màu lượng tử
hoá là 256 mức. Do việc tính sự sai khác giữa các khung hình có phương pháp
giống nhau nên có thể sử dụng trực tiếp kết quả tính sự sai khác giữa các
khung hình trong phần phân đoạn video mà không cần phải tính lại. Các tham
số để xây dựng mô-đun này được lựa chọn theo mục 4.4 trong chương 4.
Chương 5. Xây dựng hệ thống tìm kiếm video theo nội dung
83
5.2.3 Mô-đun tìm kiếm ảnh theo nội dung
Mô-đun tìm kiếm ảnh theo nội dung được sử dụng để tìm kiếm trong các
khung hình chính xem có khung hình nào gần giống với ảnh truy vấn nhất.
Cơ sở lý thuyết xây dựng mô-đun này đã được đề cập chi tiết trong
chương 2. Ở đây, việc tìm kiếm dựa vào phương pháp cải tiến là sự kết hợp
của hai thuật toán “Entropy-giá trị trung bình” và “So sánh biểu đồ màu”
được đề cập chi tiết trong chương 2 phần 2.6.4.
5.2.4 Mô-đun cơ sở dữ liệu
Việc thiết kế cơ sở dữ liệu nhằm lưu trữ, đánh chỉ mục video, thuận lợi
cho việc tìm kiếm video.
Trong cơ sở dữ liệu phải lưu được các đối tượng:
• Các file video
• Các đoạn cơ sở
• Các khung hình chính
• Các đặc trưng của các khung hình chính
Do đó cơ sở dữ liệu được thiết kế thành bốn bảng như sau:
Bảng VIDEO chứa các thông tin về các file video
Tên trường Kiểu Ý nghĩa
ID Số nguyên Khoá chính
Video_Name Chuỗi Tên của video
Filename Chuỗi Đường dẫn của file video
Length Số thực Chiều dài đoạn video
Frames_Per_Sec Số thực Số khung hình / giây
Description Memo Thông tin thêm
Chương 5. Xây dựng hệ thống tìm kiếm video theo nội dung
84
Bảng SHOT chứa các thông tin về các đoạn cơ sở
Tên trường Kiểu Ý nghĩa
ID Số nguyên Khoá chính
VideoID Số nguyên ID của video chứa đoạn (khoá ngoại)
Begin_Frame Số nguyên Khung hình bắt đầu của đoạn
End_Frame Số nguyên Khung hình kết thúc của đoạn
Bảng KEYFRAME chứa các thông tin về các khung hình chính
Tên trường Kiểu Ý nghĩa
ID Số nguyên Khoá chính
ShotID Số nguyên ID của đoạn cơ sở chứa khung hình chính (khoá
ngoại)
Frame_Position Số nguyên Vị trí của khung hình trong video
Filename Chuỗi Để thuận tiện hơn cho việc truy xuất khung
hình chính, các khung hình chính sau khi được
chọn sẽ được lưu vào máy dưới dạng ảnh.
Entropy_Value Số thực Giá trị Entropy của ảnh
Mean_Value Số thực Giá trị trung bình của biểu đồ màu
Bảng HISTOGRAM chứa các thông tin về các đặc trưng của khung hình
chính (Ở đây sử dụng đặc trưng biểu đồ màu trong không gian màu CIELAB)
Tên trường Kiểu Ý nghĩa
ID Số nguyên Khoá chính
KeyframeID Số nguyên ID của khung hình chính (khoá ngoại)
Bin Số nguyên Bin màu (chỉ số màu)
LAB_Value Số thực Giá trị của biểu đồ ứng với bin màu trên
Chương 5. Xây dựng hệ thống tìm kiếm video theo nội dung
85
Về mối quan hệ giữa các bảng trong ảnh, từ nhận xét: Có nhiều file
video, mỗi video có nhiều đoạn cơ sở (shot), mỗi đoạn cở sở có nhiều khung
hình chính (keyframe), mỗi khung hình chính có nhiều đặc trưng. Do đó ta có
mối quan hệ giữa các bảng như sau:
Hình 5.2 Mối quan hệ giữa các bảng trong cơ sở dữ liệu
5.3 Giao diện hệ thống
Các giao diện để phục vụ cho việc xây dựng cơ sở dữ liệu như giao diện
phân đoạn video, giao diện trích chọn khung hình chính đã được trình bày
trong chương 3 và chương 4. Phần này chỉ giới thiệu giao diện dành cho
người sử dụng truy vấn, tìm kiếm video mà NVLV xây dựng.
Chương 5. Xây dựng hệ thống tìm kiếm video theo nội dung
86
Hình 5.3 Giao diện cửa sổ tìm kiếm video
Kết luận chương
Từ các lý thuyết và thử nghiệm ở các chương trước, chương này NVLV
đã lựa chọn và tổng hợp thành một hệ thống tìm kiếm video khá hoàn chỉnh.
Việc xây dựng hệ thống dựa vào ý tưởng sử dụng phương pháp tìm kiếm
ảnh theo nội dung để tìm kiếm video. Tuy nhiên, không phải tìm kiếm trên
toàn bộ các khung hình mà chỉ tìm kiếm trong phạm vi các khung hình chính
(do các khung hình gần nhau thường có độ tương quan rất cao với nhau). Do
đó, hệ thống là sự kết hợp của các thành phần: tìm kiếm ảnh theo nội dung,
phân đoạn video, trích chọn khung hình chính.
Danh sách các video và
các đoạn trong CSDL
Liệt kê các khung
hình chính
Chi tiết về
các đoạn
(shot) video
Cửa sổ kết
quả phóng to Lựa chọn
ảnh truy vấn
Mở đoạn video
tìm được
Chương 5. Xây dựng hệ thống tìm kiếm video theo nội dung
87
Việc xây dựng phần mềm khá hoàn chỉnh đã cho phép người sử dụng có
thể xem nhanh (browsing) các khung hình chính trong video do đó hiểu nhanh
được nội dung của video. Hoặc người sử dụng có thể dùng ảnh để tìm kiếm
(searching) trong cơ sở dữ liệu lớn.
Kết luận
88
KẾT LUẬN
Kết luận
Việc tự động hoá trong đánh chỉ mục và tìm kiếm video theo nội dung là
một lĩnh vực rất khó và đồ sộ. Đến thời điểm này trên thế giới vẫn chưa có
một hệ thống nào có thể coi là công cụ vạn năng để đánh chỉ mục và tìm kiếm
video tự động ở mức cao (ngữ nghĩa), các hướng tiếp cận hiện nay chỉ dừng
lại trong một lĩnh vực hẹp hoặc là tìm kiếm mức thấp. Trong luận văn này
người viết đã phân tích và đánh giá một số phương pháp hiện nay trên thế giới
và đã đưa một hướng tiếp cận phù hợp. Đó là sử phương pháp tìm kiếm ảnh
theo nội dung để tìm kiếm các khung hình chính và đạt được những kết quả
nhất định. Các vấn đề mà luận văn đã làm được:
1. Nghiên cứu các hệ thống tìm kiếm video theo nội dung trên thế giới.
2. Đưa ra mô hình tìm kiếm video dựa trên cơ chế tìm kiếm ảnh.
3. Nghiên cứu, phát triển một số phương pháp tìm kiếm ảnh theo nội
dung ứng dụng trong tìm kiếm video.
4. Nghiên cứu và đưa ra giải thuật cải tiến trong phân đoạn video với độ
chính xác cao.
5. Nghiên cứu kỹ thuật trích chọn khung hình chính trong video.
6. Cài đặt hệ thống và chứng minh tính đúng đắn của các giải thuật.
Đóng góp khoa học của luận văn
1. Đưa ra được một mô hình tìm kiếm video dựa trên cơ chế tìm kiếm
ảnh. Video được phân đoạn thành các đoạn cơ sở, mỗi đoạn cơ sở
được đại diện bằng một số khung hình chính. Người sử dụng có thể
tìm kiếm video thông qua việc tìm kiếm trên các khung hình chính
dựa vào cơ chế tìm kiếm ảnh.
Kết luận
89
2. Đưa ra giải thuật tìm kiếm ảnh kết hợp tìm kiếm ảnh sử dụng đặc
trưng Entropy-giá trị trung bình và giải thuật so sánh biểu đồ màu
tăng nhanh tốc độ tìm kiếm. Entropy là một đặc trưng của ảnh có số
chiều bằng 1, do đó tìm kiếm ảnh dựa trên Entropy có tốc độ tìm
kiếm rất cao. Tuy nhiên, đôi khi phương pháp này lại không chính
xác. NVLV đưa ra giải pháp kết hợp đặc trưng Entropy và giá trị
trung bình nhằm tăng độ chính xác mà vẫn không giảm tốc độ tìm
kiếm. Phương pháp Entropy-giá trị trung bình được thực hiện trước
để thu hẹp không gian tìm kiếm sau đó sẽ dùng phương pháp so sánh
biểu đồ màu để đưa ra kết quả tìm kiếm cuối cùng đến người sử dụng.
3. Đưa ra giải thuật phân đoạn video kết hợp giữa phương pháp cửa sổ
trượt và ngưỡng so sánh để tăng độ chính xác của phân đoạn. Phương
pháp cửa sổ trượt xác định chuyển cảnh đột ngột dựa trên sự khác
nhau tương đối giữa các khung hình trong cửa sổ truy vấn. Tuy nhiên,
có những trường hợp phương pháp này đưa ra kết quả sai ví dụ trong
các trường hợp video có đối tượng nhỏ chuyển động nhanh. NVLV
đề xuất thuật toán cải tiến: ngoài việc so sánh tương đối giữa các
khung hình còn cần xét đến sự sai khác tuyệt đối giữa nhằm tăng độ
chính xác trong phân đoạn.
Hướng phát triển của đề tài
Như đã trình bày, hệ thống tìm kiếm video được xây dựng trong Luận
văn là sự kết hợp của các thành phần: tìm kiếm ảnh, phân đoạn video, trích
chọn khung hình chính. Do đó để nâng cao chất lượng của hệ thống cần cải
thiện từng thành phần:
1. Tìm kiếm ảnh: Nghiên cứu sử dụng các đặc trưng khác của ảnh như:
kết cấu, hình dạng,... Tiếp cận theo hướng tìm kiếm theo các thông tin
ngữ nghĩa có trong ảnh.
Kết luận
90
2. Phân đoạn video:
• Tăng cường độ chính xác trong phân đoạn.
• Phân đoạn được nhiều loại chuyển cảnh khác nhau.
• Tăng cường tốc độ phân đoạn: cải tiến giải thuật, sử dụng trực tiếp
video nén.
3. Trích chọn khung hình chính: Cải tiến giải thuật theo hướng trích
chọn những khung hình tiêu biểu nhất, đặc biệt tiêu biểu về mặt ngữ
nghĩa.
Tóm lại hướng nghiên cứu tương lai là tập trung vào hướng đưa các
thông tin về mặt ngữ nghĩa (đối tượng, sự kiện) vào trong việc đánh chỉ mục
và tìm kiếm video.
Tài liệu tham khảo
91
TÀI LIỆU THAM KHẢO
[1] Milan Petkovic. (2000), Content-based Video Retrieval, (EDBT) PhD
Workshop
[2] Hauptmann, A., Jin, R., N. Papernick, D. Ng, Y. Qi, Houghton,
RThornton, S. (2001), Video Retrieval with the Informedia Digital
Video Library System, Proceedings of the Tenth Text Retrieval
Conference (TREC-2001).
[3] Abraham Ittycheriah, Martin Franz, Wei-Jing Zhu, and Adwait
Ratnaparkhi. (2000), IBM's statistical question answering system. In
9th Text REtrieval Conference, Gaithersburg.
[4] Mayfield, J., McNamee, P., Costello, C., Piatko, C., and Banerjee. A.
(2001), JHU/APL at TREC 2001: Experiments in Filtering and in
Arabic, Video and Web retrieval. In TREC 2001 Proceedings.
[5] Kareem Darwish and David S. Doermann and Ryan C. Jones and
Douglas W. Oard and Mika Rautiainen. (2001), {TREC}-10
Experiments at University of Maryland {CLIR} and Video.
[6] Mark E. Rorvig, Ki-Tau Jeong, Anup Pachlag, Ramprasad Anusuri,
Diane Jenkins, Sara Oyarce. (2001), UNT TRECvid: A Brighton
Image Searcher Application.
[7] D. Tegolo. (1994), Shape analysis for image retrieval, Proc. of SPIE,
Storage and Retrieval for Image and Video Databases -II, no. 2185,
San Jose, CA, pp. 59-69.
[8] T. Chang, and C.C.J. Kuo. (1993), Texture analysis and classification
with tree-structured wavelet transform, IEEE Trans. on Image
Processing, vol. 2, no. 4, pp. 429-441.
Tài liệu tham khảo
92
[9] I.Koprinska and S.Carrato. (2001), Temporal Video Segmentation: A
Survey, Signal Processing Image Communication, Elsevier Science
[10] T. Kikukawa, S. Kawafuchi. (1992), Development of an automatic
summary editing system for the audio-visual resources, Transactions
on Electronics and Information J75-A, 204-212, 1992.
[11] A. Nagasaka, Y. Tanaka. (1995), Automatic video indexing and
full-video search for object appearances, in Visual Database
Systems II (E. Knuth and L.M. Wegner, eds.), pp. 113-127,
Elsevier.
[12] R. Kasturi, R. Jain. (1991), Dynamic vision, in Computer Vision:
Principles, R. Kasturi and R. Jain, eds.), pp. 469-480, IEEE
Computer Society Press, Washington DC.
[13] M. J. Swain. (1993), Interactive indexing into image databases,
in: Proc. SPIE Conf. Storage and Retrieval in Image and Video
Databases, pp.173-187.
[14] Gianluigi Ciocca, Raimondo Schettini. (2004), Dynamic Key-frame
Extraction for Video Summarization, Proceedings of the SPIE,
Volume 5670, pp. 137-142
[15] S.M.M Tahaghoghi et al. (2005), Video Cut Detection using Frame
Windows, Proceedings of the Twenty-eighth Australasian conference
on Computer Science, pp. 193 – 199.
[16] Janko Calic. (2004), Highly Efficient Low-level Feature Extraction
for Video Representation And Retrieval, PhD thesis, University of
London
[17] John M. Zachary. (2000), An Information Theoretic Approach to
Content Based Image Retrieval, PhD thesis, Louisiana State
University
Tài liệu tham khảo
93
[18] Shengjiu Wang. (2001), A Robust CBIR Approach Using Local Color
Histograms, Technical Report TR 01-13, Department Of Computing
Science, University of Alberta, Edmonton, Alberta, Canada
[19] Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates, José Luis
Marroquín. (2001), Searching in Metric Spaces, ACM Computing
Surveys, Vol. 33, No. 3, pp. 273–321.
[20] F. Long, H. Zhang & D. Feng (2003), Chapter 1 - Fundamental of
Content-Based Image Retrieval, pp.1-26, in “Multimedia Information
Retrieval and Management – Technological Fundamentals and
Applications”, Edited by David Dagan Feng, W. C. Siu & Hongjing
Zhang, Springer-Verlag, Germany.
[21] T. Deselaers, D. Keysers, and H. Ney. (2004), Classification error rate
for quantitative evaluation of content-based image retrieval systems.
In Int. Conf. on Pattern Recognition, Cambridge, UK.
[22] Tonomura Y., Akutsu A., Otsugi K., and Sadakata T. (1993),
VideoMAP and VideoSpaceIcon: Tools for automatizing video
content. Proc. ACM INTERCHI ’93 Conference, 131-141.
[23] Rui Y., Huang T. S. and Mehrotra S. (1998), Exploring Video
Structure Beyond the Shots. Proc. IEEE Int. Conf. on Multimedia
Computing and Systems (ICMCS), Texas USA, 237-240
[24] Pentland A., Picard R., Davenport G. and Haase K. (1994), Video and
Image Semantics: Advanced Tools for Telecommunications. IEEE
MultiMedia; 1(2):73-75
[25] Zhonghua Sun, Fu Ping. (2004), Combination of Color and Object
Outline Based Method in Video Segmentation. Proc. SPIE Storage
and Retrieval Methods and Applications for Multimedia; 5307:61-69.
Tài liệu tham khảo
94
[26] Li Zhao, Wei Qi, Stan Z. Li, S.Q.Yang, H.J. Zhang. (2000), Key-
frame Extraction and Shot Retrieval Using Nearest Feature Line
(NFL). Proc. ACM Int. Workshops on Multimedia Information
Retrieval; 217-220.
[27] Hanjalic A., Lagendijk R. L., Biemond J. (1998), A new Method for
Key Frame Based Video Content Representation. In: Image Databases
and Multimedia Search, World Scientific Singapore.
[28] Hoon S. H., Yoon K., and Kweon I. (2000), A new Technique for
Shot Detection and Key Frames Selection in Histogram Space. Proc.
12th Workshop on Image Processing and Image Understanding; 475-
479.
[29] Narasimha R., Savakis A., Rao R. M. and De Queiroz R. (2004), A
Neural Network Approach to Key Frame extraction. Proc. of SPIE-
IS&T Electronic Imaging Storage and Retrieval Methods and
Applications for Multimedia; 5307:439-447.
[30] Chetverikov D. and Szabo Zs. (1999), A Simple and Efficient
Algorithm for Detection of High Curvature Points in Planar Curves,
Proc. 23rd Workshop of the Austrian Pattern Recognition Group,
;175-184.
[31] A. Nagasaka, Y. Tanaka. (1992), Automatic Video Indexing and Full-
Video Search for Object Appearances, Visual Database Systems, vol.
II, pp. 113-127
[32] K. Otsuji, Y. Tonomura, and Y. Ohba. (1991), Video browsing using
brightness data, in Proc. SPIE-IST VCIP91, vol. 1606, pp. 980-989
[33] A.Akutsu, Y.Tonomura, H.Hashimoto and Y.Ohba. (1992), Video
indexing using motion vectors, Proc. SPIE: Visual Communication
and Image Processing '92 1818, pp1522-1530
Tài liệu tham khảo
95
[34] không gian màu
CIELAB
[35] , cơ sở dữ liệu hình ảnh
[36] TREC Video Retrieval Evaluation, website:
nlpir.nist.gov/projects/trecvid/
Phụ lục
96
PHỤ LỤC
Chuyển đổi từ không gian màu RGB sang CIELAB
Việc chuyển đổi từ RGB sang CIELAB phải qua không gian màu trung
gian XYZ. Sự chuyển đổi từ RGB sang XYZ được thực hiện bằng một ánh xạ
tuyến tính như sau:
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
B
G
R
Z
Y
X
0.950227 0.11919 0.019334
0.072169 0.71516 0.212671
0.180423 0.35758 0.412453
Từ XYZ chuyển đổi sang CIELAB
16116*
3
1
−⎟⎟⎠
⎞
⎜⎜⎝
⎛=
nY
YL với 0.008856>
nY
Y
⎟⎟⎠
⎞
⎜⎜⎝
⎛=
nY
YL 3.903* với
nY
Y còn lại
⎟⎟⎠
⎞
⎜⎜⎝
⎛
⎟⎟⎠
⎞
⎜⎜⎝
⎛−⎟⎟⎠
⎞
⎜⎜⎝
⎛=
nn Y
Yf
X
Xfa 500*
⎟⎟⎠
⎞
⎜⎜⎝
⎛
⎟⎟⎠
⎞
⎜⎜⎝
⎛−⎟⎟⎠
⎞
⎜⎜⎝
⎛=
nn Z
Zf
Y
Yfb 200*
Trong đó 3
1
)( ttf = với 008856.0>t
116
16787.7)( += ttf với t còn lại
(Xn, Yn, Zn) là giá trị của (X, Y, Z) tại điểm trắng tham chiếu (reference
white point). Trong luận văn sử dụng điểm trắng tham chiếu tại (R, G, B) =
(255, 255, 255). Tính được (Xn, Yn, Zn) = (242.366, 255.000, 277.632)
Tóm tắt luận văn
97
TÓM TẮT LUẬN VĂN
Tiếng Việt:
Sự phát triển của Công nghệ thông tin và Truyền thông đã làm gia tăng
nhanh chóng việc lưu trữ, sử dụng, truyền tải một lượng lớn video số. Do đó
việc sắp xếp, quản lý, tìm kiếm video càng ngày càng trở nên phức tạp và
nặng nhọc. Luận văn này với tên gọi “Nghiên cứu, xây dựng hệ thống tìm
kiếm video theo nội dung” (Content-Based Video Retrieval) sẽ tập trung vào
việc tự động hoá đánh chỉ mục và tìm kiếm video. Luận văn gồm ba phần
chính. Phần một: Tìm kiếm ảnh theo nội dung. Phần này nghiên cứu các vấn
đề đánh chỉ mục và tìm kiếm ảnh, đây là một phần quan trọng của hệ thống
tìm kiếm video mà NVLV xây dựng. Phần hai: Phân đoạn video. Phần này tập
trung vào việc phân đoạn video theo thời gian thành các đoạn cơ sở, tập trung
vào nghiên cứu các giải thuật nhằm tăng cường độ chính xác trong phân đoạn.
Phần ba: Trích chọn khung hình chính. Nghiên cứu các giải thuật trích chọn
các khung hình đại diện cho đoạn video với mục đích làm giảm khối lượng
lưu trữ. Hệ thống tìm kiếm video mà NVLV xây dựng là sự kết hợp của ba
thành phần trên, video sau khi được phân đoạn thành các đoạn cơ sở sẽ được
trích chọn ra các khung hình đại diện cho các đoạn cơ sở. Người sử dụng có
thể xem được tóm tắt đoạn video qua các khung hình đại diện hoặc có thể tìm
kiếm đoạn video thông qua phương pháp tìm kiếm ảnh trên các khung hình
đại diện đó.
Từ khoá: Tìm kiếm video theo nội dung, tóm tắt video, phân đoạn video, trích
chọn khung hình chính, tìm kiếm ảnh theo nội dung.
Tóm tắt luận văn
98
English:
Information and communication technology are developing very quickly
hence storing, using and transfering digital video are increasing quickly too.
Therefore video arrangement, management, search become complicated and
exhausting. This thesis with name “Content-Based Video Retrieval” will
concentrate to automate video indexing and searching. The thesis contains
three main parts. Part one: “Content-base image retrieval”. This part research
problems in indexing and searching images, it is a important part in thesis
writer’s video retrieval system. Part two: “Video segmentation”. This part
researchs how to segment video into shots. Proposes some algorithms with
high accurate. Part three: “Key-frame extraction”. This part researchs key-
frame extraction algorithms in the world and proposes appropriate approachs.
Thesis writer’s video retrieval system is combined from these three parts.
Video is segmented in to shots, and each shot is presented by some key-
frames. Users can browse video by using key-frames or using image retrieval
mechanism to search video.
Keywords: Content-Based Video Retrieval, video summarization, shot
segmentation, key frames extraction, Content-Based Image Retrieval
._.
Các file đính kèm theo tài liệu này:
- LA3256.pdf