O limiar: Otsu e o histograma.

A ideia

Numa foto de placa de tetrazólio há dois tipos de pixel: semente e papel azul. Se cada pixel virar um número, o histograma desses números costuma ter dois morros, um do papel e outro das sementes. Escolher o limiar é escolher onde cortar o vale entre os dois.

Nobuyuki Otsu propôs em 1979 um critério sem parâmetro nenhum [1]. Para cada corte possível, o histograma fica dividido em duas classes. O melhor corte é o que deixa as duas classes mais diferentes em média, pesando quantos pixels cada uma tem. A animação Segmentação ao vivo faz essa conta sobre uma semente.

Antes do histograma, um canal

A foto tem três números por pixel (vermelho, verde e azul) e o limiar precisa de um. A escolha desse número decide boa parte do resultado. Três candidatos fazem sentido para semente clara sobre papel azul.

O cinza é a luma do vídeo, \(Y'=0{,}299R+0{,}587G+0{,}114B\): a semente é mais clara que o papel. O canal \((R+G)/2-B\) mede quanto o pixel tem de vermelho e verde a mais que de azul: alto no tegumento creme e no embrião vermelho, muito negativo no papel. O terceiro é o b*, o eixo amarelo para azul do espaço de cor CIELAB, padronizado em 1976 [5]:

em que \(Y\) e \(Z\) vêm dos valores lineares de R, G e B por uma matriz fixa e \(Y_n\), \(Z_n\) são os do branco de referência. O papel azul tem b* muito negativo. Semente creme ou vermelha fica bem acima.

fotoOtsu no cinzaOtsu em (R+G)/2 − BOtsu em b*

O que derruba o cinza é a luz desigual. Neste recorte, o papel na faixa de sombra tem cinza 43,0 e o papel de baixo tem 59,6. A semente típica tem 87,6. A luz move o papel 16,6 níveis numa margem de 28 até a semente, mais da metade dela, e o limiar de Otsu (66) acaba a poucos níveis do papel claro. Em b*, a mesma sombra move o papel de −50,6 para −38,5, ou 12,1 unidades, numa margem de 36,7 até a semente (−13,9): um terço.

Há uma razão na própria fórmula (1). Se a luz sobre o papel for multiplicada por \(k\), os valores lineares X, Y e Z também são, e \(b^*\) fica multiplicado por \(k^{1/3}\). O papel continua do lado azul, mais perto do zero, mas longe da semente. A sombra muda sobretudo a claridade, e b* mede a cor.

Isso não faz de b* um campeão. Na seção Onde falha, o canal \((R+G)/2-B\) aguenta melhor uma imagem com poucas sementes, porque nesta placa o papel fica mais liso nele. O canal certo é o que afasta a semente do papel em unidades do ruído do papel e muda pouco quando a luz muda.

A conta de Otsu

Depois de escolhido o canal, cada pixel cai numa de \(L\) classes do histograma (aqui \(L=256\)). Seja \(p_i\) a fração dos pixels na classe \(i\). Um corte em \(k\) separa as classes \(0,\dots,k\) (fundo) das classes \(k+1,\dots,L-1\) (semente).

O limiar de Otsu é \(k^*=\arg\max_k\sigma_B^2(k)\). Os dois pedaços do histograma ficam o mais apertados possível em volta das suas médias, e as médias o mais longe possível uma da outra. O próprio Otsu propôs medir o quanto a separação é boa por \(\eta=\sigma_B^2(k^*)/\sigma_T^2\), um número entre 0 e 1 que não muda se o canal for multiplicado por uma constante ou somado a outra [1].

Dois valores dão escala a \(\eta\). Uma gaussiana só, cortada na média, dá \(\eta=2/\pi\approx 0{,}637\): é o que o método acha quando não há duas classes. Duas classes estreitas e distantes levam \(\eta\) para perto de 1. Nos recortes desta página, com sementes, \(\eta\) fica entre 0,65 e 0,78.

Uma passada só

Calcular médias e variâncias de novo para cada um dos 256 cortes seria desperdício. Com as somas acumuladas \(\omega(k)=\sum_{i\le k}p_i\) e \(\mu(k)=\sum_{i\le k}i\,p_i\), a fórmula (2) vira

porque \(\mu_0=\mu/\omega\), \(\mu_1=(\mu_T-\mu)/(1-\omega)\) e \(\mu_0-\mu_1=(\mu-\omega\mu_T)/\big(\omega(1-\omega)\big)\). Cada corte custa uma conta. O método inteiro é uma passada pelos pixels para montar o histograma e uma passada pelas classes. É o que roda nos instrumentos abaixo:

// h: histograma com 256 classes; devolve o corte k*
let n = soma(h), mT = Σ i·h[i]/n, w = 0, m = 0, melhor = -1, kEstrela = 0;
for (let i = 0; i < 256; i++) {
  w += h[i]/n;  m += i*h[i]/n;              // ω(k) e μ(k) acumulados
  const sB = (mT*w - m)**2 / (w*(1 - w));   // equação (3)
  if (sB > melhor) { melhor = sB; kEstrela = i; }
}

O limiar fica no meio das médias

Na placa limpa do instrumento, em b*, as duas classes do corte de Otsu têm médias −41,52 e −12,42. O meio delas é −26,97, e o limiar de Otsu é −27,0.

Esse é o mesmo ponto fixo do método iterativo de Ridler e Calvard [4]: começar de um limiar qualquer, calcular as duas médias, pôr o limiar no meio delas e repetir. Entre os pontos fixos, Otsu fica com o de maior \(\sigma_B^2\). O resultado também explica as falhas. O limiar só enxerga as médias. A largura de cada classe e o tamanho dela entram apenas pelo jeito como deslocam as médias.

Na placa real

O instrumento abaixo carrega cinco recortes reais, calcula os três canais no seu navegador e mostra a máscara, o histograma e a curva \(\sigma_B^2(t)\). O botão Otsu pula para o máximo da curva. O botão Erro mínimo usa o critério da seção Alternativas.

Na placa cheia, os três canais concordam: o Otsu marca 26,8% da imagem em b*, 28,8% em \((R+G)/2-B\) e 28,8% no cinza. Na faixa de sombra, o \(\eta\) é praticamente o mesmo nos três canais (0,654, 0,659 e 0,654) e as máscaras são muito diferentes, como na figura 1. O \(\eta\) mede o histograma, e o histograma não sabe onde cada pixel está.

No reflexo da placa, os três canais erram (30,0% a 37,1% da imagem), porque a faixa de reflexo é mais clara que o papel e, em parte, mais amarela. No recorte só de papel, o Otsu ainda devolve um limiar e marca entre 41,5% e 49,6% da imagem como semente, com \(\eta\) entre 0,60 e 0,66, perto do \(2/\pi\) de uma gaussiana só. O método sempre responde, e a resposta não diz se havia o que achar.

Onde falha

Poucas sementes num fundo grande

Para isolar o efeito do tamanho das classes, a figura 2 monta histogramas com pixels reais de uma placa: 8.817 pixels de dentro das sementes anotadas e 223.729 pixels de um quadrante sem semente. A mistura é exata, a soma ponderada dos dois histogramas, para cada fração de semente. Muda só a proporção.

O salto tem conta. Com uma fração \(f\) pequena de semente, a diferença \(\Delta\) entre as médias de semente e papel e o desvio \(\sigma\) do papel, o corte certo dá \(\sigma_B^2\approx f\,\Delta^2\) pela equação (2). Cortar o papel ao meio, se ele for perto de gaussiano, dá \(\sigma_B^2\approx\frac{2}{\pi}\sigma^2\). O Otsu troca de corte quando o segundo passa o primeiro:

A estimativa ignora a largura da classe semente e acerta a quebra com erro de até 13%. O que manda é a razão \(\Delta/\sigma\), a distância entre semente e papel em unidades do ruído do papel. Nesta placa cada semente ocupa cerca de 0,4% do recorte de 946 × 946 px: no cinza, um recorte com uma semente só já fica abaixo da quebra.

Luz desigual e reflexo

Um limiar global supõe que o papel tem o mesmo valor em toda a imagem. A sombra e o reflexo da figura 1 e do instrumento quebram essa suposição, e nenhum método que olha só o histograma conserta isso, porque o histograma perdeu a posição dos pixels.

Histograma sem dois morros

Com uma classe só, como no recorte de papel, o Otsu corta o ruído ao meio. Com contraste fraco, os dois morros se fundem e o vale some. Nos dois casos o método devolve um número com a mesma confiança de sempre.

Alternativas

Erro mínimo

Kittler e Illingworth modelaram cada classe por uma gaussiana com média, variância e peso próprios e escolheram o corte que melhor explica o histograma com esse modelo [2]. O critério é

e o limiar é o \(k\) que minimiza \(J\). Como a largura de cada classe entra na conta, a classe pequena não perde para a grande. Na mistura da figura 2, o erro mínimo não salta: em b*, com 1% de semente, marca 1,02%. Nos recortes reais, porém, ele erra de outro jeito. Na faixa de sombra, no cinza, marca 0,4% da imagem e perde quase todas as sementes. No recorte de papel, em b*, marca 89%. Quando o histograma não tem a forma de duas gaussianas, o modelo não tem onde se apoiar.

Mistura de gaussianas

A versão suave do mesmo modelo ajusta as duas gaussianas pelo algoritmo EM e corta onde as duas densidades ponderadas se cruzam. O mesmo problema aparece com outro histograma no SeedCounter: o de um descritor de forma entre as sementes de uma cena, em que semente isolada e aglomerado formam dois morros. Uma mistura de dois componentes acharia esse corte sem constante escolhida à mão. É uma proposta do projeto, ainda sem teste.

Limiar local

Em vez de um \(t\) para a imagem, um \(t(x)\) para cada vizinhança. Sauvola e Pietikäinen usam a média \(m(x)\) e o desvio \(s(x)\) numa janela: \(t(x)=m(x)\,[1+\kappa\,(s(x)/R-1)]\) [6]. Outra saída é achatar a luz antes: ajustar uma superfície suave ao papel e descontá-la, e só então aplicar um limiar global. Sezgin e Sankur catalogaram e compararam 40 métodos de limiar, agrupados pela informação que usam: forma do histograma, agrupamento, entropia, atributos do objeto, correlação espacial e superfície local [3].

No SeedCounter

Referências

1. Otsu N. (1979). A threshold selection method from gray-level histograms. IEEE Transactions on Systems, Man, and Cybernetics 9(1), 62–66. doi:10.1109/TSMC.1979.4310076
2. Kittler J., Illingworth J. (1986). Minimum error thresholding. Pattern Recognition 19(1), 41–47. doi:10.1016/0031-3203(86)90030-0
3. Sezgin M., Sankur B. (2004). Survey over image thresholding techniques and quantitative performance evaluation. Journal of Electronic Imaging 13(1), 146–165. doi:10.1117/1.1631315
4. Ridler T. W., Calvard S. (1978). Picture thresholding using an iterative selection method. IEEE Transactions on Systems, Man, and Cybernetics 8(8), 630–632. doi:10.1109/TSMC.1978.4310039
5. Robertson A. R. (1977). The CIE 1976 color-difference formulae. Color Research & Application 2(1), 7–11. doi:10.1002/j.1520-6378.1977.tb00104.x
6. Sauvola J., Pietikäinen M. (2000). Adaptive document image binarization. Pattern Recognition 33(2), 225–236. doi:10.1016/S0031-3203(99)00055-2