# HG changeset patch # User Laman # Date 2017-04-14 10:31:16 # Node ID 0d57edb8be11235ce0f3fa1662bb6e028ee90316 # Parent a86d59fab023efa3d5d0427580b8bfd0faccbae1 got rid of CRLF line ends diff --git a/src/corners.py b/src/corners.py --- a/src/corners.py +++ b/src/corners.py @@ -1,95 +1,95 @@ -from epoint import EPoint - - -class Corners: - def __init__(self): - self.corners=[] - - ## Adds a new corner if there are less than four, replaces the closest otherwise. - def add(self,x,y): - a=EPoint(x,y) - # for i,c in enumerate(self.corners): # move an improperly placed point - # if a.dist(c)<20: - # self.corners[i]=a - # return - - if len(self.corners)<4: # add a new corner - self.corners.append(a) - - if len(self.corners)<4: - return - - index,minDist=0,float('inf') # replace the corner closest to the clicked point - for i,c in enumerate(self.corners): - if a.dist(c) KLMN | ABC | ABD | ACD | BCD | index | swap - # ------------ | :-: | :-: | :-: | :-: | ----: | ---- - # A BCD | + | + | + | + | 15 | 0 - # A BDC | + | + | - | - | 12 | CD - # A CBD | - | + | + | - | 6 | BC - # A CDB | - | - | + | + | 3 | AB - # A DBC | + | - | - | + | 9 | AD - # A DCB | - | - | - | - | 0 | BD - # - # For every non-degenerate quadrangle, there must be 1-3 edges going right-left (from a higher to a lower x coordinate). - # From these pick the one with the lowest slope (dy/dx) and declare its ending point the upper left corner. For the same slope pick the one further left. - # - # @return True for a convex quadrangle, False for concave and degenerate cases. - def canonizeOrder(self): - if len(self.corners)!=4: return False # erroneus call - - a,b,c,d=self.corners - abc=doubleTriangleArea(a,b,c) - abd=doubleTriangleArea(a,b,d) - acd=doubleTriangleArea(a,c,d) - bcd=doubleTriangleArea(b,c,d) - - if any(x==0 for x in (abc,abd,acd,bcd)): return False # collinear degenerate - - swaps=[(1,3),(0,1),(1,2),(0,3),(2,3),(0,0)] - index=(8 if abc>0 else 0)|(4 if abd>0 else 0)|(2 if acd>0 else 0)|(1 if bcd>0 else 0) - if index%3!=0: return False # concave degenerate - swap=swaps[index//3] - - self.corners[swap[0]], self.corners[swap[1]] = self.corners[swap[1]], self.corners[swap[0]] # counter-clockwise order - - kIndex=None - lowestSlope=float("inf") - - for i,corner in enumerate(self.corners): # find the NK edge: going right-left with the lowest slope, secondarily the one going down - ii=(i+1)%4 - slope=abs(getSlope(corner,self.corners[ii])) - if corner.x>self.corners[ii].x and (slope KLMN | ABC | ABD | ACD | BCD | index | swap + # ------------ | :-: | :-: | :-: | :-: | ----: | ---- + # A BCD | + | + | + | + | 15 | 0 + # A BDC | + | + | - | - | 12 | CD + # A CBD | - | + | + | - | 6 | BC + # A CDB | - | - | + | + | 3 | AB + # A DBC | + | - | - | + | 9 | AD + # A DCB | - | - | - | - | 0 | BD + # + # For every non-degenerate quadrangle, there must be 1-3 edges going right-left (from a higher to a lower x coordinate). + # From these pick the one with the lowest slope (dy/dx) and declare its ending point the upper left corner. For the same slope pick the one further left. + # + # @return True for a convex quadrangle, False for concave and degenerate cases. + def canonizeOrder(self): + if len(self.corners)!=4: return False # erroneus call + + a,b,c,d=self.corners + abc=doubleTriangleArea(a,b,c) + abd=doubleTriangleArea(a,b,d) + acd=doubleTriangleArea(a,c,d) + bcd=doubleTriangleArea(b,c,d) + + if any(x==0 for x in (abc,abd,acd,bcd)): return False # collinear degenerate + + swaps=[(1,3),(0,1),(1,2),(0,3),(2,3),(0,0)] + index=(8 if abc>0 else 0)|(4 if abd>0 else 0)|(2 if acd>0 else 0)|(1 if bcd>0 else 0) + if index%3!=0: return False # concave degenerate + swap=swaps[index//3] + + self.corners[swap[0]], self.corners[swap[1]] = self.corners[swap[1]], self.corners[swap[0]] # counter-clockwise order + + kIndex=None + lowestSlope=float("inf") + + for i,corner in enumerate(self.corners): # find the NK edge: going right-left with the lowest slope, secondarily the one going down + ii=(i+1)%4 + slope=abs(getSlope(corner,self.corners[ii])) + if corner.x>self.corners[ii].x and (slope=self.boardSize or row<0 or row>=self.boardSize: return False # out of range - if self.temp[row][col]: return False # already visited - if self.board[row][col]==EMPTY: return True # found a liberty - if self.board[row][col]!=color: return False # opponent's stone - self.temp[row][col]=True # set visited - return self._floodFill(color,row,col-1) or self._floodFill(color,row,col+1) or self._floodFill(color,row-1,col) or self._floodFill(color,row+1,col) # check neighbors - - ## Removes stones at coordinates marked with True in self.temp. - def _remove(self): - for r in range(self.boardSize): - for c in range(self.boardSize): - if self.temp[r][c]: self.board[r][c]=EMPTY - - -def exportBoard(board): - substitutions={EMPTY:".", BLACK:"X", WHITE:"O"} - return "\n".join("".join(substitutions.get(x,"?") for x in row) for row in board) +EMPTY=0 +BLACK=1 +WHITE=-1 + + +class Go: + ## Initializes self.board to a list[r][c]=EMPTY. + def __init__(self,boardSize=19): + self.boardSize=boardSize + self.board=[[EMPTY]*self.boardSize for x in range(boardSize)] + + ## Executes a move. + # + # Doesn't check for kos. Suicide not allowed. + # + # @param color BLACK or WHITE + # @return True on success, False on failure (illegal move) + def move(self,color,row,col): + if self.board[row][col]!=EMPTY: return False + + self.board[row][col]=color + + # capture neighbors + for r,c in ((-1,0),(1,0),(0,-1),(0,1)): + self.temp=[[False]*self.boardSize for x in self.board] + if not self._floodFill(-color,row+r,col+c): self._remove() + + # check for suicide + self.temp=[[False]*self.boardSize for x in self.board] + if not self._floodFill(color,row,col): + self.board[row][col]=EMPTY + return False + return True + + ## Checks for liberties of a stone at given coordinates. + # + # The stone's group is marked with True in self.temp, ready for capture if needed. Recursively called for stone's neighbors. + # + # @return True if alive, False if captured + def _floodFill(self,color,row,col): + if col<0 or col>=self.boardSize or row<0 or row>=self.boardSize: return False # out of range + if self.temp[row][col]: return False # already visited + if self.board[row][col]==EMPTY: return True # found a liberty + if self.board[row][col]!=color: return False # opponent's stone + self.temp[row][col]=True # set visited + return self._floodFill(color,row,col-1) or self._floodFill(color,row,col+1) or self._floodFill(color,row-1,col) or self._floodFill(color,row+1,col) # check neighbors + + ## Removes stones at coordinates marked with True in self.temp. + def _remove(self): + for r in range(self.boardSize): + for c in range(self.boardSize): + if self.temp[r][c]: self.board[r][c]=EMPTY + + +def exportBoard(board): + substitutions={EMPTY:".", BLACK:"X", WHITE:"O"} + return "\n".join("".join(substitutions.get(x,"?") for x in row) for row in board) diff --git a/src/grid.py b/src/grid.py --- a/src/grid.py +++ b/src/grid.py @@ -1,72 +1,72 @@ -import numpy -from epoint import EPoint - - -## Projective transformation of a point with a matrix A. -# -# Takes a point as a horizontal vector, transposes it and multiplies with A from left. -# -# @return transformed point as a numpy.array -def transformPoint(point,A): - return (A*numpy.matrix(point).transpose()).getA1() - - -class Grid: - ## Creates a Grid from the provided Corners object. - # - # Finds the vanishing points of the board lines (corner points define perspectively transformed parallel lines). The vanishing points define the image horizon. - # - # The horizon can be used to construct a matrix for affine rectification of the image (restoring parallel lines parallelism). We transform the corner points by this matrix, - # interpolate them to get proper intersections' coordinates and then transform these back to get their placement at the original image. - # - # The result is stored in grid.intersections, a boardSize*boardSize list with [row][column] coordinates. - # - # @param corners list of EPoints in ABCD order per corners.Corners.canonizeOrder(). - # !! Needs a check for proper initialization. - def __init__(self,corners): - # ad - # bc - a,b,c,d=[c.toProjective() for c in corners] - - p1=numpy.cross(a,b) - p2=numpy.cross(c,d) - vanish1=numpy.cross(p1,p2) - # !! 32 bit int can overflow. keeping it reasonably small. might want to use a cleaner solution - vanish1=EPoint.fromProjective(vanish1).toProjective() # !! EPoint fails with point in infinity - - p3=numpy.cross(a,d) - p4=numpy.cross(b,c) - vanish2=numpy.cross(p3,p4) - vanish2=EPoint.fromProjective(vanish2).toProjective() - - horizon=numpy.cross(vanish1,vanish2) - - horizon=EPoint.fromProjective(horizon).toProjective() - - rectiMatrix=numpy.matrix([horizon,[0,1,0],[0,0,1]]) - rectiMatrixInv=numpy.linalg.inv(rectiMatrix) - - - affineCorners=[EPoint.fromProjective(transformPoint(x,rectiMatrix)) for x in (a,b,c,d)] - x=[affineCorners[0]-affineCorners[3],affineCorners[1]-affineCorners[2],affineCorners[0]-affineCorners[1],affineCorners[3]-affineCorners[2]] - - self.intersections=[] - boardSize=19 - for r in range(boardSize): - self.intersections.append([None]*boardSize) - rowStart=(affineCorners[0]*(boardSize-1-r)+affineCorners[1]*r) / (boardSize-1) - rowEnd=(affineCorners[3]*(boardSize-1-r)+affineCorners[2]*r) / (boardSize-1) - - for c in range(boardSize): - affineIntersection=(rowStart*(boardSize-1-c)+rowEnd*c) / (boardSize-1) - self.intersections[r][c]=EPoint.fromProjective(transformPoint(affineIntersection.toProjective(),rectiMatrixInv)) - - def stoneSizeAt(self,r,c): - intersection=self.intersections[r][c] - - if c>0: width=intersection.x - self.intersections[r][c-1].x - else: width=self.intersections[r][c+1].x - intersection.x - if r>0: height=intersection.y - self.intersections[r-1][c].y - else: height=self.intersections[r+1][c].y - intersection.y - - return (width,height) +import numpy +from epoint import EPoint + + +## Projective transformation of a point with a matrix A. +# +# Takes a point as a horizontal vector, transposes it and multiplies with A from left. +# +# @return transformed point as a numpy.array +def transformPoint(point,A): + return (A*numpy.matrix(point).transpose()).getA1() + + +class Grid: + ## Creates a Grid from the provided Corners object. + # + # Finds the vanishing points of the board lines (corner points define perspectively transformed parallel lines). The vanishing points define the image horizon. + # + # The horizon can be used to construct a matrix for affine rectification of the image (restoring parallel lines parallelism). We transform the corner points by this matrix, + # interpolate them to get proper intersections' coordinates and then transform these back to get their placement at the original image. + # + # The result is stored in grid.intersections, a boardSize*boardSize list with [row][column] coordinates. + # + # @param corners list of EPoints in ABCD order per corners.Corners.canonizeOrder(). + # !! Needs a check for proper initialization. + def __init__(self,corners): + # ad + # bc + a,b,c,d=[c.toProjective() for c in corners] + + p1=numpy.cross(a,b) + p2=numpy.cross(c,d) + vanish1=numpy.cross(p1,p2) + # !! 32 bit int can overflow. keeping it reasonably small. might want to use a cleaner solution + vanish1=EPoint.fromProjective(vanish1).toProjective() # !! EPoint fails with point in infinity + + p3=numpy.cross(a,d) + p4=numpy.cross(b,c) + vanish2=numpy.cross(p3,p4) + vanish2=EPoint.fromProjective(vanish2).toProjective() + + horizon=numpy.cross(vanish1,vanish2) + + horizon=EPoint.fromProjective(horizon).toProjective() + + rectiMatrix=numpy.matrix([horizon,[0,1,0],[0,0,1]]) + rectiMatrixInv=numpy.linalg.inv(rectiMatrix) + + + affineCorners=[EPoint.fromProjective(transformPoint(x,rectiMatrix)) for x in (a,b,c,d)] + x=[affineCorners[0]-affineCorners[3],affineCorners[1]-affineCorners[2],affineCorners[0]-affineCorners[1],affineCorners[3]-affineCorners[2]] + + self.intersections=[] + boardSize=19 + for r in range(boardSize): + self.intersections.append([None]*boardSize) + rowStart=(affineCorners[0]*(boardSize-1-r)+affineCorners[1]*r) / (boardSize-1) + rowEnd=(affineCorners[3]*(boardSize-1-r)+affineCorners[2]*r) / (boardSize-1) + + for c in range(boardSize): + affineIntersection=(rowStart*(boardSize-1-c)+rowEnd*c) / (boardSize-1) + self.intersections[r][c]=EPoint.fromProjective(transformPoint(affineIntersection.toProjective(),rectiMatrixInv)) + + def stoneSizeAt(self,r,c): + intersection=self.intersections[r][c] + + if c>0: width=intersection.x - self.intersections[r][c-1].x + else: width=self.intersections[r][c+1].x - intersection.x + if r>0: height=intersection.y - self.intersections[r-1][c].y + else: height=self.intersections[r+1][c].y - intersection.y + + return (width,height) diff --git a/src/gui/__init__.py b/src/gui/__init__.py --- a/src/gui/__init__.py +++ b/src/gui/__init__.py @@ -1,48 +1,48 @@ -import threading -import tkinter as tk - -import config -from .mainwindow import MainWindow -from .boardview import BoardView - - -class GUI: - def __init__(self): - self.root = tk.Tk() - self.root.title("OneEye {0}.{1}.{2}".format(*config.misc.version)) - - self._coreMessages=None - - self.mainWindow = MainWindow(self, master=self.root) - self.root.columnconfigure(0,weight=1) - self.root.rowconfigure(0,weight=1) - - self.root.bind("<>", lambda e: self.mainWindow.redrawImgView()) - self.root.bind("",lambda e: self.sendMsg("prevFrame")) - self.root.bind("",lambda e: self.sendMsg("nextFrame")) - - def __call__(self,ownMessages,coreMessages): - self._coreMessages=coreMessages - - self.listenerThread=threading.Thread(target=lambda: ownMessages.listen(self._handleEvent)) - self.listenerThread.start() - - self.mainWindow.mainloop() - - def sendMsg(self,actionName,args=tuple(),kwargs=None): - self._coreMessages.send(actionName,args,kwargs) - - def _handleEvent(self,e): - actions={"setCurrentFrame":self._frameHandler, "setGameState":self._stateHandler} - (actionName,args,kwargs)=e - - return actions[actionName](*args,**kwargs) - - def _frameHandler(self,newFrame): - self.mainWindow.setCurrentFrame(newFrame) - self.root.event_generate("<>") - - def _stateHandler(self,gameState): - self.mainWindow.boardView.redrawState(gameState) - -gui=GUI() +import threading +import tkinter as tk + +import config +from .mainwindow import MainWindow +from .boardview import BoardView + + +class GUI: + def __init__(self): + self.root = tk.Tk() + self.root.title("OneEye {0}.{1}.{2}".format(*config.misc.version)) + + self._coreMessages=None + + self.mainWindow = MainWindow(self, master=self.root) + self.root.columnconfigure(0,weight=1) + self.root.rowconfigure(0,weight=1) + + self.root.bind("<>", lambda e: self.mainWindow.redrawImgView()) + self.root.bind("",lambda e: self.sendMsg("prevFrame")) + self.root.bind("",lambda e: self.sendMsg("nextFrame")) + + def __call__(self,ownMessages,coreMessages): + self._coreMessages=coreMessages + + self.listenerThread=threading.Thread(target=lambda: ownMessages.listen(self._handleEvent)) + self.listenerThread.start() + + self.mainWindow.mainloop() + + def sendMsg(self,actionName,args=tuple(),kwargs=None): + self._coreMessages.send(actionName,args,kwargs) + + def _handleEvent(self,e): + actions={"setCurrentFrame":self._frameHandler, "setGameState":self._stateHandler} + (actionName,args,kwargs)=e + + return actions[actionName](*args,**kwargs) + + def _frameHandler(self,newFrame): + self.mainWindow.setCurrentFrame(newFrame) + self.root.event_generate("<>") + + def _stateHandler(self,gameState): + self.mainWindow.boardView.redrawState(gameState) + +gui=GUI() diff --git a/src/imageanalyzer.py b/src/imageanalyzer.py --- a/src/imageanalyzer.py +++ b/src/imageanalyzer.py @@ -1,65 +1,65 @@ -import logging as log -from grid import Grid -from go import exportBoard -import go - - -class ImageAnalyzer: - - def __init__(self,tresB=30,tresW=60): - self.board=[[go.EMPTY]*19 for r in range(19)] - self.grid=None - - self.tresB=tresB - self.tresW=tresW - - # let's not concern ourselves with sizecoef and shift here anymore. we want corners to come already properly recomputed - def analyze(self,image): - if self.grid==None: - log.info("ImageAnalyzer.analyze() aborted: no grid available.") - return False - - for r in range(19): - for c in range(19): - intersection=self.grid.intersections[r][c] - - self.board[r][c]=self.analyzePoint(image,r,c,intersection,*(self.grid.stoneSizeAt(r,c))) - - log.info("board analyzed:\n%s", exportBoard(self.board)) - return True - - def analyzePoint(self,image,row,col,imageCoords,stoneWidth,stoneHeight): - b=w=e=0 - - ((x1,y1),(x2,y2))=relevantRect(imageCoords,stoneWidth,stoneHeight) - - for y in range(y1,y2+1): - for x in range(x1,x2+1): - try: - red,green,blue=image.getpixel((x,y)) - except IndexError: continue - - I=(red+green+blue)/255/3 - m=min(red,green,blue) - S=1-m/I if I!=0 else 0 - if 100*Iself.tresW: w+=1 - else: e+=1 - - log.debug("(%d,%d) ... (b=%d,w=%d,e=%d)", row, col, b, w, e) - - if b>=w and b>=e: return go.BLACK - if w>=b and w>=e: return go.WHITE - return go.EMPTY - - def setGridCorners(self,corners): - self.grid=Grid(corners) - - -def relevantRect(imageCoords,stoneWidth,stoneHeight): - x=int(imageCoords.x) - y=int(imageCoords.y) - xmax=max(int(stoneWidth*2//7), 2) # !! optimal parameters subject to further research - ymax=max(int(stoneHeight*2//7), 2) - - return ((x-xmax,y-ymax), (x+xmax,y+ymax)) +import logging as log +from grid import Grid +from go import exportBoard +import go + + +class ImageAnalyzer: + + def __init__(self,tresB=30,tresW=60): + self.board=[[go.EMPTY]*19 for r in range(19)] + self.grid=None + + self.tresB=tresB + self.tresW=tresW + + # let's not concern ourselves with sizecoef and shift here anymore. we want corners to come already properly recomputed + def analyze(self,image): + if self.grid==None: + log.info("ImageAnalyzer.analyze() aborted: no grid available.") + return False + + for r in range(19): + for c in range(19): + intersection=self.grid.intersections[r][c] + + self.board[r][c]=self.analyzePoint(image,r,c,intersection,*(self.grid.stoneSizeAt(r,c))) + + log.info("board analyzed:\n%s", exportBoard(self.board)) + return True + + def analyzePoint(self,image,row,col,imageCoords,stoneWidth,stoneHeight): + b=w=e=0 + + ((x1,y1),(x2,y2))=relevantRect(imageCoords,stoneWidth,stoneHeight) + + for y in range(y1,y2+1): + for x in range(x1,x2+1): + try: + red,green,blue=image.getpixel((x,y)) + except IndexError: continue + + I=(red+green+blue)/255/3 + m=min(red,green,blue) + S=1-m/I if I!=0 else 0 + if 100*Iself.tresW: w+=1 + else: e+=1 + + log.debug("(%d,%d) ... (b=%d,w=%d,e=%d)", row, col, b, w, e) + + if b>=w and b>=e: return go.BLACK + if w>=b and w>=e: return go.WHITE + return go.EMPTY + + def setGridCorners(self,corners): + self.grid=Grid(corners) + + +def relevantRect(imageCoords,stoneWidth,stoneHeight): + x=int(imageCoords.x) + y=int(imageCoords.y) + xmax=max(int(stoneWidth*2//7), 2) # !! optimal parameters subject to further research + ymax=max(int(stoneHeight*2//7), 2) + + return ((x-xmax,y-ymax), (x+xmax,y+ymax))