ĐẠ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 Á
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Thái Nguyên 2009
DANH MỤC CÁC TỪ VIẾT TẮT:
IMQ: Inverse Multi Quadric
MQ: Multi Quadric
RBF: Radian Basic Function
11
DANH MỤC BẢNG
26
Bảng 1.1: Sai số nội suy hàm Frank với = 3
33
Bảng 2.1 : So sánh phƣơng pháp trực tiếp và phƣơng pháp nhanh
36
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
15
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 DANH MỤC HÌNH VẼ
18
Hình 2.1: Khớp hàm RBF và phục hồi lƣới bằng RBF
18
Hình 2.2: Mô tả các điểm ngoài bề mặt
20
Hình 2.3: Khôi phục một bàn tay
25
Hình 2.4: Mặt cắt qua các ngón tay
25
Hình 2.5: Phƣơng pháp điều chỉnh nhanh
28
Hình 2.6: Thuật toán tham lam cho việc khớp RBF
31
Hình 2.7: Rút gọn tâm
31
Hình 2.8: Xấp xỉ dữ liệu LIDAR
32
Hình 2.9: Mức làm trơn
34
Hình 2.10: Gia công đẳng mặt
35
Hình 2.11: Lấp lỗ và ngoại suy bề mặt
35
Hình 2.12: Biểu diễn các đối tƣợng phức tạp
40
Hình 2.13: Khôi phục hành tinh Eros
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hình 3.1: Dữ liệu 3D tải vào
43
44
Hình 3.2: Lƣới thu đƣợc sau khi đổi trật tự mảng giá trị và các đối số
45
Hình 3.3: Bề mặt đƣa vào
46
Hình 3.4: Bề mặt với các đƣờng pháp tuyến
48
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ỏ
49
Hình 3.6: Bề mặt sau khi khớp không có sự rút gọn tâm
50
Hình 3.7: Bề mặt sau khi khớp có sự rút gọn tâm
51
Hình 3.8: Tính giá trị bề mặt trên lƣới 3D
52
Hình 3.9: Lƣới mới đƣợc sinh ra
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hình 3.10: Lƣới đa giác đƣợc sinh ra
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
7
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
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 14
BÀI TOÁN KHÔI PHỤC VÀ BIỂU DIỄN CÁC ĐỐI TƢỢNG 3D
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3.3. Những lợi ích của phần mềm FastRBF 38
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
KẾT LUẬN 54
1
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Luận văn gồm có ba chƣơng:
2
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
TÁC GIẢ
3
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 , với Rs, R. Tìm
một hàm (liên tục) thỏa mãn:
, j=1,…,n (1.1)
Ý tƣởng chung để giải quyết bài toán nội suy là tìm hàm dƣới dạng
tổ hợp tuyến tính của hệ hàm cơ sở , nghĩa là:
(1.2) , x Rs
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ố
:
(1.3)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Trong đó ; ; ;
4
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 là một cơ sở của B. Khi đó B được gọi là không gian
Haar trên nếu với mọi tập các điểm phân biệt .
Ở đây ma trận A là ma trận được xây dựng bởi ; .
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 chính là không gian Haar n chiều với
R,
R. Cơ sở chính tắc của không
tập dữ liệu , ,
gian này là .
Đị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ụ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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
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:
(1.4)
với Rn. Nếu dấu bằng chỉ xảy ra khi và chỉ khi
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ở 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
R là xác định đương khi và chỉ khi đƣợc định nghĩa nhƣ sau: Định nghĩa 1.3 Hàm liên tục : Rs
nó là hàm chẵn và thỏa mãn:
(1.5)
với mọi n điểm đôi một khác nhau Rs và 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 .
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 làm hệ hàm cơ sở,
và khi đó ta có:
(1.6)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Ma trận nội suy trở thành:
6
; (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 (độ 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:
(1.8)
Với 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 gọi là đơn điệu hoàn toàn khi và
chỉ khi (1.9)
với mọi 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 Rs, hàm
bán kính , là hàm xác định dương.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Ví dụ 1.1
7
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
bậc m nếu cjck(xj – xk) ≥ 0 c Rn thỏa mãn:
8
cjp(xj) = 0, pP (đ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
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:
(1.10)
với các ký hiệu đa chỉ số: N , || = i, và x = x .x ..x .
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 (1.11) cjx = 0, || < m
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
, sử dụng hàm xác định dƣơng có điều kiện bậc 2 ta trƣớc {(xj,yj), f(xj,yj)}
đƣợc:
(1.12) Pf(x,y) = cj((x,y) – (xj,yj)) + p(x,y),
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,
(1.13)
Cho (1.12) thỏa điều kiện nội suy đƣợc hệ:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
; k = 1, 2, …,n
9
Để xác định các hệ số a1,a2,a3 sử dụng (1.11), đƣợc thêm ba điều kiện
sau:
cj = 0
cjxj = 0
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:
. = (1.14)
Trong đó:
A = ; P = , 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 , 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:
. Vì vậy:
là hàm đơn điệu hoàn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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
hoàn toàn. Vì vậy, hàm bán kính Multiquadric (MQ) tổng quát
là xác định dƣơng chặt có điều kiện bậc m, m ≥ .
2. Hàm (r)=(– 1) r/2, > 0, 2N thỏa mãn:
(k)(r)=(– 1) vì vậy (–1) (r) là
hàm đơn điệu hoàn toàn. Hơn nữa, với mọi m, m ≥ hàm
cũng là hàm đơn điệu hoàn toàn. Vì vậy, hàm Năng lượng
> 0, 2N là hàm xác định dƣơng chặt có điều kiện
bậc m, m ≥ .
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à , là hàm đơn điệu hoàn
toàn trên (0, ). Do đó, hàm (r) = (–1)k+1r2k lnr = (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:
; ;
; ;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
;
11
Cho trƣớc tập giá trị ; 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 = 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:
- Sai số lớn nhất:
Bảng 1.1 Sai số nội suy hàm Frank với = 3
IMQ
MQ
Lưới
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3D.
12
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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
13
cuối cùng là khôi phục một ảnh của một đối tƣợng hoặc bản vẽ nét đƣợc
biết tới là mảnh 2 chiều.
Nhƣ vậy có thể thấy rằng bài toán khôi phục và biểu diễn các đối tƣợng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3D là một bài toán có ý nghĩa rất lớn và quan trọng.
14
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 ta sử dụng hàm cơ sở bán kính đa điều hòa (RBFs) để khôi phục lại
các bề mặt nhẵn, đa tạp từ tập các điểm dữ liệu tập trung và phục hồi các lƣới
điểm không đầy đủ. Một bề mặt của đối tƣợng đƣợc định nghĩa hoàn toàn
giống nhƣ một tập hợp số 0 của một hàm cơ sở bán kính phù hợp với dữ liệu
bề mặt đã cho. Các phƣơng pháp nhanh cho việc khớp dữ liệu và tính giá trị
hàm RBF cho phép chúng ta mô hình các tập hợp dữ liệu lớn, bao gồm hàng
triệu các điểm bề mặt, bằng một hàm RBF đơn trƣớc một bài toán khó giải.
Một thuật toán tham lam trong quá trình khớp dữ liệu làm rút gọn số lƣợng
các tâm RBF yêu cầu để biểu diễn một bề mặt và các kết quả ở dạng nén đáng
kể và hơn nữa là thuận lợi cho tính toán. Đặc trƣng cực tiểu hóa năng lƣợng
của các hàm ghép trơn đa điều hòa dẫn đến nội suy trơn nhất. Đặc trƣng tỷ lệ
điều hòa này là đủ thích hợp để khôi phục các bề mặt từ dữ liệu mẫu không
đều. Các lỗ là sự khớp dữ liệu nhẵn và sự ngoại suy nhẵn các bề mặt. Chúng
ta sử dụng một phép xấp xỉ không nội suy khi dữ liệu là nhiễu. Sự biểu diễn
hàm thực ra mà nói là một mô hình đặc, có nghĩa là độ chênh lệch và chuẩn
bề mặt có thể đƣợc phân tích rõ ràng. Sự hỗ trợ này sinh ra các lƣới đều và
chúng ta thấy rằng sự biểu diễn RBF có các lợi ích cho việc rút gọn lƣới và
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
sự áp dụng lại lƣới.
15
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.
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
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:
trên một bề mặt M trong
Bài toán 2.1. Cho n điểm phân biệt
không gian R3, 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 .
Nếu một bề mặt M gồm có tất cả các điểm thỏa mãn phƣơng trình:
, (2.1)
thì chúng ta nói rằng hàm f xác định không tƣờng minh bề mặt M. Mô tả
các bề mặt ẩn với rất nhiều loại hàm là một kỹ thuật nổi tiếng [10].
Trong hình học kiến thiết vật thể (CSG) một mô hình ẩn đƣợc tạo thành từ
các hàm sơ cấp đơn giản nhờ sự kết hợp của các phép toán Boolean (phép
hợp, phép giao vv..) và các hàm trộn. Các kỹ thuật CSG thích hợp cho việc
thiết kế các đối tƣợng trong CAD hơn là phục hồi các đối tƣợng từ dữ liệu
mẫu. Các mặt đại số bậc thấp từng mẩu, đôi khi đƣợc xem nhƣ là các
miếng vá ẩn hoặc các tập nửa đại số, cũng có thể đƣợc sử dụng để định
nghĩa các bề mặt ẩn.
Chúng ta mong muốn mô hình đƣợc toàn bộ đối tƣợng với một hàm
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
đơn liên tục và khả vi. Sự mô tả hàm đơn có một số ƣu điểm thông qua các
16
bề mặt giới hạn từng mẩu và các miếng vá ẩn. Nó có thể tính toán ở mọi
nơi để sinh ra một lƣới đặc biệt, nghĩa là sự biểu diễn một bề mặt đa tạp có
thể đƣợc tính toán với cách giải mong muốn khi đƣợc yêu cầu. Hiếm khi,
các bề mặt mẫu không đều có thể mô tả một cách đơn giản và bài toán
tham số hóa bề mặt kết hợp với việc khớp từng mẩu các miếng vá hàm
ghép trơn bậc ba là nên tránh.
Carr et al. [11] sử dụng hàm cơ sở bán kính để khôi phục các bề mặt
hộp xƣơng sọ bằng việc nội soi 3D CT. Dữ liệu xung quanh các lỗ lớn
không đều trong hộp sọ đƣợc nội suy sử dụng hàm xác định dƣơng chặt
RBF. Tấm titan đƣợc đúc trong khuôn của bề mặt thích hợp để tạo thành
một hộp sọ giả. Tài liệu đó khai thác các đặc điểm nội suy và ngoại suy
của hàm RBF hợp lý nhƣ các đặc tính vật lý cơ bản của hàm xác định
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
với 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
đề nội suy hữu ích hơn: Tìm hàm f nhƣ sau:
17
(các điểm trên bề mặt),
Đẳng mặt
f(x) = 0
f(x) > 0
f(x) < 0
(các điểm ngoài bề mặt).
Điều này vẫn mang đến một bài toán tạo ra các điểm ngoài bề mặt
và giá trị di tƣơng ứng.
Một sự lựa chọn hiển nhiên cho hàm f là một hàm khoảng cách điểm,
với giá trị di đƣợc chọn là khoảng cách tới điểm gần nhất trên bề mặt. Các
điểm bên ngoài đối tƣợng đƣợc gán các giá trị dƣơng, trong khi các điểm
bên trong đƣợc gán giá trị âm. Theo Turk &O‟Brien những điểm ngoài bề
mặt đƣợc sinh ra bởi phần nhô ra dọc theo các đƣờng pháp tuyến bề mặt.
Các điểm ngoài bề mặt có thể đƣợc gán với mỗi mặt của bề mặt nhƣ đƣợc
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
minh họa trong hình 2.2.
Các điểm pháp tuyển ngoài bề mặt
Các điểm trên bề mặt
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ả.
18
các độ dài pháp tuyến
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
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ề
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
mặt trong khi màu lạnh (xanh) nằm ở bên trong. Có hai bài toán cần giải
19
quyết: xác định các đƣờng pháp tuyến bề mặt và định rõ khoảng cách hình
chiếu thích hợp.
Nếu ta có một lƣới không hoàn toàn, thì rất đơn giản để định nghĩa các
điểm ngoài bề mặt từ đó các đƣờng tiếp tuyến đƣợc bao hàm bởi sự liên
kết lƣới tại mỗi đỉnh. Trong trƣờng hợp điểm dữ liệu tập trung không có
trật tự, các đƣờng tiếp tuyến có thể đƣợc tính toán từ một vùng lân cận của
các điểm. Việc này cầu xác định cả phƣơng pháp tuyến và định rõ hƣớng
của pháp tuyến. Chúng ta xấp xỉ cục bộ điểm dữ liệu tập trung với một mặt
phẳng để tính toán phƣơng pháp tuyến và sử dụng tính tƣơng thích và/hoặc
thông tin bổ sung nhƣ vị trí máy quét để quyết định hƣớng của pháp tuyến.
Thông thƣờng, rất khó để dự đoán chắc chắn các pháp tuyến ở khắp nơi.
Tuy nhiên, không giống nhƣ các phƣơng pháp khác mà cũng dựa trên việc
tạo thành một hàm khoảng cách điểm, nó không quyết định để dự đoán các
đƣờng pháp tuyến ở mọi nơi. Nếu phƣơng pháp tuyến hoặc hƣớng là
không xác định tại một điểm đặc biệt thì chúng ta không đặt một pháp
tuyến tại điểm đó. Thay vào đó, chúng ta cho phép thực tế điểm dữ liệu là
một điểm 0 (nằm trên bề mặt) ràng buộc vào hàm trong vùng đó.
Đƣa ra một tập hợp các pháp tuyến bề mặt, phải thận trọng khi đƣa ra
các điểm ngoài bề mặt dọc theo các pháp tuyến để đảm bảo rằng chúng
không cắt các phần khác của bề mặt. Điểm chiếu là đƣợc vẽ ra do đó điểm
bề mặt gần nhất là điểm bề mặt sinh ra nó. Miễn là điều kiện ràng buộc
này thỏa mãn, bề mặt đƣợc xây dựng lại là tƣơng đối không nhạy với
khoảng cách hình chiếu. Hình 2.3(c) minh họa cho tác động của các điểm
ngoài bề mặt nhô ra các khoảng không thích hợp dọc theo các đƣờng pháp
tuyến. Các điểm ngoài bề mặt đã lựa chọn nằm cách một khoảng cố định
tính từ bề mặt. Bề mặt kết quả, với f bằng 0 bị biến dạng trong vùng lân
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
cận của các ngón tay ở chỗ mà các véc tơ pháp tuyến đối lập đã cắt nhau
20
và đã sinh ra các điểm ngoài bề mặt với giá trị khoảng cách tới bề mặt
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ề
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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.
21
2.3. Nội suy hàm cơ sở bán kính
Cho một tập các điểm bề mặt có giá trị bằng 0 và các điểm ngoài bề
mặt khác 0 bây giờ chúng ta có một bài toán nội suy dữ liệu tán xạ: chúng
ta muốn xấp xỉ hàm khoảng cách điểm f(x) bằng một hàm nội suy s(x). Bài
toán có thể đƣợc phát biểu nhƣ sau:
Bài toán 2.2. Cho một tập hợp các nút riêng biệt R3 và một tập
hợp các giá trị hàm R, tìm một hàm nội suy: R3 → R nhƣ sau:
(2.2)
Chú ý rằng chúng ta sử dụng ký hiệu cho các điểm x R3.
Hàm nội suy sẽ lựa chọn từ BL(2) (R3), không gian Beppo-Levi các hàm
suy rộng trên R3 với bình phƣơng đạo hàm cấp hai khả tích. Không gian
này là đủ lớn để có nhiều lời giải cho bài toán 2.2 và vì vậy chúng ta có thể
định nghĩa không gian affin của các phép nội suy:
S = {s i = 1,…,N} (2.3) BL(2) (R3) : s(xi) = fi,
Không gian BL(2) (R3) đƣợc trang bị bởi nửa chuẩn bất biến xoay định
nghĩa bởi
(2.4)
Nửa chuẩn này là một độ đo của năng lƣợng hoặc “độ nhẵn” của các
hàm: các hàm với nửa chuẩn nhỏ là nhẵn hơn so với các hàm có nửa chuẩn
lớn. Duchon [13] chứng tỏ rằng nội suy trơn nhất, nghĩa là:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
có dạng đơn giản
22
(2.5)
Với p là một đa thức tuyến tính, các hệ số là các số thực và | . | là quy tắc
Ơ cơ lít trên R3
Hàm này là một ví dụ đặc biệt của hàm RBF. Thông thƣờng, một hàm
RBF có dạng:
, (2.6)
với p là một đa thức bậc thấp và hàm cơ sở là một hàm giá trị thực trong
khoảng [0, ), thƣờng không bị chặn và chứng minh không chặt. Trong
tình huống này các điểm xi đƣợc xem nhƣ là các tâm của RBF.
Các lựa chọn phổ biến cho hàm cơ sở bao gồm hàm xác định dƣơng
chặt (cho việc khớp các hàm trơn hai biến), hàm Gauss
(chủ yếu cho các mạng thần kinh), và hàm đa bậc hai
(cho nhiều ứng dụng, trong việc khớp đặc biệt với dữ liệu
định vị). Với các hàm khớp dữ liệu 3 biến, lựa chọn tốt bao gồm hàm ghép
trơn song điều hòa ( tức là, phƣơng trình (2.5)) và tam điều hòa
( ).
Một lựa chọn tùy ý các hệ số trong phƣơng trình (2.5) sẽ sinh ra một
hàm s* không thuộc BL(2) (R3). Điều kiện BL(2) (R3) kéo theo tính trực
giao hay các điều kiện bổ sung
Thông thƣờng hơn, nếu đa thức trong phƣơng trình (2.6) là bậc m thì
điều kiện bổ sung đặt lên các hệ số là:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
, cho tất cả các đa thức q bậc cao nhất của m. (2.7)
23
Các điều kiện bổ sung này cùng với các điều kiện nội suy của phƣơng
trình (2.2) dẫn đến một hệ tuyến tính để tìm ra các hệ số định rõ hàm RBF.
Cho {p1,…,pl} là một cơ sở các đa thực bậc cao nhất là m và cho
là các hệ số tạo lên p trong cơ sở này. Thì phƣơng trình (2.2)
và (2.7) có thể viết dƣới dạng ma trận nhƣ sau:
, (2.8)
với
Trong trƣờng hợp cụ thể của hàm ghép trơn song điều hòa trong không
gian 3D, nếu giả thiết rằng phần đa thức của hàm RBF trong phƣơng trình
, thì (2.5) có dạng
P là ma trận với dòng thứ i và
Giải hệ tuyến tính (2.8) xác định đƣợc và c, và từ đó xác định s(x).
Tuy nhiên, ma trận B trong phƣơng trình (2.8) có các điều kiện không
đáng kể nhƣ số lƣợng các điểm dữ liệu N nhận đƣợc lớn hơn. Những điều
này có nghĩa là những lỗi chính yếu nhất sẽ dễ dàng đƣa vào lời giải chuẩn
nào.
Thoạt nhìn, bản chất địa phƣơng cơ bản của hàm Gauss, hàm đa bình
phƣơng ngƣợc và các hàm cơ sở tựa chặt dƣờng nhƣ dẫn
đến các đặc tính mong muốn trong hàm RBF. Ví dụ ma trận B có cấu trúc
đặc biệt (rải rác) có thể khai thác bởi các phƣơng pháp nổi tiếng và sự tính
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
toán của phƣơng trình (2.6) chỉ yêu cầu phép tổng qua các tâm xung quanh
24
thay cho tất cả các tâm N. Tuy nhiên, các hàm cơ sở tựa không chặt là phù
hợp hơn với phép ngoại suy và phép nội suy không đều, dữ liệu lấy mẫu
không cùng kiểu. Thật vậy, các thử nghiệm số sử dụng hàm Gauss và các
đa thức từng mẩu tựa chặt cho việc khớp các bề mặt vào các điểm tập
trung đã cho thấy rằng những hàm cơ sở này sinh ra các bề mặt với nhiều
thành phần lạ không mong muốn tại phần thêm vào chỗ thiếu của phép
ngoại suy ngang qua các lỗ.
Các thuộc tính tối giản năng lƣợng của hàm ghép trơn song điều hòa
giúp chúng rất phù hợp để biểu diễn các đối tƣợng 3D. Từ đó hàm cơ sở
tƣơng ứng không tựa chặt và trở lên lớn tùy ý khi r dần tới vô cực,
ma trận tƣơng ứng B của phƣơng trình (2.8) không bị thƣa và trừ cấu trúc
cân đối, không có cấu trúc rõ ràng nào có thể khai thác trong việc giải hệ.
Lƣu trữ tam giác dƣới của ma trận B đòi hỏi khoảng trống cho
số thực. Cách giải quyết thông qua một giải pháp đối xứng sẽ đòi hỏi
chỗ lƣu trữ. Đối với một bài toán với 20.000 điểm dữ liệu đây là
một yêu cầu với xấp xỉ bytes (1.5GB) bộ nhớ lõi là không thực tế.
Hơn nữa, điều kiện không đúng của ma trận B có thể tạo ra bất kỳ kết quả
nào một trong số đó lấy từ một phép tính trực tiếp không đáng tin cậy lắm.
Nhƣ vậy, rõ ràng các phƣơng pháp trực tiếp không thích hợp cho các bài
toán với . Hơn nữa, một phép tính đơn trực tiếp của phƣơng trình
(2.6) cần đến các phép tính O(N). Các hệ số này đã dẫn đến nhiều tác giả
kết luận rằng, cho dù hàm cơ sở bán kính thƣờng là phép nội suy đƣợc lựa
chọn, chúng chỉ phù hợp cho những bài toán với nhiều nhất vài ngàn điểm
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
[14,15].
25
Độ chính xác điều chỉnh
+ các nút nội suy - - - - độ chính xác tính toán
khớp bằng RBF
…… bề mặt đƣa ra
. các điểm tính toán đƣa ra
Hình 2.5 : Hình minh họa của phƣơng pháp điều chỉnh nhanh và các giá trị
tính toán
điểm tập trung dẫn đến các tâm ít hơn trong hàm cuối cùng. Trong trƣờng hợp
này 544.000 điểm tập trung đƣợc biểu diễn bởi 80.000 tâm tới một độ chính xác tƣơng đối 5x10-4 trong hình ảnh cuối cùng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hình 2.6 : Một thuật toán tham lam lặp lại việc khớp một hàm RBF vào một tập
26
Bảng 2.1 : So sánh phƣơng pháp trực tiếp và phƣơng pháp nhanh
Phƣơng pháp trực tiếp
Phƣơng pháp nhanh
Khớp dữ liệu
Đòi hỏi bộ nhớ
O(N)
Khối lƣợng tính toán giải hệ
O(NlogN)
Tính giá trị
O(1)
Khối lƣợng tính toán
O(N)
O(NlogN)
2.4. Các phương pháp nhanh:
Sự tính toán nhanh của hàm RBF đƣợc thực hiện thông qua phƣơng
pháp đa cực nhanh (FMM) của Greengard & Rokhlin [27]. Phƣơng pháp
FMM đƣợc thiết kế cho các khả năng tính toán nhanh (hàm RBF điều hòa)
trong không gian 2 và 3 chiều. Tuy nhiên Beatson et al. [8] đã sửa lại phần
lý thuyết mở rộng và tịnh tiến cho khả năng hàm RBF đa điều hòa bậc cao
hơn. Chú ý rằng hàm RBF đa điều hòa bao gồm các hàm ghép trơn điều
hòa của phƣơng trình (2.5). Phƣơng pháp FMM cũng có thể sử dụng với
hàm ghép trơn đa điều hòa trong không gian 2 và 3 chiều.
Sự mô tả đầy đủ về phƣơng pháp FMM là vƣợt qua phạm vi của luận
văn này. Tuy nhiên, chúng ta đƣa ra những nét chính ngắn gọn của phƣơng
pháp này.
Phƣơng pháp FMM dùng thực tế đơn giản là khi quá trình tính toán
đƣợc thực hiện, độ chính xác vô hạn không là yêu cầu mà cũng không là
sự kỳ vọng. Đôi khi điều này là đúng, việc dùng phép xấp xỉ là đƣợc phép.
Với sự tính toán một hàm RBF, phép xấp xỉ một lựa chọn là sự mở rộng
phạm vi xa và gần. Với các tâm gộp lại trong một phƣơng pháp phân cấp,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
sự mở rộng phạm vi xa và gần đƣợc sử dụng để sinh ra một phép xấp xỉ tới
27
phần đó của hàm RBF nhờ các tâm trong một đám đặc biệt. Một cách sử
dụng đúng đắn phép tính xấp xỉ cho các đám cách xa từ một điểm tính toán
cho phép hàm RBF có thể tính toán độ chính xác định trƣớc và phép tính
trực tiếp cho các đám ở gần tới một điểm tính toán cho phép hàm RBF tính
toán tới bất kỳ độ chính xác biết trƣớc nào và với sự giảm đáng kể thời
gian tính toán so với tính toán trực tiếp.
Các phƣơng pháp tính toán nhanh này, khi sử dụng cùng với các
phƣơng pháp khớp dữ liệu đặc biệt cho hàm RBF [3,7], làm giảm rất nhiều
dung lƣợng lƣu trữ và chi phí tính toán cho việc sử dụng hàm RBF. Chúng
giảm chi phí tính toán hàm s(x) với M điểm từ O(MN) tới O(M+NlogN)
phép tính. Chi phí của việc tính toán đồng thời độ chênh lệch với
hàm s(x) là xấp xỉ bằng hai lần việc tính toán riêng hàm s(x). Bảng 2.1 tóm
tắt các lợi ích của các phƣơng pháp nhanh so với các phƣơng pháp trực
tiếp.
Hình 2.5 minh họa hai tham số đƣợc giới thiệu bởi các phƣơng pháp
nhanh: độ chính xác khớp dữ liệu và độ chính xác tính toán. Độ chính xác
khớp dữ liệu chỉ rõ độ lệch cho phép tối đa của giá trị khớp RBF từ giá trị
đã đƣợc ghi rõ tại các nút nội suy. Nếu muốn, một độ chính xác khớp dữ
liệu khác có thể đƣợc ghi rõ ở mỗi điểm dữ liệu, nhƣ đƣợc minh họa bằng
các dải sai số khác nhau trong hình 2.5. Độ chính xác tính toán chỉ rõ sự
chính xác với những gì mà hàm khớp dữ liệu RBF sau đó đƣợc tính toán.
2.5. Rút gọn tâm RBF
Nhƣ quy ƣớc, một phép xấp xỉ sử dụng cho tất cả các điểm dữ liệu vào
(của biến xi‟ trong phƣơng trình (2.2)) nhƣ các nút của phép nội suy và
nhƣ là các tâm của hàm RBF. Tuy nhiên, dữ liệu vào cùng loại có thể xấp
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
xỉ tới độ chính xác mong muốn sử dụng các tâm ít hơn đáng kể, nhƣ đƣợc
28
minh họa trong hình 2.7. Một thuật toán tham lam có thể vì thế mà đƣợc
sử dụng để khớp lại một hàm RBF trong phạm vi độ chính xác khớp dữ
Các tâm RBF
Tập con rút gọn của các tâm RBF
Hình 2.7: Minh họa sự rút gọn tâm.
liệu mong muốn.
Một thuật toán tham lam đơn giản gồm những bƣớc sau :
1. Chọn một tập con từ các nút nội suy xi và khớp chỉ một hàm RBF cho
những nút này.
2. Tính toán phần dƣ, , tại tất cả các nút.
3. Nếu < độ chính xác khớp dữ liệu thì dừng lại.
4. Còn không thì thêm các tâm mới với lớn.
5. Khớp lại hàm RBf và quay lên bƣớc 2.
Nếu một độ chính xác khác đƣợc ghi rõ tại mỗi điểm thì điều kiện
tại bƣớc 3 có thể đƣợc thay bằng < .
Việc rút gọn tâm không cần thiết khi sử dụng các phƣơng pháp nhanh
đƣợc mô tả trong phần 2.4. Ví dụ, không có sự rút gọn nào đƣợc sử dụng
khi khớp dữ liệu cho ví dụ LIDAR của hình 2.8. Tuy nhiên, rút gọn số
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
lƣợng các tâm RBF dẫn đến các yêu cầu bộ nhớ nhỏ hơn và thời gian tính
29
toán nhanh hơn, không bị mất mát độ chính xác. Hình 2.6 minh họa quá
trình khớp dữ liệu với sự rút gọn tâm. Giống nhƣ nhiều tâm bổ sung vào
hàm RBF, bề mặt số 0 xấp xỉ gần hơn tập hợp toàn vẹn các điểm dữ liệu.
Trong trƣờng hợp này, sự quét laser của một tƣợng phật bao gồm 544.000
điểm đã đƣợc xấp xỉ bằng một hàm RBF với 80.000 tâm tới một độ chính xác tƣơng đối 1.4 x 10-4 (đạt đƣợc tại tất cả các điểm dữ liệu).
Thuật toán tham lam thƣờng dẫn đến một lƣới với thời gian khớp dữ
liệu nhanh hơn, thậm chí là với sự rút gọn vừa phải số lƣợng tâm. Điều này
là do các khả năng khớp dữ liệu với việc giải và tính toán một hệ tƣơng tự
tại mỗi lần lặp và sự thật là quá trình lặp ban đầu bao gồm việc giải các bài
toán nhỏ hơn nhiều.
2.6. Xấp xỉ dữ liệu nhiễu bằng RBF:
Trong phần 2.3 chúng ta tìm kiếm một phép nội suy mà tối giản một
bƣớc của việc làm trơn. Tuy nhiên, nếu có nhiễu trong dữ liệu, các điều
kiện nội suy của phƣơng trình (2.2) là quá chặt chẽ và chúng ta sẽ thích
đánh giá hơn tập là trung vào việc tìm một hàm làm trơn, với độ trơn đƣợc
đo bởi phƣơng trình (2.4). Nhƣ vậy, coi bài toán
, (2.9)
với và là đƣợc xác định trong phƣơng trình (2.4). Tham số làm
cân bằng độ mƣợt dựa vào độ chính xác tới dữ liệu. Nó có thể cho thấy
rằng lời giải s* cho bài toán này cũng có dạng của phƣơng trình (2.5)
nhƣng lúc này hệ số véc tơ là lời giải tới
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
, (2.10)
30
với ma trận A và P giống nhƣ trong phƣơng trình (2.8). Tham số có thể
coi nhƣ là độ cứng của hàm RBF s(x). Hệ (2.10) cũng có thể giải quyết
bằng việc sử dụng phƣơng pháp nhanh.
2.7. Tính toán bề mặt
Một hàm RBF khớp một tập dữ liệu bề mặt tạo thành một mô hình vật
thể của một đối tƣợng. Bề mặt của các đối tƣợng là nơi các điểm với hàm
RBF bằng 0. Bề mặt này có thể hiển thị trực tiếp bằng việc sử dụng một
mũi vạch tia ẩn [11] hoặc một biểu diễn trung gian rõ ràng, nhƣ là một lƣới
của đa giác, có thể tách ra đƣợc.
Một hệ thống tối ƣu lƣới đƣợc đƣa vào dẫn đến ít tam giác hơn với các
khuôn dạng tốt hơn, tức là các tam giác mỏng và dài đƣợc ngăn ngừa. Một
lƣới tiêu biểu đƣa ra từ thuật toán này đƣợc minh họa trong hình 2.10(b).
Các mặt sóng của các mặt trải ra từ các điểm hạt băng qua bề mặt cho đến
khi chúng gặp nhau hoặc cắt hộp giới hạn. Rõ ràng, một mặt sóng từ một
hạt đơn lẻ hiện ra màu đỏ trong hình 2.10(a) lan rộng trên bề mặt bức
tƣợng phật trong quá trình tạo bề mặt đồng nhất. Bề mặt kế tiếp đƣợc bắt
đầu từ các điểm hạt đúng với các tâm hàm RBF. Ý đồ là nhiều tâm sẽ nằm
trên bề mặt hoặc rất gần bề mặt. Trong trƣờng hợp các tâm ngoài bề mặt,
độ chênh lệch RBF dùng để tìm chỗ giao 0 gần nhất. Sự hội tụ là nhanh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
chóng vì độ chênh lệch là hằng số xấp xỉ gần bề mặt.
(a)
(b)
(c)
Hình 2.8 : Xấp xỉ RBF của dữ liệu LIDAR. (a) 350.000 điểm tập trung, (b) Bề
mặt làm trơn RBF xấp xỉ dữ liệu tập trung gốc
(c)
(a)
(b) Hình 2.9 : (a) khớp chính xác, (b) số lƣợng trung bình của việc áp dụng làm trơn
(hàm RBF xấp xỉ tại các điểm dữ liệu), (c) sự làm trơn tăng lên
31
Trong bất kỳ trƣờng hợp nào, chỉ một tập con nhỏ của các tâm là đƣợc
yêu cầu để khởi đầu bề mặt, một tâm cho mỗi phần bề mặt phân biệt.
Chiến lƣợc bề mặt tiếp theo ngăn ngừa các yêu cầu thông thƣờng cho một
mảng 3 chiều của các điểm mẫu và vì thế giảm thiểu số lƣợng tính toán
RBF. Do đó, đòi hỏi tính toán tăng lên với bình phƣơng độ chính xác, hơn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
là lũy thừa ba, nhƣ nó muốn nếu một số lƣợng đầy đủ là đƣợc làm mẫu.
32
Chi phí bộ nhớ cũng giảm thiểu bởi nó chỉ cần để giữ lại đỉnh lấy mẫu kết
hợp với các mặt sóng cải tiến. Các lƣới tứ giác cũng có thể đƣợc sinh ra
trong cách này. Sự nhập nhằng bề mặt có thể đƣợc giải quyết lại dễ dàng
vì khả năng tính toán theo phép phân tích độ chênh lệch của hàm RBF.
2.8. Các kết quả :
Bảng 2.2 xác định lƣợng thời gian khớp dữ liệu và tính toán cho các
hình đƣợc đƣa ra trong luận văn này. Trong tất cả các trƣờng hợp hàm
ghép trơn song điều hòa đã khớp dữ liệu. Hai điểm ngoài bề mặt đƣợc sinh
ra cho mọi điểm thứ hai trong dữ liệu bề mặt gốc, do đó số lƣợng các nút
nội suy tới cái mà một hàm RBF đƣợc khớp là xấp xỉ hai lần số lƣợng các
điểm bề mặt. Sự rút gọn tâm đƣợc sử dụng ở khắp nơi, trừ trong mẫu
LIDAR nơi mà số lƣợng các tâm hàm RBF xấp xỉ bằng số lƣợng nút nội
suy. Hình 2.1(a), 2.3, 2.6, 2.12, 2.13 và 2.14 minh họa việc khớp dữ liệu
các bề mặt tới các điểm tập trung trong khi hình 2.1(b) và 2.11 minh họa
việc khớp với các lƣới riêng. Hình 2.8 giải thích việc xấp xỉ một hàm RBF
(a)
(b)
Hình 2.10 : Gia công đẳng mặt một hàm RBF. (a) Bề mặt tiếp theo từ một hạt
đơn giản, (b) ví dụ của một lƣới tối ƣu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
trong tinh huống khớp một bề mặt nhẵn với dữ liệu LIDAR nhiễu.
33
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 MB
Hình
Số lƣợng tâm RBF
RAM tối đa (MB)
Thời gian khớp
Thời gian chỉnh bề mặt
3.564 4.299 72.461
29 29 306
68s 97s 2:51:09
27s 32s 0:04:40
331.135 662.269
83.293
187
3:09:06
0:06:41
Độ chính xác liên quan 7 x 10-4 1 x 10-3 8 x 10-4 4 x 10-4
327.323 654.645
85.468
188
3:08:44
0:04:04
3 x 10-4
6 x 10-3
345.910 518.864 518.864
390
3:08:21
0:25:39
Số lƣợng Số lƣợng nút nội điểm bề suy mặt 29.074 14.806 Bề mặt Bàn tay 26.696 13.348 Con rồng 437.645 872.487 Tƣợng đứa trẻ Xƣơng bàn tay Tƣợng LIDAR
Con rồng trong hình 2.1(a), tƣợng phật (hình 2.6) và bộ xƣơng tay
(hình 2.12) chứng minh khả năng của các phƣơng pháp nhanh để mô hình
hóa các tập dữ liệu phức tạp lớn với độ chính xác cao và đặc tính nén của
việc biểu diễn hàm RBF. Dữ liệu của con rồng đƣợc lấy từ một lƣới bao
gồm 438.000 đỉnh và 871.000 mặt, của tƣợng phật đƣợc lấy từ 544.000
đỉnh và 1.087.000 mặt. Các đƣờng pháp tuyến đƣợc tính tại các đỉnh từ các
mặt liền kề. Các phƣơng pháp trực tiếp chắc chắn sẽ không có khả năng
trên các bài toán này. Ví dụ, một phƣơng pháp trực tiếp để khớp dữ liệu
tƣợng phật có thể yêu cầu 4.700GB bộ nhớ chỉ để lƣu trữ ma trận hệ nội
suy (2.8). Các yêu cầu bộ nhớ lõi tối đa của các phƣơng pháp nhanh mới
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
trong bảng 2.2 là đặc biệt đáng chú ý trong khía cạnh này.
Hình 2.11 : Một hàm RBF đã tự động lấp những lỗ nhỏ và ngoại suy qua các
vùng bít kín trong dữ liệu quét (bên trái), để tạo ra một mô hình kín, không rỉ
nƣớc. Cấu trúc liên kết phức tạp của bức tƣợng đã đƣợc bảo tồn.
34
Hình 2.1(b) và hình 2.11 minh họa ứng dụng việc khớp dữ liệu của hàm
RBF với sụ phục hồi lƣới. Trong hình 2.1(b) một hàm RBF khớp một lƣới
không hoàn toàn thu đƣợc từ một máy quét laser. Hình ảnh này chứng
minh khả năng của hàm ghép trơn song điều hòa với phép nội suy nhẵn
qua các lỗ không đều lớn, ví dụ dƣới cằm và ngoại suy nhẵn một bề mặt
không dữ liệu. Trong hình 2.11 một hàm RBF đã đƣợc khớp vào một tập
hợp dữ liệu pho tƣợng lớn. Dù quét cẩn thận, bức tƣợng vẫn chứa nhiều lỗ
nhỏ và lỗ lớn tƣơng ứng với các vùng bị che khuất giữa các hinh ôm. Việc
khớp hàm RBF đã tự động lấp tất cả các lỗ và sinh ra một mô hình không
rỉ nƣớc của bức tƣợng không cần ngƣời dùng phải chỉ rõ bất kỳ tham số
nào khác với độ chính xác khớp dữ liệu muốn có. Chú ý làm thể nào mà
mảnh vỡ của dữ liệu vai bên phải bức tƣợng nhỏ đã đƣợc ngoại suy để
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
khôi phục dữ liệu ngực bị thiếu.
Hình 2.12 : Với việc lấy mẫu đủ, các đối tƣợng phức tạp có thể biểu biễn với
hàm RBF.
Hình 2.13 : Sự khôi phục RBF của hành tinh Eros từ dữ liệu phạm vi phân bố
không đều (trên). Ảnh và môt hình từ một hình vẽ tƣơng tự.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
35
36
Hình 2.13 minh họa sự khôi phục hành tinh Eros từ dãy dữ liệu tán xạ.
Đây là một ví dụ điển hình của dữ liệu phân bố không đều, thƣờng khó có
thể khôi phục khi sử dụng các phƣơng pháp khác.
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
Biểu diễn RBF
Hình
Lưới gốc #Mặt
Bộ nhớ
Lưới mới #Mặt
#Đỉnh 437.645 543.652 1.086.798 19.6MB
#Đỉnh 847.414 15.4MB 126.998 254.016 4.5MB 97.766 193.604 3.5MB
Bộ nhớ Tâm RBF Bộ nhớ 72.461 1.4MB 80.518 1.6MB
327.323
654.666 11.8MB
81.829 163.698 2.9MB
85.468 1.7MB
Con rồng Bức tƣợng Xƣơng bàn tay
Bảng 2.3 so sánh kích thƣớc các lƣới gốc của các tập dữ liệu con rồng,
tƣợng phật và xƣơng bàn tay với kích thƣớc của sự biểu diễn RBF tƣơng
ứng. Các kích thƣớc lới không nén nhận đƣợc bằng việc cho 3 float (12
byte) tới mỗi đỉnh và 3 số nguyên (12 byte) tới mỗi cạnh tam giác. Kích
thƣớc tệp RBF không nén tƣơng đƣơng để biểu diễn mỗi tâm với 3 float
(12byte) và mỗi hệ số với một số chính xác hai lần (8 byte). Có nghĩa
là độ chính xác đơn giản có thể là thích hợp, mà sẽ dẫn đến nén nhiều hơn,
nhƣng chúng ta vẫn chƣa xác định đƣợc tầm ảnh hƣởng của hệ số độ chính
xác lên bề mặt tính toán. Bảng này chứng minh rằng độ nén đáng kể của cả
tập điểm và dữ liệu lƣới mà một biểu diễn RBF cung cấp. Chúng ta cũng
đã liệt kê kích thƣớc của các lƣới dẫn xuất từ việc tính toán hàm RBF với
một độ chính xác có thể so sánh với dữ liệu gốc. Nó xuất hiện từ các kết
quả ban đầu mà một ứng dụng có triển vọng của hàm RBF là đan lại lƣới
các lƣới đã có. Khớp một hàm RBF không chỉ lấp các lỗ, nhƣng một lƣới
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
đều hơn (và do đó chặt hơn) có thể dẫn xuất ra từ nó.
37
2.9. Kết luận:
Các phƣơng pháp nhanh làm cho nó có thể thực hiện tính toán để biểu
diễn các đối tƣợng phức tạp của cấu trúc liên kết bất kỳ bằng hàm RBF.
Lớp độc lập, sự mô tả „bộ nội suy trơn nhất‟ của hàm ghép trơn đa điều
hòa làm cho hàm RBF đặc biệt phù hợp cho việc khớp các bề mặt với các
điểm tập trung lấy mẫu không đều và các lƣới không hoàn toàn mà chứa
các lỗ lớn không đều. Bề mặt nhẵn nhất, phù hợp nhất với dữ liệu vào,
đƣợc sinh ra. Các sự kiện đƣợc giải quyết, với điều kiện là chúng là mẫu
thỏa đáng. Bản chất hàm số của biểu diễn bằng hàm RBF cung cấp các
triển vọng mới cho các thuật toán cân chỉnh bề mặt, rút gọn lƣới, nén và
các thuật toán làm nhẵn.
Hàm RBF cũng có liên quan tới bài toán của việc hiển thị hóa khối dữ
liệu thu đƣợc trên một lƣới tọa độ không đều, nhƣ là có thể khớp tới dữ
liệu mẫu hợp lệ để xấp xỉ sự phân bố vô hƣớng nằm dƣới. Các trƣờng véc
tơ có thể đƣợc mô hình dễ dàng nếu các thành phần là độc lập. Trong
trƣờng hợp đó, một hàm RBF có thể khớp tới mỗi trƣờng thành phần. Điều
này không yêu cầu thời gian tính toán nhiều hơn là bao nhiêu vì ma trận
trong phƣơng trình (2.8) chỉ phụ thuộc vào vị trí của các nút nội suy và vì
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
thế là thuộc mỗi thành phần hàm RBF.
38
Chƣơng 3: KHAI THÁC PHẦN MỀM FASTRBF
3.1. Phần mềm FastRBF làm gì?
Phần mềm FastRBF nội suy nhẹ nhàng dữ liệu tán xạ 2D và 3D bằng
các hàm cơ sở bán kính (RBFs). Không có kỹ thuật nào khác có thể mô
hình dữ liệu bất quy tắc, không đều hiệu quả bằng phép nội suy RBF. Với
phần mềm FastRBF của công nghệ FarField hàng triệu phép đo dữ liệu có
thể đƣợc nội suy bởi một hàm đơn – một công việc trƣớc đây không thể
nghĩ đƣợc trên một máy tính để bàn. Hàm khớp và độ chênh lệch của nó
có thể tính toán ở mọi nơi nhƣ trên một lƣới, một mặt phẳng hoặc một bề
mặt bất kỳ. Những khả năng này làm cho phần mềm FastRBF lý tƣởng cho
việc hiển thị dữ liệu tán xạ, đặc biệt là dữ liệu lấy mẫu bất quy tắc, không
đều và xây dựng lại các bề mặt từ dải dữ liệu.
3.2. Ai có thể sử dụng sản phẩm FastRBF?
Các kỹ sƣ, ngƣời phát triển phần mềm và các nhà khoa học đối mặt với
các vấn đề nội suy dữ liệu phân tán lớn.
Nghiên cứu về đồ họa máy tính, nghiên cứu đảo ngƣợc, thị giác nhân
tạo cần xây dựng lại các bề mặt từ dải dữ liệu.
Các sinh viên và những nhà nghiên cứu làm việc với các mẫu đơn 2D
và 3D không đều.
Những ngƣời đã làm việc với hàm RBF cần giải quyết những hệ thống
cực lớn.
3.3. Những lợi ích của phần mềm FastRBF
Phần mềm FastRBF cho phép hàm cơ sở bán kính phù hợp với những
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
hệ thống có nhiều hơn một triệu điểm dữ liệu trên phần cứng tính toán
39
thông thƣờng. Các hàm ghép trơn đa điều hòa mà phần mềm FastRBF sử
dụng kết quả trong phép nội suy nhẵn nhất, trong sự dò ra đó chúng làm
giảm đến mức tối thiểu năng lƣợng trong đạo hàm bậc 2, bậc 3 hoặc cao
hơn. Những kết quả này trong các khả năng ngoại suy đặc biệt khi các độ
chênh lệch lớn xuất hiện trong tập hợp dữ liệu. trong trƣờng hợp dữ liệu
nhiễu, bộ khớp dải lỗi của phần mềm FastRBF khớp gần đúng dữ liệu
bằng hàm ghép trơn trong các biên lỗi định vị tại mỗi điểm dữ liệu. Sự lọc
thông thấp của dữ liệu tán xạ cũng có thể đƣợc hoàn thành ngay lập tức
với phần mềm FastRBF mà không cần lấy mẫu lại trên một lƣới chuẩn và
sử dụng các phép tính toán nhân chập có chiều sâu trong không gian hoặc
trong miền Fourier.
3.4. Các ứng dụng:
Phần mềm FastRBF đã đƣợc ứng dụng trong một số lĩnh vực khác nhau
của khoa học và nghiên cứu các vấn đề từ tạo nguyên mẫu nhanh CAD-
CAM, sự tạo ảnh y học, đồ họa máy tính và sự xử lý tín hiệu…
3.5. Các kết quả đạt được khi sử dụng phần mềm FastRBF:
3.5.1. Khớp và tính toán dữ liệu 3D:
data=fastrbf_load('C:\Program Files\FarField Technology\FastRBF
v1.4\Matlab\tutorial\FitAndEval\data.p3d')
Trƣớc tiên, chúng ta tải dữ liệu điểm 3D bằng lệnh sau:
data =
Location: [3x5000 double]
Value: [1x5000 double]
Ta thu đƣợc kết quả nhƣ sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Để hiển thị dữ liệu 3D đã tải ta dùng câu lệnh sau:
colormap(jet(256))
fastrbf_view(data)
40
Sau khi dùng 2 lệnh trên ta thu đƣợc hình ảnh của dữ liệu 3D đã đƣợc
Hình 3.1: Dữ liệu 3D đƣợc tải vào.
tải nhƣ trong hình 3.1
Để an toàn chúng ta xử lý dữ liệu bằng hàm unique nhƣ sau:
data=fastrbf_unique(data)
data =
Location: [3x5000 double]
Value: [1x5000 double]
Ta thu đƣợc kết quả:
Vì phạm vi giá trị dữ liệu là 0,1 chúng ta khớp một hàm RBF với độ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
chính xác 0,001 sử dụng hàm fit
rbf=fastrbf_fit(data,0.001)
41
rbf =
AchievedAcc: 3.3439e-004
DefaultEvalAcc: 1.0000e-005
Centres: [3x5000 double]
Coeffs: [1x5004 double]
PolyBase: [0.5000 0.5001 0.5000]
DataMin: [3.8337e-005 2.0880e-004 4.3258e-005]
DataMax: [1.0000 0.9999 1.0000]
BasicFunc: 0
BasicFuncParam: 0
BasicFuncParam2: 1
PolyDegree: 1
Rho: 0
FitType: 0
Version: 'FastRBF V 1.4.2'
Sau khi khớp ta đƣợc kết quả:
3.5.1.1. Rút gọn tâm RBF:
rbf=fastrbf_fit(data,0.001,‟reduce‟,‟verbose‟)
Để rút gọn tâm RBF ta sử dụng câu lệnh sau:
rbf =
AchievedAcc: 9.0459e-004
DefaultEvalAcc: 1.0000e-005
Centres: [3x843 double]
Coeffs: [1x847 double]
PolyBase: [0.5000 0.5001 0.5000]
DataMin: [3.8337e-005 2.0880e-004 4.3258e-005]
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Sau khi rút gọn tâm ta thu đƣợc kết quả:
DataMax: [1.0000 0.9999 1.0000]
BasicFunc: 0
BasicFuncParam: 0
BasicFuncParam2: 1
PolyDegree: 1
Rho: 0
FitType: 1
Version: 'FastRBF V 1.4.2'
Indices: [1x843 double]
42
Rút gọn tâm có kết quả là 843 tâm so với 5000 tâm của phƣơng pháp
trực tiếp.
3.5.1.2. Tính toán lƣới 3D:
g=fastrbf_grideval(rbf,‟spacing‟,0.02)
Bây giờ chúng ta tính toán hàm RBF 3D trên một lƣới bằng câu lệnh:
g =
Value: [51x51x51 double]
Min: [3.8337e-005 2.0880e-004 4.3258e-005]
Max: [1.0000 1.0002 1.0000]
Spacing: [0.0200 0.0200 0.0200]
Ta thu đƣợc kết quả:
[gX, gY, gZ] = fastrbf_gridcoords(g);
gV = permute(g.Value, [2 1 3]);
slice(gY, gX, gZ, gV, .7, .7, .3); colorbar; axis tight;
Chúng ta phải đổi trật tự mảng giá trị và các đối số bằng các lệnh sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Sau khi thực hiện lệnh ta thu đƣợc lƣới nhƣ hình 3.2
Hình 3.2: Lƣới thu đƣợc sau khi đổi trật tự mảng giá trị và các đối số
43
3.5.2. Khớp dữ liệu bề mặt 3D:
3.5.2.1. Khớp bề mặt vào dữ liệu lƣới:
Dữ liệu lƣới đƣợc tạo ra từ rất nhiều loại máy quét và thƣờng chứa các
lỗ không đều, cả lỗ lớn và lỗ nhỏ.
mesh = fastrbf_import('C:\Program Files\FarField Technology\FastRBF
v1.4\Matlab\tutorial\SurfaceFit\holey_face.obj')
Bƣớc đầu tiên ta nhập vào tệp holey_face.obj bằng câu lệnh sau:
Mesh =
Location: [3x3328 double]
Tri: [3x6283 double]
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Sau khi thực hiện lệnh ta thu đƣợc kết quả:
44
Dùng lênh: fastrbf_view(Mesh); để hiển thị đƣợc hình ảnh của bề mặt
Hình 3.3. Hình ảnh của bề mặt đƣa vào
nhƣ trong hình 3.3
MeshWithNormals = fastrbf_normalsfrommesh(Mesh)
Sau đó xác định các đƣờng pháp tuyến bằng câu lệnh sau:
MeshWithNormals =
Location: [3x3328 double]
Tri: [3x6283 double]
Gradient: [3x3328 double]
Sau khi dùng lệnh trên ta thu đƣợc kết quả:
fastrbf_view(MeshWithNormals, 'fv');
Để hiển thị bề mặt với các đƣờng pháp tuyến ta dùng lệnh:
Sau khi dùng lệnh trên ta thu đƣợc bề mặt với các đƣờng pháp tuyến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
nhƣ đƣợc mô tả trong hình 3.4
Hình 3.4. Bề mặt với các đƣờng pháp tuyến
45
Trong ví dụ này, độ dài đƣờng pháp tuyến tối đa là 5mm sẽ đƣợc sử
dụng. Các đƣờng pháp tuyến ngắn hơn 0,5mm sẽ đƣợc loại bỏ bằng lệnh
Density = fastrbf_densityfromnormals(MeshWithNormals, 0.5, 5.0)
sau:
Density =
Location: [3x6656 double]
Value: [1x6656 double]
Gradient: [3x6656 double]
Sau khi thực hiện lệnh trên thu đƣợc kết quả:
Để hiển thị đƣợc kết quả (Hình 3.5) sau khi loại bỏ các đƣờng pháp
fastrbf_view(Density);
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
tuyến ngắn hơn 0,5mm ta dùng lệnh:
Hình 3.5: Bề mặt với các đƣờng pháp tuyến có độ dài nhỏ hơn 0,5mm bị loại bỏ
46
Density = fastrbf_unique(Density)
Trƣớc khi khớp dữ liệu dùng lệnh sau:
Density =
Location: [3x6653 double]
Value: [1x6653 double]
Gradient: [3x6653 double]
Sau khi dùng lệnh trên ta thu đƣợc:
Để so sánh lợi ích của việc rút gọn tâm đầu tiên chúng ta khớp không
rbf = fastrbf_fit(Density, 0.5, ‟direct‟)
có sự rút gọn tâm. Bằng câu lệnh sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Sau khi khớp ta có kết quả:
Finished fitting RBF
rbf =
AchievedAcc: 0.1093
DefaultEvalAcc: 0.0050
Centres: [3x6653 double]
Coeffs: [1x6657 double]
PolyBase: [2.3315 -7.9726 52.4559]
DataMin: [-74.7032 -121.5387 7.3864]
DataMax: [79.3662 105.5934 97.5255]
BasicFunc: 0
BasicFuncParam: 0
BasicFuncParam2: 1
PolyDegree: 1
Rho: 0
FitType: 0
Version: 'FastRBF V 1.4.2'
47
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Dùng lệnh: fastrbf_view(rbf); để hiển thị kết quả nhƣ trong hình 3.6:
Hình 3.6: Bề mặt sau khi khớp không có sự rút gọn tâm
48
rbf = fastrbf_fit(Density, 0.5,‟reduce‟)
Bây giờ chúng ta sẽ khớp bề mặt với sự rút gọn tâm bằng câu lệnh sau:
rbf =
AchievedAcc: 0.4614
DefaultEvalAcc: 0.0050
Centres: [3x1628 double]
Coeffs: [1x1632 double]
PolyBase: [2.3315 -7.9726 52.4559]
DataMin: [-74.7032 -121.5387 7.3864]
DataMax: [79.3662 105.5934 97.5255]
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Sau khi thực h iện lệnh ta thu đƣợc:
BasicFunc: 0
BasicFuncParam: 0
BasicFuncParam2: 1
PolyDegree: 1
Rho: 0
FitType: 1
Version: 'FastRBF V 1.4.2'
Indices: [1x1628 double]
49
Hình 3.7: Khớp sau khi rút gọn tâm
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Dùng lệnh: fastrbf_view(rbf); để hiển thị kết quả nhƣ trong hình 3.7
50
Trong trƣờng hợp này, khi khớp dữ liệu với việc rút gọn tâm chỉ yêu
cầu 1157 tâm còn khớp dữ liệu không có việc rút gọn tâm yêu cầu 3984
tâm.
Tiếp theo, chúng ta có thể tính giá trị của nó trên một lƣới 3D bằng lệnh
g = fastrbf_grideval(rbf, 0.1, ‟spacing‟, 3);
slice(g.Value, 40, 27, 15);
sau:
Hình 3.8: Tính giá trị của bề mặt trên lƣới 3D
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Sau khi tính giá trị trên lƣới 3D ta có kết quả nhƣ trong hình 3.8
51
Đẳng mặt trong lƣới 3D đƣợc hiểu là tại các điểm hàm RBF có giá trị
NewMesh = fastrbf_isosurf(rbf, 2)
bằng không. Một lƣới mới đƣợc sinh ra bằng câu lệnh sau:
Hình 3.9: Lƣới mới đƣợc sinh ra
Bằng lệnh: fastrbf_view(NewMesh); ta thu đƣợc hình 3.9.
Cuối cùng, chúng ta xuất lƣới thành file newmesh.obj để cho phép nó
fastrbf_export(NewMesh, ‟NewMesh.obj‟)
có thể tải đƣợc vào trong các gói 3D khác bằng lệnh sau:
3.5.1.2. Gia công đẳng mặt:
Chúng ta bắt đầu bằng việc tải dữ liệu quét laser từ một bàn tay và
khớp một hàm RBF vào một lƣới không đầy đủ. Các điểm ngoài bề mặt
đƣợc sinh ra bởi sự nhô ra trong khoảng 0,5mm và 5mm bên ngoài bề mặt
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
bàn tay.
52
Mesh = fastrbf_import(‟Hand.obj‟);
Density = fastrbf_densityfromnormals(Mesh, 0.5, 5.0);
Density = fastrbf_unique(Density);
rbf = fastrbf_fit(Density, 0.25,‟reduce‟);
Trƣớc hết ta đƣa dữ liệu bàn tay vào bằng câu lệnh sau:
Bây giờ chúng ta muốn rút ra một lƣới đa giác. Một lƣới 1mm có thể
NewMesh = fastrbf_isosurf(rbf, 1);
đƣợc sinh ra bằng lệnh sau:
Dùng lệnh: figure; fastrbf_view(NewMesh); để xem hình ảnh chi tiết của
Hình 3.10: Lƣới đa giác 1mm dƣợc sinh ra
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
lƣới mới sinh ra nhƣ hình 3.10.
53
3.6. Kết luận:
Với việc khai thác phần mềm FastRBF giúp ta hiểu vể quy trình và các
bƣớc để khôi phục, biểu diễn các đối tƣợng 3D một cách rõ ràng và cụ thể.
Từ đó hiểu rõ hơn về bài toán khôi phục và biểu diễn các đối tƣợng 3D, cụ
thể hơn là những vấn đề bề mặt ẩn, khớp một hàm ẩn vào bề mặt…
Qua một số thí dụ đã trình bày, chúng ta thấy đƣợc những lợi ích của
phần mềm FastRBF trong việc khôi phục và biểu diễn các đối tƣợng 3D.
Đây là một phần mềm rất hữu ích cho những đối tƣợng cần sử dụng những
kết quả của nó vào công việc của mình. Qua đó, chúng ta hiểu rõ hơn về
vấn đề khôi phục và biểu diễn các đối tƣợng 3D để từ đó vận dụng vào từng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
trƣờng hợp cụ thể trong quá trình làm việc.
54
KẾT LUẬN
Luận văn đề cập đến hàm cơ sở bán kính, một hàm có nhiều ứng dụng
khác nhau trong đó là ứng dụng trong đồ họa máy tính. Đây là một ứng
dụng quan trọng trong nhiều lĩnh vực khoa học. Kết quả của luận văn gồm
có:
1. Trình bày tóm lƣợc các kết quả quan trọng về ứng dụng hàm RBF
vào đồ họa máy tính mà xuất phát điểm là giải quyết bài toán nội suy dữ
liệu rời rạc. Từ việc nghiên cứu tính khả nghịch của ma trận nội suy dẫn
đến các nghiên cứu về hàm RBF. Các phƣơng pháp xây dựng hàm RBF
đảm bảo tính đặt đúng của bài toán nội suy mà nền tảng là các kiến thức về
hàm xác định dƣơng, hàm xác định dƣơng chặt, hàm đơn điệu hoàn toàn
(GA, IMQ …). Thông qua các hàm xác định dƣơng có điều kiện, xây dựng
mô hình nội suy với độ chính xác đa thức và các hàm RBF sử dụng tƣơng
ứng (TPS, MQ…).
2. Trong chƣơng 2, luận văn đã trình bày ứng dụng hàm RBF vào việc
khôi phục và biểu diễn các đối tƣợng 3D. Các vấn đề: Bề mặt ẩn; Khớp một
hàm ẩn vào bề mặt; Nội suy hàm cơ sở bán kính; Các phƣơng pháp nhanh;
Rút gọn tâm… đã đƣợc đƣa ra để giải quyết bài toán ứng dụng hàm RBF
vào việc khôi phục và biểu diễn các đối tƣợng 3D.
3. Trong chƣơng 3, luận văn đã giới thiệu sơ lƣợc về phần mềm
Mặc dù đã hết sức cố gắng xong luận văn còn nhiều hạn chế và không
FastRBF và đƣa ra các kết quả trên một số thí dụ cụ thể.
thể tránh khỏi những sai sót. Em rất mong nhận đƣợc sự phê bình, đóng góp
ý kiến của các thầy cô và bạn đọc.
Cuối cùng, một lần nữa em xin chân thành cảm ơn sự giúp đỡ, chỉ bảo
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
nhiệt tình của thầy giáo PGS.TS. Đặng Quang Á.
55
TÀI LIỆU THAM KHẢO
[TIẾNG VIỆT]
[1] Phạm Kỳ Anh (2000), Giải tích số, NXB Đại học Quốc Gia Hà Nội.
[TIẾNG ANH]
[1]M. D. Buhmann, Radial Basis Functions: Theory and Implementations,
Cambridge University Press, Cambridge, 2003.
[2] FastRBF Toolbox, MATLAB Interface, Version 1.4, 4th August 2004,
FarField Technology Ltd.
[3] R. K. Beatson, J. B. Cherrie, and C. T. Mouat. Fast fitting of radial basis
functions: Methods based on preconditioned GMRES iteration. Advances in
Computational Mathematics, 11:253–270, 1999.
[4] R. K. Beatson, J. B. Cherrie, and D. L. Ragozin. Fast evaluation of radial
basis functions: Methods for four-dimensional polyharmonic splines. SIAM J.
Math.Anal., 32(6):1272–1310, 2001.
[5] R. K. Beatson and L. Greengard. A short course on fast multipole
methods. In M. Ainsworth, J. Levesley, W.A. Light, and M. Marletta, editors,
Wavelets Multilevel Methods and Elliptic PDEs, pages 1–37. Oxford
University Press 1997.
[6] R. K. Beatson and W. A. Light. Fast evaluation of radial basis functions:
Method for two-dimensional polyharmonic splines. IMA Journal of
Numerical Analysis, 17:343–372, 1997.
[7] R. K. Beatson, W. A. Light, and S. Billings. Fast solution of the radial
basis function interpolation equations: Domain decomposition methods. SIAM
J. Sci Comput., 22(5):1717–1740, 2000.
[8] R. K. Beatson, A. M. Tan, and M. J. D. Powell. Fast evaluation of radial
basis functions: Methods for 3-dimensional polyharmonic splines. In
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
preparation.
56
[9] F. Bernardini, C. L. Bajaj, J. Chen, and D. R. Schikore. Automatic
reconstruction of 3D CAD models from digital scans. Int. J. on Comp. Geom.
and Appl., 9(4–5):327, Aug & Oct 1999.
[10] J. Bloomenthal, editor. Introduction to Implicit Surfaces. Morgan
Kaufmann, San Francisco, California, 1997.
[11] J. C. Carr, W. R. Fright, and R. K. Beatson. Surface interpolation with
radial basis functions for medical imaging. IEEE Trans. Medical Imaging,
16(1):96–107, February 1997.
[12] E. W. Cheney and W. A. Light. A Course in Approximation Theory.
Brooks Cole, Pacific Grove, 1999.
[13] J. Duchon. Splines minimizing rotation-invariant semi-norms in Sobolev
spaces. In W. Schempp and K. Zeller, editors, Constructive Theory of
Functions of Several Variables, number 571 in Lecture Notes in Mathematics,
pages 85–100, Berlin, 1977. Springer-Verlag.
[14] N. Dyn, D. Levin, and S. Rippa. Numerical procedures for surface fitting
ofscattered data by radial functions. SIAM J. Sci. Stat. Comput., 7(2):639–
659, 1986.
[15] J. Flusser. An adaptive method for image registration. Pattern
Recognition, 25(1):45–54, 1992.
[16] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle.
Surface reconstuction from unorganized points. Computer Graphics
(SIGGRAPH’92 proceedings), 26(2):71–78, July 1992.
[17] W. E. Lorensen and H. E. Cline. Marching cubes: A high resolution 3D
surface construction algorithm. Computer Graphics, 21(4):163–169, July
1987.
[18] C. A. Micchelli. Interpolation of scattered data: Distance matrices and
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
conditionally positive definite functions. Constr. Approx., 2:11–22, 1986.
57
[19] V. V. Savchenko, A. A. Pasko, O. G. Okunev, and T. L. Kunii. Function
representation of solids reconstructed from scattered surface points and
contours. Computer Graphics Forum, 14(4):181–188, 1995.
[20] G.M. Treece, R.W. Prager, and A. H. Gee. Regularised marching
etrahedra: improved iso-surface extraction. Computers and Graphics,
23(4):583–598, 1999.
[21] G. Turk and J. F. O‟Brien. Shape transformation using variational
implicit surfaces. In SIGGRAPH’99, pages 335–342, Aug 1999.
[22] G. Turk and J. F. O‟Brien. Variational implicit surfaces. Technical
Report GITGVU-99-15, Georgia Institute of Technology, May 1999.
[23] G. Wahba. Spline Models for Observational Data. Number 59 in CBM-
SNSF Regional Conference Series in Applied Math. SIAM, 1990.
[24] G. Yngve and G. Turk. Creating smooth implicit surfaces from polygonal
meshes. Technical Report GIT-GVU-99-42, Georgia Institute of Technology,
1999.
[25] WOLFGANG NIEM, JOCHEN WINGBERMUHLE. 1997. Automatic
Reconstruction of 3D Objects Using a Mobile Monoscopic Camera. In
Proceedings of the International Conference on Recent Advances in 3D
Imaging and Modelling",Ottawa, Canada.
[26] ANDERS HEYDEN. 1995. Geometry and Algebra of Multiple
Projective Transformations. Dept of Mathematics, Lund University, Sweden.
[27] L. Greengard and V. Rokhlin. A fast algorithm for particle simulations.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
J.Comput. Phys, 73:325–348, 1987.
