Image Retargeting through Constrained Growth of Important Rectangular Partitions

Abstract

The challenge of displaying an image in a much smaller target area is to maintain recognizability of its contents. A novel rectangular partitioning based retargeting scheme is proposed in this paper to address this issue. Constrained growth of rectangular partitions containing important objects is major characteristic of this scheme. Subjective evaluation by a group of volunteers establishes usefulness of this scheme.

Keywords: Image retargeting.

Introduction

Resizing an image, even of moderate size, to display it on a small gadget (such as, cell-phones) reduces recognizability of its contents. Content-aware processing addresses this issue by differentiating image contents on the basis of their importance. Image cropping [1,2,3] and fisheye-view warping [4] are effective for images with single important object. But they are not that much effective when important contents are sparsely distributed within the image. Unimportant contents still occupy a major portion of the display in such case. Rapid Serial Visual Presentation (RSVP) [5] displays important portions of the image one-by-one.

On the other hand, seam carving (originally proposed by [6]) and optimized scale-and-stretch warping [7] are effective irrespective of spatial distribution of important contents within the image. Seam carving fits an image to the target space by iteratively removing seams that pass through less important contents of the image. Removing excessive number of seams to fit the image in small target space often induces distortion. Later on, controlled seam carving [8,9] strategies have been proposed to check such distortion. Optimized scale-and-stretch warping [7] iteratively computes local scaling factors for each local region.

This paper introduces another novel scheme that also can operate irrespective of spatial distribution of important contents. Relative enlargement of important contents is estimated here by considering their size and spatial positioning only. A simplistic rectangular partitioning of image space based on the importance of each individual content and similar partitioning of the target space add novelty to the proposed scheme. Unlike some previous literature on image retargeting, this paper does not focus on deriving importance of individual image content. Rather it focuses only on how important contents can be enlarged.

The organization of the paper is as follows: A brief discussion on extracting rectangular regions of importance is presented in section 2. In section 3, the retargeting scheme is described where important rectangles are disproportionately enlarged. Section 4 discusses about subjective control over the relative size change to obtain distortion free result. Results along with subjective evaluation are presented in section 5. Finally, conclusions are drawn in section 6.

Region of Importance Extraction

Visual attention models which compute saliency based on low-level image features are commonly used in deriving importance of image contents. The saliency model in [10] is used here for our experiments as recent experiments have established its superiority as compared to others (for e.g., the model in [11]). Face detectors [12,13] can also be combined with saliency models to incorporate some semantic knowledge in importance computation. Though face detection module is not considered in our current study.

Once the importance map is obtained, important objects are extracted as follows. A line parallel to X-axis passing through the center point of the importance map partitions it in two portions: L and R. Again, a line parallel to Y-axis passing through this center point partitions the importance map in two portions: U and B. Let Ml, Mr, Mu and MB be the maximum importance values in L, R, U and B, respectively. A threshold Ts is fixed at p% of the lowest of these four importance values.

Then the importance map is binarized using the threshold Ts to get pixels with high importance. Each set of connected important pixels form one important object. For ease of computation, we do away with the irregular shapes of important objects using a minimum rectangle rj for each important object i. The saliency map along with important rectangles identified for an image is shown in Figure 1.

Fig. 1. A sample input image (left) and important rectangles superimposed on the importance map of the image (right)

Proposed Retargeting Scheme

The retargeting scheme, proposed in this section, uses the important rectangles identified in previous section to generate the retargeted image.

Initial Position of Important Rectangles in Target Space

Edges of the important rectangles are parallel to the horizontal and vertical axis. Such a rectangle ri can be specified by its top-left and bottom-right corner points. Let, (ci, di) and (fi, gi) are these points for ri in the original image. Scaled down versions of the important rectangles are positioned in the target space (i.e., smaller display). Their positions in the target space are indicated by end points of main diagonal (ct, dt) and (ft, gt). These points are estimated as follows:

where hi and wi are height and width of the original image, respectively. ht and wt denote height and width of the target space, respectively. [•] returns the smallest integer greater than or equal to its input argument.

Growing Important Rectangles in Target Space

Important rectangles are allowed to grow within the target space. But few basic constraints are also maintained to prevent arbitrary growth of these rectangles. These constraints are:

1. Aspect ratio of each important rectangle is preserved.

2. All important rectangles are enlarged equally.

3. Rectangles do not cross the boundary of target space while being grown.

4. Relative ordering in position of the horizontal and vertical edges of these rectangles is preserved.

To ensure condition 1, height and width of a rectangle are multiplied with equal resizing gain factor A. Condition 2 is preserved by enlarging all the rectangles with equal value for A. It is also checked whether boundary of a rectangle crosses the boundary of the target space (condition 3). If it crosses the target space boundary, it is translated back into target space. Across any direction (vertical or horizontal), relative ordering of horizontal and vertical edges of these rectangles is maintained (condition 4). To maintain relative ordering of horizontal edges, rank correlation coefficient of x coordinates of the corner points before and after enlargement is checked. If there is no change in ordering, the value of the coefficient will be 1. Similar checking with y coordinates preserves relative ordering of vertical edges. Condition 4 also ensures that there is no overlapping between two rectangles. The maximum possible value for the resizing gain factor (Xmax) that satisfies all these constraints is estimated using an iterative procedure. At first iteration, its value is assigned to 1. In subsequent iterations, it is increased by a small value AX (0.01 in our implementation) and is checked whether the constraints are satisfied. Remaining computation is performed using the maximum possible value of the resizing gain factor that satisfies the afore mentioned constraints.

Partitioning into Rectangles and Mapping

After locating the important rectangles in both the original image and the target space, the remaining areas (outside these important rectangles) are partitioned into small rectangular pieces through following steps:

Step 1: All the four sides of each important rectangle ri (or its resized version in the target space) are drawn (in the raster space) with black in a white background which is of same size as original image (or target space). This produces a binary image. The upper horizontal edge of a rectangle ri is the line segment between points (ci, di) and (ci, gi) (or between points (ct, dt) and (ct, gt) in the target area). The lower horizontal edge of a rectangle ri is the line segment between points (fi, di) and (fi, gi) (or between points (ft, dt) and (ft, gt) in the target area).

Step 2: Each horizontal edge (upper and lower sides of the important rectangles) is elongated in both direction until it touches either a vertical line, a collinear horizontal line or area boundary. Whenever the elongating line encounters a black point, it is understood that it has touched either a vertical line or a collinear horizontal line.

Number of important rectangles and their edge orderings are same in both the original image and target space. Therefore, this partitioning scheme produces equal number of partitions in these spaces unless two parallel line segments become collinear or overlap with each other. But the constraint 4 mentioned in the previous section prevents two noncollinear lines to become collinear or overlap with each other. Here, the image boundaries are also considered as line segments.

One-to-one mapping between partitions in original image and target space is established. After that, content of each partition in the original image is fitted into the corresponding partition in the target area. Thus the retargeted image is obtained.

Obtaining a Distortion-Free Image

The target area being fixed, the relative enlargement of important rectangles reduces unimportant rectangles. In some cases, this may introduce various types of distortion in the retargeted image if the resizing gain factor X is large. As of the current stage of research, automatic identification of appropriate value of X is not possible considering all the artifacts. Moreover, some artifacts introduced due to relative size change of important and unimportant objects may be of subjective nature. Therefore, a possible implementation of the proposed scheme is as follows: It presents the viewer with a retargeted image with A = Amax. If the viewer is not satisfied with the quality of the result, she is allowed to gradually decrease the value of A until the desired quality is obtained.

Results and Discussions

The proposed scheme is tested using 100 images. Results for these were generated using a A value that suits the subjective quality according to our observation. These results are compared against those from cropping [1] and controlled seam carving [8]. The results obtained for some of the images are shown in Figure 2. To test the effectiveness of various retargeting strategies, it is necessary to prepare the outcomes of the comparing schemes using the same importance map. Therefore, the saliency [10] based importance map is used for all three concerned methods. The results of these retargeting schemes are presented in Figure 2. It can be observed from Figure 2 that enlargement of the important objects is much in the proposed scheme as compared to other schemes at the presence of multiple important objects. Performance of the proposed scheme is also comparable to other schemes for images with single important object.

Fig. 2. Columns from left to right: down sampled version of the original image, output of the proposed scheme, image cropping [1] and seam curving base method [8], respectively

Evaluation of retargeting is essentially of subjective nature. Hence, it is resorted to manual judgments for evaluation. All the results were presented to forty-one volunteers. They were asked to evaluate each result of each scheme as either good (score 2), average (score 1) or poor (score 0). For each scheme, scores of 100 images are summed up to find a score for that scheme. Mean score is computed for each scheme over scores given by all volunteers. Average score per image (and per volunteer) of the proposed rectangle partitioning based scheme is 1.39, whereas those for the cropping and the controlled seam curving based scheme are 0.99 and 1.09, respectively. Therefore, subjective evaluation demonstrates the usefulness of the proposed scheme over cropping and seam carving.

Conclusion

Enlarging important contents of the image through a rectangular partition based scheme restores their recognizability. All important objects are enhanced uniformly and their aspect ratios are kept unchanged. Relative ordering of their placement in the target area is also kept same as that in the original image. Ability to perform in the presence of multiple sparsely distributed important objects is another notable point for the proposed scheme.