Cómo ajustar una elipse a datos 2D

7

Me gustaría encontrar el "mejor" ajuste de una elipse a formas contiguas, posiblemente cóncavas como:

ingrese la descripción de la imagen aquí

Que he probado

Pensé que se podía asignar la dirección de los ejes mayor y menor. a,bde la elipse mapeando los valores de píxel a las coordenadas, restando la media y guardando los dos vectores propios más grandes de un PCA. Parece que funciona bastante bien para encontrar la dirección:

ingrese la descripción de la imagen aquí

Mi problema es determinar la longitud de estos dos vectores. Por ahora, he usadoλ1 λ2, de los valores propios de la PCA. Esto parece subestimar la longitud. ¿Cómo puedo determinar|a|y |b| o como alternativa, ¿se ajusta mejor una elipse a estas formas?

Enganchado
fuente
Por lo que entiendo, los valores propios miden la "potencia" del radio espectral de ese vector propio particular. No tengo los números que estás usando, pero noλ1 y λ2más en línea con las longitudes reales?
Spacey
Tienes razón sobre la relación de λa la fuerza de la proyección de vectores propios, pero no se me ocurrió otra cosa para usar. Utilizandoλ Opuesto a λescala los vectores fuera del gráfico en varios órdenes de magnitud. Simplemente elegí elcomo una suposición inicial
Enganchado
Como solo es bidimensional, publique los vectores propios que ha encontrado y sus valores propios correspondientes. Además, los puntos máximo / mínimo en cualquier borde del dibujo.
Spacey

Respuestas:

6

Continuando con mi respuesta eliminada ... Si toma una elipse llena y proyecta todos los puntos en el xeje, se proyectarán más puntos cerca del origen que en los extremos, en una distribución de forma circular. No es una distribución gaussiana, y no la distribución uniforme que mencioné en la analogía 1-D en mi respuesta eliminada. La distribución resultante en realidad tiene pdfp(x)=(1(xr)2), y desde allí puede calcular que la desviación estándar es r2.

Por lo tanto, si los datos se distribuyen uniformemente en el interior de una elipse de radios a,b (cuyos ejes son el x y y ejes), la desviación estándar de la x coordenada es a2 y de la y coordenada es b2. Entonces, el factor de corrección que necesita usar es simplemente 2.

Aquí hay un ejemplo trabajado en python que recupera el centro (matriz de traducción), la matriz de rotación y los radios de una elipse desde puntos muestreados aleatoriamente desde su interior:

import numpy

# Generate some points distributed uniformely along an ellipse
x = 2 * (numpy.random.rand(10000, 1) - 0.5)
y = 2 * (numpy.random.rand(10000, 1) - 0.5)
d = (x / 0.5) ** 2 + (y / 0.25) ** 2
inside = numpy.where(d < 1)[0]
x = x[inside]
y = y[inside]
data = numpy.hstack((x, y)).T

# Now rotate by 0.5 rad and translate it to (4, -8)
angle = 0.5
rotation = numpy.array([
    [numpy.cos(0.4), -numpy.sin(0.4)],
    [numpy.sin(0.4), numpy.cos(0.4)]])

data = numpy.dot(rotation, data)
data[0, :] += 4
data[1, :] -= 8

# Step 1: center the data to get the translation vector.
print 'Translation', data.mean(axis=1)
data -= numpy.reshape(data.mean(axis=1), (2, 1))

# Step 2: perform PCA to find rotation matrix.
scatter = numpy.dot(data, data.T)
eigenvalues, transform = numpy.linalg.eig(scatter)
print 'Rotation matrix', transform

# Step 3: Rotate back the data and compute radii.
# You can also get the radii from smaller to bigger
# with 2 / numpy.sqrt(eigenvalues)
rotated = numpy.dot(numpy.linalg.inv(transform), data)
print 'Radii', 2 * rotated.std(axis=1)
pichenettes
fuente
1
+1 ¿Le importaría ampliar cómo exactamente obtuvo el PDF p(x)=1(xr)2? Va al meollo de la cuestión. Gracias.
Spacey
El procedimiento estándar para derivar una distribución marginal 1-D a lo largo de un eje a partir de una distribución 2-D (se integra a lo largo del otro eje). La integral es entonces la longitud de una sección de la elipse, ortogonal al eje en el que proyecta.
pichenettes
3

Compruebe el ajuste de mínimos cuadrados directos de elipses por Fitzgibbon et al. ¡Es un problema de valor propio simple, cuyo tamaño no es proporcional al número de píxeles en su muestra! El único paso que depende de la cantidad de píxeles que le arroje es el cálculo de una matriz de dispersión, que aún esO(n).

pichenettes
fuente
Gracias por la referencia @pichenettes, pero ese documento no se parece a lo que estoy tratando de resolver (corríjame si me equivoco). En el documento, intentan minimizar la distancia de mínimos cuadrados de un conjunto de puntos a la curva de una elipse. En mi caso, tengo un área que me gustaría aproximar con una elipse de la mejor manera posible.
Enganchado
Ah ya veo ... lo siento
pichenettes
Sin embargo, es un enlace útil, pero encontré documentos similares cuando hice una búsqueda en Google para una elipse de mejor ajuste. Al parecer, ese problema está bien definido!
Enganchado
¿Pero no podría derivar el contorno del área y aplicarle papel @pichenettes?
Jean-Yves
Creo que hay casos de esquina (¿formas extrañas?) En las que una elipse que es una buena coincidencia para el contorno no sería una buena coincidencia para la superficie.
pichenettes