Ngày nay với sự phát triển mạnh mẽ của công nghệ thông tin, con người đã ứng dụng những thành tựu của nó trong rất nhiều lĩnh vực khác nhau. Máy tính đã trở thành một công cụ hỗ trợ đắc lực cho con người trong việc xử lý dữ liệu một cách nhanh chóng và chính xác.
Đồ họa máy tính là một lĩnh vực của khoa học máy tính nghiên cứu các phương pháp và kỹ thuật biểu diễn và thao tác các dữ liệu số hóa của các vật thể trong thực tế.
62 trang |
Chia sẻ: vietpd | Lượt xem: 1389 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Đề tài Hàm rbf và một số ứng dụng trong đồ họa máy tính, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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
NGƢỜI HƢỚNG DẪN KHOA HỌC
PGS.TS. Đặng Quang Á
Thái Nguyên 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
DANH MỤC CÁC TỪ VIẾT TẮT:
IMQ: Inverse Multi Quadric
MQ: Multi Quadric
RBF: Radian Basic Function
DANH MỤC BẢNG
Bảng 1.1: Sai số nội suy hàm Frank với = 3 11
Bảng 2.1 : So sánh phƣơng pháp trực tiếp và phƣơng pháp nhanh 26
Bảng 2.2: So sánh việc khớp hàm RBF và thời gian tính toán trên máy
tính PIII tốc độ 550MHz Ram 512
33
Bảng 2.3: So sánh yêu cầu lƣu trữ của việc nội suy bằng RBF và các
lƣới đƣợc suy ra
36
DANH MỤC HÌNH VẼ
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
Hình 3.2: Lƣới thu đƣợc sau khi đổi trật tự mảng giá trị và các đối số 43
Hình 3.3: Bề mặt đƣa vào 44
Hình 3.4: Bề mặt với các đƣờng pháp tuyến 45
Hình 3.5: Bề mặt với các đƣờng pháp tuyến có đô dài < 0,5mm bị loại
bỏ
46
Hình 3.6: Bề mặt sau khi khớp không có sự rút gọn tâm 48
Hình 3.7: Bề mặt sau khi khớp có sự rút gọn tâm 49
Hình 3.8: Tính giá trị bề mặt trên lƣới 3D 50
Hình 3.9: Lƣới mới đƣợc sinh ra 51
Hình 3.10: Lƣới đa giác đƣợc sinh ra 52
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 1
Chƣơng 1: KIẾN THỨC CHUẨN BỊ 3
1.1. Hàm cơ sở bán kính (RBF) 3
1.1.1. Nội suy dữ liệu rời rạc 3
1.1.2. Ma trận và hàm xác định dƣơng 5
1.1.3. Hàm cơ sở bán kính 6
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
3.5.1.2. Tính toán lƣới 3D 42
3.5.2. Khớp dữ liệu bề mặt 3D 43
3.5.2.1. Khớp bề mặt vào dữ liệu lƣới 43
3.5.2.2. Gia công đẳng mặt 51
3.6. Kết luận 53
KẾT LUẬN 54
1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
MỞ ĐẦU
Ngày nay với sự phát triển mạnh mẽ của công nghệ thông tin, con ngƣời
đã ứng dụng những thành tựu của nó trong rất nhiều lĩnh vực khác nhau. Máy
tính đã trở thành một công cụ hỗ trợ đắc lực cho con ngƣời trong việc xử lý
dữ liệu một cách nhanh chóng và chính xác.
Đồ họa máy tính là một lĩnh vực của khoa học máy tính nghiên cứu các
phƣơng pháp và kỹ thuật biểu diễn và thao tác các dữ liệu số hóa của các vật
thể trong thực tế. Lĩnh vực này đƣợc phát triển dựa trên nền tảng của hình học
họa hình, hình học tính toán, hình học vi phân cùng nhiều kiến thức toán học
của đại số và giải tích, cũng nhƣ các thành tựu của phần cứng máy tính.
Thuật ngữ "đồ họa máy tính" (computer graphics) đƣợc đề xuất bởi một
chuyên gia ngƣời Mỹ tên là William Fetter vào năm 1960. Khi đó ông đang
nghiên cứu xây dựng mô hình buồng lái máy bay cho hãng Boeing. William
Fetter đã dựa trên các hình ảnh 3 chiều của mô hình ngƣời phi công trong
buồng lái để xây dựng nên mô hình buồng lái tối ƣu cho máy bay Boeing.
Đây là phƣơng pháp nghiên cứu rất mới vào thời kỳ đó.
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 toán
này là lý thuyết nội suy hàm số nhiều biến. Để nội suy hàm số từ một tập
điểm đã biết thông thƣờng ngƣời ta sử dụng các hàm ghép trơn (spline) và
các biến dạng của nó. Từ khoảng hai chục năm nay ngƣời ta đã và đang phát
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Ị
Trong chƣơng này, chúng tôi trình bày các kiến thức cơ sở về hàm cơ sở
bán kính (RBF), bài toán khôi phục và biểu diễn các đối tƣợng 3D.
1.1. Hàm cơ sở bán kính (RBF):
1.1.1 Nội suy dữ liệu rời rạc:
Trong nhiều vấn đề khoa học kỹ thuật cần giải bài toán: Cho tập dữ
liệu (gồm các kết quả đo đạc và vị trí thu đƣợc những kết quả đó), yêu cầu
tìm một quy tắc cho phép suy diễn thông tin từ những kết quả đã có. Vì
vậy ta mong muốn tìm một hàm “đủ tốt” phù hợp với tập dữ liệu đã có. Có
nhiều cách để quyết định thế nào là tốt và một trong các tiêu chuẩn là
muốn hàm xấp xỉ có giá trị chính xác với những kết quả đo đạc đƣợc tại
những vị trí đã cho – Đáp ứng tiêu chuẩn này gọi là bài toán nội suy. Và
nếu những vị trí mà đã cho kết quả đo đạc không nằm trên một lƣới chuẩn
thì tiến trình trên gọi là nội suy dữ liệu rời rạc. Chính xác hơn ta có:
Bài toán 1.1 Cho tập dữ liệu
jj yx ,
,
nj ,...,1
với
jx
Rs,
jy
R. Tìm
một hàm (liên tục)
fP
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
fP
dƣới dạng
tổ hợp tuyến tính của hệ hàm cơ sở
n
kk
B
1
, nghĩa là:
n
k
kkf
xBcxP
1
, x Rs (1.2)
Từ đó, thay điều kiện (1.1) dẫn đến việc giải hệ phƣơng trình đại số
tuyến tính để xác định các hệ số
n
kk
c
1
:
yAc
(1.3)
Trong đó
jkjk xBA
;
nkj ,...,1,
;
Tnccc ,...,1
;
Tnyyy ,...,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 Rs, 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().
Gọi
nBBB ,...,, 21
là một cơ sở của B. Khi đó B được gọi là không gian
Haar trên nếu
0det A
với mọi tập các điểm phân biệt
nxxx ,...,, 21
.
Ở đây ma trận A là ma trận được xây dựng bởi
jkkj xBA ,
;
nkj ,...,1,
.
Sự tồn tại của không gian Haar đảm bảo tính khả nghịch của ma trận
nội suy, nghĩa là tồn tại duy nhất nghiệm của bài toán nội suy 1.1. Không
gian các đa thức một biến bậc
1n
chính là không gian Haar n chiều với
tập dữ liệu
jj yx ,
,
nj ,...,1
,
jx
R,
jy
R. Cơ sở chính tắc của không
gian này là
12321 ,...,,,1 nn 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
trong không gian nhiều chiều chúng ta không thể xây dựng trƣớc tập các
hàm cơ sở không phụ thuộc dữ liệu. Để giải quyết vấn đề không suy biến
của ma trận A, ta cần một phƣơng pháp khác để xây dựng hàm nội suy.
Thay vì sử dụng biểu diễn tuyến tính thông qua một hệ hàm cơ sở không
phụ thuộc dữ liệu, ta biểu diễn tuyến tính thông qua một hàm đơn phụ
thuộc dữ liệu đã cho, có tính khoảng cách, đối xứng với tâm nào đó của dữ
5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
liệu tƣơng ứng. Phƣơng pháp này đƣợc đề xuất bởi R.L Hardy năm 1971
và đƣợc gọi là phƣơng pháp hàm cở sở bán kính.
1.1.2 Ma trận và hàm xác định dƣơng:
Định nghĩa 1.2 Ma trận giá trị thực, đối xứng A được gọi là nửa xác định
dương nếu dạng toàn phương tương ứng là không âm:
n
j
n
k
jkkj Acc
1 1
0
(1.4)
với
Tnccc ,...,1
Rn. Nếu dấu bằng chỉ xảy ra khi và chỉ khi
Tc 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
kk
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 : Rs
R là xác định đương khi và chỉ khi
nó là hàm chẵn và thỏa mãn:
n
j
n
k
kjkj xxcc
1 1
0
(1.5)
với mọi n điểm đôi một khác nhau
nxx ,...,1
Rs và
Tnccc ,...,1
Rn.
Hàm
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
Tc 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
kjjkjk xxxBA
;
nkj ,...,1,
(1.7)
Tuy nhiên giải bài toán nội suy sẽ trở nên khó khăn trong không gian
nhiều chiều. Do đó, thay vì sử dụng hàm đa biến
x
(độ phức tạp sẽ tăng
lên theo số chiều), chỉ làm việc với hàm một biến cho tất cả số chiều s.
1.1.3 Hàm cơ sở bán kính:
Định nghĩa 1.4 Hàm : Rs R được gọi là hàm bán kính nếu tồn tại hàm
một biến : [0,+) R thỏa mãn:
rx
(1.8)
Với
xr
và
.
là một chuẩn nào đó trong Rs (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 0R
được gọi là đơn điệu hoàn toàn khi và
chỉ khi
01 tll
(1.9)
với mọi
,...,1,0l
với mọi t.
Việc xây dựng hàm bán kính xác định dƣơng thông qua hàm đơn điệu
hoàn toàn dựa vào kết quả sau, đƣợc đƣa ra bởi Schoenberg năm 1938.
Định lý 1.2 Cho : R+ R là hàm liên tục đơn điệu hoàn toàn. Khi đó
với mọi tập điểm hữu hạn phân biệt từng đôi một
nxxx ,...,, 21
Rs, hàm
bán kính
2rx
,
xr
là hàm xác định dương.
Ví dụ 1.1
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
có
thể sử dụng làm hàm cơ sở bán kính đảm bảo tính xác định dƣơng của ma
trận nội suy.
Tƣơng tự, hàm (t) = (t + 2) , , > 0 cũng là hàm đơn điệu hoàn
toàn. Hàm cơ sở bán kính (r) = (r2 + 2) , , > 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 (0) ≥ 0. Khi đó ma trận nội suy
không suy biến với (x) = (||x||) = (r2).
Trong trƣờng hợp tổng quát, nếu với giả thiết yếu hơn về tính đơn điệu
hoàn toàn của , nghĩa là (k), k ≥ 1 là hàm đơn điệu hoàn toàn thì cần các
điều kiện nào để sử dụng đƣợc (theo định nghĩa ma trận nội suy tƣơng
ứng không suy biến)?. Vấn đề này đã đƣợc Micchelli (1986) nghiên cứu và
đƣa ra những kết quả quan trọng về hàm xác định dƣơng có điều kiện.
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:
Định nghĩa 1.6 Hàm : Rs R được gọi là xác định dương có điều kiện
bậc m nếu
n
j 1
n
k 1
cjck(xj – xk) ≥ 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
cjp(xj) = 0, pP
1m
s
(đa thức thuộc không gian các đa thức s biến có bậc
m – 1). Nếu đẳng thức chỉ xảy ra với c = 0 thì gọi là xác định dương
chặt có điều kiện.
Điều quan trọng là có thể sử dụng hàm xác định dƣơng có điều kiện bậc
m để nội suy nếu ta cộng vào biểu thức (1.6) một đa thức đa biến bậc
1m
triệt tiêu trên tập dữ liệu đã cho. Cụ thể, hàm nội suy với độ chính
xác đa thức đƣợc cho dƣới dạng:
n
j
jj
n
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
..x
s
s
.
Khi thay điều kiện nội suy ta đƣợc hệ phƣơng trình Ac = y. Để xác định
hệ số của p(x) ta sử dụng các điều kiện
n
j 1
cjx
j
= 0, || < m (1.11)
Ví dụ 1.2
Xây dựng hàm nội suy trong không gian 2 chiều với tập dữ liệu cho
trƣớc {(xj,yj), f(xj,yj)}
n
j 1
, sử dụng hàm xác định dƣơng có điều kiện bậc 2 ta
đƣợc:
Pf(x,y) =
n
j 1
cj((x,y) – (xj,yj)) + 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
j
kkjjkkj yxfyxyxc
1
,,,
; k = 1, 2, …,n
9
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Để xác định các hệ số a1,a2,a3 sử dụng (1.11), đƣợc thêm ba điều kiện
sau:
n
j 1
cj = 0
n
j 1
cjxj = 0
n
j 1
cjyj = 0
Vậy ta đƣợc hệ n + 3 phƣơng trình n + 3 ẩn. Từ đó có thể tìm đƣợc Pf(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:
0TP
PA
.
d
c
=
0
y
(1.14)
Trong đó:
A =
n
jkjk
xx
1,
; P =
jx
, 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||) = (r2) là hàm
xác định dương chặt bậc k.
Ví dụ 1.3
1. Hàm (r) = (– 1) (r +
2
)
, > 0, > 0, N thỏa mãn:
kk rkr 21...11 . Vì vậy:
21...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
10
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
hoàn toàn. Vì vậy, hàm bán kính Multiquadric (MQ) tổng quát
221 rr là xác định dƣơng chặt có điều kiện bậc m, m ≥ .
2. Hàm (r)=(– 1) 2/ r
/2
, > 0, 2N thỏa mãn:
(k)(r)=(– 1) 2/ k
rk
21
2
...1
22
vì vậy (–1) 2/ 2/ (r) là
hàm đơn điệu hoàn toàn. Hơn nữa, với mọi m, m ≥
2/
hàm
rmm1
cũng là hàm đơn điệu hoàn toàn. Vì vậy, hàm Năng lượng
,1 2/ 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+1r2k 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 k của
(r) là: (l)(r) = (–1)k+1k(k – 1)…(k – l +1)rk-l lnr + pl(r), trong đó pl(r)
là đa thức bậc k – l. Vì vậy, đạo hàm cấp k sẽ là: (k)(r) = (–1)k+1k! lnr
+C, và đạo hàm cấp k + 1 là
r
k
r kk
!
)1()( 1)1( , là hàm đơn điệu hoàn
toàn trên (0, ). Do đó, hàm (r) = (–1)k+1r2k lnr =
2
1
(r2) 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
yx
ef
;
10
)19(
49
)19(
2
22
4
3
yx
ef
;
22 3979
4
1
3
2
1
yx
ef
;
22 7949
4
5
1 yxef
;
4321 fffff
;
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Cho trƣớc tập giá trị
jiij yxfz ,
; i, j = 1,…,n, trong đó (xi,yj) [0,1]
2
là
tập điểm nội suy. Để đơn giản, chúng tôi chọn tập điểm nội suy là lƣới đều
trên miền [0,1]2 và tập tâm trùng với tập điểm nội suy.
Xây dựng hàm nội suy Pj =
n
j 1
ck(||u - uk||). Trong đó uk = (x,y)Tập điểm
tâm, đƣợc chọn là hàm IMQ.
Cho thỏa mãn điều kiện nội suy ta đƣợc hệ n2 phƣơng trình, n2 ẩ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
- Sai số lớn nhất:
fPfP fjjf
nj
2,...,1
max
Bảng 1.1 Sai số nội suy hàm Frank với = 3
Lưới
IMQ MQ
Sai số tƣơng đối Sai số lớn nhất Sai số tƣơng đối Sai số lớn nhất
7 x 7 1.211536e-002 8.600572e-002 1.260168e-002 8.722025e-002
10 x 10 1.685702e-003 1.122684e-002 2.241647e-003 1.548224e-002
13 x 13 4.226489e-004 2.856954e-003 4.470312e-004 2.756763e-003
17 x 17 3.761833e-005 3.703740e-004 4.168475e-005 4.447710e-004
20 x 20 4.346574e-006 7.352464e-005 5.739650e-006 6.316986e-005
1.2. Bài toán khôi phục và biểu diễn các đối tượng 3D:
Ngày nay, nhờ sự phát triển nhƣ vũ bão của khoa học kỹ thuật – công
nghệ mà loài ngƣời đã có những bƣớc tiến lớn trong nhiều lĩnh vực khác
nhau. Và một trong số đó là vấn đề khôi phục và biểu diễn các đối tƣợng
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á