面向屏幕水印的雙屏最小完全覆蓋算法

朱永超，雷 浩

（成都飛機(jī)工業(yè)（集團(tuán)）有限責(zé)任公司，四川成都 610031）

0 引言

涉密單位內(nèi)網(wǎng)存在大量敏感信息，屏幕水?。?］能有效防止用戶有意或無意的拍照和截圖行為，以避免數(shù)據(jù)泄露［2］。屏幕水印的常用實(shí)現(xiàn)方法是繪制透明窗口，然后覆蓋到計(jì)算機(jī)屏幕并保持置頂［3］。為實(shí)現(xiàn)屏幕完全覆蓋，需要根據(jù)屏幕大小配置水印顯示窗口的寬度、高度及其在屏幕坐標(biāo)系下XY 坐標(biāo)軸偏移量。計(jì)算機(jī)連接單顯示器的情形最為簡單，配置水印顯示窗口大小為顯示器分辨率，XY坐標(biāo)軸偏移量為0，即可實(shí)現(xiàn)屏幕完全覆蓋。計(jì)算機(jī)連接雙顯示器且顯示器模式［4］配置為擴(kuò)展桌面時(shí)，系統(tǒng)會(huì)設(shè)置一個(gè)主顯示器和一個(gè)副顯示器，此時(shí)情形較為復(fù)雜。雙顯示器的排列順序包括左右排列和上下排列，其中左右排列可細(xì)分為主屏在左副屏在右和副屏在左主屏在右兩種情形，上下排列可細(xì)分為主屏在上副屏在下和副屏在上主屏在下兩種情形。不同的排列順序與不同的分辨率組合，存在以下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 雙顯示器不同排列與分辨率組合

對(duì)于Windows 操作系統(tǒng)，屏幕坐標(biāo)系原點(diǎn)［5］為主顯示器左上角。以類別三為例，繪制屏幕顯示坐標(biāo)如圖2 所示（彩圖掃OSID 碼可見，下同），其中黃色代表主屏，紅色代表副屏，綠色代表最小水印顯示窗口。當(dāng)副屏在左主屏在右時(shí)如圖2（a）所示，此時(shí)副屏起始點(diǎn)X 坐標(biāo)為負(fù)值。當(dāng)主屏在左副屏在右時(shí)如圖2（b）所示，此時(shí)副屏起始點(diǎn)X 坐標(biāo)為正值。由于當(dāng)主副顯示器排列順序和分辨率組合不同時(shí)，各顯示器內(nèi)像素點(diǎn)的坐標(biāo)值會(huì)發(fā)生變化，實(shí)現(xiàn)雙屏最小完全覆蓋［6］的水印窗口大小和XY 坐標(biāo)軸偏移量也會(huì)發(fā)生變化，因而如何得到最小水印窗口和XY 坐標(biāo)偏移量，實(shí)現(xiàn)雙屏不同組合的最小完全覆蓋，是本文的主要研究內(nèi)容。

Fig.2 Different coordinate values of pixels due to different positions of dual screens and resolution combinations圖2 雙屏位置不同導(dǎo)致像素點(diǎn)坐標(biāo)值不同

1 相關(guān)研究

實(shí)現(xiàn)雙屏完全覆蓋最簡單的方法是不考慮屏幕分辨率和屏幕數(shù)量，直接設(shè)置水印顯示窗口大小和XY 坐標(biāo)軸偏移量為一個(gè)較大的值，比如配置水印顯示窗口大小為10 000*10 000，X 軸偏移量為-4 000，Y 軸偏移量為-3 000，從而形成一個(gè)“巨幕”覆蓋在計(jì)算機(jī)屏幕上。巨幕法的優(yōu)點(diǎn)是算法簡單且容易實(shí)現(xiàn)，缺點(diǎn)有以下3 點(diǎn)：①不具有適應(yīng)性，不論計(jì)算機(jī)接入單顯示器還是多顯示器，水印顯示窗口大小都相同，可能造成顯示效率極低及資源浪費(fèi)情況；②渲染10 000*10 000的水印顯示窗口要占用大量系統(tǒng)資源，對(duì)于配置低的計(jì)算機(jī)，容易造成卡頓，影響正常使用；③存在特殊排列情形，使得偏移量大于4 000 或3 000，進(jìn)而造成無法實(shí)現(xiàn)完全覆蓋，如圖3所示。

Fig.3 Giant screen method cannot achieve complete screen coverage under special condition圖3 特殊情形下巨幕法無法實(shí)現(xiàn)屏幕完全覆蓋

針對(duì)雙屏最小完全覆蓋問題的其他相關(guān)研究包括：呂卿等［7］提到了實(shí)現(xiàn)屏幕水印的方法，但沒有處理雙屏及多屏適配問題。王曉媛等［8］介紹了3 類屏幕防竊拍方法，涉及屏幕水印法，但未對(duì)具體實(shí)現(xiàn)進(jìn)行說明。Shaw 等［9］設(shè)計(jì)標(biāo)記屏幕截圖和識(shí)別已標(biāo)記屏幕截圖方法，通過離線方法實(shí)現(xiàn)，但屏幕水印要求實(shí)時(shí)顯示。吳國華等［10］論述一種可溯源的屏幕水印實(shí)現(xiàn)方法，原理是將水印字符信息與視頻信號(hào)進(jìn)行疊加，并將疊加后的視頻信號(hào)輸出到顯示設(shè)備；Gugelmann 等［11］設(shè)計(jì)一種人眼看不見的符號(hào)形狀隱藏于屏幕顯示；Piec 等［12］利用人類視覺系統(tǒng)（Human Visual System）的特性，并允許通過使用快速特征檢測(cè)算法生成響應(yīng)當(dāng)前顯示內(nèi)容的動(dòng)態(tài)自適應(yīng)水印，以上3 種方法均涉及暗水?。?3］，但只考慮了單屏顯示，未涉及雙屏及多屏顯示問題。梅強(qiáng)華等［14］提出一種自動(dòng)檢測(cè)和動(dòng)態(tài)改變屏幕分辨率設(shè)置程序，但水印的顯示要求屏幕具有固定的分辨率。付海濤等［15］針對(duì)傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的部署和覆蓋問題，提出一種完全覆蓋熱點(diǎn)區(qū)域的多重覆蓋算法。楊曉波等［16］提出一種基于最小覆蓋空域的機(jī)載預(yù)警雷達(dá)的多幀檢測(cè)前跟蹤方法，但屏幕水印場(chǎng)景中雙屏及多屏之間不存在多重覆蓋問題。趙福生等［17］探討不規(guī)則圖形能否完全覆蓋俄羅斯方塊圖形，分析L 形方塊覆蓋全部空間的條件，但雙屏覆蓋問題中研究的是完全覆蓋子圖形的最小空間大小。吳陳等［18］對(duì)有限集上相容關(guān)系以及對(duì)應(yīng)完全覆蓋的基數(shù)進(jìn)行分析估計(jì)，葛洪偉等［19］提出使用蟻群算法解決組合優(yōu)化問題，臧文科等［20］提出用面上DNA 計(jì)算模型求解最小集合覆蓋問題?；诙嗥粮采w問題的復(fù)雜性考慮，以上幾種方法對(duì)多屏覆蓋方面的理論研究有指導(dǎo)意義，但缺乏計(jì)算機(jī)工程方面的指導(dǎo)。楊麗徙［21］等提出基于最小覆蓋圓的變電站優(yōu)化選址方法，該方法應(yīng)用的前提是變電站位置不變，而雙屏覆蓋問題中雙屏位置不定，自由組合，更側(cè)重于邊界值分析，尋求能夠覆蓋所有組合的最小水印大小。綜上所述，目前國內(nèi)外尚未出現(xiàn)面向屏幕水印應(yīng)用場(chǎng)景的雙屏最小覆蓋算法研究。

本文針對(duì)雙屏最小完全覆蓋問題進(jìn)行分析，探討在不同情形下實(shí)現(xiàn)雙屏完全覆蓋和獲取最高顯示效率的方法，提出3 種不同的完全覆蓋算法，比較得到雙屏最小完全覆蓋算法并對(duì)算法進(jìn)行設(shè)計(jì)和實(shí)現(xiàn)。

2 完全覆蓋算法

2.1 中心包圍算法

中心包圍算法原理是以圖1 中副屏環(huán)繞主屏四周滑動(dòng)一周，覆蓋所有可能組合情形，從而實(shí)現(xiàn)完全覆蓋。圖1（a）、（b）、（c）中心位置展示了覆蓋所有組合情形的最小顯示范圍，3種類別顯示效率計(jì)算如下：

（1）主屏分辨率和副屏分辨率相同，均為1 920*1 080，如圖1（a）所示。此時(shí)最小水印顯示窗口寬度為3*1 920，高度為3*1 080，顯示效率計(jì)算如下：

（2）主屏分辨率比副屏分辨率大，主屏分辨率為2 560*1 440，副屏分辨率為1 920*1 080，如圖1（b）所示。此時(shí)最小水印顯示窗口寬度為2*1 920+2 560，高度為2*1 080+1 440，顯示效率計(jì)算如下：

（3）主屏分辨率比副屏分辨率小，主屏分辨率為1 920*1 080，副屏分辨率為2 560*1 440，如圖1（c）所示。此時(shí)最小水印顯示窗口寬度為2*2 560+1 920，高度為2*1 440+1 080，顯示效率計(jì)算如下：

2.2 左右分屏算法

繪制圖1 中各種組合對(duì)應(yīng)的坐標(biāo)圖，將坐標(biāo)圖拆分為左右兩個(gè)部分。以圖1（c）為例，對(duì)應(yīng)雙屏組合中的類別三，左部和右部分別如圖4 區(qū)域A 和區(qū)域B 所示。左部和右部劃分的依據(jù)是：右部中副屏起始點(diǎn)X 坐標(biāo)值為正值，左部中副屏起始點(diǎn)X 坐標(biāo)值為負(fù)值。此時(shí)左部和右部主副屏各種組合存在以下特點(diǎn)：總屏寬度最大為主屏寬和副屏寬之和，總屏高度最大為主屏高與兩倍副屏高之和。為覆蓋所有組合，最小水印顯示窗口寬度應(yīng)為1 920+2 560，高度應(yīng)為1 080+2*1 440，左部和右部顯示效率相同，計(jì)算如下：

考慮雙屏組合的另外兩種類別：

（1）主副屏分辨率相同，均為1 920*1 080，如圖1（a）所示。最小水印顯示窗口寬度為1 920+1 920，高度為1 080+2*1 080，顯示效率計(jì)算如下：

（2）主屏分辨率比副屏分辨率大，主顯示器分辨率為2 560*1 440，副顯示器分辨率為1 920*1 080，如圖1（b）所示。最小水印顯示窗口寬度為2 560+1 920，高度為1 440+2*1 080，顯示效率計(jì)算如下：

2.3 左右上下分屏算法

左右上下分屏算法原理是在左右分屏算法基礎(chǔ)上，分別針對(duì)左部和右部執(zhí)行上下分屏。上下分屏的提出是為了區(qū)分嚴(yán)格左右分屏。以圖4 右部區(qū)域B 為例，二者的劃分依據(jù)是：上下分屏?xí)r副屏起始點(diǎn)X 坐標(biāo)值小于主屏寬度，而嚴(yán)格左右分屏?xí)r副屏起始點(diǎn)X 坐標(biāo)值等于主屏寬度。圖4 右部區(qū)域B 坐標(biāo)圖整體可拆分為上下分屏和嚴(yán)格左右分屏，分別如圖4區(qū)域C 和區(qū)域D 所示。

2.3.1 嚴(yán)格左右分屏

以圖4 區(qū)域D 為例，此時(shí)主屏分辨率比副屏小，主屏分辨率為1 920*1 080，副屏分辨率為2 560*1 440，當(dāng)嚴(yán)格左右分屏?xí)r，主副屏始終處于主左副右的狀態(tài)，此時(shí)總屏寬度是固定的，等于主屏寬度和副屏寬度之和，為實(shí)現(xiàn)最小覆蓋，需要根據(jù)不同的雙屏組合計(jì)算出總屏的最小高度，分以下3種情形討論：

Fig.4 Left and right coordinate map for left and right split screen圖4 左右分屏?xí)r左部和右部坐標(biāo)圖

情形1：總屏高度等于主屏高度與副屏高度之和（見圖5）。此情形下，最小水印顯示窗口寬度為1 920+2 560，高度為1 080+1 440，顯示效率計(jì)算如下：

情形2：總屏高度等于副屏高度（見圖6）。此情形下，最小水印顯示窗口寬度為1 920+2 560，高度為1 440，顯示效率計(jì)算如下：

情形3：總屏高度介于副屏高度和主副屏高度之和（見圖7）。此情形介于情形1 和情形2 之間，顯示效率最低為0.51，最高為0.89。由于最小水印顯示窗口寬度是固定的，等于主屏和副屏寬度之和，此時(shí)需根據(jù)副屏Y 軸偏移量計(jì)算得出最小高度。

考慮雙屏組合的另外兩種類別：

對(duì)于類別一，主副屏分辨率相同，均為1 920*1 080，如圖1（a）所示，對(duì)應(yīng)上述3種情形，顯示效率計(jì)算如下：

情形1：總屏高度等于主屏高度和副屏高度之和，此時(shí)最小水印顯示窗口寬度為1 920+1 920，高度為1 080+1 080。

情形2：總屏高度等于主屏高度和副屏高度之和，最小水印顯示窗口寬度為1 920+1 920，高度為1 080。

情形3：總屏高度介于副屏高度和主副屏高度之和，此情形介于情形1 和情形2 之間，顯示效率最低為0.5，最高為1。

對(duì)于類別二，主顯示器分辨率比副顯示器分辨率大，主顯示器分辨率為2 560*1 440，副顯示器分辨率為1 920*1 080，如圖1（b）所示，對(duì)應(yīng)上述3 種情形，顯示效率計(jì)算如下：

情形1：總屏高度等于主屏高度和副屏高度之和，最小水印顯示窗口寬度為2 560+1 920，高度為1 440+1 080。

情形2：總屏高度等于主屏高度和副屏高度之和，最小水印顯示窗口寬度為2 560+1 920，高度為1 440。

情形3：總屏高度介于副屏高度和主副屏高度之和，介于情形1 和情形2 之間，顯示效率最低為0.51，最高為0.89。

根據(jù)對(duì)稱性，左部與右部情況相同。

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

2.3.2 上下分屏

以圖4 區(qū)域C 為例，此時(shí)主屏分辨率比副屏小，主屏分辨率為1 920*1 080，副屏分辨率為2 560*1 440，當(dāng)上下分屏?xí)r，總屏高度是固定的，等于主屏高度和副屏高度之和，為實(shí)現(xiàn)最小覆蓋，需要根據(jù)不同的雙屏組合計(jì)算出總屏的最小寬度。分以下3種情形討論：

情形1：總屏寬度等于主屏寬度與副屏寬度之和。圖5 既可作為嚴(yán)格左右分屏，也可作為上下分屏。作為上下分屏?xí)r，最小水印顯示窗口寬度為1 920+2 560，高度為1 080+1 440，顯示效率計(jì)算如下：

情形2：總屏寬度等于副屏寬度（見圖8）。此情形下，最小水印顯示窗口寬度為2 560，高度為1 080+1 440，顯示效率計(jì)算如下：

情形3：總屏寬度介于副屏寬度與主副屏寬度之和（見圖9）。此情形介于情形1 和情形2 之間，顯示效率最低為0.51，最高為0.89。由于最小水印顯示窗口高度是固定的，等于主屏和副屏高度之和，此時(shí)需根據(jù)副屏X 軸偏移量計(jì)算得出最小水印顯示窗口寬度。

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 總屏寬度等于副屏寬度

考慮雙屏組合的另外兩種類別。對(duì)于類別一，主副屏分辨率相同，均為1 920*1 080，如圖1（a）所示，對(duì)應(yīng)上述3種情形，顯示效率計(jì)算如下：

情形1：總屏高度等于主屏高度和副屏高度之和，最小水印顯示窗口寬度為1 920+1 920，高度為1 080+1 080。

情形2：總屏寬度等于副屏寬度，最小水印顯示窗口寬度為1 920+1 920，高度為1 080。

情形3：總屏寬度介于副屏寬度和主副屏寬度之和，介于情形1和情形2之間，顯示效率最低為0.5，最高為1。

對(duì)于類別二，主顯示器分辨率比副顯示器分辨率大，主顯示器分辨率為2 560*1 440，副顯示器分辨率為1 920*1 080，如圖1（b）所示，對(duì)應(yīng)上述3種情形，顯示效率計(jì)算如下：

情形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。

根據(jù)對(duì)稱性，左部與右部情況相同。

3 算法比較與實(shí)現(xiàn)

比較3種完全覆蓋算法，匯總結(jié)果如下。

主屏分辨率和副屏相同時(shí)，3 種算法顯示效率比較如表1所示。

主屏分辨率比副屏大時(shí)，3 種算法顯示效率比較如表2所示。

主屏分辨率比副屏小時(shí)，3 種算法顯示效率比較如表3所示。

Table 1 Comparison of algorithms when the main screen resolution is equal to the vice screen表1 雙屏分辨率相同時(shí)算法比較

Table 2 Comparison of algorithms when the main screen resolution is larger than the vice screen表2 主屏分辨率比副屏大時(shí)算法比較

Table 3 Comparison of algorithms when the main screen resolution is smaller than the vice screen表3 主屏分辨率比副屏小時(shí)算法比較

對(duì)比3 種算法，中心包圍算法顯示效率最低，左右分屏算法次之，左右上下分屏算法顯示效率最高。

推廣到更一般的情形，假設(shè)主屏分辨率為x1*y1，副屏分辨率為x2*y2，則：

（1）中心包圍算法。

（2）左右分屏算法。首先根據(jù)副屏起始點(diǎn)X 坐標(biāo)值是否為正值確定雙屏組合屬于左部還是右部，然后計(jì)算顯示效率。左部和右部顯示效率計(jì)算方式相同。

（3）左右上下分屏算法。首先確定當(dāng)前雙屏組合屬于左部還是右部，然后確定當(dāng)前組合屬于上下分屏還是嚴(yán)格左右分屏，判斷依據(jù)：上下分屏?xí)r副屏起始點(diǎn)X 坐標(biāo)值小于主屏寬度，而嚴(yán)格左右分屏?xí)r副屏起始點(diǎn)X 坐標(biāo)值等于主屏寬度。

比較式（18）、式（19）、式（20）可知，對(duì)于相同的雙屏組合，顯然左右上下分屏算法顯示效率最高。

綜上可知，左右上下分屏算法顯示效率最高，為雙屏最小完全覆蓋算法。其算法流程如圖10所示。

4 結(jié)語

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

本文針對(duì)屏幕水印應(yīng)用場(chǎng)景下的雙屏最小完全覆蓋算法進(jìn)行了研究。通過分析雙屏排列順序和分辨率的不同組合，提出三種完全覆蓋算法，然后推廣到一般情形，得到每種算法的顯示效率計(jì)算公式，最終得出左右上下分屏算法為雙屏最小完全覆蓋算法，同時(shí)設(shè)計(jì)出算法對(duì)應(yīng)的程序流程圖。雙屏最小完全覆蓋算法的研究，對(duì)多屏最小完全覆蓋算法提供了有意義的參考和基礎(chǔ)，同時(shí)有助于解決暗水印應(yīng)用場(chǎng)景下無法動(dòng)態(tài)控制水印顯示位置及顏色的問題。