ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
*** Hoàng Vĩnh Thái
Nghiên cứu một số kỹ thuật phát hiện
đối tượng ảnh dựa vào kết cấu và ứng
dụng

LUẬN VĂN THẠC SĨ
Hà nội – 2006

3
MỤC LỤC


Chữ tắt
Dạng đầy đủ
Nghĩa tiếng Việt
CV
Computer Vision
Hình dung máy tính
KL
Karhumen-Loeve (transform)
Kullback-Leibler
Biến đổi Karhumen-Loeve
SAR
Simultaneous Auto-Regressive
Tự thoái lui đồng thời
DSP
Digital signal processing

Xử lý tín hiệu số
ACF
Autocorrelation Function
Hàm tự tƣơng quan
PWT
Pyramid-structured
Wavelet Transform
Biến đổi dạng sóng kiểu hình chóp
TWT
Tree-structured
wavelet transform
Biến đổi dạng sóng kiểu hình cây
MRF
Markov random field

Phân tích kết cấu đóng một vai trò quan trọng trong lĩnh vực thị giác máy
tính. Trong các ứng dụng nhƣ vậy, việc “hiểu ảnh” chính xác là một trong những
yếu tố chính dẫn đến thành công của hệ thống. Thông thƣờng việc sử dụng dựa
vào yếu tố màu sắc của đối tƣợng để hiểu ảnh (hay giải thích ảnh) là một trong
những kỹ thuật chính để hình thành nên các hệ thống này. Tuy nhiên, trong nhiều
trƣờng hợp sử dụng thông tin màu sắc để giải thích ảnh là chƣa đủ, hoặc không
thể thực hiện đƣợc trong hệ thống.
Trong các ứng dụng giám sát giao thông, hoặc kiểm tra chất lƣợng sản
phẩm công nghiệp thì thông tin về kết cấu đã đƣợc sử dụng để tăng độ chính xác
cho việc sử dụng các thông tin màu sắc đơn thuần [1,3]. Trong một số ứng dụng
khác nhƣ điều khiển chất lƣợng sản xuất vải sợi, so sánh ảnh mây vệ tinh hay địa
chất thì việc sử dụng thông tin kết cấu gần nhƣ là bắt buộc vì các thông tin về
màu sắc, hình dạng không thể hiện đƣợc trong hệ thống [11]. Thông tin kết cấu
cũng có thể đƣợc sử dụng trong phân tích ảnh y học, xác thực cho các hệ thống
an toàn bảo mật dựa vào sinh trắc học, truy vấn ảnh dựa vào nội dung, phân tích
tài liệu, mô hình hóa môi trƣờng,…
Trong vài năm gần đây, có hàng loạt các công trình nghiên cứu, các bài
báo cụ thể liên quan đến việc làm thế nào để có một mô tả kết cấu đủ hiệu quả
cho các ứng dụng thị giác máy tính. Xét một cách trực quan, kết cấu cung cấp
một lƣợng thông tin phong phú về bề mặt tự nhiên của hình ảnh. Tuy nhiên, việc
phân tích kết cấu nói chung và biểu diễn kết cấu một cách đầy đủ, hiệu quả nói
riêng vẫn là một vấn đề khó do bởi sự đa dạng và phức tạp của vấn đề kết cấu tự nhiên.
Nội dung của bản luận văn này sẽ giới thiệu về cơ sở lý thuyết cũng nhƣ
hƣớng ứng dụng của việc biểu diễn thông tin kết cấu cho chức năng phát hiện đối
tƣợng của một hệ thống thị giác máy tính điển hình. Trên cơ sở đó tiến hành thử
nghiệm xây dựng một bộ các module chƣơng trình cho việc phát hiện, phân loại
đối tƣợng dựa vào kết cấu bề mặt của đối tƣợng. Về cơ bản nội dung của luận
văn đƣợc chia thành 3 chƣơng chính sau:

6

tƣợng trong tự nhiên. Theo từ điển Webster, 1986 kết cấu “Là cấu trúc hoặc một
sự sắp xếp cơ sở, một kết hợp chặt chẽ của hầu hết các phần tử riêng lẻ tạo nên
một đối tượng” Theo từ điển Oxford, 1989 “Là sự tổ chức, cấu trúc, hoặc chất
liệu của bất kỳ những gì hình thành nên một đối tượng” Nói chung, ngƣời ta có
thể hiểu một cách chung nhất kết cấu là các tính chất thể hiện ra bên ngoài có thể
nhìn thấy và tiếp xúc đƣợc của một đối tƣợng nào đó. Nhiều ví dụ minh họa về
kết cấu nhƣ kết cấu của cát, của khói, của vân tay ngƣời,… Đối với con ngƣời,
thể hiện của kết cấu liên quan đến các cấu trúc cục bộ của bề mặt đƣợc lặp đi lặp
lại về mặt không gian. Các cấu trúc này đƣợc hình thành từ một hay một vài phần
tử cơ bản (Primitives) riêng biệt. Nó chứa các thông tin quan trọng về sự sắp xếp
cấu trúc của bề mặt. Hình 1.1 : Ví dụ về kết cấu
Kết cấu gạch
Kết cấu vân tay
Kết cấu mây
Kết cấu đất

8
Trong lĩnh vực xử lý ảnh số, tính chất kết cấu của ảnh đƣợc thể hiện thông
qua sự biến thiên về màu sắc và cƣờng độ của ảnh. Mặc dù không thể có thông
tin về nguyên nhân sự biến thiên này nhƣng thông tin về sự khác nhau của của
các pixel trong ảnh đã đƣa ra nhiều phƣơng pháp để xác định kết cấu của đối
tƣợng. Tuy nhiên từ trƣớc đến nay chƣa ai có thể đƣa ra đƣợc một định nghĩa
chính xác về mặt toán học (định nghĩa cho xử lý số) cho kết cấu của đối tƣợng
trong ảnh số. Theo [1], Haralick (1973):“Kết cấu rất khó để có được một định

(1993) dựa trên ba chiều trực giao là sự lặp lại – sự không lặp, sự vô hƣớng với
sự tƣơng phản cao - có hƣớng với sự tƣơng phản thấp, độ mịn – độ hạt của kết
cấu, kết cấu đƣợc phân chia theo sự đồng nhất về không gian của chúng thành
ba loại: kết cấu đồng nhất, kết cấu đồng nhất yếu (hình 1.4), kết cấu không đồng
nhất. Dựa trên cách phân loại này một số độ đo kết cấu (Texture Measures) đã
đƣợc nghiên cứu và áp dụng cho các hệ thống thị giác máy tính [1] .

10

Hình 1.4: Ví dụ về kết cấu đồng nhất yếu
1.1.2 Các ứng dụng của kết cấu
Trong lĩnh vực thị giác máy tính thông tin kết cấu đóng một vai trò quan
trọng. Trong hầu hết các ứng dụng, các kỹ thuật đƣợc phát triển cho việc phân
tích kết cấu tập trung vào việc tìm một mô tả kết cấu một cách hiệu quả, tổng
quát [ 1, 10, 11, 12]. Mục đích chính là để cho máy tính có thể sử dụng các thao
tác toán học cho việc thay thế, so sánh cũng nhƣ chuyển đổi kết cấu. Các giải
thuật phân tích kết cấu hầu hết liên quan đến việc chọn lọc, xác định các đặc
trƣng kết cấu và biểu diễn các đặc trƣng này dƣới một dạng mà máy tính có thể
hiểu đƣợc. Các giải thuật khác nhau có các đặc trƣng đƣợc chọn lọc và cách biểu
diễn các đặc trƣng của kết cấu khác nhau. Với các giải thuật sử dụng tiếp cận
thống kê, chúng đặc tả kết cấu qua các thông kê tín hiệu của ảnh hay các tính
chất phân bố không gian của tín hiệu ảnh. Với các giải thuật sử dụng cách tiếp
cận theo phổ của ảnh (Spectral), chúng đặc tả kết cấu theo miền phổ. Các giải
thuật tiếp cận theo mô hình kết cấu có cấu trúc, chúng đặc tả các kết cấu nhƣ là
phân cấp theo sự sắp xếp không gian của các đối tƣợng cơ bản. Cũng tƣơng tự
nhƣ mô hình xác suất cho giải thuật phân tích kết cấu. kết cấu đƣợc đặc tả dƣới
dạng hàm phân bố. Có 4 dạng ứng dụng chính của kết cấu dựa trên các kỹ thuật
phân tích kết cấu vừa nêu.

11

12
chiều. Các khoảng cách Euclidean, Chi-square, và Kullback-Leibler là các
khoảng cách đƣợc sử dụng chính để đo độ tƣơng tự của hai vector đặc trƣng. Đây
là các phƣơng pháp phân loại không tham số.
Một số phƣơng pháp phân loại khác dựa vào giả thiết về sự phân bố xác
suất của vector đặc trƣng thƣờng đƣợc gọi với tên phân loại có tham số. Phân
loại kết cấu có thể sắp xếp các dữ liệu ảnh thành các thông tin có thể hiểu đƣợc
một cách dễ dàng. Điều này làm cho nó có nhiều ứng dụng rộng rãi trong các lĩnh
vực nhƣ truy vấn ảnh dựa vào nội dung, các ứng dụng ảnh y học, các ứng dụng
kiểm tra chất lƣợng công nghiệp hay các ứng dụng về nhận dạng vân tay, mặt
ngƣời, tròng mắt trong các ứng dụng về an ninh sinh trắc học …
 Phân đoạn kết cấu
Phân đoạn kết cấu là các loại ứng dụng phân chia một ảnh thành các vùng
riêng biệt dựa vào thuộc tính kết cấu của bề mặt của các vùng. Các vùng này là
các vùng có cùng một thuộc tính kết cấu nào đó. Kết quả của quá trình phân đoạn
dựa vào kết cấu có thể làm đầu vào cho các quá trình xử lý và phân tích ảnh về
sau (chẳng hạn nhƣ nhận dạng đối tƣợng). Cũng nhƣ quá trình phân loại kết cấu,
phân đoạn kết cấu cũng gồm hai trạng thái chính là xác định các độ đo đặc trƣng
và sử dụng các thông số để cô lập các kết cấu. Tuy nhiên việc phân đoạn các kết
cấu phải làm thêm việc dò đƣợc biên của các kết cấu đã đƣợc nhận dạng. Các kỹ
thuật phân đoạn kết cấu cũng có thể là giám sát hoặc không giám sát phụ thuộc
vào thông tin đƣợc biết trƣớc của ảnh hoặc các lớp kết cấu sẵn có.
Phân đoạn kết cấu có giám sát xác định và phân biệt một hoặc nhiều vùng
phù hợp với thuộc tính kết cấu đƣợc cung cấp trong mẫu huấn luyện. Phân đoạn
kết cấu không giám sát phải lấy các lớp kết cấu khác nhau từ một ảnh trƣớc khi
phân chúng thành các vùng. So với việc phân đoạn kết cấu có giám sát thì việc
phân đoạn không giám sát linh hoạt và phù hợp hơn với các ứng dụng thế giới
thực, tuy nhiên việc thực hiện nó sẽ phức tạp và khả năng để tính toán sẽ cao hơn.

13


Hình 1.6: Ví dụ về tổng hợp kết cấu
 Tạo hình ảnh từ kết cấu
Tạo hình ảnh từ kết cấu là các ứng dụng mà phải ƣớc lƣợng hình dạng của
mặt phẳng 3 chiều dựa trên việc phân tích tính chất của kết cấu ảnh hai chiều.
Tính đồng nhất và tính đẳng hƣớng có thể cung cấp thông tin về hình dạng của bề
mặt 3 chiều. Độ nghiêng của kết cấu có thể bị ảnh hƣởng là do ảnh đƣợc xem ở
một góc nghiêng nào đó. Từ các góc nghiêng này ngƣời ta có thể suy ra các tham
số về hình dạng của bề mặt hay sử dụng các thao tác chuyển đổi. Thông qua các

15
góc nghiêng và hƣớng này chiều sâu của đối tƣợng ảnh có thể đƣợc khôi phục.
Cũng dựa vào các thông số của kết cấu này ngƣời ta có thể suy ra đƣợc bố trí của
các đối tƣợng trong ảnh.

Hình 1.7: Ứng dụng tạo lại hình ảnh trong lĩnh vực ảnh y học
1.2 Phát hiện đối tƣợng dựa vào kết cấu.
1.2.1 Phát hiện đối tƣợng
Phát hiện đối tƣợng hay phát hiện đối tƣợng trong một ảnh thực chất là
hoạt động tìm lớp các đối tƣợng nào đó đƣợc định nghĩa trƣớc trong ảnh [14]. Nó
cũng đƣợc xem nhƣ một ứng dụng của nhận dạng mẫu. Ngƣời ta thƣờng xem
phát hiện đối tƣợng ảnh nhƣ là một chức năng con trong các ứng dụng về phân
tích ảnh và thị giác máy tính. Trong một hệ thống CV điển hình các thành phần
chính đƣợc sử dụng theo tuần tự sau:
- Thu nhận ảnh.
- Xử lý nâng cao chất lƣợng ảnh đầu vào.
- Phân đoạn ảnh thành các đối tƣợng quan sát.
- Trích chọn các đặc trƣng của đối tƣợng.
- Phân loại đối tƣợng.


biểu diễn đặc trưng từ đối tƣợng ảnh (các đối tƣợng này đƣợc phân đoạn và xác
định từ trƣớc) và phân loại đối tượng ảnh thành các đối tƣợng cho mục đích
phát hiện đối tƣợng ảnh.

Hình 1.9: Sơ đồ một hệ thống giám sát giao thông
Phát hiện đối tượng là một chức năng trong hệ thống
Có thể có nhiều các định nghĩa khác nhau cho một hệ thống phát hiện đối
tƣợng ảnh. Tuy nhiên hai thành phần trên đƣợc xem là chính yếu để hình thành
nên hệ thống. Trong khuôn khổ của luận văn này việc xác định các kỹ thuật cũng
nhƣ thiết kế, so sánh, đánh giá giữa các hệ thống phát hiện đối tƣợng sẽ đƣợc
thực hiện dựa trên hai thành phần chủ yếu trên. Có rất nhiều các kỹ thuật đƣợc
phát triển để thực hiện hai chức năng trên, ta sẽ đề cập đến các kỹ thuật này ở
phần sau.

18
1.2.2 Các thành phần của hệ thống phát hiện đối tƣợng
 Xác định và biểu diễn đặc trƣng
Sau khi thu nhận đƣợc ảnh đầu vào, để có thể xử lý bằng máy tính, các
đặc trƣng của ảnh (sau khi đã tách đƣợc thành các đối tƣợng riêng biệt) sẽ đƣợc
hệ thống phát hiện đối tƣợng xác định. Các đặc trƣng này sẽ đƣợc sử dụng để
phân loại hay phát hiện các đối tƣợng cần thiết dựa vào việc so sánh với các đặc
trƣng mẫu. Việc tìm một phƣơng pháp để biểu diễn các đặc trƣng của dữ liệu ảnh
một cách hiệu quả là một trong những nghiên cứu trọng tâm trong lĩnh vực CV
nói chung và phát hiện đối tƣợng ảnh nói riêng. Tùy vào từng ứng dụng có các kỹ
thuật biểu diễn và xác định đặc trƣng khác nhau. Các đặc trƣng này phải đồng
nhất về thể hiện nhƣ các đặc trƣng mẫu trong cơ sở dữ liệu. Từ các biểu diễn đặc
trƣng này hệ thống có thể tính toán để phân loại và phát hiện đƣợc các đối tƣợng
cần thiết bằng các công cụ toán học thông thƣờng.
Về cơ bản có một số kỹ thuật biểu diễn các đặc trƣng của ảnh thƣờng
đƣợc áp dụng dựa trên các đặc trƣng dễ nhận thấy của ảnh nhƣ: các đặc trƣng về

biến. Các góc (các điểm với độ cong cao) hay các phân đoạn của biên cũng là
một trong những thành tố để biểu diễn đặc trƣng cục bộ của đối tƣợng. Với các
đặc trƣng kết hợp, các đặc trƣng sử dụng dựa trên vị trí tƣơng đối của các đối
tƣợng cục bộ và các đặc trƣng cục bộ. Vị trí tƣơng đối này có thể là khoảng cách
và các số đo về hƣớng, chiều liên kết liên quan.
 Phân loại đối tƣợng ảnh
Sau khi xác định đƣợc các đặc trƣng thích hợp của đối tƣợng thì việc tiếp
theo của một hệ thống phát hiện đối tƣợng là phân loại kết cấu và phát hiện đối
tƣợng cần. Khi số các mẫu trong cơ sở dữ liệu lớn, và số đối tƣợng cần phải phân
loại nhiều thì phải có các kỹ thuật khác nhau để hỗ trợ cho việc phân loại chính
xác. Các kỹ thuật này có thể khác nhau từ đơn giản đến phức tạp, có thể kết hợp
nhiều bộ phân loại với nhau để tạo ra một bộ phân loại nhiều tầng để tăng độ
chính xác. Tuy nhiên, theo [14], có thể quy về hai loại kỹ thuật chính sử dụng
mạng Neural trong phân loại đối tƣợng ảnh là phân loại có giám sát và phân loại

20
không giám sát phụ thuộc vào tập ví dụ mẫu sẵn có. Phân loại có giám sát
(Supervised Classification) hay còn gọi là học có giám sát (là loại kỹ thuật yêu
cầu thông tin về tập đối tƣợng mẫu để huấn luyện, đối tƣợng mới sẽ đƣợc phân
biệt nhờ hệ thống đã đƣợc huấn luyện). Các kỹ thuật phân loại này có thể dựa
trên mô hình phụ thuộc hàm phân bố (Statistical), có thể có tham số (nhƣ phân
bố Gaussian) hoặc không tham số và mô hình không phụ thuộc hàm phân bố
(Distribution - free). Phân loại không giám sát (Nonsupervised Classification) là
loại phân loại sử dụng kỹ thuật mà không cần thông tin trƣớc về đối tƣợng mẫu,
hệ thống sẽ tự nhận ra thông tin về đối tƣợng để phân loại. Trong [16], với giả sử
các đặc trƣng cho một đối tƣợng đƣợc biểu diễn trong một không gian N chiều,
một số kỹ thuật phân loại thƣờng đƣợc dùng trong phân loại đối tƣợng đƣợc thể
hiện một cách toán học và rõ ràng hơn.
 Phân loại láng giềng gần nhất (Nearest Neighbor Classifiers):
Giả sử rằng đối tƣợng mẫu đại diện cho mỗi lớp đã biết và đặc trƣng biểu











Khi đó đối tƣợng đƣợc phân vào lớp R khi và chỉ khi khoảng cách tới lớp R
là nhỏ nhất.
 
j
N
1j
R
dmind



Một vấn đề đặt ra khi sử dụng giải thuật láng giềng gần nhất này là điểm
nào trong không gian đặc trƣng sẽ là điểm đại diện cho lớp để có thể tính khoảng
cách tới điểm đặc trƣng đầu vào. Một lớp có thể chứa nhiều đối tƣợng, đƣợc thể
hiện bằng cụm các điểm trong không gian đặc trƣng nhƣ trong hình 1.10:

Hình 1.11: Một lớp đƣợc thể hiện bằng cụm các điểm
Ngƣời ta giải quyết vấn đề này bằng cách chọn điểm đại diện cho lớp là
điểm trọng tâm của cụm hoặc chọn điểm trong lớp có khoảng cách gần với điểm
đầu vào nhất.

 
 
 
 
xp
wPwxp
xwP
jj
j


Với
 
 
 
.wPwxpxp
N
1j
jj




Trong [4,6,7,8] trình bày một số kỹ thuật phân loại để đánh giá một đối
tƣợng đầu vào có thuộc một lớp các đối tƣợng nào đó hay không, dựa vào kỹ
thuật đánh giá độ tƣơng tự. Một vài phƣơng pháp đo độ tƣơng tự thƣờng đã đƣợc
sử dụng trong các hệ thống thực tế, nhất là các ứng dụng truy vấn ảnh theo nội
dung. Khác nhau duy nhất so với các bộ phân loại đã kể trên là khác nhau của
hàm tính khoảng cách và tiêu chuẩn để phân loại. Để thuận tiện cho việc trình
bày các kỹ thuật này chúng ta đƣa ra một số ký hiệu chung đƣợc dùng trong tất


, D(I, J) tƣơng ứng là L
1
, L
2
(còn gọi là khoảng cách
Euclide) và L

. Khoảng cách Minkowski là phép đo đƣợc sử dụng nhiều nhất
trong tra cứu ảnh. Một trƣờng hợp đặc biệt của khoảng cách L
1
là tập giao nhau
của các histrogram. Giao của hai histogram I và J đƣợc định nghĩa nhƣ sau:





N
i
i
N
i
ji
Jf
JfIf
jIS
1
1
)(

(I) và f
i
(J).

24
Khoảng cách toàn phƣơng đƣợc sử dụng trong nhiều hệ thống tra cứu dựa
trên histogram màu.
 Khoảng cách Mahalanobis
Phƣơng pháp đo khoảng cách Mahalanobis sử dụng thích hợp nhất khi các
chiều của vector đặc trƣng không độc lập với nhau và có độ quan trọng khác
nhau. Công thức định nghĩa khoảng cách Mahalanobis là:

)()(),(
1
JI
T
JI
FFCFFJID 
trong đó C là ma trận hiệp biến của các vector đặc trƣng.
Cách tính khoảng cách Mahalanobis có thể đƣợc đơn giản hoá nếu các
chiều của vector đặc trƣng độc lập với nhau, chỉ một phƣơng sai của mỗi thành
phần đặc trƣng c
i
là cần thiết, khi đó:




i
i
i
i
f
Jf
Jf
f
If
IfJID
^^
)(
log)(
)(
log)(),(

Trong đó f
i
^
= [f
i
(I) + f
i
(J)]/2. Khác với độ phân kỳ KL, độ phân kỳ Jeffrey
có tính đối xứng cao.

25
1.2.3 Vai trò của kết cấu trong phát hiện đối tƣợng
Nhƣ đã nêu ở phần trƣớc, việc biểu diễn các đặc trƣng của đối tƣợng ảnh
đóng một vai trò đặc biệt trong các ứng dụng CV nói chung và phát hiện đối

Tuy nhiên với nhiều mô hình biểu diễn đối tƣợng có thể rất hữu dụng vì độ
chính xác nó mang lại nhƣng lại rất nặng nề về xử lý nhất là trong các ứng dụng
yêu cầu về thời gian thực, các ứng dụng loại này yêu cầu thời gian xử lý phải tính
bằng thời gian để xử lý một khung hình của cảnh thực. Thêm nữa cách biễu diễn
này có hữu dụng (có nhận ra đƣợc đối tƣợng) khi ảnh bị co giãn hoặc các đối
tƣợng bị quay đi theo một góc nào đó. Phần 2.3 sẽ trình bày một phƣơng pháp kết
hợp cả tiếp cận có cấu trúc và tiếp cận thống kê để biểu diễn thông tin cấu trúc. Đối
với từng loại ứng dụng phát hiện đối tƣợng dựa vào kết cấu khác nhau, việc xác định
đƣợc mô hình biểu diễn thông tin kết cấu thích hợp là vô cùng quan trọng.
 Phát hiện đối tƣợng
Các đặc trƣng kết cấu của đối tƣợng phù hợp với các mô hình kết cấu
trong cơ sở dữ liệu nhƣ thế nào? Trong nhiều trƣờng hợp, với việc kết hợp nhiều
đặc trƣng và nhiều đối tƣợng khác nhau, với một phƣơng pháp phân loại để phát
hiện đối tƣợng toàn diện có thể dẫn đến việc chậm chạp trong xử lý bất kể tính
hữu dụng của nó.

Trích đoạn Xây dựng phƣơng pháp biểu diễn kết cấu Xây dựng chức năng phân loại đối tƣợng Thực nghiệm minh họa

---