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

• Название: Реализация простейших алгоритмов кластеризации в задачах технического зрения
• Анкор: fdgfd
• Дата: 21.02.2023
• Размер: 16.52 Kb.
• Имя файла: lr_claster.docx
• Тип: Задача; #948375

1. Реализация простейших алгоритмов кластеризации в задачах технического зрения

Задание:

На любом языке программирования выполнить приведение количества цветов изображения  к  заданному методом k-средних (k-means). Метод реализовать самостоятельно.
Теория:
Целью задачи кластеризации является разбиение множества объектов на классы (кластеры) на основе некоторой меры сходства объектов. При кластеризации цветов мерой сходства является близость яркостей пикселей, которую будем оценивать с помощью следующей функции:

f_i = 30*(R_i-R₀)²+59*(G_i-G₀)²+11*(B_i-B₀)².

Множители 30, 59 и 11 - отражают различную чувствительность человеческого глаза к красному, зеленому и синему цветам соответственно.
Мы будем пытаться разбить палитру на N=k кластеров и заменить цвета попавшие в какой-либо кластер центром этого кластера. Стандартным методом решения такой задачи является метод k-средних.
Алгоритм метода k-средних

Пусть имеем набор векторов x_i (i=1p) и k – число кластеров, на которые нужно разбить набор x_i. Суть алгоритма заключается в том, чтобы найти k средних m_j (j=1k) (центров кластеров) и отнести каждый из векторов x_i к одному из k кластеров.

1. 
   Случайным образом выбрать k центров m_j (j=1k);
   
2. 
   Для каждого x_i (i=1p подсчитать расстояние до каждого из m_j (j=1k);
   Отнести (приписать) x_i к кластеру j расстояние до центра которого m_j минимально. (Расстояние между цветами предлагается вычислять по формуле различия цветов, приведенной выше).
   
3. 
   Пересчитать центры кластеров m_j (j=1k) по всем кластерам;
   
4. 
   Повторять шаги 2, 3 пока кластеры не перестанут изменяться;
   

Пример

Пусть имеем 10 точек: 7 5 6 9 11 15 56 45 27 20. Необходимо разбить из на 3 кластера.

Выберем 3 центра кластера случайным образом: 6 9 15.

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

Центр кластера	6	9	15
Точки кластера	5 6 7	9 11	15 20 27 45 56
Новые центры кластеров	6	10	33

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

Центр кластера	6	10	33
Точки кластера	5 6 7	9 11 15 20	27 45 56
Новые центры кластеров	6	14	43

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

Центр кластера	6	14	43
Точки кластера	5 6 7 9	11 15 20 27	45 56
Новые центры кластеров	7	18	51

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

Центр кластера	7	18	51
Точки кластера	5 6 7 9 11	15 20 27	45 56
Новые центры кластеров	8	21	51

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

Центр кластера	8	21	51
Точки кластера	5 6 7 9 11	15 20 27	45 56
Новые центры кластеров	8	21	51

Кластеры не изменились, значит можно прекратить итерации.