中文文档

Introuction

PatchMatch is the state-of-the-art stereo match algorithm framework.

Source code for the paper[1] and it's variants are implemented. The major difference between raw PatchMatch method and it's variants is the propagation way.

• raw(the origin propgation way of PatchMatch)[1].
• rows cols sweep(rows sweep, cols sweep, reverse rows sweep, reverse cols sweep)[2].
• red black(split pixels to red and black, each turn traverse the red pixels or black ones respectively)[3].

Some experiments results are listed follwing.

Experiments

We experiment on Aloe image of Middlebury dataset 2006. And the left and right disparity map show above.

Experiment of different propagation way

This experiment explore the the affects of different propagation way of PatchMatch.

• raw[1]
• rows cols sweep[2]
• red black[3].

Left and right image show the affects of different propagation way of the left and right disparity respectively. The horizontal axis is the number of iterations, and the vertical axis is bad error 1.0 rate

We can see, raw propagation way is the best(red line), 2 iterations converge; Rows cols sweep propagation way is the second(green line), 3 iterations converge; Red black propagation way is the worse(blue line), also 3 iterations converge, but worse bad error 1.0 rate.

The figure below shows the disparity map obtained using different propagation methods. From top to bottom, raw、rows cols sweep and red black respectively. It can be seen that there are no such big differences between in these disparitp map in visual sense.

Experiment of different steps of PatchMatch

This experiment explore the the affects of different steps of PatchMatch. Left image is left disparity map comparison and right image is right disparity map comparison.

The images above show the PatchMatch has plane refinement or not, obviously, plane refinement has sufficient effect, reduce about 20%-30% bad error 1.0. This is obvious, random initialization and spatial propagation lead to coarse results, which is the reason need to refine, plane refinement reduce bad error a lot .

The images above show the PatchMatch has view propagation or not, obviously, view propagation has limited effect for raw PatchMatch, but for it's variants, has some effect in the first few iterations, but useless after 3 or 4 iterations for rwos cols sweep and 6 or 7 iterations for red black.

The images above show the PatchMatch has post-processing or not, obviously, post-processing improve the result a lot, reduce about 10% bad error 1.0.

Experiment of different window size

In this example, weirdly, increasing the window size does not lower the bad error 1.0 rate. However, increasing the window size but improve the visual effect, just as the below:

The first row is the left and right disparity maps after 3 iterations with window size 11px; and the second row is the disparity maps with window size 31px. Both generate by the raw PatchMatch method.

Apparently, the second row better than the first one in visual, but about the same of the bad error 1.0 rate.

Conclusions

In conclusion, the propagation way of raw PatchMatch method achieve the best result in all experiments. But, the raw propagation way is sequential implementation, unable to parallel. And it's variants can be implemented parallel but with slowly bad error 1.0 rate increase, so it some trade off. More analysis can refers to the report.

Citations

[1] PatchMatch

[2] other propagation way

[3] Gipuma

Appendix

Belowing table show the experiment on the full Middlebury 2006 datasets. We show the bad error 1.0 error of left and right disparity map for each method after each iteration.

Method	Dataset	iteration 1	iteration 2	iteration 3
spatial prop	Aloe	(29.709475, 31.058928)	(21.251978, 22.209633)	(19.542376, 20.550035)
spatial prop + refine		(16.692196, 18.488512)	(14.312298, 15.287677)	(14.354073, 15.190202)
spatial prop + refine + view prop		(15.375657, 16.495981)	(14.228748, 14.908539)	(14.292044, 15.072473)
spatial prop + refine + view prop + post-process		(11.802012, 12.540034)	(10.94373, 11.446294)	(10.891195, 11.403254)
spatial prop + post-process		(22.747009, 24.128109)	(15.845306, 15.868093)	(14.344579, 14.820559)
spatial prop	Baby1	(24.455206, 23.347948)	(19.199659, 16.926903)	(18.600222, 14.641058)
spatial prop + refine		(15.36745, 11.954715)	(13.823049, 11.59021)	(13.98665, 11.461946)
spatial prop + refine + view prop		(13.851188, 10.983574)	(13.571755, 11.621622)	(13.78313, 11.577776)
spatial prop + refine + view prop + post-process		(6.998888, 6.645507)	(7.326746, 6.557162)	(7.392186, 6.872587)
spatial prop + post-process		(18.411098, 16.426935)	(11.928538, 11.911524)	(11.646489, 10.438453)
spatial prop	Baby2	(34.149597, 33.292976)	(28.361364, 28.737648)	(26.852955, 25.936785)
spatial prop + refine		(21.204763, 20.40835)	(20.299065, 20.469864)	(20.571953, 20.521563)
spatial prop + refine + view prop		(20.039265, 18.948368)	(20.168837, 19.723841)	(20.555592, 20.422092)
spatial prop + refine + view prop + post-process		(17.720045, 15.941365)	(16.873896, 15.592566)	(16.345789, 16.430862)
spatial prop + post-process		(29.752634, 26.355604)	(23.667953, 24.80924)	(22.91604, 22.402985)
spatial prop	Baby3	(34.131363, 32.760838)	(24.146824, 24.02746)	(24.021894, 25.348507)
spatial prop + refine		(22.96246, 20.44035)	(21.825098, 19.087143)	(21.898077, 18.797699)
spatial prop + refine + view prop		(21.933329, 18.938091)	(21.304348, 19.335148)	(21.682232, 19.215164)
spatial prop + refine + view prop + post-process		(17.793308, 13.296432)	(16.283628, 13.318696)	(17.730843, 13.870369)
spatial prop + post-process		(28.80945, 25.135754)	(16.604614, 17.79269)	(19.561506, 17.868761)
spatial prop	Bowling1	(46.957027, 44.483765)	(41.188023, 39.243633)	(39.154839, 38.336899)
spatial prop + refine		(35.078747, 33.535549)	(35.370407, 33.695637)	(35.553825, 33.927021)
spatial prop + refine + view prop		(34.398212, 32.365028)	(34.798756, 33.106487)	(35.381424, 33.975632)
spatial prop + refine + view prop + post-process		(31.464773, 29.441311)	(31.657917, 30.823126)	(31.974205, 30.371378)
spatial prop + post-process		(42.914642, 39.038174)	(36.139088, 33.797394)	(35.211613, 33.755264)
spatial prop	Bowling2	(37.061802, 36.023426)	(29.018974, 28.662682)	(28.951864, 26.819595)
spatial prop + refine		(24.304192, 22.713684)	(23.259716, 21.88335)	(23.317675, 21.780855)
spatial prop + refine + view prop		(23.75511, 21.735708)	(23.296322, 21.725338)	(23.446404, 21.877249)
spatial prop + refine + view prop + post-process		(19.300837, 15.094869)	(18.617535, 15.266914)	(18.122141, 16.199743)
spatial prop + post-process		(33.248123, 27.449209)	(25.30047, 22.458666)	(23.439083, 20.097614)
spatial prop	Cloth1	(19.858059, 17.288223)	(12.652148, 11.436905)	(12.703999, 9.885929)
spatial prop + refine		(9.953982, 7.454145)	(9.242984, 7.135265)	(9.3065, 7.119709)
spatial prop + refine + view prop		(9.824357, 6.982306)	(9.288353, 7.155357)	(9.24752, 7.141746)
spatial prop + refine + view prop + post-process		(5.543457, 2.783719)	(5.102729, 2.588632)	(5.01912, 2.352064)
spatial prop + post-process		(13.002139, 8.035518)	(8.27403, 4.290622)	(7.543587, 2.992417)
spatial prop	Cloth2	(35.623867, 33.884277)	(23.739468, 22.534174)	(21.909992, 21.604769)
spatial prop + refine		(15.675052, 15.208164)	(14.769989, 14.540291)	(14.718806, 14.478497)
spatial prop + refine + view prop		(15.159478, 14.738156)	(14.607079, 14.327445)	(14.545284, 14.509706)
spatial prop + refine + view prop + post-process		(11.129767, 9.776544)	(10.519942, 10.202859)	(10.130454, 9.846452)
spatial prop + post-process		(27.581299, 26.129456)	(15.343612, 15.861682)	(15.328631, 14.488483)
spatial prop	Cloth3	(23.841467, 20.435543)	(15.433275, 13.716378)	(15.534384, 13.401387)
spatial prop + refine		(11.570419, 8.885216)	(10.456932, 8.181347)	(10.506189, 8.484672)
spatial prop + refine + view prop		(11.127747, 8.419859)	(10.441377, 8.248104)	(10.594336, 8.109405)
spatial prop + refine + view prop + post-process		(6.663426, 3.88554)	(6.134552, 3.753322)	(6.074924, 3.921187)
spatial prop + post-process		(16.977121, 13.214077)	(10.651371, 6.916197)	(9.162616, 6.181865)
spatial prop	Cloth4	(29.565571, 30.478746)	(19.947569, 22.840647)	(19.334, 20.401972)
spatial prop + refine		(15.517134, 17.337244)	(15.243118, 16.412832)	(15.347357, 16.532677)
spatial prop + refine + view prop		(15.882279, 16.813557)	(15.328007, 16.538294)	(15.203171, 16.705574)
spatial prop + refine + view prop + post-process		(12.021722, 11.770801)	(12.081018, 11.772674)	(12.079146, 11.611634)
spatial prop + post-process		(23.216404, 23.501654)	(13.929842, 14.887336)	(13.659572, 14.429187)
spatial prop	Flowerpots	(50.201622, 47.636837)	(42.180717, 42.48624)	(41.02047, 40.958008)
spatial prop + refine		(36.393715, 34.839508)	(35.506214, 34.621189)	(35.650936, 34.781372)
spatial prop + refine + view prop		(35.962643, 33.867275)	(35.73814, 34.589027)	(35.707836, 34.756634)
spatial prop + refine + view prop + post-process		(32.776299, 32.390995)	(32.31554, 32.183189)	(32.42934, 33.279732)
spatial prop + post-process		(47.362236, 48.181087)	(39.495331, 39.732204)	(38.98262, 40.094627)
spatial prop	Lampshade1	(50.149178, 53.37994)	(43.596531, 43.33812)	(40.674114, 43.798763)
spatial prop + refine		(36.449036, 37.001434)	(34.947258, 34.910431)	(36.237438, 35.269333)
spatial prop + refine + view prop		(35.886024, 34.017227)	(35.095188, 34.343674)	(36.045189, 34.20261)
spatial prop + refine + view prop + post-process		(32.424316, 29.446352)	(31.288309, 27.810999)	(31.484926, 28.923912)
spatial prop + post-process		(45.849197, 46.369766)	(41.365707, 39.609264)	(39.161724, 37.864052)
spatial prop	Lampshade2	(58.204231, 62.856251)	(47.467697, 50.835155)	(46.292366, 50.348293)
spatial prop + refine		(40.721554, 42.039822)	(39.519382, 41.094189)	(39.476936, 41.066101)
spatial prop + refine + view prop		(39.280945, 39.314026)	(39.751575, 40.486862)	(39.625492, 40.94376)
spatial prop + refine + view prop + post-process		(33.56345, 32.164036)	(33.766308, 33.695148)	(34.504089, 33.062229)
spatial prop + post-process		(56.212471, 54.356781)	(46.123837, 43.713253)	(42.806316, 41.38818)
spatial prop	Midd1	(61.673351, 62.588783)	(57.00901, 56.19936)	(55.084568, 57.122929)
spatial prop + refine		(53.353676, 53.958153)	(53.154316, 53.030514)	(53.366463, 53.240337)
spatial prop + refine + view prop		(53.546062, 52.996803)	(53.19849, 52.81604)	(53.292065, 53.035164)
spatial prop + refine + view prop + post-process		(53.420517, 53.325779)	(53.040394, 52.651554)	(53.01017, 53.00552)
spatial prop + post-process		(58.911362, 59.065388)	(54.058704, 55.516418)	(53.42226, 54.104038)
spatial prop	Midd2	(65.702408, 62.091476)	(59.115532, 57.283634)	(59.286606, 57.129787)
spatial prop + refine		(55.724384, 54.551826)	(55.03653, 54.735966)	(55.05138, 54.674191)
spatial prop + refine + view prop		(55.196911, 53.95842)	(54.824474, 54.121178)	(54.961685, 54.482922)
spatial prop + refine + view prop + post-process		(52.804276, 52.525097)	(53.235519, 52.847637)	(52.744282, 52.623108)
spatial prop + post-process		(60.595783, 61.597267)	(54.278587, 55.284229)	(54.367687, 54.730621)
spatial prop	Monopoly	(53.665424, 57.072784)	(43.753891, 42.409859)	(43.684338, 43.326214)
spatial prop + refine		(37.668232, 38.303337)	(36.920872, 37.480324)	(37.247879, 37.318039)
spatial prop + refine + view prop		(37.787811, 36.672565)	(36.570679, 36.349827)	(36.953815, 37.046551)
spatial prop + refine + view prop + post-process		(34.906349, 35.612835)	(35.147335, 36.153378)	(35.02837, 35.361481)
spatial prop + post-process		(47.620644, 47.265572)	(37.208836, 37.350376)	(39.613201, 39.494846)
spatial prop	Plastic	(64.571594, 65.97406)	(62.158966, 60.612103)	(62.489937, 61.272121)
spatial prop + refine		(59.148296, 59.131683)	(59.510574, 59.004536)	(59.698421, 59.415371)
spatial prop + refine + view prop		(59.514408, 57.790558)	(59.255638, 58.081272)	(59.329117, 59.028175)
spatial prop + refine + view prop + post-process		(54.136478, 57.594402)	(53.966518, 57.583542)	(52.964668, 57.729858)
spatial prop + post-process		(60.922626, 63.753117)	(56.498627, 60.539902)	(54.763912, 59.389175)
spatial prop	Rocks1	(28.354214, 28.638474)	(19.895071, 19.12496)	(18.710335, 18.839428)
spatial prop + refine		(15.775517, 14.709062)	(15.052464, 13.846105)	(15.099523, 14.23275)
spatial prop + refine + view prop		(15.526868, 13.869635)	(14.971066, 13.648967)	(14.976789, 13.920508)
spatial prop + refine + view prop + post-process		(10.846423, 10.840699)	(10.450238, 10.827345)	(10.305882, 10.721781)
spatial prop + post-process		(21.590462, 19.673767)	(13.442925, 13.013673)	(13.318919, 13.54531)
spatial prop	Rocks2	(23.88744, 24.211765)	(18.449602, 15.973927)	(18.496025, 16.321781)
spatial prop + refine		(15.87345, 12.589507)	(14.819714, 12.085851)	(14.87504, 12.180604)
spatial prop + refine + view prop		(15.409857, 12.146264)	(14.805087, 12.214309)	(14.637837, 11.858824)
spatial prop + refine + view prop + post-process		(10.428617, 7.569475)	(10.713513, 7.619714)	(10.628299, 7.772973)
spatial prop + post-process		(21.956757, 16.171701)	(13.400318, 9.960572)	(12.515103, 9.384419)
spatial prop	Wood1	(25.818203, 29.892365)	(17.155361, 14.32669)	(16.837778, 15.303093)
spatial prop + refine		(14.858951, 10.861671)	(14.033355, 10.859897)	(14.180614, 11.097049)
spatial prop + refine + view prop		(14.452659, 10.508014)	(14.171151, 10.692531)	(14.089539, 10.795434)
spatial prop + refine + view prop + post-process		(9.290318, 7.296114)	(9.560589, 6.918209)	(9.064995, 8.103969)
spatial prop + post-process		(27.025845, 24.246851)	(13.297061, 10.307528)	(13.340233, 11.044415)
spatial prop	Wood2	(27.104691, 23.25629)	(18.091333, 18.806461)	(17.676918, 17.706741)
spatial prop + refine		(16.534327, 15.568189)	(16.319975, 15.673812)	(16.044113, 16.195091)
spatial prop + refine + view prop		(16.393911, 15.192296)	(16.03293, 15.851506)	(16.084497, 16.216217)
spatial prop + refine + view prop + post-process		(11.701149, 10.674123)	(10.607642, 11.371233)	(11.245108, 11.773843)
spatial prop + post-process		(20.920162, 19.962101)	(13.315315, 14.518795)	(12.70146, 13.817956)