Seam Carving Techniques for Digital Still Images

Seam Carving Techniques for Digital Still Images

Dr. A. Guruva Reddy1, Ms. Madhavi Mallam1,

1Department of ECE, DVR & Dr.HS MIC College of Technology, Kanchikacharla.

Abstract

The Remote Sensing image gives information about the Earth. The four important factors of a Remotely Sensed Images are Spatial, Spectral, Radiometric and Temporal resolution. The accesses of high resolution images are restricted and these data is available to public with areas of strategic importance masked or obliterated. The Current practice is that, identified areas masked with black patches which will be seen in the images. In order to avoid such masking, the methods of Seam Carving used for digital still images are tried out in satellite images. Seam carving is an efficient approach of image resizing without effecting image statistics. We tried different approach of applying SC for only that particular region which has to be removed with some bias (AOI with certain extra region). This result was not satisfactory, which discusses that by increasing the bias for AOI we can improve quality of the image. Concepts of SC also suggest that the algorithm works efficiently well when applied to images of low information (i.e. low gradient change).

1. Introduction

   Seam-carving is one of several recently developed content-aware images resizing method, gained a measure of popularity due to its ability to overcome the limitations of traditional scaling and cropping. Its content-aware behaviour resizes an image based upon its content, whereas traditional methods frequently de- emphasize (isomorphic-scaling), distort (anamorphic- scaling) or remove (cropping) content that may be important to the viewer. The general approach to content-aware resizing involves first identifying regions of interest (ROI) within an image and then removing non-ROI portions of the image. Seam-carving then resizes the image by adding or removing connected pixel paths, or seams, that have the lowest accumulated energy. Multiple image importance (energy functions) can be used, such as a saliency map, entropy, and gradient. In particular, among these options the gradient operator is a simple yet effective operator for determining image complexity, which we shall use for our description. The seam value typically is obtained by averaging the value of the pixels on either side of the inserted seam.

   1. Seam

      A Seam is an optimal 8-connected path of pixels on a single image from top to bottom (vertical seam), or left to right (horizontal seam) where optimality is defined by an image energy function. The selection and the order of seam protect the content of the image, as defined by the energy function.

      The Seams should be

      Monotonically one and only pixel in each row column for vertical /horizontal seam.

      8 connected Being found a pixel on the seam, the next pixel that constitutes the seam is one of its three neighbors on the next row/ column.

      Among seams, an optimal seam is determined as a least perceivable region where the optimality is defined by the energy function based on the image gradient magnitude.

      A0	A1	A2
      A7	F(i,j)	A3
      A6	A5	A4

      Figure 1. Pixel Neighbourhood

      The pixel is 4-connected to pixel elements in the matrix and similarly the pixel is 8- connected to .The

      seam which travels through the paths of least importance can also travel diagonally in 8-connectivity which is an added advantage compared to 4- connectivity. i.e. in 4-connectivity the seam can either pass horizontally or vertically whereas in 8-connectivity the seams can pass both horizontally, vertically and also diagonally. This causes linear rather than abrupt artifacts in the retargeted image.

2. OPTIMAL SEAM DEFINITION

   The cost of a single pixel in is its value in ,

   i.e , if then

   Optimal Seam is the seam which contains the relatively minimum energy. In vertical direction optimal seam is defined as

   Figure 2. Vertical & Horizontal seam passing through the image

   1. DISCRETE IMAGE RESIZING

      Aspect ratio of a given image from to from where .This can be achieved simply by successively removing vertical seams from .This operation will not alter important parts of the image and in effect creates a non uniform content aware resizing of the image. The same aspect ratio correction from to can also be achieved by increasing the number of rows by factor of

      .The added value of such an approach is that it doesnt remove any information from the image.

      1. TO FIND OPTIMAL SEAM

         The visual impact is noticeable only along the path of the seam leaving the rest of the image intact.

         The first step is to traverse the image from the second row to the last column and compute the cumulative minimum energy M for all possible corrected seams for each entry (i,j)

         At the end of the process, the minimum value of the last row in will indicate the end of the minimal connected vertical seam.

         In the second step we backtrack from this minimum entry on to find the path of optimal seam. Randomly removing pixels should keep the average unchanged, but content-aware resizing should raise the average as it removes low energy pixels and keeps the high energy one.

         Figure 3. Energy map

         Figure 4. Cumulative Energy map

      2. OBJECT REMOVAL

   For image resizing, user usually wants to protect or remove specific object in the image. However, automatic image resizing by seam carving is difficult to meet this requirement because the energy function by low-level features is hard to discriminate different object with high-level semantics. If an intuitive and easy user interface is provided to user to define the semantic object to be protected or removed, it will be beneficial to image resizing.

   Another application of seam carving is object removal where you can select an undesirable object from the image, and use seam carving to remove it smoothly. Here, we manually assign large negative energy to the region of interest to make sure that the optimal seams pass through the region. However, since we are removing several seams from the same region this may cause distortion. To solve this problem, Seams can be inserted where the object used to be.

   output pixel would be the entropy value of the 3-by-3 neighbourhood around the corresponding pixel in the original image. This metric measures the information that each pixel contains.

   3.2 OPTIMAL SEAM DETECTION

   A vertical seam for image is defined as

   Figure 5. Original image

   where

   Likewise a horizontal seam is defined as

   ,

   , where

   Figure 6. Object removed image

3. METHODOLOGY ADOPTED FOR SEAM CARVING

As mentioned before, the main idea behind seam carving algorithm is to remove unnoticeable pixels while preserving the significant content of the image. The pixel importance can be measured by some metric such as gradient operator, entropy operator, etc.

In this section we describe each step in details.

For an image of size the following methodology is followed.

3.1 GENERATION OF ENERGY MAP

There are a number of ways to extract the unnoticeable pixels from an image. First and most straightforward is to assign energy to each pixel by using a gradient operator (e.g.Sobel) to compute the gradients in both and irections, The energy function is defined for each pixel as follows

This is a metric for measuring the variation of the image in both directions and then assigning a number to each pixel. Instead of energy function, a local entropy filter can be applied on image, where each

In other words, a vertical seam is a path from top to bottom (left to right for horizontal) containing only one pixel from each row. Horizontal seam can be detected by transposing the image.

The cost of the seam is defined as the sum of the energies of the pixels along the seam path

An optimal seam would have the minimum seam cost. In order to find this seam, we first define the cumulative minimum energy map for the second row to last row as the following

Then the optimal seam would be found by taking the minimum pixel value in the last row of which would be the end of the optimal seam path. We then track the optimal seam path by going upwards in matrix and finding the minimum value among the three adjacent pixels right above the first one. The above calculations were all described for vertical seams. For horizontal seams all the implementation can simply be done on the transposed version of the image.

3.3. BASIC METHODOLOGY FOR OBJECT REMOVAL

1. Import the image for which the object to be removed using SC technique. The image can be in any of formats like jpeg, bmp, tiff etc.

2. Identify the AOI (Area of interest) i.e. object for removal from the image. The AOI is identified manually with the help of Microsoft picture manager. In this work we are using a regular polygon like square or rectangle whose dimension vary depending on object to be removed. As a further extension we can use any irregular shape using GUI.

3. We assign high negative value to each and every pixel in the selected AOI. In order to make sure that the selected AOI possess least gradient compared to gradient of the entire image we have assigned -106 to every pixel in the AOI. The purpose of assigning high negative gradient in the image is to concentrate SC process in the specified/selected region i.e. AOI.

4. The methodology and details for Seam Removal is explained 4.3.1 and the process is shown in figure

   4.4.2. Seam Removal is a continuous and terminates when all the seams of least importance in the AOI are removed completely.

5. When the process of Seam Removal ends, the object is removed. Now find the gradient of this image i.e. object removed image.

6. To retarget the image back to its original size find

   Import Image

   Identify the object to be removed

   Assign high negative gradient to the ROI

   Perform Seam Removal

   No

   Is object Removed

   Yes

   the seam of least importance in the object removed

   image. Now insert these seams of least importance in least important regions of the image.

7. The process of Retargeting is also iterative and

   Find gradient of Seam Removed Image

   terminates only when the image is retargeted back to

   its original size i.e. number of seams removed is equal to number of seams inserted.

8. Selected object is removed from the image and the resultant image same dimensions of the original image.

9. The above process of SC for Object Removal is given.

   Find seam of least importance

   Insert seams to retarget the image

   Figure 7. Flow Diagram for Object Removal

   NO

   Is image Retargeted

   Yes

   Object Removed

   1. RESULTS & ANALYSIS

      The Seam Carving techniques discussed is applied to PAN Data of IRS 1D Satellite. The resolution of this image is 5.8m which is bandwidth.

      Object to be Removed

      Table 1 Image statistics of pre processed image

      Image statistics	Pan Image (Hyderabad)
      Min	0
      Max	255
      Mean	113.295
      Median	106
      Mode	0
      Std dev	78.649
      Entropy	7.5418

      Figure 8. Pan data of Image before Removal

      Objective of our work is to suggest a method which effectively provides security by removing an object having certain spatial attributes without effecting geographic locations of the image.

      Object Removed

      Figure 9. SC Applied to the entire image object removed

      Table 2 Image statistics of Post Processed Image

      Image statistics	Pan Image Output image (Object Removed)
      Min	0
      Max	255
      Mean	114.375
      Median	107
      Mode	0
      Std dev	78.563
      Entropy	7.561

      N

      o

      o f

      P

      i x e l

      Brightness Value

      Figure 10. Histogram of Original Image

      N

      o

      o f

      P

      i x e l

      Brightness Value

      Figure 10. Histogram of Object Removed Image

      The technique of SC for object removal is also applied on satellite image of high resolution 2.5m. The artifacts are minimal and the object removed image is more close to the original image.

   2. CONCLUSION

This paper is mainly focused the concept of SC for object removal for IRS data which is implemented using a high level interactive language called Matlab. After implementation we noticed artifacts are introduced in images which disturb the geometric quality of the images. Even though there are minor variations in image statistics these visual artifacts cannot be ignored. For obtaining better results we selected a specific AOI with different bias 50 and 100 and applied SC for object removal to the image. After object removal we inserted back AOI to the original image. In case of Bias 50 even though statistics at most remain the same, there are minor variations in the histograms distribution and reduced artifacts which cannot be accepted. In case of bias 100, the image statistics, histograms distribution remain same exactly as that of the of original image. Visual artifacts were also minimum compared to the image with bias 50. SC techniques for high resolution images are better compared to that of coarse resolution images.

REFERENCES

1. AlexeiA.Efros, and Willam T.Freeman, Image Quilting for texture synthesis and transfer.University of California, Berkeley, 2Mitsubishi Electric Research Laboratories.

2. Alex Mansfield, Peter Gehler, Luc Van Gool, and Cassten Rother, Visibility Maps for Improving Seam Carving. Computer vision laboratory, Switzerland, ESAT-PSI, KU Leven, Belgium, Microsoft research ltd, Cambridge, UK.

3. Arrate Munoz, Therry Blu, and Michael Unser, Least- Squares Image Resizing using Finite Differences, IEEE Transactions on Image Processing, vol 10, no.9, pg 1365- 1378, sept-2001.

4. Avidan and Ariel Shamir .,Seam Carving for content aware Image Resizing, Mitsubishi Electric Research Labs, Interdisciplinary centre & MERL,2007.

[5]B.C Forster.,1984,Derivation of atmospheric correction procedures for landsat mss with particular reference to urban data.International journal of remote sensing,5,no 5,pp 799-817.

[6]B.K. Mohan and S. N. Ladha., Comparision of object based and pixel and pixel based of high resolution satellite images using artificial neural networks. Centre for Studies in Resources Engineering IIT Bombay, Powai, Mumbai.

1. Bruno Aiazzi, Luciano Alparone, Stefano Baronti, Andrea Garzelli, Massino Selva. A theoretical evaluation of aliasing and misregistration effects on pan sharpening methods. Image and Signal Pocessing for Remote Sensing vol 7830, Feb 2011.

2. Claude Fillion, Gaurav Sharma, Detecting Adaptive Scaling of Images for Forensic Applications. Proc SPIE Media Forensics, vol 7541, pp 7541-36, Jan 2010. [9]C.Pohl., J.L Van Genderen, Review article Multisensor image Fusion in Remote Sensing: Concepts

,methods and applications .International Journal; of Remote sensing,19:5,823-854,25th November 2010. [10]David D.conger., Mrutyunjaya Kumar., RodneyL.Miller.,Jiebo Luo.,and Hayder Radha.,Improved Seam carving for image resizing. Michigan State University, dept of Electrical &Computer Engineering,Rochester.

Dr. A. GuruvaReddy is working as Professor, Dept. of ECE, DVR & Dr.HS MIC College of Technology, Kanchikacharla, Krisna (D). He received his B.E (ECE) degree from the University of Mysore, Karnataka,

M.E (Communication Systems) from the Anna University and Ph.D from

JNTU Ananthapur. His area of interests is Image Processing and Signal Processing

Mrs. M. Madhavi is working as Associate Professor, Dept. of ECE, DVR & Dr.HS MIC College of Technology, Kanchikacharla, Krishna (D). She received her B.Tech, from INTU Hyderabad and M.Tech (DECS) from Jawaharlal Nehru Technological University, Hyderabad in 2008. Her areas of interests is Signal

Processing and communications.