Comparar Imagenes y encontrar similitudes.

[Serapis]

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

Si, pero OJO. Esto para pasos posteriores.... para ahora mismo que vamos a detectar los picos, los cuadrantes quedan divididos, por las líneas que se cruzan delimitando el cuadrante para ese par de puntos.
Este cuadrante (su tamaño) varía para cada par, pero tranquilo, no examinamos todo (el área del cuadrante)...

Al crear la línea entre ambos puntos, al mismo tiempo se guardan en un array, porque esos puntos son el inicio del bucle 'x' para cada ciclo del bucle 'y' (para recorrer las filas y columnas).
El algoritmo de Bresenham, te vale muy bien, para trazar la línea, además opera con valores enteros, no con decimales... esos puntos deben guardarse, el punto x más a la derecha por cada 'y'. Es decir el tamaño del array es la altura (si hacmeos el recorrido de forma horizontal, es más cómodo así que hacerlo de forma vertical, elige el que más te convenga).

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.

Exacto, te da los picos mínimos, podría haber más, pero nunca menos.

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, pero cada cuadrante queda definido por las líneas que cruzan sus líneas imaginarias (ordenada y abscisa), es decir las líneas trazadas de cada 2 puntos, ofrece un cuadrante (los 4 cuadrantes posiblemente se cortan entre ellos, no nos importa).
Te adjunto una imagen de como se particiona...

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:

Si, y si no toca la figura, esa línea basta para rodear la figura en ese cuadrante.
Pero antes de buscar en el siguiente cuadrante, resolvemos todo el asunto de ESTE cuadrante.

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.

Te lo explico una vez más (pero debes tener en cuenta que lo dicho se aplica a este cuadrante, a los siguientes hay que 'desplazar' la idea... es decir es reflexivo, aplicar los cambios necesarios).

Veamos, tenemos dos puntos (miremos la figura 1 de esta nueva imagen que suba, la pongo un poco más arriba). Esos dos puntos trazando sus paralelas, se cortan en un punto... que definen el cuadrante 'NorEste'. Explico siempre sobre este cuadrante...

Un poco  de pseudocódigo que ayude a plantear como resolverlo...
Consta de dos bucles anidados:

p.d: He retirado el pseudocódigo, he puesto más abajo otro equivalente más optimizado... aunque era un detalle que esperaba que vieras, lo cierto es que supone bastante embrollo, así que... vas a trabajar igualmente bastante...

En realidad cada encuentro, no es pico, a menudo es solo una promesa.... si es una leve curva habrá muchos 'picos seguidos'
Mirando esta imagen te puedes hacer una idea clara, de lo que va haciendo el pseudocódigo (el recorrido del bucle interno).
Cada puntito marcado verde (el anterior que está a su izquierda), es el que se añade a "Picos".



En esta imagen (tras este párrafo) la línea azul, sería representaría los valores de dx, el recorrido del bucle horizontal que va tomando al iniciar cada línea (como está a mano alzada, no salen rectas muy rectas, pero se ve claramente el recorrido, y como cuando hay un saliente avanza del saliente y cuando la diagonal supera al saliente, tira de la diagonal... esas líneas eran:

Código [Seleccionar] Expandir

Si (dX < LineaDiagonal(Y) ) luego dX = LineaDiagonal(Y)
Nota que este bucle horizontal empieza en el puntoA (el de arriba y avanza hacia la derecha, buscando cambios entre negro y blanco, hasta final de línea, luego avanza a la siguiente línea empezando en el punto más adelantado hallado en la línea previa, o bien tomando como inicio el de la diagonal.



Si el bucle se recorre verticalmente desde el puntoB hacia el puntoA y de izquerda a derecha... es resultado será casi idéntico y no arroja interés apreciable (salvo que con la reflexibidad lógica por los otros cuadrantes, se puedan acometer en el mismo código dos cuadrantes diferentes). En fin elige recorrerlo en horizontal o en vertical, según te acomode mejor al código, pero no hay apenas diferencias en el resultado, más abajo te pongo una imagen con el recorrido hecho de ambas maneras y verás que no hay diferencia. Las puede haber si la figura entra y sale sobre sí misma, pero lo que no falla esel resultado final de hallar los picos.)

Con la declaración de los bucles, el código y las imágenes debería quedarte claro, los pasos...

Quizás haría falta una imagen para ver como procede la criba... luego me edito, antes termino el mensaje...
Ok, Aquí la imagen que va buscando los picos salientes, esta sería la función que 'criba' los picos, y que opera justo con los puntos obtenidos...
Nota como cuando un pico es seleccionado (por su mayor ángulo), son descartados los que están más 'arriba' que él (o abajo según se mire), en la lista.
Si dos o más puntos tuvieran casualmente el mismo ángulo, se toma por bueno el que quede mas lejos (sino éste luego apuntaría al siguiente y seríans líneas rectas pasando por varios puntos que se resumen en los puntos de los extremos).
En cuatro pasos, pues solo encontró 3 puntos salientes, la imagen final traza las líneas para ver el resultado con claridad.

Código [Seleccionar] Expandir

Array Angulos(0 a Picos.count-1) //el tamaño es el de picos
entero n = Picos.Count-1 //K-1 al inicio, pero como podemos saltarnos algunos, lo dejamos en una variable.


Salientes.Add(Picos.count-1)) //el PuntoB
Bucle para k desde Picos.Count-1 a 2 retrocediendo
   // bucle para calcular el ángulo desde el punto actual al resto anteriores.
   Bucle para j desde n hasta 1 retrocediendo
       Angulo = CalcularAngulo(Picos(0), Picos(k), Picos(j))
       Angulos (j)= Angulo  //ambas lineas pueden ser solo una, se deja en dos para que quede claro que
          // la función devuelve el ángulo que forman los 3 puntos en ese orden (con Picos(k) en medio).
   Fin bucle
   //Tomar el ángulo mayor de todos.
   Bucle para j desde n-1 hasta 1 retrocediendo
       Si Angulos(j) > Angulos(n) luego n = j
   Fin Bucle
   Salientes.Add(punto picos(n))  //
Fin bucle
Salientes.Add(Picos(0)) // El PuntoA

//Ahora puede trazarse una línea desde un punto de 'salientes' al siguiente y veremos si el trazado es correcto.
Y con esto hemos resuelto este cuadrante.

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.

Si, pero el ángulo formado entre el punto final y la línea que va de PuntoA al PuntoB (final), luego se repite desde el punto recién hallado con ángulo más saliente, el angulo será partiendo desde este al PuntoA (y a los respectivos puntos más 'hacia donde avanzamos' que quedan en la dirección opuesta de donde partimos. en este cuadrante empezamos a recorrer los picos desde el PuntoB (horariamente la aguja de las '3') y en dirección antihoraria (hasta la aguja que marca las '12'). Realmente no importa el orden en que se recorran. Si quieres reutilizar la lista previa (en vez de asignar a una nueva los válidos), empieza desde 0 hacia arriba, y eliminas los que no se quedan..
Pongo otra imagen mejor, para que se vea esto... Ya está es la última imagen subida puesto más arriba.

Nota que en realidad se toma como pico (promesa) el píxel hallado blanco tras un previo hallado negro. si esto ocurre más de una vez en la misma línea (con el recorrido horizontal que hacemos), el que quede al final (el más a la derecha hallado), es el que se añade, por eso se añade al terminar el bucle... en la misma línea se va actualizando...
Esto implica que una curva, va a ofrecer muchos 'picos promesa'.... podríamos sacar una línea tangente a la curva y tomar el punto de tangencia como válido, pero no conviene que te compliques tanto, una pequeña inexactitud, no merma el resultado ni se va a notar demasiado retraso por añadir 20 puntos más que los 3 o 4 previstos inicialmente). El tiempo dependerá del tamaño de la imagen, básicamente...

Te pongo una imagen final, que muestra algunas cosas que te decía...
1 - Que no importa si eliges un recorrido horizontal a derecgha y bajando, que si eliges un recorrido vertical subiendo y a izquierda
(linea azul es bucle 'Y' y luego bucle 'X' a derecha , línea verde es bucle 'X' y dentro bucle 'Y' ascendiendo).
2 - En cyan he encerrado una zona con curva, pero luego en un dibujo más pequeño, he realizado otro apuntado por una letra 'P' en amarillo.
3 - La forma en que avanza el bucle interno. Si toca la diganonal, el bucle x comienza en ese valor, si hubo un pico antes más adelante que la diagonal, el bucle X (es decir dX) comienza ahí....



-----------
Para finalizar... podemos optimizar el bucle interno, verás:
En realidad si recorriéramos el bucle interno de derech a izquierda, nos pararíamos al encontrar el primer pixel negro, ese punto sería el que se añade y saltamos al final de la siguiente línea y retrocediendo de derecha a izquierda. A lo sumo hasta el pixel hallado en la línea anterior (dX) o el que marque la diagonal, esto no cambia. No requiere comprobar posteriores apariciones, todavez que el que está más a la derecha es el que nos interesa.
El código resultante requerirá menos comprobaciones...




Modifico el pseudocódigo, para reflejarlo, ahora verás que es bastante sencillo y despejado.

Código [Seleccionar] Expandir


Array LineaDiagonal() <----- previamente calculada con el algoritmo de Bresenham (por ejemplo).
Entero dX= 0 // al comienzo será: PuntoSuperior.X, pero dejemos qu actúe el bucle.

Picos.Add(punto (PuntoA.Y, PuntoA.X)) //añadimos el punto inicial al comienzo (ojo, no añadirlo dos veces, si es así, empezar el bucle Y uno más adelante

// El bucle y, recorre en este cuadrante las líneas verticalmente hacia abajo
Bucle para Y desde puntoSuperior.Y hasta Punto.Derecha.Y    
   Si (dX < LineaDiagonal(Y) ) luego // LineaDiagonal(Y) tiene el valor de X en esa línea.
       dX = LineaDiagonal(Y)
   Fin si

   // El bucle x es quien hace todo el trabajo de detección
   Bucle para X desde PuntoDerecha.X hasta dX retrocediendo        
       Si (pixel(Y, X) = ColorNegro) luego //Si hay un pixel negro, es el más saliente en esta línea  
               // La figura era toda negra y el resto blanco, no?, o era al revés?                          
               dX = X      //en la siguiente línea el bucle terminará en dx (como máximo), y en lo que resta de alto, nunca menos de este valor..  
               Picos.Add(Punto (Y, dX))  // se encontró un pico se añade
               salir del bucle //no hace falta seguir mirando en esta línea.            
       Fin si
   Fin Bucle
Fin bucle
Picos.Add(Punto (PuntoB.Y,PuntoB.X)) //añadimos el punto final (ojo, no añadirlo dos veces, si es así, llegar a uno menos en el bucle Y)


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.

Ya te comentaba más arriba (al comienzo), el algoritmo de Bresenham, que además es muy fácil de entender y opera con enteros. Además también difiere segun el cuadrante (la dirección), lo que viene en sincronía con lo que vamos haciendo... podemos implementar 4 diferentes más simplificados uno para cada cuadrante.


Esta detección (de áreas) es costosa de codificar, pero es muy precisa. Si se requiere menos precisión, puedes recurrir a otros sencillos métodos...
Si te parece bien, en otro momento te comento por encima otro método más sencillo, donde no importa tanto la exactitud de las formas, se considera similar, es adecuado por ejemplo para detectar caras, de lo que no es, coches de lo que no es, etc... es decir no se requiere una exactitud en la forma, si no una clara 'compatibilidad' de la forma. Dos rostros humanos, son similares (aunque dos personas sean muy distintas), comparados con por ejemplo una lechuga, un avión, una nube, una montaña, etc...


-------------------
p.d2.: He puesto por ahí alguna incongruencia (posibemente algo esté inexacto o tal aunque procuro asegurarme alguno se escapa, si tienes dudas por ello avisa) ... en alguna parte a los puntos de los cuadrantes los he llamado PuntoA y PuntoB y en otra PuntoSuperior y PuntoDerecha... es cosa de escribir parte ayer de madrugada y parte hoy... en vez de todo del tirón, pero sin más importancia.

[footer]

Hola NEBIRE traigo aqui algunas dudas y un poco de codigo para ver si voy bien encaminado, cualquier punto de vista y/o observaciones constructivas seran tenidas en cuentas.

Con respecto al centro de cada cuadrante ya me quedo bien claro como debe ser.
Al crear las lineas del punto central tomare la distancia x que hay entre ambos puntos salientes, eso me indicara que distancia recorrera como maximo el bucle interno del scanner horizontal, esto se cumple solo en la primera fila ya que la linea esta inclinada.


Con respecto al "scanner horizontal" lo hare desde fuera hacia dentro. Cuando encuentre un pixel negro entonces la siguiente linea llegara como maximo hasta esa posicion y agregara el pixel a un array.

teniendo en cuenta la siguiente imagen:



Esto seria el scanner horizontal en el cuadrante cuatro (anti reloj)

Se puede decir que el "scanner" horizontal no me detectara el punto mas saliente de cada pico, sino que me detectara un conjunto de posibles puntos salientes, en ese conjunto de puntos esta incluido el punto saliente que estoy buscando
Por ejemplo en la imagen cada cuadrado amarillo es un punto detectado por el scanner entonces cada punto amarillo sera agregado al arraylist "posiblesPuntosSalientes" luego queda ver cual de todos esos puntos son los que busco (en la imagen son solo 2 puntos los que busco ya que son dos picos pero en el array de posibles puntos tendre: 14 puntos, para saber cual es el que busco entonces calculo el angulo en esos catorce puntos tomando el ultimo punto del cuadrante como punto central y el posible punto saliente que mas angulo me dé será el más saliente de todos, eso me lleva a decir tambien que los angulos que luego usare para comparar no se calcularan con cada punto saliente sino que se calculara con cada posible punto saliente, es correcto esto?...


Con respecto a calcular el angulo he visto en el pseudocodigo que para calcular el angulo envias tres parametros, Picos(0), Picos(k), Picos(j), por que no se envian solo dos parametros? punto central y punto del que se quiere saber el angulo?

" Si dos o más puntos tuvieran casualmente el mismo ángulo, se toma por bueno el que quede mas lejos "
Supongo que sera mas lejos del punto que se toma como central para calcular los angulos en este caso el punto B.

Estas serian las primeras dudas, ya que por esto voy a arrancar:

Sobre el pseodocodigo:
si, la figura es toda negra y el fondo es blanco.
si aplico este pseudocodigo pasara lo de la imagen de arriba, cada vez que detecte pixel negro se agregara al array, pero esto no garantiza que el pixel que se agrega sea el punto saliente sino que sera un posible punto saliente y entre esas posibilidades esta el que se busca (el mas saliente de ese pico) que se detectara con su angulo mayor al de los demas (para ese pico).



Sobre el algoritmo de Bresenham, lo busque y lo estuve viendo, algunas cosas las entiendo otras no... igual para mi suerte puede implementarlo y usarlo para hacer lineas rectas, eso queda pendiente saber como funciona al 100% ese algoritmo, una de las dudas era:
p = 2*dy - dx; Eso se puede leer como: 2 veces la distancia en el eje 'y' menos 1 vez la distancia en el eje 'x' pero no se que es eso visto del punto de vista de la matematica, que representa, que nombre tiene, que significa... etc.

He escrito algo de codigo, el codigo resuelve el primer cuadrante de cada imagen, los cuadrantes se cuentan en sentido contrario a las agujas del reloj, lo hice asi por que asi habia comenzado a hacerlo con la idea anterior (la del scanner con lineas diagonales) y para no perder tiempo modificando algo que ya estaba hecho lo hice de esta manera

El codigo tiene algunos comentarios, se hace partiendo desde la deteccion de poligono ya que lo anterior es para convertir la img en escala de grises y sacar los bordes, pintar la img etc. Tambien se incluye la imagen (que trae 5 imagenes dentro 5 en 1) esta img se llama "a.png". Al ejecutar el programa guarda en el disco "D:/" varias imagenes, que son los pasos del programa, las que tienen mas importancia son las imagenes llamadas "PPS0.png", "PPS1.png"... en esas imagenes se ven los resultados del scanner horizontal donde cada posible punto saliente es marcado en verde, los puntos rojos son los puntos mas salientes de cada lado. Luego las imagenes que se llaman "TrazarLineaX.png"... son las imagenes que muestran los puntos mas salientes y los posibles puntos salientes pero ademas de eso tambien muestra los puntos salientes que resuelven ese cuadrante (puntos de color azul), en la imagen 4 hay un error que es por la forma en que se calculan los angulos entre dos puntos, toma una recta en el eje de absisas positivo como perteneciente al cuadrante 4 entonces eso hace que tenga angulo de 360 cuando tiene 0.

subido a google drive.
link del codigo = https://drive.google.com/open?id=0B1i-JNEuRD1zU3JPOWlVbzhOLUU

PD: en entos dias subire una imagen que refleje una duda que tengo sobre esta forma de detectar los puntos salientes.

Saludos.

[Serapis]

Oh, a la noche te releo con detenimiento y contesto tus dudas, también revisaré el código, ya lo he descargado.

[Serapis]

Te voy respondiendo con cita,s al ser un mensaje algo largo y por ello difícil de retener en memoria cada cuestión planteada...

Con respecto al centro de cada cuadrante ya me quedo bien claro como debe ser.
Al crear las lineas del punto central tomare la distancia x que hay entre ambos puntos salientes, eso me indicara que distancia recorrera como maximo el bucle interno del scanner horizontal, esto se cumple solo en la primera fila ya que la linea esta inclinada.

Exacto. de ahí la importancia de tener en un array los valores de x (más a la derecha), para dicha diagonal (la línea entre tales 2 puntos).
Fíjate además que ese array determina al mismo tiempo el máximo número de pícos salientes hallados. Esto es como máximo 1 por cada píxel en x. en definitiva... ya sabes el número menor de picos al contar cuantas veces se corta la figura con la línea y como máximo, la cantidad del ancho de x (nunca o casi nunca será este valor,  pero nos ale saber que es el valor máximo de picos).  

Con respecto al "scanner horizontal" lo hare desde fuera hacia dentro. Cuando encuentre un pixel negro entonces la siguiente linea llegara como maximo hasta esa posicion y agregará el pixel a un array.

Como máximo hasta esa posición... o la línea diagonal si aparece antes de esa posición. Pero en este último caso, no se añade píxel solo se actualiza el valor límite (yo lo llamé 'dX').

Mira la última imagen que puse,. date cuenta como casi lllegando a la parte baja, se encuentra la diagonal, y todavía después encuentra algún pico...

Se puede decir que el "scanner" horizontal no me detectara el punto mas saliente de cada pico, sino que me detectara un conjunto de posibles puntos salientes, en ese conjunto de puntos esta incluido el punto saliente que estoy buscando

Si. Y luego con la siguient eparte de calcular el ángulo más saliente, identifica finalmente los correctos dejando fuera al resto de 'promesas'.
Aún así, se puede optimizar bastante... date cuenta que si en la línea se detecta un pico en x en 345, y 3 líneas más abajo en 543, la diferencia horizontal entre solo 3 líneas hace descartar la previa.... pero primero logra que funciones correctamente y luego ya te entretienes en optimizarlo. Si te hubier apuesto un pseudocódigo muy optimizado, a buen seguro sería muy farrafgoso de entender el por qué de cada cosa... tal como te lo dejé es sencillo de entender y se presta a optimizaciones aún...

teniendo en cuenta la siguiente imagen:

Esto seria el scanner horizontal en el cuadrante cuatro (anti reloj)

Por ejemplo en la imagen cada cuadrado amarillo es un punto detectado por el scanner entonces cada punto amarillo sera agregado al arraylist "posiblesPuntosSalientes"

No. Cada punto amarillo que tienes no. Solo si está más a la derecha que el punto anteriormente añadido. Es decir si tienes un punto en x=234 en Y=7, lo añades, pero no hay que añadir el x=234 para Y=8, Y=9, y=10...

De hecho al recorrerlo verticalmente (este cuadrante desde arriba hacia abajo) casi aseguramos que el bueno cuando varios en vertical son 'igual de salientes' el más prometedor será el que esté más arriba. Y digo casi para no entrar en polémica...
En tu dibujo, suponiendo que cada cuadradito fuera:
---- un píxel solo habría unos 5-6 puntos (contando el primero y el último).
---- una retícula de 5x5 píxels, seguramente haya tantos como 18 (sobre unos 30 que esería el ancho).

Se añaden siempre al comienzo, antes del bucle el PuntoA, y al final tras el bucle el PuntoB. De tal modo que si finalmente todo el tramo entre ellos estuyviera interno a la línea diagonal, solo esos 2 puntos definirían el perímetro exterior en ese cuadrante.

luego queda ver cual de todos esos puntos son los que busco (en la imagen son solo 2 puntos los que busco ya que son dos picos pero en el array de posibles puntos tendre: 14 puntos, para saber cual es el que busco entonces calculo el angulo en esos catorce puntos tomando el ultimo punto del cuadrante como punto central y el posible punto saliente que mas angulo me dé será el más saliente de todos, eso me lleva a decir tambien que los angulos que luego usare para comparar no se calcularan con cada punto saliente sino que se calculara con cada posible punto saliente, es correcto esto?...

Hago una imagen con ángulos y puntos más acentuados que permitan ver mejor los detalle y añado más comentarios que aclaren la situación. Ya están (varias, ahora las explico).

En la primera imagen, en el apartado 1. Cada 'e' (entra) y 's' (sale), cuenta los picos mínimos... 7 en total.
La línea amarilla, es la solución, 4 puntos intermedios + los 2 externos = 6 puntos delimitan ese cuadrante.
La línea cyan, deine el valor que en cada cilo tomará 'dX' al comienzo del bucle. Esta línea no son todos los puntos salientes. Las líneas verticales y horizontales (cyan), no se añadirán como 'promesas'. Tampoco (aunque en este ejemplo no sucede ninguna vez), cuando tocan la línea diagonal. esos tampoco se añaden, solo se añade aquel punto que en una línea hace el cambio de blanco a negro (o negro a blanco, según hayamos tratado la imagen) y que está en esa línea lo más a la derecha posible (para este cuadrante).

En la última imagen que subiré, he trazado la misma línea y luego he tachado los puntos que no se añadirán y luego a distancia he reasaltado (en azul) los que se irán añadiendo (las promesas).




En la siguiente imagen he trazado varias líneas fiormando ángulos (la diagonal roja va desde el PuntoA (Picos(0) al PuntoB  (Picos(k) y desde éste a cada uno de los que forman el bucle 'j'. Lógicamente he abreviado, habrá muchos más puntos promesa...


En esta otra, ahora el punto K, es el que antes fue el 'j' elegido como el de mayor ángulo. Y el bucle 'j' recorre los puntos que están 'por encima de él' (encima, debajo, ya saber que depende de la forma de recorrer los bucles, la imagen ayuda aentender y fijar el caso).
Para el caso concreto, he vuelto a trazar de rojo, la línea que va desde Picos(0) a Picos(k) (el que ahora es k, el bucle externo).
Fíjate que una posible optimización es descartar todos los picos (por encima de él), que tengan ángulo inferior a 0, es decir los que queden a la izquierda de la línea roja entre él y el puntoA de origen. al caos he marcado 2 puntos (color verde), como representantes de este caso.
Ahora bien esa optimización solo lo será en función de cuantos haya, si sale más caro una cosa que otra. Pero en cualquier caso, si el ánguilo es negativo, ya ni siquiera lo comparamos, se descarta...o mejor se eliminan d ela colección, así cuando vayamos subiendo más arriba no hay que volverlos a calcular ni comparar...


En la siguiente imagen ya quedan pocos puntos promesas (serán más, yo resumo para nio poner tantas líneas que no quede claro).


Finalmente hallamos el último punto, es decir es el de origen, no pasa por poco por otro en medio.
Fíjate que tiene ángulo negativo. En cambio el ángulo resultante es 0.


Ahora una imagen que muestra otros aspectos de interés y que espero que ayude a aclararte las dudas que puedna quedarte.
Tiene 3 apartados, al 1º me refiero aquí, los otros dos son para más abajo, donde voy respondiendo, y no se hace necesario poner más imágenes independientes.

Nota como los "puntos promesa", realmente sólo son aquellos que tiran por la línea azul. De las líneas que 'caen verticalmente solo se toma como promesa el que se encuentra por primera vez, si en la siguiente línea no hay uno más a la derecha que ese anterior, no se añade.
Con las líneas horizontales pasa los mismo, solo se añade el que está más a la derecha.
Igualmente aunque estén más a la derecha que en líneas anteriores, si no cambian tocando un pixel de blanco a negro, no cuentan aunque toquen la diagonal y estén más a la derecha... porque 'acaba la línea' sin haber tocado un punto negro', luego no se añade.

Con respecto a calcular el angulo he visto en el pseudocodigo que para calcular el angulo envias tres parametros, Picos(0), Picos(k), Picos(j), por que no se envian solo dos parametros? punto central y punto del que se quiere saber el angulo?

En efecto, Picos(0) es fijo para todos... pero el ángulo se calcula con 3 puntos. Además el orden de estos es importante, si no estarías tomando otro ángulo del 'triángulo que forman los 3 puntos.

En la última imagen subida, en el apartado 3, constan 3 puntos y el ángulo que forman entre si...

Si llamas a una función, puede pasar solo el 2º y 3º puntos siempre y cuando compartas el array y por tanto la función llamada, pueda saber el valor del punto primero ( Picos(0) ).

Picos(0) : Es el punto superior que hallamos al comienzo.
Picos(k) : Es el punto desde el cual estamos tirando ángulos hasta el resto de picos.
Picos(j) : Son cada uno de los puntos que en el presente bucle interno, nos dará los ángulos entre los cuales, se debe conocer el ángulo mayor.

Hallado el punto de este bucle, este hallado pasa a ser el el siguiente ciclo el Picos(k). (en el siguiente bucle, se descartan los picos intermedios entre el k actual y el j, es decir k pasa a ser j... este bucle puede ser un while... pero no  quiero condicionarte con detalles, tu busca la salida y ya si te alejas mucho yo te reoriento...

" Si dos o más puntos tuvieran casualmente el mismo ángulo, se toma por bueno el que quede mas lejos "
Supongo que sera mas lejos del punto que se toma como central para calcular los angulos en este caso el punto B.

En la última imagen en el apartado '2', pongo un ejemplo con dos casos. Hay varios picos salientes, pero están en líonea.
Es decir, los angulos: IAB, IAC, IAD e IAE, son iguales, luego sus puntos están alineados en línea recta).
Entonces el punto más alejado es IAE, ya que sería redundante dar por válido como picos a B,C,D y E.
Al decir más alejado, me refiero a la dirección en la que avance el bucle, como los picos los vamos recorriendo hacia atrás, el más 'lejano' será: E, si fuera creciente, desde E, el más lejano sería A (B,C y D serían redundantes).
He puesto el mismo caso con E, F, G, H e I , están en línea recta, todos tienen el mismo ángulo:
IEF = IFG = IGH = IHI (olvida el caso de que I esté alineado con ellos, y el ángulo sea 0...
Nota que todos los pìcos por dentro de la diagonal IA, tienen ángulo menor de 0, por eso la respuesta en ese caso sería la línea I-A.

Sobre el pseodocodigo:
si, la figura es toda negra y el fondo es blanco.
si aplico este pseudocodigo pasara lo de la imagen de arriba, cada vez que detecte pixel negro se agregara al array, pero esto no garantiza que el pixel que se agrega sea el punto saliente sino que sera un posible punto saliente y entre esas posibilidades esta el que se busca (el mas saliente de ese pico) que se detectara con su angulo mayor al de los demas (para ese pico).

Si, lo hemos comentado más arriba...

Sobre el algoritmo de Bresenham, lo busque y lo estuve viendo, algunas cosas las entiendo otras no... igual para mi suerte puede implementarlo y usarlo para hacer lineas rectas, eso queda pendiente saber como funciona al 100% ese algoritmo, una de las dudas era:
p = 2*dy - dx; Eso se puede leer como: 2 veces la distancia en el eje 'y' menos 1 vez la distancia en el eje 'x' pero no se que es eso visto del punto de vista de la matematica, que representa, que nombre tiene, que significa... etc.

Ok, mañana a ver si después de comer saco un tiempito y te doy unas explicaciones y un sencillo pseudocódigo que te ayude a entenderlo bien...

He escrito algo de codigo, el codigo resuelve el primer cuadrante de cada imagen, los cuadrantes se cuentan en sentido contrario a las agujas del reloj, lo hice asi por que asi habia comenzado a hacerlo con la idea anterior (la del scanner con lineas diagonales) y para no perder tiempo modificando algo que ya estaba hecho lo hice de esta manera

El codigo tiene algunos comentarios, se hace partiendo desde la deteccion de poligono ya que lo anterior es para convertir la img en escala de grises y sacar los bordes, pintar la img etc. Tambien se incluye la imagen (que trae 5 imagenes dentro 5 en 1) esta img se llama "a.png". Al ejecutar el programa guarda en el disco "D:/" varias imagenes, que son los pasos del programa, las que tienen mas importancia son las imagenes llamadas "PPS0.png", "PPS1.png"... en esas imagenes se ven los resultados del scanner horizontal donde cada posible punto saliente es marcado en verde, los puntos rojos son los puntos mas salientes de cada lado. Luego las imagenes que se llaman "TrazarLineaX.png"... son las imagenes que muestran los puntos mas salientes y los posibles puntos salientes pero ademas de eso tambien muestra los puntos salientes que resuelven ese cuadrante (puntos de color azul), en la imagen 4 hay un error que es por la forma en que se calculan los angulos entre dos puntos, toma una recta en el eje de absisas positivo como perteneciente al cuadrante 4 entonces eso hace que tenga angulo de 360 cuando tiene 0.

Bien, aunque lo descargué tengo pendiente mirarlo, a ver si saco tiempo y te comento.

PD: en entos dias subire una imagen que refleje una duda que tengo sobre esta forma de detectar los puntos salientes.

De acuerdo.
Piensa que se puede optimizar, pero lo interesante al principio es que lo entiendas bien y te funcione correctamente. Luego cuando ya lo tengas perfectamente claro puedes tratar de optimizarlo.
es evidente que si te pongo un pseudiocódigo muy optimizado, resultará complejo entender y no quedará claro el porqué de cada cosa... ahora mismo tal como está es muy sencillo y fácil de entender (creo yo, claro   o al menos esa es la idea   ).

[Serapis]

Ajustado de tiempo, iba a apuntarte a wikipedia, para el algoritmo de Bresenham, pero luego que he ido a verlo solo tiene un párrafo y el 'pseudocódigo' es desastroso e incomprensible. Así que en vez de ponerte aquí la descripción del algoritmo de Bresenham, lo editaré en la wikipedia y te paso el enlace (así será útil para todo el mundo), además en el foro no he encontrado ninguno específico dedicado a algoritmos donde ponerlo y dejarlo aquí 'encerrado' acabará perdiéndose en la 'maleza del bosque'.

Mañana estaré ocupado con un evento familiar, así que será cuando saque un tiempito el domingo (incluso probablemente en la madrugada del lunes antes de ir al trabajo). Las imágenes con las que lo acompañe, serán a mano alzada (así que alguno (bueno, muchos) en wikipedia se quejarán y espero que gente con más tiempo libre y buen hacer, con el tiempo las cambie por algunas bien trabajadas  ).

[footer]

Hola NEBIRE, una vez mas te doy gracias por la explicacion y pido disculpas por el tiempo de respuesta, es que he estado teniendo algunas complicaciones y poco tiempo, ademas mi codigo es un lio.

Asi que voy a empezar de nuevo todo el proyecto desde cero, y voy a aplicar lo que me dijiste que haga, puntos centrales, cuadrantes, promesas, cantidad minima de picos, etc.

Cuando tenga mi codigo hecho lo publicare aqui, por ahora las ideas quedaron claras, saludos,

PD: voy a revisar la wikipedia apara ver tus explicaciones, hasta la proxima. (Y)

[Serapis]

Bien...

Es importante hacer siempre un buen reparto de clases. si son un par de métodos sólo, s epueden meter de forma privada a una clase, pero cuando son muchos, acaba siendo más práctico y claro, crear una clase al efecto que contenga y mantenga toda la funcionalidad relacionada.

...mientras iré editando el artículo en wikipedia... es realmente sencillo, pero tal como estaba era incomprensible y el pseudocódigo actual, más de lo mismo, amén que no se atiene al algoritmo final... eso csí, lo iré editando sin prisas 

[Serapis]

Ya he editado prácticamente el artículo con el pseudocódigo (que ahora es inteligible, claro y eficaz, antes era un caos y estaba inacabado).

Me falta poner alguna imagen más y acompañarlo de un ejemplo didáctico que muestre paso a paso como funciona.

...y bueno, quizás retocarlo un poco más para que quede más 'enciclopédico', aunque eso ya lo harán otros con el tiempo, de hecho puede que lo acaben dotando con un desarrollo matemático que al final resulte de nuevo ininteligible para la mayoría de los mortales (a pesar de su simplicidad), cuestiones de idiotez en la pureza de las formas, frente a la claridad para el entendimiento...

https://es.wikipedia.org/wiki/Algoritmo_de_Bresenham