12 Search Results for "Veltkamp, Remco C."

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.36
Faster Fréchet Distance Under Transformations

Authors: Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves π and σ of total complexity n and a threshold δ ≥ 0, we present an 𝒪̃(n^{7 + 1/3}) time algorithm to determine whether there exists a translation t ∈ ℝ² such that the Fréchet distance between π and σ + t is at most δ. This improves on the previous best result, which is an 𝒪(n⁸) time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class T of rationally parametrized transformations with k degrees of freedom, we show that one can determine whether there is a transformation τ ∈ T such that the Fréchet distance between π and τ(σ) is at most δ in 𝒪̃(n^{3k+4/3}) time.
Cite as

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong. Faster Fréchet Distance Under Transformations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2025.36,
  author =	{Buchin, Kevin and Buchin, Maike and Huang, Zijin and Nusser, Andr\'{e} and Wong, Sampson},
  title =	{{Faster Fr\'{e}chet Distance Under Transformations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.36},
  URN =		{urn:nbn:de:0030-drops-234137},
  doi =		{10.4230/LIPIcs.ICALP.2025.36},
  annote =	{Keywords: Fr\'{e}chet distance, curve similarity, shape matching}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.31
A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

Authors: Timothy M. Chan and Isaac M. Hair

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given two convex polygons P and Q with n and m edges, the maximum overlap problem is to find a translation of P that maximizes the area of its intersection with Q. We give the first randomized algorithm for this problem with linear running time. Our result improves the previous two-and-a-half-decades-old algorithm by de Berg, Cheong, Devillers, van Kreveld, and Teillaud (1998), which ran in O((n+m)log(n+m)) time, as well as multiple recent algorithms given for special cases of the problem.
Cite as

Timothy M. Chan and Isaac M. Hair. A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2025.31,
  author =	{Chan, Timothy M. and Hair, Isaac M.},
  title =	{{A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.31},
  URN =		{urn:nbn:de:0030-drops-231832},
  doi =		{10.4230/LIPIcs.SoCG.2025.31},
  annote =	{Keywords: Convex polygons, shape matching, prune-and-search, parametric search}
}
Document
DOI: 10.4230/DagSemProc.06171.1
06171 Abstracts Collection – Content-Based Retrieval

Authors: Remco C. Veltkamp and Tim Crawford

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
From 23.04.06 to 28.04.06, the Dagstuhl Seminar 06171 `Content-Based Retrieval'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Remco C. Veltkamp and Tim Crawford. 06171 Abstracts Collection – Content-Based Retrieval. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{veltkamp_et_al:DagSemProc.06171.1,
  author =	{Veltkamp, Remco C. and Crawford, Tim},
  title =	{{06171 Abstracts Collection – Content-Based Retrieval}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.1},
  URN =		{urn:nbn:de:0030-drops-7204},
  doi =		{10.4230/DagSemProc.06171.1},
  annote =	{Keywords: Content-based retrieval, indexing, video analysis, music similarity, shape similarity}
}
Document
DOI: 10.4230/DagSemProc.06171.2
06171 Executive Summary – Content-Based Retrieval

Authors: Tim Crawford and Remco C. Veltkamp

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
The emphasis of the fourth seminar in the Dagstuhl Seminar series on "Content-Based Retrieval" lies on the PERCEPTUAL and COGNITIVE aspects of all kinds of content-based retrieval. Fundamental questions such as the role of perception and cognition in feature extraction, pattern similarity rating, indexing large collections etc. play an important role.
Cite as

Tim Crawford and Remco C. Veltkamp. 06171 Executive Summary – Content-Based Retrieval. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{crawford_et_al:DagSemProc.06171.2,
  author =	{Crawford, Tim and Veltkamp, Remco C.},
  title =	{{06171 Executive Summary – Content-Based Retrieval }},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.2},
  URN =		{urn:nbn:de:0030-drops-7577},
  doi =		{10.4230/DagSemProc.06171.2},
  annote =	{Keywords: Content-based retrieval, indexing, video analysis, music similarity, shape similarity}
}
Document
DOI: 10.4230/DagSemProc.06171.3
A User-Oriented Approach to Music Information Retrieval

Authors: Micheline Lesaffre, Marc Leman, and Jean-Pierre Martens

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
Search and retrieval of specific musical content (e.g. emotion, melody) has become an important aspect of system development but only little research is user-oriented. The success of music information retrieval technology primarily depends on both assessing and meeting the needs of its users. Potential users of music information retrieval systems, however, draw upon various ways of expressing themselves. But, who are the potential users of MIR systems and how would they describe music qualities? High-level concepts contribute to the definition of meaning in music. How can we measure meaning and emotion in music? How can we define the higher-order understanding of features of music that the average users share? Information on listener’s perception of qualities of music is needed to make automated access to music content attractive to system users. The emphasis of our investigation is on a user-oriented approach to the semantic description of music. We report the results of an experiment that explores how users perceive affects in music, and what structural descriptions of music best characterize their understanding of music expression. 79 potential users of music information retrieval systems rated different sets of adjectives, while they were listening to 160 pieces of real music. The subject group (79) was recruited amongst 774 participants in a large survey on the music background, habits and interests, preferred genres, taste and favourite titles of people who are willing to use interactive music systems. Moreover, the stimuli used reflected the musical taste of the average participant in the large survey (774). The study reveals that perceived qualities of music are affected by the profile of the user. Significant subject dependencies are found for age, music expertise, musicianship, broadness of taste and familiarity with classical music. Furthermore, interesting relationships are discovered between expressive and structural features. Analyses show that the targeted population most unanimously agrees on loudness and tempo, whilst less unanimity was found for timbre and articulation. Finally, our findings are tested and validated by means of a demo of a semantic music recommender system prototype that supports the querying of a music database by semantic descriptors for affect, structure and motion. The system, that recommends music from a relational database containing the quality ratings provided by the participants, illustrates the potential of a user-dependent and emotion-based retrieval of music.
Cite as

Micheline Lesaffre, Marc Leman, and Jean-Pierre Martens. A User-Oriented Approach to Music Information Retrieval. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{lesaffre_et_al:DagSemProc.06171.3,
  author =	{Lesaffre, Micheline and Leman, Marc and Martens, Jean-Pierre},
  title =	{{A User-Oriented Approach to Music Information Retrieval}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.3},
  URN =		{urn:nbn:de:0030-drops-6509},
  doi =		{10.4230/DagSemProc.06171.3},
  annote =	{Keywords: Semantic description, user studies, music information retrieval}
}
Document
DOI: 10.4230/DagSemProc.06171.4
After the search is over... the work begins

Authors: Tim Crawford

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
A narrative and discursive discussion of some adventures in musicology using a simple MIR system.
Cite as

Tim Crawford. After the search is over... the work begins. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{crawford:DagSemProc.06171.4,
  author =	{Crawford, Tim},
  title =	{{After the search is over... the work begins}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.4},
  URN =		{urn:nbn:de:0030-drops-7472},
  doi =		{10.4230/DagSemProc.06171.4},
  annote =	{Keywords: Music information retrieval; musicology; OMRAS; harmonic modeling}
}
Document
DOI: 10.4230/DagSemProc.06171.5
Are we Ready to Embrace the Semantic Web?

Authors: Shankar Vembu and Stephan Baumann

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
The aim of the semantic web is to describe resources available on the web using metadata elements that can be processed or interpreted by machines. MPEG-7 is the result of a standardisation effort to annotate multimedia documents, and it offers a rich suite of metadata descriptors for describing these documents at various levels of abstraction from low-level features to high-level semantics. Owing to the proliferation of multimedia content in the internet, there is now a lot of interest in the semantic web community in multimedia metadata standards in general, and MPEG-7 in particular. Despite the fact that the semantic web initiatives could benefit a lot from MPEG-7 for the annotation of multimedia documents, recent studies have underlined the limitations of MPEG-7 in describing the semantics of highly structured domains like sports or medicine. This has led to an upsurge of interest in adopting an integrated approach to the design of multimedia ontologies. In our work, we describe a systematic approach to the design of multimedia ontologies in which we use MPEG-7 to model only the structural and the low-level aspects of multimedia documents. High-level semantics are described using domain-specific vocabularies. A retrieval engine based on this framework will then be able to process high-level text-based semantic queries. Whilst a lot of research has been done in the design of multimedia ontologies, a plaguing issue is the automatic annotation of multimedia content at a semantic level. It is possible to derive low-level descriptors using state-of-the-art techniques in multimedia content analysis, but the same does not hold true when it comes to analysing multimedia content at a high level of abstraction. We discuss various approaches that have been recently proposed to accomplish this task. An interesting line of discussion is the automatic population and enrichment of multimedia ontologies that offers a lot of challenges and stresses the need for efficient approaches for the semantic analysis of multimedia documents.
Cite as

Shankar Vembu and Stephan Baumann. Are we Ready to Embrace the Semantic Web?. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{vembu_et_al:DagSemProc.06171.5,
  author =	{Vembu, Shankar and Baumann, Stephan},
  title =	{{Are we Ready to Embrace the Semantic Web?}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.5},
  URN =		{urn:nbn:de:0030-drops-6559},
  doi =		{10.4230/DagSemProc.06171.5},
  annote =	{Keywords: Semantic analysis, Multimedia ontologies, Semantic web}
}
Document
DOI: 10.4230/DagSemProc.06171.6
Efficient multi-step query processing for EMD-based similarity

Authors: Ira Assent and Thomas Seidl

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
Similarity search in large multimedia databases requires ef- ficient query processing based on suitable similarity models. Similarity models consist of a feature extraction step as well as a distance defined for these features, and they demand an efficient algorithm for retrieving similar objects under this model. In this work, we focus on the Earth Movers Distance (EMD), a recently introduced similarity model which has been successfully employed in numerous applications and has been reported as well reflecting human perceptual similarity. As its computation is complex, the direct application of the EMD to large, high-dimensional databases is not feasible. To remedy this and allow users to benefit from the high quality of the model even in larger settings, we developed various lower bounds for the EMD to be used in index-supported multistep query processing algorithms. We prove that our algorithms are complete, thus producing no false drops. We also show that it is highly efficient as experiments on large image databases with high-dimensional features demonstrate.
Cite as

Ira Assent and Thomas Seidl. Efficient multi-step query processing for EMD-based similarity. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{assent_et_al:DagSemProc.06171.6,
  author =	{Assent, Ira and Seidl, Thomas},
  title =	{{Efficient multi-step query processing for EMD-based similarity}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.6},
  URN =		{urn:nbn:de:0030-drops-6490},
  doi =		{10.4230/DagSemProc.06171.6},
  annote =	{Keywords: Content-based retrieval, indexing, multimedia databases, efficiency, similarity}
}
Document
DOI: 10.4230/DagSemProc.06171.7
Partial Matching by Structural Descriptors

Authors: Simone Marini, Biasotti Silvia, and Falcidieno Bianca

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
The extended abstract describes a method for recognizing similar sub-parts of objects described by 3D polygonal meshes. The innovation of this method is the coupling of structure and geometry in the matching process. First of all, the structure of the shape is coded in a graph where each node is associated to a sub-part of the shape. Then, the matching between two shapes is approached using a graph-matching technique relying upon a geometric description of each sub-part.
Cite as

Simone Marini, Biasotti Silvia, and Falcidieno Bianca. Partial Matching by Structural Descriptors. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{marini_et_al:DagSemProc.06171.7,
  author =	{Marini, Simone and Silvia, Biasotti and Bianca, Falcidieno},
  title =	{{Partial Matching by Structural Descriptors}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.7},
  URN =		{urn:nbn:de:0030-drops-6511},
  doi =		{10.4230/DagSemProc.06171.7},
  annote =	{Keywords: Partial Matching, 3D Structural Shape Descriptor, Graph Matching}
}
Document
DOI: 10.4230/DagSemProc.06171.8
Point-set algorithms for pattern discovery and pattern matching in music

Authors: David Meredith

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
An algorithm that discovers the themes, motives and other perceptually significant repeated patterns in a musical work can be used, for example, in a music information retrieval system for indexing a collection of music documents so that it can be searched more rapidly. It can also be used in software tools for music analysis and composition and in a music transcription system or model of music cognition for discovering grouping structure, metrical structure and voice-leading structure. In most approaches to pattern discovery in music, the data is assumed to be in the form of strings. However, string-based methods become inefficient when one is interested in finding highly embellished occurrences of a query pattern or searching for polyphonic patterns in polyphonic music. These limitations can be avoided by representing the music as a set of points in a multidimensional Euclidean space. This point-set pattern matching approach allows the maximal repeated patterns in a passage of polyphonic music to be discovered in quadratic time and all occurrences of these patterns to be found in cubic time. More recently, Clifford et al. (2006) have shown that the best match for a query point set within a text point set of size n can be found in O(n log n) time by incorporating randomised projection, uniform hashing and FFT into the point-set pattern matching approach. Also, by using appropriate heuristics for selecting compact maximal repeated patterns with many non-overlapping occurrences, the point-set pattern discovery algorithms described here can be adapted for data compression. Moreover, the efficient encodings generated when this compression algorithm is run on music data seem to resemble the motivic-thematic analyses produced by human experts.
Cite as

David Meredith. Point-set algorithms for pattern discovery and pattern matching in music. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{meredith:DagSemProc.06171.8,
  author =	{Meredith, David},
  title =	{{Point-set algorithms for pattern discovery and pattern matching in music}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.8},
  URN =		{urn:nbn:de:0030-drops-6525},
  doi =		{10.4230/DagSemProc.06171.8},
  annote =	{Keywords: Content-based music retrieval, point-set pattern matching}
}
Document
DOI: 10.4230/DagSemProc.06171.9
Properties and Performances of Shape Similarity Measures

Authors: Remco C. Veltkamp and Longin Jan Latecki

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
This paper gives an overview of shape dissimilarity measure properties, such as metric and robustness properties, and of retrieval performance measures. Fifteen shape similarity measures are shortly described and compared. Since an objective comparison of their qualities seems to be impossible, experimental comparison is needed. The Motion Picture Expert Group (MPEG), a working group of ISO/IEC has defined the MPGE-7 standard for description and search of audio and visual content. A region based and a contour based shape similarity method are part of the standard. The data set created by the MPEG-7 committee for evaluation of shape similarity measures offers an excellent possibility for objective experimental comparison of the existing approaches evaluated based on the retrieval rate. Their retrieval results on the MPEG-7 Core Experiment Core Experiment Shape-1 test set as reported in the literature and obtained by a reimplementation are compared and discussed. To compare the performance of similarity measures, we built the framework SIDESTEP – Shape-based Image Delivery Statistics Evaluation Project, http://give-lab.cs.uu.nl/sidestep/.
Cite as

Remco C. Veltkamp and Longin Jan Latecki. Properties and Performances of Shape Similarity Measures. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{veltkamp_et_al:DagSemProc.06171.9,
  author =	{Veltkamp, Remco C. and Latecki, Longin Jan},
  title =	{{Properties and Performances of Shape Similarity Measures}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.9},
  URN =		{urn:nbn:de:0030-drops-6546},
  doi =		{10.4230/DagSemProc.06171.9},
  annote =	{Keywords: Shape similarity, Evaluation}
}
Document
DOI: 10.4230/DagSemProc.06171.10
Structural Descriptors for 3D Shapes

Authors: Michela Spagnuolo, Silvia Biasotti, Bianca Falcidieno, and Simone Marini

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
Assessing the similarity among 3D shapes is a very complex and challenging research topic. While human perception have been widely studied and produced theories that received a large consensus, the computational aspects of 3D shape retrieval and matching have been only recently addressed. The majority of the methods proposed in the literature mainly focus on the geometry of shapes, in the sense of considering its spatial distribution or extent in the 3D space. From a practical point of view, the main advantage of these methods is that they do not make specific assumption on the topology of the digital models, usually triangle meshes or even triangle soups. Moreover, these methods are also computationally efficient. There is a growing consensus, however, that shapes are recognized and coded mentally in terms of relevant parts and their spatial configuration, or structure. Methods approaching the problem from a geometric point of view do not take into account the structure of the shape and generally the similarity distance between two objects depends on their spatial embedding. The presentation will discuss the definition and use of structural descriptions for assessing shape similarity. The idea is to define a shape description framework based on results of differential topology which deal with the description of shapes by means of the properties of one, or more, real-valued functions defined over the shape. Studying these properties, several topological descriptions of the shape can be defined, which may also encode different geometric and morphological attributes that globally and locally describe the shape. Examples and results will be discussed and ongoing work outlined. This work is partially supported by the EU Newtwork of Excellence AIM{@}SHAPE.
Cite as

Michela Spagnuolo, Silvia Biasotti, Bianca Falcidieno, and Simone Marini. Structural Descriptors for 3D Shapes. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{spagnuolo_et_al:DagSemProc.06171.10,
  author =	{Spagnuolo, Michela and Biasotti, Silvia and Falcidieno, Bianca and Marini, Simone},
  title =	{{Structural Descriptors for 3D Shapes}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.10},
  URN =		{urn:nbn:de:0030-drops-6532},
  doi =		{10.4230/DagSemProc.06171.10},
  annote =	{Keywords: 3D shape descriptors, computational topology}
}
  • Refine by Type
  • 12 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 10 2006

  • Refine by Author
  • 3 Crawford, Tim
  • 3 Veltkamp, Remco C.
  • 2 Marini, Simone
  • 1 Assent, Ira
  • 1 Baumann, Stephan
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 10 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Computational geometry

  • Refine by Keyword
  • 3 Content-based retrieval
  • 3 indexing
  • 2 music similarity
  • 2 shape matching
  • 2 shape similarity
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact