我们从Python开源项目中，提取了以下11个代码示例，用于说明如何使用scipy.optimize.linear_sum_assignment()。
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
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 ------------------
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
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
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
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 #%%
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
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]
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
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
