Inpainting algorithm for Jacquared Image Bad on Pha-Field Model
Zhilin Feng1, Jianwei Yin2, Jianan Zhou3
1. College of Zhijiang, Zhejiang University of Technology, Hangzhou, 310024, China
2. State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou, 310027, China
3. Department of Information and Technology, Zhejiang Vocational College of Commerce,
春夜喜雨的作者Hangzhou, 310053, China
, zjuyjw@zju.edu, pearl@zju.edu
Abstract
Jacquard image inpainting is an interesting new rearch topic in pattern preprocessing for jacquard CAD. Pha field model has been well acknowledged as an important method for image inpainting. This paper discusd the problem of jacquard image inpainting by approaching the pha field paradigm from a numerical approximation perspective. The basic idea is to reprent the damaged p
attern of interest in implicit form, and fill-in the damaged parts with a system of geometric partial differential equations derived from pha-field model. The novelty of our approach lies primarily in exploiting explicitly the constraint enforced by the numerical solving of the quential evolving of pha-field model. Extensive experiments are carried out in order to validate and compare the algorithm both quantitatively and qualitatively. They show the advantages of our algorithm and its readily application to jacquard texture.
1. Introduction
CAD technique has been broadly ud in jacquard texture industry. One of the most important aspects of the jacquard CAD system is to simulate the appearance of jacquard texture during output[1]. Automatic inpainting and restoration are cloly related to jacquard CAD system[2]. Jacquard image inpainting is to restore a damaged image with missing information, so it is needed to determine which parts of the image the computer needs to retouch and in many cas the missing delineation of objects yields valuable information[3]. Jacquard image inpainting has become an indispensable process to quantitative analysis of images for jacquard CAD system. The process of inpainting is challenging due to poor image contrast and artifacts that result in missing or diffu pattern boundaries. Thus, this task involves incorporating as much prior information as possible into
a single framework. Traditionally, jacquard image inpainting techniques require some form of expert human supervision to provide accurate and consistent identification of pattern structures of interest[4].
A key difficulty associated with digital inpainting is to t up a measure of visual nsitivity towards defects which can be ud in computer code. Most inpainting mechanisms u a singular resolution approach on the extrapolation or interpolation of pixels. Oliveira et al. introduced a simple and faster mechanism to filling the damaged area[4]. This algorithm can inpainting an image in just a few conds, it can be ud for interactive construction of tight masks. Bertalmio et.al decompos the original image into two components, one of which is procesd by inpainting and the other by texture synthesis[5]. The output image is the sum of the two procesd components. This approach still remains limited to the removal of small image gaps, however, as the diffusion process continues to blur the filled region. Chan and Shen develop inpainting schems from the viewpoint of variational principles and image prior mode [6]. The method explains successfully some aspects of the human disocclusion process in vision psychology. Edoglu et al. [7] have prented a technique for filling image regions bad on a texture-gmentation step and a tensor-voting algorithm for the smooth linking of structures across holes.科索沃事件
In the last decades, many algorithms that deal with image processing using pha-field models have been prented in the literatures [8-11]. The range of applications of pha field models in image processing includes noi removal, image gmentation and shape optimization problems. What is common to all the models is that they are all solved by minimization of an
___________________________________ 978-1-4244-2197-8/08/$25.00 ©2008 IEEE
energy functional which is designed to appropriately describe the behavior of the associated model. Moreover, pha-field approach can be en as the deterministic reflection of the Bayesian framework whereas the energy corresponds to the negative log-likelihood of the probability of a certain feature configuration.
Feng et al. [8] introduced the Allen-Cahn equation in pha transition theory to remove noi from jacquard images. For nonlocal Allen-Cahn equation can generate an area-prerving motion by mean curvature flow, it can perfectly prerve shapes of the fabric texture while in the process of denoising. Benes et al. [9] prented an algorithm of image gmentation bad on the level t solution of pha field equation. The approach can be understood as a regularization of the level t motion by means of curvature, where a special forcing term is impod to enforce the initial level t
cloly surrounding the curves of patterns with different shapes. The pha field method is also a robust and rigorous framework for topology optimization problems.
However, from a numerical point of view, it is not easy to compute a minimizer for the non-convex functional of the pha field. Barrett et al. [10] prented a fully practical finite element approximation of a pha field system with a degenerate mobility and a logarithmic free energy. Provatas et al. [11] developed a large-scale parallel adaptive mesh code for solving pha-field type equations in two and three dimensions. For the minimization of pha field model can be defined as an optimization process, we consider the model as an optimization problem, and apply the iteration theory to solve it.
匠心精神作文2. Inpainting model for jacquard image
Let 2 R :be a bounded open t and ()g L f :reprent the original image intensity. The function g has discontinuities that reprent the contours of objects in the image. L et be a image field, which stands for the state of the image system at the position and the time , and (,)u u x t R x :0t t K be the t of discontinuity points of u . Here, we assume that the image field has two stable states corresponding to and . In this ca, the pha-field energy of the image system is often given as follows:
1u 1u
2\1(,)(())(())2K E u K u x F u x dx H H H : ³ (1) where is a double well potential with wells at and (i.e., a non-negative function vanishing only at and 22
()(1)/4F u u 1 1 1 1 ). Here, the value can be interpreted as a pha field (or order parameter),
which is related to the structure of the pixel in such a
way that ()
u x ()1u x
corresponds to one of the two phas and ()1u x corresponds to the other. The t of discontinuity points of u parameterizes the interface between the two phas in the corresponding configuration and is denoted by a clod t K . The first term in reprents the interfacial energy, which penalizes high derivatives of the function u and therefore constrains the number of interfaces parating the two phas. The cond term reprents the double-well potential that tries to force the values of image pixels into one pha or the other. The small
parameter (,)E u K H H
links to the width of transition layer, which controls a ratio of the contribution from the interfacial energy and the double-well potential.
The pha-field functional simultaneously measures the quality of an evloving curve K and of an approximation function u of the image: the minimum of this functional is reached if the approximating function is clo to the original image, piecewi smooth and with few discontinuities. The problem is to find a partition of the image which minimizes this deviation. Obviously it is not possible to directly find the global minimum of the energy by examining the entire t of possible gmentations. The principle of our computational method is to generate local transformations of a given gmentation and keep the transformations when the resulting energy is reduced.
Heuristically, we expect solutions to Eq. (1) to be smooth and clo to the image g at places x K , and K constitutes edges of the image. To show existence of solutions to Eq. (1), a weak formulation was propod by De Giorgi et al . [12]by tting u K S (the jumps t of u ) and minimizing only over u SBV ,the space of functions of bounded variation. We recall some definitions and properties concerning functions with bounded variation.
Definition 1. Let . We say that u is a function with bounded variation in :, and we write , if the distributional derivative Du of is a vector-valued measure on : with finite total variation.
12(;)u L R :2(;)u BV R :u De inition 2. L et . We denote by the complement of the L ebesgue t of u , i.e., 1
(;)u L R :2
u S u x S if and only if for
some ()
lim |()|0n
B x u y z dy U U U
o ³
2
z R , where 2
(){:||}
B x y R y x U U
Def inition 3. L et . We say that u is a special function of bounded variation, and we write , if .
()u BV :()u SBV :0c
D u De Giorgi et al .[12] gave the weak formulation of the original problem (1) as follows:
(,)(,)u E u K E u S
(2) . They also proved that minimizers of the weak problem (2) are minimizers of the original problem (1). However, from a numerical point of view, it is not easy to compute a minimizer for Eq. (2), due to the term , and to the fact that this functional is not lower-micontinuous with respect to . It is natural to try to approximate Eq. (2) by simpler functionals defined on SBV spaces. Ambrosio and Tortorelli [16] showed that Eq. (2) can be approximated by a quence of elliptic functionals which are numerically more tractable. The approximation takes place in the n of the convergence.
1()u H S u S -*Let , let be the triangulations and let (0,1)(0,1): u ()T H :H denote the greatest length of the edges in the triangulations. Moreover let be the finite element space of piecewi affine functions on the mesh and let be a quence of
triangulations with ()V H :()T H :{}j
T H 0j H o .
Modica [13] proved that
Theorem1. L et (){():(){1,1}}BVC BV \\: :: ,and let be a continuous function such that {:, and :[0,W R o f )1} ()0}{1,z R W z 1(||1)()c z W z J d 2(||c z J d 1) for every , with z R 2J t .Then, the discrete functionals
2
\1(())(())2
(,)T T
K u x F u x dx E u T H H H : ° ®° f
¯³ (3) -*converge as 0H o to the functional 0()(E u c :
)
³)u dx for every L ipschitz t :
and every function , where 12
()loc u L R
1
0c ³
, and
(4)
1()())()u H S if u BVC u otherwi :°
) ®
f °¯
When the edges behind the inpainting domain are all determined, the inpainting domain is divided int
瀛湖中学
o smooth pieces. The smooth pieces are independent to each other, so we fill in the smooth pieces one by one.
3. Discretization algorithm f or inpainting
model
Let 0(,):[0,][0,]u i j M N R u o , with [0,][0,]
M N u R R u , be a discrete 2D gray level image. From the description of manual inpainting techniques, an iterative algorithm ems a natural choice. The digital inpainting procedure will construct a family of images (,,):[0,][0,]u i j n M N N R u u o such that 0(,,0)(u i j u i
,)j and lim (,,)(,)n u i j n u i j of R , where
is the output of the algorithm (inpainted image). Any general algorithm of that form can be written as
(,)R u i j 1(,)(,)(,),(,)n n n t u i j u i j tu i j i j ' : (5) where the superindex n denotes the inpainting time,
are the pixel coordinates, is the rate of improvement and stands for the update of the
image .
(,)i j t '(,)n t u i j (,)n u i j In order to arrive at the joint minimum of Eq. (3), a scheme for the mesh adaptation is first enforced to refine and reorganize a triangular mesh to characterize the esntial contour structure. Then, a conjugate gradient algorithm is applied to find the absolute minimum of the discrete version of the functional at each iteration.
(,)u T Step 1. Initialize iteration index:.
0j m Step 2. Set initial j H and j u .
Step 3. Generate an adapted triangulation j
T H by
the mesh adaptation algorithm, according to j u .Step 3.1 Compute 2L error 21(||)||j
j S u g H K H
()
||||())||
)
j j L e e S u F u H H H w :
¦
21122
21/2 1/2
2()j S S T u H H K K §· ¨¸©¹
¦,.
Step 3.2 If , then goto Step 4.
()j
j S u H K K Step 3.3 Adjust the triangular mesh by error strategy, and return to Step 3.1.
Step 4. Minimize ()j
j E u H
on the triangulation j
T H by the conjugate gradient minimizing algorithm.
Step 4.1. Initialize step index:, define a initial descent direction , define a subspace 0k m k p {}k k W p where a suitable admissible minimum of ()j
j E u H .
Step 4.2. Compute the gradient and the
Hessian approximation matrix , project ()k E u H j 2()k E u H
()k E u H and j 2()k E u H on .
k W Step 4.3. If ()0k E u H , get a minimizer and goto Step 9.
狗的画法
k u Step 4.4. Compute the incomplete Cholesky
factorization of t HDH j 2()k E u H
, where H is lower
triangular with unit diagonal entries, and D is positive diagonal.
Step 4.5. If j 2()k E u H
世界上最大的半岛is sufficiently positive definite, then compute the descent direction by
solving the linear system k d j 2()k k E u p H
()k E u H with the standard preconditioned conjugate gradient
method; If j 2()k E u H is only positive mi-definite or
almost positive mi-definite, then compute the descent direction by degenerate preconditioned conjugate gradient method.
k d Step 4.6. Compute the optimum step along by minimizing to the interval {}k t k d ()k E u k k u td for .
[0,1]t Step 4.7. Update the current index:.
1k k m Step 4.8. If 1||k k u u J , return to Setp 4.2. Otherwi, return to Step 4.1.
Step 5. Update the current index:1j j m .Step 6. Generate a new j H .
Step 7. If 1||j j H H !P , return to Step 3. Otherwi, goto Step 8. Step 8. Stop.
4. Experimental results
Now, we will prent the results of experiments for the propod model. The results have been obtained using software written in C programming language on the UNIX operating system running on a IPC SUN workstation. The tested image is reprented by 256 × 256 matrices of intensity value
s. Fig.1 shows the results of applying our algorithm on an example of inpainting damaged jacquard images. Numerical results with our propod algorithm are very encouraging. Fig. 1(a)-(c) are three damaged jacquard images which stained by lines and spots, and Fig. 1(d)-(f) are edges of Fig. 1(a)-(c) respectively. Fig. 2(a)-(c) illustrates the inpainting results of three jacquard images using our algorithm, and Fig. 2(d)-(f) are edges of Fig. 2(a)-(c) respectively.
The following experiments are designed for comparing efficiency of the propod algorithm with a numerical solving method for pha field model, i.e., Oliveira’s algorithm [4]. In Fig. 3(a)-(c), although the Oliveira’s model restores most of the high frequency texture information, the result is not satisfying. As shown in Fig. 2(a)-(c), both the lines and the spots are restored in an undetectable way by our method, where the method in Fig. 3(a)-(c) fails to keep the boundary of the different structures and cau rious visible
artifacts.
(a)(b)
(c)
(d)(e)(f)
Fig. 1(a)-(f ) Three damaged jacquard images, and
绘画日记their edges respectively
(a)(b)
(c)
(d)(e)(f)
Fig. 2(a)-(f) inpainting results using our algorithm,
and their edges respectively
(a)(b)
茶村(c)
(d)(e)(f)
Fig. 3(a)-(f
)
inpainting results using Oliveira’s algorithm, and their edges respectively
Table 1 shows comparisons of the iteration times(ITs) and the average iteration time(AIT) between the two algorithms. We can e that the two algorithms spend
Table 1. Computational time comparison between the Oliveira’s algorithm and the propod algorithm
Oliveira’s algorithm Propod algorithm ITs AIT ITs AIT
Fig.2 (a)
150.403 Fig.3 (a) 150.398 Fig.2 (b)200.547
Fig.3 (b)
200.514
Fig.2 (c) 300.652 Fig.3 (c) 300.602
the same iteration time to accomplish the inpainting process, but the propod algorithm consumes
much less time than Oliveira’s algorithm at each iteration.
5. Conclusions
This paper has prented a novel algorithm bad on pha-field model for retouching damaged patterns from jacquard texture images. The pha-field model is formulated as a variational theory of approximation in which the boundary function has a simple explicit form in terms of the approximation function. Our method improves the robustness and effectiveness by imposing some explicit smooth constrains of connection on the formation of discontinuous edges. Experiments show the propod algorithm provides a better visual effect, especially for jacquard image inpainting.
6. Acknowledgement
The work has been supported by the National High-Tech Rearch and Development Program of China("863")(No. 2007AA01Z124), the Zhejiang Provincial Natural Science Foundation of China (No. Y106045,Y1080343) and the National Natural Science Foundation, China (No. 60703042).
7. References
[1] Cho C.S., Chung B.M., and Park M.J., “Development of real-time vision-bad fabric inspection s
ystem”, IEEE Transactions on Industrial Electronics, Vol. 52, No. 4, pp. 1073-1079, 2005.
[2] Ngana H.Y.T., Panga G.K.H., Yungb S.P., Ngb M.K, “Wavelet bad methods on patterned fabric defect detection” , Pattern Recognition, Vol. 38, No. 4, pp. 559-576, 2005.
[3] Bertalmio M., Sapiro G., Calles V., “Image inpainting”, in: Proceeding of 2000 ACM SIGGRAPH, pp. 417-424, New Orleans, Louisianna, 2000.
[4] Oliveira M.M., Bowen B., Mckenna R., Chang Y.S., Fast digital image inpainting, in: Proceedings of the International Conference on Visualization, Imaging and Image Processing, Marbella, Spain, 2001.
[5] Bertalmio M.,Ve L.,Sapiro G., “Simultaneous structure and texture image inpainting”, IEEE Transactions on Image Processing, Vol. 12, No. 8, pp. 882-889, 2003.
[6] Chan T.F, Shen J., “Non-texture inpainting by curvature-driven diffusions”, Journal of Image Reprentation, Vol. 12, No. 4, pp. 436-449, 2003. [7] Edoglu S., Shen J., “Digital inpainting bad on the Mumford-Shah-Euler image model”, European Journal on Applied Mathematics, Vol. 13, No. 2, pp. 353- 370, 2002.
[8] Feng Z.L., Yin J.W., Chen G., Dong J.X., “Rearch on jacquard fabrics image denoising using Allen-Cahn level t model”, Journal of Zhejiang University (Engineering Science), Vol. 39, No. 2, pp. 185-189, 2005.
[9] Benes M., Chalupecky V., Mikula K., “Geometrical image gmentation by the Allen–Cahn equation”, Applied Numerical Mathematics, Vol. 51, No. 4, pp. 187-205, 2004.
[10] Barrett J.W., Nurnberg R., Styles V., “Finite Element Approximation of a Pha Field Model for Void Electromigration”, SIAM Journal on Numerical Analysis, Vol. 42 , No. 5, pp. 738-772, 2004.
[11] Provatas N., Goldenfeld N., Dantzig J., “Adaptive Mesh Refinement Computation of Solidification Microstructures using Dynamic Data Structures”, Journal of Computational Physics, Vol. 148, No. 1,pp. 265-290, 1999.
[12] De Giorgi E., Carriero M., et al., “Existence theorem for a minimum problem with free discontinuity t”, Archive for Rational Mechanics and Analysis, Vol. 11, No. 4, pp. 291-322, 1990.
[13] Modica L., “The gradient theory of pha transitions and the minimal interface criterion”, Archive for Rational Mechanics and Analysis, Vol. 98, No. 3, pp. 123-142, 1987.
