International audience

International audience

Volume data can be represented by voxels. In many applications of computer graphics (e.g. animation, simulation) and image processing (e.g. shape registration), such voxel data require manipulations. Among the simplest manipulations, we are interested in rigid motions, namely motions that do not change the shape of voxel objects but do change their position and orientation. Such motions are well-known as isometric transformations in continuous spaces. However, when they are applied on voxel data, some important properties of geometry and topology are generally lost. In this article, we discuss this issue, and we provide a method for rigid motions of voxel objects that preserves the global convexity properties of objects, with digital topology guarantees. This method is based on the standard notion of H-convexity, and a new notion of quasi-regularity.

This paper proposes an original method for extracting the centerline of 3D objects given only partial mesh scans as input data. Its principle relies on the construction of a normal vector accumulation map build by casting digital rays from input vertices. This map is then pruned according to a confidence voting rule: confidence in a point increases if this point has maximal votes along a ray. Points with high confidence accurately delineate the centerline of the object. The resulting centerline is robust enough to allow the reconstruction of the associated graph by a simple morphological processing of the confidence and a geodesic tracking. The overall process is unsupervised and only depends on a user-chosen maximal object radius. Experiments show a good behavior on standard mesh scans. Moreover, the proposed method is not only competitive with state-of-the-art methods on perfect data, but appears to be much more reliable on imperfect or damaged data, like holes, partial scans, noise, and scans from only one direction.

Segmentation of defects on the tree log surface remains a challenge due to the unclear seperation between the foreground and the background and the high variability of the tree surface. Even if some first works exist to process specific tree species, a generic method robust to various species is missing. We propose a new approach for segmenting defects on log surface based on the tabular object analysis. We firstly compute the log centerline by surface normal accumulation and then threshold the point cloud by the the difference between the distance to the centerline and the reference distance estimated from a patch of neighbors. The performance of the proposed approach was experimented and compared on ten logs recovered from different species. The results showed that our approach outperformed other method based on cylinder detection and was robust to several tree species. The results can be reproduced and compared on an online demonstration.

A new method to extract dashed lines in technical document is proposed in this paper by combining force histogram and discrete lines. The aim is to study the spatial location of couples of connected components using force histogram and to refine the recognition by considering surrounding discrete lines. This new model is fast and it allows a good extraction of occulted patterns in presence of noise. Efficient common methods require several thresholds to process with technical documents. The proposed method requires only few thresholds which can be automatically set from data.

A multi-scale approach is proposed for polygonal representation of a digital curve by using the notion of blurred segment and a split-and-merge strategy. Its main idea is to decompose the curve into meaningful parts that are represented by detected dominant points at the appropriate scale. The method uses no threshold and can automatically decompose the curve into meaningful parts.

We propose a new circularity measure inspired from Arkin, Latecki tools of shape matching that is constructed in a tangent space. We then introduce a linear algorithm that uses this measure for circularity measuring. This method can also be regarded as a method for circular object recognition. Experimental results show the robustness of this simple method.

A new and fast method for dominant point detection and polygonal representation of a discrete curve is proposed. Starting from results of discrete geometry, the notion of maximal blurred segment of width v has been proposed, well adapted to possibly noisy and/or not connected curves. For a given width, the dominant points of a curve C are deduced from the sequence of maximal blurred segments of C in O(n log2n) time. Comparisons with other methods of the literature prove the efficacity of our approach.

BACKGROUND: Many programs have been developed to identify transcription factor binding sites. However, most of them are not able to infer two-word motifs with variable spacer lengths. This case is encountered for RNA polymerase Sigma (sigma) Factor Binding Sites (SFBSs) usually composed of two boxes, called -35 and -10 in reference to the transcription initiation point. Our goal is to design an algorithm detecting SFBS by using combinational and statistical constraints deduced from biological observations. RESULTS: We describe a new approach to identify SFBSs by comparing two related bacterial genomes. The method, named SIGffRid (SIGma Factor binding sites Finder using R'MES to select Input Data), performs a simultaneous analysis of pairs of promoter regions of orthologous genes. SIGffRid uses a prior identification of over-represented patterns in whole genomes as selection criteria for potential -35 and -10 boxes. These patterns are then grouped using pairs of short seeds (of which one is possibly gapped), allowing a variable-length spacer between them. Next, the motifs are extended guided by statistical considerations, a feature that ensures a selection of motifs with statistically relevant properties. We applied our method to the pair of related bacterial genomes of Streptomyces coelicolor and Streptomyces avermitilis. Cross-check with the well-defined SFBSs of the SigR regulon in S. coelicolor is detailed, validating the algorithm. SFBSs for HrdB and BldN were also found; and the results suggested some new targets for these sigma factors. In addition, consensus motifs for BldD and new SFBSs binding sites were defined, overlapping previously proposed consensuses. Relevant tests were carried out also on bacteria with moderate GC content (i.e. Escherichia coli/Salmonella typhimurium and Bacillus subtilis/Bacillus licheniformis pairs). Motifs of house-keeping sigma factors were found as well as other SFBSs such as that of SigW in Bacillus strains. CONCLUSION: We demonstrate that our approach combining statistical and biological criteria was successful to predict SFBSs. The method versatility authorizes the recognition of other kinds of two-box regulatory sites.

A new very efficient linear algorithm for the segmentation of 8-connected digital curves is given. The simplicity comes from a definition of digital lines using a linear double diophantine inequality. A complete Pascal source code is given.