USO DE MÁQUINA DE VETORES DE SUPORTE E TRANSFORMADA
WATERSHED NA SEGMENTAÇÃO INDIVIDUAL DE DENTES A PARTIR DE
IMAGENS DIGITAIS INTRABUCAIS OCLUSAIS
Ramon A. S. Lins∗, Keylly Eyglys∗, Adrião Duarte Dória Neto∗, Luis Noro†, Angelo
Giuseppe Roncalli†, Maria Cristina dos Santos Medeiros†, Pedro Henrique Sette de
Souza†, Samara Martins da Silva†
∗
Laboratório de Sistemas Inteligentes
Departamento de Computação e Automação
Universidade Federal do Rio Grande do Norte, RN, Brasil
†
Departamento de Odontologia
Universidade Federal do Rio Grande do Norte, RN, Brasil
Emails: [email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected]
Abstract— In this paper we propose the development of an intelligent system capable of segment individual
teeth from occlusal intraoral digital images. The proposed system makes combined use of supervised learning
and digital image processing techniques, support vector machine and watershed transform respectively. The
segmentation is based on the colors of teeth and no teeth present in the image. After segmentation, the watershed
transform is performed to detect the regions of teeth contour. The system had a good performance in the
individual separation of teeth present and observable in images.
Keywords—
form
Occlusal intraoral digital images, Intelligent System, Support Vector Machine, Watershed Trans-
Resumo— Neste tabalho é proposto o desenvolvimento de um sistema inteligente capaz de segmentar individualmente dentes a partir de imagens digitais intrabucais oclusais. O sistema proposto faz uso combinado das
técnicas de aprendizado supervisionado e processamento digital de imagens, máquina de vetores de suporte e
transformada watershed respectivamente. A segmentação é baseada nas cores dos dentes e não dentes presentes
na imagem. Após a segmentação, a transformada watershed é utilizada para detectar as regiões de contorno dos
dentes. O sistema apresentou um bom desempenho na separação individual dos dentes presentes e observáveis
nas imagens.
Palavras-chave— Imagens Digitais Intrabucais Oclusais, Sistema Inteligente, Máquina de Vetores de Suporte,
Transformada Watershed
1
Introdução
O rápido desenvolvimento de sistemas de imagens
médicas tem aprimorado os diagnósticos e suas interpretações. Na indústria odontológica, o procedimento assistido por computador como implante
dentário, planejamento ortodôntico entre outros é
cada vez mais utilizado. Identificar as estruturas
dos dentes é apenas uma das etapas destes procedimentos. Para este propósito a segmentação
é um processo necessário na grande maioria dos
casos de análise de dentes em imagens.
O processo de segmentação em imagens dentárias é uma tarefa difı́cil de ser realizada em processamento digital de imagens. Esta dificuldade
força, na maioria das vezes, o uso de diferentes algoritmos de segmentação para diferentes etapas ou
imagens analizadas. As imagens dentárias podem
ser utilizadas de maneiras diferentes fornecendo
modelos 2D (bidimensional) ou 3D (tridimensional). Dentre as principais utilizadas na prática
temos as radiografias, as fotografias e de tomografia computadorizada.
Muitos esforços foram feitos nessa área para
desenvolver métodos que gerem bons resultados
para diferentes tipos de imagens. Algumas técnicas fazem uso de algoritmos baseados em propriedades estatı́ticas (Choorat et al., 2011), análise
de filtro (Li et al., 2010), morfologia matemática
(Mahsa Sepehrian, 2013) entre outros.
Na saúde bucal coletiva o profissional é responsável pelo diagnóstico dos problemas de saúde
oral em uma comunidade por meio de levantamentos epidemiológicos. A inspeção visual bucal é um
procedimento comumente realizado por estes profissionais, mas possui fatores limitantes, como por
exemplo o número limitado de profissionais habilitados para realização desta tarefa e diferentes
interpretações de diagnósticos.
Com o intuito de tornar esta atividade um
processo ágil, eficiente e de baixo custo foi proposto pelo departamento de odontologia em parceria com departamento de computação, ambos
da Universidade Federal do Rio Grande do Norte
- UFRN, o desenvolvimento de um sistema inteligente capaz de fazer a contagem e classificação dos
dentes de forma automática a partir de imagens
digitais, obtidas através de câmeras intraorais.
Atualmente o sistema é capaz de fazer a contagem de dentes em uma imagem digital oclusal intraoral. Nessa etapa foi proposta uma técnica de aquisição de imagens, que se ajusta as limitações enfrentadas pelos agentes de saúde em
campo, além de favorecer o seu processamento.
Para tanto, foram realizadas diversas medições de
angulação de inclinação e distância da câmera de
aquisição, onde cada uma das amostras foram avaliadas quanto ao seu resultado no processo de contagem.
Dando continuidade ao trabalho desenvolvido,
este artigo propõe uma metodologia para segmentação e detecção das regiões de contorno dos
dentes nas imagens. Estas sub-etapas são prérequisitos para o procedimento de classificação dos
tipos de dentes, atualmente em desenvolvimento.
O método proposto faz uso combinado de técnicas de aprendizado supervisionado e de processamento digital de imagens, em destaque máquina
de vetores de suporte (Support Vector Machine SVM ) e transformada watershed.
A segmentação é baseada nas cores dos dentes e não dentes presentes na imagem realizada
através da utilização da SVM, técnica usada tanto
para problemas de classificação como de regressão.
Em seguida a detecção de contorno dos dentes é feita através do uso da transformada watershed, técnica proposta por Beucher and Lantuejoul (1979) como um modelo geofı́sico de decaimento da chuva em um terreno. A idéia é que uma
gota de chuva caindo em uma superfı́cie irá gotejar através do caminho de descida mais ı́ngreme
até um mı́nimo (Beare and Lehmann, 2006).
Este artigo está organizado da seguinte forma:
Na seção 2 é feita uma revisão bibliográfica da
SVM. Na seção 3 é explicada a metodologia desenvolvida para segmentação individual dos dentes em imagens. Os resultados são descritos na
seção 4. Finalmente, na seção 5, as conclusões são
discutidas.
2
Máquinas de Vetores de Suporte
Uma breve revisão sobre máquina de vetores de
suporte será feita.
A SVM é um classificador de padrões embasado na teoria de aprendizado estatı́stico, proposto por (Vapnick, 1995), que busca encontrar
uma superfı́cie de separação ótima, minimizando
os erros de classificação. Ela pode ser usada tanto
na solução de problemas linearmente quanto não
linearmente separáveis.
Dado um conjunto de treinamento linearmente separável X com n objetos x ∈ X e suas
respectivas classes de saı́das distintas y ∈ Y, em
que Y = {−1, +1}, o hiperplano ótimo que separa
a duas classes é dado pela expressão:
f (x) = w.x + b
(1)
de forma que w.x é o produto escalar entre x e
b
é a
w, vetor normal ao hiperplano ótimo, e ||w||
distância do hiperplano à origem, para um b ∈ <.
A partir da definição do hiperplano, o conjunto de entrada pode ser separado em duas regiões:
(
w.x + b > 0
(2)
f (x) =
w.x + b < 0
Através do uso de uma função sinal sgn(f (x)),
os pontos de X mais próximos do hiperplano canônico, w.x + b = 0, formam as margens de separação (vetores de suporte) e são definidos como:
|w.x + b| = 1
(3)
O problema é restringido de forma que não
ocorram dados de treinamentos entre as margens
de separação (SVM com margens rı́gidas). Na
prática, fatores como ruı́dos, outliers entre outros
fatores tornam a tarefa de separação através de
margens rı́gidas mais difı́ceis. Para que o processo
de separação torne-se mais maleável são inseridas
variáveis de folgas ξ. Essas folgas tornam as margens mais flexı́veis (SVM com margens suaves),
de forma que os vetores de suporte sejam definidos como:
y (w.x + b) − 1 + ξ ≥ 0
(4)
Segundo Campbell (2000), a maximização da
margem de separação dos objetos em relação a
w.x + b = 0 pode ser obtida pela minimização de ||w||. Com a inserção das variáveis de
folga o problema de minimização é definido como
(Burges, 1998):
!
n
X
1
2
ξi
(5)
min ||w|| + C
w,b,ξ 2
i=1
onde C é um termo de regularização que impõe
um peso à minimização dos erros no conjunto de
treinamento em relação à minimização da complexidade do modelo (Katti Facelli, 2011).
O problema de minimização é um problema
de otimização quadrático com restrições lineares e
pode ser resolvido através do uso de multiplicadores de Lagrange. Com isso, o problema de maximização das margens suáveis para separação ótima
dos dados é definido como (Katti Facelli, 2011):
max
α
n
X
i=1
n
1 X
αi αj yi yj (xi . xj )
αi −
2 i,j=1
(
0 ≤ αi ≤ C, ∀i = 1, ..., n
Restrições: Pn
αy =0
i=1 i i
(6)
(7)
sendo α o parâmetro denominado multiplicador de Lagrange.
No caso de padrões não linearmente separáveis, deve ser feito um mapeamento Φ do espaço
de entradas X para o espaço de caracterı́sticas =.
Segundo o teorema de Cover (Haykin, 1999) para
que esse mapeamento garanta com alta probabilidade a separação dos objetos, a transformação
deve ser não linear e o espaço de caracterı́sticas
ter dimensão suficientemente alta.
Mapeando o problema de otimização tem-se
que:
max
α
n
X
i=1
αi −
n
1 X
αi αj yi yj (Φ(xi ) . Φ(xj )) (8)
2 i,j=1
Através do uso de funções kernel K o produto
escalar do espaço de entradas é calculado no espaço de caracterı́sticas (Herbrich, 2001), com isso
tem-se que:
K(xi , xj ) = Φ(xi )Φ(xj )
(9)
Segundo Mercer (1909), qualquer função kernel positiva semi-definida satisfaz a relação:
n
X
αi αj K(xi , xj ) ≥ 0
(10)
i,j=1
Uma vez feito o mapeamento, a otimização
segue como nos casos linearmente separáveis.
3
Método de Segmentação
Em resumo, como mostrado na figura 1, o processo
de segmentação dos dentes a partir de imagens digitais intrabucais oclusais é basicamente definido
em três etapas. A imagem utilizada passa por
um pré-processamento, em seguida acontece a segmentação, onde ocorre a identificação e detecção
dos limites das regiões de interesse. Como resultado são obtidas as regiões de contorno de cada
dente presente na imagem.
3.1
Pré-processamento
O pré-processamento de imagens é um procedimento utilizado com frequência em problemas de
reconhecimento de padrões. Tem como intuito
adequar os dados de entrada para diferentes objetivos, a fim de obter a melhor solução possı́vel
para um determinado problema.
A imagem digital é representada por uma matriz de pixels, menores elementos em uma imagem
digital, que podem receber um valor lógico numa
imagem binária, um nı́vel de cinza em uma imagem preta e branca, ou um vetor de valores RGB
(vermelho, verde, azul; em inglês), em imagens
coloridas, com valores que variam de 0 a 255, que
podem ser normalizados de 0 a 1 (Gonzalez and
Woods, 2010).
Nesta etapa, o dado de entrada é uma imagem digital intrabucal oclusal no sistema de cor
Figura 1: Diagrama de blocos da metodologia proposta
RGB obtida a partir da metodologia de acquisição de imagem descrita na introdução. Existem
ainda outros tipos de representações de imagens,
neste caso, é utilizado a representação denominada YCbCr que será detalhada na seção 3.1.2.
3.1.1
Adaptação de escala
Devido as diferentes escalas resultantes do processo de aquisição da imagem, é realizado um procedimento de adaptação de escala, que reduz ou
amplia a imagem para que seja atingida dimensões
próximas de 640 x 480 pixels.
3.1.2
Conversão RGB para YCbCr
O modelo YCbCr possui redundâncias que podem
ser eliminadas sem prejuı́zo a imagem, tornando os
arquivos de imagens menores sem grande perdas
visuais.
Neste modelo, o Y representa a luminância de
uma imagem, enquanto o Cb representa a crominância azul (B - Y) e o Cr a crominância vermelha
(R - Y). O processo de conversão de RGB para
YCbCr é dado pela seguinte equação:



Y
0.29900
 Cb  =  -0.16874
Cr
0.50000
0.58700
-0.33126
-0.41868


0.11400
R
0.50000   G 
-0.08131
B
(11)

 
 

Y’
Y
0
 Cb’  =  Cb  +  128 
Cr’
Cr
128
(12)
Como descrito por Acharya and Tsai (2005),
as camadas Cb e Cr podem resultar em valores
negativos. Para que sua representação fique entre
0 e 255 é necessário adicionar o escalar 128 e fazer
o seu arredondamento.
3.1.3
Ajuste de Constraste
Para conseguir um melhor contraste aplica-se em
cada camada um aumento de contraste, evidenciando as caracterı́sticas da imagem. A figura 2
mostra o processo de conversão RGB para YCbCr
e o ajuste de contraste.
A etapa de preenchimento de buracos é baseada na técnica de transformação morfológica chamada de reconstrução morfológica por erosão. Basicamente a reconstrução é feita através da erosão
de uma máscara de imagem em função de um marcador de imagem que em geral é a própria imagem.
Dado z ∈ F, sendo F uma imagem de entrada
e B um elemento estruturante, a operação de erosão é definida pela equação abaixo:
F B = {z|(B)z ⊆ F }
Após o preenchimento dos buracos a imagem
sofre uma nova erosão para que ruı́dos e elementos indesejados sejam removidos. Estes procedimentos descritos podem ser observados na figura
3. Ela representa a identificação das regiões de
interesse: (a) Imagem binária de saı́da do classificador; (b) Imagem com buracos preenchidos; (c)
Aplicação da operação morfológica de erosão para
eliminação de ruı́dos e regiões indesejadas.
(a)
Figura 2: Imagem RGB convertida para YCbCr
com ajuste de constraste
3.2
Segmentação
3.2.1
Segmentação por cores
A partir da conversão e ajuste de contraste da
imagem, a segmentação é feita através do uso de
um classificador SVM. Cada pixel da imagem é
classificado como dente ou não dente, que para
este problema foram configuradas como amostras
variadas de cores de dentes e restaurações em uma
classe, e gengiva, lı́ngua e outras texturas bucais
na segunda classe. A saı́da do classificador é uma
imagem binária com as regiões de interesse identificadas, acrescida de ruı́dos e regiões indesejadas,
ver figura 3a. Em seguida, aplica-se a técnica de
reconstrução morfológica por erosão para que regiões indesejadas, como os buracos de imagens e
ruı́dos sejam reduzidas ou eliminadas, como demonstrado a seguir.
3.2.2
Operadores morfológicos
Segundo Soille (2002), buracos de imagens binárias são definidos como um conjunto de componentes de fundo que não são conectados as bordas da
imagem. Seguindo esta ideia, podemos dizer que
buracos são conjuntos de pixels de fundo (pretos)
cercados por pixels de primeiro plano (branco) que
não se conectam as bordas dos objetos.
(13)
(b)
(c)
Figura 3: Etapas de identificação das regiões de
interesse
A combinação das técnicas de preenchimento
de buracos e erosão utilizadas na eliminação de
regiões indesejadas retorna uma imagem binária
adequada para o mapeamento de distância das regiões de interesse. A imagem de distância é utilizada pelo algoritmo watershed e ambas as técnicas
serão explicadas com mais detalhes nas subseções
adiante.
3.2.3
Transformada Watershed
Com a segmentação e adequação da imagem é necessário que as fronteiras das regiões de interesse
sejam detectadas para que cada dente seja individualmente segmentado. Neste trabalho é utilizada a transformada watershed, técnica baseada
na morfologia matemática inspirada na detecção
de superfı́cies em bacias hidrográficas.
A transformada watershed é utilizada principalmente em imagens gradiente. Nela é feita a
detecção das bacias hidrográficas de todos os mı́nimos presentes na imagem de gradientes. Meyer
(1994), define a imagem gradiente como relevos
topográficos. Este relevo sofre um processo de
inundação uniforme a partir de seus mı́nimos regionais. A partir do momento em que as inundações começam a se misturar, barreiras são erguidas
para evitar que isto aconteça, estas barreiras são
conhecidas como linhas de watershed.
A existência de muitos mı́nimos regionas podem levar a um problema de sobresegmentação.
Para que isto não aconteça é feito o uso de marcadores. Neste caso, um conjunto de marcadores é
detectado para cada objeto presente na imagem,
inclusive o fundo. Em seguida o processo de inundação é feito a partir de mı́nimos regionais identicos aos dos marcadores. Após a inundação a
imagem é segmentada de maneira que cada parte
contenha apenas um marcador.
Esta breve descrição intuitiva pode ser definida de forma mais rigorosa. Antes devemos definir a distância topográfica de cada região identificada, ou seja, devemos obter a imagem gradiente.
O cálculo da distância é feito a partir da métrica
de distância chessboard, analogia ao movimento do
rei em um jogo de xadrez. O cálculo depende apenas das coordenadas dos pixels e é definido pela
equação 10 como sendo:
conhecidos como pixels de watershed. O elemento
0 não pertence a nenhuma região watershed. Os
elementos rotulados como 1 pertencem a primeira
região watershed identificada, os elementos rotulados como 2 pertencem a segunda região watershed identificada e assim por diante, gerando
como saı́da uma matriz de rótulos que representam as regiões de interesse segmentadas.
As etapas descritas anteriormente podem ser
observadas na figura 4: (a) Imagem gradiente; (b)
Regiões de contorno.
(b)
(a)
max(|x1 − x2 |, |y1 − y2 |)
(14)
Segundo Meyer (1994), considerando f uma
função distância a partir de <2 em <, supp(f )
como suporte de f, T o intervalo de < e γ uma
função continua de T em supp(f ). Sendo (T, γ) o
caminho contido no suporte de f e Γ(p, q) o conjunto de todos os caminhos entre os pontos p e q, a
distância topográfica entre dois pontos no espaço
continuo é defnida como:
Z
DT (p, q) =
|∇f (γ(s))|ds
inf
γ∈Γ(p,q)
(15)
γ
onde o módulo do gradiente da função f representa
a variação topográfica de f.
As bacias hidrográficas BH(mi ) dos mı́nimos regionais mi como conjunto de pontos x ∈
supp(f ) que estão mais próximos de mi do que
outro mı́nimo regional para a distância topográfica são definidas como:
∀j ∈ I, j 6= i ⇒ DT (x, mi ) < DT (x, mj )
(16)
Descrevendo as linhas de watershed da função f como o conjunto de pontos do suporte de f
que não pertencem a nenhuma bacia hidrográfica
como:
W sh(f ) = supp(f ) ∩ [∪(BH(mi ))]c
i
(17)
Pode-se observar que o algoritmo de integração de imagens é na verdade um algoritmo usado
para computar distâncias ponderadas, ou seja, é o
mesmo que computar o caminho de custo mı́nimo
entre os pixels (Verbeek and Verwer, 1990). O tamanho do caminho de custo mı́nimo é na verdade
a distância topográfica.
Aplicando-se a transformada watershed na
imagem gradiente os elementos são rotulados com
números inteiros maiores ou iguais a zero e são
Figura 4: Identificação das regiões de contorno
através de imagens gradientes
4
Resultados
O método proposto foi desenvolvido no ambiente
de programação Matlab R2013a.
Foram utilizadas 31 imagens no processo de
segmentação de dentes tanto na etapa de separação por cores quanto na detecção das regiões de
contorno.
Na segmentação por cores foi utilizado um
conjunto de dados composto de 22353 pontos de 3
dimensões (YCbCr), representando os pixels pertencentes às classes dentes e não dentes. O conjunto de dados foi divido pela metade, 50% para
treinamento e 50% para teste. Os processos de
treinamento e de teste foram realizados repetidas
vezes para diferentes funções kernel. Ao término
do processo de repetição foram obtidas as informações estatı́sticas de média e variância dos resultados obtidos demostrados na tabela 1 a seguir:
Função Kernel
Quadrático
RBF
MLP
Acerto(%)
96.59
98.13
72.83
Variância
0.01
0.01
4.46
Tabela 1: Resultado da segmentação por cores dos
dentes presentes nas imagens dentais
Na detecção de contornos dos dentes das imagens utilizadas foram visualmente contabilizados
um total de 340 dentes, em que 76 deles são molares, 89 pré-molares, 59 caninos e 116 incisivos,
desconsiderado-se os terceiros molares. Através da
metodologia utilizada foi possı́vel obter uma taxa
de 87,35% de segmentação dos dentes presentes
nas imagens utilizadas.
A tabela 2 mostra de forma concisa os resultados obtidos durante o processo de reconhecimento
dos dentes.
Dentes
Molares
Pré molares
Caninos
Incisivos
Total
Presentes
76
89
59
116
340
Segmentados
56
75
58
108
297
Acerto(%)
73.68
84.27
98.31
93.10
87.35
Tabela 2: Resultado da detecção de contorno dos
dentes presentes nas imagens dentais
Problemas como dentes encobertos por lı́ngua, iluminação entre outros interferem principalmente na performance da segmentação dos dentes
molares (região mais interna da boca). Outro fator limitante está na geração dos marcadores utilizados como mı́nimos regionais nas imagens gradientes para a segmentação watershed.
5
Conclusões
Beucher and Lantuejoul (1979). Use of watershed
in contour detection, pp. 17–21.
Burges, C. J. (1998). A Tutorial on Support Vector Machines for Pattern Recognition, pp. 1–
43.
Campbell, C. (2000). Radial Basis Function
Networks: Design and Applications, Springer Verlag pp. 155–192.
Choorat, P., Chiracharit, W. and Chamnongthai,
K. (2011). A single tooth segmentation using
structural orientations and statistical textures, 4th Biomedical Engineering International Conference pp. 294–297.
Gonzalez, R. C. and Woods, R. E. (2010). Digital
Image Processing, 3 edn, Pearson.
Haykin, S. (1999). Neural Networks: A Comprehensive Foundation, 2 edn, BOOKMAN.
Herbrich, R. (2001). Learning Kernel Classifiers
Theory and Algorithms, MIT Press.
O uso combinado das técnicas de aprendizado supervisionado e processamento digital de imagens
se mostrou promissor na solução deste problema.
O modelo YCbCr utilizado no préprocessamento das imagem tornou as classes
mais separáveis, resultando em uma segmentação
por cores mais robusta.
A utilização da máquina de vetores de suporte
em conjunto com a utilização de operadores morfológicos e transformada watershed, reduziram os
ruı́dos na segmentação e identificaram de forma
adequada as regiões de interesse.
No futuro o processo de segmentação pode ser
aperfeiçoado e modificado através da inserção de
novos elementos restritivos para novas aplicações.
Katti Facelli, Ana Carolins Lorena, J. G. A. C.
P. L. F. d. C. (2011). Inteligência Artificial
- Uma abordagem de Aprendizado de Máquinas, 1 edn, GEN.
Agradecimentos
Mercer, J. (1909). Functions of positive and negative type, and their connection with the
theory of integral equations, 209: 441–458.
Este trabalho foi financiado pelo Conselho Nacional de Desenvolvimento Cientı́fico e Tecnológico
(CNPq).
Os autores gostariam de agradecer ao departamento de odontologia da Universidade Federal
do Rio Grande do Norte - UFRN pela idealização
desse trabalho e por toda assistência fornecida.
Li, H., Guo, L., Chen, T., Wang, X. and Yang, L.
(2010). The corner detector of teeth image
based on the improved SUSAN algorithm,
3rd International Conference on Biomedical
Engineering and Informatic 2: 609–612.
Mahsa Sepehrian, Ali M. Deylami, R. A. Z.
(2013). Individual Teeth Segmentation in
CBCT and MSCT Dental Images Using Watershed, 20th Iranian Conference on Biomedical Engineering pp. 27–30.
Meyer, F. (1994). Topographic distance and watershed lines, Signal Processing 38: 113–225.
Soille, P. (2002). Morphological Image Analysis, 2
edn, Springer.
Refer^
encias
Vapnick, V. (1995). The nature of statistical learning theory, Springer-Verlag .
Acharya, T. and Tsai, P.-S. (2005). JPEG2000
Standard for Image Compression: Concepts,
Algorithms and VLSI Architectures, 1 edn,
Wiley.
Verbeek, P. W. and Verwer, B. (1990). Shading
from shape, the eikonal equation solved by
grey-weighted distance transform, pp. 681–
690.
Beare, R. and Lehmann, G. (2006). The watershed
transform in itk - discussion and new developments, Insight Journal [Online] Available
from: http://hdl.handle.net/1926/202 .