Olá João,
Desculpem pela demora.
Gostaria de saber se no contexto desse EP existe um único output considerado correto
Legal!
Dependendo do digrafo e dos comprimentos dos seus arcos há mais que um caminho mínimo.
Por causa da falta de unicidade é que frequentemente usamos o artigo indefinido, apesar de ser meio pedante:
uma floresta DFS, um caminho mínimo, uma ordenação topológica, uma bipartição de um grafo,...
pois percebi que o meu SeamCarver produz uma imagem ligeiramente
Excelente!
Nesse caso devemos fazer testes pequenos para os quais visualmente podemos ver a solução.
O pessoal de COS226 diponibilizou vários arquivos para testes:
% ls *.png
10x10.png 10x12.png 12x10.png 1x1.png
1x8.png 3x4.png 3x7.png 4x6.png
5x6.png 6x5.png 7x10.png 7x3.png
8x1.png chameleon.png diagonals.png HJocean.png
HJoceanSmall.png HJoceanTransposed.png stripes.png
% ls *.txt
10x10.printseams.txt 10x12.printseams.txt 12x10.printseams.txt
3x4.printseams.txt 3x7.printseams.txt 4x6.printseams.txt
5x6.printseams.txt 6x5.printseams.txt 7x10.printseams.txt
7x3.printseams.txt diagonals.printseams.txt readme.txt
stripes.printseams.txt
mas em alguns pontos da imagem (principalmente áreas de baixa energia, céu/mar/etc.) ocorrem pequenas flutuações em relação ao exemplo.
Hmm.
Talvez você ja tenha feito isso, mas eu testaria o programa com os testes disponibilisados pelo pessoal de COS226.
Devemos nos preocupar se o cálcula da energia está correto e se nosso programa encontra um caminho mínimo.
Podemos ter vários caminhos mínimos, mas o comprimento do caminho mínimo é único para cada matriz de energia.
deveria me esforçar para obter uma imagem que seja pixel a pixel idêntica ao exemplo?
Devemos apenas procurar fazer os cálculos da energia corretamente e encontrar um caminho mínimo.
Exemplos
Notem que para diagonals.png há vários caminhos mínimos.
% java PrintSeams ../seamCarving/1x8.png
../seamCarving/1x8.png (1-by-8 image)
The table gives the dual-gradient energies of each pixel.
The asterisks denote a minimum energy vertical or horizontal seam.
Vertical seam: { 0 0 0 0 0 0 0 0 }
13.67*
13.60*
9.11*
6.48*
5.83*
9.64*
17.83*
10.49*
Total energy = 86.662685
Horizontal seam: { 4 }
13.67
13.60
9.11
6.48
5.83*
9.64
17.83
10.49
Total energy = 5.830952
% java PrintSeams 3x7.png
../seamCarving/3x7.png (3-by-7 image)
The table gives the dual-gradient energies of each pixel.
The asterisks denote a minimum energy vertical or horizontal seam.
Vertical seam: { 1 2 2 2 1 2 2 }
212.11 174.62* 175.13
283.29 294.32 173.45*
354.33 236.17 199.07*
194.42 325.15 166.88*
232.09 251.36* 309.88
320.38 279.64 241.34*
185.98 237.05 214.15*
Total energy = 1420.871702
Horizontal seam: { 0 0 1 }
212.11* 174.62* 175.13
283.29 294.32 173.45*
354.33 236.17 199.07
194.42 325.15 166.88
232.09 251.36 309.88
320.38 279.64 241.34
185.98 237.05 214.15
Total energy = 560.178311
% more ../seamCarving/3x7.printseams.txt
3x7.png (3-by-7 image)
The table gives the dual-gradient energies of each pixel.
The asterisks denote a minimum energy vertical or horizontal seam.
Vertical seam: { 1 2 2 2 1 2 2 }
212.11 174.62* 175.13
283.29 294.32 173.45*
354.33 236.17 199.07*
194.42 325.15 166.88*
232.09 251.36* 309.88
320.38 279.64 241.34*
185.98 237.05 214.15*
Total energy = 1420.871702
Horizontal seam: { 0 0 1 }
212.11* 174.62* 175.13
283.29 294.32 173.45*
354.33 236.17 199.07
194.42 325.15 166.88
232.09 251.36 309.88
320.38 279.64 241.34
185.98 237.05 214.15
Total energy = 560.178311
% java PrintSeams diagonals.png
../seamCarving/diagonals.png (9-by-12 image)
The table gives the dual-gradient energies of each pixel.
The asterisks denote a minimum energy vertical or horizontal seam.
Vertical seam: { 0 1 0 1 0 1 0 1 0 1 0 0 }
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62* 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62* 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62* 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62* 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62* 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
Total energy = 6397.757042
Horizontal seam: { 4 3 3 3 3 3 3 2 1 }
441.67 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67*
441.67 624.62 624.62 624.62 624.62 624.62 624.62 624.62* 624.62
624.62 624.62* 624.62* 624.62* 624.62* 624.62* 624.62* 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
Total energy = 5255.685103
% more ../seamCarving/diagonals.printseams.txt
diagonals.png (9-by-12 image)
The table gives the dual-gradient energies of each pixel.
The asterisks denote a minimum energy vertical or horizontal seam.
Vertical seam: { 0 0 0 0 0 0 0 0 0 0 0 0 }
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62* 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
Total energy = 6397.757042
Horizontal seam: { 0 0 0 0 0 0 0 0 1 }
441.67* 624.62* 624.62* 624.62* 624.62* 624.62* 624.62* 624.62* 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67*
441.67 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
441.67 624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62
624.62 624.62 624.62 624.62 624.62 624.62 624.62 624.62 441.67
Total energy = 5255.685103
% java PrintSeams 7x3.png
../seamCarving/7x3.png (7-by-3 image)
The table gives the dual-gradient energies of each pixel.
The asterisks denote a minimum energy vertical or horizontal seam.
Vertical seam: { 4 4 5 }
222.73 245.24 195.44 248.92 159.43* 238.59 215.45
385.96 237.12 268.77 218.95 265.27* 292.37 220.30
214.95 319.16 244.78 234.13 307.13 161.68* 301.30
Total energy = 586.385509
Horizontal seam: { 2 1 0 1 0 0 0 }
222.73 245.24 195.44* 248.92 159.43* 238.59* 215.45*
385.96 237.12* 268.77 218.95* 265.27 292.37 220.30
214.95* 319.16 244.78 234.13 307.13 161.68 301.30
Total energy = 1479.942484
% more 7x3.printseams.txt
7x3.png (7-by-3 image)
The table gives the dual-gradient energies of each pixel.
The asterisks denote a minimum energy vertical or horizontal seam.
Vertical seam: { 4 4 5 }
222.73 245.24 195.44 248.92 159.43* 238.59 215.45
385.96 237.12 268.77 218.95 265.27* 292.37 220.30
214.95 319.16 244.78 234.13 307.13 161.68* 301.30
Total energy = 586.385509
Horizontal seam: { 2 1 0 1 0 0 0 }
222.73 245.24 195.44* 248.92 159.43* 238.59* 215.45*
385.96 237.12* 268.77 218.95* 265.27 292.37 220.30
214.95* 319.16 244.78 234.13 307.13 161.68 301.30
Total energy = 1479.942484
% java PrintSeams 10x10.png
../seamCarving/10x10.png (10-by-10 image)
The table gives the dual-gradient energies of each pixel.
The asterisks denote a minimum energy vertical or horizontal seam.
Vertical seam: { 8 7 7 7 7 8 9 8 7 7 }
335.29 197.20 231.08 194.09 222.00 226.00 244.63 260.37 169.43* 254.98
275.95 136.73 272.84 254.64 280.20 178.56 236.84 128.93* 172.62 248.20
183.01 222.06 156.22 186.79 208.01 171.06 295.56 125.46* 259.00 231.78
248.53 228.47 252.25 168.24 164.97 127.18 209.46 202.49* 229.03 232.27
260.02 293.85 274.51 217.81 165.63 175.67 223.37 194.78* 243.35 217.28
117.69 208.68 294.31 243.53 161.69 253.29 236.73 217.57 221.35* 197.18
335.71 318.51 222.38 240.88 239.79 220.45 259.36 269.76 264.14 200.68*
271.41 225.20 270.73 187.06 197.58 165.59 255.09 276.89 124.04* 298.57
259.57 222.50 204.43 252.65 270.87 199.05 324.13 90.64* 245.94 248.36
272.10 324.87 216.40 218.43 177.66 174.61 178.31 125.05* 228.36 240.44
Total energy = 1582.861250
Horizontal seam: { 2 1 2 3 3 3 3 2 1 2 }
335.29 197.20 231.08 194.09 222.00 226.00 244.63 260.37 169.43 254.98
275.95 136.73* 272.84 254.64 280.20 178.56 236.84 128.93 172.62* 248.20
183.01* 222.06 156.22* 186.79 208.01 171.06 295.56 125.46* 259.00 231.78*
248.53 228.47 252.25 168.24* 164.97* 127.18* 209.46* 202.49 229.03 232.27
260.02 293.85 274.51 217.81 165.63 175.67 223.37 194.78 243.35 217.28
117.69 208.68 294.31 243.53 161.69 253.29 236.73 217.57 221.35 197.18
335.71 318.51 222.38 240.88 239.79 220.45 259.36 269.76 264.14 200.68
271.41 225.20 270.73 187.06 197.58 165.59 255.09 276.89 124.04 298.57
259.57 222.50 204.43 252.65 270.87 199.05 324.13 90.64 245.94 248.36
272.10 324.87 216.40 218.43 177.66 174.61 178.31 125.05 228.36 240.44
Total energy = 1675.680600
% more 10x10.printseams.txt
10x10.png (10-by-10 image)
The table gives the dual-gradient energies of each pixel.
The asterisks denote a minimum energy vertical or horizontal seam.
Vertical seam: { 8 7 7 7 7 8 9 8 7 7 }
335.29 197.20 231.08 194.09 222.00 226.00 244.63 260.37 169.43* 254.98
275.95 136.73 272.84 254.64 280.20 178.56 236.84 128.93* 172.62 248.20
183.01 222.06 156.22 186.79 208.01 171.06 295.56 125.46* 259.00 231.78
248.53 228.47 252.25 168.24 164.97 127.18 209.46 202.49* 229.03 232.27
260.02 293.85 274.51 217.81 165.63 175.67 223.37 194.78* 243.35 217.28
117.69 208.68 294.31 243.53 161.69 253.29 236.73 217.57 221.35* 197.18
335.71 318.51 222.38 240.88 239.79 220.45 259.36 269.76 264.14 200.68*
271.41 225.20 270.73 187.06 197.58 165.59 255.09 276.89 124.04* 298.57
259.57 222.50 204.43 252.65 270.87 199.05 324.13 90.64* 245.94 248.36
272.10 324.87 216.40 218.43 177.66 174.61 178.31 125.05* 228.36 240.44
Total energy = 1582.861250
Horizontal seam: { 2 1 2 3 3 3 3 2 1 2 }
335.29 197.20 231.08 194.09 222.00 226.00 244.63 260.37 169.43 254.98
275.95 136.73* 272.84 254.64 280.20 178.56 236.84 128.93 172.62* 248.20
183.01* 222.06 156.22* 186.79 208.01 171.06 295.56 125.46* 259.00 231.78*
248.53 228.47 252.25 168.24* 164.97* 127.18* 209.46* 202.49 229.03 232.27
260.02 293.85 274.51 217.81 165.63 175.67 223.37 194.78 243.35 217.28
117.69 208.68 294.31 243.53 161.69 253.29 236.73 217.57 221.35 197.18
335.71 318.51 222.38 240.88 239.79 220.45 259.36 269.76 264.14 200.68
271.41 225.20 270.73 187.06 197.58 165.59 255.09 276.89 124.04 298.57
259.57 222.50 204.43 252.65 270.87 199.05 324.13 90.64 245.94 248.36
272.10 324.87 216.40 218.43 177.66 174.61 178.31 125.05 228.36 240.44
Total energy = 1675.680600
