Analyse de scènes dynamiques complexes par la méthode du plongement fractal
Dynamic complex scene analysis with the fractal embedding method
OPEN ACCESS
We present a new image sequence analysis method for automatic and real-time extraction of transitory and complex motions in natural scenes. We show how to extract these motions as multidimensional point clusters obtained from the temporal embedding of grey level variations, in five successive steps: embedding, fractal indexing, point chaining, cluster identification and data extraction. We develop the two main algorithms: fractal space filling indexing and chaining in order to access directly to the relevant information. To illustrate our method, we present an automatic system for early smoke source detection through the processing of landscape images by extracting fugitive and various movements within a small spot of pixels affected by the smoke. We show how to modify the embedding technique used to obtain the data points coordinates to produce many other applications for the fractal embedding method, for example the recognition of complex moving or varying shapes objects.
Résumé
Nous présentons une nouvelle méthode d’analyse de séquences d’images adaptée à l'extraction automatique en temps réel de mouvements localisés dans des scènes naturelles. Nous montrons comment extraire ces mouvements sous la forme de voisinages de points formés dans un espace de très grande dimension par le plongement temporel des variations de niveaux de gris des pixels d'une même enveloppe. Nous présentons tout d'abord notre méthode d'extraction rapide des voisinages dans cet espace multidimensionnel. Ses étapes principales sont l'indexation et le chaînage des points : l'indexation des points se fait selon une courbe fractale qui remplit l’espace, et le chaînage des points indexés permet un accès immédiat aux points voisins. Nous validons ensuite la méthode dans le cas du plongement temporel d'enveloppes de pixels rendus dynamiques par la présence de fumée. L'application est un détecteur des feux de forêts capable de faire la distinction entre des enveloppes causées par une source de fumée ou par tout autre phénomène dynamique pouvant apparaître localement dans un paysage. On exploite les propriétés caractéristiques des mouvements fugitifs et diversifiés qui sont causés par les bouffées de fumée, même à l’intérieur de petites enveloppes de pixels. Nous généralisons ensuite les perspectives d'utilisation de la méthode du plongement fractal en envisageant d'autres types d'applications par l'extraction de caractéristiques autres que des mouvements.
Motion detection, Image sequences, Space filling curves, Clustering, Multidimensional embedding, Complex dynamic systems, Shape recognition
Mots clés
Détection de mouvement, séquences d’images, courbes space-filling, clustering, plongement multidimensionnel, systèmes dynamiques complexes, reconnaissance de forme
[1] P. Bouthemy, « Motion segmentation and qualitative dynamic scene analysis from an image sequence. » International Journal of Computer Vision, Vol. 10 (2), 1993, pp. 157-182.
[2] A. Caplier, C. Dumontier, F. Luthon, P.Y. Coulon, « Algorithme de détection de mouvement par modélisation markovienne. Mise en œuvre sur DSP. » Traitement du signal, Vol. 13, 1996, n° 2, pp. 177-190.
[3] F. Takens, « Detecting strange attractors in turbulence », Lecture Notes in Mathematics 898, Springer-Verlag 1981, pp. 366-381.
[4] R. Agrawal, C. Faloutsos, A. Swani, « Efficient similarity search in sequence databases », 4th Int. Conf. on Foundations of Data Organization and Algorithms, Chicago, October 1993, pp. 69-84.
[5] R. Agrawal, K.I. Lin, H.S. Sawhney, K. Shim, « Fast similarity search in the presence of noise, scaling and translation in time series databases. » 21st Int. Conf. on very large databases, Zurich, Switzerland, Septembre 1995, pp. 490-501.
[6] C. Faloutsos, M. Ranganathan, Y. Monolopoulos, « Fast subsequence matching in time-series databases. » Special Interest Group on Management of Data (SIGMOD), 1994, pp. 419-429.
[7] G.H.Cha, C.W.Chung, « Object-Oriented Retrieval Mechanism for Semistructured Image Collections. » 6th ACM International Multimedia Conference (ACM Multimedia ’98), Bristol UK, Sep. 1998, pp. 323-332.
[8] F. Korn, N. Sidiropoulos, C. Faloutsos, E. Siegel, « Fast nearest-neighbor search in medical image databases. » Int. Conf. on Very Large Data Bases (VLDB ’96), Bombay, India, September 1996, pp. 215-226.
[9] D. Vassiliadis, « The input-state space approach to the prediction of auroral geomagnetic activity from solar wind variables. » in Int Workshop on Applications of Artificial Intelligence in Solar Terrestrial Physics, edited by J. Joselyn, H. Lundstedt and J. Trolinger, NOAA, Boulder, 1994, pp. 145-151.
[10] A. Guttman, « R-Trees : A Dynamic Index Structure for Spatial Searching. » (R-Trees : une Structure d’Index Dynamique pour les Recherches Spatiales) ACM SIGMOD Int. Conf. on Management of Data, Boston, MA, June 1984, pp. 47-57.
[11] N. Roussopoulos, C. Faloutsos, S. Timos, « The R+-trees : A Dynamic index for multi-dimensional objects. », 13th International Conference on Very Large Databases (VLDB’87), Brighton, 1987, pp. 507-518.
[12] T. Brinkhoff, H.P. Kriegel H.P, B. Seeger, « Efficient Processing of Spatial Joins Using R-Trees », ACM SIGMOD (Special Interest Group on Management of Data), Washington D.C., 22(2) : pp. 237-246, June 1993.
[13] T. Sellis T, N. Roussopoulos, C. Faloutsos, « The R+Tree: A Dynamic Index for Multi-Dimentional Objects. », 12th Int. Conf. on Very Large Data Bases (VLDB), Brighton, 1987 pp. 507-518.
[14] J.A. Orenstein, « Spatial query processing in an object-oriented database system ». ACM SIGMOD, Washington U.S., May 1986, pp. 326-336.
[15] Hans Sagan, « Space-Filling Curves », Springer-Verlag, New York, 1994.
[16] M. Mandelbrot, « Fractal geometry of nature »,W.H. Freeman, New York, 1977.
[17] J.A. Orenstein, « Redundancy in Spatial Databases, » ACM SIGMOD Int. Conf.. On the Management of Data, Portland, OR, May-June 1989, pp. 294-305.
[18] P. Grasberger, I. Procaccia, Generalized dimension of strange attractors, Phys. Rev. Let. A, 97 (1983) 227.