Maximal n-ghosts and minimal information recovery from n projected views of an array

Imants Svalbe, Matthew Ceko

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

Digital data is now frequently stored privately and securely in the “cloud”. One repository stores several different sets of projections of the original data. Each set is kept on a separate, remote server. The information residing on any local server, purposefully, is insufficient to exactly reconstruct the full data. Here we ask: how much useful information can be gleaned from one local projection set? We answer that question by examining projection ghosts. A ghost is an assembly of signed pixels positioned to have zero sums along chosen discrete directions. The shape of each ghost is defined uniquely by its distinct set of N directions. An N-ghost with a shape that fits snuggly inside the boundary of an array defines precisely all of the array locations that cannot be exactly reconstructed from those N projected views. Minimal N-ghosts contain 2N elements: one (-1/+1) pair is needed for zero-sums along each of the N directions. Maximal N-ghosts contain $$2^N$$ elements: the number of (-1/+1) elements can double N times, once for each of the N directions. Here we construct maximal N-ghosts that cover a large area of their bounding array. By maximising the number of unrecoverable ghosted pixels, we minimise the information that can be reconstructed from N projected views. We show that at least 60% of the data in an m × m array, for m ≈ N2/4, can be masked or made “unreadable”, for a maximal set of N noise-free projections of the original m × m data.

Original languageEnglish
Title of host publicationDiscrete Geometry for Computer Imagery
Subtitle of host publication20th IAPR International Conference, DGCI 2017, Proceedings
EditorsWalter G Kropatsch, Nicole M Artner, Ines Janusch
Place of PublicationCham Switzerland
PublisherSpringer
Pages135-146
Number of pages12
Volume10502 LNCS
ISBN (Electronic)9783319662725
ISBN (Print)9783319662718
DOIs
Publication statusPublished - 2017
EventInternational Conference on Discrete Geometry for Computer Imagery 2017 - Campus Gußhaus of TU Wien, Vienna, Austria
Duration: 19 Sep 201721 Sep 2017
Conference number: 20th
http://dgci2017.prip.tuwien.ac.at

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing AG
Volume10502 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Discrete Geometry for Computer Imagery 2017
Abbreviated titleDGCI 2017
CountryAustria
CityVienna
Period19/09/1721/09/17
OtherThe aim of the DGCI conference is to gather researchers in discrete geometry and topology, and discrete models, with applications in image analysis and image synthesis.

Discrete geometry plays an expanding role in the fields of shape modelling, image synthesis, and image analysis. It deals with topological and geometrical definitions of digitized objects or digitized images and provides both a theoretical and computational framework for computer imaging.
Internet address

Keywords

  • Cloud storage
  • Data security
  • Discrete projection
  • Mojette transform
  • Tomographic reconstruction

Cite this

Svalbe, I., & Ceko, M. (2017). Maximal n-ghosts and minimal information recovery from n projected views of an array. In W. G. Kropatsch, N. M. Artner, & I. Janusch (Eds.), Discrete Geometry for Computer Imagery: 20th IAPR International Conference, DGCI 2017, Proceedings (Vol. 10502 LNCS, pp. 135-146). (Lecture Notes in Computer Science; Vol. 10502 LNCS). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-319-66272-5_12
Svalbe, Imants ; Ceko, Matthew. / Maximal n-ghosts and minimal information recovery from n projected views of an array. Discrete Geometry for Computer Imagery: 20th IAPR International Conference, DGCI 2017, Proceedings. editor / Walter G Kropatsch ; Nicole M Artner ; Ines Janusch. Vol. 10502 LNCS Cham Switzerland : Springer, 2017. pp. 135-146 (Lecture Notes in Computer Science).
@inproceedings{b1a24cf989f04d3aa947a1d8c08990af,
title = "Maximal n-ghosts and minimal information recovery from n projected views of an array",
abstract = "Digital data is now frequently stored privately and securely in the “cloud”. One repository stores several different sets of projections of the original data. Each set is kept on a separate, remote server. The information residing on any local server, purposefully, is insufficient to exactly reconstruct the full data. Here we ask: how much useful information can be gleaned from one local projection set? We answer that question by examining projection ghosts. A ghost is an assembly of signed pixels positioned to have zero sums along chosen discrete directions. The shape of each ghost is defined uniquely by its distinct set of N directions. An N-ghost with a shape that fits snuggly inside the boundary of an array defines precisely all of the array locations that cannot be exactly reconstructed from those N projected views. Minimal N-ghosts contain 2N elements: one (-1/+1) pair is needed for zero-sums along each of the N directions. Maximal N-ghosts contain $$2^N$$ elements: the number of (-1/+1) elements can double N times, once for each of the N directions. Here we construct maximal N-ghosts that cover a large area of their bounding array. By maximising the number of unrecoverable ghosted pixels, we minimise the information that can be reconstructed from N projected views. We show that at least 60{\%} of the data in an m × m array, for m ≈ N2/4, can be masked or made “unreadable”, for a maximal set of N noise-free projections of the original m × m data.",
keywords = "Cloud storage, Data security, Discrete projection, Mojette transform, Tomographic reconstruction",
author = "Imants Svalbe and Matthew Ceko",
year = "2017",
doi = "10.1007/978-3-319-66272-5_12",
language = "English",
isbn = "9783319662718",
volume = "10502 LNCS",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "135--146",
editor = "Kropatsch, {Walter G} and Artner, {Nicole M} and Ines Janusch",
booktitle = "Discrete Geometry for Computer Imagery",

}

Svalbe, I & Ceko, M 2017, Maximal n-ghosts and minimal information recovery from n projected views of an array. in WG Kropatsch, NM Artner & I Janusch (eds), Discrete Geometry for Computer Imagery: 20th IAPR International Conference, DGCI 2017, Proceedings. vol. 10502 LNCS, Lecture Notes in Computer Science, vol. 10502 LNCS, Springer, Cham Switzerland, pp. 135-146, International Conference on Discrete Geometry for Computer Imagery 2017, Vienna, Austria, 19/09/17. https://doi.org/10.1007/978-3-319-66272-5_12

Maximal n-ghosts and minimal information recovery from n projected views of an array. / Svalbe, Imants; Ceko, Matthew.

Discrete Geometry for Computer Imagery: 20th IAPR International Conference, DGCI 2017, Proceedings. ed. / Walter G Kropatsch; Nicole M Artner; Ines Janusch. Vol. 10502 LNCS Cham Switzerland : Springer, 2017. p. 135-146 (Lecture Notes in Computer Science; Vol. 10502 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Maximal n-ghosts and minimal information recovery from n projected views of an array

AU - Svalbe, Imants

AU - Ceko, Matthew

PY - 2017

Y1 - 2017

N2 - Digital data is now frequently stored privately and securely in the “cloud”. One repository stores several different sets of projections of the original data. Each set is kept on a separate, remote server. The information residing on any local server, purposefully, is insufficient to exactly reconstruct the full data. Here we ask: how much useful information can be gleaned from one local projection set? We answer that question by examining projection ghosts. A ghost is an assembly of signed pixels positioned to have zero sums along chosen discrete directions. The shape of each ghost is defined uniquely by its distinct set of N directions. An N-ghost with a shape that fits snuggly inside the boundary of an array defines precisely all of the array locations that cannot be exactly reconstructed from those N projected views. Minimal N-ghosts contain 2N elements: one (-1/+1) pair is needed for zero-sums along each of the N directions. Maximal N-ghosts contain $$2^N$$ elements: the number of (-1/+1) elements can double N times, once for each of the N directions. Here we construct maximal N-ghosts that cover a large area of their bounding array. By maximising the number of unrecoverable ghosted pixels, we minimise the information that can be reconstructed from N projected views. We show that at least 60% of the data in an m × m array, for m ≈ N2/4, can be masked or made “unreadable”, for a maximal set of N noise-free projections of the original m × m data.

AB - Digital data is now frequently stored privately and securely in the “cloud”. One repository stores several different sets of projections of the original data. Each set is kept on a separate, remote server. The information residing on any local server, purposefully, is insufficient to exactly reconstruct the full data. Here we ask: how much useful information can be gleaned from one local projection set? We answer that question by examining projection ghosts. A ghost is an assembly of signed pixels positioned to have zero sums along chosen discrete directions. The shape of each ghost is defined uniquely by its distinct set of N directions. An N-ghost with a shape that fits snuggly inside the boundary of an array defines precisely all of the array locations that cannot be exactly reconstructed from those N projected views. Minimal N-ghosts contain 2N elements: one (-1/+1) pair is needed for zero-sums along each of the N directions. Maximal N-ghosts contain $$2^N$$ elements: the number of (-1/+1) elements can double N times, once for each of the N directions. Here we construct maximal N-ghosts that cover a large area of their bounding array. By maximising the number of unrecoverable ghosted pixels, we minimise the information that can be reconstructed from N projected views. We show that at least 60% of the data in an m × m array, for m ≈ N2/4, can be masked or made “unreadable”, for a maximal set of N noise-free projections of the original m × m data.

KW - Cloud storage

KW - Data security

KW - Discrete projection

KW - Mojette transform

KW - Tomographic reconstruction

UR - http://www.scopus.com/inward/record.url?scp=85029484001&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-66272-5_12

DO - 10.1007/978-3-319-66272-5_12

M3 - Conference Paper

SN - 9783319662718

VL - 10502 LNCS

T3 - Lecture Notes in Computer Science

SP - 135

EP - 146

BT - Discrete Geometry for Computer Imagery

A2 - Kropatsch, Walter G

A2 - Artner, Nicole M

A2 - Janusch, Ines

PB - Springer

CY - Cham Switzerland

ER -

Svalbe I, Ceko M. Maximal n-ghosts and minimal information recovery from n projected views of an array. In Kropatsch WG, Artner NM, Janusch I, editors, Discrete Geometry for Computer Imagery: 20th IAPR International Conference, DGCI 2017, Proceedings. Vol. 10502 LNCS. Cham Switzerland: Springer. 2017. p. 135-146. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-66272-5_12