Устройство поиска дубликатов изображений

Изобретение относится к способам обработки цифровых изображений. Техническим результатом является обеспечение возможности сопоставления дескрипторов применительно к задаче поиска дубликатов изображений. Предложено устройство поиска дубликатов изображений. Устройство содержит блоки предобработки первого и второго изображений, блоки регистрации первого и второго изображений, блоки преобразования первого и второго изображений в цветовое пространство YIQ, блоки выделения синфазной составляющей первого и второго изображений, блоки формирования изображений в результате вращения первого и второго изображений, блоки формирования изображений при изменении угла наклона первого и второго изображений, блоки хранения моделированных изображений для первого и второго изображений, блок применения метода SIFT, блок вычисления количества одинаковых дескрипторов, блок хранения найденной пары дубликатов. 5 ил.

 

Изобретение относится к способам обработки цифровых изображений и может быть использовано в системах компьютерного зрения для идентификации и регистрации объектов на изображении, мультимедийных приложениях, работающих с визуальными данными.

Упрощенная математическая модель изображения представляет собой модель в цветовом пространстве RGB в виде массива S_i,j,k, где $$\overline{i=1,I},j=\overline{1,J}$$ - столбцы и строки изображения, $$k=\overline{1,3}$$ - цветовой канал. При использовании изображения в градациях серого, каждая точка представлена уровнем яркости в диапазоне от 0 (черный) до 255 (белый), с промежуточными значениями, представляющими различные уровни серого. Соответственно такое изображение обозначим как S_i,j.

Основная решаемая задача - сопоставление дескрипторов применительно к задаче поиска дубликатов изображений.

Поиск точечных соответствий между изображениями одного и того же объекта имеет большое значение для идентификации сцены, реконструкции объектов трехмерного пространства, поиска изображений, распознавания объектов.

Методы поиска соответствий на изображениях основаны на построении дескрипторов. Дескриптор - вектор признаков, который рассчитывается для каждой точечной особенности изображения и описывающий структуру ее окрестности. Как правило, эти вектора формируются на основе набора значений первых и вторых производных изображения в точке.

Дескрипторы могут быть представлены в виде небольших инвариантных участков, точек изображения, особых областей. При выборе способа представления областей возникает следующая альтернатива: область можно представить ее внешними характеристиками (т.е. границей) или внутренними характеристиками (совокупность элементов составляющих эту область). Внешнее представление обычно выбирается в тех случаях, когда основное внимание обращено на характеристики формы области. Внутреннее представление выбирается, если интерес представляют свойства самой области, например цвет или текстура. Иногда используются оба способа представления одновременно. Данные, представленные в форме множества пикселей, расположенных вдоль границы или внутри области, используются для получения дескрипторов, которые принимают значения в пространстве признаков. Если на таком пространстве задать меру, то можно сравнивать изображения друг с другом, вычисляя расстояние между соответствующими векторами признаков.

Для того чтобы удовлетворять задаче сопоставления изображений и их точечных особенностей, дескрипторы должны быть специфичны и выбраны таким образом, чтобы с высокой вероятностью дескрипторы разных изображений (но, принадлежащие одинаковым точечным особенностям) были правильно согласованы.

Дескрипторы должны быть:

- специфичны (отличать разные точки);

- локальны (зависеть только от небольшой окрестности);

- инвариантны (поворот, растяжение, сжатие, монотонное изменение яркости, аффинные и проективные преобразования);

- просты в вычислении.

Общая проблема методов сопоставления дескрипторов заключается в распознавании объекта на фотографиях, сделанных с разного ракурса, под разными углами обзора, в разном масштабе, при разном освещении. Это приводит к тому, что один и тот же объект в зависимости от условий съемки будет характеризоваться различными векторами-признаками. Следовательно, методы распознания должно быть инвариантны относительно таких изменений.

Анализ существующих литературных источников позволяет выделить наиболее популярные методы. Главной проблемой всех методов сопоставления дескрипторов на изображениях является нахождение аффинных инвариантных локальных особенностей. Практически ни один из рассмотренных методов не удовлетворяет данному требованию. Методы Hessian-Affine и Harris-Affine - не устойчивы к изменению угла обзора и масштабу, поэтому не реализуют в должной мере аффинную инвариантность. Метод MSER - не полностью инвариантен масштабу: не справляется с резкими изменениями уровня геометрической размытости. Постоянно расширяется число различных вариантов метода SIFT, таких как PCA-SIFT, GLOH, SURF. Они широко применяются в области распознания, детектирования, регистрации движения, но не решают проблемы аффинной инвариантности.

Известен способ распознавания объектов на изображении [Патент RU 2438174 C1, МПК G06K 9/68]. Изобретение относится к способам распознавания объектов в системах машинного зрения, телевизионных системах наблюдения, информационно-управляющих системах робототехнических комплексов.

Основная техническая задача состоит в создании способа, позволяющего повысить точность распознавания за счет повышения стабильности работы детекторов ключевых областей на изображении и увеличения количества инвариантных характеристик данных детекторов. На первом этапе входное изображение сворачивается с заданной функцией Грина. Далее полученные свертки вычитают друг из друга для получения конечно-разностной аппроксимации первой производной свертки входного изображения с фильтром, при поиске локального экстремума данной свертки приравнивают к нулю соответствующие первые производные. На следующем этапе находят все локальные экстремумы и проводят адаптивную пороговую фильтрацию для отсечения незначительных особенностей, при этом выделенные точки служат центрами окрестностей, для которых строят произвольные дескрипторы.

Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:

- построение дескрипторов изображения.

Недостатками известного способа и устройства его реализующего являются:

- низкая точность определения локальных дескрипторов. Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:

- использование способа свертки с функцией Грина не позволяет детектировать различные типы текстур.

Известен способ и устройство для обнаружения объекта на изображении [Патент US №6711293, МПК G06K 9/68]. Изобретение относится к способам распознавания объектов в системах машинного зрения.

Основная техническая задача состоит в распознавании объектов на изображении с использованием инвариантной функции масштаба. На первом этапе вычисляются разности изображений: выполняется свертка изображения с функцией Гаусса, далее еще раз вычисляется свертка свернутого изображения с функцией Гаусса для построения разностного изображения и из входного изображения вычитают разностное изображение. На втором этапе находят локальные экстремумы значений пикселей. На третьем этапе выделяют области вокруг точек экстремума.

На четвертом этапе области разбиваются на подобласти и на пятом этапе производят множество компонент - дескрипторов подобластей.

Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:

- нахождение и сопоставление дескрипторов;

- инвариантность дескрипторов к изменению масштаба.

Недостатками известного способа и устройства его реализующего являются:

- невысокая точность построения дескрипторов.

Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:

- функция Гаусса обладает ограниченным набором инвариантных характеристик, характеризующих особенности изображения, описываемые векторами-признаками, и, тем самым, данные вектора являются менее информативными.

Известен способ компьютерного распознавания объектов [Патент RU №2234127 C2, МПК G06K 9/68]. Изобретение относится к области автоматики и вычислительной техники, а именно к системам искусственного интеллекта.

Основная техническая задача заключается в увеличении скорости распознавания объектов, вводимых в компьютер. На первом этапе происходит предварительное приведение изображения объекта, вводимого в компьютер, к нормальному, стандартному для данного способа виду - изменению масштаба, поворот в требуемое положение, центрирование, вписание в прямоугольник требуемого размера, преобразование изображения объекта в изображение, выполненное в градациях - различных степенях яркости - одного цвета. Затем на него последовательно, поочередно накладываются изображения хранящихся в памяти компьютера шаблонов. Программа распознавания объектов пошагово совмещает нормализованные изображения распознаваемых объектов, центрированных и вписанных в одинаковых размеров ячейки таблицы и шаблонов, центрированных и вписанных в аналогичные ячейки таблицы шаблонов, с шагом, равным высоте строки с ячейками или ширине столбца ячеек таблиц. При этом в каждом из столбцов или в каждой из строк таблицы шаблонов, число которых равно числу столбцов или строк в таблице распознаваемых объектов, находится полный комплект шаблонов

Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:

- сопоставление дескрипторов двух изображений.

Недостатками известного способа и устройства его реализующего являются:

- отсутствие инвариантности к аффинным преобразованиям;

- необходимость обеспечения центрирования и нормализации изображений;

- необходимость полного перебора шаблонов при распознавании.

Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:

- при пошаговом совмещении изображений даже небольшие различия в структуре изображений приводят к резкому увеличению ошибки распознавания.

Известен способ и устройство для распознавания изображений объектов (Патент RU №2361273 C2, МПК G06K 9/62). Изобретение относится к вычислительной технике и может быть использовано в системах технического зрения для идентификации объектов на изображении.

Технической задачей является повышение точности и качества распознавания за счет использования трехмерной векторной модели эталона объекта. Технический результат достигается следующим образом: эталонное изображение хранят в виде векторной трехмерной модели; для каждой такой модели фиксируют набор параметров для аффинных преобразований: углы поворота по осям х, у, z и масштаб. Этот набор параметров определяют для каждой модели с учетом сложности ее формы: чем сложнее форма, тем большее количество ракурсов необходимо для наиболее полного описания возможных вариантов положения объекта в пространстве с тем, чтобы наиболее точно произвести идентификацию.

Производят следующую последовательность действий: получают векторную трехмерную модель эталонного объекта путем геометрического построения, затем, изменяя ее положение в пространстве (поворот, отражение, масштабирование), получают ряд вышеуказанных параметров, которые сохраняют и используют в дальнейшем при распознавании для воссоздания соответствующего ракурса эталона объекта. При распознавании трехмерный образ поворачивается, каждый раз генерируется ряд плоских изображений, пока не удастся найти совпадение.

Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:

- моделирование аффинных преобразований объекта.

Недостатками известного способа и устройства его реализующего являются:

- наличие этапа предварительной обработки;

- определение ряда параметров объекта, класс, к которому относится данный объект, габаритные размеры. Этот набор параметров определяют для каждой модели с учетом сложности ее формы.

Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:

- большие вычислительные затраты.

Наиболее близким к заявленному решению, выбранному нами за прототип, является способ и устройство аффинно-инвариантного распознавания шаблона [Патент №US 2011/0069889 A1, МПК G06К 9/46]. Изобретение относится к распознаванию объектов цифровых изображений.

Основным техническим требованием является распознавание объекта, инвариантного повороту, перемещению и масштабу. Данное требование достигается путем добавления аффинного инвариантного расширения к методу SIFT (Scale-invariant feature transform). ASIFT (Affine-scale-invariant feature transform) позволяет надежно идентифицировать функции, которые прошли сильные аффинные искажения. Вместо построения аффинно-инвариантных дескрипторов моделирует, с достаточной точностью, все искажения вызванные изменением положения оптических камер. Масштаб и изменение положения камеры (включает два параметра положения оси камеры) - моделируемые параметры; вращение и перемещение (также включает в себя 2 параметра изменения положения) - нормализуемые параметры. ASIFT сначала достигает аффинной инвариантности дескрипторов изображения, затем использует SIFT который стимулирует масштаб и нормализует вращение и перемещение.

Рассматриваемое устройство-прототип предполагает выполнение следующих операций:

1. Каждое изображение преобразуется, путем симулирования всех возможных аффинных искажений, вызванных изменением положения камеры с фронтальной позиции. Эти искажения зависят от двух параметров: долготы φ и широты θ. В результате на первом шаге данного алгоритма получатся определенное множество изображений, отличающихся всевозможными аффинными преобразованиями;

2. Полученные после аффинных преобразований изображения обрабатываются алгоритмом SIFT;

3. SIFT включает в себя следующие операции:

- Нахождение особых точек, путем построения пирамиды гауссианов (Gaussian) и разностей гауссианов (Difference of Gaussian, DoG).

- Уточнение особых точек с помощью аппроксимации функции DoG (разность гауссианов) многочленом Тейлора второго порядка, взятого в точке вычисленного экстремума.

- Нахождение ориентации ключевой точки, которая вычисляется исходя из направлений градиентов смежных точек.

- Построение дескрипторов. В методе SIFT дескриптором является вектор. Как и направление ключевой точки, дескриптор вычисляется на гауссиане, ближайшем по масштабу к ключевой точке, и исходя из градиентов в некотором окне ключевой точки.

Недостатками известного устройства-прототипа являются:

- Различны условия освещения (например, день/ночь).

- Объект имеет отражающую поверхность (как правило, автомобили, зеркала).

- Объект имеет сильную 3-D структуру.

- Объект имеет себе подобные дескрипторы или периодическую структуру.

Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:

- методом ASIFT рассматривается массив изображения в градации серого S_i,j (массив изображения принимает значения в диапазоне от 0 до 255), такой способ позволяет сохранить устойчивость к изменению цвета. Но при таком подходе отражающие поверхности сохраняют свои особенности, что значительно ухудшает процесс поиска соответствия между дескрипторами.

Предлагаемое устройство поиска дубликатов изображений позволяет решить одну из проблем оригинального устройства путем использования цветового пространства YIQ. Устройство реализуют следующий алгоритм. На первом этапе представим массив изображения S_i,j,k в цветовом пространстве YIQ. Это формат телевизионного стандарта NTSC. Данное цветовое пространство, так же как и человеческое зрение, более чувствительно к световой яркости (интенсивности), а не цвету. Изображение состоит из трех компонент - яркость (Y) и двух искусственных цветоразностных (I и Q) составляющих. Сигнал I называется синфазным, Q - квадратурным.

Разложим канал YIQ, на цветовые составляющие. Конверсия из RGB в YIQ осуществляется по следующим формулам:

$$\text{Y}=\text{0,299}\cdot \text{R}+\text{0,587}\cdot \text{G}+\text{0,114}\cdot \text{B}$$ ,

$$\text{I}=\text{0,596}\cdot \text{R-0,274}\cdot \text{G-0,322}\cdot \text{Â}$$ ,

$$\text{Q}=\text{0,211}\cdot \text{R-0,522}\cdot \text{G}+\text{0,311}\cdot \text{Â}$$ .

Анализ изображений различных компонент пространства YIQ показал, что компоненты I и Q не содержат блики и отражения, присущие зеркальным поверхностям. Данные компоненты не содержат яркостной информации, а показывают только цветовую, при этом отражающая структура поверхности характеризуется в большей степени изменением яркости. Выберем канал I для поиска соответствия между дескрипторами на отражающих поверхностях.

Далее полученные изображения обрабатываются алгоритмом ASIFT.

Изображения преобразуются путем симулирования всех возможных аффинных искажений, вызванных изменением положения камеры с фронтальной позиции. Эти искажения получаются путем изменения двух параметров: φ долготы и широты θ. В результате на первом шаге данного способа имеется определенное множество изображений, отличающихся различными аффинными преобразованиями. Вращения и наклоны моделируются для конечных и небольших значений широты и долготы угла, выбор шага этих параметров обеспечивается моделируемым изображением, которое принимает любую возможность обзора при других значениях широты и долготы.

Затем выполняется этап нахождение особых точек. Основным моментом в детектировании особых точек является построение пирамиды гауссианов и разностей гауссианов. Гауссианом (или, изображением размытым гауссовым фильтром) является изображение:

$$L(x,y,\sigma )=G(x,y,\sigma )*I(x,y)$$ ,

где L - значение гауссиана в точке с координатами (x, y), σ - радиус размытия, G - гауссово ядро, I - значение исходного изображения, * - оператор свертки.

Разностью гауссианов называют изображение, полученное путем попиксельного вычитания одного гауссиана исходного изображения из изображения с другим радиусом размытия.

$$D(x,y,\sigma )=(G(x,y,k\sigma )-G(x,y,\sigma ))*I(x,y)=L(x,y,k\sigma )-L(x,y,\sigma ).$$

Масштабируемым пространством изображения является набор всевозможных, сглаженных некоторым фильтром, версий исходного изображения. Доказано, что гауссово пространство является линейным, инвариантным относительно сдвигов, вращений, масштаба, не смещающим локальные экстремумы, и обладает свойством полугрупп. Различная степень размытия изображения гауссовым фильтром может быть принята за исходное изображение, взятое в некотором масштабе.

Инвариантность относительно масштаба достигается за счет нахождения ключевых точек для исходного изображения, взятого в разных масштабах. Для этого строится пирамида гауссианов: все масштабируемое пространство разбивается на некоторые участки - октавы, причем часть масштабируемого пространства, занимаемого следующей октавой, в два раза больше части, занимаемой предыдущей. К тому же, при переходе от одной октавы к другой делается ресэмплинг изображения, его размеры уменьшаются вдвое. Естественно, что каждая октава охватывает бесконечное множество гауссианов изображения, поэтому строится только некоторое их количество N, с определенным шагом по радиусу размытия. С тем же шагом достраиваются два дополнительных гауссиана (всего получается N+2), выходящих за пределы октавы. Масштаб первого изображения следующей октавы равен масштабу изображения из предыдущей октавы с номером N.

Параллельно с построением пирамиды гауссианов строится пирамида разностей гауссианов, состоящая из разностей соседних изображений в пирамиде гауссианов (фиг.1). Соответственно, количество изображений в этой пирамиде будет N+1.

Каждая разность получается из двух соседних гауссианов, количество разностей на единицу меньше количества гауссианов, при переходе к следующей октаве размер изображений уменьшается вдвое.

После построения пирамид находим особые точки. Точка будет считаться особой, если она является локальным экстремумом разности гауссианов. На фиг.2 показан этап определения точек экстремума. Она считается таковой, если значение разности гауссианов в помеченной точке, больше (меньше) всех остальных значений в точках.

В каждом изображении из пирамиды разности гауссианов определяются точки локального экстремума. Каждая точка текущего изображения DoG сравнивается с ее восьмью соседями и с девятью соседями в DoG, находящихся на уровень выше и ниже в пирамиде. Если эта точка больше (меньше) всех соседей, то она принимается за точку локального экстремума.

Следующим шагом будет уточнение особых точек - проверка пригодности точки экстремума на роль особой.

Определяются координаты особой точки с субпиксельной точностью. Это достигается с помощью аппроксимирования функции DoG многочленом Тейлора второго порядка, взятого в точке вычисленного экстремума.

$$D(x)=D+\frac{\partial D^T}{\partial x}x+\frac{1}{2}{x}^T\frac{{\partial }^{2}D}{\partial x^2}x$$ ,

где D - функция DoG, x=(x, y, σ) - вектор смещения относительно точки разложения, первая производная DoG - градиент, вторая производная DoG - матрица Гессе.

Экстремум многочлена Тейлора находится путем вычисления производной и приравнивания ее к нулю. В итоге получается смещение точки вычисленного экстремума, относительно точного:

$$\stackrel{\wedge }{х}=-\frac{{\partial }^2{D}^{-1}}{\partial x^2}\frac{\partial D}{\partial x}$$ .

Если одна из компонент ∧вектора $$\stackrel{\wedge }{х}$$ больше 0,5*шаг сетки в этом направлении, то это означает, что на самом деле точка экстремума была вычислена неверно и нужно сдвинуться к соседней точке в направлении указанных компонент. Для соседней точки все повторяется заново. Если таким образом мы вышли за пределы октавы, то следует исключить данную точку из рассмотрения.

Когда положение точки экстремума вычислено, проверяется само значение DoG в этой точке по формуле:

$$D(\stackrel{\wedge }{х})=D+\frac{1}{2}\frac{\partial D^T}{\partial x}x$$ .

Если эта проверка не проходит, то точка исключается как точка с малым контрастом.

Последняя проверка включает проверку, если особая точка лежит на границе какого-то объекта или плохо освещена, в этом случае такую точку можно исключить из рассмотрения. Эти точки имеют большой изгиб (одна из компонент второй производной) вдоль границы и малый в перпендикулярном направлении. Этот большой изгиб определяется матрицей Гессе H. Для проверки подойдет H размера 2×2.

$$H=\left[\begin{array}{cc}{D}_{xx}& D_{xy}\\ D_{xy}& D_{yy}\end{array}\right]$$ .

Пусть Tr(H) - след матрицы, a Det(H)- ее определитель.

$$Tr(H)=D_{xx}+D_{yy}=\alpha +\beta$$ ,

$$Det(H)=D_{xx}{D}_{yy}-{(D_{xy})}^2=\alpha \beta$$ .

Пусть r - отношение большего изгиба к меньшему,

$$\alpha =r\beta$$ ,

Тогда

$$\frac{Tr{(H)}^2}{Det(H)}=\frac{{(\alpha +\beta )}^2}{\alpha \beta }=\frac{{(r\alpha +\beta )}^2}{r{\beta }^2}=\frac{{(r+1)}^2}{r}$$ ,

и точка рассматривается дальше, если

$$\frac{Tr{(H)}^2}{Det(H)}<\frac{{(r+1)}^2}{r}$$ .

Направление ориентации ключевой точки вычисляется исходя из направлений градиентов точек, соседних с особой. Все вычисления градиентов производятся на изображении в пирамиде гауссианов, с масштабом, наиболее близким к масштабу ключевой точки. Величина и направление градиента в точке (x, y) вычисляются по формулам:

$$m(x,y)=\sqrt{{(L(x+1,y)-L(x-1,y))}^2+{(L(x,y+1)-L(x,y-1))}^2}$$ ,

$$\theta (x,y)={\tan }^{-1}(\frac{L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1,y)}$$ ,

где $$m$$ - величина градиента, $$\theta$$ - его направление.

Для начала определим окно (окрестность) ключевой точки, в котором будут рассмотрены градиенты. Это будет окно, требуемое для свертки с гауссовым ядром, оно будет круглым и радиус размытия для этого ядра (σ) равен 1,5*масштаб ключевой точки. Для гауссова ядра действует, так называемое, правило «трех сигм». Оно состоит в том, что значение гауссова ядра очень близко к нулю на расстоянии, превышающем 3*σ. Таким образом, радиус окна определяется как [3*σ].

Направление особой точки находится из гистограммы направлений (фиг.3). Гистограмма состоит из 36 компонент, которые равномерно покрывают промежуток в 360 градусов, и формируется она следующим образом: каждая точка окна (x, y) вносит вклад, равный m*G(x, y, σ), в ту компоненту гистограммы, которая покрывает промежуток, содержащий направление градиента θ(x, y).

Направление ключевой точки лежит в промежутке, покрываемом максимальной компонентой гистограммы. Значения максимальной компоненты (max) и двух соседних с ней интерполируются параболой, и точка максимума этой параболы берется в качестве направления ключевой точки. Если в гистограмме есть еще компоненты с величинами не меньше 0.8*max, то они аналогично интерполируются и дополнительные направления приписываются ключевой точке.

На следующем этапе происходит построение дескрипторов. В методе SIFT дескриптором является вектор. Как и направление ключевой точки, дескриптор вычисляется на гауссиане, ближайшем по масштабу к ключевой точке, и исходя из градиентов в некотором окне ключевой точки. Перед вычислением дескриптора это окно поворачивают на угол направления ключевой точки, чем и достигается инвариантность относительно поворота.

Фиг.3 схематично показывает часть изображения и полученный на ее основе дескриптор. Здесь изображены пиксели, обозначенные маленькими квадратиками. Эти пиксели берутся из квадратного окна дескриптора, которое в свою очередь поделено еще на четыре равные части (регионы). Центр этого окна находится между пикселями. Его надо выбирать как можно ближе к точным координатам ключевой точки. Круг обозначает окно свертки с гауссовым ядром (аналогично окну для вычисления направления ключевой точки). Для этого ядра определяется а, равное половине ширины окна дескриптора. В дальнейшем значение каждой точки окна дескриптора будет домножаться на значение гауссова ядра в этой точке, как на весовой коэффициент.

Справа схематически изображен дескриптор особой точки, размерности 2×2×8. Первые две цифры в значении размерности - это количество регионов по горизонтали и вертикали. Те квадраты, которые охватывали некоторый регион пикселей на левом изображении, справа охватывают гистограммы, построенные на пикселях этих регионов. Соответственно, третья цифра в размерности дескриптора означает количество компонент гистограммы этих регионов.

Каждому градиенту в окне дескриптора можно приписать три вещественные координаты (x, y, n), где x - расстояние до градиента по горизонтали, y - расстояние по вертикали, n - расстояние до направления градиента в гистограмме (имеется в виду, соответствующая гистограмма дескриптора, в которую вносит вклад этот градиент). За точку отсчета принимается левый нижний угол окна дескриптора и начальное значение гистограммы. За единичные отрезки берутся размеры регионов по горизонтали и вертикали для x и y соответственно, и количество градусов в компоненте гистограммы для n. Коэффициент трилинейной интерполяции определяется для каждой координаты (x, y, n) градиента как 1-d, где d равно расстоянию от координаты градиента до середины того единичного промежутка в который эта координата попала. Каждое вхождение градиента в гистограмму умножается на все три весовых коэффициента трилинейной интерполяции.

Дескриптор ключевой точки состоит из всех полученных гистограмм. Полученный дескриптор нормализуется, после чего все его компоненты, значение которых больше 0,2, урезаются до значения 0,2 и затем дескриптор нормализуется еще раз. В таком виде дескрипторы готовы к использованию.

На следующих этапах происходит сопоставление дескрипторов исходных изображений и изображений в цветовом пространстве YIQ. На заключительном этапе происходит объединение результатов сопоставления.

Устройство поиска дубликатов изображений (фиг.4) содержит вход, который подключен к входу блока предобработки первого изображения 1 и к входу блока предобработки второго изображения 2, блок 1 состоит из блока регистрации первого изображения 1.1, выход которого подключен к входу блока преобразования первого изображения в цветовое пространство YIQ 1.2, выход которого подключен к входу блока выделения синфазной составляющей первого изображения 1.3, выход которого подключен к входу блока формирования изображений в результате вращения первого изображения 1.4, выход которого подключен к входу блока формирования изображения при изменении угла наклона первого изображения 1.5, выход которого подключен к входу блока хранения моделированных изображений для первого изображения 1.6, выход которого подключен к первому входу блока применения метода SIFT; выход блока регистрации второго изображения 2.1 подключен ко входу блока преобразования второго изображения в цветовое пространство YIQ 2.2, выход которого подключен ко входу блока выделения синфазной составляющей второго изображения 2.3, выход которого подключен к входу блока формирования изображений в результате вращения второго изображения 2.4, выход которого подключен к входу блока формирования изображения при изменении угла наклона второго изображения 2.5, выход которого подключен к входу блока хранения моделированных изображений для второго изображения 2.6, выход которого подключен ко второму входу блока применения метода SIFT (блок-схема устройства представлена на фиг.5, патент № US6711293B1, МПК G06К 9/68), выход которого подключен к входу блока вычисления количества одинаковых дескрипторов 4, выход которого подключен к входу блока хранения найденной пары дубликатов 5, выход которого является информационным выходом устройства.

Устройство поиска дубликатов изображений реализуется и работает следующим образом. На входы блоков регистрации первого 1.1 и второго 2.1 изображения поступает два изображения, на которых необходимо найти соответствующие дескрипторы и установить их похожесть. С целью обработки изображений с зеркальными поверхностями изображения преобразуются в цветовое пространство YIQ в блоках преобразования изображения в цветовое пространство YIQ 1.2 и 2.2. Далее происходит выделение синфазной составляющей цветового пространства YIQ в блоках 1.3 и 2.3. В следующих блоках 1.4, 2.4, 1.5, 2.5 формируются изображения в результате вращения и изменения угла наклона, то есть применения аффинных преобразований. В блоках 1.6 и 2.6 записываются все полученные изображения в результате данных преобразований. В блоке применения метода SIFT осуществляется построение SIFT-дескрипторов всех изображений указанным методом. Полученные дескрипторы для пары изображений поступают на вход блока 4, в котором вычисляется количество одинаковых дескрипторов и принимается решение о том, что второе изображение является дубликатом первого, после чего найденные дубликаты записываются в блок хранения найденной пары дубликатов 5.

Технический результат - сопоставление дескрипторов применительно к задаче поиска дубликатов изображений.

Устройство поиска дубликатов изображений, содержащее блок предобработки первого изображения и блок предобработки второго изображения, блок предобработки первого изображения состоит из блока регистрации первого изображения; блока формирования изображений в результате вращения первого изображения, выход которого подключен к входу блока формирования изображения при изменении угла наклона первого изображения, выход которого подключен к входу блока хранения моделированных изображений для первого изображения, выход которого подключен к первому входу блока применения метода SIFT; блока регистрации второго изображения, блока формирования изображений в результате вращения второго изображения, выход которого подключен к входу блока формирования изображения при изменении угла наклона второго изображения, выход которого подключен к входу блока хранения моделированных изображений для второго изображения, выход которого подключен ко второму входу блока применения метода SIFT, блока хранения найденной пары дубликатов, выход которого является информационным выходом устройства, отличающееся тем, что выход блока регистрации первого изображения подключен к входу блока преобразования первого изображения в цветовое пространство YIQ, выход которого подключен к входу блока выделения синфазной составляющей первого изображения; выход блока регистрации второго изображения подключен к входу блока преобразования второго изображения в цветовое пространство YIQ, выход которого подключен к входу блока выделения синфазной составляющей второго изображения; выход блока применения метода SIFT подключен к входу блока вычисления количества одинаковых дескрипторов, выход которого подключен к входу блока хранения найденной пары дубликатов.