List non-zero connected elements in a Matrix cluster given a starting bin

I used MATLAB's histcounts2 to create a 10 row by 7 col matrix, H. I would like to create a set of non-zero bins that are connected directly or indirectly to each other. Here is an example where I got into trouble:

  H = [
  1 0 0 1 1 0 0
  1 0 0 0 1 0 0
  1 0 0 1 1 0 0
  1 0 0 1 0 0 0
  0 0 1 1 0 0 0
  0 1 0 1 0 0 1
  0 1 0 0 0 0 1
  0 1 0 0 0 1 1
  0 1 0 0 1 0 0
  0 1 0 1 1 0 0
];

In row 1, the algorithm find's the first non-zero coordinate (1,1), and then find's down the column the connected 1's: i.e., {(2,1), (3,1), (4,1)}. This set is discarded for being too small. Then, on the same row, it find's the next non-zero bin at (1,4). Desired results are the following 14 connected bin coordinates:

 1 4
 1 5
 2 5
 3 4
 3 5
 4 4
 5 3
 5 4
 6 2
 6 4
 7 2
 8 2
 9 2
10 2

This problem is simpler than a maze problem for one solid reason, and another reason that ended up causing problems when trying to optimize performance.

1. Given a found bin, the algorithm does not have to look backwards towards decreasing rows. It only has to look at the left and right columns, and the three rows ahead for a total of 5 possible searches. (Diagonal connections can occur.)
2. Once a trend is established (i.e., pos, neg, or zero slope), then the slope does not reverse. For example, the above example shows a negative slope trend. Even if (8,3) were to have a 1 due to some noise, we could not have (8,4) because that much noise is filtered out. Also, the other two clusters shown will also have the same slope.

Of the 100's of cases, most results are a good set of connected bins. For example, if bin (1,4) were changed to a 0, then the starting bin is at (5,1). The find down col 5 gets the extent of the 1's (i.e., 3 bins). Then to determine the trend, the algorithms does a find on cols 4 and 6 for rows 1-4. Since it discovers a 1 at (3,4), the conclusion is that the slope is negative, and I finish tracking in a negative slope tracking function. But the (1,4) value made the algorithm declare a positive slope. I fixed this, but then other matrices showed additional problems. I have seen some good use of MATLAB built-in functions to avoid loops. So I was hoping the get some help in using good functions to simplify the code and speed up the process.

A brute solution will be to ignore the slope trend. For a given non-zero bin, say, (2,5):

1. examine left and right cols on the row 2, i.e., (2,4) and (2,6) and mark them as found if non-zero.
2. examine forward cols (3,4), (3,5), and (3,6) and mark them as found if non-zero.

Note that two trendlines will be sufficiently far apart so as not to worry about collisions.

Then for each bin just marked, repeat the left/right/forward search. I was hoping to use the MATLAB functions to handle these searches without this much fine loop granularity to improve performance.

FYI - the histogram was created from a sequence of data, y(n). Using the above approach, the y(n)'s in the bins are selected to produce a trend line.

Below is my MATLAB 2019b configuration. (I submitted a wish-list last month for additional toolboxes.)

• Communications Toolbox
• DSP System Toolbox
• Instrument Control Toolbox
• LTE Toolbox
• MATLAB Compiler
• Parallel Computing Toolbox
• RF Toolbox
• Signal Processing Toolbox
• Symbolic Math Toolbox

Thank you in advance,

Paul

Answer 1

[Paul Hoffrichter]

I took the brute force approach which appears to handle all the edge cases.

I just mark one found bin at a time in recursive calls.

I look to my left.

I look to my right.

I look forward to my left.

I look forward directly in front.

I look forward to my right.