paper.dvi

Size: px

Start display at page:

Download "paper.dvi"

たかとしあると
5 years ago
Views:

1 SIFT 23 (410M5B1)

2 SIFT(Scale Invariant Feature Transform) SIFT SIFT SIFT SIMD SIFT SIMD MIMD Gaussian SIMD

3 Abstract Currently, with the development of image-recognition technique, to recognize a large number of objects everyday, has been developed by various research methods. However, such an environment to move against the actual camera itself, there is a problem that would have greatly diminished accuracy. It is difficult to recognize the impact of external environmental changes and the presence or absence of light and other lighting, even in the background of major changes in video camera. Therefore the recognition technique with quantity of SIFT characteristic is nominated for a masterpiece. However, dedicated hardware implementations of the high processing speed is obtained, there is a little exibility issue. Furthermore, the parallel computation system which is real-time processing correspondence and exibility is necessary. In this paper, I proposed a method to construct robust to withstand poor conditions, based on dedicated hardware configuration of the existing law. And I performed the basic design of highly parallel processors for general purpose image recognition that can be implemented in other process.

4 1 1 2 SIFT SIFT SIFT Difference-of-Gaussian SIFT SIMD 8 4 SIFT SIMD Systolic Algorithm SIFT PE SIMD Difference-of-Gaussian Gaussian i

5 SIFT SIFT Look up table PE Array ii

6 2.1 SIFT SIFT SIFT DoG SIMD TWIST TORUS PE Gaussian iii

7 iv

8 1 ITS ( ) SIFT(Scale Invariant Feature Transform) SIFT SIFT Intel Core2 Duo E x768p 7.28s SIFT SIFT SIFT SIMD 1

9 2 SIFT 2.1 SIFT SIFT Lowe (Scale-space peak description) (keypoint localization) (Orientation assognment) SIFT (keypoint descripotor) SIFT ( 2.4) 2.3 SIFT 2.2 SIFT SIFT detection (description) detection 1. Difference-of-Gaussian description

10 2.1: SIFT 2.2: SIFT 3

11 2.3: 4 2.4: SIFT

12 4 k 0 4 k 0 4 k 0 4 k 0 3 D( k 0 ) 2 D( k 0 ) 1 D( k 0 ) D( ) 0 0 DoG 2.5: DoG Difference-of-Gaussian Difference-of-Gaussian DOG DOG

2.6: 2.2.4 L(x, y) m(x, y) θ(x, y) m(u,v) = f u (u,v) 2 + f v (u,v) 2 (1) 1 f(u,v)

13 2.6: L(x, y) m(x, y) θ(x, y) m(u,v) = f u (u,v) 2 + f v (u,v) 2 (1) 1 f(u,v) θ(u,v) = tan f(u,v) (2) { fu (u,v) = L(u + 1,v) L(u 1) f v (u,v) = L(u + 1,v) L(u,v 1) (3) 6

14 : m θ 2.7 h θ = x w(x,y) δ[θ,θ(x,y)] (4) y w(u,v) = G(x,y,σ) m(x,y) (5) h θ 7

15 3 SIFT SIMD SIFT DoG SIMD 1024x gcov SIFT 64 8x8 SIMD SIMD SIMD 0 8

16 3.8: SIMD Function 1. Difference-of-Gaussian Gaussian 2. D 3. D

17 CU bas PE63 Reg PEM ADM : TWIST TORUS 4 SIFT SIMD DoG SIFT 4.1 ILLIAC IV SIMD (CU) 64 (PE) CU PE PE X8 ADM 4.11 PE 64 PEM 8 PE 10

18 DoG 64 8X8 8 8X x8 4.2 Systolic Algorithm SIFT 1. ( ) PE PE SystolicAlgorithm PE PE 3. DoG 3D SystolicAlgorithm PE 11

19 PE i j j x image 400 i 480 a-3 a-2 a-1 a a+1 a+2 a+3 a+4 addres y image 8 1x64 (8x8) : a a+1 a+2 a+3 a+4 a+5 a+6 a+7 8 m m+1 m+2 m+3 m+4 m+5 m+6 m+7 a a a a a a a a m+8 m+9 m+10 m+11 m+12 m+13 m+14 m+15 a+1 a+1 a+1 a+1 a+1 a+1 a+1 a+1 17 m+16 m+17 m+18 m+19 m+20 m+21 m+22 m+23 a+2 a+2 a+2 a+2 a+2 a+2 a+2 a+2 m+24 m+25 m+26 m+27 m+28 m+29 m+30 m+31 a+3 a+3 a+3 a+3 a+3 a+3 a+3 a+3 m+32 m+33 m+34 m+35 m+36 m+37 m+38 m+39 a+4 a+4 a+4 a+4 a+4 a+4 a+4 a+4 m+40 m+41 m+42 m+43 m+44 m+45 m+46 m+47 a+5 a+5 a+5 a+5 a+5 a+5 a+5 a+5 m+48 m+49 m+50 m+51 m+52 m+53 m+54 m+55 a+6 a+6 a+6 a+6 a+6 a+6 a+6 a+6 m+56 m+57 m+58 m+59 m+60 m+61 m+62 m+63 a+7 a+7 a+7 a+7 a+7 a+7 a+7 a+7 module address 4.11: 12

20 4.3 PE LUT θ ALU u v (8bit) θ PE LUT PE 4.4 PE LUT θ PE PE Adder Tree 13

21 CTRL Memory PE PE PE PE Column Tree Adder I/O Controller General Register Mux memory(lut) PE PE PE CU Mux Mux PE PE PE PE PE memory(lut) PE memory(lut) PE PE Column Tree Adder PE PE PE Column Tree Adder PE PE PE Column Tree Adder Row Tree Adder Row Shift Register Mux PE PE PE PE PE PE PE memory(lut) 5.12: SIMD PE SIMD 5.1 (CU) 64 (PE) SIMD PE Adder Tree PE ILLIAC IV Twisted Torus 64 8x8 PE LUT Adder Tree 14

22 PE (above) ALUSrc ALUSrc left PE M u x routing register M u x right PE MemWrite ALUSrc M u x Local Memory write data. write. data PE (dnow) MemRead register read data read data RegWrite broadcast offset ALUSrc M u x ALU ALU operation PE Adder Tree 5.13: PE 5.2 PE PE MIPS R ALU MUX PE broadcast PE 64 PE PE PE 8x8 PE Adder Tree 5.3 PE CPU I/F PE 15

23 6 SIMD MIMD 6.1 Difference-of-Gaussian Difference-of-Gaussian Gaussian Gaussian PE SMDmra t0, t1, t2 PE ( ) Gaussian 7x7( 1.3 ) 64 Gaussian Gaussian DOG PE Gaussian 64 x2 ALU DoG PE 6.2 PE DoG DOG SMDslgt PE 16

24 ORS PE OR OR OR ALL PE ANDS PE AND AND AND ALL PE SIMD SIFT cdpe PE 7 MIMD SIFT SIFT SIMD 17

7.14: Gaussian 7.1 Gaussian Gaussian Gaussian 7.14 7x7 ( 1.3 ) 7.

25 7.14: Gaussian 7.1 Gaussian Gaussian Gaussian x7 ( 1.3 ) Gaussian 70 SMDmra 5 E1 ld E2 mul E3 ac PE ( ) E4 :rou PE 18

26 7.15: E1 SMDslgt PE E2 ORS PE OR E3 ANDS PE AND 7.3 SIFT lw t0, 0(s2); t0 19

27 lw t1, 4(s3); t1 sll t2, t1,8; or t0, t1,t2; OR sw t0, 0(s1); cdpe (capture data to PE) PE PE LUT PE 64PE 7.4 X sltiu,rs,rt,immediate immediate rt rt immediate rs addi t2, s1, 0; sltiu t2, t2, 1; sw t2, 100(s0); addi t2, s1, 0; sltiu t2,t2, 36; sw t2, 100(s0); add t0, t2, t

28 step : Gaussian SIMD Gaussian Systolic Algorithm no pipeline : 196= 4 x 7 x 7 This Work : 70 = 10x7 21

29 7.17: Systolic Algorithm no pipeline : 78= 3 x 26 This Work : 26 ( ) Systolic Algorithm no Systolic Algorithm : 881 = x 36 x This Work : 125 = x (8PE + LUT + AdderTree = 64PE Systolic Array) 22

30 8 8.1 SIFT SIFT book.pgm book.key book.key./sift < book.pgm > book.key Finding keypoints keypoints found../sift < desk2.pgm > desk2.key Finding keypoints keypoints found. book.key 1 X, Y,, /* 1 */ /* 2 */

31 book.key desk2.key./match -im1 book.pgm -k1 book.key -im2 desk2.pgm -k2 Found 413 matches. sk2.key >out3.pgm book desk2 out3.pgm Look up table look-up table LUT Look up Table LUT ( ) LUT 24

32 8.3 PE Array PE PE PE PE PE NXN PE 25

33 9 SIFT SIFT SIMD SIFT 26

34 27

35 [1] SIFT HOG PCSJ/IMPS2008 [2],, SIMD, D-II, Vol.J86-D-II, No.11, pp (2003) [3],,, IMAPCAR,NEC Vol.60 No.2/ [4] Bonato, V. / Marques, E. / Constantinides, G A. A Parallel Hardwar Architecture for Scale and Rotation Invariant Feature Detection IEEE transactions on circuits and systems for video technology. - Vol. 1, no. 1 (Mar. 1991)-. - New York, N.Y. : Institute of Electrical and Electronics Engineers, c [5] Yoichi MURAOKA The Configuration of Main Memory for Illiac IV Information Processing Society of Japan Vol.16 No.4 28

17 Proposal of an Algorithm of Image Extraction and Research on Improvement of a Man-machine Interface of Food Intake Measuring System

1. (1) ( MMI ) 2. 3. MMI Personal Computer(PC) MMI PC 1 1 2 (%) (%) 100.0 95.2 100.0 80.1 2 % 31.3% 2 PC (3 ) (2) MMI 2 ( ),,,, 49,,p531-532,2005 ( ),,,,,2005,p66-p67,2005 17 Proposal of an Algorithm of