Direct methods for recovering motion

We have developed direct methods for recovering the motion of an observer in a static environment in the case of pure rotation, pure translation, and arbitrary motion when the rotation is known. Some of these methods are based on the minimization of the difference between the observed time derivative of brightness and that predicted from the spatial brightness gradient, given the estimated motion. We minimize the square of the integral of this difference taken over the image region of interest. Other methods presented here exploit the fact that surfaces have to be in front of the observer in order to be seen.We do not establish point correspondences, nor do we estimate the optical flow. We use only first-order derivatives of the image brightness, and we do not assume an analytic form for the surface. We show that the field of view should be large to accurately recover the components of motion in the direction toward the image region. We also demonstrate the importance of points where the time derivative of brightness is small and discuss difficulties resulting from very large depth ranges. We emphasize the need for adequate filtering of the image data before sampling to avoid aliasing, in both the spatial and temporal dimensions.This research was supported by the National Science Foundation under Grant No. DMC85-11966. Additional support was provided by NASA (Grant No. GSFC 5-1162) and by the Veteran's Administration.BKPH on leave from the Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139.     

Subspace methods for face recognition

Studying the inherently high-dimensional nature of the data in a lower dimensional manifold has become common in recent years. This is generally known as dimensionality reduction. A very interesting strategy for dimensionality reduction is what is known as subspace analysis. Beginning with the Eigenface method, face recognition and in general computer vision has witnessed a growing interest in algorithms that capitalize on this idea and an ample number of such efficient algorithms have been proposed. These algorithms mainly differ in the kind of projection method used (linear or non-linear) or in the criterion employed for classification. The objective of this paper is to provide a comprehensive performance evaluation of about twenty five different subspace algorithms under several important real time test conditions. For this purpose, we have considered the performance of these algorithms on data taken from four standard face and object databases namely ORL, Yale, FERET and the COIL-20 object database. This paper also presents some theoretical aspects of the algorithm and the analysis of the simulations carried out.     

Enhanced Local Subspace Affinity for feature-based motion segmentation

We present a new motion segmentation algorithm: the Enhanced Local Subspace Affinity (ELSA). Unlike Local Subspace Affinity, ELSA is robust in a variety of conditions even without manual tuning of its parameters. This result is achieved thanks to two improvements. The first is a new model selection technique for the estimation of the trajectory matrix rank. The second is an estimation of the number of motions based on the analysis of the eigenvalue spectrum of the Symmetric Normalized Laplacian matrix. Results using the Hopkins155 database and synthetic sequences are presented and compared with state of the art techniques.     

Programmer-transparent coordination of recovering concurrentprocesses: philosophy and rules for efficient implementation

An approach to coordination of cooperating concurrent processes, each capable of error direction and recovery, is presented. Error detection, rollback, and retry in a process are specified by a well-structured language construct called recovery block. Recovery points of processes must be properly coordinated to prevent a disastrous avalanche of process rollbacks. The approach relies on an intelligent processor system (that runs processes) capable of establishing and discarding the recovery points of interacting processes in a well coordinated manner such that a process never makes two consecutive rollbacks without making a retry between the two, and every process rollback becomes a minimum-distance rollback. Following a discussion of the underlying philosophy of the author's approach, basic rules of reducing storage and time overhead in such a processor system are discussed. Examples are drawn from the systems in which processes communicate through monitors     

Subspace identification methods for Hammerstein systems: rank constraint and dimension problem

This article studies the subspace identification methods (SIMs) for Hammerstein systems with major focus on a rank constraint and the related dimension problem. We analyse the effects of the rank constraint on the three steps of a unifying framework for SIMs: the rank constraint has no effect on the first two steps, but does so on the third step. If the rank constraint is ignored, as in the existing over-parametrised method (OPM) for Hammerstein system identification, the optimality of the resulting estimate can still be established. Even so, the OPM may suffer from the dimension problem resulting in a low numerical efficiency. To resolve the dimension problem, we propose a new subspace-based method, named as the least-parametrised method (LPM), for identification of Hammerstein systems with non-coupling input nonlinearities. Simulation results are provided to demonstrate the effectiveness of the LPM, and show the necessity of considering the rank constraint to improve the numerical efficiency.     

高效多子空间Skyline查询处理算法

随着Skyline查询应用的增多,子空间Skyline查询成为热点。针对实际应用中用户从多角度审视某一数据集的需求,充分研究了多子空间Skyline查询问题。在分析现有子空间Skyline查询算法解决该问题不足的基础上,提出了子空间立方体群(subspace skycube group,SSG)结构,并给出了基于该结构的同时计算任意多个子空间Skyline查询的MSSC(multiple subspace skycube)算法。该算法采用子空间候选集(subspace candidate sets,SCS),并充分利用了子空间立方体群结构中各子空间Skyline结果间的共享关系;在此基础上,算法采用求和过滤以及最大值过滤等方法,对数据集进行剪枝和过滤,从而进一步提高算法效率。最后,分别用人造数据和真实数据对算法进行实验,并与现有算法进行比较,结果表明MSSC算法可以高效地解决多子空间Skyline查询问题。     

空间光滑且完整的子空间学习算法

提出一种空间光滑且完整的子空间学习算法.它融合了主成分分析、空间光滑的子空间学习算法和局部敏感判别投影的技术特点.不但保持了数据流形的全局和局部几何结构,而且保持了它的判别信息和空间关系.从原始样本提取全局和局部特征经线性变换组成新样本,再从新样本中提取最佳分类特征,最后由分类器完成分类识别.同一般的子空间算法相比,该算法提高了识别率.实验结果验证了该算法的有效性.     

一种基于子空间划分的最优k-匿名动态规划算法

目前大部分k-匿名算法未能有效兼顾算法效率和发布数据的可用性.从子空间划分的角度研究基于空间多维划分的最优k-匿名问题,发现所有可能的子空间数量远小于所有可能的划分数量,并从理论上分析基于子空间划分的最优k-匿名问题具有最优子结构性质,从而设计出基于子空间划分的隐私保护最优k-匿名动态规划算法k-ASPDP.实验对算法k-ASPDP发布数据的可用性及算法效率与同类算法进行比较分析.实验结果表明,算法k-ASPDP是有效可行的.     

基于神经网络的运动参数估计

分别就两种约束使用神经网络对三维刚体运动进行参数估计.一是基于三维点匹配,将预测的运动参数作用于运动前的坐标,与运动后坐标进行比较;二是基于二维运动场,将使用预测的运动参数计算得出的二维运动场与图像序列中计算得出的二维运动场进行比较.两个神经网络均使用Newton-Raphson方法更新权值,以达到目标误差最小化.通过实验验证了该神经网络方法.     

高维分类属性的子空间聚类算法

高维分类数据的处理一直是数据挖掘研究所面临的巨大挑战.传统聚类算法主要针对低雏连续性数据的聚类,难以处理高维分类属性数据集.本文提出一种处理高维分类数据集的子空间聚类算法(FP-Tree-based SUBspace clustering algorithm,FPSUB),利用频繁模式树将聚类问题转化为寻找属性值的频繁模式发现问题,得到的频繁模式即候选子空间,然后基于这些子空间进行聚类.针对真实数据集的实验结果表明,FPSUB算法比其他算法具有更高的准确度.     

ClusterSLAM: A SLAM backend for simultaneous rigid body clustering and motion estimation

Computational Visual Media - We present a practical backend for stereo visual SLAM which can simultaneously discover individual rigid bodies and compute their motions in dynamic environments. While...     

Partial state observability recovering for linear systems by additional sensor implementation

This paper deals with the problem of additional sensor location in order to recover the observability of any given part of the state for structured linear systems. The proposed method is based on a graph-theoretic approach and assumes only the knowledge of the system’s structure. We first provide new graphical necessary and sufficient conditions for the generic partial observability. Then, we study the location of additional sensors in order to satisfy the latter conditions. We provide necessary and sufficient requirements to be satisfied by these additional sensors and all their possible locations. The proposed solution is simple to implement because it is based on well-known algorithms, usually used for finding successors and predecessors of vertex subsets or on computation of maximal linkings in a digraph. All the used algorithms have polynomial complexity orders.     

Passivity-preserving splitting methods for rigid body systems

A rigid body model for the dynamics of a marine vessel, used in simulations of offshore pipe-lay operations, gives rise to a set of ordinary differential equations with controls. The system is input–output passive. We propose passivity-preserving splitting methods for the numerical solution of a class of problems which includes this system as a special case. We prove the passivity-preservation property for the splitting methods, and we investigate stability and energy behaviour in numerical experiments. Implementation is discussed in detail for a special case where the splitting gives rise to the subsequent integration of two completely integrable flows. The equations for the attitude are reformulated on \(\mathit{SO}(3)\) using rotation matrices rather than local parameterisations with Euler angles.     

State and input observability recovering by additional sensor implementation: A graph-theoretic approach

This paper deals with the problem of additional sensor location in order to recover the state and input observability for structured linear systems. The proposed method is based on a graph-theoretic approach and assumes only the knowledge of the system’s structure. It allows one to provide the minimal number of the required sensors and either their pertinent location or a necessary and sufficient condition which allows one to check if a sensor location is adequate or not. We obtain a sensor placement procedure based on classical and well-known graph theory algorithms, which have polynomial complexity orders.     

Structure from motion of rigid and jointed objects

A method for recovering the three-dimensional structure of moving rigid and jointed objects from several single camera views is presented. The method is based on the fixed axis assumption: all movement consists of translations and rotations about an axis that is fixed in direction for short periods of time. This assumption makes it possible to recover the structure of any group of two or more rigidly connected points. The structure of jointed objects is recovered by analyzing them as collections of rigid parts, and then unifying the structures proposed for the parts. The method presented here has been tested on several sets of data, including movies used to demonstrate human perception of structure from motion.     

基于高维空间的在线高效子空间Skyline算法——CSky

Skyline计算是要发现数据集中不被其他点支配的所有点的集合.近来,它在实时在线服务方面的良好应用前景,使其成为数据库研究领域的一个热点.实际应用中,用户通常期望快速、渐进地返回Skyline计算结果,因此文中主要讨论了高维空间子空间Skyline渐进查询问题.据我们所知,现有的Skyline计算方法都不能直接或者通过简单修改来高效解决该种查询问题.BNL(Blocked Nested Loop)算法是一个可用来进行子空间Skyline计算的算法,但是,该方法低效且非渐进.基于此,文中提出了在线高效子空间Skyline算法--CSky(Count the Skyline).该算法充分利用了一个新颖数据结构--InvertS的特征,即通过对目标数据集进行排序,存放最可能为Skyline点的数据于算法优先扫描的位置,这使得CSky算法能高效计算出任意子空间上的Skyline;同时,CSky每次计算子空间Skyline查询时,至多访问一遍数据库;再有,算法扫描一个点时,只需和当前已发现的Skyline点进行比较即能判断该点是否为Skyline点,保证了算法的渐进性.这样,相比BNL,CSky大大减少了计算开销,具有其他基于索引的Skyline算法计算Skyline时的高效,且这种高效适用于所有子空间.理论分析和实验表明,在解决高维空间子空间Skyline查询问题方面,CSky性能大大优于BNL.     

隐子空间聚类算法的改进及其增量式算法

基于稀疏表示的隐子空间聚类(latent subspace clustering,LSC)算法,相对于传统的子空间聚类算法,具有更快的聚类速度,使其适用于更大的数据集,但是其存在字典训练具有随机性,占用内存过多等缺陷。参照LC-KSVD字典训练算法的思想,通过将一部分信号的标签信息添加进字典训练阶段,以此提高了字典的判别性,进而提出了聚类精度更好的ILSC(improved LSC)算法。但相比于LSC算法,ILSC算法在字典训练阶段的耗时却大幅增加,针对此缺陷,参照增量字典训练的思想,提出了ILSC算法的增量式聚类算法I2LSC(incremental ILSC),在确保聚类精度、NMI(normalized mutual information)、RI(Rand index)值高于LSC且与ILSC相当的同时,较之ILSC具有更快的运行速度。     

Exponential Taylor methods: Analysis and implementation

For the time integration of semilinear systems of differential equations, a class of multiderivative exponential integrators is considered. The methods are based on a Taylor series expansion of the semilinearity about the numerical solution, the required derivatives are computed by automatic differentiation. Inserting these derivatives into the variation-of-constants formula results in an exponential integrator which requires the action of the exponential of an augmented Jacobian only.The convergence properties of such exponential integrators are analyzed, and potential sources of numerical instabilities are identified. In particular, it is shown that local linearization gives rise to better stability for stiff problems. A number of numerical experiments illustrate the theoretical results.     

Polynomial methods for structure from motion

The authors analyze the limitations of structure from motion (SFM) methods presented in the literature and propose the use of a polynomial system of equations, with the unit quaternions representing rotation, to recover SFM under perspective projection. The authors combine the equations by the method of resultants with the MAXIMA symbolic algebra system, reducing the system to a single polynomial. Its real roots are then found with Sturm sequences. Since this system has multiple solutions, a hypothesize-and-verify scheme is used to eliminate incorrect ones. The scheme diminishes the sensitivity of using polynomial equations. The authors examine the effect of different rotation axes and angles on SFM accuracy and compare the performance of the algorithm to a few earlier approaches. Generally, it is found that a large amount of motion is the most important factor in getting good SFM accuracy     

Comparison of methods for logic-query implementation

A logic query Q is a triple < G, LP, D, where G is the query goal, LP is a logic program without function symbols, and D is a set of facts, possibly stored as tuples of a relational database. The answers of Q are all facts that can be inferred from LP ∪ D and unify with G. A logic query is bound if some argument of the query goal is a constant; it is canonical strongly linear (a CSL query) if LP contains exactly one recursive rule and this rule is linear, i.e., only one recursive predicate occurs in its body. In this paper, the problem of finding the answers of a bound CSL query is studied with the aim of comparing for efficiency some well-known methods for implementing logic queries: the eager method, the counting method, and the magic-set method. It is shown that the above methods can be expressed as algorithms for finding particular paths in a directed graph associated to the query. Within this graphical formalism, a worst-case complexity analysis of the three methods is performed. It turns out that the counting method has the best upper bound for noncyclic queries. On the other hand, since the counting method is not safe if queries are cyclic, the method is extended to safely implement this kind of queries as well.