A notion of visual information is introduced as the complexity not of the raw images, but of the images after the effects of nuisance factors such as viewpoint and illumination are discounted. It is rooted in ideas of J. J. Gibson, and stands in contrast to traditional information as entropy or coding length of the data regardless of its use, and regardless of the nuisance factors affecting it. The non-invertibility of nuisances such as occlusion and quantization induces an "information gap" that can only be bridged by controlling the data acquisition process. Measuring visual information entails early vision operations, tailored to the structure of the nuisances so as to be "lossless" with respect to visual decision and control tasks (as opposed to data transmission and storage tasks implicit in traditional information theory). These ideas are illustrated on visual exploration, whereby a "Shannonian Explorer" navigates unaware of the structure of the physical space surrounding it, while a "Gibsonian Explorer" is guided by the topology of the environment, despite measuring only images of it, without performing 3D reconstruction. Our operational definition of visual information suggests desirable properties that a visual representation should possess to best accomplish vision-based decision and control tasks. This paper discusses the role visual perception plays in the "signal-to-symbol barrier" problem. The "signal-to-symbol barrier" stems from the observation that perceptual agents, from plants to humans, perform measurements of physical processes at a level of granularity that is essentially continuous. They also perform actions in the continuum of physical space. And yet, cognitive science, primary epistemics, and in general modern philosophy, associate "intelligent behavior" 1 The continuum is an abstraction, so here "continuous" is to be understood as existing at a level of granularity significantly finer than the resolution of the measurement device or actuator. For instance, although retinal photoreceptors are finite in number, we do not perceive discontinuities due to retinal sampling. Even when the sensory signals and the actions are discrete (e.g. due to digital encoders or transducers), the "analog-to-digital" conversion usually occurs in a manner that is independent of the signal being sampled (e.g. fixed-rate sampling), or dependent only on coarse phenomenological aspects of the signal (e.g. adaptive sampling based on frequency characteristics or sparsity constraints). 1 with some kind of internal representation consisting of discrete symbols ("concepts", "ideas", "objects", "categories") that can be manipulated with the tools of logic or probabilistic inference. But little is known about why such a "signal-to-symbol" conversion should occur, whether it would yield an evolutionary advantage, or what principles would guide such a discretization process. Traditional Information Theory, Statistical Decision Theory, and Control Theory shed little light on this process, and indeed suggest that it 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 Rao and Blackwell ([64] page 88) indicate that the best possible agents would avoid "breaking down the data into pieces," i.e. data analysis 2 , or for that matter any kind of intermediate decision unrelated to the final task, as would instead be necessary to have a discrete internal representation. So, why would we need, or 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 principle that guides it? And with respect to the academic field of Computer Vision, why have we been performing data analysis (edge detection, feature selection, segmentation, image parsing etc.) against the basic tenets of (traditional) Information and Decision Theory? The latter would suggest that, eventually, a reductionist approach where images are fed raw into a black-box decision or control machine will be most successful. Or perhaps, on the contrary, the traditional notion of Information should be revised, and this revision will point to new principles for data analysis, and validate what Computer Vision scientists have done for decades. Yet another possibility is that data analysis is not guided by any principle, but an accident due to the constraints imposed by biological hardware, as advocated by Turing in [73] , where he showed that reaction-diffusion partial differential equations (PDEs) that govern neuronal ion concentrations, although continuous in nature, exhibit discrete solutions. So, 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 is it better to jettison it? The question of representation is ill-posed outside the scope of a task. A task can be as narrow as a binary decision, such as the presence/absence of a person in a scene, or as general as "survival," but in the context of visual perception I distinguish four broad classes of tasks, which I call the 2 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 discrete semantic entities. This is not the case for global representations such as Fourier or wavelet decomposition, or principal component analysis (PCA), that are unfortunately often referred to as "analysis" because such techniques were developed in the context of harmonic analysis, a branch of mathematics. The Fourier transform is globally invertible, which implies that there is no loss of data, and PCA consists in linear projections onto subspaces. 3 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, and the best decision would still avoid data analysis. For instance, to simplify a segment of a radio signal one could represent it as a linear combination of a small number of (high-dimensional) bases, so few numbers (the coefficients) are sufficient to represent it in a parsimonious manner. This is different than breaking down the signal into pieces, e.g. partitioning its domain into subsets, as implicit in the process of encoding a visual signal through a population of neurons each with a finite receptive field. So, is there an evolutionary advantage in data analysis, beyond it being just a way to perform lossy data compression? 2 four "R's" of vision: Reconstruction (building models of the geometry of the scene), Rendering (building models of the photometry of the scene), Recognition (or, more in general, vision-based decisions such as detection, localization, categorization), and Regulation (or, more in general, vision-based control such as tracking, manipulation etc.). For Reconstruction and Rendering, I am not aware of any principle that suggests an advantage in data analysis. It is not accidental that the current best approaches to reconstruct models of the geometry and photometry of a scene from image streams recover (piecewise) continuous surfaces and radiance functions directly from the data, as opposed to the traditional multi-step pipeline 4 that was long favored on complexity grounds [52] . In this manuscript, I explore the issue of representation for decision and control tasks. I will try to avoid philosophical discourses and will not make an attempts 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, which one might call "information." So, the first step is understanding what "information" means in the context of visual perception. That is the subject of this manuscript. What I will show is that visual perception plays a key role in understanding the signal-tosymbol barrier. Specifically, the need to be able to perform decision and control tasks in a manner that is independent of nuisance factors that affect the image formation process leads to an internal representation that is intrinsically discrete, and yet lossless, in a sense to be made clear soon. However, for this to happen the perceptual agent has to have control over certain aspects of the sensing process. This ties together inextricably sensing and control, in the sense that without the ability to control the sensing process with motion, a discrete internal representation would be a sure loss. A peculiar illustration of this phenomenon is the case of Sea Squirts, or Tunicates, shown in Fig. 1 . These are organisms that possess a nervous system (ganglion cells) and the ability to move (they are predators), but eventually settle on a rock, become stationary and thence swallow their own brain. More than sixty years ago, Norbert Wiener stormed into his students' office enunciating "entropy is information!" before immediately storming out. Claude Shannon later made this idea the centerpiece of his Mathematical Theory of Communication, formalizing and unifying the wide variety of methods that practitioners had been using to transmit signals through channels. The influence of Shannon's communication theory has since spread beyond the transmission and compression of data, and is now broadly known as Information Theory. But is the entropy of the data really "information"? There is no doubt that the more complex the data, the more costly it is to store and transmit. But what if we want to use the data for tasks other than storage or transmission? What is the "information" that an image contains about the scene it portrays? What is the value of an image if we are to recognize objects in the scene, or navigate through it? (Fig. 2) . 4 A sequence of "steps" including point-feature selection, wide-baseline matching, epipolar geometry estimation, motion estimation, triangulation, epipolar rectification, dense re-matching, surface triangulation, mesh polishing, texture mapping. 6 It is only unfortunate that, in engineering communications, the signals are heavily structured so the nuisance, often dubbed "noise," is usually assumed to be additive, zero-mean, white, and Gaussian. As a consequence, the issue of invariance was never thoroughly explored, although, interestingly, Wiener was aware of it. In ([78], p. 50) he even introduced the first (integral) moment as an invariant statistic to a group (eq. (6.01), p. 138) and called it a gestalt! 7 He was nevertheless rooted in empirical epistemology and therefore assumed that information comes from data. 8 I use the word "nuisance" in the standard sense of statistical inference; this does not imply that nuisance factors are dismissed or irrelevant. It just means that they affect the data, but not the task.  4 have little to do with the decision (perception) and control (action) task at hand. So it is intuitive that the value of data should relate to its complexity only after the effects of nuisance factors has been discounted. 9 Unfortunately, any constant function is an "invariant underlying change", so Gibson was missing the other facet of information that relates to its "usefulness" (sufficiency) towards the task. The goal of this manuscript is to define an operational notion of "information" that is relevant to visual inference tasks, as opposed to the transmission and storage of image data. Following Gibson's lead, I define Actionable Information to be the complexity (coding length 10 ) of a maximal statistic that is invariant to the nuisances associated to a given task. According to this definition, the Actionable Information in an image depends not just on the complexity of the data, but also on the structure of the scene it portrays. I illustrate this on a simple environmental exploration task, that is central to Gibson's ecological approach to perception. A robot seeking to maximize Shannon's information (a "Shannonian Explorer") is drifting along unaware of the structure of the environment, while one seeking to maximize Actionable Information (a "Gibsonian Explorer") is driven by the topology of the surrounding space. Both measure the same data (images), but the second is using it to accomplish spatial tasks. This manuscript relates to work in information theory, video compression, robotics, visual recognition, as I discuss in Sect. 7. There, I also discuss the visual representations that our operative definition implies as "lossless" relative visual decision or control tasks. 9 Appealing as the idea of characterizing "invariants under change" sounds in words, a modern Computer Vision scientist would dismiss it at the outset, for it has since become known that such invariants do not exist. Invariants were considered "the Holy Grail of Computer Vision" in the eighties, until [14] and [20] showed that they do not exist neither for viewpoint, nor for illumination. Lacking mathematical and computational foundations that enable scientific (falsifiable) discourse and engineering applications, Gibson's ideas thus remain confined to the realm of philosophy [39] and perception psychology. However, recent developments have shown that the situation is more complex than commonly assumed: [14] refers to statistics of point features, not images, and [74] shows instead that non-trivial viewpoint invariants always exist for images of Lambertian objects of general shape. Similarly, [20] consider general illumination fields, but invariants can be constructed for simpler illumination models, such as contrast transformations [2] , even though these are valid only locally. Invariance always refers to an underlying model, that is as good as the assumptions it is based on, and as useful as the ensuing algorithms are for the task of interest. Invariance to even more restricted classes of transformations is the underpinning of very simple image statistics that have recently gained significant popularity in visual recognition and categorization tasks. 10 The relation to entropy [48] requires defining a distribution of coding lengths, as will be discussed later in this manuscript. 11 It could be argued that Shannon would not seek to maximize the entropy of the data, but instead the mutual information between the scene and the data (which he called "equivocation"). Our exercise can be thought of a way to formalize this notion, but avoiding having to place an explicit probability distribution on the set of scenes, which is a tall order. Furthermore, while it is easy to formally define the mutual information between the scene and the image, computing it for an erasure channel (occlusions) under compositional infinite-dimensional domain warpings (viewpoint changes) and multiplicative infinite-dimensional disturbances (illumination) is not something easily done using the tools developed in classical Information Theory. The paper is structured in the following way. • In the previous section, as a way of motivation, I have argued that traditional information theory, as developed with an eye towards the problem of "reproducing" the output of a source, is inadequate to characterize the value of an individual image for the purpose of decision or control tasks relative to the scene that the image portrays. Images are affected by "nuisance factors" that act on the data in a complex and highly structured fashion. Although closer to our scope, Gibson's notion of information as "invariants under change" falls short because it does not consider the counterpart of invariance, which is the "discriminative" (decision) or "reachable" (control) component of the representation. • In Sect. 4.1, I introduce the notion of "actionable information" as the complexity of the maximal statistic that is invariant to a given nuisance. Similarly, I define "complete information" as the minimal statistic that is sufficient for a given task. When the nuisance is "invertible", the two are identical, and their difference, the "actionable information gap" defined in Sect. 4.3, is zero. • In the context of vision, viewpoint and illumination -away from visibility artifacts such as occlusions and cast shadows -are invertible. However, occlusions, cast shadows and quantization are not. Therefore, in general, the actionable information gap is non-zero. • The invertibility of a nuisance depends on the control authority of the sensor. While occlusions and quantization are non-invertible for a passive and static observer, they become invertible when the observer is able to control the data acquisition process (Sect. 4.3) for instance by changing viewpoint or accommodation (Fig. 10) . Similarly, cast shadows are not invertible in grayscale images, but may become invertible when one can sample multiple spectral bands. The process of "information pickup" consists in the exploration of the environment aimed at closing the information gap (Sect. 4.4). • While complete information, in general, cannot be measured, actionable information can be computed. I describe a representational structure that organizes two-dimensional (region statistics), one-dimensional (boundaries) and zero-dimensional (attributed points) image characteristics at all scales; its coding length measures actionable information (Sect. 5). This is a conceptual construction. Nevertheless, a "poor man's version" of this construction can be easily and efficiently computed. • Since complete information, and therefore the actionable information gap, cannot be known in advance, perceptual exploration must proceed based on locally computable quantities. I define the "decrease in actionable information gap" as a quantity that can be computed 12 Indeed, it is infinite, for actionable information is zero (there is no occlusion-invariant in one image) and the complete information is infinity (to compute a sufficient statistic with respect to occlusion one would have to acquire the entire light field). 6 instantaneously (in the presence of infinitesimal motion) and argue that its integral during exploration converges to the complete information, assuming a bounded universe (Sect. 4.3). • Finally, in Sect. 7 I discuss some consequence of our arguments, including a suggested set of prescriptions that a visual representation should obey, and their effects on the "signal-tosymbol barrier." Before articulating our arguments, we need to introduce certain definitions, for which we need some notation. An image is represented as a function I : -integrable, but otherwise not necessarily continuous, taking positive values in k bands, e.g. k = 3 for color, and k = 1 for grayscale. A time-indexed image is indicated by I(x, t), t ∈ Z + , assuming a discrete temporal sampling, and a sequence is denoted by {I(x, t)} T t=1 , or simply {I}. The image relates to the scene, which is represented as a collection of piecewise continuous surfaces ("shape") S ⊂ R . This model is viable only away from visibility artifacts (occlusions, cast shadows), which is discussed in Sect. 3.2. All un-modeled phenomena (deviation from Lambertian reflection, complex illumination effects etc.) are lumped into an additive "noise" term n : R 2 → R k . We finally have our image formation model: I(x) = h(ρ(X)) + n(x) x = π(g(X)), X ∈ S. (1) Summary: (Refer to Fig. 3 ) I call the image I, the reflectance ρ, illumination (contrast) h, warping w, which depends on the shape S and the viewpoint g. I further call the scene ξ, the collection of (three-dimensional, 3D) shape and reflectance ξ . = {ρ, S}, and the nuisance ν, the collection of viewpoint and illumination ν . = {g, h}. In short-hand notation, substituting X in the first equation 7
In REF , Soatto introduces the notion of Actionable Information that is the portion of data that is useful towards the accomplishment of a task and after discounting nuisance factors.
Actionable Information in Vision
ICCV 2009
Computer Science