python中的图像压缩

Question

对于我的图像压缩，我使用枕头库获得rgb中的每个像素（例如：（100，0200）。使用哈夫曼编码，我已经将其转换为二进制，以减少比特数。现在，我必须将位序列保存到文本或二进制文件中。压缩文件始终比原始文件小，但目前，我的txt文件比原始文件大。我该怎么办？在那之后，我如何读取文件并解压缩它。以下是说明：

您的代码应该读取图像文件，计算固定长度编码需要多少位，然后应用压缩算法创建较小的编码-您需要实现压缩，您不能使用压缩库。您应该输出以压缩格式存储图像所需的位数以及实现的压缩比。在保存压缩图像时，您将无法将其保存为标准图像格式，因为您将创建自己的编码，但您可以将位序列保存到文本或二进制文件中。

您的代码还应该能够提示用户输入包含压缩位序列的文本文件的文件名，然后将该文件解压缩到原始图像中–您可以假设该文件使用与上次压缩的文件相同的压缩格式。例如，如果你压缩了安抚。bmp转换成一系列位存储在Pacifica中。然后用户要求您解压缩alt\u编码。txt，你可以假设alt_安抚。txt使用与encode相同的压缩数据结构。txt（例如，它可能是原始图像数据的子集）。

有许多库可以帮助您将格式化的数据从Python存储到文件中。如果您研究这些选项并找到一种将压缩数据结构存储到文件中的方法，以便用户可以选择位文件和数据结构文件并使用数据结构来解压缩位文件

只需使用我当前的图像：flag2。bmp

这是我的密码

from PIL import  Image
import sys, string
import copy
import time


codes   = {}
def sortFreq (freqs) :
    letters = freqs.keys()
    tuples = []
    for let in letters :
        tuples.append((freqs[let],let))
    tuples.sort()
    return tuples

def buildTree(tuples) :
    while len(tuples) > 1 :
        leastTwo = tuple(tuples[0:2])                  # get the 2 to combine
        theRest  = tuples[2:]                          # all the others
        combFreq = leastTwo[0][0] + leastTwo[1][0]     # the branch points freq
        tuples   = theRest + [(combFreq,leastTwo)]     # add branch point to the end
        tuples.sort()                                  # sort it into place
    return tuples[0]            # Return the single tree inside the list

def trimTree (tree) :
     # Trim the freq counters off, leaving just the letters
    p = tree[1]                                    # ignore freq count in [0]
    if type(p) == type("") : return p              # if just a leaf, return it
    else : return (trimTree(p[0]), trimTree(p[1])) # trim left then right and recombine

def assignCodes(node, pat=''):
    global codes
    if type(node) == type("") :
        codes[node] = pat                # A leaf. set its code
    else  :                              #
        assignCodes(node[0], pat+"0")    # Branch point. Do the left branch
        assignCodes(node[1], pat+"1")    # then do the right branch.


start = time.time()
dictionary = {}
table = {}
image = Image.open('flag2.bmp')
#image.show()
width, height = image.size
px= image.load()

totalpixel = width*height
print("Total pixel: "+ str(totalpixel))

for x in range(width):
    for y in range(height):
       # print(px[x, y])
        for i in range(3):

            if dictionary.get(str(px[x, y][i])) is None:
                dictionary[str(px[x, y][i])] = 1
            else:
                dictionary[str(px[x, y][i])] = dictionary[str(px[x, y][i])] +1
table = copy.deepcopy(dictionary)

def encode2 (str) :
    global codes
    output = ""
    for ch in str : output += codes[ch]
    return output

def decode (tree, str) :
    output = ""
    p = tree
    for bit in str :
        if bit == '0' : p = p[0]     # Head up the left branch
        else          : p = p[1]     # or up the right branch
        if type(p) == type("") :
            output += p              # found a character. Add to output
            p = tree                 # and restart for next character
    return output

combination = len(dictionary)
for value in table:
    table[value] = table[value] / (totalpixel * combination) * 100
print(table)

print(dictionary)
sortdic = sortFreq(dictionary)

tree = buildTree(sortdic)
print("tree")
print(tree)
trim = trimTree(tree)
print("trim")
print(trim)
print("assign 01")
assignCodes(trim)
print(codes)
empty_tuple = ()
f = open("answer.txt","w")

for x in range(width):
    for y in range(height):
        list = []
        list.append(codes[str(px[x, y][0])])
        list.append(codes[str(px[x, y][1])])
        list.append(codes[str(px[x, y][2])])
        print(str(px[x, y]) + ": " +str(list))
        f.write(str(list))

print("decode test:", str(decode (trim, "1100")))


stop = time.time()
times = (stop - start) * 1000
print("Run time takes %d miliseconds" % times)

[flag2.bmp][1]

Answer 1

让我们利用Python标准库提供的算法，稍微重构一下代码，同时保持哈夫曼树计算和图像编码方法的精神。

首先，我们可以将符号计数重构为一个函数，并以更简洁的方式重写它：

• 使用图像。getdata（）迭代图像中的所有像素

此外，我们可以将其更改为返回一个（符号，计数）列表，按（计数，符号）升序排序。为此，我们可以将其与您的sortFreq（…）的重写版本结合起来 功能，利用：

• Python排序（…） 函数（允许我们定义排序依据的键），以及
• 元组切片以反转用于排序的元组（符号，计数）

实施：

from collections import Counter
from itertools import chain

def count_symbols(image):
    pixels = image.getdata()
    values = chain.from_iterable(pixels)
    counts = Counter(values).items()
    return sorted(counts, key=lambda x:x[::-1])

这里只需要一个小的改变——因为我们已经对符号计数进行了排序，我们只需要反转元组即可让您现有的树构建算法工作。我们可以使用列表理解和元组切片来简洁地表达这一点。

实施：

def build_tree(counts) :
    nodes = [entry[::-1] for entry in counts] # Reverse each (symbol,count) tuple
    while len(nodes) > 1 :
        leastTwo = tuple(nodes[0:2]) # get the 2 to combine
        theRest = nodes[2:] # all the others
        combFreq = leastTwo[0][0] + leastTwo[1][0]  # the branch points freq
        nodes = theRest + [(combFreq, leastTwo)] # add branch point to the end
        nodes.sort() # sort it into place
    return nodes[0] # Return the single tree inside the list

同样，只需对原始实现进行两个小改动：

• 将测试更改为检查元组（节点），以独立于符号的表示方式
• 去掉不必要的其他

实施：

def trim_tree(tree) :
    p = tree[1] # Ignore freq count in [0]
    if type(p) is tuple: # Node, trim left then right and recombine
        return (trim_tree(p[0]), trim_tree(p[1]))
    return p # Leaf, just return it

这里最重要的变化是消除对全局code变量的依赖。要解决它，我们可以将实现拆分为两个函数，一个处理递归代码分配，另一个包装器创建新的本地code字典，在其上调度递归函数，并返回输出。

让我们也将代码的表示从字符串切换到位列表（范围[0,1]中的整数）——稍后将清楚这一点的有用性。

再次，我们将更改测试以检查tuples（原因与修剪时相同）。

实施：

def assign_codes_impl(codes, node, pat):
    if type(node) == tuple:
        assign_codes_impl(codes, node[0], pat + [0]) # Branch point. Do the left branch
        assign_codes_impl(codes, node[1], pat + [1]) # then do the right branch.
    else:
        codes[node] = pat # A leaf. set its code

def assign_codes(tree):
    codes = {}
    assign_codes_impl(codes, tree, [])
    return codes

让我们绕一个小圈子，谈谈数据的编码。

首先，让我们观察原始RGB像素由3个字节表示（每个颜色通道一个字节），即每个像素24位，并形成我们的基线。

现在，您当前的算法将第一个像素编码为以下ASCII字符串：

['000', '0010', '0011']

总共23个字节（或184位）。这比生的要糟糕得多。让我们来看看原因：

• 有两个空间，这只是让它更可读的人。这些没有信息。（2字节）

总的来说，每像素12个字节根本不携带任何信息。剩下的11个字节（在这个特殊情况下）确实携带了一些信息。。。但是多少钱？

请注意，输出字母表中只有两个可能的符号是0和1。这意味着每个符号携带1位信息。由于将每个符号存储为ASCII字符（一个字节），因此每1位信息使用8位。

总而言之，在这个特殊的例子中，您使用184位来表示11位信息——比需要的多出约16.7倍，比仅以原始格式存储像素差约7.67倍。

显然，使用编码数据的朴素文本表示不会产生任何压缩。我们需要更好的方法。

从我们之前的分析中，很明显，为了有效地执行压缩（和解压缩），我们需要能够将我们的输出（或输入）视为单个位的流。标准Python库没有提供直接的解决方案来做到这一点——在最低颗粒度下，我们一次只能读取或写入一个字节的文件。

由于我们希望对可能由多个位组成的值进行编码，因此有必要根据重要性对其进行解码。让我们从最重要的到最不重要的顺序排列。

如前所述，我们将位序列表示为范围[0,1]中的整数列表。让我们从编写一些简单的实用程序函数开始：

• 将整数转换为唯一表示它的最短位序列的函数（即至少1位，但没有前导零）。
• 将位序列转换为整数的函数。
• 一个函数，它对比特序列进行零扩展（将零添加到最有效的位置）（以允许固定长度编码）。

实施：

def to_binary_list(n):
    """Convert integer into a list of bits"""
    return [n] if (n <= 1) else to_binary_list(n >> 1) + [n & 1]

def from_binary_list(bits):
    """Convert list of bits into an integer"""
    result = 0
    for bit in bits:
        result = (result << 1) | bit
    return result

def pad_bits(bits, n):
    """Prefix list of bits with enough zeros to reach n digits"""
    assert(n >= len(bits))
    return ([0] * (n - len(bits)) + bits)

示例用法：

>>> to_binary_list(14)
[1, 1, 1, 0]
>>> from_binary_list([1,1,1,0])
14
>>> pad_bits(to_binary_list(14),8)
[0, 0, 0, 0, 1, 1, 1, 0]

由于文件I/O API允许我们只保存整个字节，因此我们需要创建一个包装类来缓冲写入内存流中的位。

让我们提供写入单个位的方法以及位序列。

每个写入命令（1位或更多位）将首先将位添加到缓冲区中。一旦缓冲区包含超过8位，则从前面删除8位组，转换为范围[0-255]内的整数并保存到输出文件。直到缓冲区包含少于8位为止。

最后，让我们提供一种“刷新”流的方法——当缓冲区为非空，但包含的位不足以构成整个字节时，将零添加到最低有效位置，直到有8位，然后写入该字节。当我们关闭比特流时，我们需要它（我们稍后将看到其他一些好处）。

实施：

class OutputBitStream(object): 
    def __init__(self, file_name): 
        self.file_name = file_name
        self.file = open(self.file_name, 'wb') 
        self.bytes_written = 0
        self.buffer = []

    def write_bit(self, value):
        self.write_bits([value])

    def write_bits(self, values):
        self.buffer += values
        while len(self.buffer) >= 8:
            self._save_byte()        

    def flush(self):
        if len(self.buffer) > 0: # Add trailing zeros to complete a byte and write it
            self.buffer += [0] * (8 - len(self.buffer))
            self._save_byte()
        assert(len(self.buffer) == 0)

    def _save_byte(self):
        bits = self.buffer[:8]
        self.buffer[:] = self.buffer[8:]

        byte_value = from_binary_list(bits)
        self.file.write(bytes([byte_value]))
        self.bytes_written += 1

    def close(self): 
        self.flush()
        self.file.close()

输入比特流遵循类似的主题。我们希望一次读取1位或更多位。为此，我们从文件中加载字节，将每个字节转换为比特列表，并将其添加到缓冲区，直到有足够的字节满足读取请求。

在这种情况下，flush命令清除缓冲区（确保它只包含零）。

实施：

class InputBitStream(object): 
    def __init__(self, file_name): 
        self.file_name = file_name
        self.file = open(self.file_name, 'rb') 
        self.bytes_read = 0
        self.buffer = []

    def read_bit(self):
        return self.read_bits(1)[0]

    def read_bits(self, count):
        while len(self.buffer) < count:
            self._load_byte()
        result = self.buffer[:count]
        self.buffer[:] = self.buffer[count:]
        return result

    def flush(self):
        assert(not any(self.buffer))
        self.buffer[:] = []

    def _load_byte(self):
        value = ord(self.file.read(1))
        self.buffer += pad_bits(to_binary_list(value), 8)
        self.bytes_read += 1

    def close(self): 
        self.file.close()

接下来，我们需要定义压缩比特流的格式。解码图像需要三个基本信息块：

• 图像的形状（高度和宽度），假设它是3通道RGB图像

让我们按如下方式制作压缩格式：

• 标头
  • 图像高度（16位，无符号）
  • 图像宽度（16位，无符号）
  • 算法见此
  • 宽*高*3霍夫曼码按顺序

  实施：

  from PIL import Image
  
  def compressed_size(counts, codes):
      header_size = 2 * 16 # height and width as 16 bit values
  
      tree_size = len(counts) * (1 + 8) # Leafs: 1 bit flag, 8 bit symbol each
      tree_size += len(counts) - 1 # Nodes: 1 bit flag each
      if tree_size % 8 > 0: # Padding to next full byte
          tree_size += 8 - (tree_size % 8)
  
      # Sum for each symbol of count * code length
      pixels_size = sum([count * len(codes[symbol]) for symbol, count in counts])
      if pixels_size % 8 > 0: # Padding to next full byte
          pixels_size += 8 - (pixels_size % 8)
  
      return (header_size + tree_size + pixels_size) / 8
  
  def encode_header(image, bitstream):
      height_bits = pad_bits(to_binary_list(image.height), 16)
      bitstream.write_bits(height_bits)    
      width_bits = pad_bits(to_binary_list(image.width), 16)
      bitstream.write_bits(width_bits)
  
  def encode_tree(tree, bitstream):
      if type(tree) == tuple: # Note - write 0 and encode children
          bitstream.write_bit(0)
          encode_tree(tree[0], bitstream)
          encode_tree(tree[1], bitstream)
      else: # Leaf - write 1, followed by 8 bit symbol
          bitstream.write_bit(1)
          symbol_bits = pad_bits(to_binary_list(tree), 8)
          bitstream.write_bits(symbol_bits)
  
  def encode_pixels(image, codes, bitstream):
      for pixel in image.getdata():
          for value in pixel:
              bitstream.write_bits(codes[value])
  
  def compress_image(in_file_name, out_file_name):
      print('Compressing "%s" -> "%s"' % (in_file_name, out_file_name))
      image = Image.open(in_file_name)
      print('Image shape: (height=%d, width=%d)' % (image.height, image.width))
      size_raw = raw_size(image.height, image.width)
      print('RAW image size: %d bytes' % size_raw)
      counts = count_symbols(image)
      print('Counts: %s' % counts)
      tree = build_tree(counts)
      print('Tree: %s' % str(tree))
      trimmed_tree = trim_tree(tree)
      print('Trimmed tree: %s' % str(trimmed_tree))
      codes = assign_codes(trimmed_tree)
      print('Codes: %s' % codes)
  
      size_estimate = compressed_size(counts, codes)
      print('Estimated size: %d bytes' % size_estimate)
  
      print('Writing...')
      stream = OutputBitStream(out_file_name)
      print('* Header offset: %d' % stream.bytes_written)
      encode_header(image, stream)
      stream.flush() # Ensure next chunk is byte-aligned
      print('* Tree offset: %d' % stream.bytes_written)
      encode_tree(trimmed_tree, stream)
      stream.flush() # Ensure next chunk is byte-aligned
      print('* Pixel offset: %d' % stream.bytes_written)
      encode_pixels(image, codes, stream)
      stream.close()
  
      size_real = stream.bytes_written
      print('Wrote %d bytes.' % size_real)
  
      print('Estimate is %scorrect.' % ('' if size_estimate == size_real else 'in'))
      print('Compression ratio: %0.2f' % (float(size_raw) / size_real))
  

  实施：

  from PIL import Image
  
  def decode_header(bitstream):
      height = from_binary_list(bitstream.read_bits(16))
      width = from_binary_list(bitstream.read_bits(16))
      return (height, width)
  
  # https://stackoverflow.com/a/759766/3962537
  def decode_tree(bitstream):
      flag = bitstream.read_bits(1)[0]
      if flag == 1: # Leaf, read and return symbol
          return from_binary_list(bitstream.read_bits(8))
      left = decode_tree(bitstream)
      right = decode_tree(bitstream)
      return (left, right)
  
  def decode_value(tree, bitstream):
      bit = bitstream.read_bits(1)[0]
      node = tree[bit]
      if type(node) == tuple:
          return decode_value(node, bitstream)
      return node
  
  def decode_pixels(height, width, tree, bitstream):
      pixels = bytearray()
      for i in range(height * width * 3):
          pixels.append(decode_value(tree, bitstream))
      return Image.frombytes('RGB', (width, height), bytes(pixels))
  
  def decompress_image(in_file_name, out_file_name):
      print('Decompressing "%s" -> "%s"' % (in_file_name, out_file_name))
  
      print('Reading...')
      stream = InputBitStream(in_file_name)
      print('* Header offset: %d' % stream.bytes_read)
      height, width = decode_header(stream)
      stream.flush() # Ensure next chunk is byte-aligned
      print('* Tree offset: %d' % stream.bytes_read)    
      trimmed_tree = decode_tree(stream)
      stream.flush() # Ensure next chunk is byte-aligned
      print('* Pixel offset: %d' % stream.bytes_read)
      image = decode_pixels(height, width, trimmed_tree, stream)
      stream.close()
      print('Read %d bytes.' % stream.bytes_read)
  
      print('Image size: (height=%d, width=%d)' % (height, width))
      print('Trimmed tree: %s' % str(trimmed_tree))
      image.save(out_file_name)
  

  from PIL import ImageChops
  
  def raw_size(width, height):
      header_size = 2 * 16 # height and width as 16 bit values
      pixels_size = 3 * 8 * width * height # 3 channels, 8 bits per channel
      return (header_size + pixels_size) / 8
  
  def images_equal(file_name_a, file_name_b):
      image_a = Image.open(file_name_a)
      image_b = Image.open(file_name_b)
  
      diff = ImageChops.difference(image_a, image_b)
  
      return diff.getbbox() is None
  
  if __name__ == '__main__':
      start = time.time()
  
      compress_image('flag.png', 'answer.txt')
  
      print('-' * 40)
  
      decompress_image('answer.txt', 'flag_out.png')
  
      stop = time.time()
      times = (stop - start) * 1000
  
      print('-' * 40)
  
      print('Run time takes %d miliseconds' % times)
      print('Images equal = %s' % images_equal('flag.png', 'flag_out.png'))
  

  我用您提供的示例图像运行了脚本。

  控制台输出：

  Compressing "flag.png" -> "answer.txt"
  Image shape: (height=18, width=23)
  RAW image size: 1246 bytes
  Counts: [(24, 90), (131, 90), (215, 90), (59, 324), (60, 324), (110, 324)]
  Tree: (1242, ((594, ((270, ((90, 215), (180, ((90, 24), (90, 131))))), (324, 59))), (648, ((324, 60), (324, 110)))))
  Trimmed tree: (((215, (24, 131)), 59), (60, 110))
  Codes: {215: [0, 0, 0], 24: [0, 0, 1, 0], 131: [0, 0, 1, 1], 59: [0, 1], 60: [1, 0], 110: [1, 1]}
  Estimated size: 379 bytes
  Writing...
  * Header offset: 0
  * Tree offset: 4
  * Pixel offset: 12
  Wrote 379 bytes.
  Estimate is correct.
  Compression ratio: 3.29
  ----------------------------------------
  Decompressing "answer.txt" -> "flag_out.png"
  Reading...
  * Header offset: 0
  * Tree offset: 4
  * Pixel offset: 12
  Read 379 bytes.
  Image size: (height=18, width=23)
  Trimmed tree: (((215, (24, 131)), 59), (60, 110))
  ----------------------------------------
  Run time takes 32 miliseconds
  Images equal = True
  

  • 每个颜色通道的哈夫曼表