Theo Thonat

Abdelaziz Djelouah

Fredo Durand

George Drettakis

Thin Structures in Image Based Rendering

Input Images multi-view segmentation background images Thin Structures are common Ours Soft3D [Penner 2017] [Ortiz-Cayon 2015

viewpoints as well as a traditional 3D reconstruction from off-theshelf structure-from-motion (SfM) and multi-view stereo (MVS) methods. The 3D reconstruction is usually incorrect for the thin structure; our goal is to segment it out on the correct 3D supporting geometry to improve image based rendering. Multiple factors make this problem hard. The structures are very thin and often lack texture; as a result standard descriptors are ineffective and regularization is difficult. Also, the see-through nature of these objects makes multi-view inference challenging.

Our problem is related to de-fencing methods (e.g., [PBCL10]) but their objective is often limited to removing occluding fences, in which case segmentation can be conservative and less precise. The foreground layer can be more precisely estimated [START_REF] Xue | A computational approach for obstruction-free photography[END_REF], but this requires the small baseline of video sequences.

The key intuition in our work is that we can use multi-view information and the partial 3D reconstruction to estimate segmentation of thin structures in multiple input views. In addition to the images and reconstruction we use as input, a short user interaction is needed to define the supporting geometry and region of interest. The first part of our algorithm is a Markov Random Field (MRF)based multi-view segmentation, which can handle multiple layers of thin structures. We combine appearance cues from color models, median colors and variance, with multi-view consistency constraints on segmentation results. The second part of our solution is an IBR algorithm that allows free-viewpoint rendering of multilayer thin structures. For a given fragment, our renderer interprets alpha values as probabilities to be on a thin structure. These are used to blend weighted colors from the different views.

Our contributions can be summarized as follows:

• A multi-view segmentation algorithm for thin structures supported by simple geometries, that uses multi-view links and color variance to resolve hard ambiguous cases. • An end-to-end solution to IBR for such multi-layer thin structures, including preprocessing to ensure accurate segmentation, and post-processing to generate a clean background. • A new IBR algorithm that allows free-viewpoint navigation of scenes containing these structures.

Our results show significant improvement over previous work, in terms of the identification of the thin structures, the resulting segmentation, and most importantly in the quality of the final imagebased rendering in free-viewpoint navigation.

Related Work

Our work is related to image de-fencing, repetitive structure detection and multi-view segmentation. We also briefly discuss aspects of 3D reconstruction and Image-Based Rendering research related to our work. [LNS * 15] avoid using interest points and apply the Generalized PatchMath algorithm in combination with Particle Belief Propagation to infer the lattice structure. In the case of facades, vanishing lines [WFP10] can be used for plane detection and rectification. In this case dense descriptors are matched not only using repetition but also symmetry. In a multi-view setting, it is possible to detect repetitive elements on more complex surfaces [JTC11] using reconstructed 3D geometry and the images. This however cannot be applied to thin structures in our scenes as there is often no reliable 3D reconstruction.

The problem of image de-fencing consists in removing fences from pictures or videos. Liu et al. [LBHL08] were the first to propose an automatic method to detect and segment fences in images. Texture based inpainting [CPT04] is used to fill the extracted regions. Fences are found by searching for a lattice that explains the relationship between repeated elements in the image [START_REF] Hays | Discovering texture regularity as a higher-order correspondence problem[END_REF]. This method is further improved [PBCL10] using a multi-view approach for inpainting and a different lattice detection algorithm [PBCL09]. In the case of videos, optical flow is the main cue used to identify fences. A first method is proposed by Mu et al. [MLY12] based on motion parallax. Recently, a robust method for obstruction free photography [START_REF] Xue | A computational approach for obstruction-free photography[END_REF] was proposed to handle occlusion from both fences and windows, generating an alpha matted thin structure layer. Yi et al [YWT16] also rely on motion in their fence/non fence segmentation. Finally, Yamashita et al. [START_REF] Yamashita | Fence removal from multi-focus images[END_REF] use multi-focus flash/non flash images to identify regions corresponding to objects closer to the camera. Most of these methods assume that the fence is closer to the camera than our typical input. In video-based methods, optical flow estimation is central, and often fails on the wide-baseline input data we have. We show several comparisons to previous methods in Sec. 7.2 and in supplemental material which demonstrate that these methods are not adapted to our goals.

Multi-View Segmentation

Our work is also related to multi-view segmentation methods that try to identify the foreground object visible in different viewpoints. Some of these methods rely on consistency of the projection of 3D points [KBC12, DFB * 13] which is unreliable with thin structures. Other segmentation approaches use constraints from stereo [START_REF] Kowdle | Multiple view object cosegmentation using appearance and stereo cues[END_REF] or matching along epipolar lines [CVHC11]. Both strategies are not designed to handle ambiguities due to the often repetitive pattern. In [WFZ02], Wexler et al. estimate two layers from multiple images using a Bayesian framework. Contrary to our work, they assume foreground and background transformations are modeled by planar projections. The resulting Maximuma-Posteriori estimation requires the definition of a reference view which is not trivial when considering more complex camera setups. Our approach is able to handle complex 3D geometries and multiple layers. Thanks to our multi-view constraints, segmentation is estimated in the original input images for best rendering results. We then perform (c) multi-view, multi-layer segmentation followed by (d) post-processing to create "clean" background images and geometry. The result can be used by our multi-layer rendering algorithm (e), allowing free-viewpoint navigation.

Multi-View Stereo Reconstruction and IBR

Thin structures are also an important limitation for multi-view stereo (MVS) reconstruction methods [GSC * 07, FP10, JP11]. Ummenhofer and Brox [UB13] propose a method to reconstruct thin objects which have almost no volume compared to the surface size. Because of the errors in the 3D reconstruction and the normals, the object is not reconstructed (e.g., a sign observed from opposing viewpoints). In a different setup, Oswald et al. [START_REF] Oswald | Generalized connectivity constraints for spatio-temporal 3d reconstruction[END_REF] enforce connectivity constraints and surface genus in temporal 3D reconstruction. In their paper on scene abstraction, Hofer et al.

[HMB16] use 3D lines to represent 3D scenes. There also has been work specific to the reconstruction of wire structures from images [LCL * 17, MMBP14, CH04]; these methods have strong assumptions about the simplicity and/or tubular structure of the objects being reconstructed, and thus do not apply to our context. In general, the hypotheses on input in all of these methods are very different from ours, making them inappropriate for our data. can be used with image data based on an ordering algorithm to allow correct alpha blending; in contrast we interpret alpha values as probabilities to allow specific visibility processing for our multi-layer semi-transparent thin geometries. In recent work the Soft3D algorithm [PZ17] uses a volumetric depth-sweep approach for IBR with a set of clever filtering steps, based on guided filtering and soft visibility, with excellent results. The volumetric nature of this approach means that very fine resolution at unaccept-able storage/computation cost would be needed to represent the thin structures we treat. Our rendering algorithm shares some ideas with the soft visibility approach of Soft3D which we discuss in more detail when presenting our method. The central difference is that we work with surface-based 3D (MVS reconstruction and thin supporting geometries) rather than volumes, which allows better visual quality for free-viewpoint navigation far from the input cameras.

Initial

Overview

Our pipeline is shown in Fig. 2. We start with a set of photographs of the scene together with a 3D reconstruction, estimated using multi-view stereo (e.g., [START_REF] Jancosek | Multi-view reconstruction preserving weakly-supported surfaces[END_REF]Rea16]): We call this the proxy geometry and we assume that it completely covers the background of the scene. The 3D model usually represents the thin structure poorly and we provide a user interface to specify the supporting 3D geometry of the thin structure. The user manually specifies 3D points in images, by clicking in 2 images per point. For a plane, 3-4 points are needed and for a cylindrical segment, the user specifies 4-5 points for each of the "upper" and "lower" circles defining the cylindrical segment. The output is a collection of meshes that roughly cover the thin structures (illustrated in Fig. 2.a). This user interaction takes no more than a few minutes for all our examples (please see video).

Our goal is to segment pixels belonging to the thin structure in all the input views (Fig. 2. c). There can be multiple overlapping layers of see-through thin structures. As a result, in addition to separating the thin structures from the background, we also need to segment the thin structures into a distinct set of layers. This makes traditional appearance terms less reliable. Moreover, the segmentation of such structures is hard because the regions are not compact and challenge the balance between area and contour terms in traditional segmentation. Our key observation is that we can leverage the multiple input views to resolve ambiguity present in a given view. Consider Fig. 3: the structures on the left are very hard to extract as they have colors very similar to the door behind. However, the same structures in the right image have high contrast and can be extracted easily.

Our segmentation algorithm relies on color models and multiview constraints: for occluded layers, we use median colors [WFZ02] to leverage the multiple views and obtain a color model that is more robust to occlusions. However, for the frontmost layer, any inconsistency in colors between the different views is likely to indicate incorrect segmentation and using color variance across viewpoints is more effective. In addition to this, we use multi-view links to help resolve ambiguous cases for segmentation. The segmentation operates layer by layer, from front to back; we will refer to "foreground" as the current front-most thin structure and "background" as the layers behind together with the non-thin parts of the scene. Because we leverage the discrepancy between reprojections to background and foreground layers, we assume that the thin structure has not been reconstructed in the 3D proxy. To ensure this, we remove geometry in the close neighborhood of the supporting geometry during a preprocess step.

After multi-view segmentation, we refine the segmentation using off-the-shelf alpha matting [HRR * 11], whereas the background regions occluded by the thin structures are filled using the median images and inpainting. The resulting images are then used to create a "thin-structure-free" 3D reconstruction of the background. These correspond to the post-processing in Fig. 2(d). Details for pre-and post-processing are provided in Sec. 5.

We introduce a new rendering algorithm that handles multi-view alpha mattes, by interpreting alpha values as conditional probabilities that a fragment contains a thin structure. We estimate the overall alpha value using Bayes rule. Rendering involves a depthpeeling algorithm on the supporting geometries of the thin structures, rendered after a first ULR pass of the clean background (Fig. 2. e). Our results on scenes with thin structures show significantly better quality than previous methods, especially for the free-viewpoint navigation far from the input cameras.

Multi-view Segmentation

To resolve the difficult multi-layer segmentation problem, we use multi-view color and geometry information.

V₁ V₂

proxy Layer k Layer k + 1 p ₁ p' 1 p 2 p' 2
Figure 4: Multi-view links at iteration k. We create multi-view links by connecting two pixels which correspond to the same 3D point on the layer k (p 1 linked to p 2 and p 1 linked to p 2 ). When the 3D point really corresponds to a thin structure (p 1 ↔ p 2 ), we have linked together two pixels from the layer k. When the 3D point is in-between the thin structure (p 1 ↔ p 2 ), we do not know which layer corresponds to which pixel: p 1 is in layer k + 1, while p 2 is on the proxy but we can infer that the two pixels are on layers > k.

Multi-Layer Segmentation

Our approach handles multiple layers of thin structures, e.g, the corner of the staircase in Fig. 2. For each pixel p in each input image, we create a sorted list of N p front-to-back depth candidates d k by ray-casting the proxy and the thin structure supporting geometries. The last depth candidate d Np per pixel is always the proxy depth because we assume that the proxy is opaque, so we stop raycasting as soon as it is hit.

We denote by P the set of all pixels p for which N p ≥ 2. It corresponds to all pixels that need to be segmented because they have at least one depth candidate in addition to the proxy depth. Solving the general multi-layer segmentation problem is equivalent to assigning the correct depth to each pixel, which we model as finding a labelling that will minimize an energy function defined by multi-view information on color and geometry.

To solve the multi-label problem, we decompose it into a sequence of binary label problems, in an alpha-expansion-like fashion [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF], considering depth labels from front-to-back. For each iteration k, we select all the pixels with current segmentation ≥ k, and we want to find out how much we can expand the depth layer k. The two labels for the sub binary problems are "depth layer is k" and "depth layer is > k", i.e., "foreground" and "background" respectively.

To see the justification for this decomposition, consider Fig. 4: labels of pixels associated through the current depth layer k are linked. They are either both at the correct depth layer k, which is the case for pixels p 1 and p 2 , or both at a depth layer > k in the case of pixels p 1 and p 2 . In this case, it is not possible to associate a specific layer > k to the pixels p 1 and p 2 (see Fig. 4).

Input

Median color Median score Variance Score

k = kcurrent k = kcurrent + 1 k = kcurrent + 2
Figure 5: Advantage of using median or variance information for each depth layer for a given current depth layer. Warm colors in the score columns indicate high likelihood for this layer to give the correct depth. For the current layer, the variances give cleaner information.

For the layers beyond, the medians remove outliers while the variance score, more sensitive to occlusions, is low on the wall. For each layer, the most informative score is outlined in green.

We denote K the geometry corresponding the depth layer k. We use the term background geometry to refer to the geometry corresponding to all depth layers > k, i.e., thin structures behind the current layer or proxy of the scene. We iteratively solve these binary problems for k = 1 to k = max p∈P Np -1.

General Formulation

We can now express the segmentation as a binary labeling problem for each pixel, minimizing an MRF energy function. We start with standard color and smoothness terms, and use two terms that exploit multi-view cues. The first provides a multi-view color prediction of a foreground vs. background pixel given the reprojections from other views, while the second term links the label of pixels from different viewpoints if they correspond to the same point on the foreground layer K.

We next describe the graphcut segmentation terms before introducing our new terms in more detail.

Color Model. We compute prior probabilities for each pixel for being in the thin structure or in the proxy: P color thin and P color proxy respectively. These are estimated from global per view appearance models. In our case, we use histograms. We cluster all the colors in all input images and for a color c, we note C(c) its associated cluster, where this cluster defines the corresponding bin in the histogram. We note P I thin the set of pixels of image I currently segmented as one of the thin structures and P I proxy the set of all input pixels not in P I thin . Probabilities for a pixel p from image I with color cp are then defined as:

P color thin (p) = #{q ∈ P I thin ,C(cq) = C(cp)} #{q ∈ P I thin } P color proxy (p) = #{q ∈ P I proxy ,C(cq) = C(cp)} #{q ∈ P I proxy }, (1)
where # is set cardinality. Finally, the probabilities P color k to be part of the layer k based on the color models are given by:

P color k (p) = P color proxy (p) if k = Np, P color thin (p) otherwise.
(2)

Smoothness term. We use a standard pairwise contrast sensitive energy term, with a 4-neighbor connectivity. Specifically:

E N (p, q) = 1 1+||cp-cq|| if lp = lq, 0 otherwise.
(

) 3
with ||cp -cq|| the L 2 norm of the color difference.

Multi-View Color Term

We leverage multi-view information to determine the probability of being foreground or background by reprojection, in the spirit of multi-view stereo [SCD * 06]. Standard reprojection error approaches are not sufficiently robust in our challenging context, in particular because of occlusion. Instead we compare observed pixels to the median of the reprojections from multiple views [WFZ02] and introduce variance to allow more robust results.

Input Initialization Without color term Without MV links Full method

Figure 6: Advantage of using a multi-view approach for segmentation. The MV links allow us not only to retrieve missing segmentation because of a similar background but also to remove wrong segmentation because of possibly misleading unary terms.

For a 3D point in the current depth layer kcurrent, since we have an approximate segmentation of the previous depth layers, we can compute a reliable visibility information from input views. So with the hypothesis of low specularity, a high color variance in the reprojections of the 3D point into the input views is a strong cue of an incorrect depth. On the other hand, for a 3D point in a depth layer k > kcurrent, we do not have reliable visibility information, so even with a correct depth, a high color variance could simply be a consequence of occlusions. However, if we make the assumption that since the foregrounds are thin, a background point will not be occluded in the majority of the views, we can use the median color across views to remove occlusion outliers.

For a given view, we use the 3D information from layer k to project into the other views and collect color samples. The variance map σ I defines the variances of these samples for each pixel p. The median image M is obtained by sorting the samples by luminance, and keeping the median color value for each pixel.

The likelihood for a pixel p to be part of depth layer k is

L k (p) = G(σ I (p), 0, σ ref ) if k = kcurrent, G(I(p), M k (p), I ref ) if k > kcurrent. (4)
with G indicating a Gaussian distribution. In the case of the current depth layer kcurrent, a small variance in the color samples is likely to indicate correct depth assignment. In the case of other depth layers k > kcurrent, using the median color map M k is more robust to the occasional occlusions. We show examples of the median images in Fig. 5. In the case of the front-most layer (k = kcurrent), using the variance map gives more precise results whereas the median colors are more effective on layers further away (k > kcurrent).

Moreover, since the layers occlude each other, we introduce a prior weight λ k to take in account that the segmentation of layer k becomes more likely as it approaches the front (excluding the proxy which is prominent). Given that the layer k = Np corresponds to the proxy, we model this by a Bernoulli trial of parameter 0.6 such that λproxy

= λ Np > λ 1 > λ 2 > • • • > λ Np-1 .
Therefore the probabilities P mv k to be part of the layer k (k ≥ kcurrent), based on the multi-view information are given by:

P mv k (p) = λ k • L k (p) ∑ k ≥kcurrent λ k • L k (p) (5)

Multi-View Links

We introduce multi-view links to enforce consistency between views, transferring more reliable segmentations to views with harder configurations. We reproject each pixel into neighboring images with depth K and we create a link for each projection if its current segmentation is ≥ k. We do this since if the reprojection falls on a pixel with current segmentation < k, we do not want to change this decision; see illustration in Fig. 4, To limit issues due to coordinate rounding, links are created only if the backprojection in the opposite direction is on the same pixel.

E L (p, q) is the energy term corresponding to these multi-view links. It is created between all pairs of views (i, j), linking a pixel p from i with a pixel q from j through reprojection:

E L (p, q) = λ if lp = lq, 0 otherwise. ( 6
)
These links allow the propagation of segmentation results from views where color models are more discriminatory to images where the difference between foreground and background appearance is ambiguous. In all our results, λ = 1.0.

Unary Energy Terms

The probabilities described above give information about a layer k. The unary cost associated to a layer k is given by :

U k (p) = -log λ color • P color k (p) + λmv • P mv k (p) (7)
Terms λ color and λmv are mixing coefficients between the global and the multi-view appearance models, where λmv = 0.4 and λ color = 1λmv. We now need to compute the unary terms with respect to the labels "foreground" and "background". For the foreground label "k" the unary term is simply the unary cost associated to that depth layer. For the background label "> k" the unary term is the minimum of all the unary costs associated to the depth layers k + 1, k + 2, • • • . We take the minimum to be as conservative as possible when assigning the label k, because if k is chosen, the pixel will not appear in the following binary segmentation problems as we solve front-to-back. Therefore the unary energy term is given by:

E U (p) = U k (p) if lp = "foreground", min k >k U k (p) if lp = "background". ( 8
)
4.6. Final Energy Formulation E N (p, q) and E L (p, q) are pairwise terms used to enforce coherent segmentation respectively at image and multi-view level.

If we note by N all the pairs of neighboring pixels, and by L all the multi-view links, the final energy optimized by the MRF is as follows:

E = ∑ p∈P E U (p) + ∑ (p,q)∈N E N (p, q) + ∑ (p,q)∈L E L (p, q) (9)
In Fig. 6 we illustrate the effect of the unary terms and the multiview consistency term E L (p, q). Using only classic color models for foreground and background is sensitive to any similarity of appearance between these two parts. Adding the multi-view color term helps to take into account the other viewpoints and we clearly see that some regions that were erroneously part of the foreground model, are now less likely to be coherent in multi-view. We also see why multi-view links allow the propagation of good segmentation results across viewpoints.

Pre-and Post-Processing

Achieving high quality segmentation requires a few pre-processing steps, which we describe below. We also explain the matting and background image creation steps, required for rendering. Recall that the input to these steps is the multi-view stereo reconstruction with calibrated cameras, and the user-defined thin structure geometry.

Pre-processing

Our multi-view segmentation approach assumes that the thin structures are not reconstructed. In some cases, modern reconstruction algorithms create spurious geometry in the thin structure supporting surface S, typically filling the space between them or even reconstructing small parts of the structure. To allow high-quality segmentation, we need to remove this reconstruction, bringing our input data into the canonical form expected by the segmentation.

Removing reconstruction in the thin structure geometry. To identify the vertices of the proxy that comes from superfluous reconstruction (e.g., false surfaces between thin structured), we first compute a smoothed histogram of the log point-to-mesh L2 distance between the proxy vertices and the thin structure geometry. We then remove all the vertices for which the log-distance is

Input

Proxy log-distance Cleaning Filling New 3D Recon. smaller than the value associated to the first valley (see Fig. 7). Such removal can reveal holes in the proxy that need to be filled in order to have a depth available behind the thin structure geometry. We fill those holes by fitting local planes.

Image Thin structures Filtered thin structures

Figure 8: Thin structure candidates for a given input image. Thin structures are marked in red, between detected edges in white. We filter these thin structure candidates using multi-view information.

To initialize the multi-view segmentation, we select thin structure candidates p that have P mv k (p) > 0.9

Detection of Thin Structure candidates. We obtain first candidate points for thin structures by detecting edges in the images [Can86].

Candidate points are generated between the edges. This is illustrated in Fig. 8: the edges detected are in white, and the generated candidates points are in red. Since a large number of such candidates can be generated, we filter the result using multi-view information. More specifically, we initialize a thin structure candidate to be at layer k if P mv k (p) > 0.9 for any k < Np. Every other pixel is initialized with the back-most layer.

Post-processing

In post-process, we need to extract the foreground and an alpha matte of the thin structures, create the background image corresponding to each input view and the clean background geometry. Before matting, we remove small spurious outliers, by removing connected components with size less than 0.2% of the image size.

Alpha Matting. The tri-map for the alpha matting step is obtained by first dilating the foreground label maps to create the uncertain region and eroding to determine the foreground. The resulting segmentations for two images of one of our test scenes are provided as supplemental material. The accuracy of the tri-maps is important to the success of the subsequent steps, but also depends on the matting algorithm used. We use the approach of [HRR * 11] for matting, which provides adequate alpha mattes for rendering.

Background Generation. We use the median images, updated with the visibility information from the segmentation, as background in the regions labelled as thin structures, with a Poisson editing step to correct for small differences in color levels. A small number of pixels are black in these images, corresponding to regions occluded by the thin structures in all images; we apply standard single-image inpainting to fill these holes using a variant of PatchMatch with the "occurence" term of Kaspar et al. [KNL * 15]. Once we have generated these color-balanced background images, we perform a fresh 3D reconstruction step with the thin structures removed. This step improves the quality of the background mesh significantly (see video).

Rendering

Our rendering algorithm is based on the Unstructured Lumigraph (ULR) [START_REF] Buehler | Unstructured lumigraph rendering[END_REF] with soft visibility [EDM * 08], operating on a per-pixel basis. Standard ULR precomputes a depth buffer for each input view. During rendering, a first pass renders the depth to the frame buffer, and for each fragment, we perform a depth test for each input view with the precomputed depth. If the test fails the fragment is discarded (Fig. 9(a)). If it succeeds, the ULR weights w i are computed [START_REF] Buehler | Unstructured lumigraph rendering[END_REF] expressing the match in angle and distance between the novel and input views, and used to blend the corresponding colors from the input images.

Our scenes are more complex. The depth map for each input view is computed using the background geometry, and then augmented with the information provided by the segmentation. Each pixel on a thin structure has a depth corresponding to the supporting geometry layer determined by the segmentation, and an alpha value computed by the matting process (Fig. 9(b)). There are two main issues: first, the supporting geometry of the thin structure (dashed lines in Fig. 9(b)-(d)) is semi-transparent, and thus requires a specific rendering algorithm and second, we need to define how to combine the view-dependent alpha values in the novel view.

For the first issue, we adapt the depth peeling algorithm [START_REF] Everitt | Interactive order-independent transparency[END_REF], run in back-to-front order. This consists in progressively rendering each layer of depth with a "less-than" depth test and alpha blending with the previous layer. We first render the clean background proxy using standard ULR, then perform depth peeling using the supporting geometries.

For the second issue we propose an interpretation of α values as conditional probabilities of having a thin structure along the viewing ray of a pixel in each input view. P(thin f |V i ) is the conditional probability that a fragment f is on a thin structure, given view V i . We thus assume α i = P(thin f |V i ); we interpret ULR weights as a prior probability of each view V i :

P(V i ) = w i ∑ k w k . ( 10
)
We will apply Bayes rule to compute the overall probability of a given fragment being on a thin structure, at a given layer of the depth peeling algorithm, which can be seen as a multi-view filtering of the segmentation results. Then we use this probability as the α f value for blending the weighted ULR colors from the input views for fragment f (see Algorithm 1 for the details):

α f = P(thin f ) = ∑ i P(thin f |V i )P(V i ) = ∑ i α i w i ∑ i w i (11)
There are two cases that need to be treated as specific depth tests. First, if a fragment of a thin structure from another input view V j is in front of the current thin structure fragment f , then V j is ignored by setting w j = 0 (e.g., Fig. 9(c), V 1 is ignored), since it cannot provide information about a fragment behind it. The second case is if there is a thin structure at a depth behind the fragment f in an input view. Since the segmentation has placed it behind f , the conditional probability that the thin structure is at the depth of f is 0; we thus set P(thin f |V i ) = α i = 0. However, we include the input view in the blend of colors to be conservative. This approach is related to the consensus voting approach in Soft3D [PZ17]. Since we have surface-based geometry, instead of performing volumetric accumulation, we can directly used the probabilities computed to make a decision for each fragment, avoiding visual artifacts far from the input cameras.

Ccurrent ← C f • α f + (1 -α f ) •Ccurrent;

Results and Comparisons

We first show results of our method on a variety of scenes. We then provide comparisons with related work, and finally discuss limitations. When judging comparisons, one should consider that our results benefit from the user-defined thin geometry, but this information only could not be directly used by these previous algorithms.

Results

We ran our approach on an Xeon E5-2650 PC. For each scene we took between 10 and 30 photos. The outdoors scenes were taken In our case, we have multiple values of α from different views, that blend with the background. These are interpreted as probabilities of being a thin structure at this depth, thus in this example P(thin f |V 1 ) = α 1 = 0.8 and P(thin f |V 2 ) = α 2 = 0.5. (c) If for an input view the depth map is in front of the current fragment, the view (V 1 here) is ignored as the view gives no information about the fragment. (d) If for an input view, the depth map is behind the current fragment, the view (V 2 here) estimates there is no thin structure at the fragment location with P(thin f |V 2 ) = 0.

α = 0.8 V 1 V 1 V 2 V 2 V 1 V 2 (a) (b) (c) (d) V n V n V n V n V 1 V 2 V n α =
with a DSLR camera, and the indoors with an iPhone 6S. We use [Rea16] for camera calibration and 3D reconstruction. Note that we assume that a background depth is reconstructed for all pixels in an image; To treat a scene with a sky background for example, a bounding box could be fit to the scene to provide "far depth" for sky pixels. The user specifies the supporting geometry by providing correspondences points in a multi-view interface to fit a basic 3D primitive and then manipulates the primitive control points in a 3D window; Our current interface handles planar segments and cylinders. Please see the video for an example interaction session.

The whole offline pipeline (excluding reconstruction steps) took in the order of 5 minutes for the smaller scenes (∼ 10 images) to 20 minutes for the larger scenes (∼30 images). The rendering runs at 60 fps on a 1080p display with all datasets using a GTX 1080.

Our approach allows us to capture complex shapes which are not necessarily purely repetitive, for example in the "Stairs" scene. We provide the multi-view segmentations and the mattes for all our datasets in supplemental material. Small artifacts in the segmentation are often alleviated by the blending step of IBR. We show the results of our inpainting step and rendering from novel viewpoints in Fig. 10. The Stairs and Rolland scenes contain multiple layers of thin structure depth, and the Balcony scene is a cylinder with multiple depths. The supporting geometry could in theory have any form, as long as it can be reasonably represented by a mesh.

Comparisons

We present comparisons on rendering and segmentation. For rendering, please see the accompanying video, the improvement over of previous methods is much more evident during interactive freeviewpoint navigation.

Rendering. Our approach allows free-viewpoint navigation to regions quite far from the original cameras. We thus focus our comparisons on other methods that allow interactive freeviewpoint navigation, in particular Unstructured Lumigraph Rendering (ULR) [START_REF] Buehler | Unstructured lumigraph rendering[END_REF] and Bayesian IBR [OCDD15] (which subsumes [CDSHD13]). For these comparisons we use our reimplementation of ULR, which in contrast to the original version, uses per-pixel weights based on the geometric proxy from MVS reconstruction, and the original implementation of Bayesian IBR [OCDD15]. We show results for several scenes and novel viewpoints, far from the input cameras. Our method greatly improves over previous methods, since those methods incorrectly project thin structures onto the background geometry.

In addition to these free-viewpoint methods we compare to the recent Soft3D IBR method [PZ17]. We use an reimplementation of the complete Soft3D method provided by P. Hedman of UCL † . As can be seen in the video, Soft3D produces high quality results for certain capture configurations (e.g., all cameras in a plane) and when interpolating camera positions. When moving away from the input cameras, blurring artifacts appear due to the depth discretization. These are even more visible for thin structures. Note also that rendering a single image with Soft3D takes seconds, compared to the real-time behavior of our method.

Segmentation. To our knowledge, no previous method has addressed thin structures for image-based rendering. As a result, we compare with the most closely related methods, which are not tuned for our data. For completeness, we also compare to previous latticedetection methods in supplemental material. The results show that such methods either fail to find parts or even most of the thin structures, or sometimes only partially succeed for some but not all of the images in the multi-view dataset. This is unsuprising given our richer input (camera calibration, 3D reconstruction and userdefined thin geometry); The comparison is provided to show that these methods cannot solve our problem.

We also compare to automatic fence segmentation [YWT16] in Fig. 11. The authors kindly ran their code on our dataset, however since our data are not continuous videoframes their method cannot perform spatio-temporal refinements based on frame-by-frame optical flow. Thus the results shown are the "initial segmentation" described in the paper. If the input requirements for this method are respected, the results would be better. Similarly, we compare to the method of Xue et al. [START_REF] Xue | A computational approach for obstruction-free photography[END_REF] run on a crop of the input images. Again this method expects a smaller baseline between images, and thus cannot be used for our target scenes. † We provide a comparison of our results for the Soft3D algorithm and the original implementation on the Museum scene [CDSHD13] as an additional video. The general image quality is similar, even though the original implementation is slightly sharper.

Limitations and discussion

Our method fails when the background has the same color as the foreground in all views. Our simple thin geometries are implicitly assumed to be infinitely thin; this works well for most cases, but becomes problematic at extreme grazing angles such as Fig, 13(a). The ability to detect thin structures also depends on the resolution of the images with respect to the thickness of the structures. When the structures are too thin, our approach can fail, as seen in Fig. 13. In all our examples, the supporting surfaces produced were accurate enough to produce good quality results. Consequently, we did not perform in-depth robustness analysis. Very imprecise user input could result in inaccuracies for the supporting geometry, affecting the segmentation quality because of the larger number of incorrect multi-view links. For such input, the surface estimation could be refined between segmentation steps, e.g., using intermediate segmentation results to find dense correspondences. Automating the detection of supporting geometries could be achieved with learning-based solutions. Recent high-quality segmentation deep learning networks (e.g., [START_REF] Lin | RefineNet: Multipath refinement networks for high-resolution semantic segmentation[END_REF]) could potentially be adapted and trained to identify thin structures, although generating the training data is a challenge. Similarly, deep learning has been used to find parameters of simple geometric structures [NGDA * 16]. With suitable knowledge of semantics and the correspondence between supporting primitive type and thin structure, such an approach could be developed to allow primitive fitting based on images, potentially combined with an optimization step [OCDM * 16]. Another interesting challenge is the interaction of thin structures and vegetation which renders the problem much harder.

Rendering

Conclusions and Future Work

We have presented a new method to treat the hard problem of thin structures for image-based rendering. The central component of our approach is a segmentation algorithm which exploits multiview information and 3D reconstruction to provide segmentation of multi-layer thin structures. Our end-to-end solution allows us to produce results showing significant improvement over previous methods in terms of rendering quality, allowing common scenes with thin structured to be used in a free-viewpoint IBR context for the first time.

The key aspect of our work is to leverage multi-view information to overcome the ambiguities in the hard case of thin structure segmentation. Using other priors as discussed above will allow this approach to generalize to other structures in terms of complex geometry and varying frequencies of the repetitive patterns.

2. 1 .

 1 De-fencing and Repetitive Structure Detection Hays et al. [HLEL06] divide research on discovering repeated elements into two extremes: the first focusing on the individual element [LF04] and the other imposing strong structure priors on the general layout of the repeating elements [TTVG01]. Hays et al. are the first to automate lattice detection in real images without pre-segmentation. Further improvement is proposed by Park et al. [PBCL09] by solving the problem in an MRF setting. More recently, Liu et al.

Figure 2 :

 2 Figure 2: End-to-end solution for thin structures in IBR. (a) After reconstruction and supporting geometries extraction from user interaction, we proceed to (b) pre-processing step to remove spurious geometry. We then perform (c) multi-view, multi-layer segmentation followed by (d) post-processing to create "clean" background images and geometry. The result can be used by our multi-layer rendering algorithm (e), allowing free-viewpoint navigation.

Figure 3 :

 3 Figure 3: Benefits of a multi-view approach. Segmentation of the ambiguous area on the left can be resolved using the view on the right.

Figure 7 :

 7 Figure 7: Result of the depth pre-processing for regions with spurious reconstructed geometry in the geometry of thin structures. The histogram shows the log distances distribution between the supporting geometry and the proxy vertices. The closest vertices (red bins) are removed during the cleaning step.

Figure 9 :

 9 Figure9: (a) Traditional ULR rendering: For fragment f (green circle) we ignore view V 1 . (b) In our case, we have multiple values of α from different views, that blend with the background. These are interpreted as probabilities of being a thin structure at this depth, thus in this example P(thin f |V 1 ) = α 1 = 0.8 and P(thin f |V 2 ) = α 2 = 0.5. (c) If for an input view the depth map is in front of the current fragment, the view (V 1 here) is ignored as the view gives no information about the fragment. (d) If for an input view, the depth map is behind the current fragment, the view (V 2 here) estimates there is no thin structure at the fragment location with P(thin f |V 2 ) = 0.

ULRFigure 10 :

 10 Figure 10: Rendering results for 9 different scenes from novel views far from the input cameras. From left to right: rendering results for [OCDD15], our improved version of [BBMC01], a re-implementation of Soft3D [PZ17], the inpainted background and the top view showing the novel camera, and our result.

Figure 11 :Figure 12 :

 1112 Figure 11: Results of video de-fencing method. This is the result obtained on House and Basilic datasets with a method based on motion estimation [YWT16]. In a wide baseline setup, it is unlikely to compute reliable matches between consecutive images.Obstruction free photography[START_REF] Xue | A computational approach for obstruction-free photography[END_REF]

Figure 13 :

 13 Figure 13: (a) At extreme grazing angles, the infinitely thin assumption is insufficient. (b) Very small structures in input images can be missed by our approach (see rendering in (c)).

  ALGORITHM 1: Multi-Depth Thin Structure Rendering Algorithm.

	Input: Images with depth, background and thin geometry
	Result: Novel View
	Render clean background with standard ULR into Ccurrent;
	for each depth peel layer, back to front do
	Render alpha with depth tests in α f ;
	Render color with ULR weights in C f ;
	Blend with previous layers :

c 2018 The Author(s) Computer Graphics Forum c 2018 The Eurographics Association and John Wiley & Sons Ltd.

Acknowledgements

This research was partially funded by the doctoral fellowship of the Region Provence Alpes Cote d'Azur, ANR project SEMAPOLIS (ANR-13-CORD-0003), the EU Horizon 2020 grant No. 727188 EMOTIVE, http://www.emotiveproject.eu/, and by generous donations from Technicolor and Adobe. The authors thank P. Hedman for his Soft3D implementation, J. Philip for mesh alignment code and S. Rodriguez for his precious help finalizing the paper.


W Stechele
email: walter.stechele@ei.tum.de

L Alvado Cárcel

S Herrmann

J Lidón Simón

A Coprocessor for Accelerating Visual Information Processing

Visual information processing will play an increasingly important role in future electronics systems. In many applications, e.g. video surveillance cameras, data throughput of microprocessors is not sufficient and power consumption is too high. Instruction profiling on a typical test algorithm has shown that pixel address calculations are the dominant operations to be optimized. Therefore AddressLib, a structured scheme for pixel addressing was developed, that can be accelerated by AddressEngine, a coprocessor for visual information processing. In this paper, the architectural design of AddressEngine is described, which in the first step supports a subset of the AddressLib. Dataflow and memory organization are optimized during architectural design. AddressEngine was implemented in a FPGA and was tested with MPEG-7 Global Motion Estimation algorithm. Results on processing speed and circuit complexity are given and compared to a pure software implementation. The next step will be the support for the full AddressLib, including segment addressing. An outlook on further investigations on dynamic reconfiguration capabilities is given.

Introduction

There are various applications in visual information processing with real-time requirements, e.g. video surveillance and driver assistance. The algorithms for such applications are not standardized, and might never be, but are a topic of ongoing research. Therefore any hardware platform for implementation needs to be flexible enough to support evolving algorithms, but at the same time needs high computational density to meet the requirements.

The focus of this paper is on the design of a coprocessor for visual information processing, where a key technique is video object segmentation [START_REF] Mezaris | A test-bed for region-based image retrieval using multiple segmentation algorithms and the MPEG-7 eXperimentation Model: The Schema Reference System[END_REF].

Algorithms for video object segmentation are using many different operations. They can be grouped into high level control operations and low level pixel manipulation. Control requires a high degree of flexibility and thus is good for processor implementation. Pixel manipulation on the other hand requires applying the same operation on many pixels and thus seems to be a good candidate for hardware acceleration. The problem is how to accelerate without loosing flexibility.

As pixel addressing has shown in [START_REF] Herrmann | A Video Segmentation Algorithm for Hierarchical Object Representations and Its Implementation[END_REF] to be the dominant part in complexity, a structured approach for the definition of addressing schemes was selected as a basis for further optimization. In order to evaluate the potential of hardware acceleration, a coprocessor architecture, called AddressEngine, was developed, which supports a wide range of image analysis algorithms.

Based on instruction level profiling of a video object segmentation algorithm [START_REF] Stechele | Towards a Dynamically Reconfigurable System-on-Chip Platform for Video Signal Processing[END_REF] the maximum achievable acceleration with AddressEngine is estimated as a factor of 30, taking into account that all high level parts of the algorithm are executed on the main CPU and only low level operations are executed on AddressEngine. In contrast to a dedicated hardware accelerator, the use of AddressEngine keeps all flexibility and programmability of the algorithm on the main CPU.

The architecture concept of this coprocessor is described in section 2, starting with an overview on the addressing scheme and pixel processing, which are supported by the coprocessor. In section 3 our prototype implementation is described, including dataflow control and memory management. Results on processing speed and complexity on the FPGA are given, as well as a comparison between performances of FPGA versus software implementation of a test algorithm. The outlook presents some ideas for further investigations with this architecture, exploiting dynamic reconfiguration capabilities of FPGAs [START_REF] Becker | Configurable Systems-on-Chip: Commercial and Academic Approaches[END_REF], [START_REF] Compton | Reconfigurable Computing: A Survey of Systems and Software[END_REF].

AddressEngine

Our target platform consists of a hardware coprocessor and a software library, where low level pixel operations are executed in a processing unit with high throughput and low power dissipation.

Addressing Scheme

Although there are various different video algorithms, many of them consist of operations, which use only four ways to access the pixel data: Inter addressing, intra addressing, segment addressing, and segment indexed addressing (figure 1). These four types of addressing were implemented in the AddressLib [START_REF] Herrmann | A Video Segmentation Algorithm for Hierarchical Object Representations and Its Implementation[END_REF].

Inter addressing is the addressing mode where a result for each pixel position is calculated using data from two different frames. Its application may be computation of difference pictures or SAD (Sum of Absolute Differences).

Intra addressing is used in situations where a result is calculated for each pixel as a function of the pixel's original value and the values of its neighbors within the same image. This is typically used for FIR filter like operations, as gradient operators and morphological operators.

Segment addressing is used if arbitrarily shaped segments have to be processed. In this kind of processing, a segment is determined by local neighborhood criteria. First, the pixel processing is done in the same way as for intra addressing. Second, all neighbor pixels which have not been processed before, are tested if they fulfill specified neighborhood criteria. If they do, they might be processed in one of the following steps of the algorithm. By operating this way, an expansion process takes place: Beginning with a set of start pixels, all pixels of the segment are processed in order of geodesic distance.

Segment indexed addressing is an addressing method, which is used in parallel to one of the above addressing methods, when data associated to a segment is needed or generated during the pixel processing, e.g. segment identification numbers. This is done accessing an indexed table.

The first two schemes are well known from frame based or block based video processing. The third addressing scheme is used for pixel addressing of arbitrarily shaped segments in a rectangular frame. The fourth scheme represents indexed table accesses and differs from the other schemes by not addressing pixel data.

Pixel Processing

Pixel-level operations may be separated into basic subfunctions, such as add, sub, mult, grad, in order to achieve efficiency and flexibility. These sub-functions can be combined to form more complex operations, e.g. luminance/chrominance difference between neighboring pixels for homogeneity check, or morphological gradient operations.

Prototype Implementation

The hardware architecture of the AddressEngine coprocessor includes, in this first version, a subset of the four types of pixel addressing used in the AddressLib software, the intra-and inter addressing modes. The coprocessor has been implemented using the Alpha Data board ADM XRC-II, which contains a VirtexII 3000 FPGA with 216 kBytes of embedded RAM memory, a ZBT SRAM segmented memory (6 Mbytes) made up of 6 independent banks with one write-read 32 bits long port each. The communication between PC and the coprocessor is interrupt oriented and happens through the PCI bus which also has a width of 32 bits. Therefore the architecture design decisions are determined not only by the specifications of the AddressLib software but also by the constraints due to the hardware available in the board used.

The coprocessor architecture deals with both pixel addressing and pixel processing. It is statically configurable in this first version, since the same operation is applied to all the pixels in the whole image for one AddressEngine call. Thus the architecture implements both the processing unit and an input output interface between PC and the processing unit. This is designed to optimize the bus PCI utilization, to obtain an efficient dataflow and to minimize the number of memory accesses by means of pixel reusing and parallel neighbourhood loading.

The general scheme of the architecture, as illustrated in figure 2, consists of the following parts: The on-board memory (ZBT), the intermediate memory system (IIM/OIM), the processing unit, the pixel level controller, transmission units (TxUs), and the image level controller. The architecture description starts with an overview of the memory management. Later, the dataflow control and the whole system operation are described and finally the processing unit is analyzed in depth.

Memory Management

The ZBT on-board memory size permits to store two input and one output image structure of either image type employed, QCIF (i.e. 176 x 144 pixels, approx. 200 kBytes) or CIF (i.e. 352 x 288 pixels, approx. 800 kBytes). Since the memory width is 32 bits and the pixel size is 64 bits (i.e. 8 bits per Y,U,V channels and 16 bits per Alfa and Aux channels) two memory positions are required to store one pixel. The AddressEngine coprocessor stores the upper and the lower part of the pixel in the same position of two different ZBT banks. In that way it is possible to access any pixel within only one memory cycle deploying a very simple addressing mode.

The communication between PC and the board is interrupt oriented and realized through DMA transfers. The same design style is employed both for the input and the output interfaces of the coprocessor to optimize the PC memory on-board coupling.

The whole input image is not transferred in one pass but it is divided into parts which are written to alternate ZBT blocks. Thus an optimized usage of the PCI bus is obtained and it is possible to start processing although the input image is not completely stored in the memory. The design decisions related to the size and shape of these parts are determined by software constraints, due to the AddressLib functionality. Firstly, as the pixel addressing within the input image is not random but sequential, the image is transferred in strips, horizontal or vertical depending on the way of scanning the image. The selected strip size is sixteen lines, as the maximum range of input data required to process one pixel is nine lines. The choice of a power of two number guarantees an easy addressing mode. Sixteen is also divisor of the image size, so it makes the system management easier.

In the output interface, the same idea of alternate blocks is used, to keep the optimized use of the PCI bus, but with some differences. Firstly, the upper and the lower part of each pixel are stored sequentially in the same memory bank, in such a way the PC gets the pixel data properly ordered. And secondly, the bank switching is performed only once, as soon as it is possible to start transferring the resulting image.

The expounded way of storing pixels and how the information is transferred between PC and the coprocessor results in a specific memory distribution, see figure 3. Related to this system temporal behaviour, the strip stored in the so-called block_A is processed while the next strip is transferred to block_B and vice versa. And the Res_block_A can be transferred when the PCI bus is free, i.e. when the input image is completely stored in the ZBT.

Fig. 3: ZBT memory distribution.

Relating to the intermediate memory system, the second module defined in the AddressEngine, two memory structures have been implemented. These are the so-called IIM, input intermediate memory, and the OIM, output intermediate memory.

The IIM is implemented at the input of the processing unit because there is a successive pixel reuse at this point of the system. Thus loading the complete neighbourhood for each pixel is avoided. Furthermore, with the implementation employed the whole neighbourhood can be obtained in only one cycle, even in the worst case with perpendicular neighbourhood and scan direction, as illustrated in figure 4. In case the neighbourhood is not loaded in the IIM the image level controller takes care of halting the system until it is available. The IIM size, in tune with the strip size, is sixteen lines. The IIM structure is made up of sixteen memory blocks, with two banks for the lower and the upper part of the pixel. These 32 memory blocks are implemented in the FPGA embedded memory. At the output of the processing unit an intermediate memory system is required as well. The OIM has exactly the same structure as the IIM, but it is needed because of different reasons. It is used as a buffer structure because there are different speeds at the interface processor unit output -ZBT memory, since the processing unit provides pixels in twice the speed than can be written to the ZBT memory. The pixel level controller generates the control signals for the processing unit and the processing unit manages the image scanning. So the pixel level controller deals with the dataflow control between the intermediate memory system and the processing unit.

Dataflow Control

The transmission unit controls the transfer of lines from the ZBT memory to the intermediate memory system, in both the OIM-and the IIM structure.

The image level controller deals with the interrupt generation and manages as well all control blocks. So it controls the data transfers between PC and the coprocessor.

The PLC (fig. 5) is compound by four modules: The arbiter, the instructions FSM, the startpipeline and the control FSM (i.e. Finite-State-Machine). The control FSM generates the set of instructions to be performed in every pixel-cycle. The arbiter makes sure that the instructions in the different stages will not access to the same resources in the Process Unit. The instructions FSM can request and lock the resources in the Process Unit and generate the signals that steer the correct behavior of these resources.

Finally, the startpipeline deals with the correct order of the execution of the instructions allowing us also to have instructions of different pixel-cycles in the different stages of the Process Unit being not needed to wait till one pixelcycle is finished to start with the next one.

Finally, the dataflow through the system is managed by the image level controller according to the processing unit needs and requirements.

Interface Processor to Image Level Ctrl

The interface of the processor with the image level controller consists of a set of signals to carry out the correct supply and processing of the data.

Since the IIM and OIM act as FIFOs, the signals to control if both are in the correct state to supply and store the data to and from the processing unit consist of FULL and EMPTY signals for each of them.

For the inter addressing mode the IIM will take the form of two FIFOs, one for every input image, with 8 lines each. In this case we will generate the same signals for both of the FIFOs. In order to stop the processing unit when there is no data available to read or no empty space in the OIM to write, the image level controller will disable the pixel level controller which will not proceed with any more pixelcycles until this signal is enabled again.

Pixel Level Controller

The pixel level controller is the controlpath of the processor. Its purpose is to control the process unit (i.e. datapath) enabling the intervention of its components when necessary.

The datapath of our design is divided into four stages. In order to generate a result pixel one instruction has to be performed in each one of the stages. The pixel level controller (PLC from now on) will take charge of generating these instructions and executing them in the proper order.

Process Unit

The Process Unit (fig. 6) is the datapath of the Processor.

As has been stated before, the Process Unit is divided into four different stages.

Stage 1 performs the scanning through the image. The central position of the neighbourhood in the input image for the next pixel-cycle is calculated here. Instructions that work with the pixel position counters which indicate the current pixel of the image we are sweeping belong to this stage.

All the instructions that obtain data from the IIM and save it to the matrix register belong to stage 2. In the matrix register is stored the whole neighbourhood that will be input for the next stage. These instructions are divided into two sets: LOAD instructions and SHIFT instructions depending on whether they fill the whole matrix from scratch or whether they only add some shifting the pixels that were already in the matrix.

Stage 3 performs the execution of the pixel-operation on the neighbourhood. Operations like gradient, histogram, different filterings, etc. are carried out here.

In the fourth Stage the result pixel obtained in the third one is stored in the OIM.

Prototype Performance Results

Implementation Cost and Clock Rate

The system has been implemented with ISE 6 in a Virtex II 2V3000 board, experimental results regarding complexity and performance are shown in table 1.

Device utilization summary:

Selected Device : 2v3000ff1152-5 Table . 1

Assuming that the performance of the design is constraint by the bandwidth of the PCI bus (66 MHz) which happens to be the bottleneck of the system, the clock speed should be fast enough to work with the FPGA. With this clock frequency a 264 Mbytes/s rate can be achieved between every one of the 6 ZBT RAM banks and the FPGA.

In fact, the effect in the timings due to the processing is insignificant except for some special inter operations where we cannot start processing until both of the images have been completely transferred. Even in this situation the time wasted not due to the PCI transferences is a 12.5% of the time needed to transfer the images to the board.

The high amount of block RAM used (BRAM) in the design is due to the IIM and OIM memories. In any case there is enough free memory for a possible extension of the design with other addressing schemes.

Performance of the Memory Architecture

In order to estimate the improvement in performance added by the memory scheme used in the hardware solution a comparison between the number of memory access operations carried out by the software solution and those made by the processor in the design has been made. In table 2 CON_0 means that the one pixel neighborhood has been used and CON_8 refers to the squared 8-pixels neighborhood that appears in Figure 4.

It can be deduced from these numbers that the benefit obtained by using the memory architecture described above increases with the amount of data traffic. This is a consequence of the parallel access to the pixels in the hardware design. There, all the channels of the new pixels needed to update the neighborhood are loaded in parallel while in the software solution this is done sequentially. Therefore a structure like this is beneficial for the addressing of pixel neighborhoods.

Comparison With a Software Implementation

The performance of the hardware solution has been tested against a software platform. This test consisted of an execution of the MPEG-7 Global Motion Estimation Software

Outlook

The implementation of intra and inter addressing schemes in an FPGA was described in this paper. The next step will be to implement the segment addressing scheme on the same FPGA board. Further on there are two directions: 1) Implementation in standard cell ASIC for further power and performance optimization. 2) Exploitation of dynamically reconfigurable FPGAs for more complex processing in research.

For exploitation of dynamic reconfigurability, an FPGA with embedded RISC core and partial dynamic reconfiguration capabilities will be used. The pixel addressing will be implemented in a statically configured block of the FPGA, as all supported algorithms are using the same AddressLib scheme, whereas the pixel processing, which might be changed during the process of video analysis, will be implemented in a dynamically reconfigurable block. High level control operations will be implemented on the embedded RISC processor.

Summary

The focus of this paper is on the design of a coprocessor architecture for visual information processing, where pixel addressing has shown to be the dominant operation, exceeding even pixel processing. Therefore pixel addressing was in the focus of optimization. Structured pixel addressing schemes have been implemented both in a software library, called AddressLib, and in a coprocessor architecture, called AddressEngine, described in this paper.

The first version of the AddressEngine was implemented on a FPGA board. A set of controllers was defined to control the dataflow within the AddressEngine and to/from the PC. A pipelined architecture for pixel processing and address calculations was developed. Memory accesses are in parallel on complete neighbourhoods of pixels. This first version of the AddressEngine supports intra and inter addressing schemes. Segment addressing is planned for future versions.

The performance of the AddressEngine was analyzed regarding processing speed and circuit complexity on the FPGA. A comparison with a software implementation of the MPEG-7 Global Motion Estimation algorithm has shown that our prototype achieves an average speedup factor of 5, if the high level algorithm is kept fully programmable on the main CPU.

Fig. 1 :

 1 Fig. 1: Pixel addressing schemes: Inter (left), intra (middle), and segment (right) addressing. Arrows indicate the direction of pixel processing.

Fig. 2 :

 2 Fig. 2: Architecture general diagram

Fig. 4 :

 4 Fig. 4: Different neighbourhood types: Worst case maximum size perpendicular to scan direction

Fig. 5 :

 5 Fig. 5: Detail of the PLC inside the Processor

Fig. 6 :

 6 Fig. 6: Detailed structure of the Process Unit

[ 6 ]

 6 over 4 different test sequences on a Pentium Mobile (PM) at 1.6 GHz with 512 MB DDR RAM.The hardware platform consisted of the ADM-XRCII board connected to the PCI bus of a PC with a Pentium 4 microprocessor running at 3 GHz. The top-level software layer of the Global Motion Estimation Software was kept in the PC, which accessed to the ADM-XRCII board after every call to the AddressLib. This global motion estimation software is used for Mosaicing purposes, the test sequences are MPEG-1 CIFsized and as a result this software creates a Mosaic with the global motion of the scene.

  Table 2 shows the results.

	Memory Accesses		Software	Hardware	Saving
	Addressing Input channels	Output channels	solution memory accesses	solution memory accesses
	Inter	Y	Y	304.128	202.752	33%
	Intra	Y	Y	202.752	202.752	0%
	CON_0
	Intra	Y	Y	405.504	202.752	50%
	CON_8
	Intra	Y,U,V	Y,U,V	608.256	202.752	200%
	CON_8

Table 2

 2

Table 3

 3 shows that the prototype implementation running with 66 MHz improves performance by an average factor of 5 over a PM running with 1.6 GHz. The bottleneck is the bandwidth of the PCI bus, which restricts the loading of the images. In future implementations, the PC in fig.2could be substituted by an embedded RISC, e.g. PowerPC on the FPGA and the PCI bus replaced by a more powerful on-chip bus, e.g. CoreConnect.

	Video	Time in	Time in	Intra	Inter
		PM	FPGA	AddrEng	AddrEng
				calls	calls
	Singapore	4'35''	1'04''	4542	3173
	Dome	5'28''	1'13''	4931	3404
	Pisa	12'25''	2'21''	9294	6541
	Movie	5'22''	1'05''	4070	3085

Table 3

 3

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgment

This material is based upon work supported by the IST program of the EU in the project IST-2000-32795 SCHEMA (http://www.iti.gr/schema)


Sandro V Silva
email: <svsilva@inf.ufrgs.br

Sergio Bampi
email: bampi>@inf.ufrgs.br

Area and Throughput Trade-Offs in the Design of Pipelined Discrete Wavelet Transform Architectures

The JPEG2000 standard defines the discrete wavelet transform (DWT) as a linear space-to-frequency transform of the image domain in an irreversible compression. This irreversible discrete wavelet transform is implemented by FIR filter using 9/7 Daubechies coefficients or a lifting scheme of factorizated coefficients from 9/7 Daubechies coefficients.

This work investigates the tradeoffs between area, power and data throughput (or operating frequency) of several implementations of the Discrete Wavelet Transform using the lifting scheme in various pipeline designs. This paper shows the results of five different architectures synthesized and simulated in FPGAs. It concludes that the descriptions with pipelined operators provide the best area-power-operating frequency trade-off over non-pipelined operators descriptions. Those descriptions require around 40% more hardware to increase the maximum operating frequency up to 100% and reduce power consumption to less than 50%. Starting from behavioral HDL descriptions provide the best areapower-operating frequency trade-off, improving hardware cost and maximum operating frequency around 30% in comparison to structural descriptions for the same power requirement.

Introduction

In images from real sceneries (photography), also called still tone images, adjacent pixels are almost always correlated, meaning that there are redundant data in the image coding [START_REF] Salomon | Data Compression. The Complete Reference[END_REF]. Image storage and transmission is costly, and image compression is mandatory in embedded applications.

The image compression techniques operate reducing or eliminating the data redundancies of still tone images [START_REF] Salomon | Data Compression. The Complete Reference[END_REF]. Image compression techniques can compress with or without loss of data of original image. The lossy compression can achieve higher ratio than lossless compression. The image compressor uses a linear transform to change the image domain from space to frequency, removing the correlation between pixels. An image compression technique efficiency depends on the amount of energy the linear transform can concentrate in few bands. So, in a lossy image compressor, after the linear transform the large amount of coefficients that are close to zero are eliminated by the quantizer block, and the quantized coefficients are entropy-coded for achieving high compression ratio. The loss of information eliminated by the quantizer operation is moderately compensated by the interpolation nature of the human visual system.

In the JPEG2000 standard [START_REF][END_REF] a lossy standard for image compression is defined using the discrete wavelet transform (DWT) for space-to-frequency transformation. This domain change achieves higher compression rates than DCT, since a large amount of coefficient images are close to zero.

The DWT can be designed by a sub-band multiresolution [START_REF] Salomon | Data Compression. The Complete Reference[END_REF]. This sub-band multiresolution is made by recursive use of 9/7 taps FIR filters with Daubechies coefficients. By a lifting factorization operation [START_REF] Daubechies | Factoring wavelet transforms into lifting steps[END_REF], a simpler approach can be used, reducing the hardware complexity.

Several efficient architectures to implement a hardware one-dimensional discrete wavelet transform (1D-DWT) already exist. Implementations by filter banks are presented in [START_REF] Motra | An Efficient Hardware Implementation of DWT and IDWT[END_REF], [START_REF] Masud | Reusable Silicon IP Cores for Discrete Wavelet Transform Applications[END_REF] and implementations by lifting scheme are presented in [START_REF] Dillen | Combined Line-Based Architecture for the 5-3 and 9-7 Wavelet Transform of JPEG[END_REF], [START_REF] Lakshminarayanan | Design and FPGA Implementation of Image Block Encoders with 2D-DWT[END_REF].

To prototype the DWT to a FPGA, both behavioral or structural description can be used. A behavioral description can be mapped/synthesized through specific internal resources of FPGAs, which results in different netlists. So, to implement an Intellectual Property (IP) Core or an Application Specific Integrated Circuit (ASIC), the resulting net-list may just contain macro structures that are specific to the FPGA vendor device mapping tool. To avoid this dependence on macro blocks, a structural design is definitely the choice.

In this work we implement five designs of a Discrete Wavelet Transform (DWT) by lifting scheme using behavioral and structural descriptions. We compare the tradeoffs between area cost, throughput (maximum frequency) and power requirement by synthesis and simulation in the Quartus II tools. All these implementations are synthesized to Altera APEX 20KE FPGA devices [START_REF] Altera | Apex20K Data Sheet[END_REF].

The rest of the paper is organized as follows. Section 2 explains the operation of the DWT. Section 3 describes the design of the lifting DWT architectures. In section 4 the results about area cost and operating frequencies are presented. Finally, section 5 presents a summary discussion and concluding remarks.

Discrete Wavelet Transform

The wavelet transform is a linear transform that can operate in direct or inverse form. The wavelet transform approximates a function by representing it as a linear combination of two sets of coefficients g and h constructed from functions derived respectively by a scaling function φ(t) and a mother wavelet function (t) [START_REF] Taubman | Image Compression Fundamentals, Standards and practice[END_REF].

The two-dimensional wavelet transform is computed by recursive application of one-dimensional wavelet transform. In a 1D-DWT each octave computes two subbands from one original band and each of this sub-bands has half the number of coefficients input without data loss. In a 2D-DWT each octave computes four sub-bands and each of these ones has a quarter number of coefficient input. Figure 1 shows the input and output of one octave of 2D-DWT. The output coefficients from 1D-DWT are produced by application of two filters on data input samples, then producing two different output coefficient bands. A lowpass filter using h(x) coefficients producing an output band representing low-frequency data and a high-pass filter using g(x) coefficients producing an output band representing high frequency data.

The finite samples filtering present a problem of discontinuities its boundaries. So, the image boundary information could be lost if it were not treated properly. A simple method to eliminate this problem consists in mirroring the boundaries of the samples. The amount of samples mirroring depends on the depth of the low pass filter

The implementation of an irreversible DWT can be done by using the Daubechies biorthogonal wavelet coefficients [START_REF] Taubman | Image Compression Fundamentals, Standards and practice[END_REF], consisting of FIR filter coefficients for a 7-tap high-pass filter and a 9-tap low-pass filter, as shown in figure 2. The basic architecture defined in figure 2 requires 16 adders, 16 multipliers and 8 registers. This architecture has high area cost for a parallel implementation, thus several algorithms were developed to reduce this area cost.

Z -1 Z -1 Z -1 Z -1 Z -1 Z -1 Z -1 Z -1 Z -
The lifting DWT scheme presented in [START_REF] Daubechies | Factoring wavelet transforms into lifting steps[END_REF] has reduced computational complexity, so reducing the hardware cost to compute the DWT. This algorithm shown schematically in figure 3 was developed by a factorization of poliphase matrix from 9/7 Daubechies wavelet filter coefficients.

+ γ(1+Z) + + + -k 1/k α(1+Z) β(1+1/Z) δ(1+1/Z) 2 2 2 2 X[2n] X[2n+1] input samples X[n]

Design of the architecture

The design of the 2D-DWT has three blocks: a 1D-DWT, memory and memory control blocks, as schematically shown in figure 4. The input image samples are stored in memory, so the memory size needs to be as large as the image size. In the main step, the memory control addresses the coefficients of band to 1D-DWT and addresses the transformed coefficients back to the memory. After computation of all octaves, the transformed coefficients are transferred to next stage.

Generic 1D-DWT architecture can be designed as a pipelined structure following the lifting scheme. This basic design is shown in figure 5. It was implemented using five different approaches and synthesized to an Altera APEX 20KE FPGA device. This basic architecture can be designed with 6 multipliers, 8 adders and around 14 registers. The multiplier constants used in the lifting scheme result from a factorization of coefficients from 9/7 Daubechies filter. The factorized coefficients in table 1 are represented as floating point values, integer ratios and fixed point binary in 2's complement.

DWT architecture described with behavioral integer generic multipliers

The simplest approach of a Lifting 1D-DWT is described with integer generic multipliers. This architecture was described as an 8-stage integer pipeline with two data-flows. The first dataflow computes the even samples and the second dataflow computes the odd samples. The alpha and gamma multiplications are inserted in the flow, from even dataflow to odd dataflow, and beta and delta multiplications are inserted in the flow from odd dataflow to even dataflow, as shown in figure 3.

The implementation of an integer multiplier has lower cost than floating point multiplication. In these designs, all multiplication constants are integer divisions generated by rounding of floating point lifting constants. The result adjustment is done later by an 8-bit right shift. This rounding technique introduces a small error in coefficients, but this error is not significant to the transform result since all output coefficients are later to be quantized. The integer value coefficients used in these architectures are shown in table 1.

The error introduced by rounding can be measured by peak signal to noise ratio (PSNR) metric. The PSNR is calculated by quadratic differences between the original image pixels and the reconstructed image pixels, as showed in figure 6. From results of PSNR calculated in a tile of "Lena" image shown in table 2, the errors introduced in the output transform coefficients by the use of Lifting scheme with either floating-point coefficients or integer-rounded coefficients is always around 0.1dB. Hence, we can ignore these errors introduced by the rounding technique. The bit length of DWT internal registers depends on their relative position inside the DWT pipeline.

• The registers located before alpha multiplication in the odd dataflow and before beta multiplication in the even dataflow store integers from -127 to 128 (signed 8-bits). • The registers located after alpha multiplications and before gamma multiplication store integers from -530 to 530 (signed 11-bits). • The registers located after beta multiplication and before delta multiplication store values from -184 to 184 (signed 9-bits). • The registers located after gamma multiplication and before -k multiplication store values from -205 to 205 (signed 9-bits). • The register located after delta multiplication and before division by k stores values from -366 to 366 (signed 10-bits). • The register located at output data of the even dataflow (after division by k), corresponding to low frequency of input image samples, stores values from -298 to 298 (signed 10-bits). • The register located at output data of the odd dataflow (after multiplication by -k), corresponding to high frequency of input image samples, stores values from -252 to 252 (signed 9-bits). We kept these 9 bits, even though a low magnitude value is expected for this data output due to the nature of the transform of still-tone images.

DWT architecture described with behavioral shifted integer adders

Generic multipliers usually have high area cost. Multiplication by constant can be performed by shifted additions when the number of bits in the multiplication is large.

The decimal point showed in binary representation in Table 1 is for documenting the design of the control, as it is not considered in the hardware multiplier, which is fixpoint and is later adjusted by 8-bit right shift.

By binary representation of multiplier constants presented in table 1, the multiplication by alpha needs 6 adders, the first one to perform r0+r2, the next four ones to perform the sum between second, fourth, sixth, seventh and two complement of tenth shifted partial products of r0+r2. The last one performs the sum with r3. Figure 6 shows how ordering the partial products are done to implement the multiplication by alpha. The multiplication by beta needed 8 adders, but one adder result can be re-used, reducing this stage to 7 adders. The multiplication by gamma needs 5 adders and the multiplication by delta needs 5 adders.

The -k equivalent constant has 5 high bits and this stage needed a simple multiplication, so 4 adders can perform the multiplication by -k. The 1/k equivalent has 3 high bits, so 2 adders can perform the multiplication by 1/k. Hence, this design promotes only integer sums, reducing the area cost thus increasing the maximum operating frequency.

After all sums of each stage, the generated value is a real number, to generate the integer value on output stage a truncation promoted by an 8-bit right shift occur, as shown in figure 7.

DWT architecture described with behavioral pipeline of shifted integer adders

The architecture of lifting DWT can be naturally pipelined, but the add/shift stages represent the worst delay path between registers. Pipelining these stages increases the data throughput (operating frequency). The original arithmetic stage structure to perform the multiplication by alpha is shown in figure 8(a). The pipelining of this stage is straightforward -as the insertion of some registers inside the logic shows in figure 8(b). There is just one sum operation at each pipeline stage.

Hence, pipelining increases the area cost of the architecture, but reduces the worst delay path between registers, increasing the throughput rate of the DWT. The computation of each stage will be faster than architectures presented in section 3.1 and 3.2 and the power consumption should be reduced, allowing the trade-offs we explore later.

DWT architecture described with structural shifted integer adders

A behavioral implementation is the simplest choice to improve a design to synthesize this architecture in a FPGA device, by using specific megacore functions to implement the multipliers and adders. But should it be required to synthesize this architecture in an ASIC, all structures must be defined structurally. This implementation approach is similar to description in section 3.2 although the adders are structurally described. Except the alpha multiplications, the other multiplication blocks need to compute with signed operators, so the left bits from most significant bit (MSB) of an operator are replicated in the MSB.

All adders are implemented using Full Adder as basic blocks. The register adders are implemented by an n-bit set of full adder blocks. The length of each adder depends on the length of its inputs and length of the partial product shifted.

DWT architecture described with structural pipeline of shifted integer adders

This approach implementation has similarities with architecture described in section 3.3 and the structural description of adders described in section 3.4.

This architecture has 21 pipeline stages, as the design described in section 3.3, although the stages of sum and multiplications are designed with structural full adder. As the architecture of section 3.3, each complete sum operation is done at just one pipeline stage. With this improvement, the architecture achieves higher operating frequency at reduced power consumption.

The structural implementation of adders require more area cost than behavioral implementation, so it is expected that this implementation has higher area cost, although its throughput is higher than other architectures without pipelined arithmetic stages.

The main advantage of this architecture description is being independent of the prototyping hardware, i.e. this architecture can be prototyped onto any FPGA device or to an ASIC.

Implementation Results

Here we present all implementation results of 1D-DWT architectures presented in section 3. All VHDL descriptions we developed were compiled and simulated in an APEX20KE FPGA device from Altera. Table 3 shows the results of area cost, maximum data throughput (maximum operating frequency), number of pipeline stages and power consumption estimated at a given reference frequency (15MHz), set by the slowest architecture. The design 1 is a behavioral implementation with integer multipliers. This is the simplest architecture to implement in VHDL. The architecture synthesized from the behavioral description incurred the highest power consumption simulates at 15MHz for comparison.

The smallest area cost architecture is the design 2, consisting a behavioral description using integer-shifted adders, as showed in figure 7. This reduced area cost is due to the fact that the synthesis utilizes fast carry chain propagation and the number of pipeline stages is limited to 8. So an 8-bit adder is mapped onto just 8 Logic Elements (LEs). In simulation of a tile of "Lena" at 40MHz, this architecture consumes 626mW, in other words, the 2.7 times increase in operating frequency over the first architecture provides a 2 times increase in its power consumption.

The design 3 is a behavioral implementation with pipelined integer shifted adders, resulting in a 21-stage pipeline. This is an architecture that has about 1.6 times the area cost of design 2 and has a maximum operating frequency that is 3 times larger. When running at 128MHz, this architecture consumes 808mW, representing 1.3 times the power consumption of the second architecture when this operates at less than one-third of the frequency (40MHz). So, the architecture of design 3 definitely shows a better area-power compromise per MHz than the second architecture.

The design 4 is a structural implementation with shifted integer adders. This architecture does not use the fast carry chain propagation, so an 8-bit adder requires 16 Logic Elements (LEs). It is expected the design 4 would have 2 times the area cost and same maximum operating frequency as design 2. But the result is the design 4 has 1.5 times the area cost and higher maximum frequency than design 2. The simulations at higher operation frequencies show that these two architectures maintain equivalent power consumption at same frequencies.

The design 5 is a structural implementation with pipelined shifted integer adders and it is an improvement of design 4. It presented the lowest power consumption of all 5 designs at the same frequency. As in design 3, design 5 has higher area cost, although it has higher maximum operating frequency. One could have expected both designs 3 and 5 to have about the same maximum frequency, which was not the case. This difference is because design 3 behavioral description can use the resources of fast carry chain propagation in the FPGA structure. The simulations show that this architecture has 15% less power consumption than design 3 at same operating frequency, requiring 476mW at 95MHz.

The architectures presented in [START_REF] Masud | Reusable Silicon IP Cores for Discrete Wavelet Transform Applications[END_REF], which is closest to ours, is implemented by filter banks using 785LEs at maximum operating frequency of 85.5 MHz. Comparing with our designs, the design 2 has half of area cost and its maximum operating frequency is nearly half, so they stand in different trade-off points. The design 3 we developed using deeper pipeline has the same area cost and its maximum operating frequency is double that of [START_REF] Masud | Reusable Silicon IP Cores for Discrete Wavelet Transform Applications[END_REF]. In this case, our architecture presents considerably larger throughput with the same area and possibly higher power. Power could not be compared against the work in the literature.

Conclusions

As presented in the results of table 2, the implementation of a lifting 1D-DWT using integer rounded factorized coefficients can be done without significant loss in image quality (less than 1dB of degradation in PSNR).

The implementation of a 1D-DWT architecture synthesized to a FPGA presents better results when using an initial behavioral description that takes advantage of the structural resources of FPGAs, such as the fast carry chain propagation.

The designs with pipelined operators (design 3 and design 5) have, in both cases -behavioral or structuralshown a better tradeoff between area cost and the throughput resulting from higher operating frequency. Moreover, the designs with pipelined operators reduced power consumption around 40%, at the expense of circa 40-60% more LEs (dependent on the type of description -40% for the purely structural description and 60% for the behavioral description).

The structural HDL descriptions have worse trade-off area cost per maximum operating frequency than behavioral descriptions. The structural description presents around 30% more hardware and 30% less for the maximum operating frequency than behavioral description at same power requirement. This is because the technology mapping with commercial FPGA tools is optimized to map onto specific cores embedded in the particular FPGA family. To map the prototype to an 1D-DWT ASIC, the structural description is certainly a better starting point.

Figure 1 .

 1 Figure 1. One octave of 2D-DWT.

Figure 2 .

 2 Figure 2. DWT by 9/7 taps Daubechies FIR filter.

Figure 3 .

 3 Figure 3. Lifting DWT.

Figure 4 .

 4 Figure 4. 2D-DWT architecture.

Figure 5 .

 5 Figure 5. Lifting 1D-DWT architecture.

Figure 6 .

 6 Figure 6. PSNR calculation.

I 8 IFigure 7 .

 87 Figure 7. Alpha multiplication by shifted adders.

Figure 8 .

 8 Figure 8. Arithmetic stage structure of alpha multiplication.

Table 1 . Lifting coefficients constants.

 1

	Coefficient	Floating Point value	Integer rounded	Binary representation
	alpha	-1.586 134 342 -406/256 10.01101010
	beta	-0.052 980 118	-14/256 11.11110010
	gamma	0.882 911 075	226/256 00.11100010
	delta	0.443 506 852	114/256 00.01110001
	-k	-1.230 174 105 -314/256 10.11000101
	1/k	0.812 893 066	208/256 00.11010000

Table 2 . Measurement of rounding error.

 2

	Method	PSNR (dB)
	FIR filter by floating point 9/7 Daubechies coefficients	37.497
	FIR filter by integer rounded 9/7 Daubechies coefficients	37.483
	Lifting scheme by floating point factorized coefficients	37.094
	Lifting scheme by integer rounded factorized coefficients	36.974

Table 3 . Implementation results.

 3

	Architecture	Area cost (LEs)	Maximum Operating frequency (MHz)	Power @15MHz (mW)	Pipeline stages
	Design 1	781	16.6	310	8
	Design 2	480	44.0	248	8
	Design 3	766	157	105	21
	Design 4	701	54.4	232	8
	Design 5	1002	105	91.4	21

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Acknowledgements

The grant PDI-TI for CNPQ research agency is gratefully acknowledged.