Tracking objects in sequences of digital images

Abstract

A system for tracking objects in a temporal sequence of digital images is configured to: detect potential objects in the images, the detected potential objects being indicated as nodes, identify pairs of neighboring nodes, such that for each pair the nodes of said pair potentially represent an identical object and their spatial and/or temporal relationship with each other is within a predetermined range, connect each pair of neighboring nodes with a first type edge, identify at least one supplementary pair of distant nodes whose spatial and/or temporal relationship with each other exceeds the predetermined range, connect the pair of distant nodes with a supplementary second type edge, each of the first and second type edges being assigned a cost value, and determine a track of an object in the temporal sequence of digital images based on a set of connected first type edges and at least one second type edge.

Claims

1. A system for tracking objects in a temporal sequence of digital images, the system being configured to: detect potential objects in the images, the detected potential objects being indicated as nodes, identify pairs of neighboring nodes, such that for each pair the nodes of said pair potentially represent an identical object and their spatial and/or temporal relationship with each other is within a predetermined range, connect each pair of neighboring nodes with a first type edge, identify at least one supplementary pair of distant nodes whose spatial and/or temporal relationship with each other exceeds the predetermined range, connect the pair of distant nodes with a supplementary second type edge, each of the first and second type edges being assigned a cost value representing a probability whether the connected nodes represent an identical object or not, and determine a track of an object in the temporal sequence of digital images based on a set of connected first type edges and at least one second type edge additionally connecting at least one of the nodes connected by the set of connected first type edges.

2. The system according to claim 1, wherein the at least one supplementary pair of distant nodes is identified such that the nodes of said supplementary pair potentially represents an identical object, or such that the nodes of said supplementary pair potentially represent different objects.

3. The system according to claim 1, wherein the track is determined based on the cost values of the set of connected first type edges and/or the cost value of the at least one supplementary second type edge.

4. The system according to claim 1, comprising a neural network being configured to: assign each of the first and second type edges a cost value representing a probability whether the connected nodes represent an identical object or not.

5. The system according to claim 4, wherein the neural network is further configured to: detect the potential objects in the images, the detected potential objects being indicated as nodes, identify the pairs of neighboring nodes, connect each pair of neighboring nodes, identify the at least one supplementary pair of distant nodes, and connect the pair of distant nodes.

6. The system according to claim 1, wherein determining the track comprises: identifying a set of connected first type edges representing the track, and updating the track based on the at least one second type edge.

7. The system according to claim 1, wherein determining a track comprises: determining a graph having a plurality of components, wherein each component comprises a set of connected first type edges, and updating the graph by joining and/or cutting single components based on at least one supplementary second type edge, wherein each joined and/or cut component of the updated graph represents a track of an object.

8. The system according to claim 7, further configured to: update the graph by joining single components to a merged component, in case at least one supplementary second type edge extends along said single components.

9. The system according to claim 7, further configured to: update the graph by joining single components to the merged component, only in case the cost value of said at least one supplementary second type edge exceeds a predetermined threshold value.

10. The system according to claim 1, further configured to: connect a pair of distant nodes with a second type edge, only in case said distant nodes are also connected by a set of connected first type edges.

11. The system according to claim 1, wherein the spatial and/or temporal relationship of a pair of nodes is defined by the spatial and/or temporal distance of said pair of nodes to each other, and/or the predetermined range is defined by a predetermined spatial and/or temporal distance threshold.

12. The system according to claim 1, wherein the predetermined range is defined such that the spatial and/or temporal relationship of a pair of nodes exceeds the predetermined range, in case at least one further node is identified between the pair of nodes potentially representing the identical object like said pair of nodes.

13. The system according to claim 1, wherein the determination that nodes potentially represent an identical object is based on the cost value of the connecting edge, and/or the cost value of an edge is determined based on the scales, coordinates and/or appearances of the connected nodes.

14. A method of tracking objects in a temporal sequence of digital images, comprising the steps of: detecting potential objects in the images, the detected potential objects being indicated as nodes, identifying pairs of neighboring nodes, such that for each pair the nodes of said pair potentially represent an identical object and their spatial and/or temporal relationship with each other is within a predetermined range, connecting each pair of neighboring nodes with a first type edge, identifying at least one supplementary pair of distant nodes whose spatial and/or temporal relationship with each other exceeds the predetermined range, connecting the pair of distant nodes with a supplementary second type edge, each of the first and second type edges being assigned a cost value representing a probability whether the connected nodes represent an identical object or not, and determining a track of an object in the temporal sequence of digital images based on a set of connected first type edges and at least one second type edge additionally connecting at least one of the nodes connected by the set of connected first type edges.

15. A non-transitory computer readable medium including a computer program comprising instructions for executing the steps of the method according to claim 14 when the program is executed by a computer.

16. The system according to claim 1, wherein the set of connected first type edges define a feasible solution in the graph, and the at least one second type edge adds additional long range information to an objective on which nodes should be joint or cut without modifying the feasible solution.

17. The system according to claim 1, wherein the first type edges define possibilities of joining nodes directly into the same track and the second type edges do not define possibilities of directly joining nodes.

18. The method according to claim 14, wherein determining the track comprises: identifying a set of connected first type edges representing the track, and updating the track based on the at least one second type edge.

19. The method according to claim 14, wherein the set of connected first type edges define a feasible solution in the graph, and the at least one second type edge adds additional long range information to an objective on which nodes should be joint or cut without modifying the feasible solution.

20. The method according to claim 14, wherein the first type edges define possibilities of joining nodes directly into the same track and the second type edges do not define possibilities of directly joining nodes.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a schematic block diagram of a system according to embodiments of the present disclosure;

(2) FIG. 2a shows a comparison of exemplary tracks according to the prior art;

(3) FIG. 2b shows a comparison of exemplary tracks according to embodiments of the present disclosure;

(4) FIG. 2c shows a comparison of exemplary tracks according to the prior art;

(5) FIG. 2d shows a comparison of exemplary tracks according to embodiments of the present disclosure;

(6) FIG. 3a shows a schematic representation of neural networks according to embodiments of the present disclosure;

(7) FIG. 3b shows a schematic representation of neural networks according to embodiments of the present disclosure; and

(8) FIG. 3c shows a schematic representation of neural networks according to embodiments of the present disclosure.

DESCRIPTION OF THE EMBODIMENTS

(9) Reference will now be made in detail to exemplary embodiments of the disclosure, examples of which are illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings to refer to the same or like parts.

(10) FIG. 1 shows a block diagram of a system 10 according to embodiments of the present disclosure. The system may have various further functions, e.g. may be a robotic system or a camera system. It may further be integrated in a vehicle.

(11) The system 10 may comprise an electronic circuit, a processor (shared, dedicated, or group), a combinational logic circuit, a memory that executes one or more software programs, and/or other suitable components that provide the described functionality. In other words, system 10 may be a computer device.

(12) The system may be connected to a memory, which may store data, e.g. a computer program which when executed, carries out the method according to the present disclosure. In particular, the system or the memory may store software which may comprise a neural network according to the present disclosure.

(13) The system 10 has an input for receiving digital images or a stream of digital images. In particular, the system 10 may be connected to an optical sensor 1, in particular a digital camera. The digital camera 1 is configured such that it can record a scene, and in particular output digital data to the system 10.

(14) The system may be configured to identify objects in the images, e.g. by carrying out a computer vision algorithm for detecting the presence and location of objects in a sensed scene. For example, persons, vehicles and other objects may be detected. The system may track the detected objects across the images.

(15) In the following the operation of the neural network according to the present disclosure is explained in more detail with reference to the mathematical abstraction of multiple people tracking as a minimum cost lifted multicut problem (LMP) according to the present disclosure.

(16) The LMP is an optimization problem whose feasible solutions can be identified with decompositions of a graph. Comparing to the minimum cost multicut problem (MP), as known e.g. from: S. Tang, B. Andres, M. Andriluka, and B. Schiele. Multiperson tracking by multicuts and deep matching. In BMTT, 2016,

(17) which is defined with regard to a graph whose edges define possibilities of joining nodes directly into the same track. The LMP is defined, in addition, with regard to additional lifted edges (i.e. second type edges) that do not define possibilities of directly joining nodes. The decision of joining the nodes needs to be supported by the regular edges (i.e. first type edges).

(18) The motivation for modeling the lifted edges comes from the simple fact that persons of similar appearance are not necessarily identical. Given two detections that are far apart in time and similar in appearance, it is more likely a priori that they represent the same person. At the same time, this decision is desirably certified a posteriori by a track connecting the two. This can be achieved by introducing the two classes of edges: In order to assign two detections that are far apart in time and similar in appearance to the same cluster (i.e. person), there must exist a path (i.e. track) along the regular edges, that certifies this decision.

(19) FIGS. 2a to 2d show comparisons of exemplary tracks according to the prior art (FIGS. 2a and 2c) and according to embodiments of the present disclosure (FIGS. 2b and 2d). In particular, a comparison between conventional Multicut Problem (MP) (FIGS. 2a and 2c) and Lifted Multicut Problem (LMP) (FIGS. 2b and 2d) is provided. Ground truth tracks G of each person O are depicted as hollow lines. Regular edges are depicted as simple lines, lifted edges as double lines. Solid lines indicate joints, dotted lines indicate cuts. Costs of cutting edges are indicated by the numbers on the corresponding edges.

(20) In FIGS. 2a and 2b the same scene is processed, where three persons are in the scene, v1 is the detection (i.e. node) on the first person, v2 and v3 are the detections on the second, v4 is on the third. The costs on the edges v1v2 and v3v4 are −3, suggesting strong rewards towards cutting the edges, and this is correct (cf. ground truth). However, the cost on the edge v1v4 suggests that the first and the third person look similar and introduces a strong reward towards connecting them. As a result, the MP incorrectly connects v1 and v4 as the same person; the LMP according to the present disclosure does not connect v1 and v4, as such long-range join is not supported by the local edges.

(21) FIG. 2c and FIG. 2d is another example, where the same scene is processed once by MP and once by LMP. In the scene all the detections are on the same person, namely, a track that connects all the nodes in the graph is desirable. Due to partial occlusion or inaccurate bounding box localization, the costs on the local edges v1v2 and v3v4 could be ambiguous, sometimes even reverse. The longrange edge v1v4 correctly re-identifies the person. The MP, however, produces two clusters for a single person because the long-range edge does not have influence on the local connections. In contrast, the LMP allows us to influence an entire chain of connections between person hypotheses with a single confident long-range observation.

(22) Parameters:

(23) Given an image sequence, it may be considered an instance of the LMP with respect to: A finite set V in which every element represents a detection of one person in one image. For every detection, also its scale and the coordinates (x, y, t) of its center in the image sequence may be defined. For every pair v,w of a node v and a node w: a conditional probability of v and w to represent distinct persons, given their scales, coordinates and appearance. A graph whose edges are regular edges that connect detections v;w in the same image and also connect detections in distinct images that are close in time. A graph whose additional edges are lifted edges which connect detections that are far apart in time and similar in appearance.

(24) Feasible Set:

(25) The feasible solutions of the LMP can desirably be identified with the decompositions (clusterings, i.e. components) of the graph G. Here, in the context of tracking, every component (i.e. cluster) of detections defines a track of one person. It is therefore reasonable to think of our approach as tracking by clustering. Formally, any feasible solution of the LMP may be a 01-vector.

(26) FIGS. 3a to 3c show schematic representations of neural networks according to embodiments of the present disclosure. In particular, FIG. 3a shows a SiameseNet 20, FIG. 3b shows a StackNet 20″, and FIG. 3c shows a StackNetPose 20″. Rectangles 23, 23′, 23″ indicate the convolutional, relu and pooling layers of VGG16. Rectangles 24, 24′, 24″ indicate the fully-connected layers. Rectangles 25, 25′, 25″ on the top of each network are the loss layers. Boxes 26 are the stacked body part score maps.

(27) Traditionally, person re-identification is the task to associate observed pedestrians in non-overlapping camera views. In the context of multi-person tracking, linking the detected pedestrians across the whole video can be viewed as reidentification with special challenges: occlusions, cluttered background, large difference in image resolution and inaccurate bounding box localization. As described in the following, several CNN architectures may be used for re-identification for the multi-person tracking task. A basic CNN architecture may be VGG-16 Net, as described e.g. in: K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. CoRR, abs/1409.1556, 2014.

(28) Particularly, a novel person re-identification model is proposed that combines the body pose layout obtained with state-of-the-art pose estimation methods.

(29) ID-Net:

(30) First a VGG net is learnt to recognize e.g. N=2511 unique identities from our data collection as an N-way classification problem. The VGG estimates the probability of each image being each label by a forward pass. The network is trained by the softmax loss. During testing, given an image from unseen identities, the final softmax layer is removed and the output of the fully-connected layer is used as the identity feature. Given a pair of images, the Euclidean distance between the two identity features can be used to decide whether the pair contains the same identity.

(31) SiameseNet:

(32) Siamese architecture means the network contains two symmetry CNNs which share the parameters. It may be started with a commonly used Siamese architecture as shown in FIG. 3(a). To model the similarity fully connected layers may be used on top of the twin CNNs. More specifically, the features FC6(xi); FC6(xj) from a pair of images are extracted from the first fully-connected layer of the VGG-based Siamese network that shares the weights. Then the features are concatenated and transformed by two fully-connected layers (FC7; FC8), where FC7 are followed by a ReLU non-linearity. FC8 uses a softmax function to produce a probability estimation over a binary decision, namely the same identity or different identities.

(33) StackNet:

(34) The most effective architecture which has been explored is the StackNet, where a pair of images are stacked together along the RGB channel. According to an example, the input to the network becomes 112×224×6. Then the filter size of the first convolutional layer is changed from 3×3×3to 3×3×6, and for the rest of the network the VGG architecture may be followed. The last fully-connected layer models a 2-way classification problem, namely the same identity or different identities. During testing, given a pair of images, both SiameseNet and StackNet produce the probability of the pair being the same/different identities by a forward pass.

(35) The StackNet allows a pair of images to communicate at the early stage of the network, but it is still limited by the lack of ability to incorporate body part correspondence between the images. Hence, as further embodiment a body part fusing method is proposed to explicitly allow modeling the semantic body part information within the network.

(36) StackNetPose:

(37) A desirable property of the network is to localize the corresponding regions of the body parts, and to reason about the similarity of a pair of pedestrian images based on localized body regions as well as the full images. Such a model may be implemented by fusing body part detections into the CNN. More specifically, body part detectors may be used to produce individual score maps for 14 body parts, namely, head, shoulders, elbows, wrists, hips, knees, and ankles, each with left/right symmetry body parts except the head which is indicated by head top and head bottom. The score maps from every two symmetry body parts are combined which results in 7 scores maps; each has the same size as the input image. The pair of images as well as the 14 score maps may be stacked together to form a 112×224×20 input volume. Now the filter size of the first convolutional layer is set as 3×3×20, and the rest of the network follows the VGG16 architecture with a 2-way classification layer in the end.

(38) Pairwise Potentials:

(39) The cost of an edge may be based on three information sources: spatio-temporal relations (ST), dense correspondence matching (DM) and person re-identification confidence (Re-ID).

(40) The spatio-temporal relation based feature is commonly used in many multi-person tracking works, as it is a good affinity measure for pairs of detections that are in close proximity. ST features are able to provide useful information within a short temporal window. They model the geometric relations between bounding boxes but do not take image content into account.

(41) DeepMatching (DM) may be introduced as a powerful pairwise affinity for multi-person tracking. The DM feature is based on local image patch matching, which makes it robust to irregular camera motion and to partial occlusion in short temporal distance. The performance of the DM feature drops dramatically when increasing temporal distance. Re-ID is explicitly trained for the task of person re-identification. It is robust with respect to large temporal and spatial distance and allows long-range association. Desirably, deep reidentification model (StackNetPose) may be used for modeling the longrange connections.

(42) Throughout the description, including the claims, the term “comprising a” should be understood as being synonymous with “comprising at least one” unless otherwise stated. In addition, any range set forth in the description, including the claims should be understood as including its end value(s) unless otherwise stated. Specific values for described elements should be understood to be within accepted manufacturing or industry tolerances known to one of skill in the art, and any use of the terms “substantially” and/or “approximately” and/or “generally” should be understood to mean falling within such accepted tolerances.

(43) Although the present disclosure herein has been described with reference to particular embodiments, it is to be understood that these embodiments are merely illustrative of the principles and applications of the present disclosure.

(44) It is intended that the specification and examples be considered as exemplary only, with a true scope of the disclosure being indicated by the following claims.