數(shù)碼相機定位數(shù)學建模論文1

1、高教社杯全國大學生數(shù)學建模競賽承 諾 書我們仔細閱讀了中國大學生數(shù)學建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從a/b/c/d中選擇一項填寫）： a 我們的參賽報名號為（如果賽區(qū)設置報名號的

2、話）： 20002028 所屬學校（請?zhí)顚懲暾娜?中南大學 參賽隊員 (打印并簽名) ：1. 2. 3. 指導教師或指導教師組負責人 (打印并簽名)： 日期： 2008 年 9 月 22 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：數(shù)碼相機定位摘 要對于問題一，我們建立了兩個模型，求當坐標系原點取在該相機的光學中心時，靶標上圓的圓心在該相機像平面的像坐標。一個是橢圓最小二乘法擬合模型（模型一），這個模型中我們利用了網(wǎng)格紙選點算法和matlab軟件函數(shù)取點算法兩種算法，這兩個算法均是通過從像平面中選取六個點的坐標值，代入利用最小二乘法建立的方程組（9）式中，求得了擬合橢圓方程的參數(shù)，然

3、后通過式（2）、式（3）的轉換公式得到橢圓中心的坐標；另一個模型是直線逼近模型(模型二)，將相片轉換為tiff格式后直接調用軟件matlab6.0中的imread函數(shù)，取得相片中的若干個橢圓區(qū)域，然后分別在不同區(qū)域內(nèi)用兩條水平線和兩條豎直線去與橢圓相切，求出相切交點的坐標，由橢圓對稱性可知，兩條過對稱切點的直線會交于橢圓中心，則橢圓的中心坐標可以表示成.問題二是在問題一的基礎上進行求解，將相關數(shù)據(jù)代入模型中得出了橢圓最小二乘法擬合模型和直線逼近模型的解，結果分別見表4和表9。問題三，在模型一和模型二中，由于包含誤差較大樣本點在內(nèi)的所有樣本點都參與運算，所以會對橢圓擬合的最后結果產(chǎn)生偏差。針對這

4、種情況，采用隨機理論的思想，先隨機選取6個點擬合橢圓，然后計算與此橢圓匹配的所有樣本點個數(shù)。重復此過程一定次數(shù)（一般選取100200次），匹配樣本點多的橢圓即為最優(yōu)橢圓，由此構造了一種快速準確剔除誤差較大樣本點的改進橢圓擬合隨機化算法，并通過實例驗證了算法的精度和穩(wěn)定性，其中精度檢驗時最大誤差為0.73%，穩(wěn)定性檢驗時最大誤差為3.7%，說明模型能夠有效地處理包含有較大比例誤差點的樣本空間，擬合出具有高精度的橢圓，并且該算法的速度能夠滿足實時性的要求。問題四屬于雙目定位問題范疇，可由常規(guī)的攝像機標定問題進行反推求解，常規(guī)的攝像機標定問題是將像素坐標系信息（如相片）轉換到世界坐標系信息（如實物）

5、的三維坐標，而這里是將世界坐標系信息（靶標上的圓心）向像素坐標系信息轉換，從而測定兩部固定的數(shù)碼相機的相對位置。我們通過已知的實物和相片信息然后利用空間坐標系轉換公式求解得到由旋轉距陣和自由平移向量組成的兩部相機的外部參數(shù)矩陣，進而得到兩部數(shù)碼相機的光心坐標變換模型（見式（29），由此即得兩相機的相對位置。關鍵詞：最小二乘法、圖像網(wǎng)格處理、取色器、標定、旋轉距陣一 問題重述數(shù)碼相機定位在交通監(jiān)管（電子警察）等方面有廣泛的應用。所謂數(shù)碼相機定位是指用數(shù)碼相機攝制物體的相片確定物體表面某些特征點的位置。最常用的定位方法是雙目定位，即用兩部相機來定位。對物體上一個特征點，用兩部固定于不同位置的相機攝

6、得物體的像，分別獲得該點在兩部相機像平面上的坐標。只要知道兩部相機精確的相對位置，就可用幾何的方法得到該特征點在固定一部相機的坐標系中的坐標，即確定了特征點的位置。于是對雙目定位，精確地確定兩部相機的相對位置就是關鍵，這一過程稱為系統(tǒng)標定。標定的一種做法是：在一塊平板上畫若干個點， 同時用這兩部相機照相，分別得到這些點在它們像平面上的像點，利用這兩組像點的幾何關系就可以得到這兩部相機的相對位置。然而，無論在物平面或像平面上我們都無法直接得到?jīng)]有幾何尺寸的“點”。實際的做法是在物平面上畫若干個圓（稱為靶標），它們的圓心就是幾何的點了。而它們的像一般會變形，如圖1所示，所以必須從靶標上的這些圓的像

7、中把圓心的像精確地找到，標定就可實現(xiàn)。 圖 1 靶標上圓的像我們設計靶標如下，取1個邊長為的正方形，分別以四個頂點（對應為a、c、d、e）為圓心，為半徑作圓。以ac邊上距離a點處的b為圓心，為半徑作圓，如圖2所示。圖 2 靶標示意圖用一位置固定的數(shù)碼相機攝得其像，如圖3所示。圖3 靶標的像要求：（1） 建立數(shù)學模型和算法以確定靶標上圓的圓心在該相機像平面的像坐標, 這里坐標系原點取在該相機的光學中心，x-y平面平行于像平面；（2） 對由圖2、圖3分別給出的靶標及其像，計算靶標上圓的圓心在像平面上的像坐標, 該相機的像距（即光學中心到像平面的距離）是1577個像素單位(1毫米約為3.78個像素單

8、位)，相機分辨率為；（3） 設計一種方法檢驗你們的模型，并對方法的精度和穩(wěn)定性進行討論；（4） 建立用此靶標給出兩部固定相機相對位置的數(shù)學模型和方法。二 問題分析2.1問題背景分析數(shù)碼相機在計算機視覺中的應用逐漸普及和深入，在應用中數(shù)碼相機的標定是相當重要的。計算機視覺是一門新興的學科。隨著計算機硬件、軟件、圖像采集、處理技術的迅速發(fā)展，計算機視覺的理論和技術已被廣泛地應用于醫(yī)學圖像處理、機器人技術、文字識別、工業(yè)檢側、軍事偵察、地理勘察和現(xiàn)場測量等。計算機視覺在多種測量中的應用是一種定量分析系統(tǒng)，有確定的精度要求。一般運用于現(xiàn)場不可到達、現(xiàn)場復雜不便直接測量、保留現(xiàn)場狀態(tài)以便復測、補測和事后

9、重構現(xiàn)場等場合。通常人們把攝像機和膠片相機作為獲取原始圖像的主要設備，隨著數(shù)碼相機的出現(xiàn)和發(fā)展，在許多場合人們已逐漸采用數(shù)碼相機作為主要的圖像采集設備。這主要是由于數(shù)碼相機有如下幾個特點:有較多像素的ccu;可以根據(jù)測量的需要選擇不同的像素大小;可直接與計算機進行通訊;可選定多種焦距進行定焦距拍攝。上述特點，給圖像采集和圖像處理帶來了許多方便之處。在應用計算機視覺的測量系統(tǒng)中，無論是采用攝像機還是數(shù)碼相機作為原始圖像的采集設備，都必須進行系統(tǒng)標定。系統(tǒng)標定是應用計算機視覺進行現(xiàn)場測量和圖像處理的第一步，也是關鍵的一步。標定矩陣的精度直接影響到最終的測量精度。國內(nèi)外許多學者對此做了大量的研究，提

10、出了多種利用攝像機作為輸入設備的標定方法。2.2問題要求分析對于問題一，題目要求確定靶標上圓的圓心在該相機像平面的像坐標，這里坐標原點是取在該相機的光學中心，我們?nèi)粢怨廨S所在直線為軸，則所求靶標上圓的圓心在相機像平面上的縱坐標是相同的（在這里為該相機的像距，是一個固定值），所以只需求各和坐標即可，由實物與像之間的關系，在只考慮幾乎理想狀態(tài)下，我們可以試著確定相片上橢圓的中心坐標，并且認為靶標上圓的圓心在該相機像平面的像坐標應該是和橢圓的中心坐標很接近。問題二是在問題一建立的模型上賦予具體的數(shù)值進行求解，因此只需將題目中所給數(shù)據(jù)代入第一問的模型中即可有解決，值得注意的是在理想光學成像系統(tǒng)下焦距即

11、是像距。問題三是要求設計一種方法來給第一問設計的模型進行檢驗，同時還要求這種方法具有一定的精度和穩(wěn)定性，并能計算出來。問題的難點在于這里沒有一個標準又不能進行真實模擬，鑒于此，我們決定采用計算機仿真的思想，即給出一個確定解同時產(chǎn)生一系列隨機數(shù)，用該方法求得的一組值來達到分析的目的。對于問題四，由于這是屬于雙目定位問題。根據(jù)相機成像的原理，我們利用空間坐標系的相互轉換就應該可以實現(xiàn)在靶標給出的條件下確定兩部固定相機的相對位置。三 模型的建立及求解數(shù)碼相機圖像拍攝實際上是一個光學成像過程，而且光學成像的理論模型是針孔模型。我們將此成像過程分為3個步驟、隸屬于4個坐標系。這四個坐標系分別為: (1)

12、世界坐標系根據(jù)自然環(huán)境所選定的坐標系，坐標值用表示。 (2)圖像坐標系坐標原點在圖像平面的中心，x軸、y軸分別為平行于圖像平面的兩條垂直邊，坐標值用表示。 (3)像素坐標系坐標原點在圖像平面的左上角，x軸、y軸分別平行于圖像坐標系的x軸和y軸，坐標值用來表示，且為離散的整數(shù)值。 (4)光心坐標系以相機的光心為坐標原點，x軸、y軸分別平行于圖像坐標系的x軸和y軸，相機的光軸為z軸，坐標值用表示。由實物到相片的形成經(jīng)過了3個步驟，是分別將世界坐標系中的信息轉換到光心坐標系，再由光心坐標系轉換到圖像坐標系，最后由圖像坐標系轉換到像素坐標系。3.1 問題一的模型3.1.1基本假設1) 考慮最小二乘法的

13、要求，我們假設從圖像坐標系中選取的點的坐標值的隨機誤差服從正態(tài)分布。2) 圖3中的橢圓都是標準橢圓，不存在畸變等因素，屬于理想圖形。3) 相片沒有損壞，保存完好，圖像清晰3.1.2符號說明橢圓中心位置橢圓長軸和短軸a橢圓長軸的轉角3.1.3模型的準備1）橢圓的表示方法 在二維平面坐標系中，橢圓一般可以用2種形式來表示。一種是利用圓錐曲線方程的代數(shù)形式表示，即: （1） 另外一種更直觀的方式是用平面坐標系的幾何參數(shù)表示，即橢圓中心位置 ，長軸和短軸，長軸的轉角a。二維平面里的任意橢圓都可以用這5個參數(shù)唯一確定， 參數(shù)的幾何意義如圖4所示。圖4 二維平面橢圓的表示兩種表示形式的參數(shù)可用式(2)式(

14、6)轉換。 (2) (3) (4) (5) (6)2）坐標轉換分析根據(jù)這種轉換關系，可以先選取圖3中橢圓中點的坐標值，求得等式（1）中參數(shù)，再通過轉換，得到圖3中各個橢圓中點在像素坐標系中的坐標值，最后由坐標平移求出各個橢圓中心在圖像坐標系的的坐標值。位置如圖5圖5 圖像坐標系下各個點位置圖3.1.4模型的建立建立兩個模型，模型一中用到最小二乘法來擬合橢圓函數(shù)，將得到的擬合函數(shù)的參數(shù)，用式（2）、（3）轉換得到題中要求坐標系情況下橢圓圓心坐標。在選取點擬合過程中，考慮對精度的要求，給出在精度要求不高情況下，用網(wǎng)格取點法和高精度要求中的計算機像素取點法兩個算法；模型二中根據(jù)標準橢圓對稱性，用ma

15、tlab軟件中圖像處理庫函數(shù)建立模型，提高運行速度。模型一橢圓最小二乘法擬合最小二乘法橢圓擬合是較常用的橢圓擬合方法。最小二乘法是在隨機誤差為正態(tài)分布時，由最大似然法推出的一個最優(yōu)估計技術， 它可使測量誤差的平方和最小， 因此也被視為從一組測量值中求出一組未知量的最可信賴的方法之一. 最小二乘技術主要是尋找參數(shù)集合，從而最小化數(shù)據(jù)點與橢圓之間的距離度量. 這里的距離度量常見的有幾何距離和代數(shù)距離。幾何距離表示某點到曲線最近點的距離。平面內(nèi)某點到方程所代表曲線的代數(shù)距離就是。以下是以代數(shù)距離作為距離度量介紹最小二乘法。假設一般形式的橢圓方程如式(1)所示， 為了避免零解，并將解的任何整數(shù)倍都視為

16、對同一橢圓的表述，對參數(shù)做一些限制，約束條件設。顯然，直接應用上述方程對邊緣檢測后的離散點進行最小二乘處理， 就可以得到方程中的各系數(shù)，也即，求目標函數(shù) （7）的最小值來確定各系數(shù)。再由極值原理，欲值為最小，必有 （8）由此建立如下數(shù)學規(guī)劃模型： 我們用matlab 6.0編程并用消元法求解上述線性方程組，最終求得方程系數(shù)的值。模型二 直線逼近模型每個橢圓用兩條水平直線和兩條豎直直線逼近橢圓，使得四條直線與橢圓相切，得出每個橢圓水平、豎直邊界點。imread函數(shù)對處理的函數(shù)有特定的要求，在用imread函數(shù)調用圖片之前，先用photoshop軟件將圖3圖片格式轉換為tiff格式并無任何壓縮限制

17、，然后用imread函數(shù)取得圖片中橢圓區(qū)域。再在圖中劃分出每個橢圓的邊界，如圖6。圖6 橢圓邊界劃分對每個區(qū)域用imread函數(shù)取得的圖片數(shù)據(jù)中，分區(qū)域0hfj,higf,ilkg,dkqn,jemp在每個區(qū)域用水平線和豎直線去與橢圓相切，可以求出相切交點的坐標（以橢圓d為例）如圖7。圖7 橢圓d相切交點位置其中由橢圓對稱性可知，直線與直線交于一點且過橢圓中心，則橢圓中心可以用坐標表示，得到如下數(shù)學模型（在圖像坐標系下）： （10）3.1.5模型的求解模型一的求解模型中首先要解決的問題是得到六個點，用這六個點來算出等式（7）中參數(shù)六個點的值。對于選取這六個點，給出一下兩個算法；1) 網(wǎng)格紙選點

18、算法用一個網(wǎng)格紙放在圖形上面，建立一個坐標系，確定每一個網(wǎng)格對應像素，再取網(wǎng)格頂點正好落在每個橢圓邊界處，當取不到足夠的點時，可以移動網(wǎng)格紙位置，使得足夠多的點落在網(wǎng)格頂點，如圖8所示圖8 網(wǎng)格紙及點選取算法具體實現(xiàn)步驟：step1放置網(wǎng)格紙，使盡可能多的網(wǎng)格頂點落在橢圓邊緣step2根據(jù)相機分辨率，設置網(wǎng)格坐標刻度step3選取6個點的坐標值step4代入式（8）中，得到關于系數(shù)的線性方程組step5用消元法求得每個橢圓對應的值step6通過式（2），（3）求出每個橢圓圓心在下的坐標值step7坐標變換，得到在像素坐標系下橢圓圓心坐標值2）matlab軟件函數(shù)取點算法用photoshop軟件

19、將圖3格式轉換為tiff格式，用matlab圖形工具箱中的imread函數(shù)取得圖片中橢圓區(qū)域，再在圖片區(qū)域找出橢圓邊界上6個點的坐標值，用消元法求出最終結果 算法實現(xiàn)步驟：step1用photoshop軟件將圖3格式轉為tiff格式并無需任何壓縮step2用imread函數(shù)調用轉換后圖片step3從得到的圖片信息中提取出每個橢圓邊界點（代碼見附錄1）step4從每個橢圓邊界點中取出6個點的坐標值（代碼見附錄2）step5用matlab軟件求出式（3）的方程組形式，并用消元法求得系數(shù)值step6通過式（2），（3）和坐標變換，最終得到在像素坐標系下橢圓圓心坐標值注：消元法是以函數(shù)形式給出，代碼見

20、附錄3模型二的求解在imread圖像數(shù)據(jù)中，可以直接得到的值，代入式（10）便得到橢圓d的圓心在圖像坐標系下的坐標。相繼也可以求出靶標上其他橢圓圓心在圖像坐標系下的坐標值。算法具體實現(xiàn)步驟：step1用photoshop軟件將圖3格式轉為tiff格式并無需任何壓縮step2用imread函數(shù)調用轉換后圖片step3將圖片按橢圓位置分塊step4在每一塊中用matlab找出橢圓水平和豎直方向最大值和最小值step5用式（10）求出每個橢圓中心在圖2坐標系下的坐標值step6坐標變換，最終得到在像素坐標系下橢圓圓心坐標值3.1.5 模型的評價對于模型一，首先在圖像坐標系中對圖像進行圖像網(wǎng)格處理，得

21、到每個橢圓上的一些點的坐標值；然后根據(jù)橢圓的表達式，用最小二乘法求出每個橢圓中心在圖像坐標系中對應的坐標值。給出取點的兩種方法：網(wǎng)格取點與計算機函數(shù)取點。其中網(wǎng)格取點算法可用于對結果精度要求不高，或是沒有高清晰攝像設備的情況下，在實際中，這種取點方法能方便快速的得到一些基本的數(shù)據(jù)，給生產(chǎn)工作帶來便利，是一種輔助其他算法的工具，也可以對其他的算法結果正確性做簡單的分析，但這種方法由于精度不高，誤差大；計算機取點算法能精確的取到圖片要求區(qū)域的邊界坐標值，能用取到的精確坐標值進行最小二乘法擬合，利用這種取點算法得到的解精度很高，且當圖形有略微畸變時，可以避開畸變區(qū)域點的選取，最終得到理想的結果，但這

22、種方法需要高清晰度取像設備，不宜在室外作業(yè)，可以在實驗室的條件下做實驗數(shù)據(jù)分析。對于模型二，解決問題的前提是利用橢圓的對稱性，快速的得到橢圓上四個極值點的位置，再結合幾何圖形知識得出最終的結果，在處理具有對稱性的圖形時，能非?？焖俚牡玫骄_解，并且在程序執(zhí)行過程中花去的代價很低，但當圖形有稍微的畸變，就容易產(chǎn)生很大的誤差。模型一和模型二都有各自的適用范圍，可以根據(jù)不同的情況需求選擇不同的模型或算法來解決問題，也可以將不同的模型或算法結合起來解決待解決的問題。3.2 問題二的解答由于問題二中給出了具體的數(shù)值且問題模型并沒有改變，顯然問題二的求解必須是要在問題一模型下進行，所以只需將具體的數(shù)值代入

23、問題一的模型即可。利用matlab6.0的強大數(shù)值計算能力，我們求得了如下解。3.2.1利用模型一中網(wǎng)格取點算法求解這里只考慮用網(wǎng)格選點法，得到從圖3中取得的點的坐標如下表1表1 圖像坐標系取點坐標值橢圓x(mm)y(mm)a 190.204439.6019275.170344.5522375.170354.4526490.204459.4029595.215744.5522695.215754.4526b1105.238444.55222120.272544.55223105.238459.40294110.249861.87805122.778249.50246117.766859.402

24、9c1160.363354.45262160.363359.40293177.903149.50244175.397447.02735165.374747.02736177.903159.4029d1150.3406123.75602145.3293133.65653160.3633123.75604162.8690133.65655160.3633136.13166152.8463123.7560e165.1476133.6565270.1590123.7560375.1703141.0818480.1817138.6067585.1930128.7062682.6873123.7560在m

25、atlab6.0中擬合出每個橢圓方程的參數(shù)值，見表2表2 每個橢圓代數(shù)形式參數(shù)的擬合值 橢圓擬合 系數(shù)坐標中的點a-1.3953-0.3494-99.0371158.7387-0.7314b-1.3677-1.8741-159.2396353.1355-0.5491c-2.1063-3.0887-221.2915686.4699-0.4062d0.2270 1.7202-337.1185405.6205-0.0189e-0.0150 0.2950-148.024181.2751-0.0887由表2擬合的每個橢圓方程的參數(shù)值代入（2）（3），得到各橢圓圓心在圖像坐標系下的坐標如下：表3 圖像坐標

26、系下擬合各個橢圓中心坐標橢圓(mm)abcdex86.9180113.2818167.5217154.027575.0327y56.609552.148053.0060132.0610137.8438表3得到的是在圖像坐標系中的坐標，如圖2，圖片中心相對左上角的坐標為（135.3066，101.4799）(單位為毫米)進行坐標變換，用圖像坐標系下的各個點x坐標值值減去135.4497（mm），得到在像素坐標系下各個點的x值，用101.5873減去在下的各個點y坐標值，得到在像素坐標系下各個點的y值，如表4表4 在像素坐標系下各個點的坐標值橢圓（mm）a(mm)b(mm)c(mm)d(mm)e(

27、mm)x-48.3886-22.024832.215118.7209-60.2739y50.870449.331946.4739-30.5811-32.36393.2.2利用模型一中計算機函數(shù)取點算法求解用函數(shù)在每個橢圓上取出六個點坐標值如表5表5 各點取值x（像素）y（像素）橢圓a128320223641823310229434215353262306284206橢圓b138419223842093461206445422054302356462202橢圓c160623026431763652176460623256232486675202橢圓d15714752606475361251545

28、8247155624816585534橢圓e160422026062043607233460522956042146669232在matlab6.0中擬合出每個橢圓方程的參數(shù)值，見表6表6 每個橢圓代數(shù)形式參數(shù)的擬合值 橢圓擬合 系數(shù)坐標中的點a-2.04070.8922-243.6945340.9528-1.0293b-1.8508-0.2235-470.2341920.9710-2.2089c-0.00330.0010-0.56661.6739-0.0003d-1.0074-0.2193-684.4368815.3615-0.1040e-0.00300.0004-0.57781.6644-

29、0.0011618以一個單位像素作為刻度，圖3中的圖像可以劃分為個單元格，用matlab庫函數(shù)中的imread函數(shù)來取得每個單元格的值，再用問題一中的算法可以取得每個橢圓心坐標值，最后轉換到以光學中心為原點的坐標值，見表7表7 圖像坐標系下各橢圓圓心坐標值a(mm)b(mm)c(mm)d(mm)e(mm)x-50.0000-23.544933.862518.7831-60.1851y51.455049.603245.1058-31.4815-31.21693.2.3利用模型二求解將圖片轉換為tiff圖片格式，用取色器在轉換后圖片上找出橢圓邊界點的rgb值，可以得到表8值表8 tiff格式圖片上

30、rgb值rgb橢圓邊界內(nèi)和橢圓上可取值1515151241414133434344282828522222261212127444橢圓邊界和邊界外可取值12342342342227227227322122122142152152155204204204在表8中，橢圓內(nèi)部的rgb值都為，橢圓外部的rgb值都為，其他的值都分布在橢圓邊界附近。以一個單位像素作為刻度，圖3中的圖像可以劃分為個單元格，用matlab庫函數(shù)中的imread函數(shù)來取得每個單元格的值，再用問題一中的算法可以取得每個橢圓心坐標值，最后轉換到以光學中心為原點的坐標值（代碼見附錄5），見表9表9 光心坐標系下各橢圓圓心坐標值abc

31、dex-50.0000-23.544933.862518.7831-60.1851y51.455049.603245.1058-31.4815-31.21693.3 問題三的解答直接最小二乘法并未考慮各樣本點誤差的差異，它假設樣本數(shù)據(jù)是零均值的，且有共同的協(xié)方差陣，這與實際情況不符，因而導致參數(shù)的有偏估計，算法結果往往并不令人滿意?；谶@種考慮，我們研究了一種改進的橢圓擬合的算法。這個算法主要是用來解決在取得的圖像中有畸變的情況。3.3.1算法建立隨機方法抽取基于最小二乘法和隨機原理， 可得到一種具有較高抗干擾能力的橢圓擬合算法。算法原理如下：1) 在所有樣本點(已編號)中隨機選取6個樣本點；

32、2) 利用最小二乘法求解橢圓參數(shù)；3) 遍歷所有樣本點，求取各個點到已得到的橢圓之間的距離，最小二乘技術主要是尋找參數(shù)集合,從而最小化數(shù)據(jù)點與橢圓之間的距離度量。這里的距離度量常見的有幾何距離和代數(shù)距離。如果小于某個自己定義點閾值，則稱該樣本點為匹配點，在數(shù)組a記錄該樣本點的編號，遍歷完畢求取對于該擬合橢圓的匹配點的總個數(shù)b；4) 比較匹配點總個數(shù)c與匹配點最大值d ，當前者大于后者，將橢圓參數(shù)和記錄匹配點編號的數(shù)組m保存下來，分別拷貝至數(shù)組p和數(shù)組q，最后將b賦值給d；5) 循環(huán)執(zhí)行步驟1) 步驟4)一定次數(shù)(根據(jù)運行時間、需要結果的準確度以及樣本點總個數(shù)適當定義) ，最后在p保存了最優(yōu)橢圓

33、參數(shù)，在數(shù)組q保存了在所有樣本點中匹配點的編號，也就相應的可以得到不匹配點的編號。3.3.2算法說明算法第1)步中隨機選取6個點擬合橢圓，之所以選取6個點是因為在離散數(shù)據(jù)中， 往往5個點不能得到一個橢圓，本文選取6個點，用基于代數(shù)距離的最小二乘法擬合橢圓。之所以隨機選取樣本點進行橢圓擬合是考慮到算法的實時性和準確性。 如果考慮所有的可能性，譬如總樣本空間有300個點，選取6 個不同的樣本點一共有種可能，遍歷所有可能性在時間上是不允許的，而且也不必要。要加速計算，只需選擇其中的一部分子集。在樣本性質并不清楚的情況下，使用隨機方法抽取是一個很好的選擇。算法流程圖如圖9所示。（代碼見附錄6）開始在所

34、有樣本點e隨機選取6個點循環(huán)次數(shù)是否已到利用最小二乘法求解橢圓參數(shù)遍歷所有樣本點判斷點到橢圓的距離是否符合要求得到num_inliers 和 inliers_indexbest_elipse_par=橢圓參數(shù)max_inliers_index=inliers_indexmax_inliers=num_inliers結束num_inliersmax_inliers是否否是圖9 算法流程圖3.3.3算法對問題一模型的檢驗現(xiàn)取題二中的橢圓a作為分析對象(取點代碼見附錄7)，樣本總體上有233個樣本點，則有227個樣本點來計算點到擬合橢圓的距離，遍歷100次。為得到精確的結果，閾值應越小越好，又因為問

35、題二中的圖片上橢圓比較多標準，閾值在這里取為2個像素單位，在matlab中運行代碼，對數(shù)值進行遍歷，最終得到p中保存的最優(yōu)橢圓參數(shù)，見表10表10 p中保存的最優(yōu)橢圓參數(shù)bcdef 數(shù)值-2.54000.9736-204.7289418.6218-6.2642將得到的數(shù)值abcdex-50.0000-23.544933.862518.7831-60.1851y51.455049.603245.1058-31.4815-31.2169通過與問題二的數(shù)值比較發(fā)現(xiàn)，問題一的假設是合理的，且用問題一種建立的模型，對比較標準的圖形可以得到很精確的3.3.4算法評價在直接最小二乘法的情形中，并沒有考慮到畸

36、變給結果帶來的誤差。當給定圖片存在肉眼看不見的畸變或雜質點，如果用直接最小二乘法可能會產(chǎn)生比較小的，或者是不易察覺的誤差，分析但這些誤差可能會在生產(chǎn)工作中慢慢的積累，最終可能產(chǎn)生破壞性的影響。例如在眼睛治療中，需要對眼膜有非常高的精度要求，隨機化方法可以很好的消除因設備、雜質點等帶來的誤差隨機化算法是通過一定量的遍歷來消除畸變、雜質點等影響，得到想要的到的結果，有時這種算法能達到亞像素精度。3.3.5算法精度檢驗1)精度概念分析當給定一個誤差范圍，通過擬合值與真實值之間的比較，得到誤差平法和、方差等統(tǒng)計量來對結果進行檢驗2) 檢驗方法描述a) 給定一個圖形，并知道圖形所有點坐標值、參數(shù)值等；b

37、) 取到每個點的坐標值，并儲存；c) 對每一個圖形上的點用matlab中normrnd函數(shù)生成正態(tài)（高斯）分布的隨機數(shù)，將這個隨機數(shù)加到圖形對應點中，從而得到一個和原圖形有偏差的新圖形；d) 以新圖形上的點坐標作為已知值，用隨機化算法找到最接近原圖形的參數(shù)值e) 用新得到的參數(shù)值與已知參數(shù)值做統(tǒng)計量比較，檢驗隨機化算法擬合精度。3) 檢驗實例假設a,b值擬合誤差超過1%，認為算法不合格，否則，證明此算法在擬合方面有很高的精度a) 給定一標準橢圓，中點在原點，a=50,b=30；b) 取到每個點的值，以1為一個單位，總共有200個點x(i),y(i)(i=1,2,200)；c) 用normrnd

38、（0，0.1）生成400個白噪聲數(shù)值nx(i,1),ny(i,2) (i=1,2,200)，組成一個白噪聲序列，每兩個用來控制一個點在x軸和y軸上移動的值;將對應的點在白噪聲nx,ny的影響下產(chǎn)生新的位置值x1(i),y1(i);d) 將數(shù)據(jù)x1(i),y1(i)用隨機化算法，來求得a1,b1的值；e) 對擬合值a1,b1進行誤差分析其中將(x1(i),y1(i)點和原橢圓畫在一個圖中，如圖10圖10 隨機產(chǎn)生點與原橢圓用隨機化算法計算得a1,b1值分別為50.1205，29.8781重新生成白噪聲序列，再重復進行多次的擬合，最終得到表11中數(shù)據(jù)（代碼見附錄8）表11 擬合值123456789

39、10a150.120549.999850.000050.200149.973149.739150.031749.690250.100049.8973b129.878129.917330.010430.217830.078930.108330.110530.115730.030630.0338分別計算出a1,b1樣本均值有 a1,b1的樣本方差 計算每組數(shù)據(jù)的相對誤差如表12表12 相對誤差12345678910a10.0024 0.0000 0.00000 0.0040 0.0005 0.00520.0006 0.0062 0.0020 0.0021 b10.0041 0.0028 0.000

40、3 0.0073 0.0026 0.0036 0.0037 0.00390.0010 0.0011從先對誤差表中可得a1最大誤差為0.4%，b1最大誤差為0.73%，都沒超過1%，證明此算法有很高的精度。由于產(chǎn)生隨機序列的值可能取到很大，則會出現(xiàn)較大奇異點，使得在其他模型的求解過程中產(chǎn)生很大的誤差，而隨機化算法可以把這些有較大奇異點的地方，通過篩選把奇異點排除在正確解的范圍內(nèi)。能夠有效地處理包含有較大比例誤差點的樣本空間，擬合出具有高精度的橢圓，并且算法的速度能夠滿足實時性的要求。3.3.6算法穩(wěn)定性檢驗1) 穩(wěn)定性概念分析在一組影響變量a的因素中，當某一個因素發(fā)生一個小的變化，會使得變量發(fā)生

41、很大的變化，則變量不穩(wěn)定，如果在一定的范圍內(nèi)，影響因素的變化不能影響變量發(fā)生很大的變化，則這個變量是穩(wěn)定的。在隨機化算法中，主要解決的問題是通過循環(huán)排除畸變或奇異點等等影響，如果模型中出現(xiàn)較大的畸變或出現(xiàn)大的奇異點，而隨機化算法依然能得到擬合效果很好的擬合情況。否則認為隨機化算法穩(wěn)定性不夠。2) 檢驗方法描述1) 給定一個圖形，并指導圖形在坐標系下的所有情況和圖形本身參數(shù)值；2) 給圖形制造一定范圍的畸變或者奇異點；3) 用新圖形的坐標值擬合求解圖形的參數(shù)值；4) 進行參數(shù)檢驗，確定隨機算法是否具有較高的穩(wěn)定性3) 檢驗實例假設c,d值擬合誤差超過5%，認為算法不合格，否則，證明此算法在擬合方

42、面有很高的精度a) 給定一標準橢圓，中點在原點，c=50,d=30；b) 取到每個點的值，以1為一個單位，總共有200個點x(i),y(i)(i=1,2,200)；c) 從y=40出小區(qū)圖形右邊部分，用normrnd（0，0.1）生成400個白噪聲數(shù)值nx(i,1),ny(i,2) (i=1,2,200)，組成一個白噪聲序列，每兩個用來控制一個點在x軸和y軸上移動的值;將對應的點在白噪聲nx,ny的影響下產(chǎn)生新的位置值x1(i),y1(i);d) 將數(shù)據(jù)x1(i),y1(i)用隨機化算法，來求得c1,d1的值；e) 對擬合值a1,b1進行誤差分析用隨機化算法計算，遍歷100次，得a1,b1值分

43、別為48.1205，29.5781重新生成白噪聲序列，再重復進行多次的擬合，最終得到表13中數(shù)據(jù)表13 擬合值12345678910c147.920148.299848.000049.100148.773148.837148.233747.890248.104047.8633d128.878129.735630.710429.217829.578930.207331.110530.214731.041631.0778分別計算出c1,d1樣本均值有 a1,b1的樣本方差 計算每組數(shù)據(jù)的相對誤差如表14表14 相對誤差12345678910a10.0024 0.0000 0.00000 0.004

44、0 0.0005 0.00520.0006 0.0062 0.0020 0.0021 b10.03740.0088 0.0237 0.0261 0.0140 0.0069 0.0370 0.0072 0.03470.0359從先對誤差表中可得a1最大誤差為1.8%，b1最大誤差為3.7%，都為超過5%，證明此算法有很好的穩(wěn)定性。在較大比例誤差點的樣本空間并不會給最終的解的值帶來很大的誤差，依然能保持解的穩(wěn)定性。模型穩(wěn)定性很高。3.3.7算法評價通過以上驗證了算法能夠有效地處理包含有較大比例誤差點的樣本空間，擬合出具有高精度的橢圓，并且算法的速度能夠滿足實時性的要求。能夠有效地處理包含有較大比例

45、誤差點的樣本空間，擬合出具有高精度的橢圓，并且算法的速度能夠滿足實時性的要求。能很好的將引起較大誤差的點排除，并尋找最優(yōu)解或者近優(yōu)解，將誤差控制在很小的范圍內(nèi)。3.4問題四的模型幾何模型3.4.1基本假設設兩部相機的焦距相等，各內(nèi)部參數(shù)也相同兩部數(shù)碼相機的坐標平面是選在光心坐標平面不考慮相機透鏡的畸變，采用較好的光學鏡頭3.4.2符號說明世界坐標系中一空間點的坐標光心坐標系中一空間點的坐標對應圖像坐標系中點的坐標圖像坐標系原點在像素坐標系中的坐標分別是像素坐標系在方向和方向相鄰像素間的距離拍攝相機的焦距旋轉矩陣位移向量3.4.3模型的建立如圖11所示,將物體所在的空間設定為世界坐標系,而相機拍

46、攝的圖像是電荷藕合器件ccd面轉化的,所以,可以認為ccd平面為圖像平面,定義圖像平面為像素坐標系,坐標原點在ccd圖像平面的左上角,u、v軸平行于ccd平面的兩邊,用表示,該坐標值為整數(shù)值.圖11數(shù)碼相機成像坐標系相機拍攝的原理是將坐標系中的物體轉化成像素坐標系中的圖像,轉換過程可以通過建立兩個中間坐標系來實現(xiàn). 3個步驟是分別將世界坐標系中的信息轉換到光心坐標系，再由光心坐標系轉換到圖像坐標系，最后由圖像坐標系轉換到像素坐標系。 （11） 其中是光心坐標系中一空間點p的坐標，是對應圖像坐標系中p點的坐標，f是拍攝相機的焦距。由世界坐標系到光心坐標系的轉換關系為 （12）其中，r為旋轉矩陣，

47、t為位移向量，元素為0的列向量。由圖像坐標系到像素坐標系的轉換關系為 （13）其中，是圖像坐標系原點在像素坐標系中的坐標，分別是像素坐標系在x方向和y方向相鄰像素間的距離。將式（11），（12）代人式（13）我們得到如下模型： （14）可將式（14）簡化，得到最終模型為： （15）為式(4)右邊第1項即相機的內(nèi)部參數(shù)矩陣，為式(14)右邊第2項即相機的外部參數(shù)，為投影矩陣。3.4.4模型的求解上述是針孔模型下的成像系統(tǒng)的基本標定原理，相機的內(nèi)、外參數(shù)都作為未知內(nèi)容進行求解和標定的。在利用數(shù)碼相機進行采集圖像時，可以通過多種途徑求解出數(shù)碼相機的內(nèi)部參數(shù)，然后再根據(jù)逆向投影的方法來求解旋轉矩陣和位移向量?？蓪⑹?15)改寫成 （1） 從式(6)可見內(nèi)部參數(shù)矩陣為滿秩矩陣，令: ，用左乘式(16)兩邊并整理得 (17)令并可以進一步將式（17）改寫成 (18)其中，是世界坐標系中的第點坐標，是由對應點的圖像像素坐標的計算值。將其展開可得到如下3個方程 (19)將式(19)中的第3式分別代入上兩式消去?？傻玫饺缦聝蓚€方程 (20)若在世界坐標系中取個點，將會產(chǎn)生個方程，用矩陣形式寫出這些方程(21)從式(21)可見，若已知世界坐標中個點的坐