独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

时间:2022-10-04 07:13:11

前言

  • 此文我首发于CSDN(所以里面的图片有它的水印)
  • 趁着隔离梳理一下之前做的一个有用的功能:在浏览器中去切割多分辨率瓦片图
  • 这是一个有趣的过程,跟我一起探索吧
  • 阅读本文需具备前置知识:对krpano有所了解,如:使用krpano去开发全景

本着故弄玄虚的原则,最精彩的会放到最后揭晓,由浅入深,层层递进!


1.功能简介

  1. 减轻服务器压力,krpano切图比较消耗CPU和内存,我们团队的服务器曾经因为太多人同时切图导致卡顿、宕机
  2. 提升切图速度,在js切图速度会比后端快,前端切图与后端切图可以同时使用,这样切图速度可以快100%以上
  3. 无水印,krpano是需要花钱注册的,没有注册的情况下去切图会有无数水印,使用本工具可以解决这个问题
  4. 提升用户体验,立方体切图仅需要几秒钟,在移动端APP中,切图可以立马生成全景且仅保留在本地,点击保存的时候才上传到云端
  5. ......

DEMO: https://irispro.github.io/krpanoJSToolDemo/dist/index.html
GitHub源码地址:https://github.com/IrisPro/KrpanoToolJS
NPM地址:https://www.npmjs.com/package/@krpano/js-tools

2.回顾krpano切图

  • 在以往,咱们最常用的切图方式是使用krpanotools命令行工具在服务器切图,如果是手动切图的话,就会在本地使用 MAKE VTOUR (MULTIRES) dropletMAKE VTOUR (NORMAL) droplet,在1.20开始使用krpano Tools应用程序可以进行可视化操作,除了切图外,还能方便还原全景图。

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

3.krpano切图最常用的方式

  • 第一,普通切图,即立方体切图,将全景图切为上、下、左、右、前、后6张图。优点:切图速度快,占用存储少。缺点:场景启动时间不够快,放大模糊。
  • 第二,多分辨率切图,跟瓦片地图原理类似。优点:启动速度快,图片清晰。缺点:占用存储较多,切图时间较久,一般用于航拍、风景等大范围场景的需求,室内样板间预览,几乎不太需要。比较著名的应用案例大家可以看看720云上的何同学六百万粉丝合影,这一个场景的图片超过了百万张。在地图领域中是必用的技术.(如此就能够根据不同的缩放等级来显示不同的清晰度的图像,这样的好处是如果要加载一张4k的全景图,不需要一次性就将整个全景图都加载进来,可以先加载一个缩放等级低的全景,然后当使用者进行缩放查看细节的时候再加载清晰度更高的图像,这样就可以明显提高加载速度,避免因为图片过大使得加载时间过长和不必要的流量浪费。不足之处就是需要为一张全景图额外准备不同清晰度的图片,增加了图片处理的工作量,也增加了图片存储的空间占用。)

4.瓦片地图金字塔模型

瓦片地图金字塔模型是一种多分辨率层次模型,从瓦片金字塔的底层到顶层,分辨率越来越低,但表示的地理范围不变。首先确定地图服务平台所要提供的缩放级别的数量N,把缩放级别最高、地图比例尺最大的地图图片作为金字塔的底层,即第0层,并对其进行分块,从地图图片的左上角开始,从左至右、从上到下进行切割,分割成相同大小(比如256x256像素)的正方形地图瓦片,形成第0层瓦片矩阵;在第0层地图图片的基础上,按每像素分割为2×2个像素的方法生成第1层地图图片,并对其进行分块,分割成与下一层相同大小的正方形地图瓦片,形成第1层瓦片矩阵;采用同样的方法生成第2层瓦片矩阵;…;如此下去,直到第N一1层,构成整个瓦片金字塔。
独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

  • 其实,krpano多分辨率就是借鉴这种原理。

正片开始


5.前置知识介绍:ImageData


  • ImageData是图片的数据化,保存了图片每个像素的信息,它有以下属性:

    • data:包含图像隐藏像素的 Uint8ClampedArray 数组。如果数组没有给定,指定大小的黑色矩形图像将会被创建。
    • width: 描述图片宽度
    • height:描述图片高度
  • ImageData中的data,是一个数组,每四个元素描述一个像素,分别表示rgba,所以一张100x100px的图片,data的数组长度为 100 x 100 x 4 = 40000。我们平时用全景图渲染精度一般在10000点~20000点。

  • data数组会随着分辨率的提高指数级增长,如10000x10000的全景图与20000*20000的全景图,前者数组长度为4亿,后者16亿。所以,在处理ImageData的时候,如此复杂的计算,我们需要使用多线程技术web worker,否则会阻塞渲染进程。

  • canvas这个就不多介绍了,大家都懂。

6.普通切图(立方体切图)


其实切立方体图网上很多现成的方案,难点在于如何切瓦片图。
我使用了现成的方案,在我仓库地址中最底部有提及。

原理:将输入的图片使用canvas画出来,然后转为ImageData,通过球体转立方体的算法,将对应像素映射到每一个面上,最终再通过ImageData转回图片。

https://jaxry.github.io/panorama-to-cubemap/

demo中有三个选项:

  • Liner(柔和的细节)
  • Cubic(锋利的细节,我选择这一种,与krpano一致)
  • Lanczos(画质最好,耗时是第二种的3.5倍,太耗时且结果肉眼感知不明显)

7.多分辨率瓦片图算法(重头戏)


01.通过krpano切图结果推理多分辨率切图高清的原因

一张全景图,可以切出几百上千张碎图,越放大就越清晰,并且初次缩放和旋转场景,可以看到控制台一直在加载图片。

首先,我们来看看krpano切出来的图片的目录结构:

(图一)多分辨率切图:

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

(图二)普通切图:

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

普通切图我们好理解。除了preview.jpg和thumb.jpg,其它以pano_开头的图片都代表立方体其中一个面。

通过对比,我猜测多分辨率每一个文件夹对应立方体每一个面。

为了探究这些碎图是什么东西,我打开Photoshop,将图一中文件夹b->l1里面文件夹的图片都放在画布中,如下图三所示:

图三:

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

紧接着,我把剩下l2、l3文件夹里面的所有图片,按照上文同样的操作,放在Photoshop中把图片合并,惊奇地发现l1、l2、l3这三个文件夹每个文件夹合并的图片都是一样的,除了分辨率不一样以外,分辨率等级:l3 > l2 > l1,层级越高分辨率越高。如下图所示:

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

02.小结krpano切图规律

  1. 每一面图片的多个文件夹(l1、l2、l3)代表多张不同分辨率的图片
  2. 文件夹名称l1、l2、l3,其中的英文字母l是level的缩写,数字代表图片的层级
  3. 每一层级里面的文件夹表示这张图片的第几行,按顺序把每一行都拼起来就可以变成一面完整的图
  4. 多分辨率瓦片图高清的原因:普通切图分辨率为2048x2048,而的分辨率切图最高分辨率可以达到3200x3200,分辨率越高肯定越清晰

03.算法思路推理与实现

小思路:

  1. 每一面的图片我们可以通过普通切图拿到
  2. 把每一面的图使用canvas转成不同分辨率的图片,然后逐行对它进行切割

问题:

  1. 一张全景图需要分多少层级?
  2. 每一层级的分辨率是多少?
  3. 每一张瓦片图的最大尺寸和最小尺寸是多少?

为了能找出规律,我制作了非常多不同分辨率的全景图,使用krpano Tools去切图,并根据输出记录不同分辨率的层级、每一层级的分辨率,试图找出他们的规律。

如图所示,这是krpano Tools 1.20.10:

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

从上图中可以发现,每次切图的时候控制台会输出几个参数:

  • 全景图的分辨率
  • 一共多少层级,如图中所示 levels=3,表示有3个层级
  • 每一层级的分辨率,如图中所示,3200x3200 1664x1664 768x768,由高到低

根据这些数据,我制成了一个表格:

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

为了让样本更具参考意义,全景图的分辨率我从1000x500 一直到 60000x30000。
为什么知道了6万就不往上测试了呢?因为我电脑Photoshop的极限就在这里了,没办法输出更高分辨率的图片了,从10个样本中,我依旧可以得出以下规律:

  1. 相邻层级分辨率之比约等于 2,波动为0.2
  2. 全景图的分辨率与最高层级的分辨率之比为 3.125 ,几乎所有都一样,仅有一个波动为0.012

3.125 这个数值我会把它当成一个突破口,
即最高层级图片的分辨 = 全景图分辨率 / 3.125。

接着我查看vtour-multtires.config文件,即多分辨率切图的配置文件,这是一份krpano Tools默认的配置文件,可以手动去修改切图的配置。一般几乎不会去改动这里,我们团队生产过几十万个场景都没有改过这里,所以默认的配置已经是符合绝大部分使用场景。故,我把其中的配置作为标准来参考。

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

以下仅列举了部分配置,完整配置可以参考krpano官网文档

// 多分辨率切图配置
multires=true //  是否是多分辨率
tilesize=512 // 瓦片图大小
levels=auto // 自动层级
levelstep=2 // (重点)每一层与上一层
maxsize=auto // 最高层级分辨率(自动计算)
maxcubesize=auto // 每一面最大的尺寸
stereosupport=true 
adjustlevelsizes=true // 允许调节每一层级的尺寸
adjustlevelsizesformipmapping=true
<!-- XML中image节点信息 -->
<image>
	<cube url="panos/IMG_1914.tiles/%s/l%l/%0v/l%l_%s_%0v_%0h.jpg" multires="512,1024,2048,3840,7680" />
</image>

再通过官网,查看 cube节点的multires属性,第一个值表示单张瓦片图的大小。

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

既然单张瓦片图尺寸是512,那我就打开查看生成的图片,看看到底是不是。
结果发现:几乎所有的图片都是512x512,除了最后一张图片和最后一行。

官网对tilesize=auto的解读:

  • Size of the multi-resolution tile images.
  • Should be between 256 and 1024.
  • When using 'auto' the tool will automatically try find a good value for 'symmetric tile splitting'.
  • The today recommendation for best rendering performance is using 512 as tilesize.
  • It's a good compromise between the GPU-texture-upload-time and the number of GPU-draw-calls required to fill the screen.
  • Note - the tilesize affects the loading and decoding time and also the rendering performance.

得知:

  • 瓦片图大小在256 - 1024之间
  • 性能最好的是512。这也是krpano强大和严谨之处,他经过大量测试的出来的结果。

另一个属性:levelstep=2

  • 表示每一层与相邻一层的比为 2

到此,我们先整理一下已知信息:

  • 瓦片图的大小为512x512,但最后一行或者每行的最后一列可能不是512
  • 最高层级分辨率 = 全景图 / 3.125
  • 每一层级的分辨率与相邻层级的比为 2

虽然官方说瓦片图尺寸为256-512,但是看官方切出来的图片,最后一行很多都小于256。我通过大量样本分析,最小值为64。那么我给瓦片图尺寸的定义为:大小为64-512,优先切512的图片,最后假设不足512但也不能小于64。

每一层级的宽度 % 512 % 64 = 0

经过验证,krpano所有切图都满足这样的条件。

如果余数不为零,那咋办?同样经过大量样本推算,如果余数小于64,则舍弃,即当前层级的分辨率要减去这个余数,如果余数大于64,则相加。

这时候我简单写一条算法来计算一下我的猜想:

// 设全景图大小为10000x5000
const panoSize = 10000
// 系数,瓦片图最高层级的尺寸 = 图片宽度 / 系数
const coefficient = 3.125
// 瓦片图最大尺寸
const maxTileSize = 512
// 瓦片图最小尺寸
const minTileSize = 64
// 相邻层级的比
const levelstep = 2

// 调整层级的尺寸:控制 faceSize % 512 % 64 = 0
function adjustLevelSize(inputLevelSize: number) {

    if (inputLevelSize % maxTileSize % minTileSize === 0) return inputLevelSize

    const lastTileSize = inputLevelSize % maxTileSize

    // 最后一行小于64则舍弃
    if (lastTileSize < minTileSize) {
        inputLevelSize -= lastTileSize
    } else {
        //  最后一行瓦片的余数(对64取余)
        const minRemainder = lastTileSize % minTileSize
        if (minRemainder !== 0) {
            inputLevelSize = inputLevelSize - (minTileSize - minRemainder)
        }
    }
    return inputLevelSize
}

// 最高层级(余数为0)
let levelSize1 = panoSize / coefficient // levelSize1 = 3200
levelSize1 = adjustLevelSize(levelSize1) // levelSize1 = 3200

// 下一级(余数为0)
let levelSize2 = levelSize1 / levelstep // levelSize2 = 1600
levelSize2 = adjustLevelSize(levelSize2) // levelSize2 = 1600

// 下一级(余数为32,800 % 512 % 64 = 32,舍弃,故levelSize3 = 800 - 32 = 768)
let levelSize3 = levelSize2 / levelstep // levelSize3 = 800
levelSize3 = adjustLevelSize(levelSize3) // levelSize3 = 768

...

// 官方1万-1.5万像素的,只有三个层级,故切到第三层,那我就不能再切了,我得找出最低层级的最小分辨率。

通过以上的计算,同一张全景图我的算法与krpano切图进行对比:

level 我的算法 krpano算法
3 3200 3200
2 1600 1664
1 768 768

第二层级虽然有64像素的差距,但是我遵循的是层级比为2,krpano第二层级偶尔会略大或者略小,其实这是动态计算的,前面也有讲,几乎约等于2,在正常波动内,所以这没问题。

2万px以内的全景图,每隔1000px我都测试一下,发现没有问题,完全可用。

04.最终算法实现

analyzeImageLevel(panoWidth: number) {

    // 系数,瓦片图最高层级的尺寸 = 图片宽度 / 系数
    const coefficient = 3.125
    // 瓦片图最大尺寸
    const maxTileSize = 512
    // 瓦片图最小尺寸
    const minTileSize = 64

    // 调整层级的尺寸:控制 faceSize % 512 % 64 = 0
    function adjustLevelSize(inputLevelSize: number) {

        if (inputLevelSize % maxTileSize % minTileSize === 0) return inputLevelSize

        const lastTileSize = inputLevelSize % maxTileSize

        // 最后一行小于64则舍弃
        if (lastTileSize < minTileSize) {
            inputLevelSize -= lastTileSize
        } else {
            //  最后一行瓦片的余数(对64取余)
            const minRemainder = lastTileSize % minTileSize
            if (minRemainder !== 0) {
                inputLevelSize = inputLevelSize - (minTileSize - minRemainder)
            }
        }
        return inputLevelSize
    }

    function getLevelConfig(panoSize): ILevelConfig[] {
        let count = 1
        let levels = []
        const minFaceSize = 640
        const topLevelSize = panoSize / coefficient

        // 最高层
        levels.push({
            level: count,
            size: adjustLevelSize(topLevelSize)
        })

        getNextLevelConfig(topLevelSize)

        // 递归获取子层级
        function getNextLevelConfig(topLevelSize) {
            const levelstep = 2
            const nextLevelSize = topLevelSize / levelstep
            if (nextLevelSize + minTileSize >= minFaceSize) {
                count++
                levels.push({
                    level: count,
                    size: adjustLevelSize(nextLevelSize)
                })
                getNextLevelConfig(nextLevelSize)
            }
        }

        // 层级转为正常从小到大
        levels = levels.map((item, index) => {
            item.level = levels.length - index
            return item
        })
        return levels
    }

    this.levelConfig = getLevelConfig(panoWidth)
}

8.利用canvas分割图片

上面我们推算出了算法,得到了这样的数据:

// 层级数
// 每一层级的分辨率
let levelConfig = [
    {
        level: 1,
        size: 768,
    },
    {
        level: 2,
        size: 1600,
    },
    {
        level: 3,
        size: 3200,
    },
]

把一张图按照一定的规律风格成碎图,这很简单,不在这里详细展开,否则篇幅太长,可以去网上搜索或者我到时候单独写个文章。

9.如何在生成目录结构和下载?


大家在使用我的DEMO的时候可以发现,你传一张全景图上去,我可以在浏览器给你直接下载整个压缩包,并且里面已经分好层级和目录结构。

如图所示,这是我在浏览器生成的:

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

01.JSZip

  • 这时候,我给大家推荐一个非常好用的浏览器压缩与解压工具JSZip官方文档。效率高,速度快,压缩2G以内的非常快,有一次我压缩3700张图片,每张1m,这是内存就爆满了,不过这种极限条件下一般遇不到,解决方法也很简单,分块上传。

  • 他可以让我们很方便的去压缩文件上传到服务器,在前端压缩文件再传到后端的优势是可以极大减少请求数量,比如上传1000张需要1000个请求,压缩成一个文件仅需要一个请求,并且大文件上传速度比传碎文件速度快。

  • 做这个demo遇到很多问题:

    • Mac上unix可执行文件压缩就再解压,就不是可执行文件了,因为在Mac中可执行文件其实就是可以使用普通文稿去生成,暂时无解;
    • 在vite构建工具中,如果文件放到了assets中,打包之后的文件会带上hash,导致场景无法预览,如果放在public中又无法使用import,巧妙的解决方法:把所有需要放在assets中的打包成一个压缩包,单独导入这个压缩包,再把它解压,最终合并到zip实例中去;
    • ...

02.file-saver

下载的话,我也推荐一个好用的库,file-saver源码链接。下载文件其实很简单,但是如果有非常好用、稳定的库,那直接用就得了,不用自己写。

在早期,关于文件的操作,我都是交给后端来处理,我调接口。但现在不一样,这两个库给了我无限的想象空间,很多东西我可以在前端去组装去做,然后再统一给到后端。

10.生成预览图 preview.jpg


前面最核心都做完了,这个小图片岂能难道我?果不其然!!!

进入场景前会先加载预览图,等场景图片加载完后才显示原图,这样可以提升场景加载速度并且不会耗费太多资源。

预览图如下,是一张分辨率为256x1536的长条图。它生成的方式是立方体的六个面,按照「左、前、右、后、上、下」,自上而下拼接成。

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

我就是这样去合成的,我测试的时候把场景image节点隐藏掉,仅加载预览图,发现没问题很完美。

错就错在我是一个特别细心的人,如下图,我发现我合成的图片体积有221kb,而krpano才77kb,体积整整比它大了三倍啊。这里面到底暗藏了什么玄机?

独辟蹊径:逆推Krpano切图算法,实现在浏览器切多层级瓦片图

通过对比,我们可以直观的看出来,我的图片要比krpano清晰的,它的图片略带模糊,但是其实观感并不差,过渡都非常平滑。

那么我推测,让图片变得模糊可以大大降低图片体积,这跟我们平时压缩图片还有点不太一样,压缩图片主要是减少冗余像素,压缩率太高图片观感会比较差。

这时候,我又看了配置文件vtour-multries.config

# preview pano settings
preview=true
graypreview=false
previewsmooth=25
previewpath=%OUTPUTPATH%/panos/%BASENAME%.tiles/preview.jpg

其中有一个属性叫做:previewsmooth

瞬间明白了,krpano是给它做了一个平滑处理。仔细想想,上面已经说了场景的预览图是为了提升加载速度和平滑过渡到原图。那么,第一预览图的体积就不能太大。第二,如果预览图没有做平滑处理的话,加载之后看起来会颗粒感比较严重,影响观感。此刻很想再说一声Krpano YYDS...

所以,我也需要对预览图进行平滑处理。

图片平滑处理的方式常见的有这几种:

  • 均值平滑
  • 高斯平滑
  • 中值平滑

通过对比这几种效果,比较符合的是高斯平滑,其实就是咱们平时所说的高斯模糊

11.缩略图thumb.jpg

krpano已经做到极致了。

krpano的缩略图一般只有17kb左右,但却如此清晰,观感也很好。

如果我用高斯模糊的话,会显得不清晰,可能它应该经过其它的处理。我考虑到缩略图的使用场景,认为没必要深究缩略图,它的作用仅用来示意。使用我demo切出来的图,相信你们也看不出差别。

12总结:

01.技术上,我们需要了解:

  1. 核心点在于推理出krpano多分辨率切图的算法
  2. canvas 2d
  3. ImageData
  4. web worker
  5. 高斯模糊
  6. 善用jszip
  7. file-saver

02.对于krpano的评价

  1. 我仅仅是实现krpano的部分功能,不难发现krpano做的非常好,很多细节都考虑得很到位,并且自身也做过很多测试;
  2. krpano的价格其实并不贵,一次注册终身免费,并且我们使用的10年来,它一直在迭代;
  3. ...

03.为什么我要做这个功能?

  1. 这一定是从用户体验出发,从产品出发,从业务中来,再去思考如何与技术结合;
  2. 有点在开篇已经提过了,有一定的使用场景;

04.我为什么能够去完成它呢?

  1. 因为这不是一个KPI项目,不是一个公司项目,不是团队规划的需求,而是我自己的项目,但它的起因也是源于业务中遇到的问题;
  2. 如果在公司中,一个功能埋头2天没有头绪,那么大概已经想要放弃了,因为会有期限给你施加压力。而我自己业余项目,是每隔一段时间就去想想、看看,一步一步去找规律、求证、验证、测试,尽量成功,失败也无所谓;
  3. 做任何事情都需要耐心、沉着冷静

05.如何还原全景图?

  1. 这是后面再把它做到krpano-js-tools里面,敬请期待;
  2. 我的做法不完全沿用现在的做法,会使用 webgl,使用webgl做全景,业界的标杆是贝壳找房