Interactive Image Morphing on a Single-Chip Multiprocessor using a Multilayered Parallel Image Computing Library

Image morphing uses a combination of warping and image interpolation to produce a gradual visual transformation of one image into another. Due to the complexity of the operations involved in warping, creating the intermediate images that compose a “morph” is computationally intensive. Prior implementations have been slow, taking several seconds or even minutes, to compute each intermediate image. By optimizing the morphing algorithm for use on the Texas Instruments TMS320C80 Multimedia Video Processor (MVP), we have achieved interactive image morphing, which can compute an intermediate image in less than 200 ms. Using the University of Washington Image Computing Library (UWICL) for the MVP, a multilayered parallel image computing library, we were able to implement our interactive morphing algorithm with a minimum amount of programming effort. Thus, in addition to being significantly faster, our implementation is an excellent demonstration of the capability and development potential of the MVP and UWICL combination in higher-level algorithms and applications.     

同构平面三角网格的保凸变形方法

对于具有不同凸边界的同构平面三角网格的变形,提出了一种简单、有效的方法．该方法结合了两种已有的算法．能够保证网格边界在变形过程中始终保持凸性,且任意时刻的中间网格与初末网格同构,即不产生自交现象;同时文中方法实现了两个凸多边形的保凸变形。     

基于形态学的新的汉字字形自动生成方法

电子印刷,桌面出版,艺术,广告等领域对不同风格汉字的需求,迫切需求一种自动的汉字字形生成方法。传统方法只适用于两种字形相关不大的字体进行合成,并且需人干预,本文通过对字体的凸剖分,并建立两种不同字体的子凸集映射,提出了一种全新的基于形态变换的汉字形自动生成方法,     

Multiresolution morphing for planar curves

We present a multiresolution morphing algorithm using ``as-rigid-as-possible' shape interpolation combined with an angle-length based multiresolution decomposition of simple 2D piecewise curves. This novel multiresolution representation is defined intrinsically and has the advantage that the details' orientation follows any deformation naturally. The multiresolution morphing algorithm consists of transforming separately the coarse and detail coefficients of the multiresolution decomposition. Thus all LoD (level of detail) applications like LoD display, compression, LoD editing etc. can be applied directly to all morphs without any extra computation. Furthermore, the algorithm can robustly morph between very large size polygons with many local details as illustrated in numerous figures. The intermediate morphs behave natural and least-distorting due to the particular intrinsic multiresolution representation.     

Output feedback optimal guaranteed cost control of uncertain piecewise linear systems

This paper proposes the output feedback optimal guaranteed cost controller design method for uncertain piecewise linear systems based on the piecewise quadratic Lyapunov functions technique. By constructing piecewise quadratic Lyapunov functions for the closed‐loop augmented systems, the existence of the guaranteed cost controller for closed‐loop uncertain piecewise linear systems is cast as the feasibility of a set of bilinear matrix inequalities (BMIs). Some of the variables in BMIs are set to be searched by genetic algorithm (GA), then for a given chromosome corresponding to the variables in BMIs, the BMIs turn to be linear matrix inequalities (LMIs), and the corresponding non‐convex optimization problem, which minimizes the upper bound on cost function, reduces to a semidefinite programming (SDP) which is convex and can be solved numerically efficiently with the available software. Thus, the output feedback optimal guaranteed cost controller can be obtained by solving the non‐convex optimization problem using the mixed algorithm that combines GA and SDP. Numerical examples show the effectiveness of the proposed method. Copyright © 2008 John Wiley & Sons, Ltd.     

Volume-based three-dimensional metamorphosis using sphere-guided region correspondence

surface metamorphosis extends this paradigm by interpolating between discrete volume representations of the surfaces. The insensitivity of the established techniques to the surface topology enables morphing between completely different surfaces: however it can also lead to intermediate surfaces which have different topology from the originals. We present a method which improves on this situation by ensuring that no part of each surface remains disconnected during the morph. The morph is guided by region correspondence, derived automatically from a sphere representation of each surface: this can be combined with manual correspondence to retain user control over the morph. What emerges is a fast and flexible method for morphing surfaces, as demonstrated on several examples. Published online: 19 July 2001     

Polygonal Shape Blending with Topological Evolutions

This paper presents a new general approach to blend 2D shapes with different topologies. All possible topological evolutions are classified into three types by attaching three different topological cells. This formalism is resulted from Morse theory on the behavior of the 3D surface around a non-degenerate critical point. Also we incorporate degenerate topological evolutions into our framework which produce more attractive morphing effects. The user controls the morph by specifying the types of topological evolutions as well as the feature correspondences between the source and target shapes. Some techniques are also provided to control the vertex path during the morphing process. The amount of user input required to produce a morph is directly proportional to the amount of control the user wishes to impose on the process. The user may allow the system to automatically generate the morph as well. Our approaches are totally geometric based and are easy and fast enough in fully interactive time. Many experimental results show the applicability and flexibility of our approaches.     

Surface Reconstruction From Non-parallel Curve Networks

Building surfaces from cross‐section curves has wide applications including bio‐medical modeling. Previous work in this area has mostly focused on connecting simple closed curves on parallel cross‐sections. Here we consider the more general problem where input data may lie on non‐parallel cross‐sections and consist of curve networks that represent the segmentation of the underlying object by different material or tissue types (e.g., skin, muscle, bone, etc.) on each cross‐section. The desired output is a surface network that models both the exterior surface and the internal partitioning of the object. We introduce an algorithm that is capable of handling curve networks of arbitrary shape and topology on cross‐section planes with arbitrary orientations. Our algorithm is simple to implement and is guaranteed to produce a closed surface network that interpolates the curve network on each cross‐section. Our method is demonstrated on both synthetic and bio‐medical examples.     

汉字字形的凸剖分变形及合成

文中提出了一种全新的基于凸多边形变形的汉字字形自动生成方法. 通过对字体的凸剖分,把字体分解成若干个子凸多边形,并经过全局优化迭代建立两种不同字体的子凸多边形间的匹配关系,计算两匹配子凸多边形的形态和,再进行合并,则得到合成后的字体.理论上证明了此方法的正确性,讨论了不同剖分对生成字形的影响,可解决不同构字体间的合成问题,通过不同的结构元的形态变换,实现不同字体的衍生.实验证明此方法生成的汉字字形多,质量好,自动化程度高,并可用于三维字体生成.     

基于形状特征的可避免自交的平面多边形变形

给出了平面简单多边形的一种基于形状特征的可避免自交的变形方法。该方法将初始和目标多边形分别嵌入到以其放大的凸包边界为边界的同构平面三角网格中,通过采用对所嵌入的同构网格进行变形的方法,实现了平面多边形的变形。与已有的Surazhsky和Gotsman的方法相比,该方法考虑了初始和目标多边形的几何轮廓及其差异性,故变形过程更加自然,而且在网格剖分时使用了更少的额外顶点,因而提高了算法速度。     

An intuitive polygon morphing

We present a new algorithm for morphing simple polygons that is inspired by growing forms in nature. While previous algorithms require user-assisted definition of complicated correspondences between the morphing objects, our algorithm defines the correspondence by overlapping the input polygons. Once the morphing of one object into another is defined, very little or no user interaction is necessary to achieve intuitive results. Our algorithm is suitable namely for growth-like morphing. We present the basic algorithm and its three variations. One of them is suitable mainly for convex polygons, the other two are for more complex polygons, such as curved or spiral polygonal forms.     

3D Metamorphosis Between Different Types of Geometric Models

We present a powerful morphing technique based on level set methods, that can be combined with a variety of scan conversion/model processing techniques. Bringing these techniques together creates a general morphing approach that allows a user to morph a number of geometric model types in a single animation. We have developed techniques for converting several types of geometric models (polygonal meshes, CSG models and MRI scans) into distance volumes, the volumetric representation required by our level set morphing approach. The combination of these two capabilities allows a user to create a morphing sequence regardless of the model type of the source and target objects, freeing him/her to use whatever model type is appropriate for a particular animation.     

Smooth Image Sequences for Data‐driven Morphing

Smoothness is a quality that feels aesthetic and pleasing to the human eye. We present an algorithm for finding “as‐smooth‐as‐possible” sequences in image collections. In contrast to previous work, our method does not assume that the images show a common 3D scene, but instead may depict different object instances with varying deformations, and significant variation in lighting, texture, and color appearance. Our algorithm does not rely on a notion of camera pose, view direction, or 3D representation of an underlying scene, but instead directly optimizes the smoothness of the apparent motion of local point matches among the collection images. We increase the smoothness of our sequences by performing a global similarity transform alignment, as well as localized geometric wobble reduction and appearance stabilization. Our technique gives rise to a new kind of image morphing algorithm, in which the in‐between motion is derived in a data‐driven manner from a smooth sequence of real images without any user intervention. This new type of morph can go far beyond the ability of traditional techniques. We also demonstrate that our smooth sequences allow exploring large image collections in a stable manner.     

On delay‐dependent LMI‐based guaranteed cost control of uncertain neutral systems with discrete and distributed time‐varying delays

In this paper, the problem of designing robust guaranteed cost control law for a class of uncertain neutral system with a given quadratic cost function is considered. Based on Lyapunov–Krasovskii functional theory, a delay‐dependent criterion for the existence of guaranteed cost controller is expressed in the form of two linear matrix inequalities (LMIs), which can be solved by using effective LMI toolbox. Moreover, a convex optimization problem satisfying some LMI constraints is formulated to solve a guaranteed cost controller which achieves the minimization of the closed‐loop guaranteed cost. An efficient approach is proposed to design the guaranteed cost control for uncertain neutral systems. Computer software Matlab can be used to solve all the proposed results. Finally, a numerical example is illustrated to show the usefulness of our obtained design method. Copyright © 2006 John Wiley & Sons, Ltd.     

Isosurface construction in any dimension using Convex Hulls

We present an algorithm for constructing isosurfaces in any dimension. The input to the algorithm is a set of scalar values in a d-dimensional regular grid of (topological) hypercubes. The output is a set of (d-1)-dimensional simplices forming a piecewise linear approximation to the isosurface. The algorithm constructs the isosurface piecewise within each hypercube in the grid using the convex hull of an appropriate set of points. We prove that our algorithm correctly produces a triangulation of a (d-1 )-manifold with boundary. In dimensions three and four, lookup tables with 2/sup 8/ and 2/sup 16/ entries, respectively, can be used to speed the algorithm's running time. In three dimensions, this gives the popular marching cubes algorithm. We discuss applications of four-dimensional isosurface construction to time varying isosurfaces, interval volumes, and morphing.     

DMorph [image metamorphosis]

Image morphing is an artist-driven process. A creative human being looks at the images (or sequences) to be bridged and determines a way to make the changes that will be pleasing to the viewer and harmonious with the piece. To help these artists, I've developed a technique for automatically and smoothly turning one convex 3D shape into another. Like any automatic morph method, this technique should be viewed as a tool and not a self-guided process. DMorph has pros and cons. On the pro side, it is satisfyingly simple and robust and easy to program. It doesn't place any constraints on the two objects being interpolated except that they're convex. One object can be a 200-sided cone where 200 polygons all share a single vertex, and the other object a baseball, and the algorithm doesn't care. There's no feature matching, automatic or otherwise. The transformations are smooth, and the blending looks nice. On the con side, the program is limited to convex objects.     

Global Detection of Salient Convex Boundaries

As an important geometric property of many structures or structural components, convexity plays an important role in computer vision and image understanding. In this paper, we describe a general approach that can force various edge-grouping algorithms to detect only convex structures from a set of boundary fragments. The basic idea is to remove some fragments and fragment connections so that, on the remaining ones, a prototype edge-grouping algorithm that detects closed boundaries without the convexity constraint can only produce convex closed boundaries. We show that this approach takes polynomial time and preserves the grouping optimality by not excluding any valid convex boundary from the search space. Choosing the recently developed ratio-contour algorithm as the prototype grouping algorithm, we develop a new convex-grouping algorithm, which can detect convex salient boundaries with good continuity and proximity in a globally optimal fashion. To facilitate the application of this convex-grouping algorithm, we develop a new fragment-connection method based on four-point Bezier curves. We demonstrate the performance of this convex-grouping algorithm by conducting experiments on both synthetic and real images. In addition, we provide a comparison with some prior edge-grouping algorithms. Finally, we show that the proposed convex-grouping algorithm can be further extended to detect convex open boundaries, derive region-based image hierarchies, and incorporate some simple human-computer interactions.     

Recursive subdivision without the convex hull property

Recursive subdivision is a standard technique in computer aided geometric design for intersecting and rendering curves and surfaces. The convergence of recursive subdivision is critical for its effective use. Bézier and B-spline curves and surfaces have recursive subdivision algorithms that are known to converge. We show more generally that if a recursive subdivision algorithm exists for a given curve or surface type, then convergence is guaranteed if the blending functions are continuous, form a partition of unity, and are linearly independent. Thus, convergence of recursive subdivision does not depend on the convex hull property. We also show that even in the absence of the convex hull property, it is possible to define termination tests based on the flatness of control polygons, and to construct intersection algorithms based on recursive subdivision. Examples are given of polynomial curves to which our theorems apply.     

Efficient convex hull computation for planar freeform curves

We present an efficient real-time algorithm for computing the precise convex hulls of planar freeform curves. For this purpose, the planar curves are initially approximated with G¹-biarcs within a given error bound ε in a preprocessing step. The algorithm is based on an efficient construction of approximate convex hulls using circular arcs. The majority of redundant curve segments can be eliminated using simple geometric tests on circular arcs. In several experimental results, we demonstrate the effectiveness of the proposed approach, which shows the performance improvement in the range of 200-300 times speed up compared with the previous results (Elber et al., 2001) [8].