Efficient parameterized string matching

In parameterized string matching the pattern P matches a substring t of the text T if there exist a bijective mapping from the symbols of P to the symbols of t. We give simple and practical algorithms for finding all such pattern occurrences in sublinear time on average. The algorithms work for a single and multiple patterns.     

Scaled and permuted string matching

The goal of scaled permuted string matching is to find all occurrences of a pattern in a text, in all possible scales and permutations. Given a text of length n and a pattern of length m we present an O(n) algorithm.     

Improving the bit-parallel NFA of Baeza-Yates and Navarro for approximate string matching

We propose a new variant of the bit-parallel NFA of Baeza-Yates and Navarro (BPD) for approximate string matching [R. Baeza-Yates, G. Navarro, Faster approximate string matching, Algorithmica 23 (1999) 127-158]. BPD is one of the most practical approximate string matching algorithms under moderate pattern lengths and error levels [G. Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, J. ACM 46 (3) 1989 395-415; G. Navarro, M. Raffinot, Flexible Pattern Matching in Strings—Practical On-line Search Algorithms for Texts and Biological Sequences, Cambridge University Press, Cambridge, UK, 2002]. Given a length-m pattern and an error threshold k, the original BPD requires (m−k)(k+2) bits of space to represent an NFA with (m−k)(k+1) states. In this paper we remove redundancy from the original NFA representation. Our variant requires (m−k)(k+1) bits of space, which is optimal in the sense that exactly one bit per state is used. The space efficiency is achieved by using an alternative, but equally or even more efficient, simulation algorithm for the bit-parallel NFA. We also present experimental results to compare our modified NFA against the original BPD and its main competitors. Our new variant is more efficient than the original BPD, and it hence takes over/extends the role of the original BPD as one of the most practical approximate string matching algorithms under moderate values of k and m.     

Planar shape matching based on binary tree shape representation

In this paper we suggest a new way of representing planar two-dimensional shapes and a shape matching method which utilizes the new representation. Through merging of the neighboring boundary runs, a shape can be partitioned into a set of triangles. These triangles are inherently connected according to a binary tree structure. Here we use the binary tree with the triangles as its nodes to represent the shape. This representation is found to be insensitive to shape translation, rotation, scaling and skewing changes due to viewer's location changes (or the object's pose changes). Furthermore, the representation is of multiresolution.

In shape matching we compare the two trees representing two given shapes node by node according to the breadth-first tree traversing sequence. The comparison is done from top of the tree and moving downward, which means that we first compare the lower resolution approximations of the two shapes. If the two approximations are different, the comparison stops. Otherwise, it goes on and compares the finer details of the two shapes. Only when the two shapes are very similar, will the two corresponding trees be compared entirely. Thus, the matching algorithm utilizes the multiresolution characteristic of the tree representation and appears to be very efficient.     

Applications of approximate string matching to 2D shape recognition

A new method for the recognition of arbitrary two-dimensional (2D) shapes is described. It is based on string edit distance computation. The recognition method is invariant under translation, rotation, scaling and partial occlusion. A set of experiments are described demonstrating the robustness and reliability of the proposed approach.     

Graph matching for object recognition and recovery

A robust skeleton-based graph matching method for object recognition and recovery applications is presented. The object model uses both a skeleton model and contour segment models, for object recognition and recovery. The presented skeleton-based shape matching method uses a combination of both structural and statistical methods that are applied in a sequential manner, which largely reduce the matching space when compared with previous works. This also provides a good alternate means to alleviate difficulties encountered in segmentation problems. Experiments of object recovery using real biomedical image samples have shown satisfactory results.     

基于目标不变量的识别方法研究

一、引言不变量理论在80年代末引入计算机视觉领域,1991年召开了不变量在计算机视觉应用方面的国际研讨会。目前,对这一课题的研究引起了国内外学者的极大兴趣。视觉不变量理论的优点在于它对目标形状的描述不受目标物体的姿态、透视投影和摄像机内部参数的影响。同时它可以冗余地表示目标全局结构特征,当发生部分遮挡时,可以从剩余部分计算出表示全局的结构不变信息。     

Moving-edge detection via heat flow analogy

In this paper, a new and automatic moving-edge detection algorithm is proposed, based on using the heat flow analogy. This algorithm starts with anisotropic heat diffusion in the spatial domain, to remove noise and sharpen region boundaries for the purpose of obtaining high quality edge data. Then, isotropic and linear heat diffusion is applied in the temporal domain to calculate the total amount of heat flow. The moving-edges are represented as the total amount of heat flow out from the reference frame. The overall process is completed by non-maxima suppression and hysteresis thresholding to obtain binary moving-edges. Evaluation, on a variety of data, indicates that this approach can handle noise in the temporal domain because of the averaging inherent of isotropic heat flow. Results also show that this technique can detect moving-edges in image sequences, without background image subtraction.     

Accurate and speedy computation of image Legendre moments for computer vision applications

A novel algorithm that permits the fast and accurate computation of the Legendre image moments is introduced in this paper. The proposed algorithm is based on the block representation of an image and on a new image representation scheme, the Image Slice Representation (ISR) method. The ISR method decomposes a gray-scale image as an expansion of several two-level images of different intensities (slices) and thus enables the partial application of the well-known Image Block Representation (IBR) algorithm to each image component. Moreover, using the resulted set of image blocks, the Legendre moments’ computation can be accelerated through appropriate computation schemes. Extensive experiments prove that the proposed methodology exhibits high efficiency in calculating Legendre moments on gray-scale, but furthermore on binary images. The newly introduced algorithm is suitable for the computation of the Legendre moments for pattern recognition and computer vision applications, where the images consist of objects presented in a scene.     

A structure-preserved local matching approach for face recognition

In this paper, a novel local matching method called structure-preserved projections (SPP) is proposed for face recognition. Unlike most existing local matching methods which neglect the interactions of different sub-pattern sets during feature extraction, i.e., they assume different sub-pattern sets are independent; SPP takes the holistic context of the face into account and can preserve the configural structure of each face image in subspace. Moreover, the intrinsic manifold structure of the sub-pattern sets can also be preserved in our method. With SPP, all sub-patterns partitioned from the original face images are trained to obtain a unified subspace, in which recognition can be performed. The efficiency of the proposed algorithm is demonstrated by extensive experiments on three standard face databases (Yale, Extended YaleB and PIE). Experimental results show that SPP outperforms other holistic and local matching methods.     

基于卫星云图的台风云系特征提取算法研究

利用静止卫星观测数据,进行了滤波、去噪等预处理,及综合优化的云检测处理;在此基础上,利用改进的正交匹配小波算法和优化的遗传-模糊聚类算法,实现了西北太平洋地区台风云系特征的提取。这两种算法提取出的台风云系特征参数简单,用于热带气旋(Tropical Cyclone,TC)的监测预警中可提高效率,适用于台风预报预警监测的业务化应用。     

图像识别技术在零件装配自动识别中的应用

针对工业装配生产线的自动装配问题,基于机器视觉技术,采用图像处理的方法识别定位工件。考虑透镜的径向一阶畸变,采用RAC两步标定法标定摄像机参数,并在线对该文的方法进行了验证。实验结果表明,该方法能够获得很好的识别效果,达到一般装配作业的实时性和精度要求。     

HEGM: A hierarchical elastic graph matching for hand gesture recognition

A hierarchical scheme for elastic graph matching applied to hand gesture recognition is proposed. The proposed algorithm exploits the relative discriminatory capabilities of visual features scattered on the images, assigning the corresponding weights to each feature. A boosting algorithm is used to determine the structure of the hierarchy of a given graph. The graph is expressed by annotating the nodes of interest over the target object to form a bunch graph. Three annotation techniques, manual, semi-automatic, and automatic annotation are used to determine the position of the nodes. The scheme and the annotation approaches are applied to explore the hand gesture recognition performance. A number of filter banks are applied to hand gestures images to investigate the effect of using different feature representation approaches. Experimental results show that the hierarchical elastic graph matching (HEGM) approach classified the hand posture with a gesture recognition accuracy of 99.85% when visual features were extracted by utilizing the Histogram of Oriented Gradient (HOG) representation. The results also provide the performance measures from the aspect of recognition accuracy to matching benefits, node positions correlation and consistency on three annotation approaches, showing that the semi-automatic annotation method is more efficient and accurate than the other two methods.     

A new method for representing and matching shapes of natural objects

A new method for the representation and comparison of irregular two-dimensional shapes is presented. This method uses a polar transformation of the contour points about the geometric centre of the object. The distinctive vertices of the shape are extracted and used as comparative parameters to minimize the difference of contour distance from the centre. Experiments are performed, more than 39 000 comparisons of database shapes, provided by Sebastian et al. (ICCV (2001) 755), are made and the results are compared to those obtained therein. In addition, 450 comparisons of leaf shape are made and leaves of very similar shape are accurately distinguished. The method is shown to be invariant to translation, rotation and scaling and highly accurate in shape distinction. The method shows more tolerance to scale variation than that of Sebastian et al. (ICCV (2001) 755) and is less computationally intense.     

Vehicle matching in smart camera networks using image projection profiles at multiple instances

Tracking vehicles using a network of cameras with non-overlapping views is a challenging problem of great importance in traffic surveillance. One of the main challenges is accurate vehicle matching across the cameras. Even if the cameras have similar views on vehicles, vehicle matching remains a difficult task due to changes of their appearance between observations, and inaccurate detections and occlusions, which often occur in real scenarios. To be executed on smart cameras the matching has also to be efficient in terms of needed data and computations. To address these challenges we present a low complexity method for vehicle matching robust against appearance changes and inaccuracies in vehicle detection. We efficiently represent vehicle appearances using signature vectors composed of Radon transform like projections of the vehicle images and compare them in a coarse-to-fine fashion using a simple combination of 1-D correlations. To deal with appearance changes we include multiple observations in each vehicle appearance model. These observations are automatically collected along the vehicle trajectory. The proposed signature vectors can be calculated in low-complexity smart cameras, by a simple scan-line algorithm of the camera software itself, and transmitted to the other smart cameras or to the central server. Extensive experiments based on real traffic surveillance videos recorded in a tunnel validate our approach.     

Novel moment invariants for improved classification performance in computer vision applications

A novel set of moment invariants based on the Krawtchouk moments are introduced in this paper. These moment invariants are computed over a finite number of image intensity slices, extracted by applying an innovative image representation scheme, the image slice representation (ISR) method. Based on this technique an image is decomposed to a several non-overlapped intensity slices, which can be considered as binary slices of certain intensity. This image representation gives the advantage to accelerate the computation of image's moments since the image can be described in a number of homogenous rectangular blocks, which permits the simplification of the computation formulas. The moments computed over the extracted slices seem to be more efficient than the corresponding moments of the same order that describe the whole image, in recognizing the pattern under processing. The proposed moment invariants are exhaustively tested in several well known computer vision datasets, regarding their rotation, scaling and translation (RST) invariant recognition performance, by resulting to remarkable outcomes.     

基于多源特征后融合的分层目标检测算法

目标检测是计算机视觉领域的热门研究课题,是视频内容分析的基础。文中提出了一种基于图像多源特征后融合的分层目标检测算法。在该算法中,使用多级决策的思想对目标检测任务进行粗细两个粒度的划分。在粗粒度层面, 先使用HOG特征对图像进行分类,根据分类器的置信度分数,将测试图像分为正例、负例和不确定例。在细粒度层面,使用多种视觉特征以及多种核函数后融合的方法对不确定域中的图像做进一步分类。在同一数据集上设置了3组对比实验。实验结果表明,所提算法在各个评价指标上都有出色的表现,且在实际视频的目标检测中的效果优于Faster-RCNN。     

Multi-scale Conditional Random Fields for first-person activity recognition on elders and disabled patients

We propose a novel pervasive system to recognise human daily activities from a wearable device. The system is designed in a form of reading glasses, named ‘Smart Glasses’, integrating a 3-axis accelerometer and a first-person view camera. Our aim is to classify subject’s activities of daily living (ADLs) based on their vision and head motion data. This ego-activity recognition system not only allows caretakers to track on a specific person (such as disabled patient or elderly people), but also has the potential to remind/warn people with cognitive impairments of hazardous situations. We present the following contributions: a feature extraction method from accelerometer and video; a classification algorithm integrating both locomotive (body motions) and stationary activities (without or with small motions); a novel multi-scale dynamic graphical model for structured classification over time. In this paper, we collect, train and validate our system on two large datasets: 20 h of elder ADLs datasets and 40 h of patient ADLs datasets, containing 12 and 14 different activities separately. The results show that our method efficiently improves the system performance (F-Measure) over conventional classification approaches by an average of 20%–40% up to 84.45%, with an overall accuracy of 90.04% for elders. Furthermore, we also validate our method on 30 patients with different disabilities, achieving an overall accuracy up to 77.07%.     

A novel Hough transform method for line detection by enhancing accumulator array

In this paper, an improved Hough transform (HT) method is proposed to robustly detect line segments in images with complicated backgrounds. The work focuses on detecting line segments of distinct lengths, totally independent of prior knowledge of the original image. Based on the characteristics of accumulation distribution obtained by conventional HT, a local operator is implemented to enhance the difference between the accumulation peaks caused by line segments and noise. Through analysis of the effect of the operator, a global threshold is obtained in the histogram of the enhanced accumulator to detect peaks. Experimental results are provided to demonstrate the efficiency and robustness of the proposed method.     

Two-dimensional object recognition by matching local properties of contour points

This paper describes a two-stage Hough procedure for two-dimensional object recognition based on matching local properties of a model set of contour points. The procedure makes use of three strategies: subdivision of the parameter space, classification by multiple properties, and non-maximum suppression. The first stage estimates likely values in a coarsely quantized space of position and orientation. The second stage verifies these estimates in a more precise space with a large set of model points. In both cases, matching of model points to image contour points is based on tangent, curvature and contrast. The evaluation of the parameter space is greatly simplified by simultaneous non-maximum suppression over neighborhoods of both parameters. Experiments show that these strategies are both efficient and robust, even in the case of complex and partial data. One example uses overlapping parts, such as might occur in industrial situations.