Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
Trần Đức Thụ HÀM RBF VÀ MỘT SỐ ỨNG DỤNG
TRONG ĐỒ HỌA MÁY TÍNH
Chuyên nghành: Khoa học máy tính
Mã số: 60.48.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Hình 2.1: Khớp hàm RBF và phục hồi lƣới bằng RBF
15
Hình 2.2: Mô tả các điểm ngoài bề mặt
18
Hình 2.3: Khôi phục một bàn tay
18
Hình 2.4: Mặt cắt qua các ngón tay
20
Hình 2.5: Phƣơng pháp điều chỉnh nhanh
25
Hình 2.6: Thuật toán tham lam cho việc khớp RBF
25
Hình 2.7: Rút gọn tâm
28
Hình 2.8: Xấp xỉ dữ liệu LIDAR
31
Hình 2.9: Mức làm trơn
31
Hình 2.10: Gia công đẳng mặt
32
Hình 2.11: Lấp lỗ và ngoại suy bề mặt
34
Hình 2.12: Biểu diễn các đối tƣợng phức tạp
35
Hình 2.13: Khôi phục hành tinh Eros
35
Hình 3.1: Dữ liệu 3D tải vào
40
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


1.1.4. Hàm xác định dƣơng và đơn điệu hoàn toàn 6
1.1.5. Nội suy với độ chính xác đa thức và hàm xác định dƣơng có điều
kiện
7
1.1.6. Ví dụ nội suy bằng RBF 10
1.2. Bài toán khôi phục và biểu diễn các đối tƣợng 3D 11

Chƣơng 2: NGHIÊN CỨU ỨNG DỤNG HÀM RBF VÀO CÁC
BÀI TOÁN KHÔI PHỤC VÀ BIỂU DIỄN CÁC ĐỐI TƢỢNG 3D
14
2.1. Các bề mặt ẩn 15
2.2. Khớp một hàm ẩn vào bề mặt 16
2.3. Nội suy hàm cơ sở bán kính 23
2.4. Các phƣơng pháp nhanh 26
2.5. Rút gọn tâm 27
2.6. Xấp xỉ dữ liệu nhiễu bằng RBF 29
2.7. Tính toán bề mặt 30
2.8. Các kết quả 32
2.9. Kết luận 37

Chƣơng 3: KHAI THÁC PHẦN MỀM FASTRBF 38
3.1. Phần mềm FastRBF làm gì 38
3.2. Ai có thể sử dụng phần mềm FastRBF 38
3.3. Những lợi ích của phần mềm FastRBF 38
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

3.4.Các ứng dụng 39
3.5. Các kết quả đạt đƣợc khi sử dụng phần mềm FastRBF 39
3.5.1. Khớp và tính toán dữ liệu 3D 39
3.5.1.1. Rút gọn tâm RBF 41

triển một kỹ thuật nội suy mới có độ chính xác cao. Đó là nội suy bởi hàm cơ
sở bán kính (radial basis functions) viết tắt là RBF. Phƣơng pháp nội suy này
đã đƣợc sử dụng trong nhiều lĩnh vực của CNTT nhƣ xử lý tín hiệu, xử lý ảnh
và lý thuyết điều khiển. Một số phần mềm về hàm RBF và các ứng dụng cũng
đã đƣợc phát triển.
Luận văn gồm có ba chƣơng:
2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Chƣơng 1: Trình bày một số kiến thức cơ bản về hàm RBF. Những tính
chất của hàm RBF đƣợc áp dụng cho bài toán nội suy dữ liệu rời rạc. Đây là
những kiến thức cơ sở rất quan trọng. Tìm hiểu về bài toán khôi phục và biểu
diễn các đối tƣợng 3D.
Chƣơng 2: Nghiên cứu ứng dụng hàm RBF vào bài toán khôi phục và biểu
diễn các đối tƣợng 3D
Chƣơng 3: Tiến hành khai thác phần mềm FASTRBF.

Em xin đƣợc bày tỏ lòng biết ơn đến thầy giáo PGS.TS. Đặng Quang
Á đã tận tình hƣớng dẫn em hoàn thành luận văn này. Em cũng xin chân
thành cảm ơn các thầy cô giáo, bạn bè, đồng nghiệp, Khoa Công nghệ
Thông tin – Đại học Thái Nguyên và Trƣờng Cao đẳng Công nghiệp Việt
Đức (Thái Nguyên) đã động viên, giúp đỡ em trong quá trình học tập và
nghiên cứu.

Thái Nguyên, ngày 30 tháng 10 năm 2009
TÁC GIẢ
3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Chƣơng 1: KIẾN THỨC CHUẨN BỊ

P
thỏa mãn:

 
jjf
yxP 
, j=1,…,n (1.1)
Ý tƣởng chung để giải quyết bài toán nội suy là tìm hàm
f
P
dƣới dạng
tổ hợp tuyến tính của hệ hàm cơ sở
 
n
k
k
B
1
, nghĩa là:

   



n
k
kkf
xBcxP
1
, x  R

n
yyy ,...,
1


4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Bài toán 1.1 sẽ đƣợc đặt đúng, nghĩa là tồn tại và duy nhất nghiệm, khi
và chỉ khi ma trận A không suy biến.
Trong trƣờng hợp một chiều, ta luôn xây dựng đƣợc đa thức nội suy
bậc n – 1 cho n điểm nội suy phân biệt tùy ý. Tuy nhiên khi s ≥ 2, ta có kết
quả phủ định sau:
Định lý 1.1 (Mairhuber-Curtis) Nếu



R
s
, s ≥ 2 chứa một điểm trong
thì trong

không tồn tại không gian Haar các hàm liên tục, trừ trường
hợp không gian một chiều.
Trong đó, không gian Haar đƣợc định nghĩa nhƣ sau:
Định nghĩa 1.1 Cho không gian hàm tuyến tính hữu hạn chiều B

C(

).

gian các đa thức một biến bậc
1n
chính là không gian Haar n chiều với
tập dữ liệu
 
jj
yx ,
,
nj ,...,1
,
j
x

 R,
j
y

 R. Cơ sở chính tắc của không
gian này là
 
12
321
,...,,,1


n
n
xBxBxBB
.
Định lý trên cho thấy, để giải quyết bài toán nội suy dữ liệu rời rạc

ccc ,...,
1

 R
n
. Nếu dấu bằng chỉ xảy ra khi và chỉ khi
 
T
c 0,...,0

thì ma trận A được gọi là xác định dương.
Tính chất quan trọng của ma trận xác định dƣơng là nó có tất cả các giá
trị riêng đều dƣơng và không suy biến.
Nếu hệ hàm cơ sở
 
n
k
k
B
1
trong khai triển (1.2) làm cho ma trận nội suy
xác định dƣơng thì bài toán nội suy đƣợc đặt đúng. Hàm xác định dƣơng
đƣợc định nghĩa nhƣ sau:
Định nghĩa 1.3 Hàm liên tục : R
s


R là xác định đương khi và chỉ khi
nó là hàm chẵn và thỏa mãn:



gọi là xác định dương chặt nếu dấu bằng của (1.5) xảy ra khi
và chỉ khi
 
T
c 0,...,0
.
Từ định nghĩa 1.3 và tính chất của ma trận xác định dƣơng ta thấy, có
thể sử dụng các hàm xác định dƣơng chặt
 
kk
xxB 
làm hệ hàm cơ sở,
và khi đó ta có:

   



n
k
kkf
xxcxP
1
(1.6)
Ma trận nội suy trở thành:
6
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
.
là một chuẩn nào đó trong R
s
(thường dùng chuẩn
Euclidean). Hàm

tương ứng gọi là hàm cơ sở bán kính. Ta nói hàm

là
xác định dương (chặt) khi và chỉ khi hàm  là xác định dương (chặt).
1.1.4 Hàm xác định dƣơng và đơn điệu hoàn toàn:
Trong phần này trình bày kết quả quan trọng xây dựng một số hàm bán
kính thỏa mãn tính khả nghịch của ma trận nội suy tƣơng ứng, dựa trên
tính chất của hàm đơn điệu hoàn toàn.
Định nghĩa 1.5 Hàm

C

 
0
R
được gọi là đơn điệu hoàn toàn khi và
chỉ khi
 
 
 
01  t
l
l


7
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Xét hàm

(t) = e
–

t
với

≥ 0. Ta có: (– 1)
l

(l)
(t) = (

)
l
e
–

t
> 0. Suy ra
hàm này là đơn điệu hoàn toàn. Do đó hàm Gaussian (GA)

(r)=e
–

r

> 0 đƣợc gọi là hàm
Inverse Multiquadric (IMQ)
Theo định nghĩa hàm đơn điệu hoàn toàn, ta có

(t) ≥ 0,


(t)  0, …
Tuy nhiên nếu có


đơn điệu hoàn toàn (


(t) ≥ 0,


(t)  0, …) ta vẫn có
thể sử dụng đƣợc hàm

đảm bảo ma trận không suy biến.
Định lý 1.3 Cho

 C

[0,+) là hàm thỏa mãn


đơn điệu hoàn
toàn, khác hằng số. Giả sử thêm rằng

j 1


n
k 1
c
j
c
k
(x
j
– x
k
) ≥ 0 c  R
n
thỏa mãn:
2
8
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên



n
j 1
c
j
p(x
j
) = 0, pP
1m

j
jjf
mxc
xpxxcxP
1
1
,0


(1.10)
với các ký hiệu đa chỉ số:   N
8
0
, || =


8
1i

i
, và x

= x
1
1

.x
2
2


, sử dụng hàm xác định dƣơng có điều kiện bậc 2 ta
đƣợc:
P
f
(x,y) =


n
j 1
c
j
((x,y) – (x
j
,y
j
)) + p(x,y), (1.12)
trong đó p(x,y) là đa thức hai biến bậc 1 triệt tiêu tại các điểm nội suy,
 
yaxaayxp
321
, 
(1.13)
Cho (1.12) thỏa điều kiện nội suy đƣợc hệ:
 
  
 



n

c
j
x
j
= 0



n
j 1
c
j
y
j
= 0
Vậy ta đƣợc hệ n + 3 phƣơng trình n + 3 ẩn. Từ đó có thể tìm đƣợc P
f
(x,y).
Trong trƣờng hợp tổng quát, bài toán (1.10) sẽ dẫn tới hệ đại số tuyến
tính sau:






0
T
P
PA


j
x
, j = 1, 2, …, n; d là ma trận các hệ số của p(x)
Việc xây dựng cấu trúc cụ thể của các hàm bán kính xác định dƣơng có
điều kiện (x) =

(r) dựa trên định lý:
Định lý 1.4 Cho

là hàm liên tục và thỏa mãn
 
 
k
k
k
dr
rd

1
, r  0 là hàm
đơn điệu hoàn toàn khác hằng số. Khi đó, hàm (x) =

(||x||) =

(r
2
) là hàm
xác định dương chặt bậc k.
Ví dụ 1.3


2
1...11
. Vì vậy:

 
 
 
   
 
 
 
 






2
1...11 rr
là hàm đơn điệu hoàn
toàn. Hơn nữa, với mọi m, m ≥
 

, (– 1)
m

(m)
(r) cũng là hàm đơn điệu


 2N thỏa mãn:


(k)
(r)=(– 1)
 
2/

k
rk















2
1
2
...1


rr 

> 0,

 2N là hàm xác định dƣơng chặt có điều kiện
bậc m,

m ≥
 
2/

.
3. Hàm Thin plates spline (TPS)

(r) = (– 1)
k+1
r
2k
lnr, k

N
Là các hàm xác định dƣơng chặt có điều kiện bậc m ≥ k+1. Thật
vậy: Xét hàm

(r) = (– 1)
k+1
(r)
k
lnr. Khi đó, đào hàm cấp l, l

1)1( 


, là hàm đơn điệu hoàn
toàn trên (0, ). Do đó, hàm

(r) = (–1)
k+1
r
2k
lnr =
2
1

(r
2
) là hàm xác
định dƣơng chặt có điều kiện bậc m ≥ k + 1.
1.1.6 Ví dụ nội suy bằng hàm RBF:
Cho hàm mẫu Franke nhƣ sau:
22
)29()29(
4
1
1
4
3




3979
4
1
3
2
1



yx
ef
;
   
 
22
7949
4
5
1


yx
ef
;
4321
fffff 
;
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


tâm,

đƣợc chọn là hàm IMQ.
Cho thỏa mãn điều kiện nội suy ta đƣợc hệ n
2
phƣơng trình, n
2
ẩn. Kết quả
trong một số lƣới đƣợc cho trong bảng 1.1, với các sai số đƣợc định nghĩa
nhƣ sau:
- Sai số tƣơng đối:
   
 
2
1
2
2
11
2
fP
n
fP
n
f
n
j
jjf




3D.
12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Khôi phục đối tƣợng 3D đã trở thành một nhu cầu cần thiết trong các
lĩnh vực khác nhau nhƣ: Tạo ảnh trong y học, các ứng dụng mỹ thuật, thiết
kế sản phẩm, tạo nguyên mẫu nhanh và trong các phạm vi khác. Việc tạo
mô hình 3D bằng phƣơng pháp thủ công tốn nhiều thời gian và do vậy chi
phí sẽ đắt đỏ. Vì lý do đó, các kỹ thuật đã và đang tiếp tục đƣợc nghiên
cứu, các kỹ thuật này cho phép khôi phục tự động các đối tƣợng 3D. Các
kỹ thuật này có thể chia thành 2 phƣơng pháp: phƣơng pháp chủ động và
phƣơng pháp bị động [25]. Nhƣợc điểm của các phƣơng pháp chủ động là
quá trình khôi phục có thể trở thành một công trình ngân sách cao. Vì lý
do đó, cách tiếp cận đƣợc giới thiệu thuộc về các phƣơng pháp bị động, nó
yêu cầu ít thiết bị hơn và có thể áp dụng một cách tổng quát hơn.
Các phƣơng pháp khôi phục các đối tƣợng 3D truyền thống không thực
hiện tốt ở hai hƣớng:
- Thứ nhất: Chúng không thể xử lý các trƣờng hợp có độ phức tạp cao
đƣợc tìm thấy trong tự nhiên (Ví dụ: các bộ phận của con ngƣời hay
các ảnh cực nhỏ của mô).
- Thứ hai: Chúng không đƣa dữ liệu bề mặt vào một định dạng làm cho
gọn và thích hợp để mô phỏng, hiển thị hoặc định vị
Có 5 trƣờng hợp khôi phục các đối tƣợng 3D [26]. Trƣờng hợp đầu tiên
là với các ảnh đƣợc chụp bằng máy ảnh không định cỡ, làm việc với loại
ảnh này có thể khôi phục lại đối tƣợng so sánh với các phép biến đổi ảnh
xạ. Hai là, khôi phục từ các máy ảnh định cỡ làm việc với loại ảnh này có
thể khôi phục lại đối tƣợng so sánh với các phép biến đổi đồng dạng. Ba
là, các thuộc tính đại số của các hàm đa tuyến tính và các lý tƣởng phát
sinh bởi chúng đƣợc nghiên cứu. Trƣờng hợp thứ tƣ sử dụng kỹ thuật khôi
phục Ơ-clít khi một số thông tin của các máy ảnh đƣợc đƣa ra. Trƣờng hợp

sự áp dụng lại lƣới. 15
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 2.1: (a) Khớp một hàm RBF vào một tập hợp các điểm dữ liệu tập trung
438.000 điểm. (b) Sự phục hồi lƣới tự động sử dụng hàm RBF song điều hòa.

2.1. Các bề mặt ẩn:
Bài toán khôi phục hoặc biểu diễn bề mặt có thể phát biểu nhƣ sau:
Bài toán 2.1. Cho n điểm phân biệt
  
n
i
iii
zyx
1
,,

trên một bề mặt M trong
không gian R
3
, tìm một bề mặt M’ là gần đúng hợp lý với M.
Phƣơng pháp của chúng ta là mô hình bề mặt ẩn bằng một hàm
),,( zyxf
.
Nếu một bề mặt M gồm có tất cả các điểm
),,( zyx

dƣơng chặt. Tuy nhiên, phƣơng pháp chỉ giới hạn mô hình các bề mặt mà
có thể biểu diễn rõ ràng nhƣ một hàm 2 biến. Trong luận văn này chúng tôi
chứng minh đƣợc rằng bằng cách sử dụng các phƣơng pháp nhanh, hàm
RBF có thể khớp các tập dữ liệu 3D gồm có hàng triệu điểm không có các
giới hạn trên cấu trúc liên kết bề mặt – loại tập dữ liệu cơ bản của các ứng
dụng công nghiệp.

2.2. Khớp một hàm ẩn vào một bề mặt
Ta muốn tìm một hàm f mà xác định không tƣờng minh một bề mặt M’
và thỏa mãn phƣơng trình
,,...,1,0),,( nizyxf
iii


với
 
n
i
ii
zyx
1
,,(

là các điểm nằm trên bề mặt. Để tránh trƣờng hợp nghiệm
tầm thƣờng mà f là 0 ở mọi nơi, các điểm ngoài bề mặt đƣợc bổ sung vào
dữ liệu vào và chúng đƣa ra các giá trị khác 0. Việc này mang đến một vấn
đề nội suy hữu ích hơn: Tìm hàm f nhƣ sau:
17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


minh họa trong hình 2.2.
Đẳng mặt
f(x) = 0
f(x) > 0
f(x) < 0
18
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 2.2: Một hàm khoảng cách điểm đƣợc xây dựng từ dữ liệu bề mặt bằng
việc định rõ các điểm ngoài bề mặt dọc theo các đƣờng pháp tuyến bề mặt.
Những điểm này có thể đƣợc định rõ ở mỗi phía của bề mặt hoặc không ở
phía nào cả.

Hình 2.3. Sự khôi phục của một bàn tay từ đám điểm có và không thông qua
các độ dài pháp tuyến

Kinh nghiệm cho thấy rằng tốt hơn hết là bổ sung tại một điểm dữ liệu
hai điểm ngoài bề mặt, mỗi điểm nằm trên một phía của bề mặt. Trong
hình 2.3 các điểm bề mặt nhận đƣợc từ việc quét laser của một bàn tay
đƣợc biểu thị bằng màu xanh. Các điểm ngoài bề mặt đƣợc mã hóa màu
theo khoảng cách của chúng xuất phát từ điểm đƣợc liên kết trên bề mặt
của chúng. Màu nóng (màu đỏ) mô tả các điểm dƣơng nằm ở bên ngoài bề
mặt trong khi màu lạnh (xanh) nằm ở bên trong. Có hai bài toán cần giải
Các điểm pháp tuyển ngoài bề mặt
Các điểm trên bề mặt
19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

quyết: xác định các đƣờng pháp tuyến bề mặt và định rõ khoảng cách hình

không đúng, cả về điểm và độ lớn. Trong hình 2.3(a) và (b) giá trị của các
khoảng cách ngoài bề mặt và hình chiếu động đã đảm bảo rằng các điểm
ngoài bề mặt sinh ra một miền khoảng cách nhất quán với dữ liệu bề mặt.
Hình 2.4 là một mặt cắt qua các ngón tay của bàn tay. Hình ảnh minh họa
cách hàm RBF xấp xỉ một hàm khoảng cách gần giống bề mặt của đối
tƣợng. Các đẳng đƣờng tại +1, 0 và -1 ở phần trên của hình và hình dáng
hàm tƣơng ứng bên dƣới, minh họa việc làm thế nào các điểm ngoài bề
mặt sinh ra một hàm với một đại lƣợng chênh lệch gần bằng 1 gần bề mặt.

Hình 2.4: Mặt cắt qua các ngón tay của một bàn tay đƣợc khôi phục từ tập điểm
tập trung trong hình 2.3. Đẳng đƣờng tƣơng ứng với +1, 0 và -1 đƣợc hiển thị
(trên đỉnh) cùng với một mặt cắt nghiêng của hàm cơ cở bán kính (bên dƣới) dọc
theo đƣờng thẳng xuất hiện.