JP4833555B2 - Enhanced method of m-sequence decoding and error correction - Google Patents

Description

  The present invention relates to interaction with a medium using a digital pen. More particularly, the present invention relates to determining the position of a digital pen during interaction with one or more surfaces.

  Computer users always use a mouse and keyboard as a means of interaction with a personal computer. Personal computers offer several advantages over handwritten documents, but most users continue to perform several functions using printed materials. Some of these functions include reading documents and annotating them. When annotating, the printed document is more meaningful because it is annotated by the user. However, one problem with having an annotated printed document is that the annotation must later be re-entered into an electronic document. This requires the original user or another user to read the annotations and enter them into a personal computer. In some cases, the user captures annotations and original text with a scanner, thereby creating a new document. These multiple steps make it difficult to repeatedly handle the interaction between a printed document and an electronic version of the document. In addition, images captured by a scanner often cannot be changed. There is no way to separate the annotation from the original text. This makes it difficult to use annotations. Therefore, there is a need for an improved method for processing annotations.

  One technique for capturing handwritten information is by using a pen that can determine its position during writing. One pen with this function is Anoto Inc. Anoto pen. This pen works by using a camera to capture an image of the paper encoded with a predefined pattern. An example of the image pattern is shown in FIG. This pattern is used by the Anoto pen (according to Anoto Inc.) to determine the position of the pen on the paper. However, it is unclear how efficient the position determination by the system used by the Anoto pen is. In order to provide an efficient determination of the position of the captured image, a system is needed that provides efficient decoding of the captured image.

  Several documents disclose technical contents related to the above-described conventional technique (for example, see Non-Patent Document 1).

Douglas W. Clark and Lih-Jyh Weng, "Maximal and Near-Maximal Shift Register Sequences: Efficient Event Counters and Easy Discrete Logarithms," IEEE Transactions on Computers 43.5 (May 1994, pp 560-568)

  The conventional system has various problems as described above, and further improvement is desired.

  The present invention has been made in view of such circumstances, and an object of the present invention is to provide an enhanced technique for decoding and error correction of an m array.

  Aspects of the invention can provide a solution to at least one of the above problems, thereby locating a captured image on a document displayed in a predefined pattern. The displayed document may be in a predefined pattern on paper, an LCD (liquid crystal display) screen, or any other medium. Aspects of the invention include a decoding process that enables efficient decoding of a captured image and that can provide an efficient determination of the position of the image.

  According to one aspect of the present invention, the decoding process appropriately selects a subset of bits from the bits extracted from the captured image. According to another aspect of the invention, the process adjusts the number of iterations that the decoding process performs. According to another aspect of the present invention, the process determines the X, Y coordinates of the extracted bit position such that the X, Y coordinates match a local constraint such as a destination area. These and other aspects of the invention will be understood through the following drawings and related description.

  The foregoing summary, as well as the following detailed description of the preferred embodiments, can be better understood when read in conjunction with the appended drawings. The accompanying drawings are included as examples and are not intended as limitations on the claimed invention.

  Embodiments to which the present invention can be applied will be described below in detail with reference to the drawings. Aspects of the invention relate to determining the position of a captured image relative to a larger image. The position determination method and system described herein can be used with a multifunction pen.

  The following are separated by subtitles for the reader. Subtitles include terminology, general purpose computers, image capture pens, array encoding, decoding, error correction, and position determination.

The term pen-any writing instrument. It may or may not include a function of storing ink. In some examples, a stylus without ink function can be used as a pen according to embodiments of the present invention.

  Camera—an image capture system that can capture images from paper or any other medium.

General Purpose Computer FIG. 1 is a functional block diagram of an example of a conventional general purpose digital computing environment that can be used to implement various aspects of the present invention. In FIG. 1, computer 100 includes a processing unit 110, a system memory 120, and a system bus 130 that couples various system components including the system memory to the processing unit 110. The system bus 130 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. The system memory 120 includes read only memory (ROM) 140 and random access memory (RAM) 150.

  A BIOS (Basic Input / Output System) 160 includes a basic routine that assists in transferring information between elements in the computer 100 such as during startup, and is stored in the ROM 140. The computer 100 reads from and writes to a hard disk (not shown), a hard disk drive 170 to read from, a magnetic disk drive 180 to read from or write to a removable magnetic disk 190, and a CD (compact disc) -ROM or other optical media, etc. Also included is an optical disk drive 191 that reads from or writes to the removable optical disk 192. The hard disk drive 170, magnetic disk drive 180, and optical disk drive 191 are connected to the system bus 130 by a hard disk drive interface 192, a magnetic disk drive interface 193, and an optical disk drive interface 194, respectively. The drive and its associated computer readable media provide non-volatile storage for computer readable instructions, data structures, program modules, and other data on the personal computer 100. Examples of operating environments include other types of computer readable media capable of storing computer accessible data, such as magnetic cassettes, flash memory cards, digital video disks, Bernoulli cartridges, random access memory (RAM), read only memory (ROM), etc. Those skilled in the art will appreciate that can also be used.

  Storing several program modules on the hard disk 170, magnetic disk 190, optical disk 192, ROM 140 or RAM 150, including the operating system 195, one or more application programs 196, other program modules 197, and program data 198. Can do. A user can input commands and information into the computer 100 through input devices such as a keyboard 101 and a pointing device 102. Other input devices (not shown) include a microphone, joystick, game pad, satellite dish, scanner, and the like. These and other input devices are often connected to the processing unit 110 via a serial port interface 106 that is coupled to the system bus, but connected by other interfaces such as a parallel port, game port, universal serial bus (USB), etc. May be. In addition, these devices can be directly coupled to the system bus 130 via a suitable interface (not shown). A monitor 107 or other type of display device is also connected to the system bus 130 via an interface, such as a video adapter 108. Personal computers typically include other peripheral output devices (not shown) such as speakers and printers in addition to a monitor. In the preferred embodiment, a pen digitizer 165 and an attached pen or stylus 166 are provided to digitally capture handwritten input. Although a direct connection between the pen digitizer 165 and the serial port is shown, in practice, the pen digitizer 165 includes a parallel port, or other interface and system bus 130, as is known in the art. To the processing unit 110 directly. Further, although the digitizer 165 is shown separated from the monitor 107, the usable input area of the digitizer 165 preferably has the same spread as the display area of the monitor 107. Further, the digitizer 165 may be integrated into the monitor 107 or may exist as a separate device that overlays the monitor 107, otherwise attached to the monitor 107.

  Computer 100 may operate in a networked environment using logical connections to one or more remote computers, such as remote computer 109. The remote computer 109 may be a server, router, network PC (personal computer), peer device, or other common network node, and generally includes many or all of the elements described above in connection with the computer 100, although FIG. Shows only the memory storage device 111. The logical connection shown in FIG. 1 includes a local area network (LAN) 112 and a wide area network (WAN) 113. Such networking environments are very common in offices, enterprise-wide computer networks, intranets, and the Internet.

  When used in a LAN networking environment, the computer 100 is connected to the local network 112 through a network interface or adapter 114. When used in a WAN networking environment, the personal computer 100 typically includes a modem 115 or other means for establishing communications over a wide area network 113 such as the Internet. The modem 115 may be internal or external and is connected to the system bus 130 via the serial port interface 106. In a networked environment, program modules shown in connection with the personal computer 100, or portions thereof, can be stored in a remote memory storage device.

  It will be appreciated that the network connections shown are examples and other techniques for establishing a communications link between the computers can be used. TCP / IP (Transmission Control Protocol / Internet Protocol), Ethernet (registered trademark), FTP (file transfer protocol), HTTP (HyperText Transport Protocol), Bluetooth (trademark), IEEE (Institute of Electrical and Electronics Engineers) 802.11x, etc. The existence of various well-known arbitrary protocols is envisioned and the system can operate in a client-server configuration so that a user can retrieve a web page from a web-based server. Any of a variety of conventional web browsers can be used to display data on a web page and manipulate it.

Image Capture Pen Aspects of the present invention include converting an encoded data stream into a display format that represents the encoded data stream (eg, using an encoded data stream as described in FIG. 4B, graphically). Create a pattern). The display format may be a printout (or other physical medium) or a display that projects an encoded data stream with another image or set of images. For example, the encoded data stream may be represented as a physical graphical image on paper, a graphical image overlaid on a displayed image (eg representing the text of a document), or a physical (modified) on the display screen Cannot be a graphical image (so any image portion captured by the pen can be located on the display screen).

  This determination of the position of the captured image can be used to determine the position of user interaction with the paper, media, or display screen. In some aspects of the invention, the pen can be an ink pen that writes on paper. In another aspect, the pen can be a stylus that the user writes on the surface of the computer display. Any interaction can be returned to a system that has knowledge of the encoded image on the document or that supports the document displayed on the computer screen. By repeatedly capturing images with a pen or stylus camera as the pen or stylus crosses the document, the system can track the movement of the stylus being controlled by the user. The displayed or printed image is a watermark associated with a blank or rich paper, or a watermark associated with the displayed image, or overlaps or appears on the screen. It can be a watermark associated with an embedded fixed coding.

  2A and 2B show an example of a pen 201 including a camera 203. FIG. The pen 201 includes a tip 202 that includes or does not include an ink cylinder. The camera 203 captures the image 204 from the surface 207. Pen 201 may further include additional sensors and / or processors, as represented by box 206 shown in dashed lines. These sensors and / or processor 206 may also include the ability to send information to another pen 201 and / or personal computer (eg, via Bluetooth ™ or other wireless protocol).

  FIG. 2B shows an image viewed from the camera 203. In one example, the field of view of camera 203 (ie, the resolution of the camera's image sensor) is 32 × 32 pixels (when N = 32). In this embodiment, the captured image (32 pixels × 32 pixels) corresponds to an area of approximately 5 mm × 5 mm of the plane captured by the camera 203. Accordingly, FIG. 2B shows a field of view 32 pixels long by 32 pixels wide. The size of N is adjustable, so the higher the N, the higher the resolution of the image. Also, the field of view of the camera 203 is shown here as a square for illustrative purposes, but can include other shapes as is known in the art.

An image captured by the camera 203 can be defined as a series of image frames {I _i }. Here, I _i is captured by pen 201 at sampling time t _i . The sampling rate may be high or low depending on the system configuration and performance requirements. The size of the captured image frame may be large or small depending on the system configuration and performance requirements.

  Images captured by the camera 203 can be used directly by the processing system or can be prefiltered. This pre-filtering can be performed with the pen 201 or outside the pen 201 (such as a personal computer).

  The image size in FIG. 2B is 32 × 32 pixels. If each encoding unit size is 3 × 3 pixels, the number of captured encoded units will be about 100 units. If the encoding unit size is 5 × 5 pixels, the number of captured encoded units will be about 36.

  FIG. 2A also shows an image plane 209 where a pattern image 210 from position 204 is formed. Light received from the pattern on the object plane 207 is focused by the lens 208. The lens 208 may be a single lens or a multi-part lens system, but is represented here as a single lens for simplicity. The image capturing sensor 211 captures the image 210.

  The image sensor 211 can be large enough to capture the image 210. Alternatively, the image sensor 211 can be large enough to capture the image of the nib 202 at the position 212. For reference, the image at position 212 is referred to as a virtual pen tip. Note that the position of the virtual nib relative to the image sensor 211 is fixed because the relationship between the nib, lens 208, and image sensor 211 is constant.

The next conversion F _{s → p} converts the position coordinates in the image captured by the camera into the position coordinates in the actual image on the paper.

L _paper = F _{s → p} (L _sensor )
During writing, the nib and the paper are on the same plane. Therefore, the conversion from the virtual nib to the real nib is also F _{s → p} ,
_Lpentip = Fs _{→ p} ( _{Lvirtual-pentip} )
It becomes.

The transformation F _{s → p} can be estimated as an affine transformation. this is,

Is simplified as an estimate of F _{s → p} . Where θ _x , θ _y , s _x , and s _y are the two orientation rotations and scales of the pattern captured at position 204. Furthermore, F ′ _{s → p} can be refined by matching the captured image with the corresponding real image on the paper. “Refinement” means obtaining a more accurate estimate of the transformation F _{s → p} by a kind of optimization algorithm called a recursive method. The recursive method treats the matrix F ′ _{s → p} as an initial value. A refined estimate more accurately represents the transformation between S and P.

  The position of the virtual nib can then be determined by calibration.

The pen tip 202 is placed on a fixed position L _petip on the paper. The pen is then tilted so that the camera 203 can capture a series of images of various pen poses. A transformation F _{s → p} can be obtained for each captured image. From this conversion, the virtual pen tip position L _{virtual-pentip} can be acquired.

L _{virtual-pentip} = F _{p → s} (L _pentip )
_Where L _pentip is initially set as (0,0),
F _{p → s} = (F _{s → p} ) ⁻¹
It is.

By averaging L _{virtual-pentip} acquired from each image, the position L _{virtual-pentip} of the virtual pen tip can be determined. With L _{virtual-pentip} , a more accurate estimate of _Lpentip can be obtained. After several iterations, the exact position L _{virtual-pentip} of the virtual nib can be determined.

Here, the position L _{virtual-pentip} of the virtual nib is known. It is also possible to obtain the transformation F _{s → p} from the captured image. Finally, this information can be used to determine the actual pen tip position L _pentip .

_Lpentip = Fs _{→ p} ( _{Lvirtual-pentip} )

Array Encoding A two-dimensional array can be constructed by folding a one-dimensional sequence. Any part of a two-dimensional array that contains a sufficiently large number of bits can be used to determine its position in a complete two-dimensional array. However, it may be necessary to determine the position from one or a few captured images. The array can be created using a non-repeating sequence to minimize the possibility that a portion of the captured image will be associated with more than one position in the two-dimensional array. One characteristic of the created sequence is that the sequence does not repeat over length (or window) n. The following describes the creation of a one-dimensional sequence and then the folding of the sequence into an array.

The sequence number of the sequence can be used as a starting point for the encoding system. For example, a sequence (also called an m-sequence) can be represented as a set of q elements in a field F _q . Here, q = pn, ^where n ≧ 1, and p is a prime number. The sequence or m-sequence can be generated by a variety of different techniques, including but not limited to polynomial division. Using polynomial division, the sequence can be defined as follows:

Where P _n (x) is a primitive polynomial of degree n in the field F _q [x] (having q ⁿ elements). R _l (x) is a non-zero polynomial of degree l (l <n) in the field F _q [x]. The sequence can be created using an iterative procedure in the next two steps. First, divide the two polynomials (resulting in an element of the field _Fq ), and secondly multiply the remainder by x. This operation stops when the output starts to iterate. This process can be implemented using a linear feedback shift register (see Non-Patent Document 1). In this environment, a relationship is established between the periodic shift of the sequence and the polynomial R ₁ (x). That is, only a periodic shift of the sequence is performed by changing R _l (x), and all periodic shifts correspond to the polynomial R _l (x). One of the characteristics of the resulting sequence is that the sequence has a period of q ⁿ −1, and within a period, over a certain width (or length) n, every part exists only once in the sequence. That is. This is called a “window property”. Period q ⁿ −1 is also called the length of the sequence, and n is also called the order of the sequence.

  However, the above process is one of various processes that can be used to create a sequence with window characteristics.

Array construction An array (or m-array) that can be used to create an image (some of which can be captured by a camera) is an extension of a one-dimensional or m-sequence. Assume that A is an array of periods (m1, m2), that is, A (k + m ₁ , l) = A (k, l + m ₂ ) = A (k, 1). When the n ₁ × n ₂ window shifts the period of A, all non-zero n ₁ × n ₂ matrices over F _q appear only once. This characteristic is also called “window characteristic” in that each window is unique. The window can then be represented as an array of periods (m ₁ , m ₂ ) (where m ₁ and m ₂ are the number of horizontal and vertical bits present in the array) and order (n ₁ , n ₂ ).

A binary array (or m-array) can be constructed by folding the sequence. One approach is to take a sequence and then fold it to a size of m ₁ × m ₂ . In this case, the length of the sequence is L = m ₁ × m ₂ = 2 ⁿ −1. Alternatively, start with a predefined size space you want to cover (eg 1 sheet, 30 sheets, or computer monitor size), determine the area (m ₁ × m ₂ ), and then its size Can be assumed to be L ≧ m ₁ × m ₂ . In this case, L = 2 ⁿ −1.

  Various different folding techniques can be used. For example, FIGS. 3A to 3C show three different sequences. Each of these can be folded into an array as shown in FIG. 3D. Three different folding methods are shown as the overlay in FIG. 3D and the raster path in FIGS. 3E and 3F. The folding method shown in FIG. 3D is adopted.

In order to create a folding method as shown in FIG. 3D, a sequence {a _i } of length L and order n is created. Next, an array {b _kl } of size m ₁ × m ₂ is created from the sequence {a _i } by assuming that each bit of the array is calculated as shown by Equation 1. In this case, gcd (m ₁ , m ₂ ) = 1 and L = m ₁ × m ₂ .

b _kl = a _i (1)
In the formula, k = imod (m ₁ ), l = imod (m ₂ ), i = 0,..., L−1.

  This folding technique can alternatively be represented as placing the sequence on the diagonal of the sequence and then continuing from the opposite edge when the edge is reached.

  FIG. 4A shows a sample encoding technique that can be used to encode the array of FIG. 3D. It should be understood that other encoding techniques can be used. For example, an alternative coding technique is shown in FIG.

  Referring to FIG. 4A, the first bit 401 (eg, “1”) is represented by a column of black ink. The second bit 402 (eg, “0”) is represented by a row of black ink. It should be understood that any color ink can be used to represent the various bits. The only requirement for the color of the selected ink is that it provides significant contrast and that the media background is distinguishable by the image capture system. The bits in FIG. 4A are represented by a 3 × 3 matrix of cells. The size of the matrix can be changed to any size based on the size and resolution of the image capture system. Alternative representations of bits 0 and 1 are shown in FIGS. It should be understood that the representation of one or zero in the encoding samples of FIGS. 4A-4E can be switched without effect. FIG. 4C shows a bit representation that occupies two rows or columns in an alternating arrangement. FIG. 4D shows an alternative arrangement of dashed line rows and columns of pixels. Finally, FIG. 4E shows a pixel representation of columns and rows in the form of irregular spacing (such as two black dots followed by one black dot).

  Returning to FIG. 4A, if the bits are represented by a 3 × 3 matrix and the imaging system detects one black row and two white rows in the 3 × 3 region, zero (or 1) is detected. When one black row and two white rows are detected, 1 (or 0) is detected.

  Here, one bit is represented using a pixel or dot larger than one. It is fragile to represent one bit using a single pixel (or bit). Dust, paper creases, uneven surfaces, etc. create the problem of reading a single bit representation of a data unit. However, it should be understood that different approaches can be used to illustrate the arrangement in a plane. Several approaches are shown in FIGS. 4C-4E. It should be understood that other approaches can be used. One approach that uses only space shifted dots is shown in FIG.

  The bitstream is used to create the graphical pattern 403 of FIG. 4B. Graphical pattern 403 includes 12 rows and 18 columns. Rows and columns are formed by a bitstream that is converted to a graphical representation using bit representations 401 and 402. FIG. 4B can be considered as having the following bit representation.

Decoding When writing with the pen of FIG. 2A or moving the pen near the encoded pattern, the camera captures an image. For example, the pen 201 may use a pressure sensor when pressed against the paper and across a document on the paper. The image is then processed to determine the orientation of the captured image relative to the full representation of the encoded image and extract the bits that make up the captured image.

  In determining the orientation of the captured image relative to the entire encoded area, one may notice that not all four possible corners shown in FIGS. 5A-5D may be present in the graphical pattern 403. In fact, in the proper orientation, the corner type shown in FIG. Accordingly, the orientation that lacks the corner type shown in FIG. 5A is the correct orientation.

  With continued reference to FIG. 6, the image 601 captured by the camera is analyzed and its orientation determined to be interpretable with respect to the position actually represented by the image 601. First, the image 601 is examined to determine the angle θ necessary for image rotation so that the pixels are aligned in the horizontal and vertical directions. Note that alternative grid arrangements are possible, including rotation of the underlying grid to a non-horizontal, non-vertical arrangement (eg, 45 degrees). Because users tend to focus on horizontal and vertical patterns before others, the use of non-horizontal, non-vertical arrangements can cause visual distractions from the user. May provide the potential for benefits of removal. For the sake of brevity, the grid orientation (the horizontal and vertical orientations of the underlying grid, and any other rotation) is collectively referred to as the predefined grid orientation.

  Next, the image 601 is analyzed to determine which corners are missing. The rotation amount ο required for rotation of the image 601 to the image 603 ready for decoding is represented by ο = (θ + rotation amount {defined by which corner is missing}). The amount of rotation is shown by the equation in FIG. Returning to FIG. 6, first the angle θ is determined by the pixel layout to reach the horizontal and vertical (or other predefined grid orientation) arrangement of pixels, and the image is rotated as shown at 602. The An analysis is then performed to determine the missing corners and image 602 is rotated to image 603 to set the image for decoding. Here, the image is rotated 90 degrees counterclockwise so that the image 603 has the correct orientation and can be used for decoding.

  It should be understood that the rotation angle θ can be applied before or after the rotation of the image 601 to take into account the missing corners. It should also be understood that all four types of corners may exist by taking into account noise in the captured image. The number of corners of each type can be counted and the least number of types can be selected as the missing corner type.

  Finally, the code in image 603 is read and correlated with the original bitstream used to create image 403. Correlation can be performed in several ways. For example, it can be performed by a recursive approach in which the recovered bitstream is compared to all other bitstream fragments in the original bitstream. Second, statistical analysis between the two bitstreams can be performed, for example, by using the Hamming distance between the recovered bitstream and the original bitstream. It should be understood that various techniques can be used to determine the position of the recovered bitstream within the original bitstream.

  Having obtained the recovered bits, it is necessary to locate the captured image in the original array (such as that shown in FIG. 4B). The process of determining the location of a segment of bits within the entire array is complicated by several items. First, the actual bits to be captured may be ambiguous (eg, the camera may capture handwritten images, which will obscure the original code). Second, dust, creases, reflections, etc. can also create captured image errors. These errors make the location process more difficult. In this regard, the image capture system may need to work on non-contiguous bits extracted from the image. The following represents a method that operates on non-contiguous bits from an image.

If n is the order of the m sequence, the sequence (or m sequence) I corresponds to the power series I (x) = 1 / P _n (x), K ≧ n, and the superscript t is a matrix or vector , Suppose that the captured image contains K bits of I b = (b ₀ b ₁ b ₂ ... B _k−1 ) ^t . The K bit position s is simply the number of I period shifts where b ₀ is shifted to the beginning of the sequence. This shifted sequence R then corresponds to a power series x ^s / P _n (x), ie R = T ^s (I). In the formula, T is a periodic shift operator. Find this s indirectly. The polynomial modulo P _n (x) forms a field. It is guaranteed that x ^s ≡r ₀ + r ₁ x +... r _n−1 x ⁿ⁻¹ mod (P _n (x)). Therefore, it can be seen that (r ₀ , r ₁ , +..., R _n-1 ), and then s can be solved for s.

The relationship ^{_{x s ≡r 0 + r 1 x}} + ··· r n-1 x n-1 mod (P n (x)) _{is, R = r 0 + r 1} T (I) + ··· r n-1 T implying ^n-1 (I). The binary linear equation is written as follows.

R = r ^t A (2)
Where r = (r ₀ r ₁ r ₂ ... R _n-1 ) ^t and A = (IT (I)... T ^n-1 (I)) ^t , which is 0 shift Consists of a period shift of I from (n-1) shifts. Here, only sparse K bits in R can be used to solve r. Assuming that the difference in exponent between b _i and b ₀ in R is k _i , i = 1, 2,..., K−1, i = 1, 2,. In this case, the first element and the (k _i +1) th element of R are exactly b ₀ , b ₁ ,..., B _k−1 . i = 1,2, ···, by selecting the first element and _(k i +1) th element of A in the case of k-1, the following binary linear equation is formed.

b ^t = r ^t M (3)
Where M is an n × K submatrix of A.

  If b is error-free, the solution for r can be expressed as:

  Where

Is an arbitrary non-degenerate n × n submatrix of M;

Is the corresponding submatrix of b.

Using the known r and using the Pohlig-Hellman-Silver algorithm, such that x ^s ≡r ₀ + r ₁ x +... R _n−1 x ⁿ⁻¹ mod (P _n (x)) s can be found (see Non-Patent Document 1).

Since the matrix A (of size n × L if L = 2 ⁿ −1) can be very large, storing the entire matrix A should be avoided. In fact, as can be seen in the above process, given the extracted bits of exponent difference k _i , only the first and (k _i +1) th columns of A are relevant for the calculation. Given the size of the captured image, such selection of k _i is rather limited. Therefore, only those columns that may be involved in the calculation need be preserved. The total number of such columns is much smaller than L (where L = 2 ⁿ −1 is the length of the m sequence).

If there is an error in error correction b, the solution for r becomes more complex. The conventional method of decoding using error correction cannot be easily applied. This is because the matrix M associated with the captured image can change from one captured image to another.

Use a probabilistic approach. If an error bit number n _e at b is assumed to be relatively small compared to K, then select the correct n bits from the K bits of b, the portion of the corresponding M matrix

There is a high probability that is non-degenerate.

If all n bits selected are correct, the Hamming distance between b ^t and r ^t M, or the number of error bits associated with r, should be minimal. In this case, r is calculated by equation (4). It is likely that by repeating the process several times, the correct r that results in the smallest error bit can be identified.

If there is only one r associated with the smallest number of error bits, it is considered the correct solution. Otherwise, if r that is associated with the minimum number of error bits there are multiple, n _e is higher probability of exceeding an error correction capability of the code generated by M, the decoding process fails. The system can then proceed to process the next captured image. In another implementation, information regarding the previous position of the pen can be taken into account. That is, for each captured image, the destination area where the pen can be expected next can be identified. For example, if the user has not lifted the pen between the two image captures by the camera, the pen position determined by the second image capture should not be far from the first position. Each r associated with the minimum number of error bits is then checked to see if the position s calculated from r satisfies the position constraint, i.e., the position is within the specified destination area. be able to.

  If the position s satisfies the position constraint, the X and Y positions of the extracted bits in the array are returned. If the location constraints are not met, the decoding process fails.

  FIG. 8 illustrates a process that can be used to determine the position of a captured image in a sequence (or m-sequence). First, at step 801, a data stream associated with a captured image is received. In step 802, corresponding columns are extracted from A and a matrix M is constructed.

  In step 803, n independent column vectors are randomly selected from the matrix M and the vector r is determined by solving equation (4). This process is performed Q times (eg, 100 times) in step 804. The determination of the number of loops will be described in the section on calculating the number of loops.

  In step 805, r is sorted according to its associated error bit number. Sorting can be performed using various sorting algorithms known in the art. For example, a selective sorting algorithm can be used. The selective sorting algorithm is useful when the number of times Q is not large. However, as Q increases, other sort algorithms (such as merge sort) that more efficiently handle large numbers of items can be used.

  The system then determines in step 806 whether error correction was successful by checking whether multiple r are associated with the minimum number of error bits. If more than one r is associated with the minimum number of error bits, an error is returned at step 809 to signal that the decoding process has failed. Otherwise, in step 807, the extracted bit position s in the sequence (m-sequence) is calculated, for example by using the Pohig-Hellman-Silver algorithm.

Next, at step 808, the (X, Y) position in the array is calculated as x = s mod m ₁ and y = s mod m ₂ and the result is returned.

Position Determination FIG. 9 shows a process for determining the position of the pen tip. The input is an image captured by the camera, and the output can be the position coordinate of the pen tip. The output may include (or may not include) other information such as the rotation angle of the captured image.

  In step 901, an image is received from a camera. Next, in step 902 (as indicated by the dashed outline in step 902), such as adjusting the contrast between light and dark pixels, the received image can optionally be preprocessed. .

  Next, in step 903, the image is analyzed to determine the bitstream therein.

  Next, in step 904, n bits are randomly selected from the bitstream multiple times to determine the position of the received bitstream within the original sequence (or m-sequence).

  Finally, when the position of the captured image is determined in step 904, the position of the pen tip can be determined in step 905.

  FIG. 10 describes in more detail 903 and 904 and shows a technique for extracting the bitstream in the captured image. First, in step 1001, an image is received from a camera. The image can then optionally be subjected to image preprocessing at step 1002 (as indicated by the dashed outline in step 1002). In step 1003, a pattern is extracted. Here, pixels on various lines can be extracted to find the pattern orientation and angle θ.

  The received image is then analyzed at step 1004 to determine the underlying grid lines. If a grid line is found in step 1005, a code is extracted from the pattern in step 1006. Next, in step 1007, the code is decoded, and in step 1008, the position of the pen tip is determined. If no grid line is found in step 1005, an error is returned in step 1009.

Overview of Enhanced Decoding and Error Correction Algorithm In the embodiment of the present invention shown in FIG. 12, m is provided if the extracted bits 1201 from the captured image (corresponding to the captured area) and the destination area are given. A variant of the array decoding and error correction process decodes the X, Y positions. FIG. 12 shows a flow diagram of a process 1200 for this enhanced approach. Process 1200 includes two components 1251 and 1253.

A single decode component 1251 includes three parts.
Random bit selection: a subset of extracted bits 1201 is selected randomly (step 1203)
Decode the subset (step 1205)
Determine X and Y positions under position constraints (step 1209)

The decoding component 1253 with Smart Bit Selection includes four parts.
Smart bit selection: Select another subset of extracted bits (step 1217)
Decode the subset (step 1219)
Adjust the number of iterations (number of loops) of step 1217 and step 1219 (step 1221)
Determine X and Y positions under position constraints (step 1225)
Embodiments of the present invention use a careful strategy to select bits, adjust the number of loop iterations, and determine X, Y positions (position coordinates) according to position constraints, which are provided to process 1200. In both components 1251 and 1253, steps 1205 and 1219 (one-time decoding) calculate r using equation (4).

Are the decoded bits. Ie

It is. b and

Is the error bit associated with r.

  FIG. 12 shows a flow diagram of a process 1200 for decoding extracted bits 1201 from a captured image according to an embodiment of the present invention. Process 1200 includes components 1251 and 1253. Component 1251 obtains extracted bits 1201 (including K bits) associated with the captured image (corresponding to the captured array). In step 1203, n bits (where n is the order of the m array) are randomly selected from the extracted bits 1201. In step 1205, the process 1200 performs decoding once and calculates r. At step 1207, process 1200 determines whether an error bit is detected for b. If step 1207 determines that there are no error bits, the X and Y coordinates of the position of the array captured in step 1209 are determined. In step 1211, if the X and Y coordinates satisfy the position constraint, that is, the coordinates are within the destination area, the process 1200 sets the X and Y positions in step 1213 (for example, another process or user interface). To) to provide. Otherwise, step 1215 provides an indication of failure.

  If step 1207 detects an error bit in b, component 1253 is executed to decode including the error bit. Step 1217 selects another set of n bits from extracted bits 1201 (which differs from the n bits selected in step 1203 by at least one bit). Steps 1221 and 1223 determine the number of iterations (number of loops) required for decoding the extracted bits. Step 1225 determines the position of the captured sequence by testing which candidates obtained in step 1219 satisfy the position constraint. Steps 1217 to 1225 will be described in more detail.

The smart bit selection step 1203 randomly selects n bits from the extracted bits 1201 (with K bits) and solves for r ₁ . Equation (5) can be used to calculate the decoded bits.

Is

Is the kth bit of

B ₁ = {b _k | kεI ₁ } and

Assume that That is, B ₁ is the decoded bit with the same bits as the original bit,

Is a bit whose decoded result is different from the original bit, and I ₁ and

Is the corresponding exponent of these bits. If any of the n bits are selected from B _1, it is to be understood that the same r ₁ is obtained. Thus, if the next n bits are not carefully selected, the selected bits are a subset of B ₁ and therefore the same r ₁ may be obtained.

To avoid this situation, step 1217 selects the next n bits according to the following procedure.
1. At least one bit

1303 and select the remaining bits as B ₁ 1301 and

A random number is selected from 1303. This corresponds to the bit array 1351 as shown in FIG. Process 1200 then solves r ₂ and

B ₂ 1305, 1309, and

Find 1307, 1311.
2. Repeat step 1. When selecting the next n bits,

(I = 1, 2, 3,..., X−1, where x is the current number of loops)

There is at least one bit selected from If such a subset of bits cannot be selected, or if the number of loops has been reached, the iteration ends.

The loop count calculation error correction component 1253 adjusts the required iteration count (loop count) after each loop. The number of loops is determined by the expected error rate. Expected error rate p _e all n bits selected is not the correct reason is

It becomes. Where lt represents the number of loops, is initialized by a constant, K is the number of bits extracted from the captured array, and _ne is the minimum number of error bits that caused the error during the process 1200 iteration. N is the order of the m array,

Is the number of combinations where n bits are selected from K bits.

In this embodiment, we want p _{e to} be less than e ⁻⁵ = 0.0067. In combination with (6)

Is obtained. Adjusting the number of loops can significantly reduce the number of process 1253 iterations required for error correction.

In the X and Y position determination steps 1209 and 1225 under position constraints , the decoded position must be within the destination area. The destination area is an input to the algorithm and can be of various sizes and locations depending on different applications, or simply the entire m-array. This can usually be predicted by the application. For example, when the immediately preceding position is determined, the destination area of the current nib should be close to the immediately preceding position in consideration of the writing speed. However, if the pen is lifted, the next position can be anywhere. Therefore, in this case, the destination area should be the entire m array. The correct X, Y position is determined by the following steps.

  In step 1224, process 1200 determines that the corresponding number of error bits is

Choose less r _i . In the formula, lt represents the actual number of loops, and lr represents the position constraint rate calculated by the following formula.

In the formula, L is the length of the m sequence.

Step 1224 sorts r _i in ascending order of the number of error bits. Steps 1225, 1211, and 1212 then find the first r _i whose corresponding X, Y position is in the destination area. Steps 1225, 1211, and 1212 finally return the X, Y position as a result (via step 1213) or return an indication that the decoding procedure has failed (via step 1215).

An illustrative example of an enhanced decoding and error correction process demonstrates process 1200 performed by components 1251 and 1253. n = 3, K = 5, I = (I ₀ I ₁ ... I ₆ ) Let ^{t be} an m-sequence of order n = 3. In that case

It is. Also, when K = 5, the extracted bits b = (b ₀ b ₁ b ₂ b ₃ b ₄ ) ^t are actually s-th, (s + 1) -th, (s + 3) -th, (s + 4) -th in the m-sequence, and (s + 6) th assumed to be bits (the number of these is actually a factor of m array length ^{L = 2 n -1 = 2 3} -1 = 7). Therefore

And consists of the 0th, 1st, 3rd, 4th, and 6th columns of A. The number s that uniquely determines the X and Y position of b ₀ in the m array is calculated after solving r = (r ₀ r ₁ r ₂ ) ^t that is expected to satisfy b ^t = r ^t M. be able to. b ^t = r ^t M is not completely satisfied because error bits are possible at b.

  Process 1200 uses the following procedure. b to n = 3 bits, ie

Select at random. Solving for r ₁ ,

And in the formula

Consists of the 0th, 1st, and 2nd columns of M (

Is an n × n matrix,

Is a 1 × n vector, so

Note that is a 1 × n vector of selected bits).

  Next, the decoded bits are calculated.

Where M is an n × K matrix,

Is a 1 × n vector, so

Is a 1 × K vector.

Is the same as b, i.e., if no error bit is detected, step 1209 determines the X, Y position, and step 1211 determines whether the decoded position is within the destination area. If it is within the destination area, the decoding is successful and step 1213 is performed. Otherwise, the decoding fails as indicated by step 1215.

If is different from b, an error bit at b is detected and component 1253 is executed. Step 1217 determines a set B ₁ whose decoded bits are the same as the original bits, ie {b ₀ b ₁ b ₂ b ₃ }. Therefore

(Corresponding to the bit array 1351 in FIG. 13). The loop count (lt) is initially set to a constant, for example, 100. This can be variable depending on the application. Note that the number of error bits corresponding to r ₁ is equal to 1. Step 1221 then updates the loop count (lt) according to equation (7), so that lt ₁ = min (lt, 13) = 13.

Step 1217 then selects another n = 3 bits from b. If all the bits belong to B ₁ , eg {b ₀ b ₂ b ₃ }, step 1219 determines r ₁ again. In order to avoid such iterations, step 1217 can include, for example:

1 bit {b ₄ } is selected from B ₁ and the remaining 2 bits {b ₀ b ₁ } are selected from B ₁ .

  The selected 3 bits are

Form. Step 1219 solves for r ₂ .

Where

Consists of the 0th, 1st, and 4th columns of M.

  Step 1219

Is calculated.

Find the set B ₂ , eg {b ₀ , b ₁ , b ₄ }, so that and b are the same. In that case

(Corresponding to the bit array 1353 in FIG. 13). Step 1221 updates the number of loops (lt) according to equation (7). Note that the number of error bits associated with r ₂ is equal to 2. Substituting into equation (7) yields lt ₂ = min (lt ₁ , 32) = 13.

Step 1217 selects the other n = 3 bits from b because another iteration needs to be performed. All selected bits does not belong to B ₁ or B _2. Therefore, step 1217 is, for example,

1 bit {b ₄ } from

1 bit {b ₂ } and the remaining 1 bit {b ₀ }.

solution of r, bit selection, and until the loop count adjustment, can not be a new n = 3 bits to select any new n = 3 bits as not belonging to any B _i before all, or maximum loop Continue until the number of times lt is reached.

Process 1200 calculates five r _i (i = 1, 2, 3, 4, 5) and assumes that the number of error bits corresponds to 1, 2, 4, 3, 2, respectively (in fact, this example In this case, the number of error bits cannot exceed 2, but this example shows a larger number of error bits to explain the algorithm). Step 1224 selects r _i , eg, r ₁ , r ₂ , r ₄ , r ₅ , and the corresponding number of error bits is less than N _{e as} shown in (8).

Step 1224 sorts the selected vectors r ₁ , r ₂ , r ₄ , r ₅ in ascending order r ₁ , r ₂ , r ₅ , r ₄ in their error bit number. From the sorted candidate list, steps 1225, 1211 and 1212, it finds its first vector r corresponding position is within the destination area, such as _{r 5.} Step 1213 then outputs the corresponding position. If none of the positions are within the destination area, the decoding process fails as indicated by step 1215.

Apparatus FIG. 14 shows an apparatus 1400 for decoding bits 1201 extracted from a captured array according to an embodiment of the present invention. The apparatus 1400 includes a bit selection module 1401, a decoding module 1403, a position determination module 1405, an input interface 1407, and an output interface 1409. In this embodiment, interface 1407 can receive extracted bits 1201 from different sources, including modules that support camera 203 (as shown in FIG. 2A). Bit selection module 1401 selects n bits from extracted bits 1201 according to steps 1203 and 1217. The decoding module 1403 decodes the selected bits (n bits selected from the K extracted bits selected by the bit selection module 1401) according to steps 1205 and 1219 to detect the detected bit errors and corresponding Determine the vector r _i . The decoding module 1403 presents the determined vector r _i to the position determination module 1405. The position determination module 1405 determines the X and Y coordinates of the array captured according to steps 1209 and 1225. The position determination module 1405 presents the output interface 1409 with the result including the X and Y coordinates if successful and including the error display if unsuccessful. The output interface 1409 can present the results to another module that can perform further processing or display the results.

  Apparatus 1400 may assume various forms of implementation, including modules that use computer-readable media and modules that use dedicated hardware such as application specific integrated circuits (ASICs).

  As can be appreciated by one of ordinary skill in the art, a computer system with an associated computer readable medium that includes instructions for controlling the computer system can be used to implement the example embodiments disclosed herein. The computer system may include at least one computer, such as a microprocessor, digital signal processor, and associated peripheral electronics.

  The present invention is defined using the claims, but the present invention is such that it is intended to include the elements and steps described herein in any combination or subcombination. The claims are exemplary. Thus, there are any number of alternative combinations defining the present invention that incorporate one or more elements from the description, claims, and the specification, including the drawings, into various combinations or sub-bonds. In view of this specification, alternative combinations of aspects of the invention, alone or in combination with one or more elements or steps as defined herein, as modifications or alternatives of the invention, or It will be apparent to those skilled in the art that it can be used as part. The described description of the invention contained herein is intended to cover all such modifications and alternatives.

FIG. 7 is a diagram illustrating a general description of a computer that can be used with embodiments of the present invention. FIG. 2 illustrates an image capture system and corresponding captured image according to an embodiment of the present invention. FIG. 2 illustrates an image capture system and corresponding captured image according to an embodiment of the present invention. FIG. 4 illustrates various sequences and folding techniques according to embodiments of the present invention. FIG. 4 illustrates various sequences and folding techniques according to embodiments of the present invention. FIG. 4 illustrates various sequences and folding techniques according to embodiments of the present invention. FIG. 4 illustrates various sequences and folding techniques according to embodiments of the present invention. FIG. 4 illustrates various sequences and folding techniques according to embodiments of the present invention. FIG. 4 illustrates various sequences and folding techniques according to embodiments of the present invention. FIG. 3 illustrates various encoding systems according to embodiments of the present invention. FIG. 3 illustrates various encoding systems according to embodiments of the present invention. FIG. 3 illustrates various encoding systems according to embodiments of the present invention. FIG. 3 illustrates various encoding systems according to embodiments of the present invention. FIG. 3 illustrates various encoding systems according to embodiments of the present invention. FIG. 4 shows the resulting four possible corners associated with the encoding system according to FIGS. 4A and 4B. FIG. 4 shows the resulting four possible corners associated with the encoding system according to FIGS. 4A and 4B. FIG. 4 shows the resulting four possible corners associated with the encoding system according to FIGS. 4A and 4B. FIG. 4 shows the resulting four possible corners associated with the encoding system according to FIGS. 4A and 4B. FIG. 6 is a diagram illustrating rotation of a captured image portion according to an embodiment of the present invention. FIG. 4D illustrates various angular rotations used with the coding system of FIGS. 4A-4E. FIG. 4 illustrates a process for determining the position of a captured sequence according to an embodiment of the present invention. It is a figure which shows the method of determining the position of the capture image by embodiment of this invention. FIG. 6 shows another method for determining the position of a captured image according to an embodiment of the present invention. It is a figure which shows the expression of the encoding space in the document by a prior art. FIG. 4 is a flow diagram illustrating decoding of bits extracted from a captured image according to an embodiment of the present invention. FIG. 4 is a diagram illustrating bit selection of bits extracted from a captured image according to an embodiment of the present invention. FIG. 3 illustrates an apparatus for decoding bits extracted from a captured image according to an embodiment of the present invention.

Explanation of symbols

201 pen 202 tip 203 camera 204 image 206 additional sensor and / or processor 207 surface 208 lens
209 Image plane 210 Image 211 Image sensor 212 Virtual pen tip 1400 Decoding device 1401 Bit selection module 1403 Decoding module 1405 Position determination module 1407 Input interface 1409 Output interface

Claims (5)

Captured in the first bit in the array that are encoding the position information on the surface, in order to determine the position of the second bit sequence corresponding to the image on the surface, by a computer having a memory and a processor a method performed, the surface of the image corresponding to the second bit sequence is captured by a camera provided in the pen, the position where the determined indicates the position of the pen relative to the surface,
(A) a step of obtaining the extract bits associated with the captured image, the extracted bits, see contains the location information that is encoded, the steps to be extracted from the captured image,
(B) on the bits that are acquired by decoding the extracted bits, if the error bit caused by ambiguity of the extraction bit is not present, by decoding the extracted bits, the position of the captured image Determining the coordinates;
(C) on the bits that are acquired by decoding the extracted bits, if the error bit caused by ambiguity of the extraction bit it exists, and determining the position coordinates of the captured image ,
By decoding the first subset consisting of bits selected randomly from the extraction bit, and determining the first candidate position coordinates of the captured image,
Determining whether the first candidate for position coordinates satisfies a position constraint, wherein the position constraint includes a specific area of the first bit array that should include the position coordinates of the image. To specify ,
When the first candidate of the position coordinates satisfy the constraints of the position, and selecting the first candidate of the position coordinates, as the position coordinates of the captured image,
When the first candidate for the position coordinate does not satisfy the position constraint,
And that from the extraction bit, selects a second subset composed of different bit from the first subset,
And the decoding the bits included in the second subset of the extracted bits to determine a second candidate coordinates of the captured image,
Second candidate of the position coordinates, when it is determined to match the constraints of the position, the second candidate of the position coordinates, by a selecting as the location coordinates of the captured image, wherein Determining the position coordinates of the captured image ; and
A method executed by the processor executing instructions stored in the memory. (B)
(I) selecting a third subset comprised of randomly selected bits from the extracted bits;
(Ii) decoding the third subset;
(Iii) in response to (ii), when the error bit in the third subset which are the decoding is not detected, the position coordinates of the second bit sequence corresponding to the position coordinates of the captured image the method according to claim 1, characterized in that it comprises a step of determining. A computer-readable storage medium comprising computer-executable instructions for performing the method of claim 1. A computer-readable storage medium comprising computer-executable instructions for performing the method of claim 2. An apparatus for determining a position of a second bit array corresponding to an image on the surface captured in an array of first bits encoding position information on a surface , wherein the second bit array image of the surface corresponding to the captured by a camera provided in the pen, the position where the determined indicates the position of the pen relative to the surface,
(A) means for obtaining extracted bits associated with the captured image , the encoded bits including encoded position information and extracted from the captured image ;
(B) on the bits that are acquired by decoding the extracted bits, if there are no error bits caused by ambiguity of the extraction bit by decoding the extracted bits, the position coordinates of the captured image Means to determine ,
The bits obtained by decoding the (C) the extracted bits, if there is an error bit caused by ambiguity of the extraction bit, and means for determining the position coordinates of the captured image,
By decoding the first subset consisting of bits selected randomly from the extraction bit, means for determining a first candidate position coordinates of the captured image,
First candidate of the position coordinates, means for determining whether to satisfy the constraints specified position a specific area coordinates within said first bit sequence should include the image,
When the first candidate of the position coordinates satisfy the constraints of the position, and means for selecting the first candidate of the position coordinates, as the position coordinates of the captured image,
When the first candidate for the position coordinate does not satisfy the position constraint,
Means for selecting , from the extracted bits , a second subset composed of bits different from the first subset ;
Means for decoding bits contained in the second subset of the extracted bits to determine second candidates for position coordinates of the captured image;
Second candidate of the position coordinates, when it is determined to match the constraints of the position, the second candidate of the position coordinates, and means comprising means for selecting as said position coordinates of the image A device characterized by that.

Images