A problem I had while doing graphics, a short time ago, is that while doing repeated up/down-sampling cycles, there was continual degradation. This of course leads to the idea: a general framework for resampling that avoids this problem.
Specifically, let M -> N denote the operation (and its matrix) for sampling from positive sizes M to N. The ideal situations are that:
* M -> N should result only in a ONE-TIME degradation if M > N,
* M -> N should be lossless if M < N,
* M -> N should be the identity operation if M = N.
In the following, use the notation M -> N -> P to denote the chaining of the operations M -> N and N -> P, and similar notations for longer chains.
These three requirements can then be wrapped up in the following two conditions:
[A1] M -> N -> P = M -> P, unless N < M and N < P, and
[A2] M -> M = 1_M.
Then it follows that M -> N -> M -> N = M -> N, regardless of the relative sizes of M and N -- thus the name "Semi-Lossless".
By themselves, this already says a lot. First, it implies the following decompositions:
* M -> N = M -> M-1 -> ... -> N+1 -> N, if M > N,
* M -> N = M -> M+1 -> ... -> N-1 -> N, if M < N.
Therefore, a solution to [A1] and [A2] is defined, once all the up-1 and down-1 transforms are defined.
Second, let the rank of a sequence x_M of length M be the smallest N such that
x_M (M -> N -> M) = x_M.
Then the decomposition implies that length M sequences have a basis consisting of one length M sequence each of ranks 1, 2, ..., M.
Therefore, a solution to [A1] and [A2] is defined by specifying all the sequences
A_{M,m} of length M and rank m = { 0, 1, ..., M-1 }.
Letting B_{M,m} denote the dual basis, then a transform M -> N can be defined by:
x_M (M->N) = sum_i <B_{M,i}, x_M> A_{N,i}
where the summation index i ranges from 0 to the minimum of M-1 and N-1.
So the general solution involves an A-transform and its dual B-transform, combined with truncation or zero-extension in the following way:
* Transform the sequence x_M into
X = (X_m: m = 0, ..., M-1) = (<B_{M,m}, x_M>: m = 0, ..., M-1).
* Truncate (X_0, ..., X_{M-1}) to
(x_n: n = 0, ..., N-1) = (X_0, ..., X_{N-1}) if M > N.
* Extend (X_0, ..., X_{M-1}) to
(x_n: n = 0, ..., N-1) = (X_0, ..., X_{M-1}, 0, ..., 0)
with N - M 0's, if M < N.
* Reverse transform (X_n: n = 0, ..., N-1) to
x_N = sum_{n = 0, ..., N-1} X_n a_{N,n}.
This still leaves open the question of what the sequences A_{N,n} (and their duals B_{N,n}) are to be. Additional conditions may be imposed, including the following:
[A3] Orthogonality: M -> N = (N -> M) transpose.
In that case the dual basis for length M sequences matches the basis,
B_{M,m} = k_M A_{M,m}
up to a constant factor k_M for each M.
Other conditions include:
[A4a] Row Uniformity: The rows of M -> N all have the same sum,
which is equivalent to requiring that the the 1 -> N matrices be constant column vectors; or
[A4b] Column Uniformity: The columns of M -> N all have the same sum,
which is equivalent to requiring that all the N -> 1 matrices be constant row vectors.
Another condition is:
[A5a] Symmetry: Sequence reversal and rescaling commute
This is equivalent to either of the conditions:
[A5b] The matrix M -> N is symmetric under 180 rotation,
[A5c] Odd rank sequences are symmetric under reflection,
while even rank sequences are anti-symmetric under reflection.
For instance, for 3 -> 2, one would have:
a b c
c b a
Uniformity and symmetry determine the lowest-order transforms:
2 -> 1 = 1 1 up to proportionality
3 -> 2 = up to proportionality:
(root 2 + root 3) (root 2) (root 2 - root 3)
(root 2 - root 3) (root 2) (root 2 + root 3)
~~ +2.414 +1.414 -0.414
-0.414 +1.414 +2.414
with similar expressions for 1 -> 2 and 2 -> 3 after transposing. In this case, the rank 1 sequences are, up to proportionality, the following:
(1), (1, 1), (1, 1, 1)
the rank 2 sequences:
(1, -1), (1, 0, -1)
the rank 3 sequence:
(1, -2, 1).
The transforms 4 -> 3, 5 -> 4, 6 -> 5, 7 -> 6, ..., however, are only specified by [A4] and [A5] up to 1, 3, 6, 10, ... undetermined parameters, respectively.
One possible solution is to impose the requrement:
[A6] The rank m sequences are polynomial of degree m.
When combined with orthogonality [A3], this implies a basis decomposition consisting of orthogonal polynomials of ranks 1, 2, 3, ..., M for sequences of length M. For lengths 4, 5 and 6, the bases are, up to scale, the following:
length 4:
Rank 0: +1 +1 +1 +1,
Rank 1: +3 +1 -1 -3,
Rank 2: +1 -1 -1 +1,
Rank 3: +1 -3 +3 -1;
length 5:
Rank 0: +1 +1 +1 +1 +1,
Rank 1: +2 +1 +0 -1 -2,
Rank 2: +2 -1 -2 -1 +2,
Rank 3: +1 -2 0 +2 -1,
Rank 4: +1 -4 +6 -4 +1;
length 6:
Rank 0: +1 +1 +1 +1 +1 +1,
Rank 1: +5 +3 +1 -1 -3 -5,
Rank 2: +5 -1 -4 -4 -1 +5,
Rank 3: +5 -2 -4 +4 +2 -5,
Rank 4: +1 -3 +2 +2 -3 +1,
Rank 5: +1 -5 +10 -10 +5 -1.
This generalizes Legendre Polynomials to a discrete length M version of the polynomial basis.
I believe these sequences all have the property that:
[A7] Interpolation:
The sequences a_{M+1,m} are obtained from a_{M,m}
by linear interpolation upscaling, for each m = 0, ..., M-1.
The matrix for 4 -> 3 is then proportional to:
a b c d
e f f e
d c b a
where
a = 1 + root(1/2) + root(27/10) ~~ 3.350
b = 1 - root(1/2) + root(3/10) ~~ 0.841
c = 1 - root(1/2) - root(3/10) ~~ -0.255
d = 1 + root(1/2) - root(27/10) ~~ 0.064
e = 1 - root(2) ~~ -0.414
f = 1 + root(2) ~~ 2.414
In comparison: a transform 4 -> 3 done by averaging would have:
a = 3, b = 1, c = 0, d = 0, e = 0, f = 2.
Another possibility is a family of solutions that is uniform ([A4]), symmetric ([A5]), but violates the orthogonality requirement ([A3]) and imposes, instead, the requirement
[A8] "Haar Condition": The rank M sequences of length M are alternating:
(+1), (+1, -1), (+1, -1, +1), (+1, -1, +1, -1), etc.
This is analogous to the construction of the Haar functions.
If, instead of using the interpolation condition [A7], one uses the following modified version of it:
[A7'] The sequence A_{M,m} is obtained from
the alternating sequence A_{m,m} by interpolation,
then shortest sequences of lowest ranks length are then the following, up to proportionality:
Rank 1:
1
1 1
1 1 1
1 1 1 1
1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1
...
Rank 2:
1 -1
1 0 -1
1 1 -1 -1
1 1 0 -1 -1
1 1 1 -1 -1 -1
1 1 1 0 -1 -1 -1
...
Rank 3:
1 -1 1
3 -1 -1 3
3 1 -3 1 3
1 1 -1 -1 1 1
3 3 -1 -3 -1 3 3
...
Rank 4:
1 -1 1 -1
2 -1 0 1 -2
1 0 -1 1 0 -1
2 1 -2 0 2 -1 -2
...
Rank 5:
1 -1 1 -1 1
5 -3 1 1 -3 5
5 -1 -4 5 -4 -1 5
...
rank 6:
1 -1 1 -1 1 -1
...
rank 7:
1 -1 1 -1 1 -1 1
...
For odd ranks higher than 1, the non-zero can be adjusted for by rescaling the positive and negative coefficients appropriately, resulting in the following modification:
Rank 3 (adjusted):
1 -2 1
1 -1 -1 1
1 0 -2 0 1
1 1 -2 -2 1 1
1 1 -1 -2 -1 1 1
...
Rank 5 (adjusted):
2 -3 2 -3 2
1 -1 0 0 -1 1
2 -1 -2 2 -2 -1 2
...
Rank 7 (adjusted):
3 -4 3 -4 3 -4 3
...
Since I only starting looking at these solutions a few days ago, then in none of these cases do I actually have formulas for the sequences A_{M,m}, much less actual algorithms for the transforms and their inverses; although the first solution family seems to be something involving the binomial coefficients.