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

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ào các điểm ngoài bề mặt sinh ra một hàm với một đại lƣợng chênh lệch gần bằng 1 gần bề mặt. Hình 2.4: Mặt cắt qua các ngón tay của một bàn tay đƣợc khôi phục từ tập điểm tập trung trong hình 2.3. Đẳng đƣờng tƣơng ứng với +1, 0 và -1 đƣợc hiển thị (trên đỉnh) cùng với một mặt cắt nghiêng của hàm cơ cở bán kính (bên dƣới) dọc theo đƣờng thẳng xuất hiện. 21 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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     N ii xX 1 R3 và một tập hợp các giá trị hàm     N ii f 1 R, tìm một hàm nội suy: R3 → R nhƣ sau: .,...,1,)( Nifxs ii  (2.2) Chú ý rằng chúng ta sử dụng ký hiệu ),,( zyxX  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  BL (2) (R3) : s(xi) = fi, i = 1,…,N} (2.3) 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 )( 2 )( 2 )()()( 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 dx zy xs zx xs yx xs z xs y xs x xs s R                                                    (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à: ,minarg* ss Ss  có dạng đơn giản 22 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên    N i ii xxxpxs 1 * ,)()(  (2.5) Với p là một đa thức tuyến tính, các hệ số i 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: i N i i xxxpxs   1 )()(  , (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 )log()( 2 rrr  (cho việc khớp các hàm trơn hai biến), hàm Gauss )exp()( 2crr  (chủ yếu cho các mạng thần kinh), và hàm đa bậc hai 22)( crr  (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 ( ,)( rr  tức là, phƣơng trình (2.5)) và tam điều hòa ( 3)( rr  ). Một lựa chọn tùy ý các hệ số i 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 *s BL (2) (R3) kéo theo tính trực giao hay các điều kiện bổ sung 0 1111    N i ii N i ii N i ii N i i zyx  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à: 0)( 1   N i ii xq , cho tất cả các đa thức q bậc cao nhất của m. (2.7) 23 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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  lccc ,...,1 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:                         00 f c B c P P A T  , (2.8) với .,...,1,,...,1),( ,,...,1,),( ljNixPP NjixxA ijiJ jiiJ   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 (2.5) có dạng zcycxccxp 4321)(  , thì ,,...,1,, NjixxA jiij  P là ma trận với dòng thứ i T Niii zyx ),...,(),,,,1( 1   và .),,,( 4321 Tccccc  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 ))()(( 2 1 22   crr 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 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 rr )( 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 2 )1(3 NN 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 )(6 2 3 NO N  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ỉ 9106.1  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 000,2N . 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 [14,15]. 25 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Độ chính xác điều chỉnh + các nút nội suy - - - - độ chính xác tính toán . các điểm tính toán đƣa ra khớp bằng RBF …… bề mặt đƣ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 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 đ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. 26 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Bảng 2.1 : So sánh phƣơng pháp trực tiếp và phƣơng pháp nhanh Khớp dữ liệu Phƣơng pháp trực tiếp Phƣơng pháp nhanh Đòi hỏi bộ nhớ 2 )1( NN O(N) Khối lƣợng tính toán giải hệ )( 6 2 3 NO N  O(NlogN) Tính giá trị Khối lƣợng tính toán O(N) O(1) 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ự 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 )(xs 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 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên minh họa trong hình 2.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ữ liệu mong muốn. Hình 2.7: Minh họa sự rút gọn tâm. 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ƣ, )( iii xsf  , tại tất cả các nút. 3. Nếu  imax < độ 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 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 i đƣợ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 i < i . 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ố 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 Các tâm RBF Tập con rút gọn của các tâm RBF 29 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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     N i ii fxs N s s 1 22 3)2( ))(( 1 )(BL min  R , (2.9) với 0 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ơ TTT c ),( là lời giải tới                    00 8 f cP PlNA T  , (2.10) 30 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 chóng vì độ chênh lệch là hằng số xấp xỉ gần bề mặt. 31 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 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 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 là lũy thừa ba, nhƣ nó muốn nếu một số lƣợng đầy đủ là đƣợc làm mẫu. (a) (b) (c) (a) (b) (c) 32 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 trong tinh huống khớp một bề mặt nhẵn với dữ liệu LIDAR nhiễu. 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. (a) (b) 33 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 điểm bề mặt Số lƣợng nút nội suy Số lƣợng tâm RBF RAM tối đa (MB) Thời gian khớp Thời gian chỉnh bề mặt Độ chính xác liên quan Bề mặt 14.806 29.074 3.564 29 68s 27s 7 x 10-4 Bàn tay 13.348 26.696 4.299 29 97s 32s 1 x 10 -3 Con rồng 437.645 872.487 72.461 306 2:51:09 0:04:40 8 x 10-4 Tƣợng đứa trẻ 331.135 662.269 83.293 187 3:09:06 0:06:41 4 x 10 -4 Xƣơng bàn tay 327.323 654.645 85.468 188 3:08:44 0:04:04 3 x 10 -4 Tƣợng LIDAR 345.910 518.864 518.864 390 3:08:21 0:25:39 6 x 10 -3 Con rồng trong