1 Introduction
In this project, we design an algorithm to sequentially merge adjacent regions with similar intensities to generate a cartoonlike image that resembles the input grayscale one. Initially, each pixel on a grayscale image is treated as a region; at each iteration, only the region pair with the lowest discrepancy measurement (defined later) are selected to be merged. When two regions are merged together, the colors of the pixels in the original regions are replaced with the mean pixel intensities of the newly combined one. Therefore, as shown in Fig.
1↑, after more and more iterations of merging proceed, the output image contains fewer and fewer growing homogeneous regions.
The discrepancy measurement between regions i and j is defined as follows:
D = S_{i}U_{i} + S_{j}U_{j} − S_{ij}U_{ij}.
In this definition,
S_{i} is the sum of image pixel intensities,
A_{i} the number of pixels, and
U_{i} (
U_{i} = (S_{i})/(A_{i})) the mean pixel intensity, all in region
i. In addition, subscript
ij indicates the newly generated region through the of regions
i and
j. According to this definition, any two neighboring regions share a
D value, so efficiently locating the smallest member among all
D’s is an important issue. Moreover, when two regions are merged, the information stored in the neighbors, such as discrepancy measurements, should be accordingly updated. Furthermore, the container storing the information of regions should be designed to exchange data quickly. Based on the aforementioned concerns, we adopt a special data structure in this project: a generic doubly linked list.
2 Doubly linked list
A doubly linked list can be visualized in Fig.
3↓.
Compared to using arrays to store data, users do not have to predict the memory usage required by a linked list in advance. In addition, inserting a node into or deleting a node from a linked list is efficient. Most importantly, the concatenation of linked lists can be simply implemented using a few lines of code. Based on these merits (especially the last one), a linked list is used to store all regions of a grayscale image, as shown in Fig.
4↓.
3 Region merging
A region merging case is illustrated in Figs.
7↓ and
8↓. Fig.
7↓ the situation before two of the regions with the smallest
D are merged. Fig.
8↓ shows the result of the region merging. To facilitate region merging and information updating, each region is equipped with the following information:
1) One doubly linked list for storing the indices of pixels categorized into this region (placed at the top in each ellipse in Figs.
7↓ and
8↓)
2) One doubly linked list for storing the pointers referencing to the neighbors of this region (placed at the bottom in each ellipse)
3) One pointer referencing to the neighbor that has the smallest discrepancy with this region (arrow in red)
4) The smallest discrepancy measurement (shown in each ellipse)
5) S_{i}, A_{i}, U_{i}, and other useful auxiliary information (not shown)
In our example shown in Figs.
7↑ and
8↑, regions are marked with numbers to elucidate their roles in the diagrams. At each iteration of region merging, the region pair with the lowest discrepancy measurement (regions
1 and
2 in Fig.
7↑) is selected to merge together to produce a new one (region
1^{′}). As such, the total number of regions on a grayscale image will reduce by one after each iteration.
When regions 1 and 2 are merged together, the following operations are executed:

Region 1^{′}

The internal linked lists storing pixel indices in regions 1 and 2 are simply concatenated together in region 1^{′}.

The intensities of all pixels are set to the mean pixel intensity. (The color of region 1^{′} in Fig. 8↑ is determined by the mean pixel intensity of regions 1 and 2, shown in Fig. 7↑.)

The linked lists storing pointers referencing to neighbors in regions 1 and 2 are concatenated together. However, regions 1 and 2 are mutually neighbors, so the pointers that refer to one another should be removed from the concatenated linked list. Moreover, given that regions 1 and 2 may have common neighbor(s) (region 0, in this case), the concatenated linked list may consequently have duplicate nodes. Duplicate nodes should be removed. (As a result, the upper linked list in the ellipse of region 1^{′} in Fig. 8↑ has only two nodes instead of five, the of the all original neighbors of regions 1 and 2.)

The discrepancy measurements between region 1^{′} and its neighbors are evaluated. Among all the evaluations, the smallest one is recorded. Correspondingly, the pointer referencing to the neighbor that has the lowest discrepancy measurement with region 1^{′} is updated (the boldfaced value and the red arrow in the ellipse of region 1^{′} in Fig. 8↑).

The neighbors of region 1^{′}

The pointers originally referencing to regions 1 or 2 should be redirected to region 1^{′}. If a region has two pointers to regions 1 and 2, respectively, only one of them is redirected to region 1^{′}; the other is removed (the arrows emitting from regions 0 and 3 to 1^{′}).

The lowest discrepancy measurement and its corresponding pointer MAY need updating if the discrepancy with region 1^{′} is smaller than the originally recorded value (the red arrows emitting out of regions 0 and 3 and the emboldened values).
4 Minheap and back pointers
As mentioned in the first paragraph, the minimum is selected out of all discrepancy measurements at each regionmerging iteration. Although we can simply loop through all nodes to find the minimum (easy but inefficient), we can adopt a minheap with back pointers to boost the efficiency of locating the lowest discrepancy measurement among all region pairs.
Fig.
9↓ illustrates how a minheap (the binary tree in the middle) and back pointers (pointers stored in array “bckptr” on the left) are connected. The minheap (implemented by array “minheap”) traces each entry in array “data,” in which each entry is bound with one element in array “bckptr.” As such, users can locate the tracer of a certain data element in the minheap by simply tracing the corresponding back pointer of the data element.
The advantage of combining a minheap with back pointer is that the back pointers improve the efficiency of maintaining the minheap. Imagine that element 0 in array “data” were changed to 2.7. Without the existence of the back pointers, users must exhaustively search the minheap to find the tracer of element 0 and subsequently rearrange a number of nodes to reflect the change of element 0. However, with the help of back pointers, users can directly access the tracer of element 0 in the minheap without wasting CPU cycles to search the entire minheap.
5 Associating minheap and the into this project
The minheap and back pointers in Fig.
9↑ require modifications when integrated to trace the discrepancy measurements of in all nodes. As shown in Fig.
11↓, elements in array “minheap” trace the discrepancy measurements using pointers (symbolized by
). Back pointers (symbolized by
) and discrepancy measurements are always bound together, so they are declared as the data members of regions.
The significance of the back pointers in this application is illustrated in Figs.
11↓ and
12↓ (note that these two figures correspond to Figs.
7↑ and
8↑). When regions
1 and
2 are merged to form region
1^{′}, the discrepancy measurements of the neighbors of
1^{′} (regions
0 and
3) are changed correspondingly (
D values painted with cyan), which triggers the rearrangement of some elements in the minheap. With the back pointers, the elements whose positions in the minheap need changing can be directly located (through cyan arrows).