0
$\begingroup$

enter image description here

I possess a binary sparse symmetric matrix with square blocks centered on its main diagonal (white=0, black=1). These can be of any size and can overlap. I aim to detect centers of these squares using some image processing approach (red dots) in MATLAB. As the size of the matrix may get very large, techniques such as region growing while traversing the main diagonal is very inefficient. Can anyone have a suggestion on this?

$\endgroup$
1
$\begingroup$

"Image processing method" here really boils down to ... "for" loops.

You'd walk the main diagonal (or the first non-main diagonal next to it), and as soon as you hit a value, you count the values right of that aren't 0. Soon as you know how many these are, you're done. Half that number, add it to the number of the row, and tadah, center of square.

To deal with overlap is trivial: once you've reached the end of a row go one element further and then you go up until you hit either the diagonal or another non-zero value.

Note that you say "sparse" matrix: depending on the matrix storage format, the "how many entries are set in this row" might already be how the whole thing is stored, making this even easier.

$\endgroup$
2
  • $\begingroup$ Thanks a lot. Yet, is this more efficient than growing a square on each diagonal element as long as the grown structure is filled with 1s? $\endgroup$
    – Monotros
    Mar 13 at 17:06
  • $\begingroup$ Well, growing a square is quadratical in values to be changed, walking a line is linear and you don't have to have a shadow copy of your original matrix, because there's nothing to be changed. So yes, this is by far more efficient in terms of operations AND memory required. $\endgroup$ Mar 13 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.