finding longest length

Hi ,I have a matrix as follows I =

     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     1     0     0     0     0     0
     0     0     1     0     1     0     0     0     1     0
     0     1     0     1     1     0     1     0     0     1
     1     0     0     0     1     0     1     1     0     0
     0     0     0     0     1     0     1     0     0     0
     0     1     1     1     0     1     0     0     0     0
     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0

I need the output as follows:

I =

     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0
     0     0     1     0     0     0     0     0     1     0
     0     1     0     1     0     0     0     0     0     1
     1     0     0     0     0     0     0     1     0     0
     0     0     0     0     1     0     1     0     0     0
     0     0     0     0     0     1     0     0     0     0
     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0

i.e only the longest length of pixel that touches two opposite boundary.can any body help please?Thanks

[nick]

Hello Golam,

To transform the matrix as desired, you can use the 'bwconncomp' function to identify all connected groups of 1s.

For each of these components, check whether it touches both the first and last row or the first and last column. This will help you determine if it spans two opposite boundaries. While iterating through the connected groups, keep track of the longest component.

Kindly refer to the documentation by executing the following command in MATLAB Command Window to know more about 'bwconncomp' function :

help bwconncomp

Answer 1

[DGM]

The written description doesn't really describe what the example describes. The example returns the last true element from only the first run of true elements in each column. Here's one way.

% the test sample
A = [0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 1 0 0 0 0 0; 0 0 1 0 1 0 0 0 1 0; 
    0 1 0 1 1 0 1 0 0 1; 1 0 0 0 1 0 1 1 0 0; 0 0 0 0 1 0 1 0 0 0; 0 1 1 1 0 1 0 0 0 0; 
    0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0];

% the expected output
B = [0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0; 0 0 1 0 0 0 0 0 1 0; 
    0 1 0 1 0 0 0 0 0 1; 1 0 0 0 0 0 0 1 0 0; 0 0 0 0 1 0 1 0 0 0; 0 0 0 0 0 1 0 0 0 0; 
    0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0];

% replicate the given output
sz = size(A);
d = [A; zeros(1,sz(2))]; % trailing pad to catch runs that end at image boundary
d = diff(d,1,1) == -1; % transitions from 1 to 0
[~,row] = max(d,[],1); % find the first transition in each column
idx = sub2ind(sz,row,1:sz(2)); % convert to linear indices
idx = idx(any(d,1));  % account for cases where there are zero runs in a column
C = false(sz); % allocate
C(idx) = true; % assign

% show that they match
outpict = cat(3,A,B,C);
imshow(outpict,'initialmagnification','fit')

[Image Analyst]

Yeah, he does not have a single line that stretches all the way across the width of the array. He has two that go only partway across. See, let's label them to see what pixels belong to what blobs:

bw = logical([...
    0     0     0     0     0     0     0     0     0     0
    0     0     0     0     0     0     0     0     0     0
    0     0     0     0     1     0     0     0     0     0
    0     0     1     0     1     0     0     0     1     0
    0     1     0     1     1     0     1     0     0     1
    1     0     0     0     1     0     1     1     0     0
    0     0     0     0     1     0     1     0     0     0
    0     1     1     1     0     1     0     0     0     0
    0     0     0     0     0     0     0     0     0     0
    0     0     0     0     0     0     0     0     0     0]);
L = bwlabel(bw) % Give each blob a unique label number.

L = 10×10

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 2 0 0 1 0 1 1 0 1 0 0 2 1 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

See? The two ones on the right hand side (blob #2) are not connected to the one starting from the left hand side (Blob #1). It's at least 2 pixels away.

Can we assume that it was just a typo and that blob #2 should really have been connected to blob #1?

[DGM]

I'd sooner take the arrays as the problem description, given that the text "longest length" doesn't have much to do with the given result. If we read the text with the arrays in mind, "longest length of pixel that touches two opposite boundary" comes across as plausibly "last position at a transition between pixel values" -- which is still not quite the whole description.

I suppose it's a thoroughly dead question, so we can choose to assert our own interpretation at this point. I suspect it's possible that the 1x3 horizontal strip wasn't supposed to be deleted, but I'm just choosing to assume that the arrays are the accurate description.

I was going to post this earlier, regarding the comment about bwconncomp(). Given my assumption based on the given arrays, I don't really see how blob-based analysis really buys us anything.

A = [0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 1 0 0 0 0 0; 0 0 1 0 1 0 0 0 1 0; 
    0 1 0 1 1 0 1 0 0 1; 1 0 0 0 1 0 1 1 0 0; 0 0 0 0 1 0 1 0 0 0; 0 1 1 1 0 1 0 0 0 0; 
    0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0];

% 4-connectivity gives us 9 blobs
[L nl] = bwlabel(A,4);
op4 = labeloverlay(A,L,'colormap',lines(nl),'transparency',0);
imshow(op4,'initialmagnification','fit')

% 8-connectivity gives us 2 blobs
[L nl] = bwlabel(A,8);
op8 = labeloverlay(A,L,'colormap',lines(nl),'transparency',0);
imshow(op8,'initialmagnification','fit')

Neither case makes it any easier to find the target pixels. If anything, it makes it more difficult.

Answer 2

[Walter Roberson]

Consider using bwskel -- possibly with the 'MinBranchLength' option.

[DGM]

We can consider it. :)

% the given
A = [0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 1 0 0 0 0 0; 0 0 1 0 1 0 0 0 1 0; 
    0 1 0 1 1 0 1 0 0 1; 1 0 0 0 1 0 1 1 0 0; 0 0 0 0 1 0 1 0 0 0; 0 1 1 1 0 1 0 0 0 0; 
    0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0];
B = [0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0; 0 0 1 0 0 0 0 0 1 0; 
    0 1 0 1 0 0 0 0 0 1; 1 0 0 0 0 0 0 1 0 0; 0 0 0 0 1 0 1 0 0 0; 0 0 0 0 0 1 0 0 0 0; 
    0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0];

% for a range of branch lengths relevant only to this example
for k = 0:5
    C = bwskel(logical(A),'minbranchlength',k);
    outpict = cat(3,A,B,C);
    figure
    imshow(outpict,'initialmagnification','fit')
end

●

I apologize for the lazy and confusing composition. Coincidence is probably more important than anything here. The result we should be seeing should be composed purely of black, white, and red. Yellow pixels indicate output pixels which should be true, but aren't. Magenta pixels indicate output pixels which should be false, but aren't. In this case, we've reached steady-state at a branch length of 4.

Like I said, we're free to interpret the requirements, but at least for my own interpretation, bwskel() can't reproduce the given example. It just seems like a simple 1-D columnwise analysis rather than a blob-level analysis, or anything based on 2-D connectivity.

I guess this aspect of dead questions is as much a blessing as a curse. We're free to interpret where convenient, but we're never going to get certain clarification about whose interpretation was right.

[Image Analyst]

I was working on a solution with bwskel but then I discovered what I believe to be a bug in it so I didn't post it.

bw = logical([...
    0     0     0     0     0     0     0     0     0     0
    0     0     0     0     0     0     0     0     0     0
    0     0     1     0     1     0     0     0     1     0
    0     1     0     1     1     0     1     1     0     1
    1     0     0     0     1     0     1     1     0     0
    0     0     0     0     1     0     1     0     0     0
    0     1     1     1     0     1     0     0     0     0
    0     0     0     0     0     0     0     0     0     0
    0     0     0     0     0     0     0     0     0     0]); % 9x10 array
longBranch = bwskel(bw, "MinBranchLength", 10)

longBranch = 9x10 logical array
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0

It didn't find the skeleton which should have a length of 12. It didn't even find any skeleton whatsoever. I'll see if I can talk with tech support about it tomorrow.

[DGM]

... iinteresting. I thought it would have actually had a steady-state. I guess it doesn't.

EDIT: hmm. It's all done in MEX. Maybe I was thinking about the bwmorph() modes, wherein connected groups can at most be reduced to single pixels. Maybe bwskel() doesn't have that constraint.

[Ashish Uthama]

This is a bug, likely in the pruning logic (images.internal.pruneEdges3)within bwkel. We are tracking this at Mathworks and will work on fixing it.

[Ashish Uthama]

@Image Analyst - sorry for the delay in looking into this. I

MinBranchLength prunes branches. i.e parts of a skeleton.

The max branch I can see is 6, which looks right to me. Would you mind explaining what you expected to see for 10 (in case I misundertood).

longestBranch = bwskel(bw, "MinBranchLength", 6)
longestBranch =

9×10 logical array

0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   1   0
0   0   0   0   0   0   0   1   0   1
0   0   0   0   0   0   0   1   0   0
0   0   0   0   1   0   1   0   0   0
0   0   0   0   0   1   0   0   0   0
0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0