Multichannel image segmentation using adaptive finite elements

We present an adaptive finite element algorithm for segmentation with denoising of multichannel images in two dimensions, of which an extension to three dimensional images is straight forward. It is based on a level set formulation of the Mumford–Shah approach proposed by Chan and Vese in (JVCIR 11:130–141,(2000); IEEE Trans Image Proces 10(2):266–277, (2001); Int J Comp Vis 50(3):271–293, (2002)) In case of a minimal partition problem an exact solution is given and convergence of the discrete solution towards this solution is numerically verified.     

A Multiphase Level Set Framework for Image Segmentation Using the Mumford and Shah Model

We propose a new multiphase level set framework for image segmentation using the Mumford and Shah model, for piecewise constant and piecewise smooth optimal approximations. The proposed method is also a generalization of an active contour model without edges based 2-phase segmentation, developed by the authors earlier in T. Chan and L. Vese (1999. In Scale-Space'99, M. Nilsen et al. (Eds.), LNCS, vol. 1682, pp. 141–151) and T. Chan and L. Vese (2001. IEEE-IP, 10(2):266–277). The multiphase level set formulation is new and of interest on its own: by construction, it automatically avoids the problems of vacuum and overlap; it needs only log n level set functions for n phases in the piecewise constant case; it can represent boundaries with complex topologies, including triple junctions; in the piecewise smooth case, only two level set functions formally suffice to represent any partition, based on The Four-Color Theorem. Finally, we validate the proposed models by numerical results for signal and image denoising and segmentation, implemented using the Osher and Sethian level set method.     

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.     

Local Histogram Based Segmentation Using the Wasserstein Distance

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 research is supported by ONR grant N00014-09-1-0105 and NSF grant DMS-0610079.     

Active Contours with Free Endpoints

Image segmentation methods with length regularized edge sets are known to have segments whose endpoints either terminate perpendicularly to the boundary of the domain, terminate at a triple junction where three segments connect, or terminate at a free endpoint where the segment does not connect to any other edges. However, level set based segmentation methods are only able to capture edge structures which contain the first two types of segments. In this work, we propose an extension to the level set based image segmentation method in order to detect free endpoint structures. By generalizing the curve representation used in Chan and Vese (Trans. Image Proces. 10(2):266–277, 2001; Int. J. Comput. Vis. 50(3):271–293, 2002) to also include free endpoint structures, we are able to segment a larger class of edge types. Since our model is formulated using the level set framework, the curve evolution inherits useful properties such as the ability to change its topology by splitting and merging. The numerical method is provided as well as experimental results on both synthetic and real images.     

Unsupervised multiphase segmentation: A recursive approach

We propose an unsupervised multiphase segmentation algorithm based on Bresson et al.’s fast global minimization of Chan and Vese’s two-phase piecewise constant segmentation model. The proposed algorithm recursively partitions a region into two subregions, starting from the largest scale. The segmentation process automatically terminates and detects when all the regions cannot be partitioned further. The number of regions is not given and can be arbitrary. Furthermore, this method provides a full hierarchical representation that gives a structure of a given image.     

A New Mapped Weighted Essentially Non-oscillatory Scheme

The weighted essentially non-oscillatory (WENO) methods are a popular high-order spatial discretization for hyperbolic partial differential equations. Recently Henrick et al. (J. Comput. Phys. 207:542–567, 2005) noted that the fifth-order WENO method by Jiang and Shu (J. Comput. Phys. 126:202–228, 1996) is only third-order accurate near critical points of the smooth regions in general. Using a simple mapping function to the original weights in Jiang and Shu (J. Comput. Phys. 126:202–228, 1996), Henrick et al. developed a mapped WENO method to achieve the optimal order of accuracy near critical points. In this paper we study the mapped WENO scheme and find that, when it is used for solving the problems with discontinuities, the mapping function in Henrick et al. (J. Comput. Phys. 207:542–567, 2005) may amplify the effect from the non-smooth stencils and thus cause a potential loss of accuracy near discontinuities. This effect may be difficult to be observed for the fifth-order WENO method unless a long time simulation is desired. However, if the mapping function is applied to seventh-order WENO methods (Balsara and Shu in J. Comput. Phys. 160:405–452, 2000), the error can increase much faster so that it can be observed with a moderate output time. In this paper a new mapping function is proposed to overcome this potential loss of accuracy.     

A Nonlinear Multigrid Method for Total Variation Minimization from Image Restoration

Image restoration has been an active research topic and variational formulations are particularly effective in high quality recovery. Although there exist many modelling and theoretical results, available iterative solvers are not yet robust in solving such modeling equations. Recent attempts on developing optimisation multigrid methods have been based on first order conditions. Different from this idea, this paper proposes to use piecewise linear function spanned subspace correction to design a multilevel method for directly solving the total variation minimisation. Our method appears to be more robust than the primal-dual method (Chan et al., SIAM J. Sci. Comput. 20(6), 1964–1977, 1999) previously found reliable. Supporting numerical results are presented.     

Walrasian Equilibrium: Hardness,Approximations and Tractable Instances

We study the complexity issues for Walrasian equilibrium in a special case of combinatorial auction, called single-minded auction, in which every participant is interested in only one subset of commodities. Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004) showed that it is NP-hard to decide the existence of a Walrasian equilibrium for a single-minded auction and proposed a notion of approximate Walrasian equilibrium called relaxed Walrasian equilibrium. We show that every single-minded auction has a relaxed Walrasian equilibrium that satisfies at least two-thirds of the participants, proving a conjecture posed in Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004). Motivated by practical considerations, we introduce another concept of approximate Walrasian equilibrium called weak Walrasian equilibrium. We show NP-completeness and hardness of approximation results for weak Walrasian equilibria. In search of positive results, we restrict our attention to the tollbooth problem (Guruswami et al. in Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 1164–1173, 2005), where every participant is interested in a single path in some underlying graph. We give a polynomial time algorithm to determine the existence of a Walrasian equilibrium and compute one (if it exists), when the graph is a tree. However, the problem is still NP-hard for general graphs.     

Relational structures model of concurrency

The paper deals with the foundations of concurrency theory. We show how structurally complex concurrent behaviours can be modelled by relational structures (X, ¨, \sqsubset){(X, \diamondsuit, \sqsubset)} , where X is a set (of event occurrences), and ¨{\diamondsuit} (interpreted as commutativity) and \sqsubset{\sqsubset} (interpreted as weak causality) are binary relations on X. The paper is a continuation of the approach initiated in Gaifman and Pratt (Proceedings of LICS’87, pp 72–85, 1987), Lamport (J ACM 33:313–326, 1986), Abraham et al. (Semantics for concurrency, workshops in computing. Springer, Heidelberg, pp 311–323, 1990) and Janicki and Koutny (Lect Notes Comput Sci 506:59–74, 1991), substantially developed in Janicki and Koutny (Theoretical Computer Science 112:5–52, 1993) and Janicki and Koutny (Acta Informatica 34:367–388, 1997), and recently generalized in Guo and Janicki (Lect Notes Comput Sci 2422:178–191, 2002) and Janicki (Lect Notes Comput Sci 3407:84–98, 2005). For the first time the full model for the most general case is given.     

Improved on-line broadcast scheduling with deadlines

We study an on-line broadcast scheduling problem in which requests have deadlines, and the objective is to maximize the weighted throughput, i.e., the weighted total length of the satisfied requests. For the case where all requested pages have the same length, we present an online deterministic algorithm named BAR and prove that it is 4.56-competitive. This improves the previous algorithm of (Kim, J.-H., Chwa, K.-Y. in Theor. Comput. Sci. 325(3):479–488, 2004) which is shown to be 5-competitive by (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210–218, 2004). In the case that pages may have different lengths, we give a ( )-competitive algorithm where Δ is the ratio of maximum to minimum page lengths. This improves the (4Δ+3)-competitive algorithm of (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210–218, 2004). We also prove an almost matching lower bound of Ω(Δ/log Δ). Furthermore, for small values of Δ we give better lower bounds. The work described in this paper was fully supported by grants from the Research Grants Council of the Hong Kong SAR, China [CityU 1198/03E, HKU 7142/03E, HKU 5172/03E], an NSF Grant of China [No. 10371094], and a Nuffield Foundation Grant of UK [NAL/01004/G].     

Characteristic-Based Schemes for Multi-Class Lighthill-Whitham-Richards Traffic Models

In this paper we provide the full spectral decomposition of the Multi-Class Lighthill Whitham Richards (MCLWR) traffic models described in (Wong et al. in Transp. Res. Part A 36:827–841, 2002; Benzoni-Gavage and Colombo in Eur. J. Appl. Math. 14:587–612, 2003). Even though the eigenvalues of these models can only be found numerically, the knowledge of the spectral structure allows the use of characteristic-based High Resolution Shock Capturing (HRSC) schemes. We compare the characteristic-based approach to the component-wise schemes used in (Zhang et al. in J. Comput. Phys. 191:639–659, 2003), and propose two strategies to minimize the oscillatory behavior that can be observed when using the component-wise approach.     

Using Biologically Inspired Features for Face Processing

In this paper, we show that a new set of visual features, derived from a feed-forward model of the primate visual object recognition pathway proposed by Riesenhuber and Poggio (R&P Model) (Nature Neurosci. 2(11):1019–1025, 1999) is capable of matching the performance of some of the best current representations for face identification and facial expression recognition. Previous work has shown that the Riesenhuber and Poggio Model features can achieve a high level of performance on object recognition tasks (Serre, T., et al. in IEEE Comput. Vis. Pattern Recognit. 2:994–1000, 2005). Here we modify the R&P model in order to create a new set of features useful for face identification and expression recognition. Results from tests on the FERET, ORL and AR datasets show that these features are capable of matching and sometimes outperforming other top visual features such as local binary patterns (Ahonen, T., et al. in 8th European Conference on Computer Vision, pp. 469–481, 2004) and histogram of gradient features (Dalal, N., Triggs, B. in International Conference on Computer Vision & Pattern Recognition, pp. 886–893, 2005). Having a model based on shared lower level features, and face and object recognition specific higher level features, is consistent with findings from electrophysiology and functional magnetic resonance imaging experiments. Thus, our model begins to address the complete recognition problem in a biologically plausible way.     

An improved data hiding approach for polygon meshes

We present an improved technique for data hiding in polygonal meshes, which is based on the work of Bogomjakov et al. (Comput. Graph. Forum 27(2):637–642, 2008). Like their method, we use an arrangement on primitives relative to a reference ordering to embed a message. But instead of directly interpreting the index of a primitive in the reference ordering as the encoded/decoded bits, our method slightly modifies the mapping so that our modification doubles the chance of encoding an additional bit compared to Bogomjakov et al.’s (Comput. Graph. Forum 27(2):637–642, 2008). We illustrate the inefficiency in the original mapping of Bogomjakov et al. (Comput. Graph. Forum 27(2):637–642, 2008) with an intuitive representation using a binary tree.     

Model Checking Weighted Integer Reset Timed Automata

Weighted timed automata (WTA), introduced in Alur et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 49–62, Springer, Berlin, 2001), Behrmann et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 147–161, Springer, Berlin, 2001) are an extension of Alur and Dill (Theor. Comput. Sci. 126(2):183–235, 1994) timed automata, a widely accepted formalism for the modelling and verification of real time systems. Weighted timed automata extend timed automata by allowing costs on the locations and edges. There has been a lot of interest Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006), Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008), Brihaye et al. (Proceedings of FORMATS/FTRTFT’04, LNCS, vol. 3253, pp. 277–292, Springer, Berlin, 2004), Brihaye et al. (Inf. Comput. 204(3):408–433, 2006) in studying the model checking problem of weighted timed automata. The properties of interest are written using logic weighted CTL (WCTL), an extension of CTL with costs. It has been shown Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008) that the problem of model checking WTAs with a single clock using WCTL with no external cost variables is decidable, while 3 clocks render the problem undecidable Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006). The question of 2 clocks is open. In this paper, we introduce a subclass of weighted timed automata called weighted integer reset timed automata (WIRTA) and study the model checking problem. We give a clock reduction technique for WIRTA. Given a WIRTA A\mathcal{A} with n≥1 clocks, we show that a single clock WIRTA A￠\mathcal{A}' preserving the paths and costs of A\mathcal{A} can be obtained. This gives us the decidability of model checking WIRTA with n≥1 clocks and m≥1 costs using WCTL with no external cost variables. We then show that for a restricted version of WCTL with external cost variables, the model checking problem is undecidable for WIRTA with 3 stopwatch costs and 1 clock. Finally, we show that model checking WTA with 2 clocks and 1 stopwatch cost against WCTL with no external cost variables is undecidable, thereby answering a question that has remained long open.     

心脏MRI图像快速分割方法

在分析心脏MR图像特点的基础上,提出了先对心脏MRI图像进行K均值聚类,把K均值聚类后的图像作为特征图像,在特征上用Song和Chan提出的快速分割方法进行粗分割,再用粗分割的曲线作为水平集的初始曲线,在心脏MRI图像上用Chan和Vese方法进行细分割的心脏MR图像分割方法.并对Song和Chan快速算法中扫描图像的区域进行了改进,提高了分割速度.分割实验证明,用该方法能够快速、准确地分割心脏MRI图像.     

Multiple piecewise constant with geodesic active contours (MPC-GAC) framework for interactive image segmentation using graph cut optimization

This paper proposes an improved variational model, multiple piecewise constant with geodesic active contour (MPC-GAC) model, which generalizes the region-based active contour model by Chan and Vese, 2001 [11] and merges the edge-based active contour by Caselles et al., 1997 [7] to inherit the advantages of region-based and edge-based image segmentation models. We show that the new MPC-GAC energy functional can be iteratively minimized by graph cut algorithms with high computational efficiency compared with the level set framework. This iterative algorithm alternates between the piecewise constant functional learning and the foreground and background updating so that the energy value gradually decreases to the minimum of the energy functional. The k-means method is used to compute the piecewise constant values of the foreground and background of image. We use a graph cut method to detect and update the foreground and background. Numerical experiments show that the proposed interactive segmentation method based on the MPC-GAC model by graph cut optimization can effectively segment images with inhomogeneous objects and background.     

Solving steel mill slab design problems

The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. (INFORMS J Comput 18:129–134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS J Comput 18:129–134, 2006) for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results (Schaus et al., Constraints 16:125–147, 2010). Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality.     

A High Order Compact Scheme for the Pure-Streamfunction Formulation of the Navier-Stokes Equations

In this paper we continue the study, which was initiated in (Ben-Artzi et al. in Math. Model. Numer. Anal. 35(2):313–303, 2001; Fishelov et al. in Lecture Notes in Computer Science, vol. 2667, pp. 809–817, 2003; Ben-Artzi et al. in J. Comput. Phys. 205(2):640–664, 2005 and SIAM J. Numer. Anal. 44(5):1997–2024, 2006) of the numerical resolution of the pure streamfunction formulation of the time-dependent two-dimensional Navier-Stokes equation. Here we focus on enhancing our second-order scheme, introduced in the last three afore-mentioned articles, to fourth order accuracy. We construct fourth order approximations for the Laplacian, the biharmonic and the nonlinear convective operators. The scheme is compact (nine-point stencil) for the Laplacian and the biharmonic operators, which are both treated implicitly in the time-stepping scheme. The approximation of the convective term is compact in the no-leak boundary conditions case and is nearly compact (thirteen points stencil) in the case of general boundary conditions. However, we stress that in any case no unphysical boundary condition was applied to our scheme. Numerical results demonstrate that the fourth order accuracy is actually obtained for several test-cases.     

Constrained mesh optimization on boundary

This paper presents a new mesh optimization approach aiming to improve the mesh quality on the boundary. The existing mesh untangling and smoothing algorithms (Vachal et al. in J Comput Phys 196: 627–644, 2004; Knupp in J Numer Methods Eng 48: 1165–1185, 2002), which have been proved to work well to interior mesh optimization, are enhanced by adding constrains of surface and curve shape functions that approximate the boundary geometry from the finite element mesh. The enhanced constrained optimization guarantees that the boundary nodes to be optimized always move on the approximated boundary. A dual-grid hexahedral meshing method is used to generate sample meshes for testing the proposed mesh optimization approach. As complementary treatments to the mesh optimization, appropriate mesh topology modifications, including buffering element insertion and local mesh refinement, are performed in order to eliminate concave and distorted elements on the boundary. Finally, the optimization results of some examples are given to demonstrate the effectivity of the proposed approach.