Recorte automático de formas arbitrarias

14

Tengo una forma arbitraria definida por una máscara binaria (gris = forma, negro = fondo).

Me gustaría encontrar un rectángulo más grande posible que contenga solo píxeles grises (dicho rectángulo se muestra en amarillo):

ingrese la descripción de la imagen aquí

La forma siempre es "de una pieza", pero no es necesariamente convexa (no todos los pares de puntos en el límite de la forma se pueden conectar mediante una línea recta que atraviese la forma).

A veces existen muchos de estos "rectángulos máximos" y luego se pueden introducir más restricciones, como:

  • Tomar el rectángulo con su centro más cercano al centro de masa de la forma (o centro de la imagen)
  • Tomar un rectángulo con una relación de aspecto más cercana a una relación predefinida (es decir, 4: 3)

ingrese la descripción de la imagen aquí

Mi primer pensamiento sobre el algoritmo es el siguiente:

  1. Calcule la transformación de distancia de la forma y encuentre su centro de masa
  2. Crecer área cuadrada mientras contiene solo píxeles de forma
  3. Haga crecer el rectángulo (originalmente un cuadrado) en ancho o alto mientras contiene solo píxeles de forma.

Sin embargo, creo que dicho algoritmo sería lento y no conduciría a una solución óptima.

¿Alguna sugerencia?

Libor
fuente
2
¿Esto es útil? mathworks.com/matlabcentral/fileexchange/…
Atul Ingle
@AtulIngle Extactly! Gracias. ¿Podría agregar la respuesta para que pueda aceptarla? Luego trataré de editar la respuesta para elaborar más sobre el algoritmo, pero no quiero responder mi propia pregunta utilizando el enlace que proporcionó ...
Libor
¡Excelente! Espero leer su elaborada respuesta ya que no he leído el código.
Atul Ingle
@AtulIngle OK, he agregado un poco de discusión en la respuesta y enlace a un artículo completo mío.
Libor

Respuestas:

10

Hay un código en Matlab Fileexchange que es relevante para su problema: http://www.mathworks.com/matlabcentral/fileexchange/28155-inscriptionsrectangle/content/html/Inscriptions_Rectangle_demo.html

Actualizar

Escribí este artículo tutorial sobre el cálculo de los rectángulos inscritos más grandes basado en el enlace anterior de Atul Ingle.

El algoritmo primero busca los cuadrados más grandes en una máscara binaria. Esto se hace usando un algoritmo de programación dinámica simple. Cada nuevo píxel se actualiza utilizando los tres vecinos ya conocidos:

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

ingrese la descripción de la imagen aquí

La máscara binaria de muestra y el mapa calculado se ven así:

ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí

Tomar el máximo en el mapa revela el cuadrado inscrito más grande:

ingrese la descripción de la imagen aquí

El algoritmo de búsqueda de rectángulos escanea la máscara dos veces más buscando dos clases de rectángulos:

  • ancho mayor que el tamaño del cuadrado (y altura posiblemente menor)
  • altura mayor que el tamaño del cuadrado (y ancho posiblemente menor)

Ambas clases están delimitadas por los cuadrados más grandes ya que ningún rectángulo en un punto dado puede tener ambas dimensiones mayores que el cuadrado inscrito (aunque una dimensión puede ser más grande).

Hay que elegir alguna métrica para los tamaños de rectángulo, como área, circunferencia o suma ponderada de dimensiones.

Aquí está el mapa resultante para rectángulos:

ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí

Es conveniente almacenar la posición y el tamaño del mejor rectángulo encontrado hasta ahora en una variable en lugar de construir mapas y luego buscar máximos.

ingrese la descripción de la imagen aquí

La aplicación práctica de este algoritmo es recortar imágenes no rectangulares. He usado este algoritmo en mi biblioteca de costura de imágenes SharpStitch :

ingrese la descripción de la imagen aquí

Atul Ingle
fuente