OneEye Changeset - 7c268e382b96

Changeset - 7c268e382b96

Parent rev.

Child rev.

[Not reviewed]

default

0 2 2

Laman - 6 years ago 2019-02-14 17:18:55

geometry: rewritten Line

4 files changed with 102 insertions and 47 deletions:

exp/board_detect.py

exp/geometry.py

exp/tests/__init__.py

new file

exp/tests/test_geometry.py

0 comments (0 inline, 0 general)

exp/board_detect.py

➞

Show inline comments

 import sys
 sys.path.append("../src")
 import os
 import math
 import random
 import logging as log
 import cv2 as cv
 import numpy as np
 import scipy.cluster
 import scipy.ndimage
 import scipy.signal
-from geometry import Line, point2lineDistance
 from geometry import Line
 from polar_hough import PolarHough
 from annotations import DataFile,computeBoundingBox
 from hough import show,prepareEdgeImg,HoughTransform
 from analyzer.epoint import EPoint
 from analyzer.corners import Corners
 random.seed(361)
 log.basicConfig(level=log.DEBUG,format="%(message)s")
 def kmeans(img):
 	arr=np.reshape(img,(-1,3)).astype(np.float)
 	colors=np.array([[0,0,0],[255,255,255],[193,165,116]],np.float)
 	log.debug(colors)
 	(centers,distortion)=scipy.cluster.vq.kmeans(arr,colors)
 	log.debug("k-means centers: %s",centers)
 	return centers
 def quantize(img,centers):
 	origShape=img.shape
 	data=np.reshape(img,(-1,3))
 	(keys,dists)=scipy.cluster.vq.vq(data,centers)
 	pixels=np.array([centers[k] for k in keys],dtype=np.uint8).reshape(origShape)
 	return pixels
 def filterStones(contours,bwImg,stoneDims):
 	contourImg=cv.cvtColor(bwImg,cv.COLOR_GRAY2BGR)
 	res=[]
 	for (i,c) in enumerate(contours):
 		keep=True
 		moments=cv.moments(c)
 		center=(moments["m10"]/(moments["m00"] or 1), moments["m01"]/(moments["m00"] or 1))
 		area=cv.contourArea(c)
 		(x,y,w,h)=cv.boundingRect(c)
 		if w>stoneDims[0] or h>stoneDims[1]*1.5 or w<2 or h<2:
 			cv.drawMarker(contourImg,tuple(map(int,center)),(0,0,255),cv.MARKER_TILTED_CROSS,12)
 			keep=False
 		coverage1=area/(w*h or 1)
 		hull=cv.convexHull(c)
 		coverage2=area/(cv.contourArea(hull) or 1)
 		# if coverage2<0.8:
 		# 	cv.drawMarker(contourImg,tuple(map(int,center)),(0,127,255),cv.MARKER_DIAMOND,12)
 		# 	keep=False
 		if keep:
 			res.append((EPoint(*center),c))
 			cv.drawMarker(contourImg,tuple(map(int,center)),(255,0,0),cv.MARKER_CROSS)
 	log.debug("accepted: %s",len(res))
 	log.debug("rejected: %s",len(contours)-len(res))
 	show(contourImg,"accepted and rejected stones")
 	return res
 def groupLines(points,minCount,tolerance):
 	random.shuffle(points)
 	sample=points[:]
 	for (i,a) in enumerate(sample):
 		for (j,b) in enumerate(sample):
 			if j<=i: continue
 			ab=Line(a,b)
 			for c in points:
 				if c is a or c is b: continue
 				if point2lineDistance(a,b,c)<=tolerance:
 					ab.points.add(c)
 			if len(ab.points)>=minCount:
 				yield ab
 class BoardDetector:
 	def __init__(self,annotationsPath):
 		self._annotations=DataFile(annotationsPath)
 		self._rectW=0
 		self._rectH=0
 		self._rect=None
 	def __call__(self,img,filename):
 		# approximately detect the board
 		(h,w)=img.shape[:2]
 		log.debug("image dimensions: %s x %s",w,h)
 		show(img,filename)
 		(x1,y1,x2,y2)=self._detectRough(img,filename)
 		rect=img[y1:y2,x1:x2]
 		self._rectW=x2-x1
 		self._rectH=y2-y1
 		self._rect=rect
 		# quantize colors
 		colors=self._sampleColors(rect)
 		quantized=quantize(rect,colors)
 		gray=cv.cvtColor(rect,cv.COLOR_BGR2GRAY)
 		edges=cv.Canny(gray,70,130)
 		show(edges,"edges")
 		quantized=quantized & (255-cv.cvtColor(edges,cv.COLOR_GRAY2BGR))
 		show(quantized,"quantized, edges separated")
 		# detect black and white stones
 		stones=self._detectStones(quantized,colors)
 		# detect lines from edges and stones
 		edgeImg=prepareEdgeImg(rect)
 		hough=HoughTransform(edgeImg)
 		stonesImg=np.zeros((self._rectH,self._rectW),np.uint8)
 		for (point,c) in stones:
 			cv.circle(stonesImg,(int(point.x),int(point.y)),2,255,-1)
 		# cv.drawContours(stonesImg,[c for (point,c) in stones],-1,255,-1)
 		show(stonesImg,"detected stones")
 		hough.update(stonesImg,5)
 		hough.extract()
 		# # detect lines passing through the stones
 		# lines=self._constructLines(stones)
+		#
 		# # detect vanishing points of the lines
 		# imgCenter=EPoint(w//2-x1, h//2-y1)
 		# (a,b,c,d)=(p-EPoint(x1,y1) for p in self._annotations[filename][0])
 		# (p,q,r,s)=(Line(a,b),Line(b,c),Line(c,d),Line(d,a))
 		# v1=p.intersect(r)
 		# v2=q.intersect(s)
 		# log.debug("true vanishing points: %s ~ %s, %s ~ %s",v1,v1.toPolar(imgCenter),v2,v2.toPolar(imgCenter))
 		# vanish=self._detectVanishingPoints(lines,imgCenter,(v1.toPolar(imgCenter),v2.toPolar(imgCenter)))
+		#
 		# # rectify the image
 		# matrix=self._computeTransformationMatrix(vanish,lines)
 		# transformed=cv.warpPerspective(rect,matrix,(self._rectW,self._rectH))
+		#
 		# # determine precise board edges
 	def _detectRough(self,img,filename):
 		corners=self._annotations[filename][0]
 		(x1,y1,x2,y2)=computeBoundingBox(corners)
 		log.debug("bounding box: (%s,%s) - (%s,%s)",x1,y1,x2,y2)
 		return (x1,y1,x2,y2)
 	def _sampleColors(self,rect):
 		(h,w)=rect.shape[:2]
 		minirect=rect[h//4:3*h//4, w//4:3*w//4]
 		return kmeans(minirect)
 	def _detectStones(self,quantized,colors):
 		(h,w)=quantized.shape[:2]
 		mask=self._maskStones(quantized,colors)
 		stoneDims=(w/19,h/19)
 		log.debug("stone dims: %s - %s",tuple(x/2 for x in stoneDims),stoneDims)
 		(contours,hierarchy)=cv.findContours(mask,cv.RETR_LIST,cv.CHAIN_APPROX_SIMPLE)
 		stoneLocs=filterStones(contours,mask,stoneDims)
 		return stoneLocs
 	def _maskStones(self,quantized,colors):
 		unit=np.array([1,1,1],dtype=np.uint8)
 		maskB=cv.inRange(quantized,colors[0]-unit,colors[0]+unit)
 		distTransform=cv.distanceTransform(maskB,cv.DIST_L2,5)
 		maskB=cv.inRange(distTransform,6,20)
 		show(maskB,"black areas")
 		maskW=cv.inRange(quantized,colors[1]-unit,colors[1]+unit)
 		distTransform=cv.distanceTransform(maskW,cv.DIST_L2,5)
 		maskW=cv.inRange(distTransform,6,20)
 		show(maskW,"white areas")
 		stones=cv.bitwise_or(maskB,maskW)
 		show(stones,"black and white areas")
 		return stones
 	def _constructLines(self,stoneLocs):
 		lineDict=dict()
 		# minCount=min(max(math.sqrt(len(stoneLocs))-4,3),7)
 		minCount=6
 		log.debug("min count: %s",minCount)
 		points=[point for (point,contour) in stoneLocs]
 		for line in groupLines(points,minCount,2):
 			key=line.getSortedPoints()
 			if key in lineDict: # we already have a line with the same incident points
 				continue
 			lineDict[line.getSortedPoints()]=line
 			obsolete=set()
 			for ab in lineDict.values():
 				if ab is line: continue
 				if line.points<ab.points: # == impossible
 					del lineDict[key]
 					break
 				if ab.points<line.points:
 					obsolete.add(ab.getSortedPoints())
 			for key in obsolete: del lineDict[key]
 		log.debug("valid lines: %s",len(lineDict))
 		lines=sorted(lineDict.values(), key=lambda ab: len(ab.points), reverse=True)
 		# visualize

exp/geometry.py

➞

Show inline comments

 import math
 import numpy as np
 from analyzer.epoint import EPoint, homogenize
 from analyzer.grid import transformPoint
 from analyzer.epoint import EPoint
 class Line():
 	def __init__(self,a,b):
 		self.a=a
 		self.b=b
 		self.points={a,b}
 class Line:
 	def __init__(self,alpha,d):
 		self._alpha=alpha
 		self._d=d
 		self._sin=math.sin(alpha)
 		self._cos=math.cos(alpha)
 	def getSortedPoints(self):
 		return tuple(sorted(self.points))
 	@staticmethod
 	def fromNormal(a,b,c):
 		"""ax + by + c = 0"""
 		norm=-c/abs(c)*math.sqrt(a**2+b**2)
 		(a_,b_,c_)=(a/norm,b/norm,c/norm)
 		alpha=math.acos(a_) if b_>=0 else 2*math.pi-math.acos(a_)
 		return Line(alpha,-c_)
 	def computeAngle(self,line):
 		ab=self.a-self.b
 		cd=line.a-line.b
 		alpha=math.atan(ab.y/ab.x)
 		gamma=math.atan(cd.y/cd.x)
 		fi=max(alpha,gamma)-min(alpha,gamma)
 		return min(fi,math.pi-fi)
 	@staticmethod
 	def fromPoints(a,b):
 		return Line.fromNormal(a.y-b.y, b.x-a.x, (b.y-a.y)*a.x+(a.x-b.x)*a.y)
 	def toNormal(self):
 		# https://en.wikipedia.org/wiki/Line_(mathematics)#In_normal_form
 		"""ax + by + c = 0"""
 		return (self._cos, self._sin, -self._d)
 	def intersect(self,line):
 		p=self.toProjective()
 		q=line.toProjective()
 		return EPoint.fromProjective(np.cross(p,q))
 	def toProjective(self):
 		return homogenize(np.cross(self.a.toProjective(),self.b.toProjective()))
 	def transform(self,matrix):
 		a=EPoint.fromProjective(transformPoint(self.a.toProjective(),matrix))
 		b=EPoint.fromProjective(transformPoint(self.b.toProjective(),matrix))
 		if a is None or b is None: return None
 		return Line(a,b)
 		if self._alpha==line._alpha: return None
 		(a,b,c)=self.toNormal()
 		(d,e,f)=line.toNormal()
 		x=(b*f-c*e)/(a*e-b*d)
 		y=(c*d-a*f)/(a*e-b*d)
 		return EPoint(x,y)
 	def score(self,points):
 		score=len(self.points)
 		for a in self.points:
 			closest=sorted(points,key=lambda b: a.dist(b))[:4]
 			score+=sum(0.01 for b in closest if b in self.points)
 		return score
 	def distanceTo(self,point):
 		# https://en.wikipedia.org/wiki/Point-line_distance#Line_defined_by_an_equation
 		(a,b,c)=self.toNormal()
 		return abs(a*point.x+b*point.y+c) # a**2 + b**2 == 1 for Hesse normal form
 	def __str__(self): return "({0},{1})".format(self.a,self.b)
 	def __repr__(self): return "Line({0},{1})".format(repr(self.a),repr(self.b))
 def point2lineDistance(a,b,p):
 	# https://en.wikipedia.org/wiki/Point-line_distance#Line_defined_by_two_points
 	ab=b-a
 	num=abs(ab.y*p.x - ab.x*p.y + b.x*a.y - a.x*b.y)
 	denum=math.sqrt(ab.y**2+ab.x**2)
 	return num/denum # double_area / side_length == height
 	def __str__(self): return "({0},{1})".format(self._alpha,self._d)
 	def __repr__(self): return "Line({0},{1})".format(repr(self._alpha),repr(self._d))
 def angleDiff(alpha,beta):
 	diff=abs(alpha-beta)
 	if diff>math.pi: diff=2*math.pi-diff
 	return diff

exp/tests/__init__.py

➞

Show inline comments

new file 100644

exp/tests/test_geometry.py

➞

Show inline comments

@@ new file 100644 @@
 import math
 import random
 from unittest import TestCase
 from geometry import Line,EPoint
 random.seed(361)
 class TestLine(TestCase):
 	def testFromNormal(self):
 		p=Line.fromNormal(1,0,-1) # x-1=0
 		self.assertEqual(p._alpha,0)
 		self.assertEqual(p._d,1)
 		q=Line.fromNormal(1,1,-2) # x+y-2=0
 		self.assertAlmostEqual(q._alpha,math.pi/4)
 		self.assertAlmostEqual(q._d,math.sqrt(2))
 		r=Line.fromNormal(0,1,1) # y+1=0
 		self.assertAlmostEqual(r._alpha,math.pi*3/2)
 		self.assertEqual(r._d,1)
 	def testFromPoints(self):
 		ab=Line.fromPoints(EPoint(1,3),EPoint(1,-1))
 		self.assertEqual(ab._alpha,0)
 		self.assertEqual(ab._d,1)
 		cd=Line.fromPoints(EPoint(0,2),EPoint(-1,3))
 		self.assertAlmostEqual(cd._alpha,math.pi/4)
 		self.assertAlmostEqual(cd._d,math.sqrt(2))
 		ef=Line.fromPoints(EPoint(-2,-1),EPoint(-4,-1))
 		self.assertAlmostEqual(ef._alpha,math.pi*3/2)
 		self.assertEqual(ef._d,1)
 	def testIntersect(self):
 		for i in range(10):
 			a=EPoint(random.randint(-100,100),random.randint(-100,100))
 			b=EPoint(random.randint(-100,100),random.randint(-100,100))
 			c=EPoint(random.randint(-100,100),random.randint(-100,100))
 			ab=Line.fromPoints(a,b)
 			ac=Line.fromPoints(a,c)
 			a_=ab.intersect(ac)
 			self.assertAlmostEqual(a.x,a_.x)
 			self.assertAlmostEqual(a.y,a_.y)
 	def testDistanceTo(self):
 		p=Line(0,1)
 		q=Line(math.pi/4,math.sqrt(2))
 		r=Line(math.pi*3/2,1)
 		a=EPoint(0,0)
 		b=EPoint(1,0)
 		c=EPoint(-1,-1)
 		self.assertAlmostEqual(p.distanceTo(a),1)
 		self.assertAlmostEqual(p.distanceTo(b),0)
 		self.assertAlmostEqual(p.distanceTo(c),2)
 		self.assertAlmostEqual(q.distanceTo(a),math.sqrt(2))
 		self.assertAlmostEqual(q.distanceTo(b),math.sqrt(2)/2)
 		self.assertAlmostEqual(q.distanceTo(c),2*math.sqrt(2))
 		self.assertAlmostEqual(r.distanceTo(a),1)
 		self.assertAlmostEqual(r.distanceTo(b),1)
 		self.assertAlmostEqual(r.distanceTo(c),0)

0 comments (0 inline, 0 general)