US 8,897,576 B2Granted

Image processing device, method and program

AssigneeFUJIFILM Corporation

InventorYoshiro Kitamura

Life of this patent

Estimating the term…

Loading patent…

Abstract

Candidate points belonging to a predetermined structure are extracted from image data DV. A shape model which represents a known shape of the predetermined structure and is formed by model labels having a predetermined connection relationship is obtained. Corresponding points corresponding to the model labels are selected from the extracted candidate points under the following constraints: (a) each model label is mapped with only one of the candidate points or none of the candidate points; (b) each candidate point is mapped with only one of the model labels or none of the model labels; and (c) when a path between two candidate points which are mapped with each pair of the model labels connected with each other is determined, each candidate point which is mapped with none of the model labels is included in only one of the determined paths or none of the determined paths.

Claims8

Dependent claims

An image processing device comprising:

a candidate point extracting unit configured to extract a plurality of candidate points belonging to a predetermined structure from image data;
a shape model storing unit configured to store a shape model representing a known shape of the predetermined structure, the shape model being formed by a plurality of model labels having a predetermined connection relationship;
and
a corresponding point selecting unit configured to select a mapping relationship between the candidate points and the model labels from a set of candidate mapping relationships satisfying constraints (a) to (c) below:
(a) each model label is mapped with only one of the candidate points or none of the candidate points;
(b) each candidate point is mapped with only one of the model labels or none of the model labels;
and
(c) when a path between two candidate points which are mapped with each pair of the model labels connected with each other is determined, each candidate point which is mapped with none of the model labels is included in only one of the determined paths or none of the determined paths,
wherein, when a set of the candidate points is represented by P, a set of the model labels is represented by Q, and a mapping relationship between the candidate points and the model labels is represented by a vector x having P×Q elements, the corresponding point selecting unit selects the mapping relationship from a set C of candidate solutions satisfying a constraint expressed by Equation (1) below:
C
=
{
x
∈
{
0
,
1
}
P
×
Q
❘
∑
Sp
∈
P
⁢
⁢
xSpTq
≤
1
,
∑
Tq
∈
Q
⁢
⁢
xSpTq
+
∑
(
Sp
′
,
Sp
″
)
∈
P
×
P
❘
Sp
′
<
Sp
″
⁢
(
ySpSp
′
⁢
Sp
″
×
∑
Tq
∈
Q
⁢
⁢
xSp
′
⁢
Tq
×
∑
Tq
∈
Q
⁢
⁢
xSp
″
⁢
Tq
)
≤
1
,
∀
p
∈
P
⁢
⁢
and
⁢
⁢
∀
q
∈
Q
}
.
,
(
1
)
where xSpTq is a binary variable having a value of 1 if a certain one of the candidate points Sp is mapped with a certain one of the model labels Tq or a value of 0 if the certain one of the candidate points Sp is not mapped with the certain one of the model labels Tq, and ySpSp′Sp″ is a binary variable having a value of 1 if the certain candidate point Sp is included in a path between other two candidate points Sp′ and Sp″ belonging to the set P or a value of 0 if the certain candidate point Sp is not included in the path.

109 more elements

An image processing method comprising:

extracting a plurality of candidate points belonging to a predetermined structure from image data;
obtaining a shape model stored in advance in a shape model storing unit, the shape model representing a known shape of the predetermined structure and being formed by a plurality of model labels having a predetermined connection relationship;
and
selecting a mapping relationship between the candidate points and the model labels from a set of candidate mapping relationships satisfying constraints (a) to (c) below:
(a) each model label is mapped with only one of the candidate points or none of the candidate points;
(b) each candidate point is mapped with only one of the model labels or none of the model labels;
and
(c) when a path between two candidate points which are mapped with each pair of the model labels connected with each other is determined, each candidate point which is mapped with none of the model labels is included in only one of the determined paths or none of the determined paths,
wherein, when a set of the candidate points is represented by P, a set of the model labels is represented by Q, and a mapping relationship between the candidate points and the model labels is represented by a vector x having P×Q elements, the selecting of the mapping relationship comprises selecting the mapping relationship from a set C of candidate solutions satisfying a constraint expressed by Equation (1) below:
C
=
{
x
∈
{
0
,
1
}
P
×
Q
❘
∑
Sp
∈
P
⁢
⁢
xSpTq
≤
1
,
∑
Tq
∈
Q
⁢
⁢
xSpTq
+
∑
(
Sp
′
,
Sp
″
)
∈
P
×
P
❘
Sp
′
<
Sp
″
⁢
(
ySpSp
′
⁢
Sp
″
×
∑
Tq
∈
Q
⁢
⁢
xSp
′
⁢
Tq
×
∑
Tq
∈
Q
⁢
⁢
xSp
″
⁢
Tq
)
≤
1
,
∀
p
∈
P
⁢
⁢
and
⁢
⁢
∀
q
∈
Q
}
.
,
(
1
)
where xSpTq is a binary variable having a value of 1 if a certain one of the candidate points Sp is mapped with a certain one of the model labels Tq or a value of 0 if the certain one of the candidate points Sp is not mapped with the certain one of the model labels Tq, and ySpSp′Sp″ is a binary variable having a value of 1 if the certain candidate point Sr is included in a path between other two candidate points Sp′ and Sp″ belonging to the set P or a value of 0 if the certain candidate point Sp is not included in the path.

109 more elements

A non-transitory computer readable medium containing an image processing program for causing a computer to carry out:

extracting a plurality of candidate points belonging to a predetermined structure from image data;
obtaining a shape model stored in advance in a shape model storing unit, the shape model representing a known shape of the predetermined structure and being formed by a plurality of model labels having a predetermined connection relationship;
and
selecting a mapping relationship between the candidate points and the model labels from a set of candidate mapping relationships satisfying constraints (a) to (c) below:
(a) each model label is mapped with only one of the candidate points or none of the candidate points;
(b) each candidate point is mapped with only one of the model labels or none of the model labels;
and
(c) when a path between two candidate points which are mapped with each pair of the model labels connected with each other is determined, each candidate point which is mapped with none of the model labels is included in only one of the determined paths or none of the determined paths,
wherein, when a set of the candidate points is represented by P, a set of the model labels is represented by Q, and a mapping relationship between the candidate points and the model labels is represented by a vector x having P×Q elements, the selecting of the mapping relationship comprises selecting the mapping relationship from a set C of candidate solutions satisfying a constraint expressed by Equation (1) below:
C
=
{
x
∈
{
0
,
1
}
P
×
Q
❘
∑
Sp
∈
P
⁢
⁢
xSpTq
≤
1
,
∑
Tq
∈
Q
⁢
⁢
xSpTq
+
∑
(
Sp
′
,
Sp
″
)
∈
P
×
P
❘
Sp
′
<
Sp
″
⁢
(
ySpSp
′
⁢
Sp
″
×
∑
Tq
∈
Q
⁢
⁢
xSp
′
⁢
Tq
×
∑
Tq
∈
Q
⁢
⁢
xSp
″
⁢
Tq
)
≤
1
,
∀
p
∈
P
⁢
⁢
and
⁢
⁢
∀
q
∈
Q
}
.
,
(
1
)
where xSpTq is a binary variable having a value of 1 if a certain one of the candidate points Sp is mapped with a certain one of the model labels Tq or a value of 0 if the certain one of the candidate points Sp is not mapped with the certain one of the model labels Tq, and ySpSp′Sp″ is a binary variable having a value of 1 if the certain candidate point Sp is included in a path between other two candidate points Sp′ and Sp″ belonging to the set P or a value of 0 if the certain candidate point Sp is not included in the path.

109 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/626,503Filed 25 Sep 2012
Priority: JP 2011-20924626 Sep 2011
Published: US 2013/0077872 A128 Mar 2013
Granted: 25 Nov 2014
Term ends: Not estimatedThe source records don’t support an estimate.

Classification10 codes

G06T 7/149
Segmentation; Edge detection: involving deformable models, e.g. active contour models
G06T 7/162
Segmentation; Edge detection: involving graph-based methods
G06V 10/757
Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g.…:…
G06T 2207/20072
Special algorithmic details: graph-based image processing