OPTIMISING DIFFERENT FEATURE TYPES FOR INPAINTING-BASED IMAGE REPRESENTATIONS Ferdinand Jost Vassillen Chizhov Joachim Weickert

2025-04-29 0 0 7.35MB 6 页 10玖币

侵权投诉

OPTIMISING DIFFERENT FEATURE TYPES

FOR INPAINTING-BASED IMAGE REPRESENTATIONS

Ferdinand Jost Vassillen Chizhov Joachim Weickert ∗

Mathematical Image Analysis Group, Faculty of Mathematics and Computer Science

Campus E1.7, Saarland University, 66041 Saarbr¨

ucken, Germany

{jost, chizhov, weickert}@mia.uni-saarland.de

ABSTRACT

Inpainting-based image compression is a promising alternative to

classical transform-based lossy codecs. Typically it stores a care-

fully selected subset of all pixel locations and their colour values. In

the decoding phase the missing information is reconstructed by an

inpainting process such as homogeneous diffusion inpainting. Opti-

mising the stored data is the key for achieving good performance. A

few heuristic approaches also advocate alternative feature types such

as derivative data and construct dedicated inpainting concepts. How-

ever, one still lacks a general approach that allows to optimise and

inpaint the data simultaneously w.r.t. a collection of different feature

types, their locations, and their values. Our paper closes this gap.

We introduce a generalised inpainting process that can handle arbi-

trary features which can be expressed as linear equality constraints.

This includes e.g. colour values and derivatives of any order. We

propose a fully automatic algorithm that aims at ﬁnding the optimal

features from a given collection as well as their locations and their

function values within a speciﬁed total feature density. Its perfor-

mance is demonstrated with a novel set of features that also includes

local averages. Our experiments show that it clearly outperforms the

popular inpainting with optimised colour data with the same density.

Index Terms—Inpainting, Constrained Optimisation, Voronoi

Diagram

1. INTRODUCTION

Inpainting is the process of reconstructing an image from a subset of

its data [1]. One of its most challenging applications is lossy image

compression. Inpainting-based codecs [2] typically store a few well

chosen pixel locations of the original image with their greyscale or

colour values. In the decoding phase, the missing image parts are in-

painted from these sparse data, often with a diffusion process. These

methods have been able to outperform even widely used transform-

based codecs such as JPEG and JPEG2000 [3]. Surprisingly, al-

ready the simple linear process such as homogeneous diffusion in-

painting can give good results, if the inpainting data is thoroughly

optimised [4]. This, however, is a highly nontrivial problem.

For achieving better visual quality, it has also been advocated to

replace the greyscale/colour data by gradient data [5, 6]. However,

these papers had to undertake various speciﬁc algorithmic adapta-

tions, and the data optimisation problem becomes even harder. To

further improve the quality, it has been suggested to combine the gra-

dient information with greyscale/colour data [6]. While this sounds

∗This work has received funding from the European Research Council

(ERC) under the European Union’s Horizon 2020 research and innovation

programme (grant agreement no. 741215, ERC Advanced Grant INCOVID).

promising, it has not been done so far. Moreover, it would be desir-

able to have a more general framework that allows a straightforward

incorporation of various classes of features without the need for ded-

icated optimisation algorithms.

1.1. Our Contributions

The goal of our paper is to address these challenges. Our contribu-

tions are threefold:

1. We establish a generalised inpainting framework for linear

inpainting operators that can handle any collection of features

in terms of linear equality constraints. This class is very large

and includes e.g. derivatives of any order.

2. We introduce an efﬁcient data selection strategy. It automati-

cally distributes the available data budget among all different

features and optimises both their locations and their values.

This automates and generalises the otherwise cumbersome

feature-speciﬁc selection and optimisation process.

3. We identify a novel collection of features that includes local

averages. Experiments show that it considerably improves the

inpainting quality compared to classical inpainting.

Since our paper focuses on feature integration and data optimisation,

we postpone any coding aspects to future work.

1.2. Related Work

Some inpainting-based codecs involve information at edges [7, 8] or

isolines [9]. However, these approaches still use grey values as their

only feature and just beneﬁt from the fact that contours allow an

inexpensive encoding of their locations.

Extensions of edge-like concepts that combine greyscale data

with the additional feature of discontinuities are presented in [10–

12]. In contrast to our approach they use speciﬁc segmentation con-

cepts which do not generalise to other feature classes.

There are various attempts to reconstruct an image from features

such as zero-crossings [13] or toppoints in scale-space [14], as well

as junctions [15], and SIFT features [16]. While these papers give

interesting information-theoretic insights, they do not offer compet-

itive image representations in terms of compression quality.

Typically, an optimal placement of the features is crucial for

the reconstruction quality. There has been a lot of work on spa-

tial optimisation in the context of image inpainting, including ana-

lytic approaches [17], non-smooth optimisation [18–20], neural net-

works [21], probabilistic sparsiﬁcation [4], and densiﬁcation algo-

rithms [22, 23]. By combining the ideas of error maps [22] and

Voronoi densiﬁcation [23], our approach falls into the latter class,

but is the ﬁrst one to generalise it to large collections of feature types.

Published in Proc. ICASSP2023, June 04-10, 2023, Rhodes Island, Greece © IEEE 2023

arXiv:2210.14949v3 [eess.IV] 14 May 2023

1.3. Paper Structure

In Section 2 we review homogeneous diffusion inpainting, we

rewrite it as a constrained optimisation problem that covers many

feature types, and we discuss efﬁcient solution strategies for our

novel, more general formulation. Section 3 introduces our strategy

for optimising the feature locations and their values. Finally, we

evaluate the performance of our framework in Section 4, and we

give a conclusion and an outlook on future work in Section 5.

2. OUR FRAMEWORK

In this section we give an overview of classical sparse inpainting

with homogeneous diffusion and rewrite it in a variational formula-

tion. This allows us to extend the problem and introduce any set of

features that can be formulated as linear equations. We then suggest

an efﬁcient solution strategy for this generalised inpainting problem.

2.1. Continuous Formulation

Consider a continuous greyscale image f(x):Ω→Rwhere x:=

[x, y]>denotes a position in the rectangular image domain Ω⊂R2.

We assume that we have stored a sparse representation of fonly on

the set of the inpainting mask K⊂Ω. A classical way [7] to inpaint

the missing data is to compute a reconstruction u: Ω →Rby

solving the Laplace equation with Dirichlet conditions on the mask

Kand reﬂecting boundary conditions on the domain boundary ∂Ω:

−∆u(x) = 0,x∈Ω\K,

u(x) = f(x),x∈K,

∂nu(x) = 0,x∈∂Ω,

(1)

where ∆ = ∂xx +∂yy is the Laplacian, and ndenotes the nor-

mal vector to the boundary ∂Ω. The fact that the Laplace equation

∆u= 0 is the steady state of the homogeneous diffusion equation

∂tu= ∆u[24] motivates the name homogeneous diffusion inpaint-

ing. Problem (1) can be derived as the Euler-Lagrange equation of

the variational formulation

min

2ZΩ

k∇u(x)k2dx= min

2ZΩ

u(x)(−∆)u(x)dx,

such that u(x) = f(x),x∈K,

(2)

where k · k denotes the Euclidean norm, and ∇= [∂x, ∂y]>is

the nabla operator. Here we have used the divergence theorem and

the reﬂecting boundary conditions. This formulation will provide a

straightforward way to introduce other types of constraints.

2.2. Discrete Formulation

Digital images are typically represented on a regular pixel grid. Then

the discrete analogue of fcan be represented as a vector fwith

dimension Nequal to the number of pixels. Similarly, we get the

reconstruction vector u∈RN. We also deﬁne the inpainting mask

vector c∈ {0,1}Nand its diagonal matrix C= diag(c). This

allows to discretise the Dirichlet constraints u(x) = f(x)on K

as Cu =Cf. Finally we obtain the matrix L∈RN×Nfrom

the standard 5-point stencil discretisation of the negated Laplacian

(−∆ui,j ≈(−ui,j+1 −ui+1,j + 4ui,j −ui−1,j −ui,j−1)/h2) with

reﬂecting boundary conditions. Putting everything together results

in the discrete analogue to Equation (2):

min

2u>Lu,s.t. Cu =Cf.(3)

Since Lis a discretisation of −∆, it is a positive semideﬁnite matrix.

Thus, the above is a special case of a quadratic programming prob-

lem with linear equality constraints [25]. If the mask is non-empty,

Equation (3) can be shown to have a unique solution that matches

the unique solution of a direct discretisation of (1); see also [8].

2.3. Generalised Discrete Formulation

Our goal is to extend the discrete inpainting in Equation (3) to not

only consider grey values as constraints, but a collection of features

that can be implemented through linear equality constraints. To this

end, we replace the Dirichlet constraints Cu =Cf by mtypes of

constraints of the form CiAiu=CiAifwith i∈ {1,...,m}:

min

2u>Lu,s.t. Au =b

A:= 



C1A1

. . .

CmAm



,b:= 



C1A1f

. . .

CmAmf



.

(4)

The matrices Ai∈RN×Ndescribe convolutions with user-deﬁned

feature stencils. For example, we can implement Dirichlet con-

straints through A1=Iwith identity matrix I. First-order deriva-

tive constraints can be modelled by A2=Dxand A3=Dywith

forward difference matrices Dx,Dythat approximate ∂x, ∂y. Also

local integral constraints can be included easily, since they are linear

operators as well. We also note that the above formulation is rather

general w.r.t. the discrete linear inpainting operator L: It can be any

symmetric positive semideﬁnite matrix, e.g. a discretisation of the

biharmonic operator ∆2. Considering linear inpainting operators

and linear constraints keeps our discussion simple and is not very

limiting, since they can give good reconstructions, if the data is

optimised carefully [4]. Extending this inpainting to colour images

is straightforward: We can treat each channel separately.

2.4. Numerical Solution Strategy

The constrained optimisation problem (4) can be solved with a La-

grange multiplier approach [25]. This turns it into an unconstrained

one by introducing an additional vector λ∈RmN of unknowns:

min

umax

λ1

2u>Lu +λ>(Au −b).(5)

Setting the derivatives w.r.t. uand λto zero gives the linear system

L A>

A0u

λ=0

b.(6)

Its system matrix is symmetric but indeﬁnite. After evaluating a

variety of solvers, our algorithm of choice is SYMMLQ [26]. Sim-

ilar to the conjugate gradients solver [27] it can be derived from the

Lanczos method. However, unlike conjugate gradients, it is able to

handle indeﬁnite matrices. In fact, it can even handle singular sys-

tems as long as those have a solution. This is useful in our setting,

since it even allows for features that are linearly dependent.

3. DATA OPTIMISATION

In order to achieve a good reconstruction quality with small error

ku−fk2, one must optimise the feature masks Ciand the stored

feature values bin Equation (4). Thus, let us now propose an efﬁ-

cient and generic spatial optimisation algorithm for the masks Ci,

as well as a tonal optimisation method for the feature values b.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OPTIMISINGDIFFERENTFEATURETYPESFORINPAINTING-BASEDIMAGEREPRESENTATIONSFerdinandJostVassillenChizhovJoachimWeickertMathematicalImageAnalysisGroup,FacultyofMathematicsandComputerScienceCampusE1.7,SaarlandUniversity,66041Saarbr¨ucken,Germanyfjost,chizhov,weickertg@mia.uni-saarland.deABSTRACTInpainting...

展开>> 收起<<

OPTIMISING DIFFERENT FEATURE TYPES FOR INPAINTING-BASED IMAGE REPRESENTATIONS Ferdinand Jost Vassillen Chizhov Joachim Weickert.pdf

共6页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

OPTIMISING DIFFERENT FEATURE TYPES FOR INPAINTING-BASED IMAGE REPRESENTATIONS Ferdinand Jost Vassillen Chizhov Joachim Weickert

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: