Перейти к содержимому
Compvision.ru
Smorodov

Самоорганизующиеся карты для получения поверхности по облаку точек.

Recommended Posts

Интересное приложение самоорганизующихся карт (сети Кохонена).

http://red.csie.ntu.edu.tw/demo/art/CSM/CSM.php

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Сети Кохонена имеют немного приложений кроме визуализации многомерных данных. Но получение mesh из точек сейчас вполне актульная задача для RGBD (Kinect), но как я понимаю чтобы встроится в PCL нужно чтобы алгоритмы работали очень быстро, а SOM этим не может похвастаться даже если вводить иерархию и kd-tree. Так же для анализа сцены мне кажется было бы неплохо иметь mesh картой.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Можно GPU попробовать применять, нейронки хорошо параллелятся.

И потом, если есть хорошее начальное приближение, то не должно быть нужно много итераций.

Ссылка по тулбоксу отображения Шварца-Кристофеля: http://www.math.udel.edu/~driscoll/SC/

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

dereyly, SOM параллелятся просто. Там и Best Match можно параллельно искать(через редукцию) и веса адаптировать тоже независимо можно(т.к. зависят только от Best Match и собственных координат в сетке).

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Тут реалтайм работа SOM с Kinekt-ом (упоминаются исходники для языка Processing, но я их не обнаружил):

http://disturbmedia.com/blog/post/playing-with-pixels-in-depth-with-kinect-part-2/

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Еще статья по реконструкции поверхностей при помощи SOM:

http://i.cs.hku.hk/~yzyu/research/neurosurf/

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Соорудил матлабовский пример к лекции по SOM (теорию см. в книжке С. Хайкин "Нейронные сети. Полный курс" стр. 577-588):


clear;

% Количество примеров
samples_num=1000;
% Создаем набор данных
m=randn(2,samples_num);

%Количество нейронов на сторону решетки
w_num=10;

% для двумерной решетки
% обычно устанавливают равным "радиусу" решетки
sigma0=1; % параметр ширины топологической окрестности
% параметр убывания
tau1=1000/log(sigma0);

% Скорость обучения
nu0=0.2;
% Скорость убывания скорости обучения (чем больше тем медленее убывает)
tau2=1000;

% Инициализация весов

% Можно инициализировать случайными значениями
%w=rand(w_num, w_num,2);

% Можно инициализировать заранее заданной структурой (сетка)
[wx,wy]=meshgrid(0.1:0.1:0.1*w_num,0.1:0.1:0.1*w_num);
w(:,:,1)=wx;
w(:,:,2)=wy;

n=0;
while(1)

% Номер текущего примера
cur_sample_num=ceil(rand()*samples_num);

% Извлекли пример из выборки
cur_sample=m(:,cur_sample_num);

% Вычисляем расстояния от текущего примера до каждого нейрона
d(:,:,1)=(w(:,:,1)- repmat(cur_sample(1),w_num, w_num));
d(:,:,2)=(w(:,:,2)- repmat(cur_sample(2),w_num, w_num));

dist=(d(:,:,1).^2+d(:,:,2).^2) ;

% Находим ближайший нейрон (нейрон-победитель)
[A,B]=min(dist(:));
% B - здесь это индекс (сквозной), из него нужно сделать индекс строки и
% индекс столбца.
% Индексы в MATLAB-е начинаются с 1, поэтому для поиска столбца и строки нужно вычесть
% 1 дальше найти остаток от деления и результат целочисленного деления.
% Это и будут координаты нейрона в матрице.
% Затем добавить единицы, чтобы перейти в систему индексации MATLAB-а.
B=B-1;
I=mod(B,w_num)+1; % Строка
J=floor(B/w_num)+1;% Столбец

% номер итерации (дискретное время процесса)
n=n+1;

% чтобы не плодились графики
figure(1);

% здесь накапливается сумма квадратов коррекции.
delta_sum=zeros(2,1);

% Будем учитывать только несколько ближайших к победителю соседей
N_neighbors=2; % Размер окрестности.

I1=I-N_neighbors;
I2=I+N_neighbors;
J1=J-N_neighbors;
J2=J+N_neighbors;

% проверим, чтобы не выйти за границы массивов
if(I1<1)
I1=1;
end;

if(I2>w_num)
I2=w_num;
end;

if(J1<1)
J1=1;
end;

if(J2>w_num)
J2=w_num;
end;

% Можно рассматривать все нейроны
%for j=1: w_num
% for i=1: w_num

% Но большого смысла нет, т.к. влияние нейрона-победителя сильно
% ослабляется с расстоянием. Поэтому рассматриваем только окрестность
% нейрона-победителя.
for j=J1:J2
for i=I1:I2
% Квадрат расстояния между текущим и победившим нейронами в решетке
% (в пространстве индексов)
d_sq=(I-i)^2+(J-j)^2;
sigma=sigma0*exp(-n/tau1);
% ширина топологической окрестности нейрона
h=exp(-d_sq/(2*(sigma^2)));
% скорость обучения
nu=nu0*exp(-n/tau2);

% Достаем веса текущего нейрона
w_cur=w(i,j,:);
% Преобразуем его в вектор столбец
w_cur=reshape(w_cur,2,1);
% Находим величину коррекции весов
delta=nu*h*(cur_sample-w_cur);
% Копим сумму квадратов изменений весов (для проверки критерия останова)
delta_sum=delta_sum+delta.^2;
% Производим коррекцию
w_cur=w_cur+delta;
% Возвращаем откорректированный вес на место
w(i,j,:)=w_cur;
end;
end;

% Строим точки на графике

% Вытягиваем все веса нейронов в матрицу w_num^2 на 2, где
% w_num^2 - это общее количество нейронов сети, 2 - количество весовых
% коэффициентов у каждого нейрона

pts=reshape(w,w_num^2,2);

% Чтобы было быстрее, строим графики каждые 100 итераций
if(mod(n,100)==0)
plot(pts(:,1),pts(:,2),'or',m(1,:),m(2,:),'xg');
end;

% проверим критерий останова
if (sqrt(delta_sum(1)+delta_sum(2))/(w_num^2*n)<1e-9)
break;
end;

end;

sprintf('Потребовалось %d итераций',n)
[/code]

Выдает что то вроде этого:

post-1-0-23847700-1385905707_thumb.png

Несложно обобщить на трехмерную сетку.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

я так и не понял какая задача то решается?

вроде как есть задача получения минимальной упаковки(внешней оболочки) для облака точек или как то так.

но судя по последней картинке, там еще есть шумы\аутлайнеры?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Задача получить из шумного облака точек (например семплы с кинекта) некую упорядоченную, более-менее стабильную структуру (модель распределения).

Чтобы её можно было анализировать стандартными средствами.

Улучшенный пример из предыдущего поста SOM с учетом "совести": SOM.RAR

Выдает такое:

post-1-0-62864400-1385977279_thumb.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

>Задача получить из шумного облака точек (например семплы с кинекта) некую упорядоченную, более-менее стабильную структуру (модель распределения).

SOINN?

Она тоже построит сетку узлов. А шум (узлы, попавшие в области с малой плотностью распределения) - удалит.

Я, правда, точно не помню самый начальный алгоритм (какую сетку/граф он строит) - но модификация ESOINN даст сетку с треугольными ячейками (может, кому-то для его задачи будет полезнее 3 соседа у нейрона в середине карты, чем 4, как в SOM с прямоугольными ячейками).

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Про E-SOINN не знал, почитаю.

Если я правильно понимаю что делает SOINN, то она не обязательно дает связный граф (скорее даже её целью является кластеризация).

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

ЗЫ: SOM не обязана иметь квадратные ячейки (хотя это один из наиболее популярных вариантов (второй вариант шестигранники) ),

она может иметь произвольную структуру и зависит от того, как задана функция топологической окрестности.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

ESOINN - модификация SOINN, разница по большому счету в том, что тут только 1 слой у сети и алгоритм обучения другой.

Тут скорей подойдет алгоритм растущего нейронного газа(Growing Neural Gas), он как раз пытается построить фактически триангуляцию Делоне для входного множества точек, т.ч. для построения поверхностей эта штука должна подойти.

з.ы. раз уж зашла речь о всяких самоорганизующихся алгоритмах, то немного пропиарю себя: про SOINN можно почитать в моей статье тут: http://habrahabr.ru/post/192978/, тамже есть и ссылка на код чтобы можно было поиграться. А про ESOINN в начале января опубликую статейку на хабре...

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Вас и пиарить особо не нужно :) первая ссылка SOINN и ESOINN на github-е на Ваш код, спасибо :)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

ESOINN - модификация SOINN, разница по большому счету в том, что тут только 1 слой у сети и алгоритм обучения другой.

Тут скорей подойдет алгоритм растущего нейронного газа(Growing Neural Gas), он как раз пытается построить фактически триангуляцию Делоне для входного множества точек, т.ч. для построения поверхностей эта штука должна подойти.

з.ы. раз уж зашла речь о всяких самоорганизующихся алгоритмах, то немного пропиарю себя: про SOINN можно почитать в моей статье тут: http://habrahabr.ru/post/192978/, тамже есть и ссылка на код чтобы можно было поиграться. А про ESOINN в начале января опубликую статейку на хабре...

Я тоже Вас немного попиарил, ну и compvision.ru тоже :), если Вы не против, ссылка на Ваш github в описании к видео.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Про растущий нейронный газ:

Очень интересная демка (много разных алгоритмов получения сетки по точкам) с исходниками на java.

http://www.demogng.de/

Еще нейронный газ для формирования поверхности по облаку точек: https://github.com/kudkudak/Growing-Neural-Gas

И еще один нейронный газ :) : https://github.com/sergioroa/neuralgas (главная страница здесь: http://talkingrobots.dfki.de/software/ )

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Да конечно не против, open source же. Забавная демка получилась)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Чтобы поиграться с растущим нейронным газом, можно взять простую реализацию у меня на github.

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Чтобы поиграться с растущим нейронным газом, можно взять простую реализацию у меня на github.

Отличная штука :)

Результат смотрится получше чем ESOINN:

post-1-0-45308200-1388261458_thumb.pngpost-1-0-72833100-1388262079_thumb.pngpost-1-0-26195900-1388262086_thumb.pngpost-1-0-31356400-1388262311_thumb.png

И видео:

ЗЫ: Использованный при инициализации набор параметров:

ng::GNG model(2, 0.05, 6e-3, 0.5, 5e-4, 600, 88, 1000, 2, false);

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Ну на самом деле ESOINN более мощная штука:) Но она больше не для визуализации данных, а для майнинга. По сути она дает представление о данных "с высоты птичьего полета", т.е. качественное представление о топологической структуре классов, а нейронный газ просто пытается построить триангуляцию Делоне для показываемых классов - оттуда и лучшие результаты на задачах связанных с визуализацией, но в более "серьезных" задачах выдаваемая им информация и избыточна и зашумлена(очевидно, что на шумных классах он будет переобучаться по полной программе), ну и там есть еще ряд проблем которые можно долго перечислять) А вообще нейронный газ(как и самоорганизующиеся карты Кохонена) можно считать прародителем всех алгоритмов класса *SOINN)

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Всем привет!

Если кому-то интересна тема самоорганизующихся нейронных сетей, то можете почитать мою новую статью на хабре про алгоритм ESOINN: http://habrahabr.ru/company/itseez/blog/206116/

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Интересная статья, понятное изложение.

Хотелось бы еще один пункт видеть, а именно: "когда не следует использовать описанный в статье метод". То есть когда лучше использовать его ближайшие аналоги?

Это дало бы более полное представление и о том, когда его следует использовать.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Хороший вопрос. Формально писать это в статье сейчас времени нету, поэтому отвечу пока тут: Если рассмотреть пару SOINN vs. ESOINN, то второй алгоритм предпочтительней использовать всегда, т.к. он аккуратней работает с нечеткими границами классов, но иногда имеет смысл вводить второй слой аналогично тому, как он вводится в SOINN, на cross validation это скорей всего даст худшую точность классификации, но зато будет значительно проще анализировать топологическую стрктуру кластеров. Это дает профит, если мы сомневаемся в качестве кластеризации, тогда можно прогнать сеть с разными параметрами много раз, для каждой сети построить второй слой и по нему выделять общие паттерны во всех построенных моделях.

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

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

Есть еще вариант использовать ESOINN для обучения SVM без учителя, но в виде кода у меня руки не доходят его реализовать)

  • Like 1

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте учётную запись или войдите для комментирования

Вы должны быть пользователем, чтобы оставить комментарий

Создать учётную запись

Зарегистрируйтесь для создания учётной записи. Это просто!

Зарегистрировать учётную запись

Войти

Уже зарегистрированы? Войдите здесь.

Войти сейчас


  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу

×