采用粒子群优化的动态场景生成

MichaelHallerRynsonW.H.LauHideoSaitoRonghuaLiang(Eds.)

AdvancesinArtificialRealityandTele-Existence

16thInternationalConference

onArtificialRealityandTelexistence,ICAT2006Hangzhou,China,November29–December1,2006Proceedings

13

LectureNotesinComputerScience

CommencedPublicationin1973FoundingandFormerSeriesEditors:

GerhardGoos,JurisHartmanis,andJanvanLeeuwen

4282

EditorialBoard

DavidHutchison

LancasterUniversity,UKTakeoKanade

CarnegieMellonUniversity,Pittsburgh,PA,USAJosefKittler

UniversityofSurrey,Guildford,UKJonM.Kleinberg

CornellUniversity,Ithaca,NY,USAFriedemannMattern

ETHZurich,SwitzerlandJohnC.Mitchell

StanfordUniversity,CA,USAMoniNaor

WeizmannInstituteofScience,Rehovot,IsraelOscarNierstrasz

UniversityofBern,SwitzerlandC.PanduRangan

IndianInstituteofTechnology,Madras,IndiaBernhardSteffen

UniversityofDortmund,GermanyMadhuSudan

MassachusettsInstituteofTechnology,MA,USADemetriTerzopoulos

UniversityofCalifornia,LosAngeles,CA,USADougTygar

UniversityofCalifornia,Berkeley,CA,USAMosheY.Vardi

RiceUniversity,Houston,TX,USAGerhardWeikum

Max-PlanckInstituteofComputerScience,Saarbruecken,Germany

Creating Dynamic Panorama Using Particle Swarm Optimization

Yan Zhang1, Zhengxing Sun1,*, and Wenhui Li2

1

State Key Lab for Novel Software Technology, Nanjing University, P R China, 210093 2

College of Computer Science and Technology, Jilin University, P R China, 130012

szx@nju.edu.cn

Abstract. The dynamic panorama keeps the advantage of providing both full view of scene in static panoramas and the dynamics of the scene, which re-markably strengthens the reality of walkthrough. This paper presents a method to create dynamic panoramas. To gain the static panorama, a multi-resolution mosaic algorithm based on Particle Swarm Optimization (PSO) is first applied to a series of photographs at one fixed point. Moving objects in the scene are then captured periodically or stochastically using a video camera, and the re-sulted video clips are converted into video texture. Video texture is finally reg-istered with static panorama and combined into a compact representation. A panorama browser is also expanded to play video textures in addition to its original functions.

1 Introduction

Panoramic image is a method of making use of realistic images to get a full view panoramic space. Users can use ordinary cameras to take a serial of images surround-ing a scene. When there is overlap in these images, the system can then automatically create a 360 degrees panoramic image. This can provide users with the ability to ob-serve the virtual environment, walkthrough in the virtual environment, and perceive the environment from different viewpoints and directions voluntarily [1][2]. The panorama can be applied to various kinds of fields. For example, in virtual reality, it can be used to replace complicated 3D scene modeling and rendering [1]. It is also applied in the field of video compression, video transmission [3][4] and medical sci-ence [5], etc. Although the panorama is simple to construct and can represent static scenes naturally, it is unable to show dynamic scenes. Such monotone scenes make the panorama a very noticeable artifact. In order to overcome this disadvantage, we hope to add the dynamic scene into the panorama. Then an effective method to repre-sent dynamic scenes is needed. Continuous video is a good choice, but the limitation is that it is a very specific embodiment during a very specific period of time. So we need to repeat the video to generate a “timeless” one. However, this method can lead to visual discontinuity between the last frame and the first frame, and bad randomicity may also generate the repeated feeling. Many methods to solve this problem have been proposed. For example, Schodl [6] presented a video texture technique and

*

Corresponding author.

Z. Pan et al. (Eds.): ICAT 2006, LNCS 4282, pp. 676 – 685, 2006. © Springer-Verlag Berlin Heidelberg 2006

Creating Dynamic Panorama Using Particle Swarm Optimization 677

Kiran [7] presented flow-based video synthesis and editing technique. But they both cannot provide panorama or large view.

We present a novel method to create dynamic panoramas. We add dynamic scenes to the panorama to implement dynamic panorama. Our system first applies particle swarm optimization (PSO) based multiresolution mosaic algorithm to a series of im-ages taken at one fixed point to get the static panorama, then captures periodically or stochastically moving objects from the scene achieved by video camera, and then implements video texture to synthesize seamless video of arbitrary length, and finally video texture is registered with the static panorama to gain the dynamic panorama. The dynamic panorama preserves both the advantage of full-view walkthrough in static panoramas and the dynamics of the scene, which remarkably strengthens the reality of walkthrough.

2 Algorithm in Creating Panorama

When we synthesize panorama, two adjacent images can be overlapped by each other by approximately 50% because the tripod cannot achieve the absolutely horizontal condition, the camera may slope or turn over in the process of photographing. So one of the main problems for image mosaics is how to compute the accurate position where two images overlap. When we photograph, with the change of viewpoint and the automatic exposal, the light intensity varies greatly in different images for the same scene. So another problem for image mosaics is how to implement natural tran-sition between two registered images, which means without obvious seams or sharp transition. Therefore, how to produce the accurate mosaic view of 360° for the cir-cumstance using an abutting pair of images becomes our main problem [8][9][10]. In this paper, we make use of PSO to find an area, which contains sufficient objec-tive characters in one image and find corresponding area in another image using pat-tern matching, and then register these images. Registered image might have obvious seam and shade difference at the line of mosaics because of the original explosion difference of images. We apply multiresolution techniques for image mosaics and finally achieve image automated seamless mosaics.

2.1 Optimized Characteristic Block Extraction Based on PSO

In the first image, if we can confirm area A, then we can easily get area B using pat-tern matching methods in the other image, according to image overlapping theory, taking acceptable range of error into consideration. The more objective characters we are searching in area A, the more difference is required between this area and sur-rounding areas, and the better. Distance L2 is the simplest and the most frequently used distance function to compare the degree of similitude of two areas. The value of L2 is small when two areas are very similar to each other, and vise versa. For a certain area S, we can calculate four values of L2 by comparing itself with its surrounding up, down, left and right four areas of the same size, denoted as f1 , f2, f3, f4. The bigger of sum of f1, f2, f3, f4, the more difference between area S and its surrounding areas. We denote evaluation function of area S as:

(1) F= f1+f2+f3+f4

678 Y. Zhang, Z. Sun, and W. Li

The distance L2 of according areas is:

mnmn

fi=sqrt{∑∑[(R(pS)−R(pS))2+i

m=1n=1mn

Sk

l

mnSi

(2)

(G(p)−G(p

mnSi

))+(B(p

2

mnS)−B(p))]}

2

Where, S, Si are target area and its surrounding areas respectively; k, l are the width

mn

is and height of the area. R(),G(),B() are values of three primary colors of pixels. pS

mn

is the pixel with the coor-the pixel with the coordinate value (m,n) in area S andpS

i

dinate value (m,n) in area Si.

For any area S in the right half of the first image, the bigger of value F, the easier we can find an area with sufficient information needed for matching searching. How to find an area S containing sufficient objective characters is a better problem and we just need a satisfied result. Therefore, we can use PSO to searching for area S. PSO is an intelligent optimized method based on iteration and was firstly proposed by Ken-nedy and Eberhart [11], the basic idea of which originated from the simulation of simplified social systems.

When mosaic two images with overlapping areas, we randomly distribute 10 parti-cles in the right half of the first image. The initial position is the coordinate of several pixels and we define an initial velocity of these particles. Each particle is moving in the solution space. We can find a matching area with certain characters, by adjusting the moving direction and velocity of particles using fitness function. Each particle can decide an area of 20*20, which is used to search for areas with multiobjective charac-ters. Fig. 1 demonstrated how to find area S with sufficient characters in one image using PSO algorithm. The area in the green square is the area S we get.

Fig. 1. Optimized characteristic block extraction based on PSO. (a) is characteristic patch we found using PSO algorithm and (b) is the matching patch based on this characteristic patch.

Creating Dynamic Panorama Using Particle Swarm Optimization 679

Our PSO-based algorithms to search for characteristic areas can be described as follows:

(i). Randomly distributing 10 particles in the right half of the first area, initializing the original location of each particle and its original velocity;

(ii). Calculation fitness value of areas determined by each particle, using evaluation function F;

(iii). For each particle, comparing its current fitness value and the fitness value of the best location it ever passed and updating;

(iv). For each particle, comparing its current fitness value and the fitness value of the best location the whole particle swarm ever passed and updating; (v). Adjusting the velocity and location of particles;

(vi). The algorithm ends if termination condition, which is enough good location and biggest number of time of iteration, is met. Current global optimized position is the result. Otherwise, go to (ii). 2.2 Multiresolution Mosaic

If we simply mosaic two images together using PSO algorithm, there might be an obvious seam at the splicing tape, as shown in Fig. 2. It is not permitted. We can ap-ply multiresolution image mosaics to address this problem, in order to smooth the transition of the splicing area and get a high quality seamless image. In order to do so, we expand the original two images and apply multiresolution analysis on them to get a serial of octave like images, and at last we mosaic them at the same resolution and combine the images after image mosaics.

Fig. 2. An obvious seam image

2.2.1 Gaussian Pyramid Generation

We create a region image D, at the size of mosaic image. In the region, the centers found by PSO image mosaics algorithm is used as the boundary line. We fill white in the left side of the line and black in the right. Gaussian Pyramid is applied in the re-gion image D.

680 Y. Zhang, Z. Sun, and W. Li

The region image is represented initially at the level GD0. This image becomes the bottom or zero level of the Gaussian pyramid. Gaussian Pyramid level 1 contains image GD1, which is a reduced or low-pass filtered version of GD0. Each value within level 1 is computed as a weighted average of values in level 0 within a 5-by-5 win-dow. Each value within level 2, representing GD2, is then obtained from values within level 1 by applying the same pattern of weights.

GD0(i,j)=D(i,j)GDl(i,j)=

m=−2n=−2

∑∑w(m,n)G

22

D(l−1)

(2*i+m,2*j+n)

(3)

Where, level l satisfies 0G(i,j)=EXPAND(GDl(i,j))=/

Dl

m=−2n=−2

∑∑w(m,n)G

22

Dl

((i−m)2,(j−m)2)

(4)

where, 02.2.2 Laplacian Pyramid Generation

Two original images I1 and I2 Expand the size of the region image respectively, the extended part is filled by each original image. For the extended images I1 and I2, the Laplacian Pyramid of its RGB component chart is a sequence of error images L0,L1...LN. Each is the difference between two levels of the Gaussian pyramid. They are Laplacian Pyramid of R channel for the extended images I1 and I2.

LIN=GIN, LIl(i,j)=GIl(i,j)−GI(l+1)(i,j),0≤lwhere, N is the total number of levels in Laplacian Pyramid (in this paper N=4).

(5)

2.2.3 Image Mosaic

If we simply mosaic two images together using PSO algorithm, there might be an obvious seam at the splicing tape, as shown in Fig. 2. We can apply multiresolution image mosaics to address this problem, in order to smooth the transition of the splic-ing area and get a high quality seamless image. In order to do so, we expand the origi-nal two images and apply multi-resolution analysis on them to get a serial of octave

Creating Dynamic Panorama Using Particle Swarm Optimization 681

like images, and at last we mosaic them at the same resolution and combine the im-ages after image mosaics. As a result, we can get a seamless and smooth image.

The last images in image mosaics can be obtained by calculating the Laplacian Pyramid of its RGB system. We set the Laplacian Pyramid image in level l in each channel is LMl. We take the pixel value of GDl in level l in Gaussian Pyramid in the region image as a weight, based on which we can calculate the pixel value of LMl in its position by:

LMl=GDl(i,j)LI1(i,j)+(1−GDl(i,j))LI2(i,j)

(6)

Where, LI1 is the Laplacian Pyramid in the current level of the expanded original image Il , LI2 is the Laplacian Pyramid in the current level of the expanded original image I2. (i,j) is the position of the pixel. LI1 and LI2 can be calculated using formula (5). Each RGB channel of the last mosaic image can be rebuilt by decomposed N-level multi-resolution imageLM0,LM1,...,LM(N−1),LMN (LMN=GMN) In our paper, N=4. i.e.,

M=LM0+EXPAND(LM1+EXPAND(...(LM(N−1)+EXPAND(LMN))...)

(7)

After the rebuilt of each RGB channel image, we can calculate the RGB value and output the last resulting image, which is a clear and smooth seamless image, as shown in Fig. 3.

Fig. 3. Multiresolution Mosaic image

3 Representation for Dynamic Scenes

Finding a kind of an effective method to represent dynamic scene and joining it into the panorama can make it preserve the advantages of the full-view walkthrough of static panoramas and the reality of static scenes. Besides, it can make the scene pre-serve the dynamics, which can strengthen the reality of walkthrough. In this paper, we use the video texture technique that first presented by Schodl to represent dynamic scenes [6]. Video texture has qualities somewhere between those of a image and a

682 Y. Zhang, Z. Sun, and W. Li

video, which provides a continuous infinitely varying stream of images. While the individual frames of a video texture may be repeated from time to time, the video sequence as a whole is never repeated exactly. Video textures can be used in place of digital photos to infuse a static image with dynamic qualities and explicit action. Video texture analyzes a video clip to extract its structure, and synthesizes a new, similar looking video for arbitrary length. In the view of the observer, it is like a dy-namic endless video, bringing such kind of felling that it keeps on updating and vary-ing. When we use the video camera to capture periodically of stochastically moving objects in the scene, we have to make sure that the viewpoint is as the same as the one when we take the panorama, which means that they have to be taken at the same posi-tion. In order to implement the final register, we make the scene, which is taken by the video camera; have great repetition in the background with the panoramic images. The basic theory of synthesizing the video-camera-taken dynamic scenes according to video texture is: for a given video of dynamic texture, The fist step, we assume that there exist two similar frames of the video sequences, i and j ( j> i). Because the tran-sition from frame i to frame i+1 is the most natural, the transition from frame j to i+1 is also viable, which means it will not make a discontinuity in the sense of vision. We call frame j a transition point. After playing frame j, we can continue to play the suc-ceeding ward frame j+1, or instead we can continue to play frame i+1.As long as we have adequate similar frames in the video, we can continuously transitioning back-wards at the transition points and get a video with arbitrary length. The video texture from an input video sequence is to compute some measure of similarity between all pairs of frames in the input sequence. Once the frame-to-frame distances have been computed, it uses L2 distance:

Di,j=Ii−Ij

2

(8)

which denotes the L2 distance between each pair of images Ii and Ij. During the new video synthesis, the basic idea will be to create transitions from frame i to frame j anytime the successor of i is similar to j, that is, whenever Dij is small. Then we apply an exponential function to map distance Di+1，j to the probability of transitioning from frame i to frame j：

Pi,j=exp(−Di+1,j/σ),where:i>j

(9)

σ→, Pi,j will tend to 1 for the best transition, and 0 otherwise. In the processing As 0

of synthesizing the video texture, after playing frame i, we find out Pik，the max value in Pi,j (j≠i+1), then randomly select one frame from frame k and frame i+1 to be the next frame to play.

Once the first stage has identified good transitions for the video texture, it needs to decide in what order to play the video frames. The video texture has two ways of playing: random play and video loops. The first approach uses Monte Carlo technique to decide which frame should be played after a given frame, using the table of frame-to-frame similarities computed by the analysis algorithm. The second approach selects a small number of transitions to take in such a way that the video is guaranteed to loop after a specified number of frames. The resulting video loop can then be played in “loop” mode. For video texture played by traditional media players, loop is neces-sary. We apply video loops method to implement video texture in this paper.

Creating Dynamic Panorama Using Particle Swarm Optimization 683

4 Dynamic Panorama

After getting the static panorama and the video texture, we can organically combine them together to construct the dynamic panorama. In this paper we use particle swarm optimization (PSO) based multiresolution mosaic algorithm to register the video tex-ture and the static panorama. This process is very simple. We have already mentioned that the video texture and the panorama should be taken at the same viewpoint, and the produced sequence of video texture should be deposited into the database. So we take the first frame of the video texture to be registered with the static panorama, then apply particle swarm optimization (PSO) based multiresolution mosaic algorithm to compute the matched position of this frame with the static panorama, and then record it down and deposit it into the database. For each frame of the video, its background overlaps with the others’. In other words, each frame has a fixed matching position. So when we want to play dynamic scenes, we can read the corresponding matching position from the database to implement the matching between frames.

To display the dynamic panorama, there must be an appropriative panorama browser to implement the interactive virtual roaming. We have developed our own panorama browser. In addition to the functions of the original panorama browser, it has all functions of panorama browser and the new functions such as adding, match-ing, and playing the video texture to our browser.

When the video texture program is finished, the produced video texture has already been deposited into the database by frames. The dynamic panorama browser program first links the database and reads in the video registered data, which means position-ing the video texture in the panorama. Then, before displaying the panorama, the browser window will read the video frame which is to be played next into the buffer every 30 milliseconds. Do orthographic projection for the video frame, then mosaic it into the cylinder panorama according to the matching position. Finally, we calculate the anti-projection of the panorama with the video frame on it according the region that will be displayed in the window of the browser and get the color information, so as to finish the whole process of displaying the dynamic panorama.

Fig. 4 gives the static cylinder panorama without video texture and Fig. 5 shows some interfaces of dynamic panorama browser.

Fig. 4. Static cylinder panorama

684 Y. Zhang, Z. Sun, and W. Li

Fig. 5. The dynamic panorama. (a) interface of the browser without dynamic scenes. (b), (c), (d) interface of the browser at different moment with dynamic scenes added.

5 Conclusion

In this paper we present a method to create dynamic panoramas. We construct static panorama and video texture respectively, and add video texture to the static panorama to implement dynamic panorama. The dynamic panorama preserves both the advan-tage of full-view walkthrough in static panoramas and the dynamics of the scene, which remarkably strengthens the reality of walkthrough. We also proposed a new fast image mosaics algorithm based PSO multiresolution mosaics algorithm. Com-pared with other image mosaics algorithms, our approach is straightforward and easy to implement. We first use particle swarm optimization (PSO) to find a certain area, which contains sufficient objective characters, then we use pattern matching method to search the matching patch in another image and adjust image; at last, the mosaic image is created by a multi-resolution method. Experimental results testified that this algorithm is able to seamlessly stitch two overlapping images automatically. We have developed our own panorama browser. In addition to the functions of the original panorama browser, we add functions such as adding, matching, and playing the video texture to our browser, which makes the browser perfect.

Acknowledgement

The work described in this paper is supported by the grants from “the National Natu-ral Science Foundation of China” [Grants No. 69903006 and 60373065] and “the Program for New Century Excellent Talents in University of China” [Grant No. NCET-04-04605].

Creating Dynamic Panorama Using Particle Swarm Optimization 685

References

1. Szliski R., Shum H. Y., Creating full view panoramic image mosaics and environment maps, In: Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, California, 1997, 251-258.

2. Cai Y, Liu X.H., Wu E. H., Image-based rendering a technology for virtual reality system. Journal of Software. Vol 8 No.10, 1997, 721-728.

3. Lee K S., Fung Y. F., Wong K. H, et al., Panoramic video representation using mosaic im-age, In : Proceedings of CISST’99 , Las Vegas, USA, 1999, 390-396.

4. Hsu S., Anandan P., Hierarchical representations for mosaic based video compression. In : Proceedings of Picture Coding Symposium, San Francisco, 1996, 395-400.

5. Can A.,.Stewart C.V, Roysam B., Robust hierarchical algorithm for constructing a mosaic from images of the curved human retina. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Colorado, 1999, 286-292.

6. Schodl A. Szeliski R., video Textures, Proc SIGGRAPH’2000, New Orleans. Louisana. 2000, 4-498.

7. Kiran S. Bhat, S. M. Seitz, J. K. Hodgins, P. K.: Flow-based video synthesis and editing. ACM Trans. Graph., Vol .3, No.3, 2004, 360-363.

8. Feng J.B., Su Z.X., Liu X.P., An similar-curve based automatic mosaic algorithm of pano-ramic image. Chinese journal of computer, Vol. 26, No.11, 2003, 1604-1608.

9. Fang X. Y., Pan Z. G., Xu D.:. An improved algorithm for image mosaics. Journal of com-puter-aided design & computer graphics. Vol.15, No.11. (2003) 1362-1365.

10. Peter J. B., Edward H. A.: A Multiresolution spline with application to image mosaics.

ACM Transactions on Graphics, Vol. 2 No.4. (1983) 217-236.

11. Kennedy J., Eberhart R C.: Particle swarm optimization. In: Proc. IEEE int’l conf. On neu-ral networks. Vol. IV. IEEE, (1995) 1942-1948.