unscale2x algorithm - reverse of scale2x (notes/pseudocode)

unscale2x.txt

A reverse procedure of Scale2x, as defined by https://www.scale2x.it/algorithm:

ABC
DEF
GHI

    B   B  
 D  E0  E1  F  
 D  E2  E3  F  
    H   H  

if (B != H && D != F) {
	E0 = D == B ? D : E; // (1)
	E1 = B == F ? F : E; // (2)
	E2 = D == H ? D : E; // (3)
	E3 = H == F ? F : E; // (4)
} else {
	E0 = E;              // (5)
	E1 = E;              // (6)
	E2 = E;              // (7)
	E3 = E;              // (8)
}

Observe that if B!=D then for either block (1 or 5), E0==E.

Otherwise, we know B==D, and can substitute D for B in the code:

if (B != H && B != F) {
	E0 = B;              // (9)
	E1 = B == F ? F : E; // (10)
	E2 = B == H ? B : E; // (11)
	E3 = H == F ? F : E; // (12)
} else {
	E0 = E;              // (13)
	E1 = E;              // (14)
	E2 = E;              // (15)
	E3 = E;              // (16)
}

Note in (11) and (12), that both (B==F) and (B==H) are false, so we know E1==E and E2==E.

So whether or not B==D, we can work out the value of E.


So all we need to calculate E are:
- B and D (or in fact, just whether they're equal)
- E0 and either E1 or E2.

This means if we have E0 and E1 (given), and have unscaled the values above and to the left, we can proceed to unscale subsequent values going from left to right and top to bottom.

  BBBB
DDE0E1F0
DDE2E3F2
  H0H1


As a base case, we do need to know the unscaled values of the top/left edges and corner.  The algorithm defines how these are calculated in Scale2x:

"The image border is computed reusing the value of the nearest pixel on the border when the value of a pixel over the border is required."


So for the top-left corner, B==D==E
From previous calculations, when B==D we know that E==E1==E2, and can easily see E0==E, so E==E0==E1==E2==B==D.

For the top  edge, B==E.  E0 is always either D==B or E, so we know E==B==E0.
For the left edge, D==E.  E0 is always either D==B or E, so we know E==D==E0.

So in all three edge/corner cases, E==E0.


So pseudocode for unscaling an image looks something like this:

for (i=0; i<height; i++) {
  for (j=0; j<width; j++) {

    E0 = src[i*2][j*2];
    E1 = src[i*2][j*2+1];


    if (x==0 || y==0) {
      // top/left edge
      dst[i][j] = E0;
    } else {
      // main part of image
      B = dst[i-1][j];
      D = dst[i][j-1];

      if (B==D) {
        dst[i][j] = E1;
      } else {
        dst[i][j] = E0;
      }
    }

  }
}

Note: a Scale2x'd image should obviously have an even number of rows and columns.  But if there is an odd number, then the following logic is suggested to cope with trailing rows/columns.

In the final odd column, E1 is not available.  If the value is needed (i.e. in the case of B==D), we know that E==E1==E2 (see above), so we can just use E2 instead.
Similarly, in the final odd row, use E1 when needed in place of E2.
If there is a trailing row and column, the bottom-right corner pixel is the only one where we cannot (necessarily) recover the original E, in which case the only sensible value to take is E0.

Note that an odd number of rows/columns implies the image has been cropped after scaling, which will likely cause the image to be misaligned (see below).


Additional Remarks:

- This algorithm is not expected to achieve "nice" results in general when halving the size of an image that has not been Scale2x'd.

-In particular, it will probably perform poorly on misaligned images - if a Scale2x'd is cropped from the top or left sides by an odd number of pixels.  To guard against this, you can run the algorithm 4 times (starting at positions (0,0), (0,1), (1,0), (1,1) - you'll also have to cope with odd top/left edges) - then run Scale2x on each result (cropping slightly to make the appropriate edges "odd" again), and return one that matches perfectly.  If none of them match, then you can throw an error or return the "closest" match.

- That said, because E is only set to E0 or E1 (not B or D, etc.), this algorithm will happily shrink an image which has been doubled with nearest-neighbour scaling, because in this case E0==E1==E2==E3.  (It will also work with a vertical misalignment, because it doesn't use E2 or E3.)  However, it's not clear whether the result will be "closer" to the original than the two horizontal misalignments.



Finally, some notes on Scale3x:

    B   B   B
 D  E0  E1  E2  F0  
 D  E3  E4  E5  F3  
 D  E6  E7  E8  F6  
    H0  H1  H2

- An Unscale3x algorithm is actually really easy - the algorithm preserves the center pixel: E4 = E.  So to reverse the algorithm, you just take the center pixel of each 3x3 square.  This is a very simple scaling algorithm, so results for non-Scale3x'd images should look fairly "nice".

- Many of the same caveats apply as with Scale2x.  Images scaled up 3x with Nearest Neighbor scaling will behave well - regardless of alignment.  Other kinds of image will behave about as well as you'd expect on a nearest-neighbor shrink.

- Again, to guard against misalignment, run Unscale3x and Scale3x 9 times (one for each possible alignment, remembering to crop as needed) and take the "closest" one.

- For images cropped to a non-multiple of 3 - or misaligned images - if the center pixel of a block has been cropped off, the obvious choice is to just take the closest pixel still available.