Basic algorithm for one block

A project log for 3RGB image lossless compression format


Yann Guidon / YGDESYann Guidon / YGDES 06/01/2017 at 04:110 Comments


  1. Get the min/max of each component:
    // the input data for one 8×8 block:
    var R=Array(64),
    // scan:
      var t=R[i],
      if (minR > t) minR = t;
      if (maxR < t) maxR = t;
      if (minG > u) minG = t;
      if (maxG < u) maxG = t;
      if (minB > v) minB = t;
      if (maxB < v) maxB = t;
    maxR -= minR,
    maxG -= minG;
    maxB -= minB;
    send_phaseout(maxR, 255-minR);
    send_phaseout(maxG, 255-minG);
    send_phaseout(maxB, 255-minB);
      R[i] -= minR,
      G[i] -= minG,
      B[i] -= minB;
    // Prediction filter can be applied here too
  4. Sort the component in order of max. amplitude
    var Cmax, Cmed, Cmin;
    var maxMax, maxMed, maxMin;
      Cmed =    G; // speculative assignation
    maxMed = maxG; // (used by two cases)
    if (maxR > maxG) {
    // possible cases: BRG, RBG, RGB
        Cmin =    G; // speculative assignation
      maxMin = maxG; // (used by two cases)
      if (maxR > maxB) {
    // possible cases: RBG, RGB
          Cmax =    R;
        maxMax = maxR;
        if (maxG > maxB) {
    // actual case: RGB
            Cmin =    B;
          maxMin = maxB;
        } else {
    // actual case:  RBG
    //  (can goto to case GBR)
            Cmed =    B;
          maxMed = maxB;
      } else {
    // actual case: BRG
          Cmax =    B;
        maxMax = maxB;
          Cmed =     R;
        maxMed =  maxR;
    } else {
    // possible cases: BGR, GBR, GRB
        Cmin =    R; // speculative assignation
      maxMin = maxR; // (used by two cases)
      if (maxG > maxB) {
        // possible cases: GRB, GBR
          Cmax =    G;
        maxMax = maxG;
        if (maxR > maxB) {
    // actual case: GRB
            Cmin =    B;
          maxMin = maxB;
            Cmed =    R;
          maxMed = maxR;
        } else {
    // actual case:  GBR
            Cmed =    B;
          maxMed = maxB;
      } else {
    // actual case: BGR
          Cmax =    B;
        maxMax = maxB;
    1. σα(Cmax, Cmed) generates
    2. σα(S1, Cmin) generates
        // (Compute step 5 here)
      send_phaseout(S2, L3); // Sum
      send_phaseout(A2, L4); // Cmin
      send_phaseout(A1, L2); // Cmed
  7. Steps 5 and 6 can also be computed in parallel with a similar version, which uses predictions from the previous neighbours.
    • The sizes of the resulting 2 bistreams (with and without prediction) are compared and the largest block is discarded.
    • If prediction is used, a single-bit flag must also be set in the prefix of the block. You can't decode the whole block if there is a mix of raw and predicted values.
    • The prediction can be computed in step 3 for example.
    • Linear prediction is computed modulo the given component's range, such that negative predictions wrap around (but still give a bit-accurate result when added again, modulo the range)
  8. Both versions (raw and predicted) can also be tentatively encoded with 3R. The order of encoding follows the order in step 6, which allows accurate reconstruction:
    1. First, the block of the sums S2 is processed, with total MAX = L3<<6, and individual MAX=L3 (global for the whole tree, implicit from the data provided in step 2, which also allows to de-shuffle Cmin, Cmed and Cmax)
    2. Then, Cmin is encoded with the individual A2s. The individual L4 are used for the limits, and the total sum is limited by the sum of all L4 (that depends on maxMin and S2).
    3. Finally, Cmed is encoded with the individual A1s and L2s (which can be recovered from the previous steps 8.a and 8.b as well as maxMed)
    Cmax can be recovered later by the subtraction of the previous data.
    Of course, another flag must be set to indicate that 3R is used instead of direct encoding.

OK, it looked pretty easy and simple in the beginning and now we're doing pretty complex stuff but in theory, none of these steps should (significantly) expand input data (except for a few control bytes). For both cases of prediction (with/without) the shortest result is chosen.

Another version/approach encodes S2, A2 and A1 in separate sub-blocks with phasing-out, while at the same time computing the tree sum of the corresponding 3R. This way, each of the block can be selected for the shortest version, in case 3R inflates. The 3R flag is then stored in the first bits of the sub-block.

The number of cases is further increased for the situation of delta-images, with the encoding of the difference with the previous frame. This is possible for pre-computed videos, where a fast computer can compute all 3 cases and choose the best result, while the overhead for the decoder is marginal (only one block to decode, with just a few parameters to change).

Note: for delta-blocks, the parameters minX might be dropped because differences are centered around 0. Samples then have to be "folded" to keep them positive.