Консенсус случайной выборки

Консенсус случайной выборки ( RANSAC ) — это итерационный метод оценки параметров математической модели на основе набора наблюдаемых данных, содержащих выбросы , при этом выбросы не должны оказывать никакого влияния на значения оценок. Следовательно, его также можно интерпретировать как метод обнаружения выбросов. Это недетерминированный алгоритм в том смысле, что он дает разумный результат только с определенной вероятностью, причем эта вероятность увеличивается по мере увеличения количества итераций. Алгоритм был впервые опубликован Фишлером и Боллесом в SRI International в 1981 году. Они использовали RANSAC для решения проблемы определения местоположения (LDP), цель которой состоит в том, чтобы определить точки в пространстве, которые проецируются на изображение в набор ориентиров с известные места.

RANSAC использует повторяющуюся случайную подвыборку . Основное предположение состоит в том, что данные состоят из «внутренних значений», т. е. данных, распределение которых можно объяснить некоторым набором параметров модели, хотя и может быть подвержено шуму, и «выбросов», то есть данных, которые не соответствуют модели. Выбросы могут возникать, например, из-за экстремальных значений шума, ошибочных измерений или неверных гипотез об интерпретации данных. RANSAC также предполагает, что при наличии (обычно небольшого) набора исходных данных существует процедура, которая может оценить параметры модели, которая оптимально объясняет или соответствует этим данным.

Пример

Простой пример — подгонка линии в двух измерениях к набору наблюдений. Предполагая, что этот набор содержит как inliers , т. е. точки, которые приблизительно можно подогнать к линии, так и outliers , точки, которые не могут быть подогнаны к этой линии, простой метод наименьших квадратов для подгонки линии обычно дает линию с плохой подгонкой к линии. данные, включая выбросы и выбросы. Причина в том, что он оптимально подходит ко всем точкам, включая выбросы. С другой стороны, RANSAC пытается исключить выбросы и найти линейную модель, которая использует в своих расчетах только выбросы. Это делается путем подгонки линейных моделей к нескольким случайным выборкам данных и возврата модели, которая лучше всего соответствует подмножеству данных. Поскольку вставки, как правило, связаны более линейно, чем случайная смесь вставок и выбросов, случайное подмножество, полностью состоящее из вставок, будет иметь наилучшее соответствие модели. На практике нет никакой гарантии, что подмножество вкладок будет выбрано случайным образом, и вероятность успеха алгоритма зависит от доли вкладок в данных, а также от выбора нескольких параметров алгоритма.

• 
  Набор данных с множеством выбросов, для которого необходимо построить линию.
• 
  Встроенная линия с RANSAC; выбросы не влияют на результат.

Обзор

Алгоритм RANSAC — это метод обучения для оценки параметров модели путем случайной выборки наблюдаемых данных. Учитывая набор данных, элементы данных которого содержат как выбросы, так и выбросы, RANSAC использует схему голосования, чтобы найти оптимальный результат подбора. Элементы данных в наборе данных используются для голосования за одну или несколько моделей. Реализация этой схемы голосования основана на двух предположениях: зашумленные функции не будут последовательно голосовать за какую-либо одну модель (несколько выбросов) и что имеется достаточно функций, чтобы согласовать хорошую модель (немного недостающих данных). Алгоритм RANSAC по существу состоит из двух шагов, которые итеративно повторяются:

1. На первом этапе из входного набора данных случайным образом выбирается выборочное подмножество, содержащее минимальное количество элементов данных. Подходящая модель с параметрами модели рассчитывается с использованием только элементов этого подмножества выборки. Мощность подмножества выборки (например, количество данных в этом подмножестве) достаточна для определения параметров модели.
2. На втором этапе алгоритм проверяет, какие элементы всего набора данных соответствуют модели, созданной с помощью оцененных параметров модели, полученных на первом этапе. Элемент данных будет рассматриваться как выброс, если он не соответствует модели в пределах некоторого порога ошибки, определяющего максимальное отклонение данных для выбросов. (Элементы данных, выходящие за пределы этого отклонения, являются выбросами.)

Набор вкладок, полученных для подходящей модели, называется консенсусным набором . Алгоритм RANSAC будет итеративно повторять два вышеуказанных шага до тех пор, пока полученный консенсусный набор на определенной итерации не будет содержать достаточное количество входных значений.

Входными данными для алгоритма RANSAC является набор значений наблюдаемых данных, модель, соответствующая наблюдениям, и некоторые доверительные параметры, определяющие выбросы. Если говорить более подробно, чем вышеупомянутый обзор алгоритма RANSAC, RANSAC достигает своей цели, повторяя следующие шаги:

1. Выберите случайное подмножество исходных данных. Назовите это подмножество гипотетическими вкладышами .
2. Модель подгоняется к набору гипотетических вкладышей.
3. Затем все данные проверяются на соответствие подобранной модели. Все точки данных (исходных данных), которые хорошо соответствуют оцененной модели, в соответствии с некоторой функцией потерь , специфичной для модели , называются консенсусным набором (т. е. набором вкладок для модели).
4. Предполагаемая модель является достаточно хорошей, если достаточно много точек данных были классифицированы как часть консенсусного набора.
5. Модель можно улучшить, переоценив ее с использованием всех членов консенсусного набора. Качество подгонки как мера того, насколько хорошо модель соответствует согласованному набору, будет использоваться для уточнения подгонки модели по мере продолжения итераций (например, путем установки этого показателя в качестве критерия качества подгонки на следующей итерации).

Чтобы прийти к достаточно хорошему набору параметров модели, эта процедура повторяется фиксированное количество раз, каждый раз приводя либо к отклонению модели, поскольку слишком мало точек входит в консенсусный набор, либо к уточненной модели с согласованным размером набора. больше, чем предыдущий консенсусный набор.

• 
  РАНСАК: Вбросы и выбросы. Линейная аппроксимация точек данных в этом примере осуществляется с помощью 7 вкладок (точки данных хорошо соответствуют модели по некоторым критериям). Это не очень хорошо подходит, поскольку существует линейная линия, рядом с которой распределено большинство точек данных (т. е. больше вставных значений).

Псевдокод

Общий алгоритм RANSAC работает как следующий псевдокод :

Given:
    data – A set of observations.
    model – A model to explain the observed data points.
    n – The minimum number of data points required to estimate the model parameters.
    k – The maximum number of iterations allowed in the algorithm.
    t – A threshold value to determine data points that are fit well by the model (inlier).
    d – The number of close data points (inliers) required to assert that the model fits well to the data.

Return:
    bestFit – The model parameters which may best fit the data (or null if no good model is found).


iterations = 0
bestFit = null
bestErr = something really large // This parameter is used to sharpen the model parameters to the best data fitting as iterations go on.

while iterations < k do
    maybeInliers := n randomly selected values from data
    maybeModel := model parameters fitted to maybeInliers
    confirmedInliers := empty set
    for every point in data do
        if point fits maybeModel with an error smaller than t then
             add point to confirmedInliers
        end if
    end for
    if the number of elements in confirmedInliers is > d then
        // This implies that we may have found a good model.
        // Now test how good it is.
        betterModel := model parameters fitted to all the points in confirmedInliers
        thisErr := a measure of how well betterModel fits these points
        if thisErr < bestErr then
            bestFit := betterModel
            bestErr := thisErr
        end if
    end if
    increment iterations
end while

return bestFit

Пример кода

Реализация Python, отражающая псевдокод. Это также определяет LinearRegressor на основе наименьших квадратов, применяется RANSAC к задаче 2D-регрессии и визуализирует результат:

from copy import copy
import numpy as np
from numpy.random import default_rng
rng = default_rng()


class RANSAC:
    def __init__(self, n=10, k=100, t=0.05, d=10, model=None, loss=None, metric=None):
        self.n = n              # `n`: Minimum number of data points to estimate parameters
        self.k = k              # `k`: Maximum iterations allowed
        self.t = t              # `t`: Threshold value to determine if points are fit well
        self.d = d              # `d`: Number of close data points required to assert model fits well
        self.model = model      # `model`: class implementing `fit` and `predict`
        self.loss = loss        # `loss`: function of `y_true` and `y_pred` that returns a vector
        self.metric = metric    # `metric`: function of `y_true` and `y_pred` and returns a float
        self.best_fit = None
        self.best_error = np.inf

    def fit(self, X, y):
        for _ in range(self.k):
            ids = rng.permutation(X.shape[0])

            maybe_inliers = ids[: self.n]
            maybe_model = copy(self.model).fit(X[maybe_inliers], y[maybe_inliers])

            thresholded = (
                self.loss(y[ids][self.n :], maybe_model.predict(X[ids][self.n :]))
                < self.t
            )

            inlier_ids = ids[self.n :][np.flatnonzero(thresholded).flatten()]

            if inlier_ids.size > self.d:
                inlier_points = np.hstack([maybe_inliers, inlier_ids])
                better_model = copy(self.model).fit(X[inlier_points], y[inlier_points])

                this_error = self.metric(
                    y[inlier_points], better_model.predict(X[inlier_points])
                )

                if this_error < self.best_error:
                    self.best_error = this_error
                    self.best_fit = better_model

        return self

    def predict(self, X):
        return self.best_fit.predict(X)

def square_error_loss(y_true, y_pred):
    return (y_true - y_pred) ** 2


def mean_square_error(y_true, y_pred):
    return np.sum(square_error_loss(y_true, y_pred)) / y_true.shape[0]


class LinearRegressor:
    def __init__(self):
        self.params = None

    def fit(self, X: np.ndarray, y: np.ndarray):
        r, _ = X.shape
        X = np.hstack([np.ones((r, 1)), X])
        self.params = np.linalg.inv(X.T @ X) @ X.T @ y
        return self

    def predict(self, X: np.ndarray):
        r, _ = X.shape
        X = np.hstack([np.ones((r, 1)), X])
        return X @ self.params


if __name__ == "__main__":

    regressor = RANSAC(model=LinearRegressor(), loss=square_error_loss, metric=mean_square_error)

    X = np.array([-0.848,-0.800,-0.704,-0.632,-0.488,-0.472,-0.368,-0.336,-0.280,-0.200,-0.00800,-0.0840,0.0240,0.100,0.124,0.148,0.232,0.236,0.324,0.356,0.368,0.440,0.512,0.548,0.660,0.640,0.712,0.752,0.776,0.880,0.920,0.944,-0.108,-0.168,-0.720,-0.784,-0.224,-0.604,-0.740,-0.0440,0.388,-0.0200,0.752,0.416,-0.0800,-0.348,0.988,0.776,0.680,0.880,-0.816,-0.424,-0.932,0.272,-0.556,-0.568,-0.600,-0.716,-0.796,-0.880,-0.972,-0.916,0.816,0.892,0.956,0.980,0.988,0.992,0.00400]).reshape(-1,1)
    y = np.array([-0.917,-0.833,-0.801,-0.665,-0.605,-0.545,-0.509,-0.433,-0.397,-0.281,-0.205,-0.169,-0.0531,-0.0651,0.0349,0.0829,0.0589,0.175,0.179,0.191,0.259,0.287,0.359,0.395,0.483,0.539,0.543,0.603,0.667,0.679,0.751,0.803,-0.265,-0.341,0.111,-0.113,0.547,0.791,0.551,0.347,0.975,0.943,-0.249,-0.769,-0.625,-0.861,-0.749,-0.945,-0.493,0.163,-0.469,0.0669,0.891,0.623,-0.609,-0.677,-0.721,-0.745,-0.885,-0.897,-0.969,-0.949,0.707,0.783,0.859,0.979,0.811,0.891,-0.137]).reshape(-1,1)

    regressor.fit(X, y)

    import matplotlib.pyplot as plt
    plt.style.use("seaborn-darkgrid")
    fig, ax = plt.subplots(1, 1)
    ax.set_box_aspect(1)

    plt.scatter(X, y)

    line = np.linspace(-1, 1, num=100).reshape(-1, 1)
    plt.plot(line, regressor.predict(line), c="peru")
    plt.show()

Результат запуска RANSAC выполнение. Оранжевая линия показывает параметры метода наименьших квадратов, найденные с помощью итеративного подхода, который успешно игнорирует точки-выбросы.

Параметры

Пороговое значение для определения того, когда точка данных соответствует модели ( t ), и количество вкладок (точек данных, подогнанных к модели в пределах t ), необходимых для подтверждения того, что модель хорошо соответствует данным ( d ), определяются на основе конкретных требований. приложения и набора данных и, возможно, на основе экспериментальной оценки. Однако количество итераций ( k ) можно грубо определить как функцию желаемой вероятности успеха ( p ), как показано ниже.

Пусть p — желаемая вероятность того, что алгоритм RANSAC предоставит хотя бы один полезный результат после запуска. В крайнем случае (для упрощения вывода) RANSAC возвращает успешный результат, если на какой-то итерации он выбирает только входящие значения из набора входных данных, когда он выбирает n точек из набора данных, из которых оцениваются параметры модели. (Другими словами, все выбранные n точек данных являются внутренними элементами модели, оцененной по этим точкам). Позволять $w$ быть вероятностью выбора входного значения каждый раз, когда выбирается одна точка данных, то есть примерно

$w$ = количество вставок в данных / количество точек в данных

Распространенный случай заключается в том, что $w$ заранее неизвестно из-за неизвестного количества вставок в данных перед запуском алгоритма RANSAC, но можно дать некоторое приблизительное значение. При заданном грубом значении $w$ и грубо предполагая, что n точек, необходимых для оценки модели, выбираются независимо (это грубое предположение, поскольку в реальности каждый выбор точки данных уменьшает количество кандидатов на точки данных, которые нужно выбрать при следующем выборе), $w^{n}$ - вероятность того, что все n точек являются вкраплениями и $1-w^{n}$ — это вероятность того, что хотя бы одна из n точек является выбросом, случай, который подразумевает, что плохая модель будет оценена по этому набору точек. Эта вероятность в степени k (количество итераций при запуске алгоритма) представляет собой вероятность того, что алгоритм никогда не выберет набор из n точек, все из которых являются входными, и это то же самое, что $1-p$ (вероятность того, что алгоритм не приведет к успешной оценке модели) в крайнем случае. Следовательно,

$1-p=(1-w^{n})^{k}\,$

что после логарифмирования обеих частей приводит к

$k={\frac {\log(1-p)}{\log(1-w^{n})}}$

Этот результат предполагает, что n точек данных выбираются независимо, то есть точка, которая была выбрана один раз, заменяется и может быть выбрана снова в той же итерации. Зачастую это неразумный подход, и полученное значение k следует принимать в качестве верхнего предела в случае, если точки выбираются без замены. Например, в случае поиска линии, соответствующей набору данных, показанному на рисунке выше, алгоритм RANSAC обычно выбирает две точки на каждой итерации и вычисляет maybe_model как линия между точками, и тогда очень важно, чтобы эти две точки были различны.

Чтобы получить дополнительную уверенность, стандартное отклонение можно добавить к k или его кратные значения . Стандартное отклонение k определяется как

$\operatorname {SD} (k)={\frac {\sqrt {1-w^{n}}}{w^{n}}}$

Преимущества и недостатки

Преимуществом RANSAC является его способность выполнять надежную оценку. параметров модели, т.е. он может оценивать параметры с высокой степенью точности, даже если значительное количество выбросов в наборе данных присутствует . Недостатком RANSAC является отсутствие верхней границы времени, необходимого для вычисления этих параметров (кроме исчерпания ресурсов). Когда количество вычисляемых итераций ограничено, полученное решение может быть неоптимальным и даже не таким, которое хорошо соответствует данным. Таким образом, RANSAC предлагает компромисс; за счет вычисления большего количества итераций вероятность создания разумной модели увеличивается. Более того, RANSAC не всегда может найти оптимальный набор даже для умеренно загрязненных наборов и обычно плохо работает, когда количество вкладок меньше 50%. Оптимальный РАНСАК было предложено решить обе эти проблемы и способно найти оптимальный набор для сильно загрязненных наборов, даже для входного соотношения менее 5%. Еще одним недостатком RANSAC является то, что он требует установки пороговых значений для конкретной проблемы.

RANSAC может оценить только одну модель для определенного набора данных. Что касается любого подхода с одной моделью, когда существуют два (или более) экземпляра модели, RANSAC может не найти ни один из них. Преобразование Хафа — это один из альтернативных методов надежной оценки, который может быть полезен, когда присутствует более одного экземпляра модели. Другой подход к подбору нескольких моделей известен как PEARL. который сочетает в себе выборку модели из точек данных, как в RANSAC, с итеративной переоценкой вложенных значений и подгонкой нескольких моделей, формулируемой как задача оптимизации с глобальной энергетической функцией, описывающей качество общего решения.

Приложения

Алгоритм RANSAC часто используется в компьютерном зрении , например, для одновременного решения задачи соответствия и оценки фундаментальной матрицы , связанной с парой стереокамер; см. также: Структура из движения , преобразование масштабно-инвариантных признаков , сшивание изображений , жесткая сегментация движения .

Развитие и улучшения

С 1981 года RANSAC стал фундаментальным инструментом в области компьютерного зрения и обработки изображений. В 2006 году, к 25-летию алгоритма, на Международной конференции по компьютерному зрению и распознаванию образов (CVPR) был организован семинар, на котором были подведены итоги последних достижений и изменений в исходном алгоритме, в основном предназначенных для повышения скорости алгоритма. , надежность и точность предполагаемого решения, а также уменьшить зависимость от определяемых пользователем констант.

RANSAC может быть чувствителен к выбору правильного порога шума, который определяет, какие точки данных соответствуют модели, созданной с определенным набором параметров. Если такой порог слишком велик, то все гипотезы имеют тенденцию оцениваться одинаково (хорошо). С другой стороны, когда шумовой порог слишком мал, оцениваемые параметры имеют тенденцию быть нестабильными (т.е. при простом добавлении или удалении данных из набора вкраплений оценка параметров может колебаться). Чтобы частично компенсировать этот нежелательный эффект, Torr et al. предложил две модификации RANSAC, названные MSAC (M-оценка SAmple и консенсус) и MLESAC (SAmple и консенсус оценки максимального правдоподобия). Основная идея состоит в том, чтобы оценить качество консенсусного набора (т.е. данных, которые соответствуют модели и определенному набору параметров), вычислив его вероятность (тогда как в исходной формулировке Фишлера и Боллеса ранг представлял собой мощность такого набора). Расширение MLESAC, которое учитывает априорные вероятности, связанные с входным набором данных, предложено Тордоффом. Полученный алгоритм получил название Guided-MLESAC. Аналогичным образом, Чам предложил проводить процедуру выборки в том случае, если известна некоторая априорная информация о входных данных, т.е. может ли исходное значение быть выбросом или выбросом. Предлагаемый подход называется PROSAC, PROgressive SAmple Consensus.

Чам и др. также предложил рандомизированную версию RANSAC под названием R-RANSAC. чтобы уменьшить вычислительную нагрузку для определения хорошего консенсусного набора. Основная идея состоит в том, чтобы первоначально оценить качество модели, созданной в данный момент, используя только сокращенный набор точек вместо всего набора данных. Разумная стратегия с высокой степенью уверенности подскажет, когда необходимо оценить соответствие всего набора данных или когда от модели можно легко отказаться. Разумно предположить, что влияние этого подхода более актуально в тех случаях, когда процент ошибочных результатов велик. Тип стратегии, предложенный Chum et al. называется схемой упреждения. Нистер предложил парадигму под названием Preemptive RANSAC. это позволяет в режиме реального времени надежно оценить структуру сцены и движение камеры. Основная идея подхода состоит в генерации фиксированного количества гипотез, чтобы сравнение происходило по качеству сгенерированной гипотезы, а не по какому-то абсолютному показателю качества.

Другие исследователи пытались справиться со сложными ситуациями, когда масштаб шума неизвестен и/или присутствует несколько экземпляров модели. Первая проблема была решена в работе Ванга и Сутера. Тольдо и др. представлять каждую датум с помощью характеристической функции набора случайных моделей, соответствующих этой точке. Затем несколько моделей раскрываются как кластеры, которые группируют точки, поддерживающие одну и ту же модель. Алгоритм кластеризации, называемый J-linkage, не требует предварительного указания количества моделей и ручной настройки параметров.

RANSAC также был адаптирован для приложений рекурсивной оценки состояния, где входные измерения искажаются выбросами, а подходы с фильтром Калмана , основанные на гауссовом распределении ошибки измерения, обречены на провал. Такой подход получил название КАЛЬМАНСАК.

Связанные методы

• MLESAC (Консенсус выборки оценки максимального правдоподобия) – максимизирует вероятность того, что данные были получены на основе модели, подобранной по выборке, например, смешанной модели выбросов и выбросов.
• MAPSAC (Максимальный консенсус апостериорной выборки) – расширяет MLESAC, включая априорную вероятность подбираемых параметров, и максимизирует апостериорную вероятность.
• КАЛЬМАНСАК – причинный вывод о состоянии динамической системы
• Повторная выборка (статистика)
• Hop-Diffusion Monte Carlo использует рандомизированную выборку, включающую глобальные скачки и локальную диффузию, чтобы выбрать выборку на каждом этапе RANSAC для оценки эпиполярной геометрии между изображениями с очень широкой базой.

См. также

• Преобразование Хафа

Ссылки

• Мартин А. Фишлер и Роберт К. Боллес (июнь 1981 г.). «Консенсус случайной выборки: парадигма подбора модели с применением к анализу изображений и автоматизированной картографии» (PDF) . Комм. АКМ . 24 (6): 381–395. дои : 10.1145/358669.358692 . S2CID   972888 . Архивировано (PDF) из оригинала 10 декабря 2014 г.
• Дэвид А. Форсайт и Жан Понсе (2003). Компьютерное зрение, современный подход . Прентис Холл. ISBN  978-0-13-085198-7 .
• Ричард Хартли и Эндрю Зиссерман (2003). Множественная геометрия в компьютерном зрении (2-е изд.). Издательство Кембриджского университета.
• Струц, Т. (2016). Подбор данных и неопределенность (Практическое введение в метод взвешенных наименьших квадратов и не только) . 2-е издание, Springer Vieweg. ISBN  978-3-658-11455-8 .
• PHS Торр и Д.В. Мюррей (1997). «Разработка и сравнение робастных методов оценки фундаментальной матрицы». Международный журнал компьютерного зрения . 24 (3): 271–300. дои : 10.1023/A:1007927408552 . S2CID   12031059 .
• Ондрей Чум (2005). «Оценка геометрии в двух проекциях с помощью случайной выборки и консенсуса» (PDF) . Кандидатская диссертация .
• Сунглок Чой; Тэмин Ким и Вонпиль Ю (2009). «Оценка производительности семейства RANSAC» (PDF) . В материалах Британской конференции по машинному зрению (BMVC) . Архивировано из оригинала (PDF) 31 августа 2020 г. Проверено 1 октября 2010 г.

• Андерс Хаст; Йохан Нюсё; Андреа Маркетти (2013). «Оптимальный RANSAC - к повторяемому алгоритму поиска оптимального набора» (PDF) . Журнал WSCG . 21 (1): 21–30.
• Хоссам Исак; Юрий Бойков (2012). «Энергетическая геометрическая многомодельная подгонка» (PDF) . Международный журнал компьютерного зрения . 97 (2:1): 23–147. CiteSeerX   10.1.1.381.2434 . дои : 10.1007/s11263-011-0474-7 . S2CID   5461268 .