# HG changeset patch
# User Laman
# Date 2019-04-16 20:19:53
# Node ID 634319abff9f8712bea280dea897bb09e8d5bdd5
# Parent  386837ecb39ccfeca8a7300f566ff606eda5e48e

experimental randomized Hough transform

diff --git a/exp/hough.py b/exp/hough.py
--- a/exp/hough.py
+++ b/exp/hough.py
@@ -2,6 +2,7 @@ import sys
 sys.path.append("../src")
 
 import math
+import random
 from datetime import datetime
 import os.path
 import logging as log
@@ -168,6 +169,118 @@ class HoughTransform:
 			cv.drawMarker(img,(x,y),color,cv.MARKER_TILTED_CROSS,8)
 
 
+class Accumulator:
+	NEIGHBOURHOOD=2
+
+	def __init__(self):
+		self._acc=[]
+		self._hits=[]
+
+	def add(self,line):
+		(d,k)=self._findClosest(line)
+		if d<=self.NEIGHBOURHOOD:
+			self._acc=self._averageLines(self._acc[k],line,self._hits[k],1)
+			self._hits[k]+=1
+		else:
+			k=-1
+			self._acc.append(line)
+			self._hits.append(1)
+		return (self._hits[k],k)
+
+	def pop(self,k):
+		acc=self._acc
+		(acc[k],acc[-1])=(acc[-1],acc[k])
+		hits=self._hits
+		(hits[k],hits[-1])=(hits[-1],hits[k])
+		hits.pop()
+		return acc.pop()
+
+	def _findClosest(self,line):
+		def dist(p,q):
+			alpha=p.alpha*180/math.pi
+			beta=q.alpha*180/math.pi
+			gamma=abs(alpha-beta)
+			if gamma>180: gamma=360-gamma
+			return math.sqrt(gamma**2+(p.d-q.d)**2)
+
+		(d,key)=min(zip((dist(line,p) for p in self._acc), range(len(self._acc))))
+		return (d,key)
+
+	def _averageLines(self,ab,cd,w1,w2):
+		w=w1+w2
+		(a,b)=ab.toPoints()
+		(c,d)=cd.toPoints()
+		e=(a*w1+c*w2)/w
+		f=(b*w1+c*w2)/w
+		return Line.fromPoints(e,f)
+
+
+class RandomizedHoughTransform:
+	HIT_LIMIT=10
+	CANDIDATE_LIMIT=10
+	MIN_SCORE=50
+
+	def __init__(self,img):
+		self._img=np.copy(img)
+		(self._h,self._w)=img.shape[:2]
+
+		self._acc=Accumulator()
+		self._candidates=[]
+		self._res=[]
+
+	def _sampleLine(self):
+		""":return: (Line) p"""
+		a=self._chooseRandomPixel()
+		b=self._chooseRandomPixel()
+		while b==a: b=self._chooseRandomPixel()
+		return Line.fromPoints(a,b)
+
+	def _updateAcc(self,line):
+		(hits,k)=self._acc.add(line)
+		if hits>=self.HIT_LIMIT:
+			self._addCandidate(self._acc.pop(k))
+
+	def _addCandidate(self,line):
+		self._candidates.append(line)
+		if len(self._candidates)>=self.CANDIDATE_LIMIT:
+			for p in self._candidates:
+				p_=self._confirmLine(p)
+				if p_: self._res.append(p_)
+			self._candidates=[]
+
+	def _chooseRandomPixel(self):
+		val=0
+		while not val:
+			x=random.randrange(0,self._w)
+			y=random.randrange(0,self._h)
+			val=self._img[y,x]
+		return EPoint(x,y)
+
+	def _confirmLine(self,line):
+		score=0
+		for point in self._walkLine(line):
+			if self._img[point]==1:
+				score+=1
+		if score>self.MIN_SCORE:
+			for point in self._walkLine(line): # erase the line
+				self._img[point]=0
+			return line
+		else: return None
+
+	def _walkLine(self,line):
+		(a,b,c)=line.toNormal()
+		if abs(line.alpha-math.pi/2)<math.pi/4 or abs(line.alpha-3*math.pi/2)<math.pi/4: # vertical normal ~ horizontal line
+			for x in range(self._w):
+				y=int((-c-a*x)/b)
+				if 0<=y<self.h:
+					yield (y,x)
+		else: # a predominantly vertical line
+			for y in range(self._h):
+				x=int((-c-b*y)/a)
+				if 0<=x<self.w:
+					yield (y,x)
+
+
 def show(img,filename="x"):
 	if cfg.INTERACTIVE:
 		cv.imshow(filename,img)