用於半色調數字圖像的壓縮的方法以及計算設備的製作方法

2023-11-02 04:16:12 3

用於半色調數字圖像的壓縮的方法以及計算設備的製作方法
【專利摘要】本發明可以提供一種用於半色調數字圖像的壓縮的方法以及計算設備。基於mxn半色調矩陣和圖像的mxn像素塊，可以確定mxn像素塊的mxn半色調版本。可以對mxn半色調版本的行執行n路交錯以創建mnx1半色調段。可以將mnx1半色調段與緩衝區中的一個或多個半色調段相比較。基於該比較，可以輸出mnx1半色調段的文字碼字和表示，並且可以將mnx1半色調段的表示寫入緩衝區。可替代地，可以輸出重複碼字和重複值，並且可以將mnx1半色調段的至少一個表示寫入緩衝區。根據本發明，可以提供一種用於半色調數字圖像的壓縮的方法。
【專利說明】用於半色調數字圖像的壓縮的方法以及計算設備
【技術領域】
[0001]本發明涉及用於半色調(Halftoned)數字圖像的壓縮的方法。
【背景技術】
[0002]半色調是通過使用在尺寸、形狀或間距方面變化的點來模擬連續色調影像的技術。在基本二進位半色調方面具有單色調水平的這些點形成半色調點圖案。半色調點圖案的正確設計經由單色調水平的僅僅開/關標記提供半色調圖像中多色調和平滑陰影的外觀。

【發明內容】

[0003]本發明可以提供用於半色調數字圖像的壓縮的方法。
[0004]在示例實施例中，基於mxn半色調矩陣和圖像的第一 mxn像素塊，可以確定第一mxn像素塊的第一 mxn半色調版本。可以對第一 mxn像素塊的第一 mxn半色調版本的行執行η路交錯以創建第一 mnxl半色調段。第一 mnxl半色調段可以與先入先出(FIFO)緩衝區中的一個或多個半色調段相比較。如果所述第一 mnxl半色調段與所述FIFO緩衝區中的任意半色調段不相匹配，則可以輸出所述第一 mnxl半色調段的文字碼字和表示，並且可以將所述第一 mnxl半色調段的表示寫入所述FIFO緩衝區。如果所述第一 mnxl半色調段與所述FIFO緩衝區中的特定半色調段相匹配，則可以輸出重複碼字和重複值，並且可以將所述第一 mnxl半色調段的至少一個表示寫入所述FIFO緩衝區。
[0005]另外的實施例可以包括一種非暫時性計算機可讀介質，在所述計算機可讀介質上存儲有程序指令，該程序指令一旦由計算設備執行就導致該計算設備根據上述或其它示例實施例執行操作。
[0006]更多的實施例可以包括一種計算設備，所述計算設備包括:至少一個處理器、數據儲存器，以及在所述數據儲存器中的程序指令，所述程序指令一旦由該至少一個處理器執行就導致所述計算設備根據上述或其它示例實施例操作。
[0007]通過在適當之處參照附圖閱讀下列詳細描述，這些以及其它方面、優點和可替代物對於本領域普通技術人員來說將變得顯而易見。進一步，應當理解，在該
【發明內容】
部分以及該文件其它地方提供的描述旨在通過示例的方式而不是通過限制的方式示出所要求保護的主題。
[0008]根據本發明，可以提供用於半色調數字圖像的壓縮的方法。
【專利附圖】

【附圖說明】
[0009]圖1圖示根據示例實施例的列印設備。
[0010]圖2是圖解根據示例實施例的列印設備的計算部件的框圖。
[0011]圖3是圖解根據示例實施例的涉及列印設備的各種數據路徑的框圖。
[0012]圖4圖示根據示例實施例的半色調矩陣到圖像的像素的應用。[0013]圖5A圖示根據示例實施例的在圖像上平鋪的半色調矩陣。
[0014]圖5B圖示根據示例實施例的在具有列填充的圖像上平鋪的半色調矩陣。
[0015]圖6圖示根據示例實施例的圖像和圖像的放大部分。
[0016]圖7圖示根據示例實施例的具有列填充的圖像的半色調。
[0017]圖8圖示根據示例實施例的圖像半色調版本的部分的十六進位表示。
[0018]圖9圖示根據示例實施例的交錯圖像的半色調版本。
[0019]圖10圖示根據示例實施例的歷史緩衝區、先行緩衝區和新的段緩衝區。
[0020]圖11圖示根據示例實施例的壓縮後的半色調段的格式。
[0021 ] 圖12是根據示例實施例的流程圖。
[0022]圖13圖示根據示例實施例的歷史緩衝區、先行緩衝區和新的段緩衝區的操作，在該操作中，未找到先行緩衝區的段的匹配。
[0023]圖14圖示根據示例實施例的歷史緩衝區、先行緩衝區和新的段緩衝區的操作，在該操作中，找到先行緩衝區的兩段的匹配。
[0024]圖15圖示根據示例實施例的歷史緩衝區、先行緩衝區和新的段緩衝區的操作，在該操作中，未找到先行緩衝區的段的匹配。
[0025]圖16圖示根據示例實施例的歷史緩衝區、先行緩衝區和新的段緩衝區的操作，在該操作中，找到先行緩衝區的一段的匹配。
[0026]圖17圖示根據示例實施例的歷史緩衝區、先行緩衝區和新的段緩衝區的操作，在該操作中，因為使用了列填充而找到先行緩衝區的三段的匹配。
[0027]圖18圖示根據示例實施例的歷史緩衝區、先行緩衝區和新的段緩衝區的操作，在該操作中，找到先行緩衝區和新的段緩衝區的所有段的匹配，方便了擴展重複碼字的使用
[0028]圖19A、19B、19C和19D圖示了其中列填充的使用導致更有效率的半色調圖像壓縮的場景。
[0029]圖20是根據示例實施例的流程圖。
【具體實施方式】
[0030]在這裡描述示例方法和系統。可以進一步利用其它示例實施例或特徵，並且可以做出其它改變，只要不背離這裡呈現的主題的精神或範圍。在下列詳細描述中，參考形成該詳細描述的一部分的附圖。
[0031]這裡描述的示例實施例並不意味著是限制。將容易理解，在這裡一般描述的和在圖中示出的本發明的方面可以被布置、取代、組合、分離和以廣泛種類的不同配置被設計，所有這些在這裡被明確地預期。
[0032]1、導言
[0033]列印技術在過去的30多年間從產生僅僅黑色和白色圖像的基於簡單點矩陣的輸出設備演進到今天的能夠產生高解析度彩色圖像的基於高級雷射器的列印設備。另外，現代列印設備也可以用作複印機、掃描儀和傳真機。為了做這些，這些列印設備可能能夠存儲排隊用於列印或傳真的或者已被掃描的數目眾多的電子文件。因此，許多列印設備是專門格式的計算設備，該計算設備可以包括例如一個或多個處理器、數據儲存器和輸入/輸出接口。[0034]不管列印設備是否用在住宅、商業或其它類型的場所，列印設備可以是能夠通信連接至各種其它計算設備的共享資源。結果，在一些環境中，當數目眾多的計算設備可能正在向列印設備傳送電子文件用於列印時，列印設備的存儲需求可能相當高。通常，列印設備將每次以先到先服務的方式列印、複印、傳真和/或掃描一份電子文件。因此，列印設備可以存儲潛在的正在等待服務的大數目電子文件。由於數據儲存器(例如，諸如隨機存取存儲器(RAM)、固態存儲器、硬驅動存儲器和/或快閃記憶體之類的存儲器)的成本可能昂貴，因此為了降低列印設備的數據存儲需求而壓縮所存儲的電子文件可能是有利的。另外，由於一些電子文件可能被傳遞給列印設備和計算設備和/或從列印設備和計算設備傳遞，因此壓縮這些電子文件可能使傳遞更快並且使用較少的網絡容量。
[0035]而且，由於列印作業可能較大(例如，列印作業可能包括包含數以百計頁面的一份或多份電子文件)，因此在列印每個作業之前壓縮已排隊列印作業節省短期存儲空間。另夕卜，用戶可能想以長期存儲保存列印作業以在後來的時間進行列印。因此，壓縮列印作業可能允許更多的列印作業被保存。此外，存儲和從長期存儲器檢索大的列印作業的動作可以是慢的，但可以通過壓縮列印作業以使它們在尺寸方面較小來加速。
[0036]2、示例列印設備
[0037]圖1圖示示例列印設備100。列印設備100可以被配置為列印在各種類型物理輸出介質上部分存儲和/或完全存儲的電子文件。這些輸出介質包括但不限於各種尺寸和類型的紙張、字幕片等。列印設備100可以可互換地被稱之為「印表機」。
[0038]列印設備100可以用作例如個人計算機、伺服器設備、列印伺服器等的計算設備的本地外圍設備。在這些情況下，列印設備100可以通過例如串行埠電纜、並行埠電纜、通用串行總線(USB)電纜、Firewire (IEEE1394)電纜或高解析度多媒體接口(HDMI)電纜的電纜附接至計算設備。因此，計算設備可以用作用於列印設備100的電子文件的源。
[0039]另一方面，列印設備100可以包括有線或無線網絡接口，例如乙太網或802.11(Wifi)接口。如此被配置，列印設備100可以用作用於在網絡上能與列印設備100通信的任意數目計算設備的列印設備。在一些實施例中，列印設備100可以同時用作本地外圍設備和聯網印表機兩者。
[0040]為了使用列印設備100，計算設備可以安裝一個或多個印表機驅動器。這些印表機驅動器可以包括將待列印的電子文件從存儲在計算設備上的各種本地表示轉換成由列印設備100支持的一個或多個表示的軟體組件。
[0041]無論如何，列印設備100可以被考慮為是計算設備，並且可以實現列印相關的任務和非列印相關的任務兩者。
[0042]如以上所指出的那樣，列印設備100還可以包括複印機、傳真機和掃描儀功能。在一些實施例中，列印設備100可以使用掃描儀功能來方便複印機和/或傳真機功能。例如，列印設備100可以將物理文件掃描成電子格式，並且然後列印所得到的電子文件以提供副本，和/或經由電話接口傳送所得到的電子文件以提供傳真功能。
[0043]為了支持列印設備100的各種功能，列印設備100可以包括文件進紙器/輸出託盤102、紙張儲存器104、用戶接口 106、掃描元件108以及機殼110。應當理解，列印設備可以處理廣泛種類的形式。因此，列印設備100可以包括比圖1中圖示的更多或更少的部件，和/或採用與圖1中圖示的不同方式布置的部件。[0044]文件進紙器/輸出託盤102可以保留待掃描、複印或傳真的物理文件(例如，一張或多張紙的堆)。有利地，文件進紙器/輸出託盤102可以允許列印設備100自動餵送多個物理文件以通過列印設備100進行處理，而不需要人工幹預。文件進紙器/輸出託盤102還可以包括用於保留已由列印設備100處理的物理文件的一個或多個分離輸出託盤。這些可以包括已由列印設備100掃描、複印或傳真的物理文件以及已由例如列印設備100的傳真和/或複印功能產生的物理文件。
[0045]紙張儲存器104可以包括用於各種類型物理介質的託盤和/或餵送元件。例如，紙張儲存器104可以包括用於872xll英寸紙、A4紙、信頭紙、信封等的分離託盤。對於列印設備100的涉及輸出物理介質的任意功能(例如，列印、複印和/或接收傳真)，紙張儲存器104可以供應物理介質。
[0046]用戶接口 106可以方便列印設備100與人類或非人類用戶的交互，例如用於從用戶接收輸入和向用戶提供輸出。因此，用戶接口 106可以包括諸如鍵區、鍵盤、觸敏或存在敏感性(presence-sensitive)面板、操縱杆、麥克風、照相機和/或攝影機的輸入部件。用戶接口 106還可以包括一個或多個輸出部件，例如顯示屏(其例如可以與存在敏感性面板組合)、陰極射線管(CRT)、液晶顯示器(IXD)、基於發光二極體(LED)的顯示器、使用數字光處理(DLP? )技術的顯示器、電燈泡和/或一個或多個現在已知或後來開發的其它類似設備。用戶接口 106還可以被配置為能夠經由揚聲器、揚聲器插孔、音頻輸出埠、音頻輸出設備、耳機和/或現在已知或在未來隨後開發的其它類似設備產生可聽輸出。
[0047]掃描元件108可以是玻璃面板，在該玻璃面板下，可移動光源操作以掃描被放置在玻璃面板頂部上的物理介質。可替代地，在玻璃面板下的數字相機可以通過拍攝物理介質的圖片而「掃描」被放置在玻璃面板頂部上的物理介質。被掃描物理介質的圖像可以存儲在與列印設備100相關聯的數據儲存器中。
[0048]機殼110可以包括包含列印設備100的各種部件(例如文件進紙器/輸出託盤102、紙張儲存器104、用戶接口 106和掃描元件108)和/或與列印設備100的各種部件互聯的物理外殼。另外，機殼110可以容納圖1中未示出的其它部件。例如，機殼110可以包含一個或多個硒鼓、液體噴墨、傳送帶、墨輥和/或電源。進一步，機殼110可以包括諸如有線和/或無線網絡接口、電話接口(例如RJ45插孔)、USB接口、藍牙?接口、讀卡器埠等的通信接口。
[0049]而且，由於列印設備100可以基於通用和/或特定設計的計算設備部件，因此機殼110還可以容納一些或所有這些部件。為此，圖2圖示可以包括在列印設備100中的計算設備部件200 (例如，計算設備的功能元件)的示例實施例。
[0050]計算設備部件200可以包括處理器202、數據儲存器204和輸入/輸出功能206，所有這些可以通過系統總線208或類似機制連接。處理器202可以包括一個或多個中央處理單元(CPU)，例如一個或多個通用處理器和/或一個或多個專用處理器(例如，特定用途集成電路(ASIC)或數位訊號處理器(DSP)等)。
[0051]數據儲存器204依次可以包括易失性和/或非易失性數據儲存器，並且可以整體或部分地與處理器202集成。數據儲存器204可以存儲可由處理器202執行的程序指令和由這些指令操縱的數據以實現這裡描述的各種方法、過程或功能。可替代地，這些方法、過程或功能可以由硬體、固件和/或硬體、固件和軟體的任意組合定義。因此，數據儲存器204可以包括有形、非暫時性計算機可讀介質，在這些介質上存儲有一旦由一個或多個處理器執行就導致列印設備100實現在本說明書或附圖中公開的任意方法、過程或功能的程序指令。
[0052]輸入/輸出功能206可以包括參照用戶接口 106描述的任意功能和/或元件。因此，輸入/輸出功能206可以用於配置和/或控制處理器202的操作。輸入/輸出功能206還可以基於由處理器202執行的操作提供輸出。
[0053]應當理解，列印設備的這些示例被提供用於示例目的。進一步，除了和/或可替代於上面示例，在其它可能性之中，印表機和計算機技術的其它組合和/或子組合也可以存在，只要不背離這裡實施例的範圍。
[0054]圖3圖示可能數據路徑中由列印設備100處理的電子文件的表示可能通過的一些數據路徑。在圖3中，假設列印設備100可以包括掃描功能302和列印功能304。這些功能中的每個可以以硬體、固件、軟體或硬體、固件和/或軟體的任意組合來實施。另外，掃描功能302和列印功能304中的每個可以與計算設備300通信，並且也可能與其它計算設備通信。在一些情況下，由列印設備100支持的數據路徑可以被稱之為「管線」。
[0055]掃描至列印數據路徑310可以由掃描功能302和列印功能304支持。掃描至列印數據路徑310可以例如在用戶指令列印設備100複印物理文件時使用。響應於該指令，掃描功能302可以將物理文件掃描成電子文件，並且經由掃描至列印數據路徑310將電子文件傳送至列印功能304。掃描至列印數據路徑310的使用可能涉及至少暫時將電子文件中的一些或全部存儲在列印設備100的數據儲存器中。然後，列印功能304可以將電子文件列印成物理介質(例如一張或多張紙)。
[0056]掃描至主機數據路徑306也可以由掃描功能302和計算設備300支持。掃描至主機數據路徑306可以例如在用戶指令列印設備100掃描物理文件時使用。用戶也可以指令列印設備100將所得到的電子文件的表示傳送至計算設備100，或者列印設備100可以被預配置成將電子文件自動傳送至計算設備300。因此，響應於該指令，掃描功能302可以將物理文件掃描成電子文件，並且經由掃描至主機數據路徑306將所得到的電子文件傳送至計算設備300。掃描至列印數據路徑310的使用可能涉及至少暫時將電子文件中的一些或全部存儲在列印設備100的數據儲存器中，並且將所得到的電子文件的表示傳送至計算設備300。
[0057]主機至列印數據路徑308可以由計算設備300和列印功能304支持。主機至列印數據路徑308可以例如在用戶指令計算設備300在列印設備100上列印電子文件時使用。響應於該指令，計算設備300可以將電子文件的表示傳送至列印功能304。列印設備100經由列印功能304可以將電子文件列印成物理介質。電子文件中的一些或全部可以在電子文件的列印之前和/或期間存儲在列印設備100的數據儲存器中。
[0058]明顯地，對於上面討論的數據路徑中的至少一個以及由列印設備100支持的可能其它數據路徑，電子文件可能需要存儲和/或在網絡或電纜上傳送。電子文件的存儲和/或傳送兩者的效率能夠通過壓縮這些電子文件來提高。例如，如果電子文件能夠平均被壓縮成它們原始尺寸的四分之一，則大約四倍多的電子文件能夠存儲在固定量的數據儲存器中。進一步，這些壓縮電子文件在網絡或電纜上的傳送能夠比未壓縮電子文件的傳送大約四倍快地發生。[0059]下列部分描述提供由列印設備100處理的電子文件的壓縮的各種實施例。
[0060]3、示例圖像顏色模型
[0061]電子文件能夠使用多個顏色模型來表示。因此，穩健型壓縮技術應當能夠對這些模型中的一些或全部進行操作。進一步，半色調壓縮可能對於單個顏色模型是特定的，或者可能單獨對顏色模型的每個通道進行操作。
[0062]例如，紅綠藍(RGB)顏色模型可以用於在電子輸出設備，例如電視機、監視器和計算機屏幕上顯示圖像。RGB是加色模型，在該模型中，紅色、綠色和藍色光以各種方式一起加入以產生顏色光譜。例如，青色可以通過組合綠色和藍色形成，黃色可以通過組合紅色和綠色形成，品紅可以通過組合紅色和藍色形成，並且白色可以通過組合紅色、綠色和藍色形成。
[0063]RGB圖像的特定像素可以被表達為三通道元組(R，G，B)，其每個通道可以從零變化到預定義的最大值(例如255)。如果所有通道處於零，則結果可能是黑色。如果所有通道處於最大值，則結果可能是最亮的可表達白色。
[0064]RGB輸出通常依賴於設備，因為不同的輸出設備可以以不同的方式顯示相同的RGB圖像。因此，在一些情況下，這些不同可以由人識別。在一些實施例中，使用掃描至主機數據路徑306掃描到列印設備100中的物理文件可以使用RGB顏色模型來編碼。
[0065]青色-品紅-黃色(CMY)顏色模型可以用於通過列印設備列印彩色圖像。CMY是減色模型，在該模型中，青色、黃色和品紅以各種方式施加到白色表面以再生顏色光譜。例如，紅色可以通過組合品紅和黃色形成，藍色可以通過組合青色和品紅形成，並且綠色可以通過組合青色和黃色形成。因此，CMY顏色模型可以被考慮為RGB顏色模型的補充。
[0066]CMY圖像的特定像素可以被表達為三通道元組(C，M，Y)，其每個通道可以從零變化到預定義的最大值。如果所有通道處於零，則結果可能是白色。如果所有通道處於最大值，則結果可能是黑色。
[0067]與RGB輸出同樣地，CMY輸出通常依賴於設備，因為相同CMY圖像在不同列印設備上的列印輸出可能看起來不同。在一些情況下，這些不同可以由人識別。在一些實施例中，使用主機至列印數據路徑308和/或掃描至列印數據路徑310由列印設備100列印的電子文件可以使用CMY顏色模型編碼。
[0068]在一些實施例中，也可以使用四通道CMYK顏色模型。除了也使用主(黑色)通道以夕卜，該CMYK四通道模型可能與CMY顏色模型類似或相同。除了可能組合青色、品紅和黃色以形成黑色，獨立的主(黑色)墨源可以用於形成黑色。因此，CMYK圖像的特定像素可以被表達為四通道元組(C，M，Y，K)，其每個通道可以從零變化至預定義的最大值。
[0069]使用CMYK顏色模型，與CMY模型相同的顏色可以被支持，但通常使用較少的墨，因為K著色劑能夠代替C、M和Y著色劑的混合物。然而，CMYK顏色模型可能不總是能夠方便地轉換成其它顏色模型以及從其它顏色模型轉換，因為K著色劑的添加增加冗餘性，例如相同的顏色能夠是混合不同C、M、Y和K組合物的結果。
[0070]加色模型是灰色，也被稱之為灰度級，灰度級可以用於黑色和白色圖像的表示。與RGB和CMY/CMYK顏色模型不同，灰色顏色模型的每個像素使用對像素的強度進行編碼的單個通道來表示。由灰色通道使用的值能夠從用於黑色的零變化至用於白色的預定義最大值(例如255)。在一些實施例中，由列印設備100支持的數據路徑中的一條或多條可以能夠使用灰色顏色模型對圖像進行編碼。
[0071]另一顏色模型是YCbCr。在一些實施中，該顏色模型可以用作圖像的可替代表示。具體地，Y通道可以表示像素的亮度，並且Cb和Cr通道可以分別表示藍色-黃色色度和紅色-綠色色度。YCbCr顏色模型具有與RGB和CMY顏色模型定義明確的關係，並且能夠相對輕鬆地轉換成這些顏色模型中的任一個以及從這些顏色模型中的任一個轉換。
[0072]YCbCr顏色模型的附加優勢是，使用YCbCr顏色模型編碼的圖像的壓縮傾向於比採用RGB或CMY/CMYK顏色模型編碼的圖像的壓縮更有效率。具體地，人眼不是非常擅長於檢測圖像中的高頻(例如快速變化)色度信息。因此，使用YCbCr顏色模型編碼的圖像能夠通過忽視Cb和Cr通道的高頻組分而利用該信息。因此，如在下面更詳細討論的那樣，採用特定顏色模型編碼的圖像可以在壓縮之前被轉換成YCbCr顏色模型以便提高壓縮性能。
[0073]4、示例圖像半色調
[0074]許多數字圖像包含連續色調，在該連續色調中，圖像的顏色或灰度級部分從較亮的色調平滑地過渡到較暗的色調，或者從較暗的色調平滑地過渡到較亮的色調。然而，許多印表機不支持連續色調。代替地，印表機可能支持從最亮色調到最暗色調的離散數目的色調。例如，對於圖像的任意給定像素，簡單的黑色和白色印表機可以支持僅僅輸出黑色或白色。
[0075]半色調包括將連續色調圖像分解成像素陰影的圖案以創建平滑過渡灰色或彩色的幻影的過程。應當注意，這裡術語「圖像」可以稱之為全圖像或圖像的部分，例如圖像塊。在下面的一些示例中，為了簡單起見，操作可能針對圖像塊而不是全圖像示出。
[0076]半色調矩陣可以是mxn塊單元，每個單元包含一個或多個閾值。當向圖像應用半色調矩陣時，半色調矩陣可以在圖像上平鋪，使得圖像中的每個像素與平鋪半色調矩陣之一中的單元成對相關聯。半色調矩陣可以基於特定印表機的特性來定義，因此可以是特定於輸出設備。半色調矩陣也可以被稱之為半色調屏幕、閾值表或抖動表。
[0077]來自圖像的每個像素可以與其相關聯單元中的閾值比較來確定像素的半色調值。例如，在特定顏色通道中，像素可以採用指示該像素強度或亮度的0-255的值。相關聯單元可以包含三個閾值:64、128和240，因此定義四個範圍:0_64、65_128、129-240和241-255。像素的值落入這些範圍之一中，並且像素所落入的範圍可以限定像素的半色調值。因此，像素的半色調值可以利用2位值來限定。例如，00可以指示範圍0-64，01可以指示範圍65-128，10可以指示範圍129-240，並且11可以指示範圍241-255。
[0078]更正式地說，如果在半色調矩陣中存在為每個單元所限定的閾值，則這些閾值可以限定i個範圍，並且像素值所落入的範圍可以由log2(i)位值表示。將半色調矩陣應用於圖像中的每個像素可能導致圖像的半色調版本，在半色調版本中，每個像素由log2(i)位值表示。該半色調版本然後可以發送至支持i色調的印表機。
[0079]該過程在圖4中示出。圖像像素矩陣400包含多個單個像素，包括示例像素402和404，每個採用8位值(例如0-255)。半色調矩陣406包含單元的圖案，包括示例單元408和410，每個包括15個閾值的表示(即指示被標記從O至15的16個範圍，在0-255的全部範圍內)。
[0080]半色調矩陣406可以覆蓋在圖像像素矩陣400上，使得示例單元408與示例像素402相關聯，並且示例單元410與示例像素404相關聯。示例像素402的值可以被映射成由示例單元408的閾值限定的範圍，並且示例像素404的值可以映射成由示例單元410的閾值限定的範圍。
[0081]每個示例單元可以限定不同的閾值。例如,示例單元408可以限定閾值412,而示例單元410可以限定閾值414。因此，將像素映射成這些相應的閾可能導致確定示例像素402的值落在閾值412的第四和第五閾值之間，並且示例像素404的值落在閾值414的第十五閾值上。因此，示例像素402的半色調值可以被表示為4，而示例像素404的半色調值可以被表不為15。
[0082]更一般地，假設半色調矩陣的單元限定i_l個閾值。如果像素值大於或等於最高閾值，則半色調值為1-Ι。如果像素值小於最低閾值，則半色調值為O。如果像素值大於或等於第c閾值但小於第(c+1)閾值，則半色調值為C。
[0083]覆蓋示例圖像塊的示例半色調矩陣在圖5A中圖示出。半色調矩陣的每個單元被標記為ΑΡ..Α8或ΒΡ..Β8中之一。這些標記中的每個指示潛在不同的閾值集合。因此,標記為Al的單元可以具有與標記為Α2的單元不同的閾值集合，等等。
[0084]半色調矩陣的覆蓋圖案向左移動，使得半色調矩陣的垂直相鄰平鋪的起始位置偏移兩個單元。例如，半色調矩陣502的Al單元比半色調矩陣500的Al單元進一步向左兩個單元。相似地，半色調矩陣504的Al單元比半色調矩陣502的Al單元進一步向左兩個單元。該偏移可能導致由印表機產生的半色調圖案具有美學上吸引人的角度。
[0085]平鋪半色調矩陣的一個可能缺點是，當圖像的寬度是這樣時需要非整數的半色調矩陣來覆蓋圖像的每行。例如，在圖5Α中，圖像塊為12x8個像素，並且半色調矩陣為8x2個單元。因此，需要IV2半色調矩陣來跨越圖像塊的寬度。因為下面將更詳細解釋的原因，填充圖像塊的行可能導致圖像的半色調版本的壓縮效率增加。具體地，圖像塊可以利用額外的像素列填充，使得整數的半色調矩陣可以覆蓋在每行上。這些填充列(padding column)可以包含在圖像塊的最右列中的像素副本。
[0086]填充列的數目可以以各種方法確定。確定填充列數目r的一個可能方法是根據下列等式:
[0087]r = m-(p_q)modm
[0088]其中m為單元中半色調矩陣的寬度，P為像素中圖像塊的寬度，並且q為偏移。對於圖 5A, m=8, p=12,並且 q=2。因此，r=6。
[0089]圖5B圖示圖5A的圖像塊，其具有6個填充列，並且平鋪有半色調矩陣。除了圖5B中示出的平鋪半色調矩陣以外，更多的半色調矩陣可以通過將半色調矩陣從一對行的右端纏繞到接下來下面一對行的左端而在填充圖像塊上平鋪。因此，半色調矩陣可以在右上角中的Al…A6和ΒΡ..Β6單元上展開，並且然後「卷繞」到位於接下來最下面兩行的左側的Α7…AS和Β7…Β8單元。因此，當從左到右相鄰讀取每對行時，半色調矩陣順次重複。
[0090]為了提供基於實際圖像的另一不例，圖6圖不不例圖像600和圖像600的圖像塊602。為了簡單和例示的目的，圖像600包括單個顏色通道。圖像塊602表示圖像600的區域的擴大，即程式化的「R」。
[0091]作為示例，可以假設圖像塊602的尺寸為128x128像素。進一步假設圖5Α的8x2半色調矩陣用於覆蓋圖像塊602，並且偏移為2，則m=8，ρ=128，並且q=2。因此，填充列的數目r為2。[0092]圖7再次圖示圖像塊602，圖像塊602此時與2像素填充列700對準。填充列700可以附加至圖像塊602的右側以形成130x128像素塊。填充列700的像素可以從圖像塊602的兩個最右列導出，並且半色調可以應用於這些像素。因此，半色調後，填充列700的像素可能不類似導出它們的像素。
[0093]另外，圖7還包括圖像塊702，圖像塊702為圖像塊602的略微放大、半色調後的版本。類似地，列704是列700的略微放大、半色調後的版本。當在適當距離處觀看時，圖像塊702近似圖像塊602的陰影。該效果可以通過向圖像塊602應用合適的半色調矩陣而實現。
[0094]圖8中的半色調像素800圖示應用半色調後圖像塊602的右上角的像素。因此，半色調像素800可以表示圖像塊702的部分。在半色調像素800中，單個半色調像素可以具有採用十六進位符號的從O到F的值。O可以表示最亮的半色調像素(例如，白色)，而F可以表示最暗的半色調像素(例如，黑色)。O和F之間的半色調像素值可以表示以用於半色調像素值I的淺灰色開始的灰色陰影，並且隨著半色調像素值增加日益變得較暗。
[0095]由於圖像塊602的右上角是純色，因此半色調像素800的值反映三角圖案在圖像塊702的右上角明顯。這示出半色調如何能夠用於表示顏色的特定陰影。
[0096]給定圖像塊的半色調像素，這些像素可以被布置成段。做出這種布置的一個可能方法在圖9中示出。在圖9中，假設應用於圖像塊的半色調矩陣是8單元寬和2單元高。毫無疑問，其它尺寸的半色調矩陣可以使用。例如，一些實施例可以使用m單元寬和η單元高的mxn像素半色調矩陣。這些段可以包括填充列中的像素。
[0097]具體地，圖9示出被布置成段900A、902A、904A和906A的半色調像素800的頂部兩行的一部分。每段是半色調矩陣的尺寸，也就是說8像素寬和2像素高，或者8x2。然而，在完全一般性上，如果mxn單元半色調矩陣被使用，則相應地可以使用mxn像素段。
[0098]圖9還示出每段的2路交錯。例如，在段900A中，該段的頂部像素與該段的底部像素一個接一個地交錯。結果可能是交錯段900B，其是16像素寬和I像素高。以類似的方式，段902A可以被交錯以形成交錯段902B，段904A可以被交錯以形成交錯段904B，並且段906A可以被交錯以形成交錯段906B。一般地，如果段的高度是η像素，則可以使用η路交錯。因此，為了清楚起見，這些交錯段可以可選擇地被稱之為mnxl半色調段。
[0099]一旦它們被形成，交錯段900B、902B、904B和906B可以按圖9中示出的順序被布置，其中最左交錯段由第二最左交錯段緊接著，依次類推。這些交錯段可以按該特定順序提供給被布置以存儲這些段用於進一步處理的一個或多個緩衝區。因此，在下列討論中對「段」的引用可以假定該段是交錯段。進一步，這些段的序列可以被稱之為緩衝區的「輸入流」。
[0100]圖10圖示緩衝區布置1000，其包含12段歷史緩衝區1002(條目ΗΒ_0至HB_11)、4段先行緩衝區(lookahead buffer) 1004 (條目LB_0至LB_3)和「新」緩衝區1006。歷史緩衝區1002可以是FIFO緩衝區，因為在歷史緩衝區1002 (例如，HB_11)的一端插入的段可以按它們插入的順序行進通過至歷史緩衝區1002 (例如，ΗΒ_0)的另一端。數據流的一般方向在圖10中被示出為從底部到頂部；也就是說，段可以首先被放置在「新」緩衝區1006中、移動至先行緩衝區1004，然後至歷史緩衝區1002。
[0101]為了方便起見，歷史緩衝區1002可以被稱之為「FIFO緩衝區」，並且可以由h條目組成，而先行緩衝區1004可以由k條目組成。「新」緩衝區1006可以由圖10中示出的單個條目或更多條目組成。因此，應當理解，緩衝區布置1000的單個緩衝區可以各自包含任意數目的條目，並且圖10中示出的特定布置是為了示例的目的。例如，在一些實施中，「新」緩衝區1006的條目可以被考慮為是先行緩衝區1004的部分。
[0102]一般地，半色調段可以通過在歷史緩衝區1002中查找匹配段來壓縮。具體地，先行緩衝區1004中段的當前序列可以與歷史緩衝區1002中的段序列相比較，以確定在能夠做出的相應段序列之間的最長匹配。當考慮以HB_9、HB_10或HB_11開始的匹配時，包括在先行緩衝區1004中的段可以被考慮為歷史緩衝區1002的部分。
[0103]圖11圖示在壓縮後可以用於表示半色調段的若干不同格式。圖11基於圖10的緩衝區布置1000;也就是說，64位段，在歷史緩衝區中為12條目，在先行緩衝區中為4條目，並且在「新」緩衝區中為一個條目。毫無疑問，其它緩衝區布置可能通過相應調節圖11的格式而可以被支持。為了例示的目的，格式1100、1102和1104的尺寸未按規定比例示出。
[0104]格式1100可以表示段的文字編碼，並且可以在特定段不能基於緩衝區布置1000中的信息被壓縮時使用。因此，格式1100可以以文字碼字開始，其可以是I的單個位集合。文字碼字可以指示下一欄位包括未壓縮的段。具體地，該下一欄位可以是64位，並且可以是不能被壓縮的段的副本。
[0105]格式1102可以被稱之為重複或短重複格式。格式1102可以以重複碼字開始，其可以是O的單個位集合。該欄位可以由4位重複位置欄位和2位重複長度欄位緊接著。重複位置欄位可以指示在歷史緩衝區中重複段從哪開始。重複長度欄位可以指示從該位置開始的重複段的數目。為了高效利用重複長度欄位中的位，該欄位可以包含重複段減去I的數目。因此，如果重複長度欄位包含值「00」，則I的重複長度可以被表示。如果重複長度欄位包含值「01」，則2的重複長度可以被表示，等等。
[0106]格式1104可以被稱之為擴展重複或長重複格式。格式1104可以以擴展重複碼字開始，其可以是I的三個位集合。該欄位可以由5位重複長度欄位緊接著，指示條目HB_11中的段在先行緩衝區1004、「新」緩衝區1006和/或輸入流中的倍數。為了高效利用重複長度欄位中的位，該欄位可以包含重複段減去5的數目。因此，如果重複長度欄位包含值「00000」，則5的重複長度可以被表示。如果重複長度欄位包含值「00001」，則6的重複長度可以被表示，等等。
[0107]圖12是可以被跟緊接著以確定圖11的哪個格式用在特定場景中的全部過程的流程圖。如上所指出的，在步驟1200，先行緩衝區1004中段的當前序列可以與歷史緩衝區1002中的段序列相比較以確定能夠做出的段的相應序列之間的最長匹配。「新」緩衝區1006可以包含將從輸入流讀取的下一段。
[0108]在步驟1202，確定匹配長度是否為零，零指示未找到匹配。如果匹配長度為零，則在步驟1204處，可以採用下列動作:(I)輸出以格式1100編碼的LB_0中的段，(2)移動歷史緩衝區一段，將條目ΗΒ_0中的之前段從歷史緩衝區中清空，(3)將條目LB_0中的段移動到條目HBll中，以及(4)將新段移動到LB_3中。
[0109]如果匹配長度為非零，則採取的動作可能依賴於匹配的長度。在步驟1206，確定下列條件是否為真:匹配開始於HB_11並且具有五的長度(所有先行緩衝區段相同並且等於段並且「新」緩衝區1006中的段也與HB_11中的值相匹配)。[0110]如果條件為真，則在步驟1208，可以採取下列動作:(1)設置擴展計數值為5，(2)只要擴展計數值小於36並且「新」緩衝區1006中的段與HB_11處的段相匹配，則丟棄「新」緩衝區1006中的段並且累加擴展計數值，(3)使用格式1104，輸出具有以重複長度欄位編碼的最後擴展長度的擴展重複碼，(4)丟棄先行緩衝區1004中的所有四個值，而不更新歷史緩衝區1002，以及(5)利用來自輸入流的下一段重新加載先行緩衝區1004。
[0111]如果條件為非真，則在步驟1210處，可以採取下列動作:(I)利用編碼的匹配歷史緩衝區1002位置和匹配長度輸出格式1102，(2)以匹配長度移動運行窗口，以及(3)利用來自輸入數據流的下一段重新加載先行緩衝區1006。如果具有相同非零最好匹配長度的多個匹配存在，則可以使用以最低歷史緩衝區1002索引數開始的匹配。
[0112]注意，解壓縮器模塊可以以相同的原始歷史緩衝區值開始，並且可以利用與壓縮器模塊相同的規則維持運行窗口。另外，如果待壓縮的圖像不是段尺寸的整數倍，則最後一段可能在輸入流耗盡時以O位填充。
[0113]為了進一步示出能夠壓縮半色調圖像或圖像塊的各種方法中的一些，圖13至圖18提供如何能夠操作圖10的緩衝區、圖11的格式和圖12的過程以方便這種壓縮的示例。
[0114]圖13示出來自輸入流的段如何可以添加到「新」緩衝區1006和先行緩衝區1004。一旦初始化，歷史緩衝區1002就可以利用用於條目ΗΒ_0至HB_10的所有「F」值(即採用二進位的1111)和用於條目HB_11的所有「O」值(即採用二進位的0000)來加載。先行緩衝區1004可以利用來自輸入流的第一四段來加載。
[0115]在圖13所示出的場景中，未能找到匹配。相應地，採用格式1100的輸出可以產生，包括指示輸出段未被壓縮的文字碼字和輸出段的副本(例如，由LB_0處的段表示的64位「00000F9R)0000F9」)。因此，全部65位可以輸出用於該段。
[0116]另外，歷史緩衝區1002的段可以向上移動一個條目，其包括丟棄條目ΗΒ_0中的段。輸出段也可以是寫入的條目HB_11。
[0117]圖14示出在先行緩衝區1004和歷史緩衝區1002中的段之間找到兩段匹配的示例場景。圖14的示例場景近似從圖13的示例場景離開的位置繼續。因此，先行緩衝區1004的段已向上移動一個條目，「新」緩衝區1006中的段已被移入LB_3中，並且來自輸入流的下一段已被放置在「新」緩衝區1006中。
[0118]先行緩衝區1004中段的序列再次可以與歷史緩衝區1002中的段序列相比較以確定那些緩衝區中段的相應序列之間的最長匹配。此時，對於2段的匹配，LB_0和LB_1的段與段HB_11和LB_0相匹配(如上所指出的那樣，當搜索匹配時，先行緩衝區1004的內容可以被考慮為歷史緩衝區1002的部分)。
[0119]響應於確定存在兩段的匹配，可以產生採用格式1102的輸出。該輸出可以包括O的重複碼字(二進位)、1011的重複位置(二進位)(指示匹配開始於第11緩衝區條目和01的重複長度(二進位)(指示HB_11處的段重複兩次)(如上所指出的那樣，為了效率的目的，重複長度碼可以指代重複長度減去I)。因此，代替兩個64位的段，可以使用一個7位的值。
[0120]另外，歷史緩衝區1002中的段可以向上移動兩個條目，其可以包括丟棄條目ΗΒ_0和HB_1中的段。進一步，先行緩衝區中的段可以向上移動兩個條目，其可能涉及條目LB_0和LB_1中的段移入條目HB_10和HB_11中。另外，「新」緩衝區1006中的段可以移入條目LB_2中，並且來自輸入流的接下來兩段可以分別存儲在條目LB_3和「新」緩衝區1006中。
[0121]圖15圖示近似從圖14的示例場景離開的位置繼續的另一場景。再次，先行緩衝區1004中段的序列可以與歷史緩衝區1002中的段序列相比較，以確定那些緩衝區中段的相應序列之間的最長匹配。在此場景中，與圖13的場景相同，未找到匹配(零長度匹配)。
[0122]相應地，可以產生採用格式1100的輸出。該輸出可以包括指示輸出段未被解壓縮(I 二進位)的文字碼字和輸出段的副本(例如，由LB_0處的段表示的64位「FAE00FFFFAE00FFF」)。因此，可以針對該段輸出總的65位。另外，歷史緩衝區1002的段可以向上移動一個條目，其包括丟棄條目ΗΒ_0中的段。輸出段也可以是寫入的條目HB_11。
[0123]圖16示出在先行緩衝區1004與歷史緩衝區1002中的段之間找到一段匹配的示例場景。圖16的示例場景近似從圖15的示例場景離開的位置繼續。
[0124]先行緩衝區1004中段的序列再次可以與歷史緩衝區1002中的段序列相比較以確定那些緩衝區中段的相應序列之間的最長匹配。此時，最長匹配位於條目LB_0中的段與條目LB_11中的段之間。
[0125]響應於確定存在一段的匹配，可以產生採用格式1102的輸出。該輸出可以包括重複碼字(O 二進位)、1011的重複位置(二進位)(指示匹配開始於第11緩衝區條目和00的重複長度(二進位)(指示匹配為一段長度)(再次，重複長度可以指代實際重複長度減去I)。因此，代替64位的段，可以使用一個7位的值。
[0126]另外，歷史緩衝區1002中的段可以向上移動一個條目，其可以包括丟棄條目ΗΒ_0中的段。進一步，先行緩衝區中的段也可以向上移動一個條目，其可能涉及條目LB_0中的段移入條目HB_11中。「新」緩衝區1006中的段可以移入先行緩衝區1004的條目LB_3中，並且來自輸入流的接下來的段可以分別存儲在「新」緩衝區1006中。
[0127]圖17示出在先行緩衝區1004與歷史緩衝區1002中的段之間找到三段匹配的示例場景。先行緩衝區1004中段的序列再次可以與歷史緩衝區1002中的段序列相比較以確定那些緩衝區中段的相應序列之間的最長匹配。此時，最長匹配位於條目1^_0、1^_1和LB_2中的段與條目HB_4、HB_5和HB_6中的段之間。圖17中圈出的值表示來自填充列的值。
[0128]響應於確定存在三段的匹配，可以產生採用格式1102的輸出。該輸出可以包括重複碼字(O 二進位)、0100的重複位置(二進位)(指示匹配開始於HB_4)歷史緩衝區1002的第四條目和10的重複長度(二進位)(指示匹配針對三段繼續)。因此，代替三個64位的段，可以使用一個7位的值。
[0129]另外，歷史緩衝區1002中的段可以向上移動三個條目，其可以包括丟棄條目HB_0、HB_1和HB_2中的段。進一步，先行緩衝區中的段也可以向上移動三個條目，其可能涉及條目LB_0、LB_1和LB_2中的段移入條目HB_9、HB_10和HB_11中。「新」緩衝區1006中的段可以移入條目LB_1中，並且來自輸入流的接下來的三段可以分別存儲在LB_2、LB_3和「新」緩衝區1006中。
[0130]圖18示出在先行緩衝區1004和歷史緩衝區1002中的段之間找到五段匹配的示例場景。該場景是條目HB_11中的段與先行緩衝區1004和「新」緩衝區1006中的所有條目相匹配的「擴展重複」的示例。因此，最長匹配位於條目HB11、LB_0、LB_1、LB_2和LB_3中的段與條目LB_0、LB_1、LB_2、LB_3和「新」緩衝區1006中的段之間。[0131]響應於確定存在五段的擴展重複匹配，可以產生使用格式1104的輸出。該輸出可以包括111的擴展重複碼字(二進位)和00000的重複長度(二進位)(指示匹配針對五段繼續)(對於擴展重複碼字，重複長度碼可以指代重複長度減去5)。因此，代替五個64位的段，可以使用一個8位的值。在重複針對額外段繼續的場景中，輸入流可以繼續讀取並且重複長度可以相應地累加。
[0132]圖19A、圖19B、圖19C和圖19D提供上述列填充機制的可能益處的進一步例示。圖19A圖示具有覆蓋的示例8x2半色調矩陣的示例圖像塊1900。顯著地，在半色調後，與在點1902處開始的三個半色調矩陣對準的像素和與在點1904處開始的三個半色調矩陣對準的像素相同。
[0133]圖19B圖示包含交錯後圖19A的半色調矩陣的緩衝區布置1906。如在圖19B中所能看出的，即使與在點1902處開始的三個半色調矩陣對準的像素和與在點1904處開始的三個半色調矩陣對準的像素相同，但它們也在緩衝區布置1906中彼此偏移。結果，在先行緩衝區和歷史緩衝區中的條目之間不存在匹配。
[0134]圖19C圖示具有覆蓋的示例8x2半色調矩陣的示例圖像塊1908。除了兩個填充列1910應用於右手側以外，示例圖像塊1908與示例圖像塊1900類似。除了由填充矩陣1910的加入所做出的改變以外，與在點1902處開始的三個半色調矩陣對準的像素和與在點1904處開始的三個半色調矩陣對準的像素相同。
[0135]圖19D圖示包含交錯後圖19C的半色調矩陣的緩衝區布置1912。填充列的第一兩個像素1914 (最頂部填充像素)被圈出，填充列的第二兩個像素1916 (第二頂部填充像素)也被圈出。如在圖19D中可看出的，填充列的加入導致歷史緩衝區和先行緩衝區之間的三個匹配。具體地，條目HB_5、HB_6和HB_7與條目LB_0、LB_1和LB_2相匹配。以該方式，填充列可以導致半色調圖像的更高效壓縮。
[0136]5、示例操作
[0137]圖20是示例實施例的流程圖。由該流程圖示出的步驟可以由一個或多個列印設備，例如列印設備100和/或計算設備，例如計算設備300實施。每個單獨步驟的方面可以由單個設備執行或者分布在多個計算設備之間。圖20的示例實施例還可以包括任意特徵或始終在本說明書和/或附圖中公開的特徵。
[0138]在步驟2000,基於mxn半色調矩陣和圖像的第一mxn像素塊,可以確定第一 mxn像素塊的第一 mxn半色調版本。該確定可能涉及在圖像上平鋪mxn半色調矩陣，使得mxn半色調矩陣的垂直相鄰平鋪的開始位置偏移q像素。另外，rlxn填充像素列可以附加至圖像的最右列。在一些實施例中，P可以是在附加rlxn填充像素列之前像素中的圖像的寬度，並且r可以是m- (p-q) modm。
[0139]在步驟2002，可以在第一 mxn像素塊的第一mxn半色調版本的行上執行η路交錯，以創建第一 mnxl半色調段。
[0140]在步驟2004，第一 mnxl半色調段可以與先入先出(FIFO)緩衝區中的一個或多個半色調段相比較。該比較可能涉及確定FIFO緩衝區中與第一 mnxl半色調段相匹配的半色調段和連續緊接第一 mnxl半色調段的任意其它半色調段的最長連續範圍。
[0141]在步驟2006，可以確定第一 mnxl半色調段是否與FIFO緩衝區中的任意半色調段相匹配。如果第一 mnxl半色調段與FIFO緩衝區中的特定半色調段相匹配，則在步驟2008處可以輸出重複碼字和重複值，並且可以向FIFO緩衝區寫入第一 mnxl半色調段的至少一個表示。在一些實施例中，指示特定半色調段在FIFO緩衝區中的地點的重複位置可以包括在該輸出中。
[0142]如果第一 mnxl半色調段與FIFO緩衝區中的任意半色調段不相匹配，則在步驟2010處可以輸出第一 mnxl半色調段的文字碼字和表示，並且可以向FIFO緩衝區寫入第一mnxl半色調段的表示。
[0143]在一些實施例中，第一 mnxl半色調段可以存儲在具有其它mnxl半色調段的一個或多個先行緩衝區中。另外，FIFO緩衝區中的其它mnxl半色調段也可以與特定半色調段相匹配。j匹配半色調段可以在先行緩衝區中相鄰，和/或重複值指示j。將第一 mnxl半色調段的至少一個表示寫入FIFO緩衝區可能涉及將第一 mnxl半色調段的j表示寫入FIFO緩衝區。進一步，其它mnxl半色調段可以從圖像的其它mxn像素塊導出。在一些實施中，j匹配半色調段可以從先行緩衝區去除。
[0144]另外，重複碼字可以是短重複碼字或擴展重複碼字。在任一情況下，j可以與k比較。如果j〈k，則短重複碼字可以用作重複碼字，而如果j >k，則擴展重複碼字可以用作重複碼字。如果擴展重複碼字是重複碼字，則在向FIFO緩衝區寫入第一 mnxl半色調段的j表示之後，可以利用第二 mnxl半色調段代替先行緩衝區中的至少一個條目。第二 mnxl半色調段可以從圖像的第二 mxn像素塊導出。
[0145]而且，mxn半色調矩陣的每個單元可以包含閾值。閾值可以限定i個像素值範圍，並且第一 mxn像素塊的第一 mxn半色調版本的每個單元可以包含1g2⑴位值。對於第一mxn像素塊中的每個特定單元,確定第一 mxn像素塊的第一 mxn半色調版本可能涉及:(i)確定第一 mxn像素塊中特定單元的特定像素值，(ii)確定mxn半色調矩陣的特定單元中的i像素值範圍之一包含特定像素值，其中第一 mxn像素塊中的特定單元對應於mxn半色調矩陣的特定單元，以及(iii)向第一 mxn像素塊的第一 mxn半色調版本的特定單元寫入表示確定i像素值範圍之一的1g2 (i)位值。
[0146]6、結論
[0147]本發明不限於在本申請中描述的特定實施例方面，該特定實施例旨在作為各個方面的例示。對於本領域技術人員來說將顯而易見的是，可以做出許多更改和改變，只要不背離其精神和範圍。除了這裡列出的那些以外，在本發明範圍內的功能等同的方法和裝置將從前面的描述中顯而易見。這種更改和改變旨在落入所附權利要求的範圍內。
[0148]關於圖中以及這裡討論的梯形圖、場景和流程圖中的任意一個或所有，每塊和/或通信可以根據示例實施例表示信息的處理和/或信息的傳送。可替代實施例可以包括在這種示例實施例的範圍內。進一步，或多或少的塊和/或功能可以與這裡討論的梯形圖、場景和流程圖中的任一個一起使用，並且這些梯形圖、場景和流程圖可以部分或整體地彼此結合。
[0149]表示信息的處理的步驟或塊可以對應於能夠被配置為執行這裡描述的方法或技術的特定邏輯功能的電路。可替代地或另外地，表示信息的處理的步驟或塊可以對應於模塊、段或程序代碼的一部分(包括相關數據)。程序代碼可以包括可由處理器執行的用於實施方法或技術中的特定邏輯功能或動作的一個或多個指令。程序代碼和/或相關數據可以存儲在任意類型的計算機可讀介質上，例如存儲設備，包括盤驅動器、硬碟驅動器或其它存儲介質。
[0150]計算機可讀介質也可以包括非暫時性計算機可讀介質，例如像寄存器存儲器、處理器緩存和/或隨機存取存儲器(RAM)的短時間段存儲數據的計算機可讀介質。計算機可讀介質還可以包括較長時間段存儲程序代碼和/或數據的非暫時性計算機可讀介質，例如像只讀存儲器(ROM)、光碟或磁碟和/或緊湊盤只讀存儲器(CD-ROM)的二次或永久長期儲存器。計算機可讀介質還可以是任意其它的易失性或非易失性存儲系統。計算機可讀介質可以被考慮為例如計算機可讀存儲介質和/或有形存儲設備。
[0151]儘管這裡已公開了各個方面和實施例，但其它方面和實施例對於本領域技術人員來說將顯而易見。這裡公開的各個方面和實施例是為了例示的目的而不旨在是限制，其真實範圍和精神由所附權利要求指示。
【權利要求】
1.一種用於半色調數字圖像的壓縮的方法，包括: 基於mxn半色調矩陣和圖像的第一 mxn像素塊，由計算設備確定所述第一 mxn像素塊的第一 mxn半色調版本； 對所述第一 mxn像素塊的第一 mxn半色調版本的行執行η路交錯以創建第一 mnxl半色調段； 將所述第一 mnxl半色調段與先入先出FIFO緩衝區中的一個或多個半色調段相比較； 如果所述第一 mnxl半色調段與所述先入先出緩衝區中的任意半色調段不相匹配，則(i)輸出所述第一 mnxl半色調段的文字碼字和表示，並且(ii)將所述第一 mnxl半色調段的表示寫入所述先入先出緩衝區；以及 如果所述第一 mnxl半色調段與所述先入先出緩衝區中的特定半色調段相匹配，則(i)輸出重複碼字和重複值，並且(ii)將所述第一 mnxl半色調段的至少一個表示寫入所述先入先出緩衝區。
2.根據權利要求1所述的方法，其中所述第一mnxl半色調段與k_l個其它mnxl半色調段一起被存儲在先行緩衝區中，其中j_l ( k的所述其它mnxl半色調段也與所述先入先出緩衝區中的所述特定半色調段相匹配，其中所述j匹配半色調段在至少所述先行緩衝區中是相鄰的，其中所述重複值指示j，並且其中將所述第一 mnxl半色調段的至少一個表示寫入所述先入先出緩 衝區包括將所述第一 mnxl半色調段的j表示寫入所述先入先出緩衝區。
3.根據權利要求2所述的方法，其中所述k-Ι個其它mnxl半色調段從所述圖像的其它mxn像素塊導出。
4.根據權利要求2所述的方法，進一步包括: 將所述j匹配半色調段從所述先行緩衝區中去除。
5.根據權利要求2所述的方法，其中所述重複碼字或者是短重複碼字或者是擴展重複碼字。
6.根據權利要求5所述的方法，所述方法進一步包括: 將j與k相比較； 如果j〈k，則使用所述短重複碼字作為所述重複碼字；並且 如果j ^ k，則使用所述擴展重複碼字作為所述重複碼字。
7.根據權利要求6所述的方法，其中所述擴展重複碼字是所述重複碼字，所述方法進一步包括: 在將所述第一 mnxl半色調段的j表示寫入所述先入先出緩衝區之後，利用第二 mnxl半色調段代替所述先行緩衝區中的至少一個條目，其中所述第二 mnxl半色調段從所述圖像的第二 mxn像素塊導出。
8.根據權利要求1所述的方法，其中將所述第一mnxl半色調段與所述先入先出緩衝區中的一個或多個半色調段相比較包括:確定所述先入先出緩衝區中與所述第一 mnxl半色調段和連續緊接著所述第一 mnxl半色調段的任意其它半色調段相匹配的半色調段的最長連續範圍。
9.根據權利要求1所述的方法，其中所述第一mnxl半色調段與所述先入先出緩衝區中的所述特定半色調段相匹配，所述方法進一步包括:輸出指示所述特定半色調段在所述先入先出緩衝區中的地點的重複位置。
10.根據權利要求1所述的方法，其中所述mxn半色調矩陣的每個單元包含i_l個閾值，其中所述i_l個閾值限定i個像素值範圍，並且其中所述第一 mxn像素塊的第一 mxn半色調版本的每個單元包含1g2 (i)位值。
11.根據權利要求10所述的方法，其中對於所述第一mxn像素塊的每個特定單元，確定所述第一 mxn像素塊的第一 mxn半色調版本包括: 確定所述第一 mxn像素塊中所述特定單元的特定像素值； 確定所述mxn半色調矩陣的特定單元中的i個像素值範圍之一包含所述特定像素值，其中所述第一 mxn像素塊中的所述特定單元對應於所述mxn半色調矩陣的特定單元；並且 將表示確定所述i個像素值範圍之一的1g2 (i)位值寫入所述第一 mxn像素塊的第一mxn半色調版本的特定單元。
12.根據權利要求1所述的方法，其中確定所述第一mxn像素塊的第一mxn半色調版本包括:將所述mxn半色調矩陣在所述圖像上平鋪，使得所述mxn半色調矩陣的垂直相鄰平鋪的起始位置偏移q像素，所述方法進一步包括: 將rlxn填充像素列附加至所述圖像的最右列。
13.根據權利要求12所述的方法，其中P是在附加所述rlxn填充像素列之前像素中所述圖像的寬度，並且其中r是m-(p-q)modm。
14.一種計算設備，包括: 處理器； 數據儲存器；以及 存儲在所述數據儲存器中的程序指令，所述程序指令一旦由所述處理器執行就導致所述計算設備執行根據權利要求1至權利要求13中任意一項的方法的操作。
【文檔編號】H04N1/52GK103780796SQ201310499246
【公開日】2014年5月7日 申請日期:2013年10月22日 優先權日:2012年10月23日
【發明者】蘇東佩, 肯德裡克·翁, 拉裡·盧布曼, 麥可·M·張, 史蒂芬·L·施埃弗爾 申請人:京瓷辦公信息系統株式會社