A variant of -nearest neighbors search with cyclically permuted query points for rotation-invariant image processing
详细信息 查看全文
- 作者：Leslie R. Foulds lesfoulds@inf.ufg.br" class="auth_mail" title="E-mail the corresponding author ; Jorge P. de Morais Neto jorgepeixotomorais@gmail.com" class="auth_mail" title="E-mail the corresponding author ; Humberto J. Longo longo@inf.ufg.br" class="auth_mail" title="E-mail the corresponding author ; Hugo A.D. do Nascimento ; hadn@inf.ufg.br" class="auth_mail" title="E-mail the corresponding author ; Wellington S. Martins wellington@inf.ufg.br" class="auth_mail" title="E-mail the corresponding author
- 关键词：kk-nearest neighbors ; Circulant matrix ; Fast Fourier transform ; Parallel computing ; Image processing ; Rotation-invariance
- 刊名：Discrete Applied Mathematics
- 出版年：2015
- 出版时间：31 December 2015
- 年：2015
- 卷：197
- 期：Complete
- 页码：123-144
- 全文大小：597 K
文摘
The well-known k-nearest neighbors problem (
) involves building a data structure that reports the k closest training points to each of a given set of query points, with all points being in a given metric space S. The problem discussed here is an important operation in rotation-invariant image processing. It consists of a nontrivial variant of : given a set of training points X and a set of query points Y find, for each query point y∈Y, the k nearest training points to y, where the notion of distance is given by a pseudometric of S defined over cyclic permutations of y and the elements of X. The multiplicity of the query point permutations makes serial brute force search too costly for instances of practical size. We present a transformation that enables any instance of the variant to be solved as a problem. Although this enables the application of any algorithm, the transformation is too time costly to be practical for instances of practical dimensions. For this reason, we present a condensation algorithm for the efficient elimination of unfavorable training points (that cannot be among the k closest neighbors of y) and an effective parallel programming approach based on the discrete Fourier transform. The significant speedup gained over brute force search on practical datasets is reported. We also provide the mathematical basis of a conjecture that, if true, would enable the speedup to be significantly improved. The application of the approach to classification by support vector machines and k-means clustering is also discussed.
) involves building a data structure that reports the k closest training points to each of a given set of query points, with all points being in a given metric space S. The problem discussed here is an important operation in rotation-invariant image processing. It consists of a nontrivial variant of : given a set of training points X and a set of query points Y find, for each query point y∈Y, the k nearest training points to y, where the notion of distance is given by a pseudometric of S defined over cyclic permutations of y and the elements of X. The multiplicity of the query point permutations makes serial brute force search too costly for instances of practical size. We present a transformation that enables any instance of the variant to be solved as a problem. Although this enables the application of any algorithm, the transformation is too time costly to be practical for instances of practical dimensions. For this reason, we present a condensation algorithm for the efficient elimination of unfavorable training points (that cannot be among the k closest neighbors of y) and an effective parallel programming approach based on the discrete Fourier transform. The significant speedup gained over brute force search on practical datasets is reported. We also provide the mathematical basis of a conjecture that, if true, would enable the speedup to be significantly improved. The application of the approach to classification by support vector machines and k-means clustering is also discussed.