面向屏幕水印的双屏最小完全覆盖算法

朱永超，雷 浩

（成都飞机工业（集团）有限责任公司，四川成都 610031）

0 引言

涉密单位内网存在大量敏感信息，屏幕水印［1］能有效防止用户有意或无意的拍照和截图行为，以避免数据泄露［2］。屏幕水印的常用实现方法是绘制透明窗口，然后覆盖到计算机屏幕并保持置顶［3］。为实现屏幕完全覆盖，需要根据屏幕大小配置水印显示窗口的宽度、高度及其在屏幕坐标系下XY 坐标轴偏移量。计算机连接单显示器的情形最为简单，配置水印显示窗口大小为显示器分辨率，XY坐标轴偏移量为0，即可实现屏幕完全覆盖。计算机连接双显示器且显示器模式［4］配置为扩展桌面时，系统会设置一个主显示器和一个副显示器，此时情形较为复杂。双显示器的排列顺序包括左右排列和上下排列，其中左右排列可细分为主屏在左副屏在右和副屏在左主屏在右两种情形，上下排列可细分为主屏在上副屏在下和副屏在上主屏在下两种情形。不同的排列顺序与不同的分辨率组合，存在以下3 种类别：①主屏和副屏分辨率分辨率相同，比如均为1 920*1 080，如图1（a）所示；②主屏分辨率比副屏分辨率大，比如主屏分辨率为2 560*1 440，副屏分辨率为1 920*1 080，如图1（b）所示；③主屏分辨率比副屏分辨率小，比如主屏分辨率为1 920*1 080，副屏分辨率为2 560*1 440，如图1（c）所示。

Fig.1 Dual monitors with different arrangements and resolution combinations图1 双显示器不同排列与分辨率组合

对于Windows 操作系统，屏幕坐标系原点［5］为主显示器左上角。以类别三为例，绘制屏幕显示坐标如图2 所示（彩图扫OSID 码可见，下同），其中黄色代表主屏，红色代表副屏，绿色代表最小水印显示窗口。当副屏在左主屏在右时如图2（a）所示，此时副屏起始点X 坐标为负值。当主屏在左副屏在右时如图2（b）所示，此时副屏起始点X 坐标为正值。由于当主副显示器排列顺序和分辨率组合不同时，各显示器内像素点的坐标值会发生变化，实现双屏最小完全覆盖［6］的水印窗口大小和XY 坐标轴偏移量也会发生变化，因而如何得到最小水印窗口和XY 坐标偏移量，实现双屏不同组合的最小完全覆盖，是本文的主要研究内容。

Fig.2 Different coordinate values of pixels due to different positions of dual screens and resolution combinations图2 双屏位置不同导致像素点坐标值不同

1 相关研究

实现双屏完全覆盖最简单的方法是不考虑屏幕分辨率和屏幕数量，直接设置水印显示窗口大小和XY 坐标轴偏移量为一个较大的值，比如配置水印显示窗口大小为10 000*10 000，X 轴偏移量为-4 000，Y 轴偏移量为-3 000，从而形成一个“巨幕”覆盖在计算机屏幕上。巨幕法的优点是算法简单且容易实现，缺点有以下3 点：①不具有适应性，不论计算机接入单显示器还是多显示器，水印显示窗口大小都相同，可能造成显示效率极低及资源浪费情况；②渲染10 000*10 000的水印显示窗口要占用大量系统资源，对于配置低的计算机，容易造成卡顿，影响正常使用；③存在特殊排列情形，使得偏移量大于4 000 或3 000，进而造成无法实现完全覆盖，如图3所示。

Fig.3 Giant screen method cannot achieve complete screen coverage under special condition图3 特殊情形下巨幕法无法实现屏幕完全覆盖

针对双屏最小完全覆盖问题的其他相关研究包括：吕卿等［7］提到了实现屏幕水印的方法，但没有处理双屏及多屏适配问题。王晓媛等［8］介绍了3 类屏幕防窃拍方法，涉及屏幕水印法，但未对具体实现进行说明。Shaw 等［9］设计标记屏幕截图和识别已标记屏幕截图方法，通过离线方法实现，但屏幕水印要求实时显示。吴国华等［10］论述一种可溯源的屏幕水印实现方法，原理是将水印字符信息与视频信号进行叠加，并将叠加后的视频信号输出到显示设备；Gugelmann 等［11］设计一种人眼看不见的符号形状隐藏于屏幕显示；Piec 等［12］利用人类视觉系统（Human Visual System）的特性，并允许通过使用快速特征检测算法生成响应当前显示内容的动态自适应水印，以上3 种方法均涉及暗水印［13］，但只考虑了单屏显示，未涉及双屏及多屏显示问题。梅强华等［14］提出一种自动检测和动态改变屏幕分辨率设置程序，但水印的显示要求屏幕具有固定的分辨率。付海涛等［15］针对传感器网络中节点的部署和覆盖问题，提出一种完全覆盖热点区域的多重覆盖算法。杨晓波等［16］提出一种基于最小覆盖空域的机载预警雷达的多帧检测前跟踪方法，但屏幕水印场景中双屏及多屏之间不存在多重覆盖问题。赵福生等［17］探讨不规则图形能否完全覆盖俄罗斯方块图形，分析L 形方块覆盖全部空间的条件，但双屏覆盖问题中研究的是完全覆盖子图形的最小空间大小。吴陈等［18］对有限集上相容关系以及对应完全覆盖的基数进行分析估计，葛洪伟等［19］提出使用蚁群算法解决组合优化问题，臧文科等［20］提出用面上DNA 计算模型求解最小集合覆盖问题。基于多屏覆盖问题的复杂性考虑，以上几种方法对多屏覆盖方面的理论研究有指导意义，但缺乏计算机工程方面的指导。杨丽徙［21］等提出基于最小覆盖圆的变电站优化选址方法，该方法应用的前提是变电站位置不变，而双屏覆盖问题中双屏位置不定，自由组合，更侧重于边界值分析，寻求能够覆盖所有组合的最小水印大小。综上所述，目前国内外尚未出现面向屏幕水印应用场景的双屏最小覆盖算法研究。

本文针对双屏最小完全覆盖问题进行分析，探讨在不同情形下实现双屏完全覆盖和获取最高显示效率的方法，提出3 种不同的完全覆盖算法，比较得到双屏最小完全覆盖算法并对算法进行设计和实现。

2 完全覆盖算法

2.1 中心包围算法

中心包围算法原理是以图1 中副屏环绕主屏四周滑动一周，覆盖所有可能组合情形，从而实现完全覆盖。图1（a）、（b）、（c）中心位置展示了覆盖所有组合情形的最小显示范围，3种类别显示效率计算如下：

（1）主屏分辨率和副屏分辨率相同，均为1 920*1 080，如图1（a）所示。此时最小水印显示窗口宽度为3*1 920，高度为3*1 080，显示效率计算如下：

（2）主屏分辨率比副屏分辨率大，主屏分辨率为2 560*1 440，副屏分辨率为1 920*1 080，如图1（b）所示。此时最小水印显示窗口宽度为2*1 920+2 560，高度为2*1 080+1 440，显示效率计算如下：

（3）主屏分辨率比副屏分辨率小，主屏分辨率为1 920*1 080，副屏分辨率为2 560*1 440，如图1（c）所示。此时最小水印显示窗口宽度为2*2 560+1 920，高度为2*1 440+1 080，显示效率计算如下：

2.2 左右分屏算法

绘制图1 中各种组合对应的坐标图，将坐标图拆分为左右两个部分。以图1（c）为例，对应双屏组合中的类别三，左部和右部分别如图4 区域A 和区域B 所示。左部和右部划分的依据是：右部中副屏起始点X 坐标值为正值，左部中副屏起始点X 坐标值为负值。此时左部和右部主副屏各种组合存在以下特点：总屏宽度最大为主屏宽和副屏宽之和，总屏高度最大为主屏高与两倍副屏高之和。为覆盖所有组合，最小水印显示窗口宽度应为1 920+2 560，高度应为1 080+2*1 440，左部和右部显示效率相同，计算如下：

考虑双屏组合的另外两种类别：

（1）主副屏分辨率相同，均为1 920*1 080，如图1（a）所示。最小水印显示窗口宽度为1 920+1 920，高度为1 080+2*1 080，显示效率计算如下：

（2）主屏分辨率比副屏分辨率大，主显示器分辨率为2 560*1 440，副显示器分辨率为1 920*1 080，如图1（b）所示。最小水印显示窗口宽度为2 560+1 920，高度为1 440+2*1 080，显示效率计算如下：

2.3 左右上下分屏算法

左右上下分屏算法原理是在左右分屏算法基础上，分别针对左部和右部执行上下分屏。上下分屏的提出是为了区分严格左右分屏。以图4 右部区域B 为例，二者的划分依据是：上下分屏时副屏起始点X 坐标值小于主屏宽度，而严格左右分屏时副屏起始点X 坐标值等于主屏宽度。图4 右部区域B 坐标图整体可拆分为上下分屏和严格左右分屏，分别如图4区域C 和区域D 所示。

2.3.1 严格左右分屏

以图4 区域D 为例，此时主屏分辨率比副屏小，主屏分辨率为1 920*1 080，副屏分辨率为2 560*1 440，当严格左右分屏时，主副屏始终处于主左副右的状态，此时总屏宽度是固定的，等于主屏宽度和副屏宽度之和，为实现最小覆盖，需要根据不同的双屏组合计算出总屏的最小高度，分以下3种情形讨论：

Fig.4 Left and right coordinate map for left and right split screen图4 左右分屏时左部和右部坐标图

情形1：总屏高度等于主屏高度与副屏高度之和（见图5）。此情形下，最小水印显示窗口宽度为1 920+2 560，高度为1 080+1 440，显示效率计算如下：

情形2：总屏高度等于副屏高度（见图6）。此情形下，最小水印显示窗口宽度为1 920+2 560，高度为1 440，显示效率计算如下：

情形3：总屏高度介于副屏高度和主副屏高度之和（见图7）。此情形介于情形1 和情形2 之间，显示效率最低为0.51，最高为0.89。由于最小水印显示窗口宽度是固定的，等于主屏和副屏宽度之和，此时需根据副屏Y 轴偏移量计算得出最小高度。

考虑双屏组合的另外两种类别：

对于类别一，主副屏分辨率相同，均为1 920*1 080，如图1（a）所示，对应上述3种情形，显示效率计算如下：

情形1：总屏高度等于主屏高度和副屏高度之和，此时最小水印显示窗口宽度为1 920+1 920，高度为1 080+1 080。

情形2：总屏高度等于主屏高度和副屏高度之和，最小水印显示窗口宽度为1 920+1 920，高度为1 080。

情形3：总屏高度介于副屏高度和主副屏高度之和，此情形介于情形1 和情形2 之间，显示效率最低为0.5，最高为1。

对于类别二，主显示器分辨率比副显示器分辨率大，主显示器分辨率为2 560*1 440，副显示器分辨率为1 920*1 080，如图1（b）所示，对应上述3 种情形，显示效率计算如下：

情形1：总屏高度等于主屏高度和副屏高度之和，最小水印显示窗口宽度为2 560+1 920，高度为1 440+1 080。

情形2：总屏高度等于主屏高度和副屏高度之和，最小水印显示窗口宽度为2 560+1 920，高度为1 440。

情形3：总屏高度介于副屏高度和主副屏高度之和，介于情形1 和情形2 之间，显示效率最低为0.51，最高为0.89。

根据对称性，左部与右部情况相同。

Fig.5 The total screen height is equal to the sum of main screen height and vice screen height图5 总屏高度等于主屏高度与副屏高度之和

2.3.2 上下分屏

以图4 区域C 为例，此时主屏分辨率比副屏小，主屏分辨率为1 920*1 080，副屏分辨率为2 560*1 440，当上下分屏时，总屏高度是固定的，等于主屏高度和副屏高度之和，为实现最小覆盖，需要根据不同的双屏组合计算出总屏的最小宽度。分以下3种情形讨论：

情形1：总屏宽度等于主屏宽度与副屏宽度之和。图5 既可作为严格左右分屏，也可作为上下分屏。作为上下分屏时，最小水印显示窗口宽度为1 920+2 560，高度为1 080+1 440，显示效率计算如下：

情形2：总屏宽度等于副屏宽度（见图8）。此情形下，最小水印显示窗口宽度为2 560，高度为1 080+1 440，显示效率计算如下：

情形3：总屏宽度介于副屏宽度与主副屏宽度之和（见图9）。此情形介于情形1 和情形2 之间，显示效率最低为0.51，最高为0.89。由于最小水印显示窗口高度是固定的，等于主屏和副屏高度之和，此时需根据副屏X 轴偏移量计算得出最小水印显示窗口宽度。

Fig.6 The total screen height is equal to the vice screen图6 总屏高度等于副屏高度

Fig.7 The total screen height is between the sum of main screen and vice screen height图7 总屏高度介于副屏高度与主副屏高度之和

Fig.8 The total screen width is equal to the vice图8 总屏宽度等于副屏宽度

考虑双屏组合的另外两种类别。对于类别一，主副屏分辨率相同，均为1 920*1 080，如图1（a）所示，对应上述3种情形，显示效率计算如下：

情形1：总屏高度等于主屏高度和副屏高度之和，最小水印显示窗口宽度为1 920+1 920，高度为1 080+1 080。

情形2：总屏宽度等于副屏宽度，最小水印显示窗口宽度为1 920+1 920，高度为1 080。

情形3：总屏宽度介于副屏宽度和主副屏宽度之和，介于情形1和情形2之间，显示效率最低为0.5，最高为1。

对于类别二，主显示器分辨率比副显示器分辨率大，主显示器分辨率为2 560*1 440，副显示器分辨率为1 920*1 080，如图1（b）所示，对应上述3种情形，显示效率计算如下：

情形1：总屏高度等于主屏高度和副屏高度之和，最小水印显示窗口宽度为2 560+1 920，高度为1 440+1 080。

Fig.9 The total screen width is between the sum of main screen and vice screen width图9 总屏宽度介于副屏宽度与主副屏宽度之和

情形2：总屏宽度等于副屏宽度，最小水印显示窗口宽度为2 560，高度为1 440+1 080。

情形3：总屏宽度介于副屏宽度和主副屏宽度之和，介于情形1 和情形2 之间，显示效率最低为0.51，最高为0.89。

根据对称性，左部与右部情况相同。

3 算法比较与实现

比较3种完全覆盖算法，汇总结果如下。

主屏分辨率和副屏相同时，3 种算法显示效率比较如表1所示。

主屏分辨率比副屏大时，3 种算法显示效率比较如表2所示。

主屏分辨率比副屏小时，3 种算法显示效率比较如表3所示。

Table 1 Comparison of algorithms when the main screen resolution is equal to the vice screen表1 双屏分辨率相同时算法比较

Table 2 Comparison of algorithms when the main screen resolution is larger than the vice screen表2 主屏分辨率比副屏大时算法比较

Table 3 Comparison of algorithms when the main screen resolution is smaller than the vice screen表3 主屏分辨率比副屏小时算法比较

对比3 种算法，中心包围算法显示效率最低，左右分屏算法次之，左右上下分屏算法显示效率最高。

推广到更一般的情形，假设主屏分辨率为x1*y1，副屏分辨率为x2*y2，则：

（1）中心包围算法。

（2）左右分屏算法。首先根据副屏起始点X 坐标值是否为正值确定双屏组合属于左部还是右部，然后计算显示效率。左部和右部显示效率计算方式相同。

（3）左右上下分屏算法。首先确定当前双屏组合属于左部还是右部，然后确定当前组合属于上下分屏还是严格左右分屏，判断依据：上下分屏时副屏起始点X 坐标值小于主屏宽度，而严格左右分屏时副屏起始点X 坐标值等于主屏宽度。

比较式（18）、式（19）、式（20）可知，对于相同的双屏组合，显然左右上下分屏算法显示效率最高。

综上可知，左右上下分屏算法显示效率最高，为双屏最小完全覆盖算法。其算法流程如图10所示。

4 结语

Fig.10 Flow of Left，right，top and bottom split screen algorithm图10 左右上下分屏算法流程

本文针对屏幕水印应用场景下的双屏最小完全覆盖算法进行了研究。通过分析双屏排列顺序和分辨率的不同组合，提出三种完全覆盖算法，然后推广到一般情形，得到每种算法的显示效率计算公式，最终得出左右上下分屏算法为双屏最小完全覆盖算法，同时设计出算法对应的程序流程图。双屏最小完全覆盖算法的研究，对多屏最小完全覆盖算法提供了有意义的参考和基础，同时有助于解决暗水印应用场景下无法动态控制水印显示位置及颜色的问题。