def _calculate_gumbel_poly(lx: np.ndarray, alpha: float, d: int, method: str, log: bool):
    """Inner function that does the actual Gumbel polynomial calculation"""
    k = np.arange(d) + 1

    if method == 'pois':
        n = len(lx)
        x = np.exp(lx)  # n x 1 vector

        lppois = np.array([poisson.logcdf(d - k, xx) for xx in x]).T  # d x n matrix
        llx = k.reshape(-1, 1) @ lx.reshape(1, -1)  # d x n matrix
        labs_poch = np.array([np.sum(np.log(np.abs(alpha * j - (k - 1)))) for j in k])
        lfac = gammaln(k + 1)  # d x 1 vector

        lxabs = llx + lppois + np.tile(labs_poch - lfac, (n, 1)).T + np.tile(x, (d, 1))

        signs = sign_ff(alpha, k, d)
        offset = np.max(lxabs, 0)
        sum_ = np.sum(signs[:, None] * np.exp(lxabs - offset[None, :]), 0)
        res = np.log(sum_) + offset

        return res if log else np.exp(res)
    elif method in ('direct', 'log', 'sort'):
        log_a_dk = gumbel_coef(d, alpha, method, True)

        log_x = log_a_dk[:, None] + k.reshape(-1, 1) @ lx.reshape(1, -1)
        x = np.exp(log_x).sum(0)
        return np.log(x) if log else x
    else:
        raise ValueError(f"Unknown <method>: {method}. Use one of pois, direct, log, sort")

def calc_metric(candidate_img_blurred: np.ndarray, candidate_kpts: np.ndarray, candidate_length: int,
url_img_blurred: np.ndarray, url_kpts: np.ndarray, url_length: int, kpt_pos: tuple) -> float:
    candidate_kpts, url_kpts = serial.deserialize_keypoints(candidate_kpts), serial.deserialize_keypoints(url_kpts)
    m, n = kpt_pos[0], kpt_pos[1]
    #print((m,n))
    if(m == -1):
        return 1
    candidate_img_blurred, url_img_blurred = image.adjust_size(candidate_img_blurred, url_img_blurred)
    c_x, c_y = candidate_img_blurred.shape
    u_x, u_y = url_img_blurred.shape
    x, y = np.array(candidate_kpts[n].pt) - np.array(url_kpts[m].pt)
    if(x + c_x < 0 or x + u_x < 0):
        return 1
    if(y + c_y < 0 or y + u_y < 0):
        return 1
    candidate_img_blurred = image.align_text(candidate_img_blurred, (int(x), int(y)))
    candidate_img_blurred, url_img_blurred =  candidate_img_blurred.astype(int), url_img_blurred.astype(int)
    img_diff = abs(candidate_img_blurred - url_img_blurred)
    img_diff = img_diff.astype(int)
    divisor = max(candidate_img_blurred.size, url_img_blurred.size)
    diff = len(np.where(img_diff > 10)[0]) / float(divisor)
    return diff
    penalty = abs((float(candidate_length) - url_length)) / max(candidate_length, url_length)
    diff = diff / (1.0 - penalty * 10)
    return abs(diff)
       

def get_statistics(matrix: np.ndarray, masktotal: Union[np.ndarray, int, None],
                   mask: Union[np.ndarray, int, None] = None) -> Dict:
    """Calculate different statistics of a detector image, such as sum, max,
    center of gravity, etc."""
    assert (isinstance(matrix, np.ndarray))
    if mask is None:
        mask = 1
    if masktotal is None:
        masktotal = 1
    assert isinstance(masktotal, np.ndarray) or isinstance(masktotal, int)
    assert isinstance(mask, np.ndarray) or isinstance(mask, int)
    result = {}
    matrixorig = matrix
    for prefix, mask in [('total_', masktotal), ('', mask)]:
        matrix = matrixorig * mask
        x = np.arange(matrix.shape[0])
        y = np.arange(matrix.shape[1])
        result[prefix + 'sum'] = matrix.sum()
        result[prefix + 'max'] = matrix.max()
        result[prefix + 'beamx'] = (matrix * x[:, np.newaxis]).sum() / result[prefix + 'sum']
        result[prefix + 'beamy'] = (matrix * y[np.newaxis, :]).sum() / result[prefix + 'sum']
        result[prefix + 'sigmax'] = (
                                        (matrix * (x[:, np.newaxis] - result[prefix + 'beamx']) ** 2).sum() /
                                        result[prefix + 'sum']) ** 0.5
        result[prefix + 'sigmay'] = (
                                        (matrix * (y[np.newaxis, :] - result[prefix + 'beamy']) ** 2).sum() /
                                        result[prefix + 'sum']) ** 0.5
        result[prefix + 'sigma'] = (result[prefix + 'sigmax'] ** 2 + result[prefix + 'sigmay'] ** 2) ** 0.5
    return result

def std_dev_contrast_stretch(arr: np.ndarray, n=2):
    """ Performs a contrast stretch from +/-2σ around the mean to 
        -1 to 1. 
        """
    sigma = arr.std()*n
    m = arr.mean()
    return np.interp(arr,[m-sigma,m+sigma],[-1,1])

def create_binary_confusion_matrix(
    truth_binary_values: np.ndarray, prediction_binary_values: np.ndarray, name=None
) -> pd.Series:
    # This implementation is:
    # ~30x faster than sklearn.metrics.confusion_matrix
    # ~25x faster than sklearn.metrics.confusion_matrix(labels=[False, True])
    # ~6x faster than pandas.crosstab
    truth_binary_values = truth_binary_values.ravel()
    prediction_binary_values = prediction_binary_values.ravel()

    truth_binary_negative_values = 1 - truth_binary_values
    test_binary_negative_values = 1 - prediction_binary_values

    true_positive = np.sum(np.logical_and(truth_binary_values, prediction_binary_values))
    true_negative = np.sum(
        np.logical_and(truth_binary_negative_values, test_binary_negative_values)
    )
    false_positive = np.sum(np.logical_and(truth_binary_negative_values, prediction_binary_values))
    false_negative = np.sum(np.logical_and(truth_binary_values, test_binary_negative_values))

    # Storing the matrix as a Series instead of a DataFrame makes it easier to reference elements
    # and aggregate multiple matrices
    cm = pd.Series(
        {'TP': true_positive, 'TN': true_negative, 'FP': false_positive, 'FN': false_negative},
        name=name,
    )

    return cm

def stretch(array: np.ndarray, min: int=0, max: int=1, fill_dtype=None) -> np.array:
    """'Stretch' the profile to the fit a new min and max value and interpolate in between.
    From: http://www.labri.fr/perso/nrougier/teaching/numpy.100/  exercise #17

    Parameters
    ----------
    array: numpy.ndarray
        The numpy array to stretch.
    min : number
        The new minimum of the values.
    max : number
        The new maximum value.
    fill_dtype : numpy data type
        If None (default), the array will be stretched to the passed min and max.
        If a numpy data type (e.g. np.int16), the array will be stretched to fit the full range of values
        of that data type. If a value is given for this parameter, it overrides ``min`` and ``max``.
    """
    new_max = max
    new_min = min
    if fill_dtype is not None:
        try:
            di = np.iinfo(fill_dtype)
        except ValueError:
            di = np.finfo(fill_dtype)
        new_max = di.max
        new_min = di.min
    # perfectly normalize the array (0..1)
    stretched_array = (array - array.min())/(array.max() - array.min())
    # stretch normalized array to new max/min
    stretched_array *= new_max
    stretched_array += new_min
    return stretched_array.astype(array.dtype)

    def __call__(self, data: np.ndarray, learning_rate: float =1.0,
                 steps: int =1000, db: bool =True) -> List[float]:
        """ `Learn` the parameters of best fit for the given data and model """

        _min = data.min()
        _max = data.max()

        # scale amplitude to [0, 1]
        self.data = (data - _min) / (_max - _min)

        self.cubeX, self.cubeY = data.shape
        self.learning_rate = learning_rate
        self.steps = steps

        # perform the fit
        result = self.simplefit()

        # unscale amplitude of resultant
        result[0] = result[0] * (_max - _min) + _min

        result_as_list = result.tolist()

        self._counter += 1

        return result_as_list

def calculate_potentials(
    r: np.ndarray, potential_law=lenard_jones_potential, out=None, *args, **kwargs
):
    """

    Parameters
    ----------
    r :
        Nx3 array of particle positions
    args :
    kwargs :
        passed along to the force law

    Notes
    -----
    1. get a NxNx3 antisymmetric (upper triangular) matrix of vector distances
    2a. from 1 get a normalized NxNx3 antisymmetric (matrix of direction vectors
    2b. from 1 get a NxN (upper triangular due to symmetry) matrix of scalar distances
    3b. get a NxN matrix of force magnitudes (reshapable to
    3. multiply 2a by 3b to get forces
    4. update existing force matrix

    Returns
    -------

    """
    # TODO optimize with upper triangular matrix
    N = r.shape[0]
    rij = r.reshape(N, 1, 3) - r.reshape(1, N, 3)
    distances_ij = np.sqrt(np.sum(rij ** 2, axis=2, keepdims=True))
    distances_ij[np.arange(N), np.arange(N), :] = np.inf
    potentials = potential_law(distances_ij, *args, **kwargs)
    return potentials.sum() / 2

    def compute_statistics(self, sample: np.ndarray) -> Tuple:
        """
        Computes mean and variance of a sample

        :param sample: A sample to compute statistics for.
        :return: A tuple (mean, variance).
        """
        return sample.mean(), sample.var()

def logsumexp_double_complement(a: np.ndarray, rel_tol: float = 1e-3) -> float:
    """Calculates the following expression in a numerically stable fashion:

        log(1 - (1 - exp(a_0)) x (1 - exp(a_1)) x ...)

    where a_i are the entries of `a` and assumed to be non-positive. The algorithm is as follows:

    We define:

        exp(x_n) = 1 - \prod_{i=0}^n (1 - exp(a_n)),

    Thus, we have x_0 = a_0 and the recursion relation:

        exp(x_{n+1}) = exp(x_n) + exp(b_{n+1}),

    where

        b_{n+1} = a_{n+1} + log(1 - exp(x_n)).

    We sort `a` in the descending order and update `x` term by term. It is easy to show that x_{n} is monotonically
    increasing and that |x_{N} - x_{n}| < (N - n) |x_{n} - x_{n-1}|. We use the last inequality to bound the error
    for early stopping.

    Args:
        a: a float array
        rel_tol: relative error tolerance for early stopping of calculation

    Returns:
        a float scalar
    """
    try:
        assert isinstance(a, np.ndarray)
        a = np.asarray(a.copy(), dtype=np.float)
    except AssertionError:
        try:
            a = np.asarray(a, dtype=np.float)
        except ValueError:
            raise ValueError("The input argument must be castable to a float ndarray.")
    assert len(a) > 0
    assert 0. <= rel_tol < 1.0

    # enforce all entries of a to be negative or zero
    a[a > 0.] = 0.

    if len(a) == 1:
        return np.asscalar(a)
    else:
        a = np.sort(a.flatten())[::-1]
        x = a[0]
        sz = len(a)
        for i, entry in enumerate(a[1:]):
            x_new = np.logaddexp(x, entry + logp_complement(x))
            if np.abs(x_new - x) * (sz - i - 1) < rel_tol * np.abs(x):
                return x_new
            else:
                x = x_new
        return x

def masks(mask: np.ndarray) -> Sequence[np.ndarray]:
    masks = [mask]
    mask2 = mask.copy()
    mask2[0, 0, 0] = 1
    masks.append(mask2)
    mask3 = mask.copy()
    mask3[2, 2, 2] = 0
    masks.append(mask3)
    return masks

 def norm_image(self, arr: np.ndarray):
     """
     将一个numpy数组正则化（0~255）,并转成np.uint8类型
     :param arr: 要处理的numpy数组
     :return: 值域在0~255之间的uint8数组
     """
     if not arr.min() == arr.max():
         arr = (arr - arr.min()) / (arr.max() - arr.min()) * 255
     return np.array(arr, dtype=np.uint8)

def convert_data_to_format(data: np.ndarray, filename: str):
    if filename.endswith(".wav"):
        return (data.view(np.float32) * 32767).astype(np.int16)
    elif filename.endswith(".complex16u") or filename.endswith(".cu8"):
        return (127.5 * (data.view(np.float32) + 1.0)).astype(np.uint8)
    elif filename.endswith(".complex16s") or filename.endswith(".cs8"):
        return (127.5 * ((data.view(np.float32)) - 0.5 / 127.5)).astype(np.int8)
    else:
        return data

def new_ink(X: np.ndarray, Y: np.ndarray, degree: int, a: int = -3) -> np.ndarray:
    assert _is_integer(degree) and degree > 0, "Degree must be positive integer"
    assert isinstance(X, np.ndarray) and isinstance(Y, np.ndarray), "X and Y must be numpy arrays"
    if len(X.shape) == 1:
        X = X.reshape(1, X.shape[0])
    if len(Y.shape) == 1:
        Y = Y.reshape(1, Y.shape[0])
    X[X < a] = a
    Y[Y < a] = a
    return new_K(X, Y, degree, a) / new_K_norm(X, Y, degree, a)

def save_pfm_texture(filename: str, tex: np.ndarray):
    if tex.dtype != np.float32:
        print('Input is not 32 bit precision: converting to 32 bits.')
        tex = tex.astype(np.float32)
    height, width = tex.shape[0], tex.shape[1]
    with open(filename, 'wb+') as f:
        f.write('{}\n'.format(HEADER_MAGIC).encode())
        f.write('{} {}\n'.format(width, height).encode())
        f.write('-1.0\n'.encode())
        f.write(tex.tobytes())

def ink(x: np.ndarray, y: np.ndarray, degree: int, a: int = -3) -> np.ndarray:
    assert _is_integer(degree) and degree > 0, "Degree must be positive integer"
    assert isinstance(x, np.ndarray) and isinstance(y, np.ndarray), "X and Y must be numpy arrays"
    if len(x.shape) == 1:
        x = x.reshape(1, x.shape[0])
    if len(y.shape) == 1:
        y = y.reshape(1, y.shape[0])
    x[x < a] = a
    y[y < a] = a
    return K(x, y, degree, a) / np.sqrt(K_norm(x, y, degree, a, "x") * K_norm(x, y, degree, a, "y"))

def c_int_ext(k: int, aff: np.ndarray, adj_mat: np.ndarray, threads_nb=1) -> float:
    """
    This function calculates the inter/intra-cluster density
    as defined in Santo Fortunato, Community Detection in Graphs, Physics Reports, 486, 75-174(2010)
    Parameters
    ----------
    k : int
        The number of clusters
    aff : np.ndarray
        A 1-D array contains the affectation of nodes to their clusters
    adj_mat : np.ndarray
        Adjacency matrix
    Returns
    -------
    float, float
        The value of sum(sigma_int), sum(sigma_ext)
        which is the quality of the clustering.
    """
    global int_sigmas
    global ext_sigmas
    # initiate to zeros
    int_sigmas = np.zeros(k)
    ext_sigmas = np.zeros(k)
    # Get the number of nodes
    n = len(aff)
    # Calculates the internal and external edges
    # for each cluster
    threads = []  # type: list[Thread]
    # if threads number is too large then update it
    if n / 10 < threads_nb:
        threads_nb = int(n / 10)
    # create threads instances
    for i in range(threads_nb):
        from_i = int(i * (n / threads_nb))
        to_i = int((i + 1) * (n / threads_nb))
        t = Thread(target=calculate_int_ext_edges, args=(adj_mat, aff, from_i, to_i))
        threads.append(t)
        threads[i].start()
    # Wait fo threads to finish
    for t in threads:
        t.join()
    # Transform aff from np.ndarray to list
    # to be able to use the count function
    aff = aff.tolist() # type: list
    # Calculates the density for each cluster
    for i in range(k):
        nb_c_i = aff.count(i)
        if nb_c_i <= 1:
            int_sigmas[i] = 0
            ext_sigmas[i] = 0
        else:
            int_sigmas[i] /= (nb_c_i * (nb_c_i - 1) / 2)
            ext_sigmas[i] /= (nb_c_i * (n - nb_c_i))
    # Return the density for all the clusters
    return sum(int_sigmas) / k, sum(ext_sigmas) / k

    def __init__(self, train_x: np.ndarray, train_y: np.ndarray, features_name=None, do_standardization=True):
        # ensure that train_y is (N x 1)
        train_y = train_y.reshape((train_y.shape[0], 1))
        self.train_x = train_x
        self._raw_train_x = train_x.copy()
        self._raw_train_y = train_y.copy()
        self.train_y = train_y
        self.features_name = features_name

        self.do_standardization = do_standardization
        self._x_std_ = None
        self._x_mean_ = None

    def __init__(self, name: str, values: np.ndarray, gradients: np.ndarray):
        values = np.asarray(values)
        gradients = np.asarray(gradients)
        if values.shape != gradients.shape:
            raise ValueError("Parameter values and gradients must be the same shape")
        self.shape = values.shape
        self.name = name

        self.parameters = [Parameter(self.name, idx, value, gradient, Delta())
                           for idx, value, gradient in
                           zip(range(values.size), values.flatten(), gradients.flatten())]

        self.parameter_map = {p.name: p for p in self.parameters}

def check_for_winner(board: np.ndarray) -> int:
    """Who's won? If 3 then X has won if -3, O"""

    # Do a sum along 3 vertical + 3 horizontal + 2 diagonals
    sums_list = []
    vertical_sum = board.sum(axis=0)
    sums_list.append(vertical_sum[np.argmax(abs(vertical_sum))])

    horiz_sum = board.sum(axis=1)
    sums_list.append(horiz_sum[np.argmax(abs(horiz_sum))])

    sums_list.append(board[0, 0] + board[1, 1] + board[2, 2])
    sums_list.append(board[0, 2] + board[1, 1] + board[2, 0])

    return sums_list[np.argmax(np.abs(sums_list))]