stringtranslate.com

El método de Otsu

Una imagen de ejemplo con umbral utilizando el algoritmo de Otsu
Imagen original

En visión por computadora y procesamiento de imágenes , el método de Otsu , que lleva el nombre de Nobuyuki Otsu (大津展之, Ōtsu Nobuyuki ) , se utiliza para realizar umbrales automáticos de imágenes . [1] En la forma más simple, el algoritmo devuelve un umbral de intensidad único que separa los píxeles en dos clases, primer plano y fondo. Este umbral se determina minimizando la variación de intensidad intraclase o, de manera equivalente, maximizando la variación entre clases. [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 umbral 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 son las variaciones de estas dos clases.

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

Para 2 clases, minimizar la variación intraclase equivale a maximizar la variación entre clases: [2]

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

Las siguientes relaciones se pueden verificar fácilmente:

Las probabilidades de clase y las medias de clase 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. Pasa por todos los umbrales posibles de máxima intensidad.
    1. Actualizar y
    2. Calcular
  4. El umbral deseado corresponde al máximo

implementaciónMATLAB

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

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

Matlab tiene funciones integradas graythresh()y multithresh()en Image Processing Toolbox 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 ( imagen ,  umbral ): """  Variación intraclase de Otsu.  Si todos los píxeles están por encima o por debajo del umbral, se generará una advertencia que se puede ignorar con seguridad.  """ return np . nansum ( [ np . mean ( cls ) * np . var ( imagen , donde = cls ) # peso · varianza intraclase para cls en [ imagen > = umbral , imagen < umbral ] ] ) # Los NaN solo surgen si la clase es vacío, en cuyo caso la contribución debe ser cero, lo que logra "nansum".                     # Imagen aleatoria para demostración: image  =  np . aleatorio . randint ( 2 ,  253 ,  tamaño = ( 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]

Como todos los demás métodos de umbral global, el método de Otsu funciona mal en caso de mucho ruido, tamaños de objetos pequeños, iluminación no homogénea y una variación intraclase mayor que entre clases. [7] En esos casos, se han desarrollado adaptaciones locales del método 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 igual varianza e igual tamaño. [9] Sin embargo, el umbral de Otsu puede producir resultados satisfactorios incluso cuando estos supuestos no se cumplen, de la misma manera que las pruebas estadísticas (a las que el método de Otsu está fuertemente relacionado [10] ) pueden funcionar correctamente incluso cuando los supuestos de trabajo no se satisfacen completamente.

Se han propuesto varias variaciones de los métodos de Otsu para dar cuenta de desviaciones más severas de estos supuestos, [9] como el método de 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 vecindario inmediato para mejorar los resultados de la segmentación. [8]

En cada píxel, se calcula el valor promedio del nivel de gris de la vecindad. Divida el nivel de gris del píxel dado en valores discretos y el nivel de gris promedio también se divida en los mismos valores. Luego se forma un par: el nivel de gris del píxel y el promedio de la vecindad . Cada par pertenece a uno de los posibles contenedores bidimensionales. El número total de apariciones (frecuencia) , de un par , dividido por el número total de píxeles de 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 fuera de la diagonal será insignificante, por lo que es fácil de verificar:

La matriz discreta entre clases se define como

La traza de la matriz discreta se puede expresar como

dónde

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

Algoritmo

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

máx , s , t = 0 ;  para ss : 0 a L - 1 haga para tt : 0 a L - 1 evalúe tr ( S_b ) ; si tr ( S_b ) > máx máx = tr ( S , b ); s = ss ; t = tt ; terminar si terminar por terminar por                               devolver s , t ; 

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

Si se utilizan tablas de áreas sumadas para crear las 3 tablas, suma sobre , suma sobre y suma sobre , entonces la complejidad del 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 aproximada en términos de umbral, se pueden reducir N_bins.

implementaciónMATLAB

entradas y salidas de funciones:

histses un histograma 2D del par de valor de escala de grises y valor de escala de grises promedio de vecindad.

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.

 umbral de función = otsu_2D ( hists, total ) máximo = 0,0 ; umbral = 0 ; ayudanteVec = 0 : 255 ; mu_t0 = suma ( suma ( repmat ( helperVec ' , 1 , 256 ) .* hists )); mu_t1 = suma ( suma ( repmat ( helperVec , 256 , 1 ) .* hists )); 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 ) = hists ( 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 ); % HAY UN ERROR AQUÍ. LOS ÍNDICES EN MATLAB DEBEN SER SUPERIORES 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 )));                 if ( 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ño desigual y/o varianzas desiguales, no se cumplen los supuestos para el algoritmo de Otsu. El algoritmo de Kittler-Illingworth (también conocido como umbral de error mínimo) [11] es una variación del método de Otsu para manejar estos casos. Hay 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 estimación de máxima verosimilitud dados los datos. [9]

Si bien este algoritmo podría parecer superior al método de Otsu, introduce nuevos parámetros a estimar, y esto puede dar como resultado 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 tres clases divide tentativamente el histograma de una imagen en tres clases, y la clase TBD se procesará en las próximas iteraciones.

Umbral iterativo de tres clases basado 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 umbral único 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 sesgarse hacia la clase con mayor variación. [14] El algoritmo iterativo de umbral triclase es una variación del método de Otsu para sortear esta limitación. [15] Dada una imagen, en la primera iteración, el algoritmo de umbral triclase calcula un umbral utilizando el método de Otsu. Según el umbral , el algoritmo calcula la media de los píxeles superiores y la media de los píxeles inferiores . 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 se encuentran entre ellos se denominan 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 a la región TBD solo para obtener un nuevo umbral . Luego, el algoritmo calcula la media de los píxeles de la región TBD que están arriba y la media de los píxeles de la región TBD que están debajo . Los píxeles de la región TBD que son mayores que la media superior se agregan al primer plano temporal . Y los píxeles en la región TBD que son menores que la media inferior se agregan al fondo temporal . De manera similar, se obtiene una nueva región TBD, que contiene todos los píxeles que se encuentran entre . Esto completa la segunda iteración. Luego, el algoritmo pasa 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 sea menor que un número pequeño, la iteración se detendrá. Para la última iteración, los píxeles superiores se asignan a la clase de primer plano y los píxeles inferiores al umbral se asignan a la clase de fondo. Al final, todos los píxeles temporales del primer plano se combinan para constituir el primer plano final. Todos los píxeles del fondo temporal se combinan para convertirse en el fondo final. En la implementación, el algoritmo no implica ningún parámetro excepto el criterio de parada al 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 estándar de Otsu.

Referencias

  1. ^ M. Sezgin y B. Sankur (2004). "Encuesta sobre técnicas de umbralización de imágenes y evaluación cuantitativa del desempeño". Revista de imágenes electrónicas . 13 (1): 146–165. Código Bib : 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 grises". Transacciones IEEE sobre sistemas, hombre y cibernética . 9 (1): 62–66. doi :10.1109/TSMC.1979.4310076. S2CID  15326934.
  3. ^ Liu, Dongju (2009). "Método Otsu y K-medias". Novena Conferencia Internacional sobre Sistemas Inteligentes Híbridos IEEE . 1 : 344–349.
  4. ^ Liao, Ping-Sung (2001). "Un algoritmo rápido para umbrales multinivel" (PDF) . J.Inf. Ciencia. Ing . 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). "Umbral óptimo de múltiples niveles utilizando un enfoque de optimización Otsu de dos etapas". Letras de reconocimiento de patrones . 30 (3): 275–284. Código Bib : 2009PaReL..30..275H. doi :10.1016/j.patrec.2008.10.003.
  6. ^ Kittler, J.; Illingworth, J. (septiembre de 1985). "Selección de umbral mediante criterios de agrupación". Transacciones IEEE sobre sistemas, hombre y cibernética . 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 la segmentación". Visión por computadora, 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 grises utilizando el método Otsu bidimensional". Circuitos y sistemas, 1991. Actas de la conferencia, China., Conferencia internacional de 1991 sobre : ​​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 probabilidad basado en modelos de mezcla de poblaciones". Reconocimiento de patrones . 25 (10): 1231-1240. Código Bib : 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 el umbral de imagen". Transacciones IEEE sobre procesamiento de imágenes . 20 (8): 2392–2396. doi :10.1109/tip.2011.2114358. ISSN  1057-7149. PMID  21324779. S2CID  10561633.
  11. ^ ab Kittler, J.; Illingworth, J. (1 de enero de 1986). "Umbral mínimo de error". Reconocimiento de patrones . 19 (1): 41–47. Código Bib : 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". 2008 Congreso Internacional de 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. S2CID  14982308.
  13. ^ Zhu, Ningbo y Wang, Gang y Yang, Gaobo y Dai, Weiming (2009). "Un algoritmo rápido de umbralización de otsu 2d 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". Letras de reconocimiento de patrones . 32 (7): 956–61. Código Bib : 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 umbral triclase en segmentación de imágenes". Transacciones IEEE sobre procesamiento de imágenes . 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