Steps Towards a Theory of Visual Information: Active Perception, Signal-to-Symbol Conversion and the Interplay Between Sensing and Control
Stefano Soatto
Preface
This manuscript has been developed starting from notes for a summer course at the First International Computer Vision Summer School (ICVSS) in Scicli, Italy, in July of 2008. They were later expanded and amended for subsequent lectures in the same School in July 2009. Starting on November 1, 2009, they were further expanded for a special topics course, CS269, taught at UCLA in the Spring term of 2010.
I acknowledge contributions, in the form of discussions, suggestions, criticisms and ideas, from all my students and postdocs, especially Andrea Vedaldi, Paolo Favaro, Ganesh Sundaramoorthi, Jason Meltzer, Taehee Lee, Michalis Raptis, Alper Ayvaci, Yifei Lou, Brian Fulkerson, Teresa Ko, Daniel O’Connor, Zhao Yi, Byung-Woo Hong, Luca Valente.
In addition to my students, I am grateful to my colleagues Ying-Nian Wu, Andrea Mennucci, Anthony Yezzi, Veeravalli Varadarajan, Peter Petersen, and Alessandro Chiuso for discussions leading to many of the insights described in this manuscript. I also wish to acknowledge discussions with Joseph O’Sullivan, Richard Wesel, Alan Yuille, Serge Belongie, Pietro Perona, Jitendra Malik, Ruzena Bajcsy, Yiannis Aloimonos, Sanjoy Mitter, Roger Brockett, Peter Falb, Alan Willsky, Michael Jordan, Judea Pearl, Deva Ramanan, Charless Fowlkes, Giorgio Picci, Sandro Zampieri, Lance Williams, George Pappas, Tyler Burge, James Clark, Jan Koenderink, Yi Ma, Olivier Faugeras, John Tsotsos, Tomaso Poggio, Allen Tannenbaum, Alberto Pretto. I wish to thank Andreas Krause, Daniel Golovin, Andrea Censi, Lorenzo Rosasco, Max Welling and Taco Cohen for many useful comments and corrections. Finally, I wish to thank Roberto Cipolla, Giovanni Farinella and Sebastiano Battiato for organizing ICVSS that has initiated this project.
The work leading to this manuscript was made possible by guidance, encouragement, and generous support of three federal research agencies, under the leadership of their Program Managers: Behzad Kamgar-Parsi of ONR, Liyi Dai of ARO, and Fariba Fahroo of AFOSR. Their help in making this project happen is gratefully acknowledged. I also wish to acknowledge discussion and feedback from Tristan Nguyen, Alan Van Nevel, Gary Hewer, William McEneany, Sharon Heise, and Belinda King.
Note from 2017: Much of this work is superseded and distilled in the 2017 paper “Emergence of Invariance and Disentanglement in Deep Representations”, .
Chapter 1 Preamble
“Intelligent Behavior” is often assumed to involve some sort of “internal representation” made of discrete “symbols.” However, the Data Processing Inequality suggests that such a signal-to-symbol conversion is detrimental to the optimality of decision and control actions downstream. This opens a number of questions that motivate this manuscript. Readers uninterested in such philosophical issues can skip this section.
Perceptual agents, from plants to humans, measure samples of physical processes (“signals”) that are essentially continuous.The continuum is an abstraction; a continuous entity is to be understood as one existing at a level of granularity significantly finer than the resolution of the measurement devices. For instance, the radiance of an object is sampled by retinal photoreceptors that are finite in number; the more receptors (or the closer the viewer), the more details are being revealed, so one never has a “sufficient number of pixels” and therefore the radiance can be thought of as a continuous function. They also perform actions in the continuum of physical space. And yet, cognitive science, epistemology, and in general modern philosophy associate “intelligent behavior” with some kind of “internal representation” built upon discrete symbols (e.g. “concepts”, “ideas”, “objects”, “categories”) that can be manipulated and inferred with logic and probabilistic inference. But why should such a “signal-to-symbol” conversion occur? How does it yield an evolutionary advantage? What principles should guide it?
Information Theory suggests that such a signal-to-symbol conversion may be counter-productive: If we consider biological systems as machines that perform actions or make decisions in response to stimuli in a way that maximizes some decision or control objective, then the Data Processing InequalitySee Section 2.4.1 or page 88 of . indicates that the best possible agents would avoid data analysis, Note that I refer to data analysis as the process of “breaking down the data into pieces” (cfr. gr. analyein), i.e. the generally lossy conversion of data into “local” discrete entities (symbols). These do not include Fourier Analysis, Principal Component Analysis (PCA) and other global transforms. green for signal processing and information theory i.e., the process of breaking down signals into discrete entities or symbols.Discretization is often advocated on complexity grounds, but complexity calls for data compression, not necessarily for data analysis. Any complexity cost could be added to the decision or control functional in Section 2.4.1, and the best decision would still avoid data analysis. Is there an evolutionary advantage in data analysis, beyond it being just a way to perform data compression? These considerations apply regardless of the specific control or decision task, from the simplest binary decision (e.g. “is a specific object present in the scene?”) to the most complex (e.g. “survival”).
So, why would we need, or even benefit from, an internal representation? Is “intelligence” not possible in an “analog” setting? Or is data analysis necessary for cognition? If so, what would be the mathematical and computational principles that guide it? What if the task is not known; is a notion of representation still meaningful in the absence of a task?
In the fields of Signal Processing, Image Processing, and Computer Vision, we routinely torture the data (filtering, sampling, anti-aliasing, edge detection, feature selection, segmentation, etc.), seemingly against the basic tenets of Information and Decision Theory. The Data Processing Inequality would instead suggest an approach whereby data are fed directly into a “black-box” decision or control machine designed to optimize a (possibly very complex) cost functional.
One could argue that data analysis in biological systems is not guided by any optimality principle, but an accident due to the constraints imposed by biological hardware. In , Turing showed that (continuous) reaction-diffusion partial differential equations (PDEs) that govern ion concentrations in neurons exhibit discrete/discontinuous solutions. This may explain “spikes” in neuronal signals and perhaps from there symbols. But if we want to build machines that interact intelligently with their surroundings and are not bound by the constraints of biological hardware, should we draw inspiration from biology, or can we do better by following the principles of Information Theory?
The question of existence of an “internal representation” is best framed within the scope of a task, task which provides a falsifiability mechanism.Of course one could construe the inference of the internal representation as the task itself, but this would be self-referential. In the context of visual analysis I distinguish four broad classes of tasks, which I call the 4 r’s of vision the four “R’s” of vision: Reconstruction (building models of the geometry, or shape, of the scene), Rendering (building models of the photometry, or material properties, of the scene), Recognition and other vision-based decisions such as detection, localization, categorization and more in general scene semantics, and Regulation or, more in general, vision-based control such as tracking, navigation, obstacle avoidance, manipulation etc..
In this manuscript, we will explore the issue of representation from visual data for decision and control tasks. To avoid philosophical entanglements, we will not attempt to define “intelligent behavior” or even “knowledge,” other than to postulate that knowledge – whatever it is – comes from data, but it is not data. This leads to the notion of the “useful portion” of the data, information which one might call “information.” So, our first step will be a definition of what “information” means in the context of performing a decision or action based on sensory data.
As we will see, visual perception plays a key role in the signal-to-symbol barrier. As a result, much of this manuscript is about vision. Specifically, the need to perform decision and control tasks in a manner that is independent of nuisance factors nuisance factors including scaling and occlusion phenomena require the perceptual agent (or, more in general, its evolved species) to exercise control control over certain aspects of the sensing process. This inextricably ties sensing, information and control. A case-in-point is provided by Sea Squirts, or Tunicates, shown in Figure 1.1. These are organisms that possess a nervous system (ganglion cells) and the ability to move. They spend part of their lives as predators, but eventually settle on a rock, become stationary and thence swallow their own brain.This is sometimes used as a metaphor of tenure in academic institutions. Scaling and occlusion play a critical role: The first makes the continuum limit relevant, the second makes control a critical element in the analysis. These are present in a number of remote sensing modalities, including optical, infrared, multi-spectral imaging, as well as active ranging such as radar, lidar, time-of-flight, etc.
This manuscript is designed to allow different levels of reading. Some of the material requires some background beyond calculus and linear algebra. To make the manuscript self-contained, basic elements of topology, variational methods and optimization, image processing, radiometry, etc. are provided in a series of appendices. These are color coded. The parts of the main text that require background in the corresponding discipline are coded with the same color. The reader can then either read through the colored text if he or she is familiar with that subject, disregarding the appendices, or use the appendix as a reference in case he or she is not familiar with the subject, or skip the colored text altogether. The manuscript is structured to allow getting the “big picture” without any mathematical formalism by just reading the black text.
Summary for the experts (to be skipped by others)
This section summarizes the content of the manuscript in a succinct manner. It can be used as a summary, or as a reference to the broader picture while reading the rest of the manuscript. For most readers, this summary will be cryptic or confusing at a first reading. If it was otherwise, there would be no need for a manuscript to follow.
What makes vision difficult, and might explain the fact that almost half of the primate brain is devoted to it , is the fact that nuisance factors in the data formation process account for almost all the complexity of the data . Such factors include invertible nuisances such as contrast and viewpoint (away from occlusions), and non-invertible ones such as occlusions, quantization, noise, and general illumination changes. After discounting the effects of the nuisances in the data (invariance), even if one had started with infinite-resolution data, what is left is “thin” (supported on a zero-measure subset of the image domain). The complexity of the data after the effects of invertible nuisances has been remove is called Actionable Information. The fact that Actionable Information can be thin in the data is relevant to the signal-to-symbol barrier problem.
How can we deal with nuisances? At decision time one can marginalize them (Bayes) or search for the ones that best explain the data (max-out, or maximum-likelihood). Some, however, may be eliminated in a process called canonization. While marginalization and max-out require solving complex integration or optimization problems at decision time, canonization can be pre-computed, and hence it enables straight comparison of statistics at decision time. It is preferable if time-complexity is factored in. However, this benefit comes with a predicament, in that canonization cannot decrease the expected risk, but at best leave it unchanged. Among the statistics that leave the risk unchanged (sufficient statistics), the ones that are also invariant to the nuisances would be the ideal candidates for a representation: They would contain all and only the functions of the data that matter to the task.
Unfortunately, while for invertible nuisances one can construct complete features (invariant sufficient statistics), that act as a lossless representation, occlusion and quantization are not invertible. Thus, there is a gap between the maximal invariant and the minimal sufficient statistics. This gap cannot, in general, be filled by processing passively gathered data.
However, when one can exercise control on the sensing process, then some non-invertible nuisances can become invertible. Occlusions can be inverted by moving around the occluder. Scaling/quantization can be inverted by moving closer. Even the effects of noise can be countered by increasing temporal sampling and performing suitable averaging operations. Therefore, in an active sensing scenario one can construct representations that are (asymptotically) lossless for decision and control tasks, and yet have low complexity relative to the volume of the raw data. This inextricably ties sensing and control. It also may enable achieving provable bounds, by generalizing Rate-Distortion theory to Perception-Control tradeoffs, whereby the “amount of control authority” over the sensing process (to be properly defined) trades off the expected error in a visual decision task.
In this manuscript, we characterize representations as complete invariant statistics, and call hallucinationThe characterization of images as “controlled hallucinations” was introduced by J. Koenderink. the simulation of the data formation process starting from a representation (as opposed to the actual scene). We define Actionable Information as the complexity of the maximal invariant statistics of the data, and Complete Information as the complexity of the (minimal sufficient statistic of a) complete representation. We define co-variant detectors, that enable the process of canonization, and their associated invariant descriptors. We define canonizability, and address the following questions: (i) When is a classifier based on an invariant descriptor optimal? (in the sense of minimizing the expected risk) (ii) what is the best possible descriptor? (iii) what nuisances are canonizable? (and therefore can be dealt with in pre-processing, as opposed to having to be marginalized or max-outed at decision time).
Four concepts introduced in this study are key to the analysis and design of practical systems for performing visual decision and control tasks: Canonizability, Commutativity, Structural Stability, and Proper Sampling. canonizability commutativity structural stability proper sampling
Canonization is not sufficient to infer a complete representation, unless nuisances commute with one another. We show that the only nuisance that is canonizable and commutative is the isometric group of the plane. Affine transformations in general, and the scale group in particular, should not be canonized, but should instead be sampled and marginalized.
Canonizing functionals, designed to select an element of the canonizable nuisance group, should be stable with respect to variations of the non-canonizable nuisances. We introduce the notion of Structural Stability, that is related to catastrophe theory and persistent topology. Selection by maximum structural stability margins gives rise to a novel feature selection scheme .
Whether the structure detected by a canonizing functional is “real” (i.e. it arises from phenomena in the scene) or an “alias” (i.e. it originates from artifacts of the image formation process, for instance quantization) depends on whether the signal is properly sampled. We introduce a notion of proper sampling that, unlike traditional (Nyquist-Shannon) sampling, cannot be decided based on a single datum (one image snapshot), but instead requires multiple images. This notion gives rise to a novel feature tracking scheme .
Intra-class variability can be captured by endowing the space of representations (which are discrete entities) with a probabilistic structure and learning distributions of individual objects or parts, clustered by labels. Objects are not necessarily rigid/static, but can also include “actions” or “events” that unravel in time. Time can be treated as yet another nuisance variable, which unfortunately is not invertible and therefore cannot be canonized without a loss. Time is, therefore, best dealt with by marginalization or max-out at decision time .
Along the way in our investigation we also discuss the role of “textures” and their dual (“structures”), and characterize them as the complement of canonizable regions .
2 Related literature
The design and computation of visual representations for recognition has a long history (see and references therein). While Marr’s representation using zero-crossings of differential operators was discredited because of instability in the reconstruction process (i.e. obtaining images back from their representations), reconstructing images is not necessarily the purpose, if a representation is to support decision and control tasks. Many have attempted to design representations that are tailored to recognition (as opposed to image reconstruction) tasks, some using similar ideas of extrema of scale-spaces constructed from differential operators . However, most of these designs have been performed in an ad-hoc manner, guided by intuition, common sense, and some biological inspiration. Statistical decision theory would instead call for the direct design of general “super-classifiers” forgoing intermediate representations altogether, unless directly tied to the task.
Our earlier work aims to frame the construction of invariant/sufficient representations in the context of Active Vision, formalizing some ideas of J. J. Gibson . Gibson’s approach, however, falls short on several counts. First, invariance is too much to ask. In the process of being invariant to general viewpoints, shape becomes indiscriminative . And yet, we know we can discriminate objects that are deformed versions of the same material. Second, often priors are available, from training or otherwise, both on the nuisance and on the class, and such priors should be used. There is no point in requiring invariance to illuminations that will never be; better instead to be insensitive to common nuisances, and relax the representation where nuisances have low probability even though this opens the possibility of illusions for unlikely nuisance and scene combinations (Fig. 1.2).
Third, even though the Active Vision paradigm is appealing, in practice we often do not have control on the sensing platform.
Therefore, there remains the need to properly treat nuisances that are non-invertible, such as occlusions, quantization and noise, in a passive sensing scenario, and to be able to exploit priors when available.
The recent literature is studded with different approaches for low-level pre-processing of images for visual classification. These include various feature detectors and descriptors, too many to cite extensively, but the most common being . These are compared empirically on end-to-end tasks such as wide-baseline matching , categorization , or category localization and segmentation tasks. However, an empirical evaluation tells us which scheme performs better, but gives us no indication as to the relation between different schemes, no hint on how to improve them, and no bounds on the best achievable performance that can be extrapolated to other datasets with provable guarantees.
Therefore, there remains the need to develop a framework for the analysis and design of feature detectors/descriptors, that allows rational comparison of existing descriptors, and engineering design of new ones, and understanding of the conditions under which they can be expected to perform.
There is a sizable literature on the detection and computation of structures in images. In particular, derive detectors based on a series of axioms and postulates. However, while these explain how such low-level representations should be constructed, they give no indication as to why they would be needed in the first place. Much of the motivation in this literature stems from biology, and in particular the structure of early stages of processing in the primate visual system.
By its nature, this manuscript relates to a vast body of literature in low-level vision and also Active Vision . Ideally it relates to every paper, by providing a framework where different approaches can be understood and compared. However, it is possible that some approaches may not fit into this framework. I hope that this work provides a seed that others can grow or amend.
This manuscript also lends some analytical support for the notion of embodied cognition that has been championed by cognitive roboticists and philosophers including .
Finally, the work of Naftali Tishby and co-workers, starting from , has been addressing similar questions using an information-theoretic framework; work is underway to combine and reconcile the two approaches.
Chapter 2 Formalizing Visual Decisions
Visual classification tasks – including detection, localization, categorization, and recognition of general object classes in images and video – are challenging because of large in-class variability. For instance, the class “chair”, defined as “something you can sit on” (presumably man-made), comprises a diversity of shapes, sizes and materials that result in a wide variety of images (Figure 2.1).
Even if one sets aside within-class variability and considers the detection, localization or recognition of an individual object (e.g. this chair) from a field of alternate hypotheses (e.g. other chairs), the data still exhibits large variability due to nuisance factors nuisance such as viewpoint, illumination, occlusion, etc., that have little to do with the identity of the object (Figure 2.2).
It is tempting to hope that a powerful classifier fed with raw data could be trained to, somehow, learn-away discard the variability in images due to nuisance factors, and reliably recognize object, their classes and relations in pictures. The results in suggest otherwise, since the volume of the quotient of the set of images modulo changes of viewpoint and contrast is infinitesimal relative to the volume of the data. This means that a hypothetical classifier fed with raw images would spend almost all of its resources learning the nuisance variability, rather than the intrinsic variability of objects of interest. This is realistic at the phylogenic (at the evolutionary time scale), but not at the individual (ontogenic) level. This would hold a-fortiori once complex illumination phenomena, occlusions, and quantization – all neglected in – were factored in.T. Poggio recently put forward the hypothesis that this is true also in biology, in the sense that the complexity of the primate visual system is mainly to deal with nuisances, rather than to capture the intrinsic variability of the objects of interest .
Moreover, if one’s training consists of individual images each of a different scene, as in Fig. 2.1, the process is even more problematic as a single image does not afford the ability of disentangling nuisance variability from intrinsic variability, and the complexity of the scene is infinitely more complex than the complexity of (even infinitely many) images. Therefore, a hypothetical learning machine fed with however large a dataset of individual images, each of a different scene, would never even learn that there is a scene, with shape, reflectance, illumination, etc. but instead just learn patterns of intensity in the images.
It is equally tempting to hope that one could pre-process the data to obtain some “features,” that do not depend on these nuisances, features and yet retain all the “information” present in the data. Indeed, suggests a construction of such features that, however, requires nuisances to have the structure of a group and hence breaks down in the presence of complex illumination effects, occlusions and quantization. One could relax such strict “invariance” requirement to some sort of “insensitivity” but, in general, pre-processing can only reduce the performance of any classifier downstream . This brings into question the role of “vision-as-pre-processingFor pre-processing to be sound, some kind of “separation principle” should hold, so that different modules of a visual inference system could be designed and engineered independently, knowing that their composition or interconnection would yield sensible end-to-end performance. for general-purpose machine learning.” Why should one performAs we have already pointed out in the preamble, computational efficiency alone does not justify the discretization process. segmentation, edge detection, feature selection and other generic low-level vision (pre-processing) operations, if the classification performance decreases?
This goes to the heart of a notion of “information.” Ideally, the purpose of vision would be to “extract information” from images, where “information” intuitively relates to whatever portion of the data “matters” in some sense. Traditional Information Theory has been developed in the context data transmission, where one wants to reproduce as faithful as possible a copy of the data emitted by the source, after it has been corrupted by the channel. Thus the goal is reproduction (or reconstruction) of the data, with minimal distortion, and the “representation” simply consists of a compressed encoding of the data that exploits statistical regularity. In this context, every bit counts, and the semantic aspect of information is indeed irrelevant, as Shannon famously wrote. The theory yields a tradeoff between the minimum size of the representation as a function of the maximum amount of distortion. This tradeoff is computed explicitly for very simple cases (e.g. the memoryless Gaussian channel), but nevertheless the general formulation of the problem is one of Shannon’s most significant achievements.
In our context, the data (images) are to be used for decision purposes (detection, localization, recognition, categorization). The goal is to minimize risk. In this context, there may be conditions where most of the data is useless, and the semantic aspect is fundamental, for the sufficient statistics can be discrete (symbols) even when the data lives in the continuum.
Several have advocated the development of a theory, mirroring Shannon’s Rate-Distortion Theory, to describe the minimum requirements (in terms of size of the representation, computational or other “cost”) in order to have a recognition error that is bounded above. Ideally, like in Shannon’s case, this bound could be made arbitrarily small by paying a high-enough price. Despite many efforts, no theory has emerged, only special cases restricted to imaging modalities where some of the crucial aspects of image formation (scaling and occlusions) are not manifest. This may not be by chance because, in the context of visual recognition, the worst-case scenario is an arbitrarily high error rate. This is not surprising, and indeed can be considered trivial. What may be a bit more surprising is that even the average-case scenario can be arbitrarily bad, as we will argue in Section LABEL:sect-passive-bounds. This may also shed some light on the limitations of benchmark datasets, if the performance of a given algorithm is interpreted as representative of performance on other datasets. The result of the benchmarking are meaningful to the extent in which the dataset is representative of the scenarios one wishes to capture, but no guarantee can be made on the generalization properties of these methods. Again, scale, quantization and occlusion conjure towards the failure of any “passive” recognition scheme to provide generalization bounds. What is surprising is that, if the data acquisition process can be controlled, then both the worst-case and average-case error can be bounded, and indeed they can be made (asymptotically) arbitrarily small (Section LABEL:sect-active-bounds). Analogously to Shannon’s Rate-Distortion theory, there is a tradeoff between the “control authority” one can exercise over the sensing process, and the performance in a decision task (Section LABEL:sect-control-recognition).
In the next section, we begin the formalization process necessary to answer some of the questions raised so far. For the purpose of simplicity, we will reduce visual perception to a collection of classification tasks, which is admittedly restrictive, but sufficient to commence formalization.
By “visual decision” we mean tasks such as detection, localization, categorization and recognition of objects objects in images or video. These are all classification problems, where in some cases the class is a singleton (recognition), in other cases it can be quite general depending on functional or semantic properties of objects (Figure 2.1). Conceptually, they all require the evaluation and learning of the likelihood of the data (one or more images ) given the class label : . To simplify the narrative, we consider binary classifiers with equal prior probability . Generalizations are conceptually, although not computationally, straightforward.
It can be shown that the decision rule that minimizes the conditional risk, that is
is optimal in the sense that it minimizes the expected (Bayesian) risk
That is, if one could actually compute this quantity, which depends on the availability of the probability measure , which is tricky to even define, let alone learn and compute . However, in the context of our investigation this is irrelevant: Whatever mathematical object is, we can easily sample from it by simply capturing images , as we will see in Section 8. We will see in Section 3.1 that, even to generate “simulated images,” we do not need access to the “true” distribution , but rather to a representation, which we will define in Section 3 and discuss in Section 3.1.
Under the assumptions made, minimizing the conditional risk is equivalent to maximizing the posterior , which in turn (under equiprobable priors ) is equivalent to maximizing the likelihood :
So, in a sense, the problem of visual decision-making, including detection, localization, recognition, categorization, is encapsulated in (2.4). That would be easy enough to solve if we could actually compute the likelihood.
The difficulty in visual decision problems arises from the fact that the image depends on a number of nuisance factors nuisance that do not depend on the class, and yet they affect the data. What is a nuisance depends on the task, and may include viewpoint, illumination, partial occlusions, quantization etc. (Figure 2.2). If we could, we would base our decision not on the data , but on hidden variables that comprise the defining characteristics of the scene (object, category, location, event, activity etc.) that depend on the class , through a Markov chain . scene This would correspond to a data generation model whereby a sample is selected from , based on which a sample is selected from , from which a measurement is finally sampled via an image-formation functional .
However, because of the nuisances, we have to instead consider a generative model of the form , where is a functional that depends on the imaging device and are all the nuisance factors. It is convenient to isolate within the nuisance the additive noise component arising from the compound effects of un-modeled uncertainty, although there is no added generality as can be subsumed in the definition of . It is also useful to isolate the nuisances that act as a group on the scene, , although again we could lump them into the definition of . If we model explicitly the group and the noise, we have a model of the form
This is the formal model that we will adopt throughout the manuscript (Figure 2.2). In the next section we make this formal notation a bit more precise with a specific instantiation, the so-called Ambient-Lambert model. More realistic instantiations are described in Appendix B.1. The reader interested in generalizations of the simple symmetric binary decision case can consult any number of textbooks, for instance .
2 Image formation: The image, the scene, the nuisance, and the Lambert-Ambient (LA) Model
In this section, that can be skipped at first reading, we instantiate the formal notation (2.5) for a simple model used throughout the manuscript. All the symbols used, together with their meaning, are summarized for later reference in Appendix C in the order in which they appear. This section is necessary to make the formal notation above meaningful. However, its content will actually not be used until Sections 3.1, 3.4, and will be exploited in full only starting in Section 4. Therefore, the reader can skip this section at first reading, and come back to it, or to Appendix C, as needed. The model we introduce in this section is the simplest instantiation of (2.5) that is meaningful in the context of image analysis. More sophisticated models, and their relation to the simplest one introduced here, are described in Appendix B.1.
Nuisance factors in the image-formation process are divided into two components, , one that has the structure of a group , and a component that is not a group, e.g. quantization, occlusions, cast shadows, sensor noise etc. We denote the image-formation model formally with a functional , so that as in (2.5). This highlights the role of group nuisances , the scene , non-invertible nuisances, and the additive residual that lumps together all unmodeled phenomena including noise and quantization (non-additive noise phenomena can be subsumed in the non-invertible nuisance ). We often refer to the group nuisances as invertible invertible nuisance and the non-group nuisances as non-invertible.
Note that the number of points in the pre-image depends on , and is indicated by . The pixel locations where two pre-images coincide are the occluding boundaries, occluding boundaries also known as silhouettes. silhouette For instance, for some is an occluding boundary. If we sort the points in order of increasing depth, so that , then the pre-image, restricted to the point of first intersection, is indicated by
Note that the image only exists for , and the pre-image only exists for . For the region of the image where the scene is visible, say at time , we can represent as the graph of a function defined on the domain of the image , so . Here can be taken to be the identity function, , so that Therefore, combining this equation with (2.6), we have , with the relation between and being
This is know as the “brightness constancy constraint equation.” brightness constancy constraint Note that the two previous equations are simultaneously valid only in
3 Marginalization, extremization (max-out), blurring
If we have prior knowledge on all the hidden variables, , we can compute the likelihood in (2.4) by marginalization. This is conceptually trivial, but computationally prohibitive. Prior knowledge on the nuisance is encoded in a distribution , which may have a density with respect to a base measure . Prior knowledge on the scene is encoded in the class-conditional distribution , which may again have a density with respect to a base measure . The same goes with the group .One may encode complete ignorance of some of the group parameters by allowing a subgroup of to have a uniform prior, a.k.a. uninformative, and possibly improper, i.e. not integrating to one, if the subgroup is not compact. We can reasonablyIf this is not the case, that is if the residual exhibits significant spatial or temporal structure, such structure can be explicitly modeled, thus leaving the residual white. assume that the residual, after all relevant aspects of the problem have been explicitly modeled, is a white zero-mean Gaussian noise with covariance . Marginalization then consists of the computation of the following integral
The problem with this approach is not just that this integral is difficult to compute. Indeed, even for the simplest instantiation of the image formation model (2.6), it is not clear how to even define a base measure on the sets of scenes and nuisances , let alone putting a probability on them, and learning a prior model. It would be tempting to discretize the model (2.6) to make everything finite-dimensional; unfortunately, because of scaling and quantization phenomena in image formation, any reasonable discretization of the scene would yield a very large scale inference problem. This integral is costly to compute even for the simplest characterizations of the scene and the nuisances. Indeed, the space of scenes (shape, radiance distribution functions) does not admit a “natural” or “sufficient” discretization. However, if one was able to do so, then a threshold on the likelihood ratio, depending on the priors of each class, yields the optimal (Bayes) classifier . Recently, a local approximation of the above integral has been proposed in , and named R-HOG (reconstructive HOG).
An alternative to marginalization, where all possible values of the nuisance are considered with a weight proportional to their prior density, is to find the class together with the value of all the hidden variables that maximize the likelihood:
This procedure of eliminating nuisances by solving an optimization problem is called “extremization” or sometimes “max-out” of the hidden variables. A threshold on the result yields the maximum likelihood (ML) classifier. Needless to say, this is also a complex procedure. This procedure also relates to registration or alignment between (test) data and a “template,” a common practice in pattern recognition. Recently, a local approximation of the above integral has been proposed in , and named MV-HOG (multi-view HOG).
A third alternative to obtain statistics that reduce the variability of the data with respect to nuisances is to average the data with respect to the group action. For instance, a function of the image that is invariant to planar rotations can be easily computed by averaging rotated versions of the image. This is clearly lossy, as there are many different scenes that produce the same invariant, so one may want to restrict the averaging to small transformations. If the averaging is done properly , the process can be made lossless and therefore provide true invariance, at least to a small group of transformations, but in general produces statistics that are insensitive (as opposed to “invariant” or “stable”). The next section describes an alternative, further elaborated in Section 3. Note that the max-out procedure can be understood as a special case of marginalization when the prior is uniform (possibly improper). Therefore, we will use the term marginalization to refer to either procedure, depending on whether or not a prior is available.
4 Features
One can think of a feature as any kind of “pre-processing” of the data. The question as to whether such pre-processing is useful is addressed by the data processing inequality.
In other words, there is no benefit in pre-processing the data. This results follows simply from the Markov chain dependency , known as “data processing inequality” ( Theorem 2.8.1, page 32, and the following corollary on page 33). Thus, it seems that the best one can do is to forgo pre-processing and just use the raw data. Even if the purpose of a feature is to reduce the complexity of the problem, this is in general done at a loss, because one could include a complexity measure in the risk functional , and still be bound by (2.14). However, there are some statistics that are “useful” in a sense that we now discuss.
4.2 Sufficient statistics
Clearly, sufficiency and minimality represent useful properties of a statistic. A minimal sufficient statistic contains everything in the data that matters for the decision; no more (minimality) and no less (sufficiency). Unfortunately, (finite-dimensional) sufficient statistics do not always exist, so relaxed versions of the notion of sufficient statistics have been developed , and will be discussed later in this manuscript. Another useful property of a feature is that it contains nothing that depends on the nuisances.
4.3 Invariance
Any constant function is an invariant feature, ; obviously it is not very useful. Of all invariant features, we are interested in the “largest,” in the sense that all other invariants are functions of it. We call this the maximal invariant, and indicate it with the symbol or when the group is clear from the context. maximal invariant
In general, there is no guarantee that an invariant feature, even the maximal one, be a sufficient statistic. In the process of removing the effects of the nuisances from the data, one may lose discriminative power, quantified by an increase in the expected risk. Vice-versa, there is no guarantee that a sufficient statistic, even the minimal, be invariant. In the best of all worlds, one could have a minimal sufficient statistic that is also invariant, or vice-versa that a maximal invariant that is sufficient. In this case, the feature would be the best form of pre-processing one could hope for: It contains all and only the “information” the data contains about , and have no dependency on the nuisance. We call a minimal sufficient invariant statistic a complete feature. complete feature Note that, in general, a complete feature is still not equivalent to itself, for the map may not be injective (one-to-one). However, it can be shown that when the nuisance has the structure of a group, one can define an invariant statistical model (Definition 7.1, page 268 of ) and design a classifier, called equi-variant, equi-variant classifier that achieves the minimum (Bayesian) risk (see Theorem 7.4, page 269 of ). This can be done even in the absence of a prior, assuming a uniform (“un-informative” and possibly improper) prior. For this reason, we will be focusing on the design of invariants to the group component of the nuisance, an refer to -invariants as simply invariants.
Therefore, if all the nuisances had the structure of a group , i.e. when , the maximal invariant would also be a sufficient statistic, and this would be a very fortunate circumstance (Example 1). Unfortunately, in vision this does not usually happen, since the nuisance groups of interest act on the scene, rather than the image. Nevertheless, it may be possible to compute invariants if we are willing to act (Section 8).
4.4 Representation
Given a scene , we call the set of all possible images that can be generated by that scene up to an uninformativeFor instance, a spatially and temporally independent homoscedastic noise process. residual:
We have omitted the additive noise term since, in general, it describes the compound effect of multiple factors that we do not model explicitly, and therefore it is only described in terms of its ensemble properties from which it can be easily sampled. The sign above indicates that the scene image is determined up to the additive residual , which is assumed to be spatially and temporally white, identically distributed with an isotropic density (homoscedastic). It is, by definition, uninformative.If it is not, as previously pointed out, the phenomena that cause violations of these assumptions can be modeled explicitly.
Given an image , in general there are infinitely many scenes that could have generated it under some unknown nuisances, so that
We call any such scene a representation compatible with that image. representation A representation is a feature, i.e. , a function of the data: It is the pre-image (under ) of the measured image : , and takes values in the space of all possible scenes .
Note that there is no requirement that the representation be unique, or have anything to do with the “true” scene ; the relation between the two is explored in Chapter 8.Indeed, some philosophers would argue that for a theory to be viable it must not rely on the existence of the “true scene.”
While this concept of representation is pointless for a single image, it is important when considering multiple images of the same scene. In this case, the requirement is that the single representation simultaneously “explains” an entire set of images of the same scene:
Of all representations, we will be interested in either the “most probable,” if we are lucky enough to have a prior on the set of scenes , which is rare, or in the simplest one, which we call the minimal representation (a minimal sufficient statistic), and indicate with .
Given a scene , we are particularly interested in the minimal representation that can generate all possible images that the original scene can generate, up to uninformative residuals. We call this a complete representation: complete representation
In other words, a representation is a scene from which the given data can be hallucinated. We will elaborate the issue of hallucination in Section 3.1, where we will describe the relation to the light field. light field For the purpose of a visual decision task, a complete representation is as close as we can get to reality (the scene ) starting from the data.
5 Actionable Information and Complete Information
The complexity of the data, measured in various ways, e.g. via coding length or algorithmic complexity , has traditionally been called “information” in the context of data compression and transmission. Although the complexity of an image may be relevant to transmission and storage tasks (the most costly signal to transmit and store is white noise), it is in general not relevant to decision or control tasks. Extremely complex data, where all the complexity arises from nuisance factors, is useless for visual decisions, so one could say that such data is “uninformative.” Vice-versa, there could be very simple data that are directly relevant to the decision. So, the complexity of the data itself is not a viable measure of the information content in the data for the purpose of visual decisions. A natural image is not just a random collection of pixels; rather, an image is a sample from a distribution of (natural) images, , not a distribution in itself. So, if we want to measure the “informative content” of an image, we have to do so relative to the scene.
In Section LABEL:sect-control-recognition we will explore the relation between Actionable Information and the conditional entropy of the image given an estimated description of the scene. Now, it is possible that the maximal invariant of the data contains no information at all about the object of inference. What would be most useful to perform the task would be a complete representation, . Of all statistics of the complete representation we are interested in the smallest, so we could measure the complete information as the entropy of a minimal sufficient statistic of the complete representation. complete information
We will defer the issue of computing these quantities to Section 8, although one could already conjecture that
It is important to notice that, whereas the scene consists of complex objects (shapes, reflectance functions) that live in infinite-dimensional spaces that do not admit simple base measures, let alone distributions of which we can easily compute the entropy, the representation is a function of the measured data, which lives in a benign finite-dimensional space.
It is interesting to notice that there are cases when . This happens, for instance, when the only existing nuisances have the structure of a group. For instance, if contrast is the only nuisance, then the geometry of the level lines (or equivalently the gradient direction) is a complete contrast invariant. Likewise, for viewpoint and contrast nuisances, the ART is a complete feature.In general, however, this is not the case, and the ART should be considered just a conceptual construction to illustrate the critical role of nuisance factors in the variability of imaging data.
6 Optimality and the relation between features and the classifier
Eliminating nuisances via marginalization yields classification that is “optimal” by definition. Eliminating nuisances via the design of invariant features yields optimal classification only if the nuisances have the structure of a group, i.e. . That is, there are no other nuisances other than the group and the latter admits a representation on the image. In this case, one can “pre-process” both the data and the training set to eliminate the effects of , and design an equivalent statistical model (called an “invariant” model), and an equi-variant classifier. In Section 4 we will show constructive ways of designing invariant features, via the use of co-variant detectors and their corresponding invariant descriptors.
Optimality, as we have defined it in (2.2), does not impose restrictions on the set of classifiers, and the data processing inequality (2.14) stipulates that any pre-processing can at best keep the Bayesian risk constant, but not decrease it. In the presence of only invertible nuisances, , it is sensible to compute the maximal invariant to eliminate group nuisances, but non-invertible nuisances can only be eliminated without a loss at decision time, via marginalization or extremization. This puts all the burden on the classifier, that at decision time has to compute a complex integral (2.12), or solve a complex optimization problem (2.13).
An alternative to this strategy is to constrain the choice of classifiers by limiting the processing to be performed at decision time. For instance, one could constrain the classifiers to nearest-neighbor nearest-neighbor rules, with respect to the distance between statistics computed on the test data (features) and statistics computed on the training data (templates). Two questions then arise naturally: What is the “best” template, if there is one? Of course, even choosing the best template, a feature-template nearest neighbor is not necessarily optimal. Therefore, the second question is: When is a template-based approach optimal? We address these questions next.
This section refers to a particular instantiation of visual decision problems, where the set of allowable classifiers is constrained to be on the form
for some statistic and some choice of distance or norm in the space of images. Here is a function of the likelihood that can be pre-computed, and is called a template. template If the likelihood is given in terms of samples (training set) training set , then the template can be any statistic of the (training) data. In particular, a distance can be defined by designing features that are invariant to the group component of the nuisance . In this case, the space is the quotient of the set of images modulo the group component of the nuisance, which is in general not a linear space even when both and are linear. The distance above is a cordal distance, that does not respect the geometric structure of the quotient space . A better choice would be to define a geodesic distance, or a distance between equivalence classes, . The structure of orbit spaces of scenes under the action of finite-dimensional groups is conceptually clear and will not be further discussed here (see Appendix A.1). Instead, we focus on the two critical questions: First, what is the “best” template , and how can it be computed from the training set? Second, are there situations or conditions under which this approach can yield the same performance of the Bayes or ML classifiers? (Section 3). In Section 6 we will show that one can build the equivalent of a template also for the test set, provided that a “sufficiently exciting” test sample is available. sufficiently exciting sample
that is solved by the conditional mean and approximated by the sample mean obtained from the training set
Note that the relationship between a template-based nearest-neighbor classifier and a classifier based on the proper likelihood is not straightforward, even if the class consists of a singleton – which means that it could be captured by a single “template” if there were no nuisances. The marginalized likelihood is
assuming a normal density for the additive residual , with covariance , where is a Mahalanobis norm, ; the nearest-neighbor template-based classifier would instead try to maximize
The quantity bracketed is called the blurred template blurred template
which does not depend on the nuisance not because it has been marginalized or max-outed, but because it has been “blurred” or “smeared” all over the template. This strategy does not rest on sound decision-theoretic principles, and yet it is one of the most commonly used in a variety of classification domains, from nearest neighbor to support vector machines (SVM) to neural networks , to boosting .
It should be clear that blurring is a lossy process, as aggregating the training set into a single statistic decreases the discriminative power of the approach. One could attempt to minimize the loss, as done by Mallat and co-workers , who devise an iterative coding/blurring process that is lossless in the limit, for sufficiently concentrated nuisance distributions; the process is then truncated after two stages and not carried to the limit, so the loss remains.
Note that if instead of computing distance in the embedding space we compute the distance in the quotient, , we do not need to blur out the group in the template. In fact, the expectation of the quantity
Note that we have implicitly assumed that acts linearly on the space , lest we would have to consider , rather than . We discuss linear features in more detail in Section 4.2.
As for how the priors can be learned from the data, we defer the answer to Section 9 since it is not specific to the use of templates. For now, we note that – should a prior be available – it can be used according to (2.25) for the case of classifiers based on features/templates, (2.12) for the case of Bayesian and (2.13) for the case of ML classifiers.
The second question, which is under what conditions this template-based approach is optimal, is somewhat more delicate and will be addressed in Section 3.4. The short answer is never, in the sense that if it were optimal, there would be no need for averaging. However, a template approach can be advocated when there are constraint on decision-time, and at least some of the nuisances can be eliminated via canonization, as described in Section 3, and the residual uncertainty is described by a uni-modal class-conditional density that is well captured by its mode or mean (2.30).
When the template is computed on the test data, it can be used as a “descriptor”, descriptor that is, an invariant feature. More general descriptors will be discussed in the next chapter, and how to construct them from data will be described in Section 6.
The term template refers to a large variety of approaches, only some of which are captured by the definition we have given in this chapter. In particular, Deformable Templates, studied in depth by Grenander and coworkers , are based on premises that are not valid in our setting. In fact, in Deformable Templates there is an underlying hidden variable, the “template” (which could be given or learned), that is acted upon by a “deformation” (typically an infinite-dimensional group of diffeomorphisms). However, in Grenander’s approach the group acts transitively on the template, meaning that from the template one can “reach” any object of interest. In other words, there is a single orbit that covers the entire space of the measurements. In this case, all the “information” is contained in the deformation (the group), that is therefore not a nuisance.
To introduce the next chapter, we consider the simple example of classification of hand-written digits. This is simple because the data formation process lacks the two fundamental phenomena we discussed in the previous chapter: Scaling and occlusion. The only nuisance variability is due to small deformations of the domain (geometric deformations, including misalignment), and range (stroke thickness). Fig. 2.6 shows a collection of images from the MNIST Digit dataset and the corresponding blurred templates. Then further templates are shown when the dataset is blurred with respect to additional translation, Euclidean transformations, and affine transformations. It is clear that discriminative power has been lost, since the digits can hardly be recognized from the blurred template. However, classification is increasingly insensitive to the transformations being considered, as the distance to a template changes little as the test sample is, respectively, translated, translated and rotated, or transformed with an affine map.
The likelihood of a test sample under the blurred template changes depending on whether the template has been blurred, or whether the nuisance transformation has been marginalied, or eliminated with max-out. The latter two operations entail an integral or a search at test time. When the nuisance is canonized, through a process that we describe in the next chapter, test-time complexity is the same as when the template is blurred, but the likelihood is similar to the case when the nuisance is marginazlied or max-outed.
Chapter 3 Canonized Features
Invariant features can be designed in a number of ways. In this section we describe a constructive approach called canonization,The name “canonization” comes from the fact that a co-variant detector determines a canonical frame, or a canonical element of the group. In an ecclesiastic context, canonization is the elevation of an individual to one of the steps to the ladder of sanctitude. Similarly, a co-variant detector has the authority to elevate a group element to be “special” in the sense of determining the reference frame around which the data is described. However, this must be followed by additional steps, that are discussed in future chapters. Canonical elements are not unique, but they are isolated and sparse. that leverages on the notion of co-variant detector and its associated invariant descriptor. This is also related to the notions of alignment and registration. alignment registration The basic idea is that a group acting on a space organizes it into orbits, each orbit being an equivalence class equivalence class (reflexive, symmetric, transitive) representable with any one element along the orbit. Of all possible choices of representatives, we are looking for one that is canonical, in the sense that it is isolated and can be determined consistently for each orbit. This corresponds to cutting a section (or base) of the orbit space. All considerations (defining a base measure, distributions, discriminant functions) can be restricted to the base, which is now independent of the group and effectively represents the quotient space . Alternatively, one can use the entire orbit as an invariant representation, and then define distances and discriminant functions among orbits, for instance via max-out, , as we discussed in the previous chapter.
The name of the game in canonization is to design a functional – called feature detector – that chooses a canonical representative for a certain nuisance that is insensitive to (ideally independent of) other nuisances. We will discuss the issue of interaction of nuisances in canonization in Section 3.4. Before doing so, however, we recall some nomenclature.
and for all in the appropriate spaces, where is the identity transformation.
In other words, an invariant feature is a function of the data that does not depend on the nuisance. Note that we are focusing on the group component of the nuisance, for reasons explained in the previous chapter and further elaborated in Section 3.4. We recall the definition of representation from Section 2.4.4:
Given a collection of images , a feature is a representation if , where . Equivalently, . Given a scene , a representation is complete if it satisfies the compatibility condition ; a minimal complete representation is a minimal sufficient statistic of .
A representation is three things at once: It is a statistic, that is a function of the images. However, it is embedded in the space of scenes, so it can be thought of as a scene itself. For instance, given a single image, under the Lambert-Ambient-Static model (2.6) of Section 2.2, one can construct a representation that is a plane (shape ) with the image glued onto it, so . Finally, the representation is a finite-complexity data structure that can be stored in the memory of a digital computer. We call it a “feature,” even though it lives in the embedding space of the scene, because, as we will show in Section 8, it can be computed from data.
A minimal complete representation, which we refer to as a “representation” without additional qualifications when clear from the context, would be the ideal feature, in the sense that it captures everything about the scene that can be gathered from the data except for the effect of the nuisances. When non-invertible nuisances are absent, , a representation can be used as a representative of the orbits (equivalence classes) :
Clearly the absence of non-invertible nuisances is a rare phenomenon, especially in vision where scaling and occlusion phenomena are dominant. Nevertheless, there are some cases of practical relevance where non-invertible nuisances are by and large absent (other than the additive “noise” component), such as the classification of hand-written digits of Fig. 2.6. The case where other nuisances are present, , requires some attention and will not be fully addressed until after Section 3.4. In the next section, however, we pause to elaborate on the notion of representation and what it entails. Then, we study the groups for which complete features exist (Section 3.4).
If there were only invertible nuisances, there would be no need for a notion of representation, since the equivalence class is a complete feature and it can be inferred from a single datum. One would only have to learn the intra-class variability, that some have argued is considerably simpler . To begin understanding the notion of representation in the presence of non-invertible nuisances, we need to go back to the image formation model (2.6), and in particular to the pre-image of a point on the domain of an image (2.7):
We note that this set may contain multiple elements, and in particular all points that lie on the same projection ray :
In Section 2.4.4 we have hinted at the fact that the scene itself may not be a viable representation of the images that it has generated, which may appear strange at first. Indeed, the “true” scene may never be known, because it exists at a level of granularity that is finer than any instrument we have available to measure it. So, we only have access to the “true” scene via the data formation process (visual or otherwise). This is unlike a representation , that can be arbitrarily manipulated in order to generate any image .
In the presence of occlusions, evaluating the (hypothetical) “ideal image” , that is the image that would be obtained if there were no nuisances, requires the “inversion” of the occlusion process, including a description of the scene both in the visible and in the non-visible portions. In formulas, from (2.6) and (2.7), we have ideal image
Note that what this object returns is not the shape of the scene, but the radiance of the scene in both the visible and the occluded portions of the scene. So, in a sense, it is an image of a “semi-transparent world” made of many simply connected surfaces. Note, however, that the 3-D geometry may be recovered if we can control the data acquisition process via , with as described in Chapter 8, because by doing so we can generate the collection of all possible occluding boundaries, which is equivalent to an approximation of the 3-D geometry of the scene . In any case, the hypothetical image captures the topology of the world, reflected in the number of layers present in the pre-image. While the notion of ideal image is awkward, and we will soon move beyond it, we need to consider it for a little while longer to ascertain what would be possible (or may be possible, depending on the sensing modality) if there were only invertible nuisances.
As we have anticipated in Section 2.4.4, building a representation from a single image would not be very useful, because in general the space of all scenes is much larger than the space of all images , and lifting the image onto the scene yields no practical benefit. However, one may be able to construct a representation that is compatible with a collection of images, , in the sense that
for all and for some , but the same . In fact, once we have an hallucinated scene , we can produce infinitely many “virtual” images, that we can then compare with any real image that is actually measured. In fact, produces the set of all possible hallucinated images of the scene , and is therefore equivalent to its light fieldA representation enables generating images with any nuisance combinations. In this sense it is “equivalent” to the light field, because it can generate any image that a sampling of the light field would produce. How to store this representation, and how it is compatible with the computational architecture of the primate’s brain, is well outside the scope of this manuscript. However, others have tackled this question, most notably Koenderink and van Doorn, who have studied in depth the structure of the representation (even though it is not called a representation) and its relation to the light field, and also coined the phrase “images as controlled hallucinations.” We refer the reader to their work ( and references therein) for further investigations on this topic. In our case, we will give a constructive example on how to build and store a representation through the exploration process in Section 8. . While the hypothesis cannot be tested, and a meaningful distance cannot be computed (we do not even have a metric in the space ), the hypothesis for some can be very simply tested by comparing two images, which is a task that poses no philosophical or mathematical difficulties. In compact notation, what we can test is . We will return to this issue in Sections 5.1 and 8.
So far we have described the hallucination process, by which a representation can be used to generate images. The inverse process of hallucination is exploration, exploration by which one can use images to construct a representation. In Section 8 we will show how to perform this limit operation. Exactly how the representation , built through exploration, is related to the actual “real” scene , for instance whether they are “close” in some sense, hinges on the characterization of visual ambiguities, which we discuss in Appendix B.3.
We will come back to the notion of representation after establishing what could be done if only invertible nuisances were present, and establishing exactly what nuisances are indeed invertible.
2 Optimal classification with canonization
In this section and the next we elaborate on what would be possible if all nuisances were invertible.Note that this situation is hypothetical, for even a group (e.g. vantage point) acting on the scene () can generate non-invertible nuisances (self-occlusions ). According to the Ambient-Lambert model, a group transformation due to a change of vantage point induces on the image domain an epipolar transformation that, depending on the shape of the scene, can be arbitrarily complex. In particular, such a transformation need not be a function in the sense that self-occlusion will cause the pre-image of a point via the domain deformation to have multiple values. This issue will be resolved in later sections; for now, we assume that the scene is such that a group nuisance does not induce non-invertible transformations of the image domain. In particular, it has been shown in that – in the absence of occlusion phenomena – the closure of epipolar domain deformations has as closure the entire group of planar diffeomorphisms. So, we assume that , and focus on the role of . We will address in Section 3.4. For now, we are interested in how to design invariant and sufficient statistics for alone, as if all other nuisances were absent. In this case, we can assume that the group acts on the space of images, or that the space of scenes and the space of images coincide.
One of the many possible ways of designing an invariant feature is to use the data to “fix” a particular group element , and then “undo” it from the data. If the data does not allow fixing a group element , it means it is already invariant to . So, we define a (co-variant) feature detector to be a functional designed to choose a particular group action , from which we can easily design an invariant feature, often referred to as an invariant (feature) descriptor. Note that both the detector and the descriptor are deterministic functions of the data, hence both are features. One can think of this process as some kind of registration, or alignment, but rather than registering to a target, it is a form of “self-alignment.”
If we call the gradient of the functional with respect to (any) parametrization of the group,The following discussion is restricted to finite-dimensional groups, but it could be extended with some effort to infinite-dimensional ones. then under certain (so-called “transversality”) conditions on , the equation locally determines as a function of , , via the Implicit Function Theorem. Such conditions are independent of the parametrization and consist of the Hessian matrix (i.e. the Jacobian of ) being non-singular, . The function is unique in a neighborhood where the transversality condition is satisfied, and is called a (local) canonical representative of the group. If the canonical representative co-varies with the group, in the sense that , then the functional is called a co-variant detector. Each co-variant detector determines a local reference frame so that, if the image is transformed by the action of the group, a hypothetical observer attached to the co-variant frame (i.e., a “Lagrangian” observer) would see no changes. We summarize this in the following definition:
The equation locally determines a unique isolated extremum in the frame , and
if , then , i.e. , co-varies with .
The notation indicates the map . This may seem a little confusing at this point, since the group is acting on the scene, but is being canonized by acting on the image. This will be clarified in Sect. 3.4.1. The first “transversality” condition corresponds to the Jacobian of with respect to being non-singular:
In words, a co-variant detector is a function that determines an isolated group element in such a way that, if we transform the image, the group elements is transformed in the same manner. Examples of co-variant detectors will follow shortly.
We say that the image is -canonizable (is canonizable with respect to the group ), and is the canonical element, if there exists a covariant detector such that .
Note that, depending on the functional , the canonical element may be defined only locally, i.e. the functional may only depend on , that is a restriction of the image to a subset of its domain . In the latter case we say that is locally canonizable, or, with an abuse of nomenclature, we say that the region is canonizable. canonizable region
The transversality condition (3.7) guarantees that , the canonical element, is an isolated (Morse) critical point of the derivative of the function via the Implicit Function Theorem . So a co-variant detector is a statistic (a feature) that “extracts” a group element . With a co-variant detector we can easily construct an invariant descriptor, or local invariant feature, by considering the data itself in the reference frame determined by the detector: local invariant feature
For a given co-variant detector that fixes a canonical element via we call the statistic
Note that the descriptor is invariant with respect to the same group that is canonized by the detector. Obviously it is not invariant to other nuisances, including groups other than the one chosen to design the detector.
A trivial example of canonical detector and its corresponding descriptor can be designed for the translation group. Consider for instance the detector that finds the brightest pixel in the image. Relative to this point, that is, if we assign that point to the coordinate , the image is translation-invariant. This is because, as the image translates, so does its brightest pixel, and in the moving frame the image does not change as we translate. Similarly, we can assign the value of the brightest pixel to , the value of the darkest pixel to , linearly interpolate pixel values in between, and we have an affine contrast-covariant detector and the associated contrast-invariant descriptor.
As far as eliminating the effects of a group, all covariant detectors are equivalent.Since canonization is possible only for groups acting on the domain of the data (i.e. , images), in the presence of more complex nuisances one has to exercise caution in that the group acting on the scene may induce a different transformation on the domain of the image, which may not even be a group. For instance, a spatial translation along a direction parallel to the image plane does not induce a translation of the image plane, unless the scene is planar and fronto-parallel. We will come back to this issue later. Where they differ is in how they behave relative to all other nuisances. Later we will give more examples of detectors that are designed to “behave well” with respect to other nuisances. In the meantime, however, we state more precisely the fact that, as far as dealing with a group nuisance, all co-variant detectors do the job.
Let be a co-variant detector. Then the corresponding canonized descriptor (3.8) is an invariant sufficient statistic.
Proof: To show that the descriptor is invariant we must show that . But To show that it is complete it suffices to show that it spans the orbit space , which is evident from the definition . The notation is slightly ambiguous at this point, but will be clarified in Sect. 3.4.1.
Note that invertible nuisances may act on the domain of the image (e.g. affine transformations due to viewpoint changes), as well as on its range (e.g. contrast transformations due to illumination changes).
To construct a simple translation-covariant detector, consider an isotropic bi-variate Gaussian function ; then for any given scale , the Laplacian-of-Gaussian (LoG) is a linear translation-covariant detector. If the group includes both location and scale, so , then the same functional can be used as a translation-scale detector. Other examples are the difference-of-Gaussians (DoG) , with typically , and the Hessian-of-Gaussian (HoG) is . Among the most popular detectors, SIFT uses the DoG, as an approximation of the Laplacian.
Harris’ corner and its variants (Stephens, Lucas-Kanade, etc.) replace the Hessian with the second-moment matrix:
As we will see in Example 6, this functional has some limitations in that it is not a linear functional, and therefore it does not commute with additive nuisances such as quantization or noise.
The notion of canonizability is related to the notion of “sketchability” defined in , although the latter is introduced without ties to a specific task, and motivated in . In the case of this manuscript, the notion of canonizability arises naturally from visual classification tasks, in the sense of providing a vehicle to design an invariant descriptor. It also relates to the notion of “saliency” defined in , although again the latter stems from resource limitations rather than from a direct tie to a visual classification task.
The assumption of differentiability in a co-variant detector can be easily lifted; in Section 4.3 we will show how to construct co-variant detectors that are not differentiable. Indeed, canonization itself is not necessary to design invariant descriptors. We have already mentioned “blurring” as a way to reduce (if not eliminate) the dependency of a statistic on a group, although that does not yield a sufficient statistic. However, even for designing complete (i.e. invariant and sufficient) features, canonization is not necessary. For instance, the geometry of the level curves – or its dual, the gradient direction – is a complete contrast-invariant which does not require a contrast-detector. Indeed, even the first condition in the definition of a co-variant detector is not necessary in order to define an invariant descriptor: Assume that the image is such that for any functional , the equation does not uniquely determine . That means that for all , and therefore all statistics are already (locally) invariant to . More in general, where the structure of the image allows a “stable” and “repeatable” detection“Stability” will be captured by the notion of Structural Stability, and “repeatability” by the notion of Proper Sampling. of a frame , this can be inverted and canonized . Where the image does not enable the detection of a frame , it means that the image itself is already invariant to . These statements will be elaborated in Section 3.5 where we introduce the notion of texture.
Intuitively, if a covariant detector is “unstable”, i.e. , , then any function is “insensitive” to , in the sense that, assuming to be smooth, we have . This means that what we cannot canonize does not matter towards the goal of designing invariant (insensitive) statistics; it is already invariant (insensitive). Of course, these statistics will not be localized. In particular, the definition of canonizability, and its requirement that be an isolated critical point, would appear to exclude edges and ridges, and in general co-dimension one critical loci that are not Morse critical points. However, this is not the case, because the definition of critical point depends on the group , which can include discrete groups (thus capturing the notion of “periodic structures,” or “regular texture”) and sub-groups of the ordinary translation group, for instance planar translation along a given direction, capturing the notion of “edge” or “ridge” in the orthogonal direction. We will come back to the notion of stability in Section 4.1.
We emphasize that detectors’ only purpose is to avoid marginalizing the invertible component of the group . However, at best such detectors can yield no improvement over marginalizing the action of , that is to use no detector at all (Section 2.4.1). Therefore, one should always marginalize or max-out the nuisances if this process is viable given resource constraints. This is a design choice that has been explored empirically. In visual category recognition, some researchers prefer to use features selected around “keypoints,” whereas others prefer to compute “dense descriptors” at each pixel, or at a regular sub-sampling of the pixel grid, and let the classifier sort out which are informative, at decision time.
Canonizability, as we have defined it, entails the computation of the Jacobian, which is a differential operation. However, images are discrete, merely a sampled version of the underlying signal (assuming that is piecewise differentiable), that is the radiance of the scene. In any case, the differentiable approximation, or the computation of the Jacobian, entails a choice of scale, depending on which any given “structure” (isolated extremum) may or may not exist: A differential operator such as the Jacobian could be invertible at a certain scale, and not invertible at a different scale at the same location. Because the “true” scale is unknown (and it could be argued that it does not exist), canonizability alone is not sufficient to determine whether a region can be meaningfully canonized. “Meaningful” in this context indicates that a structure detected in an image corresponds to some structure in the scene, and is not instead a sampling artifact (“aliasing”) due to the image formation process, for instance quantization and noise. Therefore, an additional condition must be satisfied for a region to be “meaningfully” canonized. This is the condition of Proper Sampling that we will introduce in Section 5.1.
3 Optimality of feature-based classification
The use of canonization to design invariant descriptors requires the image to support “reliable” (in the sense of Definition 3) co-variant detection. As we have discussed in Remark 4, the challenge in canonization is not when the co-variant detector is unreliable, for that implies the image is already “insensitive” to the action of . Instead, the challenge is when the covariant detector reliably detects the wrong canonical element , for instance where there are multiple repeated structures that are locally indistinguishable, as is often the case in cluttered scenes. We will come back to this issue in Section 5.2.
The good news is that, when canonization works, it simplifies visual classification by eliminating the group nuisance without any loss of performance. This was already illustrated empirically in Fig. 2.6, and is formalized by the following theorem.
If a complete -invariant descriptor can be constructed from the data , it is possible to construct a classifier based on the class-conditional distribution that attains the same minimum (Bayesian) risk as the original likelihood .
The proof follows from the definitions and Theorem 7.4 on page 269 of . The classifier based on the complete invariant descriptor is called equi-variant.
Based on this result, one would surmise that it is always desirable to canonize group nuisances, whether or not they come with a prior .This may seem confusing if one consider classification of hand-written digit modulo planar rotation. However, in the case of digits such as “6” and “9”, the class identity depends on the group, which is therefore not a nuisance and should instead be part of the description . An important caveat is that, so far in this section, we have assumed that the non-invertible nuisance is absent, i.e. , or that, more generally, the canonization procedure for is independent of , or “commutes” with , in a sense that we will make precise in Definition. 6. This is true for some nuisances, but not for others, even if they have the structure of a group, as we will see in the next section. There we will show that many group nuisances indeed cannot be canonized. These include the affine and projective group (scale, skew, deformation) as well as more complex nuisances that have to be dealt with either by marginalization (2.12), or by extremization (2.13).
4 Interaction of nuisances in canonization: what is really canonizable?
The previous section described canonization of the group nuisance in the absence of other nuisances . Unfortunately, some nuisances are clearly not invertible (occlusions, quantization, additive noise), and therefore they cannot be canonized. What is worse, even group nuisances may lose their invertibility once composed with non-invertible nuisances.
In this section, we deal with the interaction between invertible and non-invertible nuisances, so we relax the condition and describe feature detectors that “commute” with . We show that the only subgroup of that has this property is the isometric group of the plane. isometric group That is, planar rotations, translations and reflections. Other nuisances, groups or not, have to be dealt with by marginalization or extremization if one wishes to retain optimal performance. This includes the similarity group of rotations translations and scale, that is instead canonized in , similarity group and the affine group, affine group that is instead canonized in .
In order to simplify the derivation, we introduce the following notation, in part already adopted earlier in the proof of Theorem 1. The notation will be fully clarified in Sect. 3.4.1. If is the “ideal image” ideal image (without nuisances, see Remark 2), , then
where is a suitable composition operator that depends on the space where the nuisance is defined. Note that, in general, the action of the group and the other nuisances do not commute: . When this happens we say that the group commutes with the (non-group) nuisance: commutative nuisance
A group nuisance commutes with a (non-group) nuisance if
Note that commutativity does not coincide with invertibility: A nuisance can be invertible, and yet not commutative (e.g. the scaling group does not commute with quantization).
For a nuisance to be canonizable without a loss, (i.e. , eliminated via pre-processing, or via a complete invariant feature) it not only has to be a group, but it also has to commute with the other nuisances. In the following we show that the only nuisances that commute with quantization are the isometric group of the plane. While it is common, following the literature on scale selection, to canonize it, scale is not canonizable without a loss, so the selection of a single representative scale is not advisable.Even rotations are technically not invertible, because of the rectangular shape of the pixels; however, this is a second-order effect that can be neglected for practical purposes. Instead, a description of a region of an image at all scales should be considered, since scale, in a quantized domain, is a semi-group, rather than a group.
Note that, per Theorem 2, only for canonizable nuisances can we design an equi-variant classifier via a co-variant detector and invariant descriptor. All other nuisances should be handled via marginalization or extremization in order to retain optimality (minimum risk), or via a template if one is willing to sacrifice optimality in favor of speed at decision time.
The only nuisance that commutes with quantization is the isometric group of the plane, that is the group of rotations, translations and reflections.
Proof: We want to characterize the group such that where is quantization. For a quantization scale , we have the measured intensity (irradiance) at a pixel
where is a ball of radius centered at , is a characteristic function that is written more generally as a kernel , for instance the Gaussian kernel , allowing the possibility of more general quantization or sampling schemes, including soft binning based on a partition of unity of rather than simple functions . Now, we have
whereas, with a change of variable , we have
where is the determinant of the Jacobian of the group computed at , so that the change of measure is . From this it can be seen that the group nuisance commutes with quantization if and only if
That is, the quantization kernel has to be -invariant, , and the group has to be an isometry. The only isometry of the plane is the set of planar rotations and translations (the Special Euclidean group ) and reflections. The set of isometries of the plane is often indicated by .
The affine group does not commute with quantization, and in particular the scaling and skew sub-groups. As immediate consequence, neither do the more general projective group and the group of general diffeomorphisms of the plane. Therefore, scale should not be (globally) canonized and the scaling sub-group should instead be sampled. We will revisit this issue in Section 5.2 where we introduce the selection tree.
So, although suggests that invariant sufficient statistics can be devised for general viewpoint changes, this is only theoretically valid in the limit when there is no quantization and the data is available at infinite resolution. In the presence of quantization, canonization of anything more than the isometric group is not advisable. Because the composition of scale and quantization is a semi-group, the entire semi-orbit – or a discretization of it – should be retained. This corresponds to a sampling of scales, rather than a scale selection procedure.
It should be noted that the sampling of the scale group could be performed uniformly, by selecting a number of equally spaced scales, or adaptively, depending on the signal. For instance, SIFT’s scale “selection” procedure , based on Lindeberg’s work , should be interpreted as an adaptive scale sampling, rather than a selection (canonization), since scale is not canonizable. Correctly, SIFT allows the selection of multiple scales at the same location, which are signal-dependent samples of scale at that location.
The additive residual does not pose a significant problem in the context of quantization since it is assumed to be spatially stationary and white/zero-mean, so quantization actually reduces the noise level:
Instead, the other important nuisance is occlusion.
Planar rotations do not generate occlusions, so canonization of rotation is, at least to first approximation, unaffected by occlusion. Translation, however, is. In particular, if planar translations are due to parallax, parallax consisting of a translation of the optical center in front of a scene that is not flat and fronto-parallel, fronto-parallel there will be occlusions unless the scene is concave. Therefore, translation cannot be globally canonized either. This means that one should consider the set of all possible translations and defer the treatment of the nuisance to training or testing. This is indeed an approach that has recently taken hold in the recognition literature .
In either case, the procedure provides multiple similarity frames, one per each canonical translation , and at that translation for each sample scale , and a canonized rotation :
where we have indicated with a canonized contrast transformation, although contrast can equivalently be eliminated by considering the level lines or the gradient direction as described in Section 6.1.
The image, or a contrast-invariant, relative to the reference frame identified by is then, by construction, invariant modulo a selection process, in the sense that the corresponding frame may or may not be present in another datum (e.g. a test image) depending on whether it is co-visible. Thus, we have a collection of local invariant featuresIf contrast invariance is desired, the image can be replaced by the gradient direction . of the form local invariant features
In this sense, we say that translation is locally canonizable: The description of an image around each at each scale can be made invariant to translation, unless the region of size around intersects the occlusion domain , which is a binary choice that can only be made at decision time, not by pre-processing test images independently.
This is particularly natural when translation is canonized using a partition of the image into -constant statistics (“segments”), such as normalized intensity, color spectral ratios, or normalized gradient direction histograms. In fact, each region (a node in the adjacency graph) or each junction (a face in the adjacency graph) can be used to canonize translation, and the image can be described by the statistics of adjacent neighbors, as we illustrate in Section 4.3.
So, although translation is not globally canonizable, we will refer to its treatment as local canonization modulo a selection process to detect whether the region around the canonical representative is subject to occlusion. What we have in the end, for each image , is a set of multiple descriptors (or templates), one per each canonical translation, and for each translation multiple scales, canonized with respect to rotation and contrast, but still dependent on deformations, complex illumination and occlusions. One can also think of local canonization as a form of adaptive sampling, where regions that are not covariant are excluded. The same reasoning can also be applied to scale, where one can think of (multiple) scale selection as adaptive sampling of scale.
In Section 4 we will show how to construct local co-variant detectors, and in Section 6 how to exploit this process to construct local invariant descriptors.
Canonization is just a way to factor out simple nuisances. Because of occlusions, this canonization process reduces to feature selection (in each individual image) and combinatorial matching. This process represents an approximation of the “correct” marginalization or max-out procedure described in Section 2.3. Therefore, if computational resources allow, the best course of action is to max-out or marginalize the nuisance, i.e. to avoid the canonization process altogether. This choice is usually dictated by the application constraints, and should be made with knowledge of the tradeoffs involved: Canonization reduces the complexity of the classifier, but at a cost in discriminative power. Marginalization is the best option if one has a prior available. Otherwise, max-out is the best option if the classifier can be computed in time useful for the task at hand.
4.1 Clarifying the formal notation I∘g𝐼𝑔I\circ g
So far we have used the notation to indicate that, if , then . This may seem inconsistent, as the scene and the image live in different spaces, and therefore acting on is not the same as acting on . We are now ready to explain this inconsistency.
For a nuisance to be eliminated in pre-processing without a loss, it has to be a group, as well as commute with non-group nuisances. After the discussion in the previous sections, this can be expressed as for all . Therefore, if we divide the group nuisance into an “invertible” component and a “non-invertible” component , so that , we then have that
But because is not invertible, and therefore it cannot be eliminated in pre-processing without a loss, its group structure is of no use, and we might as well lump with the non-invertible nuisance . Therefore, from this point on, we can assume as a formal model of image formation the following: , and for simplicity we can omit the identity . Therefore, we can represent this equivalently a or . Now it should be clear that the (invertible) group can act on the image , so the notation is justified.
For instance, in the Lambert-Ambient model, , contrast normalization is commutative: A contrast transformation applied to the albedo induces a contrast transformation on the image, and therefore it can be neutralized (“inverted”) by performing co-variant detection on the image. So, if , then , where , is invariant to contrast. Similarly, a planar rotation applied to the scene, , where
induces a rotation on the image plane, where
so . A choice of orientation on the image plane, corresponding to a canonical rotation can then be used to canonize . Calling
we have that is invariant to a planar rotation . The story is considerably different for translation, and for general rigid motions, including out-of-plane rotation.
A translation along the optical axis, induces a transformation on the image plane that depends on the shape of the scene . If the scene is planar and fronto-parallel, translation along the optical axis induces a re-scaling of the image plane, also a group: . However, if the scene is not planar and fronto-parallel, forward translation can generate very complex deformations of the image domain, including (self-) occlusions. Similarly, for translation along a direction parallel to the optical axis, , only if the scene is planar and fronto-parallel does this result in a planar translation, so that .
It should be mentioned that different data modalities yield different commutativity properties, so it is possible that for certain data types the entire group nuisances may be commutative. For instance, cast shadows are non-invertible nuisances in grayscale images. However, if one has multiple spectral bands available, then several contrast-invariant features, such as spectral ratios, can be employed to eliminate the cast shadows.
4.2 Local canonization of general rigid motion
As we have discussed, parallax motion, including translation and out-of-plane rotation, does not commute with rotation, therefore one can at best locally canonize it. If one wishes to eliminate the effects of an arbitrary rigid motion, the entire group of diffeomorphisms has to be canonized; as shown in , this comes at a loss of discriminative power, since scenes of different shape are lumped onto the same equivalence class. But since occlusions force locality, one can also approximate general diffeomorphisms locally, and therefore only canonize sub-groups of planar diffeomorphisms. There is then a tradeoff between the sub-group being canonized and the size of the domain where the canonization is valid. Given an arbitrary margin, there will be a domain where the deformation is approximated by a translation, a larger domain where it is approximated by an isometry, a larger domain yet where it is a similarity, an affine transformation, and a projective transformation.
To see that, consider a general rigid motion in space . That induces a deformation of the image domain that can be described, in the co-visible regions, by equation (2.9). In more explicit form, if we represent shape as the graph of a function in one of the images, say at time , so that , with , then under the assumptions of the Lambert-Ambient model, where
in the co-visible region . Here we have used Matlab notation, where means the first two rows of .
Of course, the size of the region where the approximation is valid cannot be determined a-priori, and should instead be estimated as part of the correspondence hypothesis testing process . However, it is common practice to select the size of the regions adaptively as a function of the scale of the translation-covariant detector. This will be further elaborated in Chapter 5.
In the next section we establish the relation between local canonization and texture.
5 Textures
This section establishes the link between the notion of canonization, described in the previous section, and the design of invariant features, tackled in the next section.
A “texture” is a region of an image that exhibits some kind of spatial regularity. Figure 3.2 shows some examples of what are often called regular textures. They share the spatial regularity of some elementary structure, or “texture element”, or “texton” . The images in Figure 3.3, on the other hand, do not exhibit regular repetition of any such structure. Instead, they are characterized by the fact that some ensemble property of the image is spatially homogeneous, i.e. , some statistic is translation-invariant. Such ensemble properties are pooled in a region whose minimal size plays the role of the elementary texture element. Translation invariance of statistics is captured by the notion of stationarity . For instance, a wide-sense stationary process has translation-invariant mean and correlation function. A strict-sense stationary process has translation-invariant statistics of all orders.
The concept of stationarity can be generalized from simple translation invariance to invariance relative to some group: In Figure 3.5 (top) the images do not have homogeneous statistics; however, in most cases one can apply an invertible transformation to the images that yields spatially homogeneous statistics.
The following characterization of texture is adapted from , where the basic definitions of stationarity, ergodicity, and Markov sufficient statistics are described in some detail. The important issue for us is that, if a process is stationary and ergodic, a statistic can be predicted from a realization of the image in some region . Once established that a process is stationary, hence spatially predictable, we can inquire on the existence of a statistic that is sufficient to perform the prediction. This is captured by the concept of Markovianity:
Equation (3.23) establishes as a Markov sufficient statistic. In general, there will be many regions that satisfy this condition; the one with the smallest area , determines a minimal sufficient statistic and the statistic defined on it is the elementary texture element. From now on, we will refer to as the minimal Markov sufficient statistic.
We can therefore seek for that satisfies the above condition. Without a complexity constraint, there are many regions that satisfy the above condition. To find , we therefore seek for the smallest one, by solving
Note that this is a consequence of the Markovian assumption and the Markov sufficient statistic satisfies the Information Bottleneck principle with . As a special case, we can choose to belong to a parametric class of functions, for instance square neighborhoods of , excluding itself, of a certain size , , so the optimization above is only with respect to the positive scalar . The tradeoff will naturally settle for . Therefore, we can simultaneously infer both and by minimizing the sample version of (3.25) with a complexity cost on :
Note that both and are necessary for extrapolation: defines the Markov neighborhood used for comparing samples, and defines the region where such samples are sought to approximate the probability distribution .
Eq. (3.26) provides means to infer both the Markov sufficient statistic as well as the scale of a texture, assuming that the stationarity and ergodicity assumptions are satisfied. Testing for stationarity (ergodicity must be assumed and cannot be validated) amounts to inferring , a texture segmentation problem. Estimating the group element amounts to a canonization, or alignment process .
Given , compression is achieved by inferring the (approximate) minimal sufficient statistic and the stationarity scale by solving (3.26). Then , for any with is stored.
Given a compressed representation , we can in principle synthesize novel instances of the texture by sampling from within . In a non-parametric setting this is done by sampling directly neighborhoods within . To extrapolate the texture from a given sample compatibility conditions have to be ensured at the boundaries of .
where the entropy is normalized by the length of the boundary (entropy rate). Since we do not know the distribution outside , the above is approximated by
In the continuum, the problem above can be solved using variational optimization as in . In the discrete, the reader can refer to for a description of compression, synthesis, segmentation and rectification algorithms.
5.2 Textures and Structures
In this section we establish the relation between textures, defined in the previous section, and structures, defined by co-variant detectors. Consider a point and its neighborhood. If it is canonizable at a scale , there is a co-variant detector with support (a statistic) that has an isolated extremum. This implies that the underlying process is not stationary at the scale . Therefore, it is not a texture. It also implies that any region of size is not sufficient to predict the image outside that region. This of course does not prevent a region that is canonizable at to be a texture at a scale . Within a region there may be multiple frames of size , spatially distributed in a way that is stationary/Markovian, so the region may be a texture at a scale . Vice-versa, if a region of an image is a texture with , it cannot have a unique (isolated) extremum within , lest it would not be a sample of a stationary process. Of course, it could have multiple extrema, each isolated within a region of size . The above argument is a sketch of a proof of the following:
For any given scale of observation , a region with is either a structure or a texture.
Hence one can detect textures for each scale, as the residual of the canonization process described in the earlier part of this chapter. One may have to impose boundary conditions so that the texture regions fill around structure regions seamlessly. This can be accomplished by an explicit generative model that enforces boundary conditions and matches marginal statistics in the texture regions, following , as illustrated by . However, this has to be done across all scales, unlike , since whether a region is classified as texture or structure depends critically on the scale .
The reader versed in low-level vision will notice that edges are not canonizable with respect to the groups we have discussed so far, including the translation group. This should come at no surprise, as we have anticipated in Remark 4, because of the aperture problem: aperture problem While one can fix translation along the direction normal to the edge (at a given scale), one cannot fix translation along the edge (Figure 3.7). However, if one considers the sub-group of translations normal to the edge, the corresponding region is indeed canonizable.
Since the decision of what is a structure depends on time (or, more in general, on the presence of multiple images), consequently, what is a texture is also a decision that requires multiple images. For instance, a random-dot stereogram is everywhere canonizable and properly sampled at some scale , since one can establish correspondence. It is, however, a texture at all coarser scales, where any statistic is translation invariant.
The “random-dot display” of Figure 3.4 (right) seems to provide a counter-example to Theorem 4. In fact, Julesz showed that random-dot displays can be successfully fused binocularly, which means that pixel-to-pixel correspondence can be established, which means the the image is canonizable at every pixel which, by Theorem 4, means that it is not a texture. But the random-dot display satisfies the definition of texture given in the previous section. How can this be explained?
First, there is no contradiction, since random-dot displays are indeed canonizable at the scale of the pixels . However, they are stationary at any coarser scale, hence they are textures at those scales.
More importantly, however, whether two regions of an image can be matched at a given scale depends not only on whether they are canonizable, but also whether they are properly sampled at that scale. We have anticipated the concept of proper sampling in Remark 6, and we will introduce and discuss the notion of proper sampling in Section 5.2, where we will revisit the random-dot display. There, we will see that the critical scales within which regions can be successfully matched (hence not called “textures” per Theorem 4) cannot be decided by analyzing one image alone. Instead, the “thresholds” for the transition from “matchable” to “non-matchable” require having multiple images of the same scene available.
Chapter 4 Designing feature detectors
We consider two qualitatively different measures of sensitivity. Note that we use the (improper) term “stability” because it is most commonly used in the literature, even though there is no equilibrium involved, and therefore the proper system-theoretic nomenclature would really be sensitivity.An even worse name used for sensitivity is “invariance,” that suggest that a statistic could be more or less invariant. Invariance, as it has been defined here, is a binary property of a statistic: It either depends on the nuisance, or it does not. Sensitivity, on the other hand, comes in shades, as a statistic can be more or less sensitive to a nuisance, regardless of whether the latter is a group. We will start from the most common notion of bounded-input bounded-output stability.
A -covariant detector (Definition 3) is bounded-input bounded-ouput (BIBO) stable if small perturbations in the nuisance cause small perturbations in the canonical element. More precisely, such that for any perturbation with we have .
where is the Jacobian (3.7) and is called the BIBO gain. As a consequence of the definition, is finite. The BIBO gain can be interpreted as the sensitivity of a detector with respect to a nuisance. Most existing feature detector approaches are BIBO stable with respect to simple nuisances. Indeed, we have the following
Any covariant detector is BIBO-stable with respect to noise and quantization.
Proof: Noise and quantization are additive, so we have , and the gain is just the inverse of the Jacobian determinant, . Per the definition of co-variant detector, the Jacobian determinant is non-zero, so the gain is finite.
BIBO stability is reassuring, and it would seem that a near-zero gain is desirable, because it is “maximally (BIBO)-stable.” However, simple inspection of (4.1) shows that is not possible without knowledge of the “true signal.” In particular, this is the case for quantization, when the operator must include spatial averaging with respect to a shift-invariance kernel (low-pass, or anti-aliasing, filter). However, a non-zero BIBO gain is irrelevant for recognition, because it corresponds to an additive perturbation of the domain deformation (domain diffeomorphisms are a vector space), which is a nuisance to begin with (corresponding to changes of viewpoint ). On the other hand, structural instabilities are the plague of feature detectors. When the Jacobian is singular, , we have a degenerate critical point, a catastrophic scenario whereby a feature detector returns the wrong canonical frame. structural stability margin
A -covariant detector is Structurally Stable if small perturbations preserve the rank of the Jacobian matrix:
In other words, a detector is structurally stable if small perturbations do not cause singularities in canonization. We define the maximum norm of the nuisance that does not cause a catastrophic change in the detection mechanism the structural stability margin. This can serve as a score to rank features.
We call the largest that satisfies equation (4.2) the structural stability margin:
Consider the set of images, approximated by a sum of Gaussians as described in Section B.2.1. The image is then represented by the centers of the Gaussians, , their variance and the amplitudes , so that . Consider a detection mechanism that finds the extrema of the image convolved with a Gaussian centered at , with standard deviation : . Among all extrema, consider the two that are closest. Without loss of generality, modulo a re-ordering of the indices, let and be the “true” extrema of the original image. In general and . Let the distance between and be , and the distance between the detected extrema be . Translation nuisances along the image plane do not alter the structural properties of the detector ( does not change). However, translation nuisance orthogonal to the image plane do. These can be represented by the scaling group , and in general is a function of that starts at when and becomes when , i.e. when the two extrema merge in the scale-space. In this case, is the structural stability margin. It can be computed analytically for simple cases of Gaussian sums, or it can be visualized as customary in the scale-space literature. It is the maximum perturbation that can be applied to a nuisance that does not produce bifurcations in the detection mechanism (Figure 4.1). Note that one could also compute the structural stability margin using Morse’s Lemma, or the statistics of the detector (e.g. the second-moment matrix). Finally, the literature on Persistent Topology also provides methods to quantify the life-span of structures, which can be used as a proxy of the structural stability margin. Indeed, the notion of structural stability proposed above is a special case of persistent topology.
A sound feature detector is one that identifies Morse critical points in that are as far as possible from singularities. Structural instabilities correspond to aliasing errors, or improper sampling proper sampling (Section 5.1), where spurious extrema in the detector arise that do not correspond to extrema in the underlying signal. Proper sampling depends on the detector functional , that in the presence of quantization depends on the scale (the area of the support of the quantization kernel). Thus the ideal detector is one that chooses that is as far as possible from singularities in the locus . The selection of the best canonical frames according to this principle is described in Section 5.2.
Note that a canonical frame is often called a “feature point” or “keypoint” (or “corner”), an inappropriate nomenclature unless is restricted to the translation group. Note also that one should not confuse a (canonical reference) frame from a (video) frame, which is an image that is part of a sequence obtained sequentially in time. Which “frame” we are referring to should be clear from the context.
Structural instabilities would be fatal if one insisted on uniqueness of the canonical element. However, as we have pointed out, occlusions prevent uniqueness in the first place; instead, we will have to select multiple canonical elements, each of which will have to be validated. Thus, in a sense, canonization is just a way of sampling the similarity group in a manner that is adapted to the signal, as opposed to being generic.
2 Maximum stability and linear detectors
In this section, as a way of example, we introduce detectors designed to be maximally BIBO stable. In other words, we look for classes of functionals that yield maximally isolated critical points. This seems to be an intuitive appealing criterion to follow. However, we will see in Section 5.1 that this does not guarantee structural stability. Nevertheless, we describe this approach because it is one of the most common in the literature, and it is better than just testing for the transversality condition (3.7), which is fragile in the sense that, in the presence of noise, it will almost always be satisfied. In Section 5.1 we will introduce an approach to feature detection that is better suited to the notion of structural stability. Therefore, the reader can skip this section unless he or she is interested in understanding the relation between the approach proposed there and the ones used in the current literature.
To design a maximally BIBO-stable detector, we look for functionals that yield critical points where the Jacobian determinant is not just non-zero, but it is largest. Following the most common approaches in the literature, we try to capture this notion using differential operators.An alternative approach not requiring differentiability is presented in Section 4.3. In this case, we look for points that are at the same time zeros of , and also critical points of . Now, in general, for a given class , there is no guarantee that the first set (zeros of ) intersects the second (zeros of ). However, we can look for classes of functions where this is the case, for all possible images . These will be functionals that satisfy the following partial differential equation (PDE):
Note that designing feature detectors by finding extrema of functionals requires continuity, which is something digital images do not possess. However, instead of finding extrema of the (discontinuous) image one can find extrema of operators, exploiting a duality as customary especially for translation-invariance. Note that the “shift-plus-average” in corresponds to template blurring, a lossy process that is not equivalent to proper marginalization or extremization.
Written in terms of , the PDE above becomes an integro-partial differential equation (I-PDE)
a condition that should be satisfied for all . Note that the condition is only required at the zero-level set, so technically speaking a solution of the entire (4.6) is not necessary. We can approximate a generic function with a linear combination of (basis) vectors , , where are, for instance, a complete orthonormal basis, then the condition above has to be satisfied for all functions . Of the many choices of basis, we favor one that follows a result of Wiener , that states that any positive distribution can be approximated arbitrarily well with a positive combination of Gaussian kernels. So, are Gaussian kernels centered at with standard deviation . Therefore, the condition above becomes
All the gradient operators can thus be transferred to the Gaussian kernel by linearity, and derivatives of Gaussian are products of Gaussians with Hermite polynomials, that form a complete orthonormal family in . Using Jacobi’s formula for the gradient of the determinant of a function with respect to its elements, we get
where denotes the Hessian matrix and is the adjugate matrix of co-factors (each element is the determinant of the minor obtained by removing row and column ). This is another way of looking at (4.4) and (4.6), but now as an ordinary (non-linear) functional equation in the unknown .
The equation (4.4) is related to Monge-Ampere’s equation in optimal transport; an approximation of the determinant of the Hessian has been used for a Gaussian Kernel in approximate form (using Haar wavelet bases and the Integral Image) in the SURF detector . monge-ampere equation
The discussion above legitimizes the use of Hessian-of-Gaussian operators for feature detection, for instance . The Laplacian-of-Gaussian operator, used in the popular SIFT , can also be partially justified on the grounds of first-order approximation of the Hessian, as customary in Newton methods. The other popularly used detector, Harris’ corner detector, however, is not explained by the derivation above. In fact, note that Harris’ operator
is not a linear functional of the image. It is still possible, however, to define the canonizing operator
and verify whether it yields isolated critical points. This is laborious and not relevant in the context of our discussion. We only mention that, because is non-linear, it does not commute with quantization, and therefore it does not meet the conditions of a proper co-variant detector (it is not commutative). Instead, below we suggest a different procedure to detect corners (or, more in general, junctions) that also provides a canonization procedure.
3 Non-linear detectors and the segmentation tree
Linear functionals are not the only feature detectors. Indeed, Theorem 4 establishes the link between feature detection and (generalized) texture segmentation. Therefore, rather than testing for canonizability (as done customarily in feature detection) one can test for stationarity (as done customarily in segmentation) and then construct features from the segmentation tree. The caveat is that, because of the interplay of the scale group with quantization, and of the translation group with occlusion, no single segmentation can be used as a viable canonization procedure, and instead the entire segmentation tree must be considered.
The starting point for this approach to canonization is a different approximation model of the image. Rather than a linear combination of globally-defined basis vectors such as Gaussians or sinusoids, we use simple functions. These are constant functions on a compact domain, whose universal approximation properties in several measures are guaranteed by Weierstrass’ theorem . In particular, let be a given “scale.” Then, given an image, we can find a partition of the domain and constant values such that a combination of simple functions approximates the original image (or any statistic computed on it) to within in each region (all filter channels can then be combined into a vector description of a region). Specifically, for a given and , we assume there is and constants and a partition of the domain such that
where is Kronecker’s Delta. Then, if we define the simple functions as characteristic functions of
This is true for scalar-valued images, but a similar construction can be followed to partition the domain into regions (often called superpixels), superpixels based on -constancy of any other statistic, such as color or any other higher-dimensional feature . In any case, a superpixelization algorithm can be thought of as a quantizer, quantizer that is an operator that takes an image and a parameter and returns a family of domain partitions with
where is the area of . We can now use this functional to determine a co-variant detector . For the case of translation, , we define (multiple) canonical elements to be the centroids of the regions , . Making the dependency on the image explicit, we have
to which there corresponds the canonizing functional
It can be easily verified that this functional is co-variant. For the case of translation (fixing ), , we have that, for that solves , and for any
where we have used the fact that the group is isometric, so .
One may also believe that this functional yields isolated extrema, based on the fact that
However, this result, as well as (4.17), is misleading because it assumes that the superpixelization is independent of (small variations in) . More precisely, in order for translation to be canonizable, the canonization process has to commute with quantization. If we assume that the underlying “ideal image” is continuous, then the “discrete” (quantized) image defined on the lattice , is related to it via the mean-value theorem, that guarantees the existence, for each , of a translation such that
where denotes the quantization nuisance. For the canonization process to be viable we must have
where denotes the area of the set-symmetric difference of the two sets and .
Note that, in general, the operator is not continuous, since it depends on . When is fixed, it is possible to design a procedure that implements an operator that is guaranteed to be stable even if the image is not continuous (but piece-wise differentiable). For instance, in a variational multi-phase region-based segmentation approach, one has an energy functional that is continuous and minimized with respect to the (infinite-dimensional) partition , so in this case we have that is defined implicitly by the first-order optimality conditions (Euler-Lagrange) , yielding a partial differential equation .
where we have assumed that is constant within each quantization region . Now, if we approximate the piecewise constant function in each into a piecewise constant function in the partition , for a given , we have
where we have now assumed that is constant within each , and we have called that constant . So, we have that for a partitioning to be BIBO Stable, we must have
which is guaranteed so long as the image is smooth within each region (but it can be discontinuous across the boundary ). Indeed, any reasonable segmentation procedure would attempt, for any given (fixed) , to place the discontinuities of the (true underlying) image at the boundaries , therefore guaranteeing stability of the boundaries with respect to small perturbations of the image per the argument above. In particular, for , there are algorithms that guarantee a globally optimal solution that is, by construction, the most stable with respect to small perturbations of the image. These results are summarized into the following statement.
A quantization/superpixelization operator, acting on a piecewise smooth underlying field and subject to additive noise, is BIBO stable at a fixed scale for a fixed tolerance (or complexity level ) if and only if it places the boundary of the quantized regions/superpixels at the discontinuities of the underlying field.
However, our concern is not just stability with respect to the partition for a fixed , but also stability with respect to singular perturbations that change singular perturbations the cardinality of the partition (a phenomenon linked to scale since ). So, the superpixelization procedure should be designed to be stable with respect to , which is not a test we can write in terms of differential operations on the image. However, one can construct a greedy method that is designed to be stable with respect to both regular (bounded) and singular perturbations.
Start at level with each pixel representing as a region, with , the number of pixels in the image.
Construct a tree by creating a node representing the merging of the two regions that have the smallest average gradient along their shared boundary: for each , obtain a new merged region where
Continue until the gradient between regions being merged fails the test (4.1), that is
At the end of the procedure, we have regions.
These regions are, by construction, BIBO stable for any given value of . Now to obtain a partition that is also stable with respect to singular perturbations, we have to choose regions that are unaffected by changes in . To this end:
Consider each pixel , and follow its path in the tree, as it is merged with other regions, together with the cost of each merging. Note that the cost is zero except when a merging occurs; call the mergings . If at a certain we have that , then the cost is given by (4.27).
Let be the instances when the region is merged with one of its neighbors, and the corresponding costs. Furthermore, let be the “iteration gaps” between two merges involving the region .
For each pixel and each set of indices sort the gaps in decreasing order of their minimum gap
The level with the largest minimum gap corresponds to the region containing the pixel that is least affected by singular perturbations. Indeed, for all , any singular perturbation is a change in the value of that does not change the region .
If we follow this procedure for every pixel , sorting their paths in decreasing order of gaps, until a minimum gap is reached, then we have that each initial region is now included in a number of (overlapping) regions that are not only BIBO stable, but also stable with respect to singular perturbations. This follows by construction and is summarized in the following statement.
Let , with be each pixel in an image. Then let be (-multiple) indices where is merged with neighboring regions,
then the regions are BIBO stable and stable with respect to singular perturbations.
Clearly many of these regions will be overlapping, and many indeed identical, so some heuristics can be devised to reduce the number of regions that, as it stands, can be more than the number of pixels in the image. A principle to guide such agglomeration is the so-called Agglomerative Information Bottleneck .
This procedure relates to MSER , where however regions are created from the watershed, and are selected based on the variation of their boundary relative to their area as the watershed progresses. It also relates to other attempts to define “stable segmentations”, for instance . However, in these cases stability is characterized empirically, and the algorithm is not guaranteed to be stable against a formal definition. Also, we are not necessarily interested in a partition of the domain, so long as a sufficient number of regions are present to enable local canonization.
So we have shown that canonizing translation via the centroid of superpixels is automatically viable, per (4.17) and (4.18), but only so long as the superpixelization is stable with respect to additive noise, for instance generated by quantization mechanisms.
Let be a partition of the domain into superpixels. Then the functional (4.16) is a (local, translation) co-variant detector so long as it is BIBO stable.
That (4.16) is covariant follows from (4.17), provided that (4.1) is satisfied.
By the same token, one could canonize rotation by considering the principal axis of the sample covariance approximation of the regions . Although advocates canonizing general viewpoint changes by considering only the adjacency graph of the regions , as we have discussed in Section 3, one should canonize no further.
An alternative (and dual) procedure for canonization is to use not the centroid of the superpixels, but their junctions, which are the points of intersection of the boundaries of adjacent superpixels. This provides a “corner detection mechanism” that is consistent with the theory, and can be used as an alternative to Harris’ corner detector discussed in the previous section. It should be noted that critical point filters have been proposed for the detection of junctions at multiple scales.
Detection and canonization are not important per se, and can be forgone if one is willing to marginalize nuisances at decision time. Simple (conservative) detection can be thought of as a way not to select canonizable regions, but to quickly reject obviously non-canonizable ones. In this, the approach can be related to Boosting . Where detection becomes important is when no marginalization can be performed, for instance in two adjacent frames in video, where one knows that the underlying scene is the same. As it turn out, this impoverished recognition problem, often called tracking, plays an important role in recognition, to the point where we devote a chapter to it, the next.
Before moving on, however, we would like to re-iterate the fact that the best mechanisms to eliminate nuisances is via marginalization or max-out. When decision-time constraints dictate that this is not feasible, canonization provides a useful way to reduce complexity, ideally keeping the expected risk in the overall decision problem unchanged (Section 2.4.1).
Chapter 5 Correspondence
In this chapter we explore the critical role that multiple images play in visual decisions. “Correspondence” refers to a particular case of visual decision problem, whereby two adjacent images are assumed to portray the same scene (owing to the physical constraints of causality and inertia, the scene is not likely to change abruptly from one image to the next), and this “bit” is used to prime the construction of models of the scene for recognition. Whether correspondence can be established depends on a variety of conditions that we describe next.
In the next section we will introduce the notion of Proper Sampling, that has been anticipated in Chapter 3, and is illustrated in Figure 5.1: A signal can be canonizable, but not properly sampled (i.e. , canonizability arises from aliasing effects, such as the block-structure due to quantization). Or, it can be properly sampled, but not canonizable (e.g. a constant region of the image), it can be not canonizable, and not properly sampled (e.g. a spatially and temporally independent realization of Gaussian “noise”), and finally it can be properly sampled and canonizable, for instance a “blob” or the fine-scale structure in a random-dot stereogram (Figure 5.2), not to be confused with “noise.”
In Chapter 3 we have seen that an invariant descriptor can be constructed via canonization, but canonizability is a necessary, not sufficient, condition for meaningful correspondence. In order to be meaningful, a structure on the image needs to correspond to a structure in the scene, as we discussed in Remark 6. Unfortunately, this condition cannot be tested on one image alone. It can either be determined at decision time, by marginalization or extremization, or it can be determined – under the Lambertian assumption – by looking at different images of the same scene, as we describe next.
Feature detection is a form of sampling, but one that is rather different from the classical sampling theory of Nyquist and Shannon. In traditional signal processing, proper sampling refers to regular sampling at twice the Nyquist rate, since a band-limited signal can be reconstructed exactly from the samples under these conditions. This assumes that the signal is band-limited, band-limited which is as much an idealization as the Lambert-Ambient static model (strictly band-limited signals do not exist, as they would have to have infinite spatial support).
But we are not interested in using the data to reconstruct a replica of the “original signal.” Instead, we are interested in using the data to solve a decision or control task as if we had the “original signal” at hand. But what is the “original signal” in our context? It is the image before any quantization phenomena occur. For a single image, since we cannot detect occlusions (Section 8.1), quantization represents the main non-invertible nuisance (neglecting complex illumination effects). Similarly, as we have seen in Theorem 3, the translation-scale group is the main invertible nuisance (since more complex groups are not invertible once composed with quantization). Therefore, following (2.8) in Section 2.2, we have that if the image is , then the “ideal image” is
Therefore, in the context of visual decisions, we can define proper sampling as a discretization that yields a response of co-variant detector functionals having the same number, type and connectivity of critical points that the “ideal image” would produce.
A signal is properly sampled at a scale if a co-variant detector operating on the image yields the same critical points as if it operated on the radiance of the scene. In other words, if is a co-variant detector for the location-scale group , and , then , and corresponding extrema are of the same type.
In other words, an image is properly sampled if it is possible to reconstruct, from the samples, not the “ideal image” (the radiance of the scene), but one that is topologically equivalent to to it, in the sense of yielding the same extrema via a co-variant detector operator. The attributed Reeb tree (ART) is a topological construction that can be assembled from the image at any given scale. It is a tree with nodes at every isolated extremum (maxima, minima, saddles), with edges connecting extrema that are “adjacent” in the sense of the Morse-Smale complex. The value of the image at the extrema is not relevant, but the ordering is, and the position of these extrema is not relevant, but the connectivity is. The ART was introduced in as a maximal contrast-viewpoint invariant away from occlusions, and is described in more detail in Section A.2. It can be shown that the outcome of any feature detector operating at a scale can be written in terms of the : , which leads to the following claim.
A signal is properly sampled at if and only if .
Thus, any of a number of efficient techniques for critical point detection can be used to compute the and test for proper sampling. Note that, in general, any feature detection mechanism alters the position of the extrema relative to the original signal, as illustrated in Example 5. This is not an issue in the context of visual decisions, because extrema move as a result of viewpoint changes, and their motion would therefore be discarded as a nuisance anyway.
The problem with the definition of proper sampling is that it requires knowledge of the “ideal image” , which is in general not available (indeed, it may be argued that it does not exist). Unlike classical sampling theory,In reality, even in classical sampling theory there is no critical sampling, since no real-signal is strictly band-limited, so in strict terms Nyquist’s frequency does not exist. there is no “critical frequency” beyond which one is guaranteed success in canonization, because of the scaling/quantization phenomenon. Therefore, to test for proper sampling on the image , rather than comparing it to the “ideal image”(which is a function of the unknown radiance distribution of the scene), we compare it to the next image , which is equivalent to it under the Lambertian assumption in the co-visible region , as done in Section 2.2. Therefore, the notion of proper sampling (now in space and time) relates to the notion of correspondence, co-detection, or “trackability” as we explain below.
We say that a signal can be properly sampled at scale at time if there exists a scale such that .
In other words, a signal is properly sampled in space and time if the feature detection mechanism is topologically consistent in adjacent times. Alternatively, we can impose that and therefore require topological consistency at the same scale. Sometimes we refer to proper sampling of corresponding regions in two images as being co-canonizable.
Note that in the complete absence of motion, proper sampling cannot be ascertained. However, complete absence of motion is only real when one has one image, as a continuous capture device will always have some changes, for instance due to noise, making two adjacent images different, and therefore the notion of topological consistency over time meaningful, since extrema due to noise will not be consistent. Note that the position of extrema will in general change due to both the feature detection mechanism, and also the inter-frame motion. Again, what matters in the context of visual decisions is the structural integrity (stability) of the detection process, i.e. its topology, rather than the actual position (geometry). If a catastrophic event happens between time and , for instance the fact that an extremum at scale splits or merges with other extrema, then tracking cannot be performed, and instead the entire s have to be compared across all scales in a complete graph matching problem.
While establishing correspondence under these circumstances can certainly be done (witness the fact that we can recognize the top-left image in Figure 5.1 as a quantized photograph of Abraham Lincoln), this has to be done by marginalization, extremization or canonization, treating correspondence as a full-fledged recognition problem (a.k.a. wide-baseline matching) wide-baseline matching rather than exploiting knowledge that the underlying scene is the same. This is the crucial “bit” provided by temporal continuity. Motivated by this reasoning, we introduce the notion of “trackability.” trackability
A region of the image is trackable at a given scale if it is canonizable and properly sampled at that scale.
It may seem at first that any region of an image can be made trackable by considering it at a sufficiently coarse scale. Unfortunately, this is not the case.
We first note that occlusions do, in general, alter the topology of the feature detection mechanism, hence the . Therefore, they cannot be properly sampled at any scale. This is not surprising: We know that we cannot track through an occlusion, as correspondence cannot be established for regions that are visible in one image (either or ) but not the other. In the context of feature detectors/descriptors, occlusion detection reduces to a combinatorial matching process at decision time. Pixel-level occlusion detection will be discussed in Section 8.1.
Note that a signal is not properly sampled per-se. In general, only trivial signals are globally properly sampled. However, there is a scale at which a signal may be properly sampled, as we will see shortly. As an illustration, Figure 5.3 shows the same image that is not properly sampled at the pixel level (left) but it is properly sampled when seen at a significantly coarser scale (small in-set image on the left, or blurred version on the right).
Note that the notion of proper sampling relates to texture, in the sense that even if two images independently exhibit stationary statistics (and therefore they are independently classified as textures), if they are co-canonizable they are properly sampled, and therefore point-correspondence can be established (Figure 5.2). Also, we recall that we consider constant-color regions to be (trivial) textures, even though they are often referred to as “textureless.” Note that a constant-intensity region is, in general, properly sampled, but not canonizable. A stochastic texture is not canonizable (by definition) at the native scale (sensor resolution), where it is usually not properly sampled, because canonizability arises from sampling/aliasing phenomena. Note, again, that all these considerations depend on scale, as we have discussed in Section 3.5. Also note that we are not assuming that the signals we measure are properly sampled. Instead, we use the definition to test the hypothesis of proper sampling at a given scale, and therefore determine co-visibility and ascertain trackability.
Although, as we have pointed out before, two-dimensional scale-spaces do not enjoy a causality property, typically the number of extrema diminishes at coarser scales, and the extrema that persist are, usually, corresponding to some structure in the image. So, although one cannot prove that for any image there exists a scale at which it can be properly sampled, in co-visible regions, one typically finds this to be the case for most natural images. This is because, at large enough scales, extrema will coalesce, and eventually quantization phenomena become negligible.However, at coarser scales, the landscape of the response of a co-variant detector becomes flatter, and therefore the BIBO gain smaller, and feature detection less reliable.
Therefore, one can conjecture that, for most natural images, in the absence of occlusions, assuming continuity and a sufficiently slow motion relative to the temporal sampling frequency, any image region is trackable. This means that there exists a large-enough scale such that .
Thus anti-aliasing in space can lead to proper sampling in time. This is important because, typically, temporal sampling is performed at a fixed rate, and we do not want to perform temporal anti-aliasing by artificially motion-blurring the images, as this would destroy spatial structures. Note, however, that once a large enough scale is found, so correspondence is established at the scale , the motion computed at that scale can be compensated for, and therefore the (back-warped) images can now be properly sampled at a scale . This procedure can be iterated, until a minimum can be found beyond which there is no topological consistency. Note that may be smaller than the native resolution of the sensor, leading to a super-resolution phenomenon. super-resolution
This suggests a procedure for tracking, whereby one first selects structurally stable features via proper sampling. The structural stability margin determines the neighborhood in the next image where detection is to be performed. If the procedure yields precisely one detection in this neighborhood, topology is preserved, and proper spatio-temporal sampling is achieved, hence trackability. Otherwise, a topological change has occurred, and the track is broken. This procedure is performed first at the coarsest level, and then propagated at finer scales by compensating for the estimated motion, and then re-selecting at the finer scales . Note that this procedure, described in more detail in the next section, is different from traditional multi-scale feature tracking, where each feature detected at the finest scale is tracked at all coarser scales. In this framework, feature detection is initiated at each scale, in the region back-warped from coarser scales.
2 The role of tracking in recognition
The goal of tracking is to provide correspondence of (similarity or isometric) reference frames , centered at , with size and orientation . This is the outcome of feature detection based on structural stability and proper sampling. Because of temporal continuity,This temporal continuity of the class label does not prevent the data from being discontinuous as a function of time, owing for instance to occlusion phenomena. However, in general one can infer a description of the scene , and of the nuisances from these continuous data, including occlusions , as we show in Section 8.1. It this were not the case, that is if the scene and the nuisances cannot be inferred from the training data, then the dependency on nuisances cannot be learned. the class label is constant under the assumption of co-visibility and false otherwise. In this sense, time acts as a “supervisor” or a “labeling device” that provides ground-truth training data. The local frames are now effectively co-detected in adjacent images. Therefore, the notion of structural stability and “sufficient separation” of extrema depends not just on the spatial scale, but also on the temporal scale. For instance, if two -pixel blobs are separated by pixels in one image, they are not sufficiently separated for tracking under temporal sampling that yields a -pixel inter-frame displacement.
Thus the ability to track depends on proper sampling in both space and time. This suggests the approach to multi-scale tracking used in :
Construct a spatial scale-space of feature detectors, until the signal is properly sampled in time.
Estimate motion at the coarser scale, with whatever feature tracking/motion estimation/optical flow algorithm one wishes to use . This is now possible because the proper sampling condition is satisfied both in space and time.In practice, there is a trade-off, as in the limit too smooth a signal will fail the transversality condition (3.7) and will not enable establishing a proper frame .
Propagate the estimated motion in the region determined by the detector to the next scale. At the next scale, there may be only one selected region in the corresponding frame, or there may be more (or none), as there can be singular perturbations (bifurcations, births and deaths).
For each region selected at the next scale, repeat the process from 2.
Note that only the terminal branches of the selection scale-space provide an estimate of the frame , whereas the hidden branches are used only to initialize the lower branches. Nevertheless, one can report each motion estimate at the native selection scale (Figure 5.4 middle), even if they are subsumed by the terminal branches of the selection tree.
This approach is called tracking on the selection tree (TST) , because it is based on proper sampling conditions and tracking is performed at each native selection scale. Indeed, note that the “second-moment-matrix” test commonly used for tracking , even if performed at each scale, cannot be relied upon to reject features that cannot be tracked. This is because it is possible, and indeed typical, that due to singular perturbations, the region passes the second-moment test (e.g. harris’ ) at each scale, but not because the feature of interest is trackable, but because additional structures have appeared in the new scale (Figure 5.4 right). This is a form of structural aliasing phenomenon. structural aliasing
Tracking provides a time-indexed frame that can be canonized in multiple images to provide samples of the canonized statistic , where lumps all other nuisances that have not been canonized (including the group nuisances that do not commute with non-invertible nuisances). These can then be used to build a descriptor, for instance a template (2.30), or more general ones that we discuss next.
Note that the process of selection by maximizing the structural stability margin can be understood as a scale canonization process, even though in Section 3.4 we argued against canonization of scale. Note, however, that here we are not making an association of features across scales other than for the purpose of initializing tracks. In particular, consider the example of the corner in Figure 5.4: The corner only exists at the finest scale. Features detected at coarser scales serve to initialize tracking at the finest scale, but features selected at coarse scales are not associated to the corner point, they are simply different local features. Aggregating multiple TSTs can also be done, when some “side information” is available that enables to group them together. For instance, in , detachability is used as side information , exploiting, again, knowledge of occlusions .
Chapter 6 Designing feature descriptors
A feature detector provides a -covariant reference frame, relative to which the image is, by construction, -invariant. So, the simplest invariant descriptor is the image itself, expressed in the reference frame determined by the detector (3.8). For the case of Euclidean and contrast transformations, , where denotes the set of monotonic continuous transformations of the range of the image. In the case in which a sequence of images is available, correspondence of reference frames is provided by tracking , as described in Section 5.1, and again the entire time series in the normalized frame, is by construction -invariant. Of course, all the non-invertible nuisances, as well as the group nuisances that do not commute with them, are not eliminated by this procedure, and therefore they have to be dealt with at decision time via either marginalization (2.12), or extremization (2.13). Using the formal image-formation model , and the maximal -invariant , we have that
However, marginalizing or max-outing the residual effects of the nuisance – that include occlusions, quantization, noise, and all un-modeled photometric phenomena such as specularities, translucency, inter-reflections etc. – can be costly at decision time. Therefore, in Section 2.6.1, we have justified the introduction of an alternate approach that attempts to simplify the decision run-time by aggregating the training set into a template. Of course, one could do the same on the test set, which may consist of a single image , or of video. The result is what is called a feature descriptor. In this chapter we will explore alternate descriptors, more general than the best template described in Section 2.6.1, which we show how to compute in Section 6.3. We also discuss relationships to sparse coding in Section 6.5, which links to the discussion of linear detectors in Section 4.2. Recall that the “best template” in Section 2.6.1 is only the best among (static) templates. Therefore in Section 6.4 we show that one can, in general, achieve better results by not eliminating the time variable as part of the feature description process, but retaining the time variable, and instead marginalizing it or max-outing it as part of the decision process. This requires the introduction of techniques to marginalize time, which we describe in Section 7.2.
Before doing all that, however, we summarize the role of various nuisances and how they are handled before the descriptor design process commences.
This section summarizes material from previous chapters, and can therefore be skipped. In Section 2.2 we have divided the nuisance into those that have the structure of a group, , and those that are non-invertible, , including the additive component , which we refer to as “noise.” Then, in Section 3.4, we have shown that of the group nuisance, only a sub-group commutes with and . These are the group-commutative nuisances, consisting of the isometric group of the plane. Indeed, these are only locally canonizable and therefore can be eliminated at the outset via co-variant detection and invariant description (3.8), modulo a selection process corresponding to combinatorial matching at decision time, to marginalize the occlusion nuisance, as described in (3.20) in Section 3.4. In this section we elaborate on how to treat the various nuisances, thus expanding (3.20).
Canonization corresponds to the selection of a particular point (feature detection) that is chosen as (translational) reference. The image in this new reference is, by construction, invariant to planar translation, assuming that the feature detection process is structurally stable, commutes with non-invertible nuisances, and there is no occlusion. There are many mechanisms to canonize translation. Examples include the extrema of the determinant of the Hessian of the image, or of the convolution with a Laplacian of Gaussian, extrema of the determinant of the second-moment matrix. In any case, one must choose multiple translations at each sample scale . As we have discussed in Section 4, scale should be sampled, not canonized (it does not commute with quantization), and it can be either sampled regularly, or adaptively in a way that yields maximum structural stability margins, as described in Section 4.1. If the image is encoded by a “segmentation tree” (a partition of the domain into regions that are constant to within a certain tolerance ), then the centroid of each region (a node in the region adjacency graph) or the junctions of boundaries of three or more regions (faces in the adjacency graph) are also viable canonization procedures that can be designed to be structurally stable.
Scale is not canonizable in the presence of quantization. Whatever descriptor one chooses should be represented at multiple scale. This is described in Section 5.2.
Note that a variety of sampling options is possible, depending on the interplay with translational feature detection. One could first sample all available scales, and then independently canonize translation in each one. Or, one could canonize translation at the native scale of the image, and then sample the image at multiple scales at that location. Or, one can simultaneously sample scale and detect translational frames by performing maximally-structurally stable translation selection, where the maximization of the stability margin is performed relative to scale. This is accomplished in a manner similar to scale selection as prescribed by , described in . It is conceptually important to understand that multiple scales can be detected at the same location, therefore the scale selection process is more like an adaptive scale sampling as opposed to a (unique) scale canonization procedure.
Planar rotation is canonizable, and therefore it should be canonized. In the presence of measurements of gravity, a natural canonical orientation is provided by the projection of the gravity vector onto the image plane (assuming it is not aligned with the optical axis).
If we have regions available from sampling translations and scale, we can canonize each one with a co-variant detector and its corresponding invariant descriptor . Co-variant detection can be performed in a number of ways, using extrema of the gradient direction (at each location, at each scale), or the principal direction of the second moment matrix at each location and scale, or nodes and faces of the adjacency graph of -constant regions , at each location and scale. The result is an unchanged number of descriptors that are now invariant to rotation as well as (locally) translation. Alternatively, rotation can be canonized by using gravity and longitude (or latitude) as canonical references.
Contrast can be canonized independently of other nuisances by replacing the intensity at every pixel with the gradient direction:
This is conceptually straightforward, except that it assumes that the image is differentiable, which in general is not the case (one can define discrete differentiability which, however, entails a choice of scale, thus making this choice still dependent on scale). It also raises issues when , i.e. , when the image is constant in a region. As an alternative mechanism, one can canonize contrast, in a local region determined by a translational frame at a scale , by normalizing the intensity by subtracting the mean and dividing by the standard deviation of the image, or of the logarithm of the image. If we call a neighborhood of size around the canonical reference , then
where and In this latter case, the canonization procedure interacts with scale, and therefore contrast normalization should be done independently at all scales. Additional options if multiple spectral bands are available is to consider spectral ratios, spectral ratio for instance in an color space one can consider the ratio and , or the normalized color space, or in an color space one can consider the and channels, etc.
Among the nuisances that cannot be canonized, in addition to scale and occlusion that should be sampled and marginalized as in Section 3.4, we have:
Complex illumination effects other than contrast cannot be canonized, and therefore their treatment should be deferred to decision time.
Quantization is intertwined with scale and cannot be canonized. At each scale, quantization error can be lumped as additive noise. Detectors for canonizable nuisances should be designed to commute with quantization and noise. Linear detectors do so by construction.
One could treat the (non-canonizable) group of skew transformation in the same way as scale, but since there is no meaningful sampling of this space, we lump the skew with other deformations and defer their treatment to marginalization or blurring.
Domain deformations other than rotations and translations, including the affine and projective group or more general diffeomorphisms, cannot be canonized in the presence of quantization, and therefore their handling should be deferred to either training (blurring) or testing (marginalization, extremization).
Occlusions, finally, are not invertible and cannot be canonized, so they will have to be explicitly detected during the matching process (via max-out or marginalization), which in this case corresponds to a selection of a subset of the local descriptors as described in Section 3.4.
What we have in the end, for each image , is a set of multiple descriptors (or templates), one per each canonical translation and, for each translation, multiple scales, canonized with respect to rotation and contrast, but still dependent on deformations, complex illumination and occlusions:
Note that the selection of occluded regions, which is excluded from the descriptor, is not known a-priori and will have to be determined as part of the matching process. As we have discussed in Section 4.1, the selection process should be designed to be invariant with respect to group-commutative nuisances, and “robust” (in the sense of structural stability) with respect to all other nuisances. The selection and tracking process described in Section 5.1 provides one such design.
In the case of video data, , one obtains a time series of descriptors, time series
where the frames are provided by the feature detection mechanism that, in the case of video, includes tracking via proper sampling (Section 5.1). Once that is done, one should store the time series of descriptors for later marginalization, if sufficient storage and computational power is available, as we describe in Section 6.4. Otherwise, a static descriptor can be devised, as we discuss in Section 6.3. Before doing so, however, we discuss the interplay between the scene and the nuisance in the next section.
2 Disentangling nuisances from the scene
In the image-formation model described in Section 2.2, and in the more general model in Section B.1, some of the nuisances interact with the scene to form an image. If the nuisances are marginalized or max-outed, as in (2.12) or (2.13), this is not a problem. However, if we want to canonize a nuisance, in the process of making the feature invariant to the nuisance, we may end up making it also invariant to some components of the scene. In other words, by abusing canonization we may end up throwing away the baby (scene) with the bath water (nuisances).
The simplest example is the interaction of viewpoint and shape. viewpoint-shape interaction In the model (2.6), we see immediately that the viewpoint and shape interact in the motion field (2.9) via , where depends on the shape of the scene. It is shown in that the group closure of domain warpings spans the entire group of diffeomorphisms, which can therefore be canonized – if we exclude the effects of occlusion and quantization. However, necessarily the canonization process eliminates the effects of the shape in the resulting descriptor, which is the ART described in Section 5.1. This had already been pointed out in . This means that if we want to perform recognition using a strict viewpoint-invariant, then we will lump all objects that have the same radiance, modulo a diffeomorphism, into the same class. That means that, for instance, all white objects are indistinguishable using a viewpoint invariant statistic, no matter how such an invariant is constructed. Of course, as pointed out in , this does not mean that we cannot recognize different objects that have the same radiance. It just means that we cannot do it with a viewpoint invariant, and instead we have to resort to marginalization or extremization.
The same phenomenon occurs with reflectance (a property of the scene) and illumination (a nuisance). reflectance-illumination interaction This is best seen from a more general model than (2.6), for instance one of the models discussed in Section B.1. In the case of moving and possibly deforming objects, there is also an ambiguity between the deformation (a characteristic of the scene) and the viewpoint (a nuisance).
Deciding how to manage the scene-nuisance interaction is ultimately a modeling choice, that should be guided by two factors. The first is the priority in terms of speed of execution (biasing towards canonizing nuisances) vis-a-vis discriminative power (biasing towards marginalization to avoid having multiple scenes collapse into the same invariant descriptor). The second is a thorough understanding of the interaction of the various factors and the ambiguities in the image formation model. This means that one should understand, given a set of images, what is the set of all possible scenes that, under different sets of nuisances, can have generated those images. This is the set of indistinguishable scenes, that therefore cannot be discriminated from their images. This issue is very complex and delicate, and a few small steps towards a complete analysis are described in Section B.3.
In this chapter, we will set this issue aside, and agree to canonize (locally) translation, rotation and contrast, and sample scale. This means that scenes that are equivalent up to a similarity transformation are indistinguishable, as shown in , which is not a major problem, but leaving the reflectance-illumination ambiguity unresolved, other than by removing local contrast transformations that represent a coarse model of illumination changes. In the next section, we move on to describe some of the descriptors that can be constructed under these premises.
3 Template descriptors for static/rigid scenes
If we are given a sequence of images of a static scene, or a rigid object, then the only temporal variability is due to viewpoint , which is a nuisance for the purpose of recognition, and therefore should be either marginalized/max-outed or canonized. In other words, there is no “information” in the time series , and once we have the tracking sequence available, the temporal ordering is irrelevant. This is not the case when we have a deforming object, say a human, where the time series contains information about the particular action or activity, and therefore temporal ordering is relevant. We will address the latter case in Section 7.2. For now, we focus on rigid scenes, where does not change over time, or rigid objects, which are just a simply connected component of the scene (detached objects). The only role of time is to enable correspondence, as we have seen in Section 5.1.
The simplest descriptor that aggregates the temporal data is the best template descriptor introduced in Section 2.6.1. However, after we canonize the invertible-commutative nuisances, via the detected frames , we do not need to blur them, and instead we can construct the template (2.30) where averaging is only performed with respect to the nuisances , rather than (2.25), where all nuisances are averaged-out. The prior is generally not known, and neither is the class-conditional density . However, if a sequence of framesWe use as the index, instead of , to emphasize the fact that the temporal order is not important in this context. has been established in multiple images , with , then it is easy to compute the best (local) template viaAs pointed out in Section 2.6.1, this notation assumes that the descriptor functional acts linearly on the set of images ; although it is possible to compute it when it is non-linear, we make this choice to simplify the notation.
where are the component of the descriptor defined in eq. (6.1) for the -th image . A sequence of canonical frames is the outcome of a tracking procedure (Section 5.1). Note that we are tracking reference frames , not just their translational component (points) , and therefore tracking has to be performed on the selection tree (Figure 5.4). The template above , therefore, is an averaging of the gradient direction, in a region determined by , according to the nuisance distribution and the class-conditional distribution , as represented in the training data. This “best-template descriptor” (BTD) is implemented in . It is related to in that it uses gradient orientations, but instead of performing spatial averaging by coarse binning, it uses the actual (data-driven) measures and average gradient directions weighted by their standard deviation over time. The major difference is that composing the template requires local correspondence, or tracking, of regions , in the training set. Of course, it is assumed that a sufficiently exciting sample is provided, lest the sample average on the right-hand side of (6.7) does not approximate the expectation on the left-hand side. Sufficient excitation is the goal of active exploration described in Chapter 8. Note that, once a template is learned from multiple images, recognition can be performed on a single test image.
It should be re-emphasized that the best-template descriptor is only the best among templates, and only relative to a chosen family of classifiers (e.g. nearest neighbors with respect to the Euclidean norm). For non-planar scenes, the descriptor can be made viewpoint-invariant by averaging, but that comes at the cost of losing shape discrimination. If we want to recognize by shape, we can marginalize it, but that comes at a (computational) cost.
It should also be emphasized that the template above is a first-order statistic (mean) from the sample distribution of canonized frames. Different statistics, for instance the median, can also be employed , as well as multi-modal descriptions of the distribution or other dimensionality reduction schemes to reduce the complexity of the samples.
4 Time HOG and Time SIFT
The best-template descriptor in the previous section is a first-order statistic of the conditional distribution . As an alternative, instead of averaging the sample, one can compute a histogram, thus retaining all statistics. For this to be done properly, one has to consider each image to be a sample from the class-conditional distribution. A wildly simplifying assumption is to assume that every pixel is independent (obviously not a realistic assumption) so that the conditional distributions can be aggregated at each pixel. This is akin to computing, for every location in a canonized frame , the temporal histogram of gradient orientations. This statistic eliminates time and discards temporal ordering.
If instead of a sequence one had only one image available, one could generate a pseudo-training set by duplicating and translating the original image in small integer intervals. The procedure of building a temporal histogram described above then would be equivalent to computing a spatial histogram of gradient orientations. SIFT and HOG describe one particular way of binning such histograms. So, one can think of SIFT and HOG as a special case of template descriptor where the nuisance distribution is not the real one, but a simulated one.
We call the distributional aggregation, rather than the averaging, of in (6.7) the Time HOG or Time SIFT, depending on how the samples are aggregated and binned into a histogram time hog time sift .
As an alternative to temporal aggregation via a histogram, one could perform aggregation by dimensionality reduction, for instance by using principal component analysis, or a kernel version of it as done in , or using sparse coding as we describe in the next section.
Although a step up from template descriptors, Time SIFT and Time HOG still discard the temporal ordering in favor of a static descriptor. In cases where the temporal ordering is important, as in the recognition of temporal events, one should instead retain the time series and compare them as we describe in Section 7.2, which corresponds to marginalizing, or max-outing, time. This process is considerably more onerous, computationally, at decision time. Before doing so, we illustrate an alternate approach to build local descriptors based on ideas from sparse coding .
5 Sparse coding and linear nuisances
Many nuisances, whether groups or not, act linearly on the (template) representation. Take for instance the instantiation of the Lambert-Ambient model (2.6), and assume that we have canonized contrast (or, equivalently, after canonization, assume ). The diffeomorphic warping includes canonizable nuisances, group nuisances that are not canonizable, and nuisances that are not invertible, such as occlusions, quantization, and additive noise. Complex as it may be, is a linear functionalA linear functional is a map from a function space to a vector space that satisfies the linearity assumption, that is for any functions an scalars . In general, linear maps can be written as the integral of the argument against a kernel, . acting on the radiance function :
The kernel that represents it is degenerate, in the sense that it is not an ordinary function but a distribution (Dirac’s Delta)
where denotes the occluded region. The kernel an ordinary function once we introduce sampling into the model:
An alternative is to approximate with piecewise linear or even piecewise constant functions, which can be done arbitrarily well under mild assumptions as described in Section 4.3, and encode the domain partition where the function is -constant:
The function can then be written as
While the group is, in general, not piecewise constant, its variation within each is not observable, and therefore we can without loss of generality assume that . Naturally, there remains to be determined which indices correspond to regions that are visible in both the template and the target image, and which ones are partially or completely occluded.
for some finite , where we have used the vector notation and . Plugging the equation above into (6.12), we have
If we consider the joint encoding of every pixel in a region centered at the canonized locations of size corresponding to the sample scales , we have
from which one can see that the coefficients representing the “ideal image” with respect to an over-complete basis are the same as the coefficients representing the “actual” image , relative to a transformed basis , whose elements are . Note that the dependency on (the location) and (scale) is reflected in the coefficients . To obtain a description, one can estimate, for each , the coefficients
from which the representation is given by
This requires knowing the basis , which in turn requires solving the above problem for all corresponding local regions of all images in the training set. This can be done by joint alignment as in .
Obviously, the linear model does not hold in the presence of occlusions. Therefore, the representation is only local where co-visibility conditions are satisfied. Occlusions, as usual, have to be marginalized or max-outed at decision time as described in Section 3.4.
As we have argued, it is possible to estimate an invariant representation from the image by assuming that the radiance function is sparse. This led to the observation that the representation of the “true” (but unknown) radiance with respect to an over-complete basis is the same of the representation of the known image with respect to a transformed basis . Note that, in general, this representation will not be unique, and there are some issues with the coherence of the basis that are beyond the scope of this manuscript (see ). However, the projection (hallucination) of the representation onto the space of images can be used to compute the residual, so any ambiguity in is annihilated by the corresponding choice of basis vectors .
A consequence of this fact is that one can just augment the dictionary with transformed versions of the bases, thus obtaining an enlarged dictionary, and then use exactly the same algorithm for encoding and . The only difference is that one would have to organize the dictionary by “linking” bases that are transformed versions of each other, or “deformation hypercolumns”
somewhat akin to “orientation hypercolumns” in visual cortex. In practice, one would sample the group according to its prior (which is a combination of and ), yielding a set of samples , from which the enlarged basis can be constructed, with elements , and the understanding that any non-zero element of multiplying a set of bases will have a non-zero coefficient .
Unfortunately, the coefficients in this representation are not identifiable: Indeed, not only are they not unique, but they are not continuously dependent on the data, so it is possible for infinitesimally close images to have wildly different set of coefficients. This is not an issue if the goal is data transmission and storage, where the only role of the representation is to generate a faithful copy of the original (un-encoded) signal. However, in order to use a representation for decision or control, this program does not carry through.
Chapter 7 Marginalizing time
As we have discussed in the previous chapter, templates average the data with respect to the distribution of the nuisances, regardless of temporal ordering. Temporal continuity provides a mechanism for tracking, as discussed in Section 5.1, but is otherwise irrelevant for the purpose of describing static scenes or rigid objects. Temporal averaging in the template is, in general, suboptimal, so one could consider statistics other than the average, for instance the entire temporal distribution, as we have done in Section 6.4. While that approach improves the descriptor in the sense of retaining the distributional properties, it still does not respect temporal ordering. These are just two approaches to canonizing time by either averaging or binning. Other approaches include a variety of “spatio-temporal interest point detectors” or other aggregated spatio-temporal statistics .
If we are interested in visual decisions involving classes of “objectsWe call such objects “actions” or “events.”” actions, events that have a temporal component, then all approaches that “canonize” time necessarily mod-out also the temporal variation of interest, in the same way in which canonizing viewpoint eliminates the dependency of the invariant descriptor on the shape of the scene (Section 6.2). At the opposite end of the spectrum one could retain the entire time series (the temporal evolution of feature descriptors) (6.1), and compare them as functions of time using any functional norm in the calculation of the classifier (Section 2.1). This would not yield a viable result because the same action, performed slower or faster, or observed from a different initial time, would result in completely different time series (6.1), if not properly managed. Proper management here means that time should not just be canonized (as in a template or Time HOG) or ignored (by comparing time series as functions), but instead should be marginalized or max-outed. The only difference between these approaches is the prior on time, which is typically either uniform or exponentially decaying, so we will focus on a uniform prior, corresponding to a max-out process for time.
The simplest mechanism to max-out time is known as dynamic time warping (DTW). dynamic time warping dtw Dynamic time warping consists in a reparametrization of the temporal axis, via a function , that is continuous and monotonic (in other words, a contrast transformation as defined it in Section 2.2). Accordingly, the dynamic time warping distance is the distance obtained by max-outing the time warping between two time series. The problem with DTW is that it preserves temporal ordering but little else. The moment one alters the time variable, all the velocities (and therefore accelerations, and therefore forces that generated the motion) are changed, and therefore the outcome of DTW does not preserve any of the dynamic characteristics of the original process that generated the data. In other words, if the time series was generated by a dynamical model, DTW does not respect the constraints imposed by the dynamics. This means that a large number of different “actions” are lumped together under DTW. The pioneering work of the psychologist Johansson, however, showed that a great deal of information can be encoded in the temporal signal (Figure 7.1). This information is destroyed by DTW.
The next two sections describe DTW and point the way to generalizing it to take into account dynamic constraints. The reader who is uninterested in the subtleties of recognizing events or actions that have similar appearance but different temporal signatures can skip the rest of this chapter.
If we consider two time series of images, and , where , for simplicity assumed to have the same length,The case of different lengths can be also considered at the cost of a more complex optimization. then the simplest distance we could define is the norm of the difference, , which corresponds to a generative model where both sequences come from an (unknown) underlying processThe notation we use in this chapter abuses the symbols defined previously, but is chosen on purpose so that the final model will resemble those of previous chapters. , corrupted by two different realizations of additive white zero-mean Gaussian “noise” (here the word noise lumps all unmodeled phenomena, not necessarily associated to sensor errors)
The distance is then the (maximum-likelihood) solution for that minimizes
subject to (7.1). Here can be interpreted as the average of the two time series, and although in principle lives in an infinite-dimensional space, no regularization is necessary at this stage, because the above has a trivial closed-form solution. However, later we will need to introduce regularizers, for instance of the form . This admittedly unusual way of writing the distance makes the extension to more general models simpler, as we discuss in the next sections.
Consider now an arbitrary contrast transformationNote that this is not the contrast transformation operating on the image values, introduced in Section 2.2, but it is a contrast transformation applied to the temporal domain. of the interval , called a time warping, so that (7.1) becomes
The data term of the cost functional we wish to optimize is still , but now subject to (7.3), so that minimization is with respect to the unknown functions and as well as . Since the model is under-determined, we must impose regularization to compute the time-warping distance
Here is a suitable space where is assumed to live and is the space of monotonic continuous (contrast) transformations. In order for to be a viable temporal index, must satisfy a number of properties. The first is continuity (time, alas, does not jump); in fact, it is common to assume a certain degree of smoothness, and for the sake of simplicity we will assume that is infinitely differentiable. The second is causality: The ordering of time instants has to be preserved by the time warping, which can be formalized by imposing that be monotonic. We can re-write the distance above as
where is a tuning parameter that can be set equal to zero, for instance by choosing , and the assumptions on the warpings are implicit in the definition of the set . This is an optimal control problem, that is solved globally using dynamic programming in a procedure called “dynamic time warping” (DTW).
It is important to note that there is nothing “dynamic” about dynamic time warping, other than its name. There is no requirement that the warping function be subject to dynamic constraints, such as those arising from forces, inertia etc. However, some notion of dynamics can be coerced into the formulation by characterizing the set in terms of the solution of a differential equation. Following , as shown by , one can represent allowable in terms of a small, but otherwise unconstrained, scalar function : where denotes a Sobolev space. If we define is not to be confused with the scale parameter. then ; we can then stack the two into in this section is not to be confused with viewpoint; the notation is used because, consistent with the notation adopted earlier, it is an invertible nuisance. , indicative of a group (invertible nuisance) and , and write the data generation model as
as done by , where . Here and are given, and are nuisance parameters that are eliminated by minimization of the same old data term , now subject to (7.6), with the addition of a regularizer and an energy cost for , for instance . Writing explicitly all the terms, the problem of dynamic time warping can be written as
subject to . Note, however, that this differential equation is only an expedient to (softly) enforce causality by imposing a small “time curvature” .
2 Time warping under dynamic constraints
The strategy to enforce dynamic constraints in dynamic time warping is illustrated in Figure 7.2:
Rather than the data being warped versions of some common function, as in (7.3), we assume that the data are outputs of dynamical models driven by inputs that are warped versions of some common function. In other words, given two time series , we will assume that there exist suitable matrices , state functions of suitable dimensions, with their initial conditions, and a common input such that the data are generated by the following model, for some warping functions :
Our goal is to find the distance between the time series by minimizing with respect to the nuisance parameters the usual data discrepancy subject to (7.8), together with regularizing terms and with . Notice that this model is considerably different from the one discussed in the previous section, as the state earlier was used to model the temporal warping, whereas now it is used to model the data, and the warping occurs at the level of the input. It is also easy to see that the model (7.8), despite being linear in the state, includes (7.6) as a special case, because we can still model the warping functions using the differential equation in (7.6). In order to write this time warping under dynamic constraint problem more explicitly, we will use the following notation:
in particular, notice that is a convolution operator, where is the transfer function. We first address the problem where (and therefore ) are given. For simplicity we will neglect the initial condition, although it is easy to take it into account if so desired. In this case, we define the distance between the two time series
subject to and . Note that we have introduced an auxiliary variable , which implies a possible discrepancy between the actual input and the warped version of the common template. This problem can be solved in two steps: A deconvolution, where are chosen to minimize the first term, and a standard dynamic time warping, where and are chosen to minimize the second term. Naturally the two can be solved simultaneously.
When the model parameters are common to the two models, but otherwise unknown, minimization of the first term corresponds to blind system identification, which in general is ill-posed barring some assumption on the class of inputs . These can be imposed in the form of generic regularizers, as common in the literature of blind deconvolution , or by restricting the classes of inputs to a suitable class, for instance sparse “spikes” . This is a general and broad problem, beyond our scope here, so we will forgo it in favor of an approach where the input is treated as the output of an auxiliary dynamical model, also known as exo-system . This combines standard DTW, where the monotonicity constraint is expressed in terms of a double integrator, with TWDC, where the actual stationary component of the temporal dynamics is estimated as part of the inference. The generic warping , the output of the exo-system satisfies
and in this section is not to be confused with a diffeomorphism of the image domain. It is, however, a diffeomorphism of the time domain, hence the choice of notation. . This is a multiplicative double integrator; one could conceivably add layers of random walks, by representing as Brownian motion. Combining this with the time-invariant component of the realization yields the generative model for the time series :
Note that the actual input function , as well as the model parameters , are common to the two time series. A slightly relaxed model, following the previous subsection, consists of defining , and allowing some slack between the two; correspondingly, to compute the distance one would have to minimize the data term
subject to (7.12), in addition to the regularizers
which yields a combined optimization problem
subject to (7.12). This distance can be either computed in a globally optimal fashion on a discretized time domain using dynamic programming, or we can run a gradient descent algorithm based on the first-order optimality conditions. The bottom line is that one could use any of the distances introduced in this section, , to compare time series, corresponding to different forms of marginalization or max-out.
This concludes the treatment of descriptors. The next chapters focus on how to construct a representation from data, and how to aggregate different objects under the same category as part of the learning process.
Chapter 8 Visual exploration
In this chapter we study the inverse problem of hallucination, introduced in Section 3.1, that is the problem of exploration. Whereas hallucination produces images given a representation; exploration produces a representation given images. The goal of exploration is to actively control the data acquisition process in such a way that aggregating Actionable Information eventually yields a complete representation. As we acquire more and more data, the hope is that the set of representations that are compatible with the data shrinks, although not necessarily to a singleton (a complete representation is not necessarily unique). In other words, we hope that the exploration process will reduce the uncertainty on the representation. When and if the inferred representation is complete, it can synthesize the light-field of the original scene up to the uncertainty of the sensors, and we say we have performed sufficient exploration. Exploration can be more or less efficient, in the sense that sufficiency can be achieved with a varying cost of resources (e.g. time, energy).
Exploration is the process that links maximal invariants, , whose complexity we called Actionable Information (AI), to minimal sufficient statistics of a complete representation, whose complexity we called complete information (CI). Because of non-invertible nuisances, the gap between AI and CI can be filled by exercising some form of control on the sensing process. Such control could be exercised in data space, for instance by choosing the most informative features, or in sensor space, for instance by selecting sensing assets in a sensor network, or in physical space, for instance by moving around an occlusion or moving closer to an unresolved region of the scene.
We start by designing a myopic explorer, driven simply by the maximization of Actionable Information. Ideally, by accumulating AI, one would hope to converge to the CI. Unfortunately, this is in general not the case for such a myopic explorer. We therefore consider a slightly less primitive explorer seeking to maximize its reward over a receding horizon. Again, in general, this strategy is not guaranteed to achieve complete efficient exploration. Thus, the modeling exercise points to the need to endow the explorer with memory that can summarize in finite complexity the results of past explorations. Such a memory will be precisely the representation we are after, and we discuss inference criteria that can drive the building of a representation. In some simple instances, such criteria yield viable computational procedures.
In all cases, occlusions and scaling/quantization play a critical role in exploration, a process that can be thought of as the inversion of such nuisances. Therefore, at the outset, we will need efficient methods to perform occlusion detection, to be used either instantaneously – by comparing two temporally adjacent images, as in myopic memoryless exploration – or incrementally, by comparing each new image with the one hallucinated from the current representation.
Optical flow optical flow refers to the deformation of the domain of an image that results from ego- or scene motion. It is, in general, different from the motion field, (2.9), that is the projection onto the image plane of the spatial velocity of the scene , unless three conditions are satisfied: Lambertian reflection, constant illumination, and co-visibility. We have already adopted the Lambertian assumption in Section 2.2, and it is true that most surfaces with benign reflectance properties (diffuse/specular) can be approximated as Lambertian almost everywhere under diffuse or sparse illuminants (e.g. the sun). In any case, widespread violation of Lambertian reflection does not enable correspondence , so we will embrace it like the majority of existing approaches to motion estimation. Similarly, constant illumination is a reasonable assumption for ego-motion (the scene is not moving relative to the light source), and even for objects moving (slowly) relative to the light source. Co-visibility is the third and crucial assumption that has to do with occlusions and until recently has been widely neglected in the computation of optical flow. If an image contains portions of its domain that are not visible in another image, these can patently not be mapped onto it by optical flow vectors. Constant visibility is often assumed because optical flow is defined in the limit where two images are sampled infinitesimally close in time, in which case there are no occluded regions, and one can focus solely on discontinuities of the motion field. But the problem is not that optical flow is discontinuous in the occluded regions; it is simply not defined; it does not exist. By definition, an occluded region cannot be explained by a displaced portion of a different image, since it is not visible in the latter. Motion in occluded regions can be hallucinated (extrapolated, or “inpainted”) but not validated on data.
The aperture problem refers to the fact that the motion field at a point can only be determined in the direction of the gradient of the image at that point (Figure 3.7). Therefore, occlusions can only be determined if the gradient of the radiance intersects transversally the boundary of the occluded region. When this does not happen (for instance when a region with constant radiance occludes another one with constant radiance), an occlusion cannot be positively discerned from a material boundary or an illumination boundary. For instance, in the Flower Garden sequence (Figure 8.1), the (uniform) sky could be attached to the branches of the tree, or it could be occluded by them. Often, priors or regularizers are imposed to resolve this ambiguity, but again such a choice is not validated from the data. We prefer to maintain the ambiguities in the representation, deferring the decision to the exploration process, when data becomes available to disambiguate the solution (e.g. the tree passing in front of a cloud). This naturally occurs over time as the initial representation converges towards the complete representation.
i.e. , the additive uncertainty is normally distributed in space and time with an isotropic and small variance . Note that we are using the (overloadedWe had already used to indicate the loss function in Section 2.1, but that should cause no confusion here.) symbol for the covariance of the noise, whereas usually we have employed the symbol . The reason for this choice will become clear in Equation (8.17), where will be interpreted as a Lagrange multiplier. lagrange multiplier We define the residual
on the entire image domain , via (for simplicity we omit the arguments of the functions when clear from the context)
Note that is undefined in , and is undefined in , in the sense that they can take any value there, including zero, which we will assume henceforth. We can then write, for any ,
and notice that, because of (i), is large but sparse,In the limit , “sparse” stands for almost everywhere zero; in practice, for a finite temporal sampling , this means that the area of is small relative to . Similarly, “dense” stands for almost everywhere non-zero. while because of (ii) is small but denseIn the limit , “sparse” stands for almost everywhere zero; in practice, for a finite temporal sampling , this means that the area of is small relative to . Similarly, “dense” stands for almost everywhere non-zero.. We will use this as an inference criterion for , seeking to optimize a data fidelity criterion that minimizes the norm of (a proxy of the area of ), and the log-likelihood of (the Mahalanobis norm relative to the variance parameter )
we can approximate, for any ,
where the linearization error has been incorporated into the uncertainty term . Therefore, following the same previous steps, we have
Since we typically do not know the variance of the process , we will treat it as a tuning parameter, and because or yield the same minimizer, we have attributed the multiplier to the second term. In addition to the data term, because the unknown is infinite-dimensional, we need to impose regularization, for instance by requiring that the total variation (TV) of be small
Not only is this result appealing on analytical grounds, but is also enables the deployment of a vast arsenal of efficient optimization schemes, as proposed in . In practice, although the global minimizer does not depend on the initial conditions, it does depend on the multipliers and , for which no “right choice” exists, so an empirical evaluation of the scheme (8.19) is necessary .
It is tempting to impose some type of regularization on the occluded region (for instance that its boundary be “short”), but we have refrained from doing so, for good reasons. In the presence of smooth motions, the occluded region is guaranteed to be small, but under no realistic circumstances is it guaranteed to be simple. For instance, walking in front of a barren tree in the winter, the occluded region is a very complex, multiply-connected, highly irregular region that would be very poorly approximated by some compact regularized blob (Figure 8.2).
Source code to perform simultaneous motion estimation and occlusion detection is available on-line from . It can be used as a seed to detect detached objects, or better detachable objects , or to temporally integrate occlusion information so as to infer depth layers as done in . We will, however, defer the temporal integration of occlusion information to the next sections, where we discuss the exploration process. For now, what matters is that it is possible, given either two adjacent images, , or an image predicted via hallucination, for instance and a real image , to determine both the deformation taking one image onto the other in the co-visible region, and the characteristic function of such a region, that is the occluded domain.
In the next section we begin discussing the implication of occlusion detection for exploration.
2 Myopic exploration
Consider an image , taken at time , and imagine using it to predict the next image, . In the next section we describe this process in the absence of non-invertible nuisances. We show that in this case one image is sufficient to determine a complete representation, and there is no need for exploration at all. The story is, of course, different when there are invertible nuisances.
In the absence of occlusions (for instance, if the images are taken by an omni-directional camera inside an empty room) and quantization errors or noise (if the images are samples of the scene radiance that satisfy Nyquist’s condition – if that was possible, that is), and if the scene obeys the Lambert-Ambient-Static model (2.6), the new image can be generated by the old image via a suitable contrast transformation of its range and diffeomorphic deformation of its domain. In other words, the first image can be used to construct a representation as we have discussed in Section 2.4.4, which in turn can be used to hallucinate any other image of the same scene, for instance . In fact, from (2.6), we can solve for in the first image via , where and substitute in the second, so we have
where and where we have aggregated the two contrast transformations and into one. This is exactly the hallucination process described in Section 3.1, whereby a single image , supported on a plane, is interpreted as a representation and used to hallucinate the next image .
In the absence of non-invertible nuisances, the only purpose of the second image is to enable the estimation of the domain deformation and the contrast transformation through equation (8.21) . So, the first image captures the radiance , and in combination with the second image they capture the shape , entangled with the nuisance in the domain deformation , as discussed in Section 6.2 and further elaborated in B.3. Any additional image , not necessarily taken at an adjacent time instant, can be explained by these two images. In fact, any additional image can be used to test the hypothesis that it is generated by the same scene, by performing the same exercise with either of the two (training) images, to test whether they are compatible with (i.e. can be generated by) the same scene, except for the residual error that is temporally and spatially white, and isotropic (homoscedastic).This kind of geometric validation is used routinely to test sparse features for compatibility with an underlying epipolar geometry . This test consists of an extremization procedure (Section 2.3 and Figure 2.5), whereby nuisance factors, as well as the scene, are inferred as part of the decision process, and the residual has high probability under the noise model. This can be thought of as a “recognition by (implicit) reconstruction” process, and was common in the early days of visual recognition via template matching.
Notice that, as discussed in Section 6.2, contrast (a nuisance) interacts with the radiance, so one can only determine the radiance up to a contrast transformation. Similarly, motion (a nuisance) interacts with the shape/deformation, so one can only determine shape up to a diffeomorphism. If one were to canonize both contrast and domain diffeomorphisms, then some discriminative power would be lost as any two scenes that are equivalent (modulo a domain diffeomorphism, whether or not they are generated by a scene with the same shape) would be indistinguishable from a maximal invariant feature (or from any invariant feature for that matter) .
In summary, in the absence of non-invertible nuisances, a single (omni-directional, infinite-resolution, noise-free) image can be used to construct a representation from which the entire light field of the scene can be hallucinated. This is what we called a complete representation. Its minimal sufficient statistic is the Complete Information, and there is no need for exploration. The need for exploration does, of course, arise as soon as non-invertible nuisances are present. The case discussed above is a wild idealization since, even in the absence of occlusions, quantization and noise introduce uncertainty in the process, and therefore there is always a benefit from acquiring additional data, even in the absence of any active control.
2.2 Dealing with non-invertible nuisances
In general, equation (8.21) is valid only in the co-visible domain (Section 2.2). Neglecting contrast transformations for simplicity, we have that
The complement of the co-visible domain is the occluded domain
Since we will assume that there is a temporal ordering (causality), we will consider only forward occlusions (sometimes called “un-occlusion” or “discovery”); that is, portions of the domain of , , whose pre-image was not visible in . The restriction of the image to this subset, cannot be explained using .
Consider now an image , and imagine using it to predict the next image , as we have done in the previous section. No matter how we choose , we cannot predict exactly what the new image is going to look like in the occluded domain , even if we had an omni-directional, infinite-resolution, noise-free camera. Therefore, in the occluded domain we have a distribution of possible “next images,” based on the priors. The entropy of this distribution measures the uncertainty in the next image, and therefore the potential “information gain” from measuring it (before we actually measure it). Once we discount other nuisance factors, by considering a maximal invariant of the next image in the occluded domain, we have the innovation
whose complexity represents the Actionable Information Increment (AIN):
The AIN is the uncertainty in the innovation, or the “degree of unpredictability” of future data. The above is the contribution to the AIN due to occlusions, that can be determined as in Section 8.1. However, we also have uncertainty due to quantization and noise.Quantization can also be thought of as a form of occlusion mechanism, since details of the radiance that exist at a scale smaller than the back-projection of the area of a pixel onto the scene are “hidden” from the measurement. Rather than moving around an occluder, one can “undo” quantization by moving closer to the scene. This is simpler to model, as it is usually independent of the scene: Uncertainty due to scaling and quantization increases linearly with distance, and uncertainty due to noise is independent of both the scene and the viewer. In all cases, however, there exists a control action that can reduce uncertainty. For the case of scale, it is zooming, or translating along the optical axis, or increasing the sensor’s resolution. For the case of noise, it is taking repeated (registered) measurements.
In all cases, what yields a non-zero innovation is the presence of non-invertible nuisances, , that include occlusion, quantization, and other unmodeled uncertainty (noise). We then have that the AIN can be computed as the conditional entropy of
where we have marginalized over all non-invertible nuisances. We therefore have, for the specific case of just two images,
This construction can be extended to the case where we have measured multiple images up to time , as we discuss in the next section.
The innovation can be thought of as a form of generalized background subtraction. In the most trivial case, the representation is derived from one image only (the background image) and the only motion in the image is due to a “foreground object.” Other background subtraction schemes, including those based on multiple layers or on an aggregate model of the background , can be understood in the framework of occlusion detection and innovation under different prediction models .
2.3 Enter the control
Clearly, the depends on the motion between and , as well as on the (unknown) scene . For a sufficiently small , , where is the rigid body velocity of the viewer (assumed constant between and ), the operator is the “hat” operator that maps a -dimensional vector of rotational and translational velocities into a “twist” and denotes the Lie algebra of “twists” associated with . Thus, the motion between and is given by , which one can control by moving the sensor with a velocity . By assuming velocity to be sufficiently small, we can take to be the unit time interval, . Therefore, the can, to a certain extent, be controlled. When emphasizing the dependency on the control input, we write . A myopic controller would simply try, at each instant, to perform a control action (e.g. a rigid motion, zooming, or capturing and averaging multiple images) so as to maximize the :
Note that the AIN is computed before the control is applied, and therefore before the “next image” is computed. Thus the AIN involves a distribution of next images, marginalized with respect to all non-invertible nuisances. Once we actually measure the next image, we sample an instance of the innovation process. If we have discovered nothing in the next image, the sample of the innovation will be zero.
Therefore, a myopic agent could easily be stuck in a situation where none of the allowable control actions yield any information gain. The observer would then stop despite having failed to attain the Complete Information. The observer could also be trapped in a loop where it keeps discovering portions of the scene it has seen before, albeit not in the immediate past, for instance as it moves around a column. This is because the controller (8.28) does not have memory.
To endow the controller with memory we can simply consider the innovation relative to the history , rather than relative to just the current image .
There are two problems with this approach: One is that it is still myopic. The other is that the history grows unbounded.
2.4 Receding-horizon explorer
A slight improvement can be had by planning a controller that maximizes the AIN over a finite horizon, for instance of length :
Of course, as soon as the agent makes one step, and acquires , the history changes to ; therefore, the agent can use the control planned for the -long interval to perform the first step, and then re-plan the control for the new horizon from to . One can also consider an infinite horizon , which presents obvious computational challenges. Regardless of the horizon, however, all controllers above have to cope with the fact that the history keeps growing. Even setting aside the fact that no provable guarantees of sufficient exploration exist for this strategy, it is clear that the agent needs to have a finite-complexity memory that summarizes all prior history.
2.5 Memory and representation
A memory is a function of past data, . Of all functions, we are interested in those that are parsimonious (minimal), and “informative” in the sense that they can generate copies not of the data, but of the maximal invariants of the data. These are the characteristics of what we have defined as a representation. At any given time , we can infer a representation that is compatible with the history and that, eventually, may converge to a complete representation . Building such a representation (memory) is an inference problem that can be framed in the context of exploration as a System Identification problem under a suitable prediction-error criterion . Given a collection of data , we are interested in determining a “model” such that the statistic best summarizes the entire past for the purpose of predicting the entire future . In Remark 14 we will shows that this is equivalent to determining
In prediction-error methods, usually the complexity constraint is enforced by choosing the bound on the order of the model (the number of free parameters), and the entropy is approximated with its empirical estimate, assuming stationarity. For the case where all the densities at play are Gaussian, minimizing the entropy above reduces to minimizing the sum of squared one-step prediction errors. This problem has also been addressed in the literature of information-based filtering , but can only be realistically solved for low-dimensional state-spaces using particle filtering, or for linear-Gaussian models (although see ).
In a causal exploration process, where data is gathered incrementally, we would like to update the estimate of the representation; by minimizing the conditional entropy above. At the same time, we would like to control the exploration process so as to maximize the AIN. This is discussed in the next section where we describe dynamic explorers.
3 Dynamic explorers
In this section we consider an entity including a sensor (a video camera) capable of exercising a control, control for instance by changing the vantage point or the characteristics of the sensor (zooming). We call such an entity an explorer. explorer In the absence of any restriction on the control, so long as there are non-invertible nuisances, the provides guidance to perform exploration, and memory provides a way to incrementally build a representation . Ideally, such a representation would eventually converge to a minimal sufficient statistic of the light field, , thus accomplishing sufficient exploration. Sufficient exploration, if possible, would enable the absence of evidence to be taken as evidence of absence .
We start with one image, say , and its maximal invariant , that is compatible with a (typically infinite) number of scenes, , that are distributed according to some prior that has high entropy (uncertainty). Compatibility means that the image can be synthesized from up to the modeling residual . As we have seen in Section 3.1, we can easily construct a sample scene by choosing to be a unit sphere, , and choosing where in the entire sphere but for a set of measure zero. Therefore, we call . Clearly, if we had only one image, as we did in Section 3.1, we would not need a representation to explain it, and indeed we do not even need a notion of scene. So, in our case, this is just the initialization of the explorer, which corresponds to one of many possible representations that are compatible with the first image (see Figure 3.1).
Given the initial distribution, and the next measurement, , we can compute an innovation , that is a stochastic process that depends on the (unknown) nuisances as well as on the distribution of . We can then update such a distribution by requiring that it minimizes the uncertainty of the innovation. The uncertainty in the innovation is the same as the uncertainty of the next measurement, and therefore we can simply minimize the conditional entropy of the next datum, once we have marginalized or max-outed the nuisances: where . In practice, carrying around the entire distribution of representations is a tall order, for the space of shape and reflectance functions do not even admit a natural metric, let alone a probabilistic structure that is computable. So, one may be interested in a point-estimate, for instance one of the (multiple) modes of the distribution, the mean, median, or a set of samples. In any case, we indicate this via . Now, instead of marginalizing over all (invertible and non-invertible) nuisances, we can canonize the invertible ones, and therefore, correspondingly, minimize the actionable information gap, instead of the conditional entropy of the raw data: At a generic time , assuming we are given , we can perform an update of the representation via
where denotes a Gaussian density with mean and isotropic standard deviation . To the equation above we must add a complexity cost, for instance where is a positive multiplier.
Now, at time , the updated representation can be used to extrapolate the next image . The hallucination process carries some uncertainty because of the non-invertible nuisances, and this uncertainty is precisely the information gain to come from the next image. Since the next image depends on where we have moved (or, more in general, on what control action we have exercised), we can choose the control so that the next image will be most informative, i.e.
where includes complexity or energy costs associated with the control action . Thus, inference and control are working together, one to maximize the uncertainty of the next data, the other to minimize it.
The construction of a representation from a collection of data treated as a batch has been described in for the case of multiple occlusion layers portraying arbitrarily deforming objects, and in for the case of rigid objects generating self-occlusions. This requires the dynamic update of the visible portion of the domain as a result of the update of the representation. In the case of , the representation consisted of an explicit model of the geometry of the scene (a collection of piecewise smooth surfaces) as well as of the photometry of the scene, consisting of the radiant tensor field, that could be used to generate “super-resolution images” (i.e. images hallucinated at a resolution higher than that of the native sensor that collected the original data), as well as to generate views from different vantage points despite non-Lambertian reflection. In all these cases, the uncertainty was assumed Gaussian, so minimum-entropy estimation reduces to wide-sense filtering (minimum-variance).
The design of a control action, given the current representation, for the case of uncertainty due to visibility has been described in for compact spaces, and extended in for unbounded domains. The case where uncertainty due to scale and noise is also present has been described in .
Note that, in general, there is no guarantee that in any meaningful sense. The most we can hope for is that , as we have pointed out. In other words, what we can hope is that our representation can at most generate data that is indistinguishable from the real data, up to the characteristics of the sensor. Since the inference of a representation is guided by a control, and the hallucination process requires the simulation of the invertible nuisance (which includes vantage point), Koenderink’s famous characterization of images as “controlled hallucinations” is particularly fitting. Following the analysis above we can say that the representation is obtained through a controlled exploration (perception) process, and from the representation we can then hallucinate images in a controlled fashion.
In general, however, it is not possible to guarantee that the exploration process will converge, even in the sense of (2.18) . However, it is trivial to design exhaustive control policies that, under suitably benign assumptions on the environment (that the scene is bounded, that the topology is trivial, and that the radiance obeys some sparsity or band-limited assumption) will achieve sufficient exploration, at least asymptotically:
For instance, a Brownian motion restricted to the traversable space will, eventually, achieve complete exploration of a static environment.
The goal of exploration is, therefore, to trade off the efficiency of the exploration process, including the cost of computing an approximation to the policy (8.32)-(8.33), with the probability of achieving sufficient exploration. This is beyond the scope of this manuscript and we refer the reader to the vast literature on Optimal Control, Path Planning, Robotic Exploration, and partially-observable Markov Decision Processes (POMDP) in Artificial Intelligence. For the case of uncertainty due to visibility (occlusions) both provide bounds on the expected path length as a function of the complexity of the environment.
The discussion above suffices to our purpose of closing the circle on the issue of representation introduced in Section 2.4.4 and discussed in Section 3.1, by providing means to approximate it asymptotically from measured data. At any given instant of time, our representation is incomplete, and any discrepancy between the observed images and the images hallucinated by the representation (the innovation) can be used to update the representation and reduce the uncertainty in .
The fact that, to ensure inference of a complete representation, a control must be exercised, links the notion of representation (and therefore of information) inextricably to a control action. More precisely, the exploration process links the control to the representation, and actionable information to the complete information. This discussion, of course, only pertains to the limiting case where we have arbitrary control authority to move in free space, into every nook and cranny (to invert occlusions), to zoom-in or move arbitrarily close and have arbitrarily high sampling rate (image resolution, to invert quantization), and to stay arbitrarily long in front of a static scene (or to sample in time arbitrarily fast relative to the time constant of the temporal changes in the scene), to invert noise. The opposite extremum is when we have no control authority whatsoever, in which case all we can compute is a maximal invariant and its actionable information, as discussed in Section 2.5. In this case the Actionable Information Gap cannot be closed.In addition to mobility, another active sensing modality can be employed, for instance by controlling accommodation) or by flooding the space with a controlled signal and measuring the return, as in Radar.
In between, we can have scenarios whereby a limited control authority can afford us an increase in actionable information by aggregating the over time, thus taking us closer to the complete information. Therefore, we can think of the “degree of invertibility” of the nuisance, properly defined, as a proxy of recognition performance. This we do in Section 8.4.
This chapter concludes the treatment of active exploration. In the next chapter we turn our attention to constructing models of not individual objects, but object classes with some intra-class variability.
The functional optimization problem (8.32) is closely related to the Information Bottleneck principle , that prescribes finding the representation that best trades off complexity and task fidelity by solving
once we substitute and recall that since , and does not depend on . When the underlying processes are stationary and Markovian, minimizing is equivalent to minimizing .
4 Controlled recognition bounds
In Communication Theory, given sufficient resources (bits), one can make the performance in the task (transmission of data) arbitrarily good, at least in principle, and for a given limit on the resources, one can quantify a bound on performance that does not depend on the particular signal being transmitted, but only on its distributional properties . It would be desirable to have a similar tool for the case of visual decision problems, whereby one could quantify performance in a visual decision (detection, localization, recognition, categorization etc.), rather than in a transmission task. The critical question is: what represents the resource, that plays the role of the bit rate in communications? What do we need to have “enough of” in order to guarantee a given level of performance in a visual decision task? Enough pixels? Enough visibility? Enough views? Enough computing power? In this section, we will see that the critical resource for visual decisions is the control authority the viewer has on the sensing process. We will argue that, for a passive observer with no control authority whatsoever, there is no amount of pixels or computing power that will suffice to guarantee an arbitrarily high level of performance in a visual decision task (Section LABEL:sect-passive-bounds). In the opposite limiting case, we will show that an omnipotent explorer, capable of going everywhere and staying there indefinitely, not only can guarantee a bound on the decision error, but can make this error arbitrarily small in the limit (Section LABEL:sect-active-bounds). In between, we will attempt to quantify the amount of control authority and characterize its tradeoff with the decision error (Section LABEL:sect-control-recognition).
Some of the results in this chapter may appear obvious to some (of course we cannot recognize something we cannot see!), misleading to others, and confusing to others yet. Some examples are admittedly straw-men, meant to illustrate the importance of mobility for cognition, but we will try to state our assumptions as clearly and unequivocally as possible, and hopefully what matters will emerge, which is the fact that control plays a key role in perception, and that the notion of visual information, which is the topic of this manuscript, is the knot that ties them. Of course it is always possible to construct specific cases and counter-examples that violate the statements, but our point is that these statements are valid on average, once one considers all possible objects and all possible scenes. So, if we want to get visual decisions under control, in the sense of being able to provide guaranteed bounds on the decision performance, we have to put control in visual decisions, in the sense of being able to exercise some kind of control authority over the sensing process.
Chapter 9 Learning Priors and Categories
Previous chapters have shown how to handle canonizable nuisances (Section 3), and non-invertible nuisances via either marginalization (2.12), extremization (2.13), or – if we are willing to sacrifice optimality for decision-time efficiency – by designing invariant descriptors (Chapters 4 and 6). In all cases, the design of a visual classification algorithm requires knowledge of priors on the nuisances as well as on the scene.
The procedure we have outlined for building a template (2.30), or a Time HOG descriptor (Section 6.4) using a training sample , assumes that a sequence of frames is available (Section 5.1). Thus we have implicitly assumed that the scene is the same, not just the class . Indeed, before Chapter 7 we even assumed that the underlying scene was static, which enabled us to attribute the variability in the data to nuisances, rather than to intrinsic factors. Even in Chapter 7 we assumed that local variability was due to nuisance factors, and in both cases this enabled us to determine the object-specific nuisance distribution.
What we have deferred until now is the possibility for intrinsic (intra-class) variability. It cannot be realistically assumed that an explicit model be available for all classes of interest, and therefore such variability should be learned, although it is likely that some basic components of models can be shared among classes. In this chapter we describe an approach to build category models starting from the local representations described in previous chapters.
The starting point are occlusions, detected as described in Section 8.1. These can be used to bootstrap a partitioning of images into detachable objects as we will show in Section LABEL:sect-detachable. Such a “segmentation” process is different than traditional (single-image) segmentation, and can be accomplished through relatively simple computations (linear programming). Such detachable objects can then be tracked over time (Section LABEL:sect-tracking), providing the support where the local descriptors of Section 6.4 can be aggregated.
However, knowledge that a certain descriptor belongs to a certain object – while an improvement on than the so-called “bag-of-feature” approach that considers the distribution of descriptors on the entire image – still fails to capture important geometric relationships. In some cases, there may be an advantage in further subdividing objects into “parts”, or subsets of descriptors based on spatial relations (Section LABEL:sect-parts).
This process produces a model of a specific object, removing nuisance variability from the data. In order to represent intrinsic variability and arrive at a categorical model it is necessary to aggregate different instances of the same class. We will assume that the class label is provided as part of the training process. This is because sometimes categories can be defined based on non-visual characteristics. For instance, an object can be called a chair if someone can sit on it, which is a functional property that may or may not have visual correlates. Thus the class distribution of chairs may include largely disparate objects with different shapes and materials.
This approach is somewhat different from the conventional approach to object categorization, that aims to detect or recognize the category before the specific object. This is motivated by studies of primate perception, where there is an evolutionary advantage in being able to assess coarse categories (e.g. animal or not) pre-attentively. The category model that is implicit in many of these approaches is not very different from an object model, and an effort is under way to make these models more specific and more discriminative to perform fine-scale categorization, or in other words getting closer to models of individual objects. In our case, objects come before categories. When we learn a model of a chair, we first learn a model of this particular chair. The fact that someone may sit on it makes it a chair just like another one regardless of its shape and appearance. This also allows one particular object to be easily attributed to multiple categories: A toy elephant can be a chair if someone can sit on it. Of course, there may be particular categories that are defined by visual similarity, in which case one can expect relatively simple categorical distribution that is well summarized by few samples.
In summary, a (detachable) object is one that triggers occlusions, and that supports a collection of descriptors that are organized into parts. A collection of objects induces a distribution of parts and their spatial configuration. Such a distribution can be multi-modal and highly complex, and often requires external supervision to be learned. Of course, descriptors and parts can be shared among objects and also among categories, but this is beyond our scope here and is the subject of current research.
Chapter 10 Discussion
Physical processes contributing to image formation occur at a level of granularity that is infinitesimal relative to the sampling capacity of optical sensors. And yet, we seem to take for granted that the epistemological process requires breaking down the data into elementary “atoms.” Information theory suggests that such a symbolization process would occur at a loss, and that integrated systems capable of sensing and action would be best designed in an end-to-end fashion.
However, we have seen that nuisance factors such as illumination and viewpoint changes account for almost all the variability in the data, and therefore the process of eliminating their influence in the data can lead to a lossless symbolization. In other words, under certain circumstances, it is possible to throw away almost all the data, and yet none of the information.
Furthermore, nuisances that are not invertible, such as occlusions, can be factored out through a controlled sensing action. Indeed, control is the “currency” that trades off performance in a perception process. The more control an agent can exercise on the sensing process, the tighter the bound that can be guaranteed on the reduction of the Actionable Information Gap.
The models we describe in this manuscript are idealized abstractions. Nevertheless, an abstraction is useful to guide investigation and to evaluate existing schemes. In fact, one of the many possible objections to our program is that the models we used in our analysis (for illumination, deformation, occlusion etc.) are so simplistic as to make the formalization exercise futile. Better is to devise new algorithms and test them on empirical benchmarks. That is generally true, although an abstraction allows us to ascertain how different algorithms are related, and determine not just whether one works better than another, but why. Shannon’s sampling theorem is valid only for strictly band-limited signals, a wildly idealized abstraction of real signals. And yet, it provides useful guidelines for the design of certain algorithms, for instance for audio processing.
Another valid objection is that we have reduced visual perception to pattern classification. We have not tackled high-level vision, perceptual organization, and all the high-level models that lie at the foundations of our understanding of higher visual processing. This does not imply that these problems are not important. We have just chosen to focus on the lowest level, which is the conversion from analog signals to discrete entities, on which high-level models can be built.
So far we have been deliberately vague about the difference between information and knowledge. We believe knowledge acts on information, but also needs tools to manipulate representations, including counterfactuals and causal analysis . Nevertheless, most investigations that we are aware of take a discrete, atomic representation as a starting point, and fail to bridge the “gap” required to explain why we need such a representation in the first place. We hope to have addressed this in a number of ways. First, by showing that even for invertible nuisances, invariants can be a set of measure zero . Second, non-invertible nuisances call for breaking down the image into pieces (segments); show that to recognize an object with a viewpoint invariant feature you have to discard its shape. Interestingly, this was already understood by Gibson, who expressed it in words: (, page 271):
“Despite the argument that because a still picture presents no transformation it can display no invariants under transformation, [in Gibson, 1973] I ventured to suggest that it did display invariants”.
We have shown that, in the absence of specific modeling of the nuisances, one would have to marginalize them as part of the matching process, which entails infinite-dimensional optimization. This does not mean that one cannot obtain positive, even impressive, results on a specific domain, for instance in semi-structured or fully structured environments where the variability due to nuisances is kept at bay. However, one should not extrapolate the optimism stemming from success on a specific domain with the solution of the general problem.
The notion of Actionable Information presented in this manuscript is closely related to the notion of Information proposed by Gibson, although he never formalized these notions; in words, however, page 245 of recites
“The hypothesis that invariance under optical transformation constitutes information for the perception of a rigid persisting object goes back to the moving-shadow experiment (Gibson and Gibson, 1957)”
“Four kinds of invariants have been postulated: those that underlie change of illumination, those that underlie change of the point of observation, those that underlie overlapping samples, and those that underlie a local disturbance of structure. […] Invariants of optical structure under changing illumination […] are not yet known, but they almost certainly involve ratios of intensity and color among parts of the array. […] Invariants […] under change of the point of observation […] some of the changes […] are transformations of its nested forms, but the major changes are gain and loss of form, that is, increments and decrement of structures, as surfaces undergo occlusion. […] The theory of the extracting of invariants by a visual system takes the place of theories of “constancy” in perception, that is, explanations of how an observer might perceive the true color, size, shape, motion and direction-from-here of objects despite the wildly fluctuating sensory impressions on which the perceptions are based.”
The line of the program sketched by Gibson in his theory of “information pickup” where “the occluded becomes unoccluded” is very closely related to the notion of invertibility of the nuisance and controlled recognition that we discuss in Chapters 8 and 8.4.
2 Alan Turing
Alan Turing is perhaps the researcher that showed the deepest insight into the questions raised in this manuscript. On one hand, he specifically addressed the rise of “discontinuous behavior” in continuous chemical systems through reaction-diffusion processes . On the other hand, he addressed the issue of intelligent behavior in machines. While Turing’s theory of morphogenesis, despite its limits, can be taken as sufficient evidence that biological systems may evolve towards discrete structures, it does not provide evidence of the need to organize measured data into discrete “information entities.”
Since in building machine vision systems we are not constrained by the chemistry of reaction-diffusion, Turing’s theory remains incomplete. In particular, it does not address why a data-processing system (biological or otherwise) built from optimality principles should exhibit discrete internal representations rather than a collection of continuous input-output maps. This “gap” thus remains open in Turing’s work. Indeed, it is summarily dismissed:
“the confusion between [analog and digital machines] is to be ignored. Strictly speaking, there are no [digital] machines. Everything really moves continuously. But there are many kinds of machine which can profitably be thought of as being discrete-state machines. For instance in considering the switches for a lighting system it is a convenient fiction that each switch must be definitely on or definitely off. There must be intermediate positions, but for most purposes we can forget about them.”
He therefore moved on to characterize “intelligent behavior” in terms of symbols, as convenient to sustain the discourse, without regard to how such symbols might come to be in the first place. Digitization is indeed an abstraction. It is, however, an abstraction that “destroys” information, in the classical sense (Section 2.4.1). And yet, it seems to be a necessary step to knowledge or “intelligence”.Note that Godel’s assertion of the limitations of logic (1931) is irrelevant in this context, as our argument is not in favor of logic, but about the necessity of a discrete/finite internal representation. This could be used as an approximation tool, and continuous techniques be used for inference rather than logic.
3 Norbert Wiener
As we have remarked earlier, despite anticipating the role of information in making a decision, Wiener remains anchored to the notion of information as entropy. To be fair, this was revolutionary at the time, and indeed Wiener is credited as one of the proposers of using notions from statistical mechanics, including entropy, in the processing of signals. Part of the problem is that the task Wiener was implicitly considering is the reconstruction of a signal under noise. This is not surprising since so much of Wiener’s work was devoted to Brownian motions and to the characterization of stochastic processes driven by “noise”.
It is interesting, however, to note that Wiener had the intuition that transformations play an important role, including the notion of the invariant under a group. On page 135 of , he remarks about the ability of the human visual system to recognize line drawings, pointing the attention to discontinuities. He also introduces the notion of “group scanning” (what we have called max-out, or registration), hypothesizing computational hardware in the brain that could be implementing such an operation (page 137). Indeed, he suggests that McCulloch’s apparatus could perform such a group-scanning. He even introduces the first moment as an invariant statistic to a group in equation (6.01) on page 138, and called it a gestalt! It is unfortunate that Wiener did not further elaborate on these points.
Wiener also implies some of the seeds of ecological vision, mixed by the notion of invariant statistics, suggesting that
“we tend to bring any object that attracts our attention into a standard position and orientation, so that the visual image which we form of it varies within as small a range as possible.”
This would be equivalent to “physical canonization” which, as Gibson suggested, can always be performed even when the nuisance is not invertible from a single image. Wiener does not explain, however, how his notion of information is compatible with his hypothesis that
“processes occur […] in a considerable number of stages each step in this process diminishes the number of neuron channels involved in the transmission of visual information”
a sentence that reveals both the attachment to transmission of information as the underlying task, and the notion of “compression” as information that is, however, not developed further.
4 David Marr
This manuscript could be interpreted as an attempt to frame the ideas of Marr into an analytical framework, although Marr did not frame the questions he asked in the context of a task.
“Our view is that vision goes symbolic almost immediately, right at the level of zero-crossings, and the beauty of this is that the transition […] is probably accomplished without loss of information”
This statement, from , is incorrect if one means “information” in the sense of Shannon . However, it is precisely correct if one is to take the approach described in this manuscript. The use of zero-crossings was ultimately rejected because the decoding process was unstable; however, as we have argued, an internal representation is not needed for reconstruction; instead, for the task of recognition, an internal representation is necessary, and zero-crossings (a special case of feature detector in our parlance) might not have been a bad idea after all.Marr’s theories pertains not to vision in general, but to visual recognition. There is no need for an internal representation (such as that afforded by the primal sketch, the 2-1/2D sketch and the full sketch) for navigation, 3-D reconstruction, rendering or control. It is interesting that Marr uses stereo, and in particular Julesz’ random dot stereograms, to validate his ideas, where a fully continuous algorithm that acts directly on the data would do as well or better.
5 Other related investigations
Donald L. Snyder used to often purport his mother’s advice to “never throw away information.” Our discussion reveals that any sensible notion of information that relates to the recognition task (as opposed to transmission) requires data (not information) to be thrown away. In other words, to gather information you must first throw away data, the more the better. So, what is “lossy” for image compression or data transmission is not lossy for recognition, and in general for understanding images. This seems at first to defy any notion of traditional information theory and decision theory, for it involves multiple intermediate decisions. We hope that our arguments have convinced the reader that this is not the case.
Some of the statements made in this manuscript may seem controversial. Certainly I do not wish to imply that individual organisms that do not exhibit visual recognition (e.g. blind people) do not have intelligence. Nor do I imply that every organism that has a visual system exhibits intelligent behavior. What I have argued is that organisms and species that need efficient visual recognition (limitations on the classifier to maximize computational efficiency at decision time) benefit from signal analysis (and therefore symbolic manipulation, internal representation etc.)
It is interesting to speculate whether there are organisms that have vision, and that use vision for regression or control tasks (e.g. visual navigation) but not to perform decisions (e.g. visual recognition). For instance, it is interesting to speculate whether the fly navigates optically, but decides olfactorily.In a personal communication, Steve Zucker remarked that the fly does not exhibit long-range lateral interactions, and yet it is known to use vision for navigation, and have strong olfactory system to guide actions. To this end, there is evidence that the fly lacks the wide-ranging lateral connections exhibited in higher mammals. Marr’s account on the fly’s visual system (and the so-called “representation” that it implies, page 34 of ) really describes a collection of analog input-output maps, or collection of sensing-action maps, with a simple decision switch, with no need for an internal representation. Wiener points out that
“complicated as the behavior patterns of birds are – in flying, in courtship, in the care of the young, and in nest building – they are carried out correctly on the very first time without the need of any large amount of instruction from the mother.”
He uses this argument in support of phylogenic (species, as opposed to ontogenic, or individual) learning, and speaks in favor of endowed input-output maps without an underlying internal representation that is easily manipulated. A contrarian view on the topic is supported by experiments in the development of an individual organism’s vision system in the absence of mobility .
Because mobility plays such an important role in this manuscript, it naturally relates to visual navigation and robotic localization and planning . In particular, propose “information-based” strategies, although by “information” they mean localization and mapping uncertainty based on range data. Range data are not subject to illumination and viewpoint nuisances, which are suppressed by the active sensing, i.e. by flooding the space with a known probing signal (e.g. laser light or radio waves) and measuring the return. There is a significant literature on vision-based navigation that is relevant to occlusion-driven navigation . In most of the literature, stereo or motion are exploited to provide a three-dimensional map of the environment, which is then handed off to a path planner, separating the photometric from the geometric and topological aspect of the problem. This separation is unnecessary, as the regions that are most informative are occlusions, where stereo provides no disparity. Another stream of related work is that on Saliency and Visual Attention , although there the focus is on navigating the image, whereas we are interested in navigating the scene, based on image data. In a nutshell, robotic navigation literature is “all scene and no image,” the visual attention literature is “all image, and no scene.” The gap can be bridged by going “from image to scene, and vice-versa” in the process of visual exploration (Chapter 8). The relationship between visual incentives and spatial exploration has been a subject of interest in psychology for a while .
This work also relates on visual recognition, by integrating structures of various dimensions into a unified representation that can, in principle, be exploited for recognition. In this sense, it presents an alternative to , that could also be used to compute Actionable Information. However, the rendition of the “primal sketch” in does not guarantee that the construction is “lossless” with respect to any particular task, because there is no underlying task guiding the construction. This work also relates to the vast literature on segmentation, particularly texture-structure transitions . Alternative approaches to this task could be specified in terms of sparse coding and non-local filtering . This paper also relates to the literature of ocular motion, and in particular saccadic motion. The human eye has non-uniform resolution, which affects motion strategies in ways that are not tailored to engineering systems with uniform resolution. One could design systems with non-uniform resolution, but mimicking the human visual system is not our goal.
Our work also relates to other attempts to formalize “information” including the concept of Information Bottleneck, , and our approach can be understood as a special case tailored to the statistics and invariance classes of interest, that are task-specific, sensor-specific, and control authority-specific. These ideas can be seen as seeds of a theory of “Controlled Sensing” that generalizes Active Vision to different modalities whereby the purpose of the control is to counteract the effect of nuisances. This is different than Active Sensing, that usually entails broadcasting a known or structured probing signal into the environment. Our work also relates to attempts to define a notion of information in statistics , economics and in other areas of image analysis and signal processing . Our particular approach to defining the underlying representational structure relates to the work of Guillemin and Golubitsky .
Last, but not least, our work relates to Active Vision , and to the “value of information” . The specific illustration of the experiment to the sub-literature on next-best-view selection . Although this area was popular in the eighties and nineties, it has so far not yielded usable notions of information that can be transposed to other visual inference problems, such as recognition and 3D reconstruction. A notable exception is the application of active vision to the automotive environment, pioneered by Dickmanns and co-workers .
Similarly to previously cited work , propose using the decrease of uncertainty as a criterion to select camera parameters, and uses information-theoretic notions to evaluate the “informative content” of laser range measurements depending on their viewpoint. Other influential literature on the relation between sensing and action include .
This manuscript of course also relates to data compression, in particular video compression, but not in the traditional sense, where the goal is to reconstruct a copy of the signal on the other side of the channel, but where the goal is to transmit a compressed representation that is to be used for decision or control tasks.
Bibliography
Appendix A Background material
Some of the concepts discussed in this manuscript use concepts from differential geometry, including the notions of group, orbit space, equivalence classes, quotients and homogeneous spaces. A good introduction to this material is . While an expository review of differential geometry is beyond the scope of this appendix, most of the concepts treated in this manuscript can be understood after going through Appendix A of , on pages 403–433 (skipping Section 1.3). Some of that material, specifically relating to the Lie groups and , and their corresponding Lie algebra , can also be found in Chapter 3 of . Our notation in this manuscript is consistent with, and in fact derived from, both and .
A.2 Basic topology (by Ganesh Sundaramoorthi)
In this appendix we describe some basic notions of topology that are useful to follow the orange-colored sections of the manuscript. We have privileged simplicity to rigor, so some of the statements made are imprecise and others are not fully developed. The interested reader can consult a differential topology book for details and clarifications.
A critical point is a local minimum if such that for such that .
A critical point is a local maximum if such that for such that .
A critical point is a saddle if it is neither a local minimum or local maximum.
A Morse function is a function such that all critical points are non-degenerate, i.e., if is a critical point, then .
By Taylor’s Theorem, we see that Morse functions are well approximated by quadratic forms around critical points:
provided that (if not, set to ). In particular, this means that Morse functions have isolated critical points.
The previous Remark, leads to the following observation:
Morse originally used the previous theorem as the definition of Morse functions. This way, a Morse function does not need to be differentiable.
A.2.2 Examples of Morse/non-Morse Functions
Examples of Morse/Non-Morse functions are the following:
Obviously, and are Morse Functions.
is not a Morse function (degenerate critical point).
A monkey saddle, i.e., :
is not a Morse function (degenerate; level sets of saddle must cross at an ‘X’).
All non-smooth functions are not Morse functions, e.g. images that have edges!
Functions that have co-dimension one critical sets (e.g. ridges and valleys) are not Morse functions. Such critical sets are commonplace in images!
A.2.3 Morse Functions are (Almost) all Functions
Morse functions seems to be a very restricted class of functions from the previous examples, however, a basic result from Morse Theory says otherwise.
Let denote a norm on a topological space . A set is dense if , i.e., for every and , there exists such that .
Let denote the norm on the space of functions, i.e.,
Then Morse functions form an open, dense subset of functions.
By the previous theorem, any smooth () function can be well approximated by a Morse function up to arbitrary precision (defined by ). For example, ridges and valleys can be approximated with a Morse function, e.g. consider the following circular ridge that can be made Morse by a slight tilt. Let which is a ridge and non-Morse:
Now consider the function , which is arbitrarily close to (in norm) and is a Morse function:
It is a basic fact that functions under the norm above are dense in all square integrable functions () functions. Therefore, even non-smooth functions can be approximated to arbitrary precision by Morse functions.
A.2.4 Reeb Graph
Let be a set. An equivalence relation on denoted is a binary relation with the following properties: for all :
(transitivity) if and , then
We denote by all elements of related to , e.g. .
A topology denoted on a set is a collection of subsets of (called open sets) such that the following properties hold:
for where is an index set (perhaps uncountable), we have .
for where is a finite index set, we have .
Let be a topological space. Let denote an equivalence relation on . The quotient space of under the equivalence relation , denoted is the topological space whose elements are
and whose topology is induced from . The quotient map is the (continuous) function defined by .
The Reeb graph of the function , denoted , is the topological space .
The Reeb graph of a function is the set of connected components of level sets of (with the additional information of the function value of each level set).
A.2.5 Examples
We will depict the Reeb graph in the following way: an element will be represented by a point in the plane, and if then the -coordinate of will be larger than .
A.2.6 Properties of Reeb Graphs
Both of these results follow from basic results in topology, namely, that connectedness and contractibility of loops are preserved under quotienting. That is, since is connected and loops in are contractible (so long as is continuous), we have that must also have these properties.
Let be a graph ( is the vertex set and is the edge set), and be a set (called the label set). Let be a function (called the attribute function). We define the attributed graph as .
Let be the set of critical points of . Define to be
Let be a graph, and , then the degree of a vertex, , is the number of edges that contain .
where is the number of maxima, the number of saddles and the number of minima
If and is a local minimum/maximum, then
If and is a saddle, then
Using the fact that for any tree , we have that and Property 2, we can conclude by simple algebraic manipulation that for a saddle.
A.2.7 Diffeomorphisms and the Attributed Reeb Tree
Note that if is a critical point of , then is a critical point of :
Therefore the vertex set in the ART of both and are equivalent. Moreover, if is a continuous path in then is a continuous path in , as diffeomorphisms do not break continuous paths. Therefore, the edge sets in the ART of and are equivalent.
By Morse Lemma, we can construct diffeomorphisms around critical points, the idea is then to “stitch” these diffeomorphisms up with “patches” to form the diffeomorphism of interest.
acts on if each is also such that
For each and , .
For the identity element , we have for all .
If acts on , then the orbit of a point is .
Define an equivalence relation in by if there exists such that . The orbit space (or the quotient of the action ) is the set .
acts on through the action : for , , and .
The orbit space where is the set of trees whose vertices have degree 1 or 3.
The second result above is simply a restatement of the Theorems above. Indeed, we can define the mapping by
The function above is well-defined since by Theorem 14, any representative will have the same Attributed Reeb Tree. Note
Theorem 15 states that is injective.
Theorem 16 states that is surjective.
Therefore, is a bijection and therefore, .
A.3 Radiometry primer (by Paolo Favaro)
where we have defined and the inner product at the denominator is called foreshortening. Similarly, the solid angle shines a patch of the surface . The two are related by
where . Substituting the expressions of and in the previous two equations into (A.2), one obtains the infinitesimal power received at the point .
Now, we want to write the portion of power exiting the surface at in the direction of a pixel through an area element . First, we need to write the direction of in the local reference frame at . We assume that is a unit vector, obtained for instance via central perspective projection
However, the point is written in the inertial frame, while is written in the frame of the camera at time . We need to first transform to the inertial frame, via , and then express this in the local frame at , which yields . We call the normalized version of this vector . Then, we need to integrate the infinitesimal power radiated from all points on the light source through their solid angle against the BRDFThe following equation, which specifies that the scene radiance is a linear transformation of the scene radiance via the BRDF is merely a model, and not something that can be proven. Indeed this equation is often used to define the BRDF., which specifies what portion of the incoming power is reflected towards . This yields the infinitesimal energy that radiates in the direction of through an area element :
Since the norm is invariant to Euclidean transformations, we can write it as . Now, if the size of the scene is small compared to its distance to the light, this term is almost constant, and therefore the measure
can be thought of as a property of the light source. Since we cannot untangle the contribution of from that of , we just choose to describe the power distribution radiated by the light source. Therefore, we have
This is the portion of power per unit area and unit solid angle radiated from a point on a reflective surface towards a point on the image at time . The next step consists of quantifying what portion of this energy gets absorbed by the pixel at location . This follows a similar calculation, which we do not report here, and instead refer the reader to (page 208). There, it is argued that the irradiance at the pixel is equal to the radiance at the corresponding point on the scene, up to an approximately constant factor, which we lump into . The point and its projection onto the image plane at time are related by the equations
After we substitute the expression of the radiance (A.9), we have the imaging equation, which we describe in Section B.1, Equation (B.7).
Appendix B
This section spells out the conditions under which the Ambient-Lambert-Static model is a reasonable approximation of the image formation process.
B.1.2 What is the “scene”…
To make the notation more precise, we define a local (Euclidean) reference frame, centered at the point with the third axis along the normal to the surface, and first two axes parallel to the tangent plane.
We call such a local reference frame , which is described in homogeneous coordinates by
where , and are unit vectors. Therefore, a point in the inertial reference frame will transform to in the local frame at . Similarly, a vector in the inertial frame will transform to in the local frame where
describes the photometry of the scene (reflectance and illumination). Note that depends on the point on the surface, and we are imposing no restrictions on such a dependency. For instance, we do not assume that is constant with respect to (homogeneous material). When emphasizing such a dependency we write .
In addition, reflectance (BRDF) and geometry (shape and pose) are properties of each object that can change over time. So, in principle, we would want to allow to be functions of time. In practice, we assume that the material of each object does not change, but only its shape, pose and of course illumination. Therefore, we will use
Note that by assuming that the world is made of surfaces we are already imposing significant restrictions, and we are implicitly choosing a level of granularity for our representation. Consider for instance the fabric shown in Figure B.2. There is no surface there. The fabric is made of thin one-dimensional threads, just woven tightly enough to give the impression of spatial continuity. Therefore, we choose to represent them as a smooth surface. Of course, the variation in the appearance due to the fine-scale structure of the threads has to be captured somehow, and we delegate this task to the reflectance model. Naturally, one could even describe each individual thread as a cylindrical surface modeled as an object , but this is well beyond the level of detail that we want to capture. This example illustrates the fact that describing objects entails a notion of scale. Something (e.g. a thread) is an object at one scale, but is merely part of a texture at a coarser scale. Figure B.2 highlights the modeling tradeoff between shape and reflectance: one could model the fabric as a very complex object (woven thread) made of homogeneous material (wool), or as a relatively simple object (a smooth surface) made of textured material. Although physically different, these two scenarios are phenomenologically indistinguishable, which relates to the discussion earlier in the manuscript of the role between the light field and the complete representation.
As we have already noted, instead of allowing the surface to deform arbitrarily in time via , and moving rigidly in space via , we can lump the motion and deformation into by allowing it to belong to a more general class of deformations , for instance diffeomorphisms, and let be constant. Alternatively, we can lump the deformation into and just describe the surface in the inertial reference frame via . This can be done with no loss of generality, and it reflects a fundamental tradeoff in modeling the interplay between shape and motion .
Now, if we agree that a scene can be described by its geometry, photometry and dynamics, we must decide how these relate to the measured images.
B.1.3 And how are the two related?
Given a description of the geometry, photometry and dynamics of a scene, a model of the image is obtained through a description of the imaging device. An imaging device is a series of elements designed to control light propagation. This is typically modeled through diffraction, reflection, and refraction. We ignore the first two, and only consider the effects of refraction. For simplicity, we can also assume that the set of objects that act as light sources and those that act as light sinks are disjoint, so that , i.e. we ignore inter-reflections. Note that needs not be simply connected, so we can divide simply connected regions of the scene into “light” and “objects” .
Now, using the notation introduced in the previous section, we want to determine the energy that impinges on a given pixel as a function of the shape of the scene , its BRDF , the light source and its energy distribution , and the position and orientation of the camera. For simplicity, given the tradeoff between shape and motion discussed in Remark 26, we describe the (possibly time-varying) shape of the scene in the inertial frame and drop the explicit description of its pose. In fact, to further simplify the notation, we can choose the inertial frame to coincide with the position and orientation of the viewer at time , so that if is the first image, then the scene can be described as a surface parameterized by : . We then describe the position and orientation of the camera at time relative to the camera at time using a moving Euclidean reference frame . Following the derivation in Appendix A.3, the intensity (irradiance) measured at a pixel on the image indexed by is given by
where the symbols above are defined as follows:
In the equation above, we have defined , and are defined by Equation (B.3) and (B.4) respectively, and indicates the (normalized) direction from to , and similarly for ;
relative motion between the scene and the camera is described by the motion of the camera and possibly the action of a more complex group , or simply by allowing the surface to change over time.
One should also add to the equation two characteristic function terms: outside the integral, which models the visibility of the scene from the pixel , and inside the integral to model the visibility of the light source from a scene point (cast shadows). We are omitting these terms here for simplicity. However, in some cases that we discuss in the next section, discontinuities due to visibility or cast shadows can be the only source of visual information.
One could argue that the real world cannot be captured by simple mathematical models of the type just described, and even classical physics is largely inadequate for the task. However, we are not looking for an absolute model. Instead, we are looking to describe the scene at the level of granularity that is suitable for us to be able to perform inference and accomplish certain tasks. So, what is the “right” granularity? For us a suitable model of the scene is one that can be validated with other existing sensing modalities, for instance touch. This is well illustrated by the fabric of Figure B.2, where at the level of granularity required the scene can be safely described as a smooth surface. Notice that this is similar to what other researchers have suggested by describing the scene as a functional that cannot be directly measured. However, such a functional can be evaluated with various test-functions. Physical instruments provide a set of test functions, and imaging device provide yet another set of test functions. The goal of the imaging model, therefore, can be thought of as relating the value of the scene functional obtained by probing with physical instruments to the value obtained by probing with images.
Note that this model does not explicitly include occlusions and shadows. Also, note that the first (diffuse) term does not depend on the viewpoint , whereas the second term (specular) does. However, note that, depending on the coefficient , the second term is only relevant when is close to the specular direction and, therefore, if one assumes that the light sources are concentrated, the second term is relevant in a small subset of the scene. If we threshold the effects of the second term based on the angle between the viewing and the specular direction, then we can write the above model as
where \hat{i}=\arg\min_{i}\frac{\big{\langle}g_{t}^{-1}{x}+L_{i}/\|L_{i}\|,N_{p}\big{\rangle}^{c}}{\langle g_{t}^{-1}{x},N_{p}\rangle} which justifies the rank-based model of . Empirical evaluation of the validity of this model, and the resulting “brightness constancy constraint,” discussed in the next subsection, has not been thoroughly addressed in the literature.
The “identity” of a scene or an object is specified by its shape and its reflectance properties . The illumination , visibility and pose/deformation are “nuisance factors” that affect the measurements but not the identity of the scene/objectDepending on the problem at hand, some unknowns may play either role: motion, for instance, could be a quantity of interest in tracking, but it is a nuisance in recognition. Illumination will almost always be a nuisance.. They change with the view, whereas the identity of the object does not. In the imaging equation (B.8) we measure for all and , and the unknowns are , which for simplicity we indicate as respectively, for all . For simplicity, we indicate all the unknowns of interest with the symbol (note that some unknowns are infinite-dimensional), and all the nuisance variables with . Equation (B.8), once we write the coordinates of the point relative to the pixel in the moving frame, , can then be written as a functional , formally, as follows:Note that the symbol for “nuisance” in the symbolic equation may be confused with , the normal to the surface in the physical model. Since the two symbols will be used exclusively in different contexts, it should be clear which one we are referring to.
∑ where, to summarize the equivalence of (B.10) with (B.8), we have
where is a subset of measure zero (the set of discontinuities), denotes functions of bounded variation. We will use the symbolic notation of (B.10) and the explicit notation of (B.8) interchangeably, depending on convenience. In some cases we may indicate the arguments of the functions explicitly.
Occlusions are an accident of image formation that significantly complicates our modeling efforts. In fact, while they are “nuisances” in the sense that they do not depend solely on the scene, the do depend on both the scene and the viewpoint (for occlusions) and illumination (for cast shadows). That is why, despite depending on the nuisance, under suitable conditions they can be exploited to infer the shape of the scene (see for occlusions and for cast shadows). For the case of illumination, as we will show, there is no loss of generality in assuming ambient + point-light illumination, at which point cast shadows are simple to model as a selection process of what sources are visible from each point. Nevertheless, it is a global inference problem that requires a global solution.
B.2 Special cases of the imaging equation and their role in visual reconstruction (taxonomy)
In its general formulation above, the imaging equation cannot be inverted. Therefore, it is common to make assumptions on some of the unknowns in order to recover the others. In this section we aim at enumerating a collection of special cases that compounded characterize most of what can be done in visual inference. We start with models of reflection.
Many common materials can be fruitfully described by a BRDF. Exceptions include translucent materials (e.g. skin), anisotropic material (e.g. brushed aluminum), micro-structured material (e.g. hair) etc. However, since our goal is not realism in a physical simulation, we are content with some common BRDF that are well established in computer graphics: Phong (corrected) , Ward and Torrance-Sparrow (simplified) .
.
As Nayar and coworkers point out , the radiance for the latter model can be written as the sum of products, where the first factor depends solely on material (diffuse and specular albedo), whereas the second factor compounds shape, pose and illumination.
In all these cases, is an unknown function called (diffuse) albedo, and is an unknown function called specular albedo. Diffuse albedo is often called just albedo, or, improperly, texture.
Note that the first term (diffuse reflectance) is the same in all three models. The second term (specular reflectance) is different. Surfaces whose reflectance is captured by the first term are called Lambertian, and are by far the most studied in computer vision.
In this case we have and . We consider two simple light source models first.
Due to the symmetry of the light source, assuming there are no shadows and having a full sphere, we can always change the global reference frame so that . However, it is only to first approximation (for convex objects) that the integral does not depend on , i.e. we can neglect vignetting. In this case, can be lumped into , yielding the simplest possible model that, when written with respect to a moving camera, gives
Note that this model effectively neglects illumination, for one can think of a scene that is self-luminous, and radiates an equal amount of energy in all directions. Even for such a simple model, however, performing visual inference is non-trivial. It has been done for a number of special cases:
When is constant, the only information in Equation (B.13) is at the discontinuities between and , i.e. at the occluding boundaries. Given suitable conditions, that have been first studied by Aström et al. , motion and shape can be recovered. The reconstruction of shape and albedo has been addressed in an infinite-dimensional optimization framework by Yezzi and Soatto in their work on stereoscopic segmentation.
The stereoscopic segmentation framework has been extended to allow the albedo to be smooth, rather than constant. The algorithm in provides an estimate of the shape of the scene as well as its albedo given its motion relative to the viewer, .
The same framework has been recently extended to allow the albedo to be piecewise constant in . This amount to performing region-based segmentation a’ la Mumford-Shah on the scene surface . Although it has not been done yet, the same ideas could be extended to piecewise smooth albedo.
When everywhere in , the image formation model can be bypassed altogether, leading to the so-called correspondence problem which we will see shortly. This is at the base of most traditional stereo reconstruction algorithms and structure from motion. Since these techniques apply without regard to the illumination, we will address this after having relaxed our assumptions on illumination.
Note that, if we neglect occlusions and cast shadows,Cast shadows for the case of point light sources is simply modeled as a selection process to determine which source is visible from which point. the sum can be taken inside the inner product and therefore there is no loss of generality in assuming that there is only one light source. If the light sources are at infinity, can be dropped from the inner product; furthermore, the intensity of the source multiplies the light direction, so the two can be lumped into the vector . We can therefore further simplify the above model to yield, taking into account camera motion,
Inference from this model has been addressed for the following cases.
Yuille et al. have shown that given enough viewpoints and lighting positions one can reconstruct the shape of the scene. Jin et al. have proposed an algorithm for doing so, which estimates shape, albedo and position of the light source in a variational optimization framework. If the position of the light source is known and there is no camera motion, this problem reduces to classical shape from shading .
In this case, one can easily show that albedo and light source cannot be recovered since there are always combinations of the two that generate the same images. However, under suitable conditions shape can still be estimated, as we discuss next.
If the combination of albedo and the cosine term (the inner product in (B.15)) result in a radiance function that has non-zero gradient, we can think of the radiance as an albedo under ambient illumination, and therefore this case reduces to multi-view stereo, which we will discuss shortly. Naturally, in this case we cannot disentangle reflectance from illumination, but under suitable conditions we can still reconstruct the shape of the scene, as we discuss shortly in the context of the correspondence problem.
If the visibility terms are included, under suitable conditions about the shape of the object and the number and nature of light sources, one can reconstruct an approximation of the shape of the scene.
Given a scene viewed under distant illumination, with no self-reflections, there is no loss of generality in assuming that the light source consists in an ambient (constant) illumination term and a number of point-light sources located at each emitting energy with intensity .
Given these considerations, we restrict our attentions to illumination models that consist of the sum of a constant ambient term and a countable number of point light sources. The general case, therefore, reduces to the special cases seen above:
Note that the energy does not depend on the direction, since for distant lights (sphere of infinite radius) all directions pointing towards the scene are normal to .
An alternative to using Gaussians is to use simple functions defined on a tiling of the sphere. For such functions to be translation-invariants, however, the sphere would have to be tiled in regular subdivisions, and this is known to be impossible, as it would entail the existence of regular polygons with an arbitrary number of faces. The same holds for discrete approximations of wavelets on the sphere.
Consider an image generated by a model (B.9). We are interested in modeling the variability induced in two images of the same scene under different illumination. We will assume that illumination can be approximated by an ambient term and a concentrated point source with intensity located at , so that each image can be approximated by where the latter term lumps together the effects of non-Lambertian reflection. This neglects vignetting (eq. (B.12)). The relationship between two images, the, can be obtained by eliminating the diffuse reflection , so as to obtain
Now, if the scene is a plane, then the first fraction on the right hand side does not depend on , i.e. it is a constant, say . The second and third term depend on if the scene is non-Lambertian. However, if non-Lambertian effects are negligible (i.e. away from the specular lobe), or altogether absent like in our assumptions, then the second term can also be approximated by a constant, say . Furthermore, for the case of a plane and are related by a homography, where and are intended in homogeneous coordinates. Therefore, the relationship between the two images can be expressed as
One can therefore think of one of the images (e.g. ) as the scene, and the images are obtained by a warping of the domain and a scaling and offset of the range. All the nuisances, are invertible, and therefore a planar Lambertian scene one can construct a complete invariant descriptor.
If the radiance of the scene is not constant, under suitable conditions one can do away with the image formation model altogether. Consider in fact the irradiance equation (A.11). Under the Lambertian assumption, given (at least) two viewpoints, indexed by and , we have that
without regard to how the radiance comes to existence. The relationship between and depends solely on the shape of the scene and the relative motion of the camera between the two time instants, :
Therefore, one can forget about how the images are generated, and simply look for the function that satisfies (substitute the last equation into the previous one)
Finding the function from the above equation is known as the correspondence problem, and the equation above is the brightness constancy constraint.
More recently, Faugeras and Keriven have cast the problem of stereo reconstruction in an infinite-dimensional optimization framework, where the equation above is integrated over the entire image, rather than just in a neighborhood of feature points, and the correspondence function is estimated implicitly by estimating the shape of the scene , with a given motion . This works even if is constant, but due to a non-uniform light and the presence of the Lambertian cosine term (the inner product in equation (B.15)) the radiance of the surface is nowhere constant (shading effect, or attached shadow) and even in the case of cast shadows, if the light does not move. In the presence of regions of constant radiance, the algorithm interpolates in ways that depend upon the regularization term used in the infinite-dimensional optimization (see for more details).
When the viewpoint is fixed, but the light changes, inverting the model above is known as photometric stereo . If the light configuration is not known and is allowed to change between views, Belhumeur and coworkers have shown that this problem cannot be solved . In particular, given two images one can pick a surface at will, and construct two light distributions that generate the given images, even if the scene is known to be Lambertian. However, this result relies on the presence of a single point light source. We conjecture that if the illumination is allowed to contain an ambient term, these results do not apply, and therefore reconstruction could be achieved. Note that psychophysical experiments suggest that face recognition is extremely hard for humans under a point light source, whereas a more complex illumination term greatly facilitates the task.
B.2.2 Non-Lambertian reflection
In this subsection we relax the assumption on reflectance. While, contrary to intuition, a more complex reflectance model can in some cases facilitate recognition, in general it is not possible to disentangle the effects of shape, reflectance and illumination. We start by making assumptions that follow the taxonomy used for the Lambertian case in the previous subsection.
In the presence of ambient illumination, the specular term of an empirical reflection model, for instance Phong’s, takes the form
In the presence of point light sources, the specular component of the Phong models becomes
where the arguments of the inner products are normalized. In this case, assuming that a portion of the scene is Lambertian and therefore motion and shape can be recovered, one can invert the equation above to estimate the position and intensity of the light sources. This is called “inverse global illumination” and was addressed by Yu and Malik . If the scene is dominantly specular, so no correspondence can be established from image to image, we are not aware of any general result that describes under what condition shape, motion and illumination can be recovered. Savarese and Perona study the case when assumptions on the position and density of the light, such as the presence of straight edges at known position, can be exploited to recover shape.
In general, one cannot separate reflectance properties of the scene with distribution properties of the light sources. Jin et al. showed that one can recover shape as well as the radiance of the scene, which mixes the effects of reflectance and illumination.
In the presence of multiple point light sources, Many have studied the conditions under which one can recover the position and intensity of the light sources, see for instance and references therein. Variations of photometric stereo have also been developed for this case, starting from .
Zickler et al. have developed techniques to exploit a very peculiar imaging setup where a point light source and the camera are switched in pairs of images, which allows us to eliminate the BRDF from the imaging equation.
B.3 Analysis of the ambiguities
The optimal design of invariant feature requires an analysis of the ambiguities in shape, motion (deformation), reflectance and illumination. While special cases of this analysis have been presented in the past, especially in the field of reconstruction (shape/motion , reflectance/illumination , shape/reflectance , exemplified below), to this date there is no comprehensive analysis of the ambiguities in shape, motion, reflectance and illumination.
We note that, instead of allowing the surface to deform arbitrarily in time via , and moving rigidly in space via , we can lump the motion and deformation into by allowing it to belong to a more general class of deformations , for instance diffeomorphisms, and let be constant. Alternatively, we can lump the deformation into and just describe the surface in the inertial reference frame via . This can be done with no loss of generality, and it reflects a fundamental tradeoff in modeling the interplay between shape and motion .
The reflectance/illumination ambiguity has been addressed in Section B.2.1. Given the conclusions reached there, we restrict our attention to illumination models that consist of the sum of a constant ambient term and a countable number of point light sources.
Even under these restrictive modeling assumption, it can be shown that illumination-invariant statistics do not exist.
There exists no discriminative illumination invariant for illumination under the Lambert-Ambient model.
This theorem was first proved by Chen et al. in (although also see , as cited by Zhou, Chellappa and Jacobs in ECCV 2004). Here we give a simplified proof that does not involved partial differential equations, but just simple linear algebra. We refer to the model (B.8) where we restrict the scene to be Lambertian, : If illumination invariants do not exist for Lambertian scenes, they obviously do not exist for more general reflectance models. Also, we neglect the effects of occlusions and cast shadows: If an illumination invariant does not exist without cast shadows, it obviously does not exist in the presence of cast shadows, since these are generated by the illumination. We neglect occlusions in the sense that we consider equivalent all scenes that are equal in their visible range.
In a series of recent papers , Yuille and coworkers have shown that for Lambertian objects viewed under point light sources from an arbitrary viewpoint there is an important class of ambiguities for 3-D reconstruction. According to , given a certain scene, seen from a collection of viewpoints under a certain light configuration, there exists a different scene, a different collection of viewpoints and a different light configuration that generates exactly the same images, and therefore from these it is not possible to reconstruct the scene geometry (shape), photometry (albedo, illumination), and dynamics (viewpoints) uniquely. In particular, equivalent scenes are characterized by a global affine transformation of the surface normals, the viewpoints, and the lighting configuration.
Yuille’s results pertain to a Lambertian scene viewed under ideal point light sources from a weak perspective (affine) camera. In , however, it is argued that a more realistic model of illumination in real-world scenes is not a collection of point sources, but an ambient illumination term, which captures the collective effect of mutual illumination, and a collection of isolated sources. Here we show that, under this illumination model, the KGBR ambiguity described in disappears, and one is left with the usual projective reconstruction ambiguity well-known in structure-from-motion . Note that Kriegman and co-workers showed that mutual illumination causes the KGBR to disappear (CVPR 2005).
To introduce the problem, we follow the notation of , where the basic model of image formation for a Lambertian scene is given by
In the presence of multiple viewpoints the different images are obtained from the imaging equation by the correspondence equation that establishes the relationship between and :
Let a collection of image of a scene with surface , albedo , viewed under an ambient illumination and a number of point light sources , be given: . The only other scene that generates the same images consists of a projective transformation of and the corresponding cameras . In the presence of calibrated cameras, the only ambiguity is a scale factor affecting and the translational component of .
from which it can be seen that and are indistinguishable from
From this equation one concludes that the ratio of the solid angles is a function of the tangent plane at , , which is not the case, hence the contradiction.
Appendix C Legenda
Symbols are defined in the order in which they are introduced in the text.
: Symbolic representation of the image formation process.
: symbolic representation of the “scene”. , the space of all possible scenes.
: Symbolic representation of the nuisances in the image formation process. They could represent viewpoint, contrast transformations, occlusions, quantization, sensor noise.
the space of contrast transformations.
: Noise process, including all unmodeled phenomena in the image formation process.
: Special Euclidean group of rigid body motions in three-dimensional Euclidean space.
Homogeneous coordinates \bar{x}=\left[\begin{array}[]{c}x\\ 1\end{array}\right].
: Pre-image of the pixel , the intersection of the projection ray with every surface on the scene.
: Pre-image of the pixel , the intersection of the projection ray with the closest point on the scene.
, : Rotational and translational component of the motion group , usually indicated with , or in homogeneous coordinates as a matrix \bar{G}=\left[\begin{array}[]{cc}R&T\\ 0&1\end{array}\right].
: the occluded domain, a subset of , that back-projects onto a portion of the scene that is visible from the current image, , but not from neighboring images or .
: Class label, without loss of generality assumed to be a positive integer, or simply for binary classification.
: a risk functional. Not to be confused with , a rotation matrix.
: Normal (Gaussian) density function.
, : Probability measures. When these are (Radon-Nikodym) differentiable with respect to the base measure, we have and where are probability density functions.
: A feature, i.e. any statistic, or deterministic function of the data.
: a complexity measure, for instance coding length, or algorithmic complexity, or entropy if the image is thought of as a distribution of pixels.
: A feature detector, a particular case of feature that serves to fix the value of a particular group element .
, : Expectation, expectation with respect to a probability measure, .
: Similarity operator, , denoting the existence of an equivalence relation, and belonging to the same equivalence class; also used to denote that an object is “sampled” from a probability distribution, .
: The estimate of an object, for instance is an estimate of .
: A characteristic function. For a set , if , and otherwise. Sometimes it is indicated by when the independent variable is clear from the context.
, : An open set (a “ball”) of radius centered at .
: A set, or a convolution kernel.
: The Jacobian determinant (the determinant of the derivative of a transformation).
: The input to a dynamical system, usually denoting a variable that is actively controlled and therefore known with high precision.
: The gradient of the image, consisting of two components and .
: Either a set, or a rotational velocity vector, depending on the context.
: The restriction of an image to a set.
: Either Dirac’s delta distribution, defined implicitly by and ; or Kronecker’s delta, if , and otherwise.
convolution operator. For two functions , .
: infinite-dimensional spaces of -integrable functions, for instance Lebesgue-measurable functions or square-integrable functions .
: The space where the average temporal signal lives, for use in Dynamic Time Warping.
: The composition operator to update a representation with the innovation. It would be a sum of all the elements involved were linear.