RELATED APPLICATION

This application corresponds to PCT/GB2017/053771, filed Dec. 15, 2017, which corresponds to British Application No. 1621404.1, filed Dec. 15, 2016, the subject matter, of which are incorporated herein by reference in their entirety.

This invention relates to a method of tracking objects located in a scene around a host object, and may also relate to the tracking of those objects around the host object. It may be used in the control of an autonomous vehicle when used to identify objects that may lie in the path of the vehicle.

There is a wide range of applications in which it would be beneficial or essential to identify objects and to track them. The operation of autonomous vehicles is one application, in which a vehicle must be able to identify and avoid objects such as cars and pedestrians as it drives along a road or off-road. Because many objects may themselves be moving, such as other vehicles, being able to track them allows the autonomous vehicle to predict where they will be in the future and better plan a safe route through the environment.

Identifying objects and tracking them is a non-trivial exercise and requires a lot of signal processing. Many techniques are known but all require a data feed, such as a set of video images, which can be processed to track objects and then to identify their location. This could be a forward-facing camera fitted to a host vehicle, or a set of cameras, or perhaps a radar or lidar system.

One known technique for determining the position of an object, within 3D space, is to use a particle filter to process information about the speed of the vehicle with a map of the environment. In use, a set of particles may be generated which each represent a hypothesis, either random or pseudo random, for the location of the vehicle. Measurement data is fed into the particle filter such as the distance of a feature identified in the map, and this is used to assign a probability to each particle. Those particles with a low probability are then dropped and more particles are produced in the vicinity of those with the highest probability. Over time, the particle filter should converge on the location of the host vehicle in the mapped environment until some probabilistic measure indicates that that an object is at a given location defined by the states of the particles. Alternatively, the probabilistic measure could be used directly in the control system or higher level fusion. The inclusion of higher order states and a motion model in the particle filter allows the particle filter to track object position, velocity, acceleration, etc. directly.

The use of the particle filter can be modified to identify objects that may or may not be present around the host vehicle. This is achieved by feeding into the particle filter a model of an object that is being looked for. Particles are generated at random or pseudo random that define the state of a potential object and the state of each particle is then used to project a wire frame image of the object into the image plane. The image is passed through an edge detector and the strongest edges in the image are retained to form a wire frame image. The projected wire frame model is then overlaid on the edges to see how well they match. If they do match, a particle is retained as a match and if not it is rejected. If the model and edges do not match then more particles are generated until a match is found.

In a real environment the object may be at a range of orientations and, to accommodate this, the wire frame model must be manipulated prior to the matching to correspond with how the wire frame will look in the image frame. This must be repeated for lots of different orientations, which is computationally intensive. Similarly, where there are lots of different objects that are to be located, lots of different wire frames are needed. Because the object may be located at a range of different distances, it is also necessary to scale the wire frame model and repeated the processing for the different scaled wire frames to see if the model matches objects in the 2D image. Consider for example the simple case of identifying cars on a road; as there are lots of different cars, lots of different wire frame models are needed, which may, for example, correspond to different vehicle types or even particular manufacturer models.

Despite the requirement of lots of computation, the applicant has appreciated that particle filtering can be advantageous because by the time an object has been identified the direction of travel and speed of movement of the object relative to the host vehicle will also have been estimated.

The object of the present invention is to provide a method of identifying the location of objects in a scene that can be carried out using fewer computations than prior art techniques such as known uses of particle filtering.

According to a first aspect, the invention provides a method of detecting objects located in an environment around a host object, comprising the steps of:(a) obtaining at least one 2D image of the scene from an image capture device fitted to the host object,(b) generating a set of particles that each comprise a set of parameters that define the state of at least one object that may be present in the scene,(c) calculating an edge strength and edge direction for each pixel of the captured 2D image; and for each particle in the set:(d) generating a 3D probabilistic model of the object that is associated with the particle, the model defining a set of edges of the object, each edge in the model defined by at least one likelihood function defining a probabilistic distribution of at least one characteristic of the edge(e) mapping the likelihood functions of the probabilistic model into the 2D plane of the captured image as a function of the parameters of the particle; and(f) processing the edge strength and edge direction values produced in step (c) with the probability values mapped in step (e) to determine the likelihood that the particle defines the state of an object present in the environment.

The edge strength and edge direction values may be stored as an edge image in a memory in step (c) for subsequent processing in step (f).

The likelihood function may comprise a probabilistic distribution of the location of the edge. This function therefore defines the edge in the model in terms of the probability that the edge may be present in a given position in 3D space.

The likelihood function may comprise a probabilistic distribution of the direction of the edge. This function therefore defines the edge in the model in terms of the probability that the edge feature may be present with a particular angular orientation in 3D space relative to one or more other edges in the set.

The step (C) of assigning an edge direction and edge strength may be performed using any suitable edge detection algorithm, For example, the edge direction and edge strength may be given by edge detection kernels which look at pixels in a region around the pixel to which the values are to be assigned. For example a Sobel “mask” may be used that has a one pixel boundary around the current pixel which means it uses 3×3 pixel masks which is convolved with the image. There is one mask for vertical edge strength and one mask for horizontal edge strength. The direction comes from the arctan of the vertical and horizontal edge strengths. This is well known in image processing and other edge detection masks exist.

This may comprise a cluster of pixels centered on the pixel that the edge direction is to be assigned to. The same sized cluster may be used for each pixel, but smaller sizes could be used, for instance at an edge of the image.

The step of assigning an edge strength may comprise determining the frequency content of or a defined area immediately surrounding each pixel. This may be the same defined area used in determining the edge direction value.

The parameters defining the state of each particle may include one or more of the overall location in 3D space of the object relative to the location of the host object, the orientation and the direction of travel and speed of travel of the object through the 3D space relative to the space or relative to the host object, the rate of acceleration of the object relative to the host vehicle, and the ambient light conditions (e.g. night, dark, or daylight). The parameters may also identify the fuzzy model for the object defined by the particle, i.e. what the object is.

Each edge in the fuzzy model may additionally be defined by a probability function defining the strength of the edge. This strength may be defined absolutely or relative to the strength of other edges in the model of the object. By strength we mean how clear the edges of the object will appear in the image in terms of the variation in colour or intensity across the edge. The edges of the model corresponding to the brake lights may be relatively strong, for example, when the lights are operating, and relatively less strong when not.

The method may in step (f) process all edges in the image obtained in step (c) that lie within a region or window corresponding to the mapped 2D model. By using all identified edges regardless of strength but instead assigning a weighting to the edge indicative of the strength, the method is capable of object-detection in low-light or changeable-light conditions or, for example, where other environmental conditions such as weather may reduce the strength of some edges. The lower weighting of the edges will result in less certainty of detection but allows a system using the method to degrade gracefully in its ability to detect objects rather than to simply stop working in certain conditions.

When thresholding is used, information from the image is necessarily lost. Furthermore, it becomes necessary to have an adaptive threshold which compensates for changeable light levels or other environmental factors, the threshold requiring tuning. The applicant has therefore noted that it is more productive to utilise all of the data. Productivity is additionally improved where a parallel-processing system is utilised, ‘decisions’ being expensive to processing power whereas parallel processing of each pixel—and relying on the low weighting of low strength edges—in the same manner is far more efficient.

Of course, the invention could apply some low level thresholding to remove some edges from the captured image within some aspects of the scope of the invention, which may be applicable with especially noisy environments with lots of objects.

By using a fuzzy model of an object where each edge feature is defined as one or more probability functions, for example representing a range of possible locations or orientations or strengths of an edges relative to other edge features along with a probability that the edge is present at a point in that range, rather than a precise wire frame model, and by processing this with all edges in the relevant region of the image rather than only looking at the strongest edges, it is possible from that one fuzzy model to identify a range of possible objects in the scene as long as the object has characteristics defined by the relative location of the edges of the object that fit the model. This reduces the number of models needed to be able to track and identify different objects. By repeating the process many times, the state of an object can be identified with a high degree of probability despite the fuzziness of the model.

Each edge may be defined with a centre position or direction or strength and a range which has the highest probability and with a range of probability values either side of the centre that are as high or lower until the edge of the range is reached where the probability may be set to zero. This range of probabilities may be expressed for each edge in the fuzzy model by a likelihood function which links the positon, direction or strength to the centre value as an X-Y plot where the centre value lies on the Y axis.

There may be multiple likelihood functions associated with each edge, each function having a probability distribution specifically associated with a corresponding portion of an edge.

The fuzzy model may include likelihood functions that define a narrower range of probable locations, directions or strengths where there is a great deal of commonality between different objects that fit the model at that edge, and a wider range of probable locations, directions or strengths of the edge where there is a less commonality between different objects across the set of objects that fit the model.

The step of generating the fuzzy model may comprise a step of retrieving the model from an electronic memory or wirelessly from a remote server.

Models may be generated for a variety of different objects. For example, the fuzzy model may comprise a model of a vehicle such as a passenger car and may include edges with associated likelihood functions that will fit a large number of different passenger cars. The set may, for example, include four curved edges forming circles corresponding to the wheels. As different cars will have different wheelbases and different wheel sizes, the probability values assigned to those curved edges will cover the expected range of wheel sizes and relative wheel positions. Hence, any edges in the image that define a circle within the range of probable sizes and positioned relative to each other within the range of probable wheelbases will result in a high probability that an object is a vehicle. The centre value of a circle may correspond to a diameter of approx. 50-70 cm, a fairly common wheel size, and the range may vary either side of this centre by 10-20 cm with a stepped probability to reflect that wheels on vehicles are common in a finite number of common sizes.

Where the model is a model of a vehicle, the edges may include the perimeter of the wheels, the top of the roof, the lower edge of the sills, the forward most and rearmost edges, the outline of the headlights and outline of the brake lights, the edge of the body sides. The model may also include one or more edges corresponding to the location of a shadow below an object that may be present in the scene. This is an example of an edge that is associated with an object but not part of the object but which can still form part of the model.

The edges for the lower body side and the shadow may have a likelihood function that has a narrow spread meaning the edge location will vary little between different passenger car objects, but the roof line may have a much wider spread.

The step (e) of mapping the probability distribution defined by the likelihood functions of the fuzzy model into the 2D plane of the captured image as a function of the state of the particle may comprise assigning a set of probability values to each pixel in the image, each one being defined by the set of likelihood functions for the model. These may be calculated by mapping the functions into the image plane and calculating the perpendicular distance of the pixel from a centre value of each function and then looking up the location likelihood values for that distance, and assigning the direction and strength likelihood values from each edge independent of the distance. Thus, where three different functions are used for each edge then a pixel will have three likelihood values associated with that edge assigned to it. These sets may be merged by summing all of the probabilities corresponding to all likelihood functions of the same characteristic, e.g. all the location probability values can combine to form one value for the pixel and all the direction probability values can combine to form another for that pixel.

The likelihood value for each particle may be calculated in a variety of different ways. In one arrangement the calculation may be made as shown in the pseudo code below:For each particleFor each projected edge featureFor each pixel positionCalculate likelihood value “a” based on edge magnitudeCalculate likelihood value “b” based on edge orientationCalculate likelihood value “c” based on edge distanceCalculate a combined pixel likelihood value by multiplying a, b and c.Calculate a combined pixel likelihood value by summing all the pixel likelihood valuesCalculate a combined particle likelihood value by multiplying the edge likelihood values.

In one modified arranged, pixels with zero edge magnitude likelihood could optionally be excluded from the likelihood calculations because they will automatically eliminate the need to calculate the distance and orientation likelihood but this is an optimisation and is not necessary.

The step (f) of processing the edges in the image with the probability values from the model may comprise for each pixel in the edge detected image assigning one or more of the edge values and multiplying each value by the probability value for the location corresponding to that pixel.

In use, if a pixel lies near to a predicted edge and the probability value for the location of an edge in the model is high for that pixel then the method will produce a high likelihood value for location for that pixel. The method may do the same for orientation and strength to get two further likelihood values for the pixel, where those likelihood functions are used.

The method may comprise summing all of the likelihood values produced for each pixel to produce the overall combined pixel likelihood value. The method may further comprise multiplying the combined pixel likelihood values to give an overall likelihood value indicative of the probability that the particle is present in the scene.

The method may process all pixels in the capture image, or only a subset that cover an area that is in a suitable region or window around the image location predicted by the mapped particle states.

The step of mapping the model may also comprise applying a transform to the model dependent on the properties of the device used to capture the image. This will enable distortions to be compensated if required.

The method may be implemented using images captured from a single image capture device. This may comprise a camera which outputs a colour or mono-chrome or pseudo colour image.

Alternatively, the method may comprise capturing images from more than one image capture device, each having a different field of view of the scene, and a different transform may be applied to the model for each camera to enable correct mapping of the likelihood function parameters into the image space of each image capture device. This allows the use of images from multiple image capture devices with a common set of particles, i.e. sharing a common set of particles.

Where two capture devices are provided, they may each capture a view of the scene from a different location and orientation, the two views overlapping so that predicted objects are present in captured images from both capture devices, or in some cases may not even overlap.

The method may use information about the different fields of view in the step of determining the probability of a particle corresponding to an object to provide an increased accuracy relative to the use of one of the capture devices.

The capture devices may comprise video cameras.

The method may comprise monitoring the status of each capture device, and in the event that one is at fault using only images from the non-faulty device to produce edge detected images for processing with the mapped fuzzy model. This allows for resilience in the event of a fault.

The method may comprise, after processing each particle, a further step of generating a new set of particles in the region of the particles in the initial set that were given relatively higher likelihoods, and repeating the method for those new particles. This may be repeated as long as the method is running to refine the particles. The method will detect objects whose position and motion around the host object correspond to the sequence of states predicted by the particles over recent time. The method when using this recursive process may be considered to function as traditional particle filter with a novel likelihood function.

According to a second aspect the invention provides a objection detection apparatus for locating at least one object in an environment around a host object, comprising:(a) an image capture device fitted to the host object which in use obtains at least one 2D image of the environment,(b) a processing means arranged in use to generate a set of particles that each comprises a set of parameters that define the state of at least one object that may be present in the scene,(c) calculating an edge strength and edge direction for each pixel of the captured 2D image for the production of an edge image; and in which the processing device is further arranged in use to process each particle in the set by the following steps:(d) generating a 3D probabilistic model of the object that is associated with the particle, the model defining a set of edges of the object, each edge in the model defined by at least one likelihood function defining a probabilistic distribution of at least one characteristic of the edge(e) mapping the likelihood functions of the probabilistic model into the 2D plane of the captured image as a function of the parameters of the particle; and(f) processing the edges identified in the image in step (c) with the probability values mapped in step (e) to determine the likelihood that the particle defines the state of an object present in the environment.

The processing means may comprise a signal processor that generates the model from a set of stored parameters, or that retrieves the model from an area of electronic memory in which the model is stored. The apparatus may include the electronic memory or the memory may be located remotely and accessed wirelessly.

