O primeiro problema do algoritmo de preenchimento com blocos, j´a descrito anteri-
ormente, ´e que aquando da existˆencia de grandes descontinuidades os blocos ultrapassam
as estremas de pr´edio. O algoritmo de Lohmann [77] ´e assim utilizado para segmentar as
ideias-chave s˜ao utilizar a transformada da distˆancia da imagem (ver figura 6.7(a)) para
encontrar rapidamente a distˆancia entre um ponto e o seu vizinho mais pr´oximo e por outro
lado, a ideia de cobrir a regi˜ao com discos m´aximos, uma vez que a utilizac¸˜ao de discos
permite detectar grandes descontinuidades no contorno.
(a) A detecc¸˜ao dos valo- res m´aximos nos pontos da circunferˆencia.
(b) A detecc¸˜ao dos extre- mos nos pontos da circun- ferˆencia.
Figura 6.7: Na primeira iterac¸˜ao do algoritmo de Lohmann s˜ao detectados os extremos do c´ırculo m´aximo centrado na posic¸˜ao do m´aximo local.
Este algoritmo necessita de trˆes parˆametros para iniciar o processamento, nomeada-
mente um ponto dentro do contorno, o tamanho m´ınimo do disco aceite e o tamanho
m´aximo da descontinuidade aceite. O tamanho m´ınimo do disco aceite permite obter mais
ou menos detalhe na cobertura da regi˜ao, enquanto o tamanho da m´axima descontinuidade
aceite permite controlar se a descontinuidade do contorno ´e realmente uma descontinui-
dade ou uma caracter´ıstica do contorno. As zonas mais fechadas s˜ao exemplos disso e
dependendo do valor da m´axima descontinuidade permitida, podem ser consideradas como
descontinuidades ou como caracter´ısticas do contorno.
Tal como o m´etodo de preenchimento com blocos, este algoritmo comec¸a a segmentac¸˜ao
Lohmann foi ligeiramente optimizado comec¸ando no m´aximo local ao inv´es de comec¸ar
no ponto inicial, tal como no algoritmo original. Deste modo, a partir do ponto inicial
´e seguido o gradiente m´aximo na imagem da transformada da distˆancia e at´e encontrar
o m´aximo local. O m´etodo converge de forma mais c´elere comec¸ando no m´aximo local
ao inv´es do ponto inicial, uma vez que o primeiro disco tem a´ı o seu raio m´aximo (ver
figura 6.7(a)) e a regi˜ao ´e mais rapidamente coberta usando o maior disco inicial.
O algoritmo de Lohmann inicia o seu processamento num ponto dentro do contorno
e para esse ponto ´e calculado o m´aximo local seguindo o gradiente da imagem da trans-
formada da distˆancia, i.e., onde o disco tem o seu m´aximo raio. Na posic¸˜ao do m´aximo
local, s˜ao obtidos todos os pontos da m´axima circunferˆencia, de modo a que por um lado,
identifique poss´ıveis pontos de descontinuidade no contorno (pontos terminais) e por outro,
encontre os m´aximos locais da circunferˆencia de modo, a utilizar estes pontos para preen-
cher novos discos centrados nestas posic¸˜oes. Tanto o teste `a descontinuidade assim como o
teste `a verificac¸˜ao se o c´ırculo encontra-se dentro do pr´edio, s˜ao utilizados para os pontos
terminais, com os objectivos de detectar se a posic¸˜ao do disco est´a dentro do contorno e
se o tamanho da descontinuidade ´e aceit´avel. Se o disco n˜ao for descartado, por estar fora
da regi˜ao, ´e realizada uma nova procura na imagem da transformada da distˆancia de modo
a encontrar os m´aximos locais no limite do disco e todos estes m´aximos s˜ao adicionados
novamente `a stack (ver figura 6.7(b)). Uma vez que a imagem da transformada da distˆancia
´e marcada com pixeis a preto para todos os discos encontrados (ver figura 6.8(a)), a regi˜ao
´e coberta, obtendo-se assim uma regi˜ao fechada dentro do pr´edio (ver figura 6.8(b)). O
processo ´e iterativo e apenas acaba quando a stack n˜ao tiver pontos da posic¸˜ao central de
(a) A imagem da transfor- mada da distˆancia ap´os 21 iterac¸˜oes.
(b) O contorno aberto ´e segmentado cobrindo a regi˜ao com discos.
Figura 6.8: O resultado do algoritmo de Lohmann aplicado ao contorno com grandes descontinuidades.
Os dois m´etodos que afectam directamente a performance do algoritmo s˜ao a detecc¸˜ao
dos m´aximos locais e o teste que verifica se o c´ırculo est´a dentro ou fora do contorno. Estes
dois m´etodos s˜ao bastante sens´ıveis e necessitam de ser devidamente testados de modo a
obter-se os melhores resultados.
O procedimento que verifica se um ponto est´a ou n˜ao dentro da regi˜ao do contorno ´e
usado para verificar se um disco est´a dentro ou fora do contorno (ver figura 6.9). Para
encontrar a linha da descontinuidade s˜ao utilizados o ponto de descontinuidade da circun-
ferˆencia do disco e o vizinho mais pr´oximo do contorno, de maneira a medir o tamanho da
descontinuidade. Se a linha recta que junta os dois pontos est´a dentro da regi˜ao relativa-
mente ao centro do disco, ent˜ao o disco ´e rejeitado.
A detecc¸˜ao dos m´aximos locais ´e implementada colocando os valores da transformada
da distˆancia dos limites da circunferˆencia dentro de uma lista circular. Os valores na lista
s˜ao suavizados e os picos s˜ao encontrados considerando a concavidade dos valores (ver
Figura 6.9: O teste dentro do pr´edio verifica se um circulo est´a dentro ou fora da regi˜ao.
Depois de obter a lista de c´ırculos que segmentam o contorno fechado, podemos con-
siderar os blocos obtidos do algoritmo de preenchimento com blocos, mas apenas conside-
rando os blocos que est˜ao dentro de pelo menos um desses c´ırculos. Deste modo podemos
utilizar o algoritmo de preenchimento com blocos para detectar os pontos do contorno den-
tro do pr´edio, mesmo tendo grandes descontinuidades.
Este algoritmo apresenta algumas desvantagens, nomeadamente contornos com zo-
nas mais fechadas s˜ao consideradas como zonas com descontinuidades, uma vez que os
parˆametros de threshold n˜ao s˜ao adaptativos. E adicionalmente, o m´etodo n˜ao considera
elementos conexos ao contorno.