[e:main,gray,bend right=10] (340:15mm) to (0:15mm);

[e:coloredborder] (180:15mm) – (180:7mm);
[e:coloredthin,color=BostonUniversityRed] (180:15mm) – (180:7mm);
[e:coloredborder] (0:15mm) – (0:7mm);
[e:coloredthin,color=BostonUniversityRed] (0:15mm) – (0:7mm);
[e:main,gray] (180:7mm) – (180:4mm);
[e:main,gray] (0:7mm) – (0:4mm);
[e:coloredborder] (180:4mm) – (0:4mm);
[e:coloredthin,color=BostonUniversityRed] (180:4mm) – (0:4mm);

[e:coloredborder] (240:15mm) – (240:7mm);
[e:coloredthin,color=BostonUniversityRed] (240:15mm) – (240:7mm);
[e:coloredborder] (60:15mm) – (60:7mm);
[e:coloredthin,color=BostonUniversityRed] (60:15mm) – (60:7mm);
[e:main,gray] (240:7mm) – (60:7mm);

[e:coloredborder] (300:15mm) – (300:7mm);
[e:coloredthin,color=BostonUniversityRed] (300:15mm) – (300:7mm);
[e:coloredborder] (120:15mm) – (120:7mm);
[e:coloredthin,color=BostonUniversityRed] (120:15mm) – (120:7mm);
[e:main,gray] (300:7mm) – (120:7mm);

[e:coloredborder] (80:11mm) – (100:11mm);
[e:coloredthin,color=BostonUniversityRed] (80:11mm) – (100:11mm);

[e:main,blue,bend right=15] (80:11mm) to (66.66:15mm); [e:main,blue,bend left=15] (100:11mm) to (180:4mm);
[e:main,myGreen,bend left=20] (100:11mm) to (113.34:15mm);
[e:main,myGreen,bend right=15] (80:11mm) to (0:4mm);

The construction of the new conformal $K_{3,3}$-bisubdivision in the second case of the proof of <ref>.

For the last case, we may assume $v_{V_1}$ and $v_{V_2}$ to belong to different bisubdivided edges $Q_1$ and $Q_2$ such that neither $Q_i$ shares an endpoint with $P$.
Here we need to distinguish between $Q_1$ and $Q_2$ sharing an endpoint and being disjoint.
<Ref> illustrates the construction of $L'$.

[v:marked] () at (113.34:15mm);
[v:marked] () at (66.66:15mm);
[v:marked] () at (120:15mm);
[v:marked] () at (60:15mm);
[v:marked] () at (200:15mm);
[v:marked] () at (180:15mm);

in 0,2,4

[v:mainempty] () at (*60:15mm);
[v:maingray] () at (*60:7mm);

in 1,3,5

[v:main] () at (*60:15mm);
[v:mainemptygray] () at (*60:7mm);

[v:maingray] () at (20:15mm);
[v:maingray] () at (140:15mm);
[v:maingray] () at (220:15mm);
[v:maingray] () at (260:15mm);
[v:maingray] () at (340:15mm);

[v:mainemptygray] () at (66.66:15mm);
[v:maingray] () at (73.32:15mm);
[v:mainemptygreen] () at (80.01:15mm);
[v:maingreen] () at (86.68:15mm);
[v:mainemptygreen] () at (93.35:15mm);
[v:maingreen] () at (100.01:15mm);
[v:mainemptygray] () at (106.68:15mm);
[v:maingray] () at (113.34:15mm);

[v:mainemptygray] () at (40:15mm);
[v:mainemptygray] () at (160:15mm);
[v:mainemptygray] () at (200:15mm);
[v:mainemptygray] () at (280:15mm);
[v:mainemptygray] () at (320:15mm);

() at (0:18mm)$b_{1}$;
() at (60:17mm)$u$;
() at (120:17mm)$v$;
() at (180:18mm)$a_{2}$;
() at (240:17mm)$b_{2}$;
() at (300:18mm)$a_{1}$;

[blue] () at (90:18mm)$C$;

[e:main,myGreen,bend left=15] (113.34:15mm) to (200:15mm);
[e:main,blue,bend right=15] (66.66:15mm) to (0:7mm);
[e:marker,BrightUbe,bend left=15] (113.34:15mm) to (200:15mm);
[e:marker,BrightUbe,bend right=15] (66.66:15mm) to (0:7mm);
[e:marker,BrightUbe] (0:7mm) – (180:15mm);
[e:marker,BrightUbe] (60:15mm) – (240:15mm);
[e:marker,BrightUbe] (120:15mm) – (300:15mm);

[e:marker,BrightUbe,bend right=28] (300:15mm) to (0:15mm) to (60:15mm) to (120:15mm) to (180:15mm) to (240:15mm);

[e:main,gray] (60:15mm) to (66.66:15mm);
[e:coloredborder] (66.66:15mm) to (73.32:15mm);
[e:coloredthin,color=BostonUniversityRed] (66.66:15mm) to (73.32:15mm);
[e:main,gray] (73.32:15mm) to (80.01:15mm);
[e:coloredborder] (80.01:15mm) to (86.68:15mm);
[e:coloredthin,color=BostonUniversityRed] (80.01:15mm) to (86.68:15mm);
[e:main,myGreen] (86.68:15mm) to (93.35:15mm);
[e:coloredborder] (93.35:15mm) to (100.01:15mm);
[e:coloredthin,color=BostonUniversityRed] (93.35:15mm) to (100.01:15mm);
[e:main,gray] (100.01:15mm) to (106.68:15mm);
[e:coloredborder] (106.68:15mm) to (113.34:15mm);
[e:coloredthin,color=BostonUniversityRed] (106.68:15mm) to (113.34:15mm);
[e:main,gray] (113.34:15mm) to (120:15mm);

[e:main,blue,densely dashed,bend right=90] (80.01:15mm) to (100.01:15mm);

[e:coloredborder,bend right=10] (0:15mm) to (20:15mm);
[e:coloredthin,red,bend right=10] (0:15mm) to (20:15mm);
[e:main,gray,bend right=10] (20:15mm) to (40:15mm);
[e:coloredborder,bend right=10] (40:15mm) to (60:15mm);
[e:coloredthin,red,bend right=10] (40:15mm) to (60:15mm);

[e:main,gray,bend right=10] (120:15mm) to (140:15mm);
[e:coloredborder,bend right=10] (140:15mm) to (160:15mm);
[e:coloredthin,red,bend right=10] (140:15mm) to (160:15mm);
[e:main,gray,bend right=10] (160:15mm) to (180:15mm);

[e:coloredborder,bend right=10] (180:15mm) to (200:15mm);
[e:coloredthin,red,bend right=10] (180:15mm) to (200:15mm);
[e:main,gray,bend right=10] (200:15mm) to (220:15mm);
[e:coloredborder,bend right=10] (220:15mm) to (240:15mm);
[e:coloredthin,red,bend right=10] (220:15mm) to (240:15mm);

[e:main,gray,bend right=10] (240:15mm) to (260:15mm);
[e:coloredborder,bend right=10] (260:15mm) to (280:15mm);
[e:coloredthin,red,bend right=10] (260:15mm) to (280:15mm);
[e:main,gray,bend right=10] (280:15mm) to (300:15mm);

[e:main,gray,bend right=10] (300:15mm) to (320:15mm);
[e:coloredborder,bend right=10] (320:15mm) to (340:15mm);
[e:coloredthin,red,bend right=10] (320:15mm) to (340:15mm);
[e:main,gray,bend right=10] (340:15mm) to (0:15mm);

[e:coloredborder] (180:7mm) – (0:7mm);
[e:coloredthin,color=BostonUniversityRed] (180:7mm) – (0:7mm);
[e:main,gray] (180:15mm) – (180:7mm);
[e:main,gray] (0:15mm) – (0:7mm);

[e:coloredborder] (240:7mm) – (60:7mm);
[e:coloredthin,color=BostonUniversityRed] (240:7mm) – (60:7mm);
[e:main,gray] (240:15mm) – (240:7mm);
[e:main,gray] (60:15mm) – (60:7mm);

[e:coloredborder] (300:15mm) – (300:7mm);
[e:coloredthin,color=BostonUniversityRed] (300:15mm) – (300:7mm);
[e:coloredborder] (120:15mm) – (120:7mm);
[e:coloredthin,color=BostonUniversityRed] (120:15mm) – (120:7mm);
[e:main,gray] (300:7mm) – (120:7mm);

[v:marked] () at (113.34:15mm);
[v:marked] () at (66.66:15mm);
[v:marked] () at (120:15mm);
[v:marked] () at (300:15mm);
[v:marked] () at (280:15mm);
[v:marked] () at (180:15mm);

in 0,2,4

[v:mainempty] () at (*60:15mm);
[v:maingray] () at (*60:7mm);

in 1,3,5

[v:main] () at (*60:15mm);
[v:mainemptygray] () at (*60:7mm);

[v:maingray] () at (20:15mm);
[v:maingray] () at (140:15mm);
[v:maingray] () at (220:15mm);
[v:maingray] () at (260:15mm);
[v:maingray] () at (340:15mm);

[v:mainemptygray] () at (66.66:15mm);
[v:maingray] () at (73.32:15mm);
[v:mainemptygreen] () at (80.01:15mm);
[v:maingreen] () at (86.68:15mm);
[v:mainemptygreen] () at (93.35:15mm);
[v:maingreen] () at (100.01:15mm);
[v:mainemptygray] () at (106.68:15mm);
[v:maingray] () at (113.34:15mm);

[v:mainemptygray] () at (40:15mm);
[v:mainemptygray] () at (160:15mm);
[v:mainemptygray] () at (200:15mm);
[v:mainemptygray] () at (280:15mm);
[v:mainemptygray] () at (320:15mm);

() at (0:18mm)$b_{1}$;
() at (60:17mm)$u$;
() at (120:17mm)$v$;
() at (180:18mm)$a_{2}$;
() at (240:17mm)$b_{2}$;
() at (300:18mm)$a_{1}$;

[blue] () at (90:18mm)$C$;

[e:main,myGreen,bend left=40] (113.34:15mm) to (280:15mm);
[e:main,blue,bend right=15] (66.66:15mm) to (0:7mm);
[e:marker,BrightUbe,bend left=40] (113.34:15mm) to (280:15mm);
[e:marker,BrightUbe,bend right=15] (66.66:15mm) to (0:7mm);
[e:marker,BrightUbe] (0:7mm) – (180:15mm);
[e:marker,BrightUbe] (120:15mm) – (300:15mm);

[e:marker,BrightUbe,bend right=28] (180:15mm) to (240:15mm) to (300:15mm) to (0:15mm) to (60:15mm) to (120:15mm);

[e:main,gray] (60:15mm) to (66.66:15mm);
[e:coloredborder] (66.66:15mm) to (73.32:15mm);
[e:coloredthin,color=BostonUniversityRed] (66.66:15mm) to (73.32:15mm);
[e:main,gray] (73.32:15mm) to (80.01:15mm);
[e:coloredborder] (80.01:15mm) to (86.68:15mm);
[e:coloredthin,color=BostonUniversityRed] (80.01:15mm) to (86.68:15mm);
[e:main,myGreen] (86.68:15mm) to (93.35:15mm);
[e:coloredborder] (93.35:15mm) to (100.01:15mm);
[e:coloredthin,color=BostonUniversityRed] (93.35:15mm) to (100.01:15mm);
[e:main,gray] (100.01:15mm) to (106.68:15mm);
[e:coloredborder] (106.68:15mm) to (113.34:15mm);
[e:coloredthin,color=BostonUniversityRed] (106.68:15mm) to (113.34:15mm);
[e:main,gray] (113.34:15mm) to (120:15mm);

[e:main,blue,densely dashed,bend right=90] (80.01:15mm) to (100.01:15mm);

[e:coloredborder,bend right=10] (0:15mm) to (20:15mm);
[e:coloredthin,red,bend right=10] (0:15mm) to (20:15mm);
[e:main,gray,bend right=10] (20:15mm) to (40:15mm);
[e:coloredborder,bend right=10] (40:15mm) to (60:15mm);
[e:coloredthin,red,bend right=10] (40:15mm) to (60:15mm);

[e:main,gray,bend right=10] (120:15mm) to (140:15mm);
[e:coloredborder,bend right=10] (140:15mm) to (160:15mm);
[e:coloredthin,red,bend right=10] (140:15mm) to (160:15mm);
[e:main,gray,bend right=10] (160:15mm) to (180:15mm);

[e:coloredborder,bend right=10] (180:15mm) to (200:15mm);
[e:coloredthin,red,bend right=10] (180:15mm) to (200:15mm);
[e:main,gray,bend right=10] (200:15mm) to (220:15mm);
[e:coloredborder,bend right=10] (220:15mm) to (240:15mm);
[e:coloredthin,red,bend right=10] (220:15mm) to (240:15mm);

[e:main,gray,bend right=10] (240:15mm) to (260:15mm);
[e:coloredborder,bend right=10] (260:15mm) to (280:15mm);
[e:coloredthin,red,bend right=10] (260:15mm) to (280:15mm);
[e:main,gray,bend right=10] (280:15mm) to (300:15mm);

[e:main,gray,bend right=10] (300:15mm) to (320:15mm);
[e:coloredborder,bend right=10] (320:15mm) to (340:15mm);
[e:coloredthin,red,bend right=10] (320:15mm) to (340:15mm);
[e:main,gray,bend right=10] (340:15mm) to (0:15mm);

[e:coloredborder] (180:7mm) – (0:7mm);
[e:coloredthin,color=BostonUniversityRed] (180:7mm) – (0:7mm);
[e:main,gray] (180:15mm) – (180:7mm);
[e:main,gray] (0:15mm) – (0:7mm);

[e:coloredborder] (240:7mm) – (60:7mm);
[e:coloredthin,color=BostonUniversityRed] (240:7mm) – (60:7mm);
[e:main,gray] (240:15mm) – (240:7mm);
[e:main,gray] (60:15mm) – (60:7mm);

[e:coloredborder] (300:15mm) – (300:7mm);
[e:coloredthin,color=BostonUniversityRed] (300:15mm) – (300:7mm);
[e:coloredborder] (120:15mm) – (120:7mm);
[e:coloredthin,color=BostonUniversityRed] (120:15mm) – (120:7mm);
[e:main,gray] (300:7mm) – (120:7mm);

[v:marked] () at (113.34:15mm);
[v:marked] () at (66.66:15mm);
[v:marked] () at (100:11mm);
[v:marked] () at (80:11mm);
[v:marked] () at (0:7mm);
[v:marked] () at (200:15mm);

in 0,2,4

[v:mainempty] () at (*60:15mm);
[v:maingray] () at (*60:7mm);

in 1,3,5

[v:main] () at (*60:15mm);
[v:mainemptygray] () at (*60:7mm);

[v:maingray] () at (20:15mm);
[v:maingray] () at (140:15mm);
[v:maingray] () at (220:15mm);
[v:maingray] () at (260:15mm);
[v:maingray] () at (340:15mm);

[v:mainemptygray] () at (66.66:15mm);
[v:maingray] () at (73.32:15mm);
[v:mainemptygreen] () at (80.01:15mm);
[v:maingreen] () at (86.68:15mm);
[v:mainemptygreen] () at (93.35:15mm);
[v:maingreen] () at (100.01:15mm);
[v:mainemptygray] () at (106.68:15mm);
[v:maingray] () at (113.34:15mm);

[v:mainemptygray] () at (40:15mm);
[v:mainemptygray] () at (160:15mm);
[v:mainemptygray] () at (200:15mm);
[v:mainemptygray] () at (280:15mm);
[v:mainemptygray] () at (320:15mm);

[v:main] () at (80:11mm);
[v:mainempty] () at (100:11mm);

() at (0:18mm)$b_{1}$;
() at (60:17mm)$u$;
() at (120:17mm)$v$;
() at (180:18mm)$a_{2}$;
() at (240:17mm)$b_{2}$;
() at (300:18mm)$a_{1}$;

[blue] () at (90:18mm)$C$;

[e:marker,BrightUbe,bend right=15] (80:11mm) to (66.66:15mm);
[e:marker,BrightUbe,bend right=15] (100:11mm) to (0:7mm);
[e:marker,BrightUbe,bend left=20] (100:11mm) to (113.34:15mm);
[e:marker,BrightUbe,bend left=30] (80:11mm) to (200:15mm);
[e:marker,BrightUbe] (80:11mm) – (100:11mm);

[e:marker,BrightUbe] (0:15mm) – (180:15mm);
[e:marker,BrightUbe] (120:15mm) – (300:15mm);

[e:marker,BrightUbe,bend right=28] (0:15mm) to (60:15mm) to (120:15mm);
[e:marker,BrightUbe,bend right=28] (180:15mm) to (240:15mm) to (300:15mm);

[e:main,gray] (60:15mm) to (66.66:15mm);
[e:coloredborder] (66.66:15mm) to (73.32:15mm);
[e:coloredthin,color=BostonUniversityRed] (66.66:15mm) to (73.32:15mm);
[e:main,gray] (73.32:15mm) to (80.01:15mm);
[e:coloredborder] (80.01:15mm) to (86.68:15mm);
[e:coloredthin,color=BostonUniversityRed] (80.01:15mm) to (86.68:15mm);
[e:main,myGreen] (86.68:15mm) to (93.35:15mm);
[e:coloredborder] (93.35:15mm) to (100.01:15mm);
[e:coloredthin,color=BostonUniversityRed] (93.35:15mm) to (100.01:15mm);
[e:main,gray] (100.01:15mm) to (106.68:15mm);
[e:coloredborder] (106.68:15mm) to (113.34:15mm);
[e:coloredthin,color=BostonUniversityRed] (106.68:15mm) to (113.34:15mm);
[e:main,gray] (113.34:15mm) to (120:15mm);

[e:main,blue,densely dashed,bend right=90] (80.01:15mm) to (100.01:15mm);

[e:coloredborder,bend right=10] (0:15mm) to (20:15mm);
[e:coloredthin,red,bend right=10] (0:15mm) to (20:15mm);
[e:main,gray,bend right=10] (20:15mm) to (40:15mm);
[e:coloredborder,bend right=10] (40:15mm) to (60:15mm);
[e:coloredthin,red,bend right=10] (40:15mm) to (60:15mm);

[e:main,gray,bend right=10] (120:15mm) to (140:15mm);
[e:coloredborder,bend right=10] (140:15mm) to (160:15mm);
[e:coloredthin,red,bend right=10] (140:15mm) to (160:15mm);
[e:main,gray,bend right=10] (160:15mm) to (180:15mm);

[e:coloredborder,bend right=10] (180:15mm) to (200:15mm);
[e:coloredthin,red,bend right=10] (180:15mm) to (200:15mm);
[e:main,gray,bend right=10] (200:15mm) to (220:15mm);
[e:coloredborder,bend right=10] (220:15mm) to (240:15mm);
[e:coloredthin,red,bend right=10] (220:15mm) to (240:15mm);

[e:main,gray,bend right=10] (240:15mm) to (260:15mm);
[e:coloredborder,bend right=10] (260:15mm) to (280:15mm);
[e:coloredthin,red,bend right=10] (260:15mm) to (280:15mm);
[e:main,gray,bend right=10] (280:15mm) to (300:15mm);

[e:main,gray,bend right=10] (300:15mm) to (320:15mm);
[e:coloredborder,bend right=10] (320:15mm) to (340:15mm);
[e:coloredthin,red,bend right=10] (320:15mm) to (340:15mm);
[e:main,gray,bend right=10] (340:15mm) to (0:15mm);

[e:coloredborder] (180:7mm) – (0:7mm);
[e:coloredthin,color=BostonUniversityRed] (180:7mm) – (0:7mm);
[e:main,gray] (180:15mm) – (180:7mm);
[e:main,gray] (0:15mm) – (0:7mm);

[e:coloredborder] (240:7mm) – (60:7mm);
[e:coloredthin,color=BostonUniversityRed] (240:7mm) – (60:7mm);
[e:main,gray] (240:15mm) – (240:7mm);
[e:main,gray] (60:15mm) – (60:7mm);

[e:coloredborder] (300:15mm) – (300:7mm);
[e:coloredthin,color=BostonUniversityRed] (300:15mm) – (300:7mm);
[e:coloredborder] (120:15mm) – (120:7mm);
[e:coloredthin,color=BostonUniversityRed] (120:15mm) – (120:7mm);
[e:main,gray] (300:7mm) – (120:7mm);

[e:coloredborder] (80:11mm) – (100:11mm);
[e:coloredthin,color=BostonUniversityRed] (80:11mm) – (100:11mm);

[e:main,blue,bend right=15] (80:11mm) to (66.66:15mm); [e:main,blue,bend right=15] (100:11mm) to (0:7mm);
[e:main,myGreen,bend left=20] (100:11mm) to (113.34:15mm);
[e:main,myGreen,bend left=30] (80:11mm) to (200:15mm);

[v:marked] () at (113.34:15mm);
[v:marked] () at (66.66:15mm);
[v:marked] () at (100:11mm);
[v:marked] () at (80:11mm);
[v:marked] () at (0:7mm);
[v:marked] () at (280:15mm);

in 0,2,4

[v:mainempty] () at (*60:15mm);
[v:maingray] () at (*60:7mm);

in 1,3,5

[v:main] () at (*60:15mm);
[v:mainemptygray] () at (*60:7mm);

[v:maingray] () at (20:15mm);
[v:maingray] () at (140:15mm);
[v:maingray] () at (220:15mm);
[v:maingray] () at (260:15mm);
[v:maingray] () at (340:15mm);

[v:mainemptygray] () at (66.66:15mm);
[v:maingray] () at (73.32:15mm);
[v:mainemptygreen] () at (80.01:15mm);
[v:maingreen] () at (86.68:15mm);
[v:mainemptygreen] () at (93.35:15mm);
[v:maingreen] () at (100.01:15mm);
[v:mainemptygray] () at (106.68:15mm);
[v:maingray] () at (113.34:15mm);

[v:mainemptygray] () at (40:15mm);
[v:mainemptygray] () at (160:15mm);
[v:mainemptygray] () at (200:15mm);
[v:mainemptygray] () at (280:15mm);
[v:mainemptygray] () at (320:15mm);

[v:main] () at (80:11mm);
[v:mainempty] () at (100:11mm);

() at (0:18mm)$b_{1}$;
() at (60:17mm)$u$;
() at (120:17mm)$v$;
() at (180:18mm)$a_{2}$;
() at (240:17mm)$b_{2}$;
() at (300:18mm)$a_{1}$;

[blue] () at (90:18mm)$C$;

[e:marker,BrightUbe,bend right=15] (80:11mm) to (66.66:15mm);
[e:marker,BrightUbe,bend right=15] (100:11mm) to (0:7mm);
[e:marker,BrightUbe,bend left=20] (100:11mm) to (113.34:15mm);
[e:marker,BrightUbe,bend right=15] (80:11mm) to (280:15mm);
[e:marker,BrightUbe] (80:11mm) – (100:11mm);

[e:marker,BrightUbe] (0:15mm) – (180:15mm);
[e:marker,BrightUbe] (120:15mm) – (300:15mm);

[e:marker,BrightUbe,bend right=28] (0:15mm) to (60:15mm) to (120:15mm);
[e:marker,BrightUbe,bend right=28] (180:15mm) to (240:15mm) to (300:15mm);

[e:main,gray] (60:15mm) to (66.66:15mm);
[e:coloredborder] (66.66:15mm) to (73.32:15mm);
[e:coloredthin,color=BostonUniversityRed] (66.66:15mm) to (73.32:15mm);
[e:main,gray] (73.32:15mm) to (80.01:15mm);
[e:coloredborder] (80.01:15mm) to (86.68:15mm);
[e:coloredthin,color=BostonUniversityRed] (80.01:15mm) to (86.68:15mm);
[e:main,myGreen] (86.68:15mm) to (93.35:15mm);
[e:coloredborder] (93.35:15mm) to (100.01:15mm);
[e:coloredthin,color=BostonUniversityRed] (93.35:15mm) to (100.01:15mm);
[e:main,gray] (100.01:15mm) to (106.68:15mm);
[e:coloredborder] (106.68:15mm) to (113.34:15mm);
[e:coloredthin,color=BostonUniversityRed] (106.68:15mm) to (113.34:15mm);
[e:main,gray] (113.34:15mm) to (120:15mm);

[e:main,blue,densely dashed,bend right=90] (80.01:15mm) to (100.01:15mm);

[e:coloredborder,bend right=10] (0:15mm) to (20:15mm);
[e:coloredthin,red,bend right=10] (0:15mm) to (20:15mm);
[e:main,gray,bend right=10] (20:15mm) to (40:15mm);
[e:coloredborder,bend right=10] (40:15mm) to (60:15mm);
[e:coloredthin,red,bend right=10] (40:15mm) to (60:15mm);

[e:main,gray,bend right=10] (120:15mm) to (140:15mm);
[e:coloredborder,bend right=10] (140:15mm) to (160:15mm);
[e:coloredthin,red,bend right=10] (140:15mm) to (160:15mm);
[e:main,gray,bend right=10] (160:15mm) to (180:15mm);

[e:coloredborder,bend right=10] (180:15mm) to (200:15mm);
[e:coloredthin,red,bend right=10] (180:15mm) to (200:15mm);
[e:main,gray,bend right=10] (200:15mm) to (220:15mm);
[e:coloredborder,bend right=10] (220:15mm) to (240:15mm);
[e:coloredthin,red,bend right=10] (220:15mm) to (240:15mm);

[e:main,gray,bend right=10] (240:15mm) to (260:15mm);
[e:coloredborder,bend right=10] (260:15mm) to (280:15mm);
[e:coloredthin,red,bend right=10] (260:15mm) to (280:15mm);
[e:main,gray,bend right=10] (280:15mm) to (300:15mm);

[e:main,gray,bend right=10] (300:15mm) to (320:15mm);
[e:coloredborder,bend right=10] (320:15mm) to (340:15mm);
[e:coloredthin,red,bend right=10] (320:15mm) to (340:15mm);
[e:main,gray,bend right=10] (340:15mm) to (0:15mm);

[e:coloredborder] (180:7mm) – (0:7mm);
[e:coloredthin,color=BostonUniversityRed] (180:7mm) – (0:7mm);
[e:main,gray] (180:15mm) – (180:7mm);
[e:main,gray] (0:15mm) – (0:7mm);

[e:coloredborder] (240:7mm) – (60:7mm);
[e:coloredthin,color=BostonUniversityRed] (240:7mm) – (60:7mm);
[e:main,gray] (240:15mm) – (240:7mm);
[e:main,gray] (60:15mm) – (60:7mm);

[e:coloredborder] (300:15mm) – (300:7mm);
[e:coloredthin,color=BostonUniversityRed] (300:15mm) – (300:7mm);
[e:coloredborder] (120:15mm) – (120:7mm);
[e:coloredthin,color=BostonUniversityRed] (120:15mm) – (120:7mm);
[e:main,gray] (300:7mm) – (120:7mm);

[e:coloredborder] (80:11mm) – (100:11mm);
[e:coloredthin,color=BostonUniversityRed] (80:11mm) – (100:11mm);

[e:main,blue,bend right=15] (80:11mm) to (66.66:15mm); [e:main,blue,bend right=15] (100:11mm) to (0:7mm);
[e:main,myGreen,bend left=20] (100:11mm) to (113.34:15mm);
[e:main,myGreen,bend right=15] (80:11mm) to (280:15mm);

The construction of the new conformal $K_{3,3}$-bisubdivision in the third case of the proof of <ref>.

So whenever we find both a $V_1$-jump and a $V_2$-jump in $L$, we are able to find a conformal bisubdivision $L'$ of $K_{3,3}$ with a bisubdivided edge $P'$ that contains all of $C$ but is shorter than $P$ in the previous bisubdivision.
Thus by choosing $L$ with minimal $P$, we still find a non-trivial tight cut as in the proofs of <ref>, but neither of these tight cuts may yield a $V_1$-jump.
Hence we must be able to construct a conformal bisubdivision of $K_{3,3}$ that splits $C$.

With this we are ready to close this section with the proof of <ref>.

Suppose $B$ is a counterexample, so there exists a $4$-cycle $C$ in $B$ such that $C$ is not a subgraph of a conformal $K_{3,3}$-bisubdivision.
By <ref> this means that there is no conformal cross over $C$ in $B$ and thus, by <ref> there exists a conformal bisubdivision $L$ of $K_{3,3}$ that splits $C$.
As we have seen in <ref> we may choose $L$ such that one of the degree three vertices in $L$ belongs to $C$, let us call that vertex $u$.
Let $P_1$, $P_2$, and $P_3$ be the bisubdivided edges of $L$ that have $u$ as an endpoint and let $v_i$ be the other endpoint of $P_i$ for all $i\in [1,3]$.
Let $Y\coloneqq \bigcup_{i=1}^3\V{P_i-v_i}$ and let us choose $L$ among all conformal bisubdivisions of $K_{3,3}$ in $B$ that split $C$ to be one where $\Abs{Y}$ is minimal.
As $L$ splits $C$ we still have $\Abs{Y\cap\V{C}}\geq 3$ and $\Abs{\V{L}\setminus Y}\geq 3$ and thus $Y$ is, as we have seen before, a non-trivial tight cut whose majority is exactly the colour class $u$ belongs to.
Without loss of generality let us assume the minority of $Y$ to be in $V_1$.
Observe that $C\cap L$ forms an $M$-conformal path that must contain internal vertices of two different bisubdivided edges of $L$.
By <ref> there must exist an internally $M$-conformal path $F$ that has one endpoint in $Y\cap V_1$ and the other one in $\Vi{2}{L-Y}$ such that $F$ is internally disjoint from $L$.
Recall the constructions illustrated in <ref> and suppose the endpoint of $F$ in $Y$ is an interior vertex of $C\cap Y$.
If this is the case, we find a conformal bisubdivision $L'$ of $K_{3,3}$ in which $ab$ and $a'b'$ belong to two different bisubdivided edges which do not share an endpoint.
By <ref> this means we find a conformal bisubdivision of $K_{3,3}$ which contains $C$ as a subgraph, contradicting $B$ being a counterexample.
Hence $F$ cannot contain an inner vertex of $C\cap L$.
But in this case, we can find a conformal $K_{3,3}$-bisubdivision $L'$ that splits $C$ such that $Y'$, which is defined for $L'$ in the same way as $Y$ is defined for $L$, contains fewer vertices than $Y$ which contradicts our choice of $L$.
So either way we reach a contradiction and thus there cannot be a counterexample to our claim.

§ AN ALGORITHM FOR $2$-MLP

To obtain an algorithmic solution for $2$-MLP, we use <ref> together with <ref>.
On a high level, we run into the following problems:
First, we do not know for which perfect matching $M$ of $B$ we might be able to find a solution for $2$-MLP and since there is a potentially exponential number of perfect matchings in $B$ it clearly does not suffice to simply test all of them.
Indeed, such an approach is doomed from the beginning since trying to solve $2$-MLP for a fixed perfect matching is equivalent to the Directed $2$-Disjoint Paths Problem.
So we take a slightly different approach.
Let $a_1,a_2,b_1,b_2$ be the four vertices of an instance of $2$-MLP.
Let $\Abs{\V{B}}=n$, then $B$ contains $\frac{n}{2}$ vertices of each colour.
For each $x\in\Set{a_1,a_2,b_1,b_2}$ we may choose from among the $\frac{n}{2}$ vertices of the opposite colour in order to find a neighbour that might be matched to $x$ by some perfect matching of $B$.
In total this means there are at most

\begin{align*}
\end{align*}

many choices of edges that might cover our four terminal vertices in a perfect matching of $B$.
Let $F\subseteq\E{B}$ be a set of at most four edges such that each vertex from among $a_1,a_2,b_1$, and $b_2$ is covered by an edge of $F$.
Next we need to decide whether $F$ is contained in a perfect matching of $B$, which can be done by the Hopcroft-Karp algorithm in time $\Fkt{\mathcal{O}}{n^{\frac{5}{2}}}$ [7].
In case such a perfect matching exists, we then alter the graph $B$ locally which takes up constant time.
The main concern of this section is to introduce this local construction and to show that the existence of a conformal cross over a well-chosen $4$-cycle certifies the existence of the desired linkage in a way that makes use of the matching edges in $F$.
The key to deciding whether a conformal cross over our $4$-cycle exists is <ref> in combination with <ref>.
In total, this approach decides $2$-MLP in time $\Fkt{\mathcal{O}}{n^5}$.

Let $B$ be a bipartite graph with a perfect matching, $F\subseteq\E{B}$ and $X\subseteq\V{B}$.
The set $F$ is said to be an $X$-cover, if every edge in $F$ contains a vertex of $X$ and every vertex in $X$ is covered by an edge of $F$.
If $F$ is an extendible set of edges in $B$ and $M$ is a perfect matching $B$ with $F\subseteq M$, $M$ is said to extend $F$.
From the discussion above it is clear that there are $\Fkt{\mathcal{O}}{\Abs{\V{B}}^2}$ many $X$-covers in $B$ for any set $X\subseteq\V{B}$ with $\Abs{X\cap V_1}=\Abs{X\cap V_2}=2$.
Given distinct vertices $a_1,a_2\in V_1$, $b_1,b_2\in V_2$, and an extendible $\Set{a_1,a_2,b_1,b_2}$-cover $F\subseteq\E{B}$ we say that $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$ if there exists a perfect matching $M$ of $B$ that extends $F$ such that there are two disjoint internally $M$-conformal paths $P_1$ and $P_2$ such that $P_i$ has endpoints $a_i$ and $b_i$ for each $i\in[1,2]$.

Let $B$ be a bipartite graph with a perfect matching, $a_1,a_2\in V_1$ and $b_1,b_2\in V_2$ four distinct vertices of $B$, and $F$ an extendible $\Set{a_1,a_2,b_1,b_2}$-cover of size four.
Let $ua_2,vb_1\in F$.
We define the following transformation of $B$ with respect to $F$, $\Brace{a_1,a_2}$, and $\Brace{b_1,b_2}$.

\begin{align*}
\MLPInstance{3}{B,F,\Set{a_1,a_2,b_1,b_2}}&\coloneqq B-u-v+a_2b_1\\
\MLPCover{3}{B,F,\Set{a_1,a_2,b_1,b_2}}&\coloneqq \Brace{F\setminus\Set{ua_2,vb_1}}\cup\Set{a_2b_1}
\end{align*}

Let $B$ be a bipartite graph with a perfect matching, $a_1,a_2\in V_1$ and $b_1,b_2\in V_2$ four distinct vertices of $B$, and $F$ an extendible $\Set{a_1,a_2,b_1,b_2}$-cover of size four.
Then $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$ if and only if $\MLPInstance{3}{B,F,\Set{a_1,a_2,b_1,b_2}}$ is a $\MLPCover{3}{B,F,\Set{a_1,a_2,b_1,b_2}}$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$.

If $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$ there is a perfect matching $M$ that extends $F$ such that there exist disjoint and internally $M$-conformal paths $P_1$ and $P_2$ where $P_i$ has endpoints $a_i$ and $b_i$ for each $i\in[1,2]$.
Let $ua_2,vb_1\in F$, then $\Set{u,v}\cap\Brace{\V{P_1}\cup\V{P_2}}=\emptyset$.
Let us add the edges $uv$ and $a_2b_1$ to $B$, then $C\coloneqq ua_2b_1vu$ is an $M$-conformal $4$-cycle in $B$.
We set $M'\coloneqq \Brace{M'\setminus\E{C}}\cup\Set{uv,a_2b_1}$, then $P_1$ and $P_2$ are internally $M'$-conformal paths that still exist in $\MLPInstance{3}{B,F,\Set{a_1,a_2,b_1,b_2}}$ and $M'\setminus\Set{uv}$ is a perfect matching of $\MLPInstance{3}{B,F,\Set{a_1,a_2,b_1,b_2}}$ that extends $\MLPCover{3}{B,F,\Set{a_1,a_2,b_1,b_2}}$.
Hence $\MLPInstance{3}{B,F,\Set{a_1,a_2,b_1,b_2}}$ is a $\MLPCover{3}{B,F,\Set{a_1,a_2,b_1,b_2}}$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$.

Now assume that $\MLPInstance{3}{B,F,\Set{a_1,a_2,b_1,b_2}}$ is a $\MLPCover{3}{B,F,\Set{a_1,a_2,b_1,b_2}}$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$.
As before let $M$ be a perfect matching extending $\MLPCover{3}{B,F,\Set{a_1,a_2,b_1,b_2}}$ and let $P_1$, $P_2$ be the corresponding internally $M$-conformal paths.
Let $ua_2,vb_1\in F$, then $M\cup\Set{uv}$ is a perfect matching of $B+a_2b_1+uv$ and $C\coloneqq ua_2b_1vu$ is an $M\cup\Set{uv}$-conformal $4$-cycle in $B+a_2b_1+uv$.
We set $M'\coloneqq \Brace{M'\setminus\E{C}}\cup\Set{ua_2,vb_1}$, then $P_1$ and $P_2$ are internally $M'$-conformal paths in $B+a_2b_1+uv$ that still exist in $B$ and $M'$ is also a perfect matching of $B$.
Thus $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$.

Let $B$ be a bipartite graph with a perfect matching, $a_1,a_2\in V_1$ and $b_1,b_2\in V_2$ four distinct vertices of $B$, $S\coloneqq\Set{a_1,a_2,b_1,b_2}$, and $F$ an extendible $S$-cover of size at least three such that $a_2b_1\in F$ if and only if $\Abs{F}=3$.
Let $ua_1,vb_2\in F$.
We define the following transformation of $B$ with respect to $F$, $\Brace{a_1,a_2}$, and $\Brace{b_1,b_2}$.
If $\Abs{F}=3$ use the following construction:

\begin{align*}
\MLPInstance{2}{B,F,S}&\coloneqq B-u-v+a_1b_2\\
\MLPCover{2}{B,F,S}&\coloneqq \Brace{F\setminus\Set{ua_1,vb_2}}\cup\Set{a_1b_2}
\end{align*}

Otherwise, we can first obtain an instance where our extendible cover has size three as required:

\begin{align*}
\MLPInstance{2}{B,F,S}&\coloneqq\MLPInstance{2}{\MLPInstance{3}{B,F,S},\MLPCover{3}{B,F,S},S}\\
\MLPCover{2}{B,F,S}&\coloneqq \MLPCover{2}{\MLPInstance{3}{B,F,S},\MLPCover{3}{B,F,S},S}
\end{align*}

Let $B$ be a bipartite graph with a perfect matching, $a_1,a_2\in V_1$ and $b_1,b_2\in V_2$ four distinct vertices of $B$, $S\coloneqq\Set{a_1,a_2,b_1,b_2}$, and $F$ an extendible $S$-cover of size at least three.
Then $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$ if and only if $\MLPInstance{2}{B,F,S}$ is a $\MLPCover{2}{B,F,S}$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$.

We only have to consider the case $\Abs{F}=3$, since the case $\Abs{F}=4$ follows, by <ref>, with the same arguments.

If $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$ there is a perfect matching $M$ that extends $F$ such that there exist disjoint and internally $M$-conformal paths $P_1$ and $P_2$ where $P_i$ has endpoints $a_i$ and $b_i$ for each $i\in[1,2]$.
Let $ua_1,vb_2\in F$, then $\Set{u,v}\cap\Brace{\V{P_1}\cup\V{P_2}}=\emptyset$.
Let us add the edges $uv$ and $a_1b_2$ to $B$, then $C\coloneqq ua_1b_2vu$ is an $M$-conformal $4$-cycle in $B$.
We set $M'\coloneqq \Brace{M'\setminus\E{C}}\cup\Set{uv,a_1b_2}$, then $P_1$ and $P_2$ are internally $M'$-conformal paths that still exist in $\MLPInstance{2}{B,F,S}$ and $M'\setminus\Set{uv}$ is a perfect matching of $\MLPInstance{2}{B,F,S}$ that extends $\MLPCover{2}{B,F,S}$.
Hence $\MLPInstance{2}{B,F,S}$ is a $\MLPCover{2}{B,F,S}$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$.

Now assume that $\MLPInstance{2}{B,F,S}$ is a $\MLPCover{2}{B,F,S}$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$.
As before let $M$ be a perfect matching extending $\MLPCover{2}{B,F,S}$ and let $P_1$, $P_2$ be the corresponding internally $M$-conformal paths.
Let $ua_1,vb_2\in F$, then $M\cup\Set{uv}$ is a perfect matching of $B+a_1b_2+uv$ and $C\coloneqq ua_1b_2vu$ is an $M\cup\Set{uv}$-conformal $4$-cycle in $B+a_1b_2+uv$.
We set $M'\coloneqq \Brace{M'\setminus\E{C}}\cup\Set{ua_1,vb_2}$, then $P_1$ and $P_2$ are internally $M'$-conformal paths in $B+a_1b_2+uv$ that still exist in $B$ and $M'$ is also a perfect matching of $B$.
Thus $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$.

Let $B$ be a bipartite graph with a perfect matching, $a_1,a_2\in V_1$ and $b_1,b_2\in V_2$ four distinct vertices of $B$, $S\coloneqq\Set{a_1,a_2,b_1,b_2}$, and $F$ an extendible $S$-cover such that $a_2b_1\in F$ if and only if $\Abs{F}\leq 3$.
We define the following transformation of $B$ with respect to $F$, $\Brace{a_1,a_2}$, and $\Brace{b_1,b_2}$.
If $\Abs{F}=2$, and therefore $F=\Set{a_1b_2,a_2b_1}$, use the following construction:
Let $x,y$ be two distinct vertices that do not belong to $B$.

\begin{align*}
\MLPInstance{}{B,F,S}&\coloneqq B+x+y+\Set{xy,xb_1,xb_2,ya_1,ya_2}
\end{align*}

Otherwise, we can first obtain an instance where our extendible cover has size two as required above:

\begin{align*}
\MLPInstance{}{B,F,S}&\coloneqq\MLPInstance{}{\MLPInstance{2}{B,F,S},\MLPCover{2}{B,F,S},S}
\end{align*}

In either case let $\MLPCycle{B,F,S}$ be the $4$-cycle $a_1yxb_2$.

Let $B$ be a bipartite graph with a perfect matching, $a_1,a_2\in V_1$ and $b_1,b_2\in V_2$ four distinct vertices of $B$, $S\coloneqq\Set{a_1,a_2,b_1,b_2}$, and $F$ an extendible $S$-cover such that $a_2b_1\in F$ if and only if $\Abs{F}\leq 3$.
Then $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$ if and only if there exists a conformal cross over $\MLPCycle{B,F,S}$ in $\MLPInstance{}{B,F,S}$.

In case $\Abs{F}\geq 3$ we may replace $B$ and $F$ by $\MLPInstance{2}{B,F,S}$ and $\MLPCover{2}{B,F,S}$ without influencing the fact whether $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$ by <ref>.
Hence, without loss of generality, we may assume $\Abs{F}=2$.

If $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$ there is a perfect matching $M$ that extends $F$ such that there exist disjoint and internally $M$-conformal paths $P_1$ and $P_2$ where $P_i$ has endpoints $a_i$ and $b_i$ for each $i\in[1,2]$.
Then $M'\coloneqq M\cup\Set{xy}$ is a perfect matching of $\MLPInstance{}{B,F,S}$ and $P_1$, $P_2$ are internally $M'$-conformal paths in $\MLPInstance{}{B,F,S}$ that, in particular, avoid the vertices $x$ and $y$.
Hence $H\coloneqq P_1+P_2+\InducedSubgraph{\MLPInstance{}{B,F,S}}{S\cup\Set{x,y}}$ is an $M'$-conformal subgraph of $\MLPInstance{}{B,F,S}$.
It is straightforward to see that $H$ is indeed a bisubdivision of $K_{3,3}$ that contains $\MLPCycle{B,F,S}$ as a subgraph, see <ref> for an illustration.
By <ref> this means that there is a conformal cross over $\MLPCycle{B,F,S}$ in $\MLPInstance{}{B,F,S}$ and thus we are done with the forward direction.

[v:main] () at (-2,1);
() at (-2,1.3)$a_{1}$;

[v:main] () at (2,1);
() at (2,1.3)$a_{2}$;

[v:maingray] () at (0,-1);
[Amethyst] () at (0,-1.3)$y$;

[v:mainemptygray] () at (0,1);
[Amethyst] () at (0,1.3)$x$;

[v:mainempty] () at (-2,-1);
() at (-2,-1.3)$b_{2}$;

[v:mainempty] () at (2,-1);
() at (2,-1.3)$b_{1}$;

[myGreen] () at (-3,1.7)$P_{1}$;
[myGreen] () at (-3,-1.7)$P_{2}$;

[Amethyst] () at (-1,0.5)$C(B,F,S)$;

[e:marker,BrightUbe] (-2,-1) – (0,-1);
[e:marker,BrightUbe] (0,-1) – (0,1);
[e:marker,BrightUbe] (0,1) – (-2,1);
[e:marker,BrightUbe] (-2,1) – (-2,-1);

[e:main,gray] (-2,-1) – (2,-1);
[e:main,gray] (-2,1) – (2,1);

[e:coloredborder] (2,1) – (2,-1);
[e:coloredthin,color=BostonUniversityRed] (2,1) – (2,-1);
[e:coloredborder] (-2,1) – (-2,-1);
[e:coloredthin,color=BostonUniversityRed] (-2,1) – (-2,-1);
[e:coloredborder] (0,1) – (0,-1);
[e:coloredthin,color=BostonUniversityRed] (0,1) – (0,-1);

[e:main,myGreen,bend left=45] (-2,1) to (-2.6, 1.7) to (-2,2.4);
[e:main,myGreen,decorate] (-2,2.4) – (2,2.4);
[e:main,myGreen, bend left=45] (2,2.4) to (3.5,0.7) to (2,-1);

[e:main,myGreen,bend right=45] (-2,-1) to (-2.6, -1.7) to (-2,-2.4);
[e:main,myGreen] (-2,-2.4) – (2,-2.4);
[e:main,myGreen, bend right=45] (2,-2.4) to (3.5,-0.7) to (2,1);

A conformal bisubdivision of $K_{3,3}$ containing the $4$-cycle $\MLPCycle{B,F,S}$.

For the reverse direction let $P_1$ and $P_2$ be the two alternating paths that form the conformal cross over $\MLPCycle{B,F,S}$ in $\MLPInstance{}{B,F,S}$ such that $P_1$ has $a_1$ as an endpoint while $P_2$ as $b_2$ as an endpoint.
Then, in particular, $P_1$ and $P_2$ are of even length.
Since $x$ and $y$ both are of degree exactly three in $\MLPInstance{}{B,F,S}$, $P_1+P_2$ must contain all neighbours of $x$ and $y$ and thus $S\subseteq\V{P_1+P_2}$.
Since $P_1$ and $P_2$ form a conformal cross over $\MLPCycle{B,F,S}$, $H\coloneqq \MLPCycle{B,F,S}+P_1+P_2+a_2b_1$ is a conformal subgraph of $\MLPInstance{}{B,F,S}$.
Indeed, $H$ is a bisubdivision of $K_{3,3}$ and thus there exists a perfect matching $M$ of $\MLPInstance{}{B,F,S}$ such that $a_1b_2,xy,a_2b_1\in M$ and $H$ is $M$-conformal.
Let $P_1'\coloneqq a_1P_1b_1$ and $P_2'\coloneqq b_2P_2a_2$, then the $P_i'$ are disjoint and  internally $M'$-conformal paths.
Moreover, $M'\setminus\Set{xy}$ is a perfect matching of $B$ that extends $F$, and thus $B$ is a $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$.

Our goal is to reduce $2$-MLP to the detection of $K_{3,3}$-free braces.
For this we need to make sure that, in case we are dealing with a 'Yes'-instance, the bisubdivision of $K_{3,3}$ cannot vanish somehow.

Let $B$ be a bipartite matching covered graph, $\CutG{B}{X}$ a non-trivial tight cut in $B$, and $M$ a perfect matching in $B$.
If $P$ is an internally $M$-conformal path with both endpoints in $X$ but $\E{P}\cap\CutG{B}{X}\neq\emptyset$, then $\E{P}\cap\CutG{B}{X}\cap M\neq\emptyset$ and $\Abs{\E{P}\cap\CutG{B}{X}}=2$.

Let $a\in V_1$ and $b\in V_2$ be the two endpoints of $P$ and let us traverse $P$ from $a$ towards $b$.
Let $e_1$ be the first edge of $\E{P}\cap\CutG{B}{X}$ we encounter this way and let $e_2$ be the second edge.
Moreover let $x_i$ be the endpoint of $e_i$ in $\Complement{X}$ and suppose $\Set{e_1,e_2}\cap M=\emptyset$.
By choice of $e_1$ and $e_2$ the path $x_1Px_2$ lies completely in $\Complement{X}$ and is $M$-conformal.
Thus $x_1Px_2$ must be of odd length and therefore $x_1$ and $x_2$ must be of different colour.
Hence both $X\cap V_1$ and $X\cap V_2$ must have a neighbour in $\Complement{X}$, this, however, contradicts <ref>, and thus one of the two edges must be an edge of $M$.

Suppose $P$ has more than two edges in $\CutG{B}{X}$.
If the majority of $X$ is in $V_1$, then the second endpoint, say $y_2$, of $e_1$ must be a vertex of $V_1$ as well and $e_2\in M$.
In this case let $a'\coloneqq y_2$.
If on the other hand the majority of $X$ is in $V_2$, then $y_2\in V_2$ and thus $e_1\in M$ implying $e_2\notin M$.
Hence $y_2$ must be covered by an edge $e'\in M\cap\E{P}$ with second endpoint $a'$.
In either case, $a'P$ is an internally $M$-conformal path with both endpoints in $X$ and an edge in $\CutG{B}{X}$.
By the arguments above, this means that $\E{a'P}\cap\CutG{B}{X}\cap M\neq\emptyset$, but this means $\Abs{M\cap\CutG{B}{X}}\geq 2$ contradicting $\CutG{B}{X}$ being a tight cut.
Hence $\Abs{\E{P}\cap\CutG{B}{X}}=2$.

Let $B$ be a bipartite graph with a perfect matching and $H\subseteq B$ a conformal subgraph $B$ such that $\Vi{1}{H}=\Set{a_1,a_2,y}$, $\Vi{2}{H}=\Set{b_1,b_2,x}$, $\E{H}=\Set{a_1b_2,a_2b_1,xy,a_1x,a_2x,b_1y,b_2y}$, and $\DegG{B}{x}=\DegG{B}{y}=3$.
Let $C\coloneqq a_1xyb_2a_1$, then there is a conformal cross over $C$ in $B$ if and only if $B$ has a brace $J$ such that $H\subseteq J$ and $J$ contains $K_{3,3}$.

Let $S\coloneqq\Set{a_1,a_2,b_2,b_2}$.
Suppose there is a conformal cross over $C$ in $B$.
This case starts out similar to the reverse direction of the previous lemma.
Let $P_1$ and $P_2$ be the two alternating paths that form the conformal cross over $C$ in $B$ such that $P_1$ has $a_1$ as an endpoint while $P_2$ as $b_2$ as an endpoint.
Then, in particular, $P_1$ and $P_2$ are of even length.
Since $x$ and $y$ both are of degree exactly three in $B$ by our assumption, $P_1+P_2$ must contain all neighbours of $x$ and $y$ and thus $S\subseteq\V{P_1+P_2}$.
Since $P_1$ and $P_2$ form a conformal cross over $C$, $H'\coloneqq C+P_1+P_2+a_2b_1$ is a conformal subgraph of $B$.
Indeed, $H'$ is a bisubdivision of $K_{3,3}$

Let us choose $B$ to be a minimal counterexample.
In case $B$ is brace, it must contain $K_{3,3}$ since it contains a conformal bisubdivision of $K_{3,3}$ and thus we are done.
Hence we may assume that there is a non-trivial tight cut $\CutG{B}{X}$ in $B$.
If $X$, or $\Complement{X}$, is disjoint from $H'$, one of the two tight cut contractions of $\CutG{B}{X}$, let us call it $B'$, still contains $H'$ as a conformal subgraph and by choice of $B$, the assertion holds true for $B'$ and we find a brace $J$ of $B'$ as desired.
By <ref>, this means that $J$ is a brace of $B$ and thus $B$ cannot be a counterexample.
Hence both $X$ and $\Complement{X}$ must contain vertices of $H'$.
Observe that $\CutG{H'}{X}$ is also a tight cut of $H'$.
Now $H'$ has exactly one $K_{3,3}$ and, possibly, a bunch of $C_4$ as its list of braces.
Moreover, the brace $J'$ of $H'$ that is isomorphic to $K_{3,3}$ must contain all six degree three vertices of $H'$, or remainders of them.
Indeed, this means that either $X$ or $\Complement{X}$ contains at least five vertices of $H$.
By <ref> this means that at most one of the two paths $P_1$ and $P_2$ may have an edge in $\CutG{B}{X}$.
If none of the two paths has an edge in $\CutG{B}{X}$, then one of the two tight cut contractions of $\CutG{B}{X}$ contains all of $H'$ as a conformal subgraph, contradicting $B$ being a minimal counterexample as before.
Hence we may assume $\E{P_1}\cap\CutG{B}{X}\neq\emptyset$.
First, assume $\Abs{\E{P_1}\cap\CutG{B}{X}}\geq 2$.
We claim that both endpoints of $P_1$ belong to one of the two shores, say $X$ and $\Abs{\E{P_1}\cap\CutG{B}{X}}= 2$.
To see this let $Q_1,\dots,Q_{\ell}$, $\ell\geq 2$ be the components of $P_1-\CutG{B}{X}$ with vertex sets in $\Complement{X}$.
By <ref> each $Q_j$ must have both endpoints in the same colour class and thus is of even length.
Thus for each $Q_j$ there exists an edge in $M\cap\CutG{B}{X}\cap\E{P_1}$ covering an endpoint of $Q_j$.
Consequently, with $\ell\geq 2$ this contradicts $\CutG{B}{X}$ being tight.
Hence  $\Abs{\E{P_1}\cap\CutG{B}{X}}\geq 2$.
However, if $P_1$ would have an endpoint in both $X$ and $\Complement{X}$, then $\Abs{\CutG{B}{X}}$ would be odd.
Also note that in case both endpoints of $P_1$ are in $X$, then all of $H$ must be in $X$ since otherwise, we could choose a perfect matching of $H'$ with at least two edges in $\CutG{B}{X}$.
Hence after contracting the shore that does not contain an endpoint of $P_1$, we obtain a matching covered graph that contains a conformal $K_{3,3}$-bisubdivision with $H$ as a subgraph.
In case $\Abs{\E{P_1}\cap\CutG{B}{X}}=1$ exactly one endpoint of $P_1$ must be contained in, say, $\Complement{X}$, while the rest of $H$ belongs to $X$.
Again, after contracting the shore that does not contain an endpoint of $P_1$ we obtain a matching covered graph that contains a conformal $K_{3,3}$-bisubdivision with $H$ as a subgraph.
Hence in neither case $B$ can be a minimal counterexample, and thus no such $B$ can exist.

The reverse follows among similar lines.
If there is a $K_{3,3}$-containing brace $J$ of $B$ such that $H\subseteq J$, then, by <ref> there must be a conformal bisubdivision $L$ of $K_{3,3}$ in $J$ that contains $C$ as a subgraph.
Indeed, as we have seen before, we can choose $L$ such that $H\subseteq L$ and thus there must be a conformal bisubdivision $L'$ of $K_{3,3}$ in $B$ such that $H\subseteq L'$.
According to <ref>, this means that there is a conformal cross over $C$ in $B$.

There exists an algorithm that, given a bipartite and matching covered graph $B$ as input, computes a list of all braces of $B$ in time $\Fkt{\mathcal{O}}{\Abs{\V{B}}\Abs{\E{B}}}$.

With this, we are finally ready for the proof of <ref>

Let $B$ be a bipartite graph with a perfect matching and $S\coloneqq\Set{a_1,a_2,b_1,b_2}$ be the set of terminals we received as input for the $2$-MLP.
By the discussion at the start of this section we only have to check for each of the at most $\Abs{\V{B}}^2$ $S$-covers $F$ whether they are extendible and whether $B$ is an $F$-instance of $2$-MLP for $\Brace{a_1,a_2}$ and $\Brace{b_1,b_2}$.
To check whether $F$ is extendable we have to check whether $B-\V{F}$ has a perfect matching which can be done by the Hopcroft-Karp algorithm in time $\Fkt{\mathcal{O}}{n^{\frac{5}{2}}}$ [7].
So we may assume $F$ to be extendible.

In case $F=\Set{a_1b_1,a_2b_2}$ we can stop immediately and return the answer 'Yes'.

If $\Abs{F\cap \Set{a_1b_1,a_2b_2}}=1$ we can reduce the problem of finding our $2$-linkage to the reachability problem in digraphs as follows.
Without loss of generality let us assume $a_1a_2\in F$ and let $M$ be a perfect matching of $B$ that extends $F$.
Moreover, let $e_a\in M$ be the edge covering $a_2$ while $e_b$ is the edge of $M$ covering $b_2$.
There exists a perfect matching $M'$ of $B$ that extends $F$ such that there is an internally $M'$-conformal path with endpoints $a_2$ and $b_2$ in $B-a_1-b_1$ if and only if there is an internally $M$-conformal path $P$ with endpoints $a_2$ and $b_2$ in $B-a_1-b_1$ by <ref>.
Testing whether such a path exists is equivalent to the reachability problem in digraphs, i.e. the problem of deciding whether there exists a directed $s$-$t$-path for given vertices $s$ and $t$.
Hence this can be done in polynomial time.

Thus we may assume $F\cap\Set{a_1b_1,a_2b_2}=\emptyset$.
By <ref> we can translate the problem into the decision problem, whether there is a conformal cross over the $4$-cycle $\MLPCycle{B,F,S}$ in $\MLPInstance{}{B,F,S}$.
Let $H$ be the subgraph of $\MLPInstance{}{B,F,S}$ induced by $S\cup\Set{x,y}$, then <ref> allows us to return 'Yes' if and only if $\MLPInstance{}{B,F,S}$ has a $K_{3,3}$-containing brace $J$ with $H\subseteq J$.
<Ref> finds all braces of $\MLPInstance{}{B,F,S}$ in time $\Fkt{\mathcal{O}}{\Abs{\V{B}}^3}$ and if there is a brace $J$ with $H\subseteq J$ we can use <ref> to decide in time $\Fkt{\mathcal{O}}{\Abs{\V{B}}^3}$ whether $J$ is $K_{3,3}$-free.

§ CONCLUSION

This paper is part of an ongoing series of papers which tries to extend the graph minors theory of Robertson and Seymour to matching minors in bipartite graphs.
While matching minors have already proven to be a powerful tool in the resolution of the Pfaffian Recognition Problem [16, 22], so far few attempts have been made to further understand the properties of matching minors in bipartite graphs.
In the previous paper of the series [6] it was proven that the exclusion of a planar matching minor in a bipartite graph leads to a relatively well behaved tree-structure, similar to how excluding a planar minor leads to bounded treewidth.
In the same paper it was also shown that excluding a planar matching minor leads to an $\XP$-algorithm for the bipartite $t$-DAPP.
In the context of these findings, this paper is a consequential next step towards a matching theoretic version of the Flat Wall Theorem, which is the content of the next paper in line.
Our hope is that positive results like these spark an increase of interest in the topic and act as a base for deeper structural insights for bipartite matching covered graphs.

§.§ Relations with Digraphs

As mentioned in the introduction, there exists a tight interaction of digraphs and bipartite graphs with perfect matchings.
This becomes particularly obvious by considering the following operation:
Let $B$ be a bipartite graph with a perfect matching $M$.
Then let $\vec{B}$ be the orientation of $B$ obtained by orienting every edge of $B$ from $V_1$ to $V_2$.
Finally let $\DirM{B}{M}$ be the digraph obtained from $\vec{B}$ by contracting every edge of $M$.
See <ref> for an illustration.

(C) [] ;

(C1) [v:ghost, position=180:40mm from C] ;

(C2) [v:ghost, position=0:0mm from C] ;

(C3) [v:ghost, position=0:40mm from C] ;

(a) [v:main,position=0:0mm from C1] ;
(ain) [v:ghost,position=0:2.25mm from a] ;

(b) [v:main,position=0:13mm from a,fill=white] ;
(e) [v:main,position=270:13mm from a,fill=white] ;

(c) [v:main,position=0:13mm from b] ;
(cin) [v:ghost,position=270:2.25mm from c] ;
(f) [v:main,position=270:13mm from b] ;
(fin) [v:ghost,position=270:2.25mm from f] ;
(i) [v:main,position=270:13mm from e] ;
(iin) [v:ghost,position=90:2.25mm from i] ;

(d) [v:main,position=0:13mm from c,fill=white] ;
(g) [v:main,position=270:13mm from c,fill=white] ;
(j) [v:main,position=0:13mm from i,fill=white] ;
(m) [v:main,position=270:13mm from i,fill=white] ;

(h) [v:main,position=0:13mm from g] ;
(hin) [v:ghost,position=90:2.25mm from h] ;
(k) [v:main,position=270:13mm from g] ;
(kin) [v:ghost,position=0:2.25mm from k] ;
(n) [v:main,position=270:13mm from j] ;
(nin) [v:ghost,position=180:2.25mm from n] ;

(l) [v:main,position=0:13mm from k,fill=white] ;
(o) [v:main,position=270:13mm from k,fill=white] ;

(p) [v:main,position=0:13mm from o] ;
(pin) [v:ghost,position=180:2.25mm from p] ;

(ab) [v:main,fill=BostonUniversityRed,position=270:4mm from C3] ;
(ei) [v:main,fill=BostonUniversityRed,position=247.5:16mm from ab] ;
(fj) [v:main,fill=BostonUniversityRed,position=292.5:16mm from ab] ;
(mn) [v:main,fill=BostonUniversityRed,position=270:32mm from ab] ;
(cg) [v:main,fill=BostonUniversityRed,position=45:15mm from fj] ;
(dh) [v:main,fill=BostonUniversityRed,position=0:15mm from cg] ;
(kl) [v:main,fill=BostonUniversityRed,position=300:15mm from cg] ;
(op) [v:main,fill=BostonUniversityRed,position=270:14.5mm from kl] ;

(b) [e:main] to (c);
(b) [e:main] to (f);

(e) [e:main] to (a);
(e) [e:main] to (f);

(d) [e:main] to (c);

(g) [e:main] to (f);
(g) [e:main] to (h);
(g) [e:main] to (k);

(j) [e:main] to (i);
(j) [e:main] to (k);
(j) [e:main] to (n);

(m) [e:main] to (i);

(l) [e:main] to (h);
(l) [e:main] to (p);

(o) [e:main] to (k);
(o) [e:main] to (n);

(ab) [e:main,->] to (fj);
(ab) [e:main,->] to (cg);

(ei) [e:main,->,bend left=15] to (fj);
(ei) [e:main,->] to (ab);

(fj) [e:main,->,bend left=15] to (ei);
(fj) [e:main,->] to (mn);
(fj) [e:main,->] to (kl);

(mn) [e:main,->] to (ei);

(cg) [e:main,->,bend right=15] to (dh);
(cg) [e:main,->] to (fj);
(cg) [e:main,->] to (kl);

(dh) [e:main,->,bend right=15] to (cg);

(kl) [e:main,->] to (dh);
(kl) [e:main,->,bend left=15] to (op);

(op) [e:main,->] to (mn);
(op) [e:main,->,bend left=15] to (kl);

(b) [e:coloredborder] to (a);
(e) [e:coloredborder] to (i);
(d) [e:coloredborder] to (h);
(g) [e:coloredborder] to (c);
(j) [e:coloredborder] to (f);
(m) [e:coloredborder] to (n);
(l) [e:coloredborder] to (k);
(o) [e:coloredborder] to (p);

(b) [e:colored,color=BostonUniversityRed] to (a);
(e) [e:colored,color=BostonUniversityRed] to (i);
(d) [e:colored,color=BostonUniversityRed] to (h);
(g) [e:colored,color=BostonUniversityRed] to (c);
(j) [e:colored,color=BostonUniversityRed] to (f);
(m) [e:colored,color=BostonUniversityRed] to (n);
(l) [e:colored,color=BostonUniversityRed] to (k);
(o) [e:colored,color=BostonUniversityRed] to (p);

Left: A bipartite graph $B$ with a perfect matching $M$. Right: The arising $M$-direction $\DirM{B}{M}$.

Clearly, once the colour classes $V_1$ and $V_2$ are uniquely identified with the direction of edges (in our case we say that edges go from $V_1$ to $V_2$) then the operation of forming the $M$-direction is invertible.
Indeed, one can obtain from every digraph a uniquely determined bipartite graph with a perfect matching and vice versa.
Moreover as it turns out, several structural properties of $B$ are reflect in $\DirM{B}{M}$ and vice versa.
These properties range from simple observations like `$B$ is connected if and only if $\DirM{B}{M}$ is weakly connected.' up to 'For each bipartite graph $J$ with a perfect matching there exists a unique family $\mathcal{J}$ of digraphs such that $B$ contains $J$ as a matching minor if and only if $\DirM{B}{M}$ contains a member of $\mathcal{J}$ as a butterfly minor.'.
This is proven and discussed in [6].
The second property in particular allows us to combine the theory of butterfly minors in digraphs and the theory of matching minors in bipartite graphs into one unified theory.
This angle of viewing digraphs and bipartite graphs with perfect matchings as related objects gives us a tool to have some sort of control over certain infinite antichains of the butterfly minor relation and, it also gives us a way to use the matching theoretic results of this paper to obtain structural results on digraphs while avoiding such problems as the absence of a directed Two Paths Theorem.

To see how this would be possible consider the example of the Directed $2$-Disjoint Paths Problem.
This problem is $\NP$-complete and by using the $M$-direction and its inverse one can easily see that the problem of finding two disjoint directed paths between given terminal vertices in a digraph can be translated into asking whether there exist disjoint internally $M$-conformal paths between given terminal vertices in the corresponding bipartite graph.
Hence, if we only slightly alter the definition of $t$-DAPP by not asking for the existence of a perfect matching for which a solution exists, but by insisting on the question whether there is solution for this particular perfect matching, the problem suddenly becomes $\NP$-hard.
So from the additional flexibility of being able to change the perfect matching possible tools can arise to deal with problems which are intractable on digraphs otherwise.
It would be interesting to see where the limits of this additional flexibility lie.

[1]
Marién Abreu, Robert EL Aldred, Martin Funk, Bill Jackson, Domenico
Labbate, and John Sheehan.
Graphs and Digraphs with all $2$-Factors Isomorphic.
Journal of Combinatorial Theory, Series B, 92(2):395–404,

[2]
Robert EL Aldred, Derek A Holton, Dingjun Lou, and Akira Saito.
M-Alternating Paths in $n$-Extendable Bipartite Graphs.
Discrete Mathematics, 269(1-3):1–11, 2003.

[3]
Jørgen Bang-Jensen, Frédéric Havet, and A Karolinna Maia.
Finding a Subdivision of a Digraph.
Theoretical Computer Science, 562:283–303, 2015.

[4]
Steven Fortune, John Hopcroft, and James Wyllie.
The Directed Subgraph Homeomorphism Problem.
Theoretical Computer Science, 10(2):111–121, 1980.

[5]
Archontia C Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung
The Directed Flat Wall Theorem.
In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 239–258. SIAM, 2020.

[6]
Archontia C Giannopoulou, Stephan Kreutzer, and Sebastian Wiederrecht.
Excluding a Planar Matching Minor in Bipartite Graphs.
arXiv preprint arXiv:2106.00703, 2021.

[7]
John E Hopcroft and Richard M Karp.
An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite
SIAM Journal on computing, 2(4):225–231, 1973.

[8]
Meike Hatzel, Roman Rabinovich, and Sebastian Wiederrecht.
Cyclewidth and the Grid Theorem for Perfect Matching
Width of Bipartite Graphs.
In International Workshop on Graph-Theoretic Concepts in
Computer Science, pages 53–65. Springer, 2019.

[9]
Meike Hatzel, Roman Rabinovich, and Sebastian Wiederrecht.
Cyclewidth and the Grid Theorem for Perfect Matching
Width of Bipartite Graphs.
arXiv preprint arXiv:1902.01322, 2019.

[10]
Heinz A Jung.
Eine Verallgemeinerung des $n$-fachen Zusammenhangs für
Mathematische Annalen, 187(2):95–103, 1970.

[11]
László Lovász.
Matching Structure and the Matching Lattice.
Journal of Combinatorial Theory, Series B, 43(2):187–222,

[12]
László Lovász.
Graph Minor Theory.
Bulletin of the American Mathematical Society, 43(1):75–86,

[13]
László Lovász and Michael D Plummer.
Matching Theory, volume 367.
American Mathematical Soc., 2009.

[14]
William McCuaig.
Even Dicycles.
Journal of Graph Theory, 35(1):46–68, 2000.

[15]
William McCuaig.
Brace Generation.
Journal of Graph Theory, 38(3):124–169, 2001.

[16]
William McCuaig.
Pólya's Permanent Problem.
Electronic Journal of Combinatorics, pages R79–R79, 2004.

[17]
Serguei Norine.
Matching Structure and Pfaffian Orientations of
PhD thesis, Georgia Institute of Technology, 2005.

[18]
Michael D Plummer.
On $n$-Extendable Graphs.
Discrete Mathematics, 31(2):201–210, 1980.

[19]
Michael D Plummer.
Matching Extension in Bipartite Graphs.
Congr. Numer, 54:245–258, 1986.

[20]
Neil Robertson and Paul D Seymour.
Graph Minors: VIII. A Kuratowski Theorem for General
Journal of Combinatorial Theory, Series B, 48(2):255–288,

[21]
Neil Robertson and Paul D Seymour.
Graph Minors: XIII. The Disjoint Paths Problem.
Journal of combinatorial theory, Series B, 63(1):65–110, 1995.

[22]
Neil Robertson, Paul D Seymour, and Robin Thomas.
Permanents, Pfaffian Orientations, and Even Directed
Annals of Mathematics, pages 929–975, 1999.

[23]
Paul D Seymour.
Disjoint Paths in Graphs.
Discrete Mathematics, 29(3):293–309, 1980.

[24]
Yossi Shiloach.
A Polynomial Solution to the Undirected Two Paths
Journal of the ACM (JACM), 27(3):445–456, 1980.

[25]
Carsten Thomassen.
2-Linked Graphs.
European Journal of Combinatorics, 1(4):371–378, 1980.

[26]
Carsten Thomassen.
The 2-Linkage Problem for Acyclic Digraphs.
Discrete mathematics, 55(1):73–87, 1985.

[27]
Klaus Wagner.
Über eine Eigenschaft der Ebenen Komplexe.
Mathematische Annalen, 114(1):570–590, 1937.

[28]
Hassler Whitney.
Congruent Graphs and the Connectivity of Graphs.
In Hassler Whitney Collected Papers, pages 61–79. Springer,


# Efficient joint noise removal and multi exposure fusion

A. Buades1¶, J.L Lisani1¶, O. Martorell1*¶

1 Institute of Applied Computing and Community Code (IAC3) and with the
Dept.of Mathematics and Computer Science, Universitat de les Illes Balears,
Cra. de Valldemossa km. 7.5, E-07122 Palma, Spain

¶The authors acknowledge the Ministerio de Ciencia, Innovación y Universidades
(MCIU), the Agencia Estatal de Investigación (AEI) and the European Regional
Development Funds (ERDF) for its support to the project TIN2017-85572-P.

*<EMAIL_ADDRESS>
## Abstract

Multi-exposure fusion (MEF) is a technique for combining different images of
the same scene acquired with different exposure settings into a single image.
All the proposed MEF algorithms combine the set of images, somehow choosing
from each one the part with better exposure.

We propose a novel multi-exposure image fusion chain taking into account noise
removal. The novel method takes advantage of DCT processing and the multi-
image nature of the MEF problem. We propose a joint fusion and denoising
strategy taking advantage of spatio-temporal patch selection and collaborative
3D thresholding. The overall strategy permits to denoise and fuse the set of
images without the need of recovering each denoised exposure image, leading to
a very efficient procedure.

##  1 Introduction

Multi-exposure fusion (MEF) is a technique for combining different images of
the same scene acquired with different exposure settings into a single image.
By keeping the best exposed parts of each image, we can recover a single image
where all features are well represented. Compared to High Dynamic Range (HDR),
MEF avoids the estimation of the camera response function and the tone
mapping, keeping during all the process the original range of the images.

All the proposed MEF algorithms combine the set of images, somehow choosing
from each one the part with better exposure. Most methods express this choice
as a combination of pixel values or their gradient, commonly weighted
depending on exposure, saturation and contrast, e.g. Mertens et al. [41]. In
order to make this choice robust, the methods use a pyramidal structure or
work at the patch level instead of the pixel one. In the case that pixel
gradient is manipulated, a final estimate has to be recovered by Poisson
editing [47].

Image fusion is an extensive research area not limited to multi-exposure
images. The combination of several images permits to improve their quality,
removing for example noise [6], compression artifacts [15], haze [21], blur
[54] or shaking blur from hand held video [10],[9].

We propose a novel multi-exposure image fusion chain taking into account noise
removal. Instead of combining gradients or pixel values, we fuse the Discrete
Cosinus Transform (DCT) coefficients of the differently exposed images. The
use of the DCT permits to include a thresholding stage attenuating noise
during the fusion process. DCT thresholding is a well known method for noise
removal, behaving extremely well with moderate noise levels and being
efficient in terms of computational complexity. We propose a novel strategy
taking advantage of DCT thresholding and the multi-image nature of the MEF
problem.

The methods in [37] and [40] propose a similar fusion procedure to ours.
However, they do not include any noise removal stage. The method in Ma et al.
[37] uses a patch based approach, in which each patch is decomposed into its
average and detail patch. Averages are combined depending on exposure, while
detail patches are averaged depending on its magnitude. Our approach also
deals differently with the average and the details but it uses DCT to
represent the details and not just the difference of the patch with its
average. While the method in [37] is applied to each color channel, we use a
color decorrelation transform.

The method in [40] uses a DCT transform but instead of combining the averages
of the patches it uses an auxiliary image obtained with Mertens et al [41]
algorithm to set the patch illumination. We combine the average coefficients
depending on local and global exposure. The method in [40] applies a
completely different strategy for luminance and chromatic parts, while our
method uses the same procedure for both components, permitting noise
reduction.

Although the proposed fusion method is able to deal with low levels of noise,
for more challenging cases the simple DCT thresholding might be insufficient.
Based on noise removal methods for image and video [8, 6], we propose a joint
strategy taking advantage of spatio-temporal patch selection [6] and
collaborative 3D thresholding [8]. The computed patch DCTs for collaborative
thresholding are directly fed into the fusion procedure. The overall strategy
permits to denoise and fuse the set of images without the need of recovering
each denoised exposure image, leading to a very fast procedure.

Section 2 describes the MEF existing literature. The proposed method for the
fusion of images with different exposures is described in Section 3. Section 4
presents the complete method including the fusion and noise removal stages. In
Section 5, we discuss the implementation of the method and compare with state
of the art algorithms and we draw some conclusions in Section 6.

##  2 Related work

Figure 1: Multi exposure data sets used for comparison.

Several MEF methods have been proposed in the literature. Mertens et al. [41]
proposed a pixel wise combination of images depending on contrast, saturation
and well-exposedness. Many algorithms appeared improving aspects of their
method or making it motion adaptive, such as Li et al. [31], An et al. [3],
Ocampo et al. [44], Liu et al. [35], Hayat et al. [16] and Hessel et al. [18].

Another type of methods combine the gradient of the images, and then they
recover the solution by Poisson image editing [47]. For several algorithms,
just the most convenient gradient is chosen, for example Kuk et al. [25].
Other methods combine all gradients, for example [53, 63, 13, 57].

Instead of fusing red, green and blue values, the YCbCr [11] color space is
often used. Paul et al. [46] combines the luminance using a gradient based
fusion. The chromatic components are fused by direct pixel-wise averaging
favoring colored pixels compared to gray ones. A similar approach is adopted
in [40].

This pixel-wise choice is not robust enough and needs to be regularized by
using pyramidal structures or working at the patch level. The Laplacian
pyramid proposed by Burt and Adelson [7] was adopted by Mertens et al. [42]
and posterior methods Ancuti et al. [4], Kou et al. [24, 23]. Patch-based
methods use as minimal unit small image windows, which makes them more robust
than pixel wise algorithms since much more values are involved in the fusion
process (Goshtasby [12], Zhang et al. [64], Zhang et al. [65], Ma et al.
[37]).

When the image sequence is not completely static, the fusion of moving objects
creates a ghosting effect. There exist three main strategies to avoid these
artifacts. The first strategy is to take into account block distance or
correlation in order to weight the combination process. Such a weighted
average might discard moving objects from the combination. The second one is
to modify the sequence to make it static [20, 34, 67, 40]. A third
straightforward strategy, adopted by several algorithms [58, 50, 55, 19], is
to fuse several instances of the same reference image. The image with middle
exposure is chosen as reference and is photometrically matched to each of the
rest. These copies of the reference are then fused by any MEF method. This
strategy permits to get rid of motion and misalignments, but does not use the
detail and structure information of the rest of images, only their color
distribution.

Several methods (Z. G. Li et al. [33, 32], Singh et al. [56], Raman et al.
[52], Li et al. [30]) separate low frequency (base images) from high frequency
(detail images) using the Bilateral filter [59] or the Guided filter [17].
This separation permits an additional enhancement of the detail part.

Variational methods [48, 5, 14] have also been proposed to model MEF fusion.
The proposed energies prefer to keep the geometry of the short exposure images
and the color distribution of the long ones. The methods [38, 26, 36] try to
optimize a quality measure of the final estimate. Ma et al. [36] proposed to
optimize a modification of the objective quality measure in [39], adapted to
color images.

Neural network methods have recently appeared for MEF and HDR imaging.
Prabhakar et al. [51] uses a loss function minimizing an exposure fusion
objective metric [39], avoiding the creation of ground truth images for the
learning phase. Prabhakar et al. [49] proposed a neural network to align
differently exposed images and merge them. Kalantari et al. [22] and Wu et al.
[60] proposed learning methods for HDR imaging. Both networks apply to
sequences of three images, and for the learning phase they need the
corresponding LDR and HDR pairs for the three images. The main difference
between both methods is that in [22] the input images are aligned by an
optical flow estimation and warping, whereas in [60] the images do not need to
be aligned before being introduced to the network.

Zhang et al. [66] and Xu et al. [61] proposed a unified deep learning
framework for several fusion tasks, including MEF. Zhang et al. [66] extract
features using convolutional layers, which are combined using an elementwise
operation (mean for multi-exposure images). The final result is reconstructed
from the fused features by additional convolutional layers. Xu et al. [61]
trained a neural network to preserve the adaptive similarity between the
fusion result and source exposures, that is, not requiring the ground truth
images. Li et al. (CNNFEAT) [29] use CNN to extract features, which are used
to combined the different exposures. However, the fused result is not the
direct output of a neural network.

There is very few literature dealing with noise removal during multi exposure
image fusion, and most published papers are focused on HDR. Akyuz et al. [2]
denoise each frame before fusion, but this is performed in the radiance
domain. Tico et al. [58] combines an initial fusion with the image of the
sequence with the shortest exposure in the luminance domain. This combination
is performed in the wavelet domain and coefficient attenuation is applied to
the coefficients of the difference of luminances. Min et al. [43] filter the
set of images by spatio-temporal motion compensated anisotropic filters prior
to HDR reconstruction. Lee et al. [28] use sub-band architecture for fusion,
with a weighted combination using a motion indicator function to avoid
ghosting effects. The low frequency bands are filtered with a multi-resolution
bilateral filter while the high frequency bands are filtered by soft
thresholding. Ahmad et al. [1] identify noisy pixels and reduce their weight
during image fusion.

##  3 Proposed fusion algorithm

We propose a novel algorithm for multi-exposure fusion adopting the Fourier
aggregation model as main tool.

Figure 2: Comparison between applying the fusion to each RGB channel
independently and using the YUV luminance and chromatic components. The
luminance of the two results is identical, while the color is enhanced by the
latter strategy.

###  3.1 Single Channel image fusion

Let assume we have a multi-exposure sequence of image luminance, supposed to
be pre-registered, which we denote by $Y_{k}$, $k=1,2,\dots,K$. Since each
image might contain well exposed areas, we apply the combination locally. We
split the images $Y_{k}$ into partially-overlapped blocks of $b\times b$
pixels, $\\{B_{k}^{l}\\},\ l=1,\dots,n_{b}$, $n_{b}$ the number of blocks.

Both under and over exposed patches will have Fourier coefficients of smaller
magnitude, due to the lack of high frequency information; while well exposed
patches will have Fourier coefficients of larger magnitude. We propose to fuse
the non-zero frequencies of each block as follows:

$\hat{B}^{l}(\xi)=\sum_{k=1}^{K}w_{k}^{l}(\xi)\hat{B}_{k}^{l}(\xi),\quad\xi\not=0,\quad
l=1,2,\dots,n_{b},$ (1)

where $\hat{B}_{k}^{l}$ denotes the DCT transform of patch $l$ in image $k$,
and the weights $w_{k}^{l}(\xi)$ are defined depending on $\xi$,

$w_{k}^{l}(\xi)=\frac{|\hat{B}_{k}^{l}(\xi)|^{p}}{\sum_{n=1}^{K}|\hat{B}_{n}^{l}(\xi)|^{p}}\qquad\xi\not=0\,.$
(2)

The parameter $p$ controls the weight of each Fourier mode.

This strategy does not apply to the zero frequency Fourier coefficient,
$\xi=0$, i.e. the mean. Since large zero frequency coefficients correspond to
over-exposed images, applying the same weighted combination would simply
overexpose the fused image. We weight these coefficients depending on how
exposed is the local patch, as well as the entire image, with respect to the
other ones.

$\hat{B}^{l}(0)=\sum_{k=1}^{K}w_{k}^{l}(0)\hat{B}_{k}^{l}(0),\quad
l=1,2,\dots,n_{b},$

where

$w_{k}^{l}(0)=\frac{1}{C}e^{-(\hat{B}_{k}^{l}(0)-0.5)^{2}/\sigma_{l}^{2}}\cdot
e^{-(\mu_{k}-0.5)^{2}/\sigma_{g}^{2}},$ (3)

with $\mu_{k}$ the average of image $k$, $C$ a normalizing constant, and
$\sigma_{l}$ and $\sigma_{g}$ parameters of the method. The averages of the
patches are normalized to $[0,1]$, then $0.5$ corresponds to the gray level
mid value.

Finally, applying the inverse DCT transform to each block we obtain the fused
blocks.

$B^{l}(x)={\mathcal{F}}^{-1}(\hat{B^{l}}(\xi)),\quad l=1,\dots,n_{b}.$ (4)

Since blocks are partially overlapped, the pixels in overlapping areas are
averaged to produce the final image.

###  3.2 Color image fusion

We use an orthonormal chromatic version of the well known YUV space, described
by the following linear transformation.

$\left(\begin{array}[]{c}\mbox{Y}\\\ \mbox{U}\\\
\mbox{V}\end{array}\right)=\left(\begin{array}[]{ccc}\frac{1}{\sqrt{3}}&\frac{1}{\sqrt{3}}&\frac{1}{\sqrt{3}}\\\
\frac{\sqrt{2}}{2}&0&-\frac{\sqrt{2}}{2}\\\
\frac{1}{\sqrt{6}}&-\frac{2}{\sqrt{6}}&\frac{1}{\sqrt{6}}\end{array}\right)\left(\begin{array}[]{c}\mbox{R}\\\
\mbox{G}\\\ \mbox{B}\end{array}\right)$

The Y channel, given by the average of the RGB values, represents the
luminance, while U and V contain the chromatic information. The use of an
orthonormal transform is motivated by the denoising stage described below.

The channel Y is processed as exposed above, with the average coefficient
combined depending on exposure. However, for the U and V components, we use
the weighted average defined by Equations (1) and (2) for all coefficients,
including $\xi=0$.

The use of such a weighting does not increase the risk of over-exposure, but
enhances the patch average chromaticity, making the result more colorful than
when applying the single channel method to each of the components R, G and B.
This is noticeable in Fig. 2, in which both strategies are compared.

###  3.3 Noise removal

Assuming a classical Gaussian uniform white noise scenario with standard
deviation $\sigma$, the proposed fusion method can naturally incorporate noise
removal. By modifying the weight definition $\eqref{weights}$ to

$w_{k}^{l}(\xi)=\frac{Thr_{\sigma}(|\hat{B}_{k}^{l}(\xi)|)^{p}}{\sum_{n=1}^{K}Thr_{\sigma}(|\hat{B}_{n}^{l}(\xi)|)^{p}},\qquad\xi\not=0$
(5)

where

$Thr_{\sigma}(|\hat{B}_{k}^{l}(\xi)|)=\left\\{\begin{array}[]{cc}0&|\hat{B}_{k}^{l}(\xi)|<{T}\cdot\sigma\\\
&\\\ |\hat{B}_{k}^{l}(\xi)|&\mbox{otherwise}\end{array}\right.$

Since the YUV color transformation is orthonormal, the noise standard
deviation is not modified by the linear transformation converting from RGB to
the mentioned space. Thus, the same thresholding can be applied to each
channel. The parameter $T$ is set to 2.7 as usual when denoising by
thresholding in an orthonormal basis.

Fig. 3 compares the application of the fusion chain with and without this DCT
thresholding stage.

When dealing with high levels of noise, the DCT thresholding method described
above is not enough to provide good denoising results. The next section
describes how the fusion method can be combined with a collaborative denoising
technique to obtain much better results.

|  |
---|---|---
|  |
One of the exposures | Fusion | Fusion with DCT thresh.
Figure 3: Noisy example with sequence Office and noise standard deviation
$15$. Top and from left to right: one image from the exposures set, fused
without and with DCT thresholding. Below: detail of the images.

##  4 Joint noise removal and fusion procedure

Figure 4: Processing scheme of a specific reference patch.

We assume as in the previous sections, that data is static and a uniform white
noise model of standard deviation $\sigma$. Many variants have been proposed
to deal with the noise removal of image sequences having the same exposure and
noise conditions. Such methods cannot be directly used for MEF.

We propose a joint noise removal and fusion procedure (see scheme in Fig. 4).
The noise removal stage uses a collaborative DCT thresholding as in [8], and a
spatio-temporal patch selection as in [6]. The spatio-temporal selection
permits a more robust patch comparison. The use of collaborative DCT
thresholding permits a natural integration with the proposed fusion method,
since both denoising and fusion are performed in the DCT domain, thus avoiding
the need to reconstruct each denoised image prior to the fusion step.

The proposed strategy is well adapted to the MEF framework, namely to the fact
that all the images have different exposure. In the patch-selection process,
only patches belonging to the same image are compared, thus avoiding computing
the similarity of patches with different exposure. In the same line, only
patches having the same exposure are used in the denoising step.

Given the static image sequence, we build 3D blocks of patches, composed by
the 2D patches from the sequence located at the same spatial position. The
distance between different 3D blocks is computed as

$d_{\text{3D}}(\bm{x},\bm{y})=\sum_{\text{image $i$ in
sequence}}||P_{i}(\bm{x})-P_{i}(\bm{y})||$

where $P_{i}(\bm{x})$ and $P_{i}(\bm{y})$ denote the 2D patches referenced by
$\bm{x}$ and $\bm{y}$ in image $i$ (each 2D patch is referenced by its top-
left vertex).

By selecting the $k$ nearest neighboring 3D blocks, we actually select $k$
patches for each exposure. Collaborative DCT thresholding (see [8, 27]) is
applied separately to the selected 2D patches belonging to the same exposure
image.

The above collaborative filtering recovers the denoised DCT patches which are
fed directly into the fusion procedure. That is, the proposed algorithm does
not need to apply the 2D inverse DCT to the grouped patches in order to
recover each denoised exposure.

Each 3D block of the $k$ selected ones contains denoised 2D DCT patches
corresponding at the same spatial location and different exposure. Each one is
combined by the fusion process which includes the additional DCT thresholding.
The inverse DCT is applied to the $k$ fused patches, which permits an
additional aggregation in the image domain.

The joint patch selection procedure reduces the dependence of noise in patch
comparison, improving the robustness of the method and reducing the usual
artifacts of collaborative filtering.

##  5 Discussion and experimental results

|  |  |
---|---|---|---
Mertens et al. [41] | Ma et al. [37] | Li et al. [32] | Paul et al. [45]
|  |  |
Kou et al. [23] | Ma et al. [36] | Martorell et al. [40] | Li et al. [29]
|  |  |
Hessel et al [18] | Zhang et al. [66] | Hayat et al. [16] | Ours
Figure 5:  Results of fusion of noise-free multi-exposure images with different methods. |  |  |
---|---|---|---
Mertens et al. [41] | Ma et al. [37] | Li et al. [32] | Paul et al. [45]
|  |  |
Kou et al. [23] | Ma et al. [36] | Martorell et al. [40] | Li et al. [29]
|  |  |
Hessel et al [18] | Zhang et al. [66] | Hayat et al. [16] | Ours
Figure 6: Extract of the results shown in Fig. 5.

In this section we compare the proposed method with state of the art
algorithms for exposure fusion. We compare with Mertens et al. [41], Ma et al.
[37], Li et al. [32], Kou et al. [23], Ma et al. [36], Hessel et al, (EEF)
[18], Paul et al. [45], Zhang et al. (IFCNN) [66], Li et al. (CNNFEAT) [29],
Hayat et al. (MEF-Sift) [16] and Martorell et al. [40]. The results from Ma et
al. [37] and Ma et al. [36] were computed with the software downloaded from
the corresponding author’s webpage. The results of Mertens et al. [41] were
obtained from the dataset provided in [62] and [39]. The code for Hessel et
al.111http://www.ipol.im/pub/art/2019/278/?utm_source=doi (EEF) [18], Paul et
al.222https://github.com/sujoyp/gradient-domain-imagefusion [46], Zhang et
al.333https://github.com/uzeful/IFCNN (IFCNN) [66], Li et
al.444https://github.com/xiaohuiben/MEF-CNN-feature (CNNFEAT) [29] and Hayat
et al.555https://github.com/ImranNust/Source-Code (MEF-Sift) [16] were
obtained from corresponding github webpage. The results from Li et al. [32],
Kou et al. [23] and Martorell et al. [40] were computed with the code provided
by the authors. In all cases, default parameter settings are adopted.

Our results were computed using the same parameters for all tests in this
section. We use blocks of size $8\times 8$ pixels and $p=7$ as the power
exponent of the coefficient magnitudes in Equation 2. A sliding window
approach is applied for the DCT based denosing/fusion. Once it is processed,
the window is moved along both directions with a displacement step of
$N_{\text{step}}=2$. The fact that the whole window is fused permits the
processing of all the pixels in the image.

###  5.1 Noise free sequences

In this case, we just compare the ability of fusing the different exposure
images. We use for our method just the fusion algorithm described in section
3, but without applying any thresholding of the DCT. Note that none of the
compared methods include this noise filtering step.

Fig. 5 displays the results of all the methods on the “Belgium House” data
set. Most methods have a good global illumination. However, looking closer to
the details in Fig. 6, we might observe that many outdoor details in Mertens
et al. [41] and Ma et al. [37] are overexposed, losing its definition. Li et
al. [32] and Kou et al. [23] are not able to mantain the letters on the
blackboard on the right side of Fig. 6 and Ma et al. [36] is not able to
preserve the details on the tree at the top of the detail image. Li et al.
[29] fusion is over-smoothed, while the result by Hayat et al. [16] is over-
saturated at bright parts. The result of [40], Hessel et al [18], Zhang et al.
[66] and ours are quite similar.

###  5.2 Noisy sequences with white uniform Gaussian Noise

We compare in Fig. 8 all the algorithms on a noisy multi exposure sequence
with standard deviation of $15$. We apply all the algorithms with their
default parameters. It is clear from this figure, that the rest of methods are
not adapted or do not take into account noise.

In Fig. 10 we add noise of standard deviation 25 to each exposure and apply
the BM3D algorithm [8] to denoise each image. We apply the different multi
exposure fusion methods to the denoised data. Our method is applied directly
to the noisy sequence.

The zoom of an extract, Fig. 11, shows that our method is the only one able to
denoise and fuse the multi exposure sequence without noticeable artifacts.

###  5.3 Realistic multi exposure noisy images

We finally test our fusion and noise removal method with a realistic noise
case. We add a signal dependent noise at each RAW image of the multi exposure
set. We then apply a standard demosaicking, color processing, gamma correction
and compression to the noisy raw images. The result is a realistic set of
noisy multi exposure color images.

We apply our denoising and fusion algorithm to these images. The result is
displayed in Fig. 12.

###  5.4 Computational analysis

The time complexity of the proposed algorithm is $\mathcal{O}(|Y|)$, where
$|Y|$ denotes the size of each image in the multi-exposure sequence.

Assuming that the 3D transforms used for the collaborative filtering are
performed in a separable way (i.e. 2D transforms followed by 1D transforms, as
detailed in [8]), the overall number of operations of the algorithm, per
pixel, is approximately

${\cal C}_{{\cal T}_{2D}}+2Kb^{2}N_{S}^{2}+2Kb^{2}{\cal C}_{{\cal
T}_{1D}}+2Kkb^{2}+k{\cal C}^{\prime}_{{\cal T}_{2D}}+kb^{2}$ (6)

where:

  * •

${\cal C}_{{\cal T}_{2D}}$ denotes the number of operations required to
compute the 2D DCT of the block of patches similar to the one centered at the
considered pixel. If we consider a neighborhood of size $N_{S}\times N_{S}$
around the pixel, this implies the computation of $KN_{S}^{2}$ 2D DCTs, where
$K$ is the number of images in the sequence. The time complexity can be
reduced by pre-computing the transforms in each block of size $K\times
N_{S}\times N_{S}$ and reusing them in overlapping blocks, similarly to what
is proposed in [8].

  * •

The second term accounts for the 3D block matching step. This implies the
exhaustive search, in a $N_{S}\times N_{S}$ neighborhood of the pixel, of 3D
blocks of size $K\times b\times b$.

  * •

The third term counts the number of operations for the computation of the 1D
DCT transforms (direct and inverse) of the $k$ nearest neighbors of each
patch, in each frame. ${\cal C}_{{\cal T}_{1D}}$ denotes the cost of computing
a 1D DCT transform (direct or inverse) of a vector of size $k$.

  * •

The fourth term accounts for the fusion step, which involves $k$ 3D blocks of
patches of size $K\times b\times b$.

  * •

The fifth term accounts for the number of operations needed to compute the $k$
inverse 2D DCT transforms of the fused patches. ${\cal C}^{\prime}_{{\cal
T}_{2D}}$ denotes the cost of computing the inverse 2D DCT transform of a
patch of $b\times b$ pixels.

  * •

Finally, the last term counts the number of operations involved in the
aggregation step.

Observe that the number of denoising operations per pixel, for each image, is
smaller than that of BM3D since only one step of the collaborative filtering
is applied. In addition, the inverse DCT is applied only to fused patches,
since denoised exposures are not required by the algorithm.

Moreover, the previous estimation assumes that an exhaustive-search algorithm
has been used for block matching. The costs ${\cal C}_{\cal T}$ of the DCT
transforms depends on the availability of fast algorithms. By using predictive
search techniques and fast separable transforms the complexity of the
algorithm could be significantly reduced. Moreover, the overall number of
operations can be further reduced by processing only one out of each
$N_{\text{step}}<b$ pixels in both the horizontal and vertical directions. Due
to the overlapping of the patches, the aggregation step used in the final step
of the algorithm guarantees that all the pixels are correctly processed. In
this case, the overall complexity of the method is reduced by a factor
$N_{\text{step}}^{2}$.

Figure 7: Noisy multi-exposure data sets used for comparison. On the first row, the noise standard deviation of each input image is $15$. On the second row the standard deviation is $25$. |  |  |
---|---|---|---
Mertens et al. [41] | Ma et al. [37] | Li et al. [32] | Paul et al. [45]
|  |  |
Kou et al. [23] | Ma et al. [36] | Martorell et al. [40] | Li et al. [29]
|  |  |
Hessel et al [18] | Zhang et al. [66] | Hayat et al. [16] | Ours
Figure 8:  Results of fusion of noisy multi-exposure images with different methods. The noise standard deviation of each input image is $15$.  |  |  |
---|---|---|---
Mertens et al. [41] | Ma et al. [37] | Li et al. [32] | Paul et al. [45]
|  |  |
Kou et al. [23] | Ma et al. [36] | Martorell et al. [40] | Li et al. [29]
|  |  |
Hessel et al [18] | Zhang et al. [66] | Hayat et al. [16] | Ours
Figure 9:  Extract of the results shown in Fig. 8. It is clear from this figure, that our method is the only one that takes noise into account  |  |  |
---|---|---|---
Mertens et al. [41] | Ma et al. [37] | Li et al. [32] | Paul et al. [45]
|  |  |
Kou et al. [23] | Ma et al. [36] | Martorell et al. [40] | Li et al. [29]
|  |  |
Hessel et al [18] | Zhang et al. [66] | Hayat et al. [16] | Ours
Figure 10:  Results of fusion and denoising. Our method is the only one applied directly to the noisy multi-exposure images. The rest of methods fuse denoised versions of the images obtained using the BM3D algorithm. The noise standard deviation of each input image is $25$.  |  |  |
---|---|---|---
Mertens et al. [41] | Ma et al. [37] | Li et al. [32] | Paul et al. [45]
|  |  |
Kou et al. [23] | Ma et al. [36] | Martorell et al. [40] | Li et al. [29]
|  |  |
Hessel et al [18] | Zhang et al. [66] | Hayat et al. [16] | Ours
Figure 11:  Extract of the results shown in Fig. 10.

Figure 12: Realistic noise simulation. From left to right: three exposure
noisy images and the fusion and noise removal result. Below an extract of each
image.

##  6 Conclusions

In this paper we propose a patch-based method for the simultaneous denoising
and fusion of a sequence of multi-exposure images. Both tasks are performed in
the DCT domain and take advantage of a collaborative 3D thesholding approach
similar to BM3D [8] for denoising, and of the state-of-the-art fusion
technique proposed in [40]. For the collaborative denoising, a spatio-temporal
criterion is used to select similar patches along the sequence, following the
approach in [6]. The overall strategy permits to denoise and fuse the set of
images without the need of recovering each denoised exposure image, leading to
a very efficient procedure.

Several experiments show that the proposed method permits to obtain state-of-
the-art fusion results even when the input multi-exposure images are noisy. As
future work, we plan to extend the current approach to multi exposure video
sequences.

## Acknowledgments

The authors thank Zhengguo Li and Fei Kou for kindly providing the
implementation of [32] and [23], respectively.

## References

  * [1] Attiq Ahmad, Muhammad Mohsin Riaz, Abdul Ghafoor, and Tahir Zaidi.  Noise resistant fusion for multi-exposure sensors.  IEEE Sensors Journal, 16(13):5123–5124, 2016.
  * [2] Ahmet Oğuz Akyüz and Erik Reinhard.  Noise reduction in high dynamic range imaging.  Journal of Visual Communication and Image Representation, 18(5):366–376, 2007.
  * [3] Jaehyun An, Sang Heon Lee, Jung Gap Kuk, and Nam Ik Cho.  A multi-exposure image fusion algorithm without ghost effect.  In Acoustics, Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on, pages 1565–1568. IEEE, 2011.
  * [4] Codruta O Ancuti, Cosmin Ancuti, Christophe De Vleeschouwer, and Alan C Bovik.  Single-scale fusion: An effective approach to merging images.  IEEE Transactions on Image Processing, 26(1):65–78, 2017.
  * [5] Marcelo Bertalmio and Stacey Levine.  Variational approach for the fusion of exposure bracketed pairs.  IEEE Transactions on Image Processing, 22(2):712–723, 2013.
  * [6] Antoni Buades, Jose-Luis Lisani, and Marko Miladinović.  Patch-based video denoising with optical flow estimation.  IEEE Transactions on Image Processing, 25(6):2573–2586, 2016.
  * [7] Peter J. Burt and Edward H. Adelson.  The laplacian pyramid as a compact image code.  IEEE TRANSACTIONS ON COMMUNICATIONS, 31:532–540, 1983.
  * [8] Kostadin Dabov, Alessandro Foi, Vladimir Katkovnik, and Karen Egiazarian.  Image denoising by sparse 3-d transform-domain collaborative filtering.  IEEE Transactions on image processing, 16(8):2080–2095, 2007.
  * [9] M. Delbracio and G. Sapiro.  Hand-Held Video Deblurring Via Efficient Fourier Aggregation.  Computational Imaging, IEEE Transactions on, 1(4):270–283, Dec 2015\.
  * [10] M. Delbracio and G. Sapiro.  Removing Camera Shake via Weighted Fourier Burst Accumulation.  Image Processing, IEEE Transactions on, 24(11):3293–3307, Nov 2015\.
  * [11] Rafael C Gonzalez and Richard E Wood.  Digital image processing, 2nd edtn.
  * [12] A. A. Goshtasby.  Fusion of multi-exposure images.  Image Vision Comput., 23(6):611–618, June 2005.
  * [13] Bo Gu, Wujing Li, Jiangtao Wong, Minyun Zhu, and Minghui Wang.  Gradient field multi-exposure images fusion for high dynamic range image visualization.  Journal of Visual Communication and Image Representation, 23(4):604 – 610, 2012.
  * [14] David Hafner and Joachim Weickert.  Variational exposure fusion with optimal local contrast.  In International Conference on Scale Space and Variational Methods in Computer Vision, pages 425–436. Springer, 2015.
  * [15] Gloria Haro, Antoni Buades, and Jean-Michel Morel.  Photographing paintings by image fusion.  SIAM Journal on Imaging Sciences, 5(3):1055–1087, 2012.
  * [16] Naila Hayat and Muhammad Imran.  Ghost-free multi exposure image fusion technique using dense sift descriptor and guided filter.  Journal of Visual Communication and Image Representation, 62:295 – 308, 2019.
  * [17] Kaiming He, Jian Sun, and Xiaoou Tang.  Guided image filtering.  IEEE transactions on pattern analysis and machine intelligence, 35(6):1397–1409, 2013.
  * [18] Charles Hessel.  Extended Exposure Fusion.  Image Processing On Line, 9:453–468, 2019.
  * [19] Jun Hu, Orazio Gallo, and Kari Pulli.  Exposure stacks of live scenes with hand-held cameras.  Computer Vision–ECCV 2012, pages 499–512, 2012.
  * [20] Jun Hu, Orazio Gallo, Kari Pulli, and Xiaobai Sun.  Hdr deghosting: How to deal with saturation?  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1163–1170, 2013.
  * [21] Neel Joshi and Michael F Cohen.  Seeing mt. rainier: Lucky imaging for multi-image denoising, sharpening, and haze removal.  In Computational Photography (ICCP), 2010 IEEE International Conference on, pages 1–8. IEEE, 2010.
  * [22] Nima Khademi Kalantari and Ravi Ramamoorthi.  Deep high dynamic range imaging of dynamic scenes.  ACM Trans. Graph., 36(4):144–1, 2017.
  * [23] Fei Kou, Zhengguo Li, Changyun Wen, and Weihai Chen.  Multi-scale exposure fusion via gradient domain guided image filtering.  In 2017 IEEE International Conference on Multimedia and Expo (ICME), pages 1105–1110. IEEE, 2017.
  * [24] Fei Kou, Zhengguo Li, Changyun Wen, and Weihai Chen.  Edge-preserving smoothing pyramid based multi-scale exposure fusion.  Journal of Visual Communication and Image Representation, 53:235–244, 2018.
  * [25] Jung Gap Kuk, Nam Ik Cho, and Sang Uk Lee.  High dynamic range (hdr) imaging by gradient domain fusion.  In Acoustics, Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on, pages 1461–1464. IEEE, 2011.
  * [26] Valero Laparra, Alexander Berardino, Johannes Ballé, and Eero P Simoncelli.  Perceptually optimized image rendering.  JOSA A, 34(9):1511–1525, 2017.
  * [27] Marc Lebrun.  An Analysis and Implementation of the BM3D Image Denoising Method.  Image Processing On Line, 2:175–213, 2012.  https://doi.org/10.5201/ipol.2012.l-bm3d.
  * [28] Dong-Kyu Lee, Rae-Hong Park, and Soonkeun Chang.  Ghost and noise removal in exposure fusion for high dynamic range imaging.  International Journal of Computer Graphics & Animation, 4(4):1, 2014.
  * [29] H. Li and L. Zhang.  Multi-exposure fusion with cnn features.  In 2018 25th IEEE International Conference on Image Processing (ICIP), pages 1723–1727, 2018.
  * [30] S. Li, X. Kang, and J. Hu.  Image fusion with guided filtering.  IEEE Trans. Image Processing, 22(7):2864–2875, 2013.
  * [31] Shutao Li and Xudong Kang.  Fast multi-exposure image fusion with median filter and recursive filter.  IEEE Transactions on Consumer Electronics, 58(2), 2012.
  * [32] Z. Li, Z. Wei, C. Wen, and J. Zheng.  Detail-enhanced multi-scale exposure fusion.  IEEE Transactions on Image Processing, 26(3):1243–1252, March 2017\.
  * [33] Z. G. Li, J. H. Zheng, and S. Rahardja.  Detail-enhanced exposure fusion.  IEEE Trans. Image Processing, 21(11):4672–4676, 2012.
  * [34] Zhengguo Li, Jinghong Zheng, Zijian Zhu, and Shiqian Wu.  Selectively detail-enhanced fusion of differently exposed images with moving objects.  IEEE Transactions on Image Processing, 23(10):4372–4382, 2014.
  * [35] Yu Liu and Zengfu Wang.  Dense sift for ghost-free multi-exposure fusion.  Journal of Visual Communication and Image Representation, 31:208–224, 2015.
  * [36] Kede Ma, Zhengfang Duanmu, Hojatollah Yeganeh, and Zhou Wang.  Multi-exposure image fusion by optimizing a structural similarity index.  IEEE Transactions on Computational Imaging, 4(1):60–72, 2018.
  * [37] Kede Ma, Hui Li, Hongwei Yong, Zhou Wang, Deyu Meng, and Lei Zhang.  Robust multi-exposure image fusion: A structural patch decomposition approach.  IEEE Trans. Image Processing, 26(5):2519–2532, 2017.
  * [38] Kede Ma, Hojatollah Yeganeh, Kai Zeng, and Zhou Wang.  High dynamic range image compression by optimizing tone mapped image quality index.  IEEE Transactions on Image Processing, 24(10):3086–3097, 2015.
  * [39] Kede Ma, Kai Zeng, and Zhou Wang.  Perceptual quality assessment for multi-exposure image fusion.  IEEE Transactions on Image Processing, 24(11):3345–3356, 2015.
  * [40] Onofre Martorell, Catalina Sbert, and Antoni Buades.  Ghosting-free dct based multi-exposure image fusion.  Signal Processing: Image Communication, 78:409–425, 2019.
  * [41] T. Mertens, J. Kautz, and F. Van Reeth.  Exposure Fusion: A Simple and Practical Alternative to High Dynamic Range Photography.  Computer Graphics Forum, 2009.
  * [42] Tom Mertens, Jan Kautz, and Frank Van Reeth.  Exposure fusion.  In Proceedings of the 15th Pacific Conference on Computer Graphics and Applications, PG ’07, pages 382–390, Washington, DC, USA, 2007\. IEEE Computer Society.
  * [43] Tae-Hong Min, Rae-Hong Park, and SoonKeun Chang.  Noise reduction in high dynamic range images.  Signal, Image and Video Processing, 5(3):315–328, 2011.
  * [44] Cristian Ocampo-Blandon and Yann Gousseau.  Non-local exposure fusion.  In Iberoamerican Congress on Pattern Recognition, pages 484–492. Springer, 2016.
  * [45] Sujoy Paul, Ioana S. Sevcenco, and P. Agathoklis.  Multi-exposure and multi-focus image fusion in gradient domain.  J. Circuits Syst. Comput., 25:1650123:1–1650123:18, 2016.
  * [46] Sujoy Paul, Ioana S Sevcenco, and Panajotis Agathoklis.  Multi-exposure and multi-focus image fusion in gradient domain.  Journal of Circuits, Systems and Computers, 25(10):1650123, 2016\.
  * [47] Patrick Pérez, Michel Gangnet, and Andrew Blake.  Poisson image editing.  In ACM Transactions on graphics (TOG), volume 22, pages 313–318. ACM, 2003.
  * [48] Gemma Piella.  Image fusion for enhanced visualization: A variational approach.  International Journal of Computer Vision, 83(1):1–11, 2009.
  * [49] K Ram Prabhakar, Rajat Arora, Kunal Pratap Singh, and R Venkatesh Babu.  A fast, scalable and reliable deghosting method for extreme exposure fusion.  In 2019 IEEE International Conference on Computational Photography (ICCP). IEEE, 2019.
  * [50] K Ram Prabhakar and R Venkatesh Babu.  Ghosting-free multi-exposure image fusion in gradient domain.  In Acoustics, Speech and Signal Processing (ICASSP), 2016 IEEE International Conference on, pages 1766–1770. IEEE, 2016.
  * [51] K Ram Prabhakar, V Sai Srikar, and R Venkatesh Babu.  Deepfuse: A deep unsupervised approach for exposure fusion with extreme exposure image pairs.  In ICCV, pages 4724–4732, 2017.
  * [52] Shanmuganathan Raman and Subhasis Chaudhuri.  Bilateral Filter Based Compositing for Variable Exposure Photography.  In P. Alliez and M. Magnor, editors, Eurographics 2009 - Short Papers. The Eurographics Association, 2009.
  * [53] Ramesh Raskar, Adrian Ilie, and Jingyi Yu.  Image fusion for context enhancement and video surrealism.  In ACM SIGGRAPH 2005 Courses, page 4. ACM, 2005.
  * [54] Alex Rav-Acha and Shmuel Peleg.  Two motion-blurred images are better than one.  Pattern recognition letters, 26(3):311–317, 2005.
  * [55] Wei-Rong Sie and Chiou-Ting Hsu.  Alignment-free exposure fusion of image pairs.  In Image Processing (ICIP), 2014 IEEE International Conference on, pages 1802–1806. IEEE, 2014.
  * [56] H. Singh, V. Kumar, and S. Bhooshan.  A novel approach for detail-enhanced exposure fusion using guided filter.  The Scientific World Journal, 2014(659217):8, 2014.
  * [57] Jian Sun, Hongyan Zhu, Zongben Xu, and Chongzhao Han.  Poisson image fusion based on markov random field fusion model.  Information fusion, 14(3):241–254, 2013.
  * [58] Marius Tico, Natasha Gelfand, and Kari Pulli.  Motion-blur-free exposure fusion.  In Image Processing (ICIP), 2010 17th IEEE International Conference on, pages 3321–3324. IEEE, 2010.
  * [59] Carlo Tomasi and Roberto Manduchi.  Bilateral filtering for gray and color images.  In Computer Vision, 1998. Sixth International Conference on, pages 839–846. IEEE, 1998.
  * [60] Shangzhe Wu, Jiarui Xu, Yu-Wing Tai, and Chi-Keung Tang.  Deep high dynamic range imaging with large foreground motions.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 117–132, 2018.
  * [61] Han Xu, Jiayi Ma, Junjun Jiang, Xiaojie Guo, and Haibin Ling.  U2fusion: A unified unsupervised image fusion network.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020\.
  * [62] Kai Zeng, Kede Ma, R. Hassen, and Z. Wang.  Perceptual evaluation of multi-exposure image fusion algorithms.  In 2014 Sixth International Workshop on Quality of Multimedia Experience (QoMEX), pages 7–12, Sept 2014.
  * [63] Wei Zhang and Wai-Kuen Cham.  Gradient-directed multiexposure composition.  IEEE Transactions on Image Processing, 21(4):2318–2323, 2012.
  * [64] Wei Zhang, Shengnan Hu, and Kan Liu.  Patch-based correlation for deghosting in exposure fusion.  Information Sciences, 415:19–27, 2017.
  * [65] Wei Zhang, Shengnan Hu, Kan Liu, and Jian Yao.  Motion-free exposure fusion based on inter-consistency and intra-consistency.  Information Sciences, 376:190–201, 2017.
  * [66] Yu Zhang, Yu Liu, Peng Sun, Han Yan, Xiaolin Zhao, and Li Zhang.  Ifcnn: A general image fusion framework based on convolutional neural network.  Information Fusion, 54:99 – 118, 2020.
  * [67] Jinghong Zheng and Zhengguo Li.  Superpixel based patch match for differently exposed images with moving objects and camera movements.  In 2015 IEEE International Conference on Image Processing (ICIP), pages 4516–4520. IEEE, 2015.