Method for Detecting Target Patterns in a Texture Region Using Probability Densities

This invention relates to a process for pattern detection in static or dynamic systems.

The systems contemplated herein encompass, in the broadest sense, all physical, chemical or bio-medical processes or materials with a state or individual features which can be characterized with a set of n parameters. The systems can be invariable (static) or variable over time (dynamic) in the study interval. In the case of dynamic systems, time is one of n parameters.

The characterizing parameters are formed either by system-imminent or by externally induced physical or technical features. They can comprise especially geometric arrangements, time arrangements or amplitude variations of certain physical or technical quantities.

Various processes for recognizing structures (patterns) in n-dimensional spaces are known. They include, for example, local search processes for density fluctuations, the so-called maximum entropy process and the so-called maximum likelihood process. However, these known processes require assumptions or prior information to be able to identify structures or patterns. Another deficiency of known methods is that expansion to more than two dimensions is very computer-intensive, that nonuniform measured quantities and many different correlations cannot be processed, and that the sensitivity in irregular patterns with strong uncorrelated disruptions is low. Furthermore, the publication of H. Atmanspacher et al. (PHYSICAL REVIEW A, vol. 40, no. 7, October 1989, USA, pages 3954-3963 "Determination of F(alpha) for a Limited Random Point Set (Galaxy Distribution)") discloses a process in which, by determining the F spectrum in a predominantly uncorrelated set of points, possibly present correlated subsets can be identified.

Another process is known from the publication of H. Ebeling et al. (PHYSICAL REVIEW E, vol. 47, no. 1, January 1993, USA, pages 704-710 "Detecting Structure in Two Dimensions Combining Voronoi Tessellation and Percolation"). In this process, the original data point field is divided into individual cells and the cell distribution is compared to the one which would have been expected in a statistical Poisson distribution.

A simplified and more reliable approach to pattern recognition in n-dimensional space is the space filter process described in DE-OS-43 17 746. Here, the system state is represented by a point distribution in the state space (n dimensions). The change of point density (gradient) around a studied point is described by isotropic scaling factor a, which is a measure for the surrounding number of points depending on the distance from the studied point. According to the known process, the difference of the frequency distribution of all a-values of the studied points and the frequency distribution of the a values of a reference state is used to recognize local density fluctuations.

However, this known space filter process has the following defects. Using the process, structures can only be detected in the state space without the possibility of classifying its orientation. Thus, comparison with predetermined searched structures and, thus, location or signalling of certain states in state space are not possible either. This process is therefore limited to applications especially in image processing. Moreover, structure recognition according to the known process can be inaccurate in cases in which local density fluctuations are "smeared" over spatial areas which are much larger than the environment considered in the study of one point. Measurement and recognition of these blurred edges of image structures are occasionally faulty, so that a subsequent indication of pattern occurrence can be unreliable.

Finally, conventional procedures for detecting system states, especially for recognizing faulty structures, are known in systems in which the existence of a fault is detected by a global process and is then located by local studies. This is frequently impractically time consuming. This especially applies in applications for state detection of a host of systems, for example, in mass production.

An object of the invention is to provide an improved process for detecting patterns or system states with which the defects or limitations of conventional processes are surmounted and which allows broad extension to many technical applications.

In addition to the change of point density in the vicinity of the studied points, the directional dependency of the point density change is incorporated into state detection. More comprehensive and accurate information evaluation is thus possible and technical applicability is extended to a variety of systems.

The studied systems can encompass not only image patterns, but also, for example, materials, mechanical devices, and biological systems. Image processing encompasses, in the broadest sense, the processing of feature patterns which conventionally occur in two- or more-dimensional mapping or in the time variation of signal amplitude. Detection of a system state, depending on the application, encompasses measures of actuator engineering, sensor engineering, analysis and registration or signalling. The optionally necessary actuator engineering comprises measures for generating system reactions which are representative of characteristic states. They include, for example, the excitation of mechanical vibrations in a study object or measures to form evoked potentials in the study of neurological systems. Sensor engineering comprises detection of all system features with reference to n parameters of interest and the representation of features in n-dimensional space. This representation comprises, for example, storage of suitable n-tuples which are assigned to the features.

According to the present invention, for each point identified by an n-tuple in state space, one or more scaling factors are detected, each of which are assigned to one of n dimensions, and each of which originate from the projection of the point number in the vicinity of a studied point onto the n-th coordinate axis in state space. According to one preferred embodiment, the portions of the projected point number, with reference to the coordinate intervals, which lie above or below adjacent to the n-th coordinate of the study point are differentiated.

Embodiments of the invention are explained in the following with reference to the attached figures.

FIGS. 1(a)-1(d) show examples to illustrate a homogenous texture (left) and statistical texture (right) with the corresponding distribution functions of scaling factor a.sub.y,

FIGS. 2(a)-2(d) show texture examples as shown in FIG. 1 in which however a target pattern occurs in the respective field center,

FIGS. 3(a)-3(b) show the curves of the expected value and standard deviation of the probability densities P.sub.1 as a function of the incline of the micropatterns, as shown in FIGS. 1 and 2,

FIG. 4 is a flow chart of the process according to the present invention, according to a first embodiment,

FIGS. 5(a)-5(d) show probability densities P.sub.2 for a homogenous texture with five target patterns,

FIGS. 6(a)-6(d) show the probability densities according to FIG. 5, but with the target patterns being grouped in the center of the field,

FIGS. 7(a)-7(d) show an example of another texture, the target pattern detected according to the present invention, and probability densities P.sub.2,

FIGS. 8(a)-8(f) show an example of a real texture with a target pattern, probability densities P.sub.2 referenced to an isotropic scaling factor, and probability densities P.sub.2 referenced to a combined scaling factor, and

FIG. 9 is a flow chart of the process according to the present invention, according to a second embodiment.

First, determination of scaling factors according to the present invention, then illustrative examples of the present invention in an image processing application, are described below.

The point of departure for determining the anisotropic scaling factors is the determination of isotropic scaling factor a, known from the aforementioned space filter process. The determination of isotropic scaling factor a and anisotropic scaling factors a.sub.j,i, according to the present invention, is described below using the example of a pixel image G (x,y) of size N*M. A gray-scale value g (x,y) (g from 0 to 255) is assigned to each pixel. Thus, each pixel comprises one piece of local and gray-scale information which can be summarized in one three-dimensional vector p.sub.i =(x.sub.i, y.sub.i, g.sub.i) Here, gray-scale value g.sub.i is normalized if necessary to obtain an amount comparable to the x and y coordinates.

To determine the scaling factors, two cubes of different size (d.sub.1.sup.3,d.sub.2.sup.3, d.sub.1 <d.sub.2,d=d.sub.2 -d.sub.1) are arranged concentrically around each point (p.sub.i). Due to the difference of the two cubes, a certain space is placed around each point. In this space, the ambient points which belong to examined point (p.sub.i) are counted. The total number of ambient points which fall in this space is called the total mass M.sub.i.

Quantity d=d.sub.2 -d.sub.1 is the width of the coordinate interval placed concentrically around the examined point. The sizes and locations of d.sub.1 and d.sub.2 are suitably chosen, depending on the specific application. This can be done, for example, by a function which represents the relationship between the point number in the vicinity of (p.sub.i) and the dimensions of the vicinity being determined for each point (p.sub.i). As suitable parameters d.sub.1 and d.sub.2, then, ambient dimensions (interval limits) are selected for which the scaling factors (determined as follows) yield exponents of distance-power functions which approximate these distance functions as closely as possible. But alternatively, it is also possible to suitably select the location and width of the examined vicinity interval depending on the case, for example, with consideration of computer processing of the examined points made as simple as possible or the like. It is also possible for the vicinity interval to be chosen separately for each coordinate. This will be especially necessary when the n-dimensional space for describing a system state has not only space coordinates, but also other system parameters (for example, gray-scale values, oscillation amplitudes, or the like) as additional coordinates.

To determine isotropic scaling factor a.sub.i the logarithmic derivation of the total mass M.sub.i is computed (compare equations (1) and (2)). ##EQU1## .theta. is the jump function (Heaviside function) and the second summand in equation (2) labels the respective distance of examined point p.sub.i from any other point of the pixel image. Isotropic scaling factor a.sub.i is simply one measure of the radial gradients of the surrounding point numbers.

To detect the directional dependency of the radial gradient, the determination of anisotropic scaling factors is now introduced in accordance with the present invention. Here, in turn, the surrounding points which fall in the space between the aforementioned cubes are counted. Instead of total mass M.sub.i, however, projections of total mass M.sub.xi (d) and M.sub.yi (d) onto the x and y directions, respectively, are determined. According to one special embodiment, the mass projections onto one coordinate axis at a time are additionally divided into parts which fall on the positive and negative side of examined point p.sub.i. Thus, in following equations (3) through (10) M.sub.xi (d) and M.sub.yi (d) denote the projections of the total mass onto the x and y directions. M.sup.+.sub.xi and M.sup.-.sub.xi (or M.sup.+.sub.yi and M.sup.-.sub.yi) denote the mass projections onto the positive and negative side of the x and y directions relative to point (p.sub.i). ##EQU2##

In equations (5) through (10) it is established by the second Heaviside factor that only points within the outer cube are considered. The signum function establishes the sign of the anisotropic scaling factor according to the mass gradient in the respective direction.

The aforementioned equations relate, for example, to the aforementioned pixel image. These considerations can be expanded in the following manner to any point distributions. The determination of anisotropic scaling factors is not fixed onto the x and y direction. Depending on the specific application, another suitable coordinate system can be chosen. It is even possible to select, for each point, a local coordinate system which can be aligned differently from point to point. Thus, for example, in the detection of images of objects with essentially round edges, the local coordinate system for each point may be aligned in a certain way with reference to a tangent of the object edge. For example, one axis of a rectangular coordinate system can be selected to be essentially parallel to the tangent. In these image detections it is advantageously possible, based on the ascertained distribution of scaling factors (see below), to distinguish sharp and diffuse edges from one another. Furthermore, the introduction of third anisotropic scaling factor a.sub.g,i is possible. This third scaling factor a.sub.g,i can be determined analogously to a.sub.x,i and a.sub.y,i with reference to the gray scale (as the third coordinate). Finally, complex scaling factors can also be formed from a host of scaling factors which each relate to individual coordinates. One example of this combined scaling factor is described with reference to FIGS. 8(e) and 8(f).

For each point of the studied system, the indicated approach yields a set of anisotropic scaling factors. Each set can comprise a maximum of n anisotropic scaling factors if n is the number of parameters for describing the system. How many and which of the anisotropic scaling factors are, in fact, determined, depends on the specific application. In addition to the anisotropic scaling factors, the above described isotropic scaling factor or a combined scaling factor (compare FIG. 9) can be assigned to each point.

In the continuing process for detection of the state of a system the set of all examined scaling factors is evaluated. Frequency distributions or probability densities of the scaling factors are detected. Thus, for example, probability density P.sub.1 for the occurrence of certain values of scaling factors can be represented using equation (11).

where

The frequency distribution or probability density is referenced each time to the totality of examined points of the system or a subset of this totality. The system state is then detected after comparison of the frequency distribution(s) with reference distributions by registering and/or signalling predetermined deviations. In doing so, the reference distributions can be referenced to a reference system or to frequency distributions of the examined system which each relate to another subset of the overall point set. Which measures for evaluation (i.e., comparison, registration and/or signalling) are taken depends on the specific applications. In the following, applications of the process according to the present invention in image processing are described as examples.

According to a first embodiment, the process is used to detect, in an image formed by a host of identical micropatterns, the orientation of the micropatterns. The totality of micropatterns forms a texture. In a homogenous texture, all micropatterns are oriented in the same manner. In the case of a statistical texture orientation, differences occur between the individual micropatterns. One system state (especially a space or time image) is determined by a predetermined homogenous or statistically arranged texture. Changes of the system state can be registered and, if necessary, signalled (or displayed) by the determination of the deviations from the predetermined texture and their location.

This sample application is described with reference to FIGS. 1-8. But the invention is not limited to the micropatterns shown.

FIGS. 1(a) and 1(b) show examples of a homogenous texture and FIGS. 1(c) and 1(d) show examples of a statistical texture. Each overall image of size N*N (N=510) contains m micropatterns (m=225) which are each represented by a n*n matrix (n=17). These micropatterns are arranged lattice-like with a center-to-center distance of 2 n. In each micropattern is a line segment. The incline of the line segment is 22.5.degree. to the x-axis. In the statistical case, the dispersion is .+-.10.degree..

For each of the N*N points the anisotropic scaling factors are determined. In doing so, dimension d.sub.2 of the larger unit (aforementioned "cube") is chosen to be preferably smaller than distance 2 n between the micropatterns in order to detect only local properties with the anisotropic scaling indices. In the calculations for the examples, d.sub.2 =19 was chosen. The black pixels within a micropattern which form the line segments are counted in determining the mass projections. In the sample case of line segments, the micropatterns are point-symmetrical so that the frequency distributions of the anisotropic scaling factors a.sub.x and a.sub.y are symmetrical to zero. In any case, the orientation of the line segments is detected by the absolute values of a.sub.x and a.sub.y which are shown in FIGS. 1(b) and 1(d).

FIGS. 1(b) and 1(d) show that scaling factor a.sub.y in the homogenous case has a relatively narrow distribution, and in the statistical case a relatively wide distribution. In addition, it can be recognized that for a subrange (cross-hatched portions of FIGS. 1(b) and 1(d)), the frequency distribution of the scaling factor in the homogenous case remains essentially the same, but changes in the statistical case.

FIGS. 2(a)-2(d) are similar to FIGS. 1(a)-1(d) but with the difference that a micropattern with an altered orientation (angle of incline 45.degree.) is shown. It can be recognized that a deviation of the scaling factor distribution is formed by the deviating micropattern. In both the homogenous and in the statistical texture the frequency distributions have double peaks. In the statistical case, however, the width of the two peaks are increased.

It was ascertained that the probability density P.sub.1 of the anisotropic scaling factors determined according to the present invention has the properties shown in FIGS. 3(a) and 3(b). Computations have shown that the average and the standard deviation of the probability density are dependent on the angle of incline of the line segments relative to the x-axis. For a homogenous texture, FIGS. 3(a) and 3(b) show the average value and standard deviation, respectively, as a function of the angle of incline .theta.. The solid and broken curves are each related to the properties of a.sub.x and a.sub.y. In contrast to the monotonic behavior of the average value, the standard deviation has extreme values at angles of incline of roughly 60.degree. and 30.degree.. At this angle of incline, the projection of the line segment onto the x direction falls entirely within inner dimension d.sub.1 with reference to a point in the middle of the segment. This is a maximum gradient of the total masses between the inner and outer "cube". When the angle of incline rises, the mass projection for pixels is at the end of the line segment within dimension d.sub.1.

If the texture is superimposed by noise, in this way the average value is not decisively changed, but the standard deviation is increased with increasing dispersion .increment..theta. in the angles of incline of the micropatterns.

Proceeding from the findings explained with reference to FIGS. 1 through 3, in the following a process according to the present invention for detecting and locating texture gradients is given. This process is explained further with reference to the example of the line segments. Since for this the average value and the standard deviation for scaling factors a.sub.x and a.sub.y are point symmetrical with reference to an angle of incline of 45.degree., in the following only one of scaling factors a.sub.x or a.sub.y is examined, depending on whether the incline is less than or greater than 45.degree.. For the sake of simplification, therefore, the subscript x or y is omitted if it is not necessary for differentiation. The approach can be extended to any texture in the process of space or time images.

A studied system has a texture which has either homogenous or statistically oriented line segments. Different system states have different textures, which differ with reference to the angles of incline. A target is a structure (or a pattern area) in which, relative to a comparison texture, a change of the angle of incline has occurred. The detection process starts with the assumption that each target forms a significant deviation from the probability density P.sub.1 of the remaining texture. In this connection, the term "typical" means that the respective probability density is representative for most parts of the system. These parts are also called "background texture".

The approach according to the present invention for detecting and locating texture gradients or targets is described with reference to the general overview in FIG. 4, and the illustration of details in FIGS. 5(a)-5(d) through 8(a)-8(f).

First of all, after measuring the image which describes one system state, the above explained mass projections are counted (100) and the anisotropic scaling factors computed therefrom (110). Then windows of size k*k pixels are defined and a host of these windows are placed with a predefined interval periodically on the image (120). For the sample values given with reference to FIGS. 1 and 2, the window interval is 34 pixels. The host of windows forms a "sliding window". Quantity k of the window is chosen depending on the properties of the texture such that, in the texture, the statistical fluctuations of the average value of the scaling factors as a result of the finiteness of the examined sample is much less than the standard deviation. Under the conditions given as the example, k=170. Then, for each window, probability densities P.sub.1 of scaling factors a.sub.x and a.sub.y are computed (130). For all probability densities P.sub.1 of each window, the average value (or expected value) and the standard deviation are determined (140). Then probability densities P.sub.2 are determined using equations (12) and (13) for these latter values (150).

Here <.vertline.a.vertline.>.sub.i (d.sub.1, d.sub.2) is the average value of P.sub.1 for window i, and .sigma..sub..vertline.a.vertline.i (d.sub.1, d.sub.2) is the corresponding standard deviation. If, as indicated above, quantity k is chosen in a suitable manner, the probability densities P.sub.1 for the different windows is the same. Therefore, the average values and standard deviations of the distributions of P.sub.1 are each roughly equal to the individual values given in equations (14) and (15).

At a given k-value, probability densities P.sub.2 each form an individual symmetrical peak at values <.vertline.a.vertline.>.sub.c and .delta..sub..vertline.a.vertline.c.

Based on the above explained two-stage statistics, both homogenous and statistical textures without a target are described in the same way by probability densities with one peak each (corresponding to the determination of P.sub.2 (160)). If one target appears, diverging distributions are found (170). The deviation depends on window size k and the micropattern density. The window size determines the frequency ratios of the windows which contain a target to the windows with a clean background. The interval of the peaks of the distributions of P.sub.2 from the typical background value decreases as the window size increases. If the windows are too large, all windows contain at least one target so that the background peak disappears. FIGS. 5(c), 5(d), 6(c), and 6(d) show probability densities P.sub.2 (<.vertline.ay.vertline.>) and P.sub.2 (.delta..vertline.a.sub.y .vertline.) for a homogenous texture with five targets. Here, the background texture and the targets have angles of incline of 22.5 and 45.degree. respectively.

In another step of the process, the targets are located. The average value and the standard deviations according to the main peaks in FIGS. 5(c), 5(d), 6(c), and 6(d) are used to define the a-region of original distribution P.sub.1 (a) which belongs to the background pixels. This a-region can be formed, for example, by a strip of c-fold width of the standard deviation according to equation (15) around the average value according to equation (14). Constant c can be 3, for example. All pixels with a value within the strip are recognized as belonging to the background, while pixels with a values outside of the strip form the targets (180). Results of this filter process are shown in FIGS. 5(b) and 6(b). We find that both the average value and the standard deviation according to equations (15) and (16) are suitable as the criterion for detecting the target (and texture gradients or structures). In addition, FIGS. 6(a)-6(d) show that when different targets are grouped, detection is facilitated.

Alternatively, it is possible to define the filter region for target location, not with reference to the aforementioned average value, but with reference to a suitably chosen reference scaling factor a.sup.*.sub.ij. Thus, for example, the filter range can be placed around a certain extreme value of P.sub.1 distributions.

Finally, the coordinates of the pixels for which a target has been recognized are registered and processed depending on the application. This processing can, for example, encompass display of the detected target, signalling, initiation of a system reaction or determination of target orientation (190).

Orientation determination, however, presupposes that the relationship between the average values and standard deviations of the a-values of the angles of incline is known. This relationship differs for different micropatterns which have a form other than the line segments shown above by way of example.

FIGS. 7(a)-7(d) show the application of the process according to the present invention in a micropattern with a more complex structure. According to FIG. 7(a), the background texture is composed of a plurality of L's. The target micropatterns are reflected accordingly. The frequency distributions of the isotropic scaling factors are identical for both types of micropatterns. But the frequency distribution of the a.sub.x values (mass projections) can cancel the "degeneration" of the micropattern, enabling differentiation between the background and target micropatterns. In this case, it is enough to execute the process simply using scaling factor a.sub.x. According to FIGS. 7(c) and 7(d), probability densities P.sub.2 deviate from the individual peak distributions, which indicates that there are target micropatterns in the image. Thus, target detection can be done relatively easily. Differentiation (or location) is, however, more difficult than in the aforementioned example of line segments. If the aforementioned strip filtration is done, for example, with c=2, the horizontal parts of the target and background micropatterns are detected. Alternatively, only all pixels for which scaling factor a.sub.x is above the width of the filter strip are selected. In the latter case, at least parts of the target micropatterns can be filtered out (see FIG. 7(b)).

In the following, the approach according to the present invention is explained using the example of the textures of a real object, with reference to FIGS. 8(a)-8(f).

Images of real objects show intensity variations (pixel gray-scale values). These intensity variations form micropatterns which in turn represent textures in their entirety. The local features of the micropatterns are characterized by the frequency distributions of the scaling factors (isotropic or anisotropic).

The test image as shown in FIG. 8(a) shows a texture which is formed by micropatterns which consist of white points. The white points all have almost the same peak gray-scale values and gray-scale value profiles. The points are periodically arranged in a lattice. A texture defect is formed at a position where there is no lattice point. This texture defect is detected and located by applying the approach according to the present invention by using isotropic scaling factor a or anisotropic scaling factors a.sub.x and a.sub.y.

First, the frequency distribution of isotropic scaling factors a for a sample of windows (k=60) which are arranged with an interval of 30 pixels on the lattice (570*570 pixels) is computed (d.sub.1 =21, d.sub.2 =61). FIGS. 8(c) and 8(d) show the corresponding average values and standard deviations of probability densities P.sub.2. Both probability densities deviate from the individual peak distributions with which the existence of a defect in the texture is displayed.

For certain windows, the a value has an especially low or high value. These windows contain the texture defect. The task of location of the texture defects is executed by selecting all strips according to the aforementioned filtration, here the value c=6 being used (see FIG. 8(b)).

The same detection and location process is executed for the test image using quantity a.sub.xy =.sqroot.a.sub.x.sup.2 +a.sub.y.sup.2 (see FIGS. 8(e) and 8(f)). Probability densities P.sub.2 of the average values and the standard distributions of the windows show the same behavior as in the isotropic case, however, the windows with the texture defects exhibit a stronger deviation of the sizes of the average values and standard deviations from the peak values (see FIGS. 8(e) and 8(f)). The texture defect can thus be located in turn with the filtration process, here a value of c=9 being used.

According to a second embodiment, the process according to the present invention is used to detect, in an image which is formed by a certain texture (background texture), the occurrence of target patterns which differ from the background texture. The corresponding process steps are shown in FIG. 9.

In the second embodiment, in contrast to the first, the host of frequency distributions (or probability densities) P.sub.1 is not placed in a relation among one another. However, but one or more distributions P.sub.1 are compared to a corresponding frequency distribution of a reference system which has only the background texture. In this example, preferably only one window is formed which comprises the entire point distribution. This comparison is formed for example by finding the difference between each frequency distribution P.sub.1 and the reference distribution. If as a result of finding the difference, a threshold value is exceeded, it is recognized that a target pattern exists in the studied texture. In another process step, this target pattern detection continues to be processed by registration, signalling and/or display. A target can be located via detection of the windows in which the threshold value is exceeded.

The process according to the present invention can finally comprise steps in which the parameters of the detected target patterns are registered, signalled and/or displayed.