algorithm - salud - Encuentra el área negra convexa más grande en una imagen
principios y normas de enfermeria en el area quirurgica (5)
Tengo una imagen de la cual este es un pequeño recorte:
Como puede ver, son píxeles blancos sobre un fondo negro. Podemos dibujar líneas imaginarias entre estos píxeles (o mejor, puntos). Con estas líneas podemos encerrar áreas.
¿Cómo puedo encontrar el área negra convex más grande en esta imagen que no contiene un píxel blanco?
Aquí hay un pequeño ejemplo dibujado a mano de lo que quiero decir con el área negra convexa más grande:
PD: la imagen no es ruido, representa los números primos por debajo de 10000000 ordenados horizontalmente.
Dibujaré un algoritmo correcto, de tiempo de polietileno. Sin lugar a dudas, hay mejoras en los datos estructurales, pero creo que se requerirá una mejor comprensión de este problema en particular para buscar conjuntos de datos de gran tamaño (o, tal vez, un límite superior ad hoc en las dimensiones del cuadro que contiene el polígono).
El ciclo principal consiste en adivinar el punto p más bajo en el polígono convexo más grande (rompiendo vínculos a favor del punto más a la izquierda) y luego calculando el polígono convexo más grande que puede ser con py los puntos q de manera que (qy> py) || (qy == py && qx> px).
El programa dinámico se basa en los mismos hechos geométricos que el escaneo de Graham . Asuma sin pérdida de generalidad que p = (0, 0) y clasifique los puntos q en el orden del ángulo en sentido antihorario que hacen con el eje x (compare dos puntos al considerar el signo de su producto escalar). Deje que los puntos en orden ordenado sean q 1 , ..., q n . Deje q 0 = p. Para cada 0 ≤ i <j ≤ n, vamos a calcular el polígono convexo más grande en los puntos q 0 , un subconjunto de q 1 , ..., q i - 1 , q i y q j .
Los casos base donde i = 0 son fáciles, ya que el único "polígono" es el segmento de área cero q 0 q j . Inductivamente, para calcular la entrada (i, j), vamos a intentar, para todos los 0 ≤ k ≤ i, extender el (k, i) polígono con (i, j). ¿Cuándo podemos hacer esto? En primer lugar, el triángulo q 0 q i q j no debe contener otros puntos. La otra condición es que el ángulo q k q i q j es mejor que no sea un giro a la derecha (una vez más, verifique el signo del producto de punto apropiado).
Al final, devuelve el polígono más grande encontrado. ¿Por qué funciona esto? No es difícil probar que los polígonos convexos tienen la subestructura óptima requerida por el programa dinámico y que el programa considera exactamente esos polígonos que satisfacen la caracterización de la convexidad de Graham.
Pensé en un enfoque para resolver este problema:
Fuera del conjunto de todos los puntos, genere todos los posibles subconjuntos de 3 puntos. Este es un conjunto de todos los triángulos en tu espacio. A partir de este conjunto, elimine todos los triángulos que contengan otro punto y obtendrá el conjunto de todos los triángulos vacíos.
Para cada uno de los triángulos vacíos, lo crecerá hasta su tamaño máximo. Es decir, para cada punto fuera del rectángulo, lo insertaría entre los dos puntos más cercanos del polígono y verificaría si hay puntos dentro de este nuevo triángulo. Si no, recordarás ese punto y el área que agrega. Por cada nuevo punto que desee agregar, aquel que maximiza el área agregada. Cuando no se puede agregar más puntos, se ha construido el polígono convexo máximo. Registre el área para cada polígono y recuerde la que tiene el área más grande.
Crucial para el rendimiento de este algoritmo es su capacidad para determinar a) si un punto se encuentra dentro de un triángulo yb) si el polígono permanece convexo después de agregar un cierto punto.
Creo que puedes reducir b) ser un problema de a) y luego solo necesitas encontrar el método más eficiente para determinar si un punto está dentro de un triángulo. La reducción del espacio de búsqueda se puede lograr de la siguiente manera: tome un triángulo y aumente todos los bordes a una longitud infinita en ambas direcciones. Esto separa el área fuera del triángulo en 6 subregiones. Lo bueno para nosotros es que solo 3 de esas subregiones pueden contener puntos que se ajusten a la restricción de convexidad. Por lo tanto, para cada punto que pruebes debes determinar si está en una subregión de expansión convexa, que nuevamente es cuestión de si está en un cierto triángulo.
El polígono completo a medida que evoluciona y se aproxima a la forma de un círculo tendrá regiones cada vez más pequeñas que aún permiten la expansión convexa. Un punto una vez en una región cóncava no volverá a formar parte de la región de expansión convexa, de modo que puede reducir rápidamente la cantidad de puntos que tendrá que considerar para la expansión. Además, mientras prueba puntos para expansión, puede reducir aún más la lista de posibles puntos. Si un punto se prueba falso, entonces está en la subregión cóncava de otro punto y, por lo tanto, no es necesario considerar todos los otros puntos en la subregión cóncava de los puntos probados, ya que también están en la subregión cóncava del punto interno. Debería poder reducir a una lista de puntos posibles muy rápidamente.
Aún así, debes hacer esto para cada triángulo vacío, por supuesto.
Lamentablemente, no puedo garantizar que al agregar siempre la región nueva máxima, su polígono se convierta en el máximo posible.
Podría intentar tratar los píxeles como vértices y realizar la triangulación de Delaunay del conjunto de puntos. Entonces necesitarías encontrar el conjunto más grande de triángulos conectados que no crea una forma cóncava y no tiene vértices internos.
Si entiendo su problema correctamente, es una instancia de etiquetado de componentes conectados. Puede comenzar, por ejemplo, en: http://en.wikipedia.org/wiki/Connected-component_labeling
Tratar de encontrar el área convexa máxima es una tarea difícil de hacer. ¿No estarías bien para encontrar rectángulos con un área máxima? Este problema es mucho más fácil y se puede resolver en O (n): tiempo lineal en cantidad de píxeles. El algoritmo sigue.
Digamos que quiere encontrar el rectángulo más grande de píxeles libres (blancos) (lo siento, tengo imágenes con diferentes colores, el blanco es equivalente a su negro, el gris es equivalente a su blanco).
Puede hacerlo de manera muy eficiente mediante el algoritmo de tiempo O(n) dos pasadas (siendo n el número de píxeles):
1) en un primer paso , vaya por columnas, de abajo hacia arriba, y para cada píxel, denote el número de píxeles consecutivos disponibles hasta este:
repetir hasta:
2) en una segunda pasada , vaya por filas, lea current_number . Para cada número k lleve un registro de las sumas de números consecutivos que fueron >= k (es decir, rectángulos potenciales de altura k ). Cierre las sumas (rectángulos potenciales) para k > current_number y observe si la suma (~ área del rectángulo) es mayor que el máximo actual; en caso afirmativo, actualice el máximo. Al final de cada línea, cierre todos los rectángulos potenciales abiertos (para todos los k ).
De esta forma obtendrás todos los rectángulos máximos. No es lo mismo que el área convexa máxima, por supuesto, pero probablemente le daría algunas pistas (algunas heurísticas) sobre dónde buscar las áreas convexas máximas.