I have been working for a while now. I am writing a blog for the first time. I don’t know how to write it. Let’s just read it. Please correct me if you have any incorrect words.
Recently, an image compression function has been used in work. I found some tools, but there was no good choice. Finally, I chose a person named jdeli, but efficiency became a problem again. I had no choice but to study its source code, but found that I was interested in one of its subtractive quantization algorithms. However, I was embarrassed that I didn't understand what it was writing at all, so I had the idea of implementing a quantitative color algorithm by myself.
I found some information myself and found three more commonly used color processing algorithms:
Popular color algorithm:
The specific algorithm is to first count the number of times all colors appear in an image, select the 256 colors with the most occurrences as the color of the palette of the picture, and then iterate through all pixels of the picture again, find the closest color in the palette for each pixel (I use the variance method here), and write it back to the picture. The implementation of this algorithm is relatively simple, but the distortion is relatively serious. Some images appear at a low frequency, but the visual effect on the human eye is quite obvious. Information will be lost. For example, high-brightness spots in the image may not be selected by the algorithm due to the small number of occurrences and will be lost.
Median slicing algorithm:
I have not studied this algorithm. Those who want to know can read this article, which contains introductions of three algorithms.
Octave Tree
This algorithm is the last algorithm I chose. Its main idea is to convert the RGB color value of the image into binary distribution into octree, for example: (173,234,144)
To convert to binary is (10101101, 11101010, 10010000), take out the first bits of R, G, B to form (111), and serve as the child nodes of the root node, where 111 is the index of the root child node array, and so on, until the last bit, and then store the component value of this color and the number of occurrences on the leaf node. See the picture for details.
One of the things I am more confused about is the merge strategy of leaf nodes. The stupidest method I use here is to find the deepest node and then merge. It is a bit simple and crude. There are other better methods. Please leave me a message. The picture is too big and cannot be uploaded, so I just upload the code. The code has not been refactored, so everyone can read it.
package com.gys.pngquant.octree;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;/** * * @ClassName Class name: Node * @Description Function description: * <p> * Octet tree implementation* </p> * * 2015-12-16 guoys Create this class function. * ********************************************************* * </p> */public class Node{private int depth = 0;// When it is 0, it is a root node private Node parent;private Node[] children = new Node[8];private Boolean isLeaf = false;private int rNum = 0;private int gNum = 0;private int bNum = 0;private int piexls = 0;private Map<Integer, List<Node>> levelMapping;// Store the relationship between the hierarchy and node public int getRGBValue(){int r = this.rNum / this.piexls;int g = this.gNum / this.piexls;int b = this.bNum / this.piexls;return (r << 16 | g << 8 | b);}public Map<Integer, List<Node>> getLevelMapping() {return levelMapping;}public void afterSetParam(){if(this.getParent() == null && this.depth == 0){levelMapping = new HashMap<Integer, List<Node>>();for (int i = 1; i <= 8; i++) {levelMapping.put(i, new ArrayList<Node>());}}} public int getrNum() {return rNum;}public void setrNum(int rNum) {if(!isLeaf){throw new UnsupportedOperationException();}this.rNum = rNum;}public int getgNum() {return gNum;}public void setgNum(int gNum) {if(!isLeaf){throw new UnsupportedOperationException();}this.gNum = gNum;}public int getbNum() {return bNum;}public void setbNum(int bNum) {if(!isLeaf){throw new UnsupportedOperationException();}this.bNum = bNum;}public int getPiexls() {return piexls;}public void setPiexls(int piexls) {if(!isLeaf){throw new UnsupportedOperationException();}this.piexls = piexls;}public int getDepth() {return depth;}// Return the number of child nodes of the node public int mergerLeafNode(){if(this.isLeaf){return 1;}this.setLeaf(true);int rNum = 0;int gNum = 0;int bNum = 0;int pixel = 0;int i = 0;for (Node child : this.children) {if(child == null){continue;}rNum += child.getgNum();gNum += child.getgNum();bNum += child.getbNum();pixel += child.getPiexls();i += 1;}this.setrNum(rNum);this.setgNum(gNum);this.setbNum(bNum);this.setPiexls(pixel);this.children = null;return i;}// Get the deepest nodepublic Node getDepestNode(){for (int i = 7; i > 0; i--) {List<Node> levelList = this.levelMapping.get(i);if(!levelList.isEmpty()){return levelList.remove(levelList.size() - 1);}}return null;}// Get the number of leaf nodes public int getLeafNum(){if(isLeaf){return 1;}int i = 0;for (Node child : this.children) {if(child != null){i += child.getLeafNum();}}return i;}public void setDepth(int depth) {this.depth = depth;}public Node getParent() {return parent;}public void setParent(Node parent) {this.parent = parent;}public Node[] getChildren() {return children;}public Node getChild(int index){return children[index];}public void setChild(int index, Node node){children[index] = node;}public Boolean isLeaf() {return isLeaf;}public void setPixel(int r, int g, int b){this.rNum += r;this.gNum += g;this.bNum += b;this.piexls += 1;}public void setLeaf(Boolean isLeaf) {this.isLeaf = isLeaf;}public void add8Bite2Root(int _taget, int _speed){if(depth != 0 || this.parent != null){throw new UnsupportedOperationException();}int speed = 7 + 1 - _speed;int r = _taget >> 16 & 0xFF;int g = _taget >> 8 & 0xFF;int b = _taget & 0xFF;Node proNode = this;for (int i=7;i>=speed;i--){int item = ((r >> i & 1) << 2) + ((g >> i & 1) << 1) + (b >> i & 1);Node child = proNode.getChild(item);if(child == null){child = new Node();child.setDepth(8-i);child.setParent(proNode);child.afterSetParam();this.levelMapping.get(child.getDepth()).add(child);proNode.setChild(item, child);}if(i == speed){child.setLeaf(true);}if(child.isLeaf()){child.setPixel(r, g, b);break;}proNode = child;}}public static Node build(int[][] matrix, int speed){Node root = new Node();root.afterSetParam(); for (int[] row : matrix) {for (int cell : row) {root.add8Bite2Root(cell, speed);}}return root;}public static byte[] mergeColors(Node root, int maxColors){byte[] byteArray = new byte[maxColors * 3];List<byte> result = new ArrayList<byte>();int leafNum = root.getLeafNum();try{while(leafNum > maxColors){int mergerLeafNode = root.getDepestNode().mergerLeafNode();leafNum -= (mergerLeafNode - 1);}}catch(Exception e){e.printStackTrace();}fillArray(root, result, 0);int i = 0;for (byte byte1 : result) {byteArray[i++] = byte1;}return byteArray;}private static void fillArray(Node node, List<byte> result, int offset){if(node == null){return;}if(node.isLeaf()){result.add((byte) (node.getrNum() / node.getPiexls()));result.add((byte) (node.getgNum() / node.getPiexls()));result.add((byte) (node.getbNum() / node.getPiexls()));result.add((byte) (node.getbNum() / node.getPiexls()));} else{for (Node child : node.getChildren()) {fillArray(child, result, offset);}}}}}Poor my only data structure in college. The code only implements an octree. It takes about 450ms to quantize a 1920*1080 image, and if level -2, it is about 100ms.
Okay, that's it. Before I wrote it, I felt that I wanted to say a lot, but I didn't know what to say when I wrote it. Please forgive me.
Summarize
The above is all the content of this article about Java's simple implementation of octree image processing code examples, I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!