When information and measures obtained from sequences of microscopic images are subject to time constraints, suitable fast algorithms must be implemented to process the whole data set. In this work, we deal with sequences of images obtained from time-lapse microscopy in order to detect single yeast cells in a microfluidics chip over time. The underlying idea consists in determining a minimum cost configuration for each couple of frames, which can be expressed by setting up and solving a linear programming (LP) problem. Laboratories seldom have the opportunity to use HPC hardware for such intent. For this reason, we propose an efficient GPU-parallel software implemented in CUDA and based on the simplex method, a common tool for solving LP problems. Our parallel strategy minimizes the threads divergence and maximizes the device occupancy, in order to maximize the overall throughput. Also, memory transfers between host and device have been minimized to exploit data locality. Experimental results on real images sequences highlight a promising speedup with respect to the CPU version suitable for real-time applications.
AndrilukaMRothSSchieleB (2008) People-tracking-bydetection and people-detection-by-tracking. In: IEEE conference on computer vision and pattern recognition (CPVR), 23–28 June 2008, pp. 1–8. Anchorage, USA: IEEE. DOI: 10.1109/CVPR.2008.4587583.
2.
AndriyenkoASchindlerKRothS (2012) Discretecontinuous optimization for multi-target tracking. In: IEEE conference on computer vision and pattern recognition (CVPR), 16–21 June 2012, pp. 1926–1933. Providence, USA: IEEE. DOI: 10.1109/CVPR.2012.6247893.
3.
BabaeeMYouYRigollG (2017) Combined segmentation, reconstruction, and tracking of multiple targets in multi-view video sequences. Computer Vision and Image Understanding154: 166–181.
4.
BerclazJFleuretFFuaP (2009) Multiple object tracking using flow linear programming. In: Twelfth IEEE international workshop on performance evaluation of tracking and surveillance (PETS-Winter), 7–9 December 2009, pp. 1–8. Snowbird, USA: IEEE. DOI: 10.1109/PETS-WINTER.2009.5399488.
5.
BibbyCReidI (2010) Real-time tracking of multiple occluding objects using level sets. In: IEEE conference on computer vision and pattern recognition (CVPR), 13–18 June 2010, pp. 1307–1314. San Francisco, USA: IEEE. DOI: 10.1109/CVPR.2010.5539818.
6.
BielingJPeschlowPMartiniP (2010) An efficient GPU implementation of the revised simplex method. In: IEEE international symposium on parallel & distributed processing, workshops and PhD forum (IPDPSW), 19–23 April 2010, pp. 1–8. Atlanta, USA: IEEE. DOI: 10.1109/IPDPSW.2010.5470831.
7.
BrediesKWolinskiH (2011) An active-contour based algorithm for the automated segmentation of dense yeast populations on transmission microscopy images. Computing and Visualization in Science14(7): 341–352.
8.
BroxTMalikJ (2010) Object segmentation by long term analysis of point trajectories. Computer Vision-ECCV2010: 282–295.
9.
CelestinoSLaccettiGLapegnaM. (2014) A bidirectional path tracing method for global illumination rendering on GPU. Applied Mathematical Sciences8(135): 6783–6790.
10.
CuomoSGallettiAGiuntaG. (2015) Toward a multi-level parallel framework on GPU cluster with PetSC-CUDA for PDE-based optical flow computation. Procedia Computer Science51: 170–179.
11.
D’AmoreLLaccettiGRomanoD. (2015) Towards a parallel component in a GPU–CUDA environment: a case study with the L-BFGS Harwell routine. International Journal of Computer Mathematics92(1): 59–76.
12.
D’AmoreLMarcellinoLMeleV. (2012) Deconvolution of 3D fluorescence microscopy images using graphics processing units. Parallel Processing and Applied Mathematics7203: 690–699.
13.
DantzigGB (1963) Linear Programming and Extensions. Princeton, NJ: Princeton University Press; Santa Monica, CA: RAND Corporation.
14.
DehghanAModiriAssari SShahM (2015) GMMCP tracker: Globally optimal generalized maximum multi clique problem for multiple object tracking. In: Proceedings of the IEEE conference on computer vision and pattern recognition, 7–12 June 2015, pp. 4091–4099. Boston, USA: IEEE. DOI: 10.1109/CVPR.2015.7299036.
15.
FioreGPerrinoGdi BernardoM. (2015) In vivo real-time control of gene expression: a comparative analysis of feedback control strategies in yeast. ACS Synthetic Biology5(2): 154–162.
16.
Gade-NielsenNFJørgensenJBDammannB (2012) MPC toolbox with GPU accelerated optimization algorithms. In: 10th European workshop on advanced control and diagnosis, 8–9 November 2012, Kgs. Lyngby, Denmark: Technical University of Denmark (DTU).
17.
GalassoFKeuperMBroxT. (2014) Spectral graph reduction for efficient image and streaming video segmentation. In: Proceedings of the IEEE conference on computer vision and pattern recognition, 23–28 June 2014, pp. 49–56. Columbus, USA: IEEE. DOI: 10.1109/CVPR.2014.14.
JiangHFelsSLittleJJ (2007) A linear programming approach for multiple object tracking. In: IEEE conference on computer vision and pattern recognition, 2007, CVPR’07, 17–22 June 2007, pp. 1–8. Minneapolis, USA: IEEE. DOI: 10.1109/CVPR.2007.383180.
20.
La BroccaRMenolascinaFdi BernardoD. (2011) Segmentation, tracking and lineage analysis of yeast cells in bright field microscopy images. In: IL NUOVO CIMENTO, September–October 2012, pp. 131–139. PR PS BB 2011 - 1st International Workshop on Pattern Recognition in Proteomics, Structural Biology and Bioinformatics. DOI: 10.1393/ncc/i2012-11342-2.
21.
LalamiMEEl-BazDBoyerV (2011a) Efficient implementation of the simplex method on a CPU-GPU system. In: 2011 IEEE International Parallel Distributed Processing Symposium, 16–20 May 2011, pp. 1999–2006. Shanghai, China: IEEE. DOI: 10.1109/IPDPS.2011.362.
22.
LalamiMEEl-BazDBoyerV (2011b) Multi GPU implementation of the simplex algorithm. In: 2011 IEEE 13th international conference on high performance computing and communications (HPCC), 2–4 September 2011, pp. 179–186. Banff, AB, Canada: IEEE. DOI: 10.1109/HPCC.2011.32.
23.
LockeJCElowitzMB (2009) Using movies to analyse gene circuit dynamics in single cells. Nature Reviews Microbiology7(5): 383–392.
MilanARothSSchindlerK (2014) Continuous energy minimization for multitarget tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence36(1): 58–72.
PirsiavashHRamananDFowlkesCC (2011) Globallyoptimal greedy algorithms for tracking a variable number of objects. In: 2011 IEEE Conference on computer vision and pattern recognition (CVPR 2011), 20–25 June 2011, pp. 1201–1208. Colorado Springs, USA: IEEE. DOI: 10.1109/CVPR.2011.5995604.
28.
PloskasNSamarasN (2015) Efficient GPU-based implementations of simplex type algorithms. Applied Mathematics and Computation250: 552–570.
29.
Roshan ZamirADehghanAShahM (2012) GMCP-tracker: global multi-object tracking using generalized minimum clique graphs. Computer Vision-ECCV2012: 343–356.
30.
ShamirR (1987) The efficiency of the simplex method: a survey. Management Science33(3): 301–334.
31.
SpampinatoDGElsteryAC (2009) Linear optimization on modern GPUs. In: IEEE international symposium on parallel and distributed processing, 2009. IPDPS 2009, 23–29 May 2009, pp. 1–8. Rome, Italy: IEEE. DOI: 10.1109/IPDPS.2009.5161106.
32.
TiwariDGuptaSGallarnoG. (2015) Reliability lessons learned from GPU experience with the titan supercomputer at oak ridge leadership computing facility. In: SC15: International conference for high performance computing, networking, storage and analysis, 15–20 November 2015, pp. 1–12. Austin, TX, USA: IEEE. DOI: 10.1145/2807591.2807666.
33.
WhaleyRCPetitetADongarraJJ (2001) Automated empirical optimizations of software and the atlas project. Parallel Computing27(1): 3–35.
34.
XavierCIyengarSS (1998) Introduction to Parallel Algorithms. New York: John Wiley & Sons. ISBN 0-471-25182-8.
35.
ZhangLLiYNevatiaR (2008) Global data association for multi-object tracking using network flows. In: IEEE conference on computer vision and pattern recognition, 2008. CVPR 2008, 23–28 June 2008, pp. 1–8. Anchorage, USA: IEEE. DOI: 10.1109/CVPR.2008.4587584.
