有向距離場 Signed Distance Filed

摘要

本文主要用於記錄有向距離場的資料

• 添加了可直接使用的Python实现

• 添加了部分资料

• 未完…

最终用Python整了一个脚本方便大家快速CV大法

结果预览

环境

• python3
• openCV
• numpy

# _*_ coding=utf-8 _*_
# MineClever 's 2D SDF Generator~
# 8SSEDT Method

import os, sys
import cv2 as cv2
import numpy as np

# def type
class Vector2 ():
    def __init__(self, x=0,y=0):
        self.data = np.array((x,y),dtype=float)

    @property
    def x (self):
        return self.data[0]

    @x.setter
    def x (self, value):
        self.data[0] = (value)
        
    @property
    def y (self):
        return self.data[1]

    @y.setter
    def y (self, value):
        self.data[1] = (value)

    def __add__ (self, value):
        return Vector2((self.x+value.x),(self.y+value.y))

    def length_squared (self) -> float:
        return (self.x*self.x + self.y*self.y)
        # return np.square(self.data)
    
    def length (self) -> float:
        return np.sqrt(self.length_squared())
    
# For a bitmap with representation:
# [0][0][0]
# [0][1][1]
# [1][1][1]

# using relative offset [offset x, offset y] :
# [-1,-1][0,-1][1,-1]
# [-1, 0][0, 0][1, 0]
# [-1, 1][0, 1][1, 1]

class SSEDT8 (object):

    class Grid ():
        
        def __init__(self, width:int , height:int):  
            self.width = width
            self.height = height
            self.size = Vector2(self.width,self.height)
            self.distances = [Vector2(0,0)]* (self.width*self.height)

        def __str__ (self):
            return "width:{},height:{}".format(self.size.x, self.size.y)
        
        def has (self, x:int, y:int) -> bool:
            return (0 <= x and x < self.size.x and 0 <= self.size.y and y < self.size.y)

        def _index (self, x:int, y:int) -> int:
            # print ("x : {}, y: {}".format(x,y))
            return int(y * self.size.x + x)

        
        def get_size(self) -> Vector2:
            return self.size

        def get_dist(self, x:int, y:int) -> Vector2:
            # print (self._index(x,y))
            return self.distances[self._index(x,y)]

        def set_dist(self, x:int, y:int, p_dinstance:Vector2) :
            self.distances[self._index(x,y)] = p_dinstance

        def update (self, x:int, y:int, offset:Vector2):
            pos = Vector2(x,y)
            offset_pos = pos + offset
            distance = self.get_dist(x, y)
            dist_sq = distance.length_squared()
            
            if (self.has(offset_pos.x, offset_pos.y)):
                offset_dist = self.get_dist(offset_pos.x, offset_pos.y) + offset
                offset_sq = offset_dist.length_squared()
                if (offset_sq < dist_sq):
                    self.set_dist(x, y, offset_dist)


    @classmethod
    def apply_offsets (cls, p_grid : Grid,x :int ,y :int, p_offsets:list):
        size = len(p_offsets)
        for i in range(size):
            p_grid.update(x,y,p_offsets[i])
    
    @classmethod
    def apply_pass (cls, p_grid : Grid, p_offsets1 : list, p_offsets2 : list, inverted=False):
        grid_size = p_grid.get_size()
        width = grid_size.x
        height = grid_size.y
        if (inverted):
            y = height - 1
            x = width - 1
            while (y > 0):
                while (x >= 0):
                    cls.apply_offsets(p_grid, x, y, p_offsets1)
                    x -= 1
                # else:
                #     x = 0
                while (x < width):
                    cls.apply_offsets(p_grid, x, y, p_offsets2)
                    x += 1
                y -= 1
        else:
            y = 0
            x = 0
            while (y < height) :
                while (x < width):
                    cls.apply_offsets(p_grid, x, y, p_offsets1)
                    x += 1
                else:
                    x = width - 1
                while (x > 0):
                    cls.apply_offsets(p_grid, x, y, p_offsets2)
                    x -= 1
                y += 1

        

    @staticmethod
    def _bind_methods():
        pass

    @classmethod
    def do_sdf (cls, p_input_image_path='',p_output_image_path='',p_max_img_size = 1024, p_px_scale = 0.025):
        # read img by openCV
        img = cv2.imread(p_input_image_path,cv2.IMREAD_UNCHANGED)

        width = img.shape[0]
        height = img.shape[1]
        max_len = height if height > width else width
        print (img.shape)
        
        if max_len > p_max_img_size:
            print("do scale")
            scale_fac = p_max_img_size / max_len
            print (scale_fac)
            img = cv2.resize(img,dsize=(int(width*scale_fac) , int(height* scale_fac)),interpolation=cv2.INTER_LANCZOS4)
            width = img.shape[0]
            height = img.shape[1]
        
        cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
        print (img.shape)
        
        # Initialise grids
        grid1 = cls.Grid(width,height)
        grid2 = cls.Grid(width,height)
        DISTANT = 999999

        for y in range(height):
            for x in range(width):
                img_pixel = img[x][y][2] / 255 # convert 255 -> 1.0
                distance = 0 if img_pixel > 0.5 else DISTANT
                grid1.set_dist(x, y, Vector2(distance, distance))
                substract_dist = DISTANT - distance
                grid2.set_dist(x, y, Vector2(substract_dist, substract_dist))


        # using relative offset [offset x, offset y] :
        # [-1,-1][0,-1][1,-1]
        # [-1, 0][0, 0][1, 0]
        # [-1, 1][0, 1][1, 1]
        
        # Pass 1

        # [2] [1] [ ]
        # [0] [ ] [ ]
        # [3] [ ] [ ]
        offsets1 = list()
        offsets1.append(Vector2(-1, 0))     # 0
        offsets1.append(Vector2(0, -1))     # 1
        offsets1.append(Vector2(-1, -1))    # 2 
        offsets1.append(Vector2(1, -1))     # 3
        
        # [ ] [ ] [ ]
        # [ ] [ ] [0]
        # [ ] [ ] [ ]
        offsets2 = list()
        offsets1.append(Vector2(1, 0))      # 0
        
        cls.apply_pass(grid1 , offsets1 ,offsets2 ,False)
        cls.apply_pass(grid2 , offsets1 ,offsets2 ,False)

        # Pass 2

        # [ ] [ ] [ ]
        # [ ] [ ] [0]
        # [2] [1] [3]
        offsets1.clear()
        offsets1.append(Vector2(1, 0))  # 0
        offsets1.append(Vector2(0, 1))  # 1
        offsets1.append(Vector2(-1, 1)) # 2
        offsets1.append(Vector2(1, 1))  # 3

        # [ ] [ ] [ ]
        # [0] [ ] [ ]
        # [ ] [ ] [ ]
        offsets2.clear()
        offsets2.append(Vector2(-1, 0)) # 0

        cls.apply_pass(grid1 , offsets1 ,offsets2 ,True)
        cls.apply_pass(grid2 , offsets1 ,offsets2 ,True)
        
        # make Img data
        out_img = np.zeros((width,height),dtype=np.float16)
        # print(out_img.shape)
        for y in range(height):
            for x in range(width):
                distance1 = grid1.get_dist(x, y)
                distance2 = grid2.get_dist(x, y)
                distance = distance2.length() - distance1.length()
                distance = (1 + max(-1, min(distance * p_px_scale, 1))) / 2.0
                out_img[x][y] = distance

        out_img_scaled = np.clip(out_img *255,0,255).astype('uint8')

        cv2.imwrite(p_output_image_path,out_img_scaled)
        

收集的距離場算法與實現

欧几里得距离转换（EDT）算法

• Ref : https://blog.csdn.net/tianwaifeimao/article/details/45078661

*0 前言*

欧几里得距离转换 (Euclidean Distance Transform, EDT) 简单的说即是以最常用的欧几里得距离作为

距离度量，找到每一个前景点到最近的背景点之间的距离。文中提及所有的算法中，均是将二维图片

转为两个一维向量的方式进行。

一些基本定义：

• 背景点为 0，黑色，为感兴趣点，Voronioi elements，sites；

• 前景点为 1：白色；

• VR:  某一背景点的 VR 指的前景点集合，这些前景点到此背景点的距离比到其他背景点距离都要短。

• VS：某一前景点的 VS 指的是背景点的集合，这些背景点到此前景点距离比到其他前景点距离都要短。

1. Saito 的算法：

step1：1-D Transformation

上到下，计算每一行中前景点到本行背景点距离最近的平方，得到中间结果 G；公式如下：

如下图 :

(a) 为原图

(b) 为 同一行的距离平方图, 即 G

step2：2-D Transformation

从左到右，对每一列，对中间结果 G 进行操作，计算本列背景点与本行背景点距离平方和的最小值，得到距离图（Distance Map）H；

如下图（4 即使最近距离的平方）.

8SSEDT 算法

Ref : https://github.com/Lisapple/8SSEDT

8點有向按序 歐幾里得距離轉換

---

有向距離場 (SDF) 是由二值圖像 計算得來, 在每像素上 , 到最近像素的有向距離(可正可負) 有不同值. 前景像素為正距離 , 背景像素為負距離. 下文中, 有向和有符號是統一意思. 有符號更加符合寫程式的觀點.

例:

每像素會擁有一個距離值:

(暗灰色像素為正值 && 負值為亮灰色)

簡單位圖為例

对于 位图 表示為:

[0][0][0]
[0][1][1]
[1][1][1]

限定全部 0 顯示為像素在 (白色) 形狀之外(也叫:背景)且全部 1 在形狀之内 (也叫:前景).

最終結果表示為:

[-2][-1][-1]
[-1][ 1][ 1]
[ 1][ 2][ 2]

• 第一個像素 (背景) 為 在一個到前景為 -2 (此時為 有向-平方) 的距離.

• 最後一個像素 (前景) 為在一個到背景為 1 的距離.

構建初始網格

For each pixel, we need to build a first grid (grid #1) with a distance duet (dx, dy)

like (dx=0, dy=0) if inside (foreground) and (dx=∞, dy=∞) if outside (background)

[∞][∞][∞]
[∞][0][0]
[0][0][0]

with (0, 0) represented by 0 and (∞, ∞) by ∞.

and a second grid (grid #2) with inverted distances:

[0][0][0]
[0][∞][∞]
[∞][∞][∞]

Note: All pixel out of bounds are use the value (∞, ∞) as:

∞  ∞  ∞ 
∞ [x][∞]
∞ [∞][0]

• Computing grids:

To get the distance x, we look all neighbours (from #1 to #8) distances:

[#1][#2][#3]
[#4][ x][#5]
[#6][#7][#8]

using relative offset [offset x, offset y] to x like so:

[-1,-1][0,-1][1,-1]
[-1, 0][0, 0][1, 0]
[-1, 1][0, 1][1, 1]

then the final value of x is

x = min(#0.distance, ..., #7.distance)

using the distance function that compute the magnitude of the distance with offset:

#?.distance = sqrt( (?dx + offset x)^2 + (?dy + offset y)^2 )

This gives:

#1.distance = (∞-1, ∞-1).distance = √(∞^2 + ∞^2) = ∞
#2.distance = (∞+0, ∞-1).distance = √(∞^2 + ∞^2) = ∞
#3.distance = (∞+1, ∞-1).distance = √(∞^2 + ∞^2) = ∞
#4.distance = (∞-1, ∞+0).distance = √(∞^2 + ∞^2) = ∞
#5.distance = (0+1, 0+0).distance = √(1^2 + 0^2) = 1
#6.distance = (0-1, 0+1).distance = √(-1^2 + 1^2) = √2
#7.distance = (0+0, 0+1).distance = √(0^2 + 1^2) = 1
#8.distance = (0+1, 0+1).distance = √(1^2 + 1^2) = √2

so

x = min(#0.distance, ..., #7.distance]) = 1

• Updated grid:

[∞][∞][∞]
[∞][1][0]
[0][0][0]

Then process the next cell on the right.

Computing method

In total 4 passes are necessary to compute all distances, two sequential passes, for each grid #1 and #2.

Using the initialised grid:

(from left to right, top to bottom)

   - - - >
| [?][?][?]
| [?][x][ ]
v [ ][ ][ ]

then (using the same grid)

(from right to left)

   < - - -
| [ ][ ][ ]
| [ ][x][?]
v [ ][ ][ ]

then

(from right to left, bottom to top)

   < - - -
^ [ ][ ][ ]
| [ ][x][?]
| [?][?][?]

then:

(from left to right)

   - - - >
^ [ ][ ][ ]
| [?][x][ ]
| [ ][ ][ ]

Computing final signed distances

Once the four steps applied on the grid #1 and #2,
we compute the difference of the magnitude of each cell (pixel) #n1 and #n2 of the two grids:

foreach (#n1 of grid #1) and (#n2 of grid #2):
	final distance = #n1.distance - #n2.distance

with #n.distance = sqrt( #n.dx * #n.dx + #n.dy * #n.dy ).

References

Distance field generator with C++ and SDL codersnotes.com

Valve paper on distance field Improved Alpha-Tested Magnification for Vector Textures and Special Effects

3D有符号距离场原理及实现

Ref: http://www.bimant.com/blog/signed-distance-field-implementation/

Dead Reckoning 算法

Ref : https://segmentfault.com/a/1190000041250697

在Unity的實現

Ref : https://zznewclear13.github.io/posts/calculate-signed-distance-field-using-compute-shader/

---