Scan-in polygonal extraction of video images

~ACKGROUNp_OF T~E INVENTIoN The present~nvent~on is directed t~ the scanning and storage of video images, 6uch as letter $onts and 8ymbols, for use in video graphics.

In the field of video graphics it is useful to store and retrieve various images to create a particular video picture.

In this regard, it is particularly desirable to store and retrieve predetermined alphanumeric character f onts . A ~tored library of fonts enables different types of textual messages to be selectively displayed on a video screen. Of a more general nature, it is desirable to be able to extract and store all kinds of images for selective retrieval and presentation in a video graphic display. The process of storing the characteristic features of a video image is referred to as "scan-in" of that image.

A scan-in method involves the preliminary step of providing a raster scanned version of the image, e.g. a symbol or character. For example, such a version can be obtained by taking a picture of the symbol with a video camera. The raster scanned image is analyzed to determine the characteristics of the symbol, and these characteristics are stored in a library for future retrieval.

In the past, the characteristic information describing a scanned image was stored in the form of a bit map. More particularly, each pixel of a video image was analy~ed to determine its red, green and blue color components. ~his color information for each pixel was arranged in a bit map having memory cells corresponding to the pixels of the video image.

When the character was to be subsequently reproduced in a video picture, the corresponding pixels in the appropriate por ~ of ~7600 the picture were control}ed in accordance with the information in the bit map.

~;

The bit map approach to storing scanned image information poses certain limitations if the image is to be reproduced at a size other than that at which it was originally scanned in.

For example, if it is desirable to reduce the size of the displayed image to 1/4 of the original scanned size, the information concerning each group of four pixels in the bit map must be reduced to a single pixel in the displayed image. If two of the original four pixels represent white and the other two represent black, it will be appreciated that some form of decision making criteria must be established to determine whether the single pixel in the displayed image is to be white or black. Regardless of which choice is made, the displayed image will not have the full integrity of the original scanned image. Typically, a relatively complex filtering procedure is utilized to carry out a reduction or amplification in the size of a video image. Even with such procedures, however, a loss in the integrity of the image occurs because arbitrary decisions of the type referred to above must be made.

In the field of video graphics, it is often more desireable to store information concerning an image in terms of its geometry, i.e. by means of vector representations, rather than in a pixel-related bit map. The vector information can be more easily modified to change the size of an image without losing the integrity of the image. In the past, however, vector representation has not been done with images which are extracted from a video frame, such as character fonts and symbols. ~ Further along these lines, the vector representation approach more readily facilitates the editing of character - ~29~;00 ~~mages. ~or example, it may be desirable to change the geometry of a stored character in order to smooth out a sharp corner or the like. In the bit-map approach, this change is performed by modifying the value of a bit. This type of change may become readily apparent and appear awkward when the size of the character is subsequently changed, particularly if it ~s enlarged.

However, changes in the geometry of an image that is stored in terms of vector representations are more easily accommodated.

Another advantage of the vector representation of video images lies in the fact that the information about the image is more easily transferred from one video machine to another.

Geometric information can be readily intexpreted and sent to various machines in a consistent fashion. However, pixel arrangements may vary from machine to machine, 50 that a bit mapped image that is extracted on one machine may not be accurately reproduced on another machine.

B~IEF STA EMENT OF THE INVENTION Accordingly, the present invention provides a novel scan in technique that enables in~ormation concerning character fonts and other predetermined images to be stored in terms of vector representations.

Briefly, in accordance with the present invention a binary bit map of a scanned image is created with each bit corresponding to a pixel of the image. This bit map can be created by digitizing a video image and storing it in a frame store in terms of any conventional form of color space, such as its red, green and blue component information.

If desired, it can be converted from one color space to another.

For example, the red, green, blue information can be converted into corresponding luminance, intensity and chroma information.

Each pixel is assigned a binary one or zero in dependence upon whether one or more of the color space parameters lies within a threshold range. For example, the luminance value of a pixel can be compared to a threshold valve.

Once the binary map for the image is created, rasterized polygons are extracted from the binary map. These polygons are detected and extracted through the use of a crack following algorithm. Basically, this algorithm locates the interface between a group of contiguous pixels all having the same binary value, e.g., all ones, and the adjacent pixels of the opposite value. These interfaces are closed loops which define rasterized polygons and can be identified by means of coordinate values related to the grid of pixels.

The rasterized polygons are smoothed by an approximation technique to generate a piece-wise linear polygon. This -4 - læ~7600 approximation technique preferably utilizes recursive adaption with a user defined tolerance to provide an optimal fit. The sides of the resulting linear polygon can be represented as vectc~rs in a coordinate system. Thus, the invention enables character fonts and other predefined images to be stored as vector representations.

Further features of the invention are described in detail hereinafter with reference to a preferred embodiment illustrated in the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS Figure 1 is a partial perspective and partial block diagram view of a scan-in system which operates in accordance with the in~ention;

Figure 2 is a binary map representation of a character;

Figure 3 is an illustration of the rasterized polygon that is extracted from the binary map of Figure 2;

Figure 4 is an enlarged view of a binary bit map;

Figures 5A-5C are examples of portions of a bit map illustrating the steps that are followed in the crack-following algorithm;

Figure 6 is an illustration of the bit map of Figure 2 after the exterior polygon has been extracted; and Figure 7 is an illustration of the steps that are followed in the procedure for fitting the rasterized polygon with a piec~-wise linear polygon.

DESCRIPTION OF THE ILLUSTRATED EMBODIMENT As an illustrative example, a preferred embodiment of the present invention will be described in the context of -5 ~ 29'7600 scanning in a particular font for the l~tter "A". It will be appreciated, however, that the invention is not 50 limited, and can be applied to the extraction and storage of any video image.

Referring to Figure 1, a video image of the desired character font can be obtained by taking a picture of the character at full video screen size with a video camera. A sheet of paper 10 or other medium containing the character is placed on a table 12. A video camera 14 produces an output signal containing information regarding the image. Typically, this output signal presents the information in terms of t~e red, green and blue components of the scanned image, although it could be in terms of any other type of color space. This information is digitized in an analog-to-digital converter 16 and stored as a frame of video information in a frame store 18. The scanned and stored image can be displayed on a video monitor 20.

The image to be scanned in need not be produced by a video camera. It can come from any suitable source of video images. For example, it can be replayed from a video tape or retrieved from any other type of video storage medium, or it can be generated using video graphic techniques.

As a first step in defining the character font, the scanned video image is transformed into a binary image. In a preferred embodiment of the invention, the red, green and blue (RGB) information for each pixel in the frame store 18 is converted into corresponding luminance, intensity and chroma (YIQ) information. The technique for making such a conversion is conventional in the art, and therefore will not be discussed in detail herein. It can be carried out, for example, by means of a suitable programmed central processing unit 22 connected to the frame store 18.

The YIQ information for each pixel is th~n transformed into a binary bit of data by thresholding that information. For example, if the scanned image comprises a relatively dark character on a light background as ~hown in Figure 1, the luminance ~Y) value for each pixel provides a good basis for obtaining the binary data. In particular, the threshold range might be established as 0 to 0.3, where a zero luminance value represents black and a one luminance value represents white.

Each pixel having a luminance value less than the threshold value of 0.3 would be labelled with a binary one, and all pixels having a luminance of 0.3 or greater would be labelled a binary zero.

For the character shown in Figure 1, the binary pixel map might appear as illustrated in Figure 2, and is stored in a binary image memory 24.

Depending on the particular image ~eing scanned, other thresholding criteria might be more preferable. For example, if the desired character appears on a multi-color or patterned background, chroma (Q) or intensity (I) might prove to be better parameters on which to base the thresholding decision. Furthermore, it is possible to use a combination of two or three of these parameters (e.g. 0.5Y + 0.3I + 0.2Q > x, where x is the threshold value) to determine whether a pixel in the binary bit map has a value of one or zero. Also, the thresholding decision can be carried out relative to multiple threshold values that define a window, e.g. 0.3 < Y < 0.6, to determine binary the value of a pixel. Similarly, the parameters that are used in the thresholding function might be those defined by another type of color space, e.g. the R, G and B values.

Once the binary pixel map is created, one or more polygons which define the shape of the character are extracted -7 ~297~00 ~-~rom it. These polygons all fall into one o~ two categories, exterior polygons and interior polygons. Figure 3 illustrates that the character "A" shown in Figure 2 has one exterior polygon 26 and one interior polygon 28. These polygons ~re re~erred to as "rasterized" polygons since they have shapes which are defined by the edges of the pixels in the raster-scanned image.

The polygons are extracted by locating the interface, ~r "crack", between the groups cf pixels which are all binary ones and the adjacent binary zero pixels. To locate the crack, the binary pixel map is scanned on a line by line basis, and ad~acent pairs of pixels are analyzed to determine whether they contain significant data. Significant data is detected wben two adjacent pixels respectively contain different binary data. With reference to the binary pixel map of Figure 2, it can be seen that the first row of the map, which contains all zeros, does not represent significant data. In the 6econd row of the map, a 0,1 sequence of bits occurs at the upper left hand corner 30 of the character. The detection of this sequence represents the start of a crack.

Once this start is located, a crack following algorithm is carried out to define the ~hape and extent of the crack. The operation of the cracX following algorithm is illustrated with reference to the 4 x 4 binary pixel map illustrated in Figure 4.

It is assumed that the O,1 sequence of bits occurring in the second row of the map has been detected to locate the start of a crack. The occurrence of a O,l bit pattern represents an exterior polygon. The lower left hand corner of the 1 pixel is assigned a starting coordinate value 0,0, and a pointer is oriented to proceed in the upward direction. In the extraction of an exterior polygon, the pointer then advances up to the 7600 coordinate point 0,1. The value of the 4 pixels ad~acent this coordinate point ar~ then detected to determine t~e next direction in which to advance.

At each point along the crack, there are three possible directions to proceed, i.e. right, left or 6traight. These three possibilities are illustrated in Figures 5A-5C. ~f any other bit pattern should be present, it will be recognized as an error condition, i.e., the pointer is not located on the crack.

In dependence upon the particular one o~ the three conditions that i~ detected, the pointer advances in the direction indicated by t~e detected condition. Thus, with reference to the bit map of Figure 4, once the pointer is located at the coordinate position 0,1 the crack following algorithm will indicate that a right turn must be made. The pointer will then ad~ance to the position 1,1. At this point, the algorithm will dictate that the pointer continue to move in a straight direction, to the coordinate point 2,1. This procedure continues, with the algorithm causing the pointer to advance to each successive point along the crack between the group of three contiguous pixels having the value of one and their adjacent zero pixels.

As the pointer proceeds around the crack, the coordinate value of each point is recorded. Thus, the output of the algorithm comprises a string of coordinate values which define the crack, or rasterized polygon, around the group of binary one pixels. In the example of Figure 4, this pixel string is as follows: (0,0), (~,1), (1,1), (2,1), (2,0), (2,-1), (1,-1), (1, o) .

Further information regarding crack following algorithms can be found in Rosenfeld and Kak, Piaital Picture 129760Q cessin~, AcademiC Press, 1982, particularly pages 219-231.

The algorithm is carrie~ out in the CPU 22, preferably by means of A look-up table which determines the orientation of the pointer as the values of each set of pixels is detected. The coordinate values that are generated by the algorithm are stored in an appropriate memory unit 25.

Once the polygon has been defined, the crack locating procedure continues to determine whether any;other polygons exist within the binary pixel map. ~or example, after the exterior polygon 26 of the character illustrated in Figure 2 has been determined, the interior polygon 28 must also be detected and followed. It will be appreciated that as the search for additional polygons is carried out, a O,l bit sequence 32 will be detected in the third row of the binary pixel map of ~igure 2.

This could cause the exterior polygon of the character to again be followed. Preferably, to prevent such duplicative effort, each binary one pixel that is detected during the crack following algorithm is labelled with an indicator. For example, the binary one value of the pixel can be changed to some other value, such as a "V" to indicate that the pixel has been visited. In this case, the binary pixel map will appear as shown in ~igure 6.

Thus, as the search for additional polygons continues, each pixel that is labelled with a V will not be detected as representing significant data.

The ~earch for other polygons will continue until the ~ourth row of the map is scanned, at which time the 1,0 bit sequence 34 will be detected to indicate the start of an interior polygon~ In the previous example regarding the tracking of an exterior polygon, the algorithm pointer followed the crack in a -10 ~ 297600 clockwise direction. In order t~at the area o~ both exterior and interior polygons be consistently defined, the algorithm proceeds around the interior polygon with ~ counterclockwise orientation.

Thus, the starting point for the crack comprises the upper left hand corner of the zero pixel in the 1,0 sequence. The algorithm then proceeds in the same fashion to follow the interior crack.

As it proceeds, each coordinate value of the crack is detected and emitted in a pixel string. In addition, the value of each binary one pixel is changed to the V indicator.

The character illustrated in Figure 2 comprises only two polygons. Thus, after the interior polygon has been followed to generate the second pixel string, no further 0,1 or 1,0 pairs will be detected in the map. Accordingly, the boundary of the character font is defined by the two pixel strings representing the exterior and interior rasterized polygons shown in Figure 3.

As a final step in the scan-in procedure, the rasterized polygon is smoothed by fitting it with a piece-wise linear polygon. This fitting technique is preferably carried out by means of recursi~e adaption with an operator-defined resolution.

Such a technique is illustrated with reference to Figure 7. This figure illustrates, in solid lines, a rasterized polygon 36 that is to be fitted with a piece-wise linear polygon.

To initiate the fitting process, two extreme points A,B on the rasterized polygon are identified and a straight line 38 is drawn between them. The largest distance dl between this line 38 and the polygon 36 is measured. I f this distance is larger than an operator settable tolerance, the original line 38 is disregarded and a new test line 40 is drawn between the starting point A and the point C on the polygon which was farthest from the line 38.

The distance d2 between the new line and the polygon is then mea ~29~7600 sured. If this distance is within the tolerance, the line 40 ismaintained ~s a side of the piece-wise linear polygon. Another line 42 is then drawn between the points B and C. Since this line coincides with the rasterized polygon, it will be maintained as part of the ultimate polygon.

This procedure continues until a complete polygon 44 (represented by the combination of dashed and heavy solid lines) i8 complete. The coordinate values of the corners of this polygon, i.e. the points A, B, C, etc., are stored as a vector representation of the polygon which defines the character or symbol. If the operator desires greater resolution in the definition of the polygon 44, the tolerance level can be suitably ~d;usted.

By storing the image as a vector representation of a polygon, editing of the image, lncluding size enlargement and r~duction, is readily facilitated without compromising the integrity of the displayed image. Since all of the sides of the polygon are linear, appropriate magnification is obtained by simply multiplying the length of each side by the magnification factor and determining new coordinate values corresponding to the new lengths. Similarly, the shape of the polygon can be edited by merely adding or changing coordinate points. For example, in the polygons ilîustrated in Figure 7, an additional coordinate value corresponding to the point 46 in the rasterized polygon can be added to the vector representation to vary the shape of the corresponding corner in the linear polygon.

It will be appreciated by those of ordinary skill in the art that the present invention can be embodied in other specific forms without departing from the spirit or essential characteristics thereof. In particular, although disclosed with -12 '' ` 1297~;00 respect to the scan-in of a character font, it can be used for the extraction of ~ny video image. The presently disclosed embodiment is therefore considered in all respects to be illustrative and not restrictive. The scope of the invention is indicated by the appended claims rather than the foregoing description, and all changes that come within the meaning and range of equivalents thereof are intended to be embraced therein.

-13