2 Search Results for "Nivat, Maurice"

Document
DOI: 10.4230/LIPIcs.ISAAC.2019.42
The Generalized Microscopic Image Reconstruction Problem

Authors: Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
This paper presents and studies a generalization of the microscopic image reconstruction problem (MIR) introduced by Frosini and Nivat [Andrea Frosini and Maurice Nivat, 2007; Nivat, 2002]. Consider a specimen for inspection, represented as a collection of points typically organized on a grid in the plane. Assume each point x has an associated physical value l_x, which we would like to determine. However, it might be that obtaining these values precisely (by a surgical probe) is difficult, risky, or impossible. The alternative is to employ aggregate measuring techniques (such as EM, CT, US or MRI), whereby each measurement is taken over a larger window, and the exact values at each point are subsequently extracted by computational methods. In this paper we extend the MIR framework in a number of ways. First, we consider a generalized setting where the inspected object is represented by an arbitrary graph G, and the vector l in R^n assigns a value l_v to each node v. A probe centered at a vertex v will capture a window encompassing its entire neighborhood N[v], i.e., the outcome of a probe centered at v is P_v = sum_{w in N[v]} l_w. We give a criterion for the graphs for which the extended MIR problem can be solved by extracting the vector l from the collection of probes, P^- = {P_v | v in V}. We then consider cases where such reconstruction is impossible (namely, graphs G for which the probe vector P is inconclusive, in the sense that there may be more than one vector l yielding P). Let us assume that surgical probes (whose outcome at vertex v is the exact value of l_v) are technically available to us (yet are expensive or risky, and must be used sparingly). We show that in such cases, it may still be possible to achieve reconstruction based on a combination of a collection of standard probes together with a suitable set of surgical probes. We aim at identifying the minimum number of surgical probes necessary for a unique reconstruction, depending on the graph topology. This is referred to as the Minimum Surgical Probing problem (MSP). Besides providing a solution for the above problems for arbitrary graphs, we also explore the range of possible behaviors of the Minimum Surgical Probing problem by determining the number of surgical probes necessary in certain specific graph families, such as perfect k-ary trees, paths, cycles, grids, tori and tubes.
Cite as

Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz. The Generalized Microscopic Image Reconstruction Problem. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2019.42,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Lotker, Zvi and Peleg, David and Rawitz, Dror},
  title =	{{The Generalized Microscopic Image Reconstruction Problem}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.42},
  URN =		{urn:nbn:de:0030-drops-115382},
  doi =		{10.4230/LIPIcs.ISAAC.2019.42},
  annote =	{Keywords: Discrete mathematics, Combinatorics, Reconstruction algorithm, Image reconstruction, Graph spectra, Grid graphs}
}
Document
DOI: 10.4230/DagSemRep.165
Discrete Tomography: Algorithms and Complexity (Dagstuhl Seminar 97042)

Authors: Peter Grtizmann and Maurice Nivat

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Peter Grtizmann and Maurice Nivat. Discrete Tomography: Algorithms and Complexity (Dagstuhl Seminar 97042). Dagstuhl Seminar Report 165, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{grtizmann_et_al:DagSemRep.165,
  author =	{Grtizmann, Peter and Nivat, Maurice},
  title =	{{Discrete Tomography: Algorithms and Complexity (Dagstuhl Seminar 97042)}},
  pages =	{1--17},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{165},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.165},
  URN =		{urn:nbn:de:0030-drops-150521},
  doi =		{10.4230/DagSemRep.165},
}
  • Refine by Author
  • 1 Bar-Noy, Amotz
  • 1 Böhnlein, Toni
  • 1 Grtizmann, Peter
  • 1 Lotker, Zvi
  • 1 Nivat, Maurice
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing

  • Refine by Keyword
  • 1 Combinatorics
  • 1 Discrete mathematics
  • 1 Graph spectra
  • 1 Grid graphs
  • 1 Image reconstruction
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 1997
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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