Non-crossing matchings of points with geometric objects

Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a non-crossing matching between point–object pairs. In this paper, we address the algorithmic problem of determining whether a non-crossing matching exists between a given point–object pair. We show that when the objects we match the points to are finite point sets, the problem is NP-complete in general, and polynomial when the objects are on a line or when their size is at most 2. When the objects are line segments, we show that the problem is NP-complete in general, and polynomial when the segments form a convex polygon or are all on a line. Finally, for objects that are straight lines, we show that the problem of finding a min-max non-crossing matching is NP-complete.     

A new modified panoramic UAV image stitching model based on the GA-SIFT and adaptive threshold method

This paper presents panoramic unmanned aerial vehicle (UAV) image stitching techniques based on an optimal Scale Invariant Feature Transform (SIFT) method. The image stitching representation associates a transformation matrix with each input image. In this study, we formulate stitching as a multi-image matching problem, and use invariant local features to find matches between the images. An improved Geometric Algebra (GA-SIFT) algorithm is proposed to realize fast feature extraction and feature matching work for the scanned images. The proposed GA-SIFT method can locate more feature points with greater accurately than the traditional SIFT method. The adaptive threshold value method proposed solves the limitation problem of high computation load and high cost of stitching time by greater feature points extraction and stitching work. The modified random sample consensus method is proposed to estimate the image transformation parameters and to determine the solution with the best consensus for the data. The experimental results demonstrate that the proposed image stitching method greatly increases the speed of the image alignment process and produces a satisfactory image stitching result. The proposed image stitching model for aerial images has good distinctiveness and robustness, and can save considerable time for large UAV image stitching.     

基于PGH矩改进SURF算法的工业散料识别研究

针对工业散料识别过程中图像特征匹配率低的问题,提出一种基于PGH矩的改进SURF图像匹配算法.首先,研究Gaussian-Hermite矩,将其扩展到复数空间中,推导出Polar-Gaussian-Hermite矩;其次,利用升降算符法计算图像PolarGaussian-Hermite矩,获得新的特征向量;最后,将原始图像提取的特征点和模板图像进行准确匹配得到最优匹配结果.实验结果表明算法能够解决缩放、旋转和曝光情况下工件匹配问题,误匹配率8%左右,满足工业散料识别系统的准确性和实时性要求.     

An efficient fractal image coding algorithm using unified feature and DCT

Fractal image compression is a promising technique to improve the efficiency of image storage and image transmission with high compression ratio, however, the huge time consumption for the fractal image coding is a great obstacle to the practical applications. In order to improve the fractal image coding, efficient fractal image coding algorithms using a special unified feature and a DCT coder are proposed in this paper. Firstly, based on a necessary condition to the best matching search rule during fractal image coding, the fast algorithm using a special unified feature (UFC) is addressed, and it can reduce the search space obviously and exclude most inappropriate matching subblocks before the best matching search. Secondly, on the basis of UFC algorithm, in order to improve the quality of the reconstructed image, a DCT coder is combined to construct a hybrid fractal image algorithm (DUFC). Experimental results show that the proposed algorithms can obtain good quality of the reconstructed images and need much less time than the baseline fractal coding algorithm.     

A graph-theoretic model to solve the approximate string matching problem allowing for translocations

In this paper, we study the approximate string matching problem under a string distance whose edit operations are translocations of equal length factors. We extend a graph-theoretic approach proposed by Rahman and Illiopoulos (2008) to model our problem. In the sequel, we devise efficient algorithms based on this model to solve a number of variants of the string matching problem with translocations.     

CL.E.KMODES: a modified <Emphasis Type="Italic">k</Emphasis>-modes clustering algorithm

In this paper we present a new method for clustering categorical data sets named CL.E.KMODES. The proposed method is a modified k-modes algorithm that incorporates a new four-step dissimilarity measure, which is based on elements of the methodological framework of the ELECTRE I multicriteria method. The four-step dissimilarity measure introduces an alternative and more accurate way of assigning objects to clusters. In particular, it compares each object with each mode, for every attribute that they have in common, and then chooses the most appropriate mode and its corresponding cluster for that object. Seven widely used data sets are tested to verify the robustness of the proposed method in six clustering evaluation measures.     

生态文明发展状况的动态奖惩评价及应用

推进生态文明建设是全面建设小康社会的新要求。本文提出一种具有奖惩特征及引导作用的生态文明评价模型。首先,根据被评价对象的实际发展趋势以及不同被评价对象同一时刻评价值的平均增量确定各被评价对象不同时刻评价值的理想点;其次,根据被评价对象实际评价值与理想点之间的差值确定被评价对象的奖惩情况、奖惩因子以及具有奖惩特征的动态综合评价值;最后,应用该方法对中国10个省域的生态文明状况进行了评价与比较分析。     

Recognizing one-DOF industrial tools using invariant moments

In this paper, a simple but efficient approach is proposed to recognize one-DOF industrial tools. Since the shape is changed with the variation of the jaw angles and a feature vectorobtained by conventional approach is not unique, we use the invariant moments and the ratio of area to perimeter squared of a boundary image to construct the required feature vector for object recognition. Two statistical classifiers based on the nearest-neighbor rule and the minimum-mean-distance rule are then utilized to pattern recognition. Experimental results show the good performance of this method in the noisy environment, as well as noise-free environment are also included.     

基于Linear Sampling方法的二维可穿透区域反演

提出用时间调和声散射远场信息来反演二维可穿透目标的一种Linear Sampling方法,通过提取包含可穿透目标的一个样本区域的支集的点列来实现反演的,因为其在区域内与区域外有显著的不同取值,由此而获得区域的逼近.这个算法特别吸引人之处是不需关于障碍物的任何先验信息.并且只需散射场在某个有限孔径中的部分远场信息,即可获得穿透区域的一个逼近.一些数值算例保证了这个反演算法是有效的和实用的.     

A Level Set Representation Method for N-Dimensional Convex Shape and Applications

In this work,we present a new method for convex shape representation,which is regardless of the dimension of the concerned objects,using level-set approaches.To the best of our knowledge,the proposed prior is the first one which can work for high dimensional objects.Convexity prior is very useful for object completion in computer vision.It is a very challenging task to represent high dimensional convex objects.In this paper,we first prove that the convexity of the considered object is equivalent to the convexity of the associated signed distance function.Then,the second order condition of convex functions is used to characterize the shape convexity equivalently.We apply this new method to two applications:object segmentation with convexity prior and convex hull problem(especially with outliers).For both applications,the involved problems can be written as a general optimization problem with three constraints.An algorithm based on the alternating direction method of multipliers is presented for the optimization problem.Numerical experiments are conducted to verify the effectiveness of the proposed representation method and algorithm.     

Average-optimal string matching

The exact string matching problem is to find the occurrences of a pattern of length m from a text of length n symbols. We develop a novel and unorthodox filtering technique for this problem. Our method is based on transforming the problem into multiple matching of carefully chosen pattern subsequences. While this is seemingly more difficult than the original problem, we show that the idea leads to very simple algorithms that are optimal on average. We then show how our basic method can be used to solve multiple string matching as well as several approximate matching problems in average optimal time. The general method can be applied to many existing string matching algorithms. Our experimental results show that the algorithms perform very well in practice.     

Using pattern matching for tiling and packing problems

This paper describes a new placement method based on pattern matching for 2D tiling problems. Tiling problem can be considered as a special case of bin packing. In the proposed method, the representation of the figures and the board is based on directional chain codes. Contrary to other works that the area has been used for the board and the figures, the proposed method is based on usage of their boundaries instead. With this representation, consideration of the area has been replaced with that of the exact string matching. With the proposed knowledge representation, rotation and reflection of the figures can be considered easily. The results of a hybrid approach of genetic algorithm and simulated annealing have been shown. This new method, introduces a novel approach for handling and solving a variety of 2D-packing problems.     

Intuitionistic Fuzzy Automaton for Approximate String Matching

This paper introduces an intuitionistic fuzzy automaton model for computing the similarity between pairs of strings. The model details the possible edit operations needed to transform any input (observed) string into a target (pattern) string by providing a membership and non-membership value between them. In the end, an algorithm is given for approximate string matching and the proposed model computes the similarity and dissimilarity between the pair of strings leading to better approximation.     

Polygonal estimation of planar convex-set perimeter from its two projections

This paper deals with the problem of extracting qualitative and quantitative information from few tomographic projections of an object without reconstructing this object. It focuses on the extraction of quantitative information, precisely the border perimeter estimation for a convex set from horizontal and vertical projections. In the case of a multiple reconstruction, lower and upper bounds for the perimeter are established. In the case of a unique reconstruction, we give conditions and a method for constructing an inscribed polygon in a convex set only from the convex-set projections. An inequality on border perimeter is proved when a convex set is included in another one. The convergence of the polygon perimeter, when the number of vertices increases, is established for such polygons.     

Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets

In this paper we introduce an algorithm for the creation of polyhedral approximations for certain kinds of digital objects in a three-dimensional space. The objects are sets of voxels represented as strongly connected subsets of an abstract cell complex. The proposed algorithm generates the convex hull of a given object and modifies the hull afterwards by recursive repetitions of generating convex hulls of subsets of the given voxel set or subsets of the background voxels. The result of this method is a polyhedron which separates object voxels from background voxels. The objects processed by this algorithm and also the background voxel components inside the convex hull of the objects are restricted to have genus 0. The second aim of this paper is to present some practical improvements to the discussed convex hull algorithm to reduce computation time.     

Gromov–Wasserstein Distances and the Metric Approach to Object Matching

This paper discusses certain modifications of the ideas concerning the Gromov–Hausdorff distance which have the goal of modeling and tackling the practical problems of object matching and comparison. Objects are viewed as metric measure spaces, and based on ideas from mass transportation, a Gromov–Wasserstein type of distance between objects is defined. This reformulation yields a distance between objects which is more amenable to practical computations but retains all the desirable theoretical underpinnings. The theoretical properties of this new notion of distance are studied, and it is established that it provides a strict metric on the collection of isomorphism classes of metric measure spaces. Furthermore, the topology generated by this metric is studied, and sufficient conditions for the pre-compactness of families of metric measure spaces are identified. A second goal of this paper is to establish links to several other practical methods proposed in the literature for comparing/matching shapes in precise terms. This is done by proving explicit lower bounds for the proposed distance that involve many of the invariants previously reported by researchers. These lower bounds can be computed in polynomial time. The numerical implementations of the ideas are discussed and computational examples are presented.     

A Bayesian approach to vectorization of object boundaries from digital images and to geometrical uncertainty assessment

A new Bayesian approach is presented for extracting 2D object boundaries with measures of uncertainty. The boundaries are described by minimal closed sequences of segments and arcs, called mixed polygons. The sequence is minimal in the sense that it is able to describe all the geometrical properties of the boundary without being redundant. Based on geometrical measures evaluated on the object boundary model, a prior distribution is introduced in order to favor a mixed polygon with good geometrical properties, avoiding short sides, collinearity between segments, and so on. The estimation process is based on a two‐stage procedure that combines reversible‐jump MCMC (RJMCMC) and classic MCMC methods. The RJMCMC method is viewed as a model selection technique, and it is used to estimate the correct number of sides of the mixed polygon. The MCMC algorithm provides a sample of mixed polygons through which to evaluate the mixed polygon that best approximates the object boundary and its geometrical uncertainty. A convergence criterion for the RJMCMC method is provided. Copyright © 2011 John Wiley & Sons, Ltd.