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

11. Hansen D.W., Hansen J.P., Nielsen M. Eye typing using Markov and active appearance models. Workshop on applications of computer vision. Orlando, Florida, USA, IEEE Computer Society, 2002, vol. 12, pp. 132-136.

12. Rowley H.A., Baluja S., Kanade T. Neural network-based face detection. Pattern anal. mack intell., 2000, vol. 5, pp. 23-38.

13. LeCun Y., Huang F., Bottou L. Learning Methods for Generic Object Recognition with Invariance to Pose and Lighting. Proceedings of CVPR’04. Washington, DC, USA, IEEE Computer Society, 2004, pp. 97-104.

14. George D., Hawkins J. A hierarchical bayesian model of invariant pattern recognition in the visual cortex. Proceedings. 2005 IEEE International Joint Conference on Neural Networks. Montreal, Canada, IEEE Computer Society, 2005, vol. 3, pp. 1812-1817.

15. Chapelle O., Haffner P., Vapnik V. SVMs for histogram-based image classification. IEEE Trans. Neural Networks. Washington, DC, USA, IEEE Computer Society, 1999, vol. 10, no. 5, pp. 1055-1064.

16. Feraud R., Bernier O., Viallet J., Collobert M. A fast and accurate face detector based on neural networks. Transactions on pat-

tern analysis and machine intelligence, 2002, vol. 3, no. 23, pp. 42-53.

17. Karnowski T., Arel I., Rose D. Deep Spatiotemporal Feature Learning with Application to Image Classification. The 9th International conference on machine learning and applications (IC-MLA’10). Washington, DC, USA, IEEE Computer Society, 2010, pp. 883-888.

18. Yu N., Notkin B.S., Sedov V.A. Neuro-iterative algorithm of tomographic reconstruction of the distributed physical fields in the fibreoptic measuring systems. Computer optics, 2009, vol. 33, no. 4, pp. 446-455.

19. Lai Z., Hongbin G., Ben N. Visual Hand Pose Estimation Based on Hierarchical Temporal Memory in Virtual Reality Cockpit Simulator. Information Technology Journal, 2011, vol. 10, no. 9, pp. 1809-1816.

20. LeCun Y., Kavukcuoglu K., Farabet C. Convolutional Networks and Applications in Vision. International Symposium on Circuits and Systems (ISCAS’10). Paris, IEEE, 2010, pp. 253-256.

УДК 004.932

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

Немировский Виктор Борисович,

канд. физ.-мат. наук, доцент каф. информатики и проектирования систем Института кибернетики Томского политехнического университета, Россия, 634050, г. Томск, пр. Ленина, д. 30. E-mail: vbn@tpu.ru

Стоянов Александр Кириллович,

канд. техн. наук, доцент каф. информатики и проектирования систем Института кибернетики Томского политехнического университета, Россия, 634050, г. Томск, пр. Ленина, д. 30. E-mail: sto@tpu.ru

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

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

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

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

Ключевые слова:

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

Введение

Задача распознавания изображений актуальна для систем технического зрения в робототехнике и иных технических системах; для поиска изобра-

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

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

Ответ на вопрос о схожести двух изображений можно было бы получить, поэлементно сравнивая их по ряду каких-либо параметров. Реализация такого прямого сравнения малоэффективна, что связано с отличиями от оригинала, которые приобретают распознаваемые изображения в процессе получения. Такие отличия приводят к появлению так называемых нечётких дубликатов. В качестве нечётких дубликатов могут пониматься изображения, отличающиеся разрешением или наличием шума, подвергшиеся небольшим фотометрическим преобразованиям; снимки одной и той же сцены, выполненные с небольшими изменениями ракурса камеры; видеокадры одной сцены. Другим случаем проявления нечётких дубликатов является изображение, подвергшееся искажениям. Кроме того, нечёткие дубликаты возникают в результате редактирования изображений и при создании коллажей. К понятию нечёткого дубликата приводит также поиск оригинала изображения по миниатюрной или увеличенной копии [3-11].

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

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

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

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

Процесс получения цифрового изображения включает в себя дискретизацию и квантование яркости [14] исходного аналогового изображения. Гистограмма - это сжатое описание уже квантованного по яркости аналогового изображения, которое и используется в качестве поискового образа. Квантование можно рассматривать как простейшую кластеризацию, приводящую к получению «сегментированного» изображения, где под сегментацией понимается процесс выделения однородных областей на изображении. Особенность такой сегментации в том, что выполняется равномерное квантование всего диапазона яркостей. В этом случае сегментация никак не связана с формой объектов, присутствующих на изображении, а значит, не обеспечивает достаточно успешного распознавания. С другой стороны, применение специальных методов сегментации, основанных на кластеризации, способно дать больше информации об объектах на изображении. Действительно, естественно предположить, что если пиксели выделенных областей изображения близки друг к другу по своим параметрам (входят в один кластер), то они принадлежат одному объекту изображения.

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

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

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

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

Рис. 1. Структура моделируемой нейронной сети

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

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

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

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

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

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

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

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

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

Л*) Ж'- - ♦ г 1

г 1

я я я

А й 1 — — X 1

X,* *2 А В X*

Рис. 2. Диаграмма Ламерея для одномерного отображения значений яркости х* и х3* - устойчивые точки; х{ - неустойчивая точка отображения

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

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

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

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

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

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

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

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

• Расстояние между двумя точками l и p должно быть тождественным, то есть dlp=dpl.

• Для расстояний между тремя точками l, p и к должно соблюдаться правило треугольника, то есть d№+dkp>dlp.

• Расстояние между двумя точками l и p должно быть положительным, то есть dlp>0, причём dlp=0, только если l совпадает с p.

Наиболее часто в метрическом пространстве используется евклидово расстояние

d. =

ip

$

где хн, хр - !-е координаты точек I ир, соответственно.

Мера близости между двумя векторами (то есть изображениями) в п-мерном векторном пространстве может быть задана в виде угла. Если заданы вектор входного изображения Б^в^,...^,,) и вектор изображения-оригинала Х=(х!,х2,.,хп), то близость векторов определяется выражением

d = arccos

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

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

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

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

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

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

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

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

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

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

н = -Ха1о&а •

I

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

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

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

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

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

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

Для целей распознавания важно иметь не

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

а б

Рис. 4. Изображения объектов, полностью не совпадающих с эталоннным: а) лицо мальчика [20]; б) пейзаж [21]

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

Количественная оценка близости ранговых распределений, представленных на рис. 5, а, приведена в таблице. Расстояния вычислялись как для раногового распределения мощности кластеров, так и для гистограмм. Определение этих расстояний выполнено из тех соображений, что, как отмечалось ранее, использование гистограмм для сравнения двух изображений до сих пор является популярным методом [22, 23]. Из таблицы видно, что вычисленные расстояния значительно превышают установленный порог близости й=0,15. При этом расстояние, вычисленное по ранговым распределениям, показывает большее различие изображений, чем при использовании гистограмм. Иными словами, качество распознавания изображения по мощности кластеров выше.

Графики, отражающие количественную оцен-

6 9

Ранг кластера

12

15

0,3

СЗ

00,2 н ’

и

о0 1 « а

о

1 \ Л — Ориї -Ради --Ради инал гс иска: ІС иска: кений 6 кений 1 пике. 4 пике.

V \ 1 Л

ч \ ч X. ч V \ ^ 'Л V- г  1 / / г

0 3 6 9 12

Ранг кластера

15

0

а б

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

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

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

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

Эталон -лицо мужчины Лицо мальчика Без искажения 0,764 0,560

Пейзаж Без искажения 0,482 0,459

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

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

Для наглядности на рис. 7 показан и график рас-

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

0 4 8 12 16

Радиус искажения

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

0 4 8 12 16

Радиус искажения

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

Выводы

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход. - М.: Изд-во «Вильямс», 2004. - 928 с.

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

3. An Evaluation of Popular Copy-Move Forgery Detection Approaches / V. Christlein, J. Jordan, C. Riess, E. Angelopoulou // IEEE Transactions on information forensics and security. -

2012.- V. 7. - Iss. 6. - P. 1841-1854.

4. Farid H. Image Forgery Detection // IEEE Signal processing magazine. - 2009. - V. 26. -№ 2. - P. 16-25.

5. Fridrich J., Soukal D. Detection of copy-move forgery in digital images // Proceedings of Digital Forensic Research Workshop. -Cleveland, 2003. - P. 55-61.

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

7. Глумов Н.И., Кузнецов А.В., Мясников В.В. Поиск дубликатов на цифровых изображениях // Компьютерная Оптика. -

2013. - Т. 37. - №3. - С. 360-368.

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

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

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

11. Добров Г.Б., Пятков Е.А. Алгоритм поиска нечётких дубликатов на основе простых признаков // Труды РОМИП 2009. -СПб.: НУ ЦСИ, 2009. - С. 78-82.

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

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

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

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

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

14. Гонсалес Р., Вудс Р. Цифровая обработка изображений. - М.: Техносфера, 2005. - 1072 с.

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

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

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

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

19. Фотоблог о моде и стиле 2012-2014. URL: http://fashion2012. ru/muzhskie-borodyi-foto.html (дата обращения: 12.03.2014).

20. Детские портреты в ч/б. URL: http://www.liveinternet.ru/us-ers/katiava/post285466584 (дата обращения: 26.02.2014).

21. Черно-белые обои для рабочего стола. URL: http://oboi-ny.ru/cherno-belye-oboi-dlya-rabochego-stola (дата обращения: 26.02.2014).

22. Ioannidis Y. The History of Histograms (abridged) // Proceedings of XXIX International Conference on Very Large Data Bases. -Berlin, Germany, September 9-12, 2003. - P. 19-30.

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

Поступила 18.03.2014 г.

UDC 004.932

APPLICATION OF MULTI-STEP IMAGE SEGMENTATION FOR NEAR-DUPLICATE IMAGE RECOGNITION

Victor B. Nemirovskiy,

Cand. Sc., Tomsk Polytechnic University, 30, Lenin Avenue, Tomsk, 634050,

Russia. E-mail: vbn@tpu.ru

Alexander K. Stoyanov,

Cand. Sc., Tomsk Polytechnic University, 30, Lenin Avenue, Tomsk, 634050, Russia. E-mail: sto@tpu.ru

The urgency of the paper is caused by the need to detect image near-duplicate in computer vision systems, as well as when image searching on Internet or in large digital archives.

The main aim of the study: usage of multi-step segmentation for near-duplicate image recognition.

The methods used in the study: clustering of image pixels brightness is used for segmentation. The recurrent neural network is used for clustering. To estimate images similarity the authors have applied the cosine distance between rank distributions of clusters cardinality. The results: The authors suggested the search patterns based on the rank distributions of brightness clusters cardinality. The paper introduces the experimental results on the near-duplicate image recognition based on application of the suggested search patterns. It is shown that the use of a multi-step segmentation and rank distribution of the brightness clusters cardinality allows determining reliably the near-duplicate of the original image with a high degree of distortion on them, up to the radius of the Gaussian distortion equal 8 pixels. Such an approach also allows solving reliably the inverse problem of detecting the original image even in its fivefold reduced copy with radius Gaussian distortion on it to 8 pixels.

Key words:

Image, pixel, point mapping, recurrent neural network, clustering, segmentation, recognition of images, ranking distribution.

REFERENCES

1. Forsyth D.A., Ponce J. Computer Vision, a Modern Approach. Moscow, Prentice Hall, 2003. 693 p.

2. Shapiro L.G., Stockman G.C. Computer vision. Moscow, Prentice Hall, 2001. 580 p.

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

4. Farid H. Image Forgery Detection. IEEE Signal processing magazine, 2009, vol. 26, no. 2, pp. 16-25.

5. Fridrich J., Soukal D. Detection of copy-move forgery in digital images. Proceedings of Digital Forensic Research Workshop. Cleveland, 2003. pp. 55-61.

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

7. Glumov N.I., Kuznetsov A.V., Myasnikov V.V. Poisk dublikatov na tsifrovykh izobrazheniyakh [The Algorithm for Copy-move Detection on Digital Images]. Kompyuternaya optika - Computer optics, 2013, vol. 37, no. 3, pp. 360-368.

8. Kuznetsov A.V., Myasnikov V.V. Algoritm obnaruzheniya dubli-katov na tsifrovykh izobrazheniyakh s ispolzovaniem effektiv-nykh lineynykh lokalnykh priznakov [Efficient Linear Local Features Based Copy-Move Detection Algorithm]. Kompyuternaya optika - Computer optics, 2013, vol. 37, no. 4, pp. 489-496.

9. Pimenov V.Yu. Metod poiska nechetkikh dublikatov izobrazheniy na osnove vyyavleniya tochechnykh osobennostey [Near-Duplicate Image Detection with Local Interest Point Extraction]. Trudy ROMIP 2007-2008 [Proc. ROMIP 2007-2008]. Saint Petersburg, NU TCSI, 2008. pp. 145-158.

10. Melnichenko A., Goncharov A. Metody poiska izobrazheniy po vi-zualnomu podobiyu i detektsii nechetkikh dublikatov izobrazhe-niy [Image retrieval methods by the visual similarity and the de-

tection of near-duplicate image]. Trudy ROMIP 2009 [Proc. ROMIP 2009]. Saint Petersburg, NU TCSI, 2009. pp. 108-121.

11. Dobrov G.B., Pyatkov E.A. Algoritm poiska nechetkikh dublika-tov na osnove prostykh priznakov [Near duplicates detection algorithm based on simple features]. Trudy ROMIP 2009 [Proc. ROMIP 2009]. Saint Petersburg, NU TCSI, 2009. pp. 78-82.

12. Baygarova N.S., Bukhshtab Yu.A., Evteeva N.N., Koryagin D.A. Nekotorye podkhody k organizatsii soderzhatelnogo poiska izobrazheniy i videoinformatsii. Institut pricladnoy matematiki im. M. V. Keldysha RAN [Various Questions Connected with Content-Based Search of Visual Information and Videoinformation Preprint, Inst. Appl. Math., the Russian Academy of Science, no. 78]. Available at: http://www.keldysh.ru/papers/2002/prep78/ prep2002_78.html (accessed 12 March 2014).

13. Kotov V.V. Ispolzovanie gistogrammnykh otsenok v zadachakh raspoznavaniya [Use of histogram estimates in recognition tasks]. Uspekhi sovremennogo estestvoznaniya, 2004, no. 4, pp. 40-42. Available at: http://www.rae.ru/use/? section= con-tent&op=show_article&article_id=7780895 (accessed 12 March 2014).

14. Gonzalez R., Woods R. Digital Image Processing. Moscow, Prentice Hall, 2002. 1072 p.

15. Nemirovsky V.B., Stoyanov A.K. Segmentatsiya izobrazheniy s pomoshchyu rekurrentnoy neyronnoy seti [Image Segmentation by Recurrent Neural Network]. Bulletin of the Tomsk Polytechnic University, 2012. vol. 321, no. 5, pp. 205-210.

16. Nemirovsky V.B., Stoyanov A.K. Multi-Step Segmentation of Images by Means of a Recurrent Neural Network. Proc. VII International Forum on Strategic Technology (IF0ST-2012). Tomsk, September 18-21, 2012. Tomsk, TPU Press, 2012. Vol. 1, pp. 557-560.

17. Stoyanov A.K. Primenenie rekurrentnoy neyronnoy seti dlya resheniya zadachi klasterizatsii [Application of recurrent neural network for clustering problem solution]. Bulletin of the Tomsk Polytechnic University, 2009, vol. 315, no. 5, pp. 144-149.

18. Kudrin B.I. Matematika tsenozov: vidovoe, rangovidovoe, rango-voe po parametru giperbolicheskie N-raspredeleniia i zakony Lot-ki, Tsipfa, Pareto, Mandelbrota. Tekhnogennaia samoorganizatsi-ya [Mathematics of cenoses: species, the rank of species, ranking in the parameter hyperbolic H-distribution and the laws of Lotka, Zipf, Pareto, Mandelbrot]. Tsenologicheskie issledovaniya. Moscow, Tsentr sistemnykh issledovaniy, Iss. 25, 2004. 248 p.

19. Fotoblog o mode i stile 2012-2014 [Photoblog about fashion and style 2012-2014]. Available at: http://fashion2012.ru/muzh-skie-borodyi-foto.html (12 March 2014).

20. Detskieportrety v ch/b [Children’s Portraits in Black and White].

Available at: http://www.liveinternet.ru/users/katiava/

post285466584 (accessed 26 February 2014).

21. Cherno-belye oboi dlya rabochego stola [Black and white wallpaper]. Available at: http://oboiny.ru/cherno-belye-oboi-dlya-ra-bochego-stola (accessed 26 February 2014).

22. Ioannidis Y. The History of Histograms (abridged). Proc. XXIX International Conference on Very Large Data Bases. Berlin, Germany, September 9-12, 2003. pp. 19-30.

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