- Email: [email protected]

Pergamon Press 1974. Vol. ~. pp. 77-83. Printed in Great Britain

STEREOMETRIC PATTERN R E ( ' O G N I T I O N BY ARTIFICIAL T O U C H NEBOJ~A S. IVANg?EVIC Institute of Physical Medicine SRS. V. Putnika 7, 11000 Beograd. Yugoslavia tReceired 5 Nocember 1973" recised 9 April 1974) Abstract--An artificial touch perception system has been created in order to study' a method of processing

information obtainable through tactile exploration of three-dimensional forms. The results can be useful for several purposes. The first part of the work concerns the project of the tactile explorator. For this purpose we used a kind of artificial limb like a finger with a certain number of touch sensitive transducers distributed along the surface of the finger tip. The information received by touching the object with the finger, is successivel? utilized as the input of the control servosystem which moves the finger point-by-point along the object surface, in order to proceed with the exploration. It must be noticed that. from a philosophical point-ofview, the parallel approach with more fingers touching simultaneously the object in several points, ,s equal to sequential touching of these points by one moving finger. The second part describes the use of the propositional calculus in logical classification of the objects. as a method of three-dimensional pattern recognition. Elaboration of the input data obtained by tactile exploration, and computation of charactcri

Computer

Exploration

INTRODUCTION

Pattern recognition

Space

Three-dimen-

build in to interface the machine with the man and the external world'? (c) How can we use such a knoMedge for design of artificial intelligence machines'? In our attempt to facilitate the individuation and analysis of the role of touch in perceptive processes and in the handling of objects of human beings and artificial systems, we tried to formulate an artificial model of the upper limb, able to operate using information about the surrounding world which it can itself procure, The prehension of objects, depending on their threedimensional form, is the task to be carried out by manipulation control. As the aims of such a task can be very different, it is not easy to attempt the generalization of prehension and manipulation principles. Our work program included the project of developing a limb capable of exploring three-dimensional forms by touch. In the first phase, the obtained information is used as an input to the limb's control system to proceed with the automatic exploration of the considered form. In the next phase, the information stored during exploration, is elaborated and used for the desired aims. As an example, we can quote several kinds of utilization: ( a / A s an input to the limb's control system.

It is clear that visual control has a dominant, but not absolute, role in manipulation and perception of threedimensional objects by human beings. How large a part tactile sense plays, it is difficult to say, but it can not be neglected. For correct manipulation of objects, it is necessary to know their spatial characteristics, such as shape and position. Before direct contact with the object, the visual sense plays an exclusive role, and decision (depending on the principal task) is based only on optical information. At the moment of touch, both optical and tactile information start to flow, resulting in intercorrelation. From this moment, visual sense can be partly released for other tasks and tactile sense can take over to pick up information about the object. Human sense of touch consists of nerve endings located in the skin and distributed in a variable geometry. Along the hand this sense has increased activity, high density and particular significance in perception of external stimuli. In studying the problem of tactile perception, there arise many questions and some of them are: (a) How do tactile sensors of human beings work? (b) How can we learn from biological sensors to simulate them and 77

78

NEBOJ~A S. IVAN~EVI~

Start Assembly of basic propositions: L I : Tactile explorator is in contact with object L2: Object's surface is plane L3: Object has six faces L4: Three pairs of parallel planes exist LS: Distances between parallel planes are equal L6: Object is rectangular LT: Object is not a hexahedron LS: Object is not a parallelepiped L9: Object is a rectangular parallelepiped LIO:Object is a nonrectangular paralielepiped LI1 Object is a cube 9

I Use visual information I "- to establish contact J

NO r YES

NO

r Optional approximation for curved surface 1 I

=-j objects with enveloping polyhedra

I Tactile exploration (

I Input matrix

Pi, j I

Computing features of polyhedron gives mathematical model of object: -equations of planes-delimiting polyhedron, number of polyhedrons faces/planes/, -angles between planes, locations of vertices.

1

Diagram of computer program for elaboration of stereometric forms using tactile information, with particular distinguishing and classification of parallelepipeds.

to allow a better positioning during manipulation, depending on the shape of the object; (b) To obtain a classification of three-dimensional forms; (c) To improve the informative content of poor quality optical images of objects.

TACTILE EXPLORATION

The term "limb" implies a device furnished with a "finger" equipped with sensors. The sensors are of the O N - O F F kind, sensitive to small pressure and distributed along the semi-spherical surface of the finger's terminal part at the cross-points of meridians and parallels. The device is moved in space by three d.c. servomotors. By "exploring" we mean the limb's ability, once in contact with the object, to move along its contour surfaces fo.llowing certain rules, using for this purpose the

information which it is gradually able to pick-up, and having so a certain autonomy. Idealized we can imagine a small sphere, whose upper and lower half corresponds respectively to the upward and downward position of the finger tip. If such a sphere slides along object's surfaces following a certain rule, then it would be able to perform the threedimensional scanning of the object. It is necessary to emphasize that it is not of essential importance to have sequential exploration of the object, point by point. The same result can be achieved using parallel scanning, i.e. simultaneous touching of more points, with as many fingers as would be convenient and possible, and without moving or sliding the fingers along the object's surface. In this paper we wilt consider exploration by one finger only, which can be easily transferred to a multi-finger case. Let us assume the finger moves translatorily with regard to the chosen Cartesian reference system X, Y,

Stereometric pattern recognition

Z, If a certain sensor is ON, it means that the finger is in contact with the object's surface, whose tangential plane at the point of contact has a determinated orientation. In a prototype under study. 33 sensors are distributed on the finger tip, which means 66 for the whole sphere. This permits one to distinguish between plane surfaces at a 30: slope from each other. In fact, a relation is realised between families of space surfaces, intended as delineating the object, and points of the semispherical finger tip (or rather, the sensors distributed thereon). If the object is at rest within the chosen coordinate system, it is possible to measure immediately' the coordinates of the touch point. Since every sensor is associated with a family of parallel planes in the space, we can also measure the two angles (azimuth and elevation of the radius-vector of touch point in the spherical coordinate s~stem) individuating this family. All these data. transmitted to the computer, allow it to calculate the equation of tangential plane in the touch point with regard to the reference system. Once a first contact with an object has been established, the finger must be able to move along the contour of the object to obtain the data for calculation of the equations of the surfaces delineating it. This function is realized by a three-dimensional servosystem controlled by the feedback electronic equipment. When a sensor indicates that contact has occurred, appropriate voltages are sent to the servomotors to move the exploratory finger along an intersection between the tangential plane in the point of contact, and the plane parallel to the X - Y plane, with a chosen sense. Therefore, to each sensor is associated a direction of movement. The voltages are present on motors only while contact exists. If contact is lost. the sensor passes from state ON to state O F F . In order to establish a new contact, there is a programmed searching cycle in the control electronics, which makes the finger perform a small rectangular trajectory until contact is re-established. Then the finger moves in the direction imposed by the contact itself. If the cycle terminates without recontacting the object, exploration ends with the decision that the object has at least one dimension inferior to the search c~cle. Exploration can eventually continue in other planes. ELABORATION OF THREE-DIMENSIONAL FORMS If we accept, as the description of an object, the conventional, verbal definition, expressed in certain combination of sentences or characteristic propositions, then this combination can be considered as a logical model of the object. Associating to the affirmative pro-

79

position the number l. and to the negative proposition the number 0, so called truth values, we can transfer from verbal to mathematical description of the object. So. on the basis of such an approach, we can form the mathematico-logical model, which symbolises the object and can be used in computer processing of classification and recognition of spatial forms. In our method for the recognition of three-dimensional forms, we use the Propositional calculus with operations already known from Boolean algebra. Elements of this calculus are basic propositions, which can be affirmation or negation of the presence of a certain feature that an object could possess. It is not necessary to take into account all established propositions, but characteristic ones only, because complete classification is hopeless if all possible inputs are taken. However, classification carried out in phases manifests a better economy as regards the complete classificatory system. As an example, a choice tree is given consisting of several phases by means of which more precise identification of a certain geometrical form can gradually' be obtained i Fig. l 1. In the elaboration procedure, the basic assumption is the proposition, signed Li(i = 1, 2 . . . . . n), and telling us. b x its truth value 1 or 0. that some feature is present or not. Individual objects are described as assemblies of corresponding features whose presence is affirmed or negated b~ tactile exploration and computer calculation. The form of an object is described in terms of logical conjunctions between propositions. By forming an association of propositions determinating this object, we obtain the base of propositional calculus. Let the assembly of the basic propositions be: L = (LI.L

2 . . . . . . L,,).

From the elements of base L, the theoric disjunction (logical sum "'OR") of 2" members of all possible conjunctions {logical multiplication "'AND"), can be formed as follows: s(L) = L , .L_,-...'L,, + LI . ~ ' . . . - L ,

+ ... + ,L i ' L 2 " . . . ' L , .

The sign over the letter means negation (logical "NOT"). If some basic propositions are joined by logical connection, the disjunction s(L) will have some empty members, the truth values of which are 0. In such a case, the number of conjunctions is reduced according to the strength of the logical connections: the stronger they are, the smaller the number of the conjunctions. The remaining conjunctions form the reduced real dis-

NEBOJgAS. IVAN('e'¢IC"

80

Choice tree

Phoses

]Plane surfaces j

j Curve surfaces]

I p,rom'°s I t "oro"e'e0'0e'. 1

rr

j po,..0.o I

TIT

1 L"oo °oro,,e,e0,0e0s l [ Rectangular paralleleoiped ]

"7"

etc. Fig. 1. Choice tree.

junction r(L), which characterizes an individual object and gives a mathe,natical and logical model which can be represented by a string of numbers. Logical connections between propositions Li could be carried out in different ways. Here we have used the form of equality, which to a certain extent can be treated as an equation and processed numerically on the computer. Here is an example of a group of characteristic propositions used in three-dimensional object recognition. with the marked phases of classification mentioned be fore:

Combination of propositions existing in the description of the object, do not exhaust all theoretical possibilities. Besides conclusion concerning logical connections between propositions, which allows distinguishing the objects, it is also possible to find common conditions for the variants in one class of objects. Considering as an example, the logical connections between propositions described above, the characteristic real disjunction, for example a cube. using an equality form. would be:

Phase I:

resulting in a new proposition:

Phase II: Phase III:

Phase IV: Phase V:

Proposition A: "There is a contact between the object and the finger". Proposition B: "Surface is curved". Proposition C: "Surface is plane". Proposition D: "'Lateral edges are parallel". Proposition E: "Lateral edges join at one point". Proposition F: "Three pairs of parallel faces exist". Proposition G: "Distances between neighbouring vertices are equal".

etc. This group may not be definite, but it can be changed and enlarged, depending on the principal task of recognition.

r[L) = A . B ' C . D . f f S . F ' G

L: Object is a cube or L=.4.B.C.D.E.F.G.

FORMAL APPARATUS The information obtained during tactile exploration, is going to be used by computer for extracting the geometrical features, essential for the construction of the mathematical model. Because sensor density is low, the model obtained by tactile exploration is only approximate, depending on the complexity of the object's shape. Initially we have

Stereometric pattern recognition

is

8l

NO

YES Testing of basic propositions and forming their real disjunction r / L /

)

@NO I'21L, WES !

II Confronting real disjunction with theorlc one s / L / I

Propositional calculus using Boolean algebra to find logical relations between propositions

Making decisions on basis of established logical connections

Fig. 2. Flow chart. limited our experiments to simple plane surfaced objects. Input data has to be obtained by scanning the object. Any touch of the object by the sensors corresponds to one plane: the equation of this plane can be determined using analytical geometry. In this way the touched body will be represented by a polyhedron which envelops the body and is composed by the group of planes whose equations are known. Coordinates of the vertices and equations of the edges can be calculated too. Further, the equation of the support plane is the same as the equation of the polyhedron's supported surface. If we suppose that an object is touched at point P {determinated by the vector r~) by sensor N (determinated by the unit vector r.), then the equation of the tangential plane is: ( r - r i) x r,, = 0. Then, if the object is scanned by being touched at more points, we can have the assembly of all surface

equations of the enveloping polyhedron, which gi~es us the mathematical model of the object. Computer calculations give other information, such as intersections and angles between planes, existence of parallelism and perpendicularit.~, etc. ~ hich forms propositions for object identification. We can note how the principle of minimal angle of prehension can be used. Determination of the lwo parallel (or almost parallel) planes can give the decision as to which way an object should be grasped. As an illustration of the text. the flo~v chart of the computer program is given (Fig. 2}. The ansv,ers of the computer for different objects, or different position of the .'~lmeobject, are shown in Fig. 3. Because of lack of computer-on-line facilities, the data for the testing program was simulated. As it is possible to see from Fig. 3, the testing program has started with simple forms: the cube in four different positions, each recognized correctly, then rectangular and nonrectangular parallelepipeds in two different positions were recognized well too. and the tetra-

82

NEBOJgAS. IVAN~'EVIC OCTA Object is not a hexahedron

[3

CUBE 1 Object is a cube CUBE 2 Object

is o cube

TETRA Object is not a hexahedron PRAPARObject is a rectangular parallelepiped KOPAR Object

is a nonrectangular

parollelepiped

TETRA 1Object is not a hexahedron TETRA 2 Object is not a hexahedron CUBE 11Object is o cube

©

CUBE 2 2 Object is a cube

0

PRAPA 1" Object is a rectangular

parallelepiped

KO.'~R l" Ot.ject

is o nonrectangular

parallelepiped

Fig, 3. Computer answers.

hedron in three positions and the octahedron in one position only, but both estimated as with the number of faces different from six, because, in the beginning, the computer program was oriented to six-faced objects only.

CONCLUSION The use of the elementary Propositional calculus introduces a formal restriction for two reasons. First. the verbal sentences are treated as hermetically closed entities: transfer from verbal to mathematical description is rather rough. Second, for the more complicated spatial forms, the number of basic propositions becomes very big, which makes very difficult or even impossible computer elaboration. To overcome such a shortcoming, it is of interest to consider an application of the Predicate calculus, as a higher level of the mathematical logic. If we accept writing the basic propositions Li in the form of the predicates P(li), which means that the predicate P is true only if the subjective variable li belongs to the area for which the value of P is truth,

and introducing existential and universal quantifiers as symbols of disjunction and conjunction, the form of theoretical disjunction s(L)will be:

s(L)----, .s[PIl)] = 31VIP(I) where I = (l~, l,_..... I, ) is the area of the subjective variables relating to the definitions of spatial forms. This way we can get a shortened algorithm in computer processingofthe three-dimensional pattern recognition procedure. Thanks to the possibility of penetrating the structure of the propositions, it seems that we could elaborate more complex three-dimensional forms with detailed verbal definitions.

Acknowledgements--This work was partly realized in the pleasant environment of the Laboratorio di Cibernetica, Naples. The author is very grateful to L. Cordelia and S. Levialdi for a good collaboration and fruitful discussions. REFERENCES I. B. Raphael. Programming a robot. IFIPS Congress, Edinburgh (1968). 2. N. Ivanc'evic'. Sensitive transducers for controlling the Beograd hand prosthesis. V Congress of Cybernetic Medicine. Naples (1968).

Stereometric pattern recognition 3. A. Guzman, Computer recognition of three-dimensional objects in a visual scene, M A C - T R - 5 9 {Thesis), M,I.T. (19681.

83

4. S. Aida. N. Ivan~evic and L. Cordelia. Visual-tactile symbiotic s~stem for stereometric pattern recognition. 2ml ll~t. Joil~t Co~jl oil Artificial llztelli~lelrce, Imperial College London {1971).