Abstract
This paper introduces the analysis of pattern properties by means of the two-sided Reed-Muller-Fourier transform. Patterns are modelled as matrices of pixels and an integer coding for the colors is chosen. Work is done in the ring \((Z_{p},\oplus , \cdot )\), where \(p >2\) is not necessarily a prime. It is shown that the transform preserves the (diagonal) symmetry of patterns, is compatible with different operations on patterns, and allows detecting and localizing noise pixels in a pattern. Finally, it is shown that there are patterns which are fixed points of the transform.
Access provided by CONRICYT-eBooks. Download conference paper PDF
Similar content being viewed by others
Keywords
- Transform Applied
- Pixel Noise
- Kronecker Product Structure
- Inverse Matrix Representation
- GENERALIZED GIBBS
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
1 Introduction
The Reed-Muller-Fourier transform (RMF), defined in the ring \((Z_{p}, \oplus , \cdot )\), p an integer larger than 2, was introduced in [1] aiming to unify relevant characteristics of the Reed-Muller transform (RM) and the Discrete Fourier transform (DFT), to be applied in the non-binary integer domain allowing to obtain polynomial expressions for multiple-valued functions. In the binary case, the RM transform has a self inverse matrix representation, which is lower triangular, and exhibits a Kronecker product structure [2,3,4]. When the RM transform was extended to the non-binary domain [5], it retained the property of realizing a bijection in the set of functions for a given valuedness and arity, but it lost the lower triangular structure and its self inversion. The DFT, however is lower triangular in all integer domains. To obtain the desired combination of properties for the RMF transform, the Gibbs algebra defined in terms of the Gibbs multiplication for the Instant Fourier Transform [6] was selected and extended to the non-binary domain in [1].
In the context of patterns, let \(\varGamma \) be a finite ordered set of colors with cardinality p, and let \(\beta : \varGamma \rightarrow Z_{p}\) be a bijection assigning an element of \(Z_{p}\) to each color in such a way that the ordering of the colors is preserved. Pixels are atoms of a picture and carry a single color. (The size of a pixel is defined according to requirements of geometric and chromatic resolution for a pattern under consideration.) A pattern is an array of pixels. In this paper, a pattern is also represented as a matrix with entries from \(Z_{p}\) obtained by applying \(\beta \) to every pixel of a picture. Operations among patterns are conducted on the corresponding numerical matrices in the ring \((Z_{p}, \oplus , \cdot )\). Pattern attributes associated to a matrix are understood as attributes of the pattern represented by such a matrix.
2 Formalisms
In what follows, some properties of patterns will be studied in a transform domain. In this paper, we select the Reed-Muller-Fourier (RMF) transform [1, 2, 7]. It is known that this transform matrix is lower triangular, self-inverse and has a Kronecker product structure [8]. Moreover, this transform is based on the Gibbs convolutional product [4]. Figure 1 shows the basic transform matrices for \(p = 4,5\), and 6 as will be used in this paper.
The following notation will be used in the rest of the paper: \(\mathbf{A}(n)\) will denote a \((p^{n}\times p^{n})\) matrix (and pattern). \(\mathbf{A}(n,m)\) will denote a \((p^{n} \times p^{m})\) matrix (and pattern). For the RMF-transform matrix, the notation \(\mathbf{R}_{p}(n)\) will be used. (If a related statement is valid for all p, the index p may be omitted.)
For a given p and n, the RMF-transform matrix is defined as the n-th Kronecker power of the basic RMF-transform matrix \(\mathbf{R}_{p}(1)\). Therefore,
H(n) will represent a matrix with all entries equal to 1 (H for “high”) and L(n) will denote a matrix with all entries equal to 0 (L for “low”). Finally, C(n) will represent a matrix with all entries equal to 0, except for the element at the left upper corner, where the entry equals 1 (leading to the name “corner”). For the analysis of patterns, a two-sided RMF-transform will be used (see definition below), a transformed pattern will be called “spectrum” and will be identified by \(\varSigma \). Unless otherwise specified, all operations will be done in the ring \((Z_{p}, \oplus , \cdot )\).
3 Analysis of Patterns by Using the RMF-Transform
In this section, we will present some considerations related to the application of the RMF-transform to analysis of patterns.
Definition 1
Given a pattern A(n, m), its spectrum \(\varSigma _{A}(n,m)\), is calculated as follows
where the superindex T denotes the transposition of a matrix.
Lemma 1
The inverse RMF transform recovers a pattern from its spectrum as follows
Proof:
Since \(R_{p}(n)\) is its own inverse, the assertion follows by applying \(R_{p}(n)\) and \((R_{p}(m))^{T}\) at both sides of Eq. (1).
Lemma 2
For all p the RMF spectrum of a square symmetric pattern is symmetric.
Proof:
If A(n) is symmetric, it holds that \(A(n) = (A(n))^{T}\). Then,
Lemma 3
If \(\mathbf{Q}(n,m) = \mathbf{A}(n,m) \oplus \mathbf{B}(n,m)\) then \(\varSigma _{Q}(n,m) = \varSigma _{A}(n,m) \oplus \varSigma _{B}(n,m)\).
Proof:
See examples in Fig. 2.
Lemma 4
The spectrum of the Kronecker product [3, 4] of two patterns equals the Kronecker product of the respective spectra. If \(\mathbf{Q}(n+r, m+s) = \mathbf{A}(n,m) \otimes \mathbf{B}(r,s)\) then \(\varSigma _{Q}(n+r, m+s) = \varSigma _{A}(n,m) \otimes \varSigma _{B}(r,s)\).
Proof:
With the compatibility theorem between Kronecker and matrix products [3],
Notice that Eq. (3) may also be written as
Since \((\mathbf{I}(n) \otimes \mathbf{R}(r)) = Diag(\mathbf{R}(r), \mathbf{R}(r), \ldots , \mathbf{R}(r))\) let it be called “the n-Block RMF transform”. Then the following is obtained:
Corollary 1
The RMF spectrum of the Kronecker product of two patterns \(\mathbf{A}(n,m)\) and \(\mathbf{B}(r,s)\), equals the n-Block RMF transform based spectrum of the Kronecker product of the (simple) RMF spectrum of the first pattern and the second pattern.
Lemma 5
Proof:
\(\mathbf{C}(0,n) = [1, 0, \ldots , 0]\). \(\varSigma _{C}(0,n) = \mathbf{R}(0) \mathbf{C}(0,n) \mathbf{R}^{T}(n) = [1, 0, \ldots , 0]{} \mathbf{R}^{T}(n)\).
Since \([1, 0, \ldots , 0]\mathbf{R}^{T} (n)\) returns the first row of \(\mathbf{R}t (n)\), which equals \(\mathbf{H}(0,n)\) -(see Fig. 2)- then \(\mathbf{C}(0,n) = \mathbf{H}(0, n)\). Similarly, \(\mathbf{C}(m,0) = \mathbf{H}(m,0)\). Considering that \(\mathbf{C}(m,n) = \mathbf{C}(m,0) \otimes \mathbf{C}(0,n)\), with Lemma 4 follows that:
Remark 1
Lemma 5 is a two-dimensional discrete extension of the Fourier transform of an impulse.
Corollary 2
Definition 2
For a given pair \((i, j ), i \in Z_{p^{m}}\) and \(j\in Z_{p^{n}}\), let \(\mathbf{P}(m,n)\) denote a “perturbation” matrix with a single 1 entry at the position (i, j), otherwise having 0 entries. Then, \(\mathbf{P}(m,n) = [0,0, \ldots , 0,1, 0, \ldots ,0] \otimes [0, 0, \ldots , 0, 1, 0, \ldots , 0]^{T}\), where the vectors are of length \(p^{m}\) and \(p^{n}\) respectively, the first 1 is at the j-th position and the second, at the i-th position.
Lemma 6
For a given pair (i, j) as in Definition 2, in the RMF spectrum \(\varSigma _{P}(m,n)\) the first i rows are 0-rows and the first j columns are 0-columns. The entry at the position (i, j) has the absolute value 1 and the remaining entries are mostly non-zero entries.
Proof:
Let \(\mathbf{P}(0,n) = [0,0, \ldots , 0,1, 0, \ldots ,0]\), with the 1 at the j-th position. Then,
It may be seen that the product \([0,0, \ldots , 0,1, 0, \ldots ,0]\cdot \mathbf{R}^{T}(n)\) extracts the j-th row of \(\mathbf{R}^{T}(n)\). Since \(\mathbf{R}^{T}(n)\) is upper triangular -(recall Fig. 2)- the j-th row has a prefix of j 0s and the first non-zero entry equals \((-1)^{j-1} \bmod p\).
Similarly, \(\mathbf{P}(m,0) = [0, 0, \ldots , 0, 1, 0, \ldots , 0]^{T}\), with the 1 at the i-th position. Then,
The product \(\mathbf{R}(m) [0, 0, \ldots , 0, 1, 0, \ldots , 0]^{T}\) extracts the i-th column of \(\mathbf{R}(m)\). Since \(\mathbf{R}(m)\) is lower triangular, its i-th column has a prefix of i 0s and the first non-zero entry equals \((-1)^{i-1} \bmod p\).
It may be seen that \(\mathbf{P}(0,n) \otimes \mathbf{P}(m,0)\) will have the first i rows and the first j columns with 0 entries. Moreover, at (i, j) the entry has magnitude \(1 \bmod p\).
Example 1
For \(p = 6\), Fig. 3 shows \(\mathbf{P}(1)\) with \((i,j) = (4,2)\).
It may be seen that the “left upper non-zero” pixel in the spectrum indicates the position of the perturbing pixel. This property may be used to detect and localize a noise pixel.
Definition 3
A mosaic is the Kronecker product of \(\mathbf{H}(n,m)\) and a basic pattern \(\mathbf{B}(r,s)\).
Example 2
Let \(p = 4\) and (for space limitations) let \(n = 1\) for \(\mathbf{H}\). Then define \(\mathbf{M}(1+r, 1+s) = \mathbf{H}(1) \otimes \mathbf{B}(r, s)\). From Lemma 4 and Corollary 2 follows that \(\varSigma _{M}(1+r, 1+s) = \varSigma _{H}(1) \otimes \varSigma _{B}(r, s) = C(1) \otimes \varSigma _{B}(r, s)\).
It becomes apparent that if a random noise pixel is added to the mosaic during the building process, with Lemma 3, the 0-region of the spectrum will be clearly “contaminated”, thus detecting the presence of a noise pixel. Moreover the position of the upper left corner of the non-zero contaminating region clearly localizes the noise pixel.
Remark 2
The matrix which has a 1-entry at the right lower corner being otherwise 0 is a fixpoint of the two-sided RMF transform. Notice that this may be interpreted as a consequence of Lemma 6 and, therefore, is valid for all p. Additional examples of fixed points are shown in Fig. 4. Recall that with Lemmas 3 and 4 new (and larger) fixed points may be generated.
4 Conclusions
For the first time the RMF transform has been applied to analyze properties of patterns. Possibly the most relevant result refers to the possibility of both detecting and localizing noise pixels in patterns.
References
Stanković, R.S.: Some remarks on Fourier transforms and differential operators for digital functions. In: Proceeding of the 22nd International Symposium on Multiple-Valued Logic, Sendai, Japan, pp. 365–370 (1992). https://doi.org/10.1109/ISMVL.1992.186818
Karpovsky, M.G., Stanković, R.S., Astola, J.T.: Spectral Logic and Its Application for the Design of Digital Devices. Wiley, Hoboken (2008)
Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, New York (1991)
Graham, A.: Kronecker Products and Matrix Calculus with Applications. Ellis Horwood Ltd., Chichester (1981)
Green, D.H., Taylor, I.S.: Multiple-valued switching circuit design by means of generalized Reed-Muller expansions. Dig. Process. 2, 63–81 (1976)
Gibbs, J.E.: Instant Fourier transform. Electron. Lett. 13(5), 122–123 (1977)
Stanković, R.S.: The Reed-Muller-Fourier transform—computing methods and factorizations. In: Seising, R., Allende-Cid, H. (eds.) Claudio Moraga: A Passion for Multi-Valued Logic and Soft Computing. SFSC, vol. 349, pp. 121–151. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-48317-7_9
Stanković, R.S., Stanković, M., Moraga, C.: The Pascal triangle (1654), the Reed-Muller-Fourier transform (1992), and the Discrete Pascal transform (2005). In: Proceedings of the 46th International Symposium on Multiple-Valued Logic, pp. 229–234. IEEE Press, New York (2016). https://doi.org/10.1109/ISMVL.2016.24
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Moraga, C., Stanković, R.S. (2018). The Reed-Muller-Fourier Transform Applied to Pattern Analysis. In: Moreno-Díaz, R., Pichler, F., Quesada-Arencibia, A. (eds) Computer Aided Systems Theory – EUROCAST 2017. EUROCAST 2017. Lecture Notes in Computer Science(), vol 10672. Springer, Cham. https://doi.org/10.1007/978-3-319-74727-9_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-74727-9_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-74726-2
Online ISBN: 978-3-319-74727-9
eBook Packages: Computer ScienceComputer Science (R0)