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/
