图文精华

About云-梭伦科技»专题 › 技术学习(版主发帖区) › 面试区 › 58同城电话号码识别核心算法
分享

58同城电话号码识别核心算法

pig2 发表于 2014-7-11 22:14:33 [显示全部楼层] 回帖奖励 阅读模式 关闭右栏 2 26191
About云VIP帮助找工作和提升
算法描述
基于要识别的图像生成01二维数组pixarr
将所有的模板读入内存
将所有的特征模板读入内存
将pixarr扫描一遍，去掉孤立点。(孤立点就是指其附近都是0的1点)
找到首次出现1的那一行，记为top，以后就在(top--->top+18)行的范围内识别
row=top  col=0
while(true)
  while(col列没出现1&&col<width)
    col++
  if(col==width)
   break
  以(top,col)为起点，沿着右和下的方向匹配每一个模板，找到吻合率最大的那个模板template0
  那么这块区域所代表的字符就应该是模板template0对应的字符
  if(该字符为'-'并且匹配率不等于1)
     表明匹配有误，往后倒退一列，基于特征模板进行匹配，为保险起见，最多只扫描三列
     将当前得到的字符修改为基于特征模板匹配得到的字符
     记录下该字符
     清理当前区域，为下一步迭代做准备
  else
     记录下该字符
     width0=模板template0的宽度
     以(top,col)为起点，沿着右和下的方向对比模板template0，将template0对应位置处的1置为0
     在(top,col)--->(top+18,col+width0-1)rectangle范围内以深度优先搜寻的方式递归遍历，每次找到一块连通区域，考察该区域
           如果该区域的最右边不超过rectangle右边框，把该区域所有1置为0


ShibiesimpleGraphical.java

  1. package zhanlianyzm;

  2. 

  3. import java.awt.image.BufferedImage;

  4. import java.io.File;

  5. import java.io.IOException;

  6. 

  7. import javax.imageio.ImageIO;

  8. 

  9. public class ShibiesimpleGraphical {

  10.         static int[][] pixarr = null;

  11.         static boolean[][] vistedarr = null;

  12.         static int[] dx = new int[8], dy = new int[8];// 方向数组

  13.         static {

  14.                 dx[0] = 0;

  15.                 dy[0] = -1;

  16.                 dx[1] = -1;

  17.                 dy[1] = -1;

  18.                 dx[2] = -1;

  19.                 dy[2] = 0;

  20.                 dx[3] = -1;

  21.                 dy[3] = 1;

  22.                 dx[4] = 0;

  23.                 dy[4] = 1;

  24.                 dx[5] = 1;

  25.                 dy[5] = 1;

  26.                 dx[6] = 1;

  27.                 dy[6] = 0;

  28.                 dx[7] = 1;

  29.                 dy[7] = -1;

  30.         }

  31. 

  32.         static void resetvistedarr() {

  33.                 for (int row = 0; row < vistedarr.length; row++)

  34.                         for (int col = 0; col < vistedarr[0].length; col++)

  35.                                 vistedarr[row][col] = false;

  36.         }

  37. 

  38.         static void makematrix(String imgfile) {

  39.                 int plex = -1;

  40.                 try {

  41.                         BufferedImage img = ImageIO.read(new File(imgfile));

  42.                         int width = img.getWidth(null);

  43.                         int height = img.getHeight(null);

  44.                         pixarr = new int[height][width];

  45.                         System.out.println("width=" + width + " height=" + height);

  46.                         for (int y = 0; y < height; y++) {

  47.                                 for (int x = 0; x < width; x++) {

  48.                                         plex = img.getRGB(x, y);

  49.                                         if (plex == -1)

  50.                                                 plex = 0;

  51.                                         else

  52.                                                 plex = 1;

  53.                                         pixarr[y][x] = plex;

  54.                                 }

  55.                         }

  56. 

  57.                 } catch (IOException e) {

  58.                         // TODO Auto-generated catch block

  59.                         e.printStackTrace();

  60.                 }

  61.                 vistedarr = new boolean[pixarr.length][pixarr[0].length];

  62.         }

  63. 

  64.         static int getfirst1row(int[][] a) {// 返回首次出现1的行下标,返回-1表示a中没有1

  65.                 for (int i = 0; i < a.length; i++)

  66.                         for (int j = 0; j < a[0].length; j++) {

  67.                                 if (a[i][j] == 1)

  68.                                         return i;

  69.                         }

  70.                 return -1;

  71.         }

  72. 

  73.         static void displaymatrix(int[][] a) {

  74.                 for (int row = 0; row < a.length; row++) {

  75.                         for (int col = 0; col < a[0].length; col++)

  76.                                 System.out.print(a[row][col] + " ");

  77.                         System.out.println();

  78.                 }

  79.         }

  80. 

  81.         public static void shibie(String imgfile) {

  82.                 makematrix(imgfile);// 基于图片生成01二维数组

  83.                 displaymatrix(pixarr);

  84.                 Template[] templatearr = MakeTemplate.maketemplate();// 将所有的模板读入内存,保存在templatearr中

  85.                 int[][] matrix = templatearr[9].getMatrix();

  86.                 // displaymatrix(matrix);

  87.                 Templatefeature[] templatefeaturearr = MakeTemplatefeature

  88.                                 .maketemplatefeature();

  89.                 filteroutlier(pixarr); // 考察pixarr整体范围，过滤孤立点

  90. 

  91.                 int top = getfirst1row(pixarr); // 找到首次出现1的那一行

  92.                 if (top == -1)

  93.                         return;

  94.                 int row = top, col = 0;

  95.                 StringBuilder builder = new StringBuilder();

  96.                 int debug = 0;

  97.                 while (true) {

  98.                         if (debug == 6)

  99.                                 System.out.println();

  100.                         debug++;

  101.             boolean featurematch=false;

  102.                         while (col < pixarr[0].length && !have1(col))

  103.                                 col++;

  104.                         if (col == pixarr[0].length)

  105.                                 break;

  106.                         int max = 0, ps = 0;

  107.                         for (int i = 0; i < templatearr.length; i++) {// 以(top,col)为起点,循环匹配每一个模板

  108.                                 int Consistent_rate = match(top, col, templatearr[i]);

  109.                                 if (Consistent_rate > max) {

  110.                                         max = Consistent_rate;

  111.                                         ps = i;

  112.                                         // System.out.println("max:" + max);

  113.                                 }

  114.                         }

  115.                         System.out.println("ch=" + templatearr[ps].getCh());

  116.                         char ch = templatearr[ps].getCh();

  117.                         if (ch == '-' && max != 100) {

  118.                                 String result = null;

  119.                                 for (int i = 0; i < templatefeaturearr.length; i++) {// 以(top,col-1)为起点,循环匹配每一个特征模板模板

  120.                                         result = featurematch(top, col - 1, templatefeaturearr[i]);// "12,53"

  121.                                         if (result != null) {

  122.                                                 ch = templatefeaturearr[i].getCh();

  123.                                                 int firstfeaturepoint_row = templatefeaturearr[i]

  124.                                                                 .getFeatureps()[0][0];// 0

  125.                                                 int firstfeaturepoint_col = templatefeaturearr[i]

  126.                                                                 .getFeatureps()[0][1];// 5

  127.                                                 int orow = templatefeaturearr[i].getOrow(); // 5

  128.                                                                                                                                         // firstfeaturepoint_row在ch模板中的相对位置

  129.                                                 int ocol = templatefeaturearr[i].getOcol(); // 5

  130.                                                                                                                                         // firstfeaturepoint_col在ch模板中的相对位置

  131.                                                 String[] strarr = result.split("\\,");

  132.                                                 int feature_startrow = Integer.parseInt(strarr[0]);

  133.                                                 int feature_startcol = Integer.parseInt(strarr[1]);

  134.                                                 int template_startrow = feature_startrow

  135.                                                                 + firstfeaturepoint_row - orow;

  136.                                                 int template_startcol = feature_startcol

  137.                                                                 + firstfeaturepoint_col - ocol;

  138.                                                 System.out.println(template_startrow + ","+ template_startcol);

  139.                                                 Template template = null;

  140.                                                 for (int im = 0; im < templatearr.length; im++) { // 寻找ch模板

  141.                                                         template = templatearr[im];

  142.                                                         if (template.getCh() == ch)

  143.                                                                 break;

  144.                                                 }

  145.                                                 int width0=template.getWidth();

  146.                                                 cleared(template_startrow, template_startcol, template.getMatrix(), ch); // 以(top,col)为起点，对比模板template0，将template0对应位置处的1置为0

  147.                                                 filternoise(pixarr, template_startrow, template_startcol, template_startrow + 18, col + width0 - 1); // 扫描局部范围，过滤噪音

  148.                                                 resetvistedarr();

  149.                                                 System.out.println("过滤噪音后=========================================================================");

  150.                                                 displaymatrix(pixarr);

  151.                                                 featurematch=true;

  152.                                                 break;

  153.                                         }//end if (result != null)

  154. 

  155.                                 }//end for(int i = 0

  156.                                 if (result == null)

  157.                                         break;

  158.                         }

  159.                         builder.append(ch);// 当前阶段吻合率最大的模板是templatearr[ps]，记下它所对应的字符

  160.            if(featurematch)

  161.                    continue;

  162.                         int width0 = templatearr[ps].getWidth();

  163. 

  164.                         if (ch == '1')

  165.                                 System.out.println();

  166.                         displaymatrix(pixarr);

  167.                         cleared(top, col, templatearr[ps].getMatrix(), ch); // 以(top,col)为起点，对比模板template0，将template0对应位置处的1置为0

  168.                         System.out.println("=================================================================================");

  169.                         System.out.println();

  170.                         displaymatrix(pixarr);

  171.                         // filteroutlier(pixarr, top, col, top + 18, col + width0 - 1); //

  172.                         // 扫描局部范围，过滤孤立点

  173.                         filternoise(pixarr, top, col, top + 18, col + width0 - 1); // 扫描局部范围，过滤噪音

  174.                         resetvistedarr();

  175.                         System.out.println("过滤噪音后=========================================================================");

  176.                         displaymatrix(pixarr);

  177.                 }

  178.                 System.out.println(builder.toString());

  179.         }

  180. 

  181.         private static String featurematch(int top, int col,

  182.                         Templatefeature templatefeature) {// 按特征模板匹配，如果成功，则返回特征模板矩阵当时所处位置

  183.                 int startcol = col;

  184.                 int[][] pixmatrix = templatefeature.getMatrix();

  185.                 int[][] featureps = templatefeature.getFeatureps();

  186.                 int h = pixmatrix.length;

  187. 

  188.                 for (int x = col; x < col + 2; x++) {// 为保险起见，最多只扫描两列

  189.                         for (int y = top; y <= top + 18 - h; y++) {

  190.                                 if (scanmatch(y, x, pixmatrix, featureps))

  191.                                         return y + "," + x;

  192.                         }

  193.                 }

  194.                 return null;

  195.         }

  196. 

  197.         private static boolean scanmatch(int y, int x, int[][] pixmatrix,

  198.                         int[][] featureps) {// 从(y,x)起对比pixarr和pixmatrix,重点考察featureps所表示的点是否匹配

  199.                 for (int p = 0; p < featureps.length; p++) {

  200.                         int row = featureps[p][0];// 行

  201.                         int col = featureps[p][1];// 列

  202.                         if (pixmatrix[row][col] != pixarr[row + y][col + x])

  203.                                 return false;

  204.                 }

  205.                 return true;

  206.         }

  207. 

  208.         static int localtop = 0, localleft = 0, localbottom = 0, localright = 0;

  209. 

  210.         private static void filternoise(int[][] pixarr, int top, int left,int bottom, int right) {// 扫描局部范围，过滤噪音

  211.                 for (int row = top; row <= bottom; row++)

  212.                         for (int col = left; col <= right; col++) {

  213.                                 if (pixarr[row][col] == 1) {

  214.                                         if (vistedarr[row][col])

  215.                                                 continue;

  216.                                         localtop = row;

  217.                                         localleft = col;

  218.                                         localbottom = row;

  219.                                         localright = col;

  220.                                         int localtop0 = localtop, localleft0 = localleft;

  221.                                         int localbottom0 = localbottom, localright0 = localright;

  222.                                         dfsTraversal(row, col, top, left, bottom);// 以(row,col)点为起点，在该局部范围内，找到一块连通区域

  223.                                         /*

  224.                                          * if(localtop==localtop0&&localleft0==localleft&&localbottom0==localbottom&&localright0==localright)

  225.                                          * continue;

  226.                                          */

  227. 

  228.                                         if (localright <= right) {// 如果该区域的最右边不超过rectangle右边框,把该区域所有1置为0

  229.                                                 for (int y = localtop; y <= localbottom; y++)

  230.                                                         for (int x = localleft; x <= localright; x++)

  231.                                                                 pixarr[y][x] = 0;

  232.                                         }

  233.                                 }

  234.                         }

  235. 

  236.         }

  237. 

  238.         private static void dfsTraversal(int row, int col, int top, int left,

  239.                         int bottom) {// 以(row,col)点为起点，深度优先遍历找到一块连通区域

  240.                 for (int i = 0; i < dx.length; i++) {// 分别往5个方向测探,上边的方向之前已经扫描处理过了，可以不必再考虑

  241.                         int row_1 = row + dy[i];

  242.                         int col_1 = col + dx[i];

  243.                         // if(row_1 <top || row > bottom || col_1 < left)

  244.                         // continue;

  245.                         if (vistedarr[row_1][col_1])

  246.                                 continue;

  247.                         vistedarr[row_1][col_1] = true;

  248.                         if (pixarr[row_1][col_1] == 1) {

  249.                                 if (row_1 > localbottom)

  250.                                         localbottom = row_1;

  251.                                 if (col_1 < localleft)

  252.                                         localleft = col_1;

  253.                                 if (col_1 > localright)

  254.                                         localright = col_1;

  255.                                 dfsTraversal(row_1, col_1, top, left, bottom);

  256.                         }

  257. 

  258.                 }

  259. 

  260.         }

  261. 

  262.         private static void filteroutlier(int[][] pixarr) {

  263.                 filteroutlier(pixarr, 0, 0, pixarr.length - 1, pixarr[0].length - 1);

  264. 

  265.         }

  266. 

  267.         private static void filteroutlier(int[][] pixarr, int top, int left,

  268.                         int bottom, int right) {// 扫描pixarr局部，去掉孤立点

  269.                 for (int row = top; row <= bottom; row++)

  270.                         for (int col = left; col <= right; col++) {

  271.                                 changepoint(pixarr, top, left, bottom, right, row, col);

  272. 

  273.                         }

  274. 

  275.         }

  276. 

  277.         private static void changepoint(int[][] pixarr, int top, int left,

  278.                         int bottom, int right, int row, int col) {

  279.                 if (pixarr[row][col] == 0)

  280.                         return;

  281.                 boolean have1 = false;

  282.                 for (int i = 0; i < dx.length; i++) {// 测探八个方向存在1否？

  283.                         int row_1 = row + dy[i];

  284.                         int col_1 = col + dx[i];

  285.                         if (row_1 >= top && row <= bottom && col_1 >= left

  286.                                         && col_1 <= right) {

  287.                                 if (pixarr[row_1][col_1] == 1) {

  288.                                         have1 = true;

  289.                                         break;

  290.                                 }

  291.                         }

  292.                 }

  293.                 if (!have1)

  294.                         pixarr[row][col] = 0;

  295.         }

  296. 

  297.         private static void cleared(int top, int left, int[][] matrix, char ch) {// 以(top,left)为起点，对比矩阵matrix，将matrix为1的点与pixarr对应位置处的数值置为0

  298.                 for (int row = 0; row < matrix.length; row++)

  299.                         for (int col = 0; col < matrix[0].length; col++) {

  300.                                 if (ch == '8'

  301.                                                 && ((row == 18 && col == 7) || (row == 12 && col == 9)))

  302.                                         System.out.println();

  303.                                 if (matrix[row][col] == 1)

  304.                                         pixarr[row + top][col + left] = 0;

  305.                         }

  306. 

  307.         }

  308. 

  309.         private static int match(int top, int left, Template template) {// 以(top,left)为起点,匹配模板template,返回吻合率

  310.                 int[][] matrix = template.getMatrix();

  311.                 double sum = 0.0;

  312.                 for (int row = 0; row < matrix.length; row++)

  313.                         for (int col = 0; col < matrix[0].length; col++) {

  314.                                 if (matrix[row][col] == pixarr[top + row][left + col])

  315.                                         sum++;

  316.                         }

  317.                 // System.out.println("sum="+sum);

  318.                 return (int) (sum * 100 / (matrix.length * matrix[0].length));

  319.         }

  320. 

  321.         private static boolean have1(int col) {//

  322.                 int sum = 0;

  323.                 int firstrow = 0;

  324.                 for (int row = 0; row < pixarr.length; row++)

  325.                         if (pixarr[row][col] == 1) { // return true;

  326.                                 if (firstrow == 0)

  327.                                         firstrow = row;

  328.                                 sum++;

  329.                         }

  330.                 if (sum == 0)

  331.                         return false;

  332.                 else {

  333.                         if (sum == 1 && firstrow > 9) {

  334.                                 pixarr[firstrow][col] = 0;

  335.                                 return false;

  336.                         }

  337.                         return true;

  338.                 }

  339.         }

  340. 

  341.         public static void main(String[] args) {

  342.                 String imgfile = "D:/58同城/8.gif";

  343.                 shibie(imgfile);

  344. 

  345.         }

  346. 

  347. }

复制代码






关注公众号，获取大数据、人工智能20套、区块链资源5阶段等资源，随时更新，获取最新技术资源
回复

使用道具 举报

自定义广告语

已有(2)人评论

跳转到指定楼层
正序浏览
hanchi 发表于 2015-3-7 23:32:42
楼主，您有这道题的数据吗？
回复

使用道具 举报

ainubis 发表于 2015-3-28 01:04:28
不错。谢谢分享。
回复

使用道具 举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发表新帖
pig2

超级版主

关注

  • 2329

    主题

  • 3339

    帖子

  • 1972

    粉丝

欢迎大家如about云官方2群322273151，更新咨询，更新资源，随时关注
TA的主题
关闭

推荐上一条 /2 下一条

关于我们· 联系我们· 加入我们· 小黑屋· 合作伙伴   

Copyright © 2001-2024 About云-梭伦科技 Powered by Discuz! X3.4 Licensed Discuz Team.

简书 / Smrz 京ICP备2020039040号 Wxb 简书网举报电话：021-34700000