Hi Dave, Yes, I eventually figured out how to do the quad counting on scan lines. You only need 2 quad patterns when using scan lines of the image and for small boards you can do almost everything with a single loop and a lookup table.
Steve Gray's article was helpful to me and I also found "A Novel Morphological Operator to Calculate Euler Number" by Zhao Zhang, Randy H. Moss and William V. Stoecker. Did you scan that article too? It was very useful to me. In fact it had all the information I needed to figure out how to do the scan line version. I was difficult finding a free version of these articles. - Don Dave Dyer wrote: > Actually, I'm the main party responsible for propagating this technique > on the web. The scanned pages were scanned by me. I use this Euler > technique in my Lines of Action programs, where it is much more directly > applicable to detecting a won position. > > Back at my first computer job, where Steve Gray was a mentor, we had a > special purpose computer called a BIP which did this quad counting as a > basic operation. It was used in an OCR system (officially) but also > ran the worlds fastest "Life" implementation at the time. > > Quad counting is only marginally applicable to Go. You could use it > to determine if a collection of stones is closed and if it has an eye, > but there are so many shape/connectivity variations that ought to be > counted as connected or not depending on higher level analysys, I doubt > it would be very useful. > > -- but it's really easy to do, either in a one-pass scan or incremetally; > basically design a scan to count the number of occurrences of each 2x2 > neighborhood type, then do some simple arithmetic on the gross counts. > http://boardspace.net/loa/english/loa-programmer.html > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
