n * n блоков и многоугольников

Question

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

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

Мое приложение (K-Nearest Neighbor) требует, чтобы я делал n n блоков из данных, которые у меня есть (многоугольник), т.е. если у меня есть многоугольник (дорога или участок земли), я хочу n квадрат, перемещающийся по нему, избегая пересечения с ребрами и помещая эти n * n пикселей в некоторую переменную.

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

Есть ли известный алгоритм, который я могу реализовать? или что-то, что уже делает это или может облегчить работу в Matlab?

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

Любые идеи?

Answer 1

Я не совсем уверен, что вы хотите, но давайте предположим, что это так: у вас есть двоичная маска, и вы хотите, чтобы все (возможно, перекрывающиеся) n * n квадраты соответствовали.

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

Например

%# create a circle - this is the binary mask 
bw = false(101); 
[xx,yy] = ndgrid(-50:50,-50:50); 
bw((xx.^2+yy.^2)<625)=true; 

%# since we'd want to know which windows fit, we'll collect the linear indices 
%# pointing into bw. Thus, we need an array of the same size as bw that contains 
%# the linear index of each pixel 
indexMask = zeros(size(bw)); 
indexMask(:) = 1:numel(indexMask); 

%# create all possible 5*5 windows with im2col. 
allWindows = im2col(indexMask,[5,5]); 

%# discard all windows that lay even partially outside the mask 
goodWindowIdx = all(bw(allWindows),1); 

goodWindows = allWindows(:,goodWindowIdx); 

Каждый столбец в goodWindows перечислены индексы, соответствующие одной позиции 5 * 5 маска, которая полностью лежит внутри многоугольника (круг в моем случае).