×

A \(p\)-adic RANSAC algorithm for stereo vision using Hensel lifting. (English) Zbl 1250.68269

Summary: A \(p\)-adic variation of the Ran(dom) Sa(mple) C(onsensus) method for solving the relative pose problem in stereo vision is developed. From two 2-adically encoded images a random sample of five pairs of corresponding points is taken, and the equations for the essential matrix are solved by lifting solutions modulo 2 to the 2-adic integers. A recently devised \(p\)-adic hierarchical classification algorithm imitiating the known LBG quantization method classifies the solutions for all the samples after having determined the number of clusters using the known intra-inter validity of clusterings. In the successful case, a cluster ranking will determine the cluster containing a 2-adic approximation to the “true” solution of the problem.

MSC:

68T45 Machine vision and scene understanding
68U10 Computing methodologies for image processing
12J25 Non-Archimedean valued fields

Software:

FIVEPOINT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Benois-Pineau, A. Yu. Khrennikov and N. V. Kotovich, ”Segmentation of images in p-adic and Euclidean metrics,” Dokl. Math. 64, 450–455 (2001). · Zbl 1042.68687
[2] P. E. Bradley, ”A dyadic solution of relative pose problems,” arXiv:0908.1919v3 (2009).
[3] P. E. Bradley, ”On p-adic classification,” p-Adic Numbers, Ultrametric Analysis and Applications 1(4), 271–285 (2009). · Zbl 1250.68221 · doi:10.1134/S2070046609040013
[4] P. E. Bradley, ”Degenerating families of dendrograms,” J. Class. 25, 27–42 (2008). · Zbl 1260.62040 · doi:10.1007/s00357-008-9009-5
[5] P. E. Bradley, ”Mumford dendrograms and discrete p-adic symmetries,” p-Adic Numbers, Ultrametric Analysis and Applications 1(2), 118–127 (2009). · Zbl 1264.14034 · doi:10.1134/S2070046609020034
[6] O. D. Faugeras and S. Maybank, ”Motion from point matches: multiplicity of solutions,” IJCV 4, 225–246 (1990). · Zbl 0722.51019 · doi:10.1007/BF00054997
[7] M. A. Fischler and R. C. Bolles, ”Random sample consensuns: A paradigm for model fitting with applications to image analysis and automated cartography,” Comm. ACM 24, 381–395 (1981). · doi:10.1145/358669.358692
[8] F. Q. Gouvca, p-Adic Numbers. An Introduction (Springer, 2003).
[9] R. Hartley, ”Projective reconstruction and invariants from multiple images,” T-PAMI 16, 1036–1040 (1994). · Zbl 05112542 · doi:10.1109/34.329005
[10] R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision (Cambridge Univ. Press, 2008). · Zbl 0956.68149
[11] T. S. Huang and A. N. Netravali, ”Motion and structure from feature correspondence: a review,” Proc. IEEE 82, 252–268 (1994). · doi:10.1109/5.265351
[12] M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1 (Springer, 2000). · Zbl 0956.13008
[13] E. Kruppa, ”Zur Ermittlung eines Objektes aus zwei Perspektiven mit innerer Orientierung,” Sitz.-Ber. Akad. Wiss., Wien, math. naturw. Kl. Abt. IIa 122, 1939–1948 (1913). · JFM 45.0776.04
[14] Z. Kukelova, M. Bujnak and T. Pajdla, ”Polynomial eigenvalue solutions to the 5-pt and 6-pt relative pose problems,” BMVC 2008, Leeds, UK, September 1–4 (2008).
[15] Y. Linde, A. Buzo and R. M. Gray, ”An algorithm for vector quantizer design,” IEEE Trans. Commun. 28, 84–95 (1980). · doi:10.1109/TCOM.1980.1094577
[16] H. C. Longuet-Higgins, ”A computer algorithm for reconstructing a scene from two projections,” Nature 293, 133–135 (1981). · doi:10.1038/293133a0
[17] F. Murtagh, ”On ultrametricity, data coding, and computation,” J. Class. 21, 167–184 (2004). · Zbl 1084.62052 · doi:10.1007/s00357-004-0015-y
[18] D. Nistér, ”An efficient solution to the five-point relative pose problem,” IEEE T-PAMI 26, 167–184 (2004). · Zbl 05111562 · doi:10.1109/TPAMI.2004.17
[19] J. Philip, ”A non-iterative algorithm for determining all essential matrices corresponding to five point pairs,” Photogrammetric Record 15, 589–599 (1996). · doi:10.1111/0031-868X.00066
[20] S. Ray and R. H. Turi, ”Determination of number of clusters in K-means clustering and application in colour image segmentation,” in Proc. ICAPRDT’99 (Calcutta, India 1999).
[21] H. Stewénius, C. Engels and D. Nistéer, Recent developments on direct relative orientation,” ISPRS J. Photogrammetry and Remote Sensing 60, 284–294 (2006). · doi:10.1016/j.isprsjprs.2006.03.005
[22] A. Weil, Basic Number Theory (Springer, 1973). · Zbl 0267.12001
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.