Application of Chaos and Fractals to Computer Vision

Computer vision has been an active area of research in computer science for over fifty years. Much progress has been made on many fronts by researchers proposing a variety of algorithms motivated by many other fields of science, including mathematics, physics, physiology, and biology. These algorithms are often focused on specific tasks such as image segmentation, classification, or image registration. Some common approaches to many algorithms is that they employ a variety of linearizing approximations to simplify the computations. Chaos theory is a field of research that provides insight into how dynamical systems can exhibit radically different behaviors from seemingly similar initial conditions. It is based on the ideas of non-linear dynamics and provides a set of tools for understanding these complex behaviors. In this text we embrace the non-linear foundations of chaos theory and employ them to solve a broad variety of computer vision applications.

Biological vision systems have been successfully modeled as hierarchical systems with lower level subsystems performing simpler tasks such as attention direction towards moving objects, and higher level subsystems performing tasks such as tracking, object recognition and scene understanding. Likewise robotics researchers have found great utility in layered systems such as the subsumption architecture. Within biological sensing systems there has been the detection of chaotic signals within the neural pathways. Chaotic systems have some unique behaviors such as basins of attraction that allow systems to quickly transit between states. Additionally, small changes to chaotic signals can lead to dramatic changes in the outputs which can make sensing organs very sensitive to subtle events. Researchers to date tend to focus on either the use of the macroscopic models or the microscopic models in their avenues of research. We will uniquely adopt both the structural macroscopic model of biological systems as well as the chaotic microscopic nature of biological systems in this text. Dividing the complex vision task into a hierarchy will allow us to address increasing levels of complexity, yet show how chaos-based methodologies can be applied through all of these levels.

Chaos theory has been found to be a very effective tool for analyzing complex non-linear systems with its beginnings being traced to weather systems prediction by Lorenz. Chaotic systems have also been tied to information theory, and systems that exhibit chaotic behavior have been shown to be sources of information. Definitively identifying systems as being chaotic, however, is extremely difficult. Fortunately simply identifying a system as being chaos-like can be beneficial and even adequate for certain analysis, and this is the approach we will adopt in this text for addressing computer vision applications using chaos theoretic techniques. Chaos and fractals are interconnected because systems that behave chaotically have phase space trajectories that are fractal in nature. Thus analyzing the fractal dimension of the phase space trajectories of systems will allow us to determine how chaotic they are and more importantly for computer vision how strongly they are creating information. The strength of information generation will prove effective in developing robust motion and change detection algorithms even in the face of complex spatio-temporally varying illumination in later chapters.

Chaotic systems are created by an underlying non-linear dynamics. In the previous chapter we explored the characteristics of chaotic systems. Objects under motion within an image can be modeled as aperiodic forcing functions impacting the amplitude response of the imaging sensors in computer vision. Recall from the previous chapter that systems undergoing aperiodic forcing functions exhibit chaos-like behavior. Interestingly, illumination changes in image sequences do not exhibit this chaos-like behavior, but rather exhibit very deterministic behavior that has very limited excursions in phase space. Recall systems can also exhibit spatial chaotic behavior and the amplitude variations across an image under varying textures will exhibit varying behavior in phase space. Also the traditional methods of analyzing texture through greylevel co-occurrence matrices is closely related to the reconstructed phase space analysis methods defined in the previous chapter. Thus chaos theory can provide a unifying framework for describing interesting temporal and spatial behavior in computer vision while providing an inherent immunity to even complex illumination changes.

To be able to differentiate image sequences exhibiting the complex behavior of moving objects and contextual change from image sequences simply experiencing changes in illumination we must be able to characterize the trajectories of these systems in phase space. The Hausdorff dimension provides a theoretical estimate of the fractional dimension of any curve in space; however it is quite difficult to calculate. Fortunately there are a number of approximations to the Hausdorff dimension that will be defined in this chapter, with one of the most common being the Box Counting dimension. The Hausdorff dimension is a global measure of the fractional dimension of a space. One of the goals of many computer vision applications is image segmentation which will require an estimate of the fractal behavior of each pixel in the image. This will require local measures of the fractality of the phase space Fortunately there are a number of local measures that will be available to us. Lastly, fractal dimensional measures will only differentiate between chaotic and non-chaotic trajectories to characterize and differentiate various textures we need measures that will be able to also differentiate between different fractal behaviors. We propose adapting measures used to analyze the Grey-level Co-occurrence Matrix for this purpose due to the structural similarity between the GLCM and the phase plot.

Pre-attentive vision systems are responsible for directing the attention of higher order vision functions to regions of the field of view that may be of interest to the system. Regions may be of interest due to motion or due to a contextual change in the image that may be due to a sudden appearance or disappearance of an object. Since the outcome of the pre-attentive system is a notification of interest to the higher order vision functions, maintaining a low false alarm rate is critical. One key cause of false alarms can be either sudden or slow changes in illumination of the field of interest of the imaging system. Another key issue is the detection rate of the system. In particular the sensitivity of the system to small changes must be maintained while its immunity to non-interesting change such as illumination is preserved. Thus the use of the proposed chaos-based methods which are inherently immune to illumination change have great promise for these types of systems. In this chapter we will first define the problem of pre-attentive vision in chaos-theoretic terms, and then propose an algorithm that utilizes the chaos-based methods of phase space analysis using global fractal measures. The chaos-based system performance is compared to traditional methods such as Mutual Information, sum of absolute differences, and Gaussian mixture models. The chaosbased methods outperform all of these traditional methods.

Attentive vision relates to the isolation of objects of interest to be able to advance them to yet higher level vision systems such as object tracking and object recognition. Since the task is related to object segmentation from the background it will require the application of local measures of fractality in phase space. These local measures will be used to identify the regions of phase space that correspond to interesting behavior such as a moving object or contextual change. Once these regions in phase space are identified the vision system will use the mapping from phase space to the original image space to identify the pixels that correspond to the object of interest. This is markedly different from traditional methods such as Optical Flow and Gaussian Mixture Models where the decisions of important change are made in the grayscale space of the original images, yet this space is corrupted by spatio-temporal illumination changes. The performance of the chaos-based approach is demonstrated both for motion-based segmentation and also contextual change-based segmentation.

The analysis of texture in computer vision has been of interest to researchers for many decades. The early work in texture by researchers such as Haralick discovered the utility of the greylevel co-occurrence matrix (GLCM) as a means for exploring the spatially varying affects present in various textures. Other means such as Gabor filters arose as being highly effective as well due to their ability to readily handle varying angles and varying spatial extents. The research in texture evolved distinctly from research in other areas of computer vision such as motion segmentation, non-textured grayscale segmentation, etc. This text is the first discussion of an approach to computer vision which can provide a unifying framework within which many computer vision problems can be solved using a common toolset, namely the analysis of images in phase space using tools from chaos theory. This chapter will further explore the role of spatial chaos in serving as a possible framework within which texture can be analyzed. The use of temporal chaos has proven useful throughout the text in approaching computer vision problems such as motion segmentation and image registration. Thus a common set of tools can now be used for solving the general computer vision problem.

Image registration is a critical upper level vision task for many applications, as is the related task of object tracking. One of the simplest tracking algorithms is the correlation tracker which does not require prior object segmentation to successfully estimate motion parameters of possible objects of interest. For image registration there are two classes of algorithms, landmark or point-based and pixel-based. Pixel-based methods are popular in applications where reliable detection of landmark points is not feasible. As with the other computer vision tasks defined in the text, the performance of these pixel-based methods is sensitive to illumination change between the image pair being registered. Unfortunately illumination change is quite common in image registration problems, particularly in outdoor scene tracking. The popular measure of Mutual Information has been widely accepted as the standard measure for image registration; however, it is sensitive to illumination change. The chaos-based measures such as the Box Counting dimension and the Information Dimension will be applied to the image registration problem. The results obtained by these methods will be shown to be superior to the results provided by the traditional measures.

The application of concepts from chaos theory to a broad range of lower level computer vision has proven useful throughout the text so far. These tasks have included motion detection and segmentation, texture analysis and image registration and tracking. The application of chaos theory to the higher level computer vision task of pattern recognition has also been an area of active research. This is particularly true in the area of chaotic neural networks based on the known chaotic behavior of biological neural systems. Pattern recognition can be considered an optimization problem where the best matching pattern maximizes the probability of correct classification. The application of optimization algorithms such as genetic algorithms to pattern recognition has also proven fruitful, and the dependence of these algorithms on random number generation for processes such as mutation makes them logical candidates for improvements using chaos theory to develop more robust random behavior. In this chapter the application of chaos theory to neural networks and genetic algorithms for the high level computer vision function of object recognition will be explored.