Reconstruction of Binary Objects from Two Orthogonal Projections by an Inspired Technique of the Graph's Theory: the Research of Maximum Flow with Minimum Cost
Reconstruction d'Objets Binaires à Partir de Deux Projections Orthogonales par une Technique Inspirée de la Théorie des Graphes: la Recherche du Flot Maximum à Coût Minimum
OPEN ACCESS
In this article we introduce a three dimensional reconstruction algorithm from tw o mutually orthogonal X-ray projections. The three dimensional reconstruction i s based on a series of parallel slices. These parallel slices are supposed binary. They are reconstructed with the help of their definite density curves on Xray radiographies. However the available information on radiographies is not complete. We propose to use as a priori information a model to reconstruct curve s ofdensity and to decrease the ambiguity during the reconstruction ofthe objects. The reconstruction is processed through several steps: the initial positioning of the model, the reconstitution of the density curves, the object's slices reconstructio n from their density curves.
The reconstruction uses a maximum flow ofminimum cost algorithm derived from the graphs theory and a model of the object's slices . For this reconstruction we propose a new algorithm for the research of the maximum flows with a minimum cost, and as models the skeleton ofthe surface to reconstruct.
Rates ofconformability, obtained between the surface to reconstruct and the result surface ofthe reconstruction, are greater than 95% . We present the results obtained for elements of differents typical shapes in the case of unnoisy and noisy densit y curves, and the application ofthe reconstruction process to the the jaw elements .
Résumé
Dans cet article, nous présentons un algorithme de reconstruction d'objets en 3D à partir de deux projections rayons X orthogonales . La reconstruction 3D est basée sur celle d'une série de tranches parallèles. Ces tranches parallèles sont supposées binaires. Elles sont reconstruites à l'aide de leurs courbes de densité définies sur le s radiographies rayons X. Cependant l'information disponible sur les radiographies n'est pas complète. Nous proposons d'utiliser un modèle comme information à priori pour reconstituer les courbes de densité et diminuer l'ambiguïté lors de l a reconstruction des objets.
La reconstruction s'effectue en plusieurs étapes : le positionnement initial du modèle, la reconstitution des courbes de densité, la reconstruction des tranches de l'objet à partir des courbes de densité.
La reconstruction utilise un algorithme de flot maximum à coût minimum inspiré de la théorie des graphes et un modèle de la surface à reconstruire . Pour cette reconstruction nous proposons un nouvel algorithme de recherche du flot maximu m à coût minimum, et comme modèle le squelette de la surface à reconstruire . Les taux de conformités, obtenus entre la surface à reconstruire et la surfac e reconstruite, sont supérieurs à 95% . Nous présentons les résultats obtenus pour des formes types dans le cas de courbes de densité bruitées et non bruitées, et l'application de la méthode à la reconstruction d'éléments de la mâchoire .
Three dimensional reconstruction, Graph, Heuristic methods .
Mots clés
Reconstruction 3D, théorie des graphes, méthode Heuristique.
[ONNA 76] D.G.W Onnasch, P.H. Heintzen, A new approach for the reconstruction of the right or left ventricle from biplan angiocardiographie recording. Comp.Card., pages 67-73, 1976
[DBAI 86] Z. Dbai, P.R. Krishanaiah, C.R. Rao , P.0 Reddy, Y.N. Sun. L.C. Zhao, Reconstruction of left ventricule from two orthogonal projections based on theorem of equal divisor curves. Technical Repport Pittsburg 1986.
[BENN 73] G.E. Bennington, An efficient minimal cost flow algorithm Management Science Vol. 19, n° 9 1042, 1051, 1973
[BUSA 61] G. Busacker and P.J. Gowen, A procedure for determining a family of minimal cost network flow pattern. O.R.O. Technical report University of Hopkins 1961.
[BUSA 65] G. Busacker and T.L. Saaty, Finite Graphs and Networks : An Introduction with Applications, McGraw-Hill, New York, 1965 .
[CHAN 71] S.K. Chang, The Reconstruction of Binary Patterns from thei r Projections, Comm. ACM 14, 1971, pages 21-25 .
[CHAN 73] S.K. Chang and C.K. Chow, The reconstruction of three-dimensional objects from two orthogonal projections and its application to cardiac cineangiography, IEE Trans. Computers C-22, 1973, pages 18-28 .
[CHAN 71] S.K. Chang and G.L. Shelton, Two algorithms for multiple-view binary pattern reconstruction . IEEE Trans. Syst. Man, Cybernet. SMC-1 , 1971, 90-94.
[DANT 60] G.B. Dantzig, On the shortest path through a network . Manag.Science. 1960, Vol. 6, pages 187-190.
[FLOY 62] R.W. Floyd, Algorithm 47, shortest path. Comm. of the ACM. 1962, Vol. 5, page 345.
[FORD 56] L.R. ford and D.R. Fulkerson, Maximal flow through a network. Canad. J. of Math. 1956, page 399.
[FORD 57] L.R. Ford, Jr. and D.R. Fulkerson, A simple algorithm for findin g maximal network flows and an application to the Hitchcock problem, Canad. J. Math. 9, 1957, pages 210-218.
[FORD 59] L.R. Ford, Jr. and D.R. Fulkerson, A network flow feasability theorem and combinatorial application. Canad. J. Math. 1959, Vol. 11, pages 440-450.
[FORD 62] L.R. Ford, Jr. and D.R. Fulkerson, Flows in networks, Princeto n Uni.Press, Princeton, N.J., 1962.
[FORD 67] L.R.Ford, Fulkerson, J-C. Arinal, Flows in netwokrs . Gauthier Villars Paris 1967.
[GOND 85] M. Gondran, M. Minoux, Graphes et algorithmes. Eyrolles 1985.
[HERM 73] T. Herman, Reconstruction of binary patterns from a few projections . Int. Comp. Symp. Amsterdam, 1973, pages 371-379 .
[HITC 41] F.L. Hitchcock, The distribution of product from several sources to numerous localities. J. Math Phys 1941, Vol . 20, pages 224.
[JIVE 85] Jiye Shao, Three dimensional algebriac reconstruction from mutuall y orthogonal projections . OPTK, Vol. 71, 142, 148. 1985.
[KLEI 67] M. Klein, A primal method for minimal cost flows with application s to the assignment and transportation problems . Manag. Sci. 1967, Vol. 14, pages 205-220.
[KLEI 73] M. Klein, Finding negative cycles . INFOR. 1973, Vol. 11, n° 1, pages 59-65 .
[MIST 81] C.A. Mistretta, A.B. Crummy, C.M. Strother, Digital angiography : perspective. Radiology, 1981, 139, pages 237-276.
[NAHA 81] D. Nahameo, C.R. Craxford, A.C. Kak, Design contraints and reconstruction algorithms for traverse-continuous-rotate CT scanners. Radiology. 1981, 139.
[REBO 93] S . Reboul, M.M. Rousset, A. Taleb-Ahmed, H. Blocquel, J.P. Dubus, Présentation d'un logiciel d'étude de la facechez l'enfant. G.I.R.S.O Lille 1993.
[REBO 93] S . Reboul, M.M. Rousset, A. Taleb-Ahmed, H . Blocquel, J.P. Dubus, Logiciel d'étude quantitative et représentation de l'évolution de la face chez l'enfant. Renc. Jeun. Cherch. en Odont A.D.F PARIS 1993.
[ROY 59] B. Roy, Cheminement et connexité dans les graphes, application aux problèmes d'ordonancement . Thèse d'état 1960, Publiée par METRA.
[SLUM 82] C. Slump Gerbrands, A new approach for the reconstruction o f the left ventricule from two projections. Computer Graphics and image s Processing. Vol. 18,36 1982.
[TALE 91] A. Taleb-Ahmed, S . Reboul, F. Salome, J-P. Dubus, Méthode de reconstruction tridimensionnelle indirecte de la dentition à partir de deux clichés radiographiques en incidence orthogonale. festival 3D, Premier Symposium International de l'Image en Relief. Paris 1991 .
[TALE 92] A. Taleb-Ahmed, S . Reboul Contribution de synthèse sur les méthodes de reconstruction . GDR Reconstruction 3D Strasbourg 1992.
[TALE 92] A. Taleb-Ahmed, S. Reboul, M.M. Rousset, J-P. Dubus, 3D reconstruction of children's jaw. 14' Conf Int IEEE EMBS. Paris 1992.
[TANA 76] E. Tanaka and T.A. Inuma, Correction functions and satistical noise s in transverse section picture reconstruction. Comput. Biol. Med. 1976, Vol. 6, pages 295-306.
[YANG 89] R.L. Yang, Traitement numérique des angiogrammes vidéodensitométrie et reconstruction d'images en 3D à partir de deux projections orthogonales. Thèse CNAM PARIS 1989.