Fast error-correcting of embedded interaction codes
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06K-009/00
G06T-007/00
출원번호
UP-0142844
(2005-05-31)
등록번호
US-7729539
(2010-06-22)
발명자
/ 주소
Lin, Zhouchen
Wang, Qiang
Wang, Jian
출원인 / 주소
Microsoft Corporation
대리인 / 주소
Perkins Coie LLP
인용정보
피인용 횟수 :
0인용 특허 :
248
초록▼
A fast decoding technique for decoding a position of a bit in a pattern provided on a media surface that can generate large amounts of solution candidates quickly by switching or flipping bits and utilizing a recursion scheme. The fast decoding technique may be employed to simultaneously decode mult
A fast decoding technique for decoding a position of a bit in a pattern provided on a media surface that can generate large amounts of solution candidates quickly by switching or flipping bits and utilizing a recursion scheme. The fast decoding technique may be employed to simultaneously decode multiple dimensions of a pattern on the media surface.
대표청구항▼
What is claimed is: 1. A method, preformed by a computer having a memory and a processor, of determining a position of a bit s in a pattern formed from a binary sequence array m of order n, comprising: capturing an image of a portion of the pattern such that the captured image includes at least n b
What is claimed is: 1. A method, preformed by a computer having a memory and a processor, of determining a position of a bit s in a pattern formed from a binary sequence array m of order n, comprising: capturing an image of a portion of the pattern such that the captured image includes at least n bits b of the array m; with a processor, solving for r where b=rM, M ^ = ( m t σ ( m t ) ⋮ σ n - 1 ( m t ) ) , σx (mt)_is the xth_cyclic shift of mt, and M is a subset of {circumflex over (M)} by: (a) randomly selecting n bits b(0) from the set of bits b so as to leave remaining bits b(0), (b) determining a number of different bits d(0) where d(0) is the number of different bits between ([b(0)]t,[ b(0)]t) and [r(0)]t(M(0), M(0)), (c) if the number of different bits d(0) is not zero, changing J bits of the n bits b(0) with J bits of b(0) to obtain n bits b(1) from the set of bits b so as to leave remaining bits b(1) and bits b(1) are different from bits b(0), (d) updating r according to the following formula: [r(1)]t=[r(0)]t+[e(0)]tEl−n[PRJ(0)]−1Ekt[M(0)]−1, (e) determining a number of different bits d(1) where d(1)=HammingWeight([e(0)]t+EjP(0))+J, (f) repeating (a)˜(d) an estimated number of times in order to ensure a high probability of successful decoding, and (g) outputting r that corresponds to the smallest value of d; and with a processor, employing a discrete logarithm technique to obtain the location of s in r. 2. The method recited in claim 1, further comprising: obtaining bits b(1) from bits b(0) by flipping J bits in b(0) by: (h) randomly selecting n bits b(0) from the set of bits b so as to leave remaining bits b(0), (i) determining a number of different bits d(0) where d(0) is the number of different bits between ([b(0)]t,[ b(0)]t) and [r(0)]t(M(0), M(0)), (j) if the number of different bits d(0) is not zero, flipping J bits of the n bits b(0) to obtain n bits b(1), (k) updating r according to the following formula: [r(1)]t=[r(0)]tEJ[M(0)]−1 , (l) determining a number of different bits d(1) where d(1)=HammingWeight([e(0)]t+Ej P(0))+J, (m) repeating (h)˜(k) for some estimated times in order to ensure a high probability of successful decoding, and (n) outputting r that corresponds to the smallest value of d; and employing a discrete logarithm technique to obtain the location of s in r. 3. The method of claim 1, where the n bits of b(0) are selected by Gaussian elimination. 4. The method of claim 1, wherein the position of the bit s in the array corresponds to a geometric position of the bit s on a writing media. 5. The method of claim 1, further comprising: determining a position of bits s in an array having a first dimension and a second dimension; and determining a cyclical shift between the bits s so as to identify the cyclical shift between the first dimension and the second dimension. 6. The method of claim 1, further comprising: solving multiple-dimension arrays simultaneously. 7. A computer-readable storage medium containing instructions that, when executed by a computer having a memory and a processor, cause the computer to perform a method for determining a position of a bit s in a pattern formed from a binary sequence array m of order n, the method comprising: capturing an image of a portion of the pattern, the image including bits b of the array m ; solving for r where b =rM, M ^ = ( m t σ ( m t ) ⋮ σ n - 1 ( m t ) ) , σx (mt) is the xth cyclic shift of mt , and M is a subset of M, at least in part by: (a) randomly selecting bits b(0) from the set of bits b so as to leave remaining bits b (0), (b) determining a number of different bits, d(0), ([b(0)]t,[ b(0)]t) and [r(0)]t(M(0), M(0)), (c) if the number of different bits d(0) is not zero, changing J bits of b(0) with J bits of b (0) to obtain b(1), wherein bits b(1) are different from bits b(0), (d) updating r according to the following formula: [r(1)]t=[r(0)]t[e(0)]tEl−n[PRJ(0)]−1Ekt[M(0)]−1, (e) determining a number of different bits d(1) , where d(1)=HammingWeight([e(0)]t+EJP(0))+J, and (f) outputting r corresponding to the smallest value of d; and employing a discrete logarithm technique to obtain the location of s in the output r. 8. The computer-readable storage medium of claim 7, the method further comprising: obtaining bits b(1) from bits b(0) by flipping J bits in b(1) by: randomly selecting bits b(1) from b so as to leave remaining bits b (0) , determining a number of different bits, d(0), between, ([b(0)]t,[ b(0)]t) and [r(0)]t(M(0), M(0)) , if the number of different bits d(0) is not zero, flipping J bits of b(0) to obtain bits b(1), updating r according to the following formula: [r(1)]t=[r(0)]tEJ[M(0)]−1, determining a number of different bits d(1) where d(1)=HammingWeight([e(0)]t+EJP(0))+J, and outputting r corresponding to the smallest value of d. 9. The computer-readable storage medium of claim 7 wherein the randomly selected bits b(0) are selected from b by Gaussian elimination. 10. The computer-readable storage medium of claim 7 wherein the position of the bit s in the array corresponds to a geometric position of the bit s on a writing media. 11. The computer-readable storage medium of claim 7, the method further comprising: determining a position of bits s in an array having a first dimension and a second dimension; and determining a cyclical shift between the bits s so as to identify the cyclical shift between the first dimension and the second dimension. 12. The computer-readable storage medium of claim 7, the method further comprising: solving multiple-dimension arrays simultaneously. 13. The computer-readable storage medium of claim 7, wherein solving for r further comprises: repeating (a)˜(d) to increase a probability of successful decoding. 14. A computing device having a memory and a processor for determining a position of a bit s in a pattern formed from a binary sequence array m of order n, comprising: a component that captures an image of a portion of the pattern, the captured image including bits b of the array m ; and a component that. with a processor, solves for r where b=rM, M ^ = ( m t σ ( m t ) ⋮ σ n - 1 ( m t ) ) , σx(mt) is the xth cyclic shift of mt , and M is a subset of {circumflex over (M)} by: selecting bits b(0) from bits b leaving bits b (0) , determining a number of different bits, d(0), between ([b(0)]t,[ b(0)]t) and [r(0)]t(M(0), M(0)) , updating r according to the following formula: [r(1)]t=[r(0)]t[e(0)]tEl−n[PRJ(0)]−1Ekt[M(0)]−1, determining a number of different bits d(1) where d(1)=HammingWeight([e(0)]t+EJP(0))+J, and outputting r that corresponds to the smallest value of d. 15. The computing device of claim 14, further comprising: a component that obtains bits b(1) from bits b(0) by flipping J bits in b(0) by: randomly selecting bits b(0) from the set of bits b so as to leaving bits b (0) , determining a number of different bits, d(0), between ([b(0)]t,[ b(0)]t) and [r(0)]t([M(0), M(0)]) , if d(0) is not zero, flipping J bits of bits b(0) to obtain bits b(1), updating r according to the following formula: [r(1)]t=[r(0)]t=Ej[M(0)]−1, determining a number of different bits d(1) where d(1)=HammingWeight([e(0)]t+EJP(0))+J, and outputting r corresponding to the smallest value of d. 16. The computing device of claim 14 wherein bits b(1) are selected by Gaussian elimination. 17. The computing device of claim 16 wherein the position of the bit s in the array corresponds to a geometric position of the bit s on a writing media. 18. The computing device of claim 17, further comprising: a component that determines a position of bits s in an array having a first dimension and a second dimension; and a component that determines a cyclical shift between the bits s so as to identify the cyclical shift between the first dimension and the second dimension. 19. The computing device of claim 18, further comprising: a component that solves multiple-dimension arrays simultaneously. 20. The computing device of claim 19, further comprising: a component that employs a discrete logarithm technique to obtain the location of s in the output r.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (248)
Sekendur Oral F., Absolute optical position determination.
Anderson Gerald B. (Scarborough MD CAX) Bamford James H. (Gaithersburg MD) Betts Timothy S. (Germantown MD) Carras Valerie M. (Kensington MD) Concagh Michael C. (Damascus MD) Daley Michael E. (Rockvi, Advanced data capture architecture data processing system and method for scanned images of document forms.
Ahearn Kevin John (Matthews NC) Weaver Frederick M. (Charlotte NC) DeArras James M. (Richmond VA) Stant Vernon L. (Richmond VA) Trautwein James A. (Charlotte NC), Audio proof of delivery system and method.
Pine Jerrold S. (Boca Raton FL) Blitman Gary K. (Boynton Beach FL) Grinage Brian L. (Boynton Beach FL) Gonzalez German (Miami FL), Binary code matrix having data and parity bits.
Omura, Katsuyuki; Inoue, Takao, Coordinate position inputting/detecting device, a method for inputting/detecting the coordinate position, and a display board system.
Ide, Tsuyoshi; Mizuta, Hideyuki; Taira, Yoichi; Nishikai, Akiko, Discrete pattern, apparatus, method, and program storage device for generating and implementing the discrete pattern.
Kieval Robert S. (Golden Valley MN) Hess Michael F. (Minneapolis MN), Dual chamber pacing system and method with continual adjustment of the AV escape interval so as to maintain optimized ve.
, Electronic input device, system, and method using human-comprehensible content to automatically correlate an annotation of a paper document with a digital version of the document.
Hecht David L. ; Jared David A. ; Flores L. Noah ; Stearns Richard G. ; Chang Kenneth H. P., Glyph address carpet methods and apparatus for providing location information in a multidimensional address space.
Hill, William; Duggan, Michael; Keely, Jr., Leroy B.; Hitchcock, Gregory C.; Whitted, J. Turner, High resolution display of image data using pixel sub-components.
Sant\Anselmo Carl (Rancho Palos Verdes CA) Sant\Anselmo Robert (Canoga Park CA) Hooper David C. (Ramona CA), Identification symbol system and method with orientation mechanism.
Yamakawa Shinji,JPX, Image processing apparatus and method for distinguishing alphanumeric symbols on a white background and those on a mesh pattern and individually processing such image data.
Akira Morishita JP; Hiroshi Mizoguchi JP, Information input device, position information holding device, and position recognizing system including them.
Fukuda Hiroyuki,JPX ; Mori Takeshi,JPX ; Tatsuta Seiji,JPX, Information reproduction system which utilizes physical information on an optically-readable code and which optically r.
Collins Roger ; Robinson Tony ; Jenkins Yolanda ; DiGrazia Karla ; Ozer Stuart ; Freedman Bryan ; Voce Maurice ; Devon Jane ; Briggs Chris, Interactive play with a computer.
Franz Alexander M. ; Horiguchi Keiko, Method and apparatus for adaptive speech recognition hypothesis construction and selection in a spoken language translation system.
Gorr Russell E. ; Hancock Thomas R. ; Judd J. Stephen ; Lin Long-Ji ; Novak Carol L. ; Rickard ; Jr. Scott T., Method and apparatus for automatically tracking the location of vehicles.
Shellhammer Stephen J. (Lake Grove NY) Nikzad Arman (Holbrook NY) Swartz Jerome (Old Field NY), Method and apparatus for decoding two-dimensional bar code.
Steiner Gerd (Heusenstamm DEX) Weniger Rudi (Offenbach am Main DEX) Braun Rolf (Offenbach am Main DEX) Otterbach Rainer (Siegen DEX) Schubert Erhard (Bad Berleburg DEX) Hofmann Ralf (Siegen DEX), Method and apparatus for determining register differences from a multi-color printed image.
Gorbet, Matthew G.; Flores, L. Noah; Hecht, David L.; Banerjee, Shilajeet, Method and apparatus for display of spatially registered information using embedded data.
Kouichi Kashiwagi JP; Naoki Urano JP; Kouji Akasaka JP, Method and apparatus for electronic memo processing for integrally managing document including paper document and electronic memo added to the document.
Comerford Liam D. (Carmel NY) Ellozy Hamed A. (Bedford Hills NY) Jelinek Frederick (Briarcliff Manor NY) Levy Stephen E. (Valhalla NY) Nahamoo David (White Plains NY), Method and apparatus for improving the paper interface to computing systems.
Monroe James C. (San Diego CA) Roberts Stephen E. (San Diego CA) Knoche Thomas A. (San Diego CA), Method and apparatus for processing ideographic characters.
Crosby,Matt; Wilkins,David C., Method and apparatus for rendering a low-resolution thumbnail image suitable for a low resolution display having a reference back to an original digital negative and an edit list of operations.
Brandenberg, Carl Brock; Kay, Robert L.; Maxwell, Kenneth J.; Cotter, R. Brandon, Method and apparatus for scheduling presentation of digital content on a personal communication device.
Stork David G. ; Angelo Michael ; Wolff Gregory J., Method and apparatus for tracking a hand-held writing instrument with multiple sensors that are calibrated by placing the writing instrument in predetermined positions with respect to the writing sur.
Cassorla Elie (Croton-on-Hudson NY) de Vries Jacqueline P. (Mahwah NJ) Moran Michael E. (Spring Valley NY) Slater James J. (Boulder CO) Unger Jay (Mohegan Lake NY), Method for associating annotation with electronically published material.
Anderson Gerald B. (Scarborough CAX) Gross Brent P. (Scarborough CAX) Marlin James W. (Longmont CO) Tucker Von D. (Roanoke TX), Method for storing and retrieving annotations and redactions in final form documents.
Van Gils Willibrordus J. (Eindhoven NLX), Method of identifying objects provided with a code field containing a dot code, a device for identifying such a dot code.
Jared David A. ; Flores L. Noah ; Hecht David L. ; Stearns Richard G. ; Chang Kenneth H. P., Methods and apparatus for robust decoding of glyph address carpets.
Dougherty Thomas J. ; Mountford S. Joy ; Dorogusker Jesse L. ; Boyden James H. ; van Allen Philip A. ; Cummings Daniel E. ; Ullmer Brygg A., Methods and systems for providing human/computer interfaces.
Fauver, Mark E.; Seibel, Eric J.; Brown, Chris M.; Reinhall, Per G.; Smithwick, Quinn Y. J., Micro-fabricated optical waveguide for use in scanning fiber displays and scanned fiber image acquisition.
Roustaei Alexander R. ; Lawrence Roland L. ; Lebaschi Ali ; Bian Long-Xiang ; Fisher Donald, Optical scanner for reading and decoding one- and-two-dimensional symbologies at variable depths of field including mem.
Bennett William E. (Mahopac NY) Boies Stephen J. (Mahopac NY) Davies Anthony R. (Romsey NY GB2) Etzold Karl-Friedrich (Briarcliff Manor NY) Rodgers Todd K. (Chappaqua NY), Optical stylus and passive digitizing tablet data input system.
Lazzouni Mohamed (Worcester MA) Kazeroonian Ali Seyed (Framingham MA) Gholizadeh Dariush (Framingham MA) Ali Omar (Roslindale MA 4), Pen and paper information recording system.
Lazzouni Mohamed (Worcester MA) Yousaf Mohamed (Shrewsbury MA) Qureshi Rizwan A. (Worcester MA) Nazir Naveed A. (Shrewsbury MA), Pen and paper information recording system using an imaging pen.
Whitehurst, Todd K.; McClure, Kelly H., Physiologically based adjustment of stimulation parameters to an implantable electronic stimulator to reduce data transmission rate.
Swartz, Jerome; Tan, Chinh; He, Duanfeng; Joseph, Eugene; Katz, Joseph, Portable instrument for electro-optically reading indicia and for projecting a bit-mapped color image.
Olive Arthur L. ; Pederson Brian D. ; Kadhiresan Veerichetty A. ; Villalta Donald L., Self-calibration system for capture verification in pacing devices.
Axman Michael S. (W. Henrietta NY) Barry Michael J. (Rochester NY) Mathieu Michael S. (Rochester NY) Timmermans Jozef (Bilsen BEX) Richards Norman (Horsham GB2), Storage and retrieval of digitized photographic images.
Schubert Karl D. (Rockville MD) Verrier Guy F. (Boca Raton FL) Gray Michael (Annapolis MD), Stylus tilt detection apparatus for communication with a remote digitizing display.
Bellegarda Eveline Jeannine (Goldens Bridge NY) Bellegarda Jerome Rene (Goldens Bridge NY) Nahamoo David (White Plains NY) Nathan Krishna Sundaram (New York NY), System and method for automatic handwriting recognition with a writer-independent chirographic label alphabet.
Mitchell, Joan Laverne; Brady, Michael Thomas; Trelewicz, Jennifer Q., System and method for enabling multiple signed independent data elements per register.
Cass Todd A. (San Francisco CA) Saund Eric (San Carlos CA), System for registering component image tiles in a camera-based scanner device transcribing scene images.
Gerety, Eugene P.; Strempski, Richard A.; Sardi, Stephen G., Two-dimensional printed code for storing biometric information and integrated off-line apparatus for reading same.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.