Reconstructing transparent objects is a challenging problem. While producing reasonable results for quite complex objects, existing approaches require custom calibration or somewhat expensive labor to achieve high precision. When an overall shape preserving salient and fine details is sufficient, we show in this paper a significant step toward solving the problem when the object's silhouette is available and simple user interaction is allowed, by using a video of a transparent object shot under varying illumination. Specifically, we estimate the normal map of the exterior surface of a given solid transparent object, from which the surface depth can be integrated. Our technical contribution lies in relating this normal estimation problem to one of graph-cut segmentation. Unlike conventional formulations, however, our graph is dual-layered, since we can see a transparent object's foreground as well as the background behind it. Quantitative and qualitative evaluation are performed to verify the efficacy of this practical solution.

We introduce a framework for outdoor photometric stereo utilizing natural environmental illumination. Our framework extends beyond existing photometric stereo methods intended for laboratory environments to encompass robust outdoor operation in the real world. In this paper, we motivate our framework, describe the components of its processing pipeline, and assess its performance in synthetic experiments as well as in natural experiments including objects in outdoor environments with complex real-world illuminations.

This paper proposes a novel approach for extracting two intrinsic feature curves on hippocampal (HC) surfaces. The hippocampus is a key target of study in medical imaging, as it degenerates in conditions such as epilepsy and Alzheimer's disease (AD), but its structure is complex. To facilitate HC morphometry, we generate two intrinsic feature curves that describe their global geometries. For example, the separation of them captures thickness changes in HC surfaces, which can be used to effectively measure HC atrophy found in patients with AD. They also separate HC surfaces into upper and lower surface patches where intrinsic shape analysis using conformal modules can be carried out. Based on these curves, we further propose a parameterization of HC surfaces called the eigen-harmonic parameterization (EHP). EHP maps each HC surface onto a parameter domain and imposes longitudinal and azimuthal coordinates on each surface, which follow the gradient and level sets of its first nontrivial Laplace--Beltrami eigenfunction, respectively. Each tubular domain is constructed according to the geometry of an individual HC surface. This gives a parameter domain with much less geometric distortion compared to spherical parameterization. With EHP, all HC surfaces are automatically registered with intrinsic feature curves preserved and geometric distortions minimized. This allows shape analysis on any number of HC surfaces to be performed consistently. We studied geometric changes over time in 138 HC surfaces of patients with AD and normal subjects scanned at two different times. We successfully located areas with significantly different shape changes over time between the two groups.

We propose a new variational model for image denoising, which employs the $L^{1}$-norm of the mean curvature of the image surface $(x,f(x))$ of a given image $f:\Omega\rightarrow\mathbb{R}$. Besides eliminating noise and preserving edges of objects efficiently, our model can keep corners of objects and greyscale intensity contrasts of images and also remove the staircase effect. In this paper, we analytically study the proposed model and justify why our model can preserve object corners and image contrasts. We apply the proposed model to the denoising of curves and plane images, and also compare the results with those obtained by using the classical Rudin–Osher–Fatemi model [Phys. D, 60 (1992), pp. 259–268].

In brain mapping research, parameterized 3-D surface models are of great interest for statistical comparisons of anatomy, surface-based registration, and signal processing. Here, we introduce the theories of continuous and discrete surface Ricci flow, which can create Riemannian metrics on surfaces with arbitrary topologies with user-defined Gaussian curvatures. The resulting conformal parameterizations have no singularities and they are intrinsic and stable. First, we convert a cortical surface model into a multiple boundary surface by cutting along selected anatomical landmark curves. Secondly, we conformally parameterize each cortical surface to a parameter domain with a user-designed Gaussian curvature arrangement. In the parameter domain, a shape index based on conformal invariants is computed, and inter-subject cortical surface matching is performed by solving a constrained harmonic map. We illustrate various target curvature arrangements and demonstrate the stability of the method using longitudinal data. To map statistical differences in cortical morphometry, we studied brain asymmetry in 14 healthy control subjects. We used a manifold version of Hotelling's T(2) test, applied to the Jacobian matrices of the surface parameterizations. A permutation test, along with the cumulative distribution of p-values, were used to estimate the overall statistical significance of differences. The results show our algorithm's power to detect subtle group differences in cortical surfaces.

We present an automatic optimization approach to outfit synthesis. Given the hair color, eye color, and skin color of the input body, plus a wardrobe of clothing items, our outfit synthesis system suggests a set of outfits subject to a particular dress code. We introduce a probabilistic framework for modeling and applying dress codes that exploits a Bayesian network trained on example images of real-world outfits. Suitable outfits are then obtained by optimizing a cost function that guides the selection of clothing items to maximize the color compatibility and dress code suitability. We demonstrate our approach on the four most common dress codes:Casual, Sportswear, Business-Casual, andBusiness. A perceptual study validated on multiple resultant outfits demonstrates the efficacy of our framework.

Reconstructing transparent objects is a challenging problem. While producing reasonable results for quite complex objects, existing approaches require custom calibration or somewhat expensive labor to achieve high precision. On the other hand, when an overall shape preserving salient and fine details is sufficient, we show in this paper a significant step toward solving the problem on a shoestring budget, by using only a video camera, a moving spotlight, and a small chrome sphere. Specifically, the problem we address is to estimate the normal map of the exterior surface of a given solid transparent object, from which the surface depth can be integrated. Our technical contribution lies in relating this normal reconstruction problem to one of graph-cut segmentation. Unlike conventional formulations, however, our graph is dual-layered, since we can see a transparent object's foreground as well as the background behind it. Quantitative and qualitative evaluation are performed to verify the efficacy of this practical solution.

In this paper, we propose novel algorithms for inpainting and refinement of diffeomorphisms. We first represent a diffeomorphism by its Beltrami coefficient. Then it is possible to refine and inpaint the diffeomorphism by processing this Beltrami coefficient. With the inpainted/refined Beltrami coefficient, we construct a new diffeomorphism using the exact Beltrami holomorphic flow algorithm proposed in this paper. We apply our algorithms on several practical applications, which include the inpainting of a highly distorted diffeomorphism, the inpainting of image sequences of deforming shapes, the super-resolution of diffeomorphisms and the global parameterization of cortical surfaces by combining local parameterizations. Experiments show that our algorithm can solve these problems with natural and smooth results. We demonstrate how our proposed method can be widely applied in areas from texture mapping to video processing, and from computer graphics to medical imaging.

We propose here a class of restoration algorithms for color images, based upon the Mumford-Shah (MS) model and nonlocal image information. The Ambrosio-Tortorelli and Shah elliptic approximations are defined to work in a small local neighborhood, which are sufficient to denoise smooth regions with sharp boundaries. However, texture is nonlocal in nature and requires semilocal/non-local information for efficient image denoising and restoration. Inspired from recent works (nonlocal means of Buades, Coll, Morel, and nonlocal total variation of Gilboa, Osher), we extend the local Ambrosio-Tortorelli and Shah approximations to MS functional (MS) to novel nonlocal formulations, for better restoration of fine structures and texture. We present several applications of the proposed nonlocal MS regularizers in image processing such as color image denoising, color image deblurring in the presence of Gaussian or impulse noise, color image inpainting, color image super-resolution, and color filter array demosaicing. In all the applications, the proposed nonlocal regularizers produce superior results over the local ones, especially in image inpainting with large missing regions. We also prove several characterizations of minimizers based upon dual norm formulations.

We present a system that automatically synthesizes indoor scenes realistically populated by a variety of furniture objects. Given examples of sensibly furnished indoor scenes, our system extracts, in advance, hierarchical and spatial relationships for various furniture objects, encoding them into priors associated with ergonomic factors, such as visibility and accessibility, which are assembled into a cost function whose optimization yields realistic furniture arrangements. To deal with the prohibitively large search space, the cost function is optimized by simulated annealing using a Metropolis-Hastings state search step. We demonstrate that our system can synthesize multiple realistic furniture arrangements and, through a perceptual study, investigate whether there is a significant difference in the perceived functionality of the automatically synthesized results relative to furniture arrangements produced by human designers.

For various 3D shape analysis tasks, the Laplace-Beltrami(LB) embedding has become increasingly popular as it enables the efficient comparison of shapes based on intrinsic geometry. One fundamental difficulty in using the LB embedding, however, is the ambiguity in the eigen-system, and it is conventionally only handled in a heuristic way. In this work, we propose a novel and intrinsic metric, the spectral l2-distance, to overcome this difficulty. We prove mathematically that this new distance satisfies the conditions of a rigorous metric. Using the resulting optimal embedding determined by the spectral l2-distance, we can perform both local and global shape analysis intrinsically in the embedding space. We demonstrate this by developing a template matching approach in the optimal embedding space to solve the challenging problem of identifying major sulci on vervet cortical surfaces. In our experiments, we validate the robustness of our method by the successful identification of major sulcal lines on a large data set of 698 cortical surfaces and illustrate its potential in brain mapping studies.

Surface registration is widely used in machine vision and medical imaging, where 1-1 correspondences between surfaces are computed to study their variations. Surface maps are usually stored as the 3D coordinates each vertex is mapped to, which often requires lots of storage memory. This causes inconvenience in data transmission and data storage, especially when a large set of surfaces are analyzed. To tackle this problem, we propose a novel representation of surface diffeomorphisms using Beltrami coefficients, which are complex-valued functions defined on surfaces with supreme norm less than 1. Fixing any 3 points on a pair of surfaces, there is a 1-1 correspondence between the set of surface diffeomorphisms between them and the set of Beltrami coefficients on the source domain. Hence, every bijective surface map can be represented by a unique Bel-trami coefficient. Conversely, given a Beltrami coefficient, we can reconstruct the unique surface map associated to it using the Beltrami Holomorphic flow (BHF) method introduced in this paper. Using this representation, 1/3 of the storage space is saved. We can further reduce the storage requirement by 90% by compressing the Beltrami coefficients using Fourier approximations. We test our algorithm on synthetic data, real human brain and hippocampal surfaces. Our results show high accuracy in the reconstructed data, while the amount of storage is greatly reduced. Our approach is compared with the Fourier compression of the coordinate functions using the same amount of data. The latter approach often shows jaggy results and cannot guarantee to preserve diffeomorphisms.

We propose a novel fourth order dual method for the minimization of the non-smooth semi-norm ∥Δ·∥1when in amalgamation with a new staircase reducing texture decomposition model of image processing. The proposed model incorporating this high order energy is a variant of the Chambolle Lions denoising model that additionally utilizes a negative Sobolev norm. We claim that the dual method is faster and more stable than the current gradient descent time marching algorithms often used to minimize such energies. Moreover, a proof of convergence of the proposed method, in conjunction with the new model, will be provided. Lastly, we provide guidelines on how the new energy and proposed framework can be naturally incorporated into many popular texture extraction and restoration models of image processing.

We generalize the primal-dual hybrid gradient (PDHG) algorithm proposed by Zhu and Chan in [An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration, CAM Report 08-34, UCLA, Los Angeles, CA, 2008] to a broader class of convex optimization problems. In addition, we survey several closely related methods and explain the connections to PDHG. We point out convergence results for a modified version of PDHG that has a similarly good empirical convergence rate for total variation (TV) minimization problems. We also prove a convergence result for PDHG applied to TV denoising with some restrictions on the PDHG step size parameters. We show how to interpret this special case as a projected averaged gradient method applied to the dual functional. We discuss the range of parameters for which these methods can be shown to converge. We also present some numerical comparisons of these algorithms applied to TV denoising, TV deblurring, and constrained $l_1$ minimization problems.

Surface registration, which transforms different sets of surface data into one common reference space, is an important process which allows us to compare or integrate the surface data effectively. If a nonrigid transformation is required, surface registration is commonly done by parameterizing the surfaces onto a simple parameter domain, such as the unit square or sphere. In this work, we are interested in looking for meaningful registrations between surfaces through parameterizations, using prior features in the form of landmark curves on the surfaces. In particular, we generate optimized conformal parameterizations which match landmark curves exactly with shape-based correspondences between them. We propose a variational method to minimize a compound energy functional that measures the harmonic energy of the parameterization maps and the shape dissimilarity between mapped points on the landmark curves. The novelty is that the computed maps are guaranteed to align the landmark features consistently and give a shape-based diffeomorphism between the landmark curves. We achieve this by intrinsically modeling our search space of maps as flows of smooth vector fields that do not flow across the landmark curves. By using the local surface geometry on the curves to define a shape measure, we compute registrations that ensure consistent correspondences between anatomical features. We test our algorithm on synthetic surface data. An application of our model to medical imaging research is shown, using experiments on brain cortical surfaces, with anatomical (sulcal) landmarks delineated, which show that our computed maps give a shape-based alignment of the sulcal curves without significantly impairing conformality. This ensures correct averaging and comparison of data across subjects.

Variational models have been studied for image segmentation application since the Mumford-Shah functional was introduced in the late 1980s. In this paper, we focus on multiphase segmentation with a new regularization term that yields an unsupervised segmentation model. We propose a functional that automatically chooses a favorable number of phases as it segments the image. The primary driving force of the segmentation is the intensity fitting term while a phase scale measure complements the regularization term. We propose a fast, yet simple, brute-force numerical algorithm and present experimental results showing the robustness and stability of the proposed model.

All surfaces can be classified by the conformal equivalence relation. Conformal invariants, which are shape indices that can be defined intrinsically on a surface, may be used to identify which surfaces are conformally equivalent, and they can also be used to measure surface deformation. Here we propose to compute a conformal invariant, or shape index, that is associated with the perimeter of the inner concentric circle in the hyperbolic parameter plane. With the surface Ricci flow method, we can conformally map a multiply connected domain to a multi-hole disk and this conformal map can preserve the values of the conformal invariant. Our algorithm provides a stable method to map the values of this shape index in the 2D (hyperbolic space) parameter domain. We also applied this new shape index for analyzing abnormalities in brain morphology in Alzheimer's disease (AD) and Williams syndrome (WS). After cutting along various landmark curves on surface models of the cerebral cortex or hippocampus, we obtained multiple connected domains. We conformally projected the surfaces to hyperbolic plane with surface Ricci flow method, accurately computed the proposed conformal invariant for each selected landmark curve, and assembled these into a feature vector.We also detected group differences in brain structure based on multivariate analysis of the surface deformation tensors induced by these Ricci flow mappings. Experimental results with 3D MRI data from 80 subjects demonstrate that our method powerfully detects brain surface abnormalities when combined with a constrained harmonic map based surface registration method.

We present a rigorous framework that defines a class of net weighting schemes in which unconstrained minimization is successively performed on a weighted objective. We show that, provided certain goals are met in the unconstrained minimization, these net weighting schemes are guaranteed to converge to the optimal solution of the original timing-constrained placement problem. These are the first results that provide conditions under which a net weighting scheme will converge to a timing optimal placement. We then identify several weighting schemes that satisfy the given convergence properties and implement them, with promising results: a modification of the weighting scheme given in [11]results in consistently improved delay over the original, 4% on average, without increase in computation time.

In this paper, we propose multivariate tensor-based surface morphometry, a new method for surface analysis, using holomorphic differentials; we also apply it to study brain anatomy. Differential forms provide a natural way to parameterize 3D surfaces, but the multivariate statistics of the resulting surface metrics have not previously been investigated. We computed new statistics from the Riemannian metric tensors that retain the full information in the deformation tensor fields. We present the canonical holomorphic one-forms with improved numerical accuracy and computational efficiency. We applied this framework to 3D MRI data to analyze hippocampal surface morphometry in Alzheimer's Disease (AD; 12 subjects), lateral ventricular surface morphometry in HIV/AIDS (11 subjects) and biomarkers in lateral ventricles in HIV/AIDS (11 subjects). Experimental results demonstrated that our method powerfully detected brain surface abnormalities. Multivariate statistics on the local tensors outperformed other TBM methods including analysis of the Jacobian determinant, the largest eigenvalue, or the pair of eigenvalues, of the surface Jacobian matrix.

Two surfaces are conformally equivalent if there exists a bijective angle-preserving map between them. The Teichmüller space for surfaces with the same topology is a finite-dimensional manifold, where each point represents a conformal equivalence class, and the conformal map is homotopic to the identity map. In this paper, we propose a novel method to apply conformal equivalence based shape index to study brain morphometry. The shape index is defined based on Teichmüller space coordinates. It is intrinsic, and invariant under conformal transformations, rigid motions and scaling. It is also simple to compute; no registration of surfaces is needed. Using the Yamabe flow method, we can conformally map a genus-zero open boundary surface to the Poincaré disk. The shape indices that we compute are the lengths of a special set of geodesics under hyperbolic metric. By computing and studying this shape index and its statistical behavior, we can analyze differences in anatomical morphometry due to disease or development. Study on twin lateral ventricular surface data shows it may help detect generic influence on lateral ventricular shapes. In leave-one-out validation tests, we achieved 100% accurate classification (versus only 68% accuracy for volume measures) in distinguishing 11 HIV/AIDS individuals from 8 healthy control subjects, based on Teichmüller coordinates for lateral ventricular surfaces extracted from their 3D MRI scans.Our conformal invariants, the Teichmüller coordinates, successfully classified all lateral ventricular surfaces, showing their promise for analyzing anatomical surface morphometry.

This paper considers two approaches to perform image restoration while preserving the contrast. The first one is the Total Variation-based Bregman iterations while the second consists in the minimization of an energy that involves robust edge preserving regularization. We show that these two approaches can be derived form a common framework. This allows us to deduce new properties and to extend and generalize these two previous approaches.

We propose and analyze a nonparametric region-based active contour model for segmenting cluttered scenes. The proposed model is unsupervised and assumes pixel intensity is independently identically distributed. Our proposed energy functional consists of a geometric regularization term that penalizes the length of the partition boundaries and a region-based image term that uses histograms of pixel intensity to distinguish different regions. More specifically, the region data encourages segmentation so that local histograms within each region are approximately homogeneous. An advantage of using local histograms in the data term is that histogram differentiation is not required to solve the energy minimization problem. We use Wasserstein distance with exponent 1 to determine the dissimilarity between two histograms. The Wasserstein distance is a metric and is able to faithfully measure the distance between two histograms, compared to many pointwise distances. Moreover, it is insensitive to oscillations, and therefore our model is robust to noise. A fast global minimization method based on (Chan et al. in SIAM J. Appl. Math. 66(5):1632–1648, 2006 ; Bresson et al. in J. Math. Imaging Vis. 28(2):151–167, 2007 ) is employed to solve the proposed model. The advantages of using this method are two-fold. First, the computational time is less than that of the method by gradient descent of the associated Euler-Lagrange equation (Chan et al. in Proc. of SSVM, pp. 697–708, 2007 ). Second, it is able to find a global minimizer. Finally, we propose a variant of our model that is able to properly segment a cluttered scene with local illumination changes.

This paper examines the issue of scale in modeling texture for the purpose of segmentation. We propose a scale descriptor for texture and an energy minimization model to find the scale of a given texture at each location. For each pixel, we use the intensity distribution in a local patch around that pixel to determine the smallest size of the domain that can be used to generate neighboring patches. The energy functional we propose to minimize is comprised of three terms: The first is the dissimilarity measure using the Wasserstein distance or Kullback-Leibler divergence between neighboring patch distributions; the second maximizes the entropy of the local patch, and the third penalizes larger size at equal fidelity. Our experiments show the proposed scale model successfully captures the intrinsic scale of texture at each location. We also apply our scale descriptor for improving texture segmentation based on histogram matching [15].

In this work, we address the problem of segmenting multiple objects, under possible occlusions, in a level set framework. A variational energy that incorporates a piecewise constant representation of the image in terms of the object regions and the object spatial order is proposed. To resolve occluded boundaries, prior knowledge of the shape of objects is also introduced within the segmentation energy. By minimizing the above energy, we solve the segmentation with depth problem, i.e., estimating the object boundaries, the object intensities, and the spatial order. The segmentation with depth problem was originally dealt with by the Nitzberg–Mumford–Shiota (NMS) variational formulation, which proposes segmentation energies for each spatial order. We discuss the relationships and show the computational advantages of our formulation over the NMS model, mainly due to our treatment of spatial order estimation within a single energy. A novelty here is that the spatial order information available in the image model is used to dynamically impose prior shape constraints only to occluded boundaries. Also presented are experiments on synthetic and real images that have promising results.

This paper proposes an algorithm to solve most of existing active contour problems based on the approach of mean curvature motion proposed by Chambolle (2004) and the image denoising model of Rudin, Osher and Fatemi (ROF) (1992). More precisely, the motion of active contours is discretized by the ROF model applied to the signed distance of the evolving contour. The advantage of this new discretization scheme is to use a time step much larger than in standard explicit schemes, which means that less iterations are needed to converge to the steady state solution. We present results on 2-D natural images.

We propose and study the notion of dense regions for the analysis of categorized gene expression data and present some searching algorithms for discovering them. The algorithms can be applied to any categorical data matrices derived from gene expression level matrices. We demonstrate that dense regions are simple but useful and statistically significant patterns that can be used to 1) identify genes and/or samples of interest and 2) eliminate genes and/or samples corresponding to outliers, noise, or abnormalities. Some theoretical studies on the properties of the dense regions are presented which allow us to characterize dense regions into several classes and to derive tailor-made algorithms for different classes of regions. Moreover, an empirical simulation study on the distribution of the size of dense regions is carried out which is then used to assess the significance of dense regions and to derive effective pruning methods to speed up the searching algorithms. Real microarray data sets are employed to test our methods. Comparisons with six other well-known clustering algorithms using synthetic and real data are also conducted which confirm the superiority of our methods in discovering dense regions. The DRIFT code and a tutorial are available as supplemental material, which can be found on the Computer Society Digital Library at http://computer.org/tcbb/archives.htm.

In medical imaging, parameterized 3-D surface models are useful for anatomical modeling and visualization, statistical comparisons of anatomy, and surface-based registration and signal processing. Here we introduce a parameterization method based on Riemann surface structure, which uses a special curvilinear net structure (conformal net) to partition the surface into a set of patches that can each be conformally mapped to a parallelogram. The resulting surface subdivision and the parameterizations of the components are intrinsic and stable (their solutions tend to be smooth functions and the boundary conditions of the Dirichlet problem can be enforced). Conformal parameterization also helps transform partial differential equations (PDEs) that may be defined on 3-D brain surface manifolds to modified PDEs on a two-dimensional parameter domain. Since the Jacobian matrix of a conformal parameterization is diagonal, the modified PDE on the parameter domain is readily solved. To illustrate our techniques, we computed parameterizations for several types of anatomical surfaces in 3-D magnetic resonance imaging scans of the brain, including the cerebral cortex, hippocampi, and lateral ventricles. For surfaces that are topologically homeomorphic to each other and have similar geometrical structures, we show that the parameterization results are consistent and the subdivided surfaces can be matched to each other. Finally, we present an automatic sulcal landmark location algorithm by solving PDEs on cortical surfaces. The landmark detection results are used as constraints for building conformal maps between surfaces that also match explicitly defined landmarks.

Anatomical features on cortical surfaces are usually represented by landmark curves, called sulci/gyri curves. These landmark curves are important information for neuroscientists to study brain diseases and to match different cortical surfaces. Manual labelling of these landmark curves is time-consuming, especially when there is a large set of data. In this paper, we proposed to trace the landmark curves on cortical surfaces automatically based on the principal directions. Suppose we are given the global conformal parametrization of a cortical surface, By fixing two endpoints, the anchor points, we propose to trace the landmark curves iteratively on the spherical/rectangular parameter domain along the principal direction. Consequently, the landmark curves can be mapped onto the cortical surface. To speed up the iterative scheme, a good initial guess of the landmark curve is necessary. We proposed a method to get a good initialization by extracting the high curvature region on the cortical surface using the Chan-Vese segmentation. This involves solving a PDE on the manifold using our global conformal parametrization technique. Experimental results show that the landmark curves detected by our algorithm closely resemble to those manually labelled curves. As an application, we used these automatically labelled landmark curves to build average cortical surfaces with an optimized brain conformal mapping method. Experimental results show our method can help automatically matching brain cortical surfaces.

The multilevel placement package mPL6 combines improved implementations of the global placer mPL5 (ISPD05) and the XDP legalizer and detailed placer (ASPDAC06). It consistently produces robust, high-quality solutions to difficult instances of mixed-size placement in fast and scalable run time. Best-choice clustering (ISPD05) is used to construct a hierarchy of problem formulations. Generalized force-directed placement guides global placement at each level of the cluster hierarchy. During the declustering pass from coarsest to finest level, large movable objects are gradually fixed in positions without overlapping with one another. This progressive legalization of large objects during continuous optimization supports determination of a completely overlap-free configuration as close as possible to the continuous solution. Various discrete heuristics are applied to this legalized placement in order to improve the final wirelength.

Density-based clustering has the advantages for 1) allowing arbitrary shape of cluster and 2) not requiring the number of clusters as input. However, when clusters touch each other, both the cluster centers and cluster boundaries (as the peaks and valleys of the density distribution) become fuzzy and difficult to determine. We introduce the notion of cluster intensity function (CIF) which captures the important characteristics of clusters. When clusters are well-separated, CIFs are similar to density functions. But, when clusters become closed to each other, CIFs still clearly reveal cluster centers, cluster boundaries, and degree of membership of each data point to the cluster that it belongs. Clustering through bump hunting and valley seeking based on these functions are more robust than that based on density functions obtained by kernel density estimation, which are often oscillatory or oversmoothed. These problems of kernel density estimation are resolved using Level Set Methods and related techniques. Comparisons with two existing density-based methods, valley seeking and DBSCAN, are presented which illustrate the advantages of our approach.

We propose a level set based variational approach that incorporates shape priors into Chan-Vese's model for the shape prior segmentation problem. In our model, besides the level set function for segmentation, as in Cremers' work, we introduce another labelling level set function to indicate the regions on which the prior shape should be compared. Our model can segment an object, whose shape is similar to the given prior shape, from a background where there are several objects. Moreover, we provide a proof for a fast solution principle, which was mentioned by F. Gibou et al., and similar to the one proposed in [B. Song et al., (2002)], for minimizing Chan-Vese's segmentation model without length term. We extend the principle to the minimization of our prescribed functionals.

We propose a general method that parameterizes general surfaces with complex (possible branching) topology using Riemann surface structure. Rather than evolve the surface geometry to a plane or sphere, we instead use the fact that all orientable surfaces are Riemann surfaces and admit conformal structures, which induce special curvilinear coordinate systems on the surfaces. We can then automatically partition the surface using a critical graph that connects zero points in the global conformal structure on the surface. The trajectories of iso-parametric curves canonically partition a surface into patches. Each of these patches is either a topological disk or a cylinder and can be conformally mapped to a parallelogram by integrating a holomorphic I-form defined on the surface. The resulting surface subdivision and the parameterizations of the components are intrinsic and stable. For surfaces with similar topology and geometry, we show that the parameterization results are consistent and the subdivided surfaces can be matched to each other using constrained harmonic maps. The surface similarity can be measured by direct computation of distance between each pair of corresponding points on two surfaces. To illustrate the technique, we computed conformal structures for anatomical surfaces in MRI scans of the brain and human face surfaces. We found that the resulting parameterizations were consistent across subjects, even for branching structures such as the ventricles, which are otherwise difficult to parameterize. Our method provides a surface-based framework for statistical comparison of surfaces and for generating grids on surfaces for PDE-based signal processing.

Restoring binary images is a problem which arises in various application fields. In our paper, this problem is considered in a variational framework: the sought-after solution minimizes an energy. Energies defined over the set of the binary images are inevitably nonconvex and there are no general methods to calculate the global minimum, while local minimizers are very often of limited interest. In this paper we define the restored image as the global minimizer of the total-variation (TV) energy functional constrained to the collection of all binary-valued images. We solve this constrained non-convex optimization problem by deriving another functional which is convex and whose (unconstrained) minimum is proven to be reached for the global minimizer of the binary constrained TV functional. Practical issues are discussed and a numerical example is provided.

The most recent version of the mPL multilevel placement algorithm, mPL6, is reviewed. This version is derived from the mPL5 placer (ISPD05) and the Patoma floorplanner (ASPDAC05). It is also augmented by new techniques for detailed placement. As a result, it can handle mixed-size placement very effectively. First-choice clustering is used to construct a hierarchy of problem formulations. Generalized force-directed placement guides global placement at each level of the cluster hierarchy. Prior to interpolation of each coarse-level solution to its adjacent finer level, however, recursive, top-down displacement-minimizing floorplanning optimizes block orientations and checks that overlap can be removed at the current level. Where necessary, the floor-planner perturbs coarse-level solutions enough that legalization of the given placement can be assured. The resulting flow is scalable and robust, and it produces very low-wirelength solutions for known benchmark circuits.

Automatic circuit placement has received renewed interest recently given the rapid increase of circuit complexity, increase of interconnect delay, and potential sub-optimality of existing placement algorithms [13]. In this paper we present a generalized force-directed algorithm embedded in mPL2's [12] multilevel framework. Our new algorithm, named mPL5, produces the shortest wirelength among all published placers with very competitive runtime on the IBM circuits used in [29]. The new contributions and enhancements are: (1) We develop a new analytical placement algorithm using a density constrained minimization formulation which can be viewed as a generalization of the force-directed method in [16]; (2) We analyze and identify the advantages of our new algorithm over the force-directed method; (3) We successfully incorporate the generalized force-directed algorithm into a multilevel framework which significantly improves wirelength and speed. Compared to Capo9.0, our algorithm mPL5 produces 8% shorter wirelength and is 2X faster. Compared to Dragon3.01, mPL5 has 3% shorter wirelength and is 12X faster. Compared to Fengshui5.0, it has 5% shorter wirelength and is 2X faster. Compared to the ultra-fast placement algorithm: FastPlace, mPL5 produces 8% shorter wirelength but is 6X slower. A fast mode of mPL5 (mPL5-fast) can produce 1% shorter wirelength than Fast-Place1.0 and is only 2X slower. Moreover, mPL5-fast has demonstrated better scalability than FastPlace1.0.

We developed a general method for global conformal parameterizations based on the structure of the cohomology group of holomorphic one-forms for surfaces with or without boundaries (Gu and Yau, 2002), (Gu and Yau, 2003). For genus zero surfaces, our algorithm can find a unique mapping between any two genus zero manifolds by minimizing the harmonic energy of the map. In this paper, we apply the algorithm to the cortical surface matching problem. We use a mesh structure to represent the brain surface. Further constraints are added to ensure that the conformal map is unique. Empirical tests on magnetic resonance imaging (MRI) data show that the mappings preserve angular relationships, are stable in MRIs acquired at different times, and are robust to differences in data triangulation, and resolution. Compared with other brain surface conformal mapping algorithms, our algorithm is more stable and has good extensibility.

Motivated by the classical TV (total variation) restoration model, we propose a new nonlinear filter-the digital TV filter for denoising and enhancing digital images, or more generally, data living on graphs. The digital TV filter is a data dependent lowpass filter, capable of denoising data without blurring jumps or edges. In iterations, it solves a global total variational (or L(1)) optimization problem, which differs from most statistical filters. Applications are given in the denoising of one dimensional (1-D) signals, two-dimensional (2-D) data with irregular structures, gray scale and color images, and nonflat image features such as chromaticity.

We propose a new model for active contours to detect objects in a given image, based on techniques of curve evolution, Mumford-Shah (1989) functional for segmentation and level sets. Our model can detect objects whose boundaries are not necessarily defined by the gradient. We minimize an energy which can be seen as a particular case of the minimal partition problem. In the level set formulation, the problem becomes a "mean-curvature flow"-like evolving the active contour, which will stop on the desired boundary. However, the stopping term does not depend on the gradient of the image, as in the classical active contour models, but is instead related to a particular segmentation of the image. We give a numerical algorithm using finite differences. Finally, we present various experimental results and in particular some examples for which the classical snakes methods based on the gradient are not applicable. Also, the initial curve can be anywhere in the image, and interior contours are automatically detected.

We have designed and implemented a new class of fast and highly scalable placement algorithms that directly handle complex constraints and achieve total wirelengths comparable to the state of the art. Our approach exploits recent advances in (i) multilevel methods for hierarchical computation, (ii) interior-point methods for nonconvex nonlinear programming, and (iii) the Fast Multipole Method for the order N evaluation of sums over the N(N-1)/2 pairwise interactions of N components. Significant adaptation of these methods for the placement problem is required, and we have therefore developed a set of customized discrete algorithms for clustering, declustering, slot assignment, and local refinement with which the continuous algorithms are naturally combined. Preliminary test runs on benchmark circuits with up to 184000 cells produce total wirelengths within approximately 5-10% of those of GORDIAN-L in less than one tenth the run time. Such an ultra-fast placement engine is badly needed for timing convergence of the synthesis and layout phases of integrated circuit design.

In this paper, we propose using partial differential equation (PDE) techniques in wavelet based image processing to reduce edge artifacts generated by wavelet thresholding. We employ minimization techniques, in particular the minimization of total variation, to modify the retained standard wavelet coefficients so that the reconstructed images have less oscillations near edges. Numerical experiments show that this approach improves the reconstructed image quality in wavelet compression and in denoising.

In PDE image restoration problems, one has to invert operators which is a sum of a blurring operator and an elliptic operator with highly varying coefficient. We present a preconditioner for such operators, which can be used with the conjugate gradient (CG) method, and compare it with Vogel and Oman's (see SIAM J. Sci. Stat. Comput., vol.17, p.227-38, 1996, and IEEE Trans. Image Processing, vol.7, p.813-24, 1998) product preconditioner.

Summary form only given. We consider the possibility of high loss compression of very noisy images such as images from ATR, ATM and surveillance imaging, in which images are taken in a high noise environment. Our goal is that after the high loss compression, the salient features (edges) of the images will be still preserved so that the shape and location of the objects can be well recognized. For very noisy images, high loss wavelet compression usually results in feature loss since edges generate high frequencies and they are removed along with the noise. We advocate a feature-retaining denoising method, followed by wavelet hard thresholding compression to get a high ratio compression which still keeps the features. In particular, we consider the total variation (TV) denoising method which can smooth out the high frequency noise while keeping the edges. Numerical experiments indicate that more wavelet coefficients of the TV-denoised images are closer to zero so that they can be eventually removed in the compression process while the coefficients that are generated by the edges are still relatively large and therefore automatically retained.

A linear wirelength objective more effectively captures timing, congestion, and other global placement considerations than a squared wirelength objective. The GORDIAN-L cell placement tool minimizes linear wirelength by first approximating the linear wirelength objective by a modified squared wirelength objective, then executing the following loop-(1) minimize the current objective to yield some approximate solution and (2) use the resulting solution to construct a more accurate objective-until the solution converges. This paper shows how to apply a generalization of an algorithm due to Weiszfeld (1937) to placement with a linear wirelength objective and that the main GORDIAN-L loop is actually a special case of this algorithm. We then propose applying a regularization parameter to the generalized Weiszfeld algorithm to control the tradeoff between convergence and solution accuracy; the GORDIAN-L iteration is equivalent to setting this regularization parameter to zero. We also apply novel numerical methods, such as the primal-Newton and primal-dual Newton iterations, to optimize the linear wirelength objective. Finally, we show both theoretically and empirically that the primal-dual Newton iteration stably attains quadratic convergence, while the generalized Weiszfeld iteration is linear convergent. Hence, primal-dual Newton is a superior choice for implementing a placer such as GORDIAN-L, or for any linear wirelength optimization.

We propose a new definition of the total variation (TV) norm for vector-valued functions that can be applied to restore color and other vector-valued images. The new TV norm has the desirable properties of 1) not penalizing discontinuities (edges) in the image, 2) being rotationally invariant in the image space, and 3) reducing to the usual TV norm in the scalar case. Some numerical experiments on denoising simple color images in red-green-blue (RGB) color space are presented.

In this paper, we present a blind deconvolution algorithm based on the total variational (TV) minimization method proposed. The motivation for regularizing with the TV norm is that it is extremely effective for recovering edges of images as well as some blurring functions, e.g., motion blur and out-of-focus blur. An alternating minimization (AM)implicit iterative scheme is devised to recover the image and simultaneously identify the point spread function (psf). Numerical results indicate that the iterative scheme is quite robust, converges very fast (especially for discontinuous blur), and both the image and the psf can be recovered under the presence of high noise level. Finally, we remark that psf's without sharp edges, e.g., Gaussian blur, can also be identified through the TV approach.

The "quadratic placement" methodology is rooted in [Module Placement Based on Resistive Network Optimization, Proud: A Sea-Of-Gate Placement Algorithm, A Combined Force and Cut Algorithm for Hierarchical VLSI Layout]and is reputedly used in many commercial and in-house tools forplacement of standard-cell and gate-array designs. The methodologyiterates between two basic steps: solving sparse systems oflinear equations, and repartitioning. This work dissects the implementationand motivations for quadratic placement. We firstshow that (i) Krylov subspace engines for solving sparse systemsof linear equations are more effective than the traditional successiveover-relaxation (SOR) engine [A Unified Approach to Partitioning and Placement] and (ii) order convergence criteriacan maintain solution quality while using substantially fewersolver iterations. We then discuss the motivations and relevanceof the quadratic placement approach, in the context of past and futurealgorithmic technology, performance requirements, and designmethodology. We provide evidence that the use of numerical linearsystems solvers with quadratic wirelength objective may be due tothe pre-1990's weakness of min-cut partitioners, i.e., numerical engineswere needed to provide helpful hints to min-cut partitioners.Finally, we note emerging methodology drivers in deep-submicrondesign that may require new placement approaches to the placement problem.

We describe some numerical techniques for the total variation image restoration method, namely a primal-dual linearization for the Euler-Lagrange equations and some preconditioning issues. We also highlight extension of this technique to color images, blind deconvolution and the staircasing effect.

Article Faster minimization of linear wirelength for global placement Share on Authors: Charles J. Alpert IBM Austin Research Laboratory, Austin, TX IBM Austin Research Laboratory, Austin, TXView Profile , Tony F. Chan UCLA Mathematics Department, Los Angeles, CA UCLA Mathematics Department, Los Angeles, CAView Profile , Dennis J.-H. Huang UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile , Andrew B. Kahng UCLA Computer Science Department, Los Angeles, CA and Cadence Design Systems, Inc., San Jose, CA UCLA Computer Science Department, Los Angeles, CA and Cadence Design Systems, Inc., San Jose, CAView Profile , Igor L. Markov UCLA Mathematics Department, Los Angeles, CA UCLA Mathematics Department, Los Angeles, CAView Profile , Pep Mulet UCLA Mathematics Department, Los Angeles, CA UCLA Mathematics Department, Los Angeles, CAView Profile , Kenneth Yan UCLA Computer Science Department, Los Angeles, CA UCLA Computer Science Department, Los Angeles, CAView Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997 Pages 4–11https://doi.org/10.1145/267665.267670Online:01 April 1997Publication History 17citation150DownloadsMetricsTotal Citations17Total Downloads150Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper presents FORTRAN 77 implementations of the lookahead Levinson algorithm of Chan and Hansen (7, 8) for solving symmetric indefinite and general Toeplitz systems. The algorithms are numerically stable for all Toeplitz matrices that do not have many consecutive ill-conditioned leading principal submatrices, and also produce estimates of the algorithm and matrix condition numbers. In contrast, the classical Levinson algorithm is only guaranteed to be numerically stable for symmetric positive definite Toeplitz matrices, and no condition estimate is produced.

In many fields of signal and image processing control, and telecommunication there is much interest today in the numerical techniques offered by linear algebra. The singular value decomposition (SVD) is one of the techniques which have proven useful in many engineering applications, but unfortunately its computation is a costly procedure. The QR factorization (QRF) requires much less computational effort, but rank and null-space estimates are not necessarily reliable. This paper presents a version of rank revealing QR (RRQR) algorithm which is suited for implementation on a VLSI systolic array. The implementation of the RRQRF requires n(n+1)/2 processors and O(n) external buffers, for a problem of order n. The execution time for the algorithm is O(nr), where r is A's numerical rank.>

This paper presents FORTRAN 77 implementations of the lookahead Levinson algorithm of Chan and Hansen [7, 8] for solving symmetric indefinite and general Toeplitz systems. The algorithms are numerically stable for all Toeplitz matrices that do not have manyconsecutiveill-conditioned leading principal submatrices, and also produce estimates of the algorithm and matrix condition numbers. In contrast, the classical Levinson algorithm is only guaranteed to be numerically stable for symmetric positive definite Toeplitz matrices, and no condition estimate is produced.

There has been a recent emergence of many interesting and highly efficient hierarchical (multilevel) algorithms (e.g. multigrid, domain decomposition, wavelets, multilevel preconditioning, the fast multipole algorithms, etc.) for solving numerical problems in scientific computing. These algorithms derive their efficiency from using a hierarchical approach to capture the sharing of global information which is inherent in the physical processes being modelled. In addition to being computationally efficient, these algorithms also possess relatively high degrees of parallelism. I therefore argue that the architectures of parallel computers (especially massively parallel ones) should be designed to support hierarchical communication and synchronization needs of these algorithms. Hierarchical architectures are also more universal because they go beyond supporting a particular class of algorithms to supporting the underlying physical processes being modelled. Finally, I propose that algorithm designers take a critical look at traditional kernel algorithms and re-examine their cost-effectiveness in a massively parallel computing environment.

This paper examines several ways of implementing multigrid algorithms on the hypercube multiprocessor. We consider both the standard multigrid algorithms and a concurrent version proposed by Gannon and Van Rosendale. We present several mappings of the mesh points onto the nodes of the cube. The main property of these mappings, which are based on binary reflected Gray codes, is that the distance between neighboring grid points remains constant from one grid level to another. This results in a communication effective implementation of multigrid algorithms on the hypercube multiprocessor.

The most well-known and widely used algorithm for computing the Singular Value Decomposition (SVD) A ---U ~V T of an m x n rectangular matrix A is the Golub-Reinsch algorithm (GR-SVD).In this paper, an improved version of the original GR-SVD algorithm is presented.The new algorithm works best for matrices with m >> n, but is more efficient even when m is only slightly greater than n (usually when m ~ 2n) and in some cases can achieve as much as 50 percent savings.If the matrix U ~s exphcltly desired, then n 2 extra storage locations are required, but otherwise no extra storage is needed.The two main modifications are: (1) first triangularizing A by Householder transformations before bldmgonahzing it (thin idea seems to be widely known among some researchers in the field, but as far as can be determined, neither a detailed analysis nor an lmplementatmn has been published before), and (2) accumulating the left Givens transformations in GR-SVD on an n x n array instead of on an m x n array.A PFORT-verified FORTRAN Implementation m included.Comparisons with the EISPACK SVD routine are given.

The set of FORTRAN subroutines given here is an implementation of the algorithm [1] for computing the Singular Value Decomposition (SVD) of a general m by n rectangular matrix A defined as A = UWV T, where U is an m × min(m,n) matrix containing the left singular vectors, W is a diagonal matrix of size min(m, n) containing the singular values, and V is an n x min(m, n) matrix containing the right singular vectors.Note that m is allowed to be greater than or less than n.For ease of presentation, we assume m to be greater than or equal to n in the following discussion.The algorithm is an improvement of the Golub-Reinsch algorithm [4], which is implemented in subroutines SVD and MINFIT in EISPACK [3] and in subroutine SSVDC in LINPACK [2].It should be more efficient than the Golub-Reinsch algorithm when m is approximately larger tJ lan 2n, as is the case in many least squares applications.The algorithm has a hybrid nature.When m is aboat equal to n, the Golub-Reinsch algorithm is employed.When the ratio m/n is larger than a threshold value, which is determined by detailed operation counts [1], the improved algorithm is used.The improved algorithm first computes the QR factorization of A using Householder transformations, and then uses the Golub-Reinsch algorithm on R. A further improvement over the Golub-Reinsch algorithm is when the left singular

Reflecting on four years of numermal consultmg at the Stanford Lmear Accelerator Center, we pomt out solved and outstandmg problems m selecting and mstalhng mathematical software, helpmg users, maintaining the hbrary and momtormg its use, and managing the consulting operatmn Key Words and Phrases.hbrary management and orgamzatmn, mathematmal software, numerical analysis CR Categories: 4.6, 5 1 W h e r e no counsel is, t h e people fall: b u t in t h e m u l t i t u d e of counsellors t h e r e is safety.