Генетические алгоритмы, основанные на сжатии изображений.
Резюме. В данном документе мы анализируем проблему сжатия изображений с использованием генетических кластеризующих алгоритмов, опирающихся на пиксели изображения.
Главная проблема при решении - найти алгоритм, рационально выполняющий кластеризацию.
В настоящее время возможность решения проблемы кластеризации с помощью ГА находится в процессе изучения.
В этой статье мы использовали ГА для получения формализованного представления изображения, а затем выполнили кластеризацию для реализации сжатия.
Помня об этой цели, мы разработали различные методы кластеризации для применения к формализованному представлению (репрезентативной выборке).
Ключевые слова: Генетический алгоритм, сжатие изображений.
1 вступление
Мы можем разделить алгоритмы кластеризации на две категории: конструктивные и итеративные алгоритмы.
В конструктивных методах объект задается различными кластерами, которые устанавливаются при разработке полного возможного решения из частичных (частных) решений.
В итеративных методах первоначальное полное решение всегда возможно и единственно, попытки улучшить это решение разными путями от одной итерации к другой.
Данной категории принадлежат такие популярные алгоритмы кластеризации как К-методы.
Наша работа основывается на статье Бхуяна.
Этот автор рассматривал проблему разбиения N объектов на M непересекающихся кластеров с использованием ГА для получения адекватной перестановке объектов.
В данной работе мы исследовали решение проблемы кластеризации основанной на ГА, в которой мы искали оптимум решения одновременно (совместно) учитывая и манипулируя множеством возможных решений (популяций).
Что создает альтернативный классическому метод.
Мы определили фитнес-функцию (ФФ), минимизирующую неупорядоченность среди сортируемых нами элементов.
В этом случае мы не смешивали фитнес расчеты с процедурой кластеризации.
Мы применили кластеризацию как последний шаг алгоритма, когда упорядоченное представление уже было получено.
Соответственно результатам, полученным в нашем эксперименте, мы считаем, что решение ГА проблемы кластеризации очень многообещающая.
2 описание ГА
ГА используются для получения упорядоченной последовательности элементов и основываются на алгоритмах, описанных в (источнике 1).
2.1. Целевая функция. (ЦФ)
В данной работе мы не рассматривали кластеризацию в ЦФ.
Мы претендуем на получение упорядоченной последовательности элементов с помощью ГА, так что мы планируем минимизировать беспорядочность в них.
В порядке достижения этого мы предлагаем нижеследующее.
Заданная упорядоченная последовательность элементов X=[Xi]
N упорядоченных элементов, где каждый элемент вектора это другой вектор, содержащий p байт.
ЦФ описывается следующим образом:
F(Xi)=SUMi=1 to N-1( dist(xi, xi+1) ).
Где dist(xi, xi+1)= SUMj=1 to p( xi,j, xi+1,j )2
Проблема заключается в том, чтобы минимизировать F - интервал сумм от одного элемента последовательности к следующему.
2.2 кластеризация последовательности решений
Упорядоченная последовательность.
В данной работе мы использовали сортированную последовательность для представления решений.
В этом представлении каждая часть представляет собой перестановку объектов. Данный тип сортированного набора предоставляет информацию о сходных элементах среди объектов, непосредственно заданных оптимальными кластерами.
Например, предположим, что имеется хромосомный набор объектов от 1 до 6, расположенных с.о. (2 3 5 1 6 4).
Мы предполагаем, что в перестановке, которая ведется для оптимизации решения, сходные объекты расположены один возле другого.
Основываясь на этой гипотезе, порядок (2 3 5 1 6 4) показывает, что 2 более похоже на 3, чем на 5, и 5 не может быть включена в один кластер с 2 без включения туда же и 3.
В частном случае разделения N объектов на M кластеров предполагает, что (O1, O2, ..., ON)
это особое размещение N объектов.
Значит каждый кластер содержится в интервале объектов (Oi, Oi+1, ..., Oj)
где 1<=i j<=N. В связи с этим количество различных возможных кластеров составляет 0.5*N*(N+1).
2.3. Начальные конструкторы популяций.
В работе [1] автор изучает три различных конструктора популяций для кластеризующих алгоритмов, основанных на ГА,
Для простоты они названы А, B и C.
Конструктор А помещает объект в сортированный список случайным образом.
Использование этой стратегии для получения начальной популяции позволяет тестировать ГА в большинстве неблагоприятных обстоятельств.
ГА совершенно грубы для областей хорошего качества в искомом пространстве (переборе областей).
Конструктор B использует эвристические алгоритмы, основанные на минимизации расстояния между двумя объектами.
Он генерирует метку (маркер) объекта случайным образом и помещает ее на первую позицию сортированного списка.
Затем он перебирает все объекты, отсутствующие в упорядоченном списке, и ищет среди них ближайший к совсем недавно добавленному в список.
Конструктор повторяет процедуру до тех пор пока все объекты не будут включены в отсортированный список.
Конструктор С использует "жадный" и вероятностный эвристический агоритм для формирования (построения, создания) начальной популяции.
Первичный замысел в данном конструкторе заключается в сбалансировании знаний о проблеме с беспорядочностью (случайным характером).
Различие между этим конструктором и конструктором В в пути нахождения ближайшего объекта к совсем недавно добавленному в сортированный список.
Этот конструктор вместо поиска среди всех объектов, которые не включены в список, ищет только К объектов, где К является константой.
ВременнАя сложность в данном случае значительно сокращается.
В данной работе мы собираемся использовать С конструктор, в котором мы позволяем пользователю вводить значение параметра К.
3 Заключение
Основываясь на результатах, полученных и детализированных в предыдущем разделе, мы утверждаем следующее:
*ГА п.с. мощный инструмент, который может иметь успех в построении алгоритмов кластеризации;
*Среди методов, предлагаемых для кластеризации, локальная настройка и динамическая кластеризация с переменными кластерами являются наилучшими.
*Назло элементарности, фиксированный метод кластеризации порождает приемлемые результаты. Как бы то ни было, мы не рекомендуем его использование (утилизацию), потому что это может быть сильно (широко) усовершенствовано локальной настройкой почти без увеличения временных затрат.
Метод локальной настройки выглядит наилучшим, когда мы фиксируем количество кластеров. Как мы ранее упоминали, этот метод улучшает в заслуживающем внимания методе фиксированной кластеризации производительность. Мы думаем, что адекватное значение параметра R должно находиться между 50 и 100. Ниже этих значений, данное действие не так значительно, а выше них мы не получили дальнейших улучшений. Это может быть объяснено тем, что при концепции фиксированного количества кластеров изображение не может быть улучшено далее некоторого предела. Поэтому, когда в одном цикле нет изменений, нет смысла продолжать применение метода, потому что был достигнут указанный предел.
Динамическая кластеризация с фиксированными кластерами не дает хороших результатов. В большинстве случаев результаты, полученные данным методом будут хуже, чем полученные методом фикс. Кластеризации.
|