CINXE.COM

<!DOCTYPE html> <html class="client-nojs" lang="de" dir="ltr"> <head> <meta charset="UTF-8"> <title>RANSAC-Algorithmus – Wikipedia</title> <script>(function(){var className="client-js";var cookie=document.cookie.match(/(?:^|; )dewikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t.",".\t,"],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","Januar","Februar","März","April","Mai","Juni","Juli","August","September","Oktober","November","Dezember"],"wgRequestId":"6db1c187-01f4-46e5-8227-6248e8a3ffa4","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"RANSAC-Algorithmus","wgTitle":"RANSAC-Algorithmus","wgCurRevisionId":239854521,"wgRevisionId":239854521,"wgArticleId":2114029,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"], "wgCategories":["Wikipedia:Exzellent","Computer Vision","Algorithmus","Regressionsanalyse"],"wgPageViewLanguage":"de","wgPageContentLanguage":"de","wgPageContentModel":"wikitext","wgRelevantPageName":"RANSAC-Algorithmus","wgRelevantArticleId":2114029,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgFlaggedRevsParams":{"tags":{"accuracy":{"levels":1}}},"wgStableRevisionId":239854521,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"de","pageLanguageDir":"ltr","pageVariantFallbacks":"de"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage", "wgULSisCompactLinksEnabled":true,"wgVector2022LanguageInHeader":false,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q218533","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.gadget.citeRef":"ready","ext.gadget.defaultPlainlinks":"ready","ext.gadget.dewikiCommonHide":"ready","ext.gadget.dewikiCommonLayout":"ready","ext.gadget.dewikiCommonStyle":"ready","ext.gadget.NavFrame":"ready","ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","mediawiki.page.gallery.styles":"ready","ext.math.styles":"ready","skins.vector.styles.legacy":"ready","ext.flaggedRevs.basic":"ready", "mediawiki.codex.messagebox.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","codex-search-styles":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.legacy.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.flaggedRevs.advanced","ext.gadget.createNewSection","ext.gadget.WikiMiniAtlas","ext.gadget.OpenStreetMap","ext.gadget.CommonsDirekt","ext.gadget.donateLink","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.compactlinks","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession", "wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=de&modules=codex-search-styles%7Cext.cite.styles%7Cext.flaggedRevs.basic%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cmediawiki.codex.messagebox.styles%7Cmediawiki.page.gallery.styles%7Cskins.vector.styles.legacy%7Cwikibase.client.init&only=styles&skin=vector"> <script async="" src="/w/load.php?lang=de&modules=startup&only=scripts&raw=1&skin=vector"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=de&modules=ext.gadget.NavFrame%2CciteRef%2CdefaultPlainlinks%2CdewikiCommonHide%2CdewikiCommonLayout%2CdewikiCommonStyle&only=styles&skin=vector"> <link rel="stylesheet" href="/w/load.php?lang=de&modules=site.styles&only=styles&skin=vector"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="RANSAC-Algorithmus – Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//de.m.wikipedia.org/wiki/RANSAC-Algorithmus"> <link rel="alternate" type="application/x-wiki" title="Seite bearbeiten" href="/w/index.php?title=RANSAC-Algorithmus&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (de)"> <link rel="EditURI" type="application/rsd+xml" href="//de.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://de.wikipedia.org/wiki/RANSAC-Algorithmus"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de"> <link rel="alternate" type="application/atom+xml" title="Atom-Feed für „Wikipedia“" href="/w/index.php?title=Spezial:Letzte_%C3%84nderungen&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin-vector-legacy mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-RANSAC-Algorithmus rootpage-RANSAC-Algorithmus skin-vector action-view"><div id="mw-page-base" class="noprint"></div> <div id="mw-head-base" class="noprint"></div> <div id="content" class="mw-body" role="main"> <a id="top"></a> <div id="siteNotice"></div> <div class="mw-indicators"> <div id="mw-indicator-topicon-Vorlage_Exzellent" class="mw-indicator"><div class="mw-parser-output"><div class="noprint"><span typeof="mw:File"><a href="#Vorlage_Exzellent" title="Dies ist ein als exzellent ausgezeichneter Artikel."><img alt="Dies ist ein als exzellent ausgezeichneter Artikel." src="//upload.wikimedia.org/wikipedia/commons/thumb/4/41/Qsicon_Exzellent.svg/15px-Qsicon_Exzellent.svg.png" decoding="async" width="15" height="15" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/41/Qsicon_Exzellent.svg/23px-Qsicon_Exzellent.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/41/Qsicon_Exzellent.svg/30px-Qsicon_Exzellent.svg.png 2x" data-file-width="24" data-file-height="24" /></a></span></div></div></div> </div> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">RANSAC-Algorithmus</span></h1> <div id="bodyContent" class="vector-body"> <div id="siteSub" class="noprint">aus Wikipedia, der freien Enzyklopädie</div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="contentSub2"></div> <div id="jump-to-nav"></div> <a class="mw-jump-link" href="#mw-head">Zur Navigation springen</a> <a class="mw-jump-link" href="#searchInput">Zur Suche springen</a> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p><b>RANSAC</b> (<span style="font-style:normal;font-weight:normal"><a href="/wiki/Englische_Sprache" title="Englische Sprache">englisch</a></span> <span lang="en-Latn" style="font-style:italic"><b>ran</b>dom <b>sa</b>mple <b>c</b>onsensus</span>, deutsch etwa „Übereinstimmung mit einer zufälligen Stichprobe“) ist ein <a href="/wiki/Resampling" title="Resampling">Resampling</a>-<a href="/wiki/Algorithmus" title="Algorithmus">Algorithmus</a> zur Schätzung eines Modells innerhalb einer <a href="/wiki/Messreihe" title="Messreihe">Reihe von Messwerten</a> mit <a href="/wiki/Ausrei%C3%9Fer" title="Ausreißer">Ausreißern</a> und groben <a href="/wiki/Messabweichung" title="Messabweichung">Fehlern</a>. Wegen seiner <a href="/wiki/Robustheit" title="Robustheit">Robustheit</a> gegenüber Ausreißern wird er vor allem bei der Auswertung automatischer Messungen vornehmlich im Fachgebiet <a href="/wiki/Computer_Vision" title="Computer Vision">Computer Vision</a> eingesetzt. Hier unterstützt RANSAC – durch Berechnung einer um Ausreißer bereinigten Datenmenge, des sogenannten <i>Consensus Sets</i> – Ausgleichsverfahren wie die <a href="/wiki/Methode_der_kleinsten_Quadrate" title="Methode der kleinsten Quadrate">Methode der kleinsten Quadrate</a>, die bei einer größeren Anzahl von Ausreißern meist versagen. </p><p>RANSAC wurde offiziell 1981 von Martin A. Fischler und Robert C. Bolles in den <a href="/wiki/Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a> vorgestellt. Eine interne Präsentation am <a href="/wiki/SRI_International" title="SRI International">SRI International</a>, an dem beide Autoren arbeiteten,<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> fand bereits im März 1980 statt.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Eine Alternative zu RANSAC sind <a href="/wiki/M-Sch%C3%A4tzer" title="M-Schätzer">M-Schätzer</a>. Diese sind im Vergleich zu anderen Schätzern wie etwa den <a href="/wiki/Maximum-Likelihood-Methode" title="Maximum-Likelihood-Methode">Maximum-Likelihood-Schätzern</a> robuster gegenüber Ausreißern. RANSAC beruht auf <a href="/wiki/Kreuzvalidierungsverfahren#Wiederholtes_zufälliges_Subsampling" title="Kreuzvalidierungsverfahren">wiederholtem zufälligem Subsampling</a><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>. </p> <div id="toc" class="toc" role="navigation" aria-labelledby="mw-toc-heading"><input type="checkbox" role="button" id="toctogglecheckbox" class="toctogglecheckbox" style="display:none" /><div class="toctitle" lang="de" dir="ltr"><h2 id="mw-toc-heading">Inhaltsverzeichnis</h2><span class="toctogglespan"><label class="toctogglelabel" for="toctogglecheckbox"></label></span></div> <ul> <li class="toclevel-1 tocsection-1"><a href="#Einleitung_und_Prinzip"><span class="tocnumber">1</span> <span class="toctext">Einleitung und Prinzip</span></a></li> <li class="toclevel-1 tocsection-2"><a href="#Anwendungen"><span class="tocnumber">2</span> <span class="toctext">Anwendungen</span></a></li> <li class="toclevel-1 tocsection-3"><a href="#Vorgehensweise_und_Parameter"><span class="tocnumber">3</span> <span class="toctext">Vorgehensweise und Parameter</span></a> <ul> <li class="toclevel-2 tocsection-4"><a href="#Maximaler_Abstand_eines_Datenpunkts_vom_Modell"><span class="tocnumber">3.1</span> <span class="toctext">Maximaler Abstand eines Datenpunkts vom Modell</span></a></li> <li class="toclevel-2 tocsection-5"><a href="#Anzahl_der_Iterationen"><span class="tocnumber">3.2</span> <span class="toctext">Anzahl der Iterationen</span></a></li> <li class="toclevel-2 tocsection-6"><a href="#Größe_des_Consensus_Sets"><span class="tocnumber">3.3</span> <span class="toctext">Größe des Consensus Sets</span></a></li> </ul> </li> <li class="toclevel-1 tocsection-7"><a href="#Adaptive_Bestimmung_der_Parameter"><span class="tocnumber">4</span> <span class="toctext">Adaptive Bestimmung der Parameter</span></a></li> <li class="toclevel-1 tocsection-8"><a href="#Beispiel"><span class="tocnumber">5</span> <span class="toctext">Beispiel</span></a></li> <li class="toclevel-1 tocsection-9"><a href="#Weiterentwicklungen"><span class="tocnumber">6</span> <span class="toctext">Weiterentwicklungen</span></a> <ul> <li class="toclevel-2 tocsection-10"><a href="#LO-RANSAC"><span class="tocnumber">6.1</span> <span class="toctext">LO-RANSAC</span></a></li> <li class="toclevel-2 tocsection-11"><a href="#MSAC"><span class="tocnumber">6.2</span> <span class="toctext">MSAC</span></a></li> </ul> </li> <li class="toclevel-1 tocsection-12"><a href="#Einzelnachweise"><span class="tocnumber">7</span> <span class="toctext">Einzelnachweise</span></a></li> <li class="toclevel-1 tocsection-13"><a href="#Literatur"><span class="tocnumber">8</span> <span class="toctext">Literatur</span></a></li> </ul> </div> <div class="mw-heading mw-heading2"><h2 id="Einleitung_und_Prinzip">Einleitung und Prinzip</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=1" title="Abschnitt bearbeiten: Einleitung und Prinzip" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=1" title="Quellcode des Abschnitts bearbeiten: Einleitung und Prinzip"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Oft liegen als Ergebnis einer Messung Datenpunkte vor, die physikalische Werte wie Druck, Entfernung oder Temperatur, wirtschaftliche Größen oder ähnliches repräsentieren. In diese Punkte soll eine möglichst genau passende, parameterabhängige Modellkurve gelegt werden. Dabei liegen mehr Datenpunkte vor, als zur Ermittlung der Parameter notwendig sind; das Modell ist also <a href="/wiki/%C3%9Cberbestimmung" title="Überbestimmung">überbestimmt</a>. Die Messwerte können Ausreißer enthalten, also Werte, die nicht in die erwartete <a href="/wiki/Messreihe" title="Messreihe">Messreihe</a> passen. Da Messungen bis zur Entwicklung der Digitaltechnik meist manuell durchgeführt wurden, führte die Kontrolle durch den Operateur dazu, dass der Anteil von Ausreißern meist gering war. Die damals eingesetzten <a href="/wiki/Ausgleichungsrechnung" title="Ausgleichungsrechnung">Ausgleichsalgorithmen</a>, wie die Methode der kleinsten Quadrate, sind gut für die Auswertung solcher Datensätze mit wenig Ausreißern geeignet: Mit ihrer Hilfe wird zuerst mit der Gesamtheit der Datenpunkte das Modell bestimmt und danach versucht, die Ausreißer zu detektieren. </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Datei:Ausrei%C3%9Fer.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/2/23/Ausrei%C3%9Fer.svg/220px-Ausrei%C3%9Fer.svg.png" decoding="async" width="220" height="167" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/23/Ausrei%C3%9Fer.svg/330px-Ausrei%C3%9Fer.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/2/23/Ausrei%C3%9Fer.svg/440px-Ausrei%C3%9Fer.svg.png 2x" data-file-width="395" data-file-height="300" /></a><figcaption>Der einzelne Ausreißer zieht die Ausgleichsgerade nach oben</figcaption></figure> <p>Mit der Entwicklung der <a href="/wiki/Digitaltechnik" title="Digitaltechnik">Digitaltechnik</a> ab Anfang der 1980er Jahre änderten sich die Grundlagen. Durch die neuen Möglichkeiten wurden zunehmend automatische Messverfahren vor allem im Fachgebiet <a href="/wiki/Computer_Vision" title="Computer Vision">Computer Vision</a> eingesetzt. Als Ergebnis liegt hier oft eine große Anzahl an Werten vor, die meist viele Ausreißer enthält. Die traditionellen Verfahren gehen von einer <a href="/wiki/Normalverteilung" title="Normalverteilung">Normalverteilung</a> der Fehler aus und liefern zum Teil kein sinnvolles Ergebnis, wenn die Datenpunkte viele Ausreißer enthalten. Dies ist in nebenstehender Darstellung illustriert. Es soll eine Gerade (das Modell) an die Punkte (Messwerte) angepasst werden. Der einzelne Ausreißer unter den 20 Datenpunkten kann einerseits durch traditionelle Verfahren vor Bestimmung der Gerade nicht ausgeschlossen werden. Andererseits beeinflusst er aufgrund seiner Lage die Ausgleichsgerade unverhältnismäßig stark (sogenannter Hebelpunkt). </p><p>Der RANSAC-Algorithmus verfolgt einen neuen, iterativen Ansatz. Statt alle Messwerte gemeinsam auszugleichen, werden lediglich so viele zufällig ausgewählte Werte benutzt, wie nötig sind, um die Modellparameter zu berechnen (im Fall einer Geraden wären das zwei Punkte). Dabei wird zunächst angenommen, dass die ausgewählten Werte keine Ausreißer sind. Diese Annahme wird überprüft, indem zuerst das Modell aus den zufällig gewählten Werten berechnet und danach die Distanz aller Messwerte (also nicht nur der ursprünglich ausgewählten) zu diesem Modell bestimmt wird. Ist die Distanz eines Messwertes zum Modell kleiner als ein vorher festgelegter Schwellenwert, dann ist dieser Messwert in Bezug auf das berechnete Modell kein grober Fehler. Er <i>unterstützt</i> es somit. Je mehr Messwerte das Modell unterstützen, desto wahrscheinlicher enthielten die zufällig zur Modellberechnung ausgewählten Werte keine Ausreißer. Diese drei Schritte – zufällige Auswahl von Messwerten, Berechnung der Modellparameter und Bestimmung der Unterstützung – werden mehrmals unabhängig voneinander wiederholt. In jeder Iteration wird gespeichert, welche Messwerte das jeweilige Modell unterstützen. Diese Menge wird <i>Consensus Set</i> genannt. Aus dem größten <i>Consensus Set</i>, das im Idealfall keine Ausreißer mehr enthält, wird abschließend mit einem der traditionellen Ausgleichsverfahren die Lösung ermittelt. </p> <div class="mw-heading mw-heading2"><h2 id="Anwendungen">Anwendungen</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=2" title="Abschnitt bearbeiten: Anwendungen" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=2" title="Quellcode des Abschnitts bearbeiten: Anwendungen"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Wie erwähnt, treten viele Ausreißer vor allem bei automatischen Messungen auf. Diese werden häufig im Fachgebiet <a href="/wiki/Computer_Vision" title="Computer Vision">Computer Vision</a> durchgeführt, so dass RANSAC insbesondere hier weit verbreitet ist. Im Folgenden werden einige Anwendungen vorgestellt. </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Datei:Alcatraz03182006.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Alcatraz03182006.jpg/550px-Alcatraz03182006.jpg" decoding="async" width="550" height="85" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Alcatraz03182006.jpg/825px-Alcatraz03182006.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Alcatraz03182006.jpg/1100px-Alcatraz03182006.jpg 2x" data-file-width="4024" data-file-height="624" /></a><figcaption>Gestitchtes Panoramabild von <a href="/wiki/Alcatraz" title="Alcatraz">Alcatraz</a>: Dazu müssen Einzelbilder passend überlagert werden, um sie danach zu überblenden. Dazu müssen gemeinsame Merkmale in den Teilbildern gefunden werden.</figcaption></figure> <p>In der <a href="/wiki/Bildverarbeitung" title="Bildverarbeitung">Bildverarbeitung</a> wird RANSAC bei der Bestimmung von homologen Punkten zwischen zwei Kamerabildern eingesetzt. Homolog sind die zwei Bildpunkte, die ein einzelner Objektpunkt in den beiden Bildern erzeugt. Die Zuordnung homologer Punkte wird Korrespondenzproblem genannt. Das Resultat einer automatischen Analyse enthält meist eine größere Anzahl Fehlzuordnungen. Verfahren, die auf dem Ergebnis der Korrespondenzanalyse aufsetzen, benutzen RANSAC, um die Fehlzuordnungen auszuschließen. Ein Beispiel für diese Vorgehensweise ist die Erstellung eines Panoramabildes aus verschiedenen kleineren Einzelaufnahmen (<a href="/wiki/Stitching" title="Stitching">Stitching</a>).<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Ein weiteres ist die Berechnung der <a href="/wiki/Epipolargeometrie" title="Epipolargeometrie">Epipolargeometrie</a>. Das ist ein Modell aus der Geometrie, das die geometrischen Beziehungen zwischen verschiedenen Kamerabildern desselben Objekts darstellt. Hier dient RANSAC zur Bestimmung der Fundamentalmatrix, die die geometrische Beziehung zwischen den Bildern beschreibt. </p><p>Bei der <a href="/wiki/DARPA_Grand_Challenge" title="DARPA Grand Challenge">DARPA Grand Challenge</a>, einem Wettbewerb für autonome Landfahrzeuge, wurde RANSAC dazu benutzt, die Fahrbahnebene zu bestimmen sowie die Bewegung des Fahrzeuges zu rekonstruieren.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </p><p>Der Algorithmus wird auch dazu verwendet, um in verrauschten dreidimensionalen Punktmengen geometrische Körper wie <a href="/wiki/Zylinder_(Geometrie)" title="Zylinder (Geometrie)">Zylinder</a> oder ähnliches anzupassen oder automatisch Punktwolken zu <a href="/wiki/Segmentierung_(Bildverarbeitung)" title="Segmentierung (Bildverarbeitung)">segmentieren</a>. Dabei werden alle Punkte, die nicht zum selben Segment gehören, als Ausreißer betrachtet. Nach einer Schätzung des dominantesten Körpers in der Punktwolke werden alle zu diesem Körper gehörenden Punkte entfernt, um im nächsten Schritt weitere Körper bestimmen zu können. Dieser Vorgang wird solange wiederholt, bis alle Körper in der Punktmenge gefunden wurden.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Vorgehensweise_und_Parameter">Vorgehensweise und Parameter</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=3" title="Abschnitt bearbeiten: Vorgehensweise und Parameter" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=3" title="Quellcode des Abschnitts bearbeiten: Vorgehensweise und Parameter"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Voraussetzung für RANSAC ist, dass mehr Datenpunkte vorliegen, als zur Bestimmung der Modellparameter notwendig sind. Der Algorithmus besteht aus folgenden Schritten: </p> <ol><li>Wähle zufällig so viele Punkte aus den Datenpunkten, wie nötig sind, um die Parameter des Modells zu berechnen. Das geschieht in Erwartung, dass diese Menge frei von Ausreißern ist.</li> <li>Ermittle mit den gewählten Punkten die Modellparameter.</li> <li>Bestimme die Teilmenge der Messwerte, deren Abstand zur Modellkurve kleiner als ein bestimmter Grenzwert ist (diese Teilmenge wird <i>Consensus Set</i> genannt). Enthält sie eine gewisse Mindestanzahl an Werten, wurde vermutlich ein gutes Modell gefunden, und der <i>Consensus Set</i> wird gespeichert.</li> <li>Wiederhole die Schritte 1–3 mehrmals.</li></ol> <p>Nach Durchführung von mehreren Iterationen wird diejenige Teilmenge gewählt, welche die meisten Punkte enthält (so denn eine gefunden wurde). Nur mit dieser Teilmenge werden mit einem der üblichen Ausgleichsverfahren die Modellparameter berechnet. Eine alternative Variante des Algorithmus beendet die Iterationen vorzeitig, wenn im Schritt 3 genügend Punkte das Modell unterstützen. Diese Variante wird als präemptives – das heißt vorzeitig abbrechendes – RANSAC bezeichnet. Bei diesem Vorgehen muss im Vorfeld bekannt sein, wie groß der Ausreißeranteil etwa ist, damit eingeschätzt werden kann, ob genügend Messwerte das Modell unterstützen. </p><p>Der Algorithmus hängt im Wesentlichen von drei Parametern ab: </p> <ol><li>dem maximalen Abstand eines Datenpunktes vom Modell, bis zu dem ein Punkt nicht als grober Fehler gilt;</li> <li>der Anzahl der Iterationen und</li> <li>der Mindestgröße des <i>Consensus Sets</i>, also der Mindestanzahl der mit dem Modell konsistenten Punkte.</li></ol> <div class="mw-heading mw-heading3"><h3 id="Maximaler_Abstand_eines_Datenpunkts_vom_Modell">Maximaler Abstand eines Datenpunkts vom Modell</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=4" title="Abschnitt bearbeiten: Maximaler Abstand eines Datenpunkts vom Modell" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=4" title="Quellcode des Abschnitts bearbeiten: Maximaler Abstand eines Datenpunkts vom Modell"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Dieser Parameter ist grundlegend für den Erfolg des Algorithmus. Im Gegensatz zu den anderen beiden Parametern muss er festgelegt werden (eine Überprüfung des <i>Consensus Set</i> braucht nicht durchgeführt zu werden, und die Anzahl der Iterationen kann nahezu beliebig hoch gewählt werden). Ist der Wert zu groß oder zu klein, kann der Algorithmus scheitern. Dies ist in den folgenden drei Bildern illustriert. Dargestellt ist jeweils ein Iterationsschritt. Die beiden zufällig ausgewählten Punkte, mit denen die grüne Modellgerade berechnet wurde, sind blau eingefärbt. Die <a href="/wiki/Fehlerschranke" title="Fehlerschranke">Fehlerschranken</a> sind als schwarze Linien dargestellt. Innerhalb dieser Linien muss ein Punkt liegen, um die Modellgerade zu unterstützen. Wird der Abstand zu groß gewählt, werden zu viele Ausreißer nicht erkannt, so dass ein falsches Modell die gleiche Anzahl von Ausreißern wie ein richtiges Modell haben kann (Bild 1a und 1b). Ist er zu gering angesetzt, kann es vorkommen, dass ein Modell, das aus einer ausreißerfreien Menge von Werten berechnet wurde, durch zu wenig andere Werte, die keine Ausreißer sind, unterstützt wird (Bild 2). </p> <ul class="gallery mw-gallery-traditional"> <li class="gallerycaption">Probleme bei zu großer oder zu kleiner Wahl der Fehlerschranke</li> <li class="gallerybox" style="width: 245px"> <div class="thumb" style="width: 240px; height: 150px;"><span typeof="mw:File"><a href="/wiki/Datei:RANSAC_MaxDist1.svg" class="mw-file-description" title="1a. Richtige Lösung, zwei Punkte sind Ausreißer."><img alt="1a. Richtige Lösung, zwei Punkte sind Ausreißer." src="//upload.wikimedia.org/wikipedia/commons/thumb/b/bc/RANSAC_MaxDist1.svg/175px-RANSAC_MaxDist1.svg.png" decoding="async" width="175" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/bc/RANSAC_MaxDist1.svg/263px-RANSAC_MaxDist1.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/bc/RANSAC_MaxDist1.svg/350px-RANSAC_MaxDist1.svg.png 2x" data-file-width="461" data-file-height="316" /></a></span></div> <div class="gallerytext">1a. Richtige Lösung, zwei Punkte sind Ausreißer.</div> </li> <li class="gallerybox" style="width: 245px"> <div class="thumb" style="width: 240px; height: 150px;"><span typeof="mw:File"><a href="/wiki/Datei:RANSAC_MaxDist2.svg" class="mw-file-description" title="1b. Zweite, falsche Lösung mit der gleichen Anzahl von Ausreißern wie bei 1a."><img alt="1b. Zweite, falsche Lösung mit der gleichen Anzahl von Ausreißern wie bei 1a." src="//upload.wikimedia.org/wikipedia/commons/thumb/6/6a/RANSAC_MaxDist2.svg/156px-RANSAC_MaxDist2.svg.png" decoding="async" width="156" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/6a/RANSAC_MaxDist2.svg/233px-RANSAC_MaxDist2.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/6a/RANSAC_MaxDist2.svg/311px-RANSAC_MaxDist2.svg.png 2x" data-file-width="457" data-file-height="353" /></a></span></div> <div class="gallerytext">1b. Zweite, falsche Lösung mit der gleichen Anzahl von Ausreißern wie bei 1a.</div> </li> <li class="gallerybox" style="width: 245px"> <div class="thumb" style="width: 240px; height: 150px;"><span typeof="mw:File"><a href="/wiki/Datei:RANSAC_MaxDistTooLow.svg" class="mw-file-description" title="2. Fehlerschranke zu klein."><img alt="2. Fehlerschranke zu klein." src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1e/RANSAC_MaxDistTooLow.svg/184px-RANSAC_MaxDistTooLow.svg.png" decoding="async" width="184" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1e/RANSAC_MaxDistTooLow.svg/276px-RANSAC_MaxDistTooLow.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1e/RANSAC_MaxDistTooLow.svg/368px-RANSAC_MaxDistTooLow.svg.png 2x" data-file-width="409" data-file-height="267" /></a></span></div> <div class="gallerytext">2. Fehlerschranke zu klein.</div> </li> </ul> <p>Trotz dieser Probleme muss dieser Wert meist <a href="/wiki/Empirie" title="Empirie">empirisch</a> festgelegt werden. Lediglich wenn die <a href="/wiki/Empirische_Standardabweichung" class="mw-redirect" title="Empirische Standardabweichung">Standardabweichung</a> der Messwerte bekannt ist, kann die Fehlergrenze mittels der Gesetze der <a href="/wiki/Wahrscheinlichkeitsverteilung" class="mw-redirect" title="Wahrscheinlichkeitsverteilung">Wahrscheinlichkeitsverteilung</a> berechnet werden. </p> <div class="mw-heading mw-heading3"><h3 id="Anzahl_der_Iterationen">Anzahl der Iterationen</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=5" title="Abschnitt bearbeiten: Anzahl der Iterationen" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=5" title="Quellcode des Abschnitts bearbeiten: Anzahl der Iterationen"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Die Anzahl von Wiederholungen kann so festgelegt werden, dass mit einer bestimmten Wahrscheinlichkeit <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}"></span> mindestens einmal eine ausreißerfreie Teilmenge aus den Datenpunkten ausgewählt wird. Ist <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01d131dfd7673938b947072a13a9744fe997e632" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}"></span> die Anzahl der Datenpunkte, die zur Berechnung eines Modells notwendig sind, und <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ϵ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3837cad72483d97bcdde49c85d3b7b859fb3fd2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }"></span> der relative Anteil an Ausreißern in den Daten, so ist die Wahrscheinlichkeit, dass bei <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> Wiederholungen nicht jedes Mal mindestens ein Ausreißer mit ausgewählt wird </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p=1-\left(1-\left(1-\epsilon \right)^{s}\right)^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>=</mo> <mn>1</mn> <mo>−</mo> <msup> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <msup> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <mi>ϵ</mi> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>s</mi> </mrow> </msup> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p=1-\left(1-\left(1-\epsilon \right)^{s}\right)^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b186f08913181f9eb56167c0639f984e46ecaf8f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:23.15ex; height:3.009ex;" alt="{\displaystyle p=1-\left(1-\left(1-\epsilon \right)^{s}\right)^{n}}"></span>.</dd></dl> <p>Damit die Wahrscheinlichkeit, dass jedes Mal mindestens ein Ausreißer mit ausgewählt wird, höchstens <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>−</mo> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1-p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9633a8692121eedfa99cace406205e5d1511ef8d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.172ex; height:2.509ex;" alt="{\displaystyle 1-p}"></span> wird, muss <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> groß genug gewählt werden. Genauer werden mindestens </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n={\frac {\log \left(1-p\right)}{\log \left(1-\left(1-\epsilon \right)^{s}\right)}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>log</mi> <mo>⁡</mo> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <mi>p</mi> </mrow> <mo>)</mo> </mrow> </mrow> <mrow> <mi>log</mi> <mo>⁡</mo> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <msup> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <mi>ϵ</mi> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>s</mi> </mrow> </msup> </mrow> <mo>)</mo> </mrow> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n={\frac {\log \left(1-p\right)}{\log \left(1-\left(1-\epsilon \right)^{s}\right)}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6141ffdc4e72a4e75a13584a8824943cd1311c40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:21.873ex; height:6.509ex;" alt="{\displaystyle n={\frac {\log \left(1-p\right)}{\log \left(1-\left(1-\epsilon \right)^{s}\right)}}}"></span></dd></dl> <p>Wiederholungen benötigt. Die Anzahl hängt also nur vom Anteil der Ausreißer, der Zahl der Parameter der Modellfunktion und der vorgegebenen Wahrscheinlichkeit der Ziehung mindestens einer ausreißerfreien Teilmenge ab. Sie ist unabhängig von der Gesamtzahl der Messwerte. </p><p>In nachstehender Tabelle ist die notwendige Anzahl von Wiederholungen abhängig vom Ausreißeranteil und von der Anzahl der erforderlichen Punkte, die zur Bestimmung der Modellparameter erforderlich sind, dargestellt. Die Wahrscheinlichkeit, mindestens eine ausreißerfreie Teilmenge aus allen Datenpunkten auszuwählen, ist dabei mit 99 % festgelegt. </p> <table class="wikitable" style="text-align:center;"> <caption>Anzahl der notwendigen Iterationen (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p=99\,\%}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>=</mo> <mn>99</mn> <mspace width="thinmathspace" /> <mi mathvariant="normal">%</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p=99\,\%}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c473960d1983491185239542124dab77398332be" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:9.005ex; height:2.676ex;" alt="{\displaystyle p=99\,\%}"></span>) </caption> <tbody><tr> <th rowspan="2">Beispiel </th> <th rowspan="2">Anzahl der<br />erforderlichen Punkte </th> <th colspan="7">Ausreißeranteil </th></tr> <tr> <th style="width:8%;">10 % </th> <th style="width:8%;">20 % </th> <th style="width:8%;">30 % </th> <th style="width:8%;">40 % </th> <th style="width:8%;">50 % </th> <th style="width:8%;">60 % </th> <th style="width:8%;">70 % </th></tr> <tr> <td>Gerade </td> <td>2 </td> <td>3 </td> <td>5 </td> <td>7 </td> <td>11 </td> <td>17 </td> <td>27 </td> <td>49 </td></tr> <tr> <td>Ebene </td> <td>3 </td> <td>4 </td> <td>7 </td> <td>11 </td> <td>19 </td> <td>35 </td> <td>70 </td> <td>169 </td></tr> <tr> <td><a href="/wiki/Epipolargeometrie#Eigenschaften_der_Fundamentalmatrix" title="Epipolargeometrie">Fundamentalmatrix</a> </td> <td>8 </td> <td>9 </td> <td>26 </td> <td>78 </td> <td>272 </td> <td>1177 </td> <td>7025 </td> <td>70188 </td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="Größe_des_Consensus_Sets"><span id="Gr.C3.B6.C3.9Fe_des_Consensus_Sets"></span>Größe des Consensus Sets</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=6" title="Abschnitt bearbeiten: Größe des Consensus Sets" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=6" title="Quellcode des Abschnitts bearbeiten: Größe des Consensus Sets"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In der allgemeinen Variante des Algorithmus muss dieser Wert nicht zwangsläufig bekannt sein, da bei Verzicht auf eine <a href="/wiki/Plausibilit%C3%A4tskontrolle" title="Plausibilitätskontrolle">Plausibilitätskontrolle</a> einfach der größte <i>Consensus Set</i> im weiteren Verlauf benutzt werden kann. Seine Kenntnis ist aber für die vorzeitig abbrechende Variante notwendig. Bei dieser wird die Mindestgröße des <i>Consensus Set</i> meist analytisch oder experimentell bestimmt. Eine gute Näherung ist die Gesamtmenge der Messwerte, abzüglich des Anteils an Ausreißern <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ϵ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3837cad72483d97bcdde49c85d3b7b859fb3fd2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }"></span>, der in den Daten vermutet wird. Für <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> Datenpunkte ist die Mindestgröße gleich <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1-\epsilon )\cdot n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> <mo>⋅</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (1-\epsilon )\cdot n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb8440397db5aad0bbf37de6468af9408fb25924" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.83ex; height:2.843ex;" alt="{\displaystyle (1-\epsilon )\cdot n}"></span>. Beispielsweise ist bei 12 Datenpunkten und 20 % Ausreißern die Mindestgröße näherungsweise 10. </p> <div class="mw-heading mw-heading2"><h2 id="Adaptive_Bestimmung_der_Parameter">Adaptive Bestimmung der Parameter</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=7" title="Abschnitt bearbeiten: Adaptive Bestimmung der Parameter" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=7" title="Quellcode des Abschnitts bearbeiten: Adaptive Bestimmung der Parameter"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Der Anteil der Ausreißer an der Gesamtmenge der Datenpunkte ist oft unbekannt. Somit ist es nicht möglich, die benötigte Zahl der Iterationen und die Mindestgröße eines <i>Consensus Set</i> zu bestimmen. In diesem Fall wird der Algorithmus mit der <a href="/wiki/Worst-Case" class="mw-redirect" title="Worst-Case">Worst-Case</a>-Annahme eines Ausreißeranteils von beispielsweise 50 % initialisiert und die Zahl der Iterationen und die Größe des <i>Consensus Set</i> entsprechend berechnet. Nach jeder Iteration werden die beiden Werte angepasst, wenn eine größere konsistente Menge gefunden wurde. Wird zum Beispiel der Algorithmus mit einem Ausreißeranteil von 50 % gestartet und enthält der berechnete <i>Consensus Set</i> aber 80 % aller Datenpunkte, ergibt sich ein verbesserter Wert für den Ausreißeranteil von 20 %. Die Zahl der Iterationen und die notwendige Größe des <i>Consensus Set</i> werden dann neu berechnet. </p> <div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=8" title="Abschnitt bearbeiten: Beispiel" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=8" title="Quellcode des Abschnitts bearbeiten: Beispiel"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In eine Menge von Punkten in der Ebene soll eine Gerade angepasst werden. Die Punkte sind im ersten Bild dargestellt. Im zweiten Bild ist das Ergebnis verschiedener Durchgänge eingezeichnet. Rote Punkte unterstützen die Gerade. Punkte, deren Abstand zur Gerade größer als die Fehlerschranke ist, sind blau eingefärbt. Das dritte Bild zeigt die gefundene Lösung nach 1000 Iterationsschritten. </p> <ul class="gallery mw-gallery-traditional"> <li class="gallerycaption">RANSAC zum Anpassen einer Geraden an Datenpunkte</li> <li class="gallerybox" style="width: 235px"> <div class="thumb" style="width: 230px; height: 180px;"><span typeof="mw:File"><a href="/wiki/Datei:RANSAC_LINIE_Datenpunkte.png" class="mw-file-description" title="1. Original-Datensatz."><img alt="1. Original-Datensatz." src="//upload.wikimedia.org/wikipedia/commons/thumb/5/5e/RANSAC_LINIE_Datenpunkte.png/200px-RANSAC_LINIE_Datenpunkte.png" decoding="async" width="200" height="150" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/5e/RANSAC_LINIE_Datenpunkte.png/300px-RANSAC_LINIE_Datenpunkte.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/5e/RANSAC_LINIE_Datenpunkte.png/400px-RANSAC_LINIE_Datenpunkte.png 2x" data-file-width="639" data-file-height="480" /></a></span></div> <div class="gallerytext">1. Original-Datensatz.</div> </li> <li class="gallerybox" style="width: 235px"> <div class="thumb" style="width: 230px; height: 180px;"><span typeof="mw:File"><a href="/wiki/Datei:RANSAC_LINIE_Animiert.gif" class="mw-file-description" title="2. Animation mehrerer Iterationen."><img alt="2. Animation mehrerer Iterationen." src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c0/RANSAC_LINIE_Animiert.gif/200px-RANSAC_LINIE_Animiert.gif" decoding="async" width="200" height="150" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c0/RANSAC_LINIE_Animiert.gif/300px-RANSAC_LINIE_Animiert.gif 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c0/RANSAC_LINIE_Animiert.gif/400px-RANSAC_LINIE_Animiert.gif 2x" data-file-width="639" data-file-height="480" /></a></span></div> <div class="gallerytext">2. Animation mehrerer Iterationen.</div> </li> <li class="gallerybox" style="width: 235px"> <div class="thumb" style="width: 230px; height: 180px;"><span typeof="mw:File"><a href="/wiki/Datei:RANSAC_LINIE_Loesung.png" class="mw-file-description" title="3. Ergebnis nach 1000 Iterationen."><img alt="3. Ergebnis nach 1000 Iterationen." src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a5/RANSAC_LINIE_Loesung.png/200px-RANSAC_LINIE_Loesung.png" decoding="async" width="200" height="150" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a5/RANSAC_LINIE_Loesung.png/300px-RANSAC_LINIE_Loesung.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a5/RANSAC_LINIE_Loesung.png/400px-RANSAC_LINIE_Loesung.png 2x" data-file-width="640" data-file-height="480" /></a></span></div> <div class="gallerytext">3. Ergebnis nach 1000 Iterationen.</div> </li> </ul> <div class="mw-heading mw-heading2"><h2 id="Weiterentwicklungen">Weiterentwicklungen</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=9" title="Abschnitt bearbeiten: Weiterentwicklungen" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=9" title="Quellcode des Abschnitts bearbeiten: Weiterentwicklungen"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Es gibt einige Erweiterungen von RANSAC, von denen hier zwei wichtige vorgestellt werden. </p> <div class="mw-heading mw-heading3"><h3 id="LO-RANSAC">LO-RANSAC</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=10" title="Abschnitt bearbeiten: LO-RANSAC" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=10" title="Quellcode des Abschnitts bearbeiten: LO-RANSAC"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Datei:RANSAC_PROBLEM_INLIENER.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c8/RANSAC_PROBLEM_INLIENER.png/220px-RANSAC_PROBLEM_INLIENER.png" decoding="async" width="220" height="165" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c8/RANSAC_PROBLEM_INLIENER.png/330px-RANSAC_PROBLEM_INLIENER.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c8/RANSAC_PROBLEM_INLIENER.png/440px-RANSAC_PROBLEM_INLIENER.png 2x" data-file-width="640" data-file-height="480" /></a><figcaption>Modellgerade wird nicht durch alle fehlerfreien Punkte unterstützt.</figcaption></figure> <p>Es hat sich in Experimenten gezeigt, dass meist mehr Iterationsschritte als die theoretisch ausreichende Anzahl nötig sind: Wird mit einer ausreißerfreien Menge von Punkten ein Modell berechnet, so müssen nicht alle anderen Werte, die keine Ausreißer sind, dieses Modell unterstützen. Das Problem ist in nebenstehender Abbildung illustriert. Obwohl die Gerade mittels zweier fehlerfreier Werte berechnet wurde (schwarze Punkte), werden einige andere offensichtlich richtige Punkte rechts oben im Bild als Ausreißer (blaue Sterne) klassifiziert. </p><p>Aus diesem Grund wird der ursprüngliche Algorithmus bei LO-RANSAC (local optimised RANSAC) im Schritt 3 erweitert. Zuerst wird wie üblich die Teilmenge der Punkte bestimmt, die keine Ausreißer sind. Danach wird mittels dieser Menge und unter Zuhilfenahme eines beliebigen Ausgleichsverfahrens wie der Methode der kleinsten Quadrate das Modell nochmals bestimmt. Als letztes wird die Teilmenge berechnet, deren Abstand zu diesem optimierten Modell kleiner als die Fehlerschranke ist. Erst diese verbesserte Teilmenge wird als <i>Consensus Set</i> gespeichert.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="MSAC">MSAC</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=11" title="Abschnitt bearbeiten: MSAC" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=11" title="Quellcode des Abschnitts bearbeiten: MSAC"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Bei RANSAC wird das Modell ausgewählt, welches durch die meisten Messwerte unterstützt wird. Dies entspricht der Minimierung einer Summe <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}"></span>, bei der alle fehlerfreien Werte mit 0 und alle Ausreißer mit einem konstanten Wert eingehen: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=\sum _{i}p({\text{Fehler}})\quad {\text{mit}}\quad p=\left\{{\begin{array}{ll}0,&{\text{wenn Fehler}}<{\text{Fehlerschranke}}\\{\text{konstant}}&{\text{wenn Fehler}}\geq {\text{Fehlerschranke}}\end{array}}\right.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </munder> <mi>p</mi> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>Fehler</mtext> </mrow> <mo stretchy="false">)</mo> <mspace width="1em" /> <mrow class="MJX-TeXAtom-ORD"> <mtext>mit</mtext> </mrow> <mspace width="1em" /> <mi>p</mi> <mo>=</mo> <mrow> <mo>{</mo> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="left left" rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>0</mn> <mo>,</mo> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>wenn Fehler</mtext> </mrow> <mo><</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>Fehlerschranke</mtext> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>konstant</mtext> </mrow> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>wenn Fehler</mtext> </mrow> <mo>≥</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>Fehlerschranke</mtext> </mrow> </mtd> </mtr> </mtable> </mrow> <mo fence="true" stretchy="true" symmetric="true"></mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C=\sum _{i}p({\text{Fehler}})\quad {\text{mit}}\quad p=\left\{{\begin{array}{ll}0,&{\text{wenn Fehler}}<{\text{Fehlerschranke}}\\{\text{konstant}}&{\text{wenn Fehler}}\geq {\text{Fehlerschranke}}\end{array}}\right.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4ff5f5f71afbd92aa9c87086c80e160268416469" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:74.809ex; height:6.676ex;" alt="{\displaystyle C=\sum _{i}p({\text{Fehler}})\quad {\text{mit}}\quad p=\left\{{\begin{array}{ll}0,&{\text{wenn Fehler}}<{\text{Fehlerschranke}}\\{\text{konstant}}&{\text{wenn Fehler}}\geq {\text{Fehlerschranke}}\end{array}}\right.}"></span></dd></dl> <p>Das berechnete Modell kann sehr ungenau sein, wenn die Fehlerschranke zu hoch angesetzt wurde – je höher diese ist, desto mehr Lösungen haben gleiche Werte für <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}"></span>. Im Extremfall sind alle Fehler der Messwerte kleiner als die Fehlerschranke, so dass <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}"></span> immer 0 ist. Damit können keine Ausreißer erkannt werden, und RANSAC liefert eine schlechte Schätzung. </p><p>MSAC (<b>M</b>-Estimator <b>SA</b>mple <b>C</b>onsensus) ist eine Erweiterung von RANSAC, die eine modifizierte zu minimierende Zielfunktion benutzt: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=\sum _{i}p({\text{Fehler}})\quad {\text{mit}}\quad p=\left\{{\begin{array}{ll}{\text{Fehler,}}&{\text{wenn Fehler}}<{\text{Fehlerschranke}}\\{\text{konstanter Wert groesser als Fehlerschranke,}}&{\text{wenn Fehler}}\geq {\text{Fehlerschranke}}\end{array}}\right.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </munder> <mi>p</mi> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>Fehler</mtext> </mrow> <mo stretchy="false">)</mo> <mspace width="1em" /> <mrow class="MJX-TeXAtom-ORD"> <mtext>mit</mtext> </mrow> <mspace width="1em" /> <mi>p</mi> <mo>=</mo> <mrow> <mo>{</mo> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="left left" rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>Fehler,</mtext> </mrow> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>wenn Fehler</mtext> </mrow> <mo><</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>Fehlerschranke</mtext> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>konstanter Wert groesser als Fehlerschranke,</mtext> </mrow> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mtext>wenn Fehler</mtext> </mrow> <mo>≥</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>Fehlerschranke</mtext> </mrow> </mtd> </mtr> </mtable> </mrow> <mo fence="true" stretchy="true" symmetric="true"></mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C=\sum _{i}p({\text{Fehler}})\quad {\text{mit}}\quad p=\left\{{\begin{array}{ll}{\text{Fehler,}}&{\text{wenn Fehler}}<{\text{Fehlerschranke}}\\{\text{konstanter Wert groesser als Fehlerschranke,}}&{\text{wenn Fehler}}\geq {\text{Fehlerschranke}}\end{array}}\right.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a6fe929103012a84ce0acf221cfec41d066352dc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:111.032ex; height:6.676ex;" alt="{\displaystyle C=\sum _{i}p({\text{Fehler}})\quad {\text{mit}}\quad p=\left\{{\begin{array}{ll}{\text{Fehler,}}&{\text{wenn Fehler}}<{\text{Fehlerschranke}}\\{\text{konstanter Wert groesser als Fehlerschranke,}}&{\text{wenn Fehler}}\geq {\text{Fehlerschranke}}\end{array}}\right.}"></span></dd></dl> <p>Mit dieser Funktion erhalten Ausreißer weiterhin eine bestimmte „Strafe“, die größer als die Fehlerschranke ist. Werte unterhalb der Fehlerschranke gehen direkt mit dem Fehler anstelle von 0 in die Summe ein. Dadurch wird das angesprochene Problem beseitigt, da ein Punkt umso weniger zur Summe beiträgt, je besser er zum Modell passt.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=12" title="Abschnitt bearbeiten: Einzelnachweise" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=12" title="Quellcode des Abschnitts bearbeiten: Einzelnachweise"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Robert C. Bolles: <cite style="font-style:italic">Homepage beim SRI</cite>. (<a rel="nofollow" class="external text" href="https://www.ai.sri.com/people/bolles/">online</a> [abgerufen am 11. März 2008]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=Robert+C.+Bolles&rft.btitle=Homepage+beim+SRI&rft.genre=book" style="display:none"> </span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">Martin A. Fischler: <cite style="font-style:italic">Homepage beim SRI</cite>. (<a rel="nofollow" class="external text" href="https://www.ai.sri.com/people/fischler/">online</a> [abgerufen am 11. März 2008]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=Martin+A.+Fischler&rft.btitle=Homepage+beim+SRI&rft.genre=book" style="display:none"> </span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">Martin A. Fischler und Robert C. Bolles: <cite style="font-style:italic">Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography</cite>. März 1980 (<a rel="nofollow" class="external text" href="https://www.ai.sri.com/pubs/files/708.pdf">online</a> [PDF; <span style="white-space:nowrap">301<span style="display:inline-block;width:.2em"> </span>kB</span>; abgerufen am 13. September 2007]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=Martin+A.+Fischler+und+Robert+C.+Bolles&rft.btitle=Random+Sample+Consensus%3A+A+Paradigm+for+Model+Fitting+with+Applications+to+Image+Analysis+and+Automated+Cartography&rft.date=1980-03&rft.genre=book" style="display:none"> </span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text">Cantzler, H. "Random sample consensus (ransac)." <i>Institute for Perception, Action and Behaviour, Division of Informatics, University of Edinburgh</i> (1981). <a rel="nofollow" class="external free" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3035&rep=rep1&type=pdf">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3035&rep=rep1&type=pdf</a></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><a href="#cite_ref-5">↑</a></span> <span class="reference-text">Dag Ewering: <cite style="font-style:italic">Modellbasiertes Tracking mittels Linien- und Punktkorrelationen</cite>. September 2006 (<a rel="nofollow" class="external text" href="http://kola.opus.hbz-nrw.de/volltexte/2006/38/pdf/DiplomarbeitEwering.pdf">online</a> [PDF; <span style="white-space:nowrap">9,5<span style="display:inline-block;width:.2em"> </span>MB</span>; abgerufen am 2. August 2007]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=Dag+Ewering&rft.btitle=Modellbasiertes+Tracking+mittels+Linien-+und+Punktkorrelationen&rft.date=2006-09&rft.genre=book" style="display:none"> </span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><a href="#cite_ref-6">↑</a></span> <span class="reference-text">Martin A. Fischler und Robert C. Bolles: <cite style="font-style:italic">RANSAC: An Historical Perspective</cite>. 6. Juni 2006 (<a rel="nofollow" class="external text" href="http://cmp.felk.cvut.cz/ransac-cvpr2006/tutorial/R25-Bolles.ppt">online</a> [PPT; <span style="white-space:nowrap">2,8<span style="display:inline-block;width:.2em"> </span>MB</span>; abgerufen am 11. März 2008]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=Martin+A.+Fischler+und+Robert+C.+Bolles&rft.btitle=RANSAC%3A+An+Historical+Perspective&rft.date=2006-06-06&rft.genre=book" style="display:none"> </span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><a href="#cite_ref-7">↑</a></span> <span class="reference-text">Christian Beder und <a href="/wiki/Wolfgang_F%C3%B6rstner" title="Wolfgang Förstner">Wolfgang Förstner</a>: <cite style="font-style:italic">Direkte Bestimmung von Zylindern aus 3D-Punkten ohne Nutzung von Oberflächennormalen</cite>. 2006 (<a rel="nofollow" class="external text" href="http://www.ipb.uni-bonn.de/pdfs/Beder2006Direkte.pdf">uni-bonn.de</a> [PDF; abgerufen am 25. August 2016]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=Christian+Beder+und+Wolfgang+F%C3%B6rstner&rft.btitle=Direkte+Bestimmung+von+Zylindern+aus+3D-Punkten+ohne+Nutzung+von+Oberfl%C3%A4chennormalen&rft.date=2006&rft.genre=book" style="display:none"> </span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><a href="#cite_ref-8">↑</a></span> <span class="reference-text">Ondřej Chum, Jiři Matas and Štěpàn Obdržàlek: <cite style="font-style:italic">Enhancing RANSAC By Generalized Model Optimization</cite>. 2004 (<a rel="nofollow" class="external text" href="ftp://cmp.felk.cvut.cz/pub/cmp/articles/chum/chum-accv04.pdf">online</a> [PDF; abgerufen am 7. August 2007]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=Ond%C5%99ej+Chum%2C+Ji%C5%99i+Matas+and+%C5%A0t%C4%9Bp%C3%A0n+Obdr%C5%BE%C3%A0lek&rft.btitle=Enhancing+RANSAC+By+Generalized+Model+Optimization&rft.date=2004&rft.genre=book" style="display:none"> </span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><a href="#cite_ref-9">↑</a></span> <span class="reference-text">P.H.S. Torr und A. Zisserman: <cite style="font-style:italic">MLESAC: A new robust estimator with application to estimating image geometry</cite>. 1996 (<a rel="nofollow" class="external text" href="http://www.robots.ox.ac.uk/~vgg/publications/papers/torr00.pdf">online</a> [PDF; <span style="white-space:nowrap">855<span style="display:inline-block;width:.2em"> </span>kB</span>; abgerufen am 7. August 2007]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=P.H.S.+Torr+und+A.+Zisserman&rft.btitle=MLESAC%3A+A+new+robust+estimator+with+application+to+estimating+image+geometry&rft.date=1996&rft.genre=book" style="display:none"> </span></span> </li> </ol> <div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit&section=13" title="Abschnitt bearbeiten: Literatur" class="mw-editsection-visualeditor"><span>Bearbeiten</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit&section=13" title="Quellcode des Abschnitts bearbeiten: Literatur"><span>Quelltext bearbeiten</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><span class="cite">Martin A. Fischler und Robert C. Bolles: <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190405162514/https://www.sri.com/sites/default/files/publications/ransac-publication.pdf"><i>Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography.</i></a> (PDF; 1,2 MB) 1981, archiviert vom <style data-mw-deduplicate="TemplateStyles:r235239667">.mw-parser-output .dewiki-iconexternal>a{background-position:center right;background-repeat:no-repeat}body.skin-minerva .mw-parser-output .dewiki-iconexternal>a{background-image:url("https://upload.wikimedia.org/wikipedia/commons/a/a4/OOjs_UI_icon_external-link-ltr-progressive.svg")!important;background-size:10px;padding-right:13px!important}body.skin-timeless .mw-parser-output .dewiki-iconexternal>a,body.skin-monobook .mw-parser-output .dewiki-iconexternal>a{background-image:url("https://upload.wikimedia.org/wikipedia/commons/3/30/MediaWiki_external_link_icon.svg")!important;padding-right:13px!important}body.skin-vector .mw-parser-output .dewiki-iconexternal>a{background-image:url("https://upload.wikimedia.org/wikipedia/commons/9/96/Link-external-small-ltr-progressive.svg")!important;background-size:0.857em;padding-right:1em!important}</style><span class="dewiki-iconexternal"><a class="external text" href="https://redirecter.toolforge.org/?url=https%3A%2F%2Fwww.sri.com%2Fsites%2Fdefault%2Ffiles%2Fpublications%2Fransac-publication.pdf">Original</a></span> (nicht mehr online verfügbar) am <span style="white-space:nowrap;">5. April 2019</span><span>;</span><span class="Abrufdatum"> abgerufen am 14. Oktober 2019</span>.</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3ARANSAC-Algorithmus&rft.title=Random+Sample+Consensus%3A+A+Paradigm+for+Model+Fitting+with+Applications+to+Image+Analysis+and+Automated+Cartography&rft.description=Random+Sample+Consensus%3A+A+Paradigm+for+Model+Fitting+with+Applications+to+Image+Analysis+and+Automated+Cartography&rft.identifier=https%3A%2F%2Fweb.archive.org%2Fweb%2F20190405162514%2Fhttps%3A%2F%2Fwww.sri.com%2Fsites%2Fdefault%2Ffiles%2Fpublications%2Fransac-publication.pdf&rft.creator=Martin+A.+Fischler+und+Robert+C.+Bolles&rft.date=1981&rft.source=https://www.sri.com/sites/default/files/publications/ransac-publication.pdf"> </span></li> <li><span class="cite">Verschiedene Autoren: <a rel="nofollow" class="external text" href="http://cmp.felk.cvut.cz/ransac-cvpr2006/"><i>25 Years of RANSAC, Workshop in conjunction with CVPR 2006.</i></a> 2006,<span class="Abrufdatum"> abgerufen am 11. März 2008</span>.</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3ARANSAC-Algorithmus&rft.title=25+Years+of+RANSAC%2C+Workshop+in+conjunction+with+CVPR+2006&rft.description=25+Years+of+RANSAC%2C+Workshop+in+conjunction+with+CVPR+2006&rft.identifier=http%3A%2F%2Fcmp.felk.cvut.cz%2Fransac-cvpr2006%2F&rft.creator=Verschiedene+Autoren&rft.date=2006"> </span></li> <li><span class="cite">Peter Kovesi: <a rel="nofollow" class="external text" href="http://www.csse.uwa.edu.au/~pk/research/matlabfns/Robust/ransac.m"><i>RANSAC – Robustly fits a model to data with the RANSAC algorithm (Matlab-Implementation).</i></a> 2007,<span class="Abrufdatum"> abgerufen am 11. März 2008</span>.</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3ARANSAC-Algorithmus&rft.title=RANSAC+%E2%80%93+Robustly+fits+a+model+to+data+with+the+RANSAC+algorithm+%28Matlab-Implementation%29&rft.description=RANSAC+%E2%80%93+Robustly+fits+a+model+to+data+with+the+RANSAC+algorithm+%28Matlab-Implementation%29&rft.identifier=http%3A%2F%2Fwww.csse.uwa.edu.au%2F%7Epk%2Fresearch%2Fmatlabfns%2FRobust%2Fransac.m&rft.creator=Peter+Kovesi&rft.date=2007"> </span></li> <li>Volker Rodehorst: <cite style="font-style:italic">Photogrammetrische 3D-Rekonstruktion im Nahbereich durch Auto-Kalibrierung mit projektiver Geometrie</cite>. wvb Wissenschaftlicher Verlag Berlin, 2004, <a href="/wiki/Spezial:ISBN-Suche/9783936846836" class="internal mw-magiclink-isbn">ISBN 978-3-936846-83-6</a> (Hochschulschrift, zugl. Dissertation, <a href="/wiki/TU_Berlin" class="mw-redirect" title="TU Berlin">TU Berlin</a> 2004).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=Volker+Rodehorst&rft.btitle=Photogrammetrische+3D-Rekonstruktion+im+Nahbereich+durch+Auto-Kalibrierung+mit+projektiver+Geometrie&rft.date=2004&rft.genre=book&rft.isbn=9783936846836&rft.pub=wvb+Wissenschaftlicher+Verlag+Berlin" style="display:none"> </span></li> <li>Richard Hartley, Andrew Zisserman: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Multiple View Geometry in Computer Vision</cite>. 2. Auflage. Cambridge University Press, Cambridge, UK 2004, <a href="/wiki/Spezial:ISBN-Suche/9780521540513" class="internal mw-magiclink-isbn">ISBN 978-0-521-54051-3</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=Richard+Hartley%2C+Andrew+Zisserman&rft.btitle=Multiple+View+Geometry+in+Computer+Vision&rft.date=2004&rft.edition=2.&rft.genre=book&rft.isbn=9780521540513&rft.place=Cambridge%2C+UK&rft.pub=Cambridge+University+Press" style="display:none"> </span></li> <li>Tilo Strutz: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Data Fitting and Uncertainty (A practical introduction to weighted least squares and beyond)</cite>. 2nd edition Auflage. Springer Vieweg, 2016, <a href="/wiki/Spezial:ISBN-Suche/9783658114558" class="internal mw-magiclink-isbn">ISBN 978-3-658-11455-8</a> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:RANSAC-Algorithmus&rft.au=Tilo+Strutz&rft.btitle=Data+Fitting+and+Uncertainty+%28A+practical+introduction+to+weighted+least+squares+and+beyond%29&rft.date=2016&rft.edition=2nd+edition&rft.genre=book&rft.isbn=9783658114558&rft.pub=Springer+Vieweg" style="display:none"> </span></li></ul> <div class="hintergrundfarbe1 rahmenfarbe1 navigation-not-searchable noprint" style="border-top-style: solid; border-top-width: 1px; clear: both; margin-top:1em; padding: 0.25em; overflow: hidden; word-break: break-word; word-wrap: break-word;" id="Vorlage_Exzellent"><div class="noviewer noresize" style="display: table-cell; padding-bottom: 0.2em; padding-left: 0.25em; padding-right: 1em; padding-top: 0.2em; vertical-align: middle;" aria-hidden="true" role="presentation"><span typeof="mw:File"><a href="/wiki/Wikipedia:Exzellente_Artikel" title="Wikipedia:Exzellente Artikel"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/4/41/Qsicon_Exzellent.svg/24px-Qsicon_Exzellent.svg.png" decoding="async" width="24" height="24" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/41/Qsicon_Exzellent.svg/36px-Qsicon_Exzellent.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/41/Qsicon_Exzellent.svg/48px-Qsicon_Exzellent.svg.png 2x" data-file-width="24" data-file-height="24" /></a></span></div> <div style="display: table-cell; vertical-align: middle; width: 100%;"> <div role="contentinfo"> Dieser Artikel wurde am 3. April 2008 in <a href="/wiki/Spezial:Permanenter_Link/44465130" title="Spezial:Permanenter Link/44465130">dieser Version</a> in die Liste der <a href="/wiki/Wikipedia:Exzellente_Artikel" title="Wikipedia:Exzellente Artikel">exzellenten Artikel</a> aufgenommen.</div> </div></div></div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Abgerufen von „<a dir="ltr" href="https://de.wikipedia.org/w/index.php?title=RANSAC-Algorithmus&oldid=239854521">https://de.wikipedia.org/w/index.php?title=RANSAC-Algorithmus&oldid=239854521</a>“</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Wikipedia:Kategorien" title="Wikipedia:Kategorien">Kategorien</a>: <ul><li><a href="/wiki/Kategorie:Wikipedia:Exzellent" title="Kategorie:Wikipedia:Exzellent">Wikipedia:Exzellent</a></li><li><a href="/wiki/Kategorie:Computer_Vision" title="Kategorie:Computer Vision">Computer Vision</a></li><li><a href="/wiki/Kategorie:Algorithmus" title="Kategorie:Algorithmus">Algorithmus</a></li><li><a href="/wiki/Kategorie:Regressionsanalyse" title="Kategorie:Regressionsanalyse">Regressionsanalyse</a></li></ul></div></div> </div> </div> <div id="mw-navigation"> <h2>Navigationsmenü</h2> <div id="mw-head"> <nav id="p-personal" class="mw-portlet mw-portlet-personal vector-user-menu-legacy vector-menu" aria-labelledby="p-personal-label" > <h3 id="p-personal-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Meine Werkzeuge</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anonuserpage" class="mw-list-item"><span title="Benutzerseite der IP-Adresse, von der aus du Änderungen durchführst">Nicht angemeldet</span></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Spezial:Meine_Diskussionsseite" title="Diskussion über Änderungen von dieser IP-Adresse [n]" accesskey="n"><span>Diskussionsseite</span></a></li><li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Spezial:Meine_Beitr%C3%A4ge" title="Eine Liste der Bearbeitungen, die von dieser IP-Adresse gemacht wurden [y]" accesskey="y"><span>Beiträge</span></a></li><li id="pt-createaccount" class="mw-list-item"><a href="/w/index.php?title=Spezial:Benutzerkonto_anlegen&returnto=RANSAC-Algorithmus" title="Wir ermutigen dich dazu, ein Benutzerkonto zu erstellen und dich anzumelden. Es ist jedoch nicht zwingend erforderlich."><span>Benutzerkonto erstellen</span></a></li><li id="pt-login" class="mw-list-item"><a href="/w/index.php?title=Spezial:Anmelden&returnto=RANSAC-Algorithmus" title="Anmelden ist zwar keine Pflicht, wird aber gerne gesehen. [o]" accesskey="o"><span>Anmelden</span></a></li> </ul> </div> </nav> <div id="left-navigation"> <nav id="p-namespaces" class="mw-portlet mw-portlet-namespaces vector-menu-tabs vector-menu-tabs-legacy vector-menu" aria-labelledby="p-namespaces-label" > <h3 id="p-namespaces-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Namensräume</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected mw-list-item"><a href="/wiki/RANSAC-Algorithmus" title="Seiteninhalt anzeigen [c]" accesskey="c"><span>Artikel</span></a></li><li id="ca-talk" class="mw-list-item"><a href="/wiki/Diskussion:RANSAC-Algorithmus" rel="discussion" title="Diskussion zum Seiteninhalt [t]" accesskey="t"><span>Diskussion</span></a></li> </ul> </div> </nav> <nav id="p-variants" class="mw-portlet mw-portlet-variants emptyPortlet vector-menu-dropdown vector-menu" aria-labelledby="p-variants-label" > <input type="checkbox" id="p-variants-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-variants" class="vector-menu-checkbox" aria-labelledby="p-variants-label" > <label id="p-variants-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Deutsch</span> </label> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </nav> </div> <div id="right-navigation"> <nav id="p-views" class="mw-portlet mw-portlet-views vector-menu-tabs vector-menu-tabs-legacy vector-menu" aria-labelledby="p-views-label" > <h3 id="p-views-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Ansichten</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected mw-list-item"><a href="/wiki/RANSAC-Algorithmus"><span>Lesen</span></a></li><li id="ca-ve-edit" class="mw-list-item"><a href="/w/index.php?title=RANSAC-Algorithmus&veaction=edit" title="Diese Seite mit dem VisualEditor bearbeiten [v]" accesskey="v"><span>Bearbeiten</span></a></li><li id="ca-edit" class="collapsible mw-list-item"><a href="/w/index.php?title=RANSAC-Algorithmus&action=edit" title="Den Quelltext dieser Seite bearbeiten [e]" accesskey="e"><span>Quelltext bearbeiten</span></a></li><li id="ca-history" class="mw-list-item"><a href="/w/index.php?title=RANSAC-Algorithmus&action=history" title="Frühere Versionen dieser Seite [h]" accesskey="h"><span>Versionsgeschichte</span></a></li> </ul> </div> </nav> <nav id="p-cactions" class="mw-portlet mw-portlet-cactions emptyPortlet vector-menu-dropdown vector-menu" aria-labelledby="p-cactions-label" title="Weitere Optionen" > <input type="checkbox" id="p-cactions-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-cactions" class="vector-menu-checkbox" aria-labelledby="p-cactions-label" > <label id="p-cactions-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Weitere</span> </label> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </nav> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <h3 >Suche</h3> <form action="/w/index.php" id="searchform" class="vector-search-box-form"> <div id="simpleSearch" class="vector-search-box-inner" data-search-loc="header-navigation"> <input class="vector-search-box-input" type="search" name="search" placeholder="Wikipedia durchsuchen" aria-label="Wikipedia durchsuchen" autocapitalize="sentences" title="Durchsuche die Wikipedia [f]" accesskey="f" id="searchInput" > <input type="hidden" name="title" value="Spezial:Suche"> <input id="mw-searchButton" class="searchButton mw-fallbackSearchButton" type="submit" name="fulltext" title="Suche nach Seiten, die diesen Text enthalten" value="Suchen"> <input id="searchButton" class="searchButton" type="submit" name="go" title="Gehe direkt zu der Seite mit genau diesem Namen, falls sie vorhanden ist." value="Artikel"> </div> </form> </div> </div> </div> <div id="mw-panel" class="vector-legacy-sidebar"> <div id="p-logo" role="banner"> <a class="mw-wiki-logo" href="/wiki/Wikipedia:Hauptseite" title="Hauptseite"></a> </div> <nav id="p-navigation" class="mw-portlet mw-portlet-navigation vector-menu-portal portal vector-menu" aria-labelledby="p-navigation-label" > <h3 id="p-navigation-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Navigation</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Wikipedia:Hauptseite" title="Hauptseite besuchen [z]" accesskey="z"><span>Hauptseite</span></a></li><li id="n-topics" class="mw-list-item"><a href="/wiki/Portal:Wikipedia_nach_Themen"><span>Themenportale</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Spezial:Zuf%C3%A4llige_Seite" title="Zufällige Seite aufrufen [x]" accesskey="x"><span>Zufälliger Artikel</span></a></li> </ul> </div> </nav> <nav id="p-Mitmachen" class="mw-portlet mw-portlet-Mitmachen vector-menu-portal portal vector-menu" aria-labelledby="p-Mitmachen-label" > <h3 id="p-Mitmachen-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Mitmachen</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-Artikel-verbessern" class="mw-list-item"><a href="/wiki/Wikipedia:Beteiligen"><span>Artikel verbessern</span></a></li><li id="n-Neuerartikel" class="mw-list-item"><a href="/wiki/Hilfe:Neuen_Artikel_anlegen"><span>Neuen Artikel anlegen</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Autorenportal" title="Info-Zentrum über Beteiligungsmöglichkeiten"><span>Autorenportal</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Hilfe:%C3%9Cbersicht" title="Übersicht über Hilfeseiten"><span>Hilfe</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Spezial:Letzte_%C3%84nderungen" title="Liste der letzten Änderungen in Wikipedia [r]" accesskey="r"><span>Letzte Änderungen</span></a></li><li id="n-contact" class="mw-list-item"><a href="/wiki/Wikipedia:Kontakt" title="Kontaktmöglichkeiten"><span>Kontakt</span></a></li><li id="n-sitesupport" class="mw-list-item"><a href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_de.wikipedia.org&uselang=de" title="Unterstütze uns"><span>Spenden</span></a></li> </ul> </div> </nav> <nav id="p-tb" class="mw-portlet mw-portlet-tb vector-menu-portal portal vector-menu" aria-labelledby="p-tb-label" > <h3 id="p-tb-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Werkzeuge</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Spezial:Linkliste/RANSAC-Algorithmus" title="Liste aller Seiten, die hierher verlinken [j]" accesskey="j"><span>Links auf diese Seite</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Spezial:%C3%84nderungen_an_verlinkten_Seiten/RANSAC-Algorithmus" rel="nofollow" title="Letzte Änderungen an Seiten, die von hier verlinkt sind [k]" accesskey="k"><span>Änderungen an verlinkten Seiten</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Spezial:Spezialseiten" title="Liste aller Spezialseiten [q]" accesskey="q"><span>Spezialseiten</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=RANSAC-Algorithmus&oldid=239854521" title="Dauerhafter Link zu dieser Seitenversion"><span>Permanenter Link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=RANSAC-Algorithmus&action=info" title="Weitere Informationen über diese Seite"><span>Seiteninformationen</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Spezial:Zitierhilfe&page=RANSAC-Algorithmus&id=239854521&wpFormIdentifier=titleform" title="Hinweise, wie diese Seite zitiert werden kann"><span>Artikel zitieren</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Spezial:URL-K%C3%BCrzung&url=https%3A%2F%2Fde.wikipedia.org%2Fwiki%2FRANSAC-Algorithmus"><span>Kurzlink</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Spezial:QrCode&url=https%3A%2F%2Fde.wikipedia.org%2Fwiki%2FRANSAC-Algorithmus"><span>QR-Code herunterladen</span></a></li> </ul> </div> </nav> <nav id="p-coll-print_export" class="mw-portlet mw-portlet-coll-print_export vector-menu-portal portal vector-menu" aria-labelledby="p-coll-print_export-label" > <h3 id="p-coll-print_export-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">Drucken/exportieren</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Spezial:DownloadAsPdf&page=RANSAC-Algorithmus&action=show-download-screen"><span>Als PDF herunterladen</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=RANSAC-Algorithmus&printable=yes" title="Druckansicht dieser Seite [p]" accesskey="p"><span>Druckversion</span></a></li> </ul> </div> </nav> <nav id="p-wikibase-otherprojects" class="mw-portlet mw-portlet-wikibase-otherprojects vector-menu-portal portal vector-menu" aria-labelledby="p-wikibase-otherprojects-label" > <h3 id="p-wikibase-otherprojects-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">In anderen Projekten</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q218533" title="Link zum verbundenen Objekt im Datenrepositorium [g]" accesskey="g"><span>Wikidata-Datenobjekt</span></a></li> </ul> </div> </nav> <nav id="p-lang" class="mw-portlet mw-portlet-lang vector-menu-portal portal vector-menu" aria-labelledby="p-lang-label" > <h3 id="p-lang-label" class="vector-menu-heading " > <span class="vector-menu-heading-label">In anderen Sprachen</span> </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%AA%D9%88%D8%A7%D9%81%D9%82_%D8%A7%D9%84%D8%B9%D9%8A%D9%86%D8%A7%D8%AA_%D8%A7%D9%84%D8%B9%D8%B4%D9%88%D8%A7%D8%A6%D9%8A%D8%A9" title="توافق العينات العشوائية – Arabisch" lang="ar" hreflang="ar" data-title="توافق العينات العشوائية" data-language-autonym="العربية" data-language-local-name="Arabisch" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Consens_de_mostra_aleat%C3%B2ria" title="Consens de mostra aleatòria – Katalanisch" lang="ca" hreflang="ca" data-title="Consens de mostra aleatòria" data-language-autonym="Català" data-language-local-name="Katalanisch" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Random_sample_consensus" title="Random sample consensus – Englisch" lang="en" hreflang="en" data-title="Random sample consensus" data-language-autonym="English" data-language-local-name="Englisch" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/RANSAC" title="RANSAC – Spanisch" lang="es" hreflang="es" data-title="RANSAC" data-language-autonym="Español" data-language-local-name="Spanisch" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%A7%D8%AC%D9%85%D8%A7%D8%B9_%D9%86%D9%85%D9%88%D9%86%D9%87_%D8%AA%D8%B5%D8%A7%D8%AF%D9%81%DB%8C" title="اجماع نمونه تصادفی – Persisch" lang="fa" hreflang="fa" data-title="اجماع نمونه تصادفی" data-language-autonym="فارسی" data-language-local-name="Persisch" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/RANSAC" title="RANSAC – Französisch" lang="fr" hreflang="fr" data-title="RANSAC" data-language-autonym="Français" data-language-local-name="Französisch" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/RANSAC" title="RANSAC – Italienisch" lang="it" hreflang="it" data-title="RANSAC" data-language-autonym="Italiano" data-language-local-name="Italienisch" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/RANSAC" title="RANSAC – Portugiesisch" lang="pt" hreflang="pt" data-title="RANSAC" data-language-autonym="Português" data-language-local-name="Portugiesisch" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/RANSAC" title="RANSAC – Russisch" lang="ru" hreflang="ru" data-title="RANSAC" data-language-autonym="Русский" data-language-local-name="Russisch" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/RANSAC" title="RANSAC – Ukrainisch" lang="uk" hreflang="uk" data-title="RANSAC" data-language-autonym="Українська" data-language-local-name="Ukrainisch" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E9%9A%A8%E6%A9%9F%E6%8A%BD%E6%A8%A3%E4%B8%80%E8%87%B4" title="隨機抽樣一致 – Chinesisch" lang="zh" hreflang="zh" data-title="隨機抽樣一致" data-language-autonym="中文" data-language-local-name="Chinesisch" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q218533#sitelinks-wikipedia" title="Links auf Artikel in anderen Sprachen bearbeiten" class="wbc-editpage">Links bearbeiten</a></span></div> </div> </nav> </div> </div> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> Diese Seite wurde zuletzt am 5. Dezember 2023 um 14:38 Uhr bearbeitet.</li> <li id="footer-info-copyright"><div id="footer-info-copyright-stats" class="noprint"><a rel="nofollow" class="external text" href="https://pageviews.wmcloud.org/?pages=RANSAC-Algorithmus&project=de.wikipedia.org">Abrufstatistik</a> · <a rel="nofollow" class="external text" href="https://xtools.wmcloud.org/authorship/de.wikipedia.org/RANSAC-Algorithmus?uselang=de">Autoren</a> </div><div id="footer-info-copyright-separator"><br /></div><div id="footer-info-copyright-info"> <p>Der Text ist unter der Lizenz <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">„Creative-Commons Namensnennung – Weitergabe unter gleichen Bedingungen“</a> verfügbar; Informationen zu den Urhebern und zum Lizenzstatus eingebundener Mediendateien (etwa Bilder oder Videos) können im Regelfall durch Anklicken dieser abgerufen werden. Möglicherweise unterliegen die Inhalte jeweils zusätzlichen Bedingungen. Durch die Nutzung dieser Website erklären Sie sich mit den <span class="plainlinks"><a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/de">Nutzungsbedingungen</a> und der <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Privacy_policy/de">Datenschutzrichtlinie</a></span> einverstanden.<br /> </p> Wikipedia® ist eine eingetragene Marke der Wikimedia Foundation Inc.</div></li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/de">Datenschutz</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:%C3%9Cber_Wikipedia">Über Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:Impressum">Impressum</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Verhaltenskodex</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Entwickler</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/de.wikipedia.org">Statistiken</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Stellungnahme zu Cookies</a></li> <li id="footer-places-mobileview"><a href="//de.m.wikipedia.org/w/index.php?title=RANSAC-Algorithmus&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile Ansicht</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> <script>(RLQ=window.RLQ||[]).push(function(){mw.log.warn("This page is using the deprecated ResourceLoader module \"codex-search-styles\".\n[1.43] Use a CodexModule with codexComponents to set your specific components used: https://www.mediawiki.org/wiki/Codex#Using_a_limited_subset_of_components");mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-4ws7h","wgBackendResponseTime":168,"wgPageParseReport":{"limitreport":{"cputime":"0.247","walltime":"0.433","ppvisitednodes":{"value":1448,"limit":1000000},"postexpandincludesize":{"value":26985,"limit":2097152},"templateargumentsize":{"value":5031,"limit":2097152},"expansiondepth":{"value":10,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":15835,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 299.968 1 -total"," 32.98% 98.942 11 Vorlage:Literatur"," 29.12% 87.338 3 Vorlage:Internetquelle"," 12.58% 37.734 1 Vorlage:Exzellent"," 9.69% 29.067 1 Vorlage:EnS"," 5.29% 15.864 1 Vorlage:Referrer"," 4.69% 14.078 1 Vorlage:IconExternal"," 3.21% 9.634 3 Vorlage:Str_len"," 2.41% 7.221 2 Vorlage:FormatDate"," 1.52% 4.548 1 Vorlage:Hinweisbaustein"]},"scribunto":{"limitreport-timeusage":{"value":"0.103","limit":"10.000"},"limitreport-memusage":{"value":3931675,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5dc468848-5hg4f","timestamp":"20241122073009","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"RANSAC-Algorithmus","url":"https:\/\/de.wikipedia.org\/wiki\/RANSAC-Algorithmus","sameAs":"http:\/\/www.wikidata.org\/entity\/Q218533","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q218533","author":{"@type":"Organization","name":"Autoren der Wikimedia-Projekte"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2006-12-29T23:47:25Z"}</script> </body> </html>