Re: [computer-go] Re: Euler numbers
At 10:19 AM 11/27/2007, you wrote: ... 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. ... i also used to work with steve and dave. steve replied to a post i just sent him with: ... Euler number (an ambiguous designation, not recognized by most mathematicians) is easily calculated this way. Let Q1=the number of 2x2 neighborhoods with this configuration: X 0 0 1, and let Q3 be the number of these: X 1 1 0, where X is don't care. Then E=Q1-Q3. The Q's are counted with a raster sweep that moves across and down by one cell, so a given pixel is examined four times. Also E=B-H where B is the number of blobs (connected sets of 1's) and H is the number of holes (connected sets of 0's inside blobs). This formula for E does not treat the following patterns optimally, but it can be improved by making it slightly more complicated. 1 0 0 1 and 0 1 1 0. Holes on the edge can be counted by surrounding the image with a frame of 1's, but separate blobs touching the edge will become connected. It's been 36 years since I published this work (IEEE Trans. Computers, May 1971) so I may not recall everything perfectly. Incidentally, 2x2 neighborhoods are much better for tracing boundaries than 3x3, being faster and less ambiguous in crowded areas. I thought about the Go problem a little but never wrote any code. I'm not sure how much help the Euler number stuff would be. I got to be about low intermediate as a player. Steve Gray ... thanks --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: euler numbers
Here are some links I found while reading the Euler numbers thread. The first one is mentioned by Don and looks very useful for building an actual algorithm. Its A Novel Morphological Operator To Calculate Euler Number by Zhang and Stoecker. http://scholarsmine.umr.edu/post_prints/pdf/00930291_09007dcc8030c7df.pdf Next is the Gray paper Local Properties of Binary Images in Two Dimensions. http://turing.iimas.unam.mx/~elena/CompVis/Gray71BinaryImages.pdf This paper has a brief description of the Quad algorithm applied to a game called Lines of Action (LOA). http://www.cs.unimaas.nl/m.winands/documents/The_Quad_Heuristic_in_Lines_of_ Action.pdf Finally, there is this brief paper by my old undergraduate adviser at MIT that extends the Euler number calculation to continuous gray scale domains, but also briefly mentions the discrete case. http://people.csail.mit.edu/bkph/articles/APE_continuous.pdf Chuck Paulson www.PuffinwareLLC.com http://www.puffinwarellc.com/ iMetaSearch - indexing and clustering search results with Latent Semantic Analysis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Euler numbers
On 27/11/2007, Dave Dyer [EMAIL PROTECTED] 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 Thanks for this Dave. Does anyone else find the poor scan ironic, given what this was used for? BTW: my library (the Bodleian) claims to have this, I can look it up if anyone needs clarifications on the scan. cheers stuart ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Euler numbers
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/
[computer-go] Re: Euler numbers
... 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? That one is news to me. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Euler numbers
Dave Dyer wrote: ... 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? That one is news to me. The version of that paper I found was also scanned.It's only 3 pages long and it get's right to the point. Thanks for the help on this. - Don ___ 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/
