Распознавание нечётких дубликатов изображений, основанное на ранговом распределении мощностей кластеров яркости

ОБРАБОТКА ИЗОБРАЖЕНИЙ, РАСПОЗНАВАНИЕ ОБРАЗОВ

РАСПОЗНАВАНИЕ НЕЧЁТКИХ ДУБЛИКАТОВ ИЗОБРАЖЕНИЙ, ОСНОВАННОЕ НА РАНГОВОМ РАСПРЕДЕЛЕНИИ МОЩНОСТЕЙ КЛАСТЕРОВ ЯРКОСТИ

Немировский В.Б., Стоянов А.К.

Институт кибернетики ФГБОУВПО «Национальный исследовательский Томский политехнический университет»

Аннотация

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

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

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

Введение

Задача распознавания дубликатов изображений актуальна для поиска изображений по образцу в Интернете, цифровых архивах и библиотеках; при анализе содержания космических и аэрофотоснимков, для систем технического зрения и т.д. [1].

Под нечёткими дубликатами мы будем понимать изображения, которые могут быть переведены друг в друга путём таких преобразований, как поворот, сдвиг, изменение угла обзора, изменение разрешения, изменение масштаба, изменение освещения [2]. Такие изображения могут быть получены в результате изменения условий их съёмки или при их редактировании [3 - 8]. Это устоявшийся термин информационного поиска.

Задача распознавания нечётких дубликатов относится к задачам распознавания изображений. Современные технологии распознавания изображений основаны на сравнении их визуальных примитивов и количественной оценке близости изображений по значениям этих примитивов. Визуальные примитивы изображения - это те его характеристики, которые вычисляются по исходному изображению и могут быть использованы для распознавания и поиска. Поисковый образ изображения, сгенерированный из таких примитивов, отражает его содержание, невелик по размеру и удобен для организации поиска. Использование визуальных примитивов является на сегодняшний день достаточно эффективным и универсальным средством распознавания и поиска изображений в коллекциях оцифрованных изображений [9].

Очень часто при распознавании изображения в качестве его образа выбирают гистограммы - распределение пикселей по какому-то из выбранных визуальных примитивов [10]. Это могут быть гистограммы яркостей, цветов или выходов фильтров и т.п. Применение гистограмм привлекательно тем, что близость между ними определяется просто и её мож-

но быстро вычислять, используя известные меры близости. Несмотря на предельную простоту подхода, он показывает довольно стабильные результаты [9]. Однако при сопоставлении изображений с помощью гистограмм бывает много ошибочных результатов.

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

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

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

1. Многошаговая сегментация изображения

Для сегментации изображений был выбран метод многошаговой сегментации полутоновых изображений, предложенный и рассмотренный нами в [11 - 13]. Этот метод свободен от главного недостатка большинства методов, основанных на кластеризации, -необходимости априорного задания числа кластеров. Метод основан на кластеризации значений яркости пикселей изображения рекуррентной нейронной сетью, представленной на рис. 1.

В [13] показано, что нейронную сеть с локальной обратной связью нейронов входного слоя можно использовать для кластеризации данных. Обратная связь приводит к одномерному отображению входных значений на активационной функции нейронов сети. Сегментация выполняется в несколько шагов, каждый из которых использует результаты предыдущего шага в качестве входных данных. Сегментация завершается, когда энтропия изображения, полученного на очередном шаге, перестаёт меняться. Описанная процедура была названа многошаговой сегментацией.

4ч ч

Рис.1. Структура моделируемой нейронной сети Многошаговая сегментация обеспечивает максимально упорядоченное по яркости распределение однородных областей пикселей на изображении. Это позволяет считать, что преобразованное изображение свободно от излишних подробностей и в то же время наиболее полно передаёт семантику представленной на нём сцены.

2. Распознавание сегментированных изображений

Чтобы разобраться в особенностях распознавания изображения, сегментированного описанной выше многошаговой процедурой, обратимся к диаграмме Ламерея (рис. 2).

X ] х; А В

Рис. 2. Диаграмма Ламерея для одномерного отображения значений яркости. х* и х* - устойчивые точки; х* -неустойчивая точка отображения Она наглядно представляет процесс одномерного отображения значений яркости на активационной функции нейрона /(х), лежащий в основе кластеризации. В качестве такой функции рассматривается сиг-моида. В процессе отображения хп+1 =/(хп), где п -номер текущей итерации, любое значение х, попавшее в интервал между точками А и В, достигнет устойчивой точки за одно и то же количество итераций. Именно этим свойством и обеспечивается эффект кластеризации значений яркости и, как следствие, сегментация изображения [11].

Покажем, что эта особенность одномерного отображения даёт возможность отождествлять сегменти-

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

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

Первый вариант: после преобразования изменённое значение яркости останется в интервале АВ. Значит, это значение в процессе отображения достигнет устойчивой точки х3 за то же количество итераций, как и в случае оригинального изображения (т. е. значение попадёт в тот же кластер).

Второй вариант: в результате преобразования значение яркости пикселя оригинального изображения выйдет за пределы интервала АВ. В этом случае значение после преобразования попадёт в другой кластер.

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

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

3. Оценка близости изображений

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

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

Мера близости между двумя векторами (то есть изображениями) в п-мерном векторном пространстве может быть задана в виде угла. Пусть заданы вектор входного изображения = (*ь *2,..., *п) и вектор изображения-оригинала X = х

, х2, ... , хп ). Тогда близость

векторов определяется выражением

(

= агссоБ

' х.

X • 5

где | | и | X | в знаменателе соответственно длины векторов 5 и X, а в числителе стоит их скалярное произведение. Такая мера называется косинусным расстоянием, и для неё соблюдаются все требуемые аксиомы метрического пространства. Принадлежность входного изображения 5 к оригиналу X определяется с помощью решающего правила: 5 е X, если < е,

где е << 1 - наперёд заданная положительная величина.

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

Ранговое распределение - это зависимость некоторой величины от ранга - порядкового номера в ряду её значений, упорядоченных по убыванию. Такое распределение широко используется при анализе текстов, технических и физических систем и лежит в основе рангового анализа систем [6].

Для нашего исследования важно то, что ранговые распределения с одинаковым числом рангов можно сравнивать.

4. Экспериментальные результаты

С целью проверки возможности применения многошаговой сегментации для распознавания нечётких дубликатов нами был проведён ряд экспериментов с изображениями в градациях серого цвета. При их проведении применялась программа сегментации изображений, реализующая описанный ранее алгоритм. В ней программная модель рекуррентной нейронной сети, представленная на рис. 1, использовалась в качестве модуля для кластеризации яркости. Параметры нейронной сети рассчитывались по методике, приведённой в [11, 12].

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

Энтропия Н, требуемая для оценки степени завершённости сегментации изображения, на каждом шаге оценивалась по формуле Шеннона

Н = "ХР'1о& Р1.

г

Здесь р1 = / N ; - число значений яркости, попавшей в г -й кластер; N - общее количество всех значений яркости. Суммирование велось по количеству кластеров, полученных при отображении входных значений яркостей пикселей на активационной функции нейрона.

С помощью описанной многошаговой процедуры получались сегментированные изображения оригинала изображения и его нечётких дубликатов. Создание дубликатов моделировалось Гауссовым искажением яркостей пикселей эталонного изображения, выполненным с помощью растрового редактора Adobe Photoshop.

На рис. 3 и 4 приведены некоторые из использованных для распознавания изображений. Соответствующие им ранговые распределения мощностей кластеров яркости приведены на рис. 5а, б. На рисунке по ординате откладывались относительные значения мощности кластеров, вычисленные как отношение числа пикселей, попавших в данный кластер, к общему числу пикселей изображения. По абсциссе откладывались номера рангов кластеров.

W I у

Si I Я

а) б) в)

Рис. 3. Лицо мужчины: а) оригинал изображения, взятого из [15]; б) Гауссово искажение изображения

а) б)

Рис. 4. Изображения, полностью не совпадающие с оригиналом: а) лицо мальчика [16]; б) пейзаж [17]

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

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

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

Мощность кластера 0,3

0,2

0,1

а) О

Мощность кластера 0,3

0,2

0,1

б) О

Рис. 5. Ранговое распределение мощностей кластеров яркости: а) оригинал из [15]; б) оригинал и его искажённые дубликаты

Чем более похожи сравниваемые изображения, тем меньше расстояние й между ними, определённое по (1). Полному совпадению изображений соответствует нулевое значение й. Пороговое расстояние, при котором изображение считается совпадающим с оригинальным, было выбрано равным й0 = 0,157. Это соответствует 10 % (в градусах) от угла в 90°, при котором и-мерные вектора сравниваемых изображений ортогональны, то есть изображения совершенно разные. Выбранный порог соответствует порогу, установленному на основании визуальной оценки совпадения изображений. Он обеспечивает количественную оценку близости, соответствующую субъективному человеческому восприятию схожих изображений. Действительно, при радиусе искажения, равном 8 пикселям, согласно принятой нами метрике, й = 0,15 < й0 и сравниваемые изображения имеют достаточно высокую степень сходства. В этом несложно убедиться, обратившись к рис. 3. Изображения оригинала (рис. 3а) и его дубликата (рис. 3б) трудно считать относящимися к разным людям. Заметим, что предложенный порог различения довольно жёсткий. Человеческий глаз позволяет распознать дубликат и при более высоком уровне искажений (рис. 3в).

Количественная оценка близости ранговых распределений, представленных на рис. 5а, приведена в табл. 1. Расстояния вычислялись как для рангового распределения мощности кластеров, так и для гистограмм. Определение расстояний для гистограмм выполнено из того соображения, что их использование для сравнения двух изображений до сих пор является популярным методом [18].

Таблица 1. Косинусное расстояние между ранговыми распределениями мощностей кластеров яркости эталонного изображения и изображений других объектов

Изображения Расстояние по мощности кластеров Расстояние по гистограммам

Лицо мальчика - лицо мужчины 0,764 0,560

Пейзаж - лицо мужчины 0,482 0,459

Из таблицы видно, что вычисленные расстояния значительно превышают установленный порог распознавания й0 = 0,157. При этом расстояние, вычисленное по ранговым распределениям, показывает большее различие изображений, чем при использовании гистограмм. Иными словами, качество распознавания изображения по мощности кластеров выше.

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

Расстояние

0,6

0,4

0,2

0 4 8 12 16

Рис. 6. Зависимость косинусного растояния между эталоном и его дубликатами от радиуса Гауссового искажения

Изучение результатов, представленных на рис. 6, показывает, что расстояние между оригиналом и его дубликатами, вычисленное по ранговому распределению мощности кластеров, в разы (примерно, от двух до четырёх) меньше расстояния, определённого по гистограммам яркости. Порог распознавания й0=0,157 для гистограмм достигается при значительно меньших искажениях, чем для распределения мощности кластеров.

Дубликаты оригинала могут быть искажёнными за счёт изменений яркости, а также иметь другой масштаб. Многошаговая сегментация позволяет получать числовые характеристики для распознавания изображения по его уменьшенному и искажённому дубликату. На рис. 7 приведён график зависимости косинусного расстояния от радиуса Гауссового размытия при сравнении неискажённого оригинала изображения с его уменьшенными в 5 раз и искажёнными дубликатами. Дубликаты с разной степенью искажения были сделаны для оригинала изображения с рис. 3а. Для наглядности на рис. 7 показан и график расстояния между оригиналом и искажённым, но не уменьшенным дубликатом. Видно, что расхождение между кривыми значительно лишь при малых радиусах искажения (примерно до трёх пикселей). При больших радиусах кривые почти совпадают, что свидетельствует о высоком совпадении результатов сравнения в обоих случаях.

! А - Оригинал Л ----Пейзаж ----Мальчик

1 V \ \

\\ л \ V - Ранг астера

3 6 9 12 15

\ ( \ - Оригинал ----Радиус искажения 6 пике. ----Радиус искажения 12 пике.

\

Ранг астера

J_ ^— - -------^

3 6 9 12 15

Расстояние 0,3

0,2

0,1

-Без уменьшения ---Уменьшение в 5 раз

Рад лус искаже ний

О 4 8 12 16

Рис. 7. Зависимость косинусного расстояния между оригиналом и его уменьшенными дубликатами от радиуса Гауссового искажения

Описанный подход был применён нами и к распознаванию цветных изображений. При этом цветное изображение предварительно преобразовывалось в градации серого цвета следующим образом. В качестве яркости пикселей серого изображения использовался яркостный компонент цветовой модели YUV, использованной в [19]. В этой модели яркостный компонент

Y изображения несёт основную информацию об изображении, а цветоразностные компоненты U и V менее информативны. Поэтому для сегментации и распознавания у оригинала и дубликатов кластеризовалась только яркость Y, а цветоразностные компоненты в распознавании не учитывались. Яркостный компонент

Y цветовой модели YUV уже содержит косвенную информацию о цвете, поскольку является взвешенной суммой цветовых компонентов RGB-модели

Y = 0,299R + 0,587G + 0,114B .

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

Для проверки возможности применения обсуждаемой процедуры распознавания для цветных изображений и их нечётких дубликатов были использованы изображения, некоторые их которых приведёны на рис. 8. Создание дубликатов моделировалось Гауссовым искажением яркостей пикселей эталонного изображения, выполненным с помощью растрового редактора Adobe Photoshop.

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

На рис. 8б, г представлены те цветные дубликаты, которые ещё распознаются при установленном пороге распознавания d0 = 0,157.

Количественная оценка зависимости расстояния между эталонами и их дубликатами от радиуса Гауссового искажения представлена на рис. 9.

Из рисунка видно, что при d0= 0,157 распознавание для всех указанных сочетаний происходит для довольно высоких значений радиуса искажения, примерно до 11-13 пикселей. Кроме того, видно, что от

сочетания цветовых представлений оригинала и дубликатов зависит и распознавание.

tа

а)\

б)\

Ч *

г) I

Рис. 8. Результаты распознавания цветных изображений; а) цветной оригинал из [20]; б) Гауссово искажение изображения (радиус искажения - 12 пикселей); в) серый оригинал; г) Гауссово искажение изображения (радиус искажения - 10 пикселей) Расстояние

0,2

0,1

-7 —2 ........3---4 //

[?2

.У У ..........

.........' Padi ус иск юкенм i, пике.

0 2 4 6 8 10 12 14

Рис. 9. Зависимость косинусного расстояния между эталоном и его дубликатами от радиуса Гауссового искажения в случае цветных изображений; 1) цветной оригинал - цветные дубликаты; 2) серый оригинал - серые дубликаты; 3) цветной оригинал - серые дубликаты; 4) серый оригинал - цветные дубликаты

Наиболее искажённые (примерно 13 пикселей) дубликаты распознаются для сочетания цветной оригинал и цветные дубликаты. При сочетании серый оригинал - серые дубликаты успешное распознавание завершается при меньших искажениях (примерно 11 пикселей). Сочетания разных цветовых представлений дают предельное расстояние при промежуточных искажениях. Во всех исследованных случаях, тем не менее, степень визуального искажения дубликатов значительна (рис. 8).

Выводы

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

2. Ранговое распределение мощности кластеров яркости на сегментированном изображении являет-

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

3. При выбранном пороге распознавания d0 = 0,157 распознавание на основе рангового распределения позволяет определять нечёткие дубликаты изображения в градациях серого цвета до радиуса Гауссовых искажений на них, равного 8-11 пикселям и пятикратного уменьшения их размеров.

4. Использование рангового распределения позволяет надёжно решать задачу обнаружения оригинала изображения и для случая цветных изображений.

Литература

1. Шапиро, Л. Компьютерное зрение / Л. Шапиро, Дж. Сток-ман. - Под ред. С. Соколова. - Пер. с англ. А. Богуславский. - М.: Бином. Лаборатория знаний, 2006. - 752 с.

2. Пименов, В.Ю. Метод поиска нечётких дубликатов изображений на основе выявления точечных особенностей. Труды РОМИП 2007-2008.- СПб.: НУ ЦСИ. 2008. -С. 145-158.

3. Christiein, V. An Evaluation of Popular Copy-Move Forgery Detection Approaches / V. Christlein, C. Riess, J. Jordan, C. Riess, E. Angelopoulou // IEEE Transactions on Information Forensics and Security. - 2012. - Vol. 7(6). - P. 1841-1854.

4. Farid, H. Image Forgery Detection / H. Farid // IEEE Signal Processing Magazine. - 2009. - P. 16-25.

5. Sridevi, M. Comparative Study of Image forgery and Copy-move Techniques / M. Sridevi, C. Mala, S. Sanyam. - Proceedings of the Second International Conference on Computer Science, Engineering and Applications (ICCSEA 2012). - New Delhi, India, 2012. - P. 715-723.

6. Глумов, Н.И. Поиск дубликатов на цифровых изображениях / Н.И. Глумов, А.В. Кузнецов, В.В. Мясников // Компьютерная оптика. - 2013. - Т. 37, № 3. - С. 360-367.

7. Кузнецов, А.В. Алгоритм обнаружения дубликатов на цифровых изображениях с использованием эффективных линейных локальных признаков / А.В. Кузнецов, В.В. Мясников // Компьютерная оптика. - 2013. - Т. 37, № 4. -С. 489- 496.

8. Мельниченко, А. Методы поиска изображений по визуальному подобию и детекции нечётких дубликатов изображений / А. Мельниченко, А. Гончаров // Труды РОМИП 2009. - СПб.:НУ ЦСИ. - 2009. - С. 108-121.

9. Байгарова, Н.С. Некоторые подходы к организации содержательного поиска изображений и видеоинформации [Электронный ресурс] / Н.С. Байгарова, Ю.А. Бух-штаб, Н.Н. Евтеева, Д.А. Корягин // Институт прикладной математики им. М.В. Келдыша РАН. - URL: http://www.keldysh.ru/papers/2002/prep78/prep2002_78.html (дата обращения: 26.05.2014).

10. Котов, В.В. Использование гистограммных оценок в задачах распознавания / В.В. Котов // Успехи современного естествознания. - 2004. - № 4. - С. 40-42.

11. Немировский, В.Б Сегментация изображений с помощью рекуррентной нейронной сети / В.Б. Немировский, А.К. Стоянов // Известия Томского политехнического университета. - 2012. - Т. 321, № 5. - С. 205-210.

12. Nemirovsky, V.B. Multi-Step Segmentation of Images by Means of a Recurrent Neural Network / V.B. Nemirovsky, A.K. Stoyanov // 7th International Forum on Strategic Technology (IFOST - 2012): Proceedings: in 2 vol., Tomsk, September 18-21, 2012. - Tomsk: TPU Press, 2012. -Vol. 1. - P. 557-560.

13. Стоянов, А.К. Применение рекуррентной нейронной сети для решения задачи кластеризации / А.К. Стоянов // Известия Томского политехнического университета. -2009. - Т. 315, № 5. - С. 144-149.

14. Кудрин, Б.И. Математика ценозов: видовое, рангови-довое, ранговое по параметру гиперболические Н-рас-пределения и законы Лотки, Ципфа, Парето, Мандельб-рота / Б. И. Кудрин. - Техногенная самоорганизация. Вып. 25. Ценологические исследования. - М.: Центр системных исследований, 2004. - 248 с.

15. Фотоблог о моде и стиле 2012-2014 [Электронный ресурс]. - URL: http://mens.by/style/shine/470-mustache-side-burns (дата обращения: 26.05.2014).

16. Детские портреты в ч/б [Электронный ресурс]. - URL: http://www.liveinternet.ru/users/katiava/post285466584 (дата обращения: 26.05.2014).

17. Чёрно-белые обои для рабочего стола [Электронный ресурс]. - URL: http://oboiny.ru/cherno-belye-oboi-dlya-ra-bochego-stola/ (дата обращения: 26.05.2014).

18. Dalal, N. Histograms of Oriented Gradients for Human Detection. / N. Dalal, W. Triggs // IEEE Computer Society Conference on Computer Vision and Pattern Recognition CVPR05. - 2005. - Vol. 1(3). - P. 886-893.

19. Немировский, В.Б. Сегментация цветных изображений природных объектов с помощью рекуррентной нейронной сети / В.Б. Немировский, А.К. Стоянов // Известия Томского политехнического университета. - 2013. -Т. 323, № 1. - С. 212-216.

References

1. Shapiro, L.G. Computer vision / L.G. Shapiro, G.C. Stockman. - Prentice Hall, 2001 - 580 p.

2. Pimenov, V.Iu. Near-Duplicate Image Detection with Local Interest Point Extraction / V.Iu. Pimenov // Trudy ROMIP 2007-2008 (Proc. ROMIP 2007-2008). - Saint Petersburg.: NU TCSI. - 2008. - P. 145-158. - (In Russian).

3. Christlein, V. An Evaluation of Popular Copy-Move Forgery Detection Approaches / V. Christlein, C. Riess, J. Jordan, C. Riess, E. Angelopoulou // IEEE Transactions on information forensics and security. - 2012. - Vol. 7(6). -P. 1841-1854.

4. Farid, H. Image Forgery Detection / H. Farid // IEEE Signal processing magazine. - 2009. - P. 16-25.

5. Sridevi, M. Comparative Study of Image forgery and Copy-move Techniques / M. Sridevi, C. Mala, S. Sanyam. - Proceedings of the Second International Conference on Computer Science, Engineering and Applications (ICCSEA 2012). - New Delhi, India, 2012. - P. 715-723.

6. Glumov, N.I. The Algorithm for Copy-move Detection on Digital Images / N.I. Glumov, A.V. Kuznetsov, V.V. Myas-nikov // Computer Optics. - 2013. - V. 37(3). - P. 360-368.

7. Kuznetcov, A.V. Efficient Linear Local Features Based Copy-Move Detection Algorithm / A.V. Kuznetsov, V.V. My-asnikov / Computer Optics. - 2013. - V. 37(4). - P. 489496.

8. Melnichenko, A. Image retrieval methods by the visual similarity and the detection of near-duplicate image. / A. Melnichenko, A. Goncharov // Trudy ROMIP 2009 (Proceedings ROMIP 2009). - Saint Petersburg.: NU TCSI. -2009 - P. 108-121. - (In Russian).

9. Baigarova, N.S. Various Questions Connected with Content-Based Search of Visual Information and Videoinformation [Electronical Resource] / N.S. Baigarova, Iu.A. Bukh-shtab, N.N. Evteeva, D.A. Koriagin // Preprint, Inst. Appl. Math., the Russian Academy of Science]. - Available at: http://www.keldysh.ru/papers/2002/prep78/prep2002_78.html (accessed 26 May 2014). - (In Russian).

10. Kotov, V.V. Use of histogram estimates in recognition tasks / V.V. Kotov // Uspehi sovremennogo estestvoznaniia. - 2004. -

N 4. - P. 40-42. - Available at: http://www.rae.ru/use/7sec-tion=content&op=show_article&article_id=7780895 (accessed 12 March 2014). - (In Russian).

11. Nemirovsky, V.B. Image Segmentation by Recurrent Neural Network / V.B. Nemirovsky, A.K. Stoyanov // Bulletin of the Tomsk Polytechnic University. - 2012. - Vol. 321(5).

- P. 205-210.

12. Nemirovsky, V.B. Multi-Step Segmentation of Images by Means of a Recurrent Neural Network / V.B. Nemirovsky, A.K. Stoyanov // 7th International Forum on Strategic Technology (IFOST - 2012): Proceedings: in 2 vol., Tomsk, September 18-21, 2012. - Tomsk: TPU Press, 2012. - Vol. 1. -P. 557-560.

13. Stoyanov, A.K. Distribution of two-dimensional areas in Euclidean space / A.K. Stoyanov // Bulletin of the Tomsk Polytechnic University. - 2009. - Vol. 315(5). - P. 144-149.

- (In Russian).

14. Kudrin, B.I. Mathematics of cenoses: species, the rank of species, ranking in the parameter hyperbolic H-distribution laws Lotka, Zipf, Pareto, and Mandelbrot / B.I. Kudrin //

"Cenologicheskie issledovaniia", Issue 25. - Moscow: "Centr sistemnykh issledovanii" Publisher, 2004. - 248 p. - (In Russian).

15. Photoblog about fashion and style 2012-2014 [Electronical Resource]. - Available at: http://mens.by/style/shine/470-mustache-sideburns (26 May 2014).

16. Children's Portraits in Black and White [Electronical Resource]. - Available at: http://www.liveinternet.ru / us-ers/katiava/post285466584 (accessed 26 May 2014).

17. Black and White wallpaper [Electronical Resource]. -Available at: http://oboiny.ru/cherno-belye-oboi-dlya-rabo-chego-stola (accessed 26 May 2014).

18. Dalal, N. Histograms of Oriented Gradients for Human Detection / N. Dalal, W. Triggs // IEEE Computer Society Conference on Computer Vision and Pattern Recognition CVPR05. - 2005. - Vol. 1(3). - P. 886-893.

19. Nemirovsky, V.B. Segmentation of color Images of naturel Objects by Recurrent Neural Network / V.B. Nemirovsky, A.K. Stoyanov // Bulletin of the Tomsk Polytechnic University. - 2013. - Vol. 323(1). - P. 212-216. - (In Russian).

NEAR-DUPLICATE IMAGE RECOGNITION BASED ON THE RANK DISTRIBUTION OF THE BRIGHTNESS CLUSTERS CARDINALITY

V.B. Nemirovskiy, A.K. Stoyanov Institute of Cybernetics, National Research Tomsk Polytechnic University

Abstract

In this paper the usage of multi-step segmentation for near-duplicate image recognition is investigated. The clustering of image pixels brightness is used for segmentation. The clustering is realized by means of a recurrent neural network.

The search pattern based on the rank distributions of the brightness clusters cardinality is suggested. Experimental results on the near-duplicate image recognition based on the application of the suggested search pattern are given. It is shown that the use of a multi-step segmentation and rank distributions of the brightness clusters cardinality allows one to successfully recognize the duplicates, which are received by a considerable visual distortion of the original image or by the change of image scale.

Key words: image, pixel, point mapping, recurrent neural network, clustering, segmentation, image recognition, ranking distribution.

Сведения об авторах

Немировский Виктор Борисович, 1945 года рождения, окончил Томский государственный университет в 1967 году, кандидат физико-математических наук, доцент каф. информатики и проектирования систем Института кибернетики Томского политехнического университета. Область научных интересов: нейронные сети, искусственный интеллект, обработка изображений. E-mail: vbn@tpu.ru .

Victor Borisovich Nemirovskiy (b. 1945), graduated from Tomsk State University in 1967, Candidate of Physical and Mathematical Sciences, associate professor of the Informatics and Computer-Aided Design Systems department, Institute of Cybernetics of Tomsk Polytechnic University. Research interests are neural networks, artificial intelligence, image processing.

Стоянов Александр Кириллович, 1946 года рождения, окончил Томский политехнический институт в 1970 году, кандидат технических наук, доцент каф. информатики и проектирования систем Института кибернетики Томского политехнического университета. Область научных интересов: нейронные сети, искусственный интеллект, извлечение знаний из данных, обработка изображений.

E-mail: sto@tpu.ru.

Alexander Kirillovich Stoyanov (b. 1946), graduated from Tomsk Polytechnic Institute in 1970, Candidate of Technical Sciences, associate professor of the Informatics and Computer-Aided Design Systems department, Institute of Cybernetics of Tomsk Polytechnic University. Research interests are neural networks, artificial intelligence, data mining, image processing.

f

Поступила в редакцию 15 июня 2014 г.