Algorithme de coupe énumérative pour la minimisation de fonction d'énergie

Algorithme de coupe énumérative pour la minimisation de fonction d'énergie

Cutting Enumerative Algorithm for the Minimizing of Energy Function

M.Douimi H.Cherifi 

[MI-INSA de Rouen, URA CNRS 137 8 B .P. 08, Place Emile Blondel, 76 131 Mont-Saint-Aignan Cedex

TSI, UMR CNRS 84 2 B .P. 505, 3 rue Javelin Pognon, 42 007 Saint-Etienne

Corresponding Author Email: 
douimi@lmi.insa-rouen.fr
Page: 
67-78
|
Received: 
5 December 1996
| |
Accepted: 
N/A
| | Citation

OPEN ACCESS

Abstract: 

We study the 1-D reconstruction problem of real-valued data . This problem can be formulated by minimizing the energy function or hamìltonien. To solve this problem, many methods have been proposed such as, simulated annealing (SA), the graduated nonconvexiiy (GNC), and mean field annealing (MFA). We propose a new algorithm called "Discontinuity Position Sweep" (in French Balayage par Position de Discontinuité: (BPD)) . This new algorithm comes from cutting enumerative methods in combinatorial optimization and its main advantages over the aforementioned methods are that it is parallelisable together, it is faster and it finds the better solution.

Résumé

Nous étudions le problème de reconstruction de données unidimensionnelle par minimisation de la fonction d'énergie ou hamiltonien. Plusieurs méthodes de relaxation, stochastique et déterministe, ont été proposées pour résoudre ce problème d'optimisation globale et non convexe, notamment le recuit simulé (SA), le recuit par champ moyen (MFA), et la non convexité graduelle (GNC) . Nous proposons un nouvel algorithme déterministe de coupe énumérative en optimisation combinatoire. Cet algorithme que nous appelons Balayage par Position de Discontinuité (BPD) permet d'obtenir des gains significatifs en terme de temps de calcul et de qualité de la solution obtenue . De plus, il est de nature parallélisable.

Keywords: 

Non convex global optimization, Markov random field, ligne process, intensity process, GNC algorithm, hypercube, Gray code

Mots clés

Optimisation globale et non convexe, champ de Markov, processus booléen, processus scalaire, algorithme GNC, hypercube, code de Gray

1. Introduction
2. Présentation d'un Modèle
3. Algorithme GNC
4. Algorithme BPD
5. Résultats Expérimentaux
6. Conclusion Et Perspectives
  References

[1] A.A. Amini, T.E . Weymouth & R .C. Jain (1990), «Using dynamic programming for solving variationnel problems en vision», IEEE Trans. on Pattern Anal. Mach. Intell., vol 12, n°, pp 855-867, Septembre 1990.

[2] A . Blake & A . Zisserman (1987), Visual Reconstruction, MIT Press, Cambridge 1987.

[3] A. Blake (1989), «Comparaison of the Efficency of Deterministic and Stochastic Algorithms for Visual Reconstruction», IEEE Trans. on Pattern Anal Mach. Intell., vol. 11, janv. 1989.

[4] M. Bertero, T.A . Poggio & V. Torre (1988), «Ill-posed problems in early vision», Procedings of the IEEE Vol. 76, n° 8, pp. 869-889, Août 1988.

[5] M. Basseville & B . Espiau & J . Gasnier (1981), «Edge Detection using Sequential Methods for Change in Level - Part I : A sequential edge detection algorithm», IEEE Trans. on Acoustics, Speech and Signal Processing, Vol. ASSSP-29, n° 1, Feb. 1981, pp . 24-31.

[6] M . Bassevile & A . Benhallam & all . (1992), «Fiches d'algorithmes de segmentation de signaux», Traitement du signal, Supplément au vol . 9, n ° 1, 1992 .

[7] J . Besag (1986), On the Statistical Analysis of Dirty Pictures», Royal Statistical Society, Vol. 48, n° 3, pp 259-302, 1986.

[8] A. De Cesare (1996), Algorithmes rapides de restauration des signaux : application à l'imagerie médicale . Thèse de l'Université de Paris-Sud, Février 1996 .

[9] B . Chalmond (1988), «Image restoration using an estimated Markov model» , Signal Processing, Vol. 15, pp . 115-129, 1988.

[10] JP. Cocquerez & S. Philipp (1991), «GDR 134 . Traitement du signal et images. Rapport Segmentation . lère partie : Prétraitement et approche frontière», Publication du CNRS, opération GDRS 134., (ouvrage collectif de synthèse), 1991.

[11] M. Cosnard & D . Trystram (1993), Algorithmes et architectures parallèles, Inter-Editions, 1993 .

[12] M . Douimi (1995), Modélisation markovienne et optimisation numérique pour la restauration des signaux en (ID) et (2D). Thèse de l'Université de Rouen, Oct. 1995.

[13] D . Geiger & F. Girosi, (1989) «Parallel and determinist algorithms for MRFs : surface reconstruction and integration», MITAI Memo 1114, Juin 1989.

[14] D. Geman & S . Geman (1984), «Stochastic Relaxation, Gibbs Distributions and the Baysian Restoration of Image», IEEE Trans. on Pattern Anal. Mach. Intell., Vol . 6, pp . 721-741, nov. 1984.

[15] G . Golub & C . H . Van Loan (1993), Matrix Computations, The Johns Hopkins University Press, Baltimore, London, 2 edition, 1993.

[16] R . Horst & H . Tuy (1993), Global optimization : Deterministic approaches, Springer-Verlag, Berlin, New York, 2 edition, 1993.

[17] R . Horst & P. M. Pardalos (1995), Nonconvex optimization and its applications . Handbook of Global Optimization, Kluwer Academic Publishers, Netherlands, 1995.

[18] M . Nielsen (1994), «Surface Reconstruction : GNCs and MFAs», Rapport INRIA N°2353, spetembre 1994.

[19] L. S . Jacoby, J . S . Kowalik & J . T . Pizzo (1972), Iterative Methods for Nonlinear Optimisation Problems. Prentice-Hall, Inc, New-Jersey, 1972.

[20] S . Kirpatrick, C. D. Gellatt, & M . P. Vecchi (1983), Optimization by simulated annealing, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1983.

[21] P. J . Laurent (1972), Approximation et Optimisation, Herman, Paris, 1972.

[22] D. Mumford & J . Shah (1985), «Boundary detection by minimizing functionals», In Proc. IEEE CVPR, pp . 22, 1985.

[23] T. Pavlidis & Y.T. Liow (1990), «Integrating Region Growing and Edge Detection», IEEE Trans. on PAMI, Vol . 12, N° 3, pp. 225-233, March 1990.

[24] W. Snyder, Y. Sik Han, G. Bilbro, R . Whitaker & S . Pizer (1995), "Image Relaxation : Restoration and Feature Extraction". In IEEE Transaction On Pattern Analysis and Machine Intelligence , Vol . 17 n° 6, june (1995).

[25] A . Tikhonov & V. Arsenine (1976), «Méthodes de résolution de problèmes mal posés» . Editions MIR , Moscou 1976.