在矩阵中找到十字的最快方法 [英] Fastest way to find a cross in a matrix

问题描述

定义:
如果元素
，则A(i，j)= 1是十字的中点 A(i-1，j)= 1
A(i + 1，j)= 1
A(i，j + 1)= 1
A(i，j-1)= 1
元素和中点一起在矩阵A中形成一个叉，其中A至少是一个3×3矩阵，并且 i ， j ∈ℕ\ {0}

Definition:
A(i, j) = 1 is a midpoint of a cross if the elements
A(i-1, j) = 1
A(i+1, j) = 1
A(i, j+1) = 1
A(i, j-1) = 1.
Together the elements and the midpoint form a cross in a matrix A, where A is at least a 3-by-3 matrix and i, j ∈ ℕ\{0}.

假设上面的图像是8、8矩阵A，以自然数1、2、3 ...作为元素.根据这个定义，矩阵总共有3个叉.十字的中点分别在A(2,2)，A(5，4)和A(5，5)上.

Suppose the image above is the 8-by-8 matrix A with natural numbers 1, 2, 3 ... as elements. From this definition the matrix has a total of 3 crosses. The crosses have their midpoints on A(2,2), A(5, 4) and A(5, 5).

我想做的是编写一个函数，该函数可以找到矩阵A中的交叉数.我有一个主意，但我不确定它是最佳的.这是它的伪代码:

What I want to do is write a function that finds the number of crosses in the matrix A. I have an idea but I'm not sure it's the most optimal one. Here's the pseudocode for it:

ITERATE FROM row 2 TO row 7
    ITERATE FROM column 1 TO column 8
        IF current element contains 1
            INCREMENT xcount by 1
            IF xcount >= 3
                CHECK IF counted 1:s is part of a cross
        ELSE IF xcount IS NOT 0
            SET xcount to 0

这个想法是迭代从第2行到第7行的每一列.如果在同一行上发现3个连续的1:s，我会立即检查1:s是否属于十字架.这应该可以工作，但是想象一下有一个非常大的矩阵A-在这种情况下，此代码的效率如何?使用矢量符号不能解决这个问题吗?

The idea is to iterate through every column from row 2 to row 7. If I find 3 consecutive 1:s on the same row I immediately check if the 1:s belongs to a cross. This should work, but imagine having a very large matrix A - how efficient would this code be in that situation? Couldn't this problem be solved using vector notation?

非常感谢任何回答.预先感谢！

Any answer is very much appreciated. Thanks in advance!

推荐答案

目前不在matlab附近，但这就是我要做的.假设A是二进制的(只有0'a和1's):

Not near matlab at the moment, but this is what I'd do. Assuming A is binary (has only 0'a and 1's):

 crs=[0 1 0 ; 1 1 1 ; 0 1 0];           % a minimal "cross" filter
 C=conv2(A,crs./sum(crs(:)),'same');    % convolve A with it
 [x y]=find(C>0.9);                     % find x,y positions of the crosses by looking
                                        % for peak values of C

因此，您基本上可以用最小"(归一化)叉形(crs)进行卷积，并使用max查找峰. x和y是您的交叉位置的坐标.无需使用循环，只需使用内置(且非常快)的2d卷积和max函数.

so you basically convolve with a "minimal" (normalized) cross (crs) and look for peaks using max. x and y are the coordinates of your cross positions. No need to use for loops, just the built in (and pretty fast) 2d convolution, and the max function.

阈值条件C>0.9只是为了说明需要通过强度crs加权的阈值.在这种情况下，我已在卷积线(crs/sum(crs(:)))中对crs进行了归一化处理，因此，如果如示例中的A是二进制矩阵，您会发现最小归一化交叉的卷积将保留像素值，其中十字在1处，而其他像素将小于1(这就是我任意选择0.9的原因).因此，如果阈值始终为二进制，则可以将其替换为C==1.

The threshold condition C>0.9, is just to illustrate that there's need to be a threshold that is weighted by intensity of crs. In this case I have normalized crs in the colvolution line (crs/sum(crs(:))) so if A is a binary matrix as in the example, you find that the convolution of the minimal normalized cross will leave the value of the pixel where the cross is at 1, whereas other pixels will be less than 1 (that's why I arbitrarily chose 0.9) . So you can replace the threshold to C==1, if it's always a binary.

显示十字架位置的另一种方法是查看C.*(C==1).这将生成一个尺寸为A且只有1 s的矩阵，仅在十字架位于...

Another way to visulize the position of the cross is just to look at C.*(C==1). This will generate a matrix the size of A with 1s only where the crosses were...

为获得最大速度，您可以考虑将其写为一个衬纸，例如:

For maximal speed, you may consider writing it as a one liner, for example:

[x y]=find(conv2(A,[0 1 0 ; 1 1 1 ; 0 1 0]./5,'same')==1); 

这篇关于在矩阵中找到十字的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！