A new approach to computing the Euler characteristic

In this paper we describe a new approach to computing the Euler characteristic of a three dimensional digital image. Our approach is based on computing the change in numbers of black components, tunnels and cavities in 3 × 3 × 3 neighborhood of an object (black) point due to its deletion. The existing algorithms to computing the Euler characteristic of a 3D digital image are based on counting the numbers of all k-dimensional elements (0 ≤ k ≤ 3) in a polyhedral representation of the image. Our approach can be modified for (6,26), (18,6), (6,18) and other connectivity relations of grid points. A parallel implementation of the algorithm is described using the concept of sub-fields.     

基于多特征融合的图像检索算法

为有效提取和描述图像特征,提高图像检索性能,提出一种基于纹理、颜色和形状多特征融合的图像检索算法。检测彩色图像的边缘,对其进行变换得到基元图像。遍历基元图像得到基元共生矩阵,对每个基元求梯度值得到基元梯度直方图。将彩色图像量化到64色颜色空间,得到对应的颜色直方图。利用上述3个特征量描述图像特征,并用于图像检索。实验结果表明,与BCTF和MCM算法相比,该算法的查全率和查准率较高,计算复杂度较低。     

Blended Hermite interpolants

In (Röschel, l997) B-spline technique was used for blending of Lagrange interpolants. In this paper we generalize this idea replacing Lagrange by Hermite interpolants. The generated subspline b(t) interpolates the Hermite input data consisting of parameter values t_i and corresponding derivatives a_i,j, j=0,…,_i−1, and is called blended Hermite interpolant (BHI). It has local control, is connected in affinely invariant way with the input and consists of integral (polynomial) segments of degree 2·k−1, where k−1max{_i}−1 denotes the degree of the B-spline basis functions used for the blending. This method automatically generates one of the possible interpolating subsplines of class C^k−1 with the advantage that no additional input data is necessary.     

A systolic algorithm for solving dense linear systems

For an arbitrary n × n matrix A and an n × 1 column vector b, we present a systolic algorithm to solve the dense linear equations Ax = b. An important consideration is that the pivot row can be changed during the execution of our systolic algorithm. The computational model consists of n linear systolic arrays. For 1 ≤ i ≤ n, the i^th linear array is responsible to eliminate the i^th unknown variable x_i of x. This algorithm requires 4n time steps to solve the linear system. The elapsed time unit within a time step is independent of the problem size n. Since the structure of a PE is simple and the same type PE executes the identical instructions, it is very suitable for VLSI implementation. The design process and correctness proof are considered in detail. Moreover, this algorithm can detect whether A is singular or not.     

Analysis of a finite buffer queue with different scheduling and push-out schemes

A queueing system M₁, M₂/G₁, G₂/1/N with different scheduling and push-out scheme is analyzed in this paper. This work is motivated by the study of the performance of an output link of ATM switches with traffic of two classes with different priorities. However, the queueing model developed in this paper is more general than that of the output link of ATM switches with two-class priority traffic. General service time distributions are allowed for classes 1 and 2 and a general service discipline function, ₁(i, j), is introduced where ₁(i, j) is the probability that a class 1 packet will be served, given that there are i class 1 and j class 2 packets waiting for service. An exact solution is obtained for the loss probabilities for classes 1 and 2, the queue length distribution and the mean waiting time for class 1. The queue length distribution and the mean waiting time for class 2 are calculated approximately. It is shown that the approximation is an upper bound and the error due to the approximation is very small when the loss probability of class 2 is small (e.g., less than 0.01).     

Distribution of black nodes at various levels in a linear quadtree

The distribution of black leaf nodes at each level of a linear quadtree is of significant interest in the context of estimation of time and space complexities of linear quadtree based algorithms. The maximum number of black nodes of a given level that can be fitted in a square grid of size 2ⁿ × 2ⁿ can readily be estimated from the ratio of areas. We show that the actual value of the maximum number of nodes of a level is much less than the maximum obtained from the ratio of the areas. This is due to the fact that the number of nodes possible at a level k, 0≤k≤n − 1, should consider the sum of areas occupied by the actual number of nodes present at levels k + 1, k + 2, …, n − 1.     

Multi-joint histogram based modelling for image indexing and retrieval

This paper presents a novel approach for image retrieval, named multi-joint histogram based modelling (MJHM), in which the joint correlation histograms are constructed between the motif and texton maps. Firstly, the quantized image is divided into non-overlapping 2 × 2 grids. Then each grid is replaced by a scan motif and texton values to construct the transformed motif and texton maps (images) respectively. The motif transformed map minimizes the local gradient and texton transformed map identifies the equality of grayscales while traversing the 2 × 2 grid. Finally, the correlation histograms are constructed between the transformed motif and texton maps. The performance of the proposed method (MJHM) is tested by conducting two experiments on Corel-5K and Corel-10K benchmark databases. The results after investigation show significant improvements in terms of precision, average retrieval precision (ARP), recall and average retrieval rate (ARR) as compared to multi-texton histogram (MTH), smart content based image retrieval system (CMCM) and other state-of-the-art techniques for image retrieval.     

A description of the effect of short range ordering in the compound energy formalism

The current state of the compound energy formalism (CEF) to model ordering and the technique to handle short range ordering (SRO) were discussed. Although there are some methods which allow better treatment for SRO, such as the cluster variation method (CVM) or the Monte Carlo method (MC), these methods are difficult to handle in multi-component systems because of their complexity. In the compound energy formalism, SRO is not explicitly described. However it is possible to take the contribution of SRO to the Gibbs free energy into account through the reciprocal parameter, which has the same concentration dependency as ΔG_m^SRO. Introducing the reciprocal parameter of the form, L_i,j:i,j for the two sublattice model and L_{i,j:i,j:^*:^*} for the four sublattice model, one can satisfactorily describe the contribution of SRO to the Gibbs free energy in the CEF.     

Algorithms for generalized vertex-rankings of partial k-trees

A c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels >i leaves connected components, each having at most c vertices with label i. A c-vertex-ranking is optimal if the number of labels used is as small as possible. We present sequential and parallel algorithms to find an optimal c-vertex-ranking of a partial k-tree, that is, a graph of treewidth bounded by a fixed integer k. The sequential algorithm takes polynomial-time for any positive integer c. The parallel algorithm takes O(log n) parallel time using a polynomial number of processors on the common CRCW PRAM, where n is the number of vertices in G.     

结合代数多重网格的钻石编码隐写算法

针对隐写算法安全性的问题,提出一种结合代数多重网格（AMG）的钻石编码（DE）隐写算法。首先,通过AMG方法将图像的像素点分成粗细网格两个部分。然后,结合DE把机密信息分别嵌入到粗细网格两个像素序列中。其中,粗网格部分像素的改变对整幅图像的质量影响较小,而细网格部分像素的改变对整幅图像的质量影响较大。又因为DE的k值跟信息隐藏容量密切相关,随着k值的增加像素改变量变大,所以用DE嵌入的过程中,粗网格部分选择的k值不小于细网格。最后,选择DE的k值等于1与2,提出了三种隐写方案。与最低有效位（LSB）置换、随机LSB匹配、DE算法和自适应边缘检测算法进行比较,实验结果表明,三种隐写方案的一阶Markov安全指标皆优于其他对比隐写算法。     

A class of robust edge detectors based on latin squares

The theory of Latin Square experimental designs is extended to edge detection of multi-grey level pictorial data. Latin Square designs are realized using mask operations either as a square or in linear forms using ANOVA to estimate the model parameters. The test statistics are based upon the robust F-test and the thresholds are selected by an empirical interactive process. A post hoc comparison method is used to confine the edge element ambiguities to 2-pixel layer thickness in masks greater than 2 × 2 × k. Computer simulations are shown to verify the theory.     

Infinite words and biprefix codes

Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set {v_ii0} of (finite) words on A such that ƒ=v₀v₁…v_i…, {v_ii1} is a biprefix code and v_i≠v_j for positive integers i≠j.     

Complexities of special matrix multiplication problems

This paper develops optimal algorithms to multiply an n × n symmetric tridiagonal matrix by: (i) an arbitrary n × m matrix using 2nm − m multiplications; (ii) a symmetric tridiagonal matrix using 6n − 7 multiplications; and (iii) a tridiagonal matrix using 7n −8 multiplications. Efficient algorithms are also developed to multiply a tridiagonal matrix by an arbitrary matrix, and to multiply two tridiagonal matrices.     

Sojourn time distribution in the M/M/1 queue with discriminatory processor-sharing

In this paper, we consider a queue with multiple K job classes, Poisson arrivals, exponentially distributed required service times in which a single processor serves according to the DPS discipline. More precisely, if there are n_i class i jobs in the system, i=1,…,K, each class j job receives a fraction _j/∑_i=1^K_in_i of the processor capacity. For this queue, we obtain a system of equations for joint transforms of the sojourn time and the number of jobs. Using this system of equations we find the moments of the sojourn time as a solution of linear simultaneous equations, which solves an open problem.     

An asymptotic theory for recurrence relations based on minimization and maximization

We derive asymptotic approximations for the sequence f(n) defined recursively by f(n)=min_1j<n {f(j)+f(n−j)}+g(n), when the asymptotic behavior of g(n) is known. Our tools are general enough and applicable to another sequence F(n)=max_1j<n {F(j)+F(n−j)+min{g(j),g(n−j)}}, also frequently encountered in divide-and-conquer problems. Applications of our results to algorithms, group testing, dichotomous search, etc. are discussed.     

A multi-tree routing scheme using acyclic orientations

We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G=(V,E). The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication. A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N(v) of the destination v has at least k parent pointers. A capacity-k acorn A to destination v is k-vertex fault-tolerant to v. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w V−N(v) can be partitioned into k nonempty classes labeled 1,2,…,k such that any set of sink trees T₁,T₂,…,T_k are pairwise independent, where tree T_i is a sink tree generated by parent pointers labeled i together with the parent pointers into v. We present an linear time optimization algorithm for finding an acorn A of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity-k acorn A, yielding a k-independent sink tree generating scheme.     

Design and use of DIP-1: A fast, flexible and dynamically microprogrammable pipelined image processor

The design of a fast, flexible and dynamically microprogrammable pipelined image processor is presented. The machine is especially suited, though not completely devoted, to perform local operations (up to 16 × 16) of both logical and arithmetic character on pictures, stored in a random access image memory in a 256 level grey scale. Separate parts of the machine take care of data manipulation and address generation. The machine's functioning is illustrated by discussing the way in which arithmetic N × N neighbourhood operations and binary 3 × 3 neighbourhood operations were implemented and finally the software supporting microprogram development and debugging and the run-time support software is described.     

New bounds for multi-label interval routing

Interval routing (IR) is a space-efficient routing method for computer networks. For longest routing path analysis, researchers have focused on lower bounds for many years. For any n-node graph G of diameter D, there exists an upper bound of 2D for IR using one or more labels, and an upper bound of for IR using or more labels. We present two upper bounds in the first part of the paper. We show that for every integer i>0, every n-node graph of diameter D has a k-dominating set of size for . This result implies a new upper bound of for IR using or more labels, where i is any positive integer constant. We apply the result by Kutten and Peleg [8] to achieve an upper bound of (1+)D for IR using O(n/D) or more labels, where is any constant in (0,1). The second part of the paper offers some lower bounds for planar graphs. For any M-label interval routing scheme (M-IRS), where , we derive a lower bound of [(2M+1)/(2M)]D−1 on the longest path for , and a lower bound of [(2(1+δ)M+1)/(2(1+δ)M)]D, where δ(0,1], for . The latter result implies a lower bound of on the number of labels needed to achieve optimality.