$${L_q}$$ -Closest-Point to Affine Subspaces Using the Generalized Weiszfeld Algorithm
Tóm tắt
This paper presents a method for finding an
$$L_q$$
-closest-point to a set of affine subspaces, that is a point for which the sum of the q-th power of orthogonal distances to all the subspaces is minimized, where
$$1 \le q < 2$$
. We give a theoretical proof for the convergence of the proposed algorithm to a unique
$$L_q$$
minimum. The proposed method is motivated by the
$$L_q$$
Weiszfeld algorithm, an extremely simple and rapid averaging algorithm, that finds the
$$L_q$$
mean of a set of given points in a Euclidean space. The proposed algorithm is applied to the triangulation problem in computer vision by finding the
$$L_q$$
-closest-point to a set of lines in 3D. Our experimental results for the triangulation problem confirm that the
$$L_q$$
-closest-point method, for
$$1 \le q < 2$$
, is more robust to outliers than the
$$L_2$$
-closest-point method.
Tài liệu tham khảo
Aftab, K., Hartley, R., & Trumpf, J. (submitted). Generalized Weiszfeld algorithms for Lq optimization.
Ameri, B., & Fritsch, D. (2000). Automatic 3d building reconstruction using plane-roof structures. Washington, DC: ASPRS.
Brimberg, J. (2003). Further notes on convergence of the weiszfeld algorithm. Yugoslav Journal of Operations Research, 13(2), 199–206.
Brimberg, J., & Chen, R. (1998). A note on convergence in the single facility minisum location problem. Computers & Mathematics with Applications, 35(9), 25–31.
Brimberg, J., & Love, R. F. (1993). Global convergence of a generalized iterative procedure for the minisum location problem with lp distances. Operations Research, 41(6), 1153–1163.
Chartrand, R., & Yin, W. (2008). Iteratively reweighted algorithms for compressive sensing. In IEEE International Conference on Acoustics, Speech and Signal Processing.
Chi, E. C., & Lange, K. (2014). A look at the generalized heron problem through the lens of majorization-minimization. The American Mathematical Monthly, 121(2), 95–108.
Daubechies, I., DeVore, R., Fornasier, M., & Gunturk, S. (2008). Iteratively re-weighted least squares minimization: Proof of faster than linear rate for sparse recovery. In 42nd Annual Conference on Information Sciences and Systems.
Dick, A.R., Torr, P.H., Ruffle, S.J., & Cipolla, R. (2001). Combining single view recognition and multiple view stereo for architectural scenes. In IEEE International Conference on Computer Vision
Eckhardt, U. (1980). Weber’s problem and weiszfeld’s algorithm in general spaces. Mathematical Programming, 18(1), 186–196.
Eldar, Y., & Mishali, M. (2009). Robust recovery of signals from a structured union of subspaces. IEEE Transactions on Information Theory, 55(11), 5302–5316.
Fletcher, P. T., Venkatasubramanian, S., & Joshi, S. (2009). The geometric median on Riemannian manifolds with application to robust atlas estimation. NeuroImage, 45(1), S143–S152.
Furukawa, Y., Curless, B., Seitz, S., & Szeliski, R. (2009). Manhattan-world stereo. In IEEE Conference on Computer Vision and Pattern Recognition.
Furukawa, Y., Curless, B., Seitz, S.M., & Szeliski, R. (2009). Reconstructing building interiors from images. In IEEE International Conference on Computer Vision.
Hartley, R., Aftab, K., & Trumpf, J. (2011). L1 rotation averaging using the Weiszfeld algorithm. In IEEE Conference on Computer Vision and Pattern Recognition.
Hartley, R., Trumpf, J., Dai, Y., & Li, H. (2013). Rotation averaging. International Journal of Computer Vision, 103(3), 267–305.
Hartley, R. I., & Sturm, P. (1997). Triangulation. Computer Vision and Image Understanding, 68(2), 146–157.
Hartley, R. I., & Zisserman, A. (2004). Multiple view geometry in computer vision (2nd ed.). Cambridge: Cambridge University Press.
Henry, P., Krainin, M., Herbst, E., Ren, X., & Fox, D. (2010). Rgb-d mapping: Using depth cameras for dense 3d modeling of indoor environments. In the 12th International Symposium on Experimental Robotics (ISER).
Kleiman, S., & Laksov, D. (1972). Schubert calculus. American Mathematical Monthly, 79, 1061–1082.
Lourakis, M. A., & Argyros, A. (2009). SBA: A Software Package for Generic Sparse Bundle Adjustment. ACM Transactions on Mathematical Software (TOMS), 36(1), 2.
Luenberger, D. G. (2003). Linear and nonlinear programming. New York: Springer.
Ma, R. (2004). Building model reconstruction from lidar data and aerial photographs. Ph.D. thesis, The Ohio State University.
Mordukhovich, B., & Nam, N. M. (2011). Applications of variational analysis to a generalized fermat-torricelli problem. Journal of Optimization Theory and Applications, 148(3), 431–454.
Mordukhovich, B. S., Nam, N. M., & Salinas, J, Jr. (2012). Solving a generalized heron problem by means of convex analysis. The American Mathematical Monthly, 119(2), 87–99.
Müller, P., Zeng, G., Wonka, P., & Van Gool, L. (2007). Image-based procedural modeling of facades. ACM Transactions on Graphics, 26(3), 85.
Pu, S., & Vosselman, G. (2009). Knowledge based reconstruction of building models from terrestrial laser scanning data. ISPRS Journal of Photogrammetry and Remote Sensing, 64(6), 575–584.
Remondino, F., & El-Hakim, S. (2006). Image-based 3d modelling: A review. The Photogrammetric Record, 21(115), 269–291.
Schindler, K., & Bauer, J. (2003). A model-based method for building reconstruction. In: First IEEE International Workshop on Higher-Level Knowledge in 3D Modeling and Motion Analysis.
Semple, J. G., & Kneebone, G. T. (1979). Algebraic Projective Geometry. London: Oxford University Press.
Taillandier, F. (2005). Automatic building reconstruction from cadastral maps and aerial images. International Archives of Photogrammetry and Remote Sensing, 36, 105–110.
Triggs, B., McLauchlan, P. F., Hartley, R. I., & Fitzgibbon, A. W. (2000). Bundle adjustment—a modern synthesis. In: Vision algorithms: Theory and practice (pp. 298–372). Springer.
Vanegas, C.A., Aliaga, D.G., & Benes, B. (2010). Building reconstruction using manhattan-world grammars. In IEEE Conference on Computer Vision and Pattern Recognition.
Weiszfeld, E. (1937). Sur le point pour lequel la somme des distances de \(n\) points donnés est minimum. Tohoku Mathematical Journal, 43(355—-386), 2.
Werner, T., & Zisserman, A. (2003). New techniques for automated architectural reconstruction from photographs. In European Conference on Computer Vision.
Wilczkowiak, M., Trombettoni, G., Jermann, C., Sturm, P., & Boyer, E. (2003). Scene modeling based on constraint system decomposition techniques. In Ninth IEEE International Conference on Computer Vision.
Yang, L. (2010). Riemannian median and its estimation. LMS Journal of Computation and Mathematics, 13, 461–479.