Method and apparatus for processing digital data

• US 5,065,447 A
• Filed: 07/05/1989
• Issued: 11/12/1991
• Est. Priority Date: 07/05/1989
• Status: Expired due to Term

• Current Assignee: MediaBin, Inc. (HP Inc.)
• Original Assignee: Iterated Systems Inc (Hewlett-Packard Enterprise Company)
• Inventors: Sloan, Alan D., Barnsley, Michael F.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/375,840
• Time in Patent Office: 860 Days
• Field of Search: 382/8, 382/27, 382/56, 382/34, 382/30, 382/41, 358/433, 358/467, 364/518
• US Class Current: 382/249
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G10L 25/36 using chaos theory
• CPC Class Codes: H04N 19/99 involving fractal coding

Abstract

Digital image data is automatically processed by dividing stored image data into domain blocks and range blocks. The range blocks are subjected to processes such as a shrinking process to obtain a mapped range blocks. Then, for each domain block, the mapped range block which is most similar to the domain block is determined, and the address of that range block and the processes the block was subjected to are combined as an identifier which is appended to a list of identifiers for other domain blocks. The list of identifiers for all domain blocks is called a fractal transform and constitutes a compressed representation of the input image. To decompress the fractal transform and recover the input image, an arbitrary input image is formed into range blocks and the range blocks processed in a manner specified by the identifiers to form a representation of the original input image.

Claims

1. A method for automatically processing digital image data consisting of image information, the method comprising the steps performed by a data processor of:

storing the image data in the data processor;

generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that all of the image information is contained in at least one of the domain blocks;

creating, from the stored image data, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the stored image data with each of the subsets having a unique address, the creating step including the substep of

executing, for each of the mapped range

blocks, a corresponding procedure upon the one

of the subsets of the stored image data which

corresponds to the mapped range block;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block a procedure and a address of the corresponding subset of the stored image data;

selecting, for each of the domain blocks, the one of the mapped range blocks which most closely corresponds according to predetermined criteria; and

representing the image information as a set of the identifiers of the selected mapped range blocks.

2. A method as recited in claim 1 wherein the digital image data consists of a plurality of pixels and wherein the step of generating the domain blocks includes the substep of generating the domain blocks with unequal numbers of pixels.

3. A method as recited in claim 1 wherein the digital image data consists of a plurality of pixels and wherein the step of generating the domain blocks includes the substep of generating the domain blocks each with the same number of pixels.

4. A method as recited in claim 1 wherein the step of creating a plurality of uniquely addressable mapped range blocks includes the substeps of:

creating a plurality of initial range blocks having greater numbers of pixels than the domain blocks;

shrinking the initial range blocks to create shrunken range blocks which have the same number of pixels as the domain blocks; and

using the shrunken range blocks to form the mapped range blocks.

5. A method as recited in claim 4 wherein the step of shrinking comprises the substep of selecting certain ones of the pixels of each initial range block to form a corresponding shrunken range block.

6. A method as recited in claim 5 wherein the substep of selecting pixels includes the substep of selecting pixels equally spaced in the initial range blocks.

7. A method as recited in claim 4 wherein the shrinking step includes the substep of averaging adjacent pixels.

8. A method as recited in claim 3 wherein the step of creating a plurality of uniquely addressable mapped range blocks includes the substep of:

rotating the mapped range blocks by a predetermined number of degrees.

9. A method as recited in claim 3 wherein the step of creating a plurality of uniquely addressable mapped range blocks includes the substep of inverting the mapped range block.

10. A method as recited in claim 1 wherein the step of generating the domain blocks includes the substep of assigning each portion of the stored image information to only one of the domain blocks such that the domain blocks are non-overlapping.

11. A method as recited in claim 1 wherein the step of selecting the mapped range blocks includes the substep of selecting, for each domain block, a most closely corresponding one of the mapped range blocks.

12. A method as recited in claim 11 wherein the step of selecting the most closely corresponding one of the mapped range blocks includes the step of selecting, for each domain block, the mapped range block which has the minimum Hausdorff distance from the domain block.

13. A method as recited in claim 11 wherein the step of selecting the most closely corresponding one of mapped range blocks includes the step of selecting, for each domain block, the mapped range block with the minimum modified Hausdorff distance calculated as D[db,mrb]+D[1-db,1-mrb], where D is a distance calculated between a pair of sets of data each representative of an image, db is a domain block, mrb is a mapped range block, 1-db is the inverse of a domain block, and 1-mrb is an inverse of a mapped range block.

14. A method as recited in claim 1 wherein the step of selecting the most closely corresponding one of the mapped range blocks includes the substeps of:

calculating, for each of the domain blocks, the mapped weighted L² distance D_L from each of the range blocks as ##EQU2## where x_i,y_i are indexed intensity values in respective images, w_i are non-negative numbers, and N is the number

of pixels in each domain block; and

selecting, for each domain block, the mapped range block with the minimum weighted L² distance.

15. A method as recited in claim 1 wherein the step of creating mapped range blocks includes the step of creating a mapped range block comprising an escape block having the same size as the mapped range blocks and containing digital data representing an all white image.

16. A method for automatically processing digital image data consisting of a plurality of pixels each having one of a plurality of grayscale values, the method comprising the steps performed by a data processor of:

storing the image data in the data processor;

generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that all of the image information is contained in at least one of the domain blocks;

creating, from the stored image data, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the stored image data with each of the subsets having a unique address, the creating step including the substep of executing, for each of the mapped range blocks, a corresponding procedure upon the one of the subsets of the stored image data which corresponds to the mapped range block;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block a procedure and an address of the corresponding subset of stored image data;

selecting, for each of the domain blocks the one of the mapped range blocks which most closely corresponds according to a first predetermined criteria; and

representing the image information as a set of the identifiers of the selected mapped range blocks.

17. A method as recited in claim 16 wherein the step of selecting includes the substeps of:

transforming the grayscale values of the pixels of each domain block by a linear function including at least one vertical scaling parameter;

transforming the grayscale values of the pixels of the shrunken range blocks by the linear function;

selecting, for each of the domain blocks, the one of the mapped range blocks having transformed pixel values which most closely corresponds to the transformed pixel values of the domain block according to the first predetermined criteria;

and wherein the step of representing the image information includes the substep of representing the image information as a set of values each including an identifier of the selected mapped range block and the at least one vertical scaling parameter.

18. A method as recited in claim 17 wherein the first criteria comprises minimizing the Hausdorff distance between each domain block and the selected shrunken range block.

19. A method as recited in claim 17 wherein the substeps of transforming pixel values of the domain blocks and shrunken range blocks comprises selecting the at least one vertical scaling parameter to maximize the correspondence between the domain blocks and shrunken range blocks according to a second predetermined criteria.

20. A method as recited in claim 19 wherein the first and second predetermined criteria are different.

21. A method as recited in claim 20 wherein the second predetermined criteria comprises minimizing the L² distance between the domain blocks and the shrunken range blocks.

22. A method for automatically processing digital image data consisting of image information in a data processor which includes a memory having a plurality of buffers each having a plurality of addressable areas specified by a buffer address, the method comprising the steps of:

storing the image data in the data processor;

generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that all of the image information is contained in at least one of the domain blocks;

creating, from the stored image data, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the stored image data with each of the subsets having a unique address, the creating step including the substep of

executing, for each of the mapped range blocks, a corresponding procedure upon the one of the subsets of the stored image data which corresponds to the mapped range block;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers corresponding to an addressable area in the buffers and including both a procedure and a buffer address;

selecting, for each of the domain blocks the one of the mapped range blocks which most closely corresponds according to predetermined criteria; and

representing the image information as a set of the selected identifiers;

storing a predetermined pattern of digital data in one of the buffers designated as a source buffer;

determining, for each of the identifiers, a pattern of data corresponding to each identifier by applying the procedure in that identifier to the portion of the source buffer indicated by the buffer address in that identifier;

storing the pattern of data into the addressable area of another one of the buffers, designated as a destination buffer, indicated in the corresponding identifier;

repeating the determining and destination buffer storing steps, with the destination buffer being considered as the source buffer, until predetermined criteria are met; and

providing the contents of the destination buffer as data representative of an image when the predetermined criteria are met.

23. A method for automatically enhancing digital image data in a data processor which includes a memory having a plurality of buffers each having a plurality of addressable areas specified by a buffer address, the image data consisting of image information at a first resolution, the method comprising the steps of:

storing the image data in a first one of the buffers;

generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that all of the image information is contained in at least one of the domain blocks;

creating, from the stored image data, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the stored image data with each of the subsets having a unique address, the creating step including the substep of

executing, for each of the mapped range blocks, a corresponding procedure upon the one of the subsets of the stored image data which corresponds to the mapped range block;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers corresponding to an addressable area in the buffers and including both a procedure and a buffer address;

selecting, for each of the domain blocks the one of the mapped range blocks which most closely corresponds according to predetermined criteria; and

representing the image information as a set of the selected identifiers;

storing a predetermined pattern of digital data in a second one of the buffers designated as a source buffer, the second buffer being larger than the first buffer;

determining, for each of the identifiers, a pattern of data corresponding to each identifier by applying the procedure in that identifier to the portion of the source buffer indicated by the buffer address in that identifier;

storing the pattern of data into the addressable area of a third one of the buffers, designated as a destination buffer, indicated in the corresponding identifier, the third buffer being larger than the first buffer;

repeating the determining and destination buffer storing steps, with the destination buffer being considered as the source buffer, until predetermined criteria are met; and

providing the contents of the destination buffer as output image data when the predetermined criteria are met, the output image data being representative of the input image at a second resolution higher than the first resolution.

24. A method for automatically generating an image by a data processor from a set of identifiers, the data processor including a memory having a plurality of buffers each having a plurality of addressable areas specified by a buffer address, and each of the identifiers corresponding to an addressable area in the buffers and including a buffer address and a procedure specification, the method comprising the steps, performed by a data processor, of:

storing a predetermined pattern of digital data in one of the buffers designated as a source buffer;

determining, for each of the identifiers, a pattern of data corresponding to each identifier by applying the procedure specified in that identifier to the portion of the source buffer indicated by the buffer address in that identifier;

storing the patterns of data into the addressable area of another one of the buffers, designated as a destination buffer, indicated in the corresponding identifier;

repeating the determining and destination buffer storing steps, with the destination buffer being considered as the source buffer, until predetermined criteria are met; and

providing the contents of the destination buffer as data representative of an image when the predetermined criteria are met.

25. A method as recited in claim 24 wherein the step of providing the contents of the destination buffer when the predetermined criteria are met includes the substep of determining when the contents of the source and destination buffers differ by less than a predetermined amount.

26. A method as recited in claim 24 wherein the step of providing the contents of the destination buffer as data representative of an image when the predetermined criteria are met includes the steps of determining and storing into the destination buffer a predetermined number of times.

27. A method as recited in claim 24 wherein the step of storing digital data into the destination buffer includes the step of storing at least one of the patterns into each addressable area of the destination buffer.

28. A method for automatically generating an image by a data processor from a set of identifiers, the data processor including a memory having a plurality of buffers each having a plurality of addressable areas specified by a buffer address, and each of the identifiers corresponding to an addressable area in the buffers and including a buffer address, the method comprising the steps, performed by a data processor, of:

storing a predetermined pattern of digital data in one of the buffers designated as a source buffer;

determining, for each of the identifiers, a pattern of data corresponding to each identifier by the portion of the source buffer indicated by the buffer address in that identifier;

storing the patterns of data into the addressable area of another one of the buffers, designated as a destination buffer, indicated in the corresponding identifier;

repeating the determining and destination buffer storing steps, with the destination buffer being considered as the source buffer, until predetermined criteria are met; and

providing the contents of the destination buffer as data representative of an image when the predetermined criteria are met.

29. A method for generating an image by a data processor from a set of identifiers, the data processor including a memory having a buffer with a plurality of addressable areas specified by a buffer address, and each of the identifiers corresponding to an addressable area in the buffer and including both a procedure and a buffer address, the method comprising the steps, performed by a data processor, of:

storing a predetermined pattern of digital data in the buffer;

determining, for each of the identifiers, a pattern of data corresponding to each identifier by applying the procedure specified in that identifier to the portion of the buffer indicated by the buffer address in that identifier;

storing the patterns of data into the addressable areas indicated in the corresponding identifiers;

repeating the determining and buffer storing steps until predetermined criteria are met; and

providing the contents of the buffer as data representative of an image when the predetermined criteria are met.

30. A method for automatically generating a digital data representation of a motion picture having a plurality of individual sequential frames each containing frame image information, comprising the steps performed by a data processor of:

initializing first and second processing buffers in the data processor;

digitizing image information contained in a frame to produce digitized image data;

storing the digitized image data into the first processing buffer;

creating in the first processing buffer a plurality of uniquely addressable domain blocks from the stored image data of the first processing buffer, each of the domain blocks representing a different portion of the frame image information such that all of the frame image information is contained in at least one of the domain blocks;

creating in the second processing buffer, from the data stored in the second processing buffer, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the stored second processing buffer data with each of the subsets having a unique address, the creating step including the substep of

executing, for each of the mapped range blocks, a corresponding procedure upon the one of the subsets of the second processing buffer data which corresponds to the mapped range block;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block a procedure and an address of the corresponding subset of stored second processing buffer data;

selecting, for each of the domain blocks of the first processing buffer, the one of the mapped range blocks of the second processing buffer which most closely corresponds according to predetermined criteria;

replacing each of the domain blocks with the corresponding selected mapped range block;

forming a current transform as a set of the identifiers of the selected mapped range blocks;

copying the contents of the first processing buffer into the second processing buffer;

repeating the digitizing, storing, first and second processing buffer creating, assigning, selecting, replacing, forming, and copying steps until all of the frames have been digitized; and

supplying the sequence of current transforms for each of the frames as a compressed representation of image information in the motion picture.

31. A method as recited in claim 30 wherein image data from the first frame is repeatedly processed a predetermined number of times to produce a series of current transforms representative of the first frame, and image data from each succeeding frame is processed once to produce a single current transform representative of each succeeding frame.

32. A method for automatically generating digital data representing the frames of a motion picture by a data processor from a sequence of current transforms each having a set of identifiers comprising compressed digital data representative of the frames, the data processor including a memory having a plurality of buffers each having a plurality of addressable areas specified by a buffer address, and each of the identifiers corresponding to an addressable area in the buffers and including a buffer address and a procedure specification, the method comprising the steps, performed by the data processor, of:

initializing a predetermined pattern of digital data into one of the buffers designated as a source buffer;

inputting a current transform and storing the current transform in another of the buffers designated as the destination buffer;

determining, for each of the identifiers, a pattern of data corresponding to each identifier by applying the procedure specified in that identifier to the portion of the source buffer indicated by the buffer address in that identifier;

storing the patterns of data into the addressable areas of the destination buffer which are specified by the corresponding identifiers;

providing the contents of the destination buffer as data representative of an image in a frame;

copying the contents of the destination buffer into the source buffer; and

repeating the inputting, determining, storing, providing, and copying steps for each current transform of the sequence.

33. Apparatus for generating compressed digital data representative of frames of video image information to be transmitted over a standard telephone line, comprising:

frame grabber means for receiving video data and for storing frame data comprising image data representative of image information in a single frame of video data;

a video encoder, the video encoder comprising means for;

storing the image data in the video encoder;

generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that data representing all of the image information is contained in at least one of the domain blocks,

creating, from the stored image data, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the stored image data with each of the subsets having a unique address, the creating step including the substep of

executing, for each of the mapped range blocks, a corresponding procedure upon the one of the subsets of the stored image data which corresponds to the mapped range block;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block a procedure and an address of the corresponding subset of image data,

selecting, for each of the domain blocks, the one of the mapped range blocks which most closely corresponds according to predetermined criteria and

representing the image information as a set of the identifiers of the selected mapped range blocks; and

control means coupled to the frame grabber means and the video encoder for supplying the frame data to the video encoder and for commanding the video encoder to generate compressed digital data comprising the set of the identifiers of the selected mapped range blocks representing the frame data.

34. Apparatus for producing video data for display on a video output device from a sequence of current transforms received over a standard telephone line and each having a set of identifiers comprising compressed digital data representative of the frames, comprising:

a data input circuit for receiving and accumulating the compressed digital data;

a video decoder coupled to the data input circuit, the video decoder comprising;

a memory having a plurality of buffers each having a plurality of addressable areas specified by a buffer address, and each of the identifiers corresponding to an addressable area in the buffers and including a buffer address and a procedure specification, and means for;

storing a predetermined pattern of digital data in one of the buffers designated as a source buffer,

determining, for each of the identifiers, a pattern of data corresponding to each identifier by applying the procedure specified in that identifier to the portion of the source buffer indicated by the buffer address in that identifier,

storing the patterns of data into the addressable area of another one of the buffers, designated as a destination buffer, indicated in the corresponding identifier, and

providing the contents of the destination buffer as decompressed digital data representative of a frame of image information;

a video output circuit coupled to the video decoder for converting digital data into signals for display of an image on a video display device; and

control means coupled to the data input circuit and the video decoder for supplying the accumulated digital data to the video decoder and for commanding the video decoder to produce and supply the decompressed digital data to the video output circuit.

35. A method for automatically processing digital image data consisting of image information, the method comprising the steps performed by a data processor of:

storing the image data in the data processor;

generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that all of the image information is contained in at least one of the domain blocks;

creating, from the stored image data, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the stored image data with each of the subsets having a unique address, the creating step including the substep of

executing, for each of the mapped range blocks, a procedure upon the one of the subsets of the stored image data which corresponds to the mapped range block;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block an address of the corresponding subset of stored image data;

selecting, for each of the domain blocks, the one of the mapped range blocks which most closely corresponds according to predetermined criteria; and

representing the image information as a set of the identifiers of the selected mapped range blocks.

36. A method for automatically processing digital image data consisting of a plurality of pixels each having one of a plurality of grayscale values, the method comprising the steps performed by a data processor of:

storing the image data in the data processor;

generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that all of the image information is contained in at least one of the domain blocks;

creating, from the stored image data, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the stored image data with each of the subsets having a unique address, the creating step including the substep of executing, for each of the mapped range blocks, a corresponding procedure upon the one of the subsets of the stored image data which corresponds to the mapped range block;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block an address of the corresponding subset of stored image data;

selecting, for each of the domain blocks the one of the mapped range blocks which most closely corresponds according to a first predetermined criteria; and

representing the image information as a set of the identifiers of the selected mapped range blocks.

37. Apparatus for automatically processing digital image data consisting of image information, comprising:

means for storing the image data;

means for generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that all of the image information is contained in at least one of the domain blocks;

means for creating, from the stored image data, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the stored image data with each of the subsets having a unique address, the creating means including means for executing, for each of the mapped range blocks, a procedure upon the one of the subsets of the stored image data which corresponds to the mapped range block;

means for assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block an address of the corresponding subset of stored image data;

means for selecting, for each of the domain blocks, the one of the mapped range blocks which most closely corresponds according to predetermined criteria; and

means for representing the image information as a set of the identifiers of the selected mapped range blocks.

38. Apparatus as recited in claim 37, wherein the means for assigning unique identifiers comprises means for assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block a procedure and an address of the corresponding subset of stored image data.