[Discode] 生成 & 识别Discode

简介

书接上文,在上一章节中,我详细的分析了市场上已经落地应用的部分商用方案,也针对自己的实际需求进行了思考,设计了适合需求的编码规范和编码形式。在本章节中,我将会分享一下Discode的生成和识别过程和技术细节。

目录

  1. 生成Discode
  2. 识别Discode
  3. Github仓库
  4. 编后语
  5. 版权声明

生成Discode

如何生成图形编码?

在前面的设计原型中,Discode中包含四个定位点的设计。按照设计Discode的定位点类似于微信小程序码的定位点,基础元素是由一个圆环和一个圆点组成的图案。

定位点

之后会将其等距离的放置在图形编码的四个角上,用于图形的定位,如下图所示。

确定好定位点之后,我们就需要生成我们的图形编码了。图形编码包含两个部分:

一、用什么规则来代表数据?

参考条形码的设计,我决定通过点与线来分别代表0和1。之所以会有这样子的想法,是我认为在之后的学习研究识别过程中,点与线的识别应该会有更多现成的代码可以参考学习,不用自己再花大量时间来研究。

基于这种想法,通过简单的编程在canvas上生成了上图的DEMO图形,拥有五个定位点与按照一定规则环状点线的编码区所组成的Discode。(之所以在图形的中心也包含一个定位点,主要是当时想用来确认圆心是否能够被计算正确,所以增加的辅助图形,在技术验证后就被品牌Icon代替。)

二、存储数据量要设计多大?

在之前的原型设计中,我曾经分析过小程序拥有多种容量的设计,比如36线、72线、144线等设计。通过增加线密度来增加图形的数据承载量。因此我也对此进行了一些简单的实验。

上图是每隔五度绘制一位数据的72线版本的Discode,可以很容易的看到,在内圈的1-3层,由于图形之间的间隙过小,很容易产生图形与图形间粘连在一块的问题,特别是第二圈右下角的多线段连在一块很难辨别的问题。

题外话

那为啥微信小程序可以支持72线?

通过观察微信小程序的设计规范可以发现,之所以元信息区并不是从最内圈开始的原因:就是为了解决72线可能会导致图形绘制过于密集,导致编码图形难以被识别和处理。而选择了往外移了几圈,才开始进行实质性的编码。

微信小程序码编码设计

对比实际编码出来的图形,我们可以发现,为了美观考虑,小程序码在元信息区往圆心方向的编码区其实只有36线,即10度才记录一个编码,只有在元信息区才开始使用72线,即5度进行一个编码。

那问题就迎刃而解了,要么就是将实际数据编码区往外移,要么就是减少单圈编码密度。最终我还是选择了减少单圈编码密度作为我的解决方法,之所以选择这个方法就是图省事,简单快速的解决问题,不然将编码区外移又需要耗费一部分的时间来重新设计编码规范,我着实是不想这么干。

增大到10度一编码后,图形的视觉效果就好多了,另外也部分程度上的解决了图形粘黏的问题。解决了编码问题后,我们只要将定位点、编码区组装起来就是我们设计出来的Discode了。

其实到这一步Discode就已经生成完成了,只要在中间预留的空白处填上我们希望填充的Logo即可。

识别Discode

识别Discode主要有以下的几个步骤:

  1. 使用Hough Circle获取定位点的圆心坐标

通过Hough Circle Transform获得四个定位点的相对于图片的位置信息。

  1. 通过四个定位点计算编码区圆心位置

接下来连接对角点,形成两条线段(红线与蓝线),计算交点位置。

如上图顺序对应0-3的四个坐标代入公式计算得出圆心坐标。

\( y_{cross} = \frac{(y_{0} – y_{1}) \times (y_{3} – y_{2}) \times x_{0} + (y_{3} – y_{2}) \times (x_{1} – x_{0}) \times y_{0} + (y_{1} – y_{0}) \times (y_{3} – y_{2}) \times x_{2} + (x_{2} – x_{3}) \times (y_{1} – y_{0}) \times y_{2}}{(x_{1} – x_{0}) \times (y_{3} – y_{2}) + (y_{0} – y_{1}) \times (x_{3} – x_{2})}\) \(x_{cross} = x_{2} + \frac{(x_{3}-x_{2})\times(y_{cross} – y_{2})}{y_{3} – y_{2}}\)
  1. 设置ROI(Region of interest)识别指定区域

Discode的编码起点如下图所示:

Discode从上图的矩形框中开始生成第一位编码,然后在相同半径内沿着逆时针方向(红箭头),生成接下来的编码,当一圈编码完成后就自增半径,开始第二圈的编码直到编码五圈为止。

而识别其实就是逆向这个过程,如上图设置图像的ROI到图像的编码开始点,然后逆时针一个一个识别,一圈一圈识别,直到识别完成。

  1. 使用Canny edge detection获得识别区的轮廓

在上一步中,我们设置了图像的ROI,接下来我们要做的就是计算这个ROI内的图形到底代表的是0还是1。

识别的核心原理:计算ROI区域内的图形的面积。

之所以我们可以这么做,是因为我们已知ROI的面积信息,我们也知道长线段占用的面积理应大于短线段的常理,基于这两个信息,我们只要计算ROI内图形面积,并通过经验设定一个阈值来判定是长线段还是短线段。知道线段类型后,转换成0和1就水到渠成了。

这里我们引入了Canney边缘检测,通过边缘检测获得ROI内图形的轮廓数据。

  1. 通过contourArea函数计算轮廓面积

获得轮廓数据后,我们就可以计算出ROI中的闭合图形个数以及总面积信息,之所以有时候个数会大于1,是因为有时候ROI会重复识别到上一个图形的边缘,导致到污染了识别区。不过由于这种现象仅仅发生于长线段的交接处才会发生,且数据影响不大,因此我也没有做进一步的处理。如果要继续优化,可以继续精细化ROI区域,使得覆盖率提高。或者调整生成图形算法,加大线段之间的间隙,避免互相粘黏。

  1. 判定图形代表0或1

通过多次的实验可得,短线段的占用的面积必定小于10,大于10的必定是长线段。因此在这里使用10作为阈值,用于判定ROI内的图像是代表0或1。

  1. 分割 & 转换

将每个图像代表的二进制数值存入数组当中并将其按照6bit为一位通过编码字典,重新转换成可阅读的字符串。

  1. 输出结果

由于有时候编码的字符不一定会用完全部可用编码位,因此还会在有效编码后面加入一些随机数据作为填充,使得图形更加美观。

Github仓库

https://github.com/7gugu/Discode

仓库中包含了完整的生成和识别图形代码,可以自行运行学习一下。实测通过FireFox 100是可以正常运行的。

编后语

至此整个Discode系列就全部更新完成了。原来在这个部分我思考了很久,写了几个版本的内容,先是是过拆分成两个章节来慢慢讲解,也试过回溯历史结合QRCode来阐述为啥我要这么做,但效果都不尽如意,过于的繁琐冗余,最后还是秉着少即是多的原则,缩减成一章来讲解。五月中的时候恰好碰上了组内的技术分享,有幸向其他同事分享了我的这个想法,也得到很多宝贵的建议。之后由于毕业设计和工作上的琐事,使得进度很慢,对此向期待这篇技术分享的朋友说声抱歉。接下去我应该会专注于wasm和三维建模上,希望以后可以投入游戏产业,继续实现个人梦想。

版权声明

知识共享许可协议

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

[Discode] 设计Discode

简介

在本篇文章中我将一步步的阐述我设计Discode的流程以及我的思考点。虽然Discode作为一种编码仍然比较稚嫩,但作为入门自己的第一个图形编码仍然是不错的例子。

目录

  • 分析现有编码的设计
  • Discode的视觉设计
  • Discode的技术指标
  • Discode的编码设计
  • 编后语
  • 版权声明

分析现有编码的设计

当前世面上各家厂商为了用户纷纷都推出了自有的编码规范,仅仅在大陆地区而言,当前能够看到的自由编码普遍是圆形二维码,也有像是QQ小程序码的变种圆形二维码。

从这四种只有编码中我们不难观察出一个规律,大家的编码样式的元素基本都是:

  1. 图形编码环绕着Logo
  2. 四点定位

图形编码环绕着Logo

这种设计有两个好处:

  1. 具有高自由度的品牌露出的能力

开发者可以自由的定义自己的图标类型,使得用户一眼就能识别出编码对应的软件信息(比如广东省的粤核酸小程序的Logo是DNA双链+号码,用户扫描前就已经可以预测到自己扫描的是一个粤核酸的小程序)。

  1. 不占用实际编码区域

现有的二维码规范中,已经通过纠错编码的能力,来实现图片覆盖二维码后仍能识别的能力。但对于一个新生的图形编码而言,设计一个出色的纠错编码并不是一件容易的事情,即使套用现有的编码规范仍有可能因为经验不足等因素导致到后来Coding过程中出现一些不可预见的限制。因此将分开显示能够极大的规避掉初期编码水平不足给自己挖坑的风险。

有好处当然也是有坏处的:

  1. 需要开发全新的生成与识别规则

环形编码意味着不能直接复用二维码已有的生成能力也不能直接识别,所有的东西都需要从0开始。

  1. 编码容量有限

环状编码的本质就是在圆圈上作文章,比如使用点、线段等作为二进制中的1,空白作为二进制中的0,实现二进制编码成图像元素。受制于圆形的特性:一圈是360度,为了视觉识别的准确性和速度,一般都会设计为每5-10度的圆弧内记录一个编码。因此单圈的能够承载的编码都是有限的,比如小程序码就是设计了36线,54线,72线的小程序码。假如我们10度编码一位信息,则一圈最多可以编码36位二进制信息。同时自定义的编码还有长度限制,因此单圈的实际编码数量肯定是远远小于36位的。

思考:如何拓展容量?

圆形编码有两种扩大容量的方式:

1.使用更密集的图形(在更小的弧度内编码信息)

比如小程序码的36线就是每10度作为一个编码区,54线就是6.6度一个编码区,72线就是5度一个编码区。

2.扩大半径(增加圈数)

比如支付宝只有3圈编码区域,AppClips则是5圈编码区

2.四点定位

以小程序码为例,分别在左上右上左下设置了Mark Point(定位点),其实右下角的Logo也是一个定位点,不过他是一个特殊的定位点,需要使用特殊的计算方式确定真实的圆心(在此不赘述),最终微信是可以通过这四点的圆心坐标,计算出对角线交线的坐标点,而这个坐标点就是小程序码的圆心。另外通过这四个点还能确定编码的实际区域,方便进行透视变换矫正图形到正确的位置。

思考:定位点是必须的吗?

虽然定位点确实能够帮助我们进行很炫酷的图形变换来矫正图形到正确的形态,但对于刚刚入门图形编码的我来说这个也太难了吧!遂开始寻找有没有不需要定位点的图形码,没想到还真的有,那就是Apple为App小程序推出的AppClips Code。

那么问题来了,为什么AppClip码可以不要定位点?那它要怎么定位圆心?机器如何对其进行纠正?通过查阅设计文档得出的答案居然是:标准限制+人工对准。

文档地址: Human Interface Guidelines > App Clips > App Clip Codes

阅读了Apple的设计规范之后,我才悟到其实我们不需要强行考虑复杂的环境,我们完全可以设计一些标准规避到复杂环境的可能,让用户遵守标准就好了,这样子就可以规避到很多问题,极大的降低工程的技术难度,为后续的继续设计奠定了基础。

Discode的视觉设计

完成上一节的市场分析后,我们就可以开始思考一下我们的Discode到底要长什么样子了。

基于市面上的圆形码,我的初步想法是:通过定位点来定位图像,同样支持品牌Logo的露出,另外也需要支持可变容量。因此原型设计中我参考了小程序码的定位点设计,出于后期编码的简单化考虑和法务风险规避的考虑,我把小程序码右下角的官方Logo去掉,替换成为了定位点。如果日后需要增加官方Logo的话,则如下图所示可以在品牌Logo的右下角增加一个官方的小Logo。

对于可变容量我也思考了两种方向,增大圈数或者加大密度,考虑到半径的动态变化可能会对识别造成一些不可规避的难点,我还是选择了减小编码区所占用的弧度,来增加编码密度实现容量的可变性。为此我同样参考了小程序码的设计并根据圆弧的弧度为360度进行平均分割,设计了36区、72区和144区的编码区密度,其分别占用10度/编码区、5度/编码区、2.5度/编码区。为了容量和设计美观度的考虑,暂定的圈数应该为3圈,确保可以将Discode印刷于一个非常小的区块中。

Discode的编码设计

图像编码中最核心的部分之一就是数据的编码规则了,通过编码规则,我们才能将二进制的数据转换成特定的图形并组合成一块就可以生成出自己的图形编码了,反过来的就是识别的流程了,不过具体怎么做我会留到接下来的生成和识别的解析文章中来讲解。

设计编码主要是遵循以下的几步:

  1. 确定编码的使用场景(决定未来的可能场景)
  2. 确定编码的宽度(决定可以容纳多少的字符)
  3. 根据编码容量来调整实际可编码的字符
  4. 分配字符到编码规则
  5. 根据视觉调整编码规则(这一步会发生在生成Discode后才会进行,在《生成Discode》中会讲到如何调整)
  6. 确定最终编码规则 & 整理成编码字典

1. 确定编码什么字符

在这一步我们先要确定我们的使用场景:

  • 可以记录网址吗?
  • 可以记录图片吗?
  • 区分大小写字符吗?
  • 可以记录邮箱吗?
  • 我们需要考虑损毁吗?
  • 我们要考虑修复能力吗?
  • 如果要修复能力我们要支持多少百分比的恢复能力呢?
  • 中文字符要考虑吗?

这些都是需要我们根据我们的未来使用场景来预设的。在我们的本次的项目周期走,我认为网址信息和邮箱信息是必须的,因为这样子才能让Discode具有实际的落地场景。图片二维码一般都是依托于Base64来实现的,存储图片这种高密度信息,显然不是Discode的长处,因此不考虑实现。中文字符可以通过UniCode字符集实现,不过其本质还是特定字符+字母,因此实现特殊字符、大小写字母和数字的编码后就可以实现,因此可以考虑作为第二目标来实现。修复能力需要依托于支持校验的编码实现,本次开发更偏向于探究如何实现,因此参考AppClips的思路,我决定使用技术规范,来规避掉损毁的可能性,在此不考虑损毁修复的能力。

综合上述的思考:Discode的初步可编码字符就显而易见了,UniCode需要的&#;,邮箱网址需要要的@.,大小写字母和数字,一共67种字符。

2. 确定编码的宽度

按照计算机的二进制规范来看,我首先还是想到熟悉的\(2^{n}\)次方,1 Byte = 8 Bit,但是8位二进制数最大可以代表\(2^{8}\)=256个数字,对于需求中的67个数字而言冗余空间太多了,因此要进行一下缩减,那么要不就是使用7位128个,要不就是6位64个。128对于67而言冗余空间接近翻倍,太浪费了,但6位64个又存不下全部字符着实是让我有点苦恼。最终我还是选择了6位作为最终的编码长度,其中的原因主要是有两个,第一是编码密度可以达到100%,即每一位都会用于实际的编码当中,不会有冗余空间;第二则是6恰好与360的具有倍数关系,360/6 = 60,而60也恰好与2.5、5、10之间构成倍数关系,恰好满足144位、72位、36位的需求。因此出于这两点考虑选择了6位为最终的编码宽度。

3. 根据宽度来调整可实际编码的字符

确定了6位的编码宽度后,就确定了实际的容量了,即字符表最大可以存64个字符,那么大小写字符一种52个,数字字符10个,剩余2个空位。在使用场景中我有说过我的假设场景中存在用来存储邮箱地址和网址的想法,对于邮箱而言最重要的两个字符便是邮箱根地址,即@xxx.com中的@.,因此我选择了@.作为字符表最后两个空位所要代表的符号。

4. 分配字符到编码规则中

因为这次的开发中不需要考虑到纠错校验,因此分配到字符到编码规则中就很简单了,只要把所有可能出现的数字都列成表格,再一一对应填上就好了。

其中我还是有一点小考量的,开始符我设定为了.,结束符则是@,这其实是我的个人偏好而已,一个约定俗成的设定,其实换过来也是OK的。然后小写字母从000 001一直到011 010,而大写字母则是在则是最高位(第六位)设置为1,即100 001111 010,剩余的空间就用数字填空就好了。

到这里我的Discode的专属字符表就设计完成了,其实整个过程非常的简单有趣。另外一般而言,只要我们不外泄这张实际的编码表,其实基本上没人能够逆向这个图形编码的意义。(破解方法仍然是有的,只是成本问题,只要对方知道字符表大概能存哪些字符,通过一些数学统计方法仍旧是可以逆向出来的,不过对于Discode这样子的一个开源项目,其实没啥意义去逆向破解。)

Discode的技术指标

综合视觉设计和编码设计最终可以得出Discode的最终技术指标如下:

  1. 支持图像定位
  2. 支持30位的数据
  3. 支持a-z、A-Z、0-9、”@“、”.“共64种字符
  4. 支持自定义品牌Logo

编后语

说实话,其实这篇博文我觉得更像是我的一个思路的整理集,不太像一篇文笔流畅的技术解析文章,这点我确实意识到了。不过我还是想尽力分享一下我的思路出来看看能不能帮助到更多对此感兴趣的小伙伴,因为这实在是太有趣也太有成就感了。

版权声明

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

[Discode] 为啥要设计新的二维码系统?

这是《Discode的诞生与技术细节》系列文章的第一篇文章,分别讲述了为啥我会萌生设计一个新的图形编码系统、图形编码的技术指标以及未来的文章规划。

背景

2017年初的时候,微信小程序推出了它们自己的二维码编码系统,称作小程序码,也被大众称之为菊花码。这种新的编码系统着实是令我大开眼界,后续也了解到了Snapchat和Facebook自己也有编码系统,这些奇形怪状的图形编码系统着实吸引着我去了解它们的技术原理,但可惜的是,彼时的我恰逢高三冲刺阶段,并没有这么多的精力去学习和了解这些编码系统更深层次的技术原理,只可将其放在了自己的技术待办清单中。

起因

在2022年年初的时候,我有一天偶然在电梯间看到一个支付宝的广告,发现支付宝居然也按捺不住推出了自己的图形编码系统(支付宝小程序码介绍),这再一次勾起了我蠢蠢欲动的内心欲望:做一个属于自己的编码系统。

支付宝小程序码

成果

说干就干,由于恰逢春节期间,自己有很多的个人时间,因此可以集中比较大的一块时间进行集中的研究和开发。目前已经成功开发出了一个Demo版本的编码系统,这套编码系统我将其称作为DisCode系统,分别是Disc(光盘)和Code(编码)撮合成的一个合成词,读音类同Disco(迪斯科),之所以叫做这个名字,是因为其实际的解码过程就像是读取光盘的过程,而且图形也近似于一张光盘,因此被命名为Discode系统。下图的这个就是Discode编码,编码了v2ex.com。

Discode

技术指标

  1. 支持30Bit的数据*
  2. 支持a-z、A-Z、0-9、”@“、”.“共64种字符**
  3. 支持自定义品牌ICON

*:图像中的一个圈可以编码6Bit的数据,理论上是支持\(6x(x\geq 1)\)Bit的数据

**:目前仅仅是设计了一一对应的原始编码,理论上是可以支持带纠错功能的编码的,这需要结合你的实际场景进行设计

计划

在接下来的三个月内,计划沉淀出两篇技术文章和完整可运行的项目来一步步的阐述我的思考、设计和编码流程:

  1. 《设计Discode》
  2. 《生成 & 识别Discode》
  3. 《Discode生成和识别源码》

希望通过这两篇文章和全流程的项目,能够帮到一部分需要开发或者想要了解这项技术的开发者或者爱好者。

版权声明

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

wTodo Watch版微软Todo客户端

背景

我是一个很喜欢用电脑记录待办事项的人,感觉不通过待办事项我很容易就记不住事情。由于原来是在华为全家桶的用户,对跨平台有强需求(Windows+Android),因此顺理成章的选择了微软Todo作为我的待办事项记录平台。说实话,即使今天我已经开始转回Apple全家桶,但Todo的工作效率还是比Apple自家出品的”提醒事项”要好用很多。(Todo添加逻辑很自然,一打开界面就可以添加编辑待办事项,没那么多繁琐的设置)。

简介

wTodo是一款为Apple Watch适配的第三方Microsoft Todo应用, 通过该应用您可以在Watch端, 操作自己的待办清单。

系统需求

  1. iOS 15.0+
  2. watchOS 8.0+

商店链接

仅售1元

应用截图

Apple Watch Series 7 截图

使用指南

https://w-todo-guide.vercel.app/