A multi-scale image reconstruction algorithm for electrical capacitance tomography

Electrical capacitance tomography (ECT) is considered as a promising process tomography (PT) technology, and its successful applications depend mainly on the precision and speed of the image reconstruction algorithms. In this paper, based on the wavelet multi-scale analysis method, an efficient image reconstruction algorithm is presented. The original inverse problem is decomposed into a sequence of inverse problems, which are solved successively from the largest scale to the smallest scale. At different scales, the inverse problem is solved by a generalized regularized total least squares (TLS) method, which is developed using a combinational minimax estimation method and an extended stabilizing functional, until the solution of the original inverse problem is found. The homotopy algorithm is employed to solve the objective functional. The proposed algorithm is tested by the noise-free capacitance data and the noise-contaminated capacitance data, and excellent numerical performances and satisfactory results are observed. In the cases considered in this paper, the reconstruction results show remarkable improvement in the accuracy. The spatial resolution of the reconstructed images by the proposed algorithm is enhanced and the artifacts in the reconstructed images can be eliminated effectively. As a result, a promising algorithm is introduced for ECT image reconstruction.     

Stability results for uniquely determined sets from two directions in discrete tomography

In this paper we prove several new stability results for the reconstruction of binary images from two projections. We consider an original image that is uniquely determined by its projections and possible reconstructions from slightly different projections. We show that for a given difference in the projections, the reconstruction can only be disjoint from the original image if the size of the image is not too large. We also prove an upper bound for the size of the image given the error in the projections and the size of the intersection between the image and the reconstruction.     

Continuous-time image reconstruction for binary tomography

Binary tomography is the process of reconstructing a binary image from a finite number of projections. We present a novel method for solving binary tomographic inverse problems using a continuous-time image reconstruction (CIR) system described by nonlinear differential equations based on the minimization of a double Kullback–Leibler divergence. We prove theoretically that the divergence measure monotonically decreases in time. Moreover, we demonstrate numerically that the quality of the reconstructed images of the nonlinear CIR system is better than those from an iterative reconstruction method.     

Bounds on the quality of reconstructed images in binary tomography

Binary tomography deals with the problem of reconstructing a binary image from its projections. In particular, there is a focus on highly underdetermined reconstruction problems for which many solutions may exist. In such cases, it is important to have a quality measure for the reconstruction with respect to the unknown original image.     

Multi-resolution method for binary tomography

Multi-resolution and region-growing strategies have been successfully used in several fields of image processing. In this paper we investigate how these two strategies can be applied for binary tomography. We included these strategies into a reconstruction method using simulated annealing and tested these new methods on different images.     

A new approach to the reconstruction of images from Radon projections

A new approach is proposed for reconstruction of images from Radon projections. Based on Fourier expansions in orthogonal polynomials of two and three variables, instead of Fourier transforms, the approach provides a new algorithm for the computed tomography. The convergence of the algorithm is established under mild assumptions.     

Complexity results for reconstructing binary images with disjoint components from horizontal and vertical projections

The problem of reconstructing a special class of binary images from their horizontal and vertical projections is considered. We present a general framework for analyzing the worst case complexity of this task if the image consists of more than one pairwise disjoint component. Applying the presented technique we analyze the complexity of reconstructing canonical hv-convex binary images. We also present parameterized complexity results on general and so-called glued hv-convex images. Moreover, we study how our results are related to the reconstruction of permutation matrices from four projections.     

An algorithm for reconstructing convex bodies from their projections

An algorithm is described for the approximative reconstruction of a plane convex body from its projections in a finite number of directions.A priori anda posteriori error estimates are given, and the convergence of certain sequences of an approximative solution of the reconstruction problem to the exact solution is proven. Finally, it is shown that, after small modifications, the algorithm can be applied to reconstruct convex bodies from discrete projectional data.The algorithm consists in an approximation of the convex body, to be reconstructed, by recursively defined cores and envelopes, following the ideas of Kuba [6] for the reconstruction of binary patterns.This paper was started at the University of Erlangen-Nürnberg in 1983–1984, when the second author was a fellow of the Alexander von Humboldt Foundation, while the last author was supported by the German Research Council (DFG, Contract Ko-506/8-1).     

A complex time based construction heuristic for batch scheduling problems in the chemical industry

In this paper we investigate a heuristic for batch processing problems occurring in the chemical industry, where the objective is to minimize the makespan. Usually, this kind of problem is solved using mixed-integer linear programs. However, due to the large number of binary variables good results within a reasonable computational time could only be obtained for small instances.We propose an iterative construction algorithm which alternates between construction and deconstruction phases. Moreover, we suggest diversification and intensification strategies in order to obtain good suboptimal solutions within moderate running times. Computational results show the power of this algorithm.     

A parallel balance scheme for banded linear systems

A parallel algorithm is proposed for the solution of narrow banded non‐symmetric linear systems. The linear system is partitioned into blocks of rows with a small number of unknowns common to multiple blocks. Our technique yields a reduced system defined only on these common unknowns which can then be solved by a direct or iterative method. A projection based extension to this approach is also proposed for computing the reduced system implicitly, which gives rise to an inner–outer iteration method. In addition, the product of a vector with the reduced system matrix can be computed efficiently on a multiprocessor by concurrent projections onto subspaces of block rows. Scalable implementations of the algorithm can be devized for hierarchical parallel architectures by exploiting the two‐level parallelism inherent in the method. Our experiments indicate that the proposed algorithm is a robust and competitive alternative to existing methods, particularly for difficult problems with strong indefinite symmetric part. Copyright © 2001 John Wiley & Sons, Ltd.     

Reconstruction of Discrete Sets from Four Projections: Strong Decomposability

In this paper we introduce the class of strongly decomposable discrete sets and give an efficient algorithm for reconstructing discrete sets of this class from four projections. It is also shown that every Q-convex set (along the set of directions {x, y}) consisting of several components is strongly decomposable. As a consequence of strong decomposability we get that in a subclass of hv-convex discrete sets the reconstruction from four projections can be solved in polynomial time.     

三维加权PFDK重建算法研究

基于滤波反投影的Feldkamp-Davis-Kress(FDK)算法,具有数学形式简单、容易实现和计算速度快等优点,在医疗和工业等领域得到了广泛的应用.平行重排(PF DK)算法是FDK算法的一种推广,针对PFDK算法重建出的图像受锥角的影响加大的问题,给出一种三维加权PFDK图像重建算法,并研究了重排过程中径向插值间隔对重建图像质量的影响,分别采用三种不同插值总数(插值间隔分别是1单位,0.5单位,0.25单位)重排数据.实验结果表明给出的三维加权PFDK算法可有效减少锥角的影响,且当采用2倍插值总数时重建结果较好.     

基于PICCS的非局部TGV能谱CT重建算法

能谱CT将宽谱划分为窄谱,导致通道内光子数目明显减少,加大了噪声影响,故从噪声投影中重建出高质量图像是能谱CT的一个研究热点.传统全变分(total variational,TV)容易造成重建图像中出现块状伪影等问题,总广义全变分(total generalized variation,TGV)算法可以逼近任意阶函数,再结合非局部均值算法的思想,同时考虑到不同能谱通道下重建图像的相关性,将高质量全能谱重建图像作为先验图像指导能谱CT重建,提出了基于先验图像约束压缩感知(prior image constrained compressed sensing,PICCS)的非局部TGV重建算法.实验结果表明,所提算法在抑制噪声的同时能够有效复原图像细节及边缘信息,且收敛速度快.     

Prior Learning and Convex-Concave Regularization of Binary Tomography

In our previous work, we introduced a convex-concave regularization approach to the reconstruction of binary objects from few projections within a limited range of angles. A convex reconstruction functional, comprising the projections equations and a smoothness prior, was complemented with a concave penalty term enforcing binary solutions. In the present work we investigate alternatives to the smoothness prior in terms of probabilistically learnt priors encoding local object structure. We show that the difference-of-convex-functions DC-programming framework is flexible enough to cope with this more general model class. Numerical results show that reconstruction becomes feasible under conditions where our previous approach fails.     

Observations on a class of nasty linear complementarity problems

Earlier papers by Murty [16] and Fathi [7] have exhibited classes of linear complementarity problems for which the computational effort (number of pivot steps) required to solve them by Lemke's algorithm [13] or Murty's algorithm [15] grows exponentially with the pronlem size (number of variables). In this paper we consider the sequences of complementary bases that arise as these problems are solved by the aforementioned algorithms. There is a natural correspondence between these bases and binary n-vectors through which the basis sequences can be identified with particular hamiltonian paths on the unit n-cube and with the binary Gray code representations of the integers from 0 to 2ⁿ-1.     

Optimal berth allocation and time-invariant quay crane assignment in container terminals

Due to the dramatic increase in the world’s container traffic, the efficient management of operations in seaport container terminals has become a crucial issue. In this work, we focus on the integrated planning of the following problems faced at container terminals: berth allocation, quay crane assignment (number), and quay crane assignment (specific). First, we formulate a new binary integer linear program for the integrated solution of the berth allocation and quay crane assignment (number) problems called BACAP. Then we extend it by incorporating the quay crane assignment (specific) problem as well, which is named BACASP. Computational experiments performed on problem instances of various sizes indicate that the model for BACAP is very efficient and even large instances up to 60 vessels can be solved to optimality. Unfortunately, this is not the case for BACASP. Therefore, to be able to solve large instances, we present a necessary and sufficient condition for generating an optimal solution of BACASP from an optimal solution of BACAP using a post-processing algorithm. In case this condition is not satisfied, we make use of a cutting plane algorithm which solves BACAP repeatedly by adding cuts generated from the optimal solutions until the aforementioned condition holds. This method proves to be viable and enables us to solve large BACASP instances as well. To the best of our knowledge, these are the largest instances that can be solved to optimality for this difficult problem, which makes our work applicable to realistic problems.     

背包问题的两阶段动态规划算法

本文通过理论分析给出了背包问题的两阶段动态规划算法，用例题说明了其求解过程。在计算机上运用本文所述算法和背包问题的动态规划算法求解了大量例题。解题实践说明，对于大中型背包问题，两阶段动态规划算法由于只要求对少量变量进行排序而使解题时间大为缩短，是一种值得推荐的算法。     

Distributed algebraic multigrid for finite element computations

The Finite Element Method has been successfully applied to a variety of problems in engineering, medicine, biology, and physics. However, this method can be computationally intensive, particularly for problems in which an unstructured mesh of elements is generated. In such situations, the Algebraic Multigrid (AMG) can prove to be a robust method for solving the discretized linear systems that emerge from the problem. Unfortunately, AMG requires a large amount of storage (thus causing swapping on most sequential machines), and typically converges slowly. We show that distributing the algorithm across a cluster of workstations can help alleviate these problems. The distributed algorithm is run on a number of geomechanics problems that are solved using finite elements. The results show that distributed processing is extremely useful in maintaining the performance of the AMG algorithm with increasing problem size, particularly by reducing the amount of disk swapping required.     

Discrete and geometric Branch and Bound algorithms for?medical image registration

Aiming at the development of an exact solution method for registration problems, we present two different Branch & Bound algorithms for a mixed integer programming formulation of the problem. The first B&B algorithm branches on binary assignment variables and makes use of an optimality condition that is derived from a graph matching formulation. The second, geometric B&B algorithm applies a geometric branching strategy on continuous transformation variables. The two approaches are compared for synthetic test examples as well as for 2-dimensional medical data. The results show that medium sized problem instances can be solved to global optimality in a reasonable amount of time.     

The Topological Gradient Method: From Optimal Design to Image Processing

The aim of this article is to review and extend the applications of the topological gradient to major image processing problems. We briefly review the topological gradient, and then present its application to the crack localization problem, which can be solved using the Dirichlet to Neumann approach. A very natural application of this technique in image processing is the inpainting problem, which can be solved by identifying the optimal location of the missing edges. Edge detection is of extreme importance, as edges convey essential information in a picture. A second natural application is then the image reconstruction. A class of image reconstruction problems is considered that includes restoration, demosaicing, segmentation and super-resolution. These problems are studied using a unified theoretical framework which is based on the topological gradient method. This tool is able to find the localization and orientation of the edges for blurred, low sampled, partially masked, noisy images. We review existing algorithms and propose new ones. The performance of our approach is compared with conventional image reconstruction processes.