Résumé: We aim to study the set of color sets of continuous regions of an image given as a matrix of mrows over n ≥mcolumns 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 maximalif 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(nm2σ)using a Monte Carlo algorithm (with polynomially small probability of error) or within deterministic O(nm2σlog(|L|nm2+2))time. We then show how to build a data structure which occupies O(nm logn +|L|)space such that a query which asks for all the maximal locations with a given fingerprint fcan be answered in time O(|f| +loglogn +k), where kis the number of maximal locations with fingerprintf. If the query asks only for the presence of the fingerprint, then the space usage becomes O(nm logn +|F|)while the query time becomes O(|f| +loglogn). We eventually consider the special case of squared regions (squares).

Langue: Anglais
Index décimal 621 .Physique appliquée (électrotechnique, génie civil, génie mécanique, ingénierie appliquée, principes physiques en ingénierie)
Thème Informatique

Mots clés:
Image algorithms
Text algorithms
Fingerprint
Set of characters
Set of colors
Maximal locations