一些實(shí)施例中，可通過(guò)使用算數(shù)編碼、 化ffman編碼、枚舉編碼或其他損失較小的編碼方法對(duì)S的緊湊表示進(jìn)行編碼和發(fā)送來(lái)編碼 和發(fā)送R。
[0060] 在一些實(shí)施例中，通過(guò)使用與上文中對(duì)R= 中的列進(jìn)行編碼和發(fā)送相似的方 法來(lái)對(duì)查詢X的緊湊表示rx = O X進(jìn)行編碼和發(fā)送，而不是對(duì)R進(jìn)行編碼和發(fā)送，其中O是如 上的KxL矩陣。在運(yùn)些實(shí)施例中，針對(duì)R對(duì)rx進(jìn)行檢查，W驗(yàn)證X在S'中的成員身份。如果rx是 R中的列，則X被聲明為S'中的成員。此外，可通過(guò)使用約束編程從rx和S重新構(gòu)建X。在距離 函數(shù)d是Ll距離函數(shù)的實(shí)施例中，可通過(guò)使用線性編程來(lái)重新構(gòu)建X，其中d(x，S)含S可作為 線性約束。在距離函數(shù)d是L2距離函數(shù)的實(shí)施例中，可通過(guò)使用平方編程來(lái)重新構(gòu)建X。
[0061] 此外，為了減少假陽(yáng)錯(cuò)誤或?yàn)榱嗽诖鎯?chǔ)復(fù)雜度和計(jì)算復(fù)雜度之間進(jìn)行平衡，可使 用利用用于成員身份測(cè)試的Bloom過(guò)濾器和用于在成功成員身份測(cè)試后進(jìn)行最近鄰捜索 (例如，基于k-d樹算法）的Bloom過(guò)濾器的混合系統(tǒng)。
[0062] 現(xiàn)在參見圖3和4,圖3示出了示例捜索系統(tǒng)210的簡(jiǎn)化框圖的框圖。捜索系統(tǒng)210包 括存儲(chǔ)器212,214、特征擴(kuò)展模塊216、散列運(yùn)算器220和匹配捜索單元218。存儲(chǔ)器212存儲(chǔ) 數(shù)據(jù)點(diǎn)的集合S。特征擴(kuò)展模塊216從存儲(chǔ)器212獲得數(shù)據(jù)點(diǎn)的集合并應(yīng)用特征擴(kuò)展操作，W 生成擴(kuò)展集合S'。散列運(yùn)算器220使用散列函數(shù)的集合來(lái)生成二進(jìn)制字符串（通過(guò)將散列函 數(shù)應(yīng)用于擴(kuò)展集合S'的元素）。散列運(yùn)算器輸出二進(jìn)制字符串B，然后可將二進(jìn)制字符串B存 儲(chǔ)在存儲(chǔ)器214中。
[0063] 匹配捜索單元218接收查詢X。然后，像散列運(yùn)算器220中所使用的那樣，匹配捜索 單元21則尋散列函數(shù)的相同集合應(yīng)用于查詢X。匹配捜索單元218然后將X的散列值與二進(jìn)制 字符串B進(jìn)行比較，W嘗試在擴(kuò)展集合S'中標(biāo)識(shí)針對(duì)查詢X的匹配。結(jié)果示為f (X)。
[0064] 圖4W流程圖的形式示出了示例捜索過(guò)程300,該示例捜索過(guò)程300使用Bloom過(guò)濾 器來(lái)降低針對(duì)擴(kuò)展集合的存儲(chǔ)要求。如操作302所示，確定闊值誤差5。在操作304中，初始化 擴(kuò)展集合S'，并首先將其填充WS中的所有元素。然后，在操作306中，針對(duì)S中的一個(gè)元素， 確定包含元素V的鄰域V(S),使得V(S)中的每個(gè)元素V滿足條件d(v，s)含5。在操作308中，落 入鄰域V(S)中的所有元素V被添加到擴(kuò)展集合S'。如操作310所示，針對(duì)S中的所有S重復(fù)操 作306和308。一旦"擴(kuò)展"了所有s，則如操作312所示，將散列函數(shù)的集合應(yīng)用于擴(kuò)展集合s' 的每個(gè)元素，W生成二進(jìn)制字符串B。然后，在操作313中，將二進(jìn)制字符串B存儲(chǔ)在存儲(chǔ)器 中。
[0065] 在操作314中，接收查詢X。在操作316中，將散列函數(shù)應(yīng)用到查詢，并將結(jié)果與二進(jìn) 制字符串B進(jìn)行比較，W評(píng)估是否很有可能存在針對(duì)擴(kuò)展集合S'中的查詢X的匹配（由于對(duì) 散列函數(shù)的依賴，出走出現(xiàn)假陽(yáng)結(jié)果的可能性）。在操作118中，輸出捜索結(jié)果，例如f(x)。捜 索結(jié)果的輸出可包括輸出是否找到匹配（即f (X))和/或來(lái)自S'的匹配元素、或指向該元素 的指針。
[0066] 概要表示
[0067] 在一些實(shí)現(xiàn)中，二進(jìn)制字符串B可被稱為"概要表示"。例如，在基于特征的圖像視 覺(jué)捜索情況中，可通過(guò)特征的集合來(lái)表示圖像。為了確定特征X是否在圖像中（或在從圖像 提取的S特征的集合中）出現(xiàn)，可隨圖像附帶特征的"概要表示"。在一種實(shí)施例中，概要表示 是從圖像提取的比特流編碼特征的一部分。在另一實(shí)施例中，概要表示是表示數(shù)據(jù)庫(kù)中的 圖像的單獨(dú)記錄。
[0068] 在一種示例中，該概要表示采用長(zhǎng)度為m的二進(jìn)制數(shù)組的形式，其通過(guò)如Bloom過(guò) 濾器中的k個(gè)散列函數(shù)填充W提取特征，并且在使用近似匹配和特征擴(kuò)展的情況中具有最 大可允許距離8。假定S'中的特征總數(shù)是n(擴(kuò)展后），選擇參數(shù)(m，k)，W滿足假陽(yáng)不超過(guò)特 定闊值e運(yùn)一要求，該要求可被表達(dá)為：
[0069] (l-e_kn/m)k< ￡.
[0070] 在一種實(shí)施例中，k可被設(shè)置為&二^ln 2,在關(guān)于Bloom過(guò)濾器的文獻(xiàn)中運(yùn)是合 理的。針對(duì)圖像捜索，可從有限集(例如{2,4,8，16}或{2,3,4,5,6,7,8，...，16})中選擇4， W滿足目標(biāo)闊值e。
[0071] 為了提供說(shuō)明性示例，假定在圖像X中標(biāo)識(shí)了4個(gè)特征{so,SI,S2}。我們使用長(zhǎng)度m 為16的二進(jìn)制數(shù)組B和k = 3個(gè)散列函數(shù)來(lái)如下所示存儲(chǔ)所述4個(gè)特征：
[0072] 步驟1:將B初始化成全為零。
[0073]
[0074] 步驟2:假定ho(SO) = 1、hi (SO) = 2、h2 (SO) = 7。將B中的相應(yīng)位置設(shè)置為1，W存儲(chǔ) SOo
[0075]
[0076] 步驟3 :假定ho(Si) = 9、hi (Si) = 2、h2 (Si) = D。將B中的相應(yīng)位置設(shè)置為1，W存儲(chǔ) Slo
[0077]
[007引步驟4:假定ho(S2) = F、hi (S2) = 7、h2 (S2) = 0。將B中的相應(yīng)位置設(shè)置為1，W存儲(chǔ) Slo
[0079]
[0080] 所得到的數(shù)組B = IllO OOOl OlOO OlOl是X的概要表示。
[0081] 為了檢查X中是否存在特征t，可W簡(jiǎn)單地計(jì)算ho(t)、hi(t)和h2(t)。如果B[ho (0]、8比1(*)]和8比2(0]都被設(shè)為1，則乂中存在*(有可能是假陽(yáng)）；否則并非如此(確定 的)。
[0082] 在一些方案中，對(duì)N個(gè)(N含2)圖片的獨(dú)立概要表示進(jìn)行組合(N個(gè)二進(jìn)制向量的二 進(jìn)制OR)，W提供對(duì)整個(gè)集合的單個(gè)概要表示。具體地，令^ = 1X0, ...，XN-l}表示N個(gè)圖片的 集合(擴(kuò)展后），并且令Bi表示基于XiQ = O,...，N-1)的Bloom過(guò)濾器的概要表示?；谙嗤?Bloom過(guò)濾器的S'的概要表示是：
[0083]
[0084] 注意到，運(yùn)里的求和對(duì)于標(biāo)準(zhǔn)二進(jìn)制Bloom過(guò)濾器是邏輯性的，針對(duì)計(jì)數(shù)Bloom過(guò) 濾器或其變形是算術(shù)性的。該特征在特征/描述符數(shù)據(jù)庫(kù)是動(dòng)態(tài)的應(yīng)用中尤其有用。例如， 當(dāng)將具有概要表示Bn的新圖像添加到集合S'時(shí)，可通過(guò)簡(jiǎn)單地將Bn添加 Bs到來(lái)高效地更新 Bso
[0085] 分層假陽(yáng)
[0086] 在W上示例中，參數(shù)(m，k)針對(duì)所有n個(gè)特征保持恒定，從而假陽(yáng)概率也是恒定的。 然而，在一些實(shí)現(xiàn)中，可能能夠提供至少兩種假陽(yáng)概率。在一些情況中，可允許的假陽(yáng)概率 針對(duì)不同的特征可W不同。例如，假定先驗(yàn)地知道特征X的概率Px,并且Px不是常量。令Ex表 示測(cè)試X的假陽(yáng)概率。則對(duì)于具有高Px的特征，可要求Ex相對(duì)較低;對(duì)于具有低Px的特征，Ex 可相對(duì)較高。換言之，將維持PxEx的平衡。
[0087] 另一可能場(chǎng)景是，特征被分類到變化重要性的多于一個(gè)不同類別中。例如，從圖片 的背景部分提取的一些特征可被認(rèn)為不如從圖片的前景部分提取的特征重要。在運(yùn)種情況 中，可能想要針對(duì)不同類別中的特征具有不同的假陽(yáng)概率。
[008引在一種實(shí)施例中，使用兩個(gè)級(jí)聯(lián)Bloom過(guò)濾器來(lái)實(shí)現(xiàn)兩種不同的假陽(yáng)概率。令EO表 示小于1的第一假陽(yáng)概率，并且令e康示第二假陽(yáng)概率，其中El是小于EO的正實(shí)數(shù)。假定將要 存儲(chǔ)n個(gè)特征，其中前n/2個(gè)特征預(yù)計(jì)具有假陽(yáng)概率e0,而后n/2個(gè)特征預(yù)計(jì)具有假陽(yáng)概率ei。 W下兩種示例Bloom過(guò)濾器可用來(lái)實(shí)現(xiàn)期望的假陽(yáng)概率。
[0089] 具有參數(shù)(mo,ko)的第一Bloom過(guò)濾器被設(shè)計(jì)為實(shí)現(xiàn)60, W使得：
[0090]
[0091] (m〇，ko)的一種可能選擇是
[0092] 具有參數(shù)(虹，ki)的第二Bloom過(guò)濾器被設(shè)計(jì)為實(shí)現(xiàn)ei，W使得：
[0093]
[0094] (mi，ki)的一種可能選擇是
[OOM]注意到，所有n個(gè)特征存儲(chǔ)在第一Bloom過(guò)濾器中，并且只有后n/2的重要特征存儲(chǔ) 在第二B loom過(guò)濾器中。
[0096] 在測(cè)試步驟中，首先針對(duì)第一Bloom過(guò)濾器檢查特征X。如果確定第一Bloom過(guò)濾器 中存在特征X，并且想要知道特征是否是重要特征，則針對(duì)第二Bloom過(guò)濾器檢查X。從而，針 對(duì)所述n/2重要特征的假陽(yáng)概率是第一 Bloom過(guò)濾器的假陽(yáng)概率和第二Bloom過(guò)濾器的假陽(yáng) 概率的乘積，即Elo
[0097] 在上例中，可將重要特征的子集一般化為小于n的任意正整數(shù)