A Model for Perception of Structural Image Feature

1. INTRODUCTION

Perception process of images by computer is composed of extracting some features from im­ ages, describing them, and making the corre­ spondence between objects and description. The process of correspondence needs much knowledge and takes much time[l]. The animal has an ability for efficient image perception which contains the fast algorithm to observe it ini­ tially and get the structure feature. It is obtained without knowledge and becomes the cue

for understanding.

This paper proposes a model of perception along this fact and a learning schema to get the structure feature. The structure feature is a positional relation of local features which is essential to recognize objects. At first, ne­ cessary conditions for these features are dis­ cussed. Then, the problem of constructing the structure feature is treated. This method obtains the maximal matching of subimages which satisfy positional constraint. And finally, experiments for images of human faces show the

efficiency of this schema.

2. FEATURE EXTRACTION

When an image is given, we can extract various features, such as edges, regions, and textures. If we have a model of objects, we do not have to get all these features. We need only the strong enough features which are appropriate as keys for recognition of images. But, in the learning schema, all features should be treated equally without such a knowledge. The struc­ ture feature is constructed by the features that satisfy the following conditions.

• (a~ They should not depend on the cordinate system and their position should not be effec­ ted by the operations that lose resolution.
• (b.) They should be clustered into some catego­ ries and the relations between them should be considered more important than the absolute value.
• tc) They should include spatial informations. We divide an image into subimages, which are sets of adjacent pixels, and attach a feature vector (X1,x2,---XN) to each subimage. Each component of this vector is the values on the feature operators.

These feature vectors are distributed spatially and if some relation between them is intrinsic for the image, we regard such relation as the structure feature[2].

3. SPATIAL MATCHING

3.1. Selection of Key Features and Labeling

Within all components of a feature vector, some components may be meaningless as the structure feature, and we must select key features. They are selected on a basis of statistical distri­ bution of each feature of images which belong to the same kind.

(Selection Algorithm)

~: Select one component Xi whose histo­ grams show resemblance for all input images.

This rescmbl ancc is measured by the configura­ tion of cores of clusters[3). Step 2: If there are different numbers of clus­ ters for Xi,somc ncar clusters are merged. Step 3: r:or each cluster of Xi, select the component Xj the distributions of which re­ semble each other for input images, and execute Step 2. This step is repeated until there doe s not exist the component that show the resem­ blance, and the sequence of components (Xi,X.,­ --) is obtained. Then, each sub image is la-J hcled by ann-tuple (Yi,Yj,---) where each componC'nt Yk is the name of cluster of cor­ responding feature Xk to which the' suhimage belongs.

During these steps, the feature which shows peculiar property in a particular image is not selected, for the hi stngrams of such features do not resemble those of other i mages, and it is considered as a meaningl ess feature for the structure feature which is common in images.

3.2 Positional Constraint

llcre, we define the notion of "match" and "positional constraint".

If two suhlmagcs Sl'=ll, s2El2,havc the same labels, we say SJ matches S2 and it is denoted by S1~s-,.

Ir thcr~ arc such subimagcs s 1 , s}ETJ, S2, s2'E': I2 that satisfy the following conditions, we say they satisfy pos ·i tiona! constraint and it is denoted hy (Sl,Si)~(S2,Si). (In the following condition, I(S),J(S) denote the row and the coluum .index of S, respectively. ) ca.) s1.::s2 , sj~sz.

(b.) If I(Sl)<J(Sj), I(SJ)=I(S]), I(S1)>I(S}), then l(S2)<I(S2), I(S2)=I(Sz), I( S 2 )>I(S2) hold, respectively. (c.) if J(SJ)<.f(Si), J(SJ)=J(SJ), J(Sl)>J(S{), then J(S2)<.l(Sz), .J(s2)=.J(S2), .J(S2)>.J(S2) hold, respectively.

Wh<'n two images T1, 1-, arC' given, a set of m;ltcht·d suhimagcs or l1 and 1-, is a set M ~s 1 , s 2 ~ where ~c s 1 ,s2 )H1 ( sjti 1 , s 2 ·r 7 , s 1 ~s 2 \ and Y(Sl, s 2 ),(SJ,~:;) tM [{s 1,S))!::(S2,s 2 )j . A set of matched s uhimagcs C'Xprcsses a common structure of images. We regard the maximal set of matched subimages as the s tructure feature. It takes much time to obtain the maximal set, so we introthiCl' a simple m;1tching ;il gorithm by 1vhich a good set can he obtain<'d, though not a maximal one.

3. 3 Simp le ~latching Algorithm

Let an image he a set of sub images { Si j \1 ~i ~1--1, lc;j~}, and let each suhimagc Si j have' a Jab('] Lij· f-or each row i, the sequence of Jahel s Lil· Li2· ... LiN is denot ed hy L<i >. When two sequences L<i> and L<j> arc given, the distance between them is defined as the rec i proc;d of the length of the longest common s ub sequence (LCS)[4], and denoted as O(i ,j). The matching algorithm is as follows:

Step 1: Let P be a set of all pairs or sequences CL1<i>, L2< j >) where L1, '-2 are from 11 , 1? , respectively.

~: Select a pair (L 1 <i1>, J. 2 <j 1>) whose distance O(i,j) is the smallest in 1' . Step 3: f-rom 1', r emove the pairs (I. 1<i>,J.?<i>l that do not satisfy i>i 1 , j > i 1 or· i < i 1 , j <j 1. Step 4: If l' is empty or there i s not a pair CL1<i>,L2<j>) which sati sfies ll(i ,j) <O , go to step 5. El se , go to s tep 2.

Step 5: Change the lah~ls of the suhimages to "don't care symbol" that arc not included in the selected rows , or that arc not included in the LCS in step 2.

StE'p 6: Repeat from s tep 1 to step S for any pair of column vectors.

In this cast· the "don't care symbol" is not included in u:s.

The suhimages which arc l eft unattached "don't care symbol" construct a set of matched sub­ images.

4. EXPFR1~1ENT

We apply our algorithm to images of human face. !Iuman faces have some suhohjects such a s h;1i r, eyes, brows, and so on. llowcver, we try to match the images without the knowledge about them. Input images arc composed of J2Rxl2R pixels and each pixel ha s 9 hit integer v;llue as intensity. (Fig. 1)

These images are divided into subimages whose sizes are 4x4, and each subimages are attached a feature vector (X ,x 2 ,x 3 ) where x 1 ,x 2,x 3 cor­ respond to mean intdns1ty, busyness and edge value, rcspcctively[5] [6). Each component is ca t egorized and consequently each suhimage has a lahcl composed of 3-tuple of cluster names. In Fig.2, concerning the first two images, the boundaries between suhimagcs attached dif­ ferent label s arc dis layed .

lly comparing thl' histograms of these features, clusters of XJ are merged, and new lahels are attached to each suhimagc. (Fig. 3)

u:s of sequences of these labe ls is calculated hy the simple matchin)! algorithm. For example, let Lrt.i> ,L2<j) he given as following se­ quenl·cs. (They arc sequences of labels which arc indexed hy arrows in Fig.3, and each letter expresses a labe l attatchcd to a suhimage.)

haadhbddhhbhhdhbdbhddddhhbhhaaaa

haaaaillJbhddddhhhdddhbbcccdbddade

u:s of these sequences is calculated in Step 2 and following result is obtained . (Labels that ar l' not included in LCS arc changed into don't c;1 rt' symho 1 " * ".) The distance between them i s l/16.

haadhb**h****dbb*b*dd**bh***a***

The result of matching first and second original images are shown in Fig. 4. In this image, only the regions in which more than one-third of subimages are left unattached "don't care symbol" are displayed. It takes about 3 minutes to match two images.

To match many images, this algorithm is applied one hy one. The result of matching four images of f'ig.l is shown in Fig. 5. Some principal sub­ objects are remained because the relative positions of them are common for all images and each of them has a same local feature.

5. CONCLUSION

We have presented an algorithm to get a struc­ ture feature of images. This feature corre­ spond to the structure we get from images at a glance, and it is used as the cue to under­ stand them. We used the relation between sub­ images and from statistical property, we got the structJre feature. TI1e advantage of this method is that we can keep from noises, because noises which happen irregularly are removed while matching process. The results of experiments show the maximal set of suhimages has enough information as the structure fea­ ture.

RHERENCES

• [ 1] Winston, P. H. "The Psychology of Computer Vision." McGraw-Hill, 1975.
• Fnomoto, H. et al. "Statistical Approach for Construction and Estimation of Syntactic Pattern Recognition Mechanism," in Proc, I.JCPR-
• Kyoto, Japan, November, 1978, pp. 359-363.
• Fukada,Y. "Spatial Clustering Procedures for Region Analysis." In Proc. IJCPR-78. Kyoto, Japan, November, 1978, pp.329-331.
• [4) Hirschberg, D. "Algorithm for the Longest Common Subsequence Problem." JACM 24:4 (1977) pp.664-675.
• [5) Ohlander, R. B. "Analysis of Natural
• Scenes." PhD thesis, Computer Science Dept. Carnegie Mellon University, April, 1975.
• Rosenfeld, A. "digital Image Processing." Academic Press, 1976.