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

NGUYẾN ĐỒNG SỸ NỘI SUY BỞI HÀM RBF VÀ ỨNG DỤNG
TRONG ĐỒ HỌA MÁY TÍNH LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS. TS. ĐẶNG QUANG Á
Thái Nguyên – 2010. Th¸i Nguyªn - 20
1

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
MỤC LỤC
MỞ ĐẦU 4
Chương 1
TỔNG QUAN VỀ NỘI SUY HÀM NHIỀU BIẾN 5
1.1. Khái niệm cơ bản về nội suy và xấp xỉ hàm số 5
1.1.1. Bài toán nội suy hàm số 5
1.1.2. Bản chất của phương pháp nội suy 7

BÀI TOÁN BIỂU DIỄN VÀ KHÔI PHỤC CÁC ĐỐI TƯỢNG 3D 24
3.1. Bài toán biểu diễn và khôi phục dữ liệu phân tán 24
3.1.1. Giới thiệu 24
3.1.2. Mô tả bài toán 25
3.2. Khôi phục đối tượng 3D từ tập điểm trên bề mặt sử dụng RBF 26
3.2.1. Trùng khớp tới dữ liệu bề mặt 3D 26
3.2.1.1. Tạo dữ liệu dày đặc từ các pháp tuyến bề mặt 27
3.2.1.2. Đảm bảo khoảng cách thích hợp tới dữ liệu bề mặt 28
3.2.1.3. Hợp lệ khoảng cách chiếu và nhiễu 30
3.2.2. Chuẩn hóa bề mặt 31
3.2.2.1. Các điểm hạt giống của bề mặt chuẩn 32
3.2.2.2. Tối ưu lưới 33
3.2.2.3. Bao biên 33
Chương 4
XÂY DỰNG VÀ CÀI ĐẶT THỬ NGHIỆM NỘI SUY BỞI RBF 35
4.1. Phân tích và xây dựng chương trình 35
4.1.1. Hàm tạo lập RBF 35
4.1.2. Hàm nội suy RBF 40
4.1.3. Một số file xây dựng chương trình 42
4.2. Kết quả thử nghiệm nội suy bởi RBF 59
KẾT LUẬN 63
HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI 63
TÀI LIỆU THAM KHẢO 64
PHỤ LỤC 66
1. Môi trường lập trình MATLAB 66
2. Các khả năng thực hiện của Matlab 66
3. Chế độ làm việc 67
4. Câu lệnh và biến 68
5. Hàm và tạo hàm 71
6. Các câu lệnh điều khiển của Matlab 72

Hình 3.11. Bề mặt đóng với biên dương. 34
Hình 3.12. Bề mặt đóng với biên âm. 34
Hình 4.1. Giao diện chương trình demo 59
Hình 4.2. Đồ thị so sánh hàm nội suy RBF và hàm interp1 59
Hình 4.3. Đồ thị biểu diễn một số dạng hàm cơ bản 60
Hình 4.4. Giao diện chức năng RBF 2D 60
Hình 4.5. Kết quả nội suy hàm z = x*exp(-x
2
-y
2
) 61
Hình 4.6. Nội suy đối tượng 3D với 2000 điểm 61
4

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 4.7. Kết quả xử lý dữ liệu trong cửa sổ lệnh 62
5

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên MỞ ĐẦU
Đồ họa máy tính ngày nay được ứng dụng rất rộng rãi trong nhiều lĩnh
vực khoa học, kĩ thuật, nghệ thuật điển hình như bài toán mô phỏng và chẩn
đoán hình ảnh, tái tạo hình ảnh, hỗ trợ thiết kế, đào tạo huấn luyện… Các
ứng dụng đồ họa rất đa dạng, phong phú và phát triển liên tục không ngừng.
Trong đồ họa máy tính bài toán khôi phục và biểu diễn các đối tượng
3D là một trong các bài toán cơ bản. Công cụ quan trọng để giải quyết bài

i) Cần phục hồi hàm số f(x) đối với mọi điểm x thuộc khoảng [a, b], khi
cho trước giá trị của hàm tại một số điểm. Các giá trị này thường là các
giá trị quan sát hoặc đo đạc được.
Xét ví dụ : Cho quan hệ hàm số y = f(x), dạng hàm là chưa biết nhưng
biết sự phụ thuộc của đại lượng y vào đại lượng x bằng phép đo thực nghiệm
theo bảng :
x
x
0
x
1
x
2
x
n
y
y
0
y
1
y
2
y
n

Xác định giá trị của y với x  x
i
(i = 1, ,n) trở thành bài toán nội suy.
Dựa vào bảng trên ta phải ước lượng đại lượng y ứng với đại lượng x khi x
không có trong bảng bằng phương pháp nội suy hay phương pháp xấp xỉ [1].

-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
Sau khi noi suy

Hình 1.2. Đồ thị biểu diễn tín hiệu sau khi nội suy.
8

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nội suy đa thức là việc xác định đa thức y = P(x) thỏa mãn điều kiện
nội suy P(x
k
) = y
k
với k = 0, ,n
ii) Khi hàm f(x) cho bởi công thức quá phức tạp đòi hỏi khối lượng tính
toán lớn và ta cần tính giá trị hàm f tại các điểm x thuộc [a, b] nào đó. Khi đó
người ta thường tính gần đúng f(x) tại một số điểm rồi xây dựng công thức
nội suy để tính các giá trị khác và làm tăng tốc độ tính toán.
iii) Ngoài ra nội suy hàm số còn được dùng để xây dựng các công thức
tính đạo hàm, tính tích phân số hoặc tìm nghiệm gần đúng của phương trình.
1.1.2. Bản chất của phương pháp nội suy

v = zeros(size(u));
for k = 1:n
w = ones(size(u));
for j = [1:k-1 k+1:n]
w = (u-x(j))./(x(k)-x(j)).*w;
end
v = v + w*y(k);
9

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên end
x = 0:pi/4:2*pi; y = cos(x); u = 0:pi/50:2*pi;
v = polyinterp(x,y,u);
plot(x,y,'',x,y,'-'),hold,plot(x,y,'o',u,v,'-');
hold off
Đồ thị minh họa :
0 1 2 3 4 5 6 7
-1
-0.8
-0.6
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1

- Đa thức lượng giác
- Hàm spline
1.2.2. Nội suy và xấp xỉ đa thức
Biết quan hệ y = f(x) bởi một số cặp giá trị (x
0
, y
0
), (x
1
, y
1
),… (x
n
, y
n
).
Ta chọn hàm nội suy là một đa thức bậc m = n
)()(
0
0
1
1
1
1
xaxaxaxaxPx
m
m
m
mm






0
1
1
1
1
10
1
11
1
111
00
1
01
1
010

(2)
Xác định đa thức nội suy bằng cách tìm các hệ số a
0
, a
1
, , a
m

m
n
m
n
m
n
mm
mm























1.2.3. Nội suy bởi hàm ghép trơn
Nội suy hàm số bởi đa thức là phương pháp xấp xỉ hàm số dựa vào giá
trị của hàm tại một số các điểm nút. Nếu muốn đạt độ chính xác cao cần phải
sử dụng nhiều nút nội suy, khi đó bậc của đa thức sẽ lớn. Điều này không
thuận tiện cho việc tính toán và sai số tính toán có thể tăng lên. Để khắc phục
11

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên nhược điểm trên người ta sử dụng các đa thức cấp thấp trên mỗi đoạn nhỏ và
ghép chúng lại với nhau sao cho kết quả là một hàm trơn tru. Hàm trơn trên
toàn đoạn lớn gọi là hàm ghép trơn (spline).
Ví dụ với hàm y = sin(x) + x
2
trên đoạn [0, 2], bước tăng 0.2; sử dụng
hàm nội suy spline bậc 3 trong môi trường MATLAB
xi=0:0.2:2;
yi=sin(xi)+xi.^2;
F1=inline('spline(xi,yi,x)','x','xi','yi');
plot(xi,yi,'r+-');
Kết quả :
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2
0
0.5
1
1.5
2
2.5
3

phải sử dụng phép nội suy 2 chiều.
Ví dụ minh họa sử dụng hàm nội suy interp2 trong MATLAB
[X,Y] = meshgrid(-3:.25:3); Z = peaks(X,Y);
[XI,YI] = meshgrid(-3:.125:3);
ZI = interp2(X,Y,Z,XI,YI);
mesh(X,Y,Z), hold, mesh(XI,YI,ZI+15); hold off
axis([-3 3 -3 3 -5 20])
-3
-2
-1
0
1
2
3
-2
0
2
-5
0
5
10
15
20
noi suy 2 chieu

Hình 1.5. Nội suy hàm hai chiều interp2.
13

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


2
3
noi suy 3 chieu

Hình 1.6. Nội suy hàm ba chiều interp3.
14

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chương 2
NỘI SUY BỞI HÀM RBF
2.1. Hàm cơ sở bán kính và các tính chất
Hàm cơ sở bán kính RBF được ứng dụng hiệu quả trong nhiều lĩnh vực
khác nhau, đặc biệt cho ứng dụng nội suy dữ liệu phân tán.
Hàm cơ sở bán kính (RBF) là hàm có dạng :




n
i
ii
xxxpxs
1
)()()(

(3)
Trong đó :
S là hàm cơ sở bán kính

với i = 1,…, n
Gọi quy trình tìm hàm nội suy s nói trên là sự trùng khớp (fitting), hàm
RBF trùng khớp được định nghĩa bởi các hệ số λ
i
của hàm cơ sở φ , các hệ số
của đa thức p trong hàm tổng s(x).
Nếu ta đặt {p
1
, , p
M
} là các đa thức cơ sở của không gian các đa thức
bậc ≤ M và c=(c
1
,…, c
M
)
T
là các hệ số theo cơ sở trên để biểu thị p(x) thì hàm
nội suy dạng s(x
i
) = f
i
có thể biểu thị bằng hệ phương trình tuyến tính :
15

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


||)(||,
21
11211
ijij
nnnn
n
xxa
aaa
aaa
A 

















nmn
c
c
c
f
f
f




111
,,Do đó có thể viết hệ phương trình trên dưới dạng ma trận :












||) với i, j = 1,…,n là ma trận nội suy
P
i,j
= p
j
(x
i
) với i, j = 1,…,n và j = 1,…,m
f = (f
1
,…,f
2
)
T

Giải hệ phương trình trên ta tính được hàm nội suy s(x).
16

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.2.2. Một số hàm cơ sở
Một số dạng hàm cơ sở thường được sử dụng :
Hàm cơ sở
2D
3D
Biharmonic spline

subplot(2,1,2); plot(x, y,'o', xi, fi,xi, sin(xi),'r'); title('noi suy RBF');
0 1 2 3 4 5 6 7 8 9 10
-1
-0.5
0
0.5
1
noi suy RBF

Hình 2.1. Nội suy một chiều RBF hàm y = sin(x).
17

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.2.3. Thành phần đa thức RBF
Thành phần đa thức của một RBF phụ thuộc vào hàm cơ sở đang được
sử dụng :
Trường hợp hàm cơ sở là spline song điều hòa (biharmonic spline) thì
thành phần đa thức là đa thức tuyến tính.
Trường hợp hàm cơ sở là spline tam điều hòa (triharmonic spline) hoặc
dạng bậc hai (multiquadric) thì thành phần đa thức là đa thức bậc hai.
Giả sử trong trường hợp 2 chiều thì cơ sở của không gian các đa thức
bậc hai là : 1, x, x
2
, y, y
2
, yx. Còn trong 3 chiều thì cơ sở sẽ là : 1, x, x
2
, y, y

*
(x
i
) = f
i
và cực
tiểu hóa tích phân của bình phương đạo hàm cấp 2 dạng :
s
*
= arg min||s||
trong đó :
||s||
2
=
dx
zy
xs
zx
xs
yx
xs
z
xs
y
xs
x
xs
R


































là một spline song điều hòa hoặc spline bản mỏng;
||s||
2là độ đo năng lượng của đạo hàm bậc hai của hàm s(x). Spline tam
điều hòa làm cực tiểu năng lượng tương ứng trong đạo hàm cấp ba của s(x),
các RBF này sẽ làm thay đổi độ trơn giữa các giá trị của các mốc nội suy.

18

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.3. Hạn chế của nội suy sử dụng RBF và giải pháp
2.3.1. Vấn đề dữ liệu lớn
Hàm nội suy RBF dạng s(x
i
) = f
i
có thể viết dưới dạng ma trận biểu thị
hệ phương trình tuyến tính :









trưng cực tiểu năng lượng rất đáng chú ý, là những công cụ nội suy trơn nhất.
Hệ phương trình trên không những đòi hỏi bộ nhớ tỉ lệ với N
2
và việc tính
toán để giải nó tỉ lệ với N
3
mà sự liên quan của hệ đó với việc đánh giá hàm
s(x) qua phương trình :



n
i
ii
xxxpxs
1
)()()(


còn tỉ lệ với N. Độ phức tạp đánh giá s(x) trở nên quan trọng khi N lớn và
s(x) được đánh giá trên một lưới mịn.

2.3.2. Dữ liệu có nhiễu
Khi sử dụng công cụ nội suy trơn nhất spline song điều hòa thì RBF có
thể không hiện ra tính trơn nếu như dữ liệu có nhiễu bởi vì nó bị thêm ràng
buộc phải nội suy giá trị nhiễu này.
Hình dưới đây được minh họa trong môi trường Matlab, tạo nhiễu bằng
cách chọn một hàm với cường độ nhiễu 0.5

19

)  f
i
. Do đó xuất hiện khái niệm độ chính xác trùng khớp (fitting
accuracy) kí hiệu m_fit, đó là giá trị sai lệch lớn nhất giữa các giá trị RBF và
các giá trị hàm f
i
cần nội suy tại các điểm x
i
đã cho.
m_fit = Max|s(x
i
– f
i
)| với i =0,…,N
Đối với mỗi điểm x
i
đã cho, việc tính giá trị RBF s(x
i
) được gọi là việc
đánh giá RBF (evaluating the RBF) tại điểm x
i
đó. Mặt khác vì các phương
pháp nội suy là xấp xỉ nhanh cho nên một giá trị đúng RBF tại các mốc
thường là không đạt được. Vì vậy nếu gọi a
i
là giá trị xấp xỉ của một RBF s tại
mốc x
i
thì độ chính xác đánh giá (evaluation accuracy) kí hiệu m_eval, được
định nghĩa là độ lệch lớn nhất giữa giá trị đúng RBF s tại x

N(N+1)/2
O(N)
Tính toán tỉ lệ
N
3
/6 + O(N
2
)
O(N log N)
Tỉ lệ đánh giá hàm
O(N)
O(1) + O(N log N)

22

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.4. Các phương pháp nhanh nội suy sử dụng RBF
2.4.1. Giảm tâm
Theo truyền thống, để nội suy các giá trị f
i
tại tập điểm x
i
thì tất cả các
điểm x
i

|<m_fit
23

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Việc giảm tâm làm tăng tốc độ sự trùng khớp và làm giảm thời gian
đánh giá mà không làm thay đổi độ chính xác. Do vậy phương pháp này chỉ
có thể thực hiện khi việc nội suy RBF có độ chính xác giới hạn. Phương pháp
giảm tâm phù hợp nhất đối với dữ liệu mà nó có các vùng dữ liệu đáng kể là
trơn so với mật độ lấy mẫu, nghĩa là dữ liệu được lấy mẫu khắp nơi liên quan
đến mức thể hiện chi tiết và độ chính xác được đặt ra.

2.4.2. Làm trơn dữ liệu nhiễu
a. Làm trơn spline (Spline Smoothing)
Làm trơn dữ liệu có thể đạt được trong một bộ lọc RBF bằng việc sửa
đổi tiêu chuẩn làm trơn thành việc tìm kiếm cực tiểu sau :
minimize









N
i
ii
















0
0
f
c
P
PIA
T


(6)
Ý nghĩa thông thường của tham số độ chính xác ε theo công thức :
|s(x
i
) – f
i