Corte automático de formas arbitrárias

14

Eu tenho uma forma arbitrária definida por uma máscara binária (cinza = forma, preto = plano de fundo).

Gostaria de encontrar o maior retângulo possível contendo apenas pixels cinza (esse retângulo é retratado em amarelo):

insira a descrição da imagem aqui

A forma é sempre "uma peça", mas não é necessariamente convexa (nem todos os pares de pontos no limite da forma podem ser conectados por uma linha reta que passa pela forma).

Às vezes, muitos desses "retângulos máximos" existem e outras restrições podem ser introduzidas, como:

  • Tomando o retângulo com o centro mais próximo do centro de massa da forma (ou centro da imagem)
  • Tomando o retângulo com a proporção mais próxima de uma proporção predefinida (ou seja 4: 3)

insira a descrição da imagem aqui

Meu primeiro pensamento sobre o algoritmo é o seguinte:

  1. Calcule a transformação da distância da forma e encontre seu centro de massa
  2. Aumente a área quadrada enquanto ela contém apenas os pixels da forma
  3. Aumente o retângulo (originalmente um quadrado) em largura ou altura, enquanto ele contém apenas os pixels da forma.

No entanto, acho que esse algoritmo seria lento e não levaria à solução ideal.

Alguma sugestão?

Libor
fonte
2
Isso é útil? mathworks.com/matlabcentral/fileexchange/...
Atul Ingle
@AtulIngle Extactly! Obrigado. Você poderia adicionar a resposta para que eu possa aceitá-la? Vou então tentar editar a resposta para elaborar mais sobre o algoritmo - mas eu não quero apenas responder a minha própria pergunta usando o link fornecido ...
Libor
Ótimo! Espero ler sua resposta elaborada, pois ainda não li o código.
Atul Ingle
@AtulIngle OK, adicionei algumas discussões na resposta e um link para um artigo completo.
Libor

Respostas:

10

Existe um código no Matlab Fileexchange que é relevante para o seu problema: http://www.mathworks.com/matlabcentral/fileexchange/28155-inscribrectangle/content/html/Inscrib_Rectangle_demo.html

Atualizar

Eu escrevi este artigo tutorial sobre como calcular os maiores retângulos inscritos com base no link acima de Atul Ingle.

O algoritmo procura primeiro os maiores quadrados em uma máscara binária. Isso é feito usando um algoritmo de programação dinâmica simples. Cada novo pixel é atualizado usando os três vizinhos já conhecidos:

squares[x,y] = min(squares[x+1,y], squares[x,y+1], squares[x+1,y+1]) + 1

insira a descrição da imagem aqui

A máscara binária de amostra e o mapa computado são assim:

insira a descrição da imagem aqui insira a descrição da imagem aqui

Tomar o máximo no mapa revela o maior quadrado inscrito:

insira a descrição da imagem aqui

O algoritmo de busca de retângulos que varre a máscara mais duas vezes procurando duas classes de retângulos:

  • largura maior que o tamanho do quadrado (e altura possivelmente menor)
  • altura maior que o tamanho do quadrado (e largura possivelmente menor)

Ambas as classes são delimitadas pelos quadrados maiores, pois nenhum retângulo em um determinado ponto pode ter ambas as dimensões maiores que o quadrado inscrito (embora uma dimensão possa ser maior).

É preciso escolher alguma métrica para os tamanhos dos retângulos, como área, circunferência ou soma ponderada das dimensões.

Aqui está o mapa resultante para retângulos:

insira a descrição da imagem aqui insira a descrição da imagem aqui

É conveniente armazenar a posição e o tamanho do melhor retângulo encontrado até agora em uma variável, em vez de criar mapas e depois procurar o máximo.

insira a descrição da imagem aqui

A aplicação prática desse algoritmo é cortar imagens não retangulares. Eu usei esse algoritmo na minha biblioteca de costura de imagens SharpStitch :

insira a descrição da imagem aqui

Atul Ingle
fonte