臺灣博碩士論文加值系統

多重相機網路的一大特色是資料量龐大，並且有低傳輸延遲的需求。因此，不同於傳統網路下考慮如何最大化個別相機的傳輸效能，我們以如何能更有效的提升頻譜使用效率作為出發點，試圖在不影響影像蒐集品質的前提下，最小化實際所需傳輸的資料量。基於鄰近相機之間所拍攝到的影像可能會有所重疊，我們引入了多視角視訊編碼技術(Multiview video coding)，使得個別相機能夠透過重疊影像之相關性以降低影像編碼時所需的資料量。在本篇論文中，我們提出了一個利用側聽編碼來去除不同相機所攝影像間相關資料的技術，此一技術的優點是相機不需要在傳輸前彼此交換資訊，也因此並不會造成頻譜的額外負擔。對於此類問題，過去的相關文獻常以相機間的幾何資訊做為估計網路相關性的依據，然而此種方式時常會因估計的誤差而損失側聽編碼的效能。因此，為了使側聽編碼的效能最大化，我們藉由實際的移動向量估計方式來計算相機間的相關性，並且提出了一個綜合考量相機參考圖像的最佳化問題，最後在不損失最佳化特性的前提下將此問題拆解成「I-圖像相機選擇」以及「P-圖像相機參考圖像決定」的這兩個問題，使得P-圖像能夠選擇與其相關性最大的I-圖像作為移動向量估計時之參考圖像。我們接著提出了三種演算法來解決I-圖像相機選擇的問題，其一是藉由分支界定法(Branch-and-bound)以得到此問題的最佳解，其二是利用模擬退火法(Simulated annealing)來求得一近似最佳值的解，最後則是透過圖學近似的方式來更有效率的選擇I-圖像相機。此外，在實際多重相機網路的應用當中，相機間的相關性會隨著不同時間點拍攝到的影像而有所變化。因此我們也提出了一個觸發I-圖像重新選擇的機制，使得整體的網路能夠在不增加太多計算複雜度的前提下，得以迎合不同時間點之相關性變化。透過3D建模軟體當中虛擬城市所拍攝到的影像以及電腦模擬結果的分析，我們比較了三種演算法的時間複雜度，以及在相機相關性改變時之效能差異。我們發現在資料相關性高時，圖學近似的方式可以得到一接近最佳值的解，而若是針對資料相關性較低的網路，模擬退火法則比較適用。此外，模擬結果也顯示我們提出的側聽編碼技術約能減少35%的資料傳輸量，而使用相機幾何資訊估計相關性的做法只能達到15%的減少量，因此確立了此種做法確實為一可能運用在缺乏頻譜資源時的多重相機網路下之資料蒐集技術。

In this thesis, we investigate the problem of correlated data gathering in the wireless multi-camera networks by considering the I-frame selection problem and the P-frame association problem. Since multiple cameras may be deployed in a neighborhood area with overlapping perspectives of the street views, we exploit the capability of transmission overhearing among cameras. If a camera can overhear transmissions from previous scheduled nearby cameras, it can reference the image and reduce the amount of bits required to be delivered to the aggregator by performing the multiview encoding technique. Unlike related works often use geometric information to predict correlation among cameras, we refer to the multiview video encoder for measuring realistic cameras correlation such that no performance loss will be caused due to prediction error. We further propose three I-frame selection algorithms based on branch-and-bound, simulated annealing, and graph approximation. We also introduce a P-frame association method to determine reference structure for all cameras such that the amount of required transmission bits can be minimized. Besides, for real-world applications, it might require multiple transmission rounds for delivering the collected images back to the data aggregator. Therefore, in this thesis, we also describe how to apply the correlated data gathering scheme via overhearing source coding for more than one transmission rounds. To evaluate the proposed algorithms, we resort to a 3D modeling software to generate quasi-realistic city views for all cameras and use a H.264 multiview video encoding reference software to encode collected images. Based on the evaluation for a semi-realistic multi-camera network, we compare the performance gain of our three proposed algorithms with a baseline approaches and point out the trade-off among the three proposed methods. That is, the graph approximation algorithm can perform well when the network is high correlated, whereas the simulated annealing algorithm might be a better choice if the network correlation level becomes low. We also show that our proposed approaches can result in 35% transmission reduction for high correlated multi-camera networks, however, only 15% can be reduced if geometric correlation is applied. The results thus motivate further investigation along this direction.

ACKNOWLEDGEMENTS ......................... i
ABSTRACT(CHINESE) .......................... ii
ABSTRACT .................................. iii
LISTOFTABLES ..............................viii
LISTOFFIGURES ............................. ix
CHAPTER1 INTRODUCTION .................... 1
CHAPTER 2 BACKGROUND AND RELATED WORK . . . . . 4
2.1 Background .............................. 4
2.1.1 H.264VideoCompressionTechnique. . . . . . . . . . . . . 4
2.1.2 InterPredictioninH.264 ................... 6
2.1.3 MultiviewVideoCoding ................... 7
2.2 RelatedWork ............................. 9
2.2.1 VisualCorrelationModel................... 10
2.2.2 EfficientVideoEncoding ................... 10
2.2.3 EfficientVideoDelivery.................... 12
CHAPTER 3 NETWORK SCENARIO AND CAMERA MODEL 14
3.1 Data-CentricClustering........................ 14
3.2 NetworkScenario ........................... 16
3.3 CameraModel............................. 17
3.3.1 CameraSensingModel .................... 17
3.3.2 CameraCorrelationModel .................. 19
CHAPTER 4 CORRELATED DATA GATHERING UNDER OVER- HEARINGSOURCECODING.................... 21
4.1 ProblemFormulation ......................... 22
4.2 ProblemDecomposition........................ 25
4.2.1 Decomposed I-Frame Selection Sub-Problem . . . . . . . . 27
4.2.2 Decomposed P-Frame Association Sub-Problem . . . . . . 28
CHAPTER 5 PROPOSED ALGORITHMS FOR I-FRAME SE-
LECTIONSUB-PROBLEM ...................... 30
5.1 AnalysisofI-FrameSelectionSub-Problem . . . . . . . . . . . . . 30
5.2 Branch-and-Bound I-Frame Selection Algorithm . . . . . . . . . . 32
5.2.1 BoundingPolicy........................ 33
5.2.2 BranchingPolicy........................ 37
5.2.3 OverallAlgorithm....................... 38
5.3 Simulated Annealing I-Frame Selection Algorithm . . . . . . . . . 38
5.3.1 NeighborhoodOperators ................... 41
5.3.2 NonuniformNeighborGeneration . . . . . . . . . . . . . . 42
5.3.3 OverallAlgorithm....................... 42
5.4 Graph Approximation for I-Frame Selection Sub-Problem . . . . . 43
5.4.1 MinimumWeightedDominatingSet . . . . . . . . . . . . . 43
5.4.2 Proposed Cameras Grouping Algorithm . . . . . . . . . . . 45
5.4.3 Analysis of Graph Approximation Algorithm . . . . . . . . 46
CHAPTER 6 CENTRALIZED CORRELATED VIDEO GATH- ERING FOR WIRELESS MULTI-CAMERA NETWORKS . . 50
6.1 Correlated Video Gathering for Multi-Camera Networks . . . . . . 50
6.2 OverallSystemArchitecture ..................... 52
6.2.1 CorrelationEstimation(CE)Phase . . . . . . . . . . . . . 53
6.2.2 TransmissionScheduling(TS)Phase. . . . . . . . . . . . . 53
6.2.3 DataTransmissionPhase................... 54
6.2.4 ProposedReestimationCriteria ............... 55
CHAPTER7 PERFORMANCEEVALUATION . . . . . . . . . . 58
7.1 Evaluation of Proposed Branch-and-Bound Algorithm . . . . . . . 60
7.1.1 Evaluation of Different Branching Methods . . . . . . . . . 61
7.1.2 Evaluation of Different Lower Bound Estimation Techniques 61
7.2 Evaluation of Proposed Simulated Annealing Algorithm . . . . . . 65
7.3 Evaluation of Proposed Graph Approximation Algorithm . . . . . 65
7.4 ComparisonofProposedAlgorithms................. 69
7.5 Evaluation of Multiple Transmission Rounds . . . . . . . . . . . . 75
7.6 EvaluationofReceivedVideoQuality ................ 80
CHAPTER 8 CONCLUSION AND FUTURE WORK . . . . . . 82
REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

[1] A. Couturier, Suicidator City Generator - Create 3D cities. [Online]. Available: http://cgchan.com/suicidator
[2] Blender Online Community, Blender - a 3D modelling and rendering package, Blender Foundation, Blender Institute, Amsterdam. [Online]. Available: http://www.blender.org
[3] Kapsch TrafficCom. [Online]. Available: http://www.kapsch.net/en/ktc/
[4] Traficon. [Online]. Available: http://www.traficon.com
[5] Citilog. [Online]. Available: http://www.citilog.com
[6] I. E. Richardson, The H.264 Advanced Video Compression Standard, 2nd ed. Wiley Publishing, 2010.
[7] ITU-T Recommendation H.264 Series H: AUDIOVISUAL AND MULTIME- DIA SYSTEMS Infrastructure of audiovisual services - Coding of moving video, ITU-T Rec. H.264 | ISO/IEC 14496, Mar 2010, E 35628.
[8] A. Smolic, “Overview of multiview video coding (MVC),” ISO/IEC JTC1/SC29/WG11, Tech. Rep., January 2008, doc. N9580.
[9] H. Schwarz, D. Marpe, and W. T, “Analysis of hierarchical B pictures and MCTF,” in IEEE International Conference on Multimedia and Expo, July 2006, pp. 1929–1932.
[10] J.-R. Ohm and G. Sullivan, “MPEG-4 advanced video coding,” ISO/IEC 14496, Tech. Rep., July 2005, doc. N7314.
[11] Y. Charfi, N. Wakamiya, and M. Murata, “Challenging issues in visual sensor networks,” IEEE Wireless Communications, vol. 16, no. 2, pp. 44–49, April 2009.
[12] G. L. Foresti, P. Mahonen, and C. S. Regazzoni, Multimedia video-based surveillance systems: Requirements, Issues and Solutions. Springer Science & Business Media, 2012, vol. 573.
[13] H. Aghajan and A. Cavallaro, Multi-camera networks: principles and appli- cations. Academic press, 2009.
[14] J. O. Berger, V. D. Oliveira, and B. Sanso, “Objective bayesian analysis of spatially correlated data,” Journal of the American statistical association, vol. 96, pp. 1361–1374, 2000.
[15] R. Dai and I. F. Akyildiz, “A spatial correlation model for visual information in wireless multimedia sensor networks,” IEEE Transactions on Multimedia, vol. 11, no. 6, pp. 1148–1159, Oct 2009.
[16] S. Colonnese, F. Cuomo, and T. Melodia, “An empirical model of multiview video coding efficiency for wireless multimedia sensor networks,” IEEE Trans- actions on Multimedia, vol. 15, no. 8, pp. 1800–1814, Dec 2013.
[17] D. Slepian and J. K. Wolf, “Noiseless coding of correlated information sources,” IEEE Transactions on Information Theory, vol. 19, no. 4, pp. 471– 480, Jul 1973.
[18] A. Wyner and J. Ziv, “The rate-distortion function for source coding with side information at the decoder,” IEEE Transactions on Information Theory, vol. 22, no. 1, pp. 1–10, Jan 1976.
[19] B. Girod, A. M. Aaron, S. Rane, and D. Rebollo-Monedero, “Distributed video coding,” Proceedings of the IEEE, vol. 93, no. 1, pp. 71–83, Jan 2005.
[20] P. Ferre, D. Agrafiotis, and D. Bull, “Fusion methods for side information generation in multi-view distributed video coding systems,” in Proceedings of IEEE International Conference on Image Processing, vol. 6, Sept 2007, pp. 409–412.
[21] C.-H. Wu and Y.-C. Tseng, “Data compression by temporal and spatial corre- lations in a body-area sensor network: A case study in pilates motion recog- nition,” IEEE Transactions on Mobile Computing, vol. 10, no. 10, pp. 1459– 1472, Oct 2011.
[22] ——, “Exploiting multi-spatial correlations of motion data in a body sensor network,” IEEE Communications Letters, vol. 16, no. 5, pp. 662–665, May 2012.
[23] Y. Kim and G. de Veciana, “Is rate adaptation beneficial for inter-session network coding?” in IEEE Military Communications Conference (MILCOM), Nov 2008, pp. 1–7.
[24] P. Wang, R. Dai, and I. F. Akyildiz, “Visual correlation-based image gathering for wireless multimedia sensor networks,” in Proceedings of IEEE INFOCOM, March 2011, pp. 2489–2497.
[25] D. Bandari, P. Frossard, and G. Pottie, “An adaptive cross layer resource allocation scheme for correlated wireless video sources,” in Wireless Commu- nications and Networking Conference (WCNC), March 2011, pp. 2065–2072.
[26] E. Kurutepe and T. Sikora, “Multi-view video streaming over P2P networks with low start-up delay,” in 15th IEEE International Conference on Image Processing, Oct 2008, pp. 3088–3091.
[27] E. Kurutepe, M. R. Civanlar, and A. M. Tekalp, “Client-driven selective streaming of multiview video for interactive 3DT
V,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 17, no. 11, pp. 1558–1565, Nov 2007.
[28] Y. Pritch, S. Ratovitch, A. Hendel, and S. Peleg, “Clustered synopsis of surveillance video,” in Proceedings of IEEE International Conference on Ad- vanced Video and Signal Based Surveillance, Sept 2009, pp. 195–200.
[29] L. Tessens, M. Morbee, H. Lee, W. Philips, and H. Aghajan, “Principal view determination for camera selection in distributed smart camera networks,” in Proceedings of ACM/IEEE International Conference on Distributed Smart Cameras, Sept 2008, pp. 1–10.
[30] L. Toni, T. Maugey, and P. Frossard, “Correlation-aware packet scheduling in multi-camera networks,” IEEE Transactions on Multimedia, vol. 16, no. 2, pp. 496–509, Feb 2014.
[31] S. Basagni, “Distributed clustering for ad hoc networks,” in Fourth Interna- tional Symposium on Parallel Architectures, Algorithms, and Networks, 1999, pp. 310–315.
[32] F. Zou, Y. Wang, X.-H. Xu, X. Li, H. Du, P. Wan, and W. Wu, “New ap- proximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs,” Theoretical Computer Sci- ence, vol. 412, no. 3, pp. 198 – 208, 2011.
[33] T.-C. Juan, S.-E. Wei, and H.-Y. Hsieh, “Data-centric clustering for data gathering in machine-to-machine wireless networks,” in IEEE International Conference on Communications Workshops (ICC), June 2013, pp. 89–94.
[34] Y.-D. Tsai, C.-Y. Song, and H.-Y. Hsieh, “Joint optimization of clustering and scheduling for machine-to-machine communications in cellular wireless networks,” in IEEE 81st Vehicular Technology Conference (VTC Spring), May 2015, pp. 1–5.
[35] R. Szeliski, Computer vision: algorithms and applications. Springer Science & Business Media, 2010.
[36] O. Faugeras, Three-dimensional Computer Vision: A Geometric Viewpoint. Cambridge, MA, USA: MIT Press, 1993.
[37] A. Goldsmith and S.-G. Chua, “Variable-rate variable-power MQAM for fad- ing channels,” IEEE Transactions on Communications, vol. 45, no. 10, pp. 1218–1230, Oct 1997.
[38] R. Hemmecke, M. Koppe, J. Lee, and R. Weismantel, “Nonlinear Integer Programming,” 2009, arXiv:0906.5171v1.
[39] R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, ser. The IBM Research Symposia Series. Springer US, 1972, pp. 85–103.
[40] B. Yelbay, S. I. Birbil, and K. Bulbul, “The set covering problem revisited: An empirical study of the value of dual information,” Journal of Industrial and Management Optimization, April 2014.
[41] M. T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, 2nd ed. New York, NY, USA: John Wiley & Sons, Inc., 2009.
[42] E. L. Lawler and D. E. Wood, “Branch-and-bound methods: A survey,” Op-
erations Research, vol. 14, no. 4, pp. 699–719, 1966.
[43] F. Romeo and A. Sangiovanni-Vincentelli, “A theoretical framework for sim-
ulated annealing,” Algorithmica, vol. 6, no. 1-6, pp. 302–345, 1991.
[44] H. Keinanen, “Simulated annealing for multi-agent coalition formation,” in
Proceedings of the Third KES International Symposium on Agent and Multi- Agent Systems: Technologies and Applications, 2009, pp. 30–39.
[45] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” SCIENCE, vol. 220, no. 4598, pp. 671–680, 1983.
[46] D. P. Williamson and D. B. Shmoys, The Design of Approximation Algo- rithms, 1st ed. New York, NY, USA: Cambridge University Press, 2011.
[47] JMVC Reference Software. [Online]. Available: http://ftp3.itu.int/av-arch/ jvt-site/2008_10_Busan/JVT-AC207.zip.
[48] P. Wang, R. Dai, and I. F. Akyildiz, “Collaborative data compression using clustered source coding for wireless multimedia sensor networks,” in Proceed- ings of IEEE INFOCOM, March 2010, pp. 1–9.
[49] Vincent Bockaert, Sensor sizes. DPreview.com. [Online]. Available: http: //www.dpreview.com/glossary
[50] D. Salomon, Data Compression: The Complete Reference. Springer, July 2012.