JPH07160879A - Image processing method - Google Patents

Abstract

PURPOSE:To execute visually coincident area division of a picture into areas such as 'light, intermediate and shadow'. CONSTITUTION:A CPU notes one picture element 210 within picture data 21 and detects the picture element being adjacent to the picture element 210. The CPU successively integrates the picture element 211 where a contrast strength measure value in color space is min. (a similarity degree is max.) from the picture elements being adjacent to the data picture element 210 of a vertex and a side to the picture element 210. By considering the connecting property of a coordinate in color space with the area in the actual picture, area division coincident with a visual feature is made to be possible. Since it is sufficient that the judgment of area integration is executed only about an adjacent cluster, a processing time and memory capacitance can be reduced. A discontinuous part is not generated in the area-integrated cluster.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image processing method,
More specifically, the present invention relates to an image processing method for dividing image data into regions having certain characteristics.

[0002]

2. Description of the Related Art In the fields of printing, photography, painting, etc.,
In many cases, the lightness, hue, saturation, coordinates (position), etc. of the image are comprehensively grasped, and the image portion is often classified into "light, middle, shadow". For example, in the step of proofreading a photograph representing a person, “light, middle,
The concept of "shadow" is often used. The judgment of "light, middle, shadow" is left to the judgment of the operator only, and the worker decides the brightness of the image when making this judgment.
It is known to comprehensively consider hue, saturation, coordinates, etc.

In recent years, in the fields of printing and the like, since the image of an original document is often processed by a computer,
Similarly, it is preferable that the “light, intermediate, and shadow” can be automatically extracted by the computer. As a general method for extracting a certain area in an image, a method of dividing an image having a difference in density using a predetermined threshold value, and a method of dividing the area using a threshold value determined by a histogram such as density or chromaticity are used. It is conceivable to use a method of performing the above, a method of dividing the area by regarding the edge of the image as a boundary line of the area.

However, each of the above-mentioned conventional image processing methods divides the area by separately judging the lightness, hue, saturation, coordinates, etc. of the image, and these are comprehensively considered. It does not perform area division. Therefore, the area divided by the conventional image processing method is different from the area based on the concept of “light, intermediate, shadow”. That is,
Depending on the image processing method described above, it is not possible to perform area division that matches human recognition, such as "light, intermediate, and shadow."

If attention is paid to the fact that the division / classification of "light, intermediate, shadow" has a hierarchical structure, the hierarchical cluster analysis method is applied to the image so that each area of "light, intermediate, shadow" is divided. It is also possible to divide and classify. However, in this case, the following problems occur. In order to perform hierarchical clustering, it is necessary to calculate the distances in the color space for all pixel pairs and find the cluster pair with the minimum distance from them. Therefore, if the number of pixels increases, the number of cluster pairs to be calculated becomes enormous, and the processing time and the required memory capacity also become enormous. For example, in image data of 512 × 512 pixels, the total number of pixels n = 512 × 512 = 262
The number of pixel pair combinations in 144 is _n C ₂ = 3.4
It becomes 36 × 10 ⁶ . If you try to keep this number of data in memory at the same time, it will take about 200-400 GB
It requires as many as s large-capacity memory. In addition, since the number of pixel pairs for the number of pixels n is _{expressed by n} C ₂ = n (n + 1) / 2, the number of pixel pairs to be calculated should increase in proportion to the square of the number of pixels n. Can be confirmed. Therefore, such a method requires a huge amount of calculation time and memory capacity, and therefore cannot be applied to clustering for high-definition images, and it is not possible to divide each region of “light, intermediate, and shadow”. It is possible.

Therefore, no matter which of the conventional image processing methods is used, the image is "light, intermediate, shadow".
Could not be divided into each area.

[0007]

SUMMARY OF THE INVENTION Therefore, an object of the present invention is to provide an image processing method capable of dividing an image into "light, intermediate, and shadow" regions according to human recognition.

[0008]

According to a first aspect of the present invention, the similarity between two areas in image data to be compared is
Of the plurality of other areas adjacent to the one area in the image data, the other area having the maximum similarity with the one area is calculated based on the coordinates of the two areas in the color space. It is an image processing method characterized by sequentially integrating into the one area.

According to a second aspect of the present invention, the similarity between two areas in the image data to be compared is calculated based on the coordinates of the two areas in the color space, and one area in the image data is calculated. Among a plurality of other areas adjacent to the other area, another area having the highest similarity to the one area is sequentially integrated into the one area, and the order of area integration and the similarity between the area integrated areas Image processing characterized in that history data representing the above is generated, and in the image data area-integrated according to the history data, the area pair having a similarity in a predetermined range is sequentially divided in the reverse order of the area integration order. Is the way.

According to a third aspect of the present invention, the variance or the center of gravity of each region on the color space due to the integration of the two regions in the image data to which the similarity according to the first or second aspect is integrated. The image processing method is characterized by calculating based on

According to a fourth aspect of the present invention, each region forming the image data is regarded as a vertex, and the similarity between two adjacent vertices is calculated based on the coordinates of the two vertices in the color space, and calculated. The similarity is regarded as a side connecting the above two vertices, and among the plurality of sides connected to one vertex,
The image processing method is characterized in that the side having the maximum similarity is searched, and the process of integrating other vertices connected to the searched side into one vertex is repeated.

[0012]

According to the first aspect of the invention, the degree of similarity between two regions (clusters) in the image data that are compared with each other is calculated based on the coordinates of the two regions in the color space. That is, when the chromaticities of the two areas are similar,
The degree of similarity increases. Then, of the plurality of other areas adjacent to the one area in the image data, the other area having the highest similarity to the one area is sequentially integrated into the one area. As a result, the areas having similar chromaticity are integrated, and the contrast between the areas can be sufficiently increased.

According to the present invention, by considering the coordinates on the color space and the coordinates on the actual image, it is possible to integrate the areas comprehensively capturing the lightness / chromaticity. From the above, it is possible to perform the area extraction in which the image is comprehensively captured, such as “light, intermediate, and shadow”. Further, according to the present invention, since the similarity only has to be calculated for the adjacent region pairs, the memory capacity for holding the data of the similarity can be reduced, and the hierarchical clustering for the image can be performed in a short time. There is also an advantage that you can.

According to the second aspect of the present invention, the degree of similarity between two areas in the image data to be compared is calculated based on the coordinates of the two areas in the color space. Then, of the plurality of other areas adjacent to the one area in the image data, the other area having the maximum similarity to the one area is sequentially integrated into the one area. At this time, history data representing the order of region integration and the degree of similarity between the regions integrated is generated. Then, among the image data obtained by the region integration, the region pairs having the similarities in the predetermined range are sequentially divided in the reverse order of the region integration order according to the history data. That is, the region-integrated image data is divided again for each region having similar features. Therefore, according to the present invention, a desired area can be extracted from the image data.

In the invention of claim 3, claim 1
Alternatively, the similarity according to claim 2 is calculated based on the variance of each area or the change of the center of gravity in the color space when the two areas to be compared in the image data are integrated. For example, when two areas are separated in the color space due to different chromaticity, the dispersion is increased by integrating these two areas. On the other hand, when the two regions are close to each other in the color space due to the similar chromaticity, the variance does not change so much even if these two regions are integrated. Also, if two areas that are far apart in the color space are integrated,
The center of gravity position before and after the integration changes greatly. On the other hand, when the two regions having a short distance are integrated, there is little variation in the position of the center of gravity before and after integration. Therefore, it is possible to calculate the similarity based on the variance or the change in the center of gravity.

In the invention described in claim 4, first, each area forming the image data is regarded as a vertex. Next, the similarity between two adjacent vertices is calculated based on the coordinates of the two vertices in the color space, and the calculated similarity is regarded as the side connecting the two vertices. That is, each area and the degree of similarity are represented by a graph structure using vertices and edges. Then, from among the plurality of sides connected to one vertex, the side having the highest degree of similarity is searched, and the process of integrating other vertices connected to the searched side into the one vertex is repeated. . By using the graph structure as described above, it becomes possible to perform region integration hierarchically.

[0017]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An image processing method according to an embodiment of the present invention will be described below.

FIG. 1 is a block diagram of an image processing apparatus capable of executing the image processing method according to this embodiment. This image processing apparatus includes a bus 10, a CPU 11, an input I / F 12, a program memory 13, a work memory 14, and an image memory 1.
5, an output I / F 16, an external storage device 17, a GDC (graphic display controller) 18, a display 19 and the like. The CPU 11 executes processing such as image area division according to a program written in the program memory 13. Input I /
F12 is an interface for inputting image data to be processed. The image data represents a natural image,
For example, RGB of 512 × 512 pixels (or CMYK,
CIE LAB) color data. The program memory 13 is for storing program data representing the processing procedure of the CPU 11 described above.

The work memory 14 stores data (tree data, which will be described later) calculated by the CPU 11 in accordance with the area division processing.
List data etc.) is to be temporarily stored. The image memory 15 is for storing the image data input from the input I / F 12. Output I / F 16
Is a digital interface for outputting area-divided image data and the like to an external device (printer or the like). The external storage device 17 includes a hard disk unit, a magneto-optical disk unit, etc.
It is a large-capacity storage device that stores image data, tree data, list data, program data, and the like that have been area-divided. The GDC 18 generates display data based on the image data and the image data after the area division. The display 19 is for displaying an image based on this display data.

Before describing the details of the image processing method according to this embodiment, an outline of hierarchical clustering will be first described. Hierarchical clustering is a region (cluster) in which features such as hue, brightness, and saturation are similar (large similarity).
The regions of the image are divided by sequentially integrating them. According to this image processing device, it is possible to divide a given image into areas of a person and a background.

For example, assume that image data representing an object and a background is given to the image processing apparatus. The image processing device is n
The coordinate point on the color space of each pixel in the image data of the pixel is set as the initial cluster. The n clusters in the color space are
Two clustered distributions are formed corresponding to the pixel representing the background and the pixel representing the person. The image processing apparatus focuses on one cluster among the n initial clusters and searches for a cluster having a chromaticity close to this cluster in the color space. That is, the image processing apparatus calculates the chromaticity and the like of one cluster and all the other clusters by using the coordinates on the color space, and finds another cluster having an approximate chromaticity.

The cluster pair thus detected is
The hue, lightness, saturation, and the like in the actual image are similar to each other. The number of clusters becomes n-1 by the image processing apparatus integrating the cluster pairs. When this process is repeatedly executed and clusters are sequentially integrated, the number of clusters finally becomes one. Here, it is assumed that the image processing apparatus stops the area integration when the number of clusters reaches two in the area integration process and classifies each pixel into two clusters. Of the two clusters thus obtained, the pixels forming the same cluster have similar chromaticities, but the pixels between different clusters have significantly different chromaticities. That is, the image data is divided into two groups having different characteristics. With the above processing, the image can be divided into two areas, the background and the person.

FIG. 2 is a conceptual diagram of image data and area integration processing. Reference numeral 21 in FIG. 2 indicates a part (9 pixels) of the image data input from the input I / F 12. FIG. 3 is a diagram showing image data in the L ^* a ^* b ^* color space. In the image processing apparatus, for example, the pixel (cluster) 210 and which pixel to integrate are determined as follows.

First, the image processing apparatus searches for a pixel (4 neighborhoods or 8 neighborhoods) adjacent to the pixel 210. Pixel 21
Only pixels adjacent to 0 can be integrated with pixel 210. Then, the image processing apparatus searches for a pixel having a minimum contrast strength scale value (having a maximum degree of similarity) among pixels adjacent to the pixel 210. The contrast intensity scale value represents the change in the variance value of the cluster when the regions are integrated in the L ^* a ^* b ^* color space (FIG. 3) as described later. The L ^* a ^* b ^* color space is a uniform color space, and the distance in this space is approximately proportional to the difference in visual chromaticity. That is, the fact that the contrast intensity scale value in the L ^* a ^* b ^* color space is small means that the chromaticity and the like of the cluster pairs are similar (the similarity is large), and the contrast intensity scale value is large. This means that the chromaticity and the like of the pair of areas are different (the degree of similarity is small).

For example, pixel 2 in the L ^* a ^* b ^* color space.
If the contrast intensity scale value of 10 and the pixel 211 is the minimum, the image processing apparatus performs the region integration of the pixel 210 and the pixel 211. By repeating such processing,
Among adjacent pixel (cluster) pairs, those having similar chromaticities are sequentially integrated, and finally 9 pixels are combined into one cluster (region).

In order to efficiently perform the above-mentioned hierarchical clustering processing, this embodiment carries out data processing by a so-called graph structure. That is, the pixels (clusters) forming the image data are regarded as vertices, the contrast intensity scale value between the pixels (clusters) in the L ^* a ^* b ^* color space is regarded as an edge, and the similarity between each region and each region, etc. Is treated as a graph. If the whole of these vertices and edges is grasped as a graph, the process of hierarchical clustering constitutes a so-called tree. less than,
Various data structures in the image processing apparatus will be described with reference to FIGS.

FIG. 5 shows vertex data 50 and edge data 51. The vertex data 50 represents cluster information, and is composed of the following data. In the figure, the label 501 may be a unique symbol in the graph, but in this embodiment, it represents the coordinates (x, y) on the real image of the cluster that is the vertex. For example, 32
If the upper 16 bits of the bit data are the y coordinate value and the lower 16 bits are the x coordinate value, the label 501 is y ×.
It is expressed as 65536 + x. Also, the width of the image is w
Then, the label 501 can be expressed as x + y × w. The L ^* average value 502, a ^* average value 503, b ^* average value 504 are the L ^* a ^* b values for each pixel in the cluster.
^{* It} represents the average value of each coordinate in the color space.
The number of samples 505 represents the total number of pixels forming a cluster. The pointer 506 to the list represents the address of the list data 60 on the work memory 14. The list data 60 is composed of edge data pointers, which will be described later (FIG. 6).
The binary tree pointer 507 represents the node of the binary tree representing the vertex before integration. That is, the binary tree data represents the cluster integration history as tree-structured data.

The edge data 51 is structured as follows. The contrast intensity scale value 511 represents the variance change in the L ^* a ^* b ^* color space between the vertices (clusters) at both ends of the side. That is, the contrast intensity scale value 511 represents a change in the variance value of the clusters in the L ^* a ^* b ^* color space before and after the integration, assuming that the two clusters to be compared are integrated. Therefore, a small contrast strength scale value means a small change in the variance value when two clusters are integrated, that is,
This means that the chromaticities of the two clusters are similar (the degree of similarity is large). On the contrary, a large contrast strength scale value means a large change in the variance value when the two clusters are integrated, that is, the chromaticity of the two clusters is different (the similarity is small). ) Is meant. When calculating the contrast strength scale value according to the lower expression of FIG. 3, each component of L ^* a ^* b ^* may be weighted.

The pointers 512 and 513 to the vertex data in the side data 51 indicate the addresses of the vertex data at both ends of the side. Therefore, by referring to the side data 51, it is possible to easily determine the connection relationship of the clusters and the similarity between the clusters.

FIG. 6 shows the relationship between the list data 60, the vertex data 50, and the side data 51. The apex data 50 and the side data 51 in this figure are as described above. The list data 60 is composed of a pointer 601 indicating the address of the side data 51. Therefore, by referring to the list data 60,
This makes it possible to grasp the connection relationship between edges and vertices. In addition, the pointer 512 in the side data 51,
By referring to 513, it is possible to find the data 50 of the two vertices at both ends of the side.
The list data 60 can be found by referring to the pointer 506 to the inside list.

FIG. 7 shows the vertex data 50 and the tree-structured node data 70. The node data 70 includes information for integrating two vertices (clusters) and constitutes a part of binary tree data. The label 701 is the label of the vertex after integration, and in this embodiment, it is one of the labels of the two vertices before integration.
L ^* average value 702, a ^* average value 703, b ^* average value 704
Is the average value of each color component after integrating the two clusters. That is, L ^* average value 702, a ^* average value 703, and b ^* average value 704 are weighted averages of the values of the respective color components according to the total number of pixels of each cluster. Contrast strength scale value 7
Reference numeral 05 shows a change in the dispersion value in the L ^* a ^* b ^* color space when the two clusters are integrated as described above.

Pointers 706 and 707 to subtrees
Indicates the integrated node data 70. By tracing the node data 70 having a hierarchical structure in this manner, the process of region integration can be grasped.

FIG. 8 is a diagram showing a B-tree. The B-tree 80 is used to search the data of the side having the minimum contrast strength scale from the lists 81 to 86, ... Using the contrast strength scale value as a key (search item). That is, by referring to the B-tree 80, the edge having the most similar chromaticity is searched for with extremely few memory accesses among the edges connecting a certain vertex (cluster) and another vertex adjacent to this vertex. It is possible. In this figure, lists 81-
A pointer indicating the address of the side data 51 is written in 86, ..., And the side data 51 indicated by the pointers in the same list have the same contrast strength scale value. These pointers are arranged corresponding to the ascending order of the contrast strength scale value 511 in the side data 51. Therefore, by examining the pointer registered in the highest list 81 and finding the side data 51 indicated by this pointer, the side data 51 having the smallest contrast strength scale value can be searched. When there are a plurality of sides having the same contrast strength scale value, a plurality of pointers are registered in the same list.

The root node of B-tree 80 has four keys 81.
1 to 814, and 5 before and after each key
There are one pointer 821 to 825, each pointer points to one node, and each key points to one list. These have a hierarchical structure as a whole. The five root pointers 821 to 825 are respectively keys 811.
Data is divided into smaller keys, keys larger than key 811 and smaller than key 812, keys larger than key 812 and smaller than key 812, keys larger than key 812 and smaller than key 813, ..., Keys larger than key 814. Data is further divided and assigned to each node that is assigned to each node and connected to each of these pointers. Therefore, for each layer, the top node 801,
By tracing 802 and 803, a list 81 of pointers to the side data indicating the minimum contrast strength scale value
Is what you can search for. In addition, B-tree 80
Has the advantage that the lists 81, ... Can be easily added and deleted. Further, when a plurality of contrast strength scale values are registered in the same list, even if one of them is deleted, the key will not be deleted until the list becomes empty. That is, since the B-tree 80 always maintains the equilibrium state, high-speed search is possible.

Next, the hierarchical clustering processing in the image processing apparatus according to this embodiment, that is, the operation of integrating each cluster into one cluster will be described. Figure 4
3 is a flowchart showing a region integration process of the image processing apparatus according to the present embodiment. First, the CPU 11 uses the input I / F
Image data is input via 12 and is stored in the image memory 1
Store in 5. Here, the image data 2 shown in FIG.
It is assumed that 1 is input. Although the actual image data has a far larger number of pixels than this, the description will be given here by taking the image data 21 of 3 × 3 pixels as an example.

In step S41, the CPU 11 calculates the vertex data 50, the edge data 51, and the node data 70 based on the image data 21 to generate a so-called lattice graph (step S41). A detailed description of the process of step S41 is made in step S4.
11, the subroutine of S412.

In step S411, the CPU 11 calculates the vertex data for each pixel of the image data 21. The vertex data 50 is the label 50 as described above.
1, the average value 502 of each color component in the L ^* a ^* b ^* color space
~ 504, number of samples 505, pointer to list 50
6, a pointer 507 to a binary tree. It should be noted that at this point in time, since area integration has not been performed, the label 501 has a coordinate value on the image data of each pixel, and the number of samples 505 is “1”. Further, the average values 502 to 504 of the respective color components become coordinate values on the L ^* a ^* b ^* color space for each pixel.

Further, the CPU 11 registers the node data 70 of the binary tree for each pixel. At this time, since region integration is not performed, so-called subtree does not exist, and therefore pointers 706 and 707 to the subtree are blank (zero). Further, the contrast strength scale value 705 indicating the change of the variance of the cluster is also blank (zero).

In step S412, the CPU 11 calculates the side data 51 according to the following procedure. First, the CPU
The pixel 11 focuses on the pixel 210 in the image data 21, and is adjacent to the pixel 210 (for example, 4 neighborhoods).
A contrast intensity scale value in the L ^* a ^* b ^* color space between the pixels 211 to 214 is obtained. That is, the CPU 11 causes L ^* a ^* in the vertex data 50 calculated in step S411 ^.
Based on the respective color components 502-504 of b ^* , the respective color components 50 between the pixels of the pixel 210 and the pixels 211-214
Examine the variance change from 2-504. These changes in variance are registered in the edge data 51 as the contrast strength scale value 511. In addition, the pointer 51 of the side data 51
In 2, 513, the addresses of the vertex data 50 at both ends of the side are written. In this way, the data 51 on the four sides centering on the pixel 210 is generated.

The CPU 11 registers the edge data 51 thus generated in the B-tree 80 of FIG. 8 as keys and pointers to the edge data. That is, the CPU 11 registers the pointers of the side data 51 in ascending order of the contrast strength scale value, and the list 81, ... Is completed. Through the processing in steps S411 and S412 described above, the initial lattice graph composed of the vertex and edge data is completed (step S
41).

Subsequently, the CPU 11 executes the judgment of step S42. At this time, since the region integration is not performed, the number of pixels becomes the total number of clusters as it is. Therefore, the determination result of step S42 is NO, and the next step S43 is executed. In step S43, C
The PU 11 refers to the B-tree 80 and searches the list 81, ... For the data 51 of the side having the minimum contrast strength scale value. When the search is finished, the CPU 11 deletes the list 81 from the entire list in advance or afterwards.

Side data 5 having the smallest contrast strength scale value 5
When 1 is retrieved, the CPU 11 integrates the vertices at both ends of the data 51 on this side. For example, if the contrast intensity scale value of the pixel 210 and the pixel 211 is the minimum, the pixel 210 and the pixel 211 are integrated. Accordingly, the CPU 11 causes the vertex data 50, the edge data 51,
The binary tree data 70 and the like are updated (step S44).

The updating process of the vertex data 50 will be described below. The CPU 11 reads the data 50 of the two vertices corresponding to the pixels 210 and 211 integrated in step S43, and integrates the data 50 of one of the vertices with the data 50 of the other vertex. For example, assume that the vertex data 50 relating to the pixel 210 is integrated with the vertex data relating to the pixel 211. Two pixels 210, 21
As a result of 1 being integrated into one cluster, the average value of each color component in the L ^* a ^* b ^* color space of the cluster after integration is 50.
2-504 varies. Therefore, the CPU 11 determines the average value 502 to 50 of each color component in the integrated cluster.
4 is registered in the vertex data 50 relating to the pixel 210.

The pointer 507 to the binary tree in the vertex data 50 is updated as follows. First, the CPU 11
Generates new node data 70, sets the pointer 507 in the vertex data 50 relating to the pixel 210 to the pointer 706 of the new node data 70, and sets the pointer 507 in the vertex data relating to the pixel 211 to the new node data 70. Are registered in the pointers 707 of. Also, the CPU 11
Represents the label 501 of the pixel 210 as the label 701 of the new node data 70 and the average value of the color components 502 to 504 of the pixels 210 and 211 as the new node data 70.
The contrast strength scale value 511 in the data 51 of the side connecting the pixels 210 and 211 is registered in the contrast strength scale value 705 of the new node data 70 in the color components 702 to 704 of FIG.

The updating process of the edge data 51 will be described below. First, the data of the sides relating to the vertices 210 and 211 are deleted from the lists 60 of both the pixels 210 and 211. When the two vertices are integrated, the information held by each vertex may be duplicated. Therefore, the list data 60,
B-Delete duplicated data in tree 80. Pixel 21
In the first stage of region integration in which 0 and 211 are integrated, there is no side where the pixels 210 and 211 are overlapped and connected, and therefore such processing is not necessary. The dissimilarity update for the newly integrated area is performed for all areas adjacent to it.

As described above, the pixels 210 and 211 are integrated into one vertex (cluster) 216. After this, the CPU
11 returns to step S42 and repeats the processing of S42 to S44. In this way, it is assumed that clusters P, Q, and R each having a plurality of pixels are generated at the stage of region integration of the image data 21 as shown in FIG. 3, for example. The processing for these clusters P, Q, and R will be described below.

In step S43, the CPU 11 sets B
-Refer to the tree 80, and search the list 81, ... For the data 51 of the side having the minimum contrast strength scale value. When the search is completed, the CPU 11 deletes the other registered search from the list, and if the list is empty, deletes the key from the B-tree. When the side data 51 having the smallest contrast strength scale value is searched, the CPU 11 integrates the vertices at both ends of the side data 51. For example, if the contrast strength scale value of the cluster P and the cluster Q is the minimum, the cluster P and the cluster Q are integrated. Along with this, the CPU 11 updates the vertex data 50, the edge data 51, the binary tree data 70, etc. (step S4).
4).

The process of updating the vertex data 50 will be described below. The CPU 11 reads the data 50 of two vertices corresponding to each of the clusters P and Q integrated in step S43, and the data 50 of one of the vertices is read.
Is integrated with the data 50 of the other vertex. For example, assume that the vertex data 50 related to the cluster P is integrated with the vertex data related to the cluster Q. As a result of the integration of the two clusters P and Q into one cluster, L ^{* of the} integrated cluster
Average value 502 to 50 of each color component in the a ^* b ^* color space
4 varies. Therefore, the CPU 11 registers the average values 502-504 of each color component in the integrated cluster in the vertex data 50 related to the cluster Q.

The pointer 507 to the binary tree in the vertex data 50 is updated as follows. First, the CPU 11
Generates new node data 70, sets the pointer 507 in the vertex data 50 related to the cluster P to the pointer 706 of the new node data 70, and sets the pointer 507 in the vertex data related to the cluster Q to the new node data 70. Are registered in the pointers 707 of. Also, the CPU 11
Represents the label 501 of the cluster P as the label 701 of the new node data 70, the average value of the color components 502 to 504 of the clusters P and Q as the color components 702 to 704 of the new node data 70, and the cluster P, The contrast strength scale value 511 in the side data 51 connecting Q is registered in the contrast strength scale value 705 of the new node data 70, respectively.

The updating process of the edge data 51 will be described below with reference to FIG. First, the CPU 11 causes the vertex P,
The pointer 601 indicating the side PQ connecting Q is set to the list data 6
Delete from 0. When there is a vertex R in which the vertices P and Q are connected together, the CPU 11 deletes the pointer 601 of the side QRR or the side RP from the list data 60 regarding the vertices P and Q, and the side QR or the side QR from the B-tree 80. RP
Delete data about. Further, the CPU 11 merges the side pointer 601 connected to the vertex P with that of the vertex Q. By the above process, the duplicated data is deleted, and the update process for the edge data 51 is completed.

Further, the contrast strength scale value 511 in the data 51 of the side with the other vertex T connected to the origins P and Q is
Update processing is performed based on the average value of L ^* a ^* b ^* of P and T after integration and the number of constituent pixels (equation in the middle part of FIG. 3). This processing is similar to that in the above-described updating processing of the vertex data 50. When updating the new contrast strength scale value 511 after integration, the edge data to be updated is deleted from the temporary B-tree and the contrast strength scale value 511 is updated.
U11 re-registers the pointer to the data 51 in the B-tree 80 using the new contrast strength scale value 511 as a key.

With the above, the process of step S44 ends. After that, the CPU 11 returns to step S42 and repeats the processing of steps S42 to S44 until the total number of clusters of the image data 21 becomes "1". When the total number of clusters becomes "1", the area integration processing ends. As a result, the image data 21 is integrated into one vertex (cluster) 250.

Although the above-described area integration processing is to integrate one cluster into another cluster in sequence, it is also possible to perform area integration in parallel in local areas of image data. Such parallel processing is particularly effective in the initial integration process.

When the area integration by the process shown in the flowchart of FIG. 4 is completed, the CPU 11 writes the binary tree node data 70 representing the integration history from the work memory 14 to the external storage device 17. Since the number of node data 70 forming the binary tree is approximately twice the total number of pixels of the image data, the number of binary tree data is enormous. Therefore, if all the binary tree searches of the binary tree data arranged on the work memory 14 are performed, the memory access becomes enormous. Therefore, in this embodiment, for each node data 70 forming a binary tree, this is written to the external storage device 17 in the order of the binary tree search, and at the time of reading, the external storage device 1 for each node data 70 is in the reverse order.
7 to the work memory 14. This makes it possible to significantly reduce the memory access to the work memory for relocation of the binary tree. Below, processing at the time of writing and reading from the root node to the external storage device 17 will be explained based on FIG. 7.

At the time of writing, the following processing is recursively executed starting from the root node or a predetermined node. First, the label 7 in the node data 70 that is the starting point
01, L ^* a ^* b ^* average values 702 to 704, and contrast strength scale value 705 are written in the external storage device 17. Then C
The PU 11 refers to the pointer 706 to this node data 70 subtree, and if the pointer 706 to the subtree is not blank, writes the next node data 70 indicated by the subtree 706 to the external storage device 17. Pointer 706
Is blank, the fact that the node data 70 in which the pointer 706 is written is “leaf” is written in the external storage device 17 and the process returns to the parent node one level higher, and the pointer 70
Similar processing is performed for 7. By repeating the above processing, the node data 70 is written in the external storage device 17 in the order of the binary tree search.

In the above writing process, the node data 70 to be the “leaf” of the binary tree is discriminated based on whether or not the pointers 706 and 707 to the subtree are blank, but whether the contrast strength scale value 705 is blank or not. It may be done depending on whether or not. Further, it may be determined that the node data 70 is a “leaf” when the number of samples 505 in the vertex data 50 corresponding to the node data 70 becomes “1”.

Next, the process of reading the node data 70 will be described. First, the CPU 11 secures an area of the node data 70 on the work memory 14, and transfers each data in the node data 70 which is the starting point read from the external storage device 17 to the area. Next, the node data read from the work memory 14 is assumed to be the one pointed by the pointer 706 of this node data 70, and the new node data 7
0 is secured and the data from the work memory 14 is read there. At this time, if the read data is not a “leaf”, the same processing is repeated for the pointer 706 of the node data 70. If it is a “leaf”, the pointers 706 and 707 of the node data 70 are left blank and the node returns to the node one level higher, and the pointer 707 of the node is pointed to to secure new node data 70, and Read the data from the memory 14,
The process is continued for the work memory 706 of this node data 70.

Next, the area extraction processing based on this binary tree will be described. By the area integration processing described above, the image data is finally integrated into one cluster (vertex) 250 as shown in FIG. By reversing the process of region integration, it is possible to obtain image data 22 obtained by dividing the image data 21 as shown in FIG. That is, image data representing a background, a person, etc. can be divided into a background image area, a person's image area, etc., and a desired image area can be extracted.

By tracing the binary tree (history data) from the root node toward the "leaf", one cluster can be sequentially divided into two clusters. To what depth can the binary tree be divided? Whether to follow is determined in advance by the following procedure. First, the operator gives the image processing apparatus a lower limit of the contrast strength scale value (similarity range) as a condition for ending the division. That is, in the process of dividing one cluster according to the binary tree, if the chromaticity of each cluster approximates to some extent, the dividing process is stopped. As a result, the image can be divided into areas having completely different characteristics.

When the lower limit value of the contrast strength scale value is given to the image processing apparatus, the CPU 11 causes the root node data 70
It is determined whether the contrast strength scale value 705 therein is smaller than the instructed lower limit value. At this time, the contrast strength scale value 705
Is smaller than the lower limit value (similarity is greater than or equal to a predetermined value), the processing ends. On the other hand, when the contrast strength scale value 705 is larger than the lower limit value (the similarity is equal to or less than the predetermined value), the CPU 1
1 refers to pointers 706 and 707 in the node data 70. If the pointers 706 and 707 are blank (no subtree exists), the CPU 11
Ends the process. If the pointers 706 and 707 are not blank, the node data 70 of the subtree indicated by the pointers 706 and 707 is referred to. If the contrast strength scale value 705 of this subtree is smaller than the lower limit value, the processing ends. By repeating these processes, the binary tree is limited (the branch of the binary tree is cut in the middle). The clusters represented by the “leaves” of the binary tree defined in this way have different characteristics to some extent.

As shown in FIG. 2B, node 2
A binary tree having 50 as a root extends toward each pixel of the image data 21, but a binary tree having four clusters as “leafs” can be obtained by cutting this binary tree in the middle. .

The area designation data indicating the divided area is generated by using each leaf of the binary tree thus limited as the root node of the subtrees below it. The area designation data is two-dimensional data having coordinate values corresponding to the image data 21. First, the CPU 11 refers to the pointers 706 and 707 of the root node. Pointer 7
If 06 and 707 are blank, the CPU 11 calculates the x and y coordinates in the real image from the label 701, and the label 7 is added to the coordinates of the area designation data corresponding to these x and y coordinates.
Write 01. If the pointers 706 and 707 are not blank, the node tree 70 of the subtree indicated by the pointers 706 and 707 is referred to, and the same processing as above is repeated. By such processing, the label 701 is attached to each of the divided areas. In addition, it is possible to extract a desired area from the image data 21 based on the label 701 attached to each area. For example, it is possible to extract only an area representing a person from image data representing a person and a background.

An example of an image divided into areas by the image processing apparatus of this embodiment is shown in FIGS. 9 and 10. FIG. 9 shows an original image. FIG. 10 shows data obtained by dividing this image into regions. By performing the hierarchical clustering of the original image of FIG. 9, the clusters are sequentially integrated as shown in (A), (B), and (C) of FIG. FIG. 11 is a tree showing the process of region integration of the original image of FIG. The horizontal axis of this tree is the logarithm of the dissimilarity of region integration. Further, images at respective stages of arrows (A), (B), and (C) attached to FIG. 11 correspond to (A), (B), and (C) of FIG. 10, respectively. Figure 1
3, FIG. 14 and FIG. 15 are respectively shown in FIG.
It is a graph corresponding to (B) and (C) and showing the vertices and edges at each stage of region integration. 13 is a graph at the stage indicated by the arrow (A) in FIG. 14, and FIG. 14 is a graph at the stage indicated by the arrow (B) in FIG. Further, FIG. 15 shows a graph at the stage indicated by the arrow (C) in FIG. FIG. 12 shows images 121-126 at each stage of region integration of the original image 121 (identical to that shown in FIG. 9). The images 123, 124, and 125 of this figure are (A) of FIG.
It corresponds to (B) and (C).

As described above, according to this embodiment, among the adjacent cluster pairs, those having the smallest contrast strength scale value in the color space (having the highest similarity) are integrated. Hierarchical clustering is performed. Therefore, since it is only necessary to determine the area integration for adjacent clusters, it is possible to significantly reduce the processing time and the memory capacity required for the processing.

Further, since the clusters having the smallest variance change in the L ^* a ^* b ^* color space are integrated, it is possible to perform area segmentation that matches the visual characteristic of capturing a global contrast relationship. . For example, in the fields of photography, video, printing, etc., gradation may be subjectively classified as "light, intermediate, shadow". According to the present embodiment, since the L ^* a ^* b ^* color space that matches the visual characteristics is used for the region division, subjective image division such as "light, intermediate, shadow" is possible. It is a thing.

In addition to the L ^* a ^* b ^* color space, it is also possible to use a color space such as the U ^* V ^* W color space or the L ^* u ^* v color space. By weighting each component in the color space and calculating the contrast intensity scale value, it is possible to appropriately select which of the lightness, the hue, and the saturation is to be subjected to the region division. Further, in the present embodiment, the area integration is performed on the pixels in the four neighborhoods, but the area integration may be performed on the pixels in the eight neighborhoods.

[0067]

As described above, according to the present invention, hierarchical clustering is performed in consideration of the coordinates on the color space and the coordinates on the actual image. Therefore, it is possible to comprehensively capture the brightness, hue, saturation, etc. of the image,
Image "light, middle, shadow" according to visual characteristics
Can be divided into areas.

Further, among the adjacent cluster pairs, those having the smallest contrast strength scale value (maximum similarity) in the color space are integrated, thereby limiting the cluster pairs to be subjected to the area integration determination. It is possible to reduce the processing time for cluster division and the load on the image processing apparatus. Further, since adjacent pixel pairs are integrated on the actual image, no discontinuous portion is generated in the integrated area.

[Brief description of drawings]

FIG. 1 is a block diagram of an image processing apparatus according to an embodiment of the present invention.

FIG. 2 is a diagram showing image data, graph structure data, and the like according to an embodiment of the present invention.

FIG. 3 is a diagram illustrating a calculation formula of a contrast intensity scale value and an L ^* a ^* b ^* color space color space according to an embodiment of the present invention.

FIG. 4 is a flowchart showing a region integration process of the image processing apparatus according to the embodiment of the present invention.

FIG. 5 is a diagram showing vertex data and edge data according to an embodiment of the present invention.

FIG. 6 is a diagram showing vertex data, edge data, and list data according to an embodiment of the present invention.

FIG. 7 is a diagram showing vertex data and node data according to an embodiment of the present invention.

FIG. 8 is a diagram showing a B-tree or the like according to an embodiment of the present invention.

FIG. 9 is a diagram showing image data according to an embodiment of the present invention.

FIG. 10 is a diagram showing region-divided image data according to an embodiment of the present invention.

FIG. 11 is a tree showing region integration according to an embodiment of the present invention.

FIG. 12 is a diagram showing region-divided image data according to an embodiment of the present invention.

FIG. 13 is a graph showing vertices and edges in a region integration process according to an embodiment of the present invention.

FIG. 14 is a graph showing vertices and edges in a region integration process according to an embodiment of the present invention.

FIG. 15 is a graph showing vertices and edges in a region integration process according to an embodiment of the present invention.

[Explanation of symbols]

 11 CPU 70 node data (historical data) 511, 705 contrast strength scale value (similarity)

Claims (4)

[Claims] 1. A similarity between two regions in image data to be compared is calculated based on the coordinates of the two regions in a color space, and a plurality of other regions adjacent to one region in the image data are calculated. An image processing method, characterized in that, of regions, other regions having a maximum degree of similarity to the one region are sequentially integrated into the one region. 2. A similarity between two areas to be compared in image data is calculated based on coordinates of the two areas in a color space, and a plurality of other areas adjacent to one area in the image data are calculated. Of the regions, other regions having the highest similarity to the one region are sequentially integrated into the one region, and history data indicating the order of region integration and the similarity between the region integrated regions is generated. An image processing method, characterized in that, of the image data that has been area-integrated according to the history data, an area pair having a similarity within a predetermined range is sequentially divided in the reverse order of the area integration order. 3. The calculation of the similarity according to claim 1 or 2 based on the variance of each area or the change of the center of gravity in the color space due to the integration of two areas to be compared in the image data. Characterized image processing method. 4. Each area constituting the image data is regarded as a vertex, the similarity between two adjacent vertices is calculated based on the coordinates of the two vertices in a color space, and the calculated similarity is calculated based on the above two values. The vertices are regarded as connecting edges, and the edge with the highest degree of similarity is searched from among the multiple edges connected to one vertex, and the other vertices connected to the searched edges are searched for. An image processing method, characterized in that the process of integrating into the image is repeated.