BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

TRẦN NGỌC HIẾU

NGHIÊN CỨU MỘT SỐ KỸ THUẬT PHÁT HIỆN
CHUYỂN CẢNH TRONG VIDEO

LUẬN VĂN KHOA HỌC MÁY TÍNH

HÀ NỘI, 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

TRẦN NGỌC HIẾU

NGHIÊN CỨU MỘT SỐ KỸ THUẬT PHÁT HIỆN
CHUYỂN CẢNH TRONG VIDEO
Chuyên ngành: Khoa hoc máy tính
Mã số: 60 48 01 01

LUẬN VĂN KHOA HỌC MÁY TÍNH

Người hướng dẫn: PGS.TS. Đỗ Năng Toàn

HÀ NỘI, 2015


LỜI CẢM ƠN

LỜI CẢM ƠN
LỜI CAM ĐOAN
DANH MỤC HÌNH VẼ
MỞ ĐẦU ....................................................................................................... 1
CHƯƠNG 1: KHÁI QUÁT VỀ XỬ LÝ VIDEO VÀ BÀI TOÁN PHÁT
HIỆN CHUYỂN CẢNH ............................................................................... 3
1.1. Khái quát về video...............................................................................................3
1.1.1. Lịch sử.................................................................................................. 3
1.1.1.1. Lịch sử điện ảnh ................................................................................ 3
1.1.1.2. Lịch sử phát sóng truyền hình ............................................................ 3
1.1.1.3. Lịch sử ghi hình video ....................................................................... 4
1.2. Các thao tác cơ bản trong Video .........................................................................5
1.2.1. Đặc điểm của Video ............................................................................. 5
1.2.2. Quá trình thu nhận ảnh .......................................................................... 6
1.2.3 Chuyển hệ màu .................................................................................... 11
1.2.3.1 Không gian màu ............................................................................... 11
1.2.3.2. Cơ sở sinh học.................................................................................. 12
1.2.4 Lấy mẫu các thành phần màu............................................................... 15
1.2.4.1. Khoảng lấy mẫu (Sampling Interval)................................................ 17
1.2.4.2. Định lý lấy mẫu của Shannon ........................................................... 18
1.2.4.3. Các tiêu chuẩn lấy mẫu. ................................................................... 19
1.3 Bài toán trích rút Video trong việc tái tạo Video ............................................. 22
CHƯƠNG 2: MỘT SỐ KỸ THUẬT PHÁT HIỆN CHUYỂN CẢNH
TRONG VIDEO ......................................................................................... 23


2.1. Phát hiện chuyển cảnh dựa vào kỹ thuật trừ ảnh............................................. 23
2.1.1. Trừ ảnh dựa vào điểm ảnh .................................................................. 24
2.1.2. Trừ ảnh phân khối .............................................................................. 25
2.1.3. Trừ ảnh dựa vào biểu đồ ..................................................................... 28

Hình 2.2 Các cửa sổ cơ sở trong thuật toán so sánh thực
Hình 2.3 Chênh lệch biểu đồ, * cắt cảnh,--- chồng mờ
Hình 2.4 So sánh biểu đồ màu giữa 2 ảnh
Hình 2.5 So sánh cặp a, chênh lệch biểu đồ liên tiếp
Hình 2.6 Phát hiện chuyển cảnh dần dần bằng kỹ thuật so sánh cặp
Hình 2.7 Ảnh trung bình cho kênh màu đỏ, biên ngang, và biên thẳng đứng
tại frame
Hình 2.8 Phép trừ màu cho khung 65 và 70
Hình 2.9 Phép trừ biên cho frame 65 và 70
Hình 2.10 Kết hợp trừ màu và trừ biên cho frame 65 và 70
Hình 2.11 Kết quả kết hợp sau khi sử dụng bộ lọc trung bình ngưỡng trễ cho
frame 60 và 70
Hình 2.12 Ví dụ cho tính toán mã LBP gốc
Hình 2.13 Lận cận cân đối vòng tròn được đặt với những giá trị khác nhau
của P và R
Hình 2.14 Giải thuật sử dụng cấu trúc lưới chồng cục bộ
Hình 2.15 Đồ thị của biến thiên cục bộ mm qua thời gian


1

MỞ ĐẦU
1. Lý do chọn đề tài
Trong thời đại ngày nay công nghệ thông tin hầu như đã thâm nhập vào
toàn bộ các lĩnh vực đời sống xã hội. Xã hội càng phát triển thì nhu cầu về
công nghệ thông tin ngày càng cao, do vậy dữ liệu số hầu như không còn xa
lạ đối với mỗi người chúng ta. Trong mọi lĩnh vực các ứng dụng công nghệ
thông tin đã trợ giúp con người rất nhiều. Hiện nay, thông tin hình ảnh đóng
vai trò rất quan trọng trong trao đổi thông tin, bởi phần lớn các thông tin mà
con người thu nhận được đều thông qua thị giác.

Thu thập tài liệu, phân tích, suy luận, tổng hợp, đánh giá. Từ đó đề xuất
nghiên cứu và tìm hiểu: “Nghiên cứu một số kỹ thuật phát hiện chuyển cảnh
trong video”.
6. Cấu trúc của luận văn
Ngoài phần Mở đầu, kết luận và tài liệu tham khảo luận văn gồm 3 chương:
Chương 1: Khái quát về xử lý video và bài toán phát hiện chuyển cảnh
1.1 Khái quát về video
1.2 Các thao tác cơ bản trong video
1.3 Bài toán phát hiện chuyển cảnh trong video
Chương 2: Một số kỹ thuật phát hiện chuyển cảnh trong video
2.1. Phát hiện chuyển cảnh dựa vào kỹ thuật trừ ảnh
2.2. Phát hiện chuyển cảnh dựa vào kỹ thuật trừ nền
2.3. Phát hiện chuyển cảnh dựa vào độ đo kết cấu LBP (Local Binary Patterm)
2.4. Phát hiện chuyển cảnh dựa vào sự biến thiên cục bộ của vecter kết cấu SP
Chương 3: Chương trình thử nghiệm
3.1 Đặt vấn đề
3.2 Phân tích và lựa chọn công cụ
3.3 Một số giao diện của chương trình


3

CHƯƠNG 1: KHÁI QUÁT VỀ XỬ LÝ VIDEO
VÀ BÀI TOÁN PHÁT HIỆN CHUYỂN CẢNH
1.1. Khái quát về video
1.1.1. Lịch sử
1.1.1.1. Lịch sử điện ảnh
Điện ảnh mới chỉ có hơn 100 năm tuổi. Sự ra đời của điện ảnh là ngày 28
Tháng 12 năm 1895 khi Auguste và Louis Lumiμere cho phát bộ phim của họ
cho một đối tượng trả tiền ở Paris. Sự phát triển của máy ảnh và máy chiếu

Thiết bị quay video có sau nhiều so với TV. Các thiết bị đã được phát
minh vào đầu những năm 1950 và RCA đã phát triển một máy tính với tốc độ
băng 6 m / giây. Họ đã sử dụng ghi âm theo chiều dọc của tín hiệu trên băng,
vì vậy tốc độ nhanh đã được yêu cầu để ghi lại các tín hiệu truyền hình băng
thông lớn. Máy ghi hình thực tế đầu tiên được phát triển vào năm 1953 bởi
tập đoàn Ampex. Nó được sử dụng sự sắp xếp quét xoắn ốc mà ngày nay
chúng ta vẫn sử dụng và cho phép tốc độ ghi lại hiệu quả cao hơn mà không
có một tốc độ băng đáng sợ.
Các thiết bị video gia đình đầu tiên được phát triển bởi Philips vào năm
1972 đã được nhanh chóng thay thế bởi các máy VHS của Panasonic và các
máy Betamax của Sony trong năm 1978. Sự xuất hiện của các định dạng đánh
dấu sự khởi đầu của kỷ nguyên video gia đình. Khả năng ghi và chỉnh sửa
chương trình được thực hiện bởi người sử dụng nhà tăng sự phổ biến của
truyền hình. Sony đã thua cuộc chiến tiếp thị bây giờ nổi tiếng vào năm 1980
khi VHS đã trở thành tiêu chuẩn chính cho người sử dụng video gia đình chủ
yếu là do thời gian còn chơi của nó . Đây là mặc dù chất lượng cao của các
định dạng Betamax.


5
1.2. Các thao tác cơ bản trong Video
1.2.1. Đặc điểm của Video
Ảnh Video: Là một chuỗi các ảnh tĩnh, chuỗi các frame ảnh (gọi là
khung hình), xuất hiện liên tiếp tạo cảm thụ theo thời gian, quan hệ thời gian
giữa các frame biểu diễn ảnh động.
S = f (x,y,t)
trong đó:
- x, y tọa độ điểm ảnh ( Thông tin về không gian).
- t: thông tin về thời gian.
 ảnh tĩnh là 1 trường hợp riêng của video, khi đó nó là một chuỗi các

50 frames/s;25 images/s
- Film : 24 images/s
1.2.2 Quá trình thu nhận ảnh
Các thiết bị thu nhận ảnh bao gồm camera, scanner các thiết bị thu nhận
này có thể cho ảnh đen trắng…
Các thiết bị thu nhận ảnh có 2 loại chính ứng với 2 loại ảnh thông dụng
Raster, Vector.
Các thiết bị thu nhận ảnh thông thường Raster là camera. Các thiết bị thu
nhận ảnh thông thường Vector là sensor hoặc bàn số hoá Digitalizer hoặc
được chuyển đổi từ ảnh Raster.
Nhìn chung các hệ thống thu nhận ảnh thực hiện 1 quá trình
• Cảm biến: biến đổi năng lượng quang học thành năng lượng điện
• Tổng hợp năng lượng điện thành ảnh.
Ảnh trên máy tính là kết quả thu nhận theo các phương pháp số hoá được
nhúng trong các thiết bị kỹ thuật khác nhau. Quá trình lưu trữ ảnh nhằm 2
mục đích:
• Tiết kiệm bộ nhớ


7
• Giảm thời gian xử lý
Việc lưu trữ thông tin trong bộ nhớ có ảnh hưởng rất lớn đến việc hiển thị, in
ấn và xử lý ảnh được xem như là 1 tập hợp các điểm với cùng kích thước nếu sử
dụng càng nhiều điểm ảnh thì bức ảnh càng đẹp, càng mịn và càng thể hiện rõ hơn
chi tiết của ảnh người ta gọi đặc điểm này là độ phân giải.
Việc lựa chọn độ phân giải thích hợp tuỳ thuộc vào nhu cầu sử dụng và
đặc trưng của mỗi ảnh cụ thể, trên cơ sở đó các ảnh thường được biểu diễn
theo 2 mô hình cơ bản:
a) Mô hình Raster
Đây là cách biểu diễn ảnh thông dụng nhất hiện nay, ảnh được biểu diễn

Công nghệ phần cứng cung cấp những thiết bị xử lý với tốc độ nhanh và chất
lượng cho cả đầu vào và ra nhưng lại chỉ hỗ trợ cho ảnh Raster. Do vậy, những
nghiên cứu về biểu diễn vectơ đều tập trung từ chuyển đổi từ ảnh Raster.

Hình 1.2 Sự chuyển đổi giữa các mô hình biểu diễn ảnh
Để dễ tưởng tượng, xét các bước cần thiết trong xử lý ảnh. Đầu tiên, ảnh
tự nhiên từ thế giới ngoài được thu nhận qua các thiết bị thu (như Camera,
máy chụp ảnh). Trước đây, ảnh thu qua Camera là các ảnh tương tự (loại
Camera ống kiểu CCIR). Gần đây, với sự phát triển của công nghệ, ảnh màu
hoặc đen trắng được lấy ra từ Camera, sau đó nó được chuyển trực tiếp thành
ảnh số tạo thuận lợi cho xử lý tiếp theo. (Máy ảnh số hiện nay là một thí dụ


9
gần gũi). Mặt khác, ảnh cũng có thể tiếp nhận từ vệ tinh; có thể quét từ ảnh
chụp bằng máy quét ảnh.

Hình 1.3 Các bước cơ bản trong xử lý ảnh
Sơ đồ này bao gồm các thành phần sau:
-

Phần thu nhận ảnh (Image Acquisition)

Ảnh có thể nhận qua camera màu hoặc đen trắng. Thường ảnh nhận qua
camera là ảnh tương tự (loại camera ống chuẩn CCIR với tần số 1/25, mỗi ảnh
25 dòng), cũng có loại camera đã số hoá (như loại CCD - Change Coupled
Device) là loại photodiot tạo cường độ sáng tại mỗi điểm ảnh.
Camera thường dùng là loại quét dòng ; ảnh tạo ra có dạng hai chiều.
Chất lượng một ảnh thu nhận được phụ thuộc vào thiết bị thu, vào môi trường
(ánh sáng, phong cảnh)


và

nội

suy

ảnh

(Image

Recognition

and

Interpretation)
Nhận dạng ảnh là quá trình xác định ảnh. Quá trình này thường thu được
bằng cách so sánh với mẫu chuẩn đã được học (hoặc lưu) từ trước. Nội suy là
phán đoán theo ý nghĩa trên cơ sở nhận dạng. Ví dụ: một loạt chữ số và nét
gạch ngang trên phong bì thư có thể được nội suy thành mã điện thoại. Có
nhiều cách phân loai ảnh khác nhau về ảnh. Theo lý thuyết về nhận dạng, các
mô hình toán học về ảnh được phân theo hai loại nhận dạng ảnh cơ bản:
- Nhận dạng theo tham số.
- Nhận dạng theo cấu trúc.
Một số đối tượng nhận dạng khá phổ biến hiện nay đang được áp dụng
trong khoa học và công nghệ là: nhận dạng ký tự (chữ in, chữ viết tay, chữ ký
điện tử), nhận dạng văn bản (Text), nhận dạng vân tay, nhận dạng mã vạch,
nhận dạng mặt người…



1.2.3.2 Cơ sở sinh học
Các màu gốc có liên quan đến các khái niệm sinh học hơn là vật lý, nó
dựa trên cơ sở phản ứng sinh lý học của mắt người đối với ánh sáng. Mắt
người có các tế bào cảm quang có hình nón nên còn được gọi là tế bào hình
nón, các tế bào này thông thường có phản ứng cực đại với ánh sáng vàng xanh lá cây (tế bào hình nón L), xanh lá cây (tế bào hình nón M) và xanh lam
(tế bào hình nón S) tương ứng với các bước sóng khoảng 564 nm, 534 nm và
420 nm. Ví dụ, màu vàng thấy được khi các tế bào cảm nhận màu xanh ánh
vàng được kích thích nhiều hơn một chút so với tế bào cảm nhận màu xanh lá
cây và màu đỏ cảm nhận được khi các tế bào cảm nhận màu vàng - xanh lá
cây được kích thích nhiều hơn so với tế bào cảm nhận màu xanh lá cây. Mặc
dù biên độ cực đại của các phản xạ của các tế bào cảm quang không diễn ra ở
các bước sóng của màu "đỏ", "xanh lá cây" và "xanh lam", ba màu này được
mô tả như là các màu gốc vì chúng có thể sử dụng một cách tương đối độc lập
để kích thích ba loại tế bào cảm quang. Để sinh ra khoảng màu tối ưu cho các
loài động vật khác, các màu gốc khác có thể được sử dụng. Với các loài vật có
bốn loại tế bào cảm quang, chẳng hạn như nhiều loại chim, người ta có lẽ phải
nói là cần tới bốn màu gốc; cho các loài vật chỉ có hai loại tế bào cảm quang,
như phần lớn các loại động vật có vú, thì chỉ cần hai màu gốc.
Biểu diễn dạng số 24 bit: Khi biểu diễn dưới dạng số, các giá trị RGB
trong mô hình 24 bpp thông thường được ghi bằng cặp ba số nguyên giữa 0


13
và 255, mỗi
ỗi số đại diện cho cường
c
độ của màu đỏ,
ỏ, xanh lá cây, xanh lam
trong trật tự như thế.
ế. Số lượng

ịnh nghĩa RGB kỹ thuật số trong CCIR 601.
Kiểu 16 bit: Kiểu
ểu 16 bpp, trong đó hoặc là
là có 5 bit cho m
mỗi màu, gọi là
kiểu 555 hay thêm một
ột bit còn
c lại cho màu xanh
anh lá cây (vì m
mắt có thể cảm
nhận màu này tốt hơn
ơn so với
v các màu khác), gọi là kiểu
ểu 565. Kiểu 24 bpp nói
chung được gọi là thật
ật màu,
m trong khi kiểu 16 bpp được gọi là cao màu.
màu
Kiểu 32 bit: Kiểu
ểu 32 bpp phần lớn là sự
ự đồng nhất chính xác với kiểu 24
bpp, do ở đây thực sự cũng chỉ có 8 bit cho mỗi màu
màu thành ph
phần, tám bit dư
đơn giản là không sử
ử dụng (ngoại trừ khả năng sử dụng nh
như
ư là kênh alpha).
Lý do của
ủa việc mở rộng của kiểu 32 bpp là

15
Chuyển đổi hệ màu:
Chuyển đổi từ RGB sang YUV:
- Cách 1:
Y = 0.299R + 0.587G + 0.114B.
U = 0.492(B − Y) = − 0.147R − 0.289G + 0.436B.
V = 0.877(R − Y) = 0.615R − 0.515G − 0.100B.
- Cách 2: (Dùng ma trận).

Chuyển đổi từ YUV sang YCrCb (JPEG):
Y = Y;
Cb = U/2 + 0.5.
Cr = V/1.6 + 0.5
1.2.4 Lấy mẫu các thành phần màu
Lấy mẫu là một quá trình, qua đó ảnh được tạo nên trên một vùng có tính
liên tục được chuyển thành các giá trị rời rạc theo tọa độ nguyên. Quá trình
này gồm 2 lựa chọn:
- Một là: khoảng lấy mẫu được đảm bảo nhờ lý thuyết lấy mẫu Shannon.
- Hai là: cách thể hiện dạng mẫu liên quan đến độ đo (Metric) được dùng
trong miền rời rạc.
Tọa độ màu tĩnh: Là tọa độ của các điểm màu tĩnh trong đó đồ thị tĩnh
màu của hệ tọa độ x, y tiêu chuẩn.


16

Độ phân giải ( Resolution): Là độ sắc nét của hình ảnh thể hiện qua số
dòng và số cột của màn ảnh hay số phần tử hình ảnh trên một đơn vị diện tích.
Ví dụ: Độ phân giải của ảnh trên màn hình CGA (Color Graphic
Adaptor) là một lưới điểm theo chiều ngang màn hình: 320 điểm chiều dọc *

g(x)≈g(rΔx)
Khi đó tín hiệu lấy mẫu được mô hình hoá:

(tích chập trong miền không gian x.)
Hoặc tương đương:


18
Trong thực tế, r không thể tính được trong khoảng vô hạn (từ − ∞ đến
+∞) mà là một số lượng NΔx mẫu lớn cụ thể. Như vậy, để đơn giản có thể nói
hàm liên tục g(x) có thể biểu diễn trên một miền với độ dài NΔx mẫu thành
chuỗi như sau:
g(x) ≈ {g(0), g(Δx), g(2Δx),..., g((N −1)Δx) }
Chú ý 1: Khoảng lấy mẫu (Sampling Interval) Δx là một tham số cần
phải được chọn đủ nhỏ, thích hợp, nếu không tín hiệu thật không thể khôi
phục lại được từ tín hiệu lấy mẫu.
Chú ý 2: Từ lý thuyết về xử lý tín hiệu số tích chập trong miền không
gian x tương đương với tích chập trong miền tần số ω tức là biến đổi Fourier
của gs(x) là:

trong đó ωx là giá trị tần số ứng với giái trị x trong miền không gian.
Điều kiện khôi phục ảnh lấy mẫu về ảnh thật được phát biểu từ định lý
lẫy mẫu của Shannon.
1.2.4.2 Định lý lấy mẫu của Shannon
Giả sử g(x) là một hàm giới hạn giải (Band Limited Function) và biến đổi
Fourier của nó là

đối với các giá trị

. Khi đó g(x) có thể