Border Tracing
AssigneeString Labs Limited
InventorJohan Øverbye
Life of this patent
Estimating the term…
Abstract
A method for scanning for borders in an image represented by pixels, the method including a first operation comprising: estimating an attribute for each of a first set of two adjacent pixel positions in the image; assessing whether a predetermined binary condition differs in respect of the two pixel positions, and if so determining that a border is present in the part of the image represented by pixels at those positions; and if a border is determined to be present in that part of the image, estimating the direction of the border as being perpendicular to a line joining the positions of the two pixels; and initiating tracing the border in that direction.
Claims29
A method for scanning for borders in an image represented by pixels, the method including a first operation comprising:
- estimating an attribute for each of a first set of two adjacent pixel positions in the image;
- assessing whether a predetermined binary condition differs in respect of the two pixel positions, and if so determining that a border is present in the part of the image represented by pixels at those positions;
- and
- if a border is determined to be present in that part of the image, estimating the direction of the border as being perpendicular to a line joining the positions of the two pixels;
- and initiating tracing the border in that direction.
A method as claimed in any preceding claim, comprising tracing the border in the estimated direction by the steps of:
- selecting a second set of two adjacent pixel positions, each of those pixel positions being adjacent to a respective one of the pixel positions of the first set and offset from that pixel position of the first set in the estimated direction;
- estimating an attribute for each of the pixel positions of the second set;
- estimating a new direction of the border in dependence on the attributes of second set of pixel positions;
- and subsequently further tracing the border.
A method as claimed in any preceding claim, wherein the attribute of each pixel position is dependent on data defining the image as represented in a plurality of pixels neighbouring that pixel position.
A method as claimed in any preceding claim, wherein the attribute of each pixel position is based on a weighted sum of a value of the pixel at that position and plurality of pixels neighbouring that pixel position.
A method as claimed in any preceding claim, wherein the attribute of each pixel position is based on a Laplacian of Gaussian filter applied to the image and centred on the pixel position.
A method as claimed in any preceding claim, wherein the attribute of each pixel position is based on an estimation of the second-order derivative of an isotropic Gaussian convolution applied to one or more visual attributes of pixels of the image with respect to the direction of the gradient of the Gaussian
A method as claimed in any preceding claim, wherein the said first operation comprises:
- if a border is not determined to be present in that part of the image initiating a further iteration of the first operation for two adjacent pixel positions offset in a predetermined direction from the set of two adjacent pixel positions of the present iteration.
A device for scanning for borders in an image represented by pixels, the device being configured to perform a first operation comprising:
- estimating an attribute for each of a first set of two adjacent pixel positions in the image;
- assessing whether a predetermined binary condition differs in respect of the two pixel positions, and if so determining that a border is present in the part of the image represented by pixels at those positions;
- and
- if a border is determined to be present in that part of the image, estimating the direction of the border as being perpendicular to a line joining the positions of the two pixels;
- and initiating tracing the border in that direction.
A device as claimed in any of claims 25 to 28, wherein the device comprises a camera and the image is derived from the camera.
A method for tracing a border in an image comprising, given a maintained set comprising two adjacent pixel positions on either side of the border and a border direction, repeating the steps of:
- forming a contiguous block of four pixel positions comprising (i) the maintained set of two pixel positions and (ii) a new set of two adjacent pixel positions, each of the pixel positions of the new set being adjacent to a respective one of the pixel positions of the maintained set and offset from that respective pixel position of the maintained set in the border direction;
- estimating an attribute for each of the pixel positions of the new set;
- estimating a new direction of the border in dependence on the attributes of new set of pixel positions;
- and
- forming a new maintained set comprising two pixels selected from the block of four pixel positions.
Dependencies are inferred from the claim text.