The invention relates to techniques for producing a set of outlines from the picture data contained in a video image such that further image processing may be performed on the outlines thus generated. Such outlines are typically used in 3D image modelling systems, print systems, and systems which perform other image transfoπnations.

The picture data in a video image will consist of an array of pixel luminance or colour values. The outline data will be a contour describing seme aspect of the image. Typically the contour will be defined as a sequence of (x, y) c-o-^rdinate pairs, but contours can also be defined as sequences of curves of various kinds such as circular arcs or cubic splines. Such outline contours may be generated for parameters of the image such as luminance or colour component values.

A typical use of the technique is to produce an outline description of, for example, a font character from a video image which has been scanned in by pointing a TV camera at an image of the character and frame-grabbing the result. Let us suppose the resulting image is represented in a frame buffer by a grey-scale with eight bits of luminance precision. The scanned image of the character will typically consist of dark grey pixels within the strokes of the character against a light grey background. Pixels on the boundary of the dark and light areas will have intermediate luminance values depending on the relative proportions of the dark and light σαπpαnents of the image which fell on the sensor corresponding to that pixel in the TV camera or scanner.

A known method for producing an outline from a grey-scale image is to -Implement a discriminator function in a hardware circuit or in software. This is used to decide whether or not a given pixel lies inside or outside an outline describing some parameter of the image. For example, a discriminator function could be used to return the value TRUE if the luminance value is below half maximum and FALSE if it is above half maximum. This would mean that all pixels less than mid-grey would be considered to be outside the

SUBSTITUTESHE T

outline, otherwise they are inside it. This would yield a set of outlines appr-oximately su-α-Ounding the dark areas of the image and thus approximating the outlines of the original character.

The discriminator circuit receives individual pixels in turn from each row of pixels starting with the top row and α-nt ^* inuing to the last from an image such as that shown in Figure 1. Starting with the extreme left-hand pixel each pixel in the row is considered and the position of a pixel where the c- scriminator function changes value from one pixel to the next is recorded. In the image of Figure 1, the top scan line consists entirely of background pixels 2 and thus no changes in the discriminator circuit output will be recorded for this scan line. The second scan line has background pixels 2, dark grey image data pixels 4 and two intermediate value pixels 6 which are less than mid-grey.

Continuing down the image fran the top to the bottom and considering each scan line in turn the pairs of outline edges are defined all the way down the image until they either meet (which is signified by the fact that they do not appear on the next scan line down) or go off the bottom of the image (in which case they can be assumed to be closed along the bottom of the image for convenience).

Thus for the example of Figure 1 an exterior contour 8 and an interior contour 10 are defined by the locations of changes in the c-Liscximinator c-Lrcuit output. Cto-ordinate pairs or curves defining the outlines 8 and 10 can then have transformations performed on them by an image modelling system and the resultant image can be mapped back into the frame buffer.

The outlines generated are only available at a resolution of one pixel and this can lead to errors when the image defined by the outlines is mapped back into the frame buffer after a transformation.

In the past it has been considered that the way to improve the detail and accuracy of the outline description is to increase the resolution of the scanner and the frame-buffer containing the video image.

One object of the present invention is to make use of the grey- scale information in the image to achieve a resolution of sub-pixel accuracy in the outlines with a scanner of the same resolution.

SUBSTITUTE SHEET

The invention is defined in the appended claims to which reference should now be made.

The invention will now be described in more detail by way of example with reference to the drawings in which:

Figure 1 shows outlines as would be defined by a prior art system;

Figure 2 shows how pixels can be interpolated to a higher resolution in an embodiment of the invention;

Figure 3 shows a block circuit diagram eiribodying the invention; and

Figure 4 shows a line produced by filtering the outline produced on a pixel by pixel basis.

In an embodiment of the invention an image is produced at a higher resolution (for example two or four times the horizontal or vertical resolution) by interpolating from the pixels of the original image onto the higher resolution one. Only the area of the image being considered by the ciiscriminator circuit need be expanded to the higher resolution at any one time, i.e. there is no need for a complete high resolution frame store. If we are interested in outlines defining changes in luminance values, we consider the image to consist of luminance values which smoothly vary between the pixel centres, and calculate what values they would have at the centres of the new sub-pixels. These sub-pixels could have their luminance values defined to a resolution of, for example, 8 bits.

An example of a linear interpolation onto a raster of twice the original horizontal and vertical resolution is shown in figure 2. In this the pixels of the original image are shown by the bold lines and have their centres at a, b, c and d. The sub-pixels to be interpolated fram this image are shown by the feint lines and the centres of four of them are shown at e, f, g and h. The sub-pixel luminance value at e would be calculated from the pixel luminance values at a, b, c, and d by the linear interpolation: e = (9d + 3b + 3c + a)/16

A similar type of interpolation would be used to derive values for f, g and h.

The values of the sub-pixels generated are then used by a discriminator circuit which is responsive to, for example, changes

SUBSTITUTE SHEET

between less than and greater than half maximum luminance value at the accuracy of the luminance values assigned to the sub-pixels. The co-ordinate locations where the output of the discriminator circuit changes can then be recorded to sub-pixel accuracy.

A block circuit diagram embodying the above technique is shown in Figure 3. This comprises a frame buffer 10 which receives an image frcm a camera 12. Data from the frame buffer 10 is scanned out line by line and is received at an input to an interpolator 14. This interpolator will comprise various line and pixel delays, adders and multipliers to produce values of a chosen parameter of the image at the sub-pixel resolution. The interpolator may operate according to the equation given above or, may take contributions from either a greater or lesser number of the adjacent pixels using predetermined interpolation equations.

After interpolation, pixel values for the chosen image parameter are supplied in scan line order to a Lscriminator circuit 16 which is preferably sensitive to changes in luminance values at a higher resolution than that of the original image. The discriminator may be a comparison circuit. When the parameter value passes through a predetermined threshold level the output of the discriminator circuit 16 changes frcm say TRUE to FALSE. This change is detected by a detector circuit 18 coupled to the output which is in turn coupled to a memory block 20 via a filter 19 and which causes the coordinate location of the change in output state of the discriminator 16 to be written into the memory 20.

It will be appreciated that without the filter 19 the outlines produced by the above method are still jagged but at a much higher resolution.

It is possible to implement the invention without using a full frame buffer. This is particularly useful where images having a very high initial resolution are being used or where it is desired to track the movement of an object in a sequence of video images. In such an application only a few lines of video data need to be stored at any one time. The total that needs to be stored is of course dependent upon the interpolation algorithm being used and an algorithm that only interpolates with horizontally adjacent pixels will only require a few pixels to be stored at any one time.

SUBSTITUTE SHξET

In order to get rid of the jagged appearance of outline contours obtained in this way it is useful to apply techniques which effectively filter out the spatial frequency caused by the sub pixel sampling resolution. This is implemented in the filter 19. For example, in figure 4 in which the outline 22 is moving more rightwards than downwards, if instead of following the outline of each of the pixels one instead follows a line which passes through the centre of the right hand edge of the final interior pixel in each scan line for that outline 22 then a much straighter and less noisy outline 24 is obt i ed. In fact straight edges in the original will appear as straight edges in the outline using this technique, but only at the resolution of the outline 22.

Other filtering methods for removing sampling noise from the outline can give further iπprovement.

For example, best straight lines or higher order curves could be fitted to the co-ordinates of the centre of each pixel edge defining the outline. Thus a vector representation of the outline could be derived.

If the same iltering methods are applied with the enhanced method after an outline has been produced using the interpolated higher resolution raster this more precise outline can be improved by the same methods.

One alternative edge detection method which can be used to find the path of the contours involves using an algebraic interpolation to find the path of a higher resolution contour through a box defined by four pixels on two adjacent lines. An estimate is first made as to where the edge passes through one line or enters the box via a pixel boundary. An estimate is then made as to where the edge passes through the next line or leaves the box via a pixel boundary.

The estimate as to the position of the contour entering and leaving the box is made by an interpolation between the values of the parameter under consideration at the corners of the box. Knowledge of the path of the contour t-hrough the box can be improved by knowledge of the values of the parameter at the sub-pixel positions e, f, g, and h of figure 2.

SUBSTITUTE SHEET

In practice only the coordinate value of the contour crossing a pixel boundary need be stored and then used for further image processing.

Any outline produced with the high resolution method will be positioned to sub-pixel resolution compared to the traditional method.

It can be seen that the sampling of the image at a higher resolution (higher spatial frequency) has allowed an improved outline to be obtained. The outline can also be post-filtered at the higher resolution (higher spatial frequency limit) . Thus a more accurate representation of the original outline is reproduced.

SUBSTITUTE SHEET