A topology preserving level set method for geometric deformable models

Active contour and surface models, also known as deformable models, are powerful image segmentation techniques. Geometric deformable models implemented using level set methods have advantages over parametric models due to their intrinsic behavior, parameterization independence, and ease of implementation. However, a long claimed advantage of geometric deformable models-the ability to automatically handle topology changes-turns out to be a liability in applications where the object to be segmented has a known topology that must be preserved. We present a new class of geometric deformable models designed using a novel topology-preserving level set method, which achieves topology preservation by applying the simple point concept from digital topology. These new models maintain the other advantages of standard geometric deformable models including subpixel accuracy and production of nonintersecting curves or surfaces. Moreover, since the topology-preserving constraint is enforced efficiently through local computations, the resulting algorithm incurs only nominal computational overhead over standard geometric deformable models. Several experiments on simulated and real data are provided to demonstrate the performance of this new deformable model algorithm.     

A migration strategy for automating a vision-based concentricity inspection station

This paper presents the development of an automation migration strategy in transforming a manual visual inspection work cell into a semi-automated one for a medical device manufacturer in China. The object under study is a washer/magnet subassembly used in an air release valve. These two circular components must be bonded concentrically and then inspected with bare eyes by a human inspector. Such inspection process was prone to error as the inspector struggled to keep up with the production cycle time. The methodology employed in this research consists of four steps. First, we examined the cost of rework through the Pareto analysis. The results indicated that the washer/magnet misalignment accounted for more than 40% of valve defects and thus deserved immediate attention. Next, we conducted two Kappa analyses to evaluate repeatability and reproducibility of the human inspectors assigned to perform the inspection tasks. The results showed that the human inspectors failed to pass these tests and a suitable automation solution must be sought. Afterwards, efforts were made to develop a vision based semi-automated concentricity inspection station to eliminate human inspection errors. Hardware setup, software algorithms, lighting and other supporting devices are presented in this paper as well as potential savings for such an installment. Finally, we conducted an economical analysis to compare the semi-automated solution with a fully automated one to identify the best automation migration strategy. The analysis results showed that the semi-automated solution was a favorable choice due to a shorter payback period and its ease of reinstallation if the factory is to be relocated.     

A multiresolution descriptor for deformable 3D shape retrieval

In this paper, we present a spectral graph wavelet framework for the analysis and design of efficient shape signatures for nonrigid 3D shape retrieval. Although this work focuses primarily on shape retrieval, our approach is, however, fairly general and can be used to address other 3D shape analysis problems. In a bid to capture the global and local geometry of 3D shapes, we propose a multiresolution signature via a cubic spline wavelet generating kernel. The parameters of the proposed signature can be easily determined as a trade-off between effectiveness and compactness. Experimental results on two standard 3D shape benchmarks demonstrate the much better performance of the proposed shape retrieval approach in comparison with three state-of-the-art methods. Additionally, our approach yields a higher retrieval accuracy when used in conjunction with the intrinsic spatial partition matching.     

3D anatomical shape atlas construction using mesh quality preserved deformable models

3D anatomical shape atlas construction has been extensively studied in medical image analysis research, owing to its importance in model-based image segmentation, longitudinal studies and populational statistical analysis, etc. Among multiple steps of 3D shape atlas construction, establishing anatomical correspondences across subjects, i.e., surface registration, is probably the most critical but challenging one. Adaptive focus deformable model (AFDM) [1] was proposed to tackle this problem by exploiting cross-scale geometry characteristics of 3D anatomy surfaces. Although the effectiveness of AFDM has been proved in various studies, its performance is highly dependent on the quality of 3D surface meshes, which often degrades along with the iterations of deformable surface registration (the process of correspondence matching). In this paper, we propose a new framework for 3D anatomical shape atlas construction. Our method aims to robustly establish correspondences across different subjects and simultaneously generate high-quality surface meshes without removing shape details. Mathematically, a new energy term is embedded into the original energy function of AFDM to preserve surface mesh qualities during deformable surface matching. More specifically, we employ the Laplacian representation to encode shape details and smoothness constraints. An expectation–maximization style algorithm is designed to optimize multiple energy terms alternatively until convergence. We demonstrate the performance of our method via a set of diverse applications, including a population of sparse cardiac MRI slices with 2D labels, 3D high resolution CT cardiac images and rodent brain MRIs with multiple structures. The constructed shape atlases exhibit good mesh qualities and preserve fine shape details. The constructed shape atlases can further benefit other research topics such as segmentation and statistical analysis.     

A CAD-based 3D data acquisition strategy for inspection

The use of a laser range sensor in the 3D digitalization process allows significant improvement in acquisition speed and in 3D measurement point density. However, if we want to use these 3D data in applications that require data with a high degree of accuracy like inspection tasks, it is mandatory that the 3D points be acquired under the best conditions of accuracy. During 3D capture of a part, several sources of error can alter the measured values. Thus we must find and model the most important parameters affecting the accuracy of the range sensor. This error model, along with the CAD model of the part, is used to produce a sensing plan to completely and accurately acquire the geometry of the part. The sensing plan is comprised of the set of viewpoints that defines the exact position and orientation of the camera relative to the part. There is no limitation with regard to the shape of the part to be digitalized. An autosynchronized range sensor fixed on a coordinate measuring machine was used. For this sensor, the accuracy of the 3D measured points is a function of the distance and of the angle of incidence relative to the surface. The strategy proposed to find the acquisition plan guarantees that the viewpoints meet the best accuracy conditions in the scanning process, solving the occlusion problems. It was found that the 3D data acquired by using the proposed strategy are around 30% more accurate than the 3D data obtained in a standard acquisition.Received: 6 May 2001, Accepted: 8 November 2002, Published online: 13 November 2003 Correspondence to: Flavio Prieto     

A multimodal approach for 3D face modeling and recognition using 3D deformable facial mask

We present a multimodal approach for face modeling and recognition. The algorithm uses three cameras to capture stereo images, two frontal and one profile, of the face. 2D facial features are extracted from one of the frontal images and a dense disparity map is computed from the two frontal images. Using the extracted 2D features and their corresponding disparities, we compute their 3D coordinates. We next align a low resolution 3D mesh model to the 3D features, re-project its vertices onto the frontal 2D image and adjust its profile silhouette vertices using the profile view image. We increase the resolution of the resulting 2D model at its center region to obtain a facial mask model covering distinctive features of the face. The 2D coordinates of the vertices, along with their disparities, result in a deformed 3D mask model specific to a given subject’s face. Our method integrates information from the extracted facial features from the 2D image modality with information from the 3D modality obtained from the stereo images. Application of the models in 3D face recognition, for 112 subjects, validates the algorithm with a 95% identification rate and 92% verification rate at 0.1% false acceptance rate.

A fast approach to deformable surface 3D tracking

Deformable surface 3D tracking is a severely under-constrained problem and great efforts have been made to solve it. A recent state-of-the-art approach solves this problem by formulating it as a second order cone programming (SOCP) problem. However, one drawback of this approach is that it is time-consuming. In this paper, we propose an effective method for 3D deformable surface tracking. First, we formulate the deformable surface tracking problem as a linear programming (LP) problem. Then, we solve the LP problem with an algorithm which converges superlinearly rather than bisection algorithm whose convergence speed is linear. Our experimental studies on synthetic and real data have demonstrated the proposed method can not only reliably recover 3D structures of surfaces but also run faster than the state-of-the-art method.     

A hierarchical dense deformable model for 3D face reconstruction from skull

3D face reconstruction from skull has been investigated deeply by computer scientists in the past two decades because it is important for identification. The dominant methods construct 3D face from the soft tissue thickness measured at a set of landmarks on skull. The quantity and position of the landmarks are very vital for 3D face reconstruction, but there is no uniform standard for the selection of the landmarks. Additionally, the acquirement of the landmarks on skull is difficult without manual assistance. In this paper, an automatic 3D face reconstruction method based on a hierarchical dense deformable model is proposed. To construct the model, the skull and face samples are acquired by CT scanner and represented as dense triangle mesh. Then a non-rigid dense mesh registration algorithm is presented to align all the samples in point-to-point correspondence. Based on the aligned samples, a global deformable model is constructed, and three local models are constructed from the segmented patches of the eye, nose and mouth. For a given skull, the globe and local deformable models are iteratively matched with it, and the reconstructed facial surface is obtained by fusing the globe and local reconstruction results. To validate the presented method, a measurement in the coefficient domain of a face deformable model is defined. The experimental results indicate that the proposed method has good performance for 3D face reconstruction from skull.     

A perceptual similarity method by pairwise comparison in a medical image case

The evolution of image techniques in medicine has improved decision making based on physicians’ experience by means of computer-aided diagnosis (CAD). This paper focuses on the development of content-based image retrieval (CBIR) and CAD techniques applied to bronchoscopies and according to different pathologies. A novel pairwise comparison method based on binary logistic regression is developed to determine those images must alike to a new image from incomplete property information, after accounting for the physicians’ appreciation of the image similarity. This method is particularly useful when problems with both a large number of features and few images are involved.     

A linear programming method for generating the most favorable weights from a pairwise comparison matrix

This paper proposes a linear programming method for generating the most favorable weights (LP-GFW) from pairwise comparison matrices, which incorporates the variable weight concept of data envelopment analysis (DEA) into the priority scheme of the analytic hierarchy process (AHP) to generate the most favorable weights for the underlying criteria and alternatives on the basis of a crisp pairwise comparison matrix. The proposed LP-GFW method can generate precise weights for perfectly consistent pairwise comparison matrices and approximate weights for inconsistent pairwise comparison matrices, which are not too far from Saaty's principal right eigenvector weights. The issue of aggregation of local most favorable weights and rank preservation methods is also discussed. Four numerical examples are examined using the LP-GFW method to illustrate its potential applications and significant advantages over some existing priority methods.     

A reputation system for e-marketplaces based on pairwise comparison

Implementing a reputation system is an effective strategy to facilitate trust and security in an online environment. In addition to that, reputation systems can help online customers through decision-making process. However, in real-world situations, these systems have to deal with plenty of problems and challenges. This paper aims to solve four problems that are common to reputation systems in e-marketplaces, namely the subjectivity of ratings, inequality of transactions, multi-context reputation and dynamic behavior of users. The proposed model starts with the pairwise comparison, which is a powerful tool for removing bias from ratings. Then, we extend the concept of pairwise comparison to contests between users. A pairwise comparison has only a winner and a loser, but we can associate a score differential with a pairwise comparison when we consider it as a match. This score differential is adjusted in a way that three other problems can be solved. We implemented our model in a multi-agent simulation in which real-world data were also incorporated. We compared our model with some of previous reputation systems. Experiments show that our model outperforms previous ones when faced with real-world challenges.     

An automated vision-based method for rapid 3D energy performance modeling of existing buildings using thermal and digital imagery

Modeling the energy performance of existing buildings enables quick identification and reporting of potential areas for building retrofit. However, current modeling practices of using energy simulation tools do not model the energy performance of buildings at their element level. As a result, potential retrofit candidates caused by construction defects and degradations are not represented. Furthermore, due to manual modeling and calibration processes, their application is often time-consuming. Current application of 2D thermography for building diagnostics is also facing several challenges due to a large number of unordered and non-geo-tagged images. To address these limitations, this paper presents a new computer vision-based method for automated 3D energy performance modeling of existing buildings using thermal and digital imagery captured by a single thermal camera. First, using a new image-based 3D reconstruction pipeline which consists of Graphic Processing Unit (GPU)-based Structure-from-Motion (SfM) and Multi-View Stereo (MVS) algorithms, the geometrical conditions of an existing building is reconstructed in 3D. Next, a 3D thermal point cloud model of the building is generated by using a new 3D thermal modeling algorithm. This algorithm involves a one-time thermal camera calibration, deriving the relative transformation by forming the Epipolar geometry between thermal and digital images, and the MVS algorithm for dense reconstruction. By automatically superimposing the 3D building and thermal point cloud models, 3D spatio-thermal models are formed, which enable the users to visualize, query, and analyze temperatures at the level of 3D points. The underlying algorithms for generating and visualizing the 3D spatio-thermal models and the 3D-registered digital and thermal images are presented in detail. The proposed method is validated for several interior and exterior locations of a typical residential building and an instructional facility. The experimental results show that inexpensive digital and thermal imagery can be converted into ubiquitous reporters of the actual energy performance of existing buildings. The proposed method expedites the modeling process and has the potential to be used as a rapid and robust building diagnostic tool.     

Interactively deformable models for surgery simulation

A methodology that addresses important issues concerned with the underlying graphical models designed for surgical simulation, as well as issues related to the real-time interactivity with, and manipulation of, these models is presented. The specific application of interest is laparoscopic surgery, which is performed using endoscopes that present a video image of the organs to the clinicians. The surgeon then performs the surgery while looking at the video monitor. The particular focus is gall bladder surgery, which involves various gastrointestinal organs. The overall objective is to simulate this environment by creating realistic, manipulable models of these organs. The models are interactively manipulable and exhibit behavior both visually acceptable and physically accurate. The approach is based on the notion of active surfaces. The rationale, mathematical formalism, and visualization techniques encompassed by the methodology are described. Recent results obtained from applying these methods to the problem of endoscopic gall bladder surgery simulation are presented     

Unsupervised deformable image registration network for 3D medical images

Image registration aims to establish an active correspondence between a pair of images. Such correspondence is critical for many significant applications, such as image fusion, tumor growth monitoring, and atlas generation. In this study, we propose an unsupervised deformable image registration network (UDIR-Net) for 3D medical images. The proposed UDIR-Net is designed in an encoder-decoder architecture and directly estimates the complex deformation field between input pairwise images without any supervised information. In particular, we recalibrate the feature slice of each feature map that is propagated between the encoder and the decoder in accordance with the importance of each feature slice and the correlation between feature slices. This method enhances the representational power of feature maps. To achieve efficient and robust training, we design a novel hierarchical loss function that evaluates multiscale similarity loss between registered image pairs. The proposed UDIR-Net is tested on different public magnetic resonance image datasets of the human brain. Experimental results show that UDIR-Net exhibits competitive performance against several state-of-the-art methods.

     

Affine-invariant geodesic geometry of deformable 3D shapes

Natural objects can be subject to various transformations yet still preserve properties that we refer to as invariants. Here, we use definitions of affine-invariant arclength for surfaces in R³ in order to extend the set of existing non-rigid shape analysis tools. We show that by re-defining the surface metric as its equi-affine version, the surface with its modified metric tensor can be treated as a canonical Euclidean object on which most classical Euclidean processing and analysis tools can be applied. The new definition of a metric is used to extend the fast marching method technique for computing geodesic distances on surfaces, where now, the distances are defined with respect to an affine-invariant arclength. Applications of the proposed framework demonstrate its invariance, efficiency, and accuracy in shape analysis.     

ASM: An adaptive simplification method for 3D point-based models

Due to the popularity of computer games and computer-animated movies, 3D models are fast becoming an important element in multimedia applications. In addition to the conventional polygonal representation for these models, the direct adoption of the original scanned 3D point set for model representation is recently gaining more and more attention due to the possibility of bypassing the time consuming mesh construction stage, and various approaches have been proposed for directly processing point-based models. In particular, the design of a simplification approach which can be directly applied to 3D point-based models to reduce their size is important for applications such as 3D model transmission and archival. Given a point-based 3D model which is defined by a point set P () and a desired reduced number of output samples n^s, the simplification approach finds a point set P_s which (i) satisfies |P_s|=n^s (|P_s| being the cardinality of P_s) and (ii) minimizes the difference of the corresponding surface S_s (defined by P_s) and the original surface S (defined by P). Although a number of previous approaches has been proposed for simplification, most of them (i) do not focus on point-based 3D models, (ii) do not consider efficiency, quality and generality together and (iii) do not consider the distribution of the output samples. In this paper, we propose an Adaptive Simplification Method (ASM) which is an efficient technique for simplifying point-based complex 3D models. Specifically, the ASM consists of three parts: a hierarchical cluster tree structure, the specification of simplification criteria and an optimization process. The ASM achieves a low computation time by clustering the points locally based on the preservation of geometric characteristics. We analyze the performance of the ASM and show that it outperforms most of the current state-of-the-art methods in terms of efficiency, quality and generality.     

Animation of deformable models

Although kinematic modelling methods are adequate for describing the shapes of static objects, they are insufficient when it comes to producing realistic animation. Physically based modelling remedies this problem by including forces, masses, strain energies and other physical quantities. The paper describes a system for the animation of deformable models. The system uses physically based modelling methods and approaches from elasticity theory for animating the models. Two different formulations, namely the primal formulation and the hybrid formulation, are implemented so that the user can select the one most suitable for an animation depending on the rigidity of the models. Collision of the models with impenetrable obstacles and constraining of the model points to fixed positions in space are implemented for use in the animations.     

A biologically inspired method for vision-based docking of wheeled mobile robots

We present a new control law for the problem of docking a wheeled robot to a target at a certain location with a desired heading. Recent research into insect navigation has inspired a solution which uses only one video camera. The control law is of the “behavioral” type in that all control actions are based on immediate visual information. Docking success under certain conditions is proved mathematically and simulation studies show the control law to be robust to camera intrinsic parameter errors. Experiments were performed for verification of the control law.     

An unequal error protection method for progressively transmitted 3D models

In this paper, we present a packet-loss resilient system for the transmission of progressively compressed three-dimensional (3D) models. It is based on a joint source and channel coding approach that trades off geometry precision for increased error resiliency to optimize the decoded model quality on the client side. We derive a theoretical framework for the overall system by which the channel packet loss behavior and the channel bandwidth can be directly related to the decoded model quality at the receiver. First, the 3D model is progressively compressed into a base mesh and a number of refinement layers. Then, we assign optimal forward error correction code rates to protect these layers according to their importance to the decoded model quality. Experimental results show that with the proposed unequal error protection approach, the decoded model quality degrades more gracefully (compared to either no error protection or equal error protection methods) as the packet-loss rate increases.     

A method for comparison of 3D surfaces using pyramidal height maps and fussy masks

A method for comparison of 3D surfaces mutually displaced in space is developed. This method is based on the measure of distinction expressed by the volume between two optimally superimposed surfaces. The volume is determined from the height map calculated with respect to a specified plane. Pyramidal representation of height maps is used to reduce the amount of examination. In addition, the maps are calculated using graphic processors. This method can be used in the problem of superposition (and identification) of identically oriented, mutually displaced surfaces.