A new approach to two-view motion segmentation using global dimension minimization. (English) Zbl 1328.68249
Summary: We present a new approach to rigid-body motion segmentation from two views. We use a previously developed nonlinear embedding of two-view point correspondences into a 9-dimensional space and identify the different motions by segmenting lower-dimensional subspaces. In order to overcome nonuniform distributions along the subspaces, whose dimensions are unknown, we suggest the novel concept of global dimension and its minimization for clustering subspaces with some theoretical motivation. We propose a fast projected gradient algorithm for minimizing global dimension and thus segmenting motions from 2-views. We develop an outlier detection framework around the proposed method, and we present state-of-the-art results on outlier-free and outlier-corrupted two-view data for segmenting motion.
MSC:
| 68T45 | Machine vision and scene understanding |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 62H35 | Image analysis in multivariate analysis |
| 62F35 | Robustness and adaptive procedures (parametric inference) |
Keywords:
global dimension; empirical dimension; subspace clustering; hybrid-linear modeling; motion segmentation; outliers; robust statisticsReferences:
| [1] | Aldroubi, A. (2013). A review of subspace segmentation: Problem, nonlinear approximations, and applications to motion segmentation. ISRN Signal Processing, 2013, 1–13. doi: 10.1155/2013/417492 . · doi:10.1155/2013/417492 |
| [2] | Arias-Castro, E., Chen, G., & Lerman, G. (2011). Spectral clustering based on local linear approximations. Electronic Journal of Statistics, 5, 1537–1587. · Zbl 1271.62132 · doi:10.1214/11-EJS651 |
| [3] | Arias-Castro, E., Lerman, G., & Zhang, T. (2013). Spectral clustering based on local PCA. ArXiv e-prints. · Zbl 1437.62225 |
| [4] | Baker, S., & Matthews, I. (2004). Lucas-kanade 20 years on: A unifying framework. International Journal of Computer Vision, 56(1), 221–255. · Zbl 1477.68324 · doi:10.1023/B:VISI.0000011205.11775.fd |
| [5] | Barbará, D., & Chen, P. (2000). Using the fractal dimension to cluster datasets. In KDD (pp. 260–264). |
| [6] | Bertsekas, D. (1995). Nonlinear programming. Optimization and neural computation series. Belmont, MA: Athena Scientific. |
| [7] | Bhatia, R. (1997). Matrix analysis. Graduate texts in mathematics series. New York: Springer. |
| [8] | Boult, T. E., & Brown, L. G. (1991). Factorization-based segmentation of motions. In Proceedings of the IEEE workshop on visual motion (pp. 179–186). |
| [9] | Bradley, P., & Mangasarian, O. (2000). k-Plane clustering. Journal of Global Optimization, 16(1), 23–32. · Zbl 0990.90135 · doi:10.1023/A:1008324625522 |
| [10] | Chen, G., Atev, S., & Lerman, G. (2009). Kernel spectral curvature clustering (KSCC). In IEEE 12th international conference on computer vision, (ICCV workshops), Kyoto (pp. 765–772). doi: 10.1109/ICCVW.2009.5457627 . |
| [11] | Chen, G., & Lerman, G. (2009a). Foundations of a multi-way spectral clustering framework for hybrid linear modeling. Foundations of Computational Mathematics, 9(5), 517–558. doi: 10.1007/s10208-009-9043-7 . · Zbl 1176.68155 · doi:10.1007/s10208-009-9043-7 |
| [12] | Chen, G., & Lerman, G. (2009b). Spectral curvature clustering (SCC). International Journal of Computer Vision, 81(3), 317–330. · doi:10.1007/s11263-008-0178-9 |
| [13] | Chen, G., & Maggioni, M. (2011). Multiscale geometric and spectral analysis of plane arrangements. In IEEE conference on computer vision and pattern recognition (CVPR). |
| [14] | Costeira, J., & Kanade, T. (1998). A multibody factorization method for independently moving objects. International Journal of Computer Vision, 29(3), 159–179. · doi:10.1023/A:1008000628999 |
| [15] | Elhamifar, E., & Vidal, R. (2009). Sparse subspace clustering. In Proceedings of the 2009 IEEE computer society conference on computer vision and pattern recognition (CVPR 09) (pp. 2790–2797). |
| [16] | Elhamifar, E., & Vidal, R. (2013). Sparse subspace clustering: Algorithm, theory, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 2765–2781. · doi:10.1109/TPAMI.2013.57 |
| [17] | Feng, X., & Perona, P. (1998). Scene segmentation from 3d motion. In Proceedings of the IEEE computer society conference on computer vision and pattern recognition (pp. 225–231). doi: 10.1109/CVPR.1998.698613 . |
| [18] | Gionis, A., Hinneburg, A., Papadimitriou, S., & Tsaparas, P. (2005). Dimension induced clustering. In KDD (pp. 51–60). |
| [19] | Grafakos, L. (2004). Classical and modern Fourier analysis. London: Pearson/Prentice Hall. · Zbl 1148.42001 |
| [20] | Haro, G., Randall, G., & Sapiro, G. (2006). Stratification learning: Detecting mixed density and dimensionality in high dimensional point clouds. In Neural information processing systems. |
| [21] | Haro, G., Randall, G., & Sapiro, G. (2008). Translated poisson mixture model for stratification learning. International Journal of Computer Vision, 80(3), 358–374. · Zbl 1477.68265 · doi:10.1007/s11263-008-0144-6 |
| [22] | Hartley, R. I., & Zisserman, A. (2000). Multiple view geometry in computer vision. Cambridge: Cambridge University Press. ISBN:0521623049. · Zbl 0956.68149 |
| [23] | Ho, J., Yang, M., Lim, J., Lee, K., & Kriegman, D. (2003). Clustering appearances of objects under varying illumination conditions. In Proceedings of international conference on computer vision and pattern recognition (vol. 1, pp. 11–18). |
| [24] | Kanatani, K. (2001). Motion segmentation by subspace separation and model selection. In Proceedings of 8th ICCV, Vancouver (vol. 3, pp. 586–591) |
| [25] | Kanatani, K. (2002). Evaluation and selection of models for motion segmentation. In 7th ECCV (vol. 3, pp. 335–349). · Zbl 1039.68662 |
| [26] | Lerman, G., & Zhang, T. (2011). Robust recovery of multiple subspaces by geometric \({{l_p}}\) l p minimization. Annals of Statistics, 39(5), 2686–2715. doi: 10.1214/11-AOS914 . · Zbl 1232.62097 · doi:10.1214/11-AOS914 |
| [27] | Levina, E., & Bickel, P. J. (2005). Maximum likelihood estimation of intrinsic dimension. In L. K. Saul, Y. Weiss, & L. Bottou (Eds.), Advances in neural information processing systems 17 (pp. 777–784). Cambridge, MA: MIT Press. |
| [28] | Liu, G., Lin, Z., & Yu, Y. (2010). Robust subspace segmentation by low-rank representation. In ICML. |
| [29] | Liu, G., Lin, Z., Yan, S., Sun, J., Yu, Y., & Ma, Y. (2013). Robust recovery of subspace structures by low-rank representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1), 171–184. doi: 10.1109/TPAMI.2012.88 . · doi:10.1109/TPAMI.2012.88 |
| [30] | Ma, Y. (2004). An invitation to 3-D vision: From images to geometric models. Interdisciplinary applied mathematics: Imaging, vision, and graphics. New York: Springer. |
| [31] | Ma, Y., Derksen, H., Hong, W., & Wright, J. (2007). Segmentation of multivariate mixed data via lossy coding and compression. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(9), 1546–1562. · doi:10.1109/TPAMI.2007.1085 |
| [32] | Ma, Y., Yang, A. Y., Derksen, H., & Fossum, R. (2008). Estimation of subspace arrangements with applications in modeling and segmenting mixed data. SIAM Review, 50(3), 413–458. · Zbl 1147.52010 · doi:10.1137/060655523 |
| [33] | Ozay, N., Sznaier, M., Lagoa, C., & Camps, O. (2010). GPCA with denoising: A moments-based convex approach. In IEEE conference on computer vision and pattern recognition (CVPR) (pp. 3209–3216). doi: 10.1109/CVPR.2010.5540075 . |
| [34] | Papadopoulo, T., & Lourakis, M. I. A. (2000). Estimating the jacobian of the singular value decomposition: Theory and applications. In Proceedings of the European conference on computer vision, ECCV 00 (pp. 554–570). New York: Springer. |
| [35] | Rao, S. R., Yang, A. Y., Sastry, S. S., & Ma, Y. (2010). Robust algebraic segmentation of mixed rigid-body and planar motions from two views. International Journal of Computer Vision, 88(3), 425–446. doi: 10.1007/s11263-009-0314-1 . · Zbl 1477.68413 · doi:10.1007/s11263-009-0314-1 |
| [36] | Roy, O., & Vetterli, M. (2007). The effective rank: A measure of effective dimensionality. In European signal processing conference (EUSIPCO) (pp. 606–610). |
| [37] | Soltanolkotabi, M., & Candès, E. J. (2012). A geometric analysis of subspace clustering with outliers. Annals of Statistics, 40(4), 2195–2238. doi: 10.1214/12-AOS1034 . · Zbl 1318.62217 · doi:10.1214/12-AOS1034 |
| [38] | Soltanolkotabi, M., Elhamifar, E., & Candes, E. (2013). Robust subspace clustering. ArXiv e-prints. |
| [39] | Tipping, M., & Bishop, C. (1999). Mixtures of probabilistic principal component analysers. Neural Computation, 11(2), 443–482. · doi:10.1162/089976699300016728 |
| [40] | Torr, P. H. S. (1998). Geometric motion segmentation and model selection. Philosophical Transactions of the Royal Society of London A, 356, 1321–1340. · Zbl 0902.68201 · doi:10.1098/rsta.1998.0224 |
| [41] | Tron, R., & Vidal, R. (2007). A benchmark for the comparison of 3-d motion segmentation algorithms. In IEEE conference on computer vision and pattern recognition, CVPR ’07 (pp. 1–8). doi: 10.1109/CVPR.2007.382974 . |
| [42] | Tseng, P. (2000). Nearest \(q\) q -flat to \(m\) m points. Journal of Optimization Theory and Applications, 105, 249–252. doi: 10.1023/A:1004678431677 . · Zbl 0971.90055 · doi:10.1023/A:1004678431677 |
| [43] | Vershynin, R. (2012). Introduction to the non-asymptotic analysis of random matrices. In Compressed sensing (pp. 210–268). Cambridge: Cambridge University Press. |
| [44] | Vidal, R. (2011). Subspace clustering. IEEE Signal Processing Magazine, 28(2), 52–68. doi: 10.1109/MSP.2010.939739 . · doi:10.1109/MSP.2010.939739 |
| [45] | Vidal, R., Ma, Y., & Sastry, S. (2005). Generalized principal component analysis (GPCA). IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(12), 1945–1959. · doi:10.1109/TPAMI.2005.244 |
| [46] | Vidal, R., Ma, Y., Soatto, S., & Sastry, S. (2006). Two-view multibody structure from motion. International Journal of Computer Vision, 68(1), 7–25. · Zbl 1477.68498 · doi:10.1007/s11263-005-4839-7 |
| [47] | Yan, J., & Pollefeys, M. (2006). A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and nondegenerate. In ECCV (vol. 4, pp. 94–106). |
| [48] | Yang, A. Y., Rao, S. R., & Ma, Y. (2006). Robust statistical estimation and segmentation of multiple subspaces. In CVPRW ’06: Proceedings of the 2006 conference on computer vision and pattern recognition workshop (p. 99). Washington, DC: IEEE Computer Society. doi: 10.1109/CVPRW.2006.178 . |
| [49] | Zhang, T., Szlam, A., & Lerman, G. (2009). Median \(K\) K -flats for hybrid linear modeling with many outliers. In IEEE 12th international conference on computer vision workshops (ICCV workshops), Kyoto (pp. 234–241). doi: 10.1109/ICCVW.2009.5457695 . |
| [50] | Zhang, T., Szlam, A., Wang, Y., & Lerman, G. (2010). Randomized hybrid linear modeling by local best-fit flats. In IEEE conference on computer vision and pattern recognition (CVPR) (pp. 1927–1934). doi: 10.1109/CVPR.2010.5539866 . |
| [51] | Zhang, T., Szlam, A., Wang, Y., & Lerman, G. (2012). Hybrid linear modeling via local best-fit flats. International Journal of Computer Vision, 100, 217–240. doi: 10.1007/s11263-012-0535-6 . · Zbl 1259.68207 · doi:10.1007/s11263-012-0535-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
