Symbols
α-β range move, 52
α-β swap, 49
α-expansion, 49
A
adjacency matrix, 444
weighted, 444
adjunction, 147
affinities, 9
alpha matte, 237
alpha value, 237
anisotropic diffusion, 169, 188
applications of GED, 407
attraction, 133
attributed graph, 425
augmenting path algorithm, 99
autarky property, 41
automatic edit cost learning, 399
B
basic energy model, 115
Bayesian, 367
belief Propagation, 490
boundaries, 3
C
catchment basin, 157
Cauchy function, 124
CCA, see component, 357, 359, 371, 374
centered, 355
centering
centroid, 367
children, 307
clique, 4
closing, 149
spectral clustering, 353
clustering, 431
CMMDS, see multidimensional scaling, 356–361, 363, 365, 370, 371, 373
co-ranking matrix, 369
color line model, 243
colorization, 191
combinatorial maps, 330
combinatorial pyramid, 337
base level combinatorial map, 341
implicit encoding, 341
level, 339
state, 339
commute-time distance, 455
commute-time embedding, 456, 458
compact partitioning, 431
component tree, 152
composed of, 325
compositing Equation, 238
concentration, 374
conductance, 363
connecting paths, 333
containment, 133
contains, 325
context, 267
contraction, 326
contraction kernel, 334
convex function, 45
coordinate, 355, 356, 361, 366–368
centered, 355
nonlinearly transformed, 363
coordinates, 365
cost, 36
cost function, 356, 357, 362, 364, 368, 369, 374
edge-based, 269
region-based, 270
covariance, 355
curse of dimensionality, 431
minimum-cut, 99
cycle, 8
D
D3P, see Data-Driven Decimation Process
data
high-dimensional, 352
set, 370
visualization, 353, 366, 367, 373
data term, 33
data-driven decimation process, 316
deblurring, 106
decoding, 354
decorrelation, 355
degree, 3
inner, 3
outer, 3
denoising, 104
derivative
diffusion, 363
dilation, 147
dimensionality
curse of, 352
intrinsic, 371
reduction, 352–354, 365, 369, 373, 374
linear, 353
nonlinear, 353
directed, 2
directed neighborhood, 321
direction, 125
discrete calculus, 6
discrete topology, 430
discretization, 427
distance, 124, 352, 353, 357, 358, 366, 368, 369, 374
commute-time, 363
concentration, 374
diffusion, 363
geodesic, 352, 359, 360, 363, 372
matrix
dense, 363
preservation, 356, 358–360, 369, 374
weighted, 360
sorted, 369
distances, 9
distortion, 366
support, 367
doubly stochastic matrices, 470
DR, see dimensionality, 353, 360, 361, 367
linear, 353
dual, 114
dual graph, 328
dual graph pyramid, 336
duality, 147
dynamic, 425
E
edge, 143
incident, 3
edge graph, 318
edges, 2
edit costs, 396
edit operations, 395
edit path, 395
eigenproblem, 355
eigenspectrum, 360
eigenvalue, 355, 359, 361, 373
problem, 362
leading, 355
electric lines of force, 287
EM algorithm, 462
embedding, 352, 353, 359, 361, 364, 367
spiky, 373
empty self-loop, 329
encoding, 354
endpoint, 3
equivalence class, 425
erosion, 147
error-tolerant graph matching, 393
exact graph matching, 387
exclusion, 133
expectation, 368
expectation-maximization, 367
exploratory
analysis, 373
data analysis, 367
extension, 155
extinction, 164
F
Fiedler value, 453
Fiedler vector, 453
filter, 149
flooding, 153
flow, 12
force, 358
forest
minimum spanning, 157
form, 426
function
source, 3
target, 3
fusion move, 51
G
Gaussian mixture model, 463
geodesic, 425
curve, 359
distance, see distance
geometric constraints, 133
Gibbs distribution, 476
global attributes, 426
gradient, 368
descent, 356
stochastic, 357, 368, 373, 374
Gram matrix, 353, 355, 359, 360, 363, 365, 454
graph, 2, 20, 143, 353, 357, 361, 373, 386
complete bipartite, 4
directed, 2
fully connected, 4
higher-order, 4
hypergraph, 4
partial graph, 4
adjacency, 6
bipartite, 4
complement, 3
complete, 4
connected, 8
digraph, 2
distance, 358
drawing, 367
edge, 363
induced, 155
isomorphism, 4
placement, 358
regular, 3
subgraph, 4
unweighted, 2
vertex, 367
weighted, 2
graph edit distance, 395
graph edit distance computation, 401
graph embedding, 409
combinatorial, 445
normalized, 445
random-walk, 445
unnormalized, 445
graph search, 266
graphical model
factor graph, 481
factorization, 479
Potts model, 485
graphical models, 476
grid, 366
elasticity, 367
H
Hausdorff metric, 427
hierarchical index, 430
hierarchy, 153
MSF, 162
hierarchy of parts, 426
higher-order energies, 43
histogram
joint, 369
Hoffman–Wielandt theorem, 447
honeycomb, 366
I
image denoising, 208
image segmentation, 266
independent set, 312
maximal, 312
maximum, 313
surviving elements, 312
indexing, 430
infimum, 143
information
context, 267
inpainting, 191
inside, 325
instabilities, 427
interpolation, 189
Isotop, 358, 367, 368, 371, 374
isotropic diffusion, 186
K
kernel, 363
L
labeling, 27
labelings, 26
Lagrange, 354
multiplier, 354
landmark, 372
Laplacian
eigenmaps, 358, 362, 363, 365, 371, 374
complete, 143
learning
manifold, 353
rate, 367
likelihood, 367
local attributes, 426
locally linear, 363
cost function, 290
electric lines of force, 287
multiobject interaction, 288
graph construction, 286
interaction
multiobject, 287
presegmentation, 286
M
majorization, 357
manifold, 352, 353, 357, 358, 360, 366, 367
disconnected, 360
learning, 353
nonconvex, 360
submanifold, 352
underlying, 371
map
self-organizing, 352, 358, 366, 367
mapping
Sammon’s nonlinear mapping, 353
topographic, 367
topographic mapping, 352
Markov random field, 32
matching, 318
matrix
p-Laplacian, 182
constitutive, 6
incidence, 6
Laplacian, 7
matting, 237
matting Laplacian, 244
maximal matching, 318
maximal independent directed edge set, 321
maximal independent edge set, 318
maximal independent set, see independent set
maximal independent vertex set, 313
candidate, 314
maximal matching, 318
maximum common subgraph, 390
maximum flow, 36
maximum-flow, 99
breakpoint, 103
parametric, 101
MDS, 353, see multidimensional scaling, 360, 370
medial axis, 426
median graph, 412
median graph via embedding, 412
meet relationship, 324
meets_each, 325
meets_exists, 325
Mercer kernel, 363
mesh, 158
metric, 424
metric-based indexing, 431
MIDES, see Maximal Independent Directed Edge Set
MIES, see Maximal Independent Edge Set
min-cut, 363
minimum common supergraph, 390
minimum spanning tree, 157
MIVS, see Maximal Independent Vertex Set
MNIST, 370
Moore-Penrose, 365
move-making, 49
MSF, see forest, minimum spanning
multidimensional scaling, 353, 369
metric
multiple kernel learning, 520
MVU, see variance, 361, 362, 371
N
K-ary, 352, 357, 359, 360, 364, 369, 372
network
electrical, 363
NLDR, 353, see dimensionality, 357, 364, 371
NLM, see Sammon, 357, 359, 371
nodes, 2
adjacent, 3
isolated, 3
nonlocal, 185
nonlocal image graph, 185, 208
nonoverlapping holed pyramid, 307
nonoverlapping pyramid without hole, 308
O
octree, 19
opening, 149
operator, 177
directional derivative, 178
weighted p-Laplace anisotropic operator, 181
weighted p-Laplace isotropic operator, 180
weighted gradient, 179
difference, 178
divergence, 179
opposing metrics method, 128
optimal GED algorithms, 401
constrained, 361
convex, 363
nonspectral, 374
pseudo-Newton, 374
spectral, 374
oriented, 2
origin, 3
orthogonal matrices, 460
overlapping pyramid, 308
P
P-brush, 116
parameter, 372
partial difference equations (PdE), 177
augmenting, 14
PCA, 353, see component, 355, 356, 366, 373
kernel, 363
permutation
matrix, 369
pivot-based, 431
pixel, 370
placement
force-directed, 358
graph, 358
point, 143
point cloud, 510
preselected edges, 321
primal, 114
principal component analysis, see component
prior term, 34
probabilistic graphical model, 512
proximal
point, 94
pseudo-Boolean functions, 43
pseudo-inverse, 365
pyramid
base, 307
level, 307
top, 307
Q
quality, 369
quantitative, 424
quantum, 424
R
RAG, 326
random walker, 166
ex aequo, 369
nonreflexive, 369
quality criteria, 352
coefficient, 364
geodesic, 154
reduction factor, see Decimation ratio
reduction function, 307
reduction window, 307, 311, 315
redundant double edge, 329
region adjacency graph, 19, 326, 333, 506
region quadtree, 17
regular pyramid, 307
p-Laplacian, 185
removal, 326
removal kernel, 336
representation
two-dimensional, 371
residual capacity, 99
residual graph, 99
resistance, 363
S
saliency map, 163
Sammon, see mapping, 357, 359, 369, 371, 374
scales, 426
scatterplot, 369
scribbles, 114
seeds, 114
segmentation
cost function
edge-based, 269
region-based, 270
graph-based
3-D, 266
multiobject, 266
multisurface, 266
n-D, 266
optimal, 266
separation constraint, 269
smoothness constraint, 269
image, 266
optimal multiple surface, 275
optimal single surface, 270
semi-supervised image clustering, 190
semi-supervised learning, 522
semidefinite programming, 361, 373
separation constraint, 269
shape, 426
shape cell, 427
shape fitting, 168
shape interior, 426
spectral, 458
Shepard
diagram, 369
shock-graph, 426
silhouette, 426
similarity, 352, 353, 358, 361, 362, 373, 374
matrix, 373
preservation, 374
similarity space, 424
simple graph, 326
simple graph pyramids, 332
singular value, 355
sink, 12
smoothing term, 34
smoothness constraint, 269
space
feature, 363
high-dimensional, 352, 358, 359, 365, 367–370
low-dimensional, 352
visualization, 370
sparsity, 358
spectral graph isomorphism, 447
spectral graph matching, 442, 451
spectral graph wavelet transform, 208
SSTRESS, 357
static, 425
step
function, 367
size, 368
stereopsis, 483
squared, 357
structural, 424
structural change, 427
subgraph, 387
subgraph isomorphism, 388
sublinear search, 430
submodularity, 40
suboptimal GED algorithms, 403
subpath, 8
superpixel, 19
supremum, 143
surviving
directed edge, 321
element, 312
undirected edge, 318
survivor, see surviving
Swiss roll, 357, 358, 370, 372
T
target, 3
target specification, 112, 134
targeted segmentation, 112
topology, 353
total variation, 94
co-area formula, 96
submodularity, 96
trail, 8
transitions, 427
tree, 10
minimal spanning, 11
component, 152
spanning, 11
U
unfolding
manifold, 358
maximum variance, 358
uprooting, 163
V
variance, 373
maximum variance unfolding, 358, 360, 363
vertex, 143
vertices, 2
vicinity, 358
visualization, 353, 366, 370, 372, 373
space, 366
W
closed, 8
open, 8
watershed
cut, 155
power, 166
ultrametric, 163
weight, 356, 360, 362, 363, 366
weighted graph matching, 450
weighted mean of a pair of graphs, 407
Welsch function, 124
X