(12) United States Patent
`Le et al.
`
`(10) Patent No.:
`
`US 7,031,517 B1
`
`(45) Date of Patent:
`
`Apr. 18, 2006
`
`USOOTO3 l 5 1 7B]
`
`(54) METHOD AND APPARATUS FOR
`SECMENTING IMAGES
`
`(75)
`
`Inventors: Delphine Anh Dan Le. New South
`Wales (AU); Alison Joan Lennon. New
`South Wales (AU); Matthieu Ilitter,
`Paris (FR)
`
`(73) Assignee:
`
`(Iannn Kabushiki Kaisha. Tokyo (JP)
`
`( * ) Notice:
`
`Subject to any disclai1ner_. the term of this
`patent is extended or adjusted under 35
`U.S.C‘. 154(1)) by 0 days.
`
`(21) Appl. No.: o9r41o,737
`
`(22)
`
`Filed:
`
`Oct. 1, 1999
`
`(30)
`
`Foreign Application Priority Data
`
`Oct. 2, 1998
`Oct. 2. 1998
`Oct. 2, 1998
`Oct. 2, 1998
`
`(AU)
`(AU)
`(AU)
`(AU)
`
`
`
`PP634l
`PP6342
`PP6343
`PP6344
`
`(51)
`
`Int. Cl.
`G06K 9/34
`382.3173
`(52) U.S. (fl.
`3821101.
`(58) Field of Classification Search
`382E128, 173. 180.224. 225, 204. 205, 240.
`382808
`
`(2006.01)
`
`See application tile for co111plete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5.579.258 A
`5.?34.T36 A "’
`S.'F48.?6l A
`
`ll.-1996 Yokoyama ................ .. 348-“"415
`3-‘I998 Palmer et al.
`382-‘I03
`
`S.-‘"1998 Chang eta].
`382-'10"?
`
`OTHER PUBLICATIONS
`
`lkonomakis ct all. “Region (irewing and Region Merging
`Image Segmentation". IEEE Digital Signal Processing Pro-
`ceedings. I997. p 299-302, vol. l.*
`
`“lmage Segementation and Approximation Through Surface
`Type Labelling and Region Merging“.
`ll7.l"-.F. F.|cctronics
`Letters, 198 p. 1380-1381, vol. 24, Iss. 22.‘
`“Spatio—Te1nporal Segmentation 01' Video Data“, by Wang,
`ct al.. Proceedings Of'l'he SHE. vol. 2182, Feb. ?. 1994. pp.
`120-131.
`
`“Video Coding By Segmenting Motion Vectors And Frame
`Diflerences". by Suk Byung Chae et al._. Optical Engineer-
`ing. vol. 32, No. 4. Apr. 1. 1994, pp. I20-131.
`
`(Continued)
`
`J ingge W11
`Primar_t-' E.\'a:niner
`Assistant E.\'cmiiner—Colin LaRose
`
`(74) .4!.r0r::re_t'_. .»‘lgr:m'. or Firrri
`Scinto
`
`Fitzpatrick, Celia, Harper 8'.
`
`(57)
`
`ABSTRACT
`
`The method discloses a method of segmenting an iniagc.
`The method firstly (304) allocates pixels as seeds in areas of
`an image as a function of the luminance ofthe pixels and the
`size of those areas. The method then grows (306) regions
`from said seeds so as to segment the image into a number of
`regions. The method considers a number of pixels that
`border the growing regions and the pixel that is most similar
`in luminance to a region it borders is appended (528) to that
`region. The method then updates (528) the luminance ofthe
`appended region. The method continues until there are no
`more pixels bordering the growing regions. The method then
`encodes the segmented image (106). It does this by splitting
`(604) the image into at number of rectangular sub-images in
`a quadtree manner until each rectangular sub-image com-
`prises a segnientod image forming the dominant portion of
`the sub-image. The method then merges (606) rectangular
`sub—in1ages which have a common dominant portion and
`share :1 eo111rnon edge.
`
`43 Claims, 15 Drawing Sheets
`
`IPR of US Pat. No. 7,974,339
`
`Google Inc.
`GOOG 1026
`
`304
`
`306
`
`

`
`US 7,031,517 B1
`Page 2
`
`OTHER PUBLICATIONS
`“Digital Image Pmcessing", by Rafael C. Gonzalez, er al._.
`Wesley Pub. Co. 1993, pp. 461-465.
`
`IEEE Trans. Panern Anal.
`“Seeded Region Growing",
`Machme lmell" ml’ 16’ 1994’ pp’ 641-647'
`‘°‘ cited by exanliner
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 1 M15
`
`Us 7,031,517 B1
`
`102
`
`
`
`segmented image
`
`110
`
`MRF merging
`of segments
`
`
`
`112
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 2 of 15
`
`Us 7,031,517 B1
`
`

`
`U.S. Patent
`
`Apr. 13,2005
`
`Sheet 3 of 15
`
`US 7,031,517 B1
`
`/ 104
`
`
`
`
`
`Seeded Region
`Growing
`
`306
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 4 of 15
`
`Us 7,031,517 B1
`
`image —>rectangIe_h'st
`
` 402
`406
`
`re-ctangIe_I1'st
`
`[10
`
`yes mi
`
`remove first element
`
`
`
`
`
`
`
`
`
`
`
`
`
`420
`
`
`
`
`
`
`
`rectangfe size
`3- h1‘_m1'n_s1'ze-
`
`no
`
`yes
`
`(split rectangle
`-9 recta ng!e_h'st
`
`418
`
`contrast < hi_threshoid?
`
`3/35
`
`no
`
`(low density of pixels of
`rectangh-2-)—> seed__J':'.st
`
`422
`
`rectangie size
`> Io_m1'n_s!ze
`
`424
`
`428
`
`ye
`
`s
`
`no
`
`426
`
`
`
`(split rectangie)
`-3- rectangle__Iist
`
`(high density of pixels of
`rectangle-)—> seed__ii.st
`
`Fig. 4A
`
`of rectang!e_!:'sr
`—> rectangle
`
`access contrast
`of rectangle
`
`410
`
`Id’?
`contrast < lo__thr5-she
`
`3/35
`
`no
`
`41 2
`
`41 6
`
`(central pixel of
`e
`r cfangie)->seed__!isf
`
`414
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 5 of 15
`
`Us 7,031,517 B1
`
`
`
`
`
`Fig.413
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 6 of 15
`
`Us 7,031,517 B1
`
`seed_!r'.5-t ~> region 3
`
`put the neighbours of each
`seed in candr'tate_!£sf
`
`502
`
`504
`
`dyn_thresho!d = 0
`
`506
`
`yes
`@ is c:ana'1'tata_!1's! empty
`no
`
`
`
`
`
`dyn_1‘hreshcu'a‘ =
`maximum (dyn__
`fhreshomfimfn)
`
`
`
`1: 0, min = 256,
`dyn_step = (size of
`c=and1'dafe__.'ist} I 300
`
`
`
`105
`
`
`
`no
`
`
`YE f'flOV9
`chosen__p:'x
`
`from
`
`
`cand1'dafe__!is1‘
`
`
`
`1-: size of
`
`can dida te___H.-3!?
`
`yes
`
`currem‘_p:’x = pixei I
`in candidafe_!:‘5!
`
`deita [current__p:fx
`< mm?
`
`
`
`min = defla [curr'evn1‘__p2':r}
`chosen__pix = cune-nf__p1'x
`cho.-3en_reg = current_reg
`
`
`
`
`J3
`'
`‘
`dyn__ste-p
`
`
`
` put each unmarked
`
`
`neighbour of
`c!1osen__p£:c in
`candidate__l.fst
`
`
`
`
`
`
`
`
`
`
`
`put chasen__p1'x in
`.negfon[chosen_reg,?
`update
`maanfchos 5-n__reg)
`
`
`
`V99
`
`min <
`
`dynmthreshold?
`
`524
`
`
`Fig. 5A
`
`528
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 7 of 15
`
`Us 7,031,517 B1
`
`
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 8 of 15
`
`Us 7,031,517 B1
`
`/106
`
`Splitting Regions
`
`
`
`
`Merging Regions
`
`604
`
`606
`
`Fig. 6
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 9 of 15
`
`Us 7,031,517 B1
`
`0 1°‘
`
`image—> rec1‘_queue
`region namese name-_queue
`
`704
`
`‘“:§$~,;?,“-'3“
`
`HO
`
`V95
`
`708
`
`606
`
`.
`
`rec! = rect_queu.9.first
`rec2f_queue. remove-First
`
`71 0
`
`names = name-s__queue.first
`narne_queue.rernoveFirst
`
`7-, 2
`
`
`
`rect.srze() > mm sxze
`
`no
`
` 1'= index of the dominant
`region in rec!
`re-ct—:~ regionfl]
`
`9
`
`yes
`
`71
`
`7'18
`
`
`
`
`
`is there a region I
`such that (proportion of
`
`name__:'.r'st.1' in rest)
`> de!ta*rect.s1'ze{)?
`
`
`
` split rec!-av nect_queue
`rect.findName-> name__queue
`
`Fig. 7A
`
`1]
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 10 of 15
`
`Us 7,031,517 B1
`
`752
`
`750
`
`K
`
` .
`
`Spiitting Initial State
`
`Fig. 7B
`
`
`
`Splitting Step 1
`
`Fig. 7C
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 11 0115
`
`Us 7,031,517 B1
`
`
`
`Splitting Step 2
`
`Fig. 713
`
`750
`
`
`Fig. 7E
`
`Splitting Final State
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 12 of 15
`
`Us 7,031,517 B1
`
`604
`
`3 8°‘
`
`.,
`
`806
`
`no
`
`808
`
`1-: NO__REGlONS-1 .
`
`fi
`
`yes
`
`count = 0
`
`810
`
`count < nb of
`rectangles in region 1"?
`
`812
`
`yes
`
`
`
`1’ ++
`
`14
`
`814
`
`
`
`ls there an adjacent
`rectangle of rectangle count
`
`in region 1??
`
`
`
`I10
`
`YES
`
`merge theme» in region I
`
`818
`
`681
`
`82°
`
`Fig. 8A
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 13 of 15
`
`Us 7,031,517 B1
`
`Merging Final Stale
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 14 of 15
`
`Us 7,031,517 B1
`
`Compute clique function for all
`pairs of neighbouring regions
`
` 902
`
` 904
`
`Select the pair of regions with the
`smallest ciique function value
`
`112
`
`
`
`
`
`clique function vaiue
`smaller than 3
`
`threshold?
`
`
`
`Output
`segmented
`image
`
`908
`
`is this
`
` Merge both regions and
`
`
`update clique function values
`with neighbouring regions
`
`
`
`Fig. 9
`
`16
`
`

`
`U.S. Patent
`
`Apr. 18,2006
`
`Sheet 15 of 15
`
`Us 7,031,517 B1
`
`[ 1000
`
`Video
`
`Interface
`
`
`
`
`
`
`1004
`
`1008
`1006
`
`
`IIO
`
`Interface
`
`Keyboard
`
`Fig 10
`
`17
`
`

`
`US 7,031,517’ B1
`
`1
`METHOD AND APPARATUS FOR
`SEGMENTING IMAGES
`
`FIELD OF INVENTION
`
`The present invention relates to the field of image seg-
`mentation. In particular, one aspect of the invention relates
`to the seeding of an image. Another aspect of the invention
`relates to segmenting images. A still further aspect of the
`invention relates to encoding an image having a number of
`segmented regions as a coded representation.
`
`BACKGROUND OF INVENTION
`
`Image segmentation is an initial step in many image
`processing tasks such as pattern recognition, image coding
`and image interpretation. For example, in scene understand-
`ing applications.
`the segmentation process generally pro-
`vides a labelling process with regions to be classified.
`The publication entitled “Digital Image Processing" by
`Rafael C. Gonzalez and Richard E. Woods, Addison-Wesley
`Publishing Company 1993 discloses on page 461-465. a
`method for image segmentation. This method utilizes a
`region splitting and merging procedure. This procedure
`subdivides an image initially into a set of arbitrary, dis-
`jointed regions and then merges andfor splits the regions
`depending whether the regions satisfy a certain homogeneity
`criteria. Typically, the homogeneity criterion is based on a
`threshold value arbitrarily selected by a user. However. this
`method suffers front the disadvantage that the choice of
`threshold values is critical for successful image segmenta-
`tion. Specifically, a particular threshold value may work
`with one image but not necessarily with others. For exan1ple_.
`this method often fails to split regions that must be separated
`or fails to merge regions that need not be separated. This is
`a consequence of the information about the uniformity in a
`region corresponding to an object surface and the disconti-
`nuity between regions corresponding to different object
`surfaces not being easily incorporated into the method.
`‘the publication entitled “Seeded Region Growing" llilili
`Trans. Pattern Anal Machine lntell., vol. 16 pp. 641-647.
`1994 (hereinafter called Adams et al) discloses a method for
`segmentation of images. The Adams method is based on a
`region growing principle of selecting a pixel adjacent to a
`region of pixels, which is most similar to the region of
`pixels. The method does not rely on the arbitrary selection
`of homogeneity thresholds, but is controlled by choosing a
`small number of pixels, called seeds. This seed selection
`may be either automatic or manual. Once the seeds have
`been selected,
`the segmented regions are grown i11 an
`iterative fashion. Adams suggest using an automatic con-
`verging squares method for seeds selection. Adams uses this
`method to locate objects of minimum and maximum inten-
`sity in biomedical images. Each step of the Adam method
`involves the addition ofone of the neighboring pixels to one
`of the regions grown from the seeds. A measure ?3(x)
`is
`defined how dilferent each of the neighboring pixels is from
`that region. The neighboring pixel having the minimum
`measure o(x) is added to the region. Adams et al make use
`of a sorted list in determining the relevant neighboring pixel
`to be added. In Adams et al_. once a pixel has been added to
`the list. the ?i(x] measure is never updated. However, this
`method is not successful for images where the number of
`regions is large and the regions have diverse cllaracteristics.
`Moreover. the Adams et al method suflers from the disad-
`vantage of slow image segmentation. Whilst. this method is
`robust and easy-to-use_. it also sufiers from the disadvantage
`
`10
`
`15
`
`30
`
`35
`
`4U
`
`45
`
`55
`
`60
`
`that the resultant segmented image is stored as a pixel-map
`representation and as such is memory consuming and not
`eflicient for feature computation
`
`SUMMARY OF THE INVENTION
`
`It is an object of the present invention to ameliorate one
`or more disadvantages of the prior art.
`According to one aspect of the invention there is provided
`a method of seeding an image.
`the image comprising a
`plurality of pixels. wherein said method comprises the step
`of: distributing seeds in areas of said image as a function of
`a property of said pixels within those areas, wherein fewer
`seeds are allocated to those areas ofthe image having pixels
`homogeneous in said property.
`According to another aspect of the invention there is
`provided a method of seeding an image having a plurality of
`pixels, the method comprising the steps of: dividing the
`image into one or 111ore regions; allocating, for each region,
`one or more seeds as a function of the contrast of said pixels
`with.in the region and the size of the region as compared to
`the size of the image, wherein fewer seeds are allocated to
`those regions of the image having pixels of homogeneous
`contrast; and storing the pixel locations of each allocated
`seed.
`
`According to still another aspect of the present invention
`there is provided a method of seeding an image comprising
`a plurality of pixels, wherein said method comprises the
`steps of: selecting the image or a previously divided area of
`the image as the current area: seeding the center of said
`current area when the contrast of the pixels and the size of
`current area meet a first predetermined condition; subdivid-
`ing said current area when the contrast of the pixels and the
`size of current area meet a second predetermined condition:
`uniformly seeding said current area in a low density manner
`when the contrast of the pixels and the size of current area
`meet a third predetermined condition; subdividing said
`current area when contrast of the pixels and the size of
`current area meet a fourth predetermined condition‘,
`tini-
`formly seeding said current area in a high density manner
`when the contrast of the pixels and the size of current area
`meet a fifth predetermined condition: and repeating the
`selecting and seeding steps until all ofsaid divided areas are
`seeded. wlicrein fewer seeds are allocated to those areas of
`the image having homogeneous contrast.
`According to still another aspect of the present invention
`there is provided a method of segmenting an image, the
`image comprising a plurality of pixels, wherein said method
`comprises the steps of: allocating one or more pixels as
`seeds: growing regions from said seeds so as to segment the
`image into a number of regions, wherein a number of pixels
`that border said growing regions are considered and that
`pixel of said number that is most similar in a property to a
`region it borders is appended to that region and the said
`property of the appended region is ttpdated and said growing
`step is
`repeated until no pixels bordering the growing
`regions are available.
`According to still another aspect of the present invention
`there is provided a method of segmenting an image. the
`image comprising a plurality of pixels, wherein said method
`comprises the steps of: allocating one or more pixels as
`seeds in the image: growing regions of pixels front said
`seeds, wherein said growing step comprises the sub—steps of:
`generating a list of pixels that border the growing regions:
`scanning a number of said pixels of the list; detemrining. for
`each said scanned pixel. a value indicative of the similarity
`of the luminance of said scanned pixel and the correspond-
`
`18
`
`

`
`US 7,031,517’ B1
`
`3
`ing lu111inance ofa growing region that said scanned pixel
`borders; selecting a pixel that has a minimum said value:
`appending said selected pixel
`to said growing region it
`borders: updating the said corresponding luminace of the
`appended region; repeating the sub-steps of the growing step
`until
`there are no more pixels that border the growing
`regions.
`According to still another aspect of the present invention
`there is provided a method of encoding an image having a
`number of segmented regions. the method comprising the
`steps of: splitting said image into a plurality of rectangular
`areas. wherein each rectangular area comprises a said region
`or part thereof forming a dominant portion of the rectangular
`area; merging said rectangular areas which have a common
`said dominant portion and share a common edge; and
`outputting the vertices of the merged rectangular areas as a
`representation of the segmented image.
`According to still another aspect of the present invention
`there is provided a method of seg111c11ti11g an image,
`the
`image comprising a plurality of pixels and the method
`comprising the steps of: allocating one or more pixels as
`seeds; growing regions from said seeds so as to segment the
`image into a number of regions; storing the segmented
`image in a queue; performing the following sub-steps until
`said queue is empty; removing and selecting the segmented
`image or a previously divided rectangular area of said
`segmented image currently stored first in the queue as the
`current rectangular area; computing a value representative of
`the size of a dominant segmented region within said current
`area divided by the sire of said current area; storing the
`co-ordinates of the current area, if said value is greater than
`a predetermined threshold, otherwise; dividing said current
`area into a plurality of rectangular areas and adding the said
`plurality of rectangular areas to the queue; merging said
`divided rectangular areas which have a common dominant
`region and share a common edge: and outputting the vertices
`of the merged rectangular areas as a representation of the
`segmented image.
`According to still another aspect of the present invention
`there is provided a method of segmenting an image,
`the
`image comprising a plurality of pixels. wherein said method
`comprises the steps of: distributing seeds in areas of said
`image as a function to fa property of said pixels within those
`areas. wherein fewer seeds are allocated to those areas ofthe
`image having pixels homogeneous in said property: and
`growing regions from said seeds so as to segment the image
`into a ntunber of regions, wherein a number of pixels that
`border said growing regions are considered and that pixel of
`said number that is most similar in said property to a region
`it borders is appended to that region and the said property of
`the appended region is updated and said growing step is
`repeated until no pixels bordering the growing regions are
`available.
`
`According to still another aspect of the present invention
`there is provided a method of segmenting an image,
`the
`image comprising a plurality of pixels, wherein said method
`comprises the steps of: (a) allocating pixels as seeds i11 areas
`of the image as a function of the luminance of the pixels
`within those areas, wherein fewer seeds are allocated to
`those areas of the image having pixels of homogeneous
`luminance and wherein said seeds form growing regions; (b)
`generating a list of pixels that border the growing regions;
`(c) scanning a number of said pixels of the list: (cl) deter-
`mining, for each said scanned pixel, a value indicative of the
`similarity of the lttminance of said scanned pixel and the
`corresponding lttminance of a growing region that said
`scanned pixel borders;
`(e} selecting a pixel
`that has a
`
`10
`
`15
`
`30
`
`35
`
`4U
`
`55
`
`60
`
`4
`to
`minim1u11 said value: (1) appending said selected pixel
`said growing region it borders; (g) updating the said corre-
`sponding luminace of the appended region; (11) repeating the
`sub-steps (b) to (g) until there are no more pixels that border
`the growing regions.
`According to still another aspect of the present invention
`there is provided apparatus for seeding an image having a
`plurality of pixels.
`the apparatus comprising: means for
`dividing the image into one or more regions; means for
`allocating. for each region. one or more seeds as a function
`of the contrast of said pixels within the region and the size
`of the region as compared to the size of the image. wherein
`fewer seeds are allocated to those regions of the image
`having pixels of homogeneous contrast: and means for
`storing the pixel locations of each allocated seed.
`According to still another aspect of the present invention
`there is provided apparatus for seeding an image comprising
`a plurality of pixels. wherein said apparatus comprises:
`means for selecting the image or a previously divided area
`of the image as the current area: means for seeding the center
`of said current area when the contrast of the pixels and the
`size of current area meet a first predetermined condition;
`means for subdividing said current area when the contrast of
`the pixels and the Si:/.C of current area meet a second
`predetermined condition: means for unifomtly seeding said
`current area in a low density n1am1er when the contrast of the
`pixels and the size ofcurrent area meet a third predetermined
`condition; means for subdividing said cttrrent area when
`contrast of the pixels and the size of current area meet a
`fourth predetermined condition: means for uniformly seed-
`ing said current arca in a high density manner when the
`contrast of the pixels and the size of current area meet a fifth
`predetermined condition: and means for repeating the opera-
`tions of the selection and seeding means until all of said
`divided areas are seeded. wherein fewer seeds are allocated
`to those areas of the image having homogeneous contrast.
`According to still another aspect of the present invention
`there is provided apparatus for segmenting a11 image, the
`image comprising a plurality of pixels, wherein said appa-
`ratus comprises: means for allocating one or more pixels as
`seeds; means for growing regions from said seeds so as to
`segment the image into a number of regions. wherein a
`number of pixels that border said growing regions are
`considered and that pixel of said number that is most similar
`in a propeny to a region it borders is appended to that region
`and the said property of the appended region is updated and
`said growing step is repeated until no pixels bordering the
`growing regions are available.
`According to still another aspect of the present invention
`there is provided apparatus for segmenting an image. the
`image comprising a plurality of pixels. wherein said appa-
`ratus comprises: means for allocating one or more pixels as
`seeds i11 the image: means for growing regions of pixels
`from said seeds, wherein said growing means comprises:
`means for generating a list of pixels that border the growing
`regions, sca1u1i11g a number of said pixels of tl1c list: means
`for detertnining, for each said scanned pixel, a value indica-
`tive of the similarity of the luminance of said scatmed pixel
`and the corresponding luminance of a growing region that
`said scanned pixel borders: means for selecting a pixel that
`has a minimum said value; means for appending said
`selected pixel to said growing region it borders; means for
`updating the said corresponding ltuninace of the appended
`region: and means for repeating the operations of the grow-
`ing means until there are no 111ore pixels that border the
`growing regions.
`
`19
`
`

`
`US 7,031,517’ B1
`
`5
`According to still another aspect of the present invention
`there is provided apparatus for encoding an image having a
`number of segmented regions. the apparatus comprising:
`means for splitting said image i11to a plurality of rectangular
`areas. wherein each rectangular area comprises a said region
`or part thereof forming a dominant portion of the rectangular
`area; means for merging said rectangular areas which have
`a common said dominant portion and share a conu11o11 edge;
`and means for outputting the vertices of the merged rectan-
`gular areas as a representation ofthe segmented image.
`According to still another aspect of the present invention
`there is provided apparatus for segmenting an image, the
`image comprising a plurality of pixels and the apparatus
`comprising; means for allocating one or more pixels as
`seeds; means for growing regions from said seeds so as to
`segment the image into a number of regions; means for
`storing the segmented image in a queue; means for removing
`and selecting, until said queue is empty,
`the segmented
`image or a previously divided rectangular area of said
`segmented image currently stored first in the queue as the
`current rectangular area; means for computing a value
`representative of the size of the dominant segmented region
`within said current area divided by the size of said current
`area; means for storing the co-ordinates of the current area,
`if said value is greater than a predetennined threshold;
`means for dividing said current area into a plurality of
`rectangular areas of said current area and adding, the said
`plurality of rectangular areas to the queue, if said value is
`less than or equal to said predetermined threshold: means for
`merging said divided rectangular areas which have a com-
`mon dominant region and share a common edge; and means
`for outputting the vertices of the merged rectangular areas as
`a representation of the segmented image.
`According to still another aspect of the present invention
`there is apparatus for segmenting an image.
`the image
`comprising a plurality of pixels, wherein said apparatus
`comprises: means for distributing seeds in areas of said
`image as a function ofa property of said pixels within those
`areas. wherein fewer seeds are allocated to those areas of the
`image having pixels homogeneous in said property; and
`means for growing regions from said seeds so as to segment
`the image into a number of regions. wherein a number of
`pixels that border said growing regions are considered and
`that pixel ofsaid number that is most similar in said property
`to a region it borders is appended to that region and the said
`property ofthe appended region is updated and said growing
`step is repeated tuitil no pixels bordering the growing
`regions are available.
`According to still another aspect of the present invention
`there is provided apparatus for segmenting an image, the
`image comprising a plurality of pixels, wherein said appa-
`ratus comprises: means for allocating pixels as seeds in areas
`of the image as a function of the luminance of the pixels
`within those areas, wherein fewer seeds are allocated to
`those areas of the image having pixels of homogeneous
`luminance a11d wherein said seeds fomi growing regions;
`means for generating a list of pixels that border the growing
`regions; means for scanning a n1u11ber of said pixels of the
`list: means for determining. for each said scamied pixel. a
`value indicative of the similarity of the luminance of said
`scamted pixel and the corresponding luminance of a growing
`region that said scanned pixel borders; means for selecting
`a pixel that has a minimum said value: means for appending
`said selected pixel to said growing region it borders; means
`for updating the said corresponding luminace of the
`appended region: and means for repeating the operations of
`the allocating means, generating means_. scamiing means_.
`
`10
`
`15
`
`30
`
`35
`
`4U
`
`55
`
`60
`
`6
`determining means, appending means, and updating means
`until
`there are no more pixels that border the growing
`regions.
`According to still another aspect of the present invention
`there is provided a computer program product. including a
`computer readable medium having recorded thereon a com-
`puter program for seeding an image. the image comprising
`a plurality of pixels, wherein said computer program product
`comprises: means for distributing seeds in areas of said
`image as a function ofa property of said pixels within those
`areas. wherein fewer seeds are allocated to those areas of the
`
`image having pixels homogeneous in said property.
`According to still another aspect of the present invention
`there is provided a computer program product. including a
`computer readable medium having recorded thereon a com-
`puter program for seeding an image having a plurality of
`pixels. the computer program product comprising: means for
`dividing the image into one or more regions: means for
`allocating, for each region, one or more seeds as a function
`of the contrast of said pixels within the region and the size
`of the region as compared to the size of the image. wherein
`fewer seeds are allocated to those regions of the image
`having pixels of homogeneous contrast; and means for
`storing the pixel locations of each allocated seed.
`According to still another aspect of the present invention
`there is provided a computer program product, including a
`computer readable mtrdium having recorded thereon a com-
`puter program for seeding an image comprising a plurality
`of pixels. wherein said computer program product com-
`prises: means for selecting the image or a previously divided
`area of the image as the current area; means tor seeding the
`center of said current area when the contrast of the pixels
`and the size of current area meet a first predetermined
`condition; means for subdividing said current area when the
`contrast of the pixels and the size of current area meet a
`second predetennined condition; means for uniformly seed-
`ing said current area in a low density manner when the
`contrast ofthe pixels and the size of current area meet a third
`predetermined condition; means for subdividing said current
`area when contrast of the pixels and the sire of current area
`meet a fourth predetennined condition; means for unifonnly
`seeding said current area in a high density manner when the
`contrast of the pixels and the size ofeurrent area meet a fifth
`predetermined condition; and means for repeating the opera-
`tions of the selection and seeding means until all of said
`divided areas are seeded, wherein fewer seeds are allocated
`to those areas of the image having homogeneous contrast.
`According to still another aspect of the present invention
`there is provided a computer program product, including a
`computer readable meditun having recorded thereon a com-
`puter program for segmenting an image,
`the image com-
`prising a plurality of pixels. wherein said computer program
`product comprises: means for allocating one or more pixels
`as seeds: and means for growing regions from said seeds so
`as to segment the image into a number of regions. wherein
`a number of pixels that border said growing regions are
`considered and that pixel of said number that is most similar
`in a property to a region it borders is appended to that region
`and the said property of the appended region is updated and
`said growing step is repeated until no pixels bordering the
`growing regions are available.
`According to still another aspect of the present invention
`there is provided a computer program product. including a
`computer readable m<:ditLn1 having recorded thereon a com-
`puter program thr segmenting an image. the image com-
`prising a plurality of pixels. wherein said computer program
`product comprises: means for allocating one or more pixels
`
`20
`
`

`
`US 7,031,517’ B1
`
`7
`as seeds i11 tl1e image; means for growing regions of pixels
`from said seeds, wherein said gnawing means comprises:
`means for generating a list of pixels that border the growing
`regions: scaruting a number of said pixels of the list: means
`for detennining. for each said scanned pixel. a value indica-
`tive of the similarity of the luminance of said scanned pixel
`and the corresponding luminance of a growing region that
`said scanned pixel borders: means for selecting a pixel that
`11as a minimum said value; means for appending said
`selected pixel to said growing region it borders: means for
`updating the said corresponding luminace of the appended
`region: and means for repeating the operations of the grow-
`ing tueans until there are no more pixels that border the
`growing regions.
`According to still another aspect of the present invention
`there is provided a computer program product; including a
`computer readable medium having recorded thereon a com-
`puter program for encoding an image having a number of
`segmented regions, the computer progratn product compris-
`ing: means for splitting said image into a plurality of
`rectangular areas, wherein each rectangular area comprises
`a said region or part thereof forming a dominant portion of
`the rectangular area; means for merging said rectangular
`areas which have a common said dominant portion and share
`a common edge; and means for outputting the vertices ofthe
`merged rectangular areas as a representation of the seg-
`mented image.
`According to still another aspect of the present invention
`there is provided a computer program product. including a
`computer readable mediutu having recorded thereon a com-
`puter program for segmenting an image; the image com-
`prising a plurality of pixels and the computer program
`product comprising: means for allocating one or more pixels
`as seeds; means for growing regions front said seeds so as
`to segment the image into a number of regions; means for
`storing the segmented image in a queue. means for removing
`and selecting. until said queue is empty,
`the segmented
`image or a previously divided rectangular area of said
`segmented image currently stored first in the queue as the
`current rectangular area, means for contputing a value
`representative of the size of the dominant segmented region
`within said current area divided by the size of said current
`area; means for storing the co-ordinates of the current area,
`if said value is greater than a predetennined threshold;
`means for dividing said current area into a plurality of
`rectangular areas of said current area and adding the said
`plurality of rectangular areas to the queue, if said value is
`less than or equal to said predetermined th.reshold_: means for
`merging said divided rectangular areas which have a com-
`mon dominant region and share a common edge; and means
`for outputt