Baum''s forward-backward algorithm revisited

In this note, we examine the forward-backward algorithm from the computational viewpoint of the underflow problem inherent in Baum's (1972) original formulation. We demonstrate that the conversion of Baum's computation of joint likelihoods into the computation of posterior probabilities results in essentially the same algorithm, except for the presence of a scaling factor suggested by Levinson et al. (1983) on rather heuristic grounds. The resulting algorithm is immune to the underflow problem, and Levinson's scaling method is given a theoretical justification. We also investigate the relationship between Baum's algorithm and the recent algorithms of Askar and Derin (1981) and Devijver (1984).     

Radial Meixner Moment Invariants for 2D and 3D Image Recognition

In this paper, we propose a new set of 2D and 3D rotation invariants based on orthogonal radial Meixner moments. We also present a theoretical mathematics to derive them. Hence, this paper introduces in the first case a new 2D radial Meixner moments based on polar representation of an object by a one-dimensional orthogonal discrete Meixner polynomials and a circular function. In the second case, we present a new 3D radial Meixner moments using a spherical representation of volumetric image by a one-dimensional orthogonal discrete Meixner polynomials and a spherical function. Further 2D and 3D rotational invariants are derived from the proposed 2D and 3D radial Meixner moments respectively. In order to prove the proposed approach, three issues are resolved mainly image reconstruction, rotational invariance and pattern recognition. The result of experiments prove that the Meixner moments have done better than the Krawtchouk moments with and without nose. Simultaneously, the reconstructed volumetric image converges quickly to the original image using 2D and 3D radial Meixner moments and the test images are clearly recognized from a set of images that are available in a PSB database.     

Fast computation of 3D Meixner’s invariant moments using 3D image cuboid representation for 3D image classification

Multimedia Tools and Applications - In this paper, we propose a new fast computation method of 3D discrete orthogonal invariant moments of Meixner. This proposed method is based on two fundamental...     

Cellular matrix model for parallel combinatorial optimization algorithms in Euclidean plane

We propose a parallel computation model, called cellular matrix model (CMM), to address large-size Euclidean graph matching problems in the plane. The parallel computation takes place by partitioning the plane into a regular grid of cells, each cell being affected to a single processor. Each processor operates on local data, starting from its cell location and extending its search to the neighborhood cells in a spiral search way. In order to deal with large-size problems, memory size and processor number are fixed as O(N), where N is the problem size. Then one key point is that closest point searching in the plane is performed in O(1) expected time for uniform or bounded distribution, for each processor independently. We define a generic loop that models the parallel projection between graphs and their matching, as executed by the many cells at a given level of computation granularity. To illustrate its efficacy and versatility, we apply the CMM, on GPU platforms, to two problems in image processing: superpixel segmentation and stereo matching energy minimization. Firstly, we propose an extended version of the well-known SLIC superpixel segmentation algorithm, which we call SPASM algorithm, by using a parallel 2D self-organizing map instead of k-means algorithm. Secondly, we investigate the idea of distributed variable neighborhood search, and propose a parallel search heuristic, called distributed local search (DLS), for global energy minimization of stereo matching problem. We evaluate the approach with regards to the state-of-the-art graph cut and belief propagation algorithms. For each problem, we argue that the parallel GPU implementation provides new competitive quality/time trade-offs, with substantial acceleration factors as the problem size increases.     

On the fast computation of orthogonal Fourier–Mellin moments with improved numerical stability

A fast and numerically stable recursive method for the computation of orthogonal Fourier?CMellin moments (OFMMs) is proposed. Fast recursive method is developed for the radial polynomials which occur in the kernel function of the OFMMs, thus enhancing the overall computation speed. The proposed method is free from any overflow situations as it does not consist of any factorial term. It is also free from underflow situations as no power terms are involved. The proposed recursive method is claimed to be fastest in comparison with the direct and other methods to compute OFMMs till date. The elimination of the computation of factorial terms makes the moments very stable even up to an order of 200, which become instable in conventional or in any other recursive methods proposed earlier wherein instability occurs at moment order ??25. Experiments are performed on standard test images to prove the superiority of the proposed method on existing methods in terms of speed and numerical stability.     

Automated low-order to high-order mesh conversion

An algorithm is presented for the CAD-free conversion of linear unstructured meshes into curved high-order meshes, which are necessary for high-order flow simulations. The algorithm operates via three steps: (1) autonomous detection of feature curves along the mesh surface, (2) reconstruction of the surface curvature from the combination of surface node positions and feature curve positions, and (3) alignment of the mesh interior to the newly curved surface. The algorithm is implemented in our freely available cross-platform graphical software program meshCurve, which transforms existing linear meshes into high-order curved meshes

     

High-order compact scheme for boundary points

In this paper, we introduce a new high-order scheme for boundary points when calculating the derivative of smooth functions by compact scheme. The primitive function reconstruction method of ENO schemes is applied to obtain the conservative form of the compact scheme. Equations for approximating the derivatives around the boundary points 1 and N are determined. For the Neumann (and mixed) boundary conditions, high-order equations are derived to determine the values of the function at the boundary points, 1 and N, before the primitive function reconstruction method is applied. We construct a subroutine that can be used with Dirichlet, Neumann, or mixed boundary conditions. Numerical tests are presented to demonstrate the capabilities of this new scheme, and a comparison to the lower-order boundary scheme shows its advantages.     

3D Curves Reconstruction Based on Deformable Models

We present a new method, based on curve evolution, for the reconstruction of a 3D curve from two different projections. It is based on the minimization of an energy functional. Following the work on geodesic active contours by Caselles et al. (in Int. Conf. on Pattern Recognition, 1996, Vol. 43, pp. 693–737), we then transform the problem of minimizing the functional into a problem of geodesic computation in a Riemann space. The Euler-Lagrange equation of this new functional is derived and its associated PDE is solved using the level set formulation, giving the existence and uniqueness results. We apply the model to the reconstruction of a vessel from a biplane angiography.     

一种MPEG-2视频流无缝拼接的码率控制算法

对压缩域中MPEG-2视频流无缝拼接的码率控制进行了研究,分析了通过调整编码参数vbv_delay来确定拼接期的目标比特数,以达到缓冲器平稳过渡的要求,同时结合压缩域中MPEG-2视频流无缝拼接中的帧转换所带来的编码复杂度变化的特点,提出了一种具体的拼接期的目标比特数分配的方案。试验表明：该方案能够有效地实现拼接过程中缓冲器的平稳过渡,同时能获得较好的视觉效果。     

基于参数分解的正则四边形插值细分曲面的快速求值

提出了两种正则四边形网格插值细分曲面的求值算法.算法基于参数m-进制分解和构造矩阵序列,通过参数分解数列对应的矩阵乘积得到基函数值,得到初始网格上对应控制点的权值,从而实现插值细分曲面求值.算法1 基于2D 细分掩模,算法2 基于张量积.数值实验表明,算法高效且低存储.     

基于LBI的二维复稀疏信号重建算法及应用研究

针对二维复稀疏信号重建时存在存储空间和计算复杂度增加的问题, 本文提出了一种快速并行重建二维复稀疏信号的并行线性Bregman迭代(Parallel fast linearized Bregman iteration, PFLBI)算法. 首先, 构建了二维复稀疏信号的结构模型以及PFLBI算法基本迭代格式; 其次, 通过变步长方式提高迭代收敛速度, 而每次迭代的步长则是通过估计中间变量的积累量突破收缩阈值需要的积累步数得到的; 再次, 对算法的性能指标进行了分析; 最后, 将该算法应用于逆合成孔径雷达(Inverse synthetic aperture radar, ISAR)成像. 实验结果表明该算法在重建性能和速度上具有优势.     

Space utilization and access path length in B-trees

B-trees are useful for the maintenance of very large indexes. In this paper a deterministic model for the computation of space utilization and access path length in B-trees is presented. The considerations include a general form of B-trees that provides underflow and overflow treatment. Results for utilization and path length for some typical B-tree situations are given.     

Approximation algorithm for hotlink assignment in the greedy model

Link-based information structures such as the web can be enhanced through the addition of hotlinks. Assume that each node in the information structure is associated with a weight representing the access frequency of the node by users. In order to access a particular node, the user must follow a path leading to it from the root. By adding new hotlinks to the tree, it may be possible to reduce the access cost of the system, namely, the expected number of steps needed to reach a leaf from the root, assuming the user can decide which hotlinks to follow in each step. The hotlink assignment   problem involves finding a set of hotlinks (with at most K=O(1)$K=O\left(1\right)$ hotlinks emanating from every node) maximizing the gain in the expected cost. The paper addresses this problem in two user models, namely, the traditional clairvoyant user model employed in [P. Bose, J. Czyzowicz, L. Gasieniec, E. Kranakis, D. Krizanc, A. Pelc, M.V. Martin, Strategies for hotlink assignments, in: Proc. 11th Symp. on Algorithms and Computation, 2000, pp. 23–34; E. Kranakis, D. Krizanc, S. Shende, Approximating hotlink assignments, in: Proc. 12th Symp. on Algorithms and Computation, 2001, pp. 756–767; P. Bose, D. Krizanc, S. Langerman, P. Morin, Asymmetrical communication protocols via hotlink assignments, in: Proc. 9th Colloq. on Structural Information and Communication Complexity, 2002, pp. 33–39; R. Matichin, D. Peleg, Approximation algorithm for hotlink assignments in web directories, in: Proc. Workshop on Algorithms and Data Structures, 2003, pp. 271–280] and the more realistic greedy user model recently introduced in [O. Gerstel, S. Kutten, R. Matichin, D. Peleg, Hotlink enhancement algorithms for web directories, in: Proc. 14th Symp. on Algorithms and Computation, 2003, pp. 68–77], and presents a polynomial time 2-approximation algorithm for the hotlink assignment problem on rooted directed trees.     

Branch Points in One-Dimensional Gaussian Scale Space

Scale space analysis combines global and local analysis in a single methodology by simplifying a signal. The simplification is indexed using a continuously varying parameter denoted scale. Different analyses can then be performed at their proper scale. We consider evolution of a polynomial by the parabolic partial differential heat equation. We first study a basis for the solution space, the heat polynomials, and subsequently the local geometry around a branch point in scale space. By a branch point of a polynomium we mean a scale and a location where two zeros of the polynomial merge. We prove that the number of branch points for a solution is for an initial polynomial of degree n. Then we prove that the branch points uniquely determine a polynomial up to a constant factor. Algorithms are presented for conversion between the polynomial's coefficients and its branch points.     

基于虚拟高度投影线的三维重建及误差补偿

针对传统三维重建方法计算复杂度高的问题,提出一种基于虚拟高度投影线的三维重建方法。该方法将场景栅格化,在栅格中引入虚拟高度线,把虚拟高度线投影到二维图像上形成投影线,并在投影线上找到对应点得到三维场景信息,以反映场景的真实信息。分析引起误差的主要来源,针对误差来源结合摄像机内外参数提出补偿方法。通过实验验证了该方法的有效性。     

分段迭代匹配追踪图像重构算法

目的 压缩采样匹配追踪（CoSaMP）算法虽然引入回溯的思想,但其原子选择需要大量的观测值且在稀疏度估计不准确时,会降低信号重构精度,增加重构时间,降低重构效率。为提高CoSaMP算法的重构精度,改善算法的重构性能,提出了一种基于广义逆的分段迭代匹配追踪（StIMP）算法。方法 为保证迭代时挑选原子的精确性和快速性,对观测矩阵广义逆化,降低原子库中原子的相干性;原子更新结合正交匹配追踪（OMP）算法筛选原子的准确性与CoSaMP算法的回溯性,将迭代过程分为两个阶段：第1阶段利用OMP算法迭代K/2次;第2阶段以第1阶段OMP算法迭代所得的残差和原子为输入,并采用CoSaMP算法继续迭代,同时改变原子选择标准,从而精确快速地重构出稀疏信号。结果 对于1维的高斯随机信号,无论在不同的稀疏度还是观测值下,相比于OMP、CoSaMP、正则化正交匹配追踪（ROMP）算法和傅里叶类圆环压缩采样匹配追踪（FR-CoSaMP）算法,StIMP算法更加稳健,且具有更高重构成功率;对于2维图像信号,在各个采样率下,StIMP算法的峰值信噪比（PSNR）均高于其他重构算法,在采样率为0.7时,StIMP算法的平均PSNR值比OMP、CoSaMP、ROMP和FR-CoSaMP算法分别高2.14 dB、1.20 dB、3.67 dB和0.90 dB,平均重构时间也较OMP、CoSaMP和FR-CoSaMP算法短。结论 提出了一种改进的重构算法,对1维高斯随机信号和2维图像信号均有更好的重构效率和重构效果,与原算法和现有的主流图像重构方法相比,StIMP算法更具高效性和实用性。     

MPEG-2实时解码中的输入缓冲器控制

分析了ＭＰＥＧ２ 的时序模型,研究了理想解码器的输入缓冲器工作过程以及实际实时解码器解码开始的时刻、解码非瞬时、码流非平稳等因素对输入缓冲器的影响,指出实际解码器的输入缓冲器必须增大。在输入缓冲器容量受限制的情况下,给出了输入缓冲器控制策略。该策略已经成功地应用于作者研制的高清晰度电视功能样机中。     

A rational high-order compact ADI method for unsteady convection–diffusion equations

Based on a fourth-order compact difference formula for the spatial discretization, which is currently proposed for the one-dimensional (1D) steady convection–diffusion problem, and the Crank–Nicolson scheme for the time discretization, a rational high-order compact alternating direction implicit (ADI) method is developed for solving two-dimensional (2D) unsteady convection–diffusion problems. The method is unconditionally stable and second-order accurate in time and fourth-order accurate in space. The resulting scheme in each ADI computation step corresponds to a tridiagonal matrix equation which can be solved by the application of the 1D tridiagonal Thomas algorithm with a considerable saving in computing time. Three examples supporting our theoretical analysis are numerically solved. The present method not only shows higher accuracy and better phase and amplitude error properties than the standard second-order Peaceman–Rachford ADI method in Peaceman and Rachford (1959) [4], the fourth-order ADI method of Karaa and Zhang (2004) [5] and the fourth-order ADI method of Tian and Ge (2007) [23], but also proves more effective than the fourth-order Padé ADI method of You (2006) [6], in the aspect of computational cost. The method proposed for the diffusion–convection problems is easy to implement and can also be used to solve pure diffusion or pure convection problems.     

Root squaring using level-index arithmetic

The symmetric level-index,sli, system for representing numbers eases the monitoring of precision while avoiding the problems associated with overflow and underflow. In this paper the practical benefits of the system are displayed, using the root-squaring method of Graeffe as a vehicle.     

Elementary differentials,their graphs and codes

When designing high-order one-step numerical methods like Runge-Kutta, Rosenbrock, or ABC-schemes for solving ordinary differential equations, one has to take into account many tens and hundreds of elementary differentials. Graphical representation of the latter in use nowadays does not solve the problem of the computerization of the enormous amount of manual work. We have proposed a simple and intuitive way of digital coding of elementary differentials or their graphs. Algorithms for generation, analysis, and synthesis of such codes were developed and implemented in a computer program, which computes tables of codes for elementary differentials of any order together with their multiplicities and gamma-factors.