Un algoritmo no supervisado aplicado a la segmentación de imágenes

Berns, Daniel Walther
UNPSJB, Facultad de Ingeniería
https://www.orcid.org/0000-0002-7231-6392
dwberns@ing.unp.edu.ar

Resumen:

En este trabajo mostramos un algoritmo no supervisado para segmentar imágenes, basado en la clasificación de pixeles mediante una red neuronal arbitraria cuyos coeficientes pueden ser calculados mediante la descomposición en valores singulares de una matriz. Proveemos un demo publicado en huggingface, y la teoría respectiva.


Palabras claves: Segmentación, Imagen, Algoritmo.

A non supervised algorithm for images segmentation

Resumen:

In this work we show an unsupervised algorithm to segment images, based on the classification of pixels by means of an arbitrary neural network whose coefficients can be calculated by decomposing a matrix into singular values. We provide a demo posted on huggingface, and the respective theory.


Keywords: Segmentation, Image, Algorithm.

Introducción

La segmentación de una imagen digital (ver (Papers With Code | Image Segmentation, 2022)) es su división en partes con características distintivas determinadas. Esta tarea tiene múltiples aplicaciones en medicina (ver (Ronneberger ., 2015), (Ramesh ., 2021), (Liu ., 2021)), sensado remoto (ver (Kotaridis y Lazaridou, 2021) y (Jurado ., 2022)), control de tráfico vehícular (ver (L. Li ., 2018)), conteo de instancias (ver (Ren y Zemel, 2017) y (Waqas Zamir ., 2019)), y navegación de vehículos autónomos (ver (Treml ., 2016) y (Papadeas ., 2021)).

Además, es posible obtener diferentes tipos de resultado. En la tarea de segmentación semántica se diferencian clases de objetos (personas, autos, edificios, zonas geográficas, condiciones climáticas, etc), mediante la clasificación de pixeles de acuerdo a categorías y regiones de la imagen, pero no se diferencian instancias de objetos (ver el trabajo sobre imágenes médicas de (Ronneberger ., 2015) y el modelo de (Wang ., 2022)). En la tarea de segmentación por instancias (ver Wei . (2022) y (Ke ., 2021)), se busca distinguir distintos objetos dentro de una misma categoría. En la segmentación panóptica (ver (Kirillov ., 2019) y (Xiong ., 2019)), es posible distinguir entre diferentes clases e instancias y se unifican las tareas de segmentación semántica y de instancias.

En orden cronológico, tenemos diferentes algoritmos de segmentación: por agrupamiento (ver (Coleman y Andrews, 1979)), por "divisorias de aguas" (ver (Beucher, 1992)), por umbral (ver (Cheriet ., 1998)), por crecimiento de regiones (ver (Shih y Cheng, 2005)), por detección de bordes (ver (Muthukrishnan y Radha, 2011)), y con redes neurales profundas (deep learning neural networks) ((Badrinarayanan ., 2017), (Minaee ., 2021)).

Los algoritmos en uso actualmente, basados en redes neurales profundas, pueden consultarse en el sitio paperswithcode.com, en las páginas Papers with code | semantic segmentation (2022), Papers with code | instance segmentation (2022) y Papers with code | panoptic segmentation (2022). Si bien las publicaciones en cuestión obtienen resultados notables por su exactitud, llas implementaciones disponibles tienen una gran complejidad tanto en el tamaño de los datos necesarios (modelos de redes neurales) como en la teoría necesaria para entender su funcionamiento. Por el contrario, en este trabajo consideramos un algoritmo implementado en menos de $70$ líneas de python (empleando la librería numpy), basado en operaciones algebraicas básicas, y cuyos resultados, adecuados en la gran mayoría de las veces, sirven de línea de base para la verificación de otros métodos.

El algoritmo presentado aquí se basa en la clasificación de puntos en $\Re ^{n}$, definida como una función $f : \Re^{n} \times \{ v: v \in N, p \in N, 2 \leq v < p\}$.

Desarrollo

Consideremos las siguientes definiciones y convenciones:

1. Una clasificación es una función que operando sobre los elementos de un conjunto $X$, les asigna a cada uno de ellos un número o rótulo de clase $c \in N: 0 \leq c < C$, donde $C + 1$ es el número total de clases (contando la clase con el rótulo 0).
2. Simbolizamos los vectores columnas con letras minúsculas en negrita $\m{v}$, y los vectores fila o transpuestos $\m{v}^{t}$.
3. Simbolizamos las matrices con letras mayúsculas en negrita $\m{Z}$, y las matrices transpuestas $\m{Z}^{t}$.
4. Dada una matriz $\m{P}$ con $n$ filas y $m$ columnas, simbolizamos sus elementos $P_{i,j}$ (donde $0 \leq i < n$, $0 \leq j < m$), y sus columnas $\m{P}_{j}$. (Esta es la convención del índice inicial 0 para arreglos numéricos).
5. Denotamos las matrices unitarias $\m{I}_{r}$ donde $r$ indica la cantidad de $1$ en su diagonal.
6. El símbolo $\m{u}_{n}$ es el vector columna de $n$ elementos iguales a $1$.

Un método de clasificación de elementos de $\Re ^{n}$

Supongamos que disponemos de $m$ datos $\m{X}_{j} \in \Re^{n}$, y que construimos con ellos una matriz $\m{X} \in \Re^{n \times m}$. La descomposición en valores singulares (ver (Strang, 2016), capítulo 7) es una operación que nos permite obtener los factores matriciales $\m{U} \in \Re^{n \times n}$, $\m{S} \in \Re^{n \times n}$, $\m{V}^{t} \in \Re^{n \times m}$ de la matriz

$$\m{X} - \frac{\m{X} \cdot \m{u} \cdot \m{u}^{t}}{m} = \m{X} \cdot (\m{I}_{m} -\frac{\m{u} \cdot \m{u}^{t}}{m}) = \m{U} \cdot \m{S} \cdot \m{V}^{t},$$ (1)

donde $\m{u} \in \Re^{m}$, $u_{i} = 1, 0 \leq i < m$, e $\m{I}_{m}$ es la matriz unitaria $\in \Re^{m \times m}$. Además, $\m{U} \cdot \m{U}^{t} = \m{I}_{n}$, $\m{V}^{t} \cdot \m{V} = \m{I}_{n}$, y la matriz $\m{S}$ es diagonal positiva. Observemos que el factor $(\m{I}_{m} -\frac{\m{u}_{m} \cdot \m{u}_{m}^{t}}{m})$ tiene al menos un autovalor nulo, dado que

$$(\m{I}_{m} -\frac{\m{u}_{m} \cdot \m{u}_{m}^{t}}{m}) \cdot \m{u} ... ...frac{\m{u}^{t} \cdot \m{u}}{m} = \m{u} - \m{u} \, \frac{m}{m} = \m{0} \, \m{u}.$$ (2)

Podemos construir una clasificación arbitraria de $\m{X}$ mediante los siguientes pasos

1. Transformación de $\m{X}$: definimos

   $$\m{H} = \m{S}_{r}^{-1} \cdot \m{U}^{t} \cdot \m{X} \cdot \left(\m{I}_{m} -\frac{\m{u} \cdot \m{u}^{t}}{m}\right) = \m{V}_{r}^{t},$$ (3)

   donde $\m{V}_{r}^{t} \in \Re^{r \times m}$ contiene las filas de $\m{V}_{t}$ correspondientes a los $r$ autovalores más significativos de $\m{S}$, y $\m{S}_{r}$ contiene los $r$ autovalores más significativos de $\m{S}$.
2. Normalización de $\m{H}$: Definimos $\m{F}$ como una función lineal de $\m{H}$ de forma tal que

   $$\delta \leq F_{i, j} \leq 1 - \delta, \qquad 0 < \delta < \frac{1}{2},$$ (4)

   $$F_{i, j} = m \, H_{i, j} + b,$$ (5)

   $$m = \frac{(1 - 2 \, \delta)}{max(\m{H}) - min(\m{H})}$$ (6)

   y

   $$b = \frac{1 - \delta - m \, max(\m{H})}{m}.$$ (7)

3. Cuantización de $\m{F}$: dado un parámetro entero $2 \leq \alpha$, calculamos los dígitos en base $\alpha$

   $$G_{i, j} = \lfloor \alpha \times F_{i,j} \rfloor,$$ (8)

   donde $\lfloor x \rfloor = max\{m \in \ \mathbb{Z} \vert m < x\}$, $x \in \Re$ es la función parte entera de $x$.

4. Clasificación: finalmente calculamos los rótulos de las clases asociadas a cada $\m{X}_{j}$ como el producto

   $$\m{c} = \m{w}^{t} \cdot \m{G},$$ (9)

   donde $w_{i} = \alpha^{n-1-i}$, para $0 \leq i < n$ y

   $$0 \leq c_{j} = \sum_{i=0}^{n-1} \alpha^{n-1-i} \, G_{i,j} \leq \s... ... 1 ) \, \frac{1 - \frac{1}{\alpha^{n}}}{1 - \frac{1}{\alpha}} = \alpha^{n} - 1.$$ (10)

El parámetro $\alpha$ determina la resolución de la clasificación (la cantidad de clases) como vemos en la ecuación 10. Si bien $\alpha$ puede ser cualquier número entero mayor o igual a $2$, el uso de números primos ( $3, 5, 7, 11, ...$) evita que los límites de clases de resoluciones diferentes coincidan.

Segmentación de imágenes

Las imágenes digitales tomadas con cámaras comerciales son arreglos numéricos agrupados en tres o cuatro matrices, que denominamos $\m{R}$, $\m{G}$, $\m{B}$, y $\m{A}$, con números enteros positivos $T = {x: 0 \leq x \leq 255}$, de $h$ filas y $w$ columnas. Las matrices $\m{R}$, $\m{G}$ y $\m{B}$ contienen información sobre la intensidad de los colores Red (rojo), Green (verde) y Blue (azul) que componen un punto de color o pixel. Cuando está presente, la matriz $\m{A}$ da información sobre la transparencia del pixel.

Definamos el pixel de la posición $(k, l)$ en la imagen, $0 \leq k < h$, $0 \leq l < w$, como la columna $\m{P}_{j}$, $j = k \times w + l$

$$\m{P}_{j} = \left[ \begin{array}{c} R_{k, l} \\ G_{k, l} \\ B_{k, l} \end{array} \right],$$ (11)

de una matriz $\m{P} \in T^{3 \times (h \times w)}$ o

$$\m{P}_{j} = \left[ \begin{array}{c} R_{k, l} \\ G_{k, l} \\ B_{k, l} \\ A_{k, l} \end{array} \right],$$ (12)

de una matriz $\m{P} \in T^{4 \times (h \times w)}$ según dispongamos o no de la matriz $\m{A}$.

Aplicamos el algoritmo de clasificación a la matriz $\m{P}$, con una resolución $2 \leq \alpha$ para obtener un vector $\m{c}^{t}$ con las clases de cada columna. Dado que conociendo $j$ y $w$ podemos calcular

$$l = mod(j, h), \qquad k = (j - l) // h,$$ (13)

donde $mod$ es la función que nos da el resto de la división de números enteros $//$, es inmediato asignar la clase correspondiente a cada pixel de la imagen original. Asi, podemos generar dos resultados diferentes

1. Mosaico: Una estructura de datos con una matriz en $[0, 1]^{n \times m}$ por clase,

   $$\begin{array}{c} j = k \times w + l, \\ c_{j} = p \rightarro... ..., \\ c_{j} \neq p \rightarrow \m{K}_{k, l, p} = 0. \end{array}$$ (14)

2. Imagen comprimida: los diferentes pixeles de cada clase son reemplazadas por un único pixel.

Este método de segmentación es una versión modificada de los propuestos en (Coleman y Andrews, 1979), basados en la determinación de grupos de pixeles mediante algoritmos de agrupamiento, según (Bell, 1966) y (Sinaga y Yang, 2020), y cuya complejidad en tiempo es NP Hard ((Mahajan ., 2009)). Dado que la complejidad temporal de los algoritmos de cálculo de descomposición en valores singulares es polinomial respecto al producto de las dimensiones de la matriz, cabe esperar una mejora en los tiempos de procesamiento (ver (X. Li ., 2019)).

Implementación

La implementación y una demostración en línea del algoritmo de segmentación está disponible en (Berns, 2022). Los programas están escritos en python, usando la librería numpy para el cálculo de la descomposición de valores singulares de una matriz, y la librería gradio para la interfase web. Como se puede ver en el sitio, se puede elegir el parámetro $\alpha$, y el tipo de resultado (vista en mosaico, o imagen simplificada). Se ha fijado el valor $\delta = 0.001$. En la solapa con el rótulo "Files" podemos ver todos los archivos de python con la implementación de la propuesta. Si bien la aplicación web tal como está publicada en https://huggingface.co/spaces/DWB1962/svd_codes puede generar imágenes comprimidas, es preferible emplear el archivo compress.py ejecutado en forma local para una comparación justa, donde los archivos tienen el mismo formato y la misma cantidad de pixeles.

A continuación vemos las imágenes 1, 2 y 3, con los valores de parámetros $\alpha = 13$ y $\delta = 0.001$ (fijo en el programa).

Figura 1: Imagen original, tamaño 1654493 bytes.

Figura 2: Mosaico, $\alpha = 13$.

Figura 3: Imagen comprimida, $\alpha = 13$, tamaño 91498 bytes.

Conclusiones

Hemos presentado un algoritmo para segmentación de imágenes, basado en una clasificación arbitraria de pixeles determinada por la descomposición de valores singulares de una matriz. En base a los resultados obtenidos, es posible comprimir significativamente una imagen en la mayoría de los casos. Se ha publicado la implementación junto con una demostración en línea en el sitio huggingface (ver (Berns, 2022)). Existen algoritmos con mejor desempeño, basados en redes neurales, cuyos artículos e implementaciones pueden consultarse en las páginas Papers with code | semantic segmentation (2022), Papers with code | instance segmentation (2022) y Papers with code | panoptic segmentation (2022). Sin embargo, creemos que este trabajo muestra la posibilidad de obtener resultados alternativos con programas más sencillos (en cantidad de líneas y librerías usadas).

Bibliografía

Badrinarayanan, V., Kendall, A., y Cipolla, R. (2017). Segnet: A deep convolutional encoder-
decoder architecture for image segmentation. IEEE transactions on pattern analysis and machine
intelligence, 39 (12), 2481–2495.

Bell, G. H. (1966). A comparison of some cluster-seeking techniques. (Inf. Téc.). STANFORD
RESEARCH INST MENLO PARK CALIF.

Berns, D. W. (2022). Huggingface | svdcodes. https://bit.ly/3gMAWO7. ((último acceso en
2022-10-25))

Beucher, S. (1992). The watershed transformation applied to image segmentation. Scanning
Microscopy, 1992 (6), 28.

Cheriet, M., Said, J. N., y Suen, C. Y. (1998). A recursive thresholding technique for image
segmentation. IEEE transactions on image processing, 7 (6), 918–921.

Coleman, G. B., y Andrews, H. C. (1979). Image segmentation by clustering. Proceedings of the
IEEE, 67 (5), 773–785.

Jurado, J. M., López, A., Pádua, L., y Sousa, J. J. (2022). Remote sensing image fusion on 3d scenarios: A review of applications for agriculture and forestry.  International Journal of Applied Earth Observation and Geoinformation, 112 , 102856.  Descargado de https://www.sciencedirect.com/science/article/pii/S1569843222000589 doi: https://doi.org/10.1016/j.jag.2022.102856

Ke, L., Tai, Y.-W., y Tang, C.-K. (2021). Deep occlusion-aware instance segmentation with overlap-
ping bilayers. En Proceedings of the ieee/cvf conference on computer vision and pattern recognition (pp. 4019–4028).

Kirillov, A., He, K., Girshick, R., Rother, C., y Dollár, P. (2019). Panoptic segmentation. En
Proceedings of the ieee/cvf conference on computer vision and pattern recognition (pp. 9404–
9413).

Kotaridis, I., y Lazaridou, M. (2021). Remote sensing image segmentation advances: A meta-
analysis. ISPRS Journal of Photogrammetry and Remote Sensing, 173 , 309–322.

Li, L., Qian, B., Lian, J., Zheng, W., y Zhou, Y. (2018). Traffic scene segmentation based on rgb-
d image and deep learning. IEEE Transactions on Intelligent Transportation Systems, 19 (5),
1664-1669. doi: 10.1109/TITS.2017.2724138

Li, X., Wang, S., y Cai, Y. (2019). Tutorial: Complexity analysis of singular value decomposition
and its variants. arXiv preprint arXiv:1906.12085 .

Liu, X., Song, L., Liu, S., y Zhang, Y. (2021). A review of deep-learning-based medical image
segmentation methods. Sustainability, 13 (3), 1224.

Mahajan, M., Nimbhorkar, P., y Varadarajan, K. (2009). The planar k-means problem is np-hard.
En International workshop on algorithms and computation (pp. 274–285).

Minaee, S., Boykov, Y. Y., Porikli, F., Plaza, A. J., Kehtarnavaz, N., y Terzopoulos, D. (2021).
Image segmentation using deep learning: A survey. IEEE transactions on pattern analysis and
machine intelligence.

Muthukrishnan, R., y Radha, M. (2011). Edge detection techniques for image segmentation.
International Journal of Computer Science & Information Technology, 3 (6), 259.

Papadeas, I., Tsochatzidis, L., Amanatiadis, A., y Pratikakis, I. (2021). Real-time semantic image
segmentation with deep learning for autonomous driving: A survey. Applied Sciences, 11 (19),
8802.

Papers with code | image segmentation. (2022). https://bit.ly/3sBdNkp. ((último acceso en
2022-10-25))

Papers with code | instance segmentation. (2022). https://bit.ly/3TXr1Dx. ((último acceso en
2022-10-25))

Papers with code | panoptic segmentation. (2022). https://bit.ly/3SUayzn. ((último acceso en
2022-10-25))

Papers with code | semantic segmentation. (2022). https://bit.ly/3N9lho4. ((último acceso en
2022-10-25))

Ramesh, K., Kumar, G. K., Swapna, K., Datta, D., y Rajest, S. S. (2021). A review of medical image segmentation algorithms. EAI Endorsed Transactions on Pervasive Health and Technology,
7 (27), e6–e6.

Ren, M., y Zemel, R. S. (2017, July). End-to-end instance segmentation with recurrent attention.
En Proceedings of the ieee conference on computer vision and pattern recognition (cvpr).

Ronneberger, O., Fischer, P., y Brox, T. (2015). U-net: Convolutional networks for biomedical image
segmentation. En International conference on medical image computing and computer-assisted
intervention (pp. 234–241).

Shih, F. Y., y Cheng, S. (2005). Automatic seeded region growing for color image segmentation.
Image and vision computing, 23 (10), 877–886.

Sinaga, K. P., y Yang, M.-S. (2020). Unsupervised k-means clustering algorithm. IEEE access, 8 ,
80716–80727.

Strang, G. (2016). Introduction to linear algebra. Wellesley-Cambridge Press. Descargado de
https://books.google.com.ar/books?id=efbxjwEACAAJ

Treml, M., Arjona-Medina, J., Unterthiner, T., Durgesh, R., Friedmann, F., Schuberth, P., . . .
others (2016). Speeding up semantic segmentation for autonomous driving.

Wang, W., Bao, H., Dong, L., Bjorck, J., Peng, Z., Liu, Q., . . . others (2022). Image as a foreign lan-
guage: Beit pretraining for all vision and vision-language tasks. arXiv preprint arXiv:2208.10442 .

Waqas Zamir, S., Arora, A., Gupta, A., Khan, S., Sun, G., Shahbaz Khan, F., . . . Bai, X. (2019).
isaid: A large-scale dataset for instance segmentation in aerial images. En Proceedings of the
ieee/cvf conference on computer vision and pattern recognition workshops (pp. 28–37).

Wei, Y., Hu, H., Xie, Z., Zhang, Z., Cao, Y., Bao, J., . . . Guo, B. (2022). Contrastive learning rivals
masked image modeling in fine-tuning via feature distillation. arXiv preprint arXiv:2205.14141 .

Xiong, Y., Liao, R., Zhao, H., Hu, R., Bai, M., Yumer, E., y Urtasun, R. (2019). Upsnet: A unified
panoptic segmentation network. En Proceedings of the ieee/cvf conference on computer vision
and pattern recognition (pp. 8818–8826).