Circulant Matrix Representation of Feature Masks and Its Applications

Rae-Hong Park; Byung Ho Cha    Department of Electronic Engineering, Sogang University, Seoul 100–611, South Korea

I Introduction

In this article, we present a circulant matrix interpretation of the edge and feature detection of images in the frequency domain and its further applications in various fields. This article presents a unified framework of previously published papers on the circulant matrix representation of edge detection and feature detection. We have reviewed the literature and unified the contexts based on a common vector-matrix representation of the circulant matrix. The spatial-domain relationship between the circulant matrix and the convolution in the linear time invariant (LTI) system is presented as a key idea of this work. Using the input-output relationship, we have presented the LTI system in vector-matrix form using a circulant matrix.

The circulant matrix has several useful properties in the discrete Fourier transform (DFT) domain and it is related to edge detection by compass gradient masks and Frei–Chen masks. We have presented the eigenvalue interpretation in the one-dimensional (1D) DFT domain, which makes the analysis of the compass gradient masks and Frei–Chen masks in the DFT domain simple. Similarly, feature masks are analyzed in the DFT domain. As an extension to the feature masks, the discrete cosine transform (DCT), discrete sine transform (DST), and discrete Hartley transform (DHT) masks are interpreted in the context of Frei–Chen masks. Also, the DHT interpretation using the singular value decomposition (SVD), based on the Karhunen–Loeve transform (KLT), is introduced by the circulant symmetric matrix.

The rest of this article is structured as follows: Section II reviews the basic matrix theory, especially special matrices such as circulant and circulant symmetric matrices, and a general case of orthogonal transforms. We explain the relationship between the convolution operation in the LTI system and the Toeplitz matrix. According to the properties of a circulant matrix, we can use eigenvalue analysis and diagonalization property in the DFT domain (Davis, 1994; Gray, 2000; Park and Choi, 1989, 1992). The circulant symmetric matrix also is related to representation of covariance matrices (Lay, 2003; Uenohara and Kanade, 1998).

In Section III, edge or line detection, one of fundamental steps in computer vision and pattern analysis, is presented, where edges or lines as features represent abrupt discontinuities in gray level, color, texture, motion, and so on (Gonzalez and Wintz, 1977; Jain, 1989; Rosenfeld and Kak, 1982). Two-dimensional (2D) 3 × 3 compass gradient masks such as the Prewitt, Sobel, and Kirsch masks, each of which consists of a set of eight directional edge components, have been commonly used in edge detection for their simplicity (Park and Choi, 1989, 1992; Yu, 1983). For a given pixel, at which 3 × 3 masks are centered, the relationship between eight intensity values of neighboring pixels and their kth (0 ≤ k ≤ 8) directional edge strength values are presented. The relationship can be expressed in vector-matrix form, where neighboring pixels are defined as the pixels covered by the 3 × 3 masks and diagonalized by the DFT matrix. In addition, edge detection by the orthogonal set of the 3 × 3 Frei–Chen masks is proposed based on a vector space approach (Frei and Chen, 1977; Park, 1990, 1998a; Park and Choi, 1990). Edge detection using the Frei–Chen masks is achieved by mapping the intensity vector using a linear transformation and then detecting edges based on the angle between the nine-dimensional (9D) intensity vector and its projection onto the edge subspace (Park, 1990). The 1D DFT domain interpretation of 3 × 3 compass gradient edge masks can be extended to complex-valued mask cases, making use of the circularity of the complex-valued weight matrix. Complex-valued compass gradient Prewitt and Sobel edge masks are expressed, in the 1D spatial and frequency domains, in terms of the two types of real-valued Frei–Chen masks (Park, 1998b, 1999a). The relationship between the compass roof masks and the Frei–Chen line masks also is presented (Park, 1998a). Generalization to analysis of N-directional complex-valued feature masks is presented (Park, 2002c). Simulation results with the synthetic image show the validity of the proposed interpretation of the edge and feature masks.

In Section IV, we can interpret four edge masks derived from the eight-point DHT. The DHT is real valued and computationally fast; thus it has been applied to various signal processing and interpretation applications. Basis functions of the eight-point DHT formulate the 3 × 3 DHT masks that are closely related to the Frei–Chen masks (Bracewell, 1986; Park et al., 1998). Similarly, the DCT and DST edge masks can be derived from the eight-point DCT and DST basis functions, respectively (Park, 1999b). We present DCT and DST basis functions first and then DHT basis functions. In addition, DHT basis functions are closely connected with KLT basis functions in advanced applications (Park, 2000, 2002a,b). Simulations with the synthetic and real (Lena) images show the validity of the proposed interpretation of various edge and feature masks.

Section V concludes the work.

II Mathematical Preliminaries

This section reviews the matrix representation of a general matrix and special kinds of matrices such as circulant matrices and symmetric circulant matrices. Properties of diagonalization and orthogonality of these matrices in the DFT domain are explained in detail. Finally, we present N-point orthogonal transforms.

A Vector-Matrix Representation

This section describes a general representation of a matrix and matrix properties, such as transpose, inverse, symmetry, diagonalization, and orthogonality. In addition, special matrices such as circulant matrices and symmetric circulant matrices are explained as mathematical tools for signal processing, especially related to the convolution in the LTI system.

1 Background of Vector-Matrix Representation

A matrix is a concise and useful way of representing a linear transformation. The transformations given by the equations

1 = a 11 ⁢ f 1 + a 12 ⁢ f 2 + a 13 ⁢ f 3 + … + a 1 ⁢ N ⁢ f N g 2 = a 21 ⁢ f 1 + a 22 ⁢ f 2 + a 23 ⁢ f 3 + … + a 2 ⁢ N ⁢ f N g 3 = a 31 ⁢ f 1 + a 32 ⁢ f 2 + a 33 ⁢ f 3 + … + a 3 ⁢ N ⁢ f N ⋮ g N = a N ⁢ 1 ⁢ f 1 + a N ⁢ 2 ⁢ f 2 + a N ⁢ 3 ⁢ f 3 + … + a N ⁢ N ⁢ f N

are represented in vector-matrix form by

1 g 2 g 3 ⋮ g N = a 11 a 12 a 13 … a 1 ⁢ N a 21 a 22 a 23 … a 2 ⁢ N a 31 a 32 a 33 … a 3 ⁢ N ⋮ ⋮ ⋮ ⋮ a N ⁢ 1 a N ⁢ 2 a N ⁢ 3 … a N ⁢ N ⁢ f 1 f 2 f 3 ⋮ f N .

Eq. (2) can be expressed simply by

= Af ,

which represents the input-output relationship of the linear system that will be explained in detail in Section III. Note that A denotes the linear system transformation with f (g) denoting the input (output) of the linear system. In Eq. (3), the N × N matrix A has several useful properties under the proper constraints.

The transpose of the N × N matrix A is denoted by At. The ith row of A is equal to the ith column of At, i.e., (At)ij = Aji:

= a 11 a 12 a 13 ...