Computer implemented method and device for anomaly detection

A device and a computer implemented method of anomaly detection, including processing a digital representation of a signal or image with a wavelet decomposition to generate a first, second, and third plurality of decomposed representations, processing a first decomposed representation of the third plurality of decomposed representations with a first generative model to determine a first likelihood, processing a second decomposed representation of the third plurality of decomposed representations with a second generative model to determine a second likelihood, processing a second decomposed representation of the second plurality of decomposed representations with a third generative model to determine a third likelihood, processing a second decomposed representation of the first plurality of decomposed representations with a fourth generative model to determine a fourth likelihood, detecting an anomaly when at least one of the first likelihood, the second likelihood, the third likelihood and the fourth likelihood meets a criterium for anomaly detection.

CROSS REFERENCE

The present application claims the benefit under 35 U.S.C. § 119 of European Patent Application No. EP 20153553.1 filed on Jan. 24, 2020, which is expressly incorporated herein by reference in its entirety.

FIELD

The present invention relates to a method and device for anomaly detection.

BACKGROUND INFORMATION

Realistic real world natural signals can be captured by sensors and represented as digital representations thereof. Visual signals can be represented by digital images. Audible signals can be represented by digital audio or as images. A robust anomaly detection for digital representation of realistic natural signals like digital images or digital audio requires a method that works robustly across diverse settings.

SUMMARY

In accordance with example embodiments of the present invention, a robust anomaly detection achieved.

In accordance with an example embodiment of the present invention, the method of anomaly detection includes processing a digital representation of a signal or image with a wavelet decomposition to generate a first plurality of decomposed representations, processing a first decomposed representation of the first plurality of decomposed representations with a wavelet decomposition to generate a second plurality of decomposed representations, processing a first decomposed representation of the second plurality of decomposed representations with a wavelet decomposition to generate a third plurality of decomposed representations, processing a first decomposed representation of the third plurality of decomposed representations with a first generative model to determine a first likelihood, processing at least one second decomposed representation of the third plurality of decomposed representations with a second generative model to determine a second likelihood, processing at least one second decomposed representation of the second plurality of decomposed representations with a third generative model to determine a third likelihood, processing at least one second decomposed representation of the first plurality of decomposed representations with a fourth generative model to determine a fourth likelihood, detecting an anomaly when at least one of the first likelihood, the second likelihood, the third likelihood and the fourth likelihood meets a criterion for anomaly detection. This wavelet decomposition produces wavelet coefficients in three levels of scale. Generally a wavelet decomposition produces as many scales of wavelet coefficients an input resolution of the digital representation allows. For an input resolution of 8×8 this means log 2(8)=3 wavelet coefficient scales can be produced. For an input resolution of 32×32, log 2(32)=5 wavelet coefficient scales are available. Accordingly, not all of the available wavelet coefficient scales are used, when the wavelet decomposition produces wavelet coefficients in three levels of scale. The wavelet decomposition produces in one example images of different resolution. The first decomposed representation at each level corresponds to a digital image that is further decomposed for the next level of scale. Using a Haar Wavelet at least one second decomposed representations at each level correspond to a digital image defined by a horizontal, a vertical or a diagonal difference between pixels of a the digital representation or the first decomposed representation of a previous level of scale. Haar Wavelet is one example, more generally, other wavelet decompositions, such as Meyer-Wavelet or Morlet-Wavelet can be used as well. The same wavelet decomposition is used at all levels. The wavelet coefficients are analyzed independently in four models for detecting an anomaly if one of the models produces a likelihood that indicates an anomaly. The wavelet coefficients in each of the decompositions have a different resolution. Hence the accuracy and reliability may be significantly improved compared to analogy detection.

Preferably, the second generative model is conditioned on the first decomposed representation of the third plurality of decomposed representations and/or that the third generative model is either conditioned on the first decomposed representation of the third plurality of decomposed representations and on the at least one second decomposed representation of the third plurality of decomposed representations or is conditioned on a reconstructed representation that is reconstructed from the first decomposed representation of the third plurality of decomposed representations and the at least one second decomposed representation by inverse wavelet decomposition, and/or that the fourth generative model is either conditioned on the first decomposed representation of the third plurality of decomposed representations, the at least one second decomposed representation of the third plurality of decomposed representations and the at least one second decomposed representation of the second plurality of decomposed representations or is conditioned on a reconstructed representation that is reconstructed from the first decomposed representation of the third plurality of decomposed representations, the at least one second decomposed representation of the third plurality of decomposed representations and/or the at least one second decomposed representation of the second plurality of decomposed representations by at least one inverse wavelet decomposition. The conditioning improves the accuracy further.

In one aspect of the present invention, the criterion is met, when at least one of the first likelihood, the second likelihood, the third likelihood and the fourth likelihood is below a threshold. The likelihood for a normal image is assumed to be in a predetermined range. If the likelihood is outside the range, an abnormal image is detected.

In accordance with an example embodiment of the present invention, the method may include comparing the first likelihood to a first threshold, comparing the second likelihood to a second threshold, comparing the third likelihood to a third threshold, comparing the fourth likelihood to a fourth threshold. The threshold may be adjustable. Thus, a normal or abnormal image is easily detectable.

The threshold test may be performed independently and an anomaly may be detected if k likelihoods of a total of K likelihoods signify anomaly. For k=1 an anomaly is detected, in case one likelihood is out of a predefined normal range.

In one aspect of the present invention, the method comprises determining a sum depending on the first likelihood, the second likelihood, the third likelihood, and the fourth likelihood, comparing the sum to a threshold in a comparison and depending on the result of the comparison detecting the anomaly or not. Thus a normal or a abnormal signal or image is detected depending on the result of the comparison. This means, the anomaly is detected by evaluating whether the first likelihood, the second likelihood, the third likelihood and the forth likelihood together meet a criterion. The sum may be determined from the likelihoods directly. A variant for the sum may be a sum of likelihoods after a division of each likelihood by a number of dimensions of the scale that the likelihood is determined for. This way each scale contributes equally to the likelihood. This means higher-resolution scales with more dimensions will contribute more to the sum.

Preferable, a pixel defines at least one intensity value, wherein the digital representation is defined by a set of said pixel, wherein the method comprises determining the first decomposed representation of the first plurality of decomposed representations depending on an average intensity value, wherein the average intensity value is determined by averaging intensity values of non-overlapping sub-sets of the set of pixel, and determining at least one of the at least one second decomposed representations depending on a difference between the intensity values of at least two different of said pixel. The pixels in this aspect are grouped in blocks of pixels for averaging, e.g. in a Haar wavelet decomposition for determining the first decomposed representation at this level.

In another aspect of the present invention, a pixel defines at least one intensity value, wherein the first decomposed representation of the first plurality of decomposed representations is defined by a set of said pixel, wherein the method comprises determining the first decomposed representation of the second plurality of decomposed representations depending on an average intensity value, wherein the average intensity value is determined by averaging intensity values of non-overlapping sub-sets of the set of pixel, and determining the at least one second decomposed representations of the second plurality of decomposed representations depending on a difference between the intensity values of at least two different of said pixel. The pixels in this aspect are also grouped in blocks of pixels for averaging, e.g. in a Haar wavelet decomposition, for determining the first decomposed representation at this level.

In another aspect of the present invention, a pixel defines at least one intensity value, wherein the first decomposed representation of the second plurality of decomposed representations is defined by a set of said pixel, wherein the method comprises determining the first decomposed representation of the third plurality of decomposed representations depending on an average intensity value, wherein the average intensity value is determined by averaging intensity values of non-overlapping sub-sets of the set of pixel, and determining the at least one second decomposed representations of the third plurality of decomposed representations depending on a difference between the intensity values of at least two different of said pixel. The pixels in this aspect are also grouped in blocks of pixels for averaging, e.g. in a Haar wavelet decomposition, for determining the first decomposed representation at this level.

The digital representation may comprise grey scale or color channels, wherein the method comprises processing a single channel separately.

In accordance with an example embodiment of the present invention, the method may comprise processing a digital training representation of a signal or image with the wavelet decomposition to generate a first plurality of decomposed training representations, processing a first decomposed training representation of the first plurality of decomposed training representations with the wavelet decomposition to generate a second plurality of decomposed training representations, processing a first decomposed training representation of the second plurality of decomposed training representations with the wavelet decomposition to generate a third plurality of decomposed training representations, determining first training data for the first model comprising the first decomposed training representation of the third plurality of decomposed training representations, determining second training data for the second model comprising the at least one second decomposed training representation of the third plurality of decomposed training representations, determining third training data for the third model comprising the at least one second decomposed training representation of the second plurality of decomposed training representations, determining fourth training data for the fourth model comprising the at least one second decomposed training representation of the first plurality of decomposed training representations. Thus, separate generative models are trained such as an invertible neural network or an autoregressive neural network, for each resolution.

Preferably, the method comprises training the first generative model with the first training data to determine the first likelihood, training the second generative model with the second training data to determine the second likelihood, training the third generative model with the third training data to determine the third likelihood, and/or training the fourth generative model with the fourth training data to determine the fourth likelihood. This distributional method trains each generative model with training data. The generative model learns the distribution of the training data. Anomalous data is then expected to have lower likelihoods than normal data.

In accordance with an example embodiment of the present invention, a device for anomaly detection is provided, wherein the device comprises input for a digital representation, an output for outputting a result of the anomaly detection and a processing arrangement, adapted to execute the steps of the method according to an example embodiment of the present invention.

Further advantageous aspects of the present invention can be derived from the following description and the figures.

DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS

FIG.1schematically depicts an example device100for anomaly detection. The device100comprises an input102for a digital representation302, an output104for outputting a result of the anomaly detection and a processing arrangement106adapted to execute the steps of the method described below referencingFIG.2. The input102may be adapted to receive signals or to provide digital representations. The output may be adapted to output a result of the anomaly detection in a graphical or audible user interface or to send the result of the anomaly detection via a communication path.

The processing arrangement106may comprise a processor106aand a storage106bfor storing instructions, digital representations and/or an output of the anomaly detection.

An example is described below using a digital image as digital representation. However, other input such as audio data may be processed alike. A pixel defines in the example at least one intensity value. The digital representation is defined by a set of said pixels.

The example method uses wavelet decomposition. Wavelets are used in a signal decomposition technique that uses wavelet functions that are translated and scaled across the input to compute wavelet coefficients at different scales and translations or positions.

The method uses generative models. Generative models here mean models that assign likelihoods to data points such that the likelihoods form a proper probability distribution:
∫x∈Ωpθ(x)=1
wherein Ω is an input domain and θ are parameters of the generative model.

Examples for a generative model are variation auto encoders, invertible neural networks, normalizing flows or autoregressive methods. They can be trained to maximize a likelihood of a training dataset, typically in log-space:

maxθ⁢𝔼x∼Ptrain_data⁢log⁢pθ(x)
wherein Ptrain_datais a training data distribution.

Likelihoods obtained from these generative models are used to detect out-of-distribution data, since out-of-distribution data should have low likelihoods. This means, one assumes that
x˜Ptrain_datalogpθ(x)≈>>x˜Pdifferent_datalogpθ(x)
wherein Ptrain_datais the underlying distribution of training data samples that were drawn from, e.g. a distribution of 28×28 grayscale images of handwritten digits for the MNIST data set if you train on MNIST, and Pdifferent_datais some other distribution, e.g., the distribution of 28×28 grayscale images of clothes for FashionMNIST.

To improve the accuracy and reliability of the anomaly detection, the method comprises decomposing signals of a training dataset using Wavelets into different resolution wavelet coefficients, training a separate generative model, such as an invertible neural network or an autoregressive neural network, for each resolution, use likelihoods obtained from these generative models for each scale to determine anomalies: An image must be within the range of likelihoods on the training data in all scales to be considered to be normal.

The method comprises a step202of providing signals for anomaly detection. The signals are in one aspect provided to the input102of the device100. The signals in the example depicted inFIG.3represent a digital representation302. The digital representation in the example is a digital image of size 32×32 pixel.

The method comprises a step204of processing the digital representation302of a signal or image with a wavelet decomposition to generate a first plurality of decomposed representations304. In the example, the digital representation302is processed by a Haar Wavelet decomposition to produce a first decomposed representation304aand at least one second decomposed representation. The wavelet decomposition produces in the example the first decomposed representation304aand three additional decomposed representations304b,304c,304d. The resolution of these decomposed representations is in the example 16×16 pixel.

The method comprises a step206of processing the first decomposed representation304aof the first plurality of decomposed representations304with a wavelet decomposition to generate a second plurality of decomposed representations306. In the example, the first decomposed representation304ais processed by the Haar Wavelet decomposition to produce a first decomposed representation306aand at least one second decomposed representation. The wavelet decomposition produces in the example the first decomposed representation306aand three additional decomposed representations306b,306c,306d. The resolution of these decomposed representations is in the example 8×8 pixel.

The method comprises a step208of processing the first decomposed representation306aof the second plurality of decomposed representations306with a wavelet decomposition to generate a third plurality of decomposed representations308. In the example, the first decomposed representation306ais processed by the Haar Wavelet decomposition to produce a first decomposed representation308aand at least one second decomposed representation. The wavelet decomposition produces in the example the first decomposed representation308aand three additional decomposed representations308b,308c,308d. The resolution of these decomposed representations is in the example 4×4 pixel.

The method comprises a step210of processing the first decomposed representation308aof the third plurality of decomposed representations308with a first generative model310to determine a first likelihood pθ1.

The method comprises a step212of processing at least one second decomposed representation308b,308c,308dof the third plurality of decomposed representations308with a second generative model312to determine a second likelihood pθ2.

The second generative model312may be conditioned on the first decomposed representation308aof the third plurality of decomposed representations308.

The method comprises a step214of processing at least one second decomposed representation306b,306c,306dof the second plurality of decomposed representations306with a third generative model106to determine a third likelihood pθ3.

The third generative model106may be conditioned on the first decomposed representation308aof the third plurality of decomposed representations308and conditioned on the at least one second decomposed representation308b,308c,308dof the third plurality of decomposed representations308.

The third generative model106may be conditioned instead on reconstructed representation that is reconstructed from the first decomposed representation308aof the third plurality of decomposed representations308and the at least one second decomposed representation308b,308c,308dby inverse wavelet decomposition. This exactly reconstructs the corresponding averages of the first decomposed representation306aof the second plurality of decomposed representations306.

The method comprises a step216of processing at least one second decomposed representation304b,304c,304dof the first plurality of decomposed representations304with a fourth generative model316to determine a fourth likelihood pθ4.

The fourth generative model316may be conditioned on the first decomposed representation308aof the third plurality of decomposed representations308, conditioned on the at least one second decomposed representation308b,308c,308dof the third plurality of decomposed representations308and conditioned on the at least one second decomposed representation306b,306c,306dof the second plurality of decomposed representations306.

The fourth generative model316may be conditioned instead on a reconstructed representation that is reconstructed from the first decomposed representation308aof the third plurality of decomposed representations308, the at least one second decomposed representation308b,308c,308dof the third plurality of decomposed representations308and/or the at least one second decomposed representation306b,306c,306dof the second plurality of decomposed representations306by at least one inverse wavelet decomposition. This exactly reconstructs the corresponding averages of the first decomposed representation304aof the first plurality of decomposed representations304.

Solid lines inFIG.3indicate the input to the generative models. Dashed lines inFIG.3indicate conditioned inputs to the generative models.

The method comprises a step218of detecting an anomaly when at least one of the first likelihood pθ1, the second likelihood pθ2, the third likelihood pθ3and the fourth likelihood pθ4meets a criterion for anomaly detection.

In the example, the first likelihood pθ1is compared to a first threshold, the second likelihood pθ2is compared to a second threshold, the third likelihood pθ3is compared to a third threshold, and the fourth likelihood pθ4is compared to a fourth threshold. The thresholds may be set to the same or to different values.

An anomaly may be detected by evaluating whether the first likelihood pθ1, the second likelihood pθ2, the third likelihood pθ3and the fourth likelihood pθ4together meet the criterion. For example a sum is determined depending on the first likelihood pθ1, the second likelihood pθ2, the third likelihood pθ3, and the fourth likelihood pθ4. The sum is compared to a threshold in a comparison and a normal or an abnormal image is detected depending on the result of the comparison. In the example, the anomaly is detected if the sum exceeds the threshold.

The sum may be a weighted sum of the likelihoods. The weight may be determined depending on the scale or resolution of the representation the likelihood is determined for. For example, the first likelihood pθ1is scaled by dividing it by the scale of the first decomposed representation308aof the third plurality of decomposed representations308that was used to determine the first likelihood pθ1. For example, the second likelihood pθ2is scaled by dividing it by the scale of the at least one second decomposed representation308b,308c,308dof the third plurality of decomposed representations308that was used to determine the second likelihood pθ2. For example, the third likelihood pθ3is scaled by dividing it by the scale of the at least one second decomposed representation306b,306c,306dof the second plurality of decomposed representations306that was used to determine the third likelihood pθ3. For example, the fourth likelihood pθ4is scaled by dividing it by the scale of the at least one second decomposed representation304b,304c,304dof the first plurality of decomposed representations304that was used to determine the fourth likelihood pθ4. The sum is in this example determined by summing up the resulting scaled likelihoods.

In one aspect, when a pixel defines at least one intensity value, the digital representation302may be defined by a set of said pixel. The pixels are arranged in a two dimensional matrix having a horizontal extension and a vertical extension, e.g. of 32×32 pixel.

For this aspect, the step204may comprise a step204aof determining the first decomposed representation304aof the first plurality of decomposed representations304depending on an average intensity value. The average intensity value is for example determined by averaging intensity values of non-overlapping sub-sets of the set of pixel of the digital representation302. In the example a 16×16 pixel image is generated using non overlapping blocks of size 2×2 pixel.

Furthermore, the step204may comprise determining at least one of the at least one second decomposed representations304b,304c,304ddepending on a difference between the intensity values of at least two different of said pixel.

In the example the step204comprises a step204bof determining the second decomposed representation304bdepending on a difference between the intensity values of pixel for a horizontal extension of the digital representation302. In the example a 16×16 pixel image is generated.

In the example the step204comprises a step204cof determining the second decomposed representation304cdepending on a difference between the intensity values of pixel for a vertical extension of the digital representation302. In the example a 16×16 pixel image is generated.

In the example the step204comprises a step204dof determining the second decomposed representation304ddepending on a difference between the intensity values of pixel for a diagonal extension of the digital representation302. In the example a 16×16 pixel image is generated.

Furthermore the step206may comprise a step206aof determining the first decomposed representation306aof the second plurality of decomposed representations306depending on an average intensity value. The average intensity value is for example determined by averaging intensity values of non-overlapping sub-sets of the set of pixel of the first decomposed representation304a. In the example a 8×8 pixel image is generated using non overlapping blocks of size 2×2 pixel.

The step206may comprise determining the at least one second decomposed representations306b,306c,306dof the second plurality of decomposed representations306depending on a difference between the intensity values of at least two different of said pixel of the first decomposed representation304a.

In the example, the step206comprises a step206bof determining the at least one second decomposed representations306bof the second plurality of decomposed representations306depending on difference between the intensity values of pixel for a horizontal extension of the first decomposed representation304a. In the example a 8×8 pixel image is generated.

In the example, the step206comprises a step206cof determining the at least one second decomposed representations306cof the second plurality of decomposed representations306depending on difference between the intensity values of pixel for a horizontal extension of the first decomposed representation304a. In the example a 8×8 pixel image is generated.

In the example, the step206comprises a step206dof determining the at least one second decomposed representations306dof the second plurality of decomposed representations306depending on difference between the intensity values of pixel for a horizontal extension of the first decomposed representation304a. In the example a 8×8 pixel image is generated.

Furthermore the step208may comprise a step208aof determining the first decomposed representation308aof the second plurality of decomposed representations308depending on an average intensity value. The average intensity value is for example determined by averaging intensity values of non-overlapping sub-sets of the set of pixel of the first decomposed representation306a. In the example a 4×4 pixel image is generated using non overlapping blocks of size 2×2 pixel.

The step208may comprise determining the at least one second decomposed representations308b,308c,308dof the second plurality of decomposed representations308depending on a difference between the intensity values of at least two different of said pixel of the first decomposed representation306a.

In the example, the step208comprises a step208bof determining the at least one second decomposed representations308bof the second plurality of decomposed representations308depending on difference between the intensity values of pixel for a horizontal extension of the first decomposed representation306a. In the example a 4×4 pixel image is generated.

In the example, the step208comprises a step208cof determining the at least one second decomposed representations308cof the second plurality of decomposed representations308depending on difference between the intensity values of pixel for a horizontal extension of the first decomposed representation306a. In the example a 4×4 pixel image is generated.

In the example, the step208comprises a step208dof determining the at least one second decomposed representations308dof the second plurality of decomposed representations308depending on difference between the intensity values of pixel for a horizontal extension of the first decomposed representation306a. In the example a 4×4 pixel image is generated.

The digital representation302may comprise a grey scale or color channels for the pixel. In this aspect, the method comprises concatenating these channels into an input and processing this input according to the steps described above. The anomaly is in this example detected in case an anomaly is detected for the input comprising all of the channels. The wavelet decomposition is in the example performed on channel basis, i.e. independently per channel. Then the result of the wavelet decomposition, i.e. the wavelet coefficients, are concatenated along channel dimension for the generative model. The generative model is in this example trained jointly for all channel.

An example method for training the models is described with reference toFIG.4. The method for training may be executed before using the models. In this aspect, the generative first model310, the generative second model312, the generative third model314and/or the generative fourth model316may be trained as described below and then uses in the method described above.

The method for training comprises a step402of initializing the parameters of the generative first model310, the generative second model312, the generative third model314and/or the generative fourth model316e.g. randomly.

Afterwards, in a step404, a digital training representation of a signal or image is processed with the wavelet decomposition to generate a first plurality of decomposed training representations. The processing is for example the same as described for step204above. Steps204a,204b,204cand204dmay be executed as well.

Afterwards, in a step406a first decomposed training representation of the first plurality of decomposed training representations304is processed with the wavelet decomposition to generate a second plurality of decomposed training representations. The processing is for example the same as described for step206above. Steps206a,206b,206cand206dmay be executed as well.

Afterwards, in a step408, a first decomposed training representation of the second plurality of decomposed training representations is processed with the wavelet decomposition to generate a third plurality of decomposed training representations. The processing is for example the same as described for step208above. Steps208a,208b,208cand208dmay be executed as well.

Afterwards the method comprises a step410of determining first training data for the first model310comprising the first decomposed training representation of the third plurality of decomposed training representations.

Afterwards the method comprises a step412of determining second training data for the second model312comprising the at least one second decomposed training representation of the third plurality of decomposed training representations.

Afterwards the method comprises a step414of determining third training data for the third model314comprising the at least one second decomposed training representation of the second plurality of decomposed training representations.

Afterwards the method comprises a step416of determining fourth training data for the fourth model316comprising the at least one second decomposed training representation of the first plurality of decomposed training representations.

The steps404to416may be repeated for a plurality of digital training representations.

Afterwards the method comprises a step418of training the first generative model310with the first training data to determine the first likelihood pθ1.

Afterwards the method comprises a step420of training the second generative model312with the second training data to determine the second likelihood pθ2.

Afterwards the method comprises a step422of training the third generative model314with the third training data to determine the third likelihood pθ3.

Afterwards the method comprises a step424of training the fourth generative model316with the fourth training data to determine the fourth likelihood pθ4.

Afterwards optionally the step202of the method described above is executed to perform abnormality detection with the so trained generative models.