Changeset - 634319abff9f
[Not reviewed]
default
0 1 0
Laman - 6 years ago 2019-04-16 20:19:53

experimental randomized Hough transform
1 file changed with 113 insertions and 0 deletions:
0 comments (0 inline, 0 general)
exp/hough.py
Show inline comments
 
@@ -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)
0 comments (0 inline, 0 general)