Thread Subject: Region overlap

Given two arrays (considering as blobs/connected component
labels in an image) what is the fastest way to figure out an
overlap:

Lets say we have these two arrays:
[ 0 1 0 0 0 0
  1 1 1 0 0 0
  1 1 0 0 0 0
  0 0 0 0 0 0
  0 0 0 0 0 0
  0 0 0 0 0 0 ]

and
[ 0 0 0 0 0 0
  0 0 1 1 0 0
  0 0 1 1 1 0
  0 0 1 0 1 0
  0 0 0 0 0 0
  0 0 0 0 0 0 ]

Whats the fastest way to figure out that the regions in
these two matrics overlap. (There will be only a sinlge
connected component per matrix). Can I avoid and'ing the
whole two matrices and then find the answer??

"Ahmad " <ahmad.humyn@gmail.com> wrote in message <g7sb26
$srr$1@fred.mathworks.com>...
> Given two arrays (considering as blobs/connected component
> labels in an image) what is the fastest way to figure out
an
> overlap:
>
> Lets say we have these two arrays:
> [ 0 1 0 0 0 0
> 1 1 1 0 0 0
> 1 1 0 0 0 0
> 0 0 0 0 0 0
> 0 0 0 0 0 0
> 0 0 0 0 0 0 ]
>
> and
> [ 0 0 0 0 0 0
> 0 0 1 1 0 0
> 0 0 1 1 1 0
> 0 0 1 0 1 0
> 0 0 0 0 0 0
> 0 0 0 0 0 0 ]
>
> Whats the fastest way to figure out that the regions in
> these two matrics overlap. (There will be only a sinlge
> connected component per matrix). Can I avoid and'ing the
> whole two matrices and then find the answer??

Why not convert the matrices to sparse form and then "and"
them together?

"Matt " <mjacobson.removethis@xorantech.com> wrote in
message <g7sbon$867$1@fred.mathworks.com>...
> "Ahmad " <ahmad.humyn@gmail.com> wrote in message <g7sb26
> $srr$1@fred.mathworks.com>...
> > Given two arrays (considering as blobs/connected component
> > labels in an image) what is the fastest way to figure out
> an
> > overlap:
> >
> > Lets say we have these two arrays:
> > [ 0 1 0 0 0 0
> > 1 1 1 0 0 0
> > 1 1 0 0 0 0
> > 0 0 0 0 0 0
> > 0 0 0 0 0 0
> > 0 0 0 0 0 0 ]
> >
> > and
> > [ 0 0 0 0 0 0
> > 0 0 1 1 0 0
> > 0 0 1 1 1 0
> > 0 0 1 0 1 0
> > 0 0 0 0 0 0
> > 0 0 0 0 0 0 ]
> >
> > Whats the fastest way to figure out that the regions in
> > these two matrics overlap. (There will be only a sinlge
> > connected component per matrix). Can I avoid and'ing the
> > whole two matrices and then find the answer??
>
> Why not convert the matrices to sparse form and then "and"
> them together?
>
>
>
Hmmm ... good idea. I think, it will be probably much than
an and with full matrices, but with being beginner, I can't
vouch for it. Does anybody know would time complexity
improve with a sparse matrix?

In article <g7sb26$srr$1@fred.mathworks.com>,
Ahmad <ahmad.humyn@gmail.com> wrote:
>Given two arrays (considering as blobs/connected component
>labels in an image) what is the fastest way to figure out an
>overlap:

There is almost never *a* fastest way in Matlab: it almost
always depends upon factors such as the matrix size and whether
the code has been fully JIT (Just In Time Compiled).
An algorithm that works best on 1024 x 2048 matrices might
not be the best algorithm for 2048 x 1024 matrices -- and which
algorithm is fastest can depend upon whether you created another
variable in-between creating the two matrices (as that can affect
whether the matrices happen to fall on the same processor cache lines
or not.)

There is an important clue in your posting that you aren't
-really- asking for the *fastest* way to do the calculation:
you neglected to include any information about your operating
system, your exact processor and speed, how much primary and secondary
cache you have, your FSB (Front Side Bus) speed, whether you have
SSE3, nor any information about exactly which toolboxes you
have, nor any information about how big the matrices are and
how populated they are (i.e., whether sparse operations might
become relavant.) This kind of information is important if you
want to be able to shave the last 2 nanoseconds off of the
performance, as would be required of the FASTEST way. "Fastest"
is a superlative, an absolute term: no way can be "fastest" unless
there is no method which is -ever- faster.

If you what you want is an algorithm with the lowest algorithmic
complexity... you'd still need to specify whether you are looking
for best average complexity or best worst-case complexity, and you'd
want to take into account that due to constants of addition and
constants of multiplications, an algorithm with the lowest algorithmic
complexity might not be the fastest way to compute something until
you get up to object sizes of 10^100 (or more).
--
  "Nothing recedes like success." -- Walter Winchell

> Hmmm ... good idea. I think, it will be probably much than
> an and with full matrices, but with being beginner, I
can't
> vouch for it. Does anybody know would time complexity
> improve with a sparse matrix?


Hmmm. Actually, when I try the following experiment, it
turns out to be much faster to manipulate logical arrays,

>> A=spones(sprand(1000,1000,.3));
>> B=spones(sprand(1000,1000,.3));
>> tic; A&B;toc
Elapsed time is 0.024451 seconds.

>> AA=logical(A); BB=logical(B);
>> tic; AA&BB;toc
Elapsed time is 0.005195 seconds.


In any case, these times seem pretty fast, granted only
with the data sizes that I've chosen and on my particular
machine.

Are you really having such a problem with speed?