Java Simple Implementation of Octree Image Processing Code Example

After a while at work, it's my first time to write a blog, and I'm not quite sure how to write it. Please bear with it, and please correct any inaccuracies that may be mentioned.

Recently, I used a function of image compression in my work. I found some tools, but there were not many good choices. Finally, I chose one called jdeli, but unfortunately, the efficiency problem remained. Out of necessity, I had to study its source code, but I found that I was completely confused by its algorithm, so I had the idea of implementing a quantization color algorithm myself.

I have found some information, and found three commonly used color processing algorithms:

Popularity Color Algorithm:

The specific algorithm is to first count the frequency of all colors in an image, and then elect the one with the highest frequency256colors as the color palette of the image, and then traverse all the pixels of the image again, find the closest color in the palette for each pixel (here I use variance as the method), and write it back to the image. The implementation of this algorithm is relatively simple, but the distortion is quite serious. Some information that appears less frequently in the image but is quite obvious to the human eye will be lost. For example, the high brightness spots in the image, due to their low frequency of occurrence, may not be selected by the algorithm and will be lost.

Median Splitting Algorithm:

I have not studied this algorithm, and those who want to understand it can take a look atThis article, there are introductions to three algorithms.

Octree

This algorithm is the one I finally chose, and its main idea is to convert the RGB color values of the image into binary and distribute them in an octree, for example: (173,234,144)

Converted to binary is (10101101,11101010,10010000), extracting the first digit of R, G, and B to form (111As a child node of the root node, among which111As the index of the root child node array, by analogy, it goes all the way to the last one, and then stores the color component value and its frequency of occurrence on the leaf nodes. See the picture for details.

One of the processing methods that I find quite perplexing is the merging strategy for leaf nodes. The most straightforward method I used here is to find the deepest level node and then merge it, which is a bit simple and rough. There might be better methods, and I also welcome everyone to leave me comments. The image is too large to upload, so I will directly upload the code. The code has not been refactored, so please bear with 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>
 *   Octree implementation
 * </p>
 * 
 *  2015-12-16  guoys created this class function.
 *
 **********************************************************
 * </p>
 */
public class Node{
	private int depth = 0;
	// When it is 0, it is the 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 level 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 original 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.getrNum();
			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 level node
	public 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())); / result.add((byte) (node.getPixels()));
			result.add((byte) (node.getgNum())); / result.add((byte) (node.getPixels()));
			result.add((byte) (node.getbNum())); / result.add((byte) (node.getPixels()));
		}
			for (Node child : node.getChildren()) {
				fillArray(child, result, offset);
			}
		}
	}
}

Poor me, the only two failed courses in college were data structures. The code implementation is just an octree, for a1920*1080 image quantization, the time it takes is roughly450ms, if the level-2That would be roughly10About 0ms.

Alright, let's leave it at that. Before writing, I felt like I had a lot to say, but when I actually wrote it, I didn't know what to say. Please forgive me.

Summary

That's all about the Java simple implementation of octree image processing code example in this article. I hope it will be helpful to everyone. Those who are interested can continue to read other related topics on this site. Welcome to leave a message if there is any deficiency. Thank you for your support to this site!

Declaration: The content of this article is from the network, the copyright belongs to the original author. The content is contributed and uploaded by Internet users spontaneously. This website does not own the copyright, does not undergo manual editing, and does not assume relevant legal liability. If you find any content suspected of copyright infringement, please send an email to notice#w3Please report any violations by sending an email to codebox.com (replace # with @ when sending an email), and provide relevant evidence. Once verified, this site will immediately delete the content suspected of infringement.