Нужно написать программу на С++ для сжатия цифровых RGB- изображений с использованием алгоритма К-средних.

class Cluster{

vector<POINT> scores;

public:

int curX , curY;//координаты текущего центроида

int lastX, lastY;//координаты предыдущего центоида

size_t Size(){ return scores.size();}//получаем размер вектора

inline void Add(POINT pt){ scores.push_back(pt); }//Добавляем пиксель к кластеру

void SetCenter();

void Clear();//Чистим вектор

static Cluster* Bind(int k, Cluster * clusarr, vector<POINT>& vpt);

static void InitialCenter(int k, Cluster * clusarr , vector<POINT>& vpt);;

static void Start(int k, Cluster * clusarr, vector<POINT>& vpt);

inline POINT& at(unsigned i){ return scores.at(i);}//Доступ к элементам вектора

};

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

void Cluster::InitialCenter(int k, Cluster * clusarr, vector<POINT>& vpt){

int size = vpt.size();

int step = size/k;

int steper = 0;

for(int i = 0;i < k;i++,steper+=step){

clusarr[i].curX = vpt[steper].x;

clusarr[i].curY = vpt[steper].y;

}

}

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

void Cluster::SetCenter(){

int sumX = 0, sumY = 0;

int i = 0;

int size = Size();

for(; i<size;sumX+=scores[i].x,i++);//the centers of mass by x

i = 0;

for(; i<size;sumY+=scores[i].y, i++);//the centers of mass by y

lastX = curX;

lastY = curY;

curX = sumX/size;

curY = sumY/size;

}

void Cluster::Clear(){

scores.clear();

}

И теперь только остался сделать простенький метод самого «привязывания» пикселей к определенному кластеру по принципу сравнения модулей отрезков:

Cluster * Cluster::Bind(int k, Cluster * clusarr, vector<POINT>& vpt){

for(int j = 0; j < k;j++)

clusarr[j].Clear();// Чистим кластер перед использованием

int size = vpt.size();

for(int i = 0; i < size; i++){// Запускаем цикл по всем пикселям множества

int min = sqrt(

pow((float)clusarr[0].curX-vpt[i].x,2)+pow((float)clusarr[0].curY-vpt[i].y,2)

);

Cluster * cl = &clusarr[0];

for(int j = 1; j < k; j++){

int tmp = sqrt(

pow((float)clusarr[j].curX-vpt[i].x,2)+pow((float)clusarr[j].curY-vpt[i].y,2)

);

if(min > tmp){ min = tmp; cl = &clusarr[j];}// Ищем близлежащий кластер

}

cl->Add(vpt[i]);// Добавляем в близ лежащий кластер текущий пиксель

}

return clusarr;

}

И наконец главный цикл:

void Cluster::Start(int k, Cluster * clusarr, vector<POINT>& vpt){

Cluster::InitialCenter(k,clusarr,vpt);

for(;;){//Запускаем основной цикл

int chk = 0;

Cluster::Bind(k,clusarr,vpt);//Связываем точки с кластерами

for(int j = 0; j < k;j++)//Высчитываем новые координаты центроидов

clusarr[j].SetCenter();

for(int p = 0; p<k;p++)//Проверяем не совпадают ли они с предыдущими цент-ми

if(clusarr[p].curX == clusarr[p].lastX && clusarr[p].curY == clusarr[p].lastY)

chk++;

if(chk == k) return;//Если да выходим с цикла

}

}

И что же из этого всего следует?

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

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

Теги:

c++

кластерный анализ

к-средних

Хабы:

C++

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

1)
 var 
n:integer;
begin 
readln(n); 
if(n<0)then write(0) 
else write(n+4);
end.

2)
 var
  a, b: integer;
 begin
  readln(a, b);
  if(a = b) then
write(1)
  else
write(0);
end.

3)
var
  a, b, c, s: integer;
 begin
  s := 0;
  readln(a, b, c);
  if(a >= 0) then s := s + 1;
  if(b >= 0) then s := s + 1;
  if(c >= 0) then s := s + 1;
  write(s);
end.

4)
var
  a, b, c, s: integer;
 begin
  s := 0;
  readln(a, b, c);
  if(a > 0) then s := s + a;
  if(b > 0) then s := s + b;
  if(c > 0) then s := s + c;
  write(s);
end.
5)
 var
  a, b, c: integer;
 begin
  readln(a, b, c);
  if (a < b) then swap(a, b);
  if (a < c) then swap(a, c);
  if (b < c) then swap(b, c);
  write(a, ' ', b, ' ', c);
end.

6)
 var n, k, s, i: integer;
 begin
  s := 0;
  readln(n, k);
  for i := 1 to n.ToString.Length do
  if(strtoint(n.ToString[i]) > k) then s := s + strtoint(n.ToString[i]);
  write(s);
 end.

7)
 var n, s, i: integer;
 begin
  s := 0;
  readln(n);
  for i := 1 to n do
    s := s + i;
  write(s);
 end.

9)
 var n, i: integer;
 begin
  readln(n);
  for i := n downto 1 do
  write(i);
 end.

12
 var
  n, i: integer;
  s: real;
 begin
  s := 0;
  readln(n);
  for i := n downto 1 do
  s:=s+(0.1*i);
    write(s);
 end.

13)
 var n, i: integer;
 begin
  readln(n);
  for i := 1 to n do
    write(sqr(i), ' ');
end.

14)
 var
  n, i, c: integer;
 begin
  i := 1;
  c := 0;
  readln(n);
  while (c <> n) do
  begin
    if(i mod 3 = 0) then begin write(i, ' ');c := c + 1; end;
    i := i + 1;
  end;
end.

15)
 var
  n, i, a: integer;
  c: real;
 begin
  i := 1;
  c := 0;
  readln(n);
  for i := 1 to n do
   begin
    read(a);
    c := c + a;
  end;
  write(c / n)
end.

16)
 var
  n, i, a: integer;
 begin
  i := 1;
  while true do
   begin
    read(a);
    if(a = 0) then break;
    n := n + 1;
  end;
  write(n)
end.

Var
    N, s, i: Integer;
    s1: real;

begin
    readln(N); {общий ввод для всех задач}
    
    if N < 0 then
        writeln('Задача 1. N=', 0)
    else writeln('Задача 1. N=', N + 4);
    
    s := 0;
    for i := 1 to n do
        s := s + i;
    writeln('Задача 7. 1+2+3+…+N=', s);
    
    write('Задача 9. Последовательность от N до 1 = ');
    for i := n downto 1 do
        write(i, ' ');
    writeln();
    
    s1 := 0;
    for i := 1 to n do
        s1 := s1 + i / 10;
    writeln('Задача 12. 0,1+0,2+0,3+..+N/10=', s1);
    
    write('Задача 13. Последовательность квадратов от 1 до N = ');
    for i := 1 to n do
        write(i * i, ' ');
    writeln();
    
    write('Задача 14. Последовательность первых N нечетных чисел = ');
    for i := 1 to n do
        write(2 * i - 1, ' ');
    writeln();
    
    if N > 0 then
        writeln('Задача 20. N степень 3 = ', frac(ln(n) / ln(3)) = 0);
    
    s := 0;
    for i := 1 to n do
        if n mod i = 0 then
            s := s + i;
    writeln('Задача 24. Сумма всех натуральных делителей числа N (сключая 1 и N) = ', s);
end.