РАЗРАБОТКА РАСПРЕДЕЛЕННОЙ СИСТЕМЫ ПОИСКА ИЗОБРАЖЕНИЙ ПО СОДЕРЖАНИЮ

1 Iteratoal Scetfc Coferece Proceedgs, Volue 2 Advaced Iforato Techologes ad Scetfc Coputg PIT 205 Е.А. Трофимов РАЗРАБОТКА РАСПРЕДЕЛЕННОЙ СИСТЕМЫ ПОИСКА ИЗОБРАЖЕНИЙ ПО СОДЕРЖАНИЮ (Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)) Исследования в области поиска изображений по содержанию стали актуальны в последние десятилетия, в связи с ростом емкости доступных накопителей данных и широким распространением цифровой фотографии, и, как следствие, ростом числа и объемов коллекций изображений. Поиск по содержанию (Cotet Based Iage Retreval, CBIR) является приоритетным подходом к решению задачи поиска изображений. Методы поиска по содержанию работают на основе анализа численных характеристик составляющих изображение пикселей и не требуют наличия текстовых аннотаций или другой дополнительной информации об изображении. Это позволяет избежать трудоемкости и субъективности составленных вручную аннотаций, неточности аннотаций, полученных автоматически или полуавтоматически. От систем поиска изображений по содержанию требуется высокая скорость работы, для обеспечения которой может быть применена модель организации распределенных вычислений MapReduce. Технология MapReduce обеспечивает высокую горизонтальную масштабируемость и отказоустойчивость, также для организации кластера не требуется дорогостоящего оборудования. В данной работе используется программный комплекс Hadoop, разработанный фондом Apache Foudato. Рис.. Схема системы поиска изображений по содержанию Система для поиска изображений состоит из нескольких частей:. Модуль формирования признаков изображений. 2. Модуль расчета дистанций между гистограммами распределения признаков. 3. Поиск наиболее похожих изображений на основе рассчитанных дистанций.. Формирование гистограмм признаков Классическим способом задания зависимости между пикселями изображения заключается в представлении каждого пикселя как отдельного столбца 37

2 Труды Международной научно-технической конференции, Том 2 «Перспективные информационные технологии» ПИТ 205 многомерной гистограммы, описываемого многомерным вектором l, содержащим пространственные координаты столбца и положительным числом w значением признака для столбца. Такой подход имеет несколько недостатков. Первый состоит в том, что большинство признаков, описывающих содержание изображения, такие как форма и текстура определяются для всего изображения, а не для его пикселей в отдельности. Для отдельного пикселя можно определить его цвет, другие признаки, описывающие содержание изображения определить проблематично. Второй недостаток подхода один пиксель один столбец заключается в порождении огромного числа столбцов. К примеру, для изображения размеров 600 на 800 пикселей гистограмма будет содержать столбцов. Вместо разделения изображения на пиксели будим делить изображение на несколько частей и примем каждую часть за столбец гистограммы. Тогда сформированный признак для каждой части изображения будет представлен столбцом многомерной гистограммы, который описывается многомерным вектором l, содержащим пространственные координаты столбца и значением признака для столбца w. При таком разделении число столбцов будет значительно меньше и его можно регулировать, задавая параметр разделения. При решении реальных задач, множество изображений среди которых будет осуществляться поиск, может насчитывать сотни тысяч изображений. Таким образом, требуется обеспечить высокую скорость формирования признаков. Этого можно добиться за счет параллельной обработки изображений. В качестве метода параллельной обработки данных применяется подход MapReduсe, обеспечивающий высокую горизонтальную масштабируемость и низкие минимальные требования к отдельным узлам кластера. Для распараллеливания процесса формирования признаков используется метод распараллеливания по данным. Рис. 2. Схема параллельного формирования признаков Здесь apper в качестве ключа использует идентификатор изображения, в качестве значения - данные изображения. Mapper производит процесс формирования признаков. Reducer имеет в качестве ключа имя признака, а в качестве значения - идентификатор изображения и гистограмму. Также он производит запись полученной гистограммы для заданного признака в файл. Таким образом, в результате будем иметь множество файлов, в каждом из которых будут 38

3 Iteratoal Scetfc Coferece Proceedgs, Volue 2 Advaced Iforato Techologes ad Scetfc Coputg PIT 205 содержаться гистограммы определенного признака для каждого из исходных изображений. 2. Расчет дистанций между гистограммами признаков В качестве дистанции между двумя гистограммами используется метрика earth over s dstace. Earth s over dstace метрика, основанная на минимальной стоимости перехода одной гистограммы в другую. Если представить два распределения, одно как массу земли которую нужно распределить, другое как набор отверстий. Тогда EMD определяет наименьшее количество работы, необходимое для заполнение отверстий землей. Вычисление EMD базируется на решении транспортной задачи линейного программирования, для решения которой существуют эффективные алгоритмы. Предположим, что несколько поставщиков каждый с заданным количеством товаров должны поставить его нескольким потребителям, каждый с ограниченной пропускной способностью. Для каждой пары поставщикпотребитель задана стоимость транспортировки единицы товара. Тогда транспортную задачу можно сформулировать как поиск наименее дорогого потока товаров отвечающих запросам потребителей. Сравнение гистограмм легко сводится к транспортной задаче, если обозначить одну гистограмму, как поставщика и другую, как потребителей. Этот процесс можно понимать, как поиск минимальной работы, необходимой для превращения одной гистограммы в другую. Сформулируем задачу линейного программирования: пусть P= - первая гистограмма из столбцов, p - столбец, wp - вес столбца. Q= - вторая гистограмма из столбцов. D = [ d ] - матрица, где - d стоимость перехода единичного значения из столбца p в столбец q. Тогда нужно найти поток F = [ f ], где f - поток между p и q j, минимизирующий общую стоимость = j= f 0, j j= = f f w w p q j j f = ( wp, ) wq j = j= = j=, d f 39, отвечающий ограничениям Ограничение () позволяет передвигаться поставщикам от P к Q и наоборот. Ограничение (2) ограничивает суммарные поставки, которые могут быть посланы в P их весом. Ограничение (3) ограничивает Q от приема количества поставок большего чем их вес. Ограничение (4) определяет максимальное суммарное число возможных поставок суммарный поток. Решив транспортную

4 Труды Международной научно-технической конференции, Том 2 «Перспективные информационные технологии» ПИТ 205 задачу, найдем оптимальный поток F, тогда EMD определена как работа, нормализованная по суммарному потоку: EMD( P, Q) = d f = j= f = j=. Для параллельного вычисления EMD применяется распараллеливание по данным. На вход apper в качестве ключа принимает одно из изображений исходного множества, в качестве значения изображение, похожие на которое требуется отыскать. Mapper вычисляет EMD между изображением-ключом и изображением-значением. Reducer в качестве ключа принимает одно из изображений исходного множества, а в качестве значения, вычисленное для ключа EMD. Также reducer производит запись в выходной файл вычисленной дистанции EMD и изображений, для которых она была вычислена. 3. Поиск изображений по содержанию После формирования признаков и вычисления дистанции между исходными изображениями и изображением для поиска, наиболее схожие изображения находятся путем выбора наименьших дистанций. Для примера, проведем эксперимент с поиском изображений, используя признак gabor flter. Исходный набор насчитывает 500 изображений. Рис. 3. Пример работы системы поиска изображений 40

5 Iteratoal Scetfc Coferece Proceedgs, Volue 2 Advaced Iforato Techologes ad Scetfc Coputg PIT 205 Разработанная программная система нашла наиболее схожие изображения, основываясь на текстурном признаке gabor flter. Для вычисления признака изображения делилось на 8 частей. Такое разделение выбрано для сохранения текстуры в каждой из частей изображения. В данной работе была описана система для распределенного поиска изображений по содержанию. Программный комплекс дает возможность быстро осуществлять поиск изображений и легко масштабировать вычислительный кластер при возрастающей нагрузке. Литература. Jeffrey Dea, Sajay Gheawat. MapReduce: Splfed Data Processg o Large Clusters Degshe Zhag, Aylw Wog, Mara Idrawa, ad Guoju Lu, Cotetbased Iage Retreval Usg Gabor Texture Features Y. Ruber, C. Toas, L. J. Gubas, The earth over s dstace as a etrc for age retreval. Iteratoal Joural of Coputer Vso, vol. 40, 2000, pp Degsheg Zhag, Aylw Wog, Mara Idrawa, Guoju Lu. Cotetbased Iage Retreval Usg Gabor Texture Features Д.В. Филимонов РЕАЛИЗАЦИЯ МЕТОДА ОКРЕСТНОСТЕЙ НА ОТЛАДОЧНОМ ОБОРУДОВАНИИ TEXAS INSTRUMENTS CC2520 DEVELOPMENT KIT (Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)) Введение В настоящее время беспроводные технологии приобретают особую популярность при решении задач распределённого сбора информации и дистанционного управления. Для решения подобных задач используются беспроводные сенсорные сети. Беспроводные сенсорные сети это набор автономных устройств для совместного контроля физических и экологических параметров в местах их установки, соединенных между собой беспроводным каналом связи. Уровень доступа к среде и физический уровень передачи данных в среде распространения определены стандартом IEEE Данный тип сетей характеризуется низким энергопотреблением устройств, высокой масштабируемостью и возможностью самоорганизации []. Радиус покрытия устройств сети зависит в первую очередь от чувствительности приемника и мощности передатчика, для увеличения зоны покрытия используются промежуточные узлы (ретрансляторы). Задачей протоколов 4

Труды Международной научно-технической конференции, Том 2 «Перспективные информационные технологии» ПИТ 205 САПР паспортов дорог WayMark призвана дать проектировщику возможность создавать схемы дислокации