TWI410894B - Method and apparatus for multiple one-dimensional templates block-matching, and optical mouse applying the method - Google Patents

Abstract

Method and apparatus for multiple one-dimensional templates block-matching utilize the one-dimensional block to search for a frame being read out and compared in the same time, and the time of the block matching is reduced and the operation circuit is simplifying to improve the frame rate and reduce the cost.

Description

Multi-plate one-dimensional block matching method and device thereof, and optical mouse for application thereof

The invention relates to a block matching method, in particular to a multi-plate one-dimensional block matching method and device thereof.

The moving object is tracked by a continuous frame generated by the sensor, and a motion vector (MV) is generated by using a block-matching algorithm (BMA) to determine the moving direction of the object. It is an efficient method. FIG. 1 is a schematic diagram 100 of generating a motion vector by a block matching method. By comparing two frames 110 and 120, for example, an n-1th frame and an nth frame, the search frame 120 generates a frame. The best matching block 132 of the template block (TB) 112 in 110 calculates the displacement between the best matching block 132 and the corresponding block 134 of the template block 112 in the frame 120. The motion vector 122, the motion vector 122, is the moving direction of the object. The conventional block matching method searches in a two-dimensional template block to produce a best matching block 132. 2 is a schematic diagram of an n-1th frame 110 in FIG. 1, and FIG. 3 is a schematic diagram of an nth frame 120 in FIG. Referring to FIG. 1 to FIG. 3, frames 110 and 120 have N×N pixels, and template block 112 is a two-dimensional block having M×M pixels. In order to search for the best matching block 132 in the frame 120. Therefore, the frame 120 is divided into a plurality of two-dimensional search blocks (SB) having M×M pixels, for example, SB ₁ to SB _{[ ( N - M + 1 ) × ( N - M + 1 ) ]} , absolute error between a gray level value of the block 112 calculates the search block and the template and SB _i, where i = 1 to [(N-M + 1) × (N-M + 1)], and produce search block SB _i Block matching coefficient of template block 112 Where TB(x, y) is the grayscale value of the pixel in the template block 112, and SB _i (x, y) is the grayscale value of the pixel in the i th search block. Seen from equation 1, coefficients S _i block matching search block SB _i represents a smaller degree of matching block 112 is higher, thus the block matching coefficient S _i smallest search block SB _i is the best matching block 132, such as a second search block SB ₂ . The movement vector 122 is generated according to the displacement between the search block SB ₂ and the corresponding block 134 of the template block 112 in the frame 120 to complete the tracking of the moving object. 4 is a conventional apparatus 200 for performing a block matching method. Referring to FIG. 1 to FIG. 4, the device 200 includes a sensor 201 for generating analog pixel data of the frame 120, such as a voltage signal, and an analog-to-digital converter 202 for converting the analog pixel data of the frame 120 into a digital position. The grayscale value, the memory 204 is used to store the two-dimensional template block 112, the memory 206 is used to store the position and grayscale value of the pixel in the frame 120, and a digital signal processor (DSP) 208 is used for the memory. Samples are taken in volume 206 to generate a plurality of two-dimensional search blocks SB _i , and block matching coefficients S _{i are} calculated to find the best matching block 132 to generate motion vectors 122. Since the conventional block matching method performs two-dimensional full-search on the frame 120, the signal processor 208 must perform [(N-M+1)×(N-M+1)] from the memory 206. The next sampling is to generate the search block SB _i , and [(N-M+1)×(N-M+1)] times the absolute value error and calculation of Equation 1 to generate the block matching coefficient S _i . Since the position of the pixel included in each search block SB _i is discontinuous, and the operation of the block matching coefficient S _i includes a subtraction, an addition, and an absolute value, and the memory 206 needs to store the data of the entire frame 120, Therefore, a good memory management mechanism and a large number of arithmetic units are required in the digital signal processor 208, which causes the circuit of the digital signal processor 208 to be too complicated and consumes the chip area and power, and requires a long time for the frame. The storage of 120 and the generation of the best matching block 132 result in an inability to increase the frame rate.

In order to increase the frame rate, a fast-search method has been proposed to reduce the number of sampling times and the number of operations of the block matching coefficient by estimating the possible positions of the best matching block 132 in advance. Although the method reduces the time for generating the best matching block 132 and achieves the purpose of increasing the frame rate, the generated motion vector is less accurate than the global search method, and the circuit of the digital signal processor 208 is still very complicated and cannot be Effectively reduce wafer area and power consumption. In order to ensure the accuracy of the motion vector, save the chip area and reduce the power consumption, an analog block matching method for sampling and computing with analog circuits has been proposed, such as the use of Mladen Panovic and Andreas Demosthenousy in 2006 in Senior Member, IEEE. The motion determination processor of the mixed signal method, as shown in FIG. 5, a sum squared error (SSE) analogy calculation circuit 300 is composed of transistors 302 to 312 and current sources 314 and 316. Output current when transistors 306 to 312 match each other and first order transistors 302 and 304 are saturated Where k is the conduction parameter and I _B is the DC bias current generated by current sources 314 and 316. When V ₁ is the analog value of one pixel in the template block, and V ₂ is the analog value of one pixel in the search block, the analog value includes the voltage value. Comparing Equation 1 and Equation 2, V _{1 is} equivalent to TB (x). , y), V _{2 is} equivalent to SB _i (x, y), and I _{0 is} equivalent to | TB(x, y) - SB _i (x, y)|. If M×M analogy calculating circuits 300 are used and the output current I _{0 of} each analog calculating circuit 300 is added and a resistor is input, the voltage difference across the resistor is equivalent to the block matching coefficient S _i , thereby greatly simplifying calculation block matching circuit complexity coefficient S _i block matching and to reduce the computational power required coefficients S _i. However, the analog block matching method based on the analogy calculation circuit 300 requires an analog memory such as a sample hold circuit (S/H circuit) to provide an analog value of the pixel. As shown in FIG. 6, a sample and hold circuit 350 includes switches 352, 358 and 360, capacitors 368 and 370, and an inverting amplifier 362 comprised of transistors 364 and 366. The switch 352 is composed of transistors 354 and 356, the gate of the transistor 356 is coupled to the signal Φ, and the gate of the transistor 354 is coupled to the signal. Switch 358 is controlled by signal Φ and switch 360 is controlled by signal . In general, the error between the input voltage V _{i of the} sample and hold circuit 350 and the output voltage V _o can be controlled to be around 6 mV. However, since the sampling process of the global search of the two-dimensional template block is complicated, the number of times the pixel data is moved is very large, and the cumulative error becomes large and is not easy to implement.

Therefore, a block matching method and an apparatus thereof which can improve the frame rate and reduce the circuit complexity and are easy to implement are the same.

The object of the present invention is to provide an easy-to-implement multi-plate one-dimensional block matching method and device thereof to improve frame rate and reduce circuit complexity.

According to the present invention, a multi-plate one-dimensional block matching method includes comparing a plurality of one-dimensional search blocks generated by a plurality of pixel data read from a frame to an independent plurality of one-dimensional template blocks, and generating And corresponding to the plurality of block matching coefficients, generating a plurality of priority blocks corresponding to each of the plurality of one-dimensional template blocks according to the block matching coefficients, and generating a motion vector according to the priority blocks.

According to the present invention, a multi-plate one-dimensional block matching device includes a memory circuit for storing a plurality of independent one-dimensional template blocks, and a buffer circuit generates a plurality of ones based on a plurality of pixel data read from a frame. a search block, a signal processing circuit generates a plurality of priority blocks for each of the plurality of one-dimensional search blocks and the plurality of one-dimensional template blocks, and a control circuit gives the plurality of priority blocks different rights The value is calculated by calculating a total weight of the plurality of priority blocks, and generating a motion vector according to a position between the largest priority block and the plurality of one-dimensional template blocks.

According to the present invention, an optical mouse using a multi-plate one-dimensional block matching method includes a light source for illuminating a surface to generate a reflected light, and a sensor for receiving the reflected light to generate a frame, a memory The circuit is configured to store a plurality of independent one-dimensional template blocks, and a buffer circuit generates a plurality of one-dimensional search blocks according to the plurality of pixel data read from the frame, and a signal processing circuit compares each of the plurality of blocks The one-dimensional search block and the plurality of one-dimensional template blocks generate a plurality of priority blocks, and a control circuit gives different weights of the plurality of priority blocks, and calculates a total weight of the plurality of priority blocks, according to the total A position between the highest priority block and the plurality of one-dimensional template blocks generates a motion vector.

The present invention utilizes a plurality of independent one-dimensional template blocks to perform a block matching method, so that the frame matching coefficient between the one-dimensional template blocks is simultaneously calculated in the process of being read, and in the message When the frame is read, the block comparison of the global search is completed, which improves the frame rate and reduces the circuit complexity and power consumption.

FIG. 7 is a schematic diagram of a multi-plate one-dimensional block matching method, and FIG. 8 is a device for performing the method. Referring to FIG. 7 and FIG. 8, the memory circuit 540 stores K one-dimensional template blocks TB ₁ to TB _{K in} a reference frame 410. Each of the board blocks TB _i has 1×B pixels, and the memory circuit 540 includes K. Memory cells 542 through 546 to store template blocks TB ₁ through TB _{K , respectively} . A frame 430 to be searched has N×N pixels. When the frame 430 is read from the sensor 570, the newly read B pixels forming the search block SB _{i are} temporarily stored in the buffer circuit 510. Where i=1 to N×(N−B+1), for example, when the first pixel (P ₁ ) to the Bth pixel (P _B ) are read, P ₁ to P _B constitute the search block SB ₁ , When the B+1th pixel (P _{B + 1} ) is read, P ₂ to P _{B + 1} constitute the search block SB ₂ , and when the N × N pixels P _{N × N} are read, P _{( N × N - B + 1 )} to P _{N × N} form the search block SB _{N ( N - B + 1 )} , so when the last pixel of the frame 430 is read, the global search of the frame 430 is also completed simultaneously. During the reading of the frame 430 from the sensor 570, the signal processing circuit 520 is based on the pixel data of the search block SB _i and the template blocks TB ₁ to TB _K in the buffer circuit 510 and the memory circuit 540, for example, analogous The voltage signal or the gray scale value of the digits is compared, and the control circuit 550 generates a motion vector 560 based on the result of the comparison by the signal processing circuit 520. In this embodiment, the buffer circuit 510 includes a memory circuit 512 for storing the newly read B pixel data, and a multiplexer 514 sequentially aligns the B pixel data to form a search block SB _{i for} providing signals. Processing circuit 520. The memory circuit 512 includes a plurality of sample and hold circuits as shown in FIG. 6, and the signal processing circuit 520 includes K calculation circuits 522 to 526 and K winning circuits 532 to 536. The calculation circuit 522 generates the block matching coefficient S _{i , 1} of the search block SB _i and the template block TB ₁ according to the pixel data of the search block SB _i and the template block TB ₁ provided by the multiplexer 514 and the memory unit 542. i=1 to N(N-B+1). The winning circuit 532 generates a plurality of priority blocks according to the block matching coefficient S _{i , 1} , for example, a front T name search block with a better matching degree with the template block TB ₁ , and records the positions of the priority blocks, for example, The relative coordinates of the template block TB ₁ . Similarly, the calculation circuits 524 and 526 generate priority corresponding to the template blocks TB ₂ to TB _K based on the pixel data of the search block SB _i and the template blocks TB ₂ to TB _K in the buffer circuit 510 and the memory units 542 to 546 . The location of the block. The control circuit 550 gives weights of different priority block positions of different rankings, and calculates a total weight of each position to generate a motion vector 560. A Department of FIG. 9 K = 6 and T = 3 the ratio of the results, the block and the template matching TB _{TB. 1} to ₆ of the first, second, and third positions are given priority blocks weights 3, 2 and 1, so the weights of positions (3, 2) in TB ₁ to TB ₆ are 3, 3, 2, 2, 0, 1, respectively, and the total weight is 3 + 3 + 2 + 2 + 0 + 1 = 11. Similarly, the total weight of each priority block location is calculated, and the priority block location with the largest total weight, such as location (3, 2), is the motion vector 560. In various embodiments, the buffer circuit 510 is implemented via a shift register or a sample and hold circuit.

10, in the present embodiment, the calculation circuit 522 to 526 is implemented by analog circuits, comprising a plurality of sum of squared errors SSE calculation circuit shown in Figure 5, according to the pixel information in the search block SB _i P _i of _{, j} , j = 1 to B, and pixel data r _{i , j} in the template blocks TB ₁ to TB _K , for example, analog voltage signals, where i=1 to K, and j=1 to B, using the formula 2 Generate block matching coefficients S _{i , 1} to S _{i , K} , i=1 to N(N-B+1) of the search block SB _i and the template blocks TB ₁ to TB _K . The parallel computing technique enables the search block SB _i to be simultaneously compared with the template blocks TB ₁ to TB _K , and the alignment is performed during the process in which the pixels are read, so the number of times the pixels are moved is small, There is a problem that the cumulative error becomes large and cannot be implemented. In addition, the addition of the block matching coefficients S _{i , 1} to S _{i , K} is achieved by combining the currents generated by each SSE according to Equation 2 into the resistor R, thereby greatly reducing the time and simplification required for calculating the block matching coefficient. The complexity of the circuit. In various embodiments, the calculation circuits 522 to 526 are implemented by a digital circuit, and the pixel data in the frame is read from the sensor 570, that is, converted into digital pixel data, such as gray scale values, by an analog digital converter. After the search block SB _{i is} generated, the block matching coefficients S _{i , 1} to S _{i , K} , i=1 to N(N−B+1) are generated according to the formula 1. Since the comparison is performed during the process of reading the pixels, it is not necessary to store all the pixel data and positions first, and it is not necessary to perform complex sampling on the stored pixel data to generate a search block, thereby effectively reducing the digital signal in FIG. The computing time of the processor 208 and the need for a memory management mechanism.

11 is an optical mouse 600 using a multi-plate one-dimensional block method, except that the searched frame 622 is focused on the table 616 via a lens group 612 to generate reflected light 620 via a light source 610, and then focused by the lens group 614. The detector 618 receives the generated, and the template block is the central block of the previously searched frame, and the rest of the calculation process and device are the same as those of FIG. 7, FIG. 8 and FIG. In the present embodiment, the light source 610 includes a light emitting diode, the sensor 618 includes a complementary metal oxide semiconductor sensor, and the number of pixels (eg, N×M) of the frame 622 is determined by the sensitivity of the sensor 618. . As shown in FIG. 12, in various embodiments, a multi-plate one-dimensional block matching method is implemented via a digital circuit. Since the frame 622 generated by the sensor 618 is an analog data, after the pixel data in the frame 622 is read, the analog pixel data is converted into digital pixel data by the analog digital converter 630. The operation. Since the optical mouse of the present invention performs parallel alignment during the reading of the pixels from the sensor 618, when the last pixel of the frame 622 is read from the sensor 618, the frame 622 is completed. The block search of the global search shortens the time required for the operation. Figure 13 is a schematic illustration of the time required for a conventional optical mouse to generate a motion vector, and Figure 14 is a schematic illustration of the time required to generate a motion vector using the optical mouse of the present invention. Referring to Figures 13 and 14, the time 740 of the conventional optical mouse to generate a motion vector includes the sensor exposure time 710, the frame readout time 720, and the operation time 730 of the block matching method, while applying the optical of the present invention. The time 750 required for the mouse to process the frame only includes the sensor exposure time 710 and the frame reading time 720, which saves the operation time 730, so that the frame rate is better, and the sensitivity of the sensor is more demanded. Low, and low circuit complexity.

100. . . Schematic diagram of generating a motion vector by block matching method

110. . . Frame

112. . . Template block

120. . . Frame

122. . . Moving vector

132. . . Best matching block

134. . . Corresponding block

200. . . Device for performing block matching method

201. . . Sensor

202. . . Analog digital converter

204. . . Memory

206. . . Memory

208. . . Digital signal processor

300. . . Square error and analogy calculation circuit

302. . . Transistor

304. . . Transistor

306. . . Transistor

308. . . Transistor

310. . . Transistor

312. . . Transistor

350. . . Sample and hold circuit

352. . . switch

354. . . Transistor

356. . . Transistor

358. . . switch

360. . . switch

362. . . Inverting amplifier

364. . . Transistor

366. . . Transistor

368. . . capacitance

370. . . capacitance

410. . . Reference frame

430. . . Searched frame

510. . . Buffer circuit

512. . . Memory circuit

514. . . Multiplexer

520. . . Signal processing circuit

522. . . Calculation circuit

524. . . Calculation circuit

526. . . Calculation circuit

532. . . Winning circuit

534. . . Winning circuit

536. . . Winning circuit

540. . . Memory circuit

542. . . Memory unit

544. . . Memory unit

546. . . Memory unit

550. . . Control circuit

560. . . Moving vector

570. . . Sensor

600. . . Optical mouse

610. . . light source

612. . . Lens group

614. . . Lens group

616. . . desktop

618. . . Sensor

620. . . reflected light

622. . . Frame

710. . . Sensor exposure time

720. . . Frame readout time

730. . . Operation time

740. . . Conventional optical mouse produces a time to move a vector

750. . . Time for generating a motion vector using the optical mouse of the present invention

1 is a schematic diagram of generating a motion vector by a block matching method; FIG. 2 is a schematic diagram of an n-1th frame in FIG. 1; FIG. 3 is a schematic diagram of an nth frame in FIG. 1; Figure 5 is a block error and analogy calculation circuit; Figure 6 is a sample and hold circuit; Figure 7 is a schematic diagram of a multi-plate one-dimensional block matching method; Figure 8 is a multi-plate one-dimensional block FIG. 9 shows a comparison result; FIG. 10 shows the calculation circuit of FIG. 8; FIG. 11 is a first embodiment of an optical mouse using a multi-plate one-dimensional block matching method; A second embodiment of an optical mouse using a multi-plate one-dimensional block matching method; FIG. 13 is a schematic diagram showing the time required for a conventional optical mouse to generate a motion vector; and FIG. 14 is an optical slide using the present invention. A schematic representation of the time required for a mouse to generate a motion vector.

410. . . Reference frame

430. . . Searched frame

Claims (27)

A multi-plate one-dimensional block matching method includes the following steps: (a) comparing a plurality of one-dimensional search blocks and independent multiple one-dimensional template regions generated by a plurality of pixel data read from a frame. Blocking, generating a plurality of corresponding block matching coefficients; (b) generating a plurality of priority blocks corresponding to each of the plurality of one-dimensional template blocks according to the block matching coefficients; and (c) according to the plurality of blocks The priority block produces a motion vector. The multi-board one-dimensional block matching method of claim 1, wherein the step (a) comprises sequentially arranging the plurality of pixel data. The multi-board one-dimensional block matching method of claim 1, wherein the step (a) comprises calculating a square error of pixel data in each of the plurality of one-dimensional search blocks and each of the plurality of one-dimensional template blocks. . The multi-plate one-dimensional block matching method of claim 1, wherein the step (a) comprises calculating an absolute value error of pixel data in each of the plurality of one-dimensional search blocks and each of the plurality of one-dimensional template blocks. with. The multi-board one-dimensional block matching method of claim 1, wherein the step (b) comprises selecting a plurality of one-dimensional search blocks corresponding to each of the plurality of one-dimensional template blocks to have a plurality of cell block matching The coefficient is used as the plurality of priority blocks. The multi-board one-dimensional block matching method of claim 5 further includes incrementing or decrementing the plurality of priority blocks according to their block matching coefficients. The multi-layer one-dimensional block matching method of claim 1, wherein the step (c) comprises the following steps: Giving the plurality of priority blocks different weights; calculating a total weight of the plurality of priority blocks; and generating the movement according to a position between the plurality of priority blocks having the largest total weight and the plurality of one-dimensional template blocks vector. The multi-board one-dimensional block matching method of claim 7, wherein the step of giving the plurality of priority blocks different weights comprises giving the highest weight of the priority block having the smallest block matching coefficient. A multi-plate one-dimensional block matching device includes: a first memory circuit for storing independent plurality of one-dimensional template blocks; and a buffer circuit for generating a plurality of pixel data according to a plurality of pixel data read from a frame a one-dimensional search block; a signal processing circuit that compares each of the plurality of one-dimensional search blocks and the plurality of one-dimensional template blocks to generate a plurality of priority blocks; and a control circuit that gives the plurality of priority areas The block has different weights, and calculates a total weight of the plurality of priority blocks, and generates a motion vector according to a position between the first block with the largest total weight and the plurality of one-dimensional template blocks. The multi-board one-dimensional block matching device of claim 9, wherein the first memory circuit comprises a plurality of memory cells to store the plurality of one-dimensional template blocks, respectively. The multi-plate one-dimensional block matching device of claim 9, wherein the buffer circuit comprises a displacement register. A multi-plate one-dimensional block matching device of claim 9, wherein the The buffer circuit includes: a second memory circuit for storing the plurality of pixel data; and a multiplexer for sequentially arranging the plurality of pixel values to generate the plurality of one-dimensional search blocks. A multi-plate one-dimensional block matching device of claim 12, wherein the second memory circuit comprises a plurality of sample and hold circuits. The multi-plate one-dimensional block matching device of claim 9, wherein the signal processing circuit comprises: a plurality of calculation circuits, generated according to pixel data in each of the plurality of one-dimensional search blocks and the plurality of one-dimensional template blocks a plurality of block matching coefficients; and a plurality of winning circuits, wherein the plurality of one-dimensional search blocks corresponding to each of the plurality of one-dimensional template blocks record a plurality of cell block matching coefficients to generate the plurality of priority Block. The multi-plate one-dimensional block matching device of claim 14, wherein the plurality of calculation circuits comprise square error and calculation circuits. A multi-plate one-dimensional block matching device as claimed in claim 14, wherein the plurality of calculation circuits comprise absolute value error and calculation circuits. An optical mouse using a multi-plate one-dimensional block matching method includes: a light source for illuminating a surface to generate a reflected light; and a sensor for receiving the reflected light to generate a frame; a memory circuit for storing a plurality of independent one-dimensional template blocks; a buffer circuit for generating a plurality of one-dimensional search blocks according to the plurality of pixel data read from the frame; a signal processing circuit for comparing each of the plurality of one-dimensional search blocks and the plurality of one-dimensional template regions The block generates a plurality of priority blocks; and a control circuit that gives the plurality of priority blocks different weights, calculates a total weight of the plurality of priority blocks, and the plurality of priority blocks according to the total weight and the plurality of The position between the one-dimensional template blocks produces a motion vector. An optical mouse using the multi-plate one-dimensional block matching method of claim 17, further comprising a first lens group for focusing the light source on the surface; and a second lens group for the reflection Light is focused on the sensor. An optical mouse using the multi-plate one-dimensional block matching method of claim 17, wherein the light source comprises a light emitting diode. An optical mouse using the multi-plate one-dimensional block matching method of claim 17, wherein the sensor comprises a complementary metal oxide semiconductor sensor. An optical mouse using the multi-plate one-dimensional block matching method of claim 17, wherein the first memory circuit includes a plurality of memory cells to store the plurality of one-dimensional template blocks, respectively. An optical mouse using the multi-plate one-dimensional block matching method of claim 17, wherein the buffer circuit includes a shift register. An optical mouse using the multi-plate one-dimensional block matching method of claim 17, wherein the buffer circuit comprises: a second memory circuit for storing the plurality of pixel data; and a multiplexer for sequentially arranging the plurality of pixel values to generate the plurality of one-dimensional search blocks. An optical mouse using the multi-plate one-dimensional block matching method of claim 23, wherein the second memory circuit includes a plurality of sample and hold circuits. An optical mouse according to claim 17, wherein the signal processing circuit comprises: a plurality of calculation circuits, sequentially according to each of the plurality of one-dimensional search blocks and the plurality of one-dimensional templates The pixel data in the block generates a plurality of block matching coefficients; and a plurality of winning circuits record a plurality of cell block matching coefficients in the plurality of one-dimensional search blocks corresponding to each of the plurality of one-dimensional template blocks To generate the plurality of priority blocks. An optical mouse using the multi-plate one-dimensional block matching method of claim 25, wherein the plurality of calculation circuits includes a square error and calculation circuit. An optical mouse using the multi-plate one-dimensional block matching method of claim 25, wherein the plurality of calculation circuits includes an absolute value error and calculation circuit.