US 4,845,765 AGrant
Process for the Automatic Recognition of Objects Liable to Overlap
Issue Date:1989-07-04
•3 Claims
•2 Drawing Sheets
Abstract
The invention relates to a process for the recognition of objects liable to overlap, on the basis of reference images of said objects and the image of the group of said objects. The process consists of coding successive elementary segments, whose ends are substantially located on the contour of each image in the "learning" phase of the contour of each object and in the object recognition phase. Pairs of characteristic segments in the contour of each image are then investigated, each characteristic segment being oriented and defined by its oriented angle, its length and its origin. Each pair giving a good image discrimination is called a transition vector. These vectors are hierarchized for the reference images and compared with the transition vectors of the image of the objects to be recognized. For any object assumed to be recognized, a fine verification takes place on the elementary segments. Application to the recognition or identification of objects and to artificial vision in robotics.
Metadata
Assignee
- Commissariat A L'Energie Atomique
Inventors
- Didier Juvin
- Shenbiao Tan
Application Information
Application Number:US 2070006
Filing Date:1988-06-08
Priority Date:1986-04-18
Art Unit:266
Classifications
IPC:
G06K 934
Field of Search:
3828;21;22;25;60;15;37
Patent Drawings (2 sheets)
Description
Background of the Invention
The present invention relates to a process for the automatic recognition or identification of objects liable to overlap. It applies to vision machines and more particularly to robotics, in which studies are presently directed at so-called "intelligent" robots able to interpret data from the external medium. The recognition or identification of partly hidden objects, e.g. as a result of a partial overlap of said objects, is of considerable importance for the next generation of vision machine.
Different processes for the recognition of objects liable to overlap are known in the art. One of these processes consists of segmenting the contour line of the image of each object to be recognized and defining in the segmentation of each contour "privileged" segments, which are in fact the longest segments. This definition of privileged segments is carried out during a learning period.
In this known process, during the period of recognizing the different objects, hypotheses are issued on the basis of an examination of the privileged segments and associated segments recognized in the contour of the image of the objects to be recognized. A "label" is then allocated to each privileged segment recognized in the contour of the image of the objects to be recognized. Then, on the basis of the different labels obtained in this way, an overall criterion is defined, which is a measure of the consistency and non-ambiguity of the labelling system. A quality score is then calculated for evaluating the hypotheses.
This type of process takes a long time and is very expensive, because it generates a large quantity of hypotheses, which must be checked according to complex criteria for measuring the consistency and non-ambiguity of the labels. This type of process is e.g. described in the doctorate thesis entitled "A bidimensional vision system in industrial robotics" by N. AYACHE, 1983.
The invention aims at obviating the disadvantages of this type of process and more particularly at permitting an automatic, fast recognition of objects liable to overlap, without it being necessary to emit, during this recognition, a large number of hypotheses and criteria for checking said hypotheses. These objectives are more particularly attained by using a particular segmentation of the contours of the images of the reference objects and the images of the object to be recognized and as a result of the choices of the pairs of characteristic segments making it possible to define "transition vectors" on the basis of which the hypotheses and recognition criteria are developed.
Summary of the Present Invention
The present specifically relates to a process for the automatic recognition of objects liable to overlap, on the basis of respective reference images of said objects, and the image of the group of objects to be recognized, said images being stored in the form of digital values representing for each image the coordinates of the points of a contour line of said image, in a frame of reference, said process consisting of coding, for each image, successive elementary segments, whereof the ends are substantially located on the corresponding contour line, so that for each segment, said coding gives the length of said segment, as well as its angle with respect to a reference direction, said coding operation being performed both during the "learning" phase of the different objects to be subsequently recognized and in a subsequent "recognition" phase of the objects liable to overlap, wherein it comprises in the learning phase: investigating for each reference image contour, pairs of successive or non-successive characteristic segments of said path, each formed from one or more elementary segments, said characteristic segments being oriented in a predetermined direction of the contour path, each pair determining a characteristic transition vector defined by parameters which are the value of the angle, oriented in the direction of the path, between the two oriented characteristic segments of the pair, the coordinates of the origin and the length of each characteristic segment of the pair, a transition vector being characteristic when its parameters bring about a discriminating power of the contour of the corresponding object, even when said object is overlapped by one or more other objects, the parameters of the transition vectors being stored, hierarchizing the transition vectors of a contour as a function of their discriminating power, modifying said hierarchization of the transition vectors during the acquisition of the transition vectors of the contours of the different objects, so as to eliminate the similar transition vectors for the different contours, said process then comprising in the recognition phase: performing the same transition vector determination operation in the characteristic segments of the contour of the image of the objects to be recognized, comparing in the hierarchization order, the values of the parameters of the transition vectors of the contour of the image of the objects to be recognized and the contour of the reference images of each object, so as to investigate the similarities of the values of said parameters, forming a presence hypothesis of an object corresponding to a transition vector for which the comparison has established a similarity, and effecting a fine check of said hypothesis by comparing successive elementary segments of the contour of the reference image of said object with successive elementary segments of the contour of the image of the objects to be recognized.
According to another feature, the coded successive elementary segments are obtained by a Freeman coding making it possible to obtain successive segments defined by their orientation and whose ends are substantially located on the contour line of each image, said Freeman coding being followed by a corrective processing making it possible to deduce from each segment coded according to Freeman, one or more sucessive elementary segments, whose ends are located on the contour line of the image, said successive elementary segments having equal lengths and permitting isotropic coding.
According to another feature, the corrective processing, for each Freeman-coded segment, comprises differentiating said segment with respect to its order number in the contour in order to compensate orientation irregularities, performing a conversion of the values resulting from the differentiation of each segment in order to compensate length irregularities, filtering the resultant signal of said conversion, sampling said signal at constant frequency and then integrating the sampled signal, said integration producing the successive coded elementary segments. The corrective processing also makes it possible to extract angular points, i.e. facilitates the extraction of the characteristic segments.
Moreover, said conversion can either be a digital-analog conversion permitting a sampling on the analog signal, or a digital-digital conversion.
Brief Description of the Drawings
The invention is described in greater detail hereinafter relative to non-limitative embodiments and the attached drawings, wherein:
FIG. 1 shows diagrammatically the characteristic segments of a contour line L.
FIG. 2 shows diagrammatically the segmentation of a contour line according to a Freeman code.
FIG. 3 shows the Freeman vectors used for coding a contour line
FIG. 4a shows diagrammatically a contour line segmented according to a Freeman code and FIG. 4b shows diagrammatically the same contour line segmented following a processing performed on Freeman segments.
FIG. 5 shows diagrammatically the derivation stage intervening in the inventive process.
FIG. 6 shows characteristic segments according to the invention of the contour line of an object.
FIG. 7 provides a better understanding of the transition vector notion between two characteristic vectors.
FIG. 8 shows diagrammatically certain characteristic segments in the contour of the image of several overlapping objects.
FIG. 9 shows diagrammatically a system making it possible to perform the inventive process.
Detailed Description of the Preferred Embodiments
The process for the automatic recognition or identification of objects liable to overlap according to the invention firstly uses a particular coding of the contours of the respective reference images of said objects taken individually, during a learning phase of each object. This particular coding is also used for the image of the group of objects to be recognized during a recognition period, the objects being liable to overlap in such a way that one or more objects are partly hidden by surrounding objects.
The reference images, as well as the overall image of the objects to be recognized are stored in the form of digital values representing, for each of said images, the coordinates of the points of a contour line of said image in a frame of reference. These images are e.g. supplied by optoelectronic means, such as a television camera. In known manner, this camera is connected to an analog-digital converter, which is in turn connected to a processing unit. The function of the latter is, during the recognition period, to determine the digital values corresponding to the coordinates of the points of the characteristic contour line of the reference image of each object. These processing means also make it possible to supply digital values corresponding to coordinates of points of a characteristic contour line of the image of the group of objects to be recognized, during a recognition period, when said objects are liable to overlap. All the digital values are obviously recorded in a memory of the aforementioned processing unit.
The following operation consists of defining characteristic coded segments, whose ends are substantially located on each contour line of the reference images during the learning period and on the contour line of the image of the objects to be recognized during the recognition period. Characteristic segment C of said type, whose ends are located on the contour line L of an image, is shown in FIG. 1. As will be shown hereinafter, each characteristic segment generally has a plurality of successive aligned elementary segments. The coding of each characteristic segment supplies the length of each segment, as well as its angle with respect to a reference direction. This coding is obviously performed both in a learning phase of the different objects to be subsequently recognized and in a subsequent recognition phase of the objects liable to overlap.
Preferably, according to the inventive process, the coding of the characteristic segments firstly consists of coding the segments, making it possible to approximate the contour line of each image in accordance with a method called "coding by Freeman vectors". This coding is followed by a corrective processing making it possible to obtain the aforementioned successive elementary segments, making it possible to define the characteristic segments of the contour line L of the considered image.
The method of coding by Freeman vectors will be made clearer on the basis of FIGS. 2 and 3.
It will firstly be considered that the contour L of the image in question (reference image of an object or image of the group of objects to be recognized) is spatially digitized in a matrix having M.times.N points in a frame of reference or X-Y coordinate grid. The Freeman coding method consists of coding elementary displacements performed along contour line L in accordance with segments as shown in FIG. 2. In the chosen matrix representation, on considering that each image element is square, there only eight orientation possibilities according to Freeman for passing from one point to another of a contour. These eight possibilities are represented by the eight vectors, called Freeman vectors, numbered 0 to 7 in FIG. 3. These eight vectors are in fact displaced by 4 in the considered matrix representation example. Thus, the Freeman vectors make it possible to define successive coded oriented segments, whose ends are located on each contour line. The coordinates of these ends are obviously known from the coordinates of the points of each contour line.
In the example of the segmented contour L of FIG. 2, if the starting point of the path of said contour is A, of coordinates 2, 3 in the chosen matrix, the Freeman chain associated with contour L can be expressed as a function of the vector numbers of FIG. 3 in the following way:
This coding is particularly interesting because it reveals the orientation of the segments of the contour line with respect to the reference direction X.
The coding of a contour line of an image by Freeman vectors leads to imprecisions in the approximate representation of the contour by coded segments. Thus, the Freeman vectors are inscribed in a square, as shown in FIG. 3, or in a rectangle. Thus, the Freeman vectors perpendicular to the sides of the square or rectangle, as well as the vectors located in the diagonals of said square or rectangle do not all have the same length. This Freeman coding is e.g. described in French patent application No. 8304447, filed on Jan. 31, 1983 in the name of the present Applicant.
It is known that Freeman coding breaks down a contour line into a succession of elementary vectors, whose direction is coded on three bits. This coding is very interesting by its conciseness, but also has disadvantages:
a significant digitization noise, because the orientation on 360.degree. is coded on three bits,
the real lengths represented by the codes are irregular, as stated hereinbefore, the orientation represented by the codes are not isotropic in the case where the picture elements are rectangular.
These shortcomings are inadmissible for the recognition of overlapping objects, because they lead to an error in the coded representation of the contours and induce privileged directions. This anistropy becomes all the more disturbing in the recognition phase where some of the informations are already deteriorated by the overlapping of objects. However, Freeman coding has an essential interest. It makes it possible to obtain a precise and non-varying contour representation, both in translation and in rotation. This notion of non-varying in translation and rotation is well known in the art and is in particular described in the aforementioned application.
According to the invention, to obviate the imprecisions of Freeman coding, a corrective processing takes place making it possible to deduce, on the basis of each segment coded according to Freeman, one or more successive elementary segments, whose ends are substantially located on the contour line of the image, said elementary segments then being isotropic and of equal lengths.
The corrective processing of the Freeman-coded contour is preferably performed according to the invention in the following way. There is firstly a differentiation of each coded segment with respect to its order number. The principle of said differentiation is as follows: F(n) is the Freeman code which is an integer between 0 and 7, n is the order of the contour segment associated with said code, i.e. .phi.d(F(i), F(j)) a differentiation function corresponding to the real orientation variation between two codes F(i) and F(j) and C a constant permitting the amplitude normalization, whereby said processing can be represented by: Fd(n)=C.phi.d(F(n+1), F(n)), in which Fd(n) are codes generated by said processing. This is followed by a conversion of these data corresponding to an abscissa normalization of the coded segments. This abscissa normalization is performed in the following way. If a Freeman code F(n) represents a real length P(F(n)), said stage transforms Fd(n) into a pseudo-continuous form Fd(p), the integer n and the real number p obeying the following relation: ##EQU1## This is followed by digital filtering on the signals resulting from the above conversion. This filtering is performed in the following way. To reduce digitization noise, use is made of a low-pass filter, whose pulse response is M(p). Filtering is simulated by a time convolution: G(p)=Fd(p).phi.M(p), in which G(p) is the filtered signal. Finally, the filtered signal is sampled. Sampling at regular interval Po on G(p) converts it into G(kPo), which can be designated G(k). The interval Po is determined as a function of the cut-off frequency Fc of the low-pass filter in order to satisfy the Nyquist criterion, but is limited by the resolution of the image on the one hand and by the requisite processing speed on the other. The code G(k) represents a mean orientation variation of the contour on a vicinity, whose size is mainly dependent on the cut-off frequency of the low-pass filter. The sign of G(k) indicates the convexity or concavity of the contour. These characteristics are very interesting, because they prepare and improve segmentation. Segmentation is followed by an integration of the sampled signal, said integration making it possible to obtain the successive elementary segments from which, according to the inventive process, will be determined in the learning and recognition phases, the transition vectors to be defined hereinafter.
FIG. 4 shows an example of a contour portion L of an image obtained by Freeman coding. This portion is formed from successive segments S.sub.i making it possible to relatively imprecisely approximate the contour line . FIG. 4b shows the same contour portion L following the aforementioned processing and before sampling and integration. It can be seen that this contour portion is defined by a larger number of segments S.sub.e, called successive elementary segments. The aforementioned processing, as will be shown hereinafter, makes it possible to determine the so-called characteristic segments grouping several elementary segments. Thus, the coding and processing described hereinbefore make it possible to approximate the contour line by the largest possible number of segments of greater length, grouping in each case several elementary segments. These long segments are the aforementioned characteristic segments. This coding and processing also make it possible to obtain an important parameter, which is the orientation of each characteristic segment with respect to a reference direction.
The aforementioned operation of differentiating the successive elementary segments in fact supplies a succession of pulses. The amplitude of each pulse is much greater when the angle between two corresponding successive elementary segments is high. The filtering operation only retains the important means orientation variations, as is shown by fig. 5, which represents the signals obtained after derivation and filtering. Sampling and integration following said filtering make it possible to reconstitute a characteristic image of object O.sub.3, constituted by characteristic segments C, each of which is equivalent to an association of several elementary segments. These characteristic segments make it possible, as will be shown hereinafter, to define transition vectors.
FIG. 6 diagrammatically shows the image of the contour of an object obtained following the aforementioned coding and processing. The real contour of said object is not shown in the drawing. All that is shown is its approximate contour following said coding and said processing. The contour thus obtained is formed from characteristic segments C1, C2, C3, . . . C8. Each of these characteristic segments is equivalent to several successive elementary segments, like segments S.sub.e in FIG. 4(b), which are themselves obtained from successive Freeman segments S.sub.i of FIG. 4a. It is assumed that the contour represented in exemplified manner in this drawing is that obtained after coding and processing of a reference image of an object O.sub.1 during the learning phase.
The process of the invention consists of choosing a predetermined contour path direction, such as that indicated by the arrow in the drawing. The process then consists of choosing characteristic pairs of successive or non-successive characteristic segments of said contour. These characteristic segments are oriented in the predetermined contour path direction. A pair of characteristic segments can e.g. be the pair of segments C1, C8, but could also be the pair of segments C8, C9. Each pair of characteristic segments makes it possible to determine a characteristic transition vector, as will be shown hereinafter.
FIG. 7 provides a better understanding of the notion of the transition vector, by referring e.g. to the pair of characteristic segments C1, C8 of object O.sub.1. The pairs of characteristic segments of a given object are those which, during the recognition phase of the different objects and even in the case of a subsequent overlapping thereof, will permit a better discrimination of the predetermined object, such as that whose coded contour is shown in FIG. 6.
A transition vector is defined as a relation between two characteristic segments of a contour. In the example represented in the drawing, segment C8 can be called e.g. the inlet segment in the zone of the contour of the image of object O.sub.1, whereas segment C1 can be called the outlet segment of said zone. The portions of the contour not belonging to the pairs of characteristic segments chosen are considered as a non-interesting part of the zone of the contour because, according to the process, no interest is attached to the path of the contour within said zone.
A transition vector for the pair of characteristic segments C1, C8 is defined by the three following parameters: the inlet orientation .alpha.8, which is the angle oriented in the predetermined travel direction between the reference axis Ox of a reference coordinate (O, x, y) and the characteristic inlet segment C8 oriented in the direction of travel, the outlet orientation, which is the oriented angle .alpha..sub.1 between the reference axis Ox and the characteristic outlet segment C1, oriented in the direction of travel, the "valid" space, which can be defined by the coordinates of the starting point P.sub.8 (x,y) and P.sub.1 (x,y) and by the length L.sub.8, L.sub.1 of the oriented segments C8 and C1.
According to the invention, a transition vector is characteristic, when its parameters (inlet orientation, outlet orientation, origin of the characteristic segments of the pair and length of these segments) leads to a discriminating power of the contour of the considered object, even if in the subsequent recognition phase, said object is overlapped by one or more other objects.
In particular, the difference .alpha..sub.d =.alpha..sub.1 -.alpha..sub.8 remains valid, even in the case of a partial overlap of the considered object by other objects, as is shown by FIG. 8. The latter shows that in the case of a partial overlap of the considered object O.sub.1 by two other objects O.sub.2 and O.sub.3, the valid space is reduced, because the characteristic vectors C8 and C1 have truncated lengths, but the difference .alpha..sub.d =.alpha..sub.1 -.alpha..sub.8 remains valid. The importance of the transition vectors is clear because, during the recognition phase, the transition vector constituted by the pair C8, C1 of characteristic vectors makes it possible to recognize the object O.sub.1, even if certain parts of the latter are hidden by other surrounding objects.
Thus, the essential information relating to a transition vector is based on the orientation difference .alpha..sub.d between the characteristic vectors of the pair relating to said transition vector. Bearing in mind this criterion, it is possible to arrange the parameters of the transition vectors in a hierarchic manner, as a function of the probability of the same orientation .alpha..sub.d appearing for a considered object and for other surrounding objects liable to overlap the considered object. The more the orientation .alpha..sub.d is particular or special for an object, the greater the importance attached to the corresponding transition vector in the dictionary of transition vector parameters formed during the learning phase of the different objects.
Thus, the hierarchization of the transition vectors is an important phase of the inventive process. These transition vectors are classified as a function of their discriminating power for the same object and are also classified according to their discriminating power for one object compared with another. The transition vectors are considered to be the most significant identification means of an object. These vectors are hierarchically arranged according to the aforementioned criteria: information quantity, the probability of disappearance and false generation in the case of overlap.
According to the inventive process, processing also takes place of the interaction between the transition vectors of a new object whose contour must be "learned" and the transition vectors of objects whose contours have already been "learned". For a new object, the manner of recording and classifying the transition vectors is dependent on that of existing objects. The transition vectors of existing objects must be rearranged in accordance with those of the new object. The case may arise that a transition vector initially considered as relevant loses much of its significance during learning. In this case, the first group of informations of the dictionary formed during the learning phase makes it possible to calculate a new transition vector to replace an already recorded transition vector which is less relevant.
The operations described hereinbefore for the learning phase are also performed during the phase of recognizing the contour of the different overlapping objects. The same operation of determining the transition vectors in the characteristic segments of the contour of the image of the objects to be recognized is performed.
During the recognition phase, a comparison is carried out, in the hierarchization order, between the values of the parameters of the transition vectors of the image contour of the objects to be recognized and the values of the parameters of the transition vectors of the reference image contour of each object, so as to investigate the similarities of values of said parameters. This comparison is a preliminary analysis, which will be followed by a fine check, as will be shown hereinafter.
The object of the preliminary analysis is to as rapidly as possible generate hypotheses concerning the presence of objects and the orientations thereof. These hypotheses are obviously issued on the basis of the recognition in the image contour of the object to be recognized of transition vectors of certain objects.
The inventive process firstly investigates a similarity between the first transition vectors of each object of the dictionary and a transition vector of the contour of the image of the object to be recognized. If no coincidence is found, the process consists of investigating coincidence with the second transition vectors of each object of the dictionary and so on.
When coincidence is found between transition vectors of the contour of an image of a reference object and transition vectors of the contour of the image of objects to be recognized, a fine verification takes place of the presence hypothesis of the partly recognized object. This fine check consists of comparing successive elementary segments of the contour of the reference image of the partly recognized object on the basis of transition vectors with the successive elementary segments of the image contour of the objects to be recognized.
Fine checking in fact consists of investigating whether there is a superimposing of the contour (defined by elementary segments) of the reference object image, as a function of its orientation indicated by the transition vector found, with part of the contour of the image of said object found in the contour of the image of objects to be recognized.
Three conditions are necessary for concluding that an object is present. It is firstly necessary to check that the segment of the object assumed as recognized is not located outside the contour of the image of the objects to be recognized. The second condition is that the ratio of the identified perimeter of the object in the contour of the image of the object to be recognized to the perimeter of said object (in the reference contour) exceeds a predetermined threshold. This check is possible because the lengths of all the elementary segments of the contour of the image of the reference object are known and one also knows the lengths of the elementary segments of said partly recognized object in the image of the contour of the objects to be recognized. It is also checked that the ratio of the sum of the absolute values of the angles corresponding to the identified angular points in the contour of the image of the objects to be recognized to the total sum of the absolute values of the angles corresponding to the angular points contained in the contour of the reference image of said object exceeds another predetermined threshold.
When these three conditions are combined, the inventive process makes it possible to affirm that the considered object is recognized among all the other objects which possibly partly overlap it.
In the case of perimeters, if the threshold ratio of the perimeter of the object being recognized to the perimeter of the reference object is selected to be unity, recognition of an object will be very difficult. This is because the condition where the ratio of the perimeters is unity corresponds to the case where the object being recognized is not covered to any extent by overlapping objects. At the other extreme, if the threshold of the perimeter ratio is selected to be zero, there is no recognition of an object to be recognized because this corresponds to the case where the object to be recognized is completely hidden by overlapping objects.
Consequently, the threshold value for the perimeter ratio need only be some value between zero and unity, but not equal to zero or unity. In practice, a good threshold value is 0.5, but other values are also satisfactory. The threshold value selected will depend on the objects being recognized in a particular work situation. Therefore a specific threshold value has not been given since the same threshold value would not be used in all situations. Similar considerations apply for the threshold value of the sum of the angles.
Following this stage, if there are transition vectors or segments of the contour to be analyzed, which do not form part of the contour of the already recognized object, the same operations are performed for another object with respect to which it is considered that one or more transition vectors have been recognized.
For example, in FIG. 8, during the recognition phase, a comparison takes place for the contour L of the image of the objects to be recognized, between the transition vector corresponding to the pair of segments A8, B8 and A1, B1 with the transition vector corresponding to the pair of segments C8, C1 of object O.sub.1 (partly hidden by overlapping during recognition). It is obvious that in the example shown in the drawing, there is a similarity of the transition vectors.
The following stage consists of performing a finer comparison between successiv elementary segments S.sub.e (cf. FIG. 4b) constituting segments A8, B8 and C8 and segments A1, B1 and C1.
The process described hereinbefore makes it possible to recognize isolated objects, partly hidden by overlapping, by reference to a dictionary of shapes, formed during the learning phase. The recognition time varies as a function of the nature of the scene to be analyzed. If use is made of a standard 16 bit microprocessor, an isolated object is recognized in less than one second, whereas a scene formed from several overlapping objects is analyzed in 2 to 5 seconds. This process offers a very satisfactory reliability, because contour processing utilizing transition vectors essentially takes account of disparities between the objects.
When an object has been recognized, an attempt is made to recognize the other objects present in the scene. For this purpose, masking takes place of all the informations relating to the segments of said object recognized in the scene.
FIG. 9 diagrammatically shows a system making it possible to perform the inventive process. This system e.g. comprises a video camera 1, which transmits to a processing system and during the learning phase video signals relating to the contours of the reference images of the different objects. This camera transmits during the recognition phase of the video signals relative to the contour of the image of the objects O.sub.1, O.sub.2, O.sub.3, O.sub.4 to be recognized.
The processing means comprise a computer 2 connected to a memory 3, in which are recorded a processing program, as well as the digital values to be processed or the processed digital values corresponding to the contours of the reference images or to the contour of the image of the objects to be recognized. Computer 2 can be equipped with a control keyboard 4. This computer controls a digitizing and storage system 5 for the signals received from the camera. Computer 2 receives the output signals from said system 5 and performs all the processing operations described hereinbefore. A display means 6 makes it possible to display the contour of the reference image of each object during the learning phase, or the contour of the image of the objects to be recognized during the recognition phase. Computer 2 can control by an output a robot 7, which seizes a recognized object, if this is necessary.
In a variant of the invention, system 5 also performs part of the processing of the signals received from the camera. This processing operation comprises the operations of extracting from the contour, coding by Freeman vectors, differentiation, digital-analog conversion, filtering, sampling and integration referred to hereinbefore. The computer receives the output signals from the processing system 5 and investigates the characteristic segments on the basis of successive elementary segments determined by the processing system 5 and calculates the transition vectors. The computer program for carrying out the process of the invention for carrying out the process of the invention is attached as Appendix I.
Claims
What is claimed is:
1. Process for the automatic recognition of objects liable to overlap, on the basis of respective reference images of said objects, and the image of a group of objects to be recognized, said images being stored in the form of digital values representing for each image the coordinates of the points of a contour line of said image, in a frame of reference, said process consisting of coding for each image, successive elementary segments, the ends of each elementary segment being substantially located on the same contour line, so that for each segment, said coding gives the length of said segment, as well as its angle with respect to a reference direction, said coding operation being performed both during a "learning" phase of the different objects to be subsequently recognized and in a subsequent "recognition" phase of the objects liable to overlap, wherein said process comprises in the learning phase the following steps: investigating for each reference image contour, pairs of successive or non-successive characteristic segments of said contour line, each formed from one or more elementary segments, said characteristic segments being oriented in a predetermined direction of the contour line, each pair determining a characteristic transition vector defined by parameters which include the value of an angle, oriented in the direction of the contour line, this angle being defined as the angle between the two oriented characteristic segments of the pair, the coordinates of the origin and the length of each characteristic segment of the pair, a transition vector being characteristic when its parameters provide a substantive discrimination of the contour of the corresponding object, even when said object is overlapped by one or more other objects, the parameters of the transition vectors being stored, hierarchizing the transition vectors of a contour as a function of their discrimination parameters, modifying said hierarchization of the transition vectors during the acquisition of the transition vectors of the contours of the different objects, so as to eliminate similar transition vectors for different contours, and said process comprising in the recognition phase the following steps: performing the same transition vector determination operation in the characteristic segments of the contour of the image of the objects to be recognized, comparing in the hierarchization order, the values of the parameters of the transition vectors of the contour of the image of the objects to be recognized and the contour of the reference images of each object, so as to investigate the similarities of the values of said parameters, forming a presence hypothesis of an object corresponding to a transition vector for which the comparison has established a similarity, and effecting a fine check of said hypothesis by comparing successive elementary segments of the contour of the reference image of said object with successive elementary segments of the contour of the image of the objects to be recognized.
2. The process according to claim 1, wherein the successive elementary coded segments are obtained by Freeman coding making it possible to obtain successive segments defined by their orientations and having ends which are located on the contour line of each image, said Freeman coding being followed by a corrective processing making it possible to deduce on the basis of each Freeman-coded segment, one or more successive elementary segments, the ends of each located on the contour line of the image, said successive elementary segments being isotropic and of the same length.
3. The process according to claim 2, wherein the corrective processing consists, for each Freeman-coded segment, of differentiating said segment with respect to its order number in the contour, in order to compensate for orientation irregularities, performing a conversion of the values resulting from the differentiation of each segment in order to compensate for length irregularities, filtering the signal resulting from said conversion, sampling said signal at a constant frequency and then integrating the sampled signal, said integration producing said successive elementary coded segments, the preceding corrective processing also making it possible to extract the angular points, and consequently the characteristic segments.
Patent Citations (5)
Non-Patent Literature (9)
- Segen, "Locating Randomly Oriented Objects from Partial View," Proc. of SPIE, vol. 449, Nov. 1983, pp. 676-684.
- Perkins, "Multilevel Vision Recognition System," IEEE Proc. of Int'l. Joint Conf. on Pattern Recognition, pp. 739-744.
- Bolles et al., "Recognizing & Locating Partially Visible Objects: The Local-Feature-Focus Method", Int'l. J. of Robotics Reserch, vol. 1, No. 3, 1982, pp. 57-82.
- Stimets et al., "Rapid Recognition of Object Outlines in Reduced Resolution Images", Pattern Recognition, vol. 19, No. 1, 1986, pp. 21-32.
- Tou, "PUMAC-A Picture Understand Machine," 5th International Conference on Pattern Recognition, vol. 1, Dec. 1980, pp. 754-758.
- Freeman, "Computer Processing of Line-Drawing Images", Computing Surveys, vol. 6, No. 1, Mar. 1974, pp. 77-85.
- Segen, "Locating Randomly Oriented Objects from Partial View," Proc. of SPIE, vol. 449, 1983, pp. 676-684.
- Perkins, "Multilevel Vision Recognition System", IEEE Proc. of Int'l. Joint Conf. on Pattern Recognition, pp. 739-744.
- Bolles et al., "Recognizing and Locating Partially Visible Objects: The Local-Feature-Focus Method," Int'l. J. of Robotics Reserach, vol. 1, No. 3, pp. 57-82.