Generation of Smooth Surfaces by Controlling Curvature Variation

To satisfy a designer's intention for constructing aesthetic shapes such as automotive bodies, we propose a surface generation method. In the surface design process, designers determine shapes according to their great concern for the reflected images of vehicle surroundings, shade lines and highlight lines. Since reflection and shading are affected by changes of surface normal, the curvature variation of the surface, which represents the change of the surface normal, should be smooth and distributed as designers want. The proposed method controls curvature distribution directly by determining a surface shape from an evolute, which is a locus of the curvature center of the generatrix and moves along directrices to form the surface. It first generates evolutes of boundary curves to be generatrices as rational Bezier curves, then interpolates their shapes with the Bezier polygons, and locates the interpolated shape to the corresponding position of the directrices. By applying this method, we have confirmed that a smooth shape is generated from four boundary curves.     

High Order Strong Stability Preserving Time Discretizations

Strong stability preserving (SSP) high order time discretizations were developed to ensure nonlinear stability properties necessary in the numerical solution of hyperbolic partial differential equations with discontinuous solutions. SSP methods preserve the strong stability properties—in any norm, seminorm or convex functional—of the spatial discretization coupled with first order Euler time stepping. This paper describes the development of SSP methods and the connections between the timestep restrictions for strong stability preservation and contractivity. Numerical examples demonstrate that common linearly stable but not strong stability preserving time discretizations may lead to violation of important boundedness properties, whereas SSP methods guarantee the desired properties provided only that these properties are satisfied with forward Euler timestepping. We review optimal explicit and implicit SSP Runge–Kutta and multistep methods, for linear and nonlinear problems. We also discuss the SSP properties of spectral deferred correction methods. The work of S. Gottlieb was supported by AFOSR grant number FA9550-06-1-0255. The work of D.I. Ketcheson was supported by a US Dept. of Energy Computational Science Graduate Fellowship under grant DE-FG02-97ER25308. The research of C.-W. Shu is supported in part by NSF grants DMS-0510345 and DMS-0809086.     

A Variational Model for Capturing Illusory Contours Using Curvature

Illusory contours, such as the classical Kanizsa triangle and square [9], are intrinsic phenomena in human vision. These contours are not completely defined by real object boundaries, but also include illusory boundaries which are not explicitly present in the images. Therefore, the major computational challenge of capturing illusory contours is to complete the illusory boundaries. In this paper, we propose a level set based variational model to capture a typical class of illusory contours such as Kanizsa triangle. Our model completes missing boundaries in a smooth way via Euler’s elastica, and also preserves corners by incorporating curvature information of object boundaries. Our model can capture illusory contours regardless of whether the missing boundaries are straight lines or curves. We compare the choice of the second order Euler’s elastica used in our model and that of the first order Euler’s elastica developed in Nitzberg-Mumford-Shiota’s work on the problem of segmentation with depth [15, 16]. We also prove that with the incorporation of curvature information of objects boundaries our model can preserve corners as completely as one wants. Finally we present the numerical results by applying our model on some standard illusory contours. This work has been supported by ONR contract N00014-03-1-0888, NSF contract DMS-9973341 and NIH contract P20 MH65166. Wei Zhu received the B.S. degree in Mathematics from Tsinghua University in 1994, the M.S. degree in Mathematics from Peking University in 1999, and the Ph.D. degree in Applied Mathematics from UCLA in 2004. He is currently a Postdoc at Courant Institute, New York University. His research interests include mathematical problems in image processing and visual neuroscience. Tony Chan received the B.S. degree in engineering and the M.S. degree in aerospace engineering, both in 1973, from the California Institute of Technology, Pasadena, and the Ph.D. degree in computer science from Stanford University, Stanford, CA, in 1978. Heis currently the Dean of the Division of Physical Science and College of Letters and Science, UCLA, where he has been a Professor in the Department of Mathematics since 1986. His research interests include PDE methods for image processing, multigrid, and domain decomposition algorithms, iterative methods, Krylov subspace methods, and parallel algorithms.     

A theory of nonmonotonic rule systems II

Conclusions We have proved a number of results on nonmonotonic rule systems. This theory allows us to capture many constructions appearing in the current literature on the logical foundations of artificial intelligence.Our results provide additional tools tying these constructs with traditional methods of logic and recursion theory.In a sequel we shall deal with rule systems containing variables in the rules and with predicate logics. We shall prove results related to the properties of recursive systems that are not necessarily highly recursive. We shall also explore connections with.Work partially supported by NSF grant RII-86-10671 and Kentucky EPSCoR program and ARO contract DAAL03-89-K-0124.Work partially supported by NSF grant DMS-89-02797 and ARO contract DAAG629-85-C-0018.Work partially supported by NSF grants DMS-87-02473 and DMS-90-06413.     

Fast Global Minimization of the Active Contour/Snake Model

The active contour/snake model is one of the most successful variational models in image segmentation. It consists of evolving a contour in images toward the boundaries of objects. Its success is based on strong mathematical properties and efficient numerical schemes based on the level set method. The only drawback of this model is the existence of local minima in the active contour energy, which makes the initial guess critical to get satisfactory results. In this paper, we propose to solve this problem by determining a global minimum of the active contour model. Our approach is based on the unification of image segmentation and image denoising tasks into a global minimization framework. More precisely, we propose to unify three well-known image variational models, namely the snake model, the Rudin–Osher–Fatemi denoising model and the Mumford–Shah segmentation model. We will establish theorems with proofs to determine the existence of a global minimum of the active contour model. From a numerical point of view, we propose a new practical way to solve the active contour propagation problem toward object boundaries through a dual formulation of the minimization problem. The dual formulation, easy to implement, allows us a fast global minimization of the snake energy. It avoids the usual drawback in the level set approach that consists of initializing the active contour in a distance function and re-initializing it periodically during the evolution, which is time-consuming. We apply our segmentation algorithms on synthetic and real-world images, such as texture images and medical images, to emphasize the performances of our model compared with other segmentation models. Research supported by NIH U54RR021813, NSF DMS-0312222, NSF ACI-0321917 and NSF DMI-0327077.     

Similarity-invariant signatures for partially occluded planar shapes

A methodology is described for associating local invariant signature functions to smooth planar curves in order to enable their translation, rotation, and scale-invariant recognition from arbitrarily clipped portions. The suggested framework incorporates previous approaches, based on locating inflections, curvature extrema, breakpoints, and other singular points on planar object boundaries, and provides a systematic way of deriving novel invariant signature functions based on curvature or cumulative turn angle of curves. These new signatures allow the specification of arbitrarily dense feature points on smooth curves, whose locations are invariant under similarity transformations. The results are useful for detecting and recognizing partially occluded planar objects, a key task in low-level robot vision.     

Representation of shift-invariant operators onL 2 byH ∞ transfer functions: An elementary proof,a generalization toL p,and a counterexample forL ∞

We give an elementary proof of the well-known fact that shift-invariant operators onL ²[0, ∞) are represented by transfer functions which are bounded and analytic on the right open half-plane. We prove a generalization to Banach space-valuedL ^p -functions, where 1≤p<∞. We show that the result no longer holds forp=∞. This research was supported partially by the Weizmann Fellowship, and partially by the Air Force Office of Scientific Research under Contract F49620-86-C-0111.     

Generation of Discrete Bicubic G^1 B-Spline Ship Hullform Surfaces from a Given Curve Network Using Virtual Iso-Parametric Curves

We propose a method that automatically generates discrete bicubic G^1 continuous B-spline surfaces that interpolate the curve network of a ship huliform.First,the curves in the network are classified into two types;boundary curves and ＂reference curves＂,The boundary curves correspond to a set of rectangular（or triangular）topological type that can be representes with tensot-product （or degenerate）B-spline surface patches.Next,in the interior of the patches,surface fitting points and cross boundary derivatives are estimated from the reference curves by constructing ＂virtual＂isoparametric curves.Finally,a discrete G^1 continuous B-spline surface is gencrated by a surface fitting algorithm.Several smooth ship hullform surfaces generated from curve networks corresponding to actual ship hullforms demonstrate the quality of the method.     

Ridges for image analysis

Representation of object shape by medial structures has been an important aspect of image analysis. Methods for describing objects in a binary image by medial axes are well understood. Many attempts have been made to construct similar medial structures for objects in gray scale images. In particular, researchers have studied images by analyzing the graphs of the intensity data and identifying ridge and valley structures on those surfaces. In this paper we review many of the definitions for ridges. Computational vision models require that medial structures should remain invariant under certain transformations of the spatial locations and intensities. For each ridge definition we point out which invariances the definition satisfies. We also give extensions of the concepts so that we can located-dimensional ridge structures withinn-dimensional images. A comparison of the ridge structures produced by the different definitions is given both by mathematical examples and by an application to a 2-dimensional MR image of a head.Research supported by National Science Foundation Grant DMS-9003037.Research supported by NIH grant # P01 CA 47982.     

Tight bounds for shared memory systems accessed by Byzantine processes

We provide efficient constructions and tight bounds for shared memory systems accessed by n processes, up to t of which may exhibit Byzantine failures, in a model previously explored by Malkhi et al. [21]. We show that sticky bits are universal in the Byzantine failure model for n ≥ 3t + 1, an improvement over the previous result requiring n ≥ (2t + 1)(t + 1). Our result follows from a new strong consensus construction that uses sticky bits and tolerates t Byzantine failures among n processes for any n ≥ 3t + 1, the best possible bound on n for strong consensus. We also present tight bounds on the efficiency of implementations of strong consensus objects from sticky bits and similar primitive objects. Research supported in part by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. This work was partially completed while at AT&T Labs and while visiting the Institute for Advanced Study, Princeton, NJ. Research supported in part by US-Israel Binational Science Foundation Grant 2002246. This work was partially completed while visiting AT&T Labs. This work was partially completed while at AT&T Labs. Research supported in part by the National Science Foundation under Grant No. CCR-0331584. A preliminary version of the results presented in this paper appeared in [23].     

Solving propositional satisfiability problems

We describe an algorithm for the satisfiability problem of prepositional logic, which is significantly more efficient for this problem than is a general mixed-integer programming code. Our algorithm is a list processor using a tree-search method, and is based on Loveland's form of the algorithm of Davis and Putnam.Deceased. Research partially supported by a research grant from the National Science Foundation (DMS-8513970).     

On the Foundations of Vision Modeling III. Noncommutative Monoids of Occlusive Preimages

A significant cue for visual perception is the occlusion pattern in 2-D retinal images, which helps humans or robots navigate successfully in the 3-D environments. There have been many works in the literature on the modeling and analysis of the occlusion phenomenon, most of which are from the analytical or statistical points of view. The current paper presents a new theory of occlusion based on the simple topological definitions of preimages and a binary operation on them called “occlu.” We study numerous topological as well as algebraic structures of the resultant noncommutative preimage monoids (a monoid is a semigroup with identity). Some implications of the new theory in terms of real vision research are also addressed. Research is partially supported by NSF (USA) under the grant number DMS-0202565. Jianhong (Jackie) Shen received the Ph.D degree in Applied Mathematics from the Massachusetts Institute of Technology in 1998, and the B.S. degree from the University of Science and Technology of China (USTC) in 1994. He was a CAM (Computational and Applied Mathematics) Assistant Professor at UCLA from 1998 to 2000. He is currently an Assistant Professor of Applied Mathematics in the University of Minnesota, MN, USA. His current research interests include image, signal, and information processing, vision modeling and computation, as well as multiscale and stochastic modeling in medical and biological sciences. His new book: Image Processing and Analysis - variational, PDE, wavelets, and stochastic methods, coauthored with Prof. Tony F. Chan (Dean of Physical Sciences, UCLA), will be published by the SIAM (Soc. Ind. Appl. Math.) Publisher in September 2005. Most of his research and teaching activities could be found at .     

On combined phase 1-phase 2 projective methods for linear programming

We compare the projective methods for linear programming due to de Ghellinck and Vial, Anstreicher, Todd, and Fraley. These algorithms have the feature that they approach feasibility and optimality simultaneously, rather than requiring an initial feasible point. We compare the directions used in these methods and the lower-bound updates employed. In many cases the directions coincide and two of the lower-bound updates give the same result. It appears that Todd's direction and Fraley's lower-bound update have slight advantages, and this is borne out in limited computational testing.This research was partially supported by NSF Grant DMS-8904406 and by ONR Contract N00004-87-K0212. The computations were carried out in the Cornell Computational Optimization Laboratory with support from NSF Grant DMS-8706133.     

Path planning for deformable linear objects

We present a new approach to path planning for deformable linear (one-dimensional) objects such as flexible wires. We introduce a method for efficiently computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. By restricting the planner to minimal-energy curves, the execution of a path becomes easier. Our curve representation is adaptive in the sense that the number of parameters automatically varies with the complexity of the underlying curve. We introduce a planner that computes paths from one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. This planner can be used as a powerful local planner in a sampling-based roadmap method. This makes it possible to compute a roadmap of the entire "shape space," which is not possible with previous approaches. Using a simplified model for obstacles, we can find minimal-energy curves of fixed length that pass through specified tangents at given control points. Our work has applications in cable routing, and motion planning for surgical suturing and snake-like robots.     

A Hierarchical and Contextual Model for Aerial Image Parsing

In this paper we present a hierarchical and contextual model for aerial image understanding. Our model organizes objects (cars, roofs, roads, trees, parking lots) in aerial scenes into hierarchical groups whose appearances and configurations are determined by statistical constraints (e.g. relative position, relative scale, etc.). Our hierarchy is a non-recursive grammar for objects in aerial images comprised of layers of nodes that can each decompose into a number of different configurations. This allows us to generate and recognize a vast number of scenes with relatively few rules. We present a minimax entropy framework for learning the statistical constraints between objects and show that this learned context allows us to rule out unlikely scene configurations and hallucinate undetected objects during inference. A similar algorithm was proposed for texture synthesis (Zhu et al. in Int. J. Comput. Vis. 2:107–126, 1998) but didn’t incorporate hierarchical information. We use a range of different bottom-up detectors (AdaBoost, TextonBoost, Compositional Boosting (Freund and Schapire in J. Comput. Syst. Sci. 55, 1997; Shotton et al. in Proceedings of the European Conference on Computer Vision, pp. 1–15, 2006; Wu et al. in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1–8, 2007)) to propose locations of objects in new aerial images and employ a cluster sampling algorithm (C4 (Porway and Zhu, 2009)) to choose the subset of detections that best explains the image according to our learned prior model. The C4 algorithm can quickly and efficiently switch between alternate competing sub-solutions, for example whether an image patch is better explained by a parking lot with cars or by a building with vents. We also show that our model can predict the locations of objects our detectors missed. We conclude by presenting parsed aerial images and experimental results showing that our cluster sampling and top-down prediction algorithms use the learned contextual cues from our model to improve detection results over traditional bottom-up detectors alone.     

A Numerical Study of Diagonally Split Runge–Kutta Methods for PDEs with Discontinuities

Diagonally split Runge–Kutta (DSRK) time discretization methods are a class of implicit time-stepping schemes which offer both high-order convergence and a form of nonlinear stability known as unconditional contractivity. This combination is not possible within the classes of Runge–Kutta or linear multistep methods and therefore appears promising for the strong stability preserving (SSP) time-stepping community which is generally concerned with computing oscillation-free numerical solutions of PDEs. Using a variety of numerical test problems, we show that although second- and third-order unconditionally contractive DSRK methods do preserve the strong stability property for all time step-sizes, they suffer from order reduction at large step-sizes. Indeed, for time-steps larger than those typically chosen for explicit methods, these DSRK methods behave like first-order implicit methods. This is unfortunate, because it is precisely to allow a large time-step that we choose to use implicit methods. These results suggest that unconditionally contractive DSRK methods are limited in usefulness as they are unable to compete with either the first-order backward Euler method for large step-sizes or with Crank–Nicolson or high-order explicit SSP Runge–Kutta methods for smaller step-sizes. We also present stage order conditions for DSRK methods and show that the observed order reduction is associated with the necessarily low stage order of the unconditionally contractive DSRK methods. The work of C.B. Macdonald was partially supported by an NSERC Canada PGS-D scholarship, a grant from NSERC Canada, and a scholarship from the Pacific Institute for the Mathematical Sciences (PIMS). The work of S. Gottlieb was supported by AFOSR grant number FA9550-06-1-0255. The work of S.J. Ruuth was partially supported by a grant from NSERC Canada.     

C 0 Interior Penalty Methods for Fourth Order Elliptic Boundary Value Problems on Polygonal Domains

C ⁰ interior penalty methods for fourth order elliptic boundary value problems on polygonal domains are analyzed in this paper. A post-processing procedure that can generate C ¹ approximate solutions from the C ⁰ approximate solutions is presented. New C ⁰ interior penalty methods based on the techniques involved in the post-processing procedure are introduced. These new methods are applicable to rough right-hand sides.Susanne C. Brenner: The work of S.C. Brenner was supported in part by the National Science Foundation under Grant Nos. DMS-00-74246 and DMS-03-11790. This revised version was published online in July 2005 with corrected volume and issue numbers.     

Scheduling models for air traffic control in terminal areas

We propose a job-shop scheduling model with sequence dependent set-up times and release dates to coordinate both inbound and outbound traffic flows on all the prefixed routes of an airport terminal area and all aircraft operations at the runway complex. The proposed model is suitable for representing several operational constraints (e.g., longitudinal and diagonal separations in specific airspace regions), and different runway configurations (e.g., crossing, parallel, with or without dependent approaches) in a uniform framework. The complexity and the highly dynamic nature of the problem call for heuristic approaches. We propose a fast dynamic local search heuristic algorithm for the job-shop model suitable for considering one of the different performance criteria and embedding aircraft position shifting control technique to limit the controllers/pilots’ workload. Finally, we describe in detail the experimental analysis of the proposed model and algorithm applied to two real case studies of Milan-Malpensa and Rome-Fiumicino airport terminal areas. This work has been partially supported by grant CNR FPCCR021074 from the Italian National Research Council.