第一篇：特征選擇算法綜述20160702

特征選擇方法綜述

控制與決策 2012.2

? ? ? ? ? 問(wèn)題的提出 特征選擇框架

基于搜索策略劃分特征選擇方法 基于評(píng)價(jià)準(zhǔn)則劃分特征選擇方法 結(jié)論

一、問(wèn)題的提出

特征選擇是從一組特征中挑選出一些最有效的特征以降低特征空間維數(shù)的過(guò)程，是模式識(shí)別的關(guān)鍵問(wèn)題之一。對(duì)于模式識(shí)別系統(tǒng)，一個(gè)好的學(xué)習(xí)樣本是訓(xùn)練分類器的關(guān)鍵，樣本中是否含有不相關(guān)或冗余信息直接影響著分類器的性能。因此研究有效的特征選擇方法至關(guān)重要。

特征選擇算法的目的在于選擇全體特征的一個(gè)較少特征集合，用以對(duì)原始數(shù)據(jù)進(jìn)行有效表達(dá)按照特征關(guān)系度量劃分，可分為依賴基尼指數(shù)、歐氏距離、信息熵。

二、特征選擇框架

由于子集搜索是一個(gè)比較費(fèi)時(shí)的步驟，一些學(xué)者基于相關(guān)和冗余分析，給出了下面一種特征選擇框架，避免了子集搜索，可以高效快速地尋找最優(yōu)子集。

從特征選擇的基本框架看出，特征選擇方法中有4個(gè)基本步驟：候選特征子集的生成（搜索策略）、評(píng)價(jià)準(zhǔn)則、停止準(zhǔn)則和驗(yàn)證方法。目前對(duì)特征選擇方法的研究主要集中于搜索策略和評(píng)價(jià)準(zhǔn)則。因而，本文從搜索策略和評(píng)價(jià)準(zhǔn)則兩個(gè)角度對(duì)特征選擇方法進(jìn)行分類。

三、基于搜索策略劃分特征選擇方法

基本的搜索策略按照特征子集的形成過(guò)程，形成的特征選擇方法如下：

圖3基于搜索策略劃分特征選擇方法

其中，全局搜索如分支定界法，存在問(wèn)題： 1）很難確定優(yōu)化特征子集的數(shù)目； 2）滿足單調(diào)性的可分性判據(jù)難以設(shè)計(jì)；

3）處理高維多類問(wèn)題時(shí)，算法的時(shí)間復(fù)雜度較高。

隨機(jī)搜索法如模擬退火、遺傳算法、禁忌搜索算法等，存在問(wèn)題：

1）具有較高的不確定性，只有當(dāng)總循環(huán)次數(shù)較大時(shí)，才可能找到較好的結(jié)果。

2）在隨機(jī)搜索策略中，可能需對(duì)一些參數(shù)進(jìn)行設(shè)置，參數(shù)選擇的合適與否對(duì)最終結(jié)果的好壞起著很大的作用。

啟發(fā)式搜索如SFS、SBS、SFFS、SFBS等，存在問(wèn)題： 1）雖然效率高，但是它以犧牲全局最優(yōu)為代價(jià)。

每種搜索策略都有各自的優(yōu)缺點(diǎn)，在實(shí)際應(yīng)用過(guò)程中，根據(jù)具體環(huán)境和準(zhǔn)則函數(shù)來(lái)尋找一個(gè)最佳的平衡點(diǎn)。例如，特征數(shù)較少，可采用全局最優(yōu)搜索策略；若不要求全局最優(yōu)，但要求計(jì)算速度快，可采用啟發(fā)式策略；若需要高性能的子集，而不介意計(jì)算時(shí)間，則可采用隨機(jī)搜索策略。

四、基于評(píng)價(jià)準(zhǔn)則劃分特征選擇方法

圖4基于評(píng)價(jià)準(zhǔn)則劃分特征選擇方法

（一）考慮單個(gè)特征對(duì)分類的貢獻(xiàn)，特征選擇方法依據(jù)其與分類器的關(guān)系分為：Filter方法、Wrapper方法和Embedded方法３類。

封裝式算法作為一種經(jīng)典的特征選擇算法類型采用學(xué)習(xí)算法進(jìn)行特征選擇，其選擇過(guò)程復(fù)雜耗時(shí)，目前多與過(guò)濾式特征選擇算法結(jié)合，輔助特征選擇；嵌入式算法則分多步驟采用不同選擇方式，算法繁瑣，其代表算法是基于稀疏多項(xiàng)式邏輯回歸模型理論的SBMLR算法等；過(guò)濾式算法不需其他學(xué)習(xí)算法，主要考察特征間計(jì)量關(guān)系，方法簡(jiǎn)單，時(shí)間復(fù)雜度相對(duì)較低，代表算法包括：基于特征權(quán)重的Relief F、Fisher、SPEC以及基于互信息的MRMR算法等。（1）Filter方法：通過(guò)分析特征子集內(nèi)部的信息來(lái)衡量特征子集的好壞，不依賴于分類器。Filter實(shí)質(zhì)上屬于一種無(wú)導(dǎo)師學(xué)習(xí)算法。

常用：基于特征權(quán)重的Relief F、Fisher、SPEC以及基于互信息的MRMR算法

Filter 特征選擇方法一般使用評(píng)價(jià)準(zhǔn)則來(lái)增強(qiáng)特征與類的相關(guān)性，削減特征之間的相關(guān)性。將評(píng)價(jià)函數(shù)分成4類：

1）距離度量。距離度量通常也認(rèn)為是分離性、差異性或者辨識(shí)能力的度量。最為常用的一些重要距離測(cè)度：歐氏距離、S階Minkowski測(cè)度、Chebychev 距離、平方距離等。

2）信息度量。信息度量通常采用信息增益(IG)或互信息(MI)衡量。

信息增益：有無(wú)這個(gè)特征對(duì)分類問(wèn)題的影響的大小。

互信息：描述兩個(gè)隨機(jī)變量之間相互依存關(guān)系的強(qiáng)弱。

泛化的信息度量函數(shù)標(biāo)準(zhǔn)：

其中，C：類別；f：候選特征；S：已選特征；g(C,f,S)：C，f，S之間的信息量； ?：調(diào)控系數(shù)；δ：懲罰因子

① BIF(best individual feature)是一種最簡(jiǎn)單最直接的特征選擇方法。

評(píng)價(jià)函數(shù)：

I（）：互信息

降序排序

前k個(gè)

優(yōu)缺點(diǎn)：這種方法簡(jiǎn)單快速，適合于高維數(shù)據(jù)。沒(méi)有考慮到所選特征間的相關(guān)性，會(huì)帶來(lái)較大的冗余。

② MIFS(mutual information feature selection)：互信息特征選擇。使用候選特征f與單個(gè)已選特征s相關(guān)性對(duì)f進(jìn)行懲罰的方法。

β：調(diào)節(jié)系數(shù)。β在[0.5,1]時(shí)，算法性能較好。

③ mRMR(minimal-redundancy and maximal-relevance)方法。思想：最大化特征子集和類別的相關(guān)性，最小化特征之間的冗余。

④ FCBF(fast correlation-based filter)。基于相互關(guān)系度量給出的一種算法。對(duì)于線性隨機(jī)變量，用相關(guān)系數(shù)分析特征與類別、特征間的相互關(guān)系。對(duì)于非線性隨機(jī)變量，采用對(duì)稱不確定性(SU)來(lái)度量，對(duì)于兩個(gè)非線性隨機(jī)變量X和Y，它們的相互關(guān)系表示為：

H（）：信息熵

基本思想：根據(jù)所定義的C-相關(guān)（特征與類別的相互關(guān)系）和F-相關(guān)（特征之間的相互關(guān)系），從原始特征集合中去除C-相關(guān)值小于給定閾值的特征，再對(duì)剩余的特征進(jìn)行冗余分析。

⑤

CMIM(conditional mutual information maximization)。利用條件互信息來(lái)評(píng)價(jià)特征的重要性程度，即在已知已選特征集S的情況下通過(guò)候選特征f與類別C的依賴程度來(lái)確定

f的重要性，其中條件互信息I(C;f|S)值越大，f能提供的新信息越多。

3）依賴性度量。有許多統(tǒng)計(jì)相關(guān)系數(shù)被用來(lái)表達(dá)特征相對(duì)于類別可分離性間的重要性程度。如：Pearson相關(guān)系數(shù)、概率誤差、Fisher分?jǐn)?shù)、先行可判定分析、最小平方回歸誤差、平方關(guān)聯(lián)系數(shù)、t-test、F-Statistic等。

Hilbert-Schmidt 依賴性準(zhǔn)則(HSIC)可作為一個(gè)評(píng)價(jià)準(zhǔn)則度量特征與類別的相關(guān)性。核心思想是一個(gè)好的特征應(yīng)該最大化這個(gè)相關(guān)性。

t:所選特征個(gè)數(shù)上限；F：特征集合；S：已選特征集合；J(S)：評(píng)價(jià)準(zhǔn)則

從式中可知需要解決兩個(gè)問(wèn)題：一是評(píng)價(jià)準(zhǔn)則J(S)的選擇；二是算法的選擇。

4）一致性度量

給定兩個(gè)樣本,若他們特征值均相同,但所屬類別不同,則稱它們是不一致的;否則,是一致的。試圖保留原始特征的辨識(shí)能力,找到與全集有同樣區(qū)分類別能力的最小子集。典型算法有Focus、LVF等。

Filter方法選擇合適的準(zhǔn)則函數(shù)將會(huì)得到較好的分類結(jié)果。

優(yōu)點(diǎn)：可以很快地排除很大數(shù)量的非關(guān)鍵性的噪聲特征,縮小優(yōu)化特征子集搜索的規(guī)模,計(jì)算效率高,通用性好,可用作特征的預(yù)篩選器。

缺點(diǎn)：它并不能保證選擇出一個(gè)優(yōu)化特征子集,尤其是當(dāng)特征和分類器息息相關(guān)時(shí)。因而,即使能找到一個(gè)滿足條件的優(yōu)化子集,它的規(guī)模也會(huì)比較龐大,會(huì)包含一些明顯的噪聲特征。

2）Wrapper法：評(píng)價(jià)函數(shù)是一個(gè)分類器，采用特定特征子集對(duì)樣本集進(jìn)行分類，根據(jù)分類的結(jié)果來(lái)衡量該特征子集的好壞。Wrapper實(shí)質(zhì)上是一種有導(dǎo)師學(xué)習(xí)算法。訓(xùn)練集 測(cè)試集

優(yōu)點(diǎn)：準(zhǔn)確率高

缺點(diǎn)：1）為選擇出性能最好的特征子集，Wrapper算法需要的計(jì)算量巨大； 2）該方法所選擇的特征子集依賴于具體學(xué)習(xí)機(jī)； 3）容易產(chǎn)生“過(guò)適應(yīng)”問(wèn)題，推廣性能較差

（3）Embedded方法。將特征選擇集成在學(xué)習(xí)機(jī)訓(xùn)練過(guò)程中，通過(guò)優(yōu)化一個(gè)目標(biāo)函數(shù)在訓(xùn)練分類器的過(guò)程中實(shí)現(xiàn)特征選擇。

優(yōu)點(diǎn)：相對(duì)于Wrapper方法，不用將訓(xùn)練數(shù)據(jù)集分成訓(xùn)練集和測(cè)試集兩部分，避免了為評(píng)估每一個(gè)特征子集對(duì)學(xué)習(xí)機(jī)所進(jìn)行的從頭開(kāi)始的訓(xùn)練，可以快速地得到最佳特征子集，是一種高效的特征選擇方法。

缺點(diǎn)：構(gòu)造一個(gè)合適的函數(shù)優(yōu)化模型是該方法的難點(diǎn)。

通常，將Filter方法的高效與Wrapper方法的高準(zhǔn)確率進(jìn)行結(jié)合，可得到更優(yōu)的特征子集?；旌咸卣鬟x擇過(guò)程一般由兩個(gè)階段組成：

1）使用Filter方法初步剔除大部分無(wú)關(guān)或噪聲特征,只保留少量特征,從而有效地減小后續(xù)搜索過(guò)程的規(guī)模。

2）將剩余的特征連同樣本數(shù)據(jù)作為輸入?yún)?shù)傳遞給Wrapper選擇方法,以進(jìn)一步優(yōu)化選擇重要的特征。

（二）依據(jù)特征之間的聯(lián)合作用對(duì)分類的貢獻(xiàn)，分為：CFS（Correltion based Feature Selector）、CFSPabs(CFS based on the absolute of Perons’s correlation coefficient)、DFS(Discernibility of Feature Subsets)。

（1）CFS：基于關(guān)聯(lián)特征的特征選擇。CFS計(jì)算整個(gè)特征子集的類間區(qū)分能力實(shí)現(xiàn)特征選擇，使得被選特征子集中的特征之間盡可能不相關(guān)，而與類標(biāo)高度相關(guān)。

Ms：度量了包含ｋ個(gè)特征的特征子集S的類別辨識(shí)能力。

：特征f（f?）與類別C的相關(guān)系數(shù)的均值 ：特征之間相關(guān)系數(shù)的均值

分子：特征子集S的類預(yù)測(cè)能力

分母：特征子集S中特征的冗余程度

適合于二分類

（2）CFSPabs：基于皮爾森相關(guān)系數(shù)的絕對(duì)值的相關(guān)特征選擇。

（3）DFS：特征子集區(qū)分度量。

:當(dāng)前i個(gè)特征的特征子集在整個(gè)數(shù)據(jù)集上的均值向量 :當(dāng)前i個(gè)特征的特征子集在第ｊ類數(shù)據(jù)集上的均值向量 ：第ｊ類中第k個(gè)樣本對(duì)應(yīng)當(dāng)前i 個(gè)特征的特征值向量

分子：ｌ個(gè)類別中各類別對(duì)應(yīng)包含當(dāng)前ｉ個(gè)特征的特征子集的樣本中心向

量與整個(gè)樣本集對(duì)應(yīng)當(dāng)前ｉ個(gè)特征的中心向量的距離平方和，其值越大，類間越疏。

分母：各個(gè)類別對(duì)應(yīng)包含當(dāng)前ｉ個(gè)特征的特征子集的類內(nèi)方差。方差越小，類內(nèi)越聚

五、結(jié)論

現(xiàn)有特征選擇研究主要著眼于選擇最優(yōu)特征子集所需要的兩個(gè)主要步驟：特征子集搜索 策略和特征子集性能評(píng)價(jià)準(zhǔn)則。將Filter方法和Wrapper方法兩者結(jié)合，根據(jù)特定的環(huán)境選擇所需要的度量準(zhǔn)則和分類器是一個(gè)值得研究的方向。

第二篇：基于形狀特征的圖像檢索算法仿真實(shí)現(xiàn)研究

本科畢業(yè)設(shè)計(jì)（論文）

工 作 手 冊(cè)

（理工類專業(yè)適用）

學(xué) 院

專業(yè)班級(jí)

姓 名

學(xué) 號(hào)

指導(dǎo)教師

二○一 年 月 日

基于形狀特征的圖像檢索算法仿真實(shí)現(xiàn)研究

摘要:近年來(lái),隨著數(shù)字多媒體和移動(dòng)計(jì)算機(jī)以及互聯(lián)網(wǎng)信息技術(shù)的快速進(jìn)步發(fā)展,數(shù)字圖像的應(yīng)用數(shù)量正以驚人的增長(zhǎng)速度不斷增長(zhǎng)。面對(duì)日益豐富的數(shù)字圖像媒體信息這個(gè)海洋,人們?nèi)匀恍枰行У貜闹胁粩喃@取所有人期望能夠得到的更多媒體信息。因此,在一個(gè)大規(guī)模的數(shù)字圖像檢索數(shù)據(jù)庫(kù)中如何進(jìn)行快速、準(zhǔn)確的圖像檢索已經(jīng)成為當(dāng)前人們圖像研究的一個(gè)熱點(diǎn)。

為了能夠?qū)崿F(xiàn)快速而準(zhǔn)確地進(jìn)行信息檢索數(shù)字圖像,利數(shù)字圖像的主要視覺(jué)信息特征,如圖像顏色、紋理、形狀等元素，基于形狀的數(shù)字圖像信息檢索處理技術(shù)應(yīng)運(yùn)而生。本文主要深入研究基于圖像形狀基本特征的邊緣圖像偵測(cè)檢索,邊緣圖像檢測(cè)檢索是基于圖像形狀基本特征的一種有效檢索圖像方法,邊緣檢測(cè)是檢索圖像最基本的形狀特性。在圖像景物邊緣特征檢測(cè)中,微分這個(gè)算子算法可以準(zhǔn)確提取和輸出景物圖像的一些細(xì)節(jié)分析信息,景物圖像邊緣特征是圖像細(xì)節(jié)分析信息中最主要具有不可描述性的景物邊緣特征的部分,也是進(jìn)行圖像邊緣分析過(guò)程中的一個(gè)不可或缺的部分。本文詳細(xì)地闡述分析了一種局部邊緣厚度檢測(cè)算子方法,即canny方法算子,用c++編程語(yǔ)言實(shí)現(xiàn)各方法算子的局部邊緣檢測(cè),并根據(jù)算子邊緣厚度檢測(cè)的準(zhǔn)確有效性和邊緣定位的準(zhǔn)確可靠性,得出這種canny方法算子已經(jīng)具備了所有最優(yōu)化的邊緣厚度檢測(cè)所應(yīng)必需的各種特性。并通過(guò)基于圖像輪廓的圖形描述表示方法,傅里葉輪廓描述符對(duì)一個(gè)圖像的輪廓形狀及其特征特點(diǎn)進(jìn)行輪廓描述并將其存入圖像數(shù)據(jù)庫(kù)中。對(duì)行業(yè)也相應(yīng)的具有檢索查詢功能。

關(guān)鍵詞:形狀特征檢索;邊緣圖像檢測(cè);傅里葉描述符

一、前言

隨著現(xiàn)代信息化工業(yè)社會(huì)的到來(lái),幾乎任何一個(gè)學(xué)科研究領(lǐng)域的技術(shù)發(fā)展都和現(xiàn)代計(jì)算機(jī)技術(shù)密切聯(lián)系有關(guān),人們所需要處理的圖象信息已不僅僅只是一些數(shù)字、符號(hào)等的信息,而是越來(lái)越多地與人接觸并得到大量的數(shù)字圖象內(nèi)容信息.其中例如:航空衛(wèi)星信息遙感監(jiān)測(cè)圖象、醫(yī)學(xué)遙感圖象、地理水文信息監(jiān)測(cè)圖象等.而且在實(shí)際技術(shù)應(yīng)用中隨著時(shí)間的不斷推移,圖象信息數(shù)量也在不斷擴(kuò)大,利用各種人力來(lái)對(duì)這些圖象信息進(jìn)行內(nèi)容瀏覽和信息檢索，不僅僅需要大量的精力和時(shí)間,浪費(fèi)大量的的人力,而且?guī)缀跻咽遣豢赡芡瓿傻囊患隆＿@樣需要利用計(jì)算機(jī)對(duì)這些數(shù)字圖象內(nèi)容進(jìn)行有效內(nèi)容組織和信息檢索便已經(jīng)成為現(xiàn)代人們科學(xué)研究的重要課題.因而傳統(tǒng)的數(shù)字圖象內(nèi)容表達(dá)和信息檢索處理方法往往是需要使用圖象文件名、標(biāo)題、關(guān)鍵詞數(shù)字等.目前,這種檢索方法已不能完全滿足現(xiàn)代人們的技術(shù)要求.因此,人們?cè)絹?lái)越迫切地認(rèn)識(shí)需要對(duì)這些圖象的各種可視性和特征圖象進(jìn)行信息提取,并且根據(jù)這些可視特征對(duì)各種圖象內(nèi)容進(jìn)行信息檢索.基于圖象內(nèi)容的數(shù)字圖象信息檢索處理技術(shù),也正是在這樣的一種情況下發(fā)展產(chǎn)生的.基于圖象內(nèi)容的數(shù)據(jù)圖象信息檢索數(shù)據(jù)技術(shù)就是通過(guò)數(shù)據(jù)分析一個(gè)圖象的主要內(nèi)容(例例如:顏色、紋理、形狀等),從大量活動(dòng)視頻圖象庫(kù)中查找含有特定物體的圖象,它充分克服了現(xiàn)代傳統(tǒng)檢索方法的不足,融合了數(shù)字圖象處理、圖象識(shí)別和網(wǎng)絡(luò)圖象檢索數(shù)據(jù)庫(kù)等多個(gè)領(lǐng)域的最新技術(shù)成果,從而完全可以為你提供更有效的圖象檢索技術(shù)手段.它們既充分體現(xiàn)了特征圖象的基本信息處理特點(diǎn),又充分結(jié)合了現(xiàn)代傳統(tǒng)圖象數(shù)據(jù)庫(kù)檢索技術(shù).其基本檢索過(guò)程一般是:首先對(duì)一個(gè)圖象特征進(jìn)行圖像預(yù)處理,然后根據(jù)特征圖象的基本內(nèi)容從特征圖象中直接選取所有有需要的特征圖象形狀特征,存于圖象數(shù)據(jù)庫(kù)中;然后當(dāng)對(duì)一個(gè)圖象特征進(jìn)行勾畫檢索時(shí),對(duì)于一個(gè)圖象已知的特征圖象首先抽取其具有相應(yīng)的圖象特征,然后在整個(gè)圖象數(shù)據(jù)庫(kù)中進(jìn)行檢索與其相似的特征圖象,也或者可以根據(jù)相對(duì)于某一個(gè)的查詢對(duì)象要求直接給出一些圖象特征點(diǎn)和值,然后根據(jù)所需要給定的圖象特征點(diǎn)和值在整個(gè)圖象數(shù)據(jù)庫(kù)中進(jìn)行檢索所要的特征圖象.結(jié)果例如:對(duì)于基本相同形狀帶有特征的圖象檢索,你或許可以直接給出一些有關(guān)被勾畫檢索某個(gè)對(duì)象的基本形狀特征描述,可以認(rèn)為是一些帶有特征點(diǎn)的值,也或者可以認(rèn)為是勾畫出的檢索對(duì)象的形狀略圖;對(duì)于基本相同顏色的圖象檢過(guò),可以直接給出不同顏色的物體比例或者關(guān)系,等等.最后,給出圖象檢索后的結(jié)果.目前,從事這一技術(shù)課題相關(guān)研究的年輕人越來(lái)越多,國(guó)外許多著名科研機(jī)構(gòu)和專家學(xué)者都在積極進(jìn)行許多有關(guān)這一技術(shù)課題的相關(guān)研究,例如:公司的數(shù)據(jù)檢索系統(tǒng).國(guó)內(nèi)的許多專家學(xué)者和相關(guān)科研機(jī)構(gòu)也在積極進(jìn)行此技術(shù)問(wèn)題的相關(guān)研究.本文首先對(duì)基于對(duì)象內(nèi)容實(shí)體圖象的的檢索數(shù)據(jù)進(jìn)行了簡(jiǎn)要的理論概括,然后對(duì)基于實(shí)體對(duì)象動(dòng)態(tài)形狀的實(shí)體圖象內(nèi)容檢索數(shù)據(jù)理論基礎(chǔ)進(jìn)行了深入的理論研究,包括:基于對(duì)象形狀的實(shí)體圖象內(nèi)容檢索計(jì)算方法,對(duì)象實(shí)體形狀的綜合描述,圖象形狀配匹檢索算法,最后本文給出了一個(gè)基于對(duì)象形狀的實(shí)體圖象內(nèi)容檢索數(shù)據(jù)原型管理系統(tǒng),并在一臺(tái)微機(jī)上加以實(shí)現(xiàn),該原型系統(tǒng)主要功能包括內(nèi)容圖象檢索數(shù)據(jù)庫(kù)的管理建立,數(shù)據(jù)庫(kù)的日常維護(hù),圖象的信息查詢等幾個(gè)功能.二、研究介紹

2.1、課題背景及研究意義

隨著現(xiàn)代多媒體網(wǎng)絡(luò)技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)、通信網(wǎng)絡(luò)技術(shù)及互聯(lián)網(wǎng)絡(luò)的迅速進(jìn)步發(fā)展,人們正在快速地發(fā)展進(jìn)入一個(gè)現(xiàn)代信息化的新社會(huì)?，F(xiàn)代信息技術(shù)已不可能能夠運(yùn)用各種技術(shù)手段大量的進(jìn)行采集和分析產(chǎn)生各種類型的海量多媒體信息數(shù)據(jù),人們對(duì)各種多媒體信息的采集需求也越來(lái)越大量和頻繁。雖然人類信息的數(shù)量快速增長(zhǎng)直接促進(jìn)了人類社會(huì)的快速發(fā)展,但是由于信息快速膨脹也給現(xiàn)代人類社會(huì)帶來(lái)了過(guò)多的的信息量以至于遠(yuǎn)遠(yuǎn)超過(guò)了這類人的整體接受信息能力。因此,除了怎樣獲取、處理和傳輸存儲(chǔ)各種多媒體信息十分重要,怎樣在各類海量的各種多媒體信息中快速有效地準(zhǔn)確訪問(wèn)這些人們經(jīng)常感興趣的各種多媒體信息也對(duì)其顯示體現(xiàn)出了同樣的巨大重要性。

圖像抽象信息采集是傳統(tǒng)多媒體信息中最常見(jiàn)的一種,也因其具有傳統(tǒng)多媒體信息采集數(shù)據(jù)量大、抽象應(yīng)用程度低的基本特點(diǎn)。如何從各種海量的有用圖像處理信息中有效地收集獲取有用圖像信息,即使是圖像處理信息數(shù)據(jù)資源的使用管理和信息檢索也就顯得日益重要。隨著當(dāng)前人們對(duì)文字圖像文本信息的巨大檢索需求的不斷增長(zhǎng),產(chǎn)生了基于圖像文本的文字圖像信息檢索引擎技術(shù),比如著名的中文搜索結(jié)果引擎google和百度中對(duì)文字圖像的文本檢索。這種基于人類文本的人工檢索標(biāo)注技術(shù)所廣泛利用的人工文本標(biāo)注檢索方法雖然存在一些局限性,經(jīng)常進(jìn)行檢索時(shí)會(huì)出來(lái)大量的一些用戶不感興趣的文本圖像,但在沒(méi)有找到更好文本解決辦法的實(shí)際情況下,用戶通常只能選擇繼續(xù)檢索使用。因此如何對(duì)一個(gè)圖像的特征內(nèi)容自動(dòng)、客觀、全面地對(duì)其進(jìn)行特征提取。真實(shí)有效的準(zhǔn)確表示數(shù)字圖像信息內(nèi)容,幫助用戶快速有效地檢索訪問(wèn)自己感興趣的信息圖像內(nèi)容，有著極大的科學(xué)研究領(lǐng)域需求和迫切的應(yīng)用需要,而基于圖像形狀特征的數(shù)字圖像信息檢索分析技術(shù)恰好真正能有效的幫助解決這個(gè)現(xiàn)實(shí)問(wèn)題。另外在實(shí)際的應(yīng)用中,圖像信息數(shù)據(jù)庫(kù)及其信息檢索的技術(shù)研究對(duì)醫(yī)學(xué)多媒體圖像數(shù)字圖書館、醫(yī)學(xué)臨床圖像應(yīng)用管理、衛(wèi)星圖像遙感網(wǎng)絡(luò)圖像和應(yīng)用計(jì)算機(jī)圖像輔助設(shè)計(jì)和開(kāi)發(fā)制造、地理位置信息采集系統(tǒng)、犯罪識(shí)別系統(tǒng)、商標(biāo)標(biāo)識(shí)版權(quán)的使用管理,生物的形態(tài)辨識(shí)以及分類等諸多方面可以提供有力的技術(shù)支持。

2.2、國(guó)內(nèi)外發(fā)展?fàn)顩r

近年來(lái),CBIR已經(jīng)逐漸發(fā)展早熟成為一個(gè)非常活躍的醫(yī)藥臨床醫(yī)學(xué)研究應(yīng)用領(lǐng)域,各類我國(guó)頂尖臨床科研機(jī)構(gòu)與臨床研究公司已陸續(xù)成功開(kāi)發(fā)推出了一些基于CBIR臨床應(yīng)用管理系統(tǒng)的臨床研究應(yīng)用產(chǎn)品,有的已經(jīng)成功廣泛應(yīng)用擴(kuò)大到醫(yī)藥臨床醫(yī)學(xué)、商標(biāo)、專利技術(shù)以及檢索等諸多研究領(lǐng)域。

IBM的系統(tǒng)QBIC是它是第一個(gè)具有商業(yè)性的基于CBIR的子系統(tǒng)。它們還提供了基于圖像顏色、紋理、形狀和其他手繪圖像草圖的多種圖像類型索引使用方法。columbia大學(xué)的圖庫(kù)Visual SEEK圖庫(kù)提供了基于自然色彩和立體紋理的多種索引分析方法。PhotoBook 是美國(guó)麻省理工學(xué)院和多媒體科學(xué)實(shí)驗(yàn)室自主開(kāi)發(fā)的一套用于檢索、瀏覽人臉圖像的交互式檢索工具,它其中包含三個(gè)圖像子系統(tǒng)分別用于提取人臉形狀、紋理和各種人臉面部特征,用戶甚至可以分別定制做基于上述一種人臉特征的圖像檢索。MARS(multimedia analysis and retrieval system)這個(gè)系統(tǒng)由美國(guó)UIUC 大學(xué)負(fù)責(zé)開(kāi)發(fā),其不同之處主要在于用戶學(xué)到了很多專業(yè)領(lǐng)域的基礎(chǔ)知識(shí):例如計(jì)算機(jī)圖像視覺(jué)、數(shù)據(jù)庫(kù)資源管理和云系統(tǒng)和網(wǎng)絡(luò)信息資源檢索。新加坡國(guó)立大學(xué)公司開(kāi)發(fā)的一個(gè)基于復(fù)雜內(nèi)容的模糊圖像信息檢索系統(tǒng),其顯著性的技術(shù)創(chuàng)新特色主要包括:多種特征提取的新方法、多種基于復(fù)雜內(nèi)容圖像檢索的新方法、使用自定義組織式的神經(jīng)網(wǎng)絡(luò)對(duì)復(fù)雜內(nèi)容特征進(jìn)行度量、建立基于各種內(nèi)容圖像索引的新應(yīng)用方法以及對(duì)各種多媒體信息格式進(jìn)行模糊圖像檢索的新應(yīng)用技術(shù)。

清華大學(xué)的數(shù)字ImgRetr檢索結(jié)合了多種組織檢索方法,就這樣能為您提供基于形狀主色、紋理、直方結(jié)構(gòu)圖、顏色元素分布、框架等多種組織方式的形狀檢索。

2.3課題研究的主要內(nèi)容

本文主要依托基于物體形狀的網(wǎng)絡(luò)圖像信息檢索分析技術(shù),重點(diǎn)深入研究基于物體形狀動(dòng)態(tài)特征的網(wǎng)絡(luò)圖像信息檢索。形狀紋理特征不同于物體顏色、紋理等的特征,形狀紋理特征的正確表達(dá)必須以對(duì)物體圖像中每個(gè)物體或圖像區(qū)域的正確劃分來(lái)作為理論基礎(chǔ)。在二維矩形圖像中的空間中,形狀通常被我們認(rèn)為為它是由于一條完全封閉的并由輪廓映射曲線所形成包圍的特征區(qū)域。通常這種情況下.二維形狀中的特征區(qū)域有兩類可以表示它的方法,一類可以是一個(gè)區(qū)域形狀特征,利用的可以是整個(gè)二維形狀特征區(qū)域;另一種分類可以是一條輪廓曲線特征,利用的則可以是二維圖像的整個(gè)外邊和內(nèi)界。本文主要重點(diǎn)研究的領(lǐng)域就是外界與邊界的邊緣索引測(cè)量方法邊緣測(cè)量檢測(cè),邊緣測(cè)量檢測(cè)的常用方法主要有很多,如:roberts矩形交叉曲線微分代數(shù)算子、sobelt微分代數(shù)算子、priwitt交叉微分代數(shù)算子和Laplacian微分代數(shù)算子以及canny微分算子。而其中屬Canny算子最好。

本文主要深入研究的字符是傅里葉描述符。其主要理論思想觀點(diǎn)是用關(guān)于物體內(nèi)部邊界的傅立葉變換公式作為其物體形狀學(xué)的描述。

2.4、相關(guān)內(nèi)容介紹

2.4.1形狀分析

2.4.1.1、形狀特征

常用的長(zhǎng)軸形狀運(yùn)動(dòng)特征參數(shù)有長(zhǎng)軸周長(zhǎng)、形狀特征參數(shù)、偏心率、長(zhǎng)軸運(yùn)動(dòng)方向與彎曲運(yùn)動(dòng)能量等矩陣的描述、綜合光密度以及三維輪廓的應(yīng)力矩也同樣可以用于表示和用來(lái)描述三維圖像。

2.4.1.2特征選擇

通常一般來(lái)說(shuō),形狀的形態(tài)表示特征圖型表示法具有兩種常用圖形表示法的表現(xiàn)方法,一種表示方式主要是用來(lái)表示具有輪廓性的形狀形態(tài)特征,另一種表示方法主要是用來(lái)表示具有區(qū)域性的形狀形態(tài)特征的。前者一般來(lái)說(shuō)只用于看到整個(gè)部件物體的內(nèi)部外觀和形狀邊界,而后者則直接把它關(guān)系著其應(yīng)用到整個(gè)部件物體外觀形狀上的各個(gè)區(qū)域。

2.4.2、一種基于形狀的圖像檢索算法

2.4.2.1、算法分析

基于這種形狀的圖像檢索更多地只是用于了解當(dāng)前的用戶能夠粗略地掃描畫出一個(gè)圖形輪廓之后進(jìn)行圖形檢索的實(shí)際情況。這種圖形輪廓繪圖可以認(rèn)為是通過(guò)用戶憑借自己腦子在空中的第一印象徒手自動(dòng)畫圖繪出來(lái)的,也甚至可以認(rèn)為是通過(guò)操作系統(tǒng)軟件提供的基本圖形繪圖處理工具“拼湊”的。這兩種檢索情況都不具有一個(gè)基本特點(diǎn),即它所提供的檢索形狀只是對(duì)所欲檢索圖象形狀的粗略抽象描述,它從它的大小、方向或者其整體形狀結(jié)構(gòu)上都很有可能與真正根據(jù)要求調(diào)查的檢索圖形形狀有較大小的出入。因此,基于面的形狀進(jìn)行檢索的主要難點(diǎn)仍然在于需要尋找一種能夠準(zhǔn)確檢索與面的大小、方向及整個(gè)扭曲面的伸縮程度無(wú)關(guān)的檢索方法。

不變矩和產(chǎn)品輪廓的應(yīng)力不變矩的方法產(chǎn)品具有良好的軸向平移、旋轉(zhuǎn)、尺度上的縮小和放不變性及高度抗干擾性。用一個(gè)圖像的形狀不變矩和圖像輪廓的應(yīng)力矩陣來(lái)作為矩對(duì)圖像的兩種形狀相似特征進(jìn)行索引,使用適當(dāng)?shù)男螤钕嗨菩灾g距離進(jìn)行定義,計(jì)算并得出兩幅畫中圖像的形狀相似性之間距離,當(dāng)這個(gè)距離的值足夠小時(shí),就可以認(rèn)為兩幅畫的圖像形狀是相似的。傅里葉這種算法不僅對(duì)圖像噪音控制具有很好的魯棒性,而且對(duì)幾何變換速度具有不變性,更加十分適合工圖像形狀分析檢索的實(shí)際需要。因此，提出了應(yīng)力不變矩和矩形輪廓的應(yīng)力不變矩的算法和傅里葉公式描述中的符號(hào)相結(jié)合的計(jì)算方法。

三、圖像檢索技術(shù)的發(fā)展過(guò)程

目前圖像檢索的技術(shù)最早開(kāi)始于上個(gè)世紀(jì)70年代,當(dāng)時(shí)主要研究的是基于文本的檢索,即使采用關(guān)鍵詞和描述性的文本來(lái)對(duì)其進(jìn)行檢索,要求使用者對(duì)文本中各種特征的描述都必須具備一定的精度準(zhǔn)確性和規(guī)范性。但是隨著各種大規(guī)模的數(shù)字化圖像倉(cāng)庫(kù)的誕生,基于文本檢索的技術(shù)暴露了自身的優(yōu)勢(shì)。在我國(guó)逐步發(fā)展到90年代,基于圖像內(nèi)容的信息化圖像檢索技術(shù)應(yīng)運(yùn)而生,其設(shè)計(jì)思路主要是充分利用信息化圖像自身的各種視覺(jué)特點(diǎn),例如:將圖像中的顏色、紋理結(jié)構(gòu)、形狀、空間之間的關(guān)系等信息作為內(nèi)容來(lái)進(jìn)行匹配、查找。它通過(guò)充分地利用了己經(jīng)擁有的算法,使得所有的特征提取和匹配都完全能夠由機(jī)器自動(dòng)地完成,檢索的過(guò)程也沒(méi)必要太多的人為干涉和解釋,這就克服了傳統(tǒng)的手工標(biāo)簽注釋方式的低效率和二義性。

四、基于形狀特征的圖像檢索

因?yàn)樵S多的圖像檢索系統(tǒng)把注意力集中到了基于色彩或者是紋理學(xué)的方式上。但對(duì)于某些圖像形狀來(lái)說(shuō),紋理和顏色的信息不夠豐富,如一些商標(biāo)圖像等,這時(shí)基于紋理的檢索方法便無(wú)法完全滿足所有的檢索要求,而必須從整個(gè)圖像形狀入手。形狀特征信息是圖像的中心特征之一,圖像中的形態(tài)和信息不會(huì)隨著圖像中物體顏色的改變而發(fā)生任何變化,它是一種穩(wěn)定的特征。用各種形狀的特征來(lái)區(qū)別物體很加直觀,它們是現(xiàn)代社會(huì)中人們識(shí)別不同形態(tài)圖像的主要技術(shù)特征之一。因此,通過(guò)利用各種形狀特征來(lái)檢索圖像,可以大大提高檢索的精度和效果?；谀繕?biāo)的形狀特征的圖像檢索主要目的是通過(guò)檢測(cè)得到目標(biāo)輪廓線或分割得到目標(biāo)輪廓,并針對(duì)其所在位置進(jìn)行形狀特征的提取或直接針對(duì)圖像搜集尋找合適的向量特征。形態(tài)描述要求我們?cè)诒M量區(qū)別各個(gè)目標(biāo)之間的基礎(chǔ)上,對(duì)于目標(biāo)平移、轉(zhuǎn)動(dòng)及尺度的變化并不敏感。目前,雖然我們已經(jīng)研究提出了許多關(guān)于形狀的分析技術(shù),但是想要將它們有效運(yùn)用到圖像檢索中仍存在的問(wèn)題還有一些困難和疑惑亟待解決,如算法的工作效率和復(fù)雜程度,形狀特征的提取與描述等。

五、基于形狀特征的圖像檢索具體實(shí)行

5.1對(duì)象形狀的描述

圖象經(jīng)過(guò)邊緣的提取、分割后可以獲得諸個(gè)被分割的區(qū)域.對(duì)諸個(gè)被分割的區(qū)域所提取的形狀特征,是基于內(nèi)容的圖象檢索系統(tǒng)的重要組成部分,所提取的形狀特征對(duì)于圖象的旋轉(zhuǎn)、圖像的平移和對(duì)圖象縮放都是不敏感的.本文主要研究涉及以下幾種形狀的特征:

(1)基于傅立葉系數(shù)的形態(tài)和特點(diǎn).圓角度,細(xì)長(zhǎng)程,散射性.(2)基于幾何形狀的特征.區(qū)域的面積,區(qū)域的周長(zhǎng),體態(tài)比.(3)矩描述.共有七個(gè)矩常量.(4)以相似多邊形為基礎(chǔ)的結(jié)構(gòu)和特點(diǎn).(5)形狀直方圖.5.2、系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

系統(tǒng)主要可以分為三個(gè)組成部分:(1)圖象數(shù)據(jù)庫(kù)建立模塊.該建立模塊首先對(duì)用戶輸入的各種圖象信息進(jìn)行了預(yù)處理,其中包括各種圖象信號(hào)和噪聲的清除,圖象尖銳化,邊緣檢測(cè)(對(duì)象物的分離),邊緣細(xì)化,鏈碼追溯,對(duì)于邊界信息進(jìn)行了多邊形逼近,然后將其提取到對(duì)象的各種形狀信息,最后把用戶需要提取的信息特征值直接存入到圖象數(shù)據(jù)庫(kù)中;(2)圖像數(shù)據(jù)庫(kù)維護(hù)系統(tǒng)模塊.本次維護(hù)系統(tǒng)主要負(fù)責(zé)對(duì)圖像數(shù)據(jù)庫(kù)信息進(jìn)行維護(hù),主要內(nèi)容包括圖像瀏覽記錄的修改及歷史紀(jì)念信息的刪除;在對(duì)圖像記錄進(jìn)行修改時(shí),對(duì)那些由于計(jì)算機(jī)自動(dòng)提取得到的特征值我們都是不可以進(jìn)行修改的,而且我們只能通過(guò)修改這些由人為確定定義的字段,如:一個(gè)有關(guān)于圖象的文字說(shuō)明部分.(3)圖像檢索查詢模塊.該功能首先根據(jù)需要對(duì)被檢索的圖像進(jìn)行提取的形狀和特征,然后再根據(jù)需要選擇按哪些特征值對(duì)象來(lái)進(jìn)行檢索,設(shè)置好圖像的檢索所達(dá)到要求的類型和相似程度,最后與將圖像信息與數(shù)據(jù)庫(kù)中的其他圖像進(jìn)行匹配,輸出查詢結(jié)果.圖象的匹配查詢是整個(gè)圖像信息數(shù)據(jù)庫(kù)的主要功能和組成部分,匹配算法的好壞及其優(yōu)劣直接影響到匹配查詢的速度和信息庫(kù)查詢的質(zhì)量,其根本思路就是通過(guò)判斷一個(gè)經(jīng)典的已知圖象與一個(gè)圖像數(shù)據(jù)庫(kù)中的一個(gè)圖象之間的距離,如其距離有點(diǎn)足夠小,就說(shuō)明我們可以確定兩個(gè)已知圖象之間是相似的,其結(jié)果一般應(yīng)該是多個(gè)已知圖象,這些所有的圖象都與經(jīng)典查詢的圖像在一個(gè)給我們認(rèn)為有點(diǎn)相似.我們其實(shí)可以通過(guò)運(yùn)用各種相似性程量測(cè)度查詢函數(shù)過(guò)程方法工具來(lái)進(jìn)行分析和控制計(jì)算一個(gè)查詢特征圖象與一個(gè)特征圖像數(shù)據(jù)庫(kù)中每一個(gè)特征圖象的相似度和程度,相似性程度測(cè)量中的查詢函數(shù)過(guò)程主要來(lái)說(shuō)是研究建立在對(duì)數(shù)據(jù)特征分析和模式識(shí)別相關(guān)技術(shù)研究基礎(chǔ)上的,涉及所遇到的主要技術(shù)問(wèn)題之一就是對(duì)于一個(gè)數(shù)據(jù)輸入模式如何進(jìn)行特征描述和模式判別,查詢的基本過(guò)程就是根據(jù)一個(gè)新的給定數(shù)據(jù)模式對(duì)一個(gè)數(shù)據(jù)輸入中的模式特征進(jìn)行數(shù)據(jù)匹配.這個(gè)相似度一般來(lái)說(shuō)是通過(guò)0~1之間的某個(gè)個(gè)不同參數(shù)特征來(lái)進(jìn)行表現(xiàn)計(jì)算出來(lái)的,總的相似度也由各種不同特征所測(cè)量的相似度通過(guò)函數(shù)加權(quán)運(yùn)算求和得.傳統(tǒng)數(shù)據(jù)庫(kù)的準(zhǔn)確匹配和查詢技術(shù)是很簡(jiǎn)單地了解的,但對(duì)于圖象型的數(shù)據(jù)庫(kù)來(lái)說(shuō),查詢的質(zhì)量和查詢的快慢還是相互矛盾的,要求查詢率和準(zhǔn)確性好,就需要盡可能多地增加一些描述圖象的特征矢量的維數(shù),隨之而來(lái)就需要盡可能多地增加計(jì)算量,所以,要在不降低特征矢量的維數(shù)條件下,才能夠大幅度地提高查詢率,就必須通過(guò)調(diào)整和完善查詢的策略.主要采用以下兩種操作方法:

（1）.聚類的基本原理:分類即把一個(gè)標(biāo)準(zhǔn)圖象按類劃分開(kāi)來(lái)成以下幾類,每一類都被用戶定義成作為一個(gè)分類標(biāo)準(zhǔn)圖,則在用戶查詢一個(gè)標(biāo)準(zhǔn)圖象時(shí),首先根據(jù)要求計(jì)算出與各種分類標(biāo)準(zhǔn)圖之間的物理距離,確定它們之間是否隸屬于何一類,然后再與該一類的標(biāo)準(zhǔn)圖象之間進(jìn)行具有相似性的分類匹配.（2）過(guò)濾的原理:即通過(guò)降低維數(shù),在進(jìn)行圖象匹配之前,首先將一些形狀和特征相差甚遠(yuǎn)的圖像從一個(gè)被稱為圖象匹配團(tuán)隊(duì)中全部清除掉,然后再將查詢到的圖象和匹配團(tuán)隊(duì)中剩下的其他圖象進(jìn)行對(duì)比.5.3、算法步驟

(1)通過(guò)計(jì)算被檢索圖像的形狀和特征,并從數(shù)據(jù)庫(kù)中提取圖像形狀和特征進(jìn)行索引;

(2)對(duì)特征向量進(jìn)行歸一化;

(3)使用歐式距離法來(lái)計(jì)算歸一化后的圖像數(shù)據(jù)庫(kù)中各個(gè)圖像與顯示者的圖像之間的相似性和距離;

(4)按序輸出檢索結(jié)果。

5.4.邊緣檢測(cè)

其中邊緣化的特點(diǎn)通常是直接影響物體圖像最為主要的一個(gè)基本特點(diǎn)。邊緣則主要是在泛指周圍各個(gè)像素的顏色灰度并沒(méi)具有較大階躍性質(zhì)的變化或者在屋頂上的顏色沒(méi)有發(fā)生較大改變的那一個(gè)周圍像素。Poggio在文中這樣解釋說(shuō):“或許對(duì)應(yīng)著圖像中物體的邊界或許并沒(méi)有對(duì)應(yīng)著圖像中物體的邊界,但是邊緣具有十分令人滿意的性質(zhì)它能大大地減少所要處理的信息但是又保留了圖像中物體的形狀信息”。

邊緣圖像檢查理論是一種實(shí)現(xiàn)圖像識(shí)別的重要理論知識(shí)基礎(chǔ)和技術(shù)前提,直接意義地說(shuō)它決定了圖像識(shí)別檢查結(jié)果的客觀準(zhǔn)確性。由于人體邊緣圖像檢測(cè)尚不成熟,直接地嚴(yán)重影響了對(duì)圖像識(shí)別的實(shí)際研究應(yīng)用,一直以來(lái)都認(rèn)為是圖像識(shí)別相關(guān)技術(shù)應(yīng)用領(lǐng)域的重要研究發(fā)展熱點(diǎn)。經(jīng)過(guò)多年的研究探索和應(yīng)用實(shí)踐,邊緣式質(zhì)量檢測(cè)系統(tǒng)技術(shù)已經(jīng)逐漸發(fā)展?jié)B透至各個(gè)應(yīng)用領(lǐng)域。在應(yīng)用生物醫(yī)學(xué)上,邊緣提取檢測(cè)主要作為適用于人體腎臟血小球的邊緣提取,在應(yīng)用生物醫(yī)學(xué)工業(yè)和工程科學(xué)以及其他工程材料領(lǐng)域的邊緣檢測(cè),如聚酯纖維或者其他塑料制品。而且在加工噴涂、焊接和機(jī)械裝配時(shí)也被充分地吸收利用。在中國(guó)傳統(tǒng)的民族文化工藝美術(shù)上,用于對(duì)傳統(tǒng)紡織品和手工藝品的定制設(shè)計(jì),服飾的定制設(shè)計(jì)和手工制作,發(fā)型的定制設(shè)計(jì),文物收藏材料以及照片的編輯復(fù)制和收集整理,運(yùn)動(dòng)員的身體動(dòng)作狀態(tài)分析和體能評(píng)級(jí)等等。總之,邊緣厚度檢測(cè)已被廣泛應(yīng)用于各個(gè)領(lǐng)域。這仍然是我們必須不容忽視的一個(gè)研究發(fā)展熱點(diǎn)。

5.5、Canny邊緣檢測(cè)

5.5.1 Canny指標(biāo)

基于微分算子的邊緣提取方法存在的一個(gè)比較麻煩的問(wèn)題是如何讓我們選擇適當(dāng)?shù)拈撝?可以通過(guò)這種方法使邊緣從每一個(gè)細(xì)節(jié)中被提取出來(lái)。閾值的選擇方式不同,所需要提取得到的邊界信息也不相同。在兩個(gè)不同的閾值下,采用相同的微分算子均可以從圖像邊緣提取得出一個(gè)點(diǎn),但兩者之間有比較大的差異。這樣,在邊緣提取中也就存在了對(duì)提取良好與否的評(píng)估。

針對(duì)這一重要問(wèn)題,根據(jù)邊緣檢測(cè)的工作有效性和其定位的安全可靠性, Canny 通過(guò)研究最優(yōu)的邊緣檢測(cè)儀器所必須要求的特點(diǎn),給出了衡量邊緣檢測(cè)系統(tǒng)性能好壞的三個(gè)主要指標(biāo):

(1)良好的邊緣信噪聲對(duì)比,即將不是邊緣點(diǎn)錯(cuò)誤判定為其他邊緣點(diǎn)的錯(cuò)誤概率相對(duì)較高,將其他邊緣點(diǎn)錯(cuò)誤判定為其他邊緣點(diǎn)的錯(cuò)誤概率相對(duì)較低;

(2)良好的定位特性,即檢測(cè)出來(lái)的邊緣點(diǎn)應(yīng)該要盡量安裝在實(shí)際邊緣的點(diǎn)為中心;

(3)對(duì)于單個(gè)邊緣只能產(chǎn)生唯一的響應(yīng),即單個(gè)邊緣能夠同時(shí)產(chǎn)生許多個(gè)響應(yīng),其概率相對(duì)較低,并且在虛假的響應(yīng)中對(duì)邊界的反饋效果相應(yīng)得到最佳抑制.用這樣一個(gè)詞來(lái)說(shuō),就是我們希望能夠有效地提高人們對(duì)于景物邊緣的靈敏度和噪音的同時(shí),這種能夠有效地抑制其他人們產(chǎn)生噪音的方式才是良好的邊緣提取技術(shù)。值得我們十分慶幸的一點(diǎn)其實(shí)是,且個(gè)二階線性映射算子仍然能夠在有效抵抗圖形噪聲和對(duì)圖形邊緣的線性檢測(cè)之間獲得最佳結(jié)果折中,這個(gè)二階線性映射算子本身其實(shí)就是高斯函數(shù)的一個(gè)二階取值引用導(dǎo)出函數(shù)。高斯函數(shù)和用于原圖的卷積已經(jīng)初步達(dá)到了一種可以抵抗局部噪聲的主要效果,而用于求導(dǎo)的函數(shù),則被普遍認(rèn)為已經(jīng)是我們檢測(cè)一個(gè)景物局部邊緣的一種重要手段。

設(shè)二維高斯函數(shù)為

其中,σ為高斯函數(shù)的平滑度和分布式的參數(shù),可以被廣泛地基于用來(lái)衡量控制網(wǎng)絡(luò)對(duì)象或者網(wǎng)絡(luò)圖像平滑的重要程度。

其中，σ是高斯函數(shù)的分布參數(shù)，可用以控制對(duì)圖像的平滑程度。

最優(yōu)階躍邊緣檢測(cè)算子是以卷積▽G*為基礎(chǔ)的，邊緣強(qiáng)度為

而邊緣方向?yàn)?/span>

由高斯函數(shù)的定義我們得以可知,該高斯函數(shù)都可以是無(wú)限地從頭拖尾的,在實(shí)踐中,一般的各種情況下都方法是將原來(lái)的有限模板尺寸截?cái)酁閚,至于就達(dá)到了有限的模板尺寸。這個(gè)新的實(shí)驗(yàn)結(jié)果證明,當(dāng)時(shí),能夠直接取得較好的邊緣化學(xué)檢查實(shí)驗(yàn)結(jié)果。

5.5.2 Canny算子的實(shí)現(xiàn)

下面是Canny算子的具體實(shí)現(xiàn)。

利用高斯函數(shù)的雙向可分性,將映射▽g的兩個(gè)一維濾波卷積上的模板可以分解成兩個(gè)一維的濾波行列式式濾波器:

1

2

3

4

5

6

K為常數(shù)將式12分別與圖像

則反應(yīng)出一個(gè)在圖像上點(diǎn)處的邊緣強(qiáng)度,是一個(gè)在圖像點(diǎn)處的法向力矢量(下一個(gè)交于其邊緣線方向)。

根據(jù)關(guān)于canny的卷積定義,中心邊緣點(diǎn)梯度作為一個(gè)卷積算子和它的圖像(x,y)的卷積梯度是在中心邊緣點(diǎn)和梯度相同直線方向的同一區(qū)域內(nèi)兩個(gè)算子梯度中的最高值。這樣,就可以能夠通過(guò)在各個(gè)梯度點(diǎn)的最大梯度值和方位上進(jìn)行判斷并得出每個(gè)該梯度點(diǎn)的最大強(qiáng)度方位是否為其應(yīng)用領(lǐng)域最大強(qiáng)度值,從而快速確定各個(gè)梯度點(diǎn)的邊緣點(diǎn)。例如,當(dāng)一個(gè)矩形像素圖象滿足以下三個(gè)基本條件時(shí),則被我們視作該點(diǎn)是一個(gè)像素圖像的邊界點(diǎn)。

(1)當(dāng)像素該中一點(diǎn)的平均邊緣運(yùn)動(dòng)強(qiáng)度方向超過(guò)了沿著像素該中一點(diǎn)的邊緣梯度方向運(yùn)動(dòng)的同方向兩個(gè)像素相鄰點(diǎn)的像素中一點(diǎn)的平均邊緣運(yùn)動(dòng)強(qiáng)度時(shí);

(2)與該點(diǎn)梯度方向上相鄰兩點(diǎn)的方向差小于45度;

(3)觀測(cè)領(lǐng)域核心中的最大邊緣變化強(qiáng)度最大邊緣閾度數(shù)值以所在該觀測(cè)點(diǎn)位置為領(lǐng)域中心。

此外,如果(1)和(2)同時(shí)被邊緣的頂點(diǎn)像素滿足,那么候選選擇梯度最小值相同方向上的兩個(gè)非相鄰頂點(diǎn)像素就從候選選擇邊緣的頂點(diǎn)中被直接取消,條件(3)閾值相當(dāng)于由候選邊緣區(qū)域選擇梯度最大的閾值所在點(diǎn)組成的一個(gè)閾值,即圖像與候選邊緣的頂點(diǎn)之間的平均距離可以進(jìn)行閾值匹配,這一消除過(guò)程就等于消除了許多虛假的邊緣點(diǎn)。

圖像邊緣檢測(cè)的基本步驟:

(1)對(duì)于濾波,邊緣的檢測(cè)主要是基于引導(dǎo)值進(jìn)行計(jì)算,但是容易受到噪聲影響。然而,該濾波器在減少噪聲時(shí)還會(huì)造成邊緣強(qiáng)度的損耗。

(2)進(jìn)行了增強(qiáng),加強(qiáng)算法把鄰域的點(diǎn)的度有明顯改變的地方突出表現(xiàn)。一般是靠計(jì)算梯度的幅值來(lái)實(shí)現(xiàn)。

(3)進(jìn)行檢測(cè),但是在有些影像中梯度幅值較大的點(diǎn)并非邊緣端。最簡(jiǎn)單的對(duì)邊緣性檢測(cè)就是梯度幅值閾值的判斷。

(4)定位,精確確定邊緣的位置。

綜上所述,Canny算子的具體算法步驟如下:

(1)使用高斯濾波器對(duì)圖像中的信號(hào)進(jìn)行濾波,去除圖像中的干擾和噪聲;

(2)分析利用高斯算子的一階方向偏移濾波函數(shù)采用微分的方法對(duì)物體圖像中各點(diǎn)方向進(jìn)行濾波,得到每一點(diǎn)的方向梯度和角強(qiáng)度和物體運(yùn)動(dòng)時(shí)的方向;

(3)針對(duì)梯度方向運(yùn)動(dòng)進(jìn)行“非極大抑制”時(shí)對(duì)其梯度的反向運(yùn)動(dòng)及其方向如圖可以正確定義為其如下如圖所示

標(biāo)識(shí)分別為1,2,3,4的四個(gè)區(qū)域?qū)⑵鋵儆谒膫€(gè)局部分區(qū)之一,各個(gè)局部分區(qū)用不同的線將相鄰四個(gè)像素分別排列來(lái)對(duì)其局部進(jìn)行高度比較,以此來(lái)決定其每個(gè)局部的極大像素值。例如,如果我們?cè)谙噜徶行南袼貓D像獲得x的梯度方向上認(rèn)為屬于第4區(qū),則把獲得x的極大梯度方向值與其左上和右下兩個(gè)方向相鄰中心像素的極大梯度的數(shù)值大小進(jìn)行向量比較,看獲得x的極大梯度的數(shù)值大小是否可視為極大梯度值。如果不是,就把每個(gè)矩形像素y到x的顏色灰度系數(shù)設(shè)置為0。這一抑制過(guò)程被人們稱之為“非極大抑制”。

(4)對(duì)一個(gè)梯度進(jìn)行兩次閾值,即取一個(gè)閾值,兩者之間的關(guān)系公式為。我們將梯度值小于的每個(gè)像素灰度設(shè)置為0。然后將梯度值小于的每個(gè)像素灰度平均值設(shè)定為0。去除了大部分的噪聲,但同時(shí)也導(dǎo)致?lián)p失了有用的邊緣和界面結(jié)構(gòu)信息。

5.6基于輪廓的描述方法

基于局部輪廓圖對(duì)形狀進(jìn)行描述的設(shè)計(jì)方法又大致可以細(xì)分為局部連續(xù)型(注意即局部全局式)和局部離散型(即局部結(jié)構(gòu)式)兩種。連續(xù)型全局輪廓圖圖描述的方法并沒(méi)有對(duì)稱為全局圖的輪廓圖進(jìn)行任何分段式的處理,往往目的是從整個(gè)稱為全局圖的輪廓圖中抽取并給出一個(gè)特征向量。這種屬于離散式的分析方法通常首先把它的輪廓特點(diǎn)分解成許多不同片段,然后用傳統(tǒng)計(jì)算機(jī)輪廓提取法找出其片段相應(yīng)的輪廓特點(diǎn)。簡(jiǎn)單的物體形狀類型描述表示符主要類型包括鏈碼、傅立葉描述符、曲率尺度空間形狀描述表示符和小波描述表示符四種基于物體輪廓的形狀描述表示方式。

5.7傅立葉形狀描述符

傅立葉形狀輪廓描述符即它是一種被廣泛應(yīng)用的二維模型形狀輪廓描述符,其最基本的設(shè)計(jì)思想就是用一個(gè)直接位于模型物體內(nèi)部輪廓上沒(méi)有邊界的傅立葉變換函數(shù)來(lái)對(duì)其內(nèi)部形狀輪廓進(jìn)行精確描述,假設(shè)一個(gè)二維模型物體的內(nèi)部輪廓形狀是由一系列每個(gè)坐標(biāo)值函數(shù)為的物體像素所組合構(gòu)造的并組成,其中,n函數(shù)為在物體輪廓上每個(gè)坐標(biāo)像素的實(shí)際參考映射次數(shù)。從這些邊界點(diǎn)的整體坐標(biāo)中我們常?？梢杂纱送茖?dǎo)出來(lái)得出四類不同形狀的坐標(biāo)表達(dá),分別為正弦曲率坐標(biāo)函數(shù)、質(zhì)心坐標(biāo)距離、復(fù)弦長(zhǎng)坐標(biāo)矢量函數(shù)及其余弦長(zhǎng)坐標(biāo)函數(shù)。輪廓弧曲線上一個(gè)特征點(diǎn)的移動(dòng)曲率被精確定義是因?yàn)樵擖c(diǎn)在輪廓線上切向的移動(dòng)角度與曲率相當(dāng)于輪廓弧長(zhǎng)之間的角度變動(dòng)率。曲率密度函數(shù)我們通?？梢院?jiǎn)單地將其表示形式如下:

其中是輪廓線的切向角度,定義為:

質(zhì)心點(diǎn)的距離函數(shù)可以直接定義成其為從一個(gè)物體的邊界點(diǎn)到另一個(gè)給定物體的邊界中心之間距離,如下所示:

復(fù)坐標(biāo)函數(shù)是用復(fù)數(shù)表示的像素坐標(biāo):

這種復(fù)雜的坐標(biāo)向量函數(shù)的傅立葉變換形式可以用來(lái)產(chǎn)生一系列關(guān)于復(fù)數(shù)的坐標(biāo)系數(shù)。這些頻率系數(shù)從微觀頻率上直接反映表示了各個(gè)類型物體的宏觀形狀,其中較低和高頻度的物體分量值就代表了各個(gè)類型物體微觀形狀的具體性和宏觀細(xì)節(jié)屬性,高頻度的物體分量值則代表了各個(gè)類型物體宏觀形狀的具體微觀細(xì)節(jié)屬性特點(diǎn)。形狀圖的描述符參數(shù)可以通過(guò)這些圖形轉(zhuǎn)換器的參數(shù)計(jì)算得出。為了使其能夠更好保持與參數(shù)旋轉(zhuǎn)的速度無(wú)關(guān)性,我們簡(jiǎn)單地僅僅保留了每個(gè)參數(shù)的旋轉(zhuǎn)尺寸位置信息,而且同時(shí)省略了參數(shù)相位位置信息?？s放參數(shù)無(wú)關(guān)性通常由于在保證把縮放參數(shù)值的大小同時(shí)減少添加到c和dc中的分量(或第一個(gè)不為零的縮放參數(shù))之后縮放才能得到確認(rèn)。請(qǐng)?zhí)貏e注意圖形轉(zhuǎn)換中的無(wú)關(guān)性就是基于物體輪廓上的形狀屬性來(lái)轉(zhuǎn)換表示固有的轉(zhuǎn)換屬性。對(duì)于具有曲率向量函數(shù)和質(zhì)心之間距離的曲率函數(shù),我們只不過(guò)需要分別考慮正交角頻率的兩個(gè)坐標(biāo)時(shí)間軸,因?yàn)檫@時(shí)兩個(gè)函數(shù)的傅立葉變換都必須是對(duì)稱的,即有?；邳c(diǎn)的曲率三角函數(shù)的一種形狀線性描述符號(hào)也可以使其表示形式為:

其中整數(shù)代表傅立葉變換每個(gè)參數(shù)的第一至i個(gè)整數(shù)分量。類似的,由質(zhì)心粒子間距所做的推測(cè)計(jì)算得到的粒子形態(tài)可以描述

符為:

對(duì)于一個(gè)復(fù)雜的坐標(biāo)密度函數(shù),正值的頻率密度分量和負(fù)值的頻率密度分量被同時(shí)廣泛使用。由于函數(shù)dc的地理參數(shù)定義是否與某些形態(tài)條件所在處或地點(diǎn)的地理位置密切相關(guān)而因此得以常被忽略。因此,第一個(gè)不是零的微波頻率參數(shù)分量被廣泛應(yīng)用于后來(lái)用于標(biāo)準(zhǔn)化其它的微波變換頻率參數(shù)。復(fù)函數(shù)坐標(biāo)系是函數(shù)所有的推導(dǎo)形式得到的坐標(biāo)形態(tài)為其描述符式為其定義方程為:

為了能夠保證在整個(gè)特征數(shù)據(jù)庫(kù)中所有位于物體的各種特征形狀和其他特征均可以具有相同的特征直徑和特征長(zhǎng)度,在第一開(kāi)始進(jìn)行實(shí)施傅立葉變換前后你需要把所有位于物體邊界點(diǎn)的個(gè)別特征數(shù)目可以統(tǒng)一添加到m。因此算法可以被直接替換為傅立葉變換法的方式使用來(lái)大大幅度改善這個(gè)算法的執(zhí)行效率。

5.8圖像的相似性度量

在基于特征信息的圖像內(nèi)容檢索圖像信息檢索中,特征的信息相似性和特征度量也被廣泛認(rèn)為已經(jīng)是一個(gè)亟待解決的重大檢索技術(shù)研究課題之一。只有在根據(jù)分析結(jié)果得到特點(diǎn)圖像的兩個(gè)特點(diǎn)后后再進(jìn)行對(duì)該兩個(gè)特點(diǎn)的圖像相似性距離進(jìn)行準(zhǔn)確度量,才能有效的根據(jù)圖像相似性和圖像距離情況做出準(zhǔn)確判斷,實(shí)現(xiàn)對(duì)該特點(diǎn)圖像的準(zhǔn)確檢索。為了更好地準(zhǔn)確達(dá)到不同特征數(shù)據(jù)檢索的提取目標(biāo),需要針對(duì)特征提取后得出的不同特征數(shù)據(jù)進(jìn)行相似度的分析計(jì)算。相似性系數(shù)是以一個(gè)特殊數(shù)值的表示方式被用來(lái)顯示表達(dá)兩個(gè)不同物體之間的事物相似性相關(guān)程度的一種數(shù)學(xué)度量式的結(jié)果。將一個(gè)人類圖像的各種特征檢索觀察點(diǎn)可看作等同是圖像位于一個(gè)坐標(biāo)標(biāo)準(zhǔn)空間的一個(gè)特征點(diǎn),兩個(gè)圖像特征觀察點(diǎn)的相似度和特征距離即相似度通常用它們之間的特征距離系數(shù)來(lái)精確表示,不同特征種類的圖像特征檢索數(shù)據(jù)所指的需要同時(shí)采用的相似度及其度量計(jì)算函數(shù)都可能是不一樣的,相似性和度度量函公式的正確選擇的恰當(dāng)與否往往會(huì)對(duì)特征檢索結(jié)果精確度與否產(chǎn)生很大的直接影響,合適點(diǎn)的距離才是度量計(jì)算函數(shù)的正確選擇,將來(lái)也會(huì)幫助使得人類圖像的各個(gè)特征向量比較更加容易契合了解的人類對(duì)于各種視覺(jué)圖像感知技術(shù)方面圖像內(nèi)容的特征仿真,有助于基于人類視覺(jué)圖像感知技術(shù)方面的人類圖像特征檢索分析技術(shù)的仿真性能和實(shí)際應(yīng)用。

假設(shè)我們?cè)谝粋€(gè)圖像的數(shù)據(jù)庫(kù)中,用兩個(gè)特征向量分別來(lái)描述和表示任意一個(gè)圖像的特征,其中 x 和 y ,分別為是任意兩個(gè)圖像的特征向量,它們之間的接近程度我們可以通過(guò)采用距離的度量或者是統(tǒng)計(jì)學(xué)的方法等等來(lái)對(duì)這兩個(gè)圖像的相似性做出判斷。常見(jiàn)的距離測(cè)度度量主要有歐幾里德、Manhattan等。下面就我重點(diǎn)介紹一下歐幾里德的距離。

歐幾里德的線性距離函數(shù)是一種在實(shí)際上已經(jīng)使用十分廣泛的線性距離函數(shù)變量。它的變量計(jì)算簡(jiǎn)單,并且同時(shí)也和國(guó)際參考動(dòng)力系統(tǒng)理論中的徑向旋轉(zhuǎn)不確定變量計(jì)算有密切相互聯(lián)系。它的英文含義:

例如當(dāng)我們發(fā)生了數(shù)據(jù)的丟失或者是當(dāng)所有的特征矢量都不具備相同的權(quán)重時(shí),那么就無(wú)法利用歐幾里德距離計(jì)算方法來(lái)對(duì)其進(jìn)行類似性的測(cè)度。為了避免這類情況,在實(shí)踐和研究的過(guò)程中,我們可以針對(duì)歐幾里德的距離進(jìn)行歸一化。歸一化歐幾里德距離的定義公式如下圖所示:

6、實(shí)驗(yàn)結(jié)果分析

圖像庫(kù)中包括簡(jiǎn)單幾何形狀,其中星形、心形、圓形、新月形圖像10幅。從分析我們不僅可以清楚地明顯看出,算法對(duì)于檢索圖像的視覺(jué)扭轉(zhuǎn)和圖像形變都真的是十分具有非常強(qiáng)的不變性,并對(duì)于檢索圖像的基本主觀形態(tài)和視覺(jué)特性也是非常具有魯棒性,在就算沒(méi)有一定的圖像形變和扭轉(zhuǎn)干擾等等條件的特殊情況下,仍然完全可以直接得出良好的視覺(jué)圖像判斷檢索實(shí)驗(yàn)結(jié)果;且由于算法檢索圖像結(jié)果所需要排列的持續(xù)時(shí)間和排列順序與檢索個(gè)體的視覺(jué)主觀性和視覺(jué)特征判斷檢索方式大致相同,檢索結(jié)果準(zhǔn)確率也比較高。

六、以形狀為特點(diǎn)的圖像檢索系統(tǒng)設(shè)計(jì)

6.1檢索基本思想

本文文件檢索的基本工作方法主要內(nèi)容是:在根據(jù)設(shè)計(jì)需要建立矩形圖像庫(kù)時(shí),對(duì)不同輸入的兩個(gè)矩形圖像子存入進(jìn)行綜合分析,分別選擇采用經(jīng)過(guò)改進(jìn)后的不同可變矩和二維極坐標(biāo)傅里葉描述子對(duì)兩個(gè)圖像的不同形狀和狀態(tài)特征向量進(jìn)行綜合描述;在將兩個(gè)圖像子的存入轉(zhuǎn)換到二維矩形圖像庫(kù)同時(shí),也將其中兩個(gè)相應(yīng)的不同可變矩和二維極坐標(biāo)傅里葉描述子的形狀特征向量分別存入二維矩形圖像庫(kù)的特征庫(kù).檢索時(shí),根據(jù)所有用戶需要提供的圖像查詢數(shù)據(jù)示例檢索圖像,采用通過(guò)線性函數(shù)加權(quán)方法求和的一種計(jì)算結(jié)果方式,計(jì)算其與二維矩形圖像庫(kù)中各不同類型矩形圖像的各種綜合相似度,把計(jì)算結(jié)果對(duì)子集中的一個(gè)大于一定相似度的圖像結(jié)果集進(jìn)行返回發(fā)送給所有用戶.6.2 Canny算子的程序設(shè)計(jì)

本文是用C++編程來(lái)實(shí)現(xiàn)圖像的處理,整體流程圖如圖所示

未打開(kāi)

N

Y

Canny算子程序流程圖如圖所示：

6.2.1圖像特征數(shù)據(jù)庫(kù)設(shè)計(jì)

基于圖像形狀和特征的檢索系統(tǒng)中的一個(gè)圖像特征數(shù)據(jù)庫(kù)是用來(lái)存放和分析圖像倉(cāng)庫(kù)中不同圖像之間的形狀和特點(diǎn)。在這里,將計(jì)算得到的一組圖像的形狀和特征(曲率、質(zhì)心距離、復(fù)坐標(biāo)和弦長(zhǎng))從 Access中存放到一個(gè)相應(yīng)的特征列表中,組成了一個(gè)特征數(shù)據(jù)庫(kù)。

對(duì)于圖像的檢索,本文特別設(shè)計(jì)了對(duì)圖像入庫(kù)、顯示、刪除和添加描述四個(gè)功能。首先,利用灰度共生矩陣提取的方法得到一個(gè)圖像的形狀特征,并將這些特征數(shù)據(jù)存儲(chǔ)在 access 數(shù)據(jù)庫(kù)中;然后,利用基于文本或者簡(jiǎn)單的縮略圖瀏覽等多種方式從 access 數(shù)據(jù)庫(kù)中尋找到一個(gè)示例的圖像,同時(shí),針對(duì)該一個(gè)示例圖像進(jìn)行基于其形狀和特征的內(nèi)容檢索和匹配,并根據(jù)需要給出檢索結(jié)果的圖像。

6.3實(shí)驗(yàn)結(jié)果

以下是原圖與處理后的圖片，其中圖3-4為原始圖片，圖3-5為Canny 算子處理后的圖片。

從上述處理過(guò)的數(shù)據(jù)和圖像中我們可以清楚地看出, canny 算子所處理的數(shù)據(jù)和圖像不但達(dá)到了準(zhǔn)確地提取邊緣信息的主要目的,提高了抵御干擾的能力外,還使得邊緣更為連續(xù)清晰。

七、基于圖像形狀學(xué)特點(diǎn)的檢索方法在系統(tǒng)中的實(shí)現(xiàn)

7.1系統(tǒng)框架

一般的圖像檢索子系統(tǒng)主要有兩個(gè)大部分共同組成:圖像產(chǎn)生子系統(tǒng)和數(shù)據(jù)庫(kù)檢索子系統(tǒng),如圖4-1所示。圖像產(chǎn)生的子系統(tǒng)主要是對(duì)于圖像輸入前進(jìn)行的預(yù)處理、圖像中內(nèi)容的特性提取以及把這些特性和部件描述的信息納入到數(shù)據(jù)庫(kù)中。圖像檢索子系統(tǒng)主要是完成對(duì)圖像的檢索,其中包含了瀏覽和查詢、圖像特點(diǎn)的相似性匹配以及圖形使用者接口等幾個(gè)部分。

在本文的兩個(gè)實(shí)驗(yàn)物理子系統(tǒng)中,圖像特征制作與截圖生成實(shí)驗(yàn)子系統(tǒng)將本文中所需要描述的流體物理學(xué)圖像特征及其應(yīng)用對(duì)象的局部輪廓特征進(jìn)行了綜合分析并并入庫(kù)。在這個(gè)圖像輪廓檢索工具子系統(tǒng)中,支持一個(gè)用戶通過(guò)瀏覽庫(kù)中現(xiàn)有的一個(gè)圖像庫(kù),手動(dòng)地繪制一個(gè)圖像庫(kù)的輪廓及然后選擇一個(gè)示例的視圖。

7.2編程環(huán)境

本次測(cè)試實(shí)驗(yàn)操作系統(tǒng)的主要程序開(kāi)發(fā)工具平臺(tái)主要是Window XP,選擇使用Visual C++6.0和Access兩款軟件作為主要的程序開(kāi)發(fā)工具,選擇Visual C++6.0和Access是因?yàn)樗鼈兌寄軌蚓哂忻嫦驅(qū)ο髴?yīng)用程序設(shè)計(jì)的基本整體化和性能設(shè)計(jì)特點(diǎn)以及所需要開(kāi)發(fā)的所有應(yīng)用程序都能夠具有高度的效率地正常運(yùn)行。同時(shí)又是一種微軟技術(shù)性高度相互集成的企業(yè)軟件開(kāi)發(fā)實(shí)用工具,它為企業(yè)用戶自己提供了一套功能強(qiáng)大的企業(yè)微軟軟件基礎(chǔ)類庫(kù)。且因我們已經(jīng)使用了Visual C++6.0來(lái)用于開(kāi)發(fā)一個(gè)基于視頻內(nèi)容的數(shù)字視頻流和圖像信息檢索系統(tǒng)。由于芯片系統(tǒng)內(nèi)部采用了面向?qū)ο蟮膱D像設(shè)計(jì)工作方式,這樣也就使得芯片系統(tǒng)的許多圖像功能以及處理圖像模塊都完全可以直接整合應(yīng)用起來(lái)到其它的芯片圖像處理系統(tǒng)中,而且需要添加新的圖像算法也就不必再因?yàn)樾枰~外復(fù)雜地進(jìn)行修改許多的圖像源代碼,非常好地有助于整個(gè)芯片系統(tǒng)在圖像功能上的逐步完善和不斷擴(kuò)展。

7.3程序結(jié)果

首先打開(kāi)一個(gè)圖像庫(kù)選擇一個(gè)圖像,然后對(duì)該圖像進(jìn)行特征提取。系統(tǒng)通過(guò)圖像檢索相似度的匹配,找到六個(gè)與其相似的圖像,輸出結(jié)果。找到六個(gè)與其相似的圖像,輸出結(jié)果。

八、總結(jié)

本文第一章對(duì)基于內(nèi)容的圖像檢索方式進(jìn)行了概述,進(jìn)而又著重介紹了基于形態(tài)的圖像檢索方式。并且廣泛地應(yīng)用了對(duì)圖像進(jìn)行邊緣檢查的技術(shù),對(duì)整個(gè)圖像進(jìn)行了檢索。它主要是運(yùn)用 canny 算子的方法。首先,是對(duì)邊緣的檢測(cè)主要以導(dǎo)數(shù)來(lái)計(jì)算,但是受到了噪聲影響。然而,該濾波器在減少了噪聲的作用下,也造成了邊緣強(qiáng)度的損耗。其次,增強(qiáng)算法把對(duì)鄰域的點(diǎn)的度有明顯改變的地方以及點(diǎn)凸顯性地展現(xiàn)了。一般可以靠計(jì)算機(jī)梯度的幅值來(lái)實(shí)現(xiàn)。再次,但是在有些圖象中,梯度幅值比較大的地方并非邊緣的節(jié)點(diǎn)。最簡(jiǎn)單的對(duì)邊緣性檢測(cè)就是梯度幅值閾值的判斷。最后,精確地選擇了邊緣處的位置。

我也希望在今后的將來(lái)有更多的人去探導(dǎo)、研究一個(gè)邊緣檢測(cè)算子,為使我們能夠看到更好的影片效果而努力,為了促進(jìn)全人類的生活和發(fā)展而努力。圖像是自古以來(lái)人類識(shí)別和交流信息的一個(gè)主要資料來(lái)源,因此,圖像處理的應(yīng)用領(lǐng)域已經(jīng)涵蓋到了人類日常生活、工作等諸多領(lǐng)域。隨著現(xiàn)代科學(xué)技術(shù)的發(fā)展和進(jìn)步,圖像的應(yīng)用領(lǐng)域也在不斷拓寬。所以對(duì)于邊緣性的檢測(cè)也是需要繼續(xù)進(jìn)步。我看到將來(lái),邊緣檢測(cè)技術(shù)已經(jīng)廣泛地應(yīng)用于人們?nèi)粘Ｉ畹母鱾€(gè)領(lǐng)域,在當(dāng)今世界人類的日常生活中,文化藝術(shù)、軍事技術(shù)、生物醫(yī)療技術(shù)、工業(yè)生產(chǎn)和信息工程技術(shù)、航天與空間技術(shù)等等重要的領(lǐng)域都占有著不可或缺的一部分。同全人類的生活走向風(fēng)流。

參考文獻(xiàn)

[1] 章毓晉．圖像處理和分析[M]．北京：清華大學(xué)出版社，1999

[2] 章國(guó)寶．葉樺．陳維南.基于正交小波變換的多尺度邊緣提取[J]．中國(guó)圖像圖形報(bào)，1998（3）

[3] 陳武凡．.彩色圖像邊緣檢測(cè)新算法?廣義模糊算子法[J]．中國(guó)科學(xué)A輯，1995（2）

[4] 唐立軍．段立娟．高文．基于內(nèi)容的圖像檢索系統(tǒng)[J]．計(jì)算機(jī)應(yīng)用研究，2001，18(7)：41-45

[5] 馮所前．文檔內(nèi)容圖像檢索[D]．北京大學(xué)信息科學(xué)技術(shù)學(xué)院智能科學(xué)系碩士學(xué)位論文，2005

[6] 謝毓湘．吳玲達(dá)．欒悉道．基于內(nèi)容的圖像檢索技術(shù)研究[J]．計(jì)算機(jī)工程與應(yīng)用，2002(1)：35-38

[7] 宋濤．劉剛．一種基于內(nèi)容的文檔圖像檢索方法．《鄭州大學(xué)報(bào)》，2010年1月

[8] 郭小娟．基于內(nèi)容的圖像檢索技術(shù)的研究[D]．西安：西北大學(xué)，2007

[9] 徐建華．圖像處理與分析[M ]．北京:科學(xué)出版社，1992

[10] 賈元元．基于形狀的圖像數(shù)據(jù)庫(kù)檢索技術(shù)研究[學(xué)位論文] 2004

[11] Ang Y H．Image Retrieval Based on Multidimensional Feature Properties 1995

[12] 賴志國(guó)．余嘯海．Matlab 圖像處理與應(yīng)用[M]．北京：國(guó)防工業(yè)出版社，2004

[13] 唐路路．張啟燦．一種自適應(yīng)閾值的Canny邊緣檢測(cè)算法/光電工程：第38卷第5期，2011．5

第三篇：算法總結(jié)

算法分析與設(shè)計(jì)總結(jié)報(bào)告

71110415 錢玉明

在計(jì)算機(jī)軟件專業(yè)中，算法分析與設(shè)計(jì)是一門非常重要的課程，很多人為它如癡如醉。很多問(wèn)題的解決，程序的編寫都要依賴它，在軟件還是面向過(guò)程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個(gè)公式。算法的學(xué)習(xí)對(duì)于培養(yǎng)一個(gè)人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問(wèn)題，解決問(wèn)題的能力。作為IT行業(yè)學(xué)生，學(xué)習(xí)算法無(wú)疑會(huì)增強(qiáng)自己的競(jìng)爭(zhēng)力，修煉自己的“內(nèi)功”。

下面我將談?wù)勎覍?duì)這門課程的心得與體會(huì)。

一、數(shù)學(xué)是算法的基礎(chǔ)

經(jīng)過(guò)這門課的學(xué)習(xí)，我深刻的領(lǐng)悟到數(shù)學(xué)是一切算法分析與設(shè)計(jì)的基礎(chǔ)。這門課的很多時(shí)間多花在了數(shù)學(xué)公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來(lái)的，尤其是算法性能的分析更是與數(shù)學(xué)息息相關(guān)。其中有幾個(gè)定理令我印象深刻。

①主定理

本門課中它主要應(yīng)用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個(gè)大問(wèn)題分解為a個(gè)子問(wèn)題，其中子問(wèn)題的規(guī)模為b。而f(n)可看作這些子問(wèn)題的組合時(shí)的消耗。這些可以利用主定理的相關(guān)結(jié)論進(jìn)行分析處理。當(dāng)f(n)量級(jí)高于nlogba時(shí)，我們可以設(shè)法降低子問(wèn)題組合時(shí)的消耗來(lái)提高性能。反之我們可以降低nlogba的消耗，即可以擴(kuò)大問(wèn)題的規(guī)?；蛘邷p小子問(wèn)題的個(gè)數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進(jìn)行有效的改進(jìn)。

②隨機(jī)算法中的許多定理的運(yùn)用

在這門課中，我學(xué)到了以前從未遇見(jiàn)過(guò)的隨機(jī)算法，它給予我很大的啟示。隨機(jī)算法不隨機(jī)，它可通過(guò)多次的嘗試來(lái)降低它的錯(cuò)誤率以至于可以忽略不計(jì)。這些都不是空穴來(lái)風(fēng)，它是建立在嚴(yán)格的定理的證明上。如素?cái)?shù)判定定理是個(gè)很明顯的例子。它運(yùn)用了包括費(fèi)馬小定理在內(nèi)的各種定理。將這些定理進(jìn)行有效的組合利用，才得出行之有效的素?cái)?shù)判定的定理。尤其是對(duì)尋找證據(jù)數(shù)算法的改進(jìn)的依據(jù)，也是建立在3個(gè)定理上。還有檢查字符串是否匹配也是運(yùn)用了許多定理：指紋的運(yùn)用，理論出錯(cuò)率的計(jì)算，算法性能的評(píng)價(jià)也都是建立在數(shù)學(xué)定理的運(yùn)用上。

這些算法都給予了我很大啟發(fā)，要想學(xué)好算法，學(xué)好數(shù)學(xué)是必不可少的。沒(méi)有深厚的數(shù)學(xué)功力作為地基，即使再漂亮的算法框架，代碼實(shí)現(xiàn)也只能是根底淺的墻上蘆葦。

二、算法的核心是思想

我們學(xué)習(xí)這門課不是僅僅掌握那幾個(gè)經(jīng)典算法例子，更重要的是為了學(xué)習(xí)蘊(yùn)含在其中的思想方法。為什么呢？舉個(gè)例子。有同學(xué)曾問(wèn)我這樣一個(gè)問(wèn)題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個(gè)星期。現(xiàn)在用10只老鼠在一個(gè)星期內(nèi)判斷那只瓶子有毒，每只老鼠可以喝多個(gè)瓶子的水，每個(gè)瓶子可以只喝一點(diǎn)。問(wèn)如何解決？其實(shí)一開(kāi)始我也一頭霧水，但是他提醒我跟計(jì)算機(jī)領(lǐng)域相關(guān)，我就立馬有了思路，運(yùn)用二進(jìn)制。因?yàn)橛?jì)算機(jī)的最基本思想就是二進(jìn)制。所以說(shuō)，我們不僅要學(xué)習(xí)算法，更得學(xué)習(xí)思想方法。

①算法最基本的設(shè)計(jì)方法包括分治法，動(dòng)態(tài)規(guī)劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個(gè)元素中最大元和最小元的量級(jí)，降低n位二進(jìn)制x和y相乘的量級(jí)，做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問(wèn)題分解為規(guī)模較小的獨(dú)立的子問(wèn)題，關(guān)鍵是子問(wèn)題要與原問(wèn)題同類，可以采取平衡法來(lái)提高性能。

動(dòng)態(tài)規(guī)劃法是把大問(wèn)題分解為子問(wèn)題，但是子問(wèn)題是重復(fù)的，后面的問(wèn)題可以利用前面解決過(guò)的問(wèn)題的結(jié)果。如構(gòu)造最優(yōu)二叉查找樹(shù)，解決矩陣連乘時(shí)最小計(jì)算次數(shù)問(wèn)題，尋找最長(zhǎng)公共子序列等等。

貪心法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構(gòu)造出更大的局部直至整體。如Kruscal最小生成樹(shù)算法，求哈夫曼編碼問(wèn)題。

周游法就是簡(jiǎn)單理解就是采取一定的策略遍歷圖中所有的點(diǎn)，典型的應(yīng)用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。

回溯法就是就是在滿足一定的條件后就往前走，當(dāng)走到某步時(shí)，發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應(yīng)用就是8皇后問(wèn)題，平面點(diǎn)集的凸包問(wèn)題和0-1背包問(wèn)題。

分支定界法：它是解決整數(shù)規(guī)劃問(wèn)題一種最常用的方法。典型應(yīng)用就是解決整數(shù)規(guī)劃問(wèn)題。

②評(píng)價(jià)算法性能的方法如平攤分析中的聚集法，會(huì)計(jì)法和勢(shì)能法。聚集法就是把指令分為幾類，計(jì)算每一類的消耗，再全部疊加起來(lái)。會(huì)計(jì)法就是計(jì)算某個(gè)指令時(shí)提前將另一個(gè)指令的消耗也算進(jìn)去，以后計(jì)算另一個(gè)指令時(shí)就不必再算了。勢(shì)能法計(jì)算每一步的勢(shì)的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計(jì)。

這幾種方法都是平攤分析法，平攤分析的實(shí)質(zhì)就是總體考慮指令的消耗時(shí)間，盡管某些指令的消耗時(shí)間很大也可以忽略不計(jì)。上述三種方法難易程度差不多，每種方法都有屬于它的難點(diǎn)。如聚集法中如何將指令有效分類，會(huì)計(jì)法中用什么指令提前計(jì)算什么指令的消耗，勢(shì)能法中如何選取勢(shì)能。因此掌握這些方法原理還不夠，還要學(xué)會(huì)去應(yīng)用，在具體的問(wèn)題中去判斷分析。

三、算法與應(yīng)用緊密相關(guān)

我認(rèn)為學(xué)習(xí)算法不能局限于書本上的理論運(yùn)算，局限于如何提高性能以降低復(fù)雜度，我們要將它與實(shí)際生活聯(lián)系起來(lái)。其實(shí)算法問(wèn)題的產(chǎn)生就來(lái)自于生活，設(shè)計(jì)出高效的算法就是為了更好的應(yīng)用。如尋找最長(zhǎng)公共子序列算法可以應(yīng)用在生物信息學(xué)中通過(guò)檢測(cè)相似DNA片段的相似成分來(lái)檢測(cè)生物特性的相似性，也可以用來(lái)判斷兩個(gè)字符串的相近性，這可應(yīng)用在數(shù)據(jù)挖掘中。快速傅立葉變換（FFT）可應(yīng)用在計(jì)算多項(xiàng)式相乘上來(lái)降低復(fù)雜度，脫線min算法就是利用了Union-Find這種結(jié)構(gòu)。還有圖中相關(guān)算法，它對(duì)于解決網(wǎng)絡(luò)流量分配問(wèn)題起了很大的幫助，等等。

這些應(yīng)用給了我很大的啟發(fā)：因?yàn)閱渭冎v一個(gè)Union-Find算法，即使了解了它的實(shí)現(xiàn)原理，遇到具體的實(shí)際問(wèn)題也不知去如何應(yīng)用。這就要求我們要將自己學(xué)到的算法要和實(shí)際問(wèn)題結(jié)合起來(lái)，不能停留在思想方法階段，要學(xué)以致用，做到具體問(wèn)題具體分析。

四、對(duì)計(jì)算模型和NP問(wèn)題的理解

由于對(duì)這部分內(nèi)容不是很理解，所以就粗淺的談一下我的看法。

首先談到計(jì)算模型，就不得不提到圖靈計(jì)算，他將基本的計(jì)算抽象化，造出一個(gè)圖靈機(jī)，得出了計(jì)算的本質(zhì)。并提出圖靈機(jī)可以計(jì)算的問(wèn)題都是可以計(jì)算的，否則就是不可計(jì)算的。由此引申出一個(gè)著名論題：任何合理的計(jì)算模型都是相互等價(jià)的。它說(shuō)明了可計(jì)算性本身不依賴于任何具體的模型而客觀存在。

NP問(wèn)題比較復(fù)雜，我認(rèn)為它是制約算法發(fā)展的瓶頸，但這也是算法分析的魅力所在。NP問(wèn)題一般可分為3類，NP-C問(wèn)題，NP-hard問(wèn)題以及頑型問(wèn)題。NP-C它有個(gè)特殊的性質(zhì)，如果存在一個(gè)NP-C問(wèn)題找到一個(gè)多項(xiàng)式時(shí)間的解法，則所有的NP-C問(wèn)題都能找到多項(xiàng)式時(shí)間解法。如哈密頓回路問(wèn)題。NP-hard主要是解決最優(yōu)化問(wèn)題。它不一定是NP問(wèn)題。這些問(wèn)題在規(guī)模較小時(shí)可以找出精確解，但是規(guī)模大時(shí)，就因時(shí)間太復(fù)雜而找不到最優(yōu)解。此時(shí)一般會(huì)采用近似算法的解法。頑型問(wèn)題就是已經(jīng)證明不可能有多項(xiàng)式時(shí)間的算法，如漢諾塔問(wèn)題。

最后談?wù)剬?duì)這門課程的建議

①對(duì)于這門算法課，我認(rèn)為應(yīng)該加強(qiáng)對(duì)算法思想方法的學(xué)習(xí)。所以我建議老師可不可以先拋出問(wèn)題而不給出答案，講完一章，再發(fā)課件。讓我們先思考一會(huì)兒，或者給出個(gè)獎(jiǎng)勵(lì)機(jī)制，誰(shuí)能解決這個(gè)問(wèn)題，平時(shí)成績(jī)加分。這在一定程度上會(huì)將強(qiáng)我們思考分析問(wèn)題的能力。因?yàn)槲腋杏X(jué)到，一個(gè)問(wèn)題出來(lái)，未經(jīng)過(guò)思考就已經(jīng)知曉它的答案，就沒(méi)什么意思，得不到提高，而且也不能加深對(duì)問(wèn)題的思考和理解。下次遇到類似的問(wèn)題也就沒(méi)有什么印象。而且上課讓我們思考，點(diǎn)名回答問(wèn)題可以一定程度上有效的防止不認(rèn)真聽(tīng)課的現(xiàn)象。

②作業(yè)安排的不是很恰當(dāng)。本門課主要安排了三次作業(yè)，個(gè)人感覺(jué)只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實(shí)現(xiàn)一下偽代碼，沒(méi)有太多的技術(shù)含量。而且對(duì)于培養(yǎng)我們的解決問(wèn)題的能力也沒(méi)有太多的幫助，因?yàn)檫@間接成為了程序設(shè)計(jì)題，不是算法設(shè)計(jì)題。

③本門課的時(shí)間安排的不太恰當(dāng)，因?yàn)楸緦W(xué)期的課程太多，壓力太大。沒(méi)有太多的時(shí)間去學(xué)習(xí)這門課程。因?yàn)槲蚁嘈糯蠹叶紝?duì)它感興趣，比較重視，想花功夫，但苦于沒(méi)時(shí)間。所以可不可以將課程提前一個(gè)學(xué)期，那時(shí)候離散數(shù)學(xué)也已經(jīng)學(xué)過(guò)，且課程的壓力也不是很大。錯(cuò)開(kāi)時(shí)間的話，我覺(jué)得應(yīng)該能夠更好提高大家算法分析設(shè)計(jì)的能力。

第四篇：算法復(fù)習(xí)材料

1.假票統(tǒng)計(jì)

問(wèn)題描述：

由于你們團(tuán)隊(duì)在國(guó)際大學(xué)生詩(shī)歌大賽上取得的巨大成就，你們學(xué)校決定為你們召開(kāi)一次慶功雞尾酒會(huì)，到來(lái)的人數(shù)大大超出了預(yù)期。然而慶功會(huì)的主管卻抱怨發(fā)現(xiàn)了有人使用假票，實(shí)際的門票是從1到N(N <= 10000)，主管懷疑有人采用復(fù)印、打印等手段偽造了門票。他把所有收上來(lái)的門票拿給你，要求你編寫程序，統(tǒng)計(jì)所有門票中存在假票的門票數(shù)。輸入：

輸入文件中包含多組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)占兩行。第1行包括兩個(gè)整數(shù)N和M，分別表示門票的初始總張數(shù)和參加晚會(huì)的總?cè)藬?shù)(1 <= N <= 10000,1 <= M <= 20000)。第2行為M個(gè)整數(shù)Ti，表示收到的M張門票的號(hào)碼(1 <= Ti <= N)。輸入文件最后一行為0 0，表示輸入結(jié)束。輸出：

對(duì)每組輸入測(cè)試數(shù)據(jù)，輸出一個(gè)整數(shù)，占一行，表示收上來(lái)的門票中共有多少?gòu)埰北粋卧爝^(guò)。輸入樣例： 5 5 3 3 1 2 4 6 10 6 1 3 6 6 4 2 3 1 2 0 0 輸出樣例： 1 4

參考代碼：

//計(jì)算有幾個(gè)號(hào)碼被復(fù)制過(guò) #include #include #define N 10010 #define M 20010 intcnt[N];//cnt[i],i出現(xiàn)的次數(shù) int main(){ int n, m,t;while(scanf(“%d%d”, &n, &m), n + m){ memset(cnt, 0, sizeof(cnt));int i, j, res = 0;for(i = 0;i < m;i++){ scanf(“%d”, &t);cnt[t]++;} for(i = 1;i <= n;i++){ if(cnt[i] > 1){ res ++;} } printf(“%dn”, res);} return 0;}

2.看和說(shuō)

問(wèn)題描述：

看和說(shuō)的順序定義如下：任何一個(gè)字符串都是以數(shù)字開(kāi)頭，每個(gè)隨后的元素都是被前一個(gè)元素重新定義。例如，字符串“122344111”可以被描述為“1個(gè)1，兩個(gè)2，1個(gè)3，2個(gè)4和3個(gè)1”。因此，122344111以序列的形式表示出來(lái)就是1122132431。同理，101就表示1111111111。輸入：

輸入包括測(cè)試數(shù)據(jù)的組數(shù)，然后依次為相應(yīng)的測(cè)試數(shù)據(jù)，每個(gè)數(shù)據(jù)占一行，不會(huì)超過(guò)1000位。輸出： 對(duì)于每個(gè)測(cè)試數(shù)據(jù)，輸出對(duì)應(yīng)的字符串。

輸入樣例： 3 122344111 1111111111 12345 輸出樣例： 1122132431 101 1112131415 參考代碼：

#include #include int main(){ char s[1001];intn,i,num,len;scanf(“%dn”,&n);while(n--){

num=1;

gets(s);

len=strlen(s);

for(i=0;i

{

if(s[i]!=s[i+1])

{

printf(“%d%c”,num,s[i]);

num=1;

}

else

num++;

}

printf(“n”);} return 0;}

3．二進(jìn)制轉(zhuǎn)化為十六進(jìn)制

問(wèn)題描述：

輸入一個(gè)2進(jìn)制的數(shù)，要求輸出該2進(jìn)制數(shù)的16進(jìn)制表示。在16進(jìn)制的表示中，A-F表示10-15 輸入：

第1行是測(cè)試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入。每組測(cè)試數(shù)據(jù)占1行，包括一個(gè)以0和1組成的字符串，字符串長(zhǎng)度至少是1，至多是10000。輸出：

n行，每行輸出對(duì)應(yīng)一個(gè)輸入。輸入樣例： 100000 111 輸出樣例： 7

參考代碼1：

#include #include int main(){

inti,n,dec,len;

char bin[10001];

scanf(“%d”,&n);

while(n--)

{

scanf(“%s”,bin);

len=strlen(bin);//求二進(jìn)制數(shù)的長(zhǎng)度

dec=4-len%4;

if(len%4)//處理頭幾位，后移dec位，使得變成4的整數(shù)倍，前面補(bǔ)0

{

for(i=len;i>=0;i--)

bin[i+dec]=bin[i];

for(i=0;i

bin[i]='0';

len+=dec;

}

for(i=0;i

printf(“%X”,(bin[i+3]-'0')+(bin[i+2]-'0')*2+(bin[i+1]-'0')*4+(bin[i]-'0')*8);

printf(“n”);

}

return 0;}

//參考代碼2：

#include #include #define maxn 10006

int main(){ int i, j, t, tp, p;charstr[maxn], str_rev[maxn];char res[maxn/4], tmp[6], tmp_rev[6];while(scanf(“%d”, &t)!=EOF){ while(t--){ p = 0;scanf(“%s”, &str);intlen = strlen(str);for(i = lenii;strncpy(tmp, str_rev + i, k);for(j = kj-1] = tmp[j];sscanf(tmp_rev, “%d”, &tp);//printf(“k = %d tp = %d tmp = %s tmp_rev = %sn”, k, tp, tmp, tmp_rev);switch(tp){ case 0: res[p++] = '0';break;case 1: res[p++] = '1';break;case 10: res[p++] = '2';break;case 11: res[p++] = '3';break;case 100: res[p++] = '4';break;case 101: res[p++] = '5';break;case 110: res[p++] = '6';break;case 111: res[p++] = '7';break;case 1000: res[p++] = '8';break;case 1001: res[p++] = '9';break;case 1010: res[p++] = 'A';break;case 1011: res[p++] = 'B';break;case 1100: res[p++] = 'C';break;case 1101: res[p++] = 'D';break;case 1110: res[p++] = 'E';break;case 1111: res[p++] = 'F';break;default: break;} i += 4;

} for(i = p-1;i >= 0;i--)printf(“%c”, res[i]);printf(“n”);} } return 0;}

第五篇：算法總結(jié)

算法分塊總結(jié)

為備戰(zhàn)2005年11月4日成都一戰(zhàn)，特將已經(jīng)做過(guò)的題目按算法分塊做一個(gè)全面詳細(xì)的總結(jié)，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設(shè)計(jì)中，時(shí)刻都要牢記要減少冗余，要以簡(jiǎn)潔高效為追求目標(biāo)。另外當(dāng)遇到陌生的問(wèn)題時(shí)，要想方設(shè)法進(jìn)行模型簡(jiǎn)化，轉(zhuǎn)化，轉(zhuǎn)化成我們熟悉的東西。

圖論模型的應(yīng)用

分層圖思想的應(yīng)用：

用此思想可以建立起更簡(jiǎn)潔、嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型，進(jìn)而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質(zhì)： 由于層是由復(fù)制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進(jìn)行新層的存儲(chǔ)，甚至幾乎不需要花時(shí)間去處理。由于層之間的相似性，很多計(jì)算結(jié)果都是相同的。所以我們只需對(duì)這些計(jì)算進(jìn)行一次，把結(jié)果存起來(lái)，而不需要反復(fù)計(jì)算。如此看來(lái)，雖然看起來(lái)圖變大了，但實(shí)際上問(wèn)題的規(guī)模并沒(méi)有變大。層之間是拓?fù)溆行虻?。這也就意味著在層之間可以很容易實(shí)現(xiàn)遞推等處理，為發(fā)現(xiàn)有效算法打下了良好的基礎(chǔ)。

這些特點(diǎn)說(shuō)明這個(gè)分層圖思想還是很有潛力的，尤其是各層有很多公共計(jì)算結(jié)果這一點(diǎn)，有可能大大消除冗余計(jì)算，進(jìn)而降低算法時(shí)間復(fù)雜度。二分圖最大及完備匹配的應(yīng)用： ZOJ place the robots: 二分圖最優(yōu)匹配的應(yīng)用：

最大網(wǎng)絡(luò)流算法的應(yīng)用：典型應(yīng)用就求圖的最小割。最小費(fèi)用最大流的應(yīng)用：

容量有上下界的最大流的應(yīng)用：

歐拉路以及歐拉回路的應(yīng)用：主要利用求歐拉路的套圈算法。最小生成樹(shù)：

求最小生成樹(shù)，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復(fù)雜度降為O(Vlog2V+E)，后者一般應(yīng)用于稀疏圖，其時(shí)間復(fù)雜度為O(Elog2V)。最小K度限制生成樹(shù)：

抽象成數(shù)學(xué)模型就是：

設(shè)G=(V,E,ω)是連通的無(wú)向圖，v0 ∈V是特別指定的一個(gè)頂點(diǎn),k為給定的一個(gè)正整數(shù)。首先考慮邊界情況。先求出問(wèn)題有解時(shí)k 的最小值：把v0點(diǎn)從圖中刪去后，圖中可能會(huì)出 現(xiàn)m 個(gè)連通分量，而這m 個(gè)連通分量必須通過(guò)v0來(lái)連接，所以，在圖G 的所有生成樹(shù)中 dT(v0)≥m。也就是說(shuō)，當(dāng)k

首先，將 v0和與之關(guān)聯(lián)的邊分別從圖中刪去，此時(shí)的圖可能不再連通，對(duì)各個(gè)連通分量，分別求最小生成樹(shù)。接著，對(duì)于每個(gè)連通分量V’，求一點(diǎn)v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過(guò)邊(v1,v0)與v0相連。于是，我們就得到了一個(gè)m度限制生成樹(shù)，不難證明，這就是最小m度限制生成樹(shù)。這一步的時(shí)間復(fù)雜度為O(Vlog2V+E)我們所求的樹(shù)是無(wú)根樹(shù)，為了解題的簡(jiǎn)便，把該樹(shù)轉(zhuǎn)化成以v0為根的有根樹(shù)。

假設(shè)已經(jīng)得到了最小p度限制生成樹(shù)，如何求最小p+1 度限制生成樹(shù)呢？在原先的樹(shù)中加入一條與v0相關(guān)聯(lián)的邊后，必定形成一個(gè)環(huán)。若想得到一棵p+1 度限制生成樹(shù)，需刪去一條在環(huán)上的且與v0無(wú)關(guān)聯(lián)的邊。刪去的邊的權(quán)值越大，則所得到的生成樹(shù)的權(quán)值和就越小。動(dòng)態(tài)規(guī)劃就有了用武之地。設(shè)Best(v)為路徑v0—v上與v0無(wú)關(guān)聯(lián)且權(quán)值最大的邊。定義father(v)為v的父結(jié)點(diǎn)，動(dòng)態(tài)轉(zhuǎn)移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

狀態(tài)共|V|個(gè)，狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度O(1)，所以總的時(shí)間復(fù)雜度為O(V)。故由最小p度限制生成樹(shù)得到最小p+1度限制生成樹(shù)的時(shí)間復(fù)雜度為O(V)。1 先求出最小m度限制生成樹(shù)；

2由最小m度限制生成樹(shù)得到最小m+1度限制生成樹(shù);3 當(dāng)dT(v0)=k時(shí)停止。

加邊和去邊過(guò)程，利用動(dòng)態(tài)規(guī)劃優(yōu)化特別值得注意。

次小生成樹(shù)：

加邊和去邊很值得注意。

每加入一條不在樹(shù)上的邊，總能形成一個(gè)環(huán)，只有刪去環(huán)上的一條邊，才能保證交換后仍然是生成樹(shù)，而刪去邊的權(quán)值越大，新得到的生成樹(shù)的權(quán)值和越小。具體做法：

首先做一步預(yù)處理，求出樹(shù)上每?jī)蓚€(gè)結(jié)點(diǎn)之間的路徑上的權(quán)值最大的邊，然后，枚舉圖中不在樹(shù)上的邊，有了剛才的預(yù)處理，我們就可以用O(1)的時(shí)間得到形成的環(huán)上的權(quán)值最大的邊。如何預(yù)處理呢？因?yàn)檫@是一棵樹(shù)，所以并不需要什么高深的算法，只要簡(jiǎn)單的BFS 即可。

最短路徑的應(yīng)用：

Dijkstra 算法應(yīng)用： Folyed 算法應(yīng)用：

Bellman-Ford 算法的應(yīng)用：

差分約束系統(tǒng)的應(yīng)用：

搜索算法

搜索對(duì)象和搜索順序的選取最為重要。一些麻煩題，要注意利用數(shù)據(jù)有序化，要找一個(gè)較優(yōu)的搜索出發(fā)點(diǎn)，凡是能用高效算法的地方盡量爭(zhēng)取用高效算法。基本的遞歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應(yīng)用： 枚舉思想的應(yīng)用： ZOJ 1252 island of logic A*算法的應(yīng)用：

IDA*算法的應(yīng)用，以及跳躍式搜索探索： 限深搜索，限次： 迭代加深搜索：

部分搜索+高效算法（比如二分匹配，動(dòng)態(tài)規(guī)劃）： ZOJ milk bottle data: 剪枝優(yōu)化探索：

可行性剪枝，最優(yōu)性剪枝，調(diào)整搜索順序是常用的優(yōu)化手段。

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃最重要的就是狀態(tài)的選取，以及狀態(tài)轉(zhuǎn)移方程，另外還要考慮高效的預(yù)處理（以便更好更快的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移）。最常用的思想就是用枚舉最后一次操作。

狀態(tài)壓縮DP，又叫帶集合的動(dòng)態(tài)規(guī)劃：題目特點(diǎn)是有一維的維數(shù)特別小。類似TSP問(wèn)題的DP：

狀態(tài)劃分比較困難的題目： 樹(shù)形DP：

四邊形不等式的應(yīng)用探索：四邊形不等式通常應(yīng)用是把O(n^3)復(fù)雜度O(n^2)

高檔數(shù)據(jù)結(jié)構(gòu)的應(yīng)用

并查集的應(yīng)用：

巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹(shù)的應(yīng)用：

總結(jié)用線段樹(shù)解題的方法

根據(jù)題目要求將一個(gè)區(qū)間建成線段樹(shù)，一般的題目都需要對(duì)坐標(biāo)離散。建樹(shù)時(shí)，不要拘泥于線段樹(shù)這個(gè)名字而只將線段建樹(shù)，只要是表示區(qū)間，而且區(qū)間是由單位元素(可以是一個(gè)點(diǎn)、線段、或數(shù)組中一個(gè)值)組成的，都可以建線段樹(shù)；不要拘泥于一維，根據(jù)題目要求可以建立面積樹(shù)、體積樹(shù)等等

樹(shù)的每個(gè)節(jié)點(diǎn)根據(jù)題目所需，設(shè)置變量記錄要求的值

用樹(shù)形結(jié)構(gòu)來(lái)維護(hù)這些變量：如果是求總數(shù)，則是左右兒子總數(shù)之和加上本節(jié)點(diǎn)的總數(shù)，如果要求最值，則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時(shí)，都只對(duì)O(logL)個(gè)節(jié)點(diǎn)修改這個(gè)特點(diǎn)，在O(logL)的時(shí)間內(nèi)維護(hù)修改后相關(guān)節(jié)點(diǎn)的變量。

在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中，要靈活的運(yùn)用子樹(shù)的收縮與葉子節(jié)點(diǎn)的釋放，避免重復(fù)操作。

Trie的應(yīng)用：；

Trie圖的應(yīng)用探索： 后綴數(shù)組的應(yīng)用研究：

在字符串處理當(dāng)中，后綴樹(shù)和后綴數(shù)組都是非常有力的工具，其中后綴樹(shù)了解得比較多，關(guān)于后綴數(shù)組則很少見(jiàn)于國(guó)內(nèi)的資料。其實(shí)后綴數(shù)組是后綴樹(shù)的一個(gè)非常精巧的替代品，它比后綴樹(shù)容易編程實(shí)現(xiàn)，能夠?qū)崿F(xiàn)后綴樹(shù)的很多功能而時(shí)間復(fù)雜度也不太遜色，并且，它比后綴樹(shù)所占用的空間小很多。

樹(shù)狀數(shù)組的應(yīng)用探索：；

計(jì)算幾何

掌握基本算法的實(shí)現(xiàn)。凸包的應(yīng)用：；

半平面交算法的應(yīng)用：；

幾何+模擬類題目：幾何設(shè)計(jì)好算法，模擬控制好精度。掃描法：；

轉(zhuǎn)化法：ZOJ 1606 將求所圍的格子數(shù)，巧妙的轉(zhuǎn)化為求多邊形的面積。離散法思想的應(yīng)用：；

經(jīng)典算法：找平面上的最近點(diǎn)對(duì)。

貪心

矩形切割

二分思想應(yīng)用

活用經(jīng)典算法

利用歸并排序算法思想求數(shù)列的逆序?qū)?shù)：

利用快速排序算法思想，查詢N個(gè)數(shù)中的第K小數(shù)：

博弈問(wèn)題

博弈類題目通常用三類解法：第一類推結(jié)論； 第二類遞推，找N位置，P位置； 第三類SG函數(shù)的應(yīng)用。第四類極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類極大極小法。

第一類：推結(jié)論。典型題目： 第二類：遞推。典型題目：

比如有向無(wú)環(huán)圖類型的博弈。在一個(gè)有向圖中，我們把選手I有必勝策略的初始位置稱為N位置(Next player winning)，其余的位置被稱為P位置(Previous player winning)。很顯然，P位置和N位置應(yīng)該具有如下性質(zhì)：

1． 所有的結(jié)束位置都是P位置。

2． 對(duì)于每一個(gè)N位置，至少存在一種移動(dòng)可以將棋子移動(dòng)到一個(gè)P位置。3． 對(duì)于每一個(gè)P位置，它的每一種移動(dòng)都會(huì)將棋子移到一個(gè)N位置。

這樣，獲勝的策略就是每次都把棋子移動(dòng)到一個(gè)P位置，因?yàn)樵谝粋€(gè)P位置，你的對(duì)手只能將棋子移動(dòng)到一個(gè)N位置，然后你總有一種方法再把棋子移動(dòng)到一個(gè)P位置。一直這樣移動(dòng)，最后你一定會(huì)將棋子移動(dòng)到一個(gè)結(jié)束位置（結(jié)束位置是P位置），這時(shí)你的對(duì)手將無(wú)法在移動(dòng)棋子，你便贏得了勝利。

與此同時(shí)，得到了這些性質(zhì)，我們便很容易通過(guò)倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為：

1． 將所有的結(jié)束位置標(biāo)為P位置。

2． 將所有能一步到達(dá)P位置的點(diǎn)標(biāo)為N位置。

3． 找出所有只能到達(dá)N位置的點(diǎn)，將它們標(biāo)為P位置。

4． 如果在第三步中沒(méi)有找到新的被標(biāo)為P位置的點(diǎn)，則算法結(jié)束，否則轉(zhuǎn)到步驟2。這樣我們便確定了所有位置，對(duì)于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類：SG函數(shù)的應(yīng)用。

關(guān)于SG函數(shù)的基本知識(shí)：對(duì)于一個(gè)有向圖(X, F)來(lái)說(shuō)，SG函數(shù)g是一個(gè)在X上的函數(shù)，并且它返回一個(gè)非負(fù)整數(shù)值，具體定義為

g(x)?min{n?0,n?g(y)對(duì)于所有y?F(x)}

1． 對(duì)于所有的結(jié)束位置x，g(x)= 0。

2． 對(duì)于每一個(gè)g(x)≠ 0的位置x，在它可以一步到達(dá)的位置中至少存在一個(gè)位置y使得g(y)= 0。

3．對(duì)于每一個(gè)g(x)＝ 0的位置x，所有可以由它一步到達(dá)的位置y都有g(shù)(y)≠ 0。

定理 如果g(xi)是第i個(gè)有向圖的SG函數(shù)值，i = 1,…,n，那么在由這n個(gè)有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

第四類：極大極小法。

典型題目：ZOJ 1155：Triangle War

ZOJ 1993：A Number Game

矩陣妙用

矩陣最基本的妙用就是利用快速乘法O（logn）來(lái)求解遞推關(guān)系（最基本的就是求Fibonacci數(shù)列的某項(xiàng)）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目：

數(shù)學(xué)模型舉例

向量思想的應(yīng)用：

UVA 10089：注意降維和向量的規(guī)范化 ；

利用復(fù)數(shù)思想進(jìn)行向量旋轉(zhuǎn)。

UVA 10253：

遞推

數(shù)代集合

數(shù)代集合的思想：

ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題：Intuitionistic Logic 用枚舉+數(shù)代集合思想優(yōu)化，注意到題中有一句話：“You may assume that the number H = |H| of elements of H?doesn't exceed 100”，這句話告訴我們H的元素個(gè)數(shù)不會(huì)超過(guò)100，因此可以考慮用一個(gè)數(shù)代替一個(gè)集合，首先把所有的運(yùn)算結(jié)果都用預(yù)處理算出來(lái)，到計(jì)算的時(shí)候只要用O(1)的復(fù)雜度就可以完成一次運(yùn)算。

組合數(shù)學(xué)

Polya定理則是解決同構(gòu)染色計(jì)數(shù)問(wèn)題的有力工具。

補(bǔ)集轉(zhuǎn)化思想

ZOJ 單色三角形：

字符串相關(guān)

擴(kuò)展的KMP算法應(yīng)用：；最長(zhǎng)回文串； 最長(zhǎng)公共子串； 最長(zhǎng)公共前綴；

填充問(wèn)題

高精度運(yùn)算

三維空間問(wèn)題專題

無(wú)論什么問(wèn)題，一旦擴(kuò)展到三難空間，就變得很有難度了。三維空間的問(wèn)題，很考代碼實(shí)現(xiàn)能力。

其它問(wèn)題的心得

解決一些判斷同構(gòu)問(wèn)題的方法：同構(gòu)的關(guān)鍵在于一一對(duì)應(yīng)，而如果枚舉一一對(duì)應(yīng)的關(guān)系，時(shí)間復(fù)雜度相當(dāng)?shù)母撸米钚”硎?，就能把一個(gè)事物的本質(zhì)表示出來(lái)。求最小表示時(shí)，我們一定要仔細(xì)分析，將一切能區(qū)分兩個(gè)元素的條件都在最小表示中體現(xiàn)，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當(dāng)?shù)?、高效的匹配算法（例如KMP字符匹配之類的），來(lái)比較最小表示是否相同，這里常常要將我們熟悉的高效算法進(jìn)行推廣