Method of pixel to vector conversion in an automatic picture coding system

• US 4,777,651 A
• Filed: 06/25/1984
• Issued: 10/11/1988
• Est. Priority Date: 06/25/1984
• Status: Expired due to Fees

• Current Assignee: Tektronix Incorporated (Fortive Corp.)
• Original Assignee: Tektronix Incorporated (Fortive Corp.)
• Inventors: McCann, Benjamin E., Rieger, Michael L.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/624,434
• Time in Patent Office: 1,569 Days
• Field of Search: 382/21, 382/22, 382/25, 382/55, 382/56
• US Class Current: 382/242
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding

Abstract

An automatic picture coding system including a method for converting a bit-map image of the picture to vectors as the picture is being scanned. The bit map is delayed as it is being generated to form a series of tessellations or windows of data. The windows are propagated through a series of neighborhood-logic elements which perform data transformation operations such as growing, smoothing and thinning of the bit-map image. A bit stream output from the neighborhood logic which output includes only line and edge features of the original picture is transferred serially to a microcomputer where the features are partitioned into a plurality of line segments. Each line segment is chain coded and temporarily stored, as it is acquired, in a corresponding one of a plurality of lists, the lists being linked in an order corresponding with the order in which the segments are acquired. When the storage of each chain-coded segment is completed, the segment is converted to vectors and transmitted to a user device for display, storage, or further processing, the lists in which the converted segments were stored being unlinked and deallocated. The process is continued until the entire document has been scanned and converted to vectorial data.

Claims

1. A method of encoding pictures, comprising the steps of:

raster scanning a picture;

generating, as the picture is being scanned, a bit map representative of the features of the picture;

regenerating the bit map, as the picture is acquired during the scanning and generating steps, as a bit stream representative of line and edge features of the picture;

temporarily storing, as the bit stream is regenerated, those portions of the bit stream which represent the line and edge features of the picture, said temporary storing step including the steps of

converting the bit stream, as it is regenerated, into a plurality of chain-coded line segments; and

storing the plurality of chain-coded line segments, as the scanning and regenerating steps continue, in a corresponding plurality of storage elements linked in an order corresponding with the order in which the features of the picture are encountered during the scanning, generating and regenerating steps;

converting each stored line segment to vectorial data;

transmitting the vectorial data to a user device; and

continuing the preceding steps until the entire picture is scanned and encoded.

2. The method of claim 1, wherein the first converting step includes the step of generating a chain code for each element of the bit stream, the chain code having a directional component corresponding with the direction of the associated line segment in directions corresponding with the general directions in which the picture is raster scanned.

3. The method of claim 1, which includes the steps of:

allocating each of the plurality of storage elements when the corresponding line segment is first regenerated; and

deallocating each of the plurality of storage elements after the corresponding line segment is converted to vectorial data.

4. The method of claim 1, wherein the first converting step includes the step of delimiting the start and the end of each line segment.

5. The method of claim 4, comprising the steps of:

allocating each of the plurality of storage elements when the start of the corresponding line segment is delimited; and

deallocating each of the plurality of storage elements after the corresponding line segment is converted to vectorial data.

6. The method of claim 4, wherein the storing step includes the step of storing the spatial location of the start of each of the line segments in the corresponding one of the plurality of storage elements.

7. The method of claim 1, wherein the regenerating step includes thinning the features of the bit-map representation of the picture.

8. The method of claim 1, wherein the storing step includes concatenating two or more line segments which together have a spatial orientation transverse to the general direction of scanning of the picture for storage in a single one of the plurality of storage elements.

9. A method of encoding pictures, comprising the steps of:

raster scanning a picture with a detection device;

acquiring, as the picture is being scanned, a representation of successive portions of the picture in the form of a bit map;

regenerating the bit map as the picture is acquired during the scanning step as a bit stream representative of line and edge features of the picture;

encoding the bit stream as it is generated in the previous step as a plurality of chain codes representing discontinuous contours, each contour representing a segment of the regenerated features of the picture, each of the contours including at least one of the chain codes, each of the chain codes having a directional component corresponding with the general directions in which the picture is scanned;

storing each of the chain codes successively in a storage element corresponding with the contour with which the chain code is associated, the storage elements being ordered in the same order in which the contours are intercepted as the picture is scanned;

converting each of the chain-coded contours, as each is completely generated, to a vectorial signal set representing an abstraction of the chain-coded contour; and

transmitting the converted contours to an output device for display, archival storage, or further processing.

10. The method of claim 9 which includes simultaneously with the transmitting step, the step of:

removing from the ordered storage elements each of the storage elements corresponding with a transmitted contour.

11. The method of claim 9, wherein the encoding step includes the steps of:

classifying each element of the regenerated bit stream as at least one of the classes of contour elements including a contour beginning, a contour end, and a contour continuation; and

generating one of said chain codes for each contour beginning and each contour continuation.

12. The method of claim 11, which includes, simultaneously with the transmitting step, the step of:

removing from the ordered storage elements those storage elements corresponding with a converted contour, when the converted contour has been transmitted.

13. Apparatus for automatically converting a document to machine script, comprising:

means for raster scanning said document;

means coupled to said scanning means for generating a series of tessellations of black and white pixels from said scanned document, each of the tessellations including a center pixel and adjacent pixels surrounding the center pixel;

means for regenerating the series of tessellations as a bit stream having a plurality of elements, each element of the bit stream corresponding with a tessellation having a black center pixel, the bit stream being representative of line and edge features of the scanned document, such features including a plurality of discontinuous contours;

means receiving the bit stream for classifying in succession each element of the bit stream as a unique set of contour segments, which set includes at least one of the contour segments representing a contour start, a contour end, and a contour continuation;

means for generating a data item representing the directional orientation of each of the contour start segments and each of the contour continuation segments in directions corresponding with the general directions in which the document is scanned;

means for storing the data items representing each of the plurality of contours, each said storage means being associated with one contour and allocated responsive to said classifying means when a contour start segment associated with said one contour is received, the one contour being stored in the associated storage means as the data items representing the contour continuation segments of the one contour are successively received while the document is being scanned by said raster scanning means, each of the plurality of storage means being ordered in accordance with the relative order of the contours as successively received in the bit stream;

means responsive to said classifying means receiving a contour end segment for converting the stored contour associated with the received contour end segment to a vectorial data set representing an abstraction of the associated stored contour, and including means for deallocating the storage means corresponding with the converted contour; and

means for utilizing the vectorial data set.

14. The apparatus of claim 13, wherein each said storage means includes means for storing a data item representing a starting location on said scanned document of the contour stored therein.

15. A method of encoding pictures, comprising the steps of:

raster scanning a picture;

generating, as the picture is being scanned, a bit map representative of black and white pixels of the scanned picture;

regenerating from the bit map as it is acquired during the scanning step, a bit stream having a plurality of elements representing line and edge features of the picture, the bit stream representing a linear concatenation of successive rasters of the bit-map representation of the picture;

temporarily storing the line and edge features of the picture, said temporary storing step including the steps of

decoding each element of the bit stream successively as it is generated, the decoding step including the steps of

partitioning the features of the picture into a plurality of linear contours, each of the contours including one or more contour segments, each contour segment having an orientation with respect to the picture being scanned;

classifying each contour segment as one of a class of contour segments including a contour-start segment, a contour-end segment, and a contour-continuation segment; and

assigning a chain code to each contour-start segment and each contour-continuation segment of the bit stream element according to its orientation and in the general directions in which the picture is raster scanned;

allocating a storage element for each contour-start segment decoded;

storing in the allocated storage element a data item representing the spatial location of the contour-start segment;

storing the chain code corresponding with the contour-start segment in the allocated storage element;

linking the allocated storage element with other such storage elements in an order corresponding with the order in which the contours are decoded; and

storing each chain code representing a contour-continuation segment in the storage element associated with the contour;

converting each of the temporarily stored chain-coded contours to a vectorial signal set which is an abstraction of the chain-coded contour when a contour-end segment associated with the contour is decoded;

transmitting each of the converted contours to a user device;

unlinking and deallocating each of the storage elements associated with the converted contours; and

repeating the above steps until the entire picture is scanned and encoded.

16. The method of claim 15, wherein the classifying step includes the steps of:

detecting a combination of contour segments including two contour-start segments together having an orientation transverse to the general direction of scanning of the picture;

temporarily storing in another storage element the detected combination of contour segments, thereby concatenating the transversely oriented contour segments; and

copying the contents of the other storage element into one of the allocated storage elements.

17. The method of claim 16, further including after the copying step the step of storing another contour in the one allocated storage element, thereby appending the other contour to the concatenated contour segments.

18. The method of claim 16, wherein the copying step includes the step of appending the concatenated contour segments to another contour previously stored in the one allocated storage element.