專利名稱：探測儀器探測定位的優化方法
探測儀器探測定位的優化方法技術領域
本發明屬于圖形學技術領域，涉及探測儀器探測定位的優化方法。
技術背景
幾何探測方法主要研究的是通過探測結果來確定或者證實一個物體的結構或性 質(比如形狀，位置等)。Cole和Yap從機器人研究的問題中提出了最早的幾何探測方 法——手指探測finger probe，該方法主要是通過探測獲得一條直線和待測物體的第一個 相交點的信息，由這些交點信息來重構待測物體；在一些確認類的方法比如“基于形狀 的模型model-based problem”方法中，待測的物體形狀是已知的，但具體的方位或位置 是不可知的，該方法主要是研究至少需要多少個探測信息數據才能夠確認其具體方位。 而且現有技術每做一次探測，探測儀器的位置是不確定的，需要根據探測得到的數據調 整新的位置；同時所配置的探測儀器個數與多邊形或者多面體的頂點個數有關，當探測 的物體頂點個數很多時，探測儀器數量會增加得很快。
這些探測問題在機器人，圖形學以及學習理論方面都有著很多的應用。許多學 者都在這一領域進行了很多的研究，以下是與本發明相關的一些代表文獻。
1 .R.Cole and C.K.Yap.Shape from probing.Journal of Algorithms, 8: 19~38, 1987.
2.D.Dobkin, H.Edelsbrunner, and C.K.Yap.Probing convex polytopes.In Proceedings of the 18th ACM Symposium on Theory of Computation (STOC ' 86),pages424—432, 1986.
3.H.Edelsbrunner and S.Skiena.Probing convex polygons with χ-rays.SIAM Journal on Computing, 17(5) 870—882，1988.
4.R.J.Gardner and M.Kiderlen.A solution to Hammer ' s χ-ray reconstruction problem.Advances in Mathematics, 214(1) 323—343，2007.
5.W.E.L.Grimson and T.Lozano-Perez.Model-based recognition and localization from sparse range or tactiledata.The International Journal of Robotics Research, 3: 3—35, 1984.
6.P.C.Hammer.Problem 2.1n V.L.Klee, editor, Proceedings of the AMS Symposium in Pure Mathematics, volume VII Convexity, pages 489—499，1963.
7.E.Joseph and S.Skiena.Model-based probing strategies for convex polygons. Computational Geometry Theory and Applications, 2: 209—221，1992.
8.S.-Y.R.Li.Reconstruction of polygons from projections.Information Processing Letters, 28(5) 235—240，1988.
9.H.Meijer and S.S.Skiena.Reconstructing polygons from χ-rays.Geometriae Dedicata, 61(2) 191—204，1996.
lO.A.S.Rao and K.Y.Goldberg.Shape from diameter Recognizing polygonal parts with a parallel-jaw gripper.The International Journal of Robotics Research, 13 (1) 16—37,1994.
11.S.S.Skiena.Problems in geometric probing.Algorithmica，4(4) 599—605， 1989.
12.S.S.Skiena.Interactive reconstruction via geometric probing.Proceedings of the IEEE，80(9) 1364—1383，1992.
13.M.Sormann，J.Bauer, C.Zach, A.Klaus，and K.Karner.VR modeler from image sequences to 3D mo dels. In Proceedings of the 20th Spring Conference on Computer Graphics，pages 148—156，2004.
14.Y.K.Wang, M.J.Magee， and J.K.Aggarwal.Matching three-dimensional objects using silhouettes.IEEE Transactions on Pattern Analysis and Machine Intelligence，6 513—518，1984.
15.A.Bottino and A.Laurentini.Introducing a new problem shape-from-silhouette when the relative positions of the viewpoints is unknown.IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(11) 1484—1493，2003.
16.J.H.Conway，R.H.Hardin, and J.A.Sloane.Packing lines，planes，etc. packings in Grassmannian spaces.Experimental Mathematics，5，1996.
17.R.Fabio.From point cloud to surface the modeling and visualization problem. In International Workshop on Visualization and Animation of Reality-based 3D models，2003. International Archives of Photogrammetry，Remote Sensing and Spatial Information Sciences， Vol.XXXIV-5/WlO.
18.Y.H.Fang，H.L.Chou, and Z.Chen.3D shape recovery of complex objects from multiple silhouette images.Physical Review Letters, 24(9—10) 1279—1293, 2003.
19.R.H.Hardin, N.J.A.Sloane，and W.D.Smith.Spherical coverings, 2008.http:// www.research.att.com/ njas/coverings/.
20.W. C.Karl, G.C.Verghese, and A.S.Willsky.Reconstructing ellipsoids from projections.Computer Vision, Graphics，and Image Processing, 56 (2) 124—139，1994.
21.T.Kayikcioglu，A.GangaL and M.Turhal.Reconstructing coronary arterial segments from three projection boundaries.Physical Review Letters，22(6—7) 611—624， 2001.
22.M.Lindenbaum and A.Bruckstein.Reconstruction of polygonal sets by constrained and unconstrained double probing.Annals of Mathematics and Artificial Intelligence，4 (3-4) 345—361，1991.
23.W.Martin andJ.K.Aggarwal.Volumetric description of objects from multiple views. IEEE Transactions on Pattern Analysis and Machine Intelligence，5 150—158，1983.
24.S.Sarkar，P.J.Phillips，Z.Liu, I.R.Vega, P.Grother, and K.W.Bowyer.The humanid gait challenge problem Data sets，performance，and analysis.IEEE Transactions on PatternAnalysis and Machine Intelligence, 27(2) 162—177，2005.點可以與三條或以上的線相切；
所述探測三維情況下多面體的優化步驟如下
步驟201 將K個探測儀器放置在一個半徑為1的球面上，任意方向、位于球面內任意位置且多面體的最大面面角不超過α，發明內容
本發明旨在提出一種探測儀器探測定位的優化方法，其應用平面和空間點的定 位原理，對給定的待測二維多邊形或者三維多面體，配置數量最少的一組探測儀器從不 同角度探測獲得的輪廓信息來重構出該多邊形或者多面體的具體位置和形狀。
為了實現上述目的，本發明的技術方案是一種探測儀器探測定位的優化方 法，以使用最少的探測儀器在二維和三維情況下重構出被測的多邊形和多面體；
所述探測二維情況下多邊形的優化步驟如下
步驟101 將K個探測儀器放置在一個半徑為1的圓周上，假設所有K個探測 儀器均勻放置在圓周上，待測多邊形P有m個頂點，可以位于圓內任何位置，且多邊形P最大內角不超過α，則
權利要求
1. 一種探測儀器探測定位的優化方法，其特征在于，使用最少的攝像機在二維和三 維情況下重構出被測的多邊形和多面體；所述探測二維情況下多邊形的優化步驟如下步驟101:將K個探測儀器放置在一個半徑為1的圓周上，假設所有K個探測儀器 均勻放置在圓周上，待測多邊形P有m個頂點，可以位于圓內任何位置，且多邊形P最大內角不超過α，則K=P^I;每個探測儀器可以獲得兩條分別與該多邊形某個頂點相切的射線，這兩條射線以探測儀器所在位置為頂點構成一個錐形，則探測儀器的每條射線 上至少與多邊形P的一個頂點相切；步驟102 根據切線位于探測儀器的左右位置把所有的切線分為左切線和右切線； 設P1是所有的左切線相交獲得的凸多邊形，P是所有的右切線相交獲得的凸多邊形；步驟103:通過計算任意兩個相鄰探測儀器的左切線的交點得到凸多邊形P1;通過計 算任意兩個相鄰探測儀器的右切線的交點得到凸多邊形P ；兩個凸多邊形P1和P都最多 只有K個頂點；步驟104:在線性時間內求得所述兩個凸多邊形P1和P的相交圖形；所述的相交圖 形為新凸多邊形，其至多含有2m個頂點；步驟105 根據以下規則在所述新凸多邊形中找到被測多邊形PWm個頂點a.如果新凸多邊形中的一個結點被至少三個探測儀器觀測到，則必然可以確定該結 點為平P的一個頂點；b.如果新凸多邊形中的一個頂點不屬于被測多邊形P，其相鄰兩個頂點必然屬于P；c.如果新凸多邊形中的一條邊屬于被測多邊形P，則這兩個結點必然與至少三條邊相 切，那么這兩個結點必然屬于P;d.由于每個探測儀器至少可以看到P中的兩個頂點，且r t* ι a* ι ιM :::::“1…a^i……_ I:麵wW^* · 則個探測儀器可以與至少3m個結點相切，則新凸多邊形中至少有一個結點可以與三條或以上的線相切；所述探測三維情況下多面體的優化步驟如下步驟201:將K個探測儀器放置在一個半徑為1的球面上，被測多面體Q可以是任意方向、位于球面內任意位置且多面體的最大面面角不超過α，PJK=I 1胸Jl ；每個探測儀器可以獲取多條射線與多面體的多個頂點相切，這些射線以探測儀器所在位置 為頂點形成一個多面錐體，探測儀器的每條射線至少與多面體Q的一個頂點相切；步驟202:設多面體Q有η個面、m個頂點，則K個探測儀器獲得的K個多面錐體 相交的新多面體最多含有n+m個頂點；步驟203 根據以下規則在所述新多面體中找到被測多面體Q的m個頂點 a.如果新多面體中的一個頂點不屬于被測多面體Q，其周圍相鄰結點必然都屬于Q；b.如果新多面體中的一條棱屬于被測多面體Q，那么這條棱的兩個結點必然與至少三 條棱相切，則這兩個結點必然屬于Q ；c.至少有一個多面體的頂點可以被確定下來。
2.如權利要求1所述的探測儀器探測定位的優化方法，其特征在于所述探測儀器 是攝像機或者觸覺感受器。
全文摘要
本發明屬于圖形學技術領域，涉及探測儀器探測定位的優化方法。本發明應用平面和空間點的定位原理，對給定的待測二維多邊形或者三維多面體，配置數量最少的一組探測儀器從不同角度探測獲得的與多邊形或多面體切線信息來重構出該多邊形或者多面體的具體位置和形狀。使用本發明優化方法，探測所需要的最優或最少的探測儀器的數量只與多邊形的最大內角或者多面體的最大面面角有關；一旦所需要的觸覺感受器的數量確定，其放置位置可以永久固定。
文檔編號G01B11/00GK102022978SQ20091019605
公開日2011年4月20日 申請日期2009年9月22日 優先權日2009年9月22日
發明者王怡慧, 魯道夫 申請人:復旦大學
專業數控銑床產品供應商
20年生產經驗，實力工廠，精工品質，質量有保障
