Aquí hay una imagen en blanco y negro.
Se representa, como es de esperar, como una matriz de bits: 0 es blanco, 1 es negro. Su desafío de programación es determinar la cantidad de componentes conexos en dicha imagen. En este ejemplo, hay tres de ellos:
¡No es necesario que los coloree! Solo estoy aclarando lo que quiero decir con «componente conexo».
Puede hacer las siguientes suposiciones. Los píxeles negros de un componente comparten un borde, no solo una esquina. Suponga que esto:
no sucede. Los componentes conexos están fuertemente conectados (sus píxeles comparten un borde) y los diferentes componentes no se tocan ni siquiera en las esquinas de los píxeles. Con una imagen de alta resolución como el ejemplo anterior, esas son suposiciones muy naturales (Nota: en una versión anterior de esta respuesta, era demasiado laxo aquí. Ahora fue corregido).
Otra suposición simplificadora que puede hacer es que no hay agujeros. Las «manchas», los componentes conectados, están completas y llenos. Estas manchas se denominan simplemente conexas.
No sucede
Finalmente, puede suponer que el borde exterior de la matriz es todo blanco. Si no es así, puedes ponerle un relleno blanco.
Entonces:
- Entrada: matriz de bits, que representa una imagen con componentes simplemente conectados.
- Salida: un número entero que representa el número de componentes.
- ¡VAMOS!
En realidad, este es un problema algorítmico importante y útil. Se necesitan versiones del mismo, por ejemplo, en ciencia e ingeniería para contar objetos en imágenes industriales, biológicas o médicas.
zzz
Entonces, ¿cómo lo resolverías?
Casi cualquiera que intente esto hace lo más natural: Algoritmo de relleno por difusión
. Escanee la imagen, busque un píxel negro, comience a ver sus vecinos y sus vecinos, etc., marcando los píxeles que ha encontrado en el camino. Cuando se quede atascado, retroceda hasta un píxel negro anterior que aún tenga vecinos sin procesar y continúe hasta que haya completado un mancha. Agregue
al recuento de manchas. Comenzar de nuevo.
Aquí hay una animación rápida (de la página Wiki loc. Cit.) De un algoritmo de relleno de inundación que llena una mancha blanca sobre un fondo negro.
Este no es un algoritmo muy difícil, pero tampoco es sencillo. El artículo de Wikipedia muestra varias versiones, incluida una bastante optimizada con unas 100 líneas de pseudocódigo. También vea Connected-component
(Naturalmente, otros programadores han abordado el problema , pero como puede ver, ni siquiera ellos pudieron reducirlo a sus programas habituales de Jelly de 9 bytes. Excepto por el tipo que hizo trampa con el imfill de Matlab, las soluciones son cientos de bytes de código denso.)
Pero recuerde, no le pedí que llenara nada, ni que etiquetara las manchas. Solo queremos contar ¿hay una manera mas fácil?
Sí, la hay, de una manera increíblemente simple y fácil. Le permite contar el número de componentes conectados en el caso simplemente conectado y, de hecho, funciona de manera más general: cuenta el número de componentes menos el número de agujeros. Si asumimos que no hay agujeros, como hicimos, entonces simplemente obtienes la cantidad de manchas.
Aquí está el algoritmo completo.
Establezca un contador en
. Escanee la imagen completa, una vez, mirando cuadros de
píxeles ancladas en cada píxel. Agregue 1 al contador cada vez que vea esto (un «punto»):
Reste 1 cada vez que vea que (una «T»):
Hecho. El contador tiene el número de componentes conectados.
Sí, en serio. Sin colas, sin pilas, sin recursividad, sin backtracking, sin rellenos por difusión, sin etiquetado, nada. Solo una pasada simple, lineal y única a través de la matriz y contando dos combinaciones simples de píxeles.
Si esta es la entrada:
Obtendrá un
y sin restas. Salida:
. Correcto.
Si esta es la entrada:
Contará dos
y un . Salida
Correcto
Ahora un ejemplo mas complicado:
Hay
y hay Salida: 1. Correcto
La naturaleza local del algoritmo deja bastante claro que si funciona para manchas individuales, funciona para cualquier número de manchas. De hecho, es aditivo bajo superposiciones. Superponga dos manchas separadas y el algoritmo simplemente acumulará los resultados de cada uno independiente.
Este algoritmo es una instancia de algo verdaderamente profundo: el comportamiento local-global de la Característica de Euler
. En palabras simples, si tiene datos geométricos locales y está interesado en las características globales, tome una suma alternada. En nuestro caso, «puntos menos T» es lo mismo que «componentes menos agujeros». La misma idea se encuentra detrás de resultados profundos como el Teorema del punto fijo de Lefschetz y el Teorema de Gauss-Bonnet
Tendremos que guardar una prueba completa para otra respuesta, pero diría que este es un ejemplo asombroso de un problema algorítmico aparentemente desafiante que resulta tener una solución ridículamente simple.