The Levenshtein distance as a measure of mirror symmetry and homogeneity for binary digital patterns

Abstract. The complexity of a digital pattern, image, map, or sequence of symbols is a salient feature that finds numerous applications in a variety of domains of knowledge [1], [7], [10], [11]. Two features of patterns that form inherent components of pattern complexity, are mirror (reflection) symmetry and homogeneity [8], [9]. In the raster graphics representation mode, a pattern consists of a two-dimensional array (matrix) of elements (pixels, symbols). It is assumed here that the elements are binary-valued (black-white). With such a representation it is common to compute properties of 2-dimensional patterns, such as complexity, mirror-symmetry, and homogeneity, along the 1-dimensional rows, columns, and diagonals of the array [4]. In addition, within each row, mirror symmetries may be analysed either globally or locally [3]. A pattern that does not exhibit global mirror symmetry may still possess an abundant number of local mirror symmetries. Local symmetries permit graded measures of symmetry rather than all-or-nothing decisions. One powerful type of local symmetry is the sub-symmetry, a contiguous subset of elements of the pattern that is palindromic (has mirror symmetry). It has been shown empirically that the total number of sub-symmetries present in a pattern may serve as an excellent predictor of the perception of both visual pattern complexity [5], and auditory pattern complexity [6]. The present research project explores how two well-known measures of the distance between binary patterns and their inversions, correlate with sub-symmetries, as well as other measures of symmetry and homogeneity.