کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952475 1442038 2016 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Indexing and querying color sets of images
ترجمه فارسی عنوان
نمایه سازی و پرس و جو مجموعه رنگ از تصاویر
کلمات کلیدی
الگوریتم های تصویر الگوریتم های متن، اثر انگشت، مجموعه ای از شخصیت ها مجموعه ای از رنگ، مکانهای حداکثر
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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(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(nmlog⁡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(nmlog⁡n+|F|) while the query time becomes O(|f|+log⁡log⁡n). We eventually consider the special case of squared regions (squares).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 647, 27 September 2016, Pages 74-84
نویسندگان
, , ,