Summary form only given. X-ray computerized tomography (CT) and related imaging modalities (e.g., PET) are notorious for their excessive computational demands, especially when noise-resistant probabilistic methods such as regularized tomography are used. The basic idea of regularized tomography is to compute a smooth image whose simulated projections (line integrals) approximate the observed, noisy X-ray projections. The computational expense in previous methods stems from explicitly applying a large sparse projection matrix to enforce these smoothness and data fidelity constraints during each of many iterations of the algorithm. Here we review our recent work in regularized tomography in which the smoothness constraint is analytically transformed from the image to the projection domain, before any computations begin. As a result, iterations take place entirely in the projection domain, avoiding the repeated sparse matrix-vector products. A more surprising benefit is the decoupling of a large system of regularization equations into many small systems of simpler independent equations, whose solution requires an "embarassingly parallel" computation. Here, we demonstrate that this method provides linear speedup of regularized tomography for up to 20 compute nodes (Pentium 4, 1.5 GHz) on a 100 Mb/s network using a Matlab MPI implementation.

Is the real problem in resolving correspondence using current stereo algorithms the lack of the "right" matching criterion? In studying the related task of reconstructing three-dimensional space curves from their projections in multiple views, we suggest that the problem is more basic: matching and reconstruction are coupled, and so reconstruction algorithms should exploit this rather than assuming that matching can be successfully performed before reconstruction. To realize this coupling, a generative model of curves is introduced which has two key components: (i) a prior distribution of general space curves and (ii) an image formation model which describes how 3D curves are projected onto the image plane. A novel aspect of the image formation model is that it uses an exact description of the gradient field of a piecewise constant image. Based on this forward model, a fully automatic algorithm for solving the inverse problem is developed for an arbitrary number of views. The resulting algorithm is robust to partial occlusion, deficiencies in image curve extraction and it does not rely on photometric information. The relative motion of the cameras is assumed to be given. Several experiments are carried out on various realistic scenarios. In particular, we focus on scenes where traditional correlation-based methods would fail.

While complaints about typical edge operators are common, proposals articulating a notion of the "perfect" edge map are comparatively rare, hindering the improvement of contour enhancement techniques. To address this situation, we suggest that one objective of visual contour computation is the estimation of a clean sketch from a corrupted rendition, the latter modeling noisy and low contrast edge or line operator responses to an image. Our formal model of this clean sketch is the curve indicator random field (CIRF), whose role is to provide a basis for defining edge likelihood models by eliminating the parameter along each curve to create an image of curves. For curves modeled with stationary Markov processes, this ideal edge prior is non-Gaussian and its moment generating functional has a form closely related to the Feynman-Kac formula. This sketch model leads to a nonlinear, minimum mean squared error contour enhancement filter that requires the solution of two elliptic partial differential equations. The framework is also independent of the order of the contour model, allowing us to introduce a Markov process model for contour curvature. We analyze the distribution of such curves and show that its mode is the Euler spiral, a curve minimizing changes in curvature. Example computations using the contour enhancement filter with the curvature-based contour model are provided, highlighting how the filter is curvature-selective even when curvature is absent in the input.

Although the classical Blum skeleton has long been considered unstable, many have attempted to alleviate this defect through pruning. Unfortunately, these methods have an arbitrary basis, and, more importantly, they do not prevent internal structural alterations due to slight changes in an object's boundary. The result is a relative lack of development of skeleton representations for indexing object databases, despite a long history. Here we revisit a subset of the skeleton-called ligature by Blum-to demonstrate how the topological sensitivity of the skeleton can be eliminated. We relate ligature to a natural growth principle to provide an account of the perceptual parts of shape.

It is commonly held that skeleton variation due to noise is unmanageable. It is also believed that smoothing, invoked to combat noise, creates no new structures, as in the causality principle for smoothing images. We demonstrate that both views are incorrect. We characterize how smooth points of the skeleton evolve under a general boundary evolution, with the corollary that, when the boundary is smoothed by a geometric heat equation, the skeleton evolves according to a related geometric heat equation. The surprise is that, while certain aspects of the skeleton simplify, as one would expect, others can behave wildly, including the creation of new skeleton branches. Fortunately such sections can be flagged as ligature, or those portions of the skeleton related to shape concavities. Our analysis also includes junctions and an explicit model for boundary noise. Provided a smoothness condition is met, the skeleton can often reduce noise. However when the smoothness condition is violated, the skeleton can change violently, which, we speculate, corresponds to situations in which "parts" are created, e.g., when the handle appears on a rotating cup.

Bounding contours of physical objects are often fragmented by other occluding objects. Long-distance perceptual grouping seeks to join fragments belonging to the same object. Approaches to grouping based on invariants assume objects are in restricted classes, while those based on minimal energy continuations assume a shape for the missing contours and require this shape to drive the grouping process. While these assumptions may be appropriate for certain specific tasks or when contour gaps are small, in general occlusion can give rise to large gaps, and thus long-distance contour fragment grouping is a different type of perceptual organization problem. We propose the long-distance principle that those fragments should be grouped whose fragmentation could have arisen from a shared, simple occluder. The gap skeleton is introduced as a representation of this virtual occluder, and an algorithm for computing it is given. Finally, we show that a view of the virtual occluder as a disk can be interpreted as an equivalence class of curves interpolating the fragment endpoints.

Although the classical Blum skeleton has long been considered unstable, many have attempted to alleviate this defect through pruning. Unfortunately, these methods have an arbitrary basis, and, more importantly, they do not prevent internal structural alterations due to slight changes in an object's boundary. The result is a relative lack of development of skeleton representations for indexing object databases, despite a long history. Here we revisit a subset of the skeleton—called ligature by Blum—to demonstrate how the topological sensitivity of the skeleton can be alleviated. In particular, we show how the deletion of ligature regions leads to stable hierarchical descriptions, illustrating this point with several computational examples. We then relate ligature to a natural growth principle to provide an account of the perceptual parts of shape. Finally, we discuss the duality between the problems of part decomposition and contour fragment grouping.

Bounding contours of physical objects are often fragmented by other occluding objects. Long-distance perceptual grouping seeks to join fragments belonging to the same object. Approaches to grouping based on invariants assume objects are in restricted classes, while those based on minimal energy continuations assume a shape for the missing contours and require this shape to drive the grouping process. We propose the more general principle that those fragments should be grouped whose fragmentation could have arisen from a generic occluder. The gap skeleton is introduced as a representation of this virtual occluder, and an algorithm for computing it is given.