（计算数学专业论文）practice+and+theory+of+extracting+3d+ination+from+fisheye+pictures.pdf

s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 摘要 基于图象的虚拟现实技术通常采用场景的照片或视频作为输入，因此还原效 果具有高度的真实感。这些技术一般分为两类，各有其优缺点： 一类技术的算法比较简单，其获得真实感效果的代价是需要对场景在不同位 置、不同方向拍摄大量照片。这需要较多的存储空间来保存这些场景数据，并且 没有充分利用场景图象自身所蕴涵的几何特征和深度信息。 另一类技术则首先获得场景的深度信息，然后对场景进行建模，最后利用纹 理映射方式实现虚拟浏览。该技术通常基于双目视觉原理，利用两幅以上的照片 恢复场景深度。这就无法避免对图象进行大量运算，如高斯平滑、特征提取、形 状匹配等。另外，获取场景各个部分的结构信息之后，通常要借助人机交互操作 并通过拼接运算才能形成一个完整的场景结构。 在基于图象的虚拟现实技术当中，三维重建是一个核心问题。如何合理、有 效地获取和处理场景信息，以更加容易地实现场景的三维重建则是本文的研究重 点。 针对传统方法的不足之处，本文试图寻找一种新的、利用鱼眼照片对场景进 行三维重建的手段。该方法同时具有前面两类技术的优点，既能够比较容易地获 得场景结构从而进行场景建模，同时还不必保存大量的图象信息，最终实现真实 感的虚拟浏览。 鱼眼镜头和普通镜头相比具有很大的差异。鱼眼镜头是一种超广角镜头，通 常视角超过1 8 0 。，所以安装有鱼眼镜头的相机一次可以拍摄半个球面范围的场 景。如果利用鱼眼相机制作全景图的话只需很少几幅照片即可实现。由于鱼眼镜 头的视角范围非常大因此会对拍摄的场景产生强烈的变形。 鱼眼镜头的投影模型并非是传统镜头的小孔成像模型。根据近年的研究，鱼 眼镜头的投影模型主要归纳为以下几种：多项式逼近模型、球面模型、抛物面模 型，已经证明这些模型都存在一定程度的误差。本文提出了一种可校正的抛物面 模型，可以根据不同型号的鱼眼镜头计算出适合该镜头的投影参数，因此具有更 好的适应性。经过检验，该模型对鱼眼的变形能够较好地恢复。 鱼眼照片上每一个像素都会同从原点出发的某一个方向有一个简单、唯一的 对应关系，而普通镜头由于未知的焦距这种对应关系是不成立的。这一特性f 是 鱼眼镜头和普通镜头最本质的区别。通过鱼眼镜头的这一模型，我们可以得到三 维空间中的点经过鱼眼投影变换后的公式，继而又可以推导出三维空间中不同类 型的直线段经过投影后的形式。 在场景的各种本征特征中，场景或场景中所包含目标的三维信息如形状、长 度等是最基本和最重要的。场景的一些其他特征如表面法线、轮廓边界等都可以 从形状推算出来。在获知场景全面的结构信息的条件下，就可以实现场景的三维 重建。本文并不是片面地计算场景中单个像素的深度值，而是把该问题转化成为 计算场景三维结构框架的问题，这个三维框架最终反映了场景的实际结构。根据 鱼眼投影特性，对于场景中平行于坐标轴的结构框架，我们可以得到一组其在三 维空间和鱼眼照r 上所对应的约束关系。这一约束关系有助于提取场景的轮廓。 不同类型场景的重建方法也不相同。文章首先给出简单场景定义：( 1 ) 场景 框架的所有竖线和x o z 平面垂直：( 2 ) 其余的框架线和x o z 平面平行。对于简单 场景给出两种重建方法，一种是利用人机交互在鱼眼照片上直接绘制场景框架， 再根据前面的约束关系生成三维结构；另一种是利用场景结构草图，草图相当于 v i s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 场景框架在x o z 平面上的投影，能够粗略反映场景的结构。这种方法和前一种相 比，只需在重建之前利用较少的操作生成草图之后。就能够利用鱼眼投影特性自 动、准确地搜索场景框架。两种方法都只需一幅鱼眼照片就可以重建半个场景的 结构，但不足在于仅能处理简单场景。 简单场景的定义中去掉第2 个条件我们称之为复杂场景。去掉该条件就无法 完全利用前面所定义的约束关系，因此用一幅照片不能重建复杂场景。解决的方 法是利用双且视觉原理，通过视差计算边框点的实际深度，才可以得到场景的真 实结构而不会产生歧异。本文讨论了鱼眼照片的双目视觉原理，引入了鱼眼极线 约束方法。极线约束法在立体视觉匹配中起着极为重要的作用，这是因为在两幅 照片当中直接寻找匹配点是一项巨大的工作，利用极线可以把待检测点限定在一 条特定的极线范围之内，从而大大减少了搜索区域，也增加了搜索的精确度。文 章首先对双目照片搜索场景的所有竖线，然后利用极线约束法对这些竖线进行双 目匹配后得到相互对应的场景主框架，就相当于自动得到了场景的草图。同搜索 简单场景相似，根据主框架继续自动搜索场景的其他框架线最终就可得到场景框 架的完整信息。利用双目重建场景和单目相比具有很大的优势，一方面可以处理 更广范围的场景，另一方面可以原则上不需人工交互就可以重建场景的框架。 如何重建存在遮挡现象的更复杂场景也是本文着重研究的方面。由于遮挡的 原因，场景可能需要多幅照片才能拍摄完整。本文对计算几何中著名的画廊问题 进行了变形，提出了基于单侧单调多边形的限定警卫的画廊问题。该问题是这样 描述的，对于基于一条参考边的单侧单调多边形，假定警卫只允许放置在参考边 上，那么最少需要多少警卫能够完全监视整个多边形。上述问题的结论同普通画 廊问题的结论是相同的。本文给出的算法可以在o ( n l o g n ) 的时间内寻找该问题的 最小警卫数。对该问题增加一个限制，要求每个警卫只监视多边形上一段连续的 区域本文给出的算法可以在o ( n ) 的时间内寻找该问题的最小警卫数。上述问 题再增加一个限制：每条边都要由间隔不小于d 的两个警卫所监视，称为双警卫 的画廊问题，本文给出o ( n ) 时间的算法解决该问题。 研究上述画廊问题的目的是将该理论应用于利用鱼跟照片重建场景的问题 中。可以设想当我们用鱼眼相机对场景进行拍摄时，通常会将相机沿一条参考 线移动，对场景分为前后两个部分进行拍摄。假定半个场景和参考线构成的多边 形是单侧单调多边形，并且相机受参考边的限制正好有1 8 0 0 的视角，可以认为 此时利用鱼眼相机拍摄场景的问题和前面讨论的限定警卫的画廊问题是完全相 同的。拍摄场景时如何选择尽量少的拍摄点去拍摄尽量少的照片，画廊问题的解 决可以为其提供理论依据和方法。对场景所构成的多边形采用本文给出的算法， 可以得到双警卫的位置，也就是鱼眼相机双目拍摄的所有位置，在这些位置拍摄 照片可以保证场景的每条边都可以被一对双目鱼眼照片所覆盖并且照片的数量 最小。对每一组双目照片所覆盖的连续场景重建后，再合并每个部分的场景就可 以得到整个场景的三维结构。 本文全面地研究了利用鱼眼照片重建三维场景的理论，提出了一系列的定 义、公式和定理，并给出了多个场景重建的实例作为检验，其重建结果和虚拟浏 览的效果是令人满意的。 关键词：鱼眼，三维重建，画廊问题，深度，虚拟现实，草图 v i l s h a n d o n gu n i v ms i t yd o c t o r a ld i s s e r t a t i o n a b s t r a c t t h e i m a g e b a s e d v i r t u a l r e a l i t yt e c h n i q u e su s u a l l y t a k es o m e p i c t u r e s o ra s e g m e n to fv i d e oo f as c e n ea si n p u td a t at oa c h i e v er e a l i s t i ce f f e c t t h e s et e c h n i q u e s c o u l db ec l a s s i f i e di n t ot w o g r o u p s ，e a c h h a s a d v a n t a g e s a n d d i s a d v a n t a g e s r e s p e c t i v e l y o n ec l a s so ft h e s et e c h n i q u e su s es i m p l ea l g o r i t h m s b e a r i n g t h ee x p e n s eo ft a k i n g al o to f p i c t u r e sf r o md i f f e r e n tp o s i t i o n sa n d d i f f e r e n td i r e c t i o n st oas c e n ei no r d e rt o a c q u i r et h er e a l i s t i ce f f e c t t h e s et e c h n i q u e sn e e dm o r es t o r a g es p a c e t os a v et h ed a t a o fs c e n e ，a n dd o n t u t t e r l y u t i l i z et h e g e o m e t r y f e a t u r e sa n d d e p t h i n f o r m a t i o n c o n t a i n e di np i c t u r e s a n o t h e rc l a s so ft e c h n i q u e sa c q u i r e st h ed e p t hi n f o r m a t i o no fas c e n ef i r s t ，t h e n m o d e lt h e s c e n e ，a n df i n a l l y r e a l i z ev ru s i n g t e x t u r e m a p p i n g m e t h o d t h e s e t e c h n i q u e s ，b a s e do ns t e r e o s c o p i c v i s i o nr u l ei n g e n e r a l ，a l w a y su s e a tl e a s tt w o p i c t u r e st or e c o v e rt h ed e p t ho fas c e n e i nt h i sw a y , a l o to fo p e r a t i o n s ，f o r e x a m p l e ， g a u s s i a ns m o o t h n e s s ，f e a t u r ee x t r a c t i o n ，a n ds h a p em a t c h i n g ，e t c ，a r eu n a v o i d a b l e m o r e o v e r , a f t e ra c q u i r i n gt h es t r u c t u r eo fe a c hp a r to fas c e n e ，s o m eh u m a n m a c h i n e i n t e r a c t i v eo p e r a t i o n sa r ea l s on e e d e dt oh e l pt h em e r g i n gp r o c e s st oa c h i e v eaw h o l e s t r u c t u r eo fas c e n e 3 dr e c o n s t r u c t i o ni sak e r n e lp r o b l e mi ni m a g e b a s e dv r t e c h n i q u e s t h ek e y p r o b l e mr e s e a r c h e di nt h i sd i s s e r t a t i o ni sh o w t oa c q u i r ea n d p r o c e s s t h ei n f o r m a t i o n o fs c e n er e a s o n a b l ya n d e f f i c i e n t l yt or e c o n s t r u c t3 d o fs c e n e e a s i l y a i m e dt ot h o s e d i s a d v a n t a g e s i nt r a d i t i o n a l t e c h n i q u e s ，an e wt e c h n i q u e o f r e c o n s t r u c t i n g 3 dm o d e lu s i n gf i s h e y e p i c t u r e s ，i sp r o p o s e di n t h i sd i s s e r t a t i o n c o m p a r e d t ot h ef o r m e rt w o t y p e so ft e c h n i q u e s ，t h i st e c h n i q u en o to n l ya c h i e v e st h e r e a l i s t i cv r ，b u th a st h ea d v a n t a g e sc o n t a i n e di nt h et w ot y p e s ：t h es t r u c t u r eo fa s c e n ec o u l db ea c q u i r e de a s i l yw h e nm o d e l st h es c e n e ；a n daq u a n t i t yo fd a t ao fa s c e n ei sn o tr e q u i r e dn o w f i s h e y el e n s e sa r ed i f f e r e n tg r e a t l yf r o mn o r m a ll e n s e s a sat y p eo fu l t r a w i d e f i e l do fv i e w s ( f o v ) l e n s e s ，f i s h e y el e n s e su s u a l l yh a v et h ef o v e x c e e d i n g l8 0 。， w h i c hc o u l dt a k eh a l fas p h e r i c a ls c e n ei n t oas i n g l ep i c t u r e a c c o r d i n g l y ，l e s sp i c t u r e s a r ee n o u g ht oc r e a t ep a n o r a m i ci m a g ew h e nu s eaf i s h e y ec a m e r a b e c a u s eo ft h e w i d ef o vo ff i s h e y e l e n s e s ，s t r o n g d i s t o r t i o ns h o u l db e g e n e r a t e d i n f i s h e y e p i c t u r e s t h e p r o j e c t i n gm o d e l so ff i s h e y el e n s e sa r en o tb a s e d o np i n h o l er u l ee xs t i n gi n t r a d i t i o n a ll e n s e s a c c o r d i n gt or e s e a r c h i n gr e s u l t sf o rf i s h e y el e n s e si nr e c e n ty e a r s ， t h ep r o j e c t i n gm o d e l so ff i s h e y el e n s e sa r em a i n l yc l a s s i f i e di n t os e v e r a l t y p e s ： p o l y n o m i a la p p r o a c h i n gm o d e l ，s p h e r i c a lm o d e l ，a n dp a r a b o l i c a lm o d e l i th a sb e e n p r o v e d t h a ts o m ed e g r e eo fe r r o ro c c u r si nt h e s em o d e l s i nt h i sd i s s e r t a t i o n ，a n a d j u s t a b l ep a r a m e t e r i z e dp a r a b o l i c a l m o d e li s p r o p o s e d b a s e do nt h i s m o d e l ，t h e p a r a m e t e r t h a tm a y a d j u s tt od i f f e r e n tt y p eo ff i s h e y el e n s e sc o u l db ec o m p u t e d b y o u re x p e r i m e n t s ，t h i sm o d e lp e r f o r m sr e l i a b l yi nr e c t i f y i n gt h ed i s t o r t i o nc a u s e db y f i s h e y el e n s i nf i s h - e y ep i c t u r e ，e a c hp i x e lh o l d sas i m p l ec o r r e s p o n d i n gr e l a t i o nt oad i r e c t i o n u l s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n e r e c t e df r o mo r i g i n t h i sr e l a t i o n ，h o w e v e r , d o e s n te x i s ti nn o r m a lp i c t u r e sd u et o u n k n o w nf o c a ll e n g t ho fn o r m a ll e n s t h i sc h a r a c t e ri st h em o s te s s e n t i a id i f i e l - e n c e b e t w e e nf i s h e y el e n sa n dn o r m a ll e n s b a s e do nt h ec h a r a c t e r , w ec o u l dd e d u c et h e p r o j e c t i n g f u n c t i o nt h a ta3 dp o i n t p r o j e c t s o n t oap i x e li n f i s h e y ep i c t u r e ，a n d a c c o r d i n g l y ，t h ef u n c t i o n st h a td i f f e r e n tt y p e so fl i n e sp r o j e c to n t of i s h e y ep i c t u r e ， a m o n g a 】ij n t r i n s i cc h a r a c t e r i s t i c so fas c e n e ，t h e3 d i n f o r m a t i o n s u c ha ss h a p e a n d l e n g t h o fo b j e c t si nas c e n e ，i st h em o s tb a s i ca n di m p o r t a n t ，s o m eo t h e r c h a r a c t e r i s t i c s ，s u c ha ss u r f a c en o r m a la n de d g ec o n t o u r , c o u l db eg e n e r a t e df r o mt h e s h a p eo ro t h e ri n f o r m a t i o n u n d e rt h ec o n d i t i o no fa c q u f r i n gt h ew h o l es t r u c t u r eo fa s c e n e t h e3 dr e c o n s t r u c t i o nc o u l db er e a l i z e d t h em a i np r o b l e mi nt h i sd i s s e r t a t i o n i sn o tt oc o m p u t et h ed e p t hv a l u eo fe a c hp i x e li nap i c t u r e b u ti st r a n s f o r m e dt ot h e p r o b l e mo fc o m p u t i n g as c e n e sw h o l ef r a m e w h i c hr e f l e c t st h er e a ls t r u c t u r eo ft h e s c e n e b a s e do nt h ep r o j e c t i n gc h a r a c t e r i s t i c so ff i s h - e y el e n s ，f o rt h o s ef r a m el i n e s p a r a l l e l t oc o o r d i n a t ea x e si nas c e n e ，w em a y a c q u i r es e v e r a lc o n s t r a i n t sb e t w e e n t h e s el i n e si n3 d s p a c e a n dt h e i rc o r r e s p o n d i n gp r o j e c t i o n si nf i s h e y ep i c t u r e a r m e d w i t ht h e s ec o n s t r a i n t s ，w e c o u l de x t r a c tt h ec o n t o u ro fas c e n e b a s e do nt h ec o m p l e x i t yo fas c e n e t h ew a y st 0l c o v e r3 ds t r u c t u r ea r cd i f f e r e n t w ef i r s tg i v et h ed e f i n i t i o no fs i m p l es c e n e ：( 1 ) a l lv e r t i c a lf r a m el i n e sa r eu p r i g h tt o x o zp l a n e ；a n d ( 2 ) t h er e s tf r a m el i n e sa r ep a r a l l e lt ox o zp l a n e f o ras i m p l es c e n e ， t w om e t h o d sa r ed i c f a t e d ：o n ei s d r a w i n ga na s s i t a n tf r a m ed i r e c t l y o naf i s h e y e p i c t u r et h e nc r e a t i n g3 d s t r u c t u r eb a s e do nt h ec o n s t r a i n t sm e n t i o n e da b o r e ；t h eo t h e r m e t h o d u s e st h es c e n e sd r a f t ，ap i c t u r ew h i c hi sa p p r o x i m a t e l yt h ep r o j e c t i o nt h a tt h e s c e n e sf r a m ep r o j e c t so n t ox o zp l a n e ，a n dw h i c hc a nr e f l e c tt h es t r u c t u r eo fas c e n e c o a r s e l y ，t oa c c o m p l i s ht h ei o b c o m p a r e dt ot h ef o r m e ro n e ，t h i sm e t h o du s e st h e p r o ：e c t i n gc h a r a c t e r i s t i c so ff i s h e y el e n st os e a r c hf r a m ea u t o m a t i c a l l ya n da c c u r a t e l y o nt h ec o n d i t i o no fg e t t i n gad r a f tc r e a t e db yaf e wo p e r a t i o n sb e f o r er e c o n s t r u c t i o n b o t ho ft h e s et w om e t h o d sr e q u i r ej u s to n ef i s h e y ep i c t u r et or e c o n s t r u c tt h e3 d s t r u c t u r eo fah a l fs p h e r i cs c e n e t h ed i s a d v a n t a g ei so n l ys i m p l es c e n e sc o u l db e p r o c e s s e d t h ed e f i n i t i o no fc o m p l e xs c e n ei sg o tb yo m i t t i n gt h es e c o n dc o n d i t i o nd e f i n e d i ns i m p l es c e n e h o w e v e r , t h i sw i l lr e s u l ti nt h a tt h ec o n s t r a i n td e f i n e da b o r ec o u l d n o tb es a t i s f i e dc o m p l e t e l y ；a c c o r d i n g l y ，o n ef i s h e y ep i c t u r ei s n o ts u f f i c i e n tt o r e c o s t r u c tac o m p l e xs c e n e t h em e t h o dt os o l v et h ep r o b l e mi su s i n gt h es t e r e o s c o p i c r u l ea n dc o m p u t i n gt h er e a ld e p t ho ff r a m eb yp a r a l l e x i nt h i sw a y ，t h er e a ls t r u c t u r e o fs c e n ec o u l db e a c h i e v e dw i t h o u ta m b i g u i t y i nt h i sd i s s e r t a t i o n ，t h er u l eo f s t e r e o s c o p i cv i s i o na n d t h ee p i p o l a rc o n s t r a i n t so ff i s h - e y ep i c t u r ea r ci n t r o d u c e da n d d i s c u s s e d t h ee p i p o l a r ，a sw ek n o w ，p l a y sa ni m p o r t a n tr o l ei nm a t c h i n gp r o c e s so f s t e r e o s c o p i cv i s i o n s e a r c h i n gm a t c h e dp o i n t sd i r e c t l yf r o m t w o p i c t u r e si sv e r yh a r d ； h o w e v e r ，b a s e do ns t e r e o s c o p i cr u l e s ，t h ep o i n t st ob es e a r c h e dc o u l db el i m i t e dt o r e g i o n sn e a ra ne p i p o l a r ，w h i c ht h e n r e d u c e st h es e a r c h e dr e g i o ne n o r m o u s l ya n d i m p r o v et h es e a r c h i n ga c c u r a c y f i r s t s e a r c ha l lv e r t i c a ll i n e si nd o u b l e e y ep i c t u r e s ， t h e nm a t c ht h e s el i n e s u s i n ge p i p o l a r c o n s t r a i n t st o a p p r o a c h a g r o u p o f c o r r e s p o n d i n gl i n e sb e t w e e nt w op i c t u r e s t h es e to ft h e s el i n e si sc a l l e dt h es c e n e s p r i m a r yf r a m e ，w h i c h i si nf a c tt h ed r a f to ft h es c e n e h o w e v e r , i ti sa c q u i r e d s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n a u t o m a t i c a l l y s i m i l a r l yt os e a r c h i n gp r o c e s si nas i m p l es c e n e ，w et h e ns e a r c ht h e r e s tf r a m e sf r o mt h ed r a f t - - t h o s el i n e so fp r i m a r yf r a m e s ，t og e tt h ew h o l es t r u c t u r e o fas c e n e t h e r ea r eal o to fa d v a n t a g e si n3 dr e c o n s t r u c t i o nb yw a yo f d o u b l e e y e t h a nb yt h a to f s i n g l e e y e ：o n ei st h a tt h es c o p ea n d s c a l eo fp r o c e s s i b l es c e n ee x t e n d s g r e a t l y ；a n o t h e r i st h a tt h e p r o c e s s o f r e c o n s t r u c t i n gm a yb e r e a l i z e dw i t h o u t i n t e r a c t i v eo p e r a t i o ni np r i n c i p l e a n o t h e rp r o b l e m e m p h a s i z e d i nt h i sd i s s e r t a t i o ni sh o wt or e c o n s t r u c tac o m p l e x s c e n eb l o c k e di n s i d e ，d u et ot h er e a s o no f b l o c k i n g ，m o r et h a no n ep i c t u r ei sr e q u i r e d t oc o v e raw h o l es c e n e ：a na l t e r n a t i o no ft h ea r t g a l l e r yp r o b l e m i nc o m p u t a t i o n a l g e o m e t r yt h e o r i e s ，i n t h i sd i s s e r t a t i o n ，c a l l e dg u a r d r e s t r i c t i o na r tg a l l e r yp r o b l e m b a s e do ns i n g l e s i d ea n dm o n o t o n i cp o l y g o ni s p r o p o s e d t h ed e s c r i p t i o no f t h e p r o b l e mi s ：f o r a s i n g l e s i d e a n dm o n o t o n i cp o l y g o nb a s e do nar e f e r e n c ee d g e ， a s s u m i n gt h a ta l lg u a r d sc o u l do n l yb es e to nt h i se d g e ；t h e nh o wm a n yg u a r d sa r e s u f f i c i e n tt og u a r dt h ew h o l ep o l y g o n t h er e s u l to ft h i sp r o b l e mi sa ss a m ea st h a to f t h et r a d i t i o n a la r tg a l l e r yp r o b l e m a n a l g o r i t h mw h i c hh a st i m ec o m p l e x i t yo ( n l o g n j i sa p p r o a c h e dt of i n dt h em i n i m u mn u m b e ro f g u a r d s n o w w ea d dar e s t r i c t i o nt ot h e p r o b l e m ：e a c hg u a r do n l yg u a r d sap a r to fc o n s e c u t i v ee d g e so nt h ep o l y g o n a n a l g o r i t h m w i t ht i m e c o m p l e x i t yo ( n j i s p r o p o s e dt o s o l v et h e p r o b l e m f i n a l l y ， a n o t h e rr e s t r i c t i o ni sa p p e n d e d ：e a c he d g em u s tb e i n gg u a r d e db yt w og u a r d sw h o s e d i s t a n c ei sn ol e s st h a nd ，t h i sp r o b l e mi sc a l l e dd o u b l e g u a r da r tg a l l e r yp r o b l e m a n a l g o r i t h mw h i c h a l s oh a st i m e c o m p l e x i t y0 f ，l ji sp r o p o s e d t h ep u r p o s eo fr e s e a r c h i n ga r tg a l l e r yp r o b l e m sm e n t i o n e da b o v ei s a p p l y i n g t h e s et h e o r i e st ot h ep r o b l e mo fr e c o n s t r u c t i n g3 ds c e n eu s i n gf i s h e y ep i c t u r e s w e c a ni m a g i n e ，w h e nw et a k ep i c t u r e sf o ras c e n eu s i n gaf i s h e y ec a m e r a ，w eu s u a l l y n l o v et h ec a m e r aa l o n gar e f e r e n c el i n ea n dt a k ep i c t u r e sf o r w a r d sa n db a c k w a r d s s u p p o s i n g t h e p o l y g o n f o r m e db ye a c hh a l fs c e n ea n dt h er e f e r e n c el i n ei sa s i n g l e s i d e m o n o t o n i co n e ，a n dt h ef o vo ft h ec a m e r ai s j u s t 18 0 。d u et ot h e l i m i t a t i o nb yr e f e r e n c el i n e w ec a nt h i n kt h a tt h ep r o b l e mo ft a k i n gp i c t u r e sf o ra s c e n e b yf i s h e y e c a m e r ai s e q u a l t ot h e g u a r d r e s t r i c t i o n a r t g a l l e r yp r o b l e m c o n s e q u e n t l y , t h es o l v i n go f a r tg a l l e r yp r o b l e mc o u l dp r o v i d et h e o r e t i c a lf o u n d a t i o n a n dm e t h o d sf o rt h ep r o b l e mo fh o wt os e l e c tt h em i n i m u mn u m b e ro fp o s i t i o n si n o r d e rt ot a k em i n i m u mn u m b e ro fp i c t u r e s ，f o rt h ep o l y g o n sf o r m e di nas c e n e ， im p l e m e n tt h ea l g o r i t h mt o g e tt h ep o s i t i o n so fd o u b l e g u a r d w h e nt a k i n g s t e r e o p i c t u r e sb yf i s h - e y ec a m e r a ，s e t t i n gt h ec a m e r ao nt h e s ep o s i t i o n sw o u l dg u a r a n t e e t w o p o i n t s ：e a c he d g e o nas c e n ec o u l db ec o v e r e db ya p a i ro f s t e r e of i s h 。e y ep i c t u r e s a n dt h en u m b e ro ff i s h e y e p i c t u r e i st h em l n i m u m ，a f t