. Le-chemin, ou la chaîne) ? est un chemin descendant (ou une chaîne descendante) (sur G, pour P) si pour tout entier k ? [1

. Dans-un-graphe-À-sommets-valués,-un-chemin, s est de plus grande pente (sur G, pour P) si ? est un chemin (ou une chaîne) descendant(e) et si pour tout entier k ? [1; ], P(s k ) = min{P(y) | y ? ?(s k?1 )}. Dans un graphe à arcs valués (ou arêtes valuées), un chemin d'arcs (ou une chaîne d'arêtes) ? = a 0, est de plus grande pente (sur G pour P) si ? est un chemin (ou une chaîne) descendant(e) et si pour tout entier k ? [1; ], P(a k ) = min{P(y) | y ? ?(a k?1 )}

. Altitude-d-'un-chemin, avec une application de poids P. Soit E l'ensemble d'éléments de G sur lequel s'effectue la pondération Soit un chemin (ou une chaîne) ? = x 0 , . . . , x avec pour tout entier k ? [0; ], x k ? E. L'altitude, du chemin (ou de la chaîne) ? (pour P sur G), noté H P (?), ou plus simplement H(?) lorsqu'il n'y a pas d'ambiguïté sur l'application de poids considérée, {P(x k )})

E. Soient-x-et-y-deux-Éléments-de, On note ?(x, y) l'ensemble des chemins dans G allant de x à y. Soient X et Y deux sous-graphes de G. On note ?(X, Y) l'ensemble des chemins, y?Y {?(x, y)})

X. De-même-sousgraphes, G. De, H. , and Y. , ou plus simplement H(X, Y) lorsqu'il n'y a pas d'ambiguïté sur l'application de poids considérée, est l'altitude la plus basse des, ) {H P (?)})

L. Sur-graphes-À-sommets-valués and .. , 77 3.2.2 LPE inter-sommets par immersion, p.92

R. Et-cloisonnement-par-ravinement-d-'arêtes and .. , 91 3.14 LPE topologique de sommets et représentations topographiques d'étapes intermédiaires, p.93

". Définitions-"-classiques, 121 4.2 Définitions relatives à un sous-graphe, p.121

.. Coupe-minimale-relative-sur-graphe-non-orienté, 157 5.10 Approximation de multiway cut minimale selon [66] qui n'est pas une multiway cut, p.160

. Problème, images peuvent se ramener à un problème d'étiquetage, autrement dit, comment attribuer la bonne étiquette à chaque élément du problème concerné Nous débutons ce chapitre en définissant ce qu'est un problème d'étiquetage, puis nous rappelons comment celui-ci peut se résoudre dans un cadre probabiliste avec les champs aléatoires de Markov avant de le ramener à un problème de minimisation d'éner- gie. La seconde partie de ce chapitre est consacrée aux méthodes de résolution de tels problèmes reposant sur les coupes minimales de graphes. Nous commençons en traitant le cas d'un problème à seulement deux étiquettes et montrons comment il a pu être étendu pour obtenir un résultat approché dans le cas général ou bien encore un résultat optimal sous certaines conditions Une de ces méthodes est, par la suite, utilisée dans les deux applications présentées dans les chapitres 7 et 8. Les méthodes de résolution par {?, ?}-swaps ou par ?-expansions présentées dans la section 6.2.2 ont été légèrement modifiées par rapport à leurs versions d'origines parues dans, Ces modifications, mises en évidence dans les remarques 6.9 et 6, p.38

.. Problème-d-'étiquetage, 177 6.1.2 Champs aléatoires de Markov et minimisation d'énergie

.. Étiquetage-binaire, 183 6.2.2 Cas général

.. 'un-champ-de-markov, 178 6.2 Configurations possibles de coupes pour deux sites voisins dans un problème d'étiquetage binaire, p.184

I. Minimisation-par-graphe, 208 1. Nous créons une partition des triangles du maillage en assignant à chacun d'eux une image dont la texture y sera projetée de sorte à minimiser la visibilité de la jointure susceptible d'apparaître quand deux triangles voisins se

. Ensuite, nous procédons à un mélange d'images sur la texture obtenue de sorte à faire disparaître la jointure pouvant résulter de la première étape puisque celle-ci, bien que minimale, n'est pas nécessairement nulle. Pour se faire, il nous a fallu étendre le mélange multi-fréquences de deux images présenté dans

D. Enfin and . La, but de réduire l'espace mémoire occupé, nous construisons un atlas de la texture obtenue à l'étape précédente (voir section 8

.. Pyramide-laplacienne, 253 8.13 Reconstruction de l'image originale et de la pyramide gaussienne à partir de la pyramide laplacienne, p.254

W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Mathematische Annalen, vol.99, issue.1, pp.118-133, 1928.
DOI : 10.1007/BF01459088
URL : http://www.digizeitschriften.de/download/PPN235181684_0099/PPN235181684_0099___log9.pdf

D. Adalsteinsson and A. James, A Fast Level Set Method for Propagating Interfaces, Journal of Computational Physics, vol.118, issue.2, pp.269-277, 1995.
DOI : 10.1006/jcph.1995.1098

K. Ravindra, T. L. Ahuja, . Magnanti, and B. James, Orlin : Network flows : theory, algorithms, and applications, 1993.

K. Ravindra, . Ahuja, and B. James, Orlin : A fast and simple algorithm for the maximum flow problem. Rapport technique 1905-87, 1987.

K. Ravindra, J. B. Ahuja, and . Orlin-et-robert-endre-tarjan, Improved time bounds for the maximum flow problem, 1987.

K. Ravindra, J. B. Ahuja, and . Orlin-et-robert-endre-tarjan, Improved time bounds for the maximum flow problem, Society for Industrial and Applied Mathematics Journal on Computing, vol.18, issue.5, pp.939-954, 1989.

C. Allène, J. Audibert, M. Couprie, J. Cousty, and R. Keriven, Some links between min-cuts, optimal spanning forests and watersheds, pp.47-128, 2007.

C. Allène, J. Audibert, M. Couprie, J. Cousty, and R. Keriven, Some links between min-cuts, optimal spanning forests and watersheds, Proceedings of the 8th International Symposium on Mathematical Morphology, pp.253-264, 2007.

C. Allène and N. Paragios, Image renaissance using discrete optimization and the alpha-expansion algorithm, 2005.

C. Allène and N. Paragios, Image Renaissance Using Discrete Optimization, 18th International Conference on Pattern Recognition (ICPR'06), 2006.
DOI : 10.1109/ICPR.2006.686

C. Allène, J. Pons, and R. Keriven, Seamless image-based texture atlases using multi-band blending, 2008 19th International Conference on Pattern Recognition, 2008.
DOI : 10.1109/ICPR.2008.4761913

B. Appleton and H. Talbot, Globally minimal surfaces by continuous maximal flows, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, issue.1, pp.106-118, 2006.
DOI : 10.1109/TPAMI.2006.12
URL : https://hal.archives-ouvertes.fr/hal-00621983

M. Sanjeev, S. Arulampalam, N. J. Maskell, T. C. Gordon, and . Clapp, A tutorial on particle filters for on-line non-linear/non-Gaussian Bayesian tracking, IEEE Transactions on Signal Processing, vol.50, issue.2, pp.174-188, 2002.

R. Audigier, R. De-alencar, and . Lotufo, Tie-Zone Watershed, Bottlenecks, and Segmentation Robustness Analysis, XVIII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI'05), pp.55-62, 2005.
DOI : 10.1109/SIBGRAPI.2005.48

R. Audigier, R. De-alencar, and . Lotufo, Duality between the Watershed by Image Foresting Transform and the Fuzzy Connectedness Segmentation Approaches, 2006 19th Brazilian Symposium on Computer Graphics and Image Processing, pp.53-60, 2006.
DOI : 10.1109/SIBGRAPI.2006.14

R. Audigier, R. De-alencar, and . Lotufo, Watershed by image foresting transform, tie-zone, and theoretical relationships with other watershed definitions, Proceedings of the 8th International Symposium on Mathematical Morphology, pp.277-288, 2007.

R. Audigier, R. De-alencar-lotufo, and M. Couprie, The tie-zone watershed: definition, algorithm and applications, IEEE International Conference on Image Processing 2005, 2005.
DOI : 10.1109/ICIP.2005.1530140
URL : https://hal.archives-ouvertes.fr/hal-00622250

A. Baumberg, Blending Images for Texturing 3D Models, Procedings of the British Machine Vision Conference 2002, pp.404-413, 2002.
DOI : 10.5244/C.16.38

R. Beare, Efficient implementation of the locally constrained watershed transform and seeded region growing, Proceedings of the 7th International Symposium on Mathematical Morphology, pp.217-226, 2005.

W. Lowell and . Beineke, On derived graphs and digraphs, pp.17-33, 1968.

C. Berge, Graph Theory, The American Mathematical Monthly, vol.71, issue.5, 1962.
DOI : 10.2307/2312582

F. Bernardini, I. M. Martin, and H. Rushmeier, High-quality texture reconstruction from multiple scans, IEEE Transactions on Visualization and Computer Graphics, vol.7, issue.4, pp.318-332, 2001.
DOI : 10.1109/2945.965346

M. Bertalmío, V. Caselles, G. Haro, and G. Sapiro, PDE-Based Image and Surface Inpainting, Handbook of mathematical models in computer vision, chapitre 3, pp.33-61, 2005.
DOI : 10.1007/0-387-28831-7_3

M. Bertalmío and G. Sapiro, Vicent Caselles et Coloma Ballester : Image inpainting, Proceedings of the 27th International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp.417-424, 2000.

G. Bertrand, On Topological Watersheds, Journal of Mathematical Imaging and Vision, vol.34, issue.6, pp.217-230, 2005.
DOI : 10.1007/s10851-005-4891-5
URL : https://hal.archives-ouvertes.fr/hal-00622398

E. Julian and . Besag, Spatial interaction and the statistical analysis of lattice systems, Journal of Royal Statistical Society, issue.36, pp.192-236, 1974.

E. Julian and . Besag, On the statistical analysis of dirty pictures, Journal of the Royal Statistical Society, vol.48, pp.259-302, 1986.

S. Beucher, Watershed, Hierarchical Segmentation and Waterfall Algorithm, Proceedings of the Mathematical Morphology and its Applications to Image Processing, pp.69-76, 1994.
DOI : 10.1007/978-94-011-1040-2_10

S. Beucher and C. Lantuéjoul, Use of watersheds in contour detection, Proceedings of the International Workshop on Image Processing Real-Time Edge and Motion Detection/Estimation, pp.75-77, 1979.

S. Beucher and F. Meyer, The morphological approach to segmentation : the watershed transformation, éditeur : Mathematical Morphology in Image Processing, chapitre 12, pp.433-481, 1993.

Y. Boykov and V. Kolmogorov, An experimental comparison of mincut/max-flow algorithms for energy minimization in vision, Proceedings of the 2nd International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, pp.359-374, 2001.

Y. Boykov and V. Kolmogorov, An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.26, issue.9, pp.1124-1137, 2004.
DOI : 10.1109/TPAMI.2004.60

Y. Boykov and O. Veksler, Graph cuts in vision and graphics : theories and applications. In Handbook of mathematical models in computer vision, pp.79-96, 2005.

Y. Boykov, O. Veksler, and R. Zabih, Markov random fields with efficient approximations, Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231), pp.648-655, 1998.
DOI : 10.1109/CVPR.1998.698673
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.118.3857

Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, Proceedings of the 7th IEEE International Conference on Computer Vision, pp.377-384, 1999.

Y. Boykov, O. Veksler, and R. Zabih, A New Algorithm for Energy Minimization with Discontinuities, Proceedings of the 2nd International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, pp.205-220, 0191.
DOI : 10.1007/3-540-48432-9_15

Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.23, issue.11, pp.1222-1239, 2001.
DOI : 10.1109/34.969114
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.6806

M. Brown and D. G. Lowe, Recognising panoramas, Proceedings Ninth IEEE International Conference on Computer Vision, pp.1218-1225, 2003.
DOI : 10.1109/ICCV.2003.1238630

T. Brox, A. Bruhn, and J. Weickert, Variational Motion Segmentation with Level Sets, Proceedings of the 9th European Conference on Computer Vision, pp.471-483, 2006.
DOI : 10.1007/11744023_37
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.86.5468

J. Peter, . Burt, and H. Edward, Adelson : The Laplacian pyramid as a compact image code, IEEE Transactions on Communications, COM, issue.4, pp.31532-540, 1983.

J. Peter, . Burt, and H. Edward, Adelson : A multiresolution spline with application to image mosaics, Proceedings of the 10th International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp.217-236, 1983.

V. Caselles, G. Sapiro, C. Ballester, M. Bertalmío, and J. Verdera, Filling-in by joint interpolation of vector fields and grey levels, IEEE Transactions on Image Processing, vol.10, pp.1200-1211, 2001.

A. Cayley, On contour and slope lines. The London, Edinburgh and Dublin Philosophical Magazine and Journal of Science, vol.18, issue.120, pp.264-268
DOI : 10.1017/cbo9780511703706.025

B. Chalmond, Éléments de modélisation pour l'analyse d'images, de Mathématiques et applications, 2000.

F. Tony, J. Chan, and . Shen, Mathematical models of local non-texture inpaintings, Society for Industrial and Applied Mathematics Journal on Applied Mathematics, vol.62, pp.1019-1043, 2001.

F. Tony, J. Chan, and . Shen, Non-texture inpaintings by curvature-driven diffusions (CDD), Journal of Visual Communication and Image Representation, vol.12, issue.4, pp.436-449, 2001.

B. Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the ACM, vol.47, issue.6, pp.1028-1047, 2000.
DOI : 10.1145/355541.355562

L. D. Cohen, Minimal paths and fast marching methods for image analysis In Handbook of mathematical models in computer vision, pp.97-111, 2005.

D. Laurent, R. Cohen, and . Kimmel, Fast marching the global minimum of active contours, Proceedings of the 3rd IEEE International Conference on Image Processing, pp.473-476, 1996.

D. Laurent, R. Cohen, and . Kimmel, Global minimum for active contour models : a minimal path approach, International Journal of Computer Vision, vol.24, issue.1, pp.57-78, 1997.

W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver, Combinatorial optimization, 1998.
DOI : 10.1002/9781118033142
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.227.8315

H. Thomas, C. E. Cormen, R. L. Leiserson, and . Rivest, Introduction to algorithms, second edition, p.22, 2001.

M. Couprie and G. Bertrand, Topological grayscale watershed transformation, SPIE Vision Geometry VI Proceedings, pp.136-146, 1997.
URL : https://hal.archives-ouvertes.fr/hal-00622030

M. Couprie, L. Najman, and G. Bertrand, Quasi-Linear Algorithms for the Topological Watershed, Journal of Mathematical Imaging and Vision, vol.13, issue.6, pp.231-249, 2005.
DOI : 10.1007/s10851-005-4892-4
URL : https://hal.archives-ouvertes.fr/hal-00622399

J. Cousty, G. Bertrand, L. Najman, and M. Couprie, Fusion graphs : merging properties and watersheds. Rapport technique IGM2005-04, pp.58-60, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00622473

J. Cousty, G. Bertrand, L. Najman, and M. Couprie, Watershed cuts, Proceedings of the 8th International Symposium on Mathematical Morphology, pp.301-312, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00622036

J. Cousty, G. Bertrand, L. Najman, and M. Couprie, Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.31, issue.8, pp.99-105, 2007.
DOI : 10.1109/TPAMI.2008.173
URL : https://hal.archives-ouvertes.fr/hal-00622410

J. Cousty, M. Couprie, L. Najman, and G. Bertrand, Grayscale Watersheds on Perfect Fusion Graphs, Proceedings of the 11th International Workshop on Combinatorial Image Analysis, pp.60-73, 2006.
DOI : 10.1007/11774938_6
URL : https://hal.archives-ouvertes.fr/hal-00622038

J. Cousty, M. Couprie, L. Najman, and G. Bertrand, Weighted fusion graphs: Merging properties and watersheds, Discrete Applied Mathematics, vol.156, issue.15, pp.92-97, 2007.
DOI : 10.1016/j.dam.2008.01.005
URL : https://hal.archives-ouvertes.fr/hal-00622473

A. Criminisi, P. Pérez, and K. Toyama, Object removal by exemplarbased inpainting, Proceedings of the 2003 IEEE Computer Society conference on Computer Vision and Pattern Recognition, pp.721-728, 2003.
DOI : 10.1109/cvpr.2003.1211538
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.120.6785

C. Gruia, H. Karloff, and Y. Rabani, An improved approximation algorithm for multiway cut, Journal of Computer and System Sciences, vol.60, issue.3, pp.564-574, 2000.

H. William and . Cunningham, The optimal multiterminal cut problem, Reliability of computer and communication networks de DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp.105-120, 1991.

E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, and D. Paul, Seymour et Mihalis Yannakakis : The complexity of multiway cuts, Unpublished extended abstract, 1983.

E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, The complexity of multiway cuts, Proceedings of the 24th Annual Association for Computing Machinery Symposium on the Theory of Computing, pp.241-251, 1992.

E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, and D. Paul, Seymour et Mihalis Yannakakis : The complexity of multiterminal cuts, Society for Industrial and Applied Mathematics Journal on Computing, vol.23, issue.138, pp.864-894, 1994.

G. Bernard, D. , and D. R. Fulkerson, On the max-flow min-cut theorem of networks, Linear inequalities and related systems, pp.225-231

E. Paul, C. J. Debevec, J. Taylor, and . Malik, Modeling and rendering architecture from photographs : a hybrid geometry and image-based approach, Proceedings of the 23rd International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp.11-20, 1996.

D. G. , D. , and K. Simon, A dynamic algorithm for line graph recognition, Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science, pp.37-48, 1995.

H. Digabel and C. Lantuéjoul, Iterative algorithm, Proceedings of the 2nd European Symposium on Quantitive Analysis of Microstructures in Material Science, 1977.

A. Doucet, On sequential simulation-based methods for Bayesian filtering Rapport technique CUED, 1998.

A. Doucet, N. De-freitas, and N. J. Gordon, Sequential Monte Carlo methods in practice, 2001.
DOI : 10.1007/978-1-4757-3437-9

A. Doucet, S. Godsill, and C. Andrieu, On sequential Monte Carlo sampling methods for Bayesian filtering, Statistics and Computing, vol.10, issue.3, pp.197-208, 2000.
DOI : 10.1023/A:1008935410038

R. Dupont, O. Juan, and R. Keriven, Robust Segmentation of Hidden Layers in Video Sequences, 18th International Conference on Pattern Recognition (ICPR'06), 2006.
DOI : 10.1109/ICPR.2006.1016

J. Edmonds and R. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM, vol.19, issue.2, pp.248-264, 1972.
DOI : 10.1145/321694.321699

A. A. Efros and W. T. Freeman, Image quilting for texture synthesis and transfer, Proceedings of the 28th annual conference on Computer graphics and interactive techniques , SIGGRAPH '01, pp.341-346, 2001.
DOI : 10.1145/383259.383296

A. A. Efros and T. K. Leung, Texture synthesis by non-parametric sampling, Proceedings of the Seventh IEEE International Conference on Computer Vision, pp.1033-1038, 1999.
DOI : 10.1109/ICCV.1999.790383
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.2805

S. Esedoglu and J. Shen, Digital inpainting based on the Mumford???Shah???Euler image model, European Journal of Applied Mathematics, vol.13, issue.04, pp.353-370, 2002.
DOI : 10.1017/S0956792502004904

L. Euler, Solutio problematis ad geometriam situs pertinentis Commentarii Academiae Scientiarum Imperialis Petropolitanae, pp.128-140

A. X. Falcão, J. Stolfi, R. De-alencar, and . Lotufo, The image foresting transform: theory, algorithms, and applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.26, issue.1, pp.19-29, 2004.
DOI : 10.1109/TPAMI.2004.1261076

F. Pedro, . Felzenszwalb, and P. Daniel, Huttenlocher : Efficient belief propagation for early vision, Proceedings of the 2004 IEEE Computer Society conference on Computer Vision and Pattern Recognition, pp.261-268, 2004.

L. R. , S. Ford, and D. R. Fulkerson, Maximal flow through a network, Canadian Journal of Mathematics, vol.8, pp.399-404, 1956.

L. R. , S. Ford, and D. R. Fulkerson, Flows in networks, pp.146-154, 1962.

D. Freedman and P. Drineas, Energy Minimization via Graph Cuts: Settling What is Possible, 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), pp.939-946, 2005.
DOI : 10.1109/CVPR.2005.143
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.1348

N. Garg, V. V. Vazirani, and M. Yannakakis, Approximate max-flow min-(multi)cut theorems and their applications, Society for Industrial and Applied Mathematics Journal on Computing, vol.25, pp.698-707, 1996.
DOI : 10.1137/s0097539793243016
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.3217

D. Geman, S. Geman, C. Graffigne, and P. Dong, Boundary detection by constrained optimization, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.12, issue.7, pp.609-628, 1990.
DOI : 10.1109/34.56204

S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions and the bayesian restoration of images, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.6, pp.721-741, 1984.

A. V. Goldberg and E. Tardos-et-robert-endre-tarjan, Network flow algorithm ,. Paths, flows and VLSI-design, pp.101-164, 1998.

V. Andrew and . Goldberg-et-robert-endre-tarjan, A new approach to the maximum flow problem, Proceedings of the 18th annual Association for Computing Machinery Symposium on Theory of Computing, pp.136-146, 1986.

V. Andrew and . Goldberg-et-robert-endre-tarjan, Finding minimum-cost circulations by successive approximations, pp.153-211, 1987.

V. Andrew and . Goldberg-et-robert-endre-tarjan, A new approach to the maximumflow problem, Journal of the Association for Computing Machinery, vol.35, issue.4, pp.921-940, 1988.

O. Goldschmidt and S. Dorit, Hochbaum : Polynomial algorithm for the k-cut problem, Proceedings of the 29th annual Symposium on Foundations of Computer Science, pp.444-451, 1988.

O. Goldschmidt and S. Dorit, A Polynomial Algorithm for the k-cut Problem for Fixed k, Mathematics of Operations Research, vol.19, issue.1, pp.24-37, 1994.
DOI : 10.1287/moor.19.1.24

O. Goldschmidt and B. David, Shmoys : An O(|V| 2 ) algorithm for the planar 3-cut problem, Journal on Algebraic and Discrete Methods, vol.6, issue.4, pp.707-712, 1985.

N. J. Gordon, D. J. Salmond-et-adrian, and F. M. Smith, Novel approach to nonlinear/non-Gaussian Bayesian state estimation, IEE Proceedings F on Radar and Signal Processing, pp.107-113, 1993.
DOI : 10.1049/ip-f-2.1993.0015

R. E. Nuno, A. C. Gracias, S. Gleason, . Negahdaripour, and H. Mohammad, Mahoor : Fast image blending using watersheds and graph cuts, Proceedings of the 17th British Machine Vision Conference, pp.469-478, 2006.

L. Grady, Random Walks for Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, issue.11, pp.1768-1783, 2006.
DOI : 10.1109/TPAMI.2006.233

D. M. Greig, B. T. Porteous, and A. H. , Seheult : Discussion of : On the statistical analysis of dirty pictures (by j. e. besag.), Journal of the Royal Statistical Society, vol.48, pp.282-284, 1986.

D. M. Greig, B. T. Porteous, and A. H. Seheult, Exact maximum a posteriori estimation for binary images, Journal of the Royal Statistical Society, vol.51, issue.2, pp.271-279, 1989.

J. David, J. R. Heeger, and . Bergen, Pyramid-based texture analysis/synthesis, Proceedings of the 22nd International Computer on Computer Graphics and Interactive Techniques (SIGGRAPH), pp.229-238, 1995.

T. C. Hu, Integer programming and network flows, 1969.

H. Igehy and L. Pereira, Image replacement through texture synthesis, Proceedings of International Conference on Image Processing, pp.186-189, 1997.
DOI : 10.1109/ICIP.1997.632049
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.3414

H. Ishikawa, Exact optimization for markov random fields with convex priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.25, issue.10, pp.1333-1336, 2003.
DOI : 10.1109/TPAMI.2003.1233908

H. Ishikawa and D. Geiger, Occlusions, discontinuities, and epipolar lines in stereo, Proceedings of the 5th European Conference on Computer Vision, pp.232-248, 1998.
DOI : 10.1007/BFb0055670

Z. Jankó, Photorealistic 3D models of real-world objects, Thèse de doctorat, 2007.

Z. Jankó and D. Chetverikov, Photo-consistency based registration of an uncalibrated image pair to a 3D surface model using genetic algorithm, Proceedings. 2nd International Symposium on 3D Data Processing, Visualization and Transmission, 2004. 3DPVT 2004., pp.616-622, 2004.
DOI : 10.1109/TDPVT.2004.1335296

C. Jordan, Nouvelles observations sur les lignes de faîte et de thalweg Comptes rendus des séances de l'académie des sciences, pp.1023-1025

O. Juan and Y. Boykov, Active cuts for real-time graph partitioning in vision, 2005.

O. Juan and Y. Boykov, Active Graph Cuts, 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Volume 1 (CVPR'06), pp.1023-1029, 2006.
DOI : 10.1109/CVPR.2006.47

G. Kanizsa, Gramática de la visión. Paidos, 1986.

R. Manning and K. , Reducibility among combinatorial problems, Complexity of Computer Computations, pp.85-103, 1972.

A. V. Karzanov, Determining the maximal flow in network by the method of preflows, Soviet Mathematics Doklady, vol.15, pp.434-437, 1974.

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by Simulated Annealing, Science, vol.220, issue.4598, pp.671-680, 1983.
DOI : 10.1126/science.220.4598.671

P. Kohli, H. S. Philip, and . Torr, Effciently solving dynamic markov random fields using graph cuts, Proceedings of the 10th IEEE International Conference on Computer Vision, pp.922-929, 2005.

P. Kohli, H. S. Philip, and . Torr, Dynamic Graph Cuts for Efficient Inference in Markov Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, issue.12, pp.2079-2088, 2007.
DOI : 10.1109/TPAMI.2007.1128

C. Anil and . Kokaram, On missing data treatment for degraded video and film archives : a survey and a new Bayesian approach, IEEE Transactions on Image Processing, vol.13, pp.397-415, 2004.

V. Kolmogorov, Convergent Tree-Reweighted Message Passing for Energy Minimization, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, issue.10, pp.1568-1583, 2006.
DOI : 10.1109/TPAMI.2006.200

V. Kolmogorov and C. Rother, Comparison of Energy Minimization Algorithms for Highly Connected Graphs, 2006.
DOI : 10.1109/TIT.2005.856938

V. Kolmogorov and R. Zabih, What Energy Functions Can Be Minimized via Graph Cuts?, Proceedings of the 7th European Conference on Computer Vision, pp.65-81, 2002.
DOI : 10.1007/3-540-47977-5_5

N. Komodakis and G. Tziritas, Image Completion Using Global Optimization, 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Volume 1 (CVPR'06), pp.442-452, 2006.
DOI : 10.1109/CVPR.2006.141
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.98.9858

N. Komodakis and G. Tziritas, Approximate Labeling via Graph Cuts Based on Linear Programming, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, issue.8, pp.1436-1453, 2007.
DOI : 10.1109/TPAMI.2007.1061
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.9745

N. Komodakis, G. Tziritas, and N. Paragios, Fast, Approximately Optimal Solutions for Single and Dynamic MRFs, 2007 IEEE Conference on Computer Vision and Pattern Recognition, pp.1-8, 2007.
DOI : 10.1109/CVPR.2007.383095

N. Komodakis, G. Tziritas, and N. Paragios, Performance vs computational efficiency for optimizing single and dynamic MRFs: Setting the state of the art with primal-dual strategies, Computer Vision and Image Understanding, vol.112, issue.1, pp.14-29, 2008.
DOI : 10.1016/j.cviu.2008.06.007
URL : https://hal.archives-ouvertes.fr/hal-00918699

B. Korte and J. Vygen, Combinatorial optimization : theory and algorithms. Algorithms and Combinatorics, pp.123-124, 2000.

J. Bernard and J. Kruskal, On the shortest spanning tree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, pp.48-50, 1956.

V. Kwatra, A. Schödl, I. Essa, G. Turk, and A. Bobick, Graphcut textures : image and video synthesis using graph cuts, Proceedings of the 30th International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp.277-286, 2003.
DOI : 10.1145/1201775.882264

P. Labatut, J. Pons, and R. Keriven, Efficient Multi-View Reconstruction of Large-Scale Scenes using Interest Points, Delaunay Triangulation and Graph Cuts, 2007 IEEE 11th International Conference on Computer Vision, 2007.
DOI : 10.1109/ICCV.2007.4408892

E. G. and H. Landau, Handbuch der lehre von der verteilung der primzahlen . Teubner, 1909.

G. H. Philippe, Lehot : An optimal algorithm to detect a line graph and output its root graph, Journal of the Association for Computing Machinery, vol.21, issue.4, pp.569-575, 1974.

S. Victor, . Lempitsky, and V. Denis, Ivanov : Seamless mosaicing of image-based texture maps, Proceedings of the 2007 IEEE Computer Society conference on Computer Vision and Pattern Recognition, pp.236-243, 2007.

S. Victor, C. Lempitsky, A. Rother, and . Blake, Logcut -Efficient graph cut optimization for Markov random fields, Proceedings of the 11th IEEE International Conference on Computer Vision, 2007.

P. A. Hendrik, W. Lensch, H. Heidrich, and . Seidel, A silhouettebased algorithm for texture registration and stitching, Graphical Models, vol.63, issue.4, pp.245-262, 2001.

B. Lévy, S. Petitjean, N. Ray, and J. Maillot, Least squares conformal maps for automatic texture atlas generation, Proceedings of the 29th International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp.362-371, 2002.

L. Shengping-ziqing, Markov random field modeling in computer vision, 1995.

W. Lin, J. H. Hays, C. Wu, V. Kwatra, and Y. Liu, A comparison study of four texture synthesis algorithms on regular and near-regular textures . Rapport technique CMU-RI-TR-04-01, 2004.

H. Lombaert, Y. Sun, L. Grady, and C. Xu, A multilevel banded graph cuts method for fast image segmentation, Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, pp.259-265, 2005.
DOI : 10.1109/ICCV.2005.13

S. Masnou and J. Morel, Level lines based disocclusion, Proceedings 1998 International Conference on Image Processing. ICIP98 (Cat. No.98CB36269), pp.259-263, 1998.
DOI : 10.1109/ICIP.1998.999016

J. Maxwell, On Hills and Dales, Philosophical Magazine, vol.4, issue.269, pp.40421-427
DOI : 10.1017/CBO9780511710377.018

F. Meyer, Minimum Spanning Forests for Morphological Segmentation, Proceedings of the 2nd International Conference on Mathematical Morphology and its Applications to Image Processing, pp.77-84, 1994.
DOI : 10.1007/978-94-011-1040-2_11

F. Meyer, Topographic distance and watershed lines, Signal Processing, vol.38, issue.1, pp.113-125, 1994.
DOI : 10.1016/0165-1684(94)90060-4

F. Meyer, Levelings : theory and practice. In Handbook of mathematical models in computer vision, chapitre 4, pp.65-78, 2005.
DOI : 10.1007/0-387-28831-7_4

F. Meyer and S. Beucher, Morphological segmentation, Journal of Visual Communication and Image Representation, vol.1, issue.1, pp.21-46, 1990.
DOI : 10.1016/1047-3203(90)90014-M

F. Meyer and L. Najman, Morphologie mathématique 1 : approches déterministes , chapitre Segmentation, arbre de poids minimum et hiérarchies Traité IC2, série signal et image, pp.201-232, 2008.

F. Meyer and C. Vachier, Image segmentation based on viscous flooding simulation, Proceedings of the 6th International Symposium on Mathematical Morphology, pp.69-78, 2002.

H. Nagamochi and T. Ibaraki, Computing Edge-Connectivity in Multigraphs and Capacitated Graphs, SIAM Journal on Discrete Mathematics, vol.5, issue.1, pp.54-66, 1992.
DOI : 10.1137/0405004

L. Najman and M. Couprie, Building the Component Tree in Quasi-Linear Time, IEEE Transactions on Image Processing, vol.15, issue.11, pp.3531-3539, 2006.
DOI : 10.1109/TIP.2006.877518
URL : https://hal.archives-ouvertes.fr/hal-00622110

L. Najman, M. Couprie, and G. Bertrand, Watersheds, mosaics, and the emergence paradigm, Discrete Applied Mathematics, vol.147, issue.2-3, pp.301-324, 2005.
DOI : 10.1016/j.dam.2004.09.017
URL : https://hal.archives-ouvertes.fr/hal-00622113

L. Najman and M. Schmitt, Watershed of a continuous function, Signal Processing, vol.38, issue.1, pp.99-112, 1994.
DOI : 10.1016/0165-1684(94)90059-0
URL : https://hal.archives-ouvertes.fr/hal-00622129

L. Najman and M. Schmitt, Geodesic saliency of watershed contours and hierarchical segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.18, issue.12, pp.1163-1173, 1996.
DOI : 10.1109/34.546254
URL : https://hal.archives-ouvertes.fr/hal-00622128

J. Ne?, Eva Milková et Helena Ne? set ? rilova : Otakar Boruvka on minimum spanning tree problem : Translation of both the 1926 papers, comments, history, Discrete Mathematics, vol.233, pp.3-36, 2001.

T. Hieu, Q. Nguyen, and . Ji, Improved watershed segmentation using water diffusion and local shape priors, Proceedings of the 2006 IEEE Computer Society conference on Computer Vision and Pattern Recognition, pp.985-992, 2006.

M. Nitzberg, D. Mumford, and T. Shiota, Filtering, segmentation and depth, 1993.
DOI : 10.1007/3-540-56484-5

S. Osher and A. James, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, vol.79, issue.1, pp.12-49, 1988.
DOI : 10.1016/0021-9991(88)90002-2

C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the 20th Annual Association for Computing Machinery Symposium on the Theory of Computing, pp.229-234, 1988.
DOI : 10.1016/0022-0000(91)90023-x
URL : http://doi.org/10.1016/0022-0000(91)90023-x

A. Kedar, G. Patwardhan, M. Sapiro, and . Bertalmío, Video inpainting under constrained camera motion, IEEE Transactions on Image Processing, vol.16, issue.2, pp.545-553, 2007.

T. Pavlidis, Structural Pattern Recognition, 1977.
DOI : 10.1007/978-3-642-88304-0

J. Pearl, Reverend bayes on inference engines : A distributed hierarchical approach, Proceedings of the American Association of Artificial Intelligence National Conference on AI, pp.133-136, 1982.

J. Pearl, Probabilistic reasoning in intelligent systems : networks of plausible inference, 1988.

F. Pighin, J. Hecker, D. Lischinski, R. Szeliski, and H. David, Salesin : Synthesizing realistic facial expressions from photographs, Proceedings of the 25th International Conference on Computer Graphics and Interactive Techniques (SIG- GRAPH), pp.75-84, 1998.

M. Pollefeys, Self-calibration and metric 3d reconstruction from uncalibrated image sequences, Ph.D. Katholieke Universiteit Leuven, 1999.

J. Pons, R. Keriven, and O. Faugeras, Multi-View Stereo Reconstruction and Scene Flow Estimation with a Global Image-Based Matching Score, International Journal of Computer Vision, vol.24, issue.2, pp.179-193, 2007.
DOI : 10.1007/s11263-006-8671-5

R. Potts, Some generalized order-disorder transformations, Proceedings of the Cambridge Philosophical Society, pp.106-109, 1952.
DOI : 10.1103/PhysRev.60.252

R. Clay and P. , Shortest connection networks and some generalizations, Bell System Tech J, pp.1389-1401, 1957.

B. Purnomo, J. D. Cohen, and S. Kumar, Seamless texture atlases, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing , SGP '04, pp.65-74, 2004.
DOI : 10.1145/1057432.1057441
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.1197

C. Rocchini, P. Cignoni, C. Montani, and R. Scopigno, Acquiring , stitching and blending diffuse appearance attributes on 3D models. The Visual Computer, pp.186-204, 2002.

B. T. Jos, A. Roerdink, and . Meijster, The watershed transform : definitions, algorithms and parallelization strategies, Fundamenta Informaticae, vol.41, pp.187-228, 2000.

A. Rosenfeld, Picture Processing by Computer, ACM Computing Surveys, vol.1, issue.3, 1969.
DOI : 10.1145/356551.356554

A. Rosenfeld and C. Avinash, Kak : Digital picture processing, 1982.

R. Rothe, Zum Problem des Talwegs, Sitzungsberichte der Berliner Math. Gesellschaft, vol.14, pp.51-69, 1915.

C. Rother, S. Kumar, V. Kolmogorov, and A. Blake, Digital Tapestry, 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), pp.589-596, 2005.
DOI : 10.1109/CVPR.2005.130

N. D. Roussopoulos, A max {m,n} algorithm for determining the graph H from its line graph G, Information Processing Lett, pp.108-112, 1973.
DOI : 10.1016/0020-0190(73)90029-X

S. Roy and I. J. Cox, A maximum-flow formulation of the N-camera stereo correspondence problem, Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271), pp.492-502, 1998.
DOI : 10.1109/ICCV.1998.710763

K. Punam, . Saha, and K. Jayaram, Udupa : Relative fuzzy connectedness among multiple objects : theory, algorithms, and applications in image segmentation, Computer Vision and Image Understanding, vol.82, issue.1, pp.42-56, 2001.

H. Saran and V. Vijay, Vazirani : Finding k-cuts within twice the optimal, Journal on Computing, vol.24, issue.1, pp.101-108, 1995.

D. Scharstein and R. Szeliski, A taxonomy and evaluation of dense twoframe stereo correspondence algorithms, International Journal of Computer Vision, vol.47, issue.1/3, pp.7-42, 2002.
DOI : 10.1023/A:1014573219977

A. Schrijver, Combinatorial optimization : polyhedra and efficiency, 2003.

J. Serra, C. Vachier, and F. Meyer, Morphologie mathématique 1 : approches déterministes, chapitre Nivellements Traité IC2, série signal et image, pp.173-200, 2008.

J. A. Sethian, Level set methods : evolving interfaces in geometry, fluid mechanics, computer vision and materials science, 1996.

J. A. Sethian, A fast marching level set method for monotonically advancing fronts., Proceedings of the National Academy of Sciences, vol.93, issue.4, pp.1591-1595, 1996.
DOI : 10.1073/pnas.93.4.1591

J. A. Sethian, Level set methods and fast marching methods : evolving interfaces in computational geometry, fluid mechanics, computer vision and materials science, 1999.

A. Sheffer and J. C. Hart, Seamster: inconspicuous low-distortion texture seam layout, IEEE Visualization, 2002. VIS 2002., pp.291-298, 2002.
DOI : 10.1109/VISUAL.2002.1183787

J. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.22, pp.888-905, 2000.

D. Daniel and . Sleator, An O(nm log(n)) algorithm for maximum network flow. Rapport technique STAN-CS-80-831, 1980.

D. D. and S. Et-robert-endre-tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, vol.26, issue.3, pp.362-391, 1983.

P. Soille, Morphological image compositing, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, issue.5, pp.673-683, 2006.
DOI : 10.1109/TPAMI.2006.99

J. Sun, L. Yuan, J. Jia, and H. Shum, Image completion with structure propagation, Proceedings of the 32nd International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp.861-868, 2005.
DOI : 10.1145/1186822.1073274
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.6734

R. S. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov et al., Tappen et Carsten Rother : A comparative study of energy minimization methods for Markov random fields, Proceedings of the 9th European Conference on Computer Vision, pp.16-29, 2006.

F. Marshall, W. T. Tappen, and . Freeman, Comparison of graph cuts with belief propagation for stereo using identical mrf parameters, Proceedings of the 9th IEEE International Conference on Computer Vision, pp.900-907, 2003.

. Robert-endre-tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM, vol.22, issue.2, pp.215-225, 1975.
DOI : 10.1145/321879.321884

A. Mathison and T. , On computable numbers, with an application to the entscheidungsproblem, Proceedings of the London Mathematical Society, 1937.

A. Mathison and T. , On computable numbers, with an application to the entscheidungsproblem . a correction, Proceedings of the London Mathematical Society, 1937.

K. Jayaram, . Udupa, K. Punam, R. Saha, . De-alencar et al., Relative fuzzy connectedness and object definition : theory, algorithms, and applications in image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.24, issue.11, pp.1485-1500, 2002.

K. Jayaram, S. Udupa, and . Samarasekera, Fuzzy connectedness and object definition : theory, algorithms, and applications in image segmentation, Graphical Models and Image Processing, vol.58, issue.3, pp.246-261, 1996.

C. Vachier and F. Meyer, The Viscous Watershed Transform, Journal of Mathematical Imaging and Vision, vol.7, issue.3, pp.251-267, 2005.
DOI : 10.1007/s10851-005-4893-3

L. Velho and J. J. Sossai, Projective texture atlas construction for 3D photography . The Visual Computer, pp.621-629, 2007.

L. Vincent, Morphological grayscale reconstruction in image analysis: applications and efficient algorithms, IEEE Transactions on Image Processing, vol.2, issue.2, pp.176-201, 1993.
DOI : 10.1109/83.217222

L. Vincent and P. Soille, Watersheds in digital spaces: an efficient algorithm based on immersion simulations, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.13, issue.6, pp.583-598, 1991.
DOI : 10.1109/34.87344

M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky, MAP estimation via agreement on (hyper)trees : message-passing and linear programming approaches, 2003.

L. Wei and M. Levoy, Fast texture synthesis using tree-structured vector quantization, Proceedings of the 27th annual conference on Computer graphics and interactive techniques , SIGGRAPH '00, pp.479-488, 2000.
DOI : 10.1145/344779.345009
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.124.5631

H. Whitney, Congruent Graphs and the Connectivity of Graphs, American Journal of Mathematics, vol.54, issue.1, pp.150-168, 1932.
DOI : 10.2307/2371086

G. Winkler, Image analysis, random fields and dynamic Monte Carlo methods, 1995.
DOI : 10.1007/978-3-642-97522-6

M. Yannakakis, P. C. Kanellakis, S. S. Cosmadakis, and C. H. Papadimitriou, Cutting and partitioning a graph after a fixed pattern (extended abstract), Proceedings of the 10th Colloquium on Automata, Languages and Programming, pp.712-722, 1983.

C. T. Zahn, Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters, IEEE Transactions on Computers, vol.20, issue.1, pp.68-86, 1971.
DOI : 10.1109/T-C.1971.223083
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.331.6859

E. Zhang, K. Mischaikow, and G. Turk, Feature-based surface parameterization and texture mapping, Proceedings of the 32nd International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp.1-27, 2005.
DOI : 10.1145/1037957.1037958

Y. Zhang, J. Xiao, and M. Shah, Motion layer based object removal in videos, Proceedings of the 7th IEEE Workshop on Application of Computer Vision, pp.516-521, 2005.

Y. Song-chun-zhu, D. Wu, and . Mumford, Filters, random fields and maximum entropy (FRAME) : towards a unified theory for texture modeling, International Journal of Computer Vision, vol.27, pp.1-20, 1998.