यादृच्छिक नमूना सर्वसम्मति

रैंडम सैंपल कंसेंसस (RANSAC) अवलोकन किए गए डेटा के एक सेट से गणितीय मॉडल के पैरामीटर का अनुमान लगाने की एक पुनरावृत्तीय विधि है, जिसमें आउटलेर्स सम्मिलित होते हैं, जब आउटलेर्स को अनुमानों के मानों पर कोई प्रभाव नहीं दिया जाता है। इसलिए, इसकी व्याख्या एक आउट्लाइअर डिटेक्शन मेथड के रूप में भी की जा सकती है। यह इस अर्थ में एक डेटर्मीनिस्टिक एल्गोरिदम है कि यह केवल एक निश्चित संभावना के साथ एक उचित परिणाम उत्पन्न करता है, जैसे-जैसे अधिक पुनरावृत्तियों की अनुमति दी जाती है, यह संभावना बढ़ती जाती है। एल्गोरिथ्म को पहली बार 1981 में एसआरआई इंटरनेशनल में फिशलर और बोल्स द्वारा प्रकाशित किया गया था। उन्होंने लोकेशन डेटर्मिनेशन प्रॉब्लम (LDP) को हल करने के लिए आरएएनएसएसी का उपयोग किया, जहां लक्ष्य समष्टि में उन बिंदुओं को निर्धारित करना है जो एक इमेज पर ज्ञात स्थानों के साथ स्थलों के सेट में प्रोजेक्ट करते हैं।

आरएएनएसएसी रेपेटेड रैंडम सब-सैंपलिंग का उपयोग करता है। एक बुनियादी धारणा यह है कि डेटा में "इनलियर्स" होते हैं, अर्थात, डेटा जिसका डिस्ट्रीब्यूशन मॉडल पैरामीटर के कुछ सेट द्वारा समझाया जा सकता है, हालांकि नॉइज़ के अधीन हो सकता है और जो "आउटलेयर" डेटा हैं जो मॉडल में फिट नहीं होते हैं। आउटलेर्स, उदाहरण के लिए, नॉइज़ के चरम मानों से या गलत माप या डेटा की व्याख्या के बारे में गलत परिकल्पनाओं से आ सकते हैं। आरएएनएसएसी यह भी मानता है कि, इनलियर्स के (सामान्यतः छोटे) सेटों को देखते हुए, एक ऐसी प्रक्रिया उपस्थित है जो एक मॉडल के पैरामीटर का अनुमान लगा सकती है जो इस डेटा को इष्टतम रूप से समझाती है या फिट करती है।

उदाहरण

एक सरल उदाहरण अवलोकनों के एक सेट में दो आयामों में एक लाइन को फिट करना है। यह मानते हुए कि इस सेट में दोनों इनलियर्स सम्मिलित हैं, अर्थात, बिंदु जो लगभग एक रेखा पर फिट किए जा सकते हैं और आउटलेयर, बिंदु जो इस लाइन पर फिट नहीं किए जा सकते हैं, लाइन फिटिंग के लिए एक सिंपल लीस्ट स्क़ुअर्स मेथड सामान्यतः इनलियर्स और आउटलेर्स सहित डेटा के लिए बैड फिट वाली एक लाइन उत्पन्न करेगी। इसका कारण यह है कि यह आउटलेर्स सहित सभी बिंदुओं पर सर्वोत्तम रूप से फिट है। दूसरी ओर, आरएएनएसएसी, आउटलेर्स को बाहर करने और एक लीनियर मॉडल खोजने का प्रयास करता है जो अपनी गणना में केवल इनलियर्स का उपयोग करता है। यह डेटा के कई रैंडम सैंपलों में लीनियर मॉडल फिट करके और उस मॉडल को वापस करके किया जाता है जो डेटा के सबसेटों के लिए सबसे उपयुक्त है। चूँकि इनलियर्स और आउटलेर्स के रैंडम मिक्सचर की तुलना में अधिक रैखिक रूप से संबंधित होते हैं, एक रैंडम सबसेट जिसमें पूर्णतया से इनलियर्स सम्मिलित होते हैं, सबसे अच्छा मॉडल फिट होगा। व्यवहार में, इस बात की कोई गारंटी नहीं है कि इनलियर्स के एक सबसेट को रैंडम्ली संपलेड किया जाएगा और एल्गोरिदम के सफल होने की संभावना डेटा में इनलियर्स के अनुपात के साथ-साथ कई एल्गोरिदम पैरामीटर की पसंद पर निर्भर करती है।

• 

  कई आउटलेर्स वाला एक डेटा सेट जिसके लिए एक लाइन फिट की जानी है।

• 

  आरएएनएसएसी के साथ फिटेड लाइन; आउटलेर्स का परिणाम पर कोई प्रभाव नहीं पड़ता है।

अवलोकन

आरएएनएसएसी एल्गोरिथ्म अब्ज़र्व्ड डेटा के रैंडम सैंपल द्वारा किसी मॉडल के पैरामीटर का अनुमान लगाने की एक लर्निंग टेक्निक है। एक डेटासेट को देखते हुए जिसके डेटा एलेमेंटो में इनलियर्स और आउटलेर्स दोनों सम्मिलित हैं, आरएएनएसएसी ऑप्टीमल फिटिंग परिणाम खोजने के लिए वोटिंग स्कीम का उपयोग करता है। डेटासेट में डेटा एलेमेंटो का उपयोग एक या मल्टीप्ल मॉडलों के लिए वोट करने के लिए किया जाता है। इस वोटिंग स्कीम का कार्यान्वयन दो धारणाओं पर आधारित है: नॉइज़ फीचर्स किसी एक मॉडल (कुछ आउटलेर्स) के लिए लगातार वोट नहीं करेंगी और एक अच्छे मॉडल (कुछ लुप्त डेटा) पर सहमत होने के लिए पर्याप्त सुविधाएं हैं। आरएएनएसएसी एल्गोरिथ्म अनिवार्य रूप से दो चरणों से बना है जिन्हें पुनरावृत्त रूप से दोहराया जाता है:

1. पहले चरण में, इनपुट डेटासेट से न्यूनतम डेटा आइटम वाला एक सैंपल सबसेट रैंडम रूप से चुना जाता है। मॉडल पैरामीटर के साथ एक फिटिंग मॉडल की गणना केवल इस सैंपल सबसेट के एलेमेंटो का उपयोग करके की जाती है। सैंपल सबसेट की प्रमुखता (उदाहरण के लिए, इस सबसेट में डेटा की मात्रा) मॉडल पैरामीटर को निर्धारित करने के लिए पर्याप्त है।
2. दूसरे चरण में, एल्गोरिदम जाँचता है कि संपूर्ण डेटासेट के कौन से एलिमेंट पहले चरण से प्राप्त एस्टिमेटेड मॉडल पैरामीटर द्वारा तत्काल मॉडल के अनुरूप हैं। एक डेटा एलिमेंटो को आउटलेयर के रूप में माना जाएगा यदि यह इनलियर्स के अधिकतम डेटा विचलन को परिभाषित करने वाली कुछ एरर थ्रेसहोल्ड के भीतर मॉडल में फिट नहीं होता है (इस डेविएशन से परे डेटा एलिमेंट आउटलेयर हैं)।

फिटिंग मॉडल के लिए प्राप्त इनलियर्स के सेट को कंसेंसस सेट कहा जाता है। आरएएनएसएसी एल्गोरिथ्म उपरोक्त दो चरणों को तब तक दोहराएगा जब तक कि निश्चित पुनरावृत्ति में प्राप्त कंसेंसस सेट में पर्याप्त इनलाइनर न हों।

आरएएनएसएसी एल्गोरिथ्म का इनपुट अवलोकन किए गए डेटा मानों का एक सेट है, अवलोकनों के लिए उपयुक्त एक मॉडल और आउटलेर्स को परिभाषित करने वाले कुछ कॉन्फिडेंस पैरामीटर हैं। उपरोक्त आरएएनएसएसी एल्गोरिथ्म अवलोकन से अधिक विवरण में, आरएएनएसएसी निम्नलिखित चरणों को दोहराकर अपना लक्ष्य प्राप्त करता है:

1. मूल डेटा का एक रैंडम सबसेट चुनें। इस सबसेट को काल्पनिक इनलियर्स कहें।
2. एक मॉडल को काल्पनिक इनलियर्स के सेट पर फिट किया गया है।
3. फिर सभी डेटा का परीक्षण फिट किए गए मॉडल के विरुद्ध किया जाता है। सभी डेटा पॉइंट (मूल डेटा के) जो कुछ मॉडल-विशिष्ट लॉस फ़ंक्शन के अनुसार अनुमानित मॉडल को अच्छी तरह से फिट करते हैं, कंसेंसस सेट (अर्थात, मॉडल के लिए इनलियर्स का सेट) कहलाते हैं।
4. यदि पर्याप्त संख्या में डेटा पॉइंट्स को कंसेंसस सेट के हिस्से के रूप में वर्गीकृत किया गया है तो अनुमानित मॉडल काफी अच्छा है।
5. कंसेंसस सेट के सभी घटकों का उपयोग करके मॉडल का पुन: आकलन करके इसे उन्नत बनाया जा सकता है। मॉडल कंसेंसस सेट पर कितनी अच्छी तरह फिट बैठता है, इसके माप के रूप में फिटिंग गुणवत्ता का उपयोग मॉडल फिटिंग को तीव्र करने के लिए किया जाएगा क्योंकि पुनरावृत्ति आगे बढ़ती है (उदाहरण के लिए, इस माप को अगले पुनरावृत्ति में फिटिंग गुणवत्ता पैरामीटर के रूप में सेट करके)।

पर्याप्त रूप से अच्छे मॉडल पैरामीटर सेट में परिवर्तित होने के लिए, इस प्रक्रिया को निश्चित संख्या में दोहराया जाता है, प्रत्येक बार या तो मॉडल की अस्वीकृति उत्पन्न होती है क्योंकि बहुत कम बिंदु कंसेंसस सेट का हिस्सा होते हैं, या कंसेंसस सेट आकार के साथ एक रिफाइंड मॉडल पिछले कंसेंसस सेट से बड़ा होता है।

• 

  आरएएनएसएसी: इनलियर्स और आउटलेर्स। इस उदाहरण में डेटा पॉइंट्स की लीनियर फिटिंग 7 इनलियर्स के साथ है (डेटा पॉइंट कुछ पैरामीटरो के अंतर्गत मॉडल के साथ अच्छी तरह से फिट होते हैं)। यह एक अच्छी फिटिंग नहीं है क्योंकि इसमें एक लीनियर लाइन होती है जहां अधिकांश डेटा पॉइंट्स इसके पास वितरित होते हैं (अर्थात, अधिक इनलाइनर्स)।

स्यूडोकोड

सामान्य आरएएनएसएसी एल्गोरिथ्म निम्नलिखित स्यूडोकोड के रूप में कार्य करता है:

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 goes 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

उदाहरण कोड

स्यूडोकोड को प्रतिबिंबित करने वाला एक पायथन इम्प्लीमेंटेशन है। यह न्यूनतम वर्गों के आधार पर एक LinearRegressor को भी परिभाषित करता है, 2डी रिग्रेशन प्रॉब्लम पर RANSAC अनुप्रयुक्त करता है, और परिणाम की कल्पना करता है:

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 = maybe_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()

पैरामीटर

यह निर्धारित करने के लिए अवसीमा मान कि डेटा पॉइंट मॉडल (t) कब फिट बैठता है और मॉडल डेटा (d) के लिए अच्छी तरह से फिट बैठता है, यह सुनिश्चित करने के लिए आवश्यक इनलियर्स (t के भीतर मॉडल में फिट किए गए डेटा पॉइंट) की संख्या विशिष्ट आवश्यकताओं के आधार पर निर्धारित की जाती है। एप्लिकेशन और डेटासेट संभवतः प्रयोगात्मक मूल्यांकन पर आधारित है। हालाँकि, पुनरावृत्तियों की संख्या (k), मोटे तौर पर सफलता की वांछित संभावना (p) के एक फ़ंक्शन के रूप में निर्धारित की जा सकती है जैसा कि नीचे दर्शाया गया है।

मान लीजिए कि p वांछित संभावना है कि आरएएनएसएसी एल्गोरिथ्म चलने के बाद कम-से-कम एक उपयोगी परिणाम प्रदान करता है। चरम रूप में (व्युत्पत्ति को सरल बनाने के लिए), आरएएनएसएसी एक सफल परिणाम देता है यदि कुछ पुनरावृत्ति में यह इनपुट डेटा सेट से केवल इनलियर्स का चयन करता है जब यह डेटा सेट से n अंक चुनता है जिससे मॉडल पैरामीटर का अनुमान लगाया जाता है। दूसरे शब्दों में, सभी चयनित n डेटा पॉइंट इन बिंदुओं द्वारा अनुमानित मॉडल के अंतर्निहित हैं। $w$ प्रत्येक बार एक सिंगल डेटा पॉइंट का चयन करने पर एक अंतर्निहित को चुनने की संभावना होगी, जो मोटे तौर पर है,

$w$ = डेटा में इनलियर्स की संख्या / डेटा में अंकों की संख्या

एक सामान्य स्थिति यह है कि आरएएनएसएसी एल्गोरिदम चलाने से पहले डेटा में अज्ञात संख्या में इनलियर्स के कारण $w$ पहले से अच्छी तरह से ज्ञात नहीं है, लेकिन कुछ मोटा मान दिया जा सकता है। $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 के लिए व्युत्पन्न मान को उस स्थिति में ऊपरी सीमा के रूप में लिया जाना चाहिए जब बिंदुओं को प्रतिस्थापन के बिना चुना जाता है। उदाहरण के लिए, ऊपर दिए गए चित्र में दर्शाए गए डेटा सेट में फिट होने वाली रेखा को ढूंढने की स्थिति में, आरएएनएसएसी एल्गोरिदम सामान्यतः प्रत्येक पुनरावृत्ति में दो बिंदुओं को चुनता है और बिंदुओं के मध्य की रेखा के रूप में maybe_model की गणना करता है और फिर यह महत्वपूर्ण है कि दोनों बिंदु अलग-अलग हों।

एडिशनल कॉन्फिडेंस प्राप्त करने के लिए, मानक विचलन या उसके गुणकों को k में जोड़ा जा सकता है। k के मानक विचलनों को इस प्रकार परिभाषित किया गया है।

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

लाभ और हानि

आरएएनएसएसी का एक लाभ मॉडल पैरामीटर का प्रबल अनुमान करने की इसकी क्षमता है, अर्थात, यह डेटा सेट में महत्वपूर्ण संख्या में आउटलेर्स उपस्थित होने पर भी उच्च सटीकता के साथ पैरामीटर का अनुमान लगा सकता है। आरएएनएसएसी की एक हानि यह है कि इन पैरामीटरों की गणना करने में लगने वाले समय की कोई ऊपरी सीमा नहीं है (डेरिवेशन को छोड़कर)। जब गणना की गई पुनरावृत्तियों की संख्या सीमित होती है तो प्राप्त समाधान इष्टतम नहीं हो सकता है और यह ऐसा भी नहीं हो सकता है जो डेटा को अच्छे तरीके से फिट करता हो। इस तरह आरएएनएसएसी एक समझौते की प्रस्तुति करता है; अधिक संख्या में पुनरावृत्तियों की गणना करने से एक उचित मॉडल तैयार होने की संभावना बढ़ जाती है। इसके अतिरिक्त, आरएएनएसएसी सदैव मध्यम रूप से कंटामिनटेड सेटों के लिए भी ऑप्टीमल सेट ढूंढने में सक्षम नहीं होता है और यह सामान्यतः खराब प्रदर्शन करता है जब इनलियर्स की संख्या 50% से कम होती है। ऑप्टीमल आरएएनएसएसी को इन दोनों समस्याओं से निपटने के लिए प्रस्तावित किया गया था और यह अत्यधिक कंटामिनटेड सेटों के लिए ऑप्टीमल सेट खोजने में सक्षम है, यहां तक ​​कि 5% से कम के आंतरिक अनुपात के लिए भी है। आरएएनएसएसी की एक और हानि यह है कि इसमें समस्या-विशिष्ट सीमाएँ निर्धारित करने की आवश्यकता होती है।

आरएएनएसएसी किसी विशेष डेटा सेट के लिए केवल एक मॉडल का अनुमान लगा सकता है। जहां तक ​​किसी एक-मॉडल दृष्टिकोण की बात है, जब दो (या अधिक) मॉडल इंस्टेंस उपस्थित हों, तो आरएएनएसएसी किसी एक को भी ढूंढने में विफल हो सकता है। हफ़ ट्रांसफ़ॉर्म एक वैकल्पिक प्रबल अनुमान तकनीक है जो एक से अधिक मॉडल उदाहरण उपस्थित होने पर उपयोगी हो सकती है। मल्टी मॉडल फिटिंग के लिए एक अन्य दृष्टिकोण को पर्ल के नाम से जाना जाता है। जो आरएएनएसएसी में डेटा पॉइंट्स से मॉडल सैंपलिंग को इनलियर्स के पुनरावृत्तीय पुन: आकलन के साथ जोड़ती है और समग्र समाधान की गुणवत्ता का वर्णन करने वाले ग्लोबल एनर्जी फ़ंक्शन के साथ एक अनुकूलन समस्या के रूप में मल्टी-मॉडल फिटिंग तैयार किया जाता है।

ऍप्लिकेशन

आरएएनएसएसी एल्गोरिथ्म का उपयोग प्रायः कंप्यूटर विज़न में किया जाता है, उदाहरण के लिए, पत्राचार समस्या को एक साथ हल करने और स्टीरियो कैमरों के एक युग्म से संबंधित फंडामेंटल मैट्रिक्स का अनुमान लगाने के लिए; स्ट्रक्चर फ्रॉम मोशन, स्केल-इन्वेरीअन्ट फीचर ट्रांसफॉर्म, इमेज स्टिचिंग, करिजिड मोशन सेगमेंटेशन भी देखें।

विकास और सुधार

1981 से आरएएनएसएसी कंप्यूटर विज़न और इमेज प्रोसेसिंग कम्युनिटी में एक फंडामेंटल टूल बन गया है। 2006 में, एल्गोरिथम की 25वीं वर्षगांठ के लिए, मूल एल्गोरिथम में नवीनतम योगदानों और विविधताओं को संक्षेप में प्रस्तुत करने के लिए कंप्यूटर विज़न और पैटर्न रिकॉग्निशन (CVPR) पर अंतर्राष्ट्रीय सम्मेलन में एक कार्यशाला का आयोजन किया गया था, जिसका मुख्य उद्देश्य एल्गोरिथम की गति में सुधार करना था, अनुमानित समाधान की प्रबलता और सटीकता और उपयोगकर्ता परिभाषित स्थिरांक से निर्भरता को कम करना था।

आरएएनएसएसी करेक्ट नॉइज़ थ्रेसहोल्ड के चयन के प्रति संवेदनशील हो सकता है जो परिभाषित करता है कि कौन से डेटा पॉइंट पैरामीटर के एक निश्चित सेटों के साथ तत्काल मॉडल में फिट होते हैं। यदि ऐसी सीमा बहुत बड़ी है, तो सभी परिकल्पनाओं को समान (अच्छा) क्रम दिया जाता है। दूसरी ओर, जब नॉइज़ थ्रेसहोल्ड बहुत छोटी होती है, तो अनुमानित पैरामीटर अस्थिर हो जाते हैं (अर्थात केवल इनलियर्स के सेटों में डेटा जोड़ने या हटाने से, पैरामीटर के अनुमान में बदल सकता है)। इस अवांछनीय प्रभाव के लिए आंशिक रूप से क्षतिपूर्ति करने के लिए, टॉर एट अल ने आरएएनएसएसी के दो संशोधन प्रस्तावित हैं जिन्हें एमएसएसी (M-आकलनकर्ता सैंपल और कंसेंसस) और एमएलईएसएसी (अधिकतम संभावना अनुमान सैंपल और कंसेंसस) कहा जाता है। मुख्य विचार कंसेंसस सेटों की गुणवत्ता का मूल्यांकन करना है (अर्थात वह डेटा जो एक मॉडल और पैरामीटर के एक निश्चित सेटों में फिट बैठता है) इसकी संभावना की गणना करना है (जबकि फिशलर और बोल्स द्वारा मूल सूत्रीकरण में क्रम ऐसे सेटों की कार्डिनैलिटी थी)। एमएलईएसएसी का एक विस्तार जो इनपुट डाटासेट से जुड़ी पूर्व संभावनाओं को ध्यान में रखता है, टॉर्डॉफ द्वारा प्रस्तावित है। परिणामी एल्गोरिदम को निर्देशित-एमएलईएसएसी नाम दिया गया है। समान पंक्तियों के साथ, चुम ने सैंपलिंग प्रक्रिया का मार्गदर्शन करने का प्रस्ताव दिया यदि इनपुट डेटा के संबंध में कुछ प्राथमिक जानकारी ज्ञात हो, अर्थात कि क्या डेटाम इनलायर या आउटलायर होने की संभावना है। प्रस्तावित दृष्टिकोण को पीआरओएसएसी, प्रगतिशील सैंपल कंसेंसस कहा जाता है।

चुम एट अल. एक अच्छे कंसेंसस सेट की पहचान और कम्प्यूटेशनल बोझ को कम करने के लिए आर-आरएएनएसएसी नामक आरएएनएसएसी का एक रैंडम संस्करण भी प्रस्तावित किया गया। मूल विचार यह है कि प्रारंभ में संपूर्ण डेटासेट के बजाय केवल कम अंकों के सेट का उपयोग करके करंट इंस्टेंटियेटेड मॉडल की अच्छाई का मूल्यांकन किया जाए। एक ठोस रणनीति उच्च कॉन्फिडेंस के साथ बताएगी कि संपूर्ण डेटासेट की फिटिंग का मूल्यांकन करने की स्थिति कब है या मॉडल को सरलता से त्यक्त किया जा सकता है। यह सोचना उचित है कि इस दृष्टिकोण का प्रभाव उन स्थितियों में अधिक प्रासंगिक है जहां इनलियर्स का प्रतिशत बड़ा है। चुम एट अल द्वारा प्रस्तावित रणनीति का प्रकार प्रीएम्प्शन स्कीम कहलाती है। निस्टर ने प्रीमेप्टिव आरएएनएसएसी नामक एक प्रतिमान का प्रस्ताव रखा जो किसी दृश्य की संरचना और कैमरे की गति का वास्तविक समय में प्रबल अनुमान लगाने की अनुमति देता है। दृष्टिकोण का मुख्य विचार एक निश्चित संख्या में परिकल्पना उत्पन्न करना है ताकि तुलना कुछ पूर्ण गुणवत्ता मीट्रिक के बजाय उत्पन्न परिकल्पना की गुणवत्ता के संबंध में हो।

अन्य शोधकर्ताओं ने उन कठिन परिस्थितियों से निपटने का प्रयास किया जहां नॉइज़ पैमाना ज्ञात नहीं है और/या कई मॉडल उदाहरण उपस्थित हैं। पहली समस्या का समाधान वांग और स्यूटर द्वारा किया गया है। टोल्डो एट अल. बिंदु पर उपयुक्त होने वाले रैंडम मॉडल के सेट के विशिष्ट कार्य के साथ प्रत्येक डेटाम का प्रतिनिधित्व करें। फिर कई मॉडल क्लस्टर के रूप में सामने आते हैं जो एक ही मॉडल का समर्थन करने वाले बिंदुओं को समूहित करते हैं। क्लस्टरिंग एल्गोरिदम, जिसे जे-लिंकेज कहा जाता है, जिनको मॉडलों की संख्या के पूर्व विनिर्देश की आवश्यकता नहीं होती है, न ही इसे मैन्युअल पैरामीटर ट्यूनिंग की आवश्यकता होती है।

आरएएनएसएसी को पुनरावर्ती अवस्था अनुमान अनुप्रयोगों के लिए भी तैयार किया गया है, जहां इनपुट माप आउटलेर्स द्वारा दूषित हो जाते हैं और कलमन फ़िल्टर दृष्टिकोण, जो माप त्रुटि के गॉसियन वितरण पर निर्भर होते हैं, विफल होने के लिए अभिशप्त होते हैं। इस तरह के दृष्टिकोण को केएएलएमएएनएसएसी कहा जाता है।

संबंधित विधियाँ

• एमएलईएसएसी (मैक्सिमम लइकेलीहुड एस्टीमेट सैंपल कंसेंसस) - इस संभावना को अधिकतम करता है कि डेटा सैंपल-फिट मॉडल से उत्पन्न हुआ था, उदाहरण के लिए, इनलियर्स और आउटलेर्स का मिक्सचर मॉडल है।
• एमएपीएसएसी (मैक्सिमम पोस्टीरियर सैंपल कंसेंसस) - उपयुक्त किए जाने वाले पैरामीटर की प्रायर प्रोबेबिलिटी को सम्मिलित करने के लिए एमएलईएसएसी का विस्तार करता है और पोस्टीरियर प्रोबेबिलिटी को अधिकतम करता है।
• केएएलएमएएनएसएसी - एक डायनैमिकल सिस्टम की स्थिति का कॉसल इनफरेंस है।
• रेसंपलिंग (सांख्यिकी)
• हॉप-डिफ्यूजन मोंटे कार्लो बहुत वाइड-बेसलाइन इमेजो के मध्य एपिपोलर ज्योमेट्री अनुमान के लिए आरएएनएसएसी के प्रत्येक चरण पर सैंपल चुनने के लिए रैंडम सैंपलिंग का उपयोग करता है जिसमें ग्लोबल जंप और लोकल लोकल सम्मिलित होता है।

यह भी देखें

• हफ ट्रांसफॉर्म

संदर्भ

• Martin A. Fischler & Robert C. Bolles (June 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography" (PDF). Comm. ACM. 24 (6): 381–395. doi:10.1145/358669.358692. S2CID 972888. Archived (PDF) from the original on December 10, 2014.
• David A. Forsyth & Jean Ponce (2003). Computer Vision, a modern approach. Prentice Hall. ISBN 978-0-13-085198-7.
• Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in Computer Vision (2nd ed.). Cambridge University Press.
• Strutz, T. (2016). Data Fitting and Uncertainty (A practical introduction to weighted least squares and beyond). 2nd edition, Springer Vieweg. ISBN 978-3-658-11455-8.
• P.H.S. Torr & D.W. Murray (1997). "The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix". International Journal of Computer Vision. 24 (3): 271–300. doi:10.1023/A:1007927408552. S2CID 12031059.
• Ondrej Chum (2005). "Two-View Geometry Estimation by Random Sample and Consensus" (PDF). PhD Thesis.
• Sunglok Choi; Taemin Kim & Wonpil Yu (2009). "Performance Evaluation of RANSAC Family" (PDF). In Proceedings of the British Machine Vision Conference (BMVC).

• Anders Hast; Johan Nysjö; Andrea Marchetti (2013). "Optimal RANSAC – Towards a Repeatable Algorithm for Finding the Optimal Set" (PDF). Journal of WSCG. 21 (1): 21–30.
• Hossam Isack; Yuri Boykov (2012). "Energy-based Geometric Multi-Model Fitting" (PDF). International Journal of Computer Vision. 97 (2: 1): 23–147. CiteSeerX 10.1.1.381.2434. doi:10.1007/s11263-011-0474-7. S2CID 5461268.