{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T10:39:28Z","timestamp":1761647968330,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T00:00:00Z","timestamp":1338508800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001868","name":"National Science Council Taiwan","doi-asserted-by":"publisher","award":["100-2220-E-007-002100-2219-E-007-006"],"award-info":[{"award-number":["100-2220-E-007-002100-2219-E-007-006"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004725","name":"Ministry of Economic Affairs","doi-asserted-by":"publisher","award":["99-EC-17-A-01-S1-034"],"award-info":[{"award-number":["99-EC-17-A-01-S1-034"]}],"id":[{"id":"10.13039\/501100004725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>Markov random field models provide a robust formulation for the stereo vision problem of inferring three-dimensional scene geometry from two images taken from different viewpoints. One of the most advanced algorithms for solving the associated energy minimization problem in the formulation is belief propagation (BP). Although BP provides very accurate results in solving stereo vision problems, the high computational cost of the algorithm hinders it from real-time applications. In recent years, multicore architectures have been widely adopted in various industrial application domains. The high computing power of multicore processors provides new opportunities to implement stereo vision algorithms. This article examines and extracts the parallelisms in the BP method for stereo vision on multicore processors. This article shows that parallelism of the algorithm can be efficiently utilized on multicore processors. The results show that parallelization on multicore processors provides a speedup for the BP algorithm of almost 15 times compared to the single-processor implementation on the PPE of the Cell BE. The experimental results also indicate that a frame rate of 6.5 frames\/second is possible when implementing the parallelized BP algorithm on the multicore processor of Cell BE with one PPE and six SPEs.<\/jats:p>","DOI":"10.1145\/2180887.2180889","type":"journal-article","created":{"date-parts":[[2012,6,11]],"date-time":"2012-06-11T13:03:21Z","timestamp":1339419801000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Parallelization of Belief Propagation on Cell Processors for Stereo Vision"],"prefix":"10.1145","volume":"11S","author":[{"given":"Kun-Yuan","family":"Hsieh","sequence":"first","affiliation":[{"name":"National Tsing-Hua University"}]},{"given":"Chi-Hua","family":"Lai","sequence":"additional","affiliation":[{"name":"National Tsing-Hua University"}]},{"given":"Shang-Hong","family":"Lai","sequence":"additional","affiliation":[{"name":"National Tsing-Hua University"}]},{"given":"Jenq Kuen","family":"Lee","sequence":"additional","affiliation":[{"name":"National Tsing-Hua University"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium.","author":"Bader D. A.","unstructured":"Bader , D. A. , Agarwal , V. , and Madduri , K . 2007. On the design and analysis of irregular algorithms on the cell processor: A case study of list ranking . In Proceedings of the IEEE International Parallel and Distributed Processing Symposium. Bader, D. A., Agarwal, V., and Madduri, K. 2007. On the design and analysis of irregular algorithms on the cell processor: A case study of list ranking. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/34.969114"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1109\/CRV.2006.19"},{"unstructured":"Chandy K. M. and Misra J. 1988. Parallel Program Design: A Foundation. Addison Wesley Publishing Company Inc. Reading MA. Chandy K. M. and Misra J. 1988. Parallel Program Design: A Foundation . Addison Wesley Publishing Company Inc. Reading MA.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 19th International Workshop onLanguages and Compilers for Parallel Computing (LCPC\u201906)","volume":"4382","author":"Chen T.","year":"2006","unstructured":"Chen , T. , Sura , Z. , O\u2019Brien , K. M. , and O\u2019Brien , J. K. 2006 . Optimizing the use of static buffers for DMA on a Cell chip . In Proceedings of the 19th International Workshop onLanguages and Compilers for Parallel Computing (LCPC\u201906) , Revised Papers. Lecture Notes in Computer Science , vol. 4382 , 314--329. Chen, T., Sura, Z., O\u2019Brien, K. M., and O\u2019Brien, J. K. 2006. Optimizing the use of static buffers for DMA on a Cell chip. In Proceedings of the 19th International Workshop onLanguages and Compilers for Parallel Computing (LCPC\u201906), Revised Papers. Lecture Notes in Computer Science, vol. 4382, 314--329."},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1109\/SIPS.2008.4671775"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/s11263-006-7899-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1007\/s10766-007-0035-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1023\/A:1008115206617"},{"unstructured":"IBM. 2007. Cell Broadband Engine Programming Handbook version 1.1. IBM. IBM . 2007. Cell Broadband Engine Programming Handbook version 1.1. IBM.","key":"e_1_2_1_10_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1109\/ICPP.2008.39"},{"volume-title":"Proceedings of 8th International Conference on Signal Processing.","author":"Kim Y.","unstructured":"Kim , Y. , Park , S. , Chen , C. , and Jeong , H . 2006. Real-time architecture of stereo vision for robot eye . In Proceedings of 8th International Conference on Signal Processing. Kim, Y., Park, S., Chen, C., and Jeong, H. 2006. Real-time architecture of stereo vision for robot eye. In Proceedings of 8th International Conference on Signal Processing.","key":"e_1_2_1_12_1"},{"doi-asserted-by":"crossref","unstructured":"Kindermann R. and Snell J. L. 1980. Markov Random Fields and Their Applications. AMS. Kindermann R. and Snell J. L. 1980. Markov Random Fields and Their Applications . AMS.","key":"e_1_2_1_13_1","DOI":"10.1090\/conm\/001"},{"volume-title":"Proceedings of IEEE\/ACM\/IFIP Workshop on Embedded Systems for Real-Time Multimedia. 39--44","author":"Lai C.-H.","unstructured":"Lai , C.-H. , Hsieh , K.-Y. , Lai , S.-H. , and Lee , J. K . 2008. Parallelization of belief propagation method on embedded multicore processors for stereo vision . In Proceedings of IEEE\/ACM\/IFIP Workshop on Embedded Systems for Real-Time Multimedia. 39--44 . Lai, C.-H., Hsieh, K.-Y., Lai, S.-H., and Lee, J. K. 2008. Parallelization of belief propagation method on embedded multicore processors for stereo vision. In Proceedings of IEEE\/ACM\/IFIP Workshop on Embedded Systems for Real-Time Multimedia. 39--44.","key":"e_1_2_1_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/1346281.1346318"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the GSPx Multicore Applications Conference.","author":"McCool M. D.","year":"2006","unstructured":"McCool , M. D. 2006 . Data-parallel programming on the Cell BE and the GPU using the rapid-mind development platform . In Proceedings of the GSPx Multicore Applications Conference. McCool, M. D. 2006. Data-parallel programming on the Cell BE and the GPU using the rapid-mind development platform. In Proceedings of the GSPx Multicore Applications Conference."},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/1274000.1274084"},{"volume-title":"Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems. 250--255","author":"Miura J.","unstructured":"Miura , J. , Negishi , Y. , and Shirai , Y . 2002. Mobile robot map generation by integrating omnidirectional stereo and laser range finder . In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems. 250--255 . Miura, J., Negishi, Y., and Shirai, Y. 2002. Mobile robot map generation by integrating omnidirectional stereo and laser range finder. In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems. 250--255.","key":"e_1_2_1_18_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1023\/A:1008987612352"},{"volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl J.","unstructured":"Pearl , J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference . Morgan Kaufmann Publishers Inc . Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc.","key":"e_1_2_1_20_1"},{"volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium. 1--10","author":"Petrini F.","unstructured":"Petrini , F. , Fossum , G. , Fern\u00e1ndez , J. , Barbanescu , A. L. , Kistler , M. , and Perrone , M . 2007. Multicore surprise: Lessons learned from optimizing Sweep3D on the Cell broadband engine . In Proceedings of the IEEE International Parallel and Distributed Processing Symposium. 1--10 . Petrini, F., Fossum, G., Fern\u00e1ndez, J., Barbanescu, A. L., Kistler, M., and Perrone, M. 2007. Multicore surprise: Lessons learned from optimizing Sweep3D on the Cell broadband engine. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium. 1--10.","key":"e_1_2_1_21_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1023\/B:AURO.0000047287.00119.b6"},{"volume-title":"Proceedings of the IEEE Workshop on Embedded Systmes for Real-time Multimedia. 33--38","author":"Rofouei M.","unstructured":"Rofouei , M. , Moazeni , M. , and Sarrafzadeh , M . 2008. Fast GPU-based space-time correlation for activity recognition in video sequences . In Proceedings of the IEEE Workshop on Embedded Systmes for Real-time Multimedia. 33--38 . Rofouei, M., Moazeni, M., and Sarrafzadeh, M. 2008. Fast GPU-based space-time correlation for activity recognition in video sequences. In Proceedings of the IEEE Workshop on Embedded Systmes for Real-time Multimedia. 33--38.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 11th International Conference on Distributed Computing Systems.","author":"Singh A. K.","year":"1991","unstructured":"Singh , A. K. 1991 . Parallel programming: Achieving portability through abstraction . In Proceedings of the 11th International Conference on Distributed Computing Systems. Singh, A. K. 1991. Parallel programming: Achieving portability through abstraction. In Proceedings of the 11th International Conference on Distributed Computing Systems."},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1109\/TPAMI.2003.1206509"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1109\/18.910585"},{"volume-title":"Proceedings of the British Machine Vision Conference.","author":"Yang Q.","unstructured":"Yang , Q. , Wan , L. , Yang , R. , Wang , S. , Liao , M. , and Nist\u00e9r , D . 2006. Real-time global stereo matching using hierarchical belief propagation . In Proceedings of the British Machine Vision Conference. Yang, Q., Wan, L., Yang, R., Wang, S., Liao, M., and Nist\u00e9r, D. 2006. Real-time global stereo matching using hierarchical belief propagation. In Proceedings of the British Machine Vision Conference.","key":"e_1_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1109\/TIT.2005.850085"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2180887.2180889","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2180887.2180889","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:22Z","timestamp":1750240462000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2180887.2180889"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1145\/2180887.2180889"],"URL":"https:\/\/doi.org\/10.1145\/2180887.2180889","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2012,6]]},"assertion":[{"value":"2009-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}