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

朱永超，雷 浩

（成都飛機工業（集團）有限責任公司，四川成都 610031）

0 引言

涉密單位內網存在大量敏感信息，屏幕水?。?］能有效防止用戶有意或無意的拍照和截圖行為，以避免數據泄露［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 種方法均涉及暗水?。?3］，但只考慮了單屏顯示，未涉及雙屏及多屏顯示問題。梅強華等［14］提出一種自動檢測和動態改變屏幕分辨率設置程序，但水印的顯示要求屏幕具有固定的分辨率。付海濤等［15］針對傳感器網絡中節點的部署和覆蓋問題，提出一種完全覆蓋熱點區域的多重覆蓋算法。楊曉波等［16］提出一種基于最小覆蓋空域的機載預警雷達的多幀檢測前跟蹤方法，但屏幕水印場景中雙屏及多屏之間不存在多重覆蓋問題。趙福生等［17］探討不規則圖形能否完全覆蓋俄羅斯方塊圖形，分析L 形方塊覆蓋全部空間的條件，但雙屏覆蓋問題中研究的是完全覆蓋子圖形的最小空間大小。吳陳等［18］對有限集上相容關系以及對應完全覆蓋的基數進行分析估計，葛洪偉等［19］提出使用蟻群算法解決組合優化問題，臧文科等［20］提出用面上DNA 計算模型求解最小集合覆蓋問題?；诙嗥粮采w問題的復雜性考慮，以上幾種方法對多屏覆蓋方面的理論研究有指導意義，但缺乏計算機工程方面的指導。楊麗徙［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 左右上下分屏算法流程

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