[發(fā)明專利]基于拓?fù)潢P(guān)系的復(fù)雜序列圖形匹配系統(tǒng)及其實現(xiàn)方法

無效

• 申請?zhí)枺?/td>: 201010193054.6
• 申請日: 2010-06-03
• 公開（公告）號: CN101894274A
• 公開（公告）日: 2010-11-24
• 發(fā)明（設(shè)計）人: 張寶印;沈?qū)W如
• 申請（專利權(quán)）人: 江蘇如意通動漫產(chǎn)業(yè)有限公司
• 主分類號: G06K9/64
• 分類號: G06K9/64
• 代理公司: 南京天華專利代理有限責(zé)任公司 32218
• 代理人: 徐冬濤

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)字圖形圖像處理以及數(shù)字娛樂領(lǐng)域，尤其是一種基于拓?fù)潢P(guān)系的復(fù)雜序列圖形匹配方法。

背景技術(shù)

目前，序列圖形圖像的匹配技術(shù)是建立圖形之間內(nèi)在關(guān)系的關(guān)鍵技術(shù)，對于復(fù)雜圖形還涉及分層技術(shù)。這些技術(shù)是實現(xiàn)目標(biāo)自動匹配、拓?fù)潢P(guān)系自動建立、自動高質(zhì)量上色以及計算機自動內(nèi)插的關(guān)鍵。也是實現(xiàn)二維動畫制作自動化、智能化的核心技術(shù)。

序列圖形圖像配準(zhǔn)問題的研究是數(shù)字視頻、模式識別、計算機視覺以及動畫自動處理的一個主要內(nèi)容，與靜止圖像處理不同的是：序列圖形圖像包含很多幀間瞬時的相關(guān)因素(冗余度)，當(dāng)然也可以把序列圖形圖像當(dāng)作一個一個靜態(tài)圖像序列進行處理，其間處理是相對獨立的，但是，借助于多幀處理技術(shù)所產(chǎn)生的冗余度就可以使得我們?nèi)ラ_發(fā)更有效的算法，大多數(shù)情況下，相對獨立的處理序列圖形圖像的方法，根本無法滿足序列圖形圖像所要求的海量數(shù)據(jù)高速運轉(zhuǎn)等要求，也不能滿足二維動畫向自動化、智能化發(fā)展的需要。

對于序列圖形圖像在動畫領(lǐng)域的應(yīng)用，主要分為兩大類：一是基于柵格數(shù)據(jù)結(jié)構(gòu)的序列圖像配準(zhǔn)；另一個是基于矢量的序列圖形匹配。對于序列圖像配準(zhǔn)，主要方法如光流分析法、相位相關(guān)法、塊匹配法、像素逆歸法、貝斯法等；對于序列圖形匹配，主要方法如輪廓匹配、質(zhì)心匹配以及模式匹配等。

對于基于柵格數(shù)據(jù)結(jié)構(gòu)的序列圖像配準(zhǔn)，在動畫方面的應(yīng)用目前主要集中在圖像變形(Image?Morphing)領(lǐng)域，典型的如加拿大Toon?Boom公司的二維動畫制作系統(tǒng)，就是采用這個技術(shù)進行中間幀的自動內(nèi)插。另外，F(xiàn)lash網(wǎng)絡(luò)動畫制作系統(tǒng)中也應(yīng)用了這個技術(shù)。

對于基于矢量的序列圖形匹配，在動畫方面的應(yīng)用還處在研究初期，主要研究集中在簡單多邊形的相似性判斷上，目前這類研究開展比較廣泛和深入，研究成果頗多。

利用兩個圖形的輪廓形狀進行相似性判斷也是序列圖形配準(zhǔn)的一個重要手段，判斷兩個輪廓形狀是否相似的方法很多，對特殊形狀，如多邊形一般可用計算角或邊的比例的方法；對于規(guī)則的曲線可用參數(shù)判決法進行判斷。

在輪廓匹配方面，主要分為兩大類：一類是基于線的匹配算法，即以多邊形的輪廓為主要特征的匹配。典型算法是Yamamoto提出的基于多邊形輪廓的松弛迭代匹配法。其基本思想是：在多邊形輪廓上按照一定算法選取一些特征點，由這些特征點組成近似多邊形，由近似多邊形進行松弛迭代匹配達到多邊形的匹配；另一類是基于面的匹配算法，即以多邊形的面積和“質(zhì)量”為主要特征進行匹配。這類算法中Montgomery等人提出的方法具有一定的代表性，其基本思想是：將序列圖形中的任意圖形中各個輪廓中心向相鄰圖形作投影，若相鄰圖形上各輪廓中心落在距投影點一定閾值范圍內(nèi)，即認(rèn)為此兩輪廓有匹配關(guān)系。

基于多邊形質(zhì)心的多邊形匹配是充分利用序列圖形的內(nèi)部信息(各多邊形之間相互位置信息)，根據(jù)各多邊形的質(zhì)心位置變化具有連續(xù)性這一規(guī)律，在相鄰幀內(nèi)尋找各多邊形之間的匹配關(guān)系。

模式匹配是研究應(yīng)用最多的匹配方式，是圖形相似性判斷最常用的手段。其主要思想是通過大量的學(xué)習(xí)和訓(xùn)練，提取出某類相似多邊形的一些固定模式，然后利用這些固定模式與未知多邊形進行匹配。

基于柵格數(shù)據(jù)結(jié)構(gòu)的序列圖像配準(zhǔn)由于數(shù)據(jù)結(jié)構(gòu)的限制，對于圖形變化較大，出現(xiàn)遮擋等情況時無法完成配準(zhǔn)工作，基于此方法不能很好的表達序列圖形圖像的內(nèi)在聯(lián)系。

基于輪廓匹配的算法由于理論本身問題存在一定缺陷。第一類算法在多邊形形狀發(fā)生較大變化時，難以達到滿意效果；第二類方法只孤立地依靠輪廓所在局部的位置進行匹配，很可能產(chǎn)生較大的誤差，因此該方法只能達到局部最優(yōu)，而非全局最優(yōu)。另外由于各輪廓尺度大小不同，上述閾值并不是單一的，因而不好確定。

基于質(zhì)心的多邊形匹配由于多邊形產(chǎn)生疊加分割導(dǎo)致多邊形質(zhì)心產(chǎn)生較大變化，多數(shù)情況下難以完成匹配，只適合變化不大的序列圖形。

模式匹配方法由于前提條件是要預(yù)先知道一些固定模式，對于千變?nèi)f化的序列圖形在實用性上都受到一些限制。

拓?fù)潢P(guān)系是指滿足拓?fù)鋷缀螌W(xué)原理的各空間數(shù)據(jù)間的相互關(guān)系。即用結(jié)點、弧段和多邊形所表示的實體之間的鄰接、關(guān)聯(lián)、包含和連通關(guān)系。如：點與點的鄰接關(guān)系、點與面的包含關(guān)系、線與面的相離關(guān)系、面與面的重合關(guān)系等。

拓?fù)潢P(guān)系是指圖形元素之間相互空間上的連接、鄰接關(guān)系并不考慮具體位置.這種拓?fù)潢P(guān)系是由數(shù)字化的點、線、面數(shù)據(jù)形成的以用戶的查詢或應(yīng)用分析要求進行圖形選取、疊合、合并等操作。

發(fā)明內(nèi)容