• / 24
  • 下載費用:30 金幣  

層級詞典的創建.pdf

摘要
申請專利號:

CN201380075633.2

申請日:

2013.04.30

公開號:

CN105164665A

公開日:

2015.12.16

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 17/00申請日:20130430|||公開
IPC分類號: G06F17/00 主分類號: G06F17/00
申請人: 惠普發展公司,有限責任合伙企業; 普杜研究基金會
發明人: 德讓·德帕洛夫; 彼得·鮑爾; Y·G·郭; 賈恩·阿萊巴赫; 查理斯·A·博曼
地址: 美國德克薩斯州
優先權:
專利代理機構: 北京德琦知識產權代理有限公司11018 代理人: 康泉; 宋志強
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201380075633.2

授權公告號:

||||||

法律狀態公告日:

2018.10.02|||2016.01.13|||2015.12.16

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

一種創建層級詞典的方法,包括使用處理器從第一圖像提取多個符號;基于符號構造多個細化詞典條目,細化詞典條目形成細化詞典;將多個細化詞典條目分組成集群以形成多個細化詞典條目集群;以及針對細化詞典條目集群中的每個,構造多個直接詞典條目,直接詞典條目形成直接詞典。

權利要求書

權利要求書
1.  一種創建層級詞典的方法,包括使用處理器:
從第一圖像提取多個符號;
基于所述符號構造多個細化詞典條目,所述細化詞典條目形成細化詞典;
將多個所述細化詞典條目分組成集群以形成多個細化詞典條目集群;以及
針對所述細化詞典條目集群中的每個,構造多個直接詞典條目,所述直接詞典條目形成直接詞典。

2.  如權利要求1所述的方法,其中基于所述符號構造多個細化詞典條目包括:針對多個不同符號中的每個,構造多個細化詞典條目。

3.  如權利要求1所述的方法,其中基于所述符號構造多個細化詞典條目包括:
基于所述符號的相似度將所述符號分組成多個集群,每個單獨的符號集群包括相似的符號;以及
針對所述符號集群中的每個,構造多個細化詞典條目。

4.  如權利要求1所述的方法,還包括:
從后續圖像提取多個符號;
針對多個不同的符號中的每個,構造多個細化詞典條目;以及
通過組合根據在所述后續圖像之前的多個在前的圖像創建的多個詞典來構造存儲的詞典。

5.  如權利要求4所述的方法,還包括:
確定多個所述細化詞典條目是否匹配所述存儲的詞典的存儲的詞典條目,
其中,如果針對所述存儲的詞典中的多個細化詞典條目找到匹配,則使用匹配的所述存儲的詞典條目作為引用來對所述細化詞典條目進行編碼,并且
其中,如果針對所述存儲的詞典中的多個細化詞典條目未找到匹配,則通過使用所述直接詞典條目作為引用對不匹配的細化詞典條目進行編碼來創建新的直接詞典。

6.  如權利要求1所述的方法,還包括:
從后續圖像提取多個符號;
基于相似度將所述符號分組成多個集群,所述符號集群每個單獨地包括相似的符號;
針對所述符號集群中的每個,構造多個細化詞典條目;以及
通過組合從在所述后續圖像之前的多個在前的圖像創建的多個詞典來構造存儲的詞典。

7.  如權利要求1所述的方法,還包括:如果所述符號的字節數與所述直接詞典、所述細化詞典和所述存儲的詞典的字節數的組合超過閾值,則丟棄在所述存儲的詞典內的多個最不顯著的存儲的詞典條目。

8.  如權利要求5所述的方法,其中確定多個所述細化詞典條目是否匹配所述存儲的詞典的存儲的詞典條目包括:使用閾值條件熵估計來確定所述細化詞典條目之一是否匹配所述存儲的詞典條目之一。

9.  如權利要求1所述的方法,其中層級詞典創建的迭代的次數取決于所述符號的字節數和所述直接詞典、所述細化詞典和所述存儲的詞典的字節數的組合的在字節上的大小。

10.  一種圖像壓縮系統,包括:
處理器;以及
存儲器,通信地聯接到所述處理器,所述存儲器包括:
符號提取模塊,用于從多頁面二進制文檔中的后續圖像提取多個符號;
詞典構造模塊,用于基于所述符號構造多個細化詞典條目,所述細化詞典條目形成細化詞典;以及
存儲的詞典創建模塊,用于組合從多個在前的圖像得到的多個所述細化詞典和從多個在前的圖像得到的多個直接詞典,所述組合形成存儲的詞典,
其中所述詞典構造模塊還通過使用所述細化詞典對不匹配的細化詞典條目進行編碼來構造直接詞典,并且
其中所述細化詞典、所述直接詞典和所述存儲的詞典形成層級詞典。

11.  如權利要求10所述的系統,其中所述處理器使用所述符號傳輸或存儲所述層級詞典。

12.  如權利要求10所述的系統,其中所述系統被提供為在網絡上的服務。

13.  一種用于恢復在數據處理系統中的故障的計算機程序產品,所述計算機程序產品包括:
計算機可讀存儲介質,包括與其體現的計算機可用程序代碼,所述計算機可用程序代碼包括:
當由處理器執行時從多頁面文檔內的多個圖像的第一圖像提取多個符號的計算機可用程序代碼;
當由處理器執行時基于所述符號構造多個細化詞典條目的計算機可用程序代碼,所述細化詞典條目形成細化詞典;
當由處理器執行時將多個所述細化詞典條目分組成集群以形成多個細化詞典條目集群的計算機可用程序代碼;
當由處理器執行時針對所述細化詞典條目集群中的每個構造多個直接詞典條目的計算機可用程序代碼,所述直接詞典條目形成直接詞典;并且
通過組合從在所述第一圖像之后的多個后續圖像創建的多個詞典構造存儲的詞典,
其中所述直接詞典、所述細化詞典和所述存儲的詞典形成層級詞典。

14.  如權利要求13所述的計算機程序產品,還包括:
當由處理器執行時確定多個所述細化詞典條目是否匹配所述存儲的詞典的存儲的詞典條目的計算機可用程序代碼;
當由處理器執行時如果針對所述存儲的詞典中的多個細化詞典條目找到匹配則通過使用匹配的所述存儲的詞典條目作為引用對所述細化詞典條目進行編碼的計算機可用程序代碼;以及
當由處理器執行時如果針對所述存儲的詞典中的多個細化詞典條目未找到匹配則通過使用所述直接詞典條目作為引用對不匹配的細化詞典條目進行編碼來創建新的直接詞典的計算機可用程序代碼。

15.  如權利要求13所述的計算機程序產品,還包括當由處理器執行時對所述層級詞典和所述符號進行解碼以重新創建所述第一圖像和所述后續圖像的無損版本或有損版本的計算機可用程序代碼。

說明書

說明書層級詞典的創建
背景技術
隨著在計算設備之間傳輸的數據的量和在那些計算設備上的數據的存儲量的指數增加,圖像壓縮是用于減少代表圖像的數據的量的技術。圖像壓縮的使用有助于存儲圖像所需的空間或計算資源的數量以及發送圖像所需的帶寬的配給。
附圖說明
附圖示出本文所述的原理的各種示例且是說明書的一部分。所示示例僅為了說明而給出,且并不限制權利要求的范圍。
圖1是根據本文所述的原理的一個示例的用于創建在二進制文檔圖像壓縮中使用的多個層級詞典的數據處理系統的圖。
圖2A是示出根據本文所述的原理的一個示例的無損層級詞典創建方法的流程圖。
圖2B是示出根據本文所述的原理的一個示例的有損層級詞典創建方法的流程圖。
圖3是根據本文所述的原理的一個示例的層級詞典的方框圖。
圖4A是示出根據本文所述的原理的一個示例的多頁面文檔的連續頁面的無損層級詞典創建方法的流程圖。
圖4B是示出根據本文所述的原理的一個示例的多頁面文檔的連續頁面的有損層級詞典創建方法的流程圖。
圖5是根據本文所述的原理的一個示例的多頁面文檔的連續頁面的層級詞典的方框圖。
圖6是根據本文所述的原理的一個示例的描繪通過多種壓縮方法相對于IS-WXOR的壓縮比提高的曲線圖。
圖7A和圖7B是根據本文所述的原理的一個示例的描繪通過多種詞典設計方法得到的詞典條目數的曲線圖。
圖8是根據本文所述的原理的一個示例的描繪使用三種詞典壓縮方法的比特率的比較的曲線圖。
在全部附圖中,相同的參考數字標示類似的但不一定相同的元件。
具體實施方式
二進制文檔圖像壓縮用于文檔掃描、存儲和傳輸。用戶常常希望壓縮單頁面和多頁面二進制文檔圖像。由于圖像可從同一文檔源的連續頁面被處理,在多頁面二進制文檔內的圖像當中有信息冗余的可能性較高。本文描述了圖像當中的這種類型的信息冗余的利用,以便提高多頁面二進制文檔圖像壓縮的壓縮比。
本文描述了多頁面二進制文檔圖像壓縮的動態層級詞典(HD)設計。可結合本系統和方法使用任何數量的圖像壓縮方法。一個這樣的方法是由聯合二值圖像專家組開發的JBIG2圖像壓縮標準利用的方法。JBIG2標準可用于二進制文檔圖像壓縮,因為它比其它傳真編碼標準實現高得多的壓縮比。然而,雖然將在描述本系統和方法時使用JBIG2,可結合本動態HD使用任何圖像壓縮方法。
HD方法通過使用三種方法來利用多頁面二進制文檔的圖像當中的信息冗余。首先,層級詞典被構建以便每個頁面保持更多的信息用于未來使用。其次,層級詞典在存儲器中被動態地更新以在內存約束下保持盡可能多的信息。第三,條件熵估計技術更有效地利用所保存的信息。在本文呈現的實驗結果證明,與其它技術相比,通過HD技術的壓縮比提高為近似14%。
如在本說明書中和在所附權利要求中使用的,術語“圖像”應該被廣泛地理解為文檔的頁面的任何二進制表示。文檔可包括多個頁面,且因此可包括相等數量的圖像。
此外,如在本說明書中和在所附權利要求中使用的,術語“多個”或類似語言應該被廣泛地理解為包括1到無限的任何正數;零不應該理解為數字,而應該理解為沒有數字。
在下面的描述中,為了說明的目的,闡述了很多特定的細節,以便提供對本系統和方法的徹底理解。然而對本領域技術人員將明顯,可在沒有這些特定細節的情況下實施本裝置、系統和方法。在說明書中對“示例”或類似語言的提及意指關于那個示例描述的特定的特征、結構或特性如所描述的被包括,但可以不包括在其它示例中。
現在轉到附圖,圖1是根據本文所述的原理的一個示例的用于創建在二進制文檔圖像壓縮中使用的多個層級詞典的數據處理系統100的圖。可在任何數據處理場景中利用數據處理系統100,數據處理場景包括例如像軟件即服務(SaaS)、平臺即服務(PaaS)、基礎設施即服務(IaaS)、應用程序接口(API)即服務(APIaas)、其它形式的網絡服務或其組合那樣的云計算服務。此外,可在公共云網絡、私有云網絡、混合云網絡、其它形式的網絡或其組合中使用數據處理系統100。在一個示例中,由 數據處理系統100提供的方法由例如第三方提供為網絡上的服務。在另一示例中,由數據處理系統100提供的方法由本地管理員執行。
此外,可在單個計算設備內利用數據處理系統100。在該數據處理場景中,單個計算設備可利用層級詞典和本文所述的其它相關方法來掃描、存儲和/或傳輸單頁面或多頁面文檔的壓縮版本。
為了實現其期望功能,數據處理系統100包括各種硬件部件。在這些硬件部件當中的可以是多個處理器102、多個數據存儲設備104、多個外圍設備適配器106和多個網絡適配器108。可通過使用多個總線和/或網絡連接來互連這些硬件部件。在一個示例中,可經由總線107通信地聯接處理器102、數據存儲設備104、外圍設備適配器106和網絡適配器108。
處理器102可包括從數據存儲設備104檢索可執行代碼并執行可執行代碼的硬件體系結構。根據本文所述的本說明書的方法,可執行代碼在由處理器102執行時可促使處理器102至少實現層級詞典創建和二進制文檔圖像壓縮的功能。在執行代碼的過程中,處理器102可從多個其余硬件單元接收輸入并向多個其余硬件單元提供輸出。
數據存儲設備104可存儲數據,例如由處理器102或其它處理設備執行的可執行程序代碼。如將討論的,數據存儲設備104可具體存儲處理器102執行來實現至少本文所述的功能的多個應用程序。
數據存儲設備104可包括各種類型的存儲器模塊,包括易失性存儲器和非易失性存儲器。例如,本示例的數據存儲設備104包括隨機存取存儲器(RAM)111、只讀存儲器(ROM)112和硬盤驅動器(HDD)存儲器113。也可利用很多其它類型的存儲器,且本說明書設想如可適合本文所述的原理的特定應用的在數據存儲設備104中的很多不同類型的存儲器的使用。在某些示例中,可針對不同的數據存儲需要使用在數據存儲設備104中的不同類型的存儲器。例如,在某些示例中,處理器102可從只讀存儲器(ROM)112引導,在硬盤驅動器(HDD)存儲器113中維持非易失性存儲并執行存儲在隨機存取存儲器(RAM)111中的程序代碼。
通常,數據存儲設備104可包括計算機可讀介質、計算機可讀存儲介質或非瞬態計算機可讀介質等。例如,數據存儲設備104可以是但不限于電子、磁性、光學、電磁、紅外或半導體系統、裝置或設備或前述項的任何適當組合。計算機可讀存儲介質的更具體的示例可包括例如下列項:具有多個導線的電連接、便攜式計算機磁盤、硬盤、隨機存取存儲器(RAM)、只讀存儲器(ROM)、可擦除可編程只讀存儲器(EPROM或閃存)、便攜式光盤只讀存儲器(CD-ROM)、光學存儲設備、磁性存儲設備或前述項的任何適當的組合。在該文檔的上下文中,計算機可讀存儲介質可以是可包含或 存儲由指令執行系統、裝置或設備使用或結合指令執行系統、裝置或設備使用的程序的任何有形介質。在另一示例中,計算機可讀存儲介質可以是可包含或存儲由指令執行系統、裝置或設備使用或結合指令執行系統、裝置或設備使用的程序的任何非瞬態介質。
在數據處理系統100中的硬件適配器106使處理器102能夠與在數據處理系統100外部和內部的各種其它硬件元件接口。例如,外圍設備適配器106可提供像顯示設備110那樣的輸入/輸出設備的接口或訪問像外部存儲設備120那樣的其它外部設備。可提供顯示設備110以允許用戶與數據處理系統100交互并實現數據處理系統100的功能。外圍設備適配器106也可創建處理器102與打印機、顯示設備110或其它媒體輸出設備之間的接口。網絡適配器108可提供在例如網絡內的其它計算設備的接口,從而實現數據處理系統100與位于網絡內的其它設備之間的數據傳輸。
數據處理系統100還包括在多個層級詞典的創建和二進制文檔圖像壓縮中使用的多個模塊。在數據處理系統100內的各種模塊可被單獨地執行。在該示例中,各種模塊可被存儲為單獨的計算機程序產品。在另一示例中,在數據處理系統100內的各種模塊可在多個計算機程序產品內組合,每個計算機程序產品包括多個模塊。
數據處理系統100可包括符號提取模塊140,當由處理器102執行時,符號提取模塊140從在單頁面或多頁面二進制文檔中的多個圖像提取多個符號。在一個示例中,符號提取模塊140提取在大約300dpi下是大約30×20像素圖像的文本的多個單獨符號。在一個示例中,符號提取模塊140被存儲在數據處理系統100的數據存儲設備104內,并且是處理器102可訪問和可執行的。在另一示例中,符號提取模塊140被存儲在例如服務器設備上并在服務器設備上經由云計算服務為了如上所述的數據處理系統100的用戶的利益而被執行。
數據處理系統100還可包括編碼模塊142,當由處理器102執行時,編碼模塊142對直接詞典和細化詞典進行編碼,以及對符號進行編碼。在一個示例中,編碼模塊142被存儲在數據處理系統100的數據存儲設備104內,并由處理器102可訪問和可執行。在另一示例中,編碼模塊142被存儲在例如服務器設備上并在服務器設備上通過云計算服務為了如上所述的數據處理系統100的用戶的利益而被執行。
數據處理系統100還可包括存儲的詞典創建模塊144,當由處理器102執行時,存儲的詞典創建模塊144根據在前的頁面創建包括所有詞典的并集的存儲的詞典。在一個示例中,存儲的詞典創建模塊144被存儲在數據處理系統100的數據存儲設備104內,并由處理器102可訪問和可執行。在另一示例中,存儲的詞典創建模塊144被存 儲在例如服務器設備上并在服務器設備上通過云計算服務為了如上所述的數據處理系統100的用戶的利益而被執行。
數據處理系統100還可包括詞典構造模塊146,當由處理器102執行時,詞典構造模塊146構造多個細化詞典和直接詞典。在一個示例中,詞典構造模塊146被存儲在數據處理系統100的數據存儲設備104內,并由處理器102可訪問和可執行。在另一示例中,詞典構造模塊146被存儲在例如服務器設備上并在服務器設備上通過云計算服務為了如上所述的數據處理系統100的用戶的利益而被執行。
如上面提到的,JBIG2壓縮標準利用二進制圖像壓縮的有效方法。可結合本系統和方法使用的其它圖像壓縮方法可包括例如由ITU電信標準化部門(ITU-T)確定的T.4、T.6和T.82(即JBIG1)或由ITU-T、國際電工技術委員會(IEC)或國際標準化組織(ISO)等標準化的其它圖像壓縮方法。JBIG2壓縮的高壓縮比來自其詞典符號編碼方法。JBIG2編碼器可首先將文檔分成連接的組成部分或符號。文檔可以是單頁面文檔或多頁面文檔。此外,文檔可包括文本、藝術線條、表格和圖形元素。JBIG2編碼器通過對來自圖像的符號的子集進行編碼來創建詞典。所有其余符號然后使用詞典條目作為引用被編碼。
存在兩種使用JBIG2編碼器來壓縮多頁面文檔圖像的方法。第一種方法包括單獨和獨立地壓縮每個頁面。這可被稱為IS方法。IS方法不利用在文檔內的多個頁面當中的信息冗余。因此,JBIG2的壓縮比實質上低于本系統和方法所提供的壓縮比,且可實質上被提高。
使用JBIG2編碼器來壓縮多頁面文檔圖像的另一方法是提前加載所有頁面并將所有頁面壓縮在一起。這種方法可充分利用在頁面當中的信息冗余,但不切實際,因為其消耗相對太多的內存。在一些情況下,由于內存約束,JBIG2編碼器只加載一個頁面或甚至一個頁面的一部分來壓縮,且直到壓縮完成才加載下一頁面。以這種方式,JBIG2壓縮方法不利用在不同頁面當中的信息冗余,使得從內存消耗方面來說變得不實際。
本文描述了多頁面二進制文檔圖像壓縮的動態層級詞典設計方法(HD)。本系統和方法描述在給定內存約束下如何提高編碼多頁面圖像的壓縮比。本系統和方法使用層級詞典來針對多頁面文檔內的多個頁面中的每個構造附加的詞典條目。此外,本公開描述動態詞典更新策略,其在內存約束被滿足時丟棄多個“最不顯著的”詞典條目。進一步地,本系統和方法合并“條件熵”估計策略以測量兩個詞典條目之間的信息冗余。下面描述的實驗結果證明,HD方法相對于以前的壓縮方法產生較高的壓縮比。
包括JBIG2壓縮方法的一些壓縮方法允許保留詞典條目但不是來自多頁面文檔中的在前的頁面的符號,用于未來使用。因此,在當前頁面被編碼之后,存儲器設備可保留更多的詞典條目。這些附加的詞典條目可用于對在多頁面文檔內的多個后續頁面進行編碼,且因此可對后面的頁面實現較高的壓縮比。現在將結合圖2A、圖2B和圖3更詳細地描述單頁面的更多詞典條目的構造。
圖2A是示出根據本文所述的原理的一個示例的無損層級詞典創建方法的流程圖。圖2B是示出根據本文所述的原理的一個示例的有損層級詞典創建方法的流程圖。圖3是根據本文所述的原理的一個示例的層級詞典300的方框圖。在單個頁面只有一個詞典的構造中,在詞典內可包括過多的詞典條目,這又會降低單個頁面的壓縮比。這是因為相對大量的位將被用于對詞典本身進行編碼。本層級詞典結構可通過產生直接詞典來對細化詞典進行編碼從而產生大詞典大小,但具有小文件大小懲罰。
為了增加詞典條目數,同時仍然提供相對較小的文件大小懲罰,使用本層級詞典技術。本層級詞典技術通過創建第一詞典來對第二詞典進行編碼從而實現這個目的,如在圖2A、圖2B和圖3中描繪的。再次,圖2A是示出根據本文所述的原理的一個示例的無損層級詞典創建方法的流程圖。如在圖2A中描繪的,執行符號提取模塊140的處理器(圖1,102)從第一圖像提取(塊201)多個符號(圖3,306)。
執行編碼模塊(圖1,142)的處理器對可被稱為直接詞典(圖3,302)的第一詞典進行編碼。在一個示例中,直接詞典(圖3,302)使用在JBIG2標準中描述的直接編碼模式被編碼。執行編碼模塊(圖1,142)的處理器(圖1,102)使用在JBIG2標準中描述的細化編碼模式并使用直接詞典(圖3,302)作為引用對被稱為細化詞典(圖3,304)的第二詞典進行編碼。細化詞典(圖3,304)非常有效地壓縮,因為細化編碼使用來自直接詞典(圖3,302)的引用符號來對細化詞典(圖3,304)中的每個新符號進行編碼。可接著使用細化詞典(圖3,304)作為引用對在圖像中的所有符號(圖3,306)進行編碼。在一個示例中,直接詞典(圖3,302)相對小于細化詞典(圖3,304)。
在一個示例中,任何數量的細化詞典可被編碼。在該示例中且繼續上面的描述,可使用在JBIG2標準中描述的細化編碼模式并使用細化詞典(圖3,304)作為引用對第二細化詞典進行編碼。同樣,可使用在JBIG2標準中描述的細化編碼模式并使用第二細化詞典作為引用對第三細化詞典進行編碼。因此,即使在圖3中只描繪單個直接詞典(圖3,302)和單個細化詞典(圖3,304),對層級詞典進行編碼的這個過程也可被執行任何次數的迭代以得到任何數量的層級詞典(圖3,302,304)。
為了構造圖3的無損層級詞典300,可使用自底向上過程。圖2A的方法可通過從第一圖像或頁面提取(塊201)多個符號(圖3,306)開始。符號(圖3,306)的提取可由執行符號提取模塊(圖1,140)的處理器(圖1,102)執行。執行詞典構造模塊(圖1,146)的處理器(圖1,102)通過復制符號的位圖來針對多個不同的符號中的每個構造(塊202)多個細化詞典條目。細化詞典條目形成細化詞典(圖2,304)。通過使用這個策略,所有符號的位圖信息可保持在存儲器中。
處理器(圖1,102)將類似的細化詞典條目分組(塊203)成集群,且每個集群的一個代表性細化詞典條目被創建。代表性細化詞典條目是形成直接詞典的詞典條目。因此,執行詞典構造模塊(圖1,146)的處理器(圖1,102)構造(塊204)單獨的細化詞典條目集群中的每個的多個直接詞典條目。在一個示例中,為了執行聚類,可使用基于“條件熵”估計的詞典索引和設計方法。該基于條件熵估計的詞典索引和設計方法在上面被提到過且將在下面更詳細地被描述。
圖2A描繪無損層級詞典創建方法。如上面提到的,圖2B是示出根據本文所述的原理的一個示例的有損層級詞典創建方法的流程圖。為了構造圖3的有損層級詞典300,可再次使用自底向上過程。圖2B的方法可通過從第一圖像或頁面提取(塊211)多個符號(圖3,306)開始。符號(圖3,306)的提取可由執行符號提取模塊(圖1,140)的處理器(圖1,102)執行。處理器(圖1,102)基于符號(圖3,306)的相似度將符號(圖3,306)分組(塊212)成多個集群,每個單獨的符號集群包括相似的符號(圖3,306)。
執行詞典構造模塊(圖1,146)的處理器(圖1,102)針對符號集群中的每個構造(塊213)多個細化詞典條目。處理器(圖1,102)將類似的細化詞典條目分組(塊214)成集群,且針對集群中的每個創建一個代表性細化詞典條目。代表性細化詞典條目是形成直接詞典的詞典條目。因此,執行詞典構造模塊(圖1,146)的處理器(圖1,102)針對單獨的細化詞典條目集群中的每個構造(塊215)多個直接詞典條目。再次,在一個示例中,為了執行聚類,可使用基于“條件熵”估計的詞典索引和設計方法。該基于條件熵估計的詞典索引和設計方法將在下面更詳細地被描述。
現在將結合圖4A、圖4B和圖5描述對文檔的連續頁面的編碼。圖4A是示出根據本文所述的原理的一個示例的多頁面文檔的連續頁面的無損層級詞典創建方法的流程圖。圖4B是示出根據本文所述的原理的一個示例的多頁面文檔的連續頁面的有損層級詞典創建方法的流程圖。圖5是根據本文所述的原理的一個示例的多頁面文檔的連續頁面的層級詞典500的方框圖。在一些情況下,多個頁面可存在于單個文檔內。在這些多頁面二進制文檔中,在多頁面文檔內的圖像或頁面當中有信息冗余的可能性 較高,其中在圖像當中的這種類型的信息冗余的利用提高多頁面二進制文檔圖像壓縮的壓縮比。因此,對于在多頁面文檔內的連續頁面,被表示為的存儲的詞典(圖5,501)用于第k頁,其中k≠1。圖4A的無損層級詞典創建方法可由處理器(圖1,102)執行符號提取模塊140開始,符號提取模塊140從多頁面文檔的第k頁提取(塊401)多個符號(圖5,506)。再次,多頁面文檔的第k頁不是多頁面文檔的第一頁,而是其后的任何數量的后續頁面。執行詞典構造模塊(圖1,146)的處理器(圖1,102)針對多個不同符號中的每個構造(塊402)多個細化詞典條目以形成細化詞典(圖5,504)。
通過組合從在多頁面文檔內的在前的頁面創建的細化詞典(圖5,504)和直接詞典(圖5,502)由執行存儲的詞典創建模塊(圖1,144)的處理器(圖1,102)創建(塊403)存儲的詞典(圖5,501)。當沒有在系統100內強加的內存約束時,存儲的詞典(圖5,501)包括來自在前的頁面的所有詞典的并集。存儲的詞典(圖5,501)是來自多頁面文檔的在前的頁面的所有詞典的削減的并集。下面將更詳細地描述內存約束被強加在系統(圖1,100)上的情況。
因此,細化詞典(圖5,504)由執行編碼模塊(圖1,142)的處理器形成(塊403),并包括在第k頁中的每個唯一的符號作為在細化詞典(圖5,504)中的條目。圖4A的方法可通過確定(塊404)是否在存儲的詞典(圖5,501)中找到細化詞典條目的匹配來繼續。對于給定細化詞典條目中的每個,可在存儲的詞典中找到(塊404,確定“是”)匹配以有效地對細化詞典進行編碼(塊405)。執行編碼模塊(圖1,142)的處理器(圖1,102)使用匹配的存儲的詞典條目作為引用來進行編碼(塊405)。在大部分情況下,在細化詞典(圖5,504)中的條目將具有在存儲的詞典(圖5,501)中的良好匹配。因此,在這些情況下,細化詞典(圖5,504)被非常有效地編碼。
然而,在一些實例中,可能存在不具有在存儲的詞典(圖5,501)中的良好匹配(塊404,確定“否”)的細化詞典條目。為了對這些不匹配的細化詞典條目進行編碼,執行編碼模塊142的處理器(圖1,102)形成(塊406)由Dk表示的新的直接詞典(圖5,502)。如上面類似地描述的,使用基于條件熵估計的詞典索引和設計方法來構建直接詞典(圖5,502)。基于條件熵估計的詞典索引和設計方法有助于確定是否可在存儲的詞典(圖5,501)中找到給定細化詞典條目的良好匹配。因此,在細化詞典(圖5,504)中的一些條目使用存儲的詞典(圖5,501)被編碼,而其余部分使用直接詞典(圖5,502)被編碼。在多頁面文檔的第k頁的圖像中的所有符號(圖5,506)可接著使用細化詞典(圖5,504)作為引用被編碼。
上面的示例過程可通過使用處理器確定(塊407)在多頁面文檔中是否有待分析的后續頁面來繼續。如果在文檔中有待分析的后續頁面(塊407,確定“是”),則過程可循環回到塊401,且可針對新的后續頁面重新創建存儲的詞典(圖5,501)。如果在文檔中沒有待分析的后續頁面(塊407,確定“否”),則過程可終止。
已描述了圖4A的無損層級詞典創建方法,現在將描述有損層級詞典創建方法。再次,圖4B是示出根據本文所述的原理的一個示例的多頁面文檔的連續頁面的有損層級詞典創建方法的流程圖。
圖4A的有損層級詞典創建方法可由執行符號提取模塊140的處理器(圖1,102)從多頁面文檔的第k頁提取(塊411)多個符號(圖5,506)而開始。再次,多頁面文檔的第k頁不是多頁文檔的第一頁,而是其后的任何數量的后續頁面。處理器(圖1,102)基于相似度將符號(圖5,506)分組(塊412)成多個集群。因而產生的符號集群每個單獨地包括相似的符號。執行詞典構造模塊(圖1,146)的處理器(圖1,102)針對符號集群中的每個構造(塊413)多個細化詞典條目以形成細化詞典(圖5,504)。
通過組合從在多頁面文檔內的在前的頁面創建的細化詞典(圖5,504)和直接詞典(圖5,502)由執行存儲詞典創建模塊(圖1,144)的處理器(圖1,102)創建存儲的詞典(圖5,501)。再次,當沒有在系統100內強加的內存約束時,存儲的詞典(圖5,501)包括來自在前的頁面的所有詞典的并集。存儲的詞典(圖5,501)是來自多頁面文檔的在前的頁面的所有詞典的削減的并集。下面將更詳細地描述內存約束被強加在系統(圖1,100)上的情況。
圖4B的方法可通過確定(塊415)是否在存儲的詞典(圖5,501)中找到細化詞典條目的匹配來繼續。對于給定細化詞典條目中的每個,可在存儲的詞典中找到(塊415,確定“是”)匹配以有效地對細化詞典進行編碼(塊416)。執行編碼模塊(圖1,142)的處理器(圖1,102)使用匹配的存儲的詞典條目作為引用來編碼(塊416)。在大部分情況下,在細化詞典(圖5,504)中的條目將具有在存儲的詞典(圖5,501)中的良好匹配。因此,在這些情況下,細化詞典(圖5,504)被非常有效地編碼。
然而,在一些實例中,可能存在不具有在存儲的詞典(圖5,501)中的良好匹配(塊415,確定“否”)的細化詞典條目。為了對這些不匹配的細化詞典條目進行編碼,執行編碼模塊142的處理器(圖1,102)形成(塊417)由Dk表示的新的直接詞典(圖5,502)。如上面類似地描述的,使用基于條件熵估計的詞典索引和設計方法來構建直接詞典(圖5,502)。基于條件熵估計的詞典索引和設計方法有助于確定是 否可在存儲的詞典(圖5,501)中找到給定細化詞典條目的良好匹配。因此,在細化詞典(圖5,504)中的一些條目使用存儲的詞典(圖5,501)被編碼,而其余部分使用直接詞典(圖5,502)被編碼。在多頁面文檔的第k頁的圖像中的所有符號(圖5,506)可接著使用細化詞典(圖5,504)作為引用被編碼。
上面的示例過程可通過使用處理器確定(塊418)在多頁面文檔中是否有待分析的后續頁面來繼續。如果在文檔中有待分析的后續頁面(塊418,確定“是”),則過程可循環回到塊401,且可為新的后續頁面重新創建存儲的詞典(圖5,501)。如果在文檔中沒有待分析的后續頁面(塊418,確定“否”),則過程可終止。
確定是否可在存儲的詞典(圖5,501)中找到給定細化詞典條目的良好匹配的標準基于條件熵估計(CEE)。令表示在中的第j個條目并且表示在中的第i個條目。通過下式找到在中的的最佳匹配:
d*=argminH^(dk,jr|dk,is)]]>等式1
dk,is∈Dks]]>
其中是給定時的條件熵的估計。如果給定d*時的的條件熵小于預定閾值TR,
H^(dk,jr|d*)TR]]>等式2
使用存儲的詞典條目d*作為引用被編碼。否則,不使用存儲的詞典(圖5,501)被編碼。因此,如果
H^(dk,jd|d*)>TR]]>等式3
則創建的新的直接詞典條目。在一個示例中,條件熵可以用其它函數例如XOR或WXOR代替,以便以較低的壓縮比為代價減小計算成本。
為了使上述方法變得實際,可維持存儲的詞典(圖5,501)的大小,以便不增長到超出可用內存大小,如上面提到的。在內存約束被強加在系統100內的場景中使用的方法是每當第k頁的所有詞典(圖5,501,502,504)的內存大小大于1Mb時丟棄一些存儲的詞典條目。閾值被選擇為1Mb,因為標準是至少具有用于詞典(圖5,501,502,504)的1Mb存儲量的解碼器。然而,所有詞典(圖5,501,502,504)的內存大小的任何閾值可被使用,且可以是用戶可定義的。
在一個示例中,第k頁的所有詞典(圖5,501,502,504)的詞典的內存大小是Dk、和的內存大小的總和,其可使用下式被計算。令MSD是符號詞典的存儲器尺寸(以字節為單位)并等于固定分量加上每符號分量。固定分量等于2^(直接編碼模板大小_加2^(細化編碼模板大小)+8K。每符號分量等于下式:
Σi=1N32+R(w(i)×h(i))8]]>等式4
其中w(i)是符號寬度,而h(i)是符號高度。每符號開銷32字節。
在上面的示例中,待丟棄的條目是滿足下面的兩個條件的存儲的詞典條目(1)條目不被中的任何條目引用;以及(2)條目是“最不顯著的”,最不顯著的被定義為:
m^=argminmdXOR(dk,ms,dk,n)]]>等式5
其中是不同于并屬于Dk、或的任何詞典條目。函數dXOR計算在兩個詞典條目之間的漢明距離。類似的詞典條目可具有更多共同的信息。因此,通過使用上述策略,在內存大小約束下盡可能多的總信息被維持在內存中。
上述方法可通過傳輸或存儲層級詞典300、500連同符號306、506用于以后處理來繼續。該以后處理可包括層級詞典300、500和符號306、506的解碼,以便重新創建在文檔內的一個或多個原始圖像的無損或有損版本。
圖2的方法的示例可由下面的實驗結果給出。測試圖像image01.pbm被壓縮,該測試圖像在300dpi下被掃描并具有3275×2525個像素的大小。基于XOR的一遍掃描算法(OP-XOR)用于將image01.pbm壓縮15次,每次具有不同的詞典大小。通過規定OP-XOR的不同參數值來得到不同的詞典大小。當針對在image01.pbm中的每個不同的符號創建一個詞典條目時,詞典條目數在2208被最大化。在這種情況下,位流文件大小是44.75KB。
通過復制符號的位圖中的每個來針對每個不同的符號構造在細化詞典中的一個條目。所有符號的位圖信息可存儲在數據存儲設備例如數據存儲設備104或數據處理系統100的外部存儲設備120中。在細化詞典中的詞典條目作為符號被處理,且細化詞典條目的直接詞典使用OP-XOR、OP-WXOR或條件熵估計(CEE)距離測量方法被構造。
在圖2中示出使用層級結構來對image01.pbm進行編碼的結果。使用層級OPXOR算法,得到2208個詞典條目,位流文件大小是31:20KB,其比通過沒有層級結構的OP-XOR得到的44:75KB小得多。使用層級CEE算法,也得到2208個詞典條目,且 位流文件大小是26:85KB。與沒有層級結構的CEE算法的情況相比,以1:45KB文件大小增加為代價得到多393:96%的詞典條目。
然而,調節OP-XOR的參數,確定在438個條目的詞典的情況下,位流文件大小是僅僅28.11KB。下面說明的條件熵估計(CEE)距離測量用于壓縮image01.pbm。雖然CEE距離測量不需要所規定的參數并產生較小的位流文件大小25.40KB,CEE距離測量只產生447個詞典條目,其比預期的2208個詞典條目少得多。因此,在不使用上面描述的層級詞典方法的情況下,以幾乎使文件大小加倍為代價得到大詞典。使用層級詞典方法,得到具有小文件大小懲罰的大詞典。
現在將描述本動態層級詞典(HD)方法與其它方法的比較,以便在實驗上展示本系統和方法的優點。在下面的實驗中的DSC方法基于在符號和詞典條目之間的相異度測量的加權漢明距離(WXOR)。對于本動態HD方法,使用兩個版本的DSC方法。第一個版本在上面被描述,并可被稱為DH-CEE,因為其使用條件熵估計(CEE)符號距離。結合這些實驗使用的這兩個DSC方法的第二個版本用WXOR相異度測量來代替CEE相異度測量,以便看到只歸因于本動態層級詞典方法的益處。這種方法可被稱為HD-WXOR方法。
測試圖像組可被稱為EEPaper,并包含從同一文檔的連續頁面掃描的9個圖像。所有這些圖像是300dpi,并具有3275×2525個像素。測試圖像主要包括文本,但一些圖像還包括藝術線條、表格和圖形元素。然而,在EEPapter內沒有一個測試圖像包括半色調。JBIG2無損文本模式用于所有實驗。詞典的閾值總內存使用被限制到小于1MB。除非另外陳述,所有方法的參數被調節,使得每個方法實現它們的最佳壓縮比。
在下面的實驗中,整個測試圖像組被壓縮。圖6是根據本文所述的原理的一個示例的描繪通過多種壓縮方法的相對于IS-WXOR的壓縮比提高的曲線圖。圖6描繪DH-CEE方法與可選的方法的比較。在圖6的曲線圖中,一切與使用WXOR相異度測量(IS-WXOR)構造的獨立和靜態詞典相關。注意,DH-CEE方法對于所有頁面具有最高壓縮比。對于整個測試圖像組,DH-CEE與IS-WXOR相比將壓縮比提高了28%,且與DSC相比提高了14%。
DH-CEE相對于DSC壓縮比提高的一個原因是DH-CEE針對每個頁面產生大得多的詞典。圖7A和圖7B是根據本文所述的原理的一個示例的描繪通過多種詞典設計方法得到的詞典條目數的曲線圖。如在圖7A和圖7B中描繪的,較大的詞典可以更有效地對文檔或圖像進行編碼。由DH方法產生的大詞典有效地對文檔進行編碼。對于DH-CEE和DH-WXOR,由于內存約束,在9頁測試文檔的第7頁之后,動態更新控 制它們的詞典的大小。然而,在使用DH-CEE時,只需要小開銷來對大詞典進行編碼。用下面的示例證明大詞典的有效編碼。
在下一示例中,DH方法被表現為允許使用下面的實驗以相對小的開銷編碼大詞典。DH-CEE和DSC方法用于創建在EEPaper中的第一頁的大詞典,且這些大詞典根據其用來對其詞典進行編碼的位數被比較。
由DH-CEE方法產生的細化詞典在大小上是大的,因為DH-CEE針對頁面中的不同的符號中的每個創建一個細化詞典條目。對于DSC方法,其參數被調節以得到與使用DH-CEE的細化詞典一樣大的單個詞典。圖8是根據本文所述的原理的一個示例的描繪使用三種詞典壓縮方法的比特率的比較的曲線圖。如在圖8中描繪的,通過使用DH-CEE得到的位流文件大小明顯小于使用DSC得到的位流文件大小。這是由于DH-CEE的層級結構。DH-CEE使用CEE-ID建立直接詞典以有效地對細化詞典進行編碼。也注意,DH-CEE導致最小編碼詞典。
通過DH-CEE的壓縮比提高也來自條件熵估計(CEE)。為了比較,探討DH-WXOR方法,該方法用WXOR代替CEE。首先,上面結合圖2的方法描述的單個頁面實驗使用DH-WXOR方法被重復。通過使用DH-WXOR和DH-CEE得到的細化詞典是相同的,因為它們使用相同的方法來創建它們的細化詞典。如在圖8中所示的,由于層級詞典設計,通過使用DH-WXOR得到的比特率小于使用DSC得到的比特率。另一方面,使用DH-WXOR的比特率大于DH-CEE的比特率。這是因為在DH-CEE中使用的CEE比在DH-WXOR中的WXOR提供詞典條目之間的信息冗余的更好測量。因此,DH-CEE創建更好的直接詞典來對細化詞典進行編碼。
上面結合使用DH-WXOR方法的EEPaper描述的多頁面實驗被重復。如圖6所示,與DSC相比,DH-WXOR將壓縮比提高了11%。該提高來自由在圖7B中描繪的DH-WXOR的動態層級設計產生的大詞典。另一方面,使用DH-WXOR的壓縮比比DH-CEE的壓縮比小大約4%。這是因為,基于CEE,DH-CEE比DH-WXOR方法創建更好的直接詞典并選擇更好的存儲的詞典條目以結合等式1對細化詞典進行編碼。
注意,所有的上述實驗都是在1MB內存約束下進行的。如圖7A所示,從第7頁被編碼以后,繼續進行的動態更新丟棄存儲的詞典條目。如果內存約束被解除,則不會有詞典條目被丟棄,且額外的內存將被消耗。然而,根據上面的實驗結果,額外的內存使用只將壓縮比提高小于1%。這是因為動態更新通過選擇最不顯著的存儲的詞典條目來最小化由丟棄的詞典條目引起的信息損失。
在本文參考根據本文所述的原理的示例的方法、裝置(系統)和計算機程序產品的流程圖說明和/或方框圖描述了本系統和方法的方面。流程圖說明和方框圖的每個塊 以及在流程圖說明和方框圖中的塊的組合可由計算機可用程序代碼實現。可將計算機可用程序代碼提供到通用計算機、專用計算機或其它可編程數據處理裝置的處理器來產生機器,使得計算機可用程序代碼在經由例如數據處理系統100的處理器102或其它可編程數據處理裝置執行時實現一個或多個流程圖和/或方框圖塊中規定的功能或動作。在一個示例中,計算機可用程序代碼可體現在計算機可讀存儲介質內;計算機可讀存儲介質是計算機程序產品的一部分。在一個示例中,計算機可讀存儲介質是非瞬態計算機可讀介質。
說明書和附圖描述用于創建用于圖像壓縮的層級詞典的系統和方法。方法可包括:從第一圖像提取多個符號;基于符號構造多個細化詞典條目,細化詞典條目形成細化詞典;將多個細化詞典條目分組成集群以形成多個細化詞典條目集群;以及針對細化詞典條目集群中的每個,構造多個直接詞典條目,直接詞典條目形成直接詞典。這些系統和方法可具有多個優點,包括:(1)創建無損系統,其中在壓縮和重構中沒有信息丟失;(2)提供更有效地對文檔內的符號進行編碼的大詞典的更有效存儲;(3)通過使用條件熵估計提供對詞典設計和編碼過程的編碼效率的進一步提高;以及(4)通過維持并利用來自在前的頁面的信息來對連續頁面進行編碼來提高編碼效率。用于多頁面二進制文檔圖像壓縮的本動態層級詞典(HD)設計方法通過維持并利用來自在前的頁面的信息來對連續頁面進行編碼來提高編碼效率。使用下面的技術,HD方法優于其它方法。首先,層級設計允許每個頁面更多的信息被維持。其次,動態更新有助于在內存大小約束下維持盡可能多的信息。第三,條件熵估計有助于更有效地利用所維持的信息。
前面的描述被提供來說明和描述所描述的原理的示例。該描述并不旨在詳盡無遺的或將這些原理限制到所公開的任何精確形式。按照上面的教導,很多修改和變型是可能的。

關 鍵 詞:
層級 詞典 創建
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:層級詞典的創建.pdf
鏈接地址:http://www.rgyfuv.icu/p-6409532.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图