邻居

邻居

关注
发信
关注(28)粉丝(399)

algorithm - 查找径向线段的最近邻居

首先，不要被这个问题的样子吓到;)

我正在尝试在Matlab中实现一个称为圆弧模糊形状模型的形状描述符，其中一部分是获取每个径向线段的最近邻居的列表，如图1d所示)

我在MATLAB中进行了简单直接的实现，但是我陷入了算法的第5步和第6步，这主要是因为我无法绕开定义:

Xb{c,s} = {b1, ..., b{c*s}} as the sorted set of the elements in B*
so that d(b*{c,s}, bi*) <= d(b*{c,s}, bj*), i<j

对我来说，这听起来像是级联排序，首先是按距离递增，然后按索引递升排序，但是我发现最近的邻居并不是按照这篇论文。

algorithm - 查找径向线段的最近邻居-LMLPHP

作为示例，我向您展示了我从段b {4,1}获得的最近邻居，这是图1d中标记为“EX”的那个)

我得到以下b {4,1}最近邻居的列表:b{3,2}, b{3,1}, b{3,8}, b{2,1}, b{2,8}
根据该文件正确的是:b{4,2}, b{4,8}, b{3,2}, b{3,1}, b{3,8}
但是，我的点实际上是最接近于通过欧几里德距离测得的所选线段的集合!距离b{4,1} <=> b{2,1}小于b{4,1} <=> b{4,2}或b{4,1} <=> b{4,8} ...

algorithm - 查找径向线段的最近邻居-LMLPHP

这是我的(丑陋但简单明了的)MATLAB代码:
width  = 734;
height = 734;

assert(width == height, 'Image must be square in size!');

% Radius of the correlogram
R = width;

% Number of circles in correlogram
C = 4;

% Number of sections in correlogram
S = 8;

% "width" of ring segments
d = R/C;

% angle of one segment in degrees
g = 360/S;

% set of bins for the circular description of I
B = zeros(C, S);

% centroid coordinates for bins
B_star = zeros(C,S,2);


% calculate centroids of bins
for c=1:C
    for s=1:S
        alpha = deg2rad(max(s-1, 0)*g + g/2);
        r     = d*max((c-1),0) + d/2;

        B_star(c,s,1) = r*cos(alpha);
        B_star(c,s,2) = r*sin(alpha);
    end
end

% create sorted list of bin numbers which fullfill
% d(b{c,s}*, bi*) <= d(b{c,s}, bj*) where i<j

% B_star_dists is a simple square distance matrix for getting
% the distance between two centroids c_i,s_i and c_j,s_j
B_star_dists = zeros(C*S, C*S);
for i=1:C*S
    [c_i, s_i] = ind2sub([C,S], i);
    % x,y centroid coordinates for point i
    b_star_i   = [B_star(c_i, s_i, 1), B_star(c_i, s_i, 2)];

    for j=1:C*S
        [c_j, s_j] = ind2sub([C,S], j);
        % x,y centroid coordinates for point j
        b_star_j   = [B_star(c_j, s_j, 1), B_star(c_j, s_j, 2)];

        % store the euclidean distance between these two centroids
        % in the distance matrix.
        B_star_dists(i,j) = norm(b_star_i - b_star_j);
    end
end

% calculate nearest neighbour "centroids" for each centroid
% B_NN is a cell array, B{idx} gives an array of indexes to the
% nearest neighbour centroids.

B_NN = cell(C*S, 1);
for i=1:C*S
    [c_i, s_i] = ind2sub([C,S], i);

    % get a (C*S)x2 matrix of all distances, the first column are the array
    % indexes and the second column are the distances e.g
    % 1   d1
    % 2   d2
    % ..  ..
    % CS  d{c,s}

    dists = [transpose(1:C*S), B_star_dists(:, i)];

    % sort ascending by the distances first (e.g second column) then
    % sort ascending by the array index (e.g first column)
    dists = sortrows(dists, [2,1]);

    % middle section has nine neighbours, set as default
    neighbour_count = 9;

    if c_i == 1
        % inner region has S+3 neighbours
        neighbour_count = S+3;
    elseif c_i == C
        % outer most ring has 6 neighbours
        neighbour_count = 6;
    end

    B_NN{i} = dists(1:neighbour_count,1);
end

% FROM HERE ON JUST VISUALIZATION CODE

figure(1);
hold on;
for c=1:C
    % plot circles
    r = c*d;
    plot(r*cos(0:pi/50:2*pi), r*sin(0:pi/50:2*pi), 'k:');
end

for s=1:S
    % plot lines

    line_len = C*d;
    alpha    = deg2rad(s*g);

    start_pt = [0, 0];
    end_pt   = start_pt + line_len.*[cos(alpha), sin(alpha)];

    plot([start_pt(1), end_pt(1)], [start_pt(2), end_pt(2)], 'k-');
end

for c=1:C
    % plot centroids of segments
    for s=1:S
        segment_centroid = B_star(c,s, :);
        plot(segment_centroid(1), segment_centroid(2), '.k');
    end
end

% plot some nearest neighbours
% list of [C;S]
plot_nn = [4;1];

for i = 1:size(plot_nn,2)
   start_c = plot_nn(1,i);
   start_s = plot_nn(2,i);

   start_pt = [B_star(start_c, start_s,1), B_star(start_c, start_s,2)];
   start_idx = sub2ind([C, S], start_c, start_s);

   plot(start_pt(1), start_pt(2), 'xb');

   nn_idx_list = B_NN{start_idx};

   for j = 1:length(nn_idx_list)
      nn_idx = nn_idx_list(j);
      [nn_c, nn_s] = ind2sub([C, S], nn_idx);
      nn_pt = [B_star(nn_c, nn_s,1), B_star(nn_c, nn_s,2)];

      plot(nn_pt(1), nn_pt(2), 'xr');
   end
end

全文可以找到here

最佳答案

该论文谈论“地区邻国”；在欧几里得距离意义上，这些是“最近的邻居”的解释是错误的。它们只是与某个区域相邻的区域，而找到它们的方法很简单:

区域具有2个坐标:(c，s)，其中c表示它们所属的同心圆，从中心的1到边缘的C，而s表示它们所属的同心圆，从1开始(从角度开始)从0°到S，以360°角度结束。

每个c和s坐标与该区域的坐标最多相差1的区域都是一个相邻区域(段号从S到1环绕)。根据该区域的位置，有3种情况: 1d)

  • 该区域是中间区域(标记为MI)，例如区域b(2,4)
    有2个相邻的圈子和2个相邻的扇区，因此共有9个区域:
    圆圈1、2或3和扇区3、4或5的每个区域:b(1,3), b(2,3), b(3,3), b(1,4), b(2,4), b(3,4), b(1,5), b(2,5), b(3,5)
  • 该区域是内部区域(标记为IN)，例如区域b(1,8)
    只有一个相邻的圈子和2个相邻的扇区，但是所有内部区域都是邻居，因此S + 3个区域总计:
    第2圈和扇区7、8或1中的每个区域b(2,7), b(2,8), b(2,1)以及内圈中的每个区域:b(1,1), b(1,2), b(1,3), b(1,4), b(1,5), b(1,6), b(1,7), b(1,8)
  • 该区域是外部区域(标记为EX)，例如区域b(3,1)
    只有一个相邻的圈子和2个相邻的扇区，因此共有6个区域:
    圈2或3和扇区8、1或2中的每个区域:b(2,8), b(2,1), b(2,2), b(3,8), b(3,1), b(3,2)

    • 关于algorithm - 查找径向线段的最近邻居，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33053661/

    10-12 17:49
    Powered by LMLPHP ©2024 邻居 0.034091