Размещено на http://www.allbest.ru/

УДК 004.75

Казахский национальный университет имени аль-Фараби, механико-математический факультет, Казахстан, г. Алматы

Параллельные алгоритмы обработки изображений дистанционного зондирования

Темирбекова Ж.Е.

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

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

Алгоритм -means

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

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

-means минимизирует расстояния между объектами в кластерах. Минимизируемая функция в случае -means такова: объект кластеризации - центр кластера.

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

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

1. Итеративное перераспределение объектов по кластерам. Объекты распределяются по кластерам путем подсчета расстояния от объекта до центров кластеров и выбора наименьшего.

2. Когда все объекты распределены по кластерам, заново считаются их центры.

3. Если , то это означает, что кластерные центры стабилизировались и соответственно распределение закончено. Иначе переходим к шагу 1

Распараллеливание -means алгоритм

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

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

MPI является стандартным параллельным программированием на основе передачи сообщении, функция заключается в обмене информацией. MPI программы содержат "mpi.h" заголовок файла, а затем завершения инициализации программы MPI_Init (), после этого устанавливается структура топологии и новый коммуникатор затем, вызывается функция и приложения, которые будут использоваться для каждого процесса, в конце используется MPI_Finalize (), чтобы завершить работу каждого процесса.

Параллельный программный дизайн процесс обмен сообщениями показано на рис. 1.

рис. 1. Процесс обмен сообщениями

Я собираюсь реализовать параллельный -means алгоритм, основанный на MPI, называется means. Прежде чем представить means алгоритм, сначала хочу кратко описать means (Sequential -means) алгоритм, потому что means состоит из means и MPI.

Алгоритм means.

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

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

Алгоритм means:

Input: число кластеров, число объектов данных

Output: центроиды

1: Чтение объектов из файла;

2: Случайно выбрать точек в качестве начальных центроидов, обозначается как ;

3: Вычислить в формуле , обозначим через ;

4: Назначение каждого объекта до ближайшего кластера;

5: Вычислить новый центр тяжести каждого кластера в формуле

;

6: Пересчитать в формуле

;

7: Повторять шаги 3-6, пока - <порог (- <threshold);

8: Вывод результатов кластеризации: центроидов;

Алгоритм means

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

В нашем алгоритме means, параллелизм реализуется на параллелизм данных. Параллельная обработка в means согласуется из means. Данные объекты равномерно распределяются во всех процессах и кластерные центроиды реплицируются. Глобальные операции для всех кластерных центроидов выполняется в конце каждой итерации с целью создания новых центров тяжести кластеров. И, наконец, вывод результатов кластеризации: центроиды, I / O времени и времени кластеризации.

Алгоритм means:

Input: число кластеров, число объектов данных

Output: центроиды

1: MPI_Init / / начало процедуры;

2: Чтение объектов из файла;

3: Раздел объектов данных равномерно между всех процессах, и предположим, что каждый процесс имеет объектам данных;

4: Для каждого процесса, выполнить 5-11 шаги;

5: Случайно выбрать точек в качестве начальных центроидов кластера, обозначаемая как ;

6: Рассчитать в формуле , обозначается как ;

7: Назначение каждого объекта до ближайшего кластера;

8: Вычислить новый центр тяжести для каждого кластеру в

;

9: Пересчитать в ;

10: Повторит шаги 6-9, пока - <порог (- <threshold);

11: Создание кластера идентификатор для каждого объекта данных;

12: Создание новых центров тяжести кластеров в зависимости от результатов кластеризации всех процессов в конце каждой итерации;

13: Создание окончательной набор тяжести по функциям слияния и выводить кластеризации. Результат: центроидов;

14: MPI_Finalize / / завершения процедуры;

Слияние функций (Merge Function)

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

Input: тяжести наборы из в ( центроиды)

Output: центр тяжести ( центроиды)

1: Инициализация тяжести набора как пустые;

2: Если центр тяжести множества пусто, выхода и окончательное тяжести множества , в противном случае, перейти к шагу 3;

3: Найти вектор центроиды с минимальным внутренним расстоянием, которое определяется как в (3), а затем удалить из , кроме того, добавить в . Перейти к шагу 2;

4: Вывод центроидов;

Функция слияния(Merge Function) целью является найти вектор центроидов с минимальным внутренним расстоянием. Кроме того, евклидовое расстояние используется для расчета внутренней расстоянии, обозначается как Distance. В , происходит от тяжести множества и центра тяжести.

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

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

-means кластеризации в MapReduce

MapReduce является моделью программирования и связанного реализации для обработки и генерации больших наборов данных. Типичный MapReduce вычислительных процессов многие терабайты данных на тысячи машин. MapReduce обычно разбивает входной набор данных на независимые части. Количество частей зависит от размеров набора данных и количество доступных узлов. Пользователи указывают карта функции, которая обрабатывает (ключ, значение) пара для создания набора промежуточных (ключ, значение), а также снижение функции, которая объединяет все промежуточные значения, связанные с той же промежуточной ключ. MapReduce лучше всего подходит для обработки больших наборов данных и поэтому идеально подходит для кластеризации -means алгоритмов.

Алгоритм работает итеративно в несколько этапов, в следующем образом:

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

2. Каждый Mapper создает начальной кластеров из этих вспомогательных кластеров, которые затем направляются в Reducer.

3.Reduce объединяет кластеры от каждого Mapper и пересчитывает центроидов всех кластеров.

4. Эти центры тяжести в настоящее время таким образом возвращаются к первоначальному Mapper по трансляции операций.

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

6. Reducer снова объединяет кластеры и пересчитывает центроиды.

7. Эта процедура повторяется до тех пор пока Reducer решает остановить повторную данных Mapper . Это обычно происходит, когда алгоритм сходится.

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

Литература

1. Дж. Ту, Р. Гонсалес Принципы распознавания образов. - стр.110-112.Москва, 1978г.

2. Кашкин В.Б., Сухинин А.И. Дистанционное зондирование Земли из космоса. Цифровая обработка изображений: Учебное пособие. - М.: Логос, 264 с 2001г.

3. В.В. Сергеев Анализ и обработка изображений, получаемых при наблюдениях земли из космоса// Стенограмма научного сообщения на совместном семинаре ИСОИ РАН и Института компьютерных исследований СГАУ 18 апреля 2006 года.

4. К. В. Воронцов Лекции по алгоритмам кластеризации и многомерного шкалирования 21 декабря 2007 года.

5. Р. Миллер, Л. Боксер Последовательные и параллельные алгоритмы. Издательство: Бином. Лаборатория знаний 408стр, 2006г.

6. Khaled Alsabti, Sanjay Ranka and Vineet Singh. An efficient k-means clustering algorithm. In HPDM, 1998.

7. Antonio J. Plaza Parallel techniques for information extraction from hyperspectral imagery using heterogeneous networks of workstations / 2007.

8. Grace Nila Ramamoorthy. K-means Clustering Using Hadoop MapReduce// Final Project Report, University College Dublin, September 16. 2011.

9. R.C.Dubes and A.K. Jain. Algorithms for Clustering Data. Prentice Hall, 1988

10. M. Armbrust, I. Stoica, M. Zaharia, A. Fox, R. Griffith, A. Joseph, R. Katz, A. Konwinsli, G. Lee, D. Patterson, A. Rabkin, “A view of cloud computing,” Communications of

the ACM, vol. 53, no. 4, pp. 50-58, April 2010.

11. W. Zhao, H. Ma, Q. He, “Parallel K-Means Clustering Based on MapReduce,” Cloud Computing, vol. 5931, pp. 674-679, 2009.

12. S. Kantabutra, A. Couch,“Parallel K-means Clustering Algorithm on NOWs,” Technical Journal, vol. 1, no. 6, 2000.

13. D. Arthur, S. Vassilvitskii, “k-means++: the advantages of careful seeding,” Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1027-1035, 2007.

14. R. Amorim, B. Mirkin, “Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering,” Pattern Recognition, vol. 45, no. 3, pp. 1061-1075, 2012.

15. A. Jain, “Data clustering: 50 years beyond K-means,” Pattern Recognition Letters, vol. 31, no. 8, pp. 651-666, June 2010.

Размещено на Allbest.ru