Efficient encoding/decoding in the decomposition and recomposition of a high resolution image

` ` ~01~93~ -- 1 EFFICIENT ENCODING/DECODING IN THE ; DECOMPOS~TION AND RECOMPOSITION OF A HIGH RESOLUTION lMAG~ Technical Field This invention relates to transmission and/or storage of images and, more particularly, to eff~lcient encoding/decoding of image information.

Back~round of the Invention . Recently, there has been a rapid increase in the transmission and/or storage of image information and the like.

This has been especially 10 true in the use of facsimile.

Additionally, use of high resolution monitors for generating a ~oft copy and/or browsing of the image information has resulted in additional requirements being placed on digital transmission andtor storage interfaces.

In certain applications, rapid progression from a low resolution replica to a high resolution image is desirable and ss:~metimes 15 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 20 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 25 rules.

That is, the reduction rules were modified to force a pixel to sati~ify J 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,4~7 issued September 2~ 89 for one such prior arrangement.

A 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 35 change in the image reduction rules would require development of a new set ol pr~diction rules.

This Interdependence of the image reduction rules and . .i .

1 , ~ ..

:' 1 . '.'1 .. .

2~14936 the pr~diction rules is undesirable.

More 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 S 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 thisarrangement operates satisEactorily in many applications, its complexity and inefficiency renders it undesirable for other applications.

Summar~ of the Invention , 15 The 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 socalled clusters and by classifying each cluster as having one of a plurality of classifications.

In accordance with one aspect of the invention there is provided apparatus for encoding pixels in the decomposition of a high resolution image into a low resolution replica and supplemental information for transmission or storage,comprising: means for generating low resolution pixels &om supplied high resolution , pixels from an image source to obtain said low resolution replica; means for interfacing an output from said apparatus to a transmission medium or storage unit; the apparatus being CHARACTERIZED BY means for obtaining a plurality of low resolution pixels Erom said low resolution replica in a prescribed cluster conEiguration; means for obtaining a plurality of high resolution pixels from said high resolution image in prescribed relationship to said low resolution pixels in said cluster; means for obtaining a group of pixels in a prescribed relationship to a current low resolution pixel from said cluster; means for utilizing said pixels in said group and prescribed ones of said obtained high resolution pixels for determining in accordance with the prescribed . . .

-~ ~ A~ ~ 2~14936 - 2a prediction criteri~ one or more high resolution pixels to be recomposed for saidcurrent low resolution pixel are non-typically predictable, typically predictable and not an exception or typically predictable and an exception; means for classirying said cluster as being a first classification if the high resolution pixels being recomposed ~or said current low resolution p*el are determined to be typically predictable and an exception, generating a classification indicator representation of said frst classification, and, generating supplemental information for all high resolution pixels corresponding to said low resolution pixels in said cluster; means for genera~ing supplementalinformation for said current low resolution pixel if said one or more high resolution pixels to be recomposed for it are determined to be non-typically predictable;

classifying said cluster as being a second classification if none of said high resolution pixels being recomposed for said low resolution pixels in said cluster is determined to be typically predictable and an exception, generating a classification indication representative of said second classification and generating supplemental information for said one or more high resolution pixels to be recomposed for said low resolution pixel in said cluster determined to be non-typically predictable; and means for supplying as an output said classification indication, and said supplemental information, if any. ~:

In 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 classifcation flag. A cluster including typically predictable pixels with no exception and/or non-typically pixels is classified as having a 'j second classification and is ideneified 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.

`~ In recomposing a "high" resolution image, the high resolution pixels are recomposed, in accordance with an aspect of the invention, by employing the i 30 classification flags of the clusters.

If a cluster has the arst classification flag, all of the high resolution pixels are recomposed from the accompanying supplemental information.

If a cluster has the second classification f,ag, the high resolution pixels are recomposed in accordance .. . .

. ~ ~ '~ A , .

2~1~93f~ -- 3 -with the general prediction rules and if they are non-typically predictable pixels, from the accompanying supplemental information.

Brief Description of the Drawing;

In the Drawing:

FIG.l shows, in simplified block diagram form, details of a progressive image transmission and/or storage system which advantageously - employs aspects of the invention;

FIG.2 depicts in graphic form a high resolution image and a corresponding low resolution replica useful in describing embodiments of the 10 invention;

FIG.3 shows, in simplified block diagram form, details of one of the decomposition processors employed in the embodiment of FIG. 1;

FIG.4is a graphical representation of portions of a high ' resolution image and a low resolution replica useful in describing aspects of 'i~ 15 the invention;

i FIG.5is a table depicting a so-called group pixel assignment and super pixel assignment useful describing an embodiment of the invention;

FIG.6 illustrates a flow chart depicting the generic operation, in accordance with an aspect of the invention, of the decomposition processor 20 implementation of FIG.3;

FIG.7is 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;

FIG.8is a flow chart illustrating operation, in accordance with . an aspect of the invention, of the decomposition processor of FIG.3;

FIG.~ 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 30 accordance with an aspect of the invention, classifies clusters;

j FIG.ll shows, in simplifled block diagram form, details of one of recomposition processors of FIG.l;

FIG.12 illustrates a flow chart showing the generic operation, in accordance with aspects of the invention, of the the recomposition processor 35 implementation of FIG.ll;

.. . .

~; . .. , : ",: '- , -.. - - - - ~; 201~936 - 4 FIG. 13 is a flow chart o~ the genelic 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;

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 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.

~, Detailed Description ; FIG. 1 shows, in simplified block diagram forrn, 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.

Image source 101 provides, in this example, a desired high resolution image and may be, for example, either a scanner or a data base.

Once such scanner which may advantageously be employed is manufactured by Cannon and is designatedlaser copier scanner NP-9030.

The images to be transmitted may also be stored in a j 20 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 IO includes 400 dots per inch and has Mo rows and No columns and includes Mo x No ` ! pixels, as shown in FIG. 2. A so-called super pixel in high resolution image IO 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, hO(m,n), hO(m,n+1), hO(m+1,n) and hO(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 originalimage, at 400 dots per inch, it yields Mo = 3456 columns and No = 4672 lines for an A4 standard size document.

) ~, A~i ` 2~9~;

- 5 Also shown in ~IG. 2 are clusters of pixels and a grouping of pixels employed to determine if pixels are typically predictable or nontypically 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 5 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.

The high resolution pixels are supplied from image source 101 to transmitter 102 and, therein, to decomposition processor 10~1.

10 Decomposition processor 10~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 IO is decomposed into low resolution replica I1 having Ml rows and Nl columns plus supplemental information SI1 and classification flag F1.

In this example, Ml = Mo/2, Nl = Mo/2 and the 15 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=O and an imaginary reference row of pixels above row k=O, 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 20 be white.

The decomposition from high resolution image IO to low resolution replica I1 is realized by replacing every super pixel including high resolution pixels hO(m,n), hO(m+1,n), hO(m,n+1) and hO(m+1,n+1) in image IO with a single low resolution pixel L1(k,1).

The difference between the original high resolution image IO and the low resolution replica I1 is the 25 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 30 predictable pixel~ in a cluster cla~sified as being in the second classification.

Generation of the supplemental information is described below with respect to the decomposition process.

Transmitter 102 includes a number of decomposition processors, in this example, decomposition processors 10~1, 10~2 and 10~3.

Although 35 thrse decon~position processors are s~own, in this example, it will be ,1 apparent that any desired number may be employed depending on the .:

.,j 2~4~ particular application.

Indeed, a single decomposition process 10~1 could be employed, if desired.

Each of decompoisition processors 106-1 through 106-3 decomposes a "high" resolution image into a "low" resolution replica.

As described above, FI(:. 2 illustrates the relationship between the high 5 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 decompositis~n processor 106-1.

In turn, decomposition processor 10~2 ' generates low resolution replica I2 which, in turn, is supplied to 10 decomposition processor 10~3 as its "high" resolution image.

Decomposition processor 10~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 Il as shown in FIG. 2 and described above.

That is, in this 15 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 procei3sors 10~1 through 10~3.

Thus, the resolution of the basic low resolution replica I3, in this example, generated by decomposition processor 10~3 is 50 dots/inch.

The pixels L3(1,k) o~ the basic low resolution replica I3 are 20 supplied to encoder 107.

Encoder 107 encodes the pixels L3(1,k) in wellknown fashion.

Specifically, any one of several known CCITT or other standard encoding techniques may be employed.

One CCITT encoding technique i9 described in INTERNATIONAL TELEPHONE AND TELEGRAPH CONSULTATIVE COMMITTEE ~, "Facsimile ~' 25 Coding Schemes and Coding Control Functions for C~roup IV Facsimile Apparatus", Redbook, Facsimile VlI.3, Rec.T.6, 1~84, pages 4~48.

The encoded pixel information is supplied to multiplexer (MUX) 108.

Also, supplied to MUX 108 are encoded supplemental information and encoded classification nags from each of decomposition processors 10~1,10~2 and 30 10~3, namely, encoded supplemental information SI1, SI2 and SI3, respectively, and encoded classification flags F1, F2 and F3, respectively.

~IUX 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 ; ~ 3S that for transmission applications the encoded supplemental information ~ SI1, SI2 and SI3 and the encoded classification flags, F1, F2 and F3 are ' 'I .

,. ~ .

9 ~ ~;

- 7 multiplexed in reverse sequential order.

This is necessary because the lower resolution supplemental information and the classi~lcation flags, namely, SI3 and F3, in this e~ample, are required rlrst in recomposing to the original high resolution image.

The multiplexed signal is supplied to interface 10~ 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.

The 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 15 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 20 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 25 SI3 and classiflcation flag F3 to recompose a "high" resolution image I2.

Therelationship 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 30 recomposition processor 113-2 are the encoded supplemental information SI" and classification flag F2.

Recomposition processor 113-2 is responsive to the supplied low resolution pixel in~ormation 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 35 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 ' - ':' ~ .

,, 2 0 ~ to recomposition processor 113-1 are encoded supplemental inîormation SI1 and the encoded classification flag ~1.

Recomposition processor 113-1 is responsive to the supplied pixel information for I1, supplemental information SI1 and cli~ssif~lcation flag F1 to generate pixels forming the 5 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.

Since pixel information for each of images I0, I1, I2 and I3 is 10 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.

FIG. 3 shows, in simplified block diagram form, details of decomposition processor 10~1.

Since the operation and structure of each of 15 decomposition processors 10~1 through 10~3 is identical only decomposition processor 10~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 20 example I0, are supplied to reduction processor 301, CC 302 and SI encoder 303.

Reduction processor 301 yields low resolution pixels L1(k,1) 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 25 in a document eDtitled "Progressive coding method for bi-level images", submitted to the Joint Bi-level Image Group and identified as ISO/JTC1/SC2/WG8, Document N-7S, Dated January 198~. 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.

CC 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 ~lrst classification is defined as a cluster 35 having at least one pixel that is typically predictable and is an excep.ion to the general prediction rules.

The second classification is defined as a cluster :

s" .,, . , " , . . " . ~ " . : , - . , , " ,,; , " , ., : : , . . ... .. .

201~6 including typically predictable pixels with no exceptions and/or nontypically predictable pixels.

Flag encoder 30~ generates an appropriate classification flag Fl indicating the classification of the corresponding cluster.

In this example, classification flag Fl being a logical "1" indicates 5 the first classi~lcation and classif~lcation 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 predictablepixels in a cluster classified as the second classification.

The supplemental 10 information to be encoded includes, in this example, the colors of the high resolution pixels sl, s2, s3 and s4.

The prediction rules employed in this embodiment include the use of a first group of pixels, in conjunction with a current low resolution pixel Ll(k,l), to determine if the corresponding high resolution pixels to be 15 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 20 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,1) 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 25 pixel labeled S, namely, s1, s2, s3 and s4.

The prediction rules are as follows:

(a) High resolution pixels to be recomposed from the current low i resolution pixel labeled S are typically predictable and not an exception, if ! U=A=~=P=S=N=K=B=L and sl=s2=s3=s4=S.

(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 S.

(c) High resolution pixels to be recomposed from the current iow 35 resolution pixel S in conjunction with the general prediction rules are nontypically pred;ctable, if the color of any of U, A, D, P, N, K, B or L is not : .

~, ~ 20~49~ i - 10the same as S.

In this example, the color of the high ancl 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 5 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.

FIG. 6 is a flow chart illustrating the generic operation of cluster classifler 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 15 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 j desired configuration.

One advantageous configuration is one row of pixels in the low resolution replica which corresponds to two rows of high 20 resolution pixels in the high resolution image.

Operational block 804 calls subroutine CC-TG, shown in FIG. 7.

As explained below, subroutine CCTG classifies the particular cluster, causes the pixels to be appropriately encoded and generates the appropriate classification flag for the classifîed 1; cluster.

Conditional branch point 605 tests to determine if the image hi~s :~ 25 ~een completed, i. e., if all the clusters have been read, classifled 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.

-~ FIG. 7 is a flow chart illustrating subroutine CC-TG which is a 30 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 ' ~ 35 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 '.

.

. .

'I . -.

~,.. , . .; . .,. . ~ : ~ - --`" 2~ ~936 - 11 repeated until either step 703 yields a YES result or step 705 yield~ a NO result.

If the test result in step 703is YES, the cluster is a classirlcation Y - type cluster and operational block 706 causes the classiflcation flag for cluster type Y to be sent.

If the test result in step 705is NO, the cluster is 5 a classii~lcation Y+1 type ~luster and step 70B causes the classification flagfor cluster type Y+1 to be sent.

Where 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 10 via step 708.

Fig. 8 is a flow chart illustrating operation of decomposition processor 10~1 ~f 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 15 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 20 m=n=0.

Operational block 804 causes subroutine CC-T to be called.

Subroutine CC-T causes the particular clusters to be classirled, the appropriate classification flag to be sent and the encoding of the pixels in the cluster according to the technique z~signed to the cluster classification.

Details of subroutine CC-T are described below.

Operational block 805 2S 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 iî 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 30 repeated until step 806 yields a YES result.

Then, the operational process is ended via step 807.

FIG. ~ and FIG. 10 when connected A-A form a flow chart of su~routine CC-T illustrating operation of one embodiment of the invention.

In this embodiment, the clusters are being classirled as either classification 35 zero (0j or classirlcation one (1).

Again, a cluster is classified as l, . classification zero when all the pi~els in the cluster are typically predictable .i , .

..

2~(J~ - 12with no exception and/or non-typically predictable. A cluster is classifled as classii~lcation one when it includes at least one typically predictable pixel which is an exception to the general prediction rules described hereiIlbefore.

Accordingly, subroutine CC-T is entered via step 901.

Then, 5 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.

Oper~tional block 903 sets the low resolution replica column index to be l=n/2.

Conditional branch point ~04 tests to determine if the current low ~, resolution pixel L0(k,1) being processed is typically predictable in accordance - 10 with the general prediction rules described above.

If the test result in step ' ~04 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. A~ described above, a typically p~edictable pixel is an exception, if the corresponding high resolution pixels cannot be properly 15 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 ~06 causes the classification flag for the current cluster to be FLAG=1 identifying the current cluster as being a classification one type.

Operational block ~07 20 causes the classification flag F1 to be sent as an output.

Returning to step ~04, 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 25 resolution pixels in two columns and two rows of the high resolution image.

Similarly, returning to step ~05, 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 ~08 increments the high resolution image column index to be n=n+2, as described above.

Then, conditional 30 branch point 00~ tests to determine if the cluster has been completed.

If ', the test result in step 00~ is NO, the cluster has not been completed and , appropriate ones of steps ~03, ~04, ~05, ~08 and ~0~ are repeated until ¦ either step ~05 or step 00~ yields a YES result.

Again, if step ~05 yields a YES result, the cluster includes at least one typically predictable pixel 35 which is an exception and step ~OB causes the cluster to be classified as being classification one by generating FLAG=1. Iî step ~0~ yields a YES .: I ;!

, :,~,, : . :.... . , ., , :, .: . , . : ' 2014g36 - 13 - result, the cl~lster includes pixels that are typically prcdictable witho~lt an exception and/or pixels that are non-typically predictable and operational block 910 causes the cluster to be classiFled 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 5 through 910 effect the classification of the individual clusters, in accordance with aspects of the invention.

The 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 the high resolution image column index n to 10 be n=0.

Operational block 912 sets the low resolution replica column index 1 to be ' 1=n/2. ~onditional branch point 913 tests to determine if the cluster has been classified as classification ~ero, 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 pixel15 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,1) is typically predictable.

If the test result in step 915 is NO, the pixel is non-typically predictable and step 914 20 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, 3 consequently, supplemental information is not needed to be generated.

Operational block 916 causes the high resolution image column index to be incremented to l n=n~2.

Conditional branch point 917 tests to determine if the cluster which in this J 25 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 re~urned to the main routine of FIG. 8.

~ In this example, when supplemental in~ormation is needed to be 3, encoded that supplemental information is representative of the colors of the high 30 resolution pixels 91, s2, s3, and s4.

Since it is assumed, in this example, that each high ~, resolution 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 .

. . ' . ,~ il!d' ~ 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, s2is black, s3is white and s4 is black, the supplemental information to be - encoded is SI1=0101 (binary).

FIG. 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-3is identical, only recomposition processor 113-1 will be described in detail.

Accordingly, recomposition processor 113-1 includes cluster classifier (CC) l101, 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 recompositionprocessors 113 is the flrst or an only one in a series, the low resolution pixels 15 are obtained from transmission network and/or storage unit 103 (FIG. 1) via interface 110, DM~lX 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 DM~lX 111 to flag decoder r 1 1103. SI decoder 1102 must be compatible with SI encoder 303 employed in 20 decomposition processors 10~.

Similarly, flag decoder 1103 must be f 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.

¦ CC 1101 is employed, in accordance with an aspect of the 25 invention, to determine the classifications of the clusters and, in turn, which pixels in the classified clusters require supplemental information to properly 3 recompose the high resolution pixels.

It ls noted that for certain cluster clas~ifications supplemental information is required to recompose all of the 1 pixels therein.

To this end, decoded flag F1 is supplied from flag decoder 30 1103 and decoded supplemental information SI1 is supplied from Sl decoder ; 1102 to cluster classifier 1101.

~, Operation of CC 1101, in accordance with an aspect of the invention, is :lescribed below.

In this example, it i9 noted that all the low resolution pixels L1(k,1) for low resolution replica I1 are available and that 3S all high resolution pixels hO(m,n) recomposed prior to the current high resolution pi..el being recomposed are available.

,, .

2~1~9~ i';

- 15FIG. 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 5 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.

10 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.

Thus, referring to FIG. 13, there is shown a flow chart of 15 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, .~. 20 conditional branch point 1205 tests to determine if the image has beencompleted.

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.

FIG. 14 is a flow chart illustrating operation of recomposition 25 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, 30 operational block 1402 reads the number of rows M and the number of d~ columns N in the image.

Operational block 1403 initializes the high ;~ resolution image row and column indices m and n, respectively, to be l m=n=0.

Operational block 1404 calls subroutine CC-R which is employed, j in accordance with an aspect of the invention, to classify and decode the 35 clusters of pixels to recompose the high resolution image.

Subroutine CC-R is described below.

Operational b!ock 1405 increments the row index c,f the 1 ~.

':

.~ :

... :, . , - ,. . . - . ~ . . . ... .. ~ . . . , .. ,. . .... - . .. .. . . . . . .. . . .

2G14936 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. IE the test result is NO, steps 1404 through 1406 are repeated until step 1406 yields a Y~S result.

Then, the process is ended via step 1407.

FIG. 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 resolutis~n 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 nontypically predictable pixels, and classification FLAG=1 indicates that all pixels in thc 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 i 20 result in step 1505 is Y~S, 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 lowresolution pixel L1(k,1) being processed is typically predictable (as described above in relation to step 915 of FIG. 10).

If the test result in step 1507 iss NO, the pixel is nontypically 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,1).

Operational block 1509 sets the high resolution column index to be n=n~2.

Conditional branch point 1510 tests to determine if the i 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 j, .. ~; , ! ,, ' ., ~ , ':, ' '' ,' , :

~ 2~49~ - 17repeated until step 1510 yields a YES result.

Then, control is returned to the main routine of FIG. 14 via step 1511.

' ~.

: I . , .

, ~ :