En la visión por computadora y el procesamiento de imágenes , el método de Otsu , que lleva el nombre de Nobuyuki Otsu (大 津 之 之, Ōtsu Nobuyuki ) , se utiliza para realizar el umbral automático de la imagen . [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 variación de intensidad dentro de la clase 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 un k-means [3] globalmente óptimo realizado en el histograma de intensidad. La extensión a los umbrales multinivel se describió en el documento original, [2] y desde entonces se han propuesto implementaciones computacionalmente eficientes. [4] [5]
El método de Otsu
El algoritmo busca exhaustivamente el umbral que minimiza la varianza intraclase, definida como una suma ponderada de varianzas de las dos clases:
Pesos y son las probabilidades de las dos clases separadas por un umbral ,y y son variaciones de estas dos clases.
La probabilidad de clase se calcula a partir de la contenedores del histograma:
Para 2 clases, minimizar la varianza intraclase equivale a maximizar la varianza entre clases: [2]
que se expresa en términos de probabilidades de clase y clase significa , donde la clase significa , y están:
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
- Calcule el histograma y las probabilidades de cada nivel de intensidad.
- Configurar inicial y
- Paso a través de todos los umbrales posibles intensidad maxima
- Actualizar y
- Calcular
- El umbral deseado corresponde al máximo
Implementación de MATLAB u Octave
histogramCounts es un histograma de 256 elementos de una imagen en escala de grises con diferentes niveles de gris (típico de las imágenes de 8 bits). el nivel es el umbral de la imagen (doble).
nivel de función = otsu ( histogramCounts ) total = suma ( histogramCounts ); % número total de píxeles en la imagen %% OTSU umbral automáticotop = 256 ; sumaB = 0 ; wB = 0 ; máximo = 0.0 ; suma1 = punto ( 0 : arriba - 1 , histogramCounts ); para ii = 1 : arriba wF = total - wB ; si wB > 0 && wF > 0 mF = ( suma1 - sumaB ) / wF ; val = wB * wF * (( sumB / wB ) - mF ) * (( sumB / wB ) - mF ); si ( val > = máximo ) nivel = ii ; máximo = val ; final final wB = wB + histogramCounts ( ii ); sumaB = sumaB + ( ii - 1 ) * histogramCounts ( ii ); finalfinal
Matlab tiene funciones integradas graythresh()
y multithresh()
en la caja de herramientas de procesamiento de imágenes que se implementan con el método de Otsu y el método de Multi Otsu, respectivamente.
Limitaciones
El método de Otsu exhibe un rendimiento relativamente bueno si se puede suponer que el histograma tiene una distribución bimodal y que posee un valle profundo y agudo entre dos picos. Pero si el área del objeto es pequeña en comparación con el área de fondo, el histograma ya no presenta bimodalidad. [6] Y si las variaciones del objeto y las intensidades de fondo son grandes en comparación con la diferencia media, o la imagen está muy dañada por ruido aditivo, el valle nítido del histograma de nivel de gris se degrada. Entonces, el umbral posiblemente incorrecto determinado por el método de Otsu da como resultado el error de segmentación. (Aquí definimos el tamaño del objeto como la relación entre el área del objeto y el área completa de la imagen y la diferencia media como la diferencia entre las intensidades medias del objeto y el fondo)
Los resultados empíricos muestran que el rendimiento de las técnicas de umbral global utilizadas para la segmentación de objetos (incluido el método de Otsu) está limitado por el tamaño pequeño del objeto, la pequeña diferencia media entre los píxeles de primer plano y de fondo, las grandes variaciones de los píxeles que pertenecen al objeto y los que pertenecen al fondo, la gran cantidad de ruido, etc. [7]
Mejoras
Se han desarrollado varias extensiones para abordar las limitaciones del método de Otsu. Una extensión 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 dado 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 medio del nivel de gris de la vecindad. Deje que el nivel de gris del píxel dado se divida en valores discretos y el nivel de gris medio también se divide en el mismo valores. Luego se forma un par: el nivel de gris de píxeles y el promedio de la vecindad. Cada par pertenece a uno de losposibles contenedores bidimensionales. El número total de ocurrencias (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 bidimensional de Otsu 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
La y se obtiene de forma iterativa, lo que es similar al método unidimensional de Otsu. Los valores de y se cambian hasta obtener el máximo de , es decir
max , 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 ; terminar si final para final para return 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. [9] Sin embargo, incluso con el enfoque de programación dinámica, el método de 2d Otsu todavía tiene una gran complejidad de tiempo. Por lo tanto, se han realizado muchas investigaciones para reducir el costo de computación. [10]
Si se utilizan tablas de áreas sumadas para construir las 3 tablas, sume , suma sobre y suma , 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ón de Matlab
función de entradas y salidas:
hists es un Histograma 2D del valor de escala de grises y el par de valores de escala de grises promedio del vecindario.
total es el número de pares en la imagen dada. Está determinado por el número de contenedores del histograma 2D en cada dirección.
umbral es el umbral obtenido.
umbral de función = otsu_2D ( hists, total ) máximo = 0.0 ; umbral = 0 ; helperVec = 0 : 255 ; mu_t0 = sum ( sum ( 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 ); demás 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 ); final demás p_0 ( ii , jj ) = p_0 ( ii , jj - 1 ) + p_0 ( ii - 1 , jj ) - p_0 ( ii - 1 , jj - 1 ) + hists ( ii , jj ); 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 ); final si ( p_0 ( ii , jj ) == 0 ) continuar ; final si ( p_0 ( ii , jj ) == total ) romper ; final 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 ; final finalfinalfinal
Referencias
- ^ 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. doi : 10.1117 / 1.1631315 .
- ^ a b c Nobuyuki Otsu (1979). "Un método de selección de umbral a partir de histogramas de nivel de gris". IEEE Trans. Sys. Hombre. Cyber . 9 (1): 62–66. doi : 10.1109 / TSMC.1979.4310076 .
- ^ Liu, Dongju (2009). "Método Otsu y K-medias". Novena Conferencia Internacional sobre Sistemas Inteligentes Híbridos IEEE . 1 : 344–349.
- ^ Liao, Ping-Sung (2001). "Un algoritmo rápido para umbrales multinivel" (PDF) . J. Inf. Sci. Ing . 17 (5): 713–727. Archivado desde el original (PDF) el 24 de junio de 2019.
- ^ Huang, Deng-Yuan (2009). "Umbral óptimo de varios niveles utilizando un enfoque de optimización Otsu de dos etapas". Cartas de reconocimiento de patrones . 30 (3): 275-284. doi : 10.1016 / j.patrec.2008.10.003 .
- ^ Kittler, Josef y Illingworth, John (1985). "Sobre la 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 .
- ^ Lee, Sang Uk y Chung, Seok Yoon y Park, Rae Hong (1990). "Un estudio de rendimiento comparativo 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 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Jianzhuang, Liu y Wenqing, Li y Yupeng, Tian (1991). "Umbral automático de imágenes de nivel de gris utilizando el método Otsu de dos dimensiones". Circuits and Systems, 1991. Conference Proceedings, China., 1991 International Conference on : 325–327.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Zhang, Jun y Hu, Jinglu (2008). "Segmentación de imágenes basada en el método Otsu 2D con análisis de histograma". Ciencias de la Computación e Ingeniería de Software, 2008 Conferencia Internacional sobre . 6 : 105-108. doi : 10.1109 / CSSE.2008.206 . ISBN 978-0-7695-3336-0.
- ^ Zhu, Ningbo y Wang, Gang y Yang, Gaobo y Dai, Weiming (2009). "Un algoritmo de umbralización otsu 2d rápido basado en histograma mejorado". Reconocimiento de patrones, 2009. CCPR 2009. Conferencia china sobre : 1–5.CS1 maint: varios nombres: lista de autores ( enlace )
enlaces externos
- Implementación del método de umbral de Otsu como GIMP -plugin usando Script-Fu (un lenguaje basado en Scheme )
- Notas de clase sobre la creación de umbrales : cubre el método Otsu
- Un complemento para ImageJ que usa el método de Otsu para hacer el umbral
- Una explicación completa del método de Otsu con un ejemplo de trabajo e implementación de Java
- Implementación del método de Otsu en ITK
- Otsu Thresholding en C # : una implementación de C # sencilla con explicación
- El método de Otsu usando MATLAB
- Umbral de Otsu con scikit-image en Python