||Motion Vector Estimation based on RFID Localization and Video Sequence
||Department of Electrical Engineering
對於人類行為分析，移動向量(motion vector)扮演著舉足輕重的角色。一般來說，透過視訊影像分析所得的移動向量是一種短程動量(short-term motion)，其有助於局部的人類行為分析。然而，諸如動線追蹤等人類行為分析必需取得廣範圍移動的長程動量(long-term motion)。基於此考量，本論文利用RFID裝置來取得長程動量；而使用視訊分析來取得短程動量。
本論文以RFID之定位演算法來偵測長程動量並研究提昇RFID訊號的可靠性。在RFID定位環境中配置定位器(Field Generator)及讀取器(Reader)，而移動物件則攜帶標籤(Tag)。RFID系統運作方式是以定位器發出RF訊號，當標籤進入定位器RF訊號範圍時，標籤將被寫入定位器編號並由標籤將定位器編號與標籤編號以RF訊號傳送給讀取器。根據RFID運作方式，本論文提出動態調整訊號範圍定位(dynamic range adjustment localization, DRAL)演算法來定位攜帶標籤的移動物件，以取得長程動量供後續分析之用。在DRAL演算法中使用參照標籤(Reference Tag)動態來取得環境因素對訊號傳輸範圍的影響，以提昇定位的準確度。另一方面，為了解決兩定位器訊號交錯區中訊號因碰撞問題而不穩定的情況，本論文也提出頂點合併與刪除之圖形著色(graph coloring with merging and deletion, GCMD)排程演算法。GCMD排程演算法將訊號碰撞問題圖形化，透過圖形簡化與圖形著色理論來規劃最佳定位器訊號傳送排程以降低定位器訊號的碰撞對系統穩定性的影響。
人類行為分析中所需要的短程動量是視訊影像中物件真實的移動向量而不是一般應用於視訊影像壓縮之移動向量所重視的視覺最佳化。因此若直接使用視訊影像壓縮中移動向量來當人類行為分析的特徵，將使得人類行為分析結果不如預期理想。基於此考量，本論文提出了以區域基礎選擇光學流動倒投影(region-based selective optical flow back-projection, RSOFB)技術來求取更為真實的影像移動向量，以利後續人類行為分析之用。RSOFB演算法是將一區域中各個方向的光學流動(optical flow) 倒投影出該區域的移動向量。倒投影的方式為挑選受較不受雜訊干擾的光學流動當成區域移動向量各方向的分量，並最小化移動向量在各個方向分量大小與該方向光學流動大小的誤差來達成。
Motion plays one significant feature in human behavior analysis. Generally speaking the motion vector estimated by video sequence is a short-term motion that facilitated local human behavior analysis. However, some human behavior analysis need long-term motion, that is a wide range motion, such as route tracking. Based on this consideration, this dissertation used RFID device for estimating long-term motion and used video analysis for estimating short-term motion.
This dissertation presents an RFID based tracking algorithm with reliability improvement for long-term motion estimation. In this algorithm, RFID Field Generators and Readers are installed in the environment, near the entrance and exit points, for tracking the moving object. Every moving object carries a tag. The Field Generator constantly transmits trigger signal to any tag within its transmission range. When a tag receives the trigger from a Field Generator, it responds to a Reader with the ID of the Field Generator issuing the trigger. Based on the Field Generator IDs a tag responds, we proposed the dynamic range adjustment localization (DRAL) algorithm that estimates the location of the moving object associated with the tag. However by so doing, it is necessary to have significant dense of Field Generators to obtain significantly accurate location. In this algorithm, reference tags are used as reference basis for increasing the localization accuracy. On the other hand, in order to resolve interferences from different Field Generators, this dissertation also proposed a graph coloring with merging and deletion (GCMD) algorithm in RFID system for solving the interference caused from Field Generators located one near another.
The short-term motion in human behavior analysis is required to represent the actual motion displacement, rather than regions of visually significant similarity. In this dissertation, region-based selective optical flow back-projection (RSOFB) which back-projects optical flows in a region to restore the region’s motion vector from gradient-based optical flows, is proposed to obtain genuine motion displacement. The back-projection is performed based on minimizing the projection mean square errors of the motion vector on gradient directions. As optical flows of various magnitudes and directions provide various degrees of reliability in the genuine motion restoration, the optical flows to be used in the RSOFB are optimally selected based on their sensitivity to noises and their tendency in causing motion estimation errors. In this dissertation a deterministic solution is also derived for performing the minimization and obtaining the genuine motion magnitude and motion direction.
摘 要 VI
Chapter 1. Introduction 1
1.1 Scope of the Work 1
1.2 RFID-based Long-term Motion Estimation 1
1.2.1 RFID Reliability Improvement 2
1.2.2 RFID Localization 3
1.3 Vision-based Short-term Motion Estimation 5
Chapter 2. RFID Reliability Improvement 9
2.1 System overview 9
2.2 Reliability improvement with field generator scheduling 10
2.2.1 Transform the relationships among all Field Generators into a graph 12
2.2.2 Vertex Deletion and Merging 12
2.2.3 Vertex Coloring 14
2.2.4 Operation Slot Allocation 14
2.3 GCMD Algorithm Evaluation 14
2.3.1 Fixed-points test 18
2.3.2 Route test 22
Chapter 3. RFID Localization 27
3.1 Introduction of Extant RFID Localization Methods 27
3.2 Moving Object Location Estimation 29
3.2.1 The distance between the Target Tag and Field Generator estimation 29
3.2.2 The location of the Target Tag computation 32
3.3 DRAL Algorithm Evaluation 33
Chapter 4. Motion Estimation Algorithms 45
4.1 Motion Vector Estimation with Selective Optical Flows Back-projection 45
4.1.1 Horn-Schunck optical flow constraint 45
4.1.2 Optical Flows Back-projection 46
4.1.3 Selective Optical Flows 48
4.2 Adaptive Region Determination 50
4.3 Adaptive Optical Flow Restoration 51
4.4 RSOFB Algorithm Evaluation 53
Chapter 5. Case Study - Fall Detection 65
5.1 Introduction 65
5.2 Algorithm Overview 66
5.3 Feature Extraction 67
5.3.1 Extraction of Moving Object and its Feature Points 68
5.3.2 Block-based Optical Flow Back-projection 70
5.4 Motion Vectors Analysis and Fall Detection 73
5.5 Experimental Results 75
Chapter 6. Conclusions 82
List of Publications 90
 A.E. Oirrak, M. Daoudi and D. Aboutajdine, "Estimation of general 2D affine motion
using Fourier descriptors, " Pattern Recognition, vol. 35, pp. 223-228, 2002.
 A. Harter, A. Hopper, P. Steggles, A. Ward and P. Webster, "The anatomy of a
context-aware application, " Proceedings of the 5th Annual ACM/IEEE International
Conference on Mobile Computing and Networking, pp. 59–68, 1999.
 A. Singh, "Optical Flow Computation: A Unified Perspective, " IEEE Comput. Soc.
Press, Los Alamitos, CA, 1992.
 A. Sixsmith and N. Johnson, "A Smart Sensor to Detect the Falls of the Elderly, " IEEE
pervasive computing, vol. 3, no. 2, pp. 42-47, 2004.
 A. S. Tanenbaum, Computer Networks, 4th Edition, Prentice Hall PTR, New Jersey,
pp. 251-255, 2003.
 B. G. Schunck, "Motion segmentation and estimation by constraint line clustering,"
Proc. Workshop Compute Vision, pp. 58- 62, 1984.
 B. G. Schunck, "Image flow segmentation and estimation by constraint line clustering,
" IEEE Trans. Pattern Analysis and Machine Intelligence, pp.1010 – 1027, 1989.
 B.K.P. Horn and B. Schunk, "Determining Optical Flow, " Artificial Intelligence,
vol.17, no.1, pp. 185-203, 1981.
 B. Lucas and T. Kanade, "Performance of Optical Flow Techniques, " Proc. DARPA IU
Workshop, pp.121-130, 1981.
 B. Zhen, M. Kobayashi and M. Shimizu, "To read transmitter- only RFID tags with
confidence, " 15th IEEE International Symposium on Personal, Indoor and Mobile
Radio Communications, vol. 1, pp. 396-400, 2004.
 C.L. Huang, E.L. Chen, P.C. Chung and Y.R. Choo, "Adaptive Hierarchical Cluster
Matching for Motion Vector Estimation, " Proceedings of Workshop on Consumer
Electronics, pp.198-203, 2002.
 C.L. Huang, E.L. Chen, P.C. Chung and Y.R. Choo, "Optical Flow Back-Projection for
Genuine Motion Vector Estimation, " IEEE International Conference on Multimedia
and Expo, pp. 523-526, 2004.
 C. Zhu, X. Lin, L. Chau and L.M. Po, "Enhanced Hexagonal Search for Fast Block
Motion Estimation, " IEEE Trans. Circuits Syst. Video Technol, vol. 14, pp.
1210-1214, 2004. D. H. Shih, P. L. Sun, D. C. Yen and S. M. Huang, "Taxonomy and survey of RFID
anti-collision protocols, " Computer communications, vol. 29, pp. 2150-2166, 2006.
 D.P. Kottke and Y. Sun, "Motion Estimation Via Cluster Matching, " IEEE Trans.
Pattern Analysis and Machine Intelligence, vol. 16, 1994, pp. 1128 – 1132, 1994.
 F. Wu, F. Kuo and L.W. Liu, "The application of RFID on drug safety of inpatient
nursing healthcare, " ACM 7th International Conference on Electronic Commerce, vol.
113, pp. 85-92, 2005.
 G. Bebis, M. Georgiopoulos, N. Lobo and M. Shah, "Learning Affine Transformations
of the Plane for Model-Based Object Recognition, " Proceeding of the 13th
International Conference on Pattern Recognition, vol. 4, pp.60-64, 1996
 G. Y. Jin, X. Y. Lu and M. S. Park, "An Indoor Localization Mechanism Using Active
RFID Tag " IEEE International Conference on Sensor Networks, Ubiquitous, and
Trustworthy Computing, 2006. Vol. 1, 05-07 June 2006, Page(s):40 – 43
 H. D. Chon, S. Jun, H. Jung, and S. W. An, “Using RFID for Accurate Positioning”
Journal of Global Positioning Systems, vol. 3, no. 1-2, pp.32-39, 2004.
 H. H. Nagel, "On the Estimation of Optical Flow: Relation between different
approaches, " Artificial Intelligence, vol.33, pp. 299-324, 1987.
 H. Nait-Charif and McKenna SJ, "Activity summarisation and fall detection in a
supportive home environment, " Proc. of the 17th Int. Conf. on Pattern Recognition,
vol. 4: , pp. 323-326, 2004.
 H. Stockman, "Communication by Means of Reflected Power, " Proceedings of the
IRE, pp. 1196-1204, 1948.
 H. Vogt, "Multiple object identification with passive RFID tags, " IEEE International
Conference on Systems, Man and Cybernetics, vol. 3, 2002.
 J. Gibson, The Mobile Communications Handbook IEEE Press 1999.
 J. Kim and J.W. Woods, "3D Kalman Filter for Image Motion Estimation, " IEEE
Trans. Image Processing, vol. 7, pp. 42-52, 1998.
 J. L. Barron, D. J. Fleet and S. S. Beauchemin, "Performance of Optical Flow
Techniques, " Technical Report RPL-TR-9107, Univ. of Western Ontario, 1993.
 J. Siden, P. Jonsson, T. Olsson and G. Wang, "Performance degradation of RFID
system due to the distortion in RFID tag antenna, " 11th International Conference on
Microwave and Telecommunication Technology, pp. 371-373, 2001. J. Tao, M. Turjo, M.F. Wong, M. Wang and Y.P. Tan, "Fall Incidents Detection for
Intelligent Video Surveillance, " Proc. of the 15th Int. Conf. on Communications and
Signal Processing, pp. 1590-1594, 2005.
 J. Waldrop, D.W. Engels and S.E. Sarma, "Colorwave : an anticollision algorithm for
the reader collision problem, " IEEE International Conference on Communications,
vol. 2, pp. 1206-1210, 2003.
 J.Y. LU, K.S. WU and J.C. LIN, "Fast full search in motion estimation by hierarchical
use of Minkowski’s inequality (HUMI), " Pattern Recognition, vol. 31, pp. 945-952,
 K. Michael and L. McCathie, "The Pros and Cons of RFID in Supply Chain
Management, " International Conference on Mobile Business, pp. 623–629, 2005.
 K.P. Unnikrishnan, J.J. Hopfield and D.W. Tank, "Connected-digit speaker-dependent
speech recognition using a neural network with timedelayed connections, " IEEE
Trans. Signal Processing, vol. 39: , pp. 698-713, 1991.
 L. M. Ni, Y. Liu, Y. C. Lau and A.P. Patil, "LANDMARC: indoor location sensing
using active RFID", Proceedings of the First IEEE International Conference
Pervasive Computing and Communications, pp.407 - 415, 2003.
 M.H. Tsai, C.L. Huang, P.C. Chung, Y.K. Yang, Y.C. Hsu and S.L. Hsiao, "A
Psychiatric Patients Tracking System, " IEEE International Symposium on Circuit &
 M. J. Black and P. Anandan, "The robust estimation of multiple motions: Parametric
and piecewise-smooth flow fields, " Computer Vision and Image Understanding,
CVIU, vol.63, no.1, pp. 75-104, 1996.
 M.J. Chen, L.G. Chen and T.D. Chiueh, "One-Dimensional Full Search Motion
Estimation Algorithm For Video Coding, " IEEE Trans. Circuits Syst. Video Technol,
vol. 4 , pp. 504-509, 1994.
 M. Ye, R.M. Haralick and L.G. Shapiro, "Estimating piecewise-smooth optical flow
with global matching and graduated optimization, " IEEE Trans. Pattern Analysis and
Machine Intelligence, vol. 25, pp. 1625 – 1630, 2003.
 N.B. Priyantha, A. Chakraborty and H. Balakrishnan, "The Cricket location-support
system, " Proceedings of MOBICOM 2000, pp. 32–43, 2000.
 P. Anandan, "A computational framework and an algorithm for the measurement of
visual motion, " Int. J. Compute Vision, vol. 2, pp. 283-310, 1989. P.C. Chung, E.L. Chen and J.B. Wu, "A spatiotemporal neural network for recognizing
partially occluded objects, " IEEE Trans. Signal Processing, vol. 46, pp. 1991-2000,
 P.C. Chung, C.L. Huang and E.L. Chen, "A Region-based Selective Optical Flow
Back-Projection for Genuine Motion Vector Estimation, " Pattern Recognition, vol. 40,
pp. 1066-1077, 2007.
 P.L. Tai, S.Y. Huang, C.T. Liu and J.S. Wang, "Computation-aware scheme for
software-based block motion estimation, " IEEE Trans. Circuits Syst. Video Technol,
vol. 13, pp. 901-913, 2003.
 P. Moulin, R. Krishnamurthy and J.W. Woods, "Multiscale Modeling and Estimation
of Motion Fields for Video Coding, " IEEE Trans. Image Processing, vol. 6, pp.
 P.R. Foster and R.A. Burberry, "Antenna problems in RFID systems, " IEE
Colloquium on RFID Technology, pp. 3/1-3/5, 1999.
 R. Battiti, "First- and second-order methods for learning: Between steepest descent and
Newton's method, " Neural Computation, vol. 4, no.2, pp. 141-166, 1992.
 R. Krishnamurthy, P. Moulin and J.W. Woods, "Optical Flow Techniques Applied to
Video Coding, " Proceeding of IEEE Conference on Image Processing, pp.570-573,
 R. Li, B. Zeng and M.L. Liou, "A New Three-Step Search Algorithm for Block Motion
Estimation, " IEEE Trans. Circuits Syst. Video Technol, vol. 4 , pp. 438-442, 1994.
 R. Manmatha and J. Oliensis, "Extracting affine deformations from image patches. I.
Finding scale and rotation, " Proceeding of IEEE Conference on Computer Vision and
Pattern Recognition, pp. 754-755, 1993.
 R. Want, A. Hopper, V. Falcao and J. Gibbons, " The active badge location system, "
ACM Transactions on Information Systems, vol.10, no.1, pp.91–102, 1992.
 S. Uras, F. Girosi, A. Verri and V. Torre, "A computational approach to motion
perception, " Biol. Cybernet, vol. 60, pp. 79-97, 1989.
 T. Meier and K.N. Ngan, "Automatic Segmentation of Moving Objects for Video
Object Plane Generation, " IEEE Trans. Circuits Syst. Video Technol, vol. 8, pp.
 T. Papadimitriou, K.I. Diamantaras, M.G. Strintzis and M. Roumeliotis, "Video Scene
Segmentation using Spatial Contours and 3-D Robust Motion Estimation, " IEEETrans. on Circuits and Syst.Video Technol, vol. 14, no. 4 , pp. 485 - 497, 2004.
 T.S. Rappaport, “Wireless Communications: Principles and Practice”, 2nd Edition,
Prentice Hall PTR, 2002.
 V. Kulyukin, C. Gharpure, J. Nicholson and S. Pavithran, “RFID in robot-assisted
indoor navigation for the visually impaired” Proceedings of IEEE International
Conference on Intelligent Robots and Systems, vol. 2, pp. 1979- 1984, 2004.
 Wireless Integrated Network Systems(WINS) http://wins.rsc.rockwell.com/
 W. Foy, “Position-Location Solution by Taylor Series Estimation” IEEE Transactions
of Aerospace and Electronic Systems vol. AES-12, no.2, pp. 187-193, 1976.
 X. Zhou and G. Wang, "Study on the influence of curving of tag antennas on
performance of RFID system, " 4th International Conference on Microwave and
Millimeter Wave Technology, pp. 122-125, 2004.
 Y. Altunbasak, R.M. Mersereau and A.J. Patti, "A fast parametric motion estimation
algorithm with illumination and lens distortion correction, " IEEE Trans. Image
Processing, vol. 12, pp. 395-408, 2003.
 Y. Fukumizu, M. Nagata, S. Ohno and K. Taki, "A design of transponder IC for highly
collision resistive RFID systems, " IEEE Asia-Pacific Conference on Advanced System
Integrated Circuits, pp. 438-439, 2004.
 Y.W. Chen and C.J. Lin, "Combining SVMs with various feature selection strategies, "
in the book: Feature extraction, foundations and applications. Guyon I, Gunn S,
Nikravesh M and Zadeh L, Springer-Verlag, Chap. 12, 2006.