Unsupervised neighbor-preserving embedding for image stream visualization and anomaly detection

Methods and systems for detecting and correcting anomalous inputs include training a neural network to embed high-dimensional input data into a low-dimensional space with an embedding that preserves neighbor relationships. Input data items are embedded into the low-dimensional space to form respective low-dimensional codes. An anomaly is determined among the high-dimensional input data based on the low-dimensional codes. The anomaly is corrected.

BACKGROUND

Technical Field

The present invention relates to visual anomaly detection and, more particularly, to the embedding of high-dimensional data in a low-dimensional space to aid in visualization of images and anomaly detection.

Description of the Related Art

Image information can be used to perform quality control on large numbers of manufactured goods. By comparing images across large numbers of a product, anomalies can be detected and corrected or disposed of. However, the large amount of data involved makes it difficult to identify anomalies manually, and the high dimensionality of image information introduces noise to automated systems.

SUMMARY

A method for detecting and correcting anomalous inputs includes training a neural network to embed high-dimensional input data into a low-dimensional space with an embedding that preserves neighbor relationships. Input data items are embedded into the low-dimensional space to form respective low-dimensional codes. An anomaly is determined among the high-dimensional input data based on the low-dimensional codes. The anomaly is corrected.

A system for detecting and correcting anomalous inputs includes a neural network configured to embed high-dimensional input data into a low-dimensional space. A training module is configured to train the neural network to embed the high-dimensional input data with an embedding that preserves neighbor relationships. An anomaly detector is configured to use the neural network to embed input data items into the low-dimensional space to form respective low-dimensional codes and to determine anomaly among the high-dimensional input data based on the low-dimensional codes. An anomaly correction module is configured to correct the anomaly.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

Embodiments of the present invention embed high-dimensional image information into a lower-dimensional space in such a way as to maintain locality between similar images. This makes it possible to perform accurate visualization of the images in a two-dimensional display, with similar images being grouped together, and also improves automatic classification of anomalous images by reducing redundant information and noise. The present embodiments can perform the embedding in an unsupervised fashion.

The present embodiments accept a stream of images as an input. To enable visualization of the incoming data stream, which can be very rapid in some embodiments, the present embodiments embed the high-dimensional image data into a low-dimensional (e.g., two-dimensional) space. The embeddings maintain nearest-neighbor relationships between the input images.

A neural network can be trained to perform the embedding and can be trained in an unsupervised fashion using small batches of input data. To address the fact that the pairwise similarities between data points in the small batches only account for a small fraction of all pairwise similarities between data points in a large training set, the present embodiments learn embedding parameters of an encoder by comparing high-dimensional data points with some representative high-dimensional exemplars and other data points in the same batch. The exemplars are initialized by a small number of iterations of k-means updates, with the option of including manually chosen exemplars, taking into account both local data density distributions and global clustering patterns of high-dimensional data. This makes the parametric embedding insensitive to batch size and scalable to large datasets.

Further, to ensure the local neighborhood structure in the high-dimensional space is well-coded in the low-dimensional space, a large-margin criterion is used to make the distance between each data point and its kthnearest neighbor always one margin smaller than its distance to its (k+1)thnearest neighbor. To make the parameters of the neural network capture intrinsic data variances, a decoder is used to reconstruct high-dimensional data points from corresponding low-dimensional codes. The exemplars are also updated by minimizing the reconstruction error of each data point based on a convex combination of the learned high-dimensional feature vectors of exemplars, in which the combination weights are the corresponding pairwise probabilities between the data point and the exemplars, calculated in the low-dimensional space.

Referring now toFIG. 1, a manufacturing process is shown. A camera102takes images of a series of products104. In some embodiments, the products104are intended to be identical to one another, but can be defective for a wide variety of reasons, including manufacturing process variations, environmental variations, and human error. The images produced by the camera102can include multiple images for each product104, for example capturing different views and different angles or under different lighting conditions, to reveal potential defects that may not be visible from a single view. Although the present embodiments are described in the specific context of identifying anomalous or defective products, it should be understood that the present embodiments can be applied to discriminate between any set of high-dimensional inputs to identify anomalies in the set.

The camera102can represent a single imaging device or can, alternatively, represent a number of distinct imaging devices. The camera102can furthermore represent any appropriate imaging technology, for example including digital cameras that operate in the visible spectrum, ultraviolet spectrum, infrared spectrum, or a combination of these spectra. The images generated by the camera102are represented with pixels and can be compared to one another to determine similarities according to an appropriate distance metric. Similar images are referred to herein as “neighbors.” By default, such a comparison operates in a high-dimensional space, as each pixel in an image contributes to its “position.” The large number of pixels yield a significant amount of redundant, noisy data and do a poor job of representing similarity in a way that is meaningful to a human observer.

The images are therefore passed to an anomaly visualization and classification system106. The anomaly visualization and classification106embeds each image into a space of low-dimensionality, for example two dimensions. The images can then be visualized, using an appropriate display and user interface, for example with similar images being displayed close to one another on a two-dimensional field. In addition, unsupervised classification can be performed in the low-dimensional space, with the noise and redundant information from the images being effectively removed by the low-dimensional embedding.

Referring now to the drawings in which like numerals represent the same or similar elements and initially toFIG. 2, an artificial neural network (ANN) architecture200is shown. It should be understood that the present architecture is purely exemplary and that other architectures or types of neural network may be used instead. The ANN embodiment described herein is included with the intent of illustrating general principles of neural network computation at a high level of generality and should not be construed as limiting in any way.

Furthermore, the layers of neurons described below and the weights connecting them are described in a general manner and can be replaced by any type of neural network layers with any appropriate degree or type of interconnectivity. For example, layers can include convolutional layers, rectified linear unit (ReLU) layers, pooling layers, fully connected layers, or any other appropriate type of neural network layer. Furthermore, layers can be added or removed as needed and the weights can be omitted for more complicated forms of interconnection.

During feed-forward operation, a set of input neurons202each provide an input signal in parallel to a respective row of weights204. In the hardware embodiment described herein, the weights204each have a respective settable value, such that a weight output passes from the weight204to a respective hidden neuron206to represent the weighted input to the hidden neuron206. In software embodiments, the weights204may simply be represented as coefficient values that are multiplied against the relevant signals. The signal from each weight adds column-wise and flows to a hidden neuron206.

The hidden neurons206use the signals from the array of weights204to perform some calculation. The hidden neurons206then output a signal of their own to another array of weights204. This array performs in the same way, with a column of weights204receiving a signal from their respective hidden neuron206to produce a weighted signal output that adds row-wise and is provided to the output neuron208.

It should be understood that any number of these stages may be implemented, by interposing additional layers of arrays and hidden neurons206. It should also be noted that some neurons may be constant neurons209, which provide a constant output to the array. The constant neurons209can be present among the input neurons202and/or hidden neurons206and are only used during feed-forward operation.

During back propagation, the output neurons208provide a signal back across the array of weights204. The output layer compares the generated network response to training data and computes an error. The error signal can be made proportional to the error value. In this example, a row of weights204receives a signal from a respective output neuron208in parallel and produces an output which adds column-wise to provide an input to hidden neurons206. The hidden neurons206combine the weighted feedback signal with a derivative of its feed-forward calculation and stores an error value before outputting a feedback signal to its respective column of weights204. This back propagation travels through the entire network200until all hidden neurons206and the input neurons202have stored an error value.

During weight updates, the stored error values are used to update the settable values of the weights204. In this manner the weights204can be trained to adapt the neural network200to errors in its processing. It should be noted that the three modes of operation, feed forward, back propagation, and weight update, do not overlap with one another.

Referring now toFIG. 3, a method of manufacture with quality control is shown. Block302trains a machine learning system for embedding images into a low-dimensional space. It is specifically contemplated that a neural network can be used, as explained in greater detail below, but it should be understood that other machine learning systems can be used instead. Block302uses a large set of training data, which can include a large set of images. Additional detail regarding the training process in block302is provided below.

Block304then captures new images of products104using camera(s)102. Block306uses the trained neural network to embed the captured new images into the low-dimensional space in such a way as to preserve locality between neighboring images. The embedded images may be referred to herein as low-dimensional codes for the images. The two-dimensional embedding can then be used by block308to visualize images, as the embeddings of respective images encode similarity information. For example, by determining images' embedding vectors in a two-dimensional space, a distance between any two images can be determined using an appropriate metric, such as the cosine similarity or a Euclidean distance. Visualization can then include displaying sets of images, with images that are closer to one another in the low-dimensional space being displayed closer to one another than images that are farther apart in the low-dimensional space.

Block310automatically determines whether a particular image represents an anomaly. Anomalies can be detected by comparing similar views of images across different products104to identify images that are farther away from the other images in the low-dimensional space than others. This can be determined by identifying images that have an above-threshold distance from the other images or by a clustering process that groups similar images together, identifying the outliers as being anomalies.

Block312then takes action to correct the anomalies. In some embodiments, correction of an anomaly can include automatically discarding anomalous products104. In other embodiments, block312can flag the product104for further review by a human operator. In still other embodiments, block312can repair the anomaly (e.g., causing an imperfectly painted product to be re-painted).

Referring now toFIG. 4, additional detail is shown regarding the training of the neural network in block302. Block402forms batches from a large, high-dimensional input set. For example, in an input training data set that includes a million images, batches may be formed by randomly sampling 1024 images from that input set. It should be understood that any appropriate batch size can be selected instead.

Block404determines exemplars for each batch. Exemplars can be determined by running iterations of a k-means update or by random data sampling. The exemplars are used to determine neighboring probabilities between the exemplars and all other data points in the respective batch. The exemplars can be interpreted as landmarks that represent the entire dataset.

Block406determines pairwise neighboring probabilities P for the high-dimensional data in each batch. The pairwise probability between an image i and an image j are computed as:

pij=e-x(i)-x(j)22⁢σi2∑k≠i⁢e-x(i)-x(k)22⁢σi2
where x(i)is a high-dimensional feature (e.g., a pixel) vector of i in the batch, p(i|i)=0,

pij=p⁢(j❘i)+p⁢(i❘j)2⁢n,
n is the batch size, and σiis set such that the perplexity of piequals a user specified hyper-parameter u.

Block408determines the embedding in each batch using a neural network408. Each image I goes through an encoder portion of the neural network to generate the low-dimensional embedding vector f(x(i)).

Block410determines pairwise probabilities Q for the low-dimensional embeddings in each batch. Using the low-dimensional embedding vector f(x(i)), the low-dimensional pairwise probabilities are calculated as:

Block412reconstructs the high-dimensional data from the low-dimensional embeddings and the exemplars. The functions ∥x(i)−g(f(x(i))∥ and ∥x(i)−Σkθike(k)∥ are minimized, where k=1, . . . , z, z is the total number of exemplars, and:

θij=(1+f⁡(x(i))-f⁡(x(j)))-1(∑l=1z⁢(1+f⁡(x(i))-f⁡(x(l))2)-1
To make sure the kthnearest neighbor is always closer to image i than its (k+1)thnearest neighbor, the hinge-loss is minimized as follows:
max(0,1+∥f(x(i))−f(NN(i,k))∥−∥f(x(i))−f(NN(i,k+1))∥
where NN(i,k) denotes the kthnearest neighbor of the image i.

The exemplars are used to reconstruct the input images and θijis similar to qijbut computed with a normalization over all exemplars. In contrast, qijis computed with a normalization over all exemplars and other images in the same batch. The exemplars are used to reconstruct the image because the pre-defined exemplars, which were determined through k-means clustering or are manually chosen images that represent product defects, are updated to make sure the exemplars are representative of the whole data set and because the reconstruction term helps learn better low-dimensional embeddings. For example, if initial training has resulted in an encoder that produces inaccurate results, then θjiwill not be meaningful, and the convex combination of the exemplars will not properly reconstruct the input image. The value of θijis a scalar, where Σjθij=1.

Block414minimizes a loss function, which includes a Kullback-Leibler (KL) loss, a series of reconstruction errors from the low-dimensional embeddings and the exemplars, and a series of neighborhood-preserving hinge losses. Using this minimization, block416updates the parameters of the neural network and the exemplars. The KL loss function can be expressed as:

KL⁡(P❘❘Q)=∑ij:i≠j⁢pij⁢⁢log⁢⁢pijqijwherepij=e-x(i)-x(j)22⁢σi2∑k≠i⁢e-x(i)-x(k)22⁢σi2⁢⁢p⁡(i❘i)=0pij=pj❘i+pi❘j2⁢nqij=(1+f⁡(x(i)-f(x(j)2)-1∑kl:k≠l⁢(1+f⁡(x(i)-f(x(l)2)-1⁢⁢qii=0
and where N is the number of training data points, P is the Gaussian distribution calculated in block406, Q is a t-distribution calculated in block410, and K is the largest number of nearest neighbors to be considered for each data point. P and Q are calculated in a batched fashion, where each batch includes both a subset of randomly sampled training data points and all the determined exemplars. The final loss function is the sum of the KL loss, the reconstruction loss from the decoder, the reconstruction loss by the exemplars, and the hinge loss weighted by user-specified hyper-parameters.

Referring now toFIG. 5, additional detail is provided regarding the determination of anomalies in block310. Block502estimates the density of low-dimensional embeddings based on a standard Gaussian mixture model (GMM). Block504fits a standard one-class support vector machine (SVM) separately from the Gaussian mixture model on the low-dimensional embeddings of all data points. Blocks502and504can be reversed in order or can be performed concurrently. If an input image is in a low-density region of the fitted GMM (e.g., in a region with a below-threshold density), that indicates that the log-likelihood of the embedding will be small and is likely to represent an anomaly. If the one-class SVM fits a model that outputs a 1 for normal data and a −1 for abnormal data, then the SVM can also be used to mark anomalies. Block506averages the anomaly prediction from the GMM and the one-class SVM fit. Block508uses the determined combined prediction to identify anomalies in an input data set.

Referring now toFIG. 6, an anomaly detection and visualization system600is shown. The system600includes a hardware processor602and memory604. An ANN606is implemented either in a hardware or software embodiment, or a combination of the two. It is specifically contemplated that the ANN606may have an autoencoder structure, where an encoder portion of the ANN606converts high-dimensional input data to a low-dimensional embedding and where a decoder portion converts a low-dimensional embedding into a high-dimensional recreation of the original input data.

Training module608trains the ANN606using a set of high-dimensional training data. A user interface610provides visualization of a set of input data based on low-dimensional embeddings provided by the ANN606. The low-dimensional embeddings preserve neighbor relationships between images, such that the images can be displayed on a two-dimensional field in proximity to similar other images.

An anomaly detector612identifies anomalous images from among a set of input images. Anomaly correction module614then uses the identified anomalous images to take a corrective action regarding an associated product or object, for example by automatically discarding the anomalous product.

Referring now toFIG. 7, an exemplary processing system700is shown which may represent the anomaly detection and visualization system600. The processing system700includes at least one processor (CPU)704operatively coupled to other components via a system bus702. A cache706, a Read Only Memory (ROM)708, a Random Access Memory (RAM)710, an input/output (I/O) adapter720, a sound adapter730, a network adapter740, a user interface adapter750, the anomaly detection612, and the training module608, display adapter760, the ANN606, and the, are operatively coupled to the system bus702.

A first storage device722is operatively coupled to system bus702by the I/O adapter720. The storage device722can be any of a disk storage device (e.g., a magnetic or optical disk storage device), a solid state magnetic device, and so forth. The storage device722can be the same type of storage device or different types of storage devices.

A transceiver742is operatively coupled to system bus702by network adapter740. A display device762is operatively coupled to system bus702by display adapter760.

A first user input device752is operatively coupled to system bus702by user interface adapter750. The user input device752can be any of a keyboard, a mouse, a keypad, an image capture device, a motion sensing device, a microphone, a device incorporating the functionality of at least two of the preceding devices, and so forth. Of course, other types of input devices can also be used, while maintaining the spirit of the present principles. The user input device752can be the same type of user input device or different types of user input devices. The user input device752is used to input and output information to and from system700.

Of course, the processing system700may also include other elements (not shown), as readily contemplated by one of skill in the art, as well as omit certain elements. For example, various other input devices and/or output devices can be included in processing system700, depending upon the particular implementation of the same, as readily understood by one of ordinary skill in the art. For example, various types of wireless and/or wired input and/or output devices can be used. Moreover, additional processors, controllers, memories, and so forth, in various configurations can also be utilized as readily appreciated by one of ordinary skill in the art. These and other variations of the processing system700are readily contemplated by one of ordinary skill in the art given the teachings of the present principles provided herein.