teoria producto por plano pares ordenados multiplicacion mismo hallar enseñar ejercicios conjuntos conjunto como cartesiano axb axa algorithm image-processing geometry

algorithm - producto - Transformación entre dos conjuntos de puntos.



plano cartesiano de conjuntos (5)

Le daría una oportunidad al algoritmo iterativo de punto más cercano .

Here encontrarás una implementación con escalado. (SICP)

Otro link útil

Tengo objeto digamos en la imagen del modelo. Quiero calcular la transformación (desplazamiento, escala, rotación) entre el objeto en la imagen del modelo y el objeto en la imagen de destino. Quiero suponer que los objetos se pueden tratar como 2D, por lo que solo se deben calcular las transformaciones 2D.

Primero quiero hacerlo de forma manual asistida. El usuario selecciona el punto base en la imagen del modelo y luego el punto de destino en la imagen de destino. El número de puntos debe ser definido por el usuario (pero no menos de unos 2-3 puntos mínimos). Cuando los puntos proporcionan información diferente, la transformación debe promediarse y, por ejemplo, a partir de esto, se puede calcular la calidad de la coincidencia.

Así que las preguntas son más bien sobre la transformación informática de dos conjuntos de puntos, pero como quiero hacerlo en la imagen, he agregado una etiqueta de procesamiento de imagen.

Especialmente bienvenidas son las referencias y consejos con algunos códigos o pseudocódigos.

Con dos puntos es un asunto muy fácil, solo se debe tomar la rotación, la escala y el desplazamiento de la línea, pero cómo hacerlo con más puntos, y promediarla y calcular algunos factores de calidad.

La solución actual es:

void transformFnc(std::vector<PointF> basePoints, std::vector<PointF> targetPoints, PointF& offset, double rotation, double scale) { std::vector<Line> basePointsLines; std::vector<Line> targetPointsLines; assert(basePoints.size() == targetPoints.size()); int pointsNumber = basePoints.size(); for(int i = 0; i < pointsNumber; i++) { for(int j = i + 1; j < pointsNumber; j++) { basePointsLines.push_back(Line(basePoints[i], basePoints[j])); targetPointsLines.push_back(Line(targetPoints[i], targetPoints[j])); } } std::vector<double> scalesVector; std::vector<double> rotationsVector; double baseCenterX = 0, baseCenterY = 0, targetCenterX = 0, targetCenterY = 0; for(std::vector<Line>::iterator it = basePointsLines.begin(), i = targetPointsLines.begin(); it != basePointsLines.end(), i != targetPointsLines.end(); it++, i++) { scalesVector.push_back((*i).length()/(*it).length()); baseCenterX += (*it).pointAt(0.5).x(); baseCenterY += (*it).pointAt(0.5).y(); targetCenterX += (*i).pointAt(0.5).x(); targetCenterY += (*i).pointAt(0.5).y(); double rotation; rotation = (*i).angleTo((*it)); rotationsVector.push_back(rotation); } baseCenterX = baseCenterX / pointsNumber; baseCenterY = baseCenterY / pointsNumber; targetCenterX = targetCenterX / pointsNumber; targetCenterY = targetCenterY / pointsNumber; offset = PointF(targetCenterX - baseCenterX, targetCenterY - baseCenterY); scale = sum(scalesVector) / scalesVector.size(); rotation = sum(rotationsVector) / rotationsVector.size(); }

La única optimización que puedo encontrar en este código es eliminar de las escalas y rotaciones aquellos valores que difieren demasiado del resto.

Estoy buscando códigos o pseudocódigos de propuestas de solución. También pueden ser referencias a algunos códigos.

Tan lejos de las respuestas sé que:

  • Se puede utilizar el algoritmo RANSAC
  • Necesito buscar algún algoritmo de computación de transformación afín en el sentido más mínimo.

Para simplificar, suponga que sus entradas x1,...,xn y salidas y1,...,yn son números complejos.

  1. Puede calcular el desplazamiento promedio al calcular avg(y) - avg(x) , y una vez hecho esto, puede restar el promedio a x e y para que se centren alrededor de 0.

  2. Ahora quieres encontrar una rotación y escala. Puede representar ambos como un solo número complejo z , de modo que x*z debería estar lo más cerca posible de y . Pero x*z es una función R- lineal de las coordenadas (reales) (zx,zy) de z : así que puedes usar el álgebra lineal clásica para resolver z tal forma que x*z esté lo más cerca posible de y en lo más mínimo sentido cuadrado.

Poniéndolo todo junto, esto le da la transformación óptima en el sentido menos cuadrado.

Primero, generalice el problema en una transformación afín simple con una matriz de transformación afín de 3x3: ie

[M11 M12 M13] [M21 M22 M23] [M31 M32 M33]

Como ya sabemos que la tercera fila siempre será [0 0 1], simplemente podemos ignorarla.

Ahora podemos describir el problema como la siguiente ecuación matricial.

[xp0] [x0 y0 1 0 0 0 ] [yp0] [0 0 0 x0 y0 1 ] [M11] [xp1] [x1 y1 1 0 0 0 ] [M12] [yp1] = [0 0 0 x1 y1 1 ] * [M13] [xp2] [x2 y2 1 0 0 0 ] [M21] [yp2] [0 0 0 x2 y2 1 ] [M22] [xp3] [x3 y3 1 0 0 0 ] [M23] [yp3] [0 0 0 x3 y3 1 ]

donde xp y yp son las coordenadas proyectadas y x e y son las coordenadas originales.

Llamemos a esto

proj = M * trans

Entonces podemos calcular un ajuste de mínimos cuadrados para la transformación por

trans = pinv(M) * proj

donde pinv es el pseudo inverso.

Esto nos da una transformación afín que se ajusta mejor a los puntos dados en el sentido de los mínimos cuadrados.

Ahora, obviamente, esto también proporcionará cortes de cizallamiento, coordenadas y escalas no uniformes que no deseaba, por lo que debemos limitar la transformación afín de alguna manera para evitar el cizallamiento. Esto resulta ser bastante fácil, podemos usar un solo vector para describir la rotación (dirección del vector) y escala (magnitud del vector), el otro vector simplemente será ortogonal a él. Esto reduce los grados de libertad en dos.

M21 = -M12 M22 = M11

Así que reduce a

[xp0] [x0 y0 1 0] [yp0] [y0 -x0 0 1] [xp1] [x1 y1 1 0] [M11] [yp1] = [y1 -x1 0 1] * [M12] [xp2] [x2 y2 1 0] [M13] [yp2] [y2 -x2 0 1] [M23] [xp3] [x3 y3 1 0] [yp3] [y3 -x3 0 1]

y calcule M21 y M22 a partir de M12 y M11 una vez que hayamos resuelto la ecuación de matriz anterior.

Su transformación es una transformación afín, que se puede escribir en una matriz de 3 * 3. Entonces, su problema es básicamente calcular la transformación afín de error de media cuadrática de un conjunto de puntos a los otros.

Este problema se resuelve simplemente en la literatura de geometría computacional común. Un buen libro clásico es este: http://www.robots.ox.ac.uk/~vgg/hzbook/hzbook1.html (sin anuncios, es solo el libro de referencia para la mayoría de las personas). Encontrarás toda la información sobre geometría 2D y 3D. Un rápido google en palabras como "afines transformación LMSE" también le dará información y códigos.

Además, también puedes usar otros tipos de algoritmos, robustos, como RANSAC. Dependiendo de su aplicación, puede ser interesante ir más allá en esa dirección.