Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:( Cut similarity)`

.
Showing records 1 – 2 of
2 total matches.

▼ Search Limiters

1.
Curado, Manuel.
Structural *Similarity*: Applications to Object Recognition and Clustering
.

Degree: 2018, University of Alicante

URL: http://hdl.handle.net/10045/98110

In this thesis, we propose many developments in the context of Structural Similarity. We address both node (local) similarity and graph (global) similarity. Concerning node similarity, we focus on improving the diffusive process leading to compute this similarity (e.g. Commute Times) by means of modifying or rewiring the structure of the graph (Graph Densification), although some advances in Laplacian-based ranking are also included in this document. Graph Densification is a particular case of what we call graph rewiring, i.e. a novel field (similar to image processing) where input graphs are rewired to be better conditioned for the subsequent pattern recognition tasks (e.g. clustering). In the thesis, we contribute with an scalable an effective method driven by Dirichlet processes. We propose both a completely unsupervised and a semi-supervised approach for Dirichlet densification. We also contribute with new random walkers (Return Random Walks) that are useful structural filters as well as asymmetry detectors in directed brain networks used to make early predictions of Alzheimer's disease (AD). Graph similarity is addressed by means of designing structural information channels as a means of measuring the Mutual Information between graphs. To this end, we first embed the graphs by means of Commute Times. Commute times embeddings have good properties for Delaunay triangulations (the typical representation for Graph Matching in computer vision). This means that these embeddings can act as encoders in the channel as well as decoders (since they are invertible). Consequently, structural noise can be modelled by the deformation introduced in one of the manifolds to fit the other one. This methodology leads to a very high discriminative similarity measure, since the Mutual Information is measured on the manifolds (vectorial domain) through copulas and bypass entropy estimators. This is consistent with the methodology of decoupling the measurement of graph similarity in two steps: a) linearizing the Quadratic Assignment Problem (QAP) by means of the embedding trick, and b) measuring similarity in vector spaces. The QAP problem is also investigated in this thesis. More precisely, we analyze the behaviour of m-best Graph Matching methods. These methods usually start by a couple of best solutions and then expand locally the search space by excluding previous clamped variables. The next variable to clamp is usually selected randomly, but we show that this reduces the performance when structural noise arises (outliers). Alternatively, we propose several heuristics for spanning the search space and evaluate all of them, showing that they are usually better than random selection. These heuristics are particularly interesting because they exploit the structure of the affinity matrix. Efficiency is improved as well. Concerning the application domains explored in this thesis we focus on object recognition (graph similarity), clustering (rewiring), compression/decompression of graphs (links with Extremal Graph Theory), 3D shape…
*Advisors/Committee Members: Escolano, Francisco (advisor), Sáez Martínez, Juan Manuel (advisor).*

Subjects/Keywords: Graph densification; Cut similarity; Spectral clustering; Dirichlet problems; Random walkers; Commute Times; Graph algorithms; Regular Partition; Szemeredi; Alzheimer's disease; Graphs; Return Random Walk; Net4lap; Directed graphs; Spectral graph theory; Graph entropy; Mutual information; Manifold alignment; m-Best Graph Matching; Binary-Tree Partitions; QAP; Graph sparsification; Shape simplification; Alpha shapes

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Curado, M. (2018). Structural Similarity: Applications to Object Recognition and Clustering . (Thesis). University of Alicante. Retrieved from http://hdl.handle.net/10045/98110

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Curado, Manuel. “Structural Similarity: Applications to Object Recognition and Clustering .” 2018. Thesis, University of Alicante. Accessed August 08, 2020. http://hdl.handle.net/10045/98110.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Curado, Manuel. “Structural Similarity: Applications to Object Recognition and Clustering .” 2018. Web. 08 Aug 2020.

Vancouver:

Curado M. Structural Similarity: Applications to Object Recognition and Clustering . [Internet] [Thesis]. University of Alicante; 2018. [cited 2020 Aug 08]. Available from: http://hdl.handle.net/10045/98110.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Curado M. Structural Similarity: Applications to Object Recognition and Clustering . [Thesis]. University of Alicante; 2018. Available from: http://hdl.handle.net/10045/98110

Not specified: Masters Thesis or Doctoral Dissertation

2. Nayyeri, Amir. Combinatorial optimization on embedded curves.

Degree: PhD, 0112, 2013, University of Illinois – Urbana-Champaign

URL: http://hdl.handle.net/2142/42333

We describe several algorithms for classifying, comparing and optimizing curves
on surfaces. We give algorithms to compute the minimum member of a given
homology class, particularly computing the maximum flow and minimum cuts,
in surface embedded graphs. We describe approximation algorithms to compute
certain similarity measures for embedded curves on a surface. Finally, we present
algorithms to solve computational problems for compactly presented curves.
We describe the first algorithms to compute the shortest representative of a
Z2-homology class. Given a directed graph embedded on a surface of genus g
with b boundary cycles, we can compute the shortest single cycle Z2-homologous
to a given even subgraph in 2^{O(g+b)}nlog n time. As a consequence we obtain an
algorithm to compute the shortest directed non-separating cycle in 2^{O(g)}n log n time,
which improves the previous best algorithm by a factor of O(√{n}) if the genus is
a constant. Further, we can compute the shortest even subgraph in a given Z2-homology
class if the input graph is undirected in the same asymptotic running
time. As a consequence, we obtain the first near linear time algorithm to compute
minimum (s, t)-cuts in surface embedded graphs of constant genus. We also prove
that computing the shortest even subgraph in a Z2-homology class is in general
NP-hard, which explains the exponential dependence on g.
We also consider the corresponding optimization problem under Z-homology.
Given an integer circulation Φ in a directed graph embedded on a surface of genus
g, we describe algorithms to compute the minimum cost circulation that is Z-homologous
to Φ in O(g^{8n} log^{2} n log^{2} C) time if the capacities are integers whose
sum is C or in g^{O(g)}n^{3/2} time for arbitrary capacities. In particular, our algorithm
improves the best known algorithm for computing the maximum (s, t)-flow on
surface embedded graph after 20 years. The previous best algorithm, except for
planar graphs, follow from general maximum flow algorithms for sparse graphs.
Next, we consider two closely related similarity measures of curves on piecewise
linear surfaces embedded in R^{3}, called homotopy height and homotopic Frechét distance.
These similarity measures capture the longest curve that appears and the
longest length that any point travels in the best morph between two given curves, respectively.
We describe the first polynomial-time O(log n)-approximation algorithms
for both problems. Prior to our work no algorithms were known for the homotopy
height problem. For the homotopic Frechét distance, algorithms were known only
for curves on Euclidean plane with polygonal obstacles. Surprisingly, it is not even
known if deciding if either the homotopy height or the homotopic Frechét distance
is smaller that a given value is in NP.
Finally, we consider normal curves on abstract triangulated surfaces. A curve
is normal if it intersects any triangle in a finite set of arcs, each crossing between
two different edges of the triangle.…
*Advisors/Committee Members: Erickson, Jeff G. (advisor), Erickson, Jeff G. (Committee Chair), Har-Peled, Sariel (committee member), Forsyth, David A. (committee member), Dey, Tamal (committee member).*

Subjects/Keywords: Computational topology; combinatorial optimization; curves; maximum flow; minimum cut; curve similarity; normal coordinated

…Curve *similarity* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.10.1… …Generalizations of planar cuts . . . . . . . . . . . . . . . . . . . .
3.2 Undirected minimum *cut* and… …equivalence relation as a crude *similarity* measure, in which
two curves are at distance 0 if they… …are equivalent and distance ∞ if they are not.
More refined *similarity* measures can be… …defined by considering the geometry of
the underlying space. Measures of *similarity* like…

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Nayyeri, A. (2013). Combinatorial optimization on embedded curves. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/42333

Chicago Manual of Style (16^{th} Edition):

Nayyeri, Amir. “Combinatorial optimization on embedded curves.” 2013. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed August 08, 2020. http://hdl.handle.net/2142/42333.

MLA Handbook (7^{th} Edition):

Nayyeri, Amir. “Combinatorial optimization on embedded curves.” 2013. Web. 08 Aug 2020.

Vancouver:

Nayyeri A. Combinatorial optimization on embedded curves. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2013. [cited 2020 Aug 08]. Available from: http://hdl.handle.net/2142/42333.

Council of Science Editors:

Nayyeri A. Combinatorial optimization on embedded curves. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2013. Available from: http://hdl.handle.net/2142/42333