用於自動檢測和標識廣播音頻或視頻節目信號的方法和裝置的製作方法

2023-08-08 20:23:21

專利名稱:用於自動檢測和標識廣播音頻或視頻節目信號的方法和裝置的製作方法
發明背景和內容本發明涉及廣播節目的自動檢測和標識，例如音樂或演講，其通過收音機、電視或網際網路或電視信號被廣播，無論該廣播是以模擬、數字或通過英特網上的數字。通過「廣播」意味著任意有效的內容源，無論是現在已知的還是今後發明的，包括，例如流線型、對等傳輸或下載或流動或者網絡流量的檢測，包括當前內容傳送功率。該系統最初存儲已知的節目，通過數字採樣該節目並把數字採樣流分成大的時間上的片斷(segment)集合。接著處理這些片斷來抽取特定的特徵集合，即片斷的特徵。本發明處理每一組特徵來產生數字代碼，其代表用於已知節目特定片斷的特徵集合。這些代碼和標識節目的存儲數據存在作為系統一部分的資料庫中。一旦完成了一個或更多的存儲，通過從輸入信號中抽取特徵集合，為每一個時間片斷產生輸入到系統中的數字代碼並接著比較檢測的數字代碼和存儲在資料庫中的數字代碼的序列，該系統接著可以檢測並標識廣播信號中寄存節目的存在。在比較處理中應用各種測試標準來減少假陽性(false positive)、假陰性(false negative)的比率並增加對寄存節目的正確檢測。本發明還具有一定的改進並優化了比較處理使得其在相對短的時間裡執行。
圖1媒體廣播監控系統的組成單元。
圖2從一系列的音頻節目幀到節目標識的檢測的檢測算法的數據流程圖解。
圖3模式(pattern)產生模塊的流程圖。
圖4初始頻帶邊界如何導致模式在初始幀特徵和以快速播放的相同音頻節目的特徵之間失配的例子。
圖5如果改變頻帶邊界以獲得在初始音頻節目和以快速和慢速播放的相同音頻節目的幀特徵之間改善匹配的例子。
圖6新的頻帶邊界設置導致音頻檢測算法的穩定，即使在音頻節目中具有+/-2％的速度變化。
圖7DBS操作流程的圖解。
圖8SRR算法的流程圖。
表1-5計算頻帶邊界的例子。
具體實施方式背景本發明涉及一種自動標識大範圍傳播的節目，例如收音機、電視或通過網際網路數位化傳送內容。
在包括廣告客戶的廣播節目中的版權所有者，需要測量他們的節目已經何時以及何地被廣播，以便正確的計算演出版稅，遵守領土限制或者驗證按照日程安排已經播出的特定廣告。傳統的用於監控收音機或者電視的方法已經包括使用人員收聽或者收看並且接著記錄他們所聽到或者看到的，或者可選的，基於收音機和電視臺的廣播記錄。這是工作強度處理，其受限於效率或精確度。本發明的一個目標是使用改善的計算系統以使得該處理完全自動化。如此，音頻或視頻內容記錄在系統，並且接著，在檢測音頻的情況下，來自電視或者其他廣泛傳播音頻內容的其他源的無線電、聲道被輸入到系統中。在(檢測)視頻的情況下，視頻信號從任何一種源被輸入到系統中。通過本發明的方式，對所記錄的節目內容的檢測和標識會自動發生。
現有技術有很多方法用來自動檢測廣播節目。這些技術通常屬於兩種類型的其中之一提示(cue)檢測或模式標識。在Miwa等人申請的美國專利NO1,225,967、Crosby申請的3,845,391，Greenberg申請的4,547,804舉例說明了提示檢測方法。這些技術是基於在發送之前插到節目中嵌入的提示。這些方法在本領域中並沒有得到支持。在音頻中，節目中的提示信號的放置已經限制了該方法的接受，因為，它需要節目所有者和/或廣播公司的合作，這使得該方法是不切實際的。
模式標識方法通常依賴於其內容本身的光譜特徵以產生唯一的標識碼或標記(signature)。這樣，標識內容的技術包括兩個步驟第一個是從已知的內容片斷中抽取標記以提示到資料庫中，以及第二個是從檢測的內容片斷中抽取標記並在資料庫中尋找標記匹配以標識檢測的內容。這樣，優選的方法基於廣播內容本身的特徵來建立該內容獨有的標記。例如，Thomas等人申請的US專利NO.4,739,398公開了一種系統，其採用一種已知的電視節目並為每一個視頻幀在該幀內建立音頻和視頻信號之外的標記代碼。最近，提出了用於網際網路分配內容的類似檢測系統，例如，Ikeyoze等人提出的PCT申請WO01/62004A1。
對於音頻本身，Moon提出的U.S.專利NO.3,919,471公開了一種音頻識別系統，其中只使用了音頻信號，但是它在使用上是受限的，因為它目的在於使有效的時間片段(slice)表示的音頻節目與輸入的廣播信號相關。Moon中公開的匹配方法是非常密集型的計算，因為它依賴於直接的信號相關性。另外，該方法是不受歡迎的，因為發現其在精確性上存在限制，尤其是，如果節目是時間壓縮的或者在檢測之前用其他的方式改變。它還傾向於偽造正確的標識並且如果擴展時間片斷的大小來改善其正確的標識的話，其在計算上又會不經濟。Lert等人提出的U.S.專利NO.4,230,990中提出了一種減輕相關性的計算工作量的方法，其通過把其和第一種編碼方法進行組合來實現在指示節目部分的開始的節目中檢測人工編碼或者一些其他的自然產生的標記，接著在預定數量的時間之後測量特徵標記。該方法也只限於在音頻上應用，其中音頻編碼必須提示到音頻中以建立提示，這樣，降低了它的價值或者需要內容源的合作，或者依賴於表示非常不可信的新的音頻節目開始的自然標記。在Lert等人提出的U.S.專利NO.4,677,466還描述了一種對本發明的改進，其在測量和計算標記之前一直等待直到在信號中發生「可靠的情況」，但是該方法地可靠性受限於採樣時間片斷的大小。Thomas等人提出的U.S.專利NO.4,739,398通過在輸入到本發明的標記產生進程中，隨機的選擇部分信號以採樣，提供了一種數據處理負載問題。
Ellis等人提出的U.S.專利NO.5,436,653和NO.5,612,729公開了一種更複雜的計算唯一標記的方法，其中通過比較指定視頻幀和在先前的視頻幀中的相同測量之間的每一個預定數量的頻帶中能量的改變，得到相應於給定視頻幀的音頻標記。然而，匹配技術依賴於音頻和視頻前面的組合或者使用自然標記，在這種情況下，節目的開始和結束。因此，該方法具有和Lert有關只用於音頻節目的相同的問題。
另外，Blum等人提出的U.S.專利NO.5,918,223公開了一種在音頻節目中使用可聽特徵來為每一個音頻節目創建單一標記值，尤其是，振幅、斜度(即，基頻)、帶寬、低音(即，節奏分析)、亮度(即，節目中頻率響應的形狀)和Mel-頻倒譜(cepstral)係數的組。這些橫跨視頻周期的詳細特徵的集合產生很多不同的結果，並且在實際的廣播環境中並不具有足夠的穩定性。Kenyon等人提出的U.S.專利NO.5,210,820和NO.4,843,562公開了一種數字電路，其在音頻信號中使用包絡(例如，音量)特徵來建立標記。該方法通過使用時間變形技術被設計用於時間壓縮問題。基於音量會有其他的穩定性問題，即在實際環境中使用中存在困難。Well，Maxwell等人提出的U.S.專利NO.20030086341公開了一種系統，其中使用預定數量的數字採樣來建立音頻標記，該數量從音樂的開始點的預定位置開始計數。該方法在用於廣播或者以模擬的形式檢測音頻的情況，或者節目重放已經改變了速度，或者已經應用了原始軌跡的頻率均衡，或者把音頻配音提示到節目片斷中的情況。
本發明描述了一種系統和方法，藉此，可以對已知音頻和視頻節目標識而不依賴於一前一後的視頻信號(在音頻情況下)或者在信號中標識節目的已知時間的標準化的標誌，並且以唯一的和新穎的方式來計算表示音頻節目特性的代碼，而不需要不切實際的計算容量。該系統和方法的優點是精確，快速、穩定的重放速度改變並且能實時執行標識處理，這不依賴於任何的嵌入提示或水印。另外，本發明利用低成本的有效性，高效的計算平臺來執行高速數據搜索方法。
詳細描述A.概述在本發明中具體體現的廣播監控和檢測系統工作在兩個階段中登記和檢測。在登記階段，通過發送節目，已知的節目內容作為數字數據登記在系統中。在這種情況下，一系列的標記，模式矢量以及現有技術中通用的「指紋」或「標記」，作為數據序列記錄存儲在資料庫中，交叉參考它們的節目內容的標識，作為一個組。在第二個階段，未經標識的節目輸入到系統中。這種節目可以包括收音機、電視、網際網路廣播或者任何其他的音頻或視頻節目源，可以是陸地廣播、衛星、網際網路、有線電視或是其他任意的分集媒體，可以是現在已知的或是將來設計的。在監控這種節目時，不停地計算節目的模式矢量(或者任意的其他標記生成技術)。接著所計算的模式矢量用來在資料庫中搜索匹配。當找到並且證實匹配時，系統使用資料庫中的交叉參考標識來提供對內容的標識，該內容是當前播放的內容。在優選實施例中，系統是在計算機上運行的軟體，然而，可以想像到，特定目的的硬體組成單元可以取代部分或者所有的模塊來提高系統的性能和容量。
在優選實施例中，包含中央處理單元的計算機連接到音效卡和接口設備上，在接口設備中給出了音頻節目。在登記階段，CPU從音效卡中取出音頻或視頻數據，計算模式矢量數據，並且接著與定時數據和節目的標識一起，把這些結果存儲在資料庫中，如下面進一步描述的。可選的，數據可以直接從可信的媒體，諸如CD、mp3或者任意其他的包含信號的數字數據源下載。對於非音頻應用，媒體源可以是DVD盤，電影製片廠的原底反轉片、磁帶或任意其他的媒體方式，在其上固定並且存儲有節目。當然，對於一些沒有可靠的有效資源的媒體，音頻或其他節目信號用下面的方式使用。如果系統周期性地檢測未知的節目，但是實際上每次基本都是相同的標記集，其為節目媒體指定任意的標識符並且把數據輸入到資料庫中如同在登記階段已經引入了該節目。一旦在將來確定了節目的特性，那麼資料庫可以被更新以包括作為可信信息的適當信息，同時，使用檢測數據提供節目的所有人，即使節目的特性還不知道也是如此。資料庫，其典型的是通過任意類型的計算機總線或包括SCSI的數據傳輸接口，存儲在連接到計算機的中央處理單元的硬體驅動器上的數據文件。
在檢測階段，CPU從音效卡或音頻卡中取出節目數據，或者從存儲在計算機硬體驅動器的數據文件或者是外部媒體閱讀器中下載。CPU計算模式矢量數據，並且接著，連同定時數據，向存儲在硬體驅動器中的資料庫提交資料庫查詢。該資料庫可以是與計算機中相同的硬體驅動器，或者是通過數字計算機網絡訪問的外部硬體驅動器。當找到匹配數據時，CPU繼續處理數據以確定節目的特性，如下面進一步描述的。CPU接著通過現有技術中已知的各種計算機網絡系統把標識結果發送到將在使用圖片用戶界面的屏幕上播放的遠端位置，或者是將在存儲於硬體驅動器上的另一個數據文件中註冊(的遠端位置)。執行該方法的程序可以存儲在任何類型的計算機可讀媒體中，例如，硬體驅動器、CD-ROM、EEPROM或軟盤並且可以在運行時下載到計算機存儲器中。在視頻的情況下，可以使用模數轉換卡獲得信號，或者數字視頻數據可以直接從數字圖像源中直接檢測出來，例如網際網路或數位電視廣播。
該系統由四個組成單元構成。圖1示出了四個模塊之間的連接關係(1)信號處理過程在前端，(2)模式生成模塊在中間，(3)隨後是資料庫搜索啟動模塊，和(4)節目標識模塊在末端。在登記階段，模式生成模塊的結果，即產生用於已知音頻或視頻內容的標記，存儲在資料庫中並且搜索和模式標識模塊未被使用。
每個模塊的功能在下面作詳細的描述1、聲音獲取(SA)模塊SA模塊，(1)，從聲音檢測電路接收音頻數據並使其可用於其他的模塊。普通技術人員將認識到會有各種產品可以接收模擬音頻或視頻，並且可以把這些信號轉換成數字數據。那些設備可以是任意的數字音頻數據源，包括個人計算機的接口卡，其把模擬音頻轉換成可以由計算機CPU訪問的數字音頻數據，以標準格式輸出數字音頻數據的孤立設備，或具有音頻輸出的數字無線接收機。可選的，數字形式的預檢測信號可以通過典型的數據網絡從連接到系統的存儲設備中存儲。SA模塊有規律地從數字接口設備或數據存儲器中讀取數據，並且把數據讀到數據緩存或存儲器中以便可以讓模式生成模塊訪問。普通技術人員將認識到典型的數字音頻系統每隔一定間隔提供數字消息(word)，稱作採樣率。表示音頻信號的數字命令的序列是數字音頻採樣。本發明把採樣組織成許多時間幀，其由預定數量的採樣組成。時間幀存儲在序列中。可選的，存儲在計算機存儲器(如果系統支持內存分頁或交換，那麼其包括硬體驅動器)中的數據結構，可以用在時間幀非物理地存儲在序列中，但在邏輯上可以在序列中被引用或索引的地方，該序列通過存儲器尋址的方式而被檢測。
在優選實施例中，音頻信號用已知的方式調節，包括低通濾波器。在優選實施例中，信號在SA模塊中以8000Hz的速率採樣。在優選實施例中，16,384個採樣組成單個幀。以這個速率，在採樣信號之前必須被低通濾波以防止混淆。然而，在下遊計算隨著適當的調節而使用較高的採樣速率，如下面解釋的。
在視頻節目的情況中，聲音獲取模塊本質上以類似的方式運作視頻信號作為數字視頻信號而獲得，並在一個視頻幀上通過幀基礎使用已知的方法被轉換到頻域上。下面將通過描述優選實施例，描述本發明當應用到視頻上時內容。然而，系統和所描述的處理可以應用到視頻和音頻上，其中，周期性的從視頻信號中獲得標記或模式矢量。可以參考由Charles A.Poynton、John Wiley Sons提出的「A TechnicalIntroduction to Digital Video」，New York，1996。
2、模式矢量生成(PG)模塊檢測階段的PG移動操作，(2)，獲取存儲的數字音頻或視頻採樣，該採樣被檢測並且由SA模塊存儲。一旦收到採樣幀，PG模塊將計算幀的模式矢量，並且當在檢測階段，以資料庫查詢的形式發送該模式矢量到資料庫搜索模塊。在登記階段，PG模塊計算模式矢量以便其被存儲在資料庫中，與有關已知的音頻或視頻節目的其他相關信息相關。模式矢量的計算在下面作進一步描述。
幀間距對於每一個增加的音頻採樣，能夠開始一個新的幀。也即，當N是幀中的採樣數量時，每一個音頻採樣可以由N個重疊幀構成。在這些重疊幀之間的距離是幀間距。對於模式生成的較短的幀間距減輕了節目開始時間不確定性的問題。當開始時間未知時，較短的幀間距產生更好的結果。在優選實施例中，在音頻節目登記階段，使用大約一個幀的1/4即4000。其他的距離可以用來增加精確度或者減少計算時間和存儲開銷。因此，在優選實施例中，已知音頻節目的資料庫中的第一個幀相應於音頻採樣1到16,384，第二個幀相應於採樣4001到20,384，等等。在檢測階段，幀間距設置成與一個幀的長度相等。這樣，檢測的音頻節目的第一個幀包含採樣1到16,384，第二個幀包含採樣16,385到32,768，等等。
儘管在優選實施例中使用的設置是8000Hz的採樣率、16384個採樣的幀大小，4000的幀間距，但是隨著不同的結果可以使用不同的採樣率。例如，16000Hz的採樣率(優選設置的兩倍)導致32768的幀大小(兩倍的大小但是持續時間相同)，8000的幀間距(在0.5秒時幀間距是相同的)並產生當使用優選的設置時(產生的模式矢量)幾乎相同的模式矢量。唯一更多的改變是為了確定哪些快速傅立葉變換(FFT)係數將包括在每一個用來計算模式矢量的次頻段中。例如，採用優選的設置，(忽略下面解釋的速度補償方案)，頻帶1包括第66個到第92個FFT係數。用上面可選的例子，FFT係數將是第32個到第94個。假設8000Hz的採樣率，因此而調整模式矢量的計算。
在視頻的情況下，模式矢量從每一個視頻幀的二維FFT轉換中獲得。視頻幀可以考慮用類似於在音頻的情況下的採樣。這樣，可以跨越視頻幀來採集垂直和水平FFT係數，以建立用於每一個時間幀的模式矢量，該時間幀由一組視頻幀組成。普通技術人員將認識到可以組合這些方法，因為電視節目的音頻聲道特徵可以與相同節目的視頻信號的特徵相組合來產生模式矢量。
3、資料庫搜索(DBS)模塊一旦收到PG模塊的查詢後，該模塊(3)，將搜索包含已知節目的模式矢量序列的資料庫。如果找到了匹配，那麼模塊會返回一組登記號，否則相應於一組音頻或視頻節目的標識和在匹配發生的那些節目中的時間幀號碼，在這兒稱作節目-標識符(id)和幀-標識符，也稱作幀號碼。如果對資料庫的搜索沒有找到匹配，DBS模塊將分配NO-MATCHED標誌。可以預期到，用於DBS模塊的本發明的方面適用於任意種類的包含信號標記的數據集合，連同使用不同於在模式矢量生成模塊中使用的技術而獲得的標記也都適用。
4、節目檢測和標識(SDI)模塊該模塊(4)，在最近的N個連續的時間幀上監控來自DBS的匹配結果，如下面進一步描述的。在優選實施例中，N設成5，雖然隨著各種結果，也可以使用較大的或者較小的數量。使用兩種方案來確定任意的音頻或視頻節目是否已經確實被檢測。第一個方案是多數投票同意的方案，其確定，在N中匹配模式矢量的每一個線程中，處理有效序列的幀的數量是否通過指定的主要幀塊。第二個方案是幀排序方案，其在每一個潛在的線程之後，並且計算在組成一個有效序列的線程內有多少幀。如果存在這樣的線程，即其中多數的連續幀滿足幀排序需求，那麼認為該節目(無論是音頻或視頻)在該線程中被檢測。任何一個或兩個方案用來抑制假的真正檢測並用來增加正確的檢測。在優選實施例中，兩個方案都可以使用。給定一個被檢測的節目(或者不止一個)，SDI模塊將啟動兩個模式1、標識模式在這種模式下，模塊記錄所檢測節目的所有參考信息，包括標題、歌曲作者、藝術家、記錄標籤、出版社或其他任意在系統的登記階段輸入的信息，連同檢測節目的時間，以及檢測該節目的時間。該信息將被登記在檢測日誌中。2、跟蹤模式在該模式下，如果廣播的每一個新的幀的查詢結果符合下面描述的排序的需要，模塊通過監控跟蹤每一個檢測的節目。在該模式下，該算法被鎖定直到查詢的結果不能與排序需求匹配為止。一旦處在跟蹤模式下，多個檢測標誌，包括整個跟蹤過程和跟蹤中心將被記入日誌。
由PG模塊產生的模式矢量送給DBS模塊以便對資料庫實施匹配搜索。其輸出或者是NO-MATCHED標記，其表示DBS沒有在通過搜索條件的資料庫的幀中；或者是通過搜索條件的程序庫模式的節目-標識符和幀-標識符。
SDI模塊搜集DBS模塊的輸出以檢測是否存在新的音頻節目。如果存在，就標識所檢測的歌曲。圖1是從幀音頻到其檢測後的結果的算法流程圖。只要產生了模式矢量，有關本發明在視頻上的應用，其操作是類似的。可以想像到本發明用於SDI模塊的方面適用於任何類型的包含信號標記的數據集合，即使是使用不同於在模式矢量生成模塊中使用的技術而獲得的標記。
模式矢量生成PG模塊讀取一個信號幀，其最好是由16,384個採樣組成，其採樣速率最好設置成每秒8,000個採樣。這樣幀長度在時間上大約是兩秒。使用在時間上更大或更小的採樣或幀寬度可以得到不同的結果。給定x＝[x1x2…x16384]，該矢量包含一個信號幀，其中每一個xi是第n個音頻採樣值，N元素模式矢量用下面的步驟來計算。在優選實施例中，N等於31。普通技術人員將認識到N的值是任意的，並且可以隨著各種結果減少或增加。例如，漸減的N減少了計算時間和存儲的需求，但是會減少精確度。漸增的N使得結果相反。並且，所給出的方法將假設使用31元素模式矢量，以便簡化本發明的介紹。普通技術人員將認識到當N增加或減少時，根據該目標是增加精確度還是減少計算複雜性，相同的方法都可以運行。
1、x的傅立葉變換用與幀的採樣量相同的點的數量來計算，以便得到頻譜矢量。
X＝[X1X2…X16384] 把FFT頻譜值分到指定寬度的頻帶上，其中在優選的實施例中，該寬度是64Hz。將進一步解釋本發明有關的優選實施例，以便簡化該說明，但不限於本發明要求的範圍。
頻帶#1是從0到64Hz，頻帶#1包含FFT係數X1到X131頻帶#2是從64到128Hz，頻帶#2包含FFT係數X132到X262，等等。
2、計算每一個頻帶的矩心(或重心COG)pk=m=1131mX131k+mm=1131X131k+m]]>在優選實施例中，只使用頻帶2到32，因為頻帶1是包括0Hz的最低的頻帶，其並不經常在FM無線傳輸中使用；並且頻帶32覆蓋直到1800Hz的頻帶，其典型的是用來對音頻指紋編碼的有效帶寬。當然，如果需要的話，可以使用更高的或更低的頻帶。用來說明信號特徵的更高或更低的頻帶內容可以根據經驗來確定。第一步，其中所搜集的用來計算步驟2中的矩心的FFT係數不同於在視頻中的情況。在視頻的情況下，FFT係數必須從複雜的平面中或者在Poynton的文章第23頁中提到的二維空間頻率平面中的位置中選擇出來，其中Poynton的文章通過參考在此結合。這些位置類似於視頻情況中的頻帶。在某種意義上類似於使用預定音頻中的頻帶，在頻域中垂直/水平面上預定的區域可以被定義並且在每一個區域中的FFT係數值用來計算相應於該區域的元素。一旦作出選擇，可以用相同的方式計算其矩心。有利的是，忽略包含幀速率、同步速率、子載波、或行速率的頻率區域。最後的結果基本上等同於音頻情況每一個視頻時間幀將具有一個與存儲在資料庫中的(模式矢量)相關的模式矢量。
在步驟3之後，獲得31元素的矢量c＝[p2p3…p32]＝[c1c2…c32]。在優選實施例中，另一個步驟把c轉換成無符號整數。因為在c中所有的元素在區間(1，131)中是正的，因此使用該無符號格式。另外的有關c的計算是把每一個元素除131歸一化成0和1之間的值，這個131是每一個頻帶中的FFT元素數量0ci=ci1311]]>在優選實施例中，每一個元素接著轉換成無符號化的16位整數格式以方便存儲並進一步處理。為了在下遊減少時間的計算，相對於最小的閾值檢測每一個FFT係數或者ci。設置該下遊的處理以忽略這些元素，例如，通過在下遊設置中不包含這些搜集用於進一步計算的元素的方式。圖3示出了該模塊的流程圖。在優選實施例中，步驟1中的FFT和步驟3中的矩心(COG)的計算典型的使用雙精度浮點指令來實現。
速度補償方案本領域的普通技術人員將認識到為了各種原因，廣播節目經常在普通節目的速度上加速。因此，當檢測的音頻節目可以與在登記階段提供的音頻速度不同時，音頻節目檢測系統是關鍵。為了緩解這個問題，可以修改模式矢量生成公式(a)該修改將具有步驟2中每個頻帶的不同數量的FFT元件(即，帶寬)。
(b)在優選實施例中，在檢測階段，對模式矢量生成公式的修改只應用到輸入的廣播音頻信號，而在音頻節目的登記階段並不應用到模式矢量生成處理中。普通技術人員將認識到，在登記階段，隨著基本相同的結果，用於檢測階段的上述可選的頻帶的使用可以選擇執行。
該修改的詳細細節將在下面描述該公式是根據快速傅立葉變換的縮放特性的。
一首歌曲的時間加速形式是對原作的時間縮放的形式 a＞1，其中a是加速的速率，並且x(t)是在時刻t的檢測的採樣。注意到，對於a＞1，時間軸被「壓縮」。如果歌曲以2％被加速，我們得到a＝1.02。
具有縮放特性的矢量a可以用來調整傅立葉變換的值 這樣，快速重放的頻譜，或歌曲的加速形式(version)被加長。隨著2％的加速速率，在加速後，以沒有任何歌曲加速的100Hz的傅立葉變換頻率成分切換到102Hz。這意味著，如果在檢測的歌曲中存在2％的加速，那麼在步驟2中的帶寬應該根據1.02×64Hz＝65.28Hz進行調整，並且因此，在每一個頻帶中FFT分向量的數量將被調整到131×1.02的四捨五入整數，其等於134。由兩個公式用來計算每一個頻帶中FFT分向量的數量，每一個方法都是基於FFT分向量的原始數量，其等於131。
公式(1)給定加速速率r。
在頻帶#1開始，其包含FFT係數X1到Xz(1)，其中z(1)＝131×(1+r)的四捨五入整數。
(2)迭代計算每一個z(k)＝[z(k-1)+131×(1+r)]的四捨五入整數，其中k＝2到32。頻帶#由Xz(m-i)+1到Xz(m)的FFT係數構成。
(3)計算具有上面計算的新的頻帶劃分的頻帶#2到頻帶#32的矩心(COG)。用相應帶寬中的FFT成分的數量通過劃分每一個矩心(COG)來訓練歸一化。
在圖4和圖5示出了具有和不具有壓縮的不同。圖4示出了導致原作和其加速變量之間的模式失諧的原始帶寬設置。圖5示出了修改的帶寬設置給出非常好的指定模式匹配，加速速率是已知的。穩定的(robust)模式矢量生成公式上述的模式矢量生成公式可以進一步的精確以便提供穩定的匹配。該精確度還可以用來替代先前的公式。除了使頻率軸加長之外，加速的另一個效果是每個頻帶中頻率的邊界線的偏移。該精確度是為了通過延長帶寬補償頻帶邊界的偏移，使得由於重放速度引起的偏移數量只佔帶寬小的比例。因此，不需要修改算法，也即，除了頻帶位置有改變之外，和計算模式矢量一樣來計算矩心。在登記處理期間，使用該修改的頻帶邊界來建立存儲的模式矢量。普通技術人員將認識到幾種可選的方法可以用來計算頻帶寬度，其給出了相同的特性，也即，擴展帶寬使得由於重放速度變量引起的頻偏相對很小，其中由於重放速度改變引起的頻偏百分比是每一個頻帶寬度的小的百分比。此外，可以預料到的是，該技術可以用於任意的計算信號標記的方法中，該方法是基於把FFT係數分成頻帶。下面將以優選實施例的形式來描述一種具有這個影響的計算修改的頻帶分界線的方法。
用來計算新的頻帶邊界線位置的算法在頻域中號碼為k的頻帶的開始和結束索引(index)分別為sk，1，sk，2，也即FFT係數的索引。例如，索引s1，1等於1，並相應於第一個FFT係數是0Hz。假設偏移-帶寬比，其是期望的最大加速百分比除以帶寬的百分比得到的，該偏移不會超過該帶寬。在優選實施例中，假設該值是5％，但也可以使用其他的值以便增加精確度或者減少計算複雜度。
1、從頻帶k＝1開始，其開始位置是s1，1＝1，假設a 2％的加速，該位置從0,02偏移到1.02，在四捨五入之後還是等於1。因為結果的索引必須是整數，因此四捨五入是必須的。假設偏移-帶寬比等於頻帶#1的帶寬的0.4(其是2％的偏移除以5％的帶寬，偏移應該給出的數量)，接著結束位置s1，2＝(1+.02/.05)×s1，1＝1.4，或者在四捨五入之後是1。
2、現在進行計算頻帶#2的兩個位置。開始位置S2，1＝2。給定2％的偏移和5％的偏移-帶寬比，我們得到S2，2＝3。
3、繼續上述步驟直到用完所有的FFT分量。在優選的實施例中，沒有使用這些結果(相應於31.25Hz的較低序號的頻帶Sk，1＜64，和相應於2,686Hz較高序號的頻帶Sk，1＞5500)。
4、當k等於9時，S9，2＝66，並且當k等於10時，S10，1＝67，等等。為了避免由於沿著k的每一個頻帶的帶寬以k指數的增加而導致的溢出，優選的實施例任意的設置S10，1＝66，以便當k迭代達到k＝22時，s22，2＝5298。表1給出了結果列表。
5、在這點上入口的數量只有13個，但最好是共有31個入口(entry)，其中每一個入口相應於模式矢量的指定元素。
第二批頻帶通過採用步驟3中獲得的每一個帶寬的中間獲得。獲得另外的12個頻帶，如表2所示。
6、在這點上有25個頻帶。剩餘的6個頻帶通過組合兩個表中的頻帶獲得。特別的，兩個表中的入口1和2被合併，入口3和4被合併，入口5和6被合併來構成6個之多的入口，如表3所示。
通過上面的組合，31個頻帶的開始和結束位置在表4中給出。
在圖6中示出了有關一幀信號的檢測結果來論證對+/-2％的速度改變的穩定。
加速補償和固定公式的組合如果加速補償被合併，那麼上述用於調整頻帶邊界的兩種方法可以組合。加速和頻譜擴展之間的關係被用來組合該兩種方法。第k個子頻帶，開始和結束位置＝[sk，1，sk，2]，具有穩定的+/-2％的速度改變。每一個值乘以(1+r)，其中r是加速到[sk，1，sk，2]的量，接著用上面描述的四捨五入的方法。在新索引
中的結果，其具有固定的速度改變，偏移到r+/-2％。大體上，在先前的表格4中的新表格中，其中值乘以(1+2％)，並且接著使用相同的四捨五入方法。現在在登記階段使用表4從已知的音頻節目中創建模式矢量，該節目位於資料庫中。在檢測階段使用表5從檢測的輸入廣播創建模式矢量，該廣播在DBS模塊中使用以便在資料庫中找到匹配的數據記錄，如下面進一步描述的。這樣，可以組合兩種方法。以例子的方式，設置r＝0.02(2％)，並處理表4種的每一個頻帶，計算一組新的子頻帶，其具有0到4％的固定速度改變，如表5所示。
用2％的加速補償來獲得表5。在2％加速補償之後的新的31對開始和結束位置添加到表4的列表中。這個結果來自處理廣播的檢測的歌曲。
有效的補償決定了該方法具有從0到4％的穩定的速度變量。普通技術人員將認識到可以使用相同的方法來減少速度變量的影響，其中變量範圍在零附近(above and below)，也即減慢或加速重放。
資料庫搜索(DBS)模塊資料庫搜索模塊從PG模塊中獲得每一個幀的模式矢量併集合一個資料庫查詢以便把該模式矢量與具有相同模式矢量的資料庫記錄相匹配。使用軟體匹配方案來確定在資料庫查詢與存儲在資料庫中的模式矢量之間的匹配。相反，硬體匹配方案對於每一個查詢允許最多一個的匹配入口。軟體匹配方案對於每一個查詢允許不止一個的匹配入口，其中在遇到一個錯誤的閾值時，該匹配位於模式矢量足夠靠近查詢矢量的地方。匹配入口的數量可以是下面的任意一種(i)限於一些最大量，或者(ii)限於在查詢和資料庫入口之間的最大允許差錯。可以使用任何一種方法。軟體匹配方案基於這樣的事實，即在登記階段，節目模式將被過採樣。例如，在優選實施例中，用於登記的幀間距只有其用在檢測階段的1/4。因此，希望如果特定節目的第m個幀是對查詢的最好的匹配幀，那麼其鄰近的幀，例如第(m-1)個幀和第(m+1)個幀，也將具有好的匹配。針對在廣播環境中固有的不同信號條件，軟體匹配和排序方案的組合效果加強了檢測系統的穩定。
當找到匹配時，數據記錄中相應的節目-標識符號和幀號被返回。圖7的流程例示了在DBS模塊中的流程。本領於普通技術人員將認識到，如果用強制手段來實施跨越一個變量的搜索以找到變量的位置是很消耗時間的，該變量在非常大的資料庫中的給定了容差內匹配。為了計算時間問題，執行兩部分搜索。在部分1，範圍搜索方案選擇那些靠近查詢的入口。在部分2，對部分1中潛在的選項精確搜索以便選擇候選集合，其是最靠近查詢的鄰居。
下面詳細描述其步驟1、在檢測階段，從PG模塊產生的模式矢量中組合查詢。
2、執行最近的鄰居搜索算法，其由兩部分組成。部分1執行近似搜索方法。特別的，使用範圍搜索(RS)方案來確定資料庫的哪個入口落在靠近查詢的範圍內。部分2執行精確搜索方法。來自部分1的結果根據他們到查詢的距離而存儲。該搜索算法可以是(i)返回最好的M個結果(根據其到查詢的最短距離)，或者是(ii)返回所有的距離小於一些規定閾值的結果。可以使用任何一種方法。下面更詳細的描述，最相鄰的算法可以用兩種算法替代，這兩種算法在執行搜索時提供較好的計算時間性能。
3、如果存在匹配，那麼輸出節目-標識符號和相應的幀號。如果有多個匹配，輸出所有的節目-標識符號和相應的幀號。
如果沒有匹配，輸出NOMATCH標誌。
範圍搜索需要模式矢量，其在一個容差內匹配，不需要在每一個情況中都完美的匹配。從幾何學的觀點來看，範圍搜索標識了哪組入口包含在多邊形中，在該多邊形中由容差參數來確定其維數。在優選實施例中，多邊形是31維的超立方體。
範圍搜索(RS)公式在優選實施例中，模式矢量是1×31的矢量c＝[c1c2…c31]，其中c是搜索匹配時檢測的模式矢量。頻帶的數量，如上所述，可以多於或少於31，隨著各種結果，可以交替使用增加精確度或計算複雜度。搜索算法將使用31個元素矢量描述，但是普通技術人員將認識到，這些方法適用於任意大小的模式矢量。該模式矢量是M×31矩陣，其中M是存儲在資料庫中的模式矢量總數，31表示在模式矢量中的元素數量。M是可能的大數，如下面所論證的。假設整個資料庫用矩陣A表示。
那些在庫中的模式矩陣被稱作庫模式矩陣。在優選實施例中，每一個矢量z是在登記階段用已知的音頻內容所計算的31個元素的模式矢量，其用來在檢測階段搜索檢測。在檢測階段，標識訓練是為了定位一組庫模式矢量{z_opt}，其被附在容差參數確定的超立方體上。
搜索入口可以表示成任意z*的標識，即 在優選實施例中，使用L1標準，其中||x||＝|x1|+|x2|+…+|x31|是x的L1標準。因此 其中em，n稱作c和zm之間的第n個點差錯。
在整個庫中用RS算法對z*的搜索是基於對點差錯的滿意標準。也即，每一個點差錯少於一些容差，並且在優選實施例中，L1標準少於特定的數量。普通技術人員將認識到對於每一個元素的容差和L1標準可以是相同的也可以是不同的，其改變了搜索的效率。
該容差的確定是基於一些經驗上測量差錯的統計方法。另外，可以認識到，除了第一個序號L1標準外，還可以使用其它測量差錯的方法。搜索問題現在變成一個範圍搜索，其在現有技術的其它地方進行了描述。參考在J.E.Goodman and J.O』Rourke編輯的HANDBOOK OFDISGRETE AND COMPUTATIONAL GEOMETRY，第575-598頁，Boca Raton，NY，1997，CRC Press中的P.K.Agarwal撰寫的範圍搜索，C++代碼也可以從Telos Pr出版，1997，ISBN0387948600 SteveSkiena撰寫的The Algorithm Design Manual中得到。
下面是本方法中用來確定z*的步驟1)設置L等於包含所有庫模式矢量的索引的索引集合L＝{1，2，3，…，M}2)開始於n＝13)計算c的第n個元素到每一個zm，n的第n個元素之間的em，n，其中m的範圍從1到M。
4)更新L到只包括那些模式矢量的索引，其中第n個點差錯小於規定的容錯TnL＝{1≤m≤M，其中em，k＜Tk，1≤k≤n}Tn可以任意設置。在優選實施例中，Tn設成cn值的10％。
5)如果L現在是空集合併且n≤31，那麼退出並給出NO-MATCH標誌。
否則設n＝n+1。
如果n＞31，到步驟6。
否則到步驟3。
6)計算在L到c之間的所有模式矢量之間的差錯em＝||zm-c||；m∈L通過檢查所有的em來確定最好的解決方案並且得到z*。可選的，為了軟體匹配的目的，可以使用兩個標準的其中之一。標準1隻選擇具有小於某些規定閾值emax的差錯的zm。
標準2從L中選擇最好的M個候選者，其中M個候選者是距離第M個差錯大小最小的差錯大小。
一旦確定具有最好的L1匹配的索引m，該索引用來獲得相應於模式矢量zm的數據記錄。該資料庫模塊接著輸出節目-標識符和相應的幀號。
注意到，在第n次迭代開始時，索引集合L包含庫模式矢量的索引，其從m＝1到n-1的點差錯通過容查檢測。在第N次重複開始時，索引集合L是L＝{1≤m≤M，其中em，k＜Tk，k從1到n-1}RS算法的流程如圖8所示。
可以預料，本發明應用於音頻節目的庫大小，M，對於30000首歌曲來說是1千萬的數量級。下面示出了該估計歌曲數量 ＝30,000一般的歌曲長度 ＝204秒(3分24秒)採樣率 ＝每秒8,000個採樣幀大小 ＝16,384個採樣幀間距 ＝4,000個採樣每首歌曲的幀的數量是歌曲長度乘以每秒的採樣個數，減去幀大小，得到的值除以幀間距。在優選實施例中，其大概是＝404個幀具有30,000首歌曲的M＝12,117,120。
關於這個圖，第一次重複需要大約12,000,000次減法和分支表述實施來更新標識集合L。下一次重複將可能會少，但也是以百萬計的。並且存儲器必須留出保存所有在容差檢測中需要的減法結果的中間值的地方。
快速範圍搜索算法對本方法有一定的改善，即減少了為了找到z*而必須執行的減法的量。並且更重要的是，執行時間不會按比例增加到與資料庫大小一樣快，其對於這個大小的資料庫來說是特別重要的。獲得這個改善的性能是以使用大量的存儲器為代價的。然而，普通技術人員將認識到，由於計算機存儲器成本歷史性地在持續減少，其可以合理的交替使用。對RS算法的修改是使用標識而不計算精確的差錯值。該修改在下面做進一步的解釋。
用來獲得檢測的模式矢量和保存在資料庫中的模式矢量之間的最好匹配的改進的搜索方法在這兒稱作快速範圍搜索算法。如前，A是由M行模式矢量構成的庫矩陣 每一行是指定的模式矢量。共有M個模式矢量，並且在優選實施例中，每一個具有31個元素。
步驟1、把A每一列隔離開 2、列中的每一個元素以升序存儲 Z^1,kZ^2,kZ^M,k;]]>k＝1到313、作為排序的結果，每一個元素zm，k映射到
兩個交叉索引表被構造對於每一個k＝1到31，表Rk是
的映射，表Tk是
的映射。
普通技術人員將認識到排序和表格創建可以發生在登記階段之後但先於在檢測階段對任何匹配的搜索。通過在登記階段具有預先分類的模式矢量，該方法以在整個排序矢量上從搜索開始，如下所描述的。
索引搜索給定查詢矢量c＝[c1c2…c31]以及容差矢量T＝[T1T2…T31]，可以使用二元搜索方法來抽取落在容差之內的那些元素的索引。也可以採用其它的搜索方法，但是在log(M)的時間內執行的二元(binary)搜索是優選的。
步驟1、設置k＝1。
2、執行二元搜索以便在經過排序的列k
到M中定位最靠近並且多於或者等於ck-Tk的元素
接著執行二元搜索來定位最靠近並且少於或等於ck+Tk的元素
這樣，在集合{Z^m^,k,m^Lkm^m^Uk}]]>中的所有元素都滿足容差的需要。這樣，在每一個列中兩次使用二元搜索來定位
和
此外，讓
作為包含所有
的索引的索引集合，其滿足容差需求 3、k＝k+1。如果k＞31，那麼轉到下一步。
可選的，處理可以計算哪一列具有最少量的通過檢測的頻帶，並且在下一步中從這個數量的頻帶開始。通過增加經過排序的k值，其中相應的頻帶號從最小到最大，該結果可以比單一的在k上的增加迭代更快速的收斂。
4、重複步驟2和3直到k＝32以便獲得每一對界限{m^Lk,m^Uk},]]>k＝1到31，並且因此確定31個
每一個Pk被單獨獲得。對於每一個k，在每一對{m^Lk,m^Uk},]]>k＝1到31上封裝的所有索引可以迴轉成使用Tk的原始索引。接著，對31組索引執行交集操作。
可選的方式是對第一個兩組索引交集，其結果接著與第三組索引交集，等等，直到最後一組索引已經被交集。這由下面概述執行5、恢復k＝1。
6、在
中找回所有的索引，並存到陣列R中。
7、使用表Tk把在R中的所有索引轉換成原始索引 把所有的索引m存到集合S中。
使用表Rk+1把m轉換成
(這樣，在列1中給出的索引轉換成在列2中的索引的表示)。接著看將要檢測的結果是否落在{m^Lk,m^Uk}]]>的界限內。
應用容差檢測並產生{m^,m^Lk+1m^m^Uk+1}]]>這樣，對於第k個元素，每一個連續的
將是先前的
減去那些沒有通過容差檢測的索引。因此，在步驟6中當k＝30時，
是滿足所有31次容差檢測的索引。
8、k＝k+1。
9、轉到步驟6並且循環直到k＝31。
10、這裡，集合S是在31次交集循環後所有的原始索引。如果S是空的，那麼給出NO-MATCH標誌。否則，對於硬體匹配，我們繼續定位唯一的獲勝者，其例如可能是最接近的候選者。對於軟體匹配，我們繼續獲得所有的有資格的入口。
進一步增加快速RS算法的速度從步驟4開始，而不是從k＝1開始，接著k＝2，接著k＝3，…，直到最後，可以測量在每一列中候選者的總數。在每一列中的所有候選者的總數等於在每一個
中候選者的總數。接著改變k的順序以便第一個檢測的k位於具有最少的候選者的
的地方，等等，直到檢索所有的k。接著對候選者的排序從具有較少數量的候選者的列開始。最後的結果與對以k順序增加的31個索引的相同集合交集的結果相同，但是通過對k以升序重新排列，交集操作的次數被減少並且因此而加快搜索。
搜索增強器(booster)普通技術人員將認識到，當前的搜索方法通常根據頻帶基本原理在頻帶上搜索。使用優選實施例的經驗研究示出了用於該頻帶的在通過過濾的資料庫中的60％到90％的入口搜索結果的初始迭代。假設資料庫具有6000首歌曲標題，並且每首歌具有300個入口，那麼將要搜索的入口總數是1,800,000個。隨著60％的返回，在第一次交集之後，系統必須處理不止一百萬的入口。如果最初的交集大小比較小，那麼用來在單一搜索結果上收斂所需要的交集數量會減少。本發明的另一個目標是，在這兒稱作輔助器，(是因為)用這種方式對搜索進行預處理以減少在開始處理交集中搜索結果的數量。
輔助器使用不同的索引方案以便不止一個頻帶可以集中在一起。通過輔助器的方式，在輔助器中的單一搜索循環等同於在範圍搜索方法中的多個循環，並且因此提高了搜索速度。排序方案用來確定搜索的順序以便最小化用於交集索引的搜索數量。為了建立該排序，在普通的範圍搜索處理期間，計算每一個頻帶中的返回百分比的最大、平均數和標準偏差。這些經驗上的結論用來選擇將使用輔助器處理而集中在一起的頻帶。
輔助器索引方案是對二進位-十進位轉換的擴展，其中二進位的元素的矢量轉換成十進位的整數。這種擴展是簡單的。特別的，如果大小為N的矢量
的基數是M，其中M是整數，那麼轉換公式如下x=[X1X2XN];]]>0≤xk≤M-1dx=n=1MxnMn-1]]>公式(1)注意到公式的轉換具有可逆性。也即，該公式可以用來把
轉換成
因此，該轉換具有一對一的關係，這使得每一個唯一的
可以從唯一的
中計算得到。在優選實施例中，資料庫保存模式矢量，每一個模式矢量按照16-比特的無符號整數來存儲。這意味著每一個模式是可以看作一個編碼矢量，具有M＝65536，並且N＝31，以及可以為每一個模式矢量計算唯一的
模式矢量的多維轉換結果映射到一維空間中。對模式矢量的搜索，該模式矢量在距離查詢矢量y=[y1,y2,,yn]]]>的必需距離內，其在別處稱作容差需求而在這裡稱作間隙需求，用來定位資料庫中的所有入口x=[x1,x2,,xn]]]>以滿足間隙需求|xk-yk|≤Q；k＝1…31。在優選實施例中，編碼是16比特，容差Tk是16比特範圍的10％，這樣使得Q＝10％×64k＝6554。實際上，使用值為6,000。
輔助器把每一個頻帶中的間隙需求(在別處稱作容差需求)映射到相應的
中的間隙需求。雖然，該搜索可以迭代地跳出所有的滿足所有間隙需求的入口，但該方法的主要難點在於多個間隙需求導致
上的多個分裂(disjoint)段。尤其是，在
中用於標識有資格的入口需要31次迭代，其中
轉換成
並且第一次循環是用於頻帶1，第31次循環是用於頻帶31。普通技術人員將認識到，通過改變模式矢量中的頻帶數量，迭代的次數也會改變，但是本發明的宗旨是相同的。
為了避過技術難點，可以採用兩種折中方案第一個，只選擇頻帶的子集包括在輔助器中，即，只對子集中的索引用公式1編碼。第二個，使用較小的基數。第一個折中方案減少了迭代循環的次數，或者尤其是，減少了分裂段的數量，因此就CPU的實際速度而言在每一個段上的搜索是可行的。第二個折中方案減少了存儲器的需求量，並且更重要的是，它允許對輔助器的搜索結果硬編碼以便可以在輔助器中更快速地搜索。這個在優選實施例中的處理將在下面詳細描述1、設基數N＝31。
2、從31個頻帶中選擇3個。也可以選擇更多或者更少的。然而，如果相對於M選擇大量的頻帶，那麼輔助器方法會變得更慢並且其有效性會受到更多的限制。如果太少，那麼它不夠精確並且不能加速，因此應該從經驗上確定最佳的數量。
在優選實施例中，N＝31，從31個中選擇3個。這種組合會得到(a)新索引的動態範圍是從0到32767。因此每一個新的索引可以用2個字節來編碼。
(b)搜索結果的硬編碼建立32768個倉庫(bin)倉庫0到倉庫32767。倉庫m保存所有庫模式矢量的索引，該模式矢量的3-頻帶元素在轉換後得到值m。
4、搜索方法(a)給出查詢矢量y=[y1,y2,,yn]]]>(b)選出三個指定頻帶中的元素。
(c)使用公式1把使用三個頻帶的查詢矢量轉換成一個數字。
(d)通過尋找轉換的查詢和變換的庫模式因子之間最接近的匹配值m，收集所有的在三個指定的頻帶中滿足間隙需求的庫矢量的索引。
(e)把(d)中的索引傳遞到輸出並恢復上述在那些索引集合中的逐個頻帶(band-by-band)搜索。
普通技術人員將認識到使用公式1對庫模式矢量的轉換可以在操作之前執行，以便減少運行時間的計算負載。
D、歌曲檢測和標識(SDI)模塊SDI模塊獲得DBS模塊的結果並且接著提供最終的音頻或視頻節目標識認證。SDI模塊包含兩個子程序1、檢測-過濾有關檢測過的歌曲數量的規律性無規則的匹配，其中DBS模塊返回不同的有關連續幀集合的節目-標識符號，是正常的，表示肯定沒有節目正在被檢測。相反，如果一致的返回，其中DBS模塊一直返回相同的有關連續幀集合的歌曲數量，這表明節目被成功檢測。
當檢測到一致返回時，基於「大多數投票規則」的簡單算法被用來阻止不規則的返回。假設DBS模塊輸出用於被檢測的節目或歌曲的第i個幀的特定節目-標識符和幀-標識符。由於無規則的返回，該結果節目-標識符最初將不把其認為是在該幀中有效的節目標識。相反，系統把結果認為是i，i+1，i+2，…，i+2K的鄰近幀(也即，非-重疊幀)，其中在優選實施例中，K被設在2到4之間。如果在這些(2K+1)個幀中沒有主要的獲勝者，那麼該系統將給出歌曲數量＝0以表示在第i個幀中檢測結果為空。如果有獲勝者，即，至少(K+1)個幀與相同的節目-標識符號產生的幀i是鄰近的，那麼該系統將為第i個幀給出檢測的歌曲數量作為這種多數獲勝的節目-標識符號。普通技術人員將認識到，多數投票計算可以是很多種方式，例如，在某些應用於提供更有力的檢測中是有利的，其中多數閾值是大於K+1並且小於或等於2K+1的值，其中2K+1的閾值將指定無異義的投票。這減少了對潛在地更多未檢測的結果成本的錯誤肯定。為了這個目的，多數投票將被限定用來包括這些可選的閾值。為了計算速度，優選實施例使用中部濾波器確定主要投票。在Z被排序之後，在2K+1個號碼的陣列中的中值，Z＝[z1z2…z2K+1]，K＝1，2，…，是第K個入口。例如，如果Z＝[1，99，100]，那麼Z的中值是99。用於這種計算的規則如下所述假設DBS模塊為第n個幀返回節目-標識符#[n]。為了計算用於幀i的中值讓x＝median([#[i] #[i+1]…#[i+2K]])
那麼讓y＝1-median{[sgn(|#[i]-x|)sgn(|#[i+1]-x|)…sgn(|#[i+2K]-x|)]}其中sgn(x)=1x>00x=0-1x0]]>那麼檢測的結果是x倍的y相乘。該公式的主要特徵是其可以在一個關口上執行而不需要循環執行和計數器。
2、節目標識執行音頻或視頻節目使用多數規則進行檢測，如上面所解釋的，那麼下一步將利用附加的認證測試來確定是否存在將被檢測的歌舞的幀同步。尤其是，幀同步測試檢測由DBS模塊輸出的用於每一個第p個幀的幀-標識符號是隨著時間單一增加的，也即，隨著p增加。如果不是，或者如果幀索引是隨機的，那麼檢測宣告無效。下面是整個SDI的逐步(step-by-step)方法。在節目的一部分已經被重複的情況下，例如，在每次可以編輯到節目中的歌曲合唱，另外的基本上相同的而只是具有變化的時間幀的模式矢量將由DBS模塊找到。在這些情況中，系統通過把他們存儲在緩存中並把他們提交給下面解釋的排序檢測，向前傳送這些結果。當開始排序檢測時，這些中間結果的一些將具有時間幀索引，在排序檢測下認為其是無效的，並且接著被忽略。如果存在單一的中間線程，那麼檢測的開始和停止時間被更新。
SDI算法和步驟在檢測了第p個廣播幀之後，讓sp作為具有最多鄰近2K+1個節目-標識符的構造倉庫
這裡，sm，n＝在第m個廣播幀中將要被DBS模塊檢測的第n個節目-標識符。注意Pm是倉庫大小。通常，對於不同的m，Pm是不同的。
相應的，fp是另一個具有相應的幀號碼或者幀索引的構造 其中，fm，n＝sm，n的相應幀索引。
並且，SI＝上一個歌曲或者節目的節目_標識符，其被成功檢測，以便順利的滿足投票檢測和連續測試。建立寄存器以保存該結果直到檢測到新的和不同的歌曲和節目。
步驟1、計算sp的多數投票。
取出sp的第一個倉庫中的每一個節目作為參考。搜索2K個倉庫的剩餘部分來確定在第一個倉庫中的任何節目是否通過多數投票需求。
2、如果wp＝0，p＝p+1。轉到步驟1。
否則，如果是單元素集合(即一個集合裡有一個元素)並且不等於零設SI＝wp。轉到步驟3。
否則，如果具有不止一個的候選者設SI＝wp(具有多個節目匹配的情況)。轉到步驟3。
在wp中的每一個sp，m執行步驟3-7。
3、對於Dp中的每一個sp，m，從fp中相應的幀形成矩陣A
A=1f12f2......2K+1f2K+1]]>其中，ft是fp中第t個倉庫中的sp，m幀。
如果在屬於sp，m中的第t個倉庫中沒有幀，那麼ft＝0。
4、實現對A的壓縮，刪除A中的第q行，其中fq＝0。
5、用下面的步驟通過刪除行來清除AA、從n＝1開始。
B、計算d1＝f1n+1-f1n和d2＝kn+1-kn。在執行步驟5之後，移除所有的不匹配節目-標識符的入口，該步驟只標識那些正確排序的入口。
C、這裡，數量d1是B中兩個檢測幀之間的的幀偏移。該數量也可以轉換成實際的時間偏移通過採樣中的幀間距乘以該值和通過每秒的採樣個數除該值。數量d2是兩個廣播幀之間的幀偏移。d是兩個偏移之比，其表示檢測順序的增長速率。特別的，在優選實施例中，系統期望理想的速率4作為用於d的值。然而，對d的彈性限制是實用的如果[d1∈(4[d2-1]+2，4[d2-1]+6)]，那麼兩個幀是以正確的排序。這樣，對於d2＝1，期望2到6個幀的偏移在兩個鄰近的具有相同節目-標識符的廣播幀之間。如果d2＝2，那麼偏移是從2+4到6+4個幀。因此，除4個幀在範圍上的額外偏移之外，該範圍是相同的。2和6的數值是以理想值4為中心的範圍。代替單一數值的範圍允許偏移有1比特的彈性(變化)而不是固定的。為了更少的靈活性，可以選擇的範圍是從3到5。用相同的方式，該範圍可以是從1到7以更加靈活。到步驟D。
否則，n＝n+1，以便對B中的所有入口排序，如果n＜N，轉到步驟C。
否則，轉到步驟D。
D、返回矩陣C。C中的每一行由滿足排序需求的入口構成。
通過刪除那些不能匹配排序需求的行來壓縮B。另外，注意通過八B的第一個入口作為參考，如果第二個入口不滿足匹配需求，那麼進程會跳到第三個入口來看看其是否和第一個入口都滿足排序需求。如果第二個入口滿足需求，那麼第二個入口變成第三個入口的參考。
這兒，再次強制進行多數投票需求。
如果C中入口的數量不滿足多數投票需求，那麼入口sp，m沒有資格進行進一步的測試，返回到步驟3來獲取Dp中的下一個入口。
否則，繼續執行步驟6。
再次使用多數投票測試，因為即使在步驟5中多數投票通過了，在用排序規則需求清理結果之後，多數投票測試也可能失敗。如果修改的多數投票通過，那麼新的節目或者歌曲已經被正確的檢測，否則，就不存在檢測。
6、讓s＝C中入口的數量(即，行數)。
如果s＜K，轉到步驟9。
否則繼續執行回歸分析A、讓C1＝[C11C21…Cs1]T和C2＝[C12C22…Cs2]T分別作為C的第一和第二列，其中上標T表示矩陣轉置。構造下面的矩陣用來回歸分析。回歸分析用來計算幀-標識符號碼排序的線性測量D=n=1sCn12n=1sCn1n=1sCn1S]]>E=n=1sCn12Cn2n=1sCn2]]>B、計算斜度和截距
C、還計算C的相關係數r。
7、如果[r＞0.9並且slope≥2並且slope≤6]，那麼有關入口sp，m的線程已經通過了所有的測試並且對於跟蹤模式是有效入口。把入口sp，m和相應的線程存儲到稱作Final_List的寄存器中。
否則，放棄入口sp，m。
繼續對中Dp的下一個入口測試。
8、進入跟蹤模式。每一個Final_List中的線程將被集體或者單獨的跟蹤。
9、開始跟蹤模式A、創建小資料庫用於跟蹤i、在集體跟蹤模式中，小數據塊包含所有的Final_List中的合格入口的模式矢量。
ii、在單獨跟蹤模式中，用於每一個指定入口Final_List的只包含模式矢量的指定資料庫為其入口而建立。
B、如果跟蹤模式＝集體跟蹤，i、p＝p+1。
ii、運行對第(p+1)個廣播幀的檢測。
iii、更新每一個線程的順序。通過觀察該線程是否滿足排序需求來監控每一個線程的指標。
iv、返回步驟i繼續跟蹤，是否存在至少一個滿足排序需求的線程。
否則，退出跟蹤。
如果跟蹤模式＝單獨跟蹤，那麼為每一個線程使用指定的資料庫以用於跟蹤。步驟與集體跟蹤的步驟一致。
這裡的排序需求與其在步驟5c中使用的步驟一樣。也即，我們期望對於新的廣播幀的檢測的幀標識符是以單一的增加方式，並且在優選實施例中，在廣播的連續幀之間的增加量是在2到6之間。
如果對於任意的將被跟蹤的線程，相對於先前的幀，新的廣播不滿足排序需求，那麼執行容差策略。也即，每一個跟蹤可以有最多Q次的失敗，其中Q＝0，1，2，…如果Q＝0，那麼在不滿足排序需求中沒有容差。
C、在跟蹤模式結束之後，檢查每一個線程的指標。該具有最高分數的線程是Final_List中的優勝者。
i、該分數可以根據線程中的每一個幀與廣播中的相應幀之間的差錯計算；或者根據線程的持續時間來計算。或者同時根據兩者來計算。在我們的優選實施例中，持續時間作為每一個線程的跟蹤分數。跟蹤周期中持續時間最長的就是獲勝的線程。
D、如果在步驟2中有多個節目將被記錄，通過獲勝的線程的節目-標識符來校正該記錄。
10、等待新的第p個來自廣播的幀，返回到步驟1。
普通技術人員將認識到，在步驟6中用於檢測連續幀-標識符的線性而使用的值可以被改變或者使得檢測更加容易或者使得檢測更加難。當與未檢測的相比較，增加或降低正確標識的數量時，這使控制該結果是否增加假陽性或抑制假陽性。
雖然已經詳細的描述並解釋了本發明，但是可以清楚地理解上述僅僅是為了解釋和舉例，並且不是用來限制的。可以理解對本發明在單個實施例的上下文中所描述的用於明確的各種特徵，也可以用於對單個實施例的組合中。相反的，在單個實施例的上下文中描寫的本發明的各種為了簡潔的特徵可以用來單獨地使用或者以任意適當的方式組合使用。可以理解，在附錄中描述的特殊實施例，其目的是為了提供本發明的非常詳細的內容而不是用來限定的。可以理解，如果需要的話，本發明的任何的軟體部件可以以ROM(只讀存儲器)的形式來實現或者存儲在任何類型的計算機可讀媒體中，包括CD-ROM，磁性媒體，或者作為存儲在計算機存儲器的數字數據文件被傳輸。如果需要的話，軟體單元通常可以使用常規技術以硬體的形式實現。
本發明的精神和範圍僅僅由所附的權利要求
書來限制。
表1
表2
表3
表4在穩定模式的產生中31個頻帶的開始和結束位置
表5
權利要求
1.一種由數位訊號處理系統執行的方法，其產生有關已知信號的標記，該標記包括一組至少有一個元素的數值，並且對應於至少的信號時間幀，這種已知信號由標識索引來標識並且這種時間幀由時間幀索引來標識，包括把至少一個信號的時間幀轉換到頻域上，使得對於這樣的時間幀來說，具有預先確定數量的以至少一個預定寬度的頻帶分組的頻率幅度值；為每一個頻帶計算一個單獨的數值，其等於預定的在頻帶內分組的頻率幅度值函數；在計算機資料庫中存儲與其相應的時間幀索引和標識索引相關的標記。
2.根據權利要求
1所述的方法，其中所述的預先確定包括其中之一(i)線性組合，(ii)二次函數，(iii)矩心，(iv)方差，或者(v)第n個排序矩，其中n是預定的數字。
3.根據權利要求
2所述的方法，還包括在相應的頻帶中，用預定數量的頻率幅度值分割的函數結果。
4.根據權利要求
1所述的方法，其中所述函數是線性組合，其中每一組線性組合的係數基本上等於在由預定常數分割的頻帶範圍內的頻率幅度值的按序索引。
5.根據權利要求
1所述的方法，其中所述預定頻帶的數量在10和100之間。
6.根據權利要求
1所述的方法，其中所述頻帶佔用大約0Hz和近似等於和低於4000Hz的範圍。
7.根據權利要求
4所述的方法，其中所述預定的常數基本上等於相應頻帶中頻率幅度值的總和。
8.根據權利要求
7所述的方法，還包括在相應頻帶中用預定數量的頻率幅度值分割的函數結果。
9.根據權利要求
1所述的方法，其中所述頻帶的寬度設成基本上大於由已知信號的重放速度的預定最大變化量產生的頻率幅度偏移量，這種將被測量的偏移位於頻帶的上邊界或下邊界。
10.根據權利要求
9所述的方法，其中所述頻帶的上邊界等於下邊界加上一個數值，該數值等於最相關的重放速度變量值乘以下邊界乘以常數的絕對值，其中所述常數的範圍在1和100之間。
11.根據權利要求
10所述的方法，其中所述常數在10和50之間。
12.根據權利要求
9所述的方法，其中所述對於每一個頻帶，頻帶的上邊界基本上等於頻帶的下邊界乘以一加預定值的和。
13.根據權利要求
10所述的方法，其中所述預定的數值基本上在0和近似10之間。
14.一種由信號處理系統執行的方法，其用來確定連續時間幀持續時間的預定數量的一部分的檢測信號是否是基本上與來自多個已知信號的部分至少一個已知信號相同的信號，多個已知信號的每一部分包含多個連續時間幀的持續時間並且已知信號的每個時間幀具有標識索引和時間幀索引，包括為至少一個已知信號的至少一個時間幀，計算第一個標記，其包括從在時間幀期間檢測的預定數量的頻率幅度值中分離出來的一組序號；在計算機數據塊中存儲各個第一個標記，其具有相應的信號標識索引和所述已知信號的實際開始的時間幀的鄰近時間位置；為檢測的信號的至少一個時間幀計算第二個標記，其包括從在時間幀期間檢測的頻率數值的預定字中分離出來的一組數字；從存儲的第一標記集合中選擇第一標記，這些第一標記與第二標記滿足預定的匹配標準，其中所述這種選擇作為檢測信號中的每一個新的時間幀的到達結果而重複發生。
15.根據權利要求
14所述的方法，其中所述第一個標記和第二個標記被計算並用權利要求
1、2或9所述的方法存儲。
16.根據權利要求
14所述的方法，其中所述預定匹配標準包括計算一組差值的絕對值，該差值是每一個包括第一標記的號碼集合的按序成員和每一個這種元的對應於包括第二標記的號碼集合的按序成員之間的差；計算絕對值的和；以及確定該和是否產生小於預定值的絕對值。
17.根據權利要求
14所述的方法，其中所述預定的匹配標準包括計算一組差值的絕對值，該差值是每一個包括第一標記的號碼集合的按序成員和每一個這種元的對應於包括第二標記的號碼集合的按序成員之間的差；計算絕對值集合的總和；以及確定該和是否是所有檢測的第一標記的最小和。
18.根據權利要求
14所述的方法，其中所述預定的匹配標準包括用下面組之一計算差值(i)第一標記到第二標記的近似矢量間距；(ii)第一標記和第二標記之間的近似L-1標準；(iii)在第一標記中的任一成員和其相應的在第二標記中的成員之間的近似最大差值；(iv)在第一標記中的任一成員和其相應的在第二標記中的按序成員之間的近似最小差值；(v)在第一標記中的所有成員和他們在第二標記中的相應成員之間近似平均差值。
19.根據權利要求
14所述的方法，還包括步驟確定第一標記的成員是否滿足預定的匹配標準並具有相同的標識索引，該索引等於或者大於K+1和2K+1之間的並包括這兩個值的數字，其中所述K被估計，使得2K+1等於時間幀的預定數量。
20.根據權利要求
14所述的方法，其中所述匹配標準包括與被檢測信號匹配時間幀的時間幀索引值相比，確定相應於與相同的標識索引匹配的第一標記匹配的時間幀索引值增加是否基本沒有變化。
21.根據權利要求
14所述的方法，其中所述匹配標準包括確定相應於與相同的標識索引匹配的第一標記匹配的時間幀索引值是否基本上是與被檢測信號的匹配時間幀的時間幀索引值線性相關。
22.根據權利要求
14所述的方法，其中所述匹配標準包括計算在相應於與相同標識索引匹配的第一標記的時間幀索引值與被檢測信號的匹配時間幀的時間幀索引值之間的近似回歸分析。
23.根據權利要求
22所述的方法，其中所述確定包括測試相關的係數是否大於或近似等於5。
24.根據權利要求
23所述的方法，其中所述確定包括測試線性斜度是否在近似2到6並且包括2和6的範圍內。
25.根據權利要求
14所述的方法，其中所述被檢測信號的時間幀索引和匹配已知信號被周期性跟蹤以確定至少兩個時間幀的順序，被檢測信號的時間幀索引與匹配的已知信號的時間幀索引的增加而近似一致的增加。
26.一種由信號處理系統執行的方法，其用來確定連續時間幀持續時間的預定數量的一部分的檢測信號是否是基本上與大部分來自已知信號的部分至少一個已知信號相同的信號，多個已知信號的每一部分包含多個連續時間幀的持續時間並且已知信號的每個時間幀具有標識索引和時間幀索引，包括為至少一個已知信號的至少一個時間幀，計算第一個標記，其包括從在時間幀期間檢測的預定數量的頻率幅度值中分離出來的一組序號；在計算機數據塊中存儲每一個標記，其具有相應的已知標識索引和所述已知信號的實際開始的時間幀的鄰近時間位置；為檢測的信號的至少一個時間幀計算第二個標記，其包括從在時間幀期間檢測的頻率幅度值的預定數量中分離出來的一組數字；從存儲的第一標記集合中選擇第一標記，這些第一標記與第二標記滿足預定的匹配標準；在至少一個數據結構中存儲時間幀索引和相應於匹配第一標記的標識索引；從數據結構中刪除那些時間幀索引和相應的標識索引，其中所述在列表中少於K+1個入口具有相同的標識索引，其中所述K被計算使得2K+1等於組成部分被檢測信號的預定的時間幀數量；從列表中刪除那些時間幀索引和標識索引，其中不能確定第一標記的時間幀索引是基本同步於被檢測信號的時間幀索引而增加。
27.一種由包括搜索資料庫的信號處理系統執行的方法，其包括一組至少n個第一標記，其具有相應的標識索引和時間幀索引，其中所述每一個第一標記表示在時間幀期間已知信號的頻率成分，尋找所有第一標記和第二標記的搜索滿足預定的匹配標準，其中所述第二標記表示在時間幀期間被檢測信號的頻率分量，包括在計算機存儲器中存儲第一數據陣列，其包括所有的第一標記，由此在第一數據陣列中的第n行是第n個第一標記的成員集合；對於在第一數據陣列中的至少一列，在計算機存儲器中進行排序，列元素或者以升序或者以降序排列；在計算機存儲器中對另外的數據陣列進行存儲，其中所述在第二數據陣列中的一個元素對應第一數據陣列中的一列，並且第二數據陣列中的一個元素值對照索引到在排序步驟之前產生的第一數據陣列的相應元素；用第二標記進行搜索以找到第二標記和第一數據陣列的行之間的最好匹配；通過使用第二數據陣列的對照索引並把它應用到匹配行中，來恢復任一匹配的第一標記的標識索引和時間幀索引。
28.根據權利要求
24所述的方法，其中所述搜索算法是下面搜索算法的其中之一二元搜索、B樹、線性搜索、啟發性樹搜索、深度第一搜索、寬度第一搜索。
29.由具有搜索資料庫的信號處理系統執行的方法，包括至少一個表示信號的第一標記，使用包括第二標記的查詢，其中所述第一和第二標記都是預定元素數量的集合，每一個元素一個號碼，包括對於每一個第一標記，使用預定的計算來計算第一個整數，作為包括每一個第一標記的元素子集的函數；在相應於第一整數值的計算機存儲器位置中存儲一個參考，所述參考對應於在計算第一標記中使用的相應的第一標記；用相同的應用到相應的第二標記子集中的預定算法來計算第二整數；從第二整數中選擇相應於預定差錯函數內的整數值的存儲器位置；確定任意的對應所選存儲器位置的第一標記和它們的標識索引和時間幀索引。
30.根據權利要求
29所述的方法，其中所述預定的計算是標記中至少兩個元素的線性組合。
31.根據權利要求
29所述的方法，其中所述子集具有少於第一標記的5個元素。
32.根據權利要求
29所述的方法，其中所述差錯函數是下面其中之一(i)確定兩個整數值是否在相隔的閾值距離之內；(ii)選擇第一整數，該第一整數是相比所有的其他第一整數距離第二整數最近的。
33.根據權利要求
14所述的方法，其中所述信號是包括未知標識的節目，其沒有找到匹配任何部分的任一已知信號，還包括具有相應標記的時間幀，包括建立任意的具有標識索引的標識符；向那些源自信號的標記分配標識索引；當未知信號被標識時，把任意的標識符用正確的標識替代。
34.根據權利要求
33所述的方法，還包括用預先存在的標識索引替代資料庫中任意的標識索引，該預先存在的標識索引參照標識信號的有效的標識數據。
35.一種包括中央處理單元的機器，數字數據收發機設備和包括任一的機器可讀媒質的數據存儲設備，其中所述機器可讀媒質包含電腦程式，當由機器執行該電腦程式時，其執行權利要求
1-34所述的方法。
36.一種任意類型的機器可讀媒質，其包含電腦程式的數據，當計算機執行這些程序時，其執行權利要求
1-34所述的方法。
專利摘要
本發明涉及對廣播節目的自動檢測和標識，例如通過收音機、電視、網際網路或其他媒質廣播的音樂、演講或視頻。「廣播」意味著任意的有效內容資源，不論是已知的還是今後發明的，其包括流線型、對等傳輸或者網絡流量的檢測。通過在節目期間為許多短時間段的每一個導出數字代碼，以及通過存儲數字代碼的序列和參考節目標識來登記已知的節目。輸入信號的檢測和標識通過類似地從其上抽取出數字代碼，以及通過比較檢測的數字代碼的序列和存儲的序列而進行輸入信號的檢測和標識。提供可以優化存儲節目的正確檢測率的測試標準。其他的在比較處理中優化被用來加快比較進程。
文檔編號H04H60/56GK1997989SQ20058000624
公開日2007年7月11日 申請日期2005年2月16日
發明者C·關 申請人:媒介嚮導有限公司導出引文BiBTeX, EndNote, RefMan