Image analysis algorithm

I'm not an expert on the implementation, but it might be worth checking out
ARTag. You can find more info here:
http://www.cv.iit.nrc.ca/research/ar/artag/

ARTag uses a pre-determined marker set with embedded bit-patterns. It uses a
number of techniques to correctly identify markers even when a significant
portion of the marker is occluded.

.nathan

> -----Original Message-----
> From: owner-artoolkit@h .................. [mailto:owner-
> artoolkit@h ..................] On Behalf Of Admin
> Sent: Wednesday, September 14, 2005 6:52 AM
> To: ARtoolkit forum
> Subject: Re: Image analysis algorithm
> 
> sune wrote:
> >
> >
> > Hi
> >
> >
> >
> > I have been working with ARToolkit for a few years by now and I think it
> > is a terrific tool. However I still don't understand the core of
> > ARToolkit - namely the image analysis. I hope that it will be possible
> > to modify the algorithm so that the user can cover a part of the outer
> > black square and still be able to recognize the marker. It should be
> > possible to do but I don't understand in detail what goes on in the
> > algorithm since there are no comments in the code and the C code seems
> > to have been written to be super efficient rather than easy to read (I
> > hope I do not offend anyone by assuming this).
> >
> > Does anyone have any detailed information about the image analysis
> > algorithm?
> >
> >
> >
> > Alternatively we might have to write a new algorithm from scratch. Do
> > you know any books or other sources that gives a good explanation on how
> > an image analysis algorithm like the one used in ARToolkit is
> implemented?
> >
> >
> >
> > Thank you
> >
> >
> >
> > Sune Kristensen
> >
> >
> >
> 
> Algorithm is very simple, it described here
> 
> http://www.hitl.washington.edu/artoolkit/Papers/IWAR99.kato.pdf
> 
> Basically black-white image is segmented, contour boundary of segments
> extracted and quadrilateral contour found and processed,
> in projective geometry, if P0, P1, P2, P3 - lines of contour
> X axis = P0 x P2
> Y axis = P1 x P3
> Z axis = X x Y
> That gives marker coordinate system. This algorithm is unstable. To make
> it stable you have to add some non-linear optimization, like in the
> other AR system , for example MXRtoolkit
> 
> http://mxrtoolkit.sourceforge.net/
> 
> Those algoritms can process only rectangular (or other polygon with no
> less then 2 pair of parallel sides) markers. If you want partial markers
> recognized with this algoritm, recognizable part of the marker should
> have 4 noncollinear recognizable points. They make quadrilateral
> polygon and can give rectangle through some fixed projective
> transformation.
> Or you can get rid of markers and work with feature points.
> google for 3D reconstruction, registration and robot vision, feature
> points. There are tons of articles on the net.
> Another way is use discrete fourier transform.

From:	"Nathan Heazlett" <nheazlett@b .................>	Received:	Sep 14, 2005
To	"'Admin'" <admin@c .............>, "'ARtoolkit forum'" <artoolkit@h ..................>
Subject:	RE: Image analysis algorithm
I'm not an expert on the implementation, but it might be worth checking out ARTag. You can find more info here: http://www.cv.iit.nrc.ca/research/ar/artag/ ARTag uses a pre-determined marker set with embedded bit-patterns. It uses a number of techniques to correctly identify markers even when a significant portion of the marker is occluded. .nathan > -----Original Message----- > From: owner-artoolkit@h .................. [mailto:owner- > artoolkit@h ..................] On Behalf Of Admin > Sent: Wednesday, September 14, 2005 6:52 AM > To: ARtoolkit forum > Subject: Re: Image analysis algorithm > > sune wrote: > > > > > > Hi > > > > > > > > I have been working with ARToolkit for a few years by now and I think it > > is a terrific tool. However I still don't understand the core of > > ARToolkit - namely the image analysis. I hope that it will be possible > > to modify the algorithm so that the user can cover a part of the outer > > black square and still be able to recognize the marker. It should be > > possible to do but I don't understand in detail what goes on in the > > algorithm since there are no comments in the code and the C code seems > > to have been written to be super efficient rather than easy to read (I > > hope I do not offend anyone by assuming this). > > > > Does anyone have any detailed information about the image analysis > > algorithm? > > > > > > > > Alternatively we might have to write a new algorithm from scratch. Do > > you know any books or other sources that gives a good explanation on how > > an image analysis algorithm like the one used in ARToolkit is > implemented? > > > > > > > > Thank you > > > > > > > > Sune Kristensen > > > > > > > > Algorithm is very simple, it described here > > http://www.hitl.washington.edu/artoolkit/Papers/IWAR99.kato.pdf > > Basically black-white image is segmented, contour boundary of segments > extracted and quadrilateral contour found and processed, > in projective geometry, if P0, P1, P2, P3 - lines of contour > X axis = P0 x P2 > Y axis = P1 x P3 > Z axis = X x Y > That gives marker coordinate system. This algorithm is unstable. To make > it stable you have to add some non-linear optimization, like in the > other AR system , for example MXRtoolkit > > http://mxrtoolkit.sourceforge.net/ > > Those algoritms can process only rectangular (or other polygon with no > less then 2 pair of parallel sides) markers. If you want partial markers > recognized with this algoritm, recognizable part of the marker should > have 4 noncollinear recognizable points. They make quadrilateral > polygon and can give rectangle through some fixed projective > transformation. > Or you can get rid of markers and work with feature points. > google for 3D reconstruction, registration and robot vision, feature > points. There are tons of articles on the net. > Another way is use discrete fourier transform.

From:	"sune" <sunek@d ..........>	Received:	Sep 14, 2005
To	<artoolkit@h ..................>
Subject:	Image analysis algorithm
This is a multi-part message in MIME format. ------=_NextPart_000_0000_01C5B91F.83FE4110 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Hi I have been working with ARToolkit for a few years by now and I think it is a terrific tool. However I still don't understand the core of ARToolkit - namely the image analysis. I hope that it will be possible to modify the algorithm so that the user can cover a part of the outer black square and still be able to recognize the marker. It should be possible to do but I don't understand in detail what goes on in the algorithm since there are no comments in the code and the C code seems to have been written to be super efficient rather than easy to read (I hope I do not offend anyone by assuming this). Does anyone have any detailed information about the image analysis algorithm? Alternatively we might have to write a new algorithm from scratch. Do you know any books or other sources that gives a good explanation on how an image analysis algorithm like the one used in ARToolkit is implemented? Thank you Sune Kristensen ------=_NextPart_000_0000_01C5B91F.83FE4110 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable <html xmlns:o=3D"urn:schemas-microsoft-com:office:office" = xmlns:w=3D"urn:schemas-microsoft-com:office:word" = xmlns=3D"http://www.w3.org/TR/REC-html40"> <head> <META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; = charset=3Dus-ascii"> <meta name=3DGenerator content=3D"Microsoft Word 11 (filtered medium)"> <style> <!-- /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {margin:0cm; margin-bottom:.0001pt; font-size:12.0pt; font-family:"Times New Roman";} a:link, span.MsoHyperlink {color:blue; text-decoration:underline;} a:visited, span.MsoHyperlinkFollowed {color:purple; text-decoration:underline;} span.EmailStyle17 {mso-style-type:personal-compose; font-family:Arial; color:windowtext;} @p ... Section1 {size:595.3pt 841.9pt; margin:3.0cm 2.0cm 3.0cm 2.0cm;} div.Section1 {page:Section1;} --> </style> </head> <body lang=3DDA link=3Dblue vlink=3Dpurple> <div class=3DSection1> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = lang=3DEN-GB style=3D'font-size:12.0pt'>Hi <o:p></o:p></span></font></p> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = lang=3DEN-GB style=3D'font-size:12.0pt'><o:p> </o:p></span></font></p> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = lang=3DEN-GB style=3D'font-size:12.0pt'>I have been working with ARToolkit for a few = years by now and I think it is a terrific tool. However I still don’t = understand the core of ARToolkit – namely the image analysis. I hope that it = will be possible to modify the algorithm so that the user can cover a part of = the outer black square and still be able to recognize the marker. It should be = possible to do but I don’t understand in detail what goes on in the = algorithm since there are no comments in the code and the C code seems to have = been written to be super efficient rather than easy to read (I hope I do not = offend anyone by assuming this). <o:p></o:p></span></font></p> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = lang=3DEN-GB style=3D'font-size:12.0pt'>Does anyone have any detailed information = about the image analysis algorithm? <o:p></o:p></span></font></p> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = lang=3DEN-GB style=3D'font-size:12.0pt'><o:p> </o:p></span></font></p> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = lang=3DEN-GB style=3D'font-size:12.0pt'>Alternatively we might have to write a new = algorithm from scratch. Do you know any books or other sources that gives a good explanation on how an image analysis algorithm like the one used in = ARToolkit is implemented? <o:p></o:p></span></font></p> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = lang=3DEN-GB style=3D'font-size:12.0pt'><o:p> </o:p></span></font></p> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = style=3D'font-size: 12.0pt'>Thank you<o:p></o:p></span></font></p> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = style=3D'font-size: 12.0pt'><o:p> </o:p></span></font></p> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = style=3D'font-size: 12.0pt'>Sune Kristensen<o:p></o:p></span></font></p> <p class=3DMsoNormal><font size=3D3 face=3D"Times New Roman"><span = lang=3DEN-GB style=3D'font-size:12.0pt'><o:p> </o:p></span></font></p> </div> </body> </html> ------=_NextPart_000_0000_01C5B91F.83FE4110--

From:	Admin <admin@c .............>	Received:	Sep 14, 2005
To	ARtoolkit forum <artoolkit@h ..................>
Subject:	Re: Image analysis algorithm
sune wrote: > > > Hi > > > > I have been working with ARToolkit for a few years by now and I think it > is a terrific tool. However I still don’t understand the core of > ARToolkit – namely the image analysis. I hope that it will be possible > to modify the algorithm so that the user can cover a part of the outer > black square and still be able to recognize the marker. It should be > possible to do but I don’t understand in detail what goes on in the > algorithm since there are no comments in the code and the C code seems > to have been written to be super efficient rather than easy to read (I > hope I do not offend anyone by assuming this). > > Does anyone have any detailed information about the image analysis > algorithm? > > > > Alternatively we might have to write a new algorithm from scratch. Do > you know any books or other sources that gives a good explanation on how > an image analysis algorithm like the one used in ARToolkit is implemented? > > > > Thank you > > > > Sune Kristensen > > > Algorithm is very simple, it described here http://www.hitl.washington.edu/artoolkit/Papers/IWAR99.kato.pdf Basically black-white image is segmented, contour boundary of segments extracted and quadrilateral contour found and processed, in projective geometry, if P0, P1, P2, P3 - lines of contour X axis = P0 x P2 Y axis = P1 x P3 Z axis = X x Y That gives marker coordinate system. This algorithm is unstable. To make it stable you have to add some non-linear optimization, like in the other AR system , for example MXRtoolkit http://mxrtoolkit.sourceforge.net/ Those algoritms can process only rectangular (or other polygon with no less then 2 pair of parallel sides) markers. If you want partial markers recognized with this algoritm, recognizable part of the marker should have 4 noncollinear recognizable points. They make quadrilateral polygon and can give rectangle through some fixed projective transformation. Or you can get rid of markers and work with feature points. google for 3D reconstruction, registration and robot vision, feature points. There are tons of articles on the net. Another way is use discrete fourier transform.

From:	CLG <admin@c .............>	Received:	Nov 8, 2005
To	ARtoolkit forum <artoolkit@h ..................>
Subject:	Re: Image analysis algorithm
Ji-Young Oh wrote: > Hi. > > I am new to ARToolkit, and I just finished reading the IWAR99 paper. > > I just had some problem with understanding some details in the paper. > I looked through the mailing list archive and found this snippet that is > related to my question. > > ----------------><------------------------------------------------------------ > Basically black-white image is segmented, contour boundary of segments > extracted and quadrilateral contour found and processed, > in projective geometry, if P0, P1, P2, P3 - lines of contour > X axis = P0 x P2 > Y axis = P1 x P3 > Z axis = X x Y > That gives marker coordinate system. > ----------------><------------------------------------------------------------ > > So.. my question is, why X axis is cross product of P0xP2 ??? > (Question from page 5, first paragraph under (eq 5). ) > P0 is a line with equation : P0xX + P0yY + P0z = 0 It correspond to the plane with normal vector (P0x, P0y, P0z) P0xX + P0yY + P0z*Z = 0 (plane0) P0 is a line of intersection of this palne with plane Z = 1 (corresponding to projective plane) the same for P2 Quadrilateral in question is a projective image of the parallelogram lines P0 and P2 are projective images of the parallel side of the paralelogramm. That mean the side P0par of the paralelogramm lie in the plane of plane0 and side P2par in the plane palne2 The X axis parallel both to P0par and P2par That mean it is parallel both to plane0 and plane2 Becae all of three : X, plane0 and plane2 are originate in the (0, 0, 0) that mean X is the vector corresponding to the line of intersection of plane0 and plane2 Such vector is X = plane0 x plane2 = P0 x P2 For better understanding I'd recommend some reading on projective geometry, for example http://vision.stanford.edu/~birch/projective/

From:	Ji-Young Oh <jyohjyoh@g ........>	Received:	Nov 8, 2005
To	artoolkit@h ..................
Subject:	Image analysis algorithm
Hi. I am new to ARToolkit, and I just finished reading the IWAR99 paper. I just had some problem with understanding some details in the paper. I looked through the mailing list archive and found this snippet that is related to my question. ----------------><---------------------------------------------------------= --- Basically black-white image is segmented, contour boundary of segments extracted and quadrilateral contour found and processed, in projective geometry, if P0, P1, P2, P3 - lines of contour X axis =3D P0 x P2 Y axis =3D P1 x P3 Z axis =3D X x Y That gives marker coordinate system. ----------------><---------------------------------------------------------= --- So.. my question is, why X axis is cross product of P0xP2 ??? (Question from page 5, first paragraph under (eq 5). ) If not easy to explain, could you give a reference that I can read? Thank you, Ji-Young Oh.