RASCUNHO PARA DESENVOLVIMENTO (por favor, não pontuar, pois assim que publicado o conteúdo será removido)

Tendência e criptografia de última geração (State-of-the-Art Cryptography)

O estado da arte em criptografia enfatiza:

• Eficiência: Algoritmos como AES, ChaCha20 e cifras leves para dispositivos IoT.
• Segurança pós-quântica: proteção contra computação quântica com algoritmos como CRYSTALS e NTRUEncrypt.
• Criptografia Homomórfica: Executar cálculos em dados criptografados sem descriptografá-los.
• Provas de conhecimento zero: verificar uma declaração sem revelar os dados reais.
• Criptografia Blockchain: Protegendo livros contábeis descentralizados com funções hash e algoritmos de curva elíptica.

Com curiosidade, é apresentada uma pequena lista expandida contendo as cifras históricas e modernas. Cobre desde as antigas técnicas de cifragem até os mais recentes algoritmos criptográficos já conhecidos. Estão agrupados para maior clareza. Se necessário, é fornecida alguma informação sobre algumas delas.

Compactaçao de imagem RGB para JPEG

JPEG (Joint Photographic Experts Group). O Processo eh realizado em 6 principais etapas:

1. Transformação do espaço de cores RGB para Y'CbCr (Y' = luminance component; Cr, Cb = red and blue crominance components)

2. Transformada discreta do cosseno (DCT) sobre os canais Y', Cb e Cr
   2.1 Imagem é dividida em blocos de 8 x 8 pixels
   2.2 Se a imagem não tem dimensões múltiplas de 8, deve ser preenchida a partir da lateral direita e parte inferior

3. Quantização de acordo com a % referente à qualidade
   3.1 Canal Y' utiliza matriz de quantização Q_Y
   3.2 Canais Cb e Cr utilizam matriz de quantização Q_C

4. Hufmann encoding para as quantidades AC. Quantidades DC utilizam compressão diferencial

5. Compressão

6. Escrita do arquivo JPEG

1) Transformação do espaço de cores

YCbCr definida pela CCIR 601-1 com Cb e Cr normalizados para o intervalo 0..CENTER em vez de -0.5 a 0.5. CENTER = 256 / 2 = 128.

O valores da transformação RGB para Y'CbCr foram calculados a partir da matriz inversa de Y'CbCr para RGB.

CJ =  128
Y  =  0,29900 * R + 0,58700 * G + 0,11400 * B
Cb = -0,16874 * R - 0,33126 * G + 0,50000 * B  + CENTERJSAMPLE
Cr =  0,50000 * R - 0,41869 * G - 0,08131 * B  + CENTERJSAMPLE

ou

| Y  |   |  0,299000   0,586998   0,114000 |   | R |           | 0,0 |
| Cb | = | -0,168736  -0,331263   0,500000 | x | G | + 128,0 * | 1,0 |
| Cr |   |  0,500000  -0,418686  -0,081313 |   | B |           | 1,0 |

Transformação inversa

| R |   |  1,00000  -0,000000   1,402000 |   | Y  |           | 1,0 |
| G | = |  1,00000  -0,344140  -0,714140 | x | Cb | - 128,0 * | 1,0 |
| B |   |  1,00000   1,772000   0,000000 |   | Cr |           | 1,0 |

_{Fonte: jccolor.c}

2) Transformada discreta do cosseno (Discrete Cosine Transformation - DCT)

Como o próprio nome sugere, é uma transformação aplicada para valores discretos. Considerando os blocos com tamanho 8 x 8 pixel, são calculados 8 x 8 coeficientes da DCT.

Transformada direta

S[v][u] = (1/4) * C[u] * C[v] * Sum[x=0..7] Sum[y=0..7] s[y][x] \
                    * cos((2*x+1)*u*pi/16) * cos((2*y+1)*v*pi/16) 

int N = 8
// Função para calcular os coeficientes da DCT para um bloco 8x8
// Esta função apenas calcula os coeficientes não o bloco transformado
// Código não otimizado
void dct_basis(double dct_block[N][N], int u, int v) {
    // Optimization: it is a constant (u * PI) / (2 * N)
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            double coeff_x = cos(((2.0 * x + 1.0) * u * PI) / (2.0 * N));
            double coeff_y = cos(((2.0 * y + 1.0) * v * PI) / (2.0 * N));
            dct_block[x][y] = coeff_x * coeff_y;
        }
    }
}

Transformada inversa

S[y][x] = (1/4) * Sum[u=0..7] Sum[v=0..7]  C[u] * C[v] * s[v][u] \
                     * cos((2*x+1)*u*pi/16) * cos((2*y+1)*v*pi/16) 

com:

C(u), C(v) = 1.0 / sqrt(2.0) para u, v = 0
C(u), C(v) = 1.0 para outros casos

As matrizes de transformação são ortogonais, logo, a transformada inversa se dá pela simples transposta da matriz de transformação. Expressando as equações na forma matricial:

Q = T x Y x T'
onde:
S = matriz com valores de amostra (Sample values of Y' or Cb or Cr)
T = matriz de transformação da DCT
Q = matriz de valores 

3) Matrizes de quantização

Os coeficientes de quantização para as componentes de luminância e crominância são apresentados em duas matrizes na referência indicada. Foram obtidos a partir de experimentos com limiares psicovisuais, derivados empiricamente usando luminância e crominância com subamostragem horizontal 2:1. Fornecem uma quantização com fator de qualidade de 50% (numa escala de 0 a 100%).

Os valores fornecidos na documentação são exemplos e não são necessariamente adequados para qualquer aplicação específica. Estes valores de quantização foram obtidos a partir da avaliação de resultados razoáveis em imagens de luminância e crominância de 8 bits por amostra. As características destas imagens podem ser conferidas na Figura 13 da referência.

Estes valores de quantização são apropriados para a normalização dos valores resultantes da DCT. Dividindo-os por 2, a imagem reconstruída resultante apresenta diferenças praticamente indistinguíveis da imagem original. Os valores resultantes devem ser arredondados para o inteiro mais próximo.

Matriz com coeficientes de quantização para frequências de luminância

16 11 10 16 124 140 151 161
12 12 14 19 126 158 160 155
14 13 16 24 140 157 169 156
14 17 22 29 151 187 180 162
18 22 37 56 168 109 103 177
24 35 55 64 181 104 113 192
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 199

Matriz com coeficientes de quantização para frequências de crominância

17 18 24 47 99 99 99 99
18 21 26 66 99 99 99 99
24 26 56 99 99 99 99 99
47 66 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99

_{Fonte: itu-t81, pg. 143}

Diferentes valores para o fator de qualidade modulam quão agressiva ou permissiva são essas matrizes:

JPEG permite ajustar o fator de qualidade (QF) entre 1 e 100:

• QF = 100: Baixa compressão, alta qualidade.
• QF = 50: Compressão nominal padrão.
• QF < 50: Alta compressão, baixa qualidade.

Cada matriz de quantização é escalada conforme o algoritmo seguinte:

Q(u, v) = floor(Q_Y(u, v) * S / 100 + 0,5)

onde:
S = 5000 / QF      para (QF < 50)
S = 200 - 2 * QF   para (QF > 50)

3) Teoria

4) Exemplo numérico

As amostras 8 x 8 abaixo são dadas em formato PGM (Portable Gray Map) em modo texto. A porção da imagem é tomada de um artigo publicado em https://cgjennings.ca/articles/jpeg-compression (coordenadas rows = 88...95; cols = 48...55)

# Canal Red

P2
8 8
255
232 229 228 255 146  12  71  24 
228 239 235 254 191  17  40  47 
240 229 230 255 168  24  80  60 
242 244 235 255 145  17  21  48 
235 242 243 255 108   5   5 119 
238 238 240 255  83   0  51 130 
249 247 255 250  79  27  83 122 
249 255 225 131  82 103 128  91 


# Canal Green

P2
8 8
255
241 242 240 255 165  19  67  37 
243 242 238 255 218  32  41  50 
241 242 244 255 194  23  69  81 
244 243 245 255 170  82  83  26 
248 249 251 255 141  29  28 112 
248 244 247 255 130   0  51 130 
253 249 255 255 115  30  85 126 
252 255 226 146 103 114 137 109 


# Canal Blue

P2
8 8
255
254 251 248 255 162  20  64  39 
255 255 250 255 207  16  54  49 
253 253 253 255 186  18  90  79 
252 252 252 255 171  64  66  45 
255 255 255 255 131  20  19 121 
253 255 254 255 120   0  57 131 
255 252 255 255 104  21  71 103 
255 255 242 140  38  64  87  46 

Conversão dos canais RGB para YCbCr

# Canal Y (luminancia)

P2
8 8
255
240 239 237 255 159  17  68  33 
240 243 238 255 209  26  42  49 
242 239 241 255 185  23  75  74 
244 244 243 255 163  61  63  35 
245 248 249 255 130  21  20 115 
246 243 246 255 115   0  52 130 
252 249 255 254 103  28  83 122 
251 255 228 141  89 105 129  96 


# Canal Cb (Crominância azul)

P2
8 8
255
136 135 134 128 130 130 126 131 
137 135 135 128 127 123 135 128 
134 136 135 128 128 125 137 131 
132 132 133 128 133 130 130 134 
134 132 131 128 129 128 127 131 
132 135 133 128 131 128 131 129 
130 130 128 129 129 124 121 117 
130 128 136 128  99 105 105 100 


# Canal Cr (Crominância vermelho)

P2
8 8
255
122 121 121 128 119 124 130 121 
120 125 126 127 115 122 126 127 
127 121 120 128 116 129 132 118 
126 128 122 128 115  97  98 137 
121 124 124 128 112 117 117 131 
123 124 124 128 105 128 128 128 
126 127 128 125 111 127 128 128 
126 128 126 121 123 127 128 124 

Aplicando a transformada do cosseno para o canal Y obtém-se a matriz T

H = [
   0.353553   0.353553   0.353553   0.353553   0.353553   0.353553   0.353553   0.353553
   0.490393   0.415735   0.277785   0.097545  -0.097545  -0.277785  -0.415735  -0.490393
   0.461940   0.191342  -0.191342  -0.461940  -0.461940  -0.191342   0.191342   0.461940
   0.415735  -0.097545  -0.490393  -0.277785   0.277785   0.490393   0.097545  -0.415735
   0.353553  -0.353553  -0.353553   0.353553   0.353553  -0.353553  -0.353553   0.353553
   0.277785  -0.490393   0.097545   0.415735  -0.415735  -0.097545   0.490393  -0.277785
   0.191342  -0.461940   0.461940  -0.191342  -0.191342   0.461940  -0.461940   0.191342
   0.097545  -0.277785   0.415735  -0.490393   0.490393  -0.415735   0.277785  -0.097545
]

T = H' x Y x H = [
  1332    241    -29   -134    234     87     20     70 
  -344    -76    -93    107    -55    -12    -65     11 
   270     41     66    -41     23     25      3     20 
  -105     27    -62    -27     40    -12      4    -17 
   137     20     39     28    -35     10     14      4 
     1      7    -39     -5     -5     38    -10     -6 
    71      6     32     -1    -10     19     -9     11 
    37     15      6    -34     21      9      3     -1 
]

#include<stdio.h>
#include<math.h>

double H(double n, double u, double x) {
  return sqrt(((u==0.0)?1.0:2.0)/n)*cos( (2.0*x+1.0)*u*M_PI/(2.0*n) );
}

int main(int argc, char *argv[], char *env[]) {
  double n = 8.0;
  for(double u = 0; u<n; u++) {
    for(double x = 0; x<n; x++) printf("%11.6f", H(n, u, x));
    printf("\n");
  }
  return 0;
}

Matriz de quantização para a luminância (Y), fator de qualidade 50 (de 0 a 100):

Qy_50 = [
    16    12    14    14    18    24    49    72
    11    12    13    17    22    35    64    92
    10    14    16    22    37    55    78    95
    16    19    24    29    56    64    87    98
    24    26    40    51    68    81   103   112
    40    58    57    87   109   104   121   100
    51    60    69    80   103   113   120   103
    61    55    56    62    77    92   101    99
]

A matriz resultante é a divisão de cada elemento da matriz T pelo elemento correspondente na matriz de quantização Qy_50

T_Qy50 = [
    83     20     -2    -10     13      4      0      1 
   -31     -6     -7      6     -2      0     -1      0 
    27      3      4     -2      1      0      0      0 
    -7      1     -3     -1      1      0      0      0 
     6      1      1      1     -1      0      0      0 
     0      0     -1      0      0      0      0      0 
     1      0      0      0      0      0      0      0 
     1      0      0     -1      0      0      0      0 
]

Aplica-se o algoritmo de captura em zig-zag

   20,-31,27,-6,-2,-10,-7,3,-7,6,1,4,6,13,4,-2,-2,-3,1,0,...,0

Prossegue com o algoritmo de Huffman para posteriormente compactar os coeficientes AC. O primeiro coeficiente em (1,1) = 83 refere-se à componente DC (contínua) e é excluído desta compactação sendo combinado com os demais de outras matrizes e codificado diferencialmente.

5) Source code

6) References

ToDo:

• Equações de transformação de espaços de cores
• Matrizes de quantização para luminância Y' e crominâncias Cb e Cr
• Como alterar o fator de qualidade
• Teoria
• Exemplo numérico
• Transcrever source code to javascript
• Incluir references
• Corrigir a ortografia e pontuação
• Particularidades (precisão, inteiros, algoritmos etc.)