Stereo Depth Estimation Algorithms - Revision history

imported>Student2017: /* Appendix I */

2017-12-15T16:35:33Z

Appendix I

← Older revision		Revision as of 16:35, 15 December 2017
Line 205:		Line 205:
	<br>[11] Szeliski, Richard. Computer vision: algorithms and applications. Springer Science & Business Media, 2010.		<br>[11] Szeliski, Richard. Computer vision: algorithms and applications. Springer Science & Business Media, 2010.
	<br>[12] H. Ishikawa, “Exact Optimization for Markov Random Fields with Convex Priors,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1333-1336, Oct. 2003.		<br>[12] H. Ishikawa, “Exact Optimization for Markov Random Fields with Convex Priors,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1333-1336, Oct. 2003.
	<br>[13] A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 30(6):1068-1080, June 2008.
	== Appendix II ==		== Appendix II ==
	Code and files are found at: https://github.com/yfeleke/stereo_depth		Code and files are found at: https://github.com/yfeleke/stereo_depth

imported>Student2017: /* Appendix II */

2017-12-15T16:34:38Z

Appendix II

← Older revision		Revision as of 16:34, 15 December 2017
Line 207:		Line 207:
	<br>[13] A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 30(6):1068-1080, June 2008.		<br>[13] A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 30(6):1068-1080, June 2008.
	== Appendix II ==		== Appendix II ==
	Some of the content here was derived from UCF Computer Vision class http://crcv.ucf.edu/courses/CAP5415/Fall2012/index.php		Code and files are found at: https://github.com/yfeleke/stereo_depth
	~~Code and files are found at:~~		<br>Matlab block implementation from: http://mccormickml.com/assets/StereoVision/stereoDisparity.m
	~~https~~://~~github~~.~~com~~/~~yfeleke~~/~~stereo_depth~~		<br>Some of the content here was derived from:
			* UCF Computer Vision class http://crcv.ucf.edu/courses/CAP5415/Fall2012/index.php
			* Stanford CS231A http://web.stanford.edu/class/cs231a/lectures

imported>Student2017: /* Appendix */

2017-12-15T16:05:09Z

Appendix

← Older revision		Revision as of 16:05, 15 December 2017
Line 192:		Line 192:
	A mathematical formulation for describing disparity accuracy would be a great addition to this paper. Additionally, Having CNNs investigated and contrasted with the same manner would give a more exhaustive overview of Stereo Correspondence.		A mathematical formulation for describing disparity accuracy would be a great addition to this paper. Additionally, Having CNNs investigated and contrasted with the same manner would give a more exhaustive overview of Stereo Correspondence.

	== Appendix ==		== Appendix I ==
	[1] Scharstein, D., & Szeliski, R. (2002). A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision, 47.		[1] Scharstein, D., & Szeliski, R. (2002). A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision, 47.
	<br>[2] Dall'Asta, E. and Roncella, R., 2014. A comparison of semiglobal and local dense matching algorithms for surface reconstruction. International Archives of <br>Photogrammetry, Remote Sensing and Spatial Information Sciences, 40(5): 187–194.		<br>[2] Dall'Asta, E. and Roncella, R., 2014. A comparison of semiglobal and local dense matching algorithms for surface reconstruction. International Archives of <br>Photogrammetry, Remote Sensing and Spatial Information Sciences, 40(5): 187–194.
Line 206:		Line 206:
	<br>[12] H. Ishikawa, “Exact Optimization for Markov Random Fields with Convex Priors,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1333-1336, Oct. 2003.		<br>[12] H. Ishikawa, “Exact Optimization for Markov Random Fields with Convex Priors,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1333-1336, Oct. 2003.
	<br>[13] A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 30(6):1068-1080, June 2008.		<br>[13] A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 30(6):1068-1080, June 2008.
	~~<br> some~~ of the content here was derived from UCF Computer Vision class http://crcv.ucf.edu/courses/CAP5415/Fall2012/index.php		== Appendix II ==
			Some of the content here was derived from UCF Computer Vision class http://crcv.ucf.edu/courses/CAP5415/Fall2012/index.php
			Code and files are found at:
			https://github.com/yfeleke/stereo_depth

imported>Student2017: /* Local method with SSD vs SAD */

2017-12-15T09:06:11Z

Local method with SSD vs SAD

← Older revision		Revision as of 09:06, 15 December 2017
Line 111:		Line 111:

	=== Local method with SSD vs SAD ===		=== Local method with SSD vs SAD ===
	There was a small observable difference between SAD and SSD for the local method. Some more background detail is captured in the SSD cost function. Attempts at using RMS or scatter plots to expose this information has proven challenging. One issue is that the ground truth disparity is given from both the left and right image context and another is the visual nature of the errors ~~being~~ small ~~opposing~~ an increase in error ~~data~~.		There was a small observable difference between SAD and SSD for the local method. Some more background detail is captured in the SSD cost function. Attempts at using RMS or scatter plots to expose this information has proven challenging. One issue is that the ground truth disparity is given from both the left and right image context and another is the visual nature of the errors seeming small contradicting an increase in error values..
	<br>'''The cones data set'''		<br>'''The cones data set'''
	{\|-border="1"		{\|-border="1"

imported>Student2017: /* Local algorithm benefits */

2017-12-15T09:05:09Z

Local algorithm benefits

← Older revision		Revision as of 09:05, 15 December 2017
Line 108:		Line 108:
	The experiments that were run focused on the benefits and drawback of local and global algorithms.		The experiments that were run focused on the benefits and drawback of local and global algorithms.
	=== Local algorithm benefits ===		=== Local algorithm benefits ===
	Local algorithms due to their greedy and winner take all approach utilize much smaller memory and are able to complete in much faster times than Global algorithms. The local algorithms perform well with low depth discontinuity data sets. In this section, we investigate the differences with using different cost function using a friendly dataset for evaluation. Local performance differences were significant even when the graph algorithm was implemented in C++ and the ~~blocking~~ implementation was written in Matlab.		Local algorithms due to their greedy and winner take all approach utilize much smaller memory and are able to complete in much faster times than Global algorithms. The local algorithms perform well with low depth discontinuity data sets. In this section, we investigate the differences with using different cost function using a friendly dataset for evaluation. Local performance differences were significant even when the graph algorithm was implemented in C++ and the block implementation was written in Matlab.

	=== Local method with SSD vs SAD ===		=== Local method with SSD vs SAD ===

imported>Student2017: /* Local algorithm benefits */

2017-12-15T09:04:05Z

Local algorithm benefits

← Older revision		Revision as of 09:04, 15 December 2017
Line 108:		Line 108:
	The experiments that were run focused on the benefits and drawback of local and global algorithms.		The experiments that were run focused on the benefits and drawback of local and global algorithms.
	=== Local algorithm benefits ===		=== Local algorithm benefits ===
	Local algorithms due to their greedy and winner take all approach utilize much smaller memory and are able to complete in much faster times than Global algorithms. The local algorithms perform well with low depth discontinuity data sets. In this section, we investigate the differences with using different cost function using a friendly dataset for evaluation.		Local algorithms due to their greedy and winner take all approach utilize much smaller memory and are able to complete in much faster times than Global algorithms. The local algorithms perform well with low depth discontinuity data sets. In this section, we investigate the differences with using different cost function using a friendly dataset for evaluation. Local performance differences were significant even when the graph algorithm was implemented in C++ and the blocking implementation was written in Matlab.

	=== Local method with SSD vs SAD ===		=== Local method with SSD vs SAD ===

imported>Student2017: /* Dynamic Programming */

2017-12-15T09:02:45Z

Dynamic Programming

← Older revision		Revision as of 09:02, 15 December 2017
Line 100:		Line 100:

	==== Dynamic Programming ====		==== Dynamic Programming ====
	The energy minimization problem is a 2D NP-hard problem. However, dynamic programming can find the global minimum for independent scanlines in polynomial time[11] The algorithm works by calculating costs between pairs of scan lines across the image and then finding the minimum cost path. The reason all scan line pairs are compared is to prevent streaking artifacts; If only neighbouring (vertical or horizontal) scan lines are used we get a streaking effect since the minimum cost of a removed scan line doesn't factor in the finding a minimum path for the location.		The energy minimization problem is a 2D NP-hard problem. However, dynamic programming can find the global minimum for independent scanlines in polynomial time[11] The algorithm works by calculating costs between pairs of scan lines across the image and then finding the minimum cost path. The reason all scan line pairs are compared is to prevent streaking artifacts; If only neighbouring (vertical or horizontal) scan lines are used we get a streaking effect since the minimum cost of a once-removed scan line doesn't factor in the finding a minimum path for the location.

	==== Plane Sweeping ====		==== Plane Sweeping ====

imported>Student2017: /* CNN */

2017-12-15T09:01:08Z

CNN

← Older revision		Revision as of 09:01, 15 December 2017
Line 93:		Line 93:
	----		----
	==== CNN ====		==== CNN ====
	The latest algorithms have implemented various approaches to improving on the idea of a learned stereo matching. The cost optimization designs, whether global or local, seek to gain an answer to whether a reference pixel is similar or not to the pixel under comparison. The machine learning networks seek to improve on this comparison step by adding apriori knowledge. Difficult geometry and occlusion of disparate images are considered costs that are to be minimized in previously mentioned implementations. The learned neural nets attempt to be trained with various geometric image snippets with both positive and negative matches to be able to answer the question of similarity with ~~a priori~~ knowledge.		The latest algorithms have implemented various approaches to improving on the idea of a learned stereo matching. The cost optimization designs, whether global or local, seek to gain an answer to whether a reference pixel is similar or not to the pixel under comparison. The machine learning networks seek to improve on this comparison step by adding apriori knowledge. Difficult geometry and occlusion of disparate images are considered costs that are to be minimized in previously mentioned implementations. The learned neural nets attempt to be trained with various geometric image snippets with both positive and negative matches to be able to answer the question of similarity with apriori knowledge.

	<br>Features are first extracted from input images and then these features are combined together to determine a similarity score. Here is an example neural architecture from MC_CNN [3], an algorithm that started the movement.		<br>Features are first extracted from input images and then these features are combined together to determine a similarity score. Here is an example neural architecture from MC_CNN [3], an algorithm that started the movement.

imported>Student2017: /* Graph cuts */

2017-12-15T09:00:09Z

Graph cuts

← Older revision		Revision as of 09:00, 15 December 2017
Line 87:		Line 87:

	==== Graph cuts ====		==== Graph cuts ====
	Hiroshi Ishikawa introduced using min flow or max cut algorithm paradigms to solve the global optimization problem in 2003. Hiroshi asserts, "Simulated annealing has been used to solve certain MRF problems, although it is also notoriously slow" [12]. The solutions make use of a graph with vertices corresponding to pixels and edges corresponding to connections between pixels and neighbours. Once all the disparities per pixel have been evaluated for their energy cost we can continually break off connections with nieighbouring pixels with huge disparity jumps and try to minimize the pa		Hiroshi Ishikawa introduced using min flow or max cut algorithm paradigms to solve the global optimization problem in 2003. Hiroshi asserts, "Simulated annealing has been used to solve certain MRF problems, although it is also notoriously slow" [12]. The solutions make use of a graph with vertices corresponding to pixels and edges corresponding to connections between pixels and neighbours. Once all the disparities per pixel have been evaluated for their energy cost we can continually break off connections with nieighbouring pixels with huge disparity jumps and try to minimize the overall cost.

	=== Other Methods ===		=== Other Methods ===

imported>Student2017: /* Belief Propagation */

2017-12-15T08:59:00Z

Belief Propagation

← Older revision		Revision as of 08:59, 15 December 2017
Line 84:		Line 84:

	==== Belief Propagation ====		==== Belief Propagation ====
	The belief propagation implementation of energy minimization is done by a message passing algorithm approach. Each neighbour broadcasts what it thinks its neighbours' value is supposed to be and in turn modifies own value after getting the opinion of its neighbours. You can imagine a bunch of forces pulling one way and another until a consensus is reached. Belief propagation doesn't have a mathematical proof or guarantee that a consensus can be reached to find global minima, but it is highly performant and is used or the quality of solutions that can be achieved by it.		The belief propagation implementation of energy minimization is done by a message passing algorithm approach. Each neighbour broadcasts what it thinks its neighbours' value is supposed to be and in turn modifies own value after getting the opinion of its neighbours. You can imagine a bunch of forces pulling one way and another until a consensus is reached. Belief propagation doesn't have a mathematical proof or guarantee that a consensus can be reached to find global minima, but it is highly performant and is used for the quality of solutions that can be achieved by it.

	==== Graph cuts ====		==== Graph cuts ====