ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CƠNG NGHỆ

lª thÞ kim nga

NGHIÊN CỨU MỘT SỐ KỸ THUẬT
PHÁT HIỆN CHẤT LIỆU VÀ ỨNG DỤNG

LUẬN VĂN THẠC SỸ

Hà Nội – 2006


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Lê Thị Kim Nga

NGHIÊN CỨU MỘT SỐ KỸ THUẬT PHÁT HIỆN
CHẤT LIỆU VÀ ỨNG DỤNG

Ngành: Công nghệ Thông tin
Mã số: 1.01.10

LUẬN VĂN THẠC SĨ
Người hướng dẫn khoa học: TS. Đỗ Năng Toàn

Hà Nội – 2006


LỜI CAM ĐOAN

MỤC LỤC
DANH MỤC CÁC TỪ VIẾT TẮT .................................................................. 1
DANH MỤC CÁC BẢNG ................................................................................ 1
DANH MỤC CÁC HÌNH VẼ ........................................................................... 2
MỞ ĐẦU ........................................................................................................... 4
Chương 1 -TỔNG QUAN VỀ PHÁT HIỆN CHẤT LIỆU TRONG ẢNH ...... 7
1.1 Bài toán phát hiện chất liệu trong ảnh ......................................................... 7
1.1.1 Chất liệu trong ảnh ........................................................................... 7
1.1.2 Phát hiện chất liệu ............................................................................ 8
1.2 Các đặc trưng của chất liệu trong ảnh ......................................................... 9
1.2.1 Màu sắc............................................................................................. 9
1.2.2 Kết cấu ............................................................................................ 10
1.2.3 Hình dạng ....................................................................................... 11
1.2.4 Mối quan hệ không gian ................................................................. 11
1.3 Các độ đo sự tương tự thường sử dụng ..................................................... 12
1.4 Mơ hình bài tốn phát hiện chất liệu ......................................................... 15
Chương 2 – CÁC CÁCH TIẾP CẬN TRONG PHÁT HIỆN CHẤT LIỆU... 16
2.1 Phương pháp Habin cải tiến ...................................................................... 16
2.1.1 Phương pháp Habin ........................................................................ 18
2.1.2 Phương pháp Habin cải tiến ........................................................... 20


2.2 Phương pháp trừu tượng ảnh dựa trên chữ ký nhị phân ........................... 21
2.3 Phương pháp Ma trận Ordinal Co-occurrence .......................................... 25
2.3.1 Ma trận Ordinal Co-occurrence ..................................................... 25
2.3.2 Giải thuật ........................................................................................ 27
2.3.3 So sánh các đặc điểm ..................................................................... 28
2.4 Cách tiếp cận Mạng Nơron ....................................................................... 29
2.4.1 Mơ hình Mạng Nơron nhân tạo ...................................................... 30
2.4.2 Hàm kích hoạt ................................................................................ 31


Color Cohenrence Vector

Vectơ kết dính màu

CBA

Constant – Bin Allocation

Cấp phát các bin cố định

GCH

Global Color Histogram

Biểu đồ màu tồn cục

HMM

Hidden Markov Model

Mơ hình Markov ẩn

LCH

Local Color Histogram

Biểu đồ màu cục bộ

VBA

Hình 2.11. Cấu trúc LeNet-5, Mạng Nơron xoắn. .......................................... 34
Hình 2.12. Đồ thị của hai hàm P(x/1) và P(x/2). ........................................ 39
Hình 2.13. Mơ tả thuật tốn Viterbi. ............................................................... 42
Hình 2.14. Mơ hình kiểu mẫu của một HMM ba trạng thái. .......................... 43
Hình 3.1. Ảnh kết quả phát hiện chất liệu kính. ............................................. 56
Hình 3.2. Mơ hình hoạt động của mạng nơron. .............................................. 57

2


Hình 3.3. Ví dụ các đầu vào và đầu ra cho huấn luyện mạng định tuyến. ..... 58
Hình 3.4. Cấu trúc mạng xác định mặt. .......................................................... 60
Hình 3.5. Ảnh gốc chứa một mặt trong ảnh. ................................................... 63
Hình 3.6. Vùng có da sau khi tách. ................................................................. 63
Hình 3.7. Những vùng tìm được của mạng. .................................................... 63
Hình 3.8. Kết quả cuối cùng sau khi sử dụng ngưỡng động. .......................... 63
Hình 3.9. Ảnh gốc với trường hợp có nhiều mặt. ........................................... 63
Hình 3.10. Vùng da sau khi được tách. ........................................................ 64
Hình 3.11. Ảnh trước khi tách ngưỡng động. ................................................. 64
Hình 3.12. Kết quả sau khi tách ngưỡng với trường hợp ảnh chứa nhiều mặt.64
Hình 3.13. Một ảnh mẫu từ tập phân phối thỏa mãn D và có năng lượng
cực tiểu. ............................................................................. 69
Hình 3.14. Kết quả phát hiện da mặt bằng mơ hình HMM. ........................... 71
Hình 3.15. Phát hiện nhầm màu da. ................................................................ 71

3


MỞ ĐẦU


mỗi một loại đối tượng sẽ có một kỹ thuật cụ thể, song chúng vẫn có một cơ
sở chung. Cách tiếp cận dựa vào chất liệu của đối tượng đang là một hướng
nghiên cứu mới hiện nay, ví dụ có thể phát hiện ra khn mặt người nhờ vào
chất liệu da mặt, hoặc phát hiện người dựa vào chất liệu vải mà người đó đang
mặc, hay có thể phát hiện ơ tơ dựa vào chất liệu kính v.v.. Song càng quan
trọng hơn nếu ta xét đến tính thiết thực của loại chất liệu cần phát hiện. Chẳng
hạn, kính là một loại chất liệu được sử dụng rất phổ biến, nó có khắp mọi nơi
như kính chắn gió của ơ tơ, các cửa bằng kính, các bóng đèn, kính làm tủ, làm
bàn, làm các hộp, các chai v.v.. Có thể tạo ra các hệ thống phát hiện các toà
nhà (hầu hết các tòa nhà lớn đều được làm chủ yếu là kính) trong một thành
phố, phát hiện ơ tơ (vì ơ tơ ln có kính) thơng qua chất liệu kính. Tất cả các
bài tốn trên đều có tầm quan trọng đáng kể, đặt biệt bài tốn phát hiện ơ tơ là
bài tốn đang được nhiều quan tâm ở nước ta, là một trong những bài toán
giám sát tự động: phát hiện, phân loại và đếm số ô tô tại các chốt giao thơng
hoặc tại các trạm thu phí nhằm nâng cao tiềm năng phát triển của mỗi
quốc gia.
Như vậy bài toán phát hiện chất liệu là một cách tiếp cận mới trong khoa
học nhận dạng hay mơ hình hóa trong thực tại ảo, là cơ sở để xây dựng nhiều
ứng dụng quan trọng và cần thiết. Bên cạnh đó, bài tốn phát hiện chất liệu
kính có thể ứng dụng cho bài tốn giám sát giao thơng tự động, đặt biệt ở Việt
Nam hiện nay, đây chính là tính thời sự của vấn đề.

5


Mặt khác, hiện nay trên thế giới chưa có một đề cập nào về bài toán phát
hiện chất liệu một cách rõ ràng, đặt biệt là chất liệu kính. Vì thế mà vấn đề
này rất có ý nghĩa khoa học.
Trên đây đã điểm qua tầm quan trọng của bài toán phát hiện chất liệu,
đặt biệt là chất liệu kính đã cho ta thấy rõ tính cần thiết cũng như tính thời sự

Theo quan điểm thông thường, chất liệu chính là những đặc trưng cho
một dạng vật chất cụ thể.
Theo quan điểm khoa học công nghệ nhận dạng ảnh, chất liệu của một
đối tượng chính là thành phần bao phủ bên ngồi của đối tượng đó, là thành
phần khơng thể thiếu được trong mỗi đối tượng. Có rất nhiều chất liệu khác
nhau như kính, vải, gỗ, nước, tuyết v.v.. Chất liệu tồn tại khác nhau ở mỗi đối
tượng khác nhau, chẳng hạn với những con vật thì chất liệu là những bộ lơng;
với con người chất liệu có thể là vải, da; với kính thì chất liệu cũng chính là
kính, hay chất liệu của một tồ nhà có thể là kính nếu tịa nhà có nhiều cửa
được làm bằng chất liệu kính, chất liệu của một chiếc ơ tơ có thể là kính nếu
ta chỉ xét ơ tơ với kính chắn gió v.v..
Như vậy phát hiện chất liệu cũng chính là phát hiện ảnh của chất liệu đó
trong một bức ảnh. Như thế nội dung ảnh của một đối tượng chính là nội dung
của chất liệu trong ảnh hay còn gọi là nội dung ảnh. Mà nội dung ảnh được
thể hiện bởi các đặc trưng màu sắc, kết cấu, hình dạng. Nhưng trong hầu hết
mọi chất liệu, nội dung ảnh được phản ánh bởi màu sắc và kết cấu mà thôi.

7


1.1.2 Phát hiện chất liệu
Cho trước một bức ảnh có thể tĩnh hoặc động, yêu cầu xác định xem
trong bức ảnh đó có loại chất liệu mà ta cần quan tâm khơng, thậm chí là bao
nhiêu chất liệu đó nằm trong bức ảnh.
Cách giải quyết bài toán
Tư tưởng: Cho trước một ảnh của chất liệu, ta tìm trong ảnh cần xét (ảnh
truy vấn) có ảnh của chất liệu đó hay không. Bằng cách đánh giá mức độ
giống nhau của ảnh chất liệu cho trước với ảnh của chất liệu có trong ảnh.
Nhưng đặc trưng của ảnh chất liệu chủ yếu là màu sắc, kết cấu, thơng tin
khơng gian, do đó giải quyết bài toán này bằng cách đối sánh các đặt trưng

Mọi người đều biết màu là gì, nhưng sự mơ tả chính xác và chi tiết về
màu thì lại là một chuyện khác. Màu sắc luôn là chủ đề lớn trong các ngành
khoa học khác nhau. Mặc dù vậy, một số vấn đề chủ yếu liên quan đến màu
sắc, đặt biệt là trong cảm nhận màu của con người mà tại đó sự hoạt động của
não đóng vai trị quan trọng vẫn chưa được hiểu một cách đầy đủ. Những
thuộc tính cấp thấp về cảm nhận màu của con người cũng đã được mơ hình hố
thành cơng trong khn khổ phạm vi của các thiết bị đo màu. Trong khuôn khổ
này ta thấy rằng các phương pháp thống kê là công cụ đầy sức mạnh cho việc
phân tích và mơ tả dữ liệu hình ảnh.
Một ảnh màu điển hình được lấy từ Camera số hoặc download từ
Internet thường có ba kênh màu (ảnh xám chỉ có một kênh), những giá trị của
dữ liệu ba chiều này từ ảnh màu có thể cho ta biết vị trí của điểm ảnh trong
khơng gian màu. Những điểm ảnh có cùng giá trị ví dụ (1, 1, 1) cho những
màu khác nhau trong những không gian màu khác nhau. Như vậy mô tả đầy
đủ của một ảnh màu điển hình gồm thơng tin khơng gian hai chiều với điểm
ảnh trong vùng không gian này và dữ liệu màu ba chiều với điểm ảnh màu

9


trong không gian mà chúng ta đang đề cập. Ở đây giả thiết không gian màu là
cố định, bỏ qua thơng tin khơng gian, thơng tin màu trong ảnh có thể coi như
là tín hiệu ba chiều đơn giản.
Nếu ta xem thơng tin màu của ảnh là tín hiệu một, hai, hoặc ba chiều đơn
giản thì việc phân tích các tín hiệu sử dụng ước lượng mật độ xác suất là một
cách dễ nhất để mô tả thông tin màu của ảnh. Biểu đồ màu là công cụ đơn
giản nhất, những cách khác mô tả thông tin màu gồm đại diện màu, moment
màu, vector kết dính màu v.v..

1.2.2 Kết cấu

phức tạp, trong khi rất nhiều phương pháp mơ tả hình dạng thực tế đang tồn
tại nhưng khơng có một phương pháp chung nào cho mơ tả hình dạng. Có hai
kiểu đặc điểm hình dạng chính thường được sử dụng: Đặc điểm dựa trên biên,
đặc điểm dựa trên vùng. Đặc điểm dựa trên biên chỉ sử dụng đường bao ngồi
của hình dạng trong khi đó đặc điểm vùng sử dụng tồn bộ vùng của hình
dạng. Ví dụ những đặc điểm biên bao gồm mã xích, mơ tả Fourier, những
đường viền hình học như uống cong, chiều dài biên v.v.. Đặc điểm vùng như
số chu trình, độ lệch tâm v.v..

1.2.4 Mối quan hệ khơng gian
Mối quan hệ không gian đặc trưng cho sự sắp xếp các đối tượng bên
trong một bức ảnh. Mối quan hệ giữa hai đối tượng có thể được phân loại một
cách rõ ràng như là hướng hoặc tơ pơ hình học. Mối quan hệ hướng dựa vào
vị trí liên quan và khoảng cách mêtric giữa hai đối tượng trong ảnh. Mặt khác,
mối quan hệ tơ pơ hình học khơng dựa vào khoảng cách thu được giữa hai đối
tượng mà dựa vào khái niệm lý thuyết tập hợp như giao, hợp, kết nối v.v..
*** Một trong những vấn đề thách thức to lớn để giải quyết bài toán phát
hiện hay nhận dạng đối tượng là việc chọn lựa và sự biểu diễn các đặc
trưng này.

11


1.3 Các độ đo sự tương tự thường sử dụng
Bên cạnh đó, những độ đo tương tự cũng là yếu tố đóng vai trị cốt yếu
trong việc giải quyết bài toán được đặt ra. Những độ đo lý tưởng phải có một
số thuộc tính sau:
- Độ đo tự tương quan: Đặc điểm khoảng cách giữa hai ảnh là lớn chỉ khi
những ảnh không tương tự và ngược lại khoảng cách giữa hai ảnh là nhỏ nếu
chúng tương tự. Ảnh thường được mô tả trong không gian đặc điểm và sự

- Sự bền vững: Hệ thống cần có khả năng để thay đổi những điều kiện
ảnh, ví dụ nếu ảnh được lấy dưới ánh sáng đèn điện (hơi đỏ), thì hệ thống
cũng phải cho kết quả đúng khi lấy ảnh dưới điều kiện ánh sáng ban ngày
(hơi xanh).
Có nhiều độ đo khoảng cách tương tự đã được đưa ra nhưng chúng đều
không đầy đủ các thuộc tính trên. Dưới đây là một số độ đo chung nhất
thường được sử dụng:
Histogram intersection Distance:
Độ đo khoảng cách này được định nghĩa trên phần chung của hai biểu đồ
màu. Cho hai biểu đồ màu h1, h2 khoảng cách giữa chúng có thể được định
nghĩa như sau:
N

disHI  1   min( h1i , h2i )
i 1

Việc đo khoảng cách này rất nhanh vì nó dựa trên cơng thức đơn giản.
Tuy nhiên thông tin màu không được sử dụng khi nhận được khoảng cách bởi
vậy có thể dẫn đến những kết quả không tốt.
Lp Distance:

13


Khoảng cách dạng Minkowski Lp giữa hai biểu đồ màu được định nghĩa:

disMp


   h1i  h2i


g d


g
ij

ij

ij

ij

ij

Trong đó gij biểu thị khoảng cách tương tự giữa mức i và mức j, g ij >0 là
sự tối ưu hoá giữa hai phân bố như là tổng giá trị được cực tiểu hoá.

14


g

ij

 h1i

g

ij

Hình 1.1. Sơ đồ chức năng phát hiện chất liệu

Song để tăng cường độ chính xác, ta có thể sử dụng các mơ hình học dữ
liệu – cụ thể là học các đặc trưng của chất liệu. Hiện nay, công nghệ ưu việt
nhất vẫn công nghệ Mạng Nơron, hay các phương pháp học thống kê như mơ
hình Markov ẩn, mạng xác suất Bayes, v.v..

15


Chương 2 CÁC CÁCH TIẾP CẬN TRONG PHÁT HIỆN CHẤT LIỆU
Phần này trình bày một số phương pháp được sử dụng hiệu quả trong
cách tiếp cận để giải quyết bài tốn phát hiện chất liệu. Trong đó bao gồm
các kỹ thuật dựa vào các đặc trưng cơ bản của chất liệu và các cách tiếp cận
phát hiện chất liệu dựa trên mạng nơron, mơ hình xác suất Markov ẩn.

2.1 Phương pháp Habin cải tiến
Như chúng ta đã biết, biểu đồ màu là một trong những phương pháp để
đối sánh giữa hai chất liệu. Đã có hai cách tiếp cận truyền thống để phát hiện
chất liệu là biểu đồ màu toàn cục (Global Color Histogram - GCH) và biểu đồ
màu cục bộ (Local Color Histogram - LCH), song chúng cũng chính là điểm
khởi đầu cho phương pháp Habin. GCH chỉ đưa ra biểu đồ màu của ảnh mà
khơng có thơng tin khơng gian (thơng tin vùng), do vậy hiệu quả tìm kiếm
chắc chắn sẽ bị giới hạn. Ví dụ, trong hình 2.1, ảnh A và B có cùng biểu đồ
màu do đó khoảng cách giữa A và và B sẽ bằng 0. Tuy nhiên hai ảnh này là
khác nhau.

Hình 2.1. Hai ảnh và biểu đồ màu toàn cục của chúng.

16

 Chia ảnh thành các khối và tính biểu đồ màu cho từng khối
 Xây dựng đồ thị hai phía có trọng số
 Tìm kiếm giá trị đối sánh cực đại hoặc cực tiểu, khoảng cách giữa hai
ảnh sẽ là giá trị đối sánh nhỏ nhất.
Trong hình 2.3 là ví dụ chỉ rõ cách xây dựng đồ thị hai phía. Bước đầu
giống như bước đầu của phương pháp LCH. Trong việc xây dựng đồ thị hai
phía G(X,Y,E), mỗi khối sẽ tương ứng với một đỉnh. Trong ví dụ này một ảnh
sẽ chia làm bốn khối và như vậy đồ thị có hướng sẽ có tám đỉnh, mỗi khối
trong một ảnh sẽ được nối với các khối của ảnh kia.
Nếu trọng số của mỗi cạnh chỉ rõ khoảng cách giữa hai khối được nối
với nhau thì phương pháp này sẽ tìm kiếm giá trị đối sánh nhỏ nhất trên đồ thị
và xử lý giá trị này như khoảng cách giữa hai ảnh. Thực tế, sự tương tự giữa
các khối có thể được tính bằng cơng thức:
Sij=dmax-dij
Với dmax là khoảng cách lớn nhất giữa các khối, khối i và khối j thuộc hai
ảnh tương ứng, dij là khoảng cách giữa khối i và khối j. Sij là độ tương tự giữa
hai khối i và j.

18