boris-kz / CogAlg

This project is a Computer Vision implementation of general hierarchical pattern discovery principles introduced in README

http://www.cognitivealgorithm.info

MIT License

91 stars 41 forks source link

Super CogAlg C++ discovers blob-like patterns #32

Closed Twenkid closed 4 years ago

Twenkid commented 5 years ago

Khan, Boris - see a frame from the video game "Super Contra" and some blobs, looking like Tetris, rendered by the work-in-progress C++ implementation inspired by CogAlgo comparison methods.

However probably it won't be strictly porting them (it depends how good I understand them as well :D ) and is likely to evolve in some divergent directions, depending on the gained insights.

Anyway I believe it may give insights to the "Vanilla" versions and my design would aim at making the system also more interactive, configurable and playable.

I want different comparisons and traversals to be easier to define, test, explore, apply on datasets
and thus give insights about the operation of the algorithm and what it actually discovers.

The primary comparisons and the horizontal Ps collection after the binary partitioning was straightforward.

The current stage seg-blob traversal is yet a study and a playground. Currently I do it depth-first (but would go to two-line scheme next).

"draw" window is primary g (abs(dx) + abs(dy), where dx,dy are single-compared) "Gradient" word above is about the color of the segments/blobs (too colorful there :) ).

khanh93vn commented 5 years ago

Yo! Sorry for the late reply.

Those are nasty stuffs indeed.

Could you please post the original frame image for comparison?

Twenkid commented 5 years ago

Hi Khan,

Yes, see below (due to excuses etc. and it is supposed to change soon).
I agree it's nasty stuff. Funny, though.

May you mark some examples of how the segs and blobs should be connected given the pictures below?

(The blobs are not connected yet in these pictures, also the segs are often interrupted, due to a greedy DFS search for the two-signs at once, which then breaks the segs and doesnt continue them. It'd be changed.)

1) As of the partitioning, when there is a "bridge", many adjacent connected horizontal patterns (fork_ > 1 in Boris terminology), is it supposed just to be partitioned in two or more segments?

2) One current takes the bridge pattern and links it to the rest and removes it from the collection, then the other Ps is taken as a first pattern and linked down etc.?

3) Is every pattern attached to a seg, even with Ly=1? or only regions of at least two connected lines are segments? (and the rest - skipped and not existent in that level)?

4) The segment was "without holes" (?) by definition, but the blob includes segments which are connected by bridges, and thus could the blob have holes?

Anyway, I think the bridges suppose variability in the partitioning of the segments, depending on the order of selection. ...

Currently I treat the different level Ps more generally - I aim at more compatibility between different levels of patterns and for easier tracing, reconstruction and debugging.

For example my Ps have additional variables, e.g. each has y from the start, so even if buggy or linked anywhere, it "knows" where it belongs, without a need of an external iteration with a counter.

...

As of the pictures, that was still very buggy and is yet inefficient (those gray holes were sequences of patterns attached to containers linked to nowhere). Now is better, but still not completed, a few holes and not the best way.

Eventually it should be possible to draw also the borders in a scaled-up view - when using fewer colors, sometimes the color may match, but the patterns to be different. It should also be interactive - point, mark patterns, show them separately, show only positive, show only negative, etc.

It should also display areas in an animated way.

Currently my experimental traversal is a combination of recursive DFS, greedy, with following iteration-driven calls for new recursions for consuming the remaining items into sequences of vertically connected patterns.

The original image

The blue channel is compared ([0] in OCV):

Gradient (computed "my way" though):

The whole currently, red are positive, blue are negative. Dark parts are just dark-red, dark-blue. The gray part is some sequences "leaked" somewhere.

Regions which are not connected properly - different grades of same color adjacent without a whole between them (interrupted by the neg patterns and the greedy traversal):

It's from the characters:

Something else funny, "Jurassic Park" (I think I've taken the original image from Pyimagesearch):

Zoomed x 3

Idea of how the traversal goes

Etc...

Top-down and left-right.

Also a beginning of the borders (it should be not on every line, though, but around segments)

boris-kz commented 5 years ago

Todor, C++ is a dead end, you are wasting your time. Please start with Julia. And post your code if you want a meaningful feedback.

On Mon, Jun 3, 2019 at 7:10 PM Todor Arnaudov notifications@github.com wrote:

Hi Khan,

Yes, see below (due to excuses etc. and it is supposed to change soon). I agree it's nasty stuff. Funny, though.

May you mark some examples of how the segs and blobs should be connected given the pictures below?

(The blobs are not connected yet in these pictures, also the segs are often interrupted, due to a greedy DFS search for the two-signs at once, which then breaks the segs and doesnt continue them. It'd be changed.)

1.

As of the partitioning, when there is a "bridge", many adjacent connected horizontal patterns (fork_ > 1 in Boris terminology), is it supposed just to be partitioned in two or more segments? 2.

One current takes the bridge pattern and links it to the rest and removes it from the collection, then the other Ps is taken as a first pattern and linked down etc.? 3.

Is every pattern attached to a seg, even with Ly=1? or only regions of at least two connected lines are segments? (and the rest - skipped and not existent in that level)? 4.

The segment was "without holes" (?) by definition, but the blob includes segments which are connected by bridges, and thus could the blob have holes?

Anyway, I think the bridges suppose variability in the partitioning of the segments, depending on the order of selection. ...

Currently I treat the different level Ps more generally - I aim at more compatibility between different levels of patterns and for easier tracing, reconstruction and debugging.

For example my Ps have additional variables, e.g. each has y from the start, so even if buggy or linked anywhere, it "knows" where it belongs, without a need of an external iteration with a counter.

...

As of the pictures, that was still very buggy and is yet inefficient (those gray holes were sequences of patterns attached to containers linked to nowhere). Now is better, but still not completed, a few holes and not the best way.

Eventually it should be possible to draw also the borders in a scaled-up view - when using fewer colors, sometimes the color may match, but the patterns to be different. It should also be interactive - point, mark patterns, show them separately, show only positive, show only negative, etc.

It should also display areas in an animated way.

Currently my experimental traversal is a combination of recursive DFS, greedy, with following iteration-driven calls for new recursions for consuming the remaining items into sequences of vertically connected patterns. The original image

[image: image] https://user-images.githubusercontent.com/23367640/58837539-85229b00-8664-11e9-9106-ed48069e89cb.png (C) Konami 1990 :)

The blue channel is compared ([0] in OCV):

[image: image] https://user-images.githubusercontent.com/23367640/58837635-ca46cd00-8664-11e9-8760-c480344cfc49.png

Gradient (computed "my way" though):

[image: image] https://user-images.githubusercontent.com/23367640/58837867-7dafc180-8665-11e9-8f6c-e6df42300470.png

The whole currently, red are positive, blue are negative. Dark parts are just dark-red, dark-blue. The gray part is some sequences "leaked" somewhere.

[image: image] https://user-images.githubusercontent.com/23367640/58838358-24e12880-8667-11e9-9e35-afbea07c74ec.png

Regions which are not connected properly - different grades of same color adjacent without a whole between them (interrupted by the neg patterns and the greedy traversal):

It's from the characters:

[image: image] https://user-images.githubusercontent.com/23367640/58838462-670a6a00-8667-11e9-950d-bf22a7e401f2.png

[image: image] https://user-images.githubusercontent.com/23367640/58838508-8bfedd00-8667-11e9-99b4-5d6203e7a5dd.png

[image: image] https://user-images.githubusercontent.com/23367640/58838554-b6509a80-8667-11e9-82bb-a252cb73a9bf.png

[image: image] https://user-images.githubusercontent.com/23367640/58838569-c1a3c600-8667-11e9-8ce2-aa31db8cb2ad.png

Something else funny, "Jurassic Park" (I think I've taken the original image from Pyimagesearch):

[image: image] https://user-images.githubusercontent.com/23367640/58838764-4db5ed80-8668-11e9-95cd-13b5fca5531f.png

Zoomed x 3

[image: image] https://user-images.githubusercontent.com/23367640/58838721-295a1100-8668-11e9-9df8-961c3a3e0e99.png Idea of how the traversal goes

[image: image] https://user-images.githubusercontent.com/23367640/58839052-2875af00-8669-11e9-8e8a-60069dea38e8.png

[image: image] https://user-images.githubusercontent.com/23367640/58839056-2e6b9000-8669-11e9-9668-c121d26e65a7.png

[image: image] https://user-images.githubusercontent.com/23367640/58839059-31ff1700-8669-11e9-817b-9d2e5b4146f9.png

[image: image] https://user-images.githubusercontent.com/23367640/58839064-35929e00-8669-11e9-9f7b-dda818364be4.png

[image: image] https://user-images.githubusercontent.com/23367640/58839068-39262500-8669-11e9-9b67-d6f36279888f.png

[image: image] https://user-images.githubusercontent.com/23367640/58839110-68d52d00-8669-11e9-8034-631fe847758b.png

[image: image] https://user-images.githubusercontent.com/23367640/58839118-6f63a480-8669-11e9-8d08-a8b642408479.png

[image: image] https://user-images.githubusercontent.com/23367640/58839126-75598580-8669-11e9-9e02-9f93f6f354fb.png

[image: image] https://user-images.githubusercontent.com/23367640/58839131-78ed0c80-8669-11e9-9a7c-f852197fe4d6.png

[image: image] https://user-images.githubusercontent.com/23367640/58839144-7d192a00-8669-11e9-8b10-a6c349abab43.png

[image: image] https://user-images.githubusercontent.com/23367640/58839151-80141a80-8669-11e9-83ba-b8df238e73fe.png

[image: image] https://user-images.githubusercontent.com/23367640/58839156-83a7a180-8669-11e9-8888-bce7c5b5efd9.png

[image: image] https://user-images.githubusercontent.com/23367640/58839163-86a29200-8669-11e9-9d3c-c8070c290ae6.png

Etc...

Top-down and left-right.

Also a beginning of the borders (it should be not on every line, though, but around segments)

[image: image] https://user-images.githubusercontent.com/23367640/58839313-09c3e800-866a-11e9-86cc-ee075356450e.png

[image: image] https://user-images.githubusercontent.com/23367640/58839921-6a542480-866c-11e9-9748-4acb1dfebb66.png

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/32?email_source=notifications&email_token=AFABOGP567FHBHJ5DCY6CYDPYWQH3A5CNFSM4HSAZNLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODW26DBI#issuecomment-498459013, or mute the thread https://github.com/notifications/unsubscribe-auth/AFABOGICU7ULTEFIDTNMSPLPYWQH3ANCNFSM4HSAZNLA .

khanh93vn commented 5 years ago

Cheers! I apologies in advance if some of the below are incorrect.

Please note that by Boris' definition, a composite structure include a sequence of lower structure, so that relative positions are preserved. P store a sequence of "dert"/"derts" (dert/derts), segment store a sequence of P (Py_).

Another thing should be noted is that P could be formed in series (one instance of incomplete P at a time) while segment must have multiple incompleted instances at the same time. This lead to difference in object() forming: P are formed at termination >< segments are formed at initialization to distinguish between instances.

Also, as there's no way we could know in advance if two separate Ps or two disconnected segments are of the same blob. I could think of 2 ways of doing this:

Process the whole frame, form a graph with segments as nodes, connections ("fork_" and "roots" ?) as edges. Use search techniques to form blobs
Initialize blob object instance (list) along with each new segment initilization (the one with no connected upper P). blob and segment instances have a pointer to each other. When a connection between 2 segments is detected, their 2 blobs are merged using above pointers.

Considering the three points above, when there's a bridge, three things will happen:

Initialize a new segment which contain the currently processed horizontal pattern.
All segments that contain adjacent connected horizontal patterns (each incompleted segment contains one and only one horizontal pattern) are terminated if they haven't already been.
The blobs containing segments' mentioned above are merged if haven't already been.

khanh93vn commented 5 years ago

I'm not exactly sure but the ones with horizontal stripes suggest that it has bugs somewhere. In my cases, those often has to do with P terminations.

Are the pictures above reconstructed from blobs or from gradients?

I suggest using a picture with pixels computed from partitioned gradients for debugging references.

khanh93vn commented 5 years ago

Here's a simple case of it:

segments

blob

Twenkid commented 5 years ago

@boris-kz

Please start with Julia.

OK, motivate me to work on that.

As of C++ - I don't think so. It rather kept me interested, for plenty of reasons - see above.

Twenkid commented 5 years ago

Thanks, Khan, a great illustration!

What do you mean by partitioned gradients? dx, dy? I produce and have these pictures during the run, too.

Are the pictures above reconstructed from blobs or from gradients?|

Depends which ones. Mine are not yet completely your segments. The ones regarding the segments are from segment-like structures: sequences of vertically adjacent same-sign P, single-connected, like Py_. No blob-merging there. I experimented with exhaustive traversal etc.

Please note that by Boris' definition, a composite structure include a sequence of lower structure, so >that relative positions are preserved. P store a sequence of "dert"/"derts" (dert/derts), segment store a >sequence of P (Py_).

Yes, that is what I do, too. Collecting connected components.

I'm not exactly sure but the ones with horizontal stripes suggest that it has bugs somewhere. In my cases, those often has to do with P terminations.

Well, that's right, as I mentioned, it is not correct by definition, since it doesn't follow the way you traverse them yet. Yours seems BFS, fed line-by-line, with those intermediate open segs etc. Mine above is DFS and is greedy and somewhat simpler, with only one recursive function which is fed not by a row of Ps, but with a container with all remaining lines (a deque of deques) from which it picks elements and removes them when they are cleared. It doesn't take care for the multiple forks in a delayed fashion and interrupts the search immediately ("terminates" the pattern), then starts another sequence by picking another P, and it doesn't revisit the intermediate sequences for continuation, so they are not merged afterwards. This is like a one-pass-per-segment-blob search.

Another thing should be noted is that P could be formed in series (one instance of incomplete P at a >time) while segment must have multiple incompleted instances at the same time. This lead to difference >in object() forming: P are formed at termination >< segments are formed at initialization to >distinguish between instances.

That reminds me of problems with "tracking", instance ids and references. :)

Also, as there's no way we could know in advance if two separate Ps or two disconnected segments are of the same blob. I could think of 2 ways of doing this:

Process the whole frame, form a graph with segments as nodes, connections ("fork_" and "roots" ?) as edges. Use search techniques to form blobs

Initialize blob object instance (list) along with each new segment initilization (the one with no connected upper P). blob and segment instances have a pointer to each other. When a connection between 2 segments is detected, their 2 blobs are merged using above pointers.

Sounds good. For big images with lines having many Ps there could be some hashing for faster search or bi-directional, for playing.

Considering the three points above, when there's a bridge, three things will happen:

Initialize a new segment which contain the currently processed horizontal pattern.

All segments that contain adjacent connected horizontal patterns (each incompleted segment contains one and only one horizontal pattern) are terminated if they haven't already been.

The blobs containing segments' mentioned above are merged if haven't already been.

OK, thanks.

boris-kz commented 5 years ago

Motivate me.

On Tue, Jun 4, 2019, 3:11 AM Todor Arnaudov notifications@github.com wrote:

@boris-kz https://github.com/boris-kz

Please start with Julia.

OK, motivate me to work on that.

As of C++ - I don't think so. It rather kept me interested, for plenty of reasons - see above.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/32?email_source=notifications&email_token=AFABOGJXBRHFAOJK24HCRULPYYITHA5CNFSM4HSAZNLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODW3UOQI#issuecomment-498550593, or mute the thread https://github.com/notifications/unsubscribe-auth/AFABOGK4MPVM7SOKEB2F5A3PYYITHANCNFSM4HSAZNLA .

Twenkid commented 5 years ago

OK, some day, sooner or later.

BTW we are funny. We don't even have an office room 3 x 3 m, it is too expensive :))), no powerful computers, (PCs) can't hire new developers etc. and we are practically volunteering - we must have a will of steel to focus on this instead of something else.

Yet our CEO and CTO (of the team of three) have huge demands for beating the competition, and assumes the conditions are fine - just focus-pocus and keep volunteering.

(Not that I don't believe in the project, though, "the crazy ones ... are the ones who do ..." :)) But it is too crazy. )

https://youtu.be/8rwsuXHA7RA

boris-kz commented 5 years ago

Steve Jobs was a commercial hack and hustler. We are not building a company or a product. The only fit analogy to what we are trying to do is the emergence of life. Too crazy? Tough.

On Tue, Jun 4, 2019 at 7:15 AM Todor Arnaudov notifications@github.com wrote:

OK, some day, sooner or later.

BTW we are funny. We don't even have an office room 3 x 3 m, it is too expensive :))), no powerful computers, (PCs) can't hire new developers etc. and we are practically volunteering - we must have a will of steel to focus on this instead of something else.

Yet our CEO and CTO (of the team of three) have huge demands for beating the competition, and assumes the conditions are fine - just focus-pocus and keep volunteering.

(Not that I don't believe in the project, though, "the crazy ones ... are the ones who do ..." :)) But it is too crazy. )

https://youtu.be/8rwsuXHA7RA

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/32?email_source=notifications&email_token=AFABOGMHTX2MDDRW3WADX7LPYZFFVA5CNFSM4HSAZNLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODW4HQGY#issuecomment-498628635, or mute the thread https://github.com/notifications/unsubscribe-auth/AFABOGPVH6GYDW23UI4U5A3PYZFFVANCNFSM4HSAZNLA .

Twenkid commented 5 years ago

Boris, I didn't give Jobs personally as an example, I quoted what he said in the ad and it was supportive for us. And we are not building ... - but it may help if (some of us) do.

Tough - right, but the "crazy" part is regarding the competition and our resources with which we believe we are set to create that emergent artificial life. Realizing its craziness is healthy, considering that the biggest company which is explicitly after AGI is having 700 employees, 400 PhDs (in an interview), they have all the data in the world and endless computing power and they steadily progress, and it is not just them.

As of Jobs, IMO he was a bit "crazy", only in the beginning with Apple I and II, and not that crazy. Later it was innovative for the market, but that was business made with enough resources and plenty of man-power - what we lack.

Wozniak's design was ingenious at the time, but it was engineering on a relatively small scale. Then it was supported by Microsoft's excellent BASIC in Apple][ - again a technical achievement requiring a lot of talent, developed cheaply by a few developers at Microsoft, but it was also "engineering", relatively small scale and clearly doable, done at the right time before the others. Apple and Microsoft took the lead, because there wasn't big enough competition from the ones who had a lot of resources at the time.

However it is not the case now, maybe they had better working conditions - at least offices, garages :), some customers. We're late by 15 years, considering that we possibly didn't have a lot of competition in the early 2000s, but were not focused or ready enough and we have had even less resources etc. than now. (...)

khanh93vn commented 5 years ago

The first man look like Einstein :D. Crazy one, that man.

Speaking of which, is there a single formula for /emergence of life/ ? /__/

boris-kz commented 5 years ago

Life is self-assisted replication, AKA differentiated phenotype. It has nothing to do with this project. I meant that emergence of substrate-independent intelligence, in terms of meta-evolution, can only be compared to the emergence of life. But, we digress. Todor, get a grip.

On Wed, Jun 5, 2019 at 12:36 AM Khanh Nguyen notifications@github.com wrote:

The first man look like Einstein :D. Crazy one, that man.

Speaking of which, is there a single formula for /emergence of life/ ? /__/

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/32?email_source=notifications&email_token=AFABOGPXRSGYJW6U5CCCNUTPY47EXA5CNFSM4HSAZNLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODW6SMFI#issuecomment-498935317, or mute the thread https://github.com/notifications/unsubscribe-auth/AFABOGIXOEEZRDHPDI54J33PY47EXANCNFSM4HSAZNLA .

Twenkid commented 5 years ago

Boris, I'm cool, explaining the message you interpreted with a miss of a light year. You get serious with that so called "toughness". Playing tough is a hobby, but if the goal is also to get the job done, it's something else as well.

boris-kz commented 5 years ago

If the goal is to get the job done... Stay away from Todor.

On Thu, Jun 6, 2019 at 5:35 AM Todor Arnaudov notifications@github.com wrote:

Boris, I'm cool, explaining the message you interpreted with a miss of a light year. You get serious with that so called "toughness". Playing tough is a hobby, but if the goal is also to get the job done, it's something else as well.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/32?email_source=notifications&email_token=AFABOGKC636DOJWOVKV3U43PZDK55A5CNFSM4HSAZNLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXCJOOI#issuecomment-499423033, or mute the thread https://github.com/notifications/unsubscribe-auth/AFABOGJVGGMSBLOZL5A4HN3PZDK55ANCNFSM4HSAZNLA .

Twenkid commented 5 years ago

Right :)) you finally got it :)) - Yes, you have to create a proper company and work professionally, as long as you want the job done in a timely manner and accelerating.

Twenkid commented 5 years ago

SuperCogAlg progress - I switched to Khan's traversal. I managed to code it for 1-2 sessions a few days ago, but there are some mistakes that still need to be fixed.

Interactive display and inspection etc. are growing - it started to look like "clustering" already.

Videos:

Landscape, Plovdiv Hill: https://www.youtube.com/watch?v=KPHYL_m8eLw&feature=youtu.be

Text, web: https://www.youtube.com/watch?v=D-BI65oFyYs&list=PLBUZnebxMfafV_MQF6v1WuS4wqNT8KTHp

Super Contra video game: www.youtube.com/watch?v=vgtfiUssTmk/edit

khanh93vn commented 5 years ago

That is quite some work! BTW, what are those multi-colored regions?

Twenkid commented 5 years ago

Thanks! Which ones do you mean? Some of the multi-colored stuff show different blobs no matter their sign and was to show the sequence of formation.

They were also to help spot strange mistakes of one-pixel wide and one diff-sign away single-pixel patterns, which in the red-blue palette rendering with less steps had the same color, i.e. seemed merged (but they still may be not in some cases, depending on the color assignment).

I have to try some of these renderings with your code. BTW it is good you started using more named tuples.

The blobs would also be checked with the interactive part - pointing, showing and printing the blob and the ones around, their segments etc.

Could have some formal assertions to spot wrong blobs, eventually.

BTW, is the following true:

A correctly merged blobs in the whole frame should be like islands, in rectangular vertial adjacency (different blobs can be diagonally adjacent). Those islands are surrounded fully by diff-sign patterns or borders of the frame? (The Ps can't be horizontally touching other same-color Ps)

So in many cases the neg patterns should turn into one huge "background blob" after the first pass?

Possibly "leaking" to an internal region like with the Jurassic park (there is an interruption of the border-lines).

На пн, 10.06.2019 г., 9:58 Khanh Nguyen notifications@github.com написа:

That is quite some work! BTW, what are those multi-colored regions?

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/32?email_source=notifications&email_token=AFSI7WE2F4AWGA2BA47NN2LPZX3QBA5CNFSM4HSAZNLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXJCXPQ#issuecomment-500313022, or mute the thread https://github.com/notifications/unsubscribe-auth/AFSI7WFX2TSXQ4H6UCOKUFLPZX3QBANCNFSM4HSAZNLA .

boris-kz commented 5 years ago

BTW, is the following true:

A correctly merged blobs in the whole frame should be like islands, in rectangular vertial adjacency (different blobs can be diagonally adjacent). Those islands are surrounded fully by diff-sign patterns or borders of the frame? (The Ps can't be horizontally touching other same-color Ps)

So in many cases the neg patterns should turn into one huge "background blob" after the first pass?

Possibly "leaking" to an internal region like with the Jurassic park (there is an interruption of the border-lines).

Yes. we don't know in advance if specific blobs will be meaningful, After termination, they will be evaluated and cross-compared with adjacent blobs, Resulting below-average blobs will be merged into infra-blobs, which will be rescanned to form reduced-resolution fuzzy sub blobs. That is, gradient pixels of infra-blob will be cross-compared at incremented rng in 2x2 scheme. This is not in code yet.

Twenkid commented 5 years ago

Adjacent here is more vague - it would be a set of the "nearest" same-sign (or also diff-sign) blobs, where "nearest" could vary - nearest attributed pixel, nearest "center of gravity" and or geometrical center - which in case of convex blobs will be enclosed within the blobs' "islands", but for a non-convex blob the center could lay outside of it.

Also, these huge negative single-blobs covering the frame would encompass all other small neg-blobs, and in general there are many "nearest" (or the difference in distance would often be relatively small).

Gradient of same-frame-but-different-filter blobs

One other processing that seems meaningful to me is computing a set of frames of blobs with different filters. Then comparing and clustering these different-filters-blobs with near ("adjacent") coordinates (center of gravity, borders,...) and producing traces, trajectories between them which would reflect a bigger-range global pattern than the blobs per single filter.

I suspect this may produce results which are structurally related to comp_range or "sub blobs" or something.

The differential between these blobs may be similar to doing a sequential reduction-extension of the number of colors, smoothly enough, i.e. traversing the space of input-resolution. It looks like "posterize" effect which produces clear "blobs" . The borders of these "blobs" would traverse the shapes of the objects, especially smooth ones. Something like "waves of gradients".

It's obvious, though, since the time the artists started to draw with shades. Depth is depicted by the gradient of the difference of the intensity (or just the gradient of the intensity). Same-intensity (and/or low dx,dy,g) "negative blobs" are seen as "flat" regions or planes.

More complex light, reflections, translucence may make the picture more complex, but wherever there is too much brightness ("burned" regions), spatial information from the gradient is lost anyway.

If there is a strong reflection with little losses (mirror, flat surface), then it just represents the reflected depth. There are also perspective and other optical transformations, which however are not about these intensity gradients (except losses from lenses, distance etc.)

24-bit color:

16-bit color

16 shades 4-bit grayscale with dithering (suggesting some "fuzzy blobs"):

16-shades 4-bit grayscale without dithering:

Cuts in both dimensions:

14 shades, the bands are shifting (it would be better illustrated animated)

12 shades

Etc.

Each band would be a blob.

This is idealized figure, but it is more evident in real ones:

A cat:

https://leganerd.com/wp-content/uploads/2016/03/2-2.png https://leganerd.com/2016/04/06/dithering/

Blobs de-merging and emerging

2 colors

(...)

...

Close-up, 16 colors - an encompassing blob around the eye and the "sub-blobs":

Close-up, 2 colors

PS. Yes, this is in the input space, not gradient space.

These are old observations of mine, I tested it with image viewers/editors around 2013-2014 in the context of a single-image 3D-reconstruction, but I was not in a mood to turn that idea into a developed form at the time.

In this domain, I would generate these different input-resolution images efficiently using a library, command-line tools etc. then work in that new input space, forming those "blobs" directly in 2D, searching for same-color islands.

The blobs produced from lower input-resolution and the blobs with centers ~ matching in different input-resolution would confirm anchor super blobs (bigger aread) and convergence points or "attractors", where the smaller "sub-blos" would be attached. A counterpart is "extenders" or "radiators" or so - the contours of the blobs, forming the attractor, around which there are also thin contour-edge-blobs or "sub-blobs".

boris-kz commented 5 years ago

One other processing that seems meaningful to me is computing a set of frames of blobs with different filters. Then comparing and clustering these different-filters-blobs with near ("adjacent") coordinates (center of gravity, borders,...) and producing traces, trajectories between them which would reflect a bigger-range global pattern than the blobs per single filter.

I suspect this may produce results which are structurally related to comp_range or "sub blobs" or something.

This will be comparison between filter patterns (same-filter spans), which is pretty far down the road.

Twenkid commented 5 years ago

Can you make some sort of road map of intermediate functions etc. and estimates of development time, given current speed of progress and known future steps, some "worse case scenario"?

Twenkid commented 5 years ago

Also, thus a same-filter span is a frame of blobs (all kinds, sub-, inter-...)? Does your plan include the suggested comparison to a range of varying filters?

To me it seems as a procedure resembling basic pixel comparison - there is a filter space with power equal to input resolution (say 255), this is the resolution and coordinates of it. That space is traversed to produce same-filter-span patterns (frame of blobs and the following derived structures).

I know there must be feedback to adjust it, in another unfolding I assume that for basic feedback at least two comparands are needed, thus at least two filters/frames and comparing current with the previous, as in the stages of blob formation.

Also the smallest changes in the filter wouldn't produce a lot of a difference in the average case of visual input (in some special cases they would), so that is supposed to result in a negative feedback: smaller difference would generate bigger feedback in order to find more difference/novelty per comparison.

boris-kz commented 5 years ago

Project roadmap, with additional order of composition and complexity per step:

Frame_blobs: basic pixel comparison and blob formation, done
Intra_blob: recursive sub-blob formation, hopefully done in the next few months
CompP: comparison of multivariate 1D Ps -> recursive PP and higher formation (vectorization), currently a draft.
Comp_blob: similar to compP but for 2D structures, same for sub_blobs and lateral extension across frames, forming compositionally higher super_blobs.
Sequence_frames: 3D version of all prior steps over time, forming compositionally lower and higher temporal blobs, selective D-reduction to their axes, summed-tblob feedback to the following frames.
Comp_sequence: between same-filter frame sequences to define incrementally higher-order filters_of_filters, etc., via corresponding orders of feedback. This will be dimensionally-complete hierarchically recursive alg.

Depth will be discovered, although it may help to add it as an input parameter.

On Wed, Jun 12, 2019 at 6:09 AM Todor Arnaudov notifications@github.com wrote:

Also, thus a same-filter span is a frame of blobs (all kinds, sub-, inter-...)? Does your plan include the suggested comparison to a range of varying filters?

To me it seems as a procedure resembling basic pixel comparison - there is a filter space with power equal to input resolution (say 255), this is the resolution and coordinates of it. That space is traversed to produce same-filter-span patterns (frame of blobs and the following derived structures).

I know there must be feedback to adjust it, in another unfolding I assume that for basic feedback at least two comparands are needed, thus at least two filters/frames and comparing current with the previous, as in the stages of blob formation.

Also the smallest changes in the filter wouldn't produce a lot of a difference in the average case of visual input (in some special cases they would), so that is supposed to result in a negative feedback: smaller difference would generate bigger feedback in order to find more difference/novelty per comparison.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/32?email_source=notifications&email_token=AFABOGJ2PNJ6DREPITJBSYDP2DDPLA5CNFSM4HSAZNLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXP5LOI#issuecomment-501208505, or mute the thread https://github.com/notifications/unsubscribe-auth/AFABOGLI7VDMLIRIRQPDTHTP2DDPLANCNFSM4HSAZNLA .

Twenkid commented 5 years ago

Blobs from the Py version, on Contra image: https://user-images.githubusercontent.com/23367640/58837539-85229b00-8664-11e9-9106-ed48069e89cb.png

ave = 25 (to be similar to my tests above) on the blue channel:

The huge background blob is merged. :)

Compared to current mine:

It seems Py version is fast.

Code: https://github.com/Twenkid/CogAlg/blob/master/frame_blobs.py

I guess your blob-lines up left are thicker than current mine, due to the double-comparison, mine is one-sided, unless it's something with rendering and merging. I prefer the thinner version.

boris-kz commented 5 years ago

Thanks. The reason for bilateral comp is to avoid bias: results from unilateral comp depend on the direction of scanning. That's because the signs of dx and dy are lost when computing g. Anyway, frame_blobs is an intermediate step, it's not meant to form accurate blobs on its own. If you want accuracy, compute hypot_g. And current version is obsolete, we are switching to 2x2 comp first, 3x3 comp in deeper layers. None of that is novel, the original part is summing params per P and blob, for comparison in comp_P and comp_blob.

On Thu, Jun 13, 2019 at 2:45 PM Todor Arnaudov notifications@github.com wrote:

Blobs from the Py version, on Contra image: https://user-images.githubusercontent.com/23367640/58837539-85229b00-8664-11e9-9106-ed48069e89cb.png

ave = 25 (to be similar to my tests above) on the blue channel:

[image: image] https://user-images.githubusercontent.com/23367640/59457392-f7dc0500-8e20-11e9-9177-5c0e2d16687e.png

The huge background blob is merged. :)

[image: image] https://user-images.githubusercontent.com/23367640/59454969-ea704c00-8e1b-11e9-8e3d-e02b7fffcefd.png

Compared to current mine:

[image: image] https://user-images.githubusercontent.com/23367640/59458415-117e4c00-8e23-11e9-924b-e1771c2ad235.png

It seems Py version is fast.

Code: https://github.com/Twenkid/CogAlg/blob/master/frame_blobs.py

I guess your blob-lines up left are thicker than current mine, due to the double-comparison, mine is one-sided, unless it's something with rendering and merging. I prefer the thinner version.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/32?email_source=notifications&email_token=AFABOGPTKFFOP43UBDYBWYDP2KIULA5CNFSM4HSAZNLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXUVURQ#issuecomment-501832262, or mute the thread https://github.com/notifications/unsubscribe-auth/AFABOGIHJMZCA6YWD2I352DP2KIULANCNFSM4HSAZNLA .

Twenkid commented 5 years ago

The reason for bilateral comp is to avoid bias: results from unilateral comp depend on the direction of scanning. That's because the signs of dx and dy are lost when computing g.

But the dx,dy themselves are preserved and the comp is applied the same way over the whole image, the bias doesn't matter IMO.

Anyway, frame_blobs is an intermediate step, it's not meant to form accurate blobs on its own.

I know, it's preliminary, then blobs are supposed to be partitioned in subblobs and thinned anyway.

If you want accuracy, compute hypot_g.

And current version is obsolete, we are switching to 2x2 comp first, 3x3 comp in deeper layers.

OK, getting closer to convolutions.

None of that is novel, the original part is summing params per P and blob, for comparison in comp_P and comp_blob.

I know it's like classic image processing, the lowest level resembled Sobel and Hough transform etc. Line tracing etc. are also classic stuff. IMO CogAlg seems more akin to the classic Computer Vision and Topology (continuity, partitioning), rather than DNN.

The tracing, connectedness, sub-blobs which may result in "thinning" (morphological operations, like erode vs. dilate) remind me also of a book from a conference called "Discrete Geometry for Computer Imagery".

On Thu, Jun 13, 2019 at 2:45 PM Todor Arnaudov notifications@github.com

wrote:

Blobs from the Py version, on Contra image:

https://user-images.githubusercontent.com/23367640/58837539-85229b00-8664-11e9-9106-ed48069e89cb.png

ave = 25 (to be similar to my tests above) on the blue channel:

[image: image] < https://user-images.githubusercontent.com/23367640/59457392-f7dc0500-8e20-11e9-9177-5c0e2d16687e.png

The huge background blob is merged. :)

[image: image] < https://user-images.githubusercontent.com/23367640/59454969-ea704c00-8e1b-11e9-8e3d-e02b7fffcefd.png

Compared to current mine:

[image: image] < https://user-images.githubusercontent.com/23367640/59458415-117e4c00-8e23-11e9-924b-e1771c2ad235.png

It seems Py version is fast.

Code: https://github.com/Twenkid/CogAlg/blob/master/frame_blobs.py

I guess your blob-lines up left are thicker than current mine, due to the double-comparison, mine is one-sided, unless it's something with rendering and merging. I prefer the thinner version.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub < https://github.com/boris-kz/CogAlg/issues/32?email_source=notifications&email_token=AFABOGPTKFFOP43UBDYBWYDP2KIULA5CNFSM4HSAZNLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXUVURQ#issuecomment-501832262 , or mute the thread < https://github.com/notifications/unsubscribe-auth/AFABOGIHJMZCA6YWD2I352DP2KIULANCNFSM4HSAZNLA

.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/boris-kz/CogAlg/issues/32?email_source=notifications&email_token=AFSI7WD5C3BVBBO2ZK6SDXTP2K47HA5CNFSM4HSAZNLKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXVDOJI#issuecomment-501888805, or mute the thread https://github.com/notifications/unsubscribe-auth/AFSI7WEJRT6ADRTMCTFXCYTP2K47HANCNFSM4HSAZNLA .

boris-kz commented 5 years ago

The reason for bilateral comp is to avoid bias: results from unilateral comp depend on the direction of scanning. That's because the signs of dx and dy are lost when computing g.

But the dx,dy themselves are preserved and the comp is applied the same way over the whole image, the bias doesn't matter IMO.

What I mean is that same-location (between pixels) g will be different for right-and-down vs. left-and-up scans. In general, g is supposed to be a combined representation of 4 quadrants, but unilateral only covers one. So, 2x2 diagonal g = right-and-down g + left-and-up g, which makes it omnidirectional. This is different from 2x2 orthogonal g in current frame_blobs.

I know it's like classic image processing, the lowest level resembled Sobel and Hough transform etc. Line tracing etc. are also classic stuff. IMO CogAlg seems more akin to the classic Computer Vision and Topology (continuity, partitioning), rather than DNN.

Both higher levels of CogAlg and DNN operate on top of classical stuff, but in CogAlg this extension is supposed to be organic. We preserve resolution of derived parameters, and increase range and derivation depending on their value, while DNN mutates them atrociously.

Twenkid commented 5 years ago

I realized one other reason for the thicker line - the ave had to be adjusted. 2*25 makes the lines more comparable to 25 unilateral (not 1:1). It looks like that with finer details:

Like "erode" operation to lower g, which is "dilate". Hypot with the same ave is even stronger erode (g = np.hypot(dy, dx__) - ave over the bilateral dx, dy )

BTW, the green "sparkles" on the margin rows and columns are from the original image, I render over it in order to spot gaps.

Performance test abs/hypot ...

Not max speed (little debug output, display of images, without the final rendering), but it's the same for both:

Source: the raccoon, grayscale.

ave=25, hypot, 25337 blobs, 10.586164236068726 s

ave = 30, hypot, 10.086822509765625 Terminated blobs 22121

Actually using: abs(...) instead of hypot doesn't appear to make significant difference (or hypot is even faster, depending on the blobs).

The abs with ave = 50: Terminated blobs 18814, 9.637019157409668 s (too much lost details)

ave = 37.5, abs(...) , 10.730221033096313

Terminated blobs 23173

One unilateral (if correct) comparison, g = 25, hypot, 9.8601553440094 Terminated blobs 15876

    dx1 = p__[1:-1, 0:-2]
    dx2 = p__[1:-1, 1:-1]
    dx__ = dx2-dx1

    dy1 = p__[0:-2, 1:-1]
    dy2 = p__[1:-1, 1:-1]
    dy__ = dy2 - dy1;

ave = 12, 12.260122299194336 sec, Terminated blobs 26582

Twenkid commented 5 years ago

I think some small variation in the evaluation at the lowest levels won't matter much in the higher levels as long as scanning is consistent and it captures continuity, discontinuity, intensity, length, angles etc. The feedback is to compensate for these differences.

Yes, the convolutions in DNN with appropriate kernels work like Sobel, Hough etc., but the NN parameters are implicit, encoded within the intermediate layers of weights which are all images. Here, at least at the start, there are explicit and separately addressable parameters (not just the images) - such as coordinates, gradients, lengths, angles, counts etc. which is more "classical".

boris-kz commented 5 years ago

That's cool, thanks.

Actually using: abs(...) instead of hypot doesn't appear to make significant difference (or is even faster).

Good to know. I guess in python most of computation is on objects, It should be different in faster languages.

Twenkid commented 5 years ago

Actually using: abs(...) instead of hypot doesn't appear to make significant difference (or is even faster).

Good to know. I guess in python most of computation is on objects, It should be different in faster languages.

Probably, if just doing many hypot/vs abs(a)+abs(d), but there's a lot of overhead anyway due to calls, stack, memory accesses and dynamic memory operations etc.

When timing there:

global start_time
t = time() - start_time
print("before y in range...", t)

for y in range(1, height - 1):  # first and last row are discarded
    P_ = form_P_(dert__[y])  # horizontal clustering

For just one run with the raccoon, it's randomly about 0.05-0.06 s.

Twenkid commented 5 years ago

SuperCogAlg now terminates and merges the blobs correctly in C++!

1. Super Contra

2. Jurassic Park Logo

3. The Youth Hill in Plovdiv

4. Web/Text example

The scipy raccoon image

1. Horizontal clusering Ps:

ave = 25, g = abs((dx)+abs(dy) (No kernels, now I have been building the proper structure.)

2. Blobs

3. Details:

For a visual inspection - with a pipette tool, the smallest difference per color is 2 steps (e.g. RGB (64,0,0), (66,0,0), ... for positive and respectively (0,0,68), (0,0,70)) for negative blobs, the minimum is not 0 in order to keep the color information noticeable.

Bonus:

Visualization of the Blob Formation process

The Python traversal:

https://youtu.be/9dFG6Z67_tE

In the original video (here some detail is lost) each frame draws one segment and when a blob is terminated, it's drawn entirely with a brighter shade and held for several frames.

The video is produced with a modified PyCogAlg.