Computer Graphics & Geometry
Vladimir M. Chernov
Image Processing Systems Institute of RAS
Russia,Samara 51 Molodogvardejskaya St., IPSI RAS, 443001
Phone: +7(8462)322994.
Fax: +7(8462)322763
vche@smr.ru
Keywords: Texture, Primitive extraction, p-adic numbers.
It is stated in contemporary papers that almost all effective methods of texture classification or segmentation are based either on statistical or structural approaches [1]. Statistical methods, such as using co-occurrence matrices and autoregression models, describe texture by using statistics obtained from local image features (e.g. [2], [3]). Generally speaking, such methods are suitable for processing irregular textures with random distribution of brightness function of picture elements. A specific lack of the direct statistical approach is disregarding structural (or geometrical) image properties, which is inherent to a wide range of textures.
Structural methods assume that texture is a set of periodical fragments. It is claimed in papers [1], [4], [5] that a wide class of textures has a concealed periodical ''quasilinear'' structure with unknown parameters of the periodicity. On the other hand, some metrically invariant objects on the discrete plane have visually the same ''quasilinear'' structure.
The authors do not intend to discuss advantages and disadvantages of alternative approaches to solving particular tasks of texture analysis. We shall note that these geometric (metric ones included) characteristics of an image do not have to be described adequately in terms of conventional Euclidean geometry. Moreover, while solving pattern recognition and computer vision tasks, it may turn out that the most informative features can be obtained from the analysis of metric image properties which cannot be interpreted clearly in terms of ''ordinary'' concepts of distance, closeness, etc. (see [6]). Therefore, first of all, the purpose of this paper is to illustrate the possibilities of mathematical techniques relatively new for the Computer Science - the theory of non-Archimedean (p-adic) normalized spaces (e.g. [7], [8]), - in tasks of forming the features space. Textures are a convenient testing ground for demonstration of such possibilities.
With respect to the statistical and structural approaches mentioned above, the method suggested in this paper is considered to be intermediate. On the one hand, the proposed algorithm of extracting primitives is purposed to reveal ''hidden'' quasi-periodic components of a texture image. On the other hand, we use ''stochastic'' (or ''random'') properties of some functions and objects associated with prime numbers in conjunction with spectral methods. The latter is common for the statistical approach.
In concept, the principal ideas of the method being described are not absolutely new. Formation of features on the base of different algebraic image invariants is one of the main techniques in pattern recognition [9] . Different metric structures associated with textures of particular classes has been a subject in paper [10], etc.
In the papers [11], [12] the authors proposed the method of extracting components associated with specific plane metrics (the so-called non-Archimedean or p-adic metrics). From here on we shall call this method a method of p-adic resonance. The novelty of the approach of this paper is applying non-Archimedean (p-adic) norms - and their extensions onto the discrete plane - to extacting metric invariants of textures. As shown below, these invariants are some binary images (primitives) associated with some set of primes and also metrics connected with them. These primitives can be used directly for recognition by experts or forming numerical characteristics and, consequently, features space. The possibility is at the basis of the method that one can (in a parallel way) extract one or several components from a texture image, each of them has geometric properties which can be easily distinguished visually or analysed numerically.
In this paper we continue their work on developing combined geometric and statistical methods of texture analysis. In particular, we describe examples of practical applications of this method to solving some tasks of texture analysis, i.e. segmentation and detection of texture defects.
It is well-known that prime numbers form the multiplicative basis of the natural numbers semigroup: each natural number can be presented as a product of degrees of prime numbers. On the other hand, the tasks concerned with analysis of additive properties of primes (e.g. their distribution in the positive integers) are quite difficult (e.g. see [13], [14]). It is clear: additive properties of the multiplicative objects are hard to analyze. ''Irregular behavior'' of primes leads to the idea about some ''independence'' of the features associated with different primes. ''The prime numbers play games of chance'' wrote Kac [15]. Some approaches to formalization of the naive understanding of prime numbers independence are described in this book with argumentation convincing enough.
First of all, in texture analysis tasks the researcher is interested in geometric properties of an image. Therefore we shall consider image properties in specific geometries associated with prime numbers.
Let p be a prime. Let us assume np(a) to be the p-adic exponent of an integer number a, that is the largest nonnegative number m for which
For a rational number x = [a/b] the exponent np(x) is assumed to be
Let us define a p-adic (non-Archimedean) norm on the set of rational numbers by means of the relation
| (1) |
Similarly to the fact that the completion of the field Q with respect to the usual norm ||x||¥ = |x| leads to the forming of real numbers field, its completion with respect to the norm ||x||p leads to the forming of p-adic numbers field Qp . In a standard way, a metric rp(x,y) is induced by the norm:
|
In particular, two integers are ''close'' if their difference is divided by a high degree of the given prime p.
Similarly to the fact that the norm ||·||¥ can be supplemented onto Q2, the norm ||·||p can be also supplemented onto Q2 in a number of ways.
Proposition 1. Let d be an integer free of squares. Let z = (x,y) Î Q2, g = 1,...,p-1, then the functions
| (2) |
| (3) |
Remark 1. The norms Yp,*(j)(z) are connected directly with p-adic valuations on quadratic fields
|
|
|
Proposition 2. Linear operators A: Q2® Q2 with the following matrices:
| (4) |
The form of the operators considered in Proposition 2 does not depend on non-residue d and integer g. It is defined by five integer coefficients {p;a,b,c,d} of the A matrix only.
Let a real-valued non-negative function x(n1,n2) = x(n) is defined on the set
|
Definition 1. Let us call Yp,*(j)(n)-primitive texture (or p-primitive) functions x(n), which have a constant non-zero value for n that belong to the full sphere with center in the origin of Z2 and Yp,*(j)(n)-diameters less or equal to p-1:
|
Remark 2. Independently of d and g, p-primitives are invariant with respect to action of any operator of linear isometry considered in Proposition 2.
Examples of images composed from some Yp,*(j)-primitives for different p, d and g are shown in Figs.1a-1b.
|
|
|
| 1A | 1B |
Examples of textures obtained from images in Figs. 1a-1b by using some distorting operator (namely, gaussian blur and additive noise) are shown in Figs. 2a-2b. Fig. 3 shows typical Brodatz textures [16].
|
|
|
| 2A | 2B |
In contrast with a real texture, primitive textures have a formalized description and are easier to analyze.
|
|
|
| 3A | 3B |
Prposition 3. Let w = exp{[(2pi)/(pr)]}, p be a prime,
|
| (5) |
| (6) |
Congruencies (6) define Yp,*(j)-neighborhoods of the zero with the diameters less than or equal to p-r+1. Therefore, taking into account the Parseval equality, we can conclude that the spectrum power is localized inside the neighborhood of the zero with a little Yp,*(j)-diameter. In case of a real texture image, this localization is obviously not so noticeable. But by choosing a ''good'' norm, the main part of the spectrum power is concentrated around the zero.
Let b be a subset of primes, h be a subset of norms Yp,*(j) for p Î b . Let an image (a texture) x(n) be presented in the form:
| (7) |
Let Is(hp) be a subset of Yp,*(j)-isometries (4) for hp, Card(Is(hp)) be its cardinality. We shall consider an action of the averaging operator Mp on an image (7):
| (8) |
Taking into account the quite general assumptions about statistical independence of values of the function xnon(n), the signal/noise ratio for the averaged image is larger than for the image xnon(n). Certainly, accurate numerical estimations can be obtained only for the artificially synthesized images. For real textures the correctness of this assumption can be confirmed experimentally.
Let us choose a class h = Èhp (p Î b) of norms Yp,*(j) that is representative enough. For each p and Yp,*(j) we shall define a finite set of isometries, and consider averaged images Mpx(n). After the thresholding and the binarization, we shall receive a set of primitive textures. These primitive textures and/or their numerical characteristics can be considered as features of real textures, and the convenient pattern recognition methods can be applied.
Really, invariant properties of a real texture with respect to Yp,*(j)-isometries are unknown a priori, however, ''prime numbers play games of chance'', don't they?
Step 1. Let (N×N) be the size of the image x(n) = x(n1,n2) being processed. We shall choose a subset b of prime numbers p, and consider a set of norms
|
Step 2. For each p Î b we shall calculate DFT of the image of size Np×Np, where Np = pr £ N.
Step 3. Let J be some operator of isometry (4), detJ = 1 and [x]J(m) be the DFT-spectrum of signal x(Jn), < n,m > = n1m1+n2m2.
Then J induces the dual operator J* acting on pairs of indexes of the spectral components (5):
| ||||||||||||||||||||||||||
| (9) |
For the chosen e we shall find a set b0 Ì \b of ''good'' prime numbers subject to the condition:
| (10) |
Step 4. For all the primes p Î b0 and for Y Îhp we shall define functions
| (11) |
|
We consider the set of images Yp(n) as distorted primitive textures (''Yp,*(j)-components of a real texture'') associated with ''good'' norms Yp,*(j) under the condition (10). The obtained images can be used for visual qualitative analysis of the significant components of the given texture. Fig. 4 shows the original test texture as well as primitives extracted for ''good'' primes.
|
|
|
| 4A | 4B |
|
|
|
4C |
Figure 4: (a) Fragment of synthesized texture.
(b)-(c) Two extracted primitive (resonant components).
The most obvious characteristic which distincts significantly resonance and non-resonance cases is a histogram of texture. Fig. 5 shows an example of synthesized texture.
(b)
(c)
Figure 5: (a) Typical histogram of texture.
(b) Histogram of the
averaged image (resonant case: p = 13).
(c) Histogram of the averaged image
(non-resonant case: p = 17).
One can see that histogram on Fig. 5c are similar to Gaussian distributions. Histogram on Fig. 5b is trimodal that indicates that a primitive exists.
Figs. 6a-6c shows fragments of primitives extracted with the described method from Brodatz texture. The average in (8) for primes p = 2,...,29 was calculated under
We shall note peculiarities of the realization of the proposed method. In [17] an algorithm of 2-D DFT (''DFT with a multicovering'') is described. Its structure is obviously associated with a covering of summation area with neighborhoods of decreasing Yp,g(2)-diameters for all g at once. This allows to find the set while calculating the DFT.
 |
| 6A |
|
|
|
| 6A | 6C |
Figure6: Primitives extraction from Brodatz texture.
Let us take an image which consists of several different textures, and separate them applying the proposed method. We shall extract primitives using the sliding window method. Several parallel branches of the algorithm will correspond to several prime numbers, the vector of features will consist of numerical characteristics obtained for every prime number.
Fig. 7a-7b show results of separating the features space into two classes.
|
|
|
| 7A | 7B |
Figure 7: Results of separation the features space into two classes.
(a) Original texture. (b) Segmetation result.
In this example we considered local mean value and local empirical coefficient of correlation to be features.
Fig. 8a-8d show results of detecting borders of texture defects on the base of estimating modular moments
|
|
|
|
| 8A | 8B |
|
|
|
| 8C | 8D |
Brodatz texture, p = 11.
Figure 8: Results of detecting borders of texture defects.
So the proposed method of p-adic resonance is a subsequent realization of the following closely interrelated ideas.
1. If an image is invariant over some group G of all transforms of the (discrete) plane, the relation (8) gives an image that coincides with the original image.
2. If x(n) is represented as a sum of G-invariant signal and non-invariant component (see (7)), the signal-noise ratio for ( 8) is higher than for x(n).
3. Since it is very difficult to describe the group G of all transforms for the real image x(n), we extract from x(n) components invariant over well-known groups with the simple structures. These components and/or their numerical characteristics are considered to be features of the image x(n), and the standard methods of pattern recognition can be applied.
4. The metrics (2) and (3) are extensions of p-adic metric of the field Qp onto Z2 . We consider group G to be a group of p-adic isometries whith matrices (4).
5. Applying the transform (8) to the image for some set of primes p followed by thresholding enables either to extract a ''hidden'' p-adic invariant component for the given p, or to state that it is not present. The binary vector for the specified set of primes can be presented to experts for identifying the texture. More accurate analysis can be performed using numerical characteristics (features) obtained.
In author's opinion, the capabilities of the ''resonance'' approach described in the paper are not limited to the applications considered above. In particular, in [] the author used similar approach to the visual extraction of binary primitives with predetermined geometric configuration (e.g. with local-symmertic properties).
The work was supported by the Russian Foundation for Basic Research (Grant No. 00-01-00600).
I would like to thank my joung colleague, Andrew Shabashew, for interesting experimental results.
Computer Graphics & Geometry
