TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
Viện Công nghệ Thông tin và Truyền thông

Báo cáo
Xử lý dữ liệu đa phương tiện
Nhóm 5: Tìm hiểu các phép biến đổi trong xử lý dữ liệu
đa phương tiện và ứng dụng
Giáo viên hướng dẫn: PGS.Nguyễn Thị Hoàng Lan
Sinh viên thực hiện:

Hoàng Đình Hiệp

20111584

Hoàng Anh Chiến

20111247

Nguyễn Văn Hiệp

20111590

Hà Nội, tháng 5 năm 2015


Mục lục

Lời nói đầu
Xử lý dữ liệu đa phương tiện cung cấp các kiến thức lý thuyết và cá kỹ
thuật xử lý dữ liệu đa phương tiện cần thiết trong các ứng dụng truyền thông đa
phương tiện trên mạng máy tính. Cũng như khái quát về các lại dữ liệu đa

phương tiện và xử lý dữ liệu trong truyền thông đa phương tiện; tín hiệu video,
số hoá video và nén; mã hoá dự đoán DPCM; lượng tử hoá vector; phương pháp
mã hoá các dải tần; nén ảnh dựa trên các phép biến đổi; các phương pháp nén
video; các phương pháp mã hoá audio; đồng bộ audio-video.
Để hiểu thêm lý thuyết, các kỹ thuật trong xử lý nén ảnh nhóm đã chọn
Đề tài 5: Tìm hiểu các phép biến đổi trong xử lý dữ liệu đa phương tiện và
ứng dụng. Trong đề tài này, nhóm đã tập trung vào các phép biến đổi là: KL,
PCA. Và ứng dụng của PCA trong trích chọn đặc trưng khuôn mặt.
Do hạn chế về thời gian, cũng như kiến thức và kinh nghiệm bài báo cáo không
tránh khỏi những thiếu sót. Rất mong được sự góp ý của cô và các bạn.
Nhóm xin chân thành cảm ơn!

2


Phân công công việc
-

Nguyễn Văn Hiệp:

Tìm hiểu chung các phép biến đổi đơn vị, các tính chất chung.
-

Hoàng Đình Hiệp:

Tìm hiểu các phép biến đổi KL, PCA (Principle Component Analysis).
Tìm hiểu về phương pháp trích chọn đặc trưng dựa trên các phép biến đổi KLPCA.

- Hoàng Anh Chiến:
Khảo sát các ứng dụng của phép biến đổi PCA trong trích chọn đặc trưng khuôn

mặt

3


1. Phép biến đổi đơn vị (Unitary Transform)
1.1. Định nghĩa
Định nghĩa phép biến đổi đơn vị trong không gian vector dữ liệu:
T

y = TA . x

TA .TA* = I

với điều kiện

Trong đó:
•

x

: Ma trận dữ liệu đầu vào có dạng [1*n]={

x1 , x2 , x3 ,..., xn

}

y
•


•

•
•

: Ma trận hệ số biến đổi

TA
TA*

I

: Ma trận của phép biến đổi

T

: Ma trận chuyển vị của ma trận phức liên hợp của ma trận

TA

: Ma trận đơn vị

Xét điều kiện trên ta thấy:
−1

TA .TA = I

nếu

Mặt khác: Nếu


TA

TA

−1

là trực giao thì

TA = TA ⇒ TAT .TA = I

là ma trận thực thì

Do đó: nếu ma trận

TA

TA* = TA ⇒ TAT = T AT*

vừa thực vừa trực giao thì

TA .TAT* = I

(điều kiện

được thỏa mãn)
Tồn tại một phép biến đổi ngược:

4



xˆ = TS . yˆ = ∑i Tsi y i

•

trong đó

TS = T A

−1

= T AT* ⇒ TS .T A = T A .TS = I

Tsi = ( si ,1 , si , 2 ,..., si , n )
•

chính là hàng thứ i của

ma trận

T A*

và cũng là cột thứ i của ma trận

TAT*

•

Tsi


được gọi là vector cơ sở của phép biến đổi

Phép biến đổi đơn vị phân tích vector x thành tổ hợp tuyến tính của các
vector cơ sở với hệ số phân tích là y.
Kì vọng:

ˆ j = δ [i − j ]
E Φi ,Φ

Trong không gian trực chuẩn,
−1

TA

là ma trận trực giao do đó ta có:

T

TS = TA = TA ⇒ TA .TAT = T AT .TA = I
E Φ i , Φ j = δ [i − j]
1.2. Tính chất chung của các phép biến đổi đơn vị
-

Bảo toàn năng lượng: ||x||2=||y||2 (đẳng thức Parseval), không gây sai số
giữa 2 miền không gian
5


-


Năng lượng tập trung: Đối với ảnh thông thường, năng lượng phân bố
không đều; các thành phần biến thiên nhanh chiếm năng lượng nhỏ trong
tín hiệu; nhiều phép biến đổi đơn vị tập trung năng lượng ảnh vào một vài
thành phần hệ số biến đổi.

-

Giải tương quan: Đầu vào là vector có thành phần tương quan mạnh, qua
phép biến đổi sẽ nhận được các thành phần tương quan yếu.
Đánh giá: Trong các phép biến đổi đơn vị, phương pháp biến đổi KL là tốt
nhất về lí thuyết cho nén dữ liệu.
Nguyên nhân:
o

Phép biến đổi KL đạt được sự giải tương quan tốt nhất nên về mặt
lí thuyết thì đó là phương pháp nén dữ liệu tốt nhất.

Phương pháp biến đổi cosin rời rạc được dùng theo chuẩn JPEG
Nguyên nhân: DCT là một tiêu chuẩn quốc tế cho các hệ thống mã chuyển
vị bởi nó có đặc tính gói năng lượng tốt (gói năng lượng của ảnh con vào
một phần nhỏ các hệ số hàm truyền), cho kết quả là số thực và có thuật toán
nhanh để thực hiện chúng. DCT mang lại một tỉ lệ nén hiệu quả và chất
lượng ảnh suy giảm là có thể chấp nhận được. Chính vì thế với JPEG là
một định dạng ảnh phổ biến nhất hiện nay, việc sử dụng DCT giúp giảm
được rất nhiều chi phí và tài nguyên lưu trữ truyền tải.

6


2. Phép biến đổi KL, PCA

2.1. Phép biến đổi KL

Khái niệm, cơ sở lý thuyết phép biến đổi KL
Phép biến đổi KL có nguồn gốc từ khai triển chuỗi của các quá trình ngẫu

2.1.1.

nhiên liên tục. Biến đổi KL cũng còn gọi là biến đổi Hoteling hay phương
pháp thành phần chính.
Phép biến đổi KL là phép biến đổi tuyến tính đơn vị dựa trên các vecto
riêng và các giá trị riêng của ma trận tương quan để cho phép giảm thứ
nguyên không gian với sai số nhỏ nhất.
Cơ sở lý thuyết của phép biến đổi KL
Đây là phép biến đổi không gian chiều thành không gian chiều, với . Mỗi

2.1.2.

thành phần của vectơ miêu tả một đặc tính của đối tượng. Nếu ta biến đổi
được từ không gian n chiều về không gian m chiều, như vậy ta sẽ làm giảm
được thông tin dư thừa (giảm thứ nguyên).
Mục đích của biến đổi KL là chuyển từ không gian n chiều sang không gian
trực giao m chiều sao cho sai số bình phương là nhỏ nhất. Gọi là tập các
vector cơ sở trong không gian trực giao .
Với

với

và

Mọi vector y trong không gian trực giao có thể viết:

với
Gọi là kết quả thu được trong không gian m chiều và

Sai số trong phép biến đổi
Sai số trung bình bình phương:
7


Mà , do đó
Theo định nghĩa của R, phương trình trở thành:
đạt min khi ( đạt min.
Đặt

.(5)

Như vậy đạt min khi (5) min. Để tìm min của 5 ta dùng phương pháp đạo
hàm và dẫn đến việc giải phương trình:

Phương trình 6 gọi là phương trình đặc trưng của R với là các trị riêng và
là các véctơ riêng tương ứng. Đây chính là cơ sở lý thuyết của biến đổi KL.
Biến đổi KL
Không gian quan sát

2.1.3.

Phép biến đổi KL: sao cho sai số trung bình bình phương nhỏ nhất.
là ma trận của phép biến đổi.
Các bước thực hiện:
Tính ma trận tương quan R của X:
R có giá trị riêng tương ứng với

vecto riêng (trực giao đôi một).
Có phương trình đặc trưng của R:
⇔
⇒ các giá trị riêng
8


⇒ các vecto riêng
Chọn M giá trị lớn nhất trong N giá trị tìm được, ta có M vecto tương
ứng.
Ma trận biến đổi với .

Phép biến đổi PCA

2.2.

Mục tiêu của PCA là tìm một không gian mới với số chiều nhỏ hơn không
gian cũ.
Các trục toạ độ trong không gian mới được xây dựng sao cho trên mỗi trục,
độ biến thiên của dữ liệu trên đó là lớn nhất có thể.
Thuật toán PCA
Cho ma trận

2.2.1.

Tiền xử lý

hoặc

Với là độ lệch chuẩn của cột j trong X.

Xây dựng không gian mới.
Tìm các giá trị riêng và vecto riêng của ma trận hiệp phương sai của .

R có N giá trị riêng �, ta sắp xếp theo thứ tự giảm dần, tương ứng được N
vecto riêng u.
Chuyển dữ liệu từ không gian ban đầu vào không gian mới.
Chọn ra k vecto riêng đầu tiên:
9


Toạ độ các điểm trong không gian mới là:

Trích đặc trưng bằng PCA
Các bước thực hiện:

2.2.2.

Gọi M là số mẫu đầu vào, mỗi mẫu được chuyển thành vector N chiều. Ta
có tập hợp đầu vào
Trung bình của các vector đầu vào:

Sai lệch so với tâm:

Gọi ta có ma trận tương quan của A là:

C có giá trị riêng tương ứng với
vecto riêng (trực giao đôi một).
Ta được:
Sắp xếp các giá trị riêng theo thứ tự giảm dần, tương ứng được các vecto
riêng.

Chọn ra k vector riêng u đầu tiên tương ứng với k giá trị riêng � lớn nhất.

Phép biến đổi tuyến tính là:
10


11


3. Khảo sát các ứng dụng của phép biến đổi PCA trong trích chọn đặc
trưng khuôn mặt
Giới thiệu

3.1.

Trong thực tế có vô vàn các ứng dụng đã được thiết kế phục vụ cho các
mục đích nhận dạng, nhận diện khuôn mặt người.
Ví dụ :
- ứng dụng mở khóa laptop hay mở khóa điện thoại bằng cách nhận diện
-

khuôn mặt
Ứng dụng xác định vị trí những khuôn mặt người trong một bức ảnh
Hệ thống tra cứu tội phạm: Nó giúp cơ quan an ninh có thể kiểm tra

-

một người A có phải là tội phạm đang bị truy nã hay không
Hệ thống tương tác giữa người và máy
Các hệ thống camera,...

.v.v...

Ứng dụng

3.2.

Bài toán:
Ở đây, để khảo sát ứng dụng của phép biến đổi PCA trong trích chọn đặc

3.2.1.

trưng khuôn mặt em sẽ vận dụng vào một bài toán nhỏ :
Em có một bức ảnh trong đó có thể có ảnh khuôn mặt của một người hoặc
là không phải. Và em sẽ phải kiểm tra xem bức ảnh đó có phải là mặt người
hay không. Bài toán này là một phần nhỏ trong bài toán xác định vị trí mặt
người trong một bức ảnh lớn.
Phân tích ứng dụng:
Ứng dụng dựa trên phương pháp thiết lập các khuôn mặt riêng – eigenface

3.2.2.

từ các trị riêng, vectơ riêng của một tập cơ sở dữ liệu các ảnh khuôn mặt đã
có. Ý tưởng của phương pháp là phân tích các thành phần chủ yếu tạo nên
khuôn mặt, hoặc những vectơ riêng của ma trận hiệp phương sai của tập
ảnh các khuôn mặt . Mỗi vectơ chưa một số lượng các đặc tính riêng biệt
của khuôn mặt từ đó tạo ra sự khác nhau giữa các khuôn mặt. Các vectơ
này còn được gọi là các khuôn mặt riêng – eigenfaces.
12



3.2.3.

Sơ đồ thực hiện:
Tập các ảnh mặt
người
Sử dụng phép biến đổi
PCA
Kết quả
Tạo ra khuôn mặt trung
bình và các khuôn mặt
riêng

Đưa ảnh cần kiểm tra
có phải khuôn mặt hay
không

Tính khoảng cách
Euclide

Gần không gian mặt người ???

Đúng
Là ảnh mặt người

Sai
Không là ảnh mặt
người

Đầu vào: Đầu vào là tập dữ liệu ảnh có kích thước giống nhau, mỗi ảnh là
một khuôn mặt (Tập dữ liệu huấn luyện :trainingset)

Qua quá trình vận dụng PCA để biến đổi ta có được đầu ra là các khuôn
mặt riêng (eigenfaces)
13


Sau quá trình tính toán ta đưa ảnh cần xác định có phải là mặt người hay
không vào để kiểm tra.
3.3. Chi tiết các bước thực hiện của PCA

Tính khuôn mặt trung bình:
Giả sử ta có tập huấn luyện gồm M bức ảnh khuôn mặt ,,.., Chúng ta biểu

3.3.1.

diễn mỗi bức ảnh kích thức NxN bằng một vector Γ có kích thước x1:

Các ảnh trong tập huấn luyện lần lượt là Γ1, Γ2, Γ3,…, ΓM. Khuôn mặt trung
bình của tập được ký hiệu:

Tính các vectơ riêng của ma trận hiệp phương sai C:
Để có được các chi tiết cần thiết, ảnh khuôn mặt cần được biểu diễn trong

3.3.2.

một không gian nhỏ hơn. Tương đương với việc ta cần tính các vector riêng
của ma trận hiệp phương sai (các khuôn mặt riêng)
Mỗi khuôn mặt chênh lệch với khuôn mặt trung bình một đại lượng là
vector :

Ta có ma trận hiệp phương sai:


14


Như vậy, ma trận C có kích thước N 2x N2 , việc xác định N2 vector riêng và
giá trị riêng là khó thực hiện. Ta cần một phương pháp dễ dàng hơn để tìm
các vector riêng này. Ta chỉ giữ lại những vectơ riêng tương ứng với những
trị riêng lớn nhất bởi những vectơ riêng này chứa nhiều đặc trưng nhất, còn
các vectơ ứng với các trị riêng nhỏ chỉ chứa một số ít các đặc trưng.
Thay vì việc tính các vector riêng của ma trận C, ta đi tính các vector riêng
của ma trận MxM. Xét các vector riêng vi của ATA :
ATAvi = μi vi
Nhân 2 vế của phương trình trên với A , ta có:
AAT Avi = μi Avi
Từ đó ta thấy = Avi là vector riêng của C = AAT.
Như vậy AAT và ATA có cùng các trị riêng và vector riêng của chúng quan
hệ với nhau theo = Avi
Chú ý: ATA có thể có M trị riêng và vector riêng
AAT có thể có N2 trị riêng và vector riêng
M trị riêng của ATA cùng với các vector riêng tương ứng với M trị riêng
lớn nhất của AAT
Sử dụng các vectơ khuôn mặt riêng để xác định có phải khuôn mặt
người hay không
Do các khuôn mặt riêng tương ứng với các trị riêng lớn nhất được chọn là

3.3.3.

khá đầy đủ để mô tả ảnh các khuôn mặt, nên ta có thể sử dụng chúng để xác
15



định khuôn mặt có phải là mặt người hay không. Các khuôn mặt riêng tạo
ra một không gian chiều con M từ không gian ảnh N2 ban đầu.
Một ảnh cần kiểm tra (Γ) được biến đổi thành các thành phần khuôn mặt
riêng (chiếu vào không gian ảnh mặt) bằng một biến đổi đơn giản

Với k = 1,…, M’. uTk là các vectơ riêng ta đã tính ở trên

Các trọng số của một vector Ω T = [ω1, ω2, …, ωM’ ] mô tả các phần liên
quan của mỗi khuôn mặt riêng trong biểu diễn ảnh khuôn mặt nhập vào.
Để xác định ảnh kiểm tra có phải là khuôn mặt người hay không thì ta có
thể xác định bằng cách tính toán khoảng cách Euclide:

Từ đây, ta có 2 khả năng:
(1)
(2)

: nếu ảnh kiểm tra gần không gian mặt thì đó là ảnh mặt người
: nếu ảnh kiểm tra không gần không gian mặt thì đó không phải là ảnh mặt
người
Ví dụ:

16


Ở ví dụ trên ta thấy nếu một ảnh mặt người sau khi chiếu lên không gian
mặt thì được kết quả gần giống ban đầu, còn ảnh không phải mặt người thì
sau khi chiếu được kết quả rất khác biệt so với ảnh ban đầu. Từ cách đó ta
có thể phân biệt được ảnh đưa vào là ảnh mặt người hay không.
3.4.


Thử nghiệm với Matlab

3.4.1. Tập các ảnh đầu vào
-

30 bức ảnh thể hiện các trạng thái biểu cảm khác nhau của 3 người.
Mỗi bức ảnh có kích cỡ là: 112x92 px

17


3.4.2. khuôn mặt trung bình:

18


3.4.3. Các khuôn mặt riêng được tổng hợp

4. Tài liệu tham khảo:
-

/>
-

matlab-31017/
/>
-

s4339/

/>
19