Computer Analysis of Objects' Movement in Image Sequences: Methods and Applications

1 COMPUTER ANALYSIS OF OBJECTS’ MOVEMENT IN IMAGE SEQUENCES: METHODS AND APPLICATIONS João Manuel R. S. Tavares, Fernando J. S. Carvalho, Francisco P. M. Oliveira, Ilda M. Sá Reis, Maria João M. Vasconcelos, Patrícia C. T. Gonçalves, Raquel R. Pinho, Zhen Ma Faculdade de Engenharia da Universidade do Porto Instituto de Engenharia Mecânica e Gestão Industrial Rua Dr. Roberto Frias, s/n 4200-465 Porto PORTUGAL Email: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected] ABSTRACT Computer analysis of objects’ movement in image sequences is a very complex problem, considering that it usually involves tasks for automatic detection, matching, tracking, motion analysis and deformation estimation. In spite of its complexity, this computational analysis has a wide range of important applications; for instance, in surveillance systems, clinical analysis of human gait, objects recognition, pose estimation and deformation analysis. Due to the extent of the purposes, several difficulties arise, such as the simultaneous tracking of manifold objects, their possible temporary occlusion or definitive disappearance from the image scene, changes of the viewpoints considered in images acquisition or of the illumination conditions, or even nonrigid deformations that objects may suffer in image sequences. In this paper, we present an overview of several methods that may be considered to analyze objects’ movement; namely, for their segmentation, tracking and matching in images, and for estimation of the deformation involved between images. Keywords: Image Segmentation, Movement Tracking and Analysis, Matching, Templates, Deformable Models, Point Distribution Models, Level Set Methods, Kalman Filter 2 1. INTRODUCTION Computer analysis of objects’ movement in image sequences is a very complex problem, which may involve tasks for automatic objects detection, matching, tracking and deformation estimation. Motivated by its wide range of significant applications, either in 2D or 3D domains, like in medical imaging based diagnosis, human gait analysis, surveillance systems, traffic analysis, object recognition, pose estimation and deformation analysis, the computer analysis of objects’ movement has been evolving considerably over the last decades. For this analysis, many methods may be considered according to the needs of each application, but constrains associated with computational complexity as well as with computation time are usually present. Although the performance of computer systems has been improving in the last years, the tracking systems, namely the ones that are able to capture, track and analyze the movement of objects in image sequences in a very fast way, often use some kind of simplifications in order to make straightforward and speed-up their computational process. To analyze objects’ movement along image sequences, we first need to detect (i.e. segment) the objects of interest in each image (i.e. find image regions or features corresponding to objects being tracked) and then track them through consecutive images, while maintaining the correct data association (i.e. matching features between consecutive images). Often, the deformation involved between two images of objects is also estimated. Two main sources of difficulty in performing computational analysis of objects’ movement from image sequences are: 1) changes in objects’ appearance caused by variations of the considered viewpoints, illumination conditions, topology or non-rigid geometric deformations and 2) situations of total or partial objects occlusion that may occur. This paper is organized as follows: in the next section, the segmentation of objects in images is considered, by briefly describing some usual methods and presenting some experimental results. In the third section, the problem of tracking objects along image sequences is introduced; thus, some works done in this domain are indicated and experimental results, in particularly using Kalman filtering, are presented. Then, methods to match objects’ nodes between images are presented as well as an approach to 3 estimate the deformation involved between two objects, and some experimental results obtained using them are also included. Finally, in the last section, some conclusions are addressed. 2. SEGMENTATION In Computational Vision, the identification of objects represented in images is commonly known as segmentation. For this image analysis task computational methods are frequently used, based on templates matching, statistical modeling, deformable templates, deformable models or level set methods, [1]. In resume, to accomplish this operation, we can model the images’ background or the objects to be segmented instead. Template matching is used, for example, in [2] for the identification of the human eye in images. Thus, in the referred work, a template image of a human eye is used to search for it in an input image through image correlation, [3]. After this correlation procedure, the centres of regions in the input image that are more alike with the image template used will have the highest correlation values. In Figure 1, we can see the image template used and an example of the results found in [2]. This identification method can give satisfactory results, but presents several limitations, as the difficulty to deal with geometric transforms or illumination changes. Figure 1. Image template (left) used in [2] to detect the human eye in an input image (right). Also in [2], it is proposed a method to identify skin areas in an input image. For this, sample images of skin are used to build a statistical model for posterior skin segmentation. Using that model, pixels of areas in the input image that have high probability to be associated with human skin will have high values. In Figure 2, we can see an example of the use of that kind of segmentation, [2]. 4 Figure 2. Skin regions found (right) in an input image (centre) using a statistical model built using sample skin images (some of them on the left). Statistical approaches like point distribution models are frequently used to extract the most representative characteristics of objects from images. Then, active shape models and active appearance models use point distribution models to segment and recognize the modeled objects in new images. In these methods, models are built from training examples, represented as a set of labeled points, combining statistical shape with grey levels information for the object considered, [4-9]. Since the step of labeling the objects’ points is usually manually made and so fastidious and quite time consuming, some approaches have appeared to automatically extract these landmarks points from the objects in images. For example, in [10-12] it is presented computational solutions to automatically extract landmarks from objects like hands and faces in order to smooth the construction of these models. The first modes of variation of the models built describe how the landmark points of the object considered can vary as well as the expected grey level around each of these points, Figure 3, Figure 4 and Figure 5. After the models are built, they can be employed to segment the modeled objects in new images through an active search, Figure 6 and Figure 7. To conclude, this statistical modeling is only possible if we have a training set with images of the desired object, and it will be only adequate to segment shapes of the object modeled similar to the ones observed in that training set. 5 1st mode 2nd mode 3rd mode 1st mode 2nd mode 3rd mode Figure 3. Effects of the first three modes of variation of models built for a hand (top) and for a face (bottom). 6 Figure 4. Effects of the first three modes of variation of a texture model (left) and of an appearance model (right) built for a hand. Figure 5. Effects of the first three modes of variation of a texture model (left) and an appearance model (right) for a face. Deformable templates are used, for example, in [13], for the segmentation of human eyes in images, Figure 8. In this methodology, a geometric template is built in function of the object to segment; in [13], the template is composed by one circle and two parabolas. Then, using image preprocessing operators, objects’ specific features are enhanced in the input image, building energy fields that are later used to iteratively deform the template built in order to accomplish the segmentation. For this segmentation be successfully done, the template must be adequate and should be placed in the input image near the object to segment. 7 Figure 6. New images with initial position of the mean shape model built overlapped (a, c, e, g) and the final results of the segmentation process (b, d, f, h) using an active shape model. Figure 7. Iterations of the segmentation process using an active appearance model built for a face. a) b) c) d) e) f) Figure 8. Detection (f) of the human eye in a image (b) using a deformable template (a); energy fields of intensity levels (b), edges (c), intensity valleys (d) and intensity peaks (e). 8 Usually, objects of free form are better segmented when deformable models are employed, [14]. In these methods, an elastic model is placed in the input image near the object to be segmented, and then the model is deformed in order to segment the desired object. This deformation is guided by image forces, computed by enhancing some particular characteristics of the object in the input image, like intensity edges. For instance, in [15], objects are modeled using the finite elements method, a virtual material is adopted for the object to segment, and the model built is then deformed to its final shape by image forces. More specifically, after manually defining a rough contour for the object to segment, this contour is modelled according to physical principles using the finite elements method. To move the physical model towards the border of the object to segment, the dynamic equilibrium equation is solved, that describes the equilibrium between the internal and external forces. The internal forces are defined by the physical characteristics adopted for the model, determined by the chosen virtual material and the selected level of interaction between the nodes (data points) of the model. The external forces are determined by the intensity, the edges and the distance from each pixel to the nearest edge. In Figure 9, we can see an example of the results obtained using this approach. Figure 9. Initial contour user defined (left); result of the segmentation process considering a finite element model with 118 nodes and made of rubber (right). Another way to perform the segmentation of objects in images is to use the level set method introduced by Sethian and Osher, [16]. The idea behind this method is to embed the moving contour into a higher dimensional level set function, Figure 10. The moving interface can be seen as the zero level set of the function. Then, instead of moving the contour points, we can track the zero level set of the function. The advantage of doing so is that the topological changes will be naturally handled and the 9 geometric properties, like the curvature, can be implicitly calculated. Therefore, the computational complexity is greatly decreased. Figure 10. Circle moving in a 2D plane: moving traces (left), traces in the embedded space (right). Level set methods are one of the most intensively studied approach in the past few decades, especially in the image processing fields, [17-22]. The main advantages of these methods are the ability of naturally handling topological changes and easily incorporating prior knowledge. Other characteristics like the subpixel accuracy could also be preferred in certain applications. The ability of naturally handling the topological changes is quite favorable for the tasks such as segmentation and motion tracking, where the topological structures can be quite complex or frequently changed. Segmentation algorithms based on the level set methods treat the procedure of segmentation as an evolution of the initial contours. To complete the segmentation task, proper speed functions should be defined to move the contour to the right position. The works done by Malladi et.al, [23-27], and Caselles et.al, [28, 29], first applied the level set method to do the segmentation in medical images. Their speed model used the gradient information as stopping criteria. The principle of this speed model is intuitive: When the contour moves to the neighborhood of edges, the gradients of pixels are large, which make the values of speed function become small and therefore slow down the contour. The final edge of the interested objects is considered to be the contour after moving for certain time. An example of the use of this model is illustrated in Figure 11. 16 Figure 14. Tracking 6 markers in a 7 image sequence (first image in Figure 13): the Kalman Filter’s search area is defined by solid ellipses, the predicted position for each marker is indicated by a + and the corrected position is represented with a x. 17 Figure 15. Tracking mice in a lab environment during 547 images: significant changes in movement’s direction can be tracked correctly. Figure 16. Tracking mice in a lab environment during 547 images: rapid movements can be tracked correctly. For the next tracking example, [56], consider the real images acquired by an image surveillance system in a shopping centre, Figure 18 (images from [57]). In the second image, one of the persons previously tracked starts to enter a store and so the management model will stop her tracking after the 18 sixth image. If she would come out of the store quickly, the management model could keep tracking her without any problem. However, if she comes out of the store only after several images, then the proposed approach would initialize her tracking as a new feature instead. This example shows that the method used is consistent and robust enough to be applied in long image sequences, such as those of image surveillance systems, where it is essential to free the computational resources associated with features whose tracking should be stopped. Figure 17. Tracking mice in a lab environment during 547 images: differences between the predicted positions and the associated measures along the xx direction (left); detail on the results of images 100 and 120 (right). Figure 18. Tracking persons in a shopping centre: the used management model allows the correct tracking of features during long image sequences. 19 For the last experimental tracking example, [55], consider a sequence of real images of an outdoor campus scene from the PETS (Performance Evaluation of Tracking and Surveillance) 2001 datasets, Figure 19. To detect the regions of interest in this sequence, it was used the background subtraction technique, and to reduce the noise the obtained regions were then eroded and dilated. During the sequence, a person is partially occluded by a car. Thus, as they merged, the used image processing techniques only allow the detection of one region and the correspondent captured measure is attributed by the tracking system to the car. However, the persons’ tracking is maintained during 3 frames if is used a low internal rate, equal to 0.02. Furthermore, with higher internal rates the person would be tracked for more time; for instance, with an internal rate of 4.0, the person would be continually tracked during 6 images. Then, after the person and the car split into two different regions, the tracking of the person is initialized and started. This example shows the influence of the internal rate of return in the tracking of missing features using the management model based on the net present value approach. 4. MATCHING AND SIMULATION The determination of the correspondence between the data of two objects represented in images is a topic of raised importance and hard research in Computational Vision, [58, 59]; namely, because the applications that need the determination of correspondence between objects are particularly common. Some examples that can be referred are: tracking and movement analysis ([58, 60]), 3D reconstruction ([59, 61]), objects recognition ([11, 58]) and image registration ([11]). Basically, the existing methods try to match the objects by using information that is image invariant, like curvature or displacements in a global coordinate space. In [62], for example, it is presented a method to determine matches between points of contours represented in images, that considers curvature information and optimization of the global matching cost. Briefly, first, the angles defined by each set of three consecutive data points of each contour to be match are computed. Then, it is built the matrix of matching costs, by comparing the angles associated to each point of the contours. Finally, using an optimization algorithm, a global matching of minimum cost is found. Using this approach, the contours to match can have different numbers of points and the rigid transformation involved between them can also be estimated. In Figure 20, it is visible the matches found 20 between the points of two contours and the estimated rigid transformation involved using the proposed method. This approach is more adequate for rigid objects because the higher the nonrigid deformations are, the more different will be the curvature values along the images. (a) (b) (c) (d) (e) (f) Figure 19. Tracking a person and a car with partial occlusion: in images (a)-(b) the person and the car are tracked separately; in (c)-(e) they are overlapped and the only captured measure is assigned to the car, so the person’s tracking is continued with higher uncertainty until it is stopped; in (f) the two features are again tracked independently. 21 Figure 20. Two contours defined by 28 and 32 points (left), the matches found (centre) and after applying the rigid transformation estimated (right). The matching between points of two objects can also be obtained by analyzing the displacements of those points in the respective eigenspace, commonly known as modal matching, [58]. For that, the eigenspace associated to each object is built and then the matches are found by searching for similar displacements in these spaces. For instance, in [58, 63, 64], the eigenspaces are built based on the geometrical shape of each object, then an affinity matrix is defined, whose elements, the costs of each possible matches, are found by computing the Euclidian distance between the eigenmodes associated to each object. In [63, 64], the best global matches are found by using an optimization technique in the search done on the affinity matrix. In this methodology, extra points can be matched as well by adding fictitious points in the search step, that are then matched with real points, [63-65]. This method is very fast, easy to implement and can achieve good matching results. In Figure 21, is presented an example of the results found using this method, [64]. Figure 21. Matches found between two contours, one with 136 points and other with 139, using modal matching. The optimization techniques used in [63, 64] do not consider the order of the contours’ points, which sometimes can lead to crossed matches. To overcome this, it is proposed in [66-68] a new solution based on dynamic programming to achieve the best global matching without crossed matches. Using the 22 solution proposed, the matching quality is improved and, additionally, the computation time decreases considerably. In [58, 60, 63, 65, 69], a similar modal matching method is used, but each eigenspace is built from the finite element model of the associated object. The matches are then found in a similar away. This method is computationally more demand than the geometrical approach, but the matches found are more alike with the physical behavior expected for the objects. In many applications, it is necessary to estimate the deformation involved between two objects or between two different instants of one object. One possible example is the estimation of the deformation of an object whose images were acquired using a large time step. In [58, 70-74], for instance, that estimation is accomplished according to physical principles by using the finite element method to model the objects, modal matching and optimization techniques to match the nodes of the models and the Lagrange equation of motion to estimate the nodal displacements. After segmenting the object in both images, the nodes of their physical models are matched and the deformation of one into the other is simulated by solving the dynamic equilibrium equation. Using the same approach as in [15] for the segmentation of an object, the internal forces in the equation are defined by the physical characteristics adopted for the model. However, the external forces are not determined as in [15]: using the fact that the final stage of the deformation is know, the external forces are defined in terms of the distance between the nodes of a contour and theirs correspondents in the other one. In Figure 22, it is presented an example of an experimental result using this physical methodology. 5. CONCLUSIONS Computational analysis of the movement of objects represented in images is not a trivial task. A considerable part of the work done in Computational Vision is concerned with that goal. The main reason for this high effort is the huge number of possible and important applications for that analysis; namely, in medical area. Usually, the analysis of objects’ movement involves steps of objects segmentation in images, tracking of objects’ features along image sequences and, very often, the matching of these features between consecutive images and even the estimation of the deformation involved between two images. In this 23 paper, some methods were introduced to accomplish these tasks as well as some of their applications and results. Figure 22. Original object in two different stages (top), contours and matches found between them (bottom left), and intermediate contours estimated by physical principles (bottom right). ACKNOWLEDGMENTS This paper was partially done in the scope of project “Segmentation, Tracking and Motion Analysis of Deformable (2D/3D) Objects using Physical Principles”, with reference POSC/EEA-SRI/55386/2004, financially supported by FCT - Fundação para a Ciência e a Tecnologia from Portugal. The fourth, fifth and seventh authors would like to thank also the support of their PhD grants from FCT with references SFRH/BD/29012/2006, SFRH/BD/28817/2006 and SFRH/BD/12834/2003, respectively. REFERENCES [1] Y. J. Zhang, "A review of recent evaluation methods for image segmentation," in Sixth International Symposium on Signal Processing and its Applications, Kuala Lumpur, Malaysia, 2001. [2] F. J. S. Carvalho and J. M. R. S. Tavares, "Metodologias para identificação de faces em imagens: Introdução e exemplos de resultados," in Congreso de Métodos Numéricos en Ingeniería 2005, Granada, España, 2005. [3] R. Schalkoff, Digital Image Processing and Computer Vision: John Wiley and Sons Ltd, 1989. 24 [4] L. D. Cohen and I. Cohen, "Finite Elements for Active Contour Models and Ballons for 2-D and 3-D Images," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, pp. 1131-1147, 1993. [5] T. Cootes, A. Hill, C. Taylor, and J. Haslam, "The use of active shape models for locating structures in Medical Images," Image and Vision Computing, vol. 12, pp. 355-366, 1994. [6] T. Cootes and C. Taylor, "Active Shape Models: Smart Snakes," in British Machine Vision Conference, Leeds, UK, pp. 267-275, 1992. [7] T. Cootes, C. Taylor, D. Cooper, and J. Graham, "Active Shape Models - Their Training and Applications," Computer Vision Image Understanding, vol. 61, pp. 38-59, 1995. [8] T. F. Cootes, G. J. Edwards, and C. J. Taylor, "Active appearance models," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, pp. 681-685, 2001. [9] J. Sung, T. Kanade, and D. Kim, "A Unified Gradient-Based Approach for Combining ASM into AAM," International Journal of Computer Vision, vol. 75, pp. 297-309, 2007. [10] M. J. Vasconcelos and J. M. R. S. Tavares, "Automatic Modelling Image Represented Objects using a Statistic based Approach," in The European Simulation and Modelling Conference (ESM), Porto, Portugal, pp. 7-12, 2005. [11] M. J. M. Vasconcelos and J. M. R. S. Tavares, "Methodologies to Build Automatic Point Distribution Models for Faces Represented in Images," in CompIMAGE - Computational Modelling of Objects Represented in Images: Fundamentals, Methods and Applications, Coimbra, Portugal, pp. 435440, 2006. [12] M. J. M. Vasconcelos and J. M. R. S. Tavares, "Methods to Automatically Built Point Distribution Models for Objects like Hand Palms and Faces Represented in Images," Computer Modeling in Engineering & Sciences, (in press). [13] F. J. S. Carvalho and J. M. R. S. Tavares, "Eye detection using a deformable template in static images," in VIPimage - I ECCOMAS Thematic Conference on Computational Vision and Medical Image Processing, Porto, Portugal, pp. 209-215, 2007. [14] A. Blake and M. Isard, "Active contours: the application of techniques from graphics, vision, control theory and statistics to visual tracking of shapes in motion," Springer, 1998. 25 [15] P. C. T. Gonçalves, J. M. R. S. Tavares, and R. N. Jorge, "Segmentation of objects in images using physical principles," in VIPimage - I ECCOMAS Thematic Conference on Computational Vision and Medical Image Processing, Porto, Portugal, pp. 329-334, 2007. [16] S. Osher and J. A. Sethian, "Fronts Propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations," Journal of Computational Physics, vol. 79, pp. 12-49, 1988. [17] J. S. Suri, S. Singh, S. Laxminarayan, X. Zeng, K. Liu, and L. Reden, "Shape Recovery Algorithms Using Level Sets in 2D/3D Medical Imagery: A State-of-the-Art Review," IEEE Transactions on Information Technology in Biomedicine, vol. 6, pp. 8-28, 2002. [18] J. A. Sethian, Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science, 2 ed.: Cambridge University Press, 1999. [19] T. McInerney and D. Terzopoulos, "Deformable Models in Medical Image Analysis: A Survey," Medical Image Analysis, vol. 1, pp. 91-108, 1996. [20] D. L. Pham, C. Xu, and J. L. Prince, "Current Methods in Medical Image Segmentation," Annual Review of Biomedical Engineering, vol. 2, pp. 315-338, 2000. [21] Y. Qu, T.-T. Wong, and P. A. Heng, "Image Segmentation Using the Level Set Method," in Deformable Models, J. S. Suri and A. Farag, Eds.: Springer, pp. 95-161, 2007. [22] D. Cremers, M. Rousson, and R. Deriche, "A Review of Statistical Approaches to Level Set Segmentation: Integrating Color, Texture, Motion and Shape," International Journal of Computer Vision, vol. 72, pp. 195-215, 2007. [23] R. Malladi and J. A. Sethian, "An O(N log N) algorithm for shape modeling," Proceedings of the National Academy of Sciences, vol. 93, 1996. [24] R. Malladi and J. A. Sethian, "Level Set and Fast Marching Methods in Image Processing and Computer Vision," in IEEE International Conference on Image Processing, Lausanne, Switzerland, pp. 16-19, 1996. [25] R. Malladi, J. A. Sethian, and B. Vemuri, "A Topology Independent Shape Modeling Scheme," in SPIE Conference on Geometric Methods in Computer Vision II, San Diego, California, USA, 1993.