• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            風(fēng)雨

            驀然回首 卻在燈火闌珊處
            posts - 3, comments - 2, trackbacks - 0, articles - 0
              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            置頂隨筆

            這個(gè)博客是http://hi.baidu.com/zhanggmcn的補(bǔ)充,主要存放一些代碼相關(guān)的內(nèi)容。

            posted @ 2010-05-04 10:11 zgm 閱讀(120) | 評(píng)論 (0)編輯 收藏

            2010年5月11日

             一、人臉表情識(shí)別技術(shù)目前主要的應(yīng)用領(lǐng)域包括人機(jī)交互、安全、機(jī)器人制造、醫(yī)療、通信和汽車領(lǐng)域等

             二、1971年,心理學(xué)家EkmanFriesen的研究最早提出人類有六種主要情感,每種情感以唯一的表情來反映人的一種獨(dú)特的心理活動(dòng)。這六種情感被稱為基本情感,由憤怒(anger)、高興(happiness)、悲傷 (sadness)、驚訝(surprise)、厭惡(disgust)和恐懼(fear)組成

             人臉面部表情運(yùn)動(dòng)的描述方法---人臉運(yùn)動(dòng)編碼系統(tǒng)FACS (Facial Action Coding System),根據(jù)面部肌肉的類型和運(yùn)動(dòng)特征定義了基本形變單元AUAction Unit),人臉面部的各種表情最終能分解對(duì)應(yīng)到各個(gè)AU上來,分析表情特征信息,就是分析面部AU的變化情況

             FACS有兩個(gè)主要弱點(diǎn)1.運(yùn)動(dòng)單元是純粹的局部化的空間模板;2.沒有時(shí)間描述信息,只是一個(gè)啟發(fā)式信息

            三、人臉表情識(shí)別的過程和方法

            1、表情庫的建立:目前,研究中比較常用的表情庫主要有:美國CMU機(jī)器人研究所和心理學(xué)系共同建立的Cohn-Kanade AU-Coded Facial Expression Image Database(簡稱CKACFEID)人臉表情數(shù)據(jù)庫;日本ATR建立的日本女性表情數(shù)據(jù)庫(JAFFE),它是研究亞洲人表情的重要測(cè)試庫

            2、表情識(shí)別:

            (1)圖像獲取:通過攝像頭等圖像捕捉工具獲取靜態(tài)圖像或動(dòng)態(tài)圖像序列。  

            (2)圖像預(yù)處理:圖像的大小和灰度的歸一化,頭部姿態(tài)的矯正,圖像分割等。

            è目的:改善圖像質(zhì)量,消除噪聲,統(tǒng)一圖像灰度值及尺寸,為后序特征提取和分類識(shí)別打好基礎(chǔ)

            主要工作è人臉表情識(shí)別子區(qū)域的分割以及表情圖像的歸一化處理(尺度歸一和灰度歸一) 

            (3)特征提取:將點(diǎn)陣轉(zhuǎn)化成更高級(jí)別圖像表述如形狀、運(yùn)動(dòng)、顏色、紋理、空間結(jié)構(gòu)等, 在盡可能保證穩(wěn)定性和識(shí)別率的前提下,對(duì)龐大的圖像數(shù)據(jù)進(jìn)行降維處理

            è特征提取的主要方法有:提取幾何特征、統(tǒng)計(jì)特征、頻率域特征和運(yùn)動(dòng)特征等

            1采用幾何特征進(jìn)行特征提取主要是對(duì)人臉表情的顯著特征,如眼睛、眉毛、嘴巴等的位置變化進(jìn)行定位、測(cè)量,確定其大小、距離、形狀及相互比例等特征,進(jìn)行表情識(shí)別

            優(yōu)點(diǎn):減少了輸入數(shù)據(jù)量

            缺點(diǎn):丟失了一些重要的識(shí)別和分類信息,結(jié)果的精確性不高 

            2)基于整體統(tǒng)計(jì)特征的方法主要強(qiáng)調(diào)盡可能多的保留原始人臉表情圖像中的信息,并允許分類器發(fā)現(xiàn)表情圖像中相關(guān)特征,通過對(duì)整幅人臉表情圖像進(jìn)行變換,獲取特征進(jìn)行識(shí)別。

            主要方法:PCAICA(獨(dú)立主元分析)

            PCAè一個(gè)正交維數(shù)空間來說明數(shù)據(jù)變化的主要方向 優(yōu)點(diǎn):具有較好的可重建性 缺點(diǎn):可分性較差

            ICAè可以獲取數(shù)據(jù)的獨(dú)立成份,具有很好的可分性

            基于圖像整體統(tǒng)計(jì)特征的提取方法缺點(diǎn):外來因素的干擾(光照、角度、復(fù)雜背景等)將導(dǎo)致識(shí)別率下降

            3)基于頻率域特征提取: 是將圖像從空間域轉(zhuǎn)換到頻率域提取其特征(較低層次的特征)

             主要方法:Gabor小波變換

             小波變換能夠通過定義不同的核頻率、帶寬和方向對(duì)圖像進(jìn)行多分辨率分析,能有效提取不同方向不同細(xì)節(jié)程度的圖像特征并相對(duì)穩(wěn)定,但作為低層次的特征,不易直接用于匹配和識(shí)別,常與ANN SVM 分類器結(jié)合使用,提高表情識(shí)別的準(zhǔn)確率。 

            4)基于運(yùn)動(dòng)特征的提取:提取動(dòng)態(tài)圖像序列的運(yùn)動(dòng)特征(今后研究的重點(diǎn))

             主要方法:光流法

             光流是指亮度模式引起的表觀運(yùn)動(dòng),是景物中可見點(diǎn)的三維速度矢量在成像平面上的投影,它表示景物表面上的點(diǎn)在圖像中位置的瞬時(shí)變化,同時(shí)光流場攜帶了有關(guān)運(yùn)動(dòng)和結(jié)構(gòu)的豐富信息

             光流模型是處理運(yùn)動(dòng)圖像的有效方法,其基本思想是將運(yùn)動(dòng)圖像函數(shù)f (x, y,t)作為基本函數(shù),根據(jù)圖像強(qiáng)度守恒原理建立光流約束方程,通過求解約束方程,計(jì)算運(yùn)動(dòng)參數(shù)

             優(yōu)點(diǎn):反映了表情變化的實(shí)質(zhì),受光照不均性影響較小

             缺點(diǎn):計(jì)算量大 

            (4)分類判別:包括設(shè)計(jì)和分類決策

            在表情識(shí)別的分類器設(shè)計(jì)和選擇階段,主要有以下方法:用線性分類器、神經(jīng)網(wǎng)絡(luò)分類器、支持向量機(jī)、隱馬爾可夫模型等分類識(shí)別方法

            1)   線性分類器:假設(shè)不同類別的模式空間線性可分,引起可分的主要原因是不同表情之間的差異。

            2) 神經(jīng)網(wǎng)絡(luò)分類器:人工神經(jīng)網(wǎng)絡(luò)(Artificial Neural Network,ANN)是一種模擬人腦神經(jīng)元細(xì)胞的網(wǎng)絡(luò)結(jié)構(gòu),它是由大量簡單的基本元件神經(jīng)元,相互連接成的自適應(yīng)非線性動(dòng)態(tài)系統(tǒng)。將人臉特征的坐標(biāo)位置和其相應(yīng)的灰度值作為神經(jīng)網(wǎng)絡(luò)的輸入,ANN可以提供很難想象的復(fù)雜的類間分界面。

               神經(jīng)網(wǎng)絡(luò)分類器主要有:多層感知器、BP網(wǎng)、RBF網(wǎng)

              缺點(diǎn):需要大量的訓(xùn)練樣本和訓(xùn)練時(shí)間,不能滿足實(shí)時(shí)處理要求

            3) 支持向量機(jī)(SVM)分類算法:泛化能力很強(qiáng)解決小樣本、非線性及高維模式識(shí)別問題方面表新的研究熱點(diǎn)

            基本思想:對(duì)于非線性可分樣本,首先通過非線性變換輸入空間變換到一個(gè)高維空間,然后在這個(gè)新空間中求取最優(yōu)線性分界面。這種非線性變換通過定義適當(dāng)?shù)?/span>內(nèi)積函數(shù)實(shí)現(xiàn),常用的三種內(nèi)積函數(shù)為:多項(xiàng)式內(nèi)積函數(shù)、徑向基內(nèi)積函數(shù)Sigmoid內(nèi)積函數(shù)

            4) 隱馬爾可夫模型(Hidden Markov Models, HMM):特點(diǎn):統(tǒng)計(jì)模型、健壯的數(shù)學(xué)結(jié)構(gòu),適用于動(dòng)態(tài)過程時(shí)間序列建模,具有強(qiáng)大的模式分類能力,理論上可處理任意長度的時(shí)序,應(yīng)用范圍非常廣泛。

            優(yōu)點(diǎn):運(yùn)用HMM方法能夠比較精確的描繪表情的變化本質(zhì)和動(dòng)態(tài)性能

            5) 其他方法:

            基于人臉物理模型的識(shí)別方法,將人臉圖像建模為可變形的3D網(wǎng)格表面,把空間和灰度放在一個(gè)3D空間中同時(shí)考慮。

            基于模型圖像編碼的方法是使用遺傳算法來編碼、識(shí)別與合成各種不同的表情

            四、研究展望

            1)魯棒性有待提高:

            外界因素(主要是頭部偏轉(zhuǎn)光線變化的干擾)

            采用多攝像頭技術(shù)、色彩補(bǔ)償技術(shù)予以解決,有一定效果,但并不理想

            2)表情識(shí)別計(jì)算量有待降低è確保實(shí)時(shí)性的要求

            3)加強(qiáng)多信息技術(shù)的融合

                 面部表情不是唯一的情感表現(xiàn)方式,綜合語音語調(diào)、脈搏、體溫等多方面信息來更準(zhǔn)確地推測(cè)人的內(nèi)心情感,將是表情識(shí)別技術(shù)需要考慮的問題

            posted @ 2010-05-11 10:57 zgm 閱讀(1023) | 評(píng)論 (2)編輯 收藏

            2010年5月4日


            Computing n choose k mod p

            Postby joshi13 » Tue Apr 14, 2009 4:49 am

            Hi all.

            How can we apply the modular multiplicative inverse when calculating

            (n choose k) mod p, where 'p' is a prime number.

            If you could suggest some related problems, it would be very helpful.

            Thanks in advance.


            Re: Computing n choose k mod p

            Postby mf » Tue Apr 14, 2009 10:56 am

            You could use .


            Re: Computing n choose k mod p

            Postby maxdiver » Tue Apr 14, 2009 12:03 pm

            There is another, more "mechanical", but more general, approach. It can be applied to any formula containing factorials over some modulo.

            C_n^k = n! / (k! (n-k)!)
            Let's learn how to compute n! mod p, but factorial without factors p and so on:
            n!* mod p = 1 * 2 * ... * (p-1) * _1_ * (p+1) * (p+2) * ... * (2p-1) * _2_ * (2p+1) * (2p+2) * ... * n.
            We took the usual factorial, but excluded all factors of p (1 instead of p, 2 instead of 2p, and so on).
            I name this 'strange factorial'.

            If n is not very large, we can calculate this simply, then GOTO END_SCARY_MATHS :)
            If p is not large, then GOTO BEGIN_SCARY_MATHS:
            Else - skip the rest of the post :)

            BEGIN_SCARY_MATHS:
            After taking each factor mod p, we get:
            n!* mod p = 1 * 2 * ... * (p-1) * 1 * 2 * ... * (p-1) * 2 * 1 * 2 * ... * n.
            So 'strange factorial' is really several blocks of construction:
            1 * 2 * 3 * ... * (p-1) * i
            where i is a 1-indexed index of block taken again without factors p ('strange index' :) ).
            The last block could be not full. More precisely, there will be floor(n/p) full blocks and some tail (its result we can compute easily, in O(P)).
            The result in each block is multiplication 1 * 2 * ... * (p-1), which is common to all blocks, and multiplication of all 'strange indices' i from 1 to floor(n/p).
            But multiplication of all 'strange indices' is really a 'strange factorial' again, so we can compute it recursively. Note, that in recursive calls n reduces exponentially, so this is rather fast algorithm.

            So... After so much brainfucking maths I must give a code :)
            Code: Select all
            int factmod (int n, int p) {
               long long res = 1;
               while (n > 1) {
                  long long cur = 1;
                  for (int i=2; i<p; ++i)
                     cur = (cur * i) % p;
                  res = (res * powmod (cur, n/p, p)) % p;
                  for (int i=2; i<=n%p; ++i)
                     res = (res * i) % p;
                  n /= p;
               }
               return int (res % p);
            }

            Asymptotic... There are log_p n iterations of while, inside it there O(p) multiplications, and calculation of power, that can be done in O(log n). So asymptotic is O ((log_p n) (p + log n)).
            Unfortunately I didn't check the code on any online judge, but the idea (which was explained by Andrew Stankevich) is surely right.
            END_SCARY_MATHS:

            So, we can now compute this 'strange factorial' modulo p. Because p is prime, and we've excluded all multiples of p, then the result would be different from zero. This means we can compute inverse for them, and compute C_n^k = n!* / (k!* (n-k)!*) (mod p).
            But, of course, before all this, we should check, if p was in the same power in the nominator and denominator of the fraction. If it was indeed in the same power, then we can divide by it, and we get exactly these 'strange factorials'. If the power of p in nominator was greater, then the result will obviously be 0. The last case, when power in denominator is greater than in nominator, is obviously incorrect (the fraction won't be integer).

            P.S. How to compute power of prime p in n! ? Easy formula: n/p + n/(p^2) + n/(p^3) + ...


            (轉(zhuǎn)載:http://acm.uva.es/board/viewtopic.php?f=22&t=42690&sid=25bd8f7f17abec626f2ee065fec3703b

            posted @ 2010-05-04 10:07 zgm 閱讀(566) | 評(píng)論 (0)編輯 收藏

            热久久国产欧美一区二区精品| 中文字幕久久精品| 精品国产一区二区三区久久久狼| 欧美亚洲色综久久精品国产| 久久综合给久久狠狠97色| 粉嫩小泬无遮挡久久久久久| 国内精品伊人久久久久网站| 国产精品久久久久久久久久影院 | 亚洲欧美日韩精品久久| 久久国产午夜精品一区二区三区| 久久久久久曰本AV免费免费| 久久精品草草草| 亚洲第一极品精品无码久久| 88久久精品无码一区二区毛片 | 99热精品久久只有精品| 亚洲国产美女精品久久久久∴| 精品午夜久久福利大片| 欧美日韩精品久久久免费观看| 久久精品国产福利国产秒| 综合人妻久久一区二区精品| 99久久国产亚洲高清观看2024 | 久久精品亚洲男人的天堂| 99久久777色| 久久精品国产99国产精品亚洲| 久久久99精品一区二区| 色综合合久久天天综合绕视看| 久久精品国产久精国产果冻传媒| 日产久久强奸免费的看| 久久精品国产精品亚洲人人| 欧美一区二区精品久久| 成人综合伊人五月婷久久| 亚洲精品乱码久久久久久蜜桃不卡 | 亚洲午夜精品久久久久久浪潮| 国产亚洲成人久久| 国产激情久久久久影院小草 | 蜜臀久久99精品久久久久久| 久久久精品午夜免费不卡| 久久99精品久久久久久久不卡 | 亚洲午夜无码久久久久| 狠狠色综合网站久久久久久久高清| 久久涩综合|