# A General Framework for Semi-Lossless Resampling

Started by August 12, 2013
```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:

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
...
2 -3 2 -3 2
1 -1 0 0 -1 1
2 -1 -2 2 -2 -1 2
...
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.
```
```On Monday, August 12, 2013 3:20:39 PM UTC-5, federat...@netzero.com wrote:
>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,
etc.

Oops. That should be ranks 1, 2, 3, ...
```
```On Monday, August 12, 2013 1:20:39 PM UTC-7, federat...@netzero.com wrote:
> ...
>       * M -> N should result only in a ONE-TIME degradation if M > N,

What does this mean, other than that if you only do M -> N one time it will only produce degradation one time?

> 	* M -> N should be lossless if M < N,
> ...

What is the exact definition of "lossless".

Dale B. Dalrymple
```
```On Monday, August 12, 2013 7:54:22 PM UTC-5, dbd wrote:
> >       * M -> N should result only in a ONE-TIME degradation if M > N,
> What does this mean, other than that if you only do M -> N one time it will only produce degradation one time?
> > 	* M -> N should be lossless if M < N,
> What is the exact definition of "lossless".

What you're replying to was a reference to the details that came later, that you deleted in your question. In other words, you asked a question in direct reply to its own answer (which you deleted, in both cases).
```
```On Monday, August 19, 2013 5:03:58 PM UTC-7, federat...@netzero.com wrote:
> On Monday, August 12, 2013 7:54:22 PM UTC-5, dbd wrote:
>
> > >       * M -> N should result only in a ONE-TIME degradation if M > N,
>
> > What does this mean, other than that if you only do M -> N one time it will only produce degradation one time?
>
> > > 	* M -> N should be lossless if M < N,
>
> > What is the exact definition of "lossless".
>
>
>
> What you're replying to was a reference to the details that came later, that you deleted in your question. In other words, you asked a question in direct reply to its own answer (which you deleted, in both cases).

Bull.

Dale B. Dalrymple
```
```On Monday, August 12, 2013 3:20:39 PM UTC-5:
>... repeated up/down-sampling cycles ... continual degradation ...
> the idea: a general framework for resampling that avoids this problem.

>... M -> N denote[s] the operation (and its matrix) for sampling
> from positive sizes M to N [with similar notation for composition
> e.g. M->N->P.]

This was the general framework laid out:
[A1] M -> N -> P = M -> P, unless N < M and N < P, and
[A2] M -> M = 1_M.

which yields the desire property that M->N->M->N = M->N -- thus the name "Semi-Lossless".

As mentioned, this implies that all sequences of length N decompose into a sum of sequences of ranks 1, 2, ...., N where the rank of a sequence x is the smallest value r such that x(N->r->N) = x.

So the key was to identify what the rank r sequence of length N.

Other potential properties listed were:
[A3] Orthogonality: M -> N = (N -> M) transpose.
[A4a] Row Uniformity: The rows of M -> N all have the same sum,
(i.e. all the 1->N matrices are constant column vectors).

[A4b] Column Uniformity: The columns of M -> N all have the same sum,
(i.e. all the N->1 matrixs are constant row vectors).
which is equivalent to requiring that all the N -> 1 matrices be constant row vectors.

Other conditions were listed as possibilities:
[A5a] Symmetry: Sequence reversal and rescaling commute
[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.
(all equivalent)

[A6] The rank m sequences are polynomial of degree m.

[A7] Interpolation:
The sequences a_{M+1,m} are obtained from a_{M,m}
by linear interpolation upscaling, for each m = 0, ..., M-1.

There are probably an infinite number of solutions to these conditions and therefore an infinite number of possible frameworks.

The solution listed as an example at the end of the article:

>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.

does indeed involve binomial coefficients. The general formula for the sequence A_{nr} of length n and rank r is (A_{nrm}: m = 0, ..., n-1), given by
A_{nrm} = sum_{p,q} (-1)^q C(n, r-q) C(m,p) C(q,p) C(r+p,p)
where
C(n,m) = n/1 (n-1)/2 ... (n-m+1)/m.

Binomial coefficients satisfy an entire Ramanujan-notebook's worth of identities -- making heavy use of generating functions -- so there is ample room to drastically simplify the "naive" algorithm posed int he previous article for a general framework and possibly express it in factored form.

```