png的故事:隔行扫描算法

Posted by

png的故事:隔行扫描算法

2017/06/21 · 基础技术 ·
PNG

原文出处:
AlloyTeam/june01   

png的故事:获取图片信息和像素内容

2017/03/25 · JavaScript
· 1 评论 ·
PNG

原文出处:
AlloyTeam   

前言

前文已经讲解过如何解析一张png图片,然而对于扫描算法里只是说明了逐行扫描的方式。其实png还支持一种隔行扫描技术,即Adam7隔行扫描算法。

前言

现在时富媒体时代,图片的重要性对于数十亿互联网用户来说不言而喻,图片本身就是像素点阵的合集,但是为了如何更快更好的存储图片而诞生了各种各样的图片格式:jpeg、png、gif、webp等,而这次我们要拿来开刀的,就是png。

优劣

使用隔行扫描有什么好处呢?如果大家有去仔细观察的话,会发现网络上有一些png图在加载时可以做到先显示出比较模糊的图片,然后逐渐越来越清晰,最后显示出完整的图片,类似如下效果:图片 1

这就是隔行扫描能带来的效果。隔行扫描一共会进行1到7次扫描,每一次都是跳着部分像素点进行扫描的,先扫描到像素点可以先渲染,每多一次扫描,图片就会更清晰,到最后一次扫描时就会扫描完所有像素点,进而渲染出完整的图片。

当然,也因为要进行跳像素扫描,整张图片会存储更多额外数据而导致图片大小会稍微变大,具体增加了什么额外数据下文会进行讲解。

简介

首先,png是什么鬼?我们来看看wiki上的一句话简介:

Portable Network Graphics (PNG) is a raster graphics file format that
supports lossless data compression.

也就是说,png是一种使用无损压缩的图片格式,而大家熟知的另外一种图片格式——jpeg则是采用有损压缩的方式。用通俗易懂的方式来讲,当原图片数据被编码成png格式后,是可以完全还原成原本的图片数据的,而编码成jpeg则会损耗一部分图片数据,这是因为两者的编码方式和定位不同。jpeg着重于人眼的观感,保留更多的亮度信息,去掉一些不影响观感的色度信息,因此是有损耗的压缩。png则保留原始所有的颜色信息,并且支持透明/alpha通道,然后采用无损压缩进行编码。因此对于jpeg来说,通常适合颜色更丰富、可以在人眼识别不了的情况下尽可能去掉冗余颜色数据的图片,比如照片之类的图片;而png适合需要保留原始图片信息、需要支持透明度的图片。

以下,我们来尝试获取png编码的图片数据:

生成

要导出一张基于Adam7隔行扫描的png图片是非常简单,我们可以借助Adobe的神器——PhotoShop(以下简称ps)。我们把一张普通的图片拖入到ps中,然后依次点选【文件】-【存储为Web所用的格式】,在弹出的框里选择存储为PNG-24,然后勾选交错,最后点击存储即可。

这里的交错就是只将扫描算法设为Adam7隔行扫描,如果不勾选交错,则是普通逐行扫描的png图片。

结构

图片是属于2进制文件,因此在拿到png图片并想对其进行解析的话,就得以二进制的方式进行读取操作。png图片包含两部分:文件头和数据块。

原理

Adam7隔行扫描算法的原理并不难,本质上是将一张png图片拆分成多张png小图,然后对这几张png小图进行普通的逐行扫描解析,最后将解析出来的像素数据按照一定的规则进行归位即可。

文件头

png的文件头就是png图片的前8个字节,其值为[0x89, 0x50, 0x4E, 0x47, 0x0D, 0x0A, 0x1A, 0x0A],人们常常把这个头称之为“魔数”。玩过linux的同学估计知道,可以使用file命令类判断一个文件是属于格式类型,就算我们把这个文件类型的后缀改得乱七八糟也可以识别出来,用的就是判断“魔数”这个方法。有兴趣的同学还可以使用String.fromCharCode将这个“魔数”转成字符串看看,就知道为什么png会取这个值作为文件头了。

用代码来判断也很简单:

JavaScript

// 读取指定长度字节 function readBytes(buffer, begin, length) {
    return Array.prototype.slice.call(buffer, begin, begin + length); }
  let header = readBytes(pngBuffer, 0, 8); // [0x89, 0x50, 0x4E, 0x47,
0x0D, 0x0A, 0x1A, 0x0A]

1
2
3
4
5
6
// 读取指定长度字节
function readBytes(buffer, begin, length) {
    return Array.prototype.slice.call(buffer, begin, begin + length);
}
 
let header = readBytes(pngBuffer, 0, 8); // [0x89, 0x50, 0x4E, 0x47, 0x0D, 0x0A, 0x1A, 0x0A]

分析

在解压缩完图像数据后就要马上进行拆图。拆图并不难,就是将原本存储图像数据的Buffer数组拆分成多个Buffer数组而已。关键的问题是怎么拆,这时我们先祭上wiki上这张图:

图片 2

上面这张图就说明了每次扫描需要扫描到的像素,正常来说一张基于Adam7隔行扫描的png图片是要经历7次扫描的,不过有些比较小的图片的实际扫描次数不到7次,这是因为有些扫描因为没有实际像素点而落空的原因,所以下面的讲解还是以标准的7次扫描来讲解,本质上此算法的代码写出来后,是能兼容任何大小的png图片的,因为算法本身和图片大小无关。

7次扫描,其实就回答了上面拆图的问题:要拆成7张小图。每张小图就包含了每次扫描时要归位的像素点。

以第一次扫描为例:第一次扫描的规则是从左上角(我们设定此坐标为(0,0))开始,那么它扫描到的下一个点是同一行上一个点往右偏移8个像素,即(8,0)。以此类推,再下一个点就是(16,0)、(24,0)等。当当前行所有符合规则的点都扫描完时则跳到下一个扫描行的起点,即(8,0),也就是说第一次扫描的扫描行也是以8个像素为偏移单位的。直到所有扫描行都已经扫描完成,我们就可以认为这次扫描已经结束,可以考虑进入第二次扫描。

我们以一张10*10大小的png图片来举例,下面每个数字代表一个像素点,数字的值代表这个点在第几次扫描时被扫描到:

JavaScript

1 6 4 6 2 6 4 6 1 6 7 7 7 7 7 7 7 7 7 7 5 6 5 6 5 6 5 6 5 6 7 7 7 7 7 7
7 7 7 7 3 6 4 6 3 6 4 6 3 6 7 7 7 7 7 7 7 7 7 7 5 6 5 6 5 6 5 6 5 6 7 7
7 7 7 7 7 7 7 7 1 6 4 6 2 6 4 6 1 6 7 7 7 7 7 7 7 7 7 7

1
2
3
4
5
6
7
8
9
10
1 6 4 6 2 6 4 6 1 6
7 7 7 7 7 7 7 7 7 7
5 6 5 6 5 6 5 6 5 6
7 7 7 7 7 7 7 7 7 7
3 6 4 6 3 6 4 6 3 6
7 7 7 7 7 7 7 7 7 7
5 6 5 6 5 6 5 6 5 6
7 7 7 7 7 7 7 7 7 7
1 6 4 6 2 6 4 6 1 6
7 7 7 7 7 7 7 7 7 7

按照规则,在第一次扫描时我们会扫描到4个像素点,我们把这4个像素点单独抽离出来合在一起,就是我们要拆的第一张小图:

JavaScript

(1) 6 4 6 2 6 4 6 (1) 6 7 7 7 7 7 7 7 7 7 7 5 6 5 6 5 6 5 6 5 6 7 7 7 7
7 7 7 7 7 7 1 1 3 6 4 6 3 6 4 6 3 6 ==> 1 1 7 7 7 7 7 7 7 7 7 7 5 6 5
6 5 6 5 6 5 6 7 7 7 7 7 7 7 7 7 7 (1) 6 4 6 2 6 4 6 (1) 6 7 7 7 7 7 7 7
7 7 7

1
2
3
4
5
6
7
8
9
10
(1)  6   4   6   2   6   4   6  (1)  6
7   7   7   7   7   7   7   7   7   7
5   6   5   6   5   6   5   6   5   6
7   7   7   7   7   7   7   7   7   7                   1 1
3   6   4   6   3   6   4   6   3   6        ==>        1 1
7   7   7   7   7   7   7   7   7   7
5   6   5   6   5   6   5   6   5   6
7   7   7   7   7   7   7   7   7   7
(1)  6   4   6   2   6   4   6  (1)  6
7   7   7   7   7   7   7   7   7   7

也就是说,我们的第一张小图就是2*2大小的png图片。后面的小图大小以此类推,这样我们就能得知拆图的依据了。

数据块

去掉了png图片等前8个字节,剩下的就是存放png数据的数据块,我们通常称之为chunk

顾名思义,数据块就是一段数据,我们按照一定规则对png图片(这里指的是去掉了头的png图片数据,下同)进行切分,其中一段数据就是一个数据块。每个数据块的长度是不定的,我们需要通过一定的方法去提取出来,不过我们要先知道有哪些类型的数据块才好判断。

拆图

上面有提到,拆图本质上就是把存放图片数据的Buffer数组进行切分,在nodejs里的Buffer对象有个很好用的方法——slice,它的用法和数组的同名方法一样。

直接用上面的例子,我们的第一张小图是2*2点png图片,在假设我们一个像素点所占的字节数是3个,那么我们要切出来的第一个Buffer子数组的长度就是2*(2*3+1)。也许就有人好奇了,为什么是乘以2*3+1而不是直接乘以2*3呢?之前我们提到过,拆成小图后要对小图进行普通的逐行扫描解析,这样解析的话每一行的第一个字节实际存放的不是图像数据,而是过滤类型,因此每一行所占用的字节需要在2*3的基础上加1。

数据块类型

数据块类型有很多种,但是其中大部分我们都不需要用到,因为里面没有存储我们需要用到的数据。我们需要关注的数据块只有以下四种:

  • IHDR:存放图片信息。
  • PLTE:存放索引颜色。
  • IDAT:存放图片数据。
  • IEND:图片数据结束标志。

只要解析这四种数据块就可以获取图片本身的所有数据,因此我们也称这四种数据块为“关键数据块”

像素归位

其他的小图拆分的方法是一样,在最后一次扫描完毕后,我们就会拿到7张小图。然后我们按照上面的规则对这些小图的像素进行归位,也就是填回去的意思。下面简单演示下归位的流程:“

JavaScript

(1) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (1) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) 1 1 ==> ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (
) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (
) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (1) ( ) ( ) ( ) ( ) ( ) (
) ( ) (1) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )

1
2
3
4
5
6
7
8
9
10
                  (1) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (1) ( )
                  ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
                  ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
1 1              ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
1 1     ==>      ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
                  ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
                  ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
                  ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
                  (1) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (1) ( )
                  ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )

待到7张小图的像素全部都归位后,最后我们就能拿到一张完整的png图片了。

数据块格式

数据块格式如下:

描述 长度
数据块内容长度 4字节
数据块类型 4字节
数据块内容 不定字节
crc冗余校验码 4字节

这样我们就可以轻易的指导当前数据块的长度了,即数据块内容长度 + 12字节,用代码实现如下:

JavaScript

// 读取32位无符号整型数 function readInt32(buffer, offset) {     offset
= offset || 0;     return (buffer[offset] << 24) +
(buffer[offset + 1] << 16) + (buffer[offset + 2] << 8) +
(buffer[offset + 3] << 0); }   let length =
readInt32(readBytes(4)); // 数据块内容长度 let type = readBytes(4); //
数据块类型 let chunkData = readBytes(length); // 数据块内容 let crc =
readBytes(4); // crc冗余校验码

1
2
3
4
5
6
7
8
9
10
// 读取32位无符号整型数
function readInt32(buffer, offset) {
    offset = offset || 0;
    return (buffer[offset] << 24) + (buffer[offset + 1] << 16) + (buffer[offset + 2] << 8) + (buffer[offset + 3] << 0);
}
 
let length = readInt32(readBytes(4)); // 数据块内容长度
let type = readBytes(4); // 数据块类型
let chunkData = readBytes(length); // 数据块内容
let crc = readBytes(4); // crc冗余校验码

这里的crc冗余校验码在我们解码过程中用不到,所以这里不做详解。除此之外,数据块内容长度和数据块内容好解释,不过数据块类型有何作用呢,这里我们先将这个type转成字符串类型:

JavaScript

// 将buffer数组转为字符串 function bufferToString(buffer) {     let str
= ”;     for(let i=0, len=buffer.length; i<len; i++){         str +=
String.fromCharCode(buffer[i]);     }     return str; }   type =
bufferToString(type);

1
2
3
4
5
6
7
8
9
10
// 将buffer数组转为字符串
function bufferToString(buffer) {
    let str = ”;
    for(let i=0, len=buffer.length; i<len; i++){
        str += String.fromCharCode(buffer[i]);
    }
    return str;
}
 
type = bufferToString(type);

然后会发现type的值是四个大写英文字母,没错,这就是上面提到的数据块类型。上面还提到了我们只需要解析关键数据块,因此遇到type不等于IHDR、PLTE、IDAT、IEND中任意一个的数据块就直接舍弃好了。当我们拿到一个关键数据块,就直接解析其数据块内容就可以了,即上面代码中的chunkData字段。

相关文章

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注