zoomout: ZoomOut: Spectral Upsampling for Efficient Correspondence...

In bbuchsbaum/graphweights: Constructing Adjacency Matrices Based on Spatial and Feature Similarity

ZoomOut: Spectral Upsampling for Efficient Correspondence Refinement

Description

Implements the ZoomOut algorithm described in:

**ZoomOut: Spectral Upsampling for Efficient Shape Correspondence** Simone Melzi*, Jing Ren*, Emanuele Rodolà, Abhishek Sharma, Peter Wonka, and Maks Ovsjanikov. ACM Transactions on Graphics (TOG), Volume 38, Number 6, Article 155, 2019.

ZoomOut refines a given initial correspondence (encoded as a functional map) between two domains (originally shapes). Here, we present a generalized version that takes two arbitrary undirected graphs with weighted adjacency matrices as input. By leveraging the Laplacian eigen-decomposition of these graphs, ZoomOut iteratively improves the input functional map, upsampling it in the spectral domain.

The key idea (see Section 4 of the paper) is to iteratively: 1. Convert the current functional map C_k into a pointwise map T (Eq. (2) in the paper), by matching each node in the source domain to its nearest neighbor in the target domain's spectral embedding. 2. Convert the obtained pointwise map T back into a larger functional map C_{k+1} (Eq. (1) in the paper).

Iterating these two steps refines and "upsamples" the functional map, often yielding a more accurate correspondence.

Usage

zoomout(
  W_M,
  W_N,
  C0,
  k_max,
  step = 1,
  normalized_laplacian = FALSE,
  ncv = 2 * k_max + 10,
  approx_nn = FALSE,
  verbose = FALSE
)

Arguments

W_M	A symmetric nM x nM adjacency matrix of the source graph (sparse Matrix recommended). It should be weighted and nonnegative. Diagonal entries should be zero.
W_N	A symmetric nN x nN adjacency matrix of the target graph (sparse Matrix recommended). Same format as W_M.
C0	A k0 x k0 initial functional map, typically with a small k0 (e.g. 4-20). This can be derived from an initial correspondence or from low-frequency descriptor alignment.
k_max	The maximum size of the functional map to upsample to. Must be >= k0.
step	Increment step for increasing the spectral dimension at each iteration. Default is 1. Larger step sizes can speed up computation but may lead to less stable convergence.
normalized_laplacian	Logical, whether to use the normalized graph Laplacian. Default FALSE.
ncv	Number of Lanczos vectors used in the eigendecomposition (passed to RSpectra::eigs_sym). Default is 2*k_max + 10. Increase if eigen-decomposition fails to converge or if you want more stable results.
approx_nn	Logical, whether to use approximate nearest neighbors (via RANN::nn2) instead of exact search. Default FALSE.
verbose	Logical, print progress messages. Default FALSE.

Details

**Key Steps:**

1. Compute the Laplacian eigen-decomposition of both graphs up to k_{max}+1 dimensions. Let \Phi_M^k and \Phi_N^k be the first k eigenvectors of each graph Laplacian.

2. Given the current functional map C_k, compute the pointwise map T as in Eq. (2) of the paper:

T(p) = \arg\min_q \| C_k (\Phi_N(q,:))^T - \Phi_M(p,:)^T \|_2.

Here \Phi_M(p,:) is the spectral coordinate of node p in the source graph, and similarly for \Phi_N(q,:).

3. Convert the pointwise map T back into a functional map of size (k+1) \times (k+1) as in Eq. (1):

C_{k+1} = (\Phi_M^{k+1})^+ \Pi \Phi_N^{k+1},

where \Pi is the permutation matrix representation of T, and (^+) denotes the Moore-Penrose pseudoinverse.

4. Iterate until k = k_{max}.

See Section 4 of the paper and especially Eqs. (1) and (2).

**Complexity & Sparse Matrices:** Using sparse matrices for W_M and W_N is recommended, especially for large graphs. The eigen-decomposition step (via RSpectra) will be efficient if W is sparse. The iterative refinement steps mainly involve nearest neighbor queries in k-dimensional space, whose complexity grows with k.

Value

A list with elements:

C_final	A k_{max} \times k_{max} refined functional map.
T_final	A vector of length nM giving the final pointwise correspondences from graph M to graph N.
Phi_M	The first k_{max} eigenvectors of the source graph Laplacian.
Phi_N	The first k_{max} eigenvectors of the target graph Laplacian.

References

Melzi, S., Ren, J., Rodolà, E., Sharma, A., Wonka, P., & Ovsjanikov, M. (2019). "ZoomOut: Spectral Upsampling for Efficient Shape Correspondence." ACM Transactions on Graphics (TOG), 38(6), 155.

Examples

## Not run: 
# Example with small random graphs
set.seed(123)
nM <- 50
nN <- 60
# Random adjacency for M
WM <- matrix(runif(nM*nM,0,1), nM, nM)
WM[WM<0.95] <- 0
WM <- (WM + t(WM))/2
diag(WM) <- 0
# Random adjacency for N
WN <- matrix(runif(nN*nN,0,1), nN, nN)
WN[WN<0.95] <- 0
WN <- (WN + t(WN))/2
diag(WN) <- 0

# Initial small functional map (say k0=5)
C0 <- diag(5)

# Run ZoomOut up to k_max=15
res <- zoomout(WM, WN, C0, k_max=15, step=2, verbose=TRUE)

## End(Not run)

bbuchsbaum/graphweights documentation built on Dec. 14, 2024, 1:13 a.m.