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

独辟蹊径：逆推Krpano切图算法，实现在浏览器切多层级瓦片图
前言
- 趁着隔离梳理一下之前做的一个有用的功能：在浏览器中去切割多分辨率瓦片图
- 这是一个有趣的过程，跟我一起探索吧
- 阅读本文需具备前置知识：对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) droplet、MAKE VTOUR (NORMAL) droplet，在1.20开始使用krpano Tools应用程序可以进行可视化操作，除了切图外，还能方便还原全景图。
3.krpano切图最常用的方式
- 第一，普通切图，即立方体切图，将全景图切为上、下、左、右、前、后6张图。优点：切图速度快，占用存储少。缺点：场景启动时间不够快，放大模糊。
- 第二，多分辨率切图，跟瓦片地图原理类似。优点：启动速度快，图片清晰。缺点：占用存储较多，切图时间较久，一般用于航拍、风景等大范围场景的需求，室内样板间预览，几乎不太需要。比较著名的应用案例大家可以看看720云上的何同学六百万粉丝合影，这一个场景的图片超过了百万张。在地图领域中是必用的技术.（如此就能够根据不同的缩放等级来显示不同的清晰度的图像，这样的好处是如果要加载一张4k的全景图，不需要一次性就将整个全景图都加载进来，可以先加载一个缩放等级低的全景，然后当使用者进行缩放查看细节的时候再加载清晰度更高的图像，这样就可以明显提高加载速度，避免因为图片过大使得加载时间过长和不必要的流量浪费。不足之处就是需要为一张全景图额外准备不同清晰度的图片，增加了图片处理的工作量，也增加了图片存储的空间占用。）
4.瓦片地图金字塔模型

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

（图一）多分辨率切图：

（图二）普通切图：

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

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

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

图三：

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

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：

从上图中可以发现，每次切图的时候控制台会输出几个参数：
- 全景图的分辨率
- 一共多少层级，如图中所示 levels=3，表示有3个层级
- 每一层级的分辨率，如图中所示，3200x3200 1664x1664 768x768，由高到低
根据这些数据，我制成了一个表格：

为了让样本更具参考意义，全景图的分辨率我从1000x500 一直到 60000x30000。
为什么知道了6万就不往上测试了呢？因为我电脑Photoshop的极限就在这里了，没办法输出更高分辨率的图片了，从10个样本中，我依旧可以得出以下规律：
1. 相邻层级分辨率之比约等于 2，波动为0.2
2. 全景图的分辨率与最高层级的分辨率之比为 3.125 ，几乎所有都一样，仅有一个波动为0.012
3.125 这个数值我会把它当成一个突破口，
即最高层级图片的分辨 = 全景图分辨率 / 3.125。

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

以下仅列举了部分配置，完整配置可以参考krpano官网文档
```
// 多分辨率切图配置
multires=true //  是否是多分辨率
tilesize=512 // 瓦片图大小
levels=auto // 自动层级
levelstep=2 // (重点)每一层与上一层
maxsize=auto // 最高层级分辨率（自动计算）
maxcubesize=auto // 每一面最大的尺寸
stereosupport=true 
adjustlevelsizes=true // 允许调节每一层级的尺寸
adjustlevelsizesformipmapping=true
```
```
<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属性，第一个值表示单张瓦片图的大小。

既然单张瓦片图尺寸是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的时候可以发现，你传一张全景图上去，我可以在浏览器给你直接下载整个压缩包，并且里面已经分好层级和目录结构。

如图所示，这是我在浏览器生成的：

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的长条图。它生成的方式是立方体的六个面，按照「左、前、右、后、上、下」，自上而下拼接成。

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

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

通过对比，我们可以直观的看出来，我的图片要比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做全景，业界的标杆是贝壳找房；
相关阅读:
FF300R08W2P2B11A 汽车用EasyPACK 模块 2 个独立式
 Java 枚举(enum)学习笔记
 python基础（五）----时间模块
 备战秋招，LeetCode算法大总结，啃下这块硬骨头
 Cryptanalyzing and Improving a Novel Color Image Encryption Algorithm Using RT-Enhanced Chaotic Tent Maps
探索人工智能的深度神经网络：理解、应用与未来
 Tlsr8258开发-BQB（DTM）测试
 计算机组成原理期末复习笔记整理（上）（个人复习笔记/侵删/有不足之处欢迎斧正）
干货｜MATLAB工具箱之PsPM的介绍与安装
 使用dom4j解析XML
原文地址：https://www.cnblogs.com/liuqinrui/p/16751386.html

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

前言

1.功能简介

2.回顾krpano切图

3.krpano切图最常用的方式

4.瓦片地图金字塔模型

正片开始

5.前置知识介绍：ImageData

6.普通切图（立方体切图）

7.多分辨率瓦片图算法（重头戏）

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

02.小结krpano切图规律

03.算法思路推理与实现

04.最终算法实现

8.利用canvas分割图片

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

01.JSZip

02.file-saver

10.生成预览图 preview.jpg

11.缩略图thumb.jpg

12总结：

01.技术上，我们需要了解：

02.对于krpano的评价

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

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

05.如何还原全景图？