A onda: uma frente que se propaga.

A ideia

Pense num fogo que começa no ponto clicado e se espalha pela imagem. Onde a cor do pixel é parecida com a do clique, o fogo corre. Onde a cor muda, ele quase para. Depois de um tempo \(t\), a área queimada é a semente, e a linha do fogo está na borda dela.

Crescer uma região a partir de um ponto escolhido pela pessoa é uma ideia antiga em processamento de imagens [1]. O que a matemática acrescenta é tratar o crescimento como uma frente: saber em que instante a frente chega a cada pixel, resolver isso de forma rápida e entender por que ela para.

O custo da cor

Para o fogo saber onde correr, cada pixel precisa de um número que diga o quanto a cor dele se afasta da cor do clique. O SeedCounter usa a diferença de cor \(\Delta E^*_{ab}\) do espaço CIELAB, padronizada em 1976 [2]: a distância em linha reta entre duas cores nas coordenadas \(L^*\) (claridade), \(a^*\) (verde para vermelho) e \(b^*\) (azul para amarelo).

em que \((L^*_0,a^*_0,b^*_0)\) é a cor média da janela de 5 × 5 pixels em volta do clique. A média tira o ruído de um pixel só. No recorte da figura 1, o clique cai no tegumento claro da semente de cima, com cor de referência \(L^*=54{,}0\), \(a^*=10{,}8\), \(b^*=6{,}1\). O papel azul fica, na mediana, a \(\Delta E=51{,}1\) dela. O embrião vermelho da mesma semente fica a 32,2. Há fórmulas mais finas para a diferença de cor, como a CIEDE2000 [3], mas para separar semente de papel a distância euclidiana basta.

foto e cliqueΔE até o cliquetempo de chegada Tnível da onda

O tempo de chegada e a equação eikonal

Dê a cada pixel uma velocidade \(F(x)\gt0\), alta onde a cor é parecida com a do clique e baixa onde não é. Andando um trecho \(ds\) por um pixel de velocidade \(F\), a frente gasta \(ds/F\). O tempo de chegada a \(x\) é o do caminho mais rápido:

com \(\gamma\) percorrida pelo comprimento de arco. Saindo de \(x\) na melhor direção, um passo \(h\) aumenta \(T\) em \(h/F(x)\), e em nenhuma direção aumenta menos. Isso diz que a derivada de \(T\) na direção de maior crescimento vale \(1/F\):

É a equação eikonal, a mesma da óptica geométrica, em que \(F\) faz o papel do inverso do índice de refração. Ela em geral não tem solução diferenciável: onde dois caminhos ótimos empatam, \(T\) faz um bico. A noção certa de solução é a de viscosidade, de Crandall e Lions, e para \(F\) positiva a solução de viscosidade de (3) é exatamente o menor tempo (2) [4].

Na figura 1 a velocidade é \(F=1/\big(1+(\Delta E/\kappa)^4\big)\), com \(\kappa=18\): cai à metade quando a cor se afasta 18 unidades do clique. No papel, a mediana de \(F\) é 0,015, cerca de 66 vezes mais lenta que na cor do clique. As curvas de nível se amontoam na borda porque a frente desacelera ali. Mas não param: a área alcançada vai de 4.636 pixels em \(T=200\) para 6.169 em 400, 8.314 em 800 e 15.553 em 1.600. Com a soma, a frente nunca para sozinha. Alguém tem de escolher quando parar, e a escolha de \(\kappa\) muda a resposta.

Marcha rápida e Dijkstra

Para calcular \(T\) numa grade de pixels, a marcha rápida (fast marching) de Sethian copia a ideia do algoritmo de Dijkstra para caminhos mínimos em grafos [5][8]. Os pixels ficam em três grupos: aceitos, com \(T\) definitivo; a faixa, vizinhos dos aceitos com um \(T\) provisório; e os de longe. A cada passo, o pixel da faixa com menor \(T\) é aceito, e os vizinhos dele recalculam o próprio valor. Com uma fila de prioridade, o custo total é \(O(N\log N)\) para \(N\) pixels.

A diferença está na conta do vizinho. No Dijkstra, o vizinho recebe \(T(u)+w(u,v)\): a frente só anda pelas arestas da grade. Na marcha rápida, o vizinho resolve uma versão discreta de (3), com os menores valores aceitos \(a\) na horizontal e \(b\) na vertical:

e \(T=\min(a,b)+1/F\) se não. A raiz quadrada deixa a frente andar na diagonal sem seguir as arestas. Tsitsiklis chegou ao mesmo tipo de algoritmo por outro caminho, o das trajetórias ótimas em controle [7]. As frentes como conjuntos de nível de uma função vêm do trabalho de Osher e Sethian [6].

A tabela mostra o maior erro relativo num anel de cada raio, medido nas grades desta página. O do Dijkstra fica parado em 8,24%, o valor da conta acima, e o da marcha rápida cai quando a mesma distância ocupa mais pixels. Com 4 vizinhos, o erro máximo é 41,42%.

A onda do SeedCounter: o pior trecho

A onda do SeedCounter não soma o custo ao longo do caminho. Ela olha o pior trecho: o custo de um caminho é o maior \(\Delta E\) por onde ele passa, e o valor de um pixel é o do melhor caminho até ele.

O cálculo é o Dijkstra de sempre com o máximo no lugar da soma: o vizinho \(v\) de um pixel aceito \(u\) recebe \(\max\big(T_\infty(u),\Delta E(v)\big)\). O nome \(T_\infty\) lembra uma intuição: se o custo de um trecho fosse \(\Delta E^p\) e o de um caminho a raiz \(p\)-ésima da soma, para \(p\) grande só o maior termo contaria.

A frente da onda é então uma curva de nível do próprio \(\Delta E\), sem distância propagada pela grade. Por isso ela não herda o losango nem o octógono da figura 2. Num campo sintético em que o \(\Delta E\) cresce com a distância ao centro, de modo que o alvo é um disco perfeito, a região da onda saiu redonda: os raios a 0° e a 45° diferem em menos de 0,5%. A onda usa 4 vizinhos de propósito. Com 8, duas sementes que só se tocam pela quina de um pixel seriam costuradas numa só.

Onde a onda para: o nível de fuga

Subindo \(t\) aos poucos, a região cresce pela semente até que, num certo nível, ela escapa para o papel e toma a imagem. Esse nível é o custo de fuga:

É a fórmula do passo da montanha de Ambrosetti e Rabinowitz, \(c=\inf_{\gamma}\max_t J(\gamma(t))\), com a paisagem \(J=\Delta E\) [9]. Pense no clique no fundo de um vale: entre todos os caminhos que saem do vale, o melhor é o que sobe menos, e o ponto mais alto dele é o passo, uma sela da paisagem. O teorema deles garante, em espaços de funções e sob condições de compacidade, que esse nível é um valor crítico. Aqui só a fórmula é emprestada, no plano da imagem.

No recorte da figura 1, \(c^*=48{,}2\). Até \(\Delta E\le48{,}20\) a região tem 5.699 pixels, a semente inteira com o embrião. Em \(\Delta E\le48{,}22\) ela tem 30.670 pixels: passou pelo passo e entrou no papel. A onda para logo abaixo desse nível. Com o pior trecho, o critério de parada sai da imagem, e nenhum \(\kappa\) precisa ser escolhido.

Na placa real

O instrumento abaixo começa no clique da figura 1, com os mapas calculados em Python, e refaz tudo no seu navegador. Clique em outra semente para mudar o ponto de partida. No modo da soma, o controle é o tempo \(t\) e \(\kappa\) muda a velocidade. No modo do pior trecho, o controle é o nível de \(\Delta E\), e a linha laranja do gráfico marca o nível de fuga.

Sementes encostadas e o passo da montanha

Quando duas sementes se encostam, a máscara vira uma mancha só e a pergunta passa a ser onde cortar. Aqui entra outra frente: a que parte da borda da mancha para dentro, com velocidade 1. O tempo de chegada dela é o mapa de distância \(d(x)\), a distância de cada pixel ao fundo, solução de \(|\nabla d|=1\) com \(d=0\) na borda. É a equação (3) com \(F\equiv1\).

Cada semente vira um morro no mapa de distância, com o pico perto do meio dela. Duas sementes encostadas dão dois picos, e entre eles uma sela, na cintura onde elas se tocam. O passo da montanha diz que todo caminho de um pico ao outro desce pelo menos até o nível

que é a mesma fórmula (6) com \(J=-d\). O ponto onde o melhor caminho atinge esse nível é a sela, e a linha de corte passa por ela. O divisor de águas (watershed) acha essa linha inundando \(-d\) a partir dos picos: as duas bacias se encontram na sela [10].

duas sementes reaispar sintético lado a lado

Na semente da direita há um terceiro pico, de 15,0 px, separado do principal por uma sela de 14,0 px: uma cintura de só 6,7%. Semente alongada tem uma crista no mapa de distância, e a crista tem calombos. Para não cortar uma semente ao meio, só contam os picos cuja sela fica bem abaixo deles. Na morfologia matemática isso é o h-máximo, calculado por reconstrução [11].

Onde a sela some

O lado direito da figura 3 mostra o caso que quebra a receita. Duas sementes alongadas deitadas lado a lado não formam cintura entre os centros. A união fica mais gorda no meio, a distância ali é maior que no centro de cada semente, e o mapa tem uma crista só. Não há sela, e o mapa de distância não tem corte para propor.

A figura 4 mede quando isso acontece. Para duas elipses iguais, de mesma área, lado a lado com os eixos maiores paralelos, a profundidade da cintura é \(1-d_{\text{sela}}/d_{\text{pico}}\), calculada pela geometria das elipses, sem pixel. A sobreposição é a fração da largura que uma semente avança sobre a outra.

Com 11% de sobreposição, a cintura tem 54,4% para sementes redondas (C/L 1,0), 36,0% para C/L 1,5, 17,1% para 2,2 e 1,4% para 3,5. Em C/L 3,96 ela some. O limite não é uma constante: depende do alongamento e da sobreposição juntos, uma fronteira em duas variáveis. Semente de orquídea, com razão C/L perto de 3,5, fica bem na região em que o mapa de distância deixa de ajudar.

Quando a sela some, a informação do corte não desaparece: ela vai para o contorno. Nas pontas do par aparecem duas reentrâncias, visíveis no quadro da direita da figura 3, e o corte natural liga uma à outra. Métodos que procuram esses pontos côncavos foram comparados por Zafari e colegas [12]. A fronteira da figura 4 dá uma regra calculável antes de tentar: com a razão C/L das sementes da cena, dá para saber se o mapa de distância ainda tem sela a oferecer. Essa regra é uma proposta, ainda sem implementação.

No SeedCounter

Referências

1. Adams R., Bischof L. (1994). Seeded region growing. IEEE Transactions on Pattern Analysis and Machine Intelligence 16(6), 641–647. doi:10.1109/34.295913
2. 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
3. Sharma G., Wu W., Dalal E. N. (2005). The CIEDE2000 color-difference formula: implementation notes, supplementary test data, and mathematical observations. Color Research & Application 30(1), 21–30. doi:10.1002/col.20070
4. Crandall M. G., Lions P.-L. (1983). Viscosity solutions of Hamilton-Jacobi equations. Transactions of the American Mathematical Society 277(1), 1–42. doi:10.1090/S0002-9947-1983-0690039-8
5. Sethian J. A. (1996). A fast marching level set method for monotonically advancing fronts. Proceedings of the National Academy of Sciences 93(4), 1591–1595. doi:10.1073/pnas.93.4.1591
6. Osher S., Sethian J. A. (1988). Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations. Journal of Computational Physics 79(1), 12–49. doi:10.1016/0021-9991(88)90002-2
7. Tsitsiklis J. N. (1995). Efficient algorithms for globally optimal trajectories. IEEE Transactions on Automatic Control 40(9), 1528–1538. doi:10.1109/9.412624
8. Dijkstra E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271. doi:10.1007/BF01386390
9. Ambrosetti A., Rabinowitz P. H. (1973). Dual variational methods in critical point theory and applications. Journal of Functional Analysis 14(4), 349–381. doi:10.1016/0022-1236(73)90051-7
10. Vincent L., Soille P. (1991). Watersheds in digital spaces: an efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence 13(6), 583–598. doi:10.1109/34.87344
11. Vincent L. (1993). Morphological grayscale reconstruction in image analysis: applications and efficient algorithms. IEEE Transactions on Image Processing 2(2), 176–201. doi:10.1109/83.217222
12. Zafari S., Eerola T., Sampo J., Kälviäinen H., Haario H. (2017). Comparison of concave point detection methods for overlapping convex objects segmentation. Em Image Analysis (Lecture Notes in Computer Science), 245–256. Springer. doi:10.1007/978-3-319-59129-2_21