Transformação de quantização média sucessiva otimizada

O algoritmo SMQT (Sucessive Mean Quantization Transform) é uma transformação não linear que revela a organização ou estrutura dos dados e remove propriedades como ganho e viés. Em um artigo intitulado The Successive Mean Quantization Transform, o SMQT é “aplicado no processamento de fala e processamento de imagem”. O algoritmo quando aplicado a imagens “pode ser visto como um foco progressivo nos detalhes de uma imagem”.

De acordo com outro artigo intitulado Operadores de mapeamento de tons baseados em SMQT para imagens de alta faixa dinâmica, ele produzirá uma “imagem com detalhes aprimorados”. O artigo descreve duas técnicas de aplicação dessa transformação a uma imagem.

1. Aplique SMQT na luminância de cada pixel - descreve a fórmula para obter a luminância do RGB de cada pixel.

2. Aplique SMQT em cada canal de RGB separadamente - para os canais R, G e B individualmente.

A imagem a seguir mostra o resultado das duas técnicas:

Ao aplicar a segunda técnica a uma imagem do Bruin Theatre à noite, podemos ver como o algoritmo amplia progressivamente os detalhes da imagem e revela detalhes que originalmente estavam ocultos pela escuridão:

Neste artigo, examinaremos mais de perto como esse algoritmo funciona e exploraremos uma otimização simples que permite que o algoritmo tenha muito mais desempenho em aplicações práticas de processamento de imagens.

O algoritmo SMQT

No artigo original, o algoritmo é descrito de forma abstrata. Para entender melhor o SMQT, veremos alguns exemplos simples.

Suponha que temos o seguinte vetor (você pode pensar nele como um array):

No caso de uma imagem colorida, podemos pensar nela como três vetores separados, cada um representando um canal de cor específico (RGB), e cada elemento do vetor representando a intensidade do pixel correspondente.

As etapas envolvidas na aplicação do algoritmo SMQT são:

1. Calcule a média do vetor, que neste caso é 29,58.

2. Divida o vetor em dois, deixando os números menores ou iguais a 29,58 na metade esquerda e os números maiores na metade direita:

   15	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   A segunda linha é o código que criaremos para cada valor. Os valores menores ou iguais a 29,58 recebem um 0 em seu código, e os números maiores que 29,58 recebem um 1 (isto é binário).

3. Agora ambos os vetores resultantes são divididos individualmente, de forma recursiva, seguindo a mesma regra. Em nosso exemplo, a média do primeiro vetor é (15 + 4 + 0 + 5 + 18) / 5 = 8,4, e a média do segundo vetor é (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48,7. Cada um desses dois vetores é dividido em mais dois vetores, e um segundo bit de código é adicionado a cada um dependendo de sua comparação com a média. Este é o resultado:

   4	0	5	15	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	11	11	11	11

   Observe que um 0 foi acrescentado novamente para números menores ou iguais à média (para cada vetor) e um 1 para números maiores que a média.

4. Este algoritmo é repetido recursivamente:

   0	4	5	15	18	32	31	47	48	60	64	59
   000	001	001	010	011	100	100	101	110	111	111	111

   0	4	5	15	18	31	32	47	48	60	59	64
   0000	0010	0011	0100	0110	1000	1001	1010	1100	1110	1110	1111

   0	4	5	15	18	31	32	47	48	59	60	64
   00000	00100	00110	01000	01100	10.000	10010	10100	11.000	11100	11101	11110

   Neste ponto, cada vetor tem apenas um elemento. Assim, para cada passo sucessivo, um 0 será acrescentado, pois o número será sempre igual a si mesmo (a condição para um 0 é que o número seja menor ou igual à média, que é ele mesmo).

Até agora temos um nível de quantização de L=5. Se formos usar L=8, devemos acrescentar três 0s a cada código. O resultado da conversão de cada código de binário para inteiro (para L=8) seria:

O vetor final é classificado em ordem crescente. Para obter o vetor de saída, devemos substituir o valor original do vetor de entrada pelo seu código.

Observe que no vetor resultante:

• O ganho foi removido. O original tinha um ganho baixo, com sua faixa de 0 a 64. Agora seu ganho vai de 0 a 240, que é quase toda a faixa de 8 bits. Diz-se que o ganho é removido porque não importa se multiplicarmos todos os elementos do vetor original por um número, como 2, ou se dividirmos todos por 2, o vetor de saída será aproximadamente o mesmo. Seu alcance seria aproximadamente todo o alcance do vetor de destino (8 bits para L=8). Se multiplicarmos o vetor de entrada por dois, o vetor de saída será realmente o mesmo, porque em cada etapa os mesmos números que estavam abaixo ou acima da média continuarão abaixo ou acima dela, e adicionaremos os mesmos 0s ou 1s à saída. Somente se dividirmos, o resultado será aproximadamente o mesmo, e não exatamente o mesmo, porque números ímpares como 15 terão que ser arredondados e os cálculos podem variar. Passamos de uma imagem escura para uma imagem com seus pixels variando de cores escuras (0) a cores mais claras (240), usando todo o intervalo.
• O viés é removido, embora não possamos observá-lo neste exemplo. Isso ocorre porque não temos um viés, pois nosso valor mais baixo é 0. Se realmente tivéssemos um viés, ele teria sido removido. Se pegarmos qualquer número 'K' e o somarmos a cada elemento do vetor de entrada, o cálculo dos números acima e abaixo da média em cada passo não irá variar. A saída ainda será a mesma. Isso também tornaria as imagens muito claras para se tornarem imagens que variam de cores escuras a claras.
• Temos uma imagem com detalhes aprimorados. Observe como, para cada etapa recursiva que damos, estamos realmente ampliando os detalhes e construindo a saída revelando esses detalhes o máximo possível. E como aplicaremos essa técnica a cada canal RGB, revelaremos o máximo de detalhes possível, embora perdendo informações sobre os tons originais de cada cor.

Dada uma imagem como um vetor de pixels RGB, com cada ponto sendo 8 bits para R, 8 para G e 8 para B; podemos extrair dele três vetores, um para cada cor, e aplicar o algoritmo a cada vetor. Então formamos o vetor RGB novamente a partir desses três vetores de saída e temos a imagem processada SMQT, como feito com a do Bruin Theatre.

Complexidade

O algoritmo requer que para cada nível de quantização (L), N elementos sejam inspecionados em uma primeira passagem para encontrar a média para cada vetor e, em uma segunda passagem, cada um desses N elementos deve ser comparado com a média correspondente em para dividir cada vetor por sua vez. Finalmente, N elementos devem ser substituídos por seus códigos. Portanto, a complexidade do algoritmo é O((L*2*N) + N) = O((2*L + 1)*N), que é O(L*N).

O gráfico extraído do artigo é consistente com a complexidade O(L*N). Quanto menor o L, mais rápido o processamento de forma aproximadamente linear (maior número de quadros por segundo). Para melhorar a velocidade de processamento, o artigo sugere diminuir os valores de L: “selecionar um nível L mais baixo pode ser uma maneira direta de reduzir a velocidade de processamento, mas com qualidade de imagem reduzida”.

Melhoria

Aqui encontraremos uma maneira de melhorar a velocidade sem reduzir a qualidade da imagem. vamos analisar o processo de transformação e encontrar um algoritmo mais rápido. Para ter uma perspectiva mais completa sobre isso, vejamos um exemplo com números repetidos:

Os vetores não podem mais ser divididos e os zeros devem ser acrescentados até chegarmos ao L desejado.

Para simplificar, vamos supor que a entrada pode ir de 0 a 31, e a saída de 0 a 7 (L=3), como pode ser visto no exemplo.

Observe que calcular a média do primeiro vetor (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 dá o mesmo resultado que calcular a média de todo o último vetor, já que é apenas o mesmo vetor com os elementos em uma ordem diferente: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

Na segunda etapa, devemos calcular cada vetor recursivamente. Então calculamos a média das entradas em cinza, que são os primeiros 6 elementos ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8), e a média da entrada em branco, que são os últimos 4 elementos ((25 + 31 + 31 + 25) / 4 = 28):

Observe novamente que se usarmos o último vetor, aquele que está completamente ordenado, os resultados são os mesmos. Para os 6 primeiros elementos temos: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8), e para os 4 últimos elementos: ((25 + 25 + 31 + 31) / 4 = 28) . Como é apenas uma adição, a ordem das somas não importa.

O mesmo se aplica para a próxima etapa:

Os cálculos são os mesmos do último vetor: ((7 + 1 + 1 + 7) / 4 = 4) será igual a ((1 + 1 + 7 + 7) / 4 = 4).

E o mesmo se aplicará ao restante dos vetores e etapas.

O cálculo da média é apenas a soma dos valores dos elementos do intervalo, dividida pelo número de elementos do intervalo. Isso significa que podemos pré-computar todos esses valores e evitar repetir esse cálculo L vezes.

Vamos ver as etapas para aplicar o que chamaremos de algoritmo FastSMQT ao nosso exemplo:

1. Crie uma tabela com 32 colunas e 3 linhas como você pode ver abaixo. A primeira linha da tabela representa o índice da tabela (0 a 31) e não é necessário ser incluída na codificação da tabela. Mas é mostrado explicitamente para tornar o exemplo mais fácil de seguir.

2. Itere os N elementos uma vez contando a frequência de cada valor. No nosso exemplo, os elementos 1, 7, 16, 25 e 31 têm uma frequência de 2. Todos os outros elementos têm uma frequência de 0. Esta etapa tem uma complexidade de O(N).

3. Agora que o vetor de frequência está preenchido, precisamos iterar esse vetor (o vetor de frequências, não o vetor de entrada). Não iteramos mais N elementos, mas R (R estando no intervalo: 2^L), que neste caso é 32 (0 a 31). Ao processar pixels, N pode ser muitos milhões (megapixels), mas R geralmente é 256 (um vetor para cada cor). No nosso exemplo é 32. vamos preencher as duas linhas a seguir da tabela ao mesmo tempo. A primeira dessas linhas (a segunda da tabela) terá a soma das frequências até o momento. O segundo (o terceiro da tabela) terá a soma do valor de todos os elementos que apareceram até agora.

   Em nosso exemplo, quando chegamos a 1, colocamos um 2 na segunda linha da tabela porque dois 1s apareceram até agora. E também colocamos um 2 na terceira linha da tabela, porque 1 + 1 = 2. Continuamos escrevendo esses dois valores em cada uma das próximas posições até chegarmos a 7. Como o número 7 aparece duas vezes, adicionamos 2 ao acumulador da segunda linha, porque agora 4 números apareceram até agora (1, 1, 7, 7). E adicionamos 7 + 7 = 14 à terceira linha, resultando em 2 + 14 = 16, porque 1 + 1 + 7 + 7 = 16. Continuamos com esse algoritmo até terminarmos de iterar esses elementos. A complexidade desta etapa é O(2^L), que no nosso caso é O(32), e ao trabalhar com pixels RGB é O(256).

   eu	0	1	2	...	6	7	8	...	15	16	17	...	24	25	26	...	30	31
   n	0	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
   n-cumulativo	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   soma	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

4. O próximo passo é remover da tabela as colunas com elementos que possuem frequência 0, e para ver o exemplo mais claro também removeremos a segunda linha já que não é mais relevante, como você verá.

   eu	1	7	16	25	31
   n	2	4	6	8	10
   soma	2	16	48	98	160

5. Lembre-se de que poderíamos usar o último vetor (completamente ordenado) para fazer os cálculos para cada etapa e os resultados ainda serão os mesmos. Observe que aqui, nesta tabela, temos o último vetor com todos os pré-cálculos já realizados.

   Basicamente, precisamos fazer o algoritmo SMQT neste pequeno vetor, mas ao contrário de fazê-lo no vetor original com o qual começamos, este será muito mais fácil.

   Primeiro, precisamos calcular a média de todas as amostras. Podemos encontrá-lo facilmente por: soma[31] / n[31] = 160 / 10 = 16. Então, dividimos a tabela em dois vetores e começamos a escrever o código binário para cada um:

   eu	1	7	16	25	31
   n	2	4	6	8	10
   soma	2	16	48	98	160
   código	0	0	0	1	1

   Agora dividimos cada vetor novamente. A média do primeiro vetor é: soma[16] / n[16] = 48 / 6 = 8. E a média do segundo vetor é: (soma[31] – soma[16]) / (n[31] – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   eu	1	7	16	25	31
   n	2	4	6	8	10
   soma	2	16	48	98	160
   código	00	00	01	10	11

   Há apenas um vetor para dividir. A média é: soma[7] / n[7] = 16 / 4 = 4.

   eu	1	7	16	25	31
   n	2	4	6	8	10
   soma	2	16	48	98	160
   código	000	001	010	100	110

   Como você pode ver, o código para cada elemento é o mesmo se tivéssemos seguido o algoritmo original. E fizemos o SMQT em um vetor muito menor do que aquele com N elementos e também pré-calculamos todos os valores que precisamos para encontrar a média, então é simples e rápido calcular o vetor resultante.

   A complexidade desta etapa é O(L*(2^L)), que para um L=8, e em necessidades práticas de processamento de imagem, é O(8*(256)) = O(2048) = constante.

6. A etapa final é iterar N elementos mais uma vez substituindo o elemento por seu código para cada elemento: element[i] = code[i]. A complexidade é O(N). A complexidade do FastSMQT é O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)) .

Paralelismo

Ambos os algoritmos podem ser paralelizados, embora seja mais eficiente executar um algoritmo por núcleo se vários vetores precisarem ser transformados. Por exemplo, ao processar imagens, podemos processar cada canal RGB em um núcleo diferente, em vez de paralelizar cada um desses três cálculos.

Para paralelizar o algoritmo SMQT, quando dividimos um vetor em dois, podemos processar cada subvetor em um novo núcleo se um núcleo estiver disponível (na verdade, um subvetor no núcleo atual e outro em um novo núcleo). Isso pode ser feito recursivamente até atingirmos o número total de núcleos disponíveis. As substituições de valores por códigos também podem ser feitas em paralelo para.

O algoritmo FastSMQT também pode ser paralelizado. Na primeira etapa, o vetor de entrada deve ser dividido pelo número de núcleos disponíveis (C). Um vetor de contagem de frequência deve ser criado para cada uma dessas partes e preenchido em paralelo. Em seguida, adicionamos os valores desses vetores em um vetor de frequências resultante. O próximo passo que pode ser paralelizado é o último, quando estamos substituindo os valores pelos seus códigos. Isso pode ser feito em paralelo para.

Comparação de complexidade

A complexidade total do algoritmo SMQT original é O((2*L + 1)*N), que é O(L*N).

A complexidade do FastSMQT é O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)).

Dado um L fixo, a complexidade se torna apenas O(N) para ambos. Mas as constantes que multiplicam N são muito menores para FastSMQT, e isso faz uma grande diferença no tempo de processamento como veremos.

O gráfico a seguir compara o desempenho dos algoritmos SMQT e FastSMQT para L=8, que é o caso do processamento de imagens. O gráfico mostra o tempo (em milissegundos) que leva para processar N elementos. Observe que a complexidade (com constantes) de SMQT para L=8 é O(17*N), enquanto para FastSMQT é O(2*N + 2304).

Quanto maior o N, mais tempo leva para o SMQT processar a imagem. Para FastSMQT, por outro lado, o crescimento é muito mais lento.

Para valores ainda maiores de N, a diferença de desempenho é muito mais aparente:

Aqui, o SMQT leva vários segundos para processar determinadas imagens, enquanto o FastSMQT ainda está dentro da zona de “poucos milissegundos”.

Mesmo com vários núcleos (dois, neste caso), FastSMQT ainda é claramente superior a apenas SMQT:

FastSMQT não depende de L. SMQT, por outro lado, é linearmente dependente do valor de L. Por exemplo, com N = 67108864, o tempo de execução de SMQT aumenta com o aumento do valor de L, enquanto FastSMQT não:

Conclusão

Nem todas as técnicas de otimização são aplicáveis ​​a todos os algoritmos, e a chave para melhorar o desempenho de um algoritmo geralmente está escondida em alguma percepção de como o algoritmo funciona. Este algoritmo FastSMQT aproveita as possibilidades de pré-cálculo de valores e a natureza dos cálculos de média. Como resultado, permite um processamento mais rápido do que o SMQT original. A velocidade não é afetada pelo incremento de L, embora L não possa ser muito maior que o 8 usual porque o uso de memória é 2^L, que para 8 é um aceitável 256 (número de colunas em nossa tabela de frequência), mas o ganho de desempenho tem benefícios práticos óbvios.

Essa melhoria na velocidade permitiu ao MiddleMatter implementar o algoritmo em um aplicativo iOS (e um aplicativo Android) que melhora fotos e vídeos capturados em condições de pouca luz. Com essa melhoria, foi possível realizar o processamento de vídeo no aplicativo, que de outra forma seria muito lento para dispositivos iOS.

O código C++ para algoritmos SMQT e FastSMQT está disponível no GitHub.