Comparar Imagenes y encontrar similitudes.

[footer]

Hola buenas noches a todos. Un amigo me desafio a ver si podia resolver algo, el desafio consistia en hacer que la computadora reconozca dos imagenes de entre 5, esas dos imagenes son la misma imagen pero con algunas modificaciones. Mejor les dejo algunas imagenes para que se entienda mejor la imagen del desafio es esta:



Lo primero que hice fue pintar el fondo de negro y filtrar la imagen a escala de grises y obtuve esto:




Luego lo que hice fue separar las subimagenes y obtener su borde y obtuve estas:







Ahora no se como continuar, queria saber como hago para detectar similitudes entre las imagenes, no puedo hacerlo por medio del color de los pixeles ya que las imagenes varian sus colores, aqui dio casualidad que justo el amarillo esta en ambas imagenes iguales pero la forma es lo que vale ya que a veces tocan colores muy distintos.

Queria saber si alguien tiene conocimiento sobre detectar patrones en las imagenes que me permitan saber que figura tengo alli, o algun libro o pdf que hable del tema.

Aqui les dejo el codigo con que he estado intentando, esta incluida la imagen del desafio, esta hecho en java y se me hizo un poquito espaguetti jaja pero esta todo comentado. Suerte.

Link: https://drive.google.com/open?id=0B1i-JNEuRD1zV3FQTmJ6X2pBN3M

[Serapis]

...primero debes detectar los bordes salientes...

Esto es:
- Recorre la imagen horizontalmente bajando hasta tocar el primer píxel, luego ídem pero desde abajo hacia arriba.
- Recorre la imagen verticalmente avanzando a la derecha hasta que toques el primer píxel, luego ídem pero desde la derecha y avanzando hacia la izquierda...

La forma más exacta, es resaltar los vértices salientes... Imagina que con un lápiz trazas líneas para encerrar cada figura en un polígono, pero siempre con ángulos convexos ('reentrantes', nunca cóncavos hacia afuera) y siempre tocando la figura, por supuesto.

Mediante la comparación luego de:
A - La superficie interna del polígono. buen candidato para determinar rápidamente los similares (pero no óptimo si varían en tamaño)
B - La cantidad de lados del polígono resultante. Buen candidato para a primera vista determinar similitud incluso entre diferentes tamaños.
C - Los ángulos que forman cada par de lados del polígono. Es la tarea final, las previas son aproximaciones rápidas.

Y con esto  es relativamente asequible determinar su similitud con un porcentaje.
Éste algoritmo sería el adecuado, si además las formas tienen diferente tamaño (dos figuras iguales o muy parecidas pero de diferente tamaño), ya que los ángulos se mantienen así como el número de lados del polígono.




Basicamente  en pseudocódigo son estos pasos:
Esta sería la función principal (tras los pasos que llevas)

Código [Seleccionar] Expandir

Buleano = Funcion Buscarsimilitudes(Lista de Imagenes Figuras )
   Lista Poligonos  // lista de poligono
   Lista Poligono // lista de líneas

   Por cada figura en Figuras
        Poligono = CrearPoligono(figura)
        Poligonos.Add (Poligono)
   Siguiente

   Bucle para j desde 0 Poligonos.Length -2  //el último se debe comparar
       Poligono = Poligonos.Item(j)
       Bucle para k desde j a Poligonos.Length -1
           Si EsSimilar(Poligono, Poligonos.Item(k))  luego
               // Mostrar coincidencia en la forma que tengas previsto.  
               Similares = TRUE
           Fin si
       Siguiente
   Siguiente
 
   Devolver Similares //si al menos hubo 2 similares entre sí, devolverá TRUE.
Fin Funcion

Aquí el pseudocódigo para crear un polígono de cada imagen (a grandes rasgos).
Tu primer paso será entonces un "localizador de puntos salientes" de la figura...
El segundo, será un "trazador de líneas"... primero empezamos con los 4 puntos (uno de cada orientación, se trata de intentar lanzar una línea de uno de ellos al del lado contiguo, si corta en algún punto la figura, se debe buscar otro punto saliente entre medias y repetir).
Es mejor usar una lista que un array porque no se sabe cuanto se va a almacenar.

Código [Seleccionar] Expandir

Lista = Funcion CrearPoligono(imagen Figura)
   Lista Puntos  //donde señaden los puntos.
   Lista Poligono //donde se añaden las líneas
   entero j, k
   punto centro

   centro = PuntoCentral(Figura) // se trata de hallar aprox, el punto central de la imagen, un eje de cordenadas en el centro.
   Puntos = BuscarLos4PuntosMásSalientes // (de las 4 orientaciones), da igual si prefieres buscarlos en diagonal, pero es más complejo recorrer así la imagen.    
   j=0
   k=(j+1)
   Hacer
       Linea = TrazarLinea(puntos.Item(j), Puntos.Item(k) )
       Si Linea CortaFigura(Linea, Figura) luego //Si la línea corta la figura...
           Punto = Buscar nuevo punto saliente entre ambos, y añadir delante del destino
           Puntos.Add(punto, k)            
       Sino
           //OJO: No trato el caso de que k sea el último y el 3º punto debiera ser el primero el 0º
           // queda a tu esfuerzo modificarlo como convenga...
           Si AnguloEsConcavo(puntos.Item(j), Puntos.Item(k),  Puntos.Item(k+1), centro ) = FALSE luego
             
               Poligono.Add(Linea)
               j = k
               Si (k < Puntos.Count) luego                  
                   k +=1
               Sino
                   Si (k=0) luego
                      Conectado = TRUE
                   Sino
                       k = 0
                   Fin si
               Fin si
           Sino
               El punto intermedio entre los dos se elimina // hace concavidad, la búsqueda (la programación) del más saliente no fue 'adecuada', pero bueno esto nos permite avanzar aunque sea más lentamente.
               // j y k no cambian, así al retorno se traza la línea entre esos dos (que antes tenían uno en medio).
           Fin si
       Fin si
   Repetir Mientras (Conectado= FALSE)
   Devolver Poligono
Fin funcion


También puedes buscar similitud por perímetro cuando el número de lados es desigual. Si la superficie y el perímetro son similares hay probabilidades.

Código [Seleccionar] Expandir

Buleano = EsSimilar(Lista p1, Lista p2)  // p1 y p2 son sendos polígonos
   Area1 = HallarArea(p1)
   Area2 = HallarArea(p2)
 
   Si SimilitudPorTolerancia(Area1, Area2, ToleranciaArea) = TRUE luego  //tolerancia debe expresarse en forma de porcentaje aceptable, p.e.: '90' por ciento.
        // son de tamaño similar, no hay zoom, o es escaso.
       Si SimilitudAngulos(p1, p2, ToleranciaAngulos) = TRUE luego
           Devolver TRUE
       Fin si
   Sino  // son distintos, puede que uno esté con zoom... comprobamos lados y angulos
       // comprobamos la similitud en el número de lados.
       Si SimilitudPorTolerancia(p1.Length, p2.Length, ToleranciaLados) = TRUE luego
           Si SimilitudAngulos(p1, p2, ToleranciaAngulos) = TRUE luego
               Devolver TRUE
           Fin si
       Si no
           // El número de lados si no cincide ver si hay o falta un lado de tamaño muy corto, pero no se expone aquí...
           // Si cambia el númeor de lados, vamos a exigir más exactitud, con los ángulos
           Si SimilitudAngulos(p1, p2, ToleranciaAngulos+ToleranciaExigente) = TRUE luego
               Devolver TRUE
           Fin si
       Fin si
   Fin si
Fin Funcion

Tolerancia debe ser un valor en el rango 1-100, pero si se pone 100 exige exactitud total, y si se pone 1, una casa será igual que un coche, un valor adecuado podría ser 90% es decir uno es similar a otro si es un 90% del área (esto es solo varía un 10%, no confundir ambos valores, pués puede hacerse  al derecho o al revés).

Código [Seleccionar] Expandir

Buleano = Funcion SimilitudPorTolerancia(entero v1, entero v2, byte Tolerancia)
   Si (v1 >= v2) luego  //
       Si (((v1/100) * Tolerancia) >= v2) luego Devolver TRUE
   Sino
       Si (((v2/100) * Tolerancia) >= v1) luego Devolver TRUE
   Fin si
Fin Funcion

Se traza una línea ente los puntos extremos, y considerando el centro, se ve si p2, a que lado queda
respecto de la línea, según el centro debe quedar en un sitio u otro para saber si es cóncavo o convexo.

Código [Seleccionar] Expandir

Buleano = Funcion  AnguloEsConcavo(Punto p1, Punto p2, Punto p3, Punto centro)
  Linea  
   
   Linea = TrazarLínea(p1,p3) //Trazar una línea desde p1 a p3

   //Ver donde queda p2 respecto de la linea y según p1 y p3 estén orientados respecto del centro
   Si p1.X < centro.x
       // Sin terminar... queda a tu esfuerzo
   Sino
       // Sin terminar... queda a tu esfuerzo
   Fin si
Fin Funcion

Código [Seleccionar] Expandir

Buleano = Funcion SimilitudAngulos(Poligono pol1, Poligono pol2)
   Lista Angs1, Angs2
   Decimal ang1, ang2  //valor en  coma flotante
   Buleano Similares

   Angs1 = AngulosPoligono(pol1)
   Angs2 = AngulosPoligono(pol2)

   // Quizás una figura esté rotada respecto de otra, luego exige encontrar ekl punto de coincidencia.
   // pero puede pasar que haya más de un ángulo en una figura que tenga el mismo que otro en la otra figura...
   Bucle para i desde 0 a Angs1.Length
       ang1 = Angs1.Item(i)
       Bucle para cada j desde 0 a Angs2.length
           ang2 = Angs1.Item(j)
           // se convierten a enteros, tal como exige la función...
           Si SimilitudPorTolerancia(ConvertirAEntero(ang1), ConvertirAEntero(ang2), ToleranciaAngulo) = TRUE luego
               Similares = TRUE
               Bucle para k desde j+1 a Angs1.Length
                   ang2 = Angs1.Item(k)
                   Si SimilitudPorTolerancia(ConvertirAEntero(ang1), ConvertirAEntero(ang2), ToleranciaAngulo) = False luego
                       Similares = FALSE
                       Salir del bucle
                   Fin si
               Fin Bucle
               Si (Similares = TRUE) luego Devolver TRUE
           Fin si
       Fin bucle    
   Fin Bucle
Fin Funcion

Crea una lista con los ángulos del polígono.

Código [Seleccionar] Expandir

Lista = Funcion AngulosPoligono(Poligono Pol)
   Lista Angulos
   Punto p1, p2, p3
   
   p1 = pol1.Item(0)
   p2 = pol1.Item(1)
   p3 = pol1.Item(2)
   Angulo = AnguloFormado3Pt(p1, p2, p3)
   Angulos.Add(angulo)
   Bucle para j desde 3 a p1.Length - 1 // si es un triángulo, no entrará en el bucle        
       p1=p2
       p2=p3
       p3= pol1.Item(j)
       Angulo = AnguloFormado3Pt(p1, p2, p3)
       Angulos.Add(angulo)
   Fin bucle
   // Faltan 2 ángulos, los formados por el final y el comienzo
   p1=p2
   p2=p3
   p3= pol1.Item(0)    
   Angulo = AnguloFormado3Pt(p1, p2, p3)
   Angulos.Add(angulo)

   p1=p2
   p2=p3
   p3= pol1.Item(1)    
   Angulo = AnguloFormado3Pt(p1, p2, p3)
   Angulos.Add(angulo)
   
   Devolver Angulos
Fin Funcion

Código [Seleccionar] Expandir

Decimal = AnguloFormado3Pt(Punto p1, Punto p2, Punto p3)
  // queda a tu esfuerzo, son simples matemáticas...
Fin funcion

Aumento una de las figuras y realizo un pequeño dibujo a mano alzada. Nota el número de lados del polígono que encierra la figura, sus ángulos, etc... así te formas una idea y con esto debiera valerte... aunque tienes trabajo por delante...

[Serapis]

Olvidaba decirte, que hay otra más sencilla y rápida, pero es aplicable solo cuando tengas la seguridad de que las imágenes tienenn todas la misma orientación y si no es así, deben antes ser rotadas, considerando los 4 puntos más sobresalientes de uno consderado centro.

Esto es, si hay que rotarlas, primero trazas un punto que inscriba por completo la figura, pero tocando en al menos 3 puntos el exterior del perímetro de la figura.
Luego buscas 3-4 puntos más alejados del centro.

Esos puntos te sirven para saber cuanto puede estar rotada una figura respecto d ela otra y si es preciso se rotan. También para saber si una está desplazada respecto de otra.

Recuerda que debemos tener imágenes donde el fondo es blanco y la figura (no solo el trazo que la encierra) es negro (o viceversa), pero si es transparente hay que considerar la transparencia del color opuesto a la tinta d ela figura (blanco o negro).

Finalmente solo cuando estés seguro que 'encajan' en el mismo centro.

Entonces se hace una operación xor entre los píxeles de ambas imágenes. El resultado será el siguiente:
255 xor 255 = 0
0 xor 0 = 0
255 xor 0 = 255
0 xor 255 = 255
Es decir, donde una imagen coincida (dentro y fuera de la figura) con la otra, dará un píxel negro en la imagen resultado, y blanco cuando sean distintas. Contando el número de blancos sabremos cuanto difiere (o contando los blancos sabremos cuanto es igual). Usa la tolerancia con diferentes valores, para ver qué resultados te da.

Esta solución, es la adecuada cuando no hay que ser muy extrictos y las formas son más o menos claras, del mismo tamaño, pequeñas y la velocidad es muy importante.

P.d.: Aquí no se ha considerado si la imagen están espejadas (que veo que tienes dos iguales pero espejadas entre sí). cuando cabe la posibilidad de que estén espejadas, hay que hacer 4 comparaciones (4 bucles idénticos), el primero tal cual (como si las dos estuvieren corrctas, en otra donde la segunda imagen esté invertida horizontalemente, la 3ª donde se considere invertida a la segunda figura verticalemtne y la 4º donde se consdiere invertida a la segunda figura tanto vertical como horizontalmente.
Con los reconocimientos en el mensaje anterior es fácil detectar si están invertidas, porque las  áreas, perímetros vendrán a coincidir y medidas y ángulos  conncidirán en orden inverso...

[footer]

Hola NEBIRE gracias por tus respuesta y tiempo, estuve viendo tu pseudocodigo y me parece bastante buena idea, si no me equivoco lo que me dices que haga es que formar poligonos donde cada lado del poligono estara definido por puntos salientes de la figura que se encuentren al lado, luego comparar los  poligonos y ver sus similitudes por medio de sus angulos, la verdad que tiene mucho sentido. Asi que me puse a ver si podia al menor comenzar con eso. Asi que al codigo que subi antes le agregue la clase "comparador" donde escribi algunos metodos entre ellos estan: un metodo que encuentra los primeros cuatro puntos saliente (superior, inferior, derecho, izquierdo), luego con esos puntos salientes se calcula en punto central de cada imagen, ademas tambien pinta las imagenes por dentro, las imagenes devueltas por java son estas:

(no se alcanzan a ver, pero si hacen zoom con el navegador podran notar 5 puntos, uno central y los demas son los primeros 4 puntos salientes)




El siguiente paso si no me equivoco es hacer una linea entre 2 puntos salientes que esten al lado y verificar si toca a la figura, en ese caso comprobara un nuevo punto saliente entre medio de esos 2 puntos y hara una linea nueva. Apenas puedo intentare eso y estare actualizando el post. Aqui dejo el codigo. Suerte.

String link = "https://drive.google.com/open?id=0B1i-JNEuRD1zWVFvVG4xcFpCN2s";

[Serapis]

Exacto...

Una vez con los 4 puntos y uno considerado como el 'centro geométrico', desde los 4 hay que buscar los puntos salientes que tocando a la figura logran encerrar por completo la figura.

La parte que puede parecer un poco confusa (espero que no), es la de considerar el ángulo convexo o cóncavo, ya que eso depende del cuadrante (en realidad ángulo de ambos puntos alrededor del eje).

Por último, aunque no se ha mencionado explicítamente si no que se ha dejado un poco al aire, es que consideramos similitud... porque puede tener diferentes interpretaciones según lo que busquemos:
Similitud en la forma, similitud en tamaño (área), etc...
Se ha asumido de forma genérica, pero los detalles dados permiten avanzar en la dirección que uno pretenda.

p.d.: No he mirado tu código aún... cuando avances algo más le hecho un vistazo.
Ten en cuenta que es fácil perderse, o desalientarse porque hay muchos pequeños detalles que mimar y ponder en orden. Pero bueno, cada función en pseudocódidigo está en grandes pasos (y escrito al vuelo), se puede pulir y detallar más llegado el caso.

[footer]

como elimino este mensaje? lo publique solo sin querer.

[footer]

Hola todos, hago una actualizacion de esto, he hecho un "parentesis" por que me puse a ver como podria detectar un punto saliente que este entre 2 puntos salientes, siguiendo con la idea que me dio NEBIRE he trazado lineas entre los 2 puntos y ¿como iba a hacer para que el programa detecte el punto saliente del medio?.
Se me ocurrieron 2 formas. La primer manera:
En cualquiera de la dos ideas se tiene un recorrido/ruta que no es mas que los pixeles de una linea, ese recorrido sera lo que indique la direccion del "scanner" que tampoco es mas que una linea donde entre sus puntos en algun momento estara el pixel saliente del medio, en la idea uno el recorrido se marca con una linea amarilla y el escaner con una linea roja, los puntos salientes con azul y con verde el centroide que es el centro de la figura por ultimo de color negro dibujo la linea que une un punto con el otro:




Donde la linea amarilla es el recorrido del scanner, que es la linea roja y este scanner se va moviendo hacia uno de los puntos de la linea.
Para hacer esto superficialmente lo que se hace es:

Calcular angulo de la linea que va desde el punto de salida hasta el punto de llegada, en este caso (foto) el punto de salida es el de abajo, entonces metemos ese punto en un eje cartesiano y calculamos el angulo con el otro punto, esto se hace con trigonometria
Para eso hay que detectar el cuadrante del vector y sumar los angulos del cuadrante anterior: En la imagen al angulo de color celeste se le suman 0 grados, al de marron se le suman 90 grados,  y asi con los demas angulos...


Una vez con ese angulo se hace la linea que une esos dos puntos tambien con trigonometria. Despues de esto tenemos una line hecho desde un punto hasta otro punto. (los dos mas salientes),

Lo siguiente es calcular el angulo entre el punto centroide y el punto de salida de la linea, esto se hace de la misma forma:



Con este angulo se puede trazar la lines de recorrido:  (linea amarilla) de ahi sale la linea amarilla de la imagen de arriba.



Una vez hecho eso solamente queda comprobar, para comprobar hay que meter en un array cada punto de la linea amarilla (solo la linea amarilla), e ir recorriendo cada punto uno a uno desde el ultimo hasta el primero (se recorre al revez por que se quiere detectar desde afuera hacia adentro) y por cada punto de esos hara una nueva linea, la linea scanner, para hacer la linea usara el angulo de la linea negra:





Forma 2:

Es lo mismo que antes pero cambia en que en ves de calcular la linea de recorrido con un angulo igual al angulo entre centroide y punto de salida lo que hace es calcularla a noventa grados del angulo de la linea, se obtendria esto:



para obtener la linea que es perpendicular se puede sumar o restar 90 grados al angulo de la linea el problema es que a veces habra que sumar y otras veces habra que restar
entonces para saber eso tengo que tener en cuenta que para trazar una una ruta de trayecto/recorrido para el scanner tengo que alejarme del punto centroide y para poder alejarme se tiene primero que: calcular angulo entre punto saliente y centroide, luego sumar 90 grados al angulo (que ya existe calculado antes, arriba) de la linea que se habia llamado "alpha" y obtengo una de las 2 rectas de noventa grados para tener la otra tengo que restar 90 grados al mismo angulo que antes le habia sumado, ¿cual recta elijo?. Para responder esa pregunta hace falta saber la diferencia entre los 3 angulos que se tienen que son marron,violeta,verde:



negro = es el angulo de la linea
marron = es el angulo de la linea + 90 grados.
violeta = es el angulo de la linea -90 grados.
verde = es el angulo entre el punto saliente y el centroide

y ahora hacemos las diferencias:

marron - verde = diferencia entre el angulos+90 y el angulo con centroide
violeta - verde = diferencia entre el angulo-90 y el angulo con centroide

de los dos angulos que me importan (angulo+90 y angulo-90) voy a tomar el que me de mayor diferencia con el angulo centroide por que eso quiere decir que en ese angulo me voy alejar del punto centroide la diferencia seria esta:



la diferencia es bastante en este caso, lo que sigue es igual, se traza la linea amarilla a 90 grados, se recorre esa linea desde fuera hacia dentro y en cada pixel de la linea amarilla trazara nuevas lineas (linea roja, scanner) con el angulo de la linea negra.

Aqui dejo un codigo que ilustra esto:
El codigo es una animacion que muestra los dos tipos de deteccion, si se fijan en la clase Principal hay varias opciones de configuracion, si ponen el valor de la propiedad "tipoDeDeteccion" = 1 veran la forma 1 que explique antes y si ponen "tipoDeDeteccion" = 2 veran la segunda forma, ademas hay una imagen de salida que se guarda en "D:/salidaDiagonales.png" por si quieren ver, la linea de recorrido del scanner se traza en verde, no en amarillo, por ultimo pueden cambiar el punto por defecto por uno que ustedes quieran, y esto me lleva a mencionar algunos errores que pueden pasar...

si ponen tipo de deteccion = 1 y ponen 2 puntos que esten a 45 grados ej: (10,10);(20,20) veran como la deteccion no hace su trabajo como debe ser.
Si ponen tipo de deteccion = 2 hay angulos entre puntos que hara que el programa no sepa que elegir, por ejemplo el punto (10,10);(10,10) al poner ese punto en el momento de elegir el recorrido del scanner hara la diferencia y ambas diferencias son iguales entonces el programa no sabe que elegir...
Espero no haberme olvidado de algo, ya estare viendo si puedo icluir esto en la deteccion de las imagenes de arriba. Saludos.

Subido a googleDrive
Link: https://drive.google.com/open?id=0B1i-JNEuRD1zOEdoX0Z0NHFpNlU

[Serapis]

Bien, vas avanzando... pero te daré algunas ideas...

1 - Es preferible no considerar el punto central como el punto de cruce entre las líneas que unen los puntos verticales y horizontales, sino, como muestor en el siguiente dibujo, el punto medio entre la distancia que separa los puntos horizontales, e ídem de los puntos verticales, de modo, que con ese centro es equidistante a ambos lados, pudiéndose trazar (si fuera el caso), un círculo o elipse que pase por ellos.
No es del todo obligatorio, pero reduce la cantidad de píxeles a visitar...
Se expone en la siguiente imagen (he desplazado los puntos para que no vengan a coincidir enfrente uno de otro y quede más claro la idea...


2 - Con los 4 puntos, se elige uno como inicio y una dirección (pongamos el de arriba y girando en sentido de las agujas del reloj, ahora nos centramso solo ne ese cuadrante. (son 4 bucles uno de trás de otro, que corresponden a cada cuadrante). Se lanza una línea entre los dos que limitan ese cuadrante... ¿por qué?. ahora vemos con una imagen porqué.
En la imagen se ven 6 variacones de la misma figura. Mira la última, si no corta la figura, implica que esa es la línea que encierra la figura, luego esa sería la solución para ese cuadrante.
Pero miremos a la figura 1, si recorremos los píxeles de la línea, podemos contar cuantas veces corta la figura (recordemos que la figura la tenemos en negro y el exterior en blanco, yo para que se vean con claridad los detalles, he conservado solo el contorno. en la imagen 1, la línea de contorno es interceptada 4 veces, una siempre sale otra que entra, luego podemos deducir que como mínimo hay 2 'picos' salientes. Bien si ahora te fijas en a imagen marcada como 3, verás que el controno se intercepta 10 veces, es decir hay al menos 5 'picos' salientes, se puedne contar bien, he puesto un trazado amarillo en cada saliente.
Pueden ser más pícos que el número dividido entre 2 (la marcada como 4 tiene el propósito de demostrar eso), pero nunca menos.
La 1 la 2, son la misma, en la 1 simplemente he trazado las 4 líneas que unen los 4 puntos, como idea general...
La imagen 5 redunda en lo mismo, ver que aunque el contorno sea retorcido siempre una intercepción entra en la figura y la siguiente sale.
Esos puntos de intercepción del contorno son útiles... nos sirven para saber cuantos picos cabe encontrar como mínimo.



En la siguiente imagen, vamos a analizar más en profundidad la importancia de los puntos de interceción de  contornos. Si miras con detenimiento la siguiente imagen, podrás ver que cada vez que la línea azul, corta el contorno, las veces impares, entra dentro de la figura y las veces pares sale de la figura , esto sucede siempre, da igual lo enrevesado que sea la imagen. De hecho esta característica es la base de rellenar figuras encerradas (o lo opuesto rellenar el exterior) con un color o un patrón, solo recorriendo línea a línea...


Ahora vamos al siguiente paso importante... se muestra en las siguientes imágenes...
Hemos empezado a detectar los picos, para ello se generan dos bucles, uno de recorrido vertical y otro horizontal ... por supuesto son dos bucles anidados, uno de recorrer líneas y el interno para recorrer los píxeles de cada línea.
En el horizontal vamos detectando el borde saliente, cada vez que una línea encuentre lo más a la derecha un contorno, y, en la siguientes líneas (el bucle interno anidado) empezamos (como mínimo) en esa posición, no volvemos cada vez al origen (centro de cordenadas). Esto se muestra en el trazo azul. Si recorriéramos todo, empezaríamos el bucle horizontal siempre desde la línea roja, sin embargo eso solo sucede en la primera línea. Cuando llega al pico 1(ver la marca rosada), ya empieza las siguientes líneas en ese punto. Esto acelera la búsqueda...


Se puede ver también que he trazado unas líneas rojas.... Una vez detectados los puntos salientes, desde el punto final del cuadrante (o desde el punto origen), se trazan líneas a cada uno de esos puntos recién obtenidos.
De entre todas esas líneas, aquella que arroja el ángulo más grande respecto de la línea que trazamos entre ambos puntos originales, es el punto más saliente.
De nuevo desde ese punto, trazamos líneas (la primera al punto de origen del cuadrante) y al resto de puntos obtenidos (más arriba en el eje 'Y', que la posición 'y' que ocupa éste punto), y de nuevo aquella línea que marca el ángulo mayor con respecto a la línea trazada hacia el punto del cuadrante, determina el punto más saliente....
Siguiendo el procedimiento, se obtiene todos esos puntos salientes que encierran la figura en ese cuadrante.
Es trivial, dibujar las líneas de los siguientes (saturaría la vista tantas líneas), se observa fácilmente que desde el punto final del cuadrante, marcado como 0, la línea irá al 1, luego al 3, luego al 5 y finalmente al de origen marcado como 6.


En esta otra imagen, más de  lo mismo. Tiene trabajo, pero es un modo seguro. Zonas redondeadas, pueden dar, líneas muy cortas y próximas entre sí, que pueden 'falsear' luego los ángulos. Pueden 'resumirse'...
Un detalle (en la esquina superior izquierda de la imagen) es ver como en el bucle de recorrido horizontal, se empieza siempre desde la línea del eje, (en este cuadrante desde ahí hacia la derecha).
En azul claro, el trazado necesario para detectar los picos con sus puntos. Hay que notar que el procedimiento descrito solo se 'visitan' desde los bucles (el bucle interno) los píxeles de la zona marcado en ese color cyan, no todos los del cuadrante, ya que el iniio del bucle interno, va fijandose con un valor mayor cada vez que en una línea se detecta uno más saliente.


El resto de cuadrantes es aplicar el mismo sistema, con los cambios que proceden o recurrir a senos y cosenos...

Si te queda alguna duda o las explicaciones no te parecen suficientemente claras, avisa... se puede hacer un pseudocodigo...

Cuando avances más te comento algo sobre los atractores gravitatorios... que resultan muy útiles para detectar similitud de formas con flexibilidad en contornos y en la propia forma.

[footer]

hola NEBIRE que tal, comento esto para preguntarte sobre la parte de las lineas azules, si mal no entendi la idea seria esta:
1) calcular el centro: diviendo la distancia horizontal /2 idem para la distancia vertical

2)Luego detectar la cantidad de picos minimos, esto se haria trazando una linea y detectar cuantas veces la linea corta con la imagen, siendo impar -> entrada a img, par -> salida a la img cada vez que entre o salga de la figura sumara un contador++, luego divido /2 y obtengo los posibles picos minimos a detectar.

3) y aqui viene mi principal duda, si no entendi mal lo que debo hacer es definir el cuadrante, cada cuadrante estara limitado por los 4 puntos que me daran 4 cuadrantes, elijo el primer cuadrante en sentido a las agujas del reloj, si la linea toca la figura en ese cuadrante entonces yo debo tener la cantidad minima de picos y debo buscarlos en este cuadrante para luego pasar al siguiente.
Para buscar esos picos de hacer:
Con un "scanner"  horizontal, que valla aumentando filas de a 1 y en cada fila evaluara los pixeles uno por uno de izquierda a derecha, las filas hiran de arriba hacia abajo y haria un "scanner" vertical que hira sumando columnas de a 1 y en cada columna evaluara cada pixel de abajo hacia arriba, las columnas hiran de derecha a izquierda (teniendo en cuenta la img 1)
Cada pico tendra dos puntos salientes a detectar, el superior (que lo detectara el scanner horizontal, y el punto saliente que esta mas a la derecha, que lo detectara el scanner vertical).
Y la duda es: ¿como los detecto? lei lo que escribiste pero no pude encontrar por mas de que quise asimilarlo la forma de detectar los 2 puntos salientes de cada pico (superior y el de la derecha). Esta parte me genera dudas

"cada vez que una línea encuentre lo más a la derecha un contorno, en la siguientes líneas (el bucle interno anidado) empezamos en esa posición,"

entiendo la idea pero no entiendo el funcionamiento de los bucles, el externo mueve en lineas y el interno mueve en pixeles de cada linea y cuando se detecta un borde saliente superior (no se como lo detectaria) el bucle interno de pixeles va a arrancar en la siguiente linea en la posicion que detecto en la anterior no arrancara desde el comienzo.
idem para scanner vertical.

4) Una vez detectado los puntos de cada pico se trazan linea desde el punto final (o el punto de origen) hacia cada punto detectado y la linea que tenga mayor angulo sera el punto mas saliente.

Espero no molestar mucho... Saludos.

PD: alguien no tendra el link de un post que hable sobre como hacer lineas en java? no me refiero al elemento graphics sino a calcular los puntos de la linea que pasa por dos puntos, lo logre hacer con trigonometria, y con funciones lineales, pero al comparar mis lineas con las del elemento graphics no son iguales tienes unas pequeñas diferencias, estare subiendo el codigo de las lineas mas tarde.

[Serapis]

Te contesto a la noche (más bien de madrugada). Esta mañana te estaba contestando, pero creí necesario apoyarlo con imágenes y se me fue el tiempo sin terminarlo antes de irme al trabajo...