Há alguns anos, escrevi uma implementação muito simples de compressão de imagem fractal para o trabalho dos alunos e publiquei o código no github .

Para minha surpresa, o repositório acabou sendo bastante popular, então decidi atualizar o código e escrever um artigo explicando ele e a teoria.

Teoria

Esta parte é bastante teórica e, se você estiver interessado apenas na documentação do código, poderá ignorá-la.

Mapeamentos de compactação

Vamos $$$(E, d)$ É o espaço métrico completo e $$$f: E \ rightarrow E$ - mapeamento de $$$E$ em $$$E$ .

Dizemos que $$$f$ é um mapeamento compressivo, se existir $$$0 <s <1$ tal que:

$$

$$\ forall x, y \ in E, d (f (x), f (y)) \ leq sd (x, y)$$

Com base nisso, $$$f$ denotará um mapeamento de compactação com uma taxa de compactação $$$s$ .

Existem dois teoremas importantes nos mapeamentos de contratação: o teorema de ponto fixo de Banach e o teorema da colagem .

Teorema do ponto fixo : $$$f$ tem um ponto fixo exclusivo $$$x_0$ .


Além disso, indicaremos como $$$x_0$ ponto fixo $$$f$ .

Teorema da colagem : se $$$d (x, f (x)) <\ epsilon$ então $$$d (x, x_0) <\ frac {\ epsilon} {1 - s}$ .


O segundo teorema nos diz que se encontrarmos um mapa de contração $$$f$ tal que $$$f (x)$ perto de $$$x$ , podemos ter certeza de que o ponto fixo $$$f$ também perto de $$$x$ .

Este resultado será a base do nosso trabalho futuro. E, de fato, em vez de salvar a imagem, basta salvar a exibição compressiva, cujo ponto fixo está próximo da imagem.

Telas de compressão para imagens

Nesta parte, mostrarei como criar essas telas compressivas para que o ponto fixo fique próximo da imagem.

Primeiro, vamos definir o conjunto de imagens e a distância. Vamos escolher $$$E = [0, 1] ^ {h \ vezes w}$ . $$$E$ Há muitas matrizes com $$$h$ em linhas $$$w$ colunas e com coeficientes no intervalo $$$[0, 1]$ . Então vamos levar $$$d (x, y) = \ left (\ sum_ {i = 1} ^ {h} {\ sum_ {j = 1} ^ {w} {(x_ {ij} -y_ {ij}) ^ 2}} \ right) ^ {0,5}$ . $$$d$ É a distância obtida a partir da norma Frobenius .

Vamos $$$x \ em E$ É a imagem que queremos compactar.

Vamos dividir a imagem em blocos duas vezes:

• Primeiro, dividimos a imagem em blocos finitos ou com intervalos $$$R_1, ..., R_L$ . Esses blocos são separados e cobrem a imagem inteira.
• Em seguida, dividimos a imagem em blocos de fontes ou domínios $$$D_1, ..., D_K$ . Esses blocos não são necessariamente separados e não cobrem necessariamente a imagem inteira.

Por exemplo, podemos segmentar a imagem da seguinte maneira:


Então, para cada bloco de intervalo $$$R_l$ nós selecionamos um bloco de domínio $$$D_ {k_l}$ e mapeamento $$$f_l: [0, 1] ^ {D_ {k_l}} \ rightarrow [0, 1] ^ {R_ {l}}$ .

Em seguida, podemos definir uma função $$$f$ como:

$$

$$f (x) _ {ij} = f_l (x_ {D_ {k_l}}) _ {ij} \ text {if} (i, j) \ em R_l$$

Aprovação : se $$$f_l$ estão contratando mapeamentos, então e $$$f$ mapeamento também compressivo.


Resta uma pergunta que precisa ser respondida: como escolher $$$D_ {k_l}$ e $$$f_l$ ?

O teorema da colagem oferece uma maneira de escolhê-los: se $$$x_ {R_l}$ está perto de $$$f (x_ {D_ {k_l}})$ para todos $$$l$ então $$$x$ está perto de $$$f (x)$ e pelo teorema da colagem $$$x$ e $$$x_0$ também estão próximos.

Portanto, somos independentes para todos $$$l$ podemos construir um conjunto de mapeamentos de compressão de cada $$$D_ {k}$ em $$$R_l$ e escolha o melhor. Na próxima seção, mostramos todos os detalhes desta operação.

Implementação

Em cada seção, copiarei fragmentos de código interessantes, e o script inteiro pode ser encontrado aqui .

Partições

Eu escolhi uma abordagem muito simples. Os blocos de origem e os blocos de folhas segmentam a imagem em uma grade, conforme mostrado na imagem acima.

O tamanho dos blocos é igual à potência de dois e isso simplifica bastante o trabalho. Os blocos de origem são 8 por 8 e os blocos finais são 4 por 4.

Existem esquemas de particionamento mais complexos. Por exemplo, podemos usar a árvore quadtree para dividir as áreas com muitos detalhes com mais força.

Conversões

Nesta seção, mostrarei como criar mapeamentos de compactação a partir de $$$D_ {k}$ em $$$R_l$ .

Lembre-se de que queremos gerar esse mapeamento $$$f_l$ para $$$f (x_ {D_k})$ estava perto de $$$x_ {R_l}$ . Ou seja, quanto mais mapeamentos gerarmos, maior a probabilidade de encontrar um bom.

No entanto, a qualidade da compactação depende do número de bits necessário para armazenar $$$f_l$ . Ou seja, se muitas funções forem muito grandes, a compactação será ruim. É necessário um compromisso aqui.

Eu decidi que $$$f_l$ ficará assim:

$$

$$f_l (x_ {D_k}) = s \ vezes gira _ {\ theta} (flip_d (reduz (x_ {D_k}))) + b$$

onde $$$reduzir$ - esta é uma função para passar dos blocos 8 a 8 para os blocos 4 a 4, $$$flip$ e $$$rodar$ - transformações afins, $$$s$ altera o contraste e $$$b$ - brilho.

A função reduce reduz o tamanho da imagem calculando a média dos arredores:

 def reduce(img, factor): result = np.zeros((img.shape[0] // factor, img.shape[1] // factor)) for i in range(result.shape[0]): for j in range(result.shape[1]): result[i,j] = np.mean(img[i*factor:(i+1)*factor,j*factor:(j+1)*factor]) return result 

A função de rotate gira a imagem em um determinado ângulo:

 def rotate(img, angle): return ndimage.rotate(img, angle, reshape=False) 

Para manter a forma do ângulo da imagem $$$\ theta$ só pode levar valores $$$\ {0 ^ {\ circ}, 90 ^ {\ circ}, 180 ^ {\ circ}, 270 ^ {\ circ} \}$ .

A função flip espelha a imagem se a direction for -1 e não reflete se o valor for 1:

 def flip(img, direction): return img[::direction,:] 

A conversão completa é realizada pela função apply_transformation :

 def apply_transformation(img, direction, angle, contrast=1.0, brightness=0.0): return contrast*rotate(flip(img, direction), angle) + brightness 

Precisamos de 1 bit para lembrar se o espelhamento é necessário e 2 bits para o ângulo de rotação. Além disso, se salvarmos $$$s$ e $$$b$ Usando 8 bits para cada valor, precisaremos de apenas 11 bits para salvar a conversão.

Além disso, devemos verificar se essas funções são mapeamentos de contração. A prova disso é um pouco chata, e não é realmente o que precisamos. Talvez mais tarde eu o adicione como um apêndice ao artigo.

Compressão

O algoritmo de compactação é simples. Primeiro, geramos todas as transformações afins possíveis de todos os blocos de origem usando a função generate_all_transformed_blocks :

 def generate_all_transformed_blocks(img, source_size, destination_size, step): factor = source_size // destination_size transformed_blocks = [] for k in range((img.shape[0] - source_size) // step + 1): for l in range((img.shape[1] - source_size) // step + 1): # Extract the source block and reduce it to the shape of a destination block S = reduce(img[k*step:k*step+source_size,l*step:l*step+source_size], factor) # Generate all possible transformed blocks for direction, angle in candidates: transformed_blocks.append((k, l, direction, angle, apply_transform(S, direction, angle))) return transformed_blocks 

Em seguida, para cada bloco final, verificamos todos os blocos de origem transformados gerados anteriormente. Para cada um, otimizamos o contraste e o brilho usando o método find_contrast_and_brightness2 e, se a conversão testada for a melhor de todas as encontradas até agora, salve-a:

 def compress(img, source_size, destination_size, step): transformations = [] transformed_blocks = generate_all_transformed_blocks(img, source_size, destination_size, step) for i in range(img.shape[0] // destination_size): transformations.append([]) for j in range(img.shape[1] // destination_size): print(i, j) transformations[i].append(None) min_d = float('inf') # Extract the destination block D = img[i*destination_size:(i+1)*destination_size,j*destination_size:(j+1)*destination_size] # Test all possible transformations and take the best one for k, l, direction, angle, S in transformed_blocks: contrast, brightness = find_contrast_and_brightness2(D, S) S = contrast*S + brightness d = np.sum(np.square(D - S)) if d < min_d: min_d = d transformations[i][j] = (k, l, direction, angle, contrast, brightness) return transformations 

Para encontrar o melhor contraste e brilho, o método find_contrast_and_brightness2 simplesmente resolve o problema dos mínimos quadrados:

 def find_contrast_and_brightness2(D, S): # Fit the contrast and the brightness A = np.concatenate((np.ones((S.size, 1)), np.reshape(S, (S.size, 1))), axis=1) b = np.reshape(D, (D.size,)) x, _, _, _ = np.linalg.lstsq(A, b) return x[1], x[0] 

Desembalar

O algoritmo de descompressão é ainda mais simples. Começamos com uma imagem completamente aleatória e depois aplicamos uma imagem do aperto várias vezes $$$f$ :

 def decompress(transformations, source_size, destination_size, step, nb_iter=8): factor = source_size // destination_size height = len(transformations) * destination_size width = len(transformations[0]) * destination_size iterations = [np.random.randint(0, 256, (height, width))] cur_img = np.zeros((height, width)) for i_iter in range(nb_iter): print(i_iter) for i in range(len(transformations)): for j in range(len(transformations[i])): # Apply transform k, l, flip, angle, contrast, brightness = transformations[i][j] S = reduce(iterations[-1][k*step:k*step+source_size,l*step:l*step+source_size], factor) D = apply_transformation(S, flip, angle, contrast, brightness) cur_img[i*destination_size:(i+1)*destination_size,j*destination_size:(j+1)*destination_size] = D iterations.append(cur_img) cur_img = np.zeros((height, width)) return iterations 

Esse algoritmo funciona porque o mapa de compactação possui um ponto fixo exclusivo e, independentemente da imagem de origem que escolhermos, nos esforçaremos por isso.

Acho que chegou a hora de um pequeno exemplo. Vou tentar comprimir e descompactar a imagem do macaco:


A função test_greyscale carrega a imagem, compacta, descompacta e mostra cada iteração da descompactação:


Nada mal para uma implementação tão simples!

Imagens RGB

Uma abordagem muito ingênua para compactar imagens RGB é compactar todos os três canais individualmente:

 def compress_rgb(img, source_size, destination_size, step): img_r, img_g, img_b = extract_rgb(img) return [compress(img_r, source_size, destination_size, step), \ compress(img_g, source_size, destination_size, step), \ compress(img_b, source_size, destination_size, step)] 

E para descompactar, basta descompactar os dados de três canais separadamente e coletá-los em três canais de imagem:

 def decompress_rgb(transformations, source_size, destination_size, step, nb_iter=8): img_r = decompress(transformations[0], source_size, destination_size, step, nb_iter)[-1] img_g = decompress(transformations[1], source_size, destination_size, step, nb_iter)[-1] img_b = decompress(transformations[2], source_size, destination_size, step, nb_iter)[-1] return assemble_rbg(img_r, img_g, img_b) 

Outra solução muito simples é usar a mesma tela de compactação para todos os três canais, porque eles geralmente são muito semelhantes.

Se você quiser verificar como isso funciona, execute a função test_rgb :


Artefatos apareceram. Esse método provavelmente é ingênuo demais para produzir bons resultados.

Para onde ir a seguir

Se você quiser saber mais sobre a compactação de imagem fractal, recomendo que você leia o artigo Técnicas de compactação de imagem Fractal e Wavelet de Stephen Welsted. É fácil de ler e explica técnicas mais sofisticadas.