ARToolKit | Mailing List Archive |

[ARToolKit] What is the pose estimation algorithm that used in ARToolKit?

From: | "Hyon Lim" <alex@a ..........> | Received: | Nov 12, 2007 |

To | ARToolKit@l ................. | ||

Subject: | [ARToolKit] What is the pose estimation algorithm that used in ARToolKit? | ||

In many papers, I saw DLT(Direct Linear Transform) method to estimate rotation and translation (R,t) matrix. The main concept of DLT is that given four vertices can be used to solve relation between image coordinates and world coordinates (linear method). If world coordinates are represented by four elements (x,y,z,1) and image coordinates (x,y,1). [x,y,1]^t = K*[R t]*[x,y,z,1]^t where ^t means transpose. (K = camera matrix which contains focal length and the other distortion parameters) DLT can be used to compute [R t]. If four vertices are coplanar(positioned in same plane), they are more simple. [Refer : http://www.kwon3d.com/theory/dlt/dlt.html] Does ARToolKit used this algorithm to compute pose estimation? But, this algorithm needs Singular Value Decomposition to get a minimum error solution. However, I cannot find SVD function in ARtoolkit. -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.hitlabnz.org/pipermail/artoolkit/attachments/20071112/b9165c82/attachment.html _______________________________________________ ARToolKit mailing list ARToolKit@l ................. http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit |

From: | Daniel Wagner <daniel@i ...............> | Received: | Nov 12, 2007 |

To | artoolkit@l ................., Hyon Lim <alex@a ..........> | ||

Subject: | Re: [ARToolKit] What is the pose estimation algorithm that used in ARToolKit? | ||

Hi Hyon, not finding code doesn't mean it isn't there. The ARTK source code is badly documented and the function names are far from self-explanatory. Yet, I don't think that ARTK includes an SVD function. Generally, DLT will give you a homography of between two frames of reference. In the case of marker tracking it would be mapping from the camera frame to the marker in the image. Naturally this is very similar to a pose. It is therefore not difficult to get a pose from a homography. SVD is not the only method to calculate a homography, but it is probably the best.// Still, a pose from homography function will give only a very coarse pose (usually called an initial guess). That's why one typically does a refinement step. Other than pose via DLT, this is usually not done directly, but iterative instead. The standard method for this is non-linear refinement using Gauss-Newton or Levenberg-Marquardt iteration. ARTK does not use these methods, but does a refinement by "variation": Starting with the initial guess it varies the pose into all directions (rotation only, position is adjusted respectively) and chooses the best variation. This step is iterated several times. While it is a very simple method it is not suggested because it requires a lot of iterations. Instead I'd go for GN or. LM refinement, which converges a lot faster due to putting more knowledge into the system (Jacobian matrix). I don't think that the way ARTK fines the pose has a standard name... Daniel Hyon Lim wrote: > In many papers, I saw DLT(Direct Linear Transform) method to estimate > rotation and translation (R,t) matrix. > The main concept of DLT is that given four vertices can be used to solve > relation between image coordinates and world coordinates (linear method). > If world coordinates are represented by four elements (x,y,z,1) and image > coordinates (x,y,1). > > [x,y,1]^t = K*[R t]*[x,y,z,1]^t > > where ^t means transpose. (K = camera matrix which contains focal length and > the other distortion parameters) > > DLT can be used to compute [R t]. > > If four vertices are coplanar(positioned in same plane), they are more > simple. > > [Refer : http://www.kwon3d.com/theory/dlt/dlt.html] > > Does ARToolKit used this algorithm to compute pose estimation? > But, this algorithm needs Singular Value Decomposition to get a minimum > error solution. > However, I cannot find SVD function in ARtoolkit. > -------------- next part -------------- > An HTML attachment was scrubbed... > URL: http://www.hitlabnz.org/pipermail/artoolkit/attachments/20071112/b9165c82/attachment.html > _______________________________________________ > ARToolKit mailing list > ARToolKit@l ................. > http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit > _______________________________________________ ARToolKit mailing list ARToolKit@l ................. http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit |

From: | "Hyon Lim" <alex@a ..........> | Received: | Nov 13, 2007 |

To | "Daniel Wagner" <daniel@i ...............> | ||

Subject: | Re: [ARToolKit] What is the pose estimation algorithm that used in ARToolKit? | ||

Could you explain to me with equation? Or, the algorithm statement is okay. (If you possible) I think this article will be helpful to new users. You said that they use "variation" for refinement. What is the definition of "variation"? (Numerically) On 11/12/07, Daniel Wagner <daniel@i ...............> wrote: > > Hi Hyon, > > not finding code doesn't mean it isn't there. > The ARTK source code is badly documented and the function names are far > from self-explanatory. > Yet, I don't think that ARTK includes an SVD function. > > Generally, DLT will give you a homography of between two frames of > reference. > In the case of marker tracking it would be mapping from the camera frame > to the marker in the image. > Naturally this is very similar to a pose. It is therefore not difficult > to get a pose from a homography. > SVD is not the only method to calculate a homography, but it is probably > the best.// > > Still, a pose from homography function will give only a very coarse pose > (usually called an initial guess). > That's why one typically does a refinement step. Other than pose via > DLT, this is usually not done directly, but iterative instead. > The standard method for this is non-linear refinement using Gauss-Newton > or Levenberg-Marquardt iteration. > ARTK does not use these methods, but does a refinement by "variation": > Starting with the initial guess it varies the pose into all directions > (rotation only, position is adjusted respectively) and chooses the best > variation. This step is iterated several times. While it is a very > simple method it is not suggested because it requires a lot of > iterations. Instead I'd go for GN or. LM refinement, which converges a > lot faster due to putting more knowledge into the system (Jacobian > matrix). > > I don't think that the way ARTK fines the pose has a standard name... > > Daniel > > > > Hyon Lim wrote: > > In many papers, I saw DLT(Direct Linear Transform) method to estimate > > rotation and translation (R,t) matrix. > > The main concept of DLT is that given four vertices can be used to solve > > relation between image coordinates and world coordinates (linear > method). > > If world coordinates are represented by four elements (x,y,z,1) and > image > > coordinates (x,y,1). > > > > [x,y,1]^t = K*[R t]*[x,y,z,1]^t > > > > where ^t means transpose. (K = camera matrix which contains focal length > and > > the other distortion parameters) > > > > DLT can be used to compute [R t]. > > > > If four vertices are coplanar(positioned in same plane), they are more > > simple. > > > > [Refer : http://www.kwon3d.com/theory/dlt/dlt.html] > > > > Does ARToolKit used this algorithm to compute pose estimation? > > But, this algorithm needs Singular Value Decomposition to get a minimum > > error solution. > > However, I cannot find SVD function in ARtoolkit. > > -------------- next part -------------- > > An HTML attachment was scrubbed... > > URL: > http://www.hitlabnz.org/pipermail/artoolkit/attachments/20071112/b9165c82/attachment.html > > _______________________________________________ > > ARToolKit mailing list > > ARToolKit@l ................. > > http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit > > > > -- Hyon Lim Mobile. +82-10-8212-1240 Website. http://www.alexlab.net -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.hitlabnz.org/pipermail/artoolkit/attachments/20071113/a3e2458a/attachment.html _______________________________________________ ARToolKit mailing list ARToolKit@l ................. http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit |

From: | Philip Lamb <phil@e ..........> | Received: | Nov 13, 2007 |

To | artoolkit@l ................. | ||

Subject: | Re: [ARToolKit] What is the pose estimation algorithm that used in ARToolKit? | ||

On 13/11/2007, at 12:17 AM, Daniel Wagner wrote: > The standard method for this is non-linear refinement using Gauss- > Newton > or Levenberg-Marquardt iteration. > ARTK does not use these methods, but does a refinement by "variation": > .. > I don't think that the way ARTK fines the pose has a standard name... > It is non-standard, but as Hiro told me emphatically a while ago "it worked!", and it had the benefit of being computationally quite light- weight. This is not so critical these days but back in 1997 it was much more so. ARToolKit v4.3 now uses the standard ICP algorithm for pose estimation. We have done some tests, and it has marginally more accuracy than Hiro's original algorithm, but is 2 orders of magnitude faster. It also has a robust estimator which is not of much benefit in single-marker tracking, but is really beneficial in multi-marker and natural feature texture tracking. Before everyone bombards me with emails... yes, ARToolworks is working out terms for a low-cost license for academic institutions for ARToolKit v4.3. We intend to pull up some of the code in ARToolKit v.2.x to the newer version as well. Cheers, Phil. -------------- next part -------------- A non-text attachment was scrubbed... Name: smime.p7s Type: application/pkcs7-signature Size: 2415 bytes Desc: not available Url : http://www.hitlabnz.org/pipermail/artoolkit/attachments/20071113/8dc0eec1/attachment.bin _______________________________________________ ARToolKit mailing list ARToolKit@l ................. http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit |

From: | Daniel Wagner <daniel@i ...............> | Received: | Nov 13, 2007 |

To | artoolkit@l ................. | ||

Subject: | Re: [ARToolKit] What is the pose estimation algorithm that used in ARToolKit? | ||

So here is what ARTK does: - Start with the initial coarse pose estimation - Define a variation angle (e.g. as 90=B0) - Create variations by rotating the pose around all 3 axis with the +/- variation angle - Take the best variation - Decrease the variation angle by 50% - Again check all rotations - ... This is done several times until the angle is really small. As you can see it is very brute force approach. If you do 12 iterations (as ARTK does) and 27 variations per iteration then this results in more than 300 checks. More advanced approaches use the Jacobian matrix and solve an equation (search the web for Gauss Newton iteration) to directly optimize into the right direction. This way one usually requires only a few (~3) iterations. Naturally solving the equation (e.g. using Cholesky decomposition) requires more computation than the simple variations ARTK does, but still 3 vs 300 easily balances in favor of GN or LM iteration. If you are interested in modern methods of pose estimation I suggest reading the book "Multiple View Geometry". Daniel Hyon Lim wrote: > > Could you explain to me with equation? Or, the algorithm statement is > okay. (If you possible) > I think this article will be helpful to new users. > > You said that they use "variation" for refinement. What is the > definition of "variation"? (Numerically) > _______________________________________________ ARToolKit mailing list ARToolKit@l ................. http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit |

From: | "Hyon Lim" <alex@a ..........> | Received: | Nov 13, 2007 |

To | "Philip Lamb" <phil@e ..........> | ||

Subject: | Re: [ARToolKit] What is the pose estimation algorithm that used in ARToolKit? | ||

I little bit confused about ARTK version. What is the v4.3?? I didn't hear about that. At the source forge, only v2.x present. right? On 11/13/07, Philip Lamb <phil@e ..........> wrote: > > > On 13/11/2007, at 12:17 AM, Daniel Wagner wrote: > > The standard method for this is non-linear refinement using Gauss- > > Newton > > or Levenberg-Marquardt iteration. > > ARTK does not use these methods, but does a refinement by "variation": > > .. > > I don't think that the way ARTK fines the pose has a standard name... > > > > It is non-standard, but as Hiro told me emphatically a while ago "it > worked!", and it had the benefit of being computationally quite light- > weight. This is not so critical these days but back in 1997 it was > much more so. > > ARToolKit v4.3 now uses the standard ICP algorithm for pose > estimation. We have done some tests, and it has marginally more > accuracy than Hiro's original algorithm, but is 2 orders of magnitude > faster. It also has a robust estimator which is not of much benefit > in single-marker tracking, but is really beneficial in multi-marker > and natural feature texture tracking. > > Before everyone bombards me with emails... yes, ARToolworks is > working out terms for a low-cost license for academic institutions > for ARToolKit v4.3. We intend to pull up some of the code in > ARToolKit v.2.x to the newer version as well. > > Cheers, > Phil. > > -------------- next part -------------- > A non-text attachment was scrubbed... > Name: smime.p7s > Type: application/pkcs7-signature > Size: 2415 bytes > Desc: not available > Url : > http://www.hitlabnz.org/pipermail/artoolkit/attachments/20071113/8dc0eec1/attachment.bin > _______________________________________________ > ARToolKit mailing list > ARToolKit@l ................. > http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit > -- Hyon Lim Mobile. +82-10-8212-1240 Website. http://www.alexlab.net -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.hitlabnz.org/pipermail/artoolkit/attachments/20071113/b2e26103/attachment.html _______________________________________________ ARToolKit mailing list ARToolKit@l ................. http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit |

From: | "Hyon Lim" <alex@a ..........> | Received: | Nov 13, 2007 |

To | "Daniel Wagner" <daniel@i ...............> | ||

Subject: | Re: [ARToolKit] What is the pose estimation algorithm that used in ARToolKit? | ||

To sum up our discussion, ARTK follows the sequence below. Assumption 1. We know priorly the camera calibratin matrix K. (Intrinsic parameter) 1. Extract the corner of the marker in the given image. The extracted four corner is [U_1, V_1] [U_2, V_2] [U_3, V_3] [U_4, V_4] its vector notation is [u,v] 2. Guess the initial coarse pose estimation. 3. Create variations by rotating the pose around all 3axis with the +/-. 4. Reproject it to verify our hyphothesis(transformation matrix). 5. If our hyphothesis is proper to observed scene, choose it! Question. How they set 3D point of the marker coordinate from observed 2D image(u,v)? On 11/13/07, Daniel Wagner <daniel@i ...............> wrote: > > So here is what ARTK does: > > - Start with the initial coarse pose estimation > - Define a variation angle (e.g. as 90=B0) > - Create variations by rotating the pose around all 3 axis with the +/- > variation angle > - Take the best variation > - Decrease the variation angle by 50% > - Again check all rotations > - ... > > > This is done several times until the angle is really small. > As you can see it is very brute force approach. If you do 12 iterations > (as ARTK does) and 27 variations per iteration then this results in more > than 300 checks. > > More advanced approaches use the Jacobian matrix and solve an equation > (search the web for Gauss Newton iteration) to directly optimize into > the right direction. This way one usually requires only a few (~3) > iterations. Naturally solving the equation (e.g. using Cholesky > decomposition) requires more computation than the simple variations ARTK > does, but still 3 vs 300 easily balances in favor of GN or LM iteration. > > If you are interested in modern methods of pose estimation I suggest > reading the book "Multiple View Geometry". > > Daniel > > > > Hyon Lim wrote: > > > > Could you explain to me with equation? Or, the algorithm statement is > > okay. (If you possible) > > I think this article will be helpful to new users. > > > > You said that they use "variation" for refinement. What is the > > definition of "variation"? (Numerically) > > > > _______________________________________________ > ARToolKit mailing list > ARToolKit@l ................. > http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit > -- = Hyon Lim Mobile. +82-10-8212-1240 Website. http://www.alexlab.net -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.hitlabnz.org/pipermail/artoolkit/attachments/20071113/80f92= 306/attachment.html = _______________________________________________ ARToolKit mailing list ARToolKit@l ................. http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit |

From: | Daniel Wagner <daniel@i ...............> | Received: | Nov 13, 2007 |

To | artoolkit@l ................. | ||

Subject: | Re: [ARToolKit] What is the pose estimation algorithm that used in ARToolKit? | ||

Hi Hyon Lim, Your summary is correct. I actually forgot to list the reprojection part. Thanks for adding it. The 3D coordinates of the corners are assumed to be (-w/2;h/2;0), (w/2;h/2;0), (w/2;-h/2;0), (-w/2;-h/2;0) So this is simply a marker with width and height defined as w and h that sits in the Z=3D0 plane. The pose then defines the projection of these 3D coordinates to the position of the marker in the image. Daniel Hyon Lim wrote: > To sum up our discussion, ARTK follows the sequence below. > > Assumption 1. We know priorly the camera calibratin matrix K. > (Intrinsic parameter) > > 1. Extract the corner of the marker in the given image. The extracted > four corner is > > [U_1, V_1] > [U_2, V_2] > [U_3, V_3] > [U_4, V_4] > > its vector notation is [u,v] > > 2. Guess the initial coarse pose estimation. > > 3. Create variations by rotating the pose around all 3axis with the +/-. > > 4. Reproject it to verify our hyphothesis(transformation matrix). > > 5. If our hyphothesis is proper to observed scene, choose it! > > Question. How they set 3D point of the marker coordinate from observed > 2D image(u,v)? > > > On 11/13/07, *Daniel Wagner* <daniel@i ............... > <mailto:daniel@i ...............>> wrote: > > So here is what ARTK does: > > - Start with the initial coarse pose estimation > - Define a variation angle (e.g. as 90=B0) > - Create variations by rotating the pose around all 3 axis with > the +/- > variation angle > - Take the best variation > - Decrease the variation angle by 50% > - Again check all rotations > - ... > > > This is done several times until the angle is really small. > As you can see it is very brute force approach. If you do 12 > iterations > (as ARTK does) and 27 variations per iteration then this results > in more > than 300 checks. > > More advanced approaches use the Jacobian matrix and solve an equation > (search the web for Gauss Newton iteration) to directly optimize into > the right direction. This way one usually requires only a few (~3) > iterations. Naturally solving the equation (e.g. using Cholesky > decomposition) requires more computation than the simple > variations ARTK > does, but still 3 vs 300 easily balances in favor of GN or LM > iteration. > > If you are interested in modern methods of pose estimation I suggest > reading the book "Multiple View Geometry". > > Daniel > > > > Hyon Lim wrote: > > > > Could you explain to me with equation? Or, the algorithm > statement is > > okay. (If you possible) > > I think this article will be helpful to new users. > > > > You said that they use "variation" for refinement. What is the > > definition of "variation"? (Numerically) > > > > _______________________________________________ > ARToolKit mailing list > ARToolKit@l ................. <mailto:ARToolKit@l .................> > http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit > > > > > -- = > Hyon Lim > Mobile. +82-10-8212-1240 > Website. http://www.alexlab.net = _______________________________________________ ARToolKit mailing list ARToolKit@l ................. http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit |

From: | "Hyon Lim" <alex@a ..........> | Received: | Nov 13, 2007 |

To | "Daniel Wagner" <daniel@i ...............> | ||

Subject: | Re: [ARToolKit] What is the pose estimation algorithm that used in ARToolKit? | ||

Quite understandable. Thank you very much. However, do you have an experience that implement other type of pose estimation? Using cost function (J) or other non-linear method.. something like that. I think that ARTK's algorithm is too difficult to understand (by its code). On 11/13/07, Daniel Wagner <daniel@i ...............> wrote: > > Hi Hyon Lim, > > Your summary is correct. > I actually forgot to list the reprojection part. Thanks for adding it. > > The 3D coordinates of the corners are assumed to be > (-w/2;h/2;0), (w/2;h/2;0), (w/2;-h/2;0), (-w/2;-h/2;0) > > So this is simply a marker with width and height defined as w and h that > sits in the Z=3D0 plane. > The pose then defines the projection of these 3D coordinates to the > position of the marker in the image. > > Daniel > > > > Hyon Lim wrote: > > To sum up our discussion, ARTK follows the sequence below. > > > > Assumption 1. We know priorly the camera calibratin matrix K. > > (Intrinsic parameter) > > > > 1. Extract the corner of the marker in the given image. The extracted > > four corner is > > > > [U_1, V_1] > > [U_2, V_2] > > [U_3, V_3] > > [U_4, V_4] > > > > its vector notation is [u,v] > > > > 2. Guess the initial coarse pose estimation. > > > > 3. Create variations by rotating the pose around all 3axis with the +/-. > > > > 4. Reproject it to verify our hyphothesis(transformation matrix). > > > > 5. If our hyphothesis is proper to observed scene, choose it! > > > > Question. How they set 3D point of the marker coordinate from observed > > 2D image(u,v)? > > > > > > On 11/13/07, *Daniel Wagner* <daniel@i ............... > > <mailto:daniel@i ...............>> wrote: > > > > So here is what ARTK does: > > > > - Start with the initial coarse pose estimation > > - Define a variation angle (e.g. as 90=B0) > > - Create variations by rotating the pose around all 3 axis with > > the +/- > > variation angle > > - Take the best variation > > - Decrease the variation angle by 50% > > - Again check all rotations > > - ... > > > > > > This is done several times until the angle is really small. > > As you can see it is very brute force approach. If you do 12 > > iterations > > (as ARTK does) and 27 variations per iteration then this results > > in more > > than 300 checks. > > > > More advanced approaches use the Jacobian matrix and solve an > equation > > (search the web for Gauss Newton iteration) to directly optimize > into > > the right direction. This way one usually requires only a few (~3) > > iterations. Naturally solving the equation (e.g. using Cholesky > > decomposition) requires more computation than the simple > > variations ARTK > > does, but still 3 vs 300 easily balances in favor of GN or LM > > iteration. > > > > If you are interested in modern methods of pose estimation I suggest > > reading the book "Multiple View Geometry". > > > > Daniel > > > > > > > > Hyon Lim wrote: > > > > > > Could you explain to me with equation? Or, the algorithm > > statement is > > > okay. (If you possible) > > > I think this article will be helpful to new users. > > > > > > You said that they use "variation" for refinement. What is the > > > definition of "variation"? (Numerically) > > > > > > > _______________________________________________ > > ARToolKit mailing list > > ARToolKit@l ................. <mailto:ARToolKit@l .................> > > http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit > > > > > > > > > > -- > > Hyon Lim > > Mobile. +82-10-8212-1240 > > Website. http://www.alexlab.net > > -- = Hyon Lim Mobile. +82-10-8212-1240 Website. http://www.alexlab.net -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.hitlabnz.org/pipermail/artoolkit/attachments/20071113/31837= 35f/attachment.html = _______________________________________________ ARToolKit mailing list ARToolKit@l ................. http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit |

From: | Daniel Wagner <daniel@i ...............> | Received: | Nov 13, 2007 |

To | artoolkit@l ................., Hyon Lim <alex@a ..........> | ||

Subject: | Re: [ARToolKit] What is the pose estimation algorithm that used in ARToolKit? | ||

Actually I found the ARTK pose estimation source code rather easy to understand due to its simple approach. We implemented a non-linear pose estimator (using Gauss-Newton iteration) in StbTracker, our successor to ARTK+, but it is not open source. You can look at the RPP pose estimator in ARTK+ which is probably currently one the best pose estimator from planar point clouds (look at the paper by Schweighofer and Pinz) Daniel Hyon Lim wrote: > Quite understandable. Thank you very much. > However, do you have an experience that implement other type of pose > estimation? > Using cost function (J) or other non-linear method.. something like that. > I think that ARTK's algorithm is too difficult to understand (by its > code). _______________________________________________ ARToolKit mailing list ARToolKit@l ................. http://www.hitlabnz.org/mailman/listinfo.cgi/artoolkit |