NDLI: New insights into Laplacian similarity search

Content Provider	IEEE Xplore Digital Library
Author	Xiao-Ming Wu Zhenguo Li Shih-Fu Chang
Copyright Year	2015
Description	Author affiliation: Dept. of Electr. Eng., Columbia Univ., New York, NY, USA (Xiao-Ming Wu; Shih-Fu Chang) \|\| Huawei Noah's Ark Lab., Hong Kong, China (Zhenguo Li)
Abstract	Graph-based computer vision applications rely critically on similarity metrics which compute the pairwise similarity between any pair of vertices on graphs. This paper investigates the fundamental design of commonly used similarity metrics, and provides new insights to guide their use in practice. In particular, we introduce a family of similarity metrics in the form of (L + $αΛ)^{-1},$ where L is the graph Laplacian, Λ is a positive diagonal matrix acting as a regularizer, and α is a positive balancing factor. Such metrics respect graph topology when a is small, and reproduce well-known metrics such as hitting times and the pseudo-inverse of graph Laplacian with different regularizer Λ. This paper is the first to analyze the important impact of selecting Λ in retrieving the local cluster from a seed. We find that different Λ can lead to surprisingly complementary behaviors: Λ = D (degree matrix) can reliably extract the cluster of a query if it is sparser than surrounding clusters, while Λ = I (identity matrix) is preferred if it is denser than surrounding clusters. Since in practice there is no reliable way to determine the local density in order to select the right model, we propose a new design of Λ that automatically adapts to the local density. Experiments on image retrieval verify our theoretical arguments and confirm the benefit of the proposed metric. We expect the insights of our theory to provide guidelines for more applications in computer vision and other domains.
Starting Page	1949
Ending Page	1957
File Size	673545
Page Count	9
File Format	PDF
ISSN	10636919
e-ISBN	9781467369640
DOI	10.1109/CVPR.2015.7298805
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-06-07
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Measurement Laplace equations Robustness Image retrieval Symmetric matrices Topology Harmonic analysis
Content Type	Text
Resource Type	Article
Subject	Computer Vision and Pattern Recognition Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Manifold learning using robust Graph Laplacian for interactive image search

Coherent Laplacian 3-D protrusion segmentation

Graph-Laplacian PCA: Closed-Form Solution and Robustness

Fast matting using large kernel matting Laplacian matrices

Harmonic maps and their applications in surface matching

View invariant object recognition

Graph Laplacian Kernels for Object Classification from a Single Example

Graph Matching using Commute Time Spanning Tr

Graph Matching using Commute Time Spanning Trees

New insights into Laplacian similarity search

Similar Documents

Manifold learning using robust Graph Laplacian for interactive image search

Coherent Laplacian 3-D protrusion segmentation

Graph-Laplacian PCA: Closed-Form Solution and Robustness

Fast matting using large kernel matting Laplacian matrices

Harmonic maps and their applications in surface matching

View invariant object recognition

Graph Laplacian Kernels for Object Classification from a Single Example

Graph Matching using Commute Time Spanning Tr

Graph Matching using Commute Time Spanning Trees

New insights into Laplacian similarity search