OpenCV Q&A Forum - RSS feedhttp://answers.opencv.org/questions/OpenCV answersenCopyright <a href="http://www.opencv.org">OpenCV foundation</a>, 2012-2018.Wed, 26 Jun 2013 07:42:18 -0500Does findHomography use DLT with SVD when there are more than 4 points?http://answers.opencv.org/question/2802/does-findhomography-use-dlt-with-svd-when-there-are-more-than-4-points/Information taken from here:
[Link](http://mmlab.disi.unitn.it/wiki/index.php/2D_Homography:_Algorithm_and_Tool)
Basically it says when there are more than 4 points the set of equations Ah = 0 is over-determined and we need to
- minimizing residuals with Least Square
or
- adopt the so called singular value decomosition
OpenCV with findHomography which strategy adopts when there are more than 4 points?
Ps. I know RANSAC is used to choose inliner/outlier, but what happens when inliner are more than 4 points? the system is over-determinated with more than 4 pointsTue, 02 Oct 2012 06:10:43 -0500http://answers.opencv.org/question/2802/does-findhomography-use-dlt-with-svd-when-there-are-more-than-4-points/Answer by Ben for <p>Information taken from here:</p>
<p><a href="http://mmlab.disi.unitn.it/wiki/index.php/2D_Homography:_Algorithm_and_Tool">Link</a></p>
<p>Basically it says when there are more than 4 points the set of equations Ah = 0 is over-determined and we need to</p>
<ul>
<li>minimizing residuals with Least Square</li>
</ul>
<p>or </p>
<ul>
<li>adopt the so called singular value decomosition</li>
</ul>
<p>OpenCV with findHomography which strategy adopts when there are more than 4 points? </p>
<p>Ps. I know RANSAC is used to choose inliner/outlier, but what happens when inliner are more than 4 points? the system is over-determinated with more than 4 points</p>
http://answers.opencv.org/question/2802/does-findhomography-use-dlt-with-svd-when-there-are-more-than-4-points/?answer=2807#post-id-2807`findHomography()` uses RANSAC to compute a transformation matrix.
It iteratively picks 4 random point pairs to compute a homography, then tests, how good it is (classifying other point pairs as inliers/outliers) and chooses the homography with the most inliers. This way it is very robust to outliers (false matches) whereas using all matches for computation would falsify the transformation.
**UPDATE**
Ok, here a sort of pseudo code to explain the RANSAC algorithm.
Let's say you have a list of point pairs `matchlist`, which represent matches between a source and a destination image. Now RANSAC does something like:
Homography bestH = null
while (termination criteria not fulfilled)
{
randomly choose 4 matches from matchlist
compute homography H from those 4 matches (-> not overdeterminated)
numInliers = 0
foreach (match m in matchlist)
{
if (m is inlier) numInliers += 1
}
if (numInliers > minNumInliers)
{
if (H better than bestH) bestH = H // H has more inliers than bestH
}
}
This is a very simple version, the OpenCV RANSAC algorithm probably is more complex. Termination criteria typically are
* maximum number of iterations -> give up, if you don't find a good homography after x iterations
* minimum quality of the best homography -> don't unnecessarily perform further iterations, if you already found a good enough homography
I hope, this little example helps for better understanding.Tue, 02 Oct 2012 09:25:40 -0500http://answers.opencv.org/question/2802/does-findhomography-use-dlt-with-svd-when-there-are-more-than-4-points/?answer=2807#post-id-2807Comment by stetro for <p><code>findHomography()</code> uses RANSAC to compute a transformation matrix.
It iteratively picks 4 random point pairs to compute a homography, then tests, how good it is (classifying other point pairs as inliers/outliers) and chooses the homography with the most inliers. This way it is very robust to outliers (false matches) whereas using all matches for computation would falsify the transformation.</p>
<p><strong>UPDATE</strong></p>
<p>Ok, here a sort of pseudo code to explain the RANSAC algorithm.</p>
<p>Let's say you have a list of point pairs <code>matchlist</code>, which represent matches between a source and a destination image. Now RANSAC does something like:</p>
<pre><code>Homography bestH = null
while (termination criteria not fulfilled)
{
randomly choose 4 matches from matchlist
compute homography H from those 4 matches (-> not overdeterminated)
numInliers = 0
foreach (match m in matchlist)
{
if (m is inlier) numInliers += 1
}
if (numInliers > minNumInliers)
{
if (H better than bestH) bestH = H // H has more inliers than bestH
}
}
</code></pre>
<p>This is a very simple version, the OpenCV RANSAC algorithm probably is more complex. Termination criteria typically are</p>
<ul>
<li><p>maximum number of iterations -> give up, if you don't find a good homography after x iterations</p></li>
<li><p>minimum quality of the best homography -> don't unnecessarily perform further iterations, if you already found a good enough homography</p></li>
</ul>
<p>I hope, this little example helps for better understanding.</p>
http://answers.opencv.org/question/2802/does-findhomography-use-dlt-with-svd-when-there-are-more-than-4-points/?comment=15791#post-id-15791How about Least-Median of Squares? Isn't it a way to solve a over-determined linear system?Wed, 26 Jun 2013 07:42:18 -0500http://answers.opencv.org/question/2802/does-findhomography-use-dlt-with-svd-when-there-are-more-than-4-points/?comment=15791#post-id-15791Comment by yes123 for <p><code>findHomography()</code> uses RANSAC to compute a transformation matrix.
It iteratively picks 4 random point pairs to compute a homography, then tests, how good it is (classifying other point pairs as inliers/outliers) and chooses the homography with the most inliers. This way it is very robust to outliers (false matches) whereas using all matches for computation would falsify the transformation.</p>
<p><strong>UPDATE</strong></p>
<p>Ok, here a sort of pseudo code to explain the RANSAC algorithm.</p>
<p>Let's say you have a list of point pairs <code>matchlist</code>, which represent matches between a source and a destination image. Now RANSAC does something like:</p>
<pre><code>Homography bestH = null
while (termination criteria not fulfilled)
{
randomly choose 4 matches from matchlist
compute homography H from those 4 matches (-> not overdeterminated)
numInliers = 0
foreach (match m in matchlist)
{
if (m is inlier) numInliers += 1
}
if (numInliers > minNumInliers)
{
if (H better than bestH) bestH = H // H has more inliers than bestH
}
}
</code></pre>
<p>This is a very simple version, the OpenCV RANSAC algorithm probably is more complex. Termination criteria typically are</p>
<ul>
<li><p>maximum number of iterations -> give up, if you don't find a good homography after x iterations</p></li>
<li><p>minimum quality of the best homography -> don't unnecessarily perform further iterations, if you already found a good enough homography</p></li>
</ul>
<p>I hope, this little example helps for better understanding.</p>
http://answers.opencv.org/question/2802/does-findhomography-use-dlt-with-svd-when-there-are-more-than-4-points/?comment=2812#post-id-2812So basically RANSAC always returns only 4 points to calc the homography? If it returns more points the system is over-determinated
Tue, 02 Oct 2012 12:44:07 -0500http://answers.opencv.org/question/2802/does-findhomography-use-dlt-with-svd-when-there-are-more-than-4-points/?comment=2812#post-id-2812