庫模板篩法

文本圖像壓縮中需要創(chuàng)建在圖像中出現(xiàn)的形狀庫。這些形狀通常和字符有關，在圖像中出現(xiàn)的形狀就會被指向圖形庫的指針替換。一般來說，雖然存在許多變體，但處理步驟包括如下：

• 找出、分離并且抽取所有的標記，即圖像中聚集在一起出現(xiàn)的黑色像素。

• 建立一個包含圖像中發(fā)現(xiàn)所有標記的庫

• 通過識別圖像中的符號找到庫中與之最接近的標記實現(xiàn)，并度量一個標記和下一個標記的偏移值。

• 壓縮符號順序和偏移并存儲入庫。由于這一步驟中所存儲的信息可以產(chǎn)生稱為重構文本的原始圖像的近似，所以為了重構圖像無損，需要包括下面處理步驟：存儲足夠的信息以完成從重構文本中恢復原始圖像。

當標記被抽取出來以后，需要將其與已經(jīng)在庫中的標記匹配，所有匹配庫成員的標記都會被保存在一個集合中。如果當前標記與庫中現(xiàn)有的一個標記足夠匹配的話，則將其添加到與改符號相應的匹配標記集中，盡管將一個標記與每一個庫中模板進行匹配查找出與其最接近模板的可靠，但在一個模板被發(fā)現(xiàn)于一個特定的相似閾值之內(nèi)時即立即終止運算會更有效。如果沒有發(fā)現(xiàn)足夠近似的匹配點，則將新標記添加到庫中。模板匹配對成功識別標記至關重要，匹配過程一般通過檢查誤差圖來實現(xiàn)，誤差圖通過將新符號和庫成員逐比特進行異或得到。在計算誤差圖之前，匹配的雙方必須要正確注冊。新符號添加在庫中每個符號之前，為此需要在庫中設置一個固定的參考點。

概述

文本圖像(textual image 或 text image)是一種特殊類型的黑白二值圖像，它的主要特點是其內(nèi)容一般由文字部分組成。從數(shù)據(jù)壓縮的角度來看，文本圖像存在位圖和符號兩個層次的冗余，后者是由圖像中重復的符號引起的。針對文本圖像的壓縮標準和算法主要G3，G4JBIG和JBIG2等，其中 G3，G4和 JBIG 都是基于位圖層次的壓縮方法，而JBIG2是基于位圖和符號層次冗余的兩層壓縮方法。另外，基于混合光柵內(nèi)容( mixed raster content，MRC) 的DjVu 主要用于復合文檔的壓縮，它通過一個黑白二值掩碼(mask)將圖像分成前景和背景，然后對不同的部分再采用適合的算法分別進行壓縮，其中對于掩碼的壓縮采用的是JB2算法。JB2 是 JBIG2 的一種變體，它和 JBIG2 的基本思想和實現(xiàn)方法都是類似的。JBIG2是最先進的文本圖像壓縮算法，如上所述它實現(xiàn)了一個兩層壓縮結構：首先根據(jù)“字典”的思想，采用模式匹配策略將不同的符號存儲到一個模式字典中，這樣圖像中相同的符號就可以用字典中的匹配符號及其索引進行替代；然后對于得到的字典、索引以及符號的位置信息再采用基于信息熵的算術編碼進行壓縮。 模式匹配的過程中，所謂“相同”的符號是指其相對于人的視覺是相同的，而在位圖層次往往不完全相同。如何將視覺上相同的符號歸為一類是模式匹配算法面臨的一個很大挑戰(zhàn)。這是因為，由于掃描過程中的抖動、噪音 等原因，有些視覺上相同的符號在位圖層次可能有比較大的差異，而某些外形接近的不同符號在位圖層次的差異可能是比較小的。和英文文本圖像相比，中文文本圖像中的字符集規(guī)模更大，很多漢字結構比較復雜，且形近字非常多。中文文本圖像的這些特點增加了對符號進行模式匹配的難度 。

JBIG2 是由 ITU和ISO組成的二值圖像聯(lián)合專家組(joint bi-level image expert group，JBIG)提出的一個壓縮標準。JBIG2 的一個重要特點是：只規(guī)定了解碼的標準和流程，而并沒有定義一個明確的編碼器。JBIG2 將編碼程序開放，是為了鼓勵研究者們針對不同特點的文本圖像開發(fā)更加高效的編碼算法。

JBIG2 的主要技術最早由美國貝爾實驗室的Howard 等開發(fā)，主要包括 “模式匹配與替換 ”(pattern matching and substitution，PM&S) 和“軟模式匹配”(soft pattern matching，SPM)技術。這些技術后來被ISO 采納成為了 JBIG2 標準的一部分。美國加州大學圣地亞哥分校的 Ye 等對JBIG2 進行了系統(tǒng)的研究 ，主要從符號字典設計 、模式匹配速度和有損壓縮的重構圖像質(zhì)量控制等方面提出了很多先進的算法。對于有損壓縮系統(tǒng)，Ye 等針對英文字符的特點提取了符號的尺寸、象限矩心距離(quadrant centroid distance，QCD)以及拓撲結構作為特征，并利用這些特征來減少有損壓縮中的替換誤差。由于 Ye 等在 JBIG2 方面所做出的出色工作，其研究成果通過加州大學圣地亞哥分校的技術轉移部門轉讓給了Apago 公司并應用到其商業(yè)化的產(chǎn)品中，成功實現(xiàn)了技術成果的轉化。

意義

對于一些非常重要的正式文件，它的主要存儲方式為文本圖像。與文本文件相比較，圖像文件能夠?qū)鼍案又庇^、真實的進行表述，對其不易進行篡改或者偽造。比如一些更能體現(xiàn)其真實性和有效性的圖像文件，如包含手寫簽名、銀行票據(jù)的圖像文件。當今社會，不管是在商業(yè)經(jīng)濟方面還是政府部門等領域，對于很多重要的信息都是以電子圖片的方式進行交流的。然而，不管是什么事物，它都具有兩面性，在圖像文件的管理方面，有著不容忽視的劣勢。如果用圖像的形式存儲文字信息，信息量將變得很大，所需的存儲空間也比電子文本文件大，不利于文字信息的快速識別。隨著計算機技術的進步，這些不足將會逐漸被克服。

• 文本圖像檢索的實際應用涉及面廣，可以運用到辦公的文件管理、日常生活的文件查詢、國企銀行單位票據(jù)文件查詢和檢索等多個方面。

• 文本圖像文件的高效、智能分類。在工作中，為了提高管理效率、使得信息的查詢更加方便，就需要對大量的文本圖像信息做一定的整理和分類。比如公司合同文件，它是依據(jù)公司標志信息的不同，利用文本圖像檢索技術將大量的錯綜復雜的圖像文件進行分類和歸檔，高效智能的完成圖像文件的管理，提高了業(yè)務辦公的智能性和效率。

• 文本圖像自動查詢。雖然已經(jīng)有 PDF、WORD 等電子文檔查詢的應用軟件，但是用于檢索文本圖像內(nèi)容的應用軟件很罕見。日常生活中對文本圖像文件檢索的需求卻在增加。如果對大量文本圖像進行管理，不僅需要大量的人力、物力，而且工作量也非常大。尤其是需要查找圖片文件中的關鍵字等特定信息，就要人工進行查看每張圖的內(nèi)容，并且還要相當仔細，導致工作量的增加，效率也不高，不但成本耗費大，也不能滿足當前實際應用的需求。本文所研究的文本圖像自動檢索技術實現(xiàn)文本圖像文件的快速查詢和智能管理，能夠幫助文件管理

• 人員快速、高效地處理圖像文本文件，具有較大的實際應用意義。

• 知識產(chǎn)權保護。隨著 IP 時代的到來，人們對知識產(chǎn)權也越來越重視，并頒布了相關法律對其進行保護。為了有效地管理和搜索查詢只是產(chǎn)權文件，可以使用文本圖像檢索技術。圖像文件保證了產(chǎn)權文件的不易篡改，自動檢索技術提供了關鍵信息的快捷查詢。隨著文本圖像文件量的急劇增加，文本圖像的檢索技術的作用體現(xiàn)得越來越明顯。

• 合同管理。在當今法制社會中，具有法律效力的合同文件是經(jīng)濟市場中不可或缺的文件。合同文件的關鍵信息之一是個人簽章或者手寫簽名。在合同文件圖像的管理中，管理文件的員工不需要埋頭在紙質(zhì)文檔中尋找領導需要的合同文件，只需敲敲手指就能在計算機上查找出來。手寫字體的自動檢索技術應用到合同圖像文件中個人簽名內(nèi)容的識別，將大大提高對合同管理的效率。

• 其它用途。文本圖像檢索技術同樣可以應用到軍事中，對危險病毒文件自動監(jiān)控和攔截以及對遠方地理信息的描述等等。

庫模板篩法是一種模板匹配方法，主要基于標記的特征，與輸入標記明顯不同的符號不必匹配，例如在寬度和長度上明顯不同的模板必定是不相似的。庫模板篩法主要基于面積和周長，當抽取標記后很容易得到這些數(shù)據(jù)，然而在實踐的操作中并沒有看起來容易，一方面因為它們和標記的寬度和高度有關；另一方面因為它們對噪聲和數(shù)字化過程的參數(shù)特別敏感。其他看上去更確定的特征是垂直和水平的白行程數(shù)。庫模板篩法的一個更好基礎應該是比較兩個標記中黑像素團的分布。通過將像素根據(jù)其質(zhì)心注冊，然后將其劃分為圍繞質(zhì)心的4象限來實現(xiàn)。對于每個象限，計算其質(zhì)心：對4個局部質(zhì)心，分別計算其在兩個標記中位置的距離，最后將4個距離平均。這一過程可能不斷地重復，以確定一個基于原始質(zhì)心的0級上距離（改質(zhì)心距離為0，因為使用的是質(zhì)心注冊）、一個如上所述的1級上的距離，以及更高級上的距離。測試表明，優(yōu)良的篩選結果往往是在1級距離上獲得的，更復雜的處理并無必要。

標記(signature)是邊界的一維表達，可以用多種方法來產(chǎn)生。其基本思想是將原始的二維邊界用元函數(shù)來表示，以降低表達難度。最簡單的方法就是把從重心到邊界的距離作為角度的函數(shù)來標記。

標記與鏈碼同樣不受邊界平移的影響，但是當邊界旋轉或者發(fā)生尺度變換時，標記格會發(fā)生改變。對于旋轉問題，可以采用類似于鏈碼的旋轉歸一化方法進行解決。更常用的方法是通過固定標記的起始點來歸一化。例如，可以選擇離重心最遠的邊界點作為起始點，或者選擇主軸上的某一點。雖然后者的計算量比較大，但是它比前者更加可靠，因為它用到了所有的邊界點來參與計算。而對尺度變化則可以通過幅度的歸一化來處理。

標準模板庫是一個C 軟件庫，大量影響了C 標準程序庫但并非是其的一部分。其中包含4個組件，分別為算法、容器、函數(shù)、迭代器。

模板是C 程序設計語言中的一個重要特征，而標準模板庫正是基于此特征。標準模板庫使得C 編程語言在有了同Java一樣強大的類庫的同時，保有了更大的可擴展性。

在C 標準中，STL被組織為下面的13個頭文件：、 、 、 、 、 、

標準模板庫歷史

標準模板庫系由Alexander Stepanov創(chuàng)造于1979年前后，這也正是比雅尼·斯特勞斯特魯普創(chuàng)造C 的年代。

雖然David R. Musser于1971年開始即在計算機幾何領域發(fā)展并倡導某些泛型程序設計觀念，但早期并沒有任何編程語言支持泛型程序設計。第一個支持泛型概念的語言是Ada。Alex和Musser曾于1987開發(fā)出一套相關的Ada library.

標準模板庫設計人Stepanov早期從事教育工作，1970年代研究泛型程序設計，那時他與其同事一起在GE公司開發(fā)出一個新的程序語言——Tecton。

1983年，Stepanov先生轉至Polytechnic大學教書，繼續(xù)研究泛型程序設計，同時寫了許多Scheme的程序，應用在graph與network的算法上，1985年又轉至GE公司專門教授高階程序設計，并將graph與network的Scheme程序，改用Ada寫，用了Ada以后，他發(fā)現(xiàn)到一個動態(tài)（dynamically）類型的程序（如Scheme）與強制（strongly）類型的程序（如Ada）有多么的不同。

在動態(tài)類型的程序中，所有類型都可以自由的轉換成別的類型，而強制類型的程序卻不能。但是，強制類型在出錯時較容易發(fā)現(xiàn)程序錯誤。

1988年Stepanov先生轉至HP公司運行開發(fā)泛型程序庫的工作。此時，他已經(jīng)認識C語言中指針(pointer)的威力，他表示一個程序員只要有些許硬件知識，就很容易接受C語言中指針的觀念，同時也了解到C語言的所有數(shù)據(jù)結構均可以指針間接表示，這點是C與Ada、Scheme的最大不同。

Stepanov并認為，雖然C 中的繼承功能可以表示泛型設計，但終究有個限制。雖然可以在基礎類型（superclass）定義算法和接口，但不可能要求所有對象皆是繼承這些，而且龐大的繼承體系將減低虛擬（virtual）函數(shù)的運行效率，這便違反的前面所說的“效率”原則。

到了C 模板觀念，Stepanov參加了許多有關的研討會，與C 之父Bjarne討論模板的設計細節(jié)。如，Stepanov認為C 的函數(shù)模板（function template）應該像Ada一樣，在聲明其函數(shù)原型后，應該顯式的聲明一個函數(shù)模板之實例（instance）；Bjarne則不然，他認為可以通過C 的重載（overloading）功能來表達。

Stepanov想像中的函數(shù)模板：

in*.hpp
template
             
              
Tsquare(Tx){returnx*x;}

in*.cpp
doublesquare(double);
cout<
               
               
Bjarne認為的函數(shù)模板：
               
in*.hpp
template
                
                 
Tsquare(Tx){returnx*x;}

in*.cpp
cout<
                  
                  
幾經(jīng)爭辯，Stepanov發(fā)現(xiàn)Bjarne是對的（引用侯俊杰《標準模板庫講座·第三章》）。事后Stepanov回想起來非常同意Bjarne的作法。 
                  
template 引數(shù)推導機制（arguments deduction ，在標準模板庫中占非常重要的角色。Alexander Stepanov（標準模板庫創(chuàng)造者）在與Dr. Dobb's Journal進行的訪談中說道‘1992 我重回generic-library的開發(fā)工作。這時候C 有了template 
                  
“我發(fā)現(xiàn)Bjarne完成了一個非常美妙的設計。之前我在Bell Lab曾參與數(shù)次template的相關設計討論，并且非常粗暴地要求Bjarne應該將C template設計得盡可能像Ada generics那樣。我想由于我的爭辯是如此地粗暴，他決定反對。我了解到在C 中除了擁有template classes之外還擁有template functions的重要性。然而我認為template function應該像Ada generics一樣，也就是說它們應該是顯式實例，Bjarne沒有聽進我的話，他設計了一個template function機制，其中的template是以一個重載化機制 （overloading mechanism來進行隱式實例這項特殊的技術對我的工作具有關鍵性的影響，因為我發(fā)現(xiàn)它使我得以完成Ada不可能完成的許多動作。我非常高興Bjarne當初沒有聽我的意見。’（DDJ 1995 年三月號）” 
                  
事實上，C 的模板，本身即是一套復雜的宏語言（macro language），宏語言最大的特色為：所有工作在編譯時期就已完成。顯式的聲明函數(shù)模板之實例，與直接通過C 的重載功能隱式聲明，結果一樣，并無很大區(qū)別，只是前者加重程序員的負擔，使得程序變得累贅。 
                  
1992年Meng Lee加入Alex的項目，成為另一位主要貢獻者。 
                  
1992年，HP泛型程序庫項目結束，小組解散，只剩下Stepanov先生與Meng Lee小姐（她是東方人，標準模板庫的英文名稱其實是取STepanov與Lee而來），Lee先前研究的是編譯器的制作，對C 的模板很熟，第一版的標準模板庫中許多程序都是Lee的杰作。 
                  
1993年，Andy Koenig到史丹佛演講，Stepanov便向他介紹標準模板庫，Koenig聽后，隨即邀請Stepanov參加1993年11月的ANSI/ISO C 標準化會議，并發(fā)表演講。 
                  
Bell實驗室的Andrew Koenig于1993年知道標準模板庫研究計劃后，邀請Alex于是年11月的ANSI/ISO C 標準委員會會議上展示其觀念。并獲得與會者熱烈的回應。 
                  
1994年1月6日，Koenig寄封電子郵件給Stepanov，表示如果Stepanov愿意將標準模板庫的幫助文檔撰寫齊全，在1月25日前提出，便可能成為標準C 的一部分。Stepanov回信道："Andy, are you crazy" 。 Koenig便說："Well, yes I am crazy,but why not try it"。 
                  
Alex于是在次年夏天在Waterloo舉行的會議前完成其正式的提案，并以百分之八十壓倒性多數(shù)，一舉讓這個巨大的計劃成為C Standard的一部分。 
                  
標準模板庫于1994年2月年正式成為ANSI/ISO C 的一部分，它的出現(xiàn)，促使C 程序員的思維方式更朝向泛型編程（generic program）發(fā)展。
                  
標準模板庫內(nèi)容
 
                  
STL 將“在數(shù)據(jù)上執(zhí)行的操作”與“要執(zhí)行操作的數(shù)據(jù)分開”，分別以如下概念指代：
                  

                   
 
容器：包含、放置數(shù)據(jù)的地方。
                   
 
迭代器：在容器中指出一個位置、或成對使用以劃定一個區(qū)域，用來限定操作所涉及到的數(shù)據(jù)范圍。
                   
 
算法：要執(zhí)行的操作。
                  
 
                  
標準模板庫包含了序列容器（sequence containers）與關系容器（associative containers）。 
                  
序列容器包括vector,list,forward_list,deque和array等。 
                  
關聯(lián)容器包括set,multiset,map,multimap,unordered_set,bitset和valarray等。
                  
標準模板庫迭代器
 
                  
迭代器是泛化的指針，通過使用迭代器，開發(fā)者可以操作數(shù)據(jù)結構而無需關心其內(nèi)部實現(xiàn)。根據(jù)迭代器的操作方式的不同，迭代器分為五種：
                  

                   
 
輸入迭代器
                   
 
輸出迭代器
                   
 
前向迭代器
                   
 
雙向迭代器
                   
 
隨機訪問迭代器
                  
                  
標準模板庫算法
 
                  
STL提供了一些常見 的算法，如排序和搜索等。這些算法與數(shù)據(jù)結構的實現(xiàn)進行了分離。因此，用于也可對自定義的數(shù)據(jù)結構使用這些算法，只需讓這些自定義的數(shù)據(jù)結構擁有算法所預期的迭代器。
                  
標準模板庫函數(shù)對象
 
                  
狹義的函數(shù)對象即重載了操作符()的類的實例，而廣義來講所有可用 x(...) 形式調(diào)用的 x 都可稱為函數(shù)對象、或曰可調(diào)用對象。
                  
標準模板庫適配器
 
                  
適配器（Adaptor）為一個模板類，用于提供接口映射。 
                  
標準模板庫與C 標準程序庫的差異
 
                  
一個常見的誤解是STL是C 標準程序庫的一部分，但事實上并非如此。例如hash table的數(shù)據(jù)結構實當前STL中有
                  
                   模板可供調(diào)用，但C 標準程序庫一直到C 11才加入了
                   
                    。 2100433B
                   
                  
                 
                
              
             

afximpl.h 實現(xiàn)了一套模板庫，如CArray, CList, CMap等。因為在發(fā)布時STL尚未進入C 語言標準，因此ATL自行開發(fā)實現(xiàn)了一套。

ATL定義三個宏來來影響生成的COM服務器的優(yōu)化。

• _ATL_MIN_CRT 服務器不鏈接標準的C/C 運行庫，并且ATL提供了函數(shù)malloc、realloc、new和delete的一個實現(xiàn)。不能調(diào)用任何其他的C/C 運行庫的函數(shù)。_mainATL向?qū)傻腁TL工程為所有的Release版本的定義了_ATL_MIN_CRT，但是沒有為Debug版本定義這個符號宏。

• _ATL_DLL 服務器動態(tài)鏈接工具函數(shù)庫atl.dll

• _ATL_STATIC_REGISTRY 服務器靜態(tài)鏈接對組件注冊的支持

Debug配置沒有定義上述三個符號宏。Release MinSize配置定義了_ATL_MIN_CRT和_ATL_DLL。Release MinDependency配置定義了_ATL_MIN_CRT和_ATL_STATIC_REGISTRY。