What is a seam (Seam-carving)

Question

I am reading the paper about seam carving for resizing an image.

Down on page 3 where they define a seam mathematically, I need help clarifying it.

The paper says that a seam is an 8-connected path of pixels. How can it be 8-connected if the pixel cannot be on the same row? Shouldn't it be 3-connected?

http://www.seamcarving.com/arik/imret.pdf 20 mb PDF

Answer 1

8-connected path of pixels means that all the 8 neighbors o around a pixel x:

ooo
oxo
ooo (1)

count in determining if the pixel is connected. so the x in

xoo
oxo
oox (2)

are 8-connected. in contrast, 4-connected looks only at these 4 neighbors o:

 o
oxo
 o  (3)

under this scheme, the x in fig. 2 would not considered to be connected.

(there is no 3-connected in computer graphics (that i know of))

this being said, the definition of a vertical seam:

a vertical seam is an 8-connected path of pixels in the image from top to bottom, containing one, and only one, pixel in each row of the image

seems quite easy to grasp to me. this:

x
 x
  x

is a vertical seam (because there is only one pixel per row), also:

x
 x
 x

this is; this:

x
 xx
  x

is not (because there are two pixel in row two).

hope that helps.

Answer 2

It won't be 3 connected, it would be 6 connected but since there is nothing called 6 connected path, this is called 8-connected

(The '6' is referring to the 6 potential neighbours of a given pixel - 3 in the row above and 3 in the row below:)

xxx
 o
xxx