tagtreeencoder.java

jpeg2000算法实现

                    n = ((lw>>1)<<1);
                    // Take minimum of 2 elements and put it in higher 
                    // level
                    bi = m*lw+n;
                    treeV[k+1][(m>>1)*((lw+1)>>1)+(n>>1)] =
                        (treeV[k][bi] < treeV[k][bi+lw]) ?
                        treeV[k][bi] : treeV[k][bi+lw];
                }
            }
            // Now we may have quads with 1 line, 2 or 1 columns
            if (lh%2 != 0) {
                m = ((lh>>1)<<1);
                for (n=((lw>>1)<<1)-2;n>=0;n-=2) { // All quads with 2 columns
                    // Take minimum of 2 elements and put it in higher 
                    // level
                    bi = m*lw+n;
                    treeV[k+1][(m>>1)*((lw+1)>>1)+(n>>1)] =
                        (treeV[k][bi] < treeV[k][bi+1]) ?
                        treeV[k][bi] : treeV[k][bi+1];
                }
                // Now we may have quad with 1 column, 1 line
                if (lw%2 != 0) {
                    // Just copy the value
                    n = ((lw>>1)<<1);
                    treeV[k+1][(m>>1)*((lw+1)>>1)+(n>>1)] =
                        treeV[k][m*lw+n];
                }
            }
        }
    }

    /**
     * Changes the value of a leaf in the tag tree. The new and old
     * values of the element must be not smaller than the largest
     * threshold which has yet been supplied to 'encode()'.
     *
     * @param m The vertical index of the element.
     *
     * @param n The horizontal index of the element.
     *
     * @param v The new value of the element.
     *
     *
     * */
    public void setValue(int m, int n, int v) {
        int k,idx;
        // Check arguments
        if (lvls == 0 || n < 0 || n >= w || v < treeS[lvls-1][0] ||
            treeV[0][m*w+n] < treeS[lvls-1][0]) {
            throw new IllegalArgumentException();
        }
        // Update the leaf value
        treeV[0][m*w+n] = v;
        // Update all parents
        for (k=1; k<lvls; k++) {
            idx = (m>>k)*((w+(1<<k)-1)>>k)+(n>>k);
            if (v < treeV[k][idx]) {
                // We need to update minimum and continue checking
                // in higher levels
                treeV[k][idx] = v;
            }
            else {
                // We are done: v is equal or less to minimum
                // in this level, no other minimums to update.
                break;
            }
        }
    }

    /**
     * Sets the values of the leafs to the new set of values and
     * updates the tag tree accordingly. No leaf can change its value
     * if either the new or old value is smaller than largest
     * threshold which has yet been supplied to 'encode()'. However
     * such a leaf can keep its old value (i.e. new and old value must
     * be identical.
     *
     * <P>This method is more efficient than the setValue() method if
     * a large proportion of the leafs change their value. Note that
     * for leafs which don't have their value defined yet the value
     * should be Integer.MAX_VALUE (which is the default
     * initialization value).
     *
     * @param val The new values for the leafs, in lexicographical order.
     *
     * @see #setValue
     *
     *
     * */
    public void setValues(int val[]) {
        int i,maxt;
        if (lvls == 0) { // Can't set values on empty tree
            throw new IllegalArgumentException();
        }
        // Check the values
        maxt = treeS[lvls-1][0];
        for (i=w*h-1; i>=0; i--) {
            if ((treeV[0][i] < maxt || val[i] < maxt) &&
                treeV[0][i] != val[i]) {
                throw new IllegalArgumentException();
            }
            // Update leaf value
            treeV[0][i] = val[i];
        }
        // Recalculate tree at other levels
        recalcTreeV();
    }

    /**
     * Encodes information for the specified element of the tree,
     * given the threshold and sends it to the 'out' stream. The
     * information that is coded is whether or not the value of the
     * element is greater than or equal to the value of the threshold.
     *
     * @param m The vertical index of the element.
     *
     * @param n The horizontal index of the element.
     *
     * @param t The threshold to use for encoding. It must be non-negative.
     *
     * @param out The stream where to write the coded information.
     *
     *
     * */
    public void encode(int m, int n, int t, BitOutputBuffer out) {
        int k,ts,idx,tmin;

        // Check arguments
        if (m >= h || n >= w || t < 0) {
            throw new IllegalArgumentException();
        }

        // Initialize
        k = lvls-1;
        tmin = treeS[k][0];

        // Loop on levels
        while (true) {
            // Index of element in level 'k'
            idx = (m>>k)*((w+(1<<k)-1)>>k)+(n>>k);
            // Cache state
            ts = treeS[k][idx];
            if (ts < tmin) {
                ts = tmin;
            }
            while (t > ts) {
                if (treeV[k][idx] > ts) {
                    out.writeBit(0); // Send '0' bit
                }
                else if (treeV[k][idx] == ts) {
                    out.writeBit(1); // Send '1' bit
                }
                else { // we are done: set ts and get out of this while
                    ts = t;
                    break;
                }
                // Increment of treeS[k][idx]
                ts++;
            }
            // Update state
            treeS[k][idx] = ts;
            // Update tmin or terminate
            if (k>0) {
                tmin = ts < treeV[k][idx] ? ts : treeV[k][idx];
                k--;
            }
            else {
                // Terminate
                return;
            }
        }
    }

    /**
     * Saves the current values and state of the tree. Calling
     * restore() restores the tag tree the saved state.
     *
     * @see #restore
     *
     *
     * */
    public void save() {
        int k,i;

        if (treeVbak == null) { // Nothing saved yet
            // Allocate saved arrays
            // treeV and treeS have the same dimensions
            treeVbak = new int[lvls][];
            treeSbak = new int[lvls][];
            for (k=lvls-1 ; k >= 0; k--) {
                treeVbak[k] = new int[treeV[k].length];
                treeSbak[k] = new int[treeV[k].length];
            }
        }

        // Copy the arrays
        for (k=treeV.length-1 ; k >= 0; k--) {
            System.arraycopy(treeV[k],0,treeVbak[k],0,treeV[k].length);
            System.arraycopy(treeS[k],0,treeSbak[k],0,treeS[k].length);
        }

        // Set saved state
        saved = true;
    }

    /**
     * Restores the saved values and state of the tree. An
     * IllegalArgumentException is thrown if the tree values and state
     * have not been saved yet.
     *
     * @see #save
     *
     *
     * */
    public void restore() {
        int k,i;

        if (!saved) { // Nothing saved yet
            throw new IllegalArgumentException();
        }

        // Copy the arrays
        for (k=lvls-1 ; k >= 0; k--) {
            System.arraycopy(treeVbak[k],0,treeV[k],0,treeV[k].length);
            System.arraycopy(treeSbak[k],0,treeS[k],0,treeS[k].length);
        }

    }

    /**
     * Resets the tree values and state. All the values are set to
     * Integer.MAX_VALUE and the states to 0.
     *
     *
     * */
    public void reset() {
        int k;
        // Set all values to Integer.MAX_VALUE
        // and states to 0
        for (k = lvls-1; k >= 0; k--) {
            ArrayUtil.intArraySet(treeV[k],Integer.MAX_VALUE);
            ArrayUtil.intArraySet(treeS[k],0);
        }
        // Invalidate saved tree
        saved = false;
    }

    /**
     * Resets the tree values and state. The values are set to the
     * values in 'val'. The states are all set to 0.
     *
     * @param val The new values for the leafs, in lexicographical order.
     *
     *
     * */
    public void reset(int val[]) {
        int k;
        // Set values for leaf level
        for (k=w*h-1; k>=0; k--) {
            treeV[0][k] = val[k];
        }
        // Calculate values at other levels
        recalcTreeV();
        // Set all states to 0
        for (k = lvls-1; k >= 0; k--) {
            ArrayUtil.intArraySet(treeS[k],0);
        }
        // Invalidate saved tree
        saved = false;
    }
}