stringtranslate.com

El método de Otsu

Una imagen de ejemplo umbralizada utilizando el algoritmo de Otsu
Imagen original

En la visión artificial y el procesamiento de imágenes , el método de Otsu , llamado así por Nobuyuki Otsu (大津展之, Ōtsu Nobuyuki ) , se utiliza para realizar el umbralizado automático de imágenes . [1] En la forma más simple, el algoritmo devuelve un único umbral de intensidad que separa los píxeles en dos clases, primer plano y fondo. Este umbral se determina minimizando la varianza de intensidad intraclase o, equivalentemente, maximizando la varianza interclase. [2] El método de Otsu es un análogo discreto unidimensional del análisis discriminante de Fisher , está relacionado con el método de optimización de Jenks y es equivalente a una k-media globalmente óptima [3] realizada en el histograma de intensidad. La extensión al umbralizado multinivel se describió en el artículo original [2] y desde entonces se han propuesto implementaciones computacionalmente eficientes. [4] [5]

El método de Otsu

Visualización del método de Otsu

El algoritmo busca exhaustivamente el umbral que minimiza la varianza intraclase, definida como una suma ponderada de las varianzas de las dos clases:

Los pesos y son las probabilidades de las dos clases separadas por un umbral , y y son las varianzas de estas dos clases.

La probabilidad de clase se calcula a partir de los intervalos del histograma:

Para 2 clases, minimizar la varianza intraclase es equivalente a maximizar la varianza interclase: [2]

que se expresa en términos de probabilidades de clase y medias de clase , donde las medias de clase , y son:

Las siguientes relaciones se pueden verificar fácilmente:

Las probabilidades y medias de las clases se pueden calcular de forma iterativa. Esta idea produce un algoritmo eficaz.

Algoritmo

  1. Calcular histograma y probabilidades de cada nivel de intensidad
  2. Configurar inicial y
  3. Pasar por todos los umbrales posibles de máxima intensidad
    1. Actualizar y
    2. Calcular
  4. El umbral deseado corresponde al máximo

Implementación de MATLAB

histogramCountses un histograma de 256 elementos de una imagen en escala de grises con diferentes niveles de gris (típicos para imágenes de 8 bits). leveles el umbral de la imagen (doble).

función  nivel = otsu ( histogramCounts ) total = suma ( histogramCounts ); % número total de píxeles en la imagen %% Umbral automático de OTSU top = 256 ; sumaB = 0 ; wB = 0 ; máximo = 0.0 ; suma1 = punto ( 0 : top - 1 , histogramCounts ); para ii = 1 : top wF = total - wB ; si wB > 0 && wF > 0 mF = ( suma1 - sumaB ) / wF ; val = wB * wF * (( sumaB / wB ) - mF ) * (( sumaB / wB ) - mF ); si ( val >= máximo ) nivel = ii ; máximo = val ; fin fin wB = wB + histogramCounts ( ii ); sumaB = sumaB + ( ii - 1 ) * histogramCounts ( ii ); fin fin                                                                                  

Matlab tiene funciones integradas graythresh()en multithresh()la caja de herramientas de procesamiento de imágenes que se implementan con el método de Otsu y el método Multi Otsu, respectivamente.

Implementación de Python

Esta implementación requiere la biblioteca NumPy .

importar  numpy  como  npdef  otsu_intraclass_variance ( image ,  threshold ): """ Varianza  intraclase de Otsu. Si todos los píxeles están por encima o por debajo del  umbral, esto lanzará una advertencia que puede ignorarse de forma segura.  """ return np.nansum ( [ np.mean ( cls ) * np.var ( image , where = cls ) # weight · intra-class variance for cls in [ image >= threshold , image < threshold ] ] ) # Los NaN solo surgen si la clase está vacía, en cuyo caso la contribución debe ser cero, lo que `nansum` logra.                     # Imagen aleatoria para demostración: image  =  np . random . randint ( 2 ,  253 ,  size = ( 50 ,  50 ))otsu_threshold  =  min (  rango ( np . min ( imagen )  +  1 ,  np . max ( imagen )),  clave = lambda  th :  otsu_intraclass_variance ( imagen ,  th ), )

Las bibliotecas de Python dedicadas al procesamiento de imágenes, como OpenCV y Scikit-image, proponen implementaciones integradas del algoritmo.

Limitaciones y variaciones

El método de Otsu funciona bien cuando el histograma tiene una distribución bimodal con un valle profundo y pronunciado entre los dos picos. [6]

Al igual que todos los demás métodos de umbralización global, el método de Otsu funciona mal en caso de mucho ruido, objetos de tamaño pequeño, iluminación no homogénea y una varianza intraclase mayor que interclase. [7] En esos casos, se han desarrollado adaptaciones locales del método de Otsu. [8]

Además, la base matemática del método de Otsu modela el histograma de la imagen como una mezcla de dos distribuciones normales con varianza igual y tamaño igual. [9] Sin embargo, el umbral de Otsu puede producir resultados satisfactorios incluso cuando no se cumplen estos supuestos, de la misma manera que las pruebas estadísticas (a las que el método de Otsu está estrechamente relacionado [10] ) pueden funcionar correctamente incluso cuando los supuestos de trabajo no se satisfacen por completo.

Se han propuesto varias variaciones de los métodos de Otsu para tener en cuenta las desviaciones más severas de estos supuestos, [9] como el método Kittler-Illingworth. [11]

Una variación para imágenes ruidosas

Una adaptación local popular es el método bidimensional de Otsu , que funciona mejor para la tarea de segmentación de objetos en imágenes ruidosas. Aquí, el valor de intensidad de un píxel determinado se compara con la intensidad promedio de su entorno inmediato para mejorar los resultados de la segmentación. [8]

En cada píxel se calcula el valor medio del nivel de gris del entorno. Supongamos que el nivel de gris del píxel dado se divide en valores discretos y que el nivel de gris medio también se divide en los mismos valores. Entonces se forma un par: el nivel de gris del píxel y el promedio del entorno . Cada par pertenece a uno de los posibles contenedores bidimensionales. El número total de ocurrencias (frecuencia), , de un par , dividido por el número total de píxeles en la imagen , define la función de masa de probabilidad conjunta en un histograma bidimensional:

Y el método de Otsu bidimensional se desarrolla basándose en el histograma bidimensional de la siguiente manera.

Las probabilidades de dos clases se pueden denotar como:

Los vectores de valor medio de intensidad de dos clases y el vector medio total se pueden expresar de la siguiente manera:

En la mayoría de los casos la probabilidad de que se salga de la diagonal será insignificante, por lo que es fácil verificarlo:

La matriz discreta entre clases se define como

La traza de la matriz discreta se puede expresar como

dónde

De manera similar al método unidimensional de Otsu, el umbral óptimo se obtiene maximizando .

Algoritmo

El y se obtiene de forma iterativa, lo que es similar al método unidimensional de Otsu. Los valores de y se modifican hasta obtener el máximo de , es decir

máx , s , t = 0 ;  para ss : 0 a L - 1 hacer para tt : 0 a L - 1 hacer evaluar tr ( S_b ); si tr ( S_b ) > max max = tr ( S , b ); s = ss ; t = tt ; fin si fin para fin para                               devuelve s , t ; 

Tenga en cuenta que para evaluar , podemos utilizar un algoritmo de programación dinámica recursiva rápida para mejorar el rendimiento temporal. [12] Sin embargo, incluso con el enfoque de programación dinámica, el método de Otsu 2d aún tiene una gran complejidad temporal. Por lo tanto, se han realizado muchas investigaciones para reducir el costo computacional. [13]

Si se utilizan tablas de área sumadas para construir las 3 tablas, suma sobre , suma sobre , y suma sobre , entonces la complejidad en tiempo de ejecución es el máximo de (O(N_pixels), O(N_bins*N_bins)). Tenga en cuenta que si solo se necesita una resolución gruesa en términos de umbral, se puede reducir N_bins.

Implementación de MATLAB

Entradas y salidas de funciones:

histses un histograma 2D del valor de escala de grises y el par de valores de escala de grises promedio del vecindario.

totales el número de pares en la imagen dada. Está determinado por el número de contenedores del histograma 2D en cada dirección.

thresholdes el umbral obtenido.

función  umbral = otsu_2D ( hist, total ) máximo = 0.0 ; umbral = 0 ; helperVec = 0 : 255 ; mu_t0 = suma ( suma ( repmat ( helperVec ' , 1 , 256 ) .* hist )); mu_t1 = suma ( suma ( repmat ( helperVec , 256 , 1 ) .* hist )); p_0 = ceros ( 256 ); mu_i = p_0 ; mu_j = p_0 ; para ii = 1 : 256 para jj = 1 : 256 si jj == 1 si ii == 1 p_0 ( 1 , 1 ) = hist ( 1 , 1 ); else p_0 ( ii , 1 ) = p_0 ( ii - 1 , 1 ) + hists ( ii , 1 ); mu_i ( ii , 1 ) = mu_i ( ii - 1 , 1 ) + ( ii - 1 ) * hists ( ii , 1 ); mu_j ( ii , 1 ) = mu_j ( ii - 1 , 1 ); fin más p_0 ( ii , jj ) = p_0 ( ii , jj - 1 ) + p_0 ( ii - 1 , jj ) - p_0 (                                                     ii - 1 , jj - 1 ) + hists ( ii , jj ); % AQUÍ HAY UN ERROR. LOS ÍNDICES EN MATLAB DEBEN SER MAYORES A 0. ii-1 no es válido mu_i ( ii , jj ) = mu_i ( ii , jj - 1 ) + mu_i ( ii - 1 , jj ) - mu_i ( ii - 1 , jj - 1 ) + ( ii - 1 ) * hists ( ii , jj ); mu_j ( ii , jj ) = mu_j ( ii , jj - 1 ) + mu_j ( ii - 1 , jj ) - mu_j ( ii - 1 , jj - 1 ) + ( jj - 1 ) * hists ( ii , jj ); fin         si ( p_0 ( ii , jj ) == 0 ) continuar ; terminar si ( p_0 ( ii , jj ) == total ) romper ; fin tr = (( mu_i ( ii , jj ) - p_0 ( ii , jj ) * mu_t0 ) ^ 2 + ( mu_j ( ii , jj ) - p_0 ( ii , jj ) * mu_t1 ) ^ 2 ) / ( p_0 ( ii , jj ) * ( 1 - p_0 ( ii , jj )));                 si ( tr >= máximo ) umbral = ii ; máximo = tr ; fin fin fin fin             

Una variación para imágenes desequilibradas

Cuando los niveles de gris de las clases de la imagen pueden considerarse como distribuciones normales pero con tamaños desiguales y/o varianzas desiguales, no se cumplen los supuestos del algoritmo de Otsu. El algoritmo Kittler-Illingworth (también conocido como umbralización de error mínimo) [11] es una variación del método de Otsu para manejar tales casos. Existen varias formas de describir matemáticamente este algoritmo. Una de ellas es considerar que para cada umbral que se prueba, los parámetros de las distribuciones normales en la imagen binaria resultante se estiman mediante la estimación de máxima verosimilitud dados los datos. [9]

Si bien este algoritmo puede parecer superior al método de Otsu, introduce nuevos parámetros que deben estimarse, lo que puede provocar que el algoritmo esté sobreparametrizado y, por lo tanto, sea inestable. En muchos casos en los que las suposiciones del método de Otsu parecen al menos parcialmente válidas, puede ser preferible favorecer el método de Otsu sobre el algoritmo de Kittler-Illingworth, siguiendo la navaja de Occam . [9]

El umbral de triclase divide tentativamente el histograma de una imagen en tres clases; la clase TBD se procesará en las siguientes iteraciones.

Umbralización iterativa de tres clases basada en el método de Otsu

Una limitación del método de Otsu es que no puede segmentar objetos débiles ya que el método busca un único umbral para separar una imagen en dos clases, es decir, primer plano y fondo, en una sola toma. Debido a que el método de Otsu busca segmentar una imagen con un umbral, tiende a sesgar hacia la clase con la gran varianza. [14] El algoritmo iterativo de umbralización de triclase es una variación del método de Otsu para eludir esta limitación. [15] Dada una imagen, en la primera iteración, el algoritmo de umbralización de triclase calcula un umbral utilizando el método de Otsu. Basándose en el umbral , el algoritmo calcula la media de los píxeles por encima y la media de los píxeles por debajo . Luego, el algoritmo separa tentativamente la imagen en tres clases (de ahí el nombre triclase), con los píxeles por encima de la media superior designados como la clase de primer plano temporal y los píxeles por debajo de la media inferior designados como la clase de fondo temporal. Los píxeles que caen entre se denotan como una región por determinar (TBD). Esto completa la primera iteración del algoritmo. Para la segunda iteración, el método de Otsu se aplica solo a la región TBD para obtener un nuevo umbral . A continuación, el algoritmo calcula la media de los píxeles de la región TBD que están por encima y la media de los píxeles de la región TBD que están por debajo . Los píxeles de la región TBD que son mayores que la media superior se añaden al primer plano temporal . Y los píxeles de la región TBD que son menores que la media inferior se añaden al fondo temporal . De forma similar, se obtiene una nueva región TBD, que contiene todos los píxeles que se encuentran entre . Esto completa la segunda iteración. A continuación, el algoritmo procede a la siguiente iteración para procesar la nueva región TBD hasta que cumpla el criterio de detención. El criterio es que, cuando la diferencia entre los umbrales de Otsu calculados a partir de dos iteraciones consecutivas es menor que un número pequeño, la iteración se detendrá. Para la última iteración, los píxeles por encima se asignan a la clase de primer plano y los píxeles por debajo del umbral se asignan a la clase de fondo. Al final, todos los píxeles temporales del primer plano se combinan para formar el primer plano final. Todos los píxeles temporales del fondo se combinan para formar el fondo final. En la implementación, el algoritmo no involucra ningún parámetro excepto el criterio de detención para finalizar las iteraciones. Al aplicar iterativamente el método de Otsu y reducir gradualmente la región TBD para la segmentación, el algoritmo puede obtener un resultado que preserva los objetos débiles mejor que el método de Otsu estándar.

Referencias

  1. ^ M. Sezgin y B. Sankur (2004). "Estudio sobre técnicas de umbralización de imágenes y evaluación cuantitativa del rendimiento". Journal of Electronic Imaging . 13 (1): 146–165. Bibcode :2004JEI....13..146S. doi :10.1117/1.1631315.
  2. ^ abc Nobuyuki Otsu (1979). "Un método de selección de umbral a partir de histogramas de niveles de gris". IEEE Transactions on Systems, Man, and Cybernetics . 9 (1): 62–66. doi :10.1109/TSMC.1979.4310076. S2CID  15326934.
  3. ^ Liu, Dongju (2009). "Método Otsu y K-means". Novena Conferencia Internacional sobre Sistemas Inteligentes Híbridos IEEE . 1 : 344–349.
  4. ^ Liao, Ping-Sung (2001). "Un algoritmo rápido para el umbral multinivel" (PDF) . J. Inf. Sci. Eng . 17 (5): 713–727. doi :10.6688/JISE.2001.17.5.1. S2CID  9609430. Archivado desde el original (PDF) el 24 de junio de 2019.
  5. ^ Huang, Deng-Yuan (2009). "Umbralización multinivel óptima utilizando un enfoque de optimización Otsu de dos etapas". Pattern Recognition Letters . 30 (3): 275–284. Código Bibliográfico :2009PaReL..30..275H. doi :10.1016/j.patrec.2008.10.003.
  6. ^ Kittler, J.; Illingworth, J. (septiembre de 1985). "Sobre la selección de umbrales utilizando criterios de agrupamiento". IEEE Transactions on Systems, Man, and Cybernetics . SMC-15 (5): 652–655. doi :10.1109/tsmc.1985.6313443. ISSN  0018-9472. S2CID  30272350.
  7. ^ Lee, Sang Uk y Chung, Seok Yoon y Park, Rae Hong (1990). "Un estudio comparativo del rendimiento de varias técnicas de umbralización global para segmentación". Visión artificial, gráficos y procesamiento de imágenes . 52 (2): 171–190. doi :10.1016/0734-189x(90)90053-x.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  8. ^ ab Jianzhuang, Liu y Wenqing, Li y Yupeng, Tian (1991). "Umbral automático de imágenes en niveles de gris utilizando el método Otsu bidimensional". Circuits and Systems, 1991. Actas de congresos, China., 1991 International Conference on : 325–327.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  9. ^ abcd Kurita, T.; Otsu, N.; Abdelmalek, N. (octubre de 1992). "Umbral de máxima verosimilitud basado en modelos de mezcla de poblaciones". Reconocimiento de patrones . 25 (10): 1231–1240. Bibcode :1992PatRe..25.1231K. doi :10.1016/0031-3203(92)90024-d. ISSN  0031-3203.
  10. ^ Jing-Hao Xue; Titterington, DM (agosto de 2011). "Pruebas t, pruebas F y métodos de Otsu para umbralización de imágenes". IEEE Transactions on Image Processing . 20 (8): 2392–2396. doi :10.1109/tip.2011.2114358. ISSN  1057-7149. PMID  21324779. S2CID  10561633.
  11. ^ ab Kittler, J.; Illingworth, J. (1986-01-01). "Umbral de error mínimo". Reconocimiento de patrones . 19 (1): 41–47. Bibcode :1986PatRe..19...41K. doi :10.1016/0031-3203(86)90030-0. ISSN  0031-3203.
  12. ^ Zhang, Jun y Hu, Jinglu (2008). "Segmentación de imágenes basada en el método Otsu 2D con análisis de histograma". Conferencia internacional de 2008 sobre ciencias de la computación e ingeniería de software . Vol. 6. págs. 105–108. doi :10.1109/CSSE.2008.206. ISBN 978-0-7695-3336-0. Número de identificación del sujeto  14982308.
  13. ^ Zhu, Ningbo y Wang, Gang y Yang, Gaobo y Dai, Weiming (2009). "Un algoritmo de umbralización otsu 2d rápido basado en un histograma mejorado". Reconocimiento de patrones, 2009. CCPR 2009. Conferencia china sobre : 1–5.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  14. ^ Xu, Xiangyang, Xu, Shengzhou, Jin, Lianghai y Song, Enmin (2011). "Análisis característico del umbral de Otsu y sus aplicaciones". Pattern Recognition Letters . 32 (7): 956–61. Código Bibliográfico :2011PaReL..32..956X. doi :10.1016/j.patrec.2011.01.021.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  15. ^ Cai, Hongmin, Yang, Zhong, Cao, Xinhua, Xia, Weiming y Xu, Xiaoyin. (2014). "Una nueva técnica iterativa de umbralización triclasa en la segmentación de imágenes". IEEE Transactions on Image Processing . 23 (3): 1038–46. doi :10.1109/TIP.2014.2298981. PMID  24474373. S2CID  2242995.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Enlaces externos