text: Noname manuscript No. (will be inserted by the editor) Connectivity-preserving Geometry Images · · · · · Shaofan Wang Dehui Kong Juan Xue Weijia Zhu Min Xu · Baocai Yin Hubert Roth Received: date / Accepted: date Abstract We propose connectivity-preserving geome- 1 Introduction try images (CGIMs), which map a triangular mesh onto a rectangular regular array of an image, such that the Geometry images (GIMs) are a completely regular reconstructed mesh produces no sampling errors, but remeshing method, which represents a three-dimensional merely round-oﬀ errors over the coordinates of vertices. mesh using an image-like structure, with the connectiv- By using permutation techniques on vertices, CGIMs ity information encoded in the image space [1]. The ﬁrst obtain a V-matrix whose elements are vertices of main procedure of GIMs includes three steps: mesh the original mesh, which intrinsically preserves the vertex- parametrization, sampling and scaling. A three-dimensional set and connectivity of the original mesh, and then mesh is ﬁrst mapped onto a square or spherical para- generate a CGIM array by transforming the Cartesian metric domain, and a three-dimensional matrix is then coordinates of corresponding vertices of the V-matrix obtained by sampling coordinates of points over the into RGB values. Compared with traditional geometry parametrized domain, and the matrix is ﬁnally trans- images (GIMs), CGIMs achieve the minimum recon- formed into an image array with a proper scaling. To struction error with a parametrization-free algorithm. rebuild the mesh, the vertices are obtained by trans- We apply CGIMs to lossy compression of meshes. Ex- forming the RGB values of the image into Cartesian perimental results show that while CGIMs produce a coordinates, and the edges are obtained by connecting lower eﬃciency in both encoding and decoding time and all the pairwise vertices which are adjacent in the array. larger resolutions than traditional GIMs, CGIMs per- The reconstruction error arising from GIMs includes form better Peak Signal-to-Noise Ratios and preserve two parts: the sampling error produced in the sampling details better than GIMs especially with the multi-stage step, depending on the parametrization methods, the base color and index map scheme, because CGIMs treat sampling methods, GIM resolutions and interpolating details and non-details of meshes evenly as all elements functions, and the round-oﬀ error produced trivially in of the V-matrix. the scaling step, depending on the scaling between the · · · coordinate values of vertices and RGB values of GIMs. Keywords GIM CGIM remeshing mesh · To eﬀectively decrease reconstruction errors, a so- parametrization connectivity-preserving lution is to adopt a mesh parametrization minimiz- S. Wang, D. Kong, J. Xue, W. Zhu, B. Yin ing the geometric stretch in GIMs, where the stretch Beijing Key Laboratory of Multimedia Intelligent Software metric is derived from a Taylor expansion of geomet- Technology, College of Metropolitan Transportation, Beijing ric errors. Although such a parametrization is directly University of Technology, Beijing 100124, China derived from the reconstruction error, it is diﬃcult to E-mail: wangshaofan@bjut.edu.cn achieve the global minimizer of the metric because of M. Xu the multivariate nonconvex optimization problem. An School of Mathematical Sciences, Dalian University of Tech- nology, Dalian 116085, China alternative is to ﬁrst map the whole mesh piecewise onto several charts, each of which has small distortion and H. Roth Institute of Automatic Control Engineering, University of hence is eﬀectively sampled, and then pack them to- Siegen, Siegen 57068, Germany gether into a GIM. Such methods, referred to as multi- ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Noname

text: manuscript

text: No.

text: (will

text: be

text: inserted

text: by

text: the

text: editor)

text: Connectivity-preserving

label: title

text: Geometry

text: Images

label: author

text: Shaofan

text: Wang

text: Dehui

text: Kong

text: Juan

text: Xue

text: Weijia

text: Zhu

text: Min

text: Xu

text: Baocai

text: Yin

text: Hubert

text: Roth

text: Received:

label: date

text: date

text: Accepted:

text: date

text: Abstract

text: We

label: abstract

text: propose

text: connectivity-preserving

text: geome-

text: Introduction

text: try

text: images

text: (CGIMs),

text: which

text: map

text: a

text: triangular

text: mesh

text: onto

text: a

text: rectangular

text: regular

text: array

text: of

text: an

text: image,

text: such

text: that

text: the

text: Geometry

text: images

text: (GIMs)

text: are

text: a

text: completely

text: regular

text: reconstructed

text: mesh

text: produces

text: no

text: sampling

text: errors,

text: but

text: remeshing

text: method,

text: which

text: represents

text: a

text: three-dimensional

text: merely

text: round-oﬀ

text: errors

text: over

text: the

text: coordinates

text: of

text: vertices.

text: mesh

text: using

text: an

text: image-like

text: structure,

text: with

text: the

text: connectiv-

text: By

text: using

text: permutation

text: techniques

text: on

text: vertices,

text: CGIMs

text: ity

text: information

text: encoded

text: in

text: the

text: image

text: space

text: The

text: ﬁrst

text: obtain

text: a

text: V-matrix

text: whose

text: elements

text: are

text: vertices

text: of

text: main

text: procedure

text: of

text: GIMs

text: includes

text: three

text: steps:

text: mesh

text: the

text: original

text: mesh,

text: which

text: intrinsically

text: preserves

text: the

text: vertex-

text: parametrization,

text: sampling

text: and

text: scaling.

text: A

text: three-dimensional

text: set

text: and

text: connectivity

text: of

text: the

text: original

text: mesh,

text: and

text: then

text: mesh

text: is

text: ﬁrst

text: mapped

text: onto

text: a

text: square

text: or

text: spherical

text: para-

text: generate

text: a

text: CGIM

text: array

text: by

text: transforming

text: the

text: Cartesian

text: metric

text: domain,

text: and

text: a

text: three-dimensional

text: matrix

text: is

text: then

text: coordinates

text: of

text: corresponding

text: vertices

text: of

text: the

text: V-matrix

text: obtained

text: by

text: sampling

text: coordinates

text: of

text: points

text: over

text: the

text: into

text: RGB

text: values.

text: Compared

text: with

text: traditional

text: geometry

text: parametrized

text: domain,

text: and

text: the

text: matrix

text: is

text: ﬁnally

text: trans-

text: images

text: (GIMs),

text: CGIMs

text: achieve

text: the

text: minimum

text: recon-

text: formed

text: into

text: an

text: image

text: array

text: with

text: a

text: proper

text: scaling.

text: To

text: struction

text: error

text: with

text: a

text: parametrization-free

text: algorithm.

text: rebuild

text: the

text: mesh,

text: the

text: vertices

text: are

text: obtained

text: by

text: trans-

text: We

text: apply

text: CGIMs

text: to

text: lossy

text: compression

text: of

text: meshes.

text: Ex-

text: forming

text: the

text: RGB

text: values

text: of

text: the

text: image

text: into

text: Cartesian

text: perimental

text: results

text: show

text: that

text: while

text: CGIMs

text: produce

text: a

text: coordinates,

text: and

text: the

text: edges

text: are

text: obtained

text: by

text: connecting

text: lower

text: eﬃciency

text: in

text: both

text: encoding

text: and

text: decoding

text: time

text: and

text: all

text: the

text: pairwise

text: vertices

text: which

text: are

text: adjacent

text: in

text: the

text: array.

text: larger

text: resolutions

text: than

text: traditional

text: GIMs,

text: CGIMs

text: per-

text: The

text: reconstruction

text: error

text: arising

text: from

text: GIMs

text: includes

text: form

text: better

text: Peak

text: Signal-to-Noise

text: Ratios

text: and

text: preserve

text: two

text: parts:

text: the

text: sampling

text: error

text: produced

text: in

text: the

text: sampling

text: details

text: better

text: than

text: GIMs

text: especially

text: with

text: the

text: multi-stage

text: step,

text: depending

text: on

text: the

text: parametrization

text: methods,

text: the

text: base

text: color

text: and

text: index

text: map

text: scheme,

text: because

text: CGIMs

text: treat

text: sampling

text: methods,

text: GIM

text: resolutions

text: and

text: interpolating

text: details

text: and

text: non-details

text: of

text: meshes

text: evenly

text: as

text: all

text: elements

text: functions,

text: and

text: the

text: round-oﬀ

text: error

text: produced

text: trivially

text: in

text: of

text: the

text: V-matrix.

text: the

text: scaling

text: step,

text: depending

text: on

text: the

text: scaling

text: between

text: the

text: coordinate

text: values

text: of

text: vertices

text: and

text: RGB

text: values

text: of

text: GIMs.

text: Keywords

text: GIM

text: CGIM

text: remeshing

text: mesh

text: To

text: eﬀectively

text: decrease

text: reconstruction

text: errors,

text: a

text: so-

text: parametrization

text: connectivity-preserving

text: lution

text: is

text: to

text: adopt

text: a

text: mesh

text: parametrization

text: minimiz-

text: S.

text: Wang,

text: D.

text: Kong,

text: J.

text: Xue,

text: W.

text: Zhu,

text: B.

text: Yin

text: ing

text: the

text: geometric

text: stretch

text: in

text: GIMs,

text: where

text: the

text: stretch

text: Beijing

text: Key

text: Laboratory

text: of

text: Multimedia

text: Intelligent

text: Software

text: metric

text: is

text: derived

text: from

text: a

text: Taylor

text: expansion

text: of

text: geomet-

text: Technology,

text: College

text: of

text: Metropolitan

text: Transportation,

text: Beijing

text: ric

text: errors.

text: Although

text: such

text: a

text: parametrization

text: is

text: directly

text: University

text: of

text: Technology,

text: Beijing

text: China

text: derived

text: from

text: the

text: reconstruction

text: error,

text: it

text: is

text: diﬃcult

text: to

text: E-mail:

text: wangshaofan@bjut.edu.cn

text: achieve

text: the

text: global

text: minimizer

text: of

text: the

text: metric

text: because

text: of

text: M.

text: Xu

text: the

text: multivariate

text: nonconvex

text: optimization

text: problem.

text: An

text: School

text: of

text: Mathematical

text: Sciences,

text: Dalian

text: University

text: of

text: Tech-

text: nology,

text: Dalian

text: China

text: alternative

text: is

text: to

text: ﬁrst

text: map

text: the

text: whole

text: mesh

text: piecewise

text: onto

text: several

text: charts,

text: each

text: of

text: which

text: has

text: small

text: distortion

text: and

text: H.

text: Roth

text: Institute

text: of

text: Automatic

text: Control

text: Engineering,

text: University

text: of

text: hence

text: is

text: eﬀectively

text: sampled,

text: and

text: then

text: pack

text: them

text: to-

text: Siegen,

text: Siegen

text: Germany

text: gether

text: into

text: a

text: GIM.

text: Such

text: methods,

text: referred

text: to

text: as

text: multi-

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 12 Table 1 Comparisons of resolutions, ﬁle sizes and running time of CGIMs with respect to traditional GIMs for eight models. The ﬁrst to fourth columns are the names, number of vertices, number of faces, ﬁle sizes of original models, respectively; the seventh to tenth columns are running time of CGIMs, modiﬁed CGIMs, lossless reconstruction from CGIMs, lossy recon- struction from CGIMs (averaged with ﬁve compression rates in JPEG2000), respectively; the thirteenth to ﬁfteenth columns are running time of traditional GIMs, lossless reconstruction from GIMs, lossy reconstruction from GIMs (averaged with ﬁve compression rates in JPEG2000), respectively. CGIM resolutions/size (MB)/time (s) GIM resolutions/size (MB)/time (s) | | | | size models V F modiﬁed lossless lossy lossless lossy (MB) resolutions size CGIM resolutions size GIM CGIM reconst reconst reconst reconst × × cylinder 1663 3299 0.10 218 294 0.18 20 69 4 87 512 512 0.77 56 20 20 × × fist 1198 2369 0.07 122 197 0.07 10 35 2 23 512 512 0.77 34 20 20 × × foot 10010 19974 0.66 423 970 1.17 667 1351 31 690 512 512 0.77 126 21 21 × × camel 11381 22704 0.75 475 897 1.21 758 1716 32 905 512 512 0.77 184 21 21 × × face 40969 81485 2.74 538 1493 2.29 902 2294 67 1638 1024 1024 3.0 617 83 83 × × head 25445 50801 1.69 757 1664 3.60 5445 9801 96 3259 1024 1024 3.0 311 84 83 × × david 23889 47280 1.53 841 1751 4.21 7889 17280 203 5491 1024 1024 3.0 270 83 83 × × hand 53054 105860 3.71 1468 3048 12.8 13054 20866 338 12872 1024 1024 3.0 922 84 83 recover the thumb part of the fist model better than Discussion Fig. 8 implies that CGIMs have promis- GIMs do; this is mainly because the parametrization ing advantages in preserving details compared with tra- puts the original vertices of the thumb into a smaller ditional GIMs. The reason is that GIMs treat a mesh region and imposes an inadequate sampling over that with a regular sampling over parametrized domain and region. Reconstructed meshes for GIMs look smooth hence incur a loss in high distortion parts (e.g., david’s in general, but fail in representing some details (e.g., eyes), whereas CGIMs treat details and non-details of cylinder’s top and david’s eyes); nevertheless, recon- a mesh evenly as the elements of the V-matrix. Al- structed meshes for CGIMs look coarse in lower target though the magniﬁed details show that GIMs produce rates (e.g., bunny’s ears). more compact grids in david’s eyebrows than CGIMs do, what CGIMs show is close to the faithful geometry Quantitative results We show the PSNR curves of the model. in Fig. 9, where the x-axis represents ﬁle sizes given by setting diﬀerent target rates (in JPEG2000) or diﬀerent Moreover, with the same codec JPEG2000, CGIMs quantization parameters (in MBCIM), and the y-axis do not perform better PSNRs than GIMs, but CGIMs represents the PSNR values. For cylinder, face, fist, with MBCIM codec perform better PSNRs than CGIMs CGIMs achieve better than GIMs in the whole part of with JPEG2000. This is mainly because CGIMs usu- curve, which is mainly because those three models have ally have large resolutions compared with GIMs as we small resolutions with respect to the original size of the mentioned before, which increases the compressed ﬁle mesh. In particular, fist has a bad parametrization on size for the same target rate during encoding. For large its thumb part, leading to an insuﬃcient sampling over distortion models (david, bunny, venus), CGIMs do that part and hence a bad reconstruction using GIMs. not have better PSNRs for small target rates, as the × On the other hand, GIMs with resolutions 1024 1024 quantization error produces incorrect connectivity in achieve better results for david, bunny, venus in the the cluster algorithm. Such an error decreases and ac- most part of curves, while CGIMs achieve better results cordingly the PSNR increases when the target rate is when the compression rate tends to be lower. Moreover larger. Also, MBCIM is more suitable than JPEG2000 we see that CGIMs with MBCIM coding achieve better for CGIM compression according to the experimental rate distortions than CGIMs with JPEG2000. Also, the results. Yet, CGIMs give bad PSNRs for meshes with rate distortions strongly depend on the resolutions of much larger distortion (see Fig. 10, a failure example of CGIMs: the smaller the resolutions are, the better rate hand), as those meshes have large resolutions of CGIMs distortions CGIMs achieve. and consequently the compressed ﬁle size is large for a given compression rate. Therefore, reconstruction errors of CGIMs for lossy 7 Conclusions compression depends on the quantization errors of coor- dinates of vertices, incorrect cluster algorithms during reconstructions and the incorrect connectivity incurred Advantages This paper proposes CGIMs, which by quantization errors and incorrect cluster algorithms; represent genus-zero triangular meshes by embedding moreover, the PSNR depends on the three ingredients a mesh onto a rectangular array which preserves the given above, as well as the CGIM resolutions. connectivity of vertices with round-oﬀ errors on coordi- ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: Table

text: Comparisons

label: caption

text: of

text: resolutions,

text: ﬁle

text: sizes

text: and

text: running

text: time

text: of

text: CGIMs

text: with

text: respect

text: to

text: traditional

text: GIMs

text: for

text: eight

text: models.

text: The

text: ﬁrst

text: to

text: fourth

text: columns

text: are

text: the

text: names,

text: number

text: of

text: vertices,

text: number

text: of

text: faces,

text: ﬁle

text: sizes

text: of

text: original

text: models,

text: respectively;

text: the

text: seventh

text: to

text: tenth

text: columns

text: are

text: running

text: time

text: of

text: CGIMs,

text: modiﬁed

text: CGIMs,

text: lossless

text: reconstruction

text: from

text: CGIMs,

text: lossy

text: recon-

text: struction

text: from

text: CGIMs

text: (averaged

text: with

text: ﬁve

text: compression

text: rates

text: in

text: respectively;

text: the

text: thirteenth

text: to

text: ﬁfteenth

text: columns

text: are

text: running

text: time

text: of

text: traditional

text: GIMs,

text: lossless

text: reconstruction

text: from

text: GIMs,

text: lossy

text: reconstruction

text: from

text: GIMs

text: (averaged

text: with

text: ﬁve

text: compression

text: rates

text: in

text: respectively.

text: CGIM

label: table

text: resolutions/size

text: (MB)/time

text: (s)

text: GIM

text: resolutions/size

text: (MB)/time

text: (s)

text: size

text: models

text: V

text: F

text: modiﬁed

text: lossless

text: lossy

text: lossless

text: lossy

text: (MB)

text: resolutions

text: size

text: CGIM

text: resolutions

text: size

text: GIM

text: CGIM

text: reconst

text: reconst

text: reconst

text: reconst

text: cylinder

text: fist

text: foot

text: camel

text: face

text: head

text: david

text: hand

text: recover

text: the

text: thumb

text: part

text: of

text: the

text: fist

text: model

text: better

text: than

text: Discussion

text: Fig.

text: implies

text: that

text: CGIMs

text: have

text: promis-

text: GIMs

text: do;

text: this

text: is

text: mainly

text: because

text: the

text: parametrization

text: ing

text: advantages

text: in

text: preserving

text: details

text: compared

text: with

text: tra-

text: puts

text: the

text: original

text: vertices

text: of

text: the

text: thumb

text: into

text: a

text: smaller

text: ditional

text: GIMs.

text: The

text: reason

text: is

text: that

text: GIMs

text: treat

text: a

text: mesh

text: region

text: and

text: imposes

text: an

text: inadequate

text: sampling

text: over

text: that

text: with

text: a

text: regular

text: sampling

text: over

text: parametrized

text: domain

text: and

text: region.

text: Reconstructed

text: meshes

text: for

text: GIMs

text: look

text: smooth

text: hence

text: incur

text: a

text: loss

text: in

text: high

text: distortion

text: parts

text: (e.g.,

text: david’s

text: in

text: general,

text: but

text: fail

text: in

text: representing

text: some

text: details

text: (e.g.,

text: eyes),

text: whereas

text: CGIMs

text: treat

text: details

text: and

text: non-details

text: of

text: cylinder’s

text: top

text: and

text: david’s

text: eyes);

text: nevertheless,

text: recon-

text: a

text: mesh

text: evenly

text: as

text: the

text: elements

text: of

text: the

text: V-matrix.

text: Al-

text: structed

text: meshes

text: for

text: CGIMs

text: look

text: coarse

text: in

text: lower

text: target

text: though

text: the

text: magniﬁed

text: details

text: show

text: that

text: GIMs

text: produce

text: rates

text: (e.g.,

text: bunny’s

text: ears).

text: more

text: compact

text: grids

text: in

text: david’s

text: eyebrows

text: than

text: CGIMs

text: do,

text: what

text: CGIMs

text: show

text: is

text: close

text: to

text: the

text: faithful

text: geometry

text: Quantitative

text: results

text: We

text: show

text: the

text: PSNR

text: curves

text: of

text: the

text: model.

text: in

text: Fig.

text: where

text: the

text: x-axis

text: represents

text: ﬁle

text: sizes

text: given

text: by

text: setting

text: diﬀerent

text: target

text: rates

text: (in

text: or

text: diﬀerent

text: Moreover,

text: with

text: the

text: same

text: codec

text: CGIMs

text: quantization

text: parameters

text: (in

text: MBCIM),

text: and

text: the

text: y-axis

text: do

text: not

text: perform

text: better

text: PSNRs

text: than

text: GIMs,

text: but

text: CGIMs

text: represents

text: the

text: PSNR

text: values.

text: For

text: cylinder,

text: face,

text: fist,

text: with

text: MBCIM

text: codec

text: perform

text: better

text: PSNRs

text: than

text: CGIMs

text: CGIMs

text: achieve

text: better

text: than

text: GIMs

text: in

text: the

text: whole

text: part

text: of

text: with

text: This

text: is

text: mainly

text: because

text: CGIMs

text: usu-

text: curve,

text: which

text: is

text: mainly

text: because

text: those

text: three

text: models

text: have

text: ally

text: have

text: large

text: resolutions

text: compared

text: with

text: GIMs

text: as

text: we

text: small

text: resolutions

text: with

text: respect

text: to

text: the

text: original

text: size

text: of

text: the

text: mentioned

text: before,

text: which

text: increases

text: the

text: compressed

text: ﬁle

text: mesh.

text: In

text: particular,

text: fist

text: has

text: a

text: bad

text: parametrization

text: on

text: size

text: for

text: the

text: same

text: target

text: rate

text: during

text: encoding.

text: For

text: large

text: its

text: thumb

text: part,

text: leading

text: to

text: an

text: insuﬃcient

text: sampling

text: over

text: distortion

text: models

text: (david,

text: bunny,

text: venus),

text: CGIMs

text: do

text: that

text: part

text: and

text: hence

text: a

text: bad

text: reconstruction

text: using

text: GIMs.

text: not

text: have

text: better

text: PSNRs

text: for

text: small

text: target

text: rates,

text: as

text: the

text: On

text: the

text: other

text: hand,

text: GIMs

text: with

text: resolutions

text: quantization

text: error

text: produces

text: incorrect

text: connectivity

text: in

text: achieve

text: better

text: results

text: for

text: david,

text: bunny,

text: venus

text: in

text: the

text: the

text: cluster

text: algorithm.

text: Such

text: an

text: error

text: decreases

text: and

text: ac-

text: most

text: part

text: of

text: curves,

text: while

text: CGIMs

text: achieve

text: better

text: results

text: cordingly

text: the

text: PSNR

text: increases

text: when

text: the

text: target

text: rate

text: is

text: when

text: the

text: compression

text: rate

text: tends

text: to

text: be

text: lower.

text: Moreover

text: larger.

text: Also,

text: MBCIM

text: is

text: more

text: suitable

text: than

text: we

text: see

text: that

text: CGIMs

text: with

text: MBCIM

text: coding

text: achieve

text: better

text: for

text: CGIM

text: compression

text: according

text: to

text: the

text: experimental

text: rate

text: distortions

text: than

text: CGIMs

text: with

text: Also,

text: the

text: results.

text: Yet,

text: CGIMs

text: give

text: bad

text: PSNRs

text: for

text: meshes

text: with

text: rate

text: distortions

text: strongly

text: depend

text: on

text: the

text: resolutions

text: of

text: much

text: larger

text: distortion

text: (see

text: Fig.

text: a

text: failure

text: example

text: of

text: CGIMs:

text: the

text: smaller

text: the

text: resolutions

text: are,

text: the

text: better

text: rate

text: hand),

text: as

text: those

text: meshes

text: have

text: large

text: resolutions

text: of

text: CGIMs

text: distortions

text: CGIMs

text: achieve.

text: and

text: consequently

text: the

text: compressed

text: ﬁle

text: size

text: is

text: large

text: for

text: a

text: given

text: compression

text: rate.

text: Therefore,

text: reconstruction

text: errors

text: of

text: CGIMs

text: for

text: lossy

text: Conclusions

text: compression

text: depends

text: on

text: the

text: quantization

text: errors

text: of

text: coor-

text: dinates

text: of

text: vertices,

text: incorrect

text: cluster

text: algorithms

text: during

text: reconstructions

text: and

text: the

text: incorrect

text: connectivity

text: incurred

text: Advantages

text: This

text: paper

text: proposes

text: CGIMs,

text: which

text: by

text: quantization

text: errors

text: and

text: incorrect

text: cluster

text: algorithms;

text: represent

text: genus-zero

text: triangular

text: meshes

text: by

text: embedding

text: moreover,

text: the

text: PSNR

text: depends

text: on

text: the

text: three

text: ingredients

text: a

text: mesh

text: onto

text: a

text: rectangular

text: array

text: which

text: preserves

text: the

text: given

text: above,

text: as

text: well

text: as

text: the

text: CGIM

text: resolutions.

text: connectivity

text: of

text: vertices

text: with

text: round-oﬀ

text: errors

text: on

text: coordi-

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 3 g h i g g g h i not obtain a V-matrix preserving the vertex-set and the g g g h i ' ' ' ' ' isomatrix isogim reconstruct edge-set of the mesh unless all the levels obtained from d e f d d e f f d'd'e'f'f' previous phase have the same length. The AlignAllLevels a b c c c a b c c c a b c ' ' ' ' ' phase accomplishes this work by adding repeated ele- f ments within each level such that the pairwise levels f f f f f' f' f' f' d e isomatrix a d e b isogim reconstruct a'd'e'b' obtained from previous phase are exactly the same. a c b b a c b b 4 Details of CGIMs ' ' ' ' a c b a b b b a'b'b'b' This section gives details of all phases of CGIMs. Fig. 1 CGIM examples. Columns 1-4: original meshes, V- matrices, CGIM arrays, reconstructed meshes, respectively. We ﬁrst introduce some deﬁnitions and notations. M R ∼ Let be a triangular mesh in 3. We denote v w M if the vertices v, w are adjacent in , otherwise we whose elements are vertices of the mesh, and call each (cid:54)∼ denote v w; we denote v = w if the vertices v, w are v to be an element of the level. M (cid:54) i the same vertex in , otherwise we denote v = w. We Stratify The Stratify phase gives a sequence of denote V , E, V to be the vertex-set, the edge-set, the levels of the mesh (each level contains no repeated ele- B M collection of all boundary vertices of respectively, ments but diﬀerent levels may share common elements and denote N(v) to be the collection of all the vertices and may have diﬀerent lengths) such that the union of M adjacent to v in . all elements of all the levels is equal to the vertex-set of M A V-matrix with respect to is deﬁned to be a the mesh. Obtaining such a level sequence is a funda- two-dimensional array whose elements are vertices of mental work for the isomatrix phase, and has to satisfy M M ; a level of is deﬁned to be an n-tuple [v , . . . , v ] several properties described in Lemma 1, Section A of M 1 n whose elements are vertices of , where n is called the supplementary material. Basically such properties L the length of the level. We denote (j) to be the j- guarantee that each edge of the mesh be characterized L th element of a level , and we call j to be the index either by pairwise neighboring elements of a level (such L L ≤ ≤ L of v in if v = (j), 1 j n. We denote (end) an edge is referred to as an intra-level edge), or by pair- L L to be the last element of , and denote (j : j ) := wise elements from two neighboring levels (such an edge L L L ≤ 1 2 [ (j ), (j +1), . . . , (j )] if j j ; otherwise, we de- is referred to as an inter-level edge) 1. 1L 1 ∅ 2 1 | 2| note (j : j ) := . We denote A to be the number Align2Levels The Align2Levels phase transforms 1 2 of all elements of a set A or the length of a level A, each level obtained in previous phase to two levels, one |L| and denote to be the number of all v’s of a level of which coincides with the former level and the other L v . We adopt the convention that when we perform set of which coincides with the latter level, by inserting re- ∈ ∩ ∪ \ L L operations (e.g. , , , ) on a level , then repre- peated elements within each level. This work guarantees sents the collection of all diﬀerent elements of the level that the lengths of two neighboring levels be the same L (cid:48) L L(cid:48) . Let v, v be vertices and let , be levels. Then v and the end-vertices of each inter-level edge appear in (cid:48) L (cid:48) ∼ ∈ L is called an adjacent element of v in if v v ; correct locations. L(cid:48) L moreover, v is called an adjacent element of in if AlignAllLevels Although the inter-level edges are (cid:48) ∈ L(cid:48) (cid:48) ∼ ∈ L there exists v such that v v . preserved in pairwise levels and the intra-level edges are L L M Let , be two levels of with the same preserved in neighboring elements of each level, we can- 1 2 L L length. The edge-set induced by , , denoted by L L 1 2 1 The Stratify phase essentially divides all faces of the input edge( 1; 2), is deﬁned to be the collection of pair- mesh into several triangle strips [15], i.e., series of connected [(cid:2) ] edge((cid:2)1;(cid:2)2) wise vertices obtained triangles sharing vertices. To see this, we observe that the (cid:2)1 by connecting each pair 2 ﬁrst example of Fig. 1 can be described by using two strips: of distinct neighboring elements (the horizontal, verti- dgehfi,adbecf, with dgehfi corresponding to the face set L L generated by the ﬁrst and second output levels, and adbecf cal and slash directions) of 1, 2, i.e. corresponding to the face set generated by the second and third output levels (the red triangles of the last column). Sim- L L ∪ {L L L L edge( ; ) := (j) (j+1), (j) (j+1), ilarly, the second example of Fig. 1 can be described by using 1 2 j 1 1 2 2 L L L L } three strips: afdefb,adceb,acb, with afdefb corresponding to (j) (j), (j+1) (j) , 1 2 1 2 the face set generated by the ﬁrst and second output levels, and adceb corresponding to the face set generated by the sec- ond and third output levels, and acb corresponding to the face each element of which has distinct end-vertices, with set generated by the third and fourth output levels. While tri- the index j taking all available values. angle strips propose an eﬃcient storage of triangular meshes, L Let , j = 1, . . . , n be a level sequence of the mesh, such a method cannot generate an image-like array of vertices ≥ j (cid:104)·(cid:105) and hence no image codec can be imposed. n 3. The concatenate operator which maps the ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: g

font: default

text: h

text: i

text: g

text: g

text: g

text: h

text: i

text: not

text: obtain

text: a

text: V-matrix

text: preserving

text: the

text: vertex-set

text: and

text: the

text: g

text: g

text: g

text: h

text: i

text: isomatrix

text: isogim

text: reconstruct

text: edge-set

text: of

text: the

text: mesh

text: unless

text: all

text: the

text: levels

text: obtained

text: from

text: d

text: e

text: f

text: d

text: d

text: e

text: f

text: f

text: d'd'e'f'f'

text: previous

text: phase

text: have

text: the

text: same

text: length.

text: The

text: AlignAllLevels

text: a

text: b

text: c

text: c

text: c

text: a

text: b

text: c

text: c

text: c

text: a

text: b

text: c

text: phase

text: accomplishes

text: this

text: work

text: by

text: adding

text: repeated

text: ele-

text: f

text: ments

text: within

text: each

text: level

text: such

text: that

text: the

text: pairwise

text: levels

text: f

text: f

text: f

text: f

text: f'

text: f'

text: f'

text: f'

text: d

text: e

text: isomatrix

text: a

text: d

text: e

text: b

text: isogim

text: reconstruct

text: a'd'e'b'

text: obtained

text: from

text: previous

text: phase

text: are

text: exactly

text: the

text: same.

text: a

text: c

text: b

text: b

text: a

text: c

text: b

text: b

text: Details

text: of

text: CGIMs

text: a

text: c

text: b

text: a

text: b

text: b

text: b

text: a'b'b'b'

text: This

text: section

text: gives

text: details

text: of

text: all

text: phases

text: of

text: CGIMs.

text: Fig.

text: CGIM

text: examples.

text: Columns

text: original

text: meshes,

text: V-

text: matrices,

text: CGIM

text: arrays,

text: reconstructed

text: meshes,

text: respectively.

text: We

text: ﬁrst

text: introduce

text: some

text: deﬁnitions

text: and

text: notations.

text: M

text: R

text: Let

text: be

text: a

text: triangular

text: mesh

text: in

text: We

text: denote

text: v

text: w

text: M

text: if

text: the

text: vertices

text: v,

text: w

text: are

text: adjacent

text: in

text: otherwise

text: we

text: whose

text: elements

text: are

text: vertices

text: of

text: the

text: mesh,

text: and

text: call

text: each

text: denote

text: v

text: w;

text: we

text: denote

text: v

text: w

text: if

text: the

text: vertices

text: v,

text: w

text: are

text: v

text: to

text: be

text: an

text: element

text: of

text: the

text: level.

text: M

text: i

text: the

text: same

text: vertex

text: in

text: otherwise

text: we

text: denote

text: v

text: w.

text: We

text: Stratify

text: The

text: Stratify

text: phase

text: gives

text: a

text: sequence

text: of

text: denote

text: V

text: E,

text: V

text: to

text: be

text: the

text: vertex-set,

text: the

text: edge-set,

text: the

text: levels

text: of

text: the

text: mesh

text: (each

text: level

text: contains

text: no

text: repeated

text: ele-

text: B

text: M

text: collection

text: of

text: all

text: boundary

text: vertices

text: of

text: respectively,

text: ments

text: but

text: diﬀerent

text: levels

text: may

text: share

text: common

text: elements

text: and

text: denote

text: N(v)

text: to

text: be

text: the

text: collection

text: of

text: all

text: the

text: vertices

text: and

text: may

text: have

text: diﬀerent

text: lengths)

text: such

text: that

text: the

text: union

text: of

text: M

text: adjacent

text: to

text: v

text: in

text: all

text: elements

text: of

text: all

text: the

text: levels

text: is

text: equal

text: to

text: the

text: vertex-set

text: of

text: M

text: A

text: V-matrix

text: with

text: respect

text: to

text: is

text: deﬁned

text: to

text: be

text: a

text: the

text: mesh.

text: Obtaining

text: such

text: a

text: level

text: sequence

text: is

text: a

text: funda-

text: two-dimensional

text: array

text: whose

text: elements

text: are

text: vertices

text: of

text: mental

text: work

text: for

text: the

text: isomatrix

text: phase,

text: and

text: has

text: to

text: satisfy

text: M

text: M

text: a

text: level

text: of

text: is

text: deﬁned

text: to

text: be

text: an

text: n-tuple

text: [v

text: v

text: several

text: properties

text: described

text: in

text: Lemma

text: Section

text: A

text: of

text: M

text: n

text: whose

text: elements

text: are

text: vertices

text: of

text: where

text: n

text: is

text: called

text: the

text: supplementary

text: material.

text: Basically

text: such

text: properties

text: L

text: the

text: length

text: of

text: the

text: level.

text: We

text: denote

text: (j)

text: to

text: be

text: the

text: j-

text: guarantee

text: that

text: each

text: edge

text: of

text: the

text: mesh

text: be

text: characterized

text: L

text: th

text: element

text: of

text: a

text: level

text: and

text: we

text: call

text: j

text: to

text: be

text: the

text: index

text: either

text: by

text: pairwise

text: neighboring

text: elements

text: of

text: a

text: level

text: (such

text: L

text: L

text: L

text: of

text: v

text: in

text: if

text: v

text: (j),

text: j

text: n.

text: We

text: denote

text: (end)

text: an

text: edge

text: is

text: referred

text: to

text: as

text: an

text: intra-level

text: edge),

text: or

text: by

text: pair-

text: L

text: L

text: to

text: be

text: the

text: last

text: element

text: of

text: and

text: denote

text: (j

text: j

text: wise

text: elements

text: from

text: two

text: neighboring

text: levels

text: (such

text: an

text: edge

text: L

text: L

text: L

text: (j

text: (j

text: (j

text: if

text: j

text: j

text: otherwise,

text: we

text: de-

text: is

text: referred

text: to

text: as

text: an

text: inter-level

text: edge)

text: note

text: (j

text: j

text: We

text: denote

text: A

text: to

text: be

text: the

text: number

text: The

text: phase

text: transforms

text: of

text: all

text: elements

text: of

text: a

text: set

text: A

text: or

text: the

text: length

text: of

text: a

text: level

text: A,

text: each

text: level

text: obtained

text: in

text: previous

text: phase

text: to

text: two

text: levels,

text: one

text: |L|

text: and

text: denote

text: to

text: be

text: the

text: number

text: of

text: all

text: v’s

text: of

text: a

text: level

text: of

text: which

text: coincides

text: with

text: the

text: former

text: level

text: and

text: the

text: other

text: L

text: v

text: We

text: adopt

text: the

text: convention

text: that

text: when

text: we

text: perform

text: set

text: of

text: which

text: coincides

text: with

text: the

text: latter

text: level,

text: by

text: inserting

text: re-

text: L

text: L

text: operations

text: (e.g.

text: on

text: a

text: level

text: then

text: repre-

text: peated

text: elements

text: within

text: each

text: level.

text: This

text: work

text: guarantees

text: sents

text: the

text: collection

text: of

text: all

text: diﬀerent

text: elements

text: of

text: the

text: level

text: that

text: the

text: lengths

text: of

text: two

text: neighboring

text: levels

text: be

text: the

text: same

text: L

text: L

text: Let

text: v,

text: v

text: be

text: vertices

text: and

text: let

text: be

text: levels.

text: Then

text: v

text: and

text: the

text: end-vertices

text: of

text: each

text: inter-level

text: edge

text: appear

text: in

text: L

text: L

text: is

text: called

text: an

text: adjacent

text: element

text: of

text: v

text: in

text: if

text: v

text: v

text: correct

text: locations.

text: L

text: moreover,

text: v

text: is

text: called

text: an

text: adjacent

text: element

text: of

text: in

text: if

text: AlignAllLevels

text: Although

text: the

text: inter-level

text: edges

text: are

text: L

text: there

text: exists

text: v

text: such

text: that

text: v

text: v

text: preserved

text: in

text: pairwise

text: levels

text: and

text: the

text: intra-level

text: edges

text: are

text: L

text: L

text: M

text: Let

text: be

text: two

text: levels

text: of

text: with

text: the

text: same

text: preserved

text: in

text: neighboring

text: elements

text: of

text: each

text: level,

text: we

text: can-

text: L

text: L

text: length.

text: The

text: edge-set

text: induced

text: by

text: denoted

text: by

text: L

text: L

text: The

text: Stratify

text: phase

text: essentially

text: divides

text: all

text: faces

text: of

text: the

text: input

text: edge(

text: is

text: deﬁned

text: to

text: be

text: the

text: collection

text: of

text: pair-

text: mesh

text: into

text: several

text: triangle

text: strips

text: i.e.,

text: series

text: of

text: connected

text: wise

text: vertices

text: obtained

text: triangles

text: sharing

text: vertices.

text: To

text: see

text: this,

text: we

text: observe

text: that

text: the

text: by

text: connecting

text: each

text: pair

text: ﬁrst

text: example

text: of

text: Fig.

text: can

text: be

text: described

text: by

text: using

text: two

text: strips:

text: of

text: distinct

text: neighboring

text: elements

text: (the

text: horizontal,

text: verti-

text: dgehfi,adbecf,

text: with

text: dgehfi

text: corresponding

text: to

text: the

text: face

text: set

text: L

text: L

text: generated

text: by

text: the

text: ﬁrst

text: and

text: second

text: output

text: levels,

text: and

text: adbecf

text: cal

text: and

text: slash

text: directions)

text: of

text: i.e.

text: corresponding

text: to

text: the

text: face

text: set

text: generated

text: by

text: the

text: second

text: and

text: third

text: output

text: levels

text: (the

text: red

text: triangles

text: of

text: the

text: last

text: column).

text: Sim-

text: L

text: L

text: {L

text: L

text: L

text: L

text: edge(

text: (j)

text: (j)

text: ilarly,

text: the

text: second

text: example

text: of

text: Fig.

text: can

text: be

text: described

text: by

text: using

text: j

text: L

text: L

text: L

text: L

text: three

text: strips:

text: afdefb,adceb,acb,

text: with

text: afdefb

text: corresponding

text: to

text: (j)

text: (j),

text: (j)

text: the

text: face

text: set

text: generated

text: by

text: the

text: ﬁrst

text: and

text: second

text: output

text: levels,

text: and

text: adceb

text: corresponding

text: to

text: the

text: face

text: set

text: generated

text: by

text: the

text: sec-

text: ond

text: and

text: third

text: output

text: levels,

text: and

text: acb

text: corresponding

text: to

text: the

text: face

text: each

text: element

text: of

text: which

text: has

text: distinct

text: end-vertices,

text: with

text: set

text: generated

text: by

text: the

text: third

text: and

text: fourth

text: output

text: levels.

text: While

text: tri-

text: the

text: index

text: j

text: taking

text: all

text: available

text: values.

text: angle

text: strips

text: propose

text: an

text: eﬃcient

text: storage

text: of

text: triangular

text: meshes,

text: L

text: Let

text: j

text: n

text: be

text: a

text: level

text: sequence

text: of

text: the

text: mesh,

text: such

text: a

text: method

text: cannot

text: generate

text: an

text: image-like

text: array

text: of

text: vertices

text: j

text: and

text: hence

text: no

text: image

text: codec

text: can

text: be

text: imposed.

text: n

text: The

text: concatenate

text: operator

text: which

text: maps

text: the

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 5 (cid:2)i-1 N(A) (cid:2) [EFG] remove adjacent Q contains no A B C D concatenate N(B) (cid:2) [GHI] [EFGGHIIIJr]epeatedc ealnemdiednattse leveirlregularc poamirbsine Q E F G H I J N(C) (cid:2) [I] Q=[EFGHIJ ] with (cid:2)i-1 (cid:2)i (cid:2) [EFGHIJ ] E F G H I J N(D) (cid:2) [IJ ] N(A) (cid:2) [FG] (cid:2)i-1 remove adjacent Q contains combine Q(cid:3) A B C D E N(B) (cid:2) [G] concatenate repeated elements irregular pairs with(cid:2)i-1 A C D E G J N(C) (cid:2) [GFH] [FGGGFHHIJJLK] Qca=n[dFiGdaFteH lIeJvLeKl ] cphrooopseer G J F H I L K NN((DE)) (cid:2)(cid:2)[[JHLIKJ ]] i(r1r,e3g)u, (la5r,7p),a (i5rs,8 o)f Q: Qsu(cid:3)=bl[eGvJel] (cid:2)i (cid:2) [AGCDJE] L L Fig. 3 Two examples for showing how to determine based on − and its neighbors. i i 1 L L using − and its neighboring elements, until all ver- ity, then we repeat the same step by adding v in i 1 ∈ L \ L i+1 tices are traversed. Before going to the detailed algo- for v . i+1 i rithm of Section , we illustrate the main idea using two AlignAllLevels So far, we obtain a level sequence L L− − |L | |L− | examples of Fig. 3. When the neighboring elements of +, , i = 1, . . . , r 1 such that + = , L i i+L1− L 1 i i+1 − contain no irregular pairs (see the ﬁrst example, where , + contain the same elements with diﬀerent i 1 i i where the vertices of the component [EFGHIJ] are numbers in them. We denote v , . . . , v to be all diﬀer- L L− 1 m simply connected one by one), then is simply chosen ent elements of in turn. The purpose of this phase i i L∗ to be [EFGHIJ]; otherwise (see the second example, is to obtain another level sequence , i = 1, . . . , r ∼ L∗ i 1 where I K occurs while I, K are located in nonadja- such that all the levels have the same length, and L Li L− cent positions within [FGHIJK]), we choose to be the edge-set induced by +, equals to the edge- i L∗ L∗ i i+1 the union of a few vertices of F, G, H, I, J, K together set induced by , . We do it in this way: ﬁrst for L − i i+1 L with some vertices of − . We brieﬂy outline the three i = 2, . . . , r 1, we add repeated elements in + such i 1 |L | 1≥ |L−| i sub-phases: stratify, Align2Levels, AlignAllLevels as fol- that + , j = 1, . . . , m, and we simultane- i vj i vj L− lows, and give the detailed algorithm in the next sec- ously add repeated elements in to maintain the L L− i+1 tion. same length of +, and the same edge-set induced L L− i i+1 − − by +, ; then for i = r 1, r 2, . . . , 1, we add re- i i+1 L− 1 1 |L−| ≥ |L | Stratify The purpose of this phase is to obtain a peated elements in such that + , j = L i+L1− L i vj i vj level sequence , i = 1, . . . , r . We ﬁrst parametrize 1, . . . , m. That makes , + become exactly the same i M 1 i i L∗ an open genus-zero mesh onto the planar domain set, and consequently gives the level . Finally, we ob- × Mi L∗ [0, 1] [0, 1] by using Tutte’s parametrization [16], and tain a V-matrix VM with respect to by setting i choose all the vertices whose ordinate is one to be the as its i-th row vector 2: L initial level . For i = 2, 3, . . ., we recursively de- 1 L   termine the level in two steps: (i) obtain a candi-  L∗  i L \ ∪ − L   date level Q by ordering each N( − (j)) i 1  L1∗  i 1 L k=1 k in counterclockwise direction with respect to − (j), 2 i 1 VM := . (3) and removing repeated elements within adjacent loca- .. L∗ tions of Q; (ii) if Q contains no irregular pairs, then we obtain L by combining Q with L − (see the ﬁgure r1 i i 1 (cid:2)i-1 Q on the lLeft); otherwise, we 4.2 CGIM properties obtain by combining a (cid:2)i i M proper sublevel of Q with Let VM be a V-matrix with respect to a mesh L ∪ L i−1. The whole loop ends when ik=1 k = V holds. with m rows and n columns. We denote VM(i, j) to be the element in the i-th row, j-th column of VM, and Align2Levels The purpose of this phase is to ob- L L− − tain a|Llev|el se|qLu−en|ce +i , i+1, i = 1, . . . , r1 1 such 2 The isogim phase generates a CGIM array, by using a that: + = , and all the edge-sets induced by linear transform on the three-dimensional matrix whose el- L L− i i+1 M +, are equal to the edge-set of . We do it in ements correspond to the coordinates of vertices of the V- i i+1 ∈ L \ L ≤ matrix VM obtained in the isomatrix phase. The reconstruct this way: for each distinct element v , 1 ≤ − i i+1L phase accordingly transforms the CGIM array to a vertex-set i r 1, we check the number of its neighbors in , 1 L i+1 and an edge-set of the reconstructive mesh. Such two phases and add v in i repeatedly to maintain the connectiv- are trivial hence we omit the details. ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: N(A)

text: [EFG]

text: remove

text: adjacent

text: Q

text: contains

text: no

text: A

text: B

text: C

text: D

text: concatenate

text: N(B)

text: [GHI]

text: [EFGGHIIIJr]epeatedc

text: ealnemdiednattse

text: leveirlregularc

text: poamirbsine

text: Q

text: E

text: F

text: G

text: H

text: I

text: J

text: N(C)

text: [I]

text: Q=[EFGHIJ

text: with

text: [EFGHIJ

text: E

text: F

text: G

text: H

text: I

text: J

text: N(D)

text: [IJ

text: N(A)

text: [FG]

text: remove

text: adjacent

text: Q

text: contains

text: combine

text: A

text: B

text: C

text: D

text: E

text: N(B)

text: [G]

text: concatenate

text: repeated

text: elements

text: irregular

text: pairs

text: A

text: C

text: D

text: E

text: G

text: J

text: N(C)

text: [GFH]

text: [FGGGFHHIJJLK]

text: Qca=n[dFiGdaFteH

text: lIeJvLeKl

text: cphrooopseer

text: G

text: J

text: F

text: H

text: I

text: L

text: K

text: NN((DE))

text: o)f

text: Q:

text: [AGCDJE]

text: L

text: L

text: Fig.

text: Two

text: examples

text: for

text: showing

text: how

text: to

text: determine

text: based

text: on

text: and

text: its

text: neighbors.

text: i

text: i

text: L

text: L

text: using

text: and

text: its

text: neighboring

text: elements,

text: until

text: all

text: ver-

text: ity,

text: then

text: we

text: repeat

text: the

text: same

text: step

text: by

text: adding

text: v

text: in

text: i

text: L

text: L

text: tices

text: are

text: traversed.

text: Before

text: going

text: to

text: the

text: detailed

text: algo-

text: for

text: v

text: i

text: rithm

text: of

text: Section

text: we

text: illustrate

text: the

text: main

text: idea

text: using

text: two

text: AlignAllLevels

text: So

text: far,

text: we

text: obtain

text: a

text: level

text: sequence

text: L

text: L−

text: |L

text: |L−

text: examples

text: of

text: Fig.

text: When

text: the

text: neighboring

text: elements

text: of

text: i

text: r

text: such

text: that

text: L

text: i

text: L

text: i

text: contain

text: no

text: irregular

text: pairs

text: (see

text: the

text: ﬁrst

text: example,

text: where

text: contain

text: the

text: same

text: elements

text: with

text: diﬀerent

text: i

text: i

text: i

text: where

text: the

text: vertices

text: of

text: the

text: component

text: [EFGHIJ]

text: are

text: numbers

text: in

text: them.

text: We

text: denote

text: v

text: v

text: to

text: be

text: all

text: diﬀer-

text: L

text: L−

text: m

text: simply

text: connected

text: one

text: by

text: one),

text: then

text: is

text: simply

text: chosen

text: ent

text: elements

text: of

text: in

text: turn.

text: The

text: purpose

text: of

text: this

text: phase

text: i

text: i

text: L∗

text: to

text: be

text: [EFGHIJ];

text: otherwise

text: (see

text: the

text: second

text: example,

text: is

text: to

text: obtain

text: another

text: level

text: sequence

text: i

text: r

text: L∗

text: i

text: where

text: I

text: K

text: occurs

text: while

text: I,

text: K

text: are

text: located

text: in

text: nonadja-

text: such

text: that

text: all

text: the

text: levels

text: have

text: the

text: same

text: length,

text: and

text: L

text: Li

text: L−

text: cent

text: positions

text: within

text: [FGHIJK]),

text: we

text: choose

text: to

text: be

text: the

text: edge-set

text: induced

text: by

text: equals

text: to

text: the

text: edge-

text: i

text: L∗

text: L∗

text: i

text: the

text: union

text: of

text: a

text: few

text: vertices

text: of

text: F,

text: G,

text: H,

text: I,

text: J,

text: K

text: together

text: set

text: induced

text: by

text: We

text: do

text: it

text: in

text: this

text: way:

text: ﬁrst

text: for

text: L

text: i

text: L

text: with

text: some

text: vertices

text: of

text: We

text: brieﬂy

text: outline

text: the

text: three

text: i

text: r

text: we

text: add

text: repeated

text: elements

text: in

text: such

text: i

text: |L

text: 1≥

text: |L−|

text: i

text: sub-phases:

text: stratify,

text: AlignAllLevels

text: as

text: fol-

text: that

text: j

text: m,

text: and

text: we

text: simultane-

text: i

text: vj

text: i

text: vj

text: L−

text: lows,

text: and

text: give

text: the

text: detailed

text: algorithm

text: in

text: the

text: next

text: sec-

text: ously

text: add

text: repeated

text: elements

text: in

text: to

text: maintain

text: the

text: L

text: L−

text: tion.

text: same

text: length

text: of

text: and

text: the

text: same

text: edge-set

text: induced

text: L

text: L−

text: i

text: by

text: then

text: for

text: i

text: r

text: r

text: we

text: add

text: re-

text: i

text: L−

text: |L−|

text: |L

text: Stratify

text: The

text: purpose

text: of

text: this

text: phase

text: is

text: to

text: obtain

text: a

text: peated

text: elements

text: in

text: such

text: that

text: j

text: L

text: L

text: i

text: vj

text: i

text: vj

text: level

text: sequence

text: i

text: r

text: We

text: ﬁrst

text: parametrize

text: m.

text: That

text: makes

text: become

text: exactly

text: the

text: same

text: i

text: M

text: i

text: i

text: L∗

text: an

text: open

text: genus-zero

text: mesh

text: onto

text: the

text: planar

text: domain

text: set,

text: and

text: consequently

text: gives

text: the

text: level

text: Finally,

text: we

text: ob-

text: Mi

text: L∗

text: by

text: using

text: Tutte’s

text: parametrization

text: and

text: tain

text: a

text: V-matrix

text: VM

text: with

text: respect

text: to

text: by

text: setting

text: i

text: choose

text: all

text: the

text: vertices

text: whose

text: ordinate

text: is

text: one

text: to

text: be

text: the

text: as

text: its

text: i-th

text: row

text: vector

text: L

text: initial

text: level

text: For

text: i

text: we

text: recursively

text: de-

text: L

text: termine

text: the

text: level

text: in

text: two

text: steps:

text: (i)

text: obtain

text: a

text: candi-

text: L∗

text: i

text: L

text: L

text: date

text: level

text: Q

text: by

text: ordering

text: each

text: N(

text: (j))

text: i

text: i

text: L

text: k

text: in

text: counterclockwise

text: direction

text: with

text: respect

text: to

text: (j),

text: i

text: VM

text: and

text: removing

text: repeated

text: elements

text: within

text: adjacent

text: loca-

text: L∗

text: tions

text: of

text: Q;

text: (ii)

text: if

text: Q

text: contains

text: no

text: irregular

text: pairs,

text: then

text: we

text: obtain

text: L

text: by

text: combining

text: Q

text: with

text: L

text: (see

text: the

text: ﬁgure

text: i

text: i

text: Q

text: on

text: the

text: lLeft);

text: otherwise,

text: we

text: CGIM

text: properties

text: obtain

text: by

text: combining

text: a

text: i

text: M

text: proper

text: sublevel

text: of

text: Q

text: with

text: Let

text: VM

text: be

text: a

text: V-matrix

text: with

text: respect

text: to

text: a

text: mesh

text: L

text: L

text: The

text: whole

text: loop

text: ends

text: when

text: k

text: V

text: holds.

text: with

text: m

text: rows

text: and

text: n

text: columns.

text: We

text: denote

text: VM(i,

text: j)

text: to

text: be

text: the

text: element

text: in

text: the

text: i-th

text: row,

text: j-th

text: column

text: of

text: VM,

text: and

text: The

text: purpose

text: of

text: this

text: phase

text: is

text: to

text: ob-

text: L

text: L−

text: tain

text: a|Llev|el

text: se|qLu−en|ce

text: +i

text: i

text: such

text: The

text: isogim

text: phase

text: generates

text: a

text: CGIM

text: array,

text: by

text: using

text: a

text: that:

text: and

text: all

text: the

text: edge-sets

text: induced

text: by

text: linear

text: transform

text: on

text: the

text: three-dimensional

text: matrix

text: whose

text: el-

text: L

text: L−

text: i

text: M

text: are

text: equal

text: to

text: the

text: edge-set

text: of

text: We

text: do

text: it

text: in

text: ements

text: correspond

text: to

text: the

text: coordinates

text: of

text: vertices

text: of

text: the

text: V-

text: i

text: L

text: L

text: matrix

text: VM

text: obtained

text: in

text: the

text: isomatrix

text: phase.

text: The

text: reconstruct

text: this

text: way:

text: for

text: each

text: distinct

text: element

text: v

text: i

text: phase

text: accordingly

text: transforms

text: the

text: CGIM

text: array

text: to

text: a

text: vertex-set

text: i

text: r

text: we

text: check

text: the

text: number

text: of

text: its

text: neighbors

text: in

text: L

text: and

text: an

text: edge-set

text: of

text: the

text: reconstructive

text: mesh.

text: Such

text: two

text: phases

text: and

text: add

text: v

text: in

text: i

text: repeatedly

text: to

text: maintain

text: the

text: connectiv-

text: are

text: trivial

text: hence

text: we

text: omit

text: the

text: details.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 6 denote V row to be the level consisting of the i-th row i input mesh of VM, i = 1, . . . , m, j = 1, . . . , n. Then VM is said M to be connectivity-preserving to , if the vertex-set ∪ ∪ m n VM(i, j) induced by VM equals to the vertex- mesh parametrization i=1 jM=1 ∪ − set of , and if the edge-set m 1edge(V row; V row) i=1 M i i+1 induced by VM equals to the edge-set of . choose initial level We can check that the V-matrix in the second col- umn of both examples of Fig. 1 is connectivity-preserving to the original mesh respectively. The following prop- i  2 erty shows estimates of reconstruction errors of CGIMs. Property Let VM be a V-matrix with respect to choose candidate set M M(cid:48) and let be the reconstructed mesh generated from VM by using a b-bit CGIM. Suppose that VM is M check irregular pairs connectivity-preserving to . Then the max Hausdorﬀ distance and the root-mean-square Hausdorﬀ distance M(cid:48) M between and are both bounded by √ determine level M − M − 3(max value( ) min value( ))/(2(2b 1)) Stratify 4.3 An algorithm for the isomatrix phase whether This section gives a complete algorithm for the iso- yes no matrix phase which produces a V-matrix preserving the connectivity of the original mesh. Such a property is proved in Section A of the supplementary material. M input: an open genus-zero triangular mesh . output levels output: the row resolution r , the column resolu- L∗ 1 Align2Levels tion r , a level sequence , i = 1, . . . , r and a 2 i 1 output levels V-matrix VM. M × (1) parametrize onto the planar domain [0, 1] [0, 1] AlignAllLevels using Tutte’s parametrization [16]. output levels ← L (2) set i 2, and choose the initial level to be all and V-matrix 1 vertices whose ordinate is one over the parametrized Fig. 4 An isomatrix ﬂowchart: generating a V-matrix VM domain, such that M with respect to an open genus-zero triangular mesh . L L · · · L 0 = x( (1)) < x( (2)) < < x( (end)) = 1 1 1 1 where x(·) denotes the abscissa of a vertex in R2. (9) for each component Qcj of Q, compute thLe small- (3) for j = 1, . . . , |Li−1|, order Qj :=N(vj) \ ∪ik−=11Lk by ethste ignrdeeaxteostf iQndcj(e1x)’osf aQdcj(aecnedn)t’selaedmjaecnetnstinelemi−e1ntasnind ∠ ∠ · · · ∠ L j vj−1vjQj(1)< vj−1vjQj(2)< < vj−1vjQj(end) i−1, i.e. −−→ →− L ∠ ∈ where vj := i−1(j), v1v0 := v1, and a1a2a−3−→ − { ≤ ≤ |L | ∼ L } k = min 1 k − : Qc(1) − (k) , [0, 2π) denotes the angle fr−o−m→a planar vector a2a1 j { ≤ ≤ |Li 1 | j ∼i L1 } to another planar vector a2a3 in counterclockwise kj+ = max 1 k i−1 : Qcj(end) i−1(k) , direction. ← (cid:104) (cid:105) j = 1, . . . , m (4) set Q Q , Q , . . . , Q|L | , and remove Q(k +1) 1 2 i−1 ≤ ≤ | | − which satisﬁes Q(k) = Q(k + 1), 1 k Q 1. L (5) compute all the components Qc, . . . , Qc of Q. (10) determine the level : 1 m i (6) for each component Qc with irregular pairs, com- L ← (cid:104)L − · · · L (cid:105) j (cid:48) ≤ ≤ − (1 : k ), Qc, , Qc , − (k+ : end) pute a proper sublevel Q of Qc, 1 j m, and set i i 1 1 1 m i 1 m ← (cid:48) j Qc Q . j← (cid:104) (cid:105) (11) by using Deﬁnition 4, compute (7) Q Qc, . . . , Qc . 1 m (cid:48) (cid:48) L − (8) compute all the components Qc, . . . , Qc of Q. (P , Q ) = align1( − (k : k+), Qc), j = 1, . . . , m. 1 m j j i 1 j j j ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: denote

text: V

text: row

text: to

text: be

text: the

text: level

text: consisting

text: of

text: the

text: i-th

text: row

text: i

text: input

text: mesh

text: of

text: VM,

text: i

text: m,

text: j

text: n.

text: Then

text: VM

text: is

text: said

text: M

text: to

text: be

text: connectivity-preserving

text: to

text: if

text: the

text: vertex-set

text: m

text: n

text: VM(i,

text: j)

text: induced

text: by

text: VM

text: equals

text: to

text: the

text: vertex-

text: mesh

text: parametrization

text: set

text: of

text: and

text: if

text: the

text: edge-set

text: m

text: row;

text: V

text: row)

text: M

text: i

text: induced

text: by

text: VM

text: equals

text: to

text: the

text: edge-set

text: of

text: choose

text: initial

text: level

text: We

text: can

text: check

text: that

text: the

text: V-matrix

text: in

text: the

text: second

text: col-

text: umn

text: of

text: both

text: examples

text: of

text: Fig.

text: is

text: connectivity-preserving

text: to

text: the

text: original

text: mesh

text: respectively.

text: The

text: following

text: prop-

text: i

text: erty

text: shows

text: estimates

text: of

text: reconstruction

text: errors

text: of

text: CGIMs.

text: Property

text: Let

text: VM

text: be

text: a

text: V-matrix

text: with

text: respect

text: to

text: choose

text: candidate

text: set

text: M

text: and

text: let

text: be

text: the

text: reconstructed

text: mesh

text: generated

text: from

text: VM

text: by

text: using

text: a

text: b-bit

text: CGIM.

text: Suppose

text: that

text: VM

text: is

text: M

text: check

text: irregular

text: pairs

text: connectivity-preserving

text: to

text: Then

text: the

text: max

text: Hausdorﬀ

text: distance

text: and

text: the

text: root-mean-square

text: Hausdorﬀ

text: distance

text: M

text: between

text: and

text: are

text: both

text: bounded

text: by

text: determine

text: level

text: M

text: M

text: value(

text: min

text: value(

text: Stratify

text: An

text: algorithm

text: for

text: the

text: isomatrix

text: phase

text: whether

text: This

text: section

text: gives

text: a

text: complete

text: algorithm

text: for

text: the

text: iso-

text: yes

text: no

text: matrix

text: phase

text: which

text: produces

text: a

text: V-matrix

text: preserving

text: the

text: connectivity

text: of

text: the

text: original

text: mesh.

text: Such

text: a

text: property

text: is

text: proved

text: in

text: Section

text: A

text: of

text: the

text: supplementary

text: material.

text: M

text: input:

text: an

text: open

text: genus-zero

text: triangular

text: mesh

text: output

text: levels

text: output:

text: the

text: row

text: resolution

text: r

text: the

text: column

text: resolu-

text: L∗

text: tion

text: r

text: a

text: level

text: sequence

text: i

text: r

text: and

text: a

text: i

text: output

text: levels

text: V-matrix

text: VM.

text: M

text: parametrize

text: onto

text: the

text: planar

text: domain

text: AlignAllLevels

text: using

text: Tutte’s

text: parametrization

text: output

text: levels

text: L

text: set

text: i

text: and

text: choose

text: the

text: initial

text: level

text: to

text: be

text: all

text: and

text: V-matrix

text: vertices

text: whose

text: ordinate

text: is

text: one

text: over

text: the

text: parametrized

text: Fig.

text: An

text: isomatrix

text: ﬂowchart:

text: generating

text: a

text: V-matrix

text: VM

text: domain,

text: such

text: that

text: M

text: with

text: respect

text: to

text: an

text: open

text: genus-zero

text: triangular

text: mesh

text: L

text: L

text: L

text: x(

text: x(

text: x(

text: (end))

text: where

text: x(·)

text: denotes

text: the

text: abscissa

text: of

text: a

text: vertex

text: in

text: for

text: each

text: component

text: Qcj

text: of

text: Q,

text: compute

text: thLe

text: small-

text: for

text: j

text: order

text: Qj

text: :=N(vj)

text: by

text: ethste

text: ignrdeeaxteostf

text: L

text: j

text: i.e.

text: L

text: where

text: vj

text: and

text: |L

text: L

text: k

text: min

text: k

text: (k)

text: denotes

text: the

text: angle

text: fr−o−m→a

text: planar

text: vector

text: j

text: |Li

text: j

text: ∼i

text: to

text: another

text: planar

text: vector

text: in

text: counterclockwise

text: kj+

text: max

text: k

text: Qcj(end)

text: direction.

text: j

text: m

text: set

text: Q

text: Q

text: Q

text: Q|L

text: and

text: remove

text: Q(k

text: which

text: satisﬁes

text: Q(k)

text: Q(k

text: k

text: Q

text: L

text: compute

text: all

text: the

text: components

text: Qc,

text: Qc

text: of

text: Q.

text: determine

text: the

text: level

text: m

text: i

text: for

text: each

text: component

text: Qc

text: with

text: irregular

text: pairs,

text: com-

text: L

text: L

text: j

text: k

text: Qc,

text: Qc

text: (k+

text: end)

text: pute

text: a

text: proper

text: sublevel

text: Q

text: of

text: Qc,

text: j

text: m,

text: and

text: set

text: i

text: i

text: m

text: i

text: m

text: j

text: Qc

text: Q

text: j←

text: by

text: using

text: Deﬁnition

text: compute

text: Q

text: Qc,

text: Qc

text: m

text: L

text: compute

text: all

text: the

text: components

text: Qc,

text: Qc

text: of

text: Q.

text: (P

text: Q

text: (k

text: k+),

text: Qc),

text: j

text: m.

text: m

text: j

text: j

text: i

text: j

text: j

text: j

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: remote homology detection, Bioinformatics, 2008.

text: remote

label: reference

text: homology

text: detection,

text: Bioinformatics,


text: This establishes the fact that a = v indeed satisﬁes (t) the KKT conditions and for which γi = 1(γi = 0) if − (cid:88) (cid:88) v(cid:80)i > v(t)(vi < v(t)). mαax gt(d) As KKT conditions are necessary and suﬃcient for (cid:62) ≤ ≤ 1 m ≥ m this problem [14] we see that at optimality γ v = s.t. 0 α , α y = 0, ν α t v obtained by substituting the γ obtained be- i m i i i i=1 (i) (cid:62) i=1 i=1 fore. This completes the proof. (3.19) d = α Y K Y α j j By introducing g (d) to the dual (As in Eqn. 3.6) we t get the following CSKL formulation, The above formulation is denoted as ν-CSKL (cid:88) throughout this paper. − 4 Algorithms for solving CSKL formulations max g (d) + α ∈ t i α Sn,d i We presen−t an alternating optimization scheme for (cid:62) solving the ν CSKL formulation. For a ﬁxed γ, we d = α Y K Y α j j solve the following maximization for α, (3.16) − (cid:88) (cid:88) max γT d α Note that CSKL formulation (3.16) explicitly con- ≤ ≤ 1 m ≥ m trols the sparsity of kernel selection by varying t as is s.t. 0 α , α y = 0, ν α evident from Theorem 3.1. i m i i i i=1 i=1 (cid:62) (4.20) d = α Y K Y α j j A variant of SVM is the ν-SVM [1] where parameter (cid:80) C is replaced by a parameter ν = [0, 1]. Here, the parameter ν is lower bound on the fraction of number Note that in above problem γ should satisfy the ≤ ≤ ∀ support vector and an upper bound on the fraction of conditions n γ = t, 0 γ 1, i. We can i=1 i i margin errors. In this section we extend our CSKL use standard Sequential Minimal Optimization(SMO) ∗ formulation to ν-SVM. The dual of ν-SVM is given by, solver for the above problem. Once optimal α is ∗(cid:62) ∗ calculated, we compute d as, d = α Y K Y α . Next j j step is to solve for γ. We can ﬁnd the optimal γ by − 1 (cid:62) (cid:88) (cid:88) solving g (d) using Reduced Gradient Descent or a max α Y KY α t α 2 Linear Programming based Gradient Descent. ≤ ≤ 1 m m ≥ s.t. 0 α , α y = 0, α ν i m i i i Algorithm 1 ν-CSKL Algorithm i=1 i=1 ∀ (cid:54) ∀ Require: xT K x > 0, x = 0, j (3.17) j INPUT: N = number of kernels γ = t N objOld = 0 Introducing MKL to the dual of ν-SVM and rewrit- (cid:80) ≤ while δ (cid:15) do ing it similar to equation (3.6). Solve α using SMO solver with kernel K = N γ K j j j max − (cid:107)d(cid:107)∞ (cid:88) (cid:88) CSoolmvepugte(dd)j =us(cid:16)iαn(cid:80)TgYRKejdYucαed(cid:17) Gradient Descent or α t Linear Programming based solver ≤ ≤ 1 m m ≥ − s.t. 0 α , α y = 0, α ν obj = 1αT Y N γ K Y α i m i i i −2 j=1 j j i=1 i=1 δ = obj objOld (cid:62) (3.18) dj = α Y KjY α objOld = obj end while We now introduce our CSKL formulation in the In Algorithm 2, we present our Reduced Gradient setting of ν-SVM. Algorithm to solve γ. The SVM solver is used to obtain ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: This

text: establishes

text: the

text: fact

text: that

text: a

text: v

text: indeed

text: satisﬁes

text: (t)

text: the

text: KKT

text: conditions

text: and

text: for

text: which

text: γi

text: if

label: equation

text: v(t)(vi

text: v(t)).

text: mαax

text: gt(d)

text: As

text: KKT

text: conditions

text: are

text: necessary

text: and

text: suﬃcient

text: for

text: m

text: m

text: this

text: problem

text: we

text: see

text: that

text: at

text: optimality

text: γ

text: v

text: s.t.

text: α

text: α

text: y

text: ν

text: α

text: t

text: v

text: obtained

text: by

text: substituting

text: the

text: γ

text: obtained

text: be-

text: i

text: m

text: i

text: i

text: i

text: (i)

text: fore.

text: This

text: completes

text: the

text: proof.

text: d

text: α

text: Y

text: K

text: Y

text: α

text: j

text: j

text: By

text: introducing

text: g

text: (d)

text: to

text: the

text: dual

text: (As

text: in

text: Eqn.

text: we

text: t

text: get

text: the

text: following

text: CSKL

text: formulation,

text: The

text: above

text: formulation

text: is

text: denoted

text: as

text: ν-CSKL

text: throughout

text: this

text: paper.

text: Algorithms

text: for

text: solving

text: CSKL

text: formulations

text: max

text: g

text: (d)

text: α

text: t

text: i

text: α

text: Sn,d

text: i

text: We

text: presen−t

text: an

text: alternating

text: optimization

text: scheme

text: for

text: solving

text: the

text: ν

text: CSKL

text: formulation.

text: For

text: a

text: ﬁxed

text: γ,

text: we

text: d

text: α

text: Y

text: K

text: Y

text: α

text: j

text: j

text: solve

text: the

text: following

text: maximization

text: for

text: α,

text: max

text: γT

text: d

text: α

text: Note

text: that

text: CSKL

text: formulation

text: explicitly

text: con-

text: m

text: m

text: trols

text: the

text: sparsity

text: of

text: kernel

text: selection

text: by

text: varying

text: t

text: as

text: is

text: s.t.

text: α

text: α

text: y

text: ν

text: α

text: evident

text: from

text: Theorem

text: i

text: m

text: i

text: i

text: i

text: d

text: α

text: Y

text: K

text: Y

text: α

text: j

text: j

text: A

text: variant

text: of

text: SVM

text: is

text: the

text: ν-SVM

text: where

text: parameter

text: C

text: is

text: replaced

text: by

text: a

text: parameter

text: ν

text: Here,

text: the

text: parameter

text: ν

text: is

text: lower

text: bound

text: on

text: the

text: fraction

text: of

text: number

text: Note

text: that

text: in

text: above

text: problem

text: γ

text: should

text: satisfy

text: the

text: support

text: vector

text: and

text: an

text: upper

text: bound

text: on

text: the

text: fraction

text: of

text: conditions

text: n

text: γ

text: t,

text: γ

text: i.

text: We

text: can

text: i

text: i

text: margin

text: errors.

text: In

text: this

text: section

text: we

text: extend

text: our

text: CSKL

text: use

text: standard

text: Sequential

text: Minimal

text: Optimization(SMO)

text: formulation

text: to

text: ν-SVM.

text: The

text: dual

text: of

text: ν-SVM

text: is

text: given

text: by,

text: solver

text: for

text: the

text: above

text: problem.

text: Once

text: optimal

text: α

text: is

text: calculated,

text: we

text: compute

text: d

text: as,

text: d

text: α

text: Y

text: K

text: Y

text: α

text: Next

text: j

text: j

text: step

text: is

text: to

text: solve

text: for

text: γ.

text: We

text: can

text: ﬁnd

text: the

text: optimal

text: γ

text: by

text: solving

text: g

text: (d)

text: using

text: Reduced

text: Gradient

text: Descent

text: or

text: a

text: max

text: α

text: Y

text: KY

text: α

text: t

text: α

text: Linear

text: Programming

text: based

text: Gradient

text: Descent.

text: m

text: m

text: s.t.

text: α

text: α

text: y

text: α

text: ν

text: i

text: m

text: i

text: i

text: i

text: Algorithm

text: ν-CSKL

text: Algorithm

text: Require:

text: xT

text: K

text: x

text: x

text: j

text: j

text: INPUT:

text: N

text: number

text: of

text: kernels

text: γ

text: t

text: N

text: objOld

text: Introducing

text: MKL

text: to

text: the

text: dual

text: of

text: ν-SVM

text: and

text: rewrit-

text: while

text: δ

text: do

text: ing

text: it

text: similar

text: to

text: equation

text: Solve

text: α

text: using

text: SMO

text: solver

text: with

text: kernel

text: K

text: N

text: γ

text: K

text: j

text: j

text: j

text: max

text: CSoolmvepugte(dd)j

text: Gradient

text: Descent

text: or

text: α

text: t

text: Linear

text: Programming

text: based

text: solver

text: m

text: m

text: s.t.

text: α

text: α

text: y

text: α

text: ν

text: obj

text: Y

text: N

text: γ

text: K

text: Y

text: α

text: i

text: m

text: i

text: i

text: i

text: −2

text: j

text: j

text: δ

text: obj

text: objOld

text: dj

text: α

text: Y

text: KjY

text: α

text: objOld

text: obj

text: end

text: while

text: We

text: now

text: introduce

text: our

text: CSKL

text: formulation

text: in

text: the

text: In

text: Algorithm

text: we

text: present

text: our

text: Reduced

text: Gradient

text: setting

text: of

text: ν-SVM.

text: Algorithm

text: to

text: solve

text: γ.

text: The

text: SVM

text: solver

text: is

text: used

text: to

text: obtain

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Algorithm 2 Reduc(cid:16)ed(cid:80)Gradient (cid:17)Algorithm for Solving Algorithm 3 Calculating the Descent Direction g (d) t INPUT: Kernel Weights γ, Selected Pivot µ, Calcu- J(α, γ) = −1αT Y N γ K Y α lated Gradients φ 2 j=1 −j j OUTPUT: Optimal Descent Direction D(γ, µ, φ) Set µ = argmin (abs (γ 0.5)) − m m for m = 1 to N do Set J = J 1, γ = γ new new D = 0 Compute φ = δJ for m = 1, . . . , N m − m δγm if (γm == 0 & φm φµ > 0) then Compute the descend direction D(d, µ, φ) D = 0 m − Set Dnew = D else if (γm == 1 & φm φµ < 0) then while Jnew < J do Dm = 0 γ = γnew else if (γ−(cid:80)m > 0− & m! = µ) then D = Dnew − Dm = φm φµ ν1 = (amr|Dgmm<in0(cid:16)) − Dγmm (cid:17) elsDe if=(m == µ) the(φn − φ ) ν2 = (amr|Dgmm>in(cid:16)0)−1Dγmm − (cid:17) enednfdomrif ν!=µ,γν>0 ν µ S = min γν1 , 1 γν2 max Dν1 Dν2 − − ν = argmin γν1 , 1 γν2 ν1,ν2 Dν1 Dν2 − 5 Experiments. γ = γ + S D, D (µ) = D D new max new µ ν To illustrate the beneﬁts of CSKL formulation, we D (ν) = 0 new give results on Synthetic data and the Caltech101 [19] Compute J (α, γ ) new new real-world Object Categorization dataset. We compare end while ∈ CSKL algorithm with SimpleMKL [Equation 2.1] 1 which Linesearch along D for S [0, S ] γ ← γ + SD max is a sparse selection algorithm, and Lp MKL [Equation 2.2] with p = 2 which is a non-sparse selection algorithm 2. In this section, we describe the datasets we used for our experiments. J (see Algorithm 2). The Descent Direction D is deﬁned as per Algorithm 3. In the case of ν-CSKL, the value − of J (α, γ) = γT d while in the case of C-CSKL it is To show the eﬀect of noisy kernels, we generated − γT d + αT e while the rest of the framework remains n = 18 kernels out of which 16 are informative ker- nels and 2 are noisy kernels. To build these kernels, we the same. sampled m = 500 datapoints with dimension d = 3 from Due to our assumptions on K, in both the cases, two independent Gaussian distributions with covariance J is convex and diﬀerentiable with Lipschitz gradient as the identity matrix and diﬀerent means(µ = 0 and wrt. γ [17]. For such functions the Reduced Gradient 1 µ = 3, Datapoints sampled from diﬀerent Gaussians Method converges with bounds as deﬁned in [18]. 2 are assumed to belong to diﬀerent classes). We gener- We also present a linear programming based ap- ated four kernels (two gaussian(σ = and σ =) and two proach to solve for g (d). We use some standard LP t polynomial kernels(σ = and σ =)) for each dimension Solver to solve the following linear program for ﬁnding ∗ seprately and all together(4 3 + 4 = 16). On top of descent direction D for g (d). t this, we also added two carefully chosen noisy kernels to this kernel set. min φT D D − ≥ ≥ − The Caltech101 dataset has 102 categories of images (4.21) DT 1 = 0, γ D 1 γ such as airplanes, cars, leopards, etc. It has been shown by [10, 13, 12] that multiple image descriptors aid in the generalization ability of the learnt classiﬁer. Using where φ = ∂J and step size (S) can be found m ∂γm by using line search. γ is updates as γ = γ + SD. new 1Implementation downloaded from http://asi.insa- Though this algorithm is found to converge for K > 0 rouen.fr/enseignants/ arakotom/code/mklindex.html we have no bounds on its convergence as yet. 2Implementation available in the Shogun toolbox : http://www.shogun-toolbox.org/ ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Algorithm

text: for

text: Solving

text: Algorithm

text: Calculating

text: the

text: Descent

text: Direction

text: g

text: (d)

text: t

text: INPUT:

text: Kernel

text: Weights

text: γ,

text: Selected

text: Pivot

text: µ,

text: Calcu-

text: J(α,

text: γ)

text: −1αT

text: Y

text: N

text: γ

text: K

text: Y

text: α

text: lated

text: Gradients

text: φ

text: −j

text: j

text: OUTPUT:

text: Optimal

text: Descent

text: Direction

text: D(γ,

text: µ,

text: φ)

text: Set

text: µ

text: argmin

text: (abs

text: (γ

text: m

text: m

text: for

text: m

text: to

text: N

text: do

text: Set

text: J

text: J

text: γ

text: γ

text: new

text: new

text: D

text: Compute

text: φ

text: δJ

text: for

text: m

text: N

text: m

text: m

text: δγm

text: if

text: (γm

text: φm

text: φµ

text: then

text: Compute

text: the

text: descend

text: direction

text: D(d,

text: µ,

text: φ)

text: D

text: m

text: Set

text: Dnew

text: D

text: else

text: if

text: (γm

text: φm

text: φµ

text: then

text: while

text: Jnew

text: J

text: do

text: Dm

text: γ

text: γnew

text: else

text: if

text: 0−

text: m!

text: µ)

text: then

text: D

text: Dnew

text: Dm

text: φm

text: φµ

text: ν1

text: Dγmm

text: elsDe

text: if=(m

text: µ)

text: the(φn

text: φ

text: ν2

text: enednfdomrif

text: ν

text: µ

text: S

text: min

text: γν1

text: γν2

text: max

text: ν

text: argmin

text: γν1

text: γν2

text: Experiments.

text: γ

text: γ

text: S

text: D,

text: D

text: (µ)

text: D

text: D

text: new

text: max

text: new

text: µ

text: ν

text: To

text: illustrate

text: the

text: beneﬁts

text: of

text: CSKL

text: formulation,

text: we

text: D

text: (ν)

text: new

text: give

text: results

text: on

text: Synthetic

text: data

text: and

text: the

text: Compute

text: J

text: (α,

text: γ

text: new

text: new

text: real-world

text: Object

text: Categorization

text: dataset.

text: We

text: compare

text: end

text: while

text: CSKL

text: algorithm

text: with

text: SimpleMKL

text: [Equation

text: which

text: Linesearch

text: along

text: D

text: for

text: S

text: S

text: γ

text: γ

text: SD

text: max

text: is

text: a

text: sparse

text: selection

text: algorithm,

text: and

text: Lp

text: MKL

text: [Equation

text: with

text: p

text: which

text: is

text: a

text: non-sparse

text: selection

text: algorithm

text: In

text: this

text: section,

text: we

text: describe

text: the

text: datasets

text: we

text: used

text: for

text: our

text: experiments.

text: J

text: (see

text: Algorithm

text: The

text: Descent

text: Direction

text: D

text: is

text: deﬁned

text: as

text: per

text: Algorithm

text: In

text: the

text: case

text: of

text: ν-CSKL,

text: the

text: value

text: of

text: J

text: (α,

text: γ)

text: γT

text: d

text: while

text: in

text: the

text: case

text: of

text: C-CSKL

text: it

text: is

text: To

text: show

text: the

text: eﬀect

text: of

text: noisy

text: kernels,

text: we

text: generated

text: γT

text: d

text: αT

text: e

text: while

text: the

text: rest

text: of

text: the

text: framework

text: remains

text: n

text: kernels

text: out

text: of

text: which

text: are

text: informative

text: ker-

text: nels

text: and

text: are

text: noisy

text: kernels.

text: To

text: build

text: these

text: kernels,

text: we

text: the

text: same.

text: sampled

text: m

text: datapoints

text: with

text: dimension

text: d

text: from

text: Due

text: to

text: our

text: assumptions

text: on

text: K,

text: in

text: both

text: the

text: cases,

text: two

text: independent

text: Gaussian

text: distributions

text: with

text: covariance

text: J

text: is

text: convex

text: and

text: diﬀerentiable

text: with

text: Lipschitz

text: gradient

text: as

text: the

text: identity

text: matrix

text: and

text: diﬀerent

text: means(µ

text: and

text: wrt.

text: γ

text: For

text: such

text: functions

text: the

text: Reduced

text: Gradient

text: µ

text: Datapoints

text: sampled

text: from

text: diﬀerent

text: Gaussians

text: Method

text: converges

text: with

text: bounds

text: as

text: deﬁned

text: in

text: are

text: assumed

text: to

text: belong

text: to

text: diﬀerent

text: classes).

text: We

text: gener-

text: We

text: also

text: present

text: a

text: linear

text: programming

text: based

text: ap-

text: ated

text: four

text: kernels

text: (two

text: gaussian(σ

text: and

text: σ

text: and

text: two

text: proach

text: to

text: solve

text: for

text: g

text: (d).

text: We

text: use

text: some

text: standard

text: LP

text: t

text: polynomial

text: kernels(σ

text: and

text: σ

text: for

text: each

text: dimension

text: Solver

text: to

text: solve

text: the

text: following

text: linear

text: program

text: for

text: ﬁnding

text: seprately

text: and

text: all

text: On

text: top

text: of

text: descent

text: direction

text: D

text: for

text: g

text: (d).

text: t

text: this,

text: we

text: also

text: added

text: two

text: carefully

text: chosen

text: noisy

text: kernels

text: to

text: this

text: kernel

text: set.

text: min

text: φT

text: D

text: D

text: The

text: dataset

text: has

text: categories

text: of

text: images

text: DT

text: γ

text: D

text: γ

text: such

text: as

text: airplanes,

text: cars,

text: leopards,

text: etc.

text: It

text: has

text: been

text: shown

text: by

text: that

text: multiple

text: image

text: descriptors

text: aid

text: in

text: the

text: generalization

text: ability

text: of

text: the

text: learnt

text: classiﬁer.

text: Using

text: where

text: φ

text: ∂J

text: and

text: step

text: size

text: (S)

text: can

text: be

text: found

text: m

text: ∂γm

text: by

text: using

text: line

text: search.

text: γ

text: is

text: updates

text: as

text: γ

text: γ

text: SD.

text: new

text: downloaded

text: from

text: Though

text: this

text: algorithm

text: is

text: found

text: to

text: converge

text: for

text: K

text: rouen.fr/enseignants/

text: we

text: have

text: no

text: bounds

text: on

text: its

text: convergence

text: as

text: yet.

text: available

text: in

text: the

text: Shogun

text: toolbox

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##