Я потратил некоторое время, пытаясь использовать обнаруженные вами прямоугольники для центральной линии (со странным шумом других смещенных от центра), чтобы добраться до последовательности вокруг дорожки.
Я начал с небольшой настройки вашего кода чтобы сохранить обнаруженные прямоугольники, чтобы нормализовать их так, чтобы они всегда были шире, чем высота, и сохранить в файл json
Затем я написал код, чтобы взять этот файл json и соединить прямоугольники.
Я подумал об использовании, например, kdtree для поиска ближайших соседей, но это не так просто, потому что есть пробелы, поэтому соединение не всегда с двумя ближайшими соседями. Вместо этого я попытался найти ближайшего соседа в направлении «положительное» в направлении прямоугольника и «отрицательное» - в противоположном направлении.
Три фазы обработки:
Первая фаза - это просто вычислить центр тонких концов - будет использовать их как сегмент линии для параметрических c линейных расчетов пересечения.
Вторая фаза проходит через все сегменты, пытаясь найти наиболее соединенных соседей - здесь используются угол и направление каждого прямоугольника, чтобы рассчитать расстояние по этим углам от сфокусированного прямоугольника до всех других прямоугольников, отклоняя те, которые находятся под слишком крутым углом, и выбирая ближайшие в каждом направлении - я попробовал метри c, рассчитанный из длину пути и угол, выберите минимум для положительного / отрицательного направлений. Сложности с этим заключались в том, что обнаруженные прямоугольники немного дрожали, а некоторые из них параллельны, поэтому здесь и там есть небольшая выдумка, чтобы попытаться устранить неоднозначность (в частности, установлен порог деноминации 30, чтобы заставить это изображение работать, вам может потребоваться настройка это. Если бы изображение было с более высоким разрешением, это, вероятно, было бы проще. Logi c пересечения является наиболее сложной частью. Обнаруженные прямоугольники расположены сверху вниз изображения, и их направление может быть любым, поэтому пересечение имеет Чтобы справиться с этим. Также, когда взаимодействия находятся внутри сегмента линии, который требует особой обработки, потому что не так очевидно, как вычислить длину пути и разницу углов между ними.
Этот поиск ближайших соседей использует грубую силу поиск по всем остальным - он работает достаточно быстро, чтобы не было причин пытаться оптимизировать, сравнивая только с «ближайшими» прямоугольниками.
Поиск положительных / отрицательных соседей будет успешным y мостовидные зазоры - если бы рядом с этими зазорами были прямоугольники шума, которые могли бы вызвать проблемы, но, к счастью, это не так на вашем изображении :-) Моя идея с metri c состояла в том, чтобы попробовать и предпочесть соединения под меньшими углами, чтобы противостоять шум - ваше изображение на самом деле не проявляет этого.
Пример изображения, наложенного со всеми соединениями, - это первое изображение ниже.
Третья фаза, теперь все положительные / отрицательные связи известны: go через последовательность построения. Если один узел имеет положительное или отрицательное соединение с другим, он «соединяется», если этот другой узел имеет обратное положительное или отрицательное соединение. Принятие только взаимных соединений означает, что выбросы отклоняются - они становятся последовательностями из одного прямоугольника. Обратите внимание на то, что соседние прямоугольники могут быть действительными в противоположных направлениях, поэтому, например, положительное соединение с другим узлом может быть действительным как положительное, так и отрицательное соединение от этого узла.
Поскольку начальный узел может (надеюсь, имеет) иметь оба Положительные и отрицательные соединения, я держу стек соединений, чтобы проверить. Положительное соединение начального узла сначала помещается в стек и снимается только после того, как отрицательная сторона не может больше подключаться, затем оно вставляется в начало последовательности - это обрабатывает, где нет подключенного l oop, поэтому последовательность все еще верна.
Затем он показывает вам связанные последовательности :-) См. второе изображение ниже.
Извините, код не совсем доработан / красив, но он работает для этого изображения - мне будет интересно узнать, работает ли оно с другими изображениями дорожек.
Закодировано с использованием Python 3.8.3 и opencv 4.2 в Windows / AMD64
import cv2
import numpy as np
import json
import scipy.spatial
import math
# set to true to produce copious debugging printout while trying to connect
DEBUG = False
# set to true to display image after each iteration of trying to connect
STEP = False
# the image to draw over
TRACK = 'track_ol.png'
def dist(x1,y1,x2,y2):
return math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
# normalise ang to +/-pi
def normalise(ang):
while ang<-math.pi:
ang += 2.0*math.pi
while ang>math.pi:
ang -= 2.0*math.pi
return ang
# returns the parametric distance of the intersection of l1 and l2 in terms of l1
def intersect(l1,l2):
if DEBUG:
print( f"{l1=}" )
print( f"{l2=}" )
x1,y1=l1[0][0],l1[0][1]
x2,y2=l1[1][0],l1[1][1]
x3,y3=l2[0][0],l2[0][1]
x4,y4=l2[1][0],l2[1][1]
if DEBUG:
print( f"{x1=} {y1=}" )
print( f"{x2=} {y2=}" )
print( f"{x3=} {y3=}" )
print( f"{x4=} {y4=}" )
denom = (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)
xc1,yc1=(x1+x2)/2.0,(y1+y2)/2.0
xc2,yc2=(x3+x4)/2.0,(y3+y4)/2.0
if DEBUG:
print( f"{denom=}" )
if abs(denom)<30.0: # this is a bit of a fudge - basically prefer finding parallel lines to slighly divergent ones
# parallel
# work out distance between the parallel lines https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line
dist1 = abs((y2-y1)*x3-(x2-x1)*y3+x2*y1-y2*x1)/math.sqrt(dist(x1,y1,x2,y2))
if DEBUG:
print( f"{dist1=}" )
if dist1>30.0:
if DEBUG:
print( f"Parallel rejected dist {dist1=}" )
return None,None
# work out the centres of the line joining centres of l1 and l2 - going to use the line joining these centres
intx,inty = (xc1+xc2)/2.0, (yc1+yc2)/2.0 # and if angle of intersection would be too greate
pathlength = dist(xc1,yc1,xc2,yc2)
# t = dist(xc1,yc1,intx,inty)/dist(x1,y1,x2,y2)
# u = -dist(xc2,yc2,intx,inty)/dist(x1,y1,x2,y2)
# choose the x or y which is most different
if abs(y2-y1)>abs(x2-x1):
t = (inty-y1)/(y2-y1)
else:
t = (intx-x1)/(x2-x1)
if abs(y4-y3)>abs(x4-x3):
u = (inty-y3)/(y4-y3)
else:
u = (intx-x3)/(x4-x3)
ang1 = math.atan2(y2-y1,x2-x1)
ang2 = math.atan2(yc2-yc1,xc2-xc1)
# choose the smaller change
ang = normalise(ang2-ang1)
if abs(ang)>0.5*math.pi:
pathlength = -pathlength
ang = normalise(math.pi-ang)
if DEBUG:
print( f"Parallel {xc1=} {yc1=} {xc2=} {yc2=}" )
print( f"Parallel {intx=} {inty=}" )
print( f"Parallel {pathlength} {t=} {u=} {ang=} {ang1=} {ang2=}" )
if abs(ang)>0.5*math.pi:
# print( f"Rejected ang {ang=}" )
return None,None
# if abs(ang) >0.5*math.pi:
# t = 1.0-t
if DEBUG:
print( f"Parallel {pathlength} {t=} {u=} {ang=}" )
return pathlength,ang
# work out the intersection https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
t = ((x1-x3)*(y3-y4)-(y1-y3)*(x3-x4))/denom
u = -((x1-x2)*(y1-y3)-(y1-y2)*(x1-x3))/denom
intx,inty = x1+t*(x2-x1),y1+t*(y2-y1)
pathlength = dist(xc1,yc1,intx,inty)+dist(intx,inty,xc2,yc2)
if DEBUG:
print( f"{intx=} {inty=}" )
# get the raw angle of l1 and l2
# if t is <0, turn ang1 by 180 to point towards the intersection
ang1 = math.atan2( y2-y1,x2-x1 )
ang2 = math.atan2( y4-y3,x4-x3 )
# get the angle of line from centre of l1 to centre of l2
angc = math.atan2( yc2-yc1,xc2-xc1 )
# decide if centre l2 is "forwards" (in the direction l1 points) of centre of l1 - used only when there is an intersection within one of them
# so sign of pathlength can be set correctly
# MUST do this before normalising ang1 to point to the intersection and ang2 to point away
if abs(normalise(angc-ang1)) < 0.5*math.pi:
l1forwards = True
else:
l1forwards = False
if DEBUG:
print( f"{l1forwards=} {angc=} {ang1=}" )
# now normalise ang1 to point towards the intersection
# NOTE if either intersection is within either line, ang1/ang2 normalisation doesn;t matter
# because the smaller difference angle will be used.
if t < 0.0:
ang1 = normalise(ang1+math.pi)
# we want ang2 going away from the intersection, so it u is positive reverse the angle
# now normalise ang2 to point away the intersection
if u > 1.0:
ang2 = normalise(ang2+math.pi)
# check for intersection within l1 or l2
if 0.0 <= t <= 1.0:
# internal to l1
if 0.0 <= u <= 1.0:
# this is internal to both l1 and l2
raise Exception( "This should never happen because it means the blobs overlap!")
else:
# internal only to l1
# find the smallest angle of intersection
if abs(normalise(ang2-ang1))<abs(normalise(math.pi-(ang2-ang1))):
ang = normalise(ang2-ang1)
if DEBUG:
print( "t norev" )
else:
ang = normalise(math.pi-(ang2-ang1))
if DEBUG:
print( "t rev" )
if abs(ang)>0.25*math.pi:
if DEBUG:
print( f"Rejected1 {ang=} {ang1=} {ang2=}" )
return None,None
pathlength = pathlength if l1forwards else -pathlength
else:
# not internal to l1
if 0.0 <= u <= 1.0:
# internal only to l2
if abs(normalise(ang2-ang1))<abs(normalise(math.pi-(ang2-ang1))):
ang = normalise(ang2-ang1)
if DEBUG:
print( "u norev" )
else:
ang = normalise(math.pi-(ang2-ang1))
if DEBUG:
print( "u-rev" )
if abs(ang)>0.25*math.pi:
if DEBUG:
print( f"Rejected2 {ang=} {ang1=} {ang2=}" )
return None,None
pathlength = pathlength if l1forwards else -pathlength
else:
# this is external to both l1 and l2 - use t to decide if forwards or backwards
ang = normalise(ang2-ang1)
pathlength = pathlength if t >= 0.0 else -pathlength
# ang = math.atan2(y2-y1,x2-x1)-math.atan2(y4-y3,x4-x3)
if DEBUG:
print( f"{pathlength=} {t=} {u=} {ang=} {ang1=} {ang2=}" )
if abs(ang)>0.5*math.pi:
if DEBUG:
print( f"Rejected ang {ang=}" )
return None,None
return pathlength,ang
#cv2.waitKey(0)
#cv2.destroyAllWindows()
possiblecentres = json.loads(open( "centres.json","r").read() )
# phase 1 - add the x/y coord of each end of the rectangle as the ends of a line segment
for i,candidate in enumerate(possiblecentres):
candidate.append(0) # usecount
xc,yc,dx,dy,angle = candidate[0][0],candidate[0][1],candidate[1][0]/2.0,candidate[1][1]/2.0,candidate[2]*math.pi/180.0
x1,y1 = xc-dx*math.cos(angle),yc-dx*math.sin(angle)
x2,y2 = xc+dx*math.cos(angle),yc+dx*math.sin(angle)
candidate.append(((x1,y1),(x2,y2))) #centre-endpoints
image = cv2.imread(TRACK)
# phase 2 - for each blob, find closest pos/neg blob
for i,candidate in enumerate(possiblecentres):
posintersect,pospt,posang,len1 = 1e10,None,None,None
negintersect,negpt,negang,len1 = 1e10,None,None,None
l1 = candidate[4]
if DEBUG:
print( f"\n\n\n===================================\n{i=} {l1=}" )
print( f"{candidate=}" )
for j,other in enumerate(possiblecentres):
if i==j:
continue
l2 = other[4]
if DEBUG:
print( f"\n============\n{j=} {l2=}" )
print( f"{other=}" )
pathlen,ang = intersect(l1,l2)
if pathlen is None:
continue
metric =pathlen*pathlen*math.exp(abs(ang))
if metric > 100000000:
if DEBUG:
print( f"Rejected metric {metric=}" )
continue
# print( f"{pathlen=} {ang=} {metric=}" )
# find closest intersection in +ve direction
if pathlen>=0.0 and metric<posintersect:
posintersect,pospt,posang,len1 = metric,j,ang,pathlen
if DEBUG:
print( "POS updated")
if pathlen<0.0 and metric<negintersect:
negintersect,negpt,negang,len1 = metric,j,ang,pathlen
if DEBUG:
print( "NEG updated")
if DEBUG:
print( i,candidate,posintersect,pospt,posang,negintersect,negpt,negang )
print( f"{i=} {pospt=} {negpt=}" )
# foundconnections[i] = 0
possiblecentres[i].append(((posintersect,pospt,posang,len1),(negintersect,negpt,negang,len1)))
# cv2.line(image,(int(candidate[4][0][0]),int(candidate[4][0][1])),(int(candidate[4][1][0]),int(candidate[4][1][1])),(255,255,255))
if STEP:
image = cv2.imread(TRACK)
thisrect = (candidate[0],candidate[1],candidate[2])
box = cv2.boxPoints(thisrect)
box = np.int0(box)
cv2.drawContours(image, [box], -1, (255, 255, 255), 1)
if pospt is not None:
cv2.line(image,(int(candidate[0][0]),int(candidate[0][1])),(int(possiblecentres[pospt][0][0]),int(possiblecentres[pospt][0][1])),(255,0,0))
if negpt is not None:
cv2.line(image,(int(candidate[0][0]),int(candidate[0][1])),(int(possiblecentres[negpt][0][0]),int(possiblecentres[negpt][0][1])),(0,255,0))
if STEP:
cv2.imshow('Rectangles', image)
if cv2.waitKey(0)==113:
break
# finally phase 3 - for each blob's connections, match up with another blob that reverses that connection
# This eliminates odd blobs that aren't recipricolly connected to the things they connect to
sequences = [] # each entry in this list is a sequence of indexes into possiblecentres
todos = list(range(len(possiblecentres)))
stacktochecks = [] # this should never have more than two items on it - and the first one is only removed once the circuit is complete
while True:
if stacktochecks:
print( f"{stacktochecks=}" )
print( f"{sequences[-1]=}" )
# continued sequence
startpt = stacktochecks.pop()
if stacktochecks:
# we are on the outbound leg - for a fully-connected start point there's a non-empty stack which is the other connection from that starting element
sequences[-1].append(startpt)
else:
# stack is empty so insert new points at the start of this sequence - this ensures the sequence on the list is consecutive even if the outgoing sequence didn't come back here
sequences[-1].insert(0,startpt)
print( f"continuing from {startpt=}" )
else:
if sequences:
print( f"FINISHED {sequences[-1]=}" )
if len(todos)==0:
break
# new sequence
startpt = todos.pop(0)
sequences.append([startpt])
print( f"starting from {startpt}" )
nextpos = possiblecentres[startpt][-1][0][1]
nextneg = possiblecentres[startpt][-1][1][1]
print( f"{nextpos=} {nextneg=}" )
if nextpos is not None:
if nextpos in todos:
# hasn't been used yet
if startpt == possiblecentres[nextpos][-1][0][1]:
print( f"pos match1 pushing {nextpos}" )
stacktochecks.append(nextpos)
todos.remove(nextpos)
elif startpt == possiblecentres[nextpos][-1][1][1]:
print( f"pos match2 pushing {nextpos}" )
stacktochecks.append(nextpos)
todos.remove(nextpos)
else:
#
todos.remove(nextpos)
pass
# burp3
else:
if nextpos in sequences[-1]:
# already in sequences, so we closed the loop!
# burp1
pass
else:
# not in current sequence and not in todos - that's weird, but end the sequence
pass
# burp2
# pass
if nextneg is not None:
if nextneg in todos:
# hasn't been used yet
if startpt == possiblecentres[nextneg][-1][0][1]:
print( f"neg match1 pushing {nextneg}" )
stacktochecks.append(nextneg)
todos.remove(nextneg)
elif startpt == possiblecentres[nextneg][-1][1][1]:
print( f"neg match2 pushing {nextneg}" )
stacktochecks.append(nextneg)
todos.remove(nextneg)
else:
#
todos.remove(nextneg)
pass
# burp4
else:
if nextneg in sequences[-1]:
# already in sequences, so we closed the loop!
# burp5
pass
else:
# not in current sequence and not in todos - that's weird, but end the sequence
pass
# burp6
# pass
print( f"{sequences=}")
image = cv2.imread(TRACK)
# now display the sequences, and put circles on the startpoints
for i,seq in enumerate(sequences):
for j,node in enumerate(seq):
thisnode = possiblecentres[node]
thisrect = (thisnode[0],thisnode[1],thisnode[2])
box = cv2.boxPoints(thisrect)
box = np.int0(box)
cv2.drawContours(image, [box], -1, (255, 255, 0), 1)
thisx,thisy = thisnode[0][0],thisnode[0][1]
if j == 0:
cv2.circle(image,(int(thisx),int(thisy)),10,(0,127,127),2)
firstx,firsty = thisx,thisy
if j > 0:
# draw a thick line to previous
cv2.line(image,(int(lastx),int(lasty)),(int(thisx),int(thisy)),(127,127,127),5)
if j!=0 and j+1==len(seq):
# this is the connection back to the start
cv2.line(image,(int(firstx),int(firsty)),(int(thisx),int(thisy)),(127,127,127),5)
lastx,lasty = thisx,thisy
cv2.imshow('Sequences', image)
cv2.waitKey(0)
Вещи, которые, вероятно, можно было бы улучшить, - это привести в порядок расчет пересечения, например, изменить мою выдумку на просто считайте два отрезка параллельными, используя угол, под которым они находятся, а не значение denom. Теперь есть известный хороший ответ, который вы можете использовать для проверки того, что изменения ничего не ломают - может быть довольно сложно обнаружить аномалии в обнаружении соседей, конечно, непросто на полном изображении, если показаны все соединения, поэтому мне пришлось сделать шаг через обнаружение и сосредоточиться на обнаруженных соединениях для определенного прямоугольника, чтобы понять, почему соединение перескакивает через соседа, чтобы исправить лог c.
Промежуточное изображение после фазы 2, показывающее все соединения - синее соединение - положительный, зеленый - отрицательный. ПРИМЕЧАНИЕ многие соединения накладываются друг на друга, поэтому, особенно между соседними прямоугольниками, вы видите только тот, который нарисован последним.
Вот длинная последовательность дорожки - числа являются индексами в центрах. json массив, прямоугольник 0 находится в самой нижней точке изображения (визуально), который связан с 1 и 18 может быть на один или два пикселя выше.
[18, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 19, 20, 21, 22, 12, 13, 23, 30, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 72, 88, 93, 94, 95, 97, 99, 102, 104, 105, 119, 124, 143, 144, 145, 147, 149, 152, 159, 163, 168, 172, 175, 177, 178, 176, 174, 169, 167, 165, 162, 160, 156, 155, 153, 154, 157, 161, 164, 170, 180, 182, 184, 186, 189, 191, 194, 193, 192, 190, 188, 185, 183, 181, 173, 166, 158, 151, 148, 146, 142, 135, 131, 127, 123, 120, 112, 111, 110, 108, 109, 114, 116, 117, 121, 125, 128, 132, 134, 137, 139, 140, 141, 138, 136, 133, 130, 126, 122, 118, 113, 107, 106, 103, 101, 98, 96, 87, 68, 60, 59, 61, 63, 62, 64, 65, 67, 66, 70, 71, 73, 75, 74, 76, 78, 77, 79, 81, 80, 82, 85, 84, 86, 90, 89, 92, 91, 83, 69, 58, 56, 54, 52, 50, 48, 46, 44, 42, 40, 38, 36, 34, 32, 31, 28, 29, 24, 25, 26, 27, 14, 15, 16, 17]
В следующий раз я настрою автомобильная трасса слотом scalextri c Попробую сфотографировать, посмотрю, работает ли этот код: -)