DE10161681C2 - Process for the detection of structures in (n + 1) -dimensional spaces by displacement and n-dimensional aggregation - Google Patents

Description

State of the art

Many radars are able to identify moving objects.

Object tracking in the navigation radar or surveillance radar is usually done Identification of areas with stronger reflections in the individual radar image. Preferably with repeated, limited shifted appearances in the following Radar images are confirmed as objects or targets, and their movements can thus be tracked (for example in Furuno Service manual marine radar FR1505 Mark-3 series, pp. 2-23). In more complex processes, a target is identified by comparison with "Signatures", ie typical appearance patterns of the objects sought. It can in the Usually at the individual times the location of suspected objects or a Focus of their image can be determined.

Objects from an "instantaneous image" are also identified when Radars, such radar systems then physically using their radar beam Follow objects.

By comparing the distance between images recorded at different times with the speed of travel of the objects actually sought can be determined whether different images can belong to an object or whether objects can be excluded in speed ranges of no interest. Then you can too a forecast of the subsequent movement is made. A method of this type is advantageous recognizable emergence of the objects against noise in the individual images. More complex algorithms also take into account the possibility of short-term Interruptions in the signals and other probabilistic factors. Buurma (Long range surveillance radards as indicators of bird numbers aloft, Israel Journal of Zoology, Vol. 41, especially p. 229) mentions such an iterative process, which, however, is also based on the Preselection of radar echoes in individual images.

Noise reduction by repeated addition of signals is known, with which Averaging out stochastically occurring disturbances, supported if necessary by pulling them off an average noise intensity. This works best with the same ones Useful signals, or in the case of radar images in the case of still objects, which are in successive radar images occur in the same place.

Even with moving signals that are too weak to be individual in individual pictures to emerge, or not to allow such identification, can be partially through Summation of several images (echo trail or long exposure, see Buurma p. 224) achieved that useful signals that are repeated at the same point or along a Line of movement occur, can be recognized ex-post as a trace. In contrast, spread out stochastically occurring interference signals more evenly in the room and thus only result weaker "grayscale" of the background. This can only be done by storing Spaces where the signal strength exceeds specified minimum values are supported (e.g. procedure of the SWARM software from Trios).

This corresponds to a projection of the three-dimensionally interpreted image sequence in the direction of the Time dimension on the two-dimensional level of a sum image. So it comes with 2- dimensional images with n = 2 to an aggregation along the time as third or n + 1- ter coordinate axis, and without displacement within the other coordinates. you can this projection as a side or actually oblique view of the line-like designate extended object, which represents its "long side" in space-time. The disadvantage is that with moving targets, the distribution of the signals over several locations a line of motion is masked by interference signals or by their fluctuations  can effect. In addition, sometimes no distinction can be made in images added over time more between signals from multiple targets to be captured.

In the case of stationary objects, on the other hand, the signal repeats at the same point. In the Summation over time therefore results in a stronger concentration of the signals at the same Place on (see procedure Seascan Ryan J .: Application of High Speed Scanning Radar to search, surveillance and navigation). A still small object results in space-time a line that runs parallel to the "time" dimension and only because of its spatial stability has a small extent in the direction of the spatial dimension. At summation If several images are consecutive in time, a projection takes place along the time along the narrowest side of the spatial-temporal representation of these objects. The result represents, so to speak, the "narrow side view" of this extending in space-time Objects. Therefore, there is a stronger signal amplification than that described above Projection of moving objects in a similar way. However, the resulting one leaves "Point" usually makes no statements about the time and duration of the signal. Besides, that is Detection of fixed objects of less interest. A comparable signal gain the detection of such objects would also significantly improve for moving objects.

Another established technique is image processing. In image processing is mostly differentiated between procedures in which grayscale is processed without objects delimit, and procedures in which only objects with recognizable Boundary lines are delimited and then edited.

Known image processing steps such as u. a. Capping, smoothing, edge increases, The center of gravity and the size of identified objects can be determined basically also transferred to images with more than two dimensions.

Since there are basically any number of directions and orientations, their Diversity with the number of dimensions and the resulting number of degrees of freedom increases, pattern recognition in multidimensional spaces usually triggers quickly Limits.

Another known method is the Hough transformation.

Also for the search for lines or movement patterns in multi-dimensional spaces The help of the Hough transformation or the dynamic Hough transformation result computational limits, since these are more complex calculation steps than the simple addition moved images required. Hough transformations often only take place after Restriction of an image to binary edge lines. Analogies between the Hough Transformation and subsequent invention result from the projection into one Evaluation room and the implementation of a selection algorithm in the evaluation room, (see http: / / cs-alb-pc3.massey.ac.nz/notes/59318/l11.html/ as of December 2001). A goal the invention is therefore a computationally simple method, which, however, by Use of several evaluation rooms for several types of postponement is purchased.

Another method is described in EP 0 562 004 B1.

Time series of data are also stored there in multidimensional data matrices. As a technical example described therein, a passive sonar detection, which is characterized in that noise sources are detected from different directions (see Fig. Fig. 1, Fig. 3 et seq. And Fig. 11-12), because of the unknown distance of the noise source but first No statement about the movement of the noise source is allowed because only the angle relative to the receiver is given as location information. Column 15, line 29 ff. And column 16, line 49 ff. Refer to possibilities of eliminating certain noise from the raw data. The possible visualization of the data in a data cube and its viewing "from one of the three sides" of the same is described (column 8 , line 42 f.). However, the possibility of an "oblique" view is not specified. It would also not make sense in the selected examples from sonar technology, in any case it would not lead to the "filtering" of objects according to their speed vector. The chaining along one dimension (column 20 line 18 or column 25 / line 15 ), that is to say in the case of spatial data, is in each case at right angles to the other dimension.

For an analysis of typically three-dimensional images as below described, with conversions (shifted Addition) in the gray value range and subsequent selection operations are not Role models known. There is also a mix of selection steps per without a role model Algorithm with subsequent visual analysis by humans, as they are in particular can take place following a computing method according to claim 9 or 10.

task

The object of the invention is to describe a method for searching for elongated Objects of unknown orientation in multi-dimensional spaces, or in their images in computer systems. A preferred application is the detection of moving objects, which are examined with radar, insofar as they are in single image or in snapshots stand out little from interference signals. Time is considered a dimension of one multidimensional space.

Images to be evaluated in this way could be generated using electromagnetic waves, such as radar or light, generated with acoustic methods or in some other way. to The images could have been actively emitted by the examiner when producing the images be (radar, sonar location, seismic), or there could be emissions of the observed object or ambient radiation reflected there can be observed. The distance or Location information could be determined by runtime determination, by stereoscopic bearing or by other procedures have been identified.

New solution

While intuitively detecting elongated objects by looking at them Obviously along the side, the invention is based on the idea of a projection in the Longitudinal direction of the extent of the objects, and thus on a surface perpendicular to this Direction of expansion, or on detection after projection at an acute angle. In the event of the search for moving objects is a projection (approximately) parallel to their spatiotemporal direction of movement (claim 4). This will put them on a small Cross-sectional area depicted (spatiotemporal). They are supposed to do this in a similar way amplify and thus differentiate it from other signals, as do standing objects that always generate signals at the same point when stationary images add up over time or be aggregated. Here, functions are referred to as aggregation, which the Intensity values or other properties of several points (in n + 1 space) to one Summarize value.

In many cases a movement in two-dimensional space will have to be analyzed how a track is treated in a three-dimensional space.  

Since it is not known in which direction objects are moving, and differently moving objects each with different projection directions in this way emerge, these projections for different directions (claim 1) carried out. The projection directions, or the shifts derived from them, can be selected in such a way that objects emerge which - roughly - match the move the desired speed. The resulting "cross-sectional images" allow statements that an object extended in this direction (probably) is available.

Then an analysis of the projections or total images obtained in this way can be carried out in the two-dimensional plane. Here are available in appropriate forms in particular to pattern recognition methods (claim 5 ff.) which according to delimitable Search for "spots" or blobs. It is advantageous that the size of the route Movements are determined by the fineness of the gradation of the motion vectors. The application of blur operations such as the median method can also be used The two-dimensional summation images help interrupted signals as a unit detect.

More information about the objects in these directions can be obtained from a further analysis of the information in this direction. Further evaluated only those areas in which a "cross-section" appears to have emerged.

Claim 7 proposes the formation of regression lines within n + 1- dimensional subspaces that are identified by means of the n-dimensional projection images have been. This means that one of the original search direction, slightly different direction of movement can be identified, or suspected lines of movement can be verified. In the process according to Claim 7 or 8, it may be appropriate to determine the line or regression line the intensity-mapping properties in space when performing the regression how to treat a frequency of occurrence of objects in these places.

The formation of regression lines or straight lines is basically based on the description a dependent variable. Individual incorrect values far outside of the actual one The course of the curve can cause excessive changes in the calculated course during regression lead, so that this method with noisy signals and in the presence of several Curves along which the values are concentrated are not meaningful. The application this method is made possible here by the restriction to pre-selected subspaces. The room areas or regression lines remaining after this check can be entered with are more likely to be viewed as traces of objects.

At the same time, the downstream regression analysis heals e.g. T. the restriction that the Limiting the computing effort previously analyzed only a limited number of directions can be.

It is also possible to first determine certain directions or automatic pattern recognition To recognize areas with suspected object traces, then only the signals in them To take over areas of space in order to subsequently use them in a conventional manner to carry out a non-shifted addition of several parts of the image over time (claim 8). This would have a (two) dimensional representation of the original data in a conventional chronological order  Integration entailed, which would represent the largely unchanged traces that a Processor can analyze in detail and thereby also possible error detections of the Could correct algorithms. The advantage here is the elimination of the interference signals in Space areas away from the traces of interest through the upstream analysis. If necessary, the steps described in claim 8 can be repeated or further selection steps are interposed.

Otherwise, the "oblique" projection according to claim 1 and 4 makes them diffuse appearing movement lines concentrated to clear points or short lines. On the other hand, the spatial allocation corresponding to the view is partially correct lost. This disadvantage can result from longer observation periods a mixed representation can be balanced with shifted-added representation over short periods of time, each over a long period in unshifted Starting position can be added to an image. This means that only short periods of time in the "slanted" projection shown. The mapping begins after each of these time periods back to the original place. Images of objects that focus move exactly with the motion vector, within these time periods in one Point, so that a higher contrast of the "cross-sections" is achieved. The general movement becomes recognizable in the usual way, because in the next period the object with a its "normal" two-dimensional direction of travel will (claim 10).

Especially when displaying summed grayscale images in two dimensions Color values are assigned to the pixels, in particular according to the time of the Flashing of the point, or according to the direction for which this point is part of one Motion was detected. Such summaries can be common for all directions, for individual and are formed for part of the directions (claim 11).

Applications of claim 14 arise in particular in the case of radar images whose Resolution in the distance direction is more accurate than the lateral angle information, and at therefore by means of geodetic calculation based on two distances a more precise position determination is possible. Here is a two-dimensional Apply the search method from two observation points, with the distance as a spatial dimension and the time with which the speed in the axial direction each an observation point is determined. By limiting it to two dimensions possibly with a relatively fine gradation of the Projection directions (i.e. the implicitly tested axial velocity components) can be achieved, especially for the detection of weak signals by constant Speeds of moving objects can be used. Their image will change in the case of good ones Match their speed with the direction of projection on a small one Focus area. The information from both can then be used for a period of time Observation points can be summarized. By preprocessing with handover only the movement information of recognized objects instead of the transmission of complete image data, the required bandwidth for data transmission is also limited.

A spatial aggregation in different directions can be advantageous through additions parallel images that are uniformly shifted from each other in the way of representation achieved become. Claim 15 describes a memory organization with which an advantageous Calculation of the shifts in certain directions can be achieved. It must it is not a uniform shift in the original room; for example represents a shift within a representation of radar images in Polar coordinates an extension and rotation in the original space.

Further features result from the wording of the claims.  

benefits

The invention enables detection of traces even in cases where

• - a target in a single image is not yet with a recognizable pattern (signature) maps, and
• - does not show up sufficiently over time, even with fixed integration.

Other advantageous forms

In an expedient form, the effort is restricted to all procedures a limited number of directions or motion vectors is limited. This matches with a factually joint investigation of several similar directions that are not already more closely resemble the next motion vector.

A restriction that is not explicitly mentioned in the claims can also be expedient on starting points at certain intervals from each other, and the limitation of Sum formation in several directions of displacement to a lower resolution than in the original data to save computing time. A limitation of the Sum formation at a certain distance or temporal distance from the Starting points in order to capture movements that are not completely uniform. The The geometric blurring of the images to be evaluated may limit this orientate.

In the case of movements in an area shown in polar coordinates, this can Procedure also for linear movements in the original room due to displacement successive images by a fixed value in angular and in Distance direction can be applied as long as within a period of the addition the changes in angle are sufficiently small, and thus the differences to an acquisition stay low according to strictly linear movements. A move step would then be z. B. correspond to a simultaneous rotation and stretching of the following image, that is very different movements at different points in the coordinate system represent. As a special form of a shift, other distortions of the successive images in question, such as towards a target point.

The well-known interference suppression when capturing fixed objects by averaging several images represents a special case of the invention, in which in the Parallel traces can be considered. The detection of fixed objects could therefore in the described methods with which different directions or Motion vectors are considered to be included as a possible type of motion.

The detected movements can be saved as a list.

The movements determined over a period of time can also be used as standardized lines or Arrows can be represented in a two-dimensional image. This would particularly be the case with relatively short duration of the individual projection processes, which only have short movement sections analyze, a descriptive check enable whether this is part longer Are movements.

When analyzing projections, a mean value of the interference signals could be determined or a limit of the sum from which the summed up single images in the further representation "be taken over", and the single pictures taken over this border or Mean be reduced.

Blobs of different directional sums can be compared, and in the case of blobs A selection could then be made in the same place in several directions.  

To analyze accelerated movements, a different shift can be used successive area images.

It may be advantageous for data processing to only carry out such shifts or To consider motion vectors, the integer differences between Correspond to memory addresses or integer fractions.

Possibly. it can save computing time instead of adding directional sums for entire levels calculate the summation in different for selected starting points Make directions, and cancel if it is foreseeable that none of the criterion fulfilling total value is reached.

example

Drawing 1 describes a coordinate system which is only two-dimensional for clarification and is formed from a direction axis ( 1 ) and time ( 2 ). In it, an object moves at a constant speed along the line ( 3 ) and leaves the pattern ( 4 ) shown here interrupted in the period under consideration. At the same time, interference signals ( 5 ) can occur which do not have to differ from the pattern sought in a short period of time.

With conventional integration or addition of the signal occurring at the respective location over time, the image (7) is produced, which corresponds to a projection ( 6 ) parallel to the temporal dimension. The image of the pattern along its course has a strength similar to that of short interference signals of similar intensity. In contrast, a projection parallel to the direction of movement of the object results in a concentration of the image on a point ( 8 ) which stands out clearly from the images of the interference signals (not shown) and whose identification is independent of short interruptions in the original pattern ( 4 ) , Even when projecting at an acute angle to the direction of movement, there is a favorable concentration on a shorter, more intense image ( 9 ) compared to ( 7 ). With knowledge of the direction and duration of the projection, the length and course of this image already allow conclusions to be drawn about the actual course of movement. In order to obtain an illustrative image in the direction of the spatial dimension, the areas located between the boundary lines ( 10 ) can be selected in a subsequent processing after determining the size of the image 9 . Only the useful signal ( 4 ) and here an interference signal ( 11 ) lie in this area, while the other interference signals have been "filtered out".

The areas selected in this way could in turn be spatially constantly aggregated over time to form an improved image ( 7 ), which would then be less masked by interference signals. A linear regression could also take place according to claim 7, which would initially lead to an estimated value lying in the vicinity of the actual movement line. In the next step, the interference signal ( 11 ) would have to be separated out because of its distance from this estimated value, so that a further regression with the now exclusively remaining signals ( 4 ) could take place and would thus provide improved results.

Drawing two shows three surface sections with 5.5 points side by side, the three represent successive points in time, and those determined at the respective points Intensity values. In the example, the weak differences between the Intensities do not yet make a final distinction between points with useful and interference signals or in areas without reflections at the individual times; rather one seems everywhere "Noise" to be present.

Nine 5.5 fields are shown in the lower part of the table. The middle of them is Sum of the non-shifted values of the three times filled. For example, for the middle point is the value 12 as the sum of 3 (for t = 2), 2 (for t = 1) and 7 (for t = 0). Also no concise line of movement can be seen here.

The other eight 5.5 fields now represent the sums shifted laterally and / or horizontally by one field, i.e. the oblique projections in space-time. Due to the limited size of the cutouts, the total fields are only filled in three rows or columns. The nine values in the upper left field represent, for example, the sum of the areas shifted to the top left compared to t = 0. The number 22 results from the sum of 8 (top left in t = 2), 7 (second row and column in t = 1) and again 7 (average number in t = 0). Overall, a possible movement to the top left can be seen, since the number 22 protrudes from the remaining sums.

To the right of 7 in the middle of the matrix for (t = 0) is the value 8. After the Identification described above a possible trace to the "top left", the one Has a shift of one pixel per time period, could subsequent regression according to claim 7. This could be a bit more advanced Be included. Here, for. B. in (t = 0) to the right of the Center value 8 should be included. This would make it a little more inclined Regression lines lead because this point also estimates the actual Movement would contribute, or for (t = 0) as part of the image of the moving object would be interpreted. As a result of the regression, this would result in faster movement to the left as one unit of length per unit of time.

The example also shows that when applying the invention to the calculation result it is irrelevant whether the addition or aggregation by area or by certain Starting points are made from along displacement vectors.

Claims (17)

1. Method for recognizing structures in (n + 1) -dimensional spaces, in which their image is checked with a computer system for the occurrence of patterns or signatures, whereby

• - There are distinguishable properties at different points in the room or its image that can be represented quantitatively or in binary form,
• the characteristics of the properties at a certain point in the room sometimes do not allow a sufficiently certain statement as to whether this point is part of a pattern comprising a number of positions or of a signature sought, characterized by
• that the properties of the spatial points of n-dimensional subspaces with a limited number of displacement types or projection directions are aggregated or summed up to an n-dimensional, aggregated image for each displacement type or projection direction,
• - That an object that repeats itself in the n-dimensional subspaces with variation of the (n + 1) th dimension with a change or displacement corresponding to the respective type of displacement or direction of projection, is aggregated several times or reinforcing itself at the same point Images,
• - whereby the image of objects that only move similarly to the respective types of displacement or projection directions is also more concentrated or is projected onto a shorter distance or a smaller part of the n-dimensional space than would be the case if from the same locations of the n-dimensional spaces would be aggregated to the same points of the n-dimensional target space; the types of displacement are expressed between n-dimensional spaces or areas that are adjacent within the (n + 1) -dimensional space.

2. The method according to claim 1, where the n-dimensional subspaces differing in the (n + 1) th dimension by simple displacements are assigned to the target points of the n-dimensional image which are aggregated from the properties of those assigned by the shift Points. 3. The method of claim 1, wherein the assignment to target points by a distortion of the n-dimensional output spaces, the topology of which does not change becomes. 4. The method according to any one of claims 1 to 3 for the detection of elongated tracks ( 4 ), in which a movement in an n-dimensional space is treated like a track in an (n + 1) -dimensional space,
where time ( 2 ) forms the (n + 1) largest dimension, and
the types of displacement represent movements in the n-dimensional space,
in the aggregation, shifts ( 10 ) between each successive n-dimensional image or image area are determined such that they correspond to the approximately expected speed vectors of the objects sought. 5. The method according to claim 4
with n = 2, in which for the analysis of the two-dimensionally aggregated images,
that have been created by projecting or aggregating points that differ in spatial and temporal dimensions,
Routines for image processing of two-dimensional representations are used, 6. The method according to claim 5, in which such routines for image processing are used with which patterns or stains in the aggregated images are selected according to their dimensions, the selection criteria being based on

• - the size of the searched objects in the original pictures and
• - The permissible displacement of the searched objects in the aggregated image, which comes about through the difference between the speed of the object and the respective displacement vector, weighted with the duration of the aggregation.

7. The method according to any one of the preceding claims, in which

• - In aggregate n-dimensional images, which have been formed from images (n + 1) -dimensional spaces using methods according to the preceding claims, a frequent or more intensive occurrence of sought-after properties or patterns is sought and n-dimensional partial areas are selected there .
• the associated (n + 1) -dimensional spatial area is identified or selected for each selected partial area,
  and using only the data from this spatial area, a line is determined in the n + 1-dimensional space along which there is a particularly frequent or intensive occurrence,
• and in a subsequent further processing, those spatial points or parts of the spatial area selected in the previous step are separated which are not sufficiently close to this line and are therefore not considered in the next working step,
• - It is checked whether, after this separation and the resulting restriction of the observation to a subspace or a corresponding part of the data, there is still a sufficiently characteristic form of the properties, which indicates that the structures sought are present.

8. The method according to claim 7 in which several steps of selection and regression take place, each in Areas selected using the regression line determined in the previous step become. 9. The method according to any one of the preceding claims, in which

• - first, in aggregated n-dimensional images according to one of the preceding claims, an increased occurrence of sought-after properties or patterns is sought and (n-dimensional) partial areas are selected there,
• - the associated (n + 1) -dimensional spatial areas are identified or selected,
• - and using only the data from these spatial areas, a new aggregation takes place, but without displacement, to form an n-dimensional image.

10. The method according to any one of the preceding claims, in which

• - an overall examined period is divided into shorter periods,
• - for the shorter time periods, an increased occurrence of properties sought or corresponding patterns are first sought in aggregated n-dimensional images according to one of claims 1 to 8,
• the associated n-dimensional image areas are identified or selected,
• - And these image areas from several short periods of time are combined or aggregated in a likewise n-dimensional image that represents the entire period, but without spatial displacement of the partial images from different periods of time, so that longer-lasting movements, except for the shift within of the short time segments, in their basic spatial course over the entire period.

11. The method according to claim 9 or 10, where color values are assigned to the pixels in the summed images by using the addition or aggregation of the intensity value of a point with different points Weighting is added to the registers for different colors. 12. The method of claim 11, wherein the color after the time of flashing of the pixel is selected. 13. The method according to claim 11, wherein the color according to the type of displacement or Projection direction in which this point was recognized as part of a movement becomes. 14. The method according to any one of claims 1 to 11, in which at least two different observation locations are used to study the movements, from there lists of the observed objects are transmitted, and by comparing the location information given there gives more precise information about the movement of the object can be achieved. 15. The method according to any one of claims 1 to 14, in which the memory arrangement is such that a movement by a certain distance represented in one dimension by changing the memory addresses by a fixed value is, this value differs depending on the direction of displacement. 16. Devices that can be installed by installing suitable computer programs Process according to claims 1 to 15 are suitable. 17. Devices by computer hardware tailored to these functions are suitable for carrying out processes according to claims 1 to 15.