【H.264/AVC视频编解码技术详解】七、 熵编码算法(1):基础知识

简介: 《H.264/AVC视频编解码技术详解》视频教程已经在“CSDN学院”上线,视频中详述了H.264的背景、标准协议和实现,并通过一个实战工程的形式对H.

《H.264/AVC视频编解码技术详解》视频教程已经在“CSDN学院”上线,视频中详述了H.264的背景、标准协议和实现,并通过一个实战工程的形式对H.264的标准进行解析和实现,欢迎观看!

“纸上得来终觉浅,绝知此事要躬行”,只有自己按照标准文档以代码的形式操作一遍,才能对视频压缩编码标准的思想和方法有足够深刻的理解和体会!

链接地址:H.264/AVC视频编解码技术详解

GitHub代码地址:点击这里

本节视频免费

1. 熵编码概念

“熵”这一概念原本来自于化学和热力学,用于度量能量退化的指标,即熵越高,物体或系统的做功能力越低。后来香农将这一概念引入到信息论中,用于表示消息的平均信息量。信源的熵通常可以表示信源所发出信息的不确定性,即越是随机的、前后不相关的信息,其熵越高。

在信息论中,香农提出了信源编码定理。该定理说明了香农熵与信源符号概率之间的关系,说明信息的熵为信源无损编码后的平均码字长度的下限。任何的无损编码方法都不可能使编码后的平均码长小于香农熵,只能使其尽量接近。

基于此,对信源进行熵编码的基本思想,是使其前后的码字之间尽量更加随机,尽量减小前后的相关性,更加接近其信源的香农熵。这样在表示同样的信息量时所用的数据长度更短。

在实际使用中,常用的熵编码主要有变长编码和算术编码等方法。其中变长编码相对于算术编码较为简单,但平均压缩比可能略低。常见的变长编码方法有哈夫曼编码和香农-费诺编码等。

2. 熵编码的简单实现——哈夫曼编码

戴维·哈夫曼(David·A·Huffman)于1952年在麻省理工学院的罗伯特·费诺的指导下攻读博士学位时,发明了一种基于有序频率二叉树的编码方法,该方法的编码效率超过了他的导师和信息论之父香农的研究成果(香农-费诺编码),因此又称作“最优编码方法”。

哈夫曼编码时变长编码方法的一种,该方法完全依赖于码字出现的概率来构造整体平均长度最短的编码方法。进行哈夫曼编码的关键步骤是建立符合哈夫曼编码规则的二叉树,该树又称作哈夫曼树。

哈夫曼树是一种特殊的二叉树,其终端节点的个数与待编码的码元的个数等同,而且每个终端节点上都带有各自的权值。每个终端节点的路径长度乘以该节点的权值的总和称为整个二叉树的加权路径长度。在满足条件的各种二叉树中,该路径长度最短的二叉树即为哈夫曼树。

在使用哈夫曼编码执行对码元的实际编码过程时,码元的权值可设置为其概率值,那么可以根据其权值来构建哈夫曼树。我们假设使用哈夫曼编码对以下概率的码字进行编码:

码字 概率
A 0.1
B 0.1
C 0.15
D 0.2
E 0.2
F 0.25

根据概率表构建哈夫曼树的过程如下图所示:

最终我们可以得到如下图所示的哈夫曼树:

在哈夫曼树构建完成后,便可以得到每一个码元的哈夫曼编码的码字。具体方法是:从哈夫曼树的根节点开始遍历,直至每一个终端节点,当访问某个节点的左子树时赋予码字0,访问右子树时赋予一个码字1(反之亦可),直到遍历到终端节点时这一路径所代表的0和1的串便是该码元的哈夫曼编码码字。

例如上图的哈夫曼树,根节点访问左子树ABCF,赋予码字0;然后再访问左子树ABC,赋予码字0,此时整个码字为00,然后访问右子树得到终端节点C,赋予码字1,此时便可以得到C的哈夫曼编码码字001。以此规律,整个六个元素的码元集合的编码码表为:

  • A: 0000
  • B: 0001
  • C: 001
  • D: 10
  • E: 11
  • F: 01

从这个码表中还可以看出另外一个规律:哈夫曼编码的任意一个码字,都不可能是其他码字的前缀。因此通过哈夫曼编码的信息可以紧密排列连续传输,而不用担心解码时的歧义性。

3. 哈夫曼树的构建Demo

下面的程序段给出一个构建哈夫曼树,并生成对应码元的哈夫曼编码的过程:

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

//每一个符号定义为一个结构体,包括字符和出现频次
typedef struct
{
    unsigned char   character;
    unsigned int    frequency;
} CharNode;

static bool open_input_file(ifstream &input, const char *inputFileName)
{
    input.open(inputFileName);
    if (!input.is_open())
    {
        return false;
    }
    return true;
}

struct MinHeapNode
{
    char data;
    unsigned int freq;
    MinHeapNode *left, *right;
    MinHeapNode(char data, unsigned freq)
    {
        left = right = NULL;
        this->data = data;
        this->freq = freq;
    }
};
typedef struct MinHeapNode MinHeapNode;

struct compare
{
    bool operator()(MinHeapNode* l, MinHeapNode *r)
    {
        return (l->freq > r->freq);
    }
};

static void get_huffman_code(MinHeapNode *root, string code)
{
    if (!root)
    {
        return;
    }

    if (root->data != -1)
    {
        cout << root->data << " : " << code << endl;;
    }

    get_huffman_code(root->left, code + "0");
    get_huffman_code(root->right, code + "1");
}

int _tmain(int argc, _TCHAR* argv[])
{
    ifstream inputFile;
    if (!open_input_file(inputFile, "input.txt"))
    {
        cout << "Error: opening input file failed!" << endl;
        return -1;
    }

    char buf = inputFile.get();
    CharNode nodeArr[256] = { { 0, 0 } };
    while (inputFile.good())
    {
        cout << buf;
        nodeArr[buf].character = buf;
        nodeArr[buf].frequency++;
        buf = inputFile.get();
    }
    cout << endl;

    priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare>  minHeap;
    for (int idx = 0; idx < 256; idx++)
    {
        if (nodeArr[idx].frequency > 0)
        {
            cout << "Node " << idx << ": [" << nodeArr[idx].character << ", " << nodeArr[idx].frequency << "]" << endl;
            minHeap.push(new MinHeapNode(nodeArr[idx].character, nodeArr[idx].frequency));
        }
    }

    MinHeapNode *leftNode = NULL, *rightNode = NULL, *topNode = NULL;
    while (minHeap.size() != 1)
    {
        leftNode = minHeap.top();
        minHeap.pop();

        rightNode = minHeap.top();
        minHeap.pop();

        topNode = new MinHeapNode(-1, leftNode->freq + rightNode->freq);
        topNode->left = leftNode;
        topNode->right = rightNode;
        minHeap.push(topNode);
    }

    get_huffman_code(topNode, "");

    inputFile.close();
    return 0;
}

程序的详细解释过程请到视频中观看。

目录
相关文章
|
2月前
|
人工智能 运维 算法
基于 C# 深度优先搜索算法的局域网集中管理软件技术剖析
现代化办公环境中,局域网集中管理软件是保障企业网络高效运行、实现资源合理分配以及强化信息安全管控的核心工具。此类软件需应对复杂的网络拓扑结构、海量的设备信息及多样化的用户操作,而数据结构与算法正是支撑其强大功能的基石。本文将深入剖析深度优先搜索(Depth-First Search,DFS)算法,并结合 C# 语言特性,详细阐述其在局域网集中管理软件中的应用与实现。
76 3
|
23天前
|
监控 算法 JavaScript
基于 JavaScript 图算法的局域网网络访问控制模型构建及局域网禁止上网软件的技术实现路径研究
本文探讨局域网网络访问控制软件的技术框架,将其核心功能映射为图论模型,通过节点与边表示终端设备及访问关系。以JavaScript实现DFS算法,模拟访问权限判断,优化动态策略更新与多层级访问控制。结合流量监控数据,提升网络安全响应能力,为企业自主研发提供理论支持,推动智能化演进,助力数字化管理。
41 4
|
25天前
|
存储 监控 算法
内网监控桌面与 PHP 哈希算法:从数据追踪到行为审计的技术解析
本文探讨了内网监控桌面系统的技术需求与数据结构选型,重点分析了哈希算法在企业内网安全管理中的应用。通过PHP语言实现的SHA-256算法,可有效支持软件准入控制、数据传输审计及操作日志存证等功能。文章还介绍了性能优化策略(如分块哈希计算和并行处理)与安全增强措施(如盐值强化和动态更新),并展望了哈希算法在图像处理、网络流量分析等领域的扩展应用。最终强调了构建完整内网安全闭环的重要性,为企业数字资产保护提供技术支撑。
53 2
|
2月前
|
机器学习/深度学习 存储 算法
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
本文系统讲解从基本强化学习方法到高级技术(如PPO、A3C、PlaNet等)的实现原理与编码过程,旨在通过理论结合代码的方式,构建对强化学习算法的全面理解。
129 10
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
|
2月前
|
存储 监控 算法
基于 Python 哈希表算法的局域网网络监控工具:实现高效数据管理的核心技术
在当下数字化办公的环境中,局域网网络监控工具已成为保障企业网络安全、确保其高效运行的核心手段。此类工具通过对网络数据的收集、分析与管理,赋予企业实时洞察网络活动的能力。而在其运行机制背后,数据结构与算法发挥着关键作用。本文聚焦于 PHP 语言中的哈希表算法,深入探究其在局域网网络监控工具中的应用方式及所具备的优势。
85 7
|
2月前
|
运维 监控 算法
基于 Python 迪杰斯特拉算法的局域网计算机监控技术探究
信息技术高速演进的当下,局域网计算机监控对于保障企业网络安全、优化资源配置以及提升整体运行效能具有关键意义。通过实时监测网络状态、追踪计算机活动,企业得以及时察觉潜在风险并采取相应举措。在这一复杂的监控体系背后,数据结构与算法发挥着不可或缺的作用。本文将聚焦于迪杰斯特拉(Dijkstra)算法,深入探究其在局域网计算机监控中的应用,并借助 Python 代码示例予以详细阐释。
73 6
|
2月前
|
存储 算法 物联网
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
50 0
|
3月前
|
人工智能 监控 算法
Python下的毫秒级延迟RTSP|RTMP播放器技术探究和AI视觉算法对接
本文深入解析了基于Python实现的RTSP/RTMP播放器,探讨其代码结构、实现原理及优化策略。播放器通过大牛直播SDK提供的接口,支持低延迟播放,适用于实时监控、视频会议和智能分析等场景。文章详细介绍了播放控制、硬件解码、录像与截图功能,并分析了回调机制和UI设计。此外,还讨论了性能优化方法(如硬件加速、异步处理)和功能扩展(如音量调节、多格式支持)。针对AI视觉算法对接,文章提供了YUV/RGB数据处理示例,便于开发者在Python环境下进行算法集成。最终,播放器凭借低延迟、高兼容性和灵活扩展性,为实时交互场景提供了高效解决方案。
190 4
|
3月前
|
缓存 监控 算法
基于 C# 网络套接字算法的局域网实时监控技术探究
在数字化办公与网络安全需求增长的背景下,局域网实时监控成为企业管理和安全防护的关键。本文介绍C#网络套接字算法在局域网实时监控中的应用,涵盖套接字创建、绑定监听、连接建立和数据传输等操作,并通过代码示例展示其实现方式。服务端和客户端通过套接字进行屏幕截图等数据的实时传输,保障网络稳定与信息安全。同时,文章探讨了算法的优缺点及优化方向,如异步编程、数据压缩与缓存、错误处理与重传机制,以提升系统性能。
67 2
|
4月前
|
监控 网络协议 算法
基于问题“如何监控局域网内的电脑”——Node.js 的 ARP 扫描算法实现局域网内计算机监控的技术探究
在网络管理与安全领域,监控局域网内计算机至关重要。本文探讨基于Node.js的ARP扫描算法,通过获取IP和MAC地址实现有效监控。使用`arp`库安装(`npm install arp`)并编写代码,可定期扫描并对比设备列表,判断设备上线和下线状态。此技术适用于企业网络管理和家庭网络安全防护,未来有望进一步提升效率与准确性。
94 8

热门文章

最新文章