Sunday 30 October 2016

Image Processing (Read and Write) in Java

java.awt.image.BufferedImage
To perform image read and write, the BufferedImage class can be used as holder class. This class is used to store an image in RAM.

javax.imageio.ImageIO
To perform the image read write operation we will import the ImageIO class. This class has static methods to read and write an image.

package amazon.dp;
import java.io.File;
import java.io.IOException;
import java.awt.image.BufferedImage;
import javax.imageio.ImageIO;

public class ImageReader {

     /**
      * readImage - Method to read an IMAGE
      * @param width
      * @param height
      */
     private static BufferedImage readImage(int width, int height) {

           /** Create an object of BufferedImage with parameter width, height and
            * image int type.TYPE_INT_ARGB represents the Alpha, Red, Green and Blue
            * component of the image pixel using 8 bit integer value. */
           //For storing image in RAM
           BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);


           try {

                File input_file = new File("D:\\Python\\InImage.jpg"); //image file path


                // Reading input file
                image = ImageIO.read(input_file);

                System.out.println("Reading complete.");


           } catch(IOException e) {
                System.out.println("Error: "+e);
           }

           return image;
     }

     /**
      * writeImage - Method to write an IMAGE
      * @param BufferedImage image
      */
     private static void writeImage(BufferedImage image) {
           try {
                // Output file path
                File output_file = new File("D:\\Python\\OuImage.jpg");

                // Writing to file taking type and path as
                ImageIO.write(image, "jpg", output_file);

                System.out.println("Writing complete.");
           } catch(IOException e) {
                System.out.println("Error: "+e);
           }
     }

     public static void main(String args[]) throws IOException {
           int width = 963;    //width of the image
           int height = 640;   //height of the image

           // READ Image
           BufferedImage image = readImage(width,height);

           // WRITE Image
           writeImage(image);
     }
}

Saturday 29 October 2016

Longest Repeating Subsequence

Find length of the longest repeating subsequence such that the two subsequences don’t have same string character at same position, i.e., any k’th character in the two subsequences shouldn’t have the same index in the original string.

This problem can be solved using the Longest Common Subsequence problem. LRS(str, str) where str is the input string with the restriction that when both the characters are same, they shouldn’t be on the same index in the two strings.


package amazon.dp;

public class LongestRptSubseq {

     private static int getLRS(String string) {
          
           char[] charArray = string.toCharArray();
           int len = charArray.length;
          
           int[][] dp = new int[len+1][len+1];
          
           for(int i=1;i<=len;i++) {
               
                for (int j=1;j<=len;j++) {

                     // If characters match and indexes are not same
                     if (charArray[i-1] == charArray[j-1] && i!=j) {
                           dp[i][j] =  1 + dp[i-1][j-1];
                          
                     } else {
                           // If characters do not match
                           dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                     }
                }
           }
          
           return dp[len-1][len-1];
     }

     public static void main(String[] args) {
           String string = "amazonazom";
           int len = getLRS(string);
           System.out.println("Longest Repeating Subsequence "+len);
     }
}

Count number of ways to cover a distance

Count total number of ways to cover the distance with 1, 2 and 3 steps.

Recursion solution time complexity is exponential i.e. O(3n).

Since same sub problems are solved again, this problem has overlapping sub problems property. So min square sum problem has both properties of a dynamic programming problem.


public class MaxStepsCount {

     /** Dynamic Programming. */
     private static int getMaxWaysDP(int distance) {

           int[] count = new int[distance+1];
           count[0] = 1;
           count[1] = 1;
           count[2] = 2;

           /** Memorize the Sub-problem in bottom up manner*/
           for (int i=3; i<=distance; i++) {
                count[i] = count[i-1] + count[i-2] + count[i-3];               
           }
           return count[distance];
     }


     /** Recursion Approach. */
     private static int getMaxWaysRecur(int distance) {
           if(distance<0) {
                return 0;
           } else if(distance==0) {
                return 1;
           }
           return getMaxWaysRecur(distance-1)+getMaxWaysRecur(distance-2)
                     +getMaxWaysRecur(distance-3);
     }

     public static void main(String[] args) {
           // Steps pf 1, 2 and 3.
           int distance = 10;

           /** Recursion Approach. */
           int ways = getMaxWaysRecur(distance);
           System.out.println(ways);

           /** Dynamic Programming. */
           ways = getMaxWaysDP(distance);
           System.out.println(ways);
     }
}
Related Posts Plugin for WordPress, Blogger...