Contando el número de grupos de 1s en un mapa booleano de numpy.array

16

En este momento estoy tratando con algo de procesamiento de imágenes en Python a través de PIL (Python Image Library). Mi objetivo principal es contar el número de células coloreadas en una imagen inmunohistoquímica. Sé que hay programas relevantes, bibliotecas, funciones y tutoriales al respecto, y revisé casi todos. Mi objetivo principal es escribir el código manualmente desde cero, tanto como sea posible. Por lo tanto, estoy tratando de evitar el uso de muchas bibliotecas y funciones exteriores. He escrito la mayor parte del programa. Así que aquí está lo que está sucediendo paso a paso:

El programa toma el archivo de imagen:ejemplo

Y lo procesa para los glóbulos rojos (básicamente, apaga los valores RGB por debajo de un cierto umbral para el rojo): ingrese la descripción de la imagen aquí

Y crea el mapa booleano del mismo (va a pegar una parte ya que es grande) que básicamente pone 1 donde sea que se encuentre con un píxel rojo en la segunda imagen procesada de arriba. 

22222222222222222222222222222222222222222
20000000111111110000000000000000000000002
20000000111111110000000000000000000000002
20000000111111110000000000000000000000002
20000000011111100000000000000000001100002
20000000001111100000000000000000011111002
20000000000110000000000000000000011111002
20000000000000000000000000000000111111002
20000000000000000000000000000000111111102
20000000000000000000000000000001111111102
20000000000000000000000000000001111111102
20000000000000000000000000000000111111002
20000000000000000000000000000000010000002
20000000000000000000000000000000000000002
22222222222222222222222222222222222222222

Intencionalmente generé ese marco como cosa en los bordes con 2s para ayudarme a contar el número de grupos de 1s en ese mapa booleano.

Mi pregunta para ustedes es, ¿cómo puedo contar eficientemente el número de celdas (grupos de 1s) en ese tipo de mapa booleano? Encontré http://en.wikipedia.org/wiki/Connected-component_labeling que se ve extremadamente relacionado y similar, pero por lo que veo, está en el nivel de píxeles. El mío está en el nivel booleano. Solo 1s y 0s.

Muchas gracias.

python Ibrahim C. Kurt
fuente
El etiquetado de componentes conectados es exactamente lo que necesita. No sé por qué piensas que es diferente, ya que el artículo de Wikipedia también tiene ejemplos que comienzan con matrices de 1s y 0s.
Sé que se ve similar (o tal vez igual), simplemente no puedo comprender completamente toda la página de wikipedia ya que el inglés no es mi idioma nativo. La parte del "algoritmo secuencial" de la página parece tratar con 1s y 0s pero aún así no vi la lógica detrás de ella. Forex, ¿por qué comienza marcando el norte, noreste, noroeste y oeste?
Este problema está resuelto.
¿Qué pasa si las celdas de interés se superponen? ¿No debería buscar específicamente características circulares para poder diferenciar dos celdas que parecen conectadas, no solo para encontrar blobs continuos?
endolito
las cosas se vuelven mucho más complicadas cuando las imágenes de inmunohistoquímica que tienes son de mala calidad en términos de superposición de número de células, resolución, desviación estándar de los valores de píxeles de manera regular ... He estado tratando de escribir un pequeño programa que funcione bien para tales propósitos, pero parece que la imagen de entrada y sus condiciones son muy importantes para un resultado perfecto ...
Ibrahim C. Kurt

Respuestas:

6

Algo así como un enfoque de fuerza bruta, pero hecho invirtiendo el problema para indexar sobre colecciones de píxeles para encontrar regiones, en lugar de rasterizar sobre la matriz.

data = """\
000000011111111000000000000000000000000
000000011111111000000000000000000000000
000000011111111000000000000000000000000
000000001111110000000001000000000110000
000000000111110000000011000000001111100
000000000011100000000000100000011111100
000000000000000000000000000000011111100
000000000000000000000000000000011111110
000000000000000000000000000000111111110
000000000000000000000000000000111111110
000000000000000000000000000000011111100
000000000000000000000000000000001000000
000000000000000000000000000000000000000"""

from collections import namedtuple
Point = namedtuple('Point', 'x y')

def points_adjoin(p1, p2):
    # to accept diagonal adjacency, use this form
    #return -1 <= p1.x-p2.x <= 1 and -1 <= p1.y-p2.y <= 1
    return (-1 <= p1.x-p2.x <= 1 and p1.y == p2.y or
             p1.x == p2.x and -1 <= p1.y-p2.y <= 1)

def adjoins(pts, pt):
    return any(points_adjoin(p,pt) for p in pts)

def locate_regions(datastring):
    data = map(list, datastring.splitlines())
    regions = []
    datapts = [Point(x,y) 
                for y,row in enumerate(data) 
                    for x,value in enumerate(row) if value=='1']
    for dp in datapts:
        # find all adjoining regions
        adjregs = [r for r in regions if adjoins(r,dp)]
        if adjregs:
            adjregs[0].add(dp)
            if len(adjregs) > 1:
                # joining more than one reg, merge
                regions[:] = [r for r in regions if r not in adjregs]
                regions.append(reduce(set.union, adjregs))
        else:
            # not adjoining any, start a new region
            regions.append(set([dp]))
    return regions

def region_index(regs, p):
    return next((i for i,reg in enumerate(regs) if p in reg), -1)

def print_regions(regs):
    maxx = max(p.x for r in regs for p in r)
    maxy = max(p.y for r in regs for p in r)
    allregionpts = reduce(set.union, regs)
    for y in range(-1,maxy+2):
        line = []
        for x in range(-1,maxx+2):
            p = Point(x, y)
            if p in allregionpts:
                line.append(str(region_index(regs, p)))
            else:
                line.append('.')
        print ''.join(line)
    print


# test against data set
regs = locate_regions(data)
print len(regs)
print_regions(regs)

Huellas dactilares:

4
........................................
........00000000........................
........00000000........................
........00000000........................
.........000000.........1.........33....
..........00000........11........33333..
...........000...........2......333333..
................................333333..
................................3333333.
...............................33333333.
...............................33333333.
................................333333..
.................................3......
........................................

fuente
wow ... no sé qué decir. Muy genial. Y totalmente funciona. Gracias paul
Mucho trabajo en esto, cuando ya hay una función para Scipyhacerlo, que probablemente también sea más rápida ^^ 'Pero probablemente sea un buen ejercicio de todos modos y muestra cómo hacerlo en general. Entonces votaré.
Zelphir Kaltstahl
13

Puede usar ndimage.label, que es una buena manera de hacer esto. Devuelve una nueva matriz, con cada característica que tiene un valor único y el número de características. También puede especificar un elemento de conexión.

import scipy
from scipy import ndimage
import matplotlib.pyplot as plt

#flatten to make greyscale, using your second red-black image as input.
im = scipy.misc.imread('blobs.jpg',flatten=1)
#smooth and threshold as image has compression artifacts (jpg)
im = ndimage.gaussian_filter(im, 2)
im[im<10]=0
blobs, number_of_blobs = ndimage.label(im)
print 'Number of blobls:', number_of_blobs

plt.imshow(blobs)
plt.show()

#Output is:
Number of blobls: 30

ingrese la descripción de la imagen aquí

j08lue
fuente
Gracias fraxel. Eso funciona totalmente como una solución rápida y sucia, pero tal vez debería mejorar la calidad de la imagen, porque como puede ver, hay muchas celdas combinadas. La respuesta debe ser de 30 celdas. Muchas gracias de nuevo. (editar: Traté de mejorar la calidad de resolución de la imagen y luego la borré con su código, pero aún combina muchas celdas. ¿Debe ser la forma en que flatten = 1 o imread funciona?)
1
@Ibrahim C. Kurt - He actualizado para corregir eso (¡solo lo noté!). El problema era que la imagen cargada era jpg, por lo que tenía muchos artefactos. Una pequeña cantidad de suavizado y umbral resuelve que ... Debería funcionar perfectamente para una imagen png (creo ...)
sin la necesidad de suavizar y poner umbrales.
Funciona totalmente Tienes razón. Sin la necesidad de ninguna modificación adicional, basta con cambiarlo a png desde jpg. Muchas gracias. Tengo más de 2 respuestas perfectas ahora. No sé qué hacer y decir: D
@Ibrahim C. Kurt - afortunado;)
6

Aquí hay un algoritmo que es O (número total de píxeles + número de píxeles de celda). Simplemente escaneamos la imagen en busca de píxeles de celda, y cuando encontramos una, llenamos la celda para borrarla.

Implementación en Common Lisp, pero podrás traducirlo a Python trivialmente.

(defun flood-fill (picture i j target-color replacement-color)
  ;; http://en.wikipedia.org/wiki/Flood_fill
  (when (= (aref picture i j) target-color)
    (setf (aref picture i j) replacement-color)
    (when (plusp i)
      (flood-fill picture (1- i) j target-color replacement-color))
    (when (< (1+ i) (array-dimension picture 0))
      (flood-fill picture (1+ i) j target-color replacement-color))
    (when (plusp j)
      (flood-fill picture i (1- j) target-color replacement-color))
    (when (< (1+ j) (array-dimension picture 1))
      (flood-fill picture i (1+ j) target-color replacement-color)))
  picture)


(defun count-cells (picture)
  (loop
    :with cell-count = 0
    :for i :from 0 :below (array-dimension picture 0)
    :do (loop
          :for j :from 0 :below (array-dimension picture 1)
          :unless (zerop (aref picture i j))
          :do (progn (incf cell-count)
                     (flood-fill picture i j 1 0)))
    :finally (return cell-count)))




(count-cells
  (make-array '(128 171) :element-type 'bit
              :initial-contents
              #(#171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111000000000000000000001110000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111110000000000000000000011111100
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000011111100
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111100
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111110
                #171*000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111110
                #171*000000000011111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111110
                #171*000000000011111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111100
                #171*000000000011111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
                #171*000000000001111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
                #171*000000000001111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
                #171*000000000000011110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
                #171*000000000000011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111000000000000000000011
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111100000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111100000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111110000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111000000000000000000000111111110000000000000000000
                #171*000000000000000000111111000000000000000000000000000000000000000000000000000000111110000000000000000000000000000000000001111111100001111000000000011111110000000000000000000
                #171*000000000000000000111111100000000000000000000000000000000000000000000000000011111110000000000000000000000000000000000111111111100011111100000000011111100000000000000000000
                #171*000000000000000000111111100000000000000000000000000000000000000000000000000011111110000000000000000000000000000000000111111111110111111110000000000100000000000000000000000
                #171*000000000000000000111111100000000000000000000000000000000000000000000000000011111100000000000000000000000000000000000111111111110111111110000000000000000000000000000000000
                #171*000000000000000000111111100000000000000000000000000000000000000000000000000011111100000000000000000000000000000000000011111111100111111110000000000000000000000000000000000
                #171*000000000000000000111111100000000000000000000000000000000000000000000000000011111100000000000000000000000000000000000001111111100111111110000000000000000000000000000000000
                #171*000000000000000000011111100000000000000000000000000000000000000000000000000011111001110000000000000000000000000000000000011111000011111110000000000000000000000000000000000
                #171*000000000000000000010110000000000000000000000000000000000000000000000000000000000011111000000000000000000000000000000000000000000000111010000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111000000000000000000000000000000000000000000000000000000111100000000000000000000000
                #171*000000000000000000000000000000000000000000000111100000000000000000000000000000000000111100000000000000000000000000000000000000000000000000000011111111100000000000000000000
                #171*100000000000000000000000000000000000000000001111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111100000000000000000000
                #171*111100000000000000000000000000000000000000011111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111100000000000000000000
                #171*111100000000000000000000000000000000000000011111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111100000000000000000000
                #171*111100000000000000000000000000000000000000111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111100000000000000000011
                #171*111100000000000000000000000000000000000000111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011110000000000000000000111
                #171*111100000000000000000000000000000000000000011111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111
                #171*000000000000000000000000000000000000000000011111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
                #171*000000000000000000000000000000000000000000000001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111100000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111100000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111100000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111100000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000001111111100000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111100000000000000000000000000000000000000000111111000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111100000000000000000000000000000000000000111110000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111100000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111110000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111110000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111110000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000011111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000001111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000001111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000001111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000001111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000011111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000011111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000011111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000011111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000011000000000000000000000000000000000000000000000000000001111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000001111100000000000000000000000000000000000000000000000000000111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000011111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000111111110000000000000000000000000000000000000000011111100000000000000000000000000000000000000000000000000111111000000000000000000000000000000000000000000000
                #171*000000000000000111111111000000000000000000000000000000000000000011111100000000000000000000000000000000000000000000000001111111100000000000000000000000000000000000000000000
                #171*000000000000000111111110000000000000000000000000000000000000000111111110000000000000000000000000000000000000000000000001111111100000000000000000000000000000000000000000000
                #171*000000000000000111111110000000000000000000000000000000000000001111111110000000000000000000000000000000000000000000000001111111110000000000000000001111111000000000000000000
                #171*000000000000000011111110000000000000000000000000000000000000001111111110000000000000000000000000000000000000000000000001111111110000000000000000011111111100000000000000000
                #171*000000000000000001110000000000000000000000000000000000000000000111111110000000000000000000000000000000000000000000000000011111100000000000000000011111111100000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000111111100000000000000000000000000000000000000000000000000001111000000000000000000011111111100000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000011111000000000000000000000000000000000000000000000000000000000000000000000000000011111111100000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111100000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000000000000000000000001111111000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111100000000000000000000000000000000000000000000100010000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000001111100000000000000000111111110000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000011111110000000000000011111111110000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000011111110000000000000011111111110000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000011111110000000000000011111111110000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000011111111000000000000011111111110000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000011111110000000000000011111111100000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000001111100000000000000010111111100000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000001111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000001111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000001111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000011111111110000000000000000000000000000000000000011111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000011111111110000000000000000000000000000000000000111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000011111111110000000000000000000000000000000000001111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000001111111110000000000000000000000000000000000001111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000001111111000000000000000000000000000000000000001111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000000000000000000000000000000000011111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000011111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000011111100000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000001111111110000000000000110000000000000000000000001111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000001111111110000000000001111100000000000000000000011111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000001111111110000000000111111111000000000000000000011111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000111111110000000000111111111000000000000000000111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000111111111000000000111111111100000000000000000111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000011111100001111000111111111100000000000000000111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000111111100111111111100000000000000000011111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000000111111100011111111100000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
                #171*000000000000000000000000001111111100011111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)))
--> 30

fuente
Hola Pascal, muchas gracias por la respuesta. Veo que su programa encuentra la respuesta correcta muy limpiamente. El problema es que no tengo idea sobre el lenguaje Common Lisp, pero intentaré descifrarlo y escribir un script similar en Python.
3

Más un comentario extendido que una respuesta:

Como @interjay ha insinuado, en una imagen binaria, es decir, una en la que solo hay 2 colores, los píxeles toman el valor 1 o 0. Esto puede ser cierto o no en el formato de representación de imagen que está utilizando, pero es cierto en la representación 'conceptual' de tu imagen; no permita que los detalles de implementación lo confundan con este problema. Uno de esos detalles de implementación es el uso de 2s alrededor del borde de la imagen, una forma perfectamente sensata de identificar la zona muerta alrededor de la imagen, pero sin afectar cualitativamente el carácter binario de la imagen.

En cuanto al examen de los píxeles N, NE, NW y W: esto tiene que ver con la conectividad de píxeles en la formación del componente. Cada píxel (excepto los casos especiales de borde) tiene 8 vecinos (N, S, E, W, NE, NW, SE, SW) pero ¿cuáles son candidatos para su inclusión en el mismo componente? A veces, los componentes que se encuentran solo en las esquinas (NE, NW, SE, SW) no se consideran conectados, a veces sí.

Debe decidir qué es apropiado para su aplicación. Le sugiero que realice, a mano, algunas operaciones del algoritmo secuencial, verificando diferentes vecinos para cada píxel, para tener una idea de lo que está sucediendo.


fuente