# US 9,519,974 B2 · Image processing apparatus and image processing method > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,519,974 B2 - Document ID: US9519974B2 - Status: Granted - Kind: B2 - Application number: 14/827,734 - Filed: 2015-08-17 - Published: 2016-02-25 - Granted: 2016-12-13 - Earliest claimed: 2014-08-20 - Assignees: Canon Kabushiki Kaisha - Applicants: Canon Kabushiki Kaisha - Inventors: Masahiro Ariizumi; Noriyasu Hashiguchi - Web page: https://patentgrep.com/patent/US9519974B2 ## CPC - G06T 7/11: Region-based segmentation - G06F 18/23213: with fixed number of clusters, e.g. K-means clustering - G06T 1/60: Memory management - G06T 7/174: involving the use of two or more images - G06T 7/187: involving region growing; involving region merging; involving connected component labelling - G06T 7/40: Analysis of texture (depth or shape recovery from texture G06T7/529) - G06T 7/90: Determination of colour characteristics - G06T 2207/10024: Color image - G06T 2207/20021: Dividing image into blocks, subimages or windows - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Plural block images are generated by dividing an input image into blocks each of which has a predetermined size. Clustering of pixels contained in the plural block images is performed based on a representative point associated with each of those block images to apply region segmentation to those block images. The representative point is a part of plural representative points disposed in the input image. The clustering in a target block image of the region segmentation is performed by referring to a representative point in the target block image, a representative point of a processed block image, and a representative point of an unprocessed block image. The processed and unprocessed block images are adjacent to the target block image. ## Claims ### Claim 1 An image processing apparatus for performing region segmentation of an image, comprising: a memory; and a processor in communication with the memory that, upon execution of codes stored in the memory, functions as: a generation unit configured to generate a plurality of block images by dividing an input image into blocks each of which has a predetermined size; and a segmentation unit configured to perform clustering of pixels contained in the plurality of block images based on a representative point associated with each of those block images so as to apply the region segmentation to those block images, wherein the representative point is a part of a plurality of representative points disposed in the input image, wherein the clustering in a target block image of the region segmentation is performed by referring to a representative point in the target block image, a representative point of a processed block image on which the region segmentation has been performed, and a representative point of an unprocessed block image on which the region segmentation has not been performed yet, and wherein the processed block image and the unprocessed block image are adjacent to the target block image. ### Claim 2 (depends on 1) The apparatus according to claim 1, wherein the segmentation unit performs the clustering by referring to information of representative points which exist in a predetermined range around a position of a pixel of the target block image. ### Claim 3 (depends on 1) The apparatus according to claim 1, further comprising an update unit configured to update coordinates and color information of representative points in the target block image and the processed block image after the clustering by the segmentation unit. ### Claim 4 (depends on 3) The apparatus according to claim 3, wherein the update unit determines convergence of the clustering in the target block image. ### Claim 5 (depends on 4) The apparatus according to claim 4, wherein, until it is determined that the clustering in the target block image is converged, the segmentation unit repeats the clustering in the target block image by referring to information of the updated representative points, and the update unit repeats the update of the representative points. ### Claim 6 (depends on 3) The apparatus according to claim 3, wherein the update unit does not update coordinates or color information of the representative point in the unprocessed block image. ### Claim 7 (depends on 3) The apparatus according to claim 3, wherein the update unit performs the update of the representative points in the target block image and the processed block image using a first method, and updates coordinates and color information of the representative point in the unprocessed block image using a second method different from the first method. ### Claim 8 (depends on 7) The apparatus according to claim 7, wherein change amounts of the coordinates of the representative point before and after the update by the second method are smaller than those by the first method. ### Claim 9 (depends on 1) The apparatus according to claim 1, further comprising an initialization unit configured to initialize coordinates of the plurality of representative points so that those representation points are disposed in a grid shape in the input image. ### Claim 10 (depends on 9) The apparatus according to claim 9, wherein the initialization unit initializes color information of each of the plurality of representative points based on color information of a pixel corresponding to the representative point and color information of surrounding pixels of the corresponding pixel. ### Claim 11 (depends on 9) The apparatus according to claim 9, wherein the initialization unit initializes color information of each of the plurality of representative points based on an average value of color information of a pixel corresponding to the representative point and color information of surrounding pixels of the corresponding pixel. ### Claim 12 (depends on 9) The apparatus according to claim 9, wherein the initialization unit initializes color information of each of the plurality of representative points based on a median of color information of a pixel corresponding to the representative point and color information of surrounding pixels of the corresponding pixel. ### Claim 13 (depends on 1) The apparatus according to claim 1, wherein a pixel does not overlap between block images adjacent to each other. ### Claim 14 (depends on 1) The apparatus according to claim 1, wherein there is a pixel overlapping between block images adjacent to each other. ### Claim 15 (depends on 1) The apparatus according to claim 1, further comprising: a first buffer having a memory amount capable of holding at least one block image; and a second buffer configured to hold the representative points to be referred to in the region segmentation, wherein the segmentation unit performs the clustering for the target block image held in the first buffer based on information of the representative points held in the second buffer. ### Claim 16 An image processing method of performing region segmentation of an image, comprising: using a processor to perform steps of: generating a plurality of block images by dividing an input image into blocks each of which has a predetermined size; and performing clustering of pixels contained in the plurality of block images based on a representative point associated with each of those block images so as to apply the region segmentation to those block images, wherein the representative point is a part of plurality of representative points disposed in the input image, wherein the clustering in a target block image of the region segmentation is performed by referring to a representative point in the target block image, a representative point of a processed block image on which the region segmentation has been performed, and a representative point of an unprocessed block image on which the region segmentation has not been performed yet, and the processed block image and the unprocessed block image are adjacent to the target block image. ### Claim 17 A non-transitory computer readable medium storing a computer-executable program for causing a computer to perform an image processing method, the method comprising steps of: generating a plurality of block images by dividing an input image into blocks each of which has a predetermined size; and performing clustering of pixels contained in the plurality of block images based on a representative point associated with each of those block images so as to apply the region segmentation to those block images, wherein the representative point is a part of plurality of representative points disposed in the input image, wherein the clustering in a target block image of the region segmentation is performed by referring to a representative point in the target block image, a representative point of a processed block image on which the region segmentation has been performed, and a representative point of an unprocessed block image on which the region segmentation has not been performed yet, and the processed block image and the unprocessed block image are adjacent to the target block image. ### Claim 18 An image processing method comprising: setting a plurality of representative points and a plurality of block images in an input image; and performing region segmentation on the plurality of block images by clustering of pixels contained in those block images based on the plurality of representative points, wherein the clustering of pixels in a target block image of the region segmentation is performed by referring to information of a representative point in the target block image, a representative point in a processed block image on which the region segmentation has been performed and which is adjacent to the target block image, and a representative point in an unprocessed block image on which the region segmentation has not been performed yet and which is adjacent to the target block image. ### Claim 19 (depends on 18) The method according to claim 18, further comprising updating the information of representative points in the target block image and the processed block image after the clustering of pixels in the target block image. ### Claim 20 (depends on 19) The method according to claim 19, wherein convergence of the clustering in the target block image is determined in the updating. ### Claim 21 (depends on 20) The method according to claim 20, wherein the clustering in the target block image by referring to information of the representative points and the updating of information of the representative points are repeated until it is determined that the clustering has converged. ### Claim 22 (depends on 19) The method according to claim 19, wherein in the updating, information of the representative point in the unprocessed block image is not updated. ### Claim 23 (depends on 19) The method according to claim 19, wherein the updating of information of the representative points in the target block image and the processed block image are performed by using a first method, and the updating of information of the representative point in the unprocessed block image is performed by using a second method different from the first method. ### Claim 24 (depends on 18) The method according to claim 18, wherein the clustering is performed by referring to information of representative points which exist in a predetermined range around the target block image. ### Claim 25 (depends on 18) The method according to claim 18, wherein the information of the representative point includes a pixel value and a position corresponding to the representative point. ### Claim 26 (depends on 25) The method according to claim 25, further comprising initializing positions of the plurality of representative points so that those representation points are disposed in a grid shape in the input image. ### Claim 27 (depends on 26) The method according to claim 26, further comprising initializing the pixel value of the representative point based on a pixel value of a pixel corresponding to the representative point and pixel values of surrounding pixels of the corresponding pixel. ### Claim 28 (depends on 26) The method according to claim 26, further comprising initializing the pixel value of the representative point based on an average value of pixel values of a pixel corresponding to the representative point and pixel values of surrounding pixels of the corresponding pixel. ### Claim 29 (depends on 26) The method according to claim 26, further comprising initializing the pixel value of the representative point based on a median of pixel values of a pixel corresponding to the representative point and pixel values of surrounding pixels of the corresponding pixel. ### Claim 30 (depends on 18) The method according to claim 18, wherein a pixel does not overlap between block images adjacent to each other. ### Claim 31 An image processing apparatus comprising: a memory; and a processor in communication with the memory that, upon execution of codes stored in the memory, functions as: a setting unit configured to set a plurality of representative points and a plurality of block images in an input image; and a segmentation unit configured to perform region segmentation on the plurality of block images by clustering of pixels contained in those block images based on the plurality of representative points, wherein the segmentation unit performs the clustering of pixels in a target block image of the region segmentation by referring to a representative point in the target block image, a representative point of a processed block image on which the region segmentation has been performed and which is adjacent to the target block image, and a representative point of an unprocessed block image on which the region segmentation has not been performed yet and which is adjacent to the target block image. ### Claim 32 (depends on 31) The apparatus according to claim 31, further comprising: a first buffer having a memory amount capable of holding at least one block image; and a second buffer configured to hold the representative points to be referred to in the region segmentation, wherein the segmentation unit performs the clustering for the target block image held in the first buffer based on information of the representative points held in the second buffer. ### Claim 33 A non-transitory computer readable medium storing a computer-executable program for causing a computer to perform an image processing method, the method comprising steps of: setting a plurality of representative points and a plurality of block images in an input image; and performing region segmentation on the plurality of block images by clustering of pixels contained in those block images based on the plurality of representative points, wherein the clustering of pixels in a target block image of the region segmentation is performed by referring to information of a representative point in the target block image, a representative point in a processed block image on which the region segmentation has been performed and which is adjacent to the target block image, and a representative point in an unprocessed block image on which the region segmentation has not been performed yet and which is adjacent to the target block image.