Encoding/decoding in the decomposition and recomposition of a high resolution image.

<u style="single">Technical Field</u>

0001This invention relates to transmission and/or storage of images and, more particularly, to efficient encoding/decoding of image information.

<u style="single">Background of the Invention</u>

0002Recently, there has been a rapid increase in the transmission and/or storage of image information and the like. This has been especially true in the use of facsimile. Additionally, use of high resolution monitors for generating a soft copy and/or browsing of the image information has resulted in additional requirements being placed on digital transmission and/or storage interfaces. In certain applications, rapid progression from a low resolution replica to a high resolution image is desirable and sometimes necessary. In order to improve encoding/decoding efficiency and speed, prior arrangements were employed which decomposed a high resolution image into a lower resolution replica and so-called supplemental information. The supplemental information was required to later recompose the low resolution replica into the high resolution image. In one known prior arrangement, supplemental information was generated only for pixels (picture elements) determined to be in a predetermined relation with their neighboring pixels, i. e., at an edge. Pixels that no not satisfy the above condition but that were determined to require supplemental information were forced to satisfy the above condition by modifying the image reduction rules. That is, the reduction rules were modified to force a pixel to satisfy the above condition whenever the prediction rules would cause a decoder to otherwise improperly recompose the high resolution image. See, for example, our United States patent 4,870,497 issued September 26, 1889 for one such prior arrangement.

0003A serious limitation of such a prior arrangement is that the prediction rules used to determine if supplemental information was required to be generated and encoded were based and dependent on the particular properties of the image reduction rules. Therefore, if the image reduction rules were changed, the prior prediction rules could not be used. Thus, any change in the image reduction rules would require development of a new set of prediction rules. This interdependence of the image reduction rules and the prediction rules is undesirable.

0004More recently, the interdependence between the reduction rules and the prediction rules was eliminated. This is achieved by employing so-­called general prediction rules to determine if the pixels to be recomposed are so-called typically predictable or non-typically predictable. Typically predictable pixels which would be improperly recomposed by using the general prediction rules are identified as exceptions. The non-typically predictable pixels and the typically predictable pixels that are exceptions require supplemental information to properly be recomposed. An exception was required to accompany each pixel identified as an exception. This, in turn, required the encoding and, subsequent, decoding of the exceptions. This encoding and decoding caused complexity and was inefficient. Thus, although this arrangement operates satisfactorily in many applications, its complexity and inefficiency renders it undesirable for other applications.

<u style="single">Summary of the Invention</u>

0005The limitations and other problems of the prior known prediction arrangements used in image decomposition and recomposition are overcome, in accordance with an aspect of the invention, by grouping a number of pixels into so-called clusters and by classifying each cluster as having one of a plurality of classifications.

0006In one embodiment employing two classes of clusters, a cluster including at least one so-called typically predictable pixel identified as an exception to the general prediction rules is classified as having a first classification and is identified as such by an accompanying first classification flag. A cluster including typically predictable pixels with no exception and/or non-typically pixels is classified as having a second classification and is identified as such by an accompanying second classification flag. Supplemental information is generated for all pixels in clusters having the first classification. Otherwise, supplemental information is only generated for non-typically predictable pixels.

0007In recomposing a "high" resolution image, the high resolution pixels are recomposed, in accordance with an aspect of the invention, by employing the classification flags of the clusters. If a cluster has the first classification flag, all of the high resolution pixels are recomposed from the accompanying supplemental information. If a cluster has the second classification flag, the high resolution pixels are recomposed in accordance with the general prediction rules and if they are non-typically predictable pixels, from the accompanying supplemental information.

<u style="single">Brief Description of the Drawing</u>

0008In the Drawing: <ul id="ul0001" list-style="none"><li>FIG. 1 shows, in simplified block diagram form, details of a progressive image transmission and/or storage system which advantageously employs aspects of the invention;</li><li>FIG. 2 depicts in graphic form a high resolution image and a corresponding low resolution replica useful in describing embodiments of the invention;</li><li>FIG. 3 shows, in simplified block diagram form, details of one of the decomposition processors employed in the embodiment of FIG. 1;</li><li>FIG. 4 is a graphical representation of portions of a high resolution image and a low resolution replica useful in describing aspects of the invention;</li><li>FIG. 5 is a table depicting a so-called group pixel assignment and super pixel assignment useful describing an embodiment of the invention;</li><li>FIG. 6 illustrates a flow chart depicting the generic operation, in accordance with an aspect of the invention, of the decomposition processor implementation of FIG. 3;</li><li>FIG. 7 is a flow chart of the generic subroutine CC-TG used in the operation of the decomposition processor illustrated in the flow chart of FIG. 6 which, in accordance with an aspect of the invention, classifies the clusters;</li><li>FIG. 8 is a flow chart illustrating operation, in accordance with an aspect of the invention, of the decomposition processor of FIG. 3;</li><li>FIG. 9 and FIG. 10 when connected A-A form a flow chart of subroutine CC-T used in the operation of a first illustrative embodiment of the decomposition processor illustrated in the flow chart of FIG. 4 which, in accordance with an aspect of the invention, classifies clusters;</li><li>FIG. 11 shows, in simplified block diagram form, details of one of recomposition processors of FIG. 1;</li><li>FIG. 12 illustrates a flow chart showing the generic operation, in accordance with aspects of the invention, of the the recomposition processor implementation of FIG. 11;</li><li>FIG. 13 is a flow chart of the generic subroutine CC-RG used in the operation of the recomposition processor shown in FIG. 11 which, in accordance with an aspect of the invention, recomposes pixels from the clusters;</li><li>FIG. 14 is a flow chart illustrating operation, in accordance with an aspect of the invention, of an embodiment of the recomposition processor of FIG. 11; and</li><li>FIG. 15 is a flow chart of subroutine CC-R used in the operation of the illustrative embodiment of the recomposition processor illustrated in the flow chart of FIG. 14 which, in accordance with an aspect of the invention, recomposes pixels in the clusters.</li></ul>

<u style="single">Detailed Description</u>

0009FIG. 1 shows, in simplified block diagram form, details of a progressive image transmission and/or storage system which advantageously employs aspects of the invention. Accordingly, shown are image source 101, transmitter 102, transmission network and/or storage unit 103, receiver 104 and image output unit 105.

0010Image source 101 provides, in this example, a desired high resolution image and may be, for example, either a scanner or a data base. One such scanner which may advantageously be employed is manufactured by Cannon and is designated laser copier scanner NP-9030. The images to be transmitted may also be stored in a data base on, for example, either a magnetic disc or an optical disc. In this example, not to be construed as limiting the scope of the invention, the high resolution image I0 includes 400 dots per inch and has M₀ columns and N₀ rows and includes M₀ x N₀ pixels, as shown in FIG. 2. A so-called super pixel in high resolution image I0 includes a block of "high" resolution pixels. Although any desired number of high resolution pixels from a plurality of columns and rows may be grouped to form a super pixel, in this example, it has been convenient to group four (4) high resolution pixels into a super pixel. Thus, in this example, a super pixel includes a block of four high resolution pixels, namely, h0(m,n), h0(m,n+1), h0(m+1,n) and h0(m+1,n+1), where m and n are the row and column indices, respectively, in the original high resolution image. In this example, when the Cannon scanner is employed to scan the original image, at 400 dots per inch, it yields M₀ = 3456 columns and N₀ = 4672 lines for an A4 standard size document.

0011Also shown in FIG. 2 are clusters of pixels and a grouping of pixels employed to determine if pixels are typically predictable or non-­typically predictable. In this example, not to be construed as limiting the scope of the invention, the clusters comprise a number of rows of pixels in the high resolution image and a corresponding appropriate number of rows of pixels in the low resolution replica. It will be apparent that other cluster configurations could also be used in practicing aspects of the invention.

0012The high resolution pixels are supplied from image source 101 to transmitter 102 and, therein, to decomposition processor 106-1. Decomposition processor 106-1 operates, as described below, to generate a low resolution replica I1 of the high resolution image, also shown in FIG. 2. Thus, the high resolution image I0 is decomposed into low resolution replica I1 having M₁ rows and N₁ columns plus supplemental information SI1 and classification flag F1. In this example, M₁ = M₀/2, N₁ = M₀/2 and the resolution of low resolution replica I1 is 200 dots/inch. As shown in FIG. 2, low resolution replica I1 has an imaginary reference column of pixels to the left of column l=0 and an imaginary reference row of pixels above row k=0, where l and k are the column and row indices, respectively. In this example, the pixels in the imaginary reference column and row are chosen to be white. The decomposition from high resolution image I0 to low resolution replica I1 is realized by replacing every super pixel including high resolution pixels h0(m,n), h0(m+1,n), h0(m,n+1) and h0(m+1,n+1) in image I0 with a single low resolution pixel L1(k,l). The difference between the original high resolution image I0 and the low resolution replica I1 is the supplemental information SI1 required to upgrade the lower resolution replica into a higher resolution image. It should be noted that the supplemental information for low resolution pixels is generated, in accordance with an aspect of the invention, for all low resolution pixels in a cluster classified as being in the first classification and for non-typically predictable pixels in a cluster classified as being in the second classification. Generation of the supplemental information is described below with respect to the decomposition process.

0013Transmitter 102 includes a number of decomposition processors, in this example, decomposition processors 106-1, 106-2 and 106-3. Although three decomposition processors are shown, in this example, it will be apparent that any desired number may he employed depending on the particular application. Indeed, a single decomposition process 106-1 could be employed, if desired. Each of decomposition processors 106-1 through 106-3 decomposes a 'high" resolution image into a "low" resolution replica. As described above, FIG. 2 illustrates the relationship between the high resolution image I0 and the low resolution replica I1 generated by decomposition processor 106-1. The "high" resolution image supplied to decomposition processor 106-2 is low resolution replica I1 from decomposition processor 106-1. In turn, decomposition processor 106-2 generates low resolution replica I2 which, in turn, is supplied to decomposition processor 106-3 as its "high" resolution image. Decomposition processor 106-3 generates a so-called basic low resolution replica I3. The relationship between the pixels in each "high" resolution image and "low" resolution replica is identical to the relationship between pixels in I0 and I1 as shown in FIG. 2 and described above. That is, in this example, there is a 2 to 1 reduction in dots/inch and a 4 to 1 reduction in pixels for each decomposition generated by decomposition processors 106-1 through 106-3. Thus, the resolution of the basic low resolution replica I3, in this example, generated by decomposition processor 106-3 is 50 dots/inch.

0014The pixels L3(l,k) of the basic low resolution replica I3 are supplied to encoder 107. Encoder 107 encodes the pixels L3(l,k) in well-­known fashion. Specifically, any one of several known CCITT or other standard encoding techniques may be employed. One CCITT encoding technique is described in <u style="single">INTERNATIONAL TELEPHONE AND TELEGRAPH CONSUTATIVE COMMITTEE (CCITT)</u>, "Facsimile Coding Schemes and Coding Control Functions for Group IV Facsimile Apparatus", Redbook, Facsimile VII.3, Rec.T.8, 1984, pages 40-48. The encoded pixel information is supplied to multiplexer (MUX) 108. Also, supplied to MKX 108 are encoded supplemental information and encoded classification flags from each of decomposition processors 106-1,106-2 and 106-3, namely, encoded supplemental information 511,512 and 513, respectively, and encoded classification flags F1, F2 and F3, respectively. MUX 108 combines the encoded basic pixel information, the encoded supplemental information and the encoded classification flags, in well known fashion, for transmission and/or storage. To this end, it is noted that for transmission applications the encoded supplemental information SI1,SI2 and SI3 and the encoded classification flags, F1, F2 and F₃ are multiplexed in reverse sequential order. This is necessary because the lower resolution supplemental information and the classification flags, namely, S13 and F3, in this example, are required first in recomposing to the original high resolution image.

0015The multiplexed signal is supplied to interface 109 which interfaces to transmission network and/or storage unit 103. The configuration of interface 109 is dependent on the particular transmission network and/or storage unit being employed. Such arrangements are known in the art.

0016The encoded image information is transmitted via a transmission network or obtained as desired from a storage unit and supplied to receiver 104 and therein via an appropriate interface 110 to demultiplexer (DMUX) 111. DMUX 111 demultiplexes, in well known fashion, the encoded basic low resolution pixel information, the encoded supplemental information and the encoded classification flags. The encoded basic low resolution pixel information is supplied to decoder 112, which decodes it in known fashion. Decoder 112 must be compatible with encoder 107 and one such decoder is described in the article entitled "Facsimile Coding Schemes and Coding Control Functions for Group IV Facsimile Apparatus", cited above. The decoded pixel information for I3 is supplied to recomposition processor 113-3 and to image output unit 105. Also supplied to recomposition processor 113-3 are the encoded supplemental information SI3 and encoded classification flag F3. Recomposition processor 113-3 is responsive to the basic low resolution pixel information for I3, the supplementary information SI3 and classification flag F3 to recompose a "high" resolution image I2. The relationship of low resolution replica I3 to "high" resolution image I2 is identical, to I0 and I1, as shown in FIG. 2 and described above. Pixels of the recomposed "high" resolution image I2 are supplied to image output unit 105 and to recomposition processor 113-2. Also supplied to recomposition processor 113-2 are the encoded supplemental information S12 and classification flag F2. Recomposition processor 113-2 is responsive to the supplied low resolution pixel information for I2, supplemental information SI2 and classification flag F2 to generate pixels forming "high" resolution image I1, in a manner identical to that employed in recomposition processor 113-3. The pixel information for image I1 is supplied to image output unit 105 and to recomposition processor 113-1. Again, also supplied to recomposition processor 113-1 are encoded supplemental information SI1 and the encoded classification flag F1. Recomposition processor 113-1 is responsive to the supplied pixel information for I1, supplemental information SI1 and classification flag F1 to generate pixels forming the original high resolution image I0. The structure and operation of recomposition processor 113-1 and is identical to recomposition processors 113-2 and 113-3 and is described below. Pixels forming image I0 are supplied to image output unit 105.

0017Since pixel information for each of images I0, I1, I2 and I3 is supplied to image output unit 105, any one of the resolution levels can be selected, as desired, and the recomposition process can be stopped when an acceptable or desired resolution has been obtained.

0018FIG. 3 shows, in simplified block diagram form, details of decomposition processor 106-1. Since the operation and structure of each of decomposition processors 106-1 through 106-3 is identical only decomposition processor 106-1 will be described in detail. Accordingly, decomposition processor 106-1 includes reduction processor 301, cluster classifier (CC) 302, supplemental information (SI) encoder 303 and classification flag encoder 304. High resolution pixels from an image, in this example I0, are supplied to reduction processor 301, CC 302 and SI encoder 303. Reduction processor 301 yields low resolution pixels L1(k,l) of low resolution replica I1 from the supplied high resolution pixels. To this end, reduction processor 301 may employ any desired set of reduction rules. One possible set of reduction rules which may be employed are those described in a document entitled "Progressive coding method for bi-level images", submitted to the Joint Bi-level Image Group and identified as ISO/JTC1/SC2/WG8, Document N-75, Dated January 1989. SI encoder 303 and flag encoder 304 may be any of known encoders. Preferably, the encoders are of the arithmetic type which are known in the art.

0019CC 302 is employed, in accordance with an aspect of the invention, to classify the clusters of pixels as being one of a plurality of classifications. In this example, not to be construed as limiting the scope of the invention, each cluster is classified as being in either a first classification or a second classification. The first classification is defined as a cluster having at least one pixel that is typically predictable and is an exception to the general prediction rules. The second classification is defined as a cluster including typically predictable pixels with no exceptions and/or non-­typically predictable pixels. Flag encoder 304 generates an appropriate classification flag F1 indicating the classification of the corresponding cluster. In this example, classification flag F1 being a logical "1" indicates the first classification and classification flag F1 being a logical "0" indicates the second classification. CC 302 generates a signal for enabling SI encoder 303 to encode the corresponding supplemental information for all pixels in a cluster classified as the first classification and for non-typically predictable pixels in a cluster classified as the second classification. The supplemental information to be encoded includes, in this example, the colors of the high resolution pixels s1, s2, s3 and s4.

0020The prediction rules employed in this embodiment include the use of a first group of pixels, in conjunction with a current low resolution pixel L1(k,l), to determine if the corresponding high resolution pixels to be recomposed are typically predictable, non-typically predictable or typically predictable which are exceptions to the general prediction rules. The group of pixels assigned, in this example, is graphically illustrated in FIG. 4. The row and column locations of the pixels of the assigned group in the low resolution replica and the super pixel assignments in the high resolution image are shown in FIG. 5. Thus, in low resolution replica I1 the group includes low resolution pixels labeled U, A, D, P, N, K, B and L surrounding the current low resolution pixel L1(k,l) labeled S. In high resolution image I0 the pixels are, in this example, the high resolution pixels forming the high resolution super pixel being decomposed into the current low resolution pixel labeled S, namely, s1, s2, s3 and s4.

0021The prediction rules are as follows: <ul id="ul0002" list-style="none"><li>(a) High resolution pixels to be recomposed from the current low resolution pixel labeled S are typically predictable and not an exception, if U=A=D=P=S=N=K=B=L and s1=s2=s3=s4=S.</li><li>(b) High resolution pixels to be recomposed from the current low resolution pixel S are typically predictable and an exception, if U=A=D=P=S=N=K=B=L and the color of any of s1, s2, s3 or s4 is not the same as S5.</li><li>(c) High resolution pixels to be recomposed from the current low resolution pixel S in conjunction with the general prediction rules are non-­typically predictable, if the color of any of U, A, D, P, N, K, B or L is not the same as S.</li></ul>

0022In this example, the color of the high and low resolution pixels is assumed to be either white represented by a logical "0" or black represented by a logical "1". It will be apparent that any other desired colors could equally be employed. Additionally, all the high resolution pixels are available, in this example, from an image source 101 and all the low resolution pixels are available from reduction processor 301. For subsequent ones of decomposition processors 106, the high resolution pixels are available from the prior one of decomposition processors 106.

0023FIG. 6 is a flow chart illustrating the generic operation of cluster classifier 302. The classification process is entered via start step 601. Thereafter, operational block 602 reads the image parameters, for example, the size of the image, i. e., the number of rows M and columns N to be obtained from image source 101 or from a prior one of decomposition processors 106, the number of clusters and the size, i. e., the configuration, of the cluster. Then, operational block 603 causes the next cluster of pixels to be read. As indicated above, the clusters could include pixels in any desired configuration. One advantageous configuration is one row of pixels in the low resolution replica which corresponds to two rows of high resolution pixels in the high resolution image. Operational block 604 calls subroutine CC-TG, shown in FIG. 7. As explained below, subroutine CC-­TG classifies the particular cluster, causes the pixels to be appropriately encoded and generates the appropriate classification flag for the classified cluster. Conditional branch point 605 tests to determine if the image has been completed, i. e., if all the clusters have been read, classified and appropriately encoded. If the test result is NO, steps 603 through 605 are repeated until step 605 yields a YES result. Then, the process is ended via step 606.

0024FIG. 7 is a flow chart illustrating subroutine CC-TG which is a generic classification and encoding process, in accordance with an aspect of the invention. Accordingly, the subroutine is entered via step 701. Then operational block 702 initializes the classification type index Y to Y=0. Conditional branch point 703 tests whether the current cluster is type Y. If the test result is NO, operational block 704 sets the classification index to Y=Y+1. Conditional branch point 705 tests to determine if there are any more classifications. If the test result is YES, steps 703 through 705 are repeated until either step 703 yields a YES result or step 705 yields a NO result. If the test result in step 703 is YES, the cluster is a classification Y type cluster and operational block 706 causes the classification flag for cluster type Y to be sent. If the test result in step 705 is NO, the cluster is a classification Y+1 type cluster and step 706 causes the classification flag for cluster type Y+1 to be sent. here Y+1 is the total number of possible cluster classifications. Operational block 707 causes the pixels of the cluster to be encoded via the appropriate technique assigned to the classification of the cluster. Thereafter, control is returned to the main routine of FIG. 6 via step 708.

0025Fig. 8 is a flow chart illustrating operation of decomposition processor 106-1 of FIG. 3 for an embodiment of the invention. The cluster configuration employed in this embodiment of the invention is one including high resolution pixels in two rows of the high resolution image and a corresponding single row in the low resolution replica being generated. Accordingly, the operational process in begun via start step 801. Then, operational block 802 reads the image parameters, i. e., the numbers of rows M and the number of columns N. Operational block 803 initializes the high resolution image row and column indices m and n, respectively, to be m=n=0. Operational block 804 causes subroutine CC-T to be called. Subroutine CC-T causes the particular clusters to be classified, the appropriate classification flag to be sent and the encoding of the pixels in the cluster according to the technique assigned to the cluster classification. Details of subroutine CC-T are described below. Operational block 805 causes the high resolution row index to be incremented by two rows, i. e., sets m=m+2. This follows, since the cluster includes two rows of pixels in the high resolution image. Then, conditional branch point 806 tests to determine if the image has been completed, i. e., if m≧M. If the test result is NO, the image has not been completed and steps 804 through 806 are repeated until step 806 yields a YES result. Then, the operational process is ended via step 807.

0026FIG. 9 and FIG. 10 when connected A-A form a flow chart of subroutine CC-T illustrating operation of one embodiment of the invention. In this embodiment, the clusters are being classified as either classification zero (0) or classification one (1). Again, a cluster is classified as classification zero when all the pixels in the cluster are typically predictable with no exception and/or non-typically predictable. A cluster is classified as classification one when it includes at least one typically predictable pixel which is an exception to the general prediction rules described hereinbefore.

0027Accordingly, subroutine CC-T is entered via step 901. Then, operational block 902 initializes the high resolution image column index to be n=0 and the low resolution replica row index to be k=m/2. Operational block 903 sets the low resolution replica column index to be l=n/2. Conditional branch point 904 tests to determine if the current low resolution pixel L0(k,l) being processed is typically predictable in accordance with the general prediction rules described above. If the test result in step 904 is YES, the current low resolution pixel is typically predictable and conditional branch point 905 tests to determine if it is an exception to the general prediction rules. As described above, a typically predictable pixel is an exception, if the corresponding high resolution pixels cannot be properly recomposed by using the general prediction rules. If the test result in step 905 is YES, the pixel is an exception and, consequently, the cluster is classified as being classification one. Thus, operational block 908 causes the classification flag for the current cluster to be FLAG=1 identifying the current cluster as being a classification one type. Operational block 907 causes the classification flag Fl to be sent as an output. Returning to step 904, if the test result is NO, the current low resolution pixel being processed is a non-typically predictable one and operational block 908 causes the column index in the high resolution image to be incremented by two, i. e., n=n+2. This follows because a low resolution pixel is derived from high resolution pixels in two columns and two rows of the high resolution image. Similarly, returning to step 905, if the test result is NO, the pixel is typically predictable and not an exception to the general prediction rules, as described above. Operational block 908 increments the high resolution image column index to be n=n+2, as described above. Then, conditional branch point 909 tests to determine if the cluster has been completed. If the test result in step 909 is NO, the cluster has not been completed and appropriate ones of steps 903,904,905,908 and 909 are repeated until either step 905 or step 909 yields a YES result. Again, if step 905 yields a YES result, the cluster includes at least one typically predictable pixel which is an exception and step 906 causes the cluster to be classified as being classification one by generating FLAG=1. If step 909 yields a YES result, the cluster includes pixels that are typically predictable without an exception and/or pixels that are non-typically predictable and operational block 910 causes the cluster to be classified as being classification zero by generating FLAG=0. Thereafter, step 907 causes the FLAG to be sent as output F1. As described above steps 902 through 910 effect the classification of the individual clusters, in accordance with aspects of the invention.

0028The remainder of subroutine CC-T controls the encoding of the pixels, i. e., whether or not supplemental information needs to be encoded for the pixels. To this end, operational block 911 initializes column index n to be n=0. Operational block 912 sets the low resolution replica column index l to be l=n/2. Conditional branch point 913 tests to determine if the cluster has been classified as classification zero, i. e., is FLAG=0. If the test result in step 913 is NO, the cluster is a classification one type and operational block 914 causes the supplemental information (SI1) for the high resolution pixels in the super pixel corresponding to the current low resolution pixel being processed to be encoded, as described below. Returning to step 913, if the test result is YES, the cluster classification, in this example, is classification zero and conditional branch point 915 tests to determine if the current low resolution pixel L1(k,l) is typically predictable. If the test result in step 915 is No, the pixel is non-typically predictable and step 914 causes the corresponding supplemental information (SI1) to be encoded, as described above. If the test result in step 915 is YES, the pixel is typically predictable and, consequently, supplemental information is not needed to be generated. Operational block 916 causes the column index to be incremented to n=n+2. Conditional branch point 917 tests to determine if the cluster which in this example includes pixels in a row, has been completed, i. e., if n≧N. If the test result is NO, appropriate ones of steps 912 through 917 are repeated until step 917 yields a YES result. Then, control is returned to the main routine of FIG. 8.

0029In this example, when supplemental information is needed to be encoded that supplemental information is representative of the colors of the high resolution pixels s1, s2, s3, and s4. Since it is assumed, in this example, that each high resulution pixel can be either black or white, there are sixteen possible combinations of colors for the high resolution pixels. The supplemental information (SI1) being generated for the current low resolution pixel is a binary number depending on the colors of the high resolution pixels s1, s2, s3 and s4. By way of an example, if s1 is white, s2 is black, s3 is white and s4 is black, the supplemental information to be encoded is SI1=0101 (binary).

0030FIG. 11 shows, in simplified block diagram form, details of recomposition processor 113-1. Since the operation and structure of each of recomposition processors 113-1 through 113-3 is identical, only recomposition processor 113-1 will be described in detail. Accordingly, recomposition processor 113-1 includes cluster classifier (CC) 1101, supplemental information (SI) decoder 1102 and flag decoder 1103. Low resolution pixels representative of low resolution replica I1 are, in this example, supplied to decomposition processor 113-1 from prior recomposition processor 113-2. If the particular one of recomposition processors 113 is the first or an only one in a series, the low resolution pixels are obtained from transmission network and/or storage unit 103 (FIG. 1) via interface 110, DMUX 111 and decoder 112. Encoded supplemental information SI1 is supplied from DMUX 111 (FIG. 1) to SI decoder 1102 and encoded cluster flag F1 is also supplied from DMUX 111 to flag decoder 1103. SI decoder 1102 must be compatible with SI encoder 303 employed in decomposition processors 106. Similarly, flag decoder 1103 must be compatible with flag encoder 304 also used in decomposition processors 106. Preferably, decoders 1102 and 1103 are of the arithmetic type which are known in the art.

0031CC 1101 is employed, in accordance with an aspect of the invention, to determine the classifications of the clusters and, in turn, which pixels in the classified clusters require supplemental information to properly recompose the high resolution pixels. It is noted that for certain cluster classifications supplemental information is required to recompose all of the pixels therein. To this end, decoded flag F1 is supplied from flag decoder 1103 and decoded supplemental information SI1 is supplied from SI decoder 1102 to cluster classifier 1101.

0032Operation of CC 1101, in accordance with an aspect of the invention, is described below. In this example, it is noted that all the low resolution pixels L1(k,l) for low resolution replica I1 are available and that all high resolution pixels h0(m,n) recomposed prior to the current high resolution pixel being recomposed are available.

0033FIG. 12 is a flow chart of the generic operational steps of recomposer processor 113-1 of FIG. 1. Accordingly, the operation of CC 1101 is begun via start step 1201. Then, operational block 1202 obtains the parameters of the image to be recomposed, for example, the size of the image, i. e., the number of rows M and columns N of the high resolution image I0 being recomposed, which is to be obtained from a prior one of recomposition processors 113 or from decoder 103, the number of clusters in the image and the size, i. e., the configuration of the individual clusters. Operational block 1203 causes the next cluster of pixels to be read. Operational block 1204 causes subroutine CC-RG to be called. Subroutine CC-RG is a generic subroutine which determines the classification of the cluster and, accordingly, decodes the pixels in the cluster according to the classification.

0034Thus, referring to FIG. 13, there is shown a flow chart of subroutine CC-RG. The process is entered via step 1301. Then, operational block 1302 causes the flag associated with the cluster to be read. Operational block 1303 causes the pixels in the cluster to be recomposed, i. e., decoded according to the classification of the cluster. Thereafter, control is returned to the main routine of FIG. 12. Referring again to FIG. 12, conditional branch point 1205 tests to determine if the image has been completed. If the test result is NO, steps 1203 through 1205 are repeated until step 1205 yields a YES result. Then, the process is ended via step 1206.

0035FIG. 14 is a flow chart illustrating operation of recomposition processor 113-1 of FIG. 11 for an embodiment of the invention. The cluster configuration employed in this embodiment of the invention is one including high resolution pixels in two rows and two columns of the high resolution image and a single row and column of the corresponding low resolution replica. Accordingly, the process is begun via start step 1401. Thereafter, operational block 1402 reads the number of rows M and the number of columns N in the image. Operational block 1403 initializes the high resolution image row and column indices m and n, respectively, to be m=n=0. Operational block 1404 calls subroutine CC-R which is employed, in accordance with an aspect of the invention, to classify and decode the clusters of pixels to recompose the high resolution image. Subroutine CC-R is described below. Operational block 1405 increments the row index of the high resolution image, namely setting m=m+2. Conditional branch point 1406 tests to determine if the image has been completed, namely, if m≧M. If the test result is NO, steps 1404 through 1406 are repeated until step 1406 yields a YES result. Then, the process is ended via step 1407.

0036FIG. 15 is a flow chart of subroutine CC-R illustrating the operation of one embodiment of the invention. Accordingly, the process is entered via step 1501. Then, operational block 1502 initializes the high resolution image column index to be n=0 and the low resolution replica row index to be k=m/2. Operational block 1503 causes the cluster flag to be read. Again, in this embodiment of the invention, classification FLAG=0 indicates that the pixels in the cluster are typically predictable without exception and/or non-typically predictable and are to be decoded using the general prediction rules and the corresponding supplemental information for the typically non-predictable pixels, and classification FLAG=1 indicates that all pixels in the cluster are to be decoded using the corresponding supplemental information SI1. Operational block 1504 sets the low resolution replica column index to be l=n/2. Conditional branch point 1505 tests to determine if the cluster FLAG=0. If the test result in step 1505 is NO, the cluster is a classification one type and operational block 1506 causes the supplemental information for the pixel to be decoded. That is, the color for high resolution pixels s1, s2, s3 and s4 for the pixel is obtained. If the test result in step 1505 is YES, the cluster is of classification type zero since FLAG=0 and the pixels therein are either typically predictable with no exception or non-typically predictable. Conditional branch point 1507 tests to determine if the current low resolution pixel L1(k,l) being processed is typically predictable (as described above in relation to step 915 of FIG. 10). If the test result in step 1507 is NO, the pixel is non-typically predictable and step 1506 causes the supplemental information for the pixel to be decoded, as described above. If the test result in step 1507 is YES, the pixel is typically predictable and it is decoded in accordance with the general predict rules, in this example, the color of each of s1, s2, s3, and s4 is set equal to the color of the current low resolution pixel L1(k,l). Operational block 1509 sets the high resolution column index to be n=n+2. Conditional branch point 1510 tests to determine if the cluster has been completed, namely, if n≧N. If the test result is NO, the cluster has not been completed and appropriate ones of steps 1504 through 1510 are repeated until step 1510 yields a YES result. Then, control is returned to the main routine of FIG. 14 via step 1511.