Apparatus and a method for storage and retrieval of image patterns

• US 4,020,463 A
• Filed: 02/27/1976
• Issued: 04/26/1977
• Est. Priority Date: 02/27/1976
• Status: Expired due to Term

• Current Assignee: Recognition International, Inc. (BancTec Incorporated)
• Original Assignee: Recognition Equipment Incorporated
• Inventors: Himmel, David P.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/661,814
• Time in Patent Office: 424 Days
• Field of Search: 340/146.3 H, 340/146.3 AC, 340/146.3 AE, 340/146.3 AH, 340/146.3 MA, 340/324 A, 340/324 AD, 340/146.3 SY, 178/DIG. 3
• US Class Current: 382/242
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06V 40/30 Writer recognition; Reading and verifying signatures
• CPC Class Codes: H04N 1/411 for the transmission or storage or reproduction of two-tone pictures, e.g. black and white pictures

Abstract

A line image or a line signature is optically scanned to generate digital signals for storage in an image matrix. These digital signals represent black and white cells defining the line signature or line image and are initially processed by tracing the image boundary. During the tracing a "thinning" or "peeling off" operation is performed that evaluates black cells in the image matrix for conversion into white cell digital signals. This thinning or peeling off process, also identified as data compression, continues until the line signature or line image is composed of a single cell thickness. The final phase of the data compression operation includes another boundary tracing of the one cell thick image, and connecting a sequence of boundary points defining each black cell to form a string of vectors which represent the signature. The resulting vector catalog comprises a composition of data including a vector starting point and vector directions which are encoded and stored for future retrieval. When a stored line signature or line image is to be retrieved for display, the encoded vector data is recalled from storage to generate on a cathode ray tube the original vector data. This operation is known as data decompression and produces on the cathode ray tube a synthesis of the original line image or line signature. The compression and decompression operations, except thinning or peeling off, are also applicable to textured images or images having grayscale and thickness. Such textured images are first subdivided into binary images, each representing one bit of the grayscale, then the vector boundary encoding process is completed without thinning. The encoded vectors are stored for subsequent retrieval and display.

Claims

1. Apparatus for compressing a pattern of digitized input data having a multiple bit width for removal of excess information and converting into a vector pattern, comprising in combination:

an image matrix for storing each value of digitized input data produced by pattern scanning.

a process array within said image matrix through which the digitized input data in the image matrix is shifted,

means for scanning each bit of the input data in the image matrix and generating a boundary signal at a transition between a data bit of a first value and a data bit of a second value,

means for tracing a boundary outlined by the stored input data during a tracing sequence in response to the boundary signal in a single bit sequence,

means for changing the value of excess information bits during the tracing sequence from the first value to the second value,

means responsive to each information bit of the first value after completion of the tracing sequence to generate an encoded representation of vectors having a direction based on surrounding data bits of the first and second values, and

means for storing the encoded representations of the vectors in recoverable memory.

2. Apparatus for compressing a pattern of digitized input data as set forth in claim 1 wherein said means for tracing includes means for repeating the single bit sequence for the boundary outlined until all redundant information bits are changed from the first value to the second value.

3. Apparatus for compressing a pattern of digitized input data as set forth in claim 2 including means for storing in a boundary matrix a signal for each boundary signal in a position corresponding to the information bit position in the image matrix.

4. Apparatus for compressing a pattern of digitized input data as set forth in claim 1 wherein said means for tracing includes means for repeating the single bit sequence until a one bit width image of the first value remains in said image matrix.

5. Apparatus for compressing a pattern of digitized input data as set forth in claim 1 wherein said means for changing includes means for logically interconnecting an information bit during the sequence with surrounding information bits of the image matrix to evaluate for an excess information bit.

6. Apparatus for compressing a pattern of digitized input data as set forth in claim 1 wherein said means for scanning includes means for interrupting the scanning of the image matrix in response to the generation of the boundary signal.

7. Apparatus for compressing a pattern of digitized input data as set forth in claim 1 wherein said means for changing includes means for changing the value of an information bit from the first value to the second value when the contents of adjoining bit positions in said image matrix form any one of sixteen predetermined patterns.

8. Apparatus for compressing a pattern of digitized input data as set forth in claim 1 wherein said means responsive to each information bit includes means for producing one of eight encoded representations of a vector based on the immediately preceding encoded representation of a vector.

9. Apparatus for compressing digitized input data of a signature pattern having a multiple bit width for removal of excess information into a vector pattern, comprising in combination:

means for storing in an image matrix each value of digitized input data produced by scanning the signature pattern,

a process array within said image matrix through which the digitized input data in the image matrix is shifted,

means for scanning each bit of the input data in the image matrix and generating a boundary signal at a transition between the data bit of a first value and a data bit of a second value,

means for tracing a boundary outlined by the stored input data during a tracing sequence in response to the boundary signal in a single bit sequence,

means for changing the value of excess information bits during the tracing sequence from the first value to the second value,

means for reactivating said means for scanning to generate a second boundary signal at a transition between a data bit of a first value and a data bit of a second value not previously scanned and producing a boundary signal,

means for reactivating said means for tracing and means for changing to change the value of excess information bits during the tracing of a second boundary outlined by the stored input data, and

means responsive to each information bit of the first value after completion of all tracing sequence to generate an encoded representation of vectors having a direction based on surrounding data bits of first and second values, and

memory means for storing the encoded representations of the vectors in recoverable memory.

10. Apparatus for compressing digitized input data of gray level image pattern into a vector pattern, comprising in combination:

first means for storing each bit of digitized input data produced by scanning the gray level image,

means for subdividing the stored digitized input data into a plurality of binary images from the most significant binary images to the least significant binary images,

means for storing in an image matrix each bit of the digitized input for each of the binary images,

a process array within said image matrix through which the digitized input data in the image matrix is shifted,

means for scanning each binary image of input data and generating boundary signals at a transition between a data bit of the first value and a data bit of a second value,

means for tracing the boundary outlined by the stored input data during a tracing sequence for each binary image in response to the boundary signal associated therewith in a single bit sequence,

means responsive to each information bit of the first value at the completion of the tracing sequence for each binary image to generate an encoded representation of vectors for each such image having a direction based on surrounding data bits of the first and second values, and

memory means for storing the encoded representation of the vectors in recoverable memory.

11. An apparatus for compressing a pattern of digitized input data having a multiple bit width for removal of excess information and converting into a vector pattern comprising:

a pair of two dimensional shift registers, the first of which stores the input data and the second of which stores digital marking information denoting processed cell positions to make possible a particular non-redundant processing sequence,

a pair of process arrays one each in the two dimensional shift registers and through which data is shifted,

means for scanning each bit of the input data and generating a boundary signal by a transition between a data bit of the first value and a data bit of the second value,

means for tracing a boundary outlined by the stored input data during a tracing sequence in response to the boundary signal and a single bit,

means for storing bits in the second two dimensional shift register which mark locations already processed,

means for changing the value of excess information bits during the tracing sequence from the first value to the second value,

means responsive to each information bit of the first value after completion of the tracing sequence to generate an encoded representation of vectors having a direction based on surrounding data bits of the first and second values.