Indexing and querying color sets of images

DOI10.1016/J.TCS.2016.07.041MaRDI QIDQ306719zbMATH OpenOpenAlexFDO

Authors Djamal Belazzougui, Mathieu Raffinot, Roman Kolpakov

Publication date 1 September 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.07847

zbMATH Keywords

fingerprintimage algorithmsmaximal locationsset of charactersset of colorstext algorithms

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Computing methodologies for image processing (68U10)

Abstract: We aim to study the set of color sets of continuous regions of an image given as a matrix of $m$ rows over $ngeqm$ columns where each element in the matrix is an integer from $[1,sigma]$ named a {em color}. The set of distinct colors in a region is called fingerprint. We aim to compute, index and query the fingerprints of all rectangular regions named rectangles. The set of all such fingerprints is denoted by $calF$. A rectangle is {em maximal} if it is not contained in a greater rectangle with the same fingerprint. The set of all locations of maximal rectangles is denoted by $mathcalL.$ We first explain how to determine all the $|mathcalL|$ maximal locations with their fingerprints in expected time $O(n{m}^{2}sigma)$ using a Monte Carlo algorithm (with polynomially small probability of error) or within deterministic $O(n{m}^{2}sigmalog(frac|mathcalL|n{m}^2+2))$ time. We then show how to build a data structure which occupies $O(nmlogn+mathcal|L|)$ space such that a query which asks for all the maximal locations with a given fingerprint $f$ can be answered in time $O(|f|+loglogn+k)$, where $k$ is the number of maximal locations with fingerprint $f$. If the query asks only for the presence of the fingerprint, then the space usage becomes $O(nmlogn+|calF|)$ while the query time becomes $O(|f|+loglogn)$. We eventually consider the special case of squared regions (squares).

Recommendations

• Indexed geometric jumbled pattern matching
• An efficient color representation for image retrieval
• scientific article; zbMATH DE number 6381708
• Significant-presence range queries in categorical data.
• Efficient Colored Orthogonal Range Counting

Cites work

• A Faster Query Algorithm for the Text Fingerprinting Problem
• A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
• Character sets of strings
• Efficient randomized pattern-matching algorithms
• Efficient text fingerprinting via Parikh mapping
• Faster query algorithms for the text fingerprinting problem
• scientific article; zbMATH DE number 3551946 (Why is no real title available?)
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• Inplace 2D matching in compressed images
• Near-optimal range reporting structures for categorical data
• New algorithms for text fingerprinting
• Two-dimensional dictionary matching
• Various improvements to text fingerprinting

Cited in

(3)

• Indexing and querying character sets in one- and two-dimensional words
• scientific article; zbMATH DE number 5990406 (Why is no real title available?)
• Spatial Color Distribution Based Indexing and Retrieval Scheme

This page was built for publication: Indexing and querying color sets of images

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306719)