001/* 002Copyright 2006 Jerry Huxtable 003 004Licensed under the Apache License, Version 2.0 (the "License"); 005you may not use this file except in compliance with the License. 006You may obtain a copy of the License at 007 008 http://www.apache.org/licenses/LICENSE-2.0 009 010Unless required by applicable law or agreed to in writing, software 011distributed under the License is distributed on an "AS IS" BASIS, 012WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013See the License for the specific language governing permissions and 014limitations under the License. 015*/ 016 017package com.jhlabs.image; 018 019import java.awt.*; 020import java.awt.image.*; 021 022/** 023 * A filter which reduces a binary image to a skeleton. 024 * 025 * Based on an algorithm by Zhang and Suen (CACM, March 1984, 236-239). 026 */ 027public class SkeletonFilter extends BinaryFilter { 028 029 private final static byte[] skeletonTable = { 030 0, 0, 0, 1, 0, 0, 1, 3, 0, 0, 3, 1, 1, 0, 1, 3, 031 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2, 0, 3, 0, 3, 3, 032 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 033 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 2, 2, 034 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 035 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 036 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 037 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 3, 0, 2, 0, 038 0, 1, 3, 1, 0, 0, 1, 3, 0, 0, 0, 0, 0, 0, 0, 1, 039 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 040 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 041 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 042 2, 3, 1, 3, 0, 0, 1, 3, 0, 0, 0, 0, 0, 0, 0, 1, 043 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 044 2, 3, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 045 3, 3, 0, 1, 0, 0, 0, 0, 2, 2, 0, 0, 2, 0, 0, 0 046 }; 047 048 public SkeletonFilter() { 049 newColor = 0xffffffff; 050 } 051 052 protected int[] filterPixels( int width, int height, int[] inPixels, Rectangle transformedSpace ) { 053 int[] outPixels = new int[width * height]; 054 055 int count = 0; 056 int black = 0xff000000; 057 int white = 0xffffffff; 058 for (int i = 0; i < iterations; i++) { 059 count = 0; 060 for (int pass = 0; pass < 2; pass++) { 061 for (int y = 1; y < height-1; y++) { 062 int offset = y*width+1; 063 for (int x = 1; x < width-1; x++) { 064 int pixel = inPixels[offset]; 065 if (pixel == black) { 066 int tableIndex = 0; 067 068 if (inPixels[offset-width-1] == black) 069 tableIndex |= 1; 070 if (inPixels[offset-width] == black) 071 tableIndex |= 2; 072 if (inPixels[offset-width+1] == black) 073 tableIndex |= 4; 074 if (inPixels[offset+1] == black) 075 tableIndex |= 8; 076 if (inPixels[offset+width+1] == black) 077 tableIndex |= 16; 078 if (inPixels[offset+width] == black) 079 tableIndex |= 32; 080 if (inPixels[offset+width-1] == black) 081 tableIndex |= 64; 082 if (inPixels[offset-1] == black) 083 tableIndex |= 128; 084 int code = skeletonTable[tableIndex]; 085 if (pass == 1) { 086 if (code == 2 || code == 3) { 087 if (colormap != null) 088 pixel = colormap.getColor((float)i/iterations); 089 else 090 pixel = newColor; 091 count++; 092 } 093 } else { 094 if (code == 1 || code == 3) { 095 if (colormap != null) 096 pixel = colormap.getColor((float)i/iterations); 097 else 098 pixel = newColor; 099 count++; 100 } 101 } 102 } 103 outPixels[offset++] = pixel; 104 } 105 } 106 if (pass == 0) { 107 inPixels = outPixels; 108 outPixels = new int[width * height]; 109 } 110 } 111 if (count == 0) 112 break; 113 } 114 return outPixels; 115 } 116 117 public String toString() { 118 return "Binary/Skeletonize..."; 119 } 120 121} 122