Partitioning an image

Patent metadata

Field	Value
Publication number	US-9875555-B2
Application number	US-201514945055-A
Country	US
Kind code	B2
Filing date	Nov 18, 2015
Priority date	Nov 18, 2014
Publication date	Jan 23, 2018
Grant date	Jan 23, 2018

Abstract

The invention is directed to a computer-implemented method for partitioning an image. The method comprises displaying an image that comprises a border; drawing a curve over the image; computing all closed areas delimited by the curve and the border of the image, each closed area being independent from the other computed closed areas and individually selectable.

First claim

The invention claimed is:

1. A computer-implemented method for partitioning an image comprising:
displaying an image that comprises a border;
drawing a curve over the image;
building a continuous polyline from the curve drawn over the image;
for each line forming the continuous polyline, identifying pixels of the displayed image that have the respective line of the continuous polyline as an edge;
computing all closed areas delimited by the polyline and the border of the image and all closed areas delimited by the polyline alone, each closed area being independent from one another and individually selectable by a user; and
displaying one or more of the computed closed areas together with the image on a display.

2. The computer-implemented method of claim 1 , wherein the step of building the continuous polyline comprises:
computing a set of pixels linking two distinct end points of the curve drawn over the image, wherein neighboring pixels of the set have an edge in common; and
building the continuous polyline wherein each line of the polyline is an edge of one of the pixels of the computed set of pixels.

3. The computer-implemented method of claim 2 , further comprising, after the step of identifying the pixels of the displayed image,
marking each identified pixel, the marking indicating the position of polyline relative to each identified pixel.

4. The computer-implemented method of claim 3 , wherein the step of marking each identified pixel is performed by coloring each identified pixel with at least one color encoded with a RGBA color space:
a first RGBA value indicates a polyline positioned on the right side of the pixel;
a second RGBA value indicates a polyline positioned on the left side of the pixel;
a third RGBA value indicates a polyline positioned on the up side of the pixel; and
a fourth RGBA value indicates a polyline positioned on the bottom side of the pixel.

5. The computer-implemented method of claim 4 , wherein the coloring of each pixel is cumulative.

6. The computer-implemented method of claim 1 , wherein the step of computing all closed areas delimited by the curve and the border of the image is performed by using a region growing algorithm wherein a region membership criterion of a pixel is not to be across the continuous polyline.

7. The computer-implemented method of claim 6 , wherein the region growing algorithm comprises the steps of:
(i) selecting a first pixel of the image that belongs to a first closed area;
(ii) identifying neighboring pixels of the selected first pixel that meet the criterion by using a marking on the selected pixel;
(iii) adding each neighboring pixel identified at step (ii) in a list of pixels to be selected and treated as the first selected pixel;
(iv) marking the selected first pixel as checked and adding the selected first pixel to a list of pixel belonging to the first closed areas;
(v) selecting a second pixel in the list of pixels to be selected and performing the steps (ii) to (iv) for the second pixel;
(vi) repeating the step (v) until all the pixels of the list of pixels to be selected have been selected.

8. The computed-implemented method of claim 7 , further comprising:
(vii) identifying a third pixel of the image that belongs to a second closed area, the third pixel were not marked at step (iv);
(viii) performing the steps (ii) to (vi);
(ix) repeating the steps (vii) to(viii) until all the pixels of the image are marked as checked.

9. The computer-implemented method of claim 8 , wherein the steps performed starting from the step of building a continuous polyline are carried out on a mask, wherein the mask is an image with the same size and the same number of pixels as the displayed image, and wherein the mask is initialized as a blank image and the pixels marked as checked are colored in black when added to a list of pixel belonging to a closed area.

10. The computer-implemented method of claim 1 , wherein the steps performed starting from the step of building a continuous polyline are carried out on a mask, wherein the mask is an image with the same size and the same number of pixels as the displayed image.

11. The computer-implemented method of claim 1 , wherein the computed closed areas are stored in a quadtree data structure.

12. The computer-implemented method of claim 1 , further comprising, after the step of computing all closed areas:
selecting individually at least one closed area; and
creating an independent image for each closed area selected.

13. The computer-implemented method of claim 1 , wherein the computing further comprises discarding portions of the continuous polyline that are not included in the closed areas.

14. A non-transitory computer readable medium storing a program comprising instructions for performing the method of claim 1 .

15. A system comprising a processor coupled to a memory and a graphical user interface, the memory having recorded thereon a program comprising instructions for performing the method of claim 1 .

Assignees

• Dassault Systemes

Inventors

• Letzelter Frederic
• Renard Amelie
• Peythieux Laura

Classifications

• G06T7/11 Primary

  Region-based segmentation · CPC title

• G06T7/60 Primary

  Analysis of geometric attributes · CPC title

• G06T11/23

  using straight lines or curves · CPC title

• G06T11/10

  Texturing; Colouring; Generation of textures or colours (retouching, inpainting or scratch removal G06T5/77) · CPC title

• G06T2207/20021

  Dividing image into blocks, subimages or windows · CPC title