Python scipy.optimize 模块,linear_sum_assignment() 实例源码

我们从Python开源项目中,提取了以下11个代码示例,用于说明如何使用scipy.optimize.linear_sum_assignment()

项目:brainiak    作者:brainiak    | 项目源码 | 文件源码
def _assign_posterior(self):
        """assign posterior to prior based on Hungarian algorithm

        Returns
        -------
        TFA
            Returns the instance itself.
        """

        prior_centers = self.get_centers(self.local_prior)
        posterior_centers = self.get_centers(self.local_posterior_)
        posterior_widths = self.get_widths(self.local_posterior_)
        # linear assignment on centers
        cost = distance.cdist(prior_centers, posterior_centers, 'euclidean')
        _, col_ind = linear_sum_assignment(cost)
        # reorder centers/widths based on cost assignment
        self.set_centers(self.local_posterior_, posterior_centers[col_ind])
        self.set_widths(self.local_posterior_, posterior_widths[col_ind])
        return self
项目:lorelei-speech-evaluation    作者:usc-sail    | 项目源码 | 文件源码
def document_scores(ref,out):
    # create a similarity matrix
    similarity_matrix = np.zeros((len(ref),len(out)))
    for i in range(len(ref)):
        for j in range(len(out)):
            similarity_matrix[i,j] = frame_similarity(ref[i], out[j])

    row_ind, col_ind = linear_sum_assignment(1-similarity_matrix)
    tp = similarity_matrix[row_ind, col_ind].sum()
    fp = len(out) - tp
    fn = len(ref) - tp

    return tp,fp,fn


# create a dictionary where frames are grouped by document id ------------------
项目:lorelei-speech-evaluation    作者:usc-sail    | 项目源码 | 文件源码
def document_scores(ref,out):
    # create a similarity matrix
    similarity_matrix = np.zeros((len(ref),len(out)))
    for i in range(len(ref)):
        for j in range(len(out)):
            similarity_matrix[i,j] = frame_similarity(ref[i], out[j])

    row_ind, col_ind = linear_sum_assignment(1-similarity_matrix)
    tp = similarity_matrix[row_ind, col_ind].sum()
    fp = len(out) - tp
    fn = len(ref) - tp

    return tp,fp,fn


# create a dictionary where frames are grouped by document id ------------------
项目:py-motmetrics    作者:cheind    | 项目源码 | 文件源码
def _sanitize_dists(self, dists):
        """Replace invalid distances."""

        dists = np.copy(dists)

        # Note there is an issue in scipy.optimize.linear_sum_assignment where
        # it runs forever if an entire row/column is infinite or nan. We therefore
        # make a copy of the distance matrix and compute a safe value that indicates
        # 'cannot assign'. Also note + 1 is necessary in below inv-dist computation
        # to make invdist bigger than max dist in case max dist is zero.

        valid_dists = dists[np.isfinite(dists)]
        INVDIST = 2 * valid_dists.max() + 1 if valid_dists.shape[0] > 0 else 1.
        dists[~np.isfinite(dists)] = INVDIST  

        return dists, INVDIST
项目:otRebuilder    作者:Pal3love    | 项目源码 | 文件源码
def min_cost_perfect_bipartite_matching(G):
    n = len(G)
    try:
        from scipy.optimize import linear_sum_assignment
        rows, cols = linear_sum_assignment(G)
        assert (rows == list(range(n))).all()
        return list(cols), _matching_cost(G, cols)
    except ImportError:
        pass

    try:
        from munkres import Munkres
        cols = [None] * n
        for row,col in Munkres().compute(G):
            cols[row] = col
        return cols, _matching_cost(G, cols)
    except ImportError:
        pass

    if n > 6:
        raise Exception("Install Python module 'munkres' or 'scipy >= 0.17.0'")

    # Otherwise just brute-force
    permutations = itertools.permutations(range(n))
    best = list(next(permutations))
    best_cost = _matching_cost(G, best)
    for p in permutations:
        cost = _matching_cost(G, p)
        if cost < best_cost:
            best, best_cost = list(p), cost
    return best, best_cost
项目:brainiak    作者:brainiak    | 项目源码 | 文件源码
def _assign_posterior(self):
        """assign posterior to the right prior based on
           Hungarian algorithm

        Returns
        -------
        HTFA
            Returns the instance itself.
        """

        prior_centers = self.get_centers(self.global_prior_)
        posterior_centers = self.get_centers(self.global_posterior_)
        posterior_widths = self.get_widths(self.global_posterior_)
        posterior_centers_mean_cov =\
            self.get_centers_mean_cov(self.global_posterior_)
        posterior_widths_mean_var =\
            self.get_widths_mean_var(self.global_posterior_)
        # linear assignment on centers
        cost = distance.cdist(prior_centers, posterior_centers, 'euclidean')
        _, col_ind = linear_sum_assignment(cost)
        # reorder centers/widths based on cost assignment
        self.set_centers(self.global_posterior_, posterior_centers)
        self.set_widths(self.global_posterior_, posterior_widths)
        # reorder cov/var based on cost assignment
        self.set_centers_mean_cov(
            self.global_posterior_,
            posterior_centers_mean_cov[col_ind])
        self.set_widths_mean_var(
            self.global_posterior_,
            posterior_widths_mean_var[col_ind])
        return self
项目:SCaIP    作者:simonsfoundation    | 项目源码 | 文件源码
def find_matches(D_s, print_assignment=False):

    matches=[]
    costs=[]
    t_start=time.time()
    for ii,D in enumerate(D_s):
        DD=D.copy()    
        if np.sum(np.where(np.isnan(DD)))>0:
            raise Exception('Distance Matrix contains NaN, not allowed!')


    #    indexes = m.compute(DD)
#        indexes = linear_assignment(DD)
        indexes = linear_sum_assignment(DD)
        indexes2=[(ind1,ind2) for ind1,ind2 in zip(indexes[0],indexes[1])]
        matches.append(indexes)
        DD=D.copy()   
        total = []
        for row, column in indexes2:
            value = DD[row,column]
            if print_assignment:
                print '(%d, %d) -> %f' % (row, column, value)
            total.append(value)      
        print  'FOV: %d, shape: %d,%d total cost: %f' % (ii, DD.shape[0],DD.shape[1], np.sum(total))
        print time.time()-t_start
        costs.append(total)      

    return matches,costs

#%%
项目:qmflows-namd    作者:SCM-NV    | 项目源码 | 文件源码
def swap_forward(overlaps: Tensor3D, swaps: Vector) -> Tensor3D:
    """
    Track all the crossings that happend previous to the current
    time.
    Swap the index i corresponding to the ith Molecular orbital
    with the corresponding swap at time t0.
    Repeat the same procedure with the index and swap at time t1.
    The swaps are compute with the linear sum assignment algorithm from Scipy.
    https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

    """
    for i, mtx in enumerate(np.rollaxis(overlaps, 0)):
        overlaps[i] = mtx[:, swaps][swaps]

    return overlaps
项目:multibox    作者:gvanhorn38    | 项目源码 | 文件源码
def compute_assignments(locations, confidences, gt_bboxes, num_gt_bboxes, batch_size, alpha):
  """
  locations: [batch_size * num_predictions, 4]
  confidences: [batch_size * num_predictions]
  gt_bboxes: [batch_size, max num gt_bboxes, 4]
  num_gt_bboxes : [batch_size]  The number of gt bboxes in each image of the batch
  """

  num_predictions = locations.shape[0] / batch_size
  assignment_partitions = np.zeros(batch_size * num_predictions, dtype=np.int32)
  #stacked_gt_bboxes = []
  stacked_gt_bboxes = np.zeros([0, 4], dtype=np.float32)

  log_confidences = np.log(confidences)
  v = 1. - confidences
  v[v > 1.] = 1.
  v[v <= 0] = SMALL_EPSILON
  log_one_minus_confidences = np.log(v)

  # Go through each image in the batch
  for b in range(batch_size):

    offset = b * num_predictions

    # we need to construct the cost matrix
    C = np.zeros((num_predictions, num_gt_bboxes[b]))
    for j in range(num_gt_bboxes[b]):
      C[:, j] = (alpha / 2.) * (np.linalg.norm(locations[offset:offset+num_predictions] - gt_bboxes[b][j], axis=1))**2 - log_confidences[offset:offset+num_predictions] + log_one_minus_confidences[offset:offset+num_predictions]

    #print C

    # Compute the assignments
    row_ind, col_ind = linear_sum_assignment(C)

    #print row_ind, col_ind

    for r, c in zip(row_ind, col_ind):
      assignment_partitions[offset + r] = 1
      #stacked_gt_bboxes.append(gt_bboxes[b][c])
      gt_box = gt_bboxes[b][c].reshape([1,4])
      stacked_gt_bboxes = np.concatenate((stacked_gt_bboxes, gt_box))

  #stacked_gt_bboxes = np.array(stacked_gt_bboxes).astype(np.float32)
  stacked_gt_bboxes = stacked_gt_bboxes.astype(np.float32)

  return [assignment_partitions, stacked_gt_bboxes]
项目:ramp-workflow    作者:paris-saclay-cds    | 项目源码 | 文件源码
def _match_tuples(y_true, y_pred):
    """
    Given set of true and predicted (x, y, r) tuples.

    Determine the best possible match.

    Parameters
    ----------
    y_true, y_pred : list of tuples

    Returns
    -------
    (idxs_true, idxs_pred, ious)
        idxs_true, idxs_pred : indices into y_true and y_pred of matches
        ious : corresponding IOU value of each match

        The length of the 3 arrays is identical and the minimum of the length
        of y_true and y_pred
    """
    n_true = len(y_true)
    n_pred = len(y_pred)

    iou_matrix = np.empty((n_true, n_pred))

    for i in range(n_true):
        for j in range(n_pred):
            iou_matrix[i, j] = cc_iou(y_true[i], y_pred[j])

    idxs_true, idxs_pred = linear_sum_assignment(1 - iou_matrix)

    if (not idxs_true.size) or (not idxs_pred.size):
        ious = np.array([])
    else:
        ious = iou_matrix[idxs_true, idxs_pred]
    return idxs_true, idxs_pred, ious
项目:qmflows-namd    作者:SCM-NV    | 项目源码 | 文件源码
def track_unavoided_crossings(overlaps: Tensor3D, nHOMO: int) -> Tuple:
    """
    Track the index of the states if there is a crossing using the
    algorithm  described at:
    J. Chem. Phys. 137, 014512 (2012); doi: 10.1063/1.4732536.
    """
    # 3D array containing the costs
    # Notice that the cost is compute on half of the overlap matrices
    # correspoding to Sji_t, the other half corresponds to Sij_t
    nOverlaps, nOrbitals, _ = overlaps.shape

    # Indexes taking into account the crossing
    # There are 2 Overlap matrices at each time t
    indexes = np.empty((nOverlaps + 1, nOrbitals), dtype=np.int)
    indexes[0] = np.arange(nOrbitals, dtype=np.int)

    # Track the crossing using the overlap matrices

    for k in range(nOverlaps):
        # Cost matrix to track the corssings
        logger.info("Tracking crossings at time: {}".format(k))
        cost_mtx_homos = np.negative(overlaps[k, :nHOMO, :nHOMO] ** 2)
        cost_mtx_lumos = np.negative(overlaps[k, nHOMO:, nHOMO:] ** 2)

        # Compute the swap at time t + dt using two set of Orbitals:
        # HOMOs and LUMOS
        swaps_homos = linear_sum_assignment(cost_mtx_homos)[1]
        swaps_lumos = linear_sum_assignment(cost_mtx_lumos)[1]
        total_swaps = np.concatenate((swaps_homos, swaps_lumos + nHOMO))
        indexes[k + 1] = total_swaps

        # update the overlaps at times > t with the previous swaps
        if k != (nOverlaps - 1):  # last element
            k1 = k + 1
            # Update the matrix Sji at time t
            overlaps[k] = swap_columns(overlaps[k], total_swaps)
            # Update all the matrices Sji at time > t
            overlaps[k1:] = swap_forward(overlaps[k1:], total_swaps)
    # Accumulate the swaps
    acc = indexes[0]
    arr = np.empty(indexes.shape, dtype=np.int)
    arr[0] = acc

    # Fold accumulating the crossings
    for i in range(nOverlaps):
        acc = acc[indexes[i + 1]]
        arr[i + 1] = acc

    return overlaps, arr