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)


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
Number of pages11
Volume10502 LNCS
ISBN (Electronic)9783319662725
ISBN (Print)9783319662718
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

Publication series

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


ConferenceInternational Conference on Discrete Geometry for Computer Imagery 2017
Abbreviated titleDGCI 2017
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


  • 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). Springer.