Large families of “grey” arrays with perfect auto-correlation and optimal cross-correlation

Imants Svalbe, Matthew Ceko, Andrew Tirkel

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

1 Citation (Scopus)

Abstract

Digital watermarking applications have a voracious demand for large sets of distinct 2D arrays of variable size that possess both strong auto-correlation and weak cross-correlation. We use the discrete Finite Radon Transform to construct “perfect” p × p arrays, for p any prime. Here the array elements are comprised of the integers {0,\pm 1,+2\}. Each array exhibits perfect periodic auto-correlation, having peak correlation value p2, with all off-peak values being exactly zero. Each array, by design, contains just 3(p-1)/2 zero elements, the minimum number possible when using this “grey” alphabet. The grey alphabet and the low number of zero elements maximises the efficiency with which these perfect arrays can be embedded into discrete data. The most useful aspect of this work is that large families of such arrays can be constructed. Here the family size, M, is given by M = p2-1. Each of the M(M-1)/2 intra-family periodic cross-correlations is guaranteed to have one of the three lowest possible merit factors for arrays with this alphabet. The merit factors here are given by v2/(p2-v2), for v = 2, 3 and 4. Whilst the strength of the auto-correlation rises with array size p as p2, the strength of the many (order p4) cross-correlations between all M family members falls as 1/p2.

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
Pages46-56
Number of pages11
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

  • Discrete projection
  • Finite Radon Transform
  • Low cross-correlation arrays
  • Perfect arrays
  • Watermarking

Cite this

Svalbe, I., Ceko, M., & Tirkel, A. (2017). Large families of “grey” arrays with perfect auto-correlation and optimal cross-correlation. 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. 46-56). (Lecture Notes in Computer Science; Vol. 10502 LNCS). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-319-66272-5_5
Svalbe, Imants ; Ceko, Matthew ; Tirkel, Andrew. / Large families of “grey” arrays with perfect auto-correlation and optimal cross-correlation. 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. 46-56 (Lecture Notes in Computer Science).
@inproceedings{5e0fc8dd4bbf4b3babea7d7c1c26557b,
title = "Large families of “grey” arrays with perfect auto-correlation and optimal cross-correlation",
abstract = "Digital watermarking applications have a voracious demand for large sets of distinct 2D arrays of variable size that possess both strong auto-correlation and weak cross-correlation. We use the discrete Finite Radon Transform to construct “perfect” p × p arrays, for p any prime. Here the array elements are comprised of the integers {0,\pm 1,+2\}. Each array exhibits perfect periodic auto-correlation, having peak correlation value p2, with all off-peak values being exactly zero. Each array, by design, contains just 3(p-1)/2 zero elements, the minimum number possible when using this “grey” alphabet. The grey alphabet and the low number of zero elements maximises the efficiency with which these perfect arrays can be embedded into discrete data. The most useful aspect of this work is that large families of such arrays can be constructed. Here the family size, M, is given by M = p2-1. Each of the M(M-1)/2 intra-family periodic cross-correlations is guaranteed to have one of the three lowest possible merit factors for arrays with this alphabet. The merit factors here are given by v2/(p2-v2), for v = 2, 3 and 4. Whilst the strength of the auto-correlation rises with array size p as p2, the strength of the many (order p4) cross-correlations between all M family members falls as 1/p2.",
keywords = "Discrete projection, Finite Radon Transform, Low cross-correlation arrays, Perfect arrays, Watermarking",
author = "Imants Svalbe and Matthew Ceko and Andrew Tirkel",
year = "2017",
doi = "10.1007/978-3-319-66272-5_5",
language = "English",
isbn = "9783319662718",
volume = "10502 LNCS",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "46--56",
editor = "Kropatsch, {Walter G} and Artner, {Nicole M} and Ines Janusch",
booktitle = "Discrete Geometry for Computer Imagery",

}

Svalbe, I, Ceko, M & Tirkel, A 2017, Large families of “grey” arrays with perfect auto-correlation and optimal cross-correlation. 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. 46-56, International Conference on Discrete Geometry for Computer Imagery 2017, Vienna, Austria, 19/09/17. https://doi.org/10.1007/978-3-319-66272-5_5

Large families of “grey” arrays with perfect auto-correlation and optimal cross-correlation. / Svalbe, Imants; Ceko, Matthew; Tirkel, Andrew.

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. 46-56 (Lecture Notes in Computer Science; Vol. 10502 LNCS).

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

TY - GEN

T1 - Large families of “grey” arrays with perfect auto-correlation and optimal cross-correlation

AU - Svalbe, Imants

AU - Ceko, Matthew

AU - Tirkel, Andrew

PY - 2017

Y1 - 2017

N2 - Digital watermarking applications have a voracious demand for large sets of distinct 2D arrays of variable size that possess both strong auto-correlation and weak cross-correlation. We use the discrete Finite Radon Transform to construct “perfect” p × p arrays, for p any prime. Here the array elements are comprised of the integers {0,\pm 1,+2\}. Each array exhibits perfect periodic auto-correlation, having peak correlation value p2, with all off-peak values being exactly zero. Each array, by design, contains just 3(p-1)/2 zero elements, the minimum number possible when using this “grey” alphabet. The grey alphabet and the low number of zero elements maximises the efficiency with which these perfect arrays can be embedded into discrete data. The most useful aspect of this work is that large families of such arrays can be constructed. Here the family size, M, is given by M = p2-1. Each of the M(M-1)/2 intra-family periodic cross-correlations is guaranteed to have one of the three lowest possible merit factors for arrays with this alphabet. The merit factors here are given by v2/(p2-v2), for v = 2, 3 and 4. Whilst the strength of the auto-correlation rises with array size p as p2, the strength of the many (order p4) cross-correlations between all M family members falls as 1/p2.

AB - Digital watermarking applications have a voracious demand for large sets of distinct 2D arrays of variable size that possess both strong auto-correlation and weak cross-correlation. We use the discrete Finite Radon Transform to construct “perfect” p × p arrays, for p any prime. Here the array elements are comprised of the integers {0,\pm 1,+2\}. Each array exhibits perfect periodic auto-correlation, having peak correlation value p2, with all off-peak values being exactly zero. Each array, by design, contains just 3(p-1)/2 zero elements, the minimum number possible when using this “grey” alphabet. The grey alphabet and the low number of zero elements maximises the efficiency with which these perfect arrays can be embedded into discrete data. The most useful aspect of this work is that large families of such arrays can be constructed. Here the family size, M, is given by M = p2-1. Each of the M(M-1)/2 intra-family periodic cross-correlations is guaranteed to have one of the three lowest possible merit factors for arrays with this alphabet. The merit factors here are given by v2/(p2-v2), for v = 2, 3 and 4. Whilst the strength of the auto-correlation rises with array size p as p2, the strength of the many (order p4) cross-correlations between all M family members falls as 1/p2.

KW - Discrete projection

KW - Finite Radon Transform

KW - Low cross-correlation arrays

KW - Perfect arrays

KW - Watermarking

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

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

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

M3 - Conference Paper

SN - 9783319662718

VL - 10502 LNCS

T3 - Lecture Notes in Computer Science

SP - 46

EP - 56

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, Tirkel A. Large families of “grey” arrays with perfect auto-correlation and optimal cross-correlation. 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. 46-56. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-66272-5_5