Überschneidung von 2D-Polygonen

Question

Ich habe zwei numpy-Arrays, die OpenCV konvexe Hüllen sind, und ich möchte auf Schnittstellen überprüfen, ohne Schleifen zu erstellen oder Bilder zu erstellen und numpy.bitwise_and darauf auszuführen, was beides in Python ziemlich langsam ist. Die Arrays sehen so aus:

[[[x1 y1]]
 [[x2 y2]]
 [[x3 y3]]
...
 [[xn yn]]]

Wenn [[x1 y1]] als ein einzelnes Element betrachtet wird, möchte ich den Schnitt zwischen zwei numpy ndarrays durchführen. Wie kann ich das machen? Ich habe ein paar Fragen ähnlicher Art gefunden, aber ich konnte die Lösung dafür nicht daraus ableiten.

Answer 1

Sie können eine Ansicht des Arrays als Eindimensional zur intersect1d-Funktion wie folgt verwenden:

def multidim_intersect(arr1, arr2):
    arr1_view = arr1.view([('',arr1.dtype)]*arr1.shape[1])
    arr2_view = arr2.view([('',arr2.dtype)]*arr2.shape[1])
    intersected = numpy.intersect1d(arr1_view, arr2_view)
    return intersected.view(arr1.dtype).reshape(-1, arr1.shape[1])

Dies erstellt eine Ansicht jedes Arrays, wobei jede Zeile in ein Tupel von Werten geändert wird. Anschließend erfolgt der Schnitt und das Ergebnis wird wieder im Originalformat geändert. Hier ist ein Beispiel zur Verwendung:

test_arr1 = numpy.array([[0, 2],
                         [1, 3],
                         [4, 5],
                         [0, 2]])

test_arr2 = numpy.array([[1, 2],
                         [0, 2],
                         [3, 1],
                         [1, 3]])

print multidim_intersect(test_arr1, test_arr2)

Dies gibt aus:

[[0 2]
 [1 3]]

Answer 2

Sie können http://pypi.python.org/pypi/Polygon/2.0.4 verwenden, hier ist ein Beispiel:

>>> import Polygon
>>> a = Polygon.Polygon([(0,0),(1,0),(0,1)])
>>> b = Polygon.Polygon([(0.3,0.3), (0.3, 0.6), (0.6, 0.3)])
>>> a & b
Polygon:
  <0:Contour: [0:0.60, 0.30] [1:0.30, 0.30] [2:0.30, 0.60]>

Um das Ergebnis von cv2.findContours in das Polygon-Punktformat zu konvertieren, können Sie:

points1 = contours[0].reshape(-1,2)

Dies konvertiert die Form von (N, 1, 2) in (N, 2)

Hier ist ein vollständiges Beispiel:

import Polygon
import cv2
import numpy as np
from scipy.misc import bytescale

y, x = np.ogrid[-2:2:100j, -2:2:100j]

f1 = bytescale(np.exp(-x**2 - y**2), low=0, high=255)
f2 = bytescale(np.exp(-(x+1)**2 - y**2), low=0, high=255)

c1, hierarchy = cv2.findContours((f1>120).astype(np.uint8), 
                                       cv2.cv.CV_RETR_EXTERNAL, 
                                       cv2.CHAIN_APPROX_SIMPLE)

c2, hierarchy = cv2.findContours((f2>120).astype(np.uint8), 
                                       cv2.cv.CV_RETR_EXTERNAL, 
                                       cv2.CHAIN_APPROX_SIMPLE)

points1 = c1[0].reshape(-1,2) # konvertiere Form (n, 1, 2) zu (n, 2)
points2 = c2[0].reshape(-1,2)

import pylab as pl
poly1 = pl.Polygon(points1, color="blue", alpha=0.5)
poly2 = pl.Polygon(points2, color="red", alpha=0.5)
pl.figure(figsize=(8,3))
ax = pl.subplot(121)
ax.add_artist(poly1)
ax.add_artist(poly2)
pl.xlim(0, 100)
pl.ylim(0, 100)

a = Polygon.Polygon(points1)
b = Polygon.Polygon(points2)
intersect = a&b # berechne das Schnittpolygon

poly3 = pl.Polygon(intersect[0], color="green") # intersect[0] sind die Punkte des Polygons
ax = pl.subplot(122)
ax.add_artist(poly3)
pl.xlim(0, 100)
pl.ylim(0, 100)
pl.show()

Ergebnis:

Answer 3

Also das ist, was ich gemacht habe, um die Aufgabe zu erledigen:

import Polygon, numpy

# Hier habe ich einige Konturen extrahiert und kombiniert und daraus eine konvexe Hülle erstellt.
# Jetzt möchte ich überprüfen, ob eine auf andere Weise erworbene Kontur mit dieser Hülle überschneidet oder nicht.

for contour in contours:  # Das Ergebnis von cv2.findContours ist eine Liste von Konturen
    contour1 = contour.flatten()
    contour1 = numpy.reshape(contour1, (int(contour1.shape[0]/2),-1))
    poly1 = Polygon.Polygon(contour1)

    hull = hull.flatten()  # Dies ist die zuvor konstruierte Hülle
    hull = numpy.reshape(hull, (int(hull.shape[0]/2),-1))
    poly2 = Polygon.Polygon(hull)

    if (poly1 & poly2).area()<= some_max_val:
        some_operations

Ich musste eine for-Schleife verwenden, und das alles sieht insgesamt etwas mühsam aus, obwohl es mir die erwarteten Ergebnisse liefert. Jegliche bessere Methoden wären sehr willkommen!

Answer 4

inspiriert von jiterrace's Antwort

Ich bin auf diesen Beitrag gestoßen, als ich mit Udacity Deep Learning-Kurs( gearbeitet habe, um die Überschneidung zwischen Trainings- und Testdaten zu finden).

Ich bin nicht vertraut mit "Ansicht" und fand die Syntax etwas schwer zu verstehen, wahrscheinlich genauso, wenn ich versuche, mit meinen Freunden zu kommunizieren, die in "Tabelle" denken. Mein Ansatz besteht grundsätzlich darin, das ndarray der Form (N, X, Y) in die Form (N, X*Y, 1) zu flattten/reshape.

print(train_dataset.shape)
print(test_dataset.shape)
#(200000L, 28L, 28L)
#(10000L, 28L, 28L)

1). INNER JOIN (einfacher zu verstehen, aber langsam)

import pandas as pd

%%timeit -n 1 -r 1
def multidim_intersect_df(arr1, arr2):
    p1 = pd.DataFrame([r.flatten() for r in arr1]).drop_duplicates()
    p2 = pd.DataFrame([r.flatten() for r in arr2]).drop_duplicates()
    res = p1.merge(p2)
    return res
inters_df = multidim_intersect_df(train_dataset, test_dataset)
print(inters_df.shape)
#(1153, 784)
#1 loop, best of 1: 2min 56s per loop

2). SET INTERSECTION (schnell)

%%timeit -n 1 -r 1
def multidim_intersect(arr1, arr2):
    arr1_new = arr1.reshape((-1, arr1.shape[1]*arr1.shape[2])) # -1 bedeutet, dass die Zeilenanzahl aus anderen Dimensionen abgeleitet wird
    arr2_new = arr2.reshape((-1, arr2.shape[1]*arr2.shape[2]))
    intersected = set(map(tuple, arr1_new)).intersection(set(map(tuple, arr2_new)))  # liste ist nicht hashbar, deshalb tuple verwenden
    return list(intersected)  # in der Form (N, 28*28)

inters = multidim_intersect(train_dataset, test_dataset)
print(len(inters))
# 1153
#1 loop, best of 1: 34,6 s per loop