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):
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)
Meu primeiro pensamento sobre o algoritmo é o seguinte:
- Calcule a transformação da distância da forma e encontre seu centro de massa
- Aumente a área quadrada enquanto ela contém apenas os pixels da forma
- 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?
image-processing
image
geometry
Libor
fonte
fonte
Respostas:
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:
A máscara binária de amostra e o mapa computado são assim:
Tomar o máximo no mapa revela o maior quadrado inscrito:
O algoritmo de busca de retângulos que varre a máscara mais duas vezes procurando duas classes de retângulos:
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:
É 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.
A aplicação prática desse algoritmo é cortar imagens não retangulares. Eu usei esse algoritmo na minha biblioteca de costura de imagens SharpStitch :
fonte