Cuadro delimitador mínimo: Revelando el poder de la optimización espacial en la visión por computadora

Por Fouad Sabry

¿Qué es el cuadro delimitador mínimo?

En geometría, el cuadro delimitador mínimo o el cuadro delimitador más pequeño para un conjunto de puntos S en N dimensiones es el cuadro con la medida más pequeña dentro de la cual todos los puntos mienten. Cuando se utilizan otros tipos de medidas, el cuadro mínimo generalmente se denomina en consecuencia, por ejemplo, "cuadro delimitador de perímetro mínimo".

Cómo se beneficiará

(I) Información y validaciones sobre los siguientes temas:

Capítulo 1: Cuadro delimitador mínimo

Capítulo 2: Casco convexo

Capítulo 3: Detección de colisiones

Capítulo 4: Geometría computacional

Capítulo 5: Volumen delimitador

Capítulo 6: Esfera delimitadora

Capítulo 7: Árbol R

Capítulo 8: Politopo convexo

Capítulo 9: Rectángulo delimitador mínimo

Capítulo 10: Algoritmos de casco convexo

(II) Respondiendo al público Preguntas principales sobre el cuadro delimitador mínimo.

(III) Ejemplos del mundo real sobre el uso del cuadro delimitador mínimo en muchos campos.

Para quién es este libro

Profesionales, estudiantes de pregrado y posgrado, entusiastas, aficionados y aquellos que quieran ir más allá del conocimiento o la información básica para cualquier tipo de cuadro delimitador mínimo.

 

 

• Idioma: Español
• Editorial: Mil Millones De Conocimientos [Spanish]
• Fecha de lanzamiento: 5 may 2024

Vista previa del libro

Capítulo 1: Cuadro delimitador mínimo

El cuadro delimitador o envolvente más bajo o más pequeño de un conjunto de puntos S en N cotas es el cuadro con la medida más pequeña (área, volumen o hipervolumen en cotas superiores) que contiene todos los puntos. Cuando se emplean diferentes unidades de medida, el cuadro mínimo se denomina típicamente cuadro delimitador de perímetro mínimo.

El hecho de que el cuadro delimitador mínimo de un conjunto de puntos sea idéntico al cuadro delimitador mínimo de su envoltura convexa se puede aprovechar para acelerar los cálculos.

Las etiquetas caja e hiperrectángulo se derivan de su uso en el sistema de coordenadas cartesianas, donde se representan como un rectángulo (caso bidimensional), paralelepípedo rectangular (instancia tridimensional), etc.

En dos dimensiones, se denomina rectángulo delimitador mínimo.

El cuadro delimitador mínimo alineado con el eje (o AABB) para un conjunto de puntos determinado es el cuadro delimitador mínimo cuyos bordes son paralelos a los ejes de coordenadas (cartesianas). Es el producto cartesiano de N intervalos determinado por el valor mínimo y máximo de la coordenada asociada para cada punto en S.

Los cuadros delimitadores mínimos alineados con los ejes se utilizan para aproximarse a la ubicación de un objeto y para describir su forma de una manera muy básica. En geometría computacional y sus aplicaciones, por ejemplo, cuando es necesario localizar intersecciones en un grupo de objetos, las intersecciones entre sus MBB sirven como comprobación inicial. Debido al hecho de que suele ser una operación considerablemente menos costosa que la comprobación de intersección real (porque simplemente requiere comparaciones de coordenadas), permite omitir rápidamente las comprobaciones de emparejamientos que están muy separados.

El cuadro delimitador mínimo orientado arbitrariamente es el cuadro delimitador mínimo que se calcula sin restricciones de orientación. Los algoritmos de cuadro delimitador mínimo basados en el método de calibradores giratorios pueden encontrar el cuadro delimitador de área mínima o perímetro mínimo de un polígono convexo bidimensional en tiempo lineal y de un punto tridimensional establecido en el tiempo requerido para construir su envoltura convexa seguido de un cálculo de tiempo lineal.

Cuando un objeto tiene su propio sistema de coordenadas local, puede ser ventajoso guardar un cuadro delimitador relativo a estos ejes, que no requiere transformación a medida que cambia la propia transformación del objeto.

En el procesamiento digital de imágenes, el cuadro delimitador es simplemente las coordenadas del borde rectangular que encierra completamente una imagen digital cuando se muestra en una página, lienzo, pantalla u otro fondo bidimensional.

{Fin del capítulo 1}

Capítulo 2: Casco convexo

La envoltura convexa, la envoltura convexa o el cierre convexo de una forma en geometría es el conjunto convexo más pequeño que contiene la forma. La envoltura convexa puede definirse como la intersección de todos los conjuntos convexos que contienen un subconjunto particular de un espacio euclídeo, o como el conjunto de todas las combinaciones convexas de puntos en el subconjunto. Para un subconjunto acotado del plano, el casco convexo se puede ver como la forma contenida por una banda elástica extendida.

Los conjuntos abiertos son los cascos convexos de los conjuntos abiertos, y los conjuntos compactos tienen cascos convexos que son compactos.

Cada conjunto compacto convexo es el casco convexo de sus extremidades.

El operador de casco convexo es un ejemplo de operador de cierre, cada antimatroide se puede representar aplicando este operador de cierre a conjuntos de puntos finitos.

Encontrar la envoltura convexa de un número finito de puntos en el plano u otros espacios euclidianos de baja dimensión presenta desafíos algorítmicos, y el doble problema de la superposición de semiespacios, son problemas esenciales de geometría computacional.

Pueden resolverse en el tiempo O(n\log n) para conjuntos de puntos bidimensionales o tridimensionales, y en el tiempo coincidiendo con la complejidad de salida del peor de los casos dada por el teorema del límite superior en dimensiones superiores.

Las envolturas convexas también se han explorado para polígonos simples, movimiento browniano, curvas espaciales y epígrafes de funciones, además de conjuntos de puntos finitos. En matemáticas, estadística, optimización combinatoria, economía, modelado geométrico y etología, los cascos convexos tienen numerosos usos. El cráneo convexo, el casco convexo ortogonal, las capas convexas, la triangulación de Delaunay y el diagrama de Voronoi son estructuras relacionadas.

Una colección de puntos en un espacio euclidiano es convexa si contiene los segmentos de recta que conectan cada par de sus puntos.

La envoltura convexa de un conjunto dado X puede definirse como:

El conjunto convexo mínimo (único) que contiene X

La intersección de todos los conjuntos convexos que contienen X

El conjunto de todas las combinaciones convexas de puntos en X

La unión de todos los simplices con vértices en X

Para conjuntos que están limitados en el plano euclidiano, no en una sola línea, el límite de la envoltura convexa es la curva cerrada simple con un perímetro mínimo que contiene X .

Uno puede imaginar estirar una banda elástica para que rodee todo el conjunto S y luego soltarla, permitiendo que se encoja; cuando se aprieta, encierra el casco convexo de S .

En el caso de los objetos tridimensionales, la definición inicial de la envoltura convexa especifica que es el volumen delimitador convexo más pequeño posible. La definición que utiliza intersecciones de conjuntos convexos puede extenderse a geometría no euclidiana, y la definición que utiliza combinaciones convexas puede extenderse desde espacios euclidianos a espacios vectoriales reales arbitrarios o espacios afines; Las cascas convexas también se pueden generalizar abstractamente a las matroides orientadas.

No es obvio que la primera definición tenga sentido: ¿por qué debería existir un único conjunto convexo mínimo que contenga X , para cada X ? Sin embargo, la segunda acepción, la intersección de todos los conjuntos convexos que contienen X , está claramente definida.

Es un subconjunto de todos los demás conjuntos convexos Y que contienen X , porque Y se incluye entre los conjuntos que se intersecan.

Por lo tanto, es exactamente el único conjunto convexo mínimo que contiene X .

Por lo tanto, las dos definiciones iniciales son idénticas.

Cada conjunto convexo que contiene X debe (asumiendo que es convexo) contener todas las combinaciones convexas de puntos en X , por lo que el conjunto de todas las combinaciones convexas está contenido en la