您当前位置: 首页 »

数据结构 & 算法

分类目录归档: 数据结构 & 算法

【h264、baseline、flv】使用baseline做双向强交互直播不利的几点因素

再说baseline做强交互不利因素之前,先说说现在直播的场景情况。

 

场景如上图,推流段不是移动平台,就是PC机。当然最近几年也出现专门用来推流的定制盒子,本质不是一个嵌入式windows,就是一个android设备(android设备较多)。

  • 而对于PC机作为推流端来说其实问题并不大,只要在保证带宽足够理想的情况下,采用264的任何一种profile都能尽可能的做到最大延时接近编码器固有延时的效果。同样对于使用何种容器来说问题都不大。

 

  • 但对于移动设备来说,需要匹配的情景就很多了,主要是由于移动设备的电池续航能力、操作系统小类别太多、整体性能表现。在使用264编解码时,一般尽量采用硬编解码,对于实在没有办法的情况下才使用软编解码。就仅仅一个硬编解码上就存在诸多差异,例如有些profile硬件不支持,或者rom上存在一些问题导致本该支持的profile,支持的不好或者根本不支持。

 

  • 除了上述提到的问题以外,其实还有一个隐形问题,那就是用户使用习惯问题。现在的用户越来越偏向于使用web方式展现的产品,一方面对于开发者来说,界面改动较为简单灵活,另一方面对于用户来说,只需要打开浏览器即可,简化使用步骤。

然而上述提到的这些问题,就造就了可能大家会想到flash、h5和native应用,对于native应用来说还好,开发起来虽然周期长,但可塑性比较强。对于flash和h5来说可选择余地就非常小了。

暂时不说flash和h5本身在做双向强交互直播是否可行,先说一说两者采用的协议类型。对于flash来说:

  • 通讯协议为rtmp系列协议(包括rtmpt等),协议本身并不是太复杂,但涉及当初并不是用来做双向强交互的直播协议,因此协议本身就没有在双向强交互上做太多的考虑。

 

  • 由于协议本身所承载的流媒体容器格式为flv或f4v,现在大部分直播平台基本采用的是flv作为容器,同时flv也是一种较为简单易用的容器

 

  • 但由于flv容器格式的限制,在adobe官方手册中就已经说明,flv容器支持的264的profile范围中,目前仅对baseline、extended、main、high、high10、high4:2:2、high4:4:4,在经过简单测试之后,如果不考虑flash端推流的情况下,用户电脑(移动端一般用h5,不用flash)性能具备一定保证的情况下,再根据官方手册并测试(as3手册),没有实际去测试过high10,不过脑补得知high10也是可以的,但延时太大,也有可能会引起其他flash异常。因此往往最佳的选择就在baseline、main、high中选择,因为他们的颜色编码是8bit的。从解码效率和广泛性来说,这三种都可以。

 

  • 但由于是双向直播,因此,在这时就需要考虑编解码器的时延问题。这时,大家一贯的做法就是关闭B帧编码,这样即可极大的提高编解码延时。当关闭了B帧编码之后,剩下几种profile互相比拼的就是在给定的一个平均分辨率、gop的情况下,编解码固有时延和数据码率,以及支持的广泛性。实测之后发现high其实在不同浏览器的flash上表现存在一定差异,主要情形为编解码速度、性能开销等等。因此在flash上使用high这种方式时,还需要综合考虑。

 

接下来说一说h5方式的直播:

  • h5方式的直播一般是通过websocket进行通讯,协议是hls,容器格式为ts、ps。然而我对hls和ts、ps都不是很了解。

 

  • h5支持还有待进一步推广,目前在较新的chrome系浏览器和较新的firefox浏览器上均支持较好。IE系暂时较弱(我把edge理解成IE系)。

 

  • 就目前来说,从开发手机端开发难度,和各手机厂商的支持力度上,无论是webview app还是native app来说,hls+ps/ts也是较优选择。

 

  • 通过看了苹果官方的FAQ得知,hls协议似乎仅仅支持baseline、main、high三种,不清楚是由于ts、ps容器特性导致的,还是hls协议特点。因此在决定使用哪一种profile时,又回到了和flash一样的情况下。

 

通过以上可以得知,实际上在使用x264编码时,最终在profile的选择上基本就限制在了baseline、main、high三种。从算法复杂度上来上讲,baseline是最为简单,而high是较为最为复杂(主要是预测模型比前两者多不少)。

不过在实际工程应用中,我们还是做了一个比较脑残又没有办法的决定,那就是使用baseline。原因有二:

  1. 我们使用的编码库是openh264,早期版本的openh264宏块分割方式较小,也仅仅支持baseline,对main也只是仅限于试验阶段。
  2. 在同样的profile级别下,参数大致相同的情况下,openh264的编码时延比x264的utral模式下略高,但码率略低(未做定量测试,简单定性测试得到的结论)。编码完的数据解码出来的视觉感受差别不大,反正都是渣画质。

考虑到使用场景和当时网络的大环境,确实选择openh264,即是无奈的选择,也是一个极其脑残的选择。说无奈主要是现实,说脑残是因为压根就没有做过定性分析。。。。。。

然后接下来就开始“数落数落”baseline不适合做双向强交互直播的原因。在看x264的代码时,偶然对编码中的预测做了少许的了解。

—- 我是装逼的分割线 1号 —-

传统上对一副图像的处理,一般的理论是基于“分割”,由于图像一般情况下具有前景和后景之分,也就是说,前景和背景之间存在着大量的局部图像细节,对于图像压缩中的思路往往是,尽量将相似的区域用差别不大的统一一个区域去表达,对于差异较大的区域,尽量在用较多的数据量去存储以此保留图像的局部细节。

那么就会存在如何分割图像的问题。如果是一副简单单值图,例如大学时代我做的非矢量图压缩(理论基础差不多),那么只需要根据图像分辨率,做相应的最佳分割快大小计算,并做简单切割即可。将区域内的有色的点和无色的点进行记录,并按做纵向或横向切割成色带,记录色带中有色点或者无色点的坐标值即可。整个思路转换成代码思维,类似于多级联映射表。当然这个做法的关键还在于公式如何设计,即如何动态计算切割区域的大小。由于是做印章方面,所以图像不会太大,因此公式也非常简单。

最终压缩可以理解成单值图的无损压缩,实测试之后,和转换成矢量图之后的文件大小相比,应该两者都会比现在主流的大部分图像编码小非常多。

接着通过类似7z、rar工具里面的二进制压缩算法进行再次压缩,文件最大还能缩小60%左右。一个500k的位图最终生成文件在3k左右。

—- 我是装逼的分割线 2号 —-

由于有上面的实践基础,因此在理解264的压缩时,我也能够理解到“分割”时的重要性。

首先,在baseline模式下,x264的预测模型相对于其他high来说,非常简单。这样的情况就决定了,在局部的细节切块相比high来说有着很多不足,对二进制数据进行压缩前就已经输在起跑线了。即细节丢失比high多。

其次在编码算法上(或者说压缩算法上),baseline仅仅使用cavlc,而对其他两者来说他们既可以使用cavlc也可以使用cabac。没有做过定性或者定考量分析,但通过网上资料获知,cavlc的效率似乎没有cabac高,具体在哪些指标有所体现目前暂时并不清楚。

因此,可以得知。baseline除了在实时性上满足了双向强交互直播对时间的要求,对于相同质量下的压缩比并不是很好。但又由于baseline相对其他profile的简单特点,其实广泛性还是比较不错的。

手里有台android 2.3时代的三星手机,对baseline的视频进行解码,手机基本可以应付(不清楚是硬解还是软解,因为当时的arm好像还有没有对264硬解做太多优化),但相同视频长度的main和high的话,那就有点头疼了。看来baseline对老旧手机还是比较“良好”的。

2017-11-22 | | matlab, 数据结构 & 算法, 音视频_图像相关, 音视频编解码

【h264、baseline、flv】使用baseline做双向强交互直播不利的几点因素已关闭评论

【x264、宏块、邻居】x264中对宏块预测方向与邻居类型的定义

在x264中,由于单一宏块预测方向与264规范定义实际上是一直的,即预测方向只有:左(left)、上(top)、左上(left-top)、右上(right-top)。

没有其他的另外四个方向,估计可能是zig-zag的数据排列有关,或只是由于对称关系,不需要做重复预测。

有上述4中预测方向,x264中定义了几种邻居关系(下面拿I帧4×4的宏块距离说明):

  • 垂直方向,即I_PRED_4x4_V、I_PRED_4x4_DC_TOP,实际上是向上方向预测(top)
  • 水平方向,即I_PRED_4x4_H、I_PRED_4x4_HU、I_PRED_4x4_DC_LEFT,实际上是向左方向预测(left)
  • 左边和向上方向,即I_PRED_4x4_DC
  • 向上旋转到右上方向,即I_PRED_4x4_DDL、I_PRED_4x4_VL
  • 左边旋转到向上方向,即I_PRED_4x4_DDR、I_PRED_4x4_VR、I_PRED_4x4_HD
  • 左边旋转到向上方向,即I_PRED_4x4_VL
  • I_PRED_4x4_DC_128代表自身?
2017-11-21 | | 数据结构 & 算法, 音视频_图像相关, 音视频编解码

【x264、宏块、邻居】x264中对宏块预测方向与邻居类型的定义已关闭评论

【matlab、启动错误】在远程桌面中无法启动matlab问题

最近一直在通过远程桌面的方式使用笔记本,突然发现matlab死活都打不开,出现如下错误

555

 

起初以为安装出问题,后来网上看了下才知道是远程桌面的锅。直接用基本登录,问题解决。

2016-11-22 | | matlab, win, 图像处理, 数据结构 & 算法, 编码技巧, 音视频_图像相关

【matlab、启动错误】在远程桌面中无法启动matlab问题已关闭评论

【有向图、迭代、抽象、线性代数、数学】有向图用矩阵理论化计算可能路径

在数据结构和数学中,都有着有向图的理论路径计算和迭代。一下是线性代数中对有向图的一个抽象。

 

 

%e6%9c%89%e5%90%91%e5%9b%be

%e6%9c%89%e5%90%91%e5%9b%be1

 

 

 

 

可见, 如果需要枚举出某个断点到另一个断点的可能路径的话,那就是对A矩阵进行做幂计算。例如计算1号端点到4号断点4次中转以内的可能路径,那么只需要对A矩阵做四次幂运算(1,2,3,4),然后求和4种幂运算中的a14,即可得到可能的路径数。

2016-09-26 | | 思考, 数学, 数据结构 & 算法, 算法导论, 线性代数

【有向图、迭代、抽象、线性代数、数学】有向图用矩阵理论化计算可能路径已关闭评论

【matlab、c++、0.499】关于matlab和c++在浮点数转整数的问题 – 四舍五入

当用c/c++做浮点数转换成整数时,处理一般都很简单,丢掉小数位置保留整数部分(没有看过具体的汇编,不清楚如果浮点数表达的位置太大,以至于整数溢出的情况)。

 

而在matlab中,浮点数转换成整数时候,会有四舍五入的规则,即:

uint8(0.499) = 0

uint8(0.5) = 1

 

所以在用matlab时,需要注意到数值转换与c/c++的不同。

2016-07-04 | | matlab, 图像处理, 数据结构 & 算法, 编码技巧, 音视频_图像相关

【matlab、c++、0.499】关于matlab和c++在浮点数转整数的问题 – 四舍五入已关闭评论

【Matlab、安装问题、路径问题、环境问题】安装完matlab后,出现各种命令未定义的情况

首次安装完matlab时,在导入授权后,打开发现一堆警告,各种命令不可用,大致内容如下:

Warning: C:\Program Files\MATLAB\R2012a\toolbox\local\pathdef.m not found.
Toolbox Path Cache is not being used. Type ‘help toolbox_path_cache’ for more info
Undefined function or variable ‘ispc’.
Warning: MATLAB did not appear to successfully set the search path. To recover for this session of MATLAB, type “restoredefaultpath;matlabrc”. To find out how to avoid this warning the next time you start MATLAB, type “docsearch problem path” after recovering for this session.
Warning: Duplicate directory name: C:\Program Files\MATLAB\R2012a\toolbox\local.
Warning: Initializing Handle Graphics failed in matlabrc.
This indicates a potentially serious problem in your MATLAB setup,
which should be resolved as soon as possible. Error detected was:
MATLAB:undefinedVarOrClass
Undefined variable “graphics” or class “graphics.internal.initializeMATLABRoot”.
Warning: Initializing Java preferences failed in matlabrc.
This indicates a potentially serious problem in your MATLAB setup,
which should be resolved as soon as possible. Error detected was:
MATLAB:UndefinedFunction
Undefined function ‘usejava’ for input arguments of type ‘char’.
> In matlabrc at 113
Warning: Failed to add default profiler filters.
> In matlabrc at 168
>> rtwintgt -setup
Undefined function ‘rtwintgt’ for input arguments of type ‘char’.

>> help toolbox_path_cache
Undefined function ‘help’ for input arguments of type ‘char’.

 

实际上是安装的时候路径出错,用管理员模式启动,然后执行这个命令:

restoredefaultpath;matlabrc

matlab执行环境变量恢复以后,系统正常可用。

2016-06-07 | | matlab, 图像处理, 数据结构 & 算法, 音视频_图像相关

【Matlab、安装问题、路径问题、环境问题】安装完matlab后,出现各种命令未定义的情况已关闭评论

【STL、C++】为减小编译后产生代码的体积做的一些妥协

好像从vs2010开始,vs自带的max宏就不再被推荐为C++中使用的首选,而是尽可能的改为std::max这个模板函数。

在effective c++中也讲到了max宏和std::max之间的差别(但有时使用起来,还是不如max宏来的方便,尤其是当max的入参不是同一个类型时。)

 

好了,说正事。

在vs2010中,std::max被定义为一个模板函数,其中函数的参数类型推导主要依赖于第一个参数;且std::max被inline修饰。在vs中,inline的强度并没有forceinline那么强,因此编译时,编译器即可能会让模板函数展开,也有可能不会让模板函数展开。

有时候有些开源项目中,大量的使用了std::max,这也会进一步的导致编译速度减慢,编译出来的文件变大;这里面除了inline还有一定的原因和模板的特性有关。

为了解决这类问题,有事不得不做出一些折中或妥协。即,当杜写一个公共函数,在该函数中将std::max进行特例化,以此来达到优化编译的目的。假设在不调整诸如fpo之类的优化参数时,编译器都会一定只会将std::max进行仅有的有限次实例化,且也可以控制函数是否进行inline。编译时不仅加快了编译速度,同时也减小了编译输出文件的大小。

所以在一些实际项目中,如果对编译产出的要求比较高,有时不得不牺牲代码设计和可阅读性来达到目的。

2016-04-18 | | win, 数据结构 & 算法, 编码技巧

【STL、C++】为减小编译后产生代码的体积做的一些妥协已关闭评论

如何做好程序的性能优化

本来标题想取名成 《如何做好代码的性能优化》,但发现如果仅仅说代码性能优化的话就太狭义了。

最近一年一直在单线程框架的工程上写代码,阅读框架代码以后,不禁感叹道:“这个框架的设计者不仅是个高手,而且对windows相当了解,甚至借鉴了windows内核里面的一些设计元素。”

首先介绍一下我手里的这个框架:

1,总体来说,整个程序几乎就是单线程+异步(对于DNS解析、IO操作等一些耗时或难以异步的模块,会另启一个线程去执行和管理)。

2,在这个单线程框架中,所有的业务、网络协议栈、数据处理都在挂在这个单线程中去运行,并且绝大对数情况和业务下面都能够很好的运行。

3,模块间通讯采取模拟异步/同步事件、异步/同步消息的方式来完成

4,数据通讯很简单,直接用堆内存传递,用完立即释放。

5,定时器是最简单的“轮询”方式实现(并非真正轮询)

 

现在遇到一个比较严重的问题,就是在这个单线程模型中,由于开发的时候存在编码人技能层次不齐,以及任务力度控制不均匀。

导致开发一些功能在获得执行时间时,执行时间太长或没有及时的将任务中断并将执行时间让给其他任务执行。

这样的现象导致最严重的问题,自身流程过长,效率不一定高(如果还依赖其他模块的执行结果)。并且其他模块不能及时的拿到执行时间,并将执行结果及时反馈。进而引起血崩效应,导致部分要求时效性高的功能出现问题。

 

为了解决这类问题,就要做程序性能上的优化。这个问题上,一般采取的优化策略有几种:

1,代码级优化,就是通过各种技巧,将本来执行效率低的代码进行一点一点的修改并加快。这种优化方式周期长,效果不见得很明显,但对于长久来说是具备一定好处的;可以让优化者能够熟悉和了解整个代码的运行情况和流程等。

2,业务/功能优化,通过将长流程或者耗时的流程将功能和业务优化掉。然长流程变成短流程,然后进而增加执行时间在任务中的切换频率。可以促进轻量级任务的提早执行和结束,也间接能够提高大部分任务的及时性。但对于原本又长又臭的任务来说,此类优化可能带来的改善并不大,同时还需要优化者对程序整体有一定度的把握。

3,任务分拆,这样优化方式是将任务的关联性和时效性做一个定性分析。将相关任务集中起来,不相关任务分拆开;并将任务流中的上下游进行松耦,接着再对相关的业务进行松耦。这样做的好处在于一切以任务执行为视角,进行分拆,可以有效的区分开重任务和轻任务。同样也可以定性的了解到即使性要求高的任务和及时性要求低的任务。缺点在于,优化者同样也要对整个程序有一定的了解。

4,框架优化。这个难度大,没有做太大分析。

 

因为1和2都是夹杂着代码上技巧性的优化,这种优化如果考虑不当很有可能事倍功半,反而降低代码的可阅读性和可维护性。之前,我就遇到过一些成天嚷嚷着“算法”的人在用“算法”的思维去优化代码,结果代码优化下来性能是有一定的改善,但可维护性和可阅读性就差到极点了。甚至优化者本人自己去维度代码也是满天飞的bug。

介于4这种都是构架师水平,我最终选择3。

从任务的关联性出发,将一些重任务,以及及时性要求高的任务进行分类,并把这些任务的旁路任务进行一同整理。最终得到几类任务:

1,一般任务

2,及时性高任务

3,重任务

 

其中一般任务继续保留在原先的单线程框架中。及时性高的任务会从中剥离出来,并挂在一个新的单线程框架中;后期随着这个单线程任务量的增加,最终线程会逐步调整代码中的线程数。

重任务,其中重任务也被挂在一个新的单线程框架中,处理方式与及时性任务的处理方式一致。只不过对于及时性高的任务,可能还需要做一些代码层面上的执行优化,不过应该不多。

 

通过上面的方案进行优化了以后,发现整个客户端任务执行的拖沓、任务切换的不及时得到了较大的改善。看来改善任务安排有时候比起用一些代码技巧更为重要。

 

当然,我在这里说说是很容易的,实际写起代码来未必那么容易。因为涉及到多线程,就需要留意任务的关联性。因为关联性的存在,就会出现线程资源竞争,资源出现竞争时,就会很容易出现数据不同步,死锁,野指针等问题。

这是就需要经验和一定的代码技巧来解决这类问题。因此合理调整程序结构与代码技巧同样重要,如果一味的追求代码技巧和所谓的“算法”,那最终会失去对整个程序的可持续维护和开发的可能。这就如我之前所呆的一家公司一样,软件在国内某行业里还是有点小名气,但是真的要去看代码的话…………………bug、可阅读性不是在人类可理解范围内。反而这个团队内总有人一味的强调“算法”、“二叉树”什么的,数据结构与算法确实是程序的核心之一的东西,但现在国内的公司并非科研机构,顶多只能算一个做的工程。多数时候其实以工程的思维就能把问题解决好的,根本没有必要上升到“算法”层面,再说了,代码都没写好装什么逼呢?

2015-08-01 | | win, windbg, 数据结构 & 算法, 算法导论, 编码技巧

如何做好程序的性能优化已关闭评论

折半查找与二叉树的对应

折半查找的前提是,数列需要是有序的。
有这么一个数组:【10, 11, 100, 200, 232, 245, 246, 400】
需要进行查找 10 这个元素
2014-01-07 | | 数据结构 & 算法

折半查找与二叉树的对应已关闭评论