C++

Forum

 
Seam Carving using DP

Mae4ashy (29)
Hello together!

I'm currently working on an implementation of the Seam Carving Algorithm, using Dynamic Programming. But sadly my function that is supposed to get the Seam with the lowest Energy doesn't seem to choose the lowest-energy-seam. There is always an offset of about 3 to 4 points in the energy value. So for example the seam has energy of 8.17 when it is supposed to have an energy of 4.15.

This is my code so far:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
  // the DP algorithm
// compute and return the minimum energy vertical seam in an array
// the returned vector contains at position y the x-coordinate to y

std::vector<unsigned> GetMinSeam(const Array& array){
  unsigned w = array.Width();
  unsigned h = array.Height();
  std::vector<unsigned> seam(h);
  
  Array e = energies(array); //Array containing all the energies
  Array dp (w-1,h-2); //dp-table
  
  double min = std::numeric_limits<double>::max();
  
  for(unsigned int j=0; j<w-1; ++j){
    dp(j,0) = e(j,0);
  }
  
  for(unsigned int j=1; j<h-2; ++j){ //calculate dp-table
    for(unsigned int i=0; i<w-1; ++i){
      if(i==0){
        dp(i,j) = e(i,j) + std::min(dp(i,j-1), dp(i+1,j-1));
      }
      else if(i==w-2){
        dp(i,j) = e(i,j) + std::min(dp(i,j-1), dp(i-1, j-1));
      }
      else{
        double t = std::min(dp(i,j-1), dp(i-1,j-1));
        dp(i,j) = e(i,j) + std::min(t, dp(i+1, j-1));
      }
    }
  }

  unsigned p,o; //search for lowest energy in last row of dp-table
  for(o=0; o<w-1; ++o){
    if(dp(o, h-3) < min){
      min = dp(o,h-3);
      p = o;
    }
  }
  seam.at(h-2) = o;
  
  int u;
  for(int k = h-3; k>0; --k){ //reconstruct the way of lowest energy in dp-table
    if(p == w-2){
      if(dp(p,k-1)<dp(p-1,k-1)){
        seam.at(k) = p;
      }
      else{
        seam.at(k) = p-1;
        p = p-1;
      }
    }
    else if(p == 0){
      if(dp(p,k-1)<dp(p+1,k-1)){
        seam.at(k) = p;
      }
      else{
        seam.at(k) = p+1;
        p = p+1;
      }
    }
    else{
      if(dp(p-1,k-1)<dp(p,k-1)){
        u = p-1;
      }
      else{
        u = p;
      }
      if(dp(u,k-1)<dp(p+1,k-1)){
        seam.at(k) = u;
        p = u;
      }
      else{
        seam.at(k)=p+1;
        p = p+1;
      }
    }
  }
  
  return seam;
}


The Array is a class, that consists of two unsigned values, width and height, as well as the data the cells are holding. There are functions for accessing those values and an overloaded operator "=".

I've tried a lot, but I don't know where the problem is, so I really hope that someone here can take a look and maybe help find the fault.

Thanks a lot!
lastchance (6980)
Why don't you print out your dp() table to debug it? You can use a simple replacement energy function (linear or V shape perhaps) and keep width and height small.

Don't try to compute your seam until the dp() table is correct; otherwise you are conflating two separate problems and it's hard to debug

Print p and min after line 40.

Your dp() table "looks" correct (provided the energies are correct); however, I'm not convinced that your back-tracing of the seam is.

Can you give us some complete code to run? (Simplify the energy function as above). Apart from anything else, you can't guarantee that the error isn't in a different bit of code; (your energies() routine is the prime candidate - you need to do a unit test on that alone).

Please try to use the same counting variable in each direction (e.g. lines 15-17 would more naturally have used i than j).



seam.at(h-2) = o;
You've just found the minimum energy in row h-3. Why are you indexing the seam at h-2?
Last edited on
Mae4ashy (29)
Okay, so this is my energy function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
double energy(const Array& array, unsigned x, unsigned y){
  if ((x == 0 || x == array.Width() - 1) && (y == 0 || y == array.Height() - 1))
    return 1; // max distance at the corners
  // otherwise: sum of all (available) surrounding pixels
  double result = 0;
  if (x > 0)
    result += distance(array(x, y), array(x - 1, y));
  if (x < array.Width() - 1)
    result += distance(array(x, y), array(x + 1, y));
  if (y > 0)
    result += distance(array(x, y), array(x, y - 1));
  if (y < array.Height() - 1)
    result += distance(array(x, y), array(x, y + 1));
  return result;
}


It is using a distance-function, that just calculates std::abs() of two double values. The energies function i used before is just using this function above to compute the energy of a whole array.

I altered the problems you talked about in line 15-17 and line 41 and i added a print after line 40. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
class Array{
    private:
    double* data = nullptr;
    unsigned int width;
    unsigned int height;
    
    void swap(Array& a);

public:
   Array::Array(unsigned int w, unsigned int h): width{w}, height{h} {
        data = new double[width*height];
    }
   Array::Array(const Array& a): width{a.width}, height{a.height}{
        data = new double[width*height];
        std::copy(a.data, a.data + width*height, data);
    }
   Array::~Array(){
        assert(data != nullptr);
        delete[] data;
   }
    
    Array& operator=(const Array& a);
    
    double& Array::operator()(unsigned int x, unsigned int y){
        assert(x < width);
        assert(y < height);
        return data[y*width+x];
    }
    
    unsigned int Width() const; //returns width

    unsigned int Height() const; //returns height
};

double GetSeamEnergy(const Array& array, const std::vector<unsigned>& seam){
  double total = 0;
  for (unsigned y = 0; y < seam.size(); ++y){
    total += energy(array,seam[y],y);
  }
  return total;
}

void cut_x(const Array& array, Array& copy, unsigned omit, unsigned y){
  for (unsigned x = 0; x != omit; ++x){
    copy(x,y) = array(x,y);
  }
  for (unsigned x = omit+1; x != array.Width(); ++x){
    copy(x-1,y) = array(x,y);
  }
}


Array SeamCut(const Array& array, const std::vector<unsigned>& seam){
  unsigned w = array.Width();
  unsigned h = array.Height();
  Array copy(w-1,h);
  
  for(std::size_t i = 0; i<h-1; ++i){
    cut_x(array, copy, seam.at(i), i);
  }

  return copy;
}

int main(){

  unsigned iterations, seams;  

  Array img = 
  std::cin << iterations;
  std::cin << seams;

   Array result = img;
   for (unsigned i = 1; i <= iterations; ++i){
      double energy = 0;
      for (unsigned j = 1; j <= seams; ++j){
        std::vector<unsigned> seam = GetMinSeam(result);
        energy = GetSeamEnergy(result, seam);
        result = SeamCut(result, seam);
      }
  std::cout << energy;
}
  return 0;
}


So here I added the class that I'm using as data structure plus a hopefully working easier main function. I left the Array img = empty, so that you can add whatever you want to use for reading the image.

The energies function is working just fine, so if you're saying the computing of my dp table looks fine, then the problem will be most likely in the backtracing of the seam.

Thanks a lot for your help!
lastchance (6980)
You already calculated the total energy of the seam in the last row of GetMinSeam:
1
2
3
4
5
6
7
 
  unsigned p,o; //search for lowest energy in last row of dp-table
  for(o=0; o<w-1; ++o){
    if(dp(o, h-3) < min){
      min = dp(o,h-3);           // <==== HERE
      p = o;
    }
  }



Why are you trying to do it again in
1
2
3
4
5
6
7
 
double GetSeamEnergy(const Array& array, const std::vector<unsigned>& seam){
  double total = 0;
  for (unsigned y = 0; y < seam.size(); ++y){
    total += energy(array,seam[y],y);
  }
  return total;
}

?



Also, in GetMinSeam(), which finds minimum summative energy in row h-3
seam.at(h-2) = o;
Did you mean
seam.at(h-2) = p; <==== p, not o
or even
seam.at(h-3) = p; <==== h-3, not h-2


If you want to check the minimum-energy summation CHECK THE ELEMENTS IN THE LAST ROW OF YOUR dp-table FIRST.
Last edited on
Mae4ashy (29)
The seam is a vector that stores in every cell the x value to the corresponding y value seam[y] while x < width and y < height. So in GetMinSeam I'm backtracing those values by looking for the path with the minimum energy in the dp-table, starting with traversing through the last row of the dp table to find the minimum value there and then looking at the values above that one.

GetSeamEnergy is a function to return the total energy of the seam, to check if the seam was calculated correctly or if it is not the minimal seam.

Yes, that's right, it has to be p and not o in line 41. I went through all the indices again and changed some. Now the energy value has gotten a bit better. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
std::vector<unsigned> GetMinSeam(const Array& array){
  unsigned w = array.Width();
  unsigned h = array.Height();
  std::vector<unsigned> seam(h);
  
  Array e = energies(array);
  Array dp (w,h); 
  
  double min = std::numeric_limits<double>::max();
  
  for(unsigned int i=0; i<w; ++i){
    dp(i,0) = e(i,0);
  }
  
  for(unsigned int j=1; j<h-1; ++j){ 
    for(unsigned int i=0; i<w; ++i){
      if(i==0){
        dp(i,j) = e(i,j) + std::min(dp(i,j-1), dp(i+1,j-1));
      }
      else if(i==w-1){
        dp(i,j) = e(i,j) + std::min(dp(i,j-1), dp(i-1, j-1));
      }
      else{
        double t = std::min(dp(i,j-1), dp(i-1,j-1));
        dp(i,j) = e(i,j) + std::min(t, dp(i+1, j-1));
      }
    }
  }

  unsigned p,o;
  for(o=0; o<w; ++o){
    if(dp(o, h-1) < min){ //i changed that cause i gave the seam length h
      min = dp(o,h-1);
      p = o;
    }
  }
  
  std::cerr << min << " " << p << std::endl;
  seam.at(h-1) = p; //changed that as well, thanks for telling :)
  
  int u;
  for(int k = h-1; k>0; --k){
    if(p == w-1){
      if(dp(p,k-1)<dp(p-1,k-1)){
        seam.at(k-1) = p; //that didn't match as well
      }
      else{
        seam.at(k-1) = p-1;
        p = p-1;
      }
    }
    else if(p == 0){
      if(dp(p,k-1)<=dp(p+1,k-1)){
        seam.at(k-1) = p;
      }
      else{
        seam.at(k-1) = p+1;
        p = p+1;
      }
    }
    else{
      if(dp(p-1,k-1)<=dp(p,k-1)){
        u = p-1;
      }
      else{
        u = p;
      }
      if(dp(u,k-1)<=dp(p+1,k-1)){
        seam.at(k-1) = u;
        p = u;
      }
      else{
        seam.at(k-1)=p+1;
        p = p+1;
      }
    }
  }
  
  std::cerr << GetSeamEnergy(array,seam) << " " << std::endl;
  
  return seam;
}


How can I check the elements in the last row of my dp-table?
lastchance (6980)
Just print them out!

Pick a small example and do it by hand. Check your calculations: i.e. print out dp[][] and the seam.

Isn't your seam energy supposed to be the same as min? Which (if either) gives the correct answer?
Mae4ashy (29)
Yes that is right. I just used the GetSeamEnergy function to check if my Seam gets the same value. And i just realized, that I printed min and it is absolutely not the same value.

Seems like it is time to check the dp-table :)
Mae4ashy (29)
I found something strange. The min I get is 0, but there is no 0 in the last row of the dp-table.

And if I put (dp(o,h-1) <= min) I get 0 again, but this time there is another p. How can that happen, if i just calculate it after printing my dp-table?

Edit: It is working now, when I only remove one seam. I don't really know why there should be a problem for several seams, cause then it should only call on the function several times, but at least there is some progress :D
Or maybe it isn't removing the previous seam properly.
Last edited on
Mae4ashy (29)
Thanks a lot for the good help, i figured it out now :)))
Topic archived. No new replies allowed.