Verfahren zur extraktion von kantensegmenten

The invention concerns a procedure within the range of machine seeing and the digital pattern recognition, a procedure for the extraction of outline-based picture characteristics. The recognition and detection of objects (e.g. Persons or vehicles) in digital pictures is a relevant topic the machine of seeing and the pattern recognition. A necessary step for object detection is usually the extraction of picture characteristics, which can represent certain object characteristics such as form, color, texture, movement, etc. Picture characteristics can be used in combination with different procedures of the pattern recognition, like Template comparison or machine learning, in order to determine the object situation (position, size and rotation). The problem of object detection is substantially made more difficult by the given high number of unknown object-specific parameters. These unknown quantities are for example the object situation, varying appearance of the object in the picture or the presence of possible covering. With deformationable or articulated objects, like for example persons, also the form will exhibit a high variability. The quantity of all unknown quantities defines the search area, a detection procedure must scan which for the desired object. The search is usually based on the comparison between characteristics. On the one hand reference characteristics will become from one or more pictures with object examples computed, on the other hand characteristics extracted from that picture, in which the object is to be detected. During the search the reference characteristics are compared with the picture characteristics which can be tested and if a high similarity is determined, the object is detected. In practice a high detection rate, a low false alarm rate and a real time ability are mostly demanded. These conditions can by one (n) computingefficient extraction and comparison by informative characteristics to be more easily realized. A goal of the invention is the ErsteUung of a procedure for the MerkmalsextrakUon, that the form of arbitrary objects in an efficient way by edge segment characteristics to represent can and independently of the size, position and twist of the object low cost of computation which can be detected necessary. These goals are achieved according to invention with a procedure of the kind initially specified with the characteristics stated in the characteristic of the requirement 1. With the received results the pattern recognition procedure is then continued. The procedure according to invention represents thus a stage and/or a preliminary stage of a pattern recognition procedure. 2…. Volkswagen Oll, • i: ö:. o. .o • ooDo • • •… • '… “O J1 S, • OooO the procedure according to invention makes an efficient search possible for objects in digital pictures in real time independently of position, size and twist of the object. A reduction of the cost of computation results on use of the characteristics of the requirements 2, 4 and/or 6. the comparison of the Dichtewerte of the samples with the Dichtewerten becomes with the characteristics of the requirements 2, 5, and/or 8 determined simplified. The invention concerns the moreover one also a data medium, which is characterized by the fact that on it a program for the execution in the requirements 1 to 8 stressed of the procedure is stored. In the following the invention is more near described on the basis the designs: Fig, la and lb show the approximation of the form of a free forming object by linear line segments by the piece in a digital picture. In order to be able to achieve an efficient extraction of the outline characteristics, the forms which can be looked for must be approximated by edge segments with discrete orientation. Fig. la an original object form and Fig shows. l b shows the approximation of the outlines in accordance with Fig. la by straight-line edge segments. Fig. an example of the line by line construction of Integralbildem so called shows 2 along the number of directions, given by the form approximation, which are defined particularly by the possible discrete directions in the digital pictures due to the discrete pixel situations. Along all directions and over the entire gradient picture summing the intensity values of a gradient picture and registering takes place in each case for the individual pixels determined kumulaUven sum values for the education of an appropriate number of integral pictures. Fig. 2 shows also examples, how from the difference of the intensity values B-A in the integral picture the sum of the intensities for the grey marked and/or between B and A lying pixels in the original gradient picture results in. Fig. the computation of line integrals and/or intensity sums shows 3 along the edge segments given by a sample object, that in Fig. 3 right is represented. The sample object consists of three straight-line pieces of edge. The presence of the individual pieces of edge is examined with the help of a sentence by integral pictures, which became to receive for different discrete directions. The directions, for which the integral pictures were provided, correspond to the directions of the edge segments in the sample. Fig. the regulation of line integrals (sum of the gradient intensities) shows 4 along the directions, which correspond to the edge segments of the sample object, as this right in Fig. 4 is represented. Four 3 • • • • oo • • • OooO • • o • • o • • • • • • • • eoeo • • ge gg eoo oeoe • EEC of integral pictures of the represented form is sufficient, in order to compute the characteristics of the edge segments according to the sample object in eight differently turned situations, whereby the position and size of the object can be arbitrary. The execution of the efficient characteristic extraction is explained on the basis an example object of a person silhouette. Fig. la in, in particular in digital form available, picture, in particular, shows gradient picture with the most important edges or picture gradients of a pedestrian. In order to be able to determine a hn1 ichkeii between the edge segments of a reference model and the picture, one would have to normally sum all pixel intensities separately along the edges of the reference model, in order to determine whether similar edge segments are present in the picture. The number of necessary arithmetic operations is given additions by N-1, whereby N is the number of edge pixels. The number of necessary operations can be substantially reduced by the procedure way according to invention, against what the final result of the object search remains similar. At the time of the execution of the characteristic extraction procedure according to invention become first, as in Fig. l b represented, which replaces edges of the reference model by straight-line Kantensegrnente. Over an efficient Surnmation of the pixel intensities along the outline to ensure and because of the discrete nature of digital pictures, for the orientation of the edge segments which can be given discrete values are given. It is favourable, if at least one of these given directions with one of the axes of coordinates of the picture includes an angle of for instance 0°, 26,6°, 45°, 63,4° or 90°. On the basis the picture, in which the search for the sample is to take place, a digital gradient picture is provided. The efficient computation of the sums of pixel intensities along individual edge segments and/or directions thereupon by integral pictures so called realizes. Integral pictures, as them admit 2002102024 A1 e.g. from US are, are also under the name, Summed AREA Table= e.g. from the WHERE 9963489 A1 and US 6031934 A1 well-known. Integral pictures are by the dozen computed a tabulated form by cumulative sums of pixel intensities along certain directions in the gradient picture. That is, that the integral picture is a picture, in that the pixel value in the place (x, y) the sum of intensities between the pixel at the row beginning and the final pixel (x, y) represented. Fig. 2 shows the basic concept for the construction directions discrete given by integral pictures for some and/or in a digital picture. The discrete directions are given by the discrete dissolution of a digital picture. The lines of the integral picture for a given direction # are calculated by a gradient picture by line by line summation of all pixel values, whereby summing all 4 ....... w can take place oo • • O0 • • • eoöO Ö Ö O0 O0 OOO 0600 • O0 of pixel values very fast, recursively. It is intended that for the gradient picture a number of discrete directions is given, as an integral picture of the gradient picture is provided, as for each of these directions over the entire gradient picture along the respective direction a cumulative summation and/or a sequential summation of the intensity values is made in each case along the respective direction lying, successive pixels, and which are registered for the respective pixels received sums into the respective integral picture, in the following the sum of the intensities in the integral picture is e.g. computed along a direction for a given distance, the distance B-A, by a subtraction Endund of the initial value of the distance in the integral picture, represented like it in fig. 2 for example for the points A and B is. The difference of the accumulated intensity values of the pixels A and B corresponds to the sum of the intensities of all grey marked pixels in the gradient picture. For other directions (e.g. = 26,6°, 45°, 63,4°) the sum computation is accomplished homogenously. For each discrete direction an integral picture is computed. With the help of a sentence by Integralbildem, provided by appropriate summing along the given directions, in each case over the entire integral picture, can along the edge segments of a hypothetical picture object (Fig. l b) the sums of the pixel intensities to be efficiently determined. The number of necessary operations is given independent by simple subtraction between Endund initial intensity values, an arithmetic operation per edge segment of the position and size of the object in the integral picture. The constant cost of computation is given by the fact that the computation of the sum of the intensities for all possible places in the picture is to be always counted and independently of the length of the edge segments through one subtraction. Fig. 3 right a Musterobjek't, which is to be found in the digital picture, shows an arrow with three edges A, B and C. the discrete directions of A, B and C three integral pictures is accordingly computed, in which the sums of the pixel intensities are accumulated along these directions. In Fig. 3 left is represented and/or the directions indicated the integral pictures, which are used for the cumulative summation and/or computation of the intensity sums along the edges A, B, and C. The advantage regarding computing complexity results from the fact that the integral pictures must be computed only once and the moreover one only three arithmetic operations are needed, in order to examine for an object position and a size the presence of edges in the picture. …. o vv - Volkswagen the integral pictures can be computed efficiently recursively, because cumulative sums represent a konsekutive addition, with which each again computed value of the sum of the earlier value and a new intensity value consists. The procedure according to invention makes possible still that integral pictures, which are calculated by discrete orientations for a sentence, for which detection of differently rotary sample objects be used can. Fig. this characteristic of the procedure demonstrates 4. Rotations around discrete steps produce again edge segments, which correspond to one of given discrete orientations. The sample object was turned around a repeated of /4 and eight new possible sample situations were generated (Fig. 4 right). For the determination of the sums of the intensities along the edges of these objects four integral pictures are needed. The individual edge segments are drawn in schematically in the integral pictures, the differences of the values at the edge terminator points supply the sums of the intensities. For the field use of the procedure according to invention also a multiplicity of orientations can be used, e.g. twelve discrete orientations; the cost of computation remains however significant under the cost of computation of a direct evaluation, with which the intensity values of each pixel must be picked out and summed. Furthermore with the procedure way according to invention it is intended that for those, in particular for a given number of, along which respective directions lying pixels the difference of the intensity values in the integral picture is formed and by division of the respective difference by the distance of the respective both pixels standardized Dichtewerte is determined. Thus a given number of largest Dichtewerte can as Kantenbzw. Outline segments and as representatively for the digital picture respected and to the comparison with given samples of discrete Kantenbzw. Outline segments to be consulted. These Dichtewerte can be determined and become rapidly by appropriate difference formation in the integral pictures with the Dichtewerten Kantenbzw. Outline segments of the pictures of discrete Kantenbzw, given as samples. Outline segments compared. It is planned that for the comparison samples are consulted by discrete edges and/or outline segments, those for the same discrete directions was determined as the Dichtewerte derived from the taken up respective integral pictures. The Dichtewerte, which are given by the sample, are compared with the determined Dichtewerten. Favourable way for each of the individual directions a majority is determined by best, standardized Dichtewerten and used as comparison with the Dichtewerten given by the sample. With statement of an agreement and/or fulfillment 6 • ee 'o it o '' e “'o Qe WHETHER • • • ee • EO of a comparison criterion the densities determined in the integral picture and the associated edge segments become as the edge segments of the sample object accordingly rated and if necessary for a further evaluation consulted. A reduction of the cost of computation can be achieved additionally, if from the gradient picture, in particular edge picture, an edge orientation picture is derived, whose pixel is to be inferred the orientation of the gradients at a pixel of the digital picture and with position of the respective integral pictures only from pixels is considered, which correspond to a given orientation. If the situation of the edge segments admits approximately is, pixels can be separated, edge orientations are assigned for the establishment of the integral picture, which do not agree with the looked for edge directions. If along respective orientation, e.g. 26,6°, lying pixels of this direction deviate somewhat (Fig. 2), then it is appropriate, if during the sequential summation of the pixels the intensities of the pixels lying within a given lateral distance to the respective direction vector are successively summed. ...... . v w OOOOOOg0000 O • • • • • • • • Ü mm mm gsI O oe • oe