2.5D

perspective

M. Frydler , W.S. Mokrzycki

Institute of Mathematical Machines, 02-798, Warsaw, Krzywickiego 34, mfrydler@imm.org.pl Institute of Computer Science PAS, 01-237 Warsaw, Ordona 21, wmokrzyc@ipipan.waw.pl

Abstract:

This article concerns generating 2.5 D models of nonconvex polyhedral that are a complete representation ofthis polyhedral, according to viewing sphere with perspective concept. Those models are going to be used forvisual identification based on them and a scene depth map. We give a new conception and an algorithm for face-depended generation of multi-face views. It does not require any preprocessing or auxiliary mechanisms norcomplex calculations connected with them.

Key words:

Object visual identification, depth map, 2,5 D precise models, viewing sphere with perspective, viewing points,models completion state of viewing representation.

1 Introduction

Method of generating 2.5 D viewing representation of nonconvex polyhedral for object visualidentification described in [10] is based on the following idea: centrally generate views relative object featureschosen for identification, calculate one-view areas on viewing sphere which correspond with earlier generatedviews, check if whole viewing sphere is covered with one-view areas. If this cover is complete, generation ofviewing representation is finished. If not generate additional views corresponding with uncovered areas ofviewing sphere and again check if this cover is complete. Continue until complete viewing sphere cover isgenerated. Complete viewing sphere cover with one-view areas means that generated representation is complete.Methods from [16] and [18] are better. To achieve complete representation we don’t need to work in a loop.Complete representation is obtained by strict covering viewing sphere by one-view areas and controlling “edge”register (of no covered area).

When register is set to “empty” generation of model viewing representation is done. Generatedrepresentation is complete which follows from the generation method. However to achieve completerepresentation we have to calculate one-view areas on viewing sphere and operate them in a given order.Without their help it is not possible to get a complete set of views of virtual polyhedron model. On the top of thatdescribed methods are for convex polyhedral only. In this article we present a method for generating a completeviewing representation of nonconvex polyhedral. It’s more calculation efficient then described above.

2 Research assumptions

This research focuses on developing of a method and of an algorithm for generation of multi-view,nonconvex polyhedral representation. For representation generation we use viewing sphere with perspectiveconcept. For this following conditions have to be met:

1. Models are accurate - every model is equivalent to b-rep model.

2. 2.5 D models are used – this model has enough information to identify 3D object3. Models are viewing models – it is possible to identify object from any view

Use of a viewing sphere (Fig. 1) with perspective as a projection space allows simple view standardization.Uses: Recognition of objects not bigger then a few meters and distant (from the system) not more then 10 – 20meters.

Mentioned above uses allow to make certain assumptions about recognition system strategies. We assumefollowing steps of recognition processes

1. 2. 3. 4. 5. 6. 7.

Determining recognizable object types.

Definition of identification task(choose an object’s shell feature used for object identification)Generation of viewing models for each object system should identifyCreation of database containing all views of all modelsAcquisition of scene space data and visual data

Isolation of scene elements and their transformation to model structures stored in the databaseIdentification of objects by comparing them with database models.

3 View generation space – viewing sphere with perspective

Let object be a non convex, non transparent polyhedral without holes or pits. Let’s consider its faces si asfeatures areas, those areas will be used as a foundation for accurate viewing model determining. This model is aset of 2.5D accurate views, acquired through perspective projection from viewing sphere, according to the modelfrom [10] (Fig 1). This model is best for 3D scene data acquisition and gives identification system reliability.

Fig. 1 Concept of view sphere and “one view” areas.

The concept from [10] of generating 2.5 D view representation based on assumed generation space model is asfollows:

- Create a viewing sphere. Each object has its own sphere, for all views of this particular object

(fig 1).

- Circumscribe a sphere on a polyhedron. Sphere is small (radius r) and its center is at the

polyhedron center.

- On this sphere place a space cone with angle of flare 2α. This is the viewing cone. Vertex ofthis cone is a model viewing point PW. Distance between polyhedron’s center and modelviewing point is R. Viewing axis always goes through the sphere’s center.

- Unconstrained movement of cone vertex, where cone is tangent to the small sphere createslarge sphere with radius R. This sphere is called viewing sphere.

- Dependencies between values α , r and R and polyhedron vertices coordinates (Xvi,Yvi,Zvi)are:

r=maxi=1,.,k

R=

xvi2+yvi2+zvi2rsinα - Generate views, taking into account only object features selected for identification i.e. faces.

Faces visible in the viewing cone create a view, external edges from this view create view’scontour.

- Calculate one-view areas. Those areas correspond with particular views.

Complete set of views for a given polyhedron is obtained by covering of viewing sphere with

one-view areas. Views are generated in such a way that corresponding one-view areascompletely cover viewing sphere. Algorithm makes this approach complete.

Fig. 2 Covering viewing sphere with “one-view” areas.

Changing one view to the other is a visual event. This event occurs as a result of point PW movement.This event is manifested by appearance of a new feature in a view, disappearance of a feature or both.

4 Method’s basic concepts and assumptions

Consider nontransparent, nonconvex polyhedron. Its faces si are identification features. As a viewing spacetake a viewing sphere with perspective fig 1. View generation idea requires introduction of polyhedral naturalrepresentation concept.

4.1 Polyhedral natural representation

Let’s consider a polyhedron as a set of pyramids with top vertices in polyhedron geometrical center and withpolyhedron faces as bases. Pyramid top vertex is described by all polyhedron vertices and its base by a vertex

sequence of a corresponding face. This natural representation may be used for convex and nonconvex polyhedralalike.

In described here idea of generation of polyhedral view representation this natural representation leads

to acquiring of a complete set of views. This set I acquired through “views from above a face” mechanism. If weare able to get all polyhedron views from above all of its faces then we are able to create a complete set of viewsby adding together views from above all faces.4.2 Basic concepts and definitions

Viewing face SW is one of the polyhedron faces. During view generation each polyhedron face is a viewingface. Over viewing face we take and move current viewing point PW to generate all possible views from abovethis face

View is created by faces that are visible in the viewing cone at a certain viewing point PW position. Externaledges of a view create a viewing contour.

Viewing face pyramid is a pyramid described by the center of a viewing sphere and current viewing face.

Face SW Viewing potential PWSW is a sum of faces visible from above face SW. Edges between faces fromPWSW and other edges are called Face SW viewing potential boundary.

Viewing potential pyramid OPW has a common vertex with viewing face pyramid but has wider angle of flare.Complementary viewing cone SDW is a cone defined by current viewing axis (it’s collinear with its height)and has an opposite direction of flare then the viewing cone. It intersects viewing cone with angle Π/2, so itsangle of flare is Π/2-α.

Complementary, boundary cone is a cone that complements cone DSW. Its angle of flare is twice wider thanin cone DSW.

Viewing representation is created for the polyhedral with following features: nonconvex polyhedral with nopits, if a face is intersected by viewing ax it’s visible.

5 Visual problem and its solution

5.1 Problem analysis

Lets define our problem: Generate a 2.5 D complete view model of a nonconvex polyhedron. Number ofpolyhedron faces m >=6. Generation is conducted based on viewing sphere with perspective.

Divide this problem into as many sub problems as the number of our polyhedron faces. Each sub problemis generating all possible polyhedron views from above current face SW. Lets take tangent vector for each faceand translate it to center of view sphere. Sub “view task” is about to finding versors (for current face) that eachof them lay inside complementary viewing cone. This cone certainly consist current face versor.

So let’s take face SW for which we want to generate complete set of 2.5D views. We need to recognize itspyramid OSW, its viewing potential and the pyramid of this potential OPWsw. Next we need to recognizenormal versors of polyhedron faces that lay inside of pyramids OSWsw and OPWsw.

During our further task we will be interested only in such faces which tangent versors lay inside ofpyramids OSWsw and OPWsw. It is proper because if some versor lay outside OSWsw its face is invisible onlyif view axis lay inside OSWsw. However, when vector lay inside OPW, it doesn’t mean that sw face (whichdefines pyramids) is visible. It depends on its surroundings. This face can be covered by other visible face(which belongs to viewing potential). Information, about presents (inside contour potential view) of faces witchtangent vectors lay outside potential view pyramid, is very important. Existing of such faces mean that insideOPWsw lay sk face which is invisible in every “view above sw face”. This information helps us to define visiblecondition for hollow polyhedron.

5.2 Generation of views from above the face – creation of complementary cones

Let’s take a nonconvex polyhedron for which we won’t to generate views. We have to calculate normalversors vni of all faces and anchor them in polyhedron center. Next we need to circumscribe a sphere on thispolyhedron and place both in a viewing sphere with an appropriate radius. Then we should choose onepolyhedron face from which we will start generating views. Next we have to do the following steps:

• •

Identify pyramid OSW and calculate pyramid OPWsw

OSW

Find normal versors

∑vn

j

in

kswfaces inside OSW cone

OPWsw

• Find normal versors

∑vn

i

pkswfaces inside OPWsw cone in

Further calculations we will constrain to normal versors from cone OPWSW. Idea of generating views

from above a face which we will use here relays on finding all views that we can get with each versor fromcone OSW and removing duplicate views.

OPWsw

Let’s go to execution of the above idea. First we have specify which versors from the set

OSW

∑vn

i

may go into

views with one vector from the set

∑vn

j

. The most inaccurate activity mentioned here is reciprocal existence

of faces in one view i.e. faces sj (with normal versor vnj ) with rest of the faces si from the viewing potential ofthis (sj) face. One way of doing this is “rolling” of complementary cone around normal versor vnj andrecognition of “entering” and “leaving” this cone by other normal versors vni.

Lets go through possible configurations of complementary, boundary cone, versors and faces:1. if complementary cone is empty there are no other faces accept for face sj

2. if in complementary cone of versor vnj there are normal versors of all neighboring (with sj) faces, sj can not

appear in a view on its own

3. if we place around versor vnj complementary, boundary cone then in this cone we will find only versors

that go into view with versor vnj. Doing this for all versors corresponding with viewing face pyramid wewill get subsets:

∑

SDG(vn1)

,.,∑

SDG(vnj)

,.,∑

SDG(ksw)

contains faces that coexist

in a view with versor vnj

OSW

4. versors from set

∑vn

i

that have angle between them smaller than Π/2-α can not exist in the same view

5. All possible views with versor vnj we can achieve by “rolling” complementary cone. Executing this task for

each versor vnj we will get complete set of combinations of views with versors in OSW.

So the algorithm for finding set of views for viewing face could look like this.

From

∑

OSWsw

take one versor vni i.e. vnj and create (from set

∑

OPWsw

) a set

wid

∑

wid

vnjof versors that can exist in a view with versor vnj. Let number of versors in ∑

rd

vnj be kj.

Next calculate angular distances between versors vni and versor vnj and order them in an ascending manner:

r1(vn1),.,rd(vnk) . Versor vi which is most distant is going to be used for definition of scanning

direction KOS. For this direction scanning cone will start turning around versorvnj. Now let’s start calculatingthe views for versorvnj.5.3 Algorithm loop PA

In set

∑

SDGvnj

find a versor closest to generator of the scanning cone (vni2) from the front side (in the

direction of cone movement). Do the same from the back side (opposite to the direction of cone movement).During cone movement versor that is closer to the generator will trigger visual event first. When this happensstop cone movement and register new view widi+1(vnj).

∑OSW

we can move to the next versor from the set ∑

If there are no more versors in set

beginning of the algorithm loop.

SDGvnj

we are done generating views for versor vnj. Now. If there are still versors in

sw

∑

SDGvnj

go to the

As you can see scanning round versors from set

∑

SDGvnj

is based on executing a loop around

each versor with scanning cone. During this task we check if any visual events were triggered . .

6 Algorithms

6. 1 Algorithm of generating views.

We assume following -View face lay inside View (because of type of polyhedron).

1. Algorithm of computing view potential of sj face

1 Designate vectors of OSWsw and OPWsw.

2 For each sj versor, which belong to OSWsw, build complementary cone.3 Designate versors that lay inside complementary cone.

2. Algorithm of computing views

1 Rotate complementary cone around first versor which lay inside OSWsw and note every visual event. Thisevent is manifested by appearance of a new versor inside OSWsw or by disappearance of versor whichpreviously lay inside OSWsw.

2 Repeat previous step on every versor which lay inside OSWsw.

3 Remove events that repeat itself (events are considered the same when they consist of same set of vectors).

9 Summary

This approach to generating 2.5 D models of nonconvex polyhedral requires farther studies and researches. Ournext task is to implement this set of algorithms. Result will be presented.

8 REFERENCES

1987

[1] Connell J.H., Brady M.: Generating and generalizing models of visual objects. AI, 31, 159-183.1990

[2] Bowyer K.W., Dyer Ch.R.: Aspect Graphs: An Introduction and Survey of Recent Results. SPIE, 1395.1991

[3] Gigus Z., Canny J., Seidel R.: Efficiently computing and representing aspect graph of polyhedral object.IEEE Trans. PAMI, 13(6), 542-551.1993

[4] Zhank S., Sullivan G.D., Baker K.D.: The automatic construction of a view-independent relational modelfor 3D object recognition. IEEE Trans. PAMI, 15(6). 531-544.1995

[5] Leonardis A., Kovacic S., Pernus F.: Recognition and pose determination of 3D objects using multiple views.Proc. CAIP'95, LNCS 970, Springer-verlag, Berlin, 778-783.

[6] Suk T., Flusser J.: The projective invariants for polygon. Proc. CAIP'95, LNCS 970, Springer-Verlag,729-734.1996

[7] Arbel T., Ferrie F.P.: Informative views and sequential recognition. Proc. ECCV'96, Cambridge, UK, April,469-481.

[8] Hlavac V., Leonardis A., Werner T.: Automatic selection of reference views for image-based scenerepresentation. Proc. ECCV'96, Cambridge, UK, April, 526-535.1997

[9] Arbel T., Ferrie F.P.: Informative views and sequential recognition. Proc. ECCV'96, Cambridge, UK, April,469-481.

>󰀔󰀓@'󰀅ENRZVND0󰀑󰀏0RNU]\\FNL:󰀑6󰀑󰀝0XOWL󰀐YLHZPRGHOVRIFRQYH[SRO\\KHGUDO󰀑0*󰀉9󰀏󰀙󰀋󰀗󰀌󰀏󰀗󰀔󰀜󰀐󰀗󰀘󰀓󰀑[11] Madsen C.B., Christensen H.I.: A viewpoint planning strategy for determining true angles on polyhedralobjects by camera alignment. IEEE Trans. PAMI, 19(2), 158-163.

[12] Shimshoni I., Ponce J.: Finite-resolution aspect graphs of polyhedral objects.1998

>󰀔󰀖@'󰀅ENRZVND0󰀑󰀏0RNU]\\FNL:󰀑6󰀑󰀝$QHZYLHZPRGHORIFRQYH[SRO\\KHGUDOZLWKIHDWXUHGHSHQGHQWYLHZ󰀑MG&V, 7(1//2), (Proc. GKPO'98, Borki, Poland, 18-22 May), 325-334.

>󰀔󰀗@'󰀅ENRZVND0󰀑󰀏0RNU]\\FNL:󰀑6󰀑󰀝&RQGLWLRQVRQPRGHOVIRUREMHFWYLVXDOLGHQWLILFDWLRQ󰀑3URF󰀑$&6󰀊󰀜󰀛󰀏Szczecin, 19-20 Nov.,

[15] Kovacic S., Leonardis A.: Planning sequences of views for 3D object recognition and pose determination.PR, 31(10), 1407- 1417.1999

[16] Kowalczyk M., Mokrzycki W.S.: Determining complete object's view model by joining one-view areas.Proc. ACS'99, Szczecin, 18-19 Nov., 68-72.2001

[17] Kowalczyk M., Mokrzycki W.S.: Obtaining complete 212D view representation of polyhedral using conceptof seedling single-view area. Submitted to CV &IU.2002

[18] Kowalczyk M., Mokrzycki W.S.: A new method of finding one-view areas and tight view sphere covering.Proc. ICCVG'02, Zakopane, Poland, Sept. 25-29, 443-449.