27633879
A more efficient branch and bound algorithm for feature selection
Abstract An algorithm is presented to be able to select the globally optimal subset of d features from a larger D -feature set. This is a fundamental problem in statistical pattern recognition and combinatorial optimization. Exhaustive enumeration is computationally unfeasible in most applications. This algorithm dynamically searches for the globally optimal solution on a minimum solution tree which is a subtree of the solution tree used in the traditional branch and bound algorithm. The new algorithm is compared theoretically with the branch and bound algorithm. The analysis and the experimental results show that it is more efficient than the traditional algorithm.
34534588
Lane boundary detection using a multiresolution Hough transform
Lane boundary detection is the problem of estimating the geometric structure of the lane boundaries of a road based on the images grabbed by a camera on board a vehicle. We use the Hough transform to detect lane boundaries with a parabolic model under a variety of road pavement types, lane structures and weather conditions. In the three-dimensional Hough space, a parabolic curve is represented as a straight line. To simplify the computation, the parametric space can be divided into (i) a two-dimensional space measured by the parameters which are shared by all the lane edges, and (ii) a one-dimensional space of the parameter which makes a distinction among different edges in an image. A multiresolution strategy is used to improve both the speed and accuracy of the Hough transform. Experimental results show that the proposed method is relatively less prone to the image noise and is computationally tractable.
41609314
A robust and fast skew detection algorithm for generic documents
Abstract A robust and fast skew detection algorithm based on hierarchical Hough transform is proposed. It is capable of detecting the skew angle for various document images, including technical articles, postal labels, handwritten text, forms, drawings and bar codes. The algorithm is robust even when black margins introduced by photocopying are present in the image and when the document is scanned at a low resolution of 50 dpi. The algorithm consists of two steps. In the first step we quickly extract the centroids of connected components using a graph data structure. Then, a hierarchical Hough transform (at two different angular resolutions) is applied to the selected centroids. The skew angle corresponds to the location of the highest peak in the Hough space. The performance of the algorithm is shown on a number of document images collected from various application domains. The algorithm is not very sensitive to algorithmic parameters. For an A4 size document image scanned at 50 dpi (typically 413 × 575 pixels), our algorithm is able to detect the skew angle with an accuracy of 0.1° in 0.4s of CPU time on a SunSparc 20 workstation.
39489918
An economical contour extraction algorithm for understanding large-size engineering drawings
An algorithm is described which produces the extraction of an object's contours in a binary image while storing only two raster lines at a time during processing. The major data structure used is a block adjacency graph which occupies much less space (typically one hundredth) than the original image. Because this algorithm has very low costs of memory space and processing time, it is a powerful tool for processing large-size engineering drawings. Applications of the method to the recognition of some loop-structure logical symbols are described.<<ETX>>
34993677
Automatic text location in images and video frames
Abstract Textual data is very important in a number of applications such as image database indexing and document understanding. The goal of automatic text location without character recognition capabilities is to extract image regions that contain only text. These regions can then be either fed to an optical character recognition module or highlighted for a user. Text location is a very difficult problem because the characters in text can vary in font, size, spacing, alignment, orientation, color and texture. Further, characters are often embedded in a complex background in the image. We propose a new text location algorithm that is suitable in a number of applications, including conversion of newspaper advertisements from paper documents to their electronic versions, World Wide Web search, color image indexing and video indexing. In many of these applications, it is not necessary to extract all the text, so we emphasize on extracting important text with large size and high contrast. Our algorithm is very fast and has been shown to be successful in extracting important text in a large number of test images.
46138594
Document Representation and Its Application to Page Decomposition
Transforming a paper document to its electronic version in a form suitable for efficient storage, retrieval, and interpretation continues to be a challenging problem. An efficient representation scheme for document images is necessary to solve this problem. Document representation involves techniques of thresholding, skew detection, geometric layout analysis, and logical layout analysis. The derived representation can then be used in document storage and retrieval. Page segmentation is an important stage in representing document images obtained by scanning journal pages. The performance of a document understanding system greatly depends on the correctness of page segmentation and labeling of different regions such as text, tables, images, drawings, and rulers. We use the traditional bottom-up approach based on the connected component extraction to efficiently implement page segmentation and region identification. A new document model which preserves top-down generation information is proposed based on which a document is logically represented for interactive editing, storage, retrieval, transfer, and logical analysis. Our algorithm has a high accuracy and takes approximately 1.4 seconds on a SGI Indy workstation for model creation, including orientation estimation, segmentation, and labeling (text, table, image, drawing, and ruler) for a 2550/spl times/3300 image of a typical journal page scanned at 300 dpi. This method is applicable to documents from various technical journals and can accommodate moderate amounts of skew and noise.
828878
Image denoising via lossy compression and wavelet thresholding
Some past work has proposed to use lossy compression to remove noise, based on the rationale that a reasonable compression method retains the dominant signal features more than the randomness of the noise. Building on this theme, we explain why compression (via coefficient quantization) is appropriate for filtering noise from signal by making the connection that quantization of transform coefficients approximates the operation of wavelet thresholding for denoising. That is, denoising is mainly due to the zero-zone and that the full precision of the thresholded coefficients is of secondary importance. The method of quantization is facilitated by a criterion similar to Rissanen's minimum description length principle. An important issue is the threshold value of the zero-zone (and of wavelet thresholding). For a natural image, it has been observed that its subband coefficients can be well modeled by a Laplacian distribution. With this assumption, we derive a threshold which is easy to compute and is intuitive. Experiments show that the proposed threshold performs close to optimal thresholding.
6486491
A fast lightweight approach to origin-destination IP traffic estimation using partial measurements
In this paper, a novel approach is proposed for estimating traffic matrices. Our method, called PamTram for PArtial Measurement of TRAffic Matrices, couples lightweight origin-destination (OD) flow measurements along with a computationally lightweight algorithm for producing OD estimates. The first key aspect of our method is to actively select a small number of informative OD flows to measure in each estimation interval. To avoid the heavy computation of optimal selection, we use intuition from game theory to develop randomized selection rules, with the goals of reducing errors and adapting to traffic changes. We show that it is sufficient to measure only one flow per measurement period to drastically reduce errors-thus rendering our method lightweight in terms of measurement overhead. The second key aspect is an explanation and proof that an Iterative Proportional Fitting algorithm approximates traffic matrix estimates when the goal is a minimum mean-squared error; this makes our method lightweight in terms of computation overhead. A one-step error bound is provided for PamTram that bounds the average error for the worst scenario. We validate our method using data from Sprint's European Tier-1 IP backbone network and demonstrate its consistent improvement over previous methods.
1687904
PGGA: A predictable and grouped genetic algorithm for job scheduling
This paper presents a predictable and grouped genetic algorithm (PGGA) for job scheduling. The novelty of the PGGA is two-fold: (1) a job workload estimation algorithm is designed to estimate a job workload based on its historical execution records and (2) the divisible load theory (DLT) is employed to predict an optimal fitness value by which the PGGA speeds up the convergence process in searching a large scheduling space. Comparison with traditional scheduling methods, such as first-come-first-serve (FCFS) and random scheduling, heuristics, such as a typical genetic algorithm, Min-Min and Max-Min indicates that the PGGA is more effective and efficient in finding optimal scheduling solutions.
18904561
A New Method of Realizing Fingerprint Authentication on Smartcard
A new method of realizing fingerprint authentication on Smartcard has been presented. Based on SOC, this method puts the pre-processing algorithm, which is the most time-wasting process, out of card. It not only decreases the complexity of realizing fingerprint authentication on Smartcard, but also ensures the security of fingerprint information due to the original fingerprint image has been transformed with cryptography algorithm of this paper. The experimental results demonstrate that this method can shorten the time of fingerprint verification effectively.
652118
Stagewise Lasso
Many statistical machine learning algorithms minimize either an empirical loss function as in AdaBoost, or a penalized empirical loss as in Lasso or SVM. A single regularization tuning parameter controls the trade-off between fidelity to the data and generalizability, or equivalently between bias and variance. When this tuning parameter changes, a regularization "path" of solutions to the minimization problem is generated, and the whole path is needed to select a tuning parameter to optimize the prediction or interpretation performance. Algorithms such as homotopy-Lasso or LARS-Lasso and Forward Stagewise Fitting (FSF) (aka e-Boosting) are of great interest because of their resulted sparse models for interpretation in addition to prediction. 
 
In this paper, we propose the BLasso algorithm that ties the FSF (e-Boosting) algorithm with the Lasso method that minimizes the L1 penalized L2 loss. BLasso is derived as a coordinate descent method with a fixed stepsize applied to the general Lasso loss function (L1 penalized convex loss). It consists of both a forward step and a backward step. The forward step is similar to e-Boosting or FSF, but the backward step is new and revises the FSF (or e-Boosting) path to approximate the Lasso path. In the cases of a finite number of base learners and a bounded Hessian of the loss function, the BLasso path is shown to converge to the Lasso path when the stepsize goes to zero. For cases with a larger number of base learners than the sample size and when the true model is sparse, our simulations indicate that the BLasso model estimates are sparser than those from FSF with comparable or slightly better prediction performance, and that the the discrete stepsize of BLasso and FSF has an additional regularization effect in terms of prediction and sparsity. Moreover, we introduce the Generalized BLasso algorithm to minimize a general convex loss penalized by a general convex function. Since the (Generalized) BLasso relies only on differences not derivatives, we conclude that it provides a class of simple and easy-to-implement algorithms for tracing the regularization or solution paths of penalized minimization problems.