DIGITAL DATA PROCESSINGThis invention relates to digital data processing. It relates particularly to digital data information which is present in a stored digitised image matrix and to a method of and means for detecting significant features in the stored information.
When it is required to view a particular digital image automatically, it is usually necessary to identify corner and edge features since these correspond to the outlines of objects and to prominent surface markings which are present in the stored image.
This operation gives a quantity of low-level information which can be used for further work, but it is most important that the data extracted at this early stage should be of a reliable quality.
A description of the edge features present in an image is only helpful for certain parts of the image. For other parts of the image, the so-called image corners, corresponding to edge junctions and sharp bends in edges, and to isolated point-like features, are important. Where the kind of feature to be expected in the image is not restricted in any way, for example, in a depiction of a natural scene, then merely to describe the image in terms of edges alone or of corners alone would be incapable of providing understanding of the whole amount of the information present.
Some data processing methods have been proposed which will extract either edge or corner information from an image matrix. One edge extractor is the Canny edge filter. However, this device can suffer from an inability to form edge junctions and it may be necessary to perform an additional heuristic processing operation in order to overcome this problem. In addition, in textured regions of the image, edges can sometimes form a poor and unreliable descriptive feature and this therefore may lead one to prefer a corner description.
Some of the best available corner detectors have been proposed by Moravec, Nagel, Beaudet and Kitchen & Rosenfeld. These corner detectors are, however, not ideal since they can be temporally inconsistent in their responses (that is, they are unreliable), and they can respond too readily to the presence of small imperfections in strong image edges.
The present invention was devised in an attempt to overcome some of the disadvantages of both edge and corner feature detectors.
According to the invention, there is provided a method of processing digital data in a digitised image matrix in order to detect the positions of any sharp intensity variations present in adjacent ones of the pixels representing said image, the method comprising the steps of comparing the intensity of each primary pixel with those of the secondary pixels which surround it, calculating whether said primary pixel can be classified as having a constant, an edge-like or a comer-like value, and collating this information to give positions of both edge and corner features which are present in said image matrix.
Conveniently, before said comparison stage, the original image matrix may be processed to form an intermediate simplified image which excludes unnecessary detail. This intermediate image may be a quaternary image.
In one embodiment, the method may include the further step of taking a second digitised image matrix after a given time interval has elapsed, and comparing the processed digital area of the said second image with that of a first image, such that any change in the positions of the selected features of the images will be detected.
By way of example, a particular embodiment of the invention will now be described with reference to the accompanying drawing the single Figure of which shows a block diagram of the main components of an image motion surveillance detector.
The detector device of the invention will first be described with reference to the main components shown in the Figure and the operation of the feature extraction stage will be explained later.
The surveillance detector comprises a video camera 1 which provides information for a digital data processor 2 and this acts to supply output signals on an output line 3. The processor 2 receives input signals from the video camera and these are delivered to an image digitisation stage 4. After this stage, the input information is passed into a frame store 6 and the pixels in this store are then processed in turn by a corner/edge feature extraction circuit 7.
The data obtained from the feature extraction circuit 7 is then applied to a feature matching block 8. In parallel with this, the data is also fed into a delay block 9 which will hold this data for a predetermined time interval before delivering it to the block 8.
At the feature matching block 8, the extracted features of the data stream are compared with the set of features which is compiled after the predetermined time interval. The information obtained is thus able to show any movement of the selected extracted feature which has taken place during the specified time interval. From this information it is possible to calculate the location and image velocity of a moving body which is viewed by the video camera 1.
In order to detect the presence of a sharp intensity variation in adjacent ones of the pixels representing the image matrix, it is first necessary to compare the intensity of light at one primary pixel with the intensities of each of the secondary pixels which surround it.
There may be at least twentyfour of the secondary pixels, or possibly several hundred A local auto-correlation function for each of the primary pixels is thus required and this will describe whether the local patch of image intensities, represented by the possible total of twentyfive pixels, is approximately constant in value, is edge-like, or is cornerlike. Corners are indicated by the auto-correlation function being sharply peaked, and edges by the auto-correlation function being ridge shaped. The explicit auto-correlation function may not need to be calculated, but only a determination of its second-order expansion about the origin may be necessary. A mathematical specification of these requirements will now be given.
Let the (possibly pre-smoothed) image intensities be represented by the array of values Ix,y, where x and y are theCartesian image coordinates. To start with, the two first gradients are calculated, thusXx,y = I x+1,y - 1x-1,y Yx,y = Ix, y+i - IX9Y-1 Next, the smoothed quadratic gradients are calculated A = X2 * WB =y2 * WC=(X.Y)*W where * represents convolution, and W is a smoothing-filter, an explicit example being(1 2 1) W = (2 4 2)(1 2 1)Finally, the corner/edge response, R, is calculatedR = (A.B-C2) - k(A+B)2 a value of 0.1 being typical for the parameter k.
The presence of a corner region is indicated by the value for R being large and positive. An individual pixel is deemed to be a corner if its response, R, is larger than the responses of each of its eight neighbouring pixels. Similarly, an edge region is indicated by R being large and negative. A pixel is deemed to be an edge pixel if its response, R, is smaller (more negative) than its two neighbours in either the x or y direction, depending on which of the first gradients,X and Y, are larger in magnitude.
Standard edge clean-up algorithms (similar to those used in theCanny edge filter) are applied to the edge image, to remove short lines and spurs, and to complete breaks in edges. The result is a quaternary (that is, a four-state) image, with each pixel classified as a corner, a corner neighbourhood, an edge or a background. The edges are thin (that is, they are one pixel in width) and run between the corner regions. The problem of junction formation is overcome by the presence of corner regions surrounding the corners, at which regions the edges terminate. The problem of edge inconsistency in textured image regions is overcome by their being represented by regions containing corners but few edges.
One way of effecting the necessary calculations would be by processing the data by means of an off-the-shelf microcomputer, with the algorithm being implemented in either high or low-level software. The input to the microcomputer would be digitised images, and the output would be the locations and image velocities of the required feature combinations. However, due to the number of calculations involved, use of a microcomputer would be relatively slow, and this slowness will be undesirable for time-critical applications.
For the time-critical applications, special-purpose hardware could be constructed to calculate the intermediate images X, Y, A, B, C and R, and to select appropriate local maxima or minima values of the corner/edge response R as corner or edge pixels respectively.
This proposed special-purpose hardware would be pipelined, and make use of convolution chips and other dedicated VLSI circuits.
This step would be followed by stages for edge clean-up and feature tracking on one or more microcomputers.
Where the scene viewed by the video camera can be expected to change with the passage of time, the invention can be used to process a second digitised image matrix after a given time interval has elapsed. The processed data of the said second image can then be compared with that of a first image so that any change in the positions of the selected features of the images will be detected.
Use of the digital data processing method has been proposed in the construction of passive equipment for surveying a scene, such as for a burglar alarm system. With imagery acquired from a static surveying camera, any consistent motion of edge and corner features will indicate a moving target whilst inconsistent motion may be due to image noise, wind-blown vegetation etc. In a traffic control application, the method can be used to detect the presence of moving vehicles. Since the digitised image could be produced from infra-red radiation rather than visible light, the system could still work effectively at night-time or in bad weather conditions.
Use of the data processing method for the automatic scanning of cytological cell material has also been proposed.
The foregoing description of an embodiment of the invention has been given by way of example only and a number of modifications may be made without departing from the scope of the invention as defined in the appended claims. For instance, although the invention has been described as a method of processing the data in a single image matrix, this would be equally applicable to processing material from two or more image matrices, so that a three-dimensional effect could be obtained.