Computer system process and user interface for providing intelligent scissors for image composition

Claim 3

The method according to claim 1, wherein: the image comprises a plurality of pixels; the first and second points are each one of the pixels; the first path comprises three or more first-path pixels including the first and second points; the second path comprises three or more second-path pixels including the first and second points; the step of determining a first total rotation amount of the first path comprises the steps of determining a rotation amount between each adjacent pair of the first-path pixels and summing these rotation amounts; and the step of determining a second total rotation amount of the second path comprises the steps of determining a rotation amount between each adjacent pair of the second-path pixels and summing these rotation amounts.

Claim 4

The method according to claim 2, wherein the steps of determining a cost of the first path and determining a cost of the second path further each comprise the steps of: determining a gradient magnitude G(p) of each pixel p in the path; determining an edge direction E(p) for each pixel p in the path; determining a direction D(p,q) between said pixel p and a neighboring pixel q in the path; determining an edge orientation θ(p,q) between said pixel p and the neighboring pixel q; determining a cost of an edge from said pixel p to said neighboring pixel q according to the below formula: Halfcost (p,q)=D(p,q)(λ.sub.2 +λ.sub.3 +λ.sub.4 -(1-λ.sub.0)·G(p).sup.λ1 ·Multiplier(p,q) Halfcost (q,p)=D(q,p)(λ.sub.2 +λ.sub.3 +λ.sub.4 -(1-λ.sub.0)·G(q).sup.λ1 ·Multiplier(p,q) Cost(p,q)=Halfcost(p,q)+Halfcost(q,p) where Multiplier(p,q)=λ 3 +λ 4 Z(p)+λ 2 (π-2χ(p,q)/π, χ(p,q) is the lesser of |θ(p,q)-E(p,q)| or π-|θ(p,q)-E(p,q)|, Z(p) is a Laplacian zero-crossing of pixel p{Multiplier (p,q)=λ 3 +λ 4 Z(p)+λ 2 (π-2χ(p,q))/π}, and λ 0 -λ 4 are scaling factors of a tension variable, a gradient response gamma, a gradient direction influence, a gradient magnitude influence and a zero crossing influence, respectively, which are used to modulate the gradient magnitude G(p) against the gradient direction D(p).

Claim 5

The method according to claim 2, wherein: the rotation amount is measured in gradients of 45 degrees.

Claim 6

The method according to claim 1, wherein: the step of selecting one of the first and second paths according to the first and second total rotation amounts includes selecting according to a maximum total rotation amount.

Claim 7

The method according to claim 1, wherein: the step of selecting one of the first and second paths according to the first and second total rotation amounts includes selecting according to a minimum total rotation amount.

Claim 10

The method according to claim 7, wherein: of the one or more paths of the trace, only the selected path is modified.

Claim 11

A storage device in which is stored image data including object-trace data associated with an image, the object-trace data being generated by a method comprising the steps of: selecting a first point on an edge of the object, determining a first path from the first point to a second point in the image, determining a cost of the first path, determining a second path from the first point to the second point, determining a cost of the second path, selecting one of the first and second paths, including, when the costs of the first and second paths are equal, by determining a first total rotation amount of the first path, determining a second total rotation amount of the second path, and selecting one of the first and second paths according to the first and second total rotation amounts.

Claim 12

A storage device in which is stored image data including object-trace data associated with an image, the object-trace data being generated by a method comprising the steps of: selecting a first point on an edge of the object, determining a first path from the first point to a second point in the image, determining a cost of the first path, determining a second path from the first point to the second point, determining a cost of the second path, selecting one of the first and second paths, including, when the costs of the first and second paths are equal, by determining a first total rotation amount of the first path, determining a second total rotation amount of the second path, and selecting one of the first and second paths according to the first and second total rotation amounts.

Claim 13

The method of claim 7, wherein: the image comprises a plurality of pixels; the first edited path comprises three or more first-edited-path pixels of the plurality of pixels, including the control point and the first of the pair of boundary points of the selected path; the second edited path comprises three or more second-edited-path pixels of the plurality of pixels, including the control point and the first of the pair of boundary points of the selected path; the step of determining a first total rotation amount of the first edited path comprises the steps of determining a rotation amount between each adjacent pair of the first-edited-path pixels and summing these rotation amounts; and the step of determining a second total rotation amount of the second edited path comprises the steps of determining a rotation amount between each adjacent pair of the second-edited-path pixels and summing these rotation amounts.

Claim 14

The method of claim 10, wherein the steps of determining a cost of the first edited path and determining a cost of the second edited path further each comprise the steps of: determining a gradient magnitude G(p) of each pixel p in the path; determining an edge direction E(p) for each pixel p in the path; determining a direction D(p,q) between said pixel p and a neighboring pixel q in the path; determining an edge orientation θ(p,q) between said pixel p and the neighboring pixel q; determining a cost of an edge from said pixel p to said neighboring pixel q according to the below formula: Halfcost(p,q)=D(p,q)(λ.sub.2 +λ.sub.3 +λ.sub.4 -(1-λ.sub.0)·G(p).sup.λ1 ·Multiplier(p,q)) Halfcost(q,p)=D(q,p)(λ.sub.2 +λ.sub.3 +λ.sub.4 -(1-λ.sub.0)·G(q).sup.λ1 ·Multiplier(q,p)) Cost(p,q)=Halfcost(p,q)+Halfcost(q,p) where Multiplier (p,q)=λ 3 +λ 4 Z(P)+λ 2 (π-2χ(p,q))/π, X(p,q) is the lesser of |θ(p,q)-E(p,q)| or π-|θ(p,q)-E(p,q)|, Z(p) is a Laplacian zero-crossing of pixel p, and λ 0 -λ 4 are scaling factors of a tension variable, a gradient response gamma, a gradient direction influence, a gradient magnitude influence and a zero crossing influence, respectively, which are used to modulate the gradient magnitude G(p) against the gradient direction D(p).

Claim 15

The method of claim 10, wherein: the rotation amount is measured in gradients of 45 degrees.

Claim 18

The method of claim 13, wherein: of the one or more paths of the trace, only the selected path is modified.

Claim 19

The method of claim 13, wherein: the image comprises a plurality of pixels; the first edited path comprises three or more first-edited-path pixels of the plurality of pixels, including the new location point and the second of the pair of boundary points of the selected path; the second edited path comprises three or more second-edited-path pixels of the plurality of pixels, including the new location point and the second of the pair of boundary points of the selected path; the step of determining a first total rotation amount of the first edited path comprises the steps of determining a rotation amount between each adjacent pair of the first-edited-path pixels and summing these rotation amounts; and the step of determining a second total rotation amount of the second edited path comprises the steps of determining a rotation amount between each adjacent pair of the second-edited-path pixels and summing these rotation amounts.

Claim 20

The method of claim 15, wherein the steps of determining a cost of the first edited path and determining a cost of the second edited path further each comprise the steps of: determining a gradient magnitude G(p) of each pixel p in the path; determining an edge direction E(p) for each pixel p in the path; determining a direction D(p,q) between said pixel p and a neighboring pixel q in the path; determining an edge orientation θ(p,q) between said pixel p and the neighboring pixel q; determining a cost of an edge from said pixel p to said neighboring pixel q according to the below formula: Halfcost(p,q)=D(p,q)(λ.sub.2 +λ.sub.3 +λ.sub.4 -(1-λ.sub.0)·G(p).sup.λ1 ·Multiplier(p,q)) Halfcost(q,p)=D(q,p)(λ.sub.2 +λ.sub.3 +λ.sub.4 -(1-λ.sub.0)·G(q).sup.λ1 ·Multiplier(q,p)) Cost(p,q)=Halfcost(p,q)+Halfcost(q,p) where Multiplier(p,q)=λ 3 +λ 4 Z(P)+λ 2 (π-2χ(p,q))/π, χ(p,q) is the lesser of |θ(p,q)-E(p,q)| or π-|θ(p,q)-E(p,q)|, Z(p) is a Laplacian zero-crossing of pixel p, and λ 0 -λ 4 are scaling factors of a tension variable, a gradient response gamma, a gradient direction influence, a gradient magnitude influence and a zero crossing influence, respectively, which are used to modulate the gradient magnitude G(p) against the gradient direction D(p).

Claim 21

The method of claim 2, wherein the steps of determining a cost of the first path and determining a cost of the second path further each comprise the steps of: determining a gradient magnitude G(p) of at least one pixel p in the path; determining an edge orientation e(p,q) between the pixel p and a neighboring pixel q; determining an edge direction E(p) for the pixel p; determining an edge-orientation cost χ(p,q) that is the lesser of |θ(p,q)-E(p,q)| or π-|θ(p,q)-E(p,q)|; and determining a cost of an edge from the pixel p to the neighboring pixel q including modulating the edge-orientation cost χ(p,q) by the gradient magnitude G(p).

Claim 22

The method of claim 2, wherein the steps of determining a cost of the first path and determining a cost of the second path further each comprise the steps of: determining a gradient magnitude G(p) of at least one pixel p in the path; determining a Laplacian zero-crossing of the pixel p; and determining a cost of an edge from the pixel p to a neighboring pixel q including modulating the Laplacian zero-crossing of the pixel p by the gradient magnitude G(p).

Claim 23

The method of claim 2, wherein the steps of determining a cost of the first path and determining a cost of the second path farther each comprise the step of: determining a cost of an edge from at least one pixel p in the path to a neighboring pixel q including determining a value equal to a gradient magnitude G(p) of the pixel p raised to an exponential power.

Claim 24

The method of claim 19, wherein: the step of determining a value comprises determining a value equal to the gradient magnitude G(p) of the pixel p raised to an exponential power represented by a scaling factor of a gradient response gamma λ1.

Claim 25

A video system comprising: a storage device for storing image data including object-trace data associated with an object in an image; and an object tracer for extracting the object trace data from the image, constructed and adapted to select a first point on an edge of the object, determine a first path from the first point to a second point in the image, determine a cost of the first path, determine a second path from the first point to the second point, determine a cost of the second path, select one of the first and second paths, including to, when the costs of the first and second paths are equal, determine a first total rotation amount of the first path, determine a second total rotation amount of the second path, and select one of the first and second paths according to the first and second total rotation amounts.

Claim 26

A video system comprising: a storage device for storing image data including object-trace data associated with an object in an image; and an object tracer for extracting the object trace data from the image, constructed and adapted to select a first point on an edge of the object, determine a first path from the first point to a second point in the image, determine a cost of the first path, determine a second path from the first point to the second point, determine a cost of the second path, select one of the first and second paths, including to, when the costs of the first and second paths are equal, determine a first total rotation amount of the first path, determine a second total rotation amount of the second path, and select one of the first and second paths according to the first and second total rotation amounts.

Claim 27

The video system of claim 21, further comprising: a capture device for receiving the image data.

Claim 28

The video system of claim 21, further comprising: a trace editor for editing the object trace data, wherein the trace data comprises one or more paths, each including a pair of boundary points on a boundary of the object, the trace editor constructed and arranged to select a path, select a control point between the pair of boundary points on the selected path, determine a first edited path from a first of the pair of boundary points of the selected path to the control point, determine a cost of the first edited path, determine a second edited path from the first of the pair of boundary points to the control point, determine a cost of the second edited path, select one of the first and second edited paths, including to, when the costs of the first and second edited paths are equal, determine a first total rotation amount of the first edited path, determine a second total rotation amount of the second edited path, and select one of the first and second edited paths according to the first and second total rotation amounts.

Claim 29

The video system of claim 21, further comprising: a trace editor for editing the object trace data, wherein the trace data comprises one or more paths, each including a pair of boundary points on a boundary of the object, the trace editor constructed and arranged to select a path, move a first of the pair of boundary points of the selected path to a new location point along the boundary of the object; determine a first edited path from a second of the pair of boundary points of the selected path to the new location point; determine a cost of the first edited path; determine a second edited path from a second of the pair of boundary points of the selected path to the new location point; determine a cost of the second edited path; select one of the first and second edited paths, including to, when the costs of the first and second edited paths are equal, determine a first total rotation amount of the first edited path, determine a second total rotation amount of the second edited path, and select one of the first and second edited paths according to the first and second total rotation amounts.

Claim 36

The method of claim 27, wherein: the step of determining a value comprises determining a value equal to the gradient magnitude G(p) of the pixel p raised to an exponential power represented by a scaling factor of a gradient response gamma λ1.

Claim 37

The method of claim 7, wherein: the step of selecting one of the first and second edited paths according to the first and second total rotation amounts includes selecting according to a maximum total rotation amount.

Claim 38

The method of claim 7, wherein: the step of selecting one of the first and second edited paths according to the first and second total rotation amounts includes selecting according to a minimum total rotation amount.

Claim 39

The method of claim 15, wherein: the rotation amount is measured in gradients of 45 degrees.

Claim 40

The method of claim 13, wherein: the step of selecting one of the first and second edited paths according to the first and second total rotation amounts includes selecting according to a maximum total rotation amount.

Claim 41

The method of claim 13, wherein: the step of selecting one of the first and second edited paths according to the first and second total rotation amounts includes selecting according to a minimum total rotation amount.

Claim 42

A computer program product for use with a computing system having a processor and a storage device for storing image data including object-trace data associated with an object in an image, the computer program product comprising a computer usable medium having embodied therein computer readable program code method steps for extracting the object trace data from the image, the method steps comprising: selecting a first point on an edge of the object, determining a first path from the first point to a second point in the image, determining a cost of the first path, determining a second path from the first point to the second point, determining a cost of the second path, selecting one of the first and second paths, including, when the costs of the first and second paths are equal, determining a first total rotation amount of the first path, determining a second total rotation amount of the second path, and selecting one of the first and second paths according to the first and second total rotation amounts.

Claim 43

A computer program product for use with a computing system having a processor and a storage device for storing image data including object-trace data associated with an object in an image, the computer program product comprising a computer usable medium having embodied therein computer readable program code method steps for extracting the object trace data from the image, the method steps comprising: selecting a first point on an edge of the object, determining a first path from the first point to a second point in the image, determining a cost of the first path, determining a second path from the first point to the second point, determining a cost of the second path, selecting one of the first and second paths, including, when the costs of the first and second paths are equal, determining a first total rotation amount of the first path, determining a second total rotation amount of the second path, and selecting one of the first and second paths according to the first and second total rotation amounts.

Claim 44

The computer program product of claim 34, wherein the method steps further comprise: editing the object trace data, wherein the trace data comprises one or more paths, each including a pair of boundary points on a boundary of the object, including the steps of selecting a path, selecting a control point between the pair of boundary points on the selected path, determining a first edited path from a first of the pair of boundary points of the selected path to the control point, determining a cost of the first edited path, determining a second edited path from the first of the pair of boundary points to the control point, determining a cost of the second edited path, selecting one of the first and second edited paths, including to, when the costs of the first and second edited paths are equal, determining a first total rotation amount of the first edited path, determining a second total rotation amount of the second edited path, and selecting one of the first and second edited paths according to the first and second total rotation amounts.

Claim 45

The computer program product of claim 34, wherein the method steps further comprise: editing the object trace data, wherein the trace data comprises one or more paths, each including a pair of boundary points on a boundary of the object, including the steps of selecting a path, moving a first of the pair of boundary points of the selected path to a new location point along the boundary of the object; determining a first edited path from a second of the pair of boundary points of the selected path to the new location point; determining a cost of the first edited path; determining a second edited path from a second of the pair of boundary points of the selected path to the new location point; determining a cost of the second edited path; select one of the first and second edited paths, including to, when the costs of the first and second edited paths are equal, determining a first total rotation amount of the first edited path, determining a second total rotation amount of the second edited path, and selecting one of the first and second edited paths according to the first and second total rotation amounts.