Image data resolution change apparatus and process utilizing boundary compression coding of objects

• US 4,124,871 A
• Filed: 08/31/1977
• Issued: 11/07/1978
• Est. Priority Date: 08/31/1977
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Morrin, Thomas H. II
• Primary Examiner(s): Griffin, Robert L.
• Assistant Examiner(s): Coles, Edward L.
• Application Number:
  US05/829,387
• Time in Patent Office: 433 Days
• Field of Search: 358/287, 358/77, 358/180, 358/96, 358/166, 358/260, 340/146.3 AE, 340/146.3 MA, 340/324 AD
• US Class Current: 358/444
• CPC Class Codes: G06T 3/40 Scaling of whole images or parts thereof, e.g. expanding or contracting
• CPC Class Codes: H04N 1/3935 with modification of image resolution, i.e. determining the values of picture elements at new relative positions
• CPC Class Codes: H04N 1/411 for the transmission or storage or reproduction of two-tone pictures, e.g. black and white pictures

Abstract

Resolution or size changing of scanned objects can be accomplished on contour coded data using the information obtained in the boundary following of exterior and interior borders of objects. The compressed boundary following data has its resolution changed by scale factor multiplying after decoding. The rescaled image is placed into a memory store for display. Uncompressed data is resolution changed by boundary following the stored image to obtain the object boundary coordinates. These coordinates are concurrently multiplied by a scale factor, compared to the scaled coordinate of the previous boundary picutre element and either contour encoded to compress the shrunken image or directed to a second memory store for display. The coordinates of each successive point are changed by the multipliers that scale the coordinates by the consolidation ratios. Each coordinate is affected separately. Any rational reduction factor can be achieved.

Claims

1. Apparatus for resolution changing objects in a black and white image, the objects being patterned black picture elements stored in a bit addressable random access memory store, said apparatus comprising:

means for accessing the image in the memory store in a predetermined sequential order;

means for indicating memory coordinates of each picture element in encountered objects of the image accessed from the memory store;

border follower means responsive to said accessing means for following the connected picture elements of the borders of the object;

multiplier means for scale factor multiplying the memory coordinates of each picture element of the encountered objects; and

encoder means responsive to said following means for encoding the relative position of each picture element according to its multiplied memory coordinates into a machine usable coded format of the resolution changed object.

2. Apparatus for resolution changing objects as defined in claim 1 wherein said encoder means includes:

latch means for storing the scale factor multiplied memory coordinates of a picture element; and

comparator means for comparing the multiplied memory coordinates of the present picture element to those of the immediately previous picture element stored in said latch means, said comparator means providing the memory coordinates for encoding into the machine usable coded format.

3. Apparatus for resolution changing objects in a black and white image, the objects being patterned black picture elements stored in a bit addressable random access memory store, said apparatus comprising:

means for accessing the image in the memory in a predetermined sequential order, including means for indicating that an initial black picture element of an object has been encountered;

means responsive to said accessing means for following the outer border of said object to encounter successive neighboring black picture elements,

means for indicating the memory coordinates of said black picture elements retrieved by said accessing means;

multiplier means for scale factor multiplying the memory coordinates of each black picture element of said object;

means connected to said multiplier means for indicating the relative position of each successive black picture element encountered;

means responsive to said following means for encoding the relative position of each picture element in a machine usable coded format; and

control means connected to said memory, responsive to said following means for changing each encountered black picture element to white to thereby shrink and delete said object from said memory;

said control means including means connected to said encoding means, responsive to said following means for deactivating said encoding means upon said follower reencountering said initial black picture elememt to thereby de-limit the outer boundary of the object.

4. Apparatus for resolution changing objects in a black and white image, the objects being patterned black picture elements stored in a bit addressable random access memory store, the apparatus including:

means for accessing the image in the memory in a predetermined sequential order, including means for indicating that an initial black picture element of an object has been encountered;

means responsive to said accessing means for following the outer border of said object to encounter successive neighboring black picture elements,

address indication means for indicating the memory coordinates of said black picture elements retrieved by said accessing means;

position indicator means for indicating the relative position of each successive black picture element encountered;

means responsive to said following means for encoding the relative position of each picture element in a machine usable coded format; and

control means connected to said memory, responsive to said following means for changing each encountered black picture element to white to thereby shrink and delete said object from said memory;

said control means including means connected to said encoding means, responsive to said following means for deactivating said encoding means upon said follower reencountering said initial black picture element to thereby de-limit the outer boundary of the object;

wherein the improvement comprises;

multiplier means connected to said address indicator means for scale factor mutliplying the memory coordinates of each black picture element of said object;

latch means connected to said multiplier means for storing the multiplied memory coordinates of one picture element; and

comparator means for comparing the multiplied memory coordinates of the immediately previous picture element stored in said latch means to the multiplied memory coordinates of the present picture element, said comparator means providing the memory coordinates for said position indicator means.

5. Apparatus for resolution changing objects in a black and white image from contour encoded data for storage in a bit addressable random access memory store, said apparatus comprising:

decoder means for decoding the contour encoded data into memory store coordinates identifying each picture element of the objects in the image;

multiplier means for scale factor mutliplying the memory store coordinates; and

means for storing the image in the memory store according to the multiplied memory store coordinates of the objects in the image.

6. Apparatus for resolution changing objects as defined in claim 5 wherein said decoder means includes integer expansion means for providing n number of integer steps according to the contour encoded data to produce n number of picture elements and its memory store coordinates for each picture element of the objects in the image.

7. A machine implementable process for changing resolution of boundary following contour encoded compressed objects information of a black and white image, the objects being patterned black picture elements, said process comprising the steps of:

decoding the boundary encoded compressed object information;

generating coordinates for the location address from the decoded boundary object information;

multiplying the generated coordinates by a scale factor; and

storing the object data using the multiplied coordinates as the address location of black picture elements of the objects of the image.

8. A machine implementable process for changing resolution while compressing and encoding objects and hole boundaries in chain link coded form of an arbitrary black/white image composed of black and white picture elements comprising the steps of:

storing the image in a multi-dimensional writable memory;

searching said memory for black objects an object being identified when the first black picture element of a plurality of black picture elements comprising said object is encountered;

border following said object to thereby encounter successive black picture elements comprising the outer boundary of said object;

generating coordinates for the location address from the encountered black picture elements;

multiplying the generated coordinates by a scale factor;

activating an encoder in order to encode the coordinates of said encountered picture elements as the border of the object is followed until said first black picture element is reencountered;

deactivating said encoder;

changing from black to white in said multi-dimensional memory, picture elements corresponding to said encountered picture elements thereby reducing the object in order to locate inner boundaries and for eliminating the object from further consideration by reducing it to either a single point or until a white border picture element adjacent to an encountered black picture element indicative of a hole within the object is encountered.

generating coordinates for the location address from the encountered white picture elements;

multiplying the generated coordinates by a scale factor;

reactivating said encoder in order to encode the X-Y coordinates of said encountered white picture elements of said hole as the border of said hole is followed until the coordinates of the initially encountered white border picture element are re-encountered;

deactivating said encoder; and

reducing the white picture element values within the inner boundary as if the hole were a black object, the processing being recursive until the original object is in turn reduced to a single picture element.

9. A machine implementable method for changing resolution while compressing and encoding objects and hole boundaries in chain link coded form of an arbitrary black/white image composed of black and white picture elements comprising the steps of:

storing the image in a multi-dimensional writable memory;

searching said memory in row major order for black objects, an object being identified when the first black picture elements of a plurality of black picture elements comprising said object is encountered;

border following said object to thereby encounter successive black picture elements comprising the boundaries of said object;

generating coordinates for the location address from the encountered black picture elements;

multiplying the generated coordinates by a scale factor; and

encoding the coordinates of said encountered picture elements as the borders of the object are followed.

10. A machine implementable process for changing resolution while boundary encoding of a two-dimensional array of picture elements, each picture element of which exhibits a Boolean value representative of black or white such that connected clusters of black picture elements are perceived as objects, and, further, such that each object possesses a single outer contour closing upon itself, and, lastly, such that each object selectively contains inner contours circumscribing clusters of white picture elements perceived as holes, the method comprising the steps of:

(a) storing the array in a multi-dimensional writable memory;

(b) raster scanning the array until the first black picture element of a plurality of picture elements comprising an object is encountered;

(c) going to step (g) if an object picture element is encountered, otherwise going to step (d);

(d) ending the process if the encountered picture element is the last picture element, otherwise going to step (e);

(e) going to the next picture element of the stored image;

(f) returning to step (b);

(g) border following said object to thereby encounter successive black picture elements comprising the outer boundary of said object;

(h) generating location address of the boundary of the object;

(i) going to step (j) to continue boundary following object and to step (k) for the outputting of data;

(j) going to step (b) if the picture element being scanned is the last picture element of the boundary, otherwise going to step (g).

(k) multiplying the generated location address by a scale factor to change the resolution of the object;

(l) comparing the present multiplied location address with the previous multiplied location address;

(m) generating a new location address according to the scale factor multiplication and the comparison;

(n) encoding the generated new location address of said encountered picture elements; and

(o) transmitting the encoded new location address to a utilization device.

11. A machine implementable process for changing resolution of boundary following contour encoded compressed object data information of an image comprising the steps of:

(a) decoding the contour encoded compressed boundary information representing objects of the image;

(b) generating the coordinates of the location addresses of the picture elements of the objects of the decoded boundary information;

(c) multiplying the generated coordinates by a scale factor to change the resolution of the object; and

(d) storing the resolution changed information according to the multiplied coordinates of the location address in a random access memory store to obtain the changed resolution black/white image composed of black and white picture elements placed according to the contour encoded image information.