DE102015013943B4 - Testing a navigation system of a motor vehicle - Google Patents

Abstract

Method for testing a navigation system (1), wherein a test device (2): - in a test run (9), sensor data (5) describing a journey of a motor vehicle, fed into the navigation system (1) or within the navigation system (1) are simulated, and individual images (6) of an image sequence (4), which the navigation system (1) generates as a function of a specified navigation destination and the sensor data (5), are recorded, each individual image (6) being a combination (29) graphic key objects (11), and- at least one of the graphic key objects (11) is selected on the basis of configuration data and- each selected key object (11) is extracted in the individual images (6) and- from each extracted key object (11) to at least one predetermined object feature (30) a respective feature value (12) is determined, and - for each object feature (30) the determined feature values (12) of all captured individual images (6) are combined into a time signal (14), and it is detected whether at least one time signal (14) fulfills a predetermined error criterion (7), and if the error criterion (7) is fulfilled, a warning signal (8) is generated , characterized in that the test run (9) is repeated several times, and each time signal (14) of one of the test runs (9) as a reference signal (15) and each time signal (14) of another of the test runs (9) as a test signal (16) ) is used and the error criterion (7) includes that a difference (35) between at least one test signal (16) and the corresponding reference signal (15) is outside a predetermined tolerance range (36, 38).

Description

The invention relates to a method for testing a navigation system. The method is carried out by a test device which is also part of the invention.

The complexity of navigation systems in motor vehicles is increasing continuously. This is not only due to the number of available functions and the required graphic preparation of the navigation, but also to the variety of variants of the built-in navigation systems and their interaction with other devices and infotainment software components (infotainment system - information entertainment system). With increasing complexity, the probability that the navigation software contains errors also increases. It is important to find these errors before the software reaches the customer as a series version. Experience over the last few years shows that rare, complex errors can only be captured with hundreds or even thousands of hours of automated tests. In order to achieve the necessary test coverage and test time for each of the relevant navigation variants in an economically sensible manner, automated testing with little evaluation effort for the tester (human) is indispensable.

From the DE 10 2012 009 876 A1 A test method for navigation systems is known in which an image sequence generated by a navigation system for outputting navigation instructions is examined to determine which areas in the image sequence have been animated and which have remained unchanged as static or stationary areas. A movement model that simulates the animation is then configured exclusively on the basis of the moving image areas, which results in a more precise description of the movement compared to the use of the entire image sequence.

In the DE 10 2008 012 697 A1 describes a method for operating a navigation system in order to check whether current map information and current driving information match. A degree of the quality of the map information can be determined from this.

In the DE 10 2013 015 145 A1 describes a method for computer-aided testing and evaluation of the quality of data on a digital road map. The quality is assessed on the basis of quality criteria, which can include several sub-criteria and which can be selected depending on the requirements of the applications that are to use the road map.

From the U.S. 5,099,322 A a system for analyzing a video sequence is known in order to automatically detect scene changes in the video sequence. For this purpose, zones are observed within individual images, and if a zone changes in two successive individual images, a check is carried out to determine whether this change is greater than a threshold value. The comparison can be based on color, texture or brightness. A characteristic of a zone over time can also be analyzed.

In a scientific Technical article by Pimentel et al. (Pimentel, Marco AF et al., "A review of novelty detection", Elsevier - Signal Processing, Vol. 99, 2014, pp. 215-249, ISSN 0165-1684) A summary of the so-called "Novelty Detection", an area of machine learning, is available.

The invention is based on the task of automatically testing a navigation system.

The object is achieved by the subjects of the independent claims. Advantageous developments of the invention are given by the features of the dependent claims.

The invention provides a method for testing a navigation system. The method is carried out by a test device. In a test run of the navigation system, sensor data describing a journey of a motor vehicle are fed into the navigation system. The navigation system is therefore operated exactly as if it were installed in a motor vehicle and sensor data were received from the motor vehicle. Sensor data can be, for example, GPS data (GPS - Global Positioning System) and / or yaw rate data from a yaw rate sensor and / or a speed signal. The sensor data can be generated by means of a simulation or during a test drive of the navigation system. As an alternative to feeding in the sensor data, they can be simulated within the navigation system. A so-called demo mode with test scenarios can be used for this. "Demo mode" means that the navigation software of the navigation system generates the sensor data itself, based solely on an externally set starting point and destination. This saves having to supply the sensor data from outside. The vehicle drives “virtually” at a constant speed.

The navigation system then generates, in a known manner, a video sequence or animation or image sequence that can be displayed on a screen of the navigation system as a function of the sensor data and a predetermined navigation destination. The image sequence can for example, a symbol for the own vehicle and the road ahead. In the method it is now provided that individual images (frames) of this image sequence are recorded by the test device. The individual images can be captured, for example, by reading out a video signal or so-called frame grabbing or by filming the screen. It is important here that each individual image represents a combination of graphic key objects. Such a key object can, for example, be the symbol described for one's own vehicle or a road or a warning notice for a construction site. At least one of these graphic key objects is selected on the basis of configuration data. In other words, on the basis of the configuration data, a user sets in the test device which key object or which key objects are to be observed by the test device.

Each selected key object is extracted in the individual images. In other words, the selected key object is segmented in each individual image. It is thus determined which pixels (picture elements) of the individual image belong to the key object. A respective feature value is determined for at least one predetermined object feature from each extracted key object. An object feature or an object property is thus quantified in each individual image. For example, an object feature can be the area or size of the key object or a geometric orientation. This is expressed or described for each individual image as a respective feature value. For each object feature, the determined feature values of all captured individual images are then combined to form a time signal or feature profile. For example, a time signal is generated that describes the area or size of the key object over time. It is then detected whether the time signal or at least one of several time signals fulfills a predetermined error criterion. If the error criterion is met, a notification signal is generated.

The invention has the advantage that the reaction of the navigation system to the sensor data and the specified navigation destination is automatically checked by the test device and a user of the test device, i.e. H. a person only has to check the image sequence when the notification signal is generated, that is, when an unusual event in the image sequence has been recognized by the test device. Which events in the image sequence are classified as unusual can be set using the error criterion. The test device thus makes it possible to operate a navigation system for many hours or even for days without the image sequence generated by the navigation system actually having to be observed by a human observer. Using the generated information signal, that section of the image sequence can then actually be checked by the user for which the error criterion was met. A further OK signal can also be generated if the error criterion is not met.

The error criterion can for example state that the course of the time signal must lie within a predetermined value interval or tolerance range. If the time signal is outside the interval, the error criterion is met. For this purpose, the invention provides that no absolute value interval is used, but a comparison of the time signal with a reference signal is carried out. In the invention, the test run is repeated several times. A time signal or several time signals are then generated for one of the test runs, namely a reference sequence, depending on how many key objects and how many object features are observed per key object. Each time signal of this test run represents a reference signal. For another test run, namely a test sequence, a corresponding time signal is generated, which is then used as a test signal. The error criterion then includes that a difference between at least one test signal and the corresponding reference signal lies outside a predetermined tolerance range.

The test runs can be carried out with the same or with different sensor data. Even when using the same sensor data per test run, the navigation system reacts differently, depending on the utilization of other vehicle systems that are implemented with the same hardware. For example, in a multithreading processor system, the processing of the sensor data can take place differently in different test runs in the navigation system. Accordingly, different image sequences also result. For example, the display of the image sequence can be interrupted in the event of an unfavorable load on the processor system.

The invention also includes optional developments, the features of which result in additional advantages.

One aspect relates to the question of which object features are suitable for reliably detecting an error in the image sequence. A further development for this provides that an object feature is a scalar value, that is to say a “one-number feature”. For example, a number of pixels of the graphic Key object can be determined. This corresponds to the display area of the graphic key object. A scalar value has the advantage that the said time signal is determined as a time series of individual values. It can then be processed particularly efficiently by the test device. According to one development, an object feature can describe a dynamic or temporal property of the key object, for example a movement speed or a movement vector. This has the advantage that a relationship between successive individual images is taken into account. According to one development, an object feature can be a feature tuple made up of several individual features. As a result, the time signal expresses a multi-dimensional trajectory, so that the development of several individual features over time is described by a single time signal.

In a further development, an object feature is selected that is dependent on a navigation context. In this way, a respectively suitable object feature can be defined in advance for different sensor data and / or navigation destinations, so that a suitable object characteristic is specifically selected for different navigation situations. In addition or as an alternative to this, a correlation of two predetermined individual features can also describe as an object feature. In other words, an individual feature is not observed directly from the individual image, but a connection between two such individual features. These individual features can originate from the key object or also describe a relationship between an individual feature of the key object and an individual feature of another object. For example, a size ratio of two key objects can be described as an object feature.

A further development provides that the key object is extracted using a color and / or a graphic pattern. The extraction based on the color can be implemented particularly efficiently with low computational resources. A graphic pattern can be detected with a low-effort pattern recognition.

In order to be able to compare the test signal with the reference signal, a further development provides that the reference signal and / or the test signal is interpolated to a sampling rate specified for the sampling of the image sequence. This results in a synchronization of the test signal with the reference signal. Synchronization is therefore not necessary from the start. It is therefore possible to acquire individual images within the respective image sequence at different times for the different test runs. A hardware-in-the-loop test can thus be made possible in which the navigation system runs independently or asynchronously to the test device. If the described scalar value is used as the object feature, the interpolation is particularly robust. There is no need for a multidimensional, for example graphical, interpolation of an image.

In order to make the comparison between reference signals and test signals even more meaningful, a further development provides that the test signal is registered with the reference signal by means of a window-based comparison. Here, registration means that a time offset or time offset is set between the test signal and the reference signal on the basis of the window-based comparison. The window-based comparison can be, for example, a correlation or a sum of absolute difference values (SAD). The minimum correlation value or SAD value then indicates that the test signal and the reference signal have the greatest similarity, i.e. the time offset is optimal in that a recognized or detected difference between reference signal and test signal is caused solely by a difference in the image sequences and not due to an incorrect time offset.

A further development even makes it possible to automatically generate the error criterion for the comparison of test signal and reference signal. As a further development, a further reference signal is generated, for example from another section of the reference sequence or by running through the test run again. The tolerance range for the difference between the test signal and the corresponding reference signal is determined from the further reference signal (or the several further reference signals in the case of several object features) by means of a machine learning (ML) method. The so-called novelty detection method, for example, can be used as a method of machine learning. The machine learning uses the additional reference signal to identify which courses or values are typical for the reference signal, i. H. the expected behavior. This means that statistical outliers that indicate an error can then be recognized.

The following development has proven to be a particularly reliable automatic tolerance setting. It has the additional advantage that a user can use a graphic display to check whether the tolerance range has been set appropriately. In the development, the feature values of at least second reference signals are used or interpreted as coordinates of a data point. In other words, the feature values of the reference signals are used as coordinates for a given frame (or, in the case of interpolation, at a given point in time) interpreted. If, for example, two reference signals are used, one data point in a two-dimensional coordinate system results per point in time. If this is carried out for all times or sampling times of the reference signals, a point cloud results. From this point cloud, ie from the data points of the reference signals, the tolerance range is determined as a so-called decision boundary, for example by means of radial base functions (RBF - Radial Base Function). The decision boundary is the line that encloses the data points or at least most of the data points. The course or the shape of the decision limit can be adapted particularly flexibly by means of the radial basic functions described, as a result of which false alarms during error detection can be reduced.

The test device described for a navigation system of a motor vehicle also belongs to the invention. The test device is set up to carry out an embodiment of the method according to the invention. For this purpose, the test device can have a processor device that can be implemented, for example, on the basis of one or more microprocessors. The described components of the test device can thus each be implemented as program modules.

• 1 eine Skizze zu einem Testdurchlauf für ein Navigationssystem,
• 2 ein Flussschaudiagramm, welches verschiedene Ausführungsformen des erfindungsgemäßen Verfahrens veranschaulicht,
• 3 eine Skizze zur Veranschaulichung einer Extraktion mehrerer Schlüsselobjekte aus einem Einzelbild,
• 4 eine schematische Darstellung eines Zeitsignals eines Objektmerkmals eines der Schlüsselobjekte,
• 5 eine schematische Darstellung zur Veranschaulichung einer Registrierung des Zeitsignals mit einem Referenzsignal,
• 6 eine schematische Darstellung zur Veranschaulichung einer Überprüfung eines Fehlerkriteriums und
• 7 eine schematische Darstellung zur Veranschaulichung einer automatischen Festlegung des Fehlerkriteriums mittels einer Methode des maschinellen Lernens.

An exemplary embodiment of the invention is described below. This shows:

• 1 a sketch for a test run for a navigation system,
• 2 a flow chart illustrating various embodiments of the method according to the invention,
• 3 a sketch to illustrate an extraction of several key objects from a single image,
• 4th a schematic representation of a time signal of an object feature of one of the key objects,
• 5 a schematic representation to illustrate a registration of the time signal with a reference signal,
• 6 a schematic representation to illustrate a check of an error criterion and
• 7th a schematic representation to illustrate an automatic determination of the error criterion by means of a method of machine learning.

The exemplary embodiment explained below is a preferred embodiment of the invention. In the exemplary embodiment, the described components of the embodiment each represent individual features of the invention that are to be considered independently of one another, which also develop the invention independently of one another and are therefore to be regarded as part of the invention individually or in a combination other than the one shown. Furthermore, the described embodiment can also be supplemented by further features of the invention already described.

In the figures, functionally identical elements are each provided with the same reference symbols.

In 1 are a navigation system 1 and a test device 2 shown. The navigation system 1 can be part of an infotainment system. The navigation system 1 can be installed in a motor vehicle (not shown) or, for example, in a test laboratory outside a motor vehicle. The test device 2 can for example be implemented on the basis of a processor device, for example a personal computer. Using the test device 2 becomes the navigation system 1 then checked whether on a display device 3 of the navigation system 1 an image sequence 4th is generated error-free with navigation instructions. For this purpose, a trip with the motor vehicle is simulated. The navigation system receives from the journey 1 only with what sensor signals from the sensors of the motor vehicle to the navigation system 1 send or transmit. According to the test device 2 Sensor data 5 into the navigation system 1 fed in. This is referred to as what is known as sensor data replay (re-importing sensor data). Alternatively, the demo mode described can be used.

The test device 2 recorded meanwhile from the navigation system 1 Single images 6 the image sequence 4th and checked on the basis of the individual images 6 whether the image sequence 4th an error criterion 7th Fulfills. If the filter criterion 7th is fulfilled, is a notification signal 8th generated, which a user (not shown) of the test device 2 signals that the image sequence 4th contains an error. The user can then selectively use this image sequence 4th look again to see the error. If the image sequence does not contain an error here, another warning signal (“Image sequence OK”) can signal that the user has completed the image sequence 4th don't have to check. This saves the user having to look through every image sequence. He can concentrate on those image sequences that, according to the error criterion 7th contain an error.

Overall, this results in a test run 9 for the navigation system 10 . This Test run 9 can with the same sensor data 5 or repeated with other sensor data. Even when using the same sensor data 5 other individual images can be 6 result, which is related to the fact that each time there is a different load, ie different operating states in the navigation system 1 due to other processes in the navigation system 1 or in the infotainment system. These effects are known from the prior art.

2 illustrates how by means of the test device 2 different ways of checking the navigation system 1 can be realized. 2 shows how several test runs 9 can be carried out, with one test run representing a reference sequence REF and the remaining test runs 9 one test sequence TEST each. For every test run 9 are the individual images described 6 the image sequence 4th determined.

In the individual images 6 then one extraction at a time 10 of graphic key objects 11 carried out, which is explained in more detail below using 3 is described. To the graphic key objects 11 are then each for each individual image 6 Characteristic values 12 determined for different property features (see below the description in connection with 3 ). From the characteristic values 12 are then through an object analysis 13 Time signals 14th generated, a reference signal for the reference sequence REF 15th and a corresponding test signal for a respective test sequence TEST 16 every key object 11 and results for each property feature (see below 4th ).

If the reference sequence REF is not used, any test signal 16 in a store 17th and based on an initial test T1 can be tested by means of a threshold-based error detection without reference, what is in connection with 4th is explained in more detail.

The reference signal is saved 15th and the test signal 16 in a respective memory 18th can in a test T2 a threshold-based error detection with reference can be carried out. For a temporal alignment of the signals 15th , 16 can be an interpolation and registration 19th be provided what follows in connection with 5 and 6 is explained in more detail.

The described threshold-based comparison in the test T2 can be automated even further by adding for each reference signal 15th a feature distribution 20th is determined and based on the characteristics distribution 20th Decision limits 21st can be determined as a tolerance range. Decision limits can be determined by means of a method of machine learning ML. If you save these decision limits 21st in a store 22nd off and the test signals 16 in a store 23 so can in a test T3 a machine-learned error detection with reference can be carried out. This is further in connection with 7th described.

3 shows from the picture sequence 4th captured single images 6 . Every single picture 6 represents several key objects 11 represent, for example a vehicle symbol 24 for the own vehicle, a planned route 25th , a traffic flow indicator 26th , a course of the road 27 . Usually these are key objects 11 shown with different colors. By extraction 10 can the key objects 11 segmented or separated or individually and independently recognized. For example, the display color can be used as an extraction criterion or recognition criterion for this purpose. 3 shows how by extraction 10 the route 25th , the traffic flow indicator 26th and the course of the road 27 can be separated. In a synopsis 28 is once again illustrated how the combination 29 of the key objects 11 essentially the single image again 6 results. To every key object 11 can now for every single image 6 one characteristic value each 12 be determined. In the illustrated example, for example, the number N of pixels with which the respective key object 11 is shown, are counted.

4th illustrates how this reference feature 30th (for example number N of pixels) by combining all feature values 12 of the property 30th to a time signal 14th are combined that over time t the change or development of the property 30th describes. 4th illustrates the passage of time 14th for the test signal 16 .

The failure criterion 7th can only for the test T1 for example a threshold value interval 31 specify in which the test signal 16 must lie. Becomes the failure criterion 7th violated, the time signal is in this case 16 outside the threshold interval 31 so for this image defect 32 ' the warning signal 8th is produced. The warning signal 8th can also indicate at what point in time in the image sequence 4th the image defect 32 ' was detected.

5 illustrates how two time signals 14th , namely a reference signal 15th and a test signal 16 can be registered with each other. This is done first by means of re-sampling or interpolation 19th ( 2 ) every time signal 14th adapted to a predefined sampling rate so that feature values 12 recorded at different times, with one each corresponding characteristic value 12 ' can be compared at the same time.

5 also illustrates how using a window-based comparison 32 by moving 33 of the test signal 16 compared to the reference signal 15th an offset value 34 can be determined by which the test signal 16 compared to the reference signal 15th must be shifted over the time t, so that, apart from image errors, there is an optimal overlap of the two time signals 14th results. For example, the described sum of the absolute differences SAD can be calculated as a comparison measure for each time shift value.

6 then illustrates how by subtracting the reference signal 15th and the test signal 16 a difference signal 35 can be generated, which thus represents the difference value dN of the number of pixels in the illustrated example. In the test T2 can now be used as an error criterion 7th again a value interval 36 be defined, which indicates that difference signal 35 within the range of values 36 must lie so that there is no error. In addition to the image defect 32 ' , which is also used for the absolute value analysis in the test T1 was recognized, can now be compared with the reference signal 15th a second image defect 37 can be detected in the illustrated example.

7th illustrates how for the test T3 first an error criterion using machine learning 7th in the form of a decision limit 38 can be determined. Two reference signals are used for this 15th , 15 ' for two key objects 11 determined. For example, it is assumed below that the two key objects 11 to the flow of traffic 26th ("Speed &flow") and the course of the road 27 acts. For this reason, this example is referred to below as the “speed and flow example”. As a property feature 30th the number N of displayed pixels is evaluated again in the example. Here every reference signal 15th , 15 ' considered individually for each point in time, so that the individual signal values of the two reference signals 15th , 15 ' be applied. By combining a respective signal value of the reference signal 15th and the reference signal 15 ' at a given point in time there is one data point 39 , of which in 7th for the sake of clarity, only some are provided with a reference number. By means of the machine learning ML, the decision limit can now be established, for example by applying radial basis functions 38 determine which most or all of the data points 39 includes. By setting a machine learning parameter ML known per se, alternative limit profiles can be created 40 for the decision limit 38 can be specified, which means that the error rate can be set using the parameter.

In the test T3 can now use corresponding data points 41 a test sequence TEST can be determined. Are these data points 41 outside the decision limit 38 , this also creates an image defect 42 recognized in the test sequence TEST.

The embodiments of the method according to the invention that are specifically described using the exemplary embodiment can be modified in order to test the navigation system 1 adapt to different test conditions. Further information on the modification is given below.

The concept presented is based on the repeated recording of the navigation screen content with the same route. In addition to the well-known demo mode of the navigation, this is particularly possible thanks to the recently available technology of the sensor data replay: the sensor data from a real trip lasting several hours are re-imported into the navigation in the laboratory. The recording of the first run is referred to below as the reference sequence, the recordings of all subsequent recordings as test sequences.

1. 1. Berechnung von Schlüsselobjekt-Merkmalsverläufen
2. 2. Synchronisierung der Sequenzen, sowie
3. 3. Fehlererkennung mit/ohne maschinellem Lernen

The process basically comprises three components:

1. 1. Calculation of key object characteristic courses
2. 2. Synchronizing the sequences as well
3. 3. Error detection with / without machine learning

In combination with each other, these three components allow a reference-based, automated testing of the navigation, which eliminates or significantly reduces the four disadvantages described. In addition, rare, as yet unknown navigation errors can be identified automatically without explicitly modeling the error. 2 shows the basic process chain of the presented concept. Depending on the decision as to whether error detection should take place with / without a reference sequence and with / without machine learning, different procedures apply, which are indicated with the corresponding arrows.

The basis is the definition of elementary navigation objects, called key objects here. These key objects allow a simple characterization of the behavior of important navigation elements as well as a waiver of traditional pattern recognition (= "pattern matching", comparison of texture contents). 3 illustrates this with an example. Here are the objects Route, Speed & Flow as well as roads were selected as key objects. Each of the selected key objects is recognized and extracted based on the associated color in the frame. Then a characterizing key object feature is calculated for each key object (= number), for example the number N of pixels of this object. The sequence thus results in a key object characteristic curve (= curve or time signal) for each key object, which reliably maps the behavior of the key object and makes it comparable with an error-free reference sequence.

1. 1. Definition zeitlicher Schlüsselobjekt-Merkmale, beispielsweise von affinen Bewegungsparametersätzen zwischen Einzelbildern oder Frames,
2. 2. Extrahierung der Schlüsselobjekte nicht aufgrund der Farbe, sondern aufgrund (einfacher) Mustererkennungsalgorithmen,
3. 3. Berechnung eines Schlüsselobjekt-Merkmalstupels, also eines mehrdimensionalen Merkmals (siehe Bewegungsparametersatz),
4. 4. Einbeziehung von Kontexten und Korrelationen bei der Berechnung und Verarbeitung von Schlüsselobjekt-Merkmalen und Schlüsselobjekt-Merkmalsverläufen (z.B. Einbeziehung von Bewegungsparametersätzen bei der Threshold- oder ML-basierten Fehlererkennung, Threshold - Schwellwert).

It should be noted that this concept can be adapted / expanded as required. Examples of a possible adaptation / expansion would be:

1. 1. Definition of temporal key object features, for example of affine movement parameter sets between individual images or frames,
2. 2. Extraction of the key objects not based on color, but based on (simple) pattern recognition algorithms,
3. 3. Calculation of a key object feature tuple, i.e. a multi-dimensional feature (see movement parameter set),
4. 4. Inclusion of contexts and correlations in the calculation and processing of key object features and key object feature progressions (eg inclusion of movement parameter sets in the threshold or ML-based error detection, threshold value).

The availability of a reference sequence ( 2 , left) also enables the use of machine learning (ML) methods. One example of this is novelty detection, a one-class classification method that is closely related to statistical outlier detection. As part of tests, the novelty detection was experimentally combined with the key object feature calculation and adapted in such a way that it is possible to learn the expected behavior of certain key object features using the reference sequence.

This enables any number of test repetitions (= test sequences) to be automatically entered into the classifier learned in this way and rare errors to be identified on the basis of possible "unexpected" behavior. In comparison with threshold-based or threshold-based error detection mechanisms, the evaluation by humans is additionally simplified, because the computer has learned the expected behavior of the key objects, maps this knowledge using classifiers and thus only unusual events to the tester from hundreds of hours of test repetitions ( Human). This basically corresponds to a reference-based preparation and filtering of existing key object information.

In combination with each other, the three components allow

1. 1. Calculation of key object characteristic courses
2. 2. Synchronizing the sequences as well
3. 3. Error detection with / without machine learning a test of the navigation in an automated form. In summary, the idea presented has the following advantages:

Little modeling effort

The need to model error behavior (explicitly or implicitly) is largely eliminated, since a reference sequence is available for a computer-aided comparison and the comparison can be carried out reliably using the synchronization presented.

Reduced computational complexity

The computing effort for complex pattern recognition is eliminated, the calculation can be carried out in almost real time. The majority of the necessary effort consists of logical indexing, curve interpolation and, if desired, learning the decision boundary (once).

Reduced evaluation effort

The mapping of elementary key objects of the navigation as simple curve progressions as well as their difference value formation after synchronization allow for the first time a temporal processing of the image content of entire test runs in plot form. Common evaluation software tools such as EXAM do not support this: the sequence must always be checked with the eye in its entire length in a video player or single-image browser ("Picture Browser"). The representation of the navigation image content in the form of a curve enables the tester (human) to evaluate the respective test run quickly and easily.

Use of reference information

The described concept of the features and feature profiles of key objects, combined with the synchronization presented, now makes it possible for the first time to carry out a computer-aided comparison against an error-free reference sequence with little effort. Of the This gives the tester the opportunity to visually check the first run (= reference sequence REF) for defects and then to repeat the test as often as required with minimal evaluation effort (automated test of the test sequences TEST).

Detection of rare and unknown errors

The usability of a reference sequence can be interpreted as implicit modeling of unknown errors (or as explicit modeling of the expected behavior). This in turn makes it possible to identify unknown errors based on their unexpected key object behavior without creating and maintaining implicit models with massive effort. The identification of rare, unknown errors is a major challenge in the area of automated navigation testing.

Machine learning ML

The described concept of the features or feature profiles of key objects enables expected properties or expected behavior to be interpreted as feature tuples. In machine learning, these feature tuples (also called "features") form the basis for calculating a descriptive model (= training a model). The model (often a set of parameters of a “kernel” such as the RBF kernel) can then be used to classify features of unknown classes. The concept presented thus opens up the field of machine learning for future approaches.

Temporal characteristics, calculation of a context

The presented concept of the features or feature profiles of key objects currently uses "local features" (-> number of pixels from extracted key objects). “Temporal characteristics” such as movement between frames can also be considered in the future. It is also possible to introduce a “context”, that is, error detection on the basis of the recent past of the characteristic curve under consideration and in correlation with other characteristic curves. It is likely that an automatic “learning” of these networks (Bayesian networks) using the reference sequence represents a simple solution for an uncomplicated, low-maintenance testing of the navigation.

The technical implementation of the presented idea is described in principle below.

Calculation of key object characteristic courses

Instead of searching for texture similarities (pattern matching, pattern recognition), elementary navigation elements are identified using color-based extraction. These elementary objects are referred to below as key objects. In the following, further important terms are also key object characteristics and key object characteristics history.

The key objects can be selected differently depending on the objective of the automated tests. Examples of key objects are streets, routes, speed & flow, vehicle symbols or others (see example 3 ). Use is made of the fact that these key objects are typically monochrome (for the purpose of clear, graphic preparation of the navigation). With the help of the color characteristic, the key object can be extracted uniquely as a collection of pixels. The number of pixels gives the key object feature. Other key object features than the pure number of pixels are also conceivable. However, it is important for subsequent synchronization and error detection that the key object characteristic corresponds to a single number per frame. This ensures that the behavior of a key object can be easily characterized using a simple but representative curve shape for the entire sequence under consideration. A key object trait history is in 4th shown as an example. In addition, this convention supports graphic processing and thus evaluation by the tester (human). It has been shown that a simplification to a one-number feature represents an optimal trade-off between unambiguous characterization and manageability of the feature profiles.

The correct functioning of the individual key objects of the navigation can be specifically deduced from these courses (more on this under Error detection with / without machine learning). They are also essential for eliminating the disadvantages of modeling effort and computational complexity: they implicitly model the expected behavior, the complexity is limited to a logical indexing and a feature calculation (here: sum of the key object pixels). The key object characteristic curves also create the basic requirements for the usability of a reference sequence, which considerably simplifies the search for rare errors.

Synchronization of the sequences

1. 1. Interpolationsschritt: Die Schlüsselobjekt-Merkmale aller Frames einer Sequenz stellen eine Serie an Einzelwerten dar (-> Merkmalsverlauf). Diese Einzelwerte sind als Abtastwerte zu gewissen Zeitpunkten anzusehen. Die Abtastung besitzt eine variierende Abtastrate. Es ist daher nötig, diese unregelmäßige Abtastung so zu interpolieren, dass zu jedem regulären Zeitschritt (z.B. jede Sekunde) ein Abtastwert (=Schlüsselobjekt-Merkmal) existiert.
2. 2. Registrierungsschritt: Der Registrierungsschritt beinhaltet einen fensterbasierten Vergleich der interpolierten Merkmalsverläufe von Referenz-Sequenz und Test-Sequenz. Dabei wird für jede Position der SAD (Summe der Absoluten Differenzen) der Schlüsselobjekt-Merkmale berechnet und jene Position für die Registrierung verwendet, die den minimalen SAD aufweist.

The synchronization component is essential to the key object characteristic curves of a To be able to automatically compare test sequence with an already tested, error-free reference sequence. This reference comparison is extremely interesting because it represents an effective tool for the detection of previously unknown errors (explicit modeling of the error not possible, implicit modeling associated with a lot of effort). This reference comparison can only be carried out if approximate synchronicity of the two time axes is ensured for the time segment to be compared. In view of the varying frame rates, the asynchronous, internal clocks of the frame grabbers and the load on the test bench PCs, this is not trivial. Synchronization consists of two simple steps:

1. 1st interpolation step: The key object features of all frames in a sequence represent a series of individual values (-> feature profile). These individual values are to be viewed as samples at certain times. The sampling has a varying sampling rate. It is therefore necessary to interpolate this irregular sampling in such a way that a sampling value (= key object feature) exists for every regular time step (eg every second).
2. 2. Registration step: The registration step contains a window-based comparison of the interpolated characteristic curves of the reference sequence and the test sequence. The key object characteristics are calculated for each position of the SAD (sum of the absolute differences) and that position is used for the registration that has the minimum SAD.

By means of this synchronization, a section in the test sequence can be clearly assigned to the corresponding section in the reference sequence. The synchronization makes a reliable, meaningful comparison of two sequences possible, even with long recording times.

Error detection with / without machine learning

1. 1. Threshold-basierte Fehlererkennung, ohne Referenz (Test T1)
2. 2. Threshold-basierte Fehlererkennung, mit Referenz (Test T2)
3. 3. Machine-Learning-basierte Fehlererkennung, mit Referenz (Test T3)

The purpose of error detection is to identify one or more defective frames (in series or distributed over the sequence) as defective and to pass them on to the tester (human) for the final assessment. A high number of incorrectly reported errors (false positives, error does not exist in reality) must be avoided, as this would otherwise make the final evaluation by the tester considerably more difficult. In principle, three different approaches for automated error detection using the method described in this invention disclosure are possible (cf. 2 ):

1. 1. Threshold-based error detection, without reference (test T1 )
2. 2. Threshold-based error detection, with reference (test T2 )
3. 3. Machine learning-based error detection, with reference (test T3 )

T1: Threshold-based error detection, without reference

This is the simplest approach, but with a significant number of false positives, and only suitable for a few key objects. An algorithm checks the maximum / minimum values of a characteristic curve and decides whether they exceed / fall below a defined threshold. The jump behavior of the feature profile can also be checked (via differences, e.g. interesting with a blue route or road network). 4th shows an example. It has also been shown that weighting the jump behavior with the respective sampling interval can significantly reduce the number of false positives.

T2: Threshold-based error detection, with reference

By means of synchronization and reference sequence comparison, there is considerably more information about the expected key object characteristic curve than with a referenceless comparison. For each key object, a precise calculation of the difference between the reference and test features is possible. For some key objects, it makes sense to smooth the difference curve (e.g. convolution with a Gaussian curve) before a subsequent threshold calculation.

T3: Machine learning based error detection, with reference

It has been shown that certain key object features are suitable for an evaluation using statistical classification methods. It is thus possible to apply machine learning (ML) approaches to the calculated key object features and key object feature courses. To investigate this possibility, the so-called novelty detection method was applied to the features of Speed & Flow and Street Network.

It should be noted that more than two key object features can also be learned in terms of their correlation. The higher-dimensional feature space, however, makes simple visualization of the results difficult.

The basic procedure can be based on the above speed and flow example ( 7th ) in three steps:

Training using a reference sequence

Using the reference sequence, for example, the correlation of “normal” speed & flow characteristics to street network characteristics (SF-vs-SN) is learned. Each processed frame results in one data point 39 ( 7th ). Using these data points 39 a decision boundary is created using an RBF kernel 38 calculated. There is thus a mathematical description of the behavior to be expected. Outside the Decision Boundary 38 data points (= frames) are classified as faulty.

Processing of a test sequence

This is illustrated by two examples. Example 1: Processing an error-free test sequence. As expected, the SF-vs-SN data points are embedded in the area of error-free SF-vs-SN data points, ie within the decision boundary 38 . Example 2: Processing of a faulty test sequence (disturbed Speed & Flow behavior). The SF-vs-SN data points 42 of the disturbed frames are outside the expected distribution, ie outside the decision boundary 38 .

Error detection using Decision Boundary 38

The error detection 42 can thus by means of the learned Decision Boundary 38 respectively. Since the behavior of the selected key objects was learned on the basis of the reference sequence and is mapped using the decision boundary, automated error detection is thus possible for each incoming navigation frame.

At the in step 1 learned Decision Boundary 38 It is important to choose the Novelty Detection parameters necessary for the calculation so that the most comprehensive possible inclusion of all data points of the error-free reference sequence is guaranteed. This can be done using the known parameter “v” (“Nu”). This parameter in the area 0 to 1 corresponds to the ratio of the training errors to the total number of training data points and acts as the upper limit for the maximum permitted training errors. A v <= 0.01 has proven to be completely sufficient for the tested navigation sequences ( 7th ).

Overall, the example shows how navigation errors can be recognized by means of key object analysis and reference sequence comparison using the invention.

Claims (9)

Method for testing a navigation system (1), wherein a test device (2): - in a test run (9), sensor data (5) describing a journey of a motor vehicle, fed into the navigation system (1) or within the navigation system (1) are simulated, and - individual images (6) of an image sequence (4), which the navigation system (1) generates as a function of a specified navigation destination and the sensor data (5), are recorded, each individual image (6) being a combination (29) graphic key objects (11), and - at least one of the graphic key objects (11) is selected on the basis of configuration data and - each selected key object (11) is extracted in the individual images (6) and - from each extracted key object (11) to at least one predetermined object feature (30) a respective feature value (12) is determined, and - for each object feature (30) the determined feature values (12) of all recorded individual b ilder (6) are combined into a time signal (14), and - it is detected whether at least one time signal (14) fulfills a predetermined error criterion (7), and - if the error criterion (7) is fulfilled, a warning signal (8) is generated is, characterized in that the test run (9) is repeated several times, and each time signal (14) of one of the test runs (9) as a reference signal (15) and each time signal (14) of another of the test runs (9) as a test signal ( 16) is used and the error criterion (7) includes that a difference (35) between at least one test signal (16) and the corresponding reference signal (15) is outside a predetermined tolerance range (36, 38). Procedure according to Claim 1 , wherein the at least one object feature (30) comprises: - a scalar value, in particular a number of pixels (N), and / or - a dynamic property and / or - a feature tuple from several individual features. Method according to one of the preceding claims, wherein the at least one object feature (11) is dependent on a navigation context and / or describes a correlation of second predetermined individual features. Method according to one of the preceding claims, wherein the extraction (10) of the at least one key object (11) takes place on the basis of a color and / or a graphic pattern. Method according to one of the preceding claims, wherein the reference signal (15) and / or the Test signal (16) is interpolated to a sampling rate specified for sampling the image sequence (4). Method according to one of the preceding claims, wherein the test signal (16) is registered with the reference signal (15) by means of a window-based comparison (32). Method according to one of the preceding claims, wherein a further reference signal (15 ') is generated and the tolerance range (38) is determined from the further reference signal (15') by means of a method of machine learning (ML). Procedure according to Claim 7 , the respective feature values of at least two reference signals (15, 15 ') being used as coordinates of a data point (39) and, from the data points (39) of the reference signals (15, 15') using radial basis functions, the tolerance range (38) as a decision limit (38 ) which includes most or all of the data points (39) is determined. Test device (2) for a navigation system (1) of a motor vehicle, the test device (2) being set up to carry out a method according to one of the preceding claims.

Images