Super 4PCS: Đăng ký Điểm Lập Thể Toàn Cầu Nhanh Chóng Thông Qua Tổ Chức Chỉ Mục Thông Minh

Computer Graphics Forum - Tập 33 Số 5 - Trang 205-215 - 2014
Nicolas Mellado1, Dror Aiger2,2, Niloy J. Mitra1
1University College London
2Google Inc

Tóm tắt

Tóm tắtViệc thu thập dữ liệu trong các cảnh quy mô lớn thường bao gồm việc tích lũy thông tin từ nhiều lần quét. Một phương pháp thông thường là căn chỉnh cặp quét cục bộ bằng cách sử dụng thuật toán Điểm Gần Nhất Tương Tự (ICP) (hoặc các biến thể của nó), nhưng yêu cầu các cảnh tĩnh và chuyển động nhỏ giữa các cặp quét. Điều này ngăn cản việc tích lũy dữ liệu qua nhiều phiên quét và/hoặc các phương thức thu thập khác nhau (ví dụ, quét stereo, quét chiều sâu). Ngược lại, có thể sử dụng một thuật toán đăng ký toàn cầu cho phép các lần quét có tư thế ban đầu tùy ý. Tuy nhiên, thuật toán đăng ký toàn cầu hiện đại, 4PCS, có độ phức tạp thời gian bậc hai theo số lượng điểm dữ liệu. Điều này rất hạn chế khả năng áp dụng của nó cho việc thu thập các môi trường lớn. Chúng tôi giới thiệu Super 4PCS cho việc đăng ký điểm lập thể toàn cầu mà là tối ưu, tức là chạy trong thời gian tuyến tính (theo số lượng điểm dữ liệu) và cũng nhạy cảm với đầu ra trong độ phức tạp của vấn đề căn chỉnh dựa trên độ chồng lấp (chưa biết) giữa các cặp quét. Về mặt kỹ thuật, chúng tôi ánh xạ thuật toán như một 'vấn đề thể hiện' và giải quyết nó một cách hiệu quả bằng cách sử dụng một tổ chức dữ liệu chỉ mục thông minh. Thuật toán này đơn giản, tiết kiệm bộ nhớ và nhanh chóng. Chúng tôi chứng minh rằng Super 4PCS mang lại sự tăng tốc đáng kể so với các phương pháp thay thế và cho phép thu thập cảnh hiệu quả không cấu trúc ở quy mô trước đây không thể thực hiện được. Mã nguồn đầy đủ và tập dữ liệu có sẵn cho mục đích nghiên cứu tại http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/.

Từ khóa


Tài liệu tham khảo

10.1016/j.patcog.2009.05.014

AronovB. KoltunV. SharirM.:Incidences between points and circles in three and higher dimensions. InDiscrete Comput. Geom. (2005) pp.185–2006. 3

10.1145/1360612.1360684

AlbarelliA. RodolàE. TorselloA.:Loosely distinctive features for robust surface alignment. InECCV(2010) pp.519–532. 3

ArvoJ.:A simple method for box‐sphere intersection testing. InGraphics Gems GlassnerA.S. (Ed.).1990. 6 7

10.1109/34.121791

Bouaziz S., 2013, Sparse iterative closest point, CGF (SGP), 32, 1

Cheng Z.‐Q., 2013, Supermatching: Feature matching using supersym‐metric geometric constraints, IEEE TVCG, 19

10.1007/s11263-012-0552-5

10.1007/BF02189314

10.1109/34.809117

10.1016/0262-8856(92)90066-C

10.1016/j.patrec.2012.07.006

10.1007/BF00288933

10.1145/358669.358692

10.1086/427976

10.1007/s00453-003-1043-4

GuennebaudG. IacobB. ETAL.:Eigen v3.http://eigen.tuxfamily.org 2010. 7

GelfandN. MitraN.J. GuibasL.J. PottmannH.:Robust global registration. InProc. SGP(2005) pp.197–206. 3

IzadiS. KimD. HilligesO. MolyneauxD. NewcombeR. KohliP. ShottonJ. HodgesS. FreemanD. DavisonA. FitzgibbonA.:Kinectfusion: Real‐time 3d reconstruction and interaction using a moving depth camera. InProc. UIST(2011) pp.559–568. 2

IraniS. RaghavanP.:Combinatorial and experimental results for randomized point matching algorithms. InProc. Symposium on Computational Geometry(1996) pp.68–77. 2

LiX. GuskovI.:Multi‐scale features for approximate alignment of point‐based surfaces. InProc. SGP(2005). 3

10.1111/j.1467-8659.2012.03174.x

MitraN.J. GelfandN. PottmannH. GuibasL.:Registration of point cloud data from a geometric optimization perspective. InProc. SGP(2004) pp.23–31. 2

PapazovC. BurschkaD.:Stochastic optimization for rigid point set registration. InProc. Intern. Symposium on Advances in Visual Computing(2009) pp.1043–1054. 3

10.1016/j.cviu.2011.05.008

10.1090/conm/342/06151

10.1016/j.cagd.2008.01.002

10.1007/s11263-012-0568-x

10.1145/566654.566600

Rusinkiewicz S., 2001, Proc. 3DIM, 145

ShangL. GreenspanM.:Pose determination by potentialwell space embedding. InProc. 3DIM(2007) pp.297–304. 2

Tam G., 2013, Registration of 3d point clouds and meshes: A survey from rigid to nonrigid, IEEE TVCG, 19, 1199

10.1016/j.cviu.2010.11.021

10.1561/0600000017

Thông tin
Thông tin xuất bản

Computer Graphics Forum

Tập 33 Số 5

205-215

Thông tin tác giả