×

A constrained-optimization based half-quadratic algorithm for robustly Fitting sets of linearly parametrized curves. (English) Zbl 1284.90060

Summary: We consider the problem of multiple fitting of linearly parametrized curves, that arises in many computer vision problems such as road scene analysis. Data extracted from images usually contain non-Gaussian noise and outliers, which makes classical estimation methods ineffective. In this paper, we first introduce a family of robust probability density functions which appears to be well-suited to many real-world problems. Also, such noise models are suitable for defining continuation heuristics to escape shallow local minima and their robustness is devised in terms of breakdown point. Second, the usual iterative reweighted least squares (IRLS) robust estimator is extended to the problem of robustly estimating sets of linearly parametrized curves. The resulting, non-convex optimization problem is tackled within a Lagrangian approach, leading to the so-called simultaneous robust multiple fitting (SRMF) algorithm, whose global convergence to a local minimum is proved using results from constrained optimization theory.

MSC:

90C26 Nonconvex programming, global optimization
62J05 Linear regression; mixed models
90C55 Methods of successive quadratic programming type
90C90 Applications of mathematical programming
62H12 Estimation in multivariate analysis
62H35 Image analysis in multivariate analysis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allain M, Idier J, Goussard Y (2006) On global and local convergence of half-quadratic algorithms. IEEE Trans Image Process 15(5): 1130–142 · Zbl 05452741 · doi:10.1109/TIP.2005.864173
[2] Aubert G, Kornprobst P (2006) Mathematical problems in image processing: partial differential equations and the calculus of variations. Applied Mathematical Sciences, vol 147. Springer, Berlin · Zbl 1110.35001
[3] Bigorgne E, Tarel J-P (2007) Backward segmentation and region fitting for geometrical visibility range estimation. In: Proceedings of Asian Conference on Computer Vision (ACCV’07), vol II. Tokyo, Japan, pp 817–826
[4] Black MJ, Rangarajan A (1996) On the unification of line processes, outlier rejection, and robust statistics with applications in early vision. Int J Comput Vis 19(1): 57–92 · Zbl 05475543 · doi:10.1007/BF00131148
[5] Blake A, Zisserman A (1987) Visual reconstruction. MIT Press, Cambridge
[6] Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge · Zbl 1058.90049
[7] Charbonnier P, Blanc-Féraud L, Aubert G, Barlaud M (1997) Deterministic edge-preserving regularization in computed imaging. IEEE Trans Image Process 6(2): 298–311 · doi:10.1109/83.551699
[8] Delaney AH, Bresler Y (1998) Globally convergent edge-preserving regularized reconstruction: an application to limited-angle tomography. IEEE Trans Image Process 7(2): 204–221 · doi:10.1109/83.660997
[9] Fischler MA, Bolles RC (1981) Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun ACM 24: 381–395 · doi:10.1145/358669.358692
[10] Geman S, Reynolds G (1992) Constrained restoration and the recovery of discontinuities. IEEE Trans Pattern Anal Mach Intell 14(3): 367–383 · Zbl 05110945 · doi:10.1109/34.120331
[11] Hampel FR, Ronchetti EM, Rousseeuw PJ, Stahel WA (1986) Robust statistics: an approach based on influence functions. Wiley, New York
[12] Huber PJ (1981) Robust statistics. Wiley, New York · Zbl 0536.62025
[13] Huber PJ (1984) Finite sample breakdown of M- and P-estimators. Ann Stat 12: 119–126 · Zbl 0557.62034 · doi:10.1214/aos/1176346396
[14] Ieng S-S, Tarel J-P, Charbonnier P (2007) Modeling non-Gaussian noise for robust image analysis. In: Proceedings of International Conference on Computer Vision Theory and Applications (VISAPP’07), Barcelona, Spain, pp 183–190
[15] Luenberger DG (1973) Introduction to linear and nonlinear programming. Addison-Wesley, Reading · Zbl 0297.90044
[16] Minoux M (1986) Mathematical programming: theory and algorithms. Wiley, Chichester · Zbl 0602.90090
[17] Mizera I, Müller C (1999) Breakdown points and variation exponents of robust M-estimators in linear models. Ann Stat 27: 1164–1177 · Zbl 0959.62029 · doi:10.1214/aos/1017938920
[18] Nosmas J-C (1999) Remarques sur un algorithme d’optimisation pour une classe de fonctionnelles sur $${\(\backslash\)mathbb{R}\^k}$$ . C R Acad Sci Sér 1 Math 328(12): 1237–1240 · Zbl 0933.65068
[19] Rousseeuw PJ, Leroy AN (1987) Robust regression and outlier detection. Wiley, New York · Zbl 0711.62030
[20] Srivastava A, Lee A, Simoncelli E, Zhu S (2003) On advances in statistical modeling of natural images. J Math Imaging Vis 1: 17–33 · Zbl 1033.68133 · doi:10.1023/A:1021889010444
[21] Tarel J-P, Ieng S-S, Charbonnier P (2007a) Robust lane marking detection by the half quadratic approach. Collections Etudes et Recherches des Laboratoires des Ponts et Chaussées, CR 49, LCPC, 74pp
[22] Tarel J-P, Charbonnier P, Ieng S-S (2007b) Simultaneous robust fitting of multiple curves. In: Proceedings of International Conference on Computer Vision Theory and Applications (VISAPP’07), Barcelona, Spain, pp 175–182
[23] Tarel J-P, Ieng S-S, Charbonnier P (2007c) Accurate and robust image alignment for road profile reconstruction. In: Proceedings of IEEE International Conference on Image Processing (ICIP’07), vol V. San Antonio, Texas, USA, pp 365–368
[24] Tarel J-P, Ieng S-S, Charbonnier P (2002) Using robust estimation algorithms for tracking explicit curves. In: European Conference on Computer Vision (ECCV’02), vol 1. Copenhagen, Denmark, pp 492–507 · Zbl 1034.68680
[25] Veit Th, Tarel J-P, Nicolle P, Charbonnier P (2008) Evaluation of road marking feature extraction. In: Proceedings of 11th IEEE Conference on Intelligent Transportation Systems (ITSC’08), Beijing, China, pp 174–181
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.