• Guest
HabraHabr
  • Main
  • Users

  • Development
    • Programming
    • Information Security
    • Website development
    • JavaScript
    • Game development
    • Open source
    • Developed for Android
    • Machine learning
    • Abnormal programming
    • Java
    • Python
    • Development of mobile applications
    • Analysis and design of systems
    • .NET
    • Mathematics
    • Algorithms
    • C#
    • System Programming
    • C++
    • C
    • Go
    • PHP
    • Reverse engineering
    • Assembler
    • Development under Linux
    • Big Data
    • Rust
    • Cryptography
    • Entertaining problems
    • Testing of IT systems
    • Testing Web Services
    • HTML
    • Programming microcontrollers
    • API
    • High performance
    • Developed for iOS
    • CSS
    • Industrial Programming
    • Development under Windows
    • Image processing
    • Compilers
    • FPGA
    • Professional literature
    • OpenStreetMap
    • Google Chrome
    • Data Mining
    • PostgreSQL
    • Development of robotics
    • Visualization of data
    • Angular
    • ReactJS
    • Search technologies
    • Debugging
    • Test mobile applications
    • Browsers
    • Designing and refactoring
    • IT Standards
    • Solidity
    • Node.JS
    • Git
    • LaTeX
    • SQL
    • Haskell
    • Unreal Engine
    • Unity3D
    • Development for the Internet of things
    • Functional Programming
    • Amazon Web Services
    • Google Cloud Platform
    • Development under AR and VR
    • Assembly systems
    • Version control systems
    • Kotlin
    • R
    • CAD/CAM
    • Customer Optimization
    • Development of communication systems
    • Microsoft Azure
    • Perfect code
    • Atlassian
    • Visual Studio
    • NoSQL
    • Yii
    • Mono и Moonlight
    • Parallel Programming
    • Asterisk
    • Yandex API
    • WordPress
    • Sports programming
    • Lua
    • Microsoft SQL Server
    • Payment systems
    • TypeScript
    • Scala
    • Google API
    • Development of data transmission systems
    • XML
    • Regular expressions
    • Development under Tizen
    • Swift
    • MySQL
    • Geoinformation services
    • Global Positioning Systems
    • Qt
    • Dart
    • Django
    • Development for Office 365
    • Erlang/OTP
    • GPGPU
    • Eclipse
    • Maps API
    • Testing games
    • Browser Extensions
    • 1C-Bitrix
    • Development under e-commerce
    • Xamarin
    • Xcode
    • Development under Windows Phone
    • Semantics
    • CMS
    • VueJS
    • GitHub
    • Open data
    • Sphinx
    • Ruby on Rails
    • Ruby
    • Symfony
    • Drupal
    • Messaging Systems
    • CTF
    • SaaS / S+S
    • SharePoint
    • jQuery
    • Puppet
    • Firefox
    • Elm
    • MODX
    • Billing systems
    • Graphical shells
    • Kodobred
    • MongoDB
    • SCADA
    • Hadoop
    • Gradle
    • Clojure
    • F#
    • CoffeeScript
    • Matlab
    • Phalcon
    • Development under Sailfish OS
    • Magento
    • Elixir/Phoenix
    • Microsoft Edge
    • Layout of letters
    • Development for OS X
    • Forth
    • Smalltalk
    • Julia
    • Laravel
    • WebGL
    • Meteor.JS
    • Firebird/Interbase
    • SQLite
    • D
    • Mesh-networks
    • I2P
    • Derby.js
    • Emacs
    • Development under Bada
    • Mercurial
    • UML Design
    • Objective C
    • Fortran
    • Cocoa
    • Cobol
    • Apache Flex
    • Action Script
    • Joomla
    • IIS
    • Twitter API
    • Vkontakte API
    • Facebook API
    • Microsoft Access
    • PDF
    • Prolog
    • GTK+
    • LabVIEW
    • Brainfuck
    • Cubrid
    • Canvas
    • Doctrine ORM
    • Google App Engine
    • Twisted
    • XSLT
    • TDD
    • Small Basic
    • Kohana
    • Development for Java ME
    • LiveStreet
    • MooTools
    • Adobe Flash
    • GreaseMonkey
    • INFOLUST
    • Groovy & Grails
    • Lisp
    • Delphi
    • Zend Framework
    • ExtJS / Sencha Library
    • Internet Explorer
    • CodeIgniter
    • Silverlight
    • Google Web Toolkit
    • CakePHP
    • Safari
    • Opera
    • Microformats
    • Ajax
    • VIM
  • Administration
    • System administration
    • IT Infrastructure
    • *nix
    • Network technologies
    • DevOps
    • Server Administration
    • Cloud computing
    • Configuring Linux
    • Wireless technologies
    • Virtualization
    • Hosting
    • Data storage
    • Decentralized networks
    • Database Administration
    • Data Warehousing
    • Communication standards
    • PowerShell
    • Backup
    • Cisco
    • Nginx
    • Antivirus protection
    • DNS
    • Server Optimization
    • Data recovery
    • Apache
    • Spam and antispam
    • Data Compression
    • SAN
    • IPv6
    • Fidonet
    • IPTV
    • Shells
    • Administering domain names
  • Design
    • Interfaces
    • Web design
    • Working with sound
    • Usability
    • Graphic design
    • Design Games
    • Mobile App Design
    • Working with 3D-graphics
    • Typography
    • Working with video
    • Work with vector graphics
    • Accessibility
    • Prototyping
    • CGI (graphics)
    • Computer Animation
    • Working with icons
  • Control
    • Careers in the IT industry
    • Project management
    • Development Management
    • Personnel Management
    • Product Management
    • Start-up development
    • Managing the community
    • Service Desk
    • GTD
    • IT Terminology
    • Agile
    • Business Models
    • Legislation and IT-business
    • Sales management
    • CRM-systems
    • Product localization
    • ECM / EDS
    • Freelance
    • Venture investments
    • ERP-systems
    • Help Desk Software
    • Media management
    • Patenting
    • E-commerce management
    • Creative Commons
  • Marketing
    • Conferences
    • Promotion of games
    • Internet Marketing
    • Search Engine Optimization
    • Web Analytics
    • Monetize Web services
    • Content marketing
    • Monetization of IT systems
    • Monetize mobile apps
    • Mobile App Analytics
    • Growth Hacking
    • Branding
    • Monetize Games
    • Display ads
    • Contextual advertising
    • Increase Conversion Rate
  • Sundry
    • Reading room
    • Educational process in IT
    • Research and forecasts in IT
    • Finance in IT
    • Hakatonas
    • IT emigration
    • Education abroad
    • Lumber room
    • I'm on my way

Laplace Blur

Laplace Blur
 
 
Is it possible to blur Laplace instead of Gauss, how many times it is faster, and is it worth the loss of 1/32 accuracy.
 
3r311. 3r33232.
 
 
(Laplace Blur - The proposed original name of the algorithm)
 
 
Today, my internal demoscenary kicked me and forced me to write an article that had to be written six months ago. As an amateur at my leisure to develop original effect algorithms, I would like to propose to the public an “almost Gaussian blura” algorithm, featuring the use of extremely fast processor instructions (shifts and masks), and therefore is available for implementation up to microcontrollers (extremely fast in a limited environment).
 
 
According to my tradition of writing articles on Habr, I will give examples in JS, as in the most popular language, and believe it or not, it is very convenient for the rapid prototyping of algorithms. In addition, the ability to implement this effectively on JS has come along with typed arrays. On my not very powerful laptop, the fullscreen image is processed at a speed of 30fps (the multithreading of the workers was not involved).
 
 
3r330. Disclaimer for cool mathematicians [/b]
Immediately I will say that I take off my hat in front of you, because I myself consider myself not sufficiently savvy in basic mathematics. However, I am always guided by the general spirit of the fundamental approach. Therefore, before heytit my, to some extent “observant” approach to approximation, take care to count the bit complexity of the algorithm, which, in your opinion, can be obtained by the methods of classical approximation by polynomials. I guessed? You wanted to quickly approximate them? Given that they will require floating arithmetic, they will be much slower than a single bit shift, to which I will explain in the end. In a word, do not rush into theoretical fundamentalism, and do not forget about the context in which I solve the problem.
 
 
 
This description is present here rather to explain the course of my thoughts and conjectures that led me to the result. For those who will be interested:
 
 
Original Gauss Function:
 
 

 
 
g (x) = a * e ** (- ((x-b) ** 2) /c), where r3r3241.  
a is the amplitude (if the color is eight bits per channel, then it is = 256)
 
e is the Euler constant ~ ???r3r3241.  
b - the shift of the graph in x (we do not need = 0)
 
c - the parameter affecting the width of the graph associated with it as ~ w /???r3r3241.  
 
Our private function (minus from the exponent is removed with substitution of multiplication by division):
 
 

 
 
g (x) = 256 /e ** (x * x /c)
 
 
Let the dirty approximation act begin:
 
Note that the parameter c is very close to the half-width and set to 8 (this is due to how many steps you can move along one 8-bit channel).
 
We will also roughly replace e by ? noting, however, that this affects the curvature of the “bell” more than its borders. Actually, it affects 2 /e times, but the surprise is that this error compensates for the parameter introduced in the definition of the parameter s, so that the boundary conditions are still in order, and the error appears only in a slightly incorrect “normal distribution”, for graphic algorithms, this will affect the dynamics of gradient color transitions, but it is almost impossible to notice with the eye.
 
 
So now our function is this:
 
gg (x) = 256/2 ** (x * x /8) or gg (x) = 2 ** (8 - x * x /8) r3r3241.  
Note that the exponent (x * x /8) has the same range of values ​​of[0-8]as a function of a smaller order abs (x), because the latter is a candidate for replacement. Quickly check the guess by looking at how the graph changes with it gg (x) = 256 /(2 ** abs (x)):
 
 
GaussBlur vs LaplasBlur:
 
 
3r399.
 
 
It seems that the deviations are too great, besides the function, having lost its smoothness, now has a peak. But wait.
 
First, let's not forget that the smoothness of the gradients obtained by blurring does not depend on the probability density function (which is the Gauss function), but on its integral — the distribution function. At that moment I did not know this fact, but in fact, after conducting a “destructive” approximation with respect to the probability density function (Gauss), the distribution function remained quite similar.
 
 
It was
 
3r33112.
 
 
It became:
 
3r3119.
 
 
Proof, taken from the finished algorithm is the same:
 

 
 
(looking ahead, I’m saying that the blur error of my algorithm for Gausian x5 was only 3%)
 
So, we have moved much closer to the Laplace distribution function. Who would have thought, but they can wash images at 97% no worse.
 
 
Proof, the difference of the Gaucian Blura x5 and "Laplace Blura" x7:
 
 
3r3141.
 
 
(this is not a black image! You can study in the editor)
 
 
The admission of this transformation allowed us to proceed to the idea of ​​obtaining the value by iterative filtering, which I planned to reduce to the beginning.
 
 
Before the narration of a specific algorithm, it will be fair if I run ahead and immediately describe its only drawback (although the implementation can be fixed, with a loss of speed). But this algorithm is implemented using shear arithmetic, and degrees 2k are its limitation. So the original is made to blur x7 (which is the closest to the Gausian x5 in the tests). This restriction of the implementation is connected with the fact that with eight-bit color, shifting the value in the filter drive by one bit per step, any effect from a point ends in a maximum of 8 steps. I also implemented a slightly slower version in terms of proportions and additional additions, which realizes a quick division by 1.5 (having obtained as a result a radius of x15). But with the further application of this approach, the error increases, and the speed drops, which does not allow using it so. On the other hand, it is worth noting that x15 is already enough to not notice much of the difference, the result is obtained from the original or from the downsampled image. So the method is quite suitable if you need extreme speed in a limited environment.
 
 
So, the core of the algorithm is simple, four passes of the same type are performed:
 
1. Half of the value of the drive t (initially equal to zero) is added to half the value of the next pixel, the result is assigned to it. We continue this way until the end of the image line. For all lines.
 
 
Upon completion of the first pass, the image is blurred in one direction.
 
 
2. In the second pass we do the same in the opposite direction for all lines.
 
We get the image completely blurred horizontally.
 
 
3-4. Now do the same thing vertically.
 
Done!
 
 
Initially, I used a two-pass algorithm with the implementation of reverse blurring through the stack, but it is difficult to understand, not graceful, and besides, on the current architectures it turned out to be slower. Perhaps the one-pass algorithm will be faster on microcontrollers, plus it will also be possible to output the result progressively.
 
The current four-pass method of implementation, I looked at the previous guru on the blur algorithms. 3r3182. habr.com/post/151157
Taking this opportunity, I express to him my solidarity and deep gratitude.
 
 
But the hacks didn't end there. Now, on how to calculate all three color channels for one processor instruction! The fact is that the bit shift used as a division by two allows the position bits of the result to be very well controlled. The only problem is that the lower bits of the channels slide into the neighboring older ones, but you can simply reset them, rather than correct the problem, with some loss of accuracy. And according to the described filter formula, the addition of half the value of the drive with half the value of the next cell (assuming zeroing of the discharged discharges) never leads to overflow, so you should not worry about it. And the filter formula for calculating all digits at the same time becomes
 
 
buf32[i]= t = (((t 1) & 0x7F7F7F) + ((buf32[i]1) & 0x7F7F7F); 3r-3241.  
 
However, another addition is required: it was empirically found that the loss of accuracy in this formula is too significant, the brightness of the picture visually jumps noticeably. It became clear that the lost bits should be rounded to the whole, and not discarded. A simple way to do this in integer arithmetic is to add half the divider before division. The divider is a two for us, so you need to add one, in all digits, - the constant 0x010101. But with any addition you need to be careful not to get an overflow. So we cannot use this correction to calculate the half value of the next cell. (If there is a white color, we will get an overflow, therefore we will not correct it). But it turned out that the main mistake was made by the multiple division of the drive, which we can correct. Because, in fact, even with such a correction, the value in the drive will not rise above 254. But when added to 0x01010? overflow will not be guaranteed. And the formula of the filter with the correction takes the form:
 
 
buf32[i]= t = ((((0x010101 + t) 1) & 0x7F7F7F) + ((buf32[i]1) & 0x7F7F7F);
 
 
In fact, the formula performs correction quite well, so that when you repeatedly apply this algorithm to an image, artifacts begin to be seen only in the second dozen passes. (not the fact that the repetition of the Ghusian Blur will not give such artifacts).
 
 
Additionally, there is a remarkable property, with multiple passes. (It is not the merit of my algorithm, but the “normality” of the normal distribution itself). Already on the second pass, the Laplace Blur probability density function (if I figured it all out correctly) will look something like this:
 
 

 
 
That, you see, is already very close to the Ghousiana.
 
Experimentally, I found that it is permissible to use modifications with a large radius in a pair, since The property described above compensates for errors if the last pass is more accurate (the most accurate one is the x7 blur algorithm described here).
 
 
demo: impfromliga.github.io/LaplaceBlur
 
Rep: github.com/impfromliga/LaplaceBlur
 
codepen: codepen.io/impfromliga/pen/brXZjJ
 
 
A Call for Cool Mathematicians:
 
What would be interesting to know how well to use such a filter is separable, not sure if there is a symmetrical distribution pattern. Although the eye of heterogeneity and is not visible.
 
 
Suggestions, comments, constructive criticism - welcome!

It may be interesting

  • Comments
  • About article
  • Similar news
heenacruzl 31 January 2020 09:52
I loved the article, keep updating interesting articles. I will be a regular reader.
Douchebag Workout 3 Play

weber

Author

27-10-2018, 07:17

Publication Date

Algorithms / Mathematics / Abnormal programming / Image processing

Category
  • Comments: 1
  • Views: 372
MatLab /Octave machine learning:
Symbolic solution of linear
Learn OpenGL. Lesson 5.8 - Bloom
The effect of the lens is tilt-shift
Batch processing of images in Windows
Basics of sorting for beginners and
Write a comment
Name:*
E-Mail:


Comments

Here we introduce our top coupons that will help you for online shopping at discountable prices.Revounts bring you the best deals that slash the bills.If you are intrested in online shopping and want to save your savings then visit our site for best experience.
Today, 08:41

Emma Taylor

Global Dezigns is a Website Development Company in Karachi, Providing services of
website design in karachi
. We are delivering the best partnership across Pakistan. provides a complete range of web development services including web applications, website hosting and maintenance, domain registration, on-page search engine optimization, and website integration with social media platforms such as Facebook, Twitter, LinkedIn, Google Maps, and Google Local Directory. We believe we are well placed to take our knowledge and expertise to the logical next level with the latest web standards.  
  Show/hide text
https://www.globaldezigns.com/



Yesterday, 22:45

mike tomlin

This blog is really great. The information here will surely be of some help to me. Thanks!.mastering physics

Yesterday, 17:57

raymond weber

Coinyspace is the cryptocurrency community and trading forum where members can find any contributors of crypto ecosystem like currencies, exchanges & merchants. Check Out: Bitcoin Merchants
Yesterday, 16:57

noorseo

This is a great high resolution screen which you have shared for the users. Making a website is not an easy task but managing a good website is really a hard work. As far as this website is concerned, I am very happy.https://19216801.1
Yesterday, 16:01

nushra45

Adv
Website for web developers. New scripts, best ideas, programming tips. How to write a script for you here, we have a lot of information about various programming languages. You are a webmaster or a beginner programmer, it does not matter, useful articles will help to make your favorite business faster.

Login

Registration Forgot password