Số hóa bởi Trung tâm Học liệu

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG NGUYỄN ĐÌNH TRUNG NGHIÊN CỨU MỘT SỐ KỸ THUẬT
PHÂN ĐOẠN VIDEO LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên, 2014

Số hóa bởi Trung tâm Học liệu

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG NGUYỄN ĐÌNH TRUNG


Số hóa bởi Trung tâm Học liệu

LỜI CẢM ƠN
Tôi xin gửi lời cảm ơn chân thành nhất tới TS. Nguyễn Thị Hồng Minh, Cô đã
cho tôi những định hƣớng, tận tình chỉ bảo giúp đỡ tôi những ý kiến rất quý báu
để tôi hoàn thành luận văn tốt nghiệp này.
Tôi xin cảm ơn Trƣờng Đại Học Công Nghệ Thông tin và Truyền thông - Đại
Học Thái Nguyên đã hết sức tạo điều kiện cho tôi trong quá trình học, làm và
hoàn thành khóa luận này.
Xin chân thành cảm ơn quý Thầy Cô trong khoa Sau đại học Trƣờng Đại học
Công nghệ Thông tin và Truyền thông – ĐH Thái Nguyên đã nhiệt tình giảng
dạy, trang bị cho tôi những kiến thức quý báu trong suốt thời gian học tập tại
trƣờng.
Tôi xin tỏ lòng biết ơn sâu sắc tới các thầy cô, bạn bè đã dìu dắt, giúp đỡ tôi tiến
bộ trong suốt quá trình làm khóa luận tốt nghiệp.
Xin gửi lời cảm ơn tới gia đình, những ngƣời bạn của tôi đã động viên, giúp đỡ
tôi trong suốt quá trình học tập và hoàn thành luận văn.


1.1.3.4. Chuẩn ITU-T 23
1.1.4. Một số đặc trƣng của video 33
1.1.4.1. Màu sắc 33
1.1.4.2. Kết cấu 33
1.1.4.3. Hình dáng 35
1.1.4.4. Chuyển động 35
1.2. Bài toán phân đoạn Video 36
1.2.1. Bài toán 36
1.2.2. Phân loại các phƣơng pháp phân đoạn 36
1.2.3. Các yếu tố chính để xác định phƣơng pháp phân đoạn 37
Chƣơng 2 MỘT SỐ KỸ THUẬT PHÂN ĐOẠN VIDEO 38
2.1. Phân đoạn video bằng kỹ thuật phát hiện đối tƣợng từ trên xuống 38
2.2. Phân đoạn và theo vết các vùng Video 39
2.3. Phân đoạn Video bằng kỹ thuật trừ ảnh và phát hiện chuyển cảnh trong Video 41
2.3.1. Các kỹ thuật trừ ảnh 43
2.3.1.1. Trừ ảnh dựa vào điểm ảnh 43
2.3.1.2. Trừ ảnh phân khối 45
2.3.2. Phƣơng pháp biểu đồ màu. 45
2.3.2.1. Biểu đồ toàn cục 48
2.3.2.2. Biểu đồ cục bộ 48
2.3.3. Trừ ảnh dựa vào đặc trƣng 53
2.3.3.1. Đặc trƣng là cạnh 55
2.3.3.2. Đặc trƣng là vectơ chuyển động 55
2.3.4. Phƣơng pháp thống kê 61
2.3.5. Phát hiện chuyển cảnh 64
2.3.5.1. Đối với kỹ thuật phát hiện cắt cảnh 65
2.3.5.2. Đối với các kỹ thuật phát hiện chuyển cảnh dần dần 65
Chƣơng 3 CHƢƠNG TRÌNH THỬ NGHIỆM 67
3.1. Bài toán 68
3.2. Phân tích, lựa chọn công cụ 68

Discrete Cosine Transform
DV
Digital Video
DVD
Digital Video Disc
HDTV
High Definition TV
IEC
International Electrotechnical Commission
IMA
Interactive Multimedia Association
ISO
International Organization for Standardization
ISO-IEC
International Organization for Standard –
International Electrotechnical Commission
ITU-T
International Telecommunication Union
JPEG
Joint Picture Experts Group
MACE
Macintosh Audio Compression and Expansion
codec

Số hóa bởi Trung tâm Học liệu

MOV
Quick Time Movie File Extension
MPEG
Moving Picture Experts Group

WMV
Windows Media file with Audio/Video
YUV
Sơ đồ mã hoá hình ảnh màu phân cách độ chói
(Y) và hai tín hiệu màu: đỏ trừ Y (U) và xanh
trừ Y (V). Số hóa bởi Trung tâm Học liệu

DANH MỤC CÁC HÌNH VẼ
Hình 1.1: Cấu trúc phân cấp của video Error! Bookmark not defined.
Hình 1.2: Cắt cứng Error! Bookmark not defined.
Hình 1.3: Fade in Error! Bookmark not defined.
Hình 1.4: Fade out Error! Bookmark not defined.
Hình 1.5: Chồng mờ Error! Bookmark not defined.
Hình 1.6: Wipe Error! Bookmark not defined.
Hình 1.7: push sang trái Error! Bookmark not defined.
Hình 1.8: Một số loại wipe cơ bản Error! Bookmark not defined.
Hình 1.9: Sơ đồ giải nén MPEG–1 (ISO/IEC 11172)Error! Bookmark not defined.
Hình 1.10: Sơ đồ nén dữ liệu âm thanh Error! Bookmark not defined.
Hình 1.11: Mô hình hệ thống giải mã MPEG 2 Error! Bookmark not defined.
Hình 1.12: Mô hình nén và giải nén theo từng lớp của MPEG 4 Error! Bookmark
not defined.
Hình 1.13: Các ảnh rất khác nhau nhƣng có cùng biểu đồ màu Error! Bookmark not
defined.
Hình 1.14: Biểu đồ thể hiện 4 loại ảnh cơ bản Error! Bookmark not defined.
Hình 1.15: Các thao tác camera 35
Hình 2.1. Khám phá và khai thác cấu trúc các đối tƣợng ảnh………………………… 36
Hình 2.2. Sơ đồ ứng dụng kỹ thuật trừ ảnh vào phân đoạn video . Error! Bookmark not


Hình 2.20. Kết quả phát hiện cắt cảnh bằng các kỹ thuật cải tiến từ hƣớng tiếp cận so
sánh biểu đồ (HistDiff) Error! Bookmark not defined.
Hình 3.1. Giao diện phát hiện chuyển cảnh 69
Hình 3.2. Nội dung file lƣu kết quả phân đoạn 69
DANH MỤC CÁC BẢNG
Bảng 1.1. Các tiêu chuẩn của Video số 16
Bảng 1.2. Một số ràng buộc của MPEG-1 Error! Bookmark not defined.
Bảng 1.3. Mô tả kiểu CIF và QCIF 32
Bảng 2.1. So sánh các kỹ thuật trừ ảnh với việc phát hiện biên tập video 65

Số hóa bởi Trung tâm Học liệu

PHẦN MỞ ĐẦU
I. Lý do chọn đề tài
Hiện nay, phần lớn lƣợng thông tin mà con ngƣời tiếp thu đƣợc từ thế giới
bên ngoài là ở dạng thông tin thị giác, vì vậy các nghiên cứu về dạng thông
tin này đều ít nhiều mang đến những lợi ích thiết thực cho cuộc sống. Với
trình độ khoa học kỹ thuật hiện nay, thông tin thị giác đuợc số hóa dƣới hai
dạng là ảnh số và video số.
Video ra đời vào những năm đầu của thế kỷ XX và phát triển khá mạnh mẽ,
nhƣng phải đến những thập kỷ cuối của thế kỷ XX video số mới phát triển.
Với sự ra đời và phát triển mạnh của máy tính và các hệ thống viễn thông,
việc xử lý dữ liệu video đƣợc số hoá trên máy tính tỏ ra khá hiệu quả. Dữ
liệu video số đã đƣợc đƣa vào rất nhiều ứng dụng trong thực tế nhƣ đào tạo
điện tử dựa vào máy tính, hỗ trợ đào tạo trên mạng, hệ thống mô phỏng,
giám sát, video theo yêu cầu… Vấn đề nâng cao hiệu quả và chất lƣợng của
thao tác, xử lý với dữ liệu video đang đƣợc nhiều nhà nghiên cứu, triển
khai ứng dụng quan tâm
Thông tin video khác với dữ liệu dạng văn bản cũng nhƣ dữ liệu ảnh

các cảnh (scene) hay một dãy cảnh quay.
Một kịch bản điển hình trong tạo chỉ mục và tìm kiếm nội dung video đƣợc
biểu diễn trong hình 1 dƣới đây. Trƣớc tiên, các video và ảnh đầu vào đƣợc
phân đoạn thành các đơn vị theo không gian và thời gian thích hợp. Các
đặc trƣng trực quan sau đó đƣợc rút ra từ các đơn vị này để tạo chỉ mục và
tóm lƣợc, cuối cùng những video và ảnh này đƣợc đƣa ra và tìm kiếm dựa
trên các cấu trúc và đặc trƣng ở trên.

Số hóa bởi Trung tâm Học liệu Hình 1. Quá trình phân đoạn và tìm kiếm ảnh video
Chính vì vậy, việc nghiên cứu về phân đoạn Video là rất cần thiết cho một hệ
thống dữ liệu video và nó ngày càng trở nên cấp thiết hơn khi nhu cầu sử dụng
video ngày càng gia tăng. Xuất phát từ hoàn cảnh đó chúng tôi lựa chọn đề tài
"Nghiên cứu một số kỹ thuật phân đoạn video".
II. Mục tiêu nghiên cứu
Mục tiêu của đề tài là tập trung nghiên cứu một số kỹ thuật phân đoạn
video, đề xuất một số cải tiến và xây dựng một ứng dụng thực tế sử dụng
kỹ thuật cải tiến đã đƣợc nghiên cứu.
III. Nội dung nghiên cứu
Tổng quan về dữ liệu video.
Nghiên cứu các kỹ thuật phân đoạn video và đề xuất cải tiến
Triển khai ứng dụng thử nghiệm phân đoạn video nhằm tìm ra các phân
đoạn có ngữ cảnh phù hợp theo mục đích tìm kiếm
IV. Phƣơng pháp nghiên cứu
Tổng hợp các thông tin liên quan, lựa chọn các cách tiếp cận đã đƣợc
áp dụng thành công, tiến hành cài đặt thử nghiệm cho với các kỹ thuật đƣợc đề

Số hóa bởi Trung tâm Học liệu

này. Sau đó, hàng loạt các nghiên cứu khác đƣợc triển khai và đã có những ứng
dụng đáng kể. Năm 1887, khi Hannubal Good phát minh ra phim ảnh thì vấn đề
ảnh chuyển động đƣợc quan tâm đặc biệt vì những lợi ích kinh tế mà nó mang
lại. Năm 1895, một hệ thống camera/Projector với các chuẩn phim (35mm chiều
rộng, 24 khung hình trên giây) đƣợc phát triển bởi Louis Lumiére.
1.1.1.1. Một số khái niệm cơ bản
Trƣớc hết chúng ta cùng tìm hiểu để có cái nhìn cơ bản về video. Video là
tập hợp các khung hình, mỗi khung hình là một ảnh. Shot (lia) là đơn vị cơ
sở của video. Một lia là một đơn vị vật lý của dòng video, gồm các chuỗi
các khung hình liên tiếp, không thể chia nhỏ hơn, ứng với một thao tác
camera đơn.

Số hóa bởi Trung tâm Học liệu

Scene (cảnh) là các đơn vị logic của dòng video, một cảnh gồm các lia liên
quan về không gian và liền kề về thời gian, cùng mô tả một nội dung ngữ
nghĩa hoặc một tình tiết [8].
Cấu trúc phân cấp của video đƣợc thể hiện trên hình 1.1.
Khi phim đƣợc chiếu, các khung hình lần lƣợt đƣợc hiển thị ở tốc độ nhất
định. Tốc độ thƣờng thấy ở các định dạng video khác nhau là 30 và 25
hình/s. Nhƣ vậy một giờ video sẽ có số khung hình tƣơng ứng là 108000
hoặc là 90000. Dù là video ở định dạng nào thì nó cũng có dung lƣợng rất
lớn và nếu xử lý với tất cả các khung hình thì thật không hiệu quả.
Phân đoạn là quá trình phân tích và chia nội dung hình ảnh video thành các
đơn vị cơ sở gọi là các lia (shot). Việc lấy mẫu chính là chọn gần đúng một
khung video đại diện cho mỗi lia (hoặc nhiều hơn tùy theo mức độ phức tạp
của nội dung hình ảnh của lia) và đƣợc gọi là các khung-khóa [8].
Khung – khóa là khung hình đại diện mô tả nội dung chính của shot.

Hình 1.1: Cấu trúc phân cấp của video

Hình 1.6: Wipe
push: là hiện tƣợng cảnh tiếp theo xuất hiện đẩy cảnh hiện tại ra khỏi
màn hình theo hƣớng sang trái, phải, lên trên, xuống dƣới.

Hình 1.7: push sang trái

corner to corner

side to side

centre – out

boundery - in
Hình 1.8: Một số loại wipe cơ bản
1.1.2. Các ứng dụng Video
1.1.2.1. Video tƣơng tự
NTSC Video: Đây là dạng Video tƣơng tự với 525 dòng trên một khung hình, 30
khung hình trong một giây, quét cách dòng, chia làm hai trƣờng (mỗi trƣờng
262.5 dòng), có 20 dòng dự trữ cho thông tin điều khiển tại thời điểm bắt đầu
mỗi trƣờng.
PAL Video: Dạng Video này có 625 dòng trên một khung hình, 25 khung hình
trong một giây, quét cách dòng. Khung gồm hai trƣờng chẵn lẻ, mỗi trƣờng bao
gồm 312.5 dòng.

Số hóa bởi Trung tâm Học liệu

1.1.2.2. Video số
Một số tiêu chuẩn của Video số lấy theo tiêu chuẩn CCI.

CCIR

Cách dòng
Cách dòng
Liên tục
Liên tục
Bảng 1.1. Các tiêu chuẩn của Video số
1.1.3. Các chuẩn video
Sự chuẩn hóa của video tƣơng tự trong những năm đầu của thập niên 1950
(NTSC) và những năm cuối của 1960 (SECAM và PAL) làm cho ảnh chuyển
động xuất hiện hầu nhƣ khắp nơi, với các thiết bị vô tuyến đƣợc dùng rộng rãi
cho mục đích giải trí, các hệ thống ứng dụng công nghệ nhƣ phát hiện chuyển
động tiếp tục đƣợc phát triển.
Vào năm 1990, các tổ chức về chuẩn hóa nhƣ tổ chức ISO-IEC (International
Organization for Standard – International Electrotechnical Commission) đã đƣa
ra chuẩn MJPEG cho video kĩ thuật số, tổ chức chuẩn ITU-T đã đƣa ra chuẩn
H.261 và một số các chuẩn liên quan khác. Đi kèm với nó là các thiết bị tin học
giá rẻ đã tạo nên sự phát triển bùng nổ cho các ứng dụng đa phƣơng tiện.
Trong quá trình soạn thảo, xử lý và kết xuất video cần hiểu rõ về các định chuẩn
video. Ví dụ: để tạo ra một video sử dụng trên Intermet chúng ta cần phải thiết
lập các tham số nén đảm bảo tệp video theo đúng định dạng và mục đích sử
dụng. Ngoài các yếu tố kỹ thuật, việc xác định định dạng của video còn phụ
thuộc vào các yếu tố kinh nghiệm của ngƣời xử lý. MPEG, AVI cho Windows,
MOV cho QuickTime là các định dạng đƣợc sử dụng rộng rãi. Trong phần này

Số hóa bởi Trung tâm Học liệu

chúng ta làm rõ các định chuẩn với mục đích sử dụng, các kỹ thuật nén, kích cỡ,
thời gian xử lý nén và giải nén.
1.1.3.1. Định dạng AVI
Đây là định dạng phổ biến đƣợc thiết kế để dùng trong môi trƣờng
Windows Error! Reference source not found Định dạng này rất linh

dụng kiểu nén này tỏ ra khá hữu hiệu. Kiểu nén này có mã nén độ dài 8
bit dùng thuật toán nén RLE và chất lƣợng video cao.
+ Microsoft Video 1: sử dụng kỹ thuật nén mất thông tin theo phƣơng pháp nén
không gian màu. Mã nén này có nhiều tham số có thể thay đổi nhƣ: số
mầu trên khuôn hình của video (8 bit hay 24 bit mầu), chất lƣợng video,
số khung hình chính Chuẩn nén này có thể tạo ra các tệp video sử
dụng cho các chƣơng trình đào tạo từ xa hay các tệp video sử dụng cho
mạng tốc độ thấp.
+ Indeo (R) Video R3:2: sử dụng để nén video 24 bit dùng cho đĩa CD. Tỷ lệ
nén tốt, chất lƣợng hình ảnh cao và tốc độ hiển thị nhanh hơn so với
kiểu nén Microsoft Video 1. Cho kết quả tốt nhất nếu sử dụng mã nén
Indeo Video trên dữ liệu video nguồn mà trƣớc đó dữ liệu này không bị
nén với tỷ lệ cao bằng các kỹ thuật nén mất thông tin. Các tệp video
đƣợc nén bằng kỹ thuật nén Indeo (R) video R3:2 có chất lƣợng tƣơng
đƣơng với các tệp video sử dụng kỹ thuật nén Cinepak.
+ Cinepak Code By Radius: sử dụng để nén video 24 bit dùng cho CD-ROM
hoặc cho mục đích tải về từ Web. Đây là kiểu nén đạt đƣợc tỷ lệ nén
cao hơn và tốc độ giải nén nhanh hơn so với mã nén Microsoft Video 1.
Chúng ta có thể đặt tham số chất lƣợng hình ảnh. Các tệp video sau khi
xử lý có thể hiển thị lại trên đƣờng truyền có tốc độ 30 Kb/giây. Kỹ
thuật mã bằng Cinepak tạo ra sản phẩm video có tốc độ giải nén rất
nhanh nhƣng khi nén mất rất nhiều thời gian. Kỹ thuật nén này phù hợp
cho việc chuyển một đoạn video thành kết quả cuối cho ngƣời sử dụng.

Số hóa bởi Trung tâm Học liệu

Mã nén âm thanh cho Windows

giải nén nhanh. Cinepak dùng thuật toán nén không đối xứng các tệp
video có kích cỡ nhỏ nhƣng thời gian nén rất lâu. Cho kết quả tốt nhất
nếu dùng Cinepak để tạo tệp video.
+ Sorenson Video: đƣợc sử dụng để nén video 24 bit. Các tệp sử dụng mã nén
này để dùng cho CD-ROM và Web video. Nó cũng giống nhƣ mã nén
Cinepak nhƣng là mã nén mới thiết kế để nén với chất lƣợng cao. Mã
nén này cho hình ảnh tốt hơn, kích cỡ tệp video nhỏ hơn so với mã
Cinepak vì vậy nó phù hợp cho việc tạo các tệp video cuối cùng chứ
không phù hợp cho soạn thảo.
+ Planar RGB: sử dụng hiệu quả cho các khuôn hình có vùng màu đặc nhƣ các
tệp hình động (hoạt hoạ). Nó sử dụng thuật toán nén RLE kết hợp với
kỹ thuật tạo mã hình động.
+ Motion JPEGA and Motion JPEG: đƣợc dùng cho mục đích chuyển mã
video giữa các thiết bị. Ví dụ: chuyển các tệp video trong hệ thống máy
tính, các đoạn video trên băng ra các thiết bị khác của mày tính nhƣ đĩa
CD thông qua thiết bị thu video. Mã nén Motion JPEGA and Motion
JPEG đƣợc hỗ trợ nhiều trong các chíp có trên các thiết bị thu video do
đó tốc độ xử lý rất nhanh.
+ Photo - JPEG: dùng để nén một chuỗi các ảnh tĩnh có màu sắc biến đổi dần
(các đƣờng biên không rõ nét). Đây là kiểu nén mất thông tin nhƣng có
thể đặt đƣợc tham số nén để ảnh có chất lƣợng rất cao. Mã nén Photo-
JPEG là kiểu nén đối xứng - thời gian nén gần bằng thời gian giải nén,
nhƣng thời gian nén là khá nhiều so với thời gian thực của video. Các
ảnh đã đƣợc nén theo kiểu này thì không nên dùng làm nguồn để soạn
thảo vì nó đã bị mất thông tin. Tuy nhiên với tỷ lệ nén không cao nhƣng
cho chất lƣợng ảnh tốt nên có thể dùng để lƣu trữ hoặc để di chuyển
giữa các hệ thống máy tính. Rất nhiều phần mềm cho phép nén dữ liệu
video đã đƣợc cứng hoá sử dụng định dạng JPEG.

Số hóa bởi Trung tâm Học liệu

Số hóa bởi Trung tâm Học liệu

Đối với các thiết bị phần cứng hỗ trợ soạn thảo Video thƣờng có các mã
nén riêng đƣợc viết bởi nhà sản xuất thiết bị phần cứng.
Mã nén âm thanh cho chuẩn QuickTime
Đối với hệ thống Mac ngƣời ta thƣờng sử dụng các mã nén âm thanh sau:
+ mLaw 2:1: sử dụng cho việc chuyển các tệp âm thanh với các ứng dụng trên
các máy trạm. Tại đó mLaw là định dạng âm thanh chuẩn, mLaw đƣợc
sử dụng cho điện thoại số ở Bắc Mỹ và Nhật Bản.
+ 16-bit Big Endian và 16-bit Little Endian: sử dụng cho các phần cứng và
phần mềm chuyên dụng để nén âm thanh. Âm thanh đã đƣợc nén bằng
mã nén này thƣờng không tốt cho soạn thảo.
+ 24–bit Integer và 32–bit Integer: sử dụng cho âm thanh 24 bit hoặc 32 bit.
Mã nén này đƣợc sử dụng tốt cho các phần cứng và phần mềm chuyên
dụng. Nó là sản phẩm cuối do đó các tệp video chứa mã nén này không
nên dùng để soạn thảo.
+ IMA 4:1: sử dụng cho các tệp âm thanh tại các trạm. IMA 4:1 đƣợc phát triển
bởi IMA sử dụng mã ADPCM.
+ 32–bit Floating và 64–bit Floating: sử dụng trong các thiết bị phần cứng và
phần mềm chuyên dụng nhƣng thƣờng không sử dụng cho soạn thảo
Video.
+ ALaw 2:1: giống mLaw nhƣng đƣợc sử dụng cho điện thoại số ở châu Âu.
+ QDesign Music Codec: sử dụng để nén các tệp âm thanh chất lƣợng cao
dùng trên Internet. Chất lƣợng của nó tƣơng đƣơng các tệp âm thanh
trên CD-ROM có định dạng 16 bit, 44.1 kHz. Các tệp âm thanh đƣợc
nén theo mã này có thể nghe trực tiếp bằng đƣờng Internet có tốc độ
28.8 Kb/giây.
+ Qualcomm PureVoice: đƣợc thiết kế để tạo các tệp âm thanh tốt nhất ở tần số
8 kHz. Cơ sở của mã nén này dựa trên thuật toán nén chuẩn của
Telephone CDMA.