Can I read R\*-Histograms: efficient representation of spatial relations between objects of arbitrary topology on EtoBox?

R\*-Histograms: efficient representation of spatial relations between objects of arbitrary topology by Yuhang Wang; Fillia Makedon; Amit Chakrabarti is a scholarly article available to read on EtoBox.

What is R\*-Histograms: efficient representation of spatial relations between objects of arbitrary topology about?

Representation of relative spatial relations between objects is often required in many multimedia database applications because spatial relations between objects in an image convey important information about the image. Quantitative representation of spatial relations taking into account shape, size, orientation and distance is often required. The R-Histogram is such a quantitative representation of spatial relations between two objects. However, this method only considers pixels on the object boundary, assuming that the objects are homeomorphic to a 2-ball. For objects with more complicated topology, we propose in this paper the R\*-Histogram, a new extension to the R-Histogram. The R\*-Histogram generalizes the R-Histogram by taking into account all the pixels in the objects. We also introduce an efficient O(kN logN ) time algorithm to compute the R\*-Histogram, which is asymptotically faster than the original O(N 2 ) time algorithm for the R-Histogram even when k = O(n). Here, N = n 2 denotes the number of pixels in the processed n × n image and k is the number of different directions considered. The effectiveness of the R\*-Histogram is evaluated empirically with a Query By Exa

Author

Yuhang Wang; Fillia Makedon; Amit Chakrabarti

Publisher

ACM

Published

2004

Language

EN