Differential and Integral Geometry of Linear Scale-Spaces

Linear scale-space theory provides a useful framework to quantify the differential and integral geometry of spatio-temporal input images. In this paper that geometry comes about by constructing connections on the basis of the similarity jets of the linear scale-spaces and by deriving related systems of Cartan structure equations. A linear scale-space is generated by convolving an input image with Green's functions that are consistent with an appropriate Cauchy problem. The similarity jet consists of those geometric objects of the linear scale-space that are invariant under the similarity group. The constructed connection is assumed to be invariant under the group of Euclidean movements as well as under the similarity group. This connection subsequently determines a system of Cartan structure equations specifying a torsion two-form, a curvature two-form and Bianchi identities. The connection and the covariant derivatives of the curvature and torsion tensor then completely describe a particular local differential geometry of a similarity jet. The integral geometry obtained on the basis of the chosen connection is quantified by the affine translation vector and the affine rotation vectors, which are intimately related to the torsion two-form and the curvature two-form, respectively. Furthermore, conservation laws for these vectors form integral versions of the Bianchi identities. Close relations between these differential geometric identities and integral geometric conservation laws encountered in defect theory and gauge field theories are pointed out. Examples of differential and integral geometries of similarity jets of spatio-temporal input images are treated extensively.     

Flux, sorting, and supercomputer organization for AI applications

A central issue for the design of massively parallel computers is their ability to sort. We consider organizations that are suitable for fast sorting, both those that use point-to-point connections and those that connect processors with multipoint nets. We show that for fast sorting and minimal area, nets must connect at least √n nodes each, if the network has n nodes. We then discuss some of the ways that fast-sorting networks can be used to speed up other processes, such as combinatorial search.     

Simple mechanical control systems with constraints

We apply some recently developed control theoretic techniques to the analysis of a class of mechanical systems with constraints. Certain simple aspects of the theory of affine connections play an important part in our presentation. The necessary background is presented in order to illustrate how the methods may be applied. The bulk of this paper is devoted to a detailed analysis of some examples of nonholonomic mechanical control systems. We look at the Heisenberg system, the upright rolling disk, the roller racer, and the snakeboard     

Parallel computations and committee constructions

The paper reviewed the results bearing out the deep-seated relation between the parallel computations and learning procedures for the laminated neural networks one of whose formalizations is represented by the theory of committee constructions. Additionally, consideration was given to two combinatorial problems concerned with learning pattern recognition in the class of affine committees—the problem of verifying existence of a three-element affine separating committee and that of element-minimal affine separating committee. The first problem was shown to be N P-complete, whereas the second problem is N P-hard and does not belong to the Apx class.     

Recognition of Symmetrical Images Using Affine Moment Invariants in both Frequency and Spatial Domains

: In this paper, a new set of affine moment invariants is proposed in the frequency domain. By thresholding the magnitude of the Discrete Fourier Transform (DFT) of affine transformation-related images, new images which are also related by affine transformation are constructed. Then some affine invariant features in the frequency domain are obtained from the reconstructed images. Experimental results are given to show that the new affine invariants are less sensitive to noise and the recognition rate is increased when using both the available spatial domain and the proposed frequency domain affine moment invariants. Received: 10 October 2000, Received in revised form: 25 July 2001, Accepted: 25 July 2001     

Other things besides number: Abstraction,constraint propagation,and string variable types

In constraint programming (CP), a combinatorial problem is modeled declaratively as a conjunction of constraints, each of which captures some of the combinatorial substructure of the problem. Constraints are more than a modeling convenience: every constraint is partially implemented by an inference algorithm, called a propagator, that rules out some but not necessarily all infeasible candidate values of one or more unknowns in the scope of the constraint. Interleaving propagation with systematic search leads to a powerful and complete solution method, combining a high degree of re-usability with natural, high-level modeling.A propagator can be characterized as a sound approximation of a constraint on an abstraction of sets of candidate values; propagators that share an abstraction are similar in the strength of the inference they perform when identifying infeasible candidate values. In this thesis, we consider abstractions of sets of candidate values that may be described by an elegant mathematical formalism, the Galois connection. We develop a theoretical framework from the correspondence between Galois connections and propagators, unifying two disparate views of the abstraction-propagation connection, namely the oft-overlooked distinction between representational and computational over-approximations. Our framework yields compact definitions of propagator strength, even in complicated cases (i.e., involving several types, or unknowns with internal structure); it also yields a method for the principled derivation of propagators from constraint definitions.We apply this framework to the extension of an existing CP solver to constraints over strings, that is, words of finite length. We define, via a Galois connection, an over-approximation for bounded-length strings, and demonstrate two different methods for implementing this over-approximation in a CP solver. First we use the Galois connection to derive a bounded-length string representation as an aggregation of existing scalar types; propagators for this representation are obtained by manual derivation, or automated synthesis, or a combination. Then we implement a string variable type, motivating design choices with knowledge gained from the construction of the over-approximation. The resulting CP solver extension not only substantially eases modeling for combinatorial string problems, but also leads to substantial efficiency improvements over prior CP methods.     

非线性系统的对称性与线性化

本文考察具有对称结构的仿射非线性控制系统的零动态与精确线性化之间的关系。结果表明，对一类关于群对称的仿射非线性控制系统，能够得到它的低维零动态，从而在系统研究和设计中便于问题的简化。特别，文中指明了一个有意义的事实：具有关于线性群或自由适当群对称结构的仿射非线性控制系统不能通过状态反馈实现精确线性化。     

A linear signal decomposition approach to affine invariant contour identification

Means for the identification of objects from contours despite affine transform induced distortions using a linear signal space decomposition are described. This technique also yields robust estimates of the 3-D rotations of a near planar object. The ability to determine object identity and orientation from a single model representation without iteration or combinatorial search proceeds from the use of affine invariant differential measures derived via Lie group theory. The technique is extremely robust owing to the error rejection properties of signal space projections. Results illustrating the resilience of the solutions in the presence of severe non-affine distortion and pixelization are given.     

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.     

脉宽调制控制系统的适定性

不连续动态系统的适定性(即解的唯一存在性)问题是混合系统研究的基本问题之一.脉宽调制控制系统可以表示成具有时变仿射不等式约束的分段仿射系统.该文首先在Carathéodory的解定义下导出了脉宽调制控制系统无滑模和跳跃的解的适定性的充分必要条件.然后利用该结果对PWM型DC-DC降压变换器的适定性的研究表明当载波信号h(t)=O时闭环PWM DC-DC变换器总是不适定的,当载波信号h(t)的参数和比例控制器的参数满足一定的条件时,比例控制的闭环PWM DC-DC变换器是适定的.     

Multiobjective parameter estimation for non-linear systems: affine information and least-squares formulation

This paper defines a class of system information—affine information—that includes both the dynamic residuals and some types of auxiliary information that can be used in system parameter estimation as special cases. The types of information that can be cast under the affine information format give rise to quadratic functions that measure the extent to which a model fits such information, and that can be aggregated in a single weighted quadratic cost functional. This allows the definition of a multiobjective methodology for parameter estimation in non-linear system identification, which allows taking into account any type of affine information. The results are presented in terms of a set of efficient solutions of the multiobjective estimation problem—such a solution set is more meaningful than a single model. Since any affine information leads to a convex (quadratic) functional, the whole set of efficient solutions is exactly accessible via the minimization of the quadratic functional with different weightings, via a least-squares minimization (a non-iterative, computationally inexpensive procedure). The decision stage, in which a single model is chosen from the Pareto-set, becomes well-defined with a single global solution. Residual variance, fixed point location, static function and static gain are shown to fit in the class of affine information. A buck DC-DC converter is used as example.     

Observer‐based controller design of discrete‐time piecewise affine systems

This paper presents a novel observer‐based controller design method for discrete‐time piecewise affine (PWA) systems. The basic idea is as follows: at first, a piecewise linear (without affine terms) state feedback controller and a PWA observer are designed separately, and then it is proved that the output feedback controller constructed by the resulting observer and state feedback controller gains can guarantee the stability of the closed‐loop system. During the controller design, the piecewise‐quadratic Lyapunov function technique is used. Moreover, the region information is taken into account to treat the affine terms, so the controller gains can be obtained by solving a set of linear matrix inequalities, which are numerically feasible with commercially available software. Three simulation examples are given finally to verify the proposed theoretical results. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

A mathematical framework for the control of piecewise-affine models of gene networks

This article introduces results on the control of gene networks, in the context of piecewise-affine models. We propose an extension of this well-documented class of models, where some input variables can affect the main terms of the equations, with a special focus on the case of affine dependence on inputs. Some generic control problems are proposed, which are qualitative, respecting the coarse-grained nature of piecewise-affine models. Piecewise constant feedback laws that solve these control problems are characterized in terms of affine inequalities, and can even be computed explicitly for a subclass of inputs. The latter is characterized by the condition that each state variable of the system is affected by at most one input variable. These general feedback laws are then applied to a two-dimensional example, consisting in two genes inhibiting each other. This example has been observed in real biological systems, and is known to present a bistable switch for some parameter values. Here, the parameters can be controlled, allowing to express feedback laws leading to various behaviours of this system, including bi-stability as well as situations involving a unique global equilibrium.     

A survey of some combinatorial results concerning functional dependencies in database relations

A databaseR has some obvious and less obvious parameters such as the number of attributes, the size |r|, the maximum size of a domain, the number of some special functional dependencies (e.g. the minimal keys), and so on. The main aim of this paper is to survey some of the results giving connections and inequalities among these parameters. The methods are of a combinatorial nature. A generalization of the numerical dependency is also considered.This work was supported by the Hungarian National Foundation for Scientific Research, Grant No. 2575.     

Deducible and Equivalent Structural Knowledges in Distributed Algorithms

The correctness of distributed algorithms usually relies upon the use of some knowledge about the underlying network (a specific topology, some metrics, etc.). We define equivalent structural knowledges to be such knowledges that can be computed distributively, one knowing the other. We present a combinatorial characterization of this equivalence. Some applications are also given: zero knowledge, classical metrics (size, diameter, etc.). This characterization is defined in terms of graphs coverings and quasicoverings. The proofs are based upon an algorithm proposed by Mazurkiewicz, and on techniques of termination detection by Shy, Szymanski, and Prywes.     

Numerically Invariant Signature Curves

Corrected versions of the numerically invariant expressions for the affine and Euclidean signature of a planar curve introduced by Calabi et al. in (Int. J. Comput. Vision, 26: 107–135, 1998) are presented. The new formulas are valid for fine but otherwise arbitrary partitions of the curve. We also give numerically invariant expressions for the four differential invariants parameterizing the three dimensional version of the Euclidean signature curve, namely the curvature, the torsion and their derivatives with respect to arc length.     

无源性、稳定性和最优性

本文考察仿射非线性控制系统的无源性、稳定性的最优性，以及这三者之间的关系，为分析稳定性，首先研究非线性控制系统和其线性近似的无源性之间的关系。然后指出，就仿射非线性控制系统而言，无源性、稳定性和最优性在某种意义下是反馈等价的。最后讨论了带量测输出的非线性系统的无源性、稳定性和最优性三者之间的关系。     

Homotopy techniques in linear programming

In this note, we consider the solution of a linear program, using suitably adapted homotopy techniques of nonlinear programming and equation solving that move through the interior of the polytope of feasible solutions. The homotopy is defined by means of a quadratic regularizing term in an appropriate metric. We also briefly discuss algorithmic implications and connections with the affine variant of Karmarkar's method.     

Graph Searching, Elimination Trees, and a Generalization of Bandwidth

The bandwidth minimization problem has a long history and a number of practical applications. In this paper we introduce a natural extension of bandwidth to partially ordered layouts. We consider this extension from three main viewpoints: graph searching, tree decompositions, and elimination orderings. The three graph parameters pathwidth, profile, and bandwidth related to linear layouts can be defined by variants of graph searching using a standard fugitive. Switching to an inert fugitive, the two former parameters are extended to treewidth and fill-in, and our first viewpoint considers the analogous tree-like extension that arises from the bandwidth variant. Bandwidth also has a definition in terms of ordered path decompositions, and our second viewpoint extends this in a natural way to ordered tree decompositions. In showing that both extensions are equivalent we employ the third viewpoint of elimination trees, as used in the field of sparse matrix computations. We call the resulting parameter the treespan of a graph and prove some of its combinatorial and algorithmic properties.