精华内容
下载资源
问答
  • 从大量数据中通过字符串的匹配查找数据的关键是索引,对字符串的精确相等匹配,前缀匹配(like 'x%')和后缀匹配(like '%x')可以使用btree索引,对中缀匹配(like '%x%')和正则表达式匹配就可以用pg_trgm的索引了。...
    pg_trgm是用来做相似度匹配的,在一些情况下也可以拿来代替全文检索做字符匹配。
    从大量数据中通过字符串的匹配查找数据的关键是索引,对字符串的精确相等匹配,前缀匹配(like 'x%')和后缀匹配(like '%x')可以使用btree索引,对中缀匹配(like '%x%')和正则表达式匹配就可以用pg_trgm的索引了。下面用一个例子说明一下。

    1.环境

    CentOS 6.5
    PostgreSQL 9.4.0

    2.测试数据

    没有特意找什么测试数据,正好手头有一份翻译中的PostgreSQL9.3中文手册,就拿它当测试数据了。

    建表

    点击(此处)折叠或打开

    1. create table t1(id serial,c1 text);

    导数据,手册中的每一行作为一条记录。

    点击(此处)折叠或打开

    1. -bash-4.1$ tar xf pg9.3.1.html.tar.gz
    2. -bash-4.1$ find html -name *.html -exec cat {} \;|iconv -f GBK -t UTF8|sed 's\[\]\\g'|psql -p 5433 testdb -c "copy t1(c1) from stdin"
    注)翻译中的PostgreSQL9.3中文手册(pg9.3.1.html.tar.gz)可从以下位置下载:http://58.58.27.50:8079/doc/doc/postdoc_download.php

    查看数据大小

    点击(此处)折叠或打开

    1. testdb=# select count(*) from t1;
    2.  count 
    3. --------
    4.  702476
    5. (row)
    6. testdb=# select pg_table_size('t1');
    7.  pg_table_size 
    8. ---------------
    9.       37519360
    10. (row)
    11. testdb=# select * from t1 where c1 like '%存储过程%';
    12.    id | c1 
    13. --------+------------------------------------------------------------------------------------------------------------------------
    14.  132113 | >有些其它数据库系统定义动态的数据库规则。这些通常是存储过程和触发器,
    15.  132119 | >规则系统(更准确地说是查询重写规则系统)是和存储过程和触发器完全不同的东西。
    16.  260249 | >如果你的需求超过这些条件表达式的能力,你可能会希望用一种更富表现力的编程语言写一个存储过程。</P
    17.  473911 | >下面是一个用 C 写的存储过程语言处理器的模版:
    18.  562282 | >请注意开销估计函数必须用 C 写,而不能用 SQL 或者任何可用的存储过程语言,因为它们必须访问规划器/优化器的内部数据结构。
    19.  566142 | >登记编程语言,你可以用这些语言或接口写函数或者存储过程。
    20. (rows)

    3.模糊匹配测试

    3.1 通过全表扫描做模糊匹配

    点击(此处)折叠或打开

    1. testdb=# explain (analyze,buffers) select * from t1 where c1 like '%存储过程%';
    2.                                              QUERY PLAN 
    3. -----------------------------------------------------------------------------------------------------
    4.  Seq Scan on t1 (cost=0.00..13354.95 rows=30 width=21) (actual time=34.920..186.967 rows=6 loops=1)
    5.    Filter: (c1 ~~ '%存储过程%'::text)
    6.    Rows Removed by Filter: 702470
    7.    Buffers: shared hit=4574
    8.  Planning time: 0.121 ms
    9.  Execution time: 187.003 ms
    10. (rows)

    11. Time: 187.635 ms

    3.2 使用pg_trgm的gist索引扫描做模糊匹配

    点击(此处)折叠或打开

    1. testdb=# create extension pg_trgm;
    2. CREATE EXTENSION
    3. testdb=# create index t1_c1_gist_idx on t1 using gist(c1 gist_trgm_ops);
    4. LOG: checkpoints are occurring too frequently (22 seconds apart)
    5. HINT: Consider increasing the configuration parameter "checkpoint_segments".
    6. LOG: checkpoints are occurring too frequently (5 seconds apart)
    7. HINT: Consider increasing the configuration parameter "checkpoint_segments".
    8. CREATE INDEX
    9. Time: 15988.394 ms

    10. testdb=# select pg_relation_size('t1_c1_gist_idx');
    11.  pg_relation_size 
    12. ------------------
    13.          55214080
    14. (row)

    15. Time: 0.461 ms

    16. testdb=# explain (analyze,buffers) select * from t1 where c1 like '%存储过程%';
    17.                                                         QUERY PLAN 
    18. --------------------------------------------------------------------------------------------------------------------------
    19.  Bitmap Heap Scan on t1 (cost=4.52..117.60 rows=30 width=21) (actual time=71.292..71.303 rows=6 loops=1)
    20.    Recheck Cond: (c1 ~~ '%存储过程%'::text)
    21.    Heap Blocks: exact=5
    22.    Buffers: shared hit=5249
    23.    -> Bitmap Index Scan on t1_c1_gist_idx (cost=0.00..4.51 rows=30 width=0) (actual time=71.268..71.268 rows=6 loops=1)
    24.          Index Cond: (c1 ~~ '%存储过程%'::text)
    25.          Buffers: shared hit=5244
    26.  Planning time: 0.146 ms
    27.  Execution time: 71.344 ms
    28. (rows)

    29. Time: 71.976 ms

    性能提升了1倍多(187.635/71.976),可以说效果并不明显,尤其需要注意的是索引太大,而且扫描的索引数据块太多(5244),几乎把整个索引都扫了一遍。而匹配的记录其实只有6条。下面看看gin索引的效果。

    3.3 使用pg_trgm的gin索引扫描做模糊匹配

    点击(此处)折叠或打开

    1. testdb=# drop index t1_c1_gist_idx;
    2. DROP INDEX
    3. Time: 22.827 ms
    4. testdb=# create index t1_c1_gin_idx on t1 using gin(c1 gin_trgm_ops);
    5. CREATE INDEX
    6. Time: 4995.957 ms
    7. testdb=# select pg_relation_size('t1_c1_gin_idx');
    8.  pg_relation_size 
    9. ------------------
    10.          29663232
    11. (row)

    12. Time: 0.670 ms

    13. testdb=# explain (analyze,buffers) select * from t1 where c1 like '%存储过程%';
    14.                                                        QUERY PLAN 
    15. ------------------------------------------------------------------------------------------------------------------------
    16.  Bitmap Heap Scan on t1 (cost=28.23..141.32 rows=30 width=21) (actual time=0.115..0.135 rows=6 loops=1)
    17.    Recheck Cond: (c1 ~~ '%存储过程%'::text)
    18.    Heap Blocks: exact=5
    19.    Buffers: shared hit=12
    20.    -> Bitmap Index Scan on t1_c1_gin_idx (cost=0.00..28.22 rows=30 width=0) (actual time=0.093..0.093 rows=6 loops=1)
    21.          Index Cond: (c1 ~~ '%存储过程%'::text)
    22.          Buffers: shared hit=7
    23.  Planning time: 1.348 ms
    24.  Execution time: 0.265 ms
    25. (rows)

    26. Time: 2.721 ms

    gin_trgm索引的效果好多了。性能提升了69倍(187.635/2.721)
    很妙的是除了like,gin_trgm索引还可以用在正则表达式匹配上。比如,查出所有不是出现在句子结尾的“存储过程”。

    点击(此处)折叠或打开

    1. testdb=# select * from t1 where c1 ~ '存储过程[^。]';
    2.    id | c1 
    3. --------+------------------------------------------------------------------------------------------------------------------------
    4.  132113 | >有些其它数据库系统定义动态的数据库规则。这些通常是存储过程和触发器,
    5.  132119 | >规则系统(更准确地说是查询重写规则系统)是和存储过程和触发器完全不同的东西。
    6.  473911 | >下面是一个用 C 写的存储过程语言处理器的模版:
    7.  562282 | >请注意开销估计函数必须用 C 写,而不能用 SQL 或者任何可用的存储过程语言,因为它们必须访问规划器/优化器的内部数据结构。
    8. (rows)

    9. Time: 0.978 ms
    10. testdb=# explain (analyze,buffers) select * from t1 where c1 ~ '存储过程[^。]';
    11.                                                        QUERY PLAN 
    12. ------------------------------------------------------------------------------------------------------------------------
    13.  Bitmap Heap Scan on t1 (cost=28.23..141.32 rows=30 width=21) (actual time=0.141..0.172 rows=4 loops=1)
    14.    Recheck Cond: (c1 ~ '存储过程[^。]'::text)
    15.    Rows Removed by Index Recheck: 2
    16.    Heap Blocks: exact=5
    17.    Buffers: shared hit=12
    18.    -> Bitmap Index Scan on t1_c1_gin_idx (cost=0.00..28.22 rows=30 width=0) (actual time=0.120..0.120 rows=6 loops=1)
    19.          Index Cond: (c1 ~ '存储过程[^。]'::text)
    20.          Buffers: shared hit=7
    21.  Planning time: 0.441 ms
    22.  Execution time: 0.281 ms
    23. (10 rows)

    24. Time: 1.261 ms

    3.4 对比一下使用zhparser插件的全文检索的效果

    zhparser的使用方法参考前一篇博客《PostgreSQL的全文检索插件zhparser的中文分词效果》。
    libscws的分词模式设成短词+重要单字的复合分词。

    点击(此处)折叠或打开

    1. testdb=# create index t1_c1_fts_idx on t1 using gin(to_tsvector('testzhcfg',c1));
    2. CREATE INDEX
    3. Time: 4523.277 ms
    4. testdb=# select pg_relation_size('t1_c1_fts_idx');
    5.  pg_relation_size 
    6. ------------------
    7.           8765440
    8. (row)

    9. Time: 0.543 ms

    10. testdb=# explain (analyze,buffers) select * from t1 where to_tsvector('testzhcfg',c1) @@ to_tsquery('testzhcfg','存储过程');
    11.                                                              QUERY PLAN 
    12. -------------------------------------------------------------------------------------------------------------------------------------
    13.  Bitmap Heap Scan on t1 (cost=76.00..80.02 rows=1 width=21) (actual time=0.437..0.465 rows=13 loops=1)
    14.    Recheck Cond: (to_tsvector('testzhcfg'::regconfig, c1) @@ '''存储'' & ''存'' & ''储'' & ''过程'' & ''过'' & ''程'''::tsquery)
    15.    Heap Blocks: exact=12
    16.    Buffers: shared hit=35
    17.    -> Bitmap Index Scan on t1_c1_fts_idx (cost=0.00..76.00 rows=1 width=0) (actual time=0.424..0.424 rows=13 loops=1)
    18.          Index Cond: (to_tsvector('testzhcfg'::regconfig, c1) @@ '''存储'' & ''存'' & ''储'' & ''过程'' & ''过'' & ''程'''::tsquery)
    19.          Buffers: shared hit=23
    20.  Planning time: 0.192 ms
    21.  Execution time: 0.506 ms
    22. (rows)

    23. Time: 1.486 ms

    全文检索果然索引更小,搜索更快(在我的测试条件下,性能其实相差不大,而且每次测试结果都不一样;随着数据量的增大中文分词会更有性能优势)。但是pg_trgm贵在不需要涉及中文分词的那么多不确定性。比如上面的例子,用全文检索搜出来的就是13条记录,而不是6条。因为用于分词的词典里没有“存储过程”这个词,“存储过程”被拆成了“存储”和“过程”两个词,只要记录里有这两个词,不管是否连在一起,都被认为匹配。如下:

    点击(此处)折叠或打开

    1. testdb=# select * from t1 where to_tsvector('testzhcfg',c1) @@ to_tsquery('testzhcfg','存储过程');
    2.    id | c1 
    3. --------+------------------------------------------------------------------------------------------------------------------------
    4.  120827 | 在描述这些变化的日志记录刷新到永久存储器之后。如果我们遵循这个过程,
    5.  132113 | >有些其它数据库系统定义动态的数据库规则。这些通常是存储过程和触发器,
    6.  132119 | >规则系统(更准确地说是查询重写规则系统)是和存储过程和触发器完全不同的东西。
    7.  260249 | >如果你的需求超过这些条件表达式的能力,你可能会希望用一种更富表现力的编程语言写一个存储过程。</P
    8.  263598 | >表存储关于函数(或过程)的信息。参阅<A
    9.  320664 | 然后在使用过程中大概需要在一个平面文本文件里存放同等数据量五倍的空间存储数据。
    10.  376663 | 实现节点将数据保存在存储器中,因为它被读取,然后从存储器每个后续过程中返回每一个数据。</P
    11.  436633 | >存储有关与访问方法操作符族相关联的支持过程的信息。
    12.  455406 | >表为过程语言存储<SPAN
    13.  473911 | >下面是一个用 C 写的存储过程语言处理器的模版:
    14.  552426 | 我们加速了存储器分配,优化,表联合以及行传输过程。</P
    15.  562282 | >请注意开销估计函数必须用 C 写,而不能用 SQL 或者任何可用的存储过程语言,因为它们必须访问规划器/优化器的内部数据结构。
    16.  566142 | >登记编程语言,你可以用这些语言或接口写函数或者存储过程。
    17. (13 rows)
    pg_trgm本质上虽然也相当于一种特殊的分词方法,但是pg_trgm索引只有用来做初次筛选,最终结果还有recheck来把关,所以结果是确定的。

    4 pg_trgm做索引的注意事项

    4.1 不支持小于3个字的匹配条件

    pg_trgm的工作原理是把字符串切成N个3元组,然后对这些3元组做匹配,所以如果作为查询条件的字符串小于3个字符它就罢工了。
    对pg_trgm的gist索引,走的还是索引扫描。但是悲剧的是,索引没有起到任何筛选的作用,702476条记录一个不落全给提出来了,这样还不如直接全表扫描呢。

    点击(此处)折叠或打开

    1. testdb=# explain analyze select * from t1 where c1 like '%存储%';
    2.                                                          QUERY PLAN 
    3. ----------------------------------------------------------------------------------------------------------------------------
    4.  Bitmap Heap Scan on t1 (cost=4.52..117.60 rows=30 width=21) (actual time=106.022..221.730 rows=640 loops=1)
    5.    Recheck Cond: (c1 ~~ '%存储%'::text)
    6.    Rows Removed by Index Recheck: 701836
    7.    Heap Blocks: exact=4574
    8.    -> Bitmap Index Scan on t1_c1_gist_idx (cost=0.00..4.51 rows=30 width=0) (actual time=105.184..105.184 rows=702476 loops=1)
    9.          Index Cond: (c1 ~~ '%存储%'::text)
    10.  Planning time: 0.102 ms
    11.  Execution time: 221.855 ms
    12. (rows)

    13. Time: 222.311 ms

    对pg_trgm的gin索引,优化器看出来这时候走索引是白费功夫,所以就直接走的全表扫描。

    点击(此处)折叠或打开

    1. testdb=# explain analyze select * from t1 where c1 like '%存储%';
    2. ------------------------------------------------------------------------------------------------------
    3.  Seq Scan on t1 (cost=0.00..13354.95 rows=30 width=21) (actual time=0.541..207.416 rows=640 loops=1)
    4.    Filter: (c1 ~~ '%存储%'::text)
    5.    Rows Removed by Filter: 701836
    6.    Buffers: shared hit=4574
    7.  Planning time: 0.183 ms
    8.  Execution time: 207.608 ms
    9. (rows)

    10. Time: 208.288 ms

    4.2 数据库的LC_CTYPE需要设置为中文区域

    在你的环境下,可能会发现pg_trgm不支持中文,中文字符都被截掉了。就像这样:

    点击(此处)折叠或打开

    1. utf8_C=# select show_trgm('存储过程');
    2.  show_trgm 
    3. -----------
    4.  {}
    5. (row)

    正确的应该是这样:

    点击(此处)折叠或打开

    1. testdb=# select show_trgm('存储过程');
    2.                    show_trgm 
    3. ------------------------------------------------
    4.  {0x9acb56,0xa61c30,0xaad876,0xd07577,0x5e9b60}
    5. (row)

    这是因为,pg_trgm调用了系统的isalpha()函数判断字符,而isalpha()依赖于LC_CTYPE,如果数据库的LC_CTYPE是C,isalpha()就不能识别中文。所以需要把数据库的LC_CTYPE设成zh_CN。

    trgm.h:

    点击(此处)折叠或打开

    1. #define t_isdigit(x)    isdigit(TOUCHAR(x))
    2. ...
    3. #define t_isalpha(x)    isalpha(TOUCHAR(x))
    4. ...
    5. #define ISWORDCHR(c)    (t_isalpha(c) || t_isdigit(c))
    trgm_opt.c:

    点击(此处)折叠或打开

    1. /*
    2.  * Finds first word in string, returns pointer to the word,
    3.  * endword points to the character after word
    4.  */
    5. static char *
    6. find_word(char *str, int lenstr, char **endword, int *charlen)
    7. {
    8.     char     *beginword = str;

    9.     while (beginword - str < lenstr && !ISWORDCHR(beginword))
    10.         beginword += pg_mblen(beginword);

    11.     if (beginword - str >= lenstr)
    12.         return NULL;

    13.     *endword = beginword;
    14.     *charlen = 0;
    15.     while (*endword - str < lenstr && ISWORDCHR(*endword))
    16.     {
    17.         *endword += pg_mblen(*endword);
    18.         (*charlen)++;
    19.     }

    20.     return beginword;
    21. }

    数据库的LC_CTYPE:

    点击(此处)折叠或打开

    1. testdb=#  \l
                                       List of databases
         Name    |  Owner   | Encoding |  Collate   |   Ctype    |   Access privileges   
      -----------+----------+----------+------------+------------+-----------------------
       postgres  | postgres | UTF8     | zh_CN.utf8 | zh_CN.utf8 | 
       template0 | postgres | UTF8     | zh_CN.utf8 | zh_CN.utf8 | =c/postgres          +
                 |          |          |            |            | postgres=CTc/postgres
       template1 | postgres | UTF8     | zh_CN.utf8 | zh_CN.utf8 | postgres=CTc/postgres+
                 |          |          |            |            | =c/postgres
       testdb    | postgres | UTF8     | zh_CN.utf8 | zh_CN.utf8 | 
       utf8_C    | postgres | UTF8     | C          | C          | 
      (5 rows)

    5.参考

    http://blog.2ndquadrant.com/text-search-strategies-in-postgresql/
    http://www.postgresql.org/docs/9.4/static/pgtrgm.html 
    http://my.oschina.net/Kenyon/blog/366505
    展开全文
  • Sed在匹配行前后加入一

    千次阅读 2016-11-10 21:31:44
    a 追加内容 sed ‘/匹配词/a\要加入的内容’ example.file(将内容追加到匹配的目标的下一位置) i 插入内容 sed ‘/匹配词/i\要加入的内容’ example.file 将内容插入到匹配目标的上一位置) 示例: ...
    a 追加内容 sed ‘/匹配词/a\要加入的内容’ example.file(将内容追加到匹配的目标行的下一行位置)

    i 插入内容 sed ‘/匹配词/i\要加入的内容’ example.file 将内容插入到匹配的行目标的上一行位置)
    示例:
    #我要把文件的包含“chengyongxu.com”这个关键词的行前或行后加入一行,内容为“allow chengyongxu.cn”

    1 #行前加
    2 sed -i '/allow chengyongxu.com/i\allow chengyongxu.cn' the.conf.file
    3 #行前后
    4 sed -i '/allow chengyongxu.com/a\allow chengyongxu.cn' the.conf.file


    ---------------------------------------------------
    1、删除指定行的上一行
    sed -i -e :a -e '$!N;s/.*\n\(.*ServerName abc.com\)/\1/;ta' -e 'P;D' $file
    2、删除指定字符串之间的内容
    sed -i '/ServerName abc.com/,/\/VirtualHost/d' $filehttp://www.linuxso.com/shell/17542.html

    展开全文
  • 双目测距()--匹配算法对比

    万次阅读 2016-07-26 13:21:41
    参考:... 三种匹配算法比较 BM算法: 该算法代码: view plaincopy to clipboardprint? CvStereoBMState *BMState = cvCreateStereoBMState();  int SADWindowSize=15;  BMState-...

    参考:http://www.cnblogs.com/polly333/p/5130375.html

    三种匹配算法比较

    BM算法:

    该算法代码:

    view plaincopy to clipboardprint?

    1. CvStereoBMState *BMState = cvCreateStereoBMState();  
    2. int SADWindowSize=15;   
    3. BMState->SADWindowSize = SADWindowSize > 0 ? SADWindowSize : 9;  
    4. BMState->minDisparity = 0;  
    5. BMState->numberOfDisparities = 32;  
    6. BMState->textureThreshold = 10;  
    7. BMState->uniquenessRatio = 15;  
    8. BMState->speckleWindowSize = 100;  
    9. BMState->speckleRange = 32;  
    10. BMState->disp12MaxDiff = 1;  
    11. cvFindStereoCorrespondenceBM( left, right, left_disp_,BMState);  
    12.    cvNormalize( left_disp_, left_vdisp, 0, 256, CV_MINMAX ); 

     

     

    其中minDisparity是控制匹配搜索的第一个参数,代表了匹配搜苏从哪里开始,numberOfDisparities表示最大搜索视差数uniquenessRatio表示匹配功能函数,这三个参数比较重要,可以根据实验给予参数值。

    该方法速度最快,一副320*240的灰度图匹配时间为31ms,视差图如下。

    clip_image001

    这图是解释BM(bidirectional matching)算法的很好的例子。进行双向匹配,首先通过匹配代价在右图中计算得出匹配点。然后相同的原理及计算在左图中的匹配点。比较找到的左匹配点和源匹配点是否一致,如果你是,则匹配成功。

    image

    第二种方法是SGBM方法这是OpenCV的一种新算法:

    view plaincopy to clipboardprint?

    1. cv::StereoSGBM sgbm;  
    2.         sgbm.preFilterCap = 63;  
    3.         int SADWindowSize=11;   
    4.         int cn = 1;  
    5.         sgbm.SADWindowSize = SADWindowSize > 0 ? SADWindowSize : 3;  
    6.         sgbm.P1 = 4*cn*sgbm.SADWindowSize*sgbm.SADWindowSize;  
    7.         sgbm.P2 = 32*cn*sgbm.SADWindowSize*sgbm.SADWindowSize;  
    8.         sgbm.minDisparity = 0;  
    9.         sgbm.numberOfDisparities = 32;  
    10.         sgbm.uniquenessRatio = 10;  
    11.         sgbm.speckleWindowSize = 100;  
    12.         sgbm.speckleRange = 32;  
    13.         sgbm.disp12MaxDiff = 1;  
    14.  
    15.         sgbm(left , right , left_disp_);  
    16.         sgbm(right, left  , right_disp_); 

     

     

    各参数设置如BM方法,速度比较快,320*240的灰度图匹配时间为78ms,视差效果如下图。

    clip_image002

    第三种为GC方法:

    view plaincopy to clipboardprint?

    1. CvStereoGCState* state = cvCreateStereoGCState( 16, 2 );  
    2. left_disp_  =cvCreateMat( left->height,left->width, CV_32F );  
    3. right_disp_ =cvCreateMat( right->height,right->width,CV_32F );  
    4. cvFindStereoCorrespondenceGC( left, right, left_disp_, right_disp_, state, 0 );  
    5. cvReleaseStereoGCState( &state ); 

     

     

    该方法速度超慢,但效果超好。

    clip_image003

    各方法理论可以参考文献。

    函数解释

    参数注释

     

     

    (1)StereoBMState

    // 预处理滤波参数

    • preFilterType:预处理滤波器的类型,主要是用于降低亮度失真(photometric distortions)、消除噪声和增强纹理等, 有两种可选类型:CV_STEREO_BM_NORMALIZED_RESPONSE(归一化响应) 或者 CV_STEREO_BM_XSOBEL(水平方向Sobel算子,默认类型), 该参数为 int 型;
    • preFilterSize:预处理滤波器窗口大小,容许范围是[5,255],一般应该在 5x5..21x21 之间,参数必须为奇数值, int 型
    • preFilterCap:预处理滤波器的截断值,预处理的输出值仅保留[-preFilterCap, preFilterCap]范围内的值,参数范围:1 - 31(文档中是31,但代码中是 63), int

     

     

    // SAD 参数

    • SADWindowSize:SAD窗口大小,容许范围是[5,255],一般应该在 5x5 至 21x21 之间,参数必须是奇数,int 型
    • minDisparity:最小视差默认值为 0, 可以是负值,int 型
    • numberOfDisparities:视差窗口,即最大视差值与最小视差值之差, 窗口大小必须是 16 的整数倍,int 型

     

     

    // 后处理参数

    • textureThreshold:低纹理区域的判断阈值。如果当前SAD窗口内所有邻居像素点的x导数绝对值之和小于指定阈值,则该窗口对应的像素点的视差值为 0(That is, if the sum of absolute values of x-derivatives computed over SADWindowSize by SADWindowSize pixel neighborhood is smaller than the parameter, no disparity is computed at the pixel),该参数不能为负值,int 型
    • uniquenessRatio:视差唯一性百分比, 视差窗口范围内最低代价是次低代价的(1 + uniquenessRatio/100)倍时,最低代价对应的视差值才是该像素点的视差,否则该像素点的视差为 0 (the minimum margin in percents between the best (minimum) cost function value and the second best value to accept the computed disparity, that is, accept the computed disparity d^ only if SAD(d) >= SAD(d^) x (1 + uniquenessRatio/100.) for any d != d*+/-1 within the search range ),该参数不能为负值,一般5-15左右的值比较合适,int 型
    • speckleWindowSize:检查视差连通区域变化度的窗口大小, 值为 0 时取消 speckle 检查,int 型
    • speckleRange:视差变化阈值,当窗口内视差变化大于阈值时,该窗口内的视差清零,int 型

     

     

    // OpenCV2.1 新增的状态参数

    • roi1, roi2:左右视图的有效像素区域,一般由双目校正阶段的 cvStereoRectify 函数传递,也可以自行设定。一旦在状态参数中设定了 roi1 和 roi2,OpenCV 会通过cvGetValidDisparityROI 函数计算出视差图的有效区域,在有效区域外的视差值将被清零。
    • disp12MaxDiff:左视差图(直接计算得出)和右视差图(通过cvValidateDisparity计算得出)之间的最大容许差异。超过该阈值的视差值将被清零。该参数默认为 -1,即不执行左右视差检查。int 型。注意在程序调试阶段最好保持该值为 -1,以便查看不同视差窗口生成的视差效果。具体请参见《使用OpenGL动态显示双目视觉三维重构效果示例》一文中的讨论。

     

     

    在上述参数中,对视差生成效果影响较大的主要参数是 SADWindowSize、numberOfDisparities 和 uniquenessRatio 三个,一般只需对这三个参数进行调整,其余参数按默认设置即可

    在OpenCV2.1中,BM算法有C和C++ 两种实现模块。

    (2)StereoSGBMState

    SGBM算法的状态参数大部分与BM算法的一致,下面只解释不同的部分:

    • SADWindowSize:SAD窗口大小,容许范围是[1,11],一般应该在 3x3 至 11x11 之间,参数必须是奇数,int 型
    • P1, P2:控制视差变化平滑性的参数。P1、P2的值越大,视差越平滑。P1是相邻像素点视差增/减 1 时的惩罚系数;P2是相邻像素点视差变化值大于1时的惩罚系数。P2必须大于P1。OpenCV2.1提供的例程 stereo_match.cpp 给出了 P1 和 P2 比较合适的数值
    • fullDP:布尔值,当设置为 TRUE 时,运行双通道动态编程算法(full-scale 2-pass dynamic programming algorithm),会占用O(W*H*numDisparities)个字节,对于高分辨率图像将占用较大的内存空间。一般设置为 FALSE

     

     

    注意OpenCV2.1的SGBM算法是用C++ 语言编写的,没有C实现模块。与H. Hirschmuller提出的原算法相比,主要有如下变化:

    1. 算法默认运行单通道DP算法,只用了5个方向,而fullDP使能时则使用8个方向(可能需要占用大量内存)。
    2. 算法在计算匹配代价函数时,采用块匹配方法而非像素匹配(不过SADWindowSize=1时就等于像素匹配了)。
    3. 匹配代价的计算采用BT算法("Depth Discontinuities by Pixel-to-Pixel Stereo" by S. Birchfield and C. Tomasi),并没有实现基于互熵信息的匹配代价计算。
    4. 增加了一些BM算法中的预处理和后处理程序。

     

     

     

    (3)StereoGCState

    GC算法的状态参数只有两个:numberOfDisparities 和 maxIters ,并且只能通过 cvCreateStereoGCState 在创建算法状态结构体时一次性确定,不能在循环中更新状态信息。GC算法并不是一种实时算法,但可以得到物体轮廓清晰准确的视差图,适用于静态环境物体的深度重构。

    注意GC算法只能在C语言模式下运行,并且不能对视差图进行预先的边界延拓,左右视图和左右视差矩阵的大小必须一致。

    原理解释

    目前立体匹配算法是计算机视觉中的一个难点和热点,算法很多,但是一般的步骤是:

     

    A、匹配代价计算

    匹配代价计算是整个立体匹配算法的基础,实际是对不同视差下进行灰度相似性测量。常见的方法有灰度差的平方SD(squared intensity differences),灰度差的绝对值AD(absolute intensity differences)等。另外,在求原始匹配代价时可以设定一个上限值,来减弱叠加过程中的误匹配的影响。以AD法求匹配代价为例,可用下式进行计算,其中T为设定的阈值。

     

    这就是在参数设置中阈值的作用,在视差图中经常有黑色区域,就是和阈值的设置关。

     

     

    B、 匹配代价叠加

    一般来说,全局算法基于原始匹配代价进行后续算法计算。而区域算法则需要通过窗口叠加来增强匹配代价的可靠性,根据原始匹配代价不同,可分为:

     

    此图是核心算法的解释,就是计算区域内像素差值,可以为单个像素也可以为一定区域内,主要看SAD的窗口大小的设置,同时SAD设置决定误匹配的多少和运算效率问题,所以大小设置一定要很慎重。

     

    C、 视差获取

    对于区域算法来说,在完成匹配代价的叠加以后,视差的获取就很容易了,只需在一定范围内选取叠加匹配代价最优的点(SAD和SSD取最小值,NCC取最大值)作为对应匹配点,如胜者为王算法WTA(Winner-take-all)。而全局算法则直接对原始匹配代价进行处理,一般会先给出一个能量评价函数,然后通过不同的优化算法来求得能量的最小值,同时每个点的视差值也就计算出来了。

     

    D、视差细化(亚像素级)

    大多数立体匹配算法计算出来的视差都是一些离散的特定整数值,可满足一般应用的精度要求。但在一些精度要求比较高的场合,如精确的三维重构中,就需要在初始视差获取后采用一些措施对视差进行细化,如匹配代价的曲线拟合、图像滤波、图像分割等。

    亚像素级的处理就是涉及到BMState参数设置后后续参数的设置了。

    有关立体匹配的介绍和常见匹配算法的比较,推荐大家看看Stefano Mattoccia 的讲义 Stereo Vision: algorithms and applications,190页的ppt,讲解得非常形象详尽。

     

     

     

     

     

    1. opencv2.1和opencv2.0在做stereo vision方面有什么区别了?

    2.1版增强了Stereo Vision方面的功能:

    (1) 新增了 SGBM 立体匹配算法(源自Heiko Hirschmuller的《Stereo Processing by Semi-global Matching and Mutual Information》),可以获得比 BM 算法物体轮廓更清晰的视差图(但低纹理区域容易出现横/斜纹路,在 GCstate->fullDP 选项使能时可消减这种异常纹路,但对应区域视差变为0,且运行速度会有所下降),速度比 BM 稍慢, 352*288的帧处理速度大约是 5 帧/秒;

    (2) 视差效果:BM < SGBM < GC;处理速度:BM > SGBM > GC ;

    (3) BM 算法比2.0版性能有所提升,其状态参数新增了对左右视图感兴趣区域 ROI 的支持(roi1 和 roi2,由stereoRectify函数产生);

    (4) BM 算法和 GC 算法的核心代码改动不大,主要是面向多线程运算方面的(由 OpenMP 转向 Intel TBB);

    (5) cvFindStereoCorrespondenceBM 函数的disparity参数的数据格式新增了 CV_32F 的支持,这种格式的数据给出实际视差,而 2.0 版只支持 CV_16S,需要除以 16.0 才能得到实际的视差数值。

    2. 用于立体匹配的图像可以是彩色的吗?

    在OpenCV2.1中,BM和GC算法只能对8位灰度图像计算视差,SGBM算法则可以处理24位(8bits*3)彩色图像。所以在读入图像时,应该根据采用的算法来处理图像:

    int color_mode = alg == STEREO_SGBM ? 1 : 0;
    //
    // 载入图像
    cvGrabFrame( lfCam );
    cvGrabFrame( riCam );
    frame1 = cvRetrieveFrame( lfCam );
    frame2 = cvRetrieveFrame( riCam );
    if(frame1.empty()) break;
    resize(frame1, img1, img_size, 0, 0);
    resize(frame2, img2, img_size, 0, 0);
    // 选择彩色或灰度格式作为双目匹配的处理图像
    if (!color_mode && cn>1)
    {
    cvtColor(img1, img1gray, CV_BGR2GRAY);
    cvtColor(img2, img2gray, CV_BGR2GRAY);
    img1p = img1gray;
    img2p = img2gray;
    }
    else
    {
    img1p = img1;
    img2p = img2;
    }

    3. 怎样获取与原图像有效像素区域相同的视差图?

    OpenCV2.0及以前的版本中,所获取的视差图总是在左侧和右侧有明显的黑色区域,这些区域没有有效的视差数据。视差图有效像素区域与视差窗口(ndisp,一般取正值且能被16整除)和最小视差值(mindisp,一般取0或负值)相关,视差窗口越大,视差图左侧的黑色区域越大,最小视差值越小,视差图右侧的黑色区域越大。其原因是为了保证参考图像(一般是左视图)的像素点能在目标图像(右视图)中按照设定的视差匹配窗口匹配对应点,OpenCV 只从参考图像的第 (ndisp - 1 + mindisp) 列开始向右计算视差,第 0 列到第 (ndisp - 1 + mindisp) 列的区域视差统一设置为 (mindisp - 1) *16;视差计算到第 width + mindisp 列时停止,余下的右侧区域视差值也统一设置为 (mindisp - 1) *16。 

     static const int DISPARITY_SHIFT = 4;
    …
     int ndisp = state->numberOfDisparities;
        int mindisp = state->minDisparity;
         int lofs = MAX(ndisp - 1 + mindisp, 0);
        int rofs = -MIN(ndisp - 1 + mindisp, 0);
         int width = left->cols, height = left->rows;
        int width1 = width - rofs - ndisp + 1;
         short FILTERED = (short)((mindisp - 1) << DISPARITY_SHIFT);
       initialize the left and right borders of the disparity map
         for( y = 0; y < height; y++ )
        {
            for( x = 0; x < lofs; x++ )
                 dptr[y*dstep + x] = FILTERED;
             for( x = lofs + width1; x < width; x++ )
                 dptr[y*dstep + x] = FILTERED;
         }
         dptr += lofs;
        for( x = 0; x < width1; x++, dptr++ )
    
    

     

     

    这样的设置很明显是不符合实际应用的需求的,它相当于把摄像头的视场范围缩窄了。因此,OpenCV2.1 做了明显的改进,不再要求左右视图和视差图的大小(size)一致,允许对视差图进行左右边界延拓,这样,虽然计算视差时还是按上面的代码思路来处理左右边界,但是视差图的边界得到延拓后,有效视差的范围就能够与对应视图完全对应。具体的实现代码范例如下:

    //
    // 对左右视图的左边进行边界延拓,以获取与原始视图相同大小的有效视差区域
    copyMakeBorder(img1r, img1b, 0, 0, m_nMaxDisp, 0, IPL_BORDER_REPLICATE);
    copyMakeBorder(img2r, img2b, 0, 0, m_nMaxDisp, 0, IPL_BORDER_REPLICATE);
    
    //
    // 计算视差
    if( alg == STEREO_BM )
    {
    	bm(img1b, img2b, dispb);
    	// 截取与原始画面对应的视差区域(舍去加宽的部分)
    	displf = dispb.colRange(m_nMaxDisp, img1b.cols);	
    }
    else if(alg == STEREO_SGBM)
    {
    	sgbm(img1b, img2b, dispb);
    	displf = dispb.colRange(m_nMaxDisp, img1b.cols);
    }
    

     

     

     

     

     

    4. cvFindStereoCorrespondenceBM的输出结果好像不是以像素点为单位的视差?

    @scyscyao:在OpenCV2.0中,BM函数得出的结果是以16位符号数的形式的存储的,出于精度需要,所有的视差在输出时都扩大了16倍(2^4)。其具体代码表示如下:

    dptr[y*dstep] = (short)(((ndisp - mind - 1 + mindisp)*256 + (d != 0 ? (p-n)*128/d : 0) + 15) >> 4);

    可以看到,原始视差在左移8位(256)并且加上一个修正值之后又右移了4位,最终的结果就是左移4位。

    因此,在实际求距离时,cvReprojectTo3D出来的X/W,Y/W,Z/W都要乘以16 (也就是W除以16),才能得到正确的三维坐标信息。”

    OpenCV2.1中,BM算法可以用 CV_16S 或者 CV_32F 的方式输出视差数据,使用32位float格式可以得到真实的视差值,而CV_16S 格式得到的视差矩阵则需要 除以16 才能得到正确的视差。另外,OpenCV2.1另外两种立体匹配算法 SGBM 和 GC 只支持 CV_16S 格式的 disparity 矩阵

     

    5. 如何设置BM、SGBM和GC算法的状态参数?

     

     

    6. 如何实现视差图的伪彩色显示?

    首先要将16位符号整形的视差矩阵转换为8位无符号整形矩阵,然后按照一定的变换关系进行伪彩色处理。我的实现代码如下:

    // 转换为 CV_8U 格式,彩色显示
    dispLfcv = displf, dispRicv = dispri, disp8cv = disp8;
    if (alg == STEREO_GC)
    {
    	cvNormalize( &dispLfcv, &disp8cv, 0, 256, CV_MINMAX );
    } 
    else
    {
    	displf.convertTo(disp8, CV_8U, 255/(m_nMaxDisp*16.));
    }
    F_Gray2Color(&disp8cv, vdispRGB);
    

     

     

    灰度图转伪彩色图的代码,主要功能是使灰度图中 亮度越高的像素点,在伪彩色图中对应的点越趋向于 红色;亮度越低,则对应的伪彩色越趋向于 蓝色;总体上按照灰度值高低,由红渐变至蓝,中间色为绿色。其对应关系如下图所示:

     

    图20

    void F_Gray2Color(CvMat* gray_mat, CvMat* color_mat)
    {
    	if(color_mat)
    		cvZero(color_mat);
    		
    	int stype = CV_MAT_TYPE(gray_mat->type), dtype = CV_MAT_TYPE(color_mat->type);
    	int rows = gray_mat->rows, cols = gray_mat->cols;
    
    	// 判断输入的灰度图和输出的伪彩色图是否大小相同、格式是否符合要求
    	if (CV_ARE_SIZES_EQ(gray_mat, color_mat) && stype == CV_8UC1 && dtype == CV_8UC3)
    	{
    		CvMat* red = cvCreateMat(gray_mat->rows, gray_mat->cols, CV_8U);
    		CvMat* green = cvCreateMat(gray_mat->rows, gray_mat->cols, CV_8U);
    		CvMat* blue = cvCreateMat(gray_mat->rows, gray_mat->cols, CV_8U);
    		CvMat* mask = cvCreateMat(gray_mat->rows, gray_mat->cols, CV_8U);
    
    		// 计算各彩色通道的像素值
    		cvSubRS(gray_mat, cvScalar(255), blue);	// blue(I) = 255 - gray(I)
    		cvCopy(gray_mat, red);			// red(I) = gray(I)
    		cvCopy(gray_mat, green);			// green(I) = gray(I),if gray(I) < 128
    		cvCmpS(green, 128, mask, CV_CMP_GE );	// green(I) = 255 - gray(I), if gray(I) >= 128
    		cvSubRS(green, cvScalar(255), green, mask);
    		cvConvertScale(green, green, 2.0, 0.0);
    
    		// 合成伪彩色图
    		cvMerge(blue, green, red, NULL, color_mat);
    
    		cvReleaseMat( &red );
    		cvReleaseMat( &green );
    		cvReleaseMat( &blue );
    		cvReleaseMat( &mask );
    	}
    }
    

     

     

     

     

    7. 如何将视差数据保存为 txt 数据文件以便在 Matlab 中读取分析?

    由于OpenCV本身只支持 xml、yml 的数据文件读写功能,并且其xml文件与构建网页数据所用的xml文件格式不一致,在Matlab中无法读取。我们可以通过以下方式将视差数据保存为txt文件,再导入到Matlab中。

    void saveDisp(const char* filename, const Mat& mat)		
    {
    	FILE* fp = fopen(filename, "wt");
    	fprintf(fp, "%02d/n", mat.rows);
    	fprintf(fp, "%02d/n", mat.cols);
    	for(int y = 0; y < mat.rows; y++)
    	{
    		for(int x = 0; x < mat.cols; x++)
    		{
    			short disp = mat.at<short>(y, x); // 这里视差矩阵是CV_16S 格式的,故用 short 类型读取
    			fprintf(fp, "%d/n", disp); // 若视差矩阵是 CV_32F 格式,则用 float 类型读取
    		}
    	}
    	fclose(fp);
    }
    

     

     

    相应的Matlab代码为:

    function img = txt2img(filename)
    data = importdata(filename);
    r = data(1);    % 行数
    c = data(2);    % 列数
    disp = data(3:end); % 视差
    vmin = min(disp);
    vmax = max(disp);
    disp = reshape(disp, [c,r])'; % 将列向量形式的 disp 重构为 矩阵形式
    %  OpenCV 是行扫描存储图像,Matlab 是列扫描存储图像
    %  故对 disp 的重新排列是首先变成 c 行 r 列的矩阵,然后再转置回 r 行 c 列
    img = uint8( 255 * ( disp - vmin ) / ( vmax - vmin ) );
    mesh(disp);
    set(gca,'YDir','reverse');  % 通过 mesh 方式绘图时,需倒置 Y 轴方向
    axis tight; % 使坐标轴显示范围与数据范围相贴合,去除空白显示区
    

     

     

    显示效果如下:

     

    SGBM算法原理

     

     

    emi-global matching(缩写SGM)是一种用于计算双目视觉中disparity的半全局匹配算法。在OpenCV中的实现为semi-global block matching(SGBM)。

    SGBM的思路是:

    通过选取每个像素点的disparity,组成一个disparity map,设置一个和disparity map相关的全局能量函数,使这个能量函数最小化,以达到求解每个像素最优disparity的目的。

    能量函数形式如下:

    D指disparity map。E(D)是该disparity map对应的能量函数。

    p, q代表图像中的某个像素

    Np 指像素p的相邻像素点(一般认为8连通)

    C(p, Dp)指当前像素点disparity为Dp时,该像素点的cost

    P1 是一个惩罚系数,它适用于像素p相邻像素中dsparity值与p的dsparity值相差1的那些像素。

    P2 是一个惩罚系数,它适用于像素p相邻像素中dsparity值与p的dsparity值相差大于1的那些像素。

    I[.]函数返回1如果函数中的参数为真,否则返回0

    利用上述函数在一个二维图像中寻找最优解是一个NP-complete问题,耗时过于巨大,因此该问题被近似分解为多个一维问题,即线性问题。而且每个一维问题都可以用动态规划来解决。因为1个像素有8个相邻像素,因此一般分解为8个一维问题。

    考虑从左到右这一方向,如下图所示:

    则每个像素的disparity只和其左边的像素相关,有如下公式:

    r指某个指向当前像素p的方向,在此可以理解为像素p左边的相邻像素。
    Lr(p, d) 表示沿着当前方向(即从左向右),当目前像素p的disparity取值为d时,其最小cost值。

    这个最小值是从4种可能的候选值中选取的最小值:

    1.前一个像素(左相邻像素)disparity取值为d时,其最小的cost值。

    2.前一个像素(左相邻像素)disparity取值为d-1时,其最小的cost值+惩罚系数P1。

    3.前一个像素(左相邻像素)disparity取值为d+1时,其最小的cost值+惩罚系数P1。

    4.前一个像素(左相邻像素)disparity取值为其他时,其最小的cost值+惩罚系数P2。

    另外,当前像素p的cost值还需要减去前一个像素取不同disparity值时最小的cost。这是因为Lr(p, d)是会随着当前像素的右移不停增长的,为了防止数值溢出,所以要让它维持在一个较小的数值。

    C(p, d)的计算很简单,由如下两个公式计算:

    即,当前像素p和移动d之后的像素q之间,经过半个像素插值后,寻找两个像素点灰度或者RGB差值的最小值,作为C(p, d)的值。

    具体来说:设像素p的灰度/RGB值为I(p),先从I(p),(I(p)+I(p-1))/2,(I(p)+I(p+1))/2三个值中选择出和I(q)差值最小的,即

    d(p,p-d)。然后再从I(q),(I(q)+I(q-1))/2,(I(q)+I(q+1))/2三个值中选择出和I(p)差值最小的,即d(p-d,p)。最后从两个值中选取最小值,就是C(p, d)

    上面是从一个方向(从左至右)计算出的像素在取值为某一disparity值时的最小cost值。但是一个像素有8个邻域,所以一共要从8个方向计算(左右,右左,上下,下上,左上右下,右下左上,右上左下,左下右上)这个cost值。

    然后把八个方向上的cost值累加,选取累加cost值最小的disparity值作为该像素的最终disparity值。对于每个像素进行该操作后,就形成了整个图像的disparity map。公式表达如下:

    SGBM算法遍历每个像素,针对每个像素的操作和disparity的范围有关,故时间复杂度为:

    展开全文
  • 题目描述请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符,而’*’表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,...

    题目描述

    请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符,而’*’表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”ab*ac*a”匹配,但是与”aa.a”和”ab*a”均不匹配

    由于只涉及两种正则表达式的匹配,所以关键是需要分清除匹配的所有情况,对于模式串来讲,出现了’.’和’*’的时候需要单独考虑,因为两者的匹配情况是不一样的。先考虑模式串中有’*’的情况,因为’*’可以匹配0个或者多个,所以如果模式串的下一个字符是’*’的时候就有三种情况:1)匹配0个主串的字符,比如主串是abc,模式串是b*的时候,就是这种情况,那么下一步的匹配策略是主串保持不变,模式串跳到下两个字符重新比较;2)匹配1个字符,比如主串是abc,模式串是a*就是这种情况,因为只匹配到了a这一个字符。这种情况的下一步的比较策略应该是主串跳到下一个字符,模式串移动两个位置;3)匹配多个字符,比如主串是aac,模式串是a*cb就匹配到了aa这两个字符,那么这种情况下下一步的匹配策略应该是主串移动一个字符,模式串移动两个位置;如果当前的字符与主串的字符不能匹配,则主串保持不变,模式串移动两个位置。如果当前字符是’.’的话,直接逐个字符进行比较就行了。下面是这种思路的实现代码(已被牛客AC):

    package com.rhwayfun.offer;
    
    public class MatchRegString {
    
        public boolean match(char[] str, char[] pattern) {
            if (str == null || pattern == null)
                return false;
            return matchRegCore(str, 0, str.length, pattern, 0, pattern.length);
        }
    
        private boolean matchRegCore(char[] str, int i, int length1,
                char[] pattern, int j, int length2) {
            if (i == length1 && j == length2) {
                // 主串匹配到末尾,模式串要么也匹配到末尾要么当前位置的字符是*,否则返回false
                if (j == length2 || pattern[j] == '*')
                    return true;
                else
                    return false;
            }
            if (i != length1 && j == length2)
                return false;
            /*
             * 一、如果模式串的下一个字符是*, 1.1 并且模式串的当前字符能与主串的字符进行匹配,则可能出现三种情况:
             * 1、模式串的当前字符匹配到0个字符,则主串不变,模式穿移动到两个字符
             * 2、模式穿的当前字符匹配到1个字符,则主串移动一个位置,模式串移动两个位置
             * 3、模式串的当前字符匹配到多个字符,则主串移动一个位置,模式串移动两个位置。 1.2 如果不能匹配的话: 主串不变,模式串移动两个位置;
             * 二、如果下一个字符不是*,则进行逐个字符进行匹配 三、如果模式串的下一个字符是.,则就进行一个字符的匹配
             */
            if (j + 1 < length2 && pattern[j + 1] == '*') {
                if (i < length1 && (pattern[j] == str[i] || pattern[j] == '.')) {
                    return matchRegCore(str, i + 1, length1, pattern, j, length2)
                            || matchRegCore(str, i + 1, length1, pattern, j + 2,
                                    length2)
                            || matchRegCore(str, i, length1, pattern, j + 2,
                                    length2);
                } else {
                    return matchRegCore(str, i, length1, pattern, j + 2, length2);
                }
            }
            if (i < length1 && (str[i] == pattern[j] || pattern[j] == '.')) {
                return matchRegCore(str, i + 1, length1, pattern, j + 1, length2);
            }
            return false;
        }
    
        public static void main(String[] args) {
            char[] str = { 'a', 'a', 'a' };
            char[] pattern = { 'a', 'b', '*', 'a' };
            boolean b = new MatchRegString().match(str, pattern);
            System.out.println(b);
        }
    }
    
    展开全文
  • 正则匹配

    千次阅读 2013-08-06 09:54:27
    正则匹配模式 匹配模式指得是正则表达式引擎将以何种模式匹配字符串。 模式名称 启用,禁用 缺省启用 说明 UNIX_LINES (?d)启用,(?-d)禁用 是 启用Unix模式。 在此模式下,只有 '\n'被认为...
  • 有时候我们需要两个文件来记录已执行过和待执行的记录,这个时候我们需要找到已执行文件中**具有某种特征的**,以此来确定下一个执行任务。
  • MSSQL之 连接查询与子查询

    千次阅读 2016-05-16 19:06:28
    你可以使用子查询,这里一个查询的结果被用作另一个查询的条件的输入。 本章讨论如何通过应用各种类型的连接,例如内连接,外连接,交叉连接,等值连接或自连接,来从夺标中查询数据。进一步,它解释如何使用子查询
  • 1、前两种都是属于模板匹配的方法,这些概念是在《数字图像处理高级应用》里的,其是移动匹配与向量匹配很像,只是移动匹配对灰度变换的鲁棒性不好。 这里说的移动匹配:就是把模板图像在原图像上进行移动,让后计算...
  • 解题报告 (九) 二分图最大匹配

    万次阅读 2021-01-16 21:00:13
    二分图最大匹配题集-全网最全
  • 形状匹配

    千次阅读 2016-03-25 10:49:05
    HALCON提 供的基于形状匹配的算法主要是针对感兴趣的小区域来建立模板,对整个图像建立模板也可以,但这样除非是对象在整个图像中所占比例很大,比如像视频会议中人 体上半身这样的图像,我在后面的视频对象跟踪实验...
  • sed 命令,打印出匹配行的下N

    千次阅读 2013-02-28 22:06:38
    测试文件 test.log [root@localhost aaa]# cat test.log ...匹配出以a开头并以a结尾的后1: sed -n '/^a$/,+1p' test.log   输出结果: a 1 a 4   打印出符合开头是a的记录的下...
  • 在利用正则表达式的解析过程中,我们经常会遇到多行字符输出的情形,例如执行执行dir命令,如输出如下结果:1 个文件 59,629,625 字节 ...方法一:跨解析对于跨解析,首先需要解决的问题是如何匹配符,在大部分
  • 模板匹配

    千次阅读 2017-12-03 15:31:53
    去年有过一段时间的集中学习,做了许多的练习和实验,并对基于HDevelop的形状匹配算法的参数优化进行了研究,写了一篇《基于HDevelop的形状匹配算法参数的优化研究》文章,总结了在形状匹配过程中哪些参数影响到模板...
  • grep显示匹配行的上下几行的用法

    万次阅读 2018-06-20 18:11:12
    grep -C 3 love filename 显示filename文件中,love上下3内容(含love)grep -A 3 love filename 显示filename文件中,love下3内容(含love)grep -B 3 love filename 显示filename文件中,love上...
  • 大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中,参考严奶奶的教材,我也是在关于求next值的算法中卡了一下午时间,感觉挺有意思的,把一些思考的...
  • HALCON形状匹配讲解

    千次阅读 2017-12-14 15:25:32
    去年有过一段时间的集中学习,做了许多的练习和实验,并对基于HDevelop的形状匹配算法的参数优化进行了研究,写了一篇《基于HDevelop的形状匹配算法参数的优化研究》文章,总结了在形状匹配过程中哪些参数影响到模板...
  • Perl模式匹配

    千次阅读 2014-09-26 13:16:59
    Perl 内置的模式匹配让你能够简便高效地搜索大量的数据。不管你是在一个巨型的商业门户站点上用于扫描每日感兴趣的珍闻报道,还是在一个政府组织里用于精确地描述人口统计(或者人类基因组图),或是在一个教育组织...
  • 原文: ... 三种匹配算法比较 BM算法: 该算法代码: view plaincopy to clipboardprint? CvStereoBMState *BMState = cvCreateStereoBMState(); int SADWindowSize=15; 
  • ElasticSearch (ES)学习之路()ES 复杂搜索( 匹配 过滤 精准 排序 高亮) 在上文中,我们查询小红 其kinbana 语法是这样写的 GET /lei/one/_search?q=name:小丽 前文中,也是做了分析,由于有多个包含‘小丽’...
  • 标准的C和C++不支持正则表达式,但有一些函数库可以辅助C/C++程序员完成这一功能。正则表达式常用函数:编译正则表达式 regcomp()、匹配正则表达式 regexec()、释放正则表达式 regfree()。
  • HALCON基于形状匹配详解

    千次阅读 2019-05-06 13:43:51
    去年有过一段时间的集中学习,做了许多的练习和实验,并对基于HDevelop的形状匹配算法的参数优化进行了研究,写了一篇《基于HDevelop的形状匹配算法参数的优化研究》文章,总结了在形状匹配过程中哪些参数影响到模板...
  • halcon模板匹配

    千次阅读 2014-09-22 20:34:25
    * 在一个图片中获取ROI并在此图片中匹配  dev_close_window ()  dev_open_window (0, 0, 600, 600, 'black', WindowHandle)  * 窗口语句  read_image(Image,'L:/Halcon test/mk2.jpg')  *read_image(Image...
  • MySQL 索引最左匹配原则

    千次阅读 2016-10-24 22:11:58
    索引主要做3件事:过滤(filter),排序或分组(sort/group),覆盖(cover)。前两个没什么好说的,但并不是每个人都...1. 使用索引以查找匹配的记录,并得到数据的指针。 2. 使用相关数据的指针。 3. 返回查询到的记录。
  • Nginx的转发匹配规则

    千次阅读 2017-03-02 15:51:00
    正则表达式匹配,其中: ~ 为区分大小写匹配 ~* 为不区分大小写匹配 !~和!~*分别为区分大小写不匹配及不区分大小写不匹配 二.文件及目录匹配,其中: -f和!-f用来判断是否存在文件 -d和!-d用来判断是否存在目录 -e...
  • shell 下正则表达式的匹配

    千次阅读 2014-08-04 09:44:39
    一、用法讲解 (1).匹配任意单字符 ...trobule$表示匹配以trobule结尾的 d$表示匹配以字母d结尾的字符 ^$表示匹配空行 ^.$匹配只包含一个字母的 *匹配字符串中单个字符或其重复序列 compu*t表示
  • Makefile中的匹配符%

    千次阅读 多人点赞 2019-03-18 19:06:45
    一、匹配符% Make命令允许对文件名,进行类似正则运算的匹配,主要用到的匹配符是%。比如,假定当前目录下有 f1.c 和 f2.c 两个源码文件,需要将它们编译为对应的对象文件。 %.o: %.c 等同于下面的写法。 f1.o...
  • 目前网上关于滑块的缺口识别的方法很多,但是都不极简,看起来繁杂,各种算法的都有,有遍历的有二分法的... 找出图像中最佳匹配位置 :param target: 目标即背景图 :param template: 模板即需要找到的图 :return:...
  • 地图匹配算法实践

    万次阅读 热门讨论 2017-02-21 19:37:42
    地图匹配算法实践 1 背景 如下图所示,1、2、3 这三个点是汽车的GPS定位结果,尽管汽车是在道路上,但定位结果与道路存在偏差。地图匹配(Map Matching)是指将行车轨迹的经纬度采样序列与数字地图路网...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 223,495
精华内容 89,398
关键字:

五行匹配查询