## Abstract

A novel approach for fast generation of video holograms of three-dimensional (3-D) moving objects using a motion compensation-based novel-look-up-table (MC-N-LUT) method is proposed. Motion compensation has been widely employed in compression of conventional 2-D video data because of its ability to exploit high temporal correlation between successive video frames. Here, this concept of motion-compensation is firstly applied to the N-LUT based on its inherent property of shift-invariance. That is, motion vectors of 3-D moving objects are extracted between the two consecutive video frames, and with them motions of the 3-D objects at each frame are compensated. Then, through this process, 3-D object data to be calculated for its video holograms are massively reduced, which results in a dramatic increase of the computational speed of the proposed method. Experimental results with three kinds of 3-D video scenarios reveal that the average number of calculated object points and the average calculation time for one object point of the proposed method, have found to be reduced down to 86.95%, 86.53% and 34.99%, 32.30%, respectively compared to those of the conventional N-LUT and temporal redundancy-based N-LUT (TR-N-LUT) methods.

©2013 Optical Society of America

## 1. Introduction

Thus far, a number of approaches for generation of the computer-generated holograms (CGHs) of three-dimensional (3-D) objects have been proposed [1–9]. Among them, the ray-tracing method [1,2] has been known as a rigorous approach, but it has a drawback of the computational complexity because it may require one-by-one calculation of the fringe patterns for all object points. Besides, the look-up-table (LUT) method [10] shows a much enhanced computational speed because all elemental fringe patterns (EFPs) corresponding to point source contributions from each of the possible locations in the object volume are pre-calculated and stored in the LUT. However, it suffers from a great drawback of the enormous memory capacity for the LUT [11].

Recently, a novel-look-up-table (N-LUT) method to dramatically reduce the total number of pre-calculated interference patterns required for generation of the digital holograms as well as to maintain the fast computational speed of the conventional LUT was proposed [12]. In this approach, a 3-D object is approximated as a set of discretely sliced image planes having different depth. Then, only the fringe patterns of the center-located object points on each object plane, which are called 2-D PFPs, are pre-calculated, and stored in the N-LUT, so the memory size of the N-LUT could be reduced down to the order of gigabytes (GB) from the order of terabytes (TB) of the conventional LUT for the case of a 3-D object having image points of 500 × 500 × 256 [12].

At this time, the most challenging issues in the N-LUT method seem to be the memory capacity and the computational speed. In fact, for potential application of the N-LUT to the future hologram-based information terminals, its memory capacity and computation time need to be further reduced down to the order of megabytes (MB) and milliseconds per frame, respectively.

For reduction of the memory capacity, recently a new method called one-dimensional N-LUT (1-D N-LUT), in which GB-sized memory capacity of the conventional N-LUT can be decreased down to the order of MB, was proposed by employing a new concept of 1-D sub-PFPs decomposed from the conventional 2-D PFPs [13]. So far, this method might be regarded as the most effective approach for generation of the hologram patterns with a very moderate memory size. A couple of other memory reduction methods based on the center-symmetry property of the 2-D PFPs were also reported, in which only a quarter or a half part of the PFPs is stored for the N-LUT [14,15].

Moreover, many kinds of algorithmic and hardware approaches [16–20] were also proposed for accelerating the computational speed of the N-LUT. As an algorithmic approach, a spatial redundancy-based N-LUT method called SR-N-LUT [16] was proposed, in which spatially redundant data of 3-D objects are extracted using the run-length encoding (RLE) algorithm and re-grouped into the *N*-point redundancy map according to the number of adjacent object points having the same 3-D value. Then, *N*-point PFPs are generated and stored for accelerated computation of the hologram patterns of the 3-D objects.

As other algorithmic approaches, a line redundancy-based N-LUT method called LR-N-LUT [17] was also presented, in which inter-line redundant data of 3-D objects are removed using the differential pulse-code-modulation (DPCM) algorithm, as well as a block redundancy-based N-LUT method called BR-N-LUT was proposed [18], where spatially redundant data of a 3-D object are extracted in a 2-D block with the 2-D RLE algorithm and re-grouped into the *N* × *N*-point redundancy map according to the number of adjacent object points having the same 3-D value.

In addition, a couple of hardware approaches for fast generation of hologram patterns of the 3-D objects have been also presented, in which they just tried to implement the N-LUT on a field programmable gate array (FPGA) or a graphic processing unit (GPU) [7,20].

On the other hand, for the 3-D moving objects, a temporal redundancy-based N-LUT called TR-N-LUT was also proposed, where the temporal redundancy between the two consecutive video frames of the 3-D objects are removed by using the DPCM algorithm, and only the difference image is applied to the N-LUT [19]. However, the difference between two video frames gets bigger as the 3-D object moves faster, so the compression efficiency of the employed DPCM algorithm might be sharply dropped. Thus, another approach for efficient generation of the video holograms of 3-D moving objects needs to be developed.

By the way, a motion-compensation method has been widely employed in compression of the conventional 2-D video data because of its ability to exploit high temporal correlation between successive video frames [19]. In this technique, by compensating the object’s motion with an amount of estimated motion-vectors, video data to be processed could be remarkably reduced.

Here it must be mentioned that the conventional N-LUT method has a unique property of shift-invariance unlike other hologram-generation methods, which means the PFPs for each object point employed in the N-LUT may remain unchanged regardless of the location of the object points [12,19]. Basically, in the N-LUT, hologram patterns for object points on each image plane can be obtained by simply shifting the pre-calculated PFP for the center object point according to the dislocated values from the center to those object points. Therefore, for the case of 3-D moving objects, a lot of redundant object data expects to be removed just by applying this concept of motion compensation to the shift-invariant N-LUT method.

Accordingly, in this paper, we propose a novel motion compensation-based N-LUT method called here MC-N-LUT for fast generation of the video holograms of 3-D moving objects. That is, in the proposed method, motion vectors of the moving object are extracted between the two consecutive video frames, and using them object’s motion can be compensated at each frame. Then, only the hologram pattern for the difference image between the motion-compensated object image of the previous frame and the object image of the current frame is computed, then it is added to that of the motion-compensated object obtained by shifting the hologram pattern of the previous frame with the estimated motion vectors.

In addition, experiments with three kinds of 3-D video sequences are performed, and the results are compared to those of the conventional N-LUT and the TR-N-LUT methods in terms of the number of calculated object points and the computation time.

## 2. CGH generation of a 3-D object with the N-LUT

In the conventional N-LUT method [12], the number of fringe patterns to be stored in the LUT can be dramatically reduced by employing a new concept of PFPs, which results in a remarkable reduction of the required memory capacity of the N-LUT.

Figure 1 shows a geometric structure to compute the Fresnel fringe pattern of a volumetric 3-D object. Here, the location coordinate of the *p ^{th}* object point is specified by (

*x*,

_{p}*y*,

_{p}*z*), and each object point is assumed to have an associated real-valued magnitude and phase of

_{p}*a*and

_{p}*φ*, respectively. Also, the hologram pattern of a 3-D object is assumed to be positioned on the depth plane of

_{p}*z*= 0 [12]. In fact, a volumetric 3-D object can be treated as a set of object planes discretely sliced along the

*z*-direction, in which each object plane having a fixed depth is approximated as a collection of self-luminous object points of light.

In the N-LUT method, only the fringe patterns of the object points located on the center of each object plane are pre-calculated, called principal fringe patterns (PFPs) and stored in the N-LUT. Therefore, the unity-magnitude PFP for the object point (0, 0, *z _{p}*) which is positioned on the center of an object plane with a depth of

*z*,

_{p}*T*(

*x*,

*y*;

*z*), can be defined as Eq. (1) [12].

_{p}where the wave number *k* is defined as *k* = 2*π*/*λ*, in which *λ* and *θ _{R}* means the free-space wavelength of the light, and the incident angle of the reference beam, respectively. In addition, the oblique distance

*r*between the

_{p}*p*object point of (

^{th}*x*,

_{p}*y*,

_{p}*z*) and the point on the hologram plane of (

_{p}*x*,

*y*, 0) is also given by Eq. (2).

Then, the fringe patterns for other object points on each object plane can be obtained by simply shifting this pre-calculated PFP according to the dislocated values from the center to those object points. Figure 2 shows the CGH generation process of the N-LUT method for two object point *A*(-*x*_{1}, *y*_{1}, *z*_{1}) and *B*(*x*_{2}, -*y*_{2}, *z*_{1}) at an arbitrary depth plane of *z*_{1}. Here the object point *A*(-*x*_{1}, *y*_{1}, *z*_{1}) is displaced from the center point *O*(0, 0, *z*_{1}) on the object plane of *z*_{1,} so the hologram pattern for this point can be obtained by simply shifting the pre-calculated PFP for the center point contained in the N-LUT with amounts of *-x*_{1} and *y*_{1} along the direction of *x* and *y*, respectively, which is shown in Fig. 2(b). Following the same procedure mentioned above, the hologram pattern for the object point *B*(*x*_{2}, -*y*_{2}, *z*_{1}) located on the same object plane can be also obtained just shifting the pre-calculated PFP.

Accordingly, this process is performed for all object points and then its corresponding shifted versions of PFPs are obtained and added together to get the final CGH pattern for an arbitrary 3-D object. In addition, the CGH pattern for all object point should be tailored from this region overlapped with all shifted versions of PFPs as a pre-determined size as shown in Fig. 2(c).

Accordingly, in the N-LUT method, the CGH pattern of a 3-D object, *I*(*x*, *y*) can be expressed in terms of the shifted versions of pre-calculated 2-D PFPs of Eq. (1), which is shown in Eq. (3)

where *N* is the number of object points. Equation (3) shows that the CGH pattern of a 3-D object can be obtained just by shifting the PFPs depending on the displaced values of image points from the center points on each image plane and adding up them all.

## 3. Shift-invariance property of the N-LUT method

As mentioned above, the PFPs for each object points on each object plane of the N-LUT can be obtained by simply shifting the pre-calculated PFP for the center object point according to the dislocated values from the center to those object points [12].

Figure 3 shows a unique shift-invariance property of the N-LUT method. As shown Fig. 3(a), the hologram pattern for the object point *A*(0, 0, *z*_{1}) represented by ‘PFP-*A*’ is recorded as a form of Fresnel-zone-plate(FZP) in the N-LUT method. Here, the center of ‘PFP-*A*’ is positioned at (0, 0, 0) as shown in Fig. 3(b), so the object point *A'* reconstructed from this hologram pattern of ‘PFP-*A*’ is also located at (0, 0, *z*_{1}).

Now, if this hologram pattern of ‘PFP-*A*’ is shifted to the location of (*x*_{1}, 0, 0) along the *x*-direction, then the object point *A”* reconstructed from the shifted version of ‘PFP-*A”*’ is also moved to the new location of (*x*_{1}, 0, 0). At the same manner, in case the ‘PFP-*A*’ is shifted to the location of (0, *y*_{1}, 0) along the *y*-direction, then the object point *A”'* reconstructed from the shifted version of ‘PFP- *A”'*’ is also moved to the new location of (0, *y*_{1}, *z*_{1}).

In other words, in the N-LUT method, if an object point moves, then its corresponding PFP is also shifted and the object point reconstructed from this shifted PFP is found to be at the moved location, which may confirm the shift-invariance of the N-LUT method. That is, hologram patterns for the moved object points could be computed by simply shifting the corresponding PFPs with moving amounts. Based on this unique property of the N-LUT method, various types of spatial redundancy-based N-LUT methods could be realized [16–18].

Here, this unique shift-invariance property of the N-LUT can be directly applied to the 3-D moving object because a 3-D object is assumed to be composed of a set of object points. That is, as shown in Fig. 4, if the center of a 3-D object moves by *x*_{1} and *y*_{1} along the *x* or *y* directions, respectively on a fixed object plane, the hologram patterns corresponding to each of these shifted objects can be generated by simply shifting the hologram pattern *I _{A'}* (

*x*,

*y*) for the object located at (0, 0,

*z*

_{1}) with amounts of

*x*

_{1}and

*y*

_{1,}respectively, which are shown in Eq. (4) and (5).

where *I _{A'}* (

*x*,

*y*),

*I*(

_{A”}*x*,

*y*) and

*I*(

_{A”'}*x*,

*y*) represents the CGH patterns for the 3-D object at the location of

*A'*,

*A”*and

*A”'*, respectively

Therefore, if the shifted distance of the 3-D object in an input scene is extracted, then with this value the hologram pattern for the moved 3-D scene can be generated without additional calculation of its hologram pattern by taking advantage of the shift-invariance property of the N-LUT method.

Now, this shift-invariance property of the N-LUT method might be directly matched to the motion-compensation concept mostly employed in compression of video data. That is, by applying this motion compensation scheme to the N-LUT method having a shift-invariance property, a lot of redundant video data of the 3-D moving object expects to be reduced, which results in a fast generation of the 3-D video holograms.

In this new approach, motion vectors of a 3-D moving object are extracted between two the consecutive video frames, and with these estimated motion vectors, moving distances of the 3-D object at each frame are compensated. Then, through this process of motion-compensation, 3-D object data to be calculated for its video holograms could be massively reduced, which may result in a noticeable increase of the computational speed.

## 4. Motion estimation and compensation

Motion-estimation technique may extract the movement of the object in a video sequence to obtain motion vectors representing the estimated object motion. Furthermore, motion-compensation technique uses the knowledge of object motion obtained by motion estimation to compress the video data. For example, in inter-frame coding, motion-estimation and compensation have become powerful techniques to eliminate the temporal redundancy due to high correlation between consecutive frames [21,22]. That is, massive reduction of video data can be possible using this process of motion-estimation and compensation.

Figure 5 shows a process of motion-vector extraction of a car object between the two consecutive video frames using a block-matching technique [21,22]. Each frame image is divided into a matrix of ‘macro blocks’ and then motion vectors for each macro block are extracted.

As seen in Fig. 5, a macro block *A*(*x*_{1}, *y*_{1}) in the previous frame is assumed to be moved to *B*(*x*_{2}, *y*_{2}) in the current frame. That is, the movement amount of the point from *A* to *B* is *d _{x}* and

*d*in the

_{y}*x*and

*y*direction, respectively. Therefore, the shifted point

*B*can be expressed as follows.

where *d _{x}* and

*d*are designated as the motion vectors of the car object in the

_{y}*x*and

*y*direction, respectively, and

*Δt*means the time interval between two frames. That is, the motion-compensated object image can be obtained by using the object image of the previous frame and the estimated motion vectors.

There are many motion estimation algorithms such as ‘Exhaustive search (ES)’, ‘Three step search (TSS)’, ‘Simple and efficient TSS (SES)’, ‘Four step search (4SS)’, ‘Diamond Search (DS)’ and ‘Adaptive rood pattern search (ARPS)’, etc [23].

In these methods, to extract the movement of the object, a process of block matching is performed for other macro blocks in a searching area. The searching area for a good macro block match is constrained up to *R* (*R _{x}, R_{y}*) pixels on all four sides of the corresponding macro block in the previous frame as shown in Fig. 5. Here

*R*is called as the search parameter. Larger motions may require a larger

*R*, and the larger the search parameter the more computationally expensive the process of motion estimation becomes.

The matching of one macro block with another is based on the output of a cost function. The macro block that results in the least cost is the one that matches the closest to current block. There are various cost functions, of which the most popular and less computationally expensive is ‘Mean absolute difference (MAD)’ or ‘Mean squared error (MSE)’ given by Eq. (7) and Eq. (8), respectively [23].

where *M* is the side of the macro bock, *C _{ij}* and

*R*are the pixels being compared in the current and the reference macro blocks, respectively.

_{ij}In video compression techniques, the most computationally expensive and resource hungry operation in the entire compression process might be motion estimation. In the proposed method, consideration of computationally expensive for motion estimation and compensation is also important, because the time for these processing must be included to the total hologram computation time. If an accurate motion-estimation algorithm is employed, it may require a lot of time for estimation the motion vector. On the other hand, if we use a fast motion-estimation algorithm, enough reduction of the object points might be not possible due to its roughly estimated moving vectors. Therefore, an adequate motion-estimation algorithm must be selected by simultaneous consideration both of its estimation time and accuracy in the practical application.

## 5. Proposed method

Figure 6 shows an overall block-diagram of the proposed motion-compensation-based N-LUT (MC-N-LUT) method which largely consists of four steps. First, each 3-D object is segmented from the input 3-D scene of the current frame. Second, motion vectors of the 3-D objects between the previous and the current frames are extracted for each segmented intensity and depth image of the 3-D object. Third, the motion-compensated object image is obtained using the object image of the previous frame and the estimated motion vectors, and the difference image between the motion-compensated object of the previous frame and the object of the current frame is calculated. Fourth, the CGH patterns for each segmented object image are shifted along the *x* and *y* directions based on the estimated motion vectors. Moreover, the CGH pattern for the difference image obtained above is calculated with the N-LUT, and CGH patterns for each segmented object image are all added to find the final CGH pattern for the 3-D scene of the current frame and stored for the next frame.

#### 5.1 Segmentation of each object from the input 3-D scenes

In general, input 3-D scenes may contain several objects with different movements. To extract the motion vectors for each moving object, a process of object segmentation is needed. There are many image segmentation algorithms including the thresholding and the region-growing techniques [21,22].

In this paper, a thresholding method is employed for segmenting the 3-D moving objects from the input 3-D scenes as shown in Eq. (9).

where *IN* and *DEP* mean the intensity and depth value of the current frame, respectively. *IN _{seg}*

_{1},

*IN*

_{seg}_{2}and

*DEP*

_{seg}_{1},

*DEP*

_{seg}_{2}and

*T*also represent the intensity and depth values of each segmented object image and the threshold value, respectively.

Figure 7 shows a process of object segmentation by adaptation of the threshold level in the depth map. Figure 7(a) shows the input 3-D image composed of two objects of ‘House’ and ‘Car’, where ‘Car’ and ‘House’ objects are located at the front and backside of the 3-D input image, respectively. As seen in the depth-dependent histogram of the 3-D input image of Fig. 7(b), the depth values of each object can be separately grouped. That is, the depth values of the ‘Car’ and ‘House’ objects might be distributed from 40 to 80 and from 130 to 150, respectively. Therefore, the threshold value can be set at 100 in this 3-D input scene.

The finally segmented object images for ‘House’ and ‘Car’ based on the depth-dependent thresholding technique are shown in Fig. 7(c)

In this paper, three kinds of 3-D video scenarios consisting of 50 frames are computationally generated as the test videos as shown in Fig. 8, in which each frame has a resolution of 500 × 500 pixels and each video is composed of a fixed object of ‘House’ and a moving object of ‘Car’ having different depths.

In the first video scenario, called here ‘Case I’, the ‘Car’ object is moved along the straight line from the left to the right direction. On the other hand, in the second and third video scenarios, called here ‘Case II’ and ‘Case III’, respectively the ‘Car’ object is moved along the curved lines from the left to the right direction having different curving radii.

That is, for both of ‘Case II’ and ‘Case III’, the ‘Car’ object may rotate when it drives along the lanes, so the depth range of the ‘Car’ object may be changed on the frame-by-frame basis. Figure 9 shows the segmented object images of the ‘House’ and the ‘Car’ for each case of test videos of Fig. 8. In this paper, *T* has set to be 100 for three cases based on depth value.

#### 5.2 Extraction of moving vectors for each segmented 3-D object

The motion vectors may relate to the whole image or the specific parts, such as rectangular blocks and arbitrary shaped objects [21,22]. In this paper, motion vectors for arbitrary objects are selected because an operation of object-based hologram generation is employed in the proposed method.

Figure 10 shows a process of motion estimation for each segmented 3-D object, in which Fig. 10(a)-10(d) describe the outlines and the center points of each segmented object image for the two consecutive frames in the input 3-D video sequence. As you can see in Fig. 10(a) and (c), the center points of the segmented ‘Car’ object at the two consecutive frames are given by (*x _{c}*

_{1},

*y*

_{c}_{1}) and (

*x*

_{c}_{2},

*y*

_{c}_{2}), which means the ‘Car’ is moved from the location of (

*x*

_{c}_{1},

*y*

_{c}_{1}) to the location of (

*x*

_{c}_{2},

*y*

_{c}_{2}).

Figure 10(e) also shows the overlapped object image of Fig. 10(a) and 10(c), and the motion vectors between the two consecutive frames. Here, the motion vectors of the ‘Car’ object (*d _{xc}*,

*d*) can be represented by

_{yc}That is, ‘Car’ object is shifted by *d _{xc}* and

*d*along the

_{yc}*x*and

*y*direction, respectively between the two consecutive frames.

On the other hand, the center points of the segmented ‘House’ object at the two consecutive frames are given by (*x _{h}*

_{1},

*y*

_{h}_{1}) and (

*x*

_{h}_{2},

*y*

_{h}_{2}) as shown in Fig. 10(b) and 10(d).

As seen in Fig. 10(f) representing the overlapped object image of Fig. 10(b) and 10(d), the segmented object of ‘House’ was originally fixed at (*x _{h}*

_{1},

*y*

_{h}_{1}) without a movement, so its motion vectors of (

*d*,

_{xh}*d*) must be fixed to (0, 0).

_{yh}#### 5.3 Motion-compensation of the moving object and derivation the difference image

Figure 11 shows a process of motion-compensation of the segmented ‘Car’ object of the previous frame using the motion vectors estimated above and derivation of the difference image between the motion-compensated ‘Car’ object of the previous frame and the ‘Car’ object of the current frame. That is, Fig. 11(a) and 11(b) shows the ‘Car’ object images segmented from the previous and current frames, respectively.

As seen in Fig. 11(a) and 11(b), the center points of the segmented object images of ‘Car’ are given by (*x _{c}*

_{1},

*y*

_{c}_{1}) and (

*x*

_{c}_{2},

*y*

_{c}_{2}) because the car has been moved from the location of (

*x*

_{c}_{1},

*y*

_{c}_{1}) to that of (

*x*

_{c}_{2},

*y*

_{c}_{2}). Figure 11(c) and (d) also show the shifted version of Fig. 11(a) and the difference image between the motion-compensated ‘Car’ object of the previous frame and the moved ‘Car’ object of the current frame.

Here, we can obtain the object image of the current frame by compensating the difference image of Fig. 11(d) to the motion-compensated object image of the previous frame shown in Fig. 11(c). Therefore, by shifting the hologram pattern for the ‘Car’ object of Fig. 11(a) by an amount of the estimated motion vectors, the hologram compensation for the difference image of Fig. 11(d) can be performed and the hologram pattern for the ‘Car’ object of the current image can be obtained.

Figure 12 shows the motion-compensated object images of the previous frame using estimated motion vectors for three kinds of test 3-D video scenarios; ‘Case I’, ‘Case II’ and ‘Case III’. In the test 3-D videos, ‘House’ and ‘Car’ objects are assumed to be fixed and moving from the left to the right direction, respectively.

Figure 13 shows the difference images between the motion-compensated object images of the previous frame and the object images of the current frame for each case of the 3-D video scenarios. As we can expect, the difference images for the moving object of ‘Car’ can be extracted and only the hologram patterns for this difference images need to be calculated here.

#### 5.4 CGH generation with the estimated motion vectors and the N-LUT

Figure 14 shows a generation process of video holograms with the estimated motion vectors and the N-LUT. Figure 14(a) shows a part of ‘Car’ object image with 4 object points of (*A*, *B*, *C*, *D*) of the previous frame and its motion-compensated version composed of 4-object points of (*A*', *B*', *C*', *D*'). Figure 14(b) and 14(c) also shows the ‘Car’ object image of the current frame having 3 object points of (*E*, *F*, *G*) and the difference image between the motion-compensated object image of the previous frame of Fig. 14(a) and the ‘Car’ object image of the current frame of Fig. 14(b). As seen in Fig. 14(a) and 14(b), three object points of *A*', *B*' and *C*' of the motion-compensated object of the previous frame are exactly same with those of *E*, *F* and *G* of the object image of the current frame.

Now, the hologram patterns calculated for 4 object points of the previous frame and for 4 object points of its motion-compensated version are shown in Fig. 14(d) and 14(e), respectively. Here in the hologram pattern for the motion-compensated object points of Fig. 14(e), some blank region may occur because the hologram pattern is shifted according to the estimated motion vectors, thus the hologram pattern for this blank region should be generated using the N-LUT method. The finally generated hologram pattern for the motion-compensated object points of the previous frame compensated with the hologram pattern calculated for the blank region is shown in Fig. 14(f).

From the hologram pattern of Fig. 14(f), shifted version of the object points of (*A*', *B*', *C*', *D*') of the previous frame may be reconstructed. Thus, by removing the hologram pattern of the object point of *H* from the hologram pattern of Fig. 14(f), the hologram pattern of the current frame can be finally generated, which is shown in Fig. 14(g).

Therefore, the CGH patterns for the object points of the current frame can be represented by Eq. (11).

where *I _{n}* is the CGH pattern for the

*n*

^{th}frame,

*SEG*is the total number of segmented objects.

*I*,

_{S}*I*and

_{B}*I*are the CGH patterns for the segmented object, the blank region and the difference image, respectively.

_{D}*d*and

_{x}*d*also represents the motion vector in the

_{y}*x*and

*y*direction, respectively.

In this paper, the CGH patterns having a resolution of 1,600 × 1,600 pixels are generated using the intensity and depth data of the test 3-D videos of Fig. 8. Here, each pixel size of the hologram pattern is given by 10*μm* × 10*μm*. Moreover, the viewing-distance and the discretization step in the horizontal and vertical directions are set to be 600*mm* and 30*μm*, respectively. Therefore, the amount of the pixel shifts is given by 3 pixels.

Accordingly, to fully display the fringe patterns, the PFP must be shifted by 1,500 pixels (500 × 3 pixels = 1,500 pixels) horizontally and vertically. Thus, the total resolution of the PFP becomes 3,100(1,600 + 1,500) × 3,100(1,600 + 1,500) pixels.

Figure 15 shows the reconstructed object images from the CGH patterns generated with the proposed method. As seen in Fig. 15, in all scenario cases 3-D objects have been successfully reconstructed in the proposed method.

#### 5.5 Performance analysis of the proposed method

Figure 16(a)-16(c) and 16(d)-16(f) show the computed comparison results of the number of calculated object points and the calculation time of the conventional N-LUT, TR-N-LUT and proposed methods, respectively for each test video of ‘Case I’, ‘Case II’ and ‘Case III’.

The results of Fig. 16(a)-16(c) confirm that the number of calculated object points could be significantly reduced in the proposed method compared to those of the conventional N-LUT and TR-N-LUT methods, which results in a great reduction of its corresponding computation time as shown in Fig. 16(d)-16(f).

Here, for the ‘Case I’, the ‘Car’ object was assumed to move straight from the left to the right, so some good motion compensation of the moving object between the video frames might expect due to small variation of its depth and perspective, which would cause a significant reduction of the calculated object points of the proposed method all over the frames compared to the conventional N-LUT and TR-N-LUT methods as shown in Fig. 16(a). Of course, a slight increase of the number of calculated object points happened to be occurred in several frames of 2^{nd,} 7th, 12th, 18th, 26th, 33rd, 40th, 43rd and 47th which might be resulted from a minor variation of the ‘Car’ object’ perspective on those frames.

On the other hand, for the two test videos of ‘Case II’ and ‘Case III’, a degree of reduction of the calculated object points in the proposed method gets smaller relatively compared to that of ‘Case I’ because the ‘Car’ object was assume to move along the curved line in both of the ‘Case II’ and ‘Case III’, which means it may experience some changes in depth and perspective between the consecutive frames, and as a result the difference image between them would be somewhat increased. However, over the range of the 20th to 30th frame the object points to be calculated happened to be decreased. These results may stem from the fact the motion changes of the ‘Car’ object have been accurately estimated and compensated on those frames.

Furthermore, the number of calculated object points for the ‘Case III’ has been reduced less than that for the ‘Case II’ because the object of the ‘Case III’ was assumed to move along the longer curving radius than that of the ‘Case II’, which means lager changes in depth and perspective of the object image would be expected in the ‘Case III’ compared to those of the ‘Case II’.

Table 1 summarizes the comparison results on the numbers of calculated object points and the calculation times for one object point for each case of the conventional N-LUT and TR-N-LUT and proposed methods. Here in the experiment, a PC system employing an Intel Core^{TM} i7-3770 operating at 3.4 GHz, a main memory of 8 GB and an operating system of Microsoft Windows 7 as well as the Matlab 2009 are used. As you can see in Table 1, for the ‘Case I’, the numbers of calculated object points and the calculation times for one object point are estimated to be 73,603, 14,608, 6,035, and 3.085*ms*, 0.603*ms*, 0.268*ms*, respectively for each case of the conventional N-LUT, TR-N-LUT and proposed methods. These results mean that in the proposed method, the number of calculated object points and the calculation time for one object point have been reduced by 91.80%, 58.69%, and 91.30%, 55.51%, respectively compared to those of the conventional N-LUT and TR-N-LUT methods.

In the same manner, the number of calculated object points and the calculation time for one object point in the proposed method have been also reduced by 85.54%, 27.52% and 85.12%, 24.87%, respectively for the ‘Case II’, and by 83.46%, 19.07% and 83.10%, 16.98%, respectively for the ‘Case III’ compared to those of the conventional N-LUT and TR-N-LUT methods.

In short, Table 1 reveals that in the proposed method, the average number of calculated object points and the average calculation time for one object point for three video scenarios have been reduced to 9,553 and 0.412*ms*, respectively from their corresponding large values of 73,203, 14,696 and 3.061*ms*, 0.609*ms* of the conventional N-LUT and TR-N-LUT methods, which means 86.95%, 34.99% reduction of the average number of calculated object points and 86.53%, 32.30% reduction of the average calculation time have been obtained compared to the conventional N-LUT and TR-N-LUT methods. The outstanding performance of the proposed method might be stemmed from the fact that massive redundant data of the moving 3-D objects between the video frames have been effectively removed by using the newly employed motion estimation and compensation technique in the proposed method.

Now, here the calculation time of the proposed method is comparatively analyzed with those of the conventional N-LUT and TR-N-LUT methods. In the conventional N-LUT method, only one multiplication and one addition operations of the PFPs are required for calculation of each hologram sample for a given object point. That is, the total calculation time in the conventional N-LUT method can be given by Eq. (12).

where *t _{multi_amp}* and

*P*represent the multiplication time of the amplitudes of the object points and the total number of object points, respectively [12,13].

_{total}However, in the conventional TR-N-LUT method, the preprocessing time to extract the temporally redundant data between the video frames as well as the main processing time for calculation of the hologram patterns for both of the disappeared and newly added object points is required. Therefore, the total calculation time in the TR-N-LUT method can be given by Eq. (13).

where *t _{TR_EXT}*,

*M*and

_{disp}*M*mean the preprocessing time for extraction of the temporal redundancy between the video frames, the number of disappeared object points of the previous frame and the number of newly added object points of the current frame, respectively [13,19].

_{add}Furthermore, in the proposed method, the preprocessing time for object segmentation, motion estimation and compensation of the segmented object together the main processing time for calculation of the hologram patterns for both of the disappeared object points of the motion-compensated object image of the previous frame and the newly added object points of the current frame is needed. Therefore, the total calculation time in the proposed MC-N-LUT method can be given by Eq. (14).

Where *t _{SEG}*,

*t*,

_{ME}*t*represent the time for object segmentation and the time for motion estimation and the time for motion compensation, respectively.

_{MC}*N*and

_{disp}*N*also mean the number of disappeared object points in the motion-compensated object of the previous frame and the number of newly added object points of the current frame, respectively.

_{add}Figure 17 shows the results on the total calculation time for each of the ‘Case I’, ‘Case II’ and ‘Case III’ in the proposed method, which may consist of a very small portion of the preprocessing time and a very large portion of the main processing time. Here, the preprocessing time is composed of the time for image segmentation and the time for motion estimation and compensation while the main processing time consists of the time to shift the hologram patterns, the time to generate the hologram for the blank region and the time to generate the hologram for the motion-compensated object image.

Figure 17 shows the results of the total calculation time for each of the ‘Case I’, ‘Case II’ and ‘Case III’ in the proposed method, in which the total calculation time consists of the preprocessing and main processing times. As you can see in Fig. 17, a portion of the preprocessing times in the total calculation times are calculated to be very small values of less than 5%, compared to those of the main processing for all test videos of ‘Case I’, ‘Case II’ and ‘Case III’.

Table 2 shows the computed results on the preprocessing, main processing and total calculation times for each of the ‘Case I’, ‘Case II’ and ‘Case III’ in the proposed method. That is, the preprocessing, main processing and total calculation times have been found to be 0.965*sec*, 1.009*sec*, 0.982*sec* and 19.751*sec*, 33.218*sec*, 37.391*sec*, and 19.751*sec*, 33.218*sec*, 37.391*sec*, respectively for each test video of ‘Case I’, ‘Case II’ and ‘Case III’, which means the portions of the preprocessing times in the total calculation time are found to be very small values of 4.89%, 3.04% and 2.63%, respectively for each test video of ‘Case I’, ‘Case II’ and ‘Case III’.

As seen in Eq. (14) and Table 2, there might be a tradeoff between the preprocessing time and the reduction rate of the number of calculated object points in the proposed method. That is, if we employ a performance-enhanced motion-estimation and compensation algorithm, the corresponding object points to be calculated can be effectively reduced, whereas the preprocessing time for motion estimation and compensation gets increased due to its accurate processing, which means a careful selection of the motion estimation and compensation algorithm would be required because the total calculation time must include the preprocessing time.

Good experimental results mentioned above finally confirm that in the proposed method, the number of calculated object points and the resultant calculation time required for generation of 3-D hologram patterns could be significantly reduced compared to those of the conventional N-LUT and TR-N-LUT methods.

Furthermore, we can expect real-time generation of the video holograms of 3-D moving objects by practical implementation of this algorithmically well-tailored MC-N-LUT method on a graphic processing unit (GPU) board, because recent results of a GPU-based implemented N-LUT system show 300-fold enhancement of the computational speed compared to that of the conventional central processing unit (CPU)-based approach [24], which means the calculation time for one video frame could be reduced down to the order of *msec*.

## 6. Conclusions

In this paper, we proposed a novel approach, so-called MC-N-LUT, for fast generation of the video holograms of 3-D moving objects by newly applying a motion compensation technique to the N-LUT by using its unique property of shift invariance. That is, with a process of motion estimation and compensation, 3-D object data to be calculated for its video holograms have been massively reduced, which has resulted in a significant increase of the computational speed of the proposed method. Experimental results reveal that the average number of calculated object points and the average calculation time for one object point of the proposed method have been reduced down to 86.95%, 86.53% and 34.99%, 32.30%, respectively compared to those of the conventional N-LUT and TR-N-LUT methods.

## Acknowledgement

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No. 2012-0009224). The present research has been also partially conducted by the Research Grant of Kwangwoon University in 2013.

## References and links

**1. **C. J. Kuo and M. H. Tsai, Three-Dimensional Holographic Imaging, John Wiley & Sons, 2002.

**2. **T.-C. Poon, Digital Holography and Three-dimensional Display, Springer Verlag, 2007.

**3. **J. Weng, T. Shimobaba, N. Okada, H. Nakayama, M. Oikawa, N. Masuda, and T. Ito, “Generation of real-time large computer generated hologram using wavefront recording method,” Opt. Express **20**(4), 4018–4023 (2012), http://www.opticsinfobase.org/oe/abstract.cfm?uri=oe-20-4-4018. [CrossRef] [PubMed]

**4. **Y.-Z. Liu, J.-W. Dong, Y.-Y. Pu, H.-X. He, B.-C. Chen, H.-Z. Wang, H. Zheng, and Y. Yu, “Fraunhofer computer-generated hologram for diffused 3D scene in Fresnel region,” Opt. Lett. **36**(11), 2128–2130 (2011). [CrossRef] [PubMed]

**5. **M. Paturzo, P. Memmolo, A. Finizio, R. Näsänen, T. J. Naughton, and P. Ferraro, “Holographic display of synthetic 3D dynamic scene,” 3D Research **1**(2), 31–35 (2010). [CrossRef]

**6. **P. W. M. Tsang, J. P. Liu, K. W. K. Cheung, and T.-C. Poon, “Modern Methods for fast generation of digital holograms,” 3D Research **1**(2), 11–18 (2010). [CrossRef]

**7. **Z. Ali, H.-E. Kim, D. Han, J.-H. Park, and N. Kim, “Simplified novel look-up table method using compute unified device architecture,” 3D Research **2**(3), 1–5 (2011). [CrossRef]

**8. **T. Shimobaba, T. Ito, N. Masuda, Y. Ichihashi, and N. Takada, “Fast calculation of computer-generated-hologram on AMD HD5000 series GPU and OpenCL,” Opt. Express **18**(10), 9955–9960 (2010), http://www.opticsinfobase.org/oe/abstract.cfm?uri=oe-18-10-9955. [CrossRef] [PubMed]

**9. **Y. Ichihashi, H. Nakayama, T. Ito, N. Masuda, T. Shimobaba, A. Shiraki, and T. Sugie, “HORN-6 special-purpose clustered computing system for electroholography,” Opt. Express **17**(16), 13895–13903 (2009), http://www.opticsinfobase.org/oe/abstract.cfm?uri=oe-17-16-13895. [CrossRef] [PubMed]

**10. **M. Lucente, “Interactive computation of holograms using a look-up table,” J. Electron. Imaging **2**(1), 28–34 (1993). [CrossRef]

**11. **S.-C. Kim and E.-S. Kim, “Computational approaches for fast generation of digital 3-D video holograms,” Chin. Opt. Lett. **7**(12), 1083–1091 (2009). [CrossRef]

**12. **S.-C. Kim and E.-S. Kim, “Effective generation of digital holograms of 3-D objects using a novel look-up table method,” Appl. Opt. **47**(19), D55–D62 (2008). [CrossRef] [PubMed]

**13. **S. C. Kim, J. M. Kim, and E.-S. Kim, “Effective memory reduction of the novel look-up table with one-dimensional sub-principle fringe patterns in computer-generated holograms,” Opt. Express **20**(11), 12021–12034 (2012), http://www.opticsinfobase.org/oe/abstract.cfm?uri=oe-20-11-12021. [CrossRef] [PubMed]

**14. **D.-W. Kwon, S.-C. Kim, and E.-S. Kim, “Memory size reduction of the novel look-up-table method using symmetry of Fresnel zone plate,” Proc. SPIE **7957**, 79571B, 79571B-7 (2011). [CrossRef]

**15. **Z. Yang, Q. Fan, Y. Zhang, J. Liu, and J. Zhou, “A new method for producing computer generated holograms,” J. Opt. **14**(9), 095702 (2012). [CrossRef]

**16. **S.-C. Kim and E.-S. Kim, “Fast computation of hologram patterns of a 3D object using run-length encoding and novel look-up table methods,” Appl. Opt. **48**(6), 1030–1041 (2009). [CrossRef] [PubMed]

**17. **S.-C. Kim, W.-Y. Choe, and E.-S. Kim, “Accelerated computation of hologram patterns by use of interline redundancy of 3-D object images,” Opt. Eng. **50**(9), 091305 (2011). [CrossRef]

**18. **S.-C. Kim, K.-D. Na, and E.-S. Kim, “Accelerated computation of computer-generated holograms of a 3-D object with N×N-point principle fringe patterns in the novel look-up table method,” Opt. Lasers Eng. **51**(3), 185–196 (2013). [CrossRef]

**19. **S.-C. Kim, J.-H. Yoon, and E.-S. Kim, “Fast generation of three-dimensional video holograms by combined use of data compression and lookup table techniques,” Appl. Opt. **47**, 5986–5995 (2008). [CrossRef] [PubMed]

**20. **D.-W. Kwon, S.-C. Kim, and E.-S. Kim, “Hardware implementation of N-LUT method using field programmable gate array technology,” Proc. SPIE **7957**, 79571C, 79571C-8 (2011). [CrossRef]

**21. **R. C. Gonzalez and R. E. Woods, Digital Image Processing, Prentice Hall, 2007.

**22. **O. Marques, Practical Image and Video Processing Using MATLAB, Wiley-IEEE Press, 2011.

**23. **A. Barjatya, “Block matching algorithms for motion estimation,” in Technical Report, Utah State University (2004).

**24. **M.-W. Kwon, S.-H. Kim, S.-C. Kim, and E.-S Kim, “GPU-based implementation of one-dimensional N-LUT for fast computation of Fresnel hologram patterns of 3-D objects,” (submitted).