Nghiên cứu thuật toán ước lượng Vector chuyển động trong mã hóa video

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (3.72 MB, 24 trang )

Trang 1<div class="page_container" data-page="1">

HỌC VIEN CƠNG NGHỆ BƯU CHÍNH VIÊN THONG

Phạm Thị Mai Loan

NGHIÊN CỨU THUẬT TOÁN ƯỚC LƯỢNG VECTOR CHUYÊN ĐỘNG

TRONG MÃ HÓA VIDEO

Chuyên ngành: Hệ thống thông tinMã số: 60.48.01.04

TOM TAT LUẬN VĂN THẠC SĨ

HÀ NỘI - 2017

</div>Trang 2<div class="page_container" data-page="2">

Luận văn được hoàn thành tại:

HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIÊN THƠNG

Người hướng dẫn khoa học: TS. Vũ Hữu Tiến

Phản biện 1:

Luận văn sẽ được bảo vệ trước Hội đông châm luận văn thạc sĩ tại Học viện

Cơng nghệ Bưu chính Viễn thơng

Vào lúc:... gid... ngay ... thang ... .. NAM ...

Có thé tìm hiéu luận văn tại:

- Thư viện của Học viện Công nghệ Bưu chính Viễn thơng

</div>Trang 3<div class="page_container" data-page="3">

MO DAU

1. Tinh cấp thiết của đề tai

Ngày nay nhu cầu truyền dẫn tín hiệu video đang tăng một cách nhanh chóng. Vấn đề

được quan tâm nhiều nhất đối với tín hiệu video là u cầu về băng thơng. Vì lý do này, rất

nhiều các chuẩn nén video đã được phát triển. Nói chung, nén video là kỹ thuật dé truyền tín

hiệu video với mục đích duy trì chất lượng ban đầu với một số điều kiện ràng buộc: ràng

buộc về không gian lưu trữ, ràng buộc về độ trễ hoặc ràng buộc về hiệu năng tính tốn. Nó

tận dụng mức độ dư thừa dữ liệu giữa các khung hình liên tiếp để giảm yêu cầu về không

gian lưu trữ băng cách sử dụng các tài ngun tính tốn. Việc thiết kế các hệ thống nén dữ

liệu thông thường bao gồm sự thỏa hiệp giữa chất lượng, tốc độ, sử dụng tài ngun và sự

tiêu thụ cơng suất.

Vì vậy việc nghiên cứu và xây dựng mới các thuật toán ước lượng chuyên động rất cần thiết trong việc cải thiện chất lượng và thời gian xử lý của các chuẩn nén video. Do vậy, tôi đã chọn đề tài “Nghiên cứu thuật tốn ước lượng Vector chuyển động trong mã hóa Video” làm nội dung nghiên cứu cho luận văn này. Đây là một chủ đề cấp thiết cho việc ứng dụng truyền video trên các mạng viễn thông đa môi trường thé hệ mới.

2. Tổng quan về vấn đề nghiên cứu

Trên thực tế, đã có nhiều nghiên cứu về các thuật tốn tìm kiếm khác nhau được sử dụng dé dự đốn chun động giữa các khung hình.

Có hai cách tiếp cận cơ bản đối với ước lượng chuyên động: - Ước lượng chuyền động dựa trên pixel

- Ước lượng chuyén động dựa trên khối

Cách tiếp cận ước lượng chuyền động dựa trên pixel là tìm và xác định vector chuyên

động cho mỗi pixel trong ảnh. Phương pháp này còn được gọi là “phương pháp dòng

quang”. Phương pháp này làm việc dựa trên giả định về sự không thay đổi của độ sáng nghĩa là cường độ của một pixel sẽ khơng đổi khi nó dịch chuyển. Tuy nhiên số lượng vector biểu diễn chuyên động sẽ rất lớn vì mỗi pixel cần một vector tương ứng.

Một cách tiếp cận thực tế và nhanh hơn là ước lượng chuyển động dựa trên khối

BMME (Block Matching Motion Estimation). Trong phương pháp này, frame được chia

</div>Trang 4<div class="page_container" data-page="4">

thành các khối không chồng lấn nhau (có kích thước 16 x 16, 8 x 8, hoặc thậm chí 4 x 4

pixel trong các tiêu chuẩn gần đây) và với mỗi block sẽ xác định vector chuyên động trong

frame tham chiếu. Chi cần tính một vector chuyên động duy nhất cho toàn bộ khối, do đó ta

giả định là tồn bộ block chun động tịnh tiến. Điều giả định này là hợp lý ngoại trừ tại các

biên của đối tượng. Cho đến nay ước lượng chuyển động dựa trên khối được chấp nhận trong tất cả các chuẩn mã hóa video. Nó dễ thực hiện về phần cứng, có thể ước lượng và dự

đốn chuyên động thời gian thực.

Các thuật toán cơ bản gồm: thuật tốn tìm kiếm đầy đủ FSA (Full Search Algorithm), Thuật tốn tìm kiếm logarithm hai chiều TDL (Two - dimentional logarithmnic search), Thuật tốn tìm kiếm ba bước TSS (Three - step search algorithm), Thuật toán tim kiém chéo

CSA (Cross Search Algorithm), Thuật toán OTA (One-at-a-time Search Algorithm), Thuật

toán OTA cải tiễn gọi là NOTA (New One at a Time Algorithm), Thuật tốn tìm kiếm ba bước cải tiến MTSS (Modified Three-Step Search Algorithm), và các thuật toán cải tiến

- M6 phỏng và đánh giá các thuật toán ước lượng chuyên động dựa trên các tiêu chi bao gồm thời gian tìm kiếm và chất lượng hình ảnh.

4. Đối tượng và phạm vi nghiên cứu

4.1. Đối tượng nghiên cứu

Đôi tượng nghiên cứu chính của đê tài là các thuật tốn tìm kiêm các khơi hình ảnh

giơng nhau giữa khung hình trước và sau. Từ đó tìm ra vector chun động của các khôi

</div>Trang 5<div class="page_container" data-page="5">

e Thời gian tìm kiếm vector chuyên động.

e Chất lượng hình anh sau khi bù chuyển động (được đánh giá thông qua tham số

5. Phương pháp nghiên cứu

5.1. Phương pháp nghiên cứu lý thuyết

Nghiên cứu, khảo sát và đánh giá các thuật toán đã và đang được áp dụng trong các

chuân nén video dựa trên các tiêu chí vê thời gian và chât lượng hình ảnh5.2. Phương pháp thực nghiệm

Mơ phỏng và đánh giá hiệu năng của các thuật tốn dựa trên cơng cụ mơ phỏng

6. Kêt câu của đề tài

Ngồi phân mở đâu, kêt luận và danh mục tài liệu tham khảo, luận văn được kêt câuthành 3 chương như sau:

Chương 1: Tổng quan về mã hóa Video

Chương 2: Nghiên cứu các thuật tốn ước lượng Vector chuyển động trong mã hóa

Chương 3: Mơ phỏng và đánh giá các thuật tốn tạo Vector chuyên động trong mã

hóa Video

</div>Trang 6<div class="page_container" data-page="6">

Chuong 1 - TONG QUAN VE MA HOA VIDEO

Tổng quan về mã hóa video

Vai trị của nén video trong truyền thơng Nguyên tắc chính của nén video

Nguyên lý của việc nén video dựa trên các kỹ thuật giảm các dư thừa thông tin sau:

Y Dư thừa thông tin trong miền không gian (Spatial redundancy): Dư thừa thông tin

trong miền không gian xuất hiện giữa các pixel trong cùng một khung hình (ví dụ

sự tương đồng giữa các pixel). Thơng tin dư thừa được loại bỏ bằng kỹ thuật mã

hóa biến đổi (transform coding).

* Dư thừa thông tin trong miền thời gian (Temporal redundancy): Loại thông tin dư

thừa này xuất hiện khi giữa các khung ảnh liên tiếp có những thơng tin tương

đồng. Để giảm dư thừa này người ta dùng kỹ thuật mã hóa sự khác biệt giữa các

* Dư thừa thông tin trong dữ liệu ảnh sau khi nén: Dé loại bỏ dư thừa này người ta dùng mã entropy, cụ thê là mã có độ dài thay đổi (Variable Length Coding).

Kỹ thuật giảm dư thừa thông tin theo không gian

Mã hóa dự báo

Mã hóa biến đổi

Lượng tử hóa các hệ số DCT

Kỹ thuật giảm dư thừa thông tin trong miền thời gian

Uớc lượng chuyển động

Bù chuyển động

Mã có chiều dài thay đổi

Sơ đồ tổng qt của mã hóa video

Hình 1.6 mô tả so đồ tổng quát của bộ mã hóa video được sử dụng trong các chuẩn

nén như H.261, H.264, MPEG-1, MPEG-2 và H.264/MPEG-4 part 10.

</div>Trang 7<div class="page_container" data-page="7">

Ảnh đầu Intra mode | | Bit

TT sẽ sd > DCT - BO lượng : VLC " Buffer — §"

__/ Inter mode tử

Về cơ bản, quá trình giải nén bao gồm các bước giống như quá trình nén nhưng thứ

tự ngược lại. Hình 1.7 mơ ta q trình giải nén tín hiệu video.

Hình 1.7. Sơ đồ giải nén tín hiệu video

1.8. Cac tiêu chuẩn cho mã hóa tín hiệu video

1.9. Một số định dạng file video

1.10. Kết luận

Chương này đã trình bày khái quát về nguyên lý nén video nói chung và giới thiệu về

một số chuẩn nén video thơng dụng. Chương tiếp theo sẽ trình bày về các thuật toán ước lượng chuyên động trong các kỹ thuật nén video.

</div>Trang 8<div class="page_container" data-page="8">

Chương 2 — NGHIÊN CỨU CÁC THUAT TOÁN UOC LƯỢNG VECTOR CHUYEN ĐỘNG TRONG MÃ HĨA VIDEO

2.1. Cac thuật tốn tìm kiếm trong ước lượng chuyển động

2.2. Nguyên lý của thuật toán đối sánh khối (Block matching)

Kỹ thuật đối sánh khối là phương pháp ước lượng chuyển động thực tế và thông dụng nhất trong mã hóa video. Hình 2.1 mơ tả cách làm việc của kỹ thuật ước lượng chuyển

động dựa trên đối sánh khối BMME (Block Matching Motion Estimation).

Reterence frame

Hình 2.1: Ước lượng chuyền động dựa trên đối sánh khối BMME

2.2.1. Độ méo khối

Dé frame được nén trông như bản gốc, block thay thế phải càng giống block mà nó thay thé càng tốt. Vì vậy, tiêu chí phù hợp hay hàm méo được sử dụng dé xác định sự giống

nhau giữa block hiện thời và block ứng cử viên.

Có một sơ tiêu chn đê đánh giá kêt quả của q trình đơi sánh. Các tiêu chuân

thông dụng cho BMME là:

- Sai số bình phương trung bình MSE (Mean Square Error).

- Tong tri tuyét đối sự sai khác SAD (Sum of Absolute Difference)

* Sai số bình phương trung bình MSE

</div>Trang 9<div class="page_container" data-page="9">

MSE của một block gồm các pixel được tính với độ dịch chuyển (w, Wy) trong

frame tham chiếu có cơng thức như sau:

1 x+N-1Y+N-1

NxN » [RGA — Fea(it Wes + wy)|Ï (2.2)

i j=y

MSE (Wy, Wy) =

¢ Tong trị tuyệt đối sự sai khác SAD

Giống như tiêu chuan MSE, SAD cũng coi các giá trị sai khác là đương, nhưng thay

vì lay tong của bình phương, SAD lấy tổng trị tuyệt đối. SAD tại vị trí dịch chuyên (w,, Wy)

duoc xac dinh nhu sau:

2.3. Thuật tốn tìm kiếm đầy đủ FSA

2.4. Thuật tốn đối sánh khối nhanh FBMA

2.4.1. Thuật tốn tìm kiếm logarithm hai chiều

Thuật tốn được mơ tả theo các bước sau:

</div>Trang 10<div class="page_container" data-page="10">

+ Bước 2:

M'(n) M(n)

+ Bước 3:

Tìm (w,,w,)eMt(n) sao cho D(w,+q,w,+l)dat giá trị nhỏ nhất. Nếu

w,=0,w, =0 thì tới bước 5; ngược lại sang bước 4.

Tìm (w,, wy) € N(1) sao cho D(w, + q,w„ + 1) đạt giá trị nhỏ nhất.

qCq+wy,Ì — 1+ wy và (q, Ù) là điểm cho độ méo khối (sự sai khác giữa hai khối)

</div>Trang 11<div class="page_container" data-page="11">

Tìm (w„,wy) € N(1) (1) sao cho D(w, + q,wy + 1) đạt giá trị nhỏ nhất q — q + w,,l — Ì + wy và (q, L) là điểm cho độ méo khối (sự sai khác giữa hai khối) nhỏ nhất.

Hinh 2.3: Thuat toan TSS

2.4.3. Thuật toán tim kiếm chéo CSA

</div>Trang 12<div class="page_container" data-page="12">

Thuật tốn được mơ tả như sau:

Điểm tham chiếu cho block là pixel (i,j) tại góc trên bên tay trái. Block ở frame trước

tương ứng với block ở frame hiện tại được coi là block ở tọa độ (0,0).

Nếu D(w,,w,) < T thi coi như khối hiện thời khơng chuyền động và ngừng tìm kiếm.

Ngược lại sang bước 2.

Tìm (w,,w,) € M (n) sao cho D(wy + q,wy + 1) đạt giá trị nhỏ nhất.

qcq+wy,lcl+wy; M '(n) c M'(n) + (q + wy,1 + wy.

Nếu n=l sang bước 4. Ngược lain — [n/2], lặp lại bước 3.

+ Bước 4:

Nếu vi trí có độ méo nhỏ nhất nằm trong tập (q, Ù); (q — 1,l— 1); (q + 1,1 + 1) thì

sang bước 5, ngược lại sang bước 6.+ Bước 5:

M'(n) — P()

Tim (wy, wy) € M (n) sao cho D(w, + q,w, + 1)dat giá tri nhỏ nhất.

</div>Trang 13<div class="page_container" data-page="13">

Tìm (wy,wy) € M ‘(n) sao cho D(wy + q,wy + 1) dat giá trị nhỏ nhất.

qq+wy,L © Ï+ wy và (q,L là điểm cho độ méo khối (sự sai khác giữa hai khối)

Hình 2.4: Thuật tốn CSA

2.4.4. Thuật tốn tìm kiếm một điểm tại một thời điểm OTA

</div>Trang 14<div class="page_container" data-page="14">

M'(n) M(1); q=l=0

P'(n) - PA)

+ Bước 2:

Tìm (w,, Wy) € M'(n) sao cho D(w, + q, Wy + 1) đạt giá trị nhỏ nhất. Nếu (Wy, Wy) là điểm không năm ở tâm thi bước sang bước 3.

Ngược lại (Wy, Wy) là điểm nam ở tâm thi bước sang bước 4.

+ Bước 3:

qq+wy,lc©l+wy; M '(n) C M'(n) +(q +wy,Ì+wy). Và quay trở lại

bước 2.

+ Bước 4:

qcq+wy,lc©l+wy; P'(n) c P'(n) + (q + wxy,l + wy)

Tìm (wy, Wy) € P’(n) sao cho D(w, + q, Wy + 1) đạt giá trị nhỏ nhất. Nếu (Wy, Wy) là điểm khơng năm ở tâm thì bước sang bước 4.

Ngược lại (wy, Wy) là điểm năm ở tâm thi bước sang bước 5.

</div>Trang 15<div class="page_container" data-page="15">

2.5. Cac thuật toán cải tiễn

2.5.1. Thuật toán OTA mới

Các bước của NOTA được diễn giải như sau:

Bước 1: Đánh giá hàm mục tiêu cho tất cả 5 điểm theo chiều ngang.

Bước 2: Nếu điểm có độ méo tối thiểu nằm ở tâm, dừng tìm kiếm; MV sẽ chỉ đến

Bước 3: Nếu ngược lại, đánh giá hàm mục tiêu tại 4 điểm theo hướng khác với lúc trước (4 điểm này năm xung quanh theo chiều dọc của điểm có độ méo nhỏ nhất ở bước 1).

Bước 4: Tìm hai vị trí ở phía khác của điểm chiến thắng ở bước 3 theo chiều ngang; khi xét đến điểm có độ méo nhỏ nhất theo chiều ngang thì tim hai vi trí

theo chiều dọc.

Bước 5: Điểm có độ méo nhỏ nhất được coi là vị trí phù hợp nhất.

2.5.2. Thuật tốn tìm kiếm ba bước cải tiến MTSS

Thuật toán được diễn giải theo các bước sau.

+ Bước 1: Bước đầu tiên của MTSS là thực hiện đánh giá với kích thước bước bằng 1gém: các điểm tìm kiếm trên lưới 3 x 3 lớn hơn giống như trong TSS, 8 điểm tìm kiếm bổ sung trên lưới 3 x 3 nhỏ hơn tại tâm. Theo cách này, có tổng cộng 8 + 9 = 17 điểm tìm kiếm cần

được đánh giá trong bước 1. Nếu điểm có BDM tối thiểu là tâm của cửa số tìm kiếm thì quá

trình tìm kiếm sẽ kết thúc. Ngược lại thuật toán tiếp tục sang bước 2.

+ Bước 2: Nếu điểm có BDM nhỏ nhất là một trong 8 điểm quanh tâm trên lưới 3 x 3 ở

bước | thì đến bước 3; ngược lại sang bước 4.

</div>Trang 16<div class="page_container" data-page="16">

+ Bước 3: Di chuyên lưới 3 x 3 nhỏ hơn sao cho tâm cửa số là điểm chiến thắng ở bước 1. Đánh giá thêm 5 hoặc 3 điểm tùy theo vị trí của điểm chiến thắng lúc trước. Sau đó q trình tìm kiếm sẽ dừng và điểm có BDM nhỏ nhất là điểm chiến thắng.

+ Bước 4: Giảm kích thước bước của lưới 3 x 3 lớn hơn xuống một nửa và dịch chuyển tâm

về vị trí có BDM nhỏ nhất ở bước 1, và vì vậy tiếp tục tiến trình giống của thuật tốn TSS

cho đến khi kích thước bước bằng 1.

> Bat đầu tìm kiếm ở vi trí trung tâm.

> Thiết lập kích thước bước d=2 (khơng liên quan đến tham số tìm kiếm p)

> Tìm kiếm 9 vị trí quanh tâm cửa số tìm kiếm. Tính độ méo và tìm ra điểm có độ méo nhỏ nhất. Nếu điểm này là tâm của khu vực tìm kiếm thì tiếp tục ở bước 4. Ngược lại

sang bước 2.

Bước 2:

Di chuyền tâm tới điểm có độ méo nhỏ nhất. Kích thước bước vẫn duy trì là 2. Tuy

nhiên mẫu tìm kiếm tùy thuộc vào vi trí của độ méo nhỏ nhất ở bước 1.

a) Nếu điểm có độ méo tối thiểu ở bước trước nằm ở góc của khu vực tìm kiếm trước

thì chọn 5 điểm đề kiểm tra (như vẽ trong hình 2.10).

</div>Trang 17<div class="page_container" data-page="17">

b) Nêu điêm có độ méo tôi thiêu ở bước trước năm ở giữa của trục ngang hay trục

doc của cửa số tìm kiếm thì thực hiện tìm kiếm thêm 3 điểm (như trong hình 2.11).

Xác định điêm có độ méo tơi thiêu. Nêu diém này nam ở tâm, chuyên sang bước 4.

Ngược lại sang bước 3.

Bước 3: Chiến lược tìm kiêm vẫn như cũ, tuy nhiên cuối cùng sẽ sang bước 4.

Bước 4: Kích thước bước được giảm xuống 1 và tiếp tục kim tra 9 im quanh vi tri tõm.

âđ @ @a @ eđ @ âđ

âđ @ @sB AO e@ BO e@

eđ e@ e® @ @

Cau hinh ban dau Nếu điểm A cóđộ Néu điểm B có độ

méo min, thì chọn méo min, thì chọn

2.10a 2.10b

Hình 2.8: Minh họa cách lựa chọn các điểm tìm kiếm trong các trường hợp khác nhau của

thuật tốn FSS

® Tập điểm ban đầu

ry a a HM Điển cho giai đoạn thứ 2

2. Điểm cho giai đoạn thứ 3

</div>Trang 18<div class="page_container" data-page="18">

e Bat đầu tai vị trí tâm.

e_ Thiết lập kích thước bước d= 2

e Tìm kiếm 8 vi trí pixel (x,y) sao cho |x| + |y| = d quanh vi trí tâm (0,0) sử dụng mẫu điểm tìm kiếm dạng hình thoi.

e Chọn ra điểm có độ méo tối thiểu.

e Nêu điêm có độ méo tơi thiêu nam ở tâm của cửa sơ tìm kiêm, chuyên sang bước

SDSP. Ngược lại thiết lập tâm mới sang điểm này.

e Lap lại LDSP.

e Thiết lập gốc tim kiếm mới.

e Lặp lại thủ tục tìm kiếm dé tìm ra vị trí có độ méo nhỏ nhất. e Vị trí có độ méo nhỏ nhất chính là vector chuyền động.

Thuật tốn tìm ra độ méo càng chính xác khi mẫu tìm kiếm khơng q lớn hoặc khơng q nhỏ. Thuật tốn này có giá trị PSNR rất gần với tìm kiếm vét cạn trong khi chỉ

</div>Trang 19<div class="page_container" data-page="19">

2.5.5. Kết luận

Chương này đã trình bày về các thuật tốn ước lượng chuyển động dùng trong kỹ

thuật nén video. Chương 3 sẽ thực hiện đánh giá một số thuật toán được giới thiệu trong

chương này dựa trên các mô phỏng bang phần mềm Matlab.

</div>Trang 20<div class="page_container" data-page="20">

Chương 3 - MÔ PHỎNG VÀ ĐÁNH GIÁ CÁC THUẬT TOÁN TẠO VECTOR

CHUYEN ĐỘNG TRONG MÃ HÓA VIDEO

3.1. Các chuỗi video dùng để đánh giá

Trong báo cáo này sử dụng 9 chuỗi video chuẩn QCIF (Quarter Common Intermediate File Format) với nội dung chuyên động khác nhau để so sánh hiệu năng của

các thuật toán khác nhau. Các chuỗi video này được phân loại thành 3 loại: Loại A, loại B,

loại C với độ phức tạp chuyền động tăng dan.

Silent Claire Grandma

Hình 3.1: Cac frame đầu tiên của chuỗi Silent, Claire, Grandma

News Suzie Miss America

Hình 3.2: Cac frame dau tiên của chuỗi News, Suzie, Miss America

Hình 3.3: Các frame đầu tiên của chuỗi Foreman, Carphone, Salesman

3.2. Các bước mô phỏng

</div>Trang 21<div class="page_container" data-page="21">

Dé đánh giá hiệu quả của các thuật toán ước lượng chuyền động, tham số PSNR và

độ phức tạp của thuật toán được sử dụng để so sánh giữa các thuật tốn.

Tham số PSNR được đo như sau:

Bước 1: Tìm vector chuyên động cho frame 2 trên mỗi chuỗi video băng các thuật toán ước lượng chuyên động.

Bước 2: Dựa trên các vector chuyên động va frame 1, frame 2 được tái tạo (bù chuyền động).

Bước 3: Giá trị PSNR được tính dựa trên frame 2 và frame 2 được tái tạo.

Độ phức tạp của các thuật tốn được tính bằng số điểm trung bình phải tìm kiếm cho một khối ảnh.

3.3. Phân tích kết quả mơ phỏng

+ Chuỗi video Slient:

Tên thuật toán PSNR Độ phức tạp

s* Chuỗi video Grandma:

Tén thuat toan PSNR Độ phức tap

</div>