數(shù)碼相機數(shù)學(xué)建模

2008高教社杯全國大學(xué)生數(shù)學(xué)建模比賽許諾書我們認真閱讀了中國大學(xué)生數(shù)學(xué)建模比賽的比賽規(guī)則.我們完好理解，在比賽開始后參賽隊員不可以以任何方式（包含電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包含指導(dǎo)教師）研究、議論與賽題有關(guān)的問題。我們知道，剽竊他人的成就是違犯比賽規(guī)則的,假如引用他人的成就或其余公然的資料（包含網(wǎng)上查到的資料），一定依據(jù)規(guī)定的參照文件的表述方式在正文引用途和參照文件中明確列出。我們鄭重許諾，嚴格恪守比賽規(guī)則，以保證比賽的公正、公正性。若有違犯比賽規(guī)則的行為，我們將遇到嚴肅辦理。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）：A我們的參賽報名號為（假如賽區(qū)設(shè)置報名號的話）：1324615所屬學(xué)校（請?zhí)顚懲旰玫娜褐袊刭|(zhì)大學(xué)（武漢）參賽隊員(打印并署名)：1.王飛2.李丁3.代永力指導(dǎo)教師或指導(dǎo)教師組負責人(打印并署名)：付麗華日期：2008年9月22日賽區(qū)評閱編號（由賽區(qū)組委會評閱行進行編號）：2008高教社杯全國大學(xué)生數(shù)學(xué)建模比賽編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱行進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國一致編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱行進行編號）：數(shù)碼相機定位綱要相機定位是計算機視覺領(lǐng)域里從二維圖像獲取三維信息的基本要求，是達成很多視覺工作必不行少的步驟。題目利用由五個圓構(gòu)成的靶標模板(圖2)對相機進行標定。關(guān)于給出的相機拍攝的靶標的像(圖3)，本文對其進行了預(yù)辦理：第一應(yīng)用MATLAB軟件對圖3進行去噪，而后利用自行設(shè)計的算法(掃描法)提取去噪后圖形的邊沿(圖8)。事實上，標定就是找到空間坐標系和像平面坐標系之間的互相關(guān)系。而這是由相機成像的幾何模型決定的，其成像參數(shù)包含相機內(nèi)部幾何和光學(xué)特征(內(nèi)部參數(shù))，以及相機世界坐標系的三維地點和方向(外面參數(shù))。求解相機內(nèi)外參數(shù)是解決問題的重點。本文考慮了理想的狀況，即直線的投影還是直線，以及交點的投影仍舊是像的交點。利用圖2中A、B、C、D、E兩兩圓的外公切線的切點與圖3中像的外公切線的切點相對應(yīng)，經(jīng)過最小二乘法求出該相機的內(nèi)、外參數(shù)。而后，利用相機成像原理，將圖2中圓心的坐標Ac、Bc、Cc、Dc、Ec和相機內(nèi)外參數(shù)代入，即可獲取靶標上圓的圓心在該相機像平面的像坐標Ac'、Bc'、Cc'、Dc'、Ec'（見表2）。為了考證該模型，本文利用留一法，用四個圓(共有三組：A、B、D、E；B、C、D、E；A、C、D、E)的切點與對應(yīng)像點求相機內(nèi)外參數(shù)，剩下的一個圓用于做查驗。以第一組為例，詳細過程是：依據(jù)A、B、D、E算出內(nèi)外參數(shù)，而后求出C圓圓心的像的坐標Cc''，并與Ac'、Bc'所確立的直線的距離來查驗方法的精度和穩(wěn)固性。結(jié)果顯示（見本文13-14頁），本文所用方法精度較高，穩(wěn)固性較好。雙目標準時，將雙目系統(tǒng)的坐標系成立在左相機上，把右相機的坐標系有關(guān)于其的旋轉(zhuǎn)和平移參數(shù)利用最小二乘法求出，進而能夠獲取兩部相機的相對地點。重點詞：標定；內(nèi)、外參數(shù)；深度優(yōu)先搜尋；最小二乘法一、問題的提出1．背景目前，交通管理中使用人工監(jiān)控的方式已經(jīng)不合適日趨壯大的交通系統(tǒng)，而有效的電子看管（比如數(shù)碼相機定位）能更有效的管理交通系統(tǒng)運轉(zhuǎn)，于是電子看管漸漸被人們所認識。跟著數(shù)碼相機的普及，數(shù)碼相機定位在交通看管（電子警察）等方面應(yīng)用愈來愈寬泛。所謂數(shù)碼相機定位是指用數(shù)碼相機攝制物體的相片確立物體表面某些特色點的地點。目前，最常用的定位方法是雙目定位，即用兩部相機來進行定位。對物體上一個特色點，用兩部固定于不一樣地點的相機攝得物體的像，分別獲取該點在兩部相機像平面上的坐標。假如知道兩部相機精準的相對地點，便可使用幾何的方法獲取該特色點在固定一部相機的坐標系中的坐標，即確立了特色點的地點。因而可知，關(guān)于雙目定位，精準地確立兩部相機的相對地點就是重點，這一過程稱為系統(tǒng)標定。系統(tǒng)標定方法好多，常用的有張正友平面標定方法、孟胡平面圓標定方法、平行圓標定方法[1]。目前有人提出這樣一種方法：在一塊平板上畫若干個點，同時用這兩部相機照相，分別獲取這些點在它們像平面上的像點，利用這兩組像點的幾何關(guān)系就能夠獲取這兩部相機的相對地點。但是，不論在物平面或像平面上我們都沒法直接獲取沒有幾何尺寸的“點”。實質(zhì)的做法是在物平面上畫若干個圓（稱為靶標），它們的圓心就是幾何的點。而它們的像一般會變形，如圖1所示。問題的重點是，可否從靶標上的這些圓的像中把圓心的像精準地找到，假如能找到，標定便可實現(xiàn)。圖1像的變形表示圖2．問題有人設(shè)計靶標以下，取1個邊長為100mm的正方形，分別以四個極點（對應(yīng)為A、C、D、E）為圓心，12mm為半徑作圓。以AC邊上距離A點30mm處的B為圓心，12mm為半徑作圓，如圖2所示。圖2靶標表示圖用一個地點固定的數(shù)碼相機攝得其像，如圖3所示。圖3靶標的像研究的問題以下：（1）成立數(shù)學(xué)模型和算法以確立靶標上圓的圓心在該相機像平面的像坐標,這里坐標系原點取在該相機的光學(xué)中心，x-y平面平行于像平面；（2）對由圖2、圖3分別給出的靶標及其像，計算靶標上圓的圓心在像平面上的像坐標,該相機的像距（即光學(xué)中心到像平面的距離）是1577個像素單位(1毫米約為3.78個像素單位)，相機分辨率為1024×768；3）設(shè)計一種方法查驗?zāi)Ｐ停Ψ椒ǖ木群头€(wěn)固性進行議論；4）成立用此靶標給出兩部固定相機相對地點的數(shù)學(xué)模型和方法。二、符號定義Owxwywzw世界坐標系Oc數(shù)碼相機透視中心Ocxcyczc數(shù)碼相機坐標系Ou主光軸與像平面的交點Ouxuyu坐標軸分別平行于像素坐標系的坐標軸成立的物理坐標系fx0u0F數(shù)碼相機內(nèi)參矩陣，F(xiàn)0fyv0，fx,fy分別表示在001x方向和y方向上像點的物理坐標到圖像坐標的比率系數(shù)，u0,v0是主光軸與像平面交點的圖像像素坐標RT數(shù)碼相機的外參矩陣,R和T分別為模板相對數(shù)碼相機r1,1r1,2r1,3t1的旋轉(zhuǎn)重量和平移重量，Rr2,1r2,2r2,3,Tt2r3,1r3,2r3,3t3Ac、Bc、Cc、Dc、Ec圓A、B、C、D、E在靶標平面上的圓心Ac'、Bc'、Cc'、Dc'、Ec'圓心Ac、Bc、Cc、Dc、Ec在像平面上對應(yīng)的點三、問題的剖析依據(jù)題意，要找到靶標圓的圓心在像平面中的對應(yīng)點，就應(yīng)當確立數(shù)碼相機的內(nèi)、外參數(shù)，而后利用所獲取的內(nèi)、外參數(shù)來確立靶標平面上圓心在像平面上對應(yīng)點的坐標。只需找尋靶標上的點在像平面上的對應(yīng)點，就能夠利用成像原理求出相機的內(nèi)、外參數(shù)。利用圓及其切線對投影面的特色，即兩圓及其公切線在投影面上的圖形仍保持直線的投影公切于兩圓的投影，且它們在靶標平面上的切點對應(yīng)于投影面上相應(yīng)的切點，利用這一性質(zhì)就能夠找到靶標平面與投影面上部分相對應(yīng)的點，而后就能夠用所成立的模型來求出數(shù)碼相機的內(nèi)、外參數(shù)，進而就找到了靶標平面上點與投影面上點的對應(yīng)關(guān)系，再代入數(shù)據(jù)就能夠求出靶標上圓的圓心在像平面上的像坐標。模型穩(wěn)固性和精度的考證，主假如考察該模型對數(shù)據(jù)變化這一影響下所得結(jié)果的考量。這里，我們將利用留一法，同時用3組數(shù)據(jù)來進行考證。問題4中兩部相機相對地點確實定，主假如兩相機像平面坐標系之間的轉(zhuǎn)變，我們將以左相機為基準，將右相機坐標系一致到左相機上，進而獲取二者相對地點。四、模型假定1．假定數(shù)碼相機成像的原理為針孔相機模型；2．假定相機自己的配置沒有偏差；3．假定數(shù)碼相機成像產(chǎn)生較小的畸變，對結(jié)果影響不大，忽視不計；4．假定像平面中心與光學(xué)中心連線垂直于像平面。五、模型的成立與問題的解（一）模型的成立成立物點（世界坐標）和像點（像坐標）地點對應(yīng)關(guān)系方程。如圖4所示：在模板平面上，分別以兩條正交的直線為xy軸，以靶標上正方形的中心為原點，并按右手準則成立世界坐標系Owxwywzw，而后以數(shù)碼相機透視中心Oc為坐標原點，并使其x軸和y軸分別平行于像面坐標系的x軸和y軸，且方向同樣，z軸為數(shù)碼相機鏡頭的主光軸，按右手準則成立數(shù)碼相機坐標系Ocxcyczc。以像平面上像素坐標值0,0的點為坐標原點O，以水平像元陣列方向為x方向，以垂直像元陣列方向為y方向，成立像素平面坐標系OUV。最后以主光軸與像平面的交點Ou為坐標原點，并使坐標軸分別平行于像素坐標系的坐標軸來成立物理坐標系Ouxuyu，模板平面上Pw的理想成像點為Pu。圖4透視投影模型表示圖假定模型為理想透視模型依據(jù)針孔成像原理，由世界坐標點到理想像素點的齊次變換2,3以下：uxwywsvFRT(1)1

zw1此中，s為照相機坐標向像平面坐標轉(zhuǎn)變的比率系數(shù)，F(xiàn)為數(shù)碼相機內(nèi)參矩陣，T為數(shù)碼相機的外參矩陣，R和T分別為模板相對數(shù)碼相機的旋轉(zhuǎn)重量和平移重量，分別定義以下3,4：fx0u0r1,1r1,2r1,3t1F0fyv0,Rr2,1r2,2r2,3,Tt2(2)001r3,1r3,2r3,3t3此中，fx,fy分別表示在x方向和y方向上像點的相機坐標到物理坐標的比率系數(shù)，u0,v0表示主光軸與像平面交點的圖像坐標。因為世界坐標系的xy軸在模板平面上，所以關(guān)于模板上的點zw0。這款式(1)可重寫為：ufx0u0r1,1r1,2t1xwsv0fyv0r2,1r2,2t2yw(3)1001r3,1r3,2t31消去s即獲取以下理想透視數(shù)學(xué)模型:fxr1,1xwr1,2ywt1u0ur3,2ywt3r3,1xw(4)fyr2,1xwr2,2ywt2v0vr3,1xwr3,2ywt3（二）模型的求解1．圖像辦理題目中給定一幅使用待標定數(shù)碼相機拍攝的圖片（圖3靶標的像），規(guī)格為1024*768大小的位圖。圖3中有5個黑色非正規(guī)圓斑，分別標號為A、B、C、D、E，如圖5所示。黑色非正規(guī)圓斑四周為暗灰色，與圓斑顏色相差很大。使用MATLAB數(shù)學(xué)軟件讀入圖片后，將圖片轉(zhuǎn)變?yōu)?024*768的0-1矩陣，圖中黑色部分標志為0，非黑色部分標志為1。這樣，將圖片轉(zhuǎn)變?yōu)橐粋€失散化的矩陣，并用Morlet小波進行去噪辦理，去噪結(jié)果如圖5所示。圖5黑斑標號圖2．邊沿提取邊沿提取就是提取圖片中特色地區(qū)的界限，該處指提取圖5中黑斑的界限。邊沿提取算法好多，MATLAB軟件中有邊沿提取功能，但成效其實不理想。因為黑斑的特色，本文設(shè)計新的算法進行邊沿提取，稱為掃描法（算法實現(xiàn)C程序碼見附錄一）。掃描法的主要原理是：分兩次掃描，第一次按行掃描，第二次按列掃描。按行掃描時，對每一行從左往右遍歷，假如第I個點到第J個點全為黑色點，且第I-1、J+1點不為黑色，則標志第I點和第J點，其余點不標志。按列掃描與按行掃描方法同樣。按行按列掃描完后，被標志的點即為邊沿點。圖6單行像素掃描前表示圖圖6表示一行像素點，黑球表示黑色點，白球表示不為黑色的點。用按行掃描掃描圖6，從左往右遍歷，可獲取兩段黑色點段，分別為36、911，標志點3、6、9、11，其余點不標志。保存下來的邊沿點如圖7所示：圖7單行像素掃描后表示圖利用掃描法對圖5進行辦理，獲取成效圖如圖8。圖8對圖5進行邊沿提取的成效圖經(jīng)過上邊算法，獲取黑斑邊沿矩陣后，再對該矩陣使用深度優(yōu)先搜尋將5個黑斑邊沿分別出來，儲存各自的邊沿點，并將5個黑斑邊沿標號（見圖8）。3．計算機模擬求切點對圖8中隨意兩邊沿曲線的外公切線，其余點都在該直線的同一側(cè)，利用該特色，經(jīng)過計算機模擬來求兩邊沿曲線的公切線及其切點。詳細的模擬算法：對兩個邊沿曲線，以A、B為例，在曲線A上任取一點a，曲線B上任取一點b，作直線L，而后窮舉A和B上的其余點，看能否在該直線的同側(cè)，假如在同側(cè)，既可以為該直線為A、B的公切線，這兩點即為切點。比如，依據(jù)A邊沿點集和B邊沿點集，求兩邊沿曲線的兩條外公切線，并求得公切點1，3，5，6。依據(jù)上述算法，編寫部分C++程序（見附錄二），求得的A和B外公切線成效圖如圖9：圖9切線成效圖依據(jù)已成立的坐標系，將此算法應(yīng)用于A、B、C、D、E圓，可求得像上18個點坐標，這18個點散布如圖10所示。圖10像坐標系及切點對應(yīng)點靶標中各圓之間外公切線與圓切點標號，如圖11所示。圖11靶標坐標系及切點編號圓上切點及其像圖10和圖11上切點在相應(yīng)坐標系內(nèi)的坐標見表1。表1圓上切點及對應(yīng)像的在相應(yīng)坐標系中的坐標坐圓切點在世界坐標系中的坐圓上切點的像在像坐標系中的坐標(mm)標(mm)標xyxy切點1-506248.14815-62.433862-6250-61.11111-53.439153-5038-52.38095-41.005294-3850-39.41799-50.264555-2062-22.48677-60.317466-2038-26.98413-39.417997385024.07407-46.031758506236.77249-55.291019625042.85714-43.9153410503832.01058-35.4497411-50-38-57.6719621.6931212-62-50-70.6349230.6878313-50-62-61.1111140.2116414-38-50-50.2645531.746031538-509.5238130.952381650-3822.2222222.751321762-5027.2486832.010581850-6218.7830739.682544．數(shù)碼相機的內(nèi)、外參數(shù)在實質(zhì)求解的過程中最后的像坐標采納物理坐標形式(x,y)，單位為mm，且fx'fxd,fy'fyd，此中d為單位像素的物理尺寸（1/3.78）。這樣靶標上點與像平面上的點對應(yīng)關(guān)系以下：xfx'00r1,1r1,2t1xwsy0fy'0r2,1r2,2t2yw(5)1001r3,1r3,2t31由上式可得：xfx'r1,1fx'r1,2fx't1xwsyfy'r2,1fy'r2,2fy't2yw(6)1r3,1r3,2t31令單應(yīng)矩陣45a1a2a3fx'r1,1fx'r1,2fx't1Ar3,4a4a5a6fy'r2,1fy'r2,2fy't2(7)a7a81r3,1r3,2t3則可把參數(shù)求解問題轉(zhuǎn)變?yōu)橄惹髥螒?yīng)矩陣A,而后從A矩陣分別出待求參數(shù)的問題。為求取A陣,變換式(6),消去s,r3,4，并分別待求參數(shù)，則可得a1xwyw1000xwxywxa2x000xwyw1xwyywyM(8)ya8本文獲取了18個切點，將其帶入該方程組，共36個方程。已知點的個數(shù)遠遠超出解該線性方程組的需要，這是一個超定方程組。在此使用最小二乘法，解這個超定方程組，求出最優(yōu)的參數(shù)（程序見附錄三）。求出單應(yīng)矩陣A后，即可提拿出fx',fy'以及外面參數(shù)矩陣：a12a22a42a521/fx'2a82a72(9)a1a2a4a51/fy'2a7a8r3,411(10)a22a522a12a422fx'2fy'2a8fx'2fy'2a7r1,1r1,2t1fx'001r2,1r2,2t20fy'0A(11)r3,1r3,2t3001旋轉(zhuǎn)矩陣R的第三列可由其正交性求得：這里為向量叉積。依據(jù)表1中點的坐標求出相機的內(nèi)、外參數(shù)：5．求靶標圓心像在像坐標系中的坐標將靶標圓心在世界坐標系中的坐標代入方程，使用物理坐標公式，求靶標圓心像在像坐標系中的坐標：fx'r1,1xwr1,2ywt1xr3,2ywt3r3,1xw(12)fy'r2,1xwr2,2ywt2yr3,1xwr3,2ywt3求出的圓心的像坐標Ac'、Bc'、Cc'、Dc'、Ec'見表2（依據(jù)題目，若以相機光學(xué)中心為原點，則像點的z坐標均為像距417.19576mm）：表2靶標圓心及其像點坐標坐標靶標圓心坐標(mm)靶標圓心的像坐標(mm)圓編號XYXYA-5050-50.460651.7391B-2050-23.801549.6625C505033.897445.1681D-50-50-59.9735-30.9809E50-5019.3974-31.52156．兩相機相對地點確實定假定兩部相機的內(nèi)部參數(shù)同樣，兩部相機的坐標系成立同已提出的模型。為了確立兩部相機的相對地點，將左、右兩部相機中左相機固定，即以左相機坐標系為基準，則右相機有關(guān)于左相機的坐標有以下變換關(guān)系：xlxrxrRTyrylRyr(13)T1zrzlzr01此中xl，，zlT，，yr，zrT分別是左相機和右相機的像點坐標，ylxrr1,1r1,2r1,3t1Rr2,1r2,2r2,3為變換的旋轉(zhuǎn)重量，Tt2為變換的位移重量。r3,1r3,2r3,3t3因為在成立坐標系時，相機的像平面上的點位于xy平面上，故z坐標為零，因此變換關(guān)系簡化為：xlr1,1r1,2t1xrylr2,1r2,2t2yr(14)1r3,1r3,2t31經(jīng)過模板上圓切點在兩相機上的像，可用最小二乘法把九個參數(shù)標定。旋轉(zhuǎn)矩陣的第三列可依據(jù)其正交性由前兩列算出。兩坐標系的變換關(guān)系求出，即可確立它們的相對地點關(guān)系。六、模型的精度和穩(wěn)固性剖析在上一節(jié)模型的求解過程中，我們利用A、B、C、D、E5個圓上18個切點與像坐標求出相機內(nèi)、外參數(shù)，為了考證該模型，我們利用留一法，只利用4個圓（A、B、D、E；B、C、D、E；A、C、D、E）來計算另一個圓心像坐標，以A、B、D、E這一組為例，代入圓A、B、D、E上切點坐標及其相對應(yīng)的投影點坐標，求出數(shù)碼相機的一組內(nèi)、外參數(shù)，利用這組參數(shù)求出圓C的圓心在投影面上對應(yīng)點的坐標Cc''，該點應(yīng)當在圓A和圓B的圓心在投影面上像點，即Ac',Bc'所成直線上邊，但是因為不一樣的參數(shù)致使了偏差，經(jīng)過求Cc''到該直線的距離dc應(yīng)反應(yīng)所求參數(shù)偏差的大小。同理，用B、C、D、E和A、C、D、E求出此外兩組參數(shù)后，進行近似的辦理。三組數(shù)據(jù)以下：1．用A、B、D、E上切點求有關(guān)參數(shù)得：Cc''的坐標為(32.5312，45.2120)，與Ac'Bc'所成直線距離為0.062355mm。2．用B、C、D、E上切點求有關(guān)參數(shù)得：Ac''的坐標為(-51.5430，51.8816)，與Bc'Cc'所成直線距離為0.058033mm。3．用A、C、D、E上切點求有關(guān)參數(shù)：Bc'的坐標為(-25.3578，52.7422)，與Ac'Cc'所成直線距離為2.949541mm。剖析數(shù)據(jù)可知本文提出的模型精準度比較高，前兩組偏差均不到一個像素，即基本重合，完好能夠知足要求。第三組沒有考慮B圓相應(yīng)的切點，偏差較大，可見B圓的設(shè)置對計算精度有較大影響。這可能與B圓離中心較近，產(chǎn)生畸變較小所致5,6。七、模型的優(yōu)弊端長處：本模型在提取圖像邊沿時，采納掃描法，關(guān)于噪音極小的簡單的圖案，提取完好精準，比一般的通用邊沿檢測算法成效要好；該模型采納最小二乘法求取變換參數(shù)，簡單實行，且不失其精準性和穩(wěn)固性；本文采納留一法進行查驗，查驗結(jié)果精度高穩(wěn)固性好。弊端：模型沒有考慮相機物理要素及制作工藝缺點而致使的成像畸變，所以和實質(zhì)的成像結(jié)果會有必定的偏差；在使用最小二乘法計算相機內(nèi)、外參數(shù)時，由線性方程組所得的線性方程沒有經(jīng)過規(guī)格化辦理，所求結(jié)果會有必定的影響；計算旋轉(zhuǎn)矩陣第三列是直接使用了其正交性，使用叉積計算，而因為計算偏差，已得參數(shù)可能其實不嚴格知足正交性，這樣計算得出的結(jié)果其實不十分精準（但對此后計算圓心的像坐標沒有影響）。參照文件李偉、呂曉旭、錢曉凡、鐘麗云。鑒于平面模板的攝像機標定方法比較[J]，激光雜志，第27卷，第2期，54－55，2006年。毛劍飛、鄒細勇、諸靜。改良的平面模板兩步法標定攝像機[J]，中國圖象圖形學(xué)報，第9卷，第7期，846－852，2004年。雷彥章、趙慧潔、姜宏志。一種單雙目視覺系統(tǒng)聯(lián)合的三維丈量方法[J]，光學(xué)學(xué)報，第28卷，第7期，1338-1342,2008年。吳謹，王俊。鑒于投影矩陣的攝像機參數(shù)標定[J]，福建電腦，第8期，1527，2008年。孟曉橋,胡占義。一種新的鑒于圓環(huán)點的攝像機自標定方法[J]，軟件學(xué)報，第13卷，第5期，957－965，2002年。[6]J.Heikkila.Geometriccameracalibrationusingcircularcontrolpoints[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,October,22(10)，－，2000.10661077附錄附錄一：掃描法算法C代碼由圖像辦理已求出圖片的0-1矩陣，設(shè)矩陣為a[][],a[I][J]表示地點為第I行第J列的值，0為黑色點，1為非黑色點。辦理完后，圖像矩陣保存在s[][]中，值為0表示為邊沿點，值為-1的點位非邊沿點。include<stdio.h>#inclue<string.h>inta[1025][769];ints[1025][769];intmain#( ){inti,j;freopen("data.txt","r",stdin);freopen("point.txt","w",stdout);memset(s,-1,sizeof(s));for(i=0;i<768;i++){for(j=0;j<1024;j++){intt;scanf("%d",&t);a[j][i]=t;flag[j][i]=false;}}for(intii=0;ii<1024;ii++){for(intjj=0;jj<768;jj++){if(a[ii][jj]==0){s[ii][jj]=0;intkk=jj;while(a[ii][kk]==0&&kk<768)kk++;kk--;=kk+1;s[ii][kk]=0;}}}for(intjss=0;jss<768;jss++){for(intiss=0;iss<1024;iss++){if(a[iss][jss]==0){s[iss][jss]=0;intkss=iss;while(a[kss][jss]==0&&kss<1024)kss++;kss--;iss=kss+1;s[kss][jss]=0;}}}for(inti=0;i<1024;i++){for(intj=0;j<768;j++)printf("%d",s[i][j]);printf("\n");}return0;}附錄二：求公切線C++代碼structnode{intx,y;}r[2][500];//r[0]保存A的全部邊沿點，r[1]保存B全部邊沿點intt[2];//t[0]表示A邊沿點個數(shù)，t[1]表示B邊沿點個數(shù)boolCheck(doublea,doubleb,doublec,intt1,intt2,doublew){inti;for(i=0;i<t[t1];i++){doublew1=a*r[t1][i].y+b*r[t1][i].x+c;if(w1*w<0)returnfalse;}for(i=0;i<t[t2];i++){doublew1=a*r[t2][i].y+b*r[t2][i].x+c;if(w1*w<0)returnfalse;}returntrue;}voidGetQieDian( ){boolok=false;for(inti=0;i<t[0];i++){for(intj=0;j<t[1];j++){if(r[0][i].x==r[1][j].xr[1][j].y)continue;doublek=r[1][j].y)/(r[0][i].x-r[1][j].x);doublea=1;doubleb=-k;doublec=k*r[0][i].x-r[0][i].y;doublew=c;

||r[0][i].y(double)(r[0][i].y

==-ok=Check(a,b,c,0,1,-w);//abcif(ok){

為直線方程參數(shù)point[1]=r[0][i];

//

保存切點坐標point[5]=r[1][j];break;}}if(ok)break;}for(inti=0;i<t[0];i++){for(intj=0;j<t[1];j++){if(r[0][i].x==r[1][j].xr[1][j].y)continue;doublek=(double)(r[0][i].y(r[0][i].x-r[1][j].x);doubl