We introduce PolyCAT, a public eye-tracking dataset for studying visual attention on natural images viewed through irregular polygonal apertures. Thirty participants viewed 600 images from the CAT2000 dataset through 27 polygon shapes of varying geometric properties while their eye movements were recorded with an EyeLink 1000+ on a 27 ′′ 4K display at 70 cm viewing distance. PolyCAT provides sample-level gaze streams, fixation events, empirical saliency maps, scanpath sequences, and quality metrics. We report baseline saliency benchmarks and demonstrate that polygonal aperture geometry systematically affects fixation distributions, offering a controlled testbed for studying how viewing constraints modulate visual exploration.

This paper proposes the RePAIR dataset that represents a challenging benchmark to test modern computational and data driven methods for puzzle-solving and reassembly tasks. Our dataset has unique properties that are uncommon to current benchmarks for 2D and 3D puzzle solving. The fragments and fractures are realistic, caused by a collapse of a fresco during a World War II bombing at the Pompeii archaeological park. The fragments are also eroded and have missing pieces with irregular shapes and different dimensions, challenging further the reassembly algorithms. The dataset is multi-modal providing high resolution images with characteristic pictorial elements, detailed 3D scans of the fragments and meta-data annotated by the archaeologists. Ground truth has been generated through several years of unceasing fieldwork, including the excavation and cleaning of each fragment, followed by manual puzzle solving by archaeologists of a subset of approx. 1000 pieces among the 16000 available. After digitizing all the fragments in 3D, a benchmark was prepared to challenge current reassembly and puzzle-solving methods that often solve more simplistic synthetic scenarios. The tested baselines show that there clearly exists a gap to fill in solving this computationally complex problem.

Abstract Jigsaw puzzle solving, the problem of constructing a coherent whole from a set of non-overlapping unordered visual fragments, is fundamental to numerous applications, and yet most of the literature of the last two decades has focused thus far on less realistic puzzles whose pieces are identical squares. Here we formalize a new type of jigsaw puzzle where the pieces are general convex polygons generated by cutting through a global polygonal shape/image with an arbitrary number of straight cuts, a generation model inspired by the celebrated Lazy caterer’s sequence. We analyze the theoretical properties of such puzzles, including the inherent challenges in solving them once pieces are contaminated with geometrical noise. To cope with such difficulties and obtain tractable solutions, we abstract the problem as a multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process. We define evaluation metrics and present experimental results on both apictorial and pictorial puzzles to show that they are solvable completely automatically.

Jigsaw puzzle solving, the problem of constructing a coherent whole from a set of non-overlapping un-ordered fragments, is fundamental to numerous applications, and yet most of the literature has focused thus far on less realistic puzzles whose pieces are identical squares. Here we formalize a new type of jigsaw puzzle where the pieces are general convex polygons generated by cutting through a global polygonal shape with an arbitrary number of straight cuts. We analyze the theoretical properties of such puzzles, including the inherent challenges in solving them once pieces are contaminated with geometrical noise. To cope with such difficulties and obtain tractable solutions, we abstract the problem as a multi-body spring-mass dynamical sys-tem endowed with hierarchical loop constraints and a layered reconstruction process that is guided by the pictorial content of the pieces. We define evaluation metrics and present experimental results on both apictorial and pictorial puzzles to indicate that they are solvable completely automatically.

The recurring context in which objects appear holds valuable information that can be employed to predict their existence. This intuitive observation indeed led many researchers to endow appearance-based detectors with explicit reasoning about context. The underlying thesis suggests that stronger contextual relations would facilitate greater improvements in detection capacity. In practice, however, the observed improvement in many case is modest at best, and often only marginal. In this work we seek to improve our understanding of this phenomenon, in part by pursuing an opposite approach. Instead of attempting to improve detection scores by employing context, we treat the utility of context as an optimization problem: to what extent can detection scores be improved by considering context or any other kind of additional information? With this approach we explore the bounds on improvement by using contextual relations between objects and provide a tool for identifying the most helpful ones. We show that simple co-occurrence relations can often provide large gains, while in other cases a significant improvement is simply impossible or impractical with either co-occurrence or more precise spatial relations. To better understand these results we then analyze the ability of context to handle different types of false detections, revealing that tested contextual information cannot ameliorate localization errors, severely limiting its gains. These and additional insights further our understanding on where and why utilization of context for object detection succeeds and fails.

Reconstructing the missing parts of a curve has been the subject of much computational research, with applications in image inpainting, object synthesis, etc. Different approaches for solving that problem are typically based on processes that seek visually pleasing or perceptually plausible completions. In this work we focus on reconstructing the underlying physically likely shape by utilizing the global statistics of natural curves. More specifically, we develop a reconstruction model that seeks the mean physical curve for a given inducer configuration. This simple model is both straightforward to compute and it is receptive to diverse additional information, but it requires enough samples for all curve configurations, a practical requirement that limits its effective utilization. To address this practical issue we explore and exploit statistical geometrical properties of natural curves, and in particular, we show that in many cases the mean curve is scale invariant and oftentimes it is extensible. This, in turn, allows to boost the number of examples and thus the robustness of the statistics and its applicability. The reconstruction results are not only more physically plausible but they also lead to important insights on the reconstruction problem, including an elegant explanation why certain inducer configurations are more likely to yield consistent perceptual completions than others.

While recovery of hyperspectral signals from natural RGB images has been a recent subject of exploration, little to no consideration has been given to the camera response profiles used in the recovery process. In this paper we demonstrate that optimal selection of camera response filters may improve hyperspectral estimation accuracy by over 33%, emphasizing the importance of considering and selecting these response profiles wisely. Additionally, we present an evolutionary optimization methodology for optimal filter set selection from very large filter spaces, an approach that facilitates practical selection from families of customizable filters or filter optimization for multispectral cameras with more than 3 channels.

Visual curve completion, an early visual process that completes the occluded parts between observed boundary fragments (a.k.a. inducers), is a major problem in perceptual organization and a critical step toward higher level visual tasks in both biological and machine vision. Most computational contributions to solving this problem suggest desired perceptual properties that the completed contour should satisfy in the image plane, and then seek the mathematical curves that provide them. Alternatively, few studies (including by the authors) have suggested to frame the problem not in the image plane but rather in the unit tangent bundleR (2) × S(1), the space that abstracts the primary visual cortex, where curve completion allegedly occurs. Combining both schools, here we propose and develop a biologically plausible theory of elastica in the tangent bundle that provides not only perceptually superior completion results but also a rigorous computational prediction that inducer curvatures greatly affects the shape of the completed curve, as indeed indicated by human perception.

This paper addresses the problem of scene categorization while arguing that better and more accurate results can be obtained by endowing the computational process with perceptual relations between scene categories. We first describe a psychophysical paradigm that probes human scene categorization, extracts perceptual relations between scene categories, and suggests that these perceptual relations do not always conform the semantic structure between categories. We then incorporate the obtained perceptual findings into a computational classification scheme, which takes inter-class relationships into account to obtain better scene categorization regardless of the particular descriptors with which scenes are represented. We present such improved classification results using several popular descriptors, we discuss why the contribution of inter-class perceptual relations is particularly pronounced for under-sampled training sets, and we argue that this mechanism may explain the ability of the human visual system to perform well under similar conditions. Finally, we introduce an online experimental system for obtaining perceptual relations for large collections of scene categories.

We propose a theory for cortical representation and computation of visually completed curves that are generated by the visual system to fill in missing visual information (e.g., due to occlusions). Recent computational theories and physiological evidence suggest that although such curves do not correspond to explicit image evidence along their length, their construction emerges from corresponding activation patterns of orientation-selective cells in the primary visual cortex. Previous theoretical work modeled these patterns as least energetic 3D curves in the mathematical continuous space R2 × S1, which abstracts the mammalian striate cortex. Here we discuss the biological plausibility of this theory and present a neural architecture that implements it with locally connected parallel networks. Part of this contribution is also a first attempt to bridge the physiological literature on curve completion with the shape problem and a shape theory. We present completion simulations of our model in natural and synthetic scenes and discuss various observations and predictions that emerge from this theory in the context of curve completion.

Visual curve completion is a fundamental perceptual mechanism that completes the missing parts (e.g., due to occlusion) between observed contour fragments. Previous research into the shape of completed curves has generally followed an "axiomatic" approach, where desired perceptual/geometrical properties are first defined as axioms, followed by mathematical investigation into curves that satisfy them. However, determining psychophysically such desired properties is difficult and researchers still debate what they should be in the first place. Instead, here we exploit the observation that curve completion is an early visual process to formalize the problem in the unit tangent bundle R(2) × S(1), which abstracts the primary visual cortex (V1) and facilitates exploration of basic principles from which perceptual properties are later derived rather than imposed. Exploring here the elementary principle of least action in V1, we show how the problem becomes one of finding minimum-length admissible curves in R(2) × S(1). We formalize the problem in variational terms, we analyze it theoretically, and we formulate practical algorithms for the reconstruction of these completed curves. We then explore their induced visual properties vis-à-vis popular perceptual axioms and show how our theory predicts many perceptual properties reported in the corresponding perceptual literature. Finally, we demonstrate a variety of curve completions and report comparisons to psychophysical data and other completion models.

An image of a purely specular object is just a distortion of its surrounding illumination environment. Therefore, when only little (or nothing) about the illumination environment is known, inferring the geometrical structure of specular objects is a very challenging task. Nevertheless, recent studies have addressed this problem by exploiting relative motion between the observed object, the camera and the environment (e.g.,[1, 4]). In the image plane such motion induces a specular flow – the optical flow of observed specular reflections – which has been shown to be independent of environment content and therefore to facilitate shape reconstruction. The shape-from-specular-flow (SFSF) approach follows the intuitive hierarchical thinking: First, estimate the relevant (specular) flow in the image plane. Next, exploit it for (specular) shape recovery by solving the SFSF equation ([1]). The SFSF equation expresses the relationship between the specular flow, the shape of the specular object, and its motion relative to the environment. A linear form for the SFSF equation have been formulated in [4] assuming that the unknown specular object is represented via the field of its reflection vectors, r∈ S2. In this case the SFSF equation becomes ∂r(x) ∂x u(x) = ω× r(x), (1)

We explore a polar representation of optical flow in which each element of the brightness motion field is represented by its magnitude and orientation instead of its Cartesian projections. This seemingly small change in representation provides more direct access to the intrinsic structure of a flow field, and when used with existing variational inference procedures it provides a framework in which regularizers can be intuitively tailored for very different classes of motion. Our evaluations reveal that a flow estimation algorithm that is based on a polar representation can perform as well or better than the state-of-the-art when applied to traditional optical flow problems concerning camera or rigid scene motion, and at the same time, it facilitates both qualitative and quantitative improvements for non-traditional cases such as fluid flows and specular flows, whose structure is very different.

In the square jigsaw puzzle problem one is required to reconstruct the complete image from a set of non-overlapping, unordered, square puzzle parts. Here we propose a fully automatic solver for this problem, where unlike some previous work, it assumes no clues regarding parts' location and requires no prior knowledge about the original image or its simplified (e.g., lower resolution) versions. To do so, we introduce a greedy solver which combines both informed piece placement and rearrangement of puzzle segments to find the final solution. Among our other contributions are new compatibility metrics which better predict the chances of two given parts to be neighbors, and a novel estimation measure which evaluates the quality of puzzle solutions without the need for ground-truth information. Incorporating these contributions, our approach facilitates solutions that surpass state-of-the-art solvers on puzzles of size larger than ever attempted before.

Specular flow is the motion field induced on the image plane by the movement of points reflected by a curved, mirror-like surface. This flow provides information about surface shape, and when the camera and surface move as a fixed pair, shape can be recovered by solving linear differential equations along integral curves of flow. Previous analysis has shown that two distinct motions (i.e., two flow fields) are generally sufficient to guarantee a unique solution without externally-provided initial conditions. In this work, we show that we can often succeed with only one flow. The key idea is to exploit the fact that smooth surfaces induce integrability constraints on the surface normal field. We show that this induces a new differential equation that facilitates the propagation of shape information between integral curves of flow, and that combining this equation with known methods often permits the recovery of unique shape from a single specular flow given only a single seed point.

The phenomenon of visual curve completion, where the visual system completes the missing part (e.g., due to occlusion) between two contour fragments, is a major problem in perceptual organization research. Previous computational approaches for the shape of the completed curve typically follow formal descriptions of desired, image-based perceptual properties (e.g, minimum total curvature, roundedness, etc.). Unfortunately, however, it is difficult to determine such desired properties psychophysically and indeed there is no consensus in the literature for what they should be. Instead, in this paper we suggest to exploit the fact that curve completion occurs in early vision in order to formalize the problem in a space that explicitly abstracts the primary visual cortex. We first argue that a suitable abstraction is the unit tangent bundle R2× S1and then we show that a basic principle of “minimum energy consumption” in this space, namely a minimum length completion, entails desired perceptual properties for the completion in the image plane. We present formal theoretical analysis and numerical solution methods, we show results on natural images and their advantage over existing popular approaches, and we discuss how our theory explains recent findings from the perceptual literature using basic principles only.

An image of a specular (mirror-like) object is nothing but a distorted reflection of its environment. When the environment is unknown, reconstructing shape from such an image can be very difficult. This reconstruction task can be made tractable when, instead of a single image, one observes relative motion between the specular object and its environment, and therefore, a motion field-or specular flow-in the image plane. In this paper, we study the shape from specular flow problem and show that observable specular flow is directly related to surface shape through a nonlinear partial differential equation. This equation has the key property of depending only on the relative motion of the environment while being independent of its content. We take first steps toward understanding and exploiting this PDE, and we examine its qualitative properties in relation to shape geometry. We analyze several cases in which the surface shape can be recovered in closed form, and we show that, under certain conditions, specular shape can be reconstructed when both the relative motion and the content of the environment are unknown. We discuss numerical issues related to the proposed reconstruction algorithms, and we validate our findings using both real and synthetic data.

Boundary detection constitutes a crucial step in many computer vision tasks. We present a learning approach for automatically constructing high-performance local boundary detectors for natural images via genetic programming (GP). Our GP system is unique in that it combines filter kernels that were inspired by models of processing in the early stages of the primate visual system, but makes no assumptions about what constitutes a boundary, thus avoiding the need to make ad hoc intuitive definitions. By testing our evolved boundary detectors on a highly challenging benchmark set of natural images with associated human-marked boundaries, we show performance that outperforms most existing approaches.

When a curved mirror-like surface moves relative to its environment, it induces a motion field-or specular flow- on the image plane that observes it. This specular flow is related to the mirror's shape through a non-linear partial differential equation, and there is interest in understanding when and how this equation can be solved for surface shape. Existing analyses of this `shape from specular flow equation' have focused on closed-form solutions, and while they have yielded insight, their critical reliance on externally-provided initial conditions and/or specific motions makes them difficult to apply in practice. This paper resolves these issues. We show that a suitable reparameterization leads to a linear formulation of the shape from specular flow equation. This formulation radically simplifies the reconstruction process and allows, for example, both motion and shape to be recovered from as few as two specular flows even when no externally-provided initial conditions are available. Our analysis moves us closer to a practical method for recovering shape from specular flow that operates under arbitrary, unknown motions in unknown illumination environments and does not require additional shape information from other sources.

The inference of specular (mirror-like) shape is a particularly difficult problem because an image of a specular object is nothing but a distortion of the surrounding environment. Consequently, when the environment is unknown, such an image would seem to convey little information about the shape itself. It has recently been suggested (Adato et al., ICCV 2007) that observations of relative motion between a specular object and its environment can dramatically simplify the inference problem and allow one to recover shape without explicit knowledge of the environment content. However, this approach requires solving a non-linear PDE (the dasiashape from specular flow equationpsila) and analytic solutions are only known to exist for very constrained motions. In this paper, we consider the recovery of shape from specular flow under general motions. We show that while the dasiashape from specular flowpsila PDE for a single motion is non-linear, we can combine observations of multiple specular flows from distinct relative motions to yield a linear set of equations. We derive necessary conditions for this procedure, discuss several numerical issues with their solution, and validate our results quantitatively using image data.

Boundary detection constitutes a crucial step in many computer vision tasks. We present a novel learning approach to automatically construct a boundary detector for natural images via Genetic Programming (GP). Our approach aims to use GP as a learning framework for evolving computer programs that are evaluated against human-marked boundary maps, in order to accurately detect and localize boundaries in natural images. Our GP system is unique in that it combines filter kernels that were inspired by models of processing in the early stages of the primate visual system, but makes no assumption about what constitutes a boundary, thus avoiding the need to make ad-hoc intuitive definitions. By testing the evolved boundary detectors on a benchmark set of natural images with associated human-marked boundaries, we show performance to be quantitatively competitive with existing computer-vision approaches. Moreover, we show that our evolved detector provides insights into the mechanisms underlying boundary detection in the human visual system.

The image of a curved, specular (mirror-like) surface is a distorted reflection of the environment. The goal of our work is to develop a framework for recovering general shape from such distortions when the environment is neither calibrated nor known. To achieve this goal we consider far-field illumination, where the object-environment distance is relatively large, and we examine the dense specular flow that is induced on the image plane through relative object-environment motion. We show that under these very practical conditions the observed specular flow can be related to surface shape through a pair of coupled nonlinear partial differential equations. Importantly, this relationship depends only on the environment's relative motion and not its content. We examine the qualitative properties of these equations, present analytic methods for recovery of the shape in several special cases, and empirically validate our results using captured data. We also discuss the relevance to both computer vision and human perception.

Good continuation is a fundamental principle of perceptual organization that guides the grouping of parts based on how they should succeed one another within coherent wholes. Despite the general language that was used by the Gestalt psychologists in phrasing this principle, computational work has focused almost exclusively on the study of curve-like structures. Here we offer for the first time, a rigorous generalization of good continuation to arbitrary visual structures that can be abstracted as scalar functions over the image plane. The differential geometry of these structures dictates that their good continuation should be based both on their value and on the geometry of their level sets, which yield a coupled system of equations solvable for a formal model. We exhibit the resulting computation on shading and intensity functions, demonstrating how it eliminates spurious measurements while preserving both regular structure and singularities. Related implementations could be applied to color channels, motion magnitude, and disparity signals

Neurons in primary visual cortex respond selectively to oriented stimuli such as edges and lines. The long-range horizontal connections between them are thought to facilitate contour integration. While many physiological and psychophysical findings suggest that collinear or association field models of good continuation dictate particular projection patterns of horizontal connections to guide this integration process, significant evidence of interactions inconsistent with these hypotheses is accumulating. We first show that natural random variations around the collinear and association field models cannot account for these inconsistencies, a fact that motivates the search for more principled explanations. We then develop a model of long-range projection fields that formalizes good continuation based on differential geometry. The analysis implicates curvature(s) in a fundamental way, and the resulting model explains both consistent data and apparent outliers. It quantitatively predicts the (typically ignored) spread in projection distribution, its nonmonotonic variance, and the differences found among individual neurons. Surprisingly, and for the first time, this model also indicates that texture (and shading) continuation can serve as alternative and complementary functional explanations to contour integration. Because current anatomical data support both (curve and texture) integration models equally and because both are important computationally, new testable predictions are derived to allow their differentiation and identification.

The denoising of color images is an increasingly studied problem whose state-of-the-art solutions employ a variety of diffusion schemes. Specifying the correct diffusion is difficult, however, in part because of the subtleties of color interactions. We address this difficulty by proposing a perceptual organization approach to color denoising based on the principle of good continuation. We exploit the periodic chromatic (hue) component of the color in its representation as a frame field. We derive two hue curvatures and use them to construct a local model for the behavior of the color, which in turn specifies consistency constraints between nearby color measurements. These constraints are then used to replace noisy pixels by examining their spatial context. Such a contextual analysis (combined with standard methods to handle the scalar channels, saturation and lightness), results in a robust noise removal process that preserves discontinuities, singularities, and fine chromatic structures, including those that diffusion processes are prone to distort. We demonstrate our approach on a variety of synthetic and natural images.

Locally parallel dense patterns-sometimes called texture flows-define a perceptually coherent structure of particular significance to perceptual organization. We argue that with applications ranging from image segmentation and edge classification to shading analysis and shape interpretation, texture flows deserve attention equal to edge segment grouping and curve completion. This paper develops the notion of texture flow from a geometrical point of view to argue that local measurements of such structures must incorporate two curvatures. We show how basic theoretical considerations lead to a unique model for the local behavior of the flow and to a notion of texture flow "good continuation." This, in turn, translates to a specification of consistency constraints between nearby flow measurements which we use for the computation of globally (piecewise) coherent structure through the contextual framework of relaxation labeling. We demonstrate the results on synthetic and natural images.

Locally parallel dense patterns - sometimes called texture flows define a perceptually coherent structure which is important to image segmentation, edge classification, shading analysis, and shape interpretation. This paper develops the notion of texture flow from a geometrical point of view to argue that local measurements of such structures must incorporate two curvatures. We show how basic theoretical considerations lead to a unique model for the local behavior of the flow and allow for the specification of consistency constraints between nearby measurements. The computation of globally coherent structure via neighborhood relationships is demonstrated on synthetic and natural images, and is compared to orientation diffusion.

We address the problem of practical manipulation planning for rearrangement tasks of many movable objects. We study a special case of the rearrangement task, where the only allowed manipulation is pushing. We search for algorithms that can provide practical planning time for most common scenarios. We present a hierarchical classification of manipulation problems into several classes, each characterized by properties of the plans that can solve it. Such a classification allows one to consider each class individually, to analyze and exploit properties of each class, and to suggest individual planning methods accordingly. Following this classification, we suggest algorithms for two of the defined classes. Both items have been tested in a simulated environment, with up to 32 movable objects and 66 combined DOF. We present the simulations results as well as some experimental results using a real platform.

We formulate and address the problem of planning a pushing manipulation by a mobile robot which tries to rearrange several movable objects in its work space. We present an algorithm which, when given a set of goal configurations, plans a pushing path to the "cheapest" goal or announces that no such path exists. Our method provides detailed manipulation plans, including any intermediate motion of the pusher while changing contact configuration with the pushed movables. Given a pushing problem, a pushing path is found using a two-phase procedure: a context sensitive back propagation of a cost function which maps the configuration space, and a gradient descent phase which builds the pushing path. Both phases are based on a dynamic neighborhood filter which constrains each step to consider only admissible neighboring configurations. This admissibility mechanism provides a primary tool for expressing the special characteristics of the pushing manipulation. It also allows for a full integration of any geometrical constraints imposed by the pushing robot, the pushed movables and the environment. We prove optimality and completeness of our algorithm and give some experimental results in different scenarios.

Formulates and addresses the problem of planning a pushing manipulation by a mobile robot which tries to rearrange several movable objects in its work space. The authors present an algorithm which, when given a set of goal configurations, plans a pushing path to the "cheapest" goal or announces that no such path exists. The pushing path is found using a two phase procedure: context sensitive back propagation of a cost function, and a pushing path restoration phase. The latter is based on a gradient descent procedure which considers, at each step, only admissible neighboring configurations. The admissibility mechanism provides a primary tool for expressing the unique characteristics of the pushing manipulation. It also allows a full integration of any geometrical constraints imposed by the pushing robot and the pushed objects. The authors have proved the algorithm to be optimal and (resolution-) complete and give some simulation results in different scenarios, as well as some experimental results using a real platform.

Rearrangement of objects by pushing is a basic manipulation task. The authors (1995) presented a resolution-complete algorithm that plans optimal pushing manipulations for rearrangement tasks but operates in high time and space complexity. In this paper the authors address the issue of practical planning for the same kind of problems. Rather than using a classical heuristic method, the authors propose an alternative approach. The authors present a hierarchical classification of the pushing problems domain into several classes, each characterized by properties of the plans that can solve it. Such a classification allows the authors to consider each class individually, analyze and exploit properties of each class, and suggest individual planning methods. Algorithms for two of the defined classes are presented. Both algorithms were tested in a simulated environment, with up to 32 movable objects and 66 combined DOF. Some of these simulations are presented here.