The Levenshtein distance as a measure of mirror symmetry and homogeneity for binary digital patterns
Keywords: Mirror symmetry, Local symmetry, Global symmetry, Sub-symmetries, Levenshtein distance, Hamming distance, Pattern complexity, Krüger’s symmetry and homogeneity measures, Perception, Image processing, Artificial intelligence
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 , , , . Two features of patterns that form inherent components of pattern complexity, are mirror (reflection) symmetry and homogeneity , . 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 . In addition, within each row, mirror symmetries may be analysed either globally or locally . 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 , and auditory pattern complexity . 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.