n * n блоков и полигонов

Question

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

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

Мое приложение (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, которая полностью лежит внутри многоугольника (в моем случае это круг).