Indexing and querying color sets of images
| dc.contributor.author | Belazzougui, Djamal | |
| dc.contributor.author | Kolpakov, Roman | |
| dc.contributor.author | Raffinot, Mathieu | |
| dc.date.accessioned | 2016-10-02T14:35:05Z | |
| dc.date.available | 2016-10-02T14:35:05Z | |
| dc.date.issued | 2016-09-27 | |
| dc.description.abstract | We aim to study the set of color sets of continuous regions of an image given as a matrix of m rows over n ≥ m columns where each element in the matrix is an integer from [1,σ] named a 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 F. A rectangle is 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 L. We first explain how to determine all the |L| maximal locations with their fingerprints in expected time O(n⋅m^2⋅σ) using a Monte Carlo algorithm (with polynomially small probability of error) or within deterministic O(n⋅m^2⋅σ⋅log(|L|/(n⋅m^2)+2)) time. We then show how to build a data structure which occupies O(n⋅m⋅log n+|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|+log log n+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(n⋅m⋅log n+|F|) while the query time becomes O(|f|+log log n). We eventually consider the special case of squared regions (squares). | fr_FR |
| dc.identifier.issn | 0304-3975 | fr_FR |
| dc.identifier.uri | http://dl.cerist.dz/handle/CERIST/831 | |
| dc.publisher | Springer Varlag | fr_FR |
| dc.relation.ispartofseries | Theoretical Computer Science;647 | |
| dc.relation.pages | 74-84 | fr_FR |
| dc.structure | Analyse et modélisation de systèmes pour l'aide à la décision | fr_FR |
| dc.subject | Image algorithms | fr_FR |
| dc.subject | Text algorithms | fr_FR |
| dc.subject | Fingerprint | fr_FR |
| dc.subject | Set of characters | fr_FR |
| dc.subject | Set of colors | fr_FR |
| dc.subject | Maximal locations | fr_FR |
| dc.title | Indexing and querying color sets of images | fr_FR |
| dc.type | Article |