Moment invariants for the analysis of 2D flow fields

We present a novel approach for analyzing two-dimensional (2D) flow field data based on the idea of invariant moments. Moment invariants have traditionally been used in computer vision applications, and we have adapted them for the purpose of interactive exploration of flow field data. The new class of moment invariants we have developed allows us to extract and visualize 2D flow patterns, invariant under translation, scaling, and rotation. With our approach one can study arbitrary flow patterns by searching a given 2D flow data set for any type of pattern as specified by a user. Further, our approach supports the computation of moments at multiple scales, facilitating fast pattern extraction and recognition. This can be done for critical point classification, but also for patterns with greater complexity. This multi-scale moment representation is also valuable for the comparative visualization of flow field data. The specific novel contributions of the work presented are the mathematical derivation of the new class of moment invariants, their analysis regarding critical point features, the efficient computation of a novel feature space representation, and based upon this the development of a fast pattern recognition algorithm for complex flow structures.     

Exact Computation of the Topology and Geometric Invariants of the Voronoi Diagram of Spheres in 3D

In this paper, we are addressing the exact computation of the Delaunay graph (or quasi-triangulation) and the Voronoi diagram of spheres using Wu’s algorithm. Our main contributions are first a methodology for automated derivation of invariants of the Delaunay empty circumsphere predicate for spheres and the Voronoi vertex of four spheres, then the application of this methodology to get all geometrical invariants that intervene in this problem and the exact computation of the Delaunay graph and the Voronoi diagram of spheres. To the best of our knowledge, there does not exist a comprehensive treatment of the exact computation with geometrical invariants of the Delaunay graph and the Voronoi diagram of spheres. Starting from the system of equations defining the zero-dimensional algebraic set of the problem, we are applying Wu’s algorithm to transform the initial system into an equivalent Wu characteristic (triangular) set. In the corresponding system of algebraic equations, in each polynomial (except the first one), the variable with higher order from the preceding polynomial has been eliminated (by pseudo-remainder computations) and the last polynomial we obtain is a polynomial of a single variable. By regrouping all the formal coefficients for each monomial in each polynomial, we get polynomials that are invariants for the given problem. We rewrite the original system by replacing the invariant polynomials by new formal coefficients. We repeat the process until all the algebraic relationships (syzygies) between the invariants have been found by applying Wu’s algorithm on the invariants. Finally, we present an incremental algorithm for the construction of Voronoi diagrams and Delaunay graphs of spheres in 3D and its application to Geodesy.     

Computation of medial axis and offset curves of curved boundaries in planar domain

In this paper, we begin our research from the generating theory of the medial axis. The normal equidistant mapping relationships between two boundaries and its medial axis have been proposed based on the moving Frenet frames and Cesaro’s approach of the differential geometry. Two pairs of adjoint curves have been formed and the geometrical model of the medial axis transform of the planar domains with curved boundaries has been established. The relations of position mapping, scale transform and differential invariants between the curved boundaries and the medial axis have been investigated. Based on this model, a tracing algorithm for the computation of the medial axis has been generated. In order to get the accurate medial axis and branch points, a Two_Tangent_Points_Circle algorithm and a Three_Tangent_Points_Circle algorithm have been generated, which use the results of the tracing algorithm as the initial values to make the iterative process effective. These algorithms can be used for the computation of the medial axis effectively and accurately. Based on the medial axis transform and the envelope theory, the trimmed offset curves of curved boundaries have been investigated. Several numerical examples are given at the end of the paper.     

快速不变矩算法基于CUDA的并行实现研究

不变矩自提出以来被广泛应用于目标识别系统中进行特征描述,这需要能够实时计算不变矩值。虽然人们提出了许多不变矩的快速算法,仍无法在单台PC机上实现不变矩的实时计算。本文分析了基于差分矩因子的不变矩快速算法的并行性,提出了一种基于CUDA（Compute Unified Device Architecture）的快速不变矩并行实现方法,并在NVIDIA Tesla C1060 GPU（Graphic Processing Unit）上实现。对所提出算法的计算性能与普通串行算法进行了对比分析。实验结果表明,本文所提出的并行计算方法极大地提高了不变矩的计算速度,可有效地用来进行实时特征提取。     

Invariants of six points and projective reconstruction from threeuncalibrated images

There are three projective invariants of a set of six points in general position in space. It is well known that these invariants cannot be recovered from one image, however an invariant relationship does exist between space invariants and image invariants. This invariant relationship is first derived for a single image. Then this invariant relationship is used to derive the space invariants, when multiple images are available. This paper establishes that the minimum number of images for computing these invariants is three, and the computation of invariants of six points from three images can have as many as three solutions. Algorithms are presented for computing these invariants in closed form. The accuracy and stability with respect to image noise, selection of the triplets of images and distance between viewing positions are studied both through real and simulated images. Applications of these invariants are also presented. Both the results of Faugeras (1992) and Hartley et al. (1992) for projective reconstruction and Sturm's method (1869) for epipolar geometry determination from two uncalibrated images with at least seven points are extended to the case of three uncalibrated images with only six points     

Invariants for the computation of intransitive and transitive Galois groups

One hard step in the computation of Galois groups by Stauduhar’s method is the construction of relative invariants. In this note, a representation-theoretic approach is given for the construction in the case of an intransitive group.In the second part of the article, it is shown that the construction can be used for groups that have a suitable intransitive subgroup. The construction solves an open question of Fieker and Klüners.     

Resonant terms and bifurcations of nonlinear control systems with one uncontrollable mode

In this paper we provide a simple algorithm of feedback design for systems with uncontrollable linearization with only quadratic degeneracy, such as transcritical and saddle-node bifurcations. This approach avoids the computation of nonlinear normal forms. It is based only on quadratic invariants which can be determined directly from the quadratic terms in the uncontrollable dynamics.     

Reconstruction Based Recognition of Scenes with Multiple Repeated Components

This paper proposes an invariance based recognition scheme for scenes with multiple repeated components. The scheme considers three component subsets which characterize the scene completely. Each such three component subset is reconstructed using single image based information. We have developed a mathematical framework for the projective reconstruction based on relative affine structure of each such three component building block. This is extended to the case when each of the components is a quadric. A set of projective invariants of three quadrics has also been obtained by us. Although the reconstruction scheme is general and applicable to all multiple repeated components, it requires the computation of infinite homography. The infinite homography and hence the reconstruction scheme are only image computable with the given information in the case of translational repetition. We therefore develop a recognition strategy for the specific case of translationally repeated quadrics. As a recognition strategy for scenes with multiple translationally repeated quadric components, we propose to compute and store invariant values for each such three component subsets. Experiments on real data have shown the applicability of this approach for recognition of aerial images of power plants. The discriminatory power of the invariants and the stability of the recognition results have also been experimentally demonstrated.     

Invariant based programming: basic approach and teaching experiences

Program verification is usually done by adding specifications and invariants to the program and then proving that the verification conditions are all true. This makes program verification an alternative to or a complement to testing. We describe here another approach to program construction, which we refer to as invariant based programming, where we start by formulating the specifications and the internal loop invariants for the program, before we write the program code itself. The correctness of the code is then easy to check at the same time as one is constructing it. In this approach, program verification becomes a complement to coding rather than to testing. The purpose is to produce programs and software that are correct by construction. We present a new kind of diagrams, nested invariant diagrams, where program specifications and invariants (rather than the control) provide the main organizing structure. Nesting of invariants provide an extension hierarchy that allows us to express the invariants in a very compact manner. We have studied the feasibility of formulating specifications and loop invariants before the code itself has been written in a number of case studies. Our experience is that a systematic use of figures, in combination with a rough idea of the intended behavior of the algorithm, makes it rather straightforward to formulate the invariants needed for the program, to construct the code around these invariants and to check that the resulting program is indeed correct. We describe our experiences from using invariant based programming in practice, both from teaching programmers how to construct programs that they prove correct themselves, and from teaching invariant based programming for CS students in class. D. A. Duce, J. Oliveira, P. Boca and R. Boute     

非线性循环不变式的自动生成

提出了一个自动生成非线性循环不变式的算法。循环不变式可以表示成一个带参数的多项式的形式,根据断言的归纳特性,将循环不变式的生成问题转变成一个约束求解问题,这个约束求解问题的每个解对应于一个循环不变式,如果约束求解问题仅有零解,则说明不存在该参数多项式形式的循环不变式。该算法在Maple中得到了实现,并通过一些实例说明了该算法的有效性。     

An object-oriented operation-based approach to translation between MOF metaschemas

This paper proposes a new approach to the schema translation problem. We deal with schemas whose metaschemas are instances of the OMG’s MOF. Most metaschemas can be defined as an instance of the MOF; therefore, our approach is widely applicable. We leverage the well-known object-oriented concepts embedded in the MOF and its instances (object types, attributes, relationship types, operations, IsA hierarchies, refinements, invariants, pre- and postconditions, etc.) to define metaschemas, schemas and their translations.The main contribution of our approach is the extensive use of object-oriented concepts in the definition of translation mappings, particularly the use of operations (and their refinements) and invariants, both of which are formalized in OCL. Our translation mappings can be used to check that two schemas are translations of each other, and to translate one into the other, in both directions. The translation mappings are declaratively defined by means of pre- and postconditions and invariants, and they can be implemented in any suitable language. From an implementation point of view, by taking a MOF-based approach we have a wide set of tools available, including tools that execute OCL. By way of example, we have defined all schemas and metaschemas in this paper and executed all the OCL expressions in the USE tool.     

基于小波和不变矩的图像copy-move篡改盲检测

针对数字图像取证中一类常见的复制粘贴图像伪造,本文提出了一种基于小波变换和不变矩提取的检测算法。该算法利用小波变换提取图像的低频分量,对低频分量分块进行不变矩特征提取,然后将特征矢量进行按行字典排序,并且配合图像块的偏移位置信息,进行图像复制伪造区域的检测和定位。实验表明该算法能够较精确地定位出复制和粘贴的图像伪造区域,并有效地减少了运算量,提高了检测效率。     

The illumination-invariant recognition of 3D objects using localcolor invariants

Traditional approaches to three dimensional object recognition exploit the relationship between three dimensional object geometry and two dimensional image geometry. The capability of object recognition systems can be improved by also incorporating information about the color of object surfaces. Using physical models for image formation, the authors derive invariants of local color pixel distributions that are independent of viewpoint and the configuration, intensity, and spectral content of the scene illumination. These invariants capture information about the distribution of spectral reflectance which is intrinsic to a surface and thereby provide substantial discriminatory power for identifying a wide range of surfaces including many textured surfaces. These invariants can be computed efficiently from color image regions without requiring any form of segmentation. The authors have implemented an object recognition system that indexes into a database of models using the invariants and that uses associated geometric information for hypothesis verification and pose estimation. The approach to recognition is based on the computation of local invariants and is therefore relatively insensitive to occlusion. The authors present several examples demonstrating the system's ability to recognize model objects in cluttered scenes independent of object configuration and scene illumination. The discriminatory power of the invariants has been demonstrated by the system's ability to process a large set of regions over complex scenes without generating false hypotheses     

基于投影的多尺度小波矩快速算法

多尺度小波变换矩采用几何矩定义，由信号在某一尺度下的小波逼近系数计算得到，它反映的是信号在该尺度下小波分解对应的视觉不变量。由于受到矩本身计算量的限制，小波矩的计算很难实时实现。本文提出了一种基于投影变换的二维多尺度小波变换矩快速算法。该快速算法通过投影变换将二维图像小波变换低频分量信息投影到一维空间中，从而降低了多尺度小波变换矩的计算复杂度，保证了计算精度。     

Edge and corner detection by photometric quasi-invariants

Feature detection is used in many computer vision applications such as image segmentation, object recognition, and image retrieval. For these applications, robustness with respect to shadows, shading, and specularities is desired. Features based on derivatives of photometric invariants, which we is called full invariants, provide the desired robustness. However, because computation of photometric invariants involves nonlinear transformations, these features are unstable and, therefore, impractical for many applications. We propose a new class of derivatives which we refer to as quasi-invariants. These quasi-invariants are derivatives which share with full photometric invariants the property that they are insensitive for certain photometric edges, such as shadows or specular edges, but without the inherent instabilities of full photometric invariants. Experiments show that the quasi-invariant derivatives are less sensitive to noise and introduce less edge displacement than full invariant derivatives. Moreover, quasi-invariants significantly outperform the full invariant derivatives in terms of discriminative power.     

Covariant-Conics Decomposition of Quartics for 2D Shape Recognition and Alignment

This paper outlines a new geometric parameterization of 2D curves where parameterization is in terms of geometric invariants and parameters that determine intrinsic coordinate systems. This new approach handles two fundamental problems: single-computation alignment, and recognition of 2D shapes under Euclidean or affine transformations. The approach is model-based: every shape is first fitted by a quartic represented by a fourth degree 2D polynomial. Based on the decomposition of this equation into three covariant conics, we are able, in both the Euclidean and the affine cases, to define a unique intrinsic coordinate system for non-singular bounded quartics that incorporates usable alignment information contained in the polynomial representation, a complete set of geometric invariants, and thus an associated canonical form for a quartic. This representation permits shape recognition based on 11 Euclidean invariants, or 8 affine invariants. This is illustrated in experiments with real data sets.     

Passive testing of communicating systems with timeouts

ContextThe design of complex systems demands methodologies to analyze its correct behaviour. It is usual that a correct behaviour is determined by the compliance with temporal requirements. Currently, testing is the most used technology to validate the correctness of systems. Although several techniques that take into account time aspects have been proposed, most of them require the tester interacts with the system. However, if this is not possible, it is necessary to apply a passive testing approach where the tester monitors the behaviour of the system.ObjectiveThe aim of this paper is to propose a methodology to perform passive testing on communicating systems in which the behaviour of their components must fulfill temporal restrictions associated with both performance and delays/timeouts.MethodOur framework uses algorithms for checking traces collected from the systems against invariants which formally represent the most relevant properties that must be fulfilled by the system. In order to support the feasibility of the methodology, we have performed an empirical study on a complex system for automatic recognition of images based on a pipeline architecture. We have analyzed the correctness of the system’s behaviour with respect to a set of invariants. Finally, an experiment, based on mutations of the system, was conducted to study the level of detection of a set of invariants.ResultsDifferent errors were detected and fixed along the development of the system by means of the proposed methodology. The results of the experiments with the mutated versions of the system indicated that the designed set of invariants was more effective in finding errors associated to temporal aspects than those related to communication among components.ConclusionThe proposed technique has been shown to be very useful for analyzing complex timed systems, and find errors when the tester has no control over their behaviour.