Search

In this paper we propose the graduated nonconvexity and concavity procedure (GNCCP) as a general optimization framework to approximately solve the combinatorial optimization problems defined on the set of partial permutation matrices. GNCCP comprises two sub-procedures, graduated nonconvexity which realizes a convex relaxation and graduated concavity which realizes a concave relaxation. It is proved that GNCCP realizes exactly a type of convex-concave relaxation procedure (CCRP), but with a much simpler formulation without needing convex or concave relaxation in an explicit way. Actually, GNCCP involves only the gradient of the objective function and is therefore very easy to use in practical applications. Two typical related NP-hard problems, partial graph matching and quadratic assignment problem (QAP), are employed to demonstrate its simplicity and state-of-the-art performance. [ABSTRACT FROM PUBLISHER]

Manifold learning has been a popular method in many areas such as classification and recognition. In this paper, we propose a novel algorithm for pedestrian tracking based on our previous work on manifold learning. A new kind of manifold subspace is introduced, in which the intrinsic features of the target's motion can be best preserved, and the dimensionality of feature is very low. In the proposed subspace, variations of continuous pedestrian postures can be represented well by these intrinsic features. This also validates our conjecture that the movement of pedestrians can be described by some intrinsic and low-dimensional features, which are significant for tracking. Although intrinsic features are useful for tracking, algorithms that directly apply intrinsic features could not guarantee stable performance due to the influence from a complicated background. To address this issue, a foreground extraction method is introduced to enhance tracking stability by selecting the most discriminative color features to automatically distinguish the foreground from the candidate image. This preprocessing stage is proven to promote the accuracy of low-dimensional feature representation in pedestrian tracking. The whole tracking procedure, particularly dimensionality reduction, is linear and fast without complicated calculations. The experimental results validate the effectiveness of our algorithm under challenging conditions, such as a complex background, various pedestrian postures, and even occlusion. [ABSTRACT FROM PUBLISHER]

The path following algorithm was proposed recently to approximately solve the matching problems on undirected graph models and exhibited a state-of-the-art performance on matching accuracy. In this paper, we extend the path following algorithm to the matching problems on directed graph models by proposing a concave relaxation for the problem. Based on the concave and convex relaxations, a series of objective functions are constructed, and the Frank-Wolfe algorithm is then utilized to minimize them. Several experiments on synthetic and real data witness the validity of the extended path following algorithm. [ABSTRACT FROM PUBLISHER]