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)