Parallel digital image compression system for exploiting zerotree redundancies in wavelet coefficients

A system for processing digital data comprising a plurality of data elements representing an image, said system including:

• data processing means, responsive to said data elements, generating coefficients representing said data elements;
• said data processing means evaluating said coefficients at successively finer threshold values from larger coarse values to smaller fine values to determine significant and insignificant coefficients, where a coefficient is significant if its magnitude exceeds a given threshold value;
• said data processing means, responsive to coefficients evaluated thereby, representing information determined at previous coarse threshold values in the form of (a) a dominant list containing entries of evaluated coefficients that have not as yet been identified as significant at previous coarse threshold values;
• and (b) a subordinate list containing entries of evaluated coefficients that have been identified as significant at previous coarse threshold values;
• said data processing means, responsive to an evaluated coefficient, generating a tree structure having a path from an evaluated coefficient at a level of coarse information to descendant coefficients generated at levels of relatively finer information, where coarse information represents low frequency image information over a given spatial area and fine information represents high frequency image information over a relatively smaller spatial area, each descendant coefficient representing an area corresponding to a portion of an area represented by a root of said tree structure;
• said data processing means evaluating entries of coefficients on said lists to generate a plurality of symbols including (a) a first symbol indicating that a coefficient on said dominant list is significant with respect to a current threshold value and exhibits a positive value;
• (b) a second symbol indicating that a coefficient on said dominant list is significant with respect to a current threshold value and exhibits a negative value:
• (c) a third symbol indicating that a coefficient on said dominant list is insignificant with respect to a current threshold value, but that there is at least one descendant in the associated tree that is significant with respect to said current threshold value, a last named descendant being insignificant with respect to all prior larger threshold values;
• and (d) a fourth symbol indicating that a coefficient on said dominant list is insignificant with respect to a current threshold value, and that all descendants in the associated tree, except those found to be significant with respect to a prior larger threshold value, are insignificant with respect to said current threshold value;
• and
• coding means coupled to said data processing means to receive said first symbol, said second symbol, said third symbol and said fourth symbol, said coding means coding said first symbol, said second symbol, said third symbol and said fourth symbol to produce an output data bit stream;
• said data processing means comprising an array of processing elements, said array having a size of AX rows by AY columns;
• each of said processing elements of said array generating at least one zerotree, said at least one zerotree indicating that said coefficient on said dominant list is insignificant with respect to said current threshold value, and that all of said descendants in the associated tree, except those found to be significant with respect to said prior larger threshold value, are insignificant with respect to said current threshold value.