+import os\r
+import math\r
+from collections import Counter\r
+import heapq\r
+import numpy as np\r
+import struct\r
+\r
+\r
+class BitMapFile:\r
+ def __init__(self, text):\r
+ self._text = text.split()\r
+ self.magic_number = self._text[0]\r
+ self.image_width = self._text[1]\r
+ self.image_height = self._text[2]\r
+ self.image_array = self._text[3:]\r
+ self.zeros = 0\r
+ self.ones = 0\r
+ self.size = int(self.image_width) * int(self.image_height)\r
+\r
+ for _ in range(len(self.image_array)):\r
+ if self.image_array[_] == "0":\r
+ self.zeros += 1\r
+ elif self.image_array[_] == "1":\r
+ self.ones += 1\r
+ else:\r
+ print("ignore")\r
+\r
+\r
+"""\r
+To read files\r
+"""\r
+def get_file(file_path):\r
+ with open(file_path, 'r', encoding='utf-8') as file:\r
+ _file_content = file.read()\r
+ return _file_content\r
+\r
+"""\r
+To evaluate comprimento médio do código - l(c)\r
+ l(all_pixels) = ceil(log2P(all_pixels))+1\r
+"""\r
+def arithmetic_cod_preview(_pbm):\r
+ print("\n*** Arithmetic Preview ***")\r
+ pixels = [int(pixel) for pixel in _pbm.image_array]\r
+ _P0 = _pbm.zeros/_pbm.size\r
+ _P1 = _pbm.ones/_pbm.size\r
+ _PT01_int = 1\r
+\r
+ for pixel in pixels:\r
+ if pixel == 0:\r
+ _PT01_int *= _P0\r
+ elif pixel == 1:\r
+ _PT01_int *= _P1\r
+\r
+ _arithmetic_encode_lenght = np.ceil(-1*np.log2(_PT01_int)) + 1\r
+ print(f"L(image) --> {_arithmetic_encode_lenght} bits")\r
+ _entropy = calcular_entropia(_pbm.image_array)\r
+ print(f"entropy --> {_entropy} bits")\r
+ _datastream = clean_image_data(_pbm.image_array)\r
+ _entropia_conditional = calcular_entropia_condicional(_datastream)\r
+ print(f"entropy condicional --> {_entropia_conditional} bits")\r
+ return int(_arithmetic_encode_lenght)\r
+\r
+"""\r
+Arithmetic Encoding approach\r
+\r
+it uses static probabilities provided on output file\r
+\r
+c(x)=|interval_low_val +(interval_high_val).F(x)_low\r
+ =|interval_low_val +(interval_high_val).F(x)_high\r
+_to_encode_val = avg(C(all)_low,C(all)_high)\r
+_output = bin(_to_encode_val))\r
+"""\r
+def arithmetic_encode_image(_pbm):\r
+ pixels = [int(pixel) for pixel in _pbm.image_array]\r
+ _P0 = np.float64(_pbm.zeros/_pbm.size)\r
+ _P1 = np.float64(_pbm.ones/_pbm.size)\r
+ _interval = [0,1]\r
+ # probabilidades acomuladas orderdanas por ordem crescente\r
+ _Fx = {1: (0,_P1),\r
+ 0: (_P1,1)}\r
+ _output_opt_1 = f"{_pbm.zeros} {_pbm.ones} {_pbm.image_width} {_pbm.image_height} "\r
+\r
+ for pixel in pixels:\r
+ if pixel == 0:\r
+ _low_val = np.float64(_interval[0] + (_interval[1]-_interval[0]) * _Fx.get(0)[0])\r
+ _high_val = np.float64(_interval[0] + (_interval[1]-_interval[0])*_Fx.get(0)[1])\r
+ if pixel == 1:\r
+ _low_val = np.float64(_interval[0] + (_interval[1] - _interval[0]) * _Fx.get(1)[0])\r
+ _high_val = np.float64(_interval[0] + (_interval[1] - _interval[0]) * _Fx.get(1)[1])\r
+ _interval[0] = _low_val\r
+ _interval[1] = _high_val\r
+\r
+ _to_encode_value = np.float64((_interval[0]+_interval[1])/2)\r
+ print(f"to encode --> {_to_encode_value}")\r
+ _output_opt_2 = _output_opt_1 + f"{_to_encode_value}"\r
+\r
+ _size = arithmetic_cod_preview(_pbm)\r
+ _res = _to_encode_value\r
+ for _ in range(_size):\r
+ _res *=2\r
+ if _res < 1:\r
+ _output_opt_1 += "0"\r
+ else:\r
+ _output_opt_1 += "1"\r
+ _res = _res-1\r
+\r
+\r
+ return _output_opt_1,_output_opt_2\r
+\r
+"""\r
+To decode encoded pbm files with arithmetic_encode_image()\r
+ amount_of_zeros amount_of_ones image_width image_height encoded_image\r
+"""\r
+def arithmetic_decode_file(_txt):\r
+ _encoded_pbm_file = get_file(_txt).split()\r
+\r
+ amount_of_zeros = int(_encoded_pbm_file[0])\r
+ amount_of_ones = int(_encoded_pbm_file[1])\r
+ image_width = int(_encoded_pbm_file[2])\r
+ image_height = int(_encoded_pbm_file[3])\r
+ encoded_image = np.float64(_encoded_pbm_file[4])\r
+\r
+ _output = f"P1\n{image_width} {image_height}\n"\r
+ _size = int(image_width) * int(image_height)\r
+ _P0 = np.float64(amount_of_zeros/_size)\r
+ _P1 = np.float64(amount_of_ones/_size)\r
+ _Fx = {1:(0,_P1),\r
+ 0:(_P1,1)}\r
+\r
+ _constructed_image = ""\r
+ for h in range(image_height):\r
+ for w in range(image_width):\r
+ if _P1 < encoded_image < 1:\r
+ _constructed_image += "0 "\r
+ encoded_image = (encoded_image-_P1)/_P0\r
+ elif 0 < encoded_image < _P1:\r
+ _constructed_image += "1 "\r
+ encoded_image = (encoded_image - 0) / _P1\r
+\r
+ if w == image_width-1:\r
+ _constructed_image += "\n"\r
+\r
+ _output += _constructed_image\r
+ return _output\r
+\r
+\r
+def calcular_entropia(bitstream):\r
+ n = len(bitstream)\r
+ if n == 0: return 0\r
+\r
+ p0 = bitstream.count('0') / n\r
+ p1 = bitstream.count('1') / n\r
+\r
+ entropia = 0\r
+ for p in [p0, p1]:\r
+ if p > 0:\r
+ entropia -= p * math.log2(p)\r
+ return entropia\r
+\r
+\r
+def calcular_entropia_condicional(bitstream):\r
+ transicoes = {'00': 0, '01': 0, '10': 0, '11': 0}\r
+ contagem_base = {'0': 0, '1': 0}\r
+\r
+ for i in range(len(bitstream) - 1):\r
+ par = bitstream[i:i + 2]\r
+ transicoes[par] += 1\r
+ contagem_base[bitstream[i]] += 1\r
+\r
+ h_condicional = 0\r
+ for base in ['0', '1']:\r
+ p_base = contagem_base[base] / (len(bitstream) - 1)\r
+ if p_base > 0:\r
+ h_local = 0\r
+ for prox in ['0', '1']:\r
+ p_transicao = transicoes[base + prox] / contagem_base[base]\r
+ if p_transicao > 0:\r
+ h_local -= p_transicao * math.log2(p_transicao)\r
+ h_condicional += p_base * h_local\r
+\r
+ return h_condicional\r
+\r
+\r
+def clean_image_data(image_data):\r
+ clean_text = ""\r
+\r
+ for line in image_data:\r
+ line = line.strip()\r
+ line = line.replace(" ", "")\r
+ if not line or line.startswith('#'):\r
+ continue\r
+ clean_text += line\r
+\r
+ return clean_text\r
+\r
+\r
+def calcular_taxa_compressao(caminho_original, caminho_comprimido, total_pixeis):\r
+ tamanho_orig = os.path.getsize(caminho_original)\r
+ tamanho_comp = os.path.getsize(caminho_comprimido)\r
+\r
+ poupanca = (1 - (tamanho_comp / tamanho_orig)) * 100\r
+\r
+ bpp = (tamanho_comp * 8) / total_pixeis\r
+\r
+ return poupanca, bpp, tamanho_orig, tamanho_comp\r
+\r
+\r
+def xor(bitstream, largura, altura):\r
+ matriz = []\r
+ for i in range(altura):\r
+ linha = [int(b) for b in bitstream[i * largura: (i + 1) * largura]]\r
+ matriz.append(linha)\r
+\r
+ nova_imagem = ""\r
+ # A primeira linha mantém-se igual (não tem linha anterior)\r
+ nova_imagem += "".join(map(str, matriz[0]))\r
+\r
+ for i in range(1, altura):\r
+ nova_linha = []\r
+ for j in range(largura):\r
+ res = matriz[i][j] ^ matriz[i - 1][j]\r
+ nova_linha.append(str(res))\r
+ nova_imagem += "".join(nova_linha)\r
+\r
+ return nova_imagem\r
+\r
+\r
+def descodificar_xor(bitstream_transformado, largura, altura):\r
+ matriz_temp = []\r
+ for i in range(altura):\r
+ linha = [int(b) for b in bitstream_transformado[i * largura: (i + 1) * largura]]\r
+ matriz_temp.append(linha)\r
+\r
+ matriz_original = []\r
+\r
+ matriz_original.append(matriz_temp[0])\r
+\r
+ for i in range(1, altura):\r
+ linha_recuperada = []\r
+ for j in range(largura):\r
+ pixel_original = matriz_temp[i][j] ^ matriz_original[i - 1][j]\r
+ linha_recuperada.append(pixel_original)\r
+ matriz_original.append(linha_recuperada)\r
+\r
+ bitstream_final = ""\r
+ for linha in matriz_original:\r
+ bitstream_final += "".join(map(str, linha))\r
+\r
+ return bitstream_final\r
+\r
+\r
+# -------------------------------------------------------------------------\r
+# HUFFMAN IMPLEMENTATION\r
+# -------------------------------------------------------------------------\r
+\r
+class HuffmanNode:\r
+ def __init__(self, char, freq):\r
+ self.char = char # 0 ou 1 que está no pixel\r
+ self.freq = freq # Quantas vezes aparece\r
+ self.left = None # Filho à esquerda\r
+ self.right = None # Filho à direita\r
+\r
+ # Nó com menor frequencia\r
+ def __lt__(self, other):\r
+ return self.freq < other.freq\r
+\r
+\r
+# Constroi a árvore\r
+def build_huffman_tree(pixels):\r
+ frequency = Counter(pixels)\r
+ heap = [HuffmanNode(char, freq) for char, freq in frequency.items()]\r
+ heapq.heapify(heap)\r
+\r
+ # Cria a árvore de baixo para cima / frequencia menor para maior\r
+ while len(heap) > 1:\r
+ node1 = heapq.heappop(heap)\r
+ node2 = heapq.heappop(heap)\r
+ merged = HuffmanNode(None, node1.freq + node2.freq)\r
+ merged.left = node1\r
+ merged.right = node2\r
+ heapq.heappush(heap, merged)\r
+\r
+ return heap[0] if heap else None\r
+\r
+\r
+# Cria os códigos (0 para a esquerda, 1 para a direira)\r
+def make_codes(node, current_code="", codes=None):\r
+ if codes is None:\r
+ codes = {}\r
+ if node is None:\r
+ return codes\r
+ if node.char is not None:\r
+ codes[node.char] = current_code\r
+ return codes\r
+\r
+ make_codes(node.left, current_code + "0", codes)\r
+ make_codes(node.right, current_code + "1", codes)\r
+ return codes\r
+\r
+\r
+# Faz encoding do ficheiro\r
+def huffman_encode_image(_pbm):\r
+ print("\n*** Huffman Encoding ***")\r
+ pixels = _pbm.image_array\r
+\r
+ # Erro caso não encontre a imagem\r
+ if not pixels:\r
+ print("Empty image.")\r
+ return None\r
+\r
+ # Constroi a árvore e os códigos\r
+ root = build_huffman_tree(pixels)\r
+ codes = make_codes(root)\r
+\r
+ print(f"Codes: {codes}")\r
+\r
+ # Faz encode dos pixeis\r
+ encoded_str = "".join([codes[p] for p in pixels])\r
+\r
+ # Garante que o total é multiplo de 8\r
+ extra_padding = 8 - len(encoded_str) % 8\r
+ encoded_str = encoded_str + "0" * extra_padding\r
+\r
+ # Reduz o tamanho convertendo de byte para bit\r
+ b = bytearray()\r
+ for i in range(0, len(encoded_str), 8):\r
+ byte = encoded_str[i:i + 8]\r
+ b.append(int(byte, 2))\r
+\r
+ # Cabeçalho\r
+ width = int(_pbm.image_width)\r
+ height = int(_pbm.image_height)\r
+ freq0 = _pbm.zeros\r
+ freq1 = _pbm.ones\r
+ header = struct.pack('>IIIIB', width, height, freq0, freq1, extra_padding)\r
+\r
+ return header + b\r
+\r
+\r
+# Faz decode do ficheiro\r
+def huffman_decode_file(filename):\r
+ print(f"\n*** Huffman Decoding from {filename} ***")\r
+\r
+ # Lê o ficheiro\r
+ with open(filename, 'rb') as f:\r
+ file_content = f.read()\r
+\r
+ # Separa o cabeçalho\r
+ header_size = struct.calcsize('>IIIIB')\r
+ width, height, freq0, freq1, extra_padding = struct.unpack('>IIIIB', file_content[:header_size])\r
+ encoded_data = file_content[header_size:]\r
+\r
+ print(f"Header Info -> W:{width}, H:{height}, Zeros:{freq0}, Ones:{freq1}")\r
+\r
+ # Constroi a árvore\r
+ fake_pixels = ['0'] * freq0 + ['1'] * freq1\r
+ root = build_huffman_tree(fake_pixels)\r
+ codes = make_codes(root)\r
+\r
+ # Faz decode dos pixeis\r
+ reverse_codes = {v: k for k, v in codes.items()}\r
+\r
+ # Converte os bytes em string\r
+ bit_string = ""\r
+ for byte in encoded_data:\r
+ bit_string += f"{byte:08b}"\r
+\r
+ # Desencripta\r
+ decoded_pixels = []\r
+ current_code = ""\r
+ for bit in bit_string:\r
+ current_code += bit\r
+ if current_code in reverse_codes:\r
+ decoded_pixels.append(reverse_codes[current_code])\r
+ current_code = ""\r
+\r
+ # Limita o tamanho width * height\r
+ expected_pixels = width * height\r
+ decoded_pixels = decoded_pixels[:expected_pixels]\r
+\r
+ pbm_content = f"P1\n{width} {height}\n"\r
+\r
+ # Formata as linhas para não ficar sequencial\r
+ row_str = ""\r
+ for i, p in enumerate(decoded_pixels):\r
+ row_str += p + " "\r
+ if (i + 1) % width == 0:\r
+ pbm_content += row_str.strip() + "\n"\r
+ row_str = ""\r
+\r
+ print("Decoding finished.")\r
+ return pbm_content\r
projects / ue-ccd-compressaodeimagensbinarias.git / commitdiff