Cómo encontrar la pendiente de ciertas líneas que coinciden con puntos aleatorios

Question

Cómo encontrar la pendiente de ciertas líneas que coinciden con puntos aleatorios

cálculo
geometría
algoritmos
regresión
Matemáticas
parametrización

Raxi Ral

Tengo un gran conjunto de puntos aleatorios, $(x_i,y_i)$ , que, por razones desconocidas, parecen alinearse a lo largo de ciertas líneas:

Quiero calcular la pendiente de esas líneas (también sus otros parámetros, pero estoy preguntando sobre la pendiente aquí)

Separar las líneas algorítmicamente parece demasiado complejo. Supongo que necesitaría un algoritmo de clasificación, y esos nunca dan resultados estables.

Por eso solo estoy hablando de la pendiente.

Lo que hice:

Hice una muestra sintética generando líneas aleatorias:

el punto medio $\color{blue}{(c_x,c_y)}$ está dibujado en azul, y en este gráfico, las líneas tienen $-45$ ° ángulo.

Tengo la intuición de que la suma de las distancias de todos los puntos a una línea que pasa por el punto azul debe ser máxima/mínima cuando la línea coincide con la pendiente que estoy buscando (o la pendiente perpendicular).

Calculé la distancia suma de todos los puntos a una línea que pasa por el centro, con ángulo $\alpha$ , para diferentes ángulos (desde $0$ a $360$ ), y obtuve este gráfico:

Dibujé las líneas de puntos en $-45$ °, y la distancia parece ser máxima alrededor del ángulo normal $+45$ , por lo que sugiere que podría usar un solucionador de maximización para encontrar la pendiente normal a las líneas, maximizando la distancia de todos los puntos a una línea que pasa por el centro (punto azul).

Parece funcionar para diferentes ángulos que probé, pero no estoy seguro de si ese es el procedimiento correcto.

Además, la distancia no es mínima cuando la pendiente $\tan(\alpha)$ es paralela a las rectas.

EDITAR: acabo de notar que si los puntos se agrupan en dos grupos distantes, independientemente de la orientación de las líneas, la distancia máxima sería la que separa los grupos. ¿Quizás las transformadas de Fourier podrían detectar la orientación de las líneas?

Glärbo

Tenga en cuenta que en el diagrama donde los puntos forman líneas con una pendiente común (negativa), tiene logarítmico

x

$x$ y

y

$y$ escalas de eje. Entonces, los puntos

(x_{i}, y_{i})

$(x_i, y_i)$ ellos mismos no forman líneas;

(\log x_{i}, \log y_{i})

$(\log x_i, \log y_i)$ hacer. La forma en que abordaría este problema es acumulando puntos

(\log x_{i}, \log y_{i})

$(\log x_i, \log y_i)$ en conjuntos, uniendo cada punto a un conjunto si tiene un vecino lo suficientemente cercano. dado un límite de distancia adecuado, obtendrá varios conjuntos, cada uno para una línea específica, además de algunos conjuntos aleatorios en la región dispersa.

Raxi Ral

@Glärbo Por

(x_{i}, y_{i})

$(x_i,y_i)$ Me refiero al registro, tal como está dibujado. Está describiendo un algoritmo de agrupamiento, pero no hay un criterio general para decidir la "distancia adecuada". El enfoque que describo también puede fallar debido a la estructura a gran escala. Me pregunto si una transformada de Fourier calculada en todos los ángulos detectaría la

α

$\alpha$ de una manera más robusta.

greg martin

La idea de la transformada de Fourier suena prometedora.

Glärbo

@RaxiRal: Agrupación, sí, a través de una estructura de datos de conjuntos disjuntos. Se puede obtener una distancia adecuada a partir del histograma por pares, por ejemplo, el doble de la distancia del 50 % del vecino más cercano (la distancia en la que al menos el 50 % de los puntos tienen al menos un vecino más cercano). Dos veces, porque se esperan grupos lineales (por lo que cada uno tiene dos vecinos más cercanos); 50%, porque se espera que al menos la mitad de los puntos pertenezcan a un grupo lineal (el resto son puntos solitarios en el lado derecho). Este enfoque le da a cada grupo su propio ajuste; luego puede comparar los ajustes de los grupos para determinar si tiene sentido.

Glärbo

Sospecho que encontrará que la transformada de Fourier 2D rotada necesita un análisis similar (como el enfoque de agrupación): terminará mirando

α

$\alpha$ eso maximiza la diferencia en los componentes de alta frecuencia entre los dos ejes, pero ¿cuál es ese límite o rango de alta frecuencia? Los intervalos de línea no son constantes, ni tampoco lo son las distancias entre pares de vecinos más cercanos entre puntos en la misma línea. Esta es la razón por la que usaría un enfoque de agrupamiento discreto, obteniendo un ajuste para cada grupo.

motivos

Usas el término "parece". ¿Qué tan distinguibles son las líneas? ¿Probaste una transformada de Fourier 2D?

Stephen Montgomery Smith

Se parece un poco a la salida de una simulación de dinámica molecular de un cristal bajo tensión. Trate de buscar en la literatura de dinámica molecular.

usuario65203

Este podría ser un trabajo para la transformada de Radon. en.wikipedia.org/wiki/Radon_transform

Respuestas (3)

Cómo encontrar la pendiente de ciertas líneas que coinciden con puntos aleatorios

Tenga en cuenta que en el diagrama donde los puntos forman líneas con una pendiente común (negativa), tiene logarítmico $x$ y $y$ escalas de eje. Entonces, los puntos $(x_i, y_i)$ ellos mismos no forman líneas; $(\log x_i, \log y_i)$ hacer. La forma en que abordaría este problema es acumulando puntos $(\log x_i, \log y_i)$ en conjuntos, uniendo cada punto a un conjunto si tiene un vecino lo suficientemente cercano. dado un límite de distancia adecuado, obtendrá varios conjuntos, cada uno para una línea específica, además de algunos conjuntos aleatorios en la región dispersa.
@Glärbo Por $(x_i,y_i)$ Me refiero al registro, tal como está dibujado. Está describiendo un algoritmo de agrupamiento, pero no hay un criterio general para decidir la "distancia adecuada". El enfoque que describo también puede fallar debido a la estructura a gran escala. Me pregunto si una transformada de Fourier calculada en todos los ángulos detectaría la $\alpha$ de una manera más robusta.
@RaxiRal: Agrupación, sí, a través de una estructura de datos de conjuntos disjuntos. Se puede obtener una distancia adecuada a partir del histograma por pares, por ejemplo, el doble de la distancia del 50 % del vecino más cercano (la distancia en la que al menos el 50 % de los puntos tienen al menos un vecino más cercano). Dos veces, porque se esperan grupos lineales (por lo que cada uno tiene dos vecinos más cercanos); 50%, porque se espera que al menos la mitad de los puntos pertenezcan a un grupo lineal (el resto son puntos solitarios en el lado derecho). Este enfoque le da a cada grupo su propio ajuste; luego puede comparar los ajustes de los grupos para determinar si tiene sentido.
Sospecho que encontrará que la transformada de Fourier 2D rotada necesita un análisis similar (como el enfoque de agrupación): terminará mirando $\alpha$ eso maximiza la diferencia en los componentes de alta frecuencia entre los dos ejes, pero ¿cuál es ese límite o rango de alta frecuencia? Los intervalos de línea no son constantes, ni tampoco lo son las distancias entre pares de vecinos más cercanos entre puntos en la misma línea. Esta es la razón por la que usaría un enfoque de agrupamiento discreto, obteniendo un ajuste para cada grupo.
Usas el término "parece". ¿Qué tan distinguibles son las líneas? ¿Probaste una transformada de Fourier 2D?
Se parece un poco a la salida de una simulación de dinámica molecular de un cristal bajo tensión. Trate de buscar en la literatura de dinámica molecular.
Este podría ser un trabajo para la transformada de Radon. en.wikipedia.org/wiki/Radon_transform

Cesareo · Answer 1

Usando la transformación de Hough (ver aquí) sobre un mapa de bits extraído de la figura original y con algo de ayuda de un repositorio de python. El proceso comienza con la imagen proporcionada sbVut.png

import numpy as np
from skimage.transform import hough_line, hough_line_peaks
import matplotlib.pyplot as plt
from matplotlib import cm
from PIL import Image

"""
To transform the sbVut.png image into sbVut.bmp
"""

img = Image.open('/home/test/Desktop/sbVut.png')
(w,h) = img.size    
for i in range(w):
    for j in range(h):
        (r,g,b) = img.getpixel((i,j))
        r = 255-r
        g = 255-g  
        b = 255-b
        img.putpixel((i,j),(r,g,b))

thresh = 200
fn = lambda x : 255 if x > thresh else 0
r = img.convert('1')
r.save('/home/test/Desktop/sbVut.bmp')

"""
Begins the Hough transform
"""

image = np.array(Image.open('/home/test/Desktop/sbVut.bmp'))

# Classic straight-line Hough transform
(h, theta, d) = hough_line(image)

# Generating figure 1
(fig, axes) = plt.subplots(1, 3, figsize=(15, 6),
                  subplot_kw={'adjustable': 'box'})
ax = axes.ravel()

ax[0].imshow(image, cmap=cm.gray)
ax[0].set_title('Input image')
ax[0].set_axis_off()

ax[1].imshow(np.log(1 + h),
         extent=[np.rad2deg(theta[-1]), np.rad2deg(theta[0]), d[-1], d[0]], cmap=cm.gray, aspect=1/1.5)
ax[1].set_title('Hough transform')
ax[1].set_xlabel('Angles (degrees)')
ax[1].set_ylabel('Distance (pixels)')
ax[1].axis('image')

ax[2].imshow(image, cmap=cm.gray)
for _, angle, dist in zip(*hough_line_peaks(h, theta, d)):
    y0 = (dist - 0 * np.cos(angle)) / np.sin(angle)
    y1 = (dist - image.shape[1] * np.cos(angle)) / np.sin(angle)
    ax[2].plot((0, image.shape[1]), (y0, y1), '-r')
ax[2].set_xlim((0, image.shape[1]))
ax[2].set_ylim((image.shape[0], 0))
ax[2].set_axis_off()
ax[2].set_title('Detected lines')

plt.tight_layout()
plt.show()

y los resultados

usuario65203 · Answer 2

Como los puntos son densos, los segmentos serán aislados por un algoritmo de componentes conectados (o contorneado en OpenCV). No hay ningún cuidado especial que tomar.

Para cada blob, puede encajar una línea, pero supongo que solo con unir los puntos extremos es suficiente.

A continuación, los ángulos formados con la vertical (usando el rectángulo de área mínima) para las 50 manchas más grandes.

De hecho, separar las líneas algorítmicamente parece muy fácil.

Han de Bruijn · Answer 3

El método empleado por nosotros:

Convierta la imagen emitida por el OP al formato de mapa de bits de Windows
Cargue el archivo BMP en un programa de computadora, desarrollado para este propósito
Asigne el contenido de color a números reales (doble precisión)
Defina un nivel cero de esta asignación; en nuestro caso blanco = - 0.2
Defina empíricamente las limitaciones para el área que parece interesante
Use un módulo de contorno para hacer isolíneas en el nivel cero
Utilice todo tipo de limitaciones para distinguir los datos relevantes del resto
Calcule momentos de segundo orden (varianzas) para las isolíneas relevantes
Echa un vistazo a la teoría en la página web Momentos bidimensionales
Preste especial atención a la fórmula. $\;\tan(2 \theta) = 2 \sigma_{xy}/(\sigma_{xx} - \sigma_{yy})$
Calcular valor medio $\pm$ dispersión de ángulos relevantes $\alpha=-\theta$ y salida

El resultado final numérico obtenido es:

Alfa = 38 +/- 2 grados

Imagen producida:

Nota.
Un método más robusto puede ser considerar en su lugar los ángulos de los ejes menores de las elipses de inercia $\;\sigma_{yy}(x-\mu_x)^2-2\sigma_{xy}(x-\mu_x)(y-\mu_y)+\sigma_{xx}(y-\mu_y)^2=\sigma_{xx}\sigma_{yy}-\sigma_{xy}^2\;$ con el eje x.

El software complementario gratuito solo de origen (Delphi Pascal) está disponible en el sitio: publicaciones/referencias de MSE 2021
Descargo de responsabilidad . Todo lo gratis viene sin garantía :-(y sin árbitro)

Cómo encontrar la pendiente de ciertas líneas que coinciden con puntos aleatorios

Raxi Ral

Glärbo

Raxi Ral

greg martin

Glärbo

Glärbo

motivos

Stephen Montgomery Smith

usuario65203

Respuestas (3)

Cesareo

usuario65203

usuario65203

Han de Bruijn

¿Determinar los límites de una integral triple?

Encontrar el promedio con respecto a la longitud del arco

Aplicaciones geométricas de números complejos

¿Qué significa la palabra "escalabilidad" en términos de Big O?

Rotar un punto en un círculo con radio y posición conocidos

¿Por qué importa el signo en el método de Newton?

Minimizar el número de puntos en una aproximación lineal por partes

Trabajo realizado por F⃗ =sin(x2)x^+(3x−y)y^F→=sin⁡(x2)x^+(3x−y)y^\vec F=\sin(x^2)\hat x+(3x-y)\qué y necesita integral problemática?

El área promedio de la sombra de un cuadrado.

¿Hay algún nombre o algún tipo de definición para una curva trazada por un objeto que se mueve continuamente hacia otro?