Image segmentation

BACKGROUND

p-0002Various applications, for example internet shopping, require searching images based on color. In order to search an image by color the image needs to be associated with one or more colors. The association can be performed by segmenting the image into a foreground portion and a background portion, and identifying the colors from the foreground portion. Often, segmentation techniques require user intervention to initialize the foreground and the background portion. For complex images effort of user intervention needed is high. For example, the user needs to initialize Trimap T={Tb, Tf, Tu}, where Tb is the background portion, Tf is the foreground portion and Tu is unknown portion in the image. Further, the segmenting becomes unmanageably complex when thousands of images are processed.

p-0003In light of foregoing discussion there is a need for an efficient technique for segmenting images.

SUMMARY

p-0004Embodiments of the disclosure described herein provide an article of manufacture, a method, and a system for image segmentation.

p-0005An example of an article of manufacture includes a machine-readable medium. Further, the machine-readable medium carries instructions operable to cause a programmable processor to perform obtaining images of objects and metadata associated with each image. A portion of the each image is automatically initialized as at least one of a foreground portion and a background portion according to the metadata associated with the each image. The each image is then segmented into the foreground portion and the background portion. Further, at least one foreground portion depicting an object of the desired characteristics is determined. Furthermore, an image corresponding to the at least one foreground portion is provided.

p-0006An example of a method of identifying objects having desired characteristics includes receiving electronically, in a computer system, a request for objects having desired characteristics. The method includes obtaining images of objects and metadata associated with each image. Further, the method includes automatically initializing a portion of the each image as at least one of a foreground portion and a background portion according to the metadata associated with the each image. Furthermore, the method includes segmenting the each image into the foreground portion and the background portion. In addition, the method includes determining at least one foreground portion depicting an object of the desired characteristics. Further, the method includes electronically providing an image corresponding to the at least one foreground portion.

p-0007An example of a system for identifying objects having desired characteristics includes one or more remote electronic devices. Further, the system includes a communication interface in electronic communication with the one or more remote electronic devices for receiving a request for an object having the desired characteristics. Furthermore, the system includes one or more storage devices for storing images of objects. In addition, the system includes a memory for storing instructions. Further, the system includes a processor responsive to the instructions to automatically segment each image into a foreground portion and a background portion, to determine at least one foreground portion depicting the object having the desired characteristics, and to provide an image corresponding to the at least one foreground portion.

BRIEF DESCRIPTION OF THE FIGURES

p-0008The illustrative examples in drawings are not necessarily drawn to scale. Further, the boundaries in the drawings are not necessarily accurate.

p-0009<figref idrefs="DRAWINGS">FIG. 1</figref> is a block diagram of an environment, in accordance with which various embodiments can be implemented;

p-0010<figref idrefs="DRAWINGS">FIG. 2</figref> is a block diagram of a server, in accordance with one embodiment;

p-0011<figref idrefs="DRAWINGS">FIG. 3</figref> is a flowchart illustrating a method of identifying objects having desired characteristics, in accordance with one embodiment;

p-0012<figref idrefs="DRAWINGS">FIG. 4</figref> is an exemplary screen shot of image segmentation, in accordance with one embodiment;

p-0013<figref idrefs="DRAWINGS">FIG. 5</figref> is an exemplary screen shot of image segmentation, in accordance with another embodiment; and

p-0014<figref idrefs="DRAWINGS">FIG. 6</figref> is an exemplary screen shot of image segmentation, in accordance with yet another embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

p-0015<figref idrefs="DRAWINGS">FIG. 1</figref> is a block diagram of an environment <b>100</b>, in accordance with which various embodiments can be implemented. The environment <b>100</b> includes one or more electronic devices, for example an electronic device <b>105</b>A, an electronic device <b>105</b>B and an electronic device <b>105</b>N connected to each other through a network <b>110</b>. Examples of the electronic devices include, but are not limited to, computers, mobile devices, laptops, palmtops, and personal digital assistants (PDAs). Examples of the network <b>110</b> include, but are not limited to, a Local Area Network (LAN), a Wireless Local Area Network (WLAN), a Wide Area Network (WAN), wired network, wireless network, internet and a Small Area Network (SAN). Examples of a protocol used for communication by the electronic devices include, but are not limited to, an internet protocol, a wireless application protocol (WAP), Bluetooth, zigbee, infrared and any protocol applicable for communicating data.

p-0016The electronic devices are connected to a server <b>115</b> through the network <b>110</b>. In some embodiments, the electronic devices can be directly connected to the server <b>115</b>. The server <b>115</b> is connected to a database <b>120</b>.

p-0017The server <b>115</b> receives a request for identifying objects having desired characteristics from at least one electronic device, for example the electronic device <b>105</b>A. Further, the server <b>115</b> obtains images of the objects and metadata, associated with each image from the database <b>120</b>. The server <b>115</b> automatically initializes a portion of the each image as at least one of a foreground portion and a background portion based on the metadata associated with the each image. Further, the server <b>115</b> segments the each image into the foreground portion and the background portion using various segmentation techniques. Examples of the segmentation techniques include, but are not limited to, a GrabCut technique, Graph Cut, Bayes Matting, and Intelligent Scissors.

p-0018<figref idrefs="DRAWINGS">FIG. 2</figref> is a block diagram of the server <b>115</b>, in accordance with one embodiment.

p-0019The server <b>115</b> includes a bus <b>205</b> or other communication mechanism for communicating information, and a processor <b>210</b> coupled with the bus <b>205</b> for processing information. The processor <b>210</b> can be a hardwired circuit which performs functions in response with instructions. The server <b>115</b> also includes a memory <b>240</b>, such as a random access memory (RAM) or other dynamic storage device, coupled to the bus <b>205</b> for storing information and instructions to be executed by the processor <b>210</b>. The memory <b>240</b> can be used for storing temporary variables or other intermediate information. The server <b>115</b> further includes a read only memory (ROM) <b>235</b> or other static storage device coupled to the bus <b>205</b> for storing static information and instructions for the processor <b>210</b>. A storage unit <b>230</b>, such as a magnetic disk or optical disk, is provided and coupled to the bus <b>205</b> for storing information and instructions.

p-0020The server <b>115</b> can be coupled via the bus <b>205</b> to a display <b>255</b>, for example a cathode ray tube (CRT) display, a liquid crystal display (LCD), a light emitting diode (LED) display, for displaying information to a user. An input device <b>250</b>, including alphanumeric and other keys, is coupled to the bus <b>205</b> for communicating information and command selections to the processor <b>210</b>. Another type of user input device is a cursor control <b>245</b>, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to the processor <b>210</b> and for controlling cursor movement on the display <b>255</b>.

p-0021Various embodiments are related to the use of the server <b>115</b> for implementing the techniques described herein. In one embodiment, the techniques are performed by the processor <b>210</b> using information and executing instructions included in the memory <b>240</b>. Execution of the instructions included in memory <b>240</b> causes processor <b>210</b> to perform the process steps described herein. The information can be read into the memory <b>240</b> from another machine-readable medium, such as the storage unit <b>230</b>.

p-0022The term “machine-readable medium” as used herein refers to any medium that participates in providing data that causes a machine to operate in a specific fashion. In an embodiment implemented using the server <b>115</b>, various machine-readable medium are involved, for example, in providing instructions to the processor <b>210</b> for execution. The machine-readable medium can be a storage media. Storage media includes both non-volatile media and volatile media. Non-volatile media includes, for example, optical or magnetic disks, such as the storage unit <b>230</b>. Volatile media includes dynamic memory, such as the memory <b>240</b>. All such media must be tangible to enable the information carried by the media to be detected by a physical mechanism that reads the information into a machine.

p-0023Common forms of machine-readable medium include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CD-ROM, any other optical medium, punchcards, papertape, any other physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge.

p-0024In another embodiment, the machine-readable medium can be a transmission media including coaxial cables, copper wire and fiber optics, including the wires that include the bus <b>205</b>. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.

p-0025The server <b>115</b> also includes a communication interface <b>225</b> coupled to the bus <b>205</b>. The communication interface <b>225</b> provides a two-way data communication coupling to a network <b>110</b>. For example, communication interface <b>225</b> can be an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface <b>225</b> can be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links can also be implemented. In any such implementation, communication interface <b>225</b> sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information. The facsimiles can be received by the server <b>115</b> through the communication interface <b>225</b>. The server <b>115</b> is in electronic communication with other electronic devices through the communication interface <b>225</b> and the network <b>110</b>.

p-0026In some embodiments, the processor <b>210</b> may include an initializing unit <b>215</b> for processing the automatic initialization of at least one object having desired characteristics into a portion of images of objects as at least one of a foreground portion and a background portion. Further, the automatic initialization is performed using metadata associated with each image. Examples of the desired characteristics include, but are not limited to, category and colors of the objects.

p-0027The segmenting unit <b>220</b> segments the each image into the foreground portion and the background portion. Furthermore, the segmented image is displayed using the display <b>255</b>.

p-0028In some embodiments, the processor <b>210</b> may not include the initializing unit <b>215</b> and the segmenting unit <b>220</b>. The functions of the initializing unit <b>215</b> and the segmenting unit <b>220</b> are performed by the processor <b>210</b>.

p-0029<figref idrefs="DRAWINGS">FIG. 3</figref> is a flowchart illustrating a method of identifying objects having desired characteristics, in accordance with one embodiment.

p-0030At step <b>305</b>, images of objects and metadata associated with each image are obtained. Examples of the desired characteristics include, but are not limited to, colors and category of the objects. Examples of the category of the objects include, but are not limited to, a shirt, a pant, and a floral object.

p-0031The images can be obtained in a computer system in response to a request sent by a user for objects having desired characteristics. The user uses an online application, for example internet shopping, running on an electronic device for purchasing objects. The user may require searching images of the objects or the objects on the online application. The user specifies the desired characteristics of the objects which are sent as the request to the computer system by the electronic device of the use. Examples of the online applications include, but are not limited to, Yahoo!® Search.

p-0032In some embodiments, the images can be stored in distributed environment and can be fetched by the computer system in response to the request.

p-0033At step <b>310</b>, a portion of the each image is automatically initialized as at least one of a foreground portion and a background portion according to the metadata associated with the each image.

p-0034The automatic initialization is performed by estimating the locations of the foreground and the background portions in an image, based on empirical observations. For example, skin color is automatically identified by using various skin tone models in an image and the portion corresponding to the skin color is initialized as the background portion. Examples of the various skin tone models include, but are not limited to, the model provided in the publication titled, “Statistical color models with application to skin detection” by Michael J. Jones and James M. Rehg published in International Journal of Computer Vision archive, Volume 46, Issue 1 (January 2002) table of contents, Pages: 81-96, Year of Publication: 2002; and the model provided in the publication titled, “Finding Naked People” by Margaret M. Fleck, David A. Forsyth and Chris Bregler published in Lecture Notes In Computer Science; Vol. 1065, archive, Proceedings of the 4th European Conference on Computer Vision—Volume II—Volume II table of contents, Pages: 593-602, Year of Publication: 1996, which are incorporated herein by reference. Further, if a floral image includes green portions then the green portions are initialized as the background portion. Moreover, the red, green and blue color channels of the image are transformed to log-opponent channels I, Rg, By by using the following exemplary equations:

p-0035<br /><i>L</i>(<i>x</i>)=105 log₁₀(<i>x+</i>1);

p-0036<br /><i>I=L</i>(<i>G</i>);

p-0037<br /><i>Rg=L</i>(<i>R</i>)−<i>L</i>(<i>G</i>);

p-0038<br /><i>By=L</i>(<i>B</i>)−[<i>L</i>(<i>G</i>)+<i>L</i>(<i>R</i>)]/2;

p-0039<br /><i>H=</i>tan⁻¹(<i>Rg/By</i>); and

p-0040<br /><i>S=</i>(<i>Rg</i>²<i>+Bn</i>²)^1/2.

p-0041The intensity information is captured by the I channel and the color information is captured by Rg and By channels. The decision portion for skin portion is: (110&lt;H&lt;150,20&lt;S&lt;60) or (130&lt;H&lt;170, 30&lt;S&lt;130).

p-0042The automatic initializing is performed based on the metadata of the object. The metadata includes color of the object and category of the object. The automatic initializing of various categories is explained with the help of examples below.

EXAMPLE 1

Category of the Object is Shirt

p-0043An image including a shirt is automatically initialized by identifying corner portions of the image as the background portion. The skin color present in the image is also identified using various skin tone models and initialized as the background portion. A central portion, for example a blob of 5*5 in the center, of the image is initialized as the foreground portion. The central portion can be predefined and can be proportionate to the dimensions of the image.

EXAMPLE 2

Category of the Object is Pant

p-0044An image including a pant is automatically initialized by identifying corner portions of the image as the background portion. The skin color present in the image is also identified using the various skin tone models and initialized as the foreground portion. Edges present in the pant image are identified using various edge detectors and blobs around the edges are initialized as the foreground portion. Examples of the edge detectors include, but are not limited to, canny edge detector.

EXAMPLE 3

Category of the Object is Floral

p-0045An image including a floral is automatically initialized by identifying corner portions of the image as the background portion. The green color textured patches present in the floral image is also identified and initialized as the background portion. The automatic initialization performed in the floral image may not require initializing the foreground portion.

p-0046In some embodiments, the green color can be detected by using color spaces, for example, opponent color space, HSV (hue, saturation, value), HSL (hue, saturation, lightness) and RGB (red, green, blue). A color model is a mathematical model describing the way colors can be represented as multiples of numbers, typically as three or four values of color components. When the color model is associated with a precise description of how the color components are to be interpreted, for example in viewing conditions, the resulting set of colors is called color space.

p-0047For example, the automatic initialization performed in the floral image can use the method of transforming pixels in RGB color space of the floral image into opponent space using:

p-0048<br /><i>i=</i>(<i>R+B+G</i>)/3;

p-0049<br /><i>o</i>1=(<i>R+G−</i>2*<i>B</i>)/4+0.5; and

p-0050<br /><i>o</i>2=(<i>R+B−</i>2*<i>G</i>)/4+0.5.

p-0051Each pixel's i, o<b>1</b> and o<b>2</b> values of the floral image are checked to see whether they fall in the ranges specified below: <ul><li id="ul0001-0001" num="0042">40&lt;i&lt;80 and 10&lt;o<b>1</b>&lt;35 and −30&lt;o<b>2</b>&lt;0.</li></ul>

p-0052Each pixel which is in the range is classified as green pixel and each pixel which is not in the range is classified as non-green pixel.

p-0053At step <b>315</b>, the each image is segmented into the foreground portion and the background portion. The automatically initialized portions are considered as inputs for the segmentation. The segmentation can be performed using various segmenting techniques. Examples of the segmenting techniques include, but are not limited to, GrabCut technique, Graph Cut, Bayes Matting, and Intelligent Scissors.

p-0054In some embodiments, based on the initialization an initial segmentation model is built which builds a color distribution. The color distribution can then be extended throughout the picture to initialize the color pixels matching the color of the foreground portion as the foreground portion. Similar approach can be used for the background portion. The foreground portion and the background portion are then segmented.

p-0055At step <b>320</b>, at least one foreground portion depicting an object of the desired characteristics is determined. Each foreground portion can be checked and the foreground portions meeting the desired color and desired category of the object is selected as the foreground portion depicting object of the desired characteristic. The color of the foreground is considered to be the color of the image and the object.

p-0056In some embodiments, the images of the objects are tagged with the colors and the categories, and stored. When a request for objects with desired characteristics is received from the user then the tags can be checked to determine the objects of the desired characteristics. The foreground can include one or more colors and hence, the image can be tagged with the one or more colors.

p-0057At step <b>325</b>, an image corresponding to the at least one foreground portion is provided electronically. The image includes the object having the desired characteristics.

p-0058In some embodiments, the user after looking at the image may purchase the object included in the image. A transaction can be made by the user and the object can then be delivered to the user.

p-0059It will be appreciated that the method of automatically initializing and segmenting the image can be used in various applications, for example applications in which the image needs to be associated with a color.

p-0060<figref idrefs="DRAWINGS">FIG. 4</figref> is an exemplary screen shot of image segmentation, in accordance with one embodiment.

p-0061<figref idrefs="DRAWINGS">FIG. 4</figref> includes an image <b>405</b>. The image includes a shirt portion <b>410</b>. A central portion <b>415</b>, for example a blob of 5*5, of the shirt portion <b>410</b> is detected and automatically initialized as the foreground portion. The skin portions, for example a skin portion <b>420</b>, present in the shirt portion <b>410</b> are detected using various skin tone models and are automatically initialized as the background portion. Further, the corners, for example a corner <b>425</b>, of the shirt portion <b>410</b> are also automatically initialized as the background portion.

p-0062The image <b>405</b> is then segmented into the foreground portion and the background portion. The segmentation results in a foreground portion, for example a foreground portion <b>430</b>. The image <b>405</b> is associated or tagged with the color of the foreground <b>430</b>.

p-0063In the illustrated example, based on initialization an initial segmentation model can be built during segmentation. For example, building a color distribution for the automatic initialization of the foreground portions and background portions. The color distribution can be extended throughout the image to initialize the color pixels matching the color of the foreground portion as the foreground portion. For example, the foreground <b>430</b> matches the foreground color distribution and is initialized as the foreground portion.

p-0064The initial segmentation model is built with all the known background pixels as the background portion and known foreground portion as the foreground portion. Further, Gaussian Mixture Models (GMMs) are created for initial foreground and background classes. Each pixel in the foreground class is assigned to the Gaussian component in the foreground GMM and each pixel in the background class is assigned to the Gaussian component in the background GMM and is assigned to background GMM. New GMM's can be learnt from the new pixel allocation. New tentative allocation of foreground pixel and background pixel is performed using graph cut. The process followed in the GMM is repeated until the classification converges. In the process of assignment the best fit assignment in the GMM and where segmentation converges can be considered as the final assignment.

p-0065In <figref idrefs="DRAWINGS">FIG. 4</figref>, the cap region is also assigned as foreground. This is because the initially unassigned regions (cap regions) well fit the foreground GMMs and with this assignment the segmentation converges.

p-0066<figref idrefs="DRAWINGS">FIG. 5</figref> is an exemplary screen shot of image segmentation, in accordance with another embodiment.

p-0067<figref idrefs="DRAWINGS">FIG. 5</figref> includes an image <b>505</b>. The image includes a pant portion <b>510</b>. Edges present in the pant portion <b>510</b>, for example an edge portion <b>515</b>, are identified using various edge detectors and blobs around the edges, for example a blob <b>520</b> are initialized as the foreground portion. Examples of the edge detectors include, but are not limited to, canny edge detectors. The corners, for example a corner <b>525</b>, of the pant portion <b>510</b> are also automatically initialized as the background portion. The skin portion, for example a skin portion <b>530</b>, present in the pant portion <b>510</b> is detected using various skin tone models and is automatically initialized as the background portion. The segmentation results in a foreground portion for example a foreground portion <b>535</b>. The image <b>505</b> is associated or tagged with the color of the foreground <b>535</b>.

p-0068<figref idrefs="DRAWINGS">FIG. 6</figref> is an exemplary screen shot of image segmentation, in accordance with yet another embodiment.

p-0069<figref idrefs="DRAWINGS">FIG. 6</figref> includes an image <b>605</b>. The image includes a floral portion <b>610</b>. The green texture, for example a texture <b>615</b> is detected in the image <b>605</b> and the green texture is automatically initialized as the background portion. Further, the corners, for example a corner <b>620</b>, of the floral image are also automatically initialized as the background portion. The image <b>605</b> is then segmented into the foreground portion and the background portion. The segmentation results in a foreground <b>625</b>. The image <b>605</b> is associated or tagged with the color of the foreground <b>625</b>.

p-0070While exemplary embodiments of the present disclosure have been disclosed, the present disclosure may be practiced in other ways. Various modifications and enhancements may be made without departing from the scope of the present disclosure. The present disclosure is to be limited only by the claims.