Interesting Programming Problem, Need Some Help
Author Message
Interesting Programming Problem, Need Some Help

Here is a interesting problem that perhaps someone has solved
before or has an idea of how to program the solution.  Given a
square array (NxN) filled with zeros and ones (in practice, there
are many more zeros than ones), what is the distribution of patterns
of size 1, 2, 3, ...., where a pattern is defined any string of adjacent
1's, either horizontally or /and vertically distributed, and the number
of "singlets" is also of interest  To simply the problem, I'm ignoring
diagonal connections. For example, in the following array, there are:
5 ones, 1 two, 1 three, 2 fours, and 1 six.

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

APL and fortran solutions preferred, but any language appreciated.
Thanks, Leonard Howell

Mon, 06 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

Quote:

> Here is a interesting problem that perhaps someone has solved
> before or has an idea of how to program the solution.  Given a
> square array (NxN) filled with zeros and ones (in practice, there
> are many more zeros than ones), what is the distribution of patterns
> of size 1, 2, 3, ...., where a pattern is defined any string of adjacent
> 1's, either horizontally or /and vertically distributed, and the number
> of "singlets" is also of interest  To simply the problem, I'm ignoring
> diagonal connections. For example, in the following array, there are:
>  5 ones, 1 two, 1 three, 2 fours, and 1 six.

> 0 0 0 0 0 0 1 0
> 1 0 0 1 1 0 1 1
> 0 1 1 0 1 1 0 0
> 1 1 1 0 0 0 1 0
> 0 0 1 0 0 0 0 1
> 0 1 0 0 0 0 0 1
> 0 0 1 1 1 0 0 0
> 1 0 1 0 0 0 0 1

> APL and FORTRAN solutions preferred, but any language appreciated.
> Thanks, Leonard Howell

--
I can't offer code, but here is a simple approach.

The general idea is to scan all the cells in the matrix and count the
runs of which each cell is the anchor.  A cell is an anchor of a run if
it is the leftmost or bottommost cell in the run (those directions are
chosen arbitrarily).  Taking a vertical run as an example, a cell is the
bottommost of a run if its value is one and the position below it is
not.  Now count ones up the column to find the run length.  If the
length exceeds one, increment the corresponding frequency counter.  The
same idea works in other directions.  Since each run has exactly one
anchor, this algorithm can't count a row more than once.  If the code
looks for runs in four different directions, it will find each run.  If
a cell has four runs of length one, it's a singleton.

To make the programming easier in FORTRAN, start by appending rows of
zeros above and below the matrix, and appending columns of zeros at its
left and right edges.  Then loop over only the original matrix.

I think the algorithm can be executed for all cells in parallel for APL,
but I don't see how to count singletons cheaply in APL.
--------------------
Jonathan Fry
Developer
SPSS Inc.

Mon, 06 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

Quote:

> Here is a interesting problem that perhaps someone has solved
> before or has an idea of how to program the solution.  Given a
> square array (NxN) filled with zeros and ones (in practice, there
> are many more zeros than ones), what is the distribution of patterns
> of size 1, 2, 3, ...., where a pattern is defined any string of adjacent
> 1's, either horizontally or /and vertically distributed, and the number
> of "singlets" is also of interest  To simply the problem, I'm ignoring
> diagonal connections. For example, in the following array, there are:
>  5 ones, 1 two, 1 three, 2 fours, and 1 six.

> 0 0 0 0 0 0 1 0
> 1 0 0 1 1 0 1 1
> 0 1 1 0 1 1 0 0
> 1 1 1 0 0 0 1 0
> 0 0 1 0 0 0 0 1
> 0 1 0 0 0 0 0 1
> 0 0 1 1 1 0 0 0
> 1 0 1 0 0 0 0 1

> APL and FORTRAN solutions preferred, but any language appreciated.
> Thanks, Leonard Howell

First a question:

Would the following be interpreted as 2 ones and 1 three?

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

If so, then your problem is to find the longest path of all possible
paths ( 6 in your example ), then eliminate this path (by setting the
1's to 0's).  Then find the next longest path within the remaining paths
( one of the 2 fours in your example ). Then eliminate this path and so
on.  When there are no paths longer than 1 your are done.

I have written algorithms similar to this in the past.  For example, a
program to compute the "Knights Tour" (a problem in which you need to
find a path in which a chess knight can move to every square of a 6x6 or
larger grid without landing on the same square more than once.)

Jerry . . .

--

Custom Solutions              http://www.cs-software.com/
Charleston, SC  29418          Your source for discounted
Voice:  (843) 760 0597           Fortran compilers and
Fax:    (843) 552 3239             related software

Mon, 06 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

Quote:

> > Here is a interesting problem that perhaps someone has solved
> > before or has an idea of how to program the solution.  Given a
> > square array (NxN) filled with zeros and ones (in practice, there
> > are many more zeros than ones), what is the distribution of patterns
> > of size 1, 2, 3, ...., where a pattern is defined any string of adjacent
> > 1's, either horizontally or /and vertically distributed, and the number
> > of "singlets" is also of interest  To simply the problem, I'm ignoring
> > diagonal connections. For example, in the following array, there are:
> >  5 ones, 1 two, 1 three, 2 fours, and 1 six.

> > 0 0 0 0 0 0 1 0
> > 1 0 0 1 1 0 1 1
> > 0 1 1 0 1 1 0 0
> > 1 1 1 0 0 0 1 0
> > 0 0 1 0 0 0 0 1
> > 0 1 0 0 0 0 0 1
> > 0 0 1 1 1 0 0 0
> > 1 0 1 0 0 0 0 1

> > APL and FORTRAN solutions preferred, but any language appreciated.
> > Thanks, Leonard Howell

> --
> I can't offer code, but here is a simple approach.

> The general idea is to scan all the cells in the matrix and count the
> runs of which each cell is the anchor.  A cell is an anchor of a run if
> it is the leftmost or bottommost cell in the run (those directions are
> chosen arbitrarily).  Taking a vertical run as an example, a cell is the
> bottommost of a run if its value is one and the position below it is
> not.  Now count ones up the column to find the run length.  If the
> length exceeds one, increment the corresponding frequency counter.  The
> same idea works in other directions.  Since each run has exactly one
> anchor, this algorithm can't count a row more than once.  If the code
> looks for runs in four different directions, it will find each run.  If
> a cell has four runs of length one, it's a singleton.

> To make the programming easier in FORTRAN, start by appending rows of
> zeros above and below the matrix, and appending columns of zeros at its
> left and right edges.  Then loop over only the original matrix.

> I think the algorithm can be executed for all cells in parallel for APL,
> but I don't see how to count singletons cheaply in APL.
> --------------------
> Jonathan Fry
> Developer
> SPSS Inc.

--
Kindly ignore my reply above.  It solves a different problem.
--------------------
Jonathan Fry
Developer
SPSS Inc.

Mon, 06 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

Quote:

> Here is a interesting problem that perhaps someone has solved
> before or has an idea of how to program the solution.  Given a
> square array (NxN) filled with zeros and ones (in practice, there
> are many more zeros than ones), what is the distribution of patterns
> of size 1, 2, 3, ...., where a pattern is defined any string of adjacent
> 1's, either horizontally or /and vertically distributed, and the number
> of "singlets" is also of interest  To simply the problem, I'm ignoring
> diagonal connections. For example, in the following array, there are:
>  5 ones, 1 two, 1 three, 2 fours, and 1 six.

> 0 0 0 0 0 0 1 0
> 1 0 0 1 1 0 1 1
> 0 1 1 0 1 1 0 0
> 1 1 1 0 0 0 1 0
> 0 0 1 0 0 0 0 1
> 0 1 0 0 0 0 0 1
> 0 0 1 1 1 0 0 0
> 1 0 1 0 0 0 0 1

> APL and FORTRAN solutions preferred, but any language appreciated.
> Thanks, Leonard Howell

Let's generalize and suppose there are M rows and N columns, with M >= N
(you can always transpose the array to make this happen).  There is a
scanning algorithm that requires O(N) space and O(M*N) time, which is as
good as it gets.  The proof is by induction on the number of rows, M.
The algorithm requires a data structure that maintains information about
the distribution of patterns within the M X N array together with
information about the patterns that touch its bottom row.  For the
induction step, one updates this structure according to what's in the
next row.

Rather than be formal, I will proceed by example.  In the 8 X 8 array
presented, after scanning the first row I will represent the data
structure thus:

0 0 0 0 0 0 [1] 0

where the brackets enclose the tip of the lone identified pattern.
After scanning the second row, the data structure looks like this:

[1] 0 0 [2 2] 0 [3 3]

which echos the pattern of ones on the second row of the array, but also
remembers the size of each pattern in which those ones participate.  You
should be able to see that creating this updated structure requires only
the previous structure together with the new row, and that you only have
to scan the new row two or three times (or once, if you're clever with
pointers).  At the third step we get:

0 [2 2] 0 [4 4] 0 0     | 1, 3

where now, on the right, we begun to output the complete patterns that
have been identified.  The full algorithm for this pattern then looks
like:

0 0 0 0 0 0 [1] 0
[1] 0 0 [2 2] 0 [3 3]   |
0 [2 2] 0 [4 4] 0 0     | 1, 3
[5 5 5] 0 0 0 [1] 0     | 4
0 0 [6] 0 0 0 0 [1]     | 1
0 [1] 0 0 0 0 0 [2]     | 6
0 0 [3 3 3] 0 0 0       | 1, 2
[1] 0 [4] 0 0 0 0 [1]   |
| 1, 4, 1

The cumulative output, shown on the right, gives the desired result.
(To get the last bit of output, consider processing an additional row of
zeros.)

Actually, one of the most interesting aspects of the updating is not
used in this example, so let's look at the following array:

1 0 1
1 1 1
1 0 0

The algorithm proceeds as follows:

[1] 0 [1]
[5 5 5]         |
[6] 0 0         |
| 6

The interesting thing happened at the second step, where a row of three
ones overlapped two patterns.  They were merged.  Overall, though, it
should still be easy to see that the updating can occur in one pass,
left to right across each row, and that the data structure can't be any
bigger than a constant times the row size.

Here's another amusing example:

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

which is processed in this way:

[4 4 4 4]
[6 0 0 6]       |
[9 9 0 9]       |
[10] 0 [1] 0    |
| 10, 1

Here, in the second row, separate runs of 1s were connected to the same
pattern.  In general, adjacent pattern tips can merge during the
updating, pattern tips can disappear (and cause some output), and new
patterns can appear.

The trickiest part of all this is demonstrating that the data structure
can be represented succinctly as a disjoint series of intervals: in
other words, that you can't have any interleaving of the tips of two
patterns.  But this is clear, by a discrete analog of the Jordan curve
theorem, that states if you find a 1 that is the tip of one pattern, and
another 1 further on in the same row that is the tip of the same
pattern, then any intervening 1s must belong to the same pattern, even
if they are separated along that row by 0s.  The previous example
illustrates this.

This scanning algorithm clearly lends itself to a FORTRAN implementation
(which would actually scan left to right) rather than an APL one.  I
leave the details to an intrepid programmer.  Of course, since I've been
so informal (perhaps cryptic), it's also possible I've been wrong...
there's nothing like the rigor of writing a proof (or a working
program).

--Bill Huber
Quantitative Decisions
Merion, PA

Mon, 06 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

Quote:

> ...Given a square array (NxN) filled with zeros and ones

(in practice, there are many more zeros than ones), what
is the distribution of patterns of size 1, 2, 3, ...., where
a pattern is defined any string of adjacent 1's, either
horizontally or /and vertically distributed, and the number
of "singlets" is also of interest

Sounds like a transitive closure problem over the relation
of adjacency of occupied cells. A unique representative for
each connected component could also be found using the UNION/
FIND algorithms of Aho Hopcroft Ullman in almost linear time.

Quote:
> APL and FORTRAN solutions preferred, but any language appreciated.

Some background in J...

D m
.1.1...1
..11.1..
..111.11
.1....1.
.11...1.
..1.....
11.1....
.1..11.1

To select the cells
1 3 7 10 11 13 18 19 20 22 23 25 30 33 34 38 42 48 49 51 57 60 61 63
of which these
10 18 19 22 33 48 60
are connected rowwise to these
11 19 20 23 34 49 61
and similarly these
3 10 11 22 25 30 34 49
are connected columnwise to these
11 18 19 30 33 38 42 57

Give such relations (not forgetting the diagonal) one
just needs to construct the transitive closure then
select and count unique rows.

Several threads in comp.lang.apl have mentioned algorithms
for transitive closure (16 hits in dejanews for "transitive
and closure"). In particular Tom Chwastyk quotes one in
APL (as opposed to the J above;)

greg heil

http://www.scn.org/tl/anvil

Mon, 06 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

If B is a binary array,
B {is},B,0
Then
{rho}{each}({not}B){enclose}B
will list the length of individual strings
Z V (Denny) Jizba

Wed, 08 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

Quote:

> > ...Given a square array (NxN) filled with zeros and ones

(in practice, there are many more zeros than ones), what
is the distribution of patterns of size 1, 2, 3, ...., where
a pattern is defined any string of adjacent 1's, either
horizontally or /and vertically distributed, and the number
of "singlets" is also of interest

Quote:
> Sounds like a transitive closure problem over the relation

of adjacency of occupied cells. A unique representative for
each connected component could also be found using the UNION/
FIND algorithms of Aho Hopcroft Ullman in almost linear time.

Now that i think of it UNION/FIND is the way to go. Given the
set of equations between cells developed below the UNION algorithm
builds a forest of trees. When two trees are equated it walks up
one (FIND) planting the other (and each node on the path) at the top
of the other. Processing all equations thusly gives one tree for each
connected component. A second pass is required to count the sizes
of the trees. This stage uses FIND which starts at a node (occupied
cell in the original array) and walks to the root (bringing up all
nodes on the path) at the top, one would increment a counter. At
the end of this stage you have a labeling as well.

Timing of the algorithm is _ever so slightly_ super linear, by
a factor related to the inverse of Ackermans function. The tree
walk/lifting is a tad tricky but i did do it in '73 in APL (w/o
AHU's help;) and could probably be induced to do it again if you

Quote:
> Some background in J...
>         D m
> .1.1...1
> ..11.1..
> ..111.11
> .1....1.
> .11...1.
> ..1.....
> 11.1....
> .1..11.1
> To select the cells
>         adj=: ,# [:i. [:*/ \$
> 1 3 7 10 11 13 18 19 20 22 23 25 30 33 34 38 42 48 49 51 57 60 61 63
> of which these
> 10 18 19 22 33 48 60
> are connected rowwise to these
> 11 19 20 23 34 49 61
> and similarly these
> 3 10 11 22 25 30 34 49
> are connected columnwise to these
> 11 18 19 30 33 38 42 57

Gathering the above together

left=: 13 : '0 1+/adj y.*.1|.!.0"1 y.'
above=: 13 : '(0,#y.)+/ adj y.*.1|.!.0 y.'
(left,.above) m
10 18 19 22 33 48 60  3 10 11 22 25 30 34 49
11 19 20 23 34 49 61 11 18 19 30 33 38 42 57

Which are the equations that would need to be run on the forest
seeded by

Using more complicated connectivity criteria, this is a common
step in image analysis.

greg heil

http://www.scn.org/tl/anvil

Wed, 08 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

Quote:

> If B is a binary array,
>  B {is},B,0
> Then
> {rho}{each}({not}B){enclose}B
> will list the length of individual strings
>  Z V (Denny) Jizba

Sorry for the error! There should NOT be the {not} in the second
expression. I was too hasty. Try the following sequence of APL2
expressions:
B {is} 40>?10 10{rho}100
B
V{is},B,0
N{is}{enlist}{rho}{each}V{enclose}V
S{is}{ceiling}{reduce}N
({iota}S}),[1.5]+{reduce}({iota}S){jot}.=N
for patterns in the vertical direction try
V{is},({transpose}B),0
for diagonal patterns try
V{is},(({iota}{take}{rho}B){reverse}B),0
and  V{is},((-{iota}{take}{rho}B){reverse}B),0
ZVJ

Wed, 08 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

Quote:

>Here is a interesting problem that perhaps someone has solved
>before or has an idea of how to program the solution.  Given a
>square array (NxN) filled with zeros and ones (in practice, there
>are many more zeros than ones), what is the distribution of patterns
>of size 1, 2, 3, ...., where a pattern is defined any string of adjacent
>1's, either horizontally or /and vertically distributed, and the number
>of "singlets" is also of interest  To simply the problem, I'm ignoring
>diagonal connections. For example, in the following array, there are:
> 5 ones, 1 two, 1 three, 2 fours, and 1 six.

>0 0 0 0 0 0 1 0
>1 0 0 1 1 0 1 1
>0 1 1 0 1 1 0 0
>1 1 1 0 0 0 1 0
>0 0 1 0 0 0 0 1
>0 1 0 0 0 0 0 1
>0 0 1 1 1 0 0 0
>1 0 1 0 0 0 0 1

>APL and FORTRAN solutions preferred, but any language appreciated.
>Thanks, Leonard Howell

What you are looking for, in other words, is the distribution of the sizes of
the cliques in the table, where adjacency is in the horizontal/vertical
direction.

In short, the solution can be expressed as (in a pseudo-J):

solution M : freq {rho}{each} cliques adjacencymatrix M

adjacencymatrix M:   ( | (-/~) where M) e. 0,1,({rho}M)[2]

where M:   #([:i.#)

cliques M :   nub {enclose}[2]transitiveclosure M

nub V:  (nubsieve V)/V
or as  (~:#) or ~. in J

nubsieve V:  (V{iota}V)={iota}{shape}V
or as ~: in J

transitiveclosure M:   ({and}.{or})^:_  M

--
|\/| Randy A MacDonald       | I'm a boy, I want details.

BSc(Math) UNBF '83      | APL: If you can say it, it's done.

| Also http://www.godin.on.ca/randy
------------------------------------------------<-NTP>----{ gnat }-

Thu, 09 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

Leonard Howell wrote on May 21:

Quote:
> Here is a interesting problem that perhaps someone has solved before
> or has an idea of how to program the solution.  Given a square array
> (NxN) filled with zeros and ones (in practice, there are many more
> zeros than ones), what is the distribution of patterns of size 1, 2,
> 3, ...., where a pattern is defined any string of adjacent 1's,
> either horizontally or /and vertically distributed, and the number
> of "singlets" is also of interest  To simply the problem, I'm
> ignoring diagonal connections. For example, in the following array,
> there are:  5 ones, 1 two, 1 three, 2 fours, and 1 six.

This is a variation/subset of the "blob finder" problem.  Once you know
the frequency of different size blobs, it seems likely that a followup
request will be to identify the individual blobs in the matrix.

Here's my algorithm for finding blobs:

* Visit each nonzero cell (top to bottom, left to right)

* If the cell is 1, assign it a new blob index (>= 2)

* Examine the following neighbors of the cell:
. . .
. X n
n n n

* If a neighbor is 1, replace it with X's blob index

* If a neighbor is not 1 or 0, remember that blob n is
equivalent to blob X

* After visiting all the cells, make another pass through the
matrix, recoding the initial blob indices to merge equivalent
blobs and use sequential indices

The blob population counts can be accumulated by bumping a counter
whenever you change a 1 to a blob index.

This algorithm has enough inherent iterativeness that I didn't spend
much time trying to "parallelize" it for fast APL execution.  A
straightforward iterative coding (for the APL+ dialect) is given below.
It would make an interesting test for Bob Bernecky's APEX APL compiler,
or it could be translated to a conventional compiled language.  If it's
really going to be run using an interpreter, further improvements could
be made.  (In particular, the :For K loop could be parallelized easily
if Dyalog APL's P[i]{<-}.+1 feature were available in APL+.)

to vertical and horizontal lines.  Line [16] can be modified if you
want to ignore diagonal neighbors.  If you don't want the blob indices
and can't afford the space taken by the integer version of the matrix,
the code could be modified to work with just two rows of the Boolean
matrix at a time (as Bill Huber suggested).

Here are some examples:

B{<-}1=?10 15{rho}4
B
0 0 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 1 1 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 0 1
0 0 0 0 1 0 0 1 0 1 0 0 0 0 0
0 1 0 0 1 1 0 0 0 0 1 1 1 0 1
0 0 1 0 0 0 1 1 1 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0 0 0 0 0

DISP BLOBS B
. . . . . . B . . . . A . . .     3  1    <- three singletons
. . . . B B B . . . . . . . .     2  2    <- two doubles
. . . . . . . . . . . . . . .     2  4
C C . . . D D . . . . . E . E     1  5
. . . . . . . . . . . . . E .     1 13    <- one 13-item blob
. . . . . . . . . F . . E . E
. . . . F . . G . F . . . . .
. H . . F F . . . . F F F . I
. . H . . . F F F F . . . . .
. H H . . . F . . . . . . . .

B8
0 0 0 0 0 0 1 0                 Leonard's example
1 0 0 1 1 0 1 1
0 1 1 0 1 1 0 0
1 1 1 0 0 0 1 0
0 0 1 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 1 1 1 0 0 0
1 0 1 0 0 0 0 1

DISP BLOBS1 B8             BLOBS1 ignores diagonal neighbors
. . . . . . A .     5 1
B . . C C . A A     1 2
. D D . C C . .     1 3
D D D . . . E .     2 4
. . D . . . . F     1 6
. G . . . . . F
. . H H H . . .
I . H . . . . J

And here's the code:

{del} Z{<-}BLOBS B;A;C;F;I;J;K;P;R;S;T;U

[18]

[22]

[30]          :Endif

[32]      :Endif
[33]

[36]          T{<-}{enclose}I J+K

[38]          :Select A
[39]          :Caselist 0 U

[45]              ((R=R[A])/R){<-}U

[48]          :Endselect
[49]      :Endfor
[50]

[53]

[55]  P{<-}C{take}P
[56]

[59]  U{<-}T={iota}{rho}T{<-}R

[61]  T{<-}0,T[R]-1

[64]  Z{<-}T[1+Z]
[65]

[69]  F{<-}T[;2]GROUPEDSUM(1{take}{rho}T){rho}1 {+

[70]
[71]  Z{<-}(1 1{drop}{neg}1 {neg}1{drop}Z) ({reverse}F) {+

{del}

{del} Z{<-}G GROUPEDSUM D;L;T

[13]  D{<-}D[T]

{del}

{del} Z{<-}DISP A;F

[2]   Z F{<-}A
[3]   Z{<-}((2{times}2{pick}{rho}Z){rho}1 0)\('.',65{drop}#AV)[1+Z]
[4]   Z{<-}Z F
{del}

http://www.chilton.com/~jimw/aplascii.html .

Jim

Thu, 09 Nov 2000 03:00:00 GMT
Interesting Programming Problem, Need Some Help

:Leonard Howell wrote on May 21:
:
:> Here is a interesting problem that perhaps someone has solved before
:> or has an idea of how to program the solution. Given a square array
:> (NxN) filled with zeros and ones (in practice, there are many more
:> zeros than ones), what is the distribution of patterns of size 1, 2,
:> 3, ...., where a pattern is defined any string of adjacent 1's,
:> either horizontally or /and vertically distributed [...]
:
:This is a variation/subset of the "blob finder" problem. Once you know
:the frequency of different size blobs, it seems likely that a followup
:request will be to identify the individual blobs in the matrix.
:
:Here's my algorithm for finding blobs:
:
: * Visit each nonzero cell (top to bottom, left to right)
: * If the cell is 1, assign it a new blob index (>= 2)
: * Examine the following neighbors of the cell:
: . . .
: . X n
: n n n
: [snip rest of Jim's algorithm]

I happen to be working on almost the same problem right now. I have
scanned a sea map, and the blobs are islands, of course, which i extract
as objects for the 3D virtual reality.

The main problem is the speed, as we heard. In an experimental function, i
follow the edges of the blobs by finding the next pixel of the edge
(counter-clockwise) using the comparison against 8 surrounding pixels, as
Jim mentioned above. This is quite slow when the bitmap is 1000 x 1500
pixels (boolean) and the archipelago is dense.

It seems to be easiest to have a variable (nested vector) with the values
(-1 0) (-1 -1) (0 -1) ... (-1 1) for the neighbor pixels, then add it to
the current Y,X and look for the first hit. For each comparison, i rotate
the vector so that the direction i came from is the last compared place.
Each island can be given individual numbers. Filling the islands with the
same numbers would probably be a question of turning on and off ones (at
...0 1 0... places horizontally, with some special cases), and some multip
lication... Found islands can be "turned to zero", which speeds up finding
the entry point for the next search/test (a vertical {iota}1 for the
current or next column).

A solution that would do it all in a single step (8 single steps?), would
definitely create several of those animals (memory elephants, that is)...
Indeed (with regards to Randy) is this blobfinding one of the businesses
for which APL is not the most suitable.

Tomas

Fri, 10 Nov 2000 03:00:00 GMT

 Page 1 of 2 [ 23 post ] Go to page: [1] [2]

Relevant Pages