9484829
Fast Large-Scale Spectral Clustering by Sequential Shrinkage Optimization
In many applications, we need to cluster large-scale data objects. However, some recently proposed clustering algorithms such as spectral clustering can hardly handle large-scale applications due to the complexity issue, although their effectiveness has been demonstrated in previous work. In this paper, we propose a fast solver for spectral clustering. In contrast to traditional spectral clustering algorithms that first solve an eigenvalue decomposition problem, and then employ a clustering heuristic to obtain labels for the data points, our new approach sequentially decides the labels of relatively well-separated data points. Because the scale of the problem shrinks quickly during this process, it can be much faster than the traditional methods. Experiments on both synthetic data and a large collection of product records show that our algorithm can achieve significant improvement in speed as compared to traditional spectral clustering algorithms.
1299362
A new cut detection algorithm with constant false-alarm ratio for video segmentation
In this paper, a new cut detection algorithm with constant false-alarm ratio (CFAR) is proposed for video segmentation. In our method, a theoretical threshold determination strategy using the non-parameter based CFAR processing technique is developed to achieve a controllable precision as well as an evaluative recall performance for video cut detection. Simulation results show that this algorithm leads to very good detection performance as compared to the existing techniques. 2003 Elsevier Inc. All rights reserved.
5237024
Time-constraint boost for TV commercials detection
Commercials detection is very important for TV broadcast analysis. However, independent classification of video shots is very difficult because a considerable portion of individual commercial shots look very much like the programs. In this paper, the authors proposed a novel way to tackle this problem: to dependently treat successive video shots and improve the final classification performance by considering their temporal coherence. Following this idea, the authors discussed how to apply the majority-based windowing and minority-based merging techniques to the training and test process of statistical classifiers. As a result, a new algorithm named time-constraint boost is proposed. Simulation results show that this algorithm can improve both the training and generalization performance and lead to a promising commercials detection accuracy.
7331201
Webpage importance analysis using conditional Markov random walk
In this paper, we propose a novel method to calculate the Web page importance based on a conditional Markov random walk model. The main assumption in this model is that given the hyperlinks in a Web page, users are not really randomly clicking one of them. Instead, many factors may bias their behaviors, for example, the anchor text, the content relevance and the previous experiences when visiting the Web site that a destination page belongs to. As one of the results, the user might tend to visit those pages in high-quality Web sites with higher probability. To implement this idea, we reformulate the Web graph to be a two-layer structure, and the Web page importance is calculated by conditional random walk in this new Web graph. Experiments on the topic distillation task of TREC 2003 Web track showed that our new method can achieve about 18% improvement on mean average precision (MAP) and 16% on precision at 10 (P@10) over the PageRank algorithm.
21449211
Effective Feature Extraction for Play Detection in American Football Video
The fact that a typical broadcast can last over 3 hours for a game of 60 minutes makes video summarization of American football games most desirable. In this paper, we present several feature extraction methods for play detection in American football video. Wavelet based motion analysis is used to extract the trend component from the noisy motion vectors; a hybrid field-color model detects field area with both high accuracy and fast speed; and a prior knowledge driven line detection method uses the court information to estimate miss-detections. Based on the so-extracted features, a boosting chain is used for feature selection and decision making. Tested on large-size video data, the detection performance of our work is very promising.
1733796
Event detection from evolution of click-through data
Previous efforts on event detection from the web have focused primarily on web content and structure data ignoring the rich collection of web log data. In this paper, we propose the first approach to detect events from the click-through data, which is the log data of web search engines. The intuition behind event detection from click-through data is that such data is often event-driven and each event can be represented as a set ofquery-page pairs that are not only semantically similar but also have similar evolution pattern over time. Given the click-through data, in our proposed approach, we first segment it into a sequence of bipartite graphs based on theuser-defined time granularity. Next, the sequence of bipartite graphs is represented as a vector-based graph, which records the semantic and evolutionary relationships between queries and pages. After that, the vector-based graph is transformed into its dual graph, where each node is a query-page pair that will be used to represent real world events. Then, the problem of event detection is equivalent to the problem of clustering the dual graph of the vector-based graph. The clustering process is based on a two-phase graph cut algorithm. In the first phase, query-page pairs are clustered based on thesemantic-based similarity such that each cluster in the result corresponds to a specific topic. In the second phase, query-page pairs related to the same topic are further clustered based on the evolution pattern-based similarity such that each cluster is expected to represent a specific event under the specific topic. Experiments with real click-through data collected from a commercial web search engine show that the proposed approach produces high quality results.
18471428
Direct Energy Minimization for Super-Resolution on Nonlinear Manifolds
We address the problem of single image super-resolution by exploring the manifold properties. Given a set of low resolution image patches and their corresponding high resolution patches, we assume they respectively reside on two non-linear manifolds that have similar locally-linear structure. This manifold correlation can be realized by a three-layer Markov network that connects performing super-resolution with energy minimization. The main advantage of our approach is that by working directly with the network model, there is no need to actually construct the mappings for the underlying manifolds. To achieve such efficiency, we establish an energy minimization model for the network that directly accounts for the expected property entailed by the manifold assumption. The resulting energy function has two nice properties for super-resolution. First, the function is convex so that the optimization can be efficiently done. Second, it can be shown to be an upper bound of the reconstruction error by our algorithm. Thus, minimizing the energy function automatically guarantees a lower reconstruction error— an important characteristic for promising stable super-resolution results.
10793748
Robust face detection with multi-class boosting
With the aim to design a general learning framework for detecting faces of various poses or under different lighting conditions, we are motivated to formulate the task as a classification problem over data of multiple classes. Specifically, our approach focuses on a new multi-class boosting algorithm, called MBHboost, and its integration with a cascade structure for effectively performing face detection. There are three main advantages of using MBHboost: 1) each MBH weak learner is derived by sharing a good projection direction such that each class of data has its own decision boundary; 2) the proposed boosting algorithm is established based on an optimal criterion for multi-class classification; and 3) since MBHboost is flexible with respect to the number of classes, it turns out that it is possible to use only one single boosted cascade for the multi-class detection. All these properties give rise to a robust system to detect faces efficiently and accurately.
2588176
Local discriminant embedding and its variants
We present a new approach, called local discriminant embedding (LDE), to manifold learning and pattern classification. In our framework, the neighbor and class relations of data are used to construct the embedding for classification problems. The proposed algorithm learns the embedding for the submanifold of each class by solving an optimization problem. After being embedded into a low-dimensional subspace, data points of the same class maintain their intrinsic neighbor relations, whereas neighboring points of different classes no longer stick to one another. Via embedding, new test data are thus more reliably classified by the nearest neighbor rule, owing to the locally discriminating nature. We also describe two useful variants: two-dimensional LDE and kernel LDE. Comprehensive comparisons and extensive experiments on face recognition are included to demonstrate the effectiveness of our method.
429911
Probabilistic tracking with optimal scale and orientation selection
We describe a probabilistic framework based on a trust-region method to track rigid or non-rigid objects with automatic optimal scale and orientation selection. The approach uses a flexible probability model to represent an object by its salient features such as color or intensity gradient. Depending on the weighting scheme, features will contribute to the distribution differently according to their positions. We adopt a bivariate normal as the weighting function that only features within the induced covariance ellipse are considered. Notice that characterizing an object by a covariance ellipse makes it easier to define its orientation and scale. To perform tracking, a trust-region scheme is carried out for each image frame to detect a distribution similar to the target's accounting for the translation, scale, and orientation factors simultaneously. Unlike other work, the optimization process is executed over a continuous space. Consequently, our method is more robust and accurate as demonstrated in the experimental results.
10424202
A generalized shape-axis model for planar shapes
We describe a generalized shape-axis (SA) model for representing both open and closed planar curves. The SA model is an effective way to represent shapes by comparing their self-similarities. Given a 2D shape, whether it is closed or open, we use two different parametrizations for the curve. To study the self-similarity, the two parametrizations are matched to each other via a variational framework, where the self-similarity criterion is to be defined depending on the class of shapes and human perception factors. Useful self-similarity criteria include symmetry, parallelism and convexity, etc. A match is allowed to have discontinuities, and the optimal match can be computed by a dynamic programming algorithm in O(N/sup 4/) time, where N is the size of the shape. We use a grouping process for the shape axis to construct a unique SA-tree, however, when a planar shape is open, it is possible to derive an SA-forest. The generalized SA model provides a compact and informative way for 2D shape representation.