DROPS

Found 2 Possible Name Variants:

Cai, Chen
Cai, Cheng

Cai, Chen

Document

DOI: 10.4230/LIPIcs.SoCG.2020.26

Elder-Rule-Staircodes for Augmented Metric Spaces

Authors: Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

An augmented metric space (X, d_X, f_X) is a metric space (X, d_X) equipped with a function f_X: X → ℝ. It arises commonly in practice, e.g, a point cloud X in ℝ^d where each point x∈ X has a density function value f_X(x) associated to it. Such an augmented metric space naturally gives rise to a 2-parameter filtration. However, the resulting 2-parameter persistence module could still be of wild representation type, and may not have simple indecomposables. In this paper, motivated by the elder-rule for the zeroth homology of a 1-parameter filtration, we propose a barcode-like summary, called the elder-rule-staircode, as a way to encode the zeroth homology of the 2-parameter filtration induced by a finite augmented metric space. Specifically, given a finite (X, d_X, f_X), its elder-rule-staircode consists of n = |X| number of staircase-like blocks in the plane. We show that the fibered barcode, the fibered merge tree, and the graded Betti numbers associated to the zeroth homology of the 2-parameter filtration induced by (X, d_X, f_X) can all be efficiently computed once the elder-rule-staircode is given. Furthermore, for certain special cases, this staircode corresponds exactly to the set of indecomposables of the zeroth homology of the 2-parameter filtration. Finally, we develop and implement an efficient algorithm to compute the elder-rule-staircode in O(n²log n) time, which can be improved to O(n²α(n)) if X is from a fixed dimensional Euclidean space ℝ^d, where α(n) is the inverse Ackermann function.

Cite as

Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang. Elder-Rule-Staircodes for Augmented Metric Spaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.SoCG.2020.26,
  author =	{Cai, Chen and Kim, Woojin and M\'{e}moli, Facundo and Wang, Yusu},
  title =	{{Elder-Rule-Staircodes for Augmented Metric Spaces}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.26},
  URN =		{urn:nbn:de:0030-drops-121848},
  doi =		{10.4230/LIPIcs.SoCG.2020.26},
  annote =	{Keywords: Persistent homology, Multiparameter persistence, Barcodes, Elder rule, Hierarchical clustering, Graded Betti numbers}
}

Cai, Cheng

Document

DOI: 10.4230/DagSemProc.08251.3

A Robust Estimator of Image Thumbnail and Video Histogram Representation

Authors: Cheng Cai

Published in: Dagstuhl Seminar Proceedings, Volume 8251, Contextual and Social Media Understanding and Usage (2009)

Abstract

For browsing and retrieval system, images are represented by thumbnails and video shots are represented by content representations. In order to achieve better visual quality and retrieval performance, the representation estimator is expected to be accurate and robust. From the statistical perspective, representation extraction can be treated as central value estimation. In this paper, we propose an adaptive alpha-trimmed average estimator based on Gaussian distribution hypothesis test (AATA-GDHT). For a set of values, this estimator extracts the representation by trimming extreme values and then averaging the rest. The criterion to distinguish between extreme values and useful data is derived from Gaussian distribution hypothesis test on the basis of global statics. Experimental results from standard images and videos show that our proposed scheme outperforms traditional methods.For the browsing and retrieval system, images are represented by thumbnails and video shots are represented by histogram representations. In order to achieve better visual quality and retrieval performance, the representation estimator is expected to be accurate and robust. From the statistical perspective, representation extraction can be treated as central value estimation. In this paper, we propose an adaptive alpha-trimmed average estimator based on the Gaussian distribution hypothesis test. For a set of values, this estimator extracts the representation by trimming extreme values and then averaging the rest. The criterion adopted to distinguish between extreme values and useful data is derived from the Gaussian distribution hypothesis test on the basis of global statics. Experimental results from standard images and videos show that our proposed scheme outperforms traditional methods.

Cite as

Cheng Cai. A Robust Estimator of Image Thumbnail and Video Histogram Representation. In Contextual and Social Media Understanding and Usage. Dagstuhl Seminar Proceedings, Volume 8251, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{cai:DagSemProc.08251.3,
  author =	{Cai, Cheng},
  title =	{{A Robust Estimator of Image Thumbnail and Video Histogram Representation}},
  booktitle =	{Contextual and Social Media Understanding and Usage},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8251},
  editor =	{Susanne Boll and Mohan S. Kankanhalli and Gopal Pingali and Svetha Venkatesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08251.3},
  URN =		{urn:nbn:de:0030-drops-20182},
  doi =		{10.4230/DagSemProc.08251.3},
  annote =	{Keywords: Algorithms, Experimentation, Performance}
}

Search Results

Documents authored by Cai, Chen

Cai, Chen

Elder-Rule-Staircodes for Augmented Metric Spaces

Abstract

Cite as

Cai, Cheng

A Robust Estimator of Image Thumbnail and Video Histogram Representation

Abstract

Cite as

Thanks for your feedback!

Could not send message