{'fraction_non_alphanumeric': 0.029063097514340344, 'fraction_numerical': 0.01135755258126195, 'mean_word_length': 4.605787781350482, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Application of Preconditioned Alternating Direction Method of Multipliers in Depth from Focal Stack

Post capture refocusing effect in smartphone cameras is achievable by using focal stacks. However, the accuracy of this effect is totally dependent on the combination of the depth layers in the stack. The accuracy of the extended depth of field effect in this application can be improved significantly by computing an accurate depth map which has been an open issue for decades. To tackle this issue, in this paper, a framework is proposed based on Preconditioned Alternating Direction Method of Multipliers (PADMM) for depth from the focal stack and synthetic defocus application. In addition to its ability to provide high structural accuracy and occlusion handling, the optimization function of the proposed method can, in fact, converge faster and better than state of the art methods. The evaluation has been done on 21 sets of focal stacks and the optimization function has been compared against 5 other methods. Preliminary results indicate that the proposed method has a better performance in terms of structural accuracy and optimization in comparison to the current state of the art methods.


Introduction
The compact design of mobile cameras does not allow users access to lens properties such as the aperture. By having the control over the aperture in a camera, one can control the camera's depth of field (and the light flux entering the camera). This means the user can decide how much of an image remains in focus around an object. a. Depth of field (DoF) and circle of confusion for a lens representing light collection optics in an imaging system b. The relation between Circle of Confusion and the object distance/focus position c. Small depth of field with F-number 0.4 d. Large depth of field with F-number 32 Fig.1 (a) shows schematically the relation between the depth of focus (in image space) and depth of field (in object space). As illustrated in Fig.1 (c), small depth of field will make the main object in focus, while the rest of the image will be less sharp. A large depth of field will keep the entire image sharp throughout its depth; this concept is shown in Fig.1 (d). When light rays from an out of focus point source enter a lens, the point on the object is focused into a circle on the image plane. This circle is called the Circle of Confusion (CoC) which is shown as C in Fig.1 (a). The size of the CoC in used to measure the sharpness of an image. The bigger CoC shows that the point on the object is more out of focus. The diameter of CoC depends on focal length , object distance (near point) and the distance between the object point and the lens and aperture diameter . Therefore, the diameter of the CoC can be calculated using Eq. 1: Fig.1 (b) illustrates the relationship between the CoC and the object distance for an aperture f/2.8 mm for a specific camera model. The X-axis in Fig.1 (b) represents the distance of the object points in focus and the Y-axis shows how far the object would be in focus. For instance, if an object is located at the distance 1000 mm the value of CoC is 0, this means the object is fully in focus. If an object is located at the distance beyond 1200 mm then the 1.5 meter setting of the camera should be used. If an object is located at the distance beyond 2000 mm then the 3 meter setting of the camera should be used and for the objects which are located at the distance beyond 6000 mm, the infinite setting of the camera should be used.

Figure 1. Demonstration of the relation between F-number and depth of field, Circle of Confusion and Object Distance
The adjustable aperture feature is available in DSLR cameras but smartphone cameras have a fixed aperture as they are designed for ease of portability, robustness and low cost.
To overcome this shortcoming, post-capture image refocusing can be employed by using Depth from Focus (DfD) [1,2] and focal stack. The focal stack is a collection of images with different focus points which correspond to different depth layers. The focal setting presenting the maximum sharpness of pixel corresponds to the depth of the pixel or its distance to the camera. The combination of these images can generate the extended depth of field similar to the range being generated by optical properties of the camera. The accuracy of this effect is highly dependent on the accuracy of the corresponding depth map.
In handheld devices such as smartphones, a focal stack is generated by automatic focal plane sweeps to find the camera's best auto-focus setting while taking photos. However, in dynamic scenes, the slight translation of the camera by users and their handshake can introduce motion parallax. The experiments indicate that it takes about 1 2 to 1 3 seconds for a camera to capture the full extent of its focus setting. This means that the local parallax met within this short time frame can be dismissed but yet an alignment procedure is required to compensate the parallax between the first and last frame of the focal stack. Generally, an aligned focal stack should be similar to a stack captured by a telecentric camera.
In this paper, we present a framework to compute and optimize the dense depth map from the highresolution focal stack which can be used to produce an accurate synthetic defocus. The framework initiates by taking a focal stack from a moving camera as the input and generating a stabilized image sequence. At the second step, the initial depth map is estimated from the stabilized focal stack. At the end, Preconditioned Alternating Direction Method of Multipliers (PADMM) with a new cost function is applied to refine depth discontinuities and generate a noise-free depth map.
The proposed method has several advantages in comparison to the state of the art methods, such as: 1-Fast and better convergence of the optimization function 2-Occlusion handling in the generated depth map 3-High structural accuracy of the depth map 4-High performance in texture-less scenes 5-Accurate depth information along objects' boundaries and surface The rest of this paper is organized as follows: Section II outlines the previous researches. The proposed method is explained in detail in Section III. The evaluation results are presented in Section IV and Section V includes conclusion and feature work.

Previous Work
A considerable amount of researches focused on depth from focus control for decades [3][4][5][6][7][8]. Most of these methods concentrated on depth from focus/defocus or depth recovery from the focal stack on light field cameras [4,5,9,10]. Using light field cameras has an advantage of capturing simultaneous multiple views with variable focal points which provide more accurate information about the depth of the scene; however, the images are captured in low resolution and in small aperture the value of Signal-to-noise ratio (SNR) is significantly low [4]. The size of these cameras along with the mentioned challenges makes them inapplicable for handheld devices such as smartphones. Another disadvantage of light field cameras is the disability in handling occlusion due to the lack of lateral variation being captured in different viewpoints [9].
A framework to recover depth from the focal stack is presented in [3] to handle images captured on smartphones. The focal stack is being aligned to make it as similar as a focal stack captured by a telecentric camera. Multilabel Markov Random Field (MRF) optimization is used to generate all in focus image from the aligned stack. This method works quite well for the Lambertian scenes however the optimization problem during the calibration process is highly non-convex and that makes this process considerably slow. The other problem with this method is the processing time of the nonlinear least squares minimization to jointly optimize the initially estimated aperture size, focal depths, focal length and the depth map. The whole processing time of this method is ~20 minutes for 25 frames with 640×360 pixels resolution which make this algorithm almost inapplicable as a smartphone application. The depth maps generated by this method suffer from inaccurate depth values on objects surface, especially on reflective surfaces. In some cases, the depth information along the boundaries of the foreground object is mixed with the values on the background and that might result in an inaccurate synthetic defocus.
The complexity of the non-convex optimization is reformulated in [6] where depth from focus is presented as a variational problem by introducing a nonconvex data fidelity term and a convex nonsmooth regularization. The nonconvex minimization problem in [6] is aimed to be solved by a linearized alternating directions method of multipliers. This method has a superior performance in comparison to state of the art methods but the convergence of the optimization function happens very slowly and in a high number of iterations. Also, the depth map generated by this method suffers from inaccurate depth values on objects surface and missing edges and corners.
Some other approaches in this field have been proposed to facilitate the depth from focus applications by introducing coded focal stack photography [11] or coded aperture photography [12,13]. These methods require physical changes in the structure of the camera and yet the generated depth maps suffer from lack of structural quality.
Persch et al. [14] proposed a variational approach for the problem of depth from defocus based on modeling of the image formation by featuring the thin lens model and preserving the crucial physical properties such as maximum-minimum principle for the intensity values. Later, the variational model is minimized using the multiplicative Euler-Lagrange. The proposed solution in [14] appears to generate false depth levels in relatively close scenes and in general, the depth profiles are likely to be affected by the color information as the robustification method employed in [14] uses the full-color information of the focal stack.
Pérez et al. [15] proposed a focal stack frequency decomposition algorithm from light field images based on the trigonometric interpolation principle as the discrete focal stack transform. The proposed method in [15] utilizes fast discrete Fourier transform to generate refocus planes in a reasonably fast computational time. The reverse of this transformation in studied in [16] where a focal stack is used to obtain a 4D light field image set using discrete focal stack transform.
Unlike [15], Mousnier et al. [17] presented an approach to reconstruct 4D light field image sets from a stack of images taken by a fixed camera at different focal points. The algorithm initiates by calculating the focus map by utilizing region expansion with graph cut. Later, the depth map is estimated based on the calibration details of the camera and it is used to reconstruct the Epipolar images. The reconstructed Epipolar images are used for refocusing purposes.
Bailey et al. [18] proposed a method to calculate depth from the focal stack by estimating the level of the blurriness for each pixel. The method initiates by applying a focus measure to each pixel in the stack. A normalized convolution is proposed to extrapolate the invalid blur estimates. Afterwards, the per-pixel depth is calculated based on the blur estimations.
Jeong et al. [19] presented a post-processing approach to refine the estimated depth map from two images captured with different focal points. The initial depth map is calculated using a depth from defocus algorithm. To improve the quality of the depth map, mean-shift clustering is applied to the first input image to obtain the segmented image. A single depth value is assigned to each segment of the image by averaging all depth values in the corresponding segment.
Surh et al. [20] presented a novel focus measure to determine how in focus a point is on an image. The shape of the focus measure introduced in [20] contains a disk which focuses on the pixel of interest and the ring which surrounds the disk. To estimate the depth map, the initial calculated cost volume is aggregated by employing tree-based cost aggregation method. Afterwards, the depth discontinuity and unreliable depth labels are filtered based on the median of absolute deviation map and using tree-based cost aggregation method.
Focal stacks are also used to handle some of the optical features such as post-capture perspective shift and aperture reshaping. Alonso [21] developed a method in the Fourier domain for post-capture aperture reshaping in focal stacks. This allows users to change the blur shape for the out of focus points. This study came to the conclusion that by utilizing domain transformation methods such as Fourier it is possible to manipulate the optical setting of the camera. In another study, Alonso et al. [22] proposed a method for post-capture perspective shift reconstruction of a 3D scene from a focal stack. Unlike the computational approaches which estimate the depth map, the method in [22] takes advantage of depth-variant point-spread function to introduce the lateral (( , ) plane) and axial ( plane) shifts.

Focal Stack Alignment
To generate the parallax-free input focal stack we refer to Epipolar homography alignment. To do that, we merge all the homographies into Epipolar geometry. Considering there are plane patches in an image and their corresponding maps in the second image are characterized as: where is a scale factor, is a 3 × 3 rotation matrix, is the image, is the second camera's translation from first camera's point of view and ( , , ) is the normal vector of the plane surface. So we can write: Consequently it can be concluded that: where = ‖ ‖ is the distance of the plane from the origin and is represent the correlation between the basis homography and all the other homographies. The important feature of the Eq. 4 is that it reduces the number of independent parameters of a homography and makes them equal to the degree of freedom of a system with planar surface. Generally, a homography includes 5 dof indicating the camera motion and 3 dof representing the plane surface normal. Assuming more than one plane between two images, then homographies will have parameters. Eq. 4 decreases the number of the parameters to + which is equivalent of the total degree of freedom in a system with planar surface.
Using Eq. 4 the motion estimation can break down into two parts: First, considering that and are fixed, it is possible to characterize and by utilizing least square algorithm for each plane patches. To estimate we define two vectors as: can be estimated using least squares method as: where − are the parameters of the homography matrix. ( , , ) and ( ′ , ′ , ′ ) are the coordinates of the point in two camera frames.
The second part is somehow the inverse process of the first part. Assuming is fixed, and can be updated by utilizing another least square process. To estimate and we define three vectors as: is a point on the plane surface and = ( + + ). So it can be concluded that = ′ and = ′ . Then can be estimated using least square process as: . By estimating from Eq. 6 and and using Eq. 8, one can construct the global homography from Eq. 4. The alignment process will be over when the average reprojection error is smaller than a threshold.

Depth Estimation and Regularization
The depth estimation process starts with calculating the value of the focus factor for each pixel at every frame of the aligned focal stack. The value of the focus factor for a pixel ( , ) over all the frames in the stack is referred as focus function. The Modified Laplacian is used in this case to compute the focus function of : where the convolution masks on and domains are = [− , , − ] and = , respectively. The mean filter mask is used as by the radius . The initial depth map is computed by modeling the focus function using the 3-point Gaussian distribution [23]. The algorithm relies on 3 focus factors − , and + . This will result the following focus function: where and are the mean standard deviation of the Gaussian distribution and is the displacement of the object plane. The estimated depth values correspond to the location of . As long as there is a good correlation between the Gaussian model and the focus function, the depth values get more authentic. But this situation is not constant and it can be interrupted by a variety of reasons such as noise. The presence of noise in the image domain can cause the focus function not to fit on the Gaussian model. That means the initial depth map is suffering from uncertain depth values. This condition becomes severe in case of small motions of the camera. Fig.2 (b) shows the initial estimated depth map. This problem is reformulated to a convex minimization problem to be solved by PADMM [24,25]. To define the formulation of the convex problem we refer to regularization method proposed by Rudin, Osher and Fatemi (ROF) [26] which introduces a minimization problem to generate the restored image for a noisy image as: where is the regularization parameter and: and defines the vectorial gradient as: prevents the function to generate ringing artifacts along the edges but it cannot handle the discontinuities. It generally presents a loss of contrast which happens due to the use of fidelity. To overcome this issue, the ROF function is changed to a unique global minimizer by employing the vectorial norm fidelity term.

( ) = × + ( )
Using the norm allows to solve non-convex optimization problems using convex optimization methods. The important advantage of using the convex optimization is that the global optimum is achievable with a high precision in a shorter computational time. It is also independent from the initialization. Since the problem can be solved using convex optimization, we attempt to solve the ROF minimization by modifying PADMM constrained convex minimization method. Consider a generic constraint minimization problem as: where is the iteration number. By finding the linear approximation of � + , � and � + , + � around and using the Taylor expansion, we can reduce the nonlinearity computation overhead of Eq. 18 and Eq. 19. So: To convert ADMM to a preconditioned solver, we modify Eq. 18 and Eq. 19 by adding an additional proximity term as: where is the positive definite matrix 3 . So the modified Eq. 18 and Eq. 19 are: To obtain the proximity operator, we define: and then we can obtain: based on Eq. 29 and Eq. 30, the proximity operator can be defined as:

Experiments and Evaluation
For evaluation purposes, 21 sets of focal stack images by [28] are used. The focal stacks are captured using a Lytro camera which is equipped with an array of 360 × 360 micro lenses mounted on an 11 MP sensor. The images are down-sampled by the factor of 3 before applying the PADMM. Joint Bilateral Upsampling [29] is employed to up-sample the low-resolution depth map to the original size. Afterwards, the up-sampled depth map is refined using the post-processing algorithm presented in [30]. For the first part of the evaluation, the depth maps generated by the proposed method are compared against the method presented by Moeller, et al. [6], Helicon Focus [31] and Zerene Stacker [32]. Numerical comparison of these results is a challenging task as there is no ground truth and publicly available dataset, so the depth maps are compared visually. Fig. 3 shows the generated depth maps by the proposed method, Moeller, et al. [6], Helicon Focus [31] and Zerene Stacker [32]. Fig.3 (a) shows the case that the depth maps computed by Moeller, et al. [6], Helicon Focus [31] and Zerene Stacker [32] are missing a corner of an object and some parts of the background depth information are mixed with foreground depth values. Fig.3 (b) illustrates the scenario where the depth maps by Moeller, et al. [6], Helicon Focus [31] and Zerene Stacker [32] are suffering from inaccurate depth values on an object's surface. Also similar to the previous example, the background depth information is mixed with foreground depth values. Fig.3 (c) represents the case where the depth maps by Moeller, et al. [6], Helicon Focus [31] and Zerene Stacker [32] are not following the edges on the object's boundary. This might cause a problem in segmentation and synthetic defocus application. To find more visual results and the higher resolution version of the images presented in Fig. 3 please refer to Appendix 1 in the supplemental material.
a. All in focus image Proposed method Moeller, et al. [6] Helicon Focus [31] Zerene Stacker [32] b. All in focus image Proposed method Moeller, et al. [6] Helicon Focus [31] Zerene Stacker [32] c. All in focus image Proposed method Moeller, et al. [6] Helicon Focus [31] Zerene Stacker [32]  To determine the performance of the generated depth maps for synthetic defocus applications, we applied hexagon shaped uniform distributed blur, based on the depth layers. Fig. 4 illustrates the synthetic defocus generated based on the depth maps presented in Fig.3 (b). Frontal object and the background are chosen as two focal points for each sample. As it is shown in Fig. 4, faulty depth values can cause artifacts in applications such as synthetic defocus and post-capture refocusing. The synthetic defocus of Fig.3 (a) and Fig.3 (c)   shows the 3D normals of the reconstructed surface calculated using the method presented in [33]. By looking at 3D normals one can determine the smoothness of the depth values estimated by the proposed framework.  At the second part of the experiment, the performance of the proposed PADMM is compared against 5 other optimization methods including Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) [34], Classical Forward-Backward [35], Forward-Backward Splitting (FBS) [36], Accelerated FBS+Restart [37][38][39] and Adaptive Stepsize Selection FBS [39,40]. The mean and standard deviation of the residual norm for each optimization method are illustrated in Fig. 6. The maximum number of iterations and the regularization parameter are set to 300 and 0.7 for all the methods respectively. As shown in Fig. 6, the presented PADMM optimization method, results in lower convergence error in comparison to other methods.

Figure 6. Mean and Standard Deviation of the residual norm for PADMM and other 5 optimization methods
The numerical information related to the convergence of the PADMM and Moeller, et al. [6] is presented as the decay of energy in a logarithmic form in Fig.7 (a) and Fig.7 (b) respectively. As it is shown in Fig.7   The third part of the comparison is done against the method proposed by Suwajanakorn, et al. [3]. The reason that we performed a separate comparison against this method is not having access to the code of the algorithm. The authors of [3] kindly provided the focal stacks and the depth results published in their paper. Fig. 8 illustrates the comparison of the depth maps computed by the proposed method and Suwajanakorn, et al. [3]. Fig.8 (a) represents the case where the depth map computed by Suwajanakorn, et al. [3] is suffering from inaccurate depth values on a reflective surface and some other objects' surface while the depth map by the proposed method covered these issues. The depth map by Suwajanakorn, et al. [3] in Fig.8 (b) shows a similar issue to the previous example, uncertain depth values along an object's edges and surface. Fig.8 (c) shows the similar issues of the reflective surfaces and inaccurate edges which have been solved by the proposed method. However, the blue highlighted part in Fig.8 (c) illustrates the case where the proposed method computed a patch of

Decay of Energy
uncertain depth values on the background level. It is also worth pointing out the advantage of the method by Suwajanakorn, et al. [3] in computing longer depth range than the proposed method.
a. All in focus image Proposed method Suwajanakorn, et al. [3] b. All in focus image Proposed method Suwajanakorn, et al. [3] c. All in focus image Proposed method Suwajanakorn, et al. [3]

Conclusion
In this paper, a modified version of PADMM optimization method is proposed to perform on depth from the focal stack and synthetic defocus application. The proposed method is applied on a sequence of images produces by a camera with hypothetical focus and aperture values to generate the depth map. The proposed technique satisfies the constraint of the state of the art method such as uncertain depth values on objects' surface, mixed depth values on different layers of background and foreground, missed depth information on an object's boundaries which cause faulty edges and corners in the depth map. The method is evaluated in 2 parts. First, the generated depth maps with the correspondent defocused images are compared against a recent studied method. 21 sets of focal stack images are used in this comparison and all the parameters are set equally in both methods. The second part of the evaluation is done to determine the performance of the proposed optimization technique in comparison to 5 other algorithms. The results of both parts of the evaluation show that the proposed framework and modified PADMM doesn't have the best yet better performance than the recent depth from the focal stack and optimization methods. The high structural accuracy of the depth map generated by the proposed method gives the smartphone users the ability to refocus post-capture images accurately without the need to change the aperture size. The method has been implemented in Matlab R2016a on a device equipped with Intel i7-5600U @ 2.60GHz CPU and 16 GB RAM. The computational time of the modified PADMM optimization is ~1.5 second and the whole process, from initializing the focal stack to final refined depth map takes ~53 seconds on an image with 1080×1080 pixels resolution. In our future work, we plan to implement the proposed algorithm as a smartphone application. However, despite the performance and accuracy of the studied method, there is still the computational time of this technique which has to be considered as the trade-off.