# HG changeset patch
# User Laman
# Date 2019-03-04 19:29:53
# Node ID 6aace8f39e750745b5f1e790ff65b5832e7401ec
# Parent  79b929f580123a05175721a7395a7e9ec51a3f4d

detecting board diagonals with RANSAC

diff --git a/exp/board_detect.py b/exp/board_detect.py
--- a/exp/board_detect.py
+++ b/exp/board_detect.py
@@ -3,7 +3,6 @@ import sys
 sys.path.append("../src")
 
 import os
-import math
 import random
 import itertools
 import logging as log
@@ -15,6 +14,7 @@ import scipy.ndimage
 import scipy.signal
 
 from geometry import Line
+from ransac import DiagonalRansac
 from annotations import DataFile,computeBoundingBox
 from hough import show,prepareEdgeImg,HoughTransform
 from analyzer.epoint import EPoint
@@ -125,6 +125,16 @@ class BoardDetector:
 		transformed=cv.warpPerspective(rect,matrix,(self._rectW,self._rectH))
 
 		# determine precise board edges
+		intersections=[]
+		for p in lines[0]:
+			for q in lines[1]:
+				intersections.append(p.intersect(q))
+		sack=DiagonalRansac(intersections,19)
+		diagonals=sack.extract(10,2000)
+		log.debug("diagonals candidates: %s",diagonals)
+		for line in diagonals:
+			self._drawLine(linesImg,line,[0,255,255])
+		show(linesImg,"diagonals candidates")
 
 	def _detectRough(self,img,filename):
 		corners=self._annotations[filename][0]
@@ -191,7 +201,8 @@ class BoardDetector:
 
 		return matrix
 
-	def _drawLine(self,img,line):
+	def _drawLine(self,img,line,color=None):
+		if not color: color=[0,255,0]
 		(h,w)=img.shape[:2]
 		corners=[EPoint(0,0),EPoint(w,0),EPoint(0,h),EPoint(w,h)] # NW NE SW SE
 		borders=[
@@ -207,7 +218,7 @@ class BoardDetector:
 		if any(abs(x)>10**5 for x in [*a,*b]):
 			log.debug("ignored")
 			return
-		cv.line(img,(int(a.x),int(a.y)),(int(b.x),int(b.y)),[0,255,0])
+		cv.line(img,(int(a.x),int(a.y)),(int(b.x),int(b.y)),color)
 
 
 if __name__=="__main__":
diff --git a/exp/hough.py b/exp/hough.py
--- a/exp/hough.py
+++ b/exp/hough.py
@@ -27,6 +27,7 @@ class LineBag:
 		res=[]
 		for (score,alpha,beta,peaks) in self._lines:
 			if any(abs(alpha-gamma)<10 and abs(beta-delta)<10 for (_,gamma,delta,_) in res): continue
+			# avoid intersecting lines
 			if any((beta-delta)!=0 and (alpha-gamma)/(beta-delta)<0 for (_,gamma,delta,_) in res): continue
 			res.append((score,alpha,beta,peaks))
 			if len(res)>=count: break
@@ -65,7 +66,7 @@ class HoughTransform:
 				(alphaDeg,d)=keys[k]
 				line=Line(alphaDeg*math.pi/180,d-self._diagLen//2)
 				res[-1].append(self._transformOutput(line))
-			res[-1].sort(key=lambda line: line.d)
+			res[-1].sort(key=lambda line: line.d if line.alpha<math.pi else -line.d)
 			i+=1
 
 		self.show(img)
diff --git a/exp/ransac.py b/exp/ransac.py
new file mode 100644
--- /dev/null
+++ b/exp/ransac.py
@@ -0,0 +1,70 @@
+import random
+
+from geometry import Line
+
+
+class LineBag:
+	def __init__(self,capacity):
+		self._capacity=capacity
+		self._bag=[]
+
+	def put(self,item):
+		# early abort
+		if self._bag and item>self._bag[-1]: return
+
+		(v,p)=item
+		# mostly filter duplicates
+		for (i,(vi,pi)) in enumerate(self._bag):
+			if abs(p.alpha-pi.alpha)<0.02 and abs(p.d-pi.d)<5:
+				if v<vi: self._bag[i]=item
+				return
+
+		# add new and remove the last
+		self._bag.append(item)
+		self._bag.sort()
+		if len(self._bag)>self._capacity:
+			self._bag.pop()
+
+	def pull(self,count=0):
+		return self._bag[:count] if count else self._bag[:]
+
+
+class Ransac:
+	def __init__(self,points):
+		self._points=points
+
+	def extract(self,count,iterations):
+		bag=LineBag(count)
+
+		for i in range(iterations):
+			line=self._generateLine()
+			score=self._scoreLine(line)
+			bag.put((score+random.random()/1000,line))
+
+		return [line for (score,line) in bag.pull()]
+
+	def _generateLine(self):
+		(a,b)=random.sample(self._points,2)
+		return Line.fromPoints(a,b)
+
+	def _scoreLine(self,line):
+		return sum(min(line.distanceTo(p),5) for p in self._points)
+
+
+class DiagonalRansac(Ransac):
+	def __init__(self,points,sideLen):
+		super().__init__(points)
+		self._sideLen=sideLen
+
+	def _generateLine(self):
+		n=len(self._points)
+		m=self._sideLen
+		ka=random.randrange(0,n)
+		kb=ka
+
+		while ka//m==kb//m or ka%m==kb%m:
+			kb=random.randrange(0,n)
+		a=self._points[ka]
+		b=self._points[kb]
+
+		return Line.fromPoints(a,b)