Line, plane and hyperplane detection in multidimensional data has many applications in computer vision and artificial intelligence. We propose Integrated Fast Hough Transform (IFHT), a highly-efficient multidimensional Hough transform algorithm based on a new mathematical model. The parameter space of IFHT can be represented with a single k-tree to support hierarchical storage and "coarse-to-fine" search strategy. IFHT essentially changes the least square data-fitting in Li's Fast Hough transform (FHT) to the total least squares data-fitting, in which observational errors across all dimensions are taken into account, thus more practical and more resistant to data noise. It has practically resolved the problem of decreased precision of FHT for target objects mapped to boundaries between accumulators in the parameter space. In addition, it enables a straightforward visualization of the parameter space which not only provides intuitive insight on the number of objects in the data, but also helps with tuning the parameters and combining multiple instances if needed. In all simulated data with different levels of noise and parameters, IFHT surpasses Li's Fast Hough transform in terms of robustness and precision significantly.

BACKGROUND: In DNA microarray experiments, discovering groups of genes that share similar transcriptional characteristics is instrumental in functional annotation, tissue classification and motif identification. However, in many situations a subset of genes only exhibits consistent pattern over a subset of conditions. Conventional clustering algorithms that deal with the entire row or column in an expression matrix would therefore fail to detect these useful patterns in the data. Recently, biclustering has been proposed to detect a subset of genes exhibiting consistent pattern over a subset of conditions. However, most existing biclustering algorithms are based on searching for sub-matrices within a data matrix by optimizing certain heuristically defined merit functions. Moreover, most of these algorithms can only detect a restricted set of bicluster patterns. RESULTS: In this paper, we present a novel geometric perspective for the biclustering problem. The biclustering process is interpreted as the detection of linear geometries in a high dimensional data space. Such a new perspective views biclusters with different patterns as hyperplanes in a high dimensional space, and allows us to handle different types of linear patterns simultaneously by matching a specific set of linear geometries. This geometric viewpoint also inspires us to propose a generic bicluster pattern, i.e. the linear coherent model that unifies the seemingly incompatible additive and multiplicative bicluster models. As a particular realization of our framework, we have implemented a Hough transform-based hyperplane detection algorithm. The experimental results on human lymphoma gene expression dataset show that our algorithm can find biologically significant subsets of genes. CONCLUSION: We have proposed a novel geometric interpretation of the biclustering problem. We have shown that many common types of bicluster are just different spatial arrangements of hyperplanes in a high dimensional data space. An implementation of the geometric framework using the Fast Hough transform for hyperplane detection can be used to discover biologically significant subsets of genes under subsets of conditions for microarray data analysis.

In a constrained total least squares algorithm (CTLS), the selection of a minimal algebraic set of linearly independent random variables to express the noise matrix /spl Delta/C is an important task. A fast algorithm is provided using the possibly dependent random variables set. We showed that it can be viewed as a combination of the CTLS method of V.Z. Mesarovic et al. (see IEEE Trans. Image Process., vol.4, p.1096-107, 1995) and the RLS method when the noise is Gaussian. Our experimental study indicates that our algorithm has better visual and objective quality, while having a much lower computation cost. Moreover, our algorithm can also handle a more general noise model.