Enhanced approach of m-array decoding and error correction
AssigneeMicrosoft Corporation
InventorsZhouchen Lin, Yue Li, Xiaoxu Ma, Jian Wang, Qiang Wang
Life of this patent
Estimating the term…
Abstract
A process and apparatus for determining the location of a captured array from a larger image is described. A non-repeating sequence may be folded into a non-repeating array in which the array is unique for every neighboring window of a given size. A portion of the array of the neighboring window may be captured and a subset of extracted bits corresponding to the captured array is decoded to identify error bits. The location of the captured array is determined within the non-repeating array by further processing the decoded bits.
Claims24
A method performed by a computer having a memory and a processor for determining a location of a captured array of bits within an original array, the original array encoding location information on a surface, wherein the captured array corresponds to an image of the surface captured by a camera of a pen, the determined location indicating the position of the pen relative to the surface, the method comprising:
- (A) obtaining extracted bits that are associated with the captured image, the extracted bits including encoded position information;
- (B) determining position coordinates of the center of the captured image by decoding a portion of the extracted bits directly if there are no error bits;
- and
- (C) if there are error bits, determining the position coordinates of the center of the captured image,
- determining first candidates for the position coordinates of the center of the captured image by decoding a first portion of the extracted bits,
- determining whether the first candidates are consistent with a local constraint, the local constraint identifying a portion of the original array containing eligible position coordinates,
- when the first candidates are consistent with the local constraint, selecting the first candidates as the position coordinates of the center of the image, and
- when the first candidates are not consistent with the local constraint, selecting additional portions of the extracted bits,
- decoding the selected additional portions of the extracted bits to determine candidates for the position coordinates of the center of the image, and
- when candidates for the position coordinates of the center of the image are determined that are consistent with the local constraint, selecting the candidates for the position coordinates of the center of the image that are consistent with the local constraint as the position coordinates of the center of the image
- wherein the determining, selecting, and decoding are performed by the processor executing instructions stored in the memory.
A method performed by a computer having a memory and a processor for determining a location of the center of an image containing an array captured from a surface by a camera pen, the method comprising:
- (A) obtaining extracted bits that are associated with the captured array, the extracted bits including encoded position information;
- (B) determining position coordinates directly from the extracted bits if there are no error bits;
- and
- (C) if there are error bits, determining the position coordinates from a portion of the extracted bits by non-repetitive bit selections, wherein the position coordinates are consistent with a local constraint, wherein (C) comprises:
- (i) if an error bit is detected, selecting a different subset from the extracted bits, wherein at least one bit of the different subset is from previous sets of error bits;
- (ii) decoding position information from the bits of the different subset;
- (iii) in response to (ii), determining whether another decoding iteration shall be performed;
- (iv) if another decoding iteration shall be performed, selecting another subset from the extracted bits and repeating (ii);
- and
- (v) if another decoding iteration shall not be performed, determining the position coordinates of the center of the image based at least in part on the decoded position information
- wherein the determining, selecting, and decoding are performed by the processor executing instructions stored in the memory.
An apparatus that determines position coordinates of a center of an image of a surface captured by a camera pen, the image containing a portion of an array of bits, comprising:
- (a) a bit selection module that applies a smart strategy to choose a subset of bits that has at least one bit from previous sets of error bits, the subset being selected from extracted bits that correspond to the captured image, the extracted bits including encoded position information;
- (b) a decoding module that processes the subset of bits to determine error information regarding the extracted bits and that determines whether another iteration of decoding is necessary from the error information;
- and
- (c) a position determination module that processes the error information and the position information encoded within the extracted bits to determine position coordinates of the center of the image, wherein the position coordinates are within a destination area, the destination area identifying a set of candidates for position coordinates of the center of the image.
A method performed by a computer having a memory and a processor for determining location coordinates of the center of a captured image of an array of bits within an original array captured of a surface by a camera pen, the method comprising:
- (A) receiving extracted bits that are associated with the captured array, the extracted bits including encoded position information;
- (B) selecting a first bit subset from the extracted bits;
- (C) decoding the first bit subset;
- (D) if no error bits are detected, determining candidate location coordinates of the center of the captured image by decoding the encoded position information, the location coordinates being within a destination area;
- (E) selecting a different subset from the extracted bits, wherein at least one bit of the different subset does not satisfy a matrix equation {circumflex over (b)}t=rtM, wherein {circumflex over (b)} corresponds to decoded bits, M is a matrix corresponding to a portion of the captured array, and r is a vector corresponding to the coefficients of a polynomial R used to generate the original array;
- (F) decoding selected bits of the different subset to determine error bits and candidate location coordinates of the center of the captured image;
- (G) adjusting a number of iterations for performing (F), the number being adjusted according to results from (F);
- (H) if another decoding iteration shall be performed, repeating (E)-(G);
- and
- (I) if another decoding iteration shall not be performed, determining the location coordinates of the center of the captured image based at least in part on the determined error bits and candidate location coordinates for each of the selected bits, wherein the location coordinates are within the destination area
- wherein the selecting, decoding, and determining are performed by the processor executing instructions stored in the memory.
Dependencies are inferred from the claim text.