Guia Básico de Ajuste de Feixes — Os Mínimos Quadrados Não Lineares que Aprimoram as Poses da Câmera e os Pontos 3D em Conjunto

Contents — find the section you need

As poses da câmera e os pontos 3D que o Structure from Motion e o Visual-SLAM obtêm por meio de triangulação e PnP são, na melhor das hipóteses, valores iniciais aproximados provenientes de aproximações lineares e processamento sequencial. Ruído por imagem, erro de quantização em pontos correspondentes e erro propagado da estimativa sequencial se acumulam, resultando em uma reconstrução internamente inconsistente. O Bundle Adjustment (BA) é a otimização final que resolve essa inconsistência, movendo todos os parâmetros da câmera e todos os pontos 3D simultaneamente, minimizando a soma do erro de reprojeção em todos os pontos observados. O nome "bundle" vem do ajuste do feixe de raios de luz que vai de cada ponto 3D para cada câmera, todos ao mesmo tempo, para que coincidam com as posições observadas.

0. Resumo de 30 segundos

O Ajuste de Feixe é um problema de mínimos quadrados não linear cujas incógnitas são os parâmetros intrínsecos/extrínsecos das câmeras e as coordenadas dos pontos 3D, minimizando a soma dos quadrados dos erros de reprojeção em todas as observações.
Ele é resolvido iterativamente com o método de Gauss-Newton ou Levenberg-Marquardt (LM). O LM interpola suavemente, por meio de um parâmetro $\lambda$ , entre o método de Gauss-Newton, instável, porém rápido, e o método do gradiente descendente, lento, porém estável.
Como uma única câmera está sempre vinculada apenas aos pontos que ela realmente captou, a aproximação da Jacobiana e da Hessiana assume uma forma esparsa, estruturada em blocos, organizada por câmera × ponto. Essa esparsidade é a chave que torna os problemas de grande escala tratáveis.
O truque do complemento de Schur explora o fato de que os blocos de pontos 3D são mutuamente independentes (diagonal de bloco), eliminando os pontos primeiro para resolver um pequeno "sistema de câmera reduzido" envolvendo apenas as câmeras. Isso é o que torna possível resolver problemas na escala de dezenas de milhares de pontos e milhares de câmeras em tempo realista.
O Bundle Adjustment é um parente próximo da otimização do Pose Graph do SLAM, diferindo no fato de que suas incógnitas incluem os próprios pontos 3D. É uma tecnologia fundamental compartilhada, usada tanto para finalizar o SfM quanto para a otimização local/global do SLAM.

1. O que ele recebe como entrada e o que ele resolve?

A entrada consiste nas três estimativas iniciais a seguir, obtidas como resultados intermediários de SfM ou Visual-SLAM:

Valores iniciais para as poses da câmera $\{K_i, R_i, \mathbf{t}_i\}$ ( $i=1,\dots,m$ ; em muitos casos, os parâmetros intrínsecos $K_i$ são conhecidos ou fixos)
Valores iniciais para os pontos 3D $\{\mathbf{X}_j\}$ ( $j=1,\dots,n$ ; coordenadas aproximadas obtidas por triangulação)
A correspondência de qual câmera observou qual ponto — ou seja, as coordenadas da imagem $\mathbf{u}_{ij}$ para cada observação (a posição do pixel em que a câmera $i$ viu o ponto $j$ )

A saída são as poses da câmera e os pontos 3D pontos, todos ajustados simultaneamente com precisão, que são mais consistentes internamente em todas as observações. O fato de o Ajuste de Feixe não ser um método para construir uma solução do zero, mas sim uma otimização final que aprimora localmente um valor inicial já "aproximadamente correto", é importante para a discussão sobre convergência abaixo.

2. A Função de Custo: Erro de Reprojeção

A discrepância entre onde um ponto 3D $\mathbf{X}_j$ é projetado na câmera $i$ e a coordenada da imagem observada $\mathbf{u}_{ij}$ é chamada de erro de reprojeção. Escrevendo a pose da câmera $i$ como $R_i, \mathbf{t}_i$ e a função de projeção como $\pi(\cdot)$ (o mapa não linear que converte coordenadas homogêneas em coordenadas de pixel), o resíduo para uma observação é

r_{ij} = \pi\big(K_i(R_i\mathbf{X}_j + \mathbf{t}_i)\big) - \mathbf{u}_{ij}

O Ajuste de Feixe minimiza a soma dos quadrados desse resíduo em todo o conjunto de pares observados $\mathcal{O}=\{(i,j)\}$ .

\min_{\{K_i,R_i,\mathbf{t}_i,\mathbf{X}_j\}}\sum_{(i,j)\in\mathcal{O}}\rho\left(\|r_{ij}\|^2\right)

$\rho$ é uma função de perda robusta, como a perda de Huber, que impede que um único valor discrepante significativo, resultante de uma incompatibilidade, distorça toda a otimização. Esta equação tem exatamente a mesma forma já vista no Guia Introdutório de SfM — o Ajuste de Feixe lida com o núcleo computacional da resolução deste problema de minimização.

3. Resolvendo por Mínimos Quadrados Não Lineares: De Gauss-Newton a Levenberg-Marquardt

Agrupando todas as incógnitas em um único vetor $\mathbf{x}$ (todas as poses da câmera e todos os pontos 3D dispostos juntos) e escrevendo todo o conjunto de resíduos como $\mathbf{r}(\mathbf{x})$ , o objetivo da minimização é $\|\mathbf{r}(\mathbf{x})\|^2$ . Como $\mathbf{r}$ é não linear, usamos uma expansão de Taylor de primeira ordem em torno da estimativa atual $\mathbf{x}_k$ : $\mathbf{r}(\mathbf{x}_k+\Delta\mathbf{x})\approx \mathbf{r}(\mathbf{x}_k)+J\Delta\mathbf{x}$ . $J=\partial \mathbf{r}/\partial \mathbf{x}$ é a matriz Jacobiana. Substituindo isso e resolvendo para $\Delta\mathbf{x}$ , obtemos a equação normal do método de Gauss-Newton:

(J^\mathsf{T}J)\,\Delta\mathbf{x} = -J^\mathsf{T}\mathbf{r}

$H=J^\mathsf{T}J$ é a aproximação da matriz Hessiana (a aproximação de Gauss-Newton, ignorando termos de segunda ordem). Resolver essa equação para $\Delta\mathbf{x}$ , atualizar $\mathbf{x}_{k+1}=\mathbf{x}_k+\Delta\mathbf{x}$ e repetir essa operação até que o resíduo convirja é o procedimento completo.

O método de Gauss-Newton converge rapidamente quando o valor inicial está próximo da solução, mas tende a divergir com um valor inicial inadequado. O método de Levenberg-Marquardt (LM), proposto independentemente por Levenberg (1944) e Marquardt (1963), atenua esse problema adicionando um termo de amortecimento à equação normal.

(J^\mathsf{T}J + \lambda D)\,\Delta\mathbf{x} = -J^\mathsf{T}\mathbf{r}

$D$ geralmente é a diagonal de $J^\mathsf{T}J$ (ou uma matriz de escala equivalente), e $\lambda$ é o coeficiente de amortecimento. Quando $\lambda$ é pequeno, o comportamento se aproxima do método de Gauss-Newton e converge rapidamente; quando $\lambda$ é grande, o algoritmo dá passos pequenos e seguros, aproximando-se do método do gradiente descendente. Através de um esquema de controle adaptativo — que reduz $\lambda$ para acelerar sempre que o custo diminui a cada iteração, e aumenta $\lambda$ para rejeitar e encurtar o passo sempre que o custo aumenta — o método de Lewis-McChalmers (LM) concilia a velocidade do método de Gauss-Newton com a estabilidade do método do gradiente descendente. Quase todas as implementações práticas de Ajuste de Feixe (Ceres Solver, g2o, SBA e outras, discutidas abaixo) adotam o método LM ou um método de região de confiança intimamente relacionado.

4. Por que a Jacobiana é Esparsa?

As incógnitas do Ajuste de Feixe são a pose da câmera (6 graus de liberdade — 3 rotações mais 3 translações, se os parâmetros intrínsecos forem fixos) × $m$ câmeras e o ponto 3D (3 graus de liberdade) × $n$ pontos, totalizando até $6m+3n$ dimensões. Em problemas reais de SfM com dezenas de milhares de observações ou mais, tratar ingenuamente essa $J^\mathsf{T}J$ como uma matriz densa custa $O((6m+3n)^3)$ — não solucionável em tempo realista.

O que resolve o problema aqui é a estrutura em que o erro de reprojeção $r_{ij}$ "depende apenas dos parâmetros da câmera $i$ e dos parâmetros do ponto $j$ ". As derivadas parciais em relação a qualquer outra câmera $k\neq i$ ou ponto $l\neq j$ são identicamente zero.

\frac{\partial r_{ij}}{\partial \mathbf{x}_{\text{camera }k}} = 0 \ (k\neq i), \qquad \frac{\partial r_{ij}}{\partial \mathbf{X}_l} = 0 \ (l\neq j)

Em outras palavras, a linha da matriz Jacobiana gerada por uma única observação possui entradas diferentes de zero apenas no bloco correspondente à câmera e no bloco correspondente ao ponto. O número de linhas cresce proporcionalmente ao número de observações, mas o número de entradas diferentes de zero por linha permanece constante (câmera 6 + ponto 3, ou um pouco mais se os parâmetros intrínsecos forem incluídos). Essa esparsidade se manifesta, ao observar $J^\mathsf{T}J$ , na seguinte estrutura de blocos.

J^\mathsf{T}J = \begin{pmatrix} B & E \\ E^\mathsf{T} & C \end{pmatrix}

$B$ : interações entre os parâmetros da câmera. Este valor é zero, a menos que as câmeras $i$ e $k$ observem um ponto em comum, portanto, possui uma estrutura de blocos esparsos.
$C$ : interações entre os parâmetros de pontos 3D. Como os 3 graus de liberdade de um ponto $j$ nunca estão acoplados a nenhum outro ponto, esta é uma matriz diagonal em blocos — a premissa para o truque do complemento de Schur na próxima seção.
$E$ : interações entre câmeras e pontos (um bloco diferente de zero aparece para cada observação $(i,j)$ ).

5. O Pipeline Básico

O Bundle Adjustment refina conjuntamente as poses da câmera e os pontos 3D, formando repetidamente resíduos de reprojeção e um Jacobiano esparso, resolvendo através do complemento de Schur e aplicando uma etapa LM

r_{ij}

Sparse Jacobiancamera × pointblock structure Eliminate points viaSchur complement,reduced camera system Adjust

\lambda

viaLM method,update

\Delta\mathbf{x}

Checkconvergence

Cada iteração recalcula o erro de reprojeção, monta o Jacobiano esparso, resolve o sistema reduzido apenas com a câmera por meio do complemento de Schur e atualiza por meio do controle de passo do LM. Isso se repete até que a mudança no custo caia abaixo de um limite ou até que um número máximo de iterações seja atingido.

6. O Truque do Complemento de Schur: Transformando Esparsidade em Computação Reduzida

Usando a estrutura de blocos da seção anterior, podemos escrever a equação normal $(J^\mathsf{T}J+\lambda D)\Delta\mathbf{x}=-J^\mathsf{T}\mathbf{r}$ dividida na atualização da câmera $\Delta\mathbf{c}$ e na atualização do ponto $\Delta\mathbf{p}$ como

\begin{pmatrix} B' & E \\ E^\mathsf{T} & C' \end{pmatrix} \begin{pmatrix} \Delta\mathbf{c} \\ \Delta\mathbf{p} \end{pmatrix} = \begin{pmatrix} v \\ w \end{pmatrix}

(onde $B', C'$ são os blocos após a adição do termo de amortecimento). Como $C'$ é uma matriz diagonal em blocos, independente para cada ponto 3D, cada bloco 3×3 pode ser invertido individualmente, a um custo aproximadamente proporcional ao número de pontos $n$ . Usando esta $C'^{-1}$ para eliminar $\Delta\mathbf{p}$ , obtemos o sistema de câmeras reduzido, envolvendo apenas câmeras:

\left(B' - E C'^{-1}E^\mathsf{T}\right)\Delta\mathbf{c} = v - E C'^{-1}w

O $B'-EC'^{-1}E^\mathsf{T}$ do lado esquerdo é chamado de complemento de Schur. Esta matriz tem tamanho $6m\times 6m$ (dependendo apenas do número de câmeras, não do número de pontos $n$ ), e uma vez que $\Delta\mathbf{c}$ tenha sido resolvido, a atualização de cada ponto pode ser recuperada de forma eficiente com

\Delta\mathbf{p} = C'^{-1}\left(w - E^\mathsf{T}\Delta\mathbf{c}\right)

Em um problema típico de SfM, o número de pontos $n$ pode ser dezenas de vezes maior que o número de câmeras $m$ , então, em vez de resolver ingenuamente um sistema com $6m+3n$ dimensões, você só precisa lidar com o complemento de Schur, de dimensão $6m$ . Esta é a ideia central que torna o Ajuste de Feixe praticamente solucionável mesmo na escala de dezenas de milhares de pontos. Foi teoricamente organizado por Triggs et al. em "Bundle Adjustment — A Modern Synthesis" (2000) e é a implementação interna padrão em bibliotecas atuais como Ceres Solver e g2o.

O Ceres Solver oferece várias opções apenas para resolver este sistema reduzido: DENSE_SCHUR, que o resolve como uma matriz densa (até algumas centenas de câmeras); SPARSE_SCHUR, que explora a esparsidade por meio de reordenação (milhares de câmeras); e ITERATIVE_SCHUR, que aplica o gradiente conjugado ao complemento de Schur (para problemas de escala ainda maior). Escolher entre essas opções com base na escala do problema é uma regra prática.

7. Liberdade de Calibre: as Direções ao Longo das Quais a Solução Não é Determinada de Forma Única

O Bundle Adjustment retém um grau de liberdade que permite mover todo o conjunto de parâmetros sem alterar o valor da função de custo. Mover todas as câmeras e todos os pontos 3D simultaneamente, com a mesma rotação, translação e escala, deixa o erro de reprojeção completamente inalterado (no caso de uma câmera monocular, a escala absoluta também é indeterminada). Esse grau de liberdade é chamado de liberdade de calibre. Se não for tratado, torna o $J^\mathsf{T}J$ singular (com posto deficiente), o que torna a equação normal insolúvel ou numericamente instável.

Na prática, isso é contornado fixando a pose das duas primeiras câmeras ou o comprimento de uma linha de base, ou aproveitando o fato de que o próprio termo de amortecimento do LM $\lambda D$ regulariza implicitamente essa direção singular. Quando informações de escala absoluta ou pose absoluta estão disponíveis — por exemplo, de um GPS ou de uma IMU — é natural usá-las como uma restrição adicional para fixar o calibre.

8. A Diferença em Relação à Otimização do Grafo de Pose

A otimização do Grafo de Pose, abordada no Guia Introdutório de Fechamento de Loop, também pertence à mesma estrutura matemática do Ajuste de Feixe, no sentido de que minimiza, com uma perda robusta, um resíduo de mínimos quadrados não linear construído com o mapa $\mathrm{Log}$ . A diferença reside no que são as incógnitas.

Aspecto	Ajuste de Feixe	Otimização do Grafo de Pose
Incógnitas	Cada pose da câmera + cada coordenada de ponto 3D	Apenas a pose de cada câmera (nó)
Resíduo	Erro de reprojeção de ponto 3D (espaço da imagem)	Diferença em relação às observações de pose relativa (espaço $SE(3)$ )
Fonte de esparsidade	Qual câmera viu qual ponto	Quais pares de nós estão ligados por uma restrição
Uso principal	Polimento final do SfM, refinando mapas locais/globais	Correção de deriva global em SLAM (após o fechamento do loop)

Em sistemas SLAM visual reais, é comum observar uma divisão de trabalho: o ajuste de feixe local (BA local), incluindo pontos 3D, refina a área ao redor dos quadros-chave quadro a quadro, enquanto a otimização leve do Grafo de Pose, sem pontos 3D explícitos, corrige rapidamente a trajetória global sempre que um fechamento de loop é detectado. O ajuste de feixe completo, incluindo pontos 3D (BA global), é mais preciso, mas computacionalmente custoso, portanto, não pode ser executado com frequência em situações que exigem desempenho em tempo real.

9. Implementações Representativas

Ceres Solver: uma biblioteca de mínimos quadrados não lineares de propósito geral, desenvolvida pelo Google e em uso em produção desde 2010. Possui solvers baseados em Schur integrados e é usada como backend de ajuste de feixes para muitas implementações de SfM/SLAM, incluindo o COLMAP.
g2o: uma estrutura de otimização de grafos publicada por Kümmerle et al. na ICRA 2011, capaz de lidar tanto com a otimização do Grafo de Pose do SLAM quanto com o ajuste de feixes dentro da mesma estrutura. Tem sido amplamente utilizada como backend da família ORB-SLAM.
SBA (Sparse Bundle Adjustment): uma implementação inicial disponível publicamente, especializada em ajuste de feixes esparsos, publicada por Lourakis e Argyros na ACM Transactions on Mathematical Software em 2009. É frequentemente referenciada como um exemplo representativo que implementa explicitamente o truque do complemento de Schur.
Ajuste de feixe integrado do COLMAP: utiliza internamente o solucionador Ceres, alternando automaticamente entre o ajuste de feixe local e global a cada etapa do SfM incremental.

10. Condições Difíceis e Casos Comuns de Falha

Valores iniciais inadequados: O ajuste de feixe é uma otimização local — se o valor inicial estiver muito distante da solução verdadeira, ele pode convergir para uma solução local incorreta ou não convergir. A qualidade do valor inicial obtido por triangulação ou PnP determina a precisão final.
Pontos com poucas observações ou paralaxe pequena: um ponto observado a partir de um número muito pequeno de imagens, ou com pouca paralaxe, tende a ter um Jacobiano mal condicionado e pode deixar um grande erro residual concentrado puramente na direção da profundidade.
Contaminação excessiva por outliers: com muitos pontos discrepantes misturados, mesmo uma perda robusta não consegue absorvê-los completamente, e pontos vizinhos corretos podem acabar sendo arrastados e distorcidos também.
Problemas de escala extremamente grande: para reconstruções em escala urbana com contagens de observações na casa dos milhões, mesmo com o complemento de Schur, os custos de computação e memória tornam-se consideráveis, exigindo que o problema seja dividido e paralelizado, ou combinado com técnicas aproximadas (como o refinamento da região de confiança do modelo de linguagem).
Liberdade de calibre não tratada: como mencionado acima, esquecer de corrigir o calibre causa instabilidade numérica, levando à falha de convergência ou à busca por uma solução não física.

11. Escolhas Práticas

Se você precisa de alta precisão como estágio final do SfM, executar um ajuste de feixe completo no final — independentemente de ter usado a estratégia Incremental ou Global — é a regra padrão. Seguir as configurações padrão de uma implementação existente como o COLMAP provavelmente não o levará a resultados muito ruins.
Para SLAM em tempo real, o ajuste de feixe completo em cada quadro é computacionalmente muito caro. Um projeto prático combina o ajuste de feixe local apenas no conjunto mais recente de quadros-chave, com a otimização do Grafo de Pose que só é acionada no fechamento do loop. - Se você estiver construindo seu próprio pipeline do zero, é razoável construí-lo sobre uma biblioteca como Ceres Solver ou g2o. Escrever uma implementação de complemento de Schur do zero traz pouco benefício de aprendizado em relação ao custo de verificar sua correção.
Para reconstrução em larga escala, em escala urbana, em vez de depender de um único ajuste de feixe, considere métodos que dividem o problema por região e integram hierarquicamente (isso também é comumente feito como um estágio preliminar que alimenta o Estereoscopia Multivisual, discutido abaixo).

12. Resumo

O Ajuste de Feixe é um problema de mínimos quadrados não lineares que minimiza simultaneamente o erro de reprojeção em todas as câmeras e em todos os pontos 3D, resolvido iterativamente pelo método de Levenberg-Marquardt. O truque do complemento de Schur, que explora a esparsidade da relação de observação entre câmera e ponto, é o que torna essa otimização solucionável em tempo realista, mesmo na escala de dezenas de milhares de pontos. Embora compartilhe uma estrutura matemática com a otimização do Pose Graph, a escolha entre os dois se resume a se os pontos 3D são explicitamente mantidos, e é uma tecnologia fundamental compartilhada que, em última análise, sustenta a precisão tanto do SfM quanto do SLAM.

Verifique seu entendimento

Um baixo erro de reprojeção estabelece a escala métrica?

A reprojeção monocular sozinha não pode determinar a escala global. Diferencie a fixação de um medidor da adição de uma medida de tamanho físico.

Referências

What to read next

Review the backgroundIntrodução à Estrutura a partir do Movimento — Recuperando as posições 3D e da câmera simultaneamente a partir de um conjunto desordenado de fotos.Continue the seriesIntrodução à Estereoscopia Multivisual — Preenchendo uma Nuvem de Pontos Esparsa em uma Forma 3D Densa Explore another aspect of this fieldLab de brilho e luminância — exposição, gama e recorte

#Bundle Adjustment #Nonlinear Least Squares #Levenberg-Marquardt #Schur Complement #Structure from Motion