AU701613B2

AU701613B2 - Method and system for conjugate binary image analysis and processing

Info

Publication number: AU701613B2
Application number: AU42139/96A
Authority: AU
Inventors: Zhijie Zheng
Original assignee: Individual
Current assignee: Individual
Priority date: 1995-01-24
Filing date: 1996-01-23
Publication date: 1999-02-04
Anticipated expiration: 2016-01-23
Also published as: AU4213996A

Description

I

This invention relates generally to computer programming apparatus and to methods and systems of digital image generation and analysis and relates in particular to a method and system of feature recognition/detection using conjugate transformation on a rectangular grid for binary code image analysis and processing, pattern recognition, computer vision, image data bases and othe visual information management areas.

The invention according to one aspect resides in a method of feature recognition/detection using conjugate transformation on a rectangular grid for analysing binary images, which comprises first calculating a set of o intermediate invariant parameters, then using the said parameters to classify S°and group all feature patterns together according to parameter values.

More particularly, the intermediate invariant parameters are selected from conjugation, convexity index and branch.

Preferably, the method according to the invention comprises I" generating from a kernel form of a 3 x 3 window on nine Boolean point •variables for transformation of a binary image according to 512 patterns in the kernel form as a pattern set into a feature classification, processing an S0. uncertain point of a 3 x 3 window by assigning an opposite value of a central point to the uncertain point as initial value for 0 -2balanced processing border points and more preferably the method includes placing all possible feature classes into a pair of pseudo-triangular structures for both foreground and background features respectively, selecting feature classes from the structures, projecting the selected feature classes and then generating a pair of feature binary images for 0 and 1 features respectively.

Preferably, the method includes partitioning a pattern set into two conjugate sets of feature classes, each feature class set containing twelve classes and wherein one feature class in one feature class set has a unique conjugate class in another feature class set.

Preferably, the method includes detecting ten intrinsic geometric features of isolated, inner, network, 15 block edge and intersection structures for 0 and 1 feature images respectively.

The method as above-described comprises three-stage image processing by: 1) calculating three intermediate parameters, 20 2) selecting a pair of feature class sets and, 3> detecting and projecting the selected feature images.

The method also preferably includes the step of distributing two sets of feature classes into two pseudotriangles which are extensions of a rectangular grid and wherein each feature class, which is a meta-invariant cluster corresponds to a specific set of irreducible rotational invariant classes from which one pattern of an *7 irreducible class is selected as a representative of at most four other patterns in the same class and more particularly, the patterns comprise twenty four meta-geometric invariant clusters and ten intrinsically-geometric invariant clusters.

Preferably, the method includes the step of detecting and projecting selected features of geometric clusters.

More preferably, the method includes for 1 and 0 features respectively, the step of distinguishing main intrinsically geometric invariant clusters selected from: a) isolated clusters, b) inner clusters, c) network clusters, d) block-edge clusters, e) interaction clusters and any functional combination thereof.

Preferably, the method includes for 1 and 0 features respectively, the step of distinguishing main intrinsically geometric invariant clusters selected from twenty four metageometric invariant clusters and any functional combination thereof.

Some non-limiting examples of preferred embodiments of the invention will now be described with reference to the accompanying drawings in which: Figure 1 is a block diagram of the feature classifier system of the present invention.

Figure 2 is a computer software flow diagram of the classification block.

Figure 3 is a computer software flow diagram of -4feature selection and projection.

Figure 4 is a computer software flow diagram of feature selection and projection.

Figure 5 is an example of feature classification procedure.

Figure 6 shows examples of selection and projection procedure.

Figure 7 is a schedule of 24 symbolic clusters.

Figure 8 is a chart of spatial distribution of meta invariant clusters.

Figure 9 is a schedule of ten intrinsically geometr invariant clusters.

Figure 10 is a chart of visual partition of ten intrinsically geometric invariant clusters.

15 Appendix A is mathematical equations of two interme late parameters.

ic d- Appendix B is corresponding tables of 24 symbolised clusters comprised of irreducible rotational invariant classes and their representatives.

Referring to Figure 1 of the drawings, the example of the method and system of the invention comprises three main parts namely, classification, visual distribution and selection projection. The classification is described in detail in Figure 2. A binary image X is read as the input. The total number of points is denoted by N. For the I -th point x (1 5 I N) in X, as for a current point as the centre, there is a 3x3 neighbourhood. K(x) which denotes the nearest neighbouring relationship relevant to the point x. When x is a border point of X, there are some neighbouring points without 1 0 a defined value. For each undefined point x xj is assigned into an opposite value of x (either x ,x 0 or x ,x When all neighbours {x }7o have fixed values in a 3x3 pattern S(x) of x is generated. In addition to the parameter xx(conjugation), only two immediate parameters, v(convexity index) and q(branch number), need to be calculated from the pattern S(x) by the detail equations shown in 1 5 ,Appendix A. Using the three intermediate parameters a feature point G(x) is calculated and the result is put in the I-th position of All points in X are processed by this procedure and a feature image G(X) is produced. This completes the classification.

*Referring to Figure 3 of the drawings, there is shown the visual distribution step 20 of the method and part of the system of this example of the invention. In general, 512 patterns of 3 x 3 windows for binary images are partitioned into 24 meta-clusters using the three parameters. The feature points can be organised into two pseudotriangles dependent upon specific invariant values, where x e v q It is convenient for a flexible selection to use a geometric form as a visual interface and symbolise each cluster by letters or other symbols managing as two pseudo- triangles. Each pseudo-triangle contains 12 metaclusters related to either foreground or background. Two symbolic sets of meta-clusters and their corresponding relationships among 140 irreducible rotational invariant classes for the 512 patterns are provided in detail in Appendix B.

-6- Referring to Figure 4 of the drawings, there is shown the selection and projection step of the method and part of the system of this example of the invention. Feature selection collects (a,fl as a selected pair of meta-cluster sets for identifying foreground and background features. Before projection, all points of Ga(X) are assigned 0in value and all points of G 6(X) are assigned 1 in value. For each G(X) of feature image, only if x 0 and G(x) et, then G 0; and if x land G(x) ea then Ga(x)= 1. This operation projects f) selection from the input image X into a pair of two feature binary images Ga(X) and G The pair of binary images is the required output result of the invention.

10 Referring to Figure 5 of the drawings, one example of the classification on a given 6 x 6 binary image is presented in which three specific points are indicated to illustrate the detail differences between K(x) and In addition, three intermediate parameters and their corresponding letters are evaluated and assigned respectively.

1 5 Referring to Figure 6 of the drawings, examples of selection and projection are presented. Using the same binary image of Figure 5, four different selections are made and their projection results are illustrated respectively.

Referring to Figure 7 of the drawings, there is illustrated the corresponding relationship between 24 clusters of and their symbolised letters L} and {a,b I Referring to Figure 8 of the drawings, the spatial distribution of two pseudotriangles are illustrated. Different symbolised scheme may change the letters, however the detail corresponding relationship shown in Appendix B has to be invariant.

-7- Referring to Figure 9 of the drawings, by repartitioning 24 meta-clusters in two pseudo-triangles, ten intrinsically geometric invariant clusters can be formulated.

Considering different operations of edge detection and description, the most important operations in practical image analysis applications, this partition may provide the most useful configuration of the invention. In Figure 10, visual partition of ten intrinsically geometric invariant clusters are illustrated with balanced spatial property.

The invention is basically concerned with two sets of image features in which a 3 x 3 window of nine points forming a rectangular grid of nine values is selected on the basis that when the kernel central point x has a value of I a black image point results, 10 and when x has the value 0, a white image point results. The optimal structure of the conjugate classification of the kernel form of the rectangular grid is a specific configuration of the conjugate classification.

The invention enables the main intrinsically geometric invariant clusters of: Network clusters; 1 5 0 Block edge cluster and S Intersection clusters Sto be systematically and efficiently distinguished for 1 and 0 features respectively.

A. o

S.

Appendix A. (Mathematical Equations of Two Intermediate Parameters) In this invention, only two parameters, v(convexity index) and q (branch number), need to be calculated from a point x and its 3 x 3 pattern S(x).

X 0 X1 X20 1X 0

X

1

X

1 I X 2 Let S(x) =x x x X and X 2X -X XjG 0 1 7; x6 x 4X 6 x 5 x 5 x 4 each X1is a 2 x 2 pattern corresponding to four specific points of Using these notations, the following equations can be used to evaluate the convexity index for the point x, V(SWx)= Zf 1 f 1 f 1 (X 0:5 1/ 3; 9 .9 0 0I1 1 1, X ,0 1 1 ,o 0 0 10 1 1 0) 1ff1 1_ 1 1, X E "I ,AX) -1, U 0 C' 1 I' 1 0' 0 0J10' 9 90, otherwise; 0, otherwise; 2 1 0 U 1, x 3 0 1 1 0 0, 0 0' 11'}1, X O0, 2 X2e41 0 1 1 0 1, 0 11 f(X 1 1 1 1 1 0. 0 01.

E O C 1 0' 10' 0J Lb(3) ,X3f 0 1 0 1 9..90, otherwise; 0, otherwise.

Another equation is required to evaluate the branch number for the point x, q qSW) Xj #X j~~mod8)).

Appendix B. (Irreducible Classes and Representatives) There are 140 irreducible rotational invariant classes among 512 patterns in relation to the 3x3 kernel form Each irreducible rotational invariant class contains at most four patterns. For convention, only one pattern is selected as a representative of a rotational invariant class of patterns shown in the formula: a letter v,q) class class, a 0 1 0 For example, the representative o i i denotes an irreducible rotational invariant class of S0 0 1 01 0 0 0 0 0 011 the four patterns o o i. I o. i 0 o 0 0 1 1 1 0 0 1 0 0 0 Using the three invariants the 24 meta-clusters of the invention are symbolised in and corresponding to the following formula.

Appendix B. (Contd i) (Irreducible Classes and Representatives) A C G 0 00 0 10 0 01 0 B 0,0) II I II I~ 1

I

0 0 0 1 J L D E 0 1 1 01 0o1 0O1, 0 00 0 0 F H 0 0 0 1 0 1 1, 0 0 1 0 1O, 0 1 I I I I I 1 0, 1 1 0 1 0 00 1 010 0 1 I II;

II

K I I 0 11 Appendix B. (Contd ii) (irreducible Classes and Representatives) a 01 b 0o 0o 0 1I 00 0 2,1) 01 1 1 01, I I I 1 01 00 1 1 0 1, 1 01, 1I 121II 1 00 0 00 101 I, 102;I I2 112II 1 01 11 g 0, 1) 0 0 1I 1021 1 01 1 01 0 12 2 01 1 120 1, 1 0 1, 1 01, 10 1 1 0 1, I I120 0121 1 01 121 0 00 0 II II 1 0 1 01 1 00, I110 2 10 10 0 2 0 1, 1 01, 1 00 10 1 0 1 01, 0 0 021 00, 0 1 10 0 1 01, 0021 I110 1 00, 01 1 1 1 00, 00 1 10 1 1 01, 0 1 00 0 01, 1200 I110 1 0 0, 10 1 I I 10 0 01 0 0 10 1 00, I110 1 0 01, 0 1 00 0 1 0 1 01 j 3): 1 0 01, 1 0 1 d e 0,1) 1 1 1 00 0 0 00 1I1l 00 0 2 00, 0 100 0 00 1 01010 0 0 0 0 1 0 0 0 0 0 1 0 f 00 0 0 0 o; 0 02 00 1 0 01, 1 00 0 h o 0 0 0 01 0 01, I110 00 0 0 01, 10 0 00 0 1 00, 1201 00 0 1 0 0 0210 00 0 0 0 1, 1201 00 0 0 01 21 0 0 00 1 00, 0211 1 00 00 0 100, 1200, 0021 0021 0 00 00 1 0 00 0 00' 1 01 10 0 i k 00 1 0 0 0 1201 12 The claims defining the invention are as follows: 1. A method of feature recognition/detection using conjugate transformation on a rectangular grid for analysing binary images, which comprises first calculating a set of intermediate invariant parameters, then using the said parameters to classify and group all feature patterns together according to parameter values.

2. The method according to claim 1 wherein the intermediate invariant parameters are selected from conjugation, convexity index and branch.

3. The method according to claim 1 or 2 which comprises generating from a kernel form of a 3 x 3 window on nine Boolean point variables for transformation of a binary image according to 512 patterns in the kernel form S°as a pattern set into a feature classification, processing an uncertain point of a °3 x 3 window by assigning an opposite value of a central point to the uncertain point as initial value for balanced processing border points.

4. The method according to claim 3 which includes placing all possible feature classes into a pair of pseudo-triangular structures for both foreground and backgrond features respectively, selecting feature classes from the structures, projecting the selected feature classes and then generating a pair of feature binary images for 0 and 1 features respectively.

The method according to claim 4 which includes partitioning a pattern set into two conjugate sets of feature classes, each feature class set containing twelve classes and wherein one feature class in one feature class set has a unique conjugate class in another feature class set.

6. The method according to any preceding claim which includes detecting ten intrinsic geometric features of isolated, inner, network, block edge and intersection structures for 0 and 1 feature images respectively.

7. The method according to any preceding claim which comprises three-stage image processing by:

Claims

8. The method according to any preceding claim which includes the step of distributing two sets of feature classes into two pseudo-triangles which are extensions of a rectangular grid and wherein each feature class, which is a meta-geometric invariant cluster, corresponds to a specific set of irreducible rotational invariant classes from which one pattern of an irreducible class is selected as a representative of at most four other patterns in the same class. The method according to claim 8 wherein the patterns comprise S.twenty four meta-geometric invariant clusters. The method according to claim 8 wherein the patterns comprise ten intrinsically-geometric invariant clusters.
11. The method according to any preceing claim which includes the step of detecting and projecting selected features of geometric clusters. "o 12. The method according to any preceding claim which includes for 1 a.. and 0 features respectively, the step of distinguishing main intrinsically geometric invariant clusters selected from: Sa) isolated clusters, b) inner clusters, c) network clusters, d) block-edge clusters, e) interaction clusters, and any functional combination thereof.
13. The method according to any preceding claim which includes for 1 and 0 features respectivey, the step of distinguishing main intrinsically geometric invariant clusters selected from twenty four meta-geometric invariant clusters and any functional combination thereof. -14
14. A method of feature recognition/detection using conjugate transformation on a rectangular grid for analysing binary images substantially as hereinbefore described with reference to the accompanying drawings. A system for feature recognition/detection using conjugate transformation on a rectangular grid for analysing binary images substantially as hereinbefore described with reference to the accompanying drawings. Dated this 19th day of November, 1998 ZHIJIE ZHENG By My Patent Attorney JOHN L.DAVIES CO. *I o* a a ABSTRACT A method and system of three-stage image processing for feature recognition extraction and detection uses conjugate transformation on a rectangular grid for analysing digital binary images by four steps, namely classification, visual distribution, selection and projection and involves three intermediate calculable parameters namely conjugation, convexity index and branch to classify and group all possible feature patterns into feature classes by intermed- iate parameter values based on a kernel form of a 3 x 3 window of nine Boolean variables; a central point of the 3 x 3 window with its eight neighbouring points for transform- oo ation corresponds to one of 512 patterns in the kernel form, the 512 patterns comprise a pattern set, one pattern is o classified into one feature class then all possible feature .classes, which are meta-geometric invariant clusters, are distributed into a pair of pseudo-triangular structures for both foreground and background features as a conjugate organization; feature classes from the structures are selected and projected and a pair of feature binary images for 0 and 1 features is generated; the method includes direct detection of ten intrinsic geometric features of isolated, inner, network line, block edge and intersection structures for 0 and 1 feature images and their combinations respectively,