Chamfer Distance

12/04/2024

• Chamfer Distance
• In computer vision and 3D graphics, Chamfer distance is a distance function that estimates the similarity between two point clouds. For two point clouds $P = \{p_1, p_2, \, ..., \, p_m\}$ and $Q - \{q_1, q_2, \, ..., \, q_n\}$, the chamfer distance is defined as follows: $$\,\\ \text{Chamfer Distance}(P, Q) = \sum_{p \in P} \min_{q \in Q} \|p - q\|^2_2 \,\, + \sum_{q \in Q} \min_{p \in P} \|q - p\|^2_2 \,\\ $$
• The left term computes the distance from each $p$ to the nearest $q$. Specifically, it first finds the minimum distance between $p$ and $Q$, and then adds it to $P$. Since the terms are symmetric, the right term performs the same operation, finding the distance from each $q$ to the nearest $p$ and adding it to $Q$. $$\,\\ \sum_{p \in P} \min_{q \in Q} \|p - q\|^2_2 \,\\ $$


• Normalization term can be added when the point clouds have significant differences in size or density. $$\,\\ \text{Chamfer Distance}(P, Q) = \frac{1}{|P|}\sum_{p \in P} \min_{q \in Q} \|p - q\|^2_2 \,\, + \frac{1}{|Q|}\sum_{q \in Q} \min_{p \in P} \|q - p\|^2_2 \,\\ $$

    import numpy as np


    def chamfer_distance(P, Q, normalize=True):
        """
            >>> P
            array([[1, 2, 3],
                   [4, 5, 6]])
            
            >>> Q
            array([[ 7,  8,  9],
                   [10, 11, 12],
                   [13, 14, 15]])
            )
            
            >>> P[:, None, :] - Q[None, :, :]
            array([[[ -6,  -6,  -6],      P_0 - Q_0
                    [ -9,  -9,  -9],      P_0 - Q_1
                    [-12, -12, -12]],     P_0 - Q_2
    
                    [[ -3,  -3,  -3],     P_1 - Q_0
                     [ -6,  -6,  -6],     P_1 - Q_1
                     [ -9,  -9,  -9]]])   P_1 - Q_2 
    
            >>> norms
            array([[10.39230485, 15.58845727, 20.78460969],
                   [ 5.19615242, 10.39230485, 15.58845727]])
    
                 (    [P_0 - Q_0, P_0 - Q_1, P_0 - Q_2],   )
                 (    [P_1 - Q_0, P_1 - Q_1, P_1 - Q_2],   )
        """
        
        norms = np.linalg.norm(P[:, None, :] - Q[None, :, :], axis=2)
    
        P_to_Q = norms.min(axis=1)
        Q_to_P = norms.min(axis=0)
        
        if normalize:
            return P_to_Q.mean() + Q_to_P.mean()
            
        return P_to_Q + Q_to_P
    
    
    if __name__ == "__main__":
    
        np.random.seed(777)
        
        P = np.random.random((2, 3)).round(1)
        Q = np.random.random((5, 3)).round(1)
        
        d = chamfer_distance(P, Q)