HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG
---------------------------------------

NGUYỄN THANH TUẤN

NGHIÊN CỨU TĂNG TỐC ĐỘ TÌM KIẾM VECTOR CHUYỂN ĐỘNG TRONG
NÉN VIDEO SỬ DỤNG KIẾN TRÚC SONG SONG GPU NVIDIA VÀ CÔNG NGHỆ
CUDA

Chuyên ngành: HỆ THỐNG THÔNG TIN
Mã số: 60.48.01.04

LUẬN VĂN THẠC SĨ KỸ THUẬT

NGƢỜI HƢỚNG DẪN KHOA HỌC:
PGS.TS. TRẦN VĂN HOÀI

THÀNH PHỐ HỒ CHÍ MINH – NĂM 2016


LỜI CAM ĐOAN
Tôi xin cam đoan luận văn Thạc sĩ: “Nghiên cứu tăng tốc độ tìm kiếm véc tơ chuyển
động trong nén video sử dụng kiến trúc song song GPU NVIDIA và công nghệ CUDA ” là
công trính nghiên cứu của riêng tôi.
Các số liệu, kết quả đƣợc trính bày trong luận văn là trung thực, chƣa từng đƣợc
công bố trong bất kỳ công trính nào khác.
Tp.Hồ Chí Minh, ngày 23 tháng 06 năm 2016
HỌC VIÊN THỰC HIỆN LUẬN VĂN

NGUYỄN THANH TUẤN

LỜI CẢM ƠN
Tôi xin đặc biệt cảm ơn PGS.TS. Trần Văn Hoài, ngƣời đã trực tiếp chỉ bảo, dành
nhiều thời gian, tâm huyết, góp ý và động viên tôi để tôi hoàn thành đƣợc văn tốt nghiệp
này.
Xin gửi lời cảm ơn chân thành tới các thầy, cô cuả Học viện Công nghệ bƣu chình
viễn thông tạo điều kiện thuận lợi, nhiệt tính giúp đỡ tôi trong suốt quá trính nghiên cứu.
Trong quá trính nghiên cứu đề tài này, mặc dù đã có nhiều cố gắng nhƣng luận văn
không thể tránh khỏi những thiếu sót, tôi rất mong nhận đƣợc sự góp ý chân thành của quý
thầy, cô. Tôi xin chân thành cảm ơn!
Tp.Hồ Chí Minh, ngà y 23 tháng 06 nă m 2016
HỌC VIÊN THỰC HIỆN LUẬN VĂN

NGUYỄN THANH TUẤN


MỤC LỤC
LỜI CAM ĐOAN .................................................................................................................. i

LỜI CẢM ƠN ............................................................................................................ ii
MỤC LỤC ................................................................................................................. iii
DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT .............................................. vi
DANH SÁCH HÌNH VẼ ........................................................................................ viii
DANH SÁCH BẢNG .................................................................................................x
MỞ ĐẦU .....................................................................................................................1
CHƢƠNG 1. TỔNG QUAN VỀ BÙ CHUYỂN ĐỘNG VÀ CÁC THUẬT TOÁN
ĐỂ TÌM VÉC TƠ CHUYỂN ĐỘNG TRONG NÉN VIDEO ....................................3
1.1. Tổng quan về bù chuyển động trong MPEG ...................................................14
1.1.1. Khái niệm về nén Video ...........................................................................14
1.1.2. Giới thiệu chung về chuẩn MPEG .............................................................6

1.1.3. Phƣơng pháp nén video theo chuẩn MPEG ...............................................7
1.1.3.1. Các cấu trúc ảnh ..................................................................................7
1.1.3.2. Nhóm ảnh (GOP) ................................................................................8
1.1.3.3. Cấu trúc dòng bit MPEG ...................................................................10
1.1.4. Phƣơng pháp nén video theo chuẩn MPEG .............................................12
1.1.4.1. Mô hính tổng quát bộ mã hóa video theo chuẩn MPEG ...................12
1.1.4.2. Lấy thông tin theo màu .....................................................................13
1.1.4.3. Lƣợng tử hóa .....................................................................................16
1.1.4.4. Nội suy ảnh .......................................................................................17
1.1.4.5. Dự đoán bù chuyển động ..................................................................17
1.2. Các thuật toán để tím véc tơ chuyển động ......................................................23
1.2.1. Thuật toán tím kiếm ba bƣớc ...................................................................23
1.2.2. Thuật toán tím kiếm 2D-logarit................................................................24
1.2.3. Thuật toán tím kiếm trực giao ..................................................................34


1.2.4. Thuật toán tím kiếm CROSS....................................................................26
1.2.5. Thuật toán tím kiếm ba bƣớc mới ............................................................27
1.2.6. Thuật toán tím kiếm bốn bƣớc .................................................................28
1.2.7. Thuật toán tím kiếm khối dựa trên gradient descent ................................39
1.2.8. Thuật toán tím kiếm Diamond .................................................................31
CHƢƠNG 2. TỔNG QUAN VỀ CẤU TRÚC HỆ THỐNG XỬ LÝ ĐỒ HỌA GPU
VÀ CÔNG NGHỆ TÍNH TOÁN SONG SONG DỮ LIỆU CUDA ........................33
2.1. Giới thiệu đại cƣơng về tình toán song song ...................................................33
2.1.1. Tổng quan về tình toán song song............................................................33
2.1.1.1. Tại sao phải tình toán song song .......................................................33
2.1.1.2. Một số khái niệm về xử lý song song ...............................................33
2.1.2. Phân loại các kiến trúc song song ............................................................34
2.1.2.1. Kiến trúc đơn dòng lệnh, đơn luồng dữ liệu (SISD) .........................35
2.1.2.2. Kiến trúc đơn dòng lệnh, đa luồng dữ liệu (SIMD) ..........................35

2.1.2.3. Kiến trúc đa dòng lệnh, đơn luồng dữ liệu (MISD) ..........................36
2.1.2.4. Kiến trúc đa dòng lệnh, đa luồng dữ liệu (MIMD) ...........................37
2.1.3. Các mô hính lập trính song song ..............................................................37
2.1.3.1. Lập trính bộ nhớ dùng chung ............................................................37
2.1.3.2. Lập trính truyền thông điệp ...............................................................38
2.1.3.3. Mô hính song song dữ liệu ................................................................38
2.1.3.4. Mô hính hƣớng đối tƣợng .................................................................39
2.1.3.5. Mô hình logic ....................................................................................39
2.1.4. Đánh giá hiệu quả tình toán song song ....................................................39
2.2. Cấu trúc hệ thống xử lý dữ liệu đồ họa GPU ..................................................43
2.2.1. Giới thiệu về công nghệ GPU ..................................................................43
2.2.2. Tím hiểu kiến trúc GPU ...........................................................................43
2.2.2.1. Đƣờng ống dẫn đồ họa ......................................................................44
2.2.2.2. Tiến hóa của kiến trúc GPU ..............................................................45
2.2.2.3. Kiến trúc GPU hiện tại ......................................................................46


2.2.3. So sánh GPU và CPU ...............................................................................48
2.2.4. Ứng dụng của GPU trong các lĩnh vực ....................................................49
2.3. Công nghệ tình toán song song hỗ trợ dữ liệu CUDA ....................................50
2.3.1. Giới thiệu về công nghệ CUDA ...............................................................50
2.3.2. Cấu trúc của CUDA .................................................................................52
2.3.3. Ứng dụng của CUDA trong các lĩnh vực công nghệ ...............................54
2.3.3.1. CUDA trong ngành công nghiệp trò chơi .........................................54
2.3.3.2. CUDA trong các ứng dụng video số .................................................54
2.3.4. Môi trƣờng lập trính với CUDA ..............................................................55
2.3.5. Lập trính song song với CUDA ...............................................................56
2.3.5.1. CUDA là mở rộng của ngôn ngữ lập trính C ....................................56
2.3.5.2. Những mở rộng của CUDA so với ngôn ngữ lập trính C .................57
2.3.5.3. Từ khóa vi phạm kiểu hàm ...............................................................57

2.3.5.4. Từ khóa vi phạm kiểu biến ...............................................................57
2.3.5.5. Cấu hính thực thi ...............................................................................58
2.3.5.6. Các biến built-in ................................................................................59
2.3.5.7. Biên dịch với NVCC .........................................................................59
CHƢƠNG 3. MÔ TẢ CHƢƠNG TRÌNH VÀ CÁC KẾT QUẢ THỰC NGHIỆM ĐẠT ĐƢỢC
3.1. Mô tả chƣơng trính ..........................................................................................68
3.1.1. Song song hóa các thuật toán tím kiếm véc tơ chuyển động trên
CUDA. ....................................................................................................................68
3.1.2. Xây dựng chƣơng trính thực nghiệm .......................................................63
3.2. Kết quả thực nghiệm đạt đƣợc ........................................................................67
3.3. Đánh giá kết quả thực nghiệm đạt đƣợc ..........................................................72
KẾT LUẬN VÀ KIẾN NGHỊ...................................................................................82
TÀI LIỆU THAM KHẢO .........................................................................................77


DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT
Viết tắt

Tiếng Anh

Tiếng Việt

BMA

Block Matching Algorithm

Thuật toán so khớp nối

BDM


Block Distortion Measure

Độ đo biến dạng khối

BMME

Block

Matching

Motion Ƣớc lựợng chuyển động phối hợp

khối

Estimation
CUDA

Compute

Unified

Device Kiến trúc thiết bị hợp nhất cho tình toán

Architecture
DCT

Discrete Cosine Transform

Biến đổi cosin rời rạc


DFT

Discrete Fourier Transform

Biến đổi fourier rời rạc

DS

Diamond Search

Thuật toán tím kiếm kim cƣơng

DMS

Discrete Memory less Source

Nguồn không nhớ rời rạc

DPCM

Differential

Pulse

Code Điều chế xung mã vi sai

Modulation
FS

Full Search


Thuật toán tím kiếm đầy đủ (Vét cạn)

FT

Fourier Transform

Biến đổi Fourier

FFT

Fast Fourier Transform

Biến đổi Fourier nhanh

GPU

Graphics Processing Unit

Bộ xử lý đồ họa

GPGPU

General Purpose computing on Bộ xử lý đồ họa xử lý các công việc
graphics processing units

của CPU

4SS


Four Step Search

Thuật toán tím kiếm 4 bƣớc

IDCT

Inverse

Discrete

Cosine Biến đổi ngƣợc DCT

Transform
HVS

Human Visual System

Hệ thống nhín của con ngƣời

LMS

Least Mean Square

Bính phƣơng trung bính tối thiểu

LDSP

Large Diamond Search Pattern

Thuật toán tím kiếm kim cƣơng lớn


MAD

Mean Absolute Deviation

Độ lệch trị tuyệt đối trung bính

MSE

Mean Squared Error

Sai số trung bính bính phƣơng

MPEG

Moving Picture Experts Group

Nhóm các chuyên gia hính ảnh động

NTSS

New Three Step Search

Thuật toán tím kiếm ba bƣớc mới

NCCF

Normalized Cross Correlation Hàm tƣơng quan chéo chuẩn hóa



Function
PSNR

Peak Signal to Noise Rate

Tỷ số tìn hiệu đỉnh trên nhiễu

TSS

Three Step Search

Thuật toán tím kiếm ba bƣớc

SAD

Sum of Absolute Differences

Tổng các sai phân tuyệt đối

SDSP

Small Diamons Search Pattern

Thuật toán tím kiếm kim cƣơng nhỏ

SSD

Sum Squared Difference

Tổng các sai phân bính phƣơng


VLC

Variable Length Coding

Mã hóa với độ dài từ mã thay đổi


DANH SÁCH HÌNH VẼ
Hính 1.1. Sơ đồ khối hệ thống nén ảnh tiêu biểu

3

Hính 1.2. Hệ thống các chuẩn MPEG

7

Hính 1.3. Cấu trúc GOP mở

8

Hình 1.4. Cấu trúc GOP đóng

9

Hính 1.5. Kiến trúc dòng dữ liệu MPEG

11

Hính 1.6. Bộ mã hóa MPEG tiêu biểu


12

Hính 1.7. Cấu trúc lấy mẫu theo chuẩn 4:4:4

14

Hính 1.8. Cấu trúc lấy mẫu theo chuẩn 4:2:2

15

Hính 1.9. Cấu trúc lấy mẫu theo chuẩn 4:2:0

15

Hính 1.10. Cấu trúc lấy mẫu theo chuẩn 4:1:1

16

Hính 1.11. Ƣớc lƣợng chuyển động so sánh khối

20

Hính 1.12. Chia cửa sổ tím kiếm dƣới dạng lƣới theo BMA

21

Hính 1.13. Minh họa quá trính bù chuyển động theo giải thuật BMA

22


Hính 1.14. Mô hính tím kiếm theo thuật toán TSS

24

Hính 1.15. Hai đƣờng tím kiếm của thuật toán tím kiếm 2DLOG

25

Hính 1.16. Hai đƣờng tím kiếm của thuật toán tím kiếm trực giao

26

Hính 1.17. Hai đƣờng kiểm tra theo thuật toán tím kiếm CROSS

27

Hính 1.18. Hai đƣờng tím kiếm của thuật toán tím kiếm ba bƣớc mới

28

Hính 1.19. Hai đƣờng tím kiếm chuyển động lớn theo thuật toán FSS

29

Hính 1.20. Hai đƣờng tím kiếm chuyển động nhỏ của thuật toán FSS

29

Hính 1.21. Mô hính tím kiếm của thuật toán BBGDS


31

Hính 1.22. Mô hính tím kiếm theo thuật toán tím kiếm Diamond

32

Hính 2.1. Mô hính kiến trúc máy SISD

35

Hính 2.2. Mô hính kiến trúc máy SIMD

36

Hính 2.3. Mô hính kiến trúc máy MISD

36

Hính 2.4. Mô hính kiến trúc máy MIMD

37

Hính 2.5. Mô tả lập trính giữa các tác vụ dùng chung bộ nhớ

37

Hính 2.6. Mô hính lập trính truyền thông giữa hai tác vụ trên hai



máy tính

38

Hính 2.7. Mô hính lập trính song song dữ liệu

38

Hính 2.8. Kỹ thuật xen kẽ tình toán và truyền thông giữa P1 và P2

40

Hình 2.9. So sánh kiến trúc CPU và GPU

48

Hình 2.10. So sánh Gflops giữa GPU và CPU

49

Hình 2.11. Kiến trúc bộ phần mềm NVidia CUDA

51

Hình 2.12. Các thao tác thu hồi và cấp phát bộ nhớ với CUDA

51

Hình 2.13. Vùng nhớ dùng chung mang dữ liệu gần ALU hơn


52

Hính 2.14. Phân cấp luồng CUDA

53

Hính 2.15. Sơ đồ hoạt động truyền dữ liệu giữa Host và Device

56

Hính 3.1. Tuyến tình hóa luồng theo chỉ số x

62

Hính 3.2. Hai khung ảnh đầu vào đƣợc tách từ video Foreman

64

Hính 3.3. Hai khung ảnh đầu vào đƣợc chuyển sang định dạng .PGM

64

Hính 3.4. Kết quả chạy chƣơng trính với 2 khung ảnh

65

Hính 3.5. Ảnh chứa các véc tơ chuyển động

65


Hính 3.6. Ảnh bù chuyển động

66

Hính 3.7. Ảnh so sánh độ dƣ thừa với ảnh gốc sau khi bù chuyển động

66

Hính 3.8. Kết quả chạy chƣơng trính với 200 frame ảnh đầu vào

67

Hính 3.9. Giao diện phần mềm FFmpeg

68

Hính 3.10. Các khung ảnh tuần tự đƣợc xem bằng phần mềm MegaView

69

Hính 3.11. Một khung ảnh đƣợc trìch trong bộ test “football”

69

Hính 3.12. Véc tơ chuyển động của khung ảnh hính 3.10

70

Hính 3.13. Biểu đồ so sánh hiệu năng giữa các thuật toán trên GPU và
CPU


72

Hính 3.14. Biểu đồ so sánh chất lƣợng nén video theo hệ số PSNR

72


DANH SÁCH BẢNG
Bảng 2.1. Mô tả phân loại kiến trúc của Flynn

35

Bảng 3.1. Thời gian tình toán của các thuật toán trên CPU (tính
bằng giây)

70

Bảng 3.2. Thời gian tình toán của các thuật toán trên GPU (tình
bằng giây)

71

Bảng 3.3. Bảng kết quả tình toán PSNR trung bính(tình
bằng dexiBen)

71


MỞ ĐẦU

Kỹ thuật nén ảnh số đang đóng một vai trò cực kỳ quan trọng trong các hệ thống viễn
thông và truyền thông đa phƣơng tiện để giải quyết vấn đề băng thông của đƣờng truyền. Tìn
hiệu video số hóa chiếm băng thông lớn hơn rất nhiều lần so với tìn hiệu tƣơng tự. Chình ví
vậy, kỹ thuật bù chuyển động với việc xác định véc tơ chuyển động sẽ làm giảm thông tin dƣ
thừa giữa các frame liên tiếp giống nhau trong miền không gian và thời gian nhằm giảm kích
thƣớc dữ liệu để thực hiện nén video.
Tuy nhiên, kỹ thuật tình toán bù chuyển động đòi hỏi phải tím đƣợc chuyển động chình
xác của đối tƣợng và công việc này chiếm phần lớn thời gian thực hiện của giải thuật. Để
giảm thời gian thực hiện của quá trính nén video, ngoài việc cải tiến thuật toán tím kiếm véc
tơ chuyển động, việc tăng hiệu năng của các thiết bị tình toán cũng rất quan trọng.
Hiện nay, việc tăng tốc độ của CPU đã chạm tới ngƣỡng tối đa, ví ở tốc độ cao, nhiệt
độ CPU cũng tăng cao, trong khi các giải pháp tản nhiệt đã đến mức giới hạn, không thể đáp
ứng đƣợc khả năng làm mát CPU. Trƣớc tính hính đó các nhà nghiên cứu vi xử lý đã chuyển
hƣớng sang phát triển công nghệ đa lõi với cơ chế xử lý song song trong các máy tình. Trong
những năm gần đây, một trong những hƣớng nghiên cứu nhiều tiềm năng là sử dụng chip đồ
họa GPU và công nghệ xử lý song song CUDA do hãng NVIDIA phát triển nhằm tăng tốc độ
xử lý, nâng cao hiệu quả của thuật toán. Xuất phát từ những phân tìch ở trên, tác giả đã chọn
đề tài “Nghiên cứu tăng tốc độ tím kiếm véc tơ chuyển động trong nén video sử dụng kiến
trúc song song GPU NVIDIA và công nghệ CUDA”.
Nội dung luận văn gồm phần mở đầu, phần kết luận và ba chƣơng với nội dung cụ thể
nhƣ sau:
Chƣơng 1: Tổng quan về bù chuyển động và các thuật toán để tìm véc tơ chuyển
động trong nén video
Nội dung chình của chƣơng này là giới thiệu tổng quan về kỹ thuật bù chuyển động
trong nén video theo chuẩn MPEG và các thuật toán để tím kiếm véc tơ
chuyển động trong thuật toán so sánh khối.
Chƣơng 2: Tổng quan về cấu trúc hệ thống xử lý đồ họa GPU và công nghệ tính
toán song song dữ liệu CUDA
Trong chƣơng này, tác giả giới thiệu những kiến thức đại cƣơng về tình toán song song,
cấu trúc của hệ thống xử lý dữ liệu đồ họa GPU và công nghệ tình toán song song dữ liệu

CUDA của hãng NVIDIA.
Chƣơng 3: Mô tả chƣơng trình và các kết quả thử nghiệm đạt đƣợc


Từ những kiến thức đã nghiên cứu đƣợc ở chƣơng 1 và chƣơng 2, trong chƣơng 3 tác
giả tiến hành xây dựng ứng dụng song song hóa các thuật toán tím véc tơ chuyển động trên
thiết bị đồ họa của hãng NVIDIA sử dụng công nghệ CUDA và tiến hành thực nghiệm, đánh
giá các kết quả đạt đƣợc trên các bộ test chuẩn.


CHƢƠNG 1. TỔNG QUAN VỀ BÙ CHUYỂN ĐỘNG VÀ
CÁC THUẬT TOÁN ĐỂ TÌM VÉC TƠ CHUYỂN ĐỘNG
TRONG NÉN VIDEO
1.1. Tổng quan về bù chuyển động trong MPEG
1.1.1. Khái niệm về nén video
Trong lĩnh vực truyền thông video, kỹ thuật xử lý tìn hiệu chủ yếu tập trung vào mục
đìch nén. Ngƣời ta thƣờng sử dụng 3 phƣơng pháp nén đối với hính ảnh dựa vào các loại độ
dƣ: dƣ thừa không gian, dƣ thừa phổ và dƣ thừa tâm sinh lý nhín.
Nén về cơ bản là một quá trính trong đó số lƣợng số liệu (data) biểu diễn lƣợng thông
tin của một ảnh hoặc nhiều ảnh đƣợc giảm bớt bằng cách loại bỏ những
số liệu dƣ thừa trong tìn hiệu video. Các chuỗi ảnh truyền hính có nhiều phần ảnh giống
nhau. Vậy tìn hiệu truyền hính có chứa nhiều dữ liệu dƣ thừa, ta có thể bỏ qua mà không làm
mất thông tin hính ảnh. Đó là các phần xóa dòng, xóa mành, vùng ảnh tĩnh hoặc chuyển động
rất chậm, vùng ảnh nền giống nhau, mà ở đó các phần tử liên tiếp hoặc khác nhau rất ìt.
Ngoài ra, để tăng hệ số nén ảnh động, chuyển động trong ảnh truyền hính phải đƣợc
dự báo, khi đó, ta chỉ cần truyền các thông tin về hƣớng và mức độ (véc tơ) chuyển động của
các vùng ảnh khác nhau. Các phần tử lân cận trong ảnh thƣờng giống nhau, do đó chỉ cần
truyền các thông tin biến đổi. Các hệ thống nén sử dụng đặc tình này của tìn hiệu video và
các đặc trƣng của mắt ngƣời (là kém nhạy với sai số trong hính ảnh có nhiều chi tiết và các phần
tử chuyển động). Quá trính giải nén ảnh là quá trính xấp xỉ để khôi phục ảnh gốc (thƣờng thực

hiện ở phìa thu).
Một hệ thống nén video tiêu biểu (hay bộ mã hóa nguồn) bao gồm: bộ chuyển đổi, bộ
lƣợng tử hóa, bộ mă hóa (Hnh 1.1):

Hình 1.1: Sơ đồ khối hệ thống nén ảnh tiêu biểu

+ Bộ chuyển đổi: thƣờng dùng phép biến đổi Cosin rời rạc để tập trung năng
lƣợng tìn hiệu vào một số lƣợng nhỏ các hệ số khai triển để thực hiện phép nén hiệu
quả hơn là dùng tìn hiệu nguyên thủy.


+ Bộ lƣợng tử hóa: tạo ra một lƣợng ký hiệu giới hạn cho ảnh nén với hai kỹ
thuật, gồm lƣợng tử vô hƣớng (thực hiện lƣợng tử hóa cho từng phần dữ liệu) và
lƣợng tử véc tơ (thực hiện lƣợng tử hóa một lần một khối dữ liệu). Quá trính này
không thuận nghịch.
+ Bộ mã hóa: gán một từ mã, một dòng bit nhị phân cho mỗi ký hiệu.
Các hệ thống nén đƣợc phân biệt dựa trên sự kết hợp khác nhau giữa 3 bộ xử lý trên
và đƣợc phân loại nhƣ sau:
Hệ thống nén không mất thông tin (lossless data reduction): thực hiện tối thiểu tốc độ
bit mà không làm méo ảnh, hệ thống còn gọi là nén toàn bit hay có tình chất thuận nghịch.
Hệ thống nén có mất thông tin (loss data reduction): đạt đƣợc độ trung thực tốt nhất
đối với tốc độ bit cho trƣớc, hệ thống phù hợp áp dụng cho tìn hiệu âm thanh và hính ảnh ví
có hệ số nén cao.
Trong sơ đồ hính 1.1, tầng chuyển đổi và tầng mã hóa là nơi tìn hiệu xử lý không bị
tổn thất, tầng lƣợng tử là có tổn thất. Ngoài ra, dựa trên quan điểm về tổn thất chúng ta có thể
phân biệt hai loại mã hóa nhƣ sau: mã hóa entropy (mã hóa không tổn thất) và mã hóa nguồn
(mã hóa có tổn thất).

- Nén không mất thông tin (kỹ thuật mã hóa entropy):
Kỹ thuật này chỉ quan tâm đến độ đo tin trong dữ liệu mà không quan tâm đến ngữ

nghĩa của tin. Sau đây là một số kỹ thuật mã hóa entropy hay dùng trong hệ thống xử lý
video:

+ Mã hóa chiều dài dải liên tục (RLC - Run Length Coding): các chuỗi điểm
ảnh có cùng độ chói (mức màu) sẽ đƣợc mã hóa bằng cặp thông tin (độ chói, chiều dài
chuỗi).
+ Mã hóa bằng các loại bỏ trùng lặp: các chuỗi đặc biệt đƣợc thay thế bằng cờ
và số đếm lặp.
+ Mã hóa dùng mẫu thay thế: đây là dạng mã hóa thống kê mà nó thay thế các
mẫu hay lặp lại bằng một mã.
+ Mã hóa với độ dài của từ mã thay đổi (VLC- Variable-Length Coding):
Phƣơng pháp này còn đƣợc gọi là mã hóa Huffman. Nguyên lý của nó dựa trên xác
suất xuất hiện của các giá trị biên độ trùng hợp trong một bức ảnh và việc gán một từ
mã ngắn cho các giá trị có tần suất xuất hiện cao nhất và từ mã dài hơn cho các giá trị
còn lại. Khi thực hiện giải nén, các thiết lập mã trùng hợp sẽ đƣợc sử dụng để tạo lại


giá trị tìn hiệu ban đầu. Mã hóa và giải mã Huffman có thể thực hiện một cách dễ
dàng bằng cách sử dụng các bảng tím kiếm. Nhƣ vậy, mã Huffman dựa trên nguyên
tắc “ký tự có tần số xuất hiện càng cao thí số bit mã hóa càng ngắn”.
- Nén có mất thông tin:
Các kỹ thuật này dựa trên ngữ nghĩa của ảnh nên còn gọi là kỹ thuật mã hóa hƣớng
ngữ nghĩa. Có 3 loại cơ bản là mã hóa chuyển đổi, mã hóa sai phân và lƣợng tử hóa véc tơ.

+ Mã hóa chuyển đổi: dùng phép biến đổi Fourier hay Cosin để chuyển từ
miền thời gian hay miền không gian sang miền tần số. Ở đây, chúng ta quan tâm đến
phép chuyển đổi Cosin rời rạc (DCT - Discrete Cosine Transform). Đặc điểm của
phép biến đổi này là tìn hiệu ảnh trong miền không gian chuyển sang miền tần số thí
các thành phần DC và các thành phần AC mang hầu hết các thông tin chứa trong ảnh
gốc. Trong đó, DC là thành phần quan trọng nhất mang độ chói trung bính của ảnh,

các thành phần AC chứa các thông tin về chi tiết của ảnh. Sau đó, khi qua tầng lƣợng
tử hóa, các hệ số ìt quan trọng sẽ bị loại bỏ bớt và chỉ giữ lại một số hệ số hệ số đầu
tiên gọi là hệ số DCT.
+ Mã hóa sai phân: cũng đƣợc gọi là mã hóa ƣớc đoán do chỉ mã hóa sự khác
biệt giữa giá trị mẫu thực và giá trị ƣớc đoán, mã hóa sai phân thƣờng dùng cho video
hính ảnh động. Lớp kỹ thuật này bao gồm: điều mã xung sai phân, điều chế delta, điều
mã xung thích nghi.
+ Lƣợng tử hóa véc tơ: mã hóa từng khối hai chiều kìch thƣớc cố định (gọi là
véc tơ) và tra bảng tím mã phù hợp nhất. Kỹ thuật chỉ thìch hợp cho dữ liệu có
cấu trúc biết trƣớc.

1.1.2. Giới thiệu chung về chuẩn MPEG [1]
Nén tìn hiệu video theo chuẩn MPEG (Moving Picture Experts Group) là phƣơng
pháp nén ảnh động không những làm giảm dƣ thừa không gian (nhƣ JPEG) mà còn làm giảm
dƣ thừa thời gian giữa các khung ảnh. Đây là khác biệt so với JPEG là chuẩn nén ảnh tĩnh chỉ
làm giảm dƣ thừa không gian trong một khung ảnh.
Chuẩn MPEG định nghĩa một khái niệm mới là “nhóm các khung ảnh” (GOP) để giải
quyết dƣ thừa thời gian và cho phép truy xuất ngẫu nhiên khi mã hóa MPEG dùng để lƣu trữ.
Trong chuẩn MPEG, ngƣời ta quy định 3 loại khung ảnh phụ thuộc vào phƣơng pháp nén:
nén trong khung ảnh (khung I), nén ƣớc đoán (khung P) và nén nội suy hai chiều theo thời


gian (khung B). Khung I luôn luôn là khung ảnh đầu tiên trong nhóm GOP, tạo điểm truy
xuất ngẫu nhiên chuẩn.
Chuẩn nén MPEG bao gồm các tiêu chuẩn nén video có tốc độ luống bìt (tƣơng
đƣơng chất lƣợng ảnh video) khác nhau:

+ MPEG-1 (chuẩn ISO/IEC 11172): có từ tháng 11-1992. MPEG-1 dùng
cho nén động có kìch thƣớc 320x240 và tốc độ bit còn từ 1 Mbit/s đến 1,5 Mbit/s
dùng cho ghi hính trên băng từ và đĩa quang (CD), đồng thời truyền dẫn trong các

mạng (vì dụ nhƣ mạngmáy tình). Đối với mã hóa audio stereo, tốc độ khoảng 250
Kbps. MPEG-1 có các thành phần chình sau đây:
Phần 1: ISO/IEC 11172 – 1:

Hệ thống ghép kênh Video, Audio MPEG-1.

Phần 2: ISO/IEC 11172 – 2: Nén video MPEG-1.
Phần 3: ISO/IEC 11172 – 3: Nén audio MPEG-1.
Phần 4: ISO/IEC 11172 – 4: Conformance.
Phần 5: ISO/IEC 11172 – 5: Software.

+ MPEG-2: là dự án giai đoạn hai của ISO/IEC, đƣợc sử dụng cho các ứng dụng
cao hơn với tốc độ còn ≤ 10 Mbit/s cho viễn thông, truyền hính thông thƣờng.

+ MPEG-3: tiêu chuẩn nén tìn hiệu số xuống còn ≤ 50 Mbps để truyền tìn hiệu
truyền hính có độ phân giải cao (HDTV), sau đó nhập chung vào MPEG-2 và thành tiêu
chuẩn quốc tế MPEG-2 vào tháng 11 năm 1994 (ISO/IEC 13818). Tiêu chuẩn MPEG-2 này
dùng cho truyền hính thông thƣờng và truyền hính có độ phân giải cao.

+ MPEG-4: đƣợc thiết kế để mã hóa Video/Audio với tốc độ thấp (khoảng 9÷14
Kbps) chủ yếu ứng dụng trong điện thoại video, multimedia. MPEG-4 hoàn thiện vào tháng
10 – 1998.

+ MPEG-7: chuẩn này đƣợc đề nghị vào tháng 10 – 1998 và thành chuẩn quốc tế
vào tháng 9 – 2001. Mô tả này sẽ kết hợp với chình nội dung của nó cho phép khả năng tím
kiếm nhanh và hiệu quả theo yêu cầu ngƣời dùng. MPEG-7 đặc trƣng cho một tập tiêu chuẩn
biểu diễn nhiều loại thông tin multimedia khác nhau. Chình ví vậy, MPEG-7 còn đƣợc gọi là
“Giao thức mô tả nội dung đa phƣơng tiện”.
Tiêu chuẩn MPEG là sự kết hợp giữa nén trong ảnh và nén liên ảnh. Tức là phƣơng
pháp nén có tổn hao dựa trên sự biến đổi DCT và bù chuyển động. MPEG dùng biểu diễn

màu bằng YCrCb (Hình 1.2).


Hình 1.2: Hệ thống các chuẩn MPEG

1.1.3. Các khái niệm cơ bản trong nén video theo chuẩn MPEG [1]
1.1.3.1. Các cấu trúc ảnh
MPEG định nghĩa các loại ảnh khác nhau cho phép sự linh hoạt để cân nhắc giữa hiệu
quả mã hóa và truy cập ngẫu nhiên. Các loại ảnh đó nhƣ sau:

- Ảnh loại I (Intra-picture): là ảnh đƣợc mã hóa riêng, tƣơng tự nhƣ việc mã
hóa ảnh tĩnh trong JPEG. Ảnh I chứa đựng dữ liệu để tái tạo lại toàn bộ hính ảnh ví
chúng đƣợc tạo thành bằng thông tin của chỉ một ảnh và để dự báo cho ảnh B,P. Ảnh I
cho phép truy cập ngẫu nhiên, tuy nhiên cho tỷ lệ nén thấp nhất.
- Ảnh loại P (Predicted-picture): là ảnh đƣợc mã hóa có bù chuyển động từ ảnh
I hoặc ảnh P phìa trƣớc. Ảnh P cung cấp cho hệ số nén cao hơn ảnh I và có thể sử
dụng làm một ảnh so sánh cho việc bù chuyển động cho các ảnh P và B khác.
- Ảnh loại B (Bi-directional predicted picture): là ảnh đƣợc mã hóa sử dụng bù
chuyển động từ các ảnh I hoặc P ở phìa trƣớc và ở phìa sau. Ảnh B cho tỷ lệ nén cao nhất.
- Ảnh loại D (Dc-coded picture): là ảnh đƣợc sử dụng trong MPEG-1 và
MPEG-4 nhƣng không đƣợc sử dụng trong MPEG-2. Nó giống nhƣ ảnh I, tuy nhiên,
chỉ có thành phần một chiều ở đầu ra DCT đƣợc thể hiện. Nó cho phép dò tím nhanh
nhƣng chất lƣợng ảnh thấp.

1.1.3.2 Nhóm ảnh (GOP)
Đối với chuẩn MPEG, chất lƣợng ảnh không những phụ thuộc vào tỷ lệ nén trong
từng khuôn hính mà còn phụ thuộc vào độ dài của nhóm ảnh. Nhóm ảnh (GOP-Group of
picture) là khái niệm cơ bản của MPEG. Nhóm ảnh là đơn vị mang thông tin độc lập của
MPEG.
MPEG sử dụng ba loại ảnh I, B, P. Trong đó, ảnh P, B không phải là một ảnh hoàn

chỉnh mà chỉ chứa sự khác biệt giữa ảnh đó và ảnh xuất hiện trƣớc nó (đối với ảnh P) hay sự
khác biệt đối với cả khuôn hính xuất hiện trƣớc và sau nó (đối với ảnh B). Để có một khuôn
hính hoàn chỉnh, ảnh P và B cần có dữ liệu từ các ảnh lân cận. Chình ví vậy, đối với MPEG


một khái niệm mới là GOP (nhóm ảnh) đƣợc sử dụng. Mỗi GOP bắt buộc phải bắt đầu bằng
một ảnh hoàn chỉnh I và tiếp sau nó là một loạt các ảnh P và B. Nhóm ảnh có thể mở hoặc
đóng.
Nhóm ảnh mở luôn bắt đầu từ một ảnh I và kết thúc ở một ảnh trƣớc ảnh I tiếp theo,
tức là ảnh cuối cùng của GOP dùng ảnh đầu tiên của GOP tiếp theo làm ảnh chuẩn (Hính
1.3).

Hình 1.3: Cấu trúc GOP mở
Trong hính 1.3, ảnh P (ảnh 4) đƣợc dự báo trƣớc trên cơ sở ảnh I (ảnh 1). Ảnh B đƣợc
dự đoán từ hai hƣớng, ảnh B (ảnh 2) và ảnh B ( ảnh 3) đƣợc dự đoán từ
hai ảnh I (ảnh1) và ảnh P (ảnh 4). Ảnh B (ảnh 5,6) đƣợc dự đoán từ ảnh P (ảnh 4) và ảnh I
tiếp theo (ảnh 6). Một điều chú ý là thứ tự truyền ảnh và hiện ảnh trên màn hính là không
giống nhau.
Đối với cấu trúc khép kìn (đóng), việc dự đoán ảnh không sử dụng thông tin của GOP
khác. Trong trƣờng hợp này, theo quy định, ảnh cuối cùng của một GOP bao giờ cũng là ảnh
P (Hình 1.4).

Hình 1.4: Cấu trúc GOP đóng


Nhóm ảnh đƣợc xác định bởi hai thông số m và n. Thông số m xác định số khung
hính P và khung hính B xuất hiện giữa hai khung hính I gần nhau nhất. Số n xác định số
khung hính B giữa hai khung hính P. Tỷ lệ nén video của MPEG phụ thuộc rất nhiều vào độ
dài của GOP.


1.1.3.3 Cấu trúc dòng bit MPEG
Để tạo khả năng chống lỗi khi truyền tìn hiệu qua kênh có nhiễu, bộ ƣớc đoán phải
đƣợc xác lập lại (reset) thƣờng xuyên và mỗi ảnh nén trong khung hay nén ƣớc đoán đƣợc
phân đoạn thành nhiều lát nhỏ (slice) cho việc tái đồng bộ tại bộ giải mã phìa thu. Cấu trúc
dòng MPEG gồm 6 lớp: lớp dãy ảnh (sequence), lớp nhóm ảnh (GOP), lớp ảnh (picture), lớp
cắt lát dòng bit (slice), lớp macroblock, lớp khối (block). Mỗi lớp này hỗ trợ một chức năng
nhất định: một là chức năng xử lý tìn hiệu (DCT, bù chuyển động) hai là chức năng logic (tái
đồng bộ, điểm truy xuất ngẫu nhiên). Quá trính tạo ra dòng bit MPEG là ghép kênh: kết hợp
các dòng dữ liệu vào, dòng dữ liệu ra, điều chỉnh đồng bộ và quản lý bộ đệm. Cú pháp dòng
MPEG bao gồm: lớp dòng bit (stream), lớp gói (pack) và lớp gói tin (packet) nhƣ trong
Hình1.5:

- Khối (Block): Khối 8x8 các điểm ảnh tìn hiệu chói và tìn hiệu màu dùng cho
phƣơng pháp nén DCT.
- Tổ hợp cấu trúc khối (macroblock): một cấu trúc khối là một nhóm các khối
tƣơng ứng với lƣợng thông tin chứa đựng trong kìch thƣớc 16x16 điểm trên bức ảnh.
Cấu trúc khối này cũng xác định lƣợng thông tin chứa trong đó sẽ thay đổi tùy theo
cấu trúc mẫu đƣợc sử dụng. Thông tin đầu tiên trong cấu trúc khối mang dạng của nó
(là cấu trúc khối Y hay Cr,Cb) và các véc tơ bù chuyển động tƣơng ứng.
- Mảng (Slice): mảng bao gồm một vài cấu trúc khối kề nhau. Kìch thƣớc lớn
nhất của mảng có thể bao gồm toàn bộ bức ảnh và kìch thƣớc nhỏ nhất của mảng là
một cấu trúc khối. Thông tin đầu của mảng chứa đựng vị trì của mảng trong toàn bộ
ảnh và hệ số cân bằng lƣợng tử.
- Ảnh (Picture): lớp ảnh cho phép bộ giải mã xác định loại của ảnh đƣợc mã
hóa làảnh P, I hay ảnh B. Thông tin đầu dùng để chỉ thứ tự truyền khung để bộ giải mã
có thể sắp xếp các ảnh lại theo một thứ tự đúng. Trong thông tin đầu của ảnh còn chứa
các thông tin về đồng bộ, độ phân giải và phạm vi của véc tơ chuyển động.
- Nhóm ảnh (GOP): nhóm ảnh là tổ hợp của nhiều các khung I, P và B. Cấu
trúc nhóm ảnh đƣợc xác định bằng hai tham số m và n. Mỗi một nhóm ảnh bắt đầu



bằng một khung I cho phép xác định điểm bắt đầu để tím kiếm và biên tập. Thông tin
đầu gồm 25 bit chứa mã định thời và điều khiển.
- Đoạn (chương trình) video: đoạn video bao gồm thông tin đầu, một số nhóm
ảnh và thông tin kết thúc đoạn. Thông tin đầu của đoạn video chứa đựng kìch thƣớc
mỗi chiều của ảnh, kìch thƣớc của điểm ảnh, tốc độ bit của dòng video số, tần số ảnh
và bộ đệm tối thiểu cần có. Đoạn video và thông tin đầu tạo thành một dòng bit đƣợc
mã hóa gọi là dòng cơ bản (Elementary Stream) (Hính 1.5).


Hình 1.5: Kiến trúc dòng dữ liệu MPEG

1.1.4. Phương pháp nén video theo chuẩn MPEG
1.1.4.1. Mô hính tổng quát bộ mã hóa video theo chuẩn MPEG [1]
Quá trính nén theo chuẩn MPEG là sự kết hợp giữa nén trong ảnh và nén liên ảnh. Tìn
hiệu đầu vào có dạng 4:2:2 hoặc 4:2:0 đƣợc nén liên ảnh nhằm tạo ra ảnh khác biệt ở đầu ra
bộ cộng. Ảnh khác biệt này sau đó đƣợc nén trong ảnh qua các bƣớc: biến đổi DCT, lƣợng tử
hóa, mã hóa. Cuối cùng, ảnh này đƣợc trộn cùng với véc tơ chuyển động đƣa đến bộ khuyếch
đại đệm sẽ thu đƣợc ảnh đã nén. Ta xét vì dụ bộ nén theo phƣơng pháp trên, dùng ảnh I và P
trong cấu trúc GOP (Hính 1.4).
Ảnh thứ nhất trong nhóm phải đƣợc mã hóa nhƣ ảnh loại I. Trong trƣờng hợp này, sau
khi lấy mẫu lần đầu, tìn hiệu video đƣợc truyền đến khối biến đổi DCT cho các MacroBlock
riêng, sau đó bộ lƣợng tử và mã hóa entropy. Tìn hiệu ra từ bộ lƣợng tử hóa đƣợc đƣa đến bộ
lƣợng tử hóa ngƣợc và biến đổi DCT ngƣợc, sau đó đƣợc lƣu vào bộ nhớ ảnh.
Trong trƣờng hợp mã hóa ảnh loại P, mạch nén chuyển động làm việc. Trên cơ sở so
sánh ảnh đang xét và ảnh trong bộ nhớ sẽ xác định đƣợc các véc tơ chuyển động, sau đó dự
báo ảnh. Sự chênh lệch giữa ảnh đang xét và dự báo ảnh của nó đƣợc biến đổi DCT, lƣợng tử


hóa và mã hóa entropy. Cũng nhƣ trong trƣờng hợp các ảnh loại I, tìn hiệu ra từ bộ lƣợng tử

hóa đƣợc giải lƣợng tử hóa và biến đổi DCT ngƣợc rồi cộng với ảnh dự báo đang xét và lƣu
vào bộ nhớ (Hính 1.6).

Hình 1.6: Bộ mã hóa MPEG tiêu biểu

1.1.4.2. Lấy mẫu thông tin về màu [1]
Các đại diện của các màu sắc trong hính ảnh đƣợc chuyển đổi từ RGB sang YCbCr,
bao gồm ba thành phần luma (Y), đại diện cho độ chói (sáng) và hai thành phần sắc độ (Cb
và Cr) đại diện cho màu. Do đặc điểm về nhạy cảm trong mắt ngƣời đối với mật độ của màu
sắc và độ sáng, con ngƣời có thể cảm nhận tốt hơn đáng kể đối với độ sáng của một hính ảnh
(thành phần Y) so với màu sắc và độ bão hòa màu sắc của một hính ảnh (các thành phần
CbCr).
Thông tin thị giác về một vật thể đƣợc truyền đi bao gồm tin tức về độ chói, màu sắc
và vị trì của vật đó trong không gian. Khi vật thể đó chuyển động hay khi nguồn ánh sáng
chiếu lên vật thể thay đổi, các tin tức trên đều thay đổi. Nhƣ vậy, mô hính toán học của tìn
hiệu hính ảnh là các hàm phân bố độ chói L, sắc màu λ và độ bão hoà màu p trong không
gian và thời gian:

{

(
(
(

)
) }
)

(1.1)


x,y,z – tọa độ trong không gian 3 chiều với t - thời gian
Những phƣơng trính trong (1.1) xác định độ chói (L) và màu sắc ( λ, p ) cho từng
điểm di chuyển trong không gian và thời gian. Hệ thống truyền hính hiện nay là hệ thống
truyền hính phẳng, do đó khi truyền đi các ảnh đen trắng, phân bố độ chói sẽ là hàm ba chiều:


L = fL(x,y,t). Điều này cho ta thấy, ngoài giá trị độ chói tức thời L cần phải xác định chình
xác vị trì của điểm sáng trong không gian (hai chiều) màn hính.
So với tìn hiệu một chiều, quá trính số hóa tìn hiệu hính ảnh trong không gian hai
chiều có thể đƣợc thực hiện với nhiều cấu trúc lấy mẫu khác nhau và các bƣớc lƣợng tử khác
nhau nhằm giảm dung lƣợng tìn hiệu số nhận đƣợc. Tuy nhiên, trên thực tế cấu trúc lấy mẫu
trong đa số trƣờng hợp có dạng trực giao (hính chữ nhật) với giá trị bƣớc lƣợng tử không thay
đổi, ví khi đó quá trính số hóa sẽ đơn giản nhất. Khi sử dụng cấu trúc lấy mẫu trực giao, ảnh
số nhận đƣợc dƣới dạng ma trận các điểm ảnh phân bố theo dòng và cột.
Quá trính lấy mẫu tìn hiệu video phải thỏa mãn định lý lấy mẫu Nyquist.
Trên thực tế, tần số lấy mẫu thƣờng đƣợc lựa chọn cao hơn để tăng khoảng cách giữa
dải phổ chình và phổ phụ của tìn hiệu video rời rạc, khi đó thành phần phổ chình có thể đƣợc
tách ra (trong quá trính khôi phục ảnh gốc) bằng các mạch lọc thông thấp đơn giản. Ngoài ra,
tìn hiệu video tổng hợp (bao gồm thành phần màu) đƣợc lấy mẫu với tần số là bội số của tần
số sóng mang phụ fs (sóng mang màu). Với hệ PAL, tần số lấy mẫu sẽ là 3 fs (13,3 MHz)
hoặc 4 fs (17,7 MHz).
Trong hệ thống số hóa tìn hiệu video theo thành phần, ba tìn hiệu R, G, B hoặc thành
phần chói Y và hai tìn hiệu hiệu màu R-Y, B-Y sẽ đƣợc lấy mẫu với tần số đáp ứng định lý
Nyquist và là bội số của tần số dòng theo cả 2 tiêu chuẩn 525 và 625 dòng/ ảnh. Tiêu chuẩn
CCIR-601 cho phép sử dụng tần số lấy mẫu là 13,5 MHz. Số bìt để mã hóa tìn hiệu video là 8
hoặc 10 bìt.
Các tiêu chuẩn lấy mẫu video thành phần: có nhiều tiêu chuẩn lấy mẫu theo thành
phần, điểm khác nhau chủ yếu ở tỷ lệ giữa tần số lấy mẫu và phƣơng pháp lấy mẫu tìn hiệu
chói và tìn hiệu màu (hoặc hiệu màu): đó là các tiêu chuẩn 4:4:4, 4:2:2, 4:2:0, 4:1:1.
- Tiêu chuẩn 4:4:4: Tìn hiệu chói và màu đƣợc lấy mẫu tại tất cả các điểm lấy mẫu

trên dòng tìch cực của tìn hiệu video. Cấu trúc lấy mẫu trực giao (Hính 1.7)

Hình 1.7: Cấu trúc lấy mẫu theo chuẩn 4:4:4


- Tiêu chuẩn 4:2:2: Tìn hiệu chói đƣợc lấy mẫu tại tất cả các điểm lấy mẫu trên
dòng tìch cực của tìn hiệu video. Tìn hiệu màu trên mỗi dòng đƣợc lấy mẫu với tần số
bằng nửa tần số lấy mẫu tìn hiệu chói (Hính 1.8)

Hình 1.8: Cấu trúc lấy mẫu theochuẩn 4:2:2

- Tiêu chuẩn 4:2:0: Tìn hiệu chói đƣợc lấy mẫu tại tất cả các điểm lấy mẫu trên
dòng tìch cực của tìn hiệu video. Cách một điểm lấy mẫu một tìn hiệu màu. Tại dòng
chẵn chỉ lấy mẫu tìn hiệu màu CR, tại dòng chẵn lấy mẫu tìn hiệu CB. Nhƣ vậy, nếu
tần số lấy mẫu tìn hiệu chói là fD, thí tần số lấy mẫu tìn hiệu màu sẽ là fD/2 (Hính
1.9).

Hình 1.9: Cấu trúc lấy mẫu theo chuẩn 4:2:0
- Tiêu chuẩn 4:1:1: Tìn hiệu chói đƣợc lấy mẫu tại tất cả các điểm lấy mẫu trên dòng
tìch cực của tìn hiệu video. Tìn hiệu màu trên mỗi dòng đƣợc lấy mẫu với tần số bằng một