Hàm RBF và một số ứng dụng trong đồ họa máy tính

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 1n 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  0R được gọi là đơn điệu hoàn toàn khi và chỉ khi      01  tll (1.9) với mọi ,...,1,0l 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, pP 1m 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  1m 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    rmm1 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áp chủ động và phƣơng pháp bị động [25]. Nhƣợc điểm của các phƣơng pháp chủ động là quá trình khôi phục có thể trở thành một công trình ngân sách cao. Vì lý do đó, cách tiếp cận đƣợc giới thiệu thuộc về các phƣơng pháp bị động, nó yêu cầu ít thiết bị hơn và có thể áp dụng một cách tổng quát hơn. Các phƣơng pháp khôi phục các đối tƣợng 3D truyền thống không thực hiện tốt ở hai hƣớng: - Thứ nhất: Chúng không thể xử lý các trƣờng hợp có độ phức tạp cao đƣợc tìm thấy trong tự nhiên (Ví dụ: các bộ phận của con ngƣời hay các ảnh cực nhỏ của mô). - Thứ hai: Chúng không đƣa dữ liệu bề mặt vào một định dạng làm cho gọn và thích hợp để mô phỏng, hiển thị hoặc định vị Có 5 trƣờng hợp khôi phục các đối tƣợng 3D [26]. Trƣờng hợp đầu tiên là với các ảnh đƣợc chụp bằng máy ảnh không định cỡ, làm việc với loại ảnh này có thể khôi phục lại đối tƣợng so sánh với các phép biến đổi ảnh xạ. Hai là, khôi phục từ các máy ảnh định cỡ làm việc với loại ảnh này có thể khôi phục lại đối tƣợng so sánh với các phép biến đổi đồng dạng. Ba là, các thuộc tính đại số của các hàm đa tuyến tính và các lý tƣởng phát sinh bởi chúng đƣợc nghiên cứu. Trƣờng hợp thứ tƣ sử dụng kỹ thuật khôi phục Ơ-clít khi một số thông tin của các máy ảnh đƣợc đƣa ra. Trƣờng hợp 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 3D là một bài toán có ý nghĩa rất lớn và quan trọng. 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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ự áp dụng lại lƣới. 15 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 2.1: (a) Khớp một hàm RBF vào một tập hợp các điểm dữ liệu tập trung 438.000 điểm. (b) Sự phục hồi lƣới tự động sử dụng hàm RBF song điều hòa. 2.1. Các bề mặt ẩn: Bài toán khôi phục hoặc biểu diễn bề mặt có thể phát biểu nhƣ sau: Bài toán 2.1. Cho n điểm phân biệt   n iiii zyx 1 ,,  trên một bề mặt M trong 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 ),,( zyxf . Nếu một bề mặt M gồm có tất cả các điểm ),,( zyx thỏa mãn phƣơng trình: 0),,( zyxf , (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 đơ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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 ,,...,1,0),,( nizyxf iii  với  n iii zyx 1 ,,(  là các điểm nằm trên bề mặt. Để tránh trƣờng hợp nghiệm tầm thƣờng mà f là 0 ở mọi nơi, các điểm ngoài bề mặt đƣợc bổ sung vào dữ liệu vào và chúng đƣa ra các giá trị khác 0. Việc này mang đến một vấn đề nội suy hữu ích hơn: Tìm hàm f nhƣ sau: 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên nizyxf iii ,...,1,0),,(  (các điểm trên bề mặt), Nnidzyxf iiii ,...,1,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  N iii zyx 1 ,,(  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 minh họa trong hình 2.2. Đẳng mặt f(x) = 0 f(x) > 0 f(x) < 0 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 2.2: Một hàm khoảng cách điểm đƣợc xây dựng từ dữ liệu bề mặt bằng việc định rõ các điểm ngoài bề mặt dọc theo các đƣờng pháp tuyến bề mặt. Những điểm này có thể đƣợc định rõ ở mỗi phía của bề mặt hoặc không ở phía nào cả. Hình 2.3. Sự khôi phục của một bàn tay từ đám điểm có và không thông qua các độ dài pháp tuyến Kinh nghiệm cho thấy rằng tốt hơn hết là bổ sung tại một điểm dữ liệu hai điểm ngoài bề mặt, mỗi điểm nằm trên một phía của bề mặt. Trong hình 2.3 các điểm bề mặt nhận đƣợc từ việc quét laser của một bàn tay đƣợc biểu thị bằng màu xanh. Các điểm ngoài bề mặt đƣợc mã hóa màu theo khoảng cách của chúng xuất phát từ điểm đƣợc liên kết trên bề mặt của chúng. Màu nóng (màu đỏ) mô tả các điểm dƣơng nằm ở bên ngoài bề mặt trong khi màu lạnh (xanh) nằm ở bên trong. Có hai bài toán cần giải Các điểm pháp tuyển ngoài bề mặt Các điểm trên bề mặt 19 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên quyết: xác định các đƣờng pháp tuyến bề mặt và định rõ khoảng cách hình 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 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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._.