CN104331883B - A kind of image boundary extraction method based on asymmetric inversed placement model - Google Patents

Abstract

The invention discloses a kind of image boundary extraction method based on asymmetric inversed placement model, the extracting method first has to carry out NAM expressions to bianry image, obtains total subpattern number and coordinates table.Then since the subpattern of first, the upper left corner, the sequential scan of raster scanning is pressed successively, often scan to a subpattern and just obtain related parameter values, if the region and current subpattern belonging to neighbor pixel are not belonging to same region and can merge, band is then performed by order merging and the Union-find Sets algorithm combined region of path compression strategy, next neighbor pixel is otherwise continued to scan on.When the left margin of this block and the neighbor pixel of coboundary are all scanned, this block is disposed, and updates boundary information, and next subpattern is processed by above step, is completed until all subpatterns are processed, and finally exports the boundary information of bianry image.The present invention has the advantages of occupancy memory space is small, and image boundary extraction speed is fast.

Description

A Method of Image Boundary Extraction Based on Asymmetric Inverse Layout Model

technical field

The invention relates to a computer image processing technology, in particular to an image boundary extraction method based on an asymmetric inverse layout model (NAM).

Background technique

The image boundary extraction technology is closely related to the image representation method. Here we mainly introduce the related research status and the latest development trend at home and abroad on the layered data structure of the image and the image boundary extraction technology.

(1) Hierarchical data structure of images;

Image representation is one of the most active research fields at present, and it plays a key role in applications such as image compression, feature extraction, image retrieval, image denoising and image restoration, and image boundary extraction. An effective image representation algorithm can not only save storage space, but also help to improve the speed of image processing. At present, there are many binary image representation algorithms based on spatial data structure, such as: string representation algorithm, tree structure representation algorithm and code word set representation algorithm. As far as the binary image compression algorithm is concerned, although the compression performance of the compression standard JBIG is always better than any binary image representation algorithm based on the spatial data structure, but because the JBIG representation algorithm involves the entropy coding process, for many applications It is not possible to manipulate the compressed JBIG format. Hierarchical data structure is a very important region representation method in the fields of computer vision, robotics, computer graphics, image processing, pattern recognition, etc. Quad Tree (QT, Quad Tree) is a form of image layered representation, which is the earliest and most researched layered representation. The early quadtree representations were pointer-based quadtree structures. In order to significantly reduce storage space, Gargantini et al. eliminated the pointer scheme and proposed a representation method called Linear Quad Tree (LQT, Linear Quad Tree). Subramanian et al. studied the image representation method based on binary space partitioning (BSP, Binary Space Partitioning). After the image is represented by the BSP tree, the representation result can directly support algorithms such as image compression and segmentation. Based on a hybrid binary tree and quadtree representation, Kassim et al. proposed a hierarchical segmentation based image representation. Based on the B-tree triangle encoding method, Distasi et al. proposed a grayscale image representation algorithm based on spatial data structure. Based on the S-tree data structure and the Gouraud shadow method, Chung et al. proposed a grayscale image representation (STC, S-TreeCoding) method based on the S-tree spatial data structure (K.L.Chung, J.G.Wu.Improved image compression using S-tree and shading approach. IEEE Transactions on Communications, 2000, 48(5):748-751.). Subsequently, Chung et al. proposed a hybrid gray image representation (SDCT, Spatial-and DCT-based) method based on DCT domain and spatial domain (K.L.Chung, Y.W.Liu, W.M.Yan.A hybrid gray image representation usingspatial-and DCT -based approach with application to moment computation. Journal of Visual Communication and Image Representation, 2006, 17(6):1209-1226).

Although the above-mentioned hierarchical data representations have many advantages, they place too much emphasis on the symmetry of the segmentation and thus are not optimal representations. With the help of the idea of the Packing problem, with the goal of finding an asymmetric segmentation method that maximizes the segmentation, Chen et al. proposed a NAM representation method for image patterns. Zheng Yunping and others proposed a NAM grayscale image representation method based on the extended Gouraud shading method and non-overlapping rectangular subpatterns, referred to as the RNAMC representation method (Zheng Yunping, Chen Chuanbo. A new grayscale image representation algorithm research. Computer Journal of the Chinese Academy of Sciences, 2010, 33(12):2397-2406.). Since the overlapping NAM representation method is generally more efficient than the non-overlapping NAM representation method, Zheng Yunping and others proposed a NAM grayscale image representation method based on the extended Gouraud shading method and overlapping rectangular sub-patterns, referred to as the ORNAM representation method (Yunping Zheng, Zhiwen Yu, Jane You, Mudar Sarem. A novel gray image representation using overlapping rectangular NAM and extended shading approach. Journal of Visual Communication and Image Representation, 2012, 23(7): 972-983.). The experimental results show that: compared with STC, SDCT and RNAMC representation methods, under the premise of maintaining image quality, ORNAM representation method has a higher compression ratio and fewer blocks, so it can reduce data storage space more effectively. A good way to represent grayscale images. Recently, Yunping Zheng proposed a new NAM representation method for binary images and applied it to area calculation, and achieved good results (Yunping Zheng, Mudar Sarem. A novel binary image representation algorithm by using NAM and coordinate encoding procedure and its application to area calculation. Frontiers of Computer Science, 2014, 8(5):763-772.). Judging from the current situation, LQT mainly focuses on reducing the complexity of image processing operations and expanding to a wider range. There are many theoretical achievements, and there are many practical applications, and more and more. It is still the current image processing technology. A very popular image representation method in the field.

The image representation method has two purposes: first, to improve the representation efficiency of the image. Second, improve the processing speed of image operations.

(2) Image boundary extraction technology;

Boundaries are usually the outlines of objects and provide crucial features for humans to describe or recognize objects and interpret images. Therefore, identifying and extracting the boundary in the image plays an important role in computer vision and digital image analysis and application, and also has important practical value. For many years, image boundary detection and extraction has been an important research topic in the field of digital image processing, analysis and application. Traditional boundary detection methods include derivative method, gradient method, Laplacian method and various improved methods. In recent years, multi-scale edge detection, edge detection based on mathematical morphology and image boundary detection technology using fuzzy logic have also been applied. In essence, the traditional boundary detection method is based on the method of pixel gray level change. Generally, the state of each pixel and its adjacent pixels is detected first to determine whether the pixel is on the boundary of the object, and then the boundary detection image is represented by the gray value of the pixel in the image or a binary gray image. The key of traditional boundary detection and extraction methods lies in the detection performance of boundary pixels and the performance of boundary point connection algorithm. In the boundary detection application of complex images, the effect is often not ideal. In recent years, the application of object-oriented image analysis methods has gradually attracted attention. The difference from the traditional pixel-based grayscale processing method is that the image is divided into several non-overlapping regions (image objects), and then the image object is used as the basic analysis and processing unit; this method, compared to the As a basic processing unit, pixels are more suitable for combining human cognitive knowledge about the real world, so that image regions that conform to real-world objects (ground objects) in shape and classification can be extracted more effectively from images. This object-based image analysis is a new theory emerging in recent years. By using the BSP method with hierarchical structure, Wang, C.C.L. et al. proposed an efficient BSP solid boundary extraction method based on the shear operation. Their polygonal algorithm iteratively performs the clipping operation on the soma corresponding to the convex partition of the space, computing boundaries by traversing the cell connections. They use point-based representation along with finite-precision operations to improve efficiency and generate BSP solid boundary approximations (Wang, C.C.L.; Manocha, D., Efficient Boundary Extraction of BSP Solids Based on Clipping Operations. IEEE Transactions on Visualization and Computer Graphics, 2013, 19 (1):16-29).

To sum up, although many researchers have devoted themselves to the research of image boundary extraction in recent years and proposed many new boundary extraction techniques, due to the difficulty of the problem itself, most of the current methods are aimed at a specific task. , there is not yet a general solution. An important reason for the difficulty of image boundary extraction is the complexity and diversity of images. Due to the complexity of the image, it is difficult for any existing single image boundary extraction algorithm to achieve satisfactory segmentation results for general images, so we continue to work on introducing new concepts, new theories, and new methods into images. In the field of boundary extraction, more attention is paid to the effective combination of multiple boundary extraction algorithms. Most of the methods proposed in recent years combine multiple algorithms. Compared with a single boundary extraction algorithm, the boundary extraction integration technology is more effective, and Robustness, stability, accuracy and adaptability are better.

An effective image representation method can not only save storage space, but also improve the speed of image processing. The NAM representation method of the image pattern is an inverse layout expression of the image pattern. In essence, the image pattern is represented as a set of predefined sub-patterns, and the sub-patterns can be stored. Therefore, this method also directly supports image boundary extraction. and other processing algorithms.

Contents of the invention

The purpose of the present invention is to address the problems existing in the existing image boundary extraction technology, and to provide an image boundary extraction method based on an asymmetric inverse layout model (NAM), which can significantly improve the representation and extraction efficiency of image boundary extraction . The boundary extraction algorithm based on NAM first needs to encode the image, and obtain the total sub-pattern number n and the coordinate table W after encoding. Then start from the first sub-pattern in the upper left corner, scan the sub-patterns in the order of raster scanning, and obtain the coordinate values of the four corners of this sub-pattern from the coordinate table every time a sub-pattern is scanned, and then scan the west of this sub-pattern All neighbor pixels at the border and the north border, if the region to which the neighbor pixel belongs and the current sub-pattern do not belong to the same region and can be merged, execute the union-find algorithm with a rank-based merge and path compression strategy to merge the regions, otherwise continue scanning next neighbor pixel. When the neighbor pixels of the left boundary and the upper boundary of this sub-mode are all scanned, the processing of this sub-mode is completed, the boundary information is updated, and the next sub-mode is processed according to the above steps, and the binary image can be extracted until all sub-modes are processed. boundary information.

The object of the present invention is achieved through the following technical solutions: an image boundary extraction method based on an asymmetric inverse layout model, comprising the following steps:

Step S1: Encode the image b with a size of G×H by using the binary image representation method based on the asymmetric inverse layout model, and obtain the encoded total number of sub-patterns n and the coordinate table W.

The specific expression method is as follows:

Step S1.1, assign all elements of the matrix variable M to 0, the size of M is equal to the binary image b to be processed, both are G×H, and the count variable n of the sub-pattern is set to be 0; among them, G and H are natural numbers;

Step S1.2. Determine the starting point (x ₁ , y ₁ ) of an unmarked rectangular sub-pattern in the binary image b in the order of raster scanning, determine a sub-pattern with the largest area according to the starting point, and set The sub-pattern is identified in the binary image b;

Step S1.3, recording the parameters of the sub-mode, namely: the coordinates of the upper left corner (x ₁ , y ₁ ), the coordinates of the lower right corner (x ₂ , y ₂ ); let n=n+1;

Step S1.4, cyclically execute steps (S1.2) to (S1.3), until all the sub-patterns in the binary image b are marked;

Step S1.5, according to the following coordinate data compression algorithm, encode the coordinates of all non-zero elements in the matrix variable M, and store the encoding result in a coordinate table W;

①Scan the matrix variable M whose size is G×H line by line. If all the elements of this line are zero, then there is no need to encode this line. In this case, use a binary bit "0" to indicate that the line is from the beginning to the end There are no non-zero elements, and the binary bit "0" is stored in the coding table W of the row; otherwise, if there are non-zero elements in the row, a prefix "1" is added before each non-zero element ", then add codewords for identifying non-zero elements 1, 2 and -1 after the prefix, and finally store the prefix "1" and subsequent codewords in the coding table W of the row;

② Use x bits to indicate the position of the column where the non-zero element is located, and store these x bits in the coding table W of the row, where the value of x is calculated according to the following two situations;

For the first non-zero element encountered in a row, x=[log ₂ H]; the x bits here are used to indicate the position of the first non-zero element with respect to the head end of the row;

For non-zero elements encountered in a row other than the first non-zero element, x = [log ₂ (Hc)], where c is the column position of the previously encountered non-zero element; here x Bits are used to indicate the position of the non-zero element on the right side of the non-zero element of the previous encoding;

③ After the last non-zero element of a row is encoded, use a binary bit "0" to indicate that the remaining elements of the row are all zero, and store this binary bit "0" in the coding table W of the row, Otherwise, if the position of the last non-zero element of the row is at the end of the row, then there is no need to use "0" to indicate that the remaining elements of the row are all zero;

Step S1.6, output the coordinate table W, wherein W is obtained by sequentially connecting the row coding tables of all rows of the matrix variable M.

Step S2, setting a serial number j of the current scanning sub-mode, and setting j=0, and setting a pointer matrix B with a size of G×H, which is used to indicate the area pointed to by each pixel.

Step S3, get W[j] in the coordinate table.

Step S4, according to W[j], calculate the size of the current sub-mode and the coordinate information of the left boundary and the upper boundary.

Step S5, start from the bottom of the left boundary, scan upwards, find a pixel LL on the left of each left boundary pixel L (that is, LL is 1 smaller than L in the X direction), and use matrix B to find pixels L and The area to which the pixel LL belongs, and then use the union search algorithm with rank-based merging and path compression strategies to find out the ancestor areas of these two areas. If the two areas are the same area, skip to the next pixel. Otherwise, if both If two regions do not belong to the same region, it is judged whether the two ancestors can be merged according to the mean and variance.

The 2 data structures used in this step and the next step are as follows:

①Region data structure domain:

{Mean, Var, Size, Father, Count, EdgeLink}

Among them, Mean indicates the gray level mean value of this area, Var indicates the gray level variance of this area, and Size indicates the size of this area, that is, the number of pixels. These three fields are used to support the merging operation of the area. The field Father is a pointer to point to the parent node of this area, Count is used for the number of descendant areas of this area, and the above two fields are used to support the union search algorithm. Field EdgeLink points to the boundary of this area, which can be used to track the boundary information of this area.

②Edge data structure domain:

{PreLink, First, Last, SucLink}

PreLink and SucLink are used to support doubly linked lists, and First and Last point to the start and end points of corner vertices.

Step S6, after scanning the left boundary, start from the leftmost side of the upper boundary, scan to the right, and find a pixel TT above it for each upper boundary pixel T (that is, TT is 1 smaller than T in the Y direction), and use the matrix B Find out the area to which pixel T and pixel TT belong, and then use the union search algorithm with rank-based merge and path compression strategy to find the ancestor area of these two areas. If the two areas are the same area, skip to the next one pixels; otherwise, if the two regions do not belong to the same region, judge whether the two ancestors can be merged according to the mean and variance.

Step S7, update boundary information, j++, jump to step S3, until all sub-patterns are processed.

Step S8, outputting the boundary information of the binary image b.

The principle of the present invention: the present invention provides an image boundary extraction method based on an asymmetric inverse layout model based on the layout problem and the idea of the quadtree region representation method of the binary image, based on the NAM representation of the binary image , the method can significantly improve the representation and operation efficiency of image boundary extraction. The image boundary extraction method based on the asymmetric inverse layout model first needs to perform NAM representation on the binary image to obtain the total number of sub-patterns n and the coordinate table W. Then start from the first sub-pattern in the upper left corner, scan in the order of raster scanning, and get the relevant parameter value every time a sub-pattern is scanned. If the area to which the neighbor pixel belongs and the current sub-pattern do not belong to the same area and can be merged, Then execute the merge-find algorithm with rank-based merge and path compression strategy to merge regions, otherwise continue to scan the next neighbor pixel. When the neighbor pixels of the left boundary and the upper boundary of this block are all scanned, the processing of this block is completed, the boundary information is updated, and the next sub-mode is processed according to the above steps until all sub-modes are processed, and finally the boundary information of the binary image is output. The time complexity of the method of the present invention is O(nLα(n)), wherein n represents the number of blocks of the same type, L represents the side length of each block, and α(n) is the inverse function of the ackerman function.

Compared with the prior art, the present invention has the following advantages:

1. In terms of the representation of image boundary extraction, for a given 4 images, the average number of sub-modes of NAM (LQT) is 11585 (36633), and the average compression ratio CR of NAM (LQT) is 1.3801 (0.2862), that is The compression ratio of RNAM is 4.8222 times that of LQT. At the same time, the NAM representation algorithm is also 68.38% less than the LQT representation algorithm in terms of the number of sub-patterns. Obviously, NAM is better than LQT in terms of the number of sub-patterns (68.38% reduction) and compression ratio improvement (382.22% increase). of.

2. In terms of the speed of image boundary extraction, the execution speed of boundary extraction based on NAM representation is 92.39% higher than the execution speed of boundary extraction based on LQT representation, so it is a more effective boundary extraction algorithm that occupies storage space Small, the image boundary extraction speed is fast.

Therefore, the NAM boundary extraction method provided by the present invention is superior to the LQT boundary extraction method. The present invention can be applied not only to the traditional image boundary extraction market, but also to emerging fields, such as network transmission, wireless communication, medical images and the like.

3. Compared with the existing LQT-based boundary extraction method, the NAM-based boundary extraction method of the present invention has a lower bit rate and less sub-mode numbers, thereby reducing data storage space and improving image boundary more effectively The speed of extraction is therefore a better boundary extraction method for binary images. This boundary extraction method can be applied to various aspects of image processing, and has good advantages in reducing storage space, speeding up transmission speed, and improving pattern matching efficiency. Theoretical reference significance and practical application value.

Description of drawings

FIG. 1 is a complete flowchart of the NAM-based boundary extraction method of the present invention.

Fig. 2 is a flowchart of a representation method of a binary image based on NAM.

Fig. 3a is a standard binary image F16 with a size of 512×512 used in the present invention.

Fig. 3b is a standard binary image Goldhill with a size of 512×512 used in the present invention.

Fig. 3c is a standard binary image Lena with a size of 512×512 used in the present invention.

Fig. 3d is a standard binary image Peppers with a size of 512×512 used in the present invention.

Figure 4a shows the segmentation effect of the LQT method in Figure 3c.

Figure 4b presents the effect of region merging for the LQT method.

Figure 4c shows the boundary of the binary image extracted by the LQT method.

Figure 5a shows the segmentation effect of the LQT method in Figure 3c.

Figure 5b presents the effect of region merging for the NAM method.

Figure 5c shows the boundary of the binary image extracted by the NAM method.

detailed description

Example

The purpose of the present invention is to solve the problems existing in the existing image boundary extraction technology, and to provide an image boundary extraction method based on the asymmetric inverse layout model (NAM). The overall process is shown in Figure 1, which can significantly improve the image boundary extraction. Speed and at the same time can effectively reduce storage space. The image boundary extraction method based on the asymmetric inverse layout model first needs to perform NAM representation on the binary image to obtain the total number of sub-patterns n and the coordinate table W. Then start from the first sub-pattern in the upper left corner, scan in the order of raster scanning, and get the relevant parameter value every time a sub-pattern is scanned. If the area to which the neighbor pixel belongs and the current sub-pattern do not belong to the same area and can be merged, Then execute the merge-find algorithm with rank-based merge and path compression strategy to merge regions, otherwise continue to scan the next neighbor pixel. When the neighbor pixels of the left boundary and the upper boundary of this block are all scanned, the processing of this block is completed, the boundary information is updated, and the next sub-mode is processed according to the above steps until all sub-modes are processed, and finally the boundary information of the binary image is output. The time complexity of the method of the present invention is O(nLα(n)), wherein n represents the number of blocks of the same type, L represents the side length of each block, and α(n) is the inverse function of the ackerman function. The experimental results show that: compared with the current popular LQT-based boundary extraction method, the NAM-based boundary extraction method proposed by the present invention has a lower bit rate and fewer sub-patterns, thereby reducing data storage more effectively Space and improve the speed of image boundary extraction, so it is a better boundary extraction method for binary images. This method can be applied to various aspects of image processing, and has good theoretical reference significance and practical application value in reducing storage space, speeding up transmission speed, and improving pattern matching efficiency.

As shown in Figure 2, the image representation method provided by the present invention obtains a set of different sub-patterns and a coordinate table W by representing a given binary image b with a size of G×H with a rectangle NAM , and then based on these sub-patterns, an image boundary extraction method based on an asymmetric inverse layout model is proposed. Specifically include the following steps:

(S1) Use the binary image representation method based on the asymmetric inverse layout model to encode the image b of size G×H, and obtain the total sub-pattern number n after encoding and the coordinate table W.

The specific expression method is as follows:

(S1.1) Assign all elements of the matrix variable M to 0, the size of M is equal to the binary image b to be processed, both are G×H, and the count variable n=0 of the sub-pattern is made at the same time; wherein, G and H are natural numbers;

(S1.2) Determine the starting point (x ₁ , y ₁ ) of an unmarked rectangular sub-pattern in the binary image b in the order of raster scanning, determine a sub-pattern with the largest area according to the starting point, and set The sub-pattern is identified in the binary image b;

(S1.3) Record the parameters of the sub-mode, namely: the coordinates (x ₁ , y ₁ ) of the upper left corner and the coordinates (x ₂ , y ₂ ) of the lower right corner; let n=n+1;

(S1.4) cyclically execute steps (S1.2) to (S1.3), until the sub-patterns in the binary image b are marked;

(S1.5) According to the following coordinate data compression algorithm, the coordinates of all non-zero elements in the matrix variable M are encoded, and the encoding result is stored in a coordinate table W;

①Scan the matrix variable M whose size is G×H line by line. If all the elements of this line are zero, then there is no need to encode this line. In this case, use a binary bit "0" to indicate that the line is from the beginning to the end There are no non-zero elements, and the binary bit "0" is stored in the coding table W of the row; otherwise, if there are non-zero elements in the row, a prefix "1" is added before each non-zero element ", then add codewords for identifying non-zero elements 1, 2 and -1 after the prefix, and finally store the prefix "1" and subsequent codewords in the coding table W of the row;

② Use x bits to indicate the position of the column where the non-zero element is located, and store these x bits in the coding table W of the row, where the value of x is calculated according to the following two situations;

For the first non-zero element encountered in a row, x=[log ₂ H]; the x bits here are used to indicate the position of the first non-zero element with respect to the head end of the row;

For non-zero elements encountered in a row other than the first non-zero element, x = [log ₂ (Hc)], where c is the column position of the previously encountered non-zero element; here x Bits are used to indicate the position of the non-zero element on the right side of the non-zero element of the previous encoding;

③ After the last non-zero element of a row is encoded, use a binary bit "0" to indicate that the remaining elements of the row are all zero, and store this binary bit "0" in the coding table W of the row, Otherwise, if the position of the last non-zero element of the row is at the end of the row, then there is no need to use "0" to indicate that the remaining elements of the row are all zero;

(S1.6) Output the coordinate table W, wherein W is obtained by sequentially connecting the row coding tables of all rows of the matrix variable M.

(S2) Set a serial number j of the current scanning sub-mode, and make j=0, and set a pointer matrix B at the same time, the size is G×H, which is used to indicate the area pointed to by each pixel.

(S3) Obtain W[j] in the coordinate table.

(S4) According to W[j], calculate the size, left boundary and upper boundary coordinate information of the current sub-mode.

(S5) Start from the bottom of the left boundary, scan upwards, find a pixel LL on the left of each left boundary pixel L (that is, LL is 1 smaller than L in the X direction), and use matrix B to find the pixel L and The area to which the pixel LL belongs, and then use the union search algorithm with rank-based merging and path compression strategies to find out the ancestor areas of these two areas. If the two areas are the same area, skip to the next pixel. Otherwise, if both If two regions do not belong to the same region, it is judged whether the two ancestors can be merged according to the mean and variance.

The 2 data structures used in this step and the next step are as follows:

①Region data structure domain:

{Mean, Var, Size, Father, Count, EdgeLink}

Among them, Mean indicates the gray level mean value of this area, Var indicates the gray level variance of this area, and Size indicates the size of this area, that is, the number of pixels. These three fields are used to support the merging operation of the area. The field Father is a pointer to point to the parent node of this area, Count is used for the number of descendant areas of this area, and the above two fields are used to support the union search algorithm. Field EdgeLink points to the boundary of this area, which can be used to track the boundary information of this area.

②Edge data structure domain:

{PreLink, First, Last, SucLink}

PreLink and SucLink are used to support doubly linked lists, and First and Last point to the start and end points of corner vertices.

(S6) After the left boundary scanning is completed, start from the leftmost of the upper boundary, scan to the right, and find a pixel TT above it for each upper boundary pixel T (that is, TT is 1 smaller than T in the Y direction), and use the matrix B Find out the area to which pixel T and pixel TT belong, and then use the union search algorithm with rank-based merge and path compression strategy to find the ancestor area of these two areas. If the two areas are the same area, skip to the next one pixels; otherwise, if the two regions do not belong to the same region, judge whether the two ancestors can be merged according to the mean and variance.

(S7) Update boundary information, j++, jump to (S3), until all sub-patterns are processed.

(S8) Output the boundary information of the binary image b.

This example compares the two representation algorithms LQT and NAM. The size and name of the test images used are 4 grayscale images of 'F16', 'Goldhill', 'Lena' and 'Peppers' with a size of 512×512, as shown in Figure 3a, Figure 3b, Figure 3c and Figure 3d shown.

This example first gives a comparison of the experimental results of the NAM and LQT representation methods. The representation efficiency of these two methods can be measured by the following two parameters, namely: the number of sub-patterns and the compression ratio. Table 1 (Table 1 is a comparison table of compression performance) shows the comparison of the compression performance of the NAM representation algorithm and the LQT representation algorithm. Table 2 (Table 2 is a comparison table between the number of sub-patterns and the number of blocks) shows the comparison of the number of sub-patterns and blocks between NAM and LQT representation algorithms.

Algorithms F16 Goldhill Lena Pepper LQT 0.3244 0.2060 0.2720 0.3425 NAM 1.7443 0.8786 1.2486 1.6488

Table 1

Algorithms F16 Goldhill Lena Pepper LQT 31078 48946 37072 29437 NAM 8396 17203 11374 9365

Table 2

As can be seen from Tables 1 and 2, for the given 4 images, the average CR of NAM (LQT) is 1.3801 (0.2862), and the average sub-mode of NAM (LQT) is 11585 (36633), which is the compression ratio of NAM It is 4.8222 times the compression ratio of LQT, which is more conducive to saving storage space; and the number of sub-modes in NAM representation is also reduced by 68.38% on average compared with LQT representation, which is more conducive to improving the efficiency of image representation and the speed of image processing .

In summary, compared with the LQT representation algorithm, the NAM representation algorithm has a higher compression ratio and fewer blocks, which can more effectively reduce the data storage space, and thus is a better representation of binary images. method.

As shown in Figure 4a, Figure 4b and Figure 4c, it is the segmentation, merging and boundary extraction results of the LQT of 'Lena'; as shown in Figure 5a, Figure 5b and Figure 5c, it is the segmentation, merging and Boundary extraction results. Figure 4 is an example of the LQT method, in which, Figure 4a shows the segmentation effect of the LQT method in Figure 3c, Figure 4b shows the effect of the region merging of the LQT method, and Figure 4c shows the two extracted by the LQT method The bounds of the value image. Figure 5 is an example of the NAM method, in which, Figure 5a shows the segmentation effect of the LQT method in Figure 3c, Figure 5b shows the effect of the region merging of the NAM method, and Figure 5c shows the two extracted by the NAM method The bounds of the value image.

The following table 3 (table 3 is the segmentation performance comparison table expressed by NAM and LQT) shows the comparison of the segmentation efficiency expressed by NAM and LQT.

image F16 Goldhill Lena Peppers NP 262144 262144 262144 262144 31078 48946 37072 29437 8396 17203 11374 9365 575 2405 1788 1628 575 2405 1788 1628 1406 2688 1875 1343 94 156 141 140 93.31% 94.20% 92.48% 89.58%

table 3

In Table 3, NP represents the total number of pixels in the test image, and the unit is one; NB _LQT and NB _NAM represent the number of sub-patterns when the image is represented by LQT and NAM, respectively, and the unit is one; Nreg _LQT and Nreg _NAM represent the image by LQT T _NAM and T _LQT represent the execution time of segmentation algorithms based on LQT representation and NAM representation respectively, in milliseconds.

For the given 4 images, the average CR of NAM (LQT) is 1.3801 (0.2862), and the average sub-mode of NAM (LQT) is 11585 (36633), that is, the compression ratio of NAM is 4.8222 times that of LQT. This is more conducive to saving storage space; and the number of sub-patterns in NAM representation is also reduced by 68.38% on average compared with LQT representation, which is more conducive to improving the efficiency of image representation and the speed of image processing.

In addition, it is not difficult to see from Table 3 that the execution speed of the segmentation algorithm based on NAM representation is 92.39% higher than that of the segmentation algorithm based on LQT representation, so it is a more effective segmentation algorithm.

In summary, the results of this example confirm the correctness of the analysis.

The above-mentioned embodiment is a preferred embodiment of the present invention, but the embodiment of the present invention is not limited by the above-mentioned embodiment, and any other changes, modifications, substitutions, combinations, Simplifications should be equivalent replacement methods, and all are included in the protection scope of the present invention.

Claims (2)

1. An image boundary extraction method based on an asymmetric inverse layout model, characterized in that, comprising the following steps: Step S1, using the binary image representation method based on the asymmetric inverse layout model to encode the image b of size G×H to obtain the total number of sub-patterns after encoding n and the coordinate table W; Said step S1 comprises the following steps: Step S1.1, assign all elements of the matrix variable M to 0, the size of M is equal to the binary image b to be processed, both are G×H, and the count variable n of the sub-pattern is set to be 0; among them, G and H are natural numbers; Step S1.2. Determine the starting point (x ₁ , y ₁ ) of an unmarked rectangular sub-pattern in the binary image b in the order of raster scanning, determine a sub-pattern with the largest area according to the starting point, and set The sub-pattern is identified in the binary image b; Step S1.3, recording the parameters of the sub-mode, namely: the coordinates of the upper left corner (x ₁ , y ₁ ), the coordinates of the lower right corner (x ₂ , y ₂ ); let n=n+1; Step S1.4, cyclically execute steps (S1.2) to (S1.3), until all the sub-patterns in the binary image b are marked; Step S1.5, according to the coordinate data compression algorithm, encode the coordinates of all non-zero elements in the matrix variable M, and store the encoding result in a coordinate table W; Step S1.6, output the coordinate table W, wherein W is obtained by sequentially connecting the row coding tables of all rows of the matrix variable M; Step S2, setting a serial number j of the current scanning sub-mode, and making j=0, and setting a pointer matrix B at the same time, the size is G×H, which is used to indicate the area pointed to by each pixel; Step S3, obtain W[j] in the coordinate table; Step S4, according to W[j], calculate the size of the current sub-mode and the coordinate information of the left boundary and the upper boundary; Step S5, start from the bottom of the left boundary, scan upwards, find a pixel LL on the left of each left boundary pixel L, that is: LL is 1 smaller than L in the X direction, and use matrix B to find the pixel L and The area to which the pixel LL belongs, and then use the union search algorithm with rank-based merging and path compression strategies to find out the ancestor areas of these two areas. If the two areas are the same area, skip to the next pixel. Otherwise, if both If two areas do not belong to the same area, judge whether the two ancestors can be merged according to the mean and variance; Step S6, after scanning the left boundary, start from the far left of the upper boundary, scan to the right, find a pixel TT above it for each upper boundary pixel T, that is: TT is 1 smaller than T in the Y direction, and use the matrix B Find out the area to which pixel T and pixel TT belong, and then use the union search algorithm with rank-based merge and path compression strategy to find the ancestor area of these two areas. If the two areas are the same area, skip to the next one pixels; otherwise, if the two regions do not belong to the same region, judge whether the two ancestors can be merged according to the mean and variance; Step S7, update boundary information, j++, jump to step S3, until all sub-patterns are processed; Step S8, outputting boundary information of the binary image b. 2. the image boundary extraction method based on asymmetric inverse layout model according to claim 1, is characterized in that, used Region data structure field and Edge data structure field in step S5 and step S6; The Region data structure domain is: {Mean, Var, Size, Father, Count, EdgeLink}, where Mean represents the gray mean value of this region, Var represents the gray value variance of this region, and Size represents the size of this region, namely The number of pixels, these three fields are used to support the merge operation of the region; the field Father is a pointer, used to point to the parent node of this region, Count is used to the number of descendant regions of this region, the above two fields are used to support and query Set algorithm; the field EdgeLink points to the boundary of this area, and is used to track the boundary information of this area; The Edge data structure domain is: {PreLink, First, Last, SucLink}, Among them, PreLink and SucLink are used to support the doubly linked list, and First and Last point to the start and end points of the corner vertices.