Catálogo de publicaciones - libros

Partitioning is a fundamental problem in diverse fields of study such as knowledge discovery, data mining, image segmentation and grouping. The min-cut bipartitioning problem is a fundamental graph partitioning problem and is NP-Complete. In this paper, we present an effective multi-level algorithm based on simulated annealing for bisecting graph. The success of our algorithm relies on exploiting both the simulated annealing procedure and the concept of the graph core. Our experimental evaluations on 18 different graphs show that our algorithm produces encouraging solutions compared with those produced by MeTiS that is a state-of-the-art partitioner in the literature.

Szemerédi’s regularity lemma is a deep result from extremal graph theory which states that every graph can be well-approximated by the union of a constant number of random-like bipartite graphs, called regular pairs. Although the original proof was non-constructive, efficient (i.e., polynomial-time) algorithms have been developed to determine regular partitions for arbitrary graphs. This paper reports a first attempt at applying Szemerédi’s result to computer vision and pattern recognition problems. Motivated by a powerful auxiliary result which, given a partitioned graph, allows one to construct a small reduced graph which inherits many properties of the original one, we develop a two-step pairwise clustering strategy in an attempt to reduce computational costs while preserving satisfactory classification accuracy. Specifically, Szemerédi’s partitioning process is used as a preclustering step to substantially reduce the size of the input graph in a way which takes advantage of the strong notion of edge-density regularity. Clustering is then performed on the reduced graph using standard algorithms and the solutions obtained are then mapped back into the original graph to create the final groups. Experimental results conducted on standard benchmark datasets from the UCI machine learning repository as well as on image segmentation tasks confirm the effectiveness of the proposed approach.

In this work we show, that for each permuted submodular MinSum problem (Energy Minimization Task) the corresponding submodular MinSum problem can be found in polynomial time. It follows, that permuted submodular MinSum problems are exactly solvable by transforming them into corresponding submodular tasks followed by applying standart approaches (e.g. using MinCut-MaxFlow based techniques).

Meaningful notions of distance between planar shapes typically involve the computation of a correspondence between points on one shape and points on the other. To determine an optimal correspondence is a computationally challenging combinatorial problem. Traditionally it has been formulated as a shortest path problem which can be solved efficiently by Dynamic Time Warping.

In this paper, we show that shape matching can be cast as a problem of finding a minimum cut through a graph which can be solved efficiently by computing the maximum network flow. In particular, we show the equivalence of the minimum cut formulation and the shortest path formulation, i.e. we show that there exists a one-to-one correspondence of a shortest path and a graph cut and that the length of the path is identical to the cost of the cut. In addition, we provide and analyze some examples for which the proposed algorithm is faster resp. slower than the shortest path method.

Classic mosaic is one of the oldest and most durable art forms. There has been a growing interest in simulating classic mosaics from digital images recently. To be visually pleasing, a mosaic should satisfy the following constraints: tiles should be non-overlapping, tiles should align to the perceptually important edges in the underlying digital image, and orientation of the neighbouring tiles should vary smoothly across the mosaic. Most of the existing approaches operate in two steps: first they generate tile orientation field and then pack the tiles according to this field. However, previous methods perform these two steps based on heuristics or local optimisation which, in some cases, is not guaranteed to converge. Some other major disadvantages of previous approaches are: (i) either substantial user interaction or hard decision making such as edge detection is required before mosaicing starts (ii) the number of tiles per mosaic must be fixed beforehand, which may cause either undesired overlap or gap space between the tiles. In this work, we propose a novel approach by formulating the mosaic simulating problem in a global energy optimisation framework. Our algorithm also follows the two-step approach, but each step is performed with global optimisation. For the first step, we observe that the tile orientation constraints can be naturally formulated in an energy function that can be optimised with the -expansion algorithm. For the second step of tightly packing the tiles, we develop a novel graph cuts based algorithm. Our approach does not require user interaction, explicit edge detection, or fixing the number of tiles, while producing results that are visually pleasing.

In this paper, we propose a novel approach to graph regularisation based on energy minimisation. Our method hinges in the use of a Ginzburg-Landau functional whose extremum is achieved efficiently by a gradient descend optimisation process. As a result of the treatment given in this paper to the regularisation problem, constraints can be enforced in a straightforward manner. This provides a means to solve a number of problems in computer vision and pattern recognition. To illustrate the general nature of our graph regularisation algorithm, we show results on two application vehicles, photometric stereo and image segmentation. Our experimental results demonstrate the efficacy of our method for both applications under study.

The pupil localization algorithm is very important for a face recognition system. Traditional pupil localization algorithms are easy to be affected by uneven illuminations and accessories. Aiming at those limitations, a novel pupil localization algorithm is proposed in this paper. The algorithm firstly implements face image tilt adjustment and extracts eye region through the horizontal intensity gradient integral projection and Gabor filtering. Then in order to increase the eye detection accuracy, PCA is applied to select Gabor filter, and the projection enhancement algorithm is presented. At last the Negative Radial Symmetry is presented to locate the pupil position precisely in eye windows. Experimental results show that the method can locate the pupil position accurately, and demonstrate robustness to uneven lighting, noise, accessories and pose variations.

Document decomposition is a basic but crucial step for many document related applications. This paper proposes a novel approach to decompose document images into zones. It first generates overlapping zone hypotheses based on generic visual features. Then, each candidate zone is evaluated quantitatively by a learned generative zone model. We infer the optimal set of non-overlapping zones that covers a given document image by a heuristic search algorithm. The experimental results demonstrate that the proposed method is very robust to document structure variation and noise.

In this paper we propose and develop a new algorithm, Corrected Inverse-Denoising filtER (CIDER) to restore blurred and noisy images. The approach is motivated by a recent algorithm ForWaRD, which uses a regularized inverse filter followed by a wavelet denoising scheme. In ForWaRD, the restored image obtained by the regularized inverse filter is a biased estimate of the original image. In CIDER, the correction term is added to this restored image such that the resulting one is an unbiased estimator. Similarly, the wavelet denoising scheme can be applied to suppress the residual noise. Experimental results show that the performance of CIDER is better than other existing methods in our comparison study.

One new and efficient skew detection algorithm is proposed for form documents according to the feature that the horizontal line has the same skew with the form. This algorithm includes the following steps: Firstly, all horizontal connected regions, including horizontal straight-lines, are extracted from the form document by directional region growing method presented in this paper; Secondly, the optimal line is selected from all horizontal connected regions based on the elongate of connected region; Thirdly, all the pixels belonging to the optimal line are considered to calculate the line parameters with linear least-square theory. The skew angle of the optimal line is just the form skew angle. One elongate function is defined in this paper which described the elongate feature correctly for the band-like connected region. The experiment results show that the form skew angle can be detected accurately, and this skew detection algorithm is fast and robust.