El Fin Del Conocimiento - Bóveda 5/4 - CVPR - 2015 - Maximización del Consenso Globalmente Óptima Eficiente con Búsqueda en Árbol

graph LR classDef consensus fill:#f9d4d4, font-weight:bold, font-size:14px classDef residuals fill:#d4f9d4, font-weight:bold, font-size:14px classDef algorithm fill:#d4d4f9, font-weight:bold, font-size:14px classDef search fill:#f9f9d4, font-weight:bold, font-size:14px classDef generalization fill:#f9d4f9, font-weight:bold, font-size:14px A["Maximización del Consenso
Globalmente Óptima Eficiente con
Búsqueda en Árbol"] --> B["Consenso máximo: encontrar parámetros
del modelo que concuerden 1"] B --> C["Ajuste de línea consenso
máximo 2"] B --> D["Visión por computador consenso
máximo 3"] B --> E["Ejemplo de regresión lineal
1D 4"] A --> F["Residual: distancia vertical
punto-línea 5"] F --> G["RANSAC: subconjuntos, sin
garantía global 6"] F --> H["Min-max: minimizar el mayor
residual 7"] H --> I["L-infinito: dos máximos
residuales 8"] F --> J["Espacio de parámetros: residuales
en forma de V 9"] J --> K["Máximo de curvas en V: convexo,
programación lineal 10"] K --> L["Simplex: curva convexa
de vértice a vértice 11"] H --> M["Conjunto de soporte: puntos
solución min-max 12"] M --> N["Dimensión combinatoria: tamaño del
conjunto de soporte 13"] B --> O["Consenso máximo: residual,
tamaño p+1 14"] A --> P["Algoritmo: p+1 subconjuntos, min-max,
, cobertura 15"] P --> Q["Subconjuntos: polinomial en
p+1 16"] B --> R["Regresión lineal consenso máximo:
no NP-difícil 17"] F --> S["Funciones residuales: árbol
de bases 18"] S --> T["Raíz: min-max. Hijos:
eliminación de puntos 19"] S --> U["Nivel: puntos fuera de cobertura.
Factible:20"] P --> V["Objetivo: nivel más bajo
de base factible 21"] A --> W["Búsqueda en anchura: base
factible más baja 22"] A --> X["Un nivel + heurística
de factibilidad 23"] X --> Y["Heurística: bases eliminadas.
Admisible: optimalidad 24"] P --> Z["Límite de ratio de atípicos:
1/p+1 25"] A --> AA["Generaliza a residuales pseudo-convexos
26"] AA --> AB["Pseudo-convexo -conjuntos de nivel:
convexo 27"] AA --> AC["Funciones pseudo-convexas: optimización
iterativa rápida 28"] AA --> AD["Pseudo-convexo: estructura de árbol,
métodos de búsqueda 29"] B --> AE["Múltiples hipótesis: tiempo de ejecución aumentado,
solución exacta 30"] class A,B,C,D,E,O,R consensus class F,G,H,I,J,S,T,U residuals class P,Q,V,Z algorithm class W,X,Y search class AA,AB,AC,AD,AE generalization

Resumen:

1.- Problema de consenso máximo: encontrar parámetros del modelo que concuerden con el máximo número de puntos de datos.

2.- Ejemplo de ajuste de línea de consenso máximo.

3.- La triangulación y el ajuste de homografía son ejemplos prácticos de visión por computador de consenso máximo.

4.- La regresión lineal 1D es el ejemplo en ejecución utilizado para ilustrar ideas.

5.- El residual es la distancia vertical de un punto a la línea estimada.

6.- RANSAC toma muestras de subconjuntos mínimos para ajustar modelos pero no garantiza encontrar el consenso máximo global.

7.- El problema min-max minimiza el mayor residual (minimización L-infinito o regresión de Chebyshev).

8.- La solución L-infinito tiene dos puntos con el mismo residual máximo siendo minimizado.

9.- Graficar residuales en el espacio de parámetros produce curvas en forma de V para cada punto de datos.

10.- El máximo de las curvas en V es convexo y el problema min-max puede resolverse mediante programación lineal.

11.- El algoritmo Simplex es equivalente a descender la curva convexa de vértice a vértice.

12.- Dos puntos que forman la solución min-max son el conjunto activo, base o conjunto de soporte.

13.- La dimensión combinatoria es el tamaño del conjunto de soporte (p+1).

14.- Dado el conjunto de consenso máximo, la solución min-max en él tiene residual ≤ ε y un conjunto de soporte de tamaño p+1.

15.- Algoritmo: enumerar p+1 subconjuntos, resolver min-max, mantener bases con residual ≤ ε, reportar base con mayor cobertura.

16.- El número de subconjuntos es polinomial en p+1 (n elige p+1 o O(n^(p+1))).

17.- El consenso máximo para la regresión lineal no es NP-difícil, contrario a algunas afirmaciones.

18.- Las intersecciones de funciones residuales forman una estructura de árbol de bases.

19.- La base raíz es la solución min-max en el conjunto de datos completo. Las bases hijas se forman eliminando puntos.

20.- El nivel en el árbol de bases indica el número de puntos fuera de cobertura. Las bases factibles tienen residual ≤ ε.

21.- Objetivo: encontrar la base factible de nivel más bajo, garantizando la solución de consenso máximo.

22.- La búsqueda en anchura del árbol de bases nivel por nivel encuentra la base factible más baja.

23.- Una búsqueda prioriza la búsqueda por nivel más una heurística que estima la distancia a la factibilidad.

24.- Heurística: el número de bases eliminadas para alcanzar la factibilidad estima los atípicos. Las heurísticas admisibles garantizan la optimalidad.

25.- El método funciona bien pero la heurística limita el rendimiento si la proporción de atípicos > 1/(p+1).

26.- El enfoque se generaliza más allá de la regresión lineal a residuales pseudo-convexos como el error de transferencia y el error de reproyección.

27.- Los conjuntos de nivel alfa de funciones pseudo-convexas son convexos.

28.- La optimización iterativa encuentra rápidamente el óptimo de funciones pseudo-convexas.

29.- La estructura de árbol y los métodos de búsqueda aún se aplican a los residuales pseudo-convexos.

30.- El algoritmo exacto encuentra el consenso máximo incluso con múltiples hipótesis verdaderas, pero el tiempo de ejecución aumenta debido a más atípicos.

Bóveda de Conocimiento construida porDavid Vivancos 2024