Thread Subject: Picking Ones among Zeros

Hello,

What would be the simplest way to retrieve the size of connected components (ones) in a binary string?

as example, I have

a= [ 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0]

I would like to return
>>b
      4
      7
      2

There are 4 connected 'Ones' then 7 and then 2 among the zeros.

Thank you!

Frederic

On Jul 4, 5:44 pm, "Frederic Sigoillot" <sigoil...@yahoo.fr> wrote:
> Hello,
>
> What would be the simplest way to retrieve the size of connected components (ones) in a binary string?
>
> as example, I have
>
> a= [ 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0]
>
> I would like to return>>b
>
>       4
>       7
>       2
>
> There are 4 connected 'Ones' then 7 and then 2 among the zeros.
>
> Thank you!
>
> Frederic

------------------------------------------------
Do you have the image processing toolbox?
If so, run "a" though bwlabel(), then use the labeled image in
regionprops() and you're done. Just two lines of code, and superfast,
especially for such a small matrix as you gave.

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <9032f492-3164-4f68-bb9a-7af6be64fb2f@o6g2000yqj.googlegroups.com>...
> On Jul 4, 5:44?pm, "Frederic Sigoillot" <sigoil...@yahoo.fr> wrote:
> > Hello,
> >
> > What would be the simplest way to retrieve the size of connected components (ones) in a binary string?
> >
> > as example, I have
> >
> > a= [ 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0]
> >
> > I would like to return>>b
> >
> > ? ? ? 4
> > ? ? ? 7
> > ? ? ? 2
> >
> > There are 4 connected 'Ones' then 7 and then 2 among the zeros.
> >
> > Thank you!
> >
> > Frederic
>
> ------------------------------------------------
> Do you have the image processing toolbox?
> If so, run "a" though bwlabel(), then use the labeled image in
> regionprops() and you're done. Just two lines of code, and superfast,
> especially for such a small matrix as you gave.

If u dont have the toolbox u can simply:
a= [ 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0];

b = a- [a(2:end),0];
In = find(b == -1); Fi = find(b == 1);
Loc = In+1;
Size = Fi-In;

Be aware works for this case only!

or give a look at this FEX submission: getchunks id:10038

If you don't have bwlabel, this should work:

D = diff(findstr(a,1));
diff([0 find(D~=1) length(D)+1])

caveat: I didn't test this out on MATLAB, this PC doesn't have it. I think this will work though!

"Matt Fig" <spamanon@yahoo.com> wrote in message <h2okru$frv$1@fred.mathworks.com>...
> If you don't have bwlabel, this should work:
>
> D = diff(findstr(a,1));
> diff([0 find(D~=1) length(D)+1])
>
> caveat: I didn't test this out on MATLAB, this PC doesn't have it. I think this will work though!

Nit-pic...

~D is generally a lot faster than D~=1. By a factor of about 10-15 on my PC.

"Steve Amphlett" <Firstname.Lastname@Where-I-Work.com> wrote in message
> Nit-pic...
>
> ~D is generally a lot faster than D~=1. By a factor of about 10-15 on my PC.

True, where applicable!

Since I wrote the SplitVec on FEX, I'm kind of lazy to think about using stock functions:

http://www.mathworks.com/matlabcentral/fileexchange/24255
 
[l first] = SplitVec(a,[],'length','first');
l1 = l(a(first)==1)

l1 =

     4
     7
     2

% Bruno

"Matt Fig" <spamanon@yahoo.com> wrote in message <h2okru$frv$1@fred.mathworks.com>...
> If you don't have bwlabel, this should work:
>
> D = diff(findstr(a,1));
> diff([0 find(D~=1) length(D)+1])
>
> caveat: I didn't test this out on MATLAB, this PC doesn't have it. I think this will work though!

Matt, Make a test for you and it fails when a = 0 ! Any quick fix?

Bruno

"Frederic Sigoillot" <sigoillot@yahoo.fr> wrote in message <h2oif2$g5h$1@fred.mathworks.com>...
> Hello,
>
> What would be the simplest way to retrieve the size of connected components (ones) in a binary string?
>
> as example, I have
>
> a= [ 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0]
>
> I would like to return
> >>b
> 4
> 7
> 2
>
> There are 4 connected 'Ones' then 7 and then 2 among the zeros.
>
> Thank you!
>
> Frederic



Another (similar) idea that's been floated in other threads:

BlockStarts=strfind([0,a],[0,1]);
BlockEnds=strfind([a 0],[1,0]);
Lengths=BlockEnds-BlockStarts+1;

On Jul 4, 2:44 pm, "Frederic Sigoillot" <sigoil...@yahoo.fr> wrote:
> Hello,
>
> What would be the simplest way to retrieve the size of connected components (ones) in a binary string?
>
> as example, I have
>
> a= [ 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0]
>
> I would like to return>>b
>
>       4
>       7
>       2
>
> There are 4 connected 'Ones' then 7 and then 2 among the zeros.
>
> Thank you!
>
> Frederic


Here's another solution:


b = strfind(a,[1 0]) - strfind(a,[0 1])

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> Matt, Make a test for you and it fails when a = 0 ! Any quick fix?
>
> Bruno

Bruno at his most diligent :-)....

I = findstr(a,1);
if ~isempty(I)
    I = diff([0 find(diff(I)~=1) length(I)]);
end

Or if we *MUST* keep it to 2 lines:
I = findstr(a,1);
if ~isempty(I), I = diff([0 find(diff(I)~=1) length(I)]);end % HAHA, still fits...



My turn:

Bruno, your method fails for a = []. Any quick fix?

>
> My turn:
>
> Bruno, your method fails for a = []. Any quick fix?

Good find Matt. A fix with four characters, is it quick enough?

[l first] = SplitVec([a 0],[],'length','first');
l1=l(a(first)==1)

Guess a real fix is resubmit SplitVec to FEX.

Bruno

Siyi Deng <mr.siyi.deng@gmail.com> wrote in message <987ab093-7a3a-4f31-a470-832243bcbce9@q40g2000prh.googlegroups.com>...

>
> Here's another solution:
>
>
> b = strfind(a,[1 0]) - strfind(a,[0 1])

A quick fix for a=1 ? Heh?

Bruno

On Jul 6, 1:30 pm, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:
> Siyi Deng <mr.siyi.d...@gmail.com> wrote in message <987ab093-7a3a-4f31-a470-832243bcb...@q40g2000prh.googlegroups.com>...
>
> > Here's another solution:
>
> > b = strfind(a,[1 0]) - strfind(a,[0 1])
>
> A quick fix for a=1 ? Heh?
>
> Bruno

fine,

b = strfind([0,a,0],[1 0]) - strfind([0,a,0],[0 1])

still a oneliner

Another (one-liner) solution:
 
find([0 a].*[~a 1])-find([1 ~a].*[a 0])

Bruno

And another one

diff(reshape(find(xor([0 a],[a 0])),2,[]))

Bruno

For long vectors it may be worthwhile to avoid the one liners. Calling find twice on the whole array seems to be the culprit. It is interesting to see so many solutions to a problem which is so simple to state.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
N = 30;
t = zeros(1,5); % Timings.

for ii = 1:N
    a = round(rand(1,900000));
% a = [zeros(1,5),ones(1,5)];
% a(1:2:12) = ones(1,6);
% a = [];
% a = 0;
% a = 1;
    
    tic
    [l first] = SplitVec(a,[],'length','first');
    l1 = l(a(first)==1);
% [l first] = SplitVec([a 0],[],'length','first');
% l1=l(a(first)==1);
    t(1) = t(1) + toc;

    tic
    I = find(a);% Matt Fig
    if ~isempty(I);I = diff([0 find(diff(I)~=1) length(I)]);end
    t(2) = t(2) + toc;

    tic
    BlockStarts = strfind([0,a],[0,1]); % Matt
    BlockEnds = strfind([a 0],[1,0]);
    Lengths = BlockEnds-BlockStarts+1;
    t(3) = t(3) + toc;
    
    tic
    S = strfind([0,a,0],[1 0]) - strfind([0,a,0],[0 1]) ; %Siyi2
    t(4) = t(4) + toc;
    
    
    tic
    B2 = find([0 a].*[~a 1])-find([1 ~a].*[a 0]); % Bruno2
    t(5) = t(5) + toc;

    if ~isequal(I,l1',Lengths,S,B2)
        disp(' Someone Messed Up. Check whos.')
        break
    end
    
end

t./min(t)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

How (fast) they perform on my hardware:

Bruno SplitVec: 2.8668
Matt F.': 1.0000
Matt.'s (strfind): 1.4899
Siyi2 (strfind one liner): 1.5110
Bruno's 2 (double-find): 3.5590
Bruno's 3 (find/xor): 1.4440

Bruno

The same order, and on my machine (sorry I forgot to post this the first time):

    3.1187
    1.0000
    1.6928
    1.6873
    3.9964
    1.6329

I wonder how the BWLABEL solution performs. Of course, like SplitVec, BWLABEL does a lot more than solve this simple problem.

Result change a little bit if input is LOGICAL. I also add clean up CLEAR on the garbage of various codes to make sure there is little interference by memory allocation.

t = zeros(1,6); % Timings.

for ii = 1:N
    a = rand(1,900000)>0.5; % logical, instead of double

    tic
    [l first] = SplitVec(a,[],'length','first');
    l1 = l(a(first)==1);
    t(1) = t(1) + toc;
    clear l l1 first

    tic
    I = find(a);% Matt Fig
    if ~isempty(I);I = diff([0 find(diff(I)~=1) length(I)]);end
    t(2) = t(2) + toc;
    clear I

    tic
    BlockStarts = strfind([false a],[false true]); % Matt
    BlockEnds = strfind([a false],[true false]);
    Lengths = BlockEnds-BlockStarts+1;
    t(3) = t(3) + toc;
    clear BlockStarts BlockEnds Lengths

    tic
    S = strfind([false,a,false],[true false]) - ...
        strfind([false,a,false],[false true]) ; %Siyi2
    t(4) = t(4) + toc;
    clear S

    tic
    B2 = find([false a].*[~a true])-find([true ~a].*[a false]); % Bruno2
    t(5) = t(5) + toc;
    clear B2
    
    tic
    B3 = diff(reshape(find(xor([false a],[a false])),2,[]));
    t(6) = t(6) + toc;
    clear B3

end

t./min(t)

    3.3400 % SplitVec
    1.0720 % MF
    1.6607 % M
    1.7150 % S
    1.9589 % B2
    1.0000 % B3

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> Result change a little bit if input is LOGICAL. I also add clean up CLEAR on the garbage of various codes to make sure there is little interference by memory allocation.


Now that is interesting.
Anyone up for the slowest/shortest one liner contest? I have an entry:-)

cellfun('length',regexp(sprintf('%i',a),'1[1]*','match'))

Siyi Deng <mr.siyi.deng@gmail.com> wrote in message <dd44bfac-dbcb-4a24-aff0-e8d97d454878@m7g2000prd.googlegroups.com>...

> b = strfind([0,a,0],[1 0]) - strfind([0,a,0],[0 1])

It would probably be better to do this as a 2-liner, so that you don't have the overhead of constructing [0,a,0] twice.

A=[0,a,0];
b=strfind(A,[1 0]) - strfind(A,[0 1]);

Accordingly, Bruno, a fairer timing test would be to implement my approach as above.

"Matt " <xys@whatever.com> wrote in message <h3000a$c3n$1@fred.mathworks.com>...
> Siyi Deng <mr.siyi.deng@gmail.com> wrote in message <dd44bfac-dbcb-4a24-aff0-e8d97d454878@m7g2000prd.googlegroups.com>...
>
> > b = strfind([0,a,0],[1 0]) - strfind([0,a,0],[0 1])
>
> It would probably be better to do this as a 2-liner, so that you don't have the overhead of constructing [0,a,0] twice.
>
> A=[0,a,0];
> b=strfind(A,[1 0]) - strfind(A,[0 1]);
>
> Accordingly, Bruno, a fairer timing test would be to implement my approach as above.

function benchlogical

N = 30;
t = zeros(1,6); % Timings.

for ii = 1:N
    a = rand(1,900000)>0.5; % logical, instead of double


   %%%% SP
    tic
    [l first] = SplitVec(a,[],'length','first');
    l1 = l(a(first)==1);
    t(1) = t(1) + toc;
    clear l l1 first

   %%%% MF
    tic
    I = find(a);% Matt Fig
    if ~isempty(I);I = diff([0 find(diff(I)~=1) length(I)]);end
    t(2) = t(2) + toc;
    clear I

   %%%% M
    tic
    BlockStarts = strfind([false a],[false true]); % Matt
    BlockEnds = strfind([a false],[true false]);
    Lengths = BlockEnds-BlockStarts+1;
    t(3) = t(3) + toc;
    clear BlockStarts BlockEnds Lengths

   %%%% S/M
    tic
    aa = [false,a,false];
    S = strfind(aa,[true false]) - strfind(aa,[false true]) ; %Siyi2/Matt
    t(4) = t(4) + toc;
    clear aa S

   %%%% B2
    tic
    B2 = find([false a].*[~a true])-find([true ~a].*[a false]); % Bruno2
    t(5) = t(5) + toc;
    clear B2
    
   %%% B3
    tic
    B3 = diff(reshape(find(xor([false a],[a false])),2,[]));
    t(6) = t(6) + toc;
    clear B3

end

t./min(t)

end

2007B-32 bit Windows:

5.5437 (SV)
1.6845 (MF)
2.3862 (M)
2.3322 (S/M)
4.7060 (B2)
1.0000 (B3)

2009A-64 bit Windows:

3.5185 (SV)
1.1234 (MF)
1.6883 (M)
1.6361 (S/M)
3.2038 (S/M)
1.0000 (B3)

Bruno

"Matt Fig" <spamanon@yahoo.com> wrote in message <h2u429$f57$1@fred.mathworks.com>...
>
> cellfun('length',regexp(sprintf('%i',a),'1[1]*','match'))

Record holder, hard to beat this beast. LOL.

Bruno

Just for fun I wanted to see what a good For loop solution could do. I was totally surprised by how well it places in the pack. For the 'double' case, it is first on both my machines (32bit, winvista, 4GB,2007a .... 64bit,winxp,16GB,2007b), and for the 'logical' case, it is second. This using the same bench function we have been passing around.


    tic
    L = length(a);
    K = zeros(1,ceil(L/2));
    dff = 0;
    cnt = 1;

    for ii = 1:L
        if ~a(ii)
            K(cnt) = ii - dff - 1;
            if dff < ii-1
                cnt = cnt + 1;
            end
            dff = ii;
        end
    end

    if a(L)
        K(cnt) = ii - dff;
        K = K(1:cnt);
    else
        K = K(1:cnt-1);
    end
    t(7) = t(7) + toc;

On a similar note, what would be the simplest way to find location of ones in a binary string?

for example, I have
x = [0 0 1 0 1 0 1 1]

I would like to return

>>y
    3
    5
    7
    8

Thank you !!

Hira

"Hira Manzoor" <09020087@lums.edu.pk> wrote in message <h9ut4s$nku$1@fred.mathworks.com>...
> On a similar note, what would be the simplest way to find location of ones in a binary string?
>
> for example, I have
> x = [0 0 1 0 1 0 1 1]
>
> I would like to return
>
> >>y
> 3
> 5
> 7
> 8
>

find(x)

% Bruno

Hmmm.. that was pretty simple. I'm new to MATLAB and coding. My actual problem is that I want to create a strip with 8 bars at fixed locations. My ultimate purpose is to write a program that generates all possible 256 strips based on whether specific bars were present absent. One way could be use all binary numbers from 0 to 255 and bars should appear at locations where the binary number has ones. So my binary number is stored as a number not a matrix and find(x) doesn't help. Is there a way out for this or an easier way to do the above?

Thanks
Hira