Interesting Programming Problem, Need Some Help
Author 
Message 
Leonard Howel #1 / 23

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 


Jonathan Fr #2 / 23

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 


Jerry A Gree #3 / 23

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.cssoftware.com/ 7638 Oldridge Road 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 


Jonathan Fr #4 / 23

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 


whube #5 / 23

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 


Greg Hei #6 / 23

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 adj=: ,# [:i. [:*/ $ adj m 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 adj m*.1.!.0"1 m 10 18 19 22 33 48 60 are connected rowwise to these 1+adj m*.1.!.0"1 m 11 19 20 23 34 49 61 and similarly these adj m*.1.!.0 m 3 10 11 22 25 30 34 49 are connected columnwise to these 8+adj m*.1.!.0 m 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 


Zdenek V Jizb #7 / 23

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 


Greg Hei #8 / 23

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 find AHU inadequate. 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. [:*/ $ > adj m > 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 > adj m*.1.!.0"1 m > 10 18 19 22 33 48 60 > are connected rowwise to these > 1+adj m*.1.!.0"1 m > 11 19 20 23 34 49 61 > and similarly these > adj m*.1.!.0 m > 3 10 11 22 25 30 34 49 > are connected columnwise to these > 8+adj m*.1.!.0 m > 11 18 19 30 33 38 42 57
Gathering the above together adj=: ,# [:i. [:*/ $ 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 adj m 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 


Zdenek V Jizb #9 / 23

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 


Randy MacDona #10 / 23

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 pseudoJ): 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 freq: (head,#)/.  \/ 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 


Jim Weigan #11 / 23

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+.) As written, the program follows links along diagonal lines in addition 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 13item 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} For more information about the {keywords} used above, see http://www.chilton.com/~jimw/aplascii.html . Jim

Thu, 09 Nov 2000 03:00:00 GMT 


Tomas Gustafsso #12 / 23

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 (counterclockwise) 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] 
