# 设计领域新风潮：Low Poly 风格

## 背景材料

Low Poly 与 Delaunay Triangulation 的不同在于，它不要求避免极瘦三角形的出现（也不是说不强调），而是更多强调轮廓的表达。

## 算法分析

### 策略

1. The artists usually use relative regular triangles rather than extremely degenerated ones.
2. The arrangement of the mesh vertices implies the structure of the objects.
3. Non-uniform subdivision. The background is often abstracted into larger triangles than the front salient object.
4. Color disturbance. The artists choose various colors in the flat area to make the image stereoscopic.

### 效果

1. automatic （可以手动修改，但自动的效果已经很好）
2. By constraining the edge features and the technique of color picking, our result image has a clear visual effect without zigzag artifacts.
3. We propose a feature flow field to guide the iteration of the Voronoi diagram. The arrangement of vertices after optimization well reflects the structure of the object.
4. A non-uniform sampling strategy based on salient region detection to make the front object and the background have different refinement density.
5. Our method is very fast. It only costs several seconds even on images of million pixels.

### 相关工作

1. NPR (Non-photorealistic rendering), but not low-poly rendering
2. not directly. but relative
1. Image compression
2. Image vectorization
3. Image tessellation
• Some Voronoi-based methods also give results like the Low Poly style, but they have subtle difference. Besides using polygons as primary elements rather than triangles, the polygons in the Voronoi tessellation do not adapt to the shapes and details as well as the Low Poly style, so that the objects in their result images are relatively more confusing.
• do not use PSNR value to evaluate the result.

### 算法流程

1. Constrained edge feature
1. Edge Ddrawing method + Canny edge detector → produce high-quality edge segments (clean, well-localized and one-pixel wide)
2. a polygon approximation algorithm (classical Douglas-Peucker algorithm) → simplify the edges and leave the key points only
3. If an edge is longer than a minimum length, we slice it into two segments from its midpoint. We choose the minimum length same as the sampling interval $$L_i$$:

$$L_i = \eta (L_w+L_h)$$

where

$$L_w$$: image width,

$$L_h$$ image height
$$\eta$$: controls the sampling density, 0.2 in our case
2. Sampling based on saliency

use different sample densities between the saliency region and the background:

$\begin{cases} N_s &=& \lambda (N - N_c ) \\ N_b &=& (1 - \lambda )(N - N_c ) \end{cases}$

where

$$N$$: total number of sampling, $$N = \lfloor{\frac{L_w}{L_i}}\rfloor \times \lfloor\frac{L_h}{L_i}\rfloor$$

$$N_c$$: constrained point numbers in the previous step
$$\lambda$$: we choose 0.7 as an empirical value

1. Input image.
2. Saliency map.
3. Result with $$\lambda$$ = 0.2.
4. Result with $$\lambda$$ = 0.8.
3. Feature flow field

1. Vertices placement of the mesh follow the local shape structure of the object → a feature flow field to guide the optimization of the vertices positions.
2. steps

• compute a distance map $$\operatorname{D}(x)$$
• use the Jump Flooding method to solve this distance transform problem *. &neq; image-stippling problem, for density. instead CVT (centroidal Voronoi tessellation)

$F(x) = \begin{cases} \frac{255}{m} \operatorname{D}(x) \operatorname{mod}(m), \text{if} \frac{\operatorname{D}(x)}{m} \operatorname{mod}(2) = 0 \\ \frac{255}{m}(1 - \operatorname{D}(x) \operatorname{mod}(m)), \text{else} \end{cases}$

where
$$m$$: controls the width of the lanes interval in the feature flow map. $$m = \frac{L_i}{2}$$ in our experiments
4. Vertex optimization

1. CVT approximates a Poisson-disk point distribution that the seeds can cover the space fairly

2. The centroid c of a Voronoi cell is computed as follows:

$c = \frac{\sum_i w_i x_i}{\sum_i w_i}$

where
$$x_i$$: denotes the pixels in the cell
$$w_i$$ the associated weight
5. Constrained triangulation
6. Color post-processing