Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 4 декабря 2016 г.
Аннотация: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(nm^2σ) using a Monte Carlo algorithm (with polynomially small probability of error) or within deterministic View the MathML source time. We then show how to build a data structure which occupies O(nmlogn+|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+|F|) while the query time becomes O(|f|+loglogn). We eventually consider the special case of squared regions (squares).